.mesa_Sep78 .mesa Sep78

.mesa_Sep78 .mesa_Sep78

User Manual: .mesa_Sep78

Open the PDF directly: View PDF .
Page Count: 8

Download
Open PDF In Browser	View PDF

Fina1.mesa

2-Sep-78 12:59:59

-- Fina1.mesa, modified by Sweet, July 5, 1978

Page

1

9:28 AM

DIRECTORY
Code: FROM "code" USING [CodePassInconsistancy],
CodeDefs: FROM "codedefs" USING [CCIndex, CCNul1, ChunkBase, JumpCCIndex, JumpCCNu11, JumpType, Label
··CCIndex, Labe1CCNul1],
FOpCodes: FROM "fopcodes",
InlineDefs: FROM "in1inedefs",
OpTab1eDefs: FROM "optabledefs" USING [insta1igned, inst1ength],
P5ADefs: FROM "p5adefs" USING [deletecell],
P5BDefs: FROM "p5bdefs" USING [bindjump, codejump, Cpeepho1e],
TableDefs: FROM "tabledefs" USING [TableNotifier],
TreeDefs: FROM "treedefs" USING [treetype];
DEFINITIONS FROM CodeDefs;
Final: PROGRAM
IMPORTS CPtr: Code, OpTableDefs, P5ADefs, P5BDefs
EXPORTS CodeDefs, P5BDefs •
BEGIN
OPEN P5ADefs, P5BDefs;
cb: ChunkBase;

-- code base (local copy)

CJump: ARRAY JumpType[JumpE .. ZJumpN] OF JumpType a [
JumpN, JumpE, JumpGE, JumpL, JumpLE, JumpG,
UJumpGE, UJumpL, UJumpLE, UJumpG, ZJumpN, ZJumpE];
FinalNotify: PUBLIC TableDefs.TableNotifier a
BEGIN -- called by allocator whenever table area is repacked
cb ~ LOOPHOLE[base[TreeDefs.treetype]];
RETURN
END;
DidSomething: BOOLEAN;
StartIndex, EndIndex: CCIndex;
SeenSwitch: BOOLEANi
JumpCellCount: CARDINAL;
ThreadsValid: BOOLEAN;
AreThreadsValid: PUBLIC PROCEDURE RETURNS [BOOLEAN] •
BEGIN
RETURN[ThreadsValid]
END;
Cfixup: PUBLIC PROCEDURE [start: CCIndex] m
BEGIN -- a final pass over the code to fix up jumps
ThreadsValid ~ TRUE;
DidSomething ~ TRUE;
SeenSwitch ~ TRUE;
StartIndex ~ start;
--ComplementCursor[]i
DO
-- pass 0: distinguish forward and backward jumps
CPassO[];
IF -DidSomething THEN EXIT;
DidSomething ~ FALSE;
SeenSwitch ~ -SeenSwitch;
-- pass 1: convert conditional backward jumps to canonical form
--CPass1[];
-- pass 2: eliminate multiple labels
CPass2[];
-- pass 3: eliminate jump to jumps
CPass3[];
-- pass 4: eliminate unreachable code
CPass4[];
ENDLOOP; -- end of the meta-pass consisting of passes 0-4
-- pass 5: replace cj-j seq. with ccj
CPass5[];
-- pass 6: do some peephole optimization: load-store, EXCH-commutative op.
Cpeephole[StartIndex];
-- jump threads no longer maintained, debug output take note
ThreadsValid ~ FALSE;

Final.mesa

2-Sep-78 12:59:59

-- pass 7: set length and alignment (most already set)
CPass7[] :
-- pass 8: resolve (most) jump instructions
CPass8[]:
-- pass 9: resolve (remaining) jump instructions
Cpass9[]:
-- pass 10: set pad fields
CPass10[] :
-- pass 11: code jumps
CPassll[] :
--ComplementCursor[]:
RETURN
END:
ComplementCursor: PROCEDURE •
BEGIN
i: CARDINAL;
FOR i IN [431B .. 431B+16) DO MEMORY[i]
RETURN
END;

~

InlineDefs.BITNOT[MEMORY[i]] ENDLOOP:

