[llvm-dev] More on DemandedBits

[John Yates via llvm-dev]

On Mon, Aug 24, 2020 at 2:39 PM LLVM Weekly <list at llvmweekly.org> wrote:

> * DemandedBits analysis was made more precise for addition.
> [c1f6ce0](https://reviews.llvm.org/rGc1f6ce0c732).
>

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
<http://citi2.rice.edu/WS07/KennethZadeck.pdf> 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
<https://en.wikipedia.org/wiki/Adder_(electronics)#Half_adder>. 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200901/4f7bc8b4/attachment.html>