[LLVMdev] Need advice on writing scheduling pass

[Gergö Barany]

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