Revert "InstrProf: Don't keep a large sparse list around just to zero it"

This seems to be crashing on some buildbots. Reverting to investigate.

This reverts commit r218879.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@218881 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/ProfileData/CoverageMapping.h b/include/llvm/ProfileData/CoverageMapping.h
index 8f73217c4d4794d29a40bdda41db1088789a4897..6d833648a17aac709fed5f6edfc7060a7a7739a8 100644 (file)
--- a/include/llvm/ProfileData/CoverageMapping.h
+++ b/include/llvm/ProfileData/CoverageMapping.h
@@ -103,6 +103,8 @@ struct CounterExpression {
 class CounterExpressionBuilder {
   /// \brief A list of all the counter expressions
   llvm::SmallVector<CounterExpression, 16> Expressions;
 class CounterExpressionBuilder {
   /// \brief A list of all the counter expressions
   llvm::SmallVector<CounterExpression, 16> Expressions;

+  /// \brief An array of terms used in expression simplification.
+  llvm::SmallVector<int, 16> Terms;

 
   /// \brief Return the counter which corresponds to the given expression.
   ///
 
   /// \brief Return the counter which corresponds to the given expression.
   ///


@@ -111,19 +113,18 @@ class CounterExpressionBuilder {
   /// expression is added to the builder's collection of expressions.
   Counter get(const CounterExpression &E);
 
   /// expression is added to the builder's collection of expressions.
   Counter get(const CounterExpression &E);
 

-  /// \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<std::pair<unsigned, int>> &Terms);
+  /// \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 Simplifies the given expression tree
   /// by getting rid of algebraically redundant operations.
   Counter simplify(Counter ExpressionTree);
 
 public:
 
   /// \brief Simplifies the given expression tree
   /// by getting rid of algebraically redundant operations.
   Counter simplify(Counter ExpressionTree);
 
 public:

+  CounterExpressionBuilder(unsigned NumCounterValues);
+

   ArrayRef<CounterExpression> getExpressions() const { return Expressions; }
 
   /// \brief Return a counter that represents the expression
   ArrayRef<CounterExpression> 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 3a568720b08ad883f8c4e8c334e9417e304d824e..115256358edf513b5089c5e15d145d71110db227 100644 (file)
--- a/lib/ProfileData/CoverageMapping.cpp
+++ b/lib/ProfileData/CoverageMapping.cpp
@@ -27,6 +27,10 @@ using namespace coverage;
 
 #define DEBUG_TYPE "coverage-mapping"
 
 
 #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)
 Counter CounterExpressionBuilder::get(const CounterExpression &E) {
   for (unsigned I = 0, S = Expressions.size(); I < S; ++I) {
     if (Expressions[I] == E)


@@ -36,68 +40,50 @@ Counter CounterExpressionBuilder::get(const CounterExpression &E) {
   return Counter::getExpression(Expressions.size() - 1);
 }
 
   return Counter::getExpression(Expressions.size() - 1);
 }
 

-void CounterExpressionBuilder::extractTerms(
-    Counter C, int Sign, SmallVectorImpl<std::pair<unsigned, int>> &Terms) {
+void CounterExpressionBuilder::extractTerms(Counter C, int Sign) {

   switch (C.getKind()) {
   case Counter::Zero:
     break;
   case Counter::CounterValueReference:
   switch (C.getKind()) {
   case Counter::Zero:
     break;
   case Counter::CounterValueReference:

-    Terms.push_back(std::make_pair(C.getCounterID(), Sign));
+    Terms[C.getCounterID()] += Sign;

     break;
   case Counter::Expression:
     const auto &E = Expressions[C.getExpressionID()];
     break;
   case Counter::Expression:
     const auto &E = Expressions[C.getExpressionID()];

-    extractTerms(E.LHS, Sign, Terms);
-    extractTerms(E.RHS, E.Kind == CounterExpression::Subtract ? -Sign : Sign,
-                 Terms);
+    extractTerms(E.LHS, Sign);
+    extractTerms(E.RHS, E.Kind == CounterExpression::Subtract ? -Sign : Sign);

     break;
   }
 }
 
 Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) {
   // Gather constant terms.
     break;
   }
 }
 
 Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) {
   // Gather constant terms.

-  llvm::SmallVector<std::pair<unsigned, int>, 32> Terms;
-  extractTerms(ExpressionTree, +1, Terms);
-
-  // Group the terms by counter ID.
-  std::sort(Terms.begin(), Terms.end(),
-            [](const std::pair<unsigned, int> &LHS,
-               const std::pair<unsigned, int> &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());
+  for (auto &I : Terms)
+    I = 0;
+  extractTerms(ExpressionTree);

 
   Counter C;
 
   Counter C;

-  // 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)
+  // 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)

       continue;
       continue;

-    for (int I = 0; I < Term.second; ++I)
+    for (int J = 0; J < Terms[I]; ++J) {

       if (C.isZero())
       if (C.isZero())

-        C = Counter::getCounter(Term.first);
+        C = Counter::getCounter(I);

       else
         C = get(CounterExpression(CounterExpression::Add, C,
       else
         C = get(CounterExpression(CounterExpression::Add, C,

-                                  Counter::getCounter(Term.first)));
+                                  Counter::getCounter(I)));
+    }

   }
 
   // Create subtractions.
   }
 
   // Create subtractions.

-  for (auto Term : Terms) {
-    if (Term.second >= 0)
+  for (unsigned I = 0, S = Terms.size(); I < S; ++I) {
+    if (Terms[I] >= 0)

       continue;
       continue;

-    for (int I = 0; I < -Term.second; ++I)
+    for (int J = 0; J < (-Terms[I]); ++J)

       C = get(CounterExpression(CounterExpression::Subtract, C,
       C = get(CounterExpression(CounterExpression::Subtract, C,

-                                Counter::getCounter(Term.first)));
+                                Counter::getCounter(I)));

   }
   return C;
 }
   }
   return C;
 }