For remainder:

If (1 << (Bitwidth / 2)) % Divisor == 1, we can add the high and low halves

together and use a (Bitwidth / 2) urem. If (BitWidth /2) is a legal integer

type, this urem will be expand by DAGCombiner using multiply by magic

constant. We do have to take into account that adding high and low

together can produce a carry, making it a (BitWidth / 2)+1 bit number.

So we need to also add back in the carry from the first addition.

For division:

We can use the above trick to compute the remainder, subtract that

remainder from the dividend, then multiply by the multiplicative

inverse of the Divisor modulo (1 << BitWidth).

This is based on the section "Remainder by Summing Digits" in

Hacker's delight.

The remainder trick is similar to a trick you may have learned for

determining if a decimal number is divisible by 3. You can add all the

digits together and see if the sum is divisible by 3. If you're not sure

if the sum is divisible by 3, you can add its digits together. This

can be repeated until you have a single decimal digit. If that digit

is 3, 6, or 9, then the original number is divisible by 3. This works

because 10 % 3 == 1.

gcc already does this same trick. There are additional tricks gcc

does urem as well as srem, udiv, and sdiv that I plan to add in

future patches.