From ab76e48ac2c2dbfc7d6a600b9b0dd0672e6d9439 Mon Sep 17 00:00:00 2001 From: NAKAMURA Takumi Date: Thu, 15 Feb 2024 16:24:37 +0900 Subject: [MC/DC] Refactor: Let MCDCConditionID int16_t with zero-origin (#81257) Also, Let `NumConditions` `uint16_t`. It is smarter to handle the ID as signed. Narrowing to `int16_t` will reduce costs of handling byvalue. (See also #81221 and #81227) External behavior doesn't change. They below handle values as internal values plus 1. * `-dump-coverage-mapping` * `CoverageMappingReader.cpp` * `CoverageMappingWriter.cpp` --- clang/lib/CodeGen/CodeGenPGO.cpp | 8 +++---- clang/lib/CodeGen/CodeGenPGO.h | 2 ++ clang/lib/CodeGen/CoverageMappingGen.cpp | 28 ++++++++++++---------- llvm/include/llvm/ProfileData/Coverage/MCDCTypes.h | 4 ++-- llvm/lib/ProfileData/Coverage/CoverageMapping.cpp | 26 ++++++++++---------- .../ProfileData/Coverage/CoverageMappingReader.cpp | 21 +++++++++------- .../ProfileData/Coverage/CoverageMappingWriter.cpp | 12 ++++++---- llvm/unittests/ProfileData/CoverageMappingTest.cpp | 10 ++++---- 8 files changed, 61 insertions(+), 50 deletions(-) diff --git a/clang/lib/CodeGen/CodeGenPGO.cpp b/clang/lib/CodeGen/CodeGenPGO.cpp index b5ce1aa..48c5e68 100644 --- a/clang/lib/CodeGen/CodeGenPGO.cpp +++ b/clang/lib/CodeGen/CodeGenPGO.cpp @@ -1031,7 +1031,7 @@ void CodeGenPGO::emitCounterRegionMapping(const Decl *D) { std::string CoverageMapping; llvm::raw_string_ostream OS(CoverageMapping); - RegionMCDCState->CondIDMap.clear(); + RegionCondIDMap.reset(new llvm::DenseMap); CoverageMappingGen MappingGen( *CGM.getCoverageMapping(), CGM.getContext().getSourceManager(), CGM.getLangOpts(), RegionCounterMap.get(), RegionMCDCState.get()); @@ -1195,8 +1195,8 @@ void CodeGenPGO::emitMCDCCondBitmapUpdate(CGBuilderTy &Builder, const Expr *S, 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 CondID = ExprMCDCConditionIDMapIterator->second; + assert(CondID >= 0 && "Condition has no ID!"); auto *I8PtrTy = llvm::PointerType::getUnqual(CGM.getLLVMContext()); @@ -1205,7 +1205,7 @@ void CodeGenPGO::emitMCDCCondBitmapUpdate(CGBuilderTy &Builder, const Expr *S, // 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), + Builder.getInt32(CondID), MCDCCondBitmapAddr.getPointer(), Val}; Builder.CreateCall( CGM.getIntrinsic(llvm::Intrinsic::instrprof_mcdc_condbitmap_update), diff --git a/clang/lib/CodeGen/CodeGenPGO.h b/clang/lib/CodeGen/CodeGenPGO.h index d3c2b27..369bf05 100644 --- a/clang/lib/CodeGen/CodeGenPGO.h +++ b/clang/lib/CodeGen/CodeGenPGO.h @@ -36,6 +36,8 @@ private: unsigned NumRegionCounters; uint64_t FunctionHash; std::unique_ptr> RegionCounterMap; + std::unique_ptr> RegionMCDCBitmapMap; + std::unique_ptr> RegionCondIDMap; std::unique_ptr> StmtCountMap; std::unique_ptr ProfRecord; std::unique_ptr RegionMCDCState; diff --git a/clang/lib/CodeGen/CoverageMappingGen.cpp b/clang/lib/CodeGen/CoverageMappingGen.cpp index 93c3c31..fdf821a 100644 --- a/clang/lib/CodeGen/CoverageMappingGen.cpp +++ b/clang/lib/CodeGen/CoverageMappingGen.cpp @@ -686,11 +686,12 @@ private: llvm::SmallVector DecisionStack; MCDC::State &MCDCState; llvm::DenseMap &CondIDs; - mcdc::ConditionID NextID = 1; + mcdc::ConditionID NextID = 0; bool NotMapped = false; - /// Represent a sentinel value of [0,0] for the bottom of DecisionStack. - static constexpr mcdc::ConditionIDs DecisionStackSentinel{0, 0}; + /// Represent a sentinel value as a pair of final decisions for the bottom + // of DecisionStack. + static constexpr mcdc::ConditionIDs DecisionStackSentinel{-1, -1}; /// Is this a logical-AND operation? bool isLAnd(const BinaryOperator *E) const { @@ -705,12 +706,12 @@ public: /// Return whether the build of the control flow map is at the top-level /// (root) of a logical operator nest in a boolean expression prior to the /// assignment of condition IDs. - bool isIdle() const { return (NextID == 1 && !NotMapped); } + bool isIdle() const { return (NextID == 0 && !NotMapped); } /// Return whether any IDs have been assigned in the build of the control /// flow map, indicating that the map is being generated for this boolean /// expression. - bool isBuilding() const { return (NextID > 1); } + bool isBuilding() const { return (NextID > 0); } /// Set the given condition's ID. void setCondID(const Expr *Cond, mcdc::ConditionID ID) { @@ -721,7 +722,7 @@ public: mcdc::ConditionID getCondID(const Expr *Cond) const { auto I = CondIDs.find(CodeGenFunction::stripCond(Cond)); if (I == CondIDs.end()) - return 0; + return -1; else return I->second; } @@ -789,15 +790,15 @@ public: // Reset state if not doing mapping. if (NotMapped) { NotMapped = false; - assert(NextID == 1); + assert(NextID == 0); return 0; } // Set number of conditions and reset. - unsigned TotalConds = NextID - 1; + unsigned TotalConds = NextID; // Reset ID back to beginning. - NextID = 1; + NextID = 0; return TotalConds; } @@ -889,7 +890,7 @@ struct CounterCoverageMappingBuilder return RegionStack.size() - 1; } - size_t pushRegion(unsigned BitmapIdx, unsigned Conditions, + size_t pushRegion(unsigned BitmapIdx, uint16_t Conditions, std::optional StartLoc = std::nullopt, std::optional EndLoc = std::nullopt) { @@ -1038,7 +1039,7 @@ struct CounterCoverageMappingBuilder if (CodeGenFunction::isInstrumentedCondition(C)) { mcdc::Parameters BranchParams; mcdc::ConditionID ID = MCDCBuilder.getCondID(C); - if (ID > 0) + if (ID >= 0) BranchParams = mcdc::BranchParameters{ID, Conds}; // If a condition can fold to true or false, the corresponding branch @@ -2125,8 +2126,9 @@ static void dump(llvm::raw_ostream &OS, StringRef FunctionName, if (const auto *BranchParams = std::get_if(&R.MCDCParams)) { - OS << " [" << BranchParams->ID << "," << BranchParams->Conds[true]; - OS << "," << BranchParams->Conds[false] << "] "; + OS << " [" << BranchParams->ID + 1 << "," + << BranchParams->Conds[true] + 1; + OS << "," << BranchParams->Conds[false] + 1 << "] "; } if (R.Kind == CounterMappingRegion::ExpansionRegion) diff --git a/llvm/include/llvm/ProfileData/Coverage/MCDCTypes.h b/llvm/include/llvm/ProfileData/Coverage/MCDCTypes.h index 6127217..51f528b 100644 --- a/llvm/include/llvm/ProfileData/Coverage/MCDCTypes.h +++ b/llvm/include/llvm/ProfileData/Coverage/MCDCTypes.h @@ -19,7 +19,7 @@ namespace llvm::coverage::mcdc { /// The ID for MCDCBranch. -using ConditionID = unsigned int; +using ConditionID = int16_t; using ConditionIDs = std::array; struct DecisionParameters { @@ -27,7 +27,7 @@ struct DecisionParameters { unsigned BitmapIdx; /// Number of Conditions used for a Decision Region. - unsigned NumConditions; + uint16_t NumConditions; DecisionParameters() = delete; DecisionParameters(unsigned BitmapIdx, unsigned NumConditions) diff --git a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp index 9adeceb..ddce758 100644 --- a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp +++ b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp @@ -272,17 +272,17 @@ private: // Walk the binary decision diagram and try assigning both false and true to // each node. When a terminal node (ID == 0) is reached, fill in the value in // the truth table. - void buildTestVector(MCDCRecord::TestVector &TV, unsigned ID, + void buildTestVector(MCDCRecord::TestVector &TV, mcdc::ConditionID ID, unsigned Index) { - assert((Index & (1 << (ID - 1))) == 0); + assert((Index & (1 << ID)) == 0); for (auto MCDCCond : {MCDCRecord::MCDC_False, MCDCRecord::MCDC_True}) { static_assert(MCDCRecord::MCDC_False == 0); static_assert(MCDCRecord::MCDC_True == 1); - Index |= MCDCCond << (ID - 1); - TV[ID - 1] = MCDCCond; + Index |= MCDCCond << ID; + TV[ID] = MCDCCond; auto NextID = CondsMap[ID][MCDCCond]; - if (NextID > 0) { + if (NextID >= 0) { buildTestVector(TV, NextID, Index); continue; } @@ -299,17 +299,17 @@ private: } // Reset back to DontCare. - TV[ID - 1] = MCDCRecord::MCDC_DontCare; + TV[ID] = MCDCRecord::MCDC_DontCare; } /// Walk the bits in the bitmap. A bit set to '1' indicates that the test /// vector at the corresponding index was executed during a test run. void findExecutedTestVectors() { // Walk the binary decision diagram to enumerate all possible test vectors. - // We start at the root node (ID == 1) with all values being DontCare. + // We start at the root node (ID == 0) with all values being DontCare. // `Index` encodes the bitmask of true values and is initially 0. MCDCRecord::TestVector TV(NumConditions, MCDCRecord::MCDC_DontCare); - buildTestVector(TV, 1, 0); + buildTestVector(TV, 0, 0); } // Find an independence pair for each condition: @@ -371,7 +371,7 @@ public: for (const auto *B : Branches) { const auto &BranchParams = B->getBranchParams(); CondsMap[BranchParams.ID] = BranchParams.Conds; - PosToID[I] = BranchParams.ID - 1; + PosToID[I] = BranchParams.ID; CondLoc[I] = B->startLoc(); Folded[I++] = (B->Count.isZero() && B->FalseCount.isZero()); } @@ -566,10 +566,10 @@ private: assert(Branch.Kind == CounterMappingRegion::MCDCBranchRegion); auto ConditionID = Branch.getBranchParams().ID; - assert(ConditionID > 0 && "ConditionID should begin with 1"); + assert(ConditionID >= 0 && "ConditionID should be positive"); if (ConditionIDs.contains(ConditionID) || - ConditionID > DecisionParams.NumConditions) + ConditionID >= DecisionParams.NumConditions) return NotProcessed; if (!this->dominates(Branch)) @@ -577,9 +577,9 @@ private: assert(MCDCBranches.size() < DecisionParams.NumConditions); - // Put `ID=1` in front of `MCDCBranches` for convenience + // Put `ID=0` in front of `MCDCBranches` for convenience // even if `MCDCBranches` is not topological. - if (ConditionID == 1) + if (ConditionID == 0) MCDCBranches.insert(MCDCBranches.begin(), &Branch); else MCDCBranches.push_back(&Branch); diff --git a/llvm/lib/ProfileData/Coverage/CoverageMappingReader.cpp b/llvm/lib/ProfileData/Coverage/CoverageMappingReader.cpp index de7be52..d328460 100644 --- a/llvm/lib/ProfileData/Coverage/CoverageMappingReader.cpp +++ b/llvm/lib/ProfileData/Coverage/CoverageMappingReader.cpp @@ -244,7 +244,9 @@ Error RawCoverageMappingReader::readMappingRegionsSubArray( unsigned LineStart = 0; for (size_t I = 0; I < NumRegions; ++I) { Counter C, C2; - uint64_t BIDX, NC, ID, TID, FID; + uint64_t BIDX, NC; + // They are stored as internal values plus 1 (min is -1) + uint64_t ID1, TID1, FID1; mcdc::Parameters Params; CounterMappingRegion::RegionKind Kind = CounterMappingRegion::CodeRegion; @@ -303,28 +305,29 @@ Error RawCoverageMappingReader::readMappingRegionsSubArray( return Err; if (auto Err = readCounter(C2)) return Err; - if (auto Err = readIntMax(ID, std::numeric_limits::max())) + if (auto Err = readIntMax(ID1, std::numeric_limits::max())) return Err; - if (auto Err = readIntMax(TID, std::numeric_limits::max())) + if (auto Err = readIntMax(TID1, std::numeric_limits::max())) return Err; - if (auto Err = readIntMax(FID, std::numeric_limits::max())) + if (auto Err = readIntMax(FID1, std::numeric_limits::max())) return Err; - if (ID == 0) + if (ID1 == 0) return make_error( coveragemap_error::malformed, "MCDCConditionID shouldn't be zero"); Params = mcdc::BranchParameters{ - static_cast(ID), - {static_cast(FID), static_cast(TID)}}; + static_cast(static_cast(ID1) - 1), + {static_cast(static_cast(FID1) - 1), + static_cast(static_cast(TID1) - 1)}}; break; case CounterMappingRegion::MCDCDecisionRegion: Kind = CounterMappingRegion::MCDCDecisionRegion; if (auto Err = readIntMax(BIDX, std::numeric_limits::max())) return Err; - if (auto Err = readIntMax(NC, std::numeric_limits::max())) + if (auto Err = readIntMax(NC, std::numeric_limits::max())) return Err; Params = mcdc::DecisionParameters{static_cast(BIDX), - static_cast(NC)}; + static_cast(NC)}; break; default: return make_error(coveragemap_error::malformed, diff --git a/llvm/lib/ProfileData/Coverage/CoverageMappingWriter.cpp b/llvm/lib/ProfileData/Coverage/CoverageMappingWriter.cpp index 6125cce..5036bde 100644 --- a/llvm/lib/ProfileData/Coverage/CoverageMappingWriter.cpp +++ b/llvm/lib/ProfileData/Coverage/CoverageMappingWriter.cpp @@ -253,12 +253,16 @@ void CoverageMappingWriter::write(raw_ostream &OS) { writeCounter(MinExpressions, Count, OS); writeCounter(MinExpressions, FalseCount, OS); { + // They are written as internal values plus 1. const auto &BranchParams = I->getBranchParams(); ParamsShouldBeNull = false; - assert(BranchParams.ID > 0); - encodeULEB128(static_cast(BranchParams.ID), OS); - encodeULEB128(static_cast(BranchParams.Conds[true]), OS); - encodeULEB128(static_cast(BranchParams.Conds[false]), OS); + assert(BranchParams.ID >= 0); + unsigned ID1 = BranchParams.ID + 1; + unsigned TID1 = BranchParams.Conds[true] + 1; + unsigned FID1 = BranchParams.Conds[false] + 1; + encodeULEB128(ID1, OS); + encodeULEB128(TID1, OS); + encodeULEB128(FID1, OS); } break; case CounterMappingRegion::MCDCDecisionRegion: diff --git a/llvm/unittests/ProfileData/CoverageMappingTest.cpp b/llvm/unittests/ProfileData/CoverageMappingTest.cpp index db6689b..425b3d1 100644 --- a/llvm/unittests/ProfileData/CoverageMappingTest.cpp +++ b/llvm/unittests/ProfileData/CoverageMappingTest.cpp @@ -192,7 +192,7 @@ struct CoverageMappingTest : ::testing::TestWithParam> { addCMR(Counter::getZero(), File, LS, CS, LE, CE, true); } - void addMCDCDecisionCMR(unsigned Mask, unsigned NC, StringRef File, + void addMCDCDecisionCMR(unsigned Mask, uint16_t NC, StringRef File, unsigned LS, unsigned CS, unsigned LE, unsigned CE) { auto &Regions = InputFunctions.back().Regions; unsigned FileID = getFileIndexForFunction(File); @@ -872,9 +872,9 @@ TEST_P(CoverageMappingTest, non_code_region_bitmask) { addCMR(Counter::getCounter(3), "file", 1, 1, 5, 5); addMCDCDecisionCMR(0, 2, "file", 7, 1, 7, 6); - addMCDCBranchCMR(Counter::getCounter(0), Counter::getCounter(1), 1, {0, 2}, + addMCDCBranchCMR(Counter::getCounter(0), Counter::getCounter(1), 0, {-1, 1}, "file", 7, 2, 7, 3); - addMCDCBranchCMR(Counter::getCounter(2), Counter::getCounter(3), 2, {0, 0}, + addMCDCBranchCMR(Counter::getCounter(2), Counter::getCounter(3), 1, {-1, -1}, "file", 7, 4, 7, 5); EXPECT_THAT_ERROR(loadCoverageMapping(), Succeeded()); @@ -900,10 +900,10 @@ TEST_P(CoverageMappingTest, decision_before_expansion) { addExpansionCMR("foo", "B", 4, 19, 4, 20); addCMR(Counter::getCounter(0), "A", 1, 14, 1, 17); addCMR(Counter::getCounter(0), "A", 1, 14, 1, 17); - addMCDCBranchCMR(Counter::getCounter(0), Counter::getCounter(1), 1, {0, 2}, + addMCDCBranchCMR(Counter::getCounter(0), Counter::getCounter(1), 0, {-1, 1}, "A", 1, 14, 1, 17); addCMR(Counter::getCounter(1), "B", 1, 14, 1, 17); - addMCDCBranchCMR(Counter::getCounter(1), Counter::getCounter(2), 2, {0, 0}, + addMCDCBranchCMR(Counter::getCounter(1), Counter::getCounter(2), 1, {-1, -1}, "B", 1, 14, 1, 17); // InputFunctionCoverageData::Regions is rewritten after the write. -- cgit v1.1