Hi everyone,
I'm in the formative stage of my PhD studies. My current focus is on
integrated approaches to instruction scheduling and register allocation. A
colleague pointed me to Evan Cheng's talk at the August 2008 developer
meeting [1], where he very briefly mentioned allowing the register allocator
to reschedule instructions as a "crazy idea" for the future.
I independently arrived at the same crazy idea 
and I'm wondering if
anybody ever went and actually implemented a rescheduling allocator in LLVM.
I've done some poking around the web, the mailing list archives and the LLVM
source code, but I haven't found anything suggesting that this has been
done. If anyone has tried it and would be willing to share code, insights,
or lessons learned, I would be very grateful to hear from them.
[1] http://www.llvm.org/devmtg/2008-08/
Thanks,
Gergo
We don't have a rescheduling allocator, but we do have a post allocation rescheduler. Check out PostRASchedulerList.cpp
It would still be interesting to be able to change scheduling during allocation, I think.
/jakob
A more pressing need is a pre-regalloc scheduler that can switch modes to balance reducing latency vs. reducing register pressure.
The problem is the current approach is the scheduler is locked into one mode or the other. For x86, it generally makes sense to schedule for low register pressure. That is, until you are dealing with a block that are explicitly SSE code in 64-bit mode. In that case, you have relatively large number of registers to play with and the register pressure reduction scheduler doesn't work well. Same issue in ARM, there are a ton of 32-bit and 64-bit floating point registers.
Evan
Right. I'm actually working on implementing a variant of IPS (Goodman and
Hsu, Code scheduling and register allocation in large basic blocks,
http://doi.acm.org/10.1145/55364.55407) based on the existing list-td and
list-tdrr schedulers; this requires handling of physical register
dependencies in those schedulers, which I am currently struggling with. It's
all in a very messy pre-prototype stage, but I'm getting there and will be
happy to contribute my work when it's nice and clean.
Thanks for the feedback, Jakob and Evan.
Gergo
A more pressing need is a pre-regalloc scheduler that can switch modes to
balance reducing latency vs. reducing register pressure.
Right. I'm actually working on implementing a variant of IPS (Goodman and
Hsu, Code scheduling and register allocation in large basic blocks,
http://doi.acm.org/10.1145/55364.55407) based on the existing list-td and
Well, David is a LLVM contributor himself so perhaps he can give you some pointers.
list-tdrr schedulers; this requires handling of physical register
dependencies in those schedulers, which I am currently struggling with. It's
all in a very messy pre-prototype stage, but I'm getting there and will be
happy to contribute my work when it's nice and clean.
Sounds great. Thanks.
Evan
Took me a while to figure what Evan meant. I do have a lot of opinions about register allocation, but I am David Goodwin, not David Goodman... so I don't know anything about the work in this particular paper.
David