[PGO] Register promote profile counter updates

[davidxl]

Summary

Two of the biggest problems with the current PGO instrumentation are 1) instrumented multi-threaded program performance 2) multi-threaded profile counter precision. Both are due to contentions created due to shared profile counter updates in hot regions of the program. In a multi-threaded program with work-sharing loop, with instrumentation increasing the number of threads actually slows down the program significantly -- from 10s elapse time with one thread down to > 5min using 16 threads. What is worse, the hottest block count is 4000000000 with 1 thread, but dropped to only 177119367 with 32 threads -- 95% of the counts are lost due to data races. Using atomic RMW is one way to fix the problem, but it will greatly slows down the instrumented program (see data below).

This patch implements the loop based register promotion for counter updates. It makes use of existing SSA updater utility (load store promotion) and isolates the change inside the lowerer without the need to expose the aliasing properties of the counter variables to any of the existing optimizer components. The lowerer has the full knowledge of counters and requires very little analysis. It supports speculative code motion and works at lower optimization level.

With this patch, the performance of the multi-threaded program mentioned above is improved greatly. For one thread, it speeds up the program by 22%. For 16 threads, the elapse time is only 0.9s, > 300x speedup compared without the patch. The profile counter precision is also greatly improved. With 32 threads, the hottest block count is 3996000000 only 0.09% counts are lost.

The patch speeds up single threaded instrumentation binary performance as well.

Here are the spec2000 int numbers

 164.gzip     -0.81%
   175.vpr      2.05%
    176.gcc     11.08%
    181.mcf     -0.61%
 186.crafty     -3.46%
 197.parser      4.90%
    252.eon     18.00%
253.perlbmk     11.21%
 255.vortex     -0.04%
  256.bzip2      8.67%
  300.twolf      3.89%

Here are the spec06 numbers

400.perlbench         -1.87%
     401.bzip2           16.98%
       403.gcc            4.82%
       429.mcf           12.88%
     445.gobmk          1.83%
     456.hmmer         12.48%
     458.sjeng           -0.19%
462.libquantum       28.09%
   464.h264ref          6.49%
   471.omnetpp         1.21%
     473.astar             8.31%
 483.xalancbmk        0.95%
    450.soplex          12.35%
    447.dealII            6.33%
    453.povray         -3.29%
      444.namd          1.88%

I did some analysis on the povray regression: the program has a few hot loops with some blocks guarded by input flags which are never executed. Hoisting counter update outside the loop thus increases dynamic instruction count.

Lastly, here is the SPEC2k number of using atomic fetch-add compared the base line without this patch:

164.gzip       -14.02%
     175.vpr       -16.02%
     176.gcc       -14.15%
     181.mcf        -4.48%
  186.crafty       -44.98%
  197.parser       -11.69%
     252.eon       -13.79%
 253.perlbmk         6.26%
  255.vortex        -4.70%
   256.bzip2        -4.06%
   300.twolf       -17.24%

[efriedma]

Did you do an analysis of whether this produces the same counter values for single-threaded code?

It looks like the way you're doing hoisting doesn't interact correctly with loops that don't exit; if a call in a loop throws an exception, or calls exit(), the counter values will be off.

[davidxl]

See the summary for precision data. With this patch, the multi-threaded counter value is much closer to the single threaded case with very little loss.

It is unlikely that loops with calls to no-return function can be in the hot paths. Regardless, the patch already disables promotion for such loops (with multiple existing blocks). If we want to improve training run performance for such loops, we can make enhancement insert counter flush before the noreturn calls.

[vsk]

This is a really interesting patch. I haven't worked with SSAUpdater before, so I think it would be best if someone else reviewed that part of the patch.

On another note, do you know if counter promotion could be made to work with frontend-based instrumentation?

include/llvm/Transforms/InstrProfiling.h

64

It may be more convenient to introduce 'using LoadStorePair = ...'

75

Could you write this with a dash, e.g 'Register-promote'

lib/Transforms/Instrumentation/InstrProfiling.cpp

101

Would cl::Optional be more appropriate?

111

The "do-counter-promotion" flag is ternary, and should be simplified. I'd prefer a cl::opt which specifies whether counter promotion is "allowed", and an InstrProfOptions field which specifies whether it is done. In promoteCounterLoadStores, you could write:

if (!AllowCounterPromotion || !Opts.DoCounterPromotion)
  return;

148

It would help to have brief doxygen lines for the two new classes.

221

const auto &Cand?

313

const auto &LoadStore?

480

We shouldn't update the promotion candidates vector if counter promotion is disabled.

test/Transforms/PGOProfile/counter_promo.ll

3

Is the global needed?

40

You may need to add 'requires: asserts' to tests which refer to bb or variable names.

52

In this test, the CFG looks like:

   2
  /  \
4      5
|     / \
|    7    8
 \  /____/ 
   9 --- loop ---> 2
   |
  exit

Is this the simplest loop where ld/st promotion applies?

52

