I understand how both forward and backward data-flow analysis work but in what situations would we use them? Why do we need to be able to do it in both ways? Do compilers of certain types perform one way more efficiently than the other?


You can do different analysis with forward and backward flow algorithms:

Forward-analysis can provide information about some code to "future" code -- along the normal path of execution. A good example is constant propagation where you provide the value of variables to code further down the line.

Backward-analysis can provide information about some future properties "back in time". A good example is dead code elimination where you can remove assignments to variables if they will never be read in the future.

Real compilers like gcc or llvm perform both kind of analysis and there are even optimizations that require both kind of analysis simultaneously:

Partial redundancy elimination is one of those forward- and backward-analysis requiring algorithms: It tries to move code to the latest-necesary, earliest-possible place.


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.