ICS 142 Klefstad

Intermediate Code Generation

Outline Introduction Intermediate languages Types of three address statements Implementing three address statements A representation for expression trees Assignment statements Indexing Record fields Boolean expressions Flow of control statements

Introduction

programs can be translated directly to target code
using an intermediate code allows
- simpler retargeting
- machine-independent code optimization
- can easily be done by parser

Intermediate languages

tree forms
- syntax trees
  - x op y -->
```
  op
x		y
```
- graphs (DAG)
  - like trees except common subexpressions ARE the SAME structure

linear forms
- postfix
  - assumes a stack machine
  - instruction format:
    - x op y -->
      x y op
- three address code
  - uses machine generated temporaries
  - instruction format:
    - x op y -->
      Ti := x op y

Types of three address statements

usually correspond to source language instructions
- binary assignments
  - x := y op z
- unary assignments
  - x := op y
- copy assignments
  - x := y

continued
- jump statement
  - goto L
- conditional jumps
  - if x relop y goto L
- load arguments and call a subroutine
  - load x
  - load y
  - call p, n
- indexed assignment
  - x := y[i]
  - x[i] := y
- address and pointer assignments
  - x := &y
  - x := *y
  - *x := y

Implementing three address statements

representation: quadruples

good for optimization, because instructions may be moved around easily

TYPE quad IS
  RECORD
    op: operator;
    arg1: operand;
    arg2: operand;
    result: operand;
  END RECORD;

Temporary name management
- in general, a new temporary is generated each time make_temp is called
- operations no longer need their operands, so these temporaries may be reused
- behaves like a stack of temporaries

A representation for expression trees

a DAG or a tree

TYPE expr_kind IS (is_identifier, is_constant, is_operator, is_call);
TYPE expr_block(kind: expr_kind);
TYPE expr_tree IS ACCESS expr_block;
TYPE expr_block(kind: expr_kind) IS
  RECORD
    CASE kind IS
      WHEN is_identifier =>
        entry: symbol;
      WHEN is_constant =>
        value: integer;
      WHEN is_operator =>
        op: operator;
        left, right: expr_tree;
      WHEN is_call =>
        subprogram: symbol;
        arguments: expr_tree_list;
    END CASE;
  END RECORD;

Assignment statements

bottom-up propagation of location
fold constants along the way
EG page 479
top-down has some advantages

Indexing

usually have a static part and/or a dynamic part
the address of a[i] can be computed by the formula
- addr(a[i]) = addr(a) + (i - lower_bound(a)) * element_size(a)
static indexing
- add any static index to a variable's activation record offset
dynamic indexing
- add any dynamic index at run-time, usually must be scaled first
a constant index is a static index
- EG a[10]

Record fields

the compiler must keep track of the type of an expression
when an expression yields a record type, we have the type descriptor for the record type which contains the symbol table of fields
record fields are a static index
- look up the field, and add its offset to the variable's offset

Boolean expressions

have two purposes:
- to compute boolean values
  - EG
```
b: boolean := a and not c or i < k;
```
- as a conditional expression for statements
  - EG
```
IF a and not c or i < k THEN
  put(i);
END IF;
```

two methods of evaluating boolean expressions
- like arithmetics with false = 0, and true = 1
- by flow of control
  - value is represented by reaching a position in a program
  - ANDs and ORs may be short-circuited
  - NOTs never add code, just switch true and false locations

Flow of control statements

generate required labels at beginning of construct
these become inherited attributes for the rest of the statement

IF exp THEN
  stmt-list
ELSIF expr THEN
  stmt-list
ELSE
  stmt-list
END IF;

indefinite loop
```
LOOP
  stmt-list
END LOOP;
```
while loop
```
WHILE cond LOOP
  stmt-list
END LOOP;
```

for loop

FOR i IN 1..10 LOOP
  stmt-list
END LOOP;

loop exit
loop continue

case stmt

CASE i IS
  WHEN 1 | 3 | 5 =>
    put("odd");
  WHEN 2 | 4 | 6 =>
    put("even");
  WHEN OTHERS =>
    put("HuH?");
END CASE;

labels and gotos
procedure calls