LARA

Constant Propagation

Detect variables that are constant at a given program point.

Motivation

  int a, b, step, i;
  boolean c;
  a = 0;
  b = a + 10;
  step = -1;
  if (step > 0) {
    i = a;
  } else {
    i = b;
  }
  c = true;
  while (c) {
    print(i);
    i = i + step;    // can emit decrement
    if (step > 0) {
      c = (i < b);
    } else {
      c = (i > a); // can emit better instruction here
      // put here (a = a + step), redo analysis
    }
  }

Constant Propagation Domain

Also special case of interval analysis.

Which intervals do we maintain?

What is the height and the size for

  • lattice itself
  • if we have $p$ program points and $q$ variables?