Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Chris Lattner <sabre at nondot dot org>]

On Mon, 15 Dec 2003 law@redhat.com wrote:
>  >> Yes, thats why CCP had to trim down its def->use chains to just the
>  >> variables it cared about rather than all of them. It was a large memory
>  >> savings to do that.
>  >
>  >How were you representing the information before?  Why was it taking so
>  >much space?
> I believe the core problem was that the computed jumps resulted in
> insanely large PHIs and an insanely large number of PHIs.  The resulting
> use-def information was correspondingly large.

use-def and def-use information should have the exact same size, or at
worst within a constant factor if each other.  All operations for
manipulating it should also be extremely cheap.  In LLVM, for example,
changing the operand of an instruction to different value automatically
updates the use-def and def-use information for the old used value, the
new used value, and the current instruction, all in constant time (and
without any memory allocations :).

> Given infinite time and resources we might not have started with trees.
> However, starting with trees gave us somewhere to stand while we dealt
> with a lot of other issues and got us to a point where we could actually
> do some interesting things a lot faster.

I understand why tree-ssa chose to base the work on trees, and it is a
good choice.  That said, use-def and def-use information should be cheap
to keep always up-to-date and available for clients, regardless of the
representation.

-Chris

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