InstructionSimplify.cpp revision a3e292c7e85efb33899f08238f57a85996a05a0b 
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/ADT/Statistic.h"
22#include "llvm/Analysis/InstructionSimplify.h"
23#include "llvm/Analysis/ConstantFolding.h"
24#include "llvm/Analysis/Dominators.h"
25#include "llvm/Analysis/ValueTracking.h"
26#include "llvm/Support/PatternMatch.h"
27#include "llvm/Support/ValueHandle.h"
28#include "llvm/Target/TargetData.h"
29using namespace llvm;
30using namespace llvm::PatternMatch;
31
32#define RecursionLimit 3
33
34STATISTIC(NumExpand,  "Number of expansions");
35STATISTIC(NumFactor , "Number of factorizations");
36STATISTIC(NumReassoc, "Number of reassociations");
37
38static Value *SimplifyAndInst(Value *, Value *, const TargetData *,
39                              const DominatorTree *, unsigned);
40static Value *SimplifyBinOp(unsigned, Value *, Value *, const TargetData *,
41                            const DominatorTree *, unsigned);
42static Value *SimplifyCmpInst(unsigned, Value *, Value *, const TargetData *,
43                              const DominatorTree *, unsigned);
44static Value *SimplifyOrInst(Value *, Value *, const TargetData *,
45                             const DominatorTree *, unsigned);
46static Value *SimplifyXorInst(Value *, Value *, const TargetData *,
47                              const DominatorTree *, unsigned);
48
49/// ValueDominatesPHI - Does the given value dominate the specified phi node?
50static bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
51  Instruction *I = dyn_cast<Instruction>(V);
52  if (!I)
53    // Arguments and constants dominate all instructions.
54    return true;
55
56  // If we have a DominatorTree then do a precise test.
57  if (DT)
58    return DT->dominates(I, P);
59
60  // Otherwise, if the instruction is in the entry block, and is not an invoke,
61  // then it obviously dominates all phi nodes.
62  if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() &&
63      !isa<InvokeInst>(I))
64    return true;
65
66  return false;
67}
68
69/// ExpandBinOp - Simplify "A op (B op' C)" by distributing op over op', turning
70/// it into "(A op B) op' (A op C)".  Here "op" is given by Opcode and "op'" is
71/// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS.
72/// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)".
73/// Returns the simplified value, or null if no simplification was performed.
74static Value *ExpandBinOp(unsigned Opcode, Value *LHS, Value *RHS,
75                          unsigned OpcToExpand, const TargetData *TD,
76                          const DominatorTree *DT, unsigned MaxRecurse) {
77  Instruction::BinaryOps OpcodeToExpand = (Instruction::BinaryOps)OpcToExpand;
78  // Recursion is always used, so bail out at once if we already hit the limit.
79  if (!MaxRecurse--)
80    return 0;
81
82  // Check whether the expression has the form "(A op' B) op C".
83  if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS))
84    if (Op0->getOpcode() == OpcodeToExpand) {
85      // It does!  Try turning it into "(A op C) op' (B op C)".
86      Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS;
87      // Do "A op C" and "B op C" both simplify?
88      if (Value *L = SimplifyBinOp(Opcode, A, C, TD, DT, MaxRecurse))
89        if (Value *R = SimplifyBinOp(Opcode, B, C, TD, DT, MaxRecurse)) {
90          // They do! Return "L op' R" if it simplifies or is already available.
91          // If "L op' R" equals "A op' B" then "L op' R" is just the LHS.
92          if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand)
93                                     && L == B && R == A)) {
94            ++NumExpand;
95            return LHS;
96          }
97          // Otherwise return "L op' R" if it simplifies.
98          if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, TD, DT,
99                                       MaxRecurse)) {
100            ++NumExpand;
101            return V;
102          }
103        }
104    }
105
106  // Check whether the expression has the form "A op (B op' C)".
107  if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS))
108    if (Op1->getOpcode() == OpcodeToExpand) {
109      // It does!  Try turning it into "(A op B) op' (A op C)".
110      Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1);
111      // Do "A op B" and "A op C" both simplify?
112      if (Value *L = SimplifyBinOp(Opcode, A, B, TD, DT, MaxRecurse))
113        if (Value *R = SimplifyBinOp(Opcode, A, C, TD, DT, MaxRecurse)) {
114          // They do! Return "L op' R" if it simplifies or is already available.
115          // If "L op' R" equals "B op' C" then "L op' R" is just the RHS.
116          if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand)
117                                     && L == C && R == B)) {
118            ++NumExpand;
119            return RHS;
120          }
121          // Otherwise return "L op' R" if it simplifies.
122          if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, TD, DT,
123                                       MaxRecurse)) {
124            ++NumExpand;
125            return V;
126          }
127        }
128    }
129
130  return 0;
131}
132
133/// FactorizeBinOp - Simplify "LHS Opcode RHS" by factorizing out a common term
134/// using the operation OpCodeToExtract.  For example, when Opcode is Add and
135/// OpCodeToExtract is Mul then this tries to turn "(A*B)+(A*C)" into "A*(B+C)".
136/// Returns the simplified value, or null if no simplification was performed.
137static Value *FactorizeBinOp(unsigned Opcode, Value *LHS, Value *RHS,
138                             unsigned OpcToExtract, const TargetData *TD,
139                             const DominatorTree *DT, unsigned MaxRecurse) {
140  Instruction::BinaryOps OpcodeToExtract = (Instruction::BinaryOps)OpcToExtract;
141  // Recursion is always used, so bail out at once if we already hit the limit.
142  if (!MaxRecurse--)
143    return 0;
144
145  BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
146  BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
147
148  if (!Op0 || Op0->getOpcode() != OpcodeToExtract ||
149      !Op1 || Op1->getOpcode() != OpcodeToExtract)
150    return 0;
151
152  // The expression has the form "(A op' B) op (C op' D)".
153  Value *A = Op0->getOperand(0), *B = Op0->getOperand(1);
154  Value *C = Op1->getOperand(0), *D = Op1->getOperand(1);
155
156  // Use left distributivity, i.e. "X op' (Y op Z) = (X op' Y) op (X op' Z)".
157  // Does the instruction have the form "(A op' B) op (A op' D)" or, in the
158  // commutative case, "(A op' B) op (C op' A)"?
159  if (A == C || (Instruction::isCommutative(OpcodeToExtract) && A == D)) {
160    Value *DD = A == C ? D : C;
161    // Form "A op' (B op DD)" if it simplifies completely.
162    // Does "B op DD" simplify?
163    if (Value *V = SimplifyBinOp(Opcode, B, DD, TD, DT, MaxRecurse)) {
164      // It does!  Return "A op' V" if it simplifies or is already available.
165      // If V equals B then "A op' V" is just the LHS.  If V equals DD then
166      // "A op' V" is just the RHS.
167      if (V == B || V == DD) {
168        ++NumFactor;
169        return V == B ? LHS : RHS;
170      }
171      // Otherwise return "A op' V" if it simplifies.
172      if (Value *W = SimplifyBinOp(OpcodeToExtract, A, V, TD, DT, MaxRecurse)) {
173        ++NumFactor;
174        return W;
175      }
176    }
177  }
178
179  // Use right distributivity, i.e. "(X op Y) op' Z = (X op' Z) op (Y op' Z)".
180  // Does the instruction have the form "(A op' B) op (C op' B)" or, in the
181  // commutative case, "(A op' B) op (B op' D)"?
182  if (B == D || (Instruction::isCommutative(OpcodeToExtract) && B == C)) {
183    Value *CC = B == D ? C : D;
184    // Form "(A op CC) op' B" if it simplifies completely..
185    // Does "A op CC" simplify?
186    if (Value *V = SimplifyBinOp(Opcode, A, CC, TD, DT, MaxRecurse)) {
187      // It does!  Return "V op' B" if it simplifies or is already available.
188      // If V equals A then "V op' B" is just the LHS.  If V equals CC then
189      // "V op' B" is just the RHS.
190      if (V == A || V == CC) {
191        ++NumFactor;
192        return V == A ? LHS : RHS;
193      }
194      // Otherwise return "V op' B" if it simplifies.
195      if (Value *W = SimplifyBinOp(OpcodeToExtract, V, B, TD, DT, MaxRecurse)) {
196        ++NumFactor;
197        return W;
198      }
199    }
200  }
201
202  return 0;
203}
204
205/// SimplifyAssociativeBinOp - Generic simplifications for associative binary
206/// operations.  Returns the simpler value, or null if none was found.
207static Value *SimplifyAssociativeBinOp(unsigned Opc, Value *LHS, Value *RHS,
208                                       const TargetData *TD,
209                                       const DominatorTree *DT,
210                                       unsigned MaxRecurse) {
211  Instruction::BinaryOps Opcode = (Instruction::BinaryOps)Opc;
212  assert(Instruction::isAssociative(Opcode) && "Not an associative operation!");
213
214  // Recursion is always used, so bail out at once if we already hit the limit.
215  if (!MaxRecurse--)
216    return 0;
217
218  BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
219  BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
220
221  // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely.
222  if (Op0 && Op0->getOpcode() == Opcode) {
223    Value *A = Op0->getOperand(0);
224    Value *B = Op0->getOperand(1);
225    Value *C = RHS;
226
227    // Does "B op C" simplify?
228    if (Value *V = SimplifyBinOp(Opcode, B, C, TD, DT, MaxRecurse)) {
229      // It does!  Return "A op V" if it simplifies or is already available.
230      // If V equals B then "A op V" is just the LHS.
231      if (V == B) return LHS;
232      // Otherwise return "A op V" if it simplifies.
233      if (Value *W = SimplifyBinOp(Opcode, A, V, TD, DT, MaxRecurse)) {
234        ++NumReassoc;
235        return W;
236      }
237    }
238  }
239
240  // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely.
241  if (Op1 && Op1->getOpcode() == Opcode) {
242    Value *A = LHS;
243    Value *B = Op1->getOperand(0);
244    Value *C = Op1->getOperand(1);
245
246    // Does "A op B" simplify?
247    if (Value *V = SimplifyBinOp(Opcode, A, B, TD, DT, MaxRecurse)) {
248      // It does!  Return "V op C" if it simplifies or is already available.
249      // If V equals B then "V op C" is just the RHS.
250      if (V == B) return RHS;
251      // Otherwise return "V op C" if it simplifies.
252      if (Value *W = SimplifyBinOp(Opcode, V, C, TD, DT, MaxRecurse)) {
253        ++NumReassoc;
254        return W;
255      }
256    }
257  }
258
259  // The remaining transforms require commutativity as well as associativity.
260  if (!Instruction::isCommutative(Opcode))
261    return 0;
262
263  // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely.
264  if (Op0 && Op0->getOpcode() == Opcode) {
265    Value *A = Op0->getOperand(0);
266    Value *B = Op0->getOperand(1);
267    Value *C = RHS;
268
269    // Does "C op A" simplify?
270    if (Value *V = SimplifyBinOp(Opcode, C, A, TD, DT, MaxRecurse)) {
271      // It does!  Return "V op B" if it simplifies or is already available.
272      // If V equals A then "V op B" is just the LHS.
273      if (V == A) return LHS;
274      // Otherwise return "V op B" if it simplifies.
275      if (Value *W = SimplifyBinOp(Opcode, V, B, TD, DT, MaxRecurse)) {
276        ++NumReassoc;
277        return W;
278      }
279    }
280  }
281
282  // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely.
283  if (Op1 && Op1->getOpcode() == Opcode) {
284    Value *A = LHS;
285    Value *B = Op1->getOperand(0);
286    Value *C = Op1->getOperand(1);
287
288    // Does "C op A" simplify?
289    if (Value *V = SimplifyBinOp(Opcode, C, A, TD, DT, MaxRecurse)) {
290      // It does!  Return "B op V" if it simplifies or is already available.
291      // If V equals C then "B op V" is just the RHS.
292      if (V == C) return RHS;
293      // Otherwise return "B op V" if it simplifies.
294      if (Value *W = SimplifyBinOp(Opcode, B, V, TD, DT, MaxRecurse)) {
295        ++NumReassoc;
296        return W;
297      }
298    }
299  }
300
301  return 0;
302}
303
304/// ThreadBinOpOverSelect - In the case of a binary operation with a select
305/// instruction as an operand, try to simplify the binop by seeing whether
306/// evaluating it on both branches of the select results in the same value.
307/// Returns the common value if so, otherwise returns null.
308static Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS,
309                                    const TargetData *TD,
310                                    const DominatorTree *DT,
311                                    unsigned MaxRecurse) {
312  // Recursion is always used, so bail out at once if we already hit the limit.
313  if (!MaxRecurse--)
314    return 0;
315
316  SelectInst *SI;
317  if (isa<SelectInst>(LHS)) {
318    SI = cast<SelectInst>(LHS);
319  } else {
320    assert(isa<SelectInst>(RHS) && "No select instruction operand!");
321    SI = cast<SelectInst>(RHS);
322  }
323
324  // Evaluate the BinOp on the true and false branches of the select.
325  Value *TV;
326  Value *FV;
327  if (SI == LHS) {
328    TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, DT, MaxRecurse);
329    FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, DT, MaxRecurse);
330  } else {
331    TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, DT, MaxRecurse);
332    FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, DT, MaxRecurse);
333  }
334
335  // If they simplified to the same value, then return the common value.
336  // If they both failed to simplify then return null.
337  if (TV == FV)
338    return TV;
339
340  // If one branch simplified to undef, return the other one.
341  if (TV && isa<UndefValue>(TV))
342    return FV;
343  if (FV && isa<UndefValue>(FV))
344    return TV;
345
346  // If applying the operation did not change the true and false select values,
347  // then the result of the binop is the select itself.
348  if (TV == SI->getTrueValue() && FV == SI->getFalseValue())
349    return SI;
350
351  // If one branch simplified and the other did not, and the simplified
352  // value is equal to the unsimplified one, return the simplified value.
353  // For example, select (cond, X, X & Z) & Z -> X & Z.
354  if ((FV && !TV) || (TV && !FV)) {
355    // Check that the simplified value has the form "X op Y" where "op" is the
356    // same as the original operation.
357    Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV);
358    if (Simplified && Simplified->getOpcode() == Opcode) {
359      // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS".
360      // We already know that "op" is the same as for the simplified value.  See
361      // if the operands match too.  If so, return the simplified value.
362      Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue();
363      Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS;
364      Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch;
365      if (Simplified->getOperand(0) == UnsimplifiedLHS &&
366          Simplified->getOperand(1) == UnsimplifiedRHS)
367        return Simplified;
368      if (Simplified->isCommutative() &&
369          Simplified->getOperand(1) == UnsimplifiedLHS &&
370          Simplified->getOperand(0) == UnsimplifiedRHS)
371        return Simplified;
372    }
373  }
374
375  return 0;
376}
377
378/// ThreadCmpOverSelect - In the case of a comparison with a select instruction,
379/// try to simplify the comparison by seeing whether both branches of the select
380/// result in the same value.  Returns the common value if so, otherwise returns
381/// null.
382static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS,
383                                  Value *RHS, const TargetData *TD,
384                                  const DominatorTree *DT,
385                                  unsigned MaxRecurse) {
386  // Recursion is always used, so bail out at once if we already hit the limit.
387  if (!MaxRecurse--)
388    return 0;
389
390  // Make sure the select is on the LHS.
391  if (!isa<SelectInst>(LHS)) {
392    std::swap(LHS, RHS);
393    Pred = CmpInst::getSwappedPredicate(Pred);
394  }
395  assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!");
396  SelectInst *SI = cast<SelectInst>(LHS);
397
398  // Now that we have "cmp select(cond, TV, FV), RHS", analyse it.
399  // Does "cmp TV, RHS" simplify?
400  if (Value *TCmp = SimplifyCmpInst(Pred, SI->getTrueValue(), RHS, TD, DT,
401                                    MaxRecurse))
402    // It does!  Does "cmp FV, RHS" simplify?
403    if (Value *FCmp = SimplifyCmpInst(Pred, SI->getFalseValue(), RHS, TD, DT,
404                                      MaxRecurse))
405      // It does!  If they simplified to the same value, then use it as the
406      // result of the original comparison.
407      if (TCmp == FCmp)
408        return TCmp;
409  return 0;
410}
411
412/// ThreadBinOpOverPHI - In the case of a binary operation with an operand that
413/// is a PHI instruction, try to simplify the binop by seeing whether evaluating
414/// it on the incoming phi values yields the same result for every value.  If so
415/// returns the common value, otherwise returns null.
416static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS,
417                                 const TargetData *TD, const DominatorTree *DT,
418                                 unsigned MaxRecurse) {
419  // Recursion is always used, so bail out at once if we already hit the limit.
420  if (!MaxRecurse--)
421    return 0;
422
423  PHINode *PI;
424  if (isa<PHINode>(LHS)) {
425    PI = cast<PHINode>(LHS);
426    // Bail out if RHS and the phi may be mutually interdependent due to a loop.
427    if (!ValueDominatesPHI(RHS, PI, DT))
428      return 0;
429  } else {
430    assert(isa<PHINode>(RHS) && "No PHI instruction operand!");
431    PI = cast<PHINode>(RHS);
432    // Bail out if LHS and the phi may be mutually interdependent due to a loop.
433    if (!ValueDominatesPHI(LHS, PI, DT))
434      return 0;
435  }
436
437  // Evaluate the BinOp on the incoming phi values.
438  Value *CommonValue = 0;
439  for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
440    Value *Incoming = PI->getIncomingValue(i);
441    // If the incoming value is the phi node itself, it can safely be skipped.
442    if (Incoming == PI) continue;
443    Value *V = PI == LHS ?
444      SimplifyBinOp(Opcode, Incoming, RHS, TD, DT, MaxRecurse) :
445      SimplifyBinOp(Opcode, LHS, Incoming, TD, DT, MaxRecurse);
446    // If the operation failed to simplify, or simplified to a different value
447    // to previously, then give up.
448    if (!V || (CommonValue && V != CommonValue))
449      return 0;
450    CommonValue = V;
451  }
452
453  return CommonValue;
454}
455
456/// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try
457/// try to simplify the comparison by seeing whether comparing with all of the
458/// incoming phi values yields the same result every time.  If so returns the
459/// common result, otherwise returns null.
460static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
461                               const TargetData *TD, const DominatorTree *DT,
462                               unsigned MaxRecurse) {
463  // Recursion is always used, so bail out at once if we already hit the limit.
464  if (!MaxRecurse--)
465    return 0;
466
467  // Make sure the phi is on the LHS.
468  if (!isa<PHINode>(LHS)) {
469    std::swap(LHS, RHS);
470    Pred = CmpInst::getSwappedPredicate(Pred);
471  }
472  assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!");
473  PHINode *PI = cast<PHINode>(LHS);
474
475  // Bail out if RHS and the phi may be mutually interdependent due to a loop.
476  if (!ValueDominatesPHI(RHS, PI, DT))
477    return 0;
478
479  // Evaluate the BinOp on the incoming phi values.
480  Value *CommonValue = 0;
481  for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
482    Value *Incoming = PI->getIncomingValue(i);
483    // If the incoming value is the phi node itself, it can safely be skipped.
484    if (Incoming == PI) continue;
485    Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, DT, MaxRecurse);
486    // If the operation failed to simplify, or simplified to a different value
487    // to previously, then give up.
488    if (!V || (CommonValue && V != CommonValue))
489      return 0;
490    CommonValue = V;
491  }
492
493  return CommonValue;
494}
495
496/// SimplifyAddInst - Given operands for an Add, see if we can
497/// fold the result.  If not, this returns null.
498static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
499                              const TargetData *TD, const DominatorTree *DT,
500                              unsigned MaxRecurse) {
501  if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
502    if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
503      Constant *Ops[] = { CLHS, CRHS };
504      return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(),
505                                      Ops, 2, TD);
506    }
507
508    // Canonicalize the constant to the RHS.
509    std::swap(Op0, Op1);
510  }
511
512  // X + undef -> undef
513  if (isa<UndefValue>(Op1))
514    return Op1;
515
516  // X + 0 -> X
517  if (match(Op1, m_Zero()))
518    return Op0;
519
520  // X + (Y - X) -> Y
521  // (Y - X) + X -> Y
522  // Eg: X + -X -> 0
523  Value *Y = 0;
524  if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) ||
525      match(Op0, m_Sub(m_Value(Y), m_Specific(Op1))))
526    return Y;
527
528  // X + ~X -> -1   since   ~X = -X-1
529  if (match(Op0, m_Not(m_Specific(Op1))) ||
530      match(Op1, m_Not(m_Specific(Op0))))
531    return Constant::getAllOnesValue(Op0->getType());
532
533  /// i1 add -> xor.
534  if (MaxRecurse && Op0->getType()->isIntegerTy(1))
535    if (Value *V = SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1))
536      return V;
537
538  // Try some generic simplifications for associative operations.
539  if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, TD, DT,
540                                          MaxRecurse))
541    return V;
542
543  // Mul distributes over Add.  Try some generic simplifications based on this.
544  if (Value *V = FactorizeBinOp(Instruction::Add, Op0, Op1, Instruction::Mul,
545                                TD, DT, MaxRecurse))
546    return V;
547
548  // Threading Add over selects and phi nodes is pointless, so don't bother.
549  // Threading over the select in "A + select(cond, B, C)" means evaluating
550  // "A+B" and "A+C" and seeing if they are equal; but they are equal if and
551  // only if B and C are equal.  If B and C are equal then (since we assume
552  // that operands have already been simplified) "select(cond, B, C)" should
553  // have been simplified to the common value of B and C already.  Analysing
554  // "A+B" and "A+C" thus gains nothing, but costs compile time.  Similarly
555  // for threading over phi nodes.
556
557  return 0;
558}
559
560Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
561                             const TargetData *TD, const DominatorTree *DT) {
562  return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit);
563}
564
565/// SimplifySubInst - Given operands for a Sub, see if we can
566/// fold the result.  If not, this returns null.
567static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
568                              const TargetData *TD, const DominatorTree *DT,
569                              unsigned MaxRecurse) {
570  if (Constant *CLHS = dyn_cast<Constant>(Op0))
571    if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
572      Constant *Ops[] = { CLHS, CRHS };
573      return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(),
574                                      Ops, 2, TD);
575    }
576
577  // X - undef -> undef
578  // undef - X -> undef
579  if (isa<UndefValue>(Op0) || isa<UndefValue>(Op1))
580    return UndefValue::get(Op0->getType());
581
582  // X - 0 -> X
583  if (match(Op1, m_Zero()))
584    return Op0;
585
586  // X - X -> 0
587  if (Op0 == Op1)
588    return Constant::getNullValue(Op0->getType());
589
590  // (X*2) - X -> X
591  // (X<<1) - X -> X
592  Value *X = 0;
593  if (match(Op0, m_Mul(m_Specific(Op1), m_ConstantInt<2>())) ||
594      match(Op0, m_Shl(m_Specific(Op1), m_One())))
595    return Op1;
596
597  // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies.
598  // For example, (X + Y) - Y -> X; (Y + X) - Y -> X
599  Value *Y = 0, *Z = Op1;
600  if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z
601    // See if "V === Y - Z" simplifies.
602    if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, TD, DT, MaxRecurse-1))
603      // It does!  Now see if "X + V" simplifies.
604      if (Value *W = SimplifyBinOp(Instruction::Add, X, V, TD, DT,
605                                   MaxRecurse-1)) {
606        // It does, we successfully reassociated!
607        ++NumReassoc;
608        return W;
609      }
610    // See if "V === X - Z" simplifies.
611    if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, TD, DT, MaxRecurse-1))
612      // It does!  Now see if "Y + V" simplifies.
613      if (Value *W = SimplifyBinOp(Instruction::Add, Y, V, TD, DT,
614                                   MaxRecurse-1)) {
615        // It does, we successfully reassociated!
616        ++NumReassoc;
617        return W;
618      }
619  }
620
621  // X - (Y + Z) -> (X - Y) - Z or (X - Z) - Y if everything simplifies.
622  // For example, X - (X + 1) -> -1
623  X = Op0;
624  if (MaxRecurse && match(Op1, m_Add(m_Value(Y), m_Value(Z)))) { // X - (Y + Z)
625    // See if "V === X - Y" simplifies.
626    if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, TD, DT, MaxRecurse-1))
627      // It does!  Now see if "V - Z" simplifies.
628      if (Value *W = SimplifyBinOp(Instruction::Sub, V, Z, TD, DT,
629                                   MaxRecurse-1)) {
630        // It does, we successfully reassociated!
631        ++NumReassoc;
632        return W;
633      }
634    // See if "V === X - Z" simplifies.
635    if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, TD, DT, MaxRecurse-1))
636      // It does!  Now see if "V - Y" simplifies.
637      if (Value *W = SimplifyBinOp(Instruction::Sub, V, Y, TD, DT,
638                                   MaxRecurse-1)) {
639        // It does, we successfully reassociated!
640        ++NumReassoc;
641        return W;
642      }
643  }
644
645  // Z - (X - Y) -> (Z - X) + Y if everything simplifies.
646  // For example, X - (X - Y) -> Y.
647  Z = Op0;
648  if (MaxRecurse && match(Op1, m_Sub(m_Value(X), m_Value(Y)))) // Z - (X - Y)
649    // See if "V === Z - X" simplifies.
650    if (Value *V = SimplifyBinOp(Instruction::Sub, Z, X, TD, DT, MaxRecurse-1))
651      // It does!  Now see if "V + Y" simplifies.
652      if (Value *W = SimplifyBinOp(Instruction::Add, V, Y, TD, DT,
653                                   MaxRecurse-1)) {
654        // It does, we successfully reassociated!
655        ++NumReassoc;
656        return W;
657      }
658
659  // Mul distributes over Sub.  Try some generic simplifications based on this.
660  if (Value *V = FactorizeBinOp(Instruction::Sub, Op0, Op1, Instruction::Mul,
661                                TD, DT, MaxRecurse))
662    return V;
663
664  // i1 sub -> xor.
665  if (MaxRecurse && Op0->getType()->isIntegerTy(1))
666    if (Value *V = SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1))
667      return V;
668
669  // Threading Sub over selects and phi nodes is pointless, so don't bother.
670  // Threading over the select in "A - select(cond, B, C)" means evaluating
671  // "A-B" and "A-C" and seeing if they are equal; but they are equal if and
672  // only if B and C are equal.  If B and C are equal then (since we assume
673  // that operands have already been simplified) "select(cond, B, C)" should
674  // have been simplified to the common value of B and C already.  Analysing
675  // "A-B" and "A-C" thus gains nothing, but costs compile time.  Similarly
676  // for threading over phi nodes.
677
678  return 0;
679}
680
681Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
682                             const TargetData *TD, const DominatorTree *DT) {
683  return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit);
684}
685
686/// SimplifyMulInst - Given operands for a Mul, see if we can
687/// fold the result.  If not, this returns null.
688static Value *SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD,
689                              const DominatorTree *DT, unsigned MaxRecurse) {
690  if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
691    if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
692      Constant *Ops[] = { CLHS, CRHS };
693      return ConstantFoldInstOperands(Instruction::Mul, CLHS->getType(),
694                                      Ops, 2, TD);
695    }
696
697    // Canonicalize the constant to the RHS.
698    std::swap(Op0, Op1);
699  }
700
701  // X * undef -> 0
702  if (isa<UndefValue>(Op1))
703    return Constant::getNullValue(Op0->getType());
704
705  // X * 0 -> 0
706  if (match(Op1, m_Zero()))
707    return Op1;
708
709  // X * 1 -> X
710  if (match(Op1, m_One()))
711    return Op0;
712
713  /// i1 mul -> and.
714  if (MaxRecurse && Op0->getType()->isIntegerTy(1))
715    if (Value *V = SimplifyAndInst(Op0, Op1, TD, DT, MaxRecurse-1))
716      return V;
717
718  // Try some generic simplifications for associative operations.
719  if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, TD, DT,
720                                          MaxRecurse))
721    return V;
722
723  // Mul distributes over Add.  Try some generic simplifications based on this.
724  if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add,
725                             TD, DT, MaxRecurse))
726    return V;
727
728  // If the operation is with the result of a select instruction, check whether
729  // operating on either branch of the select always yields the same value.
730  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
731    if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, TD, DT,
732                                         MaxRecurse))
733      return V;
734
735  // If the operation is with the result of a phi instruction, check whether
736  // operating on all incoming values of the phi always yields the same value.
737  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
738    if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, TD, DT,
739                                      MaxRecurse))
740      return V;
741
742  return 0;
743}
744
745Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD,
746                             const DominatorTree *DT) {
747  return ::SimplifyMulInst(Op0, Op1, TD, DT, RecursionLimit);
748}
749
750/// SimplifyDiv - Given operands for an SDiv or UDiv, see if we can
751/// fold the result.  If not, this returns null.
752static Value *SimplifyDiv(unsigned Opcode, Value *Op0, Value *Op1,
753                          const TargetData *TD, const DominatorTree *DT,
754                          unsigned MaxRecurse) {
755  if (Constant *C0 = dyn_cast<Constant>(Op0)) {
756    if (Constant *C1 = dyn_cast<Constant>(Op1)) {
757      Constant *Ops[] = { C0, C1 };
758      return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, 2, TD);
759    }
760  }
761
762  bool isSigned = Opcode == Instruction::SDiv;
763
764  // X / undef -> undef
765  if (isa<UndefValue>(Op1))
766    return Op1;
767
768  // undef / X -> 0
769  if (isa<UndefValue>(Op0))
770    return Constant::getNullValue(Op0->getType());
771
772  // 0 / X -> 0, we don't need to preserve faults!
773  if (match(Op0, m_Zero()))
774    return Op0;
775
776  // X / 1 -> X
777  if (match(Op1, m_One()))
778    return Op0;
779  // Vector case. TODO: Have m_One match vectors.
780  if (ConstantVector *Op1V = dyn_cast<ConstantVector>(Op1)) {
781    if (ConstantInt *X = cast_or_null<ConstantInt>(Op1V->getSplatValue()))
782      if (X->isOne())
783        return Op0;
784  }
785
786  if (Op0->getType()->isIntegerTy(1))
787    // It can't be division by zero, hence it must be division by one.
788    return Op0;
789
790  // X / X -> 1
791  if (Op0 == Op1)
792    return ConstantInt::get(Op0->getType(), 1);
793
794  // (X * Y) / Y -> X if the multiplication does not overflow.
795  Value *X = 0, *Y = 0;
796  if (match(Op0, m_Mul(m_Value(X), m_Value(Y))) && (X == Op1 || Y == Op1)) {
797    if (Y != Op1) std::swap(X, Y); // Ensure expression is (X * Y) / Y, Y = Op1
798    BinaryOperator *Mul = dyn_cast<BinaryOperator>(Op0);
799    // If the Mul knows it does not overflow, then we are good to go.
800    if ((isSigned && Mul->hasNoSignedWrap()) ||
801        (!isSigned && Mul->hasNoUnsignedWrap()))
802      return X;
803    // If X has the form X = A / Y then X * Y cannot overflow.
804    if (BinaryOperator *Div = dyn_cast<BinaryOperator>(X))
805      if (Div->getOpcode() == Opcode && Div->getOperand(1) == Y)
806        return X;
807  }
808
809  // (X rem Y) / Y -> 0
810  if ((isSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) ||
811      (!isSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
812    return Constant::getNullValue(Op0->getType());
813
814  // If the operation is with the result of a select instruction, check whether
815  // operating on either branch of the select always yields the same value.
816  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
817    if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, TD, DT, MaxRecurse))
818      return V;
819
820  // If the operation is with the result of a phi instruction, check whether
821  // operating on all incoming values of the phi always yields the same value.
822  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
823    if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, TD, DT, MaxRecurse))
824      return V;
825
826  return 0;
827}
828
829/// SimplifySDivInst - Given operands for an SDiv, see if we can
830/// fold the result.  If not, this returns null.
831static Value *SimplifySDivInst(Value *Op0, Value *Op1, const TargetData *TD,
832                               const DominatorTree *DT, unsigned MaxRecurse) {
833  if (Value *V = SimplifyDiv(Instruction::SDiv, Op0, Op1, TD, DT, MaxRecurse))
834    return V;
835
836  return 0;
837}
838
839Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const TargetData *TD,
840                             const DominatorTree *DT) {
841  return ::SimplifySDivInst(Op0, Op1, TD, DT, RecursionLimit);
842}
843
844/// SimplifyUDivInst - Given operands for a UDiv, see if we can
845/// fold the result.  If not, this returns null.
846static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const TargetData *TD,
847                               const DominatorTree *DT, unsigned MaxRecurse) {
848  if (Value *V = SimplifyDiv(Instruction::UDiv, Op0, Op1, TD, DT, MaxRecurse))
849    return V;
850
851  return 0;
852}
853
854Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const TargetData *TD,
855                             const DominatorTree *DT) {
856  return ::SimplifyUDivInst(Op0, Op1, TD, DT, RecursionLimit);
857}
858
859/// SimplifyShift - Given operands for an Shl, LShr or AShr, see if we can
860/// fold the result.  If not, this returns null.
861static Value *SimplifyShift(unsigned Opcode, Value *Op0, Value *Op1,
862                            const TargetData *TD, const DominatorTree *DT,
863                            unsigned MaxRecurse) {
864  if (Constant *C0 = dyn_cast<Constant>(Op0)) {
865    if (Constant *C1 = dyn_cast<Constant>(Op1)) {
866      Constant *Ops[] = { C0, C1 };
867      return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, 2, TD);
868    }
869  }
870
871  // 0 shift by X -> 0
872  if (match(Op0, m_Zero()))
873    return Op0;
874
875  // X shift by 0 -> X
876  if (match(Op1, m_Zero()))
877    return Op0;
878
879  // X shift by undef -> undef because it may shift by the bitwidth.
880  if (isa<UndefValue>(Op1))
881    return Op1;
882
883  // Shifting by the bitwidth or more is undefined.
884  if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1))
885    if (CI->getValue().getLimitedValue() >=
886        Op0->getType()->getScalarSizeInBits())
887      return UndefValue::get(Op0->getType());
888
889  // If the operation is with the result of a select instruction, check whether
890  // operating on either branch of the select always yields the same value.
891  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
892    if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, TD, DT, MaxRecurse))
893      return V;
894
895  // If the operation is with the result of a phi instruction, check whether
896  // operating on all incoming values of the phi always yields the same value.
897  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
898    if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, TD, DT, MaxRecurse))
899      return V;
900
901  return 0;
902}
903
904/// SimplifyShlInst - Given operands for an Shl, see if we can
905/// fold the result.  If not, this returns null.
906static Value *SimplifyShlInst(Value *Op0, Value *Op1, const TargetData *TD,
907                              const DominatorTree *DT, unsigned MaxRecurse) {
908  if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, TD, DT, MaxRecurse))
909    return V;
910
911  // undef << X -> 0
912  if (isa<UndefValue>(Op0))
913    return Constant::getNullValue(Op0->getType());
914
915  return 0;
916}
917
918Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, const TargetData *TD,
919                             const DominatorTree *DT) {
920  return ::SimplifyShlInst(Op0, Op1, TD, DT, RecursionLimit);
921}
922
923/// SimplifyLShrInst - Given operands for an LShr, see if we can
924/// fold the result.  If not, this returns null.
925static Value *SimplifyLShrInst(Value *Op0, Value *Op1, const TargetData *TD,
926                               const DominatorTree *DT, unsigned MaxRecurse) {
927  if (Value *V = SimplifyShift(Instruction::LShr, Op0, Op1, TD, DT, MaxRecurse))
928    return V;
929
930  // undef >>l X -> 0
931  if (isa<UndefValue>(Op0))
932    return Constant::getNullValue(Op0->getType());
933
934  return 0;
935}
936
937Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, const TargetData *TD,
938                              const DominatorTree *DT) {
939  return ::SimplifyLShrInst(Op0, Op1, TD, DT, RecursionLimit);
940}
941
942/// SimplifyAShrInst - Given operands for an AShr, see if we can
943/// fold the result.  If not, this returns null.
944static Value *SimplifyAShrInst(Value *Op0, Value *Op1, const TargetData *TD,
945                              const DominatorTree *DT, unsigned MaxRecurse) {
946  if (Value *V = SimplifyShift(Instruction::AShr, Op0, Op1, TD, DT, MaxRecurse))
947    return V;
948
949  // all ones >>a X -> all ones
950  if (match(Op0, m_AllOnes()))
951    return Op0;
952
953  // undef >>a X -> all ones
954  if (isa<UndefValue>(Op0))
955    return Constant::getAllOnesValue(Op0->getType());
956
957  return 0;
958}
959
960Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, const TargetData *TD,
961                              const DominatorTree *DT) {
962  return ::SimplifyAShrInst(Op0, Op1, TD, DT, RecursionLimit);
963}
964
965/// SimplifyAndInst - Given operands for an And, see if we can
966/// fold the result.  If not, this returns null.
967static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
968                              const DominatorTree *DT, unsigned MaxRecurse) {
969  if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
970    if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
971      Constant *Ops[] = { CLHS, CRHS };
972      return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
973                                      Ops, 2, TD);
974    }
975
976    // Canonicalize the constant to the RHS.
977    std::swap(Op0, Op1);
978  }
979
980  // X & undef -> 0
981  if (isa<UndefValue>(Op1))
982    return Constant::getNullValue(Op0->getType());
983
984  // X & X = X
985  if (Op0 == Op1)
986    return Op0;
987
988  // X & 0 = 0
989  if (match(Op1, m_Zero()))
990    return Op1;
991
992  // X & -1 = X
993  if (match(Op1, m_AllOnes()))
994    return Op0;
995
996  // A & ~A  =  ~A & A  =  0
997  Value *A = 0, *B = 0;
998  if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
999      (match(Op1, m_Not(m_Value(A))) && A == Op0))
1000    return Constant::getNullValue(Op0->getType());
1001
1002  // (A | ?) & A = A
1003  if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
1004      (A == Op1 || B == Op1))
1005    return Op1;
1006
1007  // A & (A | ?) = A
1008  if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
1009      (A == Op0 || B == Op0))
1010    return Op0;
1011
1012  // Try some generic simplifications for associative operations.
1013  if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, TD, DT,
1014                                          MaxRecurse))
1015    return V;
1016
1017  // And distributes over Or.  Try some generic simplifications based on this.
1018  if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or,
1019                             TD, DT, MaxRecurse))
1020    return V;
1021
1022  // And distributes over Xor.  Try some generic simplifications based on this.
1023  if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor,
1024                             TD, DT, MaxRecurse))
1025    return V;
1026
1027  // Or distributes over And.  Try some generic simplifications based on this.
1028  if (Value *V = FactorizeBinOp(Instruction::And, Op0, Op1, Instruction::Or,
1029                                TD, DT, MaxRecurse))
1030    return V;
1031
1032  // If the operation is with the result of a select instruction, check whether
1033  // operating on either branch of the select always yields the same value.
1034  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1035    if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, DT,
1036                                         MaxRecurse))
1037      return V;
1038
1039  // If the operation is with the result of a phi instruction, check whether
1040  // operating on all incoming values of the phi always yields the same value.
1041  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1042    if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, DT,
1043                                      MaxRecurse))
1044      return V;
1045
1046  return 0;
1047}
1048
1049Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
1050                             const DominatorTree *DT) {
1051  return ::SimplifyAndInst(Op0, Op1, TD, DT, RecursionLimit);
1052}
1053
1054/// SimplifyOrInst - Given operands for an Or, see if we can
1055/// fold the result.  If not, this returns null.
1056static Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
1057                             const DominatorTree *DT, unsigned MaxRecurse) {
1058  if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
1059    if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
1060      Constant *Ops[] = { CLHS, CRHS };
1061      return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
1062                                      Ops, 2, TD);
1063    }
1064
1065    // Canonicalize the constant to the RHS.
1066    std::swap(Op0, Op1);
1067  }
1068
1069  // X | undef -> -1
1070  if (isa<UndefValue>(Op1))
1071    return Constant::getAllOnesValue(Op0->getType());
1072
1073  // X | X = X
1074  if (Op0 == Op1)
1075    return Op0;
1076
1077  // X | 0 = X
1078  if (match(Op1, m_Zero()))
1079    return Op0;
1080
1081  // X | -1 = -1
1082  if (match(Op1, m_AllOnes()))
1083    return Op1;
1084
1085  // A | ~A  =  ~A | A  =  -1
1086  Value *A = 0, *B = 0;
1087  if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
1088      (match(Op1, m_Not(m_Value(A))) && A == Op0))
1089    return Constant::getAllOnesValue(Op0->getType());
1090
1091  // (A & ?) | A = A
1092  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
1093      (A == Op1 || B == Op1))
1094    return Op1;
1095
1096  // A | (A & ?) = A
1097  if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
1098      (A == Op0 || B == Op0))
1099    return Op0;
1100
1101  // Try some generic simplifications for associative operations.
1102  if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, TD, DT,
1103                                          MaxRecurse))
1104    return V;
1105
1106  // Or distributes over And.  Try some generic simplifications based on this.
1107  if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And,
1108                             TD, DT, MaxRecurse))
1109    return V;
1110
1111  // And distributes over Or.  Try some generic simplifications based on this.
1112  if (Value *V = FactorizeBinOp(Instruction::Or, Op0, Op1, Instruction::And,
1113                                TD, DT, MaxRecurse))
1114    return V;
1115
1116  // If the operation is with the result of a select instruction, check whether
1117  // operating on either branch of the select always yields the same value.
1118  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1119    if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT,
1120                                         MaxRecurse))
1121      return V;
1122
1123  // If the operation is with the result of a phi instruction, check whether
1124  // operating on all incoming values of the phi always yields the same value.
1125  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1126    if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT,
1127                                      MaxRecurse))
1128      return V;
1129
1130  return 0;
1131}
1132
1133Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
1134                            const DominatorTree *DT) {
1135  return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit);
1136}
1137
1138/// SimplifyXorInst - Given operands for a Xor, see if we can
1139/// fold the result.  If not, this returns null.
1140static Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
1141                              const DominatorTree *DT, unsigned MaxRecurse) {
1142  if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
1143    if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
1144      Constant *Ops[] = { CLHS, CRHS };
1145      return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(),
1146                                      Ops, 2, TD);
1147    }
1148
1149    // Canonicalize the constant to the RHS.
1150    std::swap(Op0, Op1);
1151  }
1152
1153  // A ^ undef -> undef
1154  if (isa<UndefValue>(Op1))
1155    return Op1;
1156
1157  // A ^ 0 = A
1158  if (match(Op1, m_Zero()))
1159    return Op0;
1160
1161  // A ^ A = 0
1162  if (Op0 == Op1)
1163    return Constant::getNullValue(Op0->getType());
1164
1165  // A ^ ~A  =  ~A ^ A  =  -1
1166  Value *A = 0;
1167  if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
1168      (match(Op1, m_Not(m_Value(A))) && A == Op0))
1169    return Constant::getAllOnesValue(Op0->getType());
1170
1171  // Try some generic simplifications for associative operations.
1172  if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, TD, DT,
1173                                          MaxRecurse))
1174    return V;
1175
1176  // And distributes over Xor.  Try some generic simplifications based on this.
1177  if (Value *V = FactorizeBinOp(Instruction::Xor, Op0, Op1, Instruction::And,
1178                                TD, DT, MaxRecurse))
1179    return V;
1180
1181  // Threading Xor over selects and phi nodes is pointless, so don't bother.
1182  // Threading over the select in "A ^ select(cond, B, C)" means evaluating
1183  // "A^B" and "A^C" and seeing if they are equal; but they are equal if and
1184  // only if B and C are equal.  If B and C are equal then (since we assume
1185  // that operands have already been simplified) "select(cond, B, C)" should
1186  // have been simplified to the common value of B and C already.  Analysing
1187  // "A^B" and "A^C" thus gains nothing, but costs compile time.  Similarly
1188  // for threading over phi nodes.
1189
1190  return 0;
1191}
1192
1193Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
1194                             const DominatorTree *DT) {
1195  return ::SimplifyXorInst(Op0, Op1, TD, DT, RecursionLimit);
1196}
1197
1198static const Type *GetCompareTy(Value *Op) {
1199  return CmpInst::makeCmpResultType(Op->getType());
1200}
1201
1202/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
1203/// fold the result.  If not, this returns null.
1204static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1205                               const TargetData *TD, const DominatorTree *DT,
1206                               unsigned MaxRecurse) {
1207  CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
1208  assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
1209
1210  if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
1211    if (Constant *CRHS = dyn_cast<Constant>(RHS))
1212      return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
1213
1214    // If we have a constant, make sure it is on the RHS.
1215    std::swap(LHS, RHS);
1216    Pred = CmpInst::getSwappedPredicate(Pred);
1217  }
1218
1219  const Type *ITy = GetCompareTy(LHS); // The return type.
1220  const Type *OpTy = LHS->getType();   // The operand type.
1221
1222  // icmp X, X -> true/false
1223  // X icmp undef -> true/false.  For example, icmp ugt %X, undef -> false
1224  // because X could be 0.
1225  if (LHS == RHS || isa<UndefValue>(RHS))
1226    return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
1227
1228  // Special case logic when the operands have i1 type.
1229  if (OpTy->isIntegerTy(1) || (OpTy->isVectorTy() &&
1230       cast<VectorType>(OpTy)->getElementType()->isIntegerTy(1))) {
1231    switch (Pred) {
1232    default: break;
1233    case ICmpInst::ICMP_EQ:
1234      // X == 1 -> X
1235      if (match(RHS, m_One()))
1236        return LHS;
1237      break;
1238    case ICmpInst::ICMP_NE:
1239      // X != 0 -> X
1240      if (match(RHS, m_Zero()))
1241        return LHS;
1242      break;
1243    case ICmpInst::ICMP_UGT:
1244      // X >u 0 -> X
1245      if (match(RHS, m_Zero()))
1246        return LHS;
1247      break;
1248    case ICmpInst::ICMP_UGE:
1249      // X >=u 1 -> X
1250      if (match(RHS, m_One()))
1251        return LHS;
1252      break;
1253    case ICmpInst::ICMP_SLT:
1254      // X <s 0 -> X
1255      if (match(RHS, m_Zero()))
1256        return LHS;
1257      break;
1258    case ICmpInst::ICMP_SLE:
1259      // X <=s -1 -> X
1260      if (match(RHS, m_One()))
1261        return LHS;
1262      break;
1263    }
1264  }
1265
1266  // icmp <alloca*>, <global/alloca*/null> - Different stack variables have
1267  // different addresses, and what's more the address of a stack variable is
1268  // never null or equal to the address of a global.  Note that generalizing
1269  // to the case where LHS is a global variable address or null is pointless,
1270  // since if both LHS and RHS are constants then we already constant folded
1271  // the compare, and if only one of them is then we moved it to RHS already.
1272  if (isa<AllocaInst>(LHS) && (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) ||
1273                               isa<ConstantPointerNull>(RHS)))
1274    // We already know that LHS != LHS.
1275    return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
1276
1277  // If we are comparing with zero then try hard since this is a common case.
1278  if (match(RHS, m_Zero())) {
1279    bool LHSKnownNonNegative, LHSKnownNegative;
1280    switch (Pred) {
1281    default:
1282      assert(false && "Unknown ICmp predicate!");
1283    case ICmpInst::ICMP_ULT:
1284      return ConstantInt::getFalse(LHS->getContext());
1285    case ICmpInst::ICMP_UGE:
1286      return ConstantInt::getTrue(LHS->getContext());
1287    case ICmpInst::ICMP_EQ:
1288    case ICmpInst::ICMP_ULE:
1289      if (isKnownNonZero(LHS, TD))
1290        return ConstantInt::getFalse(LHS->getContext());
1291      break;
1292    case ICmpInst::ICMP_NE:
1293    case ICmpInst::ICMP_UGT:
1294      if (isKnownNonZero(LHS, TD))
1295        return ConstantInt::getTrue(LHS->getContext());
1296      break;
1297    case ICmpInst::ICMP_SLT:
1298      ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD);
1299      if (LHSKnownNegative)
1300        return ConstantInt::getTrue(LHS->getContext());
1301      if (LHSKnownNonNegative)
1302        return ConstantInt::getFalse(LHS->getContext());
1303      break;
1304    case ICmpInst::ICMP_SLE:
1305      ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD);
1306      if (LHSKnownNegative)
1307        return ConstantInt::getTrue(LHS->getContext());
1308      if (LHSKnownNonNegative && isKnownNonZero(LHS, TD))
1309        return ConstantInt::getFalse(LHS->getContext());
1310      break;
1311    case ICmpInst::ICMP_SGE:
1312      ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD);
1313      if (LHSKnownNegative)
1314        return ConstantInt::getFalse(LHS->getContext());
1315      if (LHSKnownNonNegative)
1316        return ConstantInt::getTrue(LHS->getContext());
1317      break;
1318    case ICmpInst::ICMP_SGT:
1319      ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD);
1320      if (LHSKnownNegative)
1321        return ConstantInt::getFalse(LHS->getContext());
1322      if (LHSKnownNonNegative && isKnownNonZero(LHS, TD))
1323        return ConstantInt::getTrue(LHS->getContext());
1324      break;
1325    }
1326  }
1327
1328  // See if we are doing a comparison with a constant integer.
1329  if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
1330    switch (Pred) {
1331    default: break;
1332    case ICmpInst::ICMP_UGT:
1333      if (CI->isMaxValue(false))                 // A >u MAX -> FALSE
1334        return ConstantInt::getFalse(CI->getContext());
1335      break;
1336    case ICmpInst::ICMP_UGE:
1337      if (CI->isMinValue(false))                 // A >=u MIN -> TRUE
1338        return ConstantInt::getTrue(CI->getContext());
1339      break;
1340    case ICmpInst::ICMP_ULT:
1341      if (CI->isMinValue(false))                 // A <u MIN -> FALSE
1342        return ConstantInt::getFalse(CI->getContext());
1343      break;
1344    case ICmpInst::ICMP_ULE:
1345      if (CI->isMaxValue(false))                 // A <=u MAX -> TRUE
1346        return ConstantInt::getTrue(CI->getContext());
1347      break;
1348    case ICmpInst::ICMP_SGT:
1349      if (CI->isMaxValue(true))                  // A >s MAX -> FALSE
1350        return ConstantInt::getFalse(CI->getContext());
1351      break;
1352    case ICmpInst::ICMP_SGE:
1353      if (CI->isMinValue(true))                  // A >=s MIN -> TRUE
1354        return ConstantInt::getTrue(CI->getContext());
1355      break;
1356    case ICmpInst::ICMP_SLT:
1357      if (CI->isMinValue(true))                  // A <s MIN -> FALSE
1358        return ConstantInt::getFalse(CI->getContext());
1359      break;
1360    case ICmpInst::ICMP_SLE:
1361      if (CI->isMaxValue(true))                  // A <=s MAX -> TRUE
1362        return ConstantInt::getTrue(CI->getContext());
1363      break;
1364    }
1365  }
1366
1367  // Compare of cast, for example (zext X) != 0 -> X != 0
1368  if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) {
1369    Instruction *LI = cast<CastInst>(LHS);
1370    Value *SrcOp = LI->getOperand(0);
1371    const Type *SrcTy = SrcOp->getType();
1372    const Type *DstTy = LI->getType();
1373
1374    // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input
1375    // if the integer type is the same size as the pointer type.
1376    if (MaxRecurse && TD && isa<PtrToIntInst>(LI) &&
1377        TD->getPointerSizeInBits() == DstTy->getPrimitiveSizeInBits()) {
1378      if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
1379        // Transfer the cast to the constant.
1380        if (Value *V = SimplifyICmpInst(Pred, SrcOp,
1381                                        ConstantExpr::getIntToPtr(RHSC, SrcTy),
1382                                        TD, DT, MaxRecurse-1))
1383          return V;
1384      } else if (PtrToIntInst *RI = dyn_cast<PtrToIntInst>(RHS)) {
1385        if (RI->getOperand(0)->getType() == SrcTy)
1386          // Compare without the cast.
1387          if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0),
1388                                          TD, DT, MaxRecurse-1))
1389            return V;
1390      }
1391    }
1392
1393    if (isa<ZExtInst>(LHS)) {
1394      // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the
1395      // same type.
1396      if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) {
1397        if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
1398          // Compare X and Y.  Note that signed predicates become unsigned.
1399          if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred),
1400                                          SrcOp, RI->getOperand(0), TD, DT,
1401                                          MaxRecurse-1))
1402            return V;
1403      }
1404      // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended
1405      // too.  If not, then try to deduce the result of the comparison.
1406      else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
1407        // Compute the constant that would happen if we truncated to SrcTy then
1408        // reextended to DstTy.
1409        Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
1410        Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy);
1411
1412        // If the re-extended constant didn't change then this is effectively
1413        // also a case of comparing two zero-extended values.
1414        if (RExt == CI && MaxRecurse)
1415          if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred),
1416                                          SrcOp, Trunc, TD, DT, MaxRecurse-1))
1417            return V;
1418
1419        // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit
1420        // there.  Use this to work out the result of the comparison.
1421        if (RExt != CI) {
1422          switch (Pred) {
1423          default:
1424            assert(false && "Unknown ICmp predicate!");
1425          // LHS <u RHS.
1426          case ICmpInst::ICMP_EQ:
1427          case ICmpInst::ICMP_UGT:
1428          case ICmpInst::ICMP_UGE:
1429            return ConstantInt::getFalse(CI->getContext());
1430
1431          case ICmpInst::ICMP_NE:
1432          case ICmpInst::ICMP_ULT:
1433          case ICmpInst::ICMP_ULE:
1434            return ConstantInt::getTrue(CI->getContext());
1435
1436          // LHS is non-negative.  If RHS is negative then LHS >s LHS.  If RHS
1437          // is non-negative then LHS <s RHS.
1438          case ICmpInst::ICMP_SGT:
1439          case ICmpInst::ICMP_SGE:
1440            return CI->getValue().isNegative() ?
1441              ConstantInt::getTrue(CI->getContext()) :
1442              ConstantInt::getFalse(CI->getContext());
1443
1444          case ICmpInst::ICMP_SLT:
1445          case ICmpInst::ICMP_SLE:
1446            return CI->getValue().isNegative() ?
1447              ConstantInt::getFalse(CI->getContext()) :
1448              ConstantInt::getTrue(CI->getContext());
1449          }
1450        }
1451      }
1452    }
1453
1454    if (isa<SExtInst>(LHS)) {
1455      // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the
1456      // same type.
1457      if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) {
1458        if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
1459          // Compare X and Y.  Note that the predicate does not change.
1460          if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0),
1461                                          TD, DT, MaxRecurse-1))
1462            return V;
1463      }
1464      // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended
1465      // too.  If not, then try to deduce the result of the comparison.
1466      else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
1467        // Compute the constant that would happen if we truncated to SrcTy then
1468        // reextended to DstTy.
1469        Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
1470        Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy);
1471
1472        // If the re-extended constant didn't change then this is effectively
1473        // also a case of comparing two sign-extended values.
1474        if (RExt == CI && MaxRecurse)
1475          if (Value *V = SimplifyICmpInst(Pred, SrcOp, Trunc, TD, DT,
1476                                          MaxRecurse-1))
1477            return V;
1478
1479        // Otherwise the upper bits of LHS are all equal, while RHS has varying
1480        // bits there.  Use this to work out the result of the comparison.
1481        if (RExt != CI) {
1482          switch (Pred) {
1483          default:
1484            assert(false && "Unknown ICmp predicate!");
1485          case ICmpInst::ICMP_EQ:
1486            return ConstantInt::getFalse(CI->getContext());
1487          case ICmpInst::ICMP_NE:
1488            return ConstantInt::getTrue(CI->getContext());
1489
1490          // If RHS is non-negative then LHS <s RHS.  If RHS is negative then
1491          // LHS >s RHS.
1492          case ICmpInst::ICMP_SGT:
1493          case ICmpInst::ICMP_SGE:
1494            return CI->getValue().isNegative() ?
1495              ConstantInt::getTrue(CI->getContext()) :
1496              ConstantInt::getFalse(CI->getContext());
1497          case ICmpInst::ICMP_SLT:
1498          case ICmpInst::ICMP_SLE:
1499            return CI->getValue().isNegative() ?
1500              ConstantInt::getFalse(CI->getContext()) :
1501              ConstantInt::getTrue(CI->getContext());
1502
1503          // If LHS is non-negative then LHS <u RHS.  If LHS is negative then
1504          // LHS >u RHS.
1505          case ICmpInst::ICMP_UGT:
1506          case ICmpInst::ICMP_UGE:
1507            // Comparison is true iff the LHS <s 0.
1508            if (MaxRecurse)
1509              if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SLT, SrcOp,
1510                                              Constant::getNullValue(SrcTy),
1511                                              TD, DT, MaxRecurse-1))
1512                return V;
1513            break;
1514          case ICmpInst::ICMP_ULT:
1515          case ICmpInst::ICMP_ULE:
1516            // Comparison is true iff the LHS >=s 0.
1517            if (MaxRecurse)
1518              if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SGE, SrcOp,
1519                                              Constant::getNullValue(SrcTy),
1520                                              TD, DT, MaxRecurse-1))
1521                return V;
1522            break;
1523          }
1524        }
1525      }
1526    }
1527  }
1528
1529  // If the comparison is with the result of a select instruction, check whether
1530  // comparing with either branch of the select always yields the same value.
1531  if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
1532    if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse))
1533      return V;
1534
1535  // If the comparison is with the result of a phi instruction, check whether
1536  // doing the compare with each incoming phi value yields a common result.
1537  if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
1538    if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse))
1539      return V;
1540
1541  return 0;
1542}
1543
1544Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1545                              const TargetData *TD, const DominatorTree *DT) {
1546  return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
1547}
1548
1549/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
1550/// fold the result.  If not, this returns null.
1551static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1552                               const TargetData *TD, const DominatorTree *DT,
1553                               unsigned MaxRecurse) {
1554  CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
1555  assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
1556
1557  if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
1558    if (Constant *CRHS = dyn_cast<Constant>(RHS))
1559      return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
1560
1561    // If we have a constant, make sure it is on the RHS.
1562    std::swap(LHS, RHS);
1563    Pred = CmpInst::getSwappedPredicate(Pred);
1564  }
1565
1566  // Fold trivial predicates.
1567  if (Pred == FCmpInst::FCMP_FALSE)
1568    return ConstantInt::get(GetCompareTy(LHS), 0);
1569  if (Pred == FCmpInst::FCMP_TRUE)
1570    return ConstantInt::get(GetCompareTy(LHS), 1);
1571
1572  if (isa<UndefValue>(RHS))                  // fcmp pred X, undef -> undef
1573    return UndefValue::get(GetCompareTy(LHS));
1574
1575  // fcmp x,x -> true/false.  Not all compares are foldable.
1576  if (LHS == RHS) {
1577    if (CmpInst::isTrueWhenEqual(Pred))
1578      return ConstantInt::get(GetCompareTy(LHS), 1);
1579    if (CmpInst::isFalseWhenEqual(Pred))
1580      return ConstantInt::get(GetCompareTy(LHS), 0);
1581  }
1582
1583  // Handle fcmp with constant RHS
1584  if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
1585    // If the constant is a nan, see if we can fold the comparison based on it.
1586    if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
1587      if (CFP->getValueAPF().isNaN()) {
1588        if (FCmpInst::isOrdered(Pred))   // True "if ordered and foo"
1589          return ConstantInt::getFalse(CFP->getContext());
1590        assert(FCmpInst::isUnordered(Pred) &&
1591               "Comparison must be either ordered or unordered!");
1592        // True if unordered.
1593        return ConstantInt::getTrue(CFP->getContext());
1594      }
1595      // Check whether the constant is an infinity.
1596      if (CFP->getValueAPF().isInfinity()) {
1597        if (CFP->getValueAPF().isNegative()) {
1598          switch (Pred) {
1599          case FCmpInst::FCMP_OLT:
1600            // No value is ordered and less than negative infinity.
1601            return ConstantInt::getFalse(CFP->getContext());
1602          case FCmpInst::FCMP_UGE:
1603            // All values are unordered with or at least negative infinity.
1604            return ConstantInt::getTrue(CFP->getContext());
1605          default:
1606            break;
1607          }
1608        } else {
1609          switch (Pred) {
1610          case FCmpInst::FCMP_OGT:
1611            // No value is ordered and greater than infinity.
1612            return ConstantInt::getFalse(CFP->getContext());
1613          case FCmpInst::FCMP_ULE:
1614            // All values are unordered with and at most infinity.
1615            return ConstantInt::getTrue(CFP->getContext());
1616          default:
1617            break;
1618          }
1619        }
1620      }
1621    }
1622  }
1623
1624  // If the comparison is with the result of a select instruction, check whether
1625  // comparing with either branch of the select always yields the same value.
1626  if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
1627    if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse))
1628      return V;
1629
1630  // If the comparison is with the result of a phi instruction, check whether
1631  // doing the compare with each incoming phi value yields a common result.
1632  if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
1633    if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse))
1634      return V;
1635
1636  return 0;
1637}
1638
1639Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1640                              const TargetData *TD, const DominatorTree *DT) {
1641  return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
1642}
1643
1644/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
1645/// the result.  If not, this returns null.
1646Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal,
1647                                const TargetData *TD, const DominatorTree *) {
1648  // select true, X, Y  -> X
1649  // select false, X, Y -> Y
1650  if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal))
1651    return CB->getZExtValue() ? TrueVal : FalseVal;
1652
1653  // select C, X, X -> X
1654  if (TrueVal == FalseVal)
1655    return TrueVal;
1656
1657  if (isa<UndefValue>(TrueVal))   // select C, undef, X -> X
1658    return FalseVal;
1659  if (isa<UndefValue>(FalseVal))   // select C, X, undef -> X
1660    return TrueVal;
1661  if (isa<UndefValue>(CondVal)) {  // select undef, X, Y -> X or Y
1662    if (isa<Constant>(TrueVal))
1663      return TrueVal;
1664    return FalseVal;
1665  }
1666
1667  return 0;
1668}
1669
1670/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
1671/// fold the result.  If not, this returns null.
1672Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps,
1673                             const TargetData *TD, const DominatorTree *) {
1674  // The type of the GEP pointer operand.
1675  const PointerType *PtrTy = cast<PointerType>(Ops[0]->getType());
1676
1677  // getelementptr P -> P.
1678  if (NumOps == 1)
1679    return Ops[0];
1680
1681  if (isa<UndefValue>(Ops[0])) {
1682    // Compute the (pointer) type returned by the GEP instruction.
1683    const Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, &Ops[1],
1684                                                             NumOps-1);
1685    const Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace());
1686    return UndefValue::get(GEPTy);
1687  }
1688
1689  if (NumOps == 2) {
1690    // getelementptr P, 0 -> P.
1691    if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
1692      if (C->isZero())
1693        return Ops[0];
1694    // getelementptr P, N -> P if P points to a type of zero size.
1695    if (TD) {
1696      const Type *Ty = PtrTy->getElementType();
1697      if (Ty->isSized() && TD->getTypeAllocSize(Ty) == 0)
1698        return Ops[0];
1699    }
1700  }
1701
1702  // Check to see if this is constant foldable.
1703  for (unsigned i = 0; i != NumOps; ++i)
1704    if (!isa<Constant>(Ops[i]))
1705      return 0;
1706
1707  return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]),
1708                                        (Constant *const*)Ops+1, NumOps-1);
1709}
1710
1711/// SimplifyPHINode - See if we can fold the given phi.  If not, returns null.
1712static Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) {
1713  // If all of the PHI's incoming values are the same then replace the PHI node
1714  // with the common value.
1715  Value *CommonValue = 0;
1716  bool HasUndefInput = false;
1717  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1718    Value *Incoming = PN->getIncomingValue(i);
1719    // If the incoming value is the phi node itself, it can safely be skipped.
1720    if (Incoming == PN) continue;
1721    if (isa<UndefValue>(Incoming)) {
1722      // Remember that we saw an undef value, but otherwise ignore them.
1723      HasUndefInput = true;
1724      continue;
1725    }
1726    if (CommonValue && Incoming != CommonValue)
1727      return 0;  // Not the same, bail out.
1728    CommonValue = Incoming;
1729  }
1730
1731  // If CommonValue is null then all of the incoming values were either undef or
1732  // equal to the phi node itself.
1733  if (!CommonValue)
1734    return UndefValue::get(PN->getType());
1735
1736  // If we have a PHI node like phi(X, undef, X), where X is defined by some
1737  // instruction, we cannot return X as the result of the PHI node unless it
1738  // dominates the PHI block.
1739  if (HasUndefInput)
1740    return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0;
1741
1742  return CommonValue;
1743}
1744
1745
1746//=== Helper functions for higher up the class hierarchy.
1747
1748/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
1749/// fold the result.  If not, this returns null.
1750static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
1751                            const TargetData *TD, const DominatorTree *DT,
1752                            unsigned MaxRecurse) {
1753  switch (Opcode) {
1754  case Instruction::Add: return SimplifyAddInst(LHS, RHS, /* isNSW */ false,
1755                                                /* isNUW */ false, TD, DT,
1756                                                MaxRecurse);
1757  case Instruction::Sub: return SimplifySubInst(LHS, RHS, /* isNSW */ false,
1758                                                /* isNUW */ false, TD, DT,
1759                                                MaxRecurse);
1760  case Instruction::Mul: return SimplifyMulInst(LHS, RHS, TD, DT, MaxRecurse);
1761  case Instruction::SDiv: return SimplifySDivInst(LHS, RHS, TD, DT, MaxRecurse);
1762  case Instruction::UDiv: return SimplifyUDivInst(LHS, RHS, TD, DT, MaxRecurse);
1763  case Instruction::Shl: return SimplifyShlInst(LHS, RHS, TD, DT, MaxRecurse);
1764  case Instruction::LShr: return SimplifyLShrInst(LHS, RHS, TD, DT, MaxRecurse);
1765  case Instruction::AShr: return SimplifyAShrInst(LHS, RHS, TD, DT, MaxRecurse);
1766  case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse);
1767  case Instruction::Or:  return SimplifyOrInst(LHS, RHS, TD, DT, MaxRecurse);
1768  case Instruction::Xor: return SimplifyXorInst(LHS, RHS, TD, DT, MaxRecurse);
1769  default:
1770    if (Constant *CLHS = dyn_cast<Constant>(LHS))
1771      if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
1772        Constant *COps[] = {CLHS, CRHS};
1773        return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD);
1774      }
1775
1776    // If the operation is associative, try some generic simplifications.
1777    if (Instruction::isAssociative(Opcode))
1778      if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, TD, DT,
1779                                              MaxRecurse))
1780        return V;
1781
1782    // If the operation is with the result of a select instruction, check whether
1783    // operating on either branch of the select always yields the same value.
1784    if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
1785      if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT,
1786                                           MaxRecurse))
1787        return V;
1788
1789    // If the operation is with the result of a phi instruction, check whether
1790    // operating on all incoming values of the phi always yields the same value.
1791    if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
1792      if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse))
1793        return V;
1794
1795    return 0;
1796  }
1797}
1798
1799Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
1800                           const TargetData *TD, const DominatorTree *DT) {
1801  return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit);
1802}
1803
1804/// SimplifyCmpInst - Given operands for a CmpInst, see if we can
1805/// fold the result.
1806static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1807                              const TargetData *TD, const DominatorTree *DT,
1808                              unsigned MaxRecurse) {
1809  if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
1810    return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
1811  return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
1812}
1813
1814Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1815                             const TargetData *TD, const DominatorTree *DT) {
1816  return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
1817}
1818
1819/// SimplifyInstruction - See if we can compute a simplified version of this
1820/// instruction.  If not, this returns null.
1821Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD,
1822                                 const DominatorTree *DT) {
1823  Value *Result;
1824
1825  switch (I->getOpcode()) {
1826  default:
1827    Result = ConstantFoldInstruction(I, TD);
1828    break;
1829  case Instruction::Add:
1830    Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1),
1831                             cast<BinaryOperator>(I)->hasNoSignedWrap(),
1832                             cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
1833                             TD, DT);
1834    break;
1835  case Instruction::Sub:
1836    Result = SimplifySubInst(I->getOperand(0), I->getOperand(1),
1837                             cast<BinaryOperator>(I)->hasNoSignedWrap(),
1838                             cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
1839                             TD, DT);
1840    break;
1841  case Instruction::Mul:
1842    Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), TD, DT);
1843    break;
1844  case Instruction::SDiv:
1845    Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), TD, DT);
1846    break;
1847  case Instruction::UDiv:
1848    Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), TD, DT);
1849    break;
1850  case Instruction::Shl:
1851    Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1), TD, DT);
1852    break;
1853  case Instruction::LShr:
1854    Result = SimplifyLShrInst(I->getOperand(0), I->getOperand(1), TD, DT);
1855    break;
1856  case Instruction::AShr:
1857    Result = SimplifyAShrInst(I->getOperand(0), I->getOperand(1), TD, DT);
1858    break;
1859  case Instruction::And:
1860    Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT);
1861    break;
1862  case Instruction::Or:
1863    Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT);
1864    break;
1865  case Instruction::Xor:
1866    Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT);
1867    break;
1868  case Instruction::ICmp:
1869    Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
1870                              I->getOperand(0), I->getOperand(1), TD, DT);
1871    break;
1872  case Instruction::FCmp:
1873    Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
1874                              I->getOperand(0), I->getOperand(1), TD, DT);
1875    break;
1876  case Instruction::Select:
1877    Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1),
1878                                I->getOperand(2), TD, DT);
1879    break;
1880  case Instruction::GetElementPtr: {
1881    SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
1882    Result = SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT);
1883    break;
1884  }
1885  case Instruction::PHI:
1886    Result = SimplifyPHINode(cast<PHINode>(I), DT);
1887    break;
1888  }
1889
1890  /// If called on unreachable code, the above logic may report that the
1891  /// instruction simplified to itself.  Make life easier for users by
1892  /// detecting that case here, returning a safe value instead.
1893  return Result == I ? UndefValue::get(I->getType()) : Result;
1894}
1895
1896/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
1897/// delete the From instruction.  In addition to a basic RAUW, this does a
1898/// recursive simplification of the newly formed instructions.  This catches
1899/// things where one simplification exposes other opportunities.  This only
1900/// simplifies and deletes scalar operations, it does not change the CFG.
1901///
1902void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
1903                                     const TargetData *TD,
1904                                     const DominatorTree *DT) {
1905  assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!");
1906
1907  // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that
1908  // we can know if it gets deleted out from under us or replaced in a
1909  // recursive simplification.
1910  WeakVH FromHandle(From);
1911  WeakVH ToHandle(To);
1912
1913  while (!From->use_empty()) {
1914    // Update the instruction to use the new value.
1915    Use &TheUse = From->use_begin().getUse();
1916    Instruction *User = cast<Instruction>(TheUse.getUser());
1917    TheUse = To;
1918
1919    // Check to see if the instruction can be folded due to the operand
1920    // replacement.  For example changing (or X, Y) into (or X, -1) can replace
1921    // the 'or' with -1.
1922    Value *SimplifiedVal;
1923    {
1924      // Sanity check to make sure 'User' doesn't dangle across
1925      // SimplifyInstruction.
1926      AssertingVH<> UserHandle(User);
1927
1928      SimplifiedVal = SimplifyInstruction(User, TD, DT);
1929      if (SimplifiedVal == 0) continue;
1930    }
1931
1932    // Recursively simplify this user to the new value.
1933    ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT);
1934    From = dyn_cast_or_null<Instruction>((Value*)FromHandle);
1935    To = ToHandle;
1936
1937    assert(ToHandle && "To value deleted by recursive simplification?");
1938
1939    // If the recursive simplification ended up revisiting and deleting
1940    // 'From' then we're done.
1941    if (From == 0)
1942      return;
1943  }
1944
1945  // If 'From' has value handles referring to it, do a real RAUW to update them.
1946  From->replaceAllUsesWith(To);
1947
1948  From->eraseFromParent();
1949}
1950