llvm dev - Apr 2016 - How to get started with instruction scheduling? Advice needed.

So if I use the SchedMachineModel method, can I just skip itineraries?

Phil

On Wed, Apr 20, 2016 at 12:29 PM, Sergei Larin <slarin at codeaurora.org>
wrote:
> Target does make a difference. VLIW needs more hand-holding. For what you
> are describing it should be fairly simple.
>
>
>
> Best strategy – see what other targets do. ARM might be a good start for
> generic superscalar. Hexagon for VLIW style scheduling.
>
>
>
> Depending on what you decide, you might need different target hooks.
>
>
>
> Sergei
>
>
>
> ---
>
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted
> by The Linux Foundation
>
>
>
> *From:* llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] *On Behalf Of
*Phil
> Tomson via llvm-dev
> *Sent:* Wednesday, April 20, 2016 12:51 PM
> *To:* LLVM Developers Mailing List <llvm-dev at lists.llvm.org>
> *Subject:* [llvm-dev] How to get started with instruction scheduling?
> Advice needed.
>
>
>
> I need to add instruction scheduling for a new target which is a fairly
> simple in-order execution machine.
>
> I've been watching this presentation from a 2014 LLVM dev meeting as it
> seems relevant:
>
> "SchedMachineModel: Adding and Optimizing a Subtarget"
> http://llvm.org/devmtg/2014-10/Slides/Estes-MISchedulerTutorial.pdf
>
> In this presentation the author says that there have been several ways to
> approach scheduling in LLVM over the years:
>
>    - Pre 2008: SelectionDAGISel pass creates the ScheduleDAG from the
>    SelectionDAG at the end of instruction selection
>    - ScheduleDAG works on SelectionDAG Nodes (SDNodes)
>    - Circa 2008: Post Register
>
> Allocation pass added for
>
> instruction selection ( SchedulePostRATDList
>
> works on MachineInstrs)
>
>    - Circa 2012: MIScheduler
>
> (ScheduleDAGMI) added as
>
> separate pass for pre-RA
>
> scheduling
>
>    - Circa 2014: MIScheduler
>
> adapted to optionally replace
>
> PostRA Scheduler
>
> In the presentation he goes with defining a subclass of SchedMachineModel
> in the schedule .td file. And apparently with this approach there are no
> instruction itineraries.
>
> So I'm wondering: what's the current recommended way to approach
this and
> does it depend on the type or target? (in-order, superscalar, out of order,
> VLIW...)?
>
> Someone earlier started to define instruction itineraries for our target.
> Should I continue down this road or move over to the SchedMachineModel
> approach? Are there other recommended presentations/documents that I should
> be looking at?
>
>
>
> Thanks.
>
> Phil
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160420/a2bb9902/attachment-0001.html>

I notice from looking at ARMScheduleA9.td that there seems to be a hybrid
approach where they still have itineraries but also use SchedMachineModel:

//
===---------------------------------------------------------------------===//
// The following definitions describe the simpler per-operand machine model.
// This works with MachineScheduler and will eventually replace itineraries.

class A9WriteLMOpsListType<list<WriteSequence> writes> {
  list <WriteSequence> Writes = writes;
  SchedMachineModel SchedModel = ?;
}

// Cortex-A9 machine model for scheduling and other instruction cost
heuristics.
def CortexA9Model : SchedMachineModel {
  let IssueWidth = 2; // 2 micro-ops are dispatched per cycle.
  let MicroOpBufferSize = 56; // Based on available renamed registers.
  let LoadLatency = 2; // Optimistic load latency assuming bypass.
                       // This is overriden by OperandCycles if the
                       // Itineraries are queried instead.
  let MispredictPenalty = 8; // Based on estimate of pipeline depth.

  let Itineraries = CortexA9Itineraries;

  // FIXME: Many vector operations were never given an itinerary. We
  // haven't mapped these to the new model either.
  let CompleteModel = 0;
}

I'm guessing this is probably the way forward for my case since Itineraries
seem to be already mostly defined.

Phil

