This warmed my heart. At Apollo Computer back in the mid-1980’s,

when I was leading a team building a brand new RISC backend for

the forthcoming Apollo DN10K, one of the most fun things I coded up

was analyzing arithmetic in a Wegman-Zadeck style constant folder.

(It was the first commercial compiler to include SSA and the WZ

Sparse Conditional Const algorithm.)

If I understood Simon Pilgrim’s write up correctly my approach was

a bit more aggressive.

Values were represented as a pair of masks, the first indicating

which bits were actually known to the analysis and the second

indicating the individual bit values. Using addition as an example,

we can say (as LLVM is doing) that sum bits beyond bit N cannot

be affected by input bits N and below so long as both input bits

at position N are zero. This is because if both input bits are zero

there can be no carry into bit position N+1. But we need not stop

there. We can also say the bits beyond bit N cannot be affected

by input bits N and below if at least one input bit at position N is

zero and there is no carry into bit position N. Again, this is

because there can be no carry into bit position N+1. Taken

together these conditions really amount to saying that a lower

bit position can affect the next bit position only if it produces a

carry-out.

Recall that a one-bit full adder at bit position N it has three inputs:

- Carry-in from bit position N-1
- LHS input bit N
- RHS input bit N

and two outputs:

- Result (sum) bit N
- Carry-out to bit position N+1

There will be no carry-out if at least two input bits are false.

Typically we do not think about carries between bit positions.

But, if instead of using the computer’s built-in integer addition

instruction, one uses bitwise operations then one can expose

the carries as a pair of masks, akin to the original inputs and

the final output. The problem then reduces to simulating a

cascaded pair of half-adders. At the end one has the carry

out of each bit position. If the carry out is demonstrably zero

then the result at the next bit position must be insensitive to

the values of any bits at lower bit positions.

/john