[tcb] Merge PHI nodes -- 7.4% reduction of PHI nodes (Take 2)
Kazu Hirata
kazu@cs.umass.edu
Mon Sep 20 23:52:00 GMT 2004
Hi Jeff,
> BB3:
> x1 = PHI (0 (BB0), 1 (BB1))
>
> BB4:
> x2 = PHI (x1 (BB3), x0 (BB2))
> if (x2 == 0)
> goto BB5;
> else
> goto BB6;
Thanks for detailed explanation. By the way, I'd like to point out
that I often see a variant of your example like so:
BB3:
x1 = PHI (0 (BB0), 1 (BB1))
x2 = (_Bool) x1; <- Notice this cast!
BB4:
x2 = PHI (x1 (BB3), x0 (BB2))
if (x2)
goto BB5;
else
goto BB6;
Notice that my PHI merge pass cannot get at this king as the two PHI
nodes are separated by a cast to _Bool, meaning that we miss a jump
threading opportunities.
I've written a small pass to kill the above cast like so
BB3:
x2 = PHI (0 (BB0), 1 (BB1))
BB4:
x2 = PHI (x2 (BB3), x0 (BB2))
if (x2)
goto BB5;
else
goto BB6;
provided that x1 is a single use variable, and that all the arguments
in "x1 = PHI <...>" are constants. By running this pass immediately
before my PHI merge pass, I can remove 7.9% of PHI nodes in GCC's
source code, which is 0.5% more than without this pass.
> Probably the closest thing I've come to a guideline is the threader
> will prefer to have fewer PHIs with larger vectors. if-conversion
> and CSE will tend to want more PHIs with smaller vectors.
By if-convesion, do you mean phiopt? If that's the case, I am
thinking about rewriting phiopt by looking at COND_EXPR, not the PHI
node that two edges comes to. That is, if we have
BB1
if (COND) goto BB3; else goto BB2;
BB2:;
BB3:;
x1 = PHI <1(BB1), 0(BB2), 0(BBx)> <- Notice three arguments!
then we can convert this to:
BB1
x2 = COND;
if (1) goto BB3; else goto BB2;
BB2:;
BB3:;
x1 = PHI <x2(BB1), 0(BB2), 0(BBx)> <- Notice three arguments!
Now that BB2 is unreachable, we get:
BB1
x2 = COND;
BB3:;
x1 = PHI <x2(BB1), 0(BBx)> <- Notice three arguments!
This problem has been filed as PR 14442.
> > And if the pass has negative compile time effects, then I'm definitely
> > not interested ;)
> I'd like to postpone trying to tackle this problem. I don't think
> it's something we want to be spending time on during stage3.
OK. I posted my patch simply because Diego started
tree-cleanup-branch. ;-)
Kazu Hirata
More information about the Gcc-patches
mailing list