On Wed, Apr 20, 2016 at 1:27 PM, Phil Tomson <phil.a.tomson at gmail.com>
wrote:
> So if I use the SchedMachineModel method, can I just skip itineraries?
>
> Phil
>
> On Wed, Apr 20, 2016 at 12:29 PM, Sergei Larin <slarin at
codeaurora.org>
> wrote:
>
>> Target does make a difference. VLIW needs more hand-holding. For what
you
>> are describing it should be fairly simple.
>>
>>
>>
>> Best strategy – see what other targets do. ARM might be a good start
for
>> generic superscalar. Hexagon for VLIW style scheduling.
>>
>>
>>
>> Depending on what you decide, you might need different target hooks.
>>
>>
>>
>> Sergei
>>
>>
>>
>> ---
>>
>> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum,
hosted
>> by The Linux Foundation
>>
>>
>>
>> *From:* llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] *On Behalf
Of *Phil
>> Tomson via llvm-dev
>> *Sent:* Wednesday, April 20, 2016 12:51 PM
>> *To:* LLVM Developers Mailing List <llvm-dev at lists.llvm.org>
>> *Subject:* [llvm-dev] How to get started with instruction scheduling?
>> Advice needed.
>>
>>
>>
>> I need to add instruction scheduling for a new target which is a fairly
>> simple in-order execution machine.
>>
>> I've been watching this presentation from a 2014 LLVM dev meeting
as it
>> seems relevant:
>>
>> "SchedMachineModel: Adding and Optimizing a Subtarget"
>> http://llvm.org/devmtg/2014-10/Slides/Estes-MISchedulerTutorial.pdf
>>
>> In this presentation the author says that there have been several ways
to
>> approach scheduling in LLVM over the years:
>>
>>    - Pre 2008: SelectionDAGISel pass creates the ScheduleDAG from the
>>    SelectionDAG at the end of instruction selection
>>    - ScheduleDAG works on SelectionDAG Nodes (SDNodes)
>>    - Circa 2008: Post Register
>>
>> Allocation pass added for
>>
>> instruction selection ( SchedulePostRATDList
>>
>> works on MachineInstrs)
>>
>>    - Circa 2012: MIScheduler
>>
>> (ScheduleDAGMI) added as
>>
>> separate pass for pre-RA
>>
>> scheduling
>>
>>    - Circa 2014: MIScheduler
>>
>> adapted to optionally replace
>>
>> PostRA Scheduler
>>
>> In the presentation he goes with defining a subclass of
SchedMachineModel
>> in the schedule .td file. And apparently with this approach there are
no
>> instruction itineraries.
>>
>> So I'm wondering: what's the current recommended way to
approach this and
>> does it depend on the type or target? (in-order, superscalar, out of
order,
>> VLIW...)?
>>
>> Someone earlier started to define instruction itineraries for our
target.
>> Should I continue down this road or move over to the SchedMachineModel
>> approach? Are there other recommended presentations/documents that I
should
>> be looking at?
>>
>>
>>
>> Thanks.
>>
>> Phil
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160420/dfe72a51/attachment.html>

Hi Phil.

You more or less answered your own question, but let me give you some more info.
Maybe it is of use.
>From what I understand the SchedMachineModel  is the future, although it is
not as powerful as itineraries at present. The mi-scheduler is mostly developed
around out-of-orders cores, I believe (I love to hear arguments on the
contrary). Some of the constraints that can be found in in-order micro
architectures cannot be expressed in the per-operand scheduling model and the
heuristics of the pre-RA scheduling pass is probably a bit too focussed on
register pressure for in-order cores (I have no numbers, just hearsay).
There is some documentation in comments at the start of
include/llvm/Target/TargetSchedule.td that you might find useful. If you are
going to look at an existing scheduling model, I suggest to look at an in-order
core. A good example would be AArch64/AArch64SchedA53.td. If itineraries are
present, they are used by the mi-scheduler next to the SchedMachineModel to
detect hazards. I think that is the only place where the mi-scheduler uses
itineraries.

There are some magic numbers you need for in-order operation. Most notably
MicroOpBufferSize should be set to 0 for full in-order behaviour. You also want
to set CompleteModel to 0 as that prevents asserts due to instructions without
scheduling information. There is a script that might help you to visualise if
you have provided scheduling information in the SchedMachineModel for all
instructions (utils/schedcover.py). It is very simplistic and takes as input the
debug output of tablegen. There are some usage comments at the beginning.

Regards,
Christof

From: llvm-dev <llvm-dev-bounces at lists.llvm.org<mailto:llvm-dev-bounces
at lists.llvm.org>> on behalf of Phil Tomson via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>>
Reply-To: Phil Tomson <phil.a.tomson at gmail.com<mailto:phil.a.tomson at
gmail.com>>
Date: Wednesday, 20 April 2016 23:06
To: LLVM Developers Mailing List <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>>
Subject: Re: [llvm-dev] How to get started with instruction scheduling? Advice
needed.

