llvm dev - May 2011 - [LLVMdev] Need advice on writing scheduling pass

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>

On Thu, May 26, 2011 at 15:07:24 +0200, Jonas Paulsson
wrote:
> In order to get a pre-RA scheduling, I would need something like:
> - LiveVars
> - PhiElim
> - TwoAddr
> - LiveIntervals
> - Coalescing
> - Scheduler       (new)
> - SlotIndexing
> - LiveIntervals2  (new)
> - RegAlloc
> My qeustion then is, is it really so difficult to create the live intervals
information, with modifications to the original algorithm, or even from scratch?
I've done something similar to this in the past, though without the
coalescing part. As I was interested in spilling, coalescing didn't matter
to me. I approached this in a simple but possibly inelegant way, by
integrating it into the LiveIntervals pass itself.

In LiveIntervals::runOnMachineFunction, after the computeIntervals() call
that does the actual work of the live interval analysis, I call my
scheduler. After scheduling, I simply do the following:


  // Fix up kill information for live intervals. Rescheduling may often have
  // changed which instruction is a value's last use, and we must update
  // kill flags and the kill information in the VarInfo objects.
  fixKillInformation();

  // Now, release the stuff we computed, and recompute it!
  releaseMemory();

  // Then, recompute the slot indexes. There is a function renumberIndexes,
  // but it doesn't respect our new ordering of instructions, so do this by
  // completely clearing the results of the slot index analysis and simply
  // calling it again.
  indexes_->releaseMemory();
  indexes_->runOnMachineFunction(*mf_);

  // Now compute live intervals again. That's it!
  computeIntervals();


The fixKillInformation() function is also mine; it updates the isKill flags
of MachineOperands and the lists of killing instructions maintained by
LiveVariables.

This setup isn't quite in line with LLVM's pass architecture, but it war
easy to do as a quick-and-dirty thing. Contact me off-list if you are
interested in more information of my work, my (ugly) source and my results.
I would also be interested in more details about what you are planning to
do!
> 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?
My understanding is that physregs are only ever used for very brief, local
operations; for instance, an argument register is loaded before a function
call but is dead afterwards. Return registers are immediately copied to
virtual registers and can then be considered dead.

This way, you don't need to track liveness and reaching definitions for such
registers across blocks. But probably someone with a better understanding of
this design should weigh in.


Gergo
-- 
Gergö Barany, research assistant                   gergo at
complang.tuwien.ac.at
Institute of Computer Languages        http://www.complang.tuwien.ac.at/gergo/
Vienna University of Technology                         Tel: +43-1-58801-58522
Argentinierstrasse 8/E185, 1040 Wien, Austria           Fax: +43-1-58801-18598

On May 26, 2011, at 6:36 AM, Gergö Barany wrote:
>> 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?
> 
> My understanding is that physregs are only ever used for very brief, local
> operations; for instance, an argument register is loaded before a function
> call but is dead afterwards. Return registers are immediately copied to
> virtual registers and can then be considered dead.
> 
> This way, you don't need to track liveness and reaching definitions for
such
> registers across blocks.
That's right.

It it possible to have physregs live across blocks, but they must be explicitly
added to the live-in list for each block.

/jakob

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110526/8be754cd/attachment.html>