Krishnan Kailas photo

DAISY - Demo and Tutorial

The figure below depicts the scheduling of a PowerPC code fragment into VLIW instructions by DAISY. The VLIW instructions use a tree format. VLIW tree instructions permit multiple ALU operations as well as multiple conditional branches to be executed in a single VLIW instruction (cycle). To accomplish this, at the start of each the VLIW machine reads the set of condition code registers. These condition code registers determine which path through the VLIW instruction tree is to be taken. Only operations on the taken path are executed (at least conceptually). This is in some ways similar to predicated execution.

In this example, 11 PowerPC ops were scheduled into 2 VLIW instructions (two machine cycles) with the DAISY compilation algorithm.

PowerPC to VLIW translation example

Note:An OFFPAGE branch has a target beyond the page boundary. When executed, OFFPAGE branches check if the target is translated. If yes, then the translation is branched to. Otherwise the translator is branched to. There are 3 separate paths through the 11 PowerPC instructions of this example:

  • The all fall through path has 7 PowerPC ops spread over VLIW1 and VLIW2. Hence 3.5 PowerPC ops per cycle are effectively executed in the VLIW machine.
  • The add-bc L1-sub-b OFFPAGE path has 4 PowerPC ops and executes entirely within VLIW1 yielding 4.0 PowerPC ops per cycle.
  • Finally the path which falls through at bc L1 and branches at bc L2 has 8 PowerPC ops. These eight execute over two VLIW instructions, also resulting in 4.0 PowerPC ops per cycle.

The DAISY scheduling algorithm maintains precise exceptions, even though it does aggressive re-ordering of code for achieving performance. Namely, when an exception occurs while executing the translated VLIW code, it is always possible to find a corresponding PowerPC instruction in the PowerPC code. For example, VLIW2: corresponds to the point in the PowerPC code just before sli. This is useful for achieving full architectural compatibility.

To see how the scheduling is done step-by-step in DAISY for this example, you can take a look at our interactive demo below. Here is also an explanation of relevant DAISY compilation principles.

DAISY Scheduling: Interactive

Move the mouse pointer over the instructions at left. For each instruction, the figure on the right changes to show how and why it is scheduled.

l1 l2 l3 l4 l5 l6 l7 l8 l9 l10 l11 divider Interactive example for DAISY scheduling