title: Compiler optimisation - statement rearrangement algorithms?
body: <p>So I'm interested of any approaches for compilers to rearrange specific statements in order to allow better memory allocation, e.g. register assignment. Thus in some cases it could be possible to evaluate a statement earlier, such that we can reuse the intermediate register. Consider:</p>
  
  <pre><code>input(a1,a2,a3)
  b = f1(a1,a2);
  c = f2(b,a3);
  d = f3(b,a1,a2);
  k = f4(c,1);
  l = f5(d,a3);
  r = k + l + b + c;
  </code></pre>
  
  <p>Here the compiler will use 4 "registers" - 1)b,2)c,3)d and l,4)k and r will be any of the previous.
  Instead this could be more efficient in terms of register allocation if we do something like this:</p>
  
  <pre><code>input(a1,a2,a3)
  b = f1(a1,a2);
  c = f2(b,a3);
  r = b + c + f4(c,1);
  c = f3(b,a1,a2);
  r += f5(c,a3);
  </code></pre>
  
  <p>Where we can use 3 registers.</p>
  
  <p>What I'm looking for is given a compute graph, where I have all the variable dependencies, to generate a better optimised code for registers. The question is is there any algorithmic way of doing this?</p>
  
  <p>PS: Note the example might not be the best, but couldn't think of anything else simple.</p>