Final.mesa
last modified by Sweet, 15-Sep-82 16:42:40
edited by Satterthwaite, December 1, 1985 4:06:53 pm PST
DIRECTORY
Alloc: TYPE USING [Notifier],
Code: TYPE USING [
bodyRecurLabel, CodePassInconsistency, codeptr, tailJumpOK],
CodeDefs: TYPE USING [
Base, CCIndex, CCInfoType, CCNull, codeType, JumpCCIndex, JumpCCNull,
JumpType, LabelCCIndex, LabelCCNull, RelativePC, TableCodeBytes],
ComData: TYPE USING [bodyIndex, switches],
FOpCodes: TYPE USING [qADD, qDIS, qLFC, qLI, qLL, qRET, qSELFC, qSFC],
OpTableDefs: TYPE USING [InstLength],
P5: TYPE USING [C0, C1, PeepHole],
P5F: TYPE USING [BindJump, CodeJump, CPass5, FillInPCEstimates],
P5U: TYPE USING [DeleteCell, OutJump],
PeepholeDefs: TYPE USING [
CJump, NextInteresting, PrevInteresting, RemoveThisPop, SetRealInst],
PrincOps: TYPE USING [framelink],
Symbols: TYPE USING [Base, CBTIndex, BTIndex, bodyType];
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)
bb: Symbols.Base;
FinalNotify: PUBLIC Alloc.Notifier =
BEGIN -- called by allocator whenever table area is repacked
cb ← base[codeType];
bb ← base[Symbols.bodyType];
END;
DidSomething: PUBLIC BOOL;
StartIndex, EndIndex: PUBLIC CCIndex;
SeenSwitch: BOOL;
JumpCellCount: CARDINAL;
ccInfo: PUBLIC CCInfoType ← generating;
CCInfoMeaning: PUBLIC PROC RETURNS [CCInfoType] =
BEGIN
RETURN[ccInfo]
END;
Fixup: PUBLIC PROC [start: CCIndex, 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];
TailJump[crossJump AND CPtr.tailJumpOK];
CPtr.bodyRecurLabel ← LabelCCNull; -- avoid dangling ref if deleted
DO
pass 0: distinguish forward and backward jumps
CPass0[];
IF ~DidSomething THEN EXIT;
DidSomething ← FALSE;
SeenSwitch ← ~SeenSwitch;
pass 1: eliminate multiple labels
CPass1[];
pass 2: eliminate jump to jumps
CPass2[];
pass 3: eliminate unreachable code
CPass3[];
pass 4: replace cj-j seq. with ccj
CPass4[];
pass 5: cross jumping
IF crossJump THEN P5F.CPass5[];
ENDLOOP; -- end of the meta-pass consisting of passes 0-5
pass 6: do some peephole optimization: load-store, EXCH-commutative op.
P5.PeepHole[StartIndex];
jump threads are now pc's, debug output take note
ccInfo ← binding;
pass 7: set length and alignment, count jumps
totalJumps ← jumpsafter ← CPass7[];
jumpsbefore ← jumpsafter+1;
pass 8: resolve (most) jump instructions
THROUGH [1..3] WHILE jumpsafter # 0 AND jumpsafter < jumpsbefore DO
jumpsbefore ← jumpsafter;
jumpsafter ← CPass8[];
ENDLOOP;
pass 9: resolve (remaining) jump instructions
IF jumpsafter # 0 THEN CPass9[];
pass 10: code jumps
ccInfo ← coding;
IF totalJumps # 0 THEN CPass10[];
pass 11: Remove extra source chunks
CPass11[];
END;
TailJump: PROC [jumpOK: BOOL] =
BEGIN -- remove simple tail recursion
enableLevel: CARDINAL ← 0;
next: CCIndex;
FOR c: CCIndex ← cb[StartIndex].flink, next WHILE c # CCNull DO
next ← cb[c].flink;
WITH cc: cb[c] SELECT FROM
code =>
IF ~cc.realinst AND cc.inst = FOpCodes.qSELFC THEN {
CPtr.codeptr ← cb[c].blink;
IF jumpOK AND enableLevel = 0 AND UCreturn[next] THEN
BEGIN
P5U.OutJump[Jump, CPtr.bodyRecurLabel];
P5U.DeleteCell[c]
END
ELSE
BEGIN
bti: Symbols.CBTIndex = MPtr.bodyIndex;
WITH body: bb[bti] SELECT FROM
Outer => {P5.C1[FOpCodes.qLFC, body.entryIndex]; P5U.DeleteCell[c]};
Inner => {
P5.C1[FOpCodes.qLL, PrincOps.framelink];
P5.C1[FOpCodes.qLI, body.frameOffset];
P5.C0[FOpCodes.qADD];
P5.C0[FOpCodes.qSFC];
P5U.DeleteCell[c]};
ENDCASE => ERROR;
END};
other => WITH oc: cc SELECT FROM
markbody => {
index: Symbols.BTIndex = oc.index;
WITH bb[index] SELECT FROM
Callable => EXIT;
ENDCASE};
markCatch =>
IF oc.start THEN enableLevel ← enableLevel + 1
ELSE enableLevel← enableLevel - 1;
ENDCASE;
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, markCatch => 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 ← cb[StartIndex].flink, 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,
and jumps to .+1
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 AND ~cc.catch THEN
BEGIN
unreferencedlabel: LabelCCIndex ← LOOPHOLE[c, LabelCCIndex];
DidSomething ← TRUE; P5U.DeleteCell[unreferencedlabel];
END
ELSE
BEGIN
duplabel: LabelCCIndex ← LOOPHOLE[c, LabelCCIndex];
IF nextc = CCNull THEN RETURN;
WITH cb[nextc] SELECT FROM
label =>
BEGIN
DeleteLabel[duplabel, LOOPHOLE[nextc, LabelCCIndex]];
DidSomething ← TRUE;
END;
ENDCASE;
END;
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.qDIS];
[] ← 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 BEGIN jtojexists ← FALSE; EXIT END;
jccount ← jccount +1;
IF jccount > JumpCellCount THEN
BEGIN jtojexists ← FALSE; EXIT END;
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;
IF jj.jtype = JumpLIO THEN cb[jclabel].offsetLoaded ← TRUE;
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 OR catch THEN EXIT;
jump => UnthreadJump[LOOPHOLE[oldc, JumpCCIndex]];
other => IF otag # table THEN LOOP; --body start/stop, source
ENDCASE;
P5U.DeleteCell[oldc];
DidSomething ← TRUE;
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] THEN
BEGIN
IF nextc = CCNull THEN RETURN;
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;
END;
ENDCASE => nextc ← cb[c].flink;
ENDLOOP;
END;
CPass7: PROC RETURNS [unboundJumps: CARDINAL] =
BEGIN -- pass 7: set length, count jumps
c, next: CCIndex;
look for body starting with a loop
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;
unboundJumps ← 0;
FOR c ← cb[StartIndex].flink, next WHILE c # CCNull DO
next ← cb[c].flink;
WITH cb[c] SELECT FROM
code => IF isize = 0 THEN isize ← OpTableDefs.InstLength[inst];
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;
CPass10: PROC =
BEGIN -- pass 10: 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;
IF cb[oldc].offsetLoaded THEN cb[c].offsetLoaded ← TRUE;
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.
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)
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 BEGIN rpc ← rpc+nbytes; cc.pc ← rpc; LOOP END
ELSE cc.pc ← rpc;
label => cc.pc ← rpc;
ENDCASE;
rpc ← rpc+nbytes;
ENDLOOP;
END;
CPass11: PROC =
BEGIN -- pass 11: Remove extra source chunks
prev: CCIndex ← CCNull;
FOR c: CCIndex ← cb[StartIndex].flink, cb[c].flink WHILE c # CCNull DO
WITH cc: cb[c] SELECT FROM
code => prev ← CCNull;
other => WITH cc SELECT FROM
table => prev ← CCNull;
source => {
IF prev # CCNull THEN P5U.DeleteCell[prev];
prev ← c};
ENDCASE;
ENDCASE;
ENDLOOP;
END;
END.