llvm dev - Oct 2015 - 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,

Tiago
-- 
Tiago Trevisan Jost
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151023/c3677811/attachment.html>

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
>