[LLVMdev] Need advice on writing scheduling pass

[Jonas Paulsson]

Hi,

thank you for your explanations.

In order to get a pre-RA scheduling, I would need something like:
- LiveVars
- PhiElim
- TwoAddr
- LiveIntervals
- Coalescing
- Scheduler       (new)
- SlotIndexing
- LiveIntervals2  (new)
- RegAllocMy qeustion then is, is it really so difficult to create the live intervals information, with modifications to the original algorithm, or even from scratch? Normally, it should not have to be difficult to do a non-SSA live analysis pass. The format of the LiveInterval ought to serve well for any Live analysis, or? What are the pitfalls relating to the LLVM classes?

One thing that is somewhat unclear to me is why phys-regs are only considered live to end of block? Is this because the RA later ignores these registers? How come
this information is not needed?

Jonas


> Subject: Re: [LLVMdev] Need advice on writing scheduling pass
> From: stoklund at 2pi.dk
> Date: Tue, 24 May 2011 09:59:26 -0700
> CC: llvmdev at cs.uiuc.edu
> To: jnspaulsson at hotmail.com
> 
> 
> On May 24, 2011, at 8:22 AM, Jonas Paulsson wrote:
> 
> > Hi (Jakob),
> > 
> > in reference to the prior message below, I have the following follow-up questions, as I also need a scheduling pass 
> > prior to regalloc. I need to do this in order to set VLIW-flags, so that the RA is aware of several MI's
> > per cycle with a redefined LiveRange::overlap-function. On a multiple-issue cycle, a register that gets killed
> > can be reused by another MI - these live ranges do not then overlap.
> 
> Redefining overlap() won't work for that. There is other code assuming that overlap means overlap, for example the LiveIntervalUnion used by the new register allocators.
> 
> For VLIW, you probably want to number your packets instead of individual instructions. We don't have any VLIW support, so nobody has thought about how best to do it.
> 
> > Well, I would like to schedule the VLIW code after SimpleRegisterCoalescer, so that I get more or less the 
> > final code to work with. As the instructions are rearrange, I suppose I must run the SlotIndexes and 
> > LiveIntervals again. LiveVariables should also be refreshed as a register might get killed with a different
> > MI if two users change place, etc, I suppose.
> > 
> > I would like to just rerun these passes, but you said below that LiveIntervals do not work after SSA form is
> > abandoned.
> > 
> > I wonder how you mean to update the live intervals after scheduling -- the slot indexes must surely be useless
> > with a changed order of MI's?
> > 
> > Do you know of a scheme to rewrite these passes so that they can be rerun as needed? Is all but LiveIntervals
> > ok with this as of now?
> 
> So the good news is that we are slowly moving towards a similar design. The bad news is that we are *slowly* moving...
> 
> Currently, the register allocator super-pass contains these passes:
> 
> - LiveVars
> - PhiElim
> - TwoAddr
> - LiveIntervals
> - Coalescing
> - RegAlloc
> 
> Currently, LiveVars requires SSA form, and LiveIntervals only works with simple multi-defs as produced by PhiElim and TwoAddr. That means the pass order is fixed.
> 
> The plan is to teach PhiELim and TwoAddr how to update LiveIntervals so it can run earlier:
> 
> - LiveVars
> - LiveIntervals
> - PhiElim
> - TwoAddr
> - Coalescing
> - RegAlloc
> 
> Then we can eliminate LiveVars completely:
> 
> - LiveIntervals
> - PhiElim
> - TwoAddr
> - Coalescing
> - RegAlloc
> 
> This version of LiveIntervals will compute liveness autonomously, but it is very likely to also require SSA form because of the possible speedups.
> 
> The next step is to merge PhiElim and TwoAddr into a SuperCoalescer pass:
> 
> - LiveIntervals
> - SuperCoalescing
> - RegAlloc
> 
> Finally, Andy also wants to schedule after coalescing:
> 
> - LiveIntervals
> - SuperCoalescing
> - Schedule
> - RegAlloc
> 
> We don't have any concrete plans for how that scheduler would look. It would likely benefit from the existing LiveIntervals, at least the embedded SSA form is essential.
> 
> It is not clear if such a scheduler should preserve live intervals or if everything should be recomputed. There are also phase ordering issues; the scheduler would be severely constrained by our very aggressive coalescing, and it would expose further coalescing opportunities that RegAlloc probably wouldn't be able to exploit fully.
> 
> 
> But if you want to add a VLIW scheduler tomorrow, I don't know what to tell you. It's a big project.
> 
> /jakob
> 
 		 	   		  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110526/5c823fc6/attachment.html>