llvm dev - Nov 2011 - [LLVMdev] [llvm-commits] Bottom-Up Scheduling?

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.

-Andy

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
>>>>

On Tue, 2011-11-22 at 13:27 -0600, Hal Finkel wrote:
> On Tue, 2011-10-25 at 21:00 -0700, Andrew Trick wrote:
> > 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.
> 
> Is EmitInstruction used in bottom-up scheduling at all? The version in
> the ARM recognizer seems essential, but in all of the regression tests
> (and some other .ll files I have lying around), it is never called. It
> seems that only Reset() and getHazardType() are called. Could you please
> explain the calling sequence?
I feel that I should clarify my comment: For PPC, now that Hybrid
scheduling is enabled, EmitInstruction seems never to be called (at
least it is not called when running any PPC codegen test in the
regression-test collection).

Thanks again,
Hal
> 
> Thanks again,
> Hal
> 
> > 
> > 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.
> > 
> > -Andy
> > 
> > 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
> > >>>> 
> > 
> 
-- 
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory