(no subject)

As an erstwhile compiler writer I was struck by the SPEC CPU 2006 example in Souper Results 2. 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. 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.