Sequence 4.1 – Intermediate Representation

Going beyond the AST

The abstract syntactic tree (AST) is a tree representation of the source, strongly tied to the source language.

In order to advance the compilation process, we need to go beyond the AST and approach the machine representation. For this, we use a language independent intermediate representation (IR).

Intermediate Representation

Design Choices

Lowering and Three Address Code

Lowering: transforming a high-level representation (AST) into IR

y := 4*x*x - 2*x + 1

becomes

x1 := x * x;
x2 := 4 * x1;
x3 := 2 * x;
x4 := x2 - x3;
y := x4 + 1;

Multiple IR?

In some compilers multiple IR levels are used.

GCC

Original Program

int f(int x) {
  int y = 0;
  if (x>0)
    y = 4*x*x + 1;
  return y;
}

GIMPLE

[...]
  if (x > 0) goto <D.4106>; else goto <D.4107>;
  <D.4106>:
  _1 = x * 4;
  _2 = x * _1;
  y = _2 + 1;
  <D.4107>:
  D.4108 = y;
  goto <D.4109>;
  <D.4109>:
  return D.4108;
}

RTL

[...]
(note 9 8 10 4 [bb 4] NOTE_INSN_BASIC_BLOCK)
(insn 10 9 11 4 (set (reg:SI 114)
  (ashift:SI (reg/v:SI 113 [ x ])
   (const_int 2 [0x2]))) "ex1.c":4 -1
  (nil))
(insn 11 10 12 4 (set (reg:SI 115)
  (mult:SI (reg/v:SI 113 [ x ])
   (reg:SI 114))) "ex1.c":4 -1
  (nil))
(insn 12 11 21 4 (set (reg/v:SI 112 [ <retval> ])
  (plus:SI (reg:SI 115)
   (const_int 1 [0x1]))) "ex1.c":4 -1
  (nil))
(jump_insn 21 12 22 4 (set (pc)
  (label_ref:SI 17)) 214 {*arm_jump}
  (nil)
 -> 17)
(barrier 22 21 24)
(code_label 24 22 23 5 3 (nil) [1 uses])
(note 23 24 4 5 [bb 5] NOTE_INSN_BASIC_BLOCK)
(insn 4 23 17 5 (set (reg/v:SI 112 [ <retval> ])
  (const_int 0 [0])) "ex1.c":2 -1
  (nil))
(code_label 17 4 20 7 1 (nil) [1 uses])
(note 20 17 18 7 [bb 7] NOTE_INSN_BASIC_BLOCK)
(insn 18 20 19 7 (set (reg/i:SI 0 r0)
  (reg/v:SI 112 [ <retval> ])) "ex1.c":6 -1
  (nil))
(insn 19 18 0 7 (use (reg/i:SI 0 r0)) "ex1.c":6 -1
  (nil))