[Statistics] Add a method to atomically update a statistic that contains a maximum

[craig.topper]

Summary

There are several places in the codebase that try to calculate a maximum value in a Statistic object. We currently do this in one of two ways:

MaxNumFoo = std::max(MaxNumFoo, NumFoo);

or

MaxNumFoo = (MaxNumFoo > NumFoo) ? MaxNumFoo : NumFoo;

The first version reads from MaxNumFoo one time and uncontionally rwrites to it. The second rversion possibly reads it twice depending on the result of the first compare. But we have no way of knowing if the value was changed by another thread between the reads and the writes.

This patch adds a method to the Statistic object that can ensure that we only store if our value is the max and the previous max didn't change after we read it. If it changed we'll recheck if our value should still be the max or not and try again.

This spawned from an audit I'm trying to do of all places we uses the implicit conversion to unsigned on the Statistics objects. See my previous thread on llvm-dev https://groups.google.com/forum/#!topic/llvm-dev/yfvxiorKrDQ

[chandlerc]

LGTM

Ahh, "atomic" max. I remember when I first wrote this in some other project 8 years ago now and had to figure out if it really has adequate forward progress guarantees... =] (It does.)

include/llvm/ADT/Statistic.h

#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
 
   const Statistic &operator-=(unsigned V) {
     if (V == 0)
       return *this;
     Value.fetch_sub(V, std::memory_order_relaxed);
     return init();
   }
 
+  void updateMax(unsigned V) {
+    unsigned PrevMax = Value.load(std::memory_order_relaxed);
+    // Keep trying to update max until we succeed or another thread produces
+    // a bigger max than us.
+    while (V > PrevMax && !Value.compare_exchange_weak(
+                              PrevMax, V, std::memory_order_relaxed)) {
+    }
+    init();
+  }
+
 #else  // Statistics are disabled in release builds.
 
   const Statistic &operator=(unsigned Val) {
     return *this;
   }
 
   const Statistic &operator++() {
     return *this;
#else  // Statistics are disabled in release builds.
   const Statistic &operator+=(const unsigned &V) {
     return *this;
   }
 
   const Statistic &operator-=(const unsigned &V) {
     return *this;
   }
 
+  void updateMax(unsigned V) {}
+
 #endif  // !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
 
 protected:
   Statistic &init() {
     bool tmp = Initialized;
     sys::MemoryFence();
     if (!tmp) RegisterStatistic();
     TsanHappensAfter(this);

lib/Analysis/CallGraphSCCPass.cpp

do {
                      << Iteration << '\n');
       DevirtualizedCall = false;
       Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall);
     } while (Iteration++ < MaxIterations && DevirtualizedCall);
     
     if (DevirtualizedCall)
       DEBUG(dbgs() << "  CGSCCPASSMGR: Stopped iteration after " << Iteration
                    << " times, due to -max-cg-scc-iterations\n");
-    
-    if (Iteration > MaxSCCIterations)
-      MaxSCCIterations = Iteration;
-    
+    MaxSCCIterations.updateMax(Iteration);
   }
   Changed |= doFinalization(CG);
   return Changed;
 }
 
 
 /// Initialize CG
 bool CGPassManager::doInitialization(CallGraph &CG) {

lib/CodeGen/SelectionDAG/StatepointLowering.cpp

StatepointLoweringState::allocateStackSlot(EVT ValueType,
   MFI.markAsStatepointSpillSlotObjectIndex(FI);
 
   Builder.FuncInfo.StatepointStackSlots.push_back(FI);
   AllocatedStackSlots.resize(AllocatedStackSlots.size()+1, true);
   assert(AllocatedStackSlots.size() ==
          Builder.FuncInfo.StatepointStackSlots.size() &&
          "Broken invariant");
 
-  StatepointMaxSlotsRequired = std::max<unsigned long>(
-      StatepointMaxSlotsRequired, Builder.FuncInfo.StatepointStackSlots.size());
+  StatepointMaxSlotsRequired.updateMax(
+      Builder.FuncInfo.StatepointStackSlots.size());
 
   return SpillSlot;
 }
 
 /// Utility function for reservePreviousStackSlotForValue. Tries to find
 /// stack slot index to which we have spilled value for previous statepoints.
 /// LookUpDepth specifies maximum DFS depth this function is allowed to look.
 static Optional<int> findPreviousSpillSlot(const Value *Val,

lib/Transforms/Scalar/SROA.cpp

for (Slice *S : P.splitSliceTails()) {
     ++NumUses;
   }
   for (Slice &S : P) {
     Promotable &= Rewriter.visit(&S);
     ++NumUses;
   }
 
   NumAllocaPartitionUses += NumUses;
-  MaxUsesPerAllocaPartition =
-      std::max<unsigned>(NumUses, MaxUsesPerAllocaPartition);
+  MaxUsesPerAllocaPartition.updateMax(NumUses);
 
   // Now that we've processed all the slices in the new partition, check if any
   // PHIs or Selects would block promotion.
   for (PHINode *PHI : PHIUsers)
     if (!isSafePHIToSpeculate(*PHI)) {
       Promotable = false;
       PHIUsers.clear();
       SelectUsers.clear();
if (AllocaInst *NewAI = rewritePartition(AI, AS, P)) {
         uint64_t Size = std::min(AllocaSize, P.size() * SizeOfByte);
         Fragments.push_back(Fragment(NewAI, P.beginOffset() * SizeOfByte, Size));
       }
     }
     ++NumPartitions;
   }
 
   NumAllocaPartitions += NumPartitions;
-  MaxPartitionsPerAlloca =
-      std::max<unsigned>(NumPartitions, MaxPartitionsPerAlloca);
+  MaxPartitionsPerAlloca.updateMax(NumPartitions);
 
   // Migrate debug information from the old alloca to the new alloca(s)
   // and the individual partitions.
   if (DbgDeclareInst *DbgDecl = FindAllocaDbgDeclare(&AI)) {
     auto *Var = DbgDecl->getVariable();
     auto *Expr = DbgDecl->getExpression();
     DIBuilder DIB(*AI.getModule(), /*AllowUnresolved*/ false);
     uint64_t AllocaSize = DL.getTypeSizeInBits(AI.getAllocatedType());