On Thu, 5 Dec 2024, Filip Kastl wrote: > 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.
I guess it's how we choose other such numbers, so whatever you chose is fine - I was mostly curious here ;) Richard. > Cheers, > Filip > -- Richard Biener <rguent...@suse.de> SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg, Germany; GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)
