InstructionSimplify.cpp revision d04a8d4b33ff316ca4cf961e06c9e312eff8e64f 
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.  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").  All operands are assumed to have already been
15// simplified: This is usually true and assuming it simplifies the logic (if
16// they have not been simplified then results are correct but maybe suboptimal).
17//
18//===----------------------------------------------------------------------===//
19
20#define DEBUG_TYPE "instsimplify"
21#include "llvm/Analysis/InstructionSimplify.h"
22#include "llvm/ADT/SetVector.h"
23#include "llvm/ADT/Statistic.h"
24#include "llvm/Analysis/AliasAnalysis.h"
25#include "llvm/Analysis/ConstantFolding.h"
26#include "llvm/Analysis/Dominators.h"
27#include "llvm/Analysis/ValueTracking.h"
28#include "llvm/DataLayout.h"
29#include "llvm/GlobalAlias.h"
30#include "llvm/Operator.h"
31#include "llvm/Support/ConstantRange.h"
32#include "llvm/Support/GetElementPtrTypeIterator.h"
33#include "llvm/Support/PatternMatch.h"
34#include "llvm/Support/ValueHandle.h"
35using namespace llvm;
36using namespace llvm::PatternMatch;
37
38enum { RecursionLimit = 3 };
39
40STATISTIC(NumExpand,  "Number of expansions");
41STATISTIC(NumFactor , "Number of factorizations");
42STATISTIC(NumReassoc, "Number of reassociations");
43
44struct Query {
45  const DataLayout *TD;
46  const TargetLibraryInfo *TLI;
47  const DominatorTree *DT;
48
49  Query(const DataLayout *td, const TargetLibraryInfo *tli,
50        const DominatorTree *dt) : TD(td), TLI(tli), DT(dt) {}
51};
52
53static Value *SimplifyAndInst(Value *, Value *, const Query &, unsigned);
54static Value *SimplifyBinOp(unsigned, Value *, Value *, const Query &,
55                            unsigned);
56static Value *SimplifyCmpInst(unsigned, Value *, Value *, const Query &,
57                              unsigned);
58static Value *SimplifyOrInst(Value *, Value *, const Query &, unsigned);
59static Value *SimplifyXorInst(Value *, Value *, const Query &, unsigned);
60static Value *SimplifyTruncInst(Value *, Type *, const Query &, unsigned);
61
62/// getFalse - For a boolean type, or a vector of boolean type, return false, or
63/// a vector with every element false, as appropriate for the type.
64static Constant *getFalse(Type *Ty) {
65  assert(Ty->getScalarType()->isIntegerTy(1) &&
66         "Expected i1 type or a vector of i1!");
67  return Constant::getNullValue(Ty);
68}
69
70/// getTrue - For a boolean type, or a vector of boolean type, return true, or
71/// a vector with every element true, as appropriate for the type.
72static Constant *getTrue(Type *Ty) {
73  assert(Ty->getScalarType()->isIntegerTy(1) &&
74         "Expected i1 type or a vector of i1!");
75  return Constant::getAllOnesValue(Ty);
76}
77
78/// isSameCompare - Is V equivalent to the comparison "LHS Pred RHS"?
79static bool isSameCompare(Value *V, CmpInst::Predicate Pred, Value *LHS,
80                          Value *RHS) {
81  CmpInst *Cmp = dyn_cast<CmpInst>(V);
82  if (!Cmp)
83    return false;
84  CmpInst::Predicate CPred = Cmp->getPredicate();
85  Value *CLHS = Cmp->getOperand(0), *CRHS = Cmp->getOperand(1);
86  if (CPred == Pred && CLHS == LHS && CRHS == RHS)
87    return true;
88  return CPred == CmpInst::getSwappedPredicate(Pred) && CLHS == RHS &&
89    CRHS == LHS;
90}
91
92/// ValueDominatesPHI - Does the given value dominate the specified phi node?
93static bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
94  Instruction *I = dyn_cast<Instruction>(V);
95  if (!I)
96    // Arguments and constants dominate all instructions.
97    return true;
98
99  // If we are processing instructions (and/or basic blocks) that have not been
100  // fully added to a function, the parent nodes may still be null. Simply
101  // return the conservative answer in these cases.
102  if (!I->getParent() || !P->getParent() || !I->getParent()->getParent())
103    return false;
104
105  // If we have a DominatorTree then do a precise test.
106  if (DT) {
107    if (!DT->isReachableFromEntry(P->getParent()))
108      return true;
109    if (!DT->isReachableFromEntry(I->getParent()))
110      return false;
111    return DT->dominates(I, P);
112  }
113
114  // Otherwise, if the instruction is in the entry block, and is not an invoke,
115  // then it obviously dominates all phi nodes.
116  if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() &&
117      !isa<InvokeInst>(I))
118    return true;
119
120  return false;
121}
122
123/// ExpandBinOp - Simplify "A op (B op' C)" by distributing op over op', turning
124/// it into "(A op B) op' (A op C)".  Here "op" is given by Opcode and "op'" is
125/// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS.
126/// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)".
127/// Returns the simplified value, or null if no simplification was performed.
128static Value *ExpandBinOp(unsigned Opcode, Value *LHS, Value *RHS,
129                          unsigned OpcToExpand, const Query &Q,
130                          unsigned MaxRecurse) {
131  Instruction::BinaryOps OpcodeToExpand = (Instruction::BinaryOps)OpcToExpand;
132  // Recursion is always used, so bail out at once if we already hit the limit.
133  if (!MaxRecurse--)
134    return 0;
135
136  // Check whether the expression has the form "(A op' B) op C".
137  if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS))
138    if (Op0->getOpcode() == OpcodeToExpand) {
139      // It does!  Try turning it into "(A op C) op' (B op C)".
140      Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS;
141      // Do "A op C" and "B op C" both simplify?
142      if (Value *L = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse))
143        if (Value *R = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) {
144          // They do! Return "L op' R" if it simplifies or is already available.
145          // If "L op' R" equals "A op' B" then "L op' R" is just the LHS.
146          if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand)
147                                     && L == B && R == A)) {
148            ++NumExpand;
149            return LHS;
150          }
151          // Otherwise return "L op' R" if it simplifies.
152          if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) {
153            ++NumExpand;
154            return V;
155          }
156        }
157    }
158
159  // Check whether the expression has the form "A op (B op' C)".
160  if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS))
161    if (Op1->getOpcode() == OpcodeToExpand) {
162      // It does!  Try turning it into "(A op B) op' (A op C)".
163      Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1);
164      // Do "A op B" and "A op C" both simplify?
165      if (Value *L = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse))
166        if (Value *R = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) {
167          // They do! Return "L op' R" if it simplifies or is already available.
168          // If "L op' R" equals "B op' C" then "L op' R" is just the RHS.
169          if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand)
170                                     && L == C && R == B)) {
171            ++NumExpand;
172            return RHS;
173          }
174          // Otherwise return "L op' R" if it simplifies.
175          if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) {
176            ++NumExpand;
177            return V;
178          }
179        }
180    }
181
182  return 0;
183}
184
185/// FactorizeBinOp - Simplify "LHS Opcode RHS" by factorizing out a common term
186/// using the operation OpCodeToExtract.  For example, when Opcode is Add and
187/// OpCodeToExtract is Mul then this tries to turn "(A*B)+(A*C)" into "A*(B+C)".
188/// Returns the simplified value, or null if no simplification was performed.
189static Value *FactorizeBinOp(unsigned Opcode, Value *LHS, Value *RHS,
190                             unsigned OpcToExtract, const Query &Q,
191                             unsigned MaxRecurse) {
192  Instruction::BinaryOps OpcodeToExtract = (Instruction::BinaryOps)OpcToExtract;
193  // Recursion is always used, so bail out at once if we already hit the limit.
194  if (!MaxRecurse--)
195    return 0;
196
197  BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
198  BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
199
200  if (!Op0 || Op0->getOpcode() != OpcodeToExtract ||
201      !Op1 || Op1->getOpcode() != OpcodeToExtract)
202    return 0;
203
204  // The expression has the form "(A op' B) op (C op' D)".
205  Value *A = Op0->getOperand(0), *B = Op0->getOperand(1);
206  Value *C = Op1->getOperand(0), *D = Op1->getOperand(1);
207
208  // Use left distributivity, i.e. "X op' (Y op Z) = (X op' Y) op (X op' Z)".
209  // Does the instruction have the form "(A op' B) op (A op' D)" or, in the
210  // commutative case, "(A op' B) op (C op' A)"?
211  if (A == C || (Instruction::isCommutative(OpcodeToExtract) && A == D)) {
212    Value *DD = A == C ? D : C;
213    // Form "A op' (B op DD)" if it simplifies completely.
214    // Does "B op DD" simplify?
215    if (Value *V = SimplifyBinOp(Opcode, B, DD, Q, MaxRecurse)) {
216      // It does!  Return "A op' V" if it simplifies or is already available.
217      // If V equals B then "A op' V" is just the LHS.  If V equals DD then
218      // "A op' V" is just the RHS.
219      if (V == B || V == DD) {
220        ++NumFactor;
221        return V == B ? LHS : RHS;
222      }
223      // Otherwise return "A op' V" if it simplifies.
224      if (Value *W = SimplifyBinOp(OpcodeToExtract, A, V, Q, MaxRecurse)) {
225        ++NumFactor;
226        return W;
227      }
228    }
229  }
230
231  // Use right distributivity, i.e. "(X op Y) op' Z = (X op' Z) op (Y op' Z)".
232  // Does the instruction have the form "(A op' B) op (C op' B)" or, in the
233  // commutative case, "(A op' B) op (B op' D)"?
234  if (B == D || (Instruction::isCommutative(OpcodeToExtract) && B == C)) {
235    Value *CC = B == D ? C : D;
236    // Form "(A op CC) op' B" if it simplifies completely..
237    // Does "A op CC" simplify?
238    if (Value *V = SimplifyBinOp(Opcode, A, CC, Q, MaxRecurse)) {
239      // It does!  Return "V op' B" if it simplifies or is already available.
240      // If V equals A then "V op' B" is just the LHS.  If V equals CC then
241      // "V op' B" is just the RHS.
242      if (V == A || V == CC) {
243        ++NumFactor;
244        return V == A ? LHS : RHS;
245      }
246      // Otherwise return "V op' B" if it simplifies.
247      if (Value *W = SimplifyBinOp(OpcodeToExtract, V, B, Q, MaxRecurse)) {
248        ++NumFactor;
249        return W;
250      }
251    }
252  }
253
254  return 0;
255}
256
257/// SimplifyAssociativeBinOp - Generic simplifications for associative binary
258/// operations.  Returns the simpler value, or null if none was found.
259static Value *SimplifyAssociativeBinOp(unsigned Opc, Value *LHS, Value *RHS,
260                                       const Query &Q, unsigned MaxRecurse) {
261  Instruction::BinaryOps Opcode = (Instruction::BinaryOps)Opc;
262  assert(Instruction::isAssociative(Opcode) && "Not an associative operation!");
263
264  // Recursion is always used, so bail out at once if we already hit the limit.
265  if (!MaxRecurse--)
266    return 0;
267
268  BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
269  BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
270
271  // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely.
272  if (Op0 && Op0->getOpcode() == Opcode) {
273    Value *A = Op0->getOperand(0);
274    Value *B = Op0->getOperand(1);
275    Value *C = RHS;
276
277    // Does "B op C" simplify?
278    if (Value *V = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) {
279      // It does!  Return "A op V" if it simplifies or is already available.
280      // If V equals B then "A op V" is just the LHS.
281      if (V == B) return LHS;
282      // Otherwise return "A op V" if it simplifies.
283      if (Value *W = SimplifyBinOp(Opcode, A, V, Q, MaxRecurse)) {
284        ++NumReassoc;
285        return W;
286      }
287    }
288  }
289
290  // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely.
291  if (Op1 && Op1->getOpcode() == Opcode) {
292    Value *A = LHS;
293    Value *B = Op1->getOperand(0);
294    Value *C = Op1->getOperand(1);
295
296    // Does "A op B" simplify?
297    if (Value *V = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse)) {
298      // It does!  Return "V op C" if it simplifies or is already available.
299      // If V equals B then "V op C" is just the RHS.
300      if (V == B) return RHS;
301      // Otherwise return "V op C" if it simplifies.
302      if (Value *W = SimplifyBinOp(Opcode, V, C, Q, MaxRecurse)) {
303        ++NumReassoc;
304        return W;
305      }
306    }
307  }
308
309  // The remaining transforms require commutativity as well as associativity.
310  if (!Instruction::isCommutative(Opcode))
311    return 0;
312
313  // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely.
314  if (Op0 && Op0->getOpcode() == Opcode) {
315    Value *A = Op0->getOperand(0);
316    Value *B = Op0->getOperand(1);
317    Value *C = RHS;
318
319    // Does "C op A" simplify?
320    if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) {
321      // It does!  Return "V op B" if it simplifies or is already available.
322      // If V equals A then "V op B" is just the LHS.
323      if (V == A) return LHS;
324      // Otherwise return "V op B" if it simplifies.
325      if (Value *W = SimplifyBinOp(Opcode, V, B, Q, MaxRecurse)) {
326        ++NumReassoc;
327        return W;
328      }
329    }
330  }
331
332  // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely.
333  if (Op1 && Op1->getOpcode() == Opcode) {
334    Value *A = LHS;
335    Value *B = Op1->getOperand(0);
336    Value *C = Op1->getOperand(1);
337
338    // Does "C op A" simplify?
339    if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) {
340      // It does!  Return "B op V" if it simplifies or is already available.
341      // If V equals C then "B op V" is just the RHS.
342      if (V == C) return RHS;
343      // Otherwise return "B op V" if it simplifies.
344      if (Value *W = SimplifyBinOp(Opcode, B, V, Q, MaxRecurse)) {
345        ++NumReassoc;
346        return W;
347      }
348    }
349  }
350
351  return 0;
352}
353
354/// ThreadBinOpOverSelect - In the case of a binary operation with a select
355/// instruction as an operand, try to simplify the binop by seeing whether
356/// evaluating it on both branches of the select results in the same value.
357/// Returns the common value if so, otherwise returns null.
358static Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS,
359                                    const Query &Q, unsigned MaxRecurse) {
360  // Recursion is always used, so bail out at once if we already hit the limit.
361  if (!MaxRecurse--)
362    return 0;
363
364  SelectInst *SI;
365  if (isa<SelectInst>(LHS)) {
366    SI = cast<SelectInst>(LHS);
367  } else {
368    assert(isa<SelectInst>(RHS) && "No select instruction operand!");
369    SI = cast<SelectInst>(RHS);
370  }
371
372  // Evaluate the BinOp on the true and false branches of the select.
373  Value *TV;
374  Value *FV;
375  if (SI == LHS) {
376    TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, Q, MaxRecurse);
377    FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, Q, MaxRecurse);
378  } else {
379    TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), Q, MaxRecurse);
380    FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), Q, MaxRecurse);
381  }
382
383  // If they simplified to the same value, then return the common value.
384  // If they both failed to simplify then return null.
385  if (TV == FV)
386    return TV;
387
388  // If one branch simplified to undef, return the other one.
389  if (TV && isa<UndefValue>(TV))
390    return FV;
391  if (FV && isa<UndefValue>(FV))
392    return TV;
393
394  // If applying the operation did not change the true and false select values,
395  // then the result of the binop is the select itself.
396  if (TV == SI->getTrueValue() && FV == SI->getFalseValue())
397    return SI;
398
399  // If one branch simplified and the other did not, and the simplified
400  // value is equal to the unsimplified one, return the simplified value.
401  // For example, select (cond, X, X & Z) & Z -> X & Z.
402  if ((FV && !TV) || (TV && !FV)) {
403    // Check that the simplified value has the form "X op Y" where "op" is the
404    // same as the original operation.
405    Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV);
406    if (Simplified && Simplified->getOpcode() == Opcode) {
407      // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS".
408      // We already know that "op" is the same as for the simplified value.  See
409      // if the operands match too.  If so, return the simplified value.
410      Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue();
411      Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS;
412      Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch;
413      if (Simplified->getOperand(0) == UnsimplifiedLHS &&
414          Simplified->getOperand(1) == UnsimplifiedRHS)
415        return Simplified;
416      if (Simplified->isCommutative() &&
417          Simplified->getOperand(1) == UnsimplifiedLHS &&
418          Simplified->getOperand(0) == UnsimplifiedRHS)
419        return Simplified;
420    }
421  }
422
423  return 0;
424}
425
426/// ThreadCmpOverSelect - In the case of a comparison with a select instruction,
427/// try to simplify the comparison by seeing whether both branches of the select
428/// result in the same value.  Returns the common value if so, otherwise returns
429/// null.
430static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS,
431                                  Value *RHS, const Query &Q,
432                                  unsigned MaxRecurse) {
433  // Recursion is always used, so bail out at once if we already hit the limit.
434  if (!MaxRecurse--)
435    return 0;
436
437  // Make sure the select is on the LHS.
438  if (!isa<SelectInst>(LHS)) {
439    std::swap(LHS, RHS);
440    Pred = CmpInst::getSwappedPredicate(Pred);
441  }
442  assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!");
443  SelectInst *SI = cast<SelectInst>(LHS);
444  Value *Cond = SI->getCondition();
445  Value *TV = SI->getTrueValue();
446  Value *FV = SI->getFalseValue();
447
448  // Now that we have "cmp select(Cond, TV, FV), RHS", analyse it.
449  // Does "cmp TV, RHS" simplify?
450  Value *TCmp = SimplifyCmpInst(Pred, TV, RHS, Q, MaxRecurse);
451  if (TCmp == Cond) {
452    // It not only simplified, it simplified to the select condition.  Replace
453    // it with 'true'.
454    TCmp = getTrue(Cond->getType());
455  } else if (!TCmp) {
456    // It didn't simplify.  However if "cmp TV, RHS" is equal to the select
457    // condition then we can replace it with 'true'.  Otherwise give up.
458    if (!isSameCompare(Cond, Pred, TV, RHS))
459      return 0;
460    TCmp = getTrue(Cond->getType());
461  }
462
463  // Does "cmp FV, RHS" simplify?
464  Value *FCmp = SimplifyCmpInst(Pred, FV, RHS, Q, MaxRecurse);
465  if (FCmp == Cond) {
466    // It not only simplified, it simplified to the select condition.  Replace
467    // it with 'false'.
468    FCmp = getFalse(Cond->getType());
469  } else if (!FCmp) {
470    // It didn't simplify.  However if "cmp FV, RHS" is equal to the select
471    // condition then we can replace it with 'false'.  Otherwise give up.
472    if (!isSameCompare(Cond, Pred, FV, RHS))
473      return 0;
474    FCmp = getFalse(Cond->getType());
475  }
476
477  // If both sides simplified to the same value, then use it as the result of
478  // the original comparison.
479  if (TCmp == FCmp)
480    return TCmp;
481
482  // The remaining cases only make sense if the select condition has the same
483  // type as the result of the comparison, so bail out if this is not so.
484  if (Cond->getType()->isVectorTy() != RHS->getType()->isVectorTy())
485    return 0;
486  // If the false value simplified to false, then the result of the compare
487  // is equal to "Cond && TCmp".  This also catches the case when the false
488  // value simplified to false and the true value to true, returning "Cond".
489  if (match(FCmp, m_Zero()))
490    if (Value *V = SimplifyAndInst(Cond, TCmp, Q, MaxRecurse))
491      return V;
492  // If the true value simplified to true, then the result of the compare
493  // is equal to "Cond || FCmp".
494  if (match(TCmp, m_One()))
495    if (Value *V = SimplifyOrInst(Cond, FCmp, Q, MaxRecurse))
496      return V;
497  // Finally, if the false value simplified to true and the true value to
498  // false, then the result of the compare is equal to "!Cond".
499  if (match(FCmp, m_One()) && match(TCmp, m_Zero()))
500    if (Value *V =
501        SimplifyXorInst(Cond, Constant::getAllOnesValue(Cond->getType()),
502                        Q, MaxRecurse))
503      return V;
504
505  return 0;
506}
507
508/// ThreadBinOpOverPHI - In the case of a binary operation with an operand that
509/// is a PHI instruction, try to simplify the binop by seeing whether evaluating
510/// it on the incoming phi values yields the same result for every value.  If so
511/// returns the common value, otherwise returns null.
512static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS,
513                                 const Query &Q, unsigned MaxRecurse) {
514  // Recursion is always used, so bail out at once if we already hit the limit.
515  if (!MaxRecurse--)
516    return 0;
517
518  PHINode *PI;
519  if (isa<PHINode>(LHS)) {
520    PI = cast<PHINode>(LHS);
521    // Bail out if RHS and the phi may be mutually interdependent due to a loop.
522    if (!ValueDominatesPHI(RHS, PI, Q.DT))
523      return 0;
524  } else {
525    assert(isa<PHINode>(RHS) && "No PHI instruction operand!");
526    PI = cast<PHINode>(RHS);
527    // Bail out if LHS and the phi may be mutually interdependent due to a loop.
528    if (!ValueDominatesPHI(LHS, PI, Q.DT))
529      return 0;
530  }
531
532  // Evaluate the BinOp on the incoming phi values.
533  Value *CommonValue = 0;
534  for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
535    Value *Incoming = PI->getIncomingValue(i);
536    // If the incoming value is the phi node itself, it can safely be skipped.
537    if (Incoming == PI) continue;
538    Value *V = PI == LHS ?
539      SimplifyBinOp(Opcode, Incoming, RHS, Q, MaxRecurse) :
540      SimplifyBinOp(Opcode, LHS, Incoming, Q, MaxRecurse);
541    // If the operation failed to simplify, or simplified to a different value
542    // to previously, then give up.
543    if (!V || (CommonValue && V != CommonValue))
544      return 0;
545    CommonValue = V;
546  }
547
548  return CommonValue;
549}
550
551/// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try
552/// try to simplify the comparison by seeing whether comparing with all of the
553/// incoming phi values yields the same result every time.  If so returns the
554/// common result, otherwise returns null.
555static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
556                               const Query &Q, unsigned MaxRecurse) {
557  // Recursion is always used, so bail out at once if we already hit the limit.
558  if (!MaxRecurse--)
559    return 0;
560
561  // Make sure the phi is on the LHS.
562  if (!isa<PHINode>(LHS)) {
563    std::swap(LHS, RHS);
564    Pred = CmpInst::getSwappedPredicate(Pred);
565  }
566  assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!");
567  PHINode *PI = cast<PHINode>(LHS);
568
569  // Bail out if RHS and the phi may be mutually interdependent due to a loop.
570  if (!ValueDominatesPHI(RHS, PI, Q.DT))
571    return 0;
572
573  // Evaluate the BinOp on the incoming phi values.
574  Value *CommonValue = 0;
575  for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
576    Value *Incoming = PI->getIncomingValue(i);
577    // If the incoming value is the phi node itself, it can safely be skipped.
578    if (Incoming == PI) continue;
579    Value *V = SimplifyCmpInst(Pred, Incoming, RHS, Q, MaxRecurse);
580    // If the operation failed to simplify, or simplified to a different value
581    // to previously, then give up.
582    if (!V || (CommonValue && V != CommonValue))
583      return 0;
584    CommonValue = V;
585  }
586
587  return CommonValue;
588}
589
590/// SimplifyAddInst - Given operands for an Add, see if we can
591/// fold the result.  If not, this returns null.
592static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
593                              const Query &Q, unsigned MaxRecurse) {
594  if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
595    if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
596      Constant *Ops[] = { CLHS, CRHS };
597      return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), Ops,
598                                      Q.TD, Q.TLI);
599    }
600
601    // Canonicalize the constant to the RHS.
602    std::swap(Op0, Op1);
603  }
604
605  // X + undef -> undef
606  if (match(Op1, m_Undef()))
607    return Op1;
608
609  // X + 0 -> X
610  if (match(Op1, m_Zero()))
611    return Op0;
612
613  // X + (Y - X) -> Y
614  // (Y - X) + X -> Y
615  // Eg: X + -X -> 0
616  Value *Y = 0;
617  if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) ||
618      match(Op0, m_Sub(m_Value(Y), m_Specific(Op1))))
619    return Y;
620
621  // X + ~X -> -1   since   ~X = -X-1
622  if (match(Op0, m_Not(m_Specific(Op1))) ||
623      match(Op1, m_Not(m_Specific(Op0))))
624    return Constant::getAllOnesValue(Op0->getType());
625
626  /// i1 add -> xor.
627  if (MaxRecurse && Op0->getType()->isIntegerTy(1))
628    if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1))
629      return V;
630
631  // Try some generic simplifications for associative operations.
632  if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, Q,
633                                          MaxRecurse))
634    return V;
635
636  // Mul distributes over Add.  Try some generic simplifications based on this.
637  if (Value *V = FactorizeBinOp(Instruction::Add, Op0, Op1, Instruction::Mul,
638                                Q, MaxRecurse))
639    return V;
640
641  // Threading Add over selects and phi nodes is pointless, so don't bother.
642  // Threading over the select in "A + select(cond, B, C)" means evaluating
643  // "A+B" and "A+C" and seeing if they are equal; but they are equal if and
644  // only if B and C are equal.  If B and C are equal then (since we assume
645  // that operands have already been simplified) "select(cond, B, C)" should
646  // have been simplified to the common value of B and C already.  Analysing
647  // "A+B" and "A+C" thus gains nothing, but costs compile time.  Similarly
648  // for threading over phi nodes.
649
650  return 0;
651}
652
653Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
654                             const DataLayout *TD, const TargetLibraryInfo *TLI,
655                             const DominatorTree *DT) {
656  return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, Query (TD, TLI, DT),
657                           RecursionLimit);
658}
659
660/// \brief Accumulate the constant integer offset a GEP represents.
661///
662/// Given a getelementptr instruction/constantexpr, accumulate the constant
663/// offset from the base pointer into the provided APInt 'Offset'. Returns true
664/// if the GEP has all-constant indices. Returns false if any non-constant
665/// index is encountered leaving the 'Offset' in an undefined state. The
666/// 'Offset' APInt must be the bitwidth of the target's pointer size.
667static bool accumulateGEPOffset(const DataLayout &TD, GEPOperator *GEP,
668                                APInt &Offset) {
669  unsigned IntPtrWidth = TD.getPointerSizeInBits();
670  assert(IntPtrWidth == Offset.getBitWidth());
671
672  gep_type_iterator GTI = gep_type_begin(GEP);
673  for (User::op_iterator I = GEP->op_begin() + 1, E = GEP->op_end(); I != E;
674       ++I, ++GTI) {
675    ConstantInt *OpC = dyn_cast<ConstantInt>(*I);
676    if (!OpC) return false;
677    if (OpC->isZero()) continue;
678
679    // Handle a struct index, which adds its field offset to the pointer.
680    if (StructType *STy = dyn_cast<StructType>(*GTI)) {
681      unsigned ElementIdx = OpC->getZExtValue();
682      const StructLayout *SL = TD.getStructLayout(STy);
683      Offset += APInt(IntPtrWidth, SL->getElementOffset(ElementIdx));
684      continue;
685    }
686
687    APInt TypeSize(IntPtrWidth, TD.getTypeAllocSize(GTI.getIndexedType()));
688    Offset += OpC->getValue().sextOrTrunc(IntPtrWidth) * TypeSize;
689  }
690  return true;
691}
692
693/// \brief Compute the base pointer and cumulative constant offsets for V.
694///
695/// This strips all constant offsets off of V, leaving it the base pointer, and
696/// accumulates the total constant offset applied in the returned constant. It
697/// returns 0 if V is not a pointer, and returns the constant '0' if there are
698/// no constant offsets applied.
699static Constant *stripAndComputeConstantOffsets(const DataLayout &TD,
700                                                Value *&V) {
701  if (!V->getType()->isPointerTy())
702    return 0;
703
704  unsigned IntPtrWidth = TD.getPointerSizeInBits();
705  APInt Offset = APInt::getNullValue(IntPtrWidth);
706
707  // Even though we don't look through PHI nodes, we could be called on an
708  // instruction in an unreachable block, which may be on a cycle.
709  SmallPtrSet<Value *, 4> Visited;
710  Visited.insert(V);
711  do {
712    if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
713      if (!GEP->isInBounds() || !accumulateGEPOffset(TD, GEP, Offset))
714        break;
715      V = GEP->getPointerOperand();
716    } else if (Operator::getOpcode(V) == Instruction::BitCast) {
717      V = cast<Operator>(V)->getOperand(0);
718    } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
719      if (GA->mayBeOverridden())
720        break;
721      V = GA->getAliasee();
722    } else {
723      break;
724    }
725    assert(V->getType()->isPointerTy() && "Unexpected operand type!");
726  } while (Visited.insert(V));
727
728  Type *IntPtrTy = TD.getIntPtrType(V->getContext());
729  return ConstantInt::get(IntPtrTy, Offset);
730}
731
732/// \brief Compute the constant difference between two pointer values.
733/// If the difference is not a constant, returns zero.
734static Constant *computePointerDifference(const DataLayout &TD,
735                                          Value *LHS, Value *RHS) {
736  Constant *LHSOffset = stripAndComputeConstantOffsets(TD, LHS);
737  if (!LHSOffset)
738    return 0;
739  Constant *RHSOffset = stripAndComputeConstantOffsets(TD, RHS);
740  if (!RHSOffset)
741    return 0;
742
743  // If LHS and RHS are not related via constant offsets to the same base
744  // value, there is nothing we can do here.
745  if (LHS != RHS)
746    return 0;
747
748  // Otherwise, the difference of LHS - RHS can be computed as:
749  //    LHS - RHS
750  //  = (LHSOffset + Base) - (RHSOffset + Base)
751  //  = LHSOffset - RHSOffset
752  return ConstantExpr::getSub(LHSOffset, RHSOffset);
753}
754
755/// SimplifySubInst - Given operands for a Sub, see if we can
756/// fold the result.  If not, this returns null.
757static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
758                              const Query &Q, unsigned MaxRecurse) {
759  if (Constant *CLHS = dyn_cast<Constant>(Op0))
760    if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
761      Constant *Ops[] = { CLHS, CRHS };
762      return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(),
763                                      Ops, Q.TD, Q.TLI);
764    }
765
766  // X - undef -> undef
767  // undef - X -> undef
768  if (match(Op0, m_Undef()) || match(Op1, m_Undef()))
769    return UndefValue::get(Op0->getType());
770
771  // X - 0 -> X
772  if (match(Op1, m_Zero()))
773    return Op0;
774
775  // X - X -> 0
776  if (Op0 == Op1)
777    return Constant::getNullValue(Op0->getType());
778
779  // (X*2) - X -> X
780  // (X<<1) - X -> X
781  Value *X = 0;
782  if (match(Op0, m_Mul(m_Specific(Op1), m_ConstantInt<2>())) ||
783      match(Op0, m_Shl(m_Specific(Op1), m_One())))
784    return Op1;
785
786  // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies.
787  // For example, (X + Y) - Y -> X; (Y + X) - Y -> X
788  Value *Y = 0, *Z = Op1;
789  if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z
790    // See if "V === Y - Z" simplifies.
791    if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, Q, MaxRecurse-1))
792      // It does!  Now see if "X + V" simplifies.
793      if (Value *W = SimplifyBinOp(Instruction::Add, X, V, Q, MaxRecurse-1)) {
794        // It does, we successfully reassociated!
795        ++NumReassoc;
796        return W;
797      }
798    // See if "V === X - Z" simplifies.
799    if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1))
800      // It does!  Now see if "Y + V" simplifies.
801      if (Value *W = SimplifyBinOp(Instruction::Add, Y, V, Q, MaxRecurse-1)) {
802        // It does, we successfully reassociated!
803        ++NumReassoc;
804        return W;
805      }
806  }
807
808  // X - (Y + Z) -> (X - Y) - Z or (X - Z) - Y if everything simplifies.
809  // For example, X - (X + 1) -> -1
810  X = Op0;
811  if (MaxRecurse && match(Op1, m_Add(m_Value(Y), m_Value(Z)))) { // X - (Y + Z)
812    // See if "V === X - Y" simplifies.
813    if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1))
814      // It does!  Now see if "V - Z" simplifies.
815      if (Value *W = SimplifyBinOp(Instruction::Sub, V, Z, Q, MaxRecurse-1)) {
816        // It does, we successfully reassociated!
817        ++NumReassoc;
818        return W;
819      }
820    // See if "V === X - Z" simplifies.
821    if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1))
822      // It does!  Now see if "V - Y" simplifies.
823      if (Value *W = SimplifyBinOp(Instruction::Sub, V, Y, Q, MaxRecurse-1)) {
824        // It does, we successfully reassociated!
825        ++NumReassoc;
826        return W;
827      }
828  }
829
830  // Z - (X - Y) -> (Z - X) + Y if everything simplifies.
831  // For example, X - (X - Y) -> Y.
832  Z = Op0;
833  if (MaxRecurse && match(Op1, m_Sub(m_Value(X), m_Value(Y)))) // Z - (X - Y)
834    // See if "V === Z - X" simplifies.
835    if (Value *V = SimplifyBinOp(Instruction::Sub, Z, X, Q, MaxRecurse-1))
836      // It does!  Now see if "V + Y" simplifies.
837      if (Value *W = SimplifyBinOp(Instruction::Add, V, Y, Q, MaxRecurse-1)) {
838        // It does, we successfully reassociated!
839        ++NumReassoc;
840        return W;
841      }
842
843  // trunc(X) - trunc(Y) -> trunc(X - Y) if everything simplifies.
844  if (MaxRecurse && match(Op0, m_Trunc(m_Value(X))) &&
845      match(Op1, m_Trunc(m_Value(Y))))
846    if (X->getType() == Y->getType())
847      // See if "V === X - Y" simplifies.
848      if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1))
849        // It does!  Now see if "trunc V" simplifies.
850        if (Value *W = SimplifyTruncInst(V, Op0->getType(), Q, MaxRecurse-1))
851          // It does, return the simplified "trunc V".
852          return W;
853
854  // Variations on GEP(base, I, ...) - GEP(base, i, ...) -> GEP(null, I-i, ...).
855  if (Q.TD && match(Op0, m_PtrToInt(m_Value(X))) &&
856      match(Op1, m_PtrToInt(m_Value(Y))))
857    if (Constant *Result = computePointerDifference(*Q.TD, X, Y))
858      return ConstantExpr::getIntegerCast(Result, Op0->getType(), true);
859
860  // Mul distributes over Sub.  Try some generic simplifications based on this.
861  if (Value *V = FactorizeBinOp(Instruction::Sub, Op0, Op1, Instruction::Mul,
862                                Q, MaxRecurse))
863    return V;
864
865  // i1 sub -> xor.
866  if (MaxRecurse && Op0->getType()->isIntegerTy(1))
867    if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1))
868      return V;
869
870  // Threading Sub over selects and phi nodes is pointless, so don't bother.
871  // Threading over the select in "A - select(cond, B, C)" means evaluating
872  // "A-B" and "A-C" and seeing if they are equal; but they are equal if and
873  // only if B and C are equal.  If B and C are equal then (since we assume
874  // that operands have already been simplified) "select(cond, B, C)" should
875  // have been simplified to the common value of B and C already.  Analysing
876  // "A-B" and "A-C" thus gains nothing, but costs compile time.  Similarly
877  // for threading over phi nodes.
878
879  return 0;
880}
881
882Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
883                             const DataLayout *TD, const TargetLibraryInfo *TLI,
884                             const DominatorTree *DT) {
885  return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, Query (TD, TLI, DT),
886                           RecursionLimit);
887}
888
889/// Given the operands for an FMul, see if we can fold the result
890static Value *SimplifyFMulInst(Value *Op0, Value *Op1,
891                               FastMathFlags FMF,
892                               const Query &Q,
893                               unsigned MaxRecurse) {
894 if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
895    if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
896      Constant *Ops[] = { CLHS, CRHS };
897      return ConstantFoldInstOperands(Instruction::FMul, CLHS->getType(),
898                                      Ops, Q.TD, Q.TLI);
899    }
900 }
901
902 // Check for some fast-math optimizations
903 if (FMF.NoNaNs) {
904   if (FMF.NoSignedZeros) {
905     // fmul N S 0, x ==> 0
906     if (match(Op0, m_Zero()))
907       return Op0;
908     if (match(Op1, m_Zero()))
909       return Op1;
910   }
911 }
912
913 return 0;
914}
915
916/// SimplifyMulInst - Given operands for a Mul, see if we can
917/// fold the result.  If not, this returns null.
918static Value *SimplifyMulInst(Value *Op0, Value *Op1, const Query &Q,
919                              unsigned MaxRecurse) {
920  if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
921    if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
922      Constant *Ops[] = { CLHS, CRHS };
923      return ConstantFoldInstOperands(Instruction::Mul, CLHS->getType(),
924                                      Ops, Q.TD, Q.TLI);
925    }
926
927    // Canonicalize the constant to the RHS.
928    std::swap(Op0, Op1);
929  }
930
931  // X * undef -> 0
932  if (match(Op1, m_Undef()))
933    return Constant::getNullValue(Op0->getType());
934
935  // X * 0 -> 0
936  if (match(Op1, m_Zero()))
937    return Op1;
938
939  // X * 1 -> X
940  if (match(Op1, m_One()))
941    return Op0;
942
943  // (X / Y) * Y -> X if the division is exact.
944  Value *X = 0;
945  if (match(Op0, m_Exact(m_IDiv(m_Value(X), m_Specific(Op1)))) || // (X / Y) * Y
946      match(Op1, m_Exact(m_IDiv(m_Value(X), m_Specific(Op0)))))   // Y * (X / Y)
947    return X;
948
949  // i1 mul -> and.
950  if (MaxRecurse && Op0->getType()->isIntegerTy(1))
951    if (Value *V = SimplifyAndInst(Op0, Op1, Q, MaxRecurse-1))
952      return V;
953
954  // Try some generic simplifications for associative operations.
955  if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, Q,
956                                          MaxRecurse))
957    return V;
958
959  // Mul distributes over Add.  Try some generic simplifications based on this.
960  if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add,
961                             Q, MaxRecurse))
962    return V;
963
964  // If the operation is with the result of a select instruction, check whether
965  // operating on either branch of the select always yields the same value.
966  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
967    if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, Q,
968                                         MaxRecurse))
969      return V;
970
971  // If the operation is with the result of a phi instruction, check whether
972  // operating on all incoming values of the phi always yields the same value.
973  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
974    if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, Q,
975                                      MaxRecurse))
976      return V;
977
978  return 0;
979}
980
981Value *llvm::SimplifyFMulInst(Value *Op0, Value *Op1,
982                              FastMathFlags FMF,
983                              const DataLayout *TD,
984                              const TargetLibraryInfo *TLI,
985                              const DominatorTree *DT) {
986  return ::SimplifyFMulInst(Op0, Op1, FMF, Query (TD, TLI, DT), RecursionLimit);
987}
988
989Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const DataLayout *TD,
990                             const TargetLibraryInfo *TLI,
991                             const DominatorTree *DT) {
992  return ::SimplifyMulInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit);
993}
994
995/// SimplifyDiv - Given operands for an SDiv or UDiv, see if we can
996/// fold the result.  If not, this returns null.
997static Value *SimplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
998                          const Query &Q, unsigned MaxRecurse) {
999  if (Constant *C0 = dyn_cast<Constant>(Op0)) {
1000    if (Constant *C1 = dyn_cast<Constant>(Op1)) {
1001      Constant *Ops[] = { C0, C1 };
1002      return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.TD, Q.TLI);
1003    }
1004  }
1005
1006  bool isSigned = Opcode == Instruction::SDiv;
1007
1008  // X / undef -> undef
1009  if (match(Op1, m_Undef()))
1010    return Op1;
1011
1012  // undef / X -> 0
1013  if (match(Op0, m_Undef()))
1014    return Constant::getNullValue(Op0->getType());
1015
1016  // 0 / X -> 0, we don't need to preserve faults!
1017  if (match(Op0, m_Zero()))
1018    return Op0;
1019
1020  // X / 1 -> X
1021  if (match(Op1, m_One()))
1022    return Op0;
1023
1024  if (Op0->getType()->isIntegerTy(1))
1025    // It can't be division by zero, hence it must be division by one.
1026    return Op0;
1027
1028  // X / X -> 1
1029  if (Op0 == Op1)
1030    return ConstantInt::get(Op0->getType(), 1);
1031
1032  // (X * Y) / Y -> X if the multiplication does not overflow.
1033  Value *X = 0, *Y = 0;
1034  if (match(Op0, m_Mul(m_Value(X), m_Value(Y))) && (X == Op1 || Y == Op1)) {
1035    if (Y != Op1) std::swap(X, Y); // Ensure expression is (X * Y) / Y, Y = Op1
1036    OverflowingBinaryOperator *Mul = cast<OverflowingBinaryOperator>(Op0);
1037    // If the Mul knows it does not overflow, then we are good to go.
1038    if ((isSigned && Mul->hasNoSignedWrap()) ||
1039        (!isSigned && Mul->hasNoUnsignedWrap()))
1040      return X;
1041    // If X has the form X = A / Y then X * Y cannot overflow.
1042    if (BinaryOperator *Div = dyn_cast<BinaryOperator>(X))
1043      if (Div->getOpcode() == Opcode && Div->getOperand(1) == Y)
1044        return X;
1045  }
1046
1047  // (X rem Y) / Y -> 0
1048  if ((isSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) ||
1049      (!isSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
1050    return Constant::getNullValue(Op0->getType());
1051
1052  // If the operation is with the result of a select instruction, check whether
1053  // operating on either branch of the select always yields the same value.
1054  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1055    if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
1056      return V;
1057
1058  // If the operation is with the result of a phi instruction, check whether
1059  // operating on all incoming values of the phi always yields the same value.
1060  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1061    if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
1062      return V;
1063
1064  return 0;
1065}
1066
1067/// SimplifySDivInst - Given operands for an SDiv, see if we can
1068/// fold the result.  If not, this returns null.
1069static Value *SimplifySDivInst(Value *Op0, Value *Op1, const Query &Q,
1070                               unsigned MaxRecurse) {
1071  if (Value *V = SimplifyDiv(Instruction::SDiv, Op0, Op1, Q, MaxRecurse))
1072    return V;
1073
1074  return 0;
1075}
1076
1077Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const DataLayout *TD,
1078                              const TargetLibraryInfo *TLI,
1079                              const DominatorTree *DT) {
1080  return ::SimplifySDivInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit);
1081}
1082
1083/// SimplifyUDivInst - Given operands for a UDiv, see if we can
1084/// fold the result.  If not, this returns null.
1085static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const Query &Q,
1086                               unsigned MaxRecurse) {
1087  if (Value *V = SimplifyDiv(Instruction::UDiv, Op0, Op1, Q, MaxRecurse))
1088    return V;
1089
1090  return 0;
1091}
1092
1093Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const DataLayout *TD,
1094                              const TargetLibraryInfo *TLI,
1095                              const DominatorTree *DT) {
1096  return ::SimplifyUDivInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit);
1097}
1098
1099static Value *SimplifyFDivInst(Value *Op0, Value *Op1, const Query &Q,
1100                               unsigned) {
1101  // undef / X -> undef    (the undef could be a snan).
1102  if (match(Op0, m_Undef()))
1103    return Op0;
1104
1105  // X / undef -> undef
1106  if (match(Op1, m_Undef()))
1107    return Op1;
1108
1109  return 0;
1110}
1111
1112Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, const DataLayout *TD,
1113                              const TargetLibraryInfo *TLI,
1114                              const DominatorTree *DT) {
1115  return ::SimplifyFDivInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit);
1116}
1117
1118/// SimplifyRem - Given operands for an SRem or URem, see if we can
1119/// fold the result.  If not, this returns null.
1120static Value *SimplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
1121                          const Query &Q, unsigned MaxRecurse) {
1122  if (Constant *C0 = dyn_cast<Constant>(Op0)) {
1123    if (Constant *C1 = dyn_cast<Constant>(Op1)) {
1124      Constant *Ops[] = { C0, C1 };
1125      return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.TD, Q.TLI);
1126    }
1127  }
1128
1129  // X % undef -> undef
1130  if (match(Op1, m_Undef()))
1131    return Op1;
1132
1133  // undef % X -> 0
1134  if (match(Op0, m_Undef()))
1135    return Constant::getNullValue(Op0->getType());
1136
1137  // 0 % X -> 0, we don't need to preserve faults!
1138  if (match(Op0, m_Zero()))
1139    return Op0;
1140
1141  // X % 0 -> undef, we don't need to preserve faults!
1142  if (match(Op1, m_Zero()))
1143    return UndefValue::get(Op0->getType());
1144
1145  // X % 1 -> 0
1146  if (match(Op1, m_One()))
1147    return Constant::getNullValue(Op0->getType());
1148
1149  if (Op0->getType()->isIntegerTy(1))
1150    // It can't be remainder by zero, hence it must be remainder by one.
1151    return Constant::getNullValue(Op0->getType());
1152
1153  // X % X -> 0
1154  if (Op0 == Op1)
1155    return Constant::getNullValue(Op0->getType());
1156
1157  // If the operation is with the result of a select instruction, check whether
1158  // operating on either branch of the select always yields the same value.
1159  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1160    if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
1161      return V;
1162
1163  // If the operation is with the result of a phi instruction, check whether
1164  // operating on all incoming values of the phi always yields the same value.
1165  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1166    if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
1167      return V;
1168
1169  return 0;
1170}
1171
1172/// SimplifySRemInst - Given operands for an SRem, see if we can
1173/// fold the result.  If not, this returns null.
1174static Value *SimplifySRemInst(Value *Op0, Value *Op1, const Query &Q,
1175                               unsigned MaxRecurse) {
1176  if (Value *V = SimplifyRem(Instruction::SRem, Op0, Op1, Q, MaxRecurse))
1177    return V;
1178
1179  return 0;
1180}
1181
1182Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const DataLayout *TD,
1183                              const TargetLibraryInfo *TLI,
1184                              const DominatorTree *DT) {
1185  return ::SimplifySRemInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit);
1186}
1187
1188/// SimplifyURemInst - Given operands for a URem, see if we can
1189/// fold the result.  If not, this returns null.
1190static Value *SimplifyURemInst(Value *Op0, Value *Op1, const Query &Q,
1191                               unsigned MaxRecurse) {
1192  if (Value *V = SimplifyRem(Instruction::URem, Op0, Op1, Q, MaxRecurse))
1193    return V;
1194
1195  return 0;
1196}
1197
1198Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const DataLayout *TD,
1199                              const TargetLibraryInfo *TLI,
1200                              const DominatorTree *DT) {
1201  return ::SimplifyURemInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit);
1202}
1203
1204static Value *SimplifyFRemInst(Value *Op0, Value *Op1, const Query &,
1205                               unsigned) {
1206  // undef % X -> undef    (the undef could be a snan).
1207  if (match(Op0, m_Undef()))
1208    return Op0;
1209
1210  // X % undef -> undef
1211  if (match(Op1, m_Undef()))
1212    return Op1;
1213
1214  return 0;
1215}
1216
1217Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, const DataLayout *TD,
1218                              const TargetLibraryInfo *TLI,
1219                              const DominatorTree *DT) {
1220  return ::SimplifyFRemInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit);
1221}
1222
1223/// SimplifyShift - Given operands for an Shl, LShr or AShr, see if we can
1224/// fold the result.  If not, this returns null.
1225static Value *SimplifyShift(unsigned Opcode, Value *Op0, Value *Op1,
1226                            const Query &Q, unsigned MaxRecurse) {
1227  if (Constant *C0 = dyn_cast<Constant>(Op0)) {
1228    if (Constant *C1 = dyn_cast<Constant>(Op1)) {
1229      Constant *Ops[] = { C0, C1 };
1230      return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.TD, Q.TLI);
1231    }
1232  }
1233
1234  // 0 shift by X -> 0
1235  if (match(Op0, m_Zero()))
1236    return Op0;
1237
1238  // X shift by 0 -> X
1239  if (match(Op1, m_Zero()))
1240    return Op0;
1241
1242  // X shift by undef -> undef because it may shift by the bitwidth.
1243  if (match(Op1, m_Undef()))
1244    return Op1;
1245
1246  // Shifting by the bitwidth or more is undefined.
1247  if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1))
1248    if (CI->getValue().getLimitedValue() >=
1249        Op0->getType()->getScalarSizeInBits())
1250      return UndefValue::get(Op0->getType());
1251
1252  // If the operation is with the result of a select instruction, check whether
1253  // operating on either branch of the select always yields the same value.
1254  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1255    if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
1256      return V;
1257
1258  // If the operation is with the result of a phi instruction, check whether
1259  // operating on all incoming values of the phi always yields the same value.
1260  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1261    if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
1262      return V;
1263
1264  return 0;
1265}
1266
1267/// SimplifyShlInst - Given operands for an Shl, see if we can
1268/// fold the result.  If not, this returns null.
1269static Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
1270                              const Query &Q, unsigned MaxRecurse) {
1271  if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, Q, MaxRecurse))
1272    return V;
1273
1274  // undef << X -> 0
1275  if (match(Op0, m_Undef()))
1276    return Constant::getNullValue(Op0->getType());
1277
1278  // (X >> A) << A -> X
1279  Value *X;
1280  if (match(Op0, m_Exact(m_Shr(m_Value(X), m_Specific(Op1)))))
1281    return X;
1282  return 0;
1283}
1284
1285Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
1286                             const DataLayout *TD, const TargetLibraryInfo *TLI,
1287                             const DominatorTree *DT) {
1288  return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, Query (TD, TLI, DT),
1289                           RecursionLimit);
1290}
1291
1292/// SimplifyLShrInst - Given operands for an LShr, see if we can
1293/// fold the result.  If not, this returns null.
1294static Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
1295                               const Query &Q, unsigned MaxRecurse) {
1296  if (Value *V = SimplifyShift(Instruction::LShr, Op0, Op1, Q, MaxRecurse))
1297    return V;
1298
1299  // undef >>l X -> 0
1300  if (match(Op0, m_Undef()))
1301    return Constant::getNullValue(Op0->getType());
1302
1303  // (X << A) >> A -> X
1304  Value *X;
1305  if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1))) &&
1306      cast<OverflowingBinaryOperator>(Op0)->hasNoUnsignedWrap())
1307    return X;
1308
1309  return 0;
1310}
1311
1312Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
1313                              const DataLayout *TD,
1314                              const TargetLibraryInfo *TLI,
1315                              const DominatorTree *DT) {
1316  return ::SimplifyLShrInst(Op0, Op1, isExact, Query (TD, TLI, DT),
1317                            RecursionLimit);
1318}
1319
1320/// SimplifyAShrInst - Given operands for an AShr, see if we can
1321/// fold the result.  If not, this returns null.
1322static Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
1323                               const Query &Q, unsigned MaxRecurse) {
1324  if (Value *V = SimplifyShift(Instruction::AShr, Op0, Op1, Q, MaxRecurse))
1325    return V;
1326
1327  // all ones >>a X -> all ones
1328  if (match(Op0, m_AllOnes()))
1329    return Op0;
1330
1331  // undef >>a X -> all ones
1332  if (match(Op0, m_Undef()))
1333    return Constant::getAllOnesValue(Op0->getType());
1334
1335  // (X << A) >> A -> X
1336  Value *X;
1337  if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1))) &&
1338      cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap())
1339    return X;
1340
1341  return 0;
1342}
1343
1344Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
1345                              const DataLayout *TD,
1346                              const TargetLibraryInfo *TLI,
1347                              const DominatorTree *DT) {
1348  return ::SimplifyAShrInst(Op0, Op1, isExact, Query (TD, TLI, DT),
1349                            RecursionLimit);
1350}
1351
1352/// SimplifyAndInst - Given operands for an And, see if we can
1353/// fold the result.  If not, this returns null.
1354static Value *SimplifyAndInst(Value *Op0, Value *Op1, const Query &Q,
1355                              unsigned MaxRecurse) {
1356  if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
1357    if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
1358      Constant *Ops[] = { CLHS, CRHS };
1359      return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
1360                                      Ops, Q.TD, Q.TLI);
1361    }
1362
1363    // Canonicalize the constant to the RHS.
1364    std::swap(Op0, Op1);
1365  }
1366
1367  // X & undef -> 0
1368  if (match(Op1, m_Undef()))
1369    return Constant::getNullValue(Op0->getType());
1370
1371  // X & X = X
1372  if (Op0 == Op1)
1373    return Op0;
1374
1375  // X & 0 = 0
1376  if (match(Op1, m_Zero()))
1377    return Op1;
1378
1379  // X & -1 = X
1380  if (match(Op1, m_AllOnes()))
1381    return Op0;
1382
1383  // A & ~A  =  ~A & A  =  0
1384  if (match(Op0, m_Not(m_Specific(Op1))) ||
1385      match(Op1, m_Not(m_Specific(Op0))))
1386    return Constant::getNullValue(Op0->getType());
1387
1388  // (A | ?) & A = A
1389  Value *A = 0, *B = 0;
1390  if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
1391      (A == Op1 || B == Op1))
1392    return Op1;
1393
1394  // A & (A | ?) = A
1395  if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
1396      (A == Op0 || B == Op0))
1397    return Op0;
1398
1399  // A & (-A) = A if A is a power of two or zero.
1400  if (match(Op0, m_Neg(m_Specific(Op1))) ||
1401      match(Op1, m_Neg(m_Specific(Op0)))) {
1402    if (isPowerOfTwo(Op0, Q.TD, /*OrZero*/true))
1403      return Op0;
1404    if (isPowerOfTwo(Op1, Q.TD, /*OrZero*/true))
1405      return Op1;
1406  }
1407
1408  // Try some generic simplifications for associative operations.
1409  if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, Q,
1410                                          MaxRecurse))
1411    return V;
1412
1413  // And distributes over Or.  Try some generic simplifications based on this.
1414  if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or,
1415                             Q, MaxRecurse))
1416    return V;
1417
1418  // And distributes over Xor.  Try some generic simplifications based on this.
1419  if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor,
1420                             Q, MaxRecurse))
1421    return V;
1422
1423  // Or distributes over And.  Try some generic simplifications based on this.
1424  if (Value *V = FactorizeBinOp(Instruction::And, Op0, Op1, Instruction::Or,
1425                                Q, MaxRecurse))
1426    return V;
1427
1428  // If the operation is with the result of a select instruction, check whether
1429  // operating on either branch of the select always yields the same value.
1430  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1431    if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, Q,
1432                                         MaxRecurse))
1433      return V;
1434
1435  // If the operation is with the result of a phi instruction, check whether
1436  // operating on all incoming values of the phi always yields the same value.
1437  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1438    if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, Q,
1439                                      MaxRecurse))
1440      return V;
1441
1442  return 0;
1443}
1444
1445Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const DataLayout *TD,
1446                             const TargetLibraryInfo *TLI,
1447                             const DominatorTree *DT) {
1448  return ::SimplifyAndInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit);
1449}
1450
1451/// SimplifyOrInst - Given operands for an Or, see if we can
1452/// fold the result.  If not, this returns null.
1453static Value *SimplifyOrInst(Value *Op0, Value *Op1, const Query &Q,
1454                             unsigned MaxRecurse) {
1455  if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
1456    if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
1457      Constant *Ops[] = { CLHS, CRHS };
1458      return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
1459                                      Ops, Q.TD, Q.TLI);
1460    }
1461
1462    // Canonicalize the constant to the RHS.
1463    std::swap(Op0, Op1);
1464  }
1465
1466  // X | undef -> -1
1467  if (match(Op1, m_Undef()))
1468    return Constant::getAllOnesValue(Op0->getType());
1469
1470  // X | X = X
1471  if (Op0 == Op1)
1472    return Op0;
1473
1474  // X | 0 = X
1475  if (match(Op1, m_Zero()))
1476    return Op0;
1477
1478  // X | -1 = -1
1479  if (match(Op1, m_AllOnes()))
1480    return Op1;
1481
1482  // A | ~A  =  ~A | A  =  -1
1483  if (match(Op0, m_Not(m_Specific(Op1))) ||
1484      match(Op1, m_Not(m_Specific(Op0))))
1485    return Constant::getAllOnesValue(Op0->getType());
1486
1487  // (A & ?) | A = A
1488  Value *A = 0, *B = 0;
1489  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
1490      (A == Op1 || B == Op1))
1491    return Op1;
1492
1493  // A | (A & ?) = A
1494  if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
1495      (A == Op0 || B == Op0))
1496    return Op0;
1497
1498  // ~(A & ?) | A = -1
1499  if (match(Op0, m_Not(m_And(m_Value(A), m_Value(B)))) &&
1500      (A == Op1 || B == Op1))
1501    return Constant::getAllOnesValue(Op1->getType());
1502
1503  // A | ~(A & ?) = -1
1504  if (match(Op1, m_Not(m_And(m_Value(A), m_Value(B)))) &&
1505      (A == Op0 || B == Op0))
1506    return Constant::getAllOnesValue(Op0->getType());
1507
1508  // Try some generic simplifications for associative operations.
1509  if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, Q,
1510                                          MaxRecurse))
1511    return V;
1512
1513  // Or distributes over And.  Try some generic simplifications based on this.
1514  if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, Q,
1515                             MaxRecurse))
1516    return V;
1517
1518  // And distributes over Or.  Try some generic simplifications based on this.
1519  if (Value *V = FactorizeBinOp(Instruction::Or, Op0, Op1, Instruction::And,
1520                                Q, MaxRecurse))
1521    return V;
1522
1523  // If the operation is with the result of a select instruction, check whether
1524  // operating on either branch of the select always yields the same value.
1525  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1526    if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, Q,
1527                                         MaxRecurse))
1528      return V;
1529
1530  // If the operation is with the result of a phi instruction, check whether
1531  // operating on all incoming values of the phi always yields the same value.
1532  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1533    if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, Q, MaxRecurse))
1534      return V;
1535
1536  return 0;
1537}
1538
1539Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const DataLayout *TD,
1540                            const TargetLibraryInfo *TLI,
1541                            const DominatorTree *DT) {
1542  return ::SimplifyOrInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit);
1543}
1544
1545/// SimplifyXorInst - Given operands for a Xor, see if we can
1546/// fold the result.  If not, this returns null.
1547static Value *SimplifyXorInst(Value *Op0, Value *Op1, const Query &Q,
1548                              unsigned MaxRecurse) {
1549  if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
1550    if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
1551      Constant *Ops[] = { CLHS, CRHS };
1552      return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(),
1553                                      Ops, Q.TD, Q.TLI);
1554    }
1555
1556    // Canonicalize the constant to the RHS.
1557    std::swap(Op0, Op1);
1558  }
1559
1560  // A ^ undef -> undef
1561  if (match(Op1, m_Undef()))
1562    return Op1;
1563
1564  // A ^ 0 = A
1565  if (match(Op1, m_Zero()))
1566    return Op0;
1567
1568  // A ^ A = 0
1569  if (Op0 == Op1)
1570    return Constant::getNullValue(Op0->getType());
1571
1572  // A ^ ~A  =  ~A ^ A  =  -1
1573  if (match(Op0, m_Not(m_Specific(Op1))) ||
1574      match(Op1, m_Not(m_Specific(Op0))))
1575    return Constant::getAllOnesValue(Op0->getType());
1576
1577  // Try some generic simplifications for associative operations.
1578  if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, Q,
1579                                          MaxRecurse))
1580    return V;
1581
1582  // And distributes over Xor.  Try some generic simplifications based on this.
1583  if (Value *V = FactorizeBinOp(Instruction::Xor, Op0, Op1, Instruction::And,
1584                                Q, MaxRecurse))
1585    return V;
1586
1587  // Threading Xor over selects and phi nodes is pointless, so don't bother.
1588  // Threading over the select in "A ^ select(cond, B, C)" means evaluating
1589  // "A^B" and "A^C" and seeing if they are equal; but they are equal if and
1590  // only if B and C are equal.  If B and C are equal then (since we assume
1591  // that operands have already been simplified) "select(cond, B, C)" should
1592  // have been simplified to the common value of B and C already.  Analysing
1593  // "A^B" and "A^C" thus gains nothing, but costs compile time.  Similarly
1594  // for threading over phi nodes.
1595
1596  return 0;
1597}
1598
1599Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const DataLayout *TD,
1600                             const TargetLibraryInfo *TLI,
1601                             const DominatorTree *DT) {
1602  return ::SimplifyXorInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit);
1603}
1604
1605static Type *GetCompareTy(Value *Op) {
1606  return CmpInst::makeCmpResultType(Op->getType());
1607}
1608
1609/// ExtractEquivalentCondition - Rummage around inside V looking for something
1610/// equivalent to the comparison "LHS Pred RHS".  Return such a value if found,
1611/// otherwise return null.  Helper function for analyzing max/min idioms.
1612static Value *ExtractEquivalentCondition(Value *V, CmpInst::Predicate Pred,
1613                                         Value *LHS, Value *RHS) {
1614  SelectInst *SI = dyn_cast<SelectInst>(V);
1615  if (!SI)
1616    return 0;
1617  CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
1618  if (!Cmp)
1619    return 0;
1620  Value *CmpLHS = Cmp->getOperand(0), *CmpRHS = Cmp->getOperand(1);
1621  if (Pred == Cmp->getPredicate() && LHS == CmpLHS && RHS == CmpRHS)
1622    return Cmp;
1623  if (Pred == CmpInst::getSwappedPredicate(Cmp->getPredicate()) &&
1624      LHS == CmpRHS && RHS == CmpLHS)
1625    return Cmp;
1626  return 0;
1627}
1628
1629static Constant *computePointerICmp(const DataLayout &TD,
1630                                    CmpInst::Predicate Pred,
1631                                    Value *LHS, Value *RHS) {
1632  // We can only fold certain predicates on pointer comparisons.
1633  switch (Pred) {
1634  default:
1635    return 0;
1636
1637    // Equality comaprisons are easy to fold.
1638  case CmpInst::ICMP_EQ:
1639  case CmpInst::ICMP_NE:
1640    break;
1641
1642    // We can only handle unsigned relational comparisons because 'inbounds' on
1643    // a GEP only protects against unsigned wrapping.
1644  case CmpInst::ICMP_UGT:
1645  case CmpInst::ICMP_UGE:
1646  case CmpInst::ICMP_ULT:
1647  case CmpInst::ICMP_ULE:
1648    // However, we have to switch them to their signed variants to handle
1649    // negative indices from the base pointer.
1650    Pred = ICmpInst::getSignedPredicate(Pred);
1651    break;
1652  }
1653
1654  Constant *LHSOffset = stripAndComputeConstantOffsets(TD, LHS);
1655  if (!LHSOffset)
1656    return 0;
1657  Constant *RHSOffset = stripAndComputeConstantOffsets(TD, RHS);
1658  if (!RHSOffset)
1659    return 0;
1660
1661  // If LHS and RHS are not related via constant offsets to the same base
1662  // value, there is nothing we can do here.
1663  if (LHS != RHS)
1664    return 0;
1665
1666  return ConstantExpr::getICmp(Pred, LHSOffset, RHSOffset);
1667}
1668
1669/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
1670/// fold the result.  If not, this returns null.
1671static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1672                               const Query &Q, unsigned MaxRecurse) {
1673  CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
1674  assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
1675
1676  if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
1677    if (Constant *CRHS = dyn_cast<Constant>(RHS))
1678      return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.TD, Q.TLI);
1679
1680    // If we have a constant, make sure it is on the RHS.
1681    std::swap(LHS, RHS);
1682    Pred = CmpInst::getSwappedPredicate(Pred);
1683  }
1684
1685  Type *ITy = GetCompareTy(LHS); // The return type.
1686  Type *OpTy = LHS->getType();   // The operand type.
1687
1688  // icmp X, X -> true/false
1689  // X icmp undef -> true/false.  For example, icmp ugt %X, undef -> false
1690  // because X could be 0.
1691  if (LHS == RHS || isa<UndefValue>(RHS))
1692    return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
1693
1694  // Special case logic when the operands have i1 type.
1695  if (OpTy->getScalarType()->isIntegerTy(1)) {
1696    switch (Pred) {
1697    default: break;
1698    case ICmpInst::ICMP_EQ:
1699      // X == 1 -> X
1700      if (match(RHS, m_One()))
1701        return LHS;
1702      break;
1703    case ICmpInst::ICMP_NE:
1704      // X != 0 -> X
1705      if (match(RHS, m_Zero()))
1706        return LHS;
1707      break;
1708    case ICmpInst::ICMP_UGT:
1709      // X >u 0 -> X
1710      if (match(RHS, m_Zero()))
1711        return LHS;
1712      break;
1713    case ICmpInst::ICMP_UGE:
1714      // X >=u 1 -> X
1715      if (match(RHS, m_One()))
1716        return LHS;
1717      break;
1718    case ICmpInst::ICMP_SLT:
1719      // X <s 0 -> X
1720      if (match(RHS, m_Zero()))
1721        return LHS;
1722      break;
1723    case ICmpInst::ICMP_SLE:
1724      // X <=s -1 -> X
1725      if (match(RHS, m_One()))
1726        return LHS;
1727      break;
1728    }
1729  }
1730
1731  // icmp <object*>, <object*/null> - Different identified objects have
1732  // different addresses (unless null), and what's more the address of an
1733  // identified local is never equal to another argument (again, barring null).
1734  // Note that generalizing to the case where LHS is a global variable address
1735  // or null is pointless, since if both LHS and RHS are constants then we
1736  // already constant folded the compare, and if only one of them is then we
1737  // moved it to RHS already.
1738  Value *LHSPtr = LHS->stripPointerCasts();
1739  Value *RHSPtr = RHS->stripPointerCasts();
1740  if (LHSPtr == RHSPtr)
1741    return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
1742
1743  // Be more aggressive about stripping pointer adjustments when checking a
1744  // comparison of an alloca address to another object.  We can rip off all
1745  // inbounds GEP operations, even if they are variable.
1746  LHSPtr = LHSPtr->stripInBoundsOffsets();
1747  if (llvm::isIdentifiedObject(LHSPtr)) {
1748    RHSPtr = RHSPtr->stripInBoundsOffsets();
1749    if (llvm::isKnownNonNull(LHSPtr) || llvm::isKnownNonNull(RHSPtr)) {
1750      // If both sides are different identified objects, they aren't equal
1751      // unless they're null.
1752      if (LHSPtr != RHSPtr && llvm::isIdentifiedObject(RHSPtr) &&
1753          Pred == CmpInst::ICMP_EQ)
1754        return ConstantInt::get(ITy, false);
1755
1756      // A local identified object (alloca or noalias call) can't equal any
1757      // incoming argument, unless they're both null or they belong to
1758      // different functions. The latter happens during inlining.
1759      if (Instruction *LHSInst = dyn_cast<Instruction>(LHSPtr))
1760        if (Argument *RHSArg = dyn_cast<Argument>(RHSPtr))
1761          if (LHSInst->getParent()->getParent() == RHSArg->getParent() &&
1762              Pred == CmpInst::ICMP_EQ)
1763            return ConstantInt::get(ITy, false);
1764    }
1765
1766    // Assume that the constant null is on the right.
1767    if (llvm::isKnownNonNull(LHSPtr) && isa<ConstantPointerNull>(RHSPtr)) {
1768      if (Pred == CmpInst::ICMP_EQ)
1769        return ConstantInt::get(ITy, false);
1770      else if (Pred == CmpInst::ICMP_NE)
1771        return ConstantInt::get(ITy, true);
1772    }
1773  } else if (Argument *LHSArg = dyn_cast<Argument>(LHSPtr)) {
1774    RHSPtr = RHSPtr->stripInBoundsOffsets();
1775    // An alloca can't be equal to an argument unless they come from separate
1776    // functions via inlining.
1777    if (AllocaInst *RHSInst = dyn_cast<AllocaInst>(RHSPtr)) {
1778      if (LHSArg->getParent() == RHSInst->getParent()->getParent()) {
1779        if (Pred == CmpInst::ICMP_EQ)
1780          return ConstantInt::get(ITy, false);
1781        else if (Pred == CmpInst::ICMP_NE)
1782          return ConstantInt::get(ITy, true);
1783      }
1784    }
1785  }
1786
1787  // If we are comparing with zero then try hard since this is a common case.
1788  if (match(RHS, m_Zero())) {
1789    bool LHSKnownNonNegative, LHSKnownNegative;
1790    switch (Pred) {
1791    default: llvm_unreachable("Unknown ICmp predicate!");
1792    case ICmpInst::ICMP_ULT:
1793      return getFalse(ITy);
1794    case ICmpInst::ICMP_UGE:
1795      return getTrue(ITy);
1796    case ICmpInst::ICMP_EQ:
1797    case ICmpInst::ICMP_ULE:
1798      if (isKnownNonZero(LHS, Q.TD))
1799        return getFalse(ITy);
1800      break;
1801    case ICmpInst::ICMP_NE:
1802    case ICmpInst::ICMP_UGT:
1803      if (isKnownNonZero(LHS, Q.TD))
1804        return getTrue(ITy);
1805      break;
1806    case ICmpInst::ICMP_SLT:
1807      ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.TD);
1808      if (LHSKnownNegative)
1809        return getTrue(ITy);
1810      if (LHSKnownNonNegative)
1811        return getFalse(ITy);
1812      break;
1813    case ICmpInst::ICMP_SLE:
1814      ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.TD);
1815      if (LHSKnownNegative)
1816        return getTrue(ITy);
1817      if (LHSKnownNonNegative && isKnownNonZero(LHS, Q.TD))
1818        return getFalse(ITy);
1819      break;
1820    case ICmpInst::ICMP_SGE:
1821      ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.TD);
1822      if (LHSKnownNegative)
1823        return getFalse(ITy);
1824      if (LHSKnownNonNegative)
1825        return getTrue(ITy);
1826      break;
1827    case ICmpInst::ICMP_SGT:
1828      ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.TD);
1829      if (LHSKnownNegative)
1830        return getFalse(ITy);
1831      if (LHSKnownNonNegative && isKnownNonZero(LHS, Q.TD))
1832        return getTrue(ITy);
1833      break;
1834    }
1835  }
1836
1837  // See if we are doing a comparison with a constant integer.
1838  if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
1839    // Rule out tautological comparisons (eg., ult 0 or uge 0).
1840    ConstantRange RHS_CR = ICmpInst::makeConstantRange(Pred, CI->getValue());
1841    if (RHS_CR.isEmptySet())
1842      return ConstantInt::getFalse(CI->getContext());
1843    if (RHS_CR.isFullSet())
1844      return ConstantInt::getTrue(CI->getContext());
1845
1846    // Many binary operators with constant RHS have easy to compute constant
1847    // range.  Use them to check whether the comparison is a tautology.
1848    uint32_t Width = CI->getBitWidth();
1849    APInt Lower = APInt(Width, 0);
1850    APInt Upper = APInt(Width, 0);
1851    ConstantInt *CI2;
1852    if (match(LHS, m_URem(m_Value(), m_ConstantInt(CI2)))) {
1853      // 'urem x, CI2' produces [0, CI2).
1854      Upper = CI2->getValue();
1855    } else if (match(LHS, m_SRem(m_Value(), m_ConstantInt(CI2)))) {
1856      // 'srem x, CI2' produces (-|CI2|, |CI2|).
1857      Upper = CI2->getValue().abs();
1858      Lower = (-Upper) + 1;
1859    } else if (match(LHS, m_UDiv(m_ConstantInt(CI2), m_Value()))) {
1860      // 'udiv CI2, x' produces [0, CI2].
1861      Upper = CI2->getValue() + 1;
1862    } else if (match(LHS, m_UDiv(m_Value(), m_ConstantInt(CI2)))) {
1863      // 'udiv x, CI2' produces [0, UINT_MAX / CI2].
1864      APInt NegOne = APInt::getAllOnesValue(Width);
1865      if (!CI2->isZero())
1866        Upper = NegOne.udiv(CI2->getValue()) + 1;
1867    } else if (match(LHS, m_SDiv(m_Value(), m_ConstantInt(CI2)))) {
1868      // 'sdiv x, CI2' produces [INT_MIN / CI2, INT_MAX / CI2].
1869      APInt IntMin = APInt::getSignedMinValue(Width);
1870      APInt IntMax = APInt::getSignedMaxValue(Width);
1871      APInt Val = CI2->getValue().abs();
1872      if (!Val.isMinValue()) {
1873        Lower = IntMin.sdiv(Val);
1874        Upper = IntMax.sdiv(Val) + 1;
1875      }
1876    } else if (match(LHS, m_LShr(m_Value(), m_ConstantInt(CI2)))) {
1877      // 'lshr x, CI2' produces [0, UINT_MAX >> CI2].
1878      APInt NegOne = APInt::getAllOnesValue(Width);
1879      if (CI2->getValue().ult(Width))
1880        Upper = NegOne.lshr(CI2->getValue()) + 1;
1881    } else if (match(LHS, m_AShr(m_Value(), m_ConstantInt(CI2)))) {
1882      // 'ashr x, CI2' produces [INT_MIN >> CI2, INT_MAX >> CI2].
1883      APInt IntMin = APInt::getSignedMinValue(Width);
1884      APInt IntMax = APInt::getSignedMaxValue(Width);
1885      if (CI2->getValue().ult(Width)) {
1886        Lower = IntMin.ashr(CI2->getValue());
1887        Upper = IntMax.ashr(CI2->getValue()) + 1;
1888      }
1889    } else if (match(LHS, m_Or(m_Value(), m_ConstantInt(CI2)))) {
1890      // 'or x, CI2' produces [CI2, UINT_MAX].
1891      Lower = CI2->getValue();
1892    } else if (match(LHS, m_And(m_Value(), m_ConstantInt(CI2)))) {
1893      // 'and x, CI2' produces [0, CI2].
1894      Upper = CI2->getValue() + 1;
1895    }
1896    if (Lower != Upper) {
1897      ConstantRange LHS_CR = ConstantRange(Lower, Upper);
1898      if (RHS_CR.contains(LHS_CR))
1899        return ConstantInt::getTrue(RHS->getContext());
1900      if (RHS_CR.inverse().contains(LHS_CR))
1901        return ConstantInt::getFalse(RHS->getContext());
1902    }
1903  }
1904
1905  // Compare of cast, for example (zext X) != 0 -> X != 0
1906  if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) {
1907    Instruction *LI = cast<CastInst>(LHS);
1908    Value *SrcOp = LI->getOperand(0);
1909    Type *SrcTy = SrcOp->getType();
1910    Type *DstTy = LI->getType();
1911
1912    // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input
1913    // if the integer type is the same size as the pointer type.
1914    if (MaxRecurse && Q.TD && isa<PtrToIntInst>(LI) &&
1915        Q.TD->getPointerSizeInBits() == DstTy->getPrimitiveSizeInBits()) {
1916      if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
1917        // Transfer the cast to the constant.
1918        if (Value *V = SimplifyICmpInst(Pred, SrcOp,
1919                                        ConstantExpr::getIntToPtr(RHSC, SrcTy),
1920                                        Q, MaxRecurse-1))
1921          return V;
1922      } else if (PtrToIntInst *RI = dyn_cast<PtrToIntInst>(RHS)) {
1923        if (RI->getOperand(0)->getType() == SrcTy)
1924          // Compare without the cast.
1925          if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0),
1926                                          Q, MaxRecurse-1))
1927            return V;
1928      }
1929    }
1930
1931    if (isa<ZExtInst>(LHS)) {
1932      // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the
1933      // same type.
1934      if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) {
1935        if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
1936          // Compare X and Y.  Note that signed predicates become unsigned.
1937          if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred),
1938                                          SrcOp, RI->getOperand(0), Q,
1939                                          MaxRecurse-1))
1940            return V;
1941      }
1942      // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended
1943      // too.  If not, then try to deduce the result of the comparison.
1944      else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
1945        // Compute the constant that would happen if we truncated to SrcTy then
1946        // reextended to DstTy.
1947        Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
1948        Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy);
1949
1950        // If the re-extended constant didn't change then this is effectively
1951        // also a case of comparing two zero-extended values.
1952        if (RExt == CI && MaxRecurse)
1953          if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred),
1954                                        SrcOp, Trunc, Q, MaxRecurse-1))
1955            return V;
1956
1957        // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit
1958        // there.  Use this to work out the result of the comparison.
1959        if (RExt != CI) {
1960          switch (Pred) {
1961          default: llvm_unreachable("Unknown ICmp predicate!");
1962          // LHS <u RHS.
1963          case ICmpInst::ICMP_EQ:
1964          case ICmpInst::ICMP_UGT:
1965          case ICmpInst::ICMP_UGE:
1966            return ConstantInt::getFalse(CI->getContext());
1967
1968          case ICmpInst::ICMP_NE:
1969          case ICmpInst::ICMP_ULT:
1970          case ICmpInst::ICMP_ULE:
1971            return ConstantInt::getTrue(CI->getContext());
1972
1973          // LHS is non-negative.  If RHS is negative then LHS >s LHS.  If RHS
1974          // is non-negative then LHS <s RHS.
1975          case ICmpInst::ICMP_SGT:
1976          case ICmpInst::ICMP_SGE:
1977            return CI->getValue().isNegative() ?
1978              ConstantInt::getTrue(CI->getContext()) :
1979              ConstantInt::getFalse(CI->getContext());
1980
1981          case ICmpInst::ICMP_SLT:
1982          case ICmpInst::ICMP_SLE:
1983            return CI->getValue().isNegative() ?
1984              ConstantInt::getFalse(CI->getContext()) :
1985              ConstantInt::getTrue(CI->getContext());
1986          }
1987        }
1988      }
1989    }
1990
1991    if (isa<SExtInst>(LHS)) {
1992      // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the
1993      // same type.
1994      if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) {
1995        if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
1996          // Compare X and Y.  Note that the predicate does not change.
1997          if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0),
1998                                          Q, MaxRecurse-1))
1999            return V;
2000      }
2001      // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended
2002      // too.  If not, then try to deduce the result of the comparison.
2003      else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
2004        // Compute the constant that would happen if we truncated to SrcTy then
2005        // reextended to DstTy.
2006        Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
2007        Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy);
2008
2009        // If the re-extended constant didn't change then this is effectively
2010        // also a case of comparing two sign-extended values.
2011        if (RExt == CI && MaxRecurse)
2012          if (Value *V = SimplifyICmpInst(Pred, SrcOp, Trunc, Q, MaxRecurse-1))
2013            return V;
2014
2015        // Otherwise the upper bits of LHS are all equal, while RHS has varying
2016        // bits there.  Use this to work out the result of the comparison.
2017        if (RExt != CI) {
2018          switch (Pred) {
2019          default: llvm_unreachable("Unknown ICmp predicate!");
2020          case ICmpInst::ICMP_EQ:
2021            return ConstantInt::getFalse(CI->getContext());
2022          case ICmpInst::ICMP_NE:
2023            return ConstantInt::getTrue(CI->getContext());
2024
2025          // If RHS is non-negative then LHS <s RHS.  If RHS is negative then
2026          // LHS >s RHS.
2027          case ICmpInst::ICMP_SGT:
2028          case ICmpInst::ICMP_SGE:
2029            return CI->getValue().isNegative() ?
2030              ConstantInt::getTrue(CI->getContext()) :
2031              ConstantInt::getFalse(CI->getContext());
2032          case ICmpInst::ICMP_SLT:
2033          case ICmpInst::ICMP_SLE:
2034            return CI->getValue().isNegative() ?
2035              ConstantInt::getFalse(CI->getContext()) :
2036              ConstantInt::getTrue(CI->getContext());
2037
2038          // If LHS is non-negative then LHS <u RHS.  If LHS is negative then
2039          // LHS >u RHS.
2040          case ICmpInst::ICMP_UGT:
2041          case ICmpInst::ICMP_UGE:
2042            // Comparison is true iff the LHS <s 0.
2043            if (MaxRecurse)
2044              if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SLT, SrcOp,
2045                                              Constant::getNullValue(SrcTy),
2046                                              Q, MaxRecurse-1))
2047                return V;
2048            break;
2049          case ICmpInst::ICMP_ULT:
2050          case ICmpInst::ICMP_ULE:
2051            // Comparison is true iff the LHS >=s 0.
2052            if (MaxRecurse)
2053              if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SGE, SrcOp,
2054                                              Constant::getNullValue(SrcTy),
2055                                              Q, MaxRecurse-1))
2056                return V;
2057            break;
2058          }
2059        }
2060      }
2061    }
2062  }
2063
2064  // Special logic for binary operators.
2065  BinaryOperator *LBO = dyn_cast<BinaryOperator>(LHS);
2066  BinaryOperator *RBO = dyn_cast<BinaryOperator>(RHS);
2067  if (MaxRecurse && (LBO || RBO)) {
2068    // Analyze the case when either LHS or RHS is an add instruction.
2069    Value *A = 0, *B = 0, *C = 0, *D = 0;
2070    // LHS = A + B (or A and B are null); RHS = C + D (or C and D are null).
2071    bool NoLHSWrapProblem = false, NoRHSWrapProblem = false;
2072    if (LBO && LBO->getOpcode() == Instruction::Add) {
2073      A = LBO->getOperand(0); B = LBO->getOperand(1);
2074      NoLHSWrapProblem = ICmpInst::isEquality(Pred) ||
2075        (CmpInst::isUnsigned(Pred) && LBO->hasNoUnsignedWrap()) ||
2076        (CmpInst::isSigned(Pred) && LBO->hasNoSignedWrap());
2077    }
2078    if (RBO && RBO->getOpcode() == Instruction::Add) {
2079      C = RBO->getOperand(0); D = RBO->getOperand(1);
2080      NoRHSWrapProblem = ICmpInst::isEquality(Pred) ||
2081        (CmpInst::isUnsigned(Pred) && RBO->hasNoUnsignedWrap()) ||
2082        (CmpInst::isSigned(Pred) && RBO->hasNoSignedWrap());
2083    }
2084
2085    // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow.
2086    if ((A == RHS || B == RHS) && NoLHSWrapProblem)
2087      if (Value *V = SimplifyICmpInst(Pred, A == RHS ? B : A,
2088                                      Constant::getNullValue(RHS->getType()),
2089                                      Q, MaxRecurse-1))
2090        return V;
2091
2092    // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow.
2093    if ((C == LHS || D == LHS) && NoRHSWrapProblem)
2094      if (Value *V = SimplifyICmpInst(Pred,
2095                                      Constant::getNullValue(LHS->getType()),
2096                                      C == LHS ? D : C, Q, MaxRecurse-1))
2097        return V;
2098
2099    // icmp (X+Y), (X+Z) -> icmp Y,Z for equalities or if there is no overflow.
2100    if (A && C && (A == C || A == D || B == C || B == D) &&
2101        NoLHSWrapProblem && NoRHSWrapProblem) {
2102      // Determine Y and Z in the form icmp (X+Y), (X+Z).
2103      Value *Y, *Z;
2104      if (A == C) {
2105        // C + B == C + D  ->  B == D
2106        Y = B;
2107        Z = D;
2108      } else if (A == D) {
2109        // D + B == C + D  ->  B == C
2110        Y = B;
2111        Z = C;
2112      } else if (B == C) {
2113        // A + C == C + D  ->  A == D
2114        Y = A;
2115        Z = D;
2116      } else {
2117        assert(B == D);
2118        // A + D == C + D  ->  A == C
2119        Y = A;
2120        Z = C;
2121      }
2122      if (Value *V = SimplifyICmpInst(Pred, Y, Z, Q, MaxRecurse-1))
2123        return V;
2124    }
2125  }
2126
2127  if (LBO && match(LBO, m_URem(m_Value(), m_Specific(RHS)))) {
2128    bool KnownNonNegative, KnownNegative;
2129    switch (Pred) {
2130    default:
2131      break;
2132    case ICmpInst::ICMP_SGT:
2133    case ICmpInst::ICMP_SGE:
2134      ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.TD);
2135      if (!KnownNonNegative)
2136        break;
2137      // fall-through
2138    case ICmpInst::ICMP_EQ:
2139    case ICmpInst::ICMP_UGT:
2140    case ICmpInst::ICMP_UGE:
2141      return getFalse(ITy);
2142    case ICmpInst::ICMP_SLT:
2143    case ICmpInst::ICMP_SLE:
2144      ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.TD);
2145      if (!KnownNonNegative)
2146        break;
2147      // fall-through
2148    case ICmpInst::ICMP_NE:
2149    case ICmpInst::ICMP_ULT:
2150    case ICmpInst::ICMP_ULE:
2151      return getTrue(ITy);
2152    }
2153  }
2154  if (RBO && match(RBO, m_URem(m_Value(), m_Specific(LHS)))) {
2155    bool KnownNonNegative, KnownNegative;
2156    switch (Pred) {
2157    default:
2158      break;
2159    case ICmpInst::ICMP_SGT:
2160    case ICmpInst::ICMP_SGE:
2161      ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.TD);
2162      if (!KnownNonNegative)
2163        break;
2164      // fall-through
2165    case ICmpInst::ICMP_NE:
2166    case ICmpInst::ICMP_UGT:
2167    case ICmpInst::ICMP_UGE:
2168      return getTrue(ITy);
2169    case ICmpInst::ICMP_SLT:
2170    case ICmpInst::ICMP_SLE:
2171      ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.TD);
2172      if (!KnownNonNegative)
2173        break;
2174      // fall-through
2175    case ICmpInst::ICMP_EQ:
2176    case ICmpInst::ICMP_ULT:
2177    case ICmpInst::ICMP_ULE:
2178      return getFalse(ITy);
2179    }
2180  }
2181
2182  // x udiv y <=u x.
2183  if (LBO && match(LBO, m_UDiv(m_Specific(RHS), m_Value()))) {
2184    // icmp pred (X /u Y), X
2185    if (Pred == ICmpInst::ICMP_UGT)
2186      return getFalse(ITy);
2187    if (Pred == ICmpInst::ICMP_ULE)
2188      return getTrue(ITy);
2189  }
2190
2191  if (MaxRecurse && LBO && RBO && LBO->getOpcode() == RBO->getOpcode() &&
2192      LBO->getOperand(1) == RBO->getOperand(1)) {
2193    switch (LBO->getOpcode()) {
2194    default: break;
2195    case Instruction::UDiv:
2196    case Instruction::LShr:
2197      if (ICmpInst::isSigned(Pred))
2198        break;
2199      // fall-through
2200    case Instruction::SDiv:
2201    case Instruction::AShr:
2202      if (!LBO->isExact() || !RBO->isExact())
2203        break;
2204      if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
2205                                      RBO->getOperand(0), Q, MaxRecurse-1))
2206        return V;
2207      break;
2208    case Instruction::Shl: {
2209      bool NUW = LBO->hasNoUnsignedWrap() && RBO->hasNoUnsignedWrap();
2210      bool NSW = LBO->hasNoSignedWrap() && RBO->hasNoSignedWrap();
2211      if (!NUW && !NSW)
2212        break;
2213      if (!NSW && ICmpInst::isSigned(Pred))
2214        break;
2215      if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
2216                                      RBO->getOperand(0), Q, MaxRecurse-1))
2217        return V;
2218      break;
2219    }
2220    }
2221  }
2222
2223  // Simplify comparisons involving max/min.
2224  Value *A, *B;
2225  CmpInst::Predicate P = CmpInst::BAD_ICMP_PREDICATE;
2226  CmpInst::Predicate EqP; // Chosen so that "A == max/min(A,B)" iff "A EqP B".
2227
2228  // Signed variants on "max(a,b)>=a -> true".
2229  if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) {
2230    if (A != RHS) std::swap(A, B); // smax(A, B) pred A.
2231    EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B".
2232    // We analyze this as smax(A, B) pred A.
2233    P = Pred;
2234  } else if (match(RHS, m_SMax(m_Value(A), m_Value(B))) &&
2235             (A == LHS || B == LHS)) {
2236    if (A != LHS) std::swap(A, B); // A pred smax(A, B).
2237    EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B".
2238    // We analyze this as smax(A, B) swapped-pred A.
2239    P = CmpInst::getSwappedPredicate(Pred);
2240  } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) &&
2241             (A == RHS || B == RHS)) {
2242    if (A != RHS) std::swap(A, B); // smin(A, B) pred A.
2243    EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B".
2244    // We analyze this as smax(-A, -B) swapped-pred -A.
2245    // Note that we do not need to actually form -A or -B thanks to EqP.
2246    P = CmpInst::getSwappedPredicate(Pred);
2247  } else if (match(RHS, m_SMin(m_Value(A), m_Value(B))) &&
2248             (A == LHS || B == LHS)) {
2249    if (A != LHS) std::swap(A, B); // A pred smin(A, B).
2250    EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B".
2251    // We analyze this as smax(-A, -B) pred -A.
2252    // Note that we do not need to actually form -A or -B thanks to EqP.
2253    P = Pred;
2254  }
2255  if (P != CmpInst::BAD_ICMP_PREDICATE) {
2256    // Cases correspond to "max(A, B) p A".
2257    switch (P) {
2258    default:
2259      break;
2260    case CmpInst::ICMP_EQ:
2261    case CmpInst::ICMP_SLE:
2262      // Equivalent to "A EqP B".  This may be the same as the condition tested
2263      // in the max/min; if so, we can just return that.
2264      if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B))
2265        return V;
2266      if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B))
2267        return V;
2268      // Otherwise, see if "A EqP B" simplifies.
2269      if (MaxRecurse)
2270        if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse-1))
2271          return V;
2272      break;
2273    case CmpInst::ICMP_NE:
2274    case CmpInst::ICMP_SGT: {
2275      CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP);
2276      // Equivalent to "A InvEqP B".  This may be the same as the condition
2277      // tested in the max/min; if so, we can just return that.
2278      if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B))
2279        return V;
2280      if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B))
2281        return V;
2282      // Otherwise, see if "A InvEqP B" simplifies.
2283      if (MaxRecurse)
2284        if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse-1))
2285          return V;
2286      break;
2287    }
2288    case CmpInst::ICMP_SGE:
2289      // Always true.
2290      return getTrue(ITy);
2291    case CmpInst::ICMP_SLT:
2292      // Always false.
2293      return getFalse(ITy);
2294    }
2295  }
2296
2297  // Unsigned variants on "max(a,b)>=a -> true".
2298  P = CmpInst::BAD_ICMP_PREDICATE;
2299  if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) {
2300    if (A != RHS) std::swap(A, B); // umax(A, B) pred A.
2301    EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B".
2302    // We analyze this as umax(A, B) pred A.
2303    P = Pred;
2304  } else if (match(RHS, m_UMax(m_Value(A), m_Value(B))) &&
2305             (A == LHS || B == LHS)) {
2306    if (A != LHS) std::swap(A, B); // A pred umax(A, B).
2307    EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B".
2308    // We analyze this as umax(A, B) swapped-pred A.
2309    P = CmpInst::getSwappedPredicate(Pred);
2310  } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) &&
2311             (A == RHS || B == RHS)) {
2312    if (A != RHS) std::swap(A, B); // umin(A, B) pred A.
2313    EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B".
2314    // We analyze this as umax(-A, -B) swapped-pred -A.
2315    // Note that we do not need to actually form -A or -B thanks to EqP.
2316    P = CmpInst::getSwappedPredicate(Pred);
2317  } else if (match(RHS, m_UMin(m_Value(A), m_Value(B))) &&
2318             (A == LHS || B == LHS)) {
2319    if (A != LHS) std::swap(A, B); // A pred umin(A, B).
2320    EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B".
2321    // We analyze this as umax(-A, -B) pred -A.
2322    // Note that we do not need to actually form -A or -B thanks to EqP.
2323    P = Pred;
2324  }
2325  if (P != CmpInst::BAD_ICMP_PREDICATE) {
2326    // Cases correspond to "max(A, B) p A".
2327    switch (P) {
2328    default:
2329      break;
2330    case CmpInst::ICMP_EQ:
2331    case CmpInst::ICMP_ULE:
2332      // Equivalent to "A EqP B".  This may be the same as the condition tested
2333      // in the max/min; if so, we can just return that.
2334      if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B))
2335        return V;
2336      if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B))
2337        return V;
2338      // Otherwise, see if "A EqP B" simplifies.
2339      if (MaxRecurse)
2340        if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse-1))
2341          return V;
2342      break;
2343    case CmpInst::ICMP_NE:
2344    case CmpInst::ICMP_UGT: {
2345      CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP);
2346      // Equivalent to "A InvEqP B".  This may be the same as the condition
2347      // tested in the max/min; if so, we can just return that.
2348      if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B))
2349        return V;
2350      if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B))
2351        return V;
2352      // Otherwise, see if "A InvEqP B" simplifies.
2353      if (MaxRecurse)
2354        if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse-1))
2355          return V;
2356      break;
2357    }
2358    case CmpInst::ICMP_UGE:
2359      // Always true.
2360      return getTrue(ITy);
2361    case CmpInst::ICMP_ULT:
2362      // Always false.
2363      return getFalse(ITy);
2364    }
2365  }
2366
2367  // Variants on "max(x,y) >= min(x,z)".
2368  Value *C, *D;
2369  if (match(LHS, m_SMax(m_Value(A), m_Value(B))) &&
2370      match(RHS, m_SMin(m_Value(C), m_Value(D))) &&
2371      (A == C || A == D || B == C || B == D)) {
2372    // max(x, ?) pred min(x, ?).
2373    if (Pred == CmpInst::ICMP_SGE)
2374      // Always true.
2375      return getTrue(ITy);
2376    if (Pred == CmpInst::ICMP_SLT)
2377      // Always false.
2378      return getFalse(ITy);
2379  } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) &&
2380             match(RHS, m_SMax(m_Value(C), m_Value(D))) &&
2381             (A == C || A == D || B == C || B == D)) {
2382    // min(x, ?) pred max(x, ?).
2383    if (Pred == CmpInst::ICMP_SLE)
2384      // Always true.
2385      return getTrue(ITy);
2386    if (Pred == CmpInst::ICMP_SGT)
2387      // Always false.
2388      return getFalse(ITy);
2389  } else if (match(LHS, m_UMax(m_Value(A), m_Value(B))) &&
2390             match(RHS, m_UMin(m_Value(C), m_Value(D))) &&
2391             (A == C || A == D || B == C || B == D)) {
2392    // max(x, ?) pred min(x, ?).
2393    if (Pred == CmpInst::ICMP_UGE)
2394      // Always true.
2395      return getTrue(ITy);
2396    if (Pred == CmpInst::ICMP_ULT)
2397      // Always false.
2398      return getFalse(ITy);
2399  } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) &&
2400             match(RHS, m_UMax(m_Value(C), m_Value(D))) &&
2401             (A == C || A == D || B == C || B == D)) {
2402    // min(x, ?) pred max(x, ?).
2403    if (Pred == CmpInst::ICMP_ULE)
2404      // Always true.
2405      return getTrue(ITy);
2406    if (Pred == CmpInst::ICMP_UGT)
2407      // Always false.
2408      return getFalse(ITy);
2409  }
2410
2411  // Simplify comparisons of related pointers using a powerful, recursive
2412  // GEP-walk when we have target data available..
2413  if (Q.TD && LHS->getType()->isPointerTy() && RHS->getType()->isPointerTy())
2414    if (Constant *C = computePointerICmp(*Q.TD, Pred, LHS, RHS))
2415      return C;
2416
2417  if (GetElementPtrInst *GLHS = dyn_cast<GetElementPtrInst>(LHS)) {
2418    if (GEPOperator *GRHS = dyn_cast<GEPOperator>(RHS)) {
2419      if (GLHS->getPointerOperand() == GRHS->getPointerOperand() &&
2420          GLHS->hasAllConstantIndices() && GRHS->hasAllConstantIndices() &&
2421          (ICmpInst::isEquality(Pred) ||
2422           (GLHS->isInBounds() && GRHS->isInBounds() &&
2423            Pred == ICmpInst::getSignedPredicate(Pred)))) {
2424        // The bases are equal and the indices are constant.  Build a constant
2425        // expression GEP with the same indices and a null base pointer to see
2426        // what constant folding can make out of it.
2427        Constant *Null = Constant::getNullValue(GLHS->getPointerOperandType());
2428        SmallVector<Value *, 4> IndicesLHS(GLHS->idx_begin(), GLHS->idx_end());
2429        Constant *NewLHS = ConstantExpr::getGetElementPtr(Null, IndicesLHS);
2430
2431        SmallVector<Value *, 4> IndicesRHS(GRHS->idx_begin(), GRHS->idx_end());
2432        Constant *NewRHS = ConstantExpr::getGetElementPtr(Null, IndicesRHS);
2433        return ConstantExpr::getICmp(Pred, NewLHS, NewRHS);
2434      }
2435    }
2436  }
2437
2438  // If the comparison is with the result of a select instruction, check whether
2439  // comparing with either branch of the select always yields the same value.
2440  if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
2441    if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse))
2442      return V;
2443
2444  // If the comparison is with the result of a phi instruction, check whether
2445  // doing the compare with each incoming phi value yields a common result.
2446  if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
2447    if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse))
2448      return V;
2449
2450  return 0;
2451}
2452
2453Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
2454                              const DataLayout *TD,
2455                              const TargetLibraryInfo *TLI,
2456                              const DominatorTree *DT) {
2457  return ::SimplifyICmpInst(Predicate, LHS, RHS, Query (TD, TLI, DT),
2458                            RecursionLimit);
2459}
2460
2461/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
2462/// fold the result.  If not, this returns null.
2463static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
2464                               const Query &Q, unsigned MaxRecurse) {
2465  CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
2466  assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
2467
2468  if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
2469    if (Constant *CRHS = dyn_cast<Constant>(RHS))
2470      return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.TD, Q.TLI);
2471
2472    // If we have a constant, make sure it is on the RHS.
2473    std::swap(LHS, RHS);
2474    Pred = CmpInst::getSwappedPredicate(Pred);
2475  }
2476
2477  // Fold trivial predicates.
2478  if (Pred == FCmpInst::FCMP_FALSE)
2479    return ConstantInt::get(GetCompareTy(LHS), 0);
2480  if (Pred == FCmpInst::FCMP_TRUE)
2481    return ConstantInt::get(GetCompareTy(LHS), 1);
2482
2483  if (isa<UndefValue>(RHS))                  // fcmp pred X, undef -> undef
2484    return UndefValue::get(GetCompareTy(LHS));
2485
2486  // fcmp x,x -> true/false.  Not all compares are foldable.
2487  if (LHS == RHS) {
2488    if (CmpInst::isTrueWhenEqual(Pred))
2489      return ConstantInt::get(GetCompareTy(LHS), 1);
2490    if (CmpInst::isFalseWhenEqual(Pred))
2491      return ConstantInt::get(GetCompareTy(LHS), 0);
2492  }
2493
2494  // Handle fcmp with constant RHS
2495  if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
2496    // If the constant is a nan, see if we can fold the comparison based on it.
2497    if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
2498      if (CFP->getValueAPF().isNaN()) {
2499        if (FCmpInst::isOrdered(Pred))   // True "if ordered and foo"
2500          return ConstantInt::getFalse(CFP->getContext());
2501        assert(FCmpInst::isUnordered(Pred) &&
2502               "Comparison must be either ordered or unordered!");
2503        // True if unordered.
2504        return ConstantInt::getTrue(CFP->getContext());
2505      }
2506      // Check whether the constant is an infinity.
2507      if (CFP->getValueAPF().isInfinity()) {
2508        if (CFP->getValueAPF().isNegative()) {
2509          switch (Pred) {
2510          case FCmpInst::FCMP_OLT:
2511            // No value is ordered and less than negative infinity.
2512            return ConstantInt::getFalse(CFP->getContext());
2513          case FCmpInst::FCMP_UGE:
2514            // All values are unordered with or at least negative infinity.
2515            return ConstantInt::getTrue(CFP->getContext());
2516          default:
2517            break;
2518          }
2519        } else {
2520          switch (Pred) {
2521          case FCmpInst::FCMP_OGT:
2522            // No value is ordered and greater than infinity.
2523            return ConstantInt::getFalse(CFP->getContext());
2524          case FCmpInst::FCMP_ULE:
2525            // All values are unordered with and at most infinity.
2526            return ConstantInt::getTrue(CFP->getContext());
2527          default:
2528            break;
2529          }
2530        }
2531      }
2532    }
2533  }
2534
2535  // If the comparison is with the result of a select instruction, check whether
2536  // comparing with either branch of the select always yields the same value.
2537  if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
2538    if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse))
2539      return V;
2540
2541  // If the comparison is with the result of a phi instruction, check whether
2542  // doing the compare with each incoming phi value yields a common result.
2543  if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
2544    if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse))
2545      return V;
2546
2547  return 0;
2548}
2549
2550Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
2551                              const DataLayout *TD,
2552                              const TargetLibraryInfo *TLI,
2553                              const DominatorTree *DT) {
2554  return ::SimplifyFCmpInst(Predicate, LHS, RHS, Query (TD, TLI, DT),
2555                            RecursionLimit);
2556}
2557
2558/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
2559/// the result.  If not, this returns null.
2560static Value *SimplifySelectInst(Value *CondVal, Value *TrueVal,
2561                                 Value *FalseVal, const Query &Q,
2562                                 unsigned MaxRecurse) {
2563  // select true, X, Y  -> X
2564  // select false, X, Y -> Y
2565  if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal))
2566    return CB->getZExtValue() ? TrueVal : FalseVal;
2567
2568  // select C, X, X -> X
2569  if (TrueVal == FalseVal)
2570    return TrueVal;
2571
2572  if (isa<UndefValue>(CondVal)) {  // select undef, X, Y -> X or Y
2573    if (isa<Constant>(TrueVal))
2574      return TrueVal;
2575    return FalseVal;
2576  }
2577  if (isa<UndefValue>(TrueVal))   // select C, undef, X -> X
2578    return FalseVal;
2579  if (isa<UndefValue>(FalseVal))   // select C, X, undef -> X
2580    return TrueVal;
2581
2582  return 0;
2583}
2584
2585Value *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
2586                                const DataLayout *TD,
2587                                const TargetLibraryInfo *TLI,
2588                                const DominatorTree *DT) {
2589  return ::SimplifySelectInst(Cond, TrueVal, FalseVal, Query (TD, TLI, DT),
2590                              RecursionLimit);
2591}
2592
2593/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
2594/// fold the result.  If not, this returns null.
2595static Value *SimplifyGEPInst(ArrayRef<Value *> Ops, const Query &Q, unsigned) {
2596  // The type of the GEP pointer operand.
2597  PointerType *PtrTy = dyn_cast<PointerType>(Ops[0]->getType());
2598  // The GEP pointer operand is not a pointer, it's a vector of pointers.
2599  if (!PtrTy)
2600    return 0;
2601
2602  // getelementptr P -> P.
2603  if (Ops.size() == 1)
2604    return Ops[0];
2605
2606  if (isa<UndefValue>(Ops[0])) {
2607    // Compute the (pointer) type returned by the GEP instruction.
2608    Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, Ops.slice(1));
2609    Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace());
2610    return UndefValue::get(GEPTy);
2611  }
2612
2613  if (Ops.size() == 2) {
2614    // getelementptr P, 0 -> P.
2615    if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
2616      if (C->isZero())
2617        return Ops[0];
2618    // getelementptr P, N -> P if P points to a type of zero size.
2619    if (Q.TD) {
2620      Type *Ty = PtrTy->getElementType();
2621      if (Ty->isSized() && Q.TD->getTypeAllocSize(Ty) == 0)
2622        return Ops[0];
2623    }
2624  }
2625
2626  // Check to see if this is constant foldable.
2627  for (unsigned i = 0, e = Ops.size(); i != e; ++i)
2628    if (!isa<Constant>(Ops[i]))
2629      return 0;
2630
2631  return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), Ops.slice(1));
2632}
2633
2634Value *llvm::SimplifyGEPInst(ArrayRef<Value *> Ops, const DataLayout *TD,
2635                             const TargetLibraryInfo *TLI,
2636                             const DominatorTree *DT) {
2637  return ::SimplifyGEPInst(Ops, Query (TD, TLI, DT), RecursionLimit);
2638}
2639
2640/// SimplifyInsertValueInst - Given operands for an InsertValueInst, see if we
2641/// can fold the result.  If not, this returns null.
2642static Value *SimplifyInsertValueInst(Value *Agg, Value *Val,
2643                                      ArrayRef<unsigned> Idxs, const Query &Q,
2644                                      unsigned) {
2645  if (Constant *CAgg = dyn_cast<Constant>(Agg))
2646    if (Constant *CVal = dyn_cast<Constant>(Val))
2647      return ConstantFoldInsertValueInstruction(CAgg, CVal, Idxs);
2648
2649  // insertvalue x, undef, n -> x
2650  if (match(Val, m_Undef()))
2651    return Agg;
2652
2653  // insertvalue x, (extractvalue y, n), n
2654  if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Val))
2655    if (EV->getAggregateOperand()->getType() == Agg->getType() &&
2656        EV->getIndices() == Idxs) {
2657      // insertvalue undef, (extractvalue y, n), n -> y
2658      if (match(Agg, m_Undef()))
2659        return EV->getAggregateOperand();
2660
2661      // insertvalue y, (extractvalue y, n), n -> y
2662      if (Agg == EV->getAggregateOperand())
2663        return Agg;
2664    }
2665
2666  return 0;
2667}
2668
2669Value *llvm::SimplifyInsertValueInst(Value *Agg, Value *Val,
2670                                     ArrayRef<unsigned> Idxs,
2671                                     const DataLayout *TD,
2672                                     const TargetLibraryInfo *TLI,
2673                                     const DominatorTree *DT) {
2674  return ::SimplifyInsertValueInst(Agg, Val, Idxs, Query (TD, TLI, DT),
2675                                   RecursionLimit);
2676}
2677
2678/// SimplifyPHINode - See if we can fold the given phi.  If not, returns null.
2679static Value *SimplifyPHINode(PHINode *PN, const Query &Q) {
2680  // If all of the PHI's incoming values are the same then replace the PHI node
2681  // with the common value.
2682  Value *CommonValue = 0;
2683  bool HasUndefInput = false;
2684  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
2685    Value *Incoming = PN->getIncomingValue(i);
2686    // If the incoming value is the phi node itself, it can safely be skipped.
2687    if (Incoming == PN) continue;
2688    if (isa<UndefValue>(Incoming)) {
2689      // Remember that we saw an undef value, but otherwise ignore them.
2690      HasUndefInput = true;
2691      continue;
2692    }
2693    if (CommonValue && Incoming != CommonValue)
2694      return 0;  // Not the same, bail out.
2695    CommonValue = Incoming;
2696  }
2697
2698  // If CommonValue is null then all of the incoming values were either undef or
2699  // equal to the phi node itself.
2700  if (!CommonValue)
2701    return UndefValue::get(PN->getType());
2702
2703  // If we have a PHI node like phi(X, undef, X), where X is defined by some
2704  // instruction, we cannot return X as the result of the PHI node unless it
2705  // dominates the PHI block.
2706  if (HasUndefInput)
2707    return ValueDominatesPHI(CommonValue, PN, Q.DT) ? CommonValue : 0;
2708
2709  return CommonValue;
2710}
2711
2712static Value *SimplifyTruncInst(Value *Op, Type *Ty, const Query &Q, unsigned) {
2713  if (Constant *C = dyn_cast<Constant>(Op))
2714    return ConstantFoldInstOperands(Instruction::Trunc, Ty, C, Q.TD, Q.TLI);
2715
2716  return 0;
2717}
2718
2719Value *llvm::SimplifyTruncInst(Value *Op, Type *Ty, const DataLayout *TD,
2720                               const TargetLibraryInfo *TLI,
2721                               const DominatorTree *DT) {
2722  return ::SimplifyTruncInst(Op, Ty, Query (TD, TLI, DT), RecursionLimit);
2723}
2724
2725//=== Helper functions for higher up the class hierarchy.
2726
2727/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
2728/// fold the result.  If not, this returns null.
2729static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
2730                            const Query &Q, unsigned MaxRecurse) {
2731  switch (Opcode) {
2732  case Instruction::Add:
2733    return SimplifyAddInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false,
2734                           Q, MaxRecurse);
2735  case Instruction::Sub:
2736    return SimplifySubInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false,
2737                           Q, MaxRecurse);
2738  case Instruction::Mul:  return SimplifyMulInst (LHS, RHS, Q, MaxRecurse);
2739  case Instruction::SDiv: return SimplifySDivInst(LHS, RHS, Q, MaxRecurse);
2740  case Instruction::UDiv: return SimplifyUDivInst(LHS, RHS, Q, MaxRecurse);
2741  case Instruction::FDiv: return SimplifyFDivInst(LHS, RHS, Q, MaxRecurse);
2742  case Instruction::SRem: return SimplifySRemInst(LHS, RHS, Q, MaxRecurse);
2743  case Instruction::URem: return SimplifyURemInst(LHS, RHS, Q, MaxRecurse);
2744  case Instruction::FRem: return SimplifyFRemInst(LHS, RHS, Q, MaxRecurse);
2745  case Instruction::Shl:
2746    return SimplifyShlInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false,
2747                           Q, MaxRecurse);
2748  case Instruction::LShr:
2749    return SimplifyLShrInst(LHS, RHS, /*isExact*/false, Q, MaxRecurse);
2750  case Instruction::AShr:
2751    return SimplifyAShrInst(LHS, RHS, /*isExact*/false, Q, MaxRecurse);
2752  case Instruction::And: return SimplifyAndInst(LHS, RHS, Q, MaxRecurse);
2753  case Instruction::Or:  return SimplifyOrInst (LHS, RHS, Q, MaxRecurse);
2754  case Instruction::Xor: return SimplifyXorInst(LHS, RHS, Q, MaxRecurse);
2755  default:
2756    if (Constant *CLHS = dyn_cast<Constant>(LHS))
2757      if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
2758        Constant *COps[] = {CLHS, CRHS};
2759        return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, Q.TD,
2760                                        Q.TLI);
2761      }
2762
2763    // If the operation is associative, try some generic simplifications.
2764    if (Instruction::isAssociative(Opcode))
2765      if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, Q, MaxRecurse))
2766        return V;
2767
2768    // If the operation is with the result of a select instruction check whether
2769    // operating on either branch of the select always yields the same value.
2770    if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
2771      if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, Q, MaxRecurse))
2772        return V;
2773
2774    // If the operation is with the result of a phi instruction, check whether
2775    // operating on all incoming values of the phi always yields the same value.
2776    if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
2777      if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, Q, MaxRecurse))
2778        return V;
2779
2780    return 0;
2781  }
2782}
2783
2784Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
2785                           const DataLayout *TD, const TargetLibraryInfo *TLI,
2786                           const DominatorTree *DT) {
2787  return ::SimplifyBinOp(Opcode, LHS, RHS, Query (TD, TLI, DT), RecursionLimit);
2788}
2789
2790/// SimplifyCmpInst - Given operands for a CmpInst, see if we can
2791/// fold the result.
2792static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
2793                              const Query &Q, unsigned MaxRecurse) {
2794  if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
2795    return SimplifyICmpInst(Predicate, LHS, RHS, Q, MaxRecurse);
2796  return SimplifyFCmpInst(Predicate, LHS, RHS, Q, MaxRecurse);
2797}
2798
2799Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
2800                             const DataLayout *TD, const TargetLibraryInfo *TLI,
2801                             const DominatorTree *DT) {
2802  return ::SimplifyCmpInst(Predicate, LHS, RHS, Query (TD, TLI, DT),
2803                           RecursionLimit);
2804}
2805
2806static Value *SimplifyCallInst(CallInst *CI, const Query &) {
2807  // call undef -> undef
2808  if (isa<UndefValue>(CI->getCalledValue()))
2809    return UndefValue::get(CI->getType());
2810
2811  return 0;
2812}
2813
2814/// SimplifyInstruction - See if we can compute a simplified version of this
2815/// instruction.  If not, this returns null.
2816Value *llvm::SimplifyInstruction(Instruction *I, const DataLayout *TD,
2817                                 const TargetLibraryInfo *TLI,
2818                                 const DominatorTree *DT) {
2819  Value *Result;
2820
2821  switch (I->getOpcode()) {
2822  default:
2823    Result = ConstantFoldInstruction(I, TD, TLI);
2824    break;
2825  case Instruction::Add:
2826    Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1),
2827                             cast<BinaryOperator>(I)->hasNoSignedWrap(),
2828                             cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
2829                             TD, TLI, DT);
2830    break;
2831  case Instruction::Sub:
2832    Result = SimplifySubInst(I->getOperand(0), I->getOperand(1),
2833                             cast<BinaryOperator>(I)->hasNoSignedWrap(),
2834                             cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
2835                             TD, TLI, DT);
2836    break;
2837  case Instruction::FMul:
2838    Result = SimplifyFMulInst(I->getOperand(0), I->getOperand(1),
2839                              I->getFastMathFlags(), TD, TLI, DT);
2840    break;
2841  case Instruction::Mul:
2842    Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT);
2843    break;
2844  case Instruction::SDiv:
2845    Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT);
2846    break;
2847  case Instruction::UDiv:
2848    Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT);
2849    break;
2850  case Instruction::FDiv:
2851    Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT);
2852    break;
2853  case Instruction::SRem:
2854    Result = SimplifySRemInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT);
2855    break;
2856  case Instruction::URem:
2857    Result = SimplifyURemInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT);
2858    break;
2859  case Instruction::FRem:
2860    Result = SimplifyFRemInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT);
2861    break;
2862  case Instruction::Shl:
2863    Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1),
2864                             cast<BinaryOperator>(I)->hasNoSignedWrap(),
2865                             cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
2866                             TD, TLI, DT);
2867    break;
2868  case Instruction::LShr:
2869    Result = SimplifyLShrInst(I->getOperand(0), I->getOperand(1),
2870                              cast<BinaryOperator>(I)->isExact(),
2871                              TD, TLI, DT);
2872    break;
2873  case Instruction::AShr:
2874    Result = SimplifyAShrInst(I->getOperand(0), I->getOperand(1),
2875                              cast<BinaryOperator>(I)->isExact(),
2876                              TD, TLI, DT);
2877    break;
2878  case Instruction::And:
2879    Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT);
2880    break;
2881  case Instruction::Or:
2882    Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT);
2883    break;
2884  case Instruction::Xor:
2885    Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT);
2886    break;
2887  case Instruction::ICmp:
2888    Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
2889                              I->getOperand(0), I->getOperand(1), TD, TLI, DT);
2890    break;
2891  case Instruction::FCmp:
2892    Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
2893                              I->getOperand(0), I->getOperand(1), TD, TLI, DT);
2894    break;
2895  case Instruction::Select:
2896    Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1),
2897                                I->getOperand(2), TD, TLI, DT);
2898    break;
2899  case Instruction::GetElementPtr: {
2900    SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
2901    Result = SimplifyGEPInst(Ops, TD, TLI, DT);
2902    break;
2903  }
2904  case Instruction::InsertValue: {
2905    InsertValueInst *IV = cast<InsertValueInst>(I);
2906    Result = SimplifyInsertValueInst(IV->getAggregateOperand(),
2907                                     IV->getInsertedValueOperand(),
2908                                     IV->getIndices(), TD, TLI, DT);
2909    break;
2910  }
2911  case Instruction::PHI:
2912    Result = SimplifyPHINode(cast<PHINode>(I), Query (TD, TLI, DT));
2913    break;
2914  case Instruction::Call:
2915    Result = SimplifyCallInst(cast<CallInst>(I), Query (TD, TLI, DT));
2916    break;
2917  case Instruction::Trunc:
2918    Result = SimplifyTruncInst(I->getOperand(0), I->getType(), TD, TLI, DT);
2919    break;
2920  }
2921
2922  /// If called on unreachable code, the above logic may report that the
2923  /// instruction simplified to itself.  Make life easier for users by
2924  /// detecting that case here, returning a safe value instead.
2925  return Result == I ? UndefValue::get(I->getType()) : Result;
2926}
2927
2928/// \brief Implementation of recursive simplification through an instructions
2929/// uses.
2930///
2931/// This is the common implementation of the recursive simplification routines.
2932/// If we have a pre-simplified value in 'SimpleV', that is forcibly used to
2933/// replace the instruction 'I'. Otherwise, we simply add 'I' to the list of
2934/// instructions to process and attempt to simplify it using
2935/// InstructionSimplify.
2936///
2937/// This routine returns 'true' only when *it* simplifies something. The passed
2938/// in simplified value does not count toward this.
2939static bool replaceAndRecursivelySimplifyImpl(Instruction *I, Value *SimpleV,
2940                                              const DataLayout *TD,
2941                                              const TargetLibraryInfo *TLI,
2942                                              const DominatorTree *DT) {
2943  bool Simplified = false;
2944  SmallSetVector<Instruction *, 8> Worklist;
2945
2946  // If we have an explicit value to collapse to, do that round of the
2947  // simplification loop by hand initially.
2948  if (SimpleV) {
2949    for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); UI != UE;
2950         ++UI)
2951      if (*UI != I)
2952        Worklist.insert(cast<Instruction>(*UI));
2953
2954    // Replace the instruction with its simplified value.
2955    I->replaceAllUsesWith(SimpleV);
2956
2957    // Gracefully handle edge cases where the instruction is not wired into any
2958    // parent block.
2959    if (I->getParent())
2960      I->eraseFromParent();
2961  } else {
2962    Worklist.insert(I);
2963  }
2964
2965  // Note that we must test the size on each iteration, the worklist can grow.
2966  for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
2967    I = Worklist[Idx];
2968
2969    // See if this instruction simplifies.
2970    SimpleV = SimplifyInstruction(I, TD, TLI, DT);
2971    if (!SimpleV)
2972      continue;
2973
2974    Simplified = true;
2975
2976    // Stash away all the uses of the old instruction so we can check them for
2977    // recursive simplifications after a RAUW. This is cheaper than checking all
2978    // uses of To on the recursive step in most cases.
2979    for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); UI != UE;
2980         ++UI)
2981      Worklist.insert(cast<Instruction>(*UI));
2982
2983    // Replace the instruction with its simplified value.
2984    I->replaceAllUsesWith(SimpleV);
2985
2986    // Gracefully handle edge cases where the instruction is not wired into any
2987    // parent block.
2988    if (I->getParent())
2989      I->eraseFromParent();
2990  }
2991  return Simplified;
2992}
2993
2994bool llvm::recursivelySimplifyInstruction(Instruction *I,
2995                                          const DataLayout *TD,
2996                                          const TargetLibraryInfo *TLI,
2997                                          const DominatorTree *DT) {
2998  return replaceAndRecursivelySimplifyImpl(I, 0, TD, TLI, DT);
2999}
3000
3001bool llvm::replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV,
3002                                         const DataLayout *TD,
3003                                         const TargetLibraryInfo *TLI,
3004                                         const DominatorTree *DT) {
3005  assert(I != SimpleV && "replaceAndRecursivelySimplify(X,X) is not valid!");
3006  assert(SimpleV && "Must provide a simplified value.");
3007  return replaceAndRecursivelySimplifyImpl(I, SimpleV, TD, TLI, DT);
3008}
3009