This is the mail archive of the
mailing list for the GCC project.
Thoughts on TER (was: [PATCH] Fix multiply-add regressions after expand-from-SSA)
- From: Michael Matz <matz at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Cc: Adam Nemet <anemet at caviumnetworks dot com>, Richard Guenther <rguenther at suse dot de>
- Date: Fri, 1 May 2009 23:12:41 +0200 (CEST)
- Subject: Thoughts on TER (was: [PATCH] Fix multiply-add regressions after expand-from-SSA)
- References: <email@example.com> <alpine.LNX.firstname.lastname@example.org> <email@example.com> <Pine.LNX.firstname.lastname@example.org> <email@example.com>
On Thu, 30 Apr 2009, Adam Nemet wrote:
> > That at least followed also my ideas how to implement something
> > similar to TER with expand-from-SSA.
> I see now. To be honest, I just took the code from 'case SSA_NAME:'
> which is probably something that was added now?
> > In an ideal world we would get rid of TER altogether, that's why
> > knowing which cases are currently really helped by it is useful.
> But it seems that the complexity comes from the fact that you either map
> all RTL expanders to tree codes (maybe that's already the case) or you
> would have to be able to look at the expression trees at expansion time
> which is not as easy since we're no longer in SSA.
Sort of, yes. We aren't in SSA form anymore, but not yet in RTL either,
it's something in between, where SSA names exist, but they are related
together in some partitions which themself have RTL expressions (pseudos
or MEMs) assigned. So looking up expression trees does work.
The problem TER tries to solve is that our RTL expander doesn't try to
find a cover of the whole expression trees formed from gimple
instructions, so it can't find an ideal mapping from gimple instructions
to RTL instructions, if one RTL insn has the effect of multiple gimple
insns. TER tries to work around this problem by simply building
expression trees as large as possible and hoping for the best, namely that
expand will do something useful with these large trees; often it doesn't.
Then at the RTL side we also have combine which tries something similar
(pulling multiple RTL insns into one with the combined effect).
So TER partly does something which later would have been done at combine.
As combine has the three instruction limitation TER also does something
more than combine could do. widening multiplication is one case.
But TER also does significantly less due to its restriction of following
only single-use chains. E.g. in the widening mult example TER wouldn't
have helped this case:
short s = ...
int i = (int)s * (int) s;
Optimization would have moved out the common subexpression "(int) s", and
TER wouldn't have put it back in (because that temporary has then two
uses). So expand would have seen just the muliplication of two ints,
where it would have been better if it saw that those were really just
Together, TER does things that can be done by combine, and things that
can't be done by combine. These latter things it does in a restricted
way. And for doing all that TER constructs large trees which most of the
time are simply expanded again into individual instructions by expand,
just undoing the effects of TER instead of expanding to less instructions.
So, one goal for the future would be to learn which transformations that
TER does really help (probably not that many), and then either:
(a) convince ourself that these will be done by other RTL transformations,
(b) implement them in the expanders itself, via looking up use-def
chains explicitely in the (hopefully few) places where it helps.
(c) move over the useful transformation to gimple, so that other
tree optimization passes can benefit from them, not only the RTL
I currently know of two things that are helped by TER:
1) condition chains, when we have something like this in gimple:
cond = A > B;
if (cond != 0) ...
without TER these are expanded to two jumps (and hence additional basic
blocks) hindering RTL transformers somewhat. That's why I put in a
hack for this, with the expectation that this is solved somewhere else
in the future.
2) widening multiplication where it's usefull for expand to know that
some operands are in reality just sign- or zero-extended variants of
short operands. TER helps this case only sometimes (single-use
chains), so it better be implemented somewhere else anyway.
There surely are some more, but I'd hope that they all can be sorted into
only few general themes, so that the decision between a/b/c is easy.