From 1476756523da72f668332f1d69692aa3ab838014 Mon Sep 17 00:00:00 2001 From: Justin Bogner Date: Thu, 2 Oct 2014 16:04:03 +0000 Subject: [PATCH] InstrProf: Don't keep a large sparse list around just to zero it The Terms vector here represented a polynomial of of all possible counters, and is used to simplify expressions when generating coverage mapping. There are a few problems with this: 1. Keeping the vector as a member is wasteful, since we clear it every time we use it. 2. Most expressions refer to a subset of the counters, so we end up iterating over a large number of zeros doing nothing a lot of the time. This updates the user of the vector to store the terms locally, and uses a sort and combine approach so that we only operate on counters that are actually used in a given expression. For small cases this makes very little difference, but in cases with a very large number of counted regions this is a significant performance fix. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@218879 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ProfileData/CoverageMapping.h | 15 +++--- lib/ProfileData/CoverageMapping.cpp | 62 +++++++++++++--------- 2 files changed, 45 insertions(+), 32 deletions(-) diff --git a/include/llvm/ProfileData/CoverageMapping.h b/include/llvm/ProfileData/CoverageMapping.h index 6d833648a17..8f73217c4d4 100644 --- a/include/llvm/ProfileData/CoverageMapping.h +++ b/include/llvm/ProfileData/CoverageMapping.h @@ -103,8 +103,6 @@ struct CounterExpression { class CounterExpressionBuilder { /// \brief A list of all the counter expressions llvm::SmallVector Expressions; - /// \brief An array of terms used in expression simplification. - llvm::SmallVector Terms; /// \brief Return the counter which corresponds to the given expression. /// @@ -113,18 +111,19 @@ class CounterExpressionBuilder { /// expression is added to the builder's collection of expressions. Counter get(const CounterExpression &E); - /// \brief Convert the expression tree represented by a counter - /// into a polynomial in the form of K1Counter1 + .. + KNCounterN - /// where K1 .. KN are integer constants that are stored in the Terms array. - void extractTerms(Counter C, int Sign = 1); + /// \brief Gather the terms of the expression tree for processing. + /// + /// This collects each addition and subtraction referenced by the counter into + /// a sequence that can be sorted and combined to build a simplified counter + /// expression. + void extractTerms(Counter C, int Sign, + SmallVectorImpl> &Terms); /// \brief Simplifies the given expression tree /// by getting rid of algebraically redundant operations. Counter simplify(Counter ExpressionTree); public: - CounterExpressionBuilder(unsigned NumCounterValues); - ArrayRef getExpressions() const { return Expressions; } /// \brief Return a counter that represents the expression diff --git a/lib/ProfileData/CoverageMapping.cpp b/lib/ProfileData/CoverageMapping.cpp index 115256358ed..3a568720b08 100644 --- a/lib/ProfileData/CoverageMapping.cpp +++ b/lib/ProfileData/CoverageMapping.cpp @@ -27,10 +27,6 @@ using namespace coverage; #define DEBUG_TYPE "coverage-mapping" -CounterExpressionBuilder::CounterExpressionBuilder(unsigned NumCounterValues) { - Terms.resize(NumCounterValues); -} - Counter CounterExpressionBuilder::get(const CounterExpression &E) { for (unsigned I = 0, S = Expressions.size(); I < S; ++I) { if (Expressions[I] == E) @@ -40,50 +36,68 @@ Counter CounterExpressionBuilder::get(const CounterExpression &E) { return Counter::getExpression(Expressions.size() - 1); } -void CounterExpressionBuilder::extractTerms(Counter C, int Sign) { +void CounterExpressionBuilder::extractTerms( + Counter C, int Sign, SmallVectorImpl> &Terms) { switch (C.getKind()) { case Counter::Zero: break; case Counter::CounterValueReference: - Terms[C.getCounterID()] += Sign; + Terms.push_back(std::make_pair(C.getCounterID(), Sign)); break; case Counter::Expression: const auto &E = Expressions[C.getExpressionID()]; - extractTerms(E.LHS, Sign); - extractTerms(E.RHS, E.Kind == CounterExpression::Subtract ? -Sign : Sign); + extractTerms(E.LHS, Sign, Terms); + extractTerms(E.RHS, E.Kind == CounterExpression::Subtract ? -Sign : Sign, + Terms); break; } } Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) { // Gather constant terms. - for (auto &I : Terms) - I = 0; - extractTerms(ExpressionTree); + llvm::SmallVector, 32> Terms; + extractTerms(ExpressionTree, +1, Terms); + + // Group the terms by counter ID. + std::sort(Terms.begin(), Terms.end(), + [](const std::pair &LHS, + const std::pair &RHS) { + return LHS.first < RHS.first; + }); + + // Combine terms by counter ID to eliminate counters that sum to zero. + auto Prev = Terms.begin(); + for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) { + if (I->first == Prev->first) { + Prev->second += I->second; + continue; + } + ++Prev; + *Prev = *I; + } + Terms.erase(++Prev, Terms.end()); Counter C; - // Create additions. - // Note: the additions are created first - // to avoid creation of a tree like ((0 - X) + Y) instead of (Y - X). - for (unsigned I = 0, S = Terms.size(); I < S; ++I) { - if (Terms[I] <= 0) + // Create additions. We do this before subtractions to avoid constructs like + // ((0 - X) + Y), as opposed to (Y - X). + for (auto Term : Terms) { + if (Term.second <= 0) continue; - for (int J = 0; J < Terms[I]; ++J) { + for (int I = 0; I < Term.second; ++I) if (C.isZero()) - C = Counter::getCounter(I); + C = Counter::getCounter(Term.first); else C = get(CounterExpression(CounterExpression::Add, C, - Counter::getCounter(I))); - } + Counter::getCounter(Term.first))); } // Create subtractions. - for (unsigned I = 0, S = Terms.size(); I < S; ++I) { - if (Terms[I] >= 0) + for (auto Term : Terms) { + if (Term.second >= 0) continue; - for (int J = 0; J < (-Terms[I]); ++J) + for (int I = 0; I < -Term.second; ++I) C = get(CounterExpression(CounterExpression::Subtract, C, - Counter::getCounter(I))); + Counter::getCounter(Term.first))); } return C; } -- 2.34.1