From d5c369f4600db7f05287f80edca43cc83318a310 Mon Sep 17 00:00:00 2001
From: Johannes Doerfert <doerfert@cs.uni-saarland.de>
Date: Mon, 25 Apr 2016 18:55:15 +0000
Subject: [PATCH] Do not check all GEPs for assumptions

  Before, we checked all GEPs in a statement in order to derive
  out-of-bound assumptions. However, this can not only introduce new
  parameters but it is also not clear what we can learn from GEPs that
  are not immediately used in a memory accesses inside the SCoP. As this
  case is very rare, no actual change in the behaviour is expected.

llvm-svn: 267442
---
 polly/include/polly/ScopInfo.h                     |  4 +-
 polly/lib/Analysis/ScopInfo.cpp                    | 21 +++----
 .../ScopInfo/avoid_new_parameters_from_geps.ll     | 68 ++++++++++++++++++++++
 3 files changed, 81 insertions(+), 12 deletions(-)
 create mode 100644 polly/test/ScopInfo/avoid_new_parameters_from_geps.ll

diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index e7bac93..0f440ef 100644
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -1084,8 +1084,8 @@ private:
   /// or non-optimal run-time checks.
   void deriveAssumptionsFromGEP(GetElementPtrInst *Inst, ScopDetection &SD);
 
-  /// @brief Scan @p Block and derive assumptions about parameter values.
-  void deriveAssumptions(BasicBlock *Block, ScopDetection &SD);
+  /// @brief Derive assumptions about parameter values.
+  void deriveAssumptions(ScopDetection &SD);
 
 public:
   ~ScopStmt();
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index 1891216..41f1bac 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -1443,10 +1443,17 @@ void ScopStmt::deriveAssumptionsFromGEP(GetElementPtrInst *GEP,
   isl_set_free(NotExecuted);
 }
 
-void ScopStmt::deriveAssumptions(BasicBlock *Block, ScopDetection &SD) {
-  for (Instruction &Inst : *Block)
-    if (auto *GEP = dyn_cast<GetElementPtrInst>(&Inst))
+void ScopStmt::deriveAssumptions(ScopDetection &SD) {
+  for (auto *MA : *this) {
+    if (!MA->isArrayKind())
+      continue;
+
+    MemAccInst Acc(MA->getAccessInstruction());
+    auto *GEP = dyn_cast_or_null<GetElementPtrInst>(Acc.getPointerOperand());
+
+    if (GEP)
       deriveAssumptionsFromGEP(GEP, SD);
+  }
 }
 
 void ScopStmt::collectSurroundingLoops() {
@@ -1478,13 +1485,7 @@ void ScopStmt::init(ScopDetection &SD) {
   collectSurroundingLoops();
   buildAccessRelations();
 
-  if (BB) {
-    deriveAssumptions(BB, SD);
-  } else {
-    for (BasicBlock *Block : R->blocks()) {
-      deriveAssumptions(Block, SD);
-    }
-  }
+  deriveAssumptions(SD);
 
   if (DetectReductions)
     checkForReductions();
diff --git a/polly/test/ScopInfo/avoid_new_parameters_from_geps.ll b/polly/test/ScopInfo/avoid_new_parameters_from_geps.ll
new file mode 100644
index 0000000..3f28d7a
--- /dev/null
+++ b/polly/test/ScopInfo/avoid_new_parameters_from_geps.ll
@@ -0,0 +1,68 @@
+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; Check that we do no introduce a parameter here that is actually not needed.
+;
+; CHECK:      Region: %for.body58---%land.lhs.true
+; CHECK-NEXT:     Max Loop Depth:  1
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     {  :  }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     {  :  }
+; CHECK-NEXT:     Invalid Context:
+; CHECK-NEXT:     {  : 1 = 0 }
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         i32* MemRef_team2_0_in; // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         i32* MemRef_team2_0_in; // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:     	Stmt_if_then60
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 { Stmt_if_then60[] };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 { Stmt_if_then60[] -> [] };
+; CHECK-NEXT:             MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_if_then60[] -> MemRef_team2_0_in[] };
+; CHECK-NEXT:     }
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+@sched = external global [18 x [15 x [3 x i32]]], align 16
+
+; Function Attrs: nounwind uwtable
+define void @common() #0 {
+entry:
+  br label %for.body36
+
+for.body36:                                       ; preds = %entry
+  br label %for.cond56.preheader
+
+for.cond56.preheader:                             ; preds = %for.inc158, %for.body36
+  %indvars.iv78 = phi i64 [ 0, %for.inc158 ], [ 1, %for.body36 ]
+  br label %for.body58
+
+for.body58:                                       ; preds = %for.cond56.preheader
+  %cmp59 = icmp eq i32 1, 1
+  br i1 %cmp59, label %if.then60, label %if.else71
+
+if.then60:                                        ; preds = %for.body58
+  %arrayidx70 = getelementptr inbounds [18 x [15 x [3 x i32]]], [18 x [15 x [3 x i32]]]* @sched, i64 0, i64 1, i64 %indvars.iv78, i64 1
+  br label %land.lhs.true
+
+if.else71:                                        ; preds = %for.body58
+  br label %land.lhs.true
+
+land.lhs.true:                                    ; preds = %if.else71, %if.then60
+  %team2.0.in = phi i32* [ %arrayidx70, %if.then60 ], [ undef, %if.else71 ]
+  br i1 undef, label %for.inc158, label %if.then86
+
+if.then86:                                        ; preds = %land.lhs.true
+  unreachable
+
+for.inc158:                                       ; preds = %land.lhs.true
+  br label %for.cond56.preheader
+}
-- 
2.7.4