Fixing the pre-pass scheduler on x86 (Bug 38403)

["Shobaki, Ghassan" <Ghassan dot Shobaki at amd dot com>]

Hi,

I am considering working on fixing the pre-pass scheduling problem on
x86 (Bug 38403). The pre-pass instruction scheduler currently increases
register pressure to a degree that causes the register allocator to
fail. Before I commit to this task, I would like to gather as much
information as possible about the problem. What does the GCC community
know about the complexity of this problem? Has anyone ever worked on
fixing it? If yes, did they come up with any interesting findings that I
should be aware of? 

In theory, the problem can be fixed by adding a heuristic that keeps
track of register pressure during scheduling and favors the scheduling
decisions that lead to less register pressure. I have done some initial
investigation and found that the scheduler already has a heuristic that
attempts to do that, but apparently this heuristic does not work as
expected. The code I am referring to is in the function
rank_for_schedule in haifa-sched.c. I have modified the code in that
function to make this register-weight heuristic the top-priority
heuristic but that did not make a big difference (the number of passing
CPU2006 benchmarks only went up from 5 to 6 out of 29 benchmarks). 

So, my current hypothesis is that the problem can be fixed by developing
a more effective register pressure heuristic. To keep the problem
simpler, I plan on initially limiting my work to basic-block scheduling
(i.e., setting the maximum number of basic blocks in a scheduling region
to 1). We have reasons to believe that even with this limitation,
pre-pass scheduling can give 1-2% performance improvement on x86.

Any known information about this problem?

Thank you in advance!

-Ghassan