<> <> <> <> DIRECTORY Basics, IO, Rope, VM USING [AddressForPageNumber, PagesForWords, SimpleAllocate], MDADefs, MDDefs, MDGlobalVars, MDOps, MDUtils; MDAssignRingImpl: CEDAR PROGRAM IMPORTS Basics, IO, VM, MDGlobalVars, MDOps, MDUtils EXPORTS MDOps, MDUtils = BEGIN OPEN MDADefs, MDDefs, MDGlobalVars; firstDoradoPage: DoradoPage; -- keep track of the first one?? pageTab: ARRAY [0..nPages) OF DoradoPage; -- pointers to pages aTab: ARRAY [0..DoradoPageSize) OF CARDINAL; firstPage, lastPage, thisPage: CARDINAL; fullMsg, failMsg: ROPE; totalMsg: ROPE = "%6Bb instructions in %g"; wBuf: WorkingBuffer; wRing: DoradoPage _ NEW[DoradoPageRec _ [0, 0, 0, FALSE, 0, NEW[PbtRec]] ]; NotUnique: SIGNAL = CODE; DoAssignments: PUBLIC PROC RETURNS[ok: BOOL] = TRUSTED { groups: ARRAY [0..11) OF CARDINAL _ ALL[7777B]; <> MDOps.Report[infoOnly, "Assigning locations...\n"]; IF firstDoradoPage = NIL THEN { buf: LONG POINTER _ VM.AddressForPageNumber[VM.SimpleAllocate[VM.PagesForWords[lWBuf]].page]; wBuf _ LOOPHOLE[buf]; FOR i: CARDINAL IN [0..nPages) DO -- this won't change pageTab[i] _ NEW[DoradoPageRec]; pageTab[i].absPage _ i * DoradoPageSize; pageTab[i].bt _ NEW[PbtRec _ ALL[FALSE]]; ENDLOOP; firstDoradoPage _ pageTab[0]; buf _ VM.AddressForPageNumber[VM.SimpleAllocate[VM.PagesForWords[IMsize]].page]; realToImagAddrs _ LOOPHOLE[buf]; buf _ VM.AddressForPageNumber[VM.SimpleAllocate[VM.PagesForWords[IMsize]].page]; imagToRealAddrs _ LOOPHOLE[buf]; }; FOR i: CARDINAL IN [0..MDDefs.IMsize) DO (realToImagAddrs+i)^ _ 177777B; (imagToRealAddrs+i)^ _ 177777B; ENDLOOP; BEGIN -- mark used pages from IMLocked in pageBase data structure thisAddr: CARDINAL _ 0; used: CARDINAL _ 0; FOR i: CARDINAL IN [0..nPages) DO dp: DoradoPage = pageTab[i]; FOR j: CARDINAL IN [0..DoradoPageSize) DO IF (dp.bt[j] _ imLocked[thisAddr]) THEN used _ used + 1; thisAddr _ thisAddr + 1; ENDLOOP; dp.used _ used; dp.global _ dp.ifuEntry _ 0; dp.slow_ FALSE; ENDLOOP; END; FOR i: CARDINAL DECREASING IN [0.. nInstructions) DO -- so lists are in ascending order imPtr: IMRecordPtr = MDUtils.IMPtr[i]; groupIndex: CARDINAL; imPtr.word2.branchesAndMarked _ 0; SELECT TRUE FROM imPtr.word0.onPageAndPlaced = 1 => groupIndex _ 8; imPtr.word0.globalAndIFUSeq = 1 => groupIndex _ 9; imPtr.word0.brkPAndIFUE = 1 => groupIndex _ 10; ENDCASE => { IF imPtr.links.aLinked # 0 THEN groupIndex _ 4 ELSE groupIndex _ 0; -- alists first IF Basics.BITAND[Basics.BITNOT[calledMask], imPtr.mask] = 0 THEN groupIndex _ groupIndex + 2; -- Then subroutine entries IF imPtr.word2.W2AddrAndbLink # i THEN groupIndex _ groupIndex + 1; -- Then non-unit rings }; imPtr.word1.W1AddrAndGroupLink _ groups[groupIndex]; groups[groupIndex] _ i; ENDLOOP; <> BEGIN gAbs: CARDINAL _ groups[8]; imPtr: IMRecordPtr; pAddr: CARDINAL; failMsg _ "Can't assign absolutely placed ring"; fullMsg _ "Too many instructions on page"; totalCount _ 0; DO i, pageNum: CARDINAL; IF gAbs = 7777B THEN EXIT; imPtr _ MDUtils.IMPtr[i _ gAbs]; gAbs _ imPtr.word1.W1AddrAndGroupLink; -- next in list IF imPtr.word2.branchesAndMarked = 1 THEN LOOP; -- already processed pageNum _ imPtr.word0.W0Addr/DoradoPageSize; pAddr _ pageNum * DoradoPageSize; totalCount _ CollectRing[i, wBuf, wRing] + totalCount; IF (wRing.global # 0) AND (MDUtils.CardAnd[pAddr, globalZero] # 0) THEN MDOps.Report[passFatal, "Can't have GLOBAL on page %b\n", IO.card[pAddr]]; IF (wRing.ifuEntry # 0) AND (MDUtils.CardAnd[pAddr, ifuZero] # 0) THEN MDOps.Report[passFatal, "Can't have IFU on page %b\n", IO.card[pAddr]]; PageLimits[pageNum, pageNum]; AssignPage[wBuf, wRing]; ENDLOOP; END; IF totalCount # 0 THEN MDOps.Report[infoOnly, totalMsg, IO.card[totalCount], IO.rope["rings involving ONPAGE or AT\n"] ]; <> BEGIN gGlobal: CARDINAL _ groups[9]; gIFUE: CARDINAL _ groups[10]; imPtr: IMRecordPtr; failMsg _ "Can't assign GLOBAL ring"; fullMsg _ NIL; PageLimits[0, nGlobalPages-1]; totalCount _ 0; DO i: CARDINAL; IF gGlobal = 7777B THEN EXIT; imPtr _ MDUtils.IMPtr[i _ gGlobal]; gGlobal _ imPtr.word1.W1AddrAndGroupLink; -- next in list IF imPtr.word2.branchesAndMarked = 1 THEN LOOP; -- already processed totalCount _ CollectRing[i, wBuf, wRing] + totalCount; AssignPage[wBuf, wRing]; ENDLOOP; IF totalCount # 0 THEN MDOps.Report[infoOnly, totalMsg, IO.card[totalCount], IO.rope["rings with a GLOBAL\n"] ]; PageLimits[0, nIfuPages-1]; failMsg _ "Can't assign IFU entry ring"; totalCount _ 0; DO i: CARDINAL; IF gIFUE = 7777B THEN EXIT; imPtr _ MDUtils.IMPtr[i _ gIFUE]; gIFUE _ imPtr.word1.W1AddrAndGroupLink; -- next in list IF imPtr.word2.branchesAndMarked = 1 THEN LOOP; -- already processed totalCount _ CollectRing[i, wBuf, wRing] + totalCount; AssignPage[wBuf, wRing]; ENDLOOP; IF totalCount # 0 THEN MDOps.Report[infoOnly, totalMsg, IO.card[totalCount], IO.rope["rings with an IFU entry\n"] ]; END; <> PageLimits[0, nPages - 1]; failMsg _ "Ran out of pages trying to assign ring"; FOR a: CARDINAL DECREASING IN [0..8) DO i: CARDINAL _ groups[a]; thisMsg: ROPE; totalCount _ 0; DO imPtr: IMRecordPtr; IF i = 7777B THEN EXIT; imPtr _ MDUtils.IMPtr[i]; IF imPtr.word2.branchesAndMarked = 0 THEN { -- not yet seen totalCount _ CollectRing[i, wBuf, wRing] + totalCount; AssignPage[wBuf, wRing]; }; i _ imPtr.word1.W1AddrAndGroupLink; ENDLOOP; thisMsg _ SELECT a FROM 7 => "CALLed rings including a CALL/conditional\n", 6 => NIL, -- Can't have a 1-instruction alist 5 => "other rings including a CALL/conditional\n", 4 => NIL, -- Can't have a 1-instruction alist 3 => "CALLed multi-instruction rings\n", 2 => "CALLed 1-instruction rings\n", 1 => "other multi-instruction rings\n", 0 => "other 1-instruction rings\n", ENDCASE => NIL; IF totalCount # 0 THEN MDOps.Report[infoOnly, totalMsg, IO.card[totalCount], IO.rope[thisMsg] ]; ENDLOOP; <> BEGIN first: BOOL _ TRUE; FOR i: CARDINAL IN [0..nInstructions) DO imPtr: IMRecordPtr = MDUtils.IMPtr[i]; placed: BOOL = (imPtr.word0.onPageAndPlaced = 1) AND (imPtr.word0.atW0AndatWord = 1); imPtr.word0.onPageAndPlaced _ IF placed THEN 1 ELSE 0; IF ~placed THEN { IF first THEN { MDOps.Report[passFatal, "\n\n******The following had no address assigned:\n\t%g", IO.card[i] ]; first _ FALSE; } ELSE MDOps.Report[infoOnly, "%6bB", IO.card[i]]; }; <> <> <> <<(realToImagAddr+w0)^ _ i;>> <<};>> ENDLOOP; IF ~first THEN MDOps.Report[infoOnly, "\n"]; END; RETURN[TRUE]; }; PageLimits: PROC[first, last: CARDINAL] = { firstPage _ first; lastPage _ last; thisPage _ first; }; aTrue: CARDINAL _ 0; -- statistics aFalse: CARDINAL _ 0; RingStatus: TYPE = {ok, isolatedIns, ptrToSubPage, failure }; AssignPage: PROC[wBuf: WorkingBuffer, wRing: DoradoPage] = TRUSTED { max: CARDINAL _ DoradoPageSize - wRing.used; pn: CARDINAL _ thisPage; af: CARDINAL _ aFalse; fPtr, fp: LONG POINTER TO CARDINAL; ringStatus: RingStatus; fUsed: CARDINAL _ DoradoPageSize; DO page: DoradoPage _ pageTab[pn]; IF page.used <= max THEN { [fp, ringStatus] _ AssignRing[wBuf, wRing, page]; IF ringStatus = ok THEN { thisPage _ pn; aTrue _ aTrue + 1; RETURN } ELSE { IF page.used < fUsed THEN fUsed _ page.used; fPtr _ fp; aFalse _ aFalse + 1; }; }; IF pn <= firstPage THEN EXIT; pn _ pn - 1; ENDLOOP; pn _ thisPage + 1; UNTIL pn > lastPage DO page: DoradoPage = pageTab[pn]; IF page.used <= max THEN { [fp, ringStatus] _ AssignRing[wBuf, wRing, page]; IF ringStatus = ok THEN { thisPage _ pn; aTrue _ aTrue + 1; RETURN } ELSE { IF page.used < fUsed THEN fUsed _ page.used; fPtr _ fp; aFalse _ aFalse + 1; } }; pn _ pn + 1; ENDLOOP; <> BEGIN msg: ROPE _ IF fullMsg # NIL THEN fullMsg ELSE failMsg; MDOps.Report[infoOnly, IF ringStatus = isolatedIns THEN "%g:" ELSE "%g,\n while trying to place instruction(s):", IO.rope[msg] ]; IF ringStatus = isolatedIns THEN MDUtils.PutAData[fPtr^] ELSE { fx: SubPage = LOOPHOLE[fPtr]; FOR j: CARDINAL IN [0..fx.subPageHeader.length) DO MDUtils.PutAData[fx.data[j]]; ENDLOOP; }; MDOps.Report[passFatal, " Ring consists of:\n"]; MDUtils.PutRing[FirstIns[wBuf]]; END; }; FirstIns: PROC[wBuf: WorkingBuffer] RETURNS[CARDINAL] = TRUSTED { sph: SubPage = LOOPHOLE[IF wBuf^ = 0 THEN wBuf+SIZE[SubPageHeader] ELSE wBuf]; RETURN[sph.data[0]]; }; CollectRing: PROC[i: CARDINAL, wBuf: WorkingBuffer, wRing: DoradoPage] RETURNS[CARDINAL] = TRUSTED { <> <> <> <> count: CARDINAL _ 0; aTab _ ALL[0]; aTab[0] _ 177776B; <> wRing.used _ wRing.global _ wRing.ifuEntry _ 0; wRing.slow _ FALSE; BEGIN xbt: Xbt _ LOOPHOLE[wRing.bt]; FOR i: CARDINAL IN [0..xbtWords) DO xbt[i] _ 0; ENDLOOP; END; <> DO imPtr: IMRecordPtr _ MDUtils.IMPtr[i]; i _ imPtr.word2.W2AddrAndbLink; IF imPtr.links.jbcLinked = 0 THEN EXIT; ENDLOOP; BEGIN j: CARDINAL _ i; ni: CARDINAL _ 0; top: CARDINAL = lWBuf-1; bot: CARDINAL = SIZE[SubPageHeader]; ptr: CARDINAL _ bot; end: CARDINAL _ top; nsp: CARDINAL _ 0; lastLinked: BOOL _ FALSE; DO imPtr: IMRecordPtr _ MDUtils.IMPtr[j]; imPtr.word2.branchesAndMarked _ 1; IF imPtr.word0.globalAndIFUSeq = 1 THEN { wRing.global _ wRing.global + 1; wRing.slow _ TRUE; IF wRing.global > pageGlobalMax THEN { MDOps.Report[passFatal, "***More than 1 GLOBAL on a page:\n"]; MDUtils.PutRing[j]; }; }; IF imPtr.word0.brkPAndIFUE = 1 THEN { wRing.ifuEntry _ wRing.ifuEntry + 1; wRing.slow _ TRUE; IF wRing.ifuEntry > pageIfuMax THEN { MDOps.Report[passFatal, "***More than 16 IFU entries on a page:\n"]; MDUtils.PutRing[j]; }; }; IF imPtr.word0.atW0AndatWord = 1 THEN { wn: CARDINAL _ MDUtils.CardAnd[imPtr.word0.W0Addr, WordMask]; IF aTab[0] = 177776B THEN aTab _ ALL[177777B]; IF aTab[wn] = 177777B THEN { wRing.bt[wn] _ TRUE; aTab[wn] _ j; wRing.slow _ TRUE; } ELSE MDOps.Report[passFatal, "%g....assigned to same location as %g\n", IO.card[j], IO.card[aTab[wn]] ]; }; IF ~lastLinked THEN { IF imPtr.links.jbcLinked = 0 THEN { IF end # ptr THEN { (wBuf+ptr)^ _ j; ptr _ ptr + 1 } } ELSE { len: CARDINAL = CollectSubpage[wBuf, j, end, end-ptr]; end _ end - len; IF len # 0 THEN nsp _ nsp + len - SIZE[SubPageHeader]; }; }; j _ imPtr.word2.W2AddrAndbLink; lastLinked _ imPtr.links.jbcLinked = 1; ni _ ni + 1; IF j = i THEN EXIT; ENDLOOP; IF ni > DoradoPageSize THEN { MDOps.Report[passFatal, "%g instructions had to go on the same page (limit is 64):\n", IO.card[ni]]; MDUtils.PutRing[i]; ni _ ptr - bot + nsp; }; wRing.used _ ni; <> wBuf^ _ ptr - bot; (wBuf+top)^ _ 0; FOR m: CARDINAL IN [0..top-end+1) DO (wBuf+ptr+m)^ _ (wBuf+end+m)^; ENDLOOP; RETURN[ni]; END; }; CollectSubpage: PROC[wBuf: WorkingBuffer, start, end, len: CARDINAL] RETURNS[CARDINAL] = TRUSTED { <> <> <> <> <> IF len <= SIZE[SubPageHeader] THEN RETURN[0]; BEGIN i: CARDINAL _ start; data: ARRAY [0..SubPageSize) OF CARDINAL; jBot: CARDINAL _ end - len; jTop: CARDINAL _ end; dBot: CARDINAL _ 0; dTop: CARDINAL _ SubPageSize; spn: CARDINAL _ 177777B; iAbs: CARDINAL; DO imPtr: IMRecordPtr _ MDUtils.IMPtr[i]; IF imPtr.word0.atW0AndatWord = 1 THEN { -- absolute placement spa: CARDINAL _ PageShift[imPtr.word0.W0Addr]; IF spn = 177777B THEN { spn _ spa; iAbs _ i } ELSE { IF spn # spa THEN MDOps.Report[passFatal, "%g....must be in subpage with %g, but has conflicting assignment", IO.card[i], IO.card[iAbs] ]; }; }; IF imPtr.links.aLink = i THEN { -- not on a +1 list, put at end IF jTop = jBot THEN RETURN[0]; jTop _ jTop - 1; (wBuf+jTop)^ _ i; } ELSE { -- on a +1 list, put the list at the beginning i0, i1: CARDINAL; gotIt: BOOL _ FALSE; FOR j: CARDINAL IN [0..dBot) DO IF data[j] = i THEN GOTO ska; -- already got it ENDLOOP; IF gotIt THEN LOOP; i1 _ i; WHILE imPtr.links.aLinked = 1 DO -- find beginning of alist i1 _ imPtr.links.aLink; imPtr _ MDUtils.IMPtr[i1]; ENDLOOP; i0 _ i1; DO IF dBot = dTop THEN RETURN[0]; data[dBot] _ i1; dBot _ dBot + 1; i1 _ imPtr.links.aLink; imPtr _ MDUtils.IMPtr[i1]; IF i1 = i0 THEN EXIT; ENDLOOP; imPtr _ MDUtils.IMPtr[i]; EXITS ska => NULL; }; i _ imPtr.word2.W2AddrAndbLink; IF imPtr.links.jbcLinked = 0 THEN EXIT; ENDLOOP; <> BEGIN v: CARDINAL _ jTop - dBot - SIZE[SubPageHeader]; nw: CARDINAL; sph: SubPageHeader; IF v < jBot THEN RETURN[0]; FOR m: CARDINAL IN [0..dBot) DO (wBuf+v+SIZE[SubPageHeader]+m)^ _ data[m]; ENDLOOP; nw _ end - v - SIZE[SubPageHeader]; IF nw > 16 THEN MDOps.Report[passFatal, "%g....more than 16 instructions in subpage\n", IO.card[start]]; sph.aLists _ IF dBot # 0 THEN 1 ELSE 0; sph.spn1 _ spn+1; sph.length _ nw; (wBuf+v)^ _ LOOPHOLE[sph]; RETURN[end - v]; END; END; }; PageShift: PROC[addr: CARDINAL] RETURNS[CARDINAL] = { x: WORD = Basics.BITAND[LOOPHOLE[addr], DoradoPageSize-20B]; RETURN[LOOPHOLE[Basics.BITSHIFT[x, -4], CARDINAL]]; }; AssignRing: PROC[wBuf: WorkingBuffer, wRing, page: DoradoPage] RETURNS[fPtr: LONG POINTER TO CARDINAL, status: RingStatus] = TRUSTED { <> <> <> xRing: XDoradoPage = LOOPHOLE[wRing]; xPage: XDoradoPage = LOOPHOLE[page]; fSub: LONG POINTER TO CARDINAL = LOOPHOLE[wBuf + SIZE[SubPageHeader] + wBuf^]; subTab: SubPage = LOOPHOLE[wBuf]; assignList: LIST OF Assignment _ NIL; xbt: XDoradoPage = NEW[XDoradoPageRec]; dbt: DoradoPage = LOOPHOLE[xbt]; xbt.bt _ NEW[XbtRec _ ALL[0]]; IF wRing.slow THEN { IF wRing.global + page.global > pageGlobalMax THEN RETURN[NIL, failure]; IF wRing.ifuEntry + page.ifuEntry > pageIfuMax THEN RETURN[NIL, failure]; <> FOR i: CARDINAL IN [0..xbtWords) DO rBits: WORD = xRing.bt[i]; pBits: WORD = xPage.bt[i]; IF Basics.BITAND[rBits, pBits] # 0 THEN RETURN[NIL, failure]; xbt.bt[i] _ Basics.BITOR[rBits, pBits]; ENDLOOP; } ELSE FOR i: CARDINAL IN [0..xbtWords) DO xbt.bt[i] _ xPage.bt[i]; ENDLOOP; <> BEGIN xSub: LONG POINTER TO CARDINAL _ fSub; UNTIL xSub^ = 0 DO sub: SubPage = LOOPHOLE[xSub]; IF sub.subPageHeader.aLists # 0 THEN IF ~MDUtils.PlaceSubpage[sub, page.absPage, xbt] THEN RETURN[xSub, ptrToSubPage]; xSub _ LOOPHOLE[xSub + SIZE[SubPageHeader] + sub.subPageHeader.length]; ENDLOOP; <<>> <> xSub _ fSub; UNTIL xSub^ = 0 DO sub: SubPage = LOOPHOLE[xSub]; IF sub.subPageHeader.aLists = 0 THEN IF ~MDUtils.PlaceSubpage[sub, page.absPage, xbt] THEN RETURN[xSub, ptrToSubPage]; xSub _ LOOPHOLE[xSub + SIZE[SubPageHeader] + sub.subPageHeader.length]; ENDLOOP; <<>> <> FOR j: CARDINAL IN [0..subTab.subPageHeader.length) DO jx: CARDINAL; w0: CARDINAL; imPtr: IMRecordPtr = MDUtils.IMPtr[jx _ subTab.data[j]]; IF imPtr.word0.atW0AndatWord = 1 THEN -- absolutely placed w0 _ page.absPage + MDUtils.CardAnd[imPtr.word0.W0Addr, WordMask] ELSE { loc: CARDINAL = MDUtils.Find1Place[imPtr.mask, xbt.bt]; IF loc = 177777B THEN RETURN[wBuf+SIZE[SubPageHeader]+j, isolatedIns]; w0 _ page.absPage + loc; }; IF (imagToRealAddrs+jx)^ # 177777B THEN SIGNAL NotUnique; IF (realToImagAddrs+w0)^ # 177777B THEN SIGNAL NotUnique; imPtr.word0.W0Addr _ w0; ENDLOOP; END; page.global _ page.global + wRing.global; page.ifuEntry _ page.ifuEntry + wRing.ifuEntry; page.used _ page.used + wRing.used; FOR i: CARDINAL IN [0.. xbtWords) DO xPage.bt[i] _ xbt.bt[i]; ENDLOOP; BEGIN xSub: LONG POINTER TO CARDINAL _ wBuf; DO sub: SubPage = LOOPHOLE[xSub]; end: LONG POINTER TO CARDINAL = LOOPHOLE[xSub+SIZE[SubPageHeader]+sub.subPageHeader.length]; xSub _ LOOPHOLE[xSub+SIZE[SubPageHeader]]; UNTIL xSub = end DO jx: CARDINAL = xSub^; imPtr: IMRecordPtr = MDUtils.IMPtr[jx]; imPtr.word0.onPageAndPlaced _ 1; imPtr.word0.atW0AndatWord _ 1; (imagToRealAddrs+jx)^ _ imPtr.word0.W0Addr; (realToImagAddrs+imPtr.word0.W0Addr)^ _ jx; xSub _ LOOPHOLE[xSub + 1]; ENDLOOP; IF xSub^ = 0 THEN EXIT; ENDLOOP; END; RETURN[NIL, ok]; }; GetPageN: PUBLIC PROC[pageNum: CARDINAL] RETURNS[DoradoPage] = { RETURN[pageTab[pageNum]] }; END.