https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118032
--- Comment #24 from Filip Kastl <pheeck at gcc dot gnu.org> --- Thanks for the preprocessed file! I've looked at -ftime-report to see if the extra time was spent in switch lowering and found out it is not! Apparently the change in behavior of switch lowering has an effect on some other passes -- they get much slower. I've also figured out which switch lowering change causes this: The patch adds a limit on the size of a switch. When this limit is exceeded, GCC uses a faster algorithm for finding bit tests and gives up on finding jump tables. The jump tables are the important part. It doesn't seem to matter that much how we search for bit tests or if we search for them at all (-fno-bit-tests). However, turn off searching for jump tables (-fno-jump-tables) and the compilation time increases from 6s to 80s. Here is a part of the output of -ftime-report if I disable jump tables: gcc insn-attrtab.ii -O2 -c --param switch-lower-slow-alg-max-cases=1000000 -ftime-report -fno-jump-tables Time variable wall GGC phase parsing : 2.34 ( 3%) 346M ( 54%) phase opt and generate : 87.07 ( 97%) 293M ( 46%) callgraph functions expansion : 86.73 ( 97%) 205M ( 32%) df live regs : 14.98 ( 17%) 0 ( 0%) df live&initialized regs : 24.05 ( 27%) 0 ( 0%) backwards jump threading : 1.24 ( 1%) 3480k ( 1%) tree switch lowering : 1.89 ( 2%) 23M ( 4%) if-conversion : 34.38 ( 38%) 12M ( 2%) TOTAL : 89.43 644M I've selected only entries contributing at least 1s to the compile time. Here are the same entries if I remove -fno-jump-tables: Time variable wall GGC phase parsing : 2.34 ( 38%) 346M ( 71%) phase opt and generate : 3.85 ( 62%) 134M ( 28%) callgraph functions expansion : 3.52 ( 57%) 47M ( 10%) df live regs : 0.06 ( 1%) 0 ( 0%) df live&initialized regs : 0.03 ( 0%) 0 ( 0%) backwards jump threading : 0.12 ( 2%) 671k ( 0%) tree switch lowering : 2.23 ( 36%) 4626k ( 1%) if-conversion : 0.01 ( 0%) 356k ( 0%) TOTAL : 6.22 485M One way to fix this would be to not apply the switch size limit on jump tables. Since finding jump tables is at least O(n^2), this could theoretically cause long compile times in some specific cases. However, nobody has reported any bug of that kind yet. There is only pr117091 for bit tests. That pr would remain fixed, I believe. Do we want to do that, though? Maybe GCC taking this long to compile something just because we didn't use jump table lowering is a sign of a problem in a different pass?
