1 //===- InstructionSimplify.cpp - Fold instruction operands ----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements routines for folding instructions into simpler forms
11 // that do not require creating new instructions. For example, this does
12 // constant folding, and can handle identities like (X&0)->0.
14 //===----------------------------------------------------------------------===//
16 #include "llvm/Analysis/InstructionSimplify.h"
17 #include "llvm/Analysis/ConstantFolding.h"
18 #include "llvm/Analysis/Dominators.h"
19 #include "llvm/Support/PatternMatch.h"
20 #include "llvm/Support/ValueHandle.h"
22 using namespace llvm::PatternMatch;
24 #define RecursionLimit 3
26 static Value *SimplifyBinOp(unsigned, Value *, Value *, const TargetData *,
27 const DominatorTree *, unsigned);
28 static Value *SimplifyCmpInst(unsigned, Value *, Value *, const TargetData *,
29 const DominatorTree *, unsigned);
31 /// ValueDominatesPHI - Does the given value dominate the specified phi node?
32 static bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
33 Instruction *I = dyn_cast<Instruction>(V);
35 // Arguments and constants dominate all instructions.
38 // If we have a DominatorTree then do a precise test.
40 return DT->dominates(I, P);
42 // Otherwise, if the instruction is in the entry block, and is not an invoke,
43 // then it obviously dominates all phi nodes.
44 if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() &&
51 /// ThreadBinOpOverSelect - In the case of a binary operation with a select
52 /// instruction as an operand, try to simplify the binop by seeing whether
53 /// evaluating it on both branches of the select results in the same value.
54 /// Returns the common value if so, otherwise returns null.
55 static Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS,
57 const DominatorTree *DT,
58 unsigned MaxRecurse) {
60 if (isa<SelectInst>(LHS)) {
61 SI = cast<SelectInst>(LHS);
63 assert(isa<SelectInst>(RHS) && "No select instruction operand!");
64 SI = cast<SelectInst>(RHS);
67 // Evaluate the BinOp on the true and false branches of the select.
71 TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, DT, MaxRecurse);
72 FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, DT, MaxRecurse);
74 TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, DT, MaxRecurse);
75 FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, DT, MaxRecurse);
78 // If they simplified to the same value, then return the common value.
79 // If they both failed to simplify then return null.
83 // If one branch simplified to undef, return the other one.
84 if (TV && isa<UndefValue>(TV))
86 if (FV && isa<UndefValue>(FV))
89 // If applying the operation did not change the true and false select values,
90 // then the result of the binop is the select itself.
91 if (TV == SI->getTrueValue() && FV == SI->getFalseValue())
94 // If one branch simplified and the other did not, and the simplified
95 // value is equal to the unsimplified one, return the simplified value.
96 // For example, select (cond, X, X & Z) & Z -> X & Z.
97 if ((FV && !TV) || (TV && !FV)) {
98 // Check that the simplified value has the form "X op Y" where "op" is the
99 // same as the original operation.
100 Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV);
101 if (Simplified && Simplified->getOpcode() == Opcode) {
102 // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS".
103 // We already know that "op" is the same as for the simplified value. See
104 // if the operands match too. If so, return the simplified value.
105 Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue();
106 Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS;
107 Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch;
108 if (Simplified->getOperand(0) == UnsimplifiedLHS &&
109 Simplified->getOperand(1) == UnsimplifiedRHS)
111 if (Simplified->isCommutative() &&
112 Simplified->getOperand(1) == UnsimplifiedLHS &&
113 Simplified->getOperand(0) == UnsimplifiedRHS)
121 /// ThreadCmpOverSelect - In the case of a comparison with a select instruction,
122 /// try to simplify the comparison by seeing whether both branches of the select
123 /// result in the same value. Returns the common value if so, otherwise returns
125 static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS,
126 Value *RHS, const TargetData *TD,
127 const DominatorTree *DT,
128 unsigned MaxRecurse) {
129 // Make sure the select is on the LHS.
130 if (!isa<SelectInst>(LHS)) {
132 Pred = CmpInst::getSwappedPredicate(Pred);
134 assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!");
135 SelectInst *SI = cast<SelectInst>(LHS);
137 // Now that we have "cmp select(cond, TV, FV), RHS", analyse it.
138 // Does "cmp TV, RHS" simplify?
139 if (Value *TCmp = SimplifyCmpInst(Pred, SI->getTrueValue(), RHS, TD, DT,
141 // It does! Does "cmp FV, RHS" simplify?
142 if (Value *FCmp = SimplifyCmpInst(Pred, SI->getFalseValue(), RHS, TD, DT,
144 // It does! If they simplified to the same value, then use it as the
145 // result of the original comparison.
151 /// ThreadBinOpOverPHI - In the case of a binary operation with an operand that
152 /// is a PHI instruction, try to simplify the binop by seeing whether evaluating
153 /// it on the incoming phi values yields the same result for every value. If so
154 /// returns the common value, otherwise returns null.
155 static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS,
156 const TargetData *TD, const DominatorTree *DT,
157 unsigned MaxRecurse) {
159 if (isa<PHINode>(LHS)) {
160 PI = cast<PHINode>(LHS);
161 // Bail out if RHS and the phi may be mutually interdependent due to a loop.
162 if (!ValueDominatesPHI(RHS, PI, DT))
165 assert(isa<PHINode>(RHS) && "No PHI instruction operand!");
166 PI = cast<PHINode>(RHS);
167 // Bail out if LHS and the phi may be mutually interdependent due to a loop.
168 if (!ValueDominatesPHI(LHS, PI, DT))
172 // Evaluate the BinOp on the incoming phi values.
173 Value *CommonValue = 0;
174 for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
175 Value *Incoming = PI->getIncomingValue(i);
176 // If the incoming value is the phi node itself, it can safely be skipped.
177 if (Incoming == PI) continue;
178 Value *V = PI == LHS ?
179 SimplifyBinOp(Opcode, Incoming, RHS, TD, DT, MaxRecurse) :
180 SimplifyBinOp(Opcode, LHS, Incoming, TD, DT, MaxRecurse);
181 // If the operation failed to simplify, or simplified to a different value
182 // to previously, then give up.
183 if (!V || (CommonValue && V != CommonValue))
191 /// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try
192 /// try to simplify the comparison by seeing whether comparing with all of the
193 /// incoming phi values yields the same result every time. If so returns the
194 /// common result, otherwise returns null.
195 static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
196 const TargetData *TD, const DominatorTree *DT,
197 unsigned MaxRecurse) {
198 // Make sure the phi is on the LHS.
199 if (!isa<PHINode>(LHS)) {
201 Pred = CmpInst::getSwappedPredicate(Pred);
203 assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!");
204 PHINode *PI = cast<PHINode>(LHS);
206 // Bail out if RHS and the phi may be mutually interdependent due to a loop.
207 if (!ValueDominatesPHI(RHS, PI, DT))
210 // Evaluate the BinOp on the incoming phi values.
211 Value *CommonValue = 0;
212 for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
213 Value *Incoming = PI->getIncomingValue(i);
214 // If the incoming value is the phi node itself, it can safely be skipped.
215 if (Incoming == PI) continue;
216 Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, DT, MaxRecurse);
217 // If the operation failed to simplify, or simplified to a different value
218 // to previously, then give up.
219 if (!V || (CommonValue && V != CommonValue))
227 /// SimplifyAddInst - Given operands for an Add, see if we can
228 /// fold the result. If not, this returns null.
229 Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
230 const TargetData *TD, const DominatorTree *) {
231 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
232 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
233 Constant *Ops[] = { CLHS, CRHS };
234 return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(),
238 // Canonicalize the constant to the RHS.
242 if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
243 // X + undef -> undef
244 if (isa<UndefValue>(Op1C))
248 if (Op1C->isNullValue())
252 // FIXME: Could pull several more out of instcombine.
256 /// SimplifyAndInst - Given operands for an And, see if we can
257 /// fold the result. If not, this returns null.
258 static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
259 const DominatorTree *DT, unsigned MaxRecurse) {
260 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
261 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
262 Constant *Ops[] = { CLHS, CRHS };
263 return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
267 // Canonicalize the constant to the RHS.
272 if (isa<UndefValue>(Op1))
273 return Constant::getNullValue(Op0->getType());
280 if (isa<ConstantAggregateZero>(Op1))
284 if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1))
285 if (CP->isAllOnesValue())
288 if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) {
293 if (Op1CI->isAllOnesValue())
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 (isa<ConstantAggregateZero>(Op1))
372 // X | <-1,-1> = <-1,-1>
373 if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1))
374 if (CP->isAllOnesValue())
377 if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) {
382 if (Op1CI->isAllOnesValue())
386 // A | ~A = ~A | A = -1
388 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
389 (match(Op1, m_Not(m_Value(A))) && A == Op0))
390 return Constant::getAllOnesValue(Op0->getType());
393 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
394 (A == Op1 || B == Op1))
398 if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
399 (A == Op0 || B == Op0))
402 // (A | B) | A -> A | B
403 if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
404 (A == Op1 || B == Op1))
407 // A | (A | B) -> A | B
408 if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
409 (A == Op0 || B == Op0))
412 // If the operation is with the result of a select instruction, check whether
413 // operating on either branch of the select always yields the same value.
414 if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
415 if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT,
419 // If the operation is with the result of a phi instruction, check whether
420 // operating on all incoming values of the phi always yields the same value.
421 if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
422 if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT,
429 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
430 const DominatorTree *DT) {
431 return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit);
434 static const Type *GetCompareTy(Value *Op) {
435 return CmpInst::makeCmpResultType(Op->getType());
438 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
439 /// fold the result. If not, this returns null.
440 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
441 const TargetData *TD, const DominatorTree *DT,
442 unsigned MaxRecurse) {
443 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
444 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
446 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
447 if (Constant *CRHS = dyn_cast<Constant>(RHS))
448 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
450 // If we have a constant, make sure it is on the RHS.
452 Pred = CmpInst::getSwappedPredicate(Pred);
455 // ITy - This is the return type of the compare we're considering.
456 const Type *ITy = GetCompareTy(LHS);
458 // icmp X, X -> true/false
459 // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false
460 // because X could be 0.
461 if (LHS == RHS || isa<UndefValue>(RHS))
462 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
464 // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
465 // addresses never equal each other! We already know that Op0 != Op1.
466 if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) ||
467 isa<ConstantPointerNull>(LHS)) &&
468 (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) ||
469 isa<ConstantPointerNull>(RHS)))
470 return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
472 // See if we are doing a comparison with a constant.
473 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
474 // If we have an icmp le or icmp ge instruction, turn it into the
475 // appropriate icmp lt or icmp gt instruction. This allows us to rely on
476 // them being folded in the code below.
479 case ICmpInst::ICMP_ULE:
480 if (CI->isMaxValue(false)) // A <=u MAX -> TRUE
481 return ConstantInt::getTrue(CI->getContext());
483 case ICmpInst::ICMP_SLE:
484 if (CI->isMaxValue(true)) // A <=s MAX -> TRUE
485 return ConstantInt::getTrue(CI->getContext());
487 case ICmpInst::ICMP_UGE:
488 if (CI->isMinValue(false)) // A >=u MIN -> TRUE
489 return ConstantInt::getTrue(CI->getContext());
491 case ICmpInst::ICMP_SGE:
492 if (CI->isMinValue(true)) // A >=s MIN -> TRUE
493 return ConstantInt::getTrue(CI->getContext());
498 // If the comparison is with the result of a select instruction, check whether
499 // comparing with either branch of the select always yields the same value.
500 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
501 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
504 // If the comparison is with the result of a phi instruction, check whether
505 // doing the compare with each incoming phi value yields a common result.
506 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
507 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
513 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
514 const TargetData *TD, const DominatorTree *DT) {
515 return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
518 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
519 /// fold the result. If not, this returns null.
520 static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
521 const TargetData *TD, const DominatorTree *DT,
522 unsigned MaxRecurse) {
523 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
524 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
526 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
527 if (Constant *CRHS = dyn_cast<Constant>(RHS))
528 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
530 // If we have a constant, make sure it is on the RHS.
532 Pred = CmpInst::getSwappedPredicate(Pred);
535 // Fold trivial predicates.
536 if (Pred == FCmpInst::FCMP_FALSE)
537 return ConstantInt::get(GetCompareTy(LHS), 0);
538 if (Pred == FCmpInst::FCMP_TRUE)
539 return ConstantInt::get(GetCompareTy(LHS), 1);
541 if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef
542 return UndefValue::get(GetCompareTy(LHS));
544 // fcmp x,x -> true/false. Not all compares are foldable.
546 if (CmpInst::isTrueWhenEqual(Pred))
547 return ConstantInt::get(GetCompareTy(LHS), 1);
548 if (CmpInst::isFalseWhenEqual(Pred))
549 return ConstantInt::get(GetCompareTy(LHS), 0);
552 // Handle fcmp with constant RHS
553 if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
554 // If the constant is a nan, see if we can fold the comparison based on it.
555 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
556 if (CFP->getValueAPF().isNaN()) {
557 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo"
558 return ConstantInt::getFalse(CFP->getContext());
559 assert(FCmpInst::isUnordered(Pred) &&
560 "Comparison must be either ordered or unordered!");
561 // True if unordered.
562 return ConstantInt::getTrue(CFP->getContext());
564 // Check whether the constant is an infinity.
565 if (CFP->getValueAPF().isInfinity()) {
566 if (CFP->getValueAPF().isNegative()) {
568 case FCmpInst::FCMP_OLT:
569 // No value is ordered and less than negative infinity.
570 return ConstantInt::getFalse(CFP->getContext());
571 case FCmpInst::FCMP_UGE:
572 // All values are unordered with or at least negative infinity.
573 return ConstantInt::getTrue(CFP->getContext());
579 case FCmpInst::FCMP_OGT:
580 // No value is ordered and greater than infinity.
581 return ConstantInt::getFalse(CFP->getContext());
582 case FCmpInst::FCMP_ULE:
583 // All values are unordered with and at most infinity.
584 return ConstantInt::getTrue(CFP->getContext());
593 // If the comparison is with the result of a select instruction, check whether
594 // comparing with either branch of the select always yields the same value.
595 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
596 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
599 // If the comparison is with the result of a phi instruction, check whether
600 // doing the compare with each incoming phi value yields a common result.
601 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
602 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
608 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
609 const TargetData *TD, const DominatorTree *DT) {
610 return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
613 /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
614 /// the result. If not, this returns null.
615 Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal,
616 const TargetData *TD, const DominatorTree *) {
617 // select true, X, Y -> X
618 // select false, X, Y -> Y
619 if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal))
620 return CB->getZExtValue() ? TrueVal : FalseVal;
622 // select C, X, X -> X
623 if (TrueVal == FalseVal)
626 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X
628 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X
630 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y
631 if (isa<Constant>(TrueVal))
639 /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
640 /// fold the result. If not, this returns null.
641 Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps,
642 const TargetData *TD, const DominatorTree *) {
643 // getelementptr P -> P.
648 //if (isa<UndefValue>(Ops[0]))
649 // return UndefValue::get(GEP.getType());
651 // getelementptr P, 0 -> P.
653 if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
657 // Check to see if this is constant foldable.
658 for (unsigned i = 0; i != NumOps; ++i)
659 if (!isa<Constant>(Ops[i]))
662 return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]),
663 (Constant *const*)Ops+1, NumOps-1);
666 /// SimplifyPHINode - See if we can fold the given phi. If not, returns null.
667 static Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) {
668 // If all of the PHI's incoming values are the same then replace the PHI node
669 // with the common value.
670 Value *CommonValue = 0;
671 bool HasUndefInput = false;
672 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
673 Value *Incoming = PN->getIncomingValue(i);
674 // If the incoming value is the phi node itself, it can safely be skipped.
675 if (Incoming == PN) continue;
676 if (isa<UndefValue>(Incoming)) {
677 // Remember that we saw an undef value, but otherwise ignore them.
678 HasUndefInput = true;
681 if (CommonValue && Incoming != CommonValue)
682 return 0; // Not the same, bail out.
683 CommonValue = Incoming;
686 // If CommonValue is null then all of the incoming values were either undef or
687 // equal to the phi node itself.
689 return UndefValue::get(PN->getType());
691 // If we have a PHI node like phi(X, undef, X), where X is defined by some
692 // instruction, we cannot return X as the result of the PHI node unless it
693 // dominates the PHI block.
695 return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0;
701 //=== Helper functions for higher up the class hierarchy.
703 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
704 /// fold the result. If not, this returns null.
705 static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
706 const TargetData *TD, const DominatorTree *DT,
707 unsigned MaxRecurse) {
709 case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse);
710 case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD, DT, MaxRecurse);
712 if (Constant *CLHS = dyn_cast<Constant>(LHS))
713 if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
714 Constant *COps[] = {CLHS, CRHS};
715 return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD);
718 // If the operation is with the result of a select instruction, check whether
719 // operating on either branch of the select always yields the same value.
720 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
721 if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT,
725 // If the operation is with the result of a phi instruction, check whether
726 // operating on all incoming values of the phi always yields the same value.
727 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
728 if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse-1))
735 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
736 const TargetData *TD, const DominatorTree *DT) {
737 return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit);
740 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
742 static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
743 const TargetData *TD, const DominatorTree *DT,
744 unsigned MaxRecurse) {
745 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
746 return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
747 return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
750 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
751 const TargetData *TD, const DominatorTree *DT) {
752 return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
755 /// SimplifyInstruction - See if we can compute a simplified version of this
756 /// instruction. If not, this returns null.
757 Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD,
758 const DominatorTree *DT) {
759 switch (I->getOpcode()) {
761 return ConstantFoldInstruction(I, TD);
762 case Instruction::Add:
763 return SimplifyAddInst(I->getOperand(0), I->getOperand(1),
764 cast<BinaryOperator>(I)->hasNoSignedWrap(),
765 cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
767 case Instruction::And:
768 return SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT);
769 case Instruction::Or:
770 return SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT);
771 case Instruction::ICmp:
772 return SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
773 I->getOperand(0), I->getOperand(1), TD, DT);
774 case Instruction::FCmp:
775 return SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
776 I->getOperand(0), I->getOperand(1), TD, DT);
777 case Instruction::Select:
778 return SimplifySelectInst(I->getOperand(0), I->getOperand(1),
779 I->getOperand(2), TD, DT);
780 case Instruction::GetElementPtr: {
781 SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
782 return SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT);
784 case Instruction::PHI:
785 return SimplifyPHINode(cast<PHINode>(I), DT);
789 /// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
790 /// delete the From instruction. In addition to a basic RAUW, this does a
791 /// recursive simplification of the newly formed instructions. This catches
792 /// things where one simplification exposes other opportunities. This only
793 /// simplifies and deletes scalar operations, it does not change the CFG.
795 void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
796 const TargetData *TD,
797 const DominatorTree *DT) {
798 assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!");
800 // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that
801 // we can know if it gets deleted out from under us or replaced in a
802 // recursive simplification.
803 WeakVH FromHandle(From);
806 while (!From->use_empty()) {
807 // Update the instruction to use the new value.
808 Use &TheUse = From->use_begin().getUse();
809 Instruction *User = cast<Instruction>(TheUse.getUser());
812 // Check to see if the instruction can be folded due to the operand
813 // replacement. For example changing (or X, Y) into (or X, -1) can replace
815 Value *SimplifiedVal;
817 // Sanity check to make sure 'User' doesn't dangle across
818 // SimplifyInstruction.
819 AssertingVH<> UserHandle(User);
821 SimplifiedVal = SimplifyInstruction(User, TD, DT);
822 if (SimplifiedVal == 0) continue;
825 // Recursively simplify this user to the new value.
826 ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT);
827 From = dyn_cast_or_null<Instruction>((Value*)FromHandle);
830 assert(ToHandle && "To value deleted by recursive simplification?");
832 // If the recursive simplification ended up revisiting and deleting
833 // 'From' then we're done.
838 // If 'From' has value handles referring to it, do a real RAUW to update them.
839 From->replaceAllUsesWith(To);
841 From->eraseFromParent();