[LLVMdev] [llvm-commits] Bottom-Up Scheduling?

Andrew Trick atrick at apple.com
Tue Oct 25 21:00:06 PDT 2011

On Oct 25, 2011, at 6:01 PM, Hal Finkel wrote:
> Is there documentation somewhere for the bottom-up scheduling? I'm
> trying to figure out what changes are necessary in order to support it
> in the PPC backend.
> Thanks in advance,
> Hal
> On Thu, 2011-10-20 at 10:21 -0700, Evan Cheng wrote:
>> On Oct 19, 2011, at 7:29 PM, Hal Finkel <hfinkel at anl.gov> wrote:
>>> Evan,
>>> Thanks for the heads up! Is there a current target that implements the
>>> scheduling as it will be? And does the bottom-up scheduling also account
>> ARM is a good model. 
> What part of ARM's implementation is associated with the bottom-up
> scheduling? I am confused because it looks like it is essentially using
> the same kind of ScoreboardHazardRecognizer that was commented out of
> the PPC 440 code.
> Thanks in advance,
> Hal

Hi Hal,

The best way to ensure the PPC scheduling isn't hosed now or in the
future is probably to make it work as much like ARM as possible.

This means (1) defaulting to the "hybrid" scheduler, (2) implementing the
register pressure limit, and (3) reenabling the hazard recognizer.

(1) TargetLowering::setSchedulingPreference(Sched::Hybrid)

(2) TargetRegisterInfo::getRegisterPressureLimit(...) should probably
return something a bit less than 32, depending on register class.

(3) The standard hazard recognizer works either bottom-up or top-down
on the itinerary data. So it *should* work out-of-box. The problem is
that PPC has overriden the API to layer some custom "bundling" logic
on top of basic hazard detection. This logic needs to be reversed for
bottom-up, or you could start by simply disabling it instead of the
entire hazard recognizer.

Now, to generate the best PPC schedules, there is one thing you may
want to override. The scheduler's priority function has a
HasReadyFilter attribute (enum). It can be overriden by specializing
hybrid_ls_rr_sort. Setting this to "true" enables proper ILP
scheduling, and maximizes the instructions that can issue in one
group, regardless of register pressure. We still care about register
pressure enough in ARM to avoid enabling this. I'm really not sure how
much it will help on modern PPC implementations though.

I realize this is confusing because we have a scheduler mode named
"ILP". That mode is intended for target's that do not have an
itinerary. It's currently setup for x86 and would need some tweaking
to work well for other targets. Again, if your target has an
itinerary, you probably want the "hybrid" mode.


On Wed, 2011-10-19 at 16:45 -0700, Evan Cheng wrote:
>>>> Hi Hal,
>>>> Heads up. We'll soon abolish top-down pre-register allocation scheduler and force every target to bottom up scheduling. The problem is tt list scheduler does not handle physical register dependency at all but it is something that's required for some upcoming legalizer change.
>>>> If you are interested in PPC, you might want to look into switching its scheduler now. The bottom up register pressure aware scheduler should work quite well for PPC.
>>>> Thanks,
>>>> Evan

More information about the llvm-dev mailing list