This is an archive of the discontinued LLVM Phabricator instance.

Improve machine schedulers for in-order processors
ClosedPublic

Authored by javed.absar on Mar 8 2017, 9:21 AM.

Details

Summary

This patch enables schedulers for in-order processors to specify instructions that
cannot be issued with any other instructions.

Schedulers for such sub-targets can now attach ‘let SingleIssue = 1; // single issue ‘
to any general sched class or individual instruction. The scheduler then does not
allow those instructions to be issued in same cycle with any other instruction.
In this way, the scheduler models more accurately the real pipeline behavior.
Some partial out-of-order processors may also benefit from this.

Diff Detail

Event Timeline

javed.absar created this revision.Mar 8 2017, 9:21 AM
MatzeB edited edge metadata.Mar 8 2017, 9:32 AM

Can't you already get this effect with BufferSize = 0 in a ProcResource?

Hi Matthias:

The single-issue restriction is on the instruction and not a limitation of the ProcResource e.g. for some processor, a load using load/store unit may be allowed dual-issue, but VLDx using the same load/store unit may not be allowed to dual-issue.

atrick edited edge metadata.Mar 8 2017, 4:10 PM

I think what Matthias was getting at is that you can add a new ProcResource to model issue constraints. If you have a dual issue machine then any instruction that can't be grouped would simply consume both issue resources. Another option might be to use the begin/end group flags.

A SingleIssue flag seems like special casing a problem that needs a general solution.

atrick added a comment.Mar 8 2017, 4:13 PM

That said, if there are multiple target maintainers who think adding a special SingleIssue case would be much better than the alternatives, then it may be worth adding.

MatzeB added a comment.Mar 8 2017, 4:22 PM

The single-issue restriction is on the instruction and not a limitation of the ProcResource e.g. for some processor, a load using load/store unit may be allowed dual-issue, but VLDx using the same load/store unit may not be allowed to dual-issue.

I guess this could still be modeled by making the instruction occupy every processor resource. So I was wondering whether we need the extension of the scheduling model.

That said, if there are multiple target maintainers who think adding a special SingleIssue case would be much better than the alternatives, then it may be worth adding.

We could also make the SingleIssue flag syntactic sugar so tablegen adds all available proc resources to the instruction.

I think what Matthias was getting at is that you can add a new ProcResource to model issue constraints. If you have a dual issue machine then any instruction that can't be grouped would simply consume both issue resources. Another option might be to use the begin/end group flags.

A SingleIssue flag seems like special casing a problem that needs a general solution.

For those of us quite familiar with the scheduler, using your suggested approach would indeed be a workaround. However, for those not so familiar, but wanting to use machine-scheduler to model their sub-target, the natural way to see ProcResource is as a resource (to do something e.g. perform an add). Using resource to impose restriction on instructions is bit counter-intuitive, and would not occur naturally at first. The sad consequence is - this aspect of the pipeline would not be properly or at all modeled.

I guess this could still be modeled by making the instruction occupy every processor resource. So I was wondering whether we need the extension of the scheduling model.

Good idea. Unfortunately a syntatic-sugar that adds 'every processor resource' would not work. For example, if div is not-pipelined and is in execution; then an instruction X that does not need UniDiv but is single issue cannot be issued and has to wait for div to finish.
Besides, workarounds destroy simplicity/elegance and having a straightforward bit 'isSingleIssue' that is simple to interpret for anyone and does exactly what it says, would possibly be better.

Separate processor resources should be defined to model issue resources rather than trying to work around it by consuming functional units. The processor resources were always intended to be used for both issue resources and functional units. It just isn't well documented or easily discoverable. It might makes sense to have either a single issue flag or a separate list of issue resources in the tablegen machine model. My argument is that the scheduler itself already supports this functionality.

There at three ways this feature is already generally supported by the scheduler's machine model:

  1. Begin/EndGroup.

This feature was added to model issue constraints that were too awkward to model with resources. It's the most straightforward way to model single issue. Adding syntactic sugar to tablegen's machine model should be trivial.

  1. Issue resources

