[llvm-dev] Help on implementation of a modulo scheduling algorithm

[Mattias Eriksson V via llvm-dev]

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?
>

Hi!

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.

--
Mattias

> Thank you in advance,
>
> Tiago
>
> --
> Tiago Trevisan Jost
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>