Pegasus graph massaging

• Constants: if they are larger than 16bits, they must be loaded by a sequence of two instructions, mvk and mvkh. A Pegasus op_const node corresponds to mvk, and op_consth corresponds to mvkh. Unlike op_const, op_consth takes a data input representing the register to be modified. You must make sure the same register is assigned to the in and out wires of a op_consth/mvkh!

  Immediate constants: if a constant fits in 5 bits, and all of its uses can use an immediate constant in place of a register, the constant node's output wire is given a special type of hard register representing an immediate value. This wire/register can then be completely ignored by your register allocator.

• Arguments at beginning of procedure: There are move (op_nop) nodes inserted after the args. This gives you the flexibility to move an argument from its original register (which is fixed by the calling convention) to any register your allocator chooses.

• Branch at end of hyperblock: We use the ``crt'' (current execution point) eta as the branch since they are similar in spirit. However, with Pegasus' non-strict execution, the crt eta could fire before or after the other etas controlled by the same predicate. In the case here, we must ensure that everything necessary is completed before the branch takes effect. Therefore we add a token edge tree (using tkands) from the other etas controlled by the same predicate to the crt eta. However, to account for the branch delay slots, a negative-latency nop is added between the token edge tree root and the crt eta (branch) -- this allows computation to complete in the branch delay slots, after the branch is issued but before it takes effect.

• Calls Calls are even more complicated than conditional branches. The result of the decomposition of a simple call is shown below.

  

  • The call is split into a call and a continuation (type op_asmcont). The call represents the branch to the callee. The continuation is where the call returns to.
  • A move is added on each regular argument input to the call.
  • A move is added on the call's output (return value) edge if such edge exists.
  • Constant nodes are created to represent the return address, which must be stored in register B3. The value is moved into the B3 register by a "constrain" node type, which is just a nop/move but with token edge input and output so that it can be more easily constrained in the graph. It is constrained to come after the call; this is to ensure that the register span for B3 is short and so will not overlap with the B3 usage for previous or subsequent calls.

• Callee-save registers are hard registers that must be preserved by the callee (the procedure that you are scheduling). The way it is handled is that the hard register is moved to a soft register with an ``op_movefrom" operation, then from the soft register back to the hard register with an ``op_moveto" operation. This will be addressed in more detail when we get to register allocation. However, it is in the interest of your scheduler to place ``op_movefrom" nodes as early in the schedule as possible, and the ``op_moveto" nodes as late as possible.