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: [Bug tree-optimization/15524] [4.0 Regression] jump threadingon trees is slow with switch statements with large # of cases


And the saga continues....

This patch introduces the concept of a case leader to CASE_LABEL_EXPR.

As Kazu outlined, the case leader is the "representative value" for
the partition of cases which reach the same destination block.   The
case leader is the only CASE_LABEL_EXPR which contains a LABEL_DECL;
other members of the partition point to the case leader.

We convert to the case leader representation as we create edges for
each SWITCH_EXPR.

In this iteration of the change we still have to do a search of the
case vector to find the case leader when we redirect an edge out of
the SWITCH_EXPR.  A future version is expected to use a hash table,
but some kinks in that code still need to be worked out.

Even though we're still doing a search of the case vector, this
patch represents a big improvement for 15524.  Instead of having
to search the entire case vector when we redirect a jump, we 
(on average) half the case vector to find the leader.


To give you an idea of how this affects compile time, we have the
critical timevars before this patch:
 tree CFG cleanup      :  28.20 (49%) usr   0.06 ( 9%) sys  29.81 (48%) 
 tree split crit edges :  14.55 (25%) usr   0.02 ( 3%) sys  14.83 (24%)
 TOTAL                 :  57.76             0.70            62.18


After this patch:
 tree CFG cleanup      :  12.29 (36%) usr   0.01 ( 2%) sys  12.35 (34%)
 tree split crit edges :   5.91 (17%) usr   0.00 ( 0%) sys   5.92 (16%)
 TOTAL                 :  33.89             0.57            36.65

That's a pretty good improvement.

FWIW, a version which uses a persistent hash table for lookups of
edge to case leaders brings the CFG cleanup and critical edge
splitting phases down into the noise with a total time of < 18
seconds.

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


Attachment: PPP
Description: Text document


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