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 // X + undef -> undef
246 if (isa<UndefValue>(Op1))
250 if (match(Op1, m_Zero()))
256 if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) ||
257 match(Op0, m_Sub(m_Value(Y), m_Specific(Op1))))
260 // X + ~X -> -1 since ~X = -X-1
261 if (match(Op0, m_Not(m_Specific(Op1))) ||
262 match(Op1, m_Not(m_Specific(Op0))))
263 return Constant::getAllOnesValue(Op0->getType());
265 // Threading Add over selects and phi nodes is pointless, so don't bother.
266 // Threading over the select in "A + select(cond, B, C)" means evaluating
267 // "A+B" and "A+C" and seeing if they are equal; but they are equal if and
268 // only if B and C are equal. If B and C are equal then (since we assume
269 // that operands have already been simplified) "select(cond, B, C)" should
270 // have been simplified to the common value of B and C already. Analysing
271 // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly
272 // for threading over phi nodes.
277 /// SimplifySubInst - Given operands for a Sub, see if we can
278 /// fold the result. If not, this returns null.
279 Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
280 const TargetData *TD, const DominatorTree *) {
281 if (Constant *CLHS = dyn_cast<Constant>(Op0))
282 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
283 Constant *Ops[] = { CLHS, CRHS };
284 return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(),
288 // X - undef -> undef
289 // undef - X -> undef
290 if (isa<UndefValue>(Op0) || isa<UndefValue>(Op1))
291 return UndefValue::get(Op0->getType());
294 if (match(Op1, m_Zero()))
299 return Constant::getNullValue(Op0->getType());
304 if (match(Op0, m_Add(m_Value(X), m_Specific(Op1))) ||
305 match(Op0, m_Add(m_Specific(Op1), m_Value(X))))
308 // Threading Sub over selects and phi nodes is pointless, so don't bother.
309 // Threading over the select in "A - select(cond, B, C)" means evaluating
310 // "A-B" and "A-C" and seeing if they are equal; but they are equal if and
311 // only if B and C are equal. If B and C are equal then (since we assume
312 // that operands have already been simplified) "select(cond, B, C)" should
313 // have been simplified to the common value of B and C already. Analysing
314 // "A-B" and "A-C" thus gains nothing, but costs compile time. Similarly
315 // for threading over phi nodes.
320 /// SimplifyAndInst - Given operands for an And, see if we can
321 /// fold the result. If not, this returns null.
322 static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
323 const DominatorTree *DT, unsigned MaxRecurse) {
324 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
325 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
326 Constant *Ops[] = { CLHS, CRHS };
327 return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
331 // Canonicalize the constant to the RHS.
336 if (isa<UndefValue>(Op1))
337 return Constant::getNullValue(Op0->getType());
344 if (match(Op1, m_Zero()))
348 if (match(Op1, m_AllOnes()))
351 // A & ~A = ~A & A = 0
352 Value *A = 0, *B = 0;
353 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
354 (match(Op1, m_Not(m_Value(A))) && A == Op0))
355 return Constant::getNullValue(Op0->getType());
358 if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
359 (A == Op1 || B == Op1))
363 if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
364 (A == Op0 || B == Op0))
367 // (A & B) & A -> A & B
368 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
369 (A == Op1 || B == Op1))
372 // A & (A & B) -> A & B
373 if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
374 (A == Op0 || B == Op0))
377 // If the operation is with the result of a select instruction, check whether
378 // operating on either branch of the select always yields the same value.
379 if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
380 if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, DT,
384 // If the operation is with the result of a phi instruction, check whether
385 // operating on all incoming values of the phi always yields the same value.
386 if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
387 if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, DT,
394 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
395 const DominatorTree *DT) {
396 return ::SimplifyAndInst(Op0, Op1, TD, DT, RecursionLimit);
399 /// SimplifyOrInst - Given operands for an Or, see if we can
400 /// fold the result. If not, this returns null.
401 static Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
402 const DominatorTree *DT, unsigned MaxRecurse) {
403 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
404 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
405 Constant *Ops[] = { CLHS, CRHS };
406 return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
410 // Canonicalize the constant to the RHS.
415 if (isa<UndefValue>(Op1))
416 return Constant::getAllOnesValue(Op0->getType());
423 if (match(Op1, m_Zero()))
427 if (match(Op1, m_AllOnes()))
430 // A | ~A = ~A | A = -1
431 Value *A = 0, *B = 0;
432 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
433 (match(Op1, m_Not(m_Value(A))) && A == Op0))
434 return Constant::getAllOnesValue(Op0->getType());
437 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
438 (A == Op1 || B == Op1))
442 if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
443 (A == Op0 || B == Op0))
446 // (A | B) | A -> A | B
447 if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
448 (A == Op1 || B == Op1))
451 // A | (A | B) -> A | B
452 if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
453 (A == Op0 || B == Op0))
456 // If the operation is with the result of a select instruction, check whether
457 // operating on either branch of the select always yields the same value.
458 if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
459 if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT,
463 // If the operation is with the result of a phi instruction, check whether
464 // operating on all incoming values of the phi always yields the same value.
465 if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
466 if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT,
473 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
474 const DominatorTree *DT) {
475 return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit);
478 /// SimplifyXorInst - Given operands for a Xor, see if we can
479 /// fold the result. If not, this returns null.
480 static Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
481 const DominatorTree *DT, unsigned MaxRecurse) {
482 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
483 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
484 Constant *Ops[] = { CLHS, CRHS };
485 return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(),
489 // Canonicalize the constant to the RHS.
493 // A ^ undef -> undef
494 if (isa<UndefValue>(Op1))
498 if (match(Op1, m_Zero()))
503 return Constant::getNullValue(Op0->getType());
505 // A ^ ~A = ~A ^ A = -1
506 Value *A = 0, *B = 0;
507 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
508 (match(Op1, m_Not(m_Value(A))) && A == Op0))
509 return Constant::getAllOnesValue(Op0->getType());
512 if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
513 (A == Op1 || B == Op1))
514 return A == Op1 ? B : A;
517 if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
518 (A == Op0 || B == Op0))
519 return A == Op0 ? B : A;
521 // Threading Xor over selects and phi nodes is pointless, so don't bother.
522 // Threading over the select in "A ^ select(cond, B, C)" means evaluating
523 // "A^B" and "A^C" and seeing if they are equal; but they are equal if and
524 // only if B and C are equal. If B and C are equal then (since we assume
525 // that operands have already been simplified) "select(cond, B, C)" should
526 // have been simplified to the common value of B and C already. Analysing
527 // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly
528 // for threading over phi nodes.
533 Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
534 const DominatorTree *DT) {
535 return ::SimplifyXorInst(Op0, Op1, TD, DT, RecursionLimit);
538 static const Type *GetCompareTy(Value *Op) {
539 return CmpInst::makeCmpResultType(Op->getType());
542 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
543 /// fold the result. If not, this returns null.
544 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
545 const TargetData *TD, const DominatorTree *DT,
546 unsigned MaxRecurse) {
547 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
548 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
550 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
551 if (Constant *CRHS = dyn_cast<Constant>(RHS))
552 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
554 // If we have a constant, make sure it is on the RHS.
556 Pred = CmpInst::getSwappedPredicate(Pred);
559 // ITy - This is the return type of the compare we're considering.
560 const Type *ITy = GetCompareTy(LHS);
562 // icmp X, X -> true/false
563 // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false
564 // because X could be 0.
565 if (LHS == RHS || isa<UndefValue>(RHS))
566 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
568 // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
569 // addresses never equal each other! We already know that Op0 != Op1.
570 if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) ||
571 isa<ConstantPointerNull>(LHS)) &&
572 (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) ||
573 isa<ConstantPointerNull>(RHS)))
574 return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
576 // See if we are doing a comparison with a constant.
577 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
578 // If we have an icmp le or icmp ge instruction, turn it into the
579 // appropriate icmp lt or icmp gt instruction. This allows us to rely on
580 // them being folded in the code below.
583 case ICmpInst::ICMP_ULE:
584 if (CI->isMaxValue(false)) // A <=u MAX -> TRUE
585 return ConstantInt::getTrue(CI->getContext());
587 case ICmpInst::ICMP_SLE:
588 if (CI->isMaxValue(true)) // A <=s MAX -> TRUE
589 return ConstantInt::getTrue(CI->getContext());
591 case ICmpInst::ICMP_UGE:
592 if (CI->isMinValue(false)) // A >=u MIN -> TRUE
593 return ConstantInt::getTrue(CI->getContext());
595 case ICmpInst::ICMP_SGE:
596 if (CI->isMinValue(true)) // A >=s MIN -> TRUE
597 return ConstantInt::getTrue(CI->getContext());
602 // If the comparison is with the result of a select instruction, check whether
603 // comparing with either branch of the select always yields the same value.
604 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
605 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
608 // If the comparison is with the result of a phi instruction, check whether
609 // doing the compare with each incoming phi value yields a common result.
610 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
611 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
617 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
618 const TargetData *TD, const DominatorTree *DT) {
619 return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
622 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
623 /// fold the result. If not, this returns null.
624 static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
625 const TargetData *TD, const DominatorTree *DT,
626 unsigned MaxRecurse) {
627 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
628 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
630 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
631 if (Constant *CRHS = dyn_cast<Constant>(RHS))
632 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
634 // If we have a constant, make sure it is on the RHS.
636 Pred = CmpInst::getSwappedPredicate(Pred);
639 // Fold trivial predicates.
640 if (Pred == FCmpInst::FCMP_FALSE)
641 return ConstantInt::get(GetCompareTy(LHS), 0);
642 if (Pred == FCmpInst::FCMP_TRUE)
643 return ConstantInt::get(GetCompareTy(LHS), 1);
645 if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef
646 return UndefValue::get(GetCompareTy(LHS));
648 // fcmp x,x -> true/false. Not all compares are foldable.
650 if (CmpInst::isTrueWhenEqual(Pred))
651 return ConstantInt::get(GetCompareTy(LHS), 1);
652 if (CmpInst::isFalseWhenEqual(Pred))
653 return ConstantInt::get(GetCompareTy(LHS), 0);
656 // Handle fcmp with constant RHS
657 if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
658 // If the constant is a nan, see if we can fold the comparison based on it.
659 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
660 if (CFP->getValueAPF().isNaN()) {
661 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo"
662 return ConstantInt::getFalse(CFP->getContext());
663 assert(FCmpInst::isUnordered(Pred) &&
664 "Comparison must be either ordered or unordered!");
665 // True if unordered.
666 return ConstantInt::getTrue(CFP->getContext());
668 // Check whether the constant is an infinity.
669 if (CFP->getValueAPF().isInfinity()) {
670 if (CFP->getValueAPF().isNegative()) {
672 case FCmpInst::FCMP_OLT:
673 // No value is ordered and less than negative infinity.
674 return ConstantInt::getFalse(CFP->getContext());
675 case FCmpInst::FCMP_UGE:
676 // All values are unordered with or at least negative infinity.
677 return ConstantInt::getTrue(CFP->getContext());
683 case FCmpInst::FCMP_OGT:
684 // No value is ordered and greater than infinity.
685 return ConstantInt::getFalse(CFP->getContext());
686 case FCmpInst::FCMP_ULE:
687 // All values are unordered with and at most infinity.
688 return ConstantInt::getTrue(CFP->getContext());
697 // If the comparison is with the result of a select instruction, check whether
698 // comparing with either branch of the select always yields the same value.
699 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
700 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
703 // If the comparison is with the result of a phi instruction, check whether
704 // doing the compare with each incoming phi value yields a common result.
705 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
706 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
712 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
713 const TargetData *TD, const DominatorTree *DT) {
714 return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
717 /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
718 /// the result. If not, this returns null.
719 Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal,
720 const TargetData *TD, const DominatorTree *) {
721 // select true, X, Y -> X
722 // select false, X, Y -> Y
723 if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal))
724 return CB->getZExtValue() ? TrueVal : FalseVal;
726 // select C, X, X -> X
727 if (TrueVal == FalseVal)
730 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X
732 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X
734 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y
735 if (isa<Constant>(TrueVal))
743 /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
744 /// fold the result. If not, this returns null.
745 Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps,
746 const TargetData *TD, const DominatorTree *) {
747 // The type of the GEP pointer operand.
748 const PointerType *PtrTy = cast<PointerType>(Ops[0]->getType());
750 // getelementptr P -> P.
754 if (isa<UndefValue>(Ops[0])) {
755 // Compute the (pointer) type returned by the GEP instruction.
756 const Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, &Ops[1],
758 const Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace());
759 return UndefValue::get(GEPTy);
763 // getelementptr P, 0 -> P.
764 if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
767 // getelementptr P, N -> P if P points to a type of zero size.
769 const Type *Ty = PtrTy->getElementType();
770 if (Ty->isSized() && TD->getTypeAllocSize(Ty) == 0)
775 // Check to see if this is constant foldable.
776 for (unsigned i = 0; i != NumOps; ++i)
777 if (!isa<Constant>(Ops[i]))
780 return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]),
781 (Constant *const*)Ops+1, NumOps-1);
784 /// SimplifyPHINode - See if we can fold the given phi. If not, returns null.
785 static Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) {
786 // If all of the PHI's incoming values are the same then replace the PHI node
787 // with the common value.
788 Value *CommonValue = 0;
789 bool HasUndefInput = false;
790 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
791 Value *Incoming = PN->getIncomingValue(i);
792 // If the incoming value is the phi node itself, it can safely be skipped.
793 if (Incoming == PN) continue;
794 if (isa<UndefValue>(Incoming)) {
795 // Remember that we saw an undef value, but otherwise ignore them.
796 HasUndefInput = true;
799 if (CommonValue && Incoming != CommonValue)
800 return 0; // Not the same, bail out.
801 CommonValue = Incoming;
804 // If CommonValue is null then all of the incoming values were either undef or
805 // equal to the phi node itself.
807 return UndefValue::get(PN->getType());
809 // If we have a PHI node like phi(X, undef, X), where X is defined by some
810 // instruction, we cannot return X as the result of the PHI node unless it
811 // dominates the PHI block.
813 return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0;
819 //=== Helper functions for higher up the class hierarchy.
821 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
822 /// fold the result. If not, this returns null.
823 static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
824 const TargetData *TD, const DominatorTree *DT,
825 unsigned MaxRecurse) {
827 case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse);
828 case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD, DT, MaxRecurse);
830 if (Constant *CLHS = dyn_cast<Constant>(LHS))
831 if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
832 Constant *COps[] = {CLHS, CRHS};
833 return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD);
836 // If the operation is with the result of a select instruction, check whether
837 // operating on either branch of the select always yields the same value.
838 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
839 if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT,
843 // If the operation is with the result of a phi instruction, check whether
844 // operating on all incoming values of the phi always yields the same value.
845 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
846 if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse-1))
853 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
854 const TargetData *TD, const DominatorTree *DT) {
855 return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit);
858 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
860 static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
861 const TargetData *TD, const DominatorTree *DT,
862 unsigned MaxRecurse) {
863 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
864 return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
865 return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
868 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
869 const TargetData *TD, const DominatorTree *DT) {
870 return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
873 /// SimplifyInstruction - See if we can compute a simplified version of this
874 /// instruction. If not, this returns null.
875 Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD,
876 const DominatorTree *DT) {
879 switch (I->getOpcode()) {
881 Result = ConstantFoldInstruction(I, TD);
883 case Instruction::Add:
884 Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1),
885 cast<BinaryOperator>(I)->hasNoSignedWrap(),
886 cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
889 case Instruction::Sub:
890 Result = SimplifySubInst(I->getOperand(0), I->getOperand(1),
891 cast<BinaryOperator>(I)->hasNoSignedWrap(),
892 cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
895 case Instruction::And:
896 Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT);
898 case Instruction::Or:
899 Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT);
901 case Instruction::Xor:
902 Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT);
904 case Instruction::ICmp:
905 Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
906 I->getOperand(0), I->getOperand(1), TD, DT);
908 case Instruction::FCmp:
909 Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
910 I->getOperand(0), I->getOperand(1), TD, DT);
912 case Instruction::Select:
913 Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1),
914 I->getOperand(2), TD, DT);
916 case Instruction::GetElementPtr: {
917 SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
918 Result = SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT);
921 case Instruction::PHI:
922 Result = SimplifyPHINode(cast<PHINode>(I), DT);
926 /// If called on unreachable code, the above logic may report that the
927 /// instruction simplified to itself. Make life easier for users by
928 /// detecting that case here, returning a safe value instead.
929 return Result == I ? UndefValue::get(I->getType()) : Result;
932 /// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
933 /// delete the From instruction. In addition to a basic RAUW, this does a
934 /// recursive simplification of the newly formed instructions. This catches
935 /// things where one simplification exposes other opportunities. This only
936 /// simplifies and deletes scalar operations, it does not change the CFG.
938 void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
939 const TargetData *TD,
940 const DominatorTree *DT) {
941 assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!");
943 // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that
944 // we can know if it gets deleted out from under us or replaced in a
945 // recursive simplification.
946 WeakVH FromHandle(From);
949 while (!From->use_empty()) {
950 // Update the instruction to use the new value.
951 Use &TheUse = From->use_begin().getUse();
952 Instruction *User = cast<Instruction>(TheUse.getUser());
955 // Check to see if the instruction can be folded due to the operand
956 // replacement. For example changing (or X, Y) into (or X, -1) can replace
958 Value *SimplifiedVal;
960 // Sanity check to make sure 'User' doesn't dangle across
961 // SimplifyInstruction.
962 AssertingVH<> UserHandle(User);
964 SimplifiedVal = SimplifyInstruction(User, TD, DT);
965 if (SimplifiedVal == 0) continue;
968 // Recursively simplify this user to the new value.
969 ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT);
970 From = dyn_cast_or_null<Instruction>((Value*)FromHandle);
973 assert(ToHandle && "To value deleted by recursive simplification?");
975 // If the recursive simplification ended up revisiting and deleting
976 // 'From' then we're done.
981 // If 'From' has value handles referring to it, do a real RAUW to update them.
982 From->replaceAllUsesWith(To);
984 From->eraseFromParent();