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. This does constant folding
12 // ("add i32 1, 1" -> "2") but can also handle non-constant operands, either
13 // returning a constant ("and i32 %x, 0" -> "0") or an already existing value
14 // ("and i32 %x, %x" -> "%x").
16 //===----------------------------------------------------------------------===//
18 #include "llvm/Analysis/InstructionSimplify.h"
19 #include "llvm/Analysis/ConstantFolding.h"
20 #include "llvm/Analysis/Dominators.h"
21 #include "llvm/Support/PatternMatch.h"
22 #include "llvm/Support/ValueHandle.h"
23 #include "llvm/Target/TargetData.h"
25 using namespace llvm::PatternMatch;
27 #define RecursionLimit 3
29 static Value *SimplifyBinOp(unsigned, Value *, Value *, const TargetData *,
30 const DominatorTree *, unsigned);
31 static Value *SimplifyCmpInst(unsigned, Value *, Value *, const TargetData *,
32 const DominatorTree *, unsigned);
34 /// ValueDominatesPHI - Does the given value dominate the specified phi node?
35 static bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
36 Instruction *I = dyn_cast<Instruction>(V);
38 // Arguments and constants dominate all instructions.
41 // If we have a DominatorTree then do a precise test.
43 return DT->dominates(I, P);
45 // Otherwise, if the instruction is in the entry block, and is not an invoke,
46 // then it obviously dominates all phi nodes.
47 if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() &&
54 /// ThreadBinOpOverSelect - In the case of a binary operation with a select
55 /// instruction as an operand, try to simplify the binop by seeing whether
56 /// evaluating it on both branches of the select results in the same value.
57 /// Returns the common value if so, otherwise returns null.
58 static Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS,
60 const DominatorTree *DT,
61 unsigned MaxRecurse) {
63 if (isa<SelectInst>(LHS)) {
64 SI = cast<SelectInst>(LHS);
66 assert(isa<SelectInst>(RHS) && "No select instruction operand!");
67 SI = cast<SelectInst>(RHS);
70 // Evaluate the BinOp on the true and false branches of the select.
74 TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, DT, MaxRecurse);
75 FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, DT, MaxRecurse);
77 TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, DT, MaxRecurse);
78 FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, DT, MaxRecurse);
81 // If they simplified to the same value, then return the common value.
82 // If they both failed to simplify then return null.
86 // If one branch simplified to undef, return the other one.
87 if (TV && isa<UndefValue>(TV))
89 if (FV && isa<UndefValue>(FV))
92 // If applying the operation did not change the true and false select values,
93 // then the result of the binop is the select itself.
94 if (TV == SI->getTrueValue() && FV == SI->getFalseValue())
97 // If one branch simplified and the other did not, and the simplified
98 // value is equal to the unsimplified one, return the simplified value.
99 // For example, select (cond, X, X & Z) & Z -> X & Z.
100 if ((FV && !TV) || (TV && !FV)) {
101 // Check that the simplified value has the form "X op Y" where "op" is the
102 // same as the original operation.
103 Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV);
104 if (Simplified && Simplified->getOpcode() == Opcode) {
105 // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS".
106 // We already know that "op" is the same as for the simplified value. See
107 // if the operands match too. If so, return the simplified value.
108 Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue();
109 Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS;
110 Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch;
111 if (Simplified->getOperand(0) == UnsimplifiedLHS &&
112 Simplified->getOperand(1) == UnsimplifiedRHS)
114 if (Simplified->isCommutative() &&
115 Simplified->getOperand(1) == UnsimplifiedLHS &&
116 Simplified->getOperand(0) == UnsimplifiedRHS)
124 /// ThreadCmpOverSelect - In the case of a comparison with a select instruction,
125 /// try to simplify the comparison by seeing whether both branches of the select
126 /// result in the same value. Returns the common value if so, otherwise returns
128 static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS,
129 Value *RHS, const TargetData *TD,
130 const DominatorTree *DT,
131 unsigned MaxRecurse) {
132 // Make sure the select is on the LHS.
133 if (!isa<SelectInst>(LHS)) {
135 Pred = CmpInst::getSwappedPredicate(Pred);
137 assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!");
138 SelectInst *SI = cast<SelectInst>(LHS);
140 // Now that we have "cmp select(cond, TV, FV), RHS", analyse it.
141 // Does "cmp TV, RHS" simplify?
142 if (Value *TCmp = SimplifyCmpInst(Pred, SI->getTrueValue(), RHS, TD, DT,
144 // It does! Does "cmp FV, RHS" simplify?
145 if (Value *FCmp = SimplifyCmpInst(Pred, SI->getFalseValue(), RHS, TD, DT,
147 // It does! If they simplified to the same value, then use it as the
148 // result of the original comparison.
154 /// ThreadBinOpOverPHI - In the case of a binary operation with an operand that
155 /// is a PHI instruction, try to simplify the binop by seeing whether evaluating
156 /// it on the incoming phi values yields the same result for every value. If so
157 /// returns the common value, otherwise returns null.
158 static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS,
159 const TargetData *TD, const DominatorTree *DT,
160 unsigned MaxRecurse) {
162 if (isa<PHINode>(LHS)) {
163 PI = cast<PHINode>(LHS);
164 // Bail out if RHS and the phi may be mutually interdependent due to a loop.
165 if (!ValueDominatesPHI(RHS, PI, DT))
168 assert(isa<PHINode>(RHS) && "No PHI instruction operand!");
169 PI = cast<PHINode>(RHS);
170 // Bail out if LHS and the phi may be mutually interdependent due to a loop.
171 if (!ValueDominatesPHI(LHS, PI, DT))
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 safely be skipped.
180 if (Incoming == PI) continue;
181 Value *V = PI == LHS ?
182 SimplifyBinOp(Opcode, Incoming, RHS, TD, DT, MaxRecurse) :
183 SimplifyBinOp(Opcode, LHS, Incoming, TD, DT, MaxRecurse);
184 // If the operation failed to simplify, or simplified to a different value
185 // to previously, then give up.
186 if (!V || (CommonValue && V != CommonValue))
194 /// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try
195 /// try to simplify the comparison by seeing whether comparing with all of the
196 /// incoming phi values yields the same result every time. If so returns the
197 /// common result, otherwise returns null.
198 static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
199 const TargetData *TD, const DominatorTree *DT,
200 unsigned MaxRecurse) {
201 // Make sure the phi is on the LHS.
202 if (!isa<PHINode>(LHS)) {
204 Pred = CmpInst::getSwappedPredicate(Pred);
206 assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!");
207 PHINode *PI = cast<PHINode>(LHS);
209 // Bail out if RHS and the phi may be mutually interdependent due to a loop.
210 if (!ValueDominatesPHI(RHS, PI, DT))
213 // Evaluate the BinOp on the incoming phi values.
214 Value *CommonValue = 0;
215 for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
216 Value *Incoming = PI->getIncomingValue(i);
217 // If the incoming value is the phi node itself, it can safely be skipped.
218 if (Incoming == PI) continue;
219 Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, DT, MaxRecurse);
220 // If the operation failed to simplify, or simplified to a different value
221 // to previously, then give up.
222 if (!V || (CommonValue && V != CommonValue))
230 /// SimplifyAddInst - Given operands for an Add, see if we can
231 /// fold the result. If not, this returns null.
232 Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
233 const TargetData *TD, const DominatorTree *) {
234 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
235 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
236 Constant *Ops[] = { CLHS, CRHS };
237 return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(),
241 // Canonicalize the constant to the RHS.
245 if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
246 // X + undef -> undef
247 if (isa<UndefValue>(Op1C))
251 if (Op1C->isNullValue())
255 // FIXME: Could pull several more out of instcombine.
257 // Threading Add over selects and phi nodes is pointless, so don't bother.
258 // Threading over the select in "A + select(cond, B, C)" means evaluating
259 // "A+B" and "A+C" and seeing if they are equal; but they are equal if and
260 // only if B and C are equal. If B and C are equal then (since we assume
261 // that operands have already been simplified) "select(cond, B, C)" should
262 // have been simplified to the common value of B and C already. Analysing
263 // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly
264 // for threading over phi nodes.
269 /// SimplifyAndInst - Given operands for an And, see if we can
270 /// fold the result. If not, this returns null.
271 static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
272 const DominatorTree *DT, unsigned MaxRecurse) {
273 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
274 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
275 Constant *Ops[] = { CLHS, CRHS };
276 return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
280 // Canonicalize the constant to the RHS.
285 if (isa<UndefValue>(Op1))
286 return Constant::getNullValue(Op0->getType());
293 if (match(Op1, m_Zero()))
297 if (match(Op1, m_AllOnes()))
300 // A & ~A = ~A & A = 0
301 Value *A = 0, *B = 0;
302 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
303 (match(Op1, m_Not(m_Value(A))) && A == Op0))
304 return Constant::getNullValue(Op0->getType());
307 if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
308 (A == Op1 || B == Op1))
312 if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
313 (A == Op0 || B == Op0))
316 // (A & B) & A -> A & B
317 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
318 (A == Op1 || B == Op1))
321 // A & (A & B) -> A & B
322 if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
323 (A == Op0 || B == Op0))
326 // If the operation is with the result of a select instruction, check whether
327 // operating on either branch of the select always yields the same value.
328 if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
329 if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, DT,
333 // If the operation is with the result of a phi instruction, check whether
334 // operating on all incoming values of the phi always yields the same value.
335 if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
336 if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, DT,
343 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
344 const DominatorTree *DT) {
345 return ::SimplifyAndInst(Op0, Op1, TD, DT, RecursionLimit);
348 /// SimplifyOrInst - Given operands for an Or, see if we can
349 /// fold the result. If not, this returns null.
350 static Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
351 const DominatorTree *DT, unsigned MaxRecurse) {
352 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
353 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
354 Constant *Ops[] = { CLHS, CRHS };
355 return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
359 // Canonicalize the constant to the RHS.
364 if (isa<UndefValue>(Op1))
365 return Constant::getAllOnesValue(Op0->getType());
372 if (match(Op1, m_Zero()))
376 if (match(Op1, m_AllOnes()))
379 // A | ~A = ~A | A = -1
380 Value *A = 0, *B = 0;
381 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
382 (match(Op1, m_Not(m_Value(A))) && A == Op0))
383 return Constant::getAllOnesValue(Op0->getType());
386 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
387 (A == Op1 || B == Op1))
391 if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
392 (A == Op0 || B == Op0))
395 // (A | B) | A -> A | B
396 if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
397 (A == Op1 || B == Op1))
400 // A | (A | B) -> A | B
401 if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
402 (A == Op0 || B == Op0))
405 // If the operation is with the result of a select instruction, check whether
406 // operating on either branch of the select always yields the same value.
407 if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
408 if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT,
412 // If the operation is with the result of a phi instruction, check whether
413 // operating on all incoming values of the phi always yields the same value.
414 if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
415 if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT,
422 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
423 const DominatorTree *DT) {
424 return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit);
427 /// SimplifyXorInst - Given operands for a Xor, see if we can
428 /// fold the result. If not, this returns null.
429 static Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
430 const DominatorTree *DT, unsigned MaxRecurse) {
431 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
432 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
433 Constant *Ops[] = { CLHS, CRHS };
434 return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(),
438 // Canonicalize the constant to the RHS.
442 // A ^ undef -> undef
443 if (isa<UndefValue>(Op1))
444 return UndefValue::get(Op0->getType());
447 if (match(Op1, m_Zero()))
452 return Constant::getNullValue(Op0->getType());
454 // A ^ ~A = ~A ^ A = -1
455 Value *A = 0, *B = 0;
456 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
457 (match(Op1, m_Not(m_Value(A))) && A == Op0))
458 return Constant::getAllOnesValue(Op0->getType());
461 if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
462 (A == Op1 || B == Op1))
463 return A == Op1 ? B : A;
466 if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
467 (A == Op0 || B == Op0))
468 return A == Op0 ? B : A;
470 // Threading Xor over selects and phi nodes is pointless, so don't bother.
471 // Threading over the select in "A ^ select(cond, B, C)" means evaluating
472 // "A^B" and "A^C" and seeing if they are equal; but they are equal if and
473 // only if B and C are equal. If B and C are equal then (since we assume
474 // that operands have already been simplified) "select(cond, B, C)" should
475 // have been simplified to the common value of B and C already. Analysing
476 // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly
477 // for threading over phi nodes.
482 Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
483 const DominatorTree *DT) {
484 return ::SimplifyXorInst(Op0, Op1, TD, DT, RecursionLimit);
487 static const Type *GetCompareTy(Value *Op) {
488 return CmpInst::makeCmpResultType(Op->getType());
491 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
492 /// fold the result. If not, this returns null.
493 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
494 const TargetData *TD, const DominatorTree *DT,
495 unsigned MaxRecurse) {
496 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
497 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
499 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
500 if (Constant *CRHS = dyn_cast<Constant>(RHS))
501 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
503 // If we have a constant, make sure it is on the RHS.
505 Pred = CmpInst::getSwappedPredicate(Pred);
508 // ITy - This is the return type of the compare we're considering.
509 const Type *ITy = GetCompareTy(LHS);
511 // icmp X, X -> true/false
512 // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false
513 // because X could be 0.
514 if (LHS == RHS || isa<UndefValue>(RHS))
515 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
517 // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
518 // addresses never equal each other! We already know that Op0 != Op1.
519 if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) ||
520 isa<ConstantPointerNull>(LHS)) &&
521 (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) ||
522 isa<ConstantPointerNull>(RHS)))
523 return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
525 // See if we are doing a comparison with a constant.
526 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
527 // If we have an icmp le or icmp ge instruction, turn it into the
528 // appropriate icmp lt or icmp gt instruction. This allows us to rely on
529 // them being folded in the code below.
532 case ICmpInst::ICMP_ULE:
533 if (CI->isMaxValue(false)) // A <=u MAX -> TRUE
534 return ConstantInt::getTrue(CI->getContext());
536 case ICmpInst::ICMP_SLE:
537 if (CI->isMaxValue(true)) // A <=s MAX -> TRUE
538 return ConstantInt::getTrue(CI->getContext());
540 case ICmpInst::ICMP_UGE:
541 if (CI->isMinValue(false)) // A >=u MIN -> TRUE
542 return ConstantInt::getTrue(CI->getContext());
544 case ICmpInst::ICMP_SGE:
545 if (CI->isMinValue(true)) // A >=s MIN -> TRUE
546 return ConstantInt::getTrue(CI->getContext());
551 // If the comparison is with the result of a select instruction, check whether
552 // comparing with either branch of the select always yields the same value.
553 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
554 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
557 // If the comparison is with the result of a phi instruction, check whether
558 // doing the compare with each incoming phi value yields a common result.
559 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
560 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
566 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
567 const TargetData *TD, const DominatorTree *DT) {
568 return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
571 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
572 /// fold the result. If not, this returns null.
573 static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
574 const TargetData *TD, const DominatorTree *DT,
575 unsigned MaxRecurse) {
576 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
577 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
579 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
580 if (Constant *CRHS = dyn_cast<Constant>(RHS))
581 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
583 // If we have a constant, make sure it is on the RHS.
585 Pred = CmpInst::getSwappedPredicate(Pred);
588 // Fold trivial predicates.
589 if (Pred == FCmpInst::FCMP_FALSE)
590 return ConstantInt::get(GetCompareTy(LHS), 0);
591 if (Pred == FCmpInst::FCMP_TRUE)
592 return ConstantInt::get(GetCompareTy(LHS), 1);
594 if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef
595 return UndefValue::get(GetCompareTy(LHS));
597 // fcmp x,x -> true/false. Not all compares are foldable.
599 if (CmpInst::isTrueWhenEqual(Pred))
600 return ConstantInt::get(GetCompareTy(LHS), 1);
601 if (CmpInst::isFalseWhenEqual(Pred))
602 return ConstantInt::get(GetCompareTy(LHS), 0);
605 // Handle fcmp with constant RHS
606 if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
607 // If the constant is a nan, see if we can fold the comparison based on it.
608 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
609 if (CFP->getValueAPF().isNaN()) {
610 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo"
611 return ConstantInt::getFalse(CFP->getContext());
612 assert(FCmpInst::isUnordered(Pred) &&
613 "Comparison must be either ordered or unordered!");
614 // True if unordered.
615 return ConstantInt::getTrue(CFP->getContext());
617 // Check whether the constant is an infinity.
618 if (CFP->getValueAPF().isInfinity()) {
619 if (CFP->getValueAPF().isNegative()) {
621 case FCmpInst::FCMP_OLT:
622 // No value is ordered and less than negative infinity.
623 return ConstantInt::getFalse(CFP->getContext());
624 case FCmpInst::FCMP_UGE:
625 // All values are unordered with or at least negative infinity.
626 return ConstantInt::getTrue(CFP->getContext());
632 case FCmpInst::FCMP_OGT:
633 // No value is ordered and greater than infinity.
634 return ConstantInt::getFalse(CFP->getContext());
635 case FCmpInst::FCMP_ULE:
636 // All values are unordered with and at most infinity.
637 return ConstantInt::getTrue(CFP->getContext());
646 // If the comparison is with the result of a select instruction, check whether
647 // comparing with either branch of the select always yields the same value.
648 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
649 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
652 // If the comparison is with the result of a phi instruction, check whether
653 // doing the compare with each incoming phi value yields a common result.
654 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
655 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
661 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
662 const TargetData *TD, const DominatorTree *DT) {
663 return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
666 /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
667 /// the result. If not, this returns null.
668 Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal,
669 const TargetData *TD, const DominatorTree *) {
670 // select true, X, Y -> X
671 // select false, X, Y -> Y
672 if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal))
673 return CB->getZExtValue() ? TrueVal : FalseVal;
675 // select C, X, X -> X
676 if (TrueVal == FalseVal)
679 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X
681 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X
683 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y
684 if (isa<Constant>(TrueVal))
692 /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
693 /// fold the result. If not, this returns null.
694 Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps,
695 const TargetData *TD, const DominatorTree *) {
696 // The type of the GEP pointer operand.
697 const PointerType *PtrTy = cast<PointerType>(Ops[0]->getType());
699 // getelementptr P -> P.
703 if (isa<UndefValue>(Ops[0])) {
704 // Compute the (pointer) type returned by the GEP instruction.
705 const Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, &Ops[1],
707 const Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace());
708 return UndefValue::get(GEPTy);
712 // getelementptr P, 0 -> P.
713 if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
716 // getelementptr P, N -> P if P points to a type of zero size.
718 const Type *Ty = PtrTy->getElementType();
719 if (Ty->isSized() && TD->getTypeAllocSize(Ty) == 0)
724 // Check to see if this is constant foldable.
725 for (unsigned i = 0; i != NumOps; ++i)
726 if (!isa<Constant>(Ops[i]))
729 return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]),
730 (Constant *const*)Ops+1, NumOps-1);
733 /// SimplifyPHINode - See if we can fold the given phi. If not, returns null.
734 static Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) {
735 // If all of the PHI's incoming values are the same then replace the PHI node
736 // with the common value.
737 Value *CommonValue = 0;
738 bool HasUndefInput = false;
739 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
740 Value *Incoming = PN->getIncomingValue(i);
741 // If the incoming value is the phi node itself, it can safely be skipped.
742 if (Incoming == PN) continue;
743 if (isa<UndefValue>(Incoming)) {
744 // Remember that we saw an undef value, but otherwise ignore them.
745 HasUndefInput = true;
748 if (CommonValue && Incoming != CommonValue)
749 return 0; // Not the same, bail out.
750 CommonValue = Incoming;
753 // If CommonValue is null then all of the incoming values were either undef or
754 // equal to the phi node itself.
756 return UndefValue::get(PN->getType());
758 // If we have a PHI node like phi(X, undef, X), where X is defined by some
759 // instruction, we cannot return X as the result of the PHI node unless it
760 // dominates the PHI block.
762 return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0;
768 //=== Helper functions for higher up the class hierarchy.
770 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
771 /// fold the result. If not, this returns null.
772 static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
773 const TargetData *TD, const DominatorTree *DT,
774 unsigned MaxRecurse) {
776 case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse);
777 case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD, DT, MaxRecurse);
779 if (Constant *CLHS = dyn_cast<Constant>(LHS))
780 if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
781 Constant *COps[] = {CLHS, CRHS};
782 return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD);
785 // If the operation is with the result of a select instruction, check whether
786 // operating on either branch of the select always yields the same value.
787 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
788 if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT,
792 // If the operation is with the result of a phi instruction, check whether
793 // operating on all incoming values of the phi always yields the same value.
794 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
795 if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse-1))
802 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
803 const TargetData *TD, const DominatorTree *DT) {
804 return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit);
807 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
809 static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
810 const TargetData *TD, const DominatorTree *DT,
811 unsigned MaxRecurse) {
812 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
813 return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
814 return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
817 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
818 const TargetData *TD, const DominatorTree *DT) {
819 return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
822 /// SimplifyInstruction - See if we can compute a simplified version of this
823 /// instruction. If not, this returns null.
824 Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD,
825 const DominatorTree *DT) {
828 switch (I->getOpcode()) {
830 Result = ConstantFoldInstruction(I, TD);
832 case Instruction::Add:
833 Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1),
834 cast<BinaryOperator>(I)->hasNoSignedWrap(),
835 cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
838 case Instruction::And:
839 Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT);
841 case Instruction::Or:
842 Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT);
844 case Instruction::Xor:
845 Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT);
847 case Instruction::ICmp:
848 Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
849 I->getOperand(0), I->getOperand(1), TD, DT);
851 case Instruction::FCmp:
852 Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
853 I->getOperand(0), I->getOperand(1), TD, DT);
855 case Instruction::Select:
856 Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1),
857 I->getOperand(2), TD, DT);
859 case Instruction::GetElementPtr: {
860 SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
861 Result = SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT);
864 case Instruction::PHI:
865 Result = SimplifyPHINode(cast<PHINode>(I), DT);
869 /// If called on unreachable code, the above logic may report that the
870 /// instruction simplified to itself. Make life easier for users by
871 /// detecting that case here, returning null if it occurs.
872 return Result == I ? 0 : Result;
875 /// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
876 /// delete the From instruction. In addition to a basic RAUW, this does a
877 /// recursive simplification of the newly formed instructions. This catches
878 /// things where one simplification exposes other opportunities. This only
879 /// simplifies and deletes scalar operations, it does not change the CFG.
881 void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
882 const TargetData *TD,
883 const DominatorTree *DT) {
884 assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!");
886 // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that
887 // we can know if it gets deleted out from under us or replaced in a
888 // recursive simplification.
889 WeakVH FromHandle(From);
892 while (!From->use_empty()) {
893 // Update the instruction to use the new value.
894 Use &TheUse = From->use_begin().getUse();
895 Instruction *User = cast<Instruction>(TheUse.getUser());
898 // Check to see if the instruction can be folded due to the operand
899 // replacement. For example changing (or X, Y) into (or X, -1) can replace
901 Value *SimplifiedVal;
903 // Sanity check to make sure 'User' doesn't dangle across
904 // SimplifyInstruction.
905 AssertingVH<> UserHandle(User);
907 SimplifiedVal = SimplifyInstruction(User, TD, DT);
908 if (SimplifiedVal == 0) continue;
911 // Recursively simplify this user to the new value.
912 ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT);
913 From = dyn_cast_or_null<Instruction>((Value*)FromHandle);
916 assert(ToHandle && "To value deleted by recursive simplification?");
918 // If the recursive simplification ended up revisiting and deleting
919 // 'From' then we're done.
924 // If 'From' has value handles referring to it, do a real RAUW to update them.
925 From->replaceAllUsesWith(To);
927 From->eraseFromParent();