MDAListImpl.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Willie-Sue, May 6, 1986 2:36:29 pm PDT
taken from MDalist.bcpl
DIRECTORY
Basics,
IO,
Rope,
MDDefs,
MDGlobalVars,
MDOps,
MDUtils;
MDAListImpl: CEDAR PROGRAM
IMPORTS
Basics, IO,
MDGlobalVars, MDOps, MDUtils
EXPORTS
MDOps, MDUtils
= BEGIN OPEN MDDefs, MDGlobalVars;
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).
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
Loop over all instructions in alist
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;
Done with this instruction, check for more in list
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
Advance to next instruction
imPtr ← MDUtils.IMPtr[ni];
ENDLOOP;
End of alist.
Fill in mask, also fill in addresses for global and page lists
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 {
Propagate page assignments through branch rings; Merge disjoint rings for same page
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;
Mask = ((Mask rshift 1)+(Mask lshift 15)) & IMptr>>IM.mask
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;
Mask = (Mask lshift 1)+(Mask rshift 15)
m1: WORD = BITSHIFT[mask, 1]; -- lshift 1
m2: WORD = BITSHIFT[mask, -15]; -- rshift 15
RETURN[BITOR[m1, m2]];
};
END.