[Polly][GSoC 2016]Do not process SCoPs with infeasible runtime context

[cs14mtech11017]

Summary

Do not process SCoPs with infeasible runtime context in the new ScopInfoWrapperPass.
Do not compute dependences for such SCoPs in the new DependenceInfoWrapperPass.

[jdoerfert]

lib/Analysis/DependenceInfo.cpp

835 ↗

(On Diff #64103)

When does this happen exactly? Can't we just prevent it in the ScopInfo pass?

lib/Analysis/ScopInfo.cpp

4280 ↗

(On Diff #64103)

This looks reasonable and as if it would prevent the problem solved above, doesn't it?

[cs14mtech11017]

lib/Analysis/DependenceInfo.cpp

835 ↗

(On Diff #64103)

For some SESE Regions, the SCoP does not have a feasible run time context. Hence the SCoP object becomes empty. Placed a null check in this patch in ScopInfoWrapperPass to prevent storing empty SCoPs to the hash map. I think this check is not mandatory, still it is better to have one.

lib/Analysis/ScopInfo.cpp

4280 ↗

(On Diff #64103)

Yes this solves the problem. Still, it would be advisable to have the other null check as well.

[jdoerfert]

Except the single comment LGTM.

lib/Analysis/DependenceInfo.cpp

835 ↗

(On Diff #64103)

If it is not expected to ever happen make it an assert please.

polly/trunk/lib/Analysis/DependenceInfo.cpp

const Dependences &DependenceInfoWrapperPass::recomputeDependences(
   std::unique_ptr<Dependences> D(new Dependences(S->getSharedIslCtx(), Level));
   D->calculateDependences(*S);
   auto Inserted = ScopToDepsMap.insert(std::make_pair(S, std::move(D)));
   return *Inserted.first->second;
 }
 
 bool DependenceInfoWrapperPass::runOnFunction(Function &F) {
   auto &SI = getAnalysis<ScopInfoWrapperPass>();
-  for (auto &It : SI)
+  for (auto &It : SI) {
+    assert(It.second && "Invalid SCoP object!");
     recomputeDependences(It.second.get(), Dependences::AL_Access);
+  }
   return false;
 }
 
 void DependenceInfoWrapperPass::print(raw_ostream &OS, const Module *M) const {
   for (auto &It : ScopToDepsMap) {
     assert((It.first && It.second) && "Invalid Scop or Dependence object!\n");
     It.second->print(OS);
   }

polly/trunk/lib/Analysis/ScopInfo.cpp

bool ScopInfoWrapperPass::runOnFunction(Function &F) {
   /// Create polyhedral descripton of scops for all the valid regions of a
   /// function.
   for (auto &It : SD) {
     Region *R = const_cast<Region *>(It);
     if (!SD.isMaxRegionInScop(*R))
       continue;
 
     ScopBuilder SB(R, AC, AA, DL, DT, LI, SD, SE);
+    std::unique_ptr<Scop> S = SB.getScop();
+    if (!S)
+      continue;
     bool Inserted =
-        RegionToScopMap.insert(std::make_pair(R, SB.getScop())).second;
+        RegionToScopMap.insert(std::make_pair(R, std::move(S))).second;
     assert(Inserted && "Building Scop for the same region twice!");
     (void)Inserted;
   }
   return false;
 }
 
 void ScopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
   for (auto &It : RegionToScopMap) {

polly/trunk/test/DependenceInfo/infeasible_context.ll

+; RUN: opt %loadPolly -polly-function-scops -analyze < %s \
+; RUN:  | FileCheck %s -check-prefix=FUNC-SCOP
+; RUN: opt %loadPolly -polly-function-dependences -analyze < %s \
+; RUN:  | FileCheck %s -check-prefix=FUNC-DEPS
+;
+; FUNC-SCOP-NOT: Statement
+; FUNC-DEPS-LABEL: Printing analysis 'Polly - Calculate dependences for all the SCoPs of a function' for function 'readgeo'
+; FUNC-DEPS-NOT: RAW dependences
+;
+; Due to an infeasible run-time check, scop object is empty and we do not compute dependences.
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+%struct.tnode.1.7.13.67.121.175.217.307.325.337.349.367.379.391.433.445.667.727.733.739 = type { i32, i32, %struct.tnode.1.7.13.67.121.175.217.307.325.337.349.367.379.391.433.445.667.727.733.739*, %struct.tnode.1.7.13.67.121.175.217.307.325.337.349.367.379.391.433.445.667.727.733.739*, %struct.tnode.1.7.13.67.121.175.217.307.325.337.349.367.379.391.433.445.667.727.733.739*, %struct.tnode.1.7.13.67.121.175.217.307.325.337.349.367.379.391.433.445.667.727.733.739*, %struct.tnode.1.7.13.67.121.175.217.307.325.337.349.367.379.391.433.445.667.727.733.739*, i32, i32, %struct.plist.0.6.12.66.120.174.216.306.324.336.348.366.378.390.432.444.666.726.732.738* }
+%struct.plist.0.6.12.66.120.174.216.306.324.336.348.366.378.390.432.444.666.726.732.738 = type { i32, %struct.plist.0.6.12.66.120.174.216.306.324.336.348.366.378.390.432.444.666.726.732.738* }
+
+@vFixedEdgeRoot = external global %struct.tnode.1.7.13.67.121.175.217.307.325.337.349.367.379.391.433.445.667.727.733.739*, align 8
+@hEdgeRoot = external global %struct.tnode.1.7.13.67.121.175.217.307.325.337.349.367.379.391.433.445.667.727.733.739*, align 8
+
+; Function Attrs: nounwind uwtable
+define void @readgeo() #0 {
+entry:
+  %vx = alloca i32, align 4
+  br label %if.end64
+
+if.end64:                                         ; preds = %entry
+  br label %for.body73
+
+for.body73:                                       ; preds = %for.inc216, %if.end64
+  %v.0101 = phi i32 [ 0, %for.inc216 ], [ 1, %if.end64 ]
+  br i1 undef, label %if.then93, label %if.else
+
+if.then93:                                        ; preds = %for.body73
+  br label %for.inc216
+
+if.else:                                          ; preds = %for.body73
+  br i1 undef, label %if.then111, label %if.end116
+
+if.then111:                                       ; preds = %if.else
+  br label %if.end116
+
+if.end116:                                        ; preds = %if.then111, %if.else
+  %rippleCount.2 = phi i32 [ 1, %if.then111 ], [ undef, %if.else ]
+  %rem11790 = and i32 %v.0101, 1
+  %cmp118 = icmp eq i32 %rem11790, 0
+  br i1 %cmp118, label %if.then120, label %if.else154
+
+if.then120:                                       ; preds = %if.end116
+  call void @tinsert()
+  br label %if.end193
+
+if.else154:                                       ; preds = %if.end116
+  call void @tinsert()
+  br label %if.end193
+
+if.end193:                                        ; preds = %if.else154, %if.then120
+  %0 = load i32, i32* %vx, align 4
+  br label %for.inc216
+
+for.inc216:                                       ; preds = %if.end193, %if.then93
+  %rippleCount.3 = phi i32 [ undef, %if.then93 ], [ %rippleCount.2, %if.end193 ]
+  %ux.2 = phi i32 [ undef, %if.then93 ], [ %0, %if.end193 ]
+  br i1 undef, label %for.body73, label %for.end218
+
+for.end218:                                       ; preds = %for.inc216
+  unreachable
+}
+
+declare void @tinsert()