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 *Incoming = PI->getIncomingValue(i);
146 // If the incoming value is the phi node itself, it can be safely skipped.
147 if (Incoming == PI) continue;
148 Value *V = PI == LHS ?
149 SimplifyBinOp(Opcode, Incoming, RHS, TD, MaxRecurse) :
150 SimplifyBinOp(Opcode, LHS, Incoming, TD, MaxRecurse);
151 // If the operation failed to simplify, or simplified to a different value
152 // to previously, then give up.
153 if (!V || (CommonValue && V != CommonValue))
161 /// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try
162 /// try to simplify the comparison by seeing whether comparing with all of the
163 /// incoming phi values yields the same result every time. If so returns the
164 /// common result, otherwise returns null.
165 static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
166 const TargetData *TD, unsigned MaxRecurse) {
167 // Make sure the phi is on the LHS.
168 if (!isa<PHINode>(LHS)) {
170 Pred = CmpInst::getSwappedPredicate(Pred);
172 assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!");
173 PHINode *PI = cast<PHINode>(LHS);
175 // Evaluate the BinOp on the incoming phi values.
176 Value *CommonValue = 0;
177 for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
178 Value *Incoming = PI->getIncomingValue(i);
179 // If the incoming value is the phi node itself, it can be safely skipped.
180 if (Incoming == PI) continue;
181 Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, MaxRecurse);
182 // If the operation failed to simplify, or simplified to a different value
183 // to previously, then give up.
184 if (!V || (CommonValue && V != CommonValue))
192 /// SimplifyAddInst - Given operands for an Add, see if we can
193 /// fold the result. If not, this returns null.
194 Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
195 const TargetData *TD) {
196 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
197 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
198 Constant *Ops[] = { CLHS, CRHS };
199 return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(),
203 // Canonicalize the constant to the RHS.
207 if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
208 // X + undef -> undef
209 if (isa<UndefValue>(Op1C))
213 if (Op1C->isNullValue())
217 // FIXME: Could pull several more out of instcombine.
221 /// SimplifyAndInst - Given operands for an And, see if we can
222 /// fold the result. If not, this returns null.
223 static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
224 unsigned MaxRecurse) {
225 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
226 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
227 Constant *Ops[] = { CLHS, CRHS };
228 return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
232 // Canonicalize the constant to the RHS.
237 if (isa<UndefValue>(Op1))
238 return Constant::getNullValue(Op0->getType());
245 if (isa<ConstantAggregateZero>(Op1))
249 if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1))
250 if (CP->isAllOnesValue())
253 if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) {
258 if (Op1CI->isAllOnesValue())
262 // A & ~A = ~A & A = 0
264 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
265 (match(Op1, m_Not(m_Value(A))) && A == Op0))
266 return Constant::getNullValue(Op0->getType());
269 if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
270 (A == Op1 || B == Op1))
274 if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
275 (A == Op0 || B == Op0))
278 // (A & B) & A -> A & B
279 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
280 (A == Op1 || B == Op1))
283 // A & (A & B) -> A & B
284 if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
285 (A == Op0 || B == Op0))
288 // If the operation is with the result of a select instruction, check whether
289 // operating on either branch of the select always yields the same value.
290 if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
291 if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD,
295 // If the operation is with the result of a phi instruction, check whether
296 // operating on all incoming values of the phi always yields the same value.
297 if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
298 if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD,
305 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD) {
306 return ::SimplifyAndInst(Op0, Op1, TD, MaxRecursionDepth);
309 /// SimplifyOrInst - Given operands for an Or, see if we can
310 /// fold the result. If not, this returns null.
311 static Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
312 unsigned MaxRecurse) {
313 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
314 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
315 Constant *Ops[] = { CLHS, CRHS };
316 return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
320 // Canonicalize the constant to the RHS.
325 if (isa<UndefValue>(Op1))
326 return Constant::getAllOnesValue(Op0->getType());
333 if (isa<ConstantAggregateZero>(Op1))
336 // X | <-1,-1> = <-1,-1>
337 if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1))
338 if (CP->isAllOnesValue())
341 if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) {
346 if (Op1CI->isAllOnesValue())
350 // A | ~A = ~A | A = -1
352 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
353 (match(Op1, m_Not(m_Value(A))) && A == Op0))
354 return Constant::getAllOnesValue(Op0->getType());
357 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
358 (A == Op1 || B == Op1))
362 if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
363 (A == Op0 || B == Op0))
366 // (A | B) | A -> A | B
367 if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
368 (A == Op1 || B == Op1))
371 // A | (A | B) -> A | B
372 if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
373 (A == Op0 || B == Op0))
376 // If the operation is with the result of a select instruction, check whether
377 // operating on either branch of the select always yields the same value.
378 if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
379 if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD,
383 // If the operation is with the result of a phi instruction, check whether
384 // operating on all incoming values of the phi always yields the same value.
385 if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
386 if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD,
393 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD) {
394 return ::SimplifyOrInst(Op0, Op1, TD, MaxRecursionDepth);
397 static const Type *GetCompareTy(Value *Op) {
398 return CmpInst::makeCmpResultType(Op->getType());
401 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
402 /// fold the result. If not, this returns null.
403 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
404 const TargetData *TD, unsigned MaxRecurse) {
405 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
406 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
408 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
409 if (Constant *CRHS = dyn_cast<Constant>(RHS))
410 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
412 // If we have a constant, make sure it is on the RHS.
414 Pred = CmpInst::getSwappedPredicate(Pred);
417 // ITy - This is the return type of the compare we're considering.
418 const Type *ITy = GetCompareTy(LHS);
420 // icmp X, X -> true/false
421 // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false
422 // because X could be 0.
423 if (LHS == RHS || isa<UndefValue>(RHS))
424 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
426 // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
427 // addresses never equal each other! We already know that Op0 != Op1.
428 if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) ||
429 isa<ConstantPointerNull>(LHS)) &&
430 (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) ||
431 isa<ConstantPointerNull>(RHS)))
432 return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
434 // See if we are doing a comparison with a constant.
435 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
436 // If we have an icmp le or icmp ge instruction, turn it into the
437 // appropriate icmp lt or icmp gt instruction. This allows us to rely on
438 // them being folded in the code below.
441 case ICmpInst::ICMP_ULE:
442 if (CI->isMaxValue(false)) // A <=u MAX -> TRUE
443 return ConstantInt::getTrue(CI->getContext());
445 case ICmpInst::ICMP_SLE:
446 if (CI->isMaxValue(true)) // A <=s MAX -> TRUE
447 return ConstantInt::getTrue(CI->getContext());
449 case ICmpInst::ICMP_UGE:
450 if (CI->isMinValue(false)) // A >=u MIN -> TRUE
451 return ConstantInt::getTrue(CI->getContext());
453 case ICmpInst::ICMP_SGE:
454 if (CI->isMinValue(true)) // A >=s MIN -> TRUE
455 return ConstantInt::getTrue(CI->getContext());
460 // If the comparison is with the result of a select instruction, check whether
461 // comparing with either branch of the select always yields the same value.
462 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
463 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, MaxRecurse-1))
466 // If the comparison is with the result of a phi instruction, check whether
467 // doing the compare with each incoming phi value yields a common result.
468 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
469 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, MaxRecurse-1))
475 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
476 const TargetData *TD) {
477 return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, MaxRecursionDepth);
480 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
481 /// fold the result. If not, this returns null.
482 static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
483 const TargetData *TD, unsigned MaxRecurse) {
484 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
485 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
487 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
488 if (Constant *CRHS = dyn_cast<Constant>(RHS))
489 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
491 // If we have a constant, make sure it is on the RHS.
493 Pred = CmpInst::getSwappedPredicate(Pred);
496 // Fold trivial predicates.
497 if (Pred == FCmpInst::FCMP_FALSE)
498 return ConstantInt::get(GetCompareTy(LHS), 0);
499 if (Pred == FCmpInst::FCMP_TRUE)
500 return ConstantInt::get(GetCompareTy(LHS), 1);
502 if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef
503 return UndefValue::get(GetCompareTy(LHS));
505 // fcmp x,x -> true/false. Not all compares are foldable.
507 if (CmpInst::isTrueWhenEqual(Pred))
508 return ConstantInt::get(GetCompareTy(LHS), 1);
509 if (CmpInst::isFalseWhenEqual(Pred))
510 return ConstantInt::get(GetCompareTy(LHS), 0);
513 // Handle fcmp with constant RHS
514 if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
515 // If the constant is a nan, see if we can fold the comparison based on it.
516 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
517 if (CFP->getValueAPF().isNaN()) {
518 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo"
519 return ConstantInt::getFalse(CFP->getContext());
520 assert(FCmpInst::isUnordered(Pred) &&
521 "Comparison must be either ordered or unordered!");
522 // True if unordered.
523 return ConstantInt::getTrue(CFP->getContext());
525 // Check whether the constant is an infinity.
526 if (CFP->getValueAPF().isInfinity()) {
527 if (CFP->getValueAPF().isNegative()) {
529 case FCmpInst::FCMP_OLT:
530 // No value is ordered and less than negative infinity.
531 return ConstantInt::getFalse(CFP->getContext());
532 case FCmpInst::FCMP_UGE:
533 // All values are unordered with or at least negative infinity.
534 return ConstantInt::getTrue(CFP->getContext());
540 case FCmpInst::FCMP_OGT:
541 // No value is ordered and greater than infinity.
542 return ConstantInt::getFalse(CFP->getContext());
543 case FCmpInst::FCMP_ULE:
544 // All values are unordered with and at most infinity.
545 return ConstantInt::getTrue(CFP->getContext());
554 // If the comparison is with the result of a select instruction, check whether
555 // comparing with either branch of the select always yields the same value.
556 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
557 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, MaxRecurse-1))
560 // If the comparison is with the result of a phi instruction, check whether
561 // doing the compare with each incoming phi value yields a common result.
562 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
563 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, MaxRecurse-1))
569 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
570 const TargetData *TD) {
571 return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, MaxRecursionDepth);
574 /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
575 /// the result. If not, this returns null.
576 Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal,
577 const TargetData *TD) {
578 // select true, X, Y -> X
579 // select false, X, Y -> Y
580 if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal))
581 return CB->getZExtValue() ? TrueVal : FalseVal;
583 // select C, X, X -> X
584 if (TrueVal == FalseVal)
587 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X
589 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X
591 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y
592 if (isa<Constant>(TrueVal))
601 /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
602 /// fold the result. If not, this returns null.
603 Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps,
604 const TargetData *TD) {
605 // getelementptr P -> P.
610 //if (isa<UndefValue>(Ops[0]))
611 // return UndefValue::get(GEP.getType());
613 // getelementptr P, 0 -> P.
615 if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
619 // Check to see if this is constant foldable.
620 for (unsigned i = 0; i != NumOps; ++i)
621 if (!isa<Constant>(Ops[i]))
624 return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]),
625 (Constant *const*)Ops+1, NumOps-1);
629 //=== Helper functions for higher up the class hierarchy.
631 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
632 /// fold the result. If not, this returns null.
633 static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
634 const TargetData *TD, unsigned MaxRecurse) {
636 case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, MaxRecurse);
637 case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD, MaxRecurse);
639 if (Constant *CLHS = dyn_cast<Constant>(LHS))
640 if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
641 Constant *COps[] = {CLHS, CRHS};
642 return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD);
645 // If the operation is with the result of a select instruction, check whether
646 // operating on either branch of the select always yields the same value.
647 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
648 if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, MaxRecurse-1))
651 // If the operation is with the result of a phi instruction, check whether
652 // operating on all incoming values of the phi always yields the same value.
653 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
654 if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, MaxRecurse-1))
661 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
662 const TargetData *TD) {
663 return ::SimplifyBinOp(Opcode, LHS, RHS, TD, MaxRecursionDepth);
666 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
668 static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
669 const TargetData *TD, unsigned MaxRecurse) {
670 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
671 return SimplifyICmpInst(Predicate, LHS, RHS, TD, MaxRecurse);
672 return SimplifyFCmpInst(Predicate, LHS, RHS, TD, MaxRecurse);
675 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
676 const TargetData *TD) {
677 return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, MaxRecursionDepth);
680 /// SimplifyInstruction - See if we can compute a simplified version of this
681 /// instruction. If not, this returns null.
682 Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD,
683 const DominatorTree *DT) {
684 switch (I->getOpcode()) {
686 return ConstantFoldInstruction(I, TD);
687 case Instruction::Add:
688 return SimplifyAddInst(I->getOperand(0), I->getOperand(1),
689 cast<BinaryOperator>(I)->hasNoSignedWrap(),
690 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), TD);
691 case Instruction::And:
692 return SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD);
693 case Instruction::Or:
694 return SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD);
695 case Instruction::ICmp:
696 return SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
697 I->getOperand(0), I->getOperand(1), TD);
698 case Instruction::FCmp:
699 return SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
700 I->getOperand(0), I->getOperand(1), TD);
701 case Instruction::Select:
702 return SimplifySelectInst(I->getOperand(0), I->getOperand(1),
703 I->getOperand(2), TD);
704 case Instruction::GetElementPtr: {
705 SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
706 return SimplifyGEPInst(&Ops[0], Ops.size(), TD);
708 case Instruction::PHI:
709 return cast<PHINode>(I)->hasConstantValue(DT);
713 /// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
714 /// delete the From instruction. In addition to a basic RAUW, this does a
715 /// recursive simplification of the newly formed instructions. This catches
716 /// things where one simplification exposes other opportunities. This only
717 /// simplifies and deletes scalar operations, it does not change the CFG.
719 void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
720 const TargetData *TD,
721 const DominatorTree *DT) {
722 assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!");
724 // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that
725 // we can know if it gets deleted out from under us or replaced in a
726 // recursive simplification.
727 WeakVH FromHandle(From);
730 while (!From->use_empty()) {
731 // Update the instruction to use the new value.
732 Use &TheUse = From->use_begin().getUse();
733 Instruction *User = cast<Instruction>(TheUse.getUser());
736 // Check to see if the instruction can be folded due to the operand
737 // replacement. For example changing (or X, Y) into (or X, -1) can replace
739 Value *SimplifiedVal;
741 // Sanity check to make sure 'User' doesn't dangle across
742 // SimplifyInstruction.
743 AssertingVH<> UserHandle(User);
745 SimplifiedVal = SimplifyInstruction(User, TD, DT);
746 if (SimplifiedVal == 0) continue;
749 // Recursively simplify this user to the new value.
750 ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT);
751 From = dyn_cast_or_null<Instruction>((Value*)FromHandle);
754 assert(ToHandle && "To value deleted by recursive simplification?");
756 // If the recursive simplification ended up revisiting and deleting
757 // 'From' then we're done.
762 // If 'From' has value handles referring to it, do a real RAUW to update them.
763 From->replaceAllUsesWith(To);
765 From->eraseFromParent();