1 //===- InstructionSimplify.cpp - Fold instruction operands ----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements routines for folding instructions into simpler forms
11 // that do not require creating new instructions. For example, this does
12 // constant folding, and can handle identities like (X&0)->0.
14 //===----------------------------------------------------------------------===//
16 #include "llvm/Analysis/InstructionSimplify.h"
17 #include "llvm/Analysis/ConstantFolding.h"
18 #include "llvm/Support/ValueHandle.h"
19 #include "llvm/Instructions.h"
20 #include "llvm/Support/PatternMatch.h"
22 using namespace llvm::PatternMatch;
24 #define MaxRecursionDepth 3
26 static Value *SimplifyBinOp(unsigned, Value *, Value *, const TargetData *,
28 static Value *SimplifyCmpInst(unsigned, Value *, Value *, const TargetData *,
31 /// ThreadBinOpOverSelect - In the case of a binary operation with a select
32 /// instruction as an operand, try to simplify the binop by seeing whether
33 /// evaluating it on both branches of the select results in the same value.
34 /// Returns the common value if so, otherwise returns null.
35 static Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS,
36 const TargetData *TD, unsigned MaxRecurse) {
38 if (isa<SelectInst>(LHS)) {
39 SI = cast<SelectInst>(LHS);
41 assert(isa<SelectInst>(RHS) && "No select instruction operand!");
42 SI = cast<SelectInst>(RHS);
45 // Evaluate the BinOp on the true and false branches of the select.
49 TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, MaxRecurse);
50 FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, MaxRecurse);
52 TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, MaxRecurse);
53 FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, MaxRecurse);
56 // If they simplified to the same value, then return the common value.
57 // If they both failed to simplify then return null.
61 // If one branch simplified to undef, return the other one.
62 if (TV && isa<UndefValue>(TV))
64 if (FV && isa<UndefValue>(FV))
67 // If applying the operation did not change the true and false select values,
68 // then the result of the binop is the select itself.
69 if (TV == SI->getTrueValue() && FV == SI->getFalseValue())
72 // If one branch simplified and the other did not, and the simplified
73 // value is equal to the unsimplified one, return the simplified value.
74 // For example, select (cond, X, X & Z) & Z -> X & Z.
75 if ((FV && !TV) || (TV && !FV)) {
76 // Check that the simplified value has the form "X op Y" where "op" is the
77 // same as the original operation.
78 Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV);
79 if (Simplified && Simplified->getOpcode() == Opcode) {
80 // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS".
81 // We already know that "op" is the same as for the simplified value. See
82 // if the operands match too. If so, return the simplified value.
83 Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue();
84 Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS;
85 Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch;
86 if (Simplified->getOperand(0) == UnsimplifiedLHS &&
87 Simplified->getOperand(1) == UnsimplifiedRHS)
89 if (Simplified->isCommutative() &&
90 Simplified->getOperand(1) == UnsimplifiedLHS &&
91 Simplified->getOperand(0) == UnsimplifiedRHS)
99 /// ThreadCmpOverSelect - In the case of a comparison with a select instruction,
100 /// try to simplify the comparison by seeing whether both branches of the select
101 /// result in the same value. Returns the common value if so, otherwise returns
103 static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS,
104 Value *RHS, const TargetData *TD,
105 unsigned MaxRecurse) {
106 // Make sure the select is on the LHS.
107 if (!isa<SelectInst>(LHS)) {
109 Pred = CmpInst::getSwappedPredicate(Pred);
111 assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!");
112 SelectInst *SI = cast<SelectInst>(LHS);
114 // Now that we have "cmp select(cond, TV, FV), RHS", analyse it.
115 // Does "cmp TV, RHS" simplify?
116 if (Value *TCmp = SimplifyCmpInst(Pred, SI->getTrueValue(), RHS, TD,
118 // It does! Does "cmp FV, RHS" simplify?
119 if (Value *FCmp = SimplifyCmpInst(Pred, SI->getFalseValue(), RHS, TD,
121 // It does! If they simplified to the same value, then use it as the
122 // result of the original comparison.
128 /// ThreadBinOpOverPHI - In the case of a binary operation with an operand that
129 /// is a PHI instruction, try to simplify the binop by seeing whether evaluating
130 /// it on the incoming phi values yields the same result for every value. If so
131 /// returns the common value, otherwise returns null.
132 static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS,
133 const TargetData *TD, unsigned MaxRecurse) {
135 if (isa<PHINode>(LHS)) {
136 PI = cast<PHINode>(LHS);
138 assert(isa<PHINode>(RHS) && "No PHI instruction operand!");
139 PI = cast<PHINode>(RHS);
142 // Evaluate the BinOp on the incoming phi values.
143 Value *CommonValue = 0;
144 for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
145 Value *V = PI == LHS ?
146 SimplifyBinOp(Opcode, PI->getIncomingValue(i), RHS, TD, MaxRecurse) :
147 SimplifyBinOp(Opcode, LHS, PI->getIncomingValue(i), TD, MaxRecurse);
148 // If the operation failed to simplify, or simplified to a different value
149 // to previously, then give up.
150 if (!V || (CommonValue && V != CommonValue))
158 /// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try
159 /// try to simplify the comparison by seeing whether comparing with all of the
160 /// incoming phi values yields the same result every time. If so returns the
161 /// common result, otherwise returns null.
162 static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
163 const TargetData *TD, unsigned MaxRecurse) {
164 // Make sure the phi is on the LHS.
165 if (!isa<PHINode>(LHS)) {
167 Pred = CmpInst::getSwappedPredicate(Pred);
169 assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!");
170 PHINode *PI = cast<PHINode>(LHS);
172 // Evaluate the BinOp on the incoming phi values.
173 Value *CommonValue = 0;
174 for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
175 Value *V = SimplifyCmpInst(Pred, PI->getIncomingValue(i), RHS, TD,
177 // If the operation failed to simplify, or simplified to a different value
178 // to previously, then give up.
179 if (!V || (CommonValue && V != CommonValue))
187 /// SimplifyAddInst - Given operands for an Add, see if we can
188 /// fold the result. If not, this returns null.
189 Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
190 const TargetData *TD) {
191 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
192 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
193 Constant *Ops[] = { CLHS, CRHS };
194 return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(),
198 // Canonicalize the constant to the RHS.
202 if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
203 // X + undef -> undef
204 if (isa<UndefValue>(Op1C))
208 if (Op1C->isNullValue())
212 // FIXME: Could pull several more out of instcombine.
216 /// SimplifyAndInst - Given operands for an And, see if we can
217 /// fold the result. If not, this returns null.
218 static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
219 unsigned MaxRecurse) {
220 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
221 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
222 Constant *Ops[] = { CLHS, CRHS };
223 return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
227 // Canonicalize the constant to the RHS.
232 if (isa<UndefValue>(Op1))
233 return Constant::getNullValue(Op0->getType());
240 if (isa<ConstantAggregateZero>(Op1))
244 if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1))
245 if (CP->isAllOnesValue())
248 if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) {
253 if (Op1CI->isAllOnesValue())
257 // A & ~A = ~A & A = 0
259 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
260 (match(Op1, m_Not(m_Value(A))) && A == Op0))
261 return Constant::getNullValue(Op0->getType());
264 if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
265 (A == Op1 || B == Op1))
269 if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
270 (A == Op0 || B == Op0))
273 // (A & B) & A -> A & B
274 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
275 (A == Op1 || B == Op1))
278 // A & (A & B) -> A & B
279 if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
280 (A == Op0 || B == Op0))
283 // If the operation is with the result of a select instruction, check whether
284 // operating on either branch of the select always yields the same value.
285 if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
286 if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD,
290 // If the operation is with the result of a phi instruction, check whether
291 // operating on all incoming values of the phi always yields the same value.
292 if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
293 if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD,
300 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD) {
301 return ::SimplifyAndInst(Op0, Op1, TD, MaxRecursionDepth);
304 /// SimplifyOrInst - Given operands for an Or, see if we can
305 /// fold the result. If not, this returns null.
306 static Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
307 unsigned MaxRecurse) {
308 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
309 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
310 Constant *Ops[] = { CLHS, CRHS };
311 return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
315 // Canonicalize the constant to the RHS.
320 if (isa<UndefValue>(Op1))
321 return Constant::getAllOnesValue(Op0->getType());
328 if (isa<ConstantAggregateZero>(Op1))
331 // X | <-1,-1> = <-1,-1>
332 if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1))
333 if (CP->isAllOnesValue())
336 if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) {
341 if (Op1CI->isAllOnesValue())
345 // A | ~A = ~A | A = -1
347 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
348 (match(Op1, m_Not(m_Value(A))) && A == Op0))
349 return Constant::getAllOnesValue(Op0->getType());
352 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
353 (A == Op1 || B == Op1))
357 if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
358 (A == Op0 || B == Op0))
361 // (A | B) | A -> A | B
362 if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
363 (A == Op1 || B == Op1))
366 // A | (A | B) -> A | B
367 if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
368 (A == Op0 || B == Op0))
371 // If the operation is with the result of a select instruction, check whether
372 // operating on either branch of the select always yields the same value.
373 if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
374 if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD,
378 // If the operation is with the result of a phi instruction, check whether
379 // operating on all incoming values of the phi always yields the same value.
380 if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
381 if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD,
388 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD) {
389 return ::SimplifyOrInst(Op0, Op1, TD, MaxRecursionDepth);
392 static const Type *GetCompareTy(Value *Op) {
393 return CmpInst::makeCmpResultType(Op->getType());
396 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
397 /// fold the result. If not, this returns null.
398 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
399 const TargetData *TD, unsigned MaxRecurse) {
400 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
401 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
403 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
404 if (Constant *CRHS = dyn_cast<Constant>(RHS))
405 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
407 // If we have a constant, make sure it is on the RHS.
409 Pred = CmpInst::getSwappedPredicate(Pred);
412 // ITy - This is the return type of the compare we're considering.
413 const Type *ITy = GetCompareTy(LHS);
415 // icmp X, X -> true/false
416 // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false
417 // because X could be 0.
418 if (LHS == RHS || isa<UndefValue>(RHS))
419 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
421 // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
422 // addresses never equal each other! We already know that Op0 != Op1.
423 if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) ||
424 isa<ConstantPointerNull>(LHS)) &&
425 (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) ||
426 isa<ConstantPointerNull>(RHS)))
427 return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
429 // See if we are doing a comparison with a constant.
430 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
431 // If we have an icmp le or icmp ge instruction, turn it into the
432 // appropriate icmp lt or icmp gt instruction. This allows us to rely on
433 // them being folded in the code below.
436 case ICmpInst::ICMP_ULE:
437 if (CI->isMaxValue(false)) // A <=u MAX -> TRUE
438 return ConstantInt::getTrue(CI->getContext());
440 case ICmpInst::ICMP_SLE:
441 if (CI->isMaxValue(true)) // A <=s MAX -> TRUE
442 return ConstantInt::getTrue(CI->getContext());
444 case ICmpInst::ICMP_UGE:
445 if (CI->isMinValue(false)) // A >=u MIN -> TRUE
446 return ConstantInt::getTrue(CI->getContext());
448 case ICmpInst::ICMP_SGE:
449 if (CI->isMinValue(true)) // A >=s MIN -> TRUE
450 return ConstantInt::getTrue(CI->getContext());
455 // If the comparison is with the result of a select instruction, check whether
456 // comparing with either branch of the select always yields the same value.
457 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
458 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, MaxRecurse-1))
461 // If the comparison is with the result of a phi instruction, check whether
462 // doing the compare with each incoming phi value yields a common result.
463 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
464 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, MaxRecurse-1))
470 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
471 const TargetData *TD) {
472 return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, MaxRecursionDepth);
475 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
476 /// fold the result. If not, this returns null.
477 static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
478 const TargetData *TD, unsigned MaxRecurse) {
479 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
480 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
482 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
483 if (Constant *CRHS = dyn_cast<Constant>(RHS))
484 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
486 // If we have a constant, make sure it is on the RHS.
488 Pred = CmpInst::getSwappedPredicate(Pred);
491 // Fold trivial predicates.
492 if (Pred == FCmpInst::FCMP_FALSE)
493 return ConstantInt::get(GetCompareTy(LHS), 0);
494 if (Pred == FCmpInst::FCMP_TRUE)
495 return ConstantInt::get(GetCompareTy(LHS), 1);
497 if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef
498 return UndefValue::get(GetCompareTy(LHS));
500 // fcmp x,x -> true/false. Not all compares are foldable.
502 if (CmpInst::isTrueWhenEqual(Pred))
503 return ConstantInt::get(GetCompareTy(LHS), 1);
504 if (CmpInst::isFalseWhenEqual(Pred))
505 return ConstantInt::get(GetCompareTy(LHS), 0);
508 // Handle fcmp with constant RHS
509 if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
510 // If the constant is a nan, see if we can fold the comparison based on it.
511 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
512 if (CFP->getValueAPF().isNaN()) {
513 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo"
514 return ConstantInt::getFalse(CFP->getContext());
515 assert(FCmpInst::isUnordered(Pred) &&
516 "Comparison must be either ordered or unordered!");
517 // True if unordered.
518 return ConstantInt::getTrue(CFP->getContext());
520 // Check whether the constant is an infinity.
521 if (CFP->getValueAPF().isInfinity()) {
522 if (CFP->getValueAPF().isNegative()) {
524 case FCmpInst::FCMP_OLT:
525 // No value is ordered and less than negative infinity.
526 return ConstantInt::getFalse(CFP->getContext());
527 case FCmpInst::FCMP_UGE:
528 // All values are unordered with or at least negative infinity.
529 return ConstantInt::getTrue(CFP->getContext());
535 case FCmpInst::FCMP_OGT:
536 // No value is ordered and greater than infinity.
537 return ConstantInt::getFalse(CFP->getContext());
538 case FCmpInst::FCMP_ULE:
539 // All values are unordered with and at most infinity.
540 return ConstantInt::getTrue(CFP->getContext());
549 // If the comparison is with the result of a select instruction, check whether
550 // comparing with either branch of the select always yields the same value.
551 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
552 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, MaxRecurse-1))
555 // If the comparison is with the result of a phi instruction, check whether
556 // doing the compare with each incoming phi value yields a common result.
557 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
558 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, MaxRecurse-1))
564 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
565 const TargetData *TD) {
566 return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, MaxRecursionDepth);
569 /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
570 /// the result. If not, this returns null.
571 Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal,
572 const TargetData *TD) {
573 // select true, X, Y -> X
574 // select false, X, Y -> Y
575 if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal))
576 return CB->getZExtValue() ? TrueVal : FalseVal;
578 // select C, X, X -> X
579 if (TrueVal == FalseVal)
582 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X
584 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X
586 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y
587 if (isa<Constant>(TrueVal))
596 /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
597 /// fold the result. If not, this returns null.
598 Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps,
599 const TargetData *TD) {
600 // getelementptr P -> P.
605 //if (isa<UndefValue>(Ops[0]))
606 // return UndefValue::get(GEP.getType());
608 // getelementptr P, 0 -> P.
610 if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
614 // Check to see if this is constant foldable.
615 for (unsigned i = 0; i != NumOps; ++i)
616 if (!isa<Constant>(Ops[i]))
619 return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]),
620 (Constant *const*)Ops+1, NumOps-1);
624 //=== Helper functions for higher up the class hierarchy.
626 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
627 /// fold the result. If not, this returns null.
628 static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
629 const TargetData *TD, unsigned MaxRecurse) {
631 case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, MaxRecurse);
632 case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD, MaxRecurse);
634 if (Constant *CLHS = dyn_cast<Constant>(LHS))
635 if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
636 Constant *COps[] = {CLHS, CRHS};
637 return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD);
640 // If the operation is with the result of a select instruction, check whether
641 // operating on either branch of the select always yields the same value.
642 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
643 if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, MaxRecurse-1))
646 // If the operation is with the result of a phi instruction, check whether
647 // operating on all incoming values of the phi always yields the same value.
648 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
649 if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, MaxRecurse-1))
656 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
657 const TargetData *TD) {
658 return ::SimplifyBinOp(Opcode, LHS, RHS, TD, MaxRecursionDepth);
661 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
663 static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
664 const TargetData *TD, unsigned MaxRecurse) {
665 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
666 return SimplifyICmpInst(Predicate, LHS, RHS, TD, MaxRecurse);
667 return SimplifyFCmpInst(Predicate, LHS, RHS, TD, MaxRecurse);
670 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
671 const TargetData *TD) {
672 return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, MaxRecursionDepth);
675 /// SimplifyInstruction - See if we can compute a simplified version of this
676 /// instruction. If not, this returns null.
677 Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD) {
678 switch (I->getOpcode()) {
680 return ConstantFoldInstruction(I, TD);
681 case Instruction::Add:
682 return SimplifyAddInst(I->getOperand(0), I->getOperand(1),
683 cast<BinaryOperator>(I)->hasNoSignedWrap(),
684 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), TD);
685 case Instruction::And:
686 return SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD);
687 case Instruction::Or:
688 return SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD);
689 case Instruction::ICmp:
690 return SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
691 I->getOperand(0), I->getOperand(1), TD);
692 case Instruction::FCmp:
693 return SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
694 I->getOperand(0), I->getOperand(1), TD);
695 case Instruction::Select:
696 return SimplifySelectInst(I->getOperand(0), I->getOperand(1),
697 I->getOperand(2), TD);
698 case Instruction::GetElementPtr: {
699 SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
700 return SimplifyGEPInst(&Ops[0], Ops.size(), TD);
702 case Instruction::PHI:
703 return cast<PHINode>(I)->hasConstantValue();
707 /// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
708 /// delete the From instruction. In addition to a basic RAUW, this does a
709 /// recursive simplification of the newly formed instructions. This catches
710 /// things where one simplification exposes other opportunities. This only
711 /// simplifies and deletes scalar operations, it does not change the CFG.
713 void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
714 const TargetData *TD) {
715 assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!");
717 // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that
718 // we can know if it gets deleted out from under us or replaced in a
719 // recursive simplification.
720 WeakVH FromHandle(From);
723 while (!From->use_empty()) {
724 // Update the instruction to use the new value.
725 Use &TheUse = From->use_begin().getUse();
726 Instruction *User = cast<Instruction>(TheUse.getUser());
729 // Check to see if the instruction can be folded due to the operand
730 // replacement. For example changing (or X, Y) into (or X, -1) can replace
732 Value *SimplifiedVal;
734 // Sanity check to make sure 'User' doesn't dangle across
735 // SimplifyInstruction.
736 AssertingVH<> UserHandle(User);
738 SimplifiedVal = SimplifyInstruction(User, TD);
739 if (SimplifiedVal == 0) continue;
742 // Recursively simplify this user to the new value.
743 ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD);
744 From = dyn_cast_or_null<Instruction>((Value*)FromHandle);
747 assert(ToHandle && "To value deleted by recursive simplification?");
749 // If the recursive simplification ended up revisiting and deleting
750 // 'From' then we're done.
755 // If 'From' has value handles referring to it, do a real RAUW to update them.
756 From->replaceAllUsesWith(To);
758 From->eraseFromParent();