DIRECTORY Alloc USING [Notifier], Code USING [CodePassInconsistency, codeptr, reentryLabel, tailJumpOK], CodeDefs USING [Base, Byte, CCIndex, CCInfoType, CCNull, codeType, JumpCCIndex, JumpCCNull, JumpType, LabelCCIndex, LabelCCNull, RelativePC], ComData USING [switches], FOpCodes USING [qLFC, qPOP, qRET], OpCodeParams USING [zJEQn, zJn, zJNEn], OpTableDefs USING [--InstAligned,-- InstLength], P5 USING [C0, C1, C1W, PeepHole], P5F USING [BindJump, CodeJump, CPass5, FillInPCEstimates], P5U USING [DeleteCell, OutJump], PeepholeDefs USING [NextInteresting, PrevInteresting, RemoveThisPop, SetRealInst], PrincOps USING [zJB, zJEQ4, zJEQB, zJGB, zJGEB, zJLB, zJLEB, zJNE4, zJNEB, zJUGB, zJUGEB, zJULB, zJULEB, zJW, zJZEQB, zJZNEB]; Final: PROGRAM IMPORTS CPtr: Code, MPtr: ComData, OpTableDefs, P5U, P5, P5F, PeepholeDefs EXPORTS CodeDefs, P5, P5F = BEGIN OPEN PeepholeDefs, CodeDefs; cb: CodeDefs.Base; -- code base (local copy) CJump: ARRAY JumpType[JumpE..ZJumpN] OF JumpType = [ JumpN, JumpE, JumpGE, JumpL, JumpLE, JumpG, UJumpGE, UJumpL, UJumpLE, UJumpG, ZJumpN, ZJumpE]; FinalNotify: PUBLIC Alloc.Notifier = BEGIN -- called by allocator whenever table area is repacked cb _ base[codeType]; END; DidSomething: PUBLIC BOOL; StartIndex: PUBLIC LabelCCIndex; EndIndex: PUBLIC CCIndex; SeenSwitch: BOOL; JumpCellCount: CARDINAL; ccInfo: PUBLIC CCInfoType _ generating; CCInfoMeaning: PUBLIC PROC RETURNS [CCInfoType] = BEGIN RETURN [ccInfo] END; Fixup: PUBLIC PROC [start: LabelCCIndex, ownEntry: CARDINAL] = BEGIN -- a final pass over the code to fix up jumps jumpsBefore, jumpsAfter, totalJumps: CARDINAL; crossJump: BOOL = MPtr.switches['j]; ccInfo _ generating; DidSomething _ TRUE; SeenSwitch _ TRUE; StartIndex _ start; PeepholeDefs.SetRealInst[FALSE]; IF crossJump AND CPtr.tailJumpOK THEN TailJump[ownEntry]; CPtr.reentryLabel _ LabelCCNull; -- avoid dangling ref if deleted DO CPass0[]; IF ~DidSomething THEN EXIT; DidSomething _ FALSE; SeenSwitch _ ~SeenSwitch; CPass1[]; CPass2[]; CPass3[]; CPass4[]; IF crossJump THEN P5F.CPass5[]; ENDLOOP; -- end of the meta-pass consisting of passes 0-5 P5.PeepHole[StartIndex]; ccInfo _ binding; totalJumps _ jumpsAfter _ CPass7[]; jumpsBefore _ jumpsAfter+1; THROUGH [1..3] WHILE jumpsAfter # 0 AND jumpsAfter < jumpsBefore DO jumpsBefore _ jumpsAfter; jumpsAfter _ CPass8[]; ENDLOOP; IF jumpsAfter # 0 THEN CPass9[]; ccInfo _ coding; IF totalJumps # 0 THEN CPass11[]; END; TailJump: PROC [ownEntry: CARDINAL] = BEGIN -- remove simple tail recursion next: CCIndex; FOR c: CCIndex _ cb[StartIndex].flink, next WHILE c # CCNull DO next _ cb[c].flink; WITH cb[c] SELECT FROM code => IF ~realinst AND inst = FOpCodes.qLFC AND parameters[1] = ownEntry AND UCreturn[next] THEN BEGIN CPtr.codeptr _ cb[c].blink; P5U.OutJump[Jump, CPtr.reentryLabel]; P5U.DeleteCell[c] END ENDCASE; ENDLOOP; END; UCreturn: PROC [start: CCIndex] RETURNS [BOOL] = BEGIN -- find (unconditional) path to RET next: CCIndex; FOR c: CCIndex _ start, next WHILE c # CCNull DO WITH cc: cb[c] SELECT FROM code => RETURN [~cc.realinst AND cc.inst = FOpCodes.qRET]; label => next _ cc.flink; jump => BEGIN IF ~UCjump[c] THEN EXIT; next _ cc.destlabel; END; other => WITH cc SELECT FROM table => EXIT; ENDCASE => next _ cc.flink; ENDCASE => EXIT; ENDLOOP; RETURN [FALSE] END; CPass0: PROC = BEGIN -- pass 0: distinguish forward and backward jumps JumpCellCount _ 0; FOR c: CCIndex _ StartIndex, cb[c].flink WHILE c # CCNull DO EndIndex _ c; WITH cb[c] SELECT FROM label => labelseen _ SeenSwitch; jump => BEGIN forward _ IF destlabel = LabelCCNull THEN TRUE ELSE ~(cb[destlabel].labelseen = SeenSwitch); JumpCellCount _ JumpCellCount + 1; END; ENDCASE; ENDLOOP; END; CPass1: PROC = BEGIN -- pass 1: eliminate multiple labels, unreferenced labels, nextC, c: CCIndex; FOR c _ cb[StartIndex].flink, nextC WHILE c # CCNull DO nextC _ NextInteresting[c]; WITH cc:cb[c] SELECT FROM jump => IF DotPlusOneJump[LOOPHOLE[c], nextC] AND (UCjump[c] OR cc.jtype IN [JumpE..UJumpLE]) THEN DeleteJump[LOOPHOLE[c]]; label => IF cc.jumplist = JumpCCNull THEN {DidSomething _ TRUE; P5U.DeleteCell[LOOPHOLE[c, LabelCCIndex]]} ELSE IF nextC # CCNull THEN WITH cb[nextC] SELECT FROM label => BEGIN DidSomething _ TRUE; DeleteLabel[LOOPHOLE[c, LabelCCIndex], LOOPHOLE[nextC, LabelCCIndex]]; END; ENDCASE; ENDCASE; ENDLOOP; END; DotPlusOneJump: PROC [jc: JumpCCIndex, next: CCIndex] RETURNS [BOOL] = INLINE BEGIN RETURN [IF next = CCNull THEN FALSE -- RRA fix ELSE WITH cb[next] SELECT FROM label => next = cb[jc].destlabel, ENDCASE => FALSE] END; DeleteJump: PROC [jc: JumpCCIndex] = BEGIN IF cb[jc].jtype IN [JumpE..UJumpLE] THEN THROUGH [0..2) DO CPtr.codeptr _ cb[jc].blink; P5.C0[FOpCodes.qPOP]; [] _ PeepholeDefs.RemoveThisPop[CPtr.codeptr]; ENDLOOP; UnthreadJump[jc]; DidSomething _ TRUE; P5U.DeleteCell[jc]; END; CPass2: PROC = BEGIN -- pass 2: eliminate jump to jumps FOR c: CCIndex _ cb[StartIndex].flink, cb[c].flink WHILE c # CCNull DO WITH jj: cb[c] SELECT FROM jump => IF jj.destlabel # LabelCCNull THEN BEGIN jtojExists: BOOL _ FALSE; jcCount: CARDINAL _ 0; jc: JumpCCIndex _ LOOPHOLE[c, JumpCCIndex]; jcLabel: LabelCCIndex; cc: CCIndex; DO jcLabel _ cb[jc].destlabel; IF (cc _ NextInteresting[jcLabel]) = CCNull THEN EXIT; IF ~UCjump[cc] THEN EXIT; jc _ LOOPHOLE[cc, JumpCCIndex]; IF jc = c THEN {jtojExists _ FALSE; EXIT}; jcCount _ jcCount +1; IF jcCount > JumpCellCount THEN {jtojExists _ FALSE; EXIT}; jtojExists _ TRUE; ENDLOOP; IF jtojExists THEN BEGIN DidSomething _ TRUE; UnthreadJump[LOOPHOLE[c, JumpCCIndex]]; jj.thread _ cb[jcLabel].jumplist; cb[jcLabel].jumplist _ LOOPHOLE[c, JumpCCIndex]; jj.destlabel _ jcLabel; END; END; ENDCASE ENDLOOP; END; CPass3: PROC = BEGIN -- pass 3: eliminate unreachable code FOR c: CCIndex _ cb[StartIndex].flink, cb[c].flink WHILE c # CCNull DO WITH cb[c] SELECT FROM jump => IF UCjump[c] OR jtype = JumpRet OR jtype = JumpCA THEN BEGIN cc: CCIndex _ flink; oldc: CCIndex; DO { IF (oldc _ cc) = CCNull THEN RETURN; cc _ cb[cc].flink; WITH cb[oldc] SELECT FROM label => IF jumplist # JumpCCNull THEN EXIT; jump => UnthreadJump[LOOPHOLE[oldc, JumpCCIndex]]; other => IF otag # table THEN GOTO skip; --body start/stop, source ENDCASE; P5U.DeleteCell[oldc]; DidSomething _ TRUE; EXITS skip => NULL } ENDLOOP; END; ENDCASE; ENDLOOP; END; CPass4: PROC = BEGIN -- pass 4: replace cj-j seq. with ccj c, nextC: CCIndex; FOR c _ cb[StartIndex].flink, nextC WHILE c # CCNull DO WITH oldC: cb[c] SELECT FROM jump => BEGIN nextC _ IF MPtr.switches['j] THEN NextInteresting[c] ELSE cb[c].flink; -- don't ignore source chunks here IF oldC.jtype IN [JumpE..ZJumpN] AND nextC # CCNull THEN WITH nc: cb[nextC] SELECT FROM jump => IF oldC.destlabel = nc.destlabel AND (UCjump[c] OR oldC.jtype IN [JumpE..UJumpLE]) THEN DeleteJump[LOOPHOLE[c]] ELSE IF UCjump[nextC] AND (PrevInteresting[oldC.destlabel] = nextC) THEN BEGIN newLbl: LabelCCIndex = nc.destlabel; nxt: CCIndex; UnthreadJump[LOOPHOLE[nextC, JumpCCIndex]]; UnthreadJump[LOOPHOLE[c, JumpCCIndex]]; oldC.destlabel _ newLbl; oldC.thread _ cb[newLbl].jumplist; cb[newLbl].jumplist _ LOOPHOLE[c, JumpCCIndex]; oldC.jtype _ CJump[oldC.jtype]; oldC.forward _ nc.forward; nxt _ nc.flink; P5U.DeleteCell[nextC]; nextC _ nxt; END; ENDCASE; END; ENDCASE => nextC _ cb[c].flink; ENDLOOP; END; CPass7: PROC RETURNS [unboundJumps: CARDINAL _ 0] = BEGIN -- pass 7: set length and alignment, count jumps c, next: CCIndex; IF ~MPtr.switches['j] THEN BEGIN c _ NextInteresting[cb[StartIndex].flink]; IF c # CCNull THEN -- RRA fix WITH cb[c] SELECT FROM label => IF jumplist # JumpCCNull THEN BEGIN CPtr.codeptr _ cb[c].blink; P5U.OutJump[Jump, LOOPHOLE[c]]; cb[LOOPHOLE[CPtr.codeptr, JumpCCIndex]].forward _ TRUE; END; ENDCASE; END; FOR c _ cb[StartIndex].flink, next WHILE c # CCNull DO next _ cb[c].flink; WITH cb[c] SELECT FROM code => BEGIN IF isize = 0 THEN isize _ OpTableDefs.InstLength[inst]; END; jump => IF jtype = JumpRet THEN P5U.DeleteCell[c] ELSE unboundJumps _ unboundJumps+1; ENDCASE; ENDLOOP; RETURN END; CPass8: PROC RETURNS [unboundJumps: CARDINAL _ 0] = BEGIN -- pass 8: resolve easy jumps P5F.FillInPCEstimates[]; FOR c: CCIndex _ cb[StartIndex].flink, cb[c].flink WHILE c # CCNull DO WITH cb[c] SELECT FROM jump => IF ~fixedup THEN BEGIN min, max: CARDINAL; target: LabelCCIndex = destlabel; IF forward THEN BEGIN min _ cb[target].minPC - minPC; max _ cb[target].maxPC - maxPC; END ELSE BEGIN min _ minPC - cb[target].minPC; max _ maxPC - cb[target].maxPC; END; IF ~P5F.BindJump[min, max, LOOPHOLE[c, JumpCCIndex]] THEN unboundJumps _ unboundJumps+1; END; ENDCASE; ENDLOOP; RETURN END; CPass9: PROC = BEGIN -- pass 9: resolve (remaining) jump instructions P5F.FillInPCEstimates[]; FOR c: CCIndex _ cb[StartIndex].flink, cb[c].flink WHILE c # CCNull DO WITH cb[c] SELECT FROM jump => IF ~fixedup THEN BEGIN nBytes: CARDINAL = IF forward THEN cb[destlabel].maxPC - maxPC ELSE maxPC - cb[destlabel].maxPC; [] _ P5F.BindJump[nBytes, nBytes, LOOPHOLE[c, JumpCCIndex]]; END; ENDCASE; ENDLOOP; END; CPass11: PROC = BEGIN -- pass 11: code jumps FillInPC[]; FOR c: CCIndex _ cb[StartIndex].flink, cb[c].flink WHILE c # CCNull DO WITH cb[c] SELECT FROM jump => BEGIN IF ~fixedup THEN SIGNAL CPtr.CodePassInconsistency ELSE P5F.CodeJump[(IF forward THEN cb[destlabel].pc - pc ELSE pc - cb[destlabel].pc), LOOPHOLE[c, JumpCCIndex]]; END; ENDCASE; ENDLOOP; END; DeleteLabel: PROC [oldc, c: LabelCCIndex] = BEGIN -- removes extra label from code stream lq, q: JumpCCIndex; IF cb[c].jumplist = JumpCCNull THEN cb[c].jumplist _ cb[oldc].jumplist ELSE BEGIN q _ cb[c].jumplist; UNTIL q = JumpCCNull DO lq _ q; q _ cb[q].thread ENDLOOP; cb[lq].thread _ cb[oldc].jumplist; END; FOR q _ cb[oldc].jumplist, cb[q].thread UNTIL q = JumpCCNull DO cb[q].destlabel _ c ENDLOOP; P5U.DeleteCell[oldc]; END; UnthreadJump: PUBLIC PROC [c: JumpCCIndex] = BEGIN -- pull jump cell out of thread from label l: LabelCCIndex = cb[c].destlabel; jc: JumpCCIndex; IF l = LabelCCNull THEN RETURN; jc _ cb[l].jumplist; IF jc = c THEN cb[l].jumplist _ cb[jc].thread ELSE BEGIN UNTIL cb[jc].thread = c DO jc _ cb[jc].thread ENDLOOP; cb[jc].thread _ cb[c].thread; END; END; UCjump: PUBLIC PROC [c: CCIndex] RETURNS [BOOL] = BEGIN -- predicate testing if c is an unconditonal jump RETURN [WITH cb[c] SELECT FROM jump => jtype = Jump, ENDCASE => FALSE] END; Removeablejump: PROC [c: CCIndex] RETURNS [BOOL] = BEGIN -- predicate testing if c is an unconditonal jump RETURN [WITH cb[c] SELECT FROM jump => (jtype = Jump OR jtype = JumpA OR jtype = JumpCA), ENDCASE => FALSE] END; FillInPC: PROC = BEGIN -- fills in relative PC of all labels and jumps. rpc: RelativePC _ 0; nbytes: CARDINAL; FOR k: CCIndex _ StartIndex, cb[k].flink UNTIL k = CCNull DO { nbytes _ (WITH cc:cb[k] SELECT FROM code => cc.isize, jump => IF cc.completed THEN 0 ELSE cc.jsize, other => (WITH cc SELECT FROM table => tablecodebytes, ENDCASE => 0), ENDCASE => 0); WITH cc:cb[k] SELECT FROM jump => IF cc.forward THEN {rpc _ rpc+nbytes; cc.pc _ rpc; GOTO skip} ELSE cc.pc _ rpc; label => cc.pc _ rpc; ENDCASE; rpc _ rpc+nbytes; EXITS skip => NULL; } ENDLOOP; END; CodeJumpDist: PUBLIC PROC [jDist: INTEGER, l: [0..7], c: JumpCCIndex] = BEGIN -- code all jump instruction(s) OPEN PrincOps, OpCodeParams; t: JumpType; RelJumpOps: ARRAY JumpType[JumpL..ZJumpN] OF Byte = [ zJLB, zJGEB, zJGB, zJLEB, zJULB, zJUGEB, zJUGB, zJULEB, zJZEQB, zJZNEB]; t _ cb[c].jtype; SELECT t FROM Jump, JumpA, JumpCA => SELECT l FROM 1 => BEGIN IF jDist NOT IN [2..9] THEN SIGNAL CPtr.CodePassInconsistency; P5.C0[zJn+jDist-2]; END; 2 => BEGIN IF jDist NOT IN [-128..128) THEN SIGNAL CPtr.CodePassInconsistency; P5.C1[zJB, jDist]; END; ENDCASE => BEGIN P5.C1W[zJW, jDist]; END; JumpE, JumpN => SELECT l FROM 1 => BEGIN IF jDist NOT IN [2..9] THEN SIGNAL CPtr.CodePassInconsistency; P5.C0[(IF t=JumpE THEN zJEQn ELSE zJNEn)+jDist-2]; END; 2 => BEGIN IF jDist NOT IN [-128..128) THEN SIGNAL CPtr.CodePassInconsistency; P5.C1[(IF t = JumpE THEN zJEQB ELSE zJNEB), jDist]; END; ENDCASE => BEGIN P5.C0[(IF t = JumpE THEN zJNE4 ELSE zJEQ4)]; P5.C1W[zJW, jDist]; END; JumpC => NULL; ENDCASE => SELECT l FROM 2 => BEGIN IF jDist NOT IN [-128..128) THEN SIGNAL CPtr.CodePassInconsistency; P5.C1[RelJumpOps[t], jDist]; END; ENDCASE => BEGIN P5.C1[RelJumpOps[CJump[t]], 5]; P5.C1W[zJW, jDist]; END; cb[c].completed _ TRUE; cb[c].jsize _ 0; -- so it doesn't have to be ignored in ComputeJumpDistance END; END. ςFinal.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Sweet, September 8, 1980 10:08 AM Satterthwaite, April 21, 1986 4:50:38 pm PST Maxwell, July 28, 1983 3:28 pm Russ Atkinson (RRA) March 6, 1985 11:18:06 pm PST pass 0: distinguish forward and backward jumps pass 1: eliminate multiple labels pass 2: eliminate jump to jumps pass 3: eliminate unreachable code pass 4: replace cj-j seq. with ccj pass 5: cross jumping pass 6: do some peephole optimization: load-store, EXCH-commutative op. jump threads are now pc's, debug output take note pass 7: set length and alignment, count jumps pass 8: resolve (most) jump instructions pass 9: resolve (remaining) jump instructions pass 11: code jumps and jumps to .+1 look for body starting with a loop aligned _ isize = 3 OR inst = PrincOps.zCATCH OR (isize # 2 AND OpTableDefs.InstAligned[inst]); all jump lengths have been resolved and pad values set PC of forward jump is end of instruction PC of backward jump is start of pad (if any) Κi˜codešœ ™ Kšœ Οmœ1™K˜KšœŸ˜-K˜šœžœžœ ˜4K˜+K˜2K˜—šœ žœ˜$KšžœŸ6˜=K˜Kšžœ˜K˜—Kšœžœžœ˜Kšœ žœ˜ Kšœ žœ ˜Kšœ žœ˜Kšœžœ˜K˜K˜Kšœžœ˜'K˜šΟn œžœžœžœ˜1Kšž˜Kšžœ ˜Kšžœ˜K˜—š œžœžœ!žœ˜>KšžœŸ-˜3Kšœ%žœ˜.Kšœ žœ˜$K˜Kšœžœ˜Kšœ žœ˜K˜Kšœžœ˜ Kšžœ žœžœ˜9Kšœ!Ÿ ˜Ašž˜Kšœ.™.K˜ Kšžœžœžœ˜Kšœžœ˜K˜Kšœ!™!K˜ Kšœ™K˜ Kšœ"™"K˜ Kšœ"™"K˜ Kšœ™Kšžœ žœ˜KšžœŸ0˜9—KšœG™GK˜Kšœ1™1K˜Kšœ-™-K˜#K˜Kšœ(™(šžœžœžœž˜CK˜K˜Kšžœ˜—Kšœ-™-Kšžœžœ ˜ Kšœ™K˜Kšžœžœ ˜!Kšžœ˜K˜K˜—š œžœ žœ˜%KšžœŸ˜&K˜šžœ)žœ ž˜?K˜šžœžœž˜˜šžœ žœ˜%Kšžœ˜šžœž˜Kšž˜K˜K˜%K˜Kšž˜———Kšžœ˜—Kšžœ˜—Kšžœ˜K˜—š œžœžœžœ˜0KšžœŸ#˜*K˜šžœžœ ž˜0šžœ žœž˜Kšœžœžœ˜:K˜˜Kšž˜Kšžœ žœžœ˜K˜Kšžœ˜—šœ žœžœž˜Kšœ žœ˜Kšžœ˜—Kšžœžœ˜—Kšžœ˜—Kšžœžœ˜Kšžœ˜K˜K˜—š œžœ˜KšžœŸ1˜8K˜šžœ&žœ ž˜šœ žœ žœž˜#K˜Kšœžœžœžœ ˜-šœ žœžœž˜K˜Kšžœ˜—Kšžœ˜—šžœ žœž˜˜Kšžœ žœ!žœ˜=Kšžœ ˜—K˜Kšžœ˜—K˜šž˜Kšœžœ˜ —Kšœ˜Kšžœ˜—Kšžœ˜K˜—š  œžœžœ žœ˜GKšžœŸ˜%Kšžœ˜K˜ šœ žœžœ ˜5K˜7K˜—K˜šžœž˜ ˜šžœž˜ ˜Kšž˜Kš žœžœžœžœžœ˜>K˜Kšžœ˜—˜Kšž˜Kš žœžœžœ žœžœ˜CK˜Kšžœ˜—šžœ˜ Kšž˜K˜Kšžœ˜———˜šžœž˜ ˜Kšž˜Kš žœžœžœžœžœ˜>Kšœžœ žœžœ˜2Kšžœ˜—˜Kšž˜Kš žœžœžœ žœžœ˜CKšœžœ žœžœ˜3Kšžœ˜—šžœ˜ Kšž˜Kšœžœ žœžœ ˜,K˜Kšžœ˜———Kšœ žœ˜šžœ˜ šžœž˜ ˜Kšž˜Kš žœžœžœ žœžœ˜CK˜Kšžœ˜—šžœ˜ Kšž˜K˜K˜Kšžœ˜————Kšœžœ˜KšœŸ:˜KKšžœ˜K˜—Kšžœ˜K˜K˜——…—0ΆH