Fix a README item: when doing a comparison with the result
[oota-llvm.git] / lib / Analysis / InstructionSimplify.cpp
1 //===- InstructionSimplify.cpp - Fold instruction operands ----------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
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.
13 //
14 //===----------------------------------------------------------------------===//
15
16 #include "llvm/Analysis/InstructionSimplify.h"
17 #include "llvm/Analysis/ConstantFolding.h"
18 #include "llvm/Support/ValueHandle.h"
19 #include "llvm/Instructions.h"
20 #include "llvm/Support/PatternMatch.h"
21 using namespace llvm;
22 using namespace llvm::PatternMatch;
23
24 /// SimplifyAddInst - Given operands for an Add, see if we can
25 /// fold the result.  If not, this returns null.
26 Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
27                              const TargetData *TD) {
28   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
29     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
30       Constant *Ops[] = { CLHS, CRHS };
31       return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(),
32                                       Ops, 2, TD);
33     }
34     
35     // Canonicalize the constant to the RHS.
36     std::swap(Op0, Op1);
37   }
38   
39   if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
40     // X + undef -> undef
41     if (isa<UndefValue>(Op1C))
42       return Op1C;
43     
44     // X + 0 --> X
45     if (Op1C->isNullValue())
46       return Op0;
47   }
48   
49   // FIXME: Could pull several more out of instcombine.
50   return 0;
51 }
52
53 /// SimplifyAndInst - Given operands for an And, see if we can
54 /// fold the result.  If not, this returns null.
55 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD) {
56   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
57     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
58       Constant *Ops[] = { CLHS, CRHS };
59       return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
60                                       Ops, 2, TD);
61     }
62   
63     // Canonicalize the constant to the RHS.
64     std::swap(Op0, Op1);
65   }
66   
67   // X & undef -> 0
68   if (isa<UndefValue>(Op1))
69     return Constant::getNullValue(Op0->getType());
70   
71   // X & X = X
72   if (Op0 == Op1)
73     return Op0;
74   
75   // X & <0,0> = <0,0>
76   if (isa<ConstantAggregateZero>(Op1))
77     return Op1;
78   
79   // X & <-1,-1> = X
80   if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1))
81     if (CP->isAllOnesValue())
82       return Op0;
83   
84   if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) {
85     // X & 0 = 0
86     if (Op1CI->isZero())
87       return Op1CI;
88     // X & -1 = X
89     if (Op1CI->isAllOnesValue())
90       return Op0;
91   }
92   
93   // A & ~A  =  ~A & A  =  0
94   Value *A, *B;
95   if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
96       (match(Op1, m_Not(m_Value(A))) && A == Op0))
97     return Constant::getNullValue(Op0->getType());
98   
99   // (A | ?) & A = A
100   if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
101       (A == Op1 || B == Op1))
102     return Op1;
103   
104   // A & (A | ?) = A
105   if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
106       (A == Op0 || B == Op0))
107     return Op0;
108   
109   // (A & B) & A -> A & B
110   if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
111       (A == Op1 || B == Op1))
112     return Op0;
113
114   // A & (A & B) -> A & B
115   if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
116       (A == Op0 || B == Op0))
117     return Op1;
118
119   return 0;
120 }
121
122 /// SimplifyOrInst - Given operands for an Or, see if we can
123 /// fold the result.  If not, this returns null.
124 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD) {
125   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
126     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
127       Constant *Ops[] = { CLHS, CRHS };
128       return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
129                                       Ops, 2, TD);
130     }
131     
132     // Canonicalize the constant to the RHS.
133     std::swap(Op0, Op1);
134   }
135   
136   // X | undef -> -1
137   if (isa<UndefValue>(Op1))
138     return Constant::getAllOnesValue(Op0->getType());
139   
140   // X | X = X
141   if (Op0 == Op1)
142     return Op0;
143
144   // X | <0,0> = X
145   if (isa<ConstantAggregateZero>(Op1))
146     return Op0;
147   
148   // X | <-1,-1> = <-1,-1>
149   if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1))
150     if (CP->isAllOnesValue())            
151       return Op1;
152   
153   if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) {
154     // X | 0 = X
155     if (Op1CI->isZero())
156       return Op0;
157     // X | -1 = -1
158     if (Op1CI->isAllOnesValue())
159       return Op1CI;
160   }
161   
162   // A | ~A  =  ~A | A  =  -1
163   Value *A, *B;
164   if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
165       (match(Op1, m_Not(m_Value(A))) && A == Op0))
166     return Constant::getAllOnesValue(Op0->getType());
167   
168   // (A & ?) | A = A
169   if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
170       (A == Op1 || B == Op1))
171     return Op1;
172   
173   // A | (A & ?) = A
174   if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
175       (A == Op0 || B == Op0))
176     return Op0;
177   
178   // (A | B) | A -> A | B
179   if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
180       (A == Op1 || B == Op1))
181     return Op0;
182
183   // A | (A | B) -> A | B
184   if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
185       (A == Op0 || B == Op0))
186     return Op1;
187
188   return 0;
189 }
190
191
192 static const Type *GetCompareTy(Value *Op) {
193   return CmpInst::makeCmpResultType(Op->getType());
194 }
195
196
197 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
198 /// fold the result.  If not, this returns null.
199 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
200                               const TargetData *TD) {
201   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
202   assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
203   
204   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
205     if (Constant *CRHS = dyn_cast<Constant>(RHS))
206       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
207
208     // If we have a constant, make sure it is on the RHS.
209     std::swap(LHS, RHS);
210     Pred = CmpInst::getSwappedPredicate(Pred);
211   }
212   
213   // ITy - This is the return type of the compare we're considering.
214   const Type *ITy = GetCompareTy(LHS);
215   
216   // icmp X, X -> true/false
217   // X icmp undef -> true/false.  For example, icmp ugt %X, undef -> false
218   // because X could be 0.
219   if (LHS == RHS || isa<UndefValue>(RHS))
220     return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
221   
222   // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
223   // addresses never equal each other!  We already know that Op0 != Op1.
224   if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) || 
225        isa<ConstantPointerNull>(LHS)) &&
226       (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) || 
227        isa<ConstantPointerNull>(RHS)))
228     return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
229   
230   // See if we are doing a comparison with a constant.
231   if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
232     // If we have an icmp le or icmp ge instruction, turn it into the
233     // appropriate icmp lt or icmp gt instruction.  This allows us to rely on
234     // them being folded in the code below.
235     switch (Pred) {
236     default: break;
237     case ICmpInst::ICMP_ULE:
238       if (CI->isMaxValue(false))                 // A <=u MAX -> TRUE
239         return ConstantInt::getTrue(CI->getContext());
240       break;
241     case ICmpInst::ICMP_SLE:
242       if (CI->isMaxValue(true))                  // A <=s MAX -> TRUE
243         return ConstantInt::getTrue(CI->getContext());
244       break;
245     case ICmpInst::ICMP_UGE:
246       if (CI->isMinValue(false))                 // A >=u MIN -> TRUE
247         return ConstantInt::getTrue(CI->getContext());
248       break;
249     case ICmpInst::ICMP_SGE:
250       if (CI->isMinValue(true))                  // A >=s MIN -> TRUE
251         return ConstantInt::getTrue(CI->getContext());
252       break;
253     }
254   }
255
256   // If the comparison is with the result of a select instruction, check whether
257   // comparing with either branch of the select always yields the same value.
258   if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) {
259     // Make sure the select is on the LHS.
260     if (!isa<SelectInst>(LHS)) {
261       std::swap(LHS, RHS);
262       Pred = CmpInst::getSwappedPredicate(Pred);
263     }
264     SelectInst *SI = cast<SelectInst>(LHS);
265     // Now that we have "icmp select(cond, TV, FV), RHS", analyse it.
266     // Does "icmp TV, RHS" simplify?
267     if (Value *TCmp = SimplifyICmpInst(Pred, SI->getTrueValue(), RHS, TD))
268       // It does!  Does "icmp FV, RHS" simplify?
269       if (Value *FCmp = SimplifyICmpInst(Pred, SI->getFalseValue(), RHS, TD))
270         // It does!  If they simplified to the same value, then use it as the
271         // result of the original comparison.
272         if (TCmp == FCmp)
273           return TCmp;
274   }
275
276   return 0;
277 }
278
279 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
280 /// fold the result.  If not, this returns null.
281 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
282                               const TargetData *TD) {
283   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
284   assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
285
286   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
287     if (Constant *CRHS = dyn_cast<Constant>(RHS))
288       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
289    
290     // If we have a constant, make sure it is on the RHS.
291     std::swap(LHS, RHS);
292     Pred = CmpInst::getSwappedPredicate(Pred);
293   }
294   
295   // Fold trivial predicates.
296   if (Pred == FCmpInst::FCMP_FALSE)
297     return ConstantInt::get(GetCompareTy(LHS), 0);
298   if (Pred == FCmpInst::FCMP_TRUE)
299     return ConstantInt::get(GetCompareTy(LHS), 1);
300
301   if (isa<UndefValue>(RHS))                  // fcmp pred X, undef -> undef
302     return UndefValue::get(GetCompareTy(LHS));
303
304   // fcmp x,x -> true/false.  Not all compares are foldable.
305   if (LHS == RHS) {
306     if (CmpInst::isTrueWhenEqual(Pred))
307       return ConstantInt::get(GetCompareTy(LHS), 1);
308     if (CmpInst::isFalseWhenEqual(Pred))
309       return ConstantInt::get(GetCompareTy(LHS), 0);
310   }
311   
312   // Handle fcmp with constant RHS
313   if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
314     // If the constant is a nan, see if we can fold the comparison based on it.
315     if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
316       if (CFP->getValueAPF().isNaN()) {
317         if (FCmpInst::isOrdered(Pred))   // True "if ordered and foo"
318           return ConstantInt::getFalse(CFP->getContext());
319         assert(FCmpInst::isUnordered(Pred) &&
320                "Comparison must be either ordered or unordered!");
321         // True if unordered.
322         return ConstantInt::getTrue(CFP->getContext());
323       }
324       // Check whether the constant is an infinity.
325       if (CFP->getValueAPF().isInfinity()) {
326         if (CFP->getValueAPF().isNegative()) {
327           switch (Pred) {
328           case FCmpInst::FCMP_OLT:
329             // No value is ordered and less than negative infinity.
330             return ConstantInt::getFalse(CFP->getContext());
331           case FCmpInst::FCMP_UGE:
332             // All values are unordered with or at least negative infinity.
333             return ConstantInt::getTrue(CFP->getContext());
334           default:
335             break;
336           }
337         } else {
338           switch (Pred) {
339           case FCmpInst::FCMP_OGT:
340             // No value is ordered and greater than infinity.
341             return ConstantInt::getFalse(CFP->getContext());
342           case FCmpInst::FCMP_ULE:
343             // All values are unordered with and at most infinity.
344             return ConstantInt::getTrue(CFP->getContext());
345           default:
346             break;
347           }
348         }
349       }
350     }
351   }
352   
353   return 0;
354 }
355
356 /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
357 /// the result.  If not, this returns null.
358 Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal,
359                                 const TargetData *TD) {
360   // select true, X, Y  -> X
361   // select false, X, Y -> Y
362   if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal))
363     return CB->getZExtValue() ? TrueVal : FalseVal;
364   
365   // select C, X, X -> X
366   if (TrueVal == FalseVal)
367     return TrueVal;
368   
369   if (isa<UndefValue>(TrueVal))   // select C, undef, X -> X
370     return FalseVal;
371   if (isa<UndefValue>(FalseVal))   // select C, X, undef -> X
372     return TrueVal;
373   if (isa<UndefValue>(CondVal)) {  // select undef, X, Y -> X or Y
374     if (isa<Constant>(TrueVal))
375       return TrueVal;
376     return FalseVal;
377   }
378   
379   
380   
381   return 0;
382 }
383
384
385 /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
386 /// fold the result.  If not, this returns null.
387 Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps,
388                              const TargetData *TD) {
389   // getelementptr P -> P.
390   if (NumOps == 1)
391     return Ops[0];
392
393   // TODO.
394   //if (isa<UndefValue>(Ops[0]))
395   //  return UndefValue::get(GEP.getType());
396
397   // getelementptr P, 0 -> P.
398   if (NumOps == 2)
399     if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
400       if (C->isZero())
401         return Ops[0];
402   
403   // Check to see if this is constant foldable.
404   for (unsigned i = 0; i != NumOps; ++i)
405     if (!isa<Constant>(Ops[i]))
406       return 0;
407   
408   return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]),
409                                         (Constant *const*)Ops+1, NumOps-1);
410 }
411
412
413 //=== Helper functions for higher up the class hierarchy.
414
415 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
416 /// fold the result.  If not, this returns null.
417 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 
418                            const TargetData *TD) {
419   switch (Opcode) {
420   case Instruction::And: return SimplifyAndInst(LHS, RHS, TD);
421   case Instruction::Or:  return SimplifyOrInst(LHS, RHS, TD);
422   default:
423     if (Constant *CLHS = dyn_cast<Constant>(LHS))
424       if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
425         Constant *COps[] = {CLHS, CRHS};
426         return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD);
427       }
428     return 0;
429   }
430 }
431
432 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
433 /// fold the result.
434 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
435                              const TargetData *TD) {
436   if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
437     return SimplifyICmpInst(Predicate, LHS, RHS, TD);
438   return SimplifyFCmpInst(Predicate, LHS, RHS, TD);
439 }
440
441
442 /// SimplifyInstruction - See if we can compute a simplified version of this
443 /// instruction.  If not, this returns null.
444 Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD) {
445   switch (I->getOpcode()) {
446   default:
447     return ConstantFoldInstruction(I, TD);
448   case Instruction::Add:
449     return SimplifyAddInst(I->getOperand(0), I->getOperand(1),
450                            cast<BinaryOperator>(I)->hasNoSignedWrap(),
451                            cast<BinaryOperator>(I)->hasNoUnsignedWrap(), TD);
452   case Instruction::And:
453     return SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD);
454   case Instruction::Or:
455     return SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD);
456   case Instruction::ICmp:
457     return SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
458                             I->getOperand(0), I->getOperand(1), TD);
459   case Instruction::FCmp:
460     return SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
461                             I->getOperand(0), I->getOperand(1), TD);
462   case Instruction::Select:
463     return SimplifySelectInst(I->getOperand(0), I->getOperand(1),
464                               I->getOperand(2), TD);
465   case Instruction::GetElementPtr: {
466     SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
467     return SimplifyGEPInst(&Ops[0], Ops.size(), TD);
468   }
469   }
470 }
471
472 /// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
473 /// delete the From instruction.  In addition to a basic RAUW, this does a
474 /// recursive simplification of the newly formed instructions.  This catches
475 /// things where one simplification exposes other opportunities.  This only
476 /// simplifies and deletes scalar operations, it does not change the CFG.
477 ///
478 void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
479                                      const TargetData *TD) {
480   assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!");
481   
482   // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that
483   // we can know if it gets deleted out from under us or replaced in a
484   // recursive simplification.
485   WeakVH FromHandle(From);
486   WeakVH ToHandle(To);
487   
488   while (!From->use_empty()) {
489     // Update the instruction to use the new value.
490     Use &TheUse = From->use_begin().getUse();
491     Instruction *User = cast<Instruction>(TheUse.getUser());
492     TheUse = To;
493
494     // Check to see if the instruction can be folded due to the operand
495     // replacement.  For example changing (or X, Y) into (or X, -1) can replace
496     // the 'or' with -1.
497     Value *SimplifiedVal;
498     {
499       // Sanity check to make sure 'User' doesn't dangle across
500       // SimplifyInstruction.
501       AssertingVH<> UserHandle(User);
502     
503       SimplifiedVal = SimplifyInstruction(User, TD);
504       if (SimplifiedVal == 0) continue;
505     }
506     
507     // Recursively simplify this user to the new value.
508     ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD);
509     From = dyn_cast_or_null<Instruction>((Value*)FromHandle);
510     To = ToHandle;
511       
512     assert(ToHandle && "To value deleted by recursive simplification?");
513       
514     // If the recursive simplification ended up revisiting and deleting
515     // 'From' then we're done.
516     if (From == 0)
517       return;
518   }
519   
520   // If 'From' has value handles referring to it, do a real RAUW to update them.
521   From->replaceAllUsesWith(To);
522   
523   From->eraseFromParent();
524 }
525