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

Vladimir Makarov vmakarov@redhat.com
Wed Apr 8 03:20:00 GMT 2009


Shobaki, Ghassan wrote:
> 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). 
>
That is a wrong heuristic because it incorrectly calculates the insn 
impact on register pressure.  For example, we have

1. use a
2. use a, dead a

The heuristic believes that the 2nd insn decreases register pressure and 
prefers #2 to #1 and that is wrong because in this case a is not 
becoming dead.

Although this heuristic was reported to be working well for powerpc and 
therefore it was added to GCC.
> 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?
>
>
I've been working on register-pressure sensitive insn scheduling last 
two months and I hope to submit this work for gcc4.5.  I am implementing 
also a mode in insn-scheduler to do only live range shrinkage.  
Implementing register pressure insn scheduling is not easy.  I already 
mentioned one issue above about dead notes.  Another issue is necessity 
to simultaniously work with ready and queue (not only with ready) to 
choose insn to schedule.  A lot of communication with IRA should be 
added too.

The bug itself is also a complicated issue which needs a good knowledge 
of insn scheduler, RA, and even reload to fix this.  The most bug cases 
are like

1. insn containing pseudos
2. ax<- something

The 2nd insn is moved before the 1st one and the first insn needs ax 
(e.g. it is a division).

The reload problem is more complicated.  For example, the 1st insn has 
only one alternative requiring ax
  1st operand: =a, r, ...
  2nd operand:  0, 0, ...

if both operands (pseudos) got memory, than cost of reloading for the 
1st and 2nd alternative is the same.  Reload can choose the 1st 
alternative and we have the same problem as above.





More information about the Gcc-bugs mailing list