Improve post-RA scheduling for SystemZ

[jonpa]

Summary

The idea of this patch is to continue the scheduler state over a MBB boundary in the case where the successor block has only one predecessor. This means that the scheduler will continue in the successor block (after emitting any branch instructions) with e.g. maintained processor resource counters. Benchmarks seem to benefit from this.

In order to do this the single HazardRecognizer is replaced with a map so that each MBB gets its own HazardRecognizer. This represent the outgoing state of that MBB. Another block which is only reached from MBB can then later take that state before beginning its first region.

*All* instructions are emitted, so that the state of the scheduler is as good as possible at the entry of the region. This means branches and also singular instructions before regions / in small MBBs.

Special care is taken for blocks with a call (which is about the only scheduling boundary on SystemZ), so that only the instructions after the call are part of the final scheduler state.

The only common code change needed is to set the MachineLoopInfo* pointer (that analysis pass seems to have been required also for post-RA scheduling, but not used for some reason).

[jonpa]

Updated per (off-line) review.

[jonpa]

Patch updated.

[jonpa]

updated per review

[jonpa]

This is the "alternate take" of the last version. I am not sure which is best...

This version introductes of MachineSchedStrategy::leaveMBB() and an optional reversal of BB schedregions traversal which

• eliminates PreviousMBB
• simplifies transferStateFromPRed()
• simplifies initialize() and setupHazardRecForScheduling() (HazardRec pointer could be removed, but kept to minimize diff for now)

This makes the idea of the order of processing scheduling regions in an MBB explicit, which is good since this patch is dependent on that order.
Overall, this simplifies the SystemZ implementation, but has some common-code changes so that the regions can be handled top-down per MBB. (MachineScheduler.cpp)

[uweigand]

It does indeed seem to be necessary to get an explicit guarantee from common code that scheduling happens in a particular order, otherwise our back-end code may silently break if common code logic happens to change in the future.

I would agree that getting common code to specifically call us in the top-down order we need to simplify cross-region tracking is also helpful. We should discuss this with the relevant common code scheduler developers -- can you check who has been working on this code lately and add them as reviewers?

[jonpa]

(gentle) ping - this patch is waiting for review of its common-code parts (MachineScheduler), which should be NFC for other targets.

[MatzeB]

This looks good to me in principle, but there are some comments below:

include/llvm/Target/TargetSubtargetInfo.h

166–170 ↗

(On Diff #107878)

My impression is that this decision is not based on the subtarget, but rather on what Scheduler is plugged in. Therefore we should better make this part of ScheduleDAGInstrs.

lib/CodeGen/MachineScheduler.cpp

408

Oh this was already required and not used by the PostMachineScheduler. Guess you got lucky and can just use it ;-)

441

///

451–489

Would it be possible to implement this more iterator style instead of synthesizing an std::vector (also std::vector is usually the wrong choice in llvm)? (I'm not talking full on STL iterator, just some object with a "get me the next region" function).

658–660

This should also call ScheduleDAGInstr::finishBlock().

[jonpa]

Thanks for review!

Patch updated.

[jonpa]

include/llvm/CodeGen/MachineScheduler.h

217 ↗

(On Diff #108609)

This comment is duplicated in several places, but not sure if this is expected.

include/llvm/Target/TargetSubtargetInfo.h

166–170 ↗

(On Diff #107878)

Aha. I changed it then so that the ScheduleDAGInstrs is called instead, which in turn calls the SchedStrategy, which makes sense as you pointed out. This is clearly better to me as well. Looks good?

lib/CodeGen/MachineScheduler.cpp

408

yes :-)

451–489

I made an attempt to wrap this in a class per your suggestion. Could not find a better vector class than std, however.. (?).

This is a bit more code compared to just calling std::reverse(). If we decide this is better, perhaps you know of an example in the LLVM code base that I could reuse if better?

658–660

yep

[atrick]

lib/CodeGen/MachineScheduler.cpp

441

Please explain what RegionBegin/End refer to here. Note that they need to be inclusive--they cannot refer to instructions outside of the identified scheduling region because those will be reordered before scheduling this region.

Also note somewhere that the scheduling pass cannot add instructions in other regions now without updating these boundaries.

[jonpa]

Comments updated per review.

Also, the comment

// MBB::size() uses instr_iterator to count. Here we need a bundle to
// count as a single instruction.

moved into getSchedRegions().

[uweigand]

A couple more comments on the SystemZ parts, see inline comments.

lib/Target/SystemZ/SystemZHazardRecognizer.cpp

415

I guess this is not only "counters". Maybe rename to "copyState" ?

463

Hmm. Shouldn't emitInstruction itself try to handle branches correctly? Maybe it only needs one extra bit of information passed in, whether to assume a branch is taken or not?

lib/Target/SystemZ/SystemZMachineScheduler.cpp

62

I'm wondering why you don't do the initial allocation of the hazard recognizer for the MBB (and taking over the predecessor state) right here. Currently, it seems that if an MBB is scheduled, this is done in "initialize", and if the MBB is not scheduled, it is done in "leaveMBB". If you'd always do it here, it seems that duplication could be removed.

lib/Target/SystemZ/SystemZMachineScheduler.h

100

This is dead now, right?

[jonpa]

SystemZ parts updated per review. See inline comments.

lib/Target/SystemZ/SystemZHazardRecognizer.cpp

415

ok

463

ok - updated so that

• EmitInstruction() will recognize that any branch in slot 1 or 2 will end current group (there is at least one instruction already in group).
• emitInstruction() takes a new parameter TakenBranch and makes sure that if true, current decoder group is empty after emission.

lib/Target/SystemZ/SystemZMachineScheduler.cpp

62

There is one subtle change in behavior with this patch, and that is the fact that initPolicy() (via enterRegion()) is never called on an empty MBB. That is why the DoneMBB argument is needed for leaveMBB().

I thought about adding an empty region for an empty MBB so that initPolicy() is always called for each MBB. That didn't quite work still, since the MBB cannot then be retrieved from Begin->getParent(), if Begin == End.

lib/Target/SystemZ/SystemZMachineScheduler.h

100

ah, yes.

[uweigand]

lib/Target/SystemZ/SystemZMachineScheduler.cpp

62

Maybe the common-code interface still isn't quite right then. Should we have an enterMBB() to properly pair with the leaveMBB(), maybe?

[jonpa]

Updated per review.
startBlock() and enterMBB() implemented / added.

[jonpa]

lib/Target/SystemZ/SystemZMachineScheduler.cpp

62

Yes, this seems better.

[uweigand]

Thanks! The SystemZ part now looks very reasonable. Just a couple of final, really just cosmetic comments inline.

I think we still need final approval for the common-code changes, though.

lib/Target/SystemZ/SystemZHazardRecognizer.cpp

435

There doesn't appear to be anything HazardRecognizer-specific left in this routine. Maybe move to the SchedPolicy (and possibly merge with getNextMIToEmit into an "advanceTo" routine with just and "end" argument)?

444

Maybe also move to the SchedPolicy and merge into its sole user? Then we wouldn't have to pass the MBB around.

lib/Target/SystemZ/SystemZMachineScheduler.cpp

62

Agreed. Final question: can't the "advance" now be done in initPolicy, so we're finally rid of this function (and the CurrBegin global)?

62

Is it even ever possible now that LastEmittedMI->getParent() is *not* equal to MBB?

66

Maybe inline into its single user? Only if the result looks simpler ...

76

Maybe use HazardRec here? It is now guaranteed to be the same ...

109

HazardRec again?

[jonpa]

SystemZ parts updated per review.

lib/Target/SystemZ/SystemZHazardRecognizer.cpp

435

Yes :-)

444

Yes, looks better.

Moved the assert that makes sure that we are aware of all terminators into emitInstruction(). The purpose is currently to check that we don't have any terminators that are branches without the isBranch/isReturn flag. It seems that CondTrap is the only example, right now. Perhaps CondTrap could get the isBranch flag instead? Do we want this assert, or could we simply assume that all terminators are branches?

lib/Target/SystemZ/SystemZMachineScheduler.cpp

62

Yes, a terminator in the single predecessor will be emitted and recorded as LastEmittedMI. I tried first to guard the update of LastEmittedMI with this check, but then realized that the HazardRec does not have the MBB member.

62

Yes, indeed :-)

