MDLinkImpl:
CEDAR
PROGRAM
IMPORTS
Basics, IO,
MDGlobalVars, MDOps, MDUtils
= BEGIN OPEN MDDefs, MDGlobalVars, Basics;
SetupLinks begins with the data structure left by Load, which describes what each instruction does (GOTO, CALL, BRANCH, RETURN, or CORETURN). It builds the linkages and other information which will be needed by the various allocation procedures that execute later as follows:
1. Propagates IFU entry restriction from IFU entries to the target instructions.
2. Propagates GOTO-target and CALL-target information from goers to goees and callers to callees.
3. Propagates xor1 constraints to targets of conditional jumps.
4. Points jbc instructions at their targets.
5. Points other branches at their targets.
All the above information is encoded in a mask which represents possible locations of the instruction within a group of 20B; the bLink and aLink pointers as described in MakePlus1 & MakePageLink; and the jbcLinked, onPage, atWord, global, and IFUE flags and W0 field as described in MDDefs.
Note that SetupLinks assumes that InitialScan has already done a lot of constraint checking.
SetupLinks:
PUBLIC
PROC
RETURNS[ok:
BOOL] =
TRUSTED {
nW2Used: CARDINAL ← 0;
w2fIndex: CARDINAL ← 0;
m1: MDDefs.IMMask;
nGlobal: CARDINAL ← 0;
not77B: WORD = BITNOT[77B];
errorsThisPass: BOOL ← FALSE;
ok ← TRUE;
MDOps.Report[infoOnly, "Linking...\n"];
Reset mask and link fields
FOR i:
CARDINAL
IN [0..nInstructions)
DO
imPtr: IMRecordPtr = MDUtils.IMPtr[i];
w2: CARDINAL ← imPtr.word2.W2AddrAndbLink;
mask: WORD ← 177777B;
IF w2 # (i+1) THEN nW2Used ← nW2Used + 1;
Initialize mask
imPtr.links ← LOOPHOLE[i]; -- null aLink, not on any +1 list
IF imPtr.word0.brkPAndIFUE # 0
THEN {
IF imPtr.word0.globalAndIFUSeq = 0
THEN mask ← ifuMask
ELSE {
erx: BOOL;
imPtr.word0.brkPAndIFUE ← 0;
imPtr.word0.globalAndIFUSeq ← 0;
erx ← MakePlus1[i-1, i]; -- IFU sequence - aLink already initialized
ok ← ok AND erx;
};
};
SELECT
TRUE
FROM
imPtr.word0.atW0AndatWord = 1 => {
mask ← XMask[mask, imPtr.word0];
imPtr.word0.onPageAndPlaced ← 1;
imPtr.word0.atW0AndatWord ← 1;
IF
BITAND[
LOOPHOLE[imPtr.word0.W0Addr], globalZero] = 0
THEN {
imPtr.word0.globalAndIFUSeq ← 1;
nGlobal ← nGlobal + 1;
};
};
imPtr.word0.globalAndIFUSeq # 0 => {
mask ← BITAND[mask, globalMask];
imPtr.word0.W0Addr ← BITAND[imPtr.word0.W0Addr, BITNOT[77B]];
imPtr.word0.atW0AndatWord ← 1;
nGlobal ← nGlobal + 1;
};
ENDCASE => imPtr.word0.atW0AndatWord ← 0;
imPtr.mask ← mask;
ENDLOOP;
Check global constraints
IF nGlobal > nGlobalPages
THEN {
MDOps.Report[passFatal, " *** More than %g (%g) GLOBAL entries\n",
IO.card[nGlobalPages], IO.card[nGlobal] ];
RETURN[FALSE];
};
Put targets of conditionals and successors of calls on +1 lists
w2Fixups ← NEW[W2FixupRep[nW2Used]];
FOR i:
CARDINAL
IN [0 .. nInstructions)
DO
imPtr: IMRecordPtr = MDUtils.IMPtr[i];
w2Addr: CARDINAL ← imPtr.word2.W2AddrAndbLink;
IF w2Addr # (i+1)
THEN {
w2Fixups[w2fIndex] ← [imAddr: i, w2Value: w2Addr];
w2fIndex ← w2fIndex + 1;
};
imPtr.word2.W2AddrAndbLink ← i;
IF imPtr.word2.iscond = 1
THEN {
erx: BOOL;
erx ← MakePlus1[imPtr.word1.W1AddrAndGroupLink, w2Addr];
ok ← ok AND erx;
IF imPtr.word1.calls = 1
THEN {
-- DblCall, W2 unavailable for return address
erx ← MakePlus1[i, i+1];
ok ← ok AND erx;
};
}
ELSE
IF imPtr.word1.calls # 0
THEN {
erx: BOOL ← MakePlus1[i, w2Addr];
ok ← ok AND erx;
};
ENDLOOP;
Establish linkages by scan of IM
FOR i:
CARDINAL
IN [0 .. nInstructions)
DO
imPtr: MDDefs.IMRecordPtr = MDUtils.IMPtr[i];
w1Ptr: MDDefs.IMRecordPtr;
w1Addr: CARDINAL ← imPtr.word1.W1AddrAndGroupLink;
IF w1Addr = WExt THEN LOOP;
w1Ptr ← MDUtils.IMPtr[w1Addr];
Mark target of conditionals
IF imPtr.word2.iscond = 1
THEN
w1Ptr.mask ← BITAND[w1Ptr.mask, evenMask];
Propagate placement restrictions to callees and goees
IF imPtr.word2.goes = 1
THEN
w1Ptr.mask ← BITAND[w1Ptr.mask, MDDefs.goedtoMask]
ELSE
IF imPtr.word1.calls = 1
AND imPtr.word1.returns = 0
THEN --
not CORETURN
w1Ptr.mask ← BITAND[w1Ptr.mask, MDDefs.calledMask];
Merge the source and target into a common circular list through bLink. The bLink pointer is needed unless the instruction returns (W1 irrelevant) or does an unconditional long GOTO/CALL, or W1 is a global.
IF imPtr.word1.jbc = 1
THEN {
w1Ptr.mask ← BITAND[w1Ptr.mask, MDDefs.jbctMask];
MakePageLink[i, w1Addr];
}
ELSE
IF (imPtr.word1.returns = 0)
AND (w1Ptr.word0.globalAndIFUSeq = 0)
AND
((imPtr.word1.usesFN # 0) OR (imPtr.word2.iscond # 0)) THEN
MakePageLink[i, w1Addr];
ENDLOOP;
Process explicit mask and +1 constraints from IMMASK
m1 ← imMask;
UNTIL m1 =
NIL
DO
iAddr: CARDINAL ← m1.addr;
imPtr: MDDefs.IMRecordPtr = MDUtils.IMPtr[iAddr];
imPtr.mask ← BITAND[imPtr.mask, m1.mask];
FOR j:
CARDINAL
IN [1..m1.mSeq]
DO
erx: BOOL ← MakePlus1[iAddr, iAddr+1];
ok ← ok AND erx;
iAddr ← iAddr + 1;
ENDLOOP;
m1 ← m1.next;
ENDLOOP;
RETURN[ok];
};
MakeSubpageLink:
PUBLIC
PROC[i1, i2:
CARDINAL] =
TRUSTED {
Record the requirement that I1 and I2 be in the same subpage. This is done by patching the last bLink in I2's current subpage to point to the first instruction in I1's subpage, and setting jbcLinked in the last instruction in I2's subpage, and patching I1's old predecessor to point to I2's last's old successor.
If I1 and I2 are already in the same page, I1's subpage must be removed from the ring first.
i, i0, link0: CARDINAL;
ip0, ip2: IMRecordPtr;
sameRing: BOOL ← FALSE;
DO
ip2 ← MDUtils.IMPtr[i2];
IF ip2.links.jbcLinked = 0 THEN EXIT; -- end of I2's subpage
i2 ← ip2.word2.W2AddrAndbLink;
ENDLOOP;
i ← i1;
DO
ip: IMRecordPtr;
IF i = i2 THEN sameRing ← TRUE; -- found i2 in i1's ring
ip ← MDUtils.IMPtr[i];
IF ip.links.jbcLinked = 0 THEN i0 ← i; -- last end of subpage
i ← ip.word2.W2AddrAndbLink;
IF i = i1 THEN EXIT;
ENDLOOP;
ip0 ← MDUtils.IMPtr[i0];
link0 ← ip0.word2.W2AddrAndbLink; -- first instr in i1's subpage
IF sameRing
THEN {
-- remove i1's subpage from the ring
ip1: IMRecordPtr;
i1 ← link0; -- search entire page
DO
IF i1 = i2 THEN RETURN; -- already in same subpage
ip1 ← MDUtils.IMPtr[i1];
IF ip1.links.jbcLinked = 0 THEN EXIT; -- end of i1's subpage
i1 ← ip1.word2.W2AddrAndbLink;
ENDLOOP;
ip0.word2.W2AddrAndbLink ← ip1.word2.W2AddrAndbLink; -- remove from ring
ip1.word2.W2AddrAndbLink ← ip2.word2.W2AddrAndbLink;
}
ELSE
-- just splice rings together
ip0.word2.W2AddrAndbLink ← ip2.word2.W2AddrAndbLink;
ip2.word2.W2AddrAndbLink ← link0;
ip2.links.jbcLinked ← 1;
};
MakePageLink:
PROC[i1, i2:
CARDINAL] =
TRUSTED {
Record the requirement that I1 and I2 be in the same page. This is done with a circular chain through bLink. Groups of instructions which must be in the same subpage have jbcLinked set in all but the last one.
i: CARDINAL ← i2;
ip1: IMRecordPtr ← MDUtils.IMPtr[i1];
ip2: IMRecordPtr ← MDUtils.IMPtr[i2];
link1: CARDINAL;
DO
IF i = i1 THEN RETURN; -- i2 is already in i1's page
i ← MDUtils.IMPtr[i].word2.W2AddrAndbLink;
IF i = i2 THEN EXIT;
ENDLOOP;
DO
IF ip1.links.jbcLinked = 0 THEN EXIT;
i1 ← ip1.word2.W2AddrAndbLink;
ip1 ← MDUtils.IMPtr[i1];
ENDLOOP;
DO
IF ip2.links.jbcLinked = 0 THEN EXIT;
i2 ← ip2.word2.W2AddrAndbLink;
ip2 ← MDUtils.IMPtr[i2];
ENDLOOP;
Now splice the pages together
link1 ← ip1.word2.W2AddrAndbLink;
ip1.word2.W2AddrAndbLink ← ip2.word2.W2AddrAndbLink;
ip2.word2.W2AddrAndbLink ← link1;
};
XMask:
PROC[oldMask:
WORD, w0: W0Word]
RETURNS[
WORD] = {
shft: WORD = BITAND[LOOPHOLE[w0], 17B];
msk: WORD = BITSHIFT[100000B, -shft]; -- rshift
RETURN[BITAND[oldMask, msk]];
};
MakePlus1:
PROC[i1, i2:
CARDINAL]
RETURNS[ok:
BOOL]=
TRUSTED {
Record the requirement that I2 be placed at the location following I1 (in the same page) by linking them together through their aLink fields. This is a circular chain with aLinked set in all but the first item. Error if I1 already has a link-from or I2 has a link-to.
ip1: IMRecordPtr = MDUtils.IMPtr[i1];
ip2: IMRecordPtr ← MDUtils.IMPtr[i2];
ok ← TRUE;
IF ip1.links.aLink = i2
THEN {
IF (ip2.links.aLinked = 0)
THEN {
MDOps.Report[infoOnly,
" *** %g....must both precede and follow %g\n", IO.card[i1], IO.card[i2] ];
ok ← FALSE;
};
RETURN;
};
IF MDUtils.IMPtr[ip1.links.aLink].links.aLinked = 1
THEN {
ErrPlus1[i1, i2, "former already has a link to", ip1.links.aLink];
ok ← FALSE;
};
IF ip2.links.aLinked = 1
THEN {
-- Find predecessor of I2
i3: CARDINAL ← i2;
DO
ip3: IMRecordPtr = MDUtils.IMPtr[i3];
IF ip3.links.aLink = i2 THEN EXIT;
i3 ← ip3.links.aLink;
ENDLOOP;
ErrPlus1[ i1, i2, "latter already has a link from", i3];
ok ← FALSE;
};
IF ok
THEN {
link1: CARDINAL ← ip1.links.aLink; -- beginning of chain
ip1.links.aLink ← i2;
ip2.links.aLinked ← 1;
WHILE ip2.links.aLink # i2
DO
-- find end of chain
ip2 ← MDUtils.IMPtr[ip2.links.aLink];
ENDLOOP;
ip2.links.aLink ← link1;
};
};
ErrPlus1:
PROC[i1, i2:
CARDINAL, msg:
ROPE, i3:
CARDINAL] = {
MDOps.Report[passFatal,
"Attempted +1 link from %g to %g;\n the %g %g\n",
IO.card[i1], IO.card[i2], IO.rope[msg], IO.card[i3] ];
};
debugging routines
Fbl:
PROC[start:
CARDINAL]
RETURNS[
ROPE] =
TRUSTED {
count: CARDINAL ← 0;
i: CARDINAL ← start;
DO
imPtr: IMRecordPtr ← MDUtils.IMPtr[i];
i ← imPtr.word2.W2AddrAndbLink;
IF i = start THEN RETURN["ok\n"];
count ← count + 1;
IF count > DoradoPageSize THEN RETURN["List Too Long"];
ENDLOOP;
};
END.