This is the mail archive of the gcc-bugs@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]

[Bug tree-optimization/21829] [4.1/4.2 Regression] missed jump threading after unroller



------- Comment #6 from law at redhat dot com  2006-03-21 05:09 -------
Subject: Re:  [4.1/4.2 Regression] missed jump
        threading after unroller

On Sat, 2006-02-11 at 00:59 +0000, pinskia at gcc dot gnu dot org wrote:
> 
> ------- Comment #5 from pinskia at gcc dot gnu dot org  2006-02-11 00:59 -------
> The problem with this one after Jeff's recent patches is that we have:
> <L13>:;
>   D.1402_17 = 0;
>   if (D.1402_17 == 1) goto <L15>; else goto <L14>;
> 
> <L15>:;
>   x_18 = 1;
> 
>   # x_19 = PHI <0(2), 0(3), x_18(4)>;
> <L14>:;
> 
> Which causes us not to be able to the jump threading as we do a CCP in VRP and
> then we get:
> <bb 2>:
>   if (v_8 < 0) goto <L13>; else goto <L14>;
> 
> <L13>:;
>   D.1402_17 = 0;
>   goto <bb 8> (<L18>);
> 
>   # x_19 = PHI <0(2)>;
> <L14>:;
>   u_20 = 1;
>   ivtmp.26_21 = 1;
>   ivtmp.26_3 = 1;
>   u_14 = 1;
>   x_13 = 0;
>   if (v_8 <= 0) goto <L1>; else goto <L3>;
> 
> So we need to be able to do some CCP and some DCE before invoking VRP.
As I mentioned earlier, the problem is inherent with non-iterating
dominator optimizations -- namely that we can't guarantee that for
block BB that we will visit all of BB's predecessors before visiting
BB when BB is at a dominance frontier.

The net result is that we may still be propagating values into a PHI
node for a block which has already been visited.  Those propagations
may result in the PHI turning into a degenerate too late for the
dominator optimizer to discover the degenerate PHI and record the
appropriate equivalence for the LHS of the degenerate PHI.

I had added support for a stripped down copy-prop to run after DOM
to pick up these kind of optimization opportunities rooted at degenerate
PHI nodes that were trivial copies.  (previously we had been running
the full-blown copy-prop pass).

However, that code does not catch this case because our PHI looks like

x_2 = PHI (0 (BB1), 0 (BB2))

ie, it's a constant initialization, not a PHI-copy.

I had played with running a similarly stripped down CCP after DOM,
but that's really expensive compile-time wise.

I then experimented with speeding up the propagation engine.  While
I may have found a couple of micro-opts, I wasn't able to find anything
which was going to give us a big enough improvement to make running
a phi-only CCP a viable option from a compile-time standpoint.

I then proceeded to implement a concept that had been floating around
in the back of my mind.  Namely a specialized PHI const/copy optimizer
which used a dominator walk plus a worklist of statements/phis to
revisit after the DOM walk (which allows us to detect secondary
effects).

It turns out this specialized PHI optimization pass is as effective
as running copy-prop and CCP on PHI nodes after DOM.  Better yet, it
is a teeny tiny slowdown compared to just running the stripped down
copyprop.  ie, for an almost unmeasurable slowdown we can do both
constant and copy propagation instead of just copy propagation.

Net result is in this PR we're able to clean up the extraneous
modulo operation and propagate its result as well.

Note that the resulting code could be simplified even more, namely
iterating VRP could allow simplification of a relational into an
equality test.  That's simply not going to happen.  We'll have to
live with less than 100% optimized code.

Bootstrapped and regression tested on i686-pc-linux-gnu.


------- Comment #7 from law at redhat dot com  2006-03-21 05:09 -------
Created an attachment (id=11077)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=11077&action=view)


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21829


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