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) #0 {
  %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
  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?

Why IR?

Why IR?

Why IR?

Why IR?

• front ends and back ends to support language-machine pairs.

Why IR?

• front ends and back ends to support language-machine pairs.
• Direct translation from AST to a target program is not easy.
  • You should consider both high-level/low-level issues.
• It is typically easier to perform optimization with IR than with AST.

Three-Address Code

%8 = add %6, %7

br i1 %cond, label %IfEqual, label %IfUnequal

ret 1

• Each instruction uses addresses where .
• Close to machine instructions
• E.g., LLVM IR

Java Bytecode

         0: iload_0
         1: iload_1
         2: iadd
         3: istore_2
         4: iload_2
         5: ireturn

• Language for a stack-based virtual machine.
• More abstract than the three-address code.

How to Generate 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

Various Representations of a Program

• Source code
• Parse tree
• AST 1, AST 2, ...
• IR 1, IR 2, ...
• Target code