Re: [tree-ssa] Lazy updating of stmt operands

[Chris Lattner <sabre at nondot dot org>]

On Thu, 11 Dec 2003 law@redhat.com wrote:
>  >Jeff Law wrote:
>  >> While it's nice to think about a world where you always have immediate
>  >> uses, you end up with FUD chains if you do that -- with ultimately a
>  >> tangled nest of pointers that is bloody impossible to work with in the
>  >> real world.
>  >
>  >Uh, no.  Here's a counter-example:
>  > http://llvm.cs.uiuc.edu/
>  >
>  >Having efficient, transparently & efficiently updated immediate use
>  >information is extremely valuable for a wide variety of optimizations.
> OK.  Maybe it was just Diego implementation that was an unmaintainable
> mess :-)

I really can't emphasize enough how important this is.  For example, this
information allows an efficient implementation of the LLVM
Value::replaceAllUsesOf operation (which makes all users of a value use
something else, think replacing 'add 2, 4' with '6').  The presence of
this operation makes copy operations in the IR completely superfluous,
along with "copy-propagation" passes (which either effectively have to be
run between all transformations, or be built into all of them).  This
simplifies transformations, makes code more maintainable, etc...

That said, implementing this efficiently is non-obvious.  It is easy to
implement replaceAllUsesOf in O(M*N) time (where N is number of users of
an operation and M is the average number of operands in the users), but
this is obviously disasterous if you have "users" with a large number of
operands, such as PHI nodes for high-degree basic blocks.

If you're interested in how we do this in LLVM, which is O(N), the code
lives in the User, Use, and Value classes.  Following the User::setOperand
code path will probably illustrate the design, and I'm more than happy to
answer any questions about it.  I believe that O(N) is the most efficient
possible, without using algorithms like union-find.

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/