This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Language-independent functions-as-trees representation


On Mon, 22 Jul 2002, Jason Merrill wrote:

> >>>>> "Mark" == Mark Mitchell <mark@codesourcery.com> writes:
> 
> >>> I was implicitly (sorry!) in SSA form.
> >> 
> >> I remain unenlightened.  Can you give an example of where such sharing
> >> would be useful?
> 
> > You mean, I assume, other than the obvious memory savings.  (In practice,
> > those savings can be rather substantial, and since we are trying to
> > avoid making compile-time any worse than it already is, something that
> > substantially reduces memory use may be worthwhile for that reason if
> > for no other.)
> 
> Yep.
> 
> > Consider that you want to do value-numbering to find places where you
> > compute the same value multiple times.  [snip]
> 
> Sure, any time you need to compare things it's faster if you can use
> pointer comparison.  I was actually hoping for a small testcase, so we
> could talk about the tradeoffs.
> 
> > However, with sharing, you must do work as you build the structure so that
> > you make sure that you really are sharing.  But that is not so hard; you
> > just keep tables of the things built from nodes you already have and check
> > to see if the node you are building uses the same operation to combine
> > the arguments as the one you already have.
> 
> The tricky part, as I mentioned before, is maintaining proper semantics
> when simplifying shared trees, or indeed when making any modifications.
> Sharing makes copying and comparison fast, but makes modification slow.
> Simplification generally involves the recursive replacement of expressions
> with temporary variables.  If the expressions are shared, this will change
> semantics unless you somehow arrange to unshare them on modification, which
> could imply an arbitrary amount of backtracking.

We also have no easy way to determine if they are currently shared, so 
unless this is added, you have to make a pass over all the trees, marking 
them, and seeing if you come across one already marked in the traversal 
(if you do, it's shared).

>  If I have a+b+c+d+e+f+g
> and I want to replace a+b with a temp, I have to make a new copy of the
> whole expression everywhere it appears, or suddenly all instances will use
> the same temp, which is wrong if 'a' changes in the interim.

Which wouldn't be so hard if you knew where the sharing starts, but you 
actually don't, unless we start and update this info.

And if we have to track what's shared, it adds memory overhead, and time 
overhead.
And adds code and maintenance cost.

And if you want to do IPA at some time in the future, having to make a 
pass over every single tree in existence in every file, to determine 
which are shared (unless we are unsharing them before writing them out, 
which runs you into the problem of memory usage/compile time when you 
actually do the compiling of them), is painful.



> 
> Or are you suggesting that we start sharing trees after simplification?


> Given that we only do GC between functions, I don't think that would
> provide any memory savings.
> 
> And I still don't see how this relates to the statement/expression
> distinction.
> 
> Jason
> 
> 


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]