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/Analysis/Dominators.h"
19 #include "llvm/Support/PatternMatch.h"
20 #include "llvm/Support/ValueHandle.h"
22 using namespace llvm::PatternMatch;
24 #define RecursionLimit 3
26 static Value *SimplifyBinOp(unsigned, Value *, Value *, const TargetData *,
27 const DominatorTree *, unsigned);
28 static Value *SimplifyCmpInst(unsigned, Value *, Value *, const TargetData *,
29 const DominatorTree *, unsigned);
31 /// ValueDominatesPHI - Does the given value dominate the specified phi node?
32 static bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
33 Instruction *I = dyn_cast<Instruction>(V);
35 // Arguments and constants dominate all instructions.
38 // If we have a DominatorTree then do a precise test.
40 return DT->dominates(I, P);
42 // Otherwise, if the instruction is in the entry block, and is not an invoke,
43 // then it obviously dominates all phi nodes.
44 if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() &&
51 /// ThreadBinOpOverSelect - In the case of a binary operation with a select
52 /// instruction as an operand, try to simplify the binop by seeing whether
53 /// evaluating it on both branches of the select results in the same value.
54 /// Returns the common value if so, otherwise returns null.
55 static Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS,
57 const DominatorTree *DT,
58 unsigned MaxRecurse) {
60 if (isa<SelectInst>(LHS)) {
61 SI = cast<SelectInst>(LHS);
63 assert(isa<SelectInst>(RHS) && "No select instruction operand!");
64 SI = cast<SelectInst>(RHS);
67 // Evaluate the BinOp on the true and false branches of the select.
71 TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, DT, MaxRecurse);
72 FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, DT, MaxRecurse);
74 TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, DT, MaxRecurse);
75 FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, DT, MaxRecurse);
78 // If they simplified to the same value, then return the common value.
79 // If they both failed to simplify then return null.
83 // If one branch simplified to undef, return the other one.
84 if (TV && isa<UndefValue>(TV))
86 if (FV && isa<UndefValue>(FV))
89 // If applying the operation did not change the true and false select values,
90 // then the result of the binop is the select itself.
91 if (TV == SI->getTrueValue() && FV == SI->getFalseValue())
94 // If one branch simplified and the other did not, and the simplified
95 // value is equal to the unsimplified one, return the simplified value.
96 // For example, select (cond, X, X & Z) & Z -> X & Z.
97 if ((FV && !TV) || (TV && !FV)) {
98 // Check that the simplified value has the form "X op Y" where "op" is the
99 // same as the original operation.
100 Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV);
101 if (Simplified && Simplified->getOpcode() == Opcode) {
102 // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS".
103 // We already know that "op" is the same as for the simplified value. See
104 // if the operands match too. If so, return the simplified value.
105 Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue();
106 Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS;
107 Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch;
108 if (Simplified->getOperand(0) == UnsimplifiedLHS &&
109 Simplified->getOperand(1) == UnsimplifiedRHS)
111 if (Simplified->isCommutative() &&
112 Simplified->getOperand(1) == UnsimplifiedLHS &&
113 Simplified->getOperand(0) == UnsimplifiedRHS)
121 /// ThreadCmpOverSelect - In the case of a comparison with a select instruction,
122 /// try to simplify the comparison by seeing whether both branches of the select
123 /// result in the same value. Returns the common value if so, otherwise returns
125 static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS,
126 Value *RHS, const TargetData *TD,
127 const DominatorTree *DT,
128 unsigned MaxRecurse) {
129 // Make sure the select is on the LHS.
130 if (!isa<SelectInst>(LHS)) {
132 Pred = CmpInst::getSwappedPredicate(Pred);
134 assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!");
135 SelectInst *SI = cast<SelectInst>(LHS);
137 // Now that we have "cmp select(cond, TV, FV), RHS", analyse it.
138 // Does "cmp TV, RHS" simplify?
139 if (Value *TCmp = SimplifyCmpInst(Pred, SI->getTrueValue(), RHS, TD, DT,
141 // It does! Does "cmp FV, RHS" simplify?
142 if (Value *FCmp = SimplifyCmpInst(Pred, SI->getFalseValue(), RHS, TD, DT,
144 // It does! If they simplified to the same value, then use it as the
145 // result of the original comparison.
151 /// ThreadBinOpOverPHI - In the case of a binary operation with an operand that
152 /// is a PHI instruction, try to simplify the binop by seeing whether evaluating
153 /// it on the incoming phi values yields the same result for every value. If so
154 /// returns the common value, otherwise returns null.
155 static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS,
156 const TargetData *TD, const DominatorTree *DT,
157 unsigned MaxRecurse) {
159 if (isa<PHINode>(LHS)) {
160 PI = cast<PHINode>(LHS);
161 // Bail out if RHS and the phi may be mutually interdependent due to a loop.
162 if (!ValueDominatesPHI(RHS, PI, DT))
165 assert(isa<PHINode>(RHS) && "No PHI instruction operand!");
166 PI = cast<PHINode>(RHS);
167 // Bail out if LHS and the phi may be mutually interdependent due to a loop.
168 if (!ValueDominatesPHI(LHS, PI, DT))
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 *Incoming = PI->getIncomingValue(i);
176 // If the incoming value is the phi node itself, it can safely be skipped.
177 if (Incoming == PI) continue;
178 Value *V = PI == LHS ?
179 SimplifyBinOp(Opcode, Incoming, RHS, TD, DT, MaxRecurse) :
180 SimplifyBinOp(Opcode, LHS, Incoming, TD, DT, MaxRecurse);
181 // If the operation failed to simplify, or simplified to a different value
182 // to previously, then give up.
183 if (!V || (CommonValue && V != CommonValue))
191 /// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try
192 /// try to simplify the comparison by seeing whether comparing with all of the
193 /// incoming phi values yields the same result every time. If so returns the
194 /// common result, otherwise returns null.
195 static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
196 const TargetData *TD, const DominatorTree *DT,
197 unsigned MaxRecurse) {
198 // Make sure the phi is on the LHS.
199 if (!isa<PHINode>(LHS)) {
201 Pred = CmpInst::getSwappedPredicate(Pred);
203 assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!");
204 PHINode *PI = cast<PHINode>(LHS);
206 // Bail out if RHS and the phi may be mutually interdependent due to a loop.
207 if (!ValueDominatesPHI(RHS, PI, DT))
210 // Evaluate the BinOp on the incoming phi values.
211 Value *CommonValue = 0;
212 for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
213 Value *Incoming = PI->getIncomingValue(i);
214 // If the incoming value is the phi node itself, it can safely be skipped.
215 if (Incoming == PI) continue;
216 Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, DT, MaxRecurse);
217 // If the operation failed to simplify, or simplified to a different value
218 // to previously, then give up.
219 if (!V || (CommonValue && V != CommonValue))
227 /// SimplifyAddInst - Given operands for an Add, see if we can
228 /// fold the result. If not, this returns null.
229 Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
230 const TargetData *TD, const DominatorTree *) {
231 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
232 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
233 Constant *Ops[] = { CLHS, CRHS };
234 return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(),
238 // Canonicalize the constant to the RHS.
242 if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
243 // X + undef -> undef
244 if (isa<UndefValue>(Op1C))
248 if (Op1C->isNullValue())
252 // FIXME: Could pull several more out of instcombine.
256 /// SimplifyAndInst - Given operands for an And, see if we can
257 /// fold the result. If not, this returns null.
258 static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
259 const DominatorTree *DT, unsigned MaxRecurse) {
260 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
261 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
262 Constant *Ops[] = { CLHS, CRHS };
263 return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
267 // Canonicalize the constant to the RHS.
272 if (isa<UndefValue>(Op1))
273 return Constant::getNullValue(Op0->getType());
280 if (match(Op1, m_Zero()))
284 if (match(Op1, m_AllOnes()))
287 // A & ~A = ~A & A = 0
289 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
290 (match(Op1, m_Not(m_Value(A))) && A == Op0))
291 return Constant::getNullValue(Op0->getType());
294 if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
295 (A == Op1 || B == Op1))
299 if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
300 (A == Op0 || B == Op0))
303 // (A & B) & A -> A & B
304 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
305 (A == Op1 || B == Op1))
308 // A & (A & B) -> A & B
309 if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
310 (A == Op0 || B == Op0))
313 // If the operation is with the result of a select instruction, check whether
314 // operating on either branch of the select always yields the same value.
315 if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
316 if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, DT,
320 // If the operation is with the result of a phi instruction, check whether
321 // operating on all incoming values of the phi always yields the same value.
322 if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
323 if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, DT,
330 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
331 const DominatorTree *DT) {
332 return ::SimplifyAndInst(Op0, Op1, TD, DT, RecursionLimit);
335 /// SimplifyOrInst - Given operands for an Or, see if we can
336 /// fold the result. If not, this returns null.
337 static Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
338 const DominatorTree *DT, unsigned MaxRecurse) {
339 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
340 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
341 Constant *Ops[] = { CLHS, CRHS };
342 return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
346 // Canonicalize the constant to the RHS.
351 if (isa<UndefValue>(Op1))
352 return Constant::getAllOnesValue(Op0->getType());
359 if (match(Op1, m_Zero()))
363 if (match(Op1, m_AllOnes()))
366 // A | ~A = ~A | A = -1
368 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
369 (match(Op1, m_Not(m_Value(A))) && A == Op0))
370 return Constant::getAllOnesValue(Op0->getType());
373 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
374 (A == Op1 || B == Op1))
378 if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
379 (A == Op0 || B == Op0))
382 // (A | B) | A -> A | B
383 if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
384 (A == Op1 || B == Op1))
387 // A | (A | B) -> A | B
388 if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
389 (A == Op0 || B == Op0))
392 // If the operation is with the result of a select instruction, check whether
393 // operating on either branch of the select always yields the same value.
394 if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
395 if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT,
399 // If the operation is with the result of a phi instruction, check whether
400 // operating on all incoming values of the phi always yields the same value.
401 if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
402 if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT,
409 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
410 const DominatorTree *DT) {
411 return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit);
414 /// SimplifyXorInst - Given operands for a Xor, see if we can
415 /// fold the result. If not, this returns null.
416 static Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
417 const DominatorTree *DT, unsigned MaxRecurse) {
418 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
419 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
420 Constant *Ops[] = { CLHS, CRHS };
421 return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(),
425 // Canonicalize the constant to the RHS.
429 // A ^ undef -> undef
430 if (isa<UndefValue>(Op1))
431 return UndefValue::get(Op0->getType());
434 if (match(Op1, m_Zero()))
439 return Constant::getNullValue(Op0->getType());
441 // A ^ ~A = ~A ^ A = -1
443 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
444 (match(Op1, m_Not(m_Value(A))) && A == Op0))
445 return Constant::getAllOnesValue(Op0->getType());
448 if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
449 (A == Op1 || B == Op1))
450 return A == Op1 ? B : A;
453 if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
454 (A == Op0 || B == Op0))
455 return A == Op0 ? B : A;
457 // If the operation is with the result of a select instruction, check whether
458 // operating on either branch of the select always yields the same value.
459 if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
460 if (Value *V = ThreadBinOpOverSelect(Instruction::Xor, Op0, Op1, TD, DT,
464 // If the operation is with the result of a phi instruction, check whether
465 // operating on all incoming values of the phi always yields the same value.
466 if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
467 if (Value *V = ThreadBinOpOverPHI(Instruction::Xor, Op0, Op1, TD, DT,
474 Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
475 const DominatorTree *DT) {
476 return ::SimplifyXorInst(Op0, Op1, TD, DT, RecursionLimit);
479 static const Type *GetCompareTy(Value *Op) {
480 return CmpInst::makeCmpResultType(Op->getType());
483 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
484 /// fold the result. If not, this returns null.
485 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
486 const TargetData *TD, const DominatorTree *DT,
487 unsigned MaxRecurse) {
488 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
489 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
491 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
492 if (Constant *CRHS = dyn_cast<Constant>(RHS))
493 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
495 // If we have a constant, make sure it is on the RHS.
497 Pred = CmpInst::getSwappedPredicate(Pred);
500 // ITy - This is the return type of the compare we're considering.
501 const Type *ITy = GetCompareTy(LHS);
503 // icmp X, X -> true/false
504 // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false
505 // because X could be 0.
506 if (LHS == RHS || isa<UndefValue>(RHS))
507 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
509 // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
510 // addresses never equal each other! We already know that Op0 != Op1.
511 if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) ||
512 isa<ConstantPointerNull>(LHS)) &&
513 (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) ||
514 isa<ConstantPointerNull>(RHS)))
515 return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
517 // See if we are doing a comparison with a constant.
518 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
519 // If we have an icmp le or icmp ge instruction, turn it into the
520 // appropriate icmp lt or icmp gt instruction. This allows us to rely on
521 // them being folded in the code below.
524 case ICmpInst::ICMP_ULE:
525 if (CI->isMaxValue(false)) // A <=u MAX -> TRUE
526 return ConstantInt::getTrue(CI->getContext());
528 case ICmpInst::ICMP_SLE:
529 if (CI->isMaxValue(true)) // A <=s MAX -> TRUE
530 return ConstantInt::getTrue(CI->getContext());
532 case ICmpInst::ICMP_UGE:
533 if (CI->isMinValue(false)) // A >=u MIN -> TRUE
534 return ConstantInt::getTrue(CI->getContext());
536 case ICmpInst::ICMP_SGE:
537 if (CI->isMinValue(true)) // A >=s MIN -> TRUE
538 return ConstantInt::getTrue(CI->getContext());
543 // If the comparison is with the result of a select instruction, check whether
544 // comparing with either branch of the select always yields the same value.
545 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
546 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
549 // If the comparison is with the result of a phi instruction, check whether
550 // doing the compare with each incoming phi value yields a common result.
551 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
552 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
558 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
559 const TargetData *TD, const DominatorTree *DT) {
560 return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
563 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
564 /// fold the result. If not, this returns null.
565 static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
566 const TargetData *TD, const DominatorTree *DT,
567 unsigned MaxRecurse) {
568 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
569 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
571 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
572 if (Constant *CRHS = dyn_cast<Constant>(RHS))
573 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
575 // If we have a constant, make sure it is on the RHS.
577 Pred = CmpInst::getSwappedPredicate(Pred);
580 // Fold trivial predicates.
581 if (Pred == FCmpInst::FCMP_FALSE)
582 return ConstantInt::get(GetCompareTy(LHS), 0);
583 if (Pred == FCmpInst::FCMP_TRUE)
584 return ConstantInt::get(GetCompareTy(LHS), 1);
586 if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef
587 return UndefValue::get(GetCompareTy(LHS));
589 // fcmp x,x -> true/false. Not all compares are foldable.
591 if (CmpInst::isTrueWhenEqual(Pred))
592 return ConstantInt::get(GetCompareTy(LHS), 1);
593 if (CmpInst::isFalseWhenEqual(Pred))
594 return ConstantInt::get(GetCompareTy(LHS), 0);
597 // Handle fcmp with constant RHS
598 if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
599 // If the constant is a nan, see if we can fold the comparison based on it.
600 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
601 if (CFP->getValueAPF().isNaN()) {
602 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo"
603 return ConstantInt::getFalse(CFP->getContext());
604 assert(FCmpInst::isUnordered(Pred) &&
605 "Comparison must be either ordered or unordered!");
606 // True if unordered.
607 return ConstantInt::getTrue(CFP->getContext());
609 // Check whether the constant is an infinity.
610 if (CFP->getValueAPF().isInfinity()) {
611 if (CFP->getValueAPF().isNegative()) {
613 case FCmpInst::FCMP_OLT:
614 // No value is ordered and less than negative infinity.
615 return ConstantInt::getFalse(CFP->getContext());
616 case FCmpInst::FCMP_UGE:
617 // All values are unordered with or at least negative infinity.
618 return ConstantInt::getTrue(CFP->getContext());
624 case FCmpInst::FCMP_OGT:
625 // No value is ordered and greater than infinity.
626 return ConstantInt::getFalse(CFP->getContext());
627 case FCmpInst::FCMP_ULE:
628 // All values are unordered with and at most infinity.
629 return ConstantInt::getTrue(CFP->getContext());
638 // If the comparison is with the result of a select instruction, check whether
639 // comparing with either branch of the select always yields the same value.
640 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
641 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
644 // If the comparison is with the result of a phi instruction, check whether
645 // doing the compare with each incoming phi value yields a common result.
646 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
647 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
653 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
654 const TargetData *TD, const DominatorTree *DT) {
655 return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
658 /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
659 /// the result. If not, this returns null.
660 Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal,
661 const TargetData *TD, const DominatorTree *) {
662 // select true, X, Y -> X
663 // select false, X, Y -> Y
664 if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal))
665 return CB->getZExtValue() ? TrueVal : FalseVal;
667 // select C, X, X -> X
668 if (TrueVal == FalseVal)
671 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X
673 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X
675 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y
676 if (isa<Constant>(TrueVal))
684 /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
685 /// fold the result. If not, this returns null.
686 Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps,
687 const TargetData *TD, const DominatorTree *) {
688 // getelementptr P -> P.
693 //if (isa<UndefValue>(Ops[0]))
694 // return UndefValue::get(GEP.getType());
696 // getelementptr P, 0 -> P.
698 if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
702 // Check to see if this is constant foldable.
703 for (unsigned i = 0; i != NumOps; ++i)
704 if (!isa<Constant>(Ops[i]))
707 return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]),
708 (Constant *const*)Ops+1, NumOps-1);
711 /// SimplifyPHINode - See if we can fold the given phi. If not, returns null.
712 static Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) {
713 // If all of the PHI's incoming values are the same then replace the PHI node
714 // with the common value.
715 Value *CommonValue = 0;
716 bool HasUndefInput = false;
717 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
718 Value *Incoming = PN->getIncomingValue(i);
719 // If the incoming value is the phi node itself, it can safely be skipped.
720 if (Incoming == PN) continue;
721 if (isa<UndefValue>(Incoming)) {
722 // Remember that we saw an undef value, but otherwise ignore them.
723 HasUndefInput = true;
726 if (CommonValue && Incoming != CommonValue)
727 return 0; // Not the same, bail out.
728 CommonValue = Incoming;
731 // If CommonValue is null then all of the incoming values were either undef or
732 // equal to the phi node itself.
734 return UndefValue::get(PN->getType());
736 // If we have a PHI node like phi(X, undef, X), where X is defined by some
737 // instruction, we cannot return X as the result of the PHI node unless it
738 // dominates the PHI block.
740 return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0;
746 //=== Helper functions for higher up the class hierarchy.
748 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
749 /// fold the result. If not, this returns null.
750 static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
751 const TargetData *TD, const DominatorTree *DT,
752 unsigned MaxRecurse) {
754 case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse);
755 case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD, DT, MaxRecurse);
757 if (Constant *CLHS = dyn_cast<Constant>(LHS))
758 if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
759 Constant *COps[] = {CLHS, CRHS};
760 return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD);
763 // If the operation is with the result of a select instruction, check whether
764 // operating on either branch of the select always yields the same value.
765 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
766 if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT,
770 // If the operation is with the result of a phi instruction, check whether
771 // operating on all incoming values of the phi always yields the same value.
772 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
773 if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse-1))
780 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
781 const TargetData *TD, const DominatorTree *DT) {
782 return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit);
785 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
787 static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
788 const TargetData *TD, const DominatorTree *DT,
789 unsigned MaxRecurse) {
790 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
791 return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
792 return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
795 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
796 const TargetData *TD, const DominatorTree *DT) {
797 return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
800 /// SimplifyInstruction - See if we can compute a simplified version of this
801 /// instruction. If not, this returns null.
802 Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD,
803 const DominatorTree *DT) {
806 switch (I->getOpcode()) {
808 Result = ConstantFoldInstruction(I, TD);
810 case Instruction::Add:
811 Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1),
812 cast<BinaryOperator>(I)->hasNoSignedWrap(),
813 cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
816 case Instruction::And:
817 Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT);
819 case Instruction::Or:
820 Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT);
822 case Instruction::Xor:
823 Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT);
825 case Instruction::ICmp:
826 Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
827 I->getOperand(0), I->getOperand(1), TD, DT);
829 case Instruction::FCmp:
830 Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
831 I->getOperand(0), I->getOperand(1), TD, DT);
833 case Instruction::Select:
834 Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1),
835 I->getOperand(2), TD, DT);
837 case Instruction::GetElementPtr: {
838 SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
839 Result = SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT);
842 case Instruction::PHI:
843 Result = SimplifyPHINode(cast<PHINode>(I), DT);
847 /// If called on unreachable code, the above logic may report that the
848 /// instruction simplified to itself. Make life easier for users by
849 /// detecting that case here, returning null if it occurs.
850 return Result == I ? 0 : Result;
853 /// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
854 /// delete the From instruction. In addition to a basic RAUW, this does a
855 /// recursive simplification of the newly formed instructions. This catches
856 /// things where one simplification exposes other opportunities. This only
857 /// simplifies and deletes scalar operations, it does not change the CFG.
859 void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
860 const TargetData *TD,
861 const DominatorTree *DT) {
862 assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!");
864 // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that
865 // we can know if it gets deleted out from under us or replaced in a
866 // recursive simplification.
867 WeakVH FromHandle(From);
870 while (!From->use_empty()) {
871 // Update the instruction to use the new value.
872 Use &TheUse = From->use_begin().getUse();
873 Instruction *User = cast<Instruction>(TheUse.getUser());
876 // Check to see if the instruction can be folded due to the operand
877 // replacement. For example changing (or X, Y) into (or X, -1) can replace
879 Value *SimplifiedVal;
881 // Sanity check to make sure 'User' doesn't dangle across
882 // SimplifyInstruction.
883 AssertingVH<> UserHandle(User);
885 SimplifiedVal = SimplifyInstruction(User, TD, DT);
886 if (SimplifiedVal == 0) continue;
889 // Recursively simplify this user to the new value.
890 ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT);
891 From = dyn_cast_or_null<Instruction>((Value*)FromHandle);
894 assert(ToHandle && "To value deleted by recursive simplification?");
896 // If the recursive simplification ended up revisiting and deleting
897 // 'From' then we're done.
902 // If 'From' has value handles referring to it, do a real RAUW to update them.
903 From->replaceAllUsesWith(To);
905 From->eraseFromParent();