Strength Reduction and Algebraic Identities

The folklore version of strength reduction is a list of tricks: multiply by a power of two becomes a shift, divide by a constant becomes a multiply by a magic reciprocal, x % 2 becomes a mask. All of those are real transformations that real compilers do. What has changed is how much any of them is worth on a current machine, and the honest answer is: usually very little, and the compiler already knows.

A modern out-of-order core executes an integer multiply in about three cycles, fully pipelined, so a multiply issued every cycle costs one cycle of throughput. A shift costs one cycle of latency. The difference exists and it is two cycles of latency on an operation that is almost never the critical path — and the compiler will pick whichever one its cost model prefers for the specific target, which it knows and you probably do not. Writing x << 1 instead of x * 2 in source does not usually make the output different; it makes the source harder to read and it makes the intent — multiply by two — invisible.

Integer division is the one place where the cost gap is still large: a division is on the order of twenty to forty cycles and is not fully pipelined, and the reciprocal-multiply trick genuinely wins. That transformation is not something to write by hand either; it requires computing a magic number and a shift with a correctness proof, and every mainstream compiler does it for a constant divisor.

The interesting content of this pass is not cost, it is which rewrites are permitted at all. x + 0 -> x is unconditional for every integer type in every language: addition of the additive identity returns the operand, for all values, with no exceptions. That is a fact about the integers, not about the compiler.

For IEEE-754 floating point it is false. If x is negative zero, x + 0.0 is positive zero, and the two are distinguishable: 1.0 / -0.0 is negative infinity, 1.0 / 0.0 is positive infinity. So a compiler that rewrites x + 0.0 to x has changed what the program computes for one input. It is not a rounding difference; it is a different value.

The list continues, and each entry is a program someone has been surprised by. x * 0.0 is not 0.0 — it is NaN when x is NaN and negative zero when x is negative. x / x is not 1.0, for zero and for NaN. (a + b) + c is not a + (b + c), because floating-point addition is not associative, which is why a compiler may not reassociate a sum to vectorize it without permission. Every one of these is a rewrite that is valid over the reals and invalid over the floats.

This is where -ffast-math comes in, and it deserves stating precisely: it is not a performance flag, it is a semantics flag. It tells the compiler to optimize as though floating-point arithmetic were real arithmetic — associative, with no NaN, no infinities, and no signed zero. Under it the rewrites above become legal, code gets faster, and programs that depended on IEEE-754 behavior stop working. It also, on some toolchains, changes the behavior of code in other translation units by setting flush-to-zero mode at startup, which is why it is one of the few flags whose effects escape the file it was applied to.

AtlasLang's strength-reduction pass performs the additive and multiplicative identities and nothing else: x + 0, x - 0, x * 1, x / 1, 0 + x, 1 * x, and x * 0 to zero. Every one of them is unconditional — and the pass guards them with if (i.type !== 'int') continue.

That guard is doing two jobs. The narrow one is to stop "a" + "" being treated as an additive identity: it happens to be one for strings today, and relying on that would break the moment a string type gained a different empty value. The broad one is documentation. AtlasLang has no floating-point type, so the guard can never fire on a float — and it is written anyway, so that the reason the identities are unconditional is visible in the code rather than assumed.

The rewrite mechanism is worth noticing too. Rather than replacing the instruction with a copy, the pass builds a map from destination register to replacement value, rewrites every use through it, and then deletes the defining instructions. That is the same shape as [[copy-propagation]] and [[common-subexpression-elimination]] — record a substitution, apply it everywhere, drop the orphans — which is not a coincidence: most value-level optimizations are substitutions with different conditions on when the substitution is allowed.

The transformation the term originally named is not about single expressions at all. Classical strength reduction operates on *induction variables* inside a loop: a value computed as a multiplication of the loop counter is replaced by a value updated with an addition each iteration.

A loop that computes base + i * 8 on every iteration is doing a multiply per iteration. If i increases by one each time, the address increases by eight each time, so the multiply can be replaced with an add on a value carried around the loop. That is a real win, it applies to essentially every array access in every loop after [[lowering]] turns indexing into address arithmetic, and it is the transformation that makes loop-heavy code competitive — see [[loop-transformations]].

The legality condition is different in kind from the identity rewrites: it depends on proving that the value really is an affine function of the loop counter, that the loop counter really does increase by a constant, and that the derived value does not overflow in a way the language cares about. That last condition is why induction-variable work in C is entangled with signed-overflow undefined behavior — the compiler is allowed to widen an int induction variable to a pointer-sized one precisely because signed overflow is undefined, and cannot make the same move for an unsigned, whose wraparound is defined.