From a1b821fac967dedd4b39d2dc8ce58e54a6cecacd Mon Sep 17 00:00:00 2001
From: David Majnemer <david.majnemer@gmail.com>
Date: Sun, 12 Jul 2015 03:53:05 +0000
Subject: [PATCH] [LICM] Don't try to sink values out of loops without any
 exits

There is no suitable basic block to sink instructions in loops without
exits.  The only way an instruction in a loop without exits can be used
is as an incoming value to a PHI.  In such cases, the incoming block for
the corresponding value is unreachable.

This fixes PR24013.

Differential Revision: http://reviews.llvm.org/D10903

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@241987 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Scalar/LICM.cpp  | 13 ++++++++++++-
 test/Transforms/LICM/PR24013.ll | 19 +++++++++++++++++++
 2 files changed, 31 insertions(+), 1 deletion(-)
 create mode 100644 test/Transforms/LICM/PR24013.ll

diff --git a/lib/Transforms/Scalar/LICM.cpp b/lib/Transforms/Scalar/LICM.cpp
index f0e6d641b18..43fc50e588f 100644
--- a/lib/Transforms/Scalar/LICM.cpp
+++ b/lib/Transforms/Scalar/LICM.cpp
@@ -602,7 +602,8 @@ static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
   // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
   // the instruction.
   while (!I.use_empty()) {
-    Instruction *User = I.user_back();
+    Value::user_iterator UI = I.user_begin();
+    auto *User = cast<Instruction>(*UI);
     if (!DT->isReachableFromEntry(User->getParent())) {
       User->replaceUsesOfWith(&I, UndefValue::get(I.getType()));
       continue;
@@ -610,6 +611,16 @@ static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
     // The user must be a PHI node.
     PHINode *PN = cast<PHINode>(User);
 
+    // Surprisingly, instructions can be used outside of loops without any
+    // exits.  This can only happen in PHI nodes if the incoming block is
+    // unreachable.
+    Use &U = UI.getUse();
+    BasicBlock *BB = PN->getIncomingBlock(U);
+    if (!DT->isReachableFromEntry(BB)) {
+      U = UndefValue::get(I.getType());
+      continue;
+    }
+
     BasicBlock *ExitBlock = PN->getParent();
     assert(ExitBlockSet.count(ExitBlock) &&
            "The LCSSA PHI is not in an exit block!");
diff --git a/test/Transforms/LICM/PR24013.ll b/test/Transforms/LICM/PR24013.ll
new file mode 100644
index 00000000000..4557bfcfd12
--- /dev/null
+++ b/test/Transforms/LICM/PR24013.ll
@@ -0,0 +1,19 @@
+; RUN: opt -licm -S < %s | FileCheck %s
+
+define void @f(i1 zeroext %p1) {
+; CHECK-LABEL: @f(
+entry:
+  br label %lbl
+
+lbl.loopexit:                                     ; No predecessors!
+  br label %lbl
+
+lbl:                                              ; preds = %lbl.loopexit, %entry
+  %phi = phi i32 [ %conv, %lbl.loopexit ], [ undef, %entry ]
+; CHECK: phi i32 [ undef, {{.*}} ], [ undef
+  br label %if.then.5
+
+if.then.5:                                        ; preds = %if.then.5, %lbl
+  %conv = zext i1 undef to i32
+  br label %if.then.5
+}
-- 
2.34.1