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


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


3/38


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


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


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.


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/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


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


10/38


11/38

Using Hash tables & BucketsUsing Hash tables & Buckets

PointerTo list ofnodes(sub-trees)


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


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


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


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


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


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


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.


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)


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);


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:


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}


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 =


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


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


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


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


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


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


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


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


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


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


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


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:


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.


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


38/38

Intr Code Gnrn

Documents

Transcript of Intr Code Gnrn