Changeset View
Changeset View
Standalone View
Standalone View
llvm/trunk/lib/Analysis/InstructionSimplify.cpp
| Show All 33 Lines | |||||
| using namespace llvm; | using namespace llvm; | ||||
| using namespace llvm::PatternMatch; | using namespace llvm::PatternMatch; | ||||
| #define DEBUG_TYPE "instsimplify" | #define DEBUG_TYPE "instsimplify" | ||||
| enum { RecursionLimit = 3 }; | enum { RecursionLimit = 3 }; | ||||
| STATISTIC(NumExpand, "Number of expansions"); | STATISTIC(NumExpand, "Number of expansions"); | ||||
| STATISTIC(NumFactor , "Number of factorizations"); | |||||
| STATISTIC(NumReassoc, "Number of reassociations"); | STATISTIC(NumReassoc, "Number of reassociations"); | ||||
| struct Query { | struct Query { | ||||
| const DataLayout *DL; | const DataLayout *DL; | ||||
| const TargetLibraryInfo *TLI; | const TargetLibraryInfo *TLI; | ||||
| const DominatorTree *DT; | const DominatorTree *DT; | ||||
| Query(const DataLayout *DL, const TargetLibraryInfo *tli, | Query(const DataLayout *DL, const TargetLibraryInfo *tli, | ||||
| ▲ Show 20 Lines • Show All 127 Lines • ▼ Show 20 Lines | if (Op1->getOpcode() == OpcodeToExpand) { | ||||
| return V; | return V; | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| return nullptr; | return nullptr; | ||||
| } | } | ||||
| /// FactorizeBinOp - Simplify "LHS Opcode RHS" by factorizing out a common term | |||||
| /// using the operation OpCodeToExtract. For example, when Opcode is Add and | |||||
| /// OpCodeToExtract is Mul then this tries to turn "(A*B)+(A*C)" into "A*(B+C)". | |||||
| /// Returns the simplified value, or null if no simplification was performed. | |||||
| static Value *FactorizeBinOp(unsigned Opcode, Value *LHS, Value *RHS, | |||||
| unsigned OpcToExtract, const Query &Q, | |||||
| unsigned MaxRecurse) { | |||||
| Instruction::BinaryOps OpcodeToExtract = (Instruction::BinaryOps)OpcToExtract; | |||||
| // Recursion is always used, so bail out at once if we already hit the limit. | |||||
| if (!MaxRecurse--) | |||||
| return nullptr; | |||||
| BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS); | |||||
| BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS); | |||||
| if (!Op0 || Op0->getOpcode() != OpcodeToExtract || | |||||
| !Op1 || Op1->getOpcode() != OpcodeToExtract) | |||||
| return nullptr; | |||||
| // The expression has the form "(A op' B) op (C op' D)". | |||||
| Value *A = Op0->getOperand(0), *B = Op0->getOperand(1); | |||||
| Value *C = Op1->getOperand(0), *D = Op1->getOperand(1); | |||||
| // Use left distributivity, i.e. "X op' (Y op Z) = (X op' Y) op (X op' Z)". | |||||
| // Does the instruction have the form "(A op' B) op (A op' D)" or, in the | |||||
| // commutative case, "(A op' B) op (C op' A)"? | |||||
| if (A == C || (Instruction::isCommutative(OpcodeToExtract) && A == D)) { | |||||
| Value *DD = A == C ? D : C; | |||||
| // Form "A op' (B op DD)" if it simplifies completely. | |||||
| // Does "B op DD" simplify? | |||||
| if (Value *V = SimplifyBinOp(Opcode, B, DD, Q, MaxRecurse)) { | |||||
| // It does! Return "A op' V" if it simplifies or is already available. | |||||
| // If V equals B then "A op' V" is just the LHS. If V equals DD then | |||||
| // "A op' V" is just the RHS. | |||||
| if (V == B || V == DD) { | |||||
| ++NumFactor; | |||||
| return V == B ? LHS : RHS; | |||||
| } | |||||
| // Otherwise return "A op' V" if it simplifies. | |||||
| if (Value *W = SimplifyBinOp(OpcodeToExtract, A, V, Q, MaxRecurse)) { | |||||
| ++NumFactor; | |||||
| return W; | |||||
| } | |||||
| } | |||||
| } | |||||
| // Use right distributivity, i.e. "(X op Y) op' Z = (X op' Z) op (Y op' Z)". | |||||
| // Does the instruction have the form "(A op' B) op (C op' B)" or, in the | |||||
| // commutative case, "(A op' B) op (B op' D)"? | |||||
| if (B == D || (Instruction::isCommutative(OpcodeToExtract) && B == C)) { | |||||
| Value *CC = B == D ? C : D; | |||||
| // Form "(A op CC) op' B" if it simplifies completely.. | |||||
| // Does "A op CC" simplify? | |||||
| if (Value *V = SimplifyBinOp(Opcode, A, CC, Q, MaxRecurse)) { | |||||
| // It does! Return "V op' B" if it simplifies or is already available. | |||||
| // If V equals A then "V op' B" is just the LHS. If V equals CC then | |||||
| // "V op' B" is just the RHS. | |||||
| if (V == A || V == CC) { | |||||
| ++NumFactor; | |||||
| return V == A ? LHS : RHS; | |||||
| } | |||||
| // Otherwise return "V op' B" if it simplifies. | |||||
| if (Value *W = SimplifyBinOp(OpcodeToExtract, V, B, Q, MaxRecurse)) { | |||||
| ++NumFactor; | |||||
| return W; | |||||
| } | |||||
| } | |||||
| } | |||||
| return nullptr; | |||||
| } | |||||
| /// SimplifyAssociativeBinOp - Generic simplifications for associative binary | /// SimplifyAssociativeBinOp - Generic simplifications for associative binary | ||||
| /// operations. Returns the simpler value, or null if none was found. | /// operations. Returns the simpler value, or null if none was found. | ||||
| static Value *SimplifyAssociativeBinOp(unsigned Opc, Value *LHS, Value *RHS, | static Value *SimplifyAssociativeBinOp(unsigned Opc, Value *LHS, Value *RHS, | ||||
| const Query &Q, unsigned MaxRecurse) { | const Query &Q, unsigned MaxRecurse) { | ||||
| Instruction::BinaryOps Opcode = (Instruction::BinaryOps)Opc; | Instruction::BinaryOps Opcode = (Instruction::BinaryOps)Opc; | ||||
| assert(Instruction::isAssociative(Opcode) && "Not an associative operation!"); | assert(Instruction::isAssociative(Opcode) && "Not an associative operation!"); | ||||
| // Recursion is always used, so bail out at once if we already hit the limit. | // Recursion is always used, so bail out at once if we already hit the limit. | ||||
| ▲ Show 20 Lines • Show All 363 Lines • ▼ Show 20 Lines | if (MaxRecurse && Op0->getType()->isIntegerTy(1)) | ||||
| if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1)) | if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1)) | ||||
| return V; | return V; | ||||
| // Try some generic simplifications for associative operations. | // Try some generic simplifications for associative operations. | ||||
| if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, Q, | if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, Q, | ||||
| MaxRecurse)) | MaxRecurse)) | ||||
| return V; | return V; | ||||
| // Mul distributes over Add. Try some generic simplifications based on this. | |||||
| if (Value *V = FactorizeBinOp(Instruction::Add, Op0, Op1, Instruction::Mul, | |||||
| Q, MaxRecurse)) | |||||
| return V; | |||||
| // Threading Add over selects and phi nodes is pointless, so don't bother. | // Threading Add over selects and phi nodes is pointless, so don't bother. | ||||
| // Threading over the select in "A + select(cond, B, C)" means evaluating | // Threading over the select in "A + select(cond, B, C)" means evaluating | ||||
| // "A+B" and "A+C" and seeing if they are equal; but they are equal if and | // "A+B" and "A+C" and seeing if they are equal; but they are equal if and | ||||
| // only if B and C are equal. If B and C are equal then (since we assume | // only if B and C are equal. If B and C are equal then (since we assume | ||||
| // that operands have already been simplified) "select(cond, B, C)" should | // that operands have already been simplified) "select(cond, B, C)" should | ||||
| // have been simplified to the common value of B and C already. Analysing | // have been simplified to the common value of B and C already. Analysing | ||||
| // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly | // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly | ||||
| // for threading over phi nodes. | // for threading over phi nodes. | ||||
| ▲ Show 20 Lines • Show All 99 Lines • ▼ Show 20 Lines | static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, | ||||
| // X - 0 -> X | // X - 0 -> X | ||||
| if (match(Op1, m_Zero())) | if (match(Op1, m_Zero())) | ||||
| return Op0; | return Op0; | ||||
| // X - X -> 0 | // X - X -> 0 | ||||
| if (Op0 == Op1) | if (Op0 == Op1) | ||||
| return Constant::getNullValue(Op0->getType()); | return Constant::getNullValue(Op0->getType()); | ||||
| // (X*2) - X -> X | |||||
| // (X<<1) - X -> X | |||||
| Value *X = nullptr; | |||||
| if (match(Op0, m_Mul(m_Specific(Op1), m_ConstantInt<2>())) || | |||||
| match(Op0, m_Shl(m_Specific(Op1), m_One()))) | |||||
| return Op1; | |||||
| // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies. | // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies. | ||||
| // For example, (X + Y) - Y -> X; (Y + X) - Y -> X | // For example, (X + Y) - Y -> X; (Y + X) - Y -> X | ||||
| Value *Y = nullptr, *Z = Op1; | Value *X = nullptr, *Y = nullptr, *Z = Op1; | ||||
| if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z | if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z | ||||
| // See if "V === Y - Z" simplifies. | // See if "V === Y - Z" simplifies. | ||||
| if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, Q, MaxRecurse-1)) | if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, Q, MaxRecurse-1)) | ||||
| // It does! Now see if "X + V" simplifies. | // It does! Now see if "X + V" simplifies. | ||||
| if (Value *W = SimplifyBinOp(Instruction::Add, X, V, Q, MaxRecurse-1)) { | if (Value *W = SimplifyBinOp(Instruction::Add, X, V, Q, MaxRecurse-1)) { | ||||
| // It does, we successfully reassociated! | // It does, we successfully reassociated! | ||||
| ++NumReassoc; | ++NumReassoc; | ||||
| return W; | return W; | ||||
| ▲ Show 20 Lines • Show All 55 Lines • ▼ Show 20 Lines | if (X->getType() == Y->getType()) | ||||
| return W; | return W; | ||||
| // Variations on GEP(base, I, ...) - GEP(base, i, ...) -> GEP(null, I-i, ...). | // Variations on GEP(base, I, ...) - GEP(base, i, ...) -> GEP(null, I-i, ...). | ||||
| if (match(Op0, m_PtrToInt(m_Value(X))) && | if (match(Op0, m_PtrToInt(m_Value(X))) && | ||||
| match(Op1, m_PtrToInt(m_Value(Y)))) | match(Op1, m_PtrToInt(m_Value(Y)))) | ||||
| if (Constant *Result = computePointerDifference(Q.DL, X, Y)) | if (Constant *Result = computePointerDifference(Q.DL, X, Y)) | ||||
| return ConstantExpr::getIntegerCast(Result, Op0->getType(), true); | return ConstantExpr::getIntegerCast(Result, Op0->getType(), true); | ||||
| // Mul distributes over Sub. Try some generic simplifications based on this. | |||||
| if (Value *V = FactorizeBinOp(Instruction::Sub, Op0, Op1, Instruction::Mul, | |||||
| Q, MaxRecurse)) | |||||
| return V; | |||||
| // i1 sub -> xor. | // i1 sub -> xor. | ||||
| if (MaxRecurse && Op0->getType()->isIntegerTy(1)) | if (MaxRecurse && Op0->getType()->isIntegerTy(1)) | ||||
| if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1)) | if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1)) | ||||
| return V; | return V; | ||||
| // Threading Sub over selects and phi nodes is pointless, so don't bother. | // Threading Sub over selects and phi nodes is pointless, so don't bother. | ||||
| // Threading over the select in "A - select(cond, B, C)" means evaluating | // Threading over the select in "A - select(cond, B, C)" means evaluating | ||||
| // "A-B" and "A-C" and seeing if they are equal; but they are equal if and | // "A-B" and "A-C" and seeing if they are equal; but they are equal if and | ||||
| ▲ Show 20 Lines • Show All 662 Lines • ▼ Show 20 Lines | if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or, | ||||
| Q, MaxRecurse)) | Q, MaxRecurse)) | ||||
| return V; | return V; | ||||
| // And distributes over Xor. Try some generic simplifications based on this. | // And distributes over Xor. Try some generic simplifications based on this. | ||||
| if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor, | if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor, | ||||
| Q, MaxRecurse)) | Q, MaxRecurse)) | ||||
| return V; | return V; | ||||
| // Or distributes over And. Try some generic simplifications based on this. | |||||
| if (Value *V = FactorizeBinOp(Instruction::And, Op0, Op1, Instruction::Or, | |||||
| Q, MaxRecurse)) | |||||
| return V; | |||||
| // If the operation is with the result of a select instruction, check whether | // If the operation is with the result of a select instruction, check whether | ||||
| // operating on either branch of the select always yields the same value. | // operating on either branch of the select always yields the same value. | ||||
| if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) | if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) | ||||
| if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, Q, | if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, Q, | ||||
| MaxRecurse)) | MaxRecurse)) | ||||
| return V; | return V; | ||||
| // If the operation is with the result of a phi instruction, check whether | // If the operation is with the result of a phi instruction, check whether | ||||
| ▲ Show 20 Lines • Show All 74 Lines • ▼ Show 20 Lines | if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, Q, | ||||
| MaxRecurse)) | MaxRecurse)) | ||||
| return V; | return V; | ||||
| // Or distributes over And. Try some generic simplifications based on this. | // Or distributes over And. Try some generic simplifications based on this. | ||||
| if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, Q, | if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, Q, | ||||
| MaxRecurse)) | MaxRecurse)) | ||||
| return V; | return V; | ||||
| // And distributes over Or. Try some generic simplifications based on this. | |||||
| if (Value *V = FactorizeBinOp(Instruction::Or, Op0, Op1, Instruction::And, | |||||
| Q, MaxRecurse)) | |||||
| return V; | |||||
| // If the operation is with the result of a select instruction, check whether | // If the operation is with the result of a select instruction, check whether | ||||
| // operating on either branch of the select always yields the same value. | // operating on either branch of the select always yields the same value. | ||||
| if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) | if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) | ||||
| if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, Q, | if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, Q, | ||||
| MaxRecurse)) | MaxRecurse)) | ||||
| return V; | return V; | ||||
| // (A & C)|(B & D) | // (A & C)|(B & D) | ||||
| ▲ Show 20 Lines • Show All 75 Lines • ▼ Show 20 Lines | if (match(Op0, m_Not(m_Specific(Op1))) || | ||||
| match(Op1, m_Not(m_Specific(Op0)))) | match(Op1, m_Not(m_Specific(Op0)))) | ||||
| return Constant::getAllOnesValue(Op0->getType()); | return Constant::getAllOnesValue(Op0->getType()); | ||||
| // Try some generic simplifications for associative operations. | // Try some generic simplifications for associative operations. | ||||
| if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, Q, | if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, Q, | ||||
| MaxRecurse)) | MaxRecurse)) | ||||
| return V; | return V; | ||||
| // And distributes over Xor. Try some generic simplifications based on this. | |||||
| if (Value *V = FactorizeBinOp(Instruction::Xor, Op0, Op1, Instruction::And, | |||||
| Q, MaxRecurse)) | |||||
| return V; | |||||
| // Threading Xor over selects and phi nodes is pointless, so don't bother. | // Threading Xor over selects and phi nodes is pointless, so don't bother. | ||||
| // Threading over the select in "A ^ select(cond, B, C)" means evaluating | // Threading over the select in "A ^ select(cond, B, C)" means evaluating | ||||
| // "A^B" and "A^C" and seeing if they are equal; but they are equal if and | // "A^B" and "A^C" and seeing if they are equal; but they are equal if and | ||||
| // only if B and C are equal. If B and C are equal then (since we assume | // only if B and C are equal. If B and C are equal then (since we assume | ||||
| // that operands have already been simplified) "select(cond, B, C)" should | // that operands have already been simplified) "select(cond, B, C)" should | ||||
| // have been simplified to the common value of B and C already. Analysing | // have been simplified to the common value of B and C already. Analysing | ||||
| // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly | // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly | ||||
| // for threading over phi nodes. | // for threading over phi nodes. | ||||
| ▲ Show 20 Lines • Show All 1,634 Lines • Show Last 20 Lines | |||||