[InstrProf][WIP] Implement boolean counters in coverage

[gulfem]

Summary

This patch inserts 1-byte boolean counters instead of an 8-byte counters
into llvm profiles for source-based code coverage. The origial idea was
proposed as "block-cov" for PGO, and this patch reuses that idea for coverage.
https://groups.google.com/g/llvm-dev/c/r03Z6JoN7d4

This is a WIP prototype implementation which only implements boolean
counters for only a handful of control-flow statements (while, for, if, switch).
I will continue to extend it for other control-flow statements.

The current 8-byte counters mechanism add counters to minimal regions,
and infer the counters in the remaining regions via adding or
subtracting counters. Whenever there is control-flow merge, it adds
the counters from all the incoming regions. When we use boolean counters,
we can use a new counter expression called or instead of an and for such
cases. Therefore, this patch adds an Or kind into CounterExpression.

Similarly, 8-byte counters mechanism infers the counters in some regions
by subtracting counters. For example, it infers the counter in the if.else
region by subtracting the counters between if.entry and if.then regions
in an if statement. However, we are not going to be able to infer counters
by subtracting two execution counts when using boolean counters.
Therefore, we need to insert additional counters for the cases where we
need to subtract counters.

[gulfem]

Created a duplicate review by mistake.

clang/lib/CodeGen/CGStmt.cpp

 
 using namespace clang;
 using namespace CodeGen;
 
 //===----------------------------------------------------------------------===//
 //                              Statement Emission
 //===----------------------------------------------------------------------===//
 
