[Solved]: Backward vs Forward Data-flow Analysis

Problem Detail: 

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?

Asked By : Haych

Answered By : lambdapower

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56962

3.2K people like this

 Download Related Notes/Documents