Subject: Re: Question: Project Part 2
From: Sorin Lerner (lerns@cs.washington.edu)
Date: Fri Jan 26 2001 - 00:43:02 PST
Sorry guys, wrong mailing list. This was meant for cse501.
Sorin
On Fri, 26 Jan 2001, Sorin Lerner wrote:
>
>
> > 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:43:06 PST