[MachineScheduler] Add a flag to enable scheduling of cfi instructions

[tellenbach]

Summary

Add a flag --schedule-cfiinstrs to enable the scheduling of cfi
instructions during instruction scheduling.

If this flag is set to false (the current default) cfi instructions
act as scheduling boundaries during instruction scheduling. This can
lead to different scheduling regions and therefore differing generated
assembly, depending on the presence of cfi instructions.

Since some targets insert cfi instructions when debug information is
generated, but not if not, the scheduling of cfi instructions leads to
improved consistency between debug and non-debug mode.

See also: http://lists.llvm.org/pipermail/llvm-dev/2019-September/135433.html

This resolves PR37240.

[fhahn]

I've not looked to closely yet, but isn't that basically the same we do for debug values? If that's the case, I think we should consider unifying the code to handle debug & CFI. Specifically, would it be possible to just extend the current handling of debug instructions to also handle CFI instructions? That should some renaming and a few code changes. I think.

llvm/lib/CodeGen/MachineScheduler.cpp

453

Can that be folded into the return, like the other conditions? Also, please update the comment with details about CFIInstructions.

[tellenbach]

In D68639#1699548, @fhahn wrote:

I've not looked to closely yet, but isn't that basically the same we do for debug values? If that's the case, I think we should consider unifying the code to handle debug & CFI. Specifically, would it be possible to just extend the current handling of debug instructions to also handle CFI instructions? That should some renaming and a few code changes. I think.

You are absolutely correct, this is essentially the same as for debug values with the addition that it can be disabled. I will try to unify both approaches, maybe both loops (currently one for the vector of debug values and one for the vector of cfi instructions) can be fused into one.

[fhahn]

In D68639#1699596, @tellenbach wrote:

In D68639#1699548, @fhahn wrote:

I've not looked to closely yet, but isn't that basically the same we do for debug values? If that's the case, I think we should consider unifying the code to handle debug & CFI. Specifically, would it be possible to just extend the current handling of debug instructions to also handle CFI instructions? That should some renaming and a few code changes. I think.

You are absolutely correct, this is essentially the same as for debug values with the addition that it can be disabled. I will try to unify both approaches, maybe both loops (currently one for the vector of debug values and one for the vector of cfi instructions) can be fused into one.

I think we could just use the same map for both debug and CFI instructions and then just rename placeDebugInstruction to something like placeUnscheduledInstructions.

[tellenbach]

Move test for scheduling boundaries into return statement

[probinson]

llvm/lib/CodeGen/MachineScheduler.cpp

445

"If <something>, <they> act as scheduling boundaries, otherwise they do." There seems to be a "not" missing somewhere.

llvm/lib/CodeGen/ScheduleDAGInstrs.cpp

825

I realize you are planning to rework this to handle CFI and DBG instructions more in the same way. But the tests don't appear to exercise the case of having a mix of CFI and DBG instructions, and I am not sure the current code will correctly handle all cases where CFI and DBG instructions are adjacent.

[tellenbach]

Thanks for your comments. Since I don't think changing instruction scheduling can fix the problem anymore I abandon this revision.

See also: http://lists.llvm.org/pipermail/llvm-dev/2019-October/135813.html

llvm/include/llvm/CodeGen/MachineScheduler.h

protected:
   void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots);
 
   /// Update scheduler DAG and queues after scheduling an instruction.
   void updateQueues(SUnit *SU, bool IsTopNode);
 
   /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
   void placeDebugValues();
 
+  /// Reinsert cfi instructions recorded in ScheduleDAGInstrs::CFIInstructions.
+  void placeCFIInstructions();
+
   /// dump the scheduled Sequence.
   void dumpSchedule() const;
 
   // Lesser helpers...
   bool checkSchedLimit();
 
   void findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots,
                              SmallVectorImpl<SUnit*> &BotRoots);

llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h

 #include <cassert>
 #include <cstdint>
 #include <list>
 #include <utility>
 #include <vector>
 
 namespace llvm {
 
-  class LiveIntervals;
-  class MachineFrameInfo;
-  class MachineFunction;
-  class MachineInstr;
-  class MachineLoopInfo;
-  class MachineOperand;
-  struct MCSchedClassDesc;
-  class PressureDiffs;
-  class PseudoSourceValue;
-  class RegPressureTracker;
-  class UndefValue;
-  class Value;
+extern cl::opt<bool> CFIInstructionScheduling;
+
 
-  /// An individual mapping from virtual register number to SUnit.
-  struct VReg2SUnit {
-    unsigned VirtReg;
-    LaneBitmask LaneMask;
-    SUnit *SU;
 
-    VReg2SUnit(unsigned VReg, LaneBitmask LaneMask, SUnit *SU)
       : VirtReg(VReg), LaneMask(LaneMask), SU(SU) {}
 
-    unsigned getSparseSetIndex() const {
-      return Register::virtReg2Index(VirtReg);
-    }
-  };
 
   /// Mapping from virtual register to SUnit including an operand index.
   struct VReg2SUnitOperIdx : public VReg2SUnit {
     unsigned OperandIndex;
 
     VReg2SUnitOperIdx(unsigned VReg, LaneBitmask LaneMask,
                       unsigned OperandIndex, SUnit *SU)
       : VReg2SUnit(VReg, LaneMask, SU), OperandIndex(OperandIndex) {}
protected:
     using DbgValueVector =
         std::vector<std::pair<MachineInstr *, MachineInstr *>>;
     /// Remember instruction that precedes DBG_VALUE.
     /// These are generated by buildSchedGraph but persist so they can be
     /// referenced when emitting the final schedule.
     DbgValueVector DbgValues;
     MachineInstr *FirstDbgValue = nullptr;
 
+    /// When building the ScheduleDAG we remember which instructions precede
+    /// CFI_INSTRUCTION to emit them at the correct position in the final
+    /// schedule
+    using CFIInstructionVector =
+        std::vector<std::pair<MachineInstr *, MachineInstr *>>;
+    CFIInstructionVector CFIInstructions;
+
     /// Set of live physical registers for updating kill flags.
     LivePhysRegs LiveRegs;
 
   public:
     explicit ScheduleDAGInstrs(MachineFunction &mf,
                                const MachineLoopInfo *mli,
                                bool RemoveKillFlags = false);
 

llvm/lib/CodeGen/MachineScheduler.cpp

 cl::opt<bool>
 DumpCriticalPathLength("misched-dcpl", cl::Hidden,
                        cl::desc("Print critical path length to stdout"));
 
 cl::opt<bool> VerifyScheduling(
     "verify-misched", cl::Hidden,
     cl::desc("Verify machine instrs before and after machine scheduling"));
 
+cl::opt<bool> CFIInstructionScheduling(
+    "schedule-cfiinstrs", cl::Hidden, cl::init(false),
+    cl::desc(
+        "Enable scheduling of CFI instructions during machine scheduling"));
 } // end namespace llvm
 
 #ifndef NDEBUG
 static cl::opt<bool> ViewMISchedDAGs("view-misched-dags", cl::Hidden,
   cl::desc("Pop up a window to show MISched dags after they are processed"));
 
 /// In some situations a few uninteresting nodes depend on nearly all other
 /// nodes in the graph, provide a cutoff to hide them.

 ///
 /// MachineScheduler does not currently support scheduling across calls. To
 /// handle calls, the DAG builder needs to be modified to create register
 /// anti/output dependencies on the registers clobbered by the call's regmask
 /// operand. In PreRA scheduling, the stack pointer adjustment already prevents
 /// scheduling across calls. In PostRA scheduling, we need the isCall to enforce
 /// the boundary, but there would be no benefit to postRA scheduling across
 /// calls this late anyway.
+///
+/// If the option CFIInstructionScheduling is not set, cfi instructions act as
+/// scheduling boundaries, otherwise they do. This allows to schedule cfi
+/// instructions.
 static bool isSchedBoundary(MachineBasicBlock::iterator MI,
                             MachineBasicBlock *MBB,
                             MachineFunction *MF,
                             const TargetInstrInfo *TII) {
-  return MI->isCall() || TII->isSchedulingBoundary(*MI, MBB, *MF);
+  return MI->isCall() ||
+         (!MI->isCFIInstruction() &&
+          TII->isSchedulingBoundary(*MI, MBB, *MF)) ||
+         (MI->isCFIInstruction() && !CFIInstructionScheduling);
 }
 
 /// A region of an MBB for scheduling.
 namespace {
 struct SchedRegion {
   /// RegionBegin is the first instruction in the scheduling region, and
   /// RegionEnd is either MBB->end() or the scheduling boundary after the
   /// last instruction in the scheduling region. These iterators cannot refer
while (true) {
     // runs, it can then use the accurate ReadyCycle time to determine whether
     // newly released nodes can move to the readyQ.
     SchedImpl->schedNode(SU, IsTopNode);
 
     updateQueues(SU, IsTopNode);
   }
   assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
 
+  placeCFIInstructions();
+
   placeDebugValues();
 
   LLVM_DEBUG({
     dbgs() << "*** Final schedule for "
            << printMBBReference(*begin()->getParent()) << " ***\n";
     dumpSchedule();
     dbgs() << '\n';
   });
for (std::vector<std::pair<MachineInstr *, MachineInstr *>>::iterator
     BB->splice(++OrigPrevMI, BB, DbgValue);
     if (OrigPrevMI == std::prev(RegionEnd))
       RegionEnd = DbgValue;
   }
   DbgValues.clear();
   FirstDbgValue = nullptr;
 }
 
+void ScheduleDAGMI::placeCFIInstructions() {
+  // If cfi instructions don't get scheduled, CFIInstructions should be empty
+  assert((CFIInstructionScheduling || CFIInstructions.empty()) &&
+         "Scheduling of CFI instructions is not enabled");
+
+  for (CFIInstructionVector::iterator CFII = CFIInstructions.end(),
+                                      CFIE = CFIInstructions.begin();
+       CFII != CFIE; --CFII) {
+    std::pair<MachineInstr *, MachineInstr *> Prev = *std::prev(CFII);
+    MachineInstr *CFIInstr = Prev.first;
+    MachineBasicBlock::iterator OrigPrevMI = Prev.second;
+    if (&*RegionBegin == CFIInstr) {
+      ++RegionBegin;
+    }
+    BB->splice(++OrigPrevMI, BB, CFIInstr);
+    if (OrigPrevMI == std::prev(RegionEnd)) {
+      RegionEnd = CFIInstr;
+    }
+  }
+  CFIInstructions.clear();
+}
+
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void ScheduleDAGMI::dumpSchedule() const {
   for (MachineBasicBlock::iterator MI = begin(), ME = end(); MI != ME; ++MI) {
     if (SUnit *SU = getSUnit(&(*MI)))
       dumpNode(*SU);
     else
       dbgs() << "Missing SUnit\n";
   }
while (true) {
     SchedImpl->schedNode(SU, IsTopNode);
 
     updateQueues(SU, IsTopNode);
   }
   assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
 
   placeDebugValues();
 
+  placeCFIInstructions();
+
   LLVM_DEBUG({
     dbgs() << "*** Final schedule for "
            << printMBBReference(*begin()->getParent()) << " ***\n";
     dumpSchedule();
     dbgs() << '\n';
   });
 }
 

llvm/lib/CodeGen/ScheduleDAGInstrs.cpp

void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA,
   // convenience.
   Value2SUsMap FPExceptions;
 
   // Remove any stale debug info; sometimes BuildSchedGraph is called again
   // without emitting the info from the previous call.
   DbgValues.clear();
   FirstDbgValue = nullptr;
 
+  CFIInstructions.clear();
+
   assert(Defs.empty() && Uses.empty() &&
          "Only BuildGraph should update Defs/Uses");
   Defs.setUniverse(TRI->getNumRegs());
   Uses.setUniverse(TRI->getNumRegs());
 
   assert(CurrentVRegDefs.empty() && "nobody else should use CurrentVRegDefs");
   assert(CurrentVRegUses.empty() && "nobody else should use CurrentVRegUses");
   unsigned NumVirtRegs = MRI.getNumVirtRegs();
   CurrentVRegDefs.setUniverse(NumVirtRegs);
   CurrentVRegUses.setUniverse(NumVirtRegs);
 
   // Model data dependencies between instructions being scheduled and the
   // ExitSU.
   addSchedBarrierDeps();
 
   // Walk the list of instructions, from bottom moving up.
   MachineInstr *DbgMI = nullptr;
+  MachineInstr *CFIInstr = nullptr;
+
   for (MachineBasicBlock::iterator MII = RegionEnd, MIE = RegionBegin;
        MII != MIE; --MII) {
     MachineInstr &MI = *std::prev(MII);
     if (DbgMI) {
       DbgValues.push_back(std::make_pair(DbgMI, &MI));
       DbgMI = nullptr;
     }
 
     if (MI.isDebugValue()) {
       DbgMI = &MI;
       continue;
     }
     if (MI.isDebugLabel())
       continue;
 
+    // If the scheduling of CFI instructions is enabled, we remember them and
+    // instructions that preced them. CFI instructions are not included in the
+    // scheduling DAG but get inserted at the correct position later
+    if (CFIInstr) {
+      CFIInstructions.push_back(std::make_pair(CFIInstr, &MI));
+      CFIInstr = nullptr;
+    }
+
+    if (MI.isCFIInstruction() && CFIInstructionScheduling) {
+      CFIInstr = &MI;
+      continue;
+    }
+
     SUnit *SU = MISUnitMap[&MI];
     assert(SU && "No SUnit mapped to this MI");
 
     if (RPTracker) {
       RegisterOperands RegOpers;
       RegOpers.collect(MI, *TRI, MRI, TrackLaneMasks, false);
       if (TrackLaneMasks) {
         SlotIndex SlotIdx = LIS->getInstructionIndex(MI);
         RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx);
       }
       if (PDiffs != nullptr)
         PDiffs->addInstruction(SU->NodeNum, RegOpers, MRI);
 
       if (RPTracker->getPos() == RegionEnd || &*RPTracker->getPos() != &MI)
         RPTracker->recedeSkipDebugValues();
       assert(&*RPTracker->getPos() == &MI && "RPTracker in sync");
       RPTracker->recede(RegOpers);
     }
 
     assert(
         (CanHandleTerminators || (!MI.isTerminator() && !MI.isPosition())) &&
         "Cannot schedule terminators or labels!");
 
+    // If a CFI_INSTRUCTION reaches this point the scheduling of cfi
+    // instructions must be enabled
+    assert((!MI.isCFIInstruction() || CFIInstructionScheduling) &&
+           "Scheduling of cfi instructions is not enabled");
+
     // Add register-based dependencies (data, anti, and output).
     // For some instructions (calls, returns, inline-asm, etc.) there can
     // be explicit uses and implicit defs, in which case the use will appear
     // on the operand list before the def. Do two passes over the operand
     // list to make sure that defs are processed before any uses.
     bool HasVRegDef = false;
     for (unsigned j = 0, n = MI.getNumOperands(); j != n; ++j) {
       const MachineOperand &MO = MI.getOperand(j);

llvm/test/CodeGen/AArch64/cfiinstrs-no-uwtable-scheduling.ll

+; RUN: llc -O1 -mtriple aarch64-arm-gnu-linux -schedule-cfiinstrs=true --verify-machineinstrs %s -o - | FileCheck %s
+; RUN: llc -O1 -mtriple aarch64-arm-gnu-linux -schedule-cfiinstrs=false --verify-machineinstrs %s -o - | FileCheck %s
+
+@.str = private unnamed_addr constant [1 x i8] zeroinitializer, align 1
+
+; Function Attrs: nounwind
+define dso_local i32 @a() #0 {
+entry:
+  %call = tail call i32 bitcast (i32 (...)* @b to i32 (i32 (...)*)*)(i32 (...)* bitcast (i32 ()* @a to i32 (...)*)) #2
+  br label %for.cond
+
+for.cond:                                 
+  %call1 = tail call i32 bitcast (i32 (...)* @c to i32 (i8*, i32 (...)*)*)(i8* getelementptr inbounds ([1 x i8], [1 x i8]* @.str, i64 0, i64 0), i32 (...)* nonnull @b) #2
+  br label %for.cond
+}
+
+declare dso_local i32 @b(...)
+declare dso_local i32 @c(...) local_unnamed_addr
+
+attributes #0 = { nounwind }
+
+; CHECK:    a:
+; CHECK:        str x30, [sp, #-32]!
+; CHECK:        adrp x0, a
+; CHECK:        add x0, x0, :lo12:a
+; CHECK:        stp x20, x19, [sp, #16]
+; CHECK:        bl b
+; CHECK:        adrp x19, .L.str
+; CHECK:        adrp x20, b
+; CHECK:        add x19, x19, :lo12:.L.str
+; CHECK:        add x20, x20, :lo12:b
+; CHECK:    .LBB0_1:
+; CHECK:        mov x0, x19
+; CHECK:        mov x1, x20
+; CHECK:        bl c
+; CHECK:        b .LBB0_1
+; CHECK:    .Lfunc_end0:
+; CHECK:        .size a, .Lfunc_end0-a

llvm/test/CodeGen/AArch64/cfiinstrs-scheduling.ll

+; RUN: llc -O1 -mtriple aarch64-arm-gnu-linux -schedule-cfiinstrs=true --verify-machineinstrs %s -o - | FileCheck --check-prefix=CHECK-SCHEDULING %s
+; RUN: llc -O1 -mtriple aarch64-arm-gnu-linux -schedule-cfiinstrs=false --verify-machineinstrs %s -o - | FileCheck --check-prefix=CHECK-NO-SCHEDULING %s
+
+@.str = private unnamed_addr constant [1 x i8] zeroinitializer, align 1
+
+; Function Attrs: uwtable
+define dso_local i32 @a() #0 {
+entry:
+  %call = tail call i32 bitcast (i32 (...)* @b to i32 (i32 (...)*)*)(i32 (...)* bitcast (i32 ()* @a to i32 (...)*)) #2
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.cond, %entry
+  %call1 = tail call i32 bitcast (i32 (...)* @c to i32 (i8*, i32 (...)*)*)(i8* getelementptr inbounds ([1 x i8], [1 x i8]* @.str, i64 0, i64 0), i32 (...)* nonnull @b) #2
+  br label %for.cond
+}
+
+declare dso_local i32 @b(...)
+declare dso_local i32 @c(...) local_unnamed_addr 
+
+; CHECK:                    a:
+; CHECK:                          .cfi_startproc
+;
+; CHECK-SCHEDULING:               str x30, [sp, #-32]!
+; CHECK-SCHEDULING:               adrp x0, a
+; CHECK-SCHEDULING:               add x0, x0, :lo12:a
+; CHECK-SCHEDULING:               stp x20, x19, [sp, #16]
+; CHECK-SCHEDULING:               .cfi_def_cfa_offset 32
+; CHECK-SCHEDULING:               .cfi_offset w19, -8
+; CHECK-SCHEDULING:               .cfi_offset w20, -16
+; CHECK-SCHEDULING:               .cfi_offset w30, -32
+; CHECK-SCHEDULING:               bl b
+; CHECK-SCHEDULING:               adrp x19, .L.str
+; CHECK-SCHEDULING:               adrp x20, b
+; CHECK-SCHEDULING:               add x19, x19, :lo12:.L.str
+; CHECK-SCHEDULING:               add x20, x20, :lo12:b
+;
+; CHECK-NO-SCHEDULING:            str x30, [sp, #-32]!
+; CHECK-NO-SCHEDULING:            stp x20, x19, [sp, #16]
+; CHECK-NO-SCHEDULING:            .cfi_def_cfa_offset 32
+; CHECK-NO-SCHEDULING:            .cfi_offset w19, -8
+; CHECK-NO-SCHEDULING:            .cfi_offset w20, -16
+; CHECK-NO-SCHEDULING:            .cfi_offset w30, -32
+; CHECK-NO-SCHEDULING:            adrp x0, a
+; CHECK-NO-SCHEDULING:            add x0, x0, :lo12:a
+; CHECK-NO-SCHEDULING:            bl b
+; CHECK-NO-SCHEDULING:            adrp x19, .L.str
+; CHECK-NO-SCHEDULING:            adrp x20, b
+; CHECK-NO-SCHEDULING:            add x19, x19, :lo12:.L.str
+; CHECK-NO-SCHEDULING:            add x20, x20, :lo12:b
+;
+; CHECK:                    .LBB0_1:
+; CHECK:                          mov x0, x19
+; CHECK:                          mov x1, x20
+; CHECK:                          bl c
+; CHECK:                          b .LBB0_1
+; CHECK:                    .Lfunc_end0:
+; CHECK:                          .size a, .Lfunc_end0-a