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. 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? Thanks Jonas On Aug 11, 2010, at 12:14 PM, Akira Hatanaka wrote:> Remove unreachable machine basic blocks > Live Variable Analysis > Eliminate PHI nodes for register allocation > Two-Address instruction pass > Process Implicit Definitions. > MachineDominator Tree Construction > Machine Natural Loop Construction > Modulo scheduing <== modulo scheduling pass inserted here > Slot index numbering > Live Interval Analysis > MachineDominator Tree Construction > Machine Natural Loop Construction > Simple Register Coalescing > Calculate spill weights > Live Stack Slot Analysis > Virtual Register Map > Linear Scan Register Allocator[...]> Here are my questions: > 1. Which passes after the scheduling pass can be run without modification? I suspect LiveIntervalAnalysis will not be able to handle the transformed BB judging from the way it handles two-address code and phijoins. Will the other passes need to be changed as well?"Simple Register Coalescing" can handle any code, but the live intervals must be correct.> 2. Is the scheduling pass inserted in the right position? Currently the scheduling pass is run right before Slot index numbering and LiveInterval analysis, since I thought it would required a lot of work to fix the indexes and intervals if the scheduling pass were run after these two passes.I recommend that you do not edit machine code between "Live Variable Analysis" and "Live Interval Analysis". LiveIntervals cannot handle general code, it requires something that is SSA form except for the specific edits from phi-elim and 2-addr. It also requires kill flags and the live variable analysis information to be correct. If you insert your pass before LiveVariables, you must preserve SSA form. If you insert your pass after LiveIntervals, you must update the intervals manually and correctly. If you don't, everything breaks. It's a pain, sorry!> 3. If the scheduling pass does local register allocation too, is there a way to tell the register allocation pass that is run later not to touch it?Yes, simply replace the virtual registers with the allocated physical registers. Then the register allocator won't touch them. Remember to create live intervals for the physical registers. That is how the register allocator detects interference.> Any advice, comments and suggestions are appreciated.It is much easier to edit machine code while it is in SSA form. That is before LiveVariables. /jakob -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110524/2cb5450c/attachment.html>
Jakob Stoklund Olesen
2011-May-24 16:59 UTC
[LLVMdev] Need advice on writing scheduling pass
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
hi Jonas, On Wed, May 25, 2011 at 12:59 AM, Jakob Stoklund Olesen <stoklund at 2pi.dk> wrote:> > 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.People had discussed VLIW support before, you may have a look at this: http://old.nabble.com/VLIW-Scheduling-td857833.html I implemented the VLIW scheduling/register allocate in llvm backend like the way described in the above thread, and it work without any problem. best regards ether
On May 24, 2011, at 9:59 AM, Jakob Stoklund Olesen wrote:> 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.This is only worth doing if these assumptions are valid: - The SSA form embedded in liveintervals permits efficient DAG construction - liveintervals are easy and cheap to update within an extended basic block (contiguously laid out blocks with no merges) - Inserting copies to break interferences is easy to do prior to physical regalloc, and the corresponding liveinterval update is cheap. This is very different from creating physreg copies, when you may not have any free physregs! Presenting the scheduler with coalesced virtual registers doesn't need to constrain the schedule. It really provides better information to the schedule. post-RA-sched is only left to cleanup split/spill code--a localized problem. -Andy
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>
Apparently Analagous Threads
- [LLVMdev] Need advice on writing scheduling pass
- [LLVMdev] Need advice on writing scheduling pass
- [LLVMdev] How to update LiveInterval information of newly inserted machine basic block
- [LLVMdev] Very slow performance of lli on x86
- [LLVMdev] Reproducing output of llvm-gcc using opt tool