diff options
| -rw-r--r-- | include/llvm/Analysis/InstructionSimplify.h | 15 | ||||
| -rw-r--r-- | lib/Analysis/InstructionSimplify.cpp | 173 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/InstructionCombining.cpp | 119 |
3 files changed, 196 insertions, 111 deletions
diff --git a/include/llvm/Analysis/InstructionSimplify.h b/include/llvm/Analysis/InstructionSimplify.h index 7d452ba..2398cf6 100644 --- a/include/llvm/Analysis/InstructionSimplify.h +++ b/include/llvm/Analysis/InstructionSimplify.h @@ -20,15 +20,26 @@ namespace llvm { class Value; class TargetData; + + /// SimplifyAndInst - Given operands for an And, see if we can + /// fold the result. If not, this returns null. + Value *SimplifyAndInst(Value *LHS, Value *RHS, + const TargetData *TD = 0); + + /// SimplifyOrInst - Given operands for an Or, see if we can + /// fold the result. If not, this returns null. + Value *SimplifyOrInst(Value *LHS, Value *RHS, + const TargetData *TD = 0); + /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can /// fold the result. If not, this returns null. Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, - const TargetData *TD = 0); + const TargetData *TD = 0); /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can /// fold the result. If not, this returns null. Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, - const TargetData *TD = 0); + const TargetData *TD = 0); //=== Helper functions for higher up the class hierarchy. diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp index 367a7d4..3c1529c 100644 --- a/lib/Analysis/InstructionSimplify.cpp +++ b/lib/Analysis/InstructionSimplify.cpp @@ -16,21 +16,133 @@ #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/ConstantFolding.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 +/// fold the result. If not, this returns null. +Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, + const TargetData *TD) { + if (Constant *CLHS = dyn_cast<Constant>(Op0)) { + if (Constant *CRHS = dyn_cast<Constant>(Op1)) { + Constant *Ops[] = { CLHS, CRHS }; + return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), + Ops, 2, TD); + } + + // Canonicalize the constant to the RHS. + std::swap(Op0, Op1); + } + + // X & undef -> 0 + if (isa<UndefValue>(Op1)) + return Constant::getNullValue(Op0->getType()); + + // X & X = X + if (Op0 == Op1) + return Op0; + + // X & <0,0> = <0,0> + if (isa<ConstantAggregateZero>(Op1)) + return Op1; + + // X & <-1,-1> = X + if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1)) + if (CP->isAllOnesValue()) + return Op0; + + if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) { + // X & 0 = 0 + if (Op1CI->isZero()) + return Op1CI; + // X & -1 = X + if (Op1CI->isAllOnesValue()) + return Op0; + } + + // A & ~A = ~A & A = 0 + Value *A, *B; + if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || + (match(Op1, m_Not(m_Value(A))) && A == Op0)) + return Constant::getNullValue(Op0->getType()); + + // (A | ?) & A = A + if (match(Op0, m_Or(m_Value(A), m_Value(B))) && + (A == Op1 || B == Op1)) + return Op1; + + // A & (A | ?) = A + if (match(Op1, m_Or(m_Value(A), m_Value(B))) && + (A == Op0 || B == Op0)) + return Op0; + + return 0; +} -/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can +/// SimplifyOrInst - Given operands for an Or, see if we can /// fold the result. If not, this returns null. -Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, - const TargetData *TD) { - if (Constant *CLHS = dyn_cast<Constant>(LHS)) - if (Constant *CRHS = dyn_cast<Constant>(RHS)) { - Constant *COps[] = {CLHS, CRHS}; - return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD); - } +Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, + const TargetData *TD) { + if (Constant *CLHS = dyn_cast<Constant>(Op0)) { + if (Constant *CRHS = dyn_cast<Constant>(Op1)) { + Constant *Ops[] = { CLHS, CRHS }; + return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), + Ops, 2, TD); + } + + // Canonicalize the constant to the RHS. + std::swap(Op0, Op1); + } + + // X | undef -> -1 + if (isa<UndefValue>(Op1)) + return Constant::getAllOnesValue(Op0->getType()); + + // X | X = X + if (Op0 == Op1) + return Op0; + + // X | <0,0> = X + if (isa<ConstantAggregateZero>(Op1)) + return Op0; + + // X | <-1,-1> = <-1,-1> + if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1)) + if (CP->isAllOnesValue()) + return Op1; + + if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) { + // X | 0 = X + if (Op1CI->isZero()) + return Op0; + // X | -1 = -1 + if (Op1CI->isAllOnesValue()) + return Op1CI; + } + + // A | ~A = ~A | A = -1 + Value *A, *B; + if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || + (match(Op1, m_Not(m_Value(A))) && A == Op0)) + return Constant::getAllOnesValue(Op0->getType()); + + // (A & ?) | A = A + if (match(Op0, m_And(m_Value(A), m_Value(B))) && + (A == Op1 || B == Op1)) + return Op1; + + // A | (A & ?) = A + if (match(Op1, m_And(m_Value(A), m_Value(B))) && + (A == Op0 || B == Op0)) + return Op0; + return 0; } + + + static const Type *GetCompareTy(Value *Op) { return CmpInst::makeCmpResultType(Op->getType()); } @@ -43,9 +155,14 @@ Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); - if (Constant *CLHS = dyn_cast<Constant>(LHS)) + if (Constant *CLHS = dyn_cast<Constant>(LHS)) { if (Constant *CRHS = dyn_cast<Constant>(RHS)) return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); + + // If we have a constant, make sure it is on the RHS. + std::swap(LHS, RHS); + Pred = CmpInst::getSwappedPredicate(Pred); + } // ITy - This is the return type of the compare we're considering. const Type *ITy = GetCompareTy(LHS); @@ -54,12 +171,6 @@ Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, if (LHS == RHS) return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); - // If we have a constant, make sure it is on the RHS. - if (isa<Constant>(LHS)) { - std::swap(LHS, RHS); - Pred = CmpInst::getSwappedPredicate(Pred); - } - if (isa<UndefValue>(RHS)) // X icmp undef -> undef return UndefValue::get(ITy); @@ -95,8 +206,6 @@ Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, return ConstantInt::getTrue(CI->getContext()); break; } - - } @@ -110,9 +219,14 @@ Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); - if (Constant *CLHS = dyn_cast<Constant>(LHS)) + if (Constant *CLHS = dyn_cast<Constant>(LHS)) { if (Constant *CRHS = dyn_cast<Constant>(RHS)) return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); + + // If we have a constant, make sure it is on the RHS. + std::swap(LHS, RHS); + Pred = CmpInst::getSwappedPredicate(Pred); + } // Fold trivial predicates. if (Pred == FCmpInst::FCMP_FALSE) @@ -120,12 +234,6 @@ Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, if (Pred == FCmpInst::FCMP_TRUE) return ConstantInt::get(GetCompareTy(LHS), 1); - // If we have a constant, make sure it is on the RHS. - if (isa<Constant>(LHS)) { - std::swap(LHS, RHS); - Pred = CmpInst::getSwappedPredicate(Pred); - } - if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef return UndefValue::get(GetCompareTy(LHS)); @@ -155,7 +263,24 @@ Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, return 0; } +//=== Helper functions for higher up the class hierarchy. +/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can +/// fold the result. If not, this returns null. +Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, + const TargetData *TD) { + switch (Opcode) { + case Instruction::And: return SimplifyAndInst(LHS, RHS, TD); + case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD); + default: + if (Constant *CLHS = dyn_cast<Constant>(LHS)) + if (Constant *CRHS = dyn_cast<Constant>(RHS)) { + Constant *COps[] = {CLHS, CRHS}; + return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD); + } + return 0; + } +} /// SimplifyCmpInst - Given operands for a CmpInst, see if we can /// fold the result. diff --git a/lib/Transforms/Scalar/InstructionCombining.cpp b/lib/Transforms/Scalar/InstructionCombining.cpp index 58a30d6..cd452b5 100644 --- a/lib/Transforms/Scalar/InstructionCombining.cpp +++ b/lib/Transforms/Scalar/InstructionCombining.cpp @@ -4292,25 +4292,15 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) { bool Changed = SimplifyCommutative(I); Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); - if (isa<UndefValue>(Op1)) // X & undef -> 0 - return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); - - // and X, X = X - if (Op0 == Op1) - return ReplaceInstUsesWith(I, Op1); + if (Value *V = SimplifyAndInst(Op0, Op1, TD)) + return ReplaceInstUsesWith(I, V); + // See if we can simplify any instructions used by the instruction whose sole // purpose is to compute bits we don't care about. if (SimplifyDemandedInstructionBits(I)) return &I; - if (isa<VectorType>(I.getType())) { - if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1)) { - if (CP->isAllOnesValue()) // X & <-1,-1> -> X - return ReplaceInstUsesWith(I, I.getOperand(0)); - } else if (isa<ConstantAggregateZero>(Op1)) { - return ReplaceInstUsesWith(I, Op1); // X & <0,0> -> <0,0> - } - } + if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(Op1)) { const APInt &AndRHSMask = AndRHS->getValue(); @@ -4431,42 +4421,29 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) { return NV; } - Value *Op0NotVal = dyn_castNotVal(Op0); - Value *Op1NotVal = dyn_castNotVal(Op1); - - if (Op0NotVal == Op1 || Op1NotVal == Op0) // A & ~A == ~A & A == 0 - return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); // (~A & ~B) == (~(A | B)) - De Morgan's Law - if (Op0NotVal && Op1NotVal && isOnlyUse(Op0) && isOnlyUse(Op1)) { - Value *Or = Builder->CreateOr(Op0NotVal, Op1NotVal, - I.getName()+".demorgan"); - return BinaryOperator::CreateNot(Or); - } - + if (Value *Op0NotVal = dyn_castNotVal(Op0)) + if (Value *Op1NotVal = dyn_castNotVal(Op1)) + if (Op0->hasOneUse() && Op1->hasOneUse()) { + Value *Or = Builder->CreateOr(Op0NotVal, Op1NotVal, + I.getName()+".demorgan"); + return BinaryOperator::CreateNot(Or); + } + { Value *A = 0, *B = 0, *C = 0, *D = 0; - if (match(Op0, m_Or(m_Value(A), m_Value(B)))) { - if (A == Op1 || B == Op1) // (A | ?) & A --> A - return ReplaceInstUsesWith(I, Op1); - - // (A|B) & ~(A&B) -> A^B - if (match(Op1, m_Not(m_And(m_Value(C), m_Value(D))))) { - if ((A == C && B == D) || (A == D && B == C)) - return BinaryOperator::CreateXor(A, B); - } - } + // (A|B) & ~(A&B) -> A^B + if (match(Op0, m_Or(m_Value(A), m_Value(B))) && + match(Op1, m_Not(m_And(m_Value(C), m_Value(D)))) && + ((A == C && B == D) || (A == D && B == C))) + return BinaryOperator::CreateXor(A, B); - if (match(Op1, m_Or(m_Value(A), m_Value(B)))) { - if (A == Op0 || B == Op0) // A & (A | ?) --> A - return ReplaceInstUsesWith(I, Op0); - - // ~(A&B) & (A|B) -> A^B - if (match(Op0, m_Not(m_And(m_Value(C), m_Value(D))))) { - if ((A == C && B == D) || (A == D && B == C)) - return BinaryOperator::CreateXor(A, B); - } - } + // ~(A&B) & (A|B) -> A^B + if (match(Op1, m_Or(m_Value(A), m_Value(B))) && + match(Op0, m_Not(m_And(m_Value(C), m_Value(D)))) && + ((A == C && B == D) || (A == D && B == C))) + return BinaryOperator::CreateXor(A, B); if (Op0->hasOneUse() && match(Op0, m_Xor(m_Value(A), m_Value(B)))) { @@ -4998,27 +4975,15 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { bool Changed = SimplifyCommutative(I); Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); - if (isa<UndefValue>(Op1)) // X | undef -> -1 - return ReplaceInstUsesWith(I, Constant::getAllOnesValue(I.getType())); - - // or X, X = X - if (Op0 == Op1) - return ReplaceInstUsesWith(I, Op0); - + if (Value *V = SimplifyOrInst(Op0, Op1, TD)) + return ReplaceInstUsesWith(I, V); + + // See if we can simplify any instructions used by the instruction whose sole // purpose is to compute bits we don't care about. if (SimplifyDemandedInstructionBits(I)) return &I; - if (isa<VectorType>(I.getType())) { - if (isa<ConstantAggregateZero>(Op1)) { - return ReplaceInstUsesWith(I, Op0); // X | <0,0> -> X - } else if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1)) { - if (CP->isAllOnesValue()) // X | <-1,-1> -> <-1,-1> - return ReplaceInstUsesWith(I, I.getOperand(1)); - } - } - // or X, -1 == -1 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { ConstantInt *C1 = 0; Value *X = 0; // (X & C1) | C2 --> (X | C2) & (C1|C2) @@ -5051,13 +5016,6 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { Value *A = 0, *B = 0; ConstantInt *C1 = 0, *C2 = 0; - if (match(Op0, m_And(m_Value(A), m_Value(B)))) - if (A == Op1 || B == Op1) // (A & ?) | A --> A - return ReplaceInstUsesWith(I, Op1); - if (match(Op1, m_And(m_Value(A), m_Value(B)))) - if (A == Op0 || B == Op0) // A | (A & ?) --> A - return ReplaceInstUsesWith(I, Op0); - // (A | B) | C and A | (B | C) -> bswap if possible. // (A >> B) | (C << D) and (A << B) | (B >> C) -> bswap if possible. if (match(Op0, m_Or(m_Value(), m_Value())) || @@ -5191,23 +5149,14 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { if (Ret) return Ret; } - if ((A = dyn_castNotVal(Op0))) { // ~A | Op1 - if (A == Op1) // ~A | A == -1 - return ReplaceInstUsesWith(I, Constant::getAllOnesValue(I.getType())); - } else { - A = 0; - } - // Note, A is still live here! - if ((B = dyn_castNotVal(Op1))) { // Op0 | ~B - if (Op0 == B) - return ReplaceInstUsesWith(I, Constant::getAllOnesValue(I.getType())); - - // (~A | ~B) == (~(A & B)) - De Morgan's Law - if (A && isOnlyUse(Op0) && isOnlyUse(Op1)) { - Value *And = Builder->CreateAnd(A, B, I.getName()+".demorgan"); - return BinaryOperator::CreateNot(And); - } - } + // (~A | ~B) == (~(A & B)) - De Morgan's Law + if (Value *Op0NotVal = dyn_castNotVal(Op0)) + if (Value *Op1NotVal = dyn_castNotVal(Op1)) + if (Op0->hasOneUse() && Op1->hasOneUse()) { + Value *And = Builder->CreateAnd(Op0NotVal, Op1NotVal, + I.getName()+".demorgan"); + return BinaryOperator::CreateNot(And); + } // (icmp1 A, B) | (icmp2 A, B) --> (icmp3 A, B) if (ICmpInst *RHS = dyn_cast<ICmpInst>(I.getOperand(1))) { |