Michael Gschwind photo Krishnan Kailas photo photo

DAISY - DAISY Compilation Principles

The DAISY scheduling algorithm does not re-order writes to resources architected in the original machine, even though it does aggressive speculative code motions. For PowerPC this means that general purpose registers r0-r31, floating point registers fp0-fp31, condition code registers cr0-cr7, special purpose registers and memory are written in the original program order. In order memory updates means that STORE instructions are executed in order. This feature serves to maintain precise exceptions.

The VLIW machine has additional registers which it uses to perform speculative execution. Results of speculatively performed operations are placed in the additional registers and then copied, in order, to registers architected in the original machine. In a machine with sufficient resources, speculatively scheduling operations as early as data dependences allow can achieve maximum parallelism on each path, regardless of the path taken.

The scheduling algorithm scans linearly through PowerPC ops until a natural stopping point is reached, such as an unconditional branch that goes beyond the boundaries of the code fragment being examined. Conditional branches place their two target addresses (fall-through and taken) in a list of continuations. Whenever the algorithm comes to a natural stopping point on the current path, it looks for the next highest priority continuation, and resumes scheduling that path. This continues until the continuation list is empty. At this point the translated code may be jumped to and executed.

An interactive example illustrates the point. In this example, the fall-through paths of each conditional branch are scheduled first (assuming the fall-through path has higher priority), followed by the two branch targets. The code fragment size is assumed to be one page, so when an offpage reference is encountered, translation stops.