X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FInstructionSimplify.cpp;h=b49b4d0c6aba31152f82f0beecd7655b57b3c82d;hb=61e3b91da711659c3cca5c4c6026a4b2aea322b4;hp=6953f16dc929a1b470a6da5d40d18268332d5878;hpb=e34537856a544c83513e390ac9552a8bc3823346;p=oota-llvm.git diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp index 6953f16dc92..b49b4d0c6ab 100644 --- a/lib/Analysis/InstructionSimplify.cpp +++ b/lib/Analysis/InstructionSimplify.cpp @@ -15,15 +15,44 @@ #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Support/ValueHandle.h" #include "llvm/Instructions.h" #include "llvm/Support/PatternMatch.h" using namespace llvm; using namespace llvm::PatternMatch; -/// SimplifyAndInst - Given operands for an And, see if we can +/// SimplifyAddInst - Given operands for an Add, see if we can /// fold the result. If not, this returns null. -Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, +Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, const TargetData *TD) { + if (Constant *CLHS = dyn_cast(Op0)) { + if (Constant *CRHS = dyn_cast(Op1)) { + Constant *Ops[] = { CLHS, CRHS }; + return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), + Ops, 2, TD); + } + + // Canonicalize the constant to the RHS. + std::swap(Op0, Op1); + } + + if (Constant *Op1C = dyn_cast(Op1)) { + // X + undef -> undef + if (isa(Op1C)) + return Op1C; + + // X + 0 --> X + if (Op1C->isNullValue()) + return Op0; + } + + // FIXME: Could pull several more out of instcombine. + return 0; +} + +/// SimplifyAndInst - Given operands for an And, see if we can +/// fold the result. If not, this returns null. +Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD) { if (Constant *CLHS = dyn_cast(Op0)) { if (Constant *CRHS = dyn_cast(Op1)) { Constant *Ops[] = { CLHS, CRHS }; @@ -77,13 +106,22 @@ Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, (A == Op0 || B == Op0)) return Op0; + // (A & B) & A -> A & B + if (match(Op0, m_And(m_Value(A), m_Value(B))) && + (A == Op1 || B == Op1)) + return Op0; + + // A & (A & B) -> A & B + if (match(Op1, m_And(m_Value(A), m_Value(B))) && + (A == Op0 || B == Op0)) + return Op1; + return 0; } /// SimplifyOrInst - Given operands for an Or, see if we can /// fold the result. If not, this returns null. -Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, - const TargetData *TD) { +Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD) { if (Constant *CLHS = dyn_cast(Op0)) { if (Constant *CRHS = dyn_cast(Op1)) { Constant *Ops[] = { CLHS, CRHS }; @@ -137,10 +175,18 @@ Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, (A == Op0 || B == Op0)) return Op0; - return 0; -} + // (A | B) | A -> A | B + if (match(Op0, m_Or(m_Value(A), m_Value(B))) && + (A == Op1 || B == Op1)) + return Op0; + // A | (A | B) -> A | B + if (match(Op1, m_Or(m_Value(A), m_Value(B))) && + (A == Op0 || B == Op0)) + return Op1; + return 0; +} static const Type *GetCompareTy(Value *Op) { @@ -168,11 +214,10 @@ Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, const Type *ITy = GetCompareTy(LHS); // icmp X, X -> true/false - if (LHS == RHS) + // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false + // because X could be 0. + if (LHS == RHS || isa(RHS)) return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); - - if (isa(RHS)) // X icmp undef -> undef - return UndefValue::get(ITy); // icmp , - Global/Stack value // addresses never equal each other! We already know that Op0 != Op1. @@ -257,12 +302,95 @@ Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, // True if unordered. return ConstantInt::getTrue(CFP->getContext()); } + // Check whether the constant is an infinity. + if (CFP->getValueAPF().isInfinity()) { + if (CFP->getValueAPF().isNegative()) { + switch (Pred) { + case FCmpInst::FCMP_OLT: + // No value is ordered and less than negative infinity. + return ConstantInt::getFalse(CFP->getContext()); + case FCmpInst::FCMP_UGE: + // All values are unordered with or at least negative infinity. + return ConstantInt::getTrue(CFP->getContext()); + default: + break; + } + } else { + switch (Pred) { + case FCmpInst::FCMP_OGT: + // No value is ordered and greater than infinity. + return ConstantInt::getFalse(CFP->getContext()); + case FCmpInst::FCMP_ULE: + // All values are unordered with and at most infinity. + return ConstantInt::getTrue(CFP->getContext()); + default: + break; + } + } + } } } return 0; } +/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold +/// the result. If not, this returns null. +Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal, + const TargetData *TD) { + // select true, X, Y -> X + // select false, X, Y -> Y + if (ConstantInt *CB = dyn_cast(CondVal)) + return CB->getZExtValue() ? TrueVal : FalseVal; + + // select C, X, X -> X + if (TrueVal == FalseVal) + return TrueVal; + + if (isa(TrueVal)) // select C, undef, X -> X + return FalseVal; + if (isa(FalseVal)) // select C, X, undef -> X + return TrueVal; + if (isa(CondVal)) { // select undef, X, Y -> X or Y + if (isa(TrueVal)) + return TrueVal; + return FalseVal; + } + + + + return 0; +} + + +/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can +/// fold the result. If not, this returns null. +Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps, + const TargetData *TD) { + // getelementptr P -> P. + if (NumOps == 1) + return Ops[0]; + + // TODO. + //if (isa(Ops[0])) + // return UndefValue::get(GEP.getType()); + + // getelementptr P, 0 -> P. + if (NumOps == 2) + if (ConstantInt *C = dyn_cast(Ops[1])) + if (C->isZero()) + return Ops[0]; + + // Check to see if this is constant foldable. + for (unsigned i = 0; i != NumOps; ++i) + if (!isa(Ops[i])) + return 0; + + return ConstantExpr::getGetElementPtr(cast(Ops[0]), + (Constant *const*)Ops+1, NumOps-1); +} + + //=== Helper functions for higher up the class hierarchy. /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can @@ -298,6 +426,10 @@ Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD) { switch (I->getOpcode()) { default: return ConstantFoldInstruction(I, TD); + case Instruction::Add: + return SimplifyAddInst(I->getOperand(0), I->getOperand(1), + cast(I)->hasNoSignedWrap(), + cast(I)->hasNoUnsignedWrap(), TD); case Instruction::And: return SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD); case Instruction::Or: @@ -308,6 +440,67 @@ Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD) { case Instruction::FCmp: return SimplifyFCmpInst(cast(I)->getPredicate(), I->getOperand(0), I->getOperand(1), TD); + case Instruction::Select: + return SimplifySelectInst(I->getOperand(0), I->getOperand(1), + I->getOperand(2), TD); + case Instruction::GetElementPtr: { + SmallVector Ops(I->op_begin(), I->op_end()); + return SimplifyGEPInst(&Ops[0], Ops.size(), TD); } + } +} + +/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then +/// delete the From instruction. In addition to a basic RAUW, this does a +/// recursive simplification of the newly formed instructions. This catches +/// things where one simplification exposes other opportunities. This only +/// simplifies and deletes scalar operations, it does not change the CFG. +/// +void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To, + const TargetData *TD) { + assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!"); + + // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that + // we can know if it gets deleted out from under us or replaced in a + // recursive simplification. + WeakVH FromHandle(From); + WeakVH ToHandle(To); + + while (!From->use_empty()) { + // Update the instruction to use the new value. + Use &TheUse = From->use_begin().getUse(); + Instruction *User = cast(TheUse.getUser()); + TheUse = To; + + // Check to see if the instruction can be folded due to the operand + // replacement. For example changing (or X, Y) into (or X, -1) can replace + // the 'or' with -1. + Value *SimplifiedVal; + { + // Sanity check to make sure 'User' doesn't dangle across + // SimplifyInstruction. + AssertingVH<> UserHandle(User); + + SimplifiedVal = SimplifyInstruction(User, TD); + if (SimplifiedVal == 0) continue; + } + + // Recursively simplify this user to the new value. + ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD); + From = dyn_cast_or_null((Value*)FromHandle); + To = ToHandle; + + assert(ToHandle && "To value deleted by recursive simplification?"); + + // If the recursive simplification ended up revisiting and deleting + // 'From' then we're done. + if (From == 0) + return; + } + + // If 'From' has value handles referring to it, do a real RAUW to update them. + From->replaceAllUsesWith(To); + + From->eraseFromParent(); }