Module divide 

A division by a constant, as a multiply by its reciprocal and a shift.

Design: spec/optimizer/19-reassociation-and-arithmetic.md section 19.5, which hands this to the back end.

A div takes twenty to forty cycles and a multiply takes three, so every compiler turns a division by a constant into a multiply by a number close to its reciprocal, scaled up by a power of two, and a shift that takes the scale back out. The number is what Granlund and Montgomery call the magic number, and multiplier works it out the way choose_multiplier at gcc/expmed.cc:3728 does.

Why the product is sixty four bits wide

gcc writes the multiply as a high multiply at the width of the division, which is an instruction the IR does not have. What it has is an ordinary multiply at sixty four bits, and a dividend of at most thirty two bits times a magic number of at most thirty three fits in one. So the dividend is widened, multiplied, and shifted by the width and the post shift at once, and the answer is the low half of that. It is also one step shorter than gcc’s when the magic number needs thirty three bits: gcc cannot hold the sum of the dividend and the high half in thirty two bits and halves the difference first, and here the sum fits.

A division at sixty four bits needs the high half of a hundred and twenty eight bit product, which is what umulh and smulh are, and it is written the way gcc writes it: the high half, then the extra add or a shift in front when the number needs sixty five bits, then the post shift. An unsigned divisor with the top bit set is left alone, since the quotient is zero or one and a compare is the right code. A power of two and an exact division need no product and are done at every width.

What the dividend is known to hold

C divides at int at least, so an unsigned short divided by ten is an int division of a value widened from sixteen bits. The widening says the value fits in sixteen bits, a magic number for sixteen bits is smaller and never needs the extra add, and a signed division of a value that cannot be negative is the unsigned one. Range is that, read off the instruction the dividend comes from.

What is left alone

Everything when the goal is size, where the div is shorter, which is what gcc does at -Os. A divisor of zero, one or minus one, which is undefined or which the optimizer has already answered. A divisor larger than anything the dividend can hold, where the quotient is zero or one and a compare is the right code, which is rare enough to wait.

How it is checked

program writes the rewrite as a short list of Steps before anything goes into the function, and the tests run that same list on numbers. At eight bits that is every dividend against every divisor. At sixteen it is every divisor, over the dividends either side of each of its multiples, which is a proof rather than a sample: the rewrite and the division it replaces only ever move at those points, so agreeing there is agreeing everywhere. At thirty two and sixty four bits there are too many multiples to go through, so it is the ends, the multiples nearest them and a random sample. cargo xtask divide runs what the compiler makes of the same divisions against gcc.

Structs

Division

One division or remainder by a constant, as far as the rewrite needs to know it.

Program

A rewrite, in the order it is written.

Enums

Range

What the dividend is known to hold.

Step

One instruction of a rewrite.

Functions

divisions

Rewrites every division and remainder by a constant that program has an answer for.

multiplier

The magic number for dividing by divisor a value of bits bits whose top bits - precision bits are known to be clear, and the shift that goes after the multiply.

program

The rewrite for one division, or None where the div is left.