Could you add checks for the operands to the adds? It would be useful to have checks for the PHIs incremented in the loop body, to ensure they make their way to the correct 'add'.

52

Could you add a check-not for further uses of __profc*?

test/Transforms/PGOProfile/counter_promo_mexits.ll

72

It would help to have 'check-nots' for further updates to __profc* in this test as well.

test/profile/Linux/counter_promo_for.c

15

Why are the IR checks needed in this test? Imho the interesting thing about this test is the "diff", and not the IR checks, which are probably better off in test/Transforms/PGOProfile.

test/profile/Linux/counter_promo_while.c

39

I have the same comment about the IR checks here.

41

Would placing a nested for loop here increase test coverage?

[davidxl]

Regarding turning this on for FE instrumentation, it can be done, but probably as a follow up (which also needs loop canonlicalization and rotation). More coverage test performance data (possibly at O0) also need to be collected.

lib/Transforms/Instrumentation/InstrProfiling.cpp

101

Sometimes the build system can append multiple instances of a common flag to the command line. Without ZeroOrMore, driver reports error.

111

We need the ability to use this option to override (either force it to be on or off) the default pipeline option. Your proposal does not seem to accomplish that.

test/Transforms/PGOProfile/counter_promo.ll

3

removed.

40

The name of the counter vars seem to be kept with the non-asserts compiler. Any idea why?

52

The purpose is to test multiple counters hoisted

52

Done.

test/profile/Linux/counter_promo_for.c

15

It is end-to-end test to make sure every single step in the piplineline (from FE ) is covered. If the transformation does not happen, it makes no sense to do DIFF any more. The LLVM tests only cover the lowering part.

test/profile/Linux/counter_promo_while.c

39

I think it is better to keep them here unless it creates big overhead which I doubt.

41

Probably a little -- as it tests the behavior of promoter with multiple loops in the same nest.

[davidxl]

Addressed Vedant's comments.

[vsk]

In D34085#779375, @davidxl wrote:

Regarding turning this on for FE instrumentation, it can be done, but probably as a follow up (which also needs loop canonlicalization and rotation). More coverage test performance data (possibly at O0) also need to be collected.

I'd be willing to help out with this, unless you already have plans to get to it.

lib/Transforms/Instrumentation/InstrProfiling.cpp

101

Ok

111

I think the 'isCounterPromotionEnabled' method makes things clear enough

170

This may be a basic question, but.. why is it that SSA.GetValueInMiddleOfBlock(ExitBlock) gives the right increment, coming from the promoted counter for {L, S}? It may help to have a short comment about this for readers who are unfamiliar with SSAUpdater (like me).

test/Transforms/PGOProfile/counter_promo.ll

40

Ah, I think ssa var names are kept, but basic block label names are not.

52

I think this is still missing

[davidxl]

Added one more test case to show the merged live-in values from multiple predecessors in the loop.

lib/Transforms/Instrumentation/InstrProfiling.cpp

170

Added a comment. The name of the API is a little misleading -- it really means getting the LiveIn value (from the promoted counter stores) to the exit block.

[davidxl]

Addressed review comments.

[davidxl]

Added another debug option.

[vsk]

For due diligence I tested out this patch on a simple multi-threaded program which runs 10^7 dot-products in 8 different threads. Post-patch, I noticed that the profile counts are much more consistent. Register-promotion kicked in and the optimizer was able to hoist some counter increments out of the loop.

Review has stalled, so I'll try looking into the SSAUpdater bits.

[vsk]

I had a look through SSAUpdater and it seems like this is doing something totally reasonable. This lgtm with some changes pointed out inline.

lib/Transforms/Instrumentation/InstrProfiling.cpp

178

There should be some test coverage for the atomic-counter-update-promoted option.

202

Would a SmallPtrSet<..., 8> be more appropriate here, given the definition for LoopExitBlocks?

[davidxl]

Update patch according to Vedant's feedback.

[davide]

FWIW, the usage of the updater seems correct.
Please note that the updater has O(N^3) worst case performance in some cases [1].
I don't think this will show up here, but you might want to double check the impact on compile time.

[1] e.g. type
llvm-stress -instructions=50000 | ./opt -mem2reg -lcssa -time-passes and run inside a profiler.

include/llvm/Transforms/InstrProfiling.h

struct PerFunctionProfileData {
     }
   };
   DenseMap<GlobalVariable *, PerFunctionProfileData> ProfileDataMap;
   std::vector<GlobalValue *> UsedVars;
   std::vector<GlobalVariable *> ReferencedNames;
   GlobalVariable *NamesVar;
   size_t NamesSize;
 
+  // vector of counter load/store pairs to be register promoted.
+  std::vector<std::pair<Instruction *, Instruction *>> PromotionCandidates;
+
   // The start value of precise value profile range for memory intrinsic sizes.
   int64_t MemOPSizeRangeStart;
   // The end value of precise value profile range for memory intrinsic sizes.
   int64_t MemOPSizeRangeLast;
 
