This is the mail archive of the 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

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

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]