[LIR] Add support for creating memsets from loops with a negative stride.

[mcrosier]

Summary

This change adds support for transforming loops such as

void test (unsigned *f) {

for (int i = 65536; i >= 0; i--) {
   f[i] = 0;
}

}

into memsets. Previously, we were unable to transform loops with negative strides.

Passes all correctness for Spec2000, Spec2006, and LNT. Transforms a number of benchmarks in Spec2000 and Spec2006.

Please take a look.

Chad

[mssimpso]

This looks reasonable to me, but I'll let someone else approve.

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

33

You can update this comment to reflect that we can handle negative strides with this patch. Loop reversal is a separate optimization, so I think it makes sense to catch the simple case here, especially since the implementation is minimal. The follow-on patch would be to handle the negative stride in processLoopMemSet.

[mcrosier]

Remove comment about adding support for negative strides.

[mcrosier]

Thanks for the feedback, Matt.

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

33

I do plan on implementing the follow-on patch, but I wanted to land this simple patch first.

[chandlerc]

LGTM, awesome patch!

[mcrosier]

Committed in r251518. Thanks, Chandler.

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

 // Beware that isel's default lowering for ctpop is highly inefficient for
 // i64 and larger types when i64 is legal and the value has few bits set.  It
 // would be good to enhance isel to emit a loop for ctpop in this case.
 //
 // We should enhance the memset/memcpy recognition to handle multiple stores in
 // the loop.  This would handle things like:
 //   void foo(_Complex float *P)
 //     for (i) { __real__(*P) = 0;  __imag__(*P) = 0; }
 //
-// We should enhance this to handle negative strides through memory.
-// Alternatively (and perhaps better) we could rely on an earlier pass to force
-// forward iteration through memory, which is generally better for cache
-// behavior.  Negative strides *do* happen for memset/memcpy loops.
-//
 // This could recognize common matrix multiplies and dot product idioms and
 // replace them with calls to BLAS (if linked in??).
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
bool runOnLoopBlock(BasicBlock *BB, const SCEV *BECount,
                       SmallVectorImpl<BasicBlock *> &ExitBlocks);
 
   bool processLoopStore(StoreInst *SI, const SCEV *BECount);
   bool processLoopMemSet(MemSetInst *MSI, const SCEV *BECount);
 
   bool processLoopStridedStore(Value *DestPtr, unsigned StoreSize,
                                unsigned StoreAlignment, Value *SplatValue,
                                Instruction *TheStore, const SCEVAddRecExpr *Ev,
-                               const SCEV *BECount);
+                               const SCEV *BECount, bool NegStride);
   bool processLoopStoreOfLoopLoad(StoreInst *SI, unsigned StoreSize,
                                   const SCEVAddRecExpr *StoreEv,
                                   const SCEVAddRecExpr *LoadEv,
                                   const SCEV *BECount);
 
   /// @}
   /// \name Noncountable Loop Idiom Handling
   /// @{
bool LoopIdiomRecognize::processLoopStore(StoreInst *SI, const SCEV *BECount) {
   const SCEVAddRecExpr *StoreEv =
       dyn_cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr));
   if (!StoreEv || StoreEv->getLoop() != CurLoop || !StoreEv->isAffine())
     return false;
 
   // Check to see if the stride matches the size of the store.  If so, then we
   // know that every byte is touched in the loop.
   unsigned StoreSize = (unsigned)SizeInBits >> 3;
-  const SCEVConstant *Stride = dyn_cast<SCEVConstant>(StoreEv->getOperand(1));
 
