[Polly][ScopDetection] Only allow SCoP-wide available base pointers

[Meinersbur]

Summary

Simplify ScopDetection::isInvariant. Essentially deny everything that is defined within the SCoP and is not load-hoisted.

The previous understanding of "invariant" has a few holes:

• Expressions without side-effects with only invariant arguments, but are defined withing the SCoP's region with the exception of selects [sic!] and PHIs. These should be part of the index expression and not of the base pointer.

• Function calls with !mayHaveSideEffects() (readnone nounwind). These must always return the same value and have no side-effect. However, we do not know which value it returns. For instance, a call

@C = external global i32
...
%ptr = call float* @getNextBasePtr(float* %A, float %B)

Might return

• %A, so it aliases with it in the SCoP
• %B, so it aliases with it in the SCoP
• @C, so it aliases with it in the SCoP
• a new pointer everytime it is called, such as malloc()
• a pointer into the allocated block of one of the aforementioned
• any of the above, at random

Hence we cannot know whether it aliases with something. It might still be useful with -polly-ignore-aliasing, if the user really wants unsafe code generation. Functions such as getNextBasePtr are usually inlined anyway (or not marked with readnone nounwind because they are defined in another translation unit).

On the other side it is a problem for the code generator if the base pointer is not available anywhere in the SCoP, when it needs to regenerate the access function (when setNewAccessRelation is called, such as in D28518, DeLICM and JSONImporter). The code generator currently assumes that base pointers are availably globally and generates invalid code (referring to the base pointer of the original code).

[Meinersbur]

• Rebase to r297195
• Update some comments
• Add context

[Meinersbur]

• Undo unnecessary change in ReportVariantBasePtr-01.ll

[grosser]

LGTM. We can add these functions later on. Let's first get it correct.

polly/trunk/lib/Analysis/ScopDetection.cpp

bool ScopDetection::isInvariant(Value &Val, const Region &Reg,
   // Loads within the SCoP may read arbitrary values, need to hoist them. If it
   // is not hoistable, it will be rejected later, but here we assume it is and
   // that makes the value invariant.
   if (auto LI = dyn_cast<LoadInst>(I)) {
     Ctx.RequiredILS.insert(LI);
     return true;
   }
 
-  if (I->mayHaveSideEffects())
-    return false;
-
-  if (isa<SelectInst>(I))
-    return false;
-
-  // When Val is a Phi node, it is likely not invariant. We do not check whether
-  // Phi nodes are actually invariant, we assume that Phi nodes are usually not
-  // invariant.
-  if (isa<PHINode>(*I))
-    return false;
-
-  for (const Use &Operand : I->operands())
-    if (!isInvariant(*Operand, Reg, Ctx))
-      return false;
-
-  return true;
 }
 
 /// Remove smax of smax(0, size) expressions from a SCEV expression and
 /// register the '...' components.
 ///
 /// Array access expressions as they are generated by gfortran contain smax(0,
 /// size) expressions that confuse the 'normal' delinearization algorithm.
 /// However, if we extract such expressions before the normal delinearization

polly/trunk/test/Isl/CodeGen/invariant_verify_function_failed.ll

-; RUN: opt %loadPolly -S -polly-codegen -polly-invariant-load-hoisting=true %s | FileCheck %s
+; RUN: opt %loadPolly -polly-detect -polly-codegen -polly-invariant-load-hoisting=true -analyze < %s | FileCheck %s
 ;
 ; This crashed at some point as the pointer returned by the call
 ; to @__errno_location is invariant and defined in the SCoP but not
 ; loaded. Therefore it is not hoisted and consequently not available
 ; at the beginning of the SCoP where we would need it if we would try
 ; to hoist %tmp. We don't try to hoist %tmp anymore but this test still
 ; checks that this passes to code generation and produces valid code.
 ;
-; CHECK: polly.start
+; This SCoP is currently rejected because %call9 is not considered a valid
+; base pointer.
+;
+; CHECK-NOT: Valid Region for Scop
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; Function Attrs: nounwind uwtable
 define void @fileblobSetFilename() #0 {
 entry:
   br i1 undef, label %if.end, label %cleanup
 

