Technique:Recognizing compiler-generated code/Division by constants
Compilers replace division by a constant with a multiply by a magic number and shifts. How to spot it, the Hacker's Delight algorithm LLVM implements, worked examples (0xAAAAAAAB for /3, 0xCCCCCCCD for /5 and /10) and how to recover the divisor.
Integer division is slow, so for a constant divisor the compiler multiplies by an approximation of 2^k / d and shifts. In a disassembler it appears as a multiplication by a large odd constant with a shift of 32+ bits and no div/idiv instruction.
Unsigned
q = (n * M) >> (W + s), where W is the word width (32 or 64): on x86 the mul or imul produces the high half in EDX/RDX, then shr edx, s. The magic number M is ceil(2^(W+s) / d), so the divisor is d ≈ 2^(W+s) / M.
Worked examples (arithmetic checked; the instruction sequences are the usual compiler output):
/3: M = 0xAAAAAAAB (3 * M = 2^33 + 1), total shift 33 (multhenshr edx, 1)./5: M = 0xCCCCCCCD (5 * M = 2^34 + 1), total shift 34 (shr edx, 2)./10: M = 0xCCCCCCCD with total shift 35 (shr edx, 3), i.e. /5 then halved; 2^35 / 10 rounded up is 0xCCCCCCCD./7: M = 0x24924925 is the 32-bit approximation of 2^32 / 7 but is not exact enough alone: LLVM sets the IsAdd flag and the code fixes up witht = n - hi; t >>= 1; t += hi; q = t >> 2(the add-and-shift pattern). Unverified: instruction sequence from memory of compiler output; the magic itself is checked (0x24924925 = floor(2^32/7)+1).- Even divisors: LLVM first shifts the dividend right by the divisor's trailing zero count (PreShift), then divides by the odd part with a smaller magic, avoiding IsAdd.
Signed
Signed division rounds toward zero, so the code multiplies with a signed magic, optionally adds or subtracts n, arithmetic-shifts right, then adds the sign bit: q += (q >>> 31) (a shr eax, 31; add edx, eax at the end). Example: /3 has signed magic 0x55555556 (3 * M = 2^32 + 2), shift 0, followed by the sign-bit fixup. Unverified: the signed /7 magic is 0x92492493 with an add of n; derived by hand.
Powers of two need no magic: unsigned shr, signed (n + ((n >> 31) >>> (32 - k))) >> k.
The algorithm in LLVM
llvm/lib/Support/DivisionByConstantInfo.cpp implements it from Hacker's Delight (Warren), chapter 10: SignedDivisionByConstantInfo::get(D) returns Magic and ShiftAmount; UnsignedDivisionByConstantInfo::get(D, LeadingZeros, AllowEvenDivisorOptimization, AllowWidenOptimization) returns Magic, PreShift, PostShift and IsAdd, plus a Widen form that uses a wider multiply for 32-bit divides on 64-bit machines (magic stored as 2^W + Magic, pre-shifted). Divisor 0 and 1 are excluded (and -1 for signed). The divisor can be re-derived with the same function to confirm a candidate: compute the info for d and compare magic and shifts.
Recovering d
- Note M (as unsigned), the register width W and the total right shift S (the multiply's implicit W plus explicit shifts).
- d = round(2^S / M). Check candidates around it with the algorithm above (or any compiler: compile
x / dand compare). - If an add/sub of n is involved (IsAdd), the true magic is 2^W + M, so use d = 2^S / (2^W + M).
- The same constant reappears for
%:r = n - q * d(animulandsubafter the magic multiply).
Evidence & references
- llvm-project
llvm/lib/Support/DivisionByConstantInfo.cpp(read in full).