https://gcc.gnu.org/bugzilla/show_bug.cgi?id=117091
--- Comment #14 from andi at firstfloor dot org --- On 2024-10-17 05:59, rguenther at suse dot de wrote: > 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.