66

Yes, I guess that looks ok.

76

ok

109

done

[uweigand]

OK, the SystemZ parts look good to me now. Thanks!

[jonpa]

ping - waiting for review of the common-code parts.

Matthias: are you happy with the changes I did according to your suggestion to avoid std::reverse?
Andy: Do the comments now look ok?

[jonpa]

ping!

This patch is now only waiting for review of the common-code parts.

[MatzeB]

You may revert the region iterator changes if there is no way to avoid the vector (see below). Either way LGTM.

lib/CodeGen/MachineScheduler.cpp

451

Capitalize parameter names.

451–489

I was thinking about something where we do not store intermediate results in a vector but compute regions on the fly. If it turns out we cannot avoid a vector then your previous approach was fine.
Using something like SmallVector<16> should save some allocations when compiling small functions.

[atrick]

Andy: Do the comments now look ok?

Yes, thanks.

[jonpa]

Updated with change back to SmallVector.

Thanks for review. Committing soon.

[jonpa]

llvm/trunk@311072

lib/CodeGen/MachineScheduler.cpp

451–489

Ah, I see. I am then going back to the previous version since it was simpler, and since I really don't want to get into rewriting the loop that extracts the scheduling regions unless really needed. I also changed to SmallVector.

lib/CodeGen/MachineScheduler.cpp

bool PostMachineScheduler::runOnMachineFunction(MachineFunction &mf) {
   } else if (!mf.getSubtarget().enablePostRAScheduler()) {
     DEBUG(dbgs() << "Subtarget disables post-MI-sched.\n");
     return false;
   }
   DEBUG(dbgs() << "Before post-MI-sched:\n"; mf.print(dbgs()));
 
   // Initialize the context of the pass.
   MF = &mf;
