Fix nondeterministic output in local stack slot alloc pass

[arsenm]

Summary

This finds all of the references to a frame index in a function, and
sorts by the offset. If multiple instructions use the same offset,
nothing was breaking the tie for sorting.

This avoids the test failures the reverted r282999 introduced.

[arsenm]

ping

[mgrang]

Matthias,

Could you please review this patch? My patch (https://reviews.llvm.org/D25695) tries to fix this by adding a FrameIdx as a tie-breaker.
But as Matt says "the same frame index wit the same offset can appear multiple times".

--Mandeep

[mgrang]

lib/CodeGen/LocalStackSlotAllocation.cpp

66

Can we change this into:

bool operator<(const FrameRef &RHS) const {
  return std::tie(LocalOffset, FrameIdx, Order) <
         std::tie(RHS.LocalOffset, RHS.FrameIdx, RHS.Order);
}

[MatzeB]

LGTM.

[mgrang]

Matt,
Could you please merge this patch?

--Mandeep

[mgrang]

Ping.

[arsenm]

r285201

lib/CodeGen/LocalStackSlotAllocation.cpp

 STATISTIC(NumBaseRegisters, "Number of virtual frame base registers allocated");
 STATISTIC(NumReplacements, "Number of frame indices references replaced");
 
 namespace {
   class FrameRef {
     MachineBasicBlock::iterator MI; // Instr referencing the frame
     int64_t LocalOffset;            // Local offset of the frame idx referenced
     int FrameIdx;                   // The frame index
+
+    // Order reference instruction appears in program. Used to ensure
+    // deterministic order when multiple instructions may reference the same
+    // location.
+    unsigned Order;
+
   public:
-    FrameRef(MachineBasicBlock::iterator I, int64_t Offset, int Idx) :
-      MI(I), LocalOffset(Offset), FrameIdx(Idx) {}
+    FrameRef(MachineInstr *I, int64_t Offset, int Idx, unsigned Ord) :
+      MI(I), LocalOffset(Offset), FrameIdx(Idx), Order(Ord) {}
     bool operator<(const FrameRef &RHS) const {
-      return LocalOffset < RHS.LocalOffset;
+      if (LocalOffset < RHS.LocalOffset)
+        return true;
+      return Order < RHS.Order;
     }
     MachineBasicBlock::iterator getMachineInstr() const { return MI; }
     int64_t getLocalOffset() const { return LocalOffset; }
     int getFrameIndex() const { return FrameIdx; }
   };
 
   class LocalStackSlotPass: public MachineFunctionPass {
     SmallVector<int64_t,16> LocalOffsets;
bool StackGrowsDown =
     TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
 
   // Collect all of the instructions in the block that reference
   // a frame index. Also store the frame index referenced to ease later
   // lookup. (For any insn that has more than one FI reference, we arbitrarily
   // choose the first one).
   SmallVector<FrameRef, 64> FrameReferenceInsns;
 
+  unsigned Order = 0;
+
   for (MachineBasicBlock &BB : Fn) {
     for (MachineInstr &MI : BB) {
       // Debug value, stackmap and patchpoint instructions can't be out of
       // range, so they don't need any updates.
       if (MI.isDebugValue() || MI.getOpcode() == TargetOpcode::STATEPOINT ||
           MI.getOpcode() == TargetOpcode::STACKMAP ||
           MI.getOpcode() == TargetOpcode::PATCHPOINT)
         continue;
for (MachineInstr &MI : BB) {
         if (MI.getOperand(i).isFI()) {
           // Don't try this with values not in the local block.
           if (!MFI.isObjectPreAllocated(MI.getOperand(i).getIndex()))
             break;
           int Idx = MI.getOperand(i).getIndex();
           int64_t LocalOffset = LocalOffsets[Idx];
           if (!TRI->needsFrameBaseReg(&MI, LocalOffset))
             break;
-          FrameReferenceInsns.push_back(FrameRef(&MI, LocalOffset, Idx));
+          FrameReferenceInsns.push_back(FrameRef(&MI, LocalOffset, Idx, Order++));
           break;
         }
       }
     }
   }
 
   // Sort the frame references by local offset
   array_pod_sort(FrameReferenceInsns.begin(), FrameReferenceInsns.end());