On Tue, Oct 29, 2024 at 01:50:57PM +0100, Richard Biener wrote: > On Mon, Oct 28, 2024 at 9:58 PM Andi Kleen <a...@linux.intel.com> wrote: > > > > From: Andi Kleen <a...@gcc.gnu.org> > > > > The current switch bit test clustering enumerates all possible case > > clusters combinations to find ones that fit the bit test constrains > > best. This causes performance problems with very large switches. > > > > For bit test clustering which happens naturally in word sized chunks > > I don't think such an expensive algorithm is really needed. > > > > This patch implements a simple greedy algorithm that walks > > the sorted list and examines word sized windows and tries > > to cluster them. > > > > Surprisingly the new algorithm gives consistly better clusters > > for the examples I tried. > > > > For example from the gcc bootstrap: > > > > old: 0-15 16-31 96-175 > > new: 0-31 96-175 > > > > I'm not fully sure why that is, probably some bug in the old > > algorithm? This shows even up in the test suite where if-to-switch-6 > > now can generate a switch, as well as a case in switch-1.c > > > > I don't have a proof that the new algorithm is always as good or better, > > but so far at least I don't see any counter examples. > > > > It also fixes the excessive compile time in PR117091, > > however this was already fixed by an earlier patch > > that doesn't run clustering when no targets have multiple > > values. > > OK if you add a comment (as part of the function comment for example) > explaining the idea of the algorithm.
I added the comment. I will commit it with this change. I also had to add a few more -fno-bit-tests to make the Linaro tester happy. However this exposes PR117352 which is a negative interaction of the more aggressive bit test conversion. I don't think it's a show stopper, this can be sorted out later. -Andi