CPassO: PROCEDURE·
BEGIN -- pass 0: distinguish forward and backward jumps
c: CClndex;
JumpCellCount ~ 0;
FOR c ~ cb[Startlndex].flink. cb[c].flink WHILE c # CCNull DO
End Index ~ c;
WITH cb[c] SELECT FROM
label =) labelseen r SeenSwitch;
jump .. )
BEGIN
forward ~
IF destlabel .. LabelCCNull THEN TRUE
ELSE -(cb[destlabel].labelseen .. SeenSwitch);
JumpCellCount r JumpCellCount + 1;
END;
ENDCASE;
ENDLOOP:
RETURN
END;
CPass2: PROCEDURE •
BEGIN
-- pass 2: eliminate multiple labels
duplabel. unreferencedlabel: LabelCCIndex:
nextc. c: CCIndex;
FOR c ~ cb[StartIndex].flink. nextc WHILE c # CCNull DO
WITH cc:cb[c] SELECT FROM
label =)
IF cc.jumplist .. JumpCCNull THEN
BEGIN
unreferencedlabel r LOOPHOLE[c. LabelCCIndex]; nextc ~ cc.flink;
DidSomething r TRUE; deletecell[unreferencedlabel];
END
ELSE
BEGIN
duplabel r LOOPHOLE[c. LabelCClndex]; nextc ~ cc.flink;
IF cc.flink a CCNull THEN RETURN;
WITH cb[cc.flink] SELECT FROM
label "')
BEGIN
deletelabel[duplabel. LOOPHOLE[cc.flink. LabelCCIndex]];
OidSomething r TRUE;
END;
ENDCASE;
END;
ENDCASE =) nextc ~ cc.flink;
ENDLOOP;
RETURN
END;
CPass3: PROCEDURE·

Page

2

Final.mesa

2-Sep-78 12:69:69

BEGIN
-- pass 3: eliminate jump to jumps
e, ee, olde: CClndex:
je: JumpCClndexi
jtojexists: BOOLEANi
jelabel, formerlabel: LabelCClndex:
jeeount: CARDINAL:
FOR e ~ eb[Startlndex].flink, eb[e].flink WHILE e # CCNull DO
WITH eb[e] SELECT FROM
jump .>
IF destlabel # LabelCCNull THEN
BEGIN
jtojexists ~ FALSE:
jeeount ~ 0:
je ~ LOOPHOLE[e, JumpCClndex]:
DO
jelabel ~ eb[je].destlabel:
IF (ec ~ cb[jclabel].flink) • CCNull THEN EXITi
IF -UCjump[cc] THEN EXIT:
jc ~ LOOPHOLE[cc, JumpCClndex]:
IF je • c THEN BEGIN jtojexists ~ FALSEi EXIT END:
jeeount ~ jecount +1:
IF jceount > JumpCellCount THEN
BEGIN jtojexists ~ FALSE; EXIT ENDi
IF jtype • JumpC AND -cb[jc].forward THEN EXIT:
jtojexists ~ TRUEi
ENDLOOPi
IF jtojexists THEN
BEGIN
DidSomething ~ TRUEi
formerlabel ~ destlabeli
unthreadjump[LOOPHOLE[c, JumpCClndex]];
IF jtype • JumpC AND cb[formerlabel].jumplist • JumpCCNull THEN
BEGIN
cc ~ cb[formerlabel].flink;
deletecell[formerlabel];
DO
oldc ~ cc;
cc ~ cb[cc].flinki
WITH cb[oldc] SELECT FROM
label.> EXIT;
jump -> unthreadjump[LOOPHOLE[oldc, JumpCClndex]];
ENDCASE;
deletecell[oldc];
ENDLOOP;
END;
thread ~ cb[jclabel].jumplist;
cb[jclabel].jumplist ~ LOOPHOLE[c, JumpCCIndex];
destlabel ~ jclabel:
END;
END;
ENDCASE
ENDLOOP;
RETURN
ENDi
CPass4: PROCEDURE •
BEGIN
-- pass 4: eliminate unreachable code
c, cc, oldc: CClndex:
FOR c ~ eb[StartIndex].flink, eb[e].flink WHILE e # CCNull DO
WITH cb[e] SELECT FROM
jump .>
IF UCjump[e] OR jtype • JumpRet THEN
BEGIN
ce ~ flink;
DO
IF (olde ~ ee) • CCNull THEN RETURN;
cc ~ cb[cc].flink:
WITH cb[olde] SELECT FROM
label -> IF jumplist # JumpCCNull THEN EXIT;
jump .> unthreadjump[LOOPHOLE[olde, JumpCClndex]]:
other .> EXIT;
ENOCASE;
deleteeell[olde]i

