<div dir="ltr"><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><span class="gmail-im" style="color:rgb(80,0,80)"><div dir="ltr"><div class="gmail_default"><span style="font-family:Arial,Helvetica,sans-serif">On Mon, Aug 24, 2020 at 2:39 PM LLVM Weekly <<a href="mailto:list@llvmweekly.org" target="_blank">list@llvmweekly.org</a>> wrote:</span><br></div></div></span><div class="gmail_quote"><span class="gmail-im" style="color:rgb(80,0,80)"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">* DemandedBits analysis was made more precise for addition.<br>[c1f6ce0](<a href="https://reviews.llvm.org/rGc1f6ce0c732" rel="noreferrer" target="_blank">https://reviews.llvm.org/rGc1f6ce0c732</a>).<br></blockquote><div><br></div></span><div class="gmail_default">This warmed my heart.  At Apollo Computer back in the mid-1980's,</div><div class="gmail_default">when I was leading a team building a brand new RISC backend for</div><div class="gmail_default">the forthcoming Apollo DN10K, one of the most fun things I coded up</div><div class="gmail_default">was analyzing arithmetic in a Wegman-Zadeck style constant folder.</div><div class="gmail_default">(It was the <a href="http://citi2.rice.edu/WS07/KennethZadeck.pdf" target="_blank">first commercial compiler to include SSA</a> and the WZ</div><div class="gmail_default">Sparse Conditional Const algorithm.)</div><div class="gmail_default"><br></div><div class="gmail_default">If I understood Simon Pilgrim's write up correctly my approach was</div><div class="gmail_default">a bit more aggressive.</div><div class="gmail_default"><br></div><div class="gmail_default">Values were represented as a pair of masks, the first indicating</div><div class="gmail_default">which bits were actually known to the analysis and the second</div><div class="gmail_default">indicating the individual bit values.  Using addition as an example,</div><div class="gmail_default">we can say (as LLVM is doing) that sum bits beyond bit N cannot</div><div class="gmail_default">be affected by input bits N and below so long as both input bits</div><div class="gmail_default">at position N are zero.  This is because if both input bits are zero</div><div class="gmail_default">there can be no carry into bit position N+1.  But we need not stop</div><div class="gmail_default">there.  We can also say the bits beyond bit N cannot be affected</div><div class="gmail_default">by input bits N and below if at least one input bit at position N is</div><div class="gmail_default">zero and there is no carry into bit position N.  Again, this is</div><div class="gmail_default">because there can be no carry into bit position N+1.  Taken</div><div class="gmail_default">together these conditions really amount to saying that a lower</div><div class="gmail_default">bit position can affect the next bit position only if it produces a</div><div class="gmail_default">carry-out.</div><div class="gmail_default"><br></div><div class="gmail_default">Recall that a one-bit full adder at bit position N it has three inputs:</div><div class="gmail_default"><ul><li>Carry-in from bit position N-1</li><li>LHS input bit N</li><li>RHS input bit N</li></ul></div><div class="gmail_default">and two outputs:</div><div class="gmail_default"><ul><li>Result (sum) bit N</li><li>Carry-out to bit position N+1</li></ul></div><div class="gmail_default">There will be no carry-out if at least two input bits are false.</div><div class="gmail_default"><br></div><div class="gmail_default">Typically we do not think about carries between bit positions.</div><div class="gmail_default">But, if instead of using the computer's built-in integer addition</div><div class="gmail_default">instruction, one uses bitwise operations then one can expose</div><div class="gmail_default">the carries as a pair of masks, akin to the original inputs and</div><div class="gmail_default">the final output.  The problem then reduces to simulating a</div><div class="gmail_default">cascaded pair of <a href="https://en.wikipedia.org/wiki/Adder_(electronics)#Half_adder" target="_blank">half-adders</a>. At the end one has the carry</div><div class="gmail_default">out of each bit position.  If the carry out is demonstrably zero</div><div class="gmail_default">then the result at the next bit position must be insensitive to</div><div class="gmail_default">the values of any bits at lower bit positions.</div><font color="#888888"><div class="gmail_default"><br></div><div class="gmail_default">/john</div><div class="gmail_default"><br></div></font></div></div></div>