[ScopInfo] Make memset etc. affine where possible.

[efriedma]

Summary

We don't actually check whether a MemoryAccess is affine in very many places, but one important one is in checks for aliasing.

[efriedma]

Delete outdated comment.

[jdoerfert]

While I agree with the commit message, I am not aware of any real benefit this will provide us given that we only leverage the constant range ScalarEvolution range analysis. If we would use a better one, e.g., along the lines of https://reviews.llvm.org/D20230, I think this patch does make sense.

This opinion was basically written down in the code:

// Check if we have non-affine accesses left, if so bail out as we cannot
// generate a good access range yet.

[efriedma]

We ran into a case similar to the included testcase, where we need to generate a runtime alias check with a memset in order to vectorize a loop. (memset isn't really non-affine, but we currently model it that way.)

[jdoerfert]

In D25706#573332, @efriedma wrote:

We ran into a case similar to the included testcase, where we need to generate a runtime alias check with a memset in order to vectorize a loop. (memset isn't really non-affine, but we currently model it that way.)

Why don't we then treat a memset/memcpy/memmove with affine length as affine access instead?
E.g. replace the "false" in ScopBuilder.cpp line 279 and 300 with "LengthIsAffine"?

[efriedma]

I assumed there was some reason we were treating the memset as non-affine... if there isn't, I'm happy to change it.

[jdoerfert]

You also have to adjust the call location to

buildMemIntrinsicAccessRelation

but I think this is the best way to go.

[efriedma]

Ping.

[efriedma]

Ping.

[jdoerfert]

LGTM.

polly/trunk/lib/Analysis/ScopBuilder.cpp

bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, Loop *L) {
   //       as we know it would be undefined to execute this instruction anyway.
   if (DestAccFunc->isZero())
     return true;
 
   auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(DestAccFunc));
   assert(DestPtrSCEV);
   DestAccFunc = SE.getMinusSCEV(DestAccFunc, DestPtrSCEV);
   addArrayAccess(Inst, MemoryAccess::MUST_WRITE, DestPtrSCEV->getValue(),
-                 IntegerType::getInt8Ty(DestPtrVal->getContext()), false,
-                 {DestAccFunc, LengthVal}, {nullptr}, Inst.getValueOperand());
+                 IntegerType::getInt8Ty(DestPtrVal->getContext()),
+                 LengthIsAffine, {DestAccFunc, LengthVal}, {nullptr},
+                 Inst.getValueOperand());
 
   auto *MemTrans = dyn_cast<MemTransferInst>(MemIntr);
   if (!MemTrans)
     return true;
 
   auto *SrcPtrVal = MemTrans->getSource();
   assert(SrcPtrVal);
 
   auto *SrcAccFunc = SE.getSCEVAtScope(SrcPtrVal, L);
   assert(SrcAccFunc);
   // Ignore accesses to "NULL".
   // TODO: See above TODO
   if (SrcAccFunc->isZero())
     return true;
 
   auto *SrcPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(SrcAccFunc));
   assert(SrcPtrSCEV);
   SrcAccFunc = SE.getMinusSCEV(SrcAccFunc, SrcPtrSCEV);
   addArrayAccess(Inst, MemoryAccess::READ, SrcPtrSCEV->getValue(),
-                 IntegerType::getInt8Ty(SrcPtrVal->getContext()), false,
-                 {SrcAccFunc, LengthVal}, {nullptr}, Inst.getValueOperand());
+                 IntegerType::getInt8Ty(SrcPtrVal->getContext()),
+                 LengthIsAffine, {SrcAccFunc, LengthVal}, {nullptr},
+                 Inst.getValueOperand());
 
   return true;
 }
 
 bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, Loop *L) {
   auto *CI = dyn_cast_or_null<CallInst>(Inst);
 
   if (CI == nullptr)

polly/trunk/lib/Analysis/ScopInfo.cpp

void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {
   // access relation is not modeled correctly.
   auto *StmtInvalidDomain = getStatement()->getInvalidDomain();
   InvalidDomain = isl_set_empty(isl_set_get_space(StmtInvalidDomain));
   isl_set_free(StmtInvalidDomain);
 
   isl_ctx *Ctx = isl_id_get_ctx(Id);
   isl_id *BaseAddrId = SAI->getBasePtrId();
 
-  if (!isAffine()) {
-    if (isa<MemIntrinsic>(getAccessInstruction()))
-      buildMemIntrinsicAccessRelation();
+  if (getAccessInstruction() && isa<MemIntrinsic>(getAccessInstruction())) {
+    AccessRelation =
+        isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId);
+    return;
+  }
 
+  if (!isAffine()) {
     // We overapproximate non-affine accesses with a possible access to the
     // whole array. For read accesses it does not make a difference, if an
     // access must or may happen. However, for write accesses it is important to
     // differentiate between writes that must happen and writes that may happen.
     if (!AccessRelation)
       AccessRelation = isl_map_from_basic_map(createBasicAccessMap(Statement));
 
     AccessRelation =

polly/trunk/test/ScopInfo/aliasing_with_non_affine_access.ll

-; RUN: opt %loadPolly -analyze -polly-scops < %s | FileCheck %s
-; RUN: opt %loadPolly -analyze -polly-scops -pass-remarks-analysis="polly-scops" 2>&1 < %s | FileCheck %s --check-prefix=REMARK
+; RUN: opt %loadPolly -analyze -polly-ast -polly-process-unprofitable -polly-allow-nonaffine < %s | FileCheck %s
 ;
-; This test case has a non-affine access (the memset call) that aliases with
-; other accesses. Thus, we bail out.
+; @test1
+; Make sure we generate the correct aliasing check for a fixed-size memset operation.
+; CHECK: if (1 && (&MemRef_0[15] <= &MemRef_1[0] || &MemRef_1[32] <= &MemRef_0[14]))
 ;
-; CHECK-NOT: Statements
+; @test2
+; Make sure we generate the correct aliasing check for a variable-size memset operation.
+; CHECK: if (1 && (&MemRef_0[15] <= &MemRef_1[0] || &MemRef_1[n] <= &MemRef_0[14]))
 ;
-; REMARK:        remark: <unknown>:0:0: SCoP begins here.
-; REMARK-NEXT:   remark: <unknown>:0:0: Possibly aliasing pointer, use restrict keyword.
-; REMARK-NEXT:   remark: <unknown>:0:0: Possibly aliasing pointer, use restrict keyword.
-; REMARK-NEXT:   remark: <unknown>:0:0: No-aliasing assumption: {  : 1 = 0 }
-; REMARK-NEXT:   remark: <unknown>:0:0: SCoP ends here but was dismissed.
+; @test3
+; We can't do anything interesting with a non-affine memset; just make sure it doesn't crash.
 ;
-; ModuleID = 'bugpoint-reduced-simplified.bc'
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 %struct.info = type { i32, %struct.ctr*, i32, %struct.ord*, %struct.ctr*, i32, i8*, i32, i32, double }
 %struct.ctr = type { i32, i8, i8, i32 }
 %struct.ord = type { i32, i8 }
 
 ; Function Attrs: argmemonly nounwind
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) #0
 
-; Function Attrs: nounwind uwtable
-define void @bestVirtualIndex(%struct.info** %ppIdxInfo) {
+define void @test1(%struct.info** %ppIdxInfo) {
 entry:
   %0 = load %struct.info*, %struct.info** %ppIdxInfo, align 8
   br label %if.end125
 
 if.end125:                                        ; preds = %entry
   %1 = load %struct.ctr*, %struct.ctr** undef, align 8
   br label %for.end143
 
 for.end143:                                       ; preds = %if.end125
   %2 = bitcast %struct.ctr* %1 to i8*
   tail call void @llvm.memset.p0i8.i64(i8* %2, i8 0, i64 32, i32 4, i1 false)
   %needToFreeIdxStr = getelementptr inbounds %struct.info, %struct.info* %0, i64 0, i32 7
   %3 = load i32, i32* %needToFreeIdxStr, align 8
   br i1 false, label %if.end149, label %if.then148
 
 if.then148:                                       ; preds = %for.end143
   br label %if.end149
 
 if.end149:                                        ; preds = %if.then148, %for.end143
   unreachable
 }
 
+define void @test2(%struct.info** %ppIdxInfo, i64 %n) {
+entry:
+  %0 = load %struct.info*, %struct.info** %ppIdxInfo, align 8
+  br label %if.end125
+
+if.end125:                                        ; preds = %entry
+  %1 = load %struct.ctr*, %struct.ctr** undef, align 8
+  br label %for.end143
+
+for.end143:                                       ; preds = %if.end125
+  %2 = bitcast %struct.ctr* %1 to i8*
+  tail call void @llvm.memset.p0i8.i64(i8* %2, i8 0, i64 %n, i32 4, i1 false)
+  %needToFreeIdxStr = getelementptr inbounds %struct.info, %struct.info* %0, i64 0, i32 7
+  %3 = load i32, i32* %needToFreeIdxStr, align 8
+  br i1 false, label %if.end149, label %if.then148
+
+if.then148:                                       ; preds = %for.end143
+  br label %if.end149
+
+if.end149:                                        ; preds = %if.then148, %for.end143
+  unreachable
+}
+
+define i32 @test3(i32* %x, i32 %n) {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  %conv = sext i32 %n to i64
+  %cmp8 = icmp sgt i32 %n, 0
+  br i1 %cmp8, label %for.body.lr.ph, label %for.cond.cleanup
+
+for.body.lr.ph:                                   ; preds = %entry.split
+  %0 = bitcast i32* %x to i8*
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry.split
+  ret i32 0
+
+for.body:                                         ; preds = %for.body, %for.body.lr.ph
+  %i.09 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]
+  %mul = mul nsw i64 %i.09, %i.09
+  tail call void @llvm.memset.p0i8.i64(i8* %0, i8 0, i64 %mul, i32 4, i1 false)
+  %add = add nuw nsw i64 %i.09, 1000
+  %arrayidx = getelementptr inbounds i32, i32* %x, i64 %add
+  store i32 5, i32* %arrayidx, align 4
+  %inc = add nuw nsw i64 %i.09, 1
+  %exitcond = icmp eq i64 %inc, %conv
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
 attributes #0 = { argmemonly nounwind }