Fix a layering violation: hasConstantValue, which is part of the PHINode

class, uses DominatorTree which is an analysis.  This change moves all of
the tricky hasConstantValue logic to SimplifyInstruction, and replaces it
with a very simple literal implementation.  I already taught users of
hasConstantValue that need tricky stuff to use SimplifyInstruction instead.
I didn't update InlineFunction because the IR looks like it might be in a
funky state at the point it calls hasConstantValue, which makes calling
SimplifyInstruction dangerous since it can in theory do a lot of tricky
reasoning.  This may be a pessimization, for example in the case where
all phi node operands are either undef or a fixed constant.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119459 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 46 insertions, 61 deletions

diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp
index cf1548e..c540d6f 100644
--- a/lib/Analysis/InstructionSimplify.cpp
+++ b/lib/Analysis/InstructionSimplify.cpp
@@ -173,7 +173,7 @@ static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS,
   Value *CommonValue = 0;
   for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
     Value *Incoming = PI->getIncomingValue(i);
-    // If the incoming value is the phi node itself, it can be safely skipped.
+    // If the incoming value is the phi node itself, it can safely be skipped.
     if (Incoming == PI) continue;
     Value *V = PI == LHS ?
       SimplifyBinOp(Opcode, Incoming, RHS, TD, DT, MaxRecurse) :
@@ -211,7 +211,7 @@ static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
   Value *CommonValue = 0;
   for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
     Value *Incoming = PI->getIncomingValue(i);
-    // If the incoming value is the phi node itself, it can be safely skipped.
+    // If the incoming value is the phi node itself, it can safely be skipped.
     if (Incoming == PI) continue;
     Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, DT, MaxRecurse);
     // If the operation failed to simplify, or simplified to a different value
@@ -663,6 +663,40 @@ Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps,
                                         (Constant *const*)Ops+1, NumOps-1);
 }
 
+/// SimplifyPHINode - See if we can fold the given phi.  If not, returns null.
+static Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) {
+  // If all of the PHI's incoming values are the same then replace the PHI node
+  // with the common value.
+  Value *CommonValue = 0;
+  bool HasUndefInput = false;
+  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
+    Value *Incoming = PN->getIncomingValue(i);
+    // If the incoming value is the phi node itself, it can safely be skipped.
+    if (Incoming == PN) continue;
+    if (isa<UndefValue>(Incoming)) {
+      // Remember that we saw an undef value, but otherwise ignore them.
+      HasUndefInput = true;
+      continue;
+    }
+    if (CommonValue && Incoming != CommonValue)
+      return 0;  // Not the same, bail out.
+    CommonValue = Incoming;
+  }
+
+  // If CommonValue is null then all of the incoming values were either undef or
+  // equal to the phi node itself.
+  if (!CommonValue)
+    return UndefValue::get(PN->getType());
+
+  // If we have a PHI node like phi(X, undef, X), where X is defined by some
+  // instruction, we cannot return X as the result of the PHI node unless it
+  // dominates the PHI block.
+  if (HasUndefInput)
+    return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0;
+
+  return CommonValue;
+}
+
 
 //=== Helper functions for higher up the class hierarchy.
 
@@ -748,7 +782,7 @@ Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD,
     return SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT);
   }
   case Instruction::PHI:
-    return cast<PHINode>(I)->hasConstantValue(DT);
+    return SimplifyPHINode(cast<PHINode>(I), DT);
   }
 }
 
