[Coverage] Add support for Branch Coverage in LLVM Source-Based Code Coverage

This is an enhancement to LLVM Source-Based Code Coverage in clang to track how
many times individual branch-generating conditions are taken (evaluate to TRUE)
and not taken (evaluate to FALSE).  Individual conditions may comprise larger
boolean expressions using boolean logical operators.  This functionality is
very similar to what is supported by GCOV except that it is very closely
anchored to the ASTs.

Differential Revision: https://reviews.llvm.org/D84467

7 files changed, 407 insertions, 42 deletions

diff --git a/clang/lib/CodeGen/CGExprScalar.cpp b/clang/lib/CodeGen/CGExprScalar.cpp
index afb03774132e..d6d5ec544c08 100644
--- a/clang/lib/CodeGen/CGExprScalar.cpp
+++ b/clang/lib/CodeGen/CGExprScalar.cpp
@@ -4191,6 +4191,7 @@ Value *ScalarExprEmitter::VisitBinLAnd(const BinaryOperator *E) {
     return Builder.CreateSExt(And, ConvertType(E->getType()), "sext");
   }
 
+  bool InstrumentRegions = CGF.CGM.getCodeGenOpts().hasProfileClangInstr();
   llvm::Type *ResTy = ConvertType(E->getType());
 
   // If we have 0 && RHS, see if we can elide RHS, if so, just return 0.
@@ -4201,6 +4202,22 @@ Value *ScalarExprEmitter::VisitBinLAnd(const BinaryOperator *E) {
       CGF.incrementProfileCounter(E);
 
       Value *RHSCond = CGF.EvaluateExprAsBool(E->getRHS());
+
+      // If we're generating for profiling or coverage, generate a branch to a
+      // block that increments the RHS counter needed to track branch condition
+      // coverage. In this case, use "FBlock" as both the final "TrueBlock" and
+      // "FalseBlock" after the increment is done.
+      if (InstrumentRegions &&
+          CodeGenFunction::isInstrumentedCondition(E->getRHS())) {
+        llvm::BasicBlock *FBlock = CGF.createBasicBlock("land.end");
+        llvm::BasicBlock *RHSBlockCnt = CGF.createBasicBlock("land.rhscnt");
+        Builder.CreateCondBr(RHSCond, RHSBlockCnt, FBlock);
+        CGF.EmitBlock(RHSBlockCnt);
+        CGF.incrementProfileCounter(E->getRHS());
+        CGF.EmitBranch(FBlock);
+        CGF.EmitBlock(FBlock);
+      }
+
       // ZExt result to int or bool.
       return Builder.CreateZExtOrBitCast(RHSCond, ResTy, "land.ext");
     }
