1 files changed, 287 insertions, 31 deletions

diff --git a/contrib/llvm-project/clang/lib/CodeGen/CodeGenPGO.cpp b/contrib/llvm-project/clang/lib/CodeGen/CodeGenPGO.cpp
index d828ac0eb5e9..fb4e86e8bd80 100644
--- a/contrib/llvm-project/clang/lib/CodeGen/CodeGenPGO.cpp
+++ b/contrib/llvm-project/clang/lib/CodeGen/CodeGenPGO.cpp
@@ -21,12 +21,15 @@
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MD5.h"
+#include <optional>
 
 static llvm::cl::opt<bool>
-    EnableValueProfiling("enable-value-profiling", llvm::cl::ZeroOrMore,
+    EnableValueProfiling("enable-value-profiling",
                          llvm::cl::desc("Enable value profiling"),
                          llvm::cl::Hidden, llvm::cl::init(false));
 
+extern llvm::cl::opt<bool> SystemHeadersCoverage;
+
 using namespace clang;
 using namespace CodeGen;
 
@@ -131,7 +134,7 @@ public:
   static_assert(LastHashType <= TooBig, "Too many types in HashType");
 
   PGOHash(PGOHashVersion HashVersion)
-      : Working(0), Count(0), HashVersion(HashVersion), MD5() {}
+      : Working(0), Count(0), HashVersion(HashVersion) {}
   void combine(HashType Type);
   uint64_t finalize();
   PGOHashVersion getHashVersion() const { return HashVersion; }
@@ -160,13 +163,24 @@ struct MapRegionCounters : public RecursiveASTVisitor<MapRegionCounters> {
   PGOHash Hash;
   /// The map of statements to counters.
   llvm::DenseMap<const Stmt *, unsigned> &CounterMap;
+  /// The next bitmap byte index to assign.
+  unsigned NextMCDCBitmapIdx;
+  /// The map of statements to MC/DC bitmap coverage objects.
+  llvm::DenseMap<const Stmt *, unsigned> &MCDCBitmapMap;
+  /// Maximum number of supported MC/DC conditions in a boolean expression.
+  unsigned MCDCMaxCond;
   /// The profile version.
   uint64_t ProfileVersion;
+  /// Diagnostics Engine used to report warnings.
+  DiagnosticsEngine &Diag;
 
   MapRegionCounters(PGOHashVersion HashVersion, uint64_t ProfileVersion,
-                    llvm::DenseMap<const Stmt *, unsigned> &CounterMap)
+                    llvm::DenseMap<const Stmt *, unsigned> &CounterMap,
+                    llvm::DenseMap<const Stmt *, unsigned> &MCDCBitmapMap,
+                    unsigned MCDCMaxCond, DiagnosticsEngine &Diag)
       : NextCounter(0), Hash(HashVersion), CounterMap(CounterMap),
-        ProfileVersion(ProfileVersion) {}
+        NextMCDCBitmapIdx(0), MCDCBitmapMap(MCDCBitmapMap),
+        MCDCMaxCond(MCDCMaxCond), ProfileVersion(ProfileVersion), Diag(Diag) {}
 
   // Blocks and lambdas are handled as separate functions, so we need not
   // traverse them in the parent context.
@@ -206,15 +220,129 @@ struct MapRegionCounters : public RecursiveASTVisitor<MapRegionCounters> {
     return Type;
   }
 
+  /// The following stacks are used with dataTraverseStmtPre() and
+  /// dataTraverseStmtPost() to track the depth of nested logical operators in a
+  /// boolean expression in a function.  The ultimate purpose is to keep track
+  /// of the number of leaf-level conditions in the boolean expression so that a
+  /// profile bitmap can be allocated based on that number.
+  ///
+  /// The stacks are also used to find error cases and notify the user.  A
+  /// standard logical operator nest for a boolean expression could be in a form
+  /// similar to this: "x = a && b && c && (d || f)"
+  unsigned NumCond = 0;
+  bool SplitNestedLogicalOp = false;
+  SmallVector<const Stmt *, 16> NonLogOpStack;
+  SmallVector<const BinaryOperator *, 16> LogOpStack;
+
+  // Hook: dataTraverseStmtPre() is invoked prior to visiting an AST Stmt node.
+  bool dataTraverseStmtPre(Stmt *S) {
+    /// If MC/DC is not enabled, MCDCMaxCond will be set to 0. Do nothing.
+    if (MCDCMaxCond == 0)
+      return true;
+
+    /// At the top of the logical operator nest, reset the number of conditions,
+    /// also forget previously seen split nesting cases.
+    if (LogOpStack.empty()) {
+      NumCond = 0;
+      SplitNestedLogicalOp = false;
+    }
+
+    if (const Expr *E = dyn_cast<Expr>(S)) {
+      const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(E->IgnoreParens());
+      if (BinOp && BinOp->isLogicalOp()) {
+        /// Check for "split-nested" logical operators. This happens when a new
+        /// boolean expression logical-op nest is encountered within an existing
+        /// boolean expression, separated by a non-logical operator.  For
+        /// example, in "x = (a && b && c && foo(d && f))", the "d && f" case
+        /// starts a new boolean expression that is separated from the other
+        /// conditions by the operator foo(). Split-nested cases are not
+        /// supported by MC/DC.
+        SplitNestedLogicalOp = SplitNestedLogicalOp || !NonLogOpStack.empty();
+
+        LogOpStack.push_back(BinOp);
+        return true;
+      }
+    }
+
+    /// Keep track of non-logical operators. These are OK as long as we don't
+    /// encounter a new logical operator after seeing one.
+    if (!LogOpStack.empty())
+      NonLogOpStack.push_back(S);
+
+    return true;
+  }
+
+  // Hook: dataTraverseStmtPost() is invoked by the AST visitor after visiting
+  // an AST Stmt node.  MC/DC will use it to to signal when the top of a
+  // logical operation (boolean expression) nest is encountered.
+  bool dataTraverseStmtPost(Stmt *S) {
+    /// If MC/DC is not enabled, MCDCMaxCond will be set to 0. Do nothing.
+    if (MCDCMaxCond == 0)
+      return true;
+
+    if (const Expr *E = dyn_cast<Expr>(S)) {
+      const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(E->IgnoreParens());
+      if (BinOp && BinOp->isLogicalOp()) {
+        assert(LogOpStack.back() == BinOp);
+        LogOpStack.pop_back();
+
+        /// At the top of logical operator nest:
+        if (LogOpStack.empty()) {
+          /// Was the "split-nested" logical operator case encountered?
+          if (SplitNestedLogicalOp) {
+            unsigned DiagID = Diag.getCustomDiagID(
+                DiagnosticsEngine::Warning,
+                "unsupported MC/DC boolean expression; "
+                "contains an operation with a nested boolean expression. "
+                "Expression will not be covered");
+            Diag.Report(S->getBeginLoc(), DiagID);
+            return true;
+          }
+
+          /// Was the maximum number of conditions encountered?
+          if (NumCond > MCDCMaxCond) {
+            unsigned DiagID = Diag.getCustomDiagID(
+                DiagnosticsEngine::Warning,
+                "unsupported MC/DC boolean expression; "
+                "number of conditions (%0) exceeds max (%1). "
+                "Expression will not be covered");
+            Diag.Report(S->getBeginLoc(), DiagID) << NumCond << MCDCMaxCond;
+            return true;
+          }
+
+          // Otherwise, allocate the number of bytes required for the bitmap
+          // based on the number of conditions. Must be at least 1-byte long.
+          MCDCBitmapMap[BinOp] = NextMCDCBitmapIdx;
+          unsigned SizeInBits = std::max<unsigned>(1L << NumCond, CHAR_BIT);
+          NextMCDCBitmapIdx += SizeInBits / CHAR_BIT;
+        }
+        return true;
+      }
+    }
+
+    if (!LogOpStack.empty())
+      NonLogOpStack.pop_back();
+
+    return true;
+  }
+
   /// 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.
+  /// version so that we facilitate backward compatibility. In addition, in
+  /// order to use MC/DC, count the number of total LHS and RHS conditions.
   bool VisitBinaryOperator(BinaryOperator *S) {
-    if (ProfileVersion >= llvm::IndexedInstrProf::Version7)
-      if (S->isLogicalOp() &&
-          CodeGenFunction::isInstrumentedCondition(S->getRHS()))
-        CounterMap[S->getRHS()] = NextCounter++;
+    if (S->isLogicalOp()) {
+      if (CodeGenFunction::isInstrumentedCondition(S->getLHS()))
+        NumCond++;
+
+      if (CodeGenFunction::isInstrumentedCondition(S->getRHS())) {
+        if (ProfileVersion >= llvm::IndexedInstrProf::Version7)
+          CounterMap[S->getRHS()] = NextCounter++;
+
+        NumCond++;
+      }
+    }
     return Base::VisitBinaryOperator(S);
   }
 
@@ -375,9 +503,9 @@ struct ComputeRegionCounts : public ConstStmtVisitor<ComputeRegionCounts> {
 
   /// BreakContinueStack - Keep counts of breaks and continues inside loops.
   struct BreakContinue {
-    uint64_t BreakCount;
-    uint64_t ContinueCount;
-    BreakContinue() : BreakCount(0), ContinueCount(0) {}
+    uint64_t BreakCount = 0;
+    uint64_t ContinueCount = 0;
+    BreakContinue() = default;
   };
   SmallVector<BreakContinue, 8> BreakContinueStack;
 
@@ -649,6 +777,14 @@ struct ComputeRegionCounts : public ConstStmtVisitor<ComputeRegionCounts> {
 
   void VisitIfStmt(const IfStmt *S) {
     RecordStmtCount(S);
+
+    if (S->isConsteval()) {
+      const Stmt *Stm = S->isNegatedConsteval() ? S->getThen() : S->getElse();
+      if (Stm)
+        Visit(Stm);
+      return;
+    }
+
     uint64_t ParentCount = CurrentCount;
     if (S->getInit())
       Visit(S->getInit());
@@ -746,8 +882,9 @@ void PGOHash::combine(HashType Type) {
   // Pass through MD5 if enough work has built up.
   if (Count && Count % NumTypesPerWord == 0) {
     using namespace llvm::support;
-    uint64_t Swapped = endian::byte_swap<uint64_t, little>(Working);
-    MD5.update(llvm::makeArrayRef((uint8_t *)&Swapped, sizeof(Swapped)));
+    uint64_t Swapped =
+        endian::byte_swap<uint64_t, llvm::endianness::little>(Working);
+    MD5.update(llvm::ArrayRef((uint8_t *)&Swapped, sizeof(Swapped)));
     Working = 0;
   }
 
@@ -772,8 +909,9 @@ uint64_t PGOHash::finalize() {
       MD5.update({(uint8_t)Working});
     } else {
       using namespace llvm::support;
-      uint64_t Swapped = endian::byte_swap<uint64_t, little>(Working);
-      MD5.update(llvm::makeArrayRef((uint8_t *)&Swapped, sizeof(Swapped)));
+      uint64_t Swapped =
+          endian::byte_swap<uint64_t, llvm::endianness::little>(Working);
+      MD5.update(llvm::ArrayRef((uint8_t *)&Swapped, sizeof(Swapped)));
     }
   }
 
@@ -814,6 +952,8 @@ void CodeGenPGO::assignRegionCounters(GlobalDecl GD, llvm::Function *Fn) {
   CGM.ClearUnusedCoverageMapping(D);
   if (Fn->hasFnAttribute(llvm::Attribute::NoProfile))
     return;
+  if (Fn->hasFnAttribute(llvm::Attribute::SkipProfile))
+    return;
 
   setFuncName(Fn);
 
@@ -838,8 +978,22 @@ void CodeGenPGO::mapRegionCounters(const Decl *D) {
     ProfileVersion = PGOReader->getVersion();
   }
 
+  // If MC/DC is enabled, set the MaxConditions to a preset value. Otherwise,
+  // set it to zero. This value impacts the number of conditions accepted in a
+  // given boolean expression, which impacts the size of the bitmap used to
+  // track test vector execution for that boolean expression.  Because the
+  // bitmap scales exponentially (2^n) based on the number of conditions seen,
+  // the maximum value is hard-coded at 6 conditions, which is more than enough
+  // for most embedded applications. Setting a maximum value prevents the
+  // bitmap footprint from growing too large without the user's knowledge. In
+  // the future, this value could be adjusted with a command-line option.
+  unsigned MCDCMaxConditions = (CGM.getCodeGenOpts().MCDCCoverage) ? 6 : 0;
+
   RegionCounterMap.reset(new llvm::DenseMap<const Stmt *, unsigned>);
-  MapRegionCounters Walker(HashVersion, ProfileVersion, *RegionCounterMap);
+  RegionMCDCBitmapMap.reset(new llvm::DenseMap<const Stmt *, unsigned>);
+  MapRegionCounters Walker(HashVersion, ProfileVersion, *RegionCounterMap,
+                           *RegionMCDCBitmapMap, MCDCMaxConditions,
+                           CGM.getDiags());
   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))
@@ -850,6 +1004,7 @@ void CodeGenPGO::mapRegionCounters(const Decl *D) {
     Walker.TraverseDecl(const_cast<CapturedDecl *>(CD));
   assert(Walker.NextCounter > 0 && "no entry counter mapped for decl");
   NumRegionCounters = Walker.NextCounter;
+  MCDCBitmapBytes = Walker.NextMCDCBitmapIdx;
   FunctionHash = Walker.Hash.finalize();
 }
 
@@ -872,7 +1027,7 @@ bool CodeGenPGO::skipRegionMappingForDecl(const Decl *D) {
   // Don't map the functions in system headers.
   const auto &SM = CGM.getContext().getSourceManager();
   auto Loc = D->getBody()->getBeginLoc();
-  return SM.isInSystemHeader(Loc);
+  return !SystemHeadersCoverage && SM.isInSystemHeader(Loc);
 }
 
 void CodeGenPGO::emitCounterRegionMapping(const Decl *D) {
@@ -881,9 +1036,11 @@ void CodeGenPGO::emitCounterRegionMapping(const Decl *D) {
 
   std::string CoverageMapping;
   llvm::raw_string_ostream OS(CoverageMapping);
-  CoverageMappingGen MappingGen(*CGM.getCoverageMapping(),
-                                CGM.getContext().getSourceManager(),
-                                CGM.getLangOpts(), RegionCounterMap.get());
+  RegionCondIDMap.reset(new llvm::DenseMap<const Stmt *, unsigned>);
+  CoverageMappingGen MappingGen(
+      *CGM.getCoverageMapping(), CGM.getContext().getSourceManager(),
+      CGM.getLangOpts(), RegionCounterMap.get(), RegionMCDCBitmapMap.get(),
+      RegionCondIDMap.get());
   MappingGen.emitCounterMapping(D, OS);
   OS.flush();
 
@@ -941,25 +1098,124 @@ CodeGenPGO::applyFunctionAttributes(llvm::IndexedInstrProfReader *PGOReader,
 
 void CodeGenPGO::emitCounterIncrement(CGBuilderTy &Builder, const Stmt *S,
                                       llvm::Value *StepV) {
-  if (!CGM.getCodeGenOpts().hasProfileClangInstr() || !RegionCounterMap)
-    return;
-  if (!Builder.GetInsertBlock())
+  if (!RegionCounterMap || !Builder.GetInsertBlock())
     return;
 
   unsigned Counter = (*RegionCounterMap)[S];
-  auto *I8PtrTy = llvm::Type::getInt8PtrTy(CGM.getLLVMContext());
 
-  llvm::Value *Args[] = {llvm::ConstantExpr::getBitCast(FuncNameVar, I8PtrTy),
+  llvm::Value *Args[] = {FuncNameVar,
                          Builder.getInt64(FunctionHash),
                          Builder.getInt32(NumRegionCounters),
                          Builder.getInt32(Counter), StepV};
   if (!StepV)
     Builder.CreateCall(CGM.getIntrinsic(llvm::Intrinsic::instrprof_increment),
-                       makeArrayRef(Args, 4));
+                       ArrayRef(Args, 4));
   else
     Builder.CreateCall(
         CGM.getIntrinsic(llvm::Intrinsic::instrprof_increment_step),
-        makeArrayRef(Args));
+        ArrayRef(Args));
+}
+
+bool CodeGenPGO::canEmitMCDCCoverage(const CGBuilderTy &Builder) {
+  return (CGM.getCodeGenOpts().hasProfileClangInstr() &&
+          CGM.getCodeGenOpts().MCDCCoverage && Builder.GetInsertBlock());
+}
+
+void CodeGenPGO::emitMCDCParameters(CGBuilderTy &Builder) {
+  if (!canEmitMCDCCoverage(Builder) || !RegionMCDCBitmapMap)
+    return;
+
+  auto *I8PtrTy = llvm::PointerType::getUnqual(CGM.getLLVMContext());
+
+  // Emit intrinsic representing MCDC bitmap parameters at function entry.
+  // This is used by the instrumentation pass, but it isn't actually lowered to
+  // anything.
+  llvm::Value *Args[3] = {llvm::ConstantExpr::getBitCast(FuncNameVar, I8PtrTy),
+                          Builder.getInt64(FunctionHash),
+                          Builder.getInt32(MCDCBitmapBytes)};
+  Builder.CreateCall(
+      CGM.getIntrinsic(llvm::Intrinsic::instrprof_mcdc_parameters), Args);
+}
+
+void CodeGenPGO::emitMCDCTestVectorBitmapUpdate(CGBuilderTy &Builder,
+                                                const Expr *S,
+                                                Address MCDCCondBitmapAddr) {
+  if (!canEmitMCDCCoverage(Builder) || !RegionMCDCBitmapMap)
+    return;
+
+  S = S->IgnoreParens();
+
+  auto ExprMCDCBitmapMapIterator = RegionMCDCBitmapMap->find(S);
+  if (ExprMCDCBitmapMapIterator == RegionMCDCBitmapMap->end())
+    return;
+
+  // Extract the ID of the global bitmap associated with this expression.
+  unsigned MCDCTestVectorBitmapID = ExprMCDCBitmapMapIterator->second;
+  auto *I8PtrTy = llvm::PointerType::getUnqual(CGM.getLLVMContext());
+
+  // Emit intrinsic responsible for updating the global bitmap corresponding to
+  // a boolean expression. The index being set is based on the value loaded
+  // from a pointer to a dedicated temporary value on the stack that is itself
+  // updated via emitMCDCCondBitmapReset() and emitMCDCCondBitmapUpdate(). The
+  // index represents an executed test vector.
+  llvm::Value *Args[5] = {llvm::ConstantExpr::getBitCast(FuncNameVar, I8PtrTy),
+                          Builder.getInt64(FunctionHash),
+                          Builder.getInt32(MCDCBitmapBytes),
+                          Builder.getInt32(MCDCTestVectorBitmapID),
+                          MCDCCondBitmapAddr.getPointer()};
+  Builder.CreateCall(
+      CGM.getIntrinsic(llvm::Intrinsic::instrprof_mcdc_tvbitmap_update), Args);
+}
+
+void CodeGenPGO::emitMCDCCondBitmapReset(CGBuilderTy &Builder, const Expr *S,
+                                         Address MCDCCondBitmapAddr) {
+  if (!canEmitMCDCCoverage(Builder) || !RegionMCDCBitmapMap)
+    return;
+
+  S = S->IgnoreParens();
+
+  if (RegionMCDCBitmapMap->find(S) == RegionMCDCBitmapMap->end())
+    return;
+
+  // Emit intrinsic that resets a dedicated temporary value on the stack to 0.
+  Builder.CreateStore(Builder.getInt32(0), MCDCCondBitmapAddr);
+}
+
+void CodeGenPGO::emitMCDCCondBitmapUpdate(CGBuilderTy &Builder, const Expr *S,
+                                          Address MCDCCondBitmapAddr,
+                                          llvm::Value *Val) {
+  if (!canEmitMCDCCoverage(Builder) || !RegionCondIDMap)
+    return;
+
+  // Even though, for simplicity, parentheses and unary logical-NOT operators
+  // are considered part of their underlying condition for both MC/DC and
+  // branch coverage, the condition IDs themselves are assigned and tracked
+  // using the underlying condition itself.  This is done solely for
+  // consistency since parentheses and logical-NOTs are ignored when checking
+  // whether the condition is actually an instrumentable condition. This can
+  // also make debugging a bit easier.
+  S = CodeGenFunction::stripCond(S);
+
+  auto ExprMCDCConditionIDMapIterator = RegionCondIDMap->find(S);
+  if (ExprMCDCConditionIDMapIterator == RegionCondIDMap->end())
+    return;
+
+  // Extract the ID of the condition we are setting in the bitmap.
+  unsigned CondID = ExprMCDCConditionIDMapIterator->second;
+  assert(CondID > 0 && "Condition has no ID!");
+
+  auto *I8PtrTy = llvm::PointerType::getUnqual(CGM.getLLVMContext());
+
+  // Emit intrinsic that updates a dedicated temporary value on the stack after
+  // a condition is evaluated. After the set of conditions has been updated,
+  // the resulting value is used to update the boolean expression's bitmap.
+  llvm::Value *Args[5] = {llvm::ConstantExpr::getBitCast(FuncNameVar, I8PtrTy),
+                          Builder.getInt64(FunctionHash),
+                          Builder.getInt32(CondID - 1),
+                          MCDCCondBitmapAddr.getPointer(), Val};
+  Builder.CreateCall(
+      CGM.getIntrinsic(llvm::Intrinsic::instrprof_mcdc_condbitmap_update),
+      Args);
 }
 
 void CodeGenPGO::setValueProfilingFlag(llvm::Module &M) {
@@ -987,7 +1243,7 @@ void CodeGenPGO::valueProfile(CGBuilderTy &Builder, uint32_t ValueKind,
     auto BuilderInsertPoint = Builder.saveIP();
     Builder.SetInsertPoint(ValueSite);
     llvm::Value *Args[5] = {
-        llvm::ConstantExpr::getBitCast(FuncNameVar, Builder.getInt8PtrTy()),
+        FuncNameVar,
         Builder.getInt64(FunctionHash),
         Builder.CreatePtrToInt(ValuePtr, Builder.getInt64Ty()),
         Builder.getInt32(ValueKind),
@@ -1025,7 +1281,7 @@ void CodeGenPGO::loadRegionCounts(llvm::IndexedInstrProfReader *PGOReader,
   llvm::Expected<llvm::InstrProfRecord> RecordExpected =
       PGOReader->getInstrProfRecord(FuncName, FunctionHash);
   if (auto E = RecordExpected.takeError()) {
-    auto IPE = llvm::InstrProfError::take(std::move(E));
+    auto IPE = std::get<0>(llvm::InstrProfError::take(std::move(E)));
     if (IPE == llvm::instrprof_error::unknown_function)
       CGM.getPGOStats().addMissing(IsInMainFile);
     else if (IPE == llvm::instrprof_error::hash_mismatch)
@@ -1106,7 +1362,7 @@ CodeGenFunction::createProfileWeightsForLoop(const Stmt *Cond,
                                              uint64_t LoopCount) const {
   if (!PGO.haveRegionCounts())
     return nullptr;
-  Optional<uint64_t> CondCount = PGO.getStmtCount(Cond);
+  std::optional<uint64_t> CondCount = PGO.getStmtCount(Cond);
   if (!CondCount || *CondCount == 0)
     return nullptr;
   return createProfileWeights(LoopCount,