DIRECTORY Basics, IO, Rope, MDDefs, MDGlobalVars, MDOps, MDUtils; MDLinkImpl: CEDAR PROGRAM IMPORTS Basics, IO, MDGlobalVars, MDOps, MDUtils EXPORTS MDOps, MDUtils = BEGIN OPEN MDDefs, MDGlobalVars, Basics; 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"]; 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; 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; IF nGlobal > nGlobalPages THEN { MDOps.Report[passFatal, " *** More than %g (%g) GLOBAL entries\n", IO.card[nGlobalPages], IO.card[nGlobal] ]; RETURN[FALSE]; }; 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; 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]; IF imPtr.word2.iscond = 1 THEN w1Ptr.mask _ BITAND[w1Ptr.mask, evenMask]; 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]; 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; 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 { 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 { 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; 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 { 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] ]; }; 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. MDLinkImpl.mesa Copyright c 1986 by Xerox Corporation. All rights reserved. Willie-Sue, May 5, 1986 12:55:17 pm PDT taken from mdlink.bcpl 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. Reset mask and link fields Initialize mask Check global constraints Put targets of conditionals and successors of calls on +1 lists Establish linkages by scan of IM Mark target of conditionals Propagate placement restrictions to callees and goees 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. Process explicit mask and +1 constraints from IMMASK 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. 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. Now splice the pages together 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. debugging routines Ê ˜šœ™Icodešœ Ïmœ1™Jšœ ˜ J˜J˜—J˜—šœ$˜$Jšœžœ˜ Jšœžœžœ˜=Jšœ˜J˜J˜—Jšžœ"˜)—Jšœ˜Jšžœ˜—J™šžœžœ˜ ˜BJšžœžœ˜*—Jšžœžœ˜J˜—J˜J™?Jšœ žœ˜$šžœžœžœž˜*J˜&Jšœžœ˜.J˜šžœžœ˜Jšœ2˜2Jšœ˜J˜—Jšœ˜šžœžœ˜ Jšœžœ˜ Jšœ8˜8Jšœžœ˜šžœžœ -˜MJšœ˜Jšœžœ˜J˜—J˜šžœžœžœ˜$Jšœžœ˜!Jšœžœ˜J˜——J˜Jšžœ˜—J˜J™ šžœžœžœž˜*J˜-J˜Jšœžœ"˜2J˜Jšžœžœžœ˜J˜Jšœ˜J™J™šžœž˜Jšœ žœ˜*—J˜J™5šžœž˜Jšœ žœ˜2šžœžœžœž  ˜NJšœ žœ ˜3——J˜J™Íšžœžœ˜Jšœ žœ˜1J˜J˜šžœžœžœ#ž˜KJšœžœž˜;Jšœ˜——J˜Jšžœ˜—J˜J™4J˜ šžœžœž˜Jšœžœ ˜J˜1Jšœ žœ˜)šžœžœžœž˜"Jšœžœ˜&Jšœžœ˜J˜Jšžœ˜—J˜ Jšžœ˜—J˜Jšžœ˜ J˜—J˜š Ÿœžœžœ žœžœ˜:J™¹J™\Jšœžœ˜J˜Jšœ žœžœ˜J˜šž˜J˜Jšžœžœžœ ˜J™J™J˜%J˜%Jšœžœ˜ J˜šžœžœ˜šžœžœ˜!˜Jšœ0žœ žœ ˜K—Jšœžœ˜ J˜—Jšžœ˜J˜—J˜šžœ2žœ˜:J˜BJšœžœ˜ J˜—šžœžœ ˜:Jšœžœ˜šž˜J˜%Jšžœžœžœ˜"Jšœ˜Jšžœ˜—J˜8Jšœžœ˜ J˜—J˜šžœžœ˜ Jšœžœ ˜9J˜J˜šžœžœ ˜3J˜%Jšžœ˜—J˜J˜—J˜—J˜š Ÿœžœ žœžœžœ˜=˜˜3Jšžœ žœ žœ žœ ˜6——J˜—J˜Jšœ™J™š Ÿœžœžœžœžœžœ˜4Jšœžœ˜Jšœžœ ˜šž˜J˜&Jšœ˜Jšžœ žœžœ ˜!J˜Jšžœžœžœ˜7Jšžœ˜—J˜—J˜Jšžœ˜——…—Þ.ÿ