CSE411: Introduction to Compilers

Intermediate Representation

Jooyong Yi (UNIST)

Where are we?

                 |-----------|        |----------|
Source Program → | Front End | → IR → | Back End | → Target Program
                 |-----------|        |----------|
                                  ↑

         |-------|            |--------|           |----------|        |-----------|
Source → | Lexer | → tokens → | Parser | → parse → | Semantic |→ AST → |   IR      | → IR
Program  |       |            |        |   tree    | Analyzer |        | Generator |
         |-------|            |--------|           |----------|        |-----------|

• IR: Intermediate Representation (or Intermediate Code)

Example of IR

• LLVM IR

int sum(int x, int y) { int z = x + y; return z; }

define i32 @sum(i32 noundef %0, i32 noundef %1) { ; noundef: no undefined value
  %3 = alloca i32, align 4 ; allocate the memory on the current call stack
  %4 = alloca i32, align 4
  %5 = alloca i32, align 4
  store i32 %0, ptr %3, align 4
  store i32 %1, ptr %4, align 4
  %6 = load i32, ptr %3, align 4
  %7 = load i32, ptr %4, align 4
  %8 = add nsw i32 %6, %7 ; nsw: no signed wrap
  store i32 %8, ptr %5, align 4
  %9 = load i32, ptr %5, align 4
  ret i32 %9
}

Another Example of IR

• Java Bytecode

static int sum(int x, int y) { int z = x + y; return z; }

  static int sum(int, int);
    descriptor: (II)I
    flags: (0x0008) ACC_STATIC
    Code:
      stack=2, locals=3, args_size=2
         0: iload_0
         1: iload_1
         2: iadd
         3: istore_2
         4: iload_2
         5: ireturn
      LineNumberTable:
        line 3: 0
        line 4: 4

Why IR?

• Why not directly translate AST to the target program?

         |-------|            |--------|           |----------|        |-----------|
Source → | Lexer | → tokens → | Parser | → parse → | Semantic |→ AST → |   Code    | → Target
Program  |       |            |        |   tree    | Analyzer |        | Generator |   Program
         |-------|            |--------|           |----------|        |-----------|

Why IR? Portability

Why IR? Portability and Maintenance

Why IR? Portability and Maintenance

Why IR? Portability and Maintenance

Why IR? Portability and Maintenance

Why IR? Reusability and Maintenance

• Code optimization routines developed for bytecode can be reused for different languages.

Why IR? Separation of Concerns

• When translating AST to target code, you should consider both language semantics and machine specifics.

Why IR? Separation of Concerns

• How many variables can you declare in a function?
• How many registers can you use in a machine?

Which IR Format?

Which IR Format? AST

                 |-----------|         |----------|
Source Program → | Front End | → AST → | Back End | → Target Program
                 |-----------|         |----------|

• Portability
• Separation of concerns

Which IR Format? AST

                                            E                                       BinExp(+) 
                                        /   |   \                                  /         \
3 - 2 + 1  == syntax check ==>         E    +   T     == abstraction ==>      BinExp(-)      Int(1)
                                     / | \      |                               /   \
                                    E  -  T    int                          Int(3)  Int(2)
                                    |     |
                                    T    int
                                    |
                                   int

• S-expression: (BinExp + (BinExp - (Int 3) (Int 2)) (Int 1))

Which IR Format? AST

1: a = 0;                                                      StmtSeq
2: while (a < N) {                                          /          \
3:  b = a + 1;                                         AssignStmt       WhileStmt
4:  c = c + b;                                         /     \         /         \
5:  a = b * 2;                                       Id(a)  Int(0)   BinExp(<)     StmtSeq
6: }                                                                   /    \        / | \
7: return c;                                                         Id(a)  Id(N)   

• At each line, which variables are live?

Which IR Format? Control Flow Graph

1: a = 0;                                                       a = 0
2: while (a < N) {                                                |
3:  b = a + 1;                                           ----   a < N  <-------
4:  c = c + b;                                           |        |           |
5:  a = b * 2;                                           |      b = a + 1     |
6: }                                                     |        |           |
7: return c;                                             |      c = c + b     |
                                                         |        |           |
                                                         |      a = b * 2     |
                                                         ↓        |___________|
                                                      return c

Which IR Format? Linear IR

1: a = 0;                                                       a = 0
2: while (a < N) {                                                |
3:  b = a + 1;                                           ----   a < N  <-------
4:  c = c + b;                                           |        |           |
5:  a = b * 2;                                           |      b = a + 1     |
6: }                                                     |        |           |
7: return c;                                             |      c = c + b     |
                                                         |        |           |
                                                         |      a = b * 2     |
                                                         ↓        |___________|
                                                      return c                                                       

entry:
  %a = alloca i32, align 4
  %b = alloca i32, align 4
  %c = alloca i32, align 4
  store i32 0, i32* %a, align 4
  br label %loop.cond

loop.cond:  
  %a_val = load i32, ptr %a, align 4
  %cmp = icmp slt i32 %a_val, %N ; slt: signed less than
  br i1 %cmp, label %loop.body, label %loop.exit

loop.body:
  ...
loop.exit:                                                                                                 
  ...

Java Bytecode

a = 0;                   0: iconst_0
while (a < N) {          1: istore_2
  b = a + 1;             2: iconst_0
  c = c + b;             3: istore_3
  a = b * 2;             4: iconst_0
}                        5: istore        4
return c;                7: iload_2
                         8: iload_1
                         9: if_icmpge     29
                         12: iload_2
                         13: iconst_1
                         14: iadd
                         15: istore_3
                         16: iload         4
                         18: iload_3
                         19: iadd
                         20: istore        4
                         22: iload_3
                         23: iconst_2
                         24: imul
                         25: istore_2
                         26: goto          7
                         29: iload         4
                         31: ireturn                                                                                                  

• Language for a stack-based virtual machine.
• More abstract than linear IR.

How to Generate IR?

static void foo() {
    int x;
    x = 1;
}

    ICONST_1
    ISTORE 0
    RETURN

How to Generate IR?

static void foo() { int x; x = 1; }

    ICONST_1
    ISTORE 0
    RETURN