From f4cfc29d86bc803e0f168ef73e2834db1df70f97 Mon Sep 17 00:00:00 2001
From: Michael Kruse <llvm@meinersbur.de>
Date: Mon, 22 May 2017 15:36:53 +0000
Subject: [PATCH] [CodeGen] Add invalidation of the loop SCEVs after merge
 block generation.

The SCEVs of loops surrounding the escape users of a merge blocks are
forgotten, so that loop trip counts based on old values can be revoked.

This fixes llvm.org//PR32536

Contributed-by: Baranidharan Mohan <mbdharan@gmail.com>

Differential Revision: https://reviews.llvm.org/D33195

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@303561 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/polly/CodeGen/BlockGenerators.h            |  5 +-
 lib/CodeGen/BlockGenerators.cpp                    | 12 ++++
 .../CodeGen/two-scops-in-row-invalidate-scevs.ll   | 70 ++++++++++++++++++++++
 3 files changed, 85 insertions(+), 2 deletions(-)
 create mode 100644 test/Isl/CodeGen/two-scops-in-row-invalidate-scevs.ll

diff --git a/include/polly/CodeGen/BlockGenerators.h b/include/polly/CodeGen/BlockGenerators.h
index c55b2e69..a30b7f91 100644
--- a/include/polly/CodeGen/BlockGenerators.h
+++ b/include/polly/CodeGen/BlockGenerators.h
@@ -580,8 +580,9 @@ protected:
   /// Invalidate the scalar evolution expressions for a scop.
   ///
   /// This function invalidates the scalar evolution results for all
-  /// instructions that are part of a given scop. This is necessary to ensure
-  /// that later scops do not obtain scalar evolution expressions that reference
+  /// instructions that are part of a given scop, and the loops
+  /// surrounding the users of merge blocks. This is necessary to ensure that
+  /// later scops do not obtain scalar evolution expressions that reference
   /// values that earlier dominated the later scop, but have been moved in the
   /// conditional part of an earlier scop and consequently do not any more
   /// dominate the later scop.
diff --git a/lib/CodeGen/BlockGenerators.cpp b/lib/CodeGen/BlockGenerators.cpp
index 7f1571ff..ffb34a30 100644
--- a/lib/CodeGen/BlockGenerators.cpp
+++ b/lib/CodeGen/BlockGenerators.cpp
@@ -858,6 +858,18 @@ void BlockGenerator::invalidateScalarEvolution(Scop &S) {
           SE.forgetValue(&Inst);
     else
       llvm_unreachable("Unexpected statement type found");
+
+  // Invalidate SCEV of loops surrounding the EscapeUsers.
+  for (const auto &EscapeMapping : EscapeMap) {
+    const EscapeUserVectorTy &EscapeUsers = EscapeMapping.second.second;
+    for (Instruction *EUser : EscapeUsers) {
+      if (Loop *L = LI.getLoopFor(EUser->getParent()))
+        while (L) {
+          SE.forgetLoop(L);
+          L = L->getParentLoop();
+        }
+    }
+  }
 }
 
 void BlockGenerator::finalizeSCoP(Scop &S) {
diff --git a/test/Isl/CodeGen/two-scops-in-row-invalidate-scevs.ll b/test/Isl/CodeGen/two-scops-in-row-invalidate-scevs.ll
new file mode 100644
index 00000000..238014ed
--- /dev/null
+++ b/test/Isl/CodeGen/two-scops-in-row-invalidate-scevs.ll
@@ -0,0 +1,70 @@
+; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
+;
+; CHECK-LABEL: for.cond:
+; CHECK:         %num.0 = phi i32 [ %add, %for.body15 ], [ 0, %for.cond.pre_entry_bb ]
+; CHECK:         br i1 false, label %for.body15, label %for.end22
+
+; CHECK-LABEL: polly.merge_new_and_old:
+; CHECK:         %num.0.merge = phi i32 [ %num.0.final_reload, %polly.exiting ], [ %num.0, %for.end22 ]
+; CHECK:         br label %for.end44
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @func(i32* %p) {
+entry:
+  %counters = alloca [64 x i32], align 16
+  %lenCounters = alloca [17 x i32], align 16
+  br label %for.cond
+
+for.cond:                                       ; preds = %for.body15, %for.cond
+  %num.0 = phi i32 [ 0, %entry ], [ %add, %for.body15 ]
+  br i1 false, label %for.body15, label %for.end22
+
+for.body15:                                       ; preds = %for.cond
+  %arrayidx17 = getelementptr inbounds [64 x i32], [64 x i32]* %counters, i64 0, i64 0
+  %0 = load i32, i32* %arrayidx17, align 4
+  %add = add i32 %num.0, %0
+  br label %for.cond
+
+for.end22:                                        ; preds = %for.cond
+  br label %for.end44
+
+for.end44:                                        ; preds = %for.end22
+  br i1 undef, label %if.then50, label %if.end67
+
+if.then50:                                        ; preds = %for.end44
+  br label %cleanup
+
+if.end67:                                         ; preds = %for.end44
+  br label %do.body
+
+do.body:                                          ; preds = %cond.end109, %if.end67
+  %e.0 = phi i32 [ 0, %if.end67 ], [ %inc128, %cond.end109 ]
+  br label %cond.end109
+
+cond.end109:                                      ; preds = %do.body
+  %idxprom122 = zext i32 %e.0 to i64
+  %arrayidx123 = getelementptr inbounds i32, i32* %p, i64 %idxprom122
+  %inc128 = add i32 %e.0, 1
+  %sub129 = sub i32 %num.0, %inc128
+  %cmp130 = icmp ugt i32 %sub129, 1
+  br i1 %cmp130, label %do.body, label %do.end
+
+do.end:                                           ; preds = %cond.end109
+  %1 = load i32, i32* %arrayidx123, align 4
+  %arrayidx142 = getelementptr inbounds [17 x i32], [17 x i32]* %lenCounters, i64 0, i64 1
+  store i32 2, i32* %arrayidx142, align 4
+  br label %for.cond201
+
+for.cond201:                                      ; preds = %for.body204, %do.end
+  br i1 undef, label %for.body204, label %for.end214
+
+for.body204:                                      ; preds = %for.cond201
+  br label %for.cond201
+
+for.end214:                                       ; preds = %for.cond201
+  br label %cleanup
+
+cleanup:                                          ; preds = %for.end214, %if.then50
+  ret void
+}
-- 
2.11.4.GIT