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/Instructions.h"
19 #include "llvm/Support/PatternMatch.h"
21 using namespace llvm::PatternMatch;
23 /// SimplifyAndInst - Given operands for an And, see if we can
24 /// fold the result. If not, this returns null.
25 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1,
26 const TargetData *TD) {
27 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
28 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
29 Constant *Ops[] = { CLHS, CRHS };
30 return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
34 // Canonicalize the constant to the RHS.
39 if (isa<UndefValue>(Op1))
40 return Constant::getNullValue(Op0->getType());
47 if (isa<ConstantAggregateZero>(Op1))
51 if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1))
52 if (CP->isAllOnesValue())
55 if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) {
60 if (Op1CI->isAllOnesValue())
64 // A & ~A = ~A & A = 0
66 if (match(Op0, m_Not(m_Value(A)) && A == Op1) ||
67 match(Op1, m_Not(m_Value(A)) && A == Op0))
68 return Constant::getNullValue(Op0->getType());
71 if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
72 (A == Op1 || B == Op1))
76 if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
77 (A == Op0 || B == Op0))
83 /// SimplifyOrInst - Given operands for an Or, see if we can
84 /// fold the result. If not, this returns null.
85 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1,
86 const TargetData *TD) {
87 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
88 if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
89 Constant *Ops[] = { CLHS, CRHS };
90 return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
94 // Canonicalize the constant to the RHS.
99 if (isa<UndefValue>(Op1))
100 return Constant::getAllOnesValue(Op0->getType());
107 if (isa<ConstantAggregateZero>(Op1))
110 // X | <-1,-1> = <-1,-1>
111 if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1))
112 if (CP->isAllOnesValue())
115 if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) {
120 if (Op1CI->isAllOnesValue())
124 // A | ~A = ~A | A = -1
126 if (match(Op0, m_Not(m_Value(A)) && A == Op1) ||
127 match(Op1, m_Not(m_Value(A)) && A == Op0))
128 return Constant::getAllOnesValue(Op0->getType());
131 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
132 (A == Op1 || B == Op1))
136 if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
137 (A == Op0 || B == Op0))
146 static const Type *GetCompareTy(Value *Op) {
147 return CmpInst::makeCmpResultType(Op->getType());
151 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
152 /// fold the result. If not, this returns null.
153 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
154 const TargetData *TD) {
155 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
156 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
158 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
159 if (Constant *CRHS = dyn_cast<Constant>(RHS))
160 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
162 // If we have a constant, make sure it is on the RHS.
164 Pred = CmpInst::getSwappedPredicate(Pred);
167 // ITy - This is the return type of the compare we're considering.
168 const Type *ITy = GetCompareTy(LHS);
170 // icmp X, X -> true/false
172 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
174 if (isa<UndefValue>(RHS)) // X icmp undef -> undef
175 return UndefValue::get(ITy);
177 // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
178 // addresses never equal each other! We already know that Op0 != Op1.
179 if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) ||
180 isa<ConstantPointerNull>(LHS)) &&
181 (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) ||
182 isa<ConstantPointerNull>(RHS)))
183 return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
185 // See if we are doing a comparison with a constant.
186 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
187 // If we have an icmp le or icmp ge instruction, turn it into the
188 // appropriate icmp lt or icmp gt instruction. This allows us to rely on
189 // them being folded in the code below.
192 case ICmpInst::ICMP_ULE:
193 if (CI->isMaxValue(false)) // A <=u MAX -> TRUE
194 return ConstantInt::getTrue(CI->getContext());
196 case ICmpInst::ICMP_SLE:
197 if (CI->isMaxValue(true)) // A <=s MAX -> TRUE
198 return ConstantInt::getTrue(CI->getContext());
200 case ICmpInst::ICMP_UGE:
201 if (CI->isMinValue(false)) // A >=u MIN -> TRUE
202 return ConstantInt::getTrue(CI->getContext());
204 case ICmpInst::ICMP_SGE:
205 if (CI->isMinValue(true)) // A >=s MIN -> TRUE
206 return ConstantInt::getTrue(CI->getContext());
215 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
216 /// fold the result. If not, this returns null.
217 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
218 const TargetData *TD) {
219 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
220 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
222 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
223 if (Constant *CRHS = dyn_cast<Constant>(RHS))
224 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
226 // If we have a constant, make sure it is on the RHS.
228 Pred = CmpInst::getSwappedPredicate(Pred);
231 // Fold trivial predicates.
232 if (Pred == FCmpInst::FCMP_FALSE)
233 return ConstantInt::get(GetCompareTy(LHS), 0);
234 if (Pred == FCmpInst::FCMP_TRUE)
235 return ConstantInt::get(GetCompareTy(LHS), 1);
237 if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef
238 return UndefValue::get(GetCompareTy(LHS));
240 // fcmp x,x -> true/false. Not all compares are foldable.
242 if (CmpInst::isTrueWhenEqual(Pred))
243 return ConstantInt::get(GetCompareTy(LHS), 1);
244 if (CmpInst::isFalseWhenEqual(Pred))
245 return ConstantInt::get(GetCompareTy(LHS), 0);
248 // Handle fcmp with constant RHS
249 if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
250 // If the constant is a nan, see if we can fold the comparison based on it.
251 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
252 if (CFP->getValueAPF().isNaN()) {
253 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo"
254 return ConstantInt::getFalse(CFP->getContext());
255 assert(FCmpInst::isUnordered(Pred) &&
256 "Comparison must be either ordered or unordered!");
257 // True if unordered.
258 return ConstantInt::getTrue(CFP->getContext());
266 //=== Helper functions for higher up the class hierarchy.
268 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
269 /// fold the result. If not, this returns null.
270 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
271 const TargetData *TD) {
273 case Instruction::And: return SimplifyAndInst(LHS, RHS, TD);
274 case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD);
276 if (Constant *CLHS = dyn_cast<Constant>(LHS))
277 if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
278 Constant *COps[] = {CLHS, CRHS};
279 return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD);
285 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
287 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
288 const TargetData *TD) {
289 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
290 return SimplifyICmpInst(Predicate, LHS, RHS, TD);
291 return SimplifyFCmpInst(Predicate, LHS, RHS, TD);
295 /// SimplifyInstruction - See if we can compute a simplified version of this
296 /// instruction. If not, this returns null.
297 Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD) {
298 switch (I->getOpcode()) {
300 return ConstantFoldInstruction(I, TD);
301 case Instruction::And:
302 return SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD);
303 case Instruction::Or:
304 return SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD);
305 case Instruction::ICmp:
306 return SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
307 I->getOperand(0), I->getOperand(1), TD);
308 case Instruction::FCmp:
309 return SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
310 I->getOperand(0), I->getOperand(1), TD);