[tree-ssa Too many edges in CFG

[Daniel Berlin]

On Thu, 8 May 2003 law@redhat.com wrote:

> In message <wvl1xz95su3.fsf@prospero.boston.redhat.com>, Jason Merrill writes:
>  >Sure, but my point is that we should have an abnormal edge there to
>  >properly model the potential flow.  Use of globals is already handled by an
>  >implicit USE, isn't it?  I don't think we need to treat calls specially in
>  >most optimizers if we describe their properties correctly.
> Thus my comment that if we want/need these edges, then they should be
> marked as fake edges since they can never be executed and that any
> code queued for insertion on a fake edge can be ignored.
>
>
>  >Morgan says that some algorithms, including PRE, break down if not all
>  >execution paths lead to the exit block.  I don't know whether that's true
>  >of our implementation, but it seems like a reasonable invariant.
> Correct.  However note that SSAPRE is a very different beast than PRE
> as Morgan describes it.  I'm not familiar enough with SSAPRE to know if
> it requires fake edges to the exit block.
It does not.

You are familiar with SSAPRE because you are familiar with PRE and
SSA. You just don't realize it.
SSAPRE is somewhat misnamed.
It should be called ESSAPRE or something.
It's "Expression SSA form building + Sparse PRE on the Expression SSA
graph + Expression SSA breakdown [ie out of ssa]"

That's all. It just builds an SSA form for expressions, does PRE
on this ESSA, then does unESSA.
It even uses the same types of algorithms for renaming, etc, they are just
modified to work on expressions, rather than variables.

Also, to save time and memory, we only build ESSA/do PRE/unESSA one
lexical expression at a time, and only for lexical expressions with >1 use.

Once you realize it's all about building an Expression SSA form and doing
Sparse PRE on it (in fact, the PRE portion is actually the most trivial
part of the implementations, and almost never the source of bugs. All
bugs usually occur in renaming or out-of-essa [known as code_motion]), it
becomes much easier to understand.




>
>
>
>