I notice from looking at ARMScheduleA9.td that there seems to be a hybrid
approach where they still have itineraries but also use SchedMachineModel:

// ===---------------------------------------------------------------------===//
// The following definitions describe the simpler per-operand machine model.
// This works with MachineScheduler and will eventually replace itineraries.

class A9WriteLMOpsListType<list<WriteSequence> writes> {
  list <WriteSequence> Writes = writes;
  SchedMachineModel SchedModel = ?;
}

// Cortex-A9 machine model for scheduling and other instruction cost heuristics.
def CortexA9Model : SchedMachineModel {
  let IssueWidth = 2; // 2 micro-ops are dispatched per cycle.
  let MicroOpBufferSize = 56; // Based on available renamed registers.
  let LoadLatency = 2; // Optimistic load latency assuming bypass.
                       // This is overriden by OperandCycles if the
                       // Itineraries are queried instead.
  let MispredictPenalty = 8; // Based on estimate of pipeline depth.

  let Itineraries = CortexA9Itineraries;

  // FIXME: Many vector operations were never given an itinerary. We
  // haven't mapped these to the new model either.
  let CompleteModel = 0;
}

I'm guessing this is probably the way forward for my case since Itineraries
seem to be already mostly defined.

Phil

On Wed, Apr 20, 2016 at 1:27 PM, Phil Tomson <phil.a.tomson at
gmail.com<mailto:phil.a.tomson at gmail.com>> wrote:
So if I use the SchedMachineModel method, can I just skip itineraries?

Phil

On Wed, Apr 20, 2016 at 12:29 PM, Sergei Larin <slarin at
codeaurora.org<mailto:slarin at codeaurora.org>> wrote:
Target does make a difference. VLIW needs more hand-holding. For what you are
describing it should be fairly simple.

Best strategy – see what other targets do. ARM might be a good start for generic
superscalar. Hexagon for VLIW style scheduling.

Depending on what you decide, you might need different target hooks.

Sergei

---
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The
Linux Foundation

From: llvm-dev [mailto:llvm-dev-bounces at
lists.llvm.org<mailto:llvm-dev-bounces at lists.llvm.org>] On Behalf Of
Phil Tomson via llvm-dev
Sent: Wednesday, April 20, 2016 12:51 PM
To: LLVM Developers Mailing List <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>>
Subject: [llvm-dev] How to get started with instruction scheduling? Advice
needed.

I need to add instruction scheduling for a new target which is a fairly simple
in-order execution machine.

I've been watching this presentation from a 2014 LLVM dev meeting as it
seems relevant:
"SchedMachineModel: Adding and Optimizing a Subtarget"
http://llvm.org/devmtg/2014-10/Slides/Estes-MISchedulerTutorial.pdf
In this presentation the author says that there have been several ways to
approach scheduling in LLVM over the years:

  *   Pre 2008: SelectionDAGISel pass creates the ScheduleDAG from the
SelectionDAG at the end of instruction selection
  *   ScheduleDAG works on SelectionDAG Nodes (SDNodes)
  *   Circa 2008: Post Register
Allocation pass added for
instruction selection ( SchedulePostRATDList
works on MachineInstrs)

  *   Circa 2012: MIScheduler
(ScheduleDAGMI) added as
separate pass for pre-RA
scheduling

  *   Circa 2014: MIScheduler
adapted to optionally replace
PostRA Scheduler

In the presentation he goes with defining a subclass of SchedMachineModel in the
schedule .td file. And apparently with this approach there are no instruction
itineraries.

So I'm wondering: what's the current recommended way to approach this
and does it depend on the type or target? (in-order, superscalar, out of order,
VLIW...)?

Someone earlier started to define instruction itineraries for our target. Should
I continue down this road or move over to the SchedMachineModel approach? Are
there other recommended presentations/documents that I should be looking at?



Thanks.

Phil


IMPORTANT NOTICE: The contents of this email and any attachments are
confidential and may also be privileged. If you are not the intended recipient,
please notify the sender immediately and do not disclose the contents to any
other person, use it for any purpose, or store or copy the information in any
medium. Thank you.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160426/e126bf61/attachment.html>