On Fri 2024-11-15 12:08:24, Richard Biener wrote: > On Fri, 15 Nov 2024, Filip Kastl wrote: > > > Hi, > > > > Andi's greedy bit test finding algorithm was reverted. I found a fix for > > the > > problem that caused the revert. I made this patch to reintroduce the greedy > > alg into GCC. However I think we should keep the old slow but more powerful > > algorithm so I added a limit on the number of cases of the switch statement > > that decides which of the two algorithms to use. > > > > Bootstrapped and regtested on x86_64-linux. > > > > I've also bootstrapped and regtested version of this patch where I force > > switch > > lowering to only use the Andi's greedy algorithm (with my fix). This also > > went > > smoothly without any testsuite regression nor problems during bootstrap > > (which > > surprised me -- I expected some testcases to rely on bit test finding to be > > powerful but I double checked and really didn't find any problems). OFC > > I've > > also checked that the greedy algorithm doesn't cause the problems from > > PR117352 > > anymore. > > > > Ok to push? > > > > Thanks, > > Filip Kastl > > > > > > -- 8< -- > > > > > > This patch adds a limit on the number of cases of a switch. When this > > limit is exceeded, switch lowering decides to use faster but less > > powerful algorithms. > > > > In particular this means that for finding bit tests switch lowering > > decides between the old dynamic programming O(n^2) algorithm and the > > new greedy algorithm that Andi Kleen recently added but then reverted > > due to PR117352. It also means that switch lowering may bail out on > > finding jump tables if the switch is too large (Btw it also may not > > bail! It can happen that the greedy algorithms finds some bit tests > > which then basically split the switch into multiple smaller switches and > > those may be small enough to fit under the limit.) > > > > The limit is implemented as --param switch-lower-slow-alg-max-cases. > > Exceeding the limit is reported through -Wdisabled-optimization. > > > > This patch fixes the issue with the greedy algorithm described in > > PR117352. The problem was incorrect usage of the is_beneficial() > > heuristic. > > Did you adjust the testcase to use the 10000 default of the param > and figure it's still fast enough with it? If the alg is quadratic > 10000^2 is quite large ;)
Ah, sorry. Forgot to mention how I came up with that number. I didn't use any scientific process for that. I wasn't sure what number to use. I picked 10000 because it seemed like no human-written switch will have that many cases. Then I ran the testcase set to 10000 and it finished under a second so I stuck with 10000. But yeah, thinking about it some more, 10000 seems like a lot. Maybe the limit could be 1000. That's also big enough. I could try to run the testcase set to 1000 on my not-so-powerful laptop this time and check that even on that machine it finishes "fast" (under a second I guess). I'm also open to any other ideas for how to choose this number. Cheers, Filip
