Showing posts with label data flow analysis. Show all posts
Showing posts with label data flow analysis. Show all posts

Monday, March 1, 2010

Terminology: "Forward" and "Backward" analyses

I got to thinking about terminology after today's lecture, and I think I see how terminology for "forward" and "backward" analysis can be confusing.  When we "look forward" to see what will happen further ahead in execution, that's actually a "backward" flow analysis ... because the information flows backward (we are looking forward, but bringing the information back to here).  It also indicates the way an iterative data flow analysis algorithm orders the nodes it visits.  In a backward flow analysis, it is most efficient to iterate from last to first, again because that's the direction the information is moving.  In a work-list algorithm, if values at node N change, it is the predecessors of N that need to be added to the work list.

Bottom line: the term comes from which way the information is moving, which is reverse of the direction we are looking for it.  So if a flow equation takes in information from the successors of a node, it is a backward analysis, and if it takes in information from the predecessors of a node, it is a forward analysis. 

Wednesday, February 24, 2010

Data flow analysis intro slides

Here are the slides I used today, with a couple of corrections to the mistakes you caught.  (There might be more mistakes ... please let me know if you spot one.)