Presently working on various aspects of Netezza's tera-scale database technology.

In an earlier role I was one of the senior engineers in the Apollo Computer compiler group.

The Apollo compiler suite was notable for shipping the first commercial software pipeliner / modulo scheduler. It may also have been the first commercial use of SSA and SSA based optimizations.

Ken Zadeck visited us at one point and got a presentation of our particular approach. I remember that he was not particularly taken with our hybrid approach of SSA-values threaded through a classic CFG and bound to live-range containers. What is true is that we were able to modulate our optimizations and transformations via access to their potential effect on the number simultaneously live live-ranges (a lowerbound on register pressure). Thus we avoided the effect of wholesale abandonment of any notion of control flow and physical locations (the hallmark of the classic SSA transform) and the disastrous register allocation consequences of subsequent reintroduction of control flow and physical location constraints.

The Apollo implementation of Conditional Const was interesting. Rather than propagate a constant we propagated a bundle of facts about the result of an IL instruction:

Given a set of operand bundles symbolic execution of an IL instruction produced a new (or refined) bundle of facts.

We also implemented SSA over the reverse CFG. This allowed us to compute for each instruction in the graph the exact nature of downstream demand. This analysis was also represented as a bit mask. Thus we could recognize when only a bit field in the middle of some register was live. We also were particularly effective at moving and/or eliminating widening operations (sign and zero extension) and field extraction. As an example when we saw two commensurate bit fields extracted and or-ed together we could perform the or operation before extraction. (Remember that this was not an optimization on an expression tree but rather a true SSA / global analysis and transformation.)

None: JohnYates (last edited 2008-01-10 19:38:58 by localhost)