Optimization

SSA (Static Single Assignment)

In many optimizations we need to disambiguate between names. The SSA form is a way to express IR so it becomes easy to optimize. In SSA every variable is assigned only once. Static refers to the textual representation of the IR.

@main() {
  a: int = const 3;
  b: int = const 7;
  a: int = add a b;
  b: int = add a b;
  print b;
}

@main {
  a.0: int = const 3;
  b.0: int = const 7;
  a.1: int = add a.0 b.0;
  b.1: int = add a.1 b.0;
  print b.1;
}

In places where control flow joins, "phony" phi functions are inserted.

@main(cond: bool) {
.entry:
  a: int = const 47;
  br cond .left .right;
.left:
  a: int = add a a;
  jmp .exit;
.right:
  a: int = mul a a;
  jmp .exit;
.exit:
  print a;
}



@main(cond: bool) {
.entry:
  a.0: int = const 47;
  br cond .left .right;
.left:
  a.2: int = add a.0 a.0;
  jmp .exit;
.right:
  a.3: int = mul a.0 a.0;
  jmp .exit;
.exit:
  a.1: int = phi a.2 a.3 .left .right;
  print a.1;
  ret;
}

Both Swift IR (SIL) and LLVM IR use SSA.

Building SSA

Key concept for building SSA is dominance frontier.

Links