This is the mail archive of the gcc-patches@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: VRP speedup


> Jan Hubicka wrote on 12/06/06 08:19:
> 
> >My overall plan with VRP is after this patch avoid more of the direct
> >folder calls (first they tend to be wrong comparing boolean_true_node
> >and they are mostly convertible to the new comparsion thingy.), rewrite
> >the ranges_intersect_p predicate so it does two comparsions instead of 6
> >
> Sounds good.
> 
> >and then try to reorg the propagation engine to avoid propagating over
> >unchanged PHI edges.
> >
> I don't follow, to do merging on a PHI node, you still need the values
> of the executed edges.  You just don't visit the source more than
> once.  Scheduling big PHI nodes late, will help but you *do* need to
> visit them.

What happens on the testcase is that we have incredibly large PHI node
after incredibly large decision tree.  As we walk the BBs in decision
tree, the individual edges of PHI node becomes live.  Each time edge
becomes live we revisit all edges of PHI node searching for live edges
and merging them to result.  Even the loop testing the liveness bits is
time consuming (ie it is not big deal at all to ^C it in GDB) in the
first part of execution, larter it becomes expensive the loop merging
the intervals into the result that is useless too, since only the
new/changed intervals needs to be revisited. CCP is fast here just
because after first two values merged in, the result is VARYING as we
shortcircuit the walk.

Delaying processing the PHI node helps in this testcase as simply many
edges become reachable before we start walking it.

What I want to have instead is callback "merge this newly executable or
changed PHI operand in" that is executed each time we visit the edge of
SSA graph that is constant time rather than O(size of PHI node) we have
now.

Honza


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