7 Intermediate Representation Between the source code and the target code. Simpler than the source code, more complex than the target code Boundary between the front-end and the back-end，convenient for porting to new platforms Possible to design optimizer for IR Parser Static checker IR generator IR Token Code generator 1/34

Return value and parameters Code Static Ex: compiling phases    procedure sort var a: array[0..9] of integer; x:integer; Begin x:= a[3]; End; Lexical Syntactic Token stream Syntax tree Type checking IR generation Construct/ query symbol table Return value and parameters Control link Access link & status 5 a[0] a[1] a[2] … a[9] 15 x 运行栈 sort Query the symbol table, whether a variable is declared Null Head “a” Array 5 “x” Integer 15 Symbol table for sort ↑15= ↑8+3

Ex: After compilation, before execution 。。。。 ↑15= ↑8+3 There’s only executable code, no symbol table or run-time stack 。。。。 Executable code

Return value and parameters Ex: Run-time 。。。。 Execution sequence ↑15= ↑8+3 load 。。。。 Code Static Executable code    Return value and parameters Control link Access link and status 5 a[0] a[1] a[2] … a[9] 15 x Run-time stack

7 Intermediate Representation Topics Introduce several common IR design: postfix representation, graph representation, and three address code Use syntax directed definition and translation scheme to explain how the structures of programming languages are translated to IRs 5/34

7.1 Intermediate language Postfix Graph Three address 7.1.1 Postfix Representation Postfix representation of expression E could be defined recursively: If E is constant or variable, E's postfix representation is E If E is an expression E1 op E2, E’s postfix representation is E1 E2 op, where E1 and E2 are the postfix representations of E1 and E2, respectively If E is represented by (E1), then the postfix representation of E1 is E’s postfix representation Brackets are not necessary (8  4) + 2 => 8 4 2 +

7.1 Intermediate language 后缀表示 图形表示 三地址代码 7.1.1 Postfix Representation Convenient for computer processing (8  4) + 2 => 8 4 2 + 返回值和参数 控制链 访问链和机器状态 局部数据临时数据    top_sp base_sp 栈 运行时！注意区分运行与编译的区别。 8

7.1 Intermediate language 后缀表示 图形表示 三地址代码 7.1.1 Postfix Representation Convenient for computer processing (8  4) + 2 => 8 4 2 + 返回值和参数 控制链 访问链和机器状态 局部数据临时数据    top_sp base_sp 栈 8 4

7.1 Intermediate language 后缀表示 图形表示 三地址代码 7.1.1 Postfix Representation Convenient for computer processing (8  4) + 2 => 8 4 2 + 返回值和参数 控制链 访问链和机器状态 局部数据临时数据    top_sp base_sp 栈 84- 即 8-4=4 8 4 4

7.1 Intermediate language 后缀表示 图形表示 三地址代码 7.1.1 Postfix Representation Convenient for computer processing (8  4) + 2 => 8 4 2 + 返回值和参数 控制链 访问链和机器状态 局部数据临时数据    top_sp base_sp 栈 4 10/34 2

7.1 Intermediate language 后缀表示 图形表示 三地址代码 7.1.1 Postfix Representation Convenient for computer processing (8  4) + 2 => 8 4 2 + 返回值和参数 控制链 访问链和机器状态 局部数据临时数据    top_sp base_sp 栈 84-2+ 即 8-4+2=6 4 6 2

7.1 Intermediate language 后缀表示 图形表示 三地址代码 7.1.2 Graph Representation Syntax Tree assign a +  b c d uminus (a) Syntax Tree a := (b + cd ) + cd’s graph representation

7.1 Intermediate language 后缀表示 图形表示 三地址代码 7.1.2 Graph Representation Syntax tree is a graph representation Directed Acyclic Graph (DAG) is as well assign a +  b c d uminus (a) Syntax Tree (b) dag a := (b + cd ) + cd’s graph representation

7.1 Intermediate language 后缀表示 图形表示 三地址代码 Syntax directed definition to generate declaration statement’s syntax tree Production Semantic Rules S  id :=E S.nptr := mknode(‘assign’, mkleaf (id, id.entry), E.nptr) E  E1 +E2 E.nptr := mknode( ‘+’, E1.nptr, E2.nptr) E  E1 E2 E.nptr := mknode( ‘’, E1.nptr, E2.nptr) E  E1 E.nptr := mkunode( ‘uminus’, E1.nptr) E  (E1) E.nptr := E1.nptr F  id E.nptr := mkleaf (id, id.entry)

7.1 Intermediate language 后缀表示 图形表示 三地址代码 7.1.3 Three address code General form：x := y op z Translate x + y  z into three address code: t1 := y  z t2 := x + t1 Ret and params Local and temp    Control link Access link and status stack Temporary variable After the local variables in the activation records 15/34

7.1 Intermediate language 后缀表示 图形表示 三地址代码 Three address Code is a linear representation of syntax tree or dag a := (b + cd ) + cd Syntax tree’s code dag’s code t1 := b t1 := b t2 := c  d t2 := c  d t3 := t1 + t2 t3 := t1 + t2 t4 := c  d t4 := t3 + t2 t5 := t3 + t4 a := t4 a := t5 assign a +  b c d uminus (a) Syntax tree assign a +  b c d uminus (b) dag

