https://gcc.gnu.org/bugzilla/show_bug.cgi?id=117091
--- Comment #13 from rguenther at suse dot de <rguenther at suse dot de> --- On Thu, 17 Oct 2024, pheeck at gcc dot gnu.org wrote: > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=117091 > > --- Comment #12 from Filip Kastl <pheeck at gcc dot gnu.org> --- > (In reply to Andi Kleen from comment #9) > > Yes I guess we should keep better switches at -O1 because machine generated > > code may have lot of switches. > > > > I don't think we need perfect clustering? Perhaps there is some heuristic > > that is good enough. Maybe just kmeans or something like that. > > > > The deep recursion I saw was for balance_case_nodes > > Yeah, maybe there exists some heuristic that we could use. I believe that > kmeans solves a different problem that just happens to also be called > clustering. > > So I think we should do this > 1) Turn off the current bit test and jump table clustering algorithms on -O0 > (Andi already submitted this patch) > 2) Turn off the current algorithms for switches bigger than some constant (not > sure how big it should be) > 3) Try to come up with a clustering algorithm which doesn't guarantee optimal > results but runs fast. Use it when the current algorithms are switched off > > BTW For (2) maybe this limit could be dynamic and proportionate to the square > root of the size of the whole program? That way O(n^2) algs would still be > linear in the size of the whole compiler input. I think we should simply add an upper bound static number and make it a new --param. We can also possibly divide the switch into two (with an if) and thus go to two times half N - finding interesting subdivisions (rather than "half") might be possible. The new --param would then apply to the part size we stop dividing the switch up.
