Re: loop optimization implementation question

[law at redhat dot com]

In message <7143AE4A-7E86-11D8-A3C2-000393BB90B6@apple.com>, Caroline Tice writ
es:
 > At first I thought about doing it in the tree-ssa optimizations, but this 
 >optimization isn't really a good tree-ssa optimization because it changes
 > the shape of the cfg (all the loop blocks and split/join edges are removed,
 >and replace with a single straight-line flow block containing a 
 >function call), which means adding a fair amount of complexity to fix up all
 > the phi-nodes and ssa variables.
Well, there's a brute force approach that would make this easy in the sense
that it doesn't require a lot of work from you.

Specifically, you note every variable which is set within the loop, take
those variables out of SSA form, update the CFG and whatnot, then put them
back into SSA form.  This is effectively what we do when we thread through
conditional branches in blocks which start with PHI nodes or NOP statements.

[ This is relatively heavyweight right now.  I'm still trying to mentally
  work through how to reduce the cost of this kind of operation.  ]


The LNO code might give you a significant amount of infrastructure to identify
the loops you care about and also help with the updating of the CFG and
SSA graph.  They have a lot of similar issues they have to address.

 > My real question is: should this optimization happen before the tree
 >gets genericized?  After generic but before gimple?  After gimple but 
 >before ssa? Or in ssa?
Well, I'd certainly prefer to _not_ have it as a one-off pass which 
optimizes trees, but instead it should use things like the CFG to
identify loops.  So it would seem to me that the earliest location should
be after we've built a CFG, but before we've put the function into SSA form.

But again, there may be things in LNO which make your analysis phase 
significantly easier.  Which would argue that it ought to be part of a
tree-ssa loop optimization pass.
jeff