polly/trunk/test/ScopDetect/base_pointer.ll

 ; CHECK-NOT: Valid Region for Scop
 
 define void @base_pointer_is_inst_inside_invariant_1(i64 %n, float* %A) {
 entry:
   br label %for.i
 
 for.i:
   %indvar.i = phi i64 [ %indvar.i.next, %for.i.inc ], [ 0, %entry ]
-; To get an instruction inside a region, we use a function without side
-; effects on which SCEV blocks, but for which it is still clear that the
-; return value remains invariant throughout the whole loop.
+; A function return value, even with readnone nounwind attributes, is not
+; considered a valid base pointer because it can return a pointer that aliases
+; with something else (e.g. %A or a global) or return a different pointer at
+; every call (e.g. malloc)
   %ptr = call float* @getNextBasePtr(float* %A)
   br label %S1
 
 S1:
   %conv = sitofp i64 %indvar.i to float
   %arrayidx5 = getelementptr float, float* %ptr, i64 %indvar.i
   store float %conv, float* %arrayidx5, align 4
   br label %for.i.inc
 
 for.i.inc:
   %indvar.i.next = add i64 %indvar.i, 1
   %exitcond.i = icmp ne i64 %indvar.i.next, %n
   br i1 %exitcond.i, label %for.i, label %exit
 
 exit:
   ret void
 }
 
 ; CHECK-LABEL: base_pointer_is_inst_inside_invariant_1
-; CHECK: Valid Region for Scop: for.i => exit
+; CHECK-NOT: Valid Region for Scop
 
 declare float* @getNextBasePtr2(float*) readnone nounwind
 
 define void @base_pointer_is_inst_inside_invariant_2(i64 %n, float* %A) {
 entry:
   br label %for.i
 
 for.i:
for.i.inc:
   %exitcond.i = icmp ne i64 %indvar.i.next, %n
   br i1 %exitcond.i, label %for.i, label %exit
 
 exit:
   ret void
 }
 
 ; CHECK-LABEL: base_pointer_is_inst_inside_invariant_2
-; CHECK: Valid Region for Scop: for.i => exit
+; CHECK-NOT: Valid Region for Scop
 
 declare float* @getNextBasePtr3(float*, i64) readnone nounwind
 
 define void @base_pointer_is_inst_inside_variant(i64 %n, float* %A) {
 entry:
   br label %for.i
 
 for.i:

polly/trunk/test/ScopDetect/base_pointer_is_inst_inside_invariant_1___%for.i---%exit.jscop

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_ptr",
+         "sizes" : [ "*" ],
+         "type" : "float"
+      }
+   ],
+   "context" : "[n] -> {  : -9223372036854775808 <= n <= 9223372036854775807 }",
+   "name" : "%for.i---%exit",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_S1[i0] -> MemRef_ptr[i0+1] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_S1[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_S1",
+         "schedule" : "[n] -> { Stmt_S1[i0] -> [i0] }"
+      }
+   ]
+}

polly/trunk/test/ScopDetect/base_pointer_setNewAccessRelation.ll

+; RUN: opt %loadPolly -disable-basicaa -polly-detect -polly-import-jscop -polly-import-jscop-dir=%S -polly-codegen -analyze < %s | FileCheck %s
+;
+; Polly codegen used to generate invalid code (referring to %ptr from the
+; original region) when regeneration of the access function is necessary.
+; The SCoP is now rejected as a whole because %ptr is not considered a valid
+; base pointer.
+;
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
+
+declare float* @getNextBasePtr(float*) readnone nounwind
+
+define void @base_pointer_is_inst_inside_invariant_1(i64 %n, float* %A) {
+entry:
+  br label %for.i
+
+for.i:
+  %indvar.i = phi i64 [ %indvar.i.next, %for.i.inc ], [ 0, %entry ]
+  br label %S1
+
+S1:
+  %ptr = call float* @getNextBasePtr(float* %A)
+  %conv = sitofp i64 %indvar.i to float
+  %arrayidx5 = getelementptr float, float* %ptr, i64 %indvar.i
+  store float %conv, float* %arrayidx5, align 4
+  br label %for.i.inc
+
+for.i.inc:
+  %indvar.i.next = add i64 %indvar.i, 1
+  %exitcond.i = icmp ne i64 %indvar.i.next, %n
+  br i1 %exitcond.i, label %for.i, label %exit
+
+exit:
+  ret void
+}
+
+
+; CHECK-NOT: Valid Region for Scop