From cbac7f163099fda6f3c036920404e4b87ab33d2a Mon Sep 17 00:00:00 2001
From: Dan Gohman <gohman@apple.com>
Date: Tue, 9 Mar 2010 01:53:33 +0000
Subject: [PATCH] Make isLCSSA ignore uses in blocks not reachable from the
 entry block, as LCSSA no longer transforms such uses.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@98033 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/LoopInfo.cpp                | 17 ++++++++++++---
 test/Transforms/LCSSA/unreachable-use.ll | 27 ++++++++++++++++++++++++
 2 files changed, 41 insertions(+), 3 deletions(-)
 create mode 100644 test/Transforms/LCSSA/unreachable-use.ll

diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp
index 453af5a5555..2139c29cc1f 100644
--- a/lib/Analysis/LoopInfo.cpp
+++ b/lib/Analysis/LoopInfo.cpp
@@ -264,6 +264,13 @@ unsigned Loop::getSmallConstantTripMultiple() const {
 
 /// isLCSSAForm - Return true if the Loop is in LCSSA form
 bool Loop::isLCSSAForm() const {
+  // Collect all the reachable blocks in the function, for fast lookups.
+  SmallPtrSet<BasicBlock *, 32> ReachableBBs;
+  BasicBlock *EntryBB = getHeader()->getParent()->begin();
+  for (df_iterator<BasicBlock *> NI = df_begin(EntryBB),
+       NE = df_end(EntryBB); NI != NE; ++NI)
+    ReachableBBs.insert(*NI);
+
   // Sort the blocks vector so that we can use binary search to do quick
   // lookups.
   SmallPtrSet<BasicBlock *, 16> LoopBBs(block_begin(), block_end());
@@ -277,9 +284,13 @@ bool Loop::isLCSSAForm() const {
         if (PHINode *P = dyn_cast<PHINode>(*UI))
           UserBB = P->getIncomingBlock(UI);
 
-        // Check the current block, as a fast-path.  Most values are used in
-        // the same block they are defined in.
-        if (UserBB != BB && !LoopBBs.count(UserBB))
+        // Check the current block, as a fast-path, before checking whether
+        // the use is anywhere in the loop.  Most values are used in the same
+        // block they are defined in.  Also, blocks not reachable from the
+        // entry are special; uses in them don't need to go through PHIs.
+        if (UserBB != BB &&
+            !LoopBBs.count(UserBB) &&
+            ReachableBBs.count(UserBB))
           return false;
       }
   }
diff --git a/test/Transforms/LCSSA/unreachable-use.ll b/test/Transforms/LCSSA/unreachable-use.ll
new file mode 100644
index 00000000000..c389c9cfa87
--- /dev/null
+++ b/test/Transforms/LCSSA/unreachable-use.ll
@@ -0,0 +1,27 @@
+; RUN: opt < %s -lcssa -S -verify-loop-info | grep {\[%\]tmp33 = load i1\\*\\* \[%\]tmp}
+; PR6546
+
+; LCSSA doesn't need to transform uses in blocks not reachable
+; from the entry block.
+
+define fastcc void @dfs() nounwind {
+bb:
+  br label %bb44
+
+bb44:
+  br i1 undef, label %bb7, label %bb45
+
+bb7:
+  %tmp = bitcast i1** undef to i1**
+  br label %bb15
+
+bb15:
+  br label %bb44
+
+bb32:
+  %tmp33 = load i1** %tmp, align 8
+  br label %bb45
+
+bb45:
+  unreachable
+}
-- 
2.34.1