[LoopIdiom] Ignore memory accesses to constant memory

[aeubanks]

Summary

A loop wasn't recognized as a memcpy because the load was thought to
potentially alias with the store. We should ignore memory operations to
constant memory since moving instructions around cannot change their
results.

[xbolva00]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

881

just return true; (no else)

[aeubanks]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

881

then the newly introduced if condition is useless if we always return true

[xbolva00]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

881

yeah, oh! sorry:)

[nikic]

While this works, I don't think this really addresses the root problem of D101017. Your example already folds fine with -globals-aa -loop-idiom. If GlobalsAA is not available at the time LoopIdiom runs, then that's a bug...

[nikic]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

876

Without looking at the users of this function, just going by the contract on the function, I think you can only do this if Access is Mod (as you can't write to constant memory), but not if Access is Ref or ModRef.

[aeubanks]

In D101190#2713091, @nikic wrote:

While this works, I don't think this really addresses the root problem of D101017. Your example already folds fine with -globals-aa -loop-idiom. If GlobalsAA is not available at the time LoopIdiom runs, then that's a bug...

oh you're right, for some reason I thought this transform wasn't happening even with globals-aa

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

bool LoopIdiomRecognize::processLoopMemSet(MemSetInst *MSI,
   return processLoopStridedStore(
       Pointer, (unsigned)SizeInBytes, MaybeAlign(MSI->getDestAlignment()),
       SplatValue, MSI, MSIs, Ev, BECount, NegStride, /*IsLoopMemset=*/true);
 }
 
 /// 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).
+/// Ignore any accesses to constant memory.
 static bool
 mayLoopAccessLocation(Value *Ptr, ModRefInfo Access, Loop *L,
                       const SCEV *BECount, unsigned StoreSize,
                       AliasAnalysis &AA,
                       SmallPtrSetImpl<Instruction *> &IgnoredStores) {
   // Get the location that may be stored across the loop.  Since the access is
   // strided positively through memory, we say that the modified location starts
   // at the pointer and has infinite size.
   LocationSize AccessSize = LocationSize::afterPointer();
 
   // If the loop iterates a fixed number of times, we can refine the access size
   // to be exactly the size of the memset, which is (BECount+1)*StoreSize
   if (const SCEVConstant *BECst = dyn_cast<SCEVConstant>(BECount))
     AccessSize = LocationSize::precise((BECst->getValue()->getZExtValue() + 1) *
                                        StoreSize);
 
   // TODO: For this to be really effective, we have to dive into the pointer
   // operand in the store.  Store to &A[i] of 100 will always return may alias
   // with store of &A[100], we need to StoreLoc to be "A" with size of 100,
   // which will then no-alias a store to &A[100].
   MemoryLocation StoreLoc(Ptr, AccessSize);
 
   for (Loop::block_iterator BI = L->block_begin(), E = L->block_end(); BI != E;
-       ++BI)
-    for (Instruction &I : **BI)
+       ++BI) {
+    for (Instruction &I : **BI) {
       if (IgnoredStores.count(&I) == 0 &&
           isModOrRefSet(
-              intersectModRef(AA.getModRefInfo(&I, StoreLoc), Access)))
+              intersectModRef(AA.getModRefInfo(&I, StoreLoc), Access))) {
+        if (auto MemLoc = MemoryLocation::getOrNone(&I)) {
+          if (!AA.pointsToConstantMemory(*MemLoc)) {
             return true;
+          }
+        } else {
+          return true;
+        }
+      }
+    }
+  }
 
   return false;
 }
 
 // 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 base pointer,
 // which is just Start - BECount*Size.
 static const SCEV *getStartForNegStride(const SCEV *Start, const SCEV *BECount,

llvm/test/Transforms/LoopIdiom/memcpy.ll

for.body:
   %incdec.ptr = getelementptr inbounds i8, i8* %q.addr.05, i64 1
   %0 = load i8, i8* %q.addr.05, align 1
   %incdec.ptr1 = getelementptr inbounds i8, i8* %p.addr.06, i64 1
   store i8 %0, i8* %p.addr.06, align 1
   %inc = add nuw nsw i32 %i.07, 1
   %exitcond.not = icmp eq i32 %inc, %n
   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
 }
+
+@__const.f.c = private unnamed_addr constant [20 x double] [double 1.051000e-01, double 1.570000e-02, double 1.850000e-02, double 0x3F823A29C779A6B5, double 2.190000e-02, double 1.410000e-02, double 9.700000e-03, double 7.580000e-02, double 1.680000e-02, double 1.188000e-01, double 1.635000e-01, double 1.120000e-02, double 3.330000e-02, double 7.770000e-02, double 2.600000e-02, double 5.680000e-02, double 5.230000e-02, double 2.230000e-02, double 3.240000e-02, double 1.195000e-01], align 16
+
+define void @memcpy_from_const_global(double* nocapture %a) {
+; CHECK-LABEL: @memcpy_from_const_global(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A1:%.*]] = bitcast double* [[A:%.*]] to i8*
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 8 [[A1]], i8* align 8 bitcast ([20 x double]* @__const.f.c to i8*), i64 160, i1 false)
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    ret void
+; CHECK:       for.body:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [20 x double], [20 x double]* @__const.f.c, i64 0, i64 [[INDVARS_IV]]
+; CHECK-NEXT:    [[TMP0:%.*]] = load double, double* [[ARRAYIDX]], align 8
+; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds double, double* [[A]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], 20
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_COND_CLEANUP:%.*]]
+;
+entry:
+  br label %for.body
+
+for.cond.cleanup:
+  ret void
+
+for.body:
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds [20 x double], [20 x double]* @__const.f.c, i64 0, i64 %indvars.iv
+  %0 = load double, double* %arrayidx, align 8
+  %arrayidx2 = getelementptr inbounds double, double* %a, i64 %indvars.iv
+  store double %0, double* %arrayidx2, align 8
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 20
+  br i1 %exitcond, label %for.body, label %for.cond.cleanup
+}