Avoid insertion sorting each new range in MemCpyOptimizer

[inolen]

Summary

While working on a project I wound up generating a fairly large lookup table (10k entries) of callbacks inside of a static constructor. Clang was taking upwards of ~10 minutes to compile the lookup table. I generated a smaller test case (http://www.inolen.com/static_initializer_test.ll) that, after running with -ftime-report, pointed fingers at GlobalOpt and MemCpyOptimizer.

Running memcpyopt through opt accounted for around ~1 minute. The main culprit was MemCpyOptimizer insertion sorting the ranges as it discovered them in tryMergingIntoMemset. I've changed this up such that ranges are always appended to the list, and once they've all been added they're sorted and merged (n log n vs n^2).

I'm not really sure who to tag as a reviewer, Lang mentioned that Chandler may be appropriate.

[nlewycky]

I'm worried about the memory usage of storing all of them. It feels like you traded CPU time for more memory when you didn't need to.

The problem was that it did a linear scan to find the range with the nearest start value. That list is already stored sorted. Why not just use bisection (std::lower_bound) to find it, saving CPU time without increasing memory usage?

lib/Transforms/Scalar/MemCpyOptimizer.cpp

258

Should be named "Head". See http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly .

403–404

I don't have a suggestion, but I think the terminology of add/merge feels weird. You're really doing an enqueue (to be resolved later) and then resolve, but that's not much better working.

[inolen]

Alright, patch updated to use std::lower_bound.

I converted over from std::list to SmallVector to have a random access iterator for std::lower_bound.

It originally used std::list to avoid expensive copies when merging ranges, but now with move semantics, I don't think this is as serious of a concern.

[nicholas]

lib/Transforms/Scalar/MemCpyOptimizer.cpp

255

Optional: consider hoisting "Ranges.end()" out to "range_iterator E = Ranges.end;". See http://llvm.org/docs/CodingStandards.html#don-t-evaluate-end-every-time-through-a-loop .

[inolen]

lib/Transforms/Scalar/MemCpyOptimizer.cpp

255

I'd removed the end iterator local due to it being invalidated during the loop at the bottom which calls Ranges.erase().

[Eugene.Zelenko]

Committed in rL242843.

lib/Transforms/Scalar/MemCpyOptimizer.cpp

 
   // If any of the stores are a memset, then it is always good to extend the
   // memset.
-  for (unsigned i = 0, e = TheStores.size(); i != e; ++i)
-    if (!isa<StoreInst>(TheStores[i]))
+  for (auto it : TheStores)
+    if (!isa<StoreInst>(*it))
       return true;
 
   // Assume that the code generator is capable of merging pairs of stores

   void addRange(int64_t Start, int64_t Size, Value *Ptr,
                 unsigned Alignment, Instruction *Inst);
 
+  void mergeRanges();
 };
 
 } // end anon namespace
 
-
-/// addRange - Add a new store to the MemsetRanges data structure.  This adds a
-/// new range for the specified store at the specified offset, merging into
-/// existing ranges as appropriate.
-///
-/// Do a linear search of the ranges to see if this can be joined and/or to
-/// find the insertion point in the list.  We keep the ranges sorted for
-/// simplicity here.  This is a linear search of a linked list, which is ugly,
-/// however the number of ranges is limited, so this won't get crazy slow.
 void MemsetRanges::addRange(int64_t Start, int64_t Size, Value *Ptr,
                             unsigned Alignment, Instruction *Inst) {
   int64_t End = Start+Size;
-  range_iterator I = Ranges.begin(), E = Ranges.end();
-
-  while (I != E && Start > I->End)
-    ++I;
-
-  // We now know that I == E, in which case we didn't find anything to merge
-  // with, or that Start <= I->End.  If End < I->Start or I == E, then we need
-  // to insert a new range.  Handle this now.
-  if (I == E || End < I->Start) {
-    MemsetRange &R = *Ranges.insert(I, MemsetRange());
-    R.Start        = Start;
-    R.End          = End;
-    R.StartPtr     = Ptr;
-    R.Alignment    = Alignment;
-    R.TheStores.push_back(Inst);
-    return;
-  }
-
-  // This store overlaps with I, add it.
-  I->TheStores.push_back(Inst);
-
-  // At this point, we may have an interval that completely contains our store.
-  // If so, just add it to the interval and return.
-  if (I->Start <= Start && I->End >= End)
-    return;
-
-  // Now we know that Start <= I->End and End >= I->Start so the range overlaps
-  // but is not entirely contained within the range.
-
-  // See if the range extends the start of the range.  In this case, it couldn't
-  // possibly cause it to join the prior range, because otherwise we would have
-  // stopped on *it*.
-  if (Start < I->Start) {
-    I->Start = Start;
-    I->StartPtr = Ptr;
-    I->Alignment = Alignment;
-  }
+  Ranges.push_back(MemsetRange { Start, End, Ptr, Alignment, { Inst } });
+}
 
-  // Now we know that Start <= I->End and Start >= I->Start (so the startpoint
-  // is in or right at the end of I), and that End >= I->Start.  Extend I out to
-  // End.
-  if (End > I->End) {
-    I->End = End;
-    range_iterator NextI = I;
-    while (++NextI != E && End >= NextI->Start) {
-      // Merge the range in.
-      I->TheStores.append(NextI->TheStores.begin(), NextI->TheStores.end());
-      if (NextI->End > I->End)
-        I->End = NextI->End;
-      Ranges.erase(NextI);
-      NextI = I;
+void MemsetRanges::mergeRanges() {
+  // Sort ranges by their starting address.
+  Ranges.sort([](const MemsetRange &lhs, const MemsetRange &rhs) {
+    return lhs.Start < rhs.Start;
+  });
+
+  // Merge overlapping ranges.
+  range_iterator I = Ranges.begin();
+  range_iterator E = Ranges.end();
+  range_iterator HEAD = I++;
+
+  while (I != E) {
+    if (I->Start > HEAD->End) {
+      // New interval, don't merge.
+      HEAD = I++;
+    } else {
+      // Interval overlaps with head, merge it.
+      HEAD->End = std::max(HEAD->End, I->End);
+      HEAD->TheStores.append(I->TheStores.begin(), I->TheStores.end());
+      Ranges.erase(I++);
     }
   }
 }

   // interesting as a small compile-time optimization.
   Ranges.addInst(0, StartInst);
 
+  // Merge overlapping ranges.
+  Ranges.mergeRanges();
+
   // If we create any memsets, we put it right before the first instruction that
   // isn't part of the memset block.  This ensure that the memset is dominated
   // by any addressing instruction needed by the start of the block.

       Builder.CreateMemSet(StartPtr, ByteVal, Range.End-Range.Start, Alignment);
 
     DEBUG(dbgs() << "Replace stores:\n";
-          for (unsigned i = 0, e = Range.TheStores.size(); i != e; ++i)
-            dbgs() << *Range.TheStores[i] << '\n';
+          for (auto it : Range.TheStores)
+            dbgs() << *it << '\n';
           dbgs() << "With: " << *AMemSet << '\n');
 
     if (!Range.TheStores.empty())