From e408935bb5339e20035d84307c666fbdd15e99e0 Mon Sep 17 00:00:00 2001
From: Michael Kruse <llvm-project@meinersbur.de>
Date: Tue, 10 Nov 2020 02:37:35 -0600
Subject: [PATCH] [Polly][ScopBuilder] Use only modeled instructions to compute
 statement granularity.

ScopBuilder distributes independent instructions between statements.
Only modeled (e.g. not synthesizable) instructions are represented.
To compute independence, non-modeled instructions were used in some
parts of determining instruction independence, which could lead to the
re-introduction of non-model instructions.

In particular, required invariant loads could be added to instruction
list, which then led to redundant MemoryAccesses for such a load.

This fixes llvm.org/PR48059.
---
 polly/lib/Analysis/ScopBuilder.cpp             | 14 +++++------
 polly/test/ScopInfo/invariant-load-instlist.ll | 32 ++++++++++++++++++++++++++
 2 files changed, 39 insertions(+), 7 deletions(-)
 create mode 100644 polly/test/ScopInfo/invariant-load-instlist.ll

diff --git a/polly/lib/Analysis/ScopBuilder.cpp b/polly/lib/Analysis/ScopBuilder.cpp
index 1215a9d..927a0b2 100644
--- a/polly/lib/Analysis/ScopBuilder.cpp
+++ b/polly/lib/Analysis/ScopBuilder.cpp
@@ -2132,11 +2132,11 @@ void ScopBuilder::buildEqivClassBlockStmts(BasicBlock *BB) {
   // The order of statements must be preserved w.r.t. their ordered
   // instructions. Without this explicit scan, we would also use non-ordered
   // instructions (whose order is arbitrary) to determine statement order.
-  for (Instruction &Inst : *BB) {
-    if (!isOrderedInstruction(&Inst))
+  for (Instruction *Inst : ModeledInsts) {
+    if (!isOrderedInstruction(Inst))
       continue;
 
-    auto LeaderIt = UnionFind.findLeader(&Inst);
+    auto LeaderIt = UnionFind.findLeader(Inst);
     if (LeaderIt == UnionFind.member_end())
       continue;
 
@@ -2146,15 +2146,15 @@ void ScopBuilder::buildEqivClassBlockStmts(BasicBlock *BB) {
 
   // Collect the instructions of all leaders. UnionFind's member iterator
   // unfortunately are not in any specific order.
-  for (Instruction &Inst : *BB) {
-    auto LeaderIt = UnionFind.findLeader(&Inst);
+  for (Instruction *Inst : ModeledInsts) {
+    auto LeaderIt = UnionFind.findLeader(Inst);
     if (LeaderIt == UnionFind.member_end())
       continue;
 
-    if (&Inst == MainInst)
+    if (Inst == MainInst)
       MainLeader = *LeaderIt;
     std::vector<Instruction *> &InstList = LeaderToInstList[*LeaderIt];
-    InstList.push_back(&Inst);
+    InstList.push_back(Inst);
   }
 
   // Finally build the statements.
diff --git a/polly/test/ScopInfo/invariant-load-instlist.ll b/polly/test/ScopInfo/invariant-load-instlist.ll
new file mode 100644
index 0000000..7348667
--- /dev/null
+++ b/polly/test/ScopInfo/invariant-load-instlist.ll
@@ -0,0 +1,32 @@
+; RUN: opt %loadPolly -polly-scops -analyze < %s
+
+; The load is a required invariant load and at the same time used in a store.
+; Polly used to add two MemoryAccesses for it which caused an assertion to fail.
+; llvm.org/PR48059
+
+target datalayout = "e-m:w-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-windows-msvc19.27.29112"
+
+@b = external dso_local global i32, align 4
+@c = external dso_local global i32*, align 8
+@a = external dso_local local_unnamed_addr global i32**, align 8
+
+define void @func() {
+for.cond1.preheader.preheader:
+  br label %for.end12
+
+for.end12:
+  br i1 undef, label %for.end12.1, label %for.end12
+
+for.end12.1:
+  %0 = phi i32* [ %1, %for.end12.1 ], [ undef, %for.end12 ]
+  %storemerge26.1 = phi i32 [ %inc14.1, %for.end12.1 ], [ 0, %for.end12 ]
+  %1 = load i32*, i32** @c, align 8
+  store i32 0, i32* %1, align 4
+  %inc14.1 = add nuw nsw i32 %storemerge26.1, 1
+  %exitcond.1.not = icmp eq i32 %inc14.1, 35
+  br i1 %exitcond.1.not, label %for.inc16.1, label %for.end12.1
+
+for.inc16.1:
+  ret void
+}
-- 
2.7.4