2
$\begingroup$

We collect most of the information about possible compiler optimizations during forward pass. Is it possible to utilize the information collected in forward pass in a backward pass so as to perform better optimizations ?

Note: I have been going through the patent Compiler with cache utilization optimizations by Roch G. Archambault et al. (2004) and was wondering what kind of information might have been utilized in their backward pass.

$\endgroup$
2
$\begingroup$

Many major compiler optimizations use backward passes. For example, computing liveness information, which is used to do dead code elimination, usually requires a backwards pass over the CFG of a program in order to identify unnecessary statements. Partial redundancy elimination, a powerful algorithm for eliminating redundant computation or rearranging code, consists of two forward passes combined with two backward passes to determine what expressions are available (forward), what expressions are anticipated (backward), etc.

Hope this helps!

$\endgroup$
  • $\begingroup$ Can you share some (good) references for the things you mention, please? (Or are they standard?) $\endgroup$ – Raphael Sep 6 '12 at 21:50
  • 1
    $\begingroup$ These are pretty standard algorithms. They're covered in depth in the Purple Dragon Book, Chapter 9. $\endgroup$ – templatetypedef Sep 6 '12 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.