+namespace llvm {
+extern cl::opt<bool> EnableBooleanCounters;
+}
+
 void CodeGenFunction::EmitStopPoint(const Stmt *S) {
   if (CGDebugInfo *DI = getDebugInfo()) {
     SourceLocation Loc;
     Loc = S->getBeginLoc();
     DI->EmitLocation(Builder, Loc);
 
     LastStopPoint = Loc;
   }
void CodeGenFunction::EmitIfStmt(const IfStmt &S) {
   Stmt::Likelihood LH = Stmt::LH_None;
   uint64_t Count = getProfileCount(S.getThen());
   if (!Count && CGM.getCodeGenOpts().OptimizationLevel)
     LH = Stmt::getLikelihood(S.getThen(), S.getElse());
   EmitBranchOnBoolExpr(S.getCond(), ThenBlock, ElseBlock, Count, LH);
 
   // Emit the 'then' code.
   EmitBlock(ThenBlock);
+  if (llvm::EnableBooleanCounters)
+    incrementProfileCounter(S.getThen());
+  else
     incrementProfileCounter(&S);
   {
     RunCleanupsScope ThenScope(*this);
     EmitStmt(S.getThen());
   }
   EmitBranch(ContBlock);
 
   // Emit the 'else' code if present.
   if (const Stmt *Else = S.getElse()) {
     {
       // There is no need to emit line number for an unconditional branch.
       auto NL = ApplyDebugLocation::CreateEmpty(*this);
       EmitBlock(ElseBlock);
     }
+    // When boolean counters are enabled, add a counter to else block.
+    if (llvm::EnableBooleanCounters)
+      incrementProfileCounter(Else);
     {
       RunCleanupsScope ElseScope(*this);
       EmitStmt(Else);
     }
     {
       // There is no need to emit line number for an unconditional branch.
       auto NL = ApplyDebugLocation::CreateEmpty(*this);
       EmitBranch(ContBlock);
     }
   }
 
   // Emit the continuation block for code after the if.
   EmitBlock(ContBlock, true);
+  // When there is no else, add a counter to continuation block.
+  if (llvm::EnableBooleanCounters && !S.getElse())
+    incrementProfileCounter(&S);
 }
 
 void CodeGenFunction::EmitWhileStmt(const WhileStmt &S,
                                     ArrayRef<const Attr *> WhileAttrs) {
   // Emit the header for the loop, which will also become
   // the continue target.
   JumpDest LoopHeader = getJumpDestInCurrentScope("while.cond");
   EmitBlock(LoopHeader.getBlock());
CGM.getDiags().Report(
         << SourceRange(S.getWhileLoc(), S.getRParenLoc());
   }
 
   // Emit the loop body.  We have to emit this in a cleanup scope
   // because it might be a singleton DeclStmt.
   {
     RunCleanupsScope BodyScope(*this);
     EmitBlock(LoopBody);
+    if (llvm::EnableBooleanCounters)
+      incrementProfileCounter(S.getBody());
+    else
       incrementProfileCounter(&S);
     EmitStmt(S.getBody());
   }
 
   BreakContinueStack.pop_back();
 
   // Immediately force cleanup.
   ConditionScope.ForceCleanup();
 
   EmitStopPoint(&S);
   // Branch to the loop header again.
   EmitBranch(LoopHeader.getBlock());
 
   LoopStack.pop();
 
   // Emit the exit block.
   EmitBlock(LoopExit.getBlock(), true);
 
   // The LoopHeader typically is just a branch if we skipped emitting
   // a branch, try to erase it.
   if (!EmitBoolCondBranch)
     SimplifyForwardingBlocks(LoopHeader.getBlock());
+
+  // When boolean counters are enabled, add a counter to continuation block.
+  if (llvm::EnableBooleanCounters)
+    incrementProfileCounter(&S);
 }
 
 void CodeGenFunction::EmitDoStmt(const DoStmt &S,
                                  ArrayRef<const Attr *> DoAttrs) {
   JumpDest LoopExit = getJumpDestInCurrentScope("do.end");
   JumpDest LoopCond = getJumpDestInCurrentScope("do.cond");
 
   uint64_t ParentCount = getCurrentProfileCount();
if (ExitBlock != LoopExit.getBlock()) {
       EmitBranchThroughCleanup(LoopExit);
     }
 
     EmitBlock(ForBody);
   } else {
     // Treat it as a non-zero constant.  Don't even create a new block for the
     // body, just fall into it.
   }
-  incrementProfileCounter(&S);
 
+  if (llvm::EnableBooleanCounters)
+    incrementProfileCounter(S.getBody());
+  else
+    incrementProfileCounter(&S);
   {
     // Create a separate cleanup scope for the body, in case it is not
     // a compound statement.
     RunCleanupsScope BodyScope(*this);
     EmitStmt(S.getBody());
   }
 
   // If there is an increment, emit it next.
void CodeGenFunction::EmitForStmt(const ForStmt &S,
   EmitBranch(CondBlock);
 
   ForScope.ForceCleanup();
 
   LoopStack.pop();
 
   // Emit the fall-through block.
   EmitBlock(LoopExit.getBlock(), true);
+
+  // When boolean counters are enabled, add a counter to continuation block.
+  if (llvm::EnableBooleanCounters)
+    incrementProfileCounter(&S);
 }
 
 void
 CodeGenFunction::EmitCXXForRangeStmt(const CXXForRangeStmt &S,
                                      ArrayRef<const Attr *> ForAttrs) {
   JumpDest LoopExit = getJumpDestInCurrentScope("for.end");
 
   LexicalScope ForScope(*this, S.getSourceRange());

clang/lib/CodeGen/CodeGenModule.cpp

void CodeGenModule::Release() {
   }
   EmitCtorList(GlobalCtors, "llvm.global_ctors");
   EmitCtorList(GlobalDtors, "llvm.global_dtors");
   EmitGlobalAnnotations();
   EmitStaticExternCAliases();
   checkAliases();
   EmitDeferredUnusedCoverageMappings();
   CodeGenPGO(*this).setValueProfilingFlag(getModule());
+  CodeGenPGO(*this).setProfileVersion(getModule());
   if (CoverageMapping)
     CoverageMapping->emit();
   if (CodeGenOpts.SanitizeCfiCrossDso) {
     CodeGenFunction(*this).EmitCfiCheckFail();
     CodeGenFunction(*this).EmitCfiCheckStub();
   }
   emitAtAvailableLinkGuard();
   if (Context.getTargetInfo().getTriple().isWasm() &&

clang/lib/CodeGen/CodeGenPGO.h

void emitEmptyCounterMapping(const Decl *D, StringRef FuncName,
                                llvm::GlobalValue::LinkageTypes Linkage);
   // Insert instrumentation or attach profile metadata at value sites
   void valueProfile(CGBuilderTy &Builder, uint32_t ValueKind,
                     llvm::Instruction *ValueSite, llvm::Value *ValuePtr);
 
   // Set a module flag indicating if value profiling is enabled.
   void setValueProfilingFlag(llvm::Module &M);
 
+  void setProfileVersion(llvm::Module &M);
+
 private:
   void setFuncName(llvm::Function *Fn);
   void setFuncName(StringRef Name, llvm::GlobalValue::LinkageTypes Linkage);
   void mapRegionCounters(const Decl *D);
   void computeRegionCounts(const Decl *D);
   void applyFunctionAttributes(llvm::IndexedInstrProfReader *PGOReader,
                                llvm::Function *Fn);
   void loadRegionCounts(llvm::IndexedInstrProfReader *PGOReader,

clang/lib/CodeGen/CodeGenPGO.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "CodeGenPGO.h"
 #include "CodeGenFunction.h"
 #include "CoverageMappingGen.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/AST/StmtVisitor.h"
+#include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MD5.h"
 
+namespace llvm {
+cl::opt<bool> EnableBooleanCounters("enable-boolean-counters",
+                                    llvm::cl::ZeroOrMore,
+                                    llvm::cl::desc("Enable boolean counters"),
+                                    llvm::cl::Hidden, llvm::cl::init(false));
+} // namespace llvm
+
 static llvm::cl::opt<bool>
     EnableValueProfiling("enable-value-profiling", llvm::cl::ZeroOrMore,
                          llvm::cl::desc("Enable value profiling"),
                          llvm::cl::Hidden, llvm::cl::init(false));
 
 using namespace clang;
 using namespace CodeGen;
 
struct MapRegionCounters : public RecursiveASTVisitor<MapRegionCounters> {
   }
 
   bool TraverseIfStmt(IfStmt *If) {
     // If we used the V1 hash, use the default traversal.
     if (Hash.getHashVersion() == PGO_HASH_V1)
       return Base::TraverseIfStmt(If);
 
     // Otherwise, keep track of which branch we're in while traversing.
+    // When boolean counters are enabled and if has an else part,
+    // do not add a counter for IfStmt, but still include in the function hash.
+    if (llvm::EnableBooleanCounters && If->getElse()) {
+      auto Type = getHashType(PGO_HASH_V1, If);
+      if (Hash.getHashVersion() != PGO_HASH_V1)
+        Type = getHashType(Hash.getHashVersion(), If);
+      if (Type != PGOHash::None)
+        Hash.combine(Type);
+    } else
       VisitStmt(If);
+
     for (Stmt *CS : If->children()) {
       if (!CS)
         continue;
-      if (CS == If->getThen())
+      if (CS == If->getThen()) {
         Hash.combine(PGOHash::IfThenBranch);
-      else if (CS == If->getElse())
+        if (llvm::EnableBooleanCounters)
+          CounterMap[If->getThen()] = NextCounter++;
+      } else if (CS == If->getElse()) {
         Hash.combine(PGOHash::IfElseBranch);
+        if (llvm::EnableBooleanCounters)
+          CounterMap[If->getElse()] = NextCounter++;
+      }
+      TraverseStmt(CS);
+    }
+    Hash.combine(PGOHash::EndOfScope);
+    return true;
+  }
+
+  bool TraverseWhileStmt(WhileStmt *While) {
+    // If we used the V1 hash, use the default traversal.
+    if (Hash.getHashVersion() == PGO_HASH_V1)
+      return Base::TraverseWhileStmt(While);
+
+    VisitStmt(While);
+    for (Stmt *CS : While->children()) {
+      if (!CS)
+        continue;
+      if (llvm::EnableBooleanCounters && CS == While->getBody())
+        CounterMap[While->getBody()] = NextCounter++;
+      TraverseStmt(CS);
+    }
+
+    if (Hash.getHashVersion() != PGO_HASH_V1)
+      Hash.combine(PGOHash::EndOfScope);
+
+    return true;
+  }
+
+  bool TraverseForStmt(ForStmt *For) {
+    // If we used the V1 hash, use the default traversal.
+    if (Hash.getHashVersion() == PGO_HASH_V1)
+      return Base::TraverseForStmt(For);
+    VisitStmt(For);
+    for (Stmt *CS : For->children()) {
+      if (!CS)
+        continue;
+      if (CS == For->getBody()) {
+        if (llvm::EnableBooleanCounters)
+          CounterMap[For->getBody()] = NextCounter++;
+      }
       TraverseStmt(CS);
     }
+
+    if (Hash.getHashVersion() != PGO_HASH_V1)
       Hash.combine(PGOHash::EndOfScope);
     return true;
   }
 
 // If the statement type \p N is nestable, and its nesting impacts profile
 // stability, define a custom traversal which tracks the end of the statement
 // in the hash (provided we're not using the V1 hash).
 #define DEFINE_NESTABLE_TRAVERSAL(N)                                           \
   bool Traverse##N(N *S) {                                                     \
     Base::Traverse##N(S);                                                      \
     if (Hash.getHashVersion() != PGO_HASH_V1)                                  \
       Hash.combine(PGOHash::EndOfScope);                                       \
     return true;                                                               \
   }
 
-  DEFINE_NESTABLE_TRAVERSAL(WhileStmt)
   DEFINE_NESTABLE_TRAVERSAL(DoStmt)
-  DEFINE_NESTABLE_TRAVERSAL(ForStmt)
   DEFINE_NESTABLE_TRAVERSAL(CXXForRangeStmt)
   DEFINE_NESTABLE_TRAVERSAL(ObjCForCollectionStmt)
   DEFINE_NESTABLE_TRAVERSAL(CXXTryStmt)
   DEFINE_NESTABLE_TRAVERSAL(CXXCatchStmt)
 
   /// Get version \p HashVersion of the PGO hash for \p S.
   PGOHash::HashType getHashType(PGOHashVersion HashVersion, const Stmt *S) {
     switch (S->getStmtClass()) {
void CodeGenPGO::emitCounterIncrement(CGBuilderTy &Builder, const Stmt *S,
 
   unsigned Counter = (*RegionCounterMap)[S];
   auto *I8PtrTy = llvm::Type::getInt8PtrTy(CGM.getLLVMContext());
 
   llvm::Value *Args[] = {llvm::ConstantExpr::getBitCast(FuncNameVar, I8PtrTy),
                          Builder.getInt64(FunctionHash),
                          Builder.getInt32(NumRegionCounters),
                          Builder.getInt32(Counter), StepV};
+
+  if (llvm::EnableBooleanCounters)
+    Builder.CreateCall(CGM.getIntrinsic(llvm::Intrinsic::instrprof_cover),
+                       makeArrayRef(Args, 4));
+  else {
     if (!StepV)
       Builder.CreateCall(CGM.getIntrinsic(llvm::Intrinsic::instrprof_increment),
                          makeArrayRef(Args, 4));
     else
       Builder.CreateCall(
           CGM.getIntrinsic(llvm::Intrinsic::instrprof_increment_step),
           makeArrayRef(Args));
   }
+}
 
 void CodeGenPGO::setValueProfilingFlag(llvm::Module &M) {
   if (CGM.getCodeGenOpts().hasProfileClangInstr())
     M.addModuleFlag(llvm::Module::Warning, "EnableValueProfiling",
                     uint32_t(EnableValueProfiling));
 }
 
+void CodeGenPGO::setProfileVersion(llvm::Module &M) {
+  if (CGM.getCodeGenOpts().hasProfileClangInstr() &&
+      llvm::EnableBooleanCounters) {
+    const StringRef VarName(INSTR_PROF_QUOTE(INSTR_PROF_RAW_VERSION_VAR));
+    llvm::Type *IntTy64 = llvm::Type::getInt64Ty(M.getContext());
+    uint64_t ProfileVersion =
+        (INSTR_PROF_RAW_VERSION | VARIANT_MASK_BYTE_COVERAGE);
+
+    auto IRLevelVersionVariable = new llvm::GlobalVariable(
+        M, IntTy64, true, llvm::GlobalValue::WeakAnyLinkage,
+        llvm::Constant::getIntegerValue(IntTy64,
+                                        llvm::APInt(64, ProfileVersion)),
+        VarName);
+
+    IRLevelVersionVariable->setVisibility(llvm::GlobalValue::DefaultVisibility);
+    llvm::Triple TT(M.getTargetTriple());
+    if (TT.supportsCOMDAT()) {
+      IRLevelVersionVariable->setLinkage(llvm::GlobalValue::ExternalLinkage);
+      IRLevelVersionVariable->setComdat(M.getOrInsertComdat(VarName));
+    }
+  }
+}
+
 // This method either inserts a call to the profile run-time during
 // instrumentation or puts profile data into metadata for PGO use.
 void CodeGenPGO::valueProfile(CGBuilderTy &Builder, uint32_t ValueKind,
     llvm::Instruction *ValueSite, llvm::Value *ValuePtr) {
 
   if (!EnableValueProfiling)
     return;
 

clang/lib/CodeGen/CoverageMappingGen.cpp

 #include "llvm/ProfileData/InstrProfReader.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Path.h"
 
 // This selects the coverage mapping format defined when `InstrProfData.inc`
 // is textually included.
 #define COVMAP_V3
 
+namespace llvm {
+extern cl::opt<bool> EnableBooleanCounters;
+}
+
 static llvm::cl::opt<bool> EmptyLineCommentCoverage(
     "emptyline-comment-coverage",
     llvm::cl::desc("Emit emptylines and comment lines as skipped regions (only "
                    "disable it on test)"),
     llvm::cl::init(true), llvm::cl::Hidden);
 
 using namespace clang;
 using namespace CodeGen;
Counter addCounters(Counter LHS, Counter RHS, bool Simplify = true) {
     return Builder.add(LHS, RHS, Simplify);
   }
 
   Counter addCounters(Counter C1, Counter C2, Counter C3,
                       bool Simplify = true) {
     return addCounters(addCounters(C1, C2, Simplify), C3, Simplify);
   }
 
+  /// Return a counter for the result of \c LHS or \c RHS.
+  Counter orCounters(Counter LHS, Counter RHS) {
+    return Builder.orCounters(LHS, RHS);
+  }
+
+  Counter orCounters(Counter C1, Counter C2, Counter C3) {
+    return orCounters(orCounters(C1, C2), C3);
+  }
+
   /// Return the region counter for the given statement.
   ///
   /// This should only be called on statements that have a dedicated counter.
   Counter getRegionCounter(const Stmt *S) {
     return Counter::getCounter(CounterMap[S]);
   }
 
   /// Push a region onto the stack.
void VisitLabelStmt(const LabelStmt *S) {
     // We can't extendRegion here or we risk overlapping with our new region.
     handleFileExit(Start);
     pushRegion(LabelCount, Start);
     Visit(S->getSubStmt());
   }
 
   void VisitBreakStmt(const BreakStmt *S) {
     assert(!BreakContinueStack.empty() && "break not in a loop or switch!");
+    if (llvm::EnableBooleanCounters)
+      BreakContinueStack.back().BreakCount = orCounters(
+          BreakContinueStack.back().BreakCount, getRegion().getCounter());
+    else
       BreakContinueStack.back().BreakCount = addCounters(
           BreakContinueStack.back().BreakCount, getRegion().getCounter());
     // FIXME: a break in a switch should terminate regions for all preceding
     // case statements, not just the most recent one.
     terminateRegion(S);
   }
 
   void VisitContinueStmt(const ContinueStmt *S) {
     assert(!BreakContinueStack.empty() && "continue stmt not in a loop!");
+    if (llvm::EnableBooleanCounters)
+      BreakContinueStack.back().ContinueCount = orCounters(
+          BreakContinueStack.back().ContinueCount, getRegion().getCounter());
+    else
       BreakContinueStack.back().ContinueCount = addCounters(
           BreakContinueStack.back().ContinueCount, getRegion().getCounter());
     terminateRegion(S);
   }
 
   void VisitCallExpr(const CallExpr *E) {
     VisitStmt(E);
 
     // Terminate the region when we hit a noreturn function.
     // (This is helpful dealing with switch statements.)
     QualType CalleeType = E->getCallee()->getType();
     if (getFunctionExtInfo(*CalleeType).getNoReturn())
       terminateRegion(E);
   }
 
   void VisitWhileStmt(const WhileStmt *S) {
     extendRegion(S);
 
     Counter ParentCount = getRegion().getCounter();
-    Counter BodyCount = getRegionCounter(S);
+    Counter BodyCount = llvm::EnableBooleanCounters
+                            ? getRegionCounter(S->getBody())
+                            : getRegionCounter(S);
 
     // Handle the body first so that we can get the backedge count.
     BreakContinueStack.push_back(BreakContinue());
     extendRegion(S->getBody());
     Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
     BreakContinue BC = BreakContinueStack.pop_back_val();
 
     bool BodyHasTerminateStmt = HasTerminateStmt;
     HasTerminateStmt = false;
 
     // Go back to handle the condition.
     Counter CondCount =
-        addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
+        llvm::EnableBooleanCounters
+            ? orCounters(ParentCount, BackedgeCount, BC.ContinueCount)
+            : addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
+
     propagateCounts(CondCount, S->getCond());
     adjustForOutOfOrderTraversal(getEnd(S));
 
     // The body count applies to the area immediately after the increment.
     auto Gap = findGapAreaBetween(S->getRParenLoc(), getStart(S->getBody()));
     if (Gap)
       fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
 
     Counter OutCount =
-        addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount));
+        llvm::EnableBooleanCounters
+            ? getRegionCounter(S)
+            : addCounters(BC.BreakCount,
+                          subtractCounters(CondCount, BodyCount));
+
     if (OutCount != ParentCount) {
       pushRegion(OutCount);
       GapRegionCounter = OutCount;
       if (BodyHasTerminateStmt)
         HasTerminateStmt = true;
     }
 
     // Create Branch Region around condition.
+    if (!llvm::EnableBooleanCounters)
       createBranchRegion(S->getCond(), BodyCount,
                          subtractCounters(CondCount, BodyCount));
   }
 
   void VisitDoStmt(const DoStmt *S) {
     extendRegion(S);
 
     Counter ParentCount = getRegion().getCounter();
     Counter BodyCount = getRegionCounter(S);
 
struct CounterCoverageMappingBuilder
   }
 
   void VisitForStmt(const ForStmt *S) {
     extendRegion(S);
     if (S->getInit())
       Visit(S->getInit());
 
     Counter ParentCount = getRegion().getCounter();
-    Counter BodyCount = getRegionCounter(S);
+    Counter BodyCount = llvm::EnableBooleanCounters
+                            ? getRegionCounter(S->getBody())
+                            : getRegionCounter(S);
 
     // The loop increment may contain a break or continue.
     if (S->getInc())
       BreakContinueStack.emplace_back();
 
     // Handle the body first so that we can get the backedge count.
     BreakContinueStack.emplace_back();
     extendRegion(S->getBody());
     Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
     BreakContinue BodyBC = BreakContinueStack.pop_back_val();
 
     bool BodyHasTerminateStmt = HasTerminateStmt;
     HasTerminateStmt = false;
 
     // The increment is essentially part of the body but it needs to include
     // the count for all the continue statements.
     BreakContinue IncrementBC;
     if (const Stmt *Inc = S->getInc()) {
+      if (llvm::EnableBooleanCounters)
+        propagateCounts(orCounters(BackedgeCount, BodyBC.ContinueCount), Inc);
+      else
         propagateCounts(addCounters(BackedgeCount, BodyBC.ContinueCount), Inc);
       IncrementBC = BreakContinueStack.pop_back_val();
     }
 
     // Go back to handle the condition.
-    Counter CondCount = addCounters(
+    Counter CondCount =
+        llvm::EnableBooleanCounters
+            ? orCounters(
+                  orCounters(ParentCount, BackedgeCount, BodyBC.ContinueCount),
+                  IncrementBC.ContinueCount)
+            : addCounters(
                   addCounters(ParentCount, BackedgeCount, BodyBC.ContinueCount),
                   IncrementBC.ContinueCount);
+
     if (const Expr *Cond = S->getCond()) {
       propagateCounts(CondCount, Cond);
       adjustForOutOfOrderTraversal(getEnd(S));
     }
 
     // The body count applies to the area immediately after the increment.
     auto Gap = findGapAreaBetween(S->getRParenLoc(), getStart(S->getBody()));
     if (Gap)
       fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
 
-    Counter OutCount = addCounters(BodyBC.BreakCount, IncrementBC.BreakCount,
-                                   subtractCounters(CondCount, BodyCount));
+    Counter OutCount =
+        llvm::EnableBooleanCounters
+            ? getRegionCounter(S)
+            : addCounters(BodyBC.BreakCount, IncrementBC.BreakCount,
     if (OutCount != ParentCount) {
       pushRegion(OutCount);
       GapRegionCounter = OutCount;
       if (BodyHasTerminateStmt)
         HasTerminateStmt = true;
     }
 
     // Create Branch Region around condition.
+    if (!llvm::EnableBooleanCounters)
       createBranchRegion(S->getCond(), BodyCount,
                          subtractCounters(CondCount, BodyCount));
   }
 
   void VisitCXXForRangeStmt(const CXXForRangeStmt *S) {
     extendRegion(S);
     if (S->getInit())
       Visit(S->getInit());
     Visit(S->getLoopVarStmt());
     Visit(S->getRangeStmt());
void VisitSwitchStmt(const SwitchStmt *S) {
     pushRegion(ExitCount);
     GapRegionCounter = ExitCount;
 
     // Ensure that handleFileExit recognizes when the end location is located
     // in a different file.
     MostRecentLocation = getStart(S);
     handleFileExit(ExitLoc);
 
+    // Early return so do not create branch regions when boolean counters are
+    // enabled.
+    if (llvm::EnableBooleanCounters)
+      return;
+
     // Create a Branch Region around each Case. Subtract the case's
     // counter from the Parent counter to track the "False" branch count.
     Counter CaseCountSum;
     bool HasDefaultCase = false;
     const SwitchCase *Case = S->getSwitchCaseList();
     for (; Case; Case = Case->getNextSwitchCase()) {
       HasDefaultCase = HasDefaultCase || isa<DefaultStmt>(Case);
       CaseCountSum =
void VisitIfStmt(const IfStmt *S) {
     if (S->getInit())
       Visit(S->getInit());
 
     // Extend into the condition before we propagate through it below - this is
     // needed to handle macros that generate the "if" but not the condition.
     extendRegion(S->getCond());
 
     Counter ParentCount = getRegion().getCounter();
-    Counter ThenCount = getRegionCounter(S);
+    Counter ThenCount = llvm::EnableBooleanCounters
+                            ? getRegionCounter(S->getThen())
+                            : getRegionCounter(S);
 
     // Emitting a counter for the condition makes it easier to interpret the
     // counter for the body when looking at the coverage.
     propagateCounts(ParentCount, S->getCond());
 
     // The 'then' count applies to the area immediately after the condition.
     auto Gap = findGapAreaBetween(S->getRParenLoc(), getStart(S->getThen()));
     if (Gap)
       fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), ThenCount);
 
     extendRegion(S->getThen());
     Counter OutCount = propagateCounts(ThenCount, S->getThen());
 
-    Counter ElseCount = subtractCounters(ParentCount, ThenCount);
+    Counter ElseCount;
+    if (llvm::EnableBooleanCounters) {
+      if (S->getElse())
+        ElseCount = getRegionCounter(S->getElse());
+    } else
+      ElseCount = subtractCounters(ParentCount, ThenCount);
+
     if (const Stmt *Else = S->getElse()) {
       bool ThenHasTerminateStmt = HasTerminateStmt;
       HasTerminateStmt = false;
 
       // The 'else' count applies to the area immediately after the 'then'.
       Gap = findGapAreaBetween(getEnd(S->getThen()), getStart(Else));
       if (Gap)
         fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), ElseCount);
       extendRegion(Else);
-      OutCount = addCounters(OutCount, propagateCounts(ElseCount, Else));
+      Counter ElseOutCount = propagateCounts(ElseCount, Else);
+      OutCount = llvm::EnableBooleanCounters
+                     ? orCounters(OutCount, ElseOutCount)
+                     : addCounters(OutCount, ElseOutCount);
 
       if (ThenHasTerminateStmt)
         HasTerminateStmt = true;
     } else
-      OutCount = addCounters(OutCount, ElseCount);
+      OutCount = llvm::EnableBooleanCounters ? getRegionCounter(S)
+                                             : addCounters(OutCount, ElseCount);
 
     if (OutCount != ParentCount) {
       pushRegion(OutCount);
       GapRegionCounter = OutCount;
     }
 
     // Create Branch Region around condition.
+    if (!llvm::EnableBooleanCounters)
       createBranchRegion(S->getCond(), ThenCount,
                          subtractCounters(ParentCount, ThenCount));
   }
 
   void VisitCXXTryStmt(const CXXTryStmt *S) {
     extendRegion(S);
     // Handle macros that generate the "try" but not the rest.
     extendRegion(S->getTryBlock());
 
     Counter ParentCount = getRegion().getCounter();

clang/test/CoverageMapping/boolean-counters.cpp

+// RUN: %clang_cc1 -mllvm -emptyline-comment-coverage=false -mllvm -enable-boolean-counters=true -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only -main-file-name return.c %s | FileCheck %s
+
+// CHECK: _Z6testIfi
+int testIf(int x) { // CHECK-NEXT: File 0, [[@LINE]]:19 -> [[@LINE+10]]:2 = #0
+                    // CHECK-NEXT: File 0, [[@LINE+5]]:7 -> [[@LINE+5]]:13 = #0
+                    // CHECK-NEXT: Gap,File 0, [[@LINE+4]]:14 -> [[@LINE+5]]:5 = #2
+                    // CHECK-NEXT: File 0, [[@LINE+4]]:5 -> [[@LINE+4]]:16 = #2
+                    // CHECK-NEXT: File 0, [[@LINE+5]]:3 -> [[@LINE+5]]:16 = #1
+  int result = 0;
+  if (x == 0)
+    result = -1;
+
+  return result;
+}
+
+// CHECK-NEXT: _Z10testIfElsei
+int testIfElse(int x) { // CHECK-NEXT: File 0, [[@LINE]]:23 -> [[@LINE+13]]:2 = #0
+                        // CHECK-NEXT: File 0, [[@LINE+7]]:7 -> [[@LINE+7]]:12 = #0
+                        // CHECK-NEXT: Gap,File 0, [[@LINE+6]]:13 -> [[@LINE+7]]:5 = #1
+                        // CHECK-NEXT: File 0, [[@LINE+6]]:5 -> [[@LINE+6]]:15 = #1
+                        // CHECK-NEXT: Gap,File 0, [[@LINE+5]]:16 -> [[@LINE+7]]:5 = #2
+                        // CHECK-NEXT: File 0, [[@LINE+6]]:5 -> [[@LINE+6]]:19 = #2
+                        // CHECK-NEXT: File 0, [[@LINE+6]]:3 -> [[@LINE+6]]:16 = (#1 || #2)
+  int result = 0;
+  if (x < 0)
+    result = 0;
+  else
+    result = x * x;
+  return result;
+}
+
+// CHECK-NEXT: _Z16testIfElseReturni
+int testIfElseReturn(int x) { // CHECK-NEXT: File 0, [[@LINE]]:29 -> [[@LINE+14]]:2 = #0
+                              // CHECK-NEXT: File 0, [[@LINE+8]]:7 -> [[@LINE+8]]:12 = #0
+                              // CHECK-NEXT: Gap,File 0, [[@LINE+7]]:13 -> [[@LINE+8]]:5 = #1
+                              // CHECK-NEXT: File 0, [[@LINE+7]]:5 -> [[@LINE+7]]:19 = #1
+                              // CHECK-NEXT: Gap,File 0, [[@LINE+6]]:20 -> [[@LINE+8]]:5 = #2
+                              // CHECK-NEXT: File 0, [[@LINE+7]]:5 -> [[@LINE+7]]:13 = #2
+                              // CHECK-NEXT: Gap,File 0, [[@LINE+6]]:14 -> [[@LINE+7]]:3 = #1
+                              // CHECK-NEXT: File 0, [[@LINE+6]]:3 -> [[@LINE+6]]:16 = #1
+  int result = 0;
+  if (x > 0)
+    result = x * x;
+  else
+    return 0;
+  return result;
+}
+
+// CHECK-NEXT: _Z10testSwitchi
+int testSwitch(int x) { // CHECK-NEXT: File 0, [[@LINE]]:23 -> [[@LINE+22]]:2 = #0
+                        // CHECK-NEXT: Gap,File 0, [[@LINE+9]]:14 -> [[@LINE+17]]:15 = 0
+                        // CHECK-NEXT: File 0, [[@LINE+9]]:3 -> [[@LINE+11]]:10 = #2
+                        // CHECK-NEXT: Gap,File 0, [[@LINE+10]]:11 -> [[@LINE+11]]:3 = 0
+                        // CHECK-NEXT: File 0, [[@LINE+10]]:3 -> [[@LINE+12]]:10 = #3
+                        // CHECK-NEXT: Gap,File 0, [[@LINE+11]]:11 -> [[@LINE+12]]:3 = 0
+                        // CHECK-NEXT: File 0, [[@LINE+11]]:3 -> [[@LINE+12]]:15 = #4
+                        // CHECK-NEXT: Gap,File 0, [[@LINE+12]]:4 -> [[@LINE+14]]:3 = #1
+                        // CHECK-NEXT: File 0, [[@LINE+13]]:3 -> [[@LINE+13]]:16 = #1
+  int result;
+  switch (x) {
+  case 1:
+    result = 1;
+    break;
+  case 2:
+    result = 2;
+    break;
+  default:
+    result = 0;
+  }
+
+  return result;
+}
+
+// CHECK-NEXT: _Z9testWhilei
+int testWhile(int x) { // CHECK-NEXT: File 0, [[@LINE]]:22 -> [[@LINE+13]]:2 = #0
+                       // CHECK-NEXT: File 0, [[@LINE+6]]:10 -> [[@LINE+6]]:16 = #0
+                       // CHECK-NEXT: Gap,File 0, [[@LINE+5]]:17 -> [[@LINE+5]]:18 = #2
+                       // CHECK-NEXT: File 0, [[@LINE+4]]:18 -> [[@LINE+7]]:4 = #2
+                       // CHECK-NEXT: File 0, [[@LINE+8]]:3 -> [[@LINE+8]]:13 = #1
+  int i = x;
+  int sum = 0;
+  while (i < 10) {
+    sum += i;
+    i++;
+  }
+
+  return sum;
+}
+
+// CHECK-NEXT: _Z12testContinuei
+int testContinue(int x) { // CHECK-NEXT: File 0, [[@LINE]]:25 -> [[@LINE+21]]:2 = #0
+                          // CHECK-NEXT: File 0, [[@LINE+12]]:10 -> [[@LINE+12]]:16 = ((#0 || #3) || #4)
+                          // CHECK-NEXT: Gap,File 0, [[@LINE+11]]:17 -> [[@LINE+11]]:18 = #2
+                          // CHECK-NEXT: File 0, [[@LINE+10]]:18 -> [[@LINE+15]]:4 = #2
+                          // CHECK-NEXT: File 0, [[@LINE+10]]:9 -> [[@LINE+10]]:15 = #2
+                          // CHECK-NEXT: Gap,File 0, [[@LINE+9]]:16 -> [[@LINE+10]]:7 = #4
+                          // CHECK-NEXT: File 0, [[@LINE+9]]:7 -> [[@LINE+9]]:15 = #4
+                          // CHECK-NEXT: Gap,File 0, [[@LINE+8]]:16 -> [[@LINE+9]]:5 = #3
+                          // CHECK-NEXT: File 0, [[@LINE+8]]:5 -> [[@LINE+10]]:4 = #3
+                          // CHECK-NEXT: Gap,File 0, [[@LINE+9]]:4 -> [[@LINE+11]]:3 = #1
+                          // CHECK-NEXT: File 0, [[@LINE+10]]:3 -> [[@LINE+10]]:13 = #1
+  int i = x;
+  int sum = 0;
+  while (i < 10) {
+    if (i == 4)
+      continue;
+    sum += i;
+    i++;
+  }
+
+  return sum;
+}

llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h

 };
 
 /// A Counter is an abstract value that describes how to compute the
 /// execution count for a region of code using the collected profile count data.
 struct Counter {
   /// The CounterExpression kind (Add or Subtract) is encoded in bit 0 next to
   /// the CounterKind. This means CounterKind has to leave bit 0 free.
   enum CounterKind { Zero, CounterValueReference, Expression };
-  static const unsigned EncodingTagBits = 2;
-  static const unsigned EncodingTagMask = 0x3;
+  static const unsigned EncodingTagBits = 3;
+  static const unsigned EncodingTagMask = 0x7;
   static const unsigned EncodingCounterTagAndExpansionRegionTagBits =
       EncodingTagBits + 1;
 
 private:
   CounterKind Kind = Zero;
   unsigned ID = 0;
 
   Counter(CounterKind Kind, unsigned ID) : Kind(Kind), ID(ID) {}
public:
   static Counter getExpression(unsigned ExpressionId) {
     return Counter(Expression, ExpressionId);
   }
 };
 
 /// A Counter expression is a value that represents an arithmetic operation
 /// with two counters.
 struct CounterExpression {
-  enum ExprKind { Subtract, Add };
+  enum ExprKind { Subtract, Add, Or };
   ExprKind Kind;
   Counter LHS, RHS;
 
   CounterExpression(ExprKind Kind, Counter LHS, Counter RHS)
       : Kind(Kind), LHS(LHS), RHS(RHS) {}
 };
 
 /// A Counter expression builder is used to construct the counter expressions.
public:
   ArrayRef<CounterExpression> getExpressions() const { return Expressions; }
 
   /// Return a counter that represents the expression that adds LHS and RHS.
   Counter add(Counter LHS, Counter RHS, bool Simplify = true);
 
   /// Return a counter that represents the expression that subtracts RHS from
   /// LHS.
   Counter subtract(Counter LHS, Counter RHS, bool Simplify = true);
+
+  /// Return a counter that represents the expression RHS || LHS
+  Counter orCounters(Counter LHS, Counter RHS);
 };
 
 using LineColPair = std::pair<unsigned, unsigned>;
 
 /// A Counter mapping region associates a source range with a specific counter.
 struct CounterMappingRegion {
   enum RegionKind {
     /// A CodeRegion associates some code with a counter

llvm/lib/ProfileData/Coverage/CoverageMapping.cpp

 }
 
 Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS,
                                            bool Simplify) {
   auto Cnt = get(CounterExpression(CounterExpression::Subtract, LHS, RHS));
   return Simplify ? simplify(Cnt) : Cnt;
 }
 
+Counter CounterExpressionBuilder::orCounters(Counter LHS, Counter RHS) {
+  if (LHS.getKind() == Counter::Zero)
+    return Counter::getCounter(RHS.getCounterID());
+  if (RHS.getKind() == Counter::Zero)
+    return Counter::getCounter(LHS.getCounterID());
+  return get(CounterExpression(CounterExpression::Or, LHS, RHS));
+}
+
 void CounterMappingContext::dump(const Counter &C, raw_ostream &OS) const {
   switch (C.getKind()) {
   case Counter::Zero:
     OS << '0';
     return;
   case Counter::CounterValueReference:
     OS << '#' << C.getCounterID();
     break;
   case Counter::Expression: {
     if (C.getExpressionID() >= Expressions.size())
       return;
     const auto &E = Expressions[C.getExpressionID()];
     OS << '(';
     dump(E.LHS, OS);
+    if (E.Kind == CounterExpression::Or)
+      OS << " || ";
+    else
       OS << (E.Kind == CounterExpression::Subtract ? " - " : " + ");
     dump(E.RHS, OS);
     OS << ')';
     break;
   }
   }
   if (CounterValues.empty())
     return;
   Expected<int64_t> Value = evaluate(C);
if (C.getExpressionID() >= Expressions.size())
       return errorCodeToError(errc::argument_out_of_domain);
     const auto &E = Expressions[C.getExpressionID()];
     Expected<int64_t> LHS = evaluate(E.LHS);
     if (!LHS)
       return LHS;
     Expected<int64_t> RHS = evaluate(E.RHS);
     if (!RHS)
       return RHS;
+    if (E.Kind == CounterExpression::Or)
+      return *RHS || *LHS;
+
     return E.Kind == CounterExpression::Subtract ? *LHS - *RHS : *LHS + *RHS;
   }
   }
   llvm_unreachable("Unhandled CounterKind");
 }
 
 unsigned CounterMappingContext::getMaxCounterID(const Counter &C) const {
   switch (C.getKind()) {

llvm/lib/ProfileData/Coverage/CoverageMappingReader.cpp

case Counter::CounterValueReference:
     C = Counter::getCounter(Value >> Counter::EncodingTagBits);
     return Error::success();
   default:
     break;
   }
   Tag -= Counter::Expression;
   switch (Tag) {
   case CounterExpression::Subtract:
-  case CounterExpression::Add: {
+  case CounterExpression::Add:
+  case CounterExpression::Or: {
     auto ID = Value >> Counter::EncodingTagBits;
     if (ID >= Expressions.size())
       return make_error<CoverageMapError>(coveragemap_error::malformed);
     Expressions[ID].Kind = CounterExpression::ExprKind(Tag);
     C = Counter::getExpression(ID);
     break;
   }
   default: