[llvm-dev] Help on implementation of a modulo scheduling algorithm
Mattias Eriksson V via llvm-dev
llvm-dev at lists.llvm.org
Fri Oct 23 07:52:00 PDT 2015
On 10/23/2015 02:13 PM, Tiago Trevisan Jost via llvm-dev wrote:
> 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?
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
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.
> Thank you in advance,
> Tiago Trevisan Jost
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
More information about the llvm-dev