Help on implementation of a modulo scheduling algorithm

Hi everyone,

I want to implement a modulo scheduling algorithm for a my VLIW backend and I would like to have your opinion about the best approach to do so.

I saw an early post which Jakob Stoklund Olesen suggested to implement the MS before LiveVariables/LiveIntervals/SlotIndex Passes, so I think I should take his advice. However, I want to try to reuse most of the work inside the framework to build the data dependence graph (DDG) for a Basic Block (loop in this case), therefore I was thinking on using the ScheduleDAGInstr Class to create that DAG with the SUnits for the instructions, because I would be able to have information about depth and height of each instruction on the BB. The problem is that the ScheduleDAGInstr class requires the LiveIntervals information in order to build the DAG associated with BB (when in PreRegAlloc)

  1. Is there any classes inside LLVM in order to create a Data Dependence Graph which does not require the use of LiveIntervals, and still work in the SSA form?
  2. Is addMachineSSAOptimization the best option to place the aforementioned MS pass?
  3. Any other advice that might help me with the implementation?

Thank you in advance,



I have done some work on a Swing modulo scheduling algorithm for our out-of-tree (VLIW) target.

We have inserted our VLIW scheduler between the register coalescer pass and the register allocator pass. This scheduler includes software pipelining and operates on ScheduleDAGInstrs and SUnits. We also have the option to run this scheduler after register allocation, but at that point I have found that SWP is very constrained by decisions made in register allocation.

I am not sure if this is the best way to do it, but it works quite well for us. In our case I think it would be hard to do the scheduling much earlier because the IR at that point is not similar enough to what the final instructions look like, and for a VLIW this makes exact scheduling, such as modulo scheduling, very hard to do.