From ff10341183adf74760e6118a55cbd1debf50f90f Mon Sep 17 00:00:00 2001 From: Duncan Sands Date: Wed, 17 Nov 2010 04:30:22 +0000 Subject: 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 --- lib/Analysis/InstructionSimplify.cpp | 40 +++++++++++++++++++++-- lib/Analysis/Lint.cpp | 4 +-- lib/VMCore/Instructions.cpp | 63 ++++-------------------------------- 3 files changed, 46 insertions(+), 61 deletions(-) (limited to 'lib') 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(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(I)->hasConstantValue(DT); + return SimplifyPHINode(cast(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(V)) { - if (Value *W = PN->hasConstantValue(DT)) + if (Value *W = PN->hasConstantValue()) return findValueImpl(W, OffsetOk, Visited); } else if (CastInst *CI = dyn_cast(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(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(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(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(InVal)) - return InVal; - - Instruction *IV = cast(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(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; } -- cgit v1.1