On Mon, Nov 23, 2009 at 10:17 AM, Ian Bolton <bol...@icerasemi.com> wrote: > David Edelsohn wrote: >> On Fri, Nov 20, 2009 at 10:05 AM, Ian Bolton <bol...@icerasemi.com> >> wrote: >> > From some simple experiments (see below), it appears as though GCC >> aims >> > to >> > create a lop-sided tree when there are constants involved (func1 >> below), >> > but a balanced tree when there aren't (func2 below). >> > >> > Our assumption is that GCC likes having constants all near to each >> other >> > to >> > aid with tree-based optimisations, but I'm fairly sure that, when it >> > comes >> > to scheduling, it would be better to have a balanced tree, so sched >> has >> > more >> > choices about what to schedule next? >> >> I think this would depend on the target architecture and instruction >> set: CISC vs RISC, many registers vs few registers, etc. I do not >> believe that GCC intentionally is trying to optimize for either, but I >> do not think there is a single, right answer. >> > Regardless of the architecture, I can't see how an unbalanced tree would > ever be a good thing.
We actually don't *unbalance* it on purpose, but we do rewrite it on purpose to maximize the number of subexpressions that are the same. IE given two sets of calculations (a+5)+(b+7)+(c+8)+(d+9)+(e+10) (a+10)+(b+9)+(c+7)+(b+8)+(a+5) we will attempt to sort and rewrite these into the same tree. It so happens that in doing so, it chooses the most trivial way to do so, which generates an unbalanced trees, in particular, left-linear form. The code i wrote in tree-ssa-reassoc.c was mainly to eliminate some missed subexpression elimination opportunities, it was not meant to be the end-all be all of reassociation. There are much nicer theoretical ways to do tree balancing that still retain equivalent subexpressions, but nobody as of yet has implemented it. It's not even clear that the tree level is where you should be doing this balancing, probably somewhere at the RTL level there should be another real instruction-tree rewriting phase. Patches welcome!
