[polly] [ScopInfo] Fix crash with sum of invariant load and AddRec.

[efriedma]

Summary

r303971 added an assertion that SCEV addition involving an AddRec
and a SCEVUnknown must involve a dominance relation: either the
SCEVUnknown value dominates the AddRec's loop, or the AddRec's
loop header dominates the SCEVUnknown. This is generally fine
for most usage of SCEV because it isn't possible to write an
expression in IR which would violate it, but it's a bit inconvenient
here for polly.

To solve the issue, just avoid creating a SCEV expression which
triggers the asssertion.

I'm not really happy with this solution, but I don't have any better
ideas.

Fixes https://bugs.llvm.org//show_bug.cgi?id=33464.

[grosser]

Yes, this is not an amazing solution, but should work.

polly/trunk/lib/Analysis/ScopInfo.cpp

 /// Scop class implement
 
 void Scop::setContext(__isl_take isl_set *NewContext) {
   NewContext = isl_set_align_params(NewContext, isl_set_get_space(Context));
   isl_set_free(Context);
   Context = NewContext;
 }
 
+namespace {
 /// Remap parameter values but keep AddRecs valid wrt. invariant loads.
 struct SCEVSensitiveParameterRewriter
     : public SCEVRewriteVisitor<SCEVSensitiveParameterRewriter> {
   ValueToValueMap &VMap;
 
 public:
   SCEVSensitiveParameterRewriter(ValueToValueMap &VMap, ScalarEvolution &SE)
       : SCEVRewriteVisitor(SE), VMap(VMap) {}
public:
 
   const SCEV *visitUnknown(const SCEVUnknown *E) {
     if (auto *NewValue = VMap.lookup(E->getValue()))
       return SE.getUnknown(NewValue);
     return E;
   }
 };
 
-const SCEV *Scop::getRepresentingInvariantLoadSCEV(const SCEV *S) {
-  return SCEVSensitiveParameterRewriter::rewrite(S, *SE, InvEquivClassVMap);
+/// Check whether we should remap a SCEV expression.
+struct SCEVFindInsideScop : public SCEVTraversal<SCEVFindInsideScop> {
+  ValueToValueMap &VMap;
+  bool FoundInside = false;
+  Scop *S;
+
+public:
+  SCEVFindInsideScop(ValueToValueMap &VMap, ScalarEvolution &SE, Scop *S)
+      : SCEVTraversal(*this), VMap(VMap), S(S) {}
+
+  static bool hasVariant(const SCEV *E, ScalarEvolution &SE,
+                         ValueToValueMap &VMap, Scop *S) {
+    SCEVFindInsideScop SFIS(VMap, SE, S);
+    SFIS.visitAll(E);
+    return SFIS.FoundInside;
+  }
+
+  bool follow(const SCEV *E) {
+    if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(E)) {
+      FoundInside |= S->getRegion().contains(AddRec->getLoop());
+    } else if (auto *Unknown = dyn_cast<SCEVUnknown>(E)) {
+      if (Instruction *I = dyn_cast<Instruction>(Unknown->getValue()))
+        FoundInside |= S->getRegion().contains(I) && !VMap.count(I);
+    }
+    return !FoundInside;
+  }
+  bool isDone() { return FoundInside; }
+};
+} // namespace
+
+const SCEV *Scop::getRepresentingInvariantLoadSCEV(const SCEV *E) {
+  // Check whether it makes sense to rewrite the SCEV.  (ScalarEvolution
+  // doesn't like addition between an AddRec and an expression that
+  // doesn't have a dominance relationship with it.)
+  if (SCEVFindInsideScop::hasVariant(E, *SE, InvEquivClassVMap, this))
+    return E;
+
+  // Rewrite SCEV.
+  return SCEVSensitiveParameterRewriter::rewrite(E, *SE, InvEquivClassVMap);
 }
 
 // This table of function names is used to translate parameter names in more
 // human-readable names. This makes it easier to interpret Polly analysis
 // results.
 StringMap<std::string> KnownNames = {
     {"_Z13get_global_idj", "global_id"},
     {"_Z12get_local_idj", "local_id"},

polly/trunk/test/ScopInfo/invariant_load_addrec_sum.ll

+; RUN: opt %loadPolly -polly-scops -polly-invariant-load-hoisting=true -polly-ignore-aliasing -polly-process-unprofitable -analyze < %s | FileCheck %s
+;
+; CHECK: Region: %entry.split---%if.end
+; CHECK:     Invariant Accesses: {
+; CHECK:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                 [y, p_1_loaded_from_j] -> { Stmt_for_body[i0] -> MemRef_j[0] };
+; CHECK:             Execution Context: [y, p_1_loaded_from_j] -> {  :  }
+; CHECK:     }
+
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                [y, p_1_loaded_from_j] -> { Stmt_for_body5[i0] -> MemRef_p[p_1_loaded_from_j + i0] };
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                [y, p_1_loaded_from_j] -> { Stmt_for_body[i0] -> MemRef_p[p_1_loaded_from_j + i0] };
+
+
+define void @a(i32 %y, i32* nocapture %p, i32* nocapture readonly %j) local_unnamed_addr #0 {
+entry:
+  br label %entry.split
+
+entry.split:
+  %tobool = icmp eq i32 %y, 0
+  br i1 %tobool, label %for.body5, label %for.body
+
+for.body:
+  %i.024 = phi i32 [ %inc, %for.body ], [ 0, %entry.split ]
+  %0 = load i32, i32* %j, align 4
+  %add = add nsw i32 %0, %i.024
+  %idxprom = sext i32 %add to i64
+  %arrayidx = getelementptr inbounds i32, i32* %p, i64 %idxprom
+  store i32 %i.024, i32* %arrayidx, align 4
+  %inc = add nuw nsw i32 %i.024, 1
+  %exitcond26 = icmp eq i32 %inc, 10000
+  br i1 %exitcond26, label %if.end, label %for.body
+
+for.body5:
+  %i1.023 = phi i32 [ %inc10, %for.body5 ], [ 0, %entry.split ]
+  %mul = shl nsw i32 %i1.023, 1
+  %1 = load i32, i32* %j, align 4
+  %add6 = add nsw i32 %1, %i1.023
+  %idxprom7 = sext i32 %add6 to i64
+  %arrayidx8 = getelementptr inbounds i32, i32* %p, i64 %idxprom7
+  store i32 %mul, i32* %arrayidx8, align 4
+  %inc10 = add nuw nsw i32 %i1.023, 1
+  %exitcond = icmp eq i32 %inc10, 10000
+  br i1 %exitcond, label %if.end, label %for.body5
+
+if.end:
+  ret void
+}
+