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

 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/Local.h"
-#include <list>
+#include <algorithm>
 using namespace llvm;
 
 #define DEBUG_TYPE "memcpyopt"

 
 namespace {
 class MemsetRanges {
-  /// Ranges - A sorted list of the memset ranges.  We use std::list here
-  /// because each element is relatively large and expensive to copy.
-  std::list<MemsetRange> Ranges;
-  typedef std::list<MemsetRange>::iterator range_iterator;
+  /// Ranges - A sorted list of the memset ranges.
+  SmallVector<MemsetRange, 8> Ranges;
+  typedef SmallVectorImpl<MemsetRange>::iterator range_iterator;
   const DataLayout &DL;
 public:
   MemsetRanges(const DataLayout &DL) : DL(DL) {}
 
-  typedef std::list<MemsetRange>::const_iterator const_iterator;
+  typedef SmallVectorImpl<MemsetRange>::const_iterator const_iterator;
   const_iterator begin() const { return Ranges.begin(); }
   const_iterator end() const { return Ranges.end(); }
   bool empty() const { return Ranges.empty(); }

 /// 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;
+  range_iterator I = std::lower_bound(Ranges.begin(), Ranges.end(), Start,
+    [](const MemsetRange &LHS, int64_t RHS) { return LHS.End < RHS; });
 
   // 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) {
+  if (I == Ranges.end() || End < I->Start) {
     MemsetRange &R = *Ranges.insert(I, MemsetRange());
     R.Start        = Start;
     R.End          = End;

   if (End > I->End) {
     I->End = End;
     range_iterator NextI = I;
-    while (++NextI != E && End >= NextI->Start) {
+    while (++NextI != Ranges.end() && End >= NextI->Start) {
       // Merge the range in.
       I->TheStores.append(NextI->TheStores.begin(), NextI->TheStores.end());
       if (NextI->End > I->End)