Download - Intr Code Gnrn
-
8/9/2019 Intr Code Gnrn
1/38
Subject code: 6CS63/06IS662Subject code: 6CS63/06IS662 NO. of lectures per week: 04NO. of lectures per week: 04
Total No. of lecture hrs: 52Total No. of lecture hrs: 52 IA marks : 25IA marks : 25 Exam hrs: 03Exam hrs: 03
Exam marks:100Exam marks:100
-
8/9/2019 Intr Code Gnrn
2/38
Unit 6: Intermediate code generation
Syllabus:Syl
labus:Variants of syntax trees;three-addressVariants of syntax trees;three-addresscode;types & declarations;Translationcode;types & declarations;Translationof expressions;type checking;controlof expressions;type checking;controlflow;back patching;switch statements;flow;back patching;switch statements;Intermediate code for procedues.Intermediate code for procedues.
:8 hrs:8 hrs
-
8/9/2019 Intr Code Gnrn
3/38
-
8/9/2019 Intr Code Gnrn
4/38
ParserStatic
checker
IntermediateCode
Generator
CodeGenerator
Intermediate
Code
We assume that a compiler front end isorganized as in the figure shown below
Here parsing, static checking, andintermediate-code generation are donesequentially.
Source
Pgm.
Front end
Back end
-
8/9/2019 Intr Code Gnrn
5/38
Directed Acyclic Graphs (DAG)
Leaves correspond to atomic operandsLeaves correspond to atomic operands Interior nodes correspond to operatorsInterior nodes correspond to operators A node N in a DAG can have more thanA node N in a DAG can have more than
one parent if N represents a commonone parent if N represents a commonsubexpressionsubexpression
Advantages:
Represents expressions more succinctlyRepresents expressions more succinctly Gives the compiler more clues forGives the compiler more clues for
generation of efficient codegeneration of efficient code
-
8/9/2019 Intr Code Gnrn
6/38
Constructing a DAG
A syntax directed definition is used toconstruct a DAG
The steps are similar to the construction of
syntax trees But before creating a new node we needto check whether an identical node alreadyexists
If such a node exists the existing node isreturned else a new node is created.
-
8/9/2019 Intr Code Gnrn
7/38
The value-number method
Nodes of a syntax tree or DAG can be stored as anarray of records. Each row of the array represents anode
In each record the first field represents an operationcode
For leaves one additional field holds the lexical value For interior nodes there are two additional fields for
left and right children We refer to each node with integer index of the
array called the value number
-
8/9/2019 Intr Code Gnrn
8/38
Algorithm for value-number
methodSuppose that nodes are stored in an array
and each node is referred to by its valuenumber. Input: label op,node l and node r Output:the value of node in the array with signature
Method:search the array for the node with label
op,left child l & right child r.If found return its valuenumber.If not found,we create in the array a new
node with label op left child l and right child r &return its value number
-
8/9/2019 Intr Code Gnrn
9/38
DAG ConstructionDAG Construction
i = i + 10i = i + 10
1 id * To i
2 num 10
3 + 1 2
4 = 1 3
=
i
+
10
-
8/9/2019 Intr Code Gnrn
10/38
-
8/9/2019 Intr Code Gnrn
11/38
Using Hash tables & BucketsUsing Hash tables & Buckets
PointerTo list ofnodes(sub-trees)
-
8/9/2019 Intr Code Gnrn
12/38
Three-address code
In three-address code,there is at most oneoperator on the right side of an instuction
If more than one operator is to be used
then they are simplifiedEg.X+y*z can be written as
T1=y*z
T2=x+T1 Three address code is built from two
concepts: addresses and instructions
-
8/9/2019 Intr Code Gnrn
13/38
Addresses
Address are of three types A name: source program names can
appear as addresses in three addersscode
A constant: compiler must be able todeal with different types of constants
A compiler generated temporary areused as addresses
-
8/9/2019 Intr Code Gnrn
14/38
Three address instructions
Assignment instructions: x=y op z; Assignments of the form: x=op y; Copy instructions: x=u;
An unconditional jump: goto L Conditional jumps(1): if x goto L Conditional jumps(2): if x relop y goto L For procedure calls and returns Indexed copy instructions Address and pointer assignments: x=&y
-
8/9/2019 Intr Code Gnrn
15/38
Quadruples
Quadruples are used to implement the threeaddress instructions in compilers. They havefour fields: op,arg1,arg2 & result.Exceptions
are: Instructions with unary operators Eg x=ydo not use arg2
Conditional & unconditional jumps put thetarget label in result. Operators like param [used pass the
parameter] use neither arg2 nor result
-
8/9/2019 Intr Code Gnrn
16/38
Quadruple representationQuadruple representation
b*-c+b*-cb*-c+b*-c
position Op Arg1 Arg2 result1 minus c t1
2 * b t1 t2
3 minus c t3
4 * b t3 t4
5 + t2 t4 t56 = t3 a
7
-
8/9/2019 Intr Code Gnrn
17/38
TRIPLES
They are also used in the implemention ofThey are also used in the implemention ofthree adress instructionsthree adress instructions but use only threeuse only threefields. The result field is missing herefields. The result field is missing here Using the triples we refer to the result ofUsing the triples we refer to the result ofan operation by its position rather than by aan operation by its position rather than by atemporary name.temporary name. When instructions are moved around weWhen instructions are moved around weneed to change all references to that resultneed to change all references to that result
-
8/9/2019 Intr Code Gnrn
18/38
Indirect Triples
They consist of listing of pointers totripples.
Here we can move an instruction by
reordering the instruction list withoutaffecting the tripples themselves.
-
8/9/2019 Intr Code Gnrn
19/38
Triple representationTriple representation
b*-c + b*-cb*-c + b*-c
position op Arg1 arg2
0 minus c
1 * b (0)2 minus c
3 * b (2)
4 + (1) (3)
5 = a (4)
-
8/9/2019 Intr Code Gnrn
20/38
Static single-assignment form
SSA is an intermediate repersentation that facilitatescertain code optimisations.
All assignments are to variables with distinct namesp1 = a+ b
q1 = p1-cp2= q1*dp3= e-p2q2= p3+q1If (flag) x = -1 ;else x = 1;
If (flag) x1 = -1 ;else x2 = 1;x3 =(x1,x2);
-
8/9/2019 Intr Code Gnrn
21/38
Types and Declarations
ex : int[2][3]
DD T id ; | D |T id ; | D | TT B C | record { D } B C | record { D } BB int | floatint | float
CC | [ num] C| [ num] C
T
int
C
[2] C
[3] C
Example:
-
8/9/2019 Intr Code Gnrn
22/38
Storage layoutStorage layout
Computing types and widthsComputing types and widths
TT B {t= B.type ; w = B.width}B {t= B.type ; w = B.width}
CCBB int {B.type = integer ; B.width = 4}int {B.type = integer ; B.width = 4}BB float {B.type = float ; B.width = 8}float {B.type = float ; B.width = 8}CC {C.type = t ; C.width =w}{C.type = t ; C.width =w}
CC [num]C1 {array(num.value,C1.type);[num]C1 {array(num.value,C1.type);C.width = num.value*C1.width}C.width = num.value*C1.width}
-
8/9/2019 Intr Code Gnrn
23/38
Translation of expressionsTranslation of expressions
Production Semantic rules
Sid = E S.CODE = E.CODE|| GEN(TOP.GET(ID.LEXEME =E.ADDR))
E E1 + E2 E.ADDR = NEW TEMP() E.CODE = E1.CODE || E2.CODE|| GEN(E.ADDR = E1.ADDR + E2.ADDR)
|-E1 E.ADDR = NEW TEMP()E.CODE = E1.CODE || GEN(E.ADDR = MINUSE1.ADDR )
|(E1) E.ADDR = E1.ADDRE.CODE = E1.CODE
|ID E.ADDR = TOP.GET(ID.LEXEME)E.CODE =
-
8/9/2019 Intr Code Gnrn
24/38
Switch Statements
There is a selector expression which needsThere is a selector expression which needsto be evaluated followed by a set of valuesto be evaluated followed by a set of valuesthat it can take.that it can take.
The expression is evaluated andThe expression is evaluated anddepending on the value generateddepending on the value generatedparticular set of statements are executedparticular set of statements are executed
There is always a set of default statementsThere is always a set of default statements
which is executed if no other valuewhich is executed if no other valuematches the expressionmatches the expression
-
8/9/2019 Intr Code Gnrn
25/38
INCREMENTAL TRANSLATIONINCREMENTAL TRANSLATION
Code attributes are usually long strings andCode attributes are usually long strings andhence are generated incrementallyhence are generated incrementally
Consider:Consider:productionproduction :: E -> E1 + E2E -> E1 + E2
semantic rulesemantic rule :: {E.addr=new temp(){E.addr=new temp()gen(E.addr = E1.addr +gen(E.addr = E1.addr +
E2.addr)}E2.addr)} Here,Here,
gen()gen() creates add instruction and appends it tocreates add instruction and appends it topreviously generated instructions that computepreviously generated instructions that computeE1E1 intointo E1.addrE1.addr andand E2E2 intointo E2.addrE2.addr
-
8/9/2019 Intr Code Gnrn
26/38
ARRAY REFERRENCESARRAY REFERRENCES
Usually array elements are numbered from 0Usually array elements are numbered from 0to n-1to n-1 If width of each element isIf width of each element is ww and base is theand base is the
relative address of the allocated storage,relative address of the allocated storage,ithith element begins @ locn.element begins @ locn.
base + i*wbase + i*w InInttdimensions address ofdimensions address ofa[ia[i11][i][i22].[i].[itt]] isis
base + ibase + i11*w*w11+ i+ i22 * w* w22 + + i+ + itt * w* wttwherewhere wwjj is the width inis the width injthjth dimensiondimension
THIS IS IMPLEMENTED BY A CORRESPONDINGTHIS IS IMPLEMENTED BY A CORRESPONDINGPRODUCTION/SEMANTICSPRODUCTION/SEMANTICS
-
8/9/2019 Intr Code Gnrn
27/38
TYPE CHECKINGTYPE CHECKING
TO CATCH TYPE MISMATCHESTO CATCH TYPE MISMATCHES
RULE:RULE: IF f HAS TYPE sIF f HAS TYPE st AND x HAS TYPE s THENt AND x HAS TYPE s THEN
EXPRESSION f(x) HAS TYPE tEXPRESSION f(x) HAS TYPE t
-
8/9/2019 Intr Code Gnrn
28/38
TYPE CONVERSIONSTYPE CONVERSIONS THERE IS A HIERARCHY IN TYPE CONVERSIONSTHERE IS A HIERARCHY IN TYPE CONVERSIONS
Different types have different machine representations andDifferent types have different machine representations andmachine instructions. Hence they need to be converted into onemachine instructions. Hence they need to be converted into onecommon type before the actual operationJava has Twotypes ofcommon type before the actual operationJava has Twotypes ofconversions:conversions:
double
float
long
int
short
byte
char
double
float
long
int
shortchar byte
1.Wideningconversions
2.Narrowingconversions
-
8/9/2019 Intr Code Gnrn
29/38
TYPE CONVERSIONTYPE CONVERSIONCONTDCONTD
Consider the production:Consider the production: E -> E1 + E2E -> E1 + E2 Its semantic can be explained with the 2 functions:Its semantic can be explained with the 2 functions: max(t1,t2)max(t1,t2) : takes 2 types: takes 2 types t1t1 andand t2t2 and returns maximum of the two in theand returns maximum of the two in the
widening hierarchywidening hierarchy widen(a,t,w)widen(a,t,w) : performs type conversion by widening address: performs type conversion by widening address aa of type t intoof type t into
a value of typea value of type wwpseudocode:pseudocode:
widen(addr a, type t, type w)widen(addr a, type t, type w){{ ifif(t=w) return a;(t=w) return a;
else ifelse if(t=int and w=float)(t=int and w=float){ temp=new Temp();{ temp=new Temp();
gen(temp = (float) a);gen(temp = (float) a);return temp;return temp;
}} elseelse error;error;
}}here,here, aa is returned ifis returned ifaa andand ww are of same typeare of same typeelse, conversion is done in a temporary that is returnedelse, conversion is done in a temporary that is returned
-
8/9/2019 Intr Code Gnrn
30/38
Flow of control statements
Consider the following statements:S->if (b) s1
where s represents statements and b represents booleanexpressions.
The translation of this
statement consists ofb.code followed bys1.code as shown.Based on the values ofb, there are jumps
within b.code.Similar are the other flow control statements
to b.true
to b.falseb.code
S1.codeb.true:
. . . . . . . .b.false:
If block
-
8/9/2019 Intr Code Gnrn
31/38
Sdd for some control statementsSdd for some control statements
production Semantic rulesP S S.Next = newlabel()
P.Code = S.code || label(S.next)
S->assign S.code= assign.codeS->if(b) s1 b.true= vewlabel()
b.false=s1.next=s.nexts.code=b.code||label(b.true) ||s1.code
S->if(b)s1 else s2 b.true=nwelabel()b.false=nwelabel()S1.next=s2.next=s.nexts.code=b.code || label(b.true)|| s1.code
||gen(goto s.next) || label(b.false)|| s2.code
-
8/9/2019 Intr Code Gnrn
32/38
Sdd for some control statementsSdd for some control statementscontdcontd
production Semantic rules
S->while(b) s1 begin=newlabel()b.true=newlabel()b.false=s.next
s1.next=begins.code=label(begin) || b.code|| label(b.true)||s1.code|| gen(goto begin)
S->s1 s2 S1.next=newlabel()S2.next=s.nexts.code=s1.code || label(s1.next) || s2.code
-
8/9/2019 Intr Code Gnrn
33/38
BACKPATCHINGBACKPATCHING
while generating code for boolean expressions and flow-of-controlwhile generating code for boolean expressions and flow-of-controlstatements,a list of jumps are passed as synthesized attributesstatements,a list of jumps are passed as synthesized attributes
when jump is generated, the target is temporarily not specifiedwhen jump is generated, the target is temporarily not specified it is added to a list of jumps without a definite targetit is added to a list of jumps without a definite target
but, all these jumps have the same targetbut, all these jumps have the same target when the proper label is determined, it is assigned to all the jumpswhen the proper label is determined, it is assigned to all the jumps
in the listin the list
-
8/9/2019 Intr Code Gnrn
34/38
Switch Statements
There is a selector expression which needsThere is a selector expression which needsto be evaluated followed by a set of valuesto be evaluated followed by a set of values
that it can take.that it can take.
The expression is evaluated andThe expression is evaluated anddepending on the value generateddepending on the value generatedparticular set of statements are executedparticular set of statements are executed
There is always a set of default statementsThere is always a set of default statementswhich is executed if no other valuewhich is executed if no other valuematches the expressionmatches the expression
-
8/9/2019 Intr Code Gnrn
35/38
Translation of a switch statementTranslation of a switch statement
Code to evaluate E into tCode to evaluate E into tgoto testgoto testL1: code for S1L1: code for S1
goto nextgoto next
L2: code for S2L2: code for S2
goto nextgoto next..
Ln: code for SnLn: code for Sngoto nextgoto next
test: if t=V1 goto L1test: if t=V1 goto L1if t=V2 goto L2 if t=V2 goto L2 goto Lngoto Ln
next:next:
-
8/9/2019 Intr Code Gnrn
36/38
Translation of switch-statement
If the number of cases is small say 10 thenwe use a sequence of conditional jumps
If the number of values exceeds 10 it ismore efficient to construct a hash table forthe values with labels of the various
statements as entries.
-
8/9/2019 Intr Code Gnrn
37/38
Intermediate code procedures
In three address code a function call isunraveled into the evaluation of parameters inpreparation of a call followed by the call itself.the statement: n=f(a[i]); is translated to:
1) t1=i * 42) t2=a[t1]3) param t2 /* makes t2 an actual parameter */4) t3=call f,15) n=t3
-
8/9/2019 Intr Code Gnrn
38/38