+  /// Lower instrumentation intrinsics in the function. Returns true if there
+  /// any lowering.
+  bool lowerIntrinsics(Function *F);
+
+  /// Register promote counter loads and stores in loops.
+  void promoteCounterLoadStores(Function *F);
+
   /// Count the number of instrumented value sites for the function.
   void computeNumValueSiteCounts(InstrProfValueProfileInst *Ins);
 
   /// Replace instrprof_value_profile with a call to runtime library.
   void lowerValueProfileInst(InstrProfValueProfileInst *Ins);
 
   /// Replace instrprof_increment with an increment of the appropriate value.
   void lowerIncrement(InstrProfIncrementInst *Inc);

include/llvm/Transforms/Instrumentation.h

                                  uint64_t TotalCount,
                                  bool AttachProfToDirectCall);
 
 /// Options for the frontend instrumentation based profiling pass.
 struct InstrProfOptions {
   // Add the 'noredzone' attribute to added runtime library calls.
   bool NoRedZone = false;
 
+  // Do counter register promotion
+  bool DoCounterPromotion = false;
+
   // Name of the profile file to use as output
   std::string InstrProfileOutput;
 
   InstrProfOptions() = default;
 };
 
 /// Insert frontend instrumentation based profiling.
 ModulePass *createInstrProfilingLegacyPass(

lib/Passes/PassBuilder.cpp

   // Delete anything that is now dead to make sure that we don't instrument
   // dead code. Instrumentation can end up keeping dead code around and
   // dramatically increase code size.
   MPM.addPass(GlobalDCEPass());
 
   if (RunProfileGen) {
     MPM.addPass(PGOInstrumentationGen());
 
+    FunctionPassManager FPM;
+    FPM.addPass(createFunctionToLoopPassAdaptor(LoopRotatePass()));
+    MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
+
     // Add the profile lowering pass.
     InstrProfOptions Options;
     if (!ProfileGenFile.empty())
       Options.InstrProfileOutput = ProfileGenFile;
+    Options.DoCounterPromotion = true;
     MPM.addPass(InstrProfiling(Options));
   }
 
   if (!ProfileUseFile.empty())
     MPM.addPass(PGOInstrumentationUse(ProfileUseFile));
 }
 
 ModulePassManager

lib/Transforms/IPO/PassManagerBuilder.cpp

     addExtensionsToPM(EP_Peephole, MPM);
   }
   if (EnablePGOInstrGen) {
     MPM.add(createPGOInstrumentationGenLegacyPass());
     // Add the profile lowering pass.
     InstrProfOptions Options;
     if (!PGOInstrGen.empty())
       Options.InstrProfileOutput = PGOInstrGen;
+    Options.DoCounterPromotion = true;
+    MPM.add(createLoopRotatePass());
     MPM.add(createInstrProfilingLegacyPass(Options));
   }
   if (!PGOInstrUse.empty())
     MPM.add(createPGOInstrumentationUseLegacyPass(PGOInstrUse));
   // Indirect call promotion that promotes intra-module targets only.
   // For ThinLTO this is done earlier due to interactions with globalopt
   // for imported functions. We don't run this at -O0.
   if (OptLevel > 0)

lib/Transforms/Instrumentation/InstrProfiling.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/InstrProfiling.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/ADT/Twine.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/GlobalVariable.h"
+#include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
-#include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Pass.h"
 #include "llvm/ProfileData/InstrProf.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/ErrorHandling.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/LoopSimplify.h"
 #include "llvm/Transforms/Utils/ModuleUtils.h"
+#include "llvm/Transforms/Utils/SSAUpdater.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <string>
 
 using namespace llvm;
 
cl::opt<double> NumCountersPerValueSite(
     cl::desc("The average number of profile counters allocated "
              "per value profiling site."),
     // This is set to a very small value because in real programs, only
     // a very small percentage of value sites have non-zero targets, e.g, 1/30.
     // For those sites with non-zero profile, the average number of targets
     // is usually smaller than 2.
     cl::init(1.0));
 
+cl::opt<bool> AtomicCounterUpdatePromoted(
+    "atomic-counter-update-promoted", cl::ZeroOrMore,
+    cl::desc("Do counter update using atomic fetch add "
+             " for promoted counters only"),
+    cl::init(false));
+
+// If the option is not specified, the default behavior about whether
+// counter promotion is done depends on how instrumentaiton lowering
+// pipeline is setup, i.e., the default value of true of this option
+// does not mean the promotion will be done by default. Explicitly
+// setting this option can override the default behavior.
+cl::opt<bool> DoCounterPromotion("do-counter-promotion", cl::ZeroOrMore,
+                                 cl::desc("Do counter register promotion"),
+                                 cl::init(true));
+cl::opt<unsigned> MaxNumberOfPromotions(
+    cl::ZeroOrMore, "max-counter-promotions-per-loop", cl::init(10),
+    cl::desc("Max number counter promotions per loop to avoid"
+             " increasing register pressure too much"));
+
+cl::opt<bool> SpeculativeCounterPromotion(
+    cl::ZeroOrMore, "speculative-counter-promotion", cl::init(false),
+    cl::desc("Allow counter promotion for loops with multiple exiting blocks "
+             " or top-tested loops. "));
+
 class InstrProfilingLegacyPass : public ModulePass {
   InstrProfiling InstrProf;
 
 public:
   static char ID;
 
   InstrProfilingLegacyPass() : ModulePass(ID) {}
   InstrProfilingLegacyPass(const InstrProfOptions &Options)
       : ModulePass(ID), InstrProf(Options) {}
 
   StringRef getPassName() const override {
     return "Frontend instrumentation-based coverage lowering";
   }
 
   bool runOnModule(Module &M) override {
     return InstrProf.run(M, getAnalysis<TargetLibraryInfoWrapperPass>().getTLI());
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
   }
 };
 
