llvm dev - Feb 2010 - [LLVMdev] Integrated instruction scheduling/register allocation

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
-- 
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 Feb 3, 2010, at 6:00 AM, Gergö Barany wrote:
> 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.
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

On Feb 3, 2010, at 10:30 AM, Jakob Stoklund Olesen wrote:
> 
> On Feb 3, 2010, at 6:00 AM, Gergö Barany wrote:
> 
>> 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.
> 
> 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
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev