[LLVMdev] (no subject)

John Yates john at yates-sheets.org
Thu Dec 4 09:25:22 PST 2014

As an erstwhile compiler writer <https://gcc.gnu.org/wiki/JohnYates> I was
struck by the SPEC CPU 2006 example in Souper Results 2
<http://blog.regehr.org/archives/1192>.  I thought I would jot down a few
notes on how 20 years ago the Apollo Computer's compiler for the DN10K
would have handle it.

That compiler represented dataflow using SSA.  As I mentioned in my gcc
wiki page we employed a hybrid approach of SSA-values threaded through a
classic CFG and bound to live-range containers.  In preparation for
constant propagation we would examine values leading up to conditional
branches.  When such a value was mentioned within the range affected by
that branch flow we inserted pseudo definitions to capture facts derivable
from the control expression.  That allowed derived facts to be exploited
within the range of the control flow.  The phi-operator at the control flow
join restored the original, less specific set of facts..

Constant propagation was via an extension of Wegman and Zadeck's algorithm
<http://www.cs.ucr.edu/~gupta/teaching/201-08/Papers/const.pdf>.  Rather
than propagate single constants through the graph we propagated "bundles".
These were compact descriptions of what we knew about the values flowing
along an edge.  A bundle contianed 6 cells equal to the width of the
machine resource being modeled (typically a register-width value):

   - signed min
   - signed max
   - unsigned min
   - unsigned max
   - mask: bit is known
   - mask: bit actual value

Symbolic execution of intermediate operators took bundles as operands and
returned new bundles.  Implementing operators was a fun challenge.
Addition and subtraction went to the trouble of determining whether the
carry in and out of each bit position was known, thereby preserving
interesting facts about bits patterns.  We were not limited to equality
comparisons to zero.  Given

if (x < 0)

we could represent the fact that the sign bit was on the then side and off
on the else side.  And given your example of

if ((x & 0xf) == 0)

we would might know nothing more on the else branch, but on the then branch
(at the very least) we would know

   - bit is known mask = 0xf
   - bit value mask = 0

When that bundle fed a subsequent

if ((x & 0x7) == 0)

constant propagation we tell us that the else branch would never be taken.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141204/cc2437ae/attachment.html>

More information about the llvm-dev mailing list