From 08368ce9847309618a2c80222cba3b2c88f77f88 Mon Sep 17 00:00:00 2001
From: Nick Lewycky <nicholas@mxc.ca>
Date: Wed, 19 Aug 2009 07:16:57 +0000
Subject: [PATCH] Fix up PHI nodes correctly in the presence of unreachable
 BBs, part two. Also delete a newed pointer, and improve readability a little
 bit.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@79411 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Utils/SSI.cpp                  | 37 +++++++++++++++----
 .../SSI/2009-08-19-UnreachableBB2.ll          | 22 +++++++++++
 2 files changed, 52 insertions(+), 7 deletions(-)
 create mode 100644 test/Transforms/SSI/2009-08-19-UnreachableBB2.ll

diff --git a/lib/Transforms/Utils/SSI.cpp b/lib/Transforms/Utils/SSI.cpp
index b4e683417cc..036dc362273 100644
--- a/lib/Transforms/Utils/SSI.cpp
+++ b/lib/Transforms/Utils/SSI.cpp
@@ -226,10 +226,9 @@ void SSI::rename(BasicBlock *BB) {
     for (BasicBlock::iterator begin = BB_succ->begin(),
          notPhi = BB_succ->getFirstNonPHI(); begin != *notPhi; ++begin) {
       Instruction *I = begin;
-      PHINode *PN;
+      PHINode *PN = dyn_cast<PHINode>(I);
       int position;
-      if ((PN = dyn_cast<PHINode>(I)) && ((position
-          = getPositionPhi(PN)) != -1)) {
+      if (PN && ((position = getPositionPhi(PN)) != -1)) {
         PN->addIncoming(value_stack[position].back(), BB);
       }
     }
@@ -254,6 +253,8 @@ void SSI::rename(BasicBlock *BB) {
       }
     }
   }
+
+  delete defined;
 }
 
 /// Substitute any use in this instruction for the last definition of
@@ -307,16 +308,16 @@ bool SSI::dominateAny(BasicBlock *BB, Instruction *value) {
 /// as an operand of another phi function used in the same BasicBlock,
 /// LLVM looks this as an error. So on the second phi, the first phi is called
 /// P and the BasicBlock it incomes is B. This P will be replaced by the value
-/// it has for BasicBlock B.
+/// it has for BasicBlock B. It also includes undef values for predecessors
+/// that were not included in the phi.
 ///
 void SSI::fixPhis() {
   for (SmallPtrSet<PHINode *, 1>::iterator begin = phisToFix.begin(),
        end = phisToFix.end(); begin != end; ++begin) {
     PHINode *PN = *begin;
     for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
-      PHINode *PN_father;
-      if ((PN_father = dyn_cast<PHINode>(PN->getIncomingValue(i))) &&
-          PN->getParent() == PN_father->getParent() &&
+      PHINode *PN_father = dyn_cast<PHINode>(PN->getIncomingValue(i));
+      if (PN_father && PN->getParent() == PN_father->getParent() &&
           !DT_->dominates(PN->getParent(), PN->getIncomingBlock(i))) {
         BasicBlock *BB = PN->getIncomingBlock(i);
         int pos = PN_father->getBasicBlockIndex(BB);
@@ -324,6 +325,28 @@ void SSI::fixPhis() {
       }
     }
   }
+
+  for (DenseMapIterator<PHINode *, unsigned> begin = phis.begin(),
+       end = phis.end(); begin != end; ++begin) {
+    PHINode *PN = begin->first;
+    BasicBlock *BB = PN->getParent();
+    pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
+    SmallVector<BasicBlock*, 8> Preds(PI, PE);
+    for (unsigned size = Preds.size();
+         PI != PE && PN->getNumIncomingValues() != size; ++PI) {
+      bool found = false;
+      for (unsigned i = 0, pn_end = PN->getNumIncomingValues();
+           i < pn_end; ++i) {
+        if (PN->getIncomingBlock(i) == *PI) {
+          found = true;
+          break;
+        }
+      }
+      if (!found) {
+        PN->addIncoming(UndefValue::get(PN->getType()), *PI);
+      }
+    }
+  }
 }
 
 /// Return which variable (position on the vector of variables) this phi
diff --git a/test/Transforms/SSI/2009-08-19-UnreachableBB2.ll b/test/Transforms/SSI/2009-08-19-UnreachableBB2.ll
new file mode 100644
index 00000000000..480c7033bc4
--- /dev/null
+++ b/test/Transforms/SSI/2009-08-19-UnreachableBB2.ll
@@ -0,0 +1,22 @@
+; RUN: llvm-as < %s | opt -ssi-everything -disable-output
+
+define void @foo() {
+entry:
+	%tmp0 = load i64* undef, align 4		; <i64> [#uses=3]
+	br i1 undef, label %end_stmt_playback, label %bb16
+
+readJournalHdr.exit:		; No predecessors!
+	br label %end_stmt_playback
+
+bb16:		; preds = %bb7
+	%tmp1 = icmp slt i64 0, %tmp0		; <i1> [#uses=1]
+	br i1 %tmp1, label %bb16, label %bb17
+
+bb17:		; preds = %bb16
+	store i64 %tmp0, i64* undef, align 4
+	br label %end_stmt_playback
+
+end_stmt_playback:		; preds = %bb17, %readJournalHdr.exit, %bb6, %bb2
+	store i64 %tmp0, i64* undef, align 4
+	ret void
+}
-- 
2.34.1