aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Analysis/InstructionSimplify.cpp40
-rw-r--r--lib/Analysis/Lint.cpp4
-rw-r--r--lib/VMCore/Instructions.cpp63
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;
}