+class PGOCounterPromoterHelper : public LoadAndStorePromoter {
+public:
+  PGOCounterPromoterHelper(Instruction *L, Instruction *S, SSAUpdater &SSA,
+                           Value *Init, BasicBlock *PH,
+                           ArrayRef<BasicBlock *> ExitBlocks,
+                           ArrayRef<Instruction *> InsertPts)
+      : LoadAndStorePromoter({L, S}, SSA), Store(S), ExitBlocks(ExitBlocks),
+        InsertPts(InsertPts) {
+    assert(isa<LoadInst>(L));
+    assert(isa<StoreInst>(S));
+    SSA.AddAvailableValue(PH, Init);
+  }
+  void doExtraRewritesBeforeFinalDeletion() const override {
+    for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
+      BasicBlock *ExitBlock = ExitBlocks[i];
+      Instruction *InsertPos = InsertPts[i];
+      Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock);
+      Value *Addr = cast<StoreInst>(Store)->getPointerOperand();
+      IRBuilder<> Builder(InsertPos);
+      if (AtomicCounterUpdatePromoted)
+        Builder.CreateAtomicRMW(AtomicRMWInst::Add, Addr, LiveInValue,
+                                AtomicOrdering::SequentiallyConsistent);
+      else {
+        LoadInst *OldVal = Builder.CreateLoad(Addr, "pgocount.promoted");
+        auto *NewVal = Builder.CreateAdd(OldVal, LiveInValue);
+        Builder.CreateStore(NewVal, Addr);
+      }
+    }
+  }
+
+private:
+  Instruction *Store;
+  ArrayRef<BasicBlock *> ExitBlocks;
+  ArrayRef<Instruction *> InsertPts;
+};
+
+class PGOCounterPromoter {
+public:
+  PGOCounterPromoter(ArrayRef<std::pair<Instruction *, Instruction *>> Cands,
+                     Loop &Loop)
+      : Candidates(Cands), ExitBlocks(), InsertPts(), ParentLoop(Loop) {
+
+    ParentLoop.getExitBlocks(ExitBlocks);
+
+    InsertPts.reserve(ExitBlocks.size());
+    for (BasicBlock *ExitBlock : ExitBlocks)
+      InsertPts.push_back(&*ExitBlock->getFirstInsertionPt());
+  }
+
+  bool run() {
+    // We can't insert into a catchswitch.
+    bool HasCatchSwitch = llvm::any_of(ExitBlocks, [](BasicBlock *Exit) {
+      return isa<CatchSwitchInst>(Exit->getTerminator());
+    });
+
+    if (HasCatchSwitch)
+      return false;
+
+    if (!ParentLoop.hasDedicatedExits())
+      return false;
+
+    BasicBlock *PH = ParentLoop.getLoopPreheader();
+    if (!PH)
+      return false;
+
+    BasicBlock *H = ParentLoop.getHeader();
+    bool TopTested =
+        ((ParentLoop.getBlocks().size() > 1) && ParentLoop.isLoopExiting(H));
+    if (!SpeculativeCounterPromotion &&
+        (TopTested || ParentLoop.getExitingBlock() == nullptr))
+      return false;
+
+    unsigned Promoted = 0;
+    for (auto Cand : Candidates) {
+
+      SmallVector<PHINode *, 4> NewPHIs;
+      SSAUpdater SSA(&NewPHIs);
+      Value *InitVal = ConstantInt::get(Cand.first->getType(), 0);
+      PGOCounterPromoterHelper Promoter(Cand.first, Cand.second, SSA, InitVal,
+                                        PH, ExitBlocks, InsertPts);
+      Promoter.run(SmallVector<Instruction *, 2>({Cand.first, Cand.second}));
+      Promoted++;
+      if (Promoted >= MaxNumberOfPromotions)
+        break;
+    }
+
+    DEBUG(dbgs() << Promoted << " counters promoted for loop (depth="
+                 << ParentLoop.getLoopDepth() << ")\n");
+    return Promoted != 0;
+  }
+
+private:
+  ArrayRef<std::pair<Instruction *, Instruction *>> Candidates;
+  SmallVector<BasicBlock *, 8> ExitBlocks;
+  SmallVector<Instruction *, 8> InsertPts;
+  Loop &ParentLoop;
+};
+
 } // end anonymous namespace
 
 PreservedAnalyses InstrProfiling::run(Module &M, ModuleAnalysisManager &AM) {
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(M);
   if (!run(M, TLI))
     return PreservedAnalyses::all();
 
   return PreservedAnalyses::none();

 
 static InstrProfIncrementInst *castToIncrementInst(Instruction *Instr) {
   InstrProfIncrementInst *Inc = dyn_cast<InstrProfIncrementInstStep>(Instr);
   if (Inc)
     return Inc;
   return dyn_cast<InstrProfIncrementInst>(Instr);
 }
 
+bool InstrProfiling::lowerIntrinsics(Function *F) {
+  bool MadeChange = false;
+  PromotionCandidates.clear();
+  for (BasicBlock &BB : *F) {
+    for (auto I = BB.begin(), E = BB.end(); I != E;) {
+      auto Instr = I++;
+      InstrProfIncrementInst *Inc = castToIncrementInst(&*Instr);
+      if (Inc) {
+        lowerIncrement(Inc);
+        MadeChange = true;
+      } else if (auto *Ind = dyn_cast<InstrProfValueProfileInst>(Instr)) {
+        lowerValueProfileInst(Ind);
+        MadeChange = true;
+      }
+    }
+  }
+
+  if (!MadeChange)
+    return false;
+
+  promoteCounterLoadStores(F);
+  return true;
+}
+
+void InstrProfiling::promoteCounterLoadStores(Function *F) {
+
+  if ((DoCounterPromotion.getNumOccurrences() == 0 &&
+       !Options.DoCounterPromotion) ||
+      !DoCounterPromotion)
+    return;
+
+  DominatorTree DT(*F);
+  LoopInfo LI(DT);
+  DenseMap<Loop *, SmallVector<std::pair<Instruction *, Instruction *>, 8>>
+      LoopPromotionCandidates;
+
+  for (auto LoadStore : PromotionCandidates) {
+    auto *CounterLoad = LoadStore.first;
+    auto *CounterStore = LoadStore.second;
+    BasicBlock *BB = CounterLoad->getParent();
+    Loop *ParentLoop = LI.getLoopFor(BB);
+    if (!ParentLoop)
+      continue;
+    LoopPromotionCandidates[ParentLoop].emplace_back(CounterLoad, CounterStore);
+  }
+
+  SmallVector<Loop *, 4> Loops = LI.getLoopsInPreorder();
+
+  for (auto *Loop : Loops) {
+    PGOCounterPromoter Promoter(LoopPromotionCandidates[Loop], *Loop);
+    Promoter.run();
+  }
+}
+
 bool InstrProfiling::run(Module &M, const TargetLibraryInfo &TLI) {
   bool MadeChange = false;
 
   this->M = &M;
   this->TLI = &TLI;
   NamesVar = nullptr;
   NamesSize = 0;
   ProfileDataMap.clear();
for (Function &F : M) {
 
     // Value profiling intrinsic lowering requires per-function profile data
     // variable to be created first.
     if (FirstProfIncInst != nullptr)
       static_cast<void>(getOrCreateRegionCounters(FirstProfIncInst));
   }
 
   for (Function &F : M)
-    for (BasicBlock &BB : F)
-      for (auto I = BB.begin(), E = BB.end(); I != E;) {
-        auto Instr = I++;
-        InstrProfIncrementInst *Inc = castToIncrementInst(&*Instr);
-        if (Inc) {
-          lowerIncrement(Inc);
-          MadeChange = true;
-        } else if (auto *Ind = dyn_cast<InstrProfValueProfileInst>(Instr)) {
-          lowerValueProfileInst(Ind);
-          MadeChange = true;
-        }
-      }
+    MadeChange |= lowerIntrinsics(&F);
 
   if (GlobalVariable *CoverageNamesVar =
           M.getNamedGlobal(getCoverageUnusedNamesVarName())) {
     lowerCoverageData(CoverageNamesVar);
     MadeChange = true;
   }
 
   if (!MadeChange)

 }
 
 void InstrProfiling::lowerIncrement(InstrProfIncrementInst *Inc) {
   GlobalVariable *Counters = getOrCreateRegionCounters(Inc);
 
   IRBuilder<> Builder(Inc);
   uint64_t Index = Inc->getIndex()->getZExtValue();
   Value *Addr = Builder.CreateConstInBoundsGEP2_64(Counters, 0, Index);
-  Value *Count = Builder.CreateLoad(Addr, "pgocount");
-  Count = Builder.CreateAdd(Count, Inc->getStep());
-  Inc->replaceAllUsesWith(Builder.CreateStore(Count, Addr));
+  Value *Load = Builder.CreateLoad(Addr, "pgocount");
+  auto *Count = Builder.CreateAdd(Load, Inc->getStep());
+  auto *Store = Builder.CreateStore(Count, Addr);
+  Inc->replaceAllUsesWith(Store);
+  PromotionCandidates.emplace_back(cast<Instruction>(Load), Store);
   Inc->eraseFromParent();
 }
 
 void InstrProfiling::lowerCoverageData(GlobalVariable *CoverageNamesVar) {
   ConstantArray *Names =
       cast<ConstantArray>(CoverageNamesVar->getInitializer());
   for (unsigned I = 0, E = Names->getNumOperands(); I < E; ++I) {
     Constant *NC = Names->getOperand(I);

test/Transforms/PGOProfile/counter_promo.ll

+; RUN: opt < %s -pgo-instr-gen -instrprof -do-counter-promotion=true -S | FileCheck --check-prefix=PROMO %s
+; RUN: opt < %s --passes=pgo-instr-gen,instrprof -do-counter-promotion=true -S | FileCheck --check-prefix=PROMO %s
+@g = common global i32 0, align 4
+
+define void @foo(i32 %n, i32 %N) {
+; PROMO-LABEL: @foo
+bb:
+  %tmp = add nsw i32 %n, 1
+  %tmp1 = add nsw i32 %n, -1
+  br label %bb2
+
+bb2:                                              ; preds = %bb9, %bb
+  %i.0 = phi i32 [ 0, %bb ], [ %tmp10, %bb9 ]
+  %tmp3 = icmp slt i32 %i.0, %tmp
+  br i1 %tmp3, label %bb4, label %bb5
+
+bb4:                                              ; preds = %bb2
+  tail call void @bar(i32 1)
+  br label %bb9
+
+bb5:                                              ; preds = %bb2
+  %tmp6 = icmp slt i32 %i.0, %tmp1
+  br i1 %tmp6, label %bb7, label %bb8
+
+bb7:                                              ; preds = %bb5
+  tail call void @bar(i32 2)
+  br label %bb9
+
+bb8:                                              ; preds = %bb5
+  tail call void @bar(i32 3)
+  br label %bb9
+
+bb9:                                              ; preds = %bb8, %bb7, %bb4
+  %tmp10 = add nsw i32 %i.0, 1
+  %tmp11 = icmp slt i32 %tmp10, %N
+  br i1 %tmp11, label %bb2, label %bb12
+
+bb12:                                             ; preds = %bb9
+  ret void
+; PROMO:  %pgocount.promoted = load {{.*}} @__profc_foo{{.*}} 0)
+; PROMO-NEXT: add 
+; PROMO-NEXT: store {{.*}}@__profc_foo{{.*}}0)
+; PROMO-NEXT:  %pgocount.promoted{{.*}} = load {{.*}} @__profc_foo{{.*}} 1)
+; PROMO-NEXT: add 
+; PROMO-NEXT: store {{.*}}@__profc_foo{{.*}}1)
+; PROMO-NEXT:  %pgocount.promoted{{.*}} = load {{.*}} @__profc_foo{{.*}} 2)
+; PROMO-NEXT: add 
+; PROMO-NEXT: store {{.*}}@__profc_foo{{.*}}2)
+; PROMO-NEXT:  %pgocount3 = load {{.*}} @__profc_foo{{.*}} 3)
+; PROMO-NEXT: add 
+; PROMO-NEXT: store {{.*}}@__profc_foo{{.*}}3)
+
+}
+
+declare void @bar(i32)

