Remove creation of vector to store loop indices

[hiraditya]

Summary

Passes make check. No performance/functionality change.

[efriedma]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

605

This arithmetic is hard to follow... which is why it was written with the vector in the first place.

If you're really unhappy with memory allocation, maybe try using iterators? Something like auto SLRef = makeArrayRef(SL); for (StoreInst *k : concat(SLRef.slice(i+1), reverse(SLRef.slice(0, i - 1))))

[hiraditya]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

605

Ok, then I'll abandon this patch.

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

                                            const SCEV *BECount,
                                            bool ForMemset) {
   // Try to find consecutive stores that can be transformed into memsets.
   SetVector<StoreInst *> Heads, Tails;
   SmallDenseMap<StoreInst *, StoreInst *> ConsecutiveChain;
 
   // Do a quadratic search on all of the given stores and find
   // all of the pairs of stores that follow each other.
-  SmallVector<unsigned, 16> IndexQueue;
-  for (unsigned i = 0, e = SL.size(); i < e; ++i) {
+  for (int i = 0, e = SL.size(); i < e; ++i) {
     assert(SL[i]->isSimple() && "Expected only non-volatile stores.");
 
     Value *FirstStoredVal = SL[i]->getValueOperand();
     Value *FirstStorePtr = SL[i]->getPointerOperand();
     const SCEVAddRecExpr *FirstStoreEv =
         cast<SCEVAddRecExpr>(SE->getSCEV(FirstStorePtr));
     APInt FirstStride = getStoreStride(FirstStoreEv);
     unsigned FirstStoreSize = getStoreSizeInBytes(SL[i], DL);

     if (ForMemset)
       FirstSplatValue = isBytewiseValue(FirstStoredVal);
     else
       FirstPatternValue = getMemSetPatternValue(FirstStoredVal, DL);
 
     assert((FirstSplatValue || FirstPatternValue) &&
            "Expected either splat value or pattern value.");
 
-    IndexQueue.clear();
     // If a store has multiple consecutive store candidates, search Stores
-    // array according to the sequence: from i+1 to e, then from i-1 to 0.
+    // array according to the sequence: from [i+1, e), then from [i-1, 0].
     // This is because usually pairing with immediate succeeding or preceding
     // candidate create the best chance to find memset opportunity.
-    unsigned j = 0;
-    for (j = i + 1; j < e; ++j)
-      IndexQueue.push_back(j);
-    for (j = i; j > 0; --j)
-      IndexQueue.push_back(j - 1);
+    // k varies from [i+1,e), [i-1,0]
+    int delta = 1;
+    int it = 0;
+    int k = i+1;
+    if (k == e) { // [i+1, e) cannot be done.
+      k = i-1;
+      delta = -1;
+    }
 
-    for (auto &k : IndexQueue) {
+    for ( ; k >= 0; k = it) {
       assert(SL[k]->isSimple() && "Expected only non-volatile stores.");
+      it = k;
+      if (it+1 == e) {
+        it = i;
+        delta = -1;
+      }
+
+      it += delta;
+
       Value *SecondStorePtr = SL[k]->getPointerOperand();
       const SCEVAddRecExpr *SecondStoreEv =
           cast<SCEVAddRecExpr>(SE->getSCEV(SecondStorePtr));
       APInt SecondStride = getStoreStride(SecondStoreEv);
 
       if (FirstStride != SecondStride)
         continue;