Missed Optimisation Bug - Unsigned Divsion by 7 (and various other constants)

Hi

It seems like Clang's routine for unsigned divide by 7 (or various other numbers) is sub-optimal.

Clang seems to be using a version of the algorithm in Hacker's Delight, which (for 32 bit divides) requires multiplication by a constant spanning up to 33 bits.

Essentially for an unsigned integer x, division by 7 is implemented by multiplying by (2^35+3)/7 (which spans 33 bits) and then shifting right 35 bits. This is expensive because it requires breaking the multiplication into two components, and performing an addition (which then requires handling overflows appropriately).

A better strategy is to implement division by 7 as (x*c+c)>>33 where c=(2^33-1)/7 (spanning only 31 bits). In this case there's no possibility of overflow, and several fewer instructions can be used. I created a thread on this example here:

https://stackoverflow.com/questions/79969064/faster-unsigned-divide-7-and-19-etc-on-aarch64-gcc-clang

As Peter Cordes and myself demonstrated, unsigned division by 7 could be implemented much more efficiently than it is.

The same thing occurs for dividing by 19, 21 and various other numbers where Clang's approach is to multiply by numbers spanning 33 bits. It is possible to implement these divides the same way (x*c+c)>>n for constants c spanning 32 bits or fewer. I believe the approach is first mentioned in a paper of Arch Robison (though I'm not sure the fact it works so generally has been appreciated). I have some brief & elementary mathematical proofs of the general case which I can share if useful.

Start with Clang's unsigned constant-division routine and reproduce the generated code for division by 7, 19, and 21, using the linked Stack Overflow discussion for the proposed comparison. Done means the relevant constant-divide cases use the more efficient strategy where applicable and generated code is validated across the affected constants.

Written by the indexing model from the issue text.