test/Transforms/PGOProfile/counter_promo_mexits.ll

+; RUN: opt < %s -pgo-instr-gen -instrprof -do-counter-promotion=true -speculative-counter-promotion -S | FileCheck --check-prefix=PROMO %s
+; RUN: opt < %s --passes=pgo-instr-gen,instrprof -do-counter-promotion=true -speculative-counter-promotion -S | FileCheck --check-prefix=PROMO %s
+
+@g = common local_unnamed_addr global i32 0, align 4
+
+define void @foo(i32 %arg) local_unnamed_addr {
+; PROMO-LABEL: @foo
+bb:
+  %tmp = add nsw i32 %arg, -1
+  br label %bb1
+bb1:                                              ; preds = %bb11, %bb
+  %tmp2 = phi i32 [ 0, %bb ], [ %tmp12, %bb11 ]
+  %tmp3 = icmp sgt i32 %tmp2, %arg
+  br i1 %tmp3, label %bb7, label %bb4
+
+bb4:                                              ; preds = %bb1
+  tail call void @bar(i32 1)
+  %tmp5 = load i32, i32* @g, align 4
+  %tmp6 = icmp sgt i32 %tmp5, 100
+  br i1 %tmp6, label %bb15_0, label %bb11
+
+bb7:                                              ; preds = %bb1
+  %tmp8 = icmp slt i32 %tmp2, %tmp
+  br i1 %tmp8, label %bb9, label %bb10
+
+bb9:                                              ; preds = %bb7
+  tail call void @bar(i32 2)
+  br label %bb11
+
+bb10:                                             ; preds = %bb7
+  tail call void @bar(i32 3)
+  br label %bb11
+
+bb11:                                             ; preds = %bb10, %bb9, %bb4
+  %tmp12 = add nuw nsw i32 %tmp2, 1
+  %tmp13 = icmp slt i32 %tmp2, 99
+  br i1 %tmp13, label %bb1, label %bb14
+
+bb14:                                             ; preds = %bb11
+; PROMO-LABEL: bb14:
+  tail call void @bar(i32 0)
+  br label %bb15
+; PROMO:  %pgocount.promoted{{.*}} = load {{.*}} @__profc_foo{{.*}} 0)
+; PROMO-NEXT: add 
+; PROMO-NEXT: store {{.*}}@__profc_foo{{.*}}0)
+; PROMO-NEXT:  %pgocount.promoted{{.*}} = load {{.*}} @__profc_foo{{.*}} 1)
+; PROMO-NEXT: add 
+; PROMO-NEXT: store {{.*}}@__profc_foo{{.*}}1)
+; PROMO-NEXT:  %pgocount.promoted{{.*}} = load {{.*}} @__profc_foo{{.*}} 2)
+; PROMO-NEXT: add 
+; PROMO-NEXT: store {{.*}}@__profc_foo{{.*}}2)
+; PROMO-NEXT:  %pgocount{{.*}} = load {{.*}} @__profc_foo{{.*}} 3)
+; PROMO-NEXT: add 
+; PROMO-NEXT: store {{.*}}@__profc_foo{{.*}}3)
+
+
+bb15_0:                                             ; preds = %bb11
+; PROMO-LABEL: bb15_0:
+  br label %bb15
+; PROMO:  %pgocount.promoted{{.*}} = load {{.*}} @__profc_foo{{.*}} 0)
+; PROMO-NEXT: add 
+; PROMO-NEXT: store {{.*}}@__profc_foo{{.*}}0)
+; PROMO-NEXT:  %pgocount.promoted{{.*}} = load {{.*}} @__profc_foo{{.*}} 1)
+; PROMO-NEXT: add 
+; PROMO-NEXT: store {{.*}}@__profc_foo{{.*}}1)
+; PROMO-NEXT:  %pgocount.promoted{{.*}} = load {{.*}} @__profc_foo{{.*}} 2)
+; PROMO-NEXT: add 
+; PROMO-NEXT: store {{.*}}@__profc_foo{{.*}}2)
+; PROMO-NEXT:  %pgocount{{.*}} = load {{.*}} @__profc_foo{{.*}} 4)
+; PROMO-NEXT: add 
+; PROMO-NEXT: store {{.*}}@__profc_foo{{.*}}4)
+
+
+bb15:                                             ; preds = %bb14, %bb4
+  tail call void @bar(i32 1)
+  ret void
+}
+
+declare void @bar(i32) local_unnamed_addr