Page

3

Final.mesa

DidSomething
ENDLOOP;
END;
ENDCASE;
ENDLOOP;
RETURN
END;

2-Sep-78 12:59:59

~

TRUE;

CPass5: PROCEDURE •
BEGIN
-- pass 5: replace cj-j seq. with ccj
c, nextc: CCIndex;
FOR c ~ cb[StartIndex].flink, cb[c].flink WHILE c # CCNull DO
WITH oldc:cb[c] SELECT FROM
jump ->
IF oldc.jtype • JumpRet THEN
BEGIN
nextc ~ oldc.b11nk;
deletecell[c];
c ~ nextc;
END ELSE
IF -UCjump[c] THEN
BEGIN
nextc ~ oldc.flink;
IF nextc .. CCNull THEN RETURN;
WITH cb[nextc] SELECT FROM
jump =>
IF UCjump[nextc] AND (oldc.forward .. forward)
AND (cb[oldc.destlabel].blink .. nextc) THEN
BEGIN
unthreadjump[LOOPHOLE[nextc, JumpCCIndex]];
unthreadjump[LOOPHOLE[c, JumpCCIndex]];
oldc.destlabel ~ destlabel;
oldc.thread ~ cb[oldc.destlabel].jumplist;
cb[oldc.destlabel].jumplist ~ LOOPHOLE[C, JumpCCIndex];
oldc.jtype ~ CJump[oldc.jtype];
deletecell[nextc];
END;
ENDCASE;
END;
ENDCASE;
ENDLOOP;
RETURN
END;
CPass7: PROCEDURE·
BEGIN -- pass 7: set length and alignment (most already set)
c: CCIndex;
FOR c ~ cb[StartIndex].flink, cb[c].flink WHILE c # CCNull DO
WITH cb[c] SELECT FROM
code ->
BEGIN
IF isize .. 0 THEN isize ~ OpTableDefs.instlength[inst];
aligned ~ isize .. 3 OR OpTableDefs.instaligned[inst];
END;
ENDCASE;
ENDLOOP;
END;
CPass8: PROCEDURE ..
BEGIN
-- pass 8: resolve (most) jump instructions
c, prey: CCIndex;
min, max: CARDINAL;
FOR c ~ cb[StartIndex].flink, cb[c].flink WHILE c # CCNull DO
End Index ~ c;
ENDLOOP;
DidSomething ~ TRUE;
WHILE DidSomething DO
DidSomething ~ FALSE;
FOR c ~ Endlndex, prey WHILE c # CCNull DO
prey ~ cb[c].blink;
WITH cb[c] SELECT FROM
jump ->

Page

4

2-Sep-78 12:59:59

Final.mesa

Page

IF

~fixedup THEN
BEGIN
[min, max] ~ EstimateJumpDistance[LOOPHOLE[c, JumpCCIndex]]:
IF max • 0 THEN
IF Removeablejump[c] AND forward THEN
BEGIN
DidSomething ~ TRUE:
IF c • EndIndex THEN EndIndex ~ prey:
del etecel1 [c]:
END
ELSE
BEGIN
IF bindjump[O, 0: LOOPHOLE[c, JumpCClndex]] THEN
DidSomething ~ TRUE:
END
ELSE
BEGIN
IF bindjump[min. max. LOOPHOLE[c. JumpCCIndex]] THEN
DidSomething ~ TRUE:
END:
END:
ENDCASE:
ENDLOOP:
ENDLOOP:
RETURN
END;

