Refactor with expansion walkingusers/chapuni/mcdc/nest/covmapdesc

1 files changed, 135 insertions, 168 deletions

diff --git a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp
index 3205863..8c5eae9 100644
--- a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp
+++ b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp
@@ -668,154 +668,166 @@ static unsigned getMaxBitmapSize(const CoverageMappingRecord &Record,
 
 namespace {
 
-/// Collect Decisions, Branchs, and Expansions and associate them.
-class MCDCDecisionRecorder {
-private:
-  /// This holds the DecisionRegion and MCDCBranches under it.
-  /// Also traverses Expansion(s).
-  /// The Decision has the number of MCDCBranches and will complete
-  /// when it is filled with unique ConditionID of MCDCBranches.
+/// Walk MappingRegions along Expansions and emit CountedRegions.
+struct CountedRegionEmitter {
+  /// A nestable Decision.
   struct DecisionRecord {
     const CounterMappingRegion *DecisionRegion;
-
-    /// They are reflected from DecisionRegion for convenience.
-    mcdc::DecisionParameters DecisionParams;
-    LineColPair DecisionStartLoc;
-    LineColPair DecisionEndLoc;
-
-    /// This is passed to `MCDCRecordProcessor`, so this should be compatible
-    /// to`ArrayRef<const CounterMappingRegion *>`.
+    unsigned NumConditions; ///< Copy of DecisionRegion.NumConditions
+    /// Pushed by traversal order.
     SmallVector<const CounterMappingRegion *> MCDCBranches;
-
-    /// IDs that are stored in MCDCBranches
-    /// Complete when all IDs (1 to NumConditions) are met.
+#ifndef NDEBUG
     DenseSet<mcdc::ConditionID> ConditionIDs;
-
-    /// Set of IDs of Expansion(s) that are relevant to DecisionRegion
-    /// and its children (via expansions).
-    /// FileID  pointed by ExpandedFileID is dedicated to the expansion, so
-    /// the location in the expansion doesn't matter.
-    DenseSet<unsigned> ExpandedFileIDs;
+#endif
 
     DecisionRecord(const CounterMappingRegion &Decision)
         : DecisionRegion(&Decision),
-          DecisionParams(Decision.getDecisionParams()),
-          DecisionStartLoc(Decision.startLoc()),
-          DecisionEndLoc(Decision.endLoc()) {
+          NumConditions(Decision.getDecisionParams().NumConditions) {
       assert(Decision.Kind == CounterMappingRegion::MCDCDecisionRegion);
     }
 
-    /// Determine whether DecisionRecord dominates `R`.
-    bool dominates(const CounterMappingRegion &R) const {
-      // Determine whether `R` is included in `DecisionRegion`.
-      if (R.FileID == DecisionRegion->FileID &&
-          R.startLoc() >= DecisionStartLoc && R.endLoc() <= DecisionEndLoc)
-        return true;
-
-      // Determine whether `R` is pointed by any of Expansions.
-      return ExpandedFileIDs.contains(R.FileID);
+    bool pushBranch(const CounterMappingRegion &B) {
+      assert(B.Kind == CounterMappingRegion::MCDCBranchRegion);
+      assert(ConditionIDs.insert(B.getBranchParams().ID).second &&
+             "Duplicate CondID");
+      MCDCBranches.push_back(&B);
+      assert(MCDCBranches.size() <= NumConditions &&
+             "MCDCBranch exceeds NumConds");
+      return (MCDCBranches.size() == NumConditions);
     }
+  };
 
-    enum Result {
-      NotProcessed = 0, /// Irrelevant to this Decision
-      Processed,        /// Added to this Decision
-      Completed,        /// Added and filled this Decision
-    };
+  const CoverageMappingRecord &Record;
+  CounterMappingContext &Ctx;
+  FunctionRecord &Function;
+  bool IsVersion11;
 
-    /// Add Branch into the Decision
-    /// \param Branch expects MCDCBranchRegion
-    /// \returns NotProcessed/Processed/Completed
-    Result addBranch(const CounterMappingRegion &Branch) {
-      assert(Branch.Kind == CounterMappingRegion::MCDCBranchRegion);
+  /// Evaluated Counters.
+  std::map<Counter, uint64_t> CounterValues;
 
-      auto ConditionID = Branch.getBranchParams().ID;
+  /// Decisions are nestable.
+  SmallVector<DecisionRecord, 1> DecisionStack;
 
-      if (ConditionIDs.contains(ConditionID) ||
-          ConditionID >= DecisionParams.NumConditions)
-        return NotProcessed;
+  /// A File pointed by Expansion
+  struct FileInfo {
+    /// The last index(+1) for each FileID in MappingRegions.
+    unsigned LastIndex = 0;
+    /// Mark Files pointed by Expansions.
+    /// Non-marked Files are root Files.
+    bool IsExpanded = false;
+  };
 
-      if (!this->dominates(Branch))
-        return NotProcessed;
+  /// The last element is a sentinel with Index=NumRegions.
+  std::vector<FileInfo> Files;
+#ifndef NDEBUG
+  DenseSet<unsigned> Visited;
+#endif
 
-      assert(MCDCBranches.size() < DecisionParams.NumConditions);
+  CountedRegionEmitter(const CoverageMappingRecord &Record,
+                       CounterMappingContext &Ctx, FunctionRecord &Function,
+                       bool IsVersion11)
+      : Record(Record), Ctx(Ctx), Function(Function), IsVersion11(IsVersion11),
+        Files(Record.Filenames.size()) {
+    // Scan MappingRegions and mark each last index by FileID.
+    for (auto [I, Region] : enumerate(Record.MappingRegions)) {
+      if (Region.FileID >= Files.size()) {
+        // Extend (only possible in CoverageMappingTests)
+        Files.resize(Region.FileID + 1);
+      }
+      Files[Region.FileID].LastIndex = I + 1;
+      if (Region.Kind == CounterMappingRegion::ExpansionRegion) {
+        if (Region.ExpandedFileID >= Files.size()) {
+          // Extend (only possible in CoverageMappingTests)
+          Files.resize(Region.ExpandedFileID + 1);
+        }
+        Files[Region.ExpandedFileID].IsExpanded = true;
+      }
+    }
+  }
 
-      // Put `ID=0` in front of `MCDCBranches` for convenience
-      // even if `MCDCBranches` is not topological.
-      if (ConditionID == 0)
-        MCDCBranches.insert(MCDCBranches.begin(), &Branch);
-      else
-        MCDCBranches.push_back(&Branch);
+  /// Evaluate C and store its evaluated Value into CounterValues.
+  Error evaluateAndCacheCounter(Counter C) {
+    if (CounterValues.count(C) > 0)
+      return Error::success();
 
-      // Mark `ID` as `assigned`.
-      ConditionIDs.insert(ConditionID);
+    auto ValueOrErr = Ctx.evaluate(C);
+    if (!ValueOrErr)
+      return ValueOrErr.takeError();
+    CounterValues[C] = *ValueOrErr;
+    return Error::success();
+  }
 
-      // `Completed` when `MCDCBranches` is full
-      return (MCDCBranches.size() == DecisionParams.NumConditions ? Completed
-                                                                  : Processed);
-    }
+  Error walk(unsigned Idx) {
+    assert(Idx < Files.size());
+    unsigned B = (Idx == 0 ? 0 : Files[Idx - 1].LastIndex);
+    unsigned E = Files[Idx].LastIndex;
+    assert(B != E && "Empty FileID");
+    assert(Visited.insert(Idx).second && "Duplicate Expansions");
+    for (unsigned I = B; I != E; ++I) {
+      const auto &Region = Record.MappingRegions[I];
+      if (Region.FileID != Idx)
+        break;
 
-    /// Record Expansion if it is relevant to this Decision.
-    /// Each `Expansion` may nest.
-    /// \returns true if recorded.
-    bool recordExpansion(const CounterMappingRegion &Expansion) {
-      if (!this->dominates(Expansion))
-        return false;
+      if (Region.Kind == CounterMappingRegion::ExpansionRegion)
+        if (auto E = walk(Region.ExpandedFileID))
+          return E;
 
-      ExpandedFileIDs.insert(Expansion.ExpandedFileID);
-      return true;
-    }
-  };
+      if (auto E = evaluateAndCacheCounter(Region.Count))
+        return E;
 
-private:
-  /// Decisions in progress
-  /// DecisionRecord is added for each MCDCDecisionRegion.
-  /// DecisionRecord is removed when Decision is completed.
-  SmallVector<DecisionRecord> Decisions;
+      if (Region.Kind == CounterMappingRegion::MCDCDecisionRegion) {
+        // Start the new Decision on the stack.
+        DecisionStack.emplace_back(Region);
+      } else if (Region.Kind == CounterMappingRegion::MCDCBranchRegion) {
+        assert(!DecisionStack.empty() && "Orphan MCDCBranch");
+        auto &D = DecisionStack.back();
+
+        if (D.pushBranch(Region)) {
+          // All Branches have been found in the Decision.
+          auto RecordOrErr = Ctx.evaluateMCDCRegion(
+              *D.DecisionRegion, D.MCDCBranches, IsVersion11);
+          if (!RecordOrErr)
+            return RecordOrErr.takeError();
+
+          // Finish the stack.
+          Function.pushMCDCRecord(std::move(*RecordOrErr));
+          DecisionStack.pop_back();
+        }
+      }
 
-public:
-  ~MCDCDecisionRecorder() {
-    assert(Decisions.empty() && "All Decisions have not been resolved");
-  }
+      // Evaluate FalseCount
+      // It may have the Counter in Branches, or Zero.
+      if (auto E = evaluateAndCacheCounter(Region.FalseCount))
+        return E;
+    }
 
-  /// Register Region and start recording.
-  void registerDecision(const CounterMappingRegion &Decision) {
-    Decisions.emplace_back(Decision);
-  }
+    assert((Idx != 0 || DecisionStack.empty()) && "Decision wasn't closed");
 
-  void recordExpansion(const CounterMappingRegion &Expansion) {
-    any_of(Decisions, [&Expansion](auto &Decision) {
-      return Decision.recordExpansion(Expansion);
-    });
+    return Error::success();
   }
 
-  using DecisionAndBranches =
-      std::pair<const CounterMappingRegion *,             /// Decision
-                SmallVector<const CounterMappingRegion *> /// Branches
-                >;
-
-  /// Add MCDCBranchRegion to DecisionRecord.
-  /// \param Branch to be processed
-  /// \returns DecisionsAndBranches if DecisionRecord completed.
-  ///     Or returns nullopt.
-  std::optional<DecisionAndBranches>
-  processBranch(const CounterMappingRegion &Branch) {
-    // Seek each Decision and apply Region to it.
-    for (auto DecisionIter = Decisions.rbegin(), DecisionEnd = Decisions.rend();
-         DecisionIter != DecisionEnd; ++DecisionIter)
-      switch (DecisionIter->addBranch(Branch)) {
-      case DecisionRecord::NotProcessed:
-        continue;
-      case DecisionRecord::Processed:
-        return std::nullopt;
-      case DecisionRecord::Completed:
-        DecisionAndBranches Result =
-            std::make_pair(DecisionIter->DecisionRegion,
-                           std::move(DecisionIter->MCDCBranches));
-        Decisions.erase(std::next(DecisionIter).base()); // No longer used.
-        return Result;
-      }
+  Error emitCountedRegions() {
+    // Walk MappingRegions along Expansions.
+    // - Evaluate Counters
+    // - Emit MCDCRecords
+    for (auto [I, F] : enumerate(Files)) {
+      if (!F.IsExpanded)
+        if (auto E = walk(I))
+          return E;
+    }
+    assert(Visited.size() == Files.size() && "Dangling FileID");
+
+    // Emit CountedRegions in the same order as MappingRegions.
+    for (const auto &Region : Record.MappingRegions) {
+      if (Region.Kind == CounterMappingRegion::MCDCDecisionRegion)
+        continue; // Don't emit.
+      // Adopt values from the CounterValues.
+      // FalseCount may be Zero unless Branches.
+      Function.pushRegion(Region, CounterValues[Region.Count],
+                          CounterValues[Region.FalseCount]);
+    }
 
-    llvm_unreachable("Branch not found in Decisions");
+    return Error::success();
   }
 };
 
@@ -880,57 +892,12 @@ Error CoverageMapping::loadFunctionRecord(
       Record.MappingRegions[0].Count.isZero() && Counts[0] > 0)
     return Error::success();
 
-  MCDCDecisionRecorder MCDCDecisions;
   FunctionRecord Function(OrigFuncName, Record.Filenames);
-  for (const auto &Region : Record.MappingRegions) {
-    // MCDCDecisionRegion should be handled first since it overlaps with
-    // others inside.
-    if (Region.Kind == CounterMappingRegion::MCDCDecisionRegion) {
-      MCDCDecisions.registerDecision(Region);
-      continue;
-    }
-    Expected<int64_t> ExecutionCount = Ctx.evaluate(Region.Count);
-    if (auto E = ExecutionCount.takeError()) {
-      consumeError(std::move(E));
-      return Error::success();
-    }
-    Expected<int64_t> AltExecutionCount = Ctx.evaluate(Region.FalseCount);
-    if (auto E = AltExecutionCount.takeError()) {
-      consumeError(std::move(E));
-      return Error::success();
-    }
-    Function.pushRegion(Region, *ExecutionCount, *AltExecutionCount);
-
-    // Record ExpansionRegion.
-    if (Region.Kind == CounterMappingRegion::ExpansionRegion) {
-      MCDCDecisions.recordExpansion(Region);
-      continue;
-    }
-
-    // Do nothing unless MCDCBranchRegion.
-    if (Region.Kind != CounterMappingRegion::MCDCBranchRegion)
-      continue;
 
-    auto Result = MCDCDecisions.processBranch(Region);
-    if (!Result) // Any Decision doesn't complete.
-      continue;
-
-    auto MCDCDecision = Result->first;
-    auto &MCDCBranches = Result->second;
-
-    // Since the bitmap identifies the executed test vectors for an MC/DC
-    // DecisionRegion, all of the information is now available to process.
-    // This is where the bulk of the MC/DC progressing takes place.
-    Expected<MCDCRecord> Record =
-        Ctx.evaluateMCDCRegion(*MCDCDecision, MCDCBranches, IsVersion11);
-    if (auto E = Record.takeError()) {
-      consumeError(std::move(E));
-      return Error::success();
-    }
-
-    // Save the MC/DC Record so that it can be visualized later.
-    Function.pushMCDCRecord(std::move(*Record));
-  }
+  // Emit CountedRegions into FunctionRecord.
+  if (auto E = CountedRegionEmitter(Record, Ctx, Function, IsVersion11)
+                   .emitCountedRegions())
+    return E;
 
   // Don't create records for (filenames, function) pairs we've already seen.
   auto FilenamesHash = hash_combine_range(Record.Filenames.begin(),