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


With loop bounds recording no longer charged to the expander it's time
to deal with the inefficiencies which are in the switch expander.

Basically we have code which does

for each case
  for each case
    see if the label in the outer loop matches any of the cases in the
    inner loop (up to the current case in the outer loop).

Needless to say this can get rather expensive.

This patch avoids the inner loop completely by keeping track of the
target labels we've seen in a bitmap and only incrementing the unique
target count when we encounter a target which hasn't been seen.

Before this patch we got the following times for expand in pr15524.


expand          :   6.53 ( 5%) usr   0.03 ( 4%) sys   6.56 ( 5%)

After this patch we see:

expand          :   0.71 ( 1%) usr   0.02 ( 3%) sys   0.75 ( 1%)


Not bad.  Unfortunately, no measurable difference on insn-attrtab.i
and friends.  Oh well.

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



Attachment: ZZZ
Description: Text document


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