CPass9: PROCEDURE·
BEGIN -- pass 9: resolve (remaining) jump instructions
c. prey: CCIndex;
nbytes: CARDINAL;
FOR c ~ EndIndex. prey WHILE c # CCNull DO
prey ~ cb[c].blink;
WITH cb[c] SELECT FROM
jump ->
IF ~fixedup THEN
BEGIN
nbytes ~ EstimateJumpDistance[LOOPHOLE[c. JumpCCIndex]].max;
[] ~ bindjump[nbytes. nbytes. LOOPHOLE[c. JumpCCIndex]]:
END;
ENDCASE;
ENDLOOP:
RETURN
END:
CPass10: PROCEDURE •
BEGIN -- pass 10: set pad field of chunks
c: CCIndex;
parity: [0 .• 2] ~ 0;
cpad: [0 .. 1];
aligned: BOOLEAN:
t: CARDINAL;
FOR c ~ cb[StartIndex].flink. cb[c].flink WHILE c
WITH cc:cb[c] SELECT FROM
code .. >
BEGIN
t ~ cc.isize;
aligned ~ cc.aligned;
END;
other '"> WITH cc SELECT FROM
table ->
BEGIN
t ~ tablecodebytes;
ali9ned ~ TRUE;
END;
ENDCASE .>
BEGIN
t

~

#

CCNull DO

0;

aligned
END;

~

FALSE;

jump ->
IF cc.completed THEN BEGIN t
ELSE

~

0; aligned

~

FALSE END

5

Final.mesa

2-Sep-78 12:59:59

Page

6

BEGIN
t to cc.jsize:
aligned to t > 1:
END:
1abel·>
BEGIN
t to 0:
aligned to FALSE:
END:
ENDCASE:
parity to (parity+t) MOD 2:
IF aligned AND parity # 0 THEN
BEGIN
cpad to 1:
parity to 0:
END
ELSE cpad to 0:
cb[c].pad to cpad:
ENDLOOP:
END:
CPassl1: PROCEDURE·
BEGIN
-- pass 11: code jumps
c: CCIndex:
FOR c to cb[StartIndex].flink. cb[c].flink WHILE c # CCNull DO
WITH cb[c] SELECT FROM
jump .>
BEGIN
IF -fixedup THEN SIGNAL CPtr.CodePassInconsistancy
ELSE codejump[ComputeJumpDistance[LOOPHOLE[c. JumpCCIndex]]. LOOPHOLE[c. JumpCCIndex]]:
END;
ENDCASE:
ENDLOOP;
RETURN
END;
deletelabel: PROCEDURE [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 to cb[c].jumplist:
UNTIL q • JumpCCNull DO
lq to q:
q ... cb[q].thread:
ENDLOOP;
cb[lq].thread to cb[oldc].jumplist:
END;
FOR q ... cb[oldc].jumplist. cb[q].thread UNTIL q • JumpCCNull
DO cb[q].destlabel to c ENDLOOP:
deletecell[oldc];
RETURN
END:
unthreadjump: PROCEDURE [c: JumpCCIndex] •
BEGIN -- pull jump cell out of thread from label
1: LabelCCIndex to cb[c].destlabel;
jc: JumpCCIndex;
IF 1 = 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 to cb[jc].thread ENDlOOP:
cb[jc].thread ... cb[c].thread;
END;
RETURN
END;

Final.mesa

2-Sep-78 12:69:69

Page

UCjump: PROCEDURE [c: CCIndex] RETURNS [BOOLEAN] •
BEGIN -- predicate testing if c is an unconditonal jump
WITH cb[c] SELECT FROM
jump -) RETURN[jtype - Jump];
ENDCASE -) RETURN[FALSE]
END;
Removeablejump: PROCEDURE [c: CCIndex] RETURNS [BOOLEAN] BEGIN -- predicate testing if c ;s an unconditonal jump
WITH cb[c] SELECT FROM
jump -) RETURN[(jtype - Jump OR jtype - JumpA OR jtype - JumpCA)];
ENDCASE -) RETURN[FALSE]
END;
dMinMax: ARRAY {unconditional. equal. relational} OF
ARRAY [0 .. 2] OF PACKED ARRAY BOOLEAN OF RECORD [min.max: [0 .. 15]]
[ [[[2.4].[1.4]]. -- unconditional. parity 0 (backward. forward)
[[3.3].[1.3]]. -- unconditional. parity 1 (backward. forward)
[[2.4].[1.4]]]. -- unconditional. parity 2 (backward. forward)
[[[2.4].[1.4]]. -- equal. parity 0 (backward. forward)
[[3.5].[1.5]]. -- equal. parity 1 (backward. forward)
[[2.5].[1.5]]]. -- equal. parity 2 (backward. forward)
[[[2.6].[2.6]]. -- relational. parity 0 (backward. forward)
[[3.7].[3.7]]. -- relational. parity 1 (backward. forward)
[[2.7].[2.7]]]]; -- relational. parity 2 (backward. forward)

