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

OK.  This ought to fix 18478, 18521 and any other breakages caused
by the introduction of CASE_LEADER _and_ speed up 15524 considerably.

As Kazu determined, sharing nodes within the case vector has some
rather unpleasant effects and IMHO fixing them was going to create
an unmaintainable mess in the tree copying code.

This patch kills the concept of a CASE_LEADER; however, it introduces
an edge to cases hash table which allows us to map from an edge to
the CASE_LABEL_EXPRs which use that edge.

Because we do not have all the hooks in place to be notified of
CFG changes, the hash table is not persistent.  Instead we create
on-demand in response to requests to redirect jumps out of SWITCH_EXPRs.

The code is designed so that it will work with or without the hash
table.  That way we don't have to worry about correctness issues
with passes that may redirect edges without creating the hash table.
[ Such passes will simply run slower if they redirect a lot of
  edges out of SWITCH_EXPRs.  ]

The effect on 15524 is dramatic.  Before this change:

tree CFG cleanup      :  15.14 (38%) usr   0.00 ( 0%) sys  15.16 (37%)
tree split crit edges :   7.50 (19%) usr   0.00 ( 0%) sys   7.50 (18%)
TOTAL                 :  40.27             0.80            41.09

After this change:

tree CFG cleanup      :   0.46 ( 3%) usr   0.00 ( 0%) sys   0.47 ( 2%)
tree split crit edges :   0.06 ( 0%) usr   0.00 ( 0%) sys   0.05 ( 0%)
TOTAL                 :  18.35             0.81            19.18

FWIW, if we could have a persistent hash table which was built during
CFG construction, the time for CFG cleanup would be effectively zero.

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]