test/profile/Linux/counter_promo_for.c

+// RUN: rm -fr %t.promo.prof
+// RUN: rm -fr %t.nopromo.prof
+// RUN: %clang_pgogen=%t.promo.prof/ -o %t.promo.gen -O2 %s
+// RUN: %clang_pgogen=%t.promo.prof/ -o %t.promo.gen.ll -emit-llvm -S -O2 %s
+// RUN: cat %t.promo.gen.ll | FileCheck --check-prefix=PROMO %s
+// RUN: %run %t.promo.gen
+// RUN: llvm-profdata merge -o %t.promo.profdata %t.promo.prof/
+// RUN: llvm-profdata show --counts --all-functions %t.promo.profdata  > %t.promo.dump
+// RUN: %clang_pgogen=%t.nopromo.prof/ -mllvm -do-counter-promotion=false -o %t.nopromo.gen -O2 %s
+// RUN: %clang_pgogen=%t.nopromo.prof/ -mllvm -do-counter-promotion=false -o %t.nopromo.gen.ll -emit-llvm -S -O2 %s
+// RUN: cat %t.nopromo.gen.ll | FileCheck --check-prefix=NOPROMO %s
+// RUN: %run %t.nopromo.gen
+// RUN: llvm-profdata merge -o %t.nopromo.profdata %t.nopromo.prof/
+// RUN: llvm-profdata show --counts --all-functions %t.nopromo.profdata  > %t.nopromo.dump
+// RUN: diff %t.promo.profdata %t.nopromo.profdata
+
+int g;
+__attribute__((noinline)) void bar(int i) { g += i; }
+
+__attribute__((noinline)) void foo(int n, int N) {
+// PROMO-LABEL: @foo
+// PROMO: load{{.*}}@__profc_foo{{.*}} 0){{.*}}
+// PROMO-NEXT: add
+// PROMO-NEXT: store{{.*}}@__profc_foo{{.*}} 0){{.*}}
+// PROMO-NEXT: load{{.*}}@__profc_foo{{.*}} 1){{.*}}
+// PROMO-NEXT: add
+// PROMO-NEXT: store{{.*}}@__profc_foo{{.*}} 1){{.*}}
+// PROMO-NEXT: load{{.*}}@__profc_foo{{.*}} 2){{.*}}
+// PROMO-NEXT: add
+// PROMO-NEXT: store{{.*}}@__profc_foo{{.*}} 2){{.*}}
+// PROMO: load{{.*}}@__profc_foo{{.*}} 3){{.*}}
+// PROMO-NEXT: add
+// PROMO-NEXT: store{{.*}}@__profc_foo{{.*}} 3){{.*}}
+//
+// NOPROMO-LABEL: @foo
+// NOPROMO: load{{.*}}@__profc_foo{{.*}} 0){{.*}}
+// NOPROMO-NEXT: add
+// NOPROMO-NEXT: store{{.*}}@__profc_foo{{.*}} 0){{.*}}
+// NOPROMO: load{{.*}}@__profc_foo{{.*}} 1){{.*}}
+// NOPROMO-NEXT: add
+// NOPROMO-NEXT: store{{.*}}@__profc_foo{{.*}} 1){{.*}}
+// NOPROMO: load{{.*}}@__profc_foo{{.*}} 2){{.*}}
+// NOPROMO-NEXT: add
+// NOPROMO-NEXT: store{{.*}}@__profc_foo{{.*}} 2){{.*}}
+  int i;
+  for (i = 0; i < N; i++) {
+    if (i < n + 1)
+      bar(1);
+    else if (i < n - 1)
+      bar(2);
+    else
+      bar(3);
+  }
+}
+
+int main() {
+  foo(10, 20); 
+  return 0;
+}

