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.
254 // Threading Add over selects and phi nodes is pointless, so don't bother.
255 // Threading over the select in "A + select(cond, B, C)" means evaluating
256 // "A+B" and "A+C" and seeing if they are equal; but they are equal if and
257 // only if B and C are equal. If B and C are equal then (since we assume
258 // that operands have already been simplified) "select(cond, B, C)" should
259 // have been simplified to the common value of B and C already. Analysing
260 // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly
261 // for threading over phi nodes.
266 /// SimplifyAndInst - Given operands for an And, see if we can
267 /// fold the result. If not, this returns null.
268 static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
269 const DominatorTree *DT, unsigned MaxRecurse) {
270 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
271 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
272 Constant *Ops[] = { CLHS, CRHS };
273 return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
277 // Canonicalize the constant to the RHS.
282 if (isa<UndefValue>(Op1))
283 return Constant::getNullValue(Op0->getType());
290 if (match(Op1, m_Zero()))
294 if (match(Op1, m_AllOnes()))
297 // A & ~A = ~A & A = 0
299 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
300 (match(Op1, m_Not(m_Value(A))) && A == Op0))
301 return Constant::getNullValue(Op0->getType());
304 if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
305 (A == Op1 || B == Op1))
309 if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
310 (A == Op0 || B == Op0))
313 // (A & B) & A -> A & B
314 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
315 (A == Op1 || B == Op1))
318 // A & (A & B) -> A & B
319 if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
320 (A == Op0 || B == Op0))
323 // If the operation is with the result of a select instruction, check whether
324 // operating on either branch of the select always yields the same value.
325 if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
326 if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, DT,
330 // If the operation is with the result of a phi instruction, check whether
331 // operating on all incoming values of the phi always yields the same value.
332 if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
333 if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, DT,
340 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
341 const DominatorTree *DT) {
342 return ::SimplifyAndInst(Op0, Op1, TD, DT, RecursionLimit);
345 /// SimplifyOrInst - Given operands for an Or, see if we can
346 /// fold the result. If not, this returns null.
347 static Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
348 const DominatorTree *DT, unsigned MaxRecurse) {
349 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
350 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
351 Constant *Ops[] = { CLHS, CRHS };
352 return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
356 // Canonicalize the constant to the RHS.
361 if (isa<UndefValue>(Op1))
362 return Constant::getAllOnesValue(Op0->getType());
369 if (match(Op1, m_Zero()))
373 if (match(Op1, m_AllOnes()))
376 // A | ~A = ~A | A = -1
378 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
379 (match(Op1, m_Not(m_Value(A))) && A == Op0))
380 return Constant::getAllOnesValue(Op0->getType());
383 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
384 (A == Op1 || B == Op1))
388 if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
389 (A == Op0 || B == Op0))
392 // (A | B) | A -> A | B
393 if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
394 (A == Op1 || B == Op1))
397 // A | (A | B) -> A | B
398 if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
399 (A == Op0 || B == Op0))
402 // If the operation is with the result of a select instruction, check whether
403 // operating on either branch of the select always yields the same value.
404 if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
405 if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT,
409 // If the operation is with the result of a phi instruction, check whether
410 // operating on all incoming values of the phi always yields the same value.
411 if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
412 if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT,
419 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
420 const DominatorTree *DT) {
421 return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit);
424 /// SimplifyXorInst - Given operands for a Xor, see if we can
425 /// fold the result. If not, this returns null.
426 static Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
427 const DominatorTree *DT, unsigned MaxRecurse) {
428 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
429 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
430 Constant *Ops[] = { CLHS, CRHS };
431 return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(),
435 // Canonicalize the constant to the RHS.
439 // A ^ undef -> undef
440 if (isa<UndefValue>(Op1))
441 return UndefValue::get(Op0->getType());
444 if (match(Op1, m_Zero()))
449 return Constant::getNullValue(Op0->getType());
451 // A ^ ~A = ~A ^ A = -1
453 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
454 (match(Op1, m_Not(m_Value(A))) && A == Op0))
455 return Constant::getAllOnesValue(Op0->getType());
458 if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
459 (A == Op1 || B == Op1))
460 return A == Op1 ? B : A;
463 if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
464 (A == Op0 || B == Op0))
465 return A == Op0 ? B : A;
467 // Threading Xor over selects and phi nodes is pointless, so don't bother.
468 // Threading over the select in "A ^ select(cond, B, C)" means evaluating
469 // "A^B" and "A^C" and seeing if they are equal; but they are equal if and
470 // only if B and C are equal. If B and C are equal then (since we assume
471 // that operands have already been simplified) "select(cond, B, C)" should
472 // have been simplified to the common value of B and C already. Analysing
473 // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly
474 // for threading over phi nodes.
479 Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
480 const DominatorTree *DT) {
481 return ::SimplifyXorInst(Op0, Op1, TD, DT, RecursionLimit);
484 static const Type *GetCompareTy(Value *Op) {
485 return CmpInst::makeCmpResultType(Op->getType());
488 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
489 /// fold the result. If not, this returns null.
490 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
491 const TargetData *TD, const DominatorTree *DT,
492 unsigned MaxRecurse) {
493 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
494 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
496 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
497 if (Constant *CRHS = dyn_cast<Constant>(RHS))
498 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
500 // If we have a constant, make sure it is on the RHS.
502 Pred = CmpInst::getSwappedPredicate(Pred);
505 // ITy - This is the return type of the compare we're considering.
506 const Type *ITy = GetCompareTy(LHS);
508 // icmp X, X -> true/false
509 // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false
510 // because X could be 0.
511 if (LHS == RHS || isa<UndefValue>(RHS))
512 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
514 // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
515 // addresses never equal each other! We already know that Op0 != Op1.
516 if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) ||
517 isa<ConstantPointerNull>(LHS)) &&
518 (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) ||
519 isa<ConstantPointerNull>(RHS)))
520 return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
522 // See if we are doing a comparison with a constant.
523 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
524 // If we have an icmp le or icmp ge instruction, turn it into the
525 // appropriate icmp lt or icmp gt instruction. This allows us to rely on
526 // them being folded in the code below.
529 case ICmpInst::ICMP_ULE:
530 if (CI->isMaxValue(false)) // A <=u MAX -> TRUE
531 return ConstantInt::getTrue(CI->getContext());
533 case ICmpInst::ICMP_SLE:
534 if (CI->isMaxValue(true)) // A <=s MAX -> TRUE
535 return ConstantInt::getTrue(CI->getContext());
537 case ICmpInst::ICMP_UGE:
538 if (CI->isMinValue(false)) // A >=u MIN -> TRUE
539 return ConstantInt::getTrue(CI->getContext());
541 case ICmpInst::ICMP_SGE:
542 if (CI->isMinValue(true)) // A >=s MIN -> TRUE
543 return ConstantInt::getTrue(CI->getContext());
548 // If the comparison is with the result of a select instruction, check whether
549 // comparing with either branch of the select always yields the same value.
550 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
551 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
554 // If the comparison is with the result of a phi instruction, check whether
555 // doing the compare with each incoming phi value yields a common result.
556 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
557 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
563 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
564 const TargetData *TD, const DominatorTree *DT) {
565 return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
568 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
569 /// fold the result. If not, this returns null.
570 static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
571 const TargetData *TD, const DominatorTree *DT,
572 unsigned MaxRecurse) {
573 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
574 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
576 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
577 if (Constant *CRHS = dyn_cast<Constant>(RHS))
578 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
580 // If we have a constant, make sure it is on the RHS.
582 Pred = CmpInst::getSwappedPredicate(Pred);
585 // Fold trivial predicates.
586 if (Pred == FCmpInst::FCMP_FALSE)
587 return ConstantInt::get(GetCompareTy(LHS), 0);
588 if (Pred == FCmpInst::FCMP_TRUE)
589 return ConstantInt::get(GetCompareTy(LHS), 1);
591 if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef
592 return UndefValue::get(GetCompareTy(LHS));
594 // fcmp x,x -> true/false. Not all compares are foldable.
596 if (CmpInst::isTrueWhenEqual(Pred))
597 return ConstantInt::get(GetCompareTy(LHS), 1);
598 if (CmpInst::isFalseWhenEqual(Pred))
599 return ConstantInt::get(GetCompareTy(LHS), 0);
602 // Handle fcmp with constant RHS
603 if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
604 // If the constant is a nan, see if we can fold the comparison based on it.
605 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
606 if (CFP->getValueAPF().isNaN()) {
607 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo"
608 return ConstantInt::getFalse(CFP->getContext());
609 assert(FCmpInst::isUnordered(Pred) &&
610 "Comparison must be either ordered or unordered!");
611 // True if unordered.
612 return ConstantInt::getTrue(CFP->getContext());
614 // Check whether the constant is an infinity.
615 if (CFP->getValueAPF().isInfinity()) {
616 if (CFP->getValueAPF().isNegative()) {
618 case FCmpInst::FCMP_OLT:
619 // No value is ordered and less than negative infinity.
620 return ConstantInt::getFalse(CFP->getContext());
621 case FCmpInst::FCMP_UGE:
622 // All values are unordered with or at least negative infinity.
623 return ConstantInt::getTrue(CFP->getContext());
629 case FCmpInst::FCMP_OGT:
630 // No value is ordered and greater than infinity.
631 return ConstantInt::getFalse(CFP->getContext());
632 case FCmpInst::FCMP_ULE:
633 // All values are unordered with and at most infinity.
634 return ConstantInt::getTrue(CFP->getContext());
643 // If the comparison is with the result of a select instruction, check whether
644 // comparing with either branch of the select always yields the same value.
645 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
646 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
649 // If the comparison is with the result of a phi instruction, check whether
650 // doing the compare with each incoming phi value yields a common result.
651 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
652 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
658 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
659 const TargetData *TD, const DominatorTree *DT) {
660 return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
663 /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
664 /// the result. If not, this returns null.
665 Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal,
666 const TargetData *TD, const DominatorTree *) {
667 // select true, X, Y -> X
668 // select false, X, Y -> Y
669 if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal))
670 return CB->getZExtValue() ? TrueVal : FalseVal;
672 // select C, X, X -> X
673 if (TrueVal == FalseVal)
676 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X
678 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X
680 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y
681 if (isa<Constant>(TrueVal))
689 /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
690 /// fold the result. If not, this returns null.
691 Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps,
692 const TargetData *TD, const DominatorTree *) {
693 // getelementptr P -> P.
698 //if (isa<UndefValue>(Ops[0]))
699 // return UndefValue::get(GEP.getType());
701 // getelementptr P, 0 -> P.
703 if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
707 // Check to see if this is constant foldable.
708 for (unsigned i = 0; i != NumOps; ++i)
709 if (!isa<Constant>(Ops[i]))
712 return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]),
713 (Constant *const*)Ops+1, NumOps-1);
716 /// SimplifyPHINode - See if we can fold the given phi. If not, returns null.
717 static Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) {
718 // If all of the PHI's incoming values are the same then replace the PHI node
719 // with the common value.
720 Value *CommonValue = 0;
721 bool HasUndefInput = false;
722 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
723 Value *Incoming = PN->getIncomingValue(i);
724 // If the incoming value is the phi node itself, it can safely be skipped.
725 if (Incoming == PN) continue;
726 if (isa<UndefValue>(Incoming)) {
727 // Remember that we saw an undef value, but otherwise ignore them.
728 HasUndefInput = true;
731 if (CommonValue && Incoming != CommonValue)
732 return 0; // Not the same, bail out.
733 CommonValue = Incoming;
736 // If CommonValue is null then all of the incoming values were either undef or
737 // equal to the phi node itself.
739 return UndefValue::get(PN->getType());
741 // If we have a PHI node like phi(X, undef, X), where X is defined by some
742 // instruction, we cannot return X as the result of the PHI node unless it
743 // dominates the PHI block.
745 return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0;
751 //=== Helper functions for higher up the class hierarchy.
753 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
754 /// fold the result. If not, this returns null.
755 static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
756 const TargetData *TD, const DominatorTree *DT,
757 unsigned MaxRecurse) {
759 case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse);
760 case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD, DT, MaxRecurse);
762 if (Constant *CLHS = dyn_cast<Constant>(LHS))
763 if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
764 Constant *COps[] = {CLHS, CRHS};
765 return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD);
768 // If the operation is with the result of a select instruction, check whether
769 // operating on either branch of the select always yields the same value.
770 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
771 if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT,
775 // If the operation is with the result of a phi instruction, check whether
776 // operating on all incoming values of the phi always yields the same value.
777 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
778 if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse-1))
785 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
786 const TargetData *TD, const DominatorTree *DT) {
787 return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit);
790 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
792 static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
793 const TargetData *TD, const DominatorTree *DT,
794 unsigned MaxRecurse) {
795 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
796 return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
797 return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
800 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
801 const TargetData *TD, const DominatorTree *DT) {
802 return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
805 /// SimplifyInstruction - See if we can compute a simplified version of this
806 /// instruction. If not, this returns null.
807 Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD,
808 const DominatorTree *DT) {
811 switch (I->getOpcode()) {
813 Result = ConstantFoldInstruction(I, TD);
815 case Instruction::Add:
816 Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1),
817 cast<BinaryOperator>(I)->hasNoSignedWrap(),
818 cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
821 case Instruction::And:
822 Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT);
824 case Instruction::Or:
825 Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT);
827 case Instruction::Xor:
828 Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT);
830 case Instruction::ICmp:
831 Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
832 I->getOperand(0), I->getOperand(1), TD, DT);
834 case Instruction::FCmp:
835 Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
836 I->getOperand(0), I->getOperand(1), TD, DT);
838 case Instruction::Select:
839 Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1),
840 I->getOperand(2), TD, DT);
842 case Instruction::GetElementPtr: {
843 SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
844 Result = SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT);
847 case Instruction::PHI:
848 Result = SimplifyPHINode(cast<PHINode>(I), DT);
852 /// If called on unreachable code, the above logic may report that the
853 /// instruction simplified to itself. Make life easier for users by
854 /// detecting that case here, returning null if it occurs.
855 return Result == I ? 0 : Result;
858 /// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
859 /// delete the From instruction. In addition to a basic RAUW, this does a
860 /// recursive simplification of the newly formed instructions. This catches
861 /// things where one simplification exposes other opportunities. This only
862 /// simplifies and deletes scalar operations, it does not change the CFG.
864 void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
865 const TargetData *TD,
866 const DominatorTree *DT) {
867 assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!");
869 // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that
870 // we can know if it gets deleted out from under us or replaced in a
871 // recursive simplification.
872 WeakVH FromHandle(From);
875 while (!From->use_empty()) {
876 // Update the instruction to use the new value.
877 Use &TheUse = From->use_begin().getUse();
878 Instruction *User = cast<Instruction>(TheUse.getUser());
881 // Check to see if the instruction can be folded due to the operand
882 // replacement. For example changing (or X, Y) into (or X, -1) can replace
884 Value *SimplifiedVal;
886 // Sanity check to make sure 'User' doesn't dangle across
887 // SimplifyInstruction.
888 AssertingVH<> UserHandle(User);
890 SimplifiedVal = SimplifyInstruction(User, TD, DT);
891 if (SimplifiedVal == 0) continue;
894 // Recursively simplify this user to the new value.
895 ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT);
896 From = dyn_cast_or_null<Instruction>((Value*)FromHandle);
899 assert(ToHandle && "To value deleted by recursive simplification?");
901 // If the recursive simplification ended up revisiting and deleting
902 // 'From' then we're done.
907 // If 'From' has value handles referring to it, do a real RAUW to update them.
908 From->replaceAllUsesWith(To);
910 From->eraseFromParent();