InstructionSimplify.cpp revision c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2 
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"
21using namespace llvm;
22using namespace llvm::PatternMatch;
23
24/// SimplifyAddInst - Given operands for an Add, see if we can
25/// fold the result.  If not, this returns null.
26Value *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.
55Value *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  return 0;
110}
111
112/// SimplifyOrInst - Given operands for an Or, see if we can
113/// fold the result.  If not, this returns null.
114Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD) {
115  if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
116    if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
117      Constant *Ops[] = { CLHS, CRHS };
118      return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
119                                      Ops, 2, TD);
120    }
121
122    // Canonicalize the constant to the RHS.
123    std::swap(Op0, Op1);
124  }
125
126  // X | undef -> -1
127  if (isa<UndefValue>(Op1))
128    return Constant::getAllOnesValue(Op0->getType());
129
130  // X | X = X
131  if (Op0 == Op1)
132    return Op0;
133
134  // X | <0,0> = X
135  if (isa<ConstantAggregateZero>(Op1))
136    return Op0;
137
138  // X | <-1,-1> = <-1,-1>
139  if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1))
140    if (CP->isAllOnesValue())
141      return Op1;
142
143  if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) {
144    // X | 0 = X
145    if (Op1CI->isZero())
146      return Op0;
147    // X | -1 = -1
148    if (Op1CI->isAllOnesValue())
149      return Op1CI;
150  }
151
152  // A | ~A  =  ~A | A  =  -1
153  Value *A, *B;
154  if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
155      (match(Op1, m_Not(m_Value(A))) && A == Op0))
156    return Constant::getAllOnesValue(Op0->getType());
157
158  // (A & ?) | A = A
159  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
160      (A == Op1 || B == Op1))
161    return Op1;
162
163  // A | (A & ?) = A
164  if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
165      (A == Op0 || B == Op0))
166    return Op0;
167
168  return 0;
169}
170
171
172static const Type *GetCompareTy(Value *Op) {
173  return CmpInst::makeCmpResultType(Op->getType());
174}
175
176
177/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
178/// fold the result.  If not, this returns null.
179Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
180                              const TargetData *TD) {
181  CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
182  assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
183
184  if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
185    if (Constant *CRHS = dyn_cast<Constant>(RHS))
186      return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
187
188    // If we have a constant, make sure it is on the RHS.
189    std::swap(LHS, RHS);
190    Pred = CmpInst::getSwappedPredicate(Pred);
191  }
192
193  // ITy - This is the return type of the compare we're considering.
194  const Type *ITy = GetCompareTy(LHS);
195
196  // icmp X, X -> true/false
197  // X icmp undef -> true/false.  For example, icmp ugt %X, undef -> false
198  // because X could be 0.
199  if (LHS == RHS || isa<UndefValue>(RHS))
200    return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
201
202  // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
203  // addresses never equal each other!  We already know that Op0 != Op1.
204  if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) ||
205       isa<ConstantPointerNull>(LHS)) &&
206      (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) ||
207       isa<ConstantPointerNull>(RHS)))
208    return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
209
210  // See if we are doing a comparison with a constant.
211  if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
212    // If we have an icmp le or icmp ge instruction, turn it into the
213    // appropriate icmp lt or icmp gt instruction.  This allows us to rely on
214    // them being folded in the code below.
215    switch (Pred) {
216    default: break;
217    case ICmpInst::ICMP_ULE:
218      if (CI->isMaxValue(false))                 // A <=u MAX -> TRUE
219        return ConstantInt::getTrue(CI->getContext());
220      break;
221    case ICmpInst::ICMP_SLE:
222      if (CI->isMaxValue(true))                  // A <=s MAX -> TRUE
223        return ConstantInt::getTrue(CI->getContext());
224      break;
225    case ICmpInst::ICMP_UGE:
226      if (CI->isMinValue(false))                 // A >=u MIN -> TRUE
227        return ConstantInt::getTrue(CI->getContext());
228      break;
229    case ICmpInst::ICMP_SGE:
230      if (CI->isMinValue(true))                  // A >=s MIN -> TRUE
231        return ConstantInt::getTrue(CI->getContext());
232      break;
233    }
234  }
235
236
237  return 0;
238}
239
240/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
241/// fold the result.  If not, this returns null.
242Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
243                              const TargetData *TD) {
244  CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
245  assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
246
247  if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
248    if (Constant *CRHS = dyn_cast<Constant>(RHS))
249      return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
250
251    // If we have a constant, make sure it is on the RHS.
252    std::swap(LHS, RHS);
253    Pred = CmpInst::getSwappedPredicate(Pred);
254  }
255
256  // Fold trivial predicates.
257  if (Pred == FCmpInst::FCMP_FALSE)
258    return ConstantInt::get(GetCompareTy(LHS), 0);
259  if (Pred == FCmpInst::FCMP_TRUE)
260    return ConstantInt::get(GetCompareTy(LHS), 1);
261
262  if (isa<UndefValue>(RHS))                  // fcmp pred X, undef -> undef
263    return UndefValue::get(GetCompareTy(LHS));
264
265  // fcmp x,x -> true/false.  Not all compares are foldable.
266  if (LHS == RHS) {
267    if (CmpInst::isTrueWhenEqual(Pred))
268      return ConstantInt::get(GetCompareTy(LHS), 1);
269    if (CmpInst::isFalseWhenEqual(Pred))
270      return ConstantInt::get(GetCompareTy(LHS), 0);
271  }
272
273  // Handle fcmp with constant RHS
274  if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
275    // If the constant is a nan, see if we can fold the comparison based on it.
276    if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
277      if (CFP->getValueAPF().isNaN()) {
278        if (FCmpInst::isOrdered(Pred))   // True "if ordered and foo"
279          return ConstantInt::getFalse(CFP->getContext());
280        assert(FCmpInst::isUnordered(Pred) &&
281               "Comparison must be either ordered or unordered!");
282        // True if unordered.
283        return ConstantInt::getTrue(CFP->getContext());
284      }
285      // Check whether the constant is an infinity.
286      if (CFP->getValueAPF().isInfinity()) {
287        if (CFP->getValueAPF().isNegative()) {
288          switch (Pred) {
289          case FCmpInst::FCMP_OLT:
290            // No value is ordered and less than negative infinity.
291            return ConstantInt::getFalse(CFP->getContext());
292          case FCmpInst::FCMP_UGE:
293            // All values are unordered with or at least negative infinity.
294            return ConstantInt::getTrue(CFP->getContext());
295          default:
296            break;
297          }
298        } else {
299          switch (Pred) {
300          case FCmpInst::FCMP_OGT:
301            // No value is ordered and greater than infinity.
302            return ConstantInt::getFalse(CFP->getContext());
303          case FCmpInst::FCMP_ULE:
304            // All values are unordered with and at most infinity.
305            return ConstantInt::getTrue(CFP->getContext());
306          default:
307            break;
308          }
309        }
310      }
311    }
312  }
313
314  return 0;
315}
316
317/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
318/// fold the result.  If not, this returns null.
319Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps,
320                             const TargetData *TD) {
321  // getelementptr P -> P.
322  if (NumOps == 1)
323    return Ops[0];
324
325  // TODO.
326  //if (isa<UndefValue>(Ops[0]))
327  //  return UndefValue::get(GEP.getType());
328
329  // getelementptr P, 0 -> P.
330  if (NumOps == 2)
331    if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
332      if (C->isZero())
333        return Ops[0];
334
335  // Check to see if this is constant foldable.
336  for (unsigned i = 0; i != NumOps; ++i)
337    if (!isa<Constant>(Ops[i]))
338      return 0;
339
340  return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]),
341                                        (Constant *const*)Ops+1, NumOps-1);
342}
343
344
345//=== Helper functions for higher up the class hierarchy.
346
347/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
348/// fold the result.  If not, this returns null.
349Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
350                           const TargetData *TD) {
351  switch (Opcode) {
352  case Instruction::And: return SimplifyAndInst(LHS, RHS, TD);
353  case Instruction::Or:  return SimplifyOrInst(LHS, RHS, TD);
354  default:
355    if (Constant *CLHS = dyn_cast<Constant>(LHS))
356      if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
357        Constant *COps[] = {CLHS, CRHS};
358        return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD);
359      }
360    return 0;
361  }
362}
363
364/// SimplifyCmpInst - Given operands for a CmpInst, see if we can
365/// fold the result.
366Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
367                             const TargetData *TD) {
368  if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
369    return SimplifyICmpInst(Predicate, LHS, RHS, TD);
370  return SimplifyFCmpInst(Predicate, LHS, RHS, TD);
371}
372
373
374/// SimplifyInstruction - See if we can compute a simplified version of this
375/// instruction.  If not, this returns null.
376Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD) {
377  switch (I->getOpcode()) {
378  default:
379    return ConstantFoldInstruction(I, TD);
380  case Instruction::Add:
381    return SimplifyAddInst(I->getOperand(0), I->getOperand(1),
382                           cast<BinaryOperator>(I)->hasNoSignedWrap(),
383                           cast<BinaryOperator>(I)->hasNoUnsignedWrap(), TD);
384  case Instruction::And:
385    return SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD);
386  case Instruction::Or:
387    return SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD);
388  case Instruction::ICmp:
389    return SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
390                            I->getOperand(0), I->getOperand(1), TD);
391  case Instruction::FCmp:
392    return SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
393                            I->getOperand(0), I->getOperand(1), TD);
394  case Instruction::GetElementPtr: {
395    SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
396    return SimplifyGEPInst(&Ops[0], Ops.size(), TD);
397  }
398  }
399}
400
401/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
402/// delete the From instruction.  In addition to a basic RAUW, this does a
403/// recursive simplification of the newly formed instructions.  This catches
404/// things where one simplification exposes other opportunities.  This only
405/// simplifies and deletes scalar operations, it does not change the CFG.
406///
407void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
408                                     const TargetData *TD) {
409  assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!");
410
411  // FromHandle - This keeps a weakvh on the from value so that we can know if
412  // it gets deleted out from under us in a recursive simplification.
413  WeakVH FromHandle(From);
414
415  while (!From->use_empty()) {
416    // Update the instruction to use the new value.
417    Use &U = From->use_begin().getUse();
418    Instruction *User = cast<Instruction>(U.getUser());
419    U = To;
420
421    // See if we can simplify it.
422    if (Value *V = SimplifyInstruction(User, TD)) {
423      // Recursively simplify this.
424      ReplaceAndSimplifyAllUses(User, V, TD);
425
426      // If the recursive simplification ended up revisiting and deleting 'From'
427      // then we're done.
428      if (FromHandle == 0)
429        return;
430    }
431  }
432  From->eraseFromParent();
433}
434
435