Define a new type of processor resource with N units. A single-issue instructions takes N unit to issue. This was an intended use of the machine model. The scheduler will model it with the issue counter.

  1. Hardware ports.

x86 models "issue" ports this way.
e.g. def IssueSlots : ProcResGroup<[Slot0, Slot1]>

It was designed to handle micro-ops, so it's slightly misleading. A single-issue instruction on a dual issue machine would simply use both issue slots. Other instructions would use the IssueSlots group. The scheduler models this with a bit for each port.

This feature was added to model issue constraints that were too awkward to model with resources. It's the most straightforward way to model single issue. Adding syntactic sugar to tablegen's machine model should be trivial.

Can you please elaborate on this a bit so I can try to develop a patch to add this. Thanks.

Hi Andrew/Matthias:
Would having a "SingleIssue" bit flag, as this patch proposes, be a good user option, even though I agree other workarounds can achieve same effect.
Thanks.

I think a SingleIssue flag would be a good user option. Representing such a flag in the tables generated by the machine model (MCSchedClassDesc) would be redundant. Either begin/endgroup already does the same thing, or it's a bug that should be fixed.

I just looked at the MachineScheduler implementation. I see this TODO:
/// TODO: Also check whether the SU must start a new group.

So, I think your patch is necessary except:

  • The SubtargetEmitter can simply set the begin/end group flags for SingleIssue
  • Instead of adding an isSingleIssue() API to TargetSchedule, you should add mustBeginGroup() and mustEndGroup() that checks the existing bits in MCSchedClassDesc.
  • In the scheduler, mustBeginGroup() is a hazard if CurMOps > 0 when isTop() is true. Similarly, mustEndGroup() is the same hazard for !isTop().
  • Your patch needs to handle isTop() && mustEndGroup(); likewise, !isTop() && mustBeginGroup() by calling bumpCycle(++NextCycle). Do this just after setting CurrMOps at CurrMOps += IncMOps, and just before checking the MOps hazard at while (CurrMOps >= SchedModel->getIssueWidth()). That obviously needs to be commented: "Bump the cycle count for issue group constraints. This must be done after NextCycle has been adjust for all other stalls. Calling bumpCycle(X) with reduces CurrMOps by one issue group and sets currCycle to X."

Your current implementation of isSingleIssue is actually only half the solution. Implementing the begin/end group bits will make it complete.

Hi Andrew:
Thanks for the help. I have made the changes as you suggested (unless I misunderstood some parts). Please have a look.
Thanks a lot.
Javed

atrick requested changes to this revision.Mar 22 2017, 10:52 AM

Thanks.

I don't think you need the SingleIssue flag in MCSchedule.h any more.

Also, I don't see the hazard checker logic yet. I think you still need to so this:

  • In the scheduler, mustBeginGroup() is a hazard if CurMOps > 0 when isTop() is true. Similarly, mustEndGroup() is the same hazard for !isTop().

It looks like only half the logic is there now--the part where you bump the cycle when finishing a group. Maybe you need a better test case to exercise the hazard checking logic?

This revision now requires changes to proceed.Mar 22 2017, 10:52 AM
javed.absar edited edge metadata.

Hi Andrew:

You are right, I had missed out the hazard part. Have fixed things now. Please have a look if it is ok now.
Thanks
Javed

That looks good. But this version of the patch no longer has the SingleIssue flag support in the SubtargetEmitter. I thought you wanted that so the feature was more self-documenting. Your previous implementation looked ok to me. I just don't think you need any flag in the implementation of the model (MCSchedule.h).

Thanks Andrew. OK, I have added back 'SingleIssue' as syntactic sugar, but not in model, as recommended (if I got you right).
Best Regards, Javed.

atrick accepted this revision.Mar 26 2017, 1:32 PM

LGTM. I think you should comment in TargetSchedule.td that SingleIssue is an alias for Begin/EndGroup.

This revision is now accepted and ready to land.Mar 26 2017, 1:32 PM
This revision was automatically updated to reflect the committed changes.