diff --git a/lib/Analysis/Lint.cpp b/lib/Analysis/Lint.cpp
index 4318a30..8b76b87 100644
--- a/lib/Analysis/Lint.cpp
+++ b/lib/Analysis/Lint.cpp
@@ -582,7 +582,7 @@ Value *Lint::findValueImpl(Value *V, bool OffsetOk,
       BBI = BB->end();
     }
   } else if (PHINode *PN = dyn_cast<PHINode>(V)) {
-    if (Value *W = PN->hasConstantValue(DT))
+    if (Value *W = PN->hasConstantValue())
       return findValueImpl(W, OffsetOk, Visited);
   } else if (CastInst *CI = dyn_cast<CastInst>(V)) {
     if (CI->isNoopCast(TD ? TD->getIntPtrType(V->getContext()) :
@@ -615,7 +615,7 @@ Value *Lint::findValueImpl(Value *V, bool OffsetOk,
 
   // As a last resort, try SimplifyInstruction or constant folding.
   if (Instruction *Inst = dyn_cast<Instruction>(V)) {
-    if (Value *W = SimplifyInstruction(Inst, TD))
+    if (Value *W = SimplifyInstruction(Inst, TD, DT))
       if (W != Inst)
         return findValueImpl(W, OffsetOk, Visited);
   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
diff --git a/lib/VMCore/Instructions.cpp b/lib/VMCore/Instructions.cpp
index 7306d86..9fc9ef0 100644
--- a/lib/VMCore/Instructions.cpp
+++ b/lib/VMCore/Instructions.cpp
@@ -19,7 +19,6 @@
 #include "llvm/Instructions.h"
 #include "llvm/Module.h"
 #include "llvm/Operator.h"
-#include "llvm/Analysis/Dominators.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/CallSite.h"
 #include "llvm/Support/ConstantRange.h"
@@ -164,61 +163,13 @@ void PHINode::resizeOperands(unsigned NumOps) {
 
 /// hasConstantValue - If the specified PHI node always merges together the same
 /// value, return the value, otherwise return null.
-///
-/// If the PHI has undef operands, but all the rest of the operands are
-/// some unique value, return that value if it can be proved that the
-/// value dominates the PHI. If DT is null, use a conservative check,
-/// otherwise use DT to test for dominance.
-///
-Value *PHINode::hasConstantValue(const DominatorTree *DT) const {
-  // If the PHI node only has one incoming value, eliminate the PHI node.
-  if (getNumIncomingValues() == 1) {
-    if (getIncomingValue(0) != this)   // not  X = phi X
-      return getIncomingValue(0);
-    return UndefValue::get(getType());  // Self cycle is dead.
-  }
-      
-  // Otherwise if all of the incoming values are the same for the PHI, replace
-  // the PHI node with the incoming value.
-  //
-  Value *InVal = 0;
-  bool HasUndefInput = false;
-  for (unsigned i = 0, e = getNumIncomingValues(); i != e; ++i)
-    if (isa<UndefValue>(getIncomingValue(i))) {
-      HasUndefInput = true;
-    } else if (getIncomingValue(i) != this) { // Not the PHI node itself...
-      if (InVal && getIncomingValue(i) != InVal)
-        return 0;  // Not the same, bail out.
-      InVal = getIncomingValue(i);
-    }
-  
-  // The only case that could cause InVal to be null is if we have a PHI node
-  // that only has entries for itself.  In this case, there is no entry into the
-  // loop, so kill the PHI.
-  //
-  if (InVal == 0) InVal = UndefValue::get(getType());
-  
-  // If we have a PHI node like phi(X, undef, X), where X is defined by some
-  // instruction, we cannot always return X as the result of the PHI node.  Only
-  // do this if X is not an instruction (thus it must dominate the PHI block),
-  // or if the client is prepared to deal with this possibility.
-  if (!HasUndefInput || !isa<Instruction>(InVal))
-    return InVal;
-  
-  Instruction *IV = cast<Instruction>(InVal);
-  if (DT) {
-    // We have a DominatorTree. Do a precise test.
-    if (!DT->dominates(IV, this))
-      return 0;
-  } else {
-    // If it is in the entry block, it obviously dominates everything.
-    if (IV->getParent() != &IV->getParent()->getParent()->getEntryBlock() ||
-        isa<InvokeInst>(IV))
-      return 0;   // Cannot guarantee that InVal dominates this PHINode.
-  }
-
-  // All of the incoming values are the same, return the value now.
-  return InVal;
+Value *PHINode::hasConstantValue() const {
+  // Exploit the fact that phi nodes always have at least one entry.
+  Value *ConstantValue = getIncomingValue(0);
+  for (unsigned i = 1, e = getNumIncomingValues(); i != e; ++i)
+    if (getIncomingValue(i) != ConstantValue)
+      return 0; // Incoming values not all the same.
+  return ConstantValue;
 }