Subject: Re: Question: Project Part 2
From: Sorin Lerner (lerns@cs.washington.edu)
Date: Fri Jan 26 2001 - 00:42:02 PST
> Hello - in the description of part 2 of the project, it says that
> our dataflow analysis framework must be applicable for arbitrary graphs.
> It then goes on to say specifically that our analysis must be able to
> run on both (or more) graphs in our IR, presumably a control-flow type
> graph and then a factored def-use chain. This seems reasonable - however,
> "arbitrary" graphs seems to imply that our analysis should work on *any*
> graph. Doesn't the analysis need to be parameterized by the type of graph
> it is dealing with? We are a bit confused ... Any feedback/advice would
> be greatly appreciated!
We never said that your *analysis* should work on *any* graph. Your
*framework* is what needs to accept arbitrary graphs. Essentially, this
means that your framework should be able to apply the worklist algorithm
on any graph (just look at the worklist algorithm -- you'll notice that
the only thing it talks about are nodes, predecessors and successors, or
essentially a graph). For example, your analysis framework might take as
input a graph, a flow function and a lattice. It will then propagate
information (lattice elements) across the edges of the input graph
according to the flow function until a fixed point is reached. Notice how
given this description, your framework does not care anymore what specific
graph it is propagating information through.
Now, each analysis will run on just *one* graph. For example, available
sub-expressions (for CSE) will probably run on the CFG. Constant
propagation will run on the factored def-use graph. However, you'll use
the same analysis *framework* for both of these analyses, because both of
them are simply propagating information over some graph.
Keep in mind that there are things that haven't really been covered in
class yet. Before starting part 2 of the project, you'll need to
understand how dataflow analyses can work on representations such as
factored def-use chains. This will either be covered in class, or you
might have to understand it as an exercise (in which case you should come
to office hours if you're having trouble).
Hope this helps!
Sorin
This archive was generated by hypermail 2b25 : Fri Jan 26 2001 - 00:42:07 PST