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

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
> 
> > for pipeline-conflict hazards?
> 
> Yes, definitely. And it should be doing a much better job of it. 
> 
> Evan
> 
> > 
> > -Hal
> > 
> > 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

-- 
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory

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

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

On Tue, 2011-10-25 at 21:00 -0700, Andrew Trick wrote:
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.
> hybrid_ls_rr_sort
Can this be done without modifying common code? It looks like
hybrid_ls_rr_sort is local to ScheduleDAGRRList.cpp.

Thanks again,
Hal

-- 
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory