[LLVMdev] VLIW Scheduling

[Tzu-Chien Chiu]

VLIW (Very Long Instruction Word) is a long instruction format (called
"group" hereafter) contains several instructions. These instructions
are not dependent on each other and could be issued in a single cycle.

At this moment there is no correspondent class for VLIW. MachineInstr
object can only represent one instruction. Usually the number of
instructions in a group is fixed. The grouping could be implicitly
maintained by inserting dummy nops to the instruction sequence. For
example, there are at most two  instructions in a VLIW, if items in
MachineBasicBlock::Insts is:

  MUL
  ADD
  ADD
  NOP
  MUL
  NOP

It implies the scheduling:

  MUL - ADD
  ADD - NOP
  MUL - NOP

Each pairs could be issued in parallel.

However, "one single MachineInstr" is the "unit" of many passes, e.g.
LiveVariables and LiveIntervals. Without modifications, some code-gen
result may be inefficient (or incorrect).

For example:

  mul %reg1025, %reg1024, 1
  add %reg1026, %reg1024, 2

Suppose the life interval of %reg1024 ends at ADD (no use after ADD).
These two instructions are not dependent and could be scheduled
together:

  mul %reg1024, %reg1025, 1 -  add %reg1026, %reg1025, 2

The life intervals of  vi%reg1024 and %reg1025 are actually _not_
interfered with each other,

  %reg1024 => r1
  %reg1025 => r1
  %reg1026 => r2

  mul  r1, r1, 1 -  add r2, r1, 2

Note the physical register r1 could be re-used. r1 is the source
register of both instructions, its valued is fetched and used as the
inputs to MUL and ADD, before the MUL updates r1. It's not an
anti-dependency.

But without modification, the live interval analysis and the register
allocator will consider %reg1024 and %reg1025, and allocate different
physical registers to each of them. What's the minimal changes I have
to make to "cheat" the LiveIntervals and LiveVariables?

What else I may have to change for VLIW scheduling?

-- 
Tzu-Chien Chiu,
3D Graphics Hardware Architect
<URL:http://www.csie.nctu.edu.tw/~jwchiu>