test/profile/Linux/counter_promo_while.c

+// RUN: rm -fr %t.promo.prof
+// RUN: rm -fr %t.nopromo.prof
+// RUN: %clang_pgogen=%t.promo.prof/ -o %t.promo.gen -O2 %s
+// RUN: %clang_pgogen=%t.promo.prof/ -o %t.promo.gen.ll -emit-llvm -S -O2 %s
+// RUN: cat %t.promo.gen.ll | FileCheck --check-prefix=PROMO %s
+// RUN: %run %t.promo.gen
+// RUN: llvm-profdata merge -o %t.promo.profdata %t.promo.prof/
+// RUN: llvm-profdata show --counts --all-functions %t.promo.profdata  > %t.promo.dump
+// RUN: %clang_pgogen=%t.nopromo.prof/ -mllvm -do-counter-promotion=false -o %t.nopromo.gen -O2 %s
+// RUN: %clang_pgogen=%t.nopromo.prof/ -mllvm -do-counter-promotion=false -o %t.nopromo.gen.ll -emit-llvm -S -O2 %s
+// RUN: cat %t.nopromo.gen.ll | FileCheck --check-prefix=NOPROMO %s
+// RUN: %run %t.nopromo.gen
+// RUN: llvm-profdata merge -o %t.nopromo.profdata %t.nopromo.prof/
+// RUN: llvm-profdata show --counts --all-functions %t.nopromo.profdata  > %t.nopromo.dump
+// RUN: diff %t.promo.profdata %t.nopromo.profdata
+int g;
+__attribute__((noinline)) void bar(int i) { g += i; }
+__attribute__((noinline)) void foo(int n, int N) {
+// PROMO-LABEL: @foo
+// PROMO: load{{.*}}@__profc_foo{{.*}} 0){{.*}}
+// PROMO-NEXT: add
+// PROMO-NEXT: store{{.*}}@__profc_foo{{.*}} 0){{.*}}
+// PROMO-NEXT: load{{.*}}@__profc_foo{{.*}} 1){{.*}}
+// PROMO-NEXT: add
+// PROMO-NEXT: store{{.*}}@__profc_foo{{.*}} 1){{.*}}
+// PROMO-NEXT: load{{.*}}@__profc_foo{{.*}} 2){{.*}}
+// PROMO-NEXT: add
+// PROMO-NEXT: store{{.*}}@__profc_foo{{.*}} 2){{.*}}
+//
+// NOPROMO-LABEL: @foo
+// NOPROMO: load{{.*}}@__profc_foo{{.*}} 0){{.*}}
+// NOPROMO-NEXT: add
+// NOPROMO-NEXT: store{{.*}}@__profc_foo{{.*}} 0){{.*}}
+// NOPROMO: load{{.*}}@__profc_foo{{.*}} 1){{.*}}
+// NOPROMO-NEXT: add
+// NOPROMO-NEXT: store{{.*}}@__profc_foo{{.*}} 1){{.*}}
+// NOPROMO: load{{.*}}@__profc_foo{{.*}} 2){{.*}}
+// NOPROMO-NEXT: add
+// NOPROMO-NEXT: store{{.*}}@__profc_foo{{.*}} 2){{.*}}
+  int i = 0;
+  while (i < N) {
+    if (i < n + 1)
+      bar(1);
+    else if (i < n - 1)
+      bar(2);
+    else
+      bar(3);
+    i++;
+  }
+}
+
+int main() {
+  foo(10, 20);
+  return 0;
+}