7.1 Intermediate language Examples of three address code Declaration x := y op z, x := op y, x := y Goto goto L If if x relop y goto L Procedural call param x call p , n Return return y Access via index x := y[i] x[i] := y Assign with address x := &y，x := y x := y

7.2 Declaration Statements Generate symbol table entry for local names Assign storage units The symbol table contains the information of the type and the address of the storage units

7.2 Declaration Statements 7.2.1 Declaration inside procedures Compute the type and address of the declared names P  {offset := 0} D S D  D ; D D  id : T {enter ( id.name, T.type, offset); offset := offset + T.width } T  integer {T.type := integer; T.width := 4 } T real {T.type := real; T.width := 8 } T array [ num ] of T1 {T.type := array (num.val, T1.type); T.width := num.val  T1.width} T T1 {T.type := pointer (T1.type); T.width := 4 }

7.2 Declaration Statements 7.2.2 Storage of the scope information If procedural declaration could be recursive, the processing of the declaration statements is different: P  D S D  D ; D | id : T | proc id ; D ; S 20/34

7.2 Declaration Statements 7.2.2 Storage of the scope information program sort(input,output) var a:array[0..10] of integer; x:integer; prcedure readarray; var i:integer; begin …a … end{readarray}; procedure exchange(i,j:integer); begin x:=a[i]; a[i]:=a[j];a[j]:=x;end{exchange}; procedure quicksort(m,n:integer) var k,v:integer; function partition(y,z:integer):integer; begin …a… …v… …exchange(i,j)… end{partition}; begin…end{quicksort}; begin … end{sort}.

7.2 Declaration Statements program sort(input,output) var a:array[0..10] of integer; x:integer; “a”, type info，address in the frame sort Null Head a x readarray exchange quicksort Symbol table of sort

7.2 Declaration Statements program sort(input,output) var a:array[0..10] of integer; x:integer; prcedure readarray; var i:integer; begin …a … end{readarray}; exchange readarray x a Head Null sort quicksort readarrary i

7.2 Declaration Statements program sort(input,output) …… prcedure readarray;…. procedure exchange(i,j:integer); begin x:=a[i]; a[i]:=a[j];a[j]:=x; end{exchange}; sort Null Head a x readarray Point to readarray exchange Point to exchange quicksort readarrary exchange Head Head i

7.2 Declaration Statements program sort(input,output) var a:array[0..10] of integer; x:integer; prcedure readarray; procedure exchange(i,j:integer); procedure quicksort(m,n:integer) var k,v:integer; sort Null Head a x readarray To readarray exchange To exchange quicksort readarrary quicksort exchange Head Head Head i k v partition 25/34 partition

7.2 Declaration Statements exchange readarray x a Head Null sort quicksort To readarray partition v k readarrary i To exchange program sort(input,output) prcedure readarray; procedure exchange(i,j:integer); procedure quicksort(m,n:integer) function partition(…. var k,v:integer; begin …a… …v… … end{partition};

7.2 Declaration Statements 7.2.2 Storage of the scope information The grammar P  D S D  D ; D | id : T | proc id ; D ; S Functions in the semantic rules mktable(previous) enter(table, name, type, offset) addwidth(table, width) enterproc(table, name, newtable) exchange readarray x a Head Null sort quicksort readarrary i enterproc(↑sort,readarray,↑readarray) mktable(↑sort) enter(table, name, type, offset)

7.2 Declaration Statements P  M D S {addwidth (top (tblptr), top (offset) ); pop(tblptr); pop (offset) } M   {t := mktable (nil); push(t, tblprt); push (0, offset) } D  D1 ; D2 D  proc id ; N D1; S {t := top(tblptr); addwidth(t, top(offset) ); pop(tblptr); pop(offset); enterproc(top(tblptr), id.name, t) } Did : T {enter(top(tblptr), id.name, T.type, top(offset)); top(offset) := top(offset) + T.width } N   {t := mktable(top(tblptr) ); push(t, tblptr); push(0, offset) }

7.3 Assignment Statements 7.3.1 Names in the symbol table S  id := E {p := lookup(id.name); if p  nil then emit ( p, ‘:=’, E.place) else error } E  E1 + E2 {E.place := newtemp; emit (E.place, ‘:=’, E1.place, ‘+’, E2.place) } Generate a new temporary name, put the name into the symbol table, and return the address of the entry Output the three address code, similar to printf

7.3 Assignment Statements 7.3.1 Names in the symbol table (cont) E  E1 {E.place := newtemp; emit (E.place, ‘:=’, ‘uminus’, E1.place) } E  (E1) {E.place := E1.place } E  id {p := lookup(id.name); if p  nil then E.place := p else error } 30/34

7.3 Assignment Statements 7.3.2 Reuse of temporary names Suitable for optimization Expansion of the symbol table Larger activation record

7.3 Assignment Statements 7.3.2 Reuse of temporary names Suitable for optimization Expansion of the symbol table Larger activation record E  E1 + E2 generate code like Calculate E1 as t1 Calculate E2 as t2 t3 := t1 + t2 ( ( ) ) ( ( ( ) ( ) ) ( ) ) The lifespan of temporary variables is similar as matched brackets

7.3 Assignment Statements Number of temp names x := a  b + c  d  e  f Statement C value $0 := a  b 1 $1 := c  d 2 $0 := $0 + $1 $1 := e  f $0 := $0  $1 x := $0

Exercise 7.1 34/34