+  MLI = &getAnalysis<MachineLoopInfo>();
   PassConfig = &getAnalysis<TargetPassConfig>();
 
   if (VerifyScheduling)
     MF->verify(this, "Before post machine scheduling.");
 
   // Instantiate the selected scheduler for this target, function, and
   // optimization level.
   std::unique_ptr<ScheduleDAGInstrs> Scheduler(createPostMachineScheduler());

 /// calls this late anyway.
 static bool isSchedBoundary(MachineBasicBlock::iterator MI,
                             MachineBasicBlock *MBB,
                             MachineFunction *MF,
                             const TargetInstrInfo *TII) {
   return MI->isCall() || TII->isSchedulingBoundary(*MI, MBB, *MF);
 }
 
 /// Main driver for both MachineScheduler and PostMachineScheduler.
 void MachineSchedulerBase::scheduleRegions(ScheduleDAGInstrs &Scheduler,
                                            bool FixKillFlags) {
   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
 
   // Visit all machine basic blocks.
   //
   // TODO: Visit blocks in global postorder or postorder within the bottom-up
   // loop tree. Then we can optionally compute global RegPressure.
   for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end();
        MBB != MBBEnd; ++MBB) {
 
     Scheduler.startBlock(&*MBB);
 
 #ifndef NDEBUG
     if (SchedOnlyFunc.getNumOccurrences() && SchedOnlyFunc != MF->getName())
       continue;
     if (SchedOnlyBlock.getNumOccurrences()
         && (int)SchedOnlyBlock != MBB->getNumber())
       continue;
 #endif
 
     // Break the block into scheduling regions [I, RegionEnd), and schedule each
     // region as soon as it is discovered. RegionEnd points the scheduling
     // boundary at the bottom of the region. The DAG does not include RegionEnd,
     // but the region does (i.e. the next RegionEnd is above the previous
     // RegionBegin). If the current block has no terminator then RegionEnd ==
     // MBB->end() for the bottom region.
     //
     // The Scheduler may insert instructions during either schedule() or
     // exitRegion(), even for empty regions. So the local iterators 'I' and
     // 'RegionEnd' are invalid across these calls.
     //
     // MBB::size() uses instr_iterator to count. Here we need a bundle to count
     // as a single instruction.
     for(MachineBasicBlock::iterator RegionEnd = MBB->end();
         RegionEnd != MBB->begin(); RegionEnd = Scheduler.begin()) {
 
       // Avoid decrementing RegionEnd for blocks with no terminator.
       if (RegionEnd != MBB->end() ||
           isSchedBoundary(&*std::prev(RegionEnd), &*MBB, MF, TII)) {
         --RegionEnd;
       }
 
       // The next region starts above the previous region. Look backward in the
       // instruction stream until we find the nearest boundary.
       unsigned NumRegionInstrs = 0;
       MachineBasicBlock::iterator I = RegionEnd;
       for (; I != MBB->begin(); --I) {
         MachineInstr &MI = *std::prev(I);
         if (isSchedBoundary(&MI, &*MBB, MF, TII))
           break;
         if (!MI.isDebugValue())
           ++NumRegionInstrs;
       }
       // Notify the scheduler of the region, even if we may skip scheduling
       // it. Perhaps it still needs to be bundled.

 /// releasePredecessors - Call releasePred on each of SU's predecessors.
 void ScheduleDAGMI::releasePredecessors(SUnit *SU) {
   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
        I != E; ++I) {
     releasePred(SU, &*I);
   }
 }
 
 /// enterRegion - Called back from MachineScheduler::runOnMachineFunction after
 /// crossing a scheduling boundary. [begin, end) includes all instructions in
 /// the region, including the boundary itself and single-instruction regions
 /// that don't get scheduled.
 void ScheduleDAGMI::enterRegion(MachineBasicBlock *bb,
                                      MachineBasicBlock::iterator begin,
                                      MachineBasicBlock::iterator end,
                                      unsigned regioninstrs)
 {
   ScheduleDAGInstrs::enterRegion(bb, begin, end, regioninstrs);
 

lib/Target/SystemZ/SystemZHazardRecognizer.h

 // scheduling candidates. This includes:
 //
 // * Decoder grouping. A decoder group can maximally hold 3 uops, and
 // instructions that always begin a new group should be scheduled when
 // the current decoder group is empty.
 // * Processor resources usage. It is beneficial to balance the use of
 // resources.
 //
+// A goal is to consider all instructions, also those outside of any
+// scheduling region. Such instructions are "advanced" past and include
+// single instructions before a scheduling region, branches etc.
+//
+// A block that has only one predecessor continues scheduling with the state
+// of it (which may be updated by emitting branches).
+//
 // ===---------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_TARGET_SYSTEMZ_SYSTEMZHAZARDRECOGNIZER_H
 #define LLVM_LIB_TARGET_SYSTEMZ_SYSTEMZHAZARDRECOGNIZER_H
 
 #include "SystemZSubtarget.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineScheduler.h"
 #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
 #include "llvm/MC/MCInstrDesc.h"
 #include "llvm/Support/raw_ostream.h"
 #include <string>
 
 namespace llvm {
 
-/// SystemZHazardRecognizer maintains the state during scheduling.
+class SystemZHazardRecognizer;
+typedef std::map<MachineBasicBlock*, SystemZHazardRecognizer*> MBB2HazRec;
+
+/// SystemZHazardRecognizer maintains the state for one MBB during scheduling.
 class SystemZHazardRecognizer : public ScheduleHazardRecognizer {
 
+  // A pointer to the global map of scheduler states.
+  MBB2HazRec *SchedStates;
+
   ScheduleDAGMI *DAG;
-  const TargetSchedModel *SchedModel;
+  const SystemZInstrInfo *TII;
+
+  // A SchedModel is needed before any DAG is built while advancing past
+  // non-scheduled instructions, so it is not always possible to call
+  // DAG->getSchedClass(SU).
+  TargetSchedModel SchedModel;
+
+  // MBB and Loop that this HazardRecognizer will operate in.
+  MachineBasicBlock *MBB;
+  const MachineLoop *Loop;
+
+  // Start of region
+  MachineBasicBlock::iterator Begin;
 
   /// Keep track of the number of decoder slots used in the current
   /// decoder group.
   unsigned CurrGroupSize;
 
   /// The tracking of resources here are quite similar to the common
   /// code use of a critical resource. However, z13 differs in the way
   /// that it has two processor sides which may be interesting to
class SystemZHazardRecognizer : public ScheduleHazardRecognizer {
 
   /// Clear all counters for processor resources.
   void clearProcResCounters();
 
   /// With the goal of alternating processor sides for stalling (FPd)
   /// ops, return true if it seems good to schedule an FPd op next.
   bool isFPdOpPreferred_distance(const SUnit *SU);
 
+  /// Last emitted instruction or nullptr.
+  MachineInstr *LastEmittedMI;
+
+  /// Wrap a non-scheduled instruction in an SU and emit it.
+  void emitInstruction(MachineInstr *MI);
+
+  /// Update the scheduler state by emitting (non-scheduled) instructions
+  /// from I to NextBegin.
+  void advance(MachineBasicBlock::iterator I,
+               MachineBasicBlock::iterator NextBegin);
+
+  /// Emit a branch in a predecessor, and return true if it is a taken branch
+  /// to MBB.
+  bool emitIncomingBranch(MachineInstr *MI);
+
+  /// Take over state and continue scheduling from end of single predecessor.
+  void takeStateFromPred();
+
+  /// LastCall is used as a compile time optimization in leaveMBB() so that
+  /// in the case of a call in MBB, the final state is achieved by looking at
+  /// just instructions after it.
+  MachineBasicBlock::iterator LastCall;
+
 public:
-  SystemZHazardRecognizer(const MachineSchedContext *C);
+  SystemZHazardRecognizer(const TargetSubtargetInfo *ST, MBB2HazRec *SchedS_);
 
-  void setDAG(ScheduleDAGMI *dag) {
-    DAG = dag;
-    SchedModel = dag->getSchedModel();
-  }
-  
+  void enterRegion(MachineBasicBlock *MBB_,
+                   const MachineLoop *Loop_,
+                   MachineBasicBlock::iterator Begin_);
+
+  /// Called just before scheduling begins, with the DAG.
+  void initialize(ScheduleDAGMI *dag);
   HazardType getHazardType(SUnit *m, int Stalls = 0) override;    
   void Reset() override;
   void EmitInstruction(SUnit *SU) override;
 
   // Cost functions used by SystemZPostRASchedStrategy while
   // evaluating candidates.
 
   /// Return the cost of decoder grouping for SU. If SU must start a

 
 #ifndef NDEBUG
   // Debug dumping.
   std::string CurGroupDbg; // current group as text
   void dumpSU(SUnit *SU, raw_ostream &OS) const;
   void dumpCurrGroup(std::string Msg = "") const;
   void dumpProcResourceCounters() const;
 #endif
+
+  /// Remeber the last (bottom-most) call in MBB. This is the Call first
+  /// passed here, since regions are bottom-up in the MBB.
+  void setLastCall(MachineBasicBlock::iterator Call) {
+    if (LastCall == nullptr)
+      LastCall = Call;
+  }
+
+  /// Leave MBB after scheduling is done. This means emiting all instructions
+  /// up to but not including the first terminator.
+  void leaveMBB();
 };
 
 } // namespace llvm
 
 #endif /* LLVM_LIB_TARGET_SYSTEMZ_SYSTEMZHAZARDRECOGNIZER_H */

lib/Target/SystemZ/SystemZHazardRecognizer.cpp

 // scheduling candidates. This includes:
 //
 // * Decoder grouping. A decoder group can maximally hold 3 uops, and
 // instructions that always begin a new group should be scheduled when
 // the current decoder group is empty.
 // * Processor resources usage. It is beneficial to balance the use of
 // resources.
 //
+// A goal is to consider all instructions, also those outside of any
+// scheduling region. Such instructions are "advanced" past and include
+// single instructions before a scheduling region, branches etc.
+//
+// A block that has only one predecessor continues scheduling with the state
+// of it (which may be updated by emitting branches).
+//
 // ===---------------------------------------------------------------------===//
 
 #include "SystemZHazardRecognizer.h"
 #include "llvm/ADT/Statistic.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "misched"
 
 // This is the limit of processor resource usage at which the
 // scheduler should try to look for other instructions (not using the
 // critical resource).
 static cl::opt<int> ProcResCostLim("procres-cost-lim", cl::Hidden,
                                    cl::desc("The OOO window for processor "
                                             "resources during scheduling."),
                                    cl::init(8));
 
 SystemZHazardRecognizer::
-SystemZHazardRecognizer(const MachineSchedContext *C) : DAG(nullptr),
-                                                        SchedModel(nullptr) {}
+SystemZHazardRecognizer(const TargetSubtargetInfo *ST, MBB2HazRec *SchedS_)
+  : SchedStates(SchedS_), DAG(nullptr), TII(nullptr),
+    MBB(nullptr), Loop(nullptr), Begin(nullptr), CurrGroupSize(0),
+    LastFPdOpCycleIdx(UINT_MAX), GrpCount(0), LastEmittedMI(nullptr),
+    LastCall(nullptr) {
+  TII = static_cast<const SystemZInstrInfo *>(ST->getInstrInfo());
+  SchedModel.init(ST->getSchedModel(), ST, TII);
+}
+
+void SystemZHazardRecognizer::enterRegion(MachineBasicBlock *MBB_,
+                                          const MachineLoop *Loop_,
+                                          MachineBasicBlock::iterator Begin_) {
+  Reset();
+  MBB = MBB_;
+  Loop = Loop_;
+  Begin = Begin_;
+}
+
+void SystemZHazardRecognizer::initialize(ScheduleDAGMI *dag) {
+  DAG = dag;
+
+  // There may be non-scheduled instructions before Begin. Look backwards
+  // until beginning of block or a call.
+  MachineBasicBlock::iterator PreRegBegin = Begin;
+  for (; PreRegBegin != MBB->begin(); --PreRegBegin) {
+    if (std::prev(PreRegBegin)->isCall())
+      break;
+  }
+
+  // If this is top-most in MBB, try to take over the state from a single
+  // predecessor.
+  if (PreRegBegin == MBB->begin())
+    takeStateFromPred();
+
+  // Emit any instructions before Begin.
+  advance(PreRegBegin, Begin);
+}
 
 unsigned SystemZHazardRecognizer::
 getNumDecoderSlots(SUnit *SU) const {
-  const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
+  const MCSchedClassDesc *SC = SchedModel.resolveSchedClass(SU->getInstr());
   if (!SC->isValid())
     return 0; // IMPLICIT_DEF / KILL -- will not make impact in output.
 
   if (SC->BeginGroup) {
     if (!SC->EndGroup)
       return 2; // Cracked instruction
     else
       return 3; // Expanded/group-alone instruction

 }
 
 ScheduleHazardRecognizer::HazardType SystemZHazardRecognizer::
 getHazardType(SUnit *m, int Stalls) {
   return (fitsIntoCurrentGroup(m) ? NoHazard : Hazard);
 }
 
 void SystemZHazardRecognizer::Reset() {
+  DAG = nullptr;
+  MBB = nullptr;
+  Loop = nullptr;
+  Begin = nullptr;
   CurrGroupSize = 0;
   clearProcResCounters();
   GrpCount = 0;
   LastFPdOpCycleIdx = UINT_MAX;
+  LastEmittedMI = nullptr;
+  LastCall = nullptr;
   DEBUG(CurGroupDbg = "";);
 }
 
 bool
 SystemZHazardRecognizer::fitsIntoCurrentGroup(SUnit *SU) const {
-  const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
+  const MCSchedClassDesc *SC = SchedModel.resolveSchedClass(SU->getInstr());
   if (!SC->isValid())
     return true;
 
   // A cracked instruction only fits into schedule if the current
   // group is empty.
   if (SC->BeginGroup)
     return (CurrGroupSize == 0);
 
if (CurrGroupSize > 0) {
     DEBUG(CurGroupDbg = "";);
 
     GrpCount++;
 
     // Reset counter for next group.
     CurrGroupSize = 0;
 
     // Decrease counters for execution units by one.
-    for (unsigned i = 0; i < SchedModel->getNumProcResourceKinds(); ++i)
+    for (unsigned i = 0; i < SchedModel.getNumProcResourceKinds(); ++i)
       if (ProcResourceCounters[i] > 0)
         ProcResourceCounters[i]--;
 
     // Clear CriticalResourceIdx if it is now below the threshold.
     if (CriticalResourceIdx != UINT_MAX &&
         (ProcResourceCounters[CriticalResourceIdx] <=
          ProcResCostLim))
       CriticalResourceIdx = UINT_MAX;
   }
 
   DEBUG(if (DbgOutput)
           dumpProcResourceCounters(););
 }
 
 #ifndef NDEBUG // Debug output
 void SystemZHazardRecognizer::dumpSU(SUnit *SU, raw_ostream &OS) const {
   OS << "SU(" << SU->NodeNum << "):";
-  OS << SchedModel->getInstrInfo()->getName(SU->getInstr()->getOpcode());
+  OS << TII->getName(SU->getInstr()->getOpcode());
 
-  const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
+  const MCSchedClassDesc *SC = SchedModel.resolveSchedClass(SU->getInstr());
   if (!SC->isValid())
     return;
   
   for (TargetSchedModel::ProcResIter
-         PI = SchedModel->getWriteProcResBegin(SC),
-         PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
+         PI = SchedModel.getWriteProcResBegin(SC),
+         PE = SchedModel.getWriteProcResEnd(SC); PI != PE; ++PI) {
     const MCProcResourceDesc &PRD =
-      *SchedModel->getProcResource(PI->ProcResourceIdx);
+      *SchedModel.getProcResource(PI->ProcResourceIdx);
     std::string FU(PRD.Name);
     // trim e.g. Z13_FXaUnit -> FXa
     FU = FU.substr(FU.find("_") + 1);
     FU.resize(FU.find("Unit"));
     OS << "/" << FU;
 
     if (PI->Cycles > 1)
       OS << "(" << PI->Cycles << "cyc)";
dbgs() << " (" << CurrGroupSize << " decoder slot"
            << (CurrGroupSize > 1 ? "s":"")
            << ")\n";
   }
 }
 
 void SystemZHazardRecognizer::dumpProcResourceCounters() const {
   bool any = false;
 
-  for (unsigned i = 0; i < SchedModel->getNumProcResourceKinds(); ++i)
+  for (unsigned i = 0; i < SchedModel.getNumProcResourceKinds(); ++i)
     if (ProcResourceCounters[i] > 0) {
       any = true;
       break;
     }
 
   if (!any)
     return;
 
   dbgs() << "+++ Resource counters:\n";
-  for (unsigned i = 0; i < SchedModel->getNumProcResourceKinds(); ++i)
+  for (unsigned i = 0; i < SchedModel.getNumProcResourceKinds(); ++i)
     if (ProcResourceCounters[i] > 0) {
       dbgs() << "+++ Extra schedule for execution unit "
-             << SchedModel->getProcResource(i)->Name
+             << SchedModel.getProcResource(i)->Name
              << ": " << ProcResourceCounters[i] << "\n";
       any = true;
     }
 }
 #endif //NDEBUG
 
 void SystemZHazardRecognizer::clearProcResCounters() {
-  ProcResourceCounters.assign(SchedModel->getNumProcResourceKinds(), 0);
+  ProcResourceCounters.assign(SchedModel.getNumProcResourceKinds(), 0);
   CriticalResourceIdx = UINT_MAX;
 }
 
 // Update state with SU as the next scheduled unit.
 void SystemZHazardRecognizer::
 EmitInstruction(SUnit *SU) {
-  const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
+  const MCSchedClassDesc *SC = SchedModel.resolveSchedClass(SU->getInstr());
   DEBUG( dumpCurrGroup("Decode group before emission"););
 
   // If scheduling an SU that must begin a new decoder group, move on
   // to next group.
   if (!fitsIntoCurrentGroup(SU))
     nextGroup();
 
   DEBUG( dbgs() << "+++ HazardRecognizer emitting "; dumpSU(SU, dbgs());
          dbgs() << "\n";
          raw_string_ostream cgd(CurGroupDbg);
          if (CurGroupDbg.length())
            cgd << ", ";
          dumpSU(SU, cgd););
 
+  LastEmittedMI = SU->getInstr();
+
   // After returning from a call, we don't know much about the state.
-  if (SU->getInstr()->isCall()) {
+  if (SU->isCall) {
     DEBUG (dbgs() << "+++ Clearing state after call.\n";);
     clearProcResCounters();
     LastFPdOpCycleIdx = UINT_MAX;
     CurrGroupSize += getNumDecoderSlots(SU);
     assert (CurrGroupSize <= 3);
     nextGroup();
     return;
   }
 
   // Increase counter for execution unit(s).
   for (TargetSchedModel::ProcResIter
-         PI = SchedModel->getWriteProcResBegin(SC),
-         PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
+         PI = SchedModel.getWriteProcResBegin(SC),
+         PE = SchedModel.getWriteProcResEnd(SC); PI != PE; ++PI) {
     // Don't handle FPd together with the other resources.
-    if (SchedModel->getProcResource(PI->ProcResourceIdx)->BufferSize == 1)
+    if (SchedModel.getProcResource(PI->ProcResourceIdx)->BufferSize == 1)
       continue;
     int &CurrCounter =
       ProcResourceCounters[PI->ProcResourceIdx];
     CurrCounter += PI->Cycles;
     // Check if this is now the new critical resource.
     if ((CurrCounter > ProcResCostLim) &&
         (CriticalResourceIdx == UINT_MAX ||
          (PI->ProcResourceIdx != CriticalResourceIdx &&
           CurrCounter >
           ProcResourceCounters[CriticalResourceIdx]))) {
       DEBUG( dbgs() << "+++ New critical resource: "
-             << SchedModel->getProcResource(PI->ProcResourceIdx)->Name
+             << SchedModel.getProcResource(PI->ProcResourceIdx)->Name
              << "\n";);
       CriticalResourceIdx = PI->ProcResourceIdx;
     }
   }
 
   // Make note of an instruction that uses a blocking resource (FPd).
   if (SU->isUnbuffered) {
     LastFPdOpCycleIdx = getCurrCycleIdx();
     DEBUG (dbgs() << "+++ Last FPd cycle index: "
            << LastFPdOpCycleIdx << "\n";);
   }
 
   // Insert SU into current group by increasing number of slots used
   // in current group.
   CurrGroupSize += getNumDecoderSlots(SU);
   assert (CurrGroupSize <= 3);
 
   // Check if current group is now full/ended. If so, move on to next
   // group to be ready to evaluate more candidates.
   if (CurrGroupSize == 3 || SC->EndGroup)
     nextGroup();
 }
 
 int SystemZHazardRecognizer::groupingCost(SUnit *SU) const {
-  const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
+  const MCSchedClassDesc *SC = SchedModel.resolveSchedClass(SU->getInstr());
   if (!SC->isValid())
     return 0;
   
   // If SU begins new group, it can either break a current group early
   // or fit naturally if current group is empty (negative cost).
   if (SC->BeginGroup) {
     if (CurrGroupSize)
       return 3 - CurrGroupSize;
if (LastFPdOpCycleIdx > getCurrCycleIdx())
     return ((LastFPdOpCycleIdx - getCurrCycleIdx()) == 3);
   return ((getCurrCycleIdx() - LastFPdOpCycleIdx) == 3);
 }
 
 int SystemZHazardRecognizer::
 resourcesCost(SUnit *SU) {
   int Cost = 0;
 
-  const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
+  const MCSchedClassDesc *SC = SchedModel.resolveSchedClass(SU->getInstr());
   if (!SC->isValid())
     return 0;
 
   // For a FPd op, either return min or max value as indicated by the
   // distance to any prior FPd op.
   if (SU->isUnbuffered)
     Cost = (isFPdOpPreferred_distance(SU) ? INT_MIN : INT_MAX);
   // For other instructions, give a cost to the use of the critical resource.
   else if (CriticalResourceIdx != UINT_MAX) {
     for (TargetSchedModel::ProcResIter
-           PI = SchedModel->getWriteProcResBegin(SC),
-           PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI)
+           PI = SchedModel.getWriteProcResBegin(SC),
+           PE = SchedModel.getWriteProcResEnd(SC); PI != PE; ++PI)
       if (PI->ProcResourceIdx == CriticalResourceIdx)
         Cost = PI->Cycles;
   }
 
   return Cost;
 }
 
+void SystemZHazardRecognizer::emitInstruction(MachineInstr *MI) {
+  // Make a temporary SUnit.
+  SUnit SU(MI, 0);
+
+  // Set interesting flags.
+  SU.isCall = MI->isCall();
+
+  const MCSchedClassDesc *SC = SchedModel.resolveSchedClass(MI);
+  for (const MCWriteProcResEntry &PRE :
+         make_range(SchedModel.getWriteProcResBegin(SC),
+                    SchedModel.getWriteProcResEnd(SC))) {
+    switch (SchedModel.getProcResource(PRE.ProcResourceIdx)->BufferSize) {
+    case 0:
+      SU.hasReservedResource = true;
+      break;
+    case 1:
+      SU.isUnbuffered = true;
+      break;
+    default:
+      break;
+    }
+  }
+
+  EmitInstruction(&SU);
+}
+
+void SystemZHazardRecognizer::
+advance(MachineBasicBlock::iterator I,
+        MachineBasicBlock::iterator NextBegin) {
+  for (; I != NextBegin; ++I) {
+    if (I->isPosition() || I->isDebugValue())
+      continue;
+    emitInstruction(&*I);
+  }
+}
+
+bool SystemZHazardRecognizer::emitIncomingBranch(MachineInstr *MI) {
+  DEBUG (dbgs() << "+++ Emitting incoming branch: "; MI->dump(););
+
+  emitInstruction(MI);
+
+  if (MI->isBranch() &&
+      (TII->getBranchInfo(*MI).Target->isReg() || // Relative branch
+       TII->getBranchInfo(*MI).Target->getMBB() == MBB)) {
+    // Taken branch from predecessor
+    if (CurrGroupSize > 0)
+      nextGroup(false /*DbgOutput*/);
+    return true;
+  }
+
+  assert ((MI->isBranch() || MI->isReturn() ||
+           MI->getOpcode() == SystemZ::CondTrap) &&
+          "Scheduler: expected a branch or conditional return/trap");
+
+  // NT branches end group after first decoder slot.
+  if (CurrGroupSize == 2)
+    nextGroup(false /*DbgOutput*/);
+
+  return false;
+}
+
+// Try to find a single predecessor that would be interesting for the
+// scheduler in the top-most region of MBB.
+static MachineBasicBlock *getSingleSchedPred(MachineBasicBlock *MBB,
+                                             const MachineLoop *Loop) {
+  if (MBB->pred_size() == 1)
+    return *MBB->pred_begin();
+
+  // The loop header has two predecessors, return the latch, but not for a
+  // single block loop.
+  if (MBB->pred_size() == 2 && Loop != nullptr && Loop->getHeader() == MBB) {
+    for (auto I = MBB->pred_begin(); I != MBB->pred_end(); ++I)
+      if (Loop->contains(*I))
+        return (*I == MBB ? nullptr : *I);
+  }
+
+  return nullptr;
+}
+
+void SystemZHazardRecognizer::
+takeStateFromPred() {
+  // Take state from single predecessor MBB, if it has been scheduled.
+  MachineBasicBlock *SinglePredMBB = getSingleSchedPred(MBB, Loop);
+  assert (!SinglePredMBB || !Loop || Loop->contains(SinglePredMBB));
+  if (SinglePredMBB == nullptr ||
+      SchedStates->find(SinglePredMBB) == SchedStates->end())
+    return;
+
+  // Be optimistic and assume that branch prediction will generally do "the
+  // right thing".
+
+  // Get incoming scheduler state.
+  SystemZHazardRecognizer *incoming = (*SchedStates)[SinglePredMBB];
+  DEBUG (dbgs() << "+++ Continued scheduling from MBB#"
+         << incoming->MBB->getNumber() << "\n";);
+
+  // Current decoder group
+  CurrGroupSize = incoming->CurrGroupSize;
+  DEBUG (CurGroupDbg = incoming->CurGroupDbg;);
+
+  // Processor resources
+  ProcResourceCounters = incoming->ProcResourceCounters;
+  CriticalResourceIdx = incoming->CriticalResourceIdx;
+
+  // FPd
+  LastFPdOpCycleIdx = incoming->LastFPdOpCycleIdx;
+  GrpCount = incoming->GrpCount;
+
+  // Emit incoming terminator(s).
+  for (MachineBasicBlock::iterator I = incoming->MBB->getFirstTerminator();
+       I != incoming->MBB->end(); I++)
+    if (emitIncomingBranch(&*I))
+      break;
+}
+
+void SystemZHazardRecognizer::leaveMBB() {
+  DAG = nullptr;
+
+  MachineBasicBlock::iterator I;
+  if (LastEmittedMI != nullptr)
+    // If scheduling was done, emit everything after the region.
+    I = std::next(MachineBasicBlock::iterator(LastEmittedMI));
+  else if (LastCall != nullptr)
+    // Otherwise, emit everything after the last call in MBB, if there is
+    // one.
+    I = std::next(MachineBasicBlock::iterator(LastCall));
+  else {
+    // Get the correct final state by emitting the whole MBB.
+    takeStateFromPred();
+    I = MBB->begin();
+  }
+
+  // Advance to first terminator. The successor block will handle them in
+  // takeStateFromPred().
+  advance(I, MBB->getFirstTerminator());
+}
+

lib/Target/SystemZ/SystemZMachineScheduler.h

 //==- SystemZMachineScheduler.h - SystemZ Scheduler Interface ----*- C++ -*-==//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // -------------------------- Post RA scheduling ---------------------------- //
 // SystemZPostRASchedStrategy is a scheduling strategy which is plugged into
 // the MachineScheduler. It has a sorted Available set of SUs and a pickNode()
 // implementation that looks to optimize decoder grouping and balance the
-// usage of processor resources.
-//===----------------------------------------------------------------------===//
+// usage of processor resources. Scheduler states are saved for the end
+// region of each MBB, so that a successor block can learn from it.
+// ===----------------------------------------------------------------------===//
 
 #include "SystemZHazardRecognizer.h"
 #include "llvm/CodeGen/MachineScheduler.h"
 #include "llvm/CodeGen/ScheduleDAG.h"
 #include <set>
 
 #ifndef LLVM_LIB_TARGET_SYSTEMZ_SYSTEMZMACHINESCHEDULER_H
 #define LLVM_LIB_TARGET_SYSTEMZ_SYSTEMZMACHINESCHEDULER_H
struct SUSet : std::set<SUnit*, SUSorter> {
     #ifndef NDEBUG
     void dump(SystemZHazardRecognizer &HazardRec);
     #endif
   };
 
   /// The set of available SUs to schedule next.
   SUSet Available;
 
-  // HazardRecognizer that tracks the scheduler state for the current
-  // region.
-  SystemZHazardRecognizer HazardRec;
-  
+  /// Maintain hazard recognizers for all blocks, so that the scheduler state
+  /// can be maintained past BB boundaries when appropariate.
+  MBB2HazRec SchedStates;
+
+  /// Pointer to the HazardRecognizer that tracks the scheduler state for
+  /// the current region.
+  SystemZHazardRecognizer *HazardRec;
+
+  /// A temporary HazardRecognizer used for regions that are separated (by a
+  /// call) from the bottom-most region of the MBB.
+  SystemZHazardRecognizer TmpHazRec;
+
+  /// Since there is no virtual leaveRegion() method, use a pointer to check
+  /// when scheduler has changed MBB, so that leaveMBB() can be called for
+  /// the previous MBB.
+  MachineBasicBlock *PreviouslyVisitedMBB;
+
+  /// Loops are checked so that headers can be identified in
+  /// takeStateFromPred().
+  const MachineLoopInfo *MLI;
 public:
   SystemZPostRASchedStrategy(const MachineSchedContext *C);
+  virtual ~SystemZPostRASchedStrategy();
+
+  /// Called for a region before scheduling.
+  void initPolicy(MachineBasicBlock::iterator Begin,
+                  MachineBasicBlock::iterator End,
+                  unsigned NumRegionInstrs) override;
 
   /// PostRA scheduling does not track pressure.
   bool shouldTrackPressure() const override { return false; }
 
   /// Initialize the strategy after building the DAG for a new region.
   void initialize(ScheduleDAGMI *dag) override;
 
   /// Pick the next node to schedule, or return NULL.

lib/Target/SystemZ/SystemZMachineScheduler.cpp

 //-- SystemZMachineScheduler.cpp - SystemZ Scheduler Interface -*- C++ -*---==//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // -------------------------- Post RA scheduling ---------------------------- //
 // SystemZPostRASchedStrategy is a scheduling strategy which is plugged into
 // the MachineScheduler. It has a sorted Available set of SUs and a pickNode()
 // implementation that looks to optimize decoder grouping and balance the
-// usage of processor resources.
-//===----------------------------------------------------------------------===//
+// usage of processor resources. Scheduler states are saved for the end
+// region of each MBB, so that a successor block can learn from it.
+// ===----------------------------------------------------------------------===//
 
 #include "SystemZMachineScheduler.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "misched"
 
 #ifndef NDEBUG
 // Print the set of SUs
 void SystemZPostRASchedStrategy::SUSet::
 dump(SystemZHazardRecognizer &HazardRec) {
   dbgs() << "{";
   for (auto &SU : *this) {
     HazardRec.dumpSU(SU, dbgs());
     if (SU != *rbegin())
       dbgs() << ",  ";
   }
   dbgs() << "}\n";
 }
 #endif
 
 SystemZPostRASchedStrategy::
 SystemZPostRASchedStrategy(const MachineSchedContext *C)
-  : DAG(nullptr), HazardRec(C) {}
+  : DAG(nullptr), HazardRec(nullptr),
+    TmpHazRec(&C->MF->getSubtarget(), &SchedStates),
+    PreviouslyVisitedMBB(nullptr), MLI(C->MLI) {}
+
+SystemZPostRASchedStrategy::~SystemZPostRASchedStrategy() {
+  // Delete hazard recognizers kept around for each MBB.
+  for (auto I : SchedStates) {
+    SystemZHazardRecognizer *hazrec = I.second;
+    delete hazrec;
+  }
+}
+
+void SystemZPostRASchedStrategy::initPolicy(MachineBasicBlock::iterator Begin,
+                                            MachineBasicBlock::iterator End,
+                                            unsigned NumRegionInstrs) {
+  MachineBasicBlock *MBB = Begin->getParent();
+  const MachineLoop *Loop = MLI->getLoopFor(MBB);
+
+  // If a new MBB has been entered, finalize the previous MBB.
+  if (PreviouslyVisitedMBB != nullptr && PreviouslyVisitedMBB != MBB)
+    SchedStates.find(PreviouslyVisitedMBB)->second->leaveMBB();
+  PreviouslyVisitedMBB = MBB;
+
+  // We can maintain the scheder state perfectly even when scheduling regions
+  // in reverse order (bottom-up) in MBB, because the only scheduling
+  // boundaries we have are calls, which simply reset the state.
+  if (SchedStates.find(MBB) != SchedStates.end()) {
+    // Use the temporary HazardRecognizer for any regions above calls.
+    DEBUG (dbgs() << "+++ Continuing in MBB#" << MBB->getNumber());
+    HazardRec = &TmpHazRec;
+  } else {
+    // First time in MBB is the bottom-most region. Make a new
+    // HazardRecognizer and save it for use by successor block.
+    DEBUG (dbgs() << "+++ Entering MBB#" << MBB->getNumber());
+    HazardRec = new SystemZHazardRecognizer(&MBB->getParent()->getSubtarget(),
+                                            &SchedStates);
+    SchedStates[MBB] = HazardRec;
+  }
+
+  DEBUG (if(Loop && Loop->getHeader() == MBB)
+           dbgs() << " (Loop header)";
+         dbgs() << ":\n";);
+
+  if (End != MBB->end() && End->isCall())
+    SchedStates[MBB]->setLastCall(End);
+
+  HazardRec->enterRegion(MBB, Loop, Begin);
+}
 
 void SystemZPostRASchedStrategy::initialize(ScheduleDAGMI *dag) {
   DAG = dag;
-  HazardRec.setDAG(dag);
-  HazardRec.Reset();
+  HazardRec->initialize(dag);
 }
 
 // Pick the next node to schedule.
 SUnit *SystemZPostRASchedStrategy::pickNode(bool &IsTopNode) {
   // Only scheduling top-down.
   IsTopNode = true;
 
   if (Available.empty())
     return nullptr;
 
   // If only one choice, return it.
   if (Available.size() == 1) {
     DEBUG (dbgs() << "+++ Only one: ";
-           HazardRec.dumpSU(*Available.begin(), dbgs()); dbgs() << "\n";);
+           HazardRec->dumpSU(*Available.begin(), dbgs()); dbgs() << "\n";);
     return *Available.begin();
   }
 
   // All nodes that are possible to schedule are stored by in the
   // Available set.
-  DEBUG(dbgs() << "+++ Available: "; Available.dump(HazardRec););
+  DEBUG(dbgs() << "+++ Available: "; Available.dump(*HazardRec););
 
   Candidate Best;
   for (auto *SU : Available) {
 
     // SU is the next candidate to be compared against current Best.
-    Candidate c(SU, HazardRec);
+    Candidate c(SU, *HazardRec);
 
     // Remeber which SU is the best candidate.
     if (Best.SU == nullptr || c < Best) {
       Best = c;
       DEBUG(dbgs() << "+++ Best sofar: ";
-            HazardRec.dumpSU(Best.SU, dbgs());
+            HazardRec->dumpSU(Best.SU, dbgs());
             if (Best.GroupingCost != 0)
               dbgs() << "\tGrouping cost:" << Best.GroupingCost;
             if (Best.ResourcesCost != 0)
               dbgs() << " Resource cost:" << Best.ResourcesCost;
             dbgs() << " Height:" << Best.SU->getHeight();
             dbgs() << "\n";);
     }
 
operator<(const Candidate &other) {
   return false;
 }
 
 void SystemZPostRASchedStrategy::schedNode(SUnit *SU, bool IsTopNode) {
   DEBUG(dbgs() << "+++ Scheduling SU(" << SU->NodeNum << ")\n";);
 
   // Remove SU from Available set and update HazardRec.
   Available.erase(SU);
-  HazardRec.EmitInstruction(SU);
+  HazardRec->EmitInstruction(SU);
 }
 
 void SystemZPostRASchedStrategy::releaseTopNode(SUnit *SU) {
   // Set isScheduleHigh flag on all SUs that we want to consider first in
   // pickNode().
   const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
   bool AffectsGrouping = (SC->isValid() && (SC->BeginGroup || SC->EndGroup));
   SU->isScheduleHigh = (AffectsGrouping || SU->isUnbuffered);
 
   // Put all released SUs in the Available set.
   Available.insert(SU);
 }

test/CodeGen/SystemZ/int-cmp-48.ll

exit:
   ret void
 }
 
 
 ; Check that we do not fold across an aliasing store.
 define void @f2(i8 *%src) {
 ; CHECK-LABEL: f2:
 ; CHECK: llc [[REG:%r[0-5]]], 0(%r2)
-; CHECK: tmll [[REG]], 1
-; CHECK: mvi 0(%r2), 0
+; CHECK-DAG: mvi 0(%r2), 0
+; CHECK-DAG: tmll [[REG]], 1
 ; CHECK: ber %r14
 ; CHECK: br %r14
 entry:
   %byte = load i8 , i8 *%src
   store i8 0, i8 *%src
   %and = and i8 %byte, 1
   %cmp = icmp eq i8 %and, 0
   br i1 %cmp, label %exit, label %store