~

EstimateJumpDistance: PROCEDURE [c: JumpCCIndex] RETURNS [min.max: CARDINAL] BEGIN -- counts the number of bytes between a jump and its label.
label: CCIndex ~ cb[c].destlabel;
start.end.k: CCIndex;
t: CARDINAL;
parity: [0 .. 2] ~ 2;
dMin. dMax: [0 .. 15];
min ~ max ~ 0;
IF cb[c].forward THEN BEGIN start ~ c; end ~ label END
ELSE BEGIN start ~ label; end ~ c END;
FOR k ~ cb[start].flink. cb[k].flink UNTIL k - end DO
WITH cc:cb[k] SELECT FROM
code -)
BEGIN
t ~ cc.isize;
IF cc.aligned THEN
BEGIN
IF parity • 2 THEN max ~ max + 1
ELSE IF (parity+t) MOD 2 # 0 THEN t ~ t + 1;
parity ~ 0;
END
ELSE IF parity # 2 THEN parity ~ (parity+t) MOD 2;
min ~ min + t;
max ~ max + t;
END;
jump .) IF cc.jtype # JumpC THEN
BEGIN
IF -cc.fixedup THEN
BEGIN
[dMin.dMax] ~ dMinMax[(SELECT cc.jtype FROM
Jump.JumpA.JumpCA =) unconditional.
JumpE.JumpN .) equal,
ENDCASE a) relational)][parity][cc.forward];
min ~ min+dMin; max ~ max+dMax;
parity ~ (SELECT cc.jtype FROM
Jump.JumpA,JumpCA -) 2.
JumpE.JumpN .) IF cc.forward AND parity # 1 THEN 2 ELSE 0,
ENDCASE -) 0);
END
ELSE IF -cc.completed THEN
BEGIN
t ~ cc.jsize;
IF t • 1 THEN
BEGIN IF parity # 2 THEN parity ~ (parity+l) MOD 2 END
ELSE
BEGIN

7

Final.mesa

2-Sep-78 12:59:69

IF parity· 2 THEN max ~ max + 1
ELSE IF (parity+t) MOD 2 # 0 THEN t ~ t + 1:
parity ~ 0:
END:
min ~ min + t:
max ~ max + t:
END:
END;
other·> WITH cc SELECT FROM
table .>
BEGIN
t ~ tablecodebytes;
.
IF parity· 2 THEN max ~ max + 1
ELSE IF (parity+t) MOD 2 # 0 THEN t ~ t + 1:
parity ~ 0:
min ~ min + t;
max ~ max + t;
END:
ENDCASE;
ENDCASE;
ENDLOOP:
RETURN
END;
ComputeJumpDistance: PROCEDURE [c: JumpCCIndex] RETURNS [nbytes: CARDINAL] •
BEGIN -- counts the number of bytes between a jump and its label.
-- all jump lengths have been resolved and pad values set
label: CCIndex ~ cb[c].destlabel;
start.end.k: CCIndex:
nbytes ~ 0;
IF cb[c].forward THEN BEGIN start ~ c: end ~ label END
ELSE BEGIN start ~ label: end ~ c END;
FOR k ~ cb[start].flink. cb[k].flink UNTIL k • end DO
nbytes ~ nbytes+cb[k].pad + (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);
ENDLOOP;
RETURN
END:
END ...

Page

8



---

Source Exif Data:

File Type                       : PDF
File Type Extension             : pdf
MIME Type                       : application/pdf
PDF Version                     : 1.3
Linearized                      : No
XMP Toolkit                     : Adobe XMP Core 4.2.1-c043 52.372728, 2009/01/18-15:56:37
Create Date                     : 2010:10:27 18:53:40-08:00
Modify Date                     : 2010:10:27 19:03:13-07:00
Metadata Date                   : 2010:10:27 19:03:13-07:00
Producer                        : Adobe Acrobat 9.4 Paper Capture Plug-in
Format                          : application/pdf
Document ID                     : uuid:32dd52af-c472-4f7f-8008-e49f6b8c48f1
Instance ID                     : uuid:2371f76c-9290-4fbb-8f42-66714044afc5
Page Layout                     : SinglePage
Page Mode                       : UseNone
Page Count                      : 8

EXIF Metadata provided by EXIF.tools