[LLVMdev] Need advice on writing scheduling pass

[Jonas Paulsson]

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>