@@ -4237,6 +4254,19 @@ Value *ScalarExprEmitter::VisitBinLAnd(const BinaryOperator *E) {
   // Reaquire the RHS block, as there may be subblocks inserted.
   RHSBlock = Builder.GetInsertBlock();
 
+  // If we're generating for profiling or coverage, generate a branch on the
+  // RHS to a block that increments the RHS true counter needed to track branch
+  // condition coverage.
+  if (InstrumentRegions &&
+      CodeGenFunction::isInstrumentedCondition(E->getRHS())) {
+    llvm::BasicBlock *RHSBlockCnt = CGF.createBasicBlock("land.rhscnt");
+    Builder.CreateCondBr(RHSCond, RHSBlockCnt, ContBlock);
+    CGF.EmitBlock(RHSBlockCnt);
+    CGF.incrementProfileCounter(E->getRHS());
+    CGF.EmitBranch(ContBlock);
+    PN->addIncoming(RHSCond, RHSBlockCnt);
+  }
+
   // Emit an unconditional branch from this block to ContBlock.
   {
     // There is no need to emit line number for unconditional branch.
@@ -4277,6 +4307,7 @@ Value *ScalarExprEmitter::VisitBinLOr(const BinaryOperator *E) {
     return Builder.CreateSExt(Or, ConvertType(E->getType()), "sext");
   }
 
+  bool InstrumentRegions = CGF.CGM.getCodeGenOpts().hasProfileClangInstr();
   llvm::Type *ResTy = ConvertType(E->getType());
 
   // If we have 1 || RHS, see if we can elide RHS, if so, just return 1.
@@ -4287,6 +4318,22 @@ Value *ScalarExprEmitter::VisitBinLOr(const BinaryOperator *E) {
       CGF.incrementProfileCounter(E);
 
       Value *RHSCond = CGF.EvaluateExprAsBool(E->getRHS());
+
+      // If we're generating for profiling or coverage, generate a branch to a
+      // block that increments the RHS counter need to track branch condition
+      // coverage. In this case, use "FBlock" as both the final "TrueBlock" and
+      // "FalseBlock" after the increment is done.
+      if (InstrumentRegions &&
+          CodeGenFunction::isInstrumentedCondition(E->getRHS())) {
+        llvm::BasicBlock *FBlock = CGF.createBasicBlock("lor.end");
+        llvm::BasicBlock *RHSBlockCnt = CGF.createBasicBlock("lor.rhscnt");
+        Builder.CreateCondBr(RHSCond, FBlock, RHSBlockCnt);
+        CGF.EmitBlock(RHSBlockCnt);
+        CGF.incrementProfileCounter(E->getRHS());
+        CGF.EmitBranch(FBlock);
+        CGF.EmitBlock(FBlock);
+      }
+
       // ZExt result to int or bool.
       return Builder.CreateZExtOrBitCast(RHSCond, ResTy, "lor.ext");
     }
@@ -4327,6 +4374,19 @@ Value *ScalarExprEmitter::VisitBinLOr(const BinaryOperator *E) {
   // Reaquire the RHS block, as there may be subblocks inserted.
   RHSBlock = Builder.GetInsertBlock();
 
+  // If we're generating for profiling or coverage, generate a branch on the
+  // RHS to a block that increments the RHS true counter needed to track branch
+  // condition coverage.
+  if (InstrumentRegions &&
+      CodeGenFunction::isInstrumentedCondition(E->getRHS())) {
+    llvm::BasicBlock *RHSBlockCnt = CGF.createBasicBlock("lor.rhscnt");
+    Builder.CreateCondBr(RHSCond, ContBlock, RHSBlockCnt);
+    CGF.EmitBlock(RHSBlockCnt);
+    CGF.incrementProfileCounter(E->getRHS());
+    CGF.EmitBranch(ContBlock);
+    PN->addIncoming(RHSCond, RHSBlockCnt);
+  }
+
   // Emit an unconditional branch from this block to ContBlock.  Insert an entry
   // into the phi node for the edge with the value of RHSCond.
   CGF.EmitBlock(ContBlock);
diff --git a/clang/lib/CodeGen/CGStmt.cpp b/clang/lib/CodeGen/CGStmt.cpp
index d67e73a2ec3b..a1a72a9f668d 100644
--- a/clang/lib/CodeGen/CGStmt.cpp
+++ b/clang/lib/CodeGen/CGStmt.cpp
@@ -1441,7 +1441,7 @@ void CodeGenFunction::EmitCaseStmt(const CaseStmt &S,
       SwitchWeights->push_back(getProfileCount(NextCase));
     if (CGM.getCodeGenOpts().hasProfileClangInstr()) {
       CaseDest = createBasicBlock("sw.bb");
-      EmitBlockWithFallThrough(CaseDest, &S);
+      EmitBlockWithFallThrough(CaseDest, CurCase);
     }
     // Since this loop is only executed when the CaseStmt has no attributes
     // use a hard-coded value.
diff --git a/clang/lib/CodeGen/CodeGenFunction.cpp b/clang/lib/CodeGen/CodeGenFunction.cpp
index a8a91c59ff2d..49f13323297c 100644
--- a/clang/lib/CodeGen/CodeGenFunction.cpp
+++ b/clang/lib/CodeGen/CodeGenFunction.cpp
@@ -1501,6 +1501,90 @@ bool CodeGenFunction::ConstantFoldsToSimpleInteger(const Expr *Cond,
   return true;
 }
 
+/// Determine whether the given condition is an instrumentable condition
+/// (i.e. no "&&" or "||").
+bool CodeGenFunction::isInstrumentedCondition(const Expr *C) {
+  // Bypass simplistic logical-NOT operator before determining whether the
+  // condition contains any other logical operator.
+  if (const UnaryOperator *UnOp = dyn_cast<UnaryOperator>(C->IgnoreParens()))
+    if (UnOp->getOpcode() == UO_LNot)
+      C = UnOp->getSubExpr();
+
+  const BinaryOperator *BOp = dyn_cast<BinaryOperator>(C->IgnoreParens());
+  return (!BOp || !BOp->isLogicalOp());
+}
+
+/// EmitBranchToCounterBlock - Emit a conditional branch to a new block that
+/// increments a profile counter based on the semantics of the given logical
+/// operator opcode.  This is used to instrument branch condition coverage for
+/// logical operators.
+void CodeGenFunction::EmitBranchToCounterBlock(
+    const Expr *Cond, BinaryOperator::Opcode LOp, llvm::BasicBlock *TrueBlock,
+    llvm::BasicBlock *FalseBlock, uint64_t TrueCount /* = 0 */,
+    Stmt::Likelihood LH /* =None */, const Expr *CntrIdx /* = nullptr */) {
+  // If not instrumenting, just emit a branch.
+  bool InstrumentRegions = CGM.getCodeGenOpts().hasProfileClangInstr();
+  if (!InstrumentRegions || !isInstrumentedCondition(Cond))
+    return EmitBranchOnBoolExpr(Cond, TrueBlock, FalseBlock, TrueCount, LH);
+
+  llvm::BasicBlock *ThenBlock = NULL;
+  llvm::BasicBlock *ElseBlock = NULL;
+  llvm::BasicBlock *NextBlock = NULL;
+
+  // Create the block we'll use to increment the appropriate counter.
+  llvm::BasicBlock *CounterIncrBlock = createBasicBlock("lop.rhscnt");
+
+  // Set block pointers according to Logical-AND (BO_LAnd) semantics. This
+  // means we need to evaluate the condition and increment the counter on TRUE:
+  //
+  // if (Cond)
+  //   goto CounterIncrBlock;
+  // else
+  //   goto FalseBlock;
+  //
+  // CounterIncrBlock:
+  //   Counter++;
+  //   goto TrueBlock;
+
+  if (LOp == BO_LAnd) {
+    ThenBlock = CounterIncrBlock;
+    ElseBlock = FalseBlock;
+    NextBlock = TrueBlock;
+  }
+
+  // Set block pointers according to Logical-OR (BO_LOr) semantics. This means
+  // we need to evaluate the condition and increment the counter on FALSE:
+  //
+  // if (Cond)
+  //   goto TrueBlock;
+  // else
+  //   goto CounterIncrBlock;
+  //
+  // CounterIncrBlock:
+  //   Counter++;
+  //   goto FalseBlock;
+
+  else if (LOp == BO_LOr) {
+    ThenBlock = TrueBlock;
+    ElseBlock = CounterIncrBlock;
+    NextBlock = FalseBlock;
+  } else {
+    llvm_unreachable("Expected Opcode must be that of a Logical Operator");
+  }
+
+  // Emit Branch based on condition.
+  EmitBranchOnBoolExpr(Cond, ThenBlock, ElseBlock, TrueCount, LH);
+
+  // Emit the block containing the counter increment(s).
+  EmitBlock(CounterIncrBlock);
+
+  // Increment corresponding counter; if index not provided, use Cond as index.
+  incrementProfileCounter(CntrIdx ? CntrIdx : Cond);
+
+  // Go to the next block.
+  EmitBranch(NextBlock);
+}
+
 /// EmitBranchOnBoolExpr - Emit a branch on a boolean condition (e.g. for an if
 /// statement) to the specified blocks.  Based on the condition, this might try
 /// to simplify the codegen of the conditional based on the branch.
@@ -1523,8 +1607,8 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond,
           ConstantBool) {
         // br(1 && X) -> br(X).
         incrementProfileCounter(CondBOp);
-        return EmitBranchOnBoolExpr(CondBOp->getRHS(), TrueBlock, FalseBlock,
-                                    TrueCount, LH);
+        return EmitBranchToCounterBlock(CondBOp->getRHS(), BO_LAnd, TrueBlock,
+                                        FalseBlock, TrueCount, LH);
       }
 
       // If we have "X && 1", simplify the code to use an uncond branch.
@@ -1532,8 +1616,8 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond,
       if (ConstantFoldsToSimpleInteger(CondBOp->getRHS(), ConstantBool) &&
           ConstantBool) {
         // br(X && 1) -> br(X).
-        return EmitBranchOnBoolExpr(CondBOp->getLHS(), TrueBlock, FalseBlock,
-                                    TrueCount, LH);
+        return EmitBranchToCounterBlock(CondBOp->getLHS(), BO_LAnd, TrueBlock,
+                                        FalseBlock, TrueCount, LH, CondBOp);
       }
 
       // Emit the LHS as a conditional.  If the LHS conditional is false, we
@@ -1559,8 +1643,8 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond,
 
       // Any temporaries created here are conditional.
       eval.begin(*this);
-      EmitBranchOnBoolExpr(CondBOp->getRHS(), TrueBlock, FalseBlock, TrueCount,
-                           LH);
+      EmitBranchToCounterBlock(CondBOp->getRHS(), BO_LAnd, TrueBlock,
+                               FalseBlock, TrueCount, LH);
       eval.end(*this);
 
       return;
@@ -1574,8 +1658,8 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond,
           !ConstantBool) {
         // br(0 || X) -> br(X).
         incrementProfileCounter(CondBOp);
-        return EmitBranchOnBoolExpr(CondBOp->getRHS(), TrueBlock, FalseBlock,
-                                    TrueCount, LH);
+        return EmitBranchToCounterBlock(CondBOp->getRHS(), BO_LOr, TrueBlock,
+                                        FalseBlock, TrueCount, LH);
       }
 
       // If we have "X || 0", simplify the code to use an uncond branch.
@@ -1583,8 +1667,8 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond,
       if (ConstantFoldsToSimpleInteger(CondBOp->getRHS(), ConstantBool) &&
           !ConstantBool) {
         // br(X || 0) -> br(X).
-        return EmitBranchOnBoolExpr(CondBOp->getLHS(), TrueBlock, FalseBlock,
-                                    TrueCount, LH);
+        return EmitBranchToCounterBlock(CondBOp->getLHS(), BO_LOr, TrueBlock,
+                                        FalseBlock, TrueCount, LH, CondBOp);
       }
 
       // Emit the LHS as a conditional.  If the LHS conditional is true, we
@@ -1613,8 +1697,8 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond,
 
       // Any temporaries created here are conditional.
       eval.begin(*this);
-      EmitBranchOnBoolExpr(CondBOp->getRHS(), TrueBlock, FalseBlock, RHSCount,
-                           LH);
+      EmitBranchToCounterBlock(CondBOp->getRHS(), BO_LOr, TrueBlock, FalseBlock,
+                               RHSCount, LH);
 
       eval.end(*this);
 
diff --git a/clang/lib/CodeGen/CodeGenFunction.h b/clang/lib/CodeGen/CodeGenFunction.h
index 142cf5d83273..9d11466f69ce 100644
--- a/clang/lib/CodeGen/CodeGenFunction.h
+++ b/clang/lib/CodeGen/CodeGenFunction.h
@@ -4394,6 +4394,21 @@ public:
   bool ConstantFoldsToSimpleInteger(const Expr *Cond, llvm::APSInt &Result,
                                     bool AllowLabels = false);
 
+  /// isInstrumentedCondition - Determine whether the given condition is an
+  /// instrumentable condition (i.e. no "&&" or "||").
+  static bool isInstrumentedCondition(const Expr *C);
+
+  /// EmitBranchToCounterBlock - Emit a conditional branch to a new block that
+  /// increments a profile counter based on the semantics of the given logical
+  /// operator opcode.  This is used to instrument branch condition coverage
+  /// for logical operators.
+  void EmitBranchToCounterBlock(const Expr *Cond, BinaryOperator::Opcode LOp,
+                                llvm::BasicBlock *TrueBlock,
+                                llvm::BasicBlock *FalseBlock,
+                                uint64_t TrueCount = 0,
+                                Stmt::Likelihood LH = Stmt::LH_None,
+                                const Expr *CntrIdx = nullptr);
+
   /// EmitBranchOnBoolExpr - Emit a branch on a boolean condition (e.g. for an
   /// if statement) to the specified blocks.  Based on the condition, this might
   /// try to simplify the codegen of the conditional based on the branch.
diff --git a/clang/lib/CodeGen/CodeGenPGO.cpp b/clang/lib/CodeGen/CodeGenPGO.cpp
index c11d99a348d1..052d58a04a14 100644
--- a/clang/lib/CodeGen/CodeGenPGO.cpp
+++ b/clang/lib/CodeGen/CodeGenPGO.cpp
@@ -160,10 +160,13 @@ struct MapRegionCounters : public RecursiveASTVisitor<MapRegionCounters> {
   PGOHash Hash;
   /// The map of statements to counters.
   llvm::DenseMap<const Stmt *, unsigned> &CounterMap;
+  /// The profile version.
+  uint64_t ProfileVersion;
 
-  MapRegionCounters(PGOHashVersion HashVersion,
+  MapRegionCounters(PGOHashVersion HashVersion, uint64_t ProfileVersion,
                     llvm::DenseMap<const Stmt *, unsigned> &CounterMap)
-      : NextCounter(0), Hash(HashVersion), CounterMap(CounterMap) {}
+      : NextCounter(0), Hash(HashVersion), CounterMap(CounterMap),
+        ProfileVersion(ProfileVersion) {}
 
   // Blocks and lambdas are handled as separate functions, so we need not
   // traverse them in the parent context.
@@ -203,6 +206,18 @@ struct MapRegionCounters : public RecursiveASTVisitor<MapRegionCounters> {
     return Type;
   }
 
+  /// The RHS of all logical operators gets a fresh counter in order to count
+  /// how many times the RHS evaluates to true or false, depending on the
+  /// semantics of the operator. This is only valid for ">= v7" of the profile
+  /// version so that we facilitate backward compatibility.
+  bool VisitBinaryOperator(BinaryOperator *S) {
+    if (ProfileVersion >= llvm::IndexedInstrProf::Version7)
+      if (S->isLogicalOp() &&
+          CodeGenFunction::isInstrumentedCondition(S->getRHS()))
+        CounterMap[S->getRHS()] = NextCounter++;
+    return Base::VisitBinaryOperator(S);
+  }
+
   /// Include \p S in the function hash.
   bool VisitStmt(Stmt *S) {
     auto Type = updateCounterMappings(S);
@@ -814,11 +829,14 @@ void CodeGenPGO::mapRegionCounters(const Decl *D) {
   // Use the latest hash version when inserting instrumentation, but use the
   // version in the indexed profile if we're reading PGO data.
   PGOHashVersion HashVersion = PGO_HASH_LATEST;
-  if (auto *PGOReader = CGM.getPGOReader())
+  uint64_t ProfileVersion = llvm::IndexedInstrProf::Version;
+  if (auto *PGOReader = CGM.getPGOReader()) {
     HashVersion = getPGOHashVersion(PGOReader, CGM);
+    ProfileVersion = PGOReader->getVersion();
+  }
 
   RegionCounterMap.reset(new llvm::DenseMap<const Stmt *, unsigned>);
-  MapRegionCounters Walker(HashVersion, *RegionCounterMap);
+  MapRegionCounters Walker(HashVersion, ProfileVersion, *RegionCounterMap);
   if (const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(D))
     Walker.TraverseDecl(const_cast<FunctionDecl *>(FD));
   else if (const ObjCMethodDecl *MD = dyn_cast_or_null<ObjCMethodDecl>(D))
diff --git a/clang/lib/CodeGen/CoverageMappingGen.cpp b/clang/lib/CodeGen/CoverageMappingGen.cpp
index 8d9c1979d87c..c474546d4abf 100644
--- a/clang/lib/CodeGen/CoverageMappingGen.cpp
+++ b/clang/lib/CodeGen/CoverageMappingGen.cpp
@@ -92,8 +92,12 @@ namespace {
 
 /// A region of source code that can be mapped to a counter.
 class SourceMappingRegion {
+  /// Primary Counter that is also used for Branch Regions for "True" branches.
   Counter Count;
 
+  /// Secondary Counter used for Branch Regions for "False" branches.
+  Optional<Counter> FalseCount;
+
   /// The region's starting location.
   Optional<SourceLocation> LocStart;
 
@@ -114,8 +118,20 @@ public:
       : Count(Count), LocStart(LocStart), LocEnd(LocEnd),
         DeferRegion(DeferRegion), GapRegion(GapRegion) {}
 
+  SourceMappingRegion(Counter Count, Optional<Counter> FalseCount,
+                      Optional<SourceLocation> LocStart,
+                      Optional<SourceLocation> LocEnd, bool DeferRegion = false,
+                      bool GapRegion = false)
+      : Count(Count), FalseCount(FalseCount), LocStart(LocStart),
+        LocEnd(LocEnd), DeferRegion(DeferRegion), GapRegion(GapRegion) {}
+
   const Counter &getCounter() const { return Count; }
 
+  const Counter &getFalseCounter() const {
+    assert(FalseCount && "Region has no alternate counter");
+    return *FalseCount;
+  }
+
   void setCounter(Counter C) { Count = C; }
 
   bool hasStartLoc() const { return LocStart.hasValue(); }
@@ -146,6 +162,8 @@ public:
   bool isGap() const { return GapRegion; }
 
   void setGap(bool Gap) { GapRegion = Gap; }
+
+  bool isBranch() const { return FalseCount.hasValue(); }
 };
 
 /// Spelling locations for the start and end of a source region.
@@ -425,6 +443,10 @@ public:
         MappingRegions.push_back(CounterMappingRegion::makeGapRegion(
             Region.getCounter(), *CovFileID, SR.LineStart, SR.ColumnStart,
             SR.LineEnd, SR.ColumnEnd));
+      } else if (Region.isBranch()) {
+        MappingRegions.push_back(CounterMappingRegion::makeBranchRegion(
+            Region.getCounter(), Region.getFalseCounter(), *CovFileID,
+            SR.LineStart, SR.ColumnStart, SR.LineEnd, SR.ColumnEnd));
       } else {
         MappingRegions.push_back(CounterMappingRegion::makeRegion(
             Region.getCounter(), *CovFileID, SR.LineStart, SR.ColumnStart,
@@ -563,12 +585,16 @@ struct CounterCoverageMappingBuilder
   /// Returns the index on the stack where the region was pushed. This can be
   /// used with popRegions to exit a "scope", ending the region that was pushed.
   size_t pushRegion(Counter Count, Optional<SourceLocation> StartLoc = None,
-                    Optional<SourceLocation> EndLoc = None) {
-    if (StartLoc) {
+                    Optional<SourceLocation> EndLoc = None,
+                    Optional<Counter> FalseCount = None) {
+
+    if (StartLoc && !FalseCount.hasValue()) {
       MostRecentLocation = *StartLoc;
       completeDeferred(Count, MostRecentLocation);
     }
-    RegionStack.emplace_back(Count, StartLoc, EndLoc);
+
+    RegionStack.emplace_back(Count, FalseCount, StartLoc, EndLoc,
+                             FalseCount.hasValue());
 
     return RegionStack.size() - 1;
   }
@@ -658,49 +684,64 @@ struct CounterCoverageMappingBuilder
         SourceLocation EndLoc = Region.hasEndLoc()
                                     ? Region.getEndLoc()
                                     : RegionStack[ParentIndex].getEndLoc();
+        bool isBranch = Region.isBranch();
         size_t StartDepth = locationDepth(StartLoc);
         size_t EndDepth = locationDepth(EndLoc);
         while (!SM.isWrittenInSameFile(StartLoc, EndLoc)) {
           bool UnnestStart = StartDepth >= EndDepth;
           bool UnnestEnd = EndDepth >= StartDepth;
           if (UnnestEnd) {
-            // The region ends in a nested file or macro expansion. Create a
-            // separate region for each expansion.
+            // The region ends in a nested file or macro expansion. If the
+            // region is not a branch region, create a separate region for each
+            // expansion, and for all regions, update the EndLoc. Branch
+            // regions should not be split in order to keep a straightforward
+            // correspondance between the region and its associated branch
+            // condition, even if the condition spans multiple depths.
             SourceLocation NestedLoc = getStartOfFileOrMacro(EndLoc);
             assert(SM.isWrittenInSameFile(NestedLoc, EndLoc));
 
-            if (!isRegionAlreadyAdded(NestedLoc, EndLoc))
-              SourceRegions.emplace_back(Region.getCounter(), NestedLoc, EndLoc);
+            if (!isBranch && !isRegionAlreadyAdded(NestedLoc, EndLoc))
+              SourceRegions.emplace_back(Region.getCounter(), NestedLoc,
+                                         EndLoc);
 
             EndLoc = getPreciseTokenLocEnd(getIncludeOrExpansionLoc(EndLoc));
             if (EndLoc.isInvalid())
-              llvm::report_fatal_error("File exit not handled before popRegions");
+              llvm::report_fatal_error(
+                  "File exit not handled before popRegions");
             EndDepth--;
           }
           if (UnnestStart) {
-            // The region begins in a nested file or macro expansion. Create a
-            // separate region for each expansion.
+            // The region ends in a nested file or macro expansion. If the
+            // region is not a branch region, create a separate region for each
+            // expansion, and for all regions, update the StartLoc. Branch
+            // regions should not be split in order to keep a straightforward
+            // correspondance between the region and its associated branch
+            // condition, even if the condition spans multiple depths.
             SourceLocation NestedLoc = getEndOfFileOrMacro(StartLoc);
             assert(SM.isWrittenInSameFile(StartLoc, NestedLoc));
 
-            if (!isRegionAlreadyAdded(StartLoc, NestedLoc))
-              SourceRegions.emplace_back(Region.getCounter(), StartLoc, NestedLoc);
+            if (!isBranch && !isRegionAlreadyAdded(StartLoc, NestedLoc))
+              SourceRegions.emplace_back(Region.getCounter(), StartLoc,
+                                         NestedLoc);
 
             StartLoc = getIncludeOrExpansionLoc(StartLoc);
             if (StartLoc.isInvalid())
-              llvm::report_fatal_error("File exit not handled before popRegions");
+              llvm::report_fatal_error(
+                  "File exit not handled before popRegions");
             StartDepth--;
           }
         }
         Region.setStartLoc(StartLoc);
         Region.setEndLoc(EndLoc);
 
-        MostRecentLocation = EndLoc;
-        // If this region happens to span an entire expansion, we need to make
-        // sure we don't overlap the parent region with it.
-        if (StartLoc == getStartOfFileOrMacro(StartLoc) &&
-            EndLoc == getEndOfFileOrMacro(EndLoc))
-          MostRecentLocation = getIncludeOrExpansionLoc(EndLoc);
+        if (!isBranch) {
+          MostRecentLocation = EndLoc;
+          // If this region happens to span an entire expansion, we need to
+          // make sure we don't overlap the parent region with it.
+          if (StartLoc == getStartOfFileOrMacro(StartLoc) &&
+              EndLoc == getEndOfFileOrMacro(EndLoc))
+            MostRecentLocation = getIncludeOrExpansionLoc(EndLoc);
+        }
 
         assert(SM.isWrittenInSameFile(Region.getBeginLoc(), EndLoc));
         assert(SpellingRegion(SM, Region).isInSourceOrder());
@@ -759,14 +800,61 @@ struct CounterCoverageMappingBuilder
     return ExitCount;
   }
 
+  /// Determine whether the given condition can be constant folded.
+  bool ConditionFoldsToBool(const Expr *Cond) {
+    Expr::EvalResult Result;
+    return (Cond->EvaluateAsInt(Result, CVM.getCodeGenModule().getContext()));
+  }
+
+  /// Create a Branch Region around an instrumentable condition for coverage
+  /// and add it to the function's SourceRegions.  A branch region tracks a
+  /// "True" counter and a "False" counter for boolean expressions that
+  /// result in the generation of a branch.
+  void createBranchRegion(const Expr *C, Counter TrueCnt, Counter FalseCnt) {
+    // Check for NULL conditions.
+    if (!C)
+      return;
+
+    // Ensure we are an instrumentable condition (i.e. no "&&" or "||").  Push
+    // region onto RegionStack but immediately pop it (which adds it to the
+    // function's SourceRegions) because it doesn't apply to any other source
+    // code other than the Condition.
+    if (CodeGenFunction::isInstrumentedCondition(C)) {
+      // If a condition can fold to true or false, the corresponding branch
+      // will be removed.  Create a region with both counters hard-coded to
+      // zero. This allows us to visualize them in a special way.
+      // Alternatively, we can prevent any optimization done via
+      // constant-folding by ensuring that ConstantFoldsToSimpleInteger() in
+      // CodeGenFunction.c always returns false, but that is very heavy-handed.
+      if (ConditionFoldsToBool(C))
+        popRegions(pushRegion(Counter::getZero(), getStart(C), getEnd(C),
+                              Counter::getZero()));
+      else
+        // Otherwise, create a region with the True counter and False counter.
+        popRegions(pushRegion(TrueCnt, getStart(C), getEnd(C), FalseCnt));
+    }
+  }
+
+  /// Create a Branch Region around a SwitchCase for code coverage
+  /// and add it to the function's SourceRegions.
+  void createSwitchCaseRegion(const SwitchCase *SC, Counter TrueCnt,
+                              Counter FalseCnt) {
+    // Push region onto RegionStack but immediately pop it (which adds it to
+    // the function's SourceRegions) because it doesn't apply to any other
+    // source other than the SwitchCase.
+    popRegions(pushRegion(TrueCnt, getStart(SC), SC->getColonLoc(), FalseCnt));
+  }
+
   /// Check whether a region with bounds \c StartLoc and \c EndLoc
   /// is already added to \c SourceRegions.
-  bool isRegionAlreadyAdded(SourceLocation StartLoc, SourceLocation EndLoc) {
+  bool isRegionAlreadyAdded(SourceLocation StartLoc, SourceLocation EndLoc,
+                            bool isBranch = false) {
     return SourceRegions.rend() !=
            std::find_if(SourceRegions.rbegin(), SourceRegions.rend(),
                         [&](const SourceMappingRegion &Region) {
                           return Region.getBeginLoc() == StartLoc &&
-                                 Region.getEndLoc() == EndLoc;
+                                 Region.getEndLoc() == EndLoc &&
+                                 Region.isBranch() == isBranch;
                         });
   }
 
@@ -783,7 +871,7 @@ struct CounterCoverageMappingBuilder
     if (getRegion().hasEndLoc() &&
         MostRecentLocation == getEndOfFileOrMacro(MostRecentLocation) &&
         isRegionAlreadyAdded(getStartOfFileOrMacro(MostRecentLocation),
-                             MostRecentLocation))
+                             MostRecentLocation, getRegion().isBranch()))
       MostRecentLocation = getIncludeOrExpansionLoc(MostRecentLocation);
   }
 
@@ -827,9 +915,14 @@ struct CounterCoverageMappingBuilder
         // The most nested region for each start location is the one with the
         // correct count. We avoid creating redundant regions by stopping once
         // we've seen this region.
-        if (StartLocs.insert(Loc).second)
-          SourceRegions.emplace_back(I.getCounter(), Loc,
-                                     getEndOfFileOrMacro(Loc));
+        if (StartLocs.insert(Loc).second) {
+          if (I.isBranch())
+            SourceRegions.emplace_back(I.getCounter(), I.getFalseCounter(), Loc,
+                                       getEndOfFileOrMacro(Loc), I.isBranch());
+          else
+            SourceRegions.emplace_back(I.getCounter(), Loc,
+                                       getEndOfFileOrMacro(Loc));
+        }
         Loc = getIncludeOrExpansionLoc(Loc);
       }
       I.setStartLoc(getPreciseTokenLocEnd(Loc));
@@ -1070,6 +1163,10 @@ struct CounterCoverageMappingBuilder
         addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount));
     if (OutCount != ParentCount)
       pushRegion(OutCount);
+
+    // Create Branch Region around condition.
+    createBranchRegion(S->getCond(), BodyCount,
+                       subtractCounters(CondCount, BodyCount));
   }
 
   void VisitDoStmt(const DoStmt *S) {
@@ -1091,6 +1188,10 @@ struct CounterCoverageMappingBuilder
         addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount));
     if (OutCount != ParentCount)
       pushRegion(OutCount);
+
+    // Create Branch Region around condition.
+    createBranchRegion(S->getCond(), BodyCount,
+                       subtractCounters(CondCount, BodyCount));
   }
 
   void VisitForStmt(const ForStmt *S) {
@@ -1138,6 +1239,10 @@ struct CounterCoverageMappingBuilder
                                    subtractCounters(CondCount, BodyCount));
     if (OutCount != ParentCount)
       pushRegion(OutCount);
+
+    // Create Branch Region around condition.
+    createBranchRegion(S->getCond(), BodyCount,
+                       subtractCounters(CondCount, BodyCount));
   }
 
   void VisitCXXForRangeStmt(const CXXForRangeStmt *S) {
@@ -1167,6 +1272,10 @@ struct CounterCoverageMappingBuilder
         addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount));
     if (OutCount != ParentCount)
       pushRegion(OutCount);
