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"
21 #include "llvm/Target/TargetData.h"
23 using namespace llvm::PatternMatch;
25 #define RecursionLimit 3
27 static Value *SimplifyBinOp(unsigned, Value *, Value *, const TargetData *,
28 const DominatorTree *, unsigned);
29 static Value *SimplifyCmpInst(unsigned, Value *, Value *, const TargetData *,
30 const DominatorTree *, unsigned);
32 /// ValueDominatesPHI - Does the given value dominate the specified phi node?
33 static bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
34 Instruction *I = dyn_cast<Instruction>(V);
36 // Arguments and constants dominate all instructions.
39 // If we have a DominatorTree then do a precise test.
41 return DT->dominates(I, P);
43 // Otherwise, if the instruction is in the entry block, and is not an invoke,
44 // then it obviously dominates all phi nodes.
45 if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() &&
52 /// ThreadBinOpOverSelect - In the case of a binary operation with a select
53 /// instruction as an operand, try to simplify the binop by seeing whether
54 /// evaluating it on both branches of the select results in the same value.
55 /// Returns the common value if so, otherwise returns null.
56 static Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS,
58 const DominatorTree *DT,
59 unsigned MaxRecurse) {
61 if (isa<SelectInst>(LHS)) {
62 SI = cast<SelectInst>(LHS);
64 assert(isa<SelectInst>(RHS) && "No select instruction operand!");
65 SI = cast<SelectInst>(RHS);
68 // Evaluate the BinOp on the true and false branches of the select.
72 TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, DT, MaxRecurse);
73 FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, DT, MaxRecurse);
75 TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, DT, MaxRecurse);
76 FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, DT, MaxRecurse);
79 // If they simplified to the same value, then return the common value.
80 // If they both failed to simplify then return null.
84 // If one branch simplified to undef, return the other one.
85 if (TV && isa<UndefValue>(TV))
87 if (FV && isa<UndefValue>(FV))
90 // If applying the operation did not change the true and false select values,
91 // then the result of the binop is the select itself.
92 if (TV == SI->getTrueValue() && FV == SI->getFalseValue())
95 // If one branch simplified and the other did not, and the simplified
96 // value is equal to the unsimplified one, return the simplified value.
97 // For example, select (cond, X, X & Z) & Z -> X & Z.
98 if ((FV && !TV) || (TV && !FV)) {
99 // Check that the simplified value has the form "X op Y" where "op" is the
100 // same as the original operation.
101 Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV);
102 if (Simplified && Simplified->getOpcode() == Opcode) {
103 // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS".
104 // We already know that "op" is the same as for the simplified value. See
105 // if the operands match too. If so, return the simplified value.
106 Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue();
107 Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS;
108 Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch;
109 if (Simplified->getOperand(0) == UnsimplifiedLHS &&
110 Simplified->getOperand(1) == UnsimplifiedRHS)
112 if (Simplified->isCommutative() &&
113 Simplified->getOperand(1) == UnsimplifiedLHS &&
114 Simplified->getOperand(0) == UnsimplifiedRHS)
122 /// ThreadCmpOverSelect - In the case of a comparison with a select instruction,
123 /// try to simplify the comparison by seeing whether both branches of the select
124 /// result in the same value. Returns the common value if so, otherwise returns
126 static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS,
127 Value *RHS, const TargetData *TD,
128 const DominatorTree *DT,
129 unsigned MaxRecurse) {
130 // Make sure the select is on the LHS.
131 if (!isa<SelectInst>(LHS)) {
133 Pred = CmpInst::getSwappedPredicate(Pred);
135 assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!");
136 SelectInst *SI = cast<SelectInst>(LHS);
138 // Now that we have "cmp select(cond, TV, FV), RHS", analyse it.
139 // Does "cmp TV, RHS" simplify?
140 if (Value *TCmp = SimplifyCmpInst(Pred, SI->getTrueValue(), RHS, TD, DT,
142 // It does! Does "cmp FV, RHS" simplify?
143 if (Value *FCmp = SimplifyCmpInst(Pred, SI->getFalseValue(), RHS, TD, DT,
145 // It does! If they simplified to the same value, then use it as the
146 // result of the original comparison.
152 /// ThreadBinOpOverPHI - In the case of a binary operation with an operand that
153 /// is a PHI instruction, try to simplify the binop by seeing whether evaluating
154 /// it on the incoming phi values yields the same result for every value. If so
155 /// returns the common value, otherwise returns null.
156 static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS,
157 const TargetData *TD, const DominatorTree *DT,
158 unsigned MaxRecurse) {
160 if (isa<PHINode>(LHS)) {
161 PI = cast<PHINode>(LHS);
162 // Bail out if RHS and the phi may be mutually interdependent due to a loop.
163 if (!ValueDominatesPHI(RHS, PI, DT))
166 assert(isa<PHINode>(RHS) && "No PHI instruction operand!");
167 PI = cast<PHINode>(RHS);
168 // Bail out if LHS and the phi may be mutually interdependent due to a loop.
169 if (!ValueDominatesPHI(LHS, PI, DT))
173 // Evaluate the BinOp on the incoming phi values.
174 Value *CommonValue = 0;
175 for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
176 Value *Incoming = PI->getIncomingValue(i);
177 // If the incoming value is the phi node itself, it can safely be skipped.
178 if (Incoming == PI) continue;
179 Value *V = PI == LHS ?
180 SimplifyBinOp(Opcode, Incoming, RHS, TD, DT, MaxRecurse) :
181 SimplifyBinOp(Opcode, LHS, Incoming, TD, DT, 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 /// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try
193 /// try to simplify the comparison by seeing whether comparing with all of the
194 /// incoming phi values yields the same result every time. If so returns the
195 /// common result, otherwise returns null.
196 static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
197 const TargetData *TD, const DominatorTree *DT,
198 unsigned MaxRecurse) {
199 // Make sure the phi is on the LHS.
200 if (!isa<PHINode>(LHS)) {
202 Pred = CmpInst::getSwappedPredicate(Pred);
204 assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!");
205 PHINode *PI = cast<PHINode>(LHS);
207 // Bail out if RHS and the phi may be mutually interdependent due to a loop.
208 if (!ValueDominatesPHI(RHS, PI, DT))
211 // Evaluate the BinOp on the incoming phi values.
212 Value *CommonValue = 0;
213 for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
214 Value *Incoming = PI->getIncomingValue(i);
215 // If the incoming value is the phi node itself, it can safely be skipped.
216 if (Incoming == PI) continue;
217 Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, DT, MaxRecurse);
218 // If the operation failed to simplify, or simplified to a different value
219 // to previously, then give up.
220 if (!V || (CommonValue && V != CommonValue))
228 /// SimplifyAddInst - Given operands for an Add, see if we can
229 /// fold the result. If not, this returns null.
230 Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
231 const TargetData *TD, const DominatorTree *) {
232 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
233 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
234 Constant *Ops[] = { CLHS, CRHS };
235 return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(),
239 // Canonicalize the constant to the RHS.
243 if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
244 // X + undef -> undef
245 if (isa<UndefValue>(Op1C))
249 if (Op1C->isNullValue())
253 // FIXME: Could pull several more out of instcombine.
255 // Threading Add over selects and phi nodes is pointless, so don't bother.
256 // Threading over the select in "A + select(cond, B, C)" means evaluating
257 // "A+B" and "A+C" and seeing if they are equal; but they are equal if and
258 // only if B and C are equal. If B and C are equal then (since we assume
259 // that operands have already been simplified) "select(cond, B, C)" should
260 // have been simplified to the common value of B and C already. Analysing
261 // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly
262 // for threading over phi nodes.
267 /// SimplifyAndInst - Given operands for an And, see if we can
268 /// fold the result. If not, this returns null.
269 static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
270 const DominatorTree *DT, unsigned MaxRecurse) {
271 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
272 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
273 Constant *Ops[] = { CLHS, CRHS };
274 return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
278 // Canonicalize the constant to the RHS.
283 if (isa<UndefValue>(Op1))
284 return Constant::getNullValue(Op0->getType());
291 if (match(Op1, m_Zero()))
295 if (match(Op1, m_AllOnes()))
298 // A & ~A = ~A & A = 0
300 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
301 (match(Op1, m_Not(m_Value(A))) && A == Op0))
302 return Constant::getNullValue(Op0->getType());
305 if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
306 (A == Op1 || B == Op1))
310 if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
311 (A == Op0 || B == Op0))
314 // (A & B) & A -> A & B
315 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
316 (A == Op1 || B == Op1))
319 // A & (A & B) -> A & B
320 if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
321 (A == Op0 || B == Op0))
324 // If the operation is with the result of a select instruction, check whether
325 // operating on either branch of the select always yields the same value.
326 if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
327 if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, DT,
331 // If the operation is with the result of a phi instruction, check whether
332 // operating on all incoming values of the phi always yields the same value.
333 if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
334 if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, DT,
341 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
342 const DominatorTree *DT) {
343 return ::SimplifyAndInst(Op0, Op1, TD, DT, RecursionLimit);
346 /// SimplifyOrInst - Given operands for an Or, see if we can
347 /// fold the result. If not, this returns null.
348 static Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
349 const DominatorTree *DT, unsigned MaxRecurse) {
350 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
351 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
352 Constant *Ops[] = { CLHS, CRHS };
353 return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
357 // Canonicalize the constant to the RHS.
362 if (isa<UndefValue>(Op1))
363 return Constant::getAllOnesValue(Op0->getType());
370 if (match(Op1, m_Zero()))
374 if (match(Op1, m_AllOnes()))
377 // A | ~A = ~A | A = -1
379 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
380 (match(Op1, m_Not(m_Value(A))) && A == Op0))
381 return Constant::getAllOnesValue(Op0->getType());
384 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
385 (A == Op1 || B == Op1))
389 if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
390 (A == Op0 || B == Op0))
393 // (A | B) | A -> A | B
394 if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
395 (A == Op1 || B == Op1))
398 // A | (A | B) -> A | B
399 if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
400 (A == Op0 || B == Op0))
403 // If the operation is with the result of a select instruction, check whether
404 // operating on either branch of the select always yields the same value.
405 if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
406 if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT,
410 // If the operation is with the result of a phi instruction, check whether
411 // operating on all incoming values of the phi always yields the same value.
412 if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
413 if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT,
420 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
421 const DominatorTree *DT) {
422 return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit);
425 /// SimplifyXorInst - Given operands for a Xor, see if we can
426 /// fold the result. If not, this returns null.
427 static Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
428 const DominatorTree *DT, unsigned MaxRecurse) {
429 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
430 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
431 Constant *Ops[] = { CLHS, CRHS };
432 return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(),
436 // Canonicalize the constant to the RHS.
440 // A ^ undef -> undef
441 if (isa<UndefValue>(Op1))
442 return UndefValue::get(Op0->getType());
445 if (match(Op1, m_Zero()))
450 return Constant::getNullValue(Op0->getType());
452 // A ^ ~A = ~A ^ A = -1
454 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
455 (match(Op1, m_Not(m_Value(A))) && A == Op0))
456 return Constant::getAllOnesValue(Op0->getType());
459 if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
460 (A == Op1 || B == Op1))
461 return A == Op1 ? B : A;
464 if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
465 (A == Op0 || B == Op0))
466 return A == Op0 ? B : A;
468 // Threading Xor over selects and phi nodes is pointless, so don't bother.
469 // Threading over the select in "A ^ select(cond, B, C)" means evaluating
470 // "A^B" and "A^C" and seeing if they are equal; but they are equal if and
471 // only if B and C are equal. If B and C are equal then (since we assume
472 // that operands have already been simplified) "select(cond, B, C)" should
473 // have been simplified to the common value of B and C already. Analysing
474 // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly
475 // for threading over phi nodes.
480 Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
481 const DominatorTree *DT) {
482 return ::SimplifyXorInst(Op0, Op1, TD, DT, RecursionLimit);
485 static const Type *GetCompareTy(Value *Op) {
486 return CmpInst::makeCmpResultType(Op->getType());
489 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
490 /// fold the result. If not, this returns null.
491 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
492 const TargetData *TD, const DominatorTree *DT,
493 unsigned MaxRecurse) {
494 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
495 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
497 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
498 if (Constant *CRHS = dyn_cast<Constant>(RHS))
499 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
501 // If we have a constant, make sure it is on the RHS.
503 Pred = CmpInst::getSwappedPredicate(Pred);
506 // ITy - This is the return type of the compare we're considering.
507 const Type *ITy = GetCompareTy(LHS);
509 // icmp X, X -> true/false
510 // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false
511 // because X could be 0.
512 if (LHS == RHS || isa<UndefValue>(RHS))
513 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
515 // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
516 // addresses never equal each other! We already know that Op0 != Op1.
517 if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) ||
518 isa<ConstantPointerNull>(LHS)) &&
519 (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) ||
520 isa<ConstantPointerNull>(RHS)))
521 return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
523 // See if we are doing a comparison with a constant.
524 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
525 // If we have an icmp le or icmp ge instruction, turn it into the
526 // appropriate icmp lt or icmp gt instruction. This allows us to rely on
527 // them being folded in the code below.
530 case ICmpInst::ICMP_ULE:
531 if (CI->isMaxValue(false)) // A <=u MAX -> TRUE
532 return ConstantInt::getTrue(CI->getContext());
534 case ICmpInst::ICMP_SLE:
535 if (CI->isMaxValue(true)) // A <=s MAX -> TRUE
536 return ConstantInt::getTrue(CI->getContext());
538 case ICmpInst::ICMP_UGE:
539 if (CI->isMinValue(false)) // A >=u MIN -> TRUE
540 return ConstantInt::getTrue(CI->getContext());
542 case ICmpInst::ICMP_SGE:
543 if (CI->isMinValue(true)) // A >=s MIN -> TRUE
544 return ConstantInt::getTrue(CI->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, DT, 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, DT, MaxRecurse-1))
564 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
565 const TargetData *TD, const DominatorTree *DT) {
566 return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
569 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
570 /// fold the result. If not, this returns null.
571 static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
572 const TargetData *TD, const DominatorTree *DT,
573 unsigned MaxRecurse) {
574 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
575 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
577 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
578 if (Constant *CRHS = dyn_cast<Constant>(RHS))
579 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
581 // If we have a constant, make sure it is on the RHS.
583 Pred = CmpInst::getSwappedPredicate(Pred);
586 // Fold trivial predicates.
587 if (Pred == FCmpInst::FCMP_FALSE)
588 return ConstantInt::get(GetCompareTy(LHS), 0);
589 if (Pred == FCmpInst::FCMP_TRUE)
590 return ConstantInt::get(GetCompareTy(LHS), 1);
592 if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef
593 return UndefValue::get(GetCompareTy(LHS));
595 // fcmp x,x -> true/false. Not all compares are foldable.
597 if (CmpInst::isTrueWhenEqual(Pred))
598 return ConstantInt::get(GetCompareTy(LHS), 1);
599 if (CmpInst::isFalseWhenEqual(Pred))
600 return ConstantInt::get(GetCompareTy(LHS), 0);
603 // Handle fcmp with constant RHS
604 if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
605 // If the constant is a nan, see if we can fold the comparison based on it.
606 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
607 if (CFP->getValueAPF().isNaN()) {
608 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo"
609 return ConstantInt::getFalse(CFP->getContext());
610 assert(FCmpInst::isUnordered(Pred) &&
611 "Comparison must be either ordered or unordered!");
612 // True if unordered.
613 return ConstantInt::getTrue(CFP->getContext());
615 // Check whether the constant is an infinity.
616 if (CFP->getValueAPF().isInfinity()) {
617 if (CFP->getValueAPF().isNegative()) {
619 case FCmpInst::FCMP_OLT:
620 // No value is ordered and less than negative infinity.
621 return ConstantInt::getFalse(CFP->getContext());
622 case FCmpInst::FCMP_UGE:
623 // All values are unordered with or at least negative infinity.
624 return ConstantInt::getTrue(CFP->getContext());
630 case FCmpInst::FCMP_OGT:
631 // No value is ordered and greater than infinity.
632 return ConstantInt::getFalse(CFP->getContext());
633 case FCmpInst::FCMP_ULE:
634 // All values are unordered with and at most infinity.
635 return ConstantInt::getTrue(CFP->getContext());
644 // If the comparison is with the result of a select instruction, check whether
645 // comparing with either branch of the select always yields the same value.
646 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
647 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
650 // If the comparison is with the result of a phi instruction, check whether
651 // doing the compare with each incoming phi value yields a common result.
652 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
653 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
659 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
660 const TargetData *TD, const DominatorTree *DT) {
661 return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
664 /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
665 /// the result. If not, this returns null.
666 Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal,
667 const TargetData *TD, const DominatorTree *) {
668 // select true, X, Y -> X
669 // select false, X, Y -> Y
670 if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal))
671 return CB->getZExtValue() ? TrueVal : FalseVal;
673 // select C, X, X -> X
674 if (TrueVal == FalseVal)
677 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X
679 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X
681 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y
682 if (isa<Constant>(TrueVal))
690 /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
691 /// fold the result. If not, this returns null.
692 Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps,
693 const TargetData *TD, const DominatorTree *) {
694 // getelementptr P -> P.
699 //if (isa<UndefValue>(Ops[0]))
700 // return UndefValue::get(GEP.getType());
703 // getelementptr P, 0 -> P.
704 if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
707 // getelementptr P, N -> P if P points to a type of zero size.
709 const Type *Ty = cast<PointerType>(Ops[0]->getType())->getElementType();
710 if (Ty->isSized() && !TD->getTypeAllocSize(Ty))
715 // Check to see if this is constant foldable.
716 for (unsigned i = 0; i != NumOps; ++i)
717 if (!isa<Constant>(Ops[i]))
720 return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]),
721 (Constant *const*)Ops+1, NumOps-1);
724 /// SimplifyPHINode - See if we can fold the given phi. If not, returns null.
725 static Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) {
726 // If all of the PHI's incoming values are the same then replace the PHI node
727 // with the common value.
728 Value *CommonValue = 0;
729 bool HasUndefInput = false;
730 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
731 Value *Incoming = PN->getIncomingValue(i);
732 // If the incoming value is the phi node itself, it can safely be skipped.
733 if (Incoming == PN) continue;
734 if (isa<UndefValue>(Incoming)) {
735 // Remember that we saw an undef value, but otherwise ignore them.
736 HasUndefInput = true;
739 if (CommonValue && Incoming != CommonValue)
740 return 0; // Not the same, bail out.
741 CommonValue = Incoming;
744 // If CommonValue is null then all of the incoming values were either undef or
745 // equal to the phi node itself.
747 return UndefValue::get(PN->getType());
749 // If we have a PHI node like phi(X, undef, X), where X is defined by some
750 // instruction, we cannot return X as the result of the PHI node unless it
751 // dominates the PHI block.
753 return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0;
759 //=== Helper functions for higher up the class hierarchy.
761 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
762 /// fold the result. If not, this returns null.
763 static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
764 const TargetData *TD, const DominatorTree *DT,
765 unsigned MaxRecurse) {
767 case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse);
768 case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD, DT, MaxRecurse);
770 if (Constant *CLHS = dyn_cast<Constant>(LHS))
771 if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
772 Constant *COps[] = {CLHS, CRHS};
773 return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD);
776 // If the operation is with the result of a select instruction, check whether
777 // operating on either branch of the select always yields the same value.
778 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
779 if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT,
783 // If the operation is with the result of a phi instruction, check whether
784 // operating on all incoming values of the phi always yields the same value.
785 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
786 if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse-1))
793 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
794 const TargetData *TD, const DominatorTree *DT) {
795 return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit);
798 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
800 static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
801 const TargetData *TD, const DominatorTree *DT,
802 unsigned MaxRecurse) {
803 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
804 return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
805 return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
808 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
809 const TargetData *TD, const DominatorTree *DT) {
810 return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
813 /// SimplifyInstruction - See if we can compute a simplified version of this
814 /// instruction. If not, this returns null.
815 Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD,
816 const DominatorTree *DT) {
819 switch (I->getOpcode()) {
821 Result = ConstantFoldInstruction(I, TD);
823 case Instruction::Add:
824 Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1),
825 cast<BinaryOperator>(I)->hasNoSignedWrap(),
826 cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
829 case Instruction::And:
830 Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT);
832 case Instruction::Or:
833 Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT);
835 case Instruction::Xor:
836 Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT);
838 case Instruction::ICmp:
839 Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
840 I->getOperand(0), I->getOperand(1), TD, DT);
842 case Instruction::FCmp:
843 Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
844 I->getOperand(0), I->getOperand(1), TD, DT);
846 case Instruction::Select:
847 Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1),
848 I->getOperand(2), TD, DT);
850 case Instruction::GetElementPtr: {
851 SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
852 Result = SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT);
855 case Instruction::PHI:
856 Result = SimplifyPHINode(cast<PHINode>(I), DT);
860 /// If called on unreachable code, the above logic may report that the
861 /// instruction simplified to itself. Make life easier for users by
862 /// detecting that case here, returning null if it occurs.
863 return Result == I ? 0 : Result;
866 /// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
867 /// delete the From instruction. In addition to a basic RAUW, this does a
868 /// recursive simplification of the newly formed instructions. This catches
869 /// things where one simplification exposes other opportunities. This only
870 /// simplifies and deletes scalar operations, it does not change the CFG.
872 void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
873 const TargetData *TD,
874 const DominatorTree *DT) {
875 assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!");
877 // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that
878 // we can know if it gets deleted out from under us or replaced in a
879 // recursive simplification.
880 WeakVH FromHandle(From);
883 while (!From->use_empty()) {
884 // Update the instruction to use the new value.
885 Use &TheUse = From->use_begin().getUse();
886 Instruction *User = cast<Instruction>(TheUse.getUser());
889 // Check to see if the instruction can be folded due to the operand
890 // replacement. For example changing (or X, Y) into (or X, -1) can replace
892 Value *SimplifiedVal;
894 // Sanity check to make sure 'User' doesn't dangle across
895 // SimplifyInstruction.
896 AssertingVH<> UserHandle(User);
898 SimplifiedVal = SimplifyInstruction(User, TD, DT);
899 if (SimplifiedVal == 0) continue;
902 // Recursively simplify this user to the new value.
903 ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT);
904 From = dyn_cast_or_null<Instruction>((Value*)FromHandle);
907 assert(ToHandle && "To value deleted by recursive simplification?");
909 // If the recursive simplification ended up revisiting and deleting
910 // 'From' then we're done.
915 // If 'From' has value handles referring to it, do a real RAUW to update them.
916 From->replaceAllUsesWith(To);
918 From->eraseFromParent();