Movatterモバイル変換

For SAM optimization and synthesis, CASH uses a new intermediate representation called Pegasus. Pegasus unifies several features of other intermediate representations: Is based on Static-Single Assignment Supports predication Supports speculation Unifies control-flow and data-flow. In Pegasus operations are asynchronously handshaking with their neighbors, to produce and consume data. The resulting circuits can be actually synthesized as locally-synchronous, globally-asynchronous implementations.

In order to expose substantial instruction-level parallelism we use several compilation techniques borrowed from predicated architectures:

• We decompose the CFG in hyperblocks; a hyperblock is a unit of speculative work.

• We use predication to transform the control-flow in each hyperblock into pure data flow. For this purpose, each basic block and each CFG edge has an associated "predicate".

• We use aggressive predicate promotion to execute speculatively all instructions with no side-effect. This figure shows how each basic block gives rise to two types of operations: computations and predicates. The predicate of blockb initially guards all instructions in blockb (shown by red arrows), but is later promoted to "true", unless it guards an instruction with side-effects (depicted in red).
  
  

The resulting representation is a form of Gated Single Assignment (a relative of Static-Single Assignment) in which predicate conditions are explicitly represented.

This is an example program, its control-flow graph (which is a single hyperblock) and the resulting representation:

Scalar optimizations can be implemented very efficiently on Pegasus.

Constant folding Dead-code elimination Common-subexpression elimination These optimizations subsume: Control-flow optimizations such as straightening, branch chaining, unreachable code elimination, code hoisting and tail merging. Dataflow-based global optimizations optimizations, such as copy propagation, constant propagation, partial redundancy elimination, value numbering, redundant memory operation removal. Mixed control- and data- optimizations: removal ofif statements with constant conditions.

A variety of new algebraic optimizations:

When implementing Pegasus in hardware we apply further optimizations.

Boolean operations can sometimes produce a result before knowing all input values; for example, a logical "and" can immediately produce a zero when one input is zero, irrespective of the value of the second input. We call such operation implementationslenient. In hardware we implement leniently boolean operations, multiplexors and side-effect operations (which do not need to compute when the guarding predicate is false).

The handshaking between operations gives rise to a naturalloop pipelining effect, in which multiple iterations of a loop can proceed simultaneously.

  int f(void)  {  int i, sum=0;    for (i=0; i < 100; i++)      sum += i;return sum;  }

Pegasus explicitly represents may-dependences through memory between operations usingtoken edges. The token edges are both a compile-time object, used to focus the optimizer and scheduler and also a run-time object, used for fine-grained synchronization for memory access only between dependent operations.

Operations that may access the same memory regions and which do not commute have token edges inserted between them: the red dashed lines in this figure. Notice that there's no token edge between*q and*r, since there is no control-flow between them. The token edges give an SSA-like representation for memory, enabling compact and powerful optimizations for memory, as the traditional scalar SSA form does. The token edge graph is maintained in a transitively reduced for throughout compilation. The meaning of the edges can thus be summarized as follows:

Memory operations guarded by a false predicate can be completely removed.

Two consecutive stores (i.e. connected by a token edge) to the same address can be simplified, since the second may overwrite the first. The first ought to be executed only when the second is not. Then the token edge connecting them can be removed, since the two stores will never occur simultaneously.

Accesses at the same address can be coalesced by or-ing the predicates. This is a form of partial-redundancy elimination.

Fine-grained tokens are also carried around loops using mu-eta operators. This gives rise to loop pipelining for memory, similar to the pipelining for scalars described above.