-  if (!Stride || StoreSize != Stride->getValue()->getValue()) {
-    // TODO: Could also handle negative stride here someday, that will require
-    // the validity check in mayLoopAccessLocation to be updated though.
-    // Enable this to print exact negative strides.
-    if (0 && Stride && StoreSize == -Stride->getValue()->getValue()) {
-      dbgs() << "NEGATIVE STRIDE: " << *SI << "\n";
-      dbgs() << "BB: " << *SI->getParent();
-    }
+  const SCEVConstant *ConstStride =
+      dyn_cast<SCEVConstant>(StoreEv->getOperand(1));
+  if (!ConstStride)
+    return false;
 
+  APInt Stride = ConstStride->getValue()->getValue();
+  if (StoreSize != Stride && StoreSize != -Stride)
     return false;
-  }
+
+  bool NegStride = StoreSize == -Stride;
 
   // See if we can optimize just this store in isolation.
   if (processLoopStridedStore(StorePtr, StoreSize, SI->getAlignment(),
-                              StoredVal, SI, StoreEv, BECount))
+                              StoredVal, SI, StoreEv, BECount, NegStride))
     return true;
 
   // If the stored value is a strided load in the same loop with the same stride
   // this this may be transformable into a memcpy.  This kicks in for stuff like
   //   for (i) A[i] = B[i];
   if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) {
     const SCEVAddRecExpr *LoadEv =
         dyn_cast<SCEVAddRecExpr>(SE->getSCEV(LI->getOperand(0)));
bool LoopIdiomRecognize::processLoopMemSet(MemSetInst *MSI,
 
   // TODO: Could also handle negative stride here someday, that will require the
   // validity check in mayLoopAccessLocation to be updated though.
   if (!Stride || MSI->getLength() != Stride->getValue())
     return false;
 
   return processLoopStridedStore(Pointer, (unsigned)SizeInBytes,
                                  MSI->getAlignment(), MSI->getValue(), MSI, Ev,
-                                 BECount);
+                                 BECount, /*NegStride=*/false);
 }
 
 /// mayLoopAccessLocation - Return true if the specified loop might access the
 /// specified pointer location, which is a loop-strided access.  The 'Access'
 /// argument specifies what the verboten forms of access are (read or write).
 static bool mayLoopAccessLocation(Value *Ptr, ModRefInfo Access, Loop *L,
                                   const SCEV *BECount, unsigned StoreSize,
                                   AliasAnalysis &AA,
static Constant *getMemSetPatternValue(Value *V, const DataLayout &DL) {
   return ConstantArray::get(AT, std::vector<Constant *>(ArraySize, C));
 }
 
 /// processLoopStridedStore - We see a strided store of some value.  If we can
 /// transform this into a memset or memset_pattern in the loop preheader, do so.
 bool LoopIdiomRecognize::processLoopStridedStore(
     Value *DestPtr, unsigned StoreSize, unsigned StoreAlignment,
     Value *StoredVal, Instruction *TheStore, const SCEVAddRecExpr *Ev,
-    const SCEV *BECount) {
+    const SCEV *BECount, bool NegStride) {
 
   // If the stored value is a byte-wise value (like i32 -1), then it may be
   // turned into a memset of i8 -1, assuming that all the consecutive bytes
   // are stored.  A store of i32 0x01020304 can never be turned into a memset,
   // but it can be turned into memset_pattern if the target supports it.
   Value *SplatValue = isBytewiseValue(StoredVal);
   Constant *PatternValue = nullptr;
   auto &DL = CurLoop->getHeader()->getModule()->getDataLayout();
bool LoopIdiomRecognize::processLoopStridedStore(
   // The trip count of the loop and the base pointer of the addrec SCEV is
   // guaranteed to be loop invariant, which means that it should dominate the
   // header.  This allows us to insert code for it in the preheader.
   BasicBlock *Preheader = CurLoop->getLoopPreheader();
   IRBuilder<> Builder(Preheader->getTerminator());
   SCEVExpander Expander(*SE, DL, "loop-idiom");
 
   Type *DestInt8PtrTy = Builder.getInt8PtrTy(DestAS);
+  Type *IntPtr = Builder.getIntPtrTy(DL, DestAS);
+
+  const SCEV *Start = Ev->getStart();
+  // If we have a negative stride, Start refers to the end of the memory
+  // location we're trying to memset.  Therefore, we need to recompute the start
+  // point, which is just Start - BECount*Size.
+  if (NegStride) {
+    const SCEV *Index = SE->getTruncateOrZeroExtend(BECount, IntPtr);
+    if (StoreSize != 1)
+      Index = SE->getMulExpr(Index, SE->getConstant(IntPtr, StoreSize),
+                             SCEV::FlagNUW);
+    Start = SE->getMinusSCEV(Ev->getStart(), Index);
+  }
 
   // Okay, we have a strided store "p[i]" of a splattable value.  We can turn
   // this into a memset in the loop preheader now if we want.  However, this
   // would be unsafe to do if there is anything else in the loop that may read
   // or write to the aliased location.  Check for any overlap by generating the
   // base pointer and checking the region.
-  Value *BasePtr = Expander.expandCodeFor(Ev->getStart(), DestInt8PtrTy,
-                                          Preheader->getTerminator());
-
+  Value *BasePtr =
+      Expander.expandCodeFor(Start, DestInt8PtrTy, Preheader->getTerminator());
   if (mayLoopAccessLocation(BasePtr, MRI_ModRef, CurLoop, BECount, StoreSize,
                             *AA, TheStore)) {
     Expander.clear();
     // If we generated new code for the base pointer, clean up.
     RecursivelyDeleteTriviallyDeadInstructions(BasePtr, TLI);
     return false;
   }
 
   // Okay, everything looks good, insert the memset.
 
   // The # stored bytes is (BECount+1)*Size.  Expand the trip count out to
   // pointer size if it isn't already.
-  Type *IntPtr = Builder.getIntPtrTy(DL, DestAS);
   BECount = SE->getTruncateOrZeroExtend(BECount, IntPtr);
 
   const SCEV *NumBytesS =
       SE->getAddExpr(BECount, SE->getOne(IntPtr), SCEV::FlagNUW);
   if (StoreSize != 1) {
     NumBytesS = SE->getMulExpr(NumBytesS, SE->getConstant(IntPtr, StoreSize),
                                SCEV::FlagNUW);
   }

test/Transforms/LoopIdiom/basic.ll

; CHECK: store
   %next.ptr = getelementptr inbounds i32, i32* %phi.ptr, i64 1
   %cmp = icmp eq i32* %next.ptr, %end.ptr
   br i1 %cmp, label %exit, label %while.body
 
 exit:
   ret void
 ; CHECK: ret void
 }
+
+; Recognize loops with a negative stride.
+define void @test15(i32* nocapture %f) {
+entry:
+  br label %for.body
+
+for.body:
+  %indvars.iv = phi i64 [ 65536, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %f, i64 %indvars.iv
+  store i32 0, i32* %arrayidx, align 4
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %cmp = icmp sgt i64 %indvars.iv, 0
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret void
+; CHECK-LABEL: @test15(
+; CHECK: call void @llvm.memset.p0i8.i64(i8* %f1, i8 0, i64 262148, i32 4, i1 false)
+; CHECK-NOT: store
+; CHECK: ret void
+}