teach ComputeNumSignBits to look through PHI nodes.

llvm-svn: 92964

3 files changed, 37 insertions, 7 deletions

diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
index 9a106248126..91e5bc3876b 100644
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -726,8 +726,7 @@ unsigned llvm::ComputeNumSignBits(Value *V, const TargetData *TD,
       
     Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1);
     if (Tmp2 == 1) return 1;
-      return std::min(Tmp, Tmp2)-1;
-    break;
+    return std::min(Tmp, Tmp2)-1;
     
   case Instruction::Sub:
     Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1);
@@ -757,8 +756,24 @@ unsigned llvm::ComputeNumSignBits(Value *V, const TargetData *TD,
     // is, at worst, one more bit than the inputs.
     Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1);
     if (Tmp == 1) return 1;  // Early out.
-      return std::min(Tmp, Tmp2)-1;
-    break;
+    return std::min(Tmp, Tmp2)-1;
+      
+  case Instruction::PHI: {
+    PHINode *PN = cast<PHINode>(U);
+    // Don't analyze large in-degree PHIs.
+    if (PN->getNumIncomingValues() > 4) break;
+    
+    // Take the minimum of all incoming values.  This can't infinitely loop
+    // because of our depth threshold.
+    Tmp = ComputeNumSignBits(PN->getIncomingValue(0), TD, Depth+1);
+    for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) {
+      if (Tmp == 1) return Tmp;
+      Tmp = std::min(Tmp,
+                     ComputeNumSignBits(PN->getIncomingValue(1), TD, Depth+1));
+    }
+    return Tmp;
+  }
+
   case Instruction::Trunc:
     // FIXME: it's tricky to do anything useful for this, but it is an important
     // case for targets like X86.
diff --git a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
index 60231857222..93b196126b2 100644
--- a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
@@ -1027,8 +1027,6 @@ static bool AddReachableCodeToWorklist(BasicBlock *BB,
           continue;
         }
       
-      
-      
       if (TD) {
         // See if we can constant fold its operands.
         for (User::op_iterator i = Inst->op_begin(), e = Inst->op_end();
@@ -1047,7 +1045,6 @@ static bool AddReachableCodeToWorklist(BasicBlock *BB,
           }
         }
       }
-      
 
       InstrsForInstCombineWorklist.push_back(Inst);
     }
diff --git a/llvm/test/Transforms/InstCombine/shift-sra.ll b/llvm/test/Transforms/InstCombine/shift-sra.ll
index c209328a800..492c16ac587 100644
--- a/llvm/test/Transforms/InstCombine/shift-sra.ll
+++ b/llvm/test/Transforms/InstCombine/shift-sra.ll
@@ -19,3 +19,21 @@ define i32 @test2(i8 %tmp) {
 ; CHECK: @test2
 ; CHECK: lshr i32 %tmp4, 3
 }
+
+define i64 @test3(i1 %X, i64 %Y, i1 %Cond) {
+  br i1 %Cond, label %T, label %F
+T:
+  %X2 = sext i1 %X to i64
+  br label %C
+F:
+  %Y2 = ashr i64 %Y, 63
+  br label %C
+C:
+  %P = phi i64 [%X2, %T], [%Y2, %F] 
+  %S = ashr i64 %P, 12
+  ret i64 %S
+  
+; CHECK: @test3
+; CHECK: %P = phi i64
+; CHECK-NEXT: ret i64 %P
+}