DIRECTORY Basics, IO, Rope, MDDefs, MDGlobalVars, MDOps, MDUtils; MDAListImpl: CEDAR PROGRAM IMPORTS Basics, IO, MDGlobalVars, MDOps, MDUtils EXPORTS MDOps, MDUtils = BEGIN OPEN MDDefs, MDGlobalVars; maxAlist: CARDINAL = 16; -- must fit on subpage BuildALists: PUBLIC PROC RETURNS[ok: BOOL] = { MDOps.Report[infoOnly, "Building allocation lists...\n"]; IF ~CheckAlists[] THEN RETURN[FALSE]; IF ~CheckRings[] THEN RETURN[FALSE]; RETURN[TRUE]; }; CheckAlists: PROC RETURNS[ok: BOOL] = TRUSTED { alistTab: ARRAY [0..maxAlist) OF CARDINAL _ ALL[0]; FOR i: CARDINAL IN [0 .. nInstructions) DO imPtr: IMRecordPtr _ MDUtils.IMPtr[i]; mask: WORD _ 177777B; length: CARDINAL _ 0; ni: CARDINAL _ i; wordFlag, pageFlag: BOOL _ FALSE; absPage, absWord: CARDINAL _ 0; -- Absolute address of list head IF imPtr.links.aLink = i THEN { -- common special case IF imPtr.mask = 0 THEN MDOps.Report[passFatal, "%g....Too many constraints\n", IO.card[i]]; LOOP; }; IF imPtr.links.aLinked = 1 THEN LOOP; -- Not an alist head DO IF imPtr.word0.atW0AndatWord = 1 THEN { word0: CARDINAL = CardAnd[imPtr.word0.W0Addr-length, WordMask]; IF wordFlag THEN IF word0 # absWord THEN { xAddr: CARDINAL = CardAnd[imPtr.word0.W0Addr, WordMask]; aAddr: CARDINAL = CardAnd[absWord+length, WordMask]; MDOps.Report[passFatal, "%g....Attempt to place at both word %g and %g\n", IO.card[i], IO.card[xAddr], IO.card[aAddr] ]; }; wordFlag _ TRUE; absWord _ word0; }; IF imPtr.word0.onPageAndPlaced = 1 THEN { page: CARDINAL = CardAnd[imPtr.word0.W0Addr, PageMask]; IF pageFlag THEN IF page # absPage THEN MDOps.Report[passFatal, "%g....Attempt to place on both page %g and %g\n", IO.card[i], IO.card[page], IO.card[absPage] ]; pageFlag _ TRUE; absPage _ page; }; IF length = maxAlist THEN { MDOps.Report[passFatal, "%g....+1 list longer than 20B\n", IO.card[i]]; EXIT; }; alistTab[length] _ ni; length _ length + 1; mask _ Rcy1[mask, imPtr.mask]; IF mask = 0 THEN MDOps.Report[passFatal, "%g....Impossible allocation list constraints\n", IO.card[i]]; ni _ imPtr.links.aLink; IF ni = i THEN EXIT; -- end of list imPtr _ MDUtils.IMPtr[ni]; ENDLOOP; FOR j: CARDINAL DECREASING IN [0 .. length) DO i: CARDINAL _ alistTab[j]; imPtr: IMRecordPtr = MDUtils.IMPtr[i]; imPtr.mask _ mask; IF wordFlag THEN { imPtr.word0.W0Addr _ CardAnd[imPtr.word0.W0Addr, PageMask] + CardAnd[absWord+j, WordMask]; imPtr.word0.atW0AndatWord _ 1; }; IF pageFlag THEN { imPtr.word0.W0Addr _ absPage + CardAnd[imPtr.word0.W0Addr, WordMask]; imPtr.word0.onPageAndPlaced _ 1; }; IF j # 0 THEN MDUtils.MakeSubpageLink[alistTab[j-1], i]; -- Force +1 list onto subpage mask _ Lcy1[mask]; ENDLOOP; ENDLOOP; RETURN[TRUE]; }; CheckRings: PROC RETURNS[ok: BOOL] = TRUSTED { pageVec: ARRAY [0..maxnPages) OF CARDINAL _ ALL[177777B]; errFlag: BOOL _ FALSE; FOR i: CARDINAL IN [0 .. nInstructions) DO MDUtils.IMPtr[i].word2.branchesAndMarked _ 0; ENDLOOP; FOR i: CARDINAL IN [0 .. nInstructions) DO imPtr: IMRecordPtr = MDUtils.IMPtr[i]; i1, i2, addr1, addr2, page: CARDINAL; ip1, ip2: IMRecordPtr; IF imPtr.word2.branchesAndMarked = 1 THEN LOOP; -- already seen IF imPtr.word0.onPageAndPlaced = 0 THEN LOOP; -- don't start here i1 _ i; ip1 _ imPtr; DO ip1.word2.branchesAndMarked _ 1; i2 _ ip1.word2.W2AddrAndbLink; ip2 _ MDUtils.IMPtr[i2]; addr1 _ ip1.word0.W0Addr; addr2 _ ip2.word0.W0Addr; IF ip2.word0.onPageAndPlaced = 1 THEN { -- check for compatibility IF CardAnd[addr1, PageMask] # CardAnd[addr2, PageMask] THEN errFlag _ TRUE; } ELSE { -- propagate ip2.word0.W0Addr _ addr2 + CardAnd[(addr1-addr2), PageMask]; ip2.word0.onPageAndPlaced _ 1; }; i1 _ i2; IF i1 = i THEN EXIT; ip1 _ ip2; ENDLOOP; IF errFlag THEN { MDOps.Report[passFatal, "The following must all be on the same page,\n but have conflicting page assignments as follows:\n"]; MDUtils.PutRing[i]; }; UNTIL ip1.links.jbcLinked = 0 DO -- make sure not in subpage i1 _ ip1.word2.W2AddrAndbLink; ip1 _ MDUtils.IMPtr[i1]; ENDLOOP; page _ addr1/DoradoPageSize; IF pageVec[page] = 177777B THEN pageVec[page] _ i1 ELSE { -- merge the rings, no need to check if same ip2: IMRecordPtr = MDUtils.IMPtr[pageVec[page]]; link1: CARDINAL = ip1.word2.W2AddrAndbLink; ip1.word2.W2AddrAndbLink _ ip2.word2.W2AddrAndbLink; ip2.word2.W2AddrAndbLink _ link1; }; ENDLOOP; RETURN[~errFlag]; }; CardAnd: PUBLIC PROC[addr: CARDINAL, mask: WORD] RETURNS[CARDINAL] = { RETURN[LOOPHOLE[Basics.BITAND[LOOPHOLE[addr], mask]] ] }; Rcy1: PROC[mask, imMask: WORD] RETURNS[WORD] = { OPEN Basics; m1: WORD = BITSHIFT[mask, -1]; -- rshift 1 m2: WORD = BITSHIFT[mask, 15]; -- lshift 15 RETURN[BITAND[BITOR[m1, m2], imMask]]; }; Lcy1: PROC[mask: WORD] RETURNS[WORD] = { OPEN Basics; m1: WORD = BITSHIFT[mask, 1]; -- lshift 1 m2: WORD = BITSHIFT[mask, -15]; -- rshift 15 RETURN[BITOR[m1, m2]]; }; END. ΘMDAListImpl.mesa Copyright c 1986 by Xerox Corporation. All rights reserved. Willie-Sue, May 6, 1986 2:36:29 pm PDT taken from MDalist.bcpl To process alists, sequence through IM as follows: 1. If aLinked then loop (not an alist head). 2. Iterate over the list as follows: For each alist element I: 3. "AND" its mask with the mask accumulated so far. Error if the mask becomes zero in the process. Mask is propagated from one alist element to the next by Mask = Mask rcy 1. 4. Check for absolute or global placement. Propagate absolute addresses to following list elements by AbsAddr = ((AbsAddr & 7700B)+((AbsAddr+1) & 77B)). 5. End of list handled as follows: a. If absolute, AbsAddr is propagated to all alist elements. b. If GlobFlag, page-relative positions are propagated to all list elements (same algorithm as propagating AbsAddr). Loop over all instructions in alist Done with this instruction, check for more in list Advance to next instruction End of alist. Fill in mask, also fill in addresses for global and page lists Propagate page assignments through branch rings; Merge disjoint rings for same page Mask = ((Mask rshift 1)+(Mask lshift 15)) & IMptr>>IM.mask Mask = (Mask lshift 1)+(Mask rshift 15) Κ˜šœ™Icodešœ Οmœ1™š žœžœž œžœž˜.Jšœžœ˜J˜&J˜šžœ žœ˜šœ<˜