+
+    // Create Branch Region around condition.
+    createBranchRegion(S->getCond(), BodyCount,
+                       subtractCounters(LoopCount, BodyCount));
   }
 
   void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S) {
@@ -1231,6 +1340,7 @@ struct CounterCoverageMappingBuilder
       BreakContinueStack.back().ContinueCount = addCounters(
           BreakContinueStack.back().ContinueCount, BC.ContinueCount);
 
+    Counter ParentCount = getRegion().getCounter();
     Counter ExitCount = getRegionCounter(S);
     SourceLocation ExitLoc = getEnd(S);
     pushRegion(ExitCount);
@@ -1239,6 +1349,28 @@ struct CounterCoverageMappingBuilder
     // in a different file.
     MostRecentLocation = getStart(S);
     handleFileExit(ExitLoc);
+
+    // 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 = addCounters(CaseCountSum, getRegionCounter(Case));
+      createSwitchCaseRegion(
+          Case, getRegionCounter(Case),
+          subtractCounters(ParentCount, getRegionCounter(Case)));
+    }
+
+    // If no explicit default case exists, create a branch region to represent
+    // the hidden branch, which will be added later by the CodeGen. This region
+    // will be associated with the switch statement's condition.
+    if (!HasDefaultCase) {
+      Counter DefaultTrue = subtractCounters(ParentCount, CaseCountSum);
+      Counter DefaultFalse = subtractCounters(ParentCount, DefaultTrue);
+      createBranchRegion(S->getCond(), DefaultTrue, DefaultFalse);
+    }
   }
 
   void VisitSwitchCase(const SwitchCase *S) {
@@ -1299,6 +1431,10 @@ struct CounterCoverageMappingBuilder
 
     if (OutCount != ParentCount)
       pushRegion(OutCount);
+
+    // Create Branch Region around condition.
+    createBranchRegion(S->getCond(), ThenCount,
+                       subtractCounters(ParentCount, ThenCount));
   }
 
   void VisitCXXTryStmt(const CXXTryStmt *S) {
@@ -1342,6 +1478,10 @@ struct CounterCoverageMappingBuilder
     extendRegion(E->getFalseExpr());
     propagateCounts(subtractCounters(ParentCount, TrueCount),
                     E->getFalseExpr());
+
+    // Create Branch Region around condition.
+    createBranchRegion(E->getCond(), TrueCount,
+                       subtractCounters(ParentCount, TrueCount));
   }
 
   void VisitBinLAnd(const BinaryOperator *E) {
@@ -1349,8 +1489,26 @@ struct CounterCoverageMappingBuilder
     propagateCounts(getRegion().getCounter(), E->getLHS());
     handleFileExit(getEnd(E->getLHS()));
 
+    // Counter tracks the right hand side of a logical and operator.
     extendRegion(E->getRHS());
     propagateCounts(getRegionCounter(E), E->getRHS());
+
+    // Extract the RHS's Execution Counter.
+    Counter RHSExecCnt = getRegionCounter(E);
+
+    // Extract the RHS's "True" Instance Counter.
+    Counter RHSTrueCnt = getRegionCounter(E->getRHS());
+
+    // Extract the Parent Region Counter.
+    Counter ParentCnt = getRegion().getCounter();
+
+    // Create Branch Region around LHS condition.
+    createBranchRegion(E->getLHS(), RHSExecCnt,
+                       subtractCounters(ParentCnt, RHSExecCnt));
+
+    // Create Branch Region around RHS condition.
+    createBranchRegion(E->getRHS(), RHSTrueCnt,
+                       subtractCounters(RHSExecCnt, RHSTrueCnt));
   }
 
   void VisitBinLOr(const BinaryOperator *E) {
@@ -1358,8 +1516,26 @@ struct CounterCoverageMappingBuilder
     propagateCounts(getRegion().getCounter(), E->getLHS());
     handleFileExit(getEnd(E->getLHS()));
 
+    // Counter tracks the right hand side of a logical or operator.
     extendRegion(E->getRHS());
     propagateCounts(getRegionCounter(E), E->getRHS());
+
+    // Extract the RHS's Execution Counter.
+    Counter RHSExecCnt = getRegionCounter(E);
+
+    // Extract the RHS's "False" Instance Counter.
+    Counter RHSFalseCnt = getRegionCounter(E->getRHS());
+
+    // Extract the Parent Region Counter.
+    Counter ParentCnt = getRegion().getCounter();
+
+    // Create Branch Region around LHS condition.
+    createBranchRegion(E->getLHS(), subtractCounters(ParentCnt, RHSExecCnt),
+                       RHSExecCnt);
+
+    // Create Branch Region around RHS condition.
+    createBranchRegion(E->getRHS(), subtractCounters(RHSExecCnt, RHSFalseCnt),
+                       RHSFalseCnt);
   }
 
   void VisitLambdaExpr(const LambdaExpr *LE) {
@@ -1396,11 +1572,20 @@ static void dump(llvm::raw_ostream &OS, StringRef FunctionName,
     case CounterMappingRegion::GapRegion:
       OS << "Gap,";
       break;
+    case CounterMappingRegion::BranchRegion:
+      OS << "Branch,";
+      break;
     }
 
     OS << "File " << R.FileID << ", " << R.LineStart << ":" << R.ColumnStart
        << " -> " << R.LineEnd << ":" << R.ColumnEnd << " = ";
     Ctx.dump(R.Count, OS);
+
+    if (R.Kind == CounterMappingRegion::BranchRegion) {
+      OS << ", ";
+      Ctx.dump(R.FalseCount, OS);
+    }
+
     if (R.Kind == CounterMappingRegion::ExpansionRegion)
       OS << " (Expanded file = " << R.ExpandedFileID << ")";
     OS << "\n";
diff --git a/clang/lib/CodeGen/CoverageMappingGen.h b/clang/lib/CodeGen/CoverageMappingGen.h
index 645ad23a9ccd..9d0aa3b9cad1 100644
--- a/clang/lib/CodeGen/CoverageMappingGen.h
+++ b/clang/lib/CodeGen/CoverageMappingGen.h
@@ -122,6 +122,9 @@ public:
   /// Return the coverage mapping translation unit file id
   /// for the given file.
   unsigned getFileID(const FileEntry *File);
+
+  /// Return an interface into CodeGenModule.
+  CodeGenModule &getCodeGenModule() { return CGM; }
 };
 
 /// Organizes the per-function state that is used while generating