LLVM  8.0.0svn
InstructionSimplify.cpp
Go to the documentation of this file.
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 
21 #include "llvm/ADT/SetVector.h"
22 #include "llvm/ADT/Statistic.h"
32 #include "llvm/IR/ConstantRange.h"
33 #include "llvm/IR/DataLayout.h"
34 #include "llvm/IR/Dominators.h"
36 #include "llvm/IR/GlobalAlias.h"
37 #include "llvm/IR/Operator.h"
38 #include "llvm/IR/PatternMatch.h"
39 #include "llvm/IR/ValueHandle.h"
40 #include "llvm/Support/KnownBits.h"
41 #include <algorithm>
42 using namespace llvm;
43 using namespace llvm::PatternMatch;
44 
45 #define DEBUG_TYPE "instsimplify"
46 
47 enum { RecursionLimit = 3 };
48 
49 STATISTIC(NumExpand, "Number of expansions");
50 STATISTIC(NumReassoc, "Number of reassociations");
51 
52 static Value *SimplifyAndInst(Value *, Value *, const SimplifyQuery &, unsigned);
53 static Value *SimplifyBinOp(unsigned, Value *, Value *, const SimplifyQuery &,
54  unsigned);
55 static Value *SimplifyFPBinOp(unsigned, Value *, Value *, const FastMathFlags &,
56  const SimplifyQuery &, unsigned);
57 static Value *SimplifyCmpInst(unsigned, Value *, Value *, const SimplifyQuery &,
58  unsigned);
59 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
60  const SimplifyQuery &Q, unsigned MaxRecurse);
61 static Value *SimplifyOrInst(Value *, Value *, const SimplifyQuery &, unsigned);
62 static Value *SimplifyXorInst(Value *, Value *, const SimplifyQuery &, unsigned);
63 static Value *SimplifyCastInst(unsigned, Value *, Type *,
64  const SimplifyQuery &, unsigned);
66  unsigned);
67 
68 static Value *foldSelectWithBinaryOp(Value *Cond, Value *TrueVal,
69  Value *FalseVal) {
70  BinaryOperator::BinaryOps BinOpCode;
71  if (auto *BO = dyn_cast<BinaryOperator>(Cond))
72  BinOpCode = BO->getOpcode();
73  else
74  return nullptr;
75 
76  CmpInst::Predicate ExpectedPred, Pred1, Pred2;
77  if (BinOpCode == BinaryOperator::Or) {
78  ExpectedPred = ICmpInst::ICMP_NE;
79  } else if (BinOpCode == BinaryOperator::And) {
80  ExpectedPred = ICmpInst::ICMP_EQ;
81  } else
82  return nullptr;
83 
84  // %A = icmp eq %TV, %FV
85  // %B = icmp eq %X, %Y (and one of these is a select operand)
86  // %C = and %A, %B
87  // %D = select %C, %TV, %FV
88  // -->
89  // %FV
90 
91  // %A = icmp ne %TV, %FV
92  // %B = icmp ne %X, %Y (and one of these is a select operand)
93  // %C = or %A, %B
94  // %D = select %C, %TV, %FV
95  // -->
96  // %TV
97  Value *X, *Y;
98  if (!match(Cond, m_c_BinOp(m_c_ICmp(Pred1, m_Specific(TrueVal),
99  m_Specific(FalseVal)),
100  m_ICmp(Pred2, m_Value(X), m_Value(Y)))) ||
101  Pred1 != Pred2 || Pred1 != ExpectedPred)
102  return nullptr;
103 
104  if (X == TrueVal || X == FalseVal || Y == TrueVal || Y == FalseVal)
105  return BinOpCode == BinaryOperator::Or ? TrueVal : FalseVal;
106 
107  return nullptr;
108 }
109 
110 /// For a boolean type or a vector of boolean type, return false or a vector
111 /// with every element false.
112 static Constant *getFalse(Type *Ty) {
113  return ConstantInt::getFalse(Ty);
114 }
115 
116 /// For a boolean type or a vector of boolean type, return true or a vector
117 /// with every element true.
118 static Constant *getTrue(Type *Ty) {
119  return ConstantInt::getTrue(Ty);
120 }
121 
122 /// isSameCompare - Is V equivalent to the comparison "LHS Pred RHS"?
123 static bool isSameCompare(Value *V, CmpInst::Predicate Pred, Value *LHS,
124  Value *RHS) {
125  CmpInst *Cmp = dyn_cast<CmpInst>(V);
126  if (!Cmp)
127  return false;
128  CmpInst::Predicate CPred = Cmp->getPredicate();
129  Value *CLHS = Cmp->getOperand(0), *CRHS = Cmp->getOperand(1);
130  if (CPred == Pred && CLHS == LHS && CRHS == RHS)
131  return true;
132  return CPred == CmpInst::getSwappedPredicate(Pred) && CLHS == RHS &&
133  CRHS == LHS;
134 }
135 
136 /// Does the given value dominate the specified phi node?
137 static bool valueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
139  if (!I)
140  // Arguments and constants dominate all instructions.
141  return true;
142 
143  // If we are processing instructions (and/or basic blocks) that have not been
144  // fully added to a function, the parent nodes may still be null. Simply
145  // return the conservative answer in these cases.
146  if (!I->getParent() || !P->getParent() || !I->getFunction())
147  return false;
148 
149  // If we have a DominatorTree then do a precise test.
150  if (DT)
151  return DT->dominates(I, P);
152 
153  // Otherwise, if the instruction is in the entry block and is not an invoke,
154  // then it obviously dominates all phi nodes.
155  if (I->getParent() == &I->getFunction()->getEntryBlock() &&
156  !isa<InvokeInst>(I))
157  return true;
158 
159  return false;
160 }
161 
162 /// Simplify "A op (B op' C)" by distributing op over op', turning it into
163 /// "(A op B) op' (A op C)". Here "op" is given by Opcode and "op'" is
164 /// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS.
165 /// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)".
166 /// Returns the simplified value, or null if no simplification was performed.
168  Instruction::BinaryOps OpcodeToExpand,
169  const SimplifyQuery &Q, unsigned MaxRecurse) {
170  // Recursion is always used, so bail out at once if we already hit the limit.
171  if (!MaxRecurse--)
172  return nullptr;
173 
174  // Check whether the expression has the form "(A op' B) op C".
175  if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS))
176  if (Op0->getOpcode() == OpcodeToExpand) {
177  // It does! Try turning it into "(A op C) op' (B op C)".
178  Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS;
179  // Do "A op C" and "B op C" both simplify?
180  if (Value *L = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse))
181  if (Value *R = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) {
182  // They do! Return "L op' R" if it simplifies or is already available.
183  // If "L op' R" equals "A op' B" then "L op' R" is just the LHS.
184  if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand)
185  && L == B && R == A)) {
186  ++NumExpand;
187  return LHS;
188  }
189  // Otherwise return "L op' R" if it simplifies.
190  if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) {
191  ++NumExpand;
192  return V;
193  }
194  }
195  }
196 
197  // Check whether the expression has the form "A op (B op' C)".
198  if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS))
199  if (Op1->getOpcode() == OpcodeToExpand) {
200  // It does! Try turning it into "(A op B) op' (A op C)".
201  Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1);
202  // Do "A op B" and "A op C" both simplify?
203  if (Value *L = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse))
204  if (Value *R = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) {
205  // They do! Return "L op' R" if it simplifies or is already available.
206  // If "L op' R" equals "B op' C" then "L op' R" is just the RHS.
207  if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand)
208  && L == C && R == B)) {
209  ++NumExpand;
210  return RHS;
211  }
212  // Otherwise return "L op' R" if it simplifies.
213  if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) {
214  ++NumExpand;
215  return V;
216  }
217  }
218  }
219 
220  return nullptr;
221 }
222 
223 /// Generic simplifications for associative binary operations.
224 /// Returns the simpler value, or null if none was found.
226  Value *LHS, Value *RHS,
227  const SimplifyQuery &Q,
228  unsigned MaxRecurse) {
229  assert(Instruction::isAssociative(Opcode) && "Not an associative operation!");
230 
231  // Recursion is always used, so bail out at once if we already hit the limit.
232  if (!MaxRecurse--)
233  return nullptr;
234 
237 
238  // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely.
239  if (Op0 && Op0->getOpcode() == Opcode) {
240  Value *A = Op0->getOperand(0);
241  Value *B = Op0->getOperand(1);
242  Value *C = RHS;
243 
244  // Does "B op C" simplify?
245  if (Value *V = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) {
246  // It does! Return "A op V" if it simplifies or is already available.
247  // If V equals B then "A op V" is just the LHS.
248  if (V == B) return LHS;
249  // Otherwise return "A op V" if it simplifies.
250  if (Value *W = SimplifyBinOp(Opcode, A, V, Q, MaxRecurse)) {
251  ++NumReassoc;
252  return W;
253  }
254  }
255  }
256 
257  // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely.
258  if (Op1 && Op1->getOpcode() == Opcode) {
259  Value *A = LHS;
260  Value *B = Op1->getOperand(0);
261  Value *C = Op1->getOperand(1);
262 
263  // Does "A op B" simplify?
264  if (Value *V = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse)) {
265  // It does! Return "V op C" if it simplifies or is already available.
266  // If V equals B then "V op C" is just the RHS.
267  if (V == B) return RHS;
268  // Otherwise return "V op C" if it simplifies.
269  if (Value *W = SimplifyBinOp(Opcode, V, C, Q, MaxRecurse)) {
270  ++NumReassoc;
271  return W;
272  }
273  }
274  }
275 
276  // The remaining transforms require commutativity as well as associativity.
277  if (!Instruction::isCommutative(Opcode))
278  return nullptr;
279 
280  // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely.
281  if (Op0 && Op0->getOpcode() == Opcode) {
282  Value *A = Op0->getOperand(0);
283  Value *B = Op0->getOperand(1);
284  Value *C = RHS;
285 
286  // Does "C op A" simplify?
287  if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) {
288  // It does! Return "V op B" if it simplifies or is already available.
289  // If V equals A then "V op B" is just the LHS.
290  if (V == A) return LHS;
291  // Otherwise return "V op B" if it simplifies.
292  if (Value *W = SimplifyBinOp(Opcode, V, B, Q, MaxRecurse)) {
293  ++NumReassoc;
294  return W;
295  }
296  }
297  }
298 
299  // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely.
300  if (Op1 && Op1->getOpcode() == Opcode) {
301  Value *A = LHS;
302  Value *B = Op1->getOperand(0);
303  Value *C = Op1->getOperand(1);
304 
305  // Does "C op A" simplify?
306  if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) {
307  // It does! Return "B op V" if it simplifies or is already available.
308  // If V equals C then "B op V" is just the RHS.
309  if (V == C) return RHS;
310  // Otherwise return "B op V" if it simplifies.
311  if (Value *W = SimplifyBinOp(Opcode, B, V, Q, MaxRecurse)) {
312  ++NumReassoc;
313  return W;
314  }
315  }
316  }
317 
318  return nullptr;
319 }
320 
321 /// In the case of a binary operation with a select instruction as an operand,
322 /// try to simplify the binop by seeing whether evaluating it on both branches
323 /// of the select results in the same value. Returns the common value if so,
324 /// otherwise returns null.
326  Value *RHS, const SimplifyQuery &Q,
327  unsigned MaxRecurse) {
328  // Recursion is always used, so bail out at once if we already hit the limit.
329  if (!MaxRecurse--)
330  return nullptr;
331 
332  SelectInst *SI;
333  if (isa<SelectInst>(LHS)) {
334  SI = cast<SelectInst>(LHS);
335  } else {
336  assert(isa<SelectInst>(RHS) && "No select instruction operand!");
337  SI = cast<SelectInst>(RHS);
338  }
339 
340  // Evaluate the BinOp on the true and false branches of the select.
341  Value *TV;
342  Value *FV;
343  if (SI == LHS) {
344  TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, Q, MaxRecurse);
345  FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, Q, MaxRecurse);
346  } else {
347  TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), Q, MaxRecurse);
348  FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), Q, MaxRecurse);
349  }
350 
351  // If they simplified to the same value, then return the common value.
352  // If they both failed to simplify then return null.
353  if (TV == FV)
354  return TV;
355 
356  // If one branch simplified to undef, return the other one.
357  if (TV && isa<UndefValue>(TV))
358  return FV;
359  if (FV && isa<UndefValue>(FV))
360  return TV;
361 
362  // If applying the operation did not change the true and false select values,
363  // then the result of the binop is the select itself.
364  if (TV == SI->getTrueValue() && FV == SI->getFalseValue())
365  return SI;
366 
367  // If one branch simplified and the other did not, and the simplified
368  // value is equal to the unsimplified one, return the simplified value.
369  // For example, select (cond, X, X & Z) & Z -> X & Z.
370  if ((FV && !TV) || (TV && !FV)) {
371  // Check that the simplified value has the form "X op Y" where "op" is the
372  // same as the original operation.
373  Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV);
374  if (Simplified && Simplified->getOpcode() == unsigned(Opcode)) {
375  // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS".
376  // We already know that "op" is the same as for the simplified value. See
377  // if the operands match too. If so, return the simplified value.
378  Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue();
379  Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS;
380  Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch;
381  if (Simplified->getOperand(0) == UnsimplifiedLHS &&
382  Simplified->getOperand(1) == UnsimplifiedRHS)
383  return Simplified;
384  if (Simplified->isCommutative() &&
385  Simplified->getOperand(1) == UnsimplifiedLHS &&
386  Simplified->getOperand(0) == UnsimplifiedRHS)
387  return Simplified;
388  }
389  }
390 
391  return nullptr;
392 }
393 
394 /// In the case of a comparison with a select instruction, try to simplify the
395 /// comparison by seeing whether both branches of the select result in the same
396 /// value. Returns the common value if so, otherwise returns null.
398  Value *RHS, const SimplifyQuery &Q,
399  unsigned MaxRecurse) {
400  // Recursion is always used, so bail out at once if we already hit the limit.
401  if (!MaxRecurse--)
402  return nullptr;
403 
404  // Make sure the select is on the LHS.
405  if (!isa<SelectInst>(LHS)) {
406  std::swap(LHS, RHS);
407  Pred = CmpInst::getSwappedPredicate(Pred);
408  }
409  assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!");
410  SelectInst *SI = cast<SelectInst>(LHS);
411  Value *Cond = SI->getCondition();
412  Value *TV = SI->getTrueValue();
413  Value *FV = SI->getFalseValue();
414 
415  // Now that we have "cmp select(Cond, TV, FV), RHS", analyse it.
416  // Does "cmp TV, RHS" simplify?
417  Value *TCmp = SimplifyCmpInst(Pred, TV, RHS, Q, MaxRecurse);
418  if (TCmp == Cond) {
419  // It not only simplified, it simplified to the select condition. Replace
420  // it with 'true'.
421  TCmp = getTrue(Cond->getType());
422  } else if (!TCmp) {
423  // It didn't simplify. However if "cmp TV, RHS" is equal to the select
424  // condition then we can replace it with 'true'. Otherwise give up.
425  if (!isSameCompare(Cond, Pred, TV, RHS))
426  return nullptr;
427  TCmp = getTrue(Cond->getType());
428  }
429 
430  // Does "cmp FV, RHS" simplify?
431  Value *FCmp = SimplifyCmpInst(Pred, FV, RHS, Q, MaxRecurse);
432  if (FCmp == Cond) {
433  // It not only simplified, it simplified to the select condition. Replace
434  // it with 'false'.
435  FCmp = getFalse(Cond->getType());
436  } else if (!FCmp) {
437  // It didn't simplify. However if "cmp FV, RHS" is equal to the select
438  // condition then we can replace it with 'false'. Otherwise give up.
439  if (!isSameCompare(Cond, Pred, FV, RHS))
440  return nullptr;
441  FCmp = getFalse(Cond->getType());
442  }
443 
444  // If both sides simplified to the same value, then use it as the result of
445  // the original comparison.
446  if (TCmp == FCmp)
447  return TCmp;
448 
449  // The remaining cases only make sense if the select condition has the same
450  // type as the result of the comparison, so bail out if this is not so.
451  if (Cond->getType()->isVectorTy() != RHS->getType()->isVectorTy())
452  return nullptr;
453  // If the false value simplified to false, then the result of the compare
454  // is equal to "Cond && TCmp". This also catches the case when the false
455  // value simplified to false and the true value to true, returning "Cond".
456  if (match(FCmp, m_Zero()))
457  if (Value *V = SimplifyAndInst(Cond, TCmp, Q, MaxRecurse))
458  return V;
459  // If the true value simplified to true, then the result of the compare
460  // is equal to "Cond || FCmp".
461  if (match(TCmp, m_One()))
462  if (Value *V = SimplifyOrInst(Cond, FCmp, Q, MaxRecurse))
463  return V;
464  // Finally, if the false value simplified to true and the true value to
465  // false, then the result of the compare is equal to "!Cond".
466  if (match(FCmp, m_One()) && match(TCmp, m_Zero()))
467  if (Value *V =
468  SimplifyXorInst(Cond, Constant::getAllOnesValue(Cond->getType()),
469  Q, MaxRecurse))
470  return V;
471 
472  return nullptr;
473 }
474 
475 /// In the case of a binary operation with an operand that is a PHI instruction,
476 /// try to simplify the binop by seeing whether evaluating it on the incoming
477 /// phi values yields the same result for every value. If so returns the common
478 /// value, otherwise returns null.
480  Value *RHS, const SimplifyQuery &Q,
481  unsigned MaxRecurse) {
482  // Recursion is always used, so bail out at once if we already hit the limit.
483  if (!MaxRecurse--)
484  return nullptr;
485 
486  PHINode *PI;
487  if (isa<PHINode>(LHS)) {
488  PI = cast<PHINode>(LHS);
489  // Bail out if RHS and the phi may be mutually interdependent due to a loop.
490  if (!valueDominatesPHI(RHS, PI, Q.DT))
491  return nullptr;
492  } else {
493  assert(isa<PHINode>(RHS) && "No PHI instruction operand!");
494  PI = cast<PHINode>(RHS);
495  // Bail out if LHS and the phi may be mutually interdependent due to a loop.
496  if (!valueDominatesPHI(LHS, PI, Q.DT))
497  return nullptr;
498  }
499 
500  // Evaluate the BinOp on the incoming phi values.
501  Value *CommonValue = nullptr;
502  for (Value *Incoming : PI->incoming_values()) {
503  // If the incoming value is the phi node itself, it can safely be skipped.
504  if (Incoming == PI) continue;
505  Value *V = PI == LHS ?
506  SimplifyBinOp(Opcode, Incoming, RHS, Q, MaxRecurse) :
507  SimplifyBinOp(Opcode, LHS, Incoming, Q, MaxRecurse);
508  // If the operation failed to simplify, or simplified to a different value
509  // to previously, then give up.
510  if (!V || (CommonValue && V != CommonValue))
511  return nullptr;
512  CommonValue = V;
513  }
514 
515  return CommonValue;
516 }
517 
518 /// In the case of a comparison with a PHI instruction, try to simplify the
519 /// comparison by seeing whether comparing with all of the incoming phi values
520 /// yields the same result every time. If so returns the common result,
521 /// otherwise returns null.
523  const SimplifyQuery &Q, unsigned MaxRecurse) {
524  // Recursion is always used, so bail out at once if we already hit the limit.
525  if (!MaxRecurse--)
526  return nullptr;
527 
528  // Make sure the phi is on the LHS.
529  if (!isa<PHINode>(LHS)) {
530  std::swap(LHS, RHS);
531  Pred = CmpInst::getSwappedPredicate(Pred);
532  }
533  assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!");
534  PHINode *PI = cast<PHINode>(LHS);
535 
536  // Bail out if RHS and the phi may be mutually interdependent due to a loop.
537  if (!valueDominatesPHI(RHS, PI, Q.DT))
538  return nullptr;
539 
540  // Evaluate the BinOp on the incoming phi values.
541  Value *CommonValue = nullptr;
542  for (Value *Incoming : PI->incoming_values()) {
543  // If the incoming value is the phi node itself, it can safely be skipped.
544  if (Incoming == PI) continue;
545  Value *V = SimplifyCmpInst(Pred, Incoming, RHS, Q, MaxRecurse);
546  // If the operation failed to simplify, or simplified to a different value
547  // to previously, then give up.
548  if (!V || (CommonValue && V != CommonValue))
549  return nullptr;
550  CommonValue = V;
551  }
552 
553  return CommonValue;
554 }
555 
557  Value *&Op0, Value *&Op1,
558  const SimplifyQuery &Q) {
559  if (auto *CLHS = dyn_cast<Constant>(Op0)) {
560  if (auto *CRHS = dyn_cast<Constant>(Op1))
561  return ConstantFoldBinaryOpOperands(Opcode, CLHS, CRHS, Q.DL);
562 
563  // Canonicalize the constant to the RHS if this is a commutative operation.
564  if (Instruction::isCommutative(Opcode))
565  std::swap(Op0, Op1);
566  }
567  return nullptr;
568 }
569 
570 /// Given operands for an Add, see if we can fold the result.
571 /// If not, this returns null.
572 static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool IsNSW, bool IsNUW,
573  const SimplifyQuery &Q, unsigned MaxRecurse) {
574  if (Constant *C = foldOrCommuteConstant(Instruction::Add, Op0, Op1, Q))
575  return C;
576 
577  // X + undef -> undef
578  if (match(Op1, m_Undef()))
579  return Op1;
580 
581  // X + 0 -> X
582  if (match(Op1, m_Zero()))
583  return Op0;
584 
585  // If two operands are negative, return 0.
586  if (isKnownNegation(Op0, Op1))
587  return Constant::getNullValue(Op0->getType());
588 
589  // X + (Y - X) -> Y
590  // (Y - X) + X -> Y
591  // Eg: X + -X -> 0
592  Value *Y = nullptr;
593  if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) ||
594  match(Op0, m_Sub(m_Value(Y), m_Specific(Op1))))
595  return Y;
596 
597  // X + ~X -> -1 since ~X = -X-1
598  Type *Ty = Op0->getType();
599  if (match(Op0, m_Not(m_Specific(Op1))) ||
600  match(Op1, m_Not(m_Specific(Op0))))
601  return Constant::getAllOnesValue(Ty);
602 
603  // add nsw/nuw (xor Y, signmask), signmask --> Y
604  // The no-wrapping add guarantees that the top bit will be set by the add.
605  // Therefore, the xor must be clearing the already set sign bit of Y.
606  if ((IsNSW || IsNUW) && match(Op1, m_SignMask()) &&
607  match(Op0, m_Xor(m_Value(Y), m_SignMask())))
608  return Y;
609 
610  // add nuw %x, -1 -> -1, because %x can only be 0.
611  if (IsNUW && match(Op1, m_AllOnes()))
612  return Op1; // Which is -1.
613 
614  /// i1 add -> xor.
615  if (MaxRecurse && Op0->getType()->isIntOrIntVectorTy(1))
616  if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1))
617  return V;
618 
619  // Try some generic simplifications for associative operations.
620  if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, Q,
621  MaxRecurse))
622  return V;
623 
624  // Threading Add over selects and phi nodes is pointless, so don't bother.
625  // Threading over the select in "A + select(cond, B, C)" means evaluating
626  // "A+B" and "A+C" and seeing if they are equal; but they are equal if and
627  // only if B and C are equal. If B and C are equal then (since we assume
628  // that operands have already been simplified) "select(cond, B, C)" should
629  // have been simplified to the common value of B and C already. Analysing
630  // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly
631  // for threading over phi nodes.
632 
633  return nullptr;
634 }
635 
636 Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool IsNSW, bool IsNUW,
637  const SimplifyQuery &Query) {
638  return ::SimplifyAddInst(Op0, Op1, IsNSW, IsNUW, Query, RecursionLimit);
639 }
640 
641 /// Compute the base pointer and cumulative constant offsets for V.
642 ///
643 /// This strips all constant offsets off of V, leaving it the base pointer, and
644 /// accumulates the total constant offset applied in the returned constant. It
645 /// returns 0 if V is not a pointer, and returns the constant '0' if there are
646 /// no constant offsets applied.
647 ///
648 /// This is very similar to GetPointerBaseWithConstantOffset except it doesn't
649 /// follow non-inbounds geps. This allows it to remain usable for icmp ult/etc.
650 /// folding.
652  bool AllowNonInbounds = false) {
654 
655  Type *IntPtrTy = DL.getIntPtrType(V->getType())->getScalarType();
656  APInt Offset = APInt::getNullValue(IntPtrTy->getIntegerBitWidth());
657 
658  // Even though we don't look through PHI nodes, we could be called on an
659  // instruction in an unreachable block, which may be on a cycle.
660  SmallPtrSet<Value *, 4> Visited;
661  Visited.insert(V);
662  do {
663  if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
664  if ((!AllowNonInbounds && !GEP->isInBounds()) ||
665  !GEP->accumulateConstantOffset(DL, Offset))
666  break;
667  V = GEP->getPointerOperand();
668  } else if (Operator::getOpcode(V) == Instruction::BitCast) {
669  V = cast<Operator>(V)->getOperand(0);
670  } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
671  if (GA->isInterposable())
672  break;
673  V = GA->getAliasee();
674  } else {
675  if (auto CS = CallSite(V))
676  if (Value *RV = CS.getReturnedArgOperand()) {
677  V = RV;
678  continue;
679  }
680  break;
681  }
682  assert(V->getType()->isPtrOrPtrVectorTy() && "Unexpected operand type!");
683  } while (Visited.insert(V).second);
684 
685  Constant *OffsetIntPtr = ConstantInt::get(IntPtrTy, Offset);
686  if (V->getType()->isVectorTy())
688  OffsetIntPtr);
689  return OffsetIntPtr;
690 }
691 
692 /// Compute the constant difference between two pointer values.
693 /// If the difference is not a constant, returns zero.
695  Value *RHS) {
696  Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS);
697  Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS);
698 
699  // If LHS and RHS are not related via constant offsets to the same base
700  // value, there is nothing we can do here.
701  if (LHS != RHS)
702  return nullptr;
703 
704  // Otherwise, the difference of LHS - RHS can be computed as:
705  // LHS - RHS
706  // = (LHSOffset + Base) - (RHSOffset + Base)
707  // = LHSOffset - RHSOffset
708  return ConstantExpr::getSub(LHSOffset, RHSOffset);
709 }
710 
711 /// Given operands for a Sub, see if we can fold the result.
712 /// If not, this returns null.
713 static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
714  const SimplifyQuery &Q, unsigned MaxRecurse) {
715  if (Constant *C = foldOrCommuteConstant(Instruction::Sub, Op0, Op1, Q))
716  return C;
717 
718  // X - undef -> undef
719  // undef - X -> undef
720  if (match(Op0, m_Undef()) || match(Op1, m_Undef()))
721  return UndefValue::get(Op0->getType());
722 
723  // X - 0 -> X
724  if (match(Op1, m_Zero()))
725  return Op0;
726 
727  // X - X -> 0
728  if (Op0 == Op1)
729  return Constant::getNullValue(Op0->getType());
730 
731  // Is this a negation?
732  if (match(Op0, m_Zero())) {
733  // 0 - X -> 0 if the sub is NUW.
734  if (isNUW)
735  return Constant::getNullValue(Op0->getType());
736 
737  KnownBits Known = computeKnownBits(Op1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
738  if (Known.Zero.isMaxSignedValue()) {
739  // Op1 is either 0 or the minimum signed value. If the sub is NSW, then
740  // Op1 must be 0 because negating the minimum signed value is undefined.
741  if (isNSW)
742  return Constant::getNullValue(Op0->getType());
743 
744  // 0 - X -> X if X is 0 or the minimum signed value.
745  return Op1;
746  }
747  }
748 
749  // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies.
750  // For example, (X + Y) - Y -> X; (Y + X) - Y -> X
751  Value *X = nullptr, *Y = nullptr, *Z = Op1;
752  if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z
753  // See if "V === Y - Z" simplifies.
754  if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, Q, MaxRecurse-1))
755  // It does! Now see if "X + V" simplifies.
756  if (Value *W = SimplifyBinOp(Instruction::Add, X, V, Q, MaxRecurse-1)) {
757  // It does, we successfully reassociated!
758  ++NumReassoc;
759  return W;
760  }
761  // See if "V === X - Z" simplifies.
762  if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1))
763  // It does! Now see if "Y + V" simplifies.
764  if (Value *W = SimplifyBinOp(Instruction::Add, Y, V, Q, MaxRecurse-1)) {
765  // It does, we successfully reassociated!
766  ++NumReassoc;
767  return W;
768  }
769  }
770 
771  // X - (Y + Z) -> (X - Y) - Z or (X - Z) - Y if everything simplifies.
772  // For example, X - (X + 1) -> -1
773  X = Op0;
774  if (MaxRecurse && match(Op1, m_Add(m_Value(Y), m_Value(Z)))) { // X - (Y + Z)
775  // See if "V === X - Y" simplifies.
776  if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1))
777  // It does! Now see if "V - Z" simplifies.
778  if (Value *W = SimplifyBinOp(Instruction::Sub, V, Z, Q, MaxRecurse-1)) {
779  // It does, we successfully reassociated!
780  ++NumReassoc;
781  return W;
782  }
783  // See if "V === X - Z" simplifies.
784  if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1))
785  // It does! Now see if "V - Y" simplifies.
786  if (Value *W = SimplifyBinOp(Instruction::Sub, V, Y, Q, MaxRecurse-1)) {
787  // It does, we successfully reassociated!
788  ++NumReassoc;
789  return W;
790  }
791  }
792 
793  // Z - (X - Y) -> (Z - X) + Y if everything simplifies.
794  // For example, X - (X - Y) -> Y.
795  Z = Op0;
796  if (MaxRecurse && match(Op1, m_Sub(m_Value(X), m_Value(Y)))) // Z - (X - Y)
797  // See if "V === Z - X" simplifies.
798  if (Value *V = SimplifyBinOp(Instruction::Sub, Z, X, Q, MaxRecurse-1))
799  // It does! Now see if "V + Y" simplifies.
800  if (Value *W = SimplifyBinOp(Instruction::Add, V, Y, Q, MaxRecurse-1)) {
801  // It does, we successfully reassociated!
802  ++NumReassoc;
803  return W;
804  }
805 
806  // trunc(X) - trunc(Y) -> trunc(X - Y) if everything simplifies.
807  if (MaxRecurse && match(Op0, m_Trunc(m_Value(X))) &&
808  match(Op1, m_Trunc(m_Value(Y))))
809  if (X->getType() == Y->getType())
810  // See if "V === X - Y" simplifies.
811  if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1))
812  // It does! Now see if "trunc V" simplifies.
813  if (Value *W = SimplifyCastInst(Instruction::Trunc, V, Op0->getType(),
814  Q, MaxRecurse - 1))
815  // It does, return the simplified "trunc V".
816  return W;
817 
818  // Variations on GEP(base, I, ...) - GEP(base, i, ...) -> GEP(null, I-i, ...).
819  if (match(Op0, m_PtrToInt(m_Value(X))) &&
820  match(Op1, m_PtrToInt(m_Value(Y))))
822  return ConstantExpr::getIntegerCast(Result, Op0->getType(), true);
823 
824  // i1 sub -> xor.
825  if (MaxRecurse && Op0->getType()->isIntOrIntVectorTy(1))
826  if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1))
827  return V;
828 
829  // Threading Sub over selects and phi nodes is pointless, so don't bother.
830  // Threading over the select in "A - select(cond, B, C)" means evaluating
831  // "A-B" and "A-C" and seeing if they are equal; but they are equal if and
832  // only if B and C are equal. If B and C are equal then (since we assume
833  // that operands have already been simplified) "select(cond, B, C)" should
834  // have been simplified to the common value of B and C already. Analysing
835  // "A-B" and "A-C" thus gains nothing, but costs compile time. Similarly
836  // for threading over phi nodes.
837 
838  return nullptr;
839 }
840 
841 Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
842  const SimplifyQuery &Q) {
843  return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, Q, RecursionLimit);
844 }
845 
846 /// Given operands for a Mul, see if we can fold the result.
847 /// If not, this returns null.
848 static Value *SimplifyMulInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
849  unsigned MaxRecurse) {
850  if (Constant *C = foldOrCommuteConstant(Instruction::Mul, Op0, Op1, Q))
851  return C;
852 
853  // X * undef -> 0
854  // X * 0 -> 0
855  if (match(Op1, m_CombineOr(m_Undef(), m_Zero())))
856  return Constant::getNullValue(Op0->getType());
857 
858  // X * 1 -> X
859  if (match(Op1, m_One()))
860  return Op0;
861 
862  // (X / Y) * Y -> X if the division is exact.
863  Value *X = nullptr;
864  if (match(Op0, m_Exact(m_IDiv(m_Value(X), m_Specific(Op1)))) || // (X / Y) * Y
865  match(Op1, m_Exact(m_IDiv(m_Value(X), m_Specific(Op0))))) // Y * (X / Y)
866  return X;
867 
868  // i1 mul -> and.
869  if (MaxRecurse && Op0->getType()->isIntOrIntVectorTy(1))
870  if (Value *V = SimplifyAndInst(Op0, Op1, Q, MaxRecurse-1))
871  return V;
872 
873  // Try some generic simplifications for associative operations.
874  if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, Q,
875  MaxRecurse))
876  return V;
877 
878  // Mul distributes over Add. Try some generic simplifications based on this.
879  if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add,
880  Q, MaxRecurse))
881  return V;
882 
883  // If the operation is with the result of a select instruction, check whether
884  // operating on either branch of the select always yields the same value.
885  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
886  if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, Q,
887  MaxRecurse))
888  return V;
889 
890  // If the operation is with the result of a phi instruction, check whether
891  // operating on all incoming values of the phi always yields the same value.
892  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
893  if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, Q,
894  MaxRecurse))
895  return V;
896 
897  return nullptr;
898 }
899 
902 }
903 
904 /// Check for common or similar folds of integer division or integer remainder.
905 /// This applies to all 4 opcodes (sdiv/udiv/srem/urem).
906 static Value *simplifyDivRem(Value *Op0, Value *Op1, bool IsDiv) {
907  Type *Ty = Op0->getType();
908 
909  // X / undef -> undef
910  // X % undef -> undef
911  if (match(Op1, m_Undef()))
912  return Op1;
913 
914  // X / 0 -> undef
915  // X % 0 -> undef
916  // We don't need to preserve faults!
917  if (match(Op1, m_Zero()))
918  return UndefValue::get(Ty);
919 
920  // If any element of a constant divisor vector is zero or undef, the whole op
921  // is undef.
922  auto *Op1C = dyn_cast<Constant>(Op1);
923  if (Op1C && Ty->isVectorTy()) {
924  unsigned NumElts = Ty->getVectorNumElements();
925  for (unsigned i = 0; i != NumElts; ++i) {
926  Constant *Elt = Op1C->getAggregateElement(i);
927  if (Elt && (Elt->isNullValue() || isa<UndefValue>(Elt)))
928  return UndefValue::get(Ty);
929  }
930  }
931 
932  // undef / X -> 0
933  // undef % X -> 0
934  if (match(Op0, m_Undef()))
935  return Constant::getNullValue(Ty);
936 
937  // 0 / X -> 0
938  // 0 % X -> 0
939  if (match(Op0, m_Zero()))
940  return Constant::getNullValue(Op0->getType());
941 
942  // X / X -> 1
943  // X % X -> 0
944  if (Op0 == Op1)
945  return IsDiv ? ConstantInt::get(Ty, 1) : Constant::getNullValue(Ty);
946 
947  // X / 1 -> X
948  // X % 1 -> 0
949  // If this is a boolean op (single-bit element type), we can't have
950  // division-by-zero or remainder-by-zero, so assume the divisor is 1.
951  // Similarly, if we're zero-extending a boolean divisor, then assume it's a 1.
952  Value *X;
953  if (match(Op1, m_One()) || Ty->isIntOrIntVectorTy(1) ||
954  (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)))
955  return IsDiv ? Op0 : Constant::getNullValue(Ty);
956 
957  return nullptr;
958 }
959 
960 /// Given a predicate and two operands, return true if the comparison is true.
961 /// This is a helper for div/rem simplification where we return some other value
962 /// when we can prove a relationship between the operands.
963 static bool isICmpTrue(ICmpInst::Predicate Pred, Value *LHS, Value *RHS,
964  const SimplifyQuery &Q, unsigned MaxRecurse) {
965  Value *V = SimplifyICmpInst(Pred, LHS, RHS, Q, MaxRecurse);
966  Constant *C = dyn_cast_or_null<Constant>(V);
967  return (C && C->isAllOnesValue());
968 }
969 
970 /// Return true if we can simplify X / Y to 0. Remainder can adapt that answer
971 /// to simplify X % Y to X.
972 static bool isDivZero(Value *X, Value *Y, const SimplifyQuery &Q,
973  unsigned MaxRecurse, bool IsSigned) {
974  // Recursion is always used, so bail out at once if we already hit the limit.
975  if (!MaxRecurse--)
976  return false;
977 
978  if (IsSigned) {
979  // |X| / |Y| --> 0
980  //
981  // We require that 1 operand is a simple constant. That could be extended to
982  // 2 variables if we computed the sign bit for each.
983  //
984  // Make sure that a constant is not the minimum signed value because taking
985  // the abs() of that is undefined.
986  Type *Ty = X->getType();
987  const APInt *C;
988  if (match(X, m_APInt(C)) && !C->isMinSignedValue()) {
989  // Is the variable divisor magnitude always greater than the constant
990  // dividend magnitude?
991  // |Y| > |C| --> Y < -abs(C) or Y > abs(C)
992  Constant *PosDividendC = ConstantInt::get(Ty, C->abs());
993  Constant *NegDividendC = ConstantInt::get(Ty, -C->abs());
994  if (isICmpTrue(CmpInst::ICMP_SLT, Y, NegDividendC, Q, MaxRecurse) ||
995  isICmpTrue(CmpInst::ICMP_SGT, Y, PosDividendC, Q, MaxRecurse))
996  return true;
997  }
998  if (match(Y, m_APInt(C))) {
999  // Special-case: we can't take the abs() of a minimum signed value. If
1000  // that's the divisor, then all we have to do is prove that the dividend
1001  // is also not the minimum signed value.
1002  if (C->isMinSignedValue())
1003  return isICmpTrue(CmpInst::ICMP_NE, X, Y, Q, MaxRecurse);
1004 
1005  // Is the variable dividend magnitude always less than the constant
1006  // divisor magnitude?
1007  // |X| < |C| --> X > -abs(C) and X < abs(C)
1008  Constant *PosDivisorC = ConstantInt::get(Ty, C->abs());
1009  Constant *NegDivisorC = ConstantInt::get(Ty, -C->abs());
1010  if (isICmpTrue(CmpInst::ICMP_SGT, X, NegDivisorC, Q, MaxRecurse) &&
1011  isICmpTrue(CmpInst::ICMP_SLT, X, PosDivisorC, Q, MaxRecurse))
1012  return true;
1013  }
1014  return false;
1015  }
1016 
1017  // IsSigned == false.
1018  // Is the dividend unsigned less than the divisor?
1019  return isICmpTrue(ICmpInst::ICMP_ULT, X, Y, Q, MaxRecurse);
1020 }
1021 
1022 /// These are simplifications common to SDiv and UDiv.
1024  const SimplifyQuery &Q, unsigned MaxRecurse) {
1025  if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
1026  return C;
1027 
1028  if (Value *V = simplifyDivRem(Op0, Op1, true))
1029  return V;
1030 
1031  bool IsSigned = Opcode == Instruction::SDiv;
1032 
1033  // (X * Y) / Y -> X if the multiplication does not overflow.
1034  Value *X;
1035  if (match(Op0, m_c_Mul(m_Value(X), m_Specific(Op1)))) {
1036  auto *Mul = cast<OverflowingBinaryOperator>(Op0);
1037  // If the Mul 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 ((IsSigned && match(X, m_SDiv(m_Value(), m_Specific(Op1)))) ||
1043  (!IsSigned && match(X, m_UDiv(m_Value(), m_Specific(Op1)))))
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  // (X /u C1) /u C2 -> 0 if C1 * C2 overflow
1053  ConstantInt *C1, *C2;
1054  if (!IsSigned && match(Op0, m_UDiv(m_Value(X), m_ConstantInt(C1))) &&
1055  match(Op1, m_ConstantInt(C2))) {
1056  bool Overflow;
1057  (void)C1->getValue().umul_ov(C2->getValue(), Overflow);
1058  if (Overflow)
1059  return Constant::getNullValue(Op0->getType());
1060  }
1061 
1062  // If the operation is with the result of a select instruction, check whether
1063  // operating on either branch of the select always yields the same value.
1064  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1065  if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
1066  return V;
1067 
1068  // If the operation is with the result of a phi instruction, check whether
1069  // operating on all incoming values of the phi always yields the same value.
1070  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1071  if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
1072  return V;
1073 
1074  if (isDivZero(Op0, Op1, Q, MaxRecurse, IsSigned))
1075  return Constant::getNullValue(Op0->getType());
1076 
1077  return nullptr;
1078 }
1079 
1080 /// These are simplifications common to SRem and URem.
1082  const SimplifyQuery &Q, unsigned MaxRecurse) {
1083  if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
1084  return C;
1085 
1086  if (Value *V = simplifyDivRem(Op0, Op1, false))
1087  return V;
1088 
1089  // (X % Y) % Y -> X % Y
1090  if ((Opcode == Instruction::SRem &&
1091  match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) ||
1092  (Opcode == Instruction::URem &&
1093  match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
1094  return Op0;
1095 
1096  // (X << Y) % X -> 0
1097  if ((Opcode == Instruction::SRem &&
1098  match(Op0, m_NSWShl(m_Specific(Op1), m_Value()))) ||
1099  (Opcode == Instruction::URem &&
1100  match(Op0, m_NUWShl(m_Specific(Op1), m_Value()))))
1101  return Constant::getNullValue(Op0->getType());
1102 
1103  // If the operation is with the result of a select instruction, check whether
1104  // operating on either branch of the select always yields the same value.
1105  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1106  if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
1107  return V;
1108 
1109  // If the operation is with the result of a phi instruction, check whether
1110  // operating on all incoming values of the phi always yields the same value.
1111  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1112  if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
1113  return V;
1114 
1115  // If X / Y == 0, then X % Y == X.
1116  if (isDivZero(Op0, Op1, Q, MaxRecurse, Opcode == Instruction::SRem))
1117  return Op0;
1118 
1119  return nullptr;
1120 }
1121 
1122 /// Given operands for an SDiv, see if we can fold the result.
1123 /// If not, this returns null.
1124 static Value *SimplifySDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1125  unsigned MaxRecurse) {
1126  // If two operands are negated and no signed overflow, return -1.
1127  if (isKnownNegation(Op0, Op1, /*NeedNSW=*/true))
1128  return Constant::getAllOnesValue(Op0->getType());
1129 
1130  return simplifyDiv(Instruction::SDiv, Op0, Op1, Q, MaxRecurse);
1131 }
1132 
1135 }
1136 
1137 /// Given operands for a UDiv, see if we can fold the result.
1138 /// If not, this returns null.
1139 static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1140  unsigned MaxRecurse) {
1141  return simplifyDiv(Instruction::UDiv, Op0, Op1, Q, MaxRecurse);
1142 }
1143 
1146 }
1147 
1148 /// Given operands for an SRem, see if we can fold the result.
1149 /// If not, this returns null.
1150 static Value *SimplifySRemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1151  unsigned MaxRecurse) {
1152  // If the divisor is 0, the result is undefined, so assume the divisor is -1.
1153  // srem Op0, (sext i1 X) --> srem Op0, -1 --> 0
1154  Value *X;
1155  if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
1156  return ConstantInt::getNullValue(Op0->getType());
1157 
1158  // If the two operands are negated, return 0.
1159  if (isKnownNegation(Op0, Op1))
1160  return ConstantInt::getNullValue(Op0->getType());
1161 
1162  return simplifyRem(Instruction::SRem, Op0, Op1, Q, MaxRecurse);
1163 }
1164 
1167 }
1168 
1169 /// Given operands for a URem, see if we can fold the result.
1170 /// If not, this returns null.
1171 static Value *SimplifyURemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1172  unsigned MaxRecurse) {
1173  return simplifyRem(Instruction::URem, Op0, Op1, Q, MaxRecurse);
1174 }
1175 
1178 }
1179 
1180 /// Returns true if a shift by \c Amount always yields undef.
1181 static bool isUndefShift(Value *Amount) {
1182  Constant *C = dyn_cast<Constant>(Amount);
1183  if (!C)
1184  return false;
1185 
1186  // X shift by undef -> undef because it may shift by the bitwidth.
1187  if (isa<UndefValue>(C))
1188  return true;
1189 
1190  // Shifting by the bitwidth or more is undefined.
1191  if (ConstantInt *CI = dyn_cast<ConstantInt>(C))
1192  if (CI->getValue().getLimitedValue() >=
1193  CI->getType()->getScalarSizeInBits())
1194  return true;
1195 
1196  // If all lanes of a vector shift are undefined the whole shift is.
1197  if (isa<ConstantVector>(C) || isa<ConstantDataVector>(C)) {
1198  for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E; ++I)
1200  return false;
1201  return true;
1202  }
1203 
1204  return false;
1205 }
1206 
1207 /// Given operands for an Shl, LShr or AShr, see if we can fold the result.
1208 /// If not, this returns null.
1210  Value *Op1, const SimplifyQuery &Q, unsigned MaxRecurse) {
1211  if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
1212  return C;
1213 
1214  // 0 shift by X -> 0
1215  if (match(Op0, m_Zero()))
1216  return Constant::getNullValue(Op0->getType());
1217 
1218  // X shift by 0 -> X
1219  // Shift-by-sign-extended bool must be shift-by-0 because shift-by-all-ones
1220  // would be poison.
1221  Value *X;
1222  if (match(Op1, m_Zero()) ||
1223  (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)))
1224  return Op0;
1225 
1226  // Fold undefined shifts.
1227  if (isUndefShift(Op1))
1228  return UndefValue::get(Op0->getType());
1229 
1230  // If the operation is with the result of a select instruction, check whether
1231  // operating on either branch of the select always yields the same value.
1232  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1233  if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
1234  return V;
1235 
1236  // If the operation is with the result of a phi instruction, check whether
1237  // operating on all incoming values of the phi always yields the same value.
1238  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1239  if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
1240  return V;
1241 
1242  // If any bits in the shift amount make that value greater than or equal to
1243  // the number of bits in the type, the shift is undefined.
1244  KnownBits Known = computeKnownBits(Op1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
1245  if (Known.One.getLimitedValue() >= Known.getBitWidth())
1246  return UndefValue::get(Op0->getType());
1247 
1248  // If all valid bits in the shift amount are known zero, the first operand is
1249  // unchanged.
1250  unsigned NumValidShiftBits = Log2_32_Ceil(Known.getBitWidth());
1251  if (Known.countMinTrailingZeros() >= NumValidShiftBits)
1252  return Op0;
1253 
1254  return nullptr;
1255 }
1256 
1257 /// Given operands for an Shl, LShr or AShr, see if we can
1258 /// fold the result. If not, this returns null.
1260  Value *Op1, bool isExact, const SimplifyQuery &Q,
1261  unsigned MaxRecurse) {
1262  if (Value *V = SimplifyShift(Opcode, Op0, Op1, Q, MaxRecurse))
1263  return V;
1264 
1265  // X >> X -> 0
1266  if (Op0 == Op1)
1267  return Constant::getNullValue(Op0->getType());
1268 
1269  // undef >> X -> 0
1270  // undef >> X -> undef (if it's exact)
1271  if (match(Op0, m_Undef()))
1272  return isExact ? Op0 : Constant::getNullValue(Op0->getType());
1273 
1274  // The low bit cannot be shifted out of an exact shift if it is set.
1275  if (isExact) {
1276  KnownBits Op0Known = computeKnownBits(Op0, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT);
1277  if (Op0Known.One[0])
1278  return Op0;
1279  }
1280 
1281  return nullptr;
1282 }
1283 
1284 /// Given operands for an Shl, see if we can fold the result.
1285 /// If not, this returns null.
1286 static Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
1287  const SimplifyQuery &Q, unsigned MaxRecurse) {
1288  if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, Q, MaxRecurse))
1289  return V;
1290 
1291  // undef << X -> 0
1292  // undef << X -> undef if (if it's NSW/NUW)
1293  if (match(Op0, m_Undef()))
1294  return isNSW || isNUW ? Op0 : Constant::getNullValue(Op0->getType());
1295 
1296  // (X >> A) << A -> X
1297  Value *X;
1298  if (match(Op0, m_Exact(m_Shr(m_Value(X), m_Specific(Op1)))))
1299  return X;
1300 
1301  // shl nuw i8 C, %x -> C iff C has sign bit set.
1302  if (isNUW && match(Op0, m_Negative()))
1303  return Op0;
1304  // NOTE: could use computeKnownBits() / LazyValueInfo,
1305  // but the cost-benefit analysis suggests it isn't worth it.
1306 
1307  return nullptr;
1308 }
1309 
1310 Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
1311  const SimplifyQuery &Q) {
1312  return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, Q, RecursionLimit);
1313 }
1314 
1315 /// Given operands for an LShr, see if we can fold the result.
1316 /// If not, this returns null.
1317 static Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
1318  const SimplifyQuery &Q, unsigned MaxRecurse) {
1319  if (Value *V = SimplifyRightShift(Instruction::LShr, Op0, Op1, isExact, Q,
1320  MaxRecurse))
1321  return V;
1322 
1323  // (X << A) >> A -> X
1324  Value *X;
1325  if (match(Op0, m_NUWShl(m_Value(X), m_Specific(Op1))))
1326  return X;
1327 
1328  // ((X << A) | Y) >> A -> X if effective width of Y is not larger than A.
1329  // We can return X as we do in the above case since OR alters no bits in X.
1330  // SimplifyDemandedBits in InstCombine can do more general optimization for
1331  // bit manipulation. This pattern aims to provide opportunities for other
1332  // optimizers by supporting a simple but common case in InstSimplify.
1333  Value *Y;
1334  const APInt *ShRAmt, *ShLAmt;
1335  if (match(Op1, m_APInt(ShRAmt)) &&
1336  match(Op0, m_c_Or(m_NUWShl(m_Value(X), m_APInt(ShLAmt)), m_Value(Y))) &&
1337  *ShRAmt == *ShLAmt) {
1338  const KnownBits YKnown = computeKnownBits(Y, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
1339  const unsigned Width = Op0->getType()->getScalarSizeInBits();
1340  const unsigned EffWidthY = Width - YKnown.countMinLeadingZeros();
1341  if (ShRAmt->uge(EffWidthY))
1342  return X;
1343  }
1344 
1345  return nullptr;
1346 }
1347 
1348 Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
1349  const SimplifyQuery &Q) {
1350  return ::SimplifyLShrInst(Op0, Op1, isExact, Q, RecursionLimit);
1351 }
1352 
1353 /// Given operands for an AShr, see if we can fold the result.
1354 /// If not, this returns null.
1355 static Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
1356  const SimplifyQuery &Q, unsigned MaxRecurse) {
1357  if (Value *V = SimplifyRightShift(Instruction::AShr, Op0, Op1, isExact, Q,
1358  MaxRecurse))
1359  return V;
1360 
1361  // all ones >>a X -> -1
1362  // Do not return Op0 because it may contain undef elements if it's a vector.
1363  if (match(Op0, m_AllOnes()))
1364  return Constant::getAllOnesValue(Op0->getType());
1365 
1366  // (X << A) >> A -> X
1367  Value *X;
1368  if (match(Op0, m_NSWShl(m_Value(X), m_Specific(Op1))))
1369  return X;
1370 
1371  // Arithmetic shifting an all-sign-bit value is a no-op.
1372  unsigned NumSignBits = ComputeNumSignBits(Op0, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
1373  if (NumSignBits == Op0->getType()->getScalarSizeInBits())
1374  return Op0;
1375 
1376  return nullptr;
1377 }
1378 
1379 Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
1380  const SimplifyQuery &Q) {
1381  return ::SimplifyAShrInst(Op0, Op1, isExact, Q, RecursionLimit);
1382 }
1383 
1384 /// Commuted variants are assumed to be handled by calling this function again
1385 /// with the parameters swapped.
1387  ICmpInst *UnsignedICmp, bool IsAnd) {
1388  Value *X, *Y;
1389 
1390  ICmpInst::Predicate EqPred;
1391  if (!match(ZeroICmp, m_ICmp(EqPred, m_Value(Y), m_Zero())) ||
1392  !ICmpInst::isEquality(EqPred))
1393  return nullptr;
1394 
1395  ICmpInst::Predicate UnsignedPred;
1396  if (match(UnsignedICmp, m_ICmp(UnsignedPred, m_Value(X), m_Specific(Y))) &&
1397  ICmpInst::isUnsigned(UnsignedPred))
1398  ;
1399  else if (match(UnsignedICmp,
1400  m_ICmp(UnsignedPred, m_Specific(Y), m_Value(X))) &&
1401  ICmpInst::isUnsigned(UnsignedPred))
1402  UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred);
1403  else
1404  return nullptr;
1405 
1406  // X < Y && Y != 0 --> X < Y
1407  // X < Y || Y != 0 --> Y != 0
1408  if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_NE)
1409  return IsAnd ? UnsignedICmp : ZeroICmp;
1410 
1411  // X >= Y || Y != 0 --> true
1412  // X >= Y || Y == 0 --> X >= Y
1413  if (UnsignedPred == ICmpInst::ICMP_UGE && !IsAnd) {
1414  if (EqPred == ICmpInst::ICMP_NE)
1415  return getTrue(UnsignedICmp->getType());
1416  return UnsignedICmp;
1417  }
1418 
1419  // X < Y && Y == 0 --> false
1420  if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_EQ &&
1421  IsAnd)
1422  return getFalse(UnsignedICmp->getType());
1423 
1424  return nullptr;
1425 }
1426 
1427 /// Commuted variants are assumed to be handled by calling this function again
1428 /// with the parameters swapped.
1430  ICmpInst::Predicate Pred0, Pred1;
1431  Value *A ,*B;
1432  if (!match(Op0, m_ICmp(Pred0, m_Value(A), m_Value(B))) ||
1433  !match(Op1, m_ICmp(Pred1, m_Specific(A), m_Specific(B))))
1434  return nullptr;
1435 
1436  // We have (icmp Pred0, A, B) & (icmp Pred1, A, B).
1437  // If Op1 is always implied true by Op0, then Op0 is a subset of Op1, and we
1438  // can eliminate Op1 from this 'and'.
1439  if (ICmpInst::isImpliedTrueByMatchingCmp(Pred0, Pred1))
1440  return Op0;
1441 
1442  // Check for any combination of predicates that are guaranteed to be disjoint.
1443  if ((Pred0 == ICmpInst::getInversePredicate(Pred1)) ||
1444  (Pred0 == ICmpInst::ICMP_EQ && ICmpInst::isFalseWhenEqual(Pred1)) ||
1445  (Pred0 == ICmpInst::ICMP_SLT && Pred1 == ICmpInst::ICMP_SGT) ||
1446  (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_UGT))
1447  return getFalse(Op0->getType());
1448 
1449  return nullptr;
1450 }
1451 
1452 /// Commuted variants are assumed to be handled by calling this function again
1453 /// with the parameters swapped.
1455  ICmpInst::Predicate Pred0, Pred1;
1456  Value *A ,*B;
1457  if (!match(Op0, m_ICmp(Pred0, m_Value(A), m_Value(B))) ||
1458  !match(Op1, m_ICmp(Pred1, m_Specific(A), m_Specific(B))))
1459  return nullptr;
1460 
1461  // We have (icmp Pred0, A, B) | (icmp Pred1, A, B).
1462  // If Op1 is always implied true by Op0, then Op0 is a subset of Op1, and we
1463  // can eliminate Op0 from this 'or'.
1464  if (ICmpInst::isImpliedTrueByMatchingCmp(Pred0, Pred1))
1465  return Op1;
1466 
1467  // Check for any combination of predicates that cover the entire range of
1468  // possibilities.
1469  if ((Pred0 == ICmpInst::getInversePredicate(Pred1)) ||
1470  (Pred0 == ICmpInst::ICMP_NE && ICmpInst::isTrueWhenEqual(Pred1)) ||
1471  (Pred0 == ICmpInst::ICMP_SLE && Pred1 == ICmpInst::ICMP_SGE) ||
1472  (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_UGE))
1473  return getTrue(Op0->getType());
1474 
1475  return nullptr;
1476 }
1477 
1478 /// Test if a pair of compares with a shared operand and 2 constants has an
1479 /// empty set intersection, full set union, or if one compare is a superset of
1480 /// the other.
1482  bool IsAnd) {
1483  // Look for this pattern: {and/or} (icmp X, C0), (icmp X, C1)).
1484  if (Cmp0->getOperand(0) != Cmp1->getOperand(0))
1485  return nullptr;
1486 
1487  const APInt *C0, *C1;
1488  if (!match(Cmp0->getOperand(1), m_APInt(C0)) ||
1489  !match(Cmp1->getOperand(1), m_APInt(C1)))
1490  return nullptr;
1491 
1492  auto Range0 = ConstantRange::makeExactICmpRegion(Cmp0->getPredicate(), *C0);
1493  auto Range1 = ConstantRange::makeExactICmpRegion(Cmp1->getPredicate(), *C1);
1494 
1495  // For and-of-compares, check if the intersection is empty:
1496  // (icmp X, C0) && (icmp X, C1) --> empty set --> false
1497  if (IsAnd && Range0.intersectWith(Range1).isEmptySet())
1498  return getFalse(Cmp0->getType());
1499 
1500  // For or-of-compares, check if the union is full:
1501  // (icmp X, C0) || (icmp X, C1) --> full set --> true
1502  if (!IsAnd && Range0.unionWith(Range1).isFullSet())
1503  return getTrue(Cmp0->getType());
1504 
1505  // Is one range a superset of the other?
1506  // If this is and-of-compares, take the smaller set:
1507  // (icmp sgt X, 4) && (icmp sgt X, 42) --> icmp sgt X, 42
1508  // If this is or-of-compares, take the larger set:
1509  // (icmp sgt X, 4) || (icmp sgt X, 42) --> icmp sgt X, 4
1510  if (Range0.contains(Range1))
1511  return IsAnd ? Cmp1 : Cmp0;
1512  if (Range1.contains(Range0))
1513  return IsAnd ? Cmp0 : Cmp1;
1514 
1515  return nullptr;
1516 }
1517 
1519  bool IsAnd) {
1520  ICmpInst::Predicate P0 = Cmp0->getPredicate(), P1 = Cmp1->getPredicate();
1521  if (!match(Cmp0->getOperand(1), m_Zero()) ||
1522  !match(Cmp1->getOperand(1), m_Zero()) || P0 != P1)
1523  return nullptr;
1524 
1525  if ((IsAnd && P0 != ICmpInst::ICMP_NE) || (!IsAnd && P1 != ICmpInst::ICMP_EQ))
1526  return nullptr;
1527 
1528  // We have either "(X == 0 || Y == 0)" or "(X != 0 && Y != 0)".
1529  Value *X = Cmp0->getOperand(0);
1530  Value *Y = Cmp1->getOperand(0);
1531 
1532  // If one of the compares is a masked version of a (not) null check, then
1533  // that compare implies the other, so we eliminate the other. Optionally, look
1534  // through a pointer-to-int cast to match a null check of a pointer type.
1535 
1536  // (X == 0) || (([ptrtoint] X & ?) == 0) --> ([ptrtoint] X & ?) == 0
1537  // (X == 0) || ((? & [ptrtoint] X) == 0) --> (? & [ptrtoint] X) == 0
1538  // (X != 0) && (([ptrtoint] X & ?) != 0) --> ([ptrtoint] X & ?) != 0
1539  // (X != 0) && ((? & [ptrtoint] X) != 0) --> (? & [ptrtoint] X) != 0
1540  if (match(Y, m_c_And(m_Specific(X), m_Value())) ||
1542  return Cmp1;
1543 
1544  // (([ptrtoint] Y & ?) == 0) || (Y == 0) --> ([ptrtoint] Y & ?) == 0
1545  // ((? & [ptrtoint] Y) == 0) || (Y == 0) --> (? & [ptrtoint] Y) == 0
1546  // (([ptrtoint] Y & ?) != 0) && (Y != 0) --> ([ptrtoint] Y & ?) != 0
1547  // ((? & [ptrtoint] Y) != 0) && (Y != 0) --> (? & [ptrtoint] Y) != 0
1548  if (match(X, m_c_And(m_Specific(Y), m_Value())) ||
1550  return Cmp0;
1551 
1552  return nullptr;
1553 }
1554 
1556  // (icmp (add V, C0), C1) & (icmp V, C0)
1557  ICmpInst::Predicate Pred0, Pred1;
1558  const APInt *C0, *C1;
1559  Value *V;
1560  if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_APInt(C0)), m_APInt(C1))))
1561  return nullptr;
1562 
1563  if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Value())))
1564  return nullptr;
1565 
1566  auto *AddInst = cast<BinaryOperator>(Op0->getOperand(0));
1567  if (AddInst->getOperand(1) != Op1->getOperand(1))
1568  return nullptr;
1569 
1570  Type *ITy = Op0->getType();
1571  bool isNSW = AddInst->hasNoSignedWrap();
1572  bool isNUW = AddInst->hasNoUnsignedWrap();
1573 
1574  const APInt Delta = *C1 - *C0;
1575  if (C0->isStrictlyPositive()) {
1576  if (Delta == 2) {
1577  if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_SGT)
1578  return getFalse(ITy);
1579  if (Pred0 == ICmpInst::ICMP_SLT && Pred1 == ICmpInst::ICMP_SGT && isNSW)
1580  return getFalse(ITy);
1581  }
1582  if (Delta == 1) {
1583  if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_SGT)
1584  return getFalse(ITy);
1585  if (Pred0 == ICmpInst::ICMP_SLE && Pred1 == ICmpInst::ICMP_SGT && isNSW)
1586  return getFalse(ITy);
1587  }
1588  }
1589  if (C0->getBoolValue() && isNUW) {
1590  if (Delta == 2)
1591  if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_UGT)
1592  return getFalse(ITy);
1593  if (Delta == 1)
1594  if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_UGT)
1595  return getFalse(ITy);
1596  }
1597 
1598  return nullptr;
1599 }
1600 
1602  if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/true))
1603  return X;
1604  if (Value *X = simplifyUnsignedRangeCheck(Op1, Op0, /*IsAnd=*/true))
1605  return X;
1606 
1607  if (Value *X = simplifyAndOfICmpsWithSameOperands(Op0, Op1))
1608  return X;
1609  if (Value *X = simplifyAndOfICmpsWithSameOperands(Op1, Op0))
1610  return X;
1611 
1612  if (Value *X = simplifyAndOrOfICmpsWithConstants(Op0, Op1, true))
1613  return X;
1614 
1615  if (Value *X = simplifyAndOrOfICmpsWithZero(Op0, Op1, true))
1616  return X;
1617 
1618  if (Value *X = simplifyAndOfICmpsWithAdd(Op0, Op1))
1619  return X;
1620  if (Value *X = simplifyAndOfICmpsWithAdd(Op1, Op0))
1621  return X;
1622 
1623  return nullptr;
1624 }
1625 
1627  // (icmp (add V, C0), C1) | (icmp V, C0)
1628  ICmpInst::Predicate Pred0, Pred1;
1629  const APInt *C0, *C1;
1630  Value *V;
1631  if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_APInt(C0)), m_APInt(C1))))
1632  return nullptr;
1633 
1634  if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Value())))
1635  return nullptr;
1636 
1637  auto *AddInst = cast<BinaryOperator>(Op0->getOperand(0));
1638  if (AddInst->getOperand(1) != Op1->getOperand(1))
1639  return nullptr;
1640 
1641  Type *ITy = Op0->getType();
1642  bool isNSW = AddInst->hasNoSignedWrap();
1643  bool isNUW = AddInst->hasNoUnsignedWrap();
1644 
1645  const APInt Delta = *C1 - *C0;
1646  if (C0->isStrictlyPositive()) {
1647  if (Delta == 2) {
1648  if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_SLE)
1649  return getTrue(ITy);
1650  if (Pred0 == ICmpInst::ICMP_SGE && Pred1 == ICmpInst::ICMP_SLE && isNSW)
1651  return getTrue(ITy);
1652  }
1653  if (Delta == 1) {
1654  if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_SLE)
1655  return getTrue(ITy);
1656  if (Pred0 == ICmpInst::ICMP_SGT && Pred1 == ICmpInst::ICMP_SLE && isNSW)
1657  return getTrue(ITy);
1658  }
1659  }
1660  if (C0->getBoolValue() && isNUW) {
1661  if (Delta == 2)
1662  if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_ULE)
1663  return getTrue(ITy);
1664  if (Delta == 1)
1665  if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_ULE)
1666  return getTrue(ITy);
1667  }
1668 
1669  return nullptr;
1670 }
1671 
1673  if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/false))
1674  return X;
1675  if (Value *X = simplifyUnsignedRangeCheck(Op1, Op0, /*IsAnd=*/false))
1676  return X;
1677 
1678  if (Value *X = simplifyOrOfICmpsWithSameOperands(Op0, Op1))
1679  return X;
1680  if (Value *X = simplifyOrOfICmpsWithSameOperands(Op1, Op0))
1681  return X;
1682 
1683  if (Value *X = simplifyAndOrOfICmpsWithConstants(Op0, Op1, false))
1684  return X;
1685 
1686  if (Value *X = simplifyAndOrOfICmpsWithZero(Op0, Op1, false))
1687  return X;
1688 
1689  if (Value *X = simplifyOrOfICmpsWithAdd(Op0, Op1))
1690  return X;
1691  if (Value *X = simplifyOrOfICmpsWithAdd(Op1, Op0))
1692  return X;
1693 
1694  return nullptr;
1695 }
1696 
1698  FCmpInst *LHS, FCmpInst *RHS, bool IsAnd) {
1699  Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1);
1700  Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1);
1701  if (LHS0->getType() != RHS0->getType())
1702  return nullptr;
1703 
1704  FCmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
1705  if ((PredL == FCmpInst::FCMP_ORD && PredR == FCmpInst::FCMP_ORD && IsAnd) ||
1706  (PredL == FCmpInst::FCMP_UNO && PredR == FCmpInst::FCMP_UNO && !IsAnd)) {
1707  // (fcmp ord NNAN, X) & (fcmp ord X, Y) --> fcmp ord X, Y
1708  // (fcmp ord NNAN, X) & (fcmp ord Y, X) --> fcmp ord Y, X
1709  // (fcmp ord X, NNAN) & (fcmp ord X, Y) --> fcmp ord X, Y
1710  // (fcmp ord X, NNAN) & (fcmp ord Y, X) --> fcmp ord Y, X
1711  // (fcmp uno NNAN, X) | (fcmp uno X, Y) --> fcmp uno X, Y
1712  // (fcmp uno NNAN, X) | (fcmp uno Y, X) --> fcmp uno Y, X
1713  // (fcmp uno X, NNAN) | (fcmp uno X, Y) --> fcmp uno X, Y
1714  // (fcmp uno X, NNAN) | (fcmp uno Y, X) --> fcmp uno Y, X
1715  if ((isKnownNeverNaN(LHS0, TLI) && (LHS1 == RHS0 || LHS1 == RHS1)) ||
1716  (isKnownNeverNaN(LHS1, TLI) && (LHS0 == RHS0 || LHS0 == RHS1)))
1717  return RHS;
1718 
1719  // (fcmp ord X, Y) & (fcmp ord NNAN, X) --> fcmp ord X, Y
1720  // (fcmp ord Y, X) & (fcmp ord NNAN, X) --> fcmp ord Y, X
1721  // (fcmp ord X, Y) & (fcmp ord X, NNAN) --> fcmp ord X, Y
1722  // (fcmp ord Y, X) & (fcmp ord X, NNAN) --> fcmp ord Y, X
1723  // (fcmp uno X, Y) | (fcmp uno NNAN, X) --> fcmp uno X, Y
1724  // (fcmp uno Y, X) | (fcmp uno NNAN, X) --> fcmp uno Y, X
1725  // (fcmp uno X, Y) | (fcmp uno X, NNAN) --> fcmp uno X, Y
1726  // (fcmp uno Y, X) | (fcmp uno X, NNAN) --> fcmp uno Y, X
1727  if ((isKnownNeverNaN(RHS0, TLI) && (RHS1 == LHS0 || RHS1 == LHS1)) ||
1728  (isKnownNeverNaN(RHS1, TLI) && (RHS0 == LHS0 || RHS0 == LHS1)))
1729  return LHS;
1730  }
1731 
1732  return nullptr;
1733 }
1734 
1736  Value *Op0, Value *Op1, bool IsAnd) {
1737  // Look through casts of the 'and' operands to find compares.
1738  auto *Cast0 = dyn_cast<CastInst>(Op0);
1739  auto *Cast1 = dyn_cast<CastInst>(Op1);
1740  if (Cast0 && Cast1 && Cast0->getOpcode() == Cast1->getOpcode() &&
1741  Cast0->getSrcTy() == Cast1->getSrcTy()) {
1742  Op0 = Cast0->getOperand(0);
1743  Op1 = Cast1->getOperand(0);
1744  }
1745 
1746  Value *V = nullptr;
1747  auto *ICmp0 = dyn_cast<ICmpInst>(Op0);
1748  auto *ICmp1 = dyn_cast<ICmpInst>(Op1);
1749  if (ICmp0 && ICmp1)
1750  V = IsAnd ? simplifyAndOfICmps(ICmp0, ICmp1) :
1751  simplifyOrOfICmps(ICmp0, ICmp1);
1752 
1753  auto *FCmp0 = dyn_cast<FCmpInst>(Op0);
1754  auto *FCmp1 = dyn_cast<FCmpInst>(Op1);
1755  if (FCmp0 && FCmp1)
1756  V = simplifyAndOrOfFCmps(TLI, FCmp0, FCmp1, IsAnd);
1757 
1758  if (!V)
1759  return nullptr;
1760  if (!Cast0)
1761  return V;
1762 
1763  // If we looked through casts, we can only handle a constant simplification
1764  // because we are not allowed to create a cast instruction here.
1765  if (auto *C = dyn_cast<Constant>(V))
1766  return ConstantExpr::getCast(Cast0->getOpcode(), C, Cast0->getType());
1767 
1768  return nullptr;
1769 }
1770 
1771 /// Given operands for an And, see if we can fold the result.
1772 /// If not, this returns null.
1773 static Value *SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1774  unsigned MaxRecurse) {
1775  if (Constant *C = foldOrCommuteConstant(Instruction::And, Op0, Op1, Q))
1776  return C;
1777 
1778  // X & undef -> 0
1779  if (match(Op1, m_Undef()))
1780  return Constant::getNullValue(Op0->getType());
1781 
1782  // X & X = X
1783  if (Op0 == Op1)
1784  return Op0;
1785 
1786  // X & 0 = 0
1787  if (match(Op1, m_Zero()))
1788  return Constant::getNullValue(Op0->getType());
1789 
1790  // X & -1 = X
1791  if (match(Op1, m_AllOnes()))
1792  return Op0;
1793 
1794  // A & ~A = ~A & A = 0
1795  if (match(Op0, m_Not(m_Specific(Op1))) ||
1796  match(Op1, m_Not(m_Specific(Op0))))
1797  return Constant::getNullValue(Op0->getType());
1798 
1799  // (A | ?) & A = A
1800  if (match(Op0, m_c_Or(m_Specific(Op1), m_Value())))
1801  return Op1;
1802 
1803  // A & (A | ?) = A
1804  if (match(Op1, m_c_Or(m_Specific(Op0), m_Value())))
1805  return Op0;
1806 
1807  // A mask that only clears known zeros of a shifted value is a no-op.
1808  Value *X;
1809  const APInt *Mask;
1810  const APInt *ShAmt;
1811  if (match(Op1, m_APInt(Mask))) {
1812  // If all bits in the inverted and shifted mask are clear:
1813  // and (shl X, ShAmt), Mask --> shl X, ShAmt
1814  if (match(Op0, m_Shl(m_Value(X), m_APInt(ShAmt))) &&
1815  (~(*Mask)).lshr(*ShAmt).isNullValue())
1816  return Op0;
1817 
1818  // If all bits in the inverted and shifted mask are clear:
1819  // and (lshr X, ShAmt), Mask --> lshr X, ShAmt
1820  if (match(Op0, m_LShr(m_Value(X), m_APInt(ShAmt))) &&
1821  (~(*Mask)).shl(*ShAmt).isNullValue())
1822  return Op0;
1823  }
1824 
1825  // A & (-A) = A if A is a power of two or zero.
1826  if (match(Op0, m_Neg(m_Specific(Op1))) ||
1827  match(Op1, m_Neg(m_Specific(Op0)))) {
1828  if (isKnownToBeAPowerOfTwo(Op0, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI,
1829  Q.DT))
1830  return Op0;
1831  if (isKnownToBeAPowerOfTwo(Op1, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI,
1832  Q.DT))
1833  return Op1;
1834  }
1835 
1836  if (Value *V = simplifyAndOrOfCmps(Q.TLI, Op0, Op1, true))
1837  return V;
1838 
1839  // Try some generic simplifications for associative operations.
1840  if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, Q,
1841  MaxRecurse))
1842  return V;
1843 
1844  // And distributes over Or. Try some generic simplifications based on this.
1845  if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or,
1846  Q, MaxRecurse))
1847  return V;
1848 
1849  // And distributes over Xor. Try some generic simplifications based on this.
1850  if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor,
1851  Q, MaxRecurse))
1852  return V;
1853 
1854  // If the operation is with the result of a select instruction, check whether
1855  // operating on either branch of the select always yields the same value.
1856  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1857  if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, Q,
1858  MaxRecurse))
1859  return V;
1860 
1861  // If the operation is with the result of a phi instruction, check whether
1862  // operating on all incoming values of the phi always yields the same value.
1863  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1864  if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, Q,
1865  MaxRecurse))
1866  return V;
1867 
1868  // Assuming the effective width of Y is not larger than A, i.e. all bits
1869  // from X and Y are disjoint in (X << A) | Y,
1870  // if the mask of this AND op covers all bits of X or Y, while it covers
1871  // no bits from the other, we can bypass this AND op. E.g.,
1872  // ((X << A) | Y) & Mask -> Y,
1873  // if Mask = ((1 << effective_width_of(Y)) - 1)
1874  // ((X << A) | Y) & Mask -> X << A,
1875  // if Mask = ((1 << effective_width_of(X)) - 1) << A
1876  // SimplifyDemandedBits in InstCombine can optimize the general case.
1877  // This pattern aims to help other passes for a common case.
1878  Value *Y, *XShifted;
1879  if (match(Op1, m_APInt(Mask)) &&
1880  match(Op0, m_c_Or(m_CombineAnd(m_NUWShl(m_Value(X), m_APInt(ShAmt)),
1881  m_Value(XShifted)),
1882  m_Value(Y)))) {
1883  const unsigned Width = Op0->getType()->getScalarSizeInBits();
1884  const unsigned ShftCnt = ShAmt->getLimitedValue(Width);
1885  const KnownBits YKnown = computeKnownBits(Y, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
1886  const unsigned EffWidthY = Width - YKnown.countMinLeadingZeros();
1887  if (EffWidthY <= ShftCnt) {
1888  const KnownBits XKnown = computeKnownBits(X, Q.DL, 0, Q.AC, Q.CxtI,
1889  Q.DT);
1890  const unsigned EffWidthX = Width - XKnown.countMinLeadingZeros();
1891  const APInt EffBitsY = APInt::getLowBitsSet(Width, EffWidthY);
1892  const APInt EffBitsX = APInt::getLowBitsSet(Width, EffWidthX) << ShftCnt;
1893  // If the mask is extracting all bits from X or Y as is, we can skip
1894  // this AND op.
1895  if (EffBitsY.isSubsetOf(*Mask) && !EffBitsX.intersects(*Mask))
1896  return Y;
1897  if (EffBitsX.isSubsetOf(*Mask) && !EffBitsY.intersects(*Mask))
1898  return XShifted;
1899  }
1900  }
1901 
1902  return nullptr;
1903 }
1904 
1907 }
1908 
1909 /// Given operands for an Or, see if we can fold the result.
1910 /// If not, this returns null.
1911 static Value *SimplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1912  unsigned MaxRecurse) {
1913  if (Constant *C = foldOrCommuteConstant(Instruction::Or, Op0, Op1, Q))
1914  return C;
1915 
1916  // X | undef -> -1
1917  // X | -1 = -1
1918  // Do not return Op1 because it may contain undef elements if it's a vector.
1919  if (match(Op1, m_Undef()) || match(Op1, m_AllOnes()))
1920  return Constant::getAllOnesValue(Op0->getType());
1921 
1922  // X | X = X
1923  // X | 0 = X
1924  if (Op0 == Op1 || match(Op1, m_Zero()))
1925  return Op0;
1926 
1927  // A | ~A = ~A | A = -1
1928  if (match(Op0, m_Not(m_Specific(Op1))) ||
1929  match(Op1, m_Not(m_Specific(Op0))))
1930  return Constant::getAllOnesValue(Op0->getType());
1931 
1932  // (A & ?) | A = A
1933  if (match(Op0, m_c_And(m_Specific(Op1), m_Value())))
1934  return Op1;
1935 
1936  // A | (A & ?) = A
1937  if (match(Op1, m_c_And(m_Specific(Op0), m_Value())))
1938  return Op0;
1939 
1940  // ~(A & ?) | A = -1
1941  if (match(Op0, m_Not(m_c_And(m_Specific(Op1), m_Value()))))
1942  return Constant::getAllOnesValue(Op1->getType());
1943 
1944  // A | ~(A & ?) = -1
1945  if (match(Op1, m_Not(m_c_And(m_Specific(Op1), m_Value()))))
1946  return Constant::getAllOnesValue(Op0->getType());
1947 
1948  Value *A, *B;
1949  // (A & ~B) | (A ^ B) -> (A ^ B)
1950  // (~B & A) | (A ^ B) -> (A ^ B)
1951  // (A & ~B) | (B ^ A) -> (B ^ A)
1952  // (~B & A) | (B ^ A) -> (B ^ A)
1953  if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
1954  (match(Op0, m_c_And(m_Specific(A), m_Not(m_Specific(B)))) ||
1955  match(Op0, m_c_And(m_Not(m_Specific(A)), m_Specific(B)))))
1956  return Op1;
1957 
1958  // Commute the 'or' operands.
1959  // (A ^ B) | (A & ~B) -> (A ^ B)
1960  // (A ^ B) | (~B & A) -> (A ^ B)
1961  // (B ^ A) | (A & ~B) -> (B ^ A)
1962  // (B ^ A) | (~B & A) -> (B ^ A)
1963  if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
1964  (match(Op1, m_c_And(m_Specific(A), m_Not(m_Specific(B)))) ||
1965  match(Op1, m_c_And(m_Not(m_Specific(A)), m_Specific(B)))))
1966  return Op0;
1967 
1968  // (A & B) | (~A ^ B) -> (~A ^ B)
1969  // (B & A) | (~A ^ B) -> (~A ^ B)
1970  // (A & B) | (B ^ ~A) -> (B ^ ~A)
1971  // (B & A) | (B ^ ~A) -> (B ^ ~A)
1972  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
1973  (match(Op1, m_c_Xor(m_Specific(A), m_Not(m_Specific(B)))) ||
1974  match(Op1, m_c_Xor(m_Not(m_Specific(A)), m_Specific(B)))))
1975  return Op1;
1976 
1977  // (~A ^ B) | (A & B) -> (~A ^ B)
1978  // (~A ^ B) | (B & A) -> (~A ^ B)
1979  // (B ^ ~A) | (A & B) -> (B ^ ~A)
1980  // (B ^ ~A) | (B & A) -> (B ^ ~A)
1981  if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
1982  (match(Op0, m_c_Xor(m_Specific(A), m_Not(m_Specific(B)))) ||
1983  match(Op0, m_c_Xor(m_Not(m_Specific(A)), m_Specific(B)))))
1984  return Op0;
1985 
1986  if (Value *V = simplifyAndOrOfCmps(Q.TLI, Op0, Op1, false))
1987  return V;
1988 
1989  // Try some generic simplifications for associative operations.
1990  if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, Q,
1991  MaxRecurse))
1992  return V;
1993 
1994  // Or distributes over And. Try some generic simplifications based on this.
1995  if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, Q,
1996  MaxRecurse))
1997  return V;
1998 
1999  // If the operation is with the result of a select instruction, check whether
2000  // operating on either branch of the select always yields the same value.
2001  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
2002  if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, Q,
2003  MaxRecurse))
2004  return V;
2005 
2006  // (A & C1)|(B & C2)
2007  const APInt *C1, *C2;
2008  if (match(Op0, m_And(m_Value(A), m_APInt(C1))) &&
2009  match(Op1, m_And(m_Value(B), m_APInt(C2)))) {
2010  if (*C1 == ~*C2) {
2011  // (A & C1)|(B & C2)
2012  // If we have: ((V + N) & C1) | (V & C2)
2013  // .. and C2 = ~C1 and C2 is 0+1+ and (N & C2) == 0
2014  // replace with V+N.
2015  Value *N;
2016  if (C2->isMask() && // C2 == 0+1+
2017  match(A, m_c_Add(m_Specific(B), m_Value(N)))) {
2018  // Add commutes, try both ways.
2019  if (MaskedValueIsZero(N, *C2, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2020  return A;
2021  }
2022  // Or commutes, try both ways.
2023  if (C1->isMask() &&
2024  match(B, m_c_Add(m_Specific(A), m_Value(N)))) {
2025  // Add commutes, try both ways.
2026  if (MaskedValueIsZero(N, *C1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2027  return B;
2028  }
2029  }
2030  }
2031 
2032  // If the operation is with the result of a phi instruction, check whether
2033  // operating on all incoming values of the phi always yields the same value.
2034  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
2035  if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, Q, MaxRecurse))
2036  return V;
2037 
2038  return nullptr;
2039 }
2040 
2043 }
2044 
2045 /// Given operands for a Xor, see if we can fold the result.
2046 /// If not, this returns null.
2047 static Value *SimplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
2048  unsigned MaxRecurse) {
2049  if (Constant *C = foldOrCommuteConstant(Instruction::Xor, Op0, Op1, Q))
2050  return C;
2051 
2052  // A ^ undef -> undef
2053  if (match(Op1, m_Undef()))
2054  return Op1;
2055 
2056  // A ^ 0 = A
2057  if (match(Op1, m_Zero()))
2058  return Op0;
2059 
2060  // A ^ A = 0
2061  if (Op0 == Op1)
2062  return Constant::getNullValue(Op0->getType());
2063 
2064  // A ^ ~A = ~A ^ A = -1
2065  if (match(Op0, m_Not(m_Specific(Op1))) ||
2066  match(Op1, m_Not(m_Specific(Op0))))
2067  return Constant::getAllOnesValue(Op0->getType());
2068 
2069  // Try some generic simplifications for associative operations.
2070  if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, Q,
2071  MaxRecurse))
2072  return V;
2073 
2074  // Threading Xor over selects and phi nodes is pointless, so don't bother.
2075  // Threading over the select in "A ^ select(cond, B, C)" means evaluating
2076  // "A^B" and "A^C" and seeing if they are equal; but they are equal if and
2077  // only if B and C are equal. If B and C are equal then (since we assume
2078  // that operands have already been simplified) "select(cond, B, C)" should
2079  // have been simplified to the common value of B and C already. Analysing
2080  // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly
2081  // for threading over phi nodes.
2082 
2083  return nullptr;
2084 }
2085 
2088 }
2089 
2090 
2092  return CmpInst::makeCmpResultType(Op->getType());
2093 }
2094 
2095 /// Rummage around inside V looking for something equivalent to the comparison
2096 /// "LHS Pred RHS". Return such a value if found, otherwise return null.
2097 /// Helper function for analyzing max/min idioms.
2099  Value *LHS, Value *RHS) {
2101  if (!SI)
2102  return nullptr;
2103  CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
2104  if (!Cmp)
2105  return nullptr;
2106  Value *CmpLHS = Cmp->getOperand(0), *CmpRHS = Cmp->getOperand(1);
2107  if (Pred == Cmp->getPredicate() && LHS == CmpLHS && RHS == CmpRHS)
2108  return Cmp;
2109  if (Pred == CmpInst::getSwappedPredicate(Cmp->getPredicate()) &&
2110  LHS == CmpRHS && RHS == CmpLHS)
2111  return Cmp;
2112  return nullptr;
2113 }
2114 
2115 // A significant optimization not implemented here is assuming that alloca
2116 // addresses are not equal to incoming argument values. They don't *alias*,
2117 // as we say, but that doesn't mean they aren't equal, so we take a
2118 // conservative approach.
2119 //
2120 // This is inspired in part by C++11 5.10p1:
2121 // "Two pointers of the same type compare equal if and only if they are both
2122 // null, both point to the same function, or both represent the same
2123 // address."
2124 //
2125 // This is pretty permissive.
2126 //
2127 // It's also partly due to C11 6.5.9p6:
2128 // "Two pointers compare equal if and only if both are null pointers, both are
2129 // pointers to the same object (including a pointer to an object and a
2130 // subobject at its beginning) or function, both are pointers to one past the
2131 // last element of the same array object, or one is a pointer to one past the
2132 // end of one array object and the other is a pointer to the start of a
2133 // different array object that happens to immediately follow the first array
2134 // object in the address space.)
2135 //
2136 // C11's version is more restrictive, however there's no reason why an argument
2137 // couldn't be a one-past-the-end value for a stack object in the caller and be
2138 // equal to the beginning of a stack object in the callee.
2139 //
2140 // If the C and C++ standards are ever made sufficiently restrictive in this
2141 // area, it may be possible to update LLVM's semantics accordingly and reinstate
2142 // this optimization.
2143 static Constant *
2145  const DominatorTree *DT, CmpInst::Predicate Pred,
2146  AssumptionCache *AC, const Instruction *CxtI,
2147  Value *LHS, Value *RHS) {
2148  // First, skip past any trivial no-ops.
2149  LHS = LHS->stripPointerCasts();
2150  RHS = RHS->stripPointerCasts();
2151 
2152  // A non-null pointer is not equal to a null pointer.
2153  if (llvm::isKnownNonZero(LHS, DL) && isa<ConstantPointerNull>(RHS) &&
2154  (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE))
2155  return ConstantInt::get(GetCompareTy(LHS),
2156  !CmpInst::isTrueWhenEqual(Pred));
2157 
2158  // We can only fold certain predicates on pointer comparisons.
2159  switch (Pred) {
2160  default:
2161  return nullptr;
2162 
2163  // Equality comaprisons are easy to fold.
2164  case CmpInst::ICMP_EQ:
2165  case CmpInst::ICMP_NE:
2166  break;
2167 
2168  // We can only handle unsigned relational comparisons because 'inbounds' on
2169  // a GEP only protects against unsigned wrapping.
2170  case CmpInst::ICMP_UGT:
2171  case CmpInst::ICMP_UGE:
2172  case CmpInst::ICMP_ULT:
2173  case CmpInst::ICMP_ULE:
2174  // However, we have to switch them to their signed variants to handle
2175  // negative indices from the base pointer.
2176  Pred = ICmpInst::getSignedPredicate(Pred);
2177  break;
2178  }
2179 
2180  // Strip off any constant offsets so that we can reason about them.
2181  // It's tempting to use getUnderlyingObject or even just stripInBoundsOffsets
2182  // here and compare base addresses like AliasAnalysis does, however there are
2183  // numerous hazards. AliasAnalysis and its utilities rely on special rules
2184  // governing loads and stores which don't apply to icmps. Also, AliasAnalysis
2185  // doesn't need to guarantee pointer inequality when it says NoAlias.
2186  Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS);
2187  Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS);
2188 
2189  // If LHS and RHS are related via constant offsets to the same base
2190  // value, we can replace it with an icmp which just compares the offsets.
2191  if (LHS == RHS)
2192  return ConstantExpr::getICmp(Pred, LHSOffset, RHSOffset);
2193 
2194  // Various optimizations for (in)equality comparisons.
2195  if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) {
2196  // Different non-empty allocations that exist at the same time have
2197  // different addresses (if the program can tell). Global variables always
2198  // exist, so they always exist during the lifetime of each other and all
2199  // allocas. Two different allocas usually have different addresses...
2200  //
2201  // However, if there's an @llvm.stackrestore dynamically in between two
2202  // allocas, they may have the same address. It's tempting to reduce the
2203  // scope of the problem by only looking at *static* allocas here. That would
2204  // cover the majority of allocas while significantly reducing the likelihood
2205  // of having an @llvm.stackrestore pop up in the middle. However, it's not
2206  // actually impossible for an @llvm.stackrestore to pop up in the middle of
2207  // an entry block. Also, if we have a block that's not attached to a
2208  // function, we can't tell if it's "static" under the current definition.
2209  // Theoretically, this problem could be fixed by creating a new kind of
2210  // instruction kind specifically for static allocas. Such a new instruction
2211  // could be required to be at the top of the entry block, thus preventing it
2212  // from being subject to a @llvm.stackrestore. Instcombine could even
2213  // convert regular allocas into these special allocas. It'd be nifty.
2214  // However, until then, this problem remains open.
2215  //
2216  // So, we'll assume that two non-empty allocas have different addresses
2217  // for now.
2218  //
2219  // With all that, if the offsets are within the bounds of their allocations
2220  // (and not one-past-the-end! so we can't use inbounds!), and their
2221  // allocations aren't the same, the pointers are not equal.
2222  //
2223  // Note that it's not necessary to check for LHS being a global variable
2224  // address, due to canonicalization and constant folding.
2225  if (isa<AllocaInst>(LHS) &&
2226  (isa<AllocaInst>(RHS) || isa<GlobalVariable>(RHS))) {
2227  ConstantInt *LHSOffsetCI = dyn_cast<ConstantInt>(LHSOffset);
2228  ConstantInt *RHSOffsetCI = dyn_cast<ConstantInt>(RHSOffset);
2229  uint64_t LHSSize, RHSSize;
2230  ObjectSizeOpts Opts;
2231  Opts.NullIsUnknownSize =
2232  NullPointerIsDefined(cast<AllocaInst>(LHS)->getFunction());
2233  if (LHSOffsetCI && RHSOffsetCI &&
2234  getObjectSize(LHS, LHSSize, DL, TLI, Opts) &&
2235  getObjectSize(RHS, RHSSize, DL, TLI, Opts)) {
2236  const APInt &LHSOffsetValue = LHSOffsetCI->getValue();
2237  const APInt &RHSOffsetValue = RHSOffsetCI->getValue();
2238  if (!LHSOffsetValue.isNegative() &&
2239  !RHSOffsetValue.isNegative() &&
2240  LHSOffsetValue.ult(LHSSize) &&
2241  RHSOffsetValue.ult(RHSSize)) {
2242  return ConstantInt::get(GetCompareTy(LHS),
2243  !CmpInst::isTrueWhenEqual(Pred));
2244  }
2245  }
2246 
2247  // Repeat the above check but this time without depending on DataLayout
2248  // or being able to compute a precise size.
2249  if (!cast<PointerType>(LHS->getType())->isEmptyTy() &&
2250  !cast<PointerType>(RHS->getType())->isEmptyTy() &&
2251  LHSOffset->isNullValue() &&
2252  RHSOffset->isNullValue())
2253  return ConstantInt::get(GetCompareTy(LHS),
2254  !CmpInst::isTrueWhenEqual(Pred));
2255  }
2256 
2257  // Even if an non-inbounds GEP occurs along the path we can still optimize
2258  // equality comparisons concerning the result. We avoid walking the whole
2259  // chain again by starting where the last calls to
2260  // stripAndComputeConstantOffsets left off and accumulate the offsets.
2261  Constant *LHSNoBound = stripAndComputeConstantOffsets(DL, LHS, true);
2262  Constant *RHSNoBound = stripAndComputeConstantOffsets(DL, RHS, true);
2263  if (LHS == RHS)
2264  return ConstantExpr::getICmp(Pred,
2265  ConstantExpr::getAdd(LHSOffset, LHSNoBound),
2266  ConstantExpr::getAdd(RHSOffset, RHSNoBound));
2267 
2268  // If one side of the equality comparison must come from a noalias call
2269  // (meaning a system memory allocation function), and the other side must
2270  // come from a pointer that cannot overlap with dynamically-allocated
2271  // memory within the lifetime of the current function (allocas, byval
2272  // arguments, globals), then determine the comparison result here.
2273  SmallVector<Value *, 8> LHSUObjs, RHSUObjs;
2274  GetUnderlyingObjects(LHS, LHSUObjs, DL);
2275  GetUnderlyingObjects(RHS, RHSUObjs, DL);
2276 
2277  // Is the set of underlying objects all noalias calls?
2278  auto IsNAC = [](ArrayRef<Value *> Objects) {
2279  return all_of(Objects, isNoAliasCall);
2280  };
2281 
2282  // Is the set of underlying objects all things which must be disjoint from
2283  // noalias calls. For allocas, we consider only static ones (dynamic
2284  // allocas might be transformed into calls to malloc not simultaneously
2285  // live with the compared-to allocation). For globals, we exclude symbols
2286  // that might be resolve lazily to symbols in another dynamically-loaded
2287  // library (and, thus, could be malloc'ed by the implementation).
2288  auto IsAllocDisjoint = [](ArrayRef<Value *> Objects) {
2289  return all_of(Objects, [](Value *V) {
2290  if (const AllocaInst *AI = dyn_cast<AllocaInst>(V))
2291  return AI->getParent() && AI->getFunction() && AI->isStaticAlloca();
2292  if (const GlobalValue *GV = dyn_cast<GlobalValue>(V))
2293  return (GV->hasLocalLinkage() || GV->hasHiddenVisibility() ||
2294  GV->hasProtectedVisibility() || GV->hasGlobalUnnamedAddr()) &&
2295  !GV->isThreadLocal();
2296  if (const Argument *A = dyn_cast<Argument>(V))
2297  return A->hasByValAttr();
2298  return false;
2299  });
2300  };
2301 
2302  if ((IsNAC(LHSUObjs) && IsAllocDisjoint(RHSUObjs)) ||
2303  (IsNAC(RHSUObjs) && IsAllocDisjoint(LHSUObjs)))
2304  return ConstantInt::get(GetCompareTy(LHS),
2305  !CmpInst::isTrueWhenEqual(Pred));
2306 
2307  // Fold comparisons for non-escaping pointer even if the allocation call
2308  // cannot be elided. We cannot fold malloc comparison to null. Also, the
2309  // dynamic allocation call could be either of the operands.
2310  Value *MI = nullptr;
2311  if (isAllocLikeFn(LHS, TLI) &&
2312  llvm::isKnownNonZero(RHS, DL, 0, nullptr, CxtI, DT))
2313  MI = LHS;
2314  else if (isAllocLikeFn(RHS, TLI) &&
2315  llvm::isKnownNonZero(LHS, DL, 0, nullptr, CxtI, DT))
2316  MI = RHS;
2317  // FIXME: We should also fold the compare when the pointer escapes, but the
2318  // compare dominates the pointer escape
2319  if (MI && !PointerMayBeCaptured(MI, true, true))
2320  return ConstantInt::get(GetCompareTy(LHS),
2322  }
2323 
2324  // Otherwise, fail.
2325  return nullptr;
2326 }
2327 
2328 /// Fold an icmp when its operands have i1 scalar type.
2330  Value *RHS, const SimplifyQuery &Q) {
2331  Type *ITy = GetCompareTy(LHS); // The return type.
2332  Type *OpTy = LHS->getType(); // The operand type.
2333  if (!OpTy->isIntOrIntVectorTy(1))
2334  return nullptr;
2335 
2336  // A boolean compared to true/false can be simplified in 14 out of the 20
2337  // (10 predicates * 2 constants) possible combinations. Cases not handled here
2338  // require a 'not' of the LHS, so those must be transformed in InstCombine.
2339  if (match(RHS, m_Zero())) {
2340  switch (Pred) {
2341  case CmpInst::ICMP_NE: // X != 0 -> X
2342  case CmpInst::ICMP_UGT: // X >u 0 -> X
2343  case CmpInst::ICMP_SLT: // X <s 0 -> X
2344  return LHS;
2345 
2346  case CmpInst::ICMP_ULT: // X <u 0 -> false
2347  case CmpInst::ICMP_SGT: // X >s 0 -> false
2348  return getFalse(ITy);
2349 
2350  case CmpInst::ICMP_UGE: // X >=u 0 -> true
2351  case CmpInst::ICMP_SLE: // X <=s 0 -> true
2352  return getTrue(ITy);
2353 
2354  default: break;
2355  }
2356  } else if (match(RHS, m_One())) {
2357  switch (Pred) {
2358  case CmpInst::ICMP_EQ: // X == 1 -> X
2359  case CmpInst::ICMP_UGE: // X >=u 1 -> X
2360  case CmpInst::ICMP_SLE: // X <=s -1 -> X
2361  return LHS;
2362 
2363  case CmpInst::ICMP_UGT: // X >u 1 -> false
2364  case CmpInst::ICMP_SLT: // X <s -1 -> false
2365  return getFalse(ITy);
2366 
2367  case CmpInst::ICMP_ULE: // X <=u 1 -> true
2368  case CmpInst::ICMP_SGE: // X >=s -1 -> true
2369  return getTrue(ITy);
2370 
2371  default: break;
2372  }
2373  }
2374 
2375  switch (Pred) {
2376  default:
2377  break;
2378  case ICmpInst::ICMP_UGE:
2379  if (isImpliedCondition(RHS, LHS, Q.DL).getValueOr(false))
2380  return getTrue(ITy);
2381  break;
2382  case ICmpInst::ICMP_SGE:
2383  /// For signed comparison, the values for an i1 are 0 and -1
2384  /// respectively. This maps into a truth table of:
2385  /// LHS | RHS | LHS >=s RHS | LHS implies RHS
2386  /// 0 | 0 | 1 (0 >= 0) | 1
2387  /// 0 | 1 | 1 (0 >= -1) | 1
2388  /// 1 | 0 | 0 (-1 >= 0) | 0
2389  /// 1 | 1 | 1 (-1 >= -1) | 1
2390  if (isImpliedCondition(LHS, RHS, Q.DL).getValueOr(false))
2391  return getTrue(ITy);
2392  break;
2393  case ICmpInst::ICMP_ULE:
2394  if (isImpliedCondition(LHS, RHS, Q.DL).getValueOr(false))
2395  return getTrue(ITy);
2396  break;
2397  }
2398 
2399  return nullptr;
2400 }
2401 
2402 /// Try hard to fold icmp with zero RHS because this is a common case.
2404  Value *RHS, const SimplifyQuery &Q) {
2405  if (!match(RHS, m_Zero()))
2406  return nullptr;
2407 
2408  Type *ITy = GetCompareTy(LHS); // The return type.
2409  switch (Pred) {
2410  default:
2411  llvm_unreachable("Unknown ICmp predicate!");
2412  case ICmpInst::ICMP_ULT:
2413  return getFalse(ITy);
2414  case ICmpInst::ICMP_UGE:
2415  return getTrue(ITy);
2416  case ICmpInst::ICMP_EQ:
2417  case ICmpInst::ICMP_ULE:
2418  if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2419  return getFalse(ITy);
2420  break;
2421  case ICmpInst::ICMP_NE:
2422  case ICmpInst::ICMP_UGT:
2423  if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2424  return getTrue(ITy);
2425  break;
2426  case ICmpInst::ICMP_SLT: {
2427  KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2428  if (LHSKnown.isNegative())
2429  return getTrue(ITy);
2430  if (LHSKnown.isNonNegative())
2431  return getFalse(ITy);
2432  break;
2433  }
2434  case ICmpInst::ICMP_SLE: {
2435  KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2436  if (LHSKnown.isNegative())
2437  return getTrue(ITy);
2438  if (LHSKnown.isNonNegative() &&
2439  isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2440  return getFalse(ITy);
2441  break;
2442  }
2443  case ICmpInst::ICMP_SGE: {
2444  KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2445  if (LHSKnown.isNegative())
2446  return getFalse(ITy);
2447  if (LHSKnown.isNonNegative())
2448  return getTrue(ITy);
2449  break;
2450  }
2451  case ICmpInst::ICMP_SGT: {
2452  KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2453  if (LHSKnown.isNegative())
2454  return getFalse(ITy);
2455  if (LHSKnown.isNonNegative() &&
2456  isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2457  return getTrue(ITy);
2458  break;
2459  }
2460  }
2461 
2462  return nullptr;
2463 }
2464 
2465 /// Many binary operators with a constant operand have an easy-to-compute
2466 /// range of outputs. This can be used to fold a comparison to always true or
2467 /// always false.
2468 static void setLimitsForBinOp(BinaryOperator &BO, APInt &Lower, APInt &Upper) {
2469  unsigned Width = Lower.getBitWidth();
2470  const APInt *C;
2471  switch (BO.getOpcode()) {
2472  case Instruction::Add:
2473  if (match(BO.getOperand(1), m_APInt(C)) && !C->isNullValue()) {
2474  // FIXME: If we have both nuw and nsw, we should reduce the range further.
2475  if (BO.hasNoUnsignedWrap()) {
2476  // 'add nuw x, C' produces [C, UINT_MAX].
2477  Lower = *C;
2478  } else if (BO.hasNoSignedWrap()) {
2479  if (C->isNegative()) {
2480  // 'add nsw x, -C' produces [SINT_MIN, SINT_MAX - C].
2481  Lower = APInt::getSignedMinValue(Width);
2482  Upper = APInt::getSignedMaxValue(Width) + *C + 1;
2483  } else {
2484  // 'add nsw x, +C' produces [SINT_MIN + C, SINT_MAX].
2485  Lower = APInt::getSignedMinValue(Width) + *C;
2486  Upper = APInt::getSignedMaxValue(Width) + 1;
2487  }
2488  }
2489  }
2490  break;
2491 
2492  case Instruction::And:
2493  if (match(BO.getOperand(1), m_APInt(C)))
2494  // 'and x, C' produces [0, C].
2495  Upper = *C + 1;
2496  break;
2497 
2498  case Instruction::Or:
2499  if (match(BO.getOperand(1), m_APInt(C)))
2500  // 'or x, C' produces [C, UINT_MAX].
2501  Lower = *C;
2502  break;
2503 
2504  case Instruction::AShr:
2505  if (match(BO.getOperand(1), m_APInt(C)) && C->ult(Width)) {
2506  // 'ashr x, C' produces [INT_MIN >> C, INT_MAX >> C].
2507  Lower = APInt::getSignedMinValue(Width).ashr(*C);
2508  Upper = APInt::getSignedMaxValue(Width).ashr(*C) + 1;
2509  } else if (match(BO.getOperand(0), m_APInt(C))) {
2510  unsigned ShiftAmount = Width - 1;
2511  if (!C->isNullValue() && BO.isExact())
2512  ShiftAmount = C->countTrailingZeros();
2513  if (C->isNegative()) {
2514  // 'ashr C, x' produces [C, C >> (Width-1)]
2515  Lower = *C;
2516  Upper = C->ashr(ShiftAmount) + 1;
2517  } else {
2518  // 'ashr C, x' produces [C >> (Width-1), C]
2519  Lower = C->ashr(ShiftAmount);
2520  Upper = *C + 1;
2521  }
2522  }
2523  break;
2524 
2525  case Instruction::LShr:
2526  if (match(BO.getOperand(1), m_APInt(C)) && C->ult(Width)) {
2527  // 'lshr x, C' produces [0, UINT_MAX >> C].
2528  Upper = APInt::getAllOnesValue(Width).lshr(*C) + 1;
2529  } else if (match(BO.getOperand(0), m_APInt(C))) {
2530  // 'lshr C, x' produces [C >> (Width-1), C].
2531  unsigned ShiftAmount = Width - 1;
2532  if (!C->isNullValue() && BO.isExact())
2533  ShiftAmount = C->countTrailingZeros();
2534  Lower = C->lshr(ShiftAmount);
2535  Upper = *C + 1;
2536  }
2537  break;
2538 
2539  case Instruction::Shl:
2540  if (match(BO.getOperand(0), m_APInt(C))) {
2541  if (BO.hasNoUnsignedWrap()) {
2542  // 'shl nuw C, x' produces [C, C << CLZ(C)]
2543  Lower = *C;
2544  Upper = Lower.shl(Lower.countLeadingZeros()) + 1;
2545  } else if (BO.hasNoSignedWrap()) { // TODO: What if both nuw+nsw?
2546  if (C->isNegative()) {
2547  // 'shl nsw C, x' produces [C << CLO(C)-1, C]
2548  unsigned ShiftAmount = C->countLeadingOnes() - 1;
2549  Lower = C->shl(ShiftAmount);
2550  Upper = *C + 1;
2551  } else {
2552  // 'shl nsw C, x' produces [C, C << CLZ(C)-1]
2553  unsigned ShiftAmount = C->countLeadingZeros() - 1;
2554  Lower = *C;
2555  Upper = C->shl(ShiftAmount) + 1;
2556  }
2557  }
2558  }
2559  break;
2560 
2561  case Instruction::SDiv:
2562  if (match(BO.getOperand(1), m_APInt(C))) {
2563  APInt IntMin = APInt::getSignedMinValue(Width);
2564  APInt IntMax = APInt::getSignedMaxValue(Width);
2565  if (C->isAllOnesValue()) {
2566  // 'sdiv x, -1' produces [INT_MIN + 1, INT_MAX]
2567  // where C != -1 and C != 0 and C != 1
2568  Lower = IntMin + 1;
2569  Upper = IntMax + 1;
2570  } else if (C->countLeadingZeros() < Width - 1) {
2571  // 'sdiv x, C' produces [INT_MIN / C, INT_MAX / C]
2572  // where C != -1 and C != 0 and C != 1
2573  Lower = IntMin.sdiv(*C);
2574  Upper = IntMax.sdiv(*C);
2575  if (Lower.sgt(Upper))
2576  std::swap(Lower, Upper);
2577  Upper = Upper + 1;
2578  assert(Upper != Lower && "Upper part of range has wrapped!");
2579  }
2580  } else if (match(BO.getOperand(0), m_APInt(C))) {
2581  if (C->isMinSignedValue()) {
2582  // 'sdiv INT_MIN, x' produces [INT_MIN, INT_MIN / -2].
2583  Lower = *C;
2584  Upper = Lower.lshr(1) + 1;
2585  } else {
2586  // 'sdiv C, x' produces [-|C|, |C|].
2587  Upper = C->abs() + 1;
2588  Lower = (-Upper) + 1;
2589  }
2590  }
2591  break;
2592 
2593  case Instruction::UDiv:
2594  if (match(BO.getOperand(1), m_APInt(C)) && !C->isNullValue()) {
2595  // 'udiv x, C' produces [0, UINT_MAX / C].
2596  Upper = APInt::getMaxValue(Width).udiv(*C) + 1;
2597  } else if (match(BO.getOperand(0), m_APInt(C))) {
2598  // 'udiv C, x' produces [0, C].
2599  Upper = *C + 1;
2600  }
2601  break;
2602 
2603  case Instruction::SRem:
2604  if (match(BO.getOperand(1), m_APInt(C))) {
2605  // 'srem x, C' produces (-|C|, |C|).
2606  Upper = C->abs();
2607  Lower = (-Upper) + 1;
2608  }
2609  break;
2610 
2611  case Instruction::URem:
2612  if (match(BO.getOperand(1), m_APInt(C)))
2613  // 'urem x, C' produces [0, C).
2614  Upper = *C;
2615  break;
2616 
2617  default:
2618  break;
2619  }
2620 }
2621 
2623  Value *RHS) {
2624  Type *ITy = GetCompareTy(RHS); // The return type.
2625 
2626  Value *X;
2627  // Sign-bit checks can be optimized to true/false after unsigned
2628  // floating-point casts:
2629  // icmp slt (bitcast (uitofp X)), 0 --> false
2630  // icmp sgt (bitcast (uitofp X)), -1 --> true
2631  if (match(LHS, m_BitCast(m_UIToFP(m_Value(X))))) {
2632  if (Pred == ICmpInst::ICMP_SLT && match(RHS, m_Zero()))
2633  return ConstantInt::getFalse(ITy);
2634  if (Pred == ICmpInst::ICMP_SGT && match(RHS, m_AllOnes()))
2635  return ConstantInt::getTrue(ITy);
2636  }
2637 
2638  const APInt *C;
2639  if (!match(RHS, m_APInt(C)))
2640  return nullptr;
2641 
2642  // Rule out tautological comparisons (eg., ult 0 or uge 0).
2644  if (RHS_CR.isEmptySet())
2645  return ConstantInt::getFalse(ITy);
2646  if (RHS_CR.isFullSet())
2647  return ConstantInt::getTrue(ITy);
2648 
2649  // Find the range of possible values for binary operators.
2650  unsigned Width = C->getBitWidth();
2651  APInt Lower = APInt(Width, 0);
2652  APInt Upper = APInt(Width, 0);
2653  if (auto *BO = dyn_cast<BinaryOperator>(LHS))
2654  setLimitsForBinOp(*BO, Lower, Upper);
2655 
2656  ConstantRange LHS_CR =
2657  Lower != Upper ? ConstantRange(Lower, Upper) : ConstantRange(Width, true);
2658 
2659  if (auto *I = dyn_cast<Instruction>(LHS))
2660  if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
2661  LHS_CR = LHS_CR.intersectWith(getConstantRangeFromMetadata(*Ranges));
2662 
2663  if (!LHS_CR.isFullSet()) {
2664  if (RHS_CR.contains(LHS_CR))
2665  return ConstantInt::getTrue(ITy);
2666  if (RHS_CR.inverse().contains(LHS_CR))
2667  return ConstantInt::getFalse(ITy);
2668  }
2669 
2670  return nullptr;
2671 }
2672 
2673 /// TODO: A large part of this logic is duplicated in InstCombine's
2674 /// foldICmpBinOp(). We should be able to share that and avoid the code
2675 /// duplication.
2677  Value *RHS, const SimplifyQuery &Q,
2678  unsigned MaxRecurse) {
2679  Type *ITy = GetCompareTy(LHS); // The return type.
2680 
2681  BinaryOperator *LBO = dyn_cast<BinaryOperator>(LHS);
2682  BinaryOperator *RBO = dyn_cast<BinaryOperator>(RHS);
2683  if (MaxRecurse && (LBO || RBO)) {
2684  // Analyze the case when either LHS or RHS is an add instruction.
2685  Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr;
2686  // LHS = A + B (or A and B are null); RHS = C + D (or C and D are null).
2687  bool NoLHSWrapProblem = false, NoRHSWrapProblem = false;
2688  if (LBO && LBO->getOpcode() == Instruction::Add) {
2689  A = LBO->getOperand(0);
2690  B = LBO->getOperand(1);
2691  NoLHSWrapProblem =
2692  ICmpInst::isEquality(Pred) ||
2693  (CmpInst::isUnsigned(Pred) && LBO->hasNoUnsignedWrap()) ||
2694  (CmpInst::isSigned(Pred) && LBO->hasNoSignedWrap());
2695  }
2696  if (RBO && RBO->getOpcode() == Instruction::Add) {
2697  C = RBO->getOperand(0);
2698  D = RBO->getOperand(1);
2699  NoRHSWrapProblem =
2700  ICmpInst::isEquality(Pred) ||
2701  (CmpInst::isUnsigned(Pred) && RBO->hasNoUnsignedWrap()) ||
2702  (CmpInst::isSigned(Pred) && RBO->hasNoSignedWrap());
2703  }
2704 
2705  // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow.
2706  if ((A == RHS || B == RHS) && NoLHSWrapProblem)
2707  if (Value *V = SimplifyICmpInst(Pred, A == RHS ? B : A,
2708  Constant::getNullValue(RHS->getType()), Q,
2709  MaxRecurse - 1))
2710  return V;
2711 
2712  // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow.
2713  if ((C == LHS || D == LHS) && NoRHSWrapProblem)
2714  if (Value *V =
2716  C == LHS ? D : C, Q, MaxRecurse - 1))
2717  return V;
2718 
2719  // icmp (X+Y), (X+Z) -> icmp Y,Z for equalities or if there is no overflow.
2720  if (A && C && (A == C || A == D || B == C || B == D) && NoLHSWrapProblem &&
2721  NoRHSWrapProblem) {
2722  // Determine Y and Z in the form icmp (X+Y), (X+Z).
2723  Value *Y, *Z;
2724  if (A == C) {
2725  // C + B == C + D -> B == D
2726  Y = B;
2727  Z = D;
2728  } else if (A == D) {
2729  // D + B == C + D -> B == C
2730  Y = B;
2731  Z = C;
2732  } else if (B == C) {
2733  // A + C == C + D -> A == D
2734  Y = A;
2735  Z = D;
2736  } else {
2737  assert(B == D);
2738  // A + D == C + D -> A == C
2739  Y = A;
2740  Z = C;
2741  }
2742  if (Value *V = SimplifyICmpInst(Pred, Y, Z, Q, MaxRecurse - 1))
2743  return V;
2744  }
2745  }
2746 
2747  {
2748  Value *Y = nullptr;
2749  // icmp pred (or X, Y), X
2750  if (LBO && match(LBO, m_c_Or(m_Value(Y), m_Specific(RHS)))) {
2751  if (Pred == ICmpInst::ICMP_ULT)
2752  return getFalse(ITy);
2753  if (Pred == ICmpInst::ICMP_UGE)
2754  return getTrue(ITy);
2755 
2756  if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE) {
2757  KnownBits RHSKnown = computeKnownBits(RHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2758  KnownBits YKnown = computeKnownBits(Y, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2759  if (RHSKnown.isNonNegative() && YKnown.isNegative())
2760  return Pred == ICmpInst::ICMP_SLT ? getTrue(ITy) : getFalse(ITy);
2761  if (RHSKnown.isNegative() || YKnown.isNonNegative())
2762  return Pred == ICmpInst::ICMP_SLT ? getFalse(ITy) : getTrue(ITy);
2763  }
2764  }
2765  // icmp pred X, (or X, Y)
2766  if (RBO && match(RBO, m_c_Or(m_Value(Y), m_Specific(LHS)))) {
2767  if (Pred == ICmpInst::ICMP_ULE)
2768  return getTrue(ITy);
2769  if (Pred == ICmpInst::ICMP_UGT)
2770  return getFalse(ITy);
2771 
2772  if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLE) {
2773  KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2774  KnownBits YKnown = computeKnownBits(Y, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2775  if (LHSKnown.isNonNegative() && YKnown.isNegative())
2776  return Pred == ICmpInst::ICMP_SGT ? getTrue(ITy) : getFalse(ITy);
2777  if (LHSKnown.isNegative() || YKnown.isNonNegative())
2778  return Pred == ICmpInst::ICMP_SGT ? getFalse(ITy) : getTrue(ITy);
2779  }
2780  }
2781  }
2782 
2783  // icmp pred (and X, Y), X
2784  if (LBO && match(LBO, m_c_And(m_Value(), m_Specific(RHS)))) {
2785  if (Pred == ICmpInst::ICMP_UGT)
2786  return getFalse(ITy);
2787  if (Pred == ICmpInst::ICMP_ULE)
2788  return getTrue(ITy);
2789  }
2790  // icmp pred X, (and X, Y)
2791  if (RBO && match(RBO, m_c_And(m_Value(), m_Specific(LHS)))) {
2792  if (Pred == ICmpInst::ICMP_UGE)
2793  return getTrue(ITy);
2794  if (Pred == ICmpInst::ICMP_ULT)
2795  return getFalse(ITy);
2796  }
2797 
2798  // 0 - (zext X) pred C
2799  if (!CmpInst::isUnsigned(Pred) && match(LHS, m_Neg(m_ZExt(m_Value())))) {
2800  if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) {
2801  if (RHSC->getValue().isStrictlyPositive()) {
2802  if (Pred == ICmpInst::ICMP_SLT)
2803  return ConstantInt::getTrue(RHSC->getContext());
2804  if (Pred == ICmpInst::ICMP_SGE)
2805  return ConstantInt::getFalse(RHSC->getContext());
2806  if (Pred == ICmpInst::ICMP_EQ)
2807  return ConstantInt::getFalse(RHSC->getContext());
2808  if (Pred == ICmpInst::ICMP_NE)
2809  return ConstantInt::getTrue(RHSC->getContext());
2810  }
2811  if (RHSC->getValue().isNonNegative()) {
2812  if (Pred == ICmpInst::ICMP_SLE)
2813  return ConstantInt::getTrue(RHSC->getContext());
2814  if (Pred == ICmpInst::ICMP_SGT)
2815  return ConstantInt::getFalse(RHSC->getContext());
2816  }
2817  }
2818  }
2819 
2820  // icmp pred (urem X, Y), Y
2821  if (LBO && match(LBO, m_URem(m_Value(), m_Specific(RHS)))) {
2822  switch (Pred) {
2823  default:
2824  break;
2825  case ICmpInst::ICMP_SGT:
2826  case ICmpInst::ICMP_SGE: {
2827  KnownBits Known = computeKnownBits(RHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2828  if (!Known.isNonNegative())
2829  break;
2831  }
2832  case ICmpInst::ICMP_EQ:
2833  case ICmpInst::ICMP_UGT:
2834  case ICmpInst::ICMP_UGE:
2835  return getFalse(ITy);
2836  case ICmpInst::ICMP_SLT:
2837  case ICmpInst::ICMP_SLE: {
2838  KnownBits Known = computeKnownBits(RHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2839  if (!Known.isNonNegative())
2840  break;
2842  }
2843  case ICmpInst::ICMP_NE:
2844  case ICmpInst::ICMP_ULT:
2845  case ICmpInst::ICMP_ULE:
2846  return getTrue(ITy);
2847  }
2848  }
2849 
2850  // icmp pred X, (urem Y, X)
2851  if (RBO && match(RBO, m_URem(m_Value(), m_Specific(LHS)))) {
2852  switch (Pred) {
2853  default:
2854  break;
2855  case ICmpInst::ICMP_SGT:
2856  case ICmpInst::ICMP_SGE: {
2857  KnownBits Known = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2858  if (!Known.isNonNegative())
2859  break;
2861  }
2862  case ICmpInst::ICMP_NE:
2863  case ICmpInst::ICMP_UGT:
2864  case ICmpInst::ICMP_UGE:
2865  return getTrue(ITy);
2866  case ICmpInst::ICMP_SLT:
2867  case ICmpInst::ICMP_SLE: {
2868  KnownBits Known = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2869  if (!Known.isNonNegative())
2870  break;
2872  }
2873  case ICmpInst::ICMP_EQ:
2874  case ICmpInst::ICMP_ULT:
2875  case ICmpInst::ICMP_ULE:
2876  return getFalse(ITy);
2877  }
2878  }
2879 
2880  // x >> y <=u x
2881  // x udiv y <=u x.
2882  if (LBO && (match(LBO, m_LShr(m_Specific(RHS), m_Value())) ||
2883  match(LBO, m_UDiv(m_Specific(RHS), m_Value())))) {
2884  // icmp pred (X op Y), X
2885  if (Pred == ICmpInst::ICMP_UGT)
2886  return getFalse(ITy);
2887  if (Pred == ICmpInst::ICMP_ULE)
2888  return getTrue(ITy);
2889  }
2890 
2891  // x >=u x >> y
2892  // x >=u x udiv y.
2893  if (RBO && (match(RBO, m_LShr(m_Specific(LHS), m_Value())) ||
2894  match(RBO, m_UDiv(m_Specific(LHS), m_Value())))) {
2895  // icmp pred X, (X op Y)
2896  if (Pred == ICmpInst::ICMP_ULT)
2897  return getFalse(ITy);
2898  if (Pred == ICmpInst::ICMP_UGE)
2899  return getTrue(ITy);
2900  }
2901 
2902  // handle:
2903  // CI2 << X == CI
2904  // CI2 << X != CI
2905  //
2906  // where CI2 is a power of 2 and CI isn't
2907  if (auto *CI = dyn_cast<ConstantInt>(RHS)) {
2908  const APInt *CI2Val, *CIVal = &CI->getValue();
2909  if (LBO && match(LBO, m_Shl(m_APInt(CI2Val), m_Value())) &&
2910  CI2Val->isPowerOf2()) {
2911  if (!CIVal->isPowerOf2()) {
2912  // CI2 << X can equal zero in some circumstances,
2913  // this simplification is unsafe if CI is zero.
2914  //
2915  // We know it is safe if:
2916  // - The shift is nsw, we can't shift out the one bit.
2917  // - The shift is nuw, we can't shift out the one bit.
2918  // - CI2 is one
2919  // - CI isn't zero
2920  if (LBO->hasNoSignedWrap() || LBO->hasNoUnsignedWrap() ||
2921  CI2Val->isOneValue() || !CI->isZero()) {
2922  if (Pred == ICmpInst::ICMP_EQ)
2923  return ConstantInt::getFalse(RHS->getContext());
2924  if (Pred == ICmpInst::ICMP_NE)
2925  return ConstantInt::getTrue(RHS->getContext());
2926  }
2927  }
2928  if (CIVal->isSignMask() && CI2Val->isOneValue()) {
2929  if (Pred == ICmpInst::ICMP_UGT)
2930  return ConstantInt::getFalse(RHS->getContext());
2931  if (Pred == ICmpInst::ICMP_ULE)
2932  return ConstantInt::getTrue(RHS->getContext());
2933  }
2934  }
2935  }
2936 
2937  if (MaxRecurse && LBO && RBO && LBO->getOpcode() == RBO->getOpcode() &&
2938  LBO->getOperand(1) == RBO->getOperand(1)) {
2939  switch (LBO->getOpcode()) {
2940  default:
2941  break;
2942  case Instruction::UDiv:
2943  case Instruction::LShr:
2944  if (ICmpInst::isSigned(Pred) || !LBO->isExact() || !RBO->isExact())
2945  break;
2946  if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
2947  RBO->getOperand(0), Q, MaxRecurse - 1))
2948  return V;
2949  break;
2950  case Instruction::SDiv:
2951  if (!ICmpInst::isEquality(Pred) || !LBO->isExact() || !RBO->isExact())
2952  break;
2953  if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
2954  RBO->getOperand(0), Q, MaxRecurse - 1))
2955  return V;
2956  break;
2957  case Instruction::AShr:
2958  if (!LBO->isExact() || !RBO->isExact())
2959  break;
2960  if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
2961  RBO->getOperand(0), Q, MaxRecurse - 1))
2962  return V;
2963  break;
2964  case Instruction::Shl: {
2965  bool NUW = LBO->hasNoUnsignedWrap() && RBO->hasNoUnsignedWrap();
2966  bool NSW = LBO->hasNoSignedWrap() && RBO->hasNoSignedWrap();
2967  if (!NUW && !NSW)
2968  break;
2969  if (!NSW && ICmpInst::isSigned(Pred))
2970  break;
2971  if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
2972  RBO->getOperand(0), Q, MaxRecurse - 1))
2973  return V;
2974  break;
2975  }
2976  }
2977  }
2978  return nullptr;
2979 }
2980 
2981 /// Simplify integer comparisons where at least one operand of the compare
2982 /// matches an integer min/max idiom.
2984  Value *RHS, const SimplifyQuery &Q,
2985  unsigned MaxRecurse) {
2986  Type *ITy = GetCompareTy(LHS); // The return type.
2987  Value *A, *B;
2989  CmpInst::Predicate EqP; // Chosen so that "A == max/min(A,B)" iff "A EqP B".
2990 
2991  // Signed variants on "max(a,b)>=a -> true".
2992  if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) {
2993  if (A != RHS)
2994  std::swap(A, B); // smax(A, B) pred A.
2995  EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B".
2996  // We analyze this as smax(A, B) pred A.
2997  P = Pred;
2998  } else if (match(RHS, m_SMax(m_Value(A), m_Value(B))) &&
2999  (A == LHS || B == LHS)) {
3000  if (A != LHS)
3001  std::swap(A, B); // A pred smax(A, B).
3002  EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B".
3003  // We analyze this as smax(A, B) swapped-pred A.
3004  P = CmpInst::getSwappedPredicate(Pred);
3005  } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) &&
3006  (A == RHS || B == RHS)) {
3007  if (A != RHS)
3008  std::swap(A, B); // smin(A, B) pred A.
3009  EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B".
3010  // We analyze this as smax(-A, -B) swapped-pred -A.
3011  // Note that we do not need to actually form -A or -B thanks to EqP.
3012  P = CmpInst::getSwappedPredicate(Pred);
3013  } else if (match(RHS, m_SMin(m_Value(A), m_Value(B))) &&
3014  (A == LHS || B == LHS)) {
3015  if (A != LHS)
3016  std::swap(A, B); // A pred smin(A, B).
3017  EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B".
3018  // We analyze this as smax(-A, -B) pred -A.
3019  // Note that we do not need to actually form -A or -B thanks to EqP.
3020  P = Pred;
3021  }
3022  if (P != CmpInst::BAD_ICMP_PREDICATE) {
3023  // Cases correspond to "max(A, B) p A".
3024  switch (P) {
3025  default:
3026  break;
3027  case CmpInst::ICMP_EQ:
3028  case CmpInst::ICMP_SLE:
3029  // Equivalent to "A EqP B". This may be the same as the condition tested
3030  // in the max/min; if so, we can just return that.
3031  if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B))
3032  return V;
3033  if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B))
3034  return V;
3035  // Otherwise, see if "A EqP B" simplifies.
3036  if (MaxRecurse)
3037  if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse - 1))
3038  return V;
3039  break;
3040  case CmpInst::ICMP_NE:
3041  case CmpInst::ICMP_SGT: {
3043  // Equivalent to "A InvEqP B". This may be the same as the condition
3044  // tested in the max/min; if so, we can just return that.
3045  if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B))
3046  return V;
3047  if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B))
3048  return V;
3049  // Otherwise, see if "A InvEqP B" simplifies.
3050  if (MaxRecurse)
3051  if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse - 1))
3052  return V;
3053  break;
3054  }
3055  case CmpInst::ICMP_SGE:
3056  // Always true.
3057  return getTrue(ITy);
3058  case CmpInst::ICMP_SLT:
3059  // Always false.
3060  return getFalse(ITy);
3061  }
3062  }
3063 
3064  // Unsigned variants on "max(a,b)>=a -> true".
3066  if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) {
3067  if (A != RHS)
3068  std::swap(A, B); // umax(A, B) pred A.
3069  EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B".
3070  // We analyze this as umax(A, B) pred A.
3071  P = Pred;
3072  } else if (match(RHS, m_UMax(m_Value(A), m_Value(B))) &&
3073  (A == LHS || B == LHS)) {
3074  if (A != LHS)
3075  std::swap(A, B); // A pred umax(A, B).
3076  EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B".
3077  // We analyze this as umax(A, B) swapped-pred A.
3078  P = CmpInst::getSwappedPredicate(Pred);
3079  } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) &&
3080  (A == RHS || B == RHS)) {
3081  if (A != RHS)
3082  std::swap(A, B); // umin(A, B) pred A.
3083  EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B".
3084  // We analyze this as umax(-A, -B) swapped-pred -A.
3085  // Note that we do not need to actually form -A or -B thanks to EqP.
3086  P = CmpInst::getSwappedPredicate(Pred);
3087  } else if (match(RHS, m_UMin(m_Value(A), m_Value(B))) &&
3088  (A == LHS || B == LHS)) {
3089  if (A != LHS)
3090  std::swap(A, B); // A pred umin(A, B).
3091  EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B".
3092  // We analyze this as umax(-A, -B) pred -A.
3093  // Note that we do not need to actually form -A or -B thanks to EqP.
3094  P = Pred;
3095  }
3096  if (P != CmpInst::BAD_ICMP_PREDICATE) {
3097  // Cases correspond to "max(A, B) p A".
3098  switch (P) {
3099  default:
3100  break;
3101  case CmpInst::ICMP_EQ:
3102  case CmpInst::ICMP_ULE:
3103  // Equivalent to "A EqP B". This may be the same as the condition tested
3104  // in the max/min; if so, we can just return that.
3105  if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B))
3106  return V;
3107  if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B))
3108  return V;
3109  // Otherwise, see if "A EqP B" simplifies.
3110  if (MaxRecurse)
3111  if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse - 1))
3112  return V;
3113  break;
3114  case CmpInst::ICMP_NE:
3115  case CmpInst::ICMP_UGT: {
3117  // Equivalent to "A InvEqP B". This may be the same as the condition
3118  // tested in the max/min; if so, we can just return that.
3119  if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B))
3120  return V;
3121  if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B))
3122  return V;
3123  // Otherwise, see if "A InvEqP B" simplifies.
3124  if (MaxRecurse)
3125  if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse - 1))
3126  return V;
3127  break;
3128  }
3129  case CmpInst::ICMP_UGE:
3130  // Always true.
3131  return getTrue(ITy);
3132  case CmpInst::ICMP_ULT:
3133  // Always false.
3134  return getFalse(ITy);
3135  }
3136  }
3137 
3138  // Variants on "max(x,y) >= min(x,z)".
3139  Value *C, *D;
3140  if (match(LHS, m_SMax(m_Value(A), m_Value(B))) &&
3141  match(RHS, m_SMin(m_Value(C), m_Value(D))) &&
3142  (A == C || A == D || B == C || B == D)) {
3143  // max(x, ?) pred min(x, ?).
3144  if (Pred == CmpInst::ICMP_SGE)
3145  // Always true.
3146  return getTrue(ITy);
3147  if (Pred == CmpInst::ICMP_SLT)
3148  // Always false.
3149  return getFalse(ITy);
3150  } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) &&
3151  match(RHS, m_SMax(m_Value(C), m_Value(D))) &&
3152  (A == C || A == D || B == C || B == D)) {
3153  // min(x, ?) pred max(x, ?).
3154  if (Pred == CmpInst::ICMP_SLE)
3155  // Always true.
3156  return getTrue(ITy);
3157  if (Pred == CmpInst::ICMP_SGT)
3158  // Always false.
3159  return getFalse(ITy);
3160  } else if (match(LHS, m_UMax(m_Value(A), m_Value(B))) &&
3161  match(RHS, m_UMin(m_Value(C), m_Value(D))) &&
3162  (A == C || A == D || B == C || B == D)) {
3163  // max(x, ?) pred min(x, ?).
3164  if (Pred == CmpInst::ICMP_UGE)
3165  // Always true.
3166  return getTrue(ITy);
3167  if (Pred == CmpInst::ICMP_ULT)
3168  // Always false.
3169  return getFalse(ITy);
3170  } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) &&
3171  match(RHS, m_UMax(m_Value(C), m_Value(D))) &&
3172  (A == C || A == D || B == C || B == D)) {
3173  // min(x, ?) pred max(x, ?).
3174  if (Pred == CmpInst::ICMP_ULE)
3175  // Always true.
3176  return getTrue(ITy);
3177  if (Pred == CmpInst::ICMP_UGT)
3178  // Always false.
3179  return getFalse(ITy);
3180  }
3181 
3182  return nullptr;
3183 }
3184 
3185 /// Given operands for an ICmpInst, see if we can fold the result.
3186 /// If not, this returns null.
3187 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
3188  const SimplifyQuery &Q, unsigned MaxRecurse) {
3189  CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
3190  assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
3191 
3192  if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
3193  if (Constant *CRHS = dyn_cast<Constant>(RHS))
3194  return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI);
3195 
3196  // If we have a constant, make sure it is on the RHS.
3197  std::swap(LHS, RHS);
3198  Pred = CmpInst::getSwappedPredicate(Pred);
3199  }
3200 
3201  Type *ITy = GetCompareTy(LHS); // The return type.
3202 
3203  // icmp X, X -> true/false
3204  // icmp X, undef -> true/false because undef could be X.
3205  if (LHS == RHS || isa<UndefValue>(RHS))
3206  return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
3207 
3208  if (Value *V = simplifyICmpOfBools(Pred, LHS, RHS, Q))
3209  return V;
3210 
3211  if (Value *V = simplifyICmpWithZero(Pred, LHS, RHS, Q))
3212  return V;
3213 
3214  if (Value *V = simplifyICmpWithConstant(Pred, LHS, RHS))
3215  return V;
3216 
3217  // If both operands have range metadata, use the metadata
3218  // to simplify the comparison.
3219  if (isa<Instruction>(RHS) && isa<Instruction>(LHS)) {
3220  auto RHS_Instr = cast<Instruction>(RHS);
3221  auto LHS_Instr = cast<Instruction>(LHS);
3222 
3223  if (RHS_Instr->getMetadata(LLVMContext::MD_range) &&
3224  LHS_Instr->getMetadata(LLVMContext::MD_range)) {
3225  auto RHS_CR = getConstantRangeFromMetadata(
3226  *RHS_Instr->getMetadata(LLVMContext::MD_range));
3227  auto LHS_CR = getConstantRangeFromMetadata(
3228  *LHS_Instr->getMetadata(LLVMContext::MD_range));
3229 
3230  auto Satisfied_CR = ConstantRange::makeSatisfyingICmpRegion(Pred, RHS_CR);
3231  if (Satisfied_CR.contains(LHS_CR))
3232  return ConstantInt::getTrue(RHS->getContext());
3233 
3234  auto InversedSatisfied_CR = ConstantRange::makeSatisfyingICmpRegion(
3235  CmpInst::getInversePredicate(Pred), RHS_CR);
3236  if (InversedSatisfied_CR.contains(LHS_CR))
3237  return ConstantInt::getFalse(RHS->getContext());
3238  }
3239  }
3240 
3241  // Compare of cast, for example (zext X) != 0 -> X != 0
3242  if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) {
3243  Instruction *LI = cast<CastInst>(LHS);
3244  Value *SrcOp = LI->getOperand(0);
3245  Type *SrcTy = SrcOp->getType();
3246  Type *DstTy = LI->getType();
3247 
3248  // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input
3249  // if the integer type is the same size as the pointer type.
3250  if (MaxRecurse && isa<PtrToIntInst>(LI) &&
3251  Q.DL.getTypeSizeInBits(SrcTy) == DstTy->getPrimitiveSizeInBits()) {
3252  if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
3253  // Transfer the cast to the constant.
3254  if (Value *V = SimplifyICmpInst(Pred, SrcOp,
3255  ConstantExpr::getIntToPtr(RHSC, SrcTy),
3256  Q, MaxRecurse-1))
3257  return V;
3258  } else if (PtrToIntInst *RI = dyn_cast<PtrToIntInst>(RHS)) {
3259  if (RI->getOperand(0)->getType() == SrcTy)
3260  // Compare without the cast.
3261  if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0),
3262  Q, MaxRecurse-1))
3263  return V;
3264  }
3265  }
3266 
3267  if (isa<ZExtInst>(LHS)) {
3268  // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the
3269  // same type.
3270  if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) {
3271  if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
3272  // Compare X and Y. Note that signed predicates become unsigned.
3274  SrcOp, RI->getOperand(0), Q,
3275  MaxRecurse-1))
3276  return V;
3277  }
3278  // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended
3279  // too. If not, then try to deduce the result of the comparison.
3280  else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
3281  // Compute the constant that would happen if we truncated to SrcTy then
3282  // reextended to DstTy.
3283  Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
3284  Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy);
3285 
3286  // If the re-extended constant didn't change then this is effectively
3287  // also a case of comparing two zero-extended values.
3288  if (RExt == CI && MaxRecurse)
3290  SrcOp, Trunc, Q, MaxRecurse-1))
3291  return V;
3292 
3293  // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit
3294  // there. Use this to work out the result of the comparison.
3295  if (RExt != CI) {
3296  switch (Pred) {
3297  default: llvm_unreachable("Unknown ICmp predicate!");
3298  // LHS <u RHS.
3299  case ICmpInst::ICMP_EQ:
3300  case ICmpInst::ICMP_UGT:
3301  case ICmpInst::ICMP_UGE:
3302  return ConstantInt::getFalse(CI->getContext());
3303 
3304  case ICmpInst::ICMP_NE:
3305  case ICmpInst::ICMP_ULT:
3306  case ICmpInst::ICMP_ULE:
3307  return ConstantInt::getTrue(CI->getContext());
3308 
3309  // LHS is non-negative. If RHS is negative then LHS >s LHS. If RHS
3310  // is non-negative then LHS <s RHS.
3311  case ICmpInst::ICMP_SGT:
3312  case ICmpInst::ICMP_SGE:
3313  return CI->getValue().isNegative() ?
3314  ConstantInt::getTrue(CI->getContext()) :
3315  ConstantInt::getFalse(CI->getContext());
3316 
3317  case ICmpInst::ICMP_SLT:
3318  case ICmpInst::ICMP_SLE:
3319  return CI->getValue().isNegative() ?
3320  ConstantInt::getFalse(CI->getContext()) :
3321  ConstantInt::getTrue(CI->getContext());
3322  }
3323  }
3324  }
3325  }
3326 
3327  if (isa<SExtInst>(LHS)) {
3328  // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the
3329  // same type.
3330  if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) {
3331  if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
3332  // Compare X and Y. Note that the predicate does not change.
3333  if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0),
3334  Q, MaxRecurse-1))
3335  return V;
3336  }
3337  // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended
3338  // too. If not, then try to deduce the result of the comparison.
3339  else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
3340  // Compute the constant that would happen if we truncated to SrcTy then
3341  // reextended to DstTy.
3342  Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
3343  Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy);
3344 
3345  // If the re-extended constant didn't change then this is effectively
3346  // also a case of comparing two sign-extended values.
3347  if (RExt == CI && MaxRecurse)
3348  if (Value *V = SimplifyICmpInst(Pred, SrcOp, Trunc, Q, MaxRecurse-1))
3349  return V;
3350 
3351  // Otherwise the upper bits of LHS are all equal, while RHS has varying
3352  // bits there. Use this to work out the result of the comparison.
3353  if (RExt != CI) {
3354  switch (Pred) {
3355  default: llvm_unreachable("Unknown ICmp predicate!");
3356  case ICmpInst::ICMP_EQ:
3357  return ConstantInt::getFalse(CI->getContext());
3358  case ICmpInst::ICMP_NE:
3359  return ConstantInt::getTrue(CI->getContext());
3360 
3361  // If RHS is non-negative then LHS <s RHS. If RHS is negative then
3362  // LHS >s RHS.
3363  case ICmpInst::ICMP_SGT:
3364  case ICmpInst::ICMP_SGE:
3365  return CI->getValue().isNegative() ?
3366  ConstantInt::getTrue(CI->getContext()) :
3367  ConstantInt::getFalse(CI->getContext());
3368  case ICmpInst::ICMP_SLT:
3369  case ICmpInst::ICMP_SLE:
3370  return CI->getValue().isNegative() ?
3371  ConstantInt::getFalse(CI->getContext()) :
3372  ConstantInt::getTrue(CI->getContext());
3373 
3374  // If LHS is non-negative then LHS <u RHS. If LHS is negative then
3375  // LHS >u RHS.
3376  case ICmpInst::ICMP_UGT:
3377  case ICmpInst::ICMP_UGE:
3378  // Comparison is true iff the LHS <s 0.
3379  if (MaxRecurse)
3380  if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SLT, SrcOp,
3381  Constant::getNullValue(SrcTy),
3382  Q, MaxRecurse-1))
3383  return V;
3384  break;
3385  case ICmpInst::ICMP_ULT:
3386  case ICmpInst::ICMP_ULE:
3387  // Comparison is true iff the LHS >=s 0.
3388  if (MaxRecurse)
3389  if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SGE, SrcOp,
3390  Constant::getNullValue(SrcTy),
3391  Q, MaxRecurse-1))
3392  return V;
3393  break;
3394  }
3395  }
3396  }
3397  }
3398  }
3399 
3400  // icmp eq|ne X, Y -> false|true if X != Y
3401  if (ICmpInst::isEquality(Pred) &&
3402  isKnownNonEqual(LHS, RHS, Q.DL, Q.AC, Q.CxtI, Q.DT)) {
3403  return Pred == ICmpInst::ICMP_NE ? getTrue(ITy) : getFalse(ITy);
3404  }
3405 
3406  if (Value *V = simplifyICmpWithBinOp(Pred, LHS, RHS, Q, MaxRecurse))
3407  return V;
3408 
3409  if (Value *V = simplifyICmpWithMinMax(Pred, LHS, RHS, Q, MaxRecurse))
3410  return V;
3411 
3412  // Simplify comparisons of related pointers using a powerful, recursive
3413  // GEP-walk when we have target data available..
3414  if (LHS->getType()->isPointerTy())
3415  if (auto *C = computePointerICmp(Q.DL, Q.TLI, Q.DT, Pred, Q.AC, Q.CxtI, LHS,
3416  RHS))
3417  return C;
3418  if (auto *CLHS = dyn_cast<PtrToIntOperator>(LHS))
3419  if (auto *CRHS = dyn_cast<PtrToIntOperator>(RHS))
3420  if (Q.DL.getTypeSizeInBits(CLHS->getPointerOperandType()) ==
3421  Q.DL.getTypeSizeInBits(CLHS->getType()) &&
3422  Q.DL.getTypeSizeInBits(CRHS->getPointerOperandType()) ==
3423  Q.DL.getTypeSizeInBits(CRHS->getType()))
3424  if (auto *C = computePointerICmp(Q.DL, Q.TLI, Q.DT, Pred, Q.AC, Q.CxtI,
3425  CLHS->getPointerOperand(),
3426  CRHS->getPointerOperand()))
3427  return C;
3428 
3429  if (GetElementPtrInst *GLHS = dyn_cast<GetElementPtrInst>(LHS)) {
3430  if (GEPOperator *GRHS = dyn_cast<GEPOperator>(RHS)) {
3431  if (GLHS->getPointerOperand() == GRHS->getPointerOperand() &&
3432  GLHS->hasAllConstantIndices() && GRHS->hasAllConstantIndices() &&
3433  (ICmpInst::isEquality(Pred) ||
3434  (GLHS->isInBounds() && GRHS->isInBounds() &&
3435  Pred == ICmpInst::getSignedPredicate(Pred)))) {
3436  // The bases are equal and the indices are constant. Build a constant
3437  // expression GEP with the same indices and a null base pointer to see
3438  // what constant folding can make out of it.
3439  Constant *Null = Constant::getNullValue(GLHS->getPointerOperandType());
3440  SmallVector<Value *, 4> IndicesLHS(GLHS->idx_begin(), GLHS->idx_end());
3442  GLHS->getSourceElementType(), Null, IndicesLHS);
3443 
3444  SmallVector<Value *, 4> IndicesRHS(GRHS->idx_begin(), GRHS->idx_end());
3446  GLHS->getSourceElementType(), Null, IndicesRHS);
3447  return ConstantExpr::getICmp(Pred, NewLHS, NewRHS);
3448  }
3449  }
3450  }
3451 
3452  // If the comparison is with the result of a select instruction, check whether
3453  // comparing with either branch of the select always yields the same value.
3454  if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
3455  if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse))
3456  return V;
3457 
3458  // If the comparison is with the result of a phi instruction, check whether
3459  // doing the compare with each incoming phi value yields a common result.
3460  if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
3461  if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse))
3462  return V;
3463 
3464  return nullptr;
3465 }
3466 
3467 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
3468  const SimplifyQuery &Q) {
3469  return ::SimplifyICmpInst(Predicate, LHS, RHS, Q, RecursionLimit);
3470 }
3471 
3472 /// Given operands for an FCmpInst, see if we can fold the result.
3473 /// If not, this returns null.
3474 static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
3475  FastMathFlags FMF, const SimplifyQuery &Q,
3476  unsigned MaxRecurse) {
3477  CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
3478  assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
3479 
3480  if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
3481  if (Constant *CRHS = dyn_cast<Constant>(RHS))
3482  return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI);
3483 
3484  // If we have a constant, make sure it is on the RHS.
3485  std::swap(LHS, RHS);
3486  Pred = CmpInst::getSwappedPredicate(Pred);
3487  }
3488 
3489  // Fold trivial predicates.
3490  Type *RetTy = GetCompareTy(LHS);
3491  if (Pred == FCmpInst::FCMP_FALSE)
3492  return getFalse(RetTy);
3493  if (Pred == FCmpInst::FCMP_TRUE)
3494  return getTrue(RetTy);
3495 
3496  // UNO/ORD predicates can be trivially folded if NaNs are ignored.
3497  if (FMF.noNaNs()) {
3498  if (Pred == FCmpInst::FCMP_UNO)
3499  return getFalse(RetTy);
3500  if (Pred == FCmpInst::FCMP_ORD)
3501  return getTrue(RetTy);
3502  }
3503 
3504  // NaN is unordered; NaN is not ordered.
3506  "Comparison must be either ordered or unordered");
3507  if (match(RHS, m_NaN()))
3508  return ConstantInt::get(RetTy, CmpInst::isUnordered(Pred));
3509 
3510  // fcmp pred x, undef and fcmp pred undef, x
3511  // fold to true if unordered, false if ordered
3512  if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS)) {
3513  // Choosing NaN for the undef will always make unordered comparison succeed
3514  // and ordered comparison fail.
3515  return ConstantInt::get(RetTy, CmpInst::isUnordered(Pred));
3516  }
3517 
3518  // fcmp x,x -> true/false. Not all compares are foldable.
3519  if (LHS == RHS) {
3520  if (CmpInst::isTrueWhenEqual(Pred))
3521  return getTrue(RetTy);
3522  if (CmpInst::isFalseWhenEqual(Pred))
3523  return getFalse(RetTy);
3524  }
3525 
3526  // Handle fcmp with constant RHS.
3527  const APFloat *C;
3528  if (match(RHS, m_APFloat(C))) {
3529  // Check whether the constant is an infinity.
3530  if (C->isInfinity()) {
3531  if (C->isNegative()) {
3532  switch (Pred) {
3533  case FCmpInst::FCMP_OLT:
3534  // No value is ordered and less than negative infinity.
3535  return getFalse(RetTy);
3536  case FCmpInst::FCMP_UGE:
3537  // All values are unordered with or at least negative infinity.
3538  return getTrue(RetTy);
3539  default:
3540  break;
3541  }
3542  } else {
3543  switch (Pred) {
3544  case FCmpInst::FCMP_OGT:
3545  // No value is ordered and greater than infinity.
3546  return getFalse(RetTy);
3547  case FCmpInst::FCMP_ULE:
3548  // All values are unordered with and at most infinity.
3549  return getTrue(RetTy);
3550  default:
3551  break;
3552  }
3553  }
3554  }
3555  if (C->isZero()) {
3556  switch (Pred) {
3557  case FCmpInst::FCMP_UGE:
3558  if (CannotBeOrderedLessThanZero(LHS, Q.TLI))
3559  return getTrue(RetTy);
3560  break;
3561  case FCmpInst::FCMP_OLT:
3562  // X < 0
3563  if (CannotBeOrderedLessThanZero(LHS, Q.TLI))
3564  return getFalse(RetTy);
3565  break;
3566  default:
3567  break;
3568  }
3569  } else if (C->isNegative()) {
3570  assert(!C->isNaN() && "Unexpected NaN constant!");
3571  // TODO: We can catch more cases by using a range check rather than
3572  // relying on CannotBeOrderedLessThanZero.
3573  switch (Pred) {
3574  case FCmpInst::FCMP_UGE:
3575  case FCmpInst::FCMP_UGT:
3576  case FCmpInst::FCMP_UNE:
3577  // (X >= 0) implies (X > C) when (C < 0)
3578  if (CannotBeOrderedLessThanZero(LHS, Q.TLI))
3579  return getTrue(RetTy);
3580  break;
3581  case FCmpInst::FCMP_OEQ:
3582  case FCmpInst::FCMP_OLE:
3583  case FCmpInst::FCMP_OLT:
3584  // (X >= 0) implies !(X < C) when (C < 0)
3585  if (CannotBeOrderedLessThanZero(LHS, Q.TLI))
3586  return getFalse(RetTy);
3587  break;
3588  default:
3589  break;
3590  }
3591  }
3592  }
3593 
3594  // If the comparison is with the result of a select instruction, check whether
3595  // comparing with either branch of the select always yields the same value.
3596  if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
3597  if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse))
3598  return V;
3599 
3600  // If the comparison is with the result of a phi instruction, check whether
3601  // doing the compare with each incoming phi value yields a common result.
3602  if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
3603  if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse))
3604  return V;
3605 
3606  return nullptr;
3607 }
3608 
3609 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
3610  FastMathFlags FMF, const SimplifyQuery &Q) {
3611  return ::SimplifyFCmpInst(Predicate, LHS, RHS, FMF, Q, RecursionLimit);
3612 }
3613 
3614 /// See if V simplifies when its operand Op is replaced with RepOp.
3615 static const Value *SimplifyWithOpReplaced(Value *V, Value *Op, Value *RepOp,
3616  const SimplifyQuery &Q,
3617  unsigned MaxRecurse) {
3618  // Trivial replacement.
3619  if (V == Op)
3620  return RepOp;
3621 
3622  // We cannot replace a constant, and shouldn't even try.
3623  if (isa<Constant>(Op))
3624  return nullptr;
3625 
3626  auto *I = dyn_cast<Instruction>(V);
3627  if (!I)
3628  return nullptr;
3629 
3630  // If this is a binary operator, try to simplify it with the replaced op.
3631  if (auto *B = dyn_cast<BinaryOperator>(I)) {
3632  // Consider:
3633  // %cmp = icmp eq i32 %x, 2147483647
3634  // %add = add nsw i32 %x, 1
3635  // %sel = select i1 %cmp, i32 -2147483648, i32 %add
3636  //
3637  // We can't replace %sel with %add unless we strip away the flags.
3638  if (isa<OverflowingBinaryOperator>(B))
3639  if (B->hasNoSignedWrap() || B->hasNoUnsignedWrap())
3640  return nullptr;
3641  if (isa<PossiblyExactOperator>(B))
3642  if (B->isExact())
3643  return nullptr;
3644 
3645  if (MaxRecurse) {
3646  if (B->getOperand(0) == Op)
3647  return SimplifyBinOp(B->getOpcode(), RepOp, B->getOperand(1), Q,
3648  MaxRecurse - 1);
3649  if (B->getOperand(1) == Op)
3650  return SimplifyBinOp(B->getOpcode(), B->getOperand(0), RepOp, Q,
3651  MaxRecurse - 1);
3652  }
3653  }
3654 
3655  // Same for CmpInsts.
3656  if (CmpInst *C = dyn_cast<CmpInst>(I)) {
3657  if (MaxRecurse) {
3658  if (C->getOperand(0) == Op)
3659  return SimplifyCmpInst(C->getPredicate(), RepOp, C->getOperand(1), Q,
3660  MaxRecurse - 1);
3661  if (C->getOperand(1) == Op)
3662  return SimplifyCmpInst(C->getPredicate(), C->getOperand(0), RepOp, Q,
3663  MaxRecurse - 1);
3664  }
3665  }
3666 
3667  // Same for GEPs.
3668  if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
3669  if (MaxRecurse) {
3670  SmallVector<Value *, 8> NewOps(GEP->getNumOperands());
3671  transform(GEP->operands(), NewOps.begin(),
3672  [&](Value *V) { return V == Op ? RepOp : V; });
3673  return SimplifyGEPInst(GEP->getSourceElementType(), NewOps, Q,
3674  MaxRecurse - 1);
3675  }
3676  }
3677 
3678  // TODO: We could hand off more cases to instsimplify here.
3679 
3680  // If all operands are constant after substituting Op for RepOp then we can
3681  // constant fold the instruction.
3682  if (Constant *CRepOp = dyn_cast<Constant>(RepOp)) {
3683  // Build a list of all constant operands.
3684  SmallVector<Constant *, 8> ConstOps;
3685  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
3686  if (I->getOperand(i) == Op)
3687  ConstOps.push_back(CRepOp);
3688  else if (Constant *COp = dyn_cast<Constant>(I->getOperand(i)))
3689  ConstOps.push_back(COp);
3690  else
3691  break;
3692  }
3693 
3694  // All operands were constants, fold it.
3695  if (ConstOps.size() == I->getNumOperands()) {
3696  if (CmpInst *C = dyn_cast<CmpInst>(I))
3697  return ConstantFoldCompareInstOperands(C->getPredicate(), ConstOps[0],
3698  ConstOps[1], Q.DL, Q.TLI);
3699 
3700  if (LoadInst *LI = dyn_cast<LoadInst>(I))
3701  if (!LI->isVolatile())
3702  return ConstantFoldLoadFromConstPtr(ConstOps[0], LI->getType(), Q.DL);
3703 
3704  return ConstantFoldInstOperands(I, ConstOps, Q.DL, Q.TLI);
3705  }
3706  }
3707 
3708  return nullptr;
3709 }
3710 
3711 /// Try to simplify a select instruction when its condition operand is an
3712 /// integer comparison where one operand of the compare is a constant.
3713 static Value *simplifySelectBitTest(Value *TrueVal, Value *FalseVal, Value *X,
3714  const APInt *Y, bool TrueWhenUnset) {
3715  const APInt *C;
3716 
3717  // (X & Y) == 0 ? X & ~Y : X --> X
3718  // (X & Y) != 0 ? X & ~Y : X --> X & ~Y
3719  if (FalseVal == X && match(TrueVal, m_And(m_Specific(X), m_APInt(C))) &&
3720  *Y == ~*C)
3721  return TrueWhenUnset ? FalseVal : TrueVal;
3722 
3723  // (X & Y) == 0 ? X : X & ~Y --> X & ~Y
3724  // (X & Y) != 0 ? X : X & ~Y --> X
3725  if (TrueVal == X && match(FalseVal, m_And(m_Specific(X), m_APInt(C))) &&
3726  *Y == ~*C)
3727  return TrueWhenUnset ? FalseVal : TrueVal;
3728 
3729  if (Y->isPowerOf2()) {
3730  // (X & Y) == 0 ? X | Y : X --> X | Y
3731  // (X & Y) != 0 ? X | Y : X --> X
3732  if (FalseVal == X && match(TrueVal, m_Or(m_Specific(X), m_APInt(C))) &&
3733  *Y == *C)
3734  return TrueWhenUnset ? TrueVal : FalseVal;
3735 
3736  // (X & Y) == 0 ? X : X | Y --> X
3737  // (X & Y) != 0 ? X : X | Y --> X | Y
3738  if (TrueVal == X && match(FalseVal, m_Or(m_Specific(X), m_APInt(C))) &&
3739  *Y == *C)
3740  return TrueWhenUnset ? TrueVal : FalseVal;
3741  }
3742 
3743  return nullptr;
3744 }
3745 
3746 /// An alternative way to test if a bit is set or not uses sgt/slt instead of
3747 /// eq/ne.
3749  ICmpInst::Predicate Pred,
3750  Value *TrueVal, Value *FalseVal) {
3751  Value *X;
3752  APInt Mask;
3753  if (!decomposeBitTestICmp(CmpLHS, CmpRHS, Pred, X, Mask))
3754  return nullptr;
3755 
3756  return simplifySelectBitTest(TrueVal, FalseVal, X, &Mask,
3757  Pred == ICmpInst::ICMP_EQ);
3758 }
3759 
3760 /// Try to simplify a select instruction when its condition operand is an
3761 /// integer comparison.
3762 static Value *simplifySelectWithICmpCond(Value *CondVal, Value *TrueVal,
3763  Value *FalseVal, const SimplifyQuery &Q,
3764  unsigned MaxRecurse) {
3765  ICmpInst::Predicate Pred;
3766  Value *CmpLHS, *CmpRHS;
3767  if (!match(CondVal, m_ICmp(Pred, m_Value(CmpLHS), m_Value(CmpRHS))))
3768  return nullptr;
3769 
3770  if (ICmpInst::isEquality(Pred) && match(CmpRHS, m_Zero())) {
3771  Value *X;
3772  const APInt *Y;
3773  if (match(CmpLHS, m_And(m_Value(X), m_APInt(Y))))
3774  if (Value *V = simplifySelectBitTest(TrueVal, FalseVal, X, Y,
3775  Pred == ICmpInst::ICMP_EQ))
3776  return V;
3777  }
3778 
3779  // Check for other compares that behave like bit test.
3780  if (Value *V = simplifySelectWithFakeICmpEq(CmpLHS, CmpRHS, Pred,
3781  TrueVal, FalseVal))
3782  return V;
3783 
3784  // If we have an equality comparison, then we know the value in one of the
3785  // arms of the select. See if substituting this value into the arm and
3786  // simplifying the result yields the same value as the other arm.
3787  if (Pred == ICmpInst::ICMP_EQ) {
3788  if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
3789  TrueVal ||
3790  SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
3791  TrueVal)
3792  return FalseVal;
3793  if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
3794  FalseVal ||
3795  SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
3796  FalseVal)
3797  return FalseVal;
3798  } else if (Pred == ICmpInst::ICMP_NE) {
3799  if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
3800  FalseVal ||
3801  SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
3802  FalseVal)
3803  return TrueVal;
3804  if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
3805  TrueVal ||
3806  SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
3807  TrueVal)
3808  return TrueVal;
3809  }
3810 
3811  return nullptr;
3812 }
3813 
3814 /// Given operands for a SelectInst, see if we can fold the result.
3815 /// If not, this returns null.
3816 static Value *SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
3817  const SimplifyQuery &Q, unsigned MaxRecurse) {
3818  if (auto *CondC = dyn_cast<Constant>(Cond)) {
3819  if (auto *TrueC = dyn_cast<Constant>(TrueVal))
3820  if (auto *FalseC = dyn_cast<Constant>(FalseVal))
3821  return ConstantFoldSelectInstruction(CondC, TrueC, FalseC);
3822 
3823  // select undef, X, Y -> X or Y
3824  if (isa<UndefValue>(CondC))
3825  return isa<Constant>(FalseVal) ? FalseVal : TrueVal;
3826 
3827  // TODO: Vector constants with undef elements don't simplify.
3828 
3829  // select true, X, Y -> X
3830  if (CondC->isAllOnesValue())
3831  return TrueVal;
3832  // select false, X, Y -> Y
3833  if (CondC->isNullValue())
3834  return FalseVal;
3835  }
3836 
3837  // select ?, X, X -> X
3838  if (TrueVal == FalseVal)
3839  return TrueVal;
3840 
3841  if (isa<UndefValue>(TrueVal)) // select ?, undef, X -> X
3842  return FalseVal;
3843  if (isa<UndefValue>(FalseVal)) // select ?, X, undef -> X
3844  return TrueVal;
3845 
3846  if (Value *V =
3847  simplifySelectWithICmpCond(Cond, TrueVal, FalseVal, Q, MaxRecurse))
3848  return V;
3849 
3850  if (Value *V = foldSelectWithBinaryOp(Cond, TrueVal, FalseVal))
3851  return V;
3852 
3853  return nullptr;
3854 }
3855 
3856 Value *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
3857  const SimplifyQuery &Q) {
3858  return ::SimplifySelectInst(Cond, TrueVal, FalseVal, Q, RecursionLimit);
3859 }
3860 
3861 /// Given operands for an GetElementPtrInst, see if we can fold the result.
3862 /// If not, this returns null.
3864  const SimplifyQuery &Q, unsigned) {
3865  // The type of the GEP pointer operand.
3866  unsigned AS =
3867  cast<PointerType>(Ops[0]->getType()->getScalarType())->getAddressSpace();
3868 
3869  // getelementptr P -> P.
3870  if (Ops.size() == 1)
3871  return Ops[0];
3872 
3873  // Compute the (pointer) type returned by the GEP instruction.
3874  Type *LastType = GetElementPtrInst::getIndexedType(SrcTy, Ops.slice(1));
3875  Type *GEPTy = PointerType::get(LastType, AS);
3876  if (VectorType *VT = dyn_cast<VectorType>(Ops[0]->getType()))
3877  GEPTy = VectorType::get(GEPTy, VT->getNumElements());
3878  else if (VectorType *VT = dyn_cast<VectorType>(Ops[1]->getType()))
3879  GEPTy = VectorType::get(GEPTy, VT->getNumElements());
3880 
3881  if (isa<UndefValue>(Ops[0]))
3882  return UndefValue::get(GEPTy);
3883 
3884  if (Ops.size() == 2) {
3885  // getelementptr P, 0 -> P.
3886  if (match(Ops[1], m_Zero()) && Ops[0]->getType() == GEPTy)
3887  return Ops[0];
3888 
3889  Type *Ty = SrcTy;
3890  if (Ty->isSized()) {
3891  Value *P;
3892  uint64_t C;
3893  uint64_t TyAllocSize = Q.DL.getTypeAllocSize(Ty);
3894  // getelementptr P, N -> P if P points to a type of zero size.
3895  if (TyAllocSize == 0 && Ops[0]->getType() == GEPTy)
3896  return Ops[0];
3897 
3898  // The following transforms are only safe if the ptrtoint cast
3899  // doesn't truncate the pointers.
3900  if (Ops[1]->getType()->getScalarSizeInBits() ==
3901  Q.DL.getIndexSizeInBits(AS)) {
3902  auto PtrToIntOrZero = [GEPTy](Value *P) -> Value * {
3903  if (match(P, m_Zero()))
3904  return Constant::getNullValue(GEPTy);
3905  Value *Temp;
3906  if (match(P, m_PtrToInt(m_Value(Temp))))
3907  if (Temp->getType() == GEPTy)
3908  return Temp;
3909  return nullptr;
3910  };
3911 
3912  // getelementptr V, (sub P, V) -> P if P points to a type of size 1.
3913  if (TyAllocSize == 1 &&
3914  match(Ops[1], m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0])))))
3915  if (Value *R = PtrToIntOrZero(P))
3916  return R;
3917 
3918  // getelementptr V, (ashr (sub P, V), C) -> Q
3919  // if P points to a type of size 1 << C.
3920  if (match(Ops[1],
3921  m_AShr(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))),
3922  m_ConstantInt(C))) &&
3923  TyAllocSize == 1ULL << C)
3924  if (Value *R = PtrToIntOrZero(P))
3925  return R;
3926 
3927  // getelementptr V, (sdiv (sub P, V), C) -> Q
3928  // if P points to a type of size C.
3929  if (match(Ops[1],
3930  m_SDiv(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))),
3931  m_SpecificInt(TyAllocSize))))
3932  if (Value *R = PtrToIntOrZero(P))
3933  return R;
3934  }
3935  }
3936  }
3937 
3938  if (Q.DL.getTypeAllocSize(LastType) == 1 &&
3939  all_of(Ops.slice(1).drop_back(1),
3940  [](Value *Idx) { return match(Idx, m_Zero()); })) {
3941  unsigned IdxWidth =
3942  Q.DL.getIndexSizeInBits(Ops[0]->getType()->getPointerAddressSpace());
3943  if (Q.DL.getTypeSizeInBits(Ops.back()->getType()) == IdxWidth) {
3944  APInt BasePtrOffset(IdxWidth, 0);
3945  Value *StrippedBasePtr =
3946  Ops[0]->stripAndAccumulateInBoundsConstantOffsets(Q.DL,
3947  BasePtrOffset);
3948 
3949  // gep (gep V, C), (sub 0, V) -> C
3950  if (match(Ops.back(),
3951  m_Sub(m_Zero(), m_PtrToInt(m_Specific(StrippedBasePtr))))) {
3952  auto *CI = ConstantInt::get(GEPTy->getContext(), BasePtrOffset);
3953  return ConstantExpr::getIntToPtr(CI, GEPTy);
3954  }
3955  // gep (gep V, C), (xor V, -1) -> C-1
3956  if (match(Ops.back(),
3957  m_Xor(m_PtrToInt(m_Specific(StrippedBasePtr)), m_AllOnes()))) {
3958  auto *CI = ConstantInt::get(GEPTy->getContext(), BasePtrOffset - 1);
3959  return ConstantExpr::getIntToPtr(CI, GEPTy);
3960  }
3961  }
3962  }
3963 
3964  // Check to see if this is constant foldable.
3965  if (!all_of(Ops, [](Value *V) { return isa<Constant>(V); }))
3966  return nullptr;
3967 
3968  auto *CE = ConstantExpr::getGetElementPtr(SrcTy, cast<Constant>(Ops[0]),
3969  Ops.slice(1));
3970  if (auto *CEFolded = ConstantFoldConstant(CE, Q.DL))
3971  return CEFolded;
3972  return CE;
3973 }
3974 
3976  const SimplifyQuery &Q) {
3977  return ::SimplifyGEPInst(SrcTy, Ops, Q, RecursionLimit);
3978 }
3979 
3980 /// Given operands for an InsertValueInst, see if we can fold the result.
3981 /// If not, this returns null.
3983  ArrayRef<unsigned> Idxs, const SimplifyQuery &Q,
3984  unsigned) {
3985  if (Constant *CAgg = dyn_cast<Constant>(Agg))
3986  if (Constant *CVal = dyn_cast<Constant>(Val))
3987  return ConstantFoldInsertValueInstruction(CAgg, CVal, Idxs);
3988 
3989  // insertvalue x, undef, n -> x
3990  if (match(Val, m_Undef()))
3991  return Agg;
3992 
3993  // insertvalue x, (extractvalue y, n), n
3994  if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Val))
3995  if (EV->getAggregateOperand()->getType() == Agg->getType() &&
3996  EV->getIndices() == Idxs) {
3997  // insertvalue undef, (extractvalue y, n), n -> y
3998  if (match(Agg, m_Undef()))
3999  return EV->getAggregateOperand();
4000 
4001  // insertvalue y, (extractvalue y, n), n -> y
4002  if (Agg == EV->getAggregateOperand())
4003  return Agg;
4004  }
4005 
4006  return nullptr;
4007 }
4008 
4010  ArrayRef<unsigned> Idxs,
4011  const SimplifyQuery &Q) {
4013 }
4014 
4016  const SimplifyQuery &Q) {
4017  // Try to constant fold.
4018  auto *VecC = dyn_cast<Constant>(Vec);
4019  auto *ValC = dyn_cast<Constant>(Val);
4020  auto *IdxC = dyn_cast<Constant>(Idx);
4021  if (VecC && ValC && IdxC)
4022  return ConstantFoldInsertElementInstruction(VecC, ValC, IdxC);
4023 
4024  // Fold into undef if index is out of bounds.
4025  if (auto *CI = dyn_cast<ConstantInt>(Idx)) {
4026  uint64_t NumElements = cast<VectorType>(Vec->getType())->getNumElements();
4027  if (CI->uge(NumElements))
4028  return UndefValue::get(Vec->getType());
4029  }
4030 
4031  // If index is undef, it might be out of bounds (see above case)
4032  if (isa<UndefValue>(Idx))
4033  return UndefValue::get(Vec->getType());
4034 
4035  return nullptr;
4036 }
4037 
4038 /// Given operands for an ExtractValueInst, see if we can fold the result.
4039 /// If not, this returns null.
4041  const SimplifyQuery &, unsigned) {
4042  if (auto *CAgg = dyn_cast<Constant>(Agg))
4043  return ConstantFoldExtractValueInstruction(CAgg, Idxs);
4044 
4045  // extractvalue x, (insertvalue y, elt, n), n -> elt
4046  unsigned NumIdxs = Idxs.size();
4047  for (auto *IVI = dyn_cast<InsertValueInst>(Agg); IVI != nullptr;
4048  IVI = dyn_cast<InsertValueInst>(IVI->getAggregateOperand())) {
4049  ArrayRef<unsigned> InsertValueIdxs = IVI->getIndices();
4050  unsigned NumInsertValueIdxs = InsertValueIdxs.size();
4051  unsigned NumCommonIdxs = std::min(NumInsertValueIdxs, NumIdxs);
4052  if (InsertValueIdxs.slice(0, NumCommonIdxs) ==
4053  Idxs.slice(0, NumCommonIdxs)) {
4054  if (NumIdxs == NumInsertValueIdxs)
4055  return IVI->getInsertedValueOperand();
4056  break;
4057  }
4058  }
4059 
4060  return nullptr;
4061 }
4062 
4064  const SimplifyQuery &Q) {
4066 }
4067 
4068 /// Given operands for an ExtractElementInst, see if we can fold the result.
4069 /// If not, this returns null.
4071  unsigned) {
4072  if (auto *CVec = dyn_cast<Constant>(Vec)) {
4073  if (auto *CIdx = dyn_cast<Constant>(Idx))
4074  return ConstantFoldExtractElementInstruction(CVec, CIdx);
4075 
4076  // The index is not relevant if our vector is a splat.
4077  if (auto *Splat = CVec->getSplatValue())
4078  return Splat;
4079 
4080  if (isa<UndefValue>(Vec))
4081  return UndefValue::get(Vec->getType()->getVectorElementType());
4082  }
4083 
4084  // If extracting a specified index from the vector, see if we can recursively
4085  // find a previously computed scalar that was inserted into the vector.
4086  if (auto *IdxC = dyn_cast<ConstantInt>(Idx)) {
4087  if (IdxC->getValue().uge(Vec->getType()->getVectorNumElements()))
4088  // definitely out of bounds, thus undefined result
4089  return UndefValue::get(Vec->getType()->getVectorElementType());
4090  if (Value *Elt = findScalarElement(Vec, IdxC->getZExtValue()))
4091  return Elt;
4092  }
4093 
4094  // An undef extract index can be arbitrarily chosen to be an out-of-range
4095  // index value, which would result in the instruction being undef.
4096  if (isa<UndefValue>(Idx))
4097  return UndefValue::get(Vec->getType()->getVectorElementType());
4098 
4099  return nullptr;
4100 }
4101 
4103  const SimplifyQuery &Q) {
4105 }
4106 
4107 /// See if we can fold the given phi. If not, returns null.
4108 static Value *SimplifyPHINode(PHINode *PN, const SimplifyQuery &Q) {
4109  // If all of the PHI's incoming values are the same then replace the PHI node
4110  // with the common value.
4111  Value *CommonValue = nullptr;
4112  bool HasUndefInput = false;
4113  for (Value *Incoming : PN->incoming_values()) {
4114  // If the incoming value is the phi node itself, it can safely be skipped.
4115  if (Incoming == PN) continue;
4116  if (isa<UndefValue>(Incoming)) {
4117  // Remember that we saw an undef value, but otherwise ignore them.
4118  HasUndefInput = true;
4119  continue;
4120  }
4121  if (CommonValue && Incoming != CommonValue)
4122  return nullptr; // Not the same, bail out.
4123  CommonValue = Incoming;
4124  }
4125 
4126  // If CommonValue is null then all of the incoming values were either undef or
4127  // equal to the phi node itself.
4128  if (!CommonValue)
4129  return UndefValue::get(PN->getType());
4130 
4131  // If we have a PHI node like phi(X, undef, X), where X is defined by some
4132  // instruction, we cannot return X as the result of the PHI node unless it
4133  // dominates the PHI block.
4134  if (HasUndefInput)
4135  return valueDominatesPHI(CommonValue, PN, Q.DT) ? CommonValue : nullptr;
4136 
4137  return CommonValue;
4138 }
4139 
4140 static Value *SimplifyCastInst(unsigned CastOpc, Value *Op,
4141  Type *Ty, const SimplifyQuery &Q, unsigned MaxRecurse) {
4142  if (auto *C = dyn_cast<Constant>(Op))
4143  return ConstantFoldCastOperand(CastOpc, C, Ty, Q.DL);
4144 
4145  if (auto *CI = dyn_cast<CastInst>(Op)) {
4146  auto *Src = CI->getOperand(0);
4147  Type *SrcTy = Src->getType();
4148  Type *MidTy = CI->getType();
4149  Type *DstTy = Ty;
4150  if (Src->getType() == Ty) {
4151  auto FirstOp = static_cast<Instruction::CastOps>(CI->getOpcode());
4152  auto SecondOp = static_cast<Instruction::CastOps>(CastOpc);
4153  Type *SrcIntPtrTy =
4154  SrcTy->isPtrOrPtrVectorTy() ? Q.DL.getIntPtrType(SrcTy) : nullptr;
4155  Type *MidIntPtrTy =
4156  MidTy->isPtrOrPtrVectorTy() ? Q.DL.getIntPtrType(MidTy) : nullptr;
4157  Type *DstIntPtrTy =
4158  DstTy->isPtrOrPtrVectorTy() ? Q.DL.getIntPtrType(DstTy) : nullptr;
4159  if (CastInst::isEliminableCastPair(FirstOp, SecondOp, SrcTy, MidTy, DstTy,
4160  SrcIntPtrTy, MidIntPtrTy,
4161  DstIntPtrTy) == Instruction::BitCast)
4162  return Src;
4163  }
4164  }
4165 
4166  // bitcast x -> x
4167  if (CastOpc == Instruction::BitCast)
4168  if (Op->getType() == Ty)
4169  return Op;
4170 
4171  return nullptr;
4172 }
4173 
4174 Value *llvm::SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty,
4175  const SimplifyQuery &Q) {
4176  return ::SimplifyCastInst(CastOpc, Op, Ty, Q, RecursionLimit);
4177 }
4178 
4179 /// For the given destination element of a shuffle, peek through shuffles to
4180 /// match a root vector source operand that contains that element in the same
4181 /// vector lane (ie, the same mask index), so we can eliminate the shuffle(s).
4182 static Value *foldIdentityShuffles(int DestElt, Value *Op0, Value *Op1,
4183  int MaskVal, Value *RootVec,
4184  unsigned MaxRecurse) {
4185  if (!MaxRecurse--)
4186  return nullptr;
4187 
4188  // Bail out if any mask value is undefined. That kind of shuffle may be
4189  // simplified further based on demanded bits or other folds.
4190  if (MaskVal == -1)
4191  return nullptr;
4192 
4193  // The mask value chooses which source operand we need to look at next.
4194  int InVecNumElts = Op0->getType()->getVectorNumElements();
4195  int RootElt = MaskVal;
4196  Value *SourceOp = Op0;
4197  if (MaskVal >= InVecNumElts) {
4198  RootElt = MaskVal - InVecNumElts;
4199  SourceOp = Op1;
4200  }
4201 
4202  // If the source operand is a shuffle itself, look through it to find the
4203  // matching root vector.
4204  if (auto *SourceShuf = dyn_cast<ShuffleVectorInst>(SourceOp)) {
4205  return foldIdentityShuffles(
4206  DestElt, SourceShuf->getOperand(0), SourceShuf->getOperand(1),
4207  SourceShuf->getMaskValue(RootElt), RootVec, MaxRecurse);
4208  }
4209 
4210  // TODO: Look through bitcasts? What if the bitcast changes the vector element
4211  // size?
4212 
4213  // The source operand is not a shuffle. Initialize the root vector value for
4214  // this shuffle if that has not been done yet.
4215  if (!RootVec)
4216  RootVec = SourceOp;
4217 
4218  // Give up as soon as a source operand does not match the existing root value.
4219  if (RootVec != SourceOp)
4220  return nullptr;
4221 
4222  // The element must be coming from the same lane in the source vector
4223  // (although it may have crossed lanes in intermediate shuffles).
4224  if (RootElt != DestElt)
4225  return nullptr;
4226 
4227  return RootVec;
4228 }
4229 
4231  Type *RetTy, const SimplifyQuery &Q,
4232  unsigned MaxRecurse) {
4233  if (isa<UndefValue>(Mask))
4234  return UndefValue::get(RetTy);
4235 
4236  Type *InVecTy = Op0->getType();
4237  unsigned MaskNumElts = Mask->getType()->getVectorNumElements();
4238  unsigned InVecNumElts = InVecTy->getVectorNumElements();
4239 
4240  SmallVector<int, 32> Indices;
4241  ShuffleVectorInst::getShuffleMask(Mask, Indices);
4242  assert(MaskNumElts == Indices.size() &&
4243  "Size of Indices not same as number of mask elements?");
4244 
4245  // Canonicalization: If mask does not select elements from an input vector,
4246  // replace that input vector with undef.
4247  bool MaskSelects0 = false, MaskSelects1 = false;
4248  for (unsigned i = 0; i != MaskNumElts; ++i) {
4249  if (Indices[i] == -1)
4250  continue;
4251  if ((unsigned)Indices[i] < InVecNumElts)
4252  MaskSelects0 = true;
4253  else
4254  MaskSelects1 = true;
4255  }
4256  if (!MaskSelects0)
4257  Op0 = UndefValue::get(InVecTy);
4258  if (!MaskSelects1)
4259  Op1 = UndefValue::get(InVecTy);
4260 
4261  auto *Op0Const = dyn_cast<Constant>(Op0);
4262  auto *Op1Const = dyn_cast<Constant>(Op1);
4263 
4264  // If all operands are constant, constant fold the shuffle.
4265  if (Op0Const && Op1Const)
4266  return ConstantFoldShuffleVectorInstruction(Op0Const, Op1Const, Mask);
4267 
4268  // Canonicalization: if only one input vector is constant, it shall be the
4269  // second one.
4270  if (Op0Const && !Op1Const) {
4271  std::swap(Op0, Op1);
4272  ShuffleVectorInst::commuteShuffleMask(Indices, InVecNumElts);
4273  }
4274 
4275  // A shuffle of a splat is always the splat itself. Legal if the shuffle's
4276  // value type is same as the input vectors' type.
4277  if (auto *OpShuf = dyn_cast<ShuffleVectorInst>(Op0))
4278  if (isa<UndefValue>(Op1) && RetTy == InVecTy &&
4279  OpShuf->getMask()->getSplatValue())
4280  return Op0;
4281 
4282  // Don't fold a shuffle with undef mask elements. This may get folded in a
4283  // better way using demanded bits or other analysis.
4284  // TODO: Should we allow this?
4285  if (find(Indices, -1) != Indices.end())
4286  return nullptr;
4287 
4288  // Check if every element of this shuffle can be mapped back to the
4289  // corresponding element of a single root vector. If so, we don't need this
4290  // shuffle. This handles simple identity shuffles as well as chains of
4291  // shuffles that may widen/narrow and/or move elements across lanes and back.
4292  Value *RootVec = nullptr;
4293  for (unsigned i = 0; i != MaskNumElts; ++i) {
4294  // Note that recursion is limited for each vector element, so if any element
4295  // exceeds the limit, this will fail to simplify.
4296  RootVec =
4297  foldIdentityShuffles(i, Op0, Op1, Indices[i], RootVec, MaxRecurse);
4298 
4299  // We can't replace a widening/narrowing shuffle with one of its operands.
4300  if (!RootVec || RootVec->getType() != RetTy)
4301  return nullptr;
4302  }
4303  return RootVec;
4304 }
4305 
4306 /// Given operands for a ShuffleVectorInst, fold the result or return null.
4308  Type *RetTy, const SimplifyQuery &Q) {
4309  return ::SimplifyShuffleVectorInst(Op0, Op1, Mask, RetTy, Q, RecursionLimit);
4310 }
4311 
4313  // If the input is a vector with undef elements, just return a default NaN.
4314  if (!In->isNaN())
4315  return ConstantFP::getNaN(In->getType());
4316 
4317  // Propagate the existing NaN constant when possible.
4318  // TODO: Should we quiet a signaling NaN?
4319  return In;
4320 }
4321 
4322 static Constant *simplifyFPBinop(Value *Op0, Value *Op1) {
4323  if (isa<UndefValue>(Op0) || isa<UndefValue>(Op1))
4324  return ConstantFP::getNaN(Op0->getType());
4325 
4326  if (match(Op0, m_NaN()))
4327  return propagateNaN(cast<Constant>(Op0));
4328  if (match(Op1, m_NaN()))
4329  return propagateNaN(cast<Constant>(Op1));
4330 
4331  return nullptr;
4332 }
4333 
4334 /// Given operands for an FAdd, see if we can fold the result. If not, this
4335 /// returns null.
4337  const SimplifyQuery &Q, unsigned MaxRecurse) {
4338  if (Constant *C = foldOrCommuteConstant(Instruction::FAdd, Op0, Op1, Q))
4339  return C;
4340 
4341  if (Constant *C = simplifyFPBinop(Op0, Op1))
4342  return C;
4343 
4344  // fadd X, -0 ==> X
4345  if (match(Op1, m_NegZeroFP()))
4346  return Op0;
4347 
4348  // fadd X, 0 ==> X, when we know X is not -0
4349  if (match(Op1, m_PosZeroFP()) &&
4350  (FMF.noSignedZeros() || CannotBeNegativeZero(Op0, Q.TLI)))
4351  return Op0;
4352 
4353  // With nnan: (+/-0.0 - X) + X --> 0.0 (and commuted variant)
4354  // We don't have to explicitly exclude infinities (ninf): INF + -INF == NaN.
4355  // Negative zeros are allowed because we always end up with positive zero:
4356  // X = -0.0: (-0.0 - (-0.0)) + (-0.0) == ( 0.0) + (-0.0) == 0.0
4357  // X = -0.0: ( 0.0 - (-0.0)) + (-0.0) == ( 0.0) + (-0.0) == 0.0
4358  // X = 0.0: (-0.0 - ( 0.0)) + ( 0.0) == (-0.0) + ( 0.0) == 0.0
4359  // X = 0.0: ( 0.0 - ( 0.0)) + ( 0.0) == ( 0.0) + ( 0.0) == 0.0
4360  if (FMF.noNaNs() && (match(Op0, m_FSub(m_AnyZeroFP(), m_Specific(Op1))) ||
4361  match(Op1, m_FSub(m_AnyZeroFP(), m_Specific(Op0)))))
4362  return ConstantFP::getNullValue(Op0->getType());
4363 
4364  // (X - Y) + Y --> X
4365  // Y + (X - Y) --> X
4366  Value *X;
4367  if (FMF.noSignedZeros() && FMF.allowReassoc() &&
4368  (match(Op0, m_FSub(m_Value(X), m_Specific(Op1))) ||
4369  match(Op1, m_FSub(m_Value(X), m_Specific(Op0)))))
4370  return X;
4371 
4372  return nullptr;
4373 }
4374 
4375 /// Given operands for an FSub, see if we can fold the result. If not, this
4376 /// returns null.
4378  const SimplifyQuery &Q, unsigned MaxRecurse) {
4379  if (Constant *C = foldOrCommuteConstant(Instruction::FSub, Op0, Op1, Q))
4380  return C;
4381 
4382  if (Constant *C = simplifyFPBinop(Op0, Op1))
4383  return C;
4384 
4385  // fsub X, +0 ==> X
4386  if (match(Op1, m_PosZeroFP()))
4387  return Op0;
4388 
4389  // fsub X, -0 ==> X, when we know X is not -0
4390  if (match(Op1, m_NegZeroFP()) &&
4391  (FMF.noSignedZeros() || CannotBeNegativeZero(Op0, Q.TLI)))
4392  return Op0;
4393 
4394  // fsub -0.0, (fsub -0.0, X) ==> X
4395  Value *X;
4396  if (match(Op0, m_NegZeroFP()) &&
4397  match(Op1, m_FSub(m_NegZeroFP(), m_Value(X))))
4398  return X;
4399 
4400  // fsub 0.0, (fsub 0.0, X) ==> X if signed zeros are ignored.
4401  if (FMF.noSignedZeros() && match(Op0, m_AnyZeroFP()) &&
4402  match(Op1, m_FSub(m_AnyZeroFP(), m_Value(X))))
4403  return X;
4404 
4405  // fsub nnan x, x ==> 0.0
4406  if (FMF.noNaNs() && Op0 == Op1)
4407  return Constant::getNullValue(Op0->getType());
4408 
4409  // Y - (Y - X) --> X
4410  // (X + Y) - Y --> X
4411  if (FMF.noSignedZeros() && FMF.allowReassoc() &&
4412  (match(Op1, m_FSub(m_Specific(Op0), m_Value(X))) ||
4413  match(Op0, m_c_FAdd(m_Specific(Op1), m_Value(X)))))
4414  return X;
4415 
4416  return nullptr;
4417 }
4418 
4419 /// Given the operands for an FMul, see if we can fold the result
4421  const SimplifyQuery &Q, unsigned MaxRecurse) {
4422  if (Constant *C = foldOrCommuteConstant(Instruction::FMul, Op0, Op1, Q))
4423  return C;
4424 
4425  if (Constant *C = simplifyFPBinop(Op0, Op1))
4426  return C;
4427 
4428  // fmul X, 1.0 ==> X
4429  if (match(Op1, m_FPOne()))
4430  return Op0;
4431 
4432  // fmul nnan nsz X, 0 ==> 0
4433  if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op1, m_AnyZeroFP()))
4434  return ConstantFP::getNullValue(Op0->getType());
4435 
4436  // sqrt(X) * sqrt(X) --> X, if we can:
4437  // 1. Remove the intermediate rounding (reassociate).
4438  // 2. Ignore non-zero negative numbers because sqrt would produce NAN.
4439  // 3. Ignore -0.0 because sqrt(-0.0) == -0.0, but -0.0 * -0.0 == 0.0.
4440  Value *X;
4441  if (Op0 == Op1 && match(Op0, m_Intrinsic<Intrinsic::sqrt>(m_Value(X))) &&
4442  FMF.allowReassoc() && FMF.noNaNs() && FMF.noSignedZeros())
4443  return X;
4444 
4445  return nullptr;
4446 }
4447 
4449  const SimplifyQuery &Q) {
4450  return ::SimplifyFAddInst(Op0, Op1, FMF, Q, RecursionLimit);
4451 }
4452 
4453 
4455  const SimplifyQuery &Q) {
4456  return ::SimplifyFSubInst(Op0, Op1, FMF, Q, RecursionLimit);
4457 }
4458 
4460  const SimplifyQuery &Q) {
4461  return ::SimplifyFMulInst(Op0, Op1, FMF, Q, RecursionLimit);
4462 }
4463 
4465  const SimplifyQuery &Q, unsigned) {
4466  if (Constant *C = foldOrCommuteConstant(Instruction::FDiv, Op0, Op1, Q))
4467  return C;
4468 
4469  if (Constant *C = simplifyFPBinop(Op0, Op1))
4470  return C;
4471 
4472  // X / 1.0 -> X
4473  if (match(Op1, m_FPOne()))
4474  return Op0;
4475 
4476  // 0 / X -> 0
4477  // Requires that NaNs are off (X could be zero) and signed zeroes are
4478  // ignored (X could be positive or negative, so the output sign is unknown).
4479  if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op0, m_AnyZeroFP()))
4480  return ConstantFP::getNullValue(Op0->getType());
4481 
4482  if (FMF.noNaNs()) {
4483  // X / X -> 1.0 is legal when NaNs are ignored.
4484  // We can ignore infinities because INF/INF is NaN.
4485  if (Op0 == Op1)
4486  return ConstantFP::get(Op0->getType(), 1.0);
4487 
4488  // (X * Y) / Y --> X if we can reassociate to the above form.
4489  Value *X;
4490  if (FMF.allowReassoc() && match(Op0, m_c_FMul(m_Value(X), m_Specific(Op1))))
4491  return X;
4492 
4493  // -X / X -> -1.0 and
4494  // X / -X -> -1.0 are legal when NaNs are ignored.
4495  // We can ignore signed zeros because +-0.0/+-0.0 is NaN and ignored.
4496  if ((BinaryOperator::isFNeg(Op0, /*IgnoreZeroSign=*/true) &&
4497  BinaryOperator::getFNegArgument(Op0) == Op1) ||
4498  (BinaryOperator::isFNeg(Op1, /*IgnoreZeroSign=*/true) &&
4499  BinaryOperator::getFNegArgument(Op1) == Op0))
4500  return ConstantFP::get(Op0->getType(), -1.0);
4501  }
4502 
4503  return nullptr;
4504 }
4505 
4507  const SimplifyQuery &Q) {
4508  return ::SimplifyFDivInst(Op0, Op1, FMF, Q, RecursionLimit);
4509 }
4510 
4512  const SimplifyQuery &Q, unsigned) {
4513  if (Constant *C = foldOrCommuteConstant(Instruction::FRem, Op0, Op1, Q))
4514  return C;
4515 
4516  if (Constant *C = simplifyFPBinop(Op0, Op1))
4517  return C;
4518 
4519  // Unlike fdiv, the result of frem always matches the sign of the dividend.
4520  // The constant match may include undef elements in a vector, so return a full
4521  // zero constant as the result.
4522  if (FMF.noNaNs()) {
4523  // +0 % X -> 0
4524  if (match(Op0, m_PosZeroFP()))
4525  return ConstantFP::getNullValue(Op0->getType());
4526  // -0 % X -> -0
4527  if (match(Op0, m_NegZeroFP()))
4528  return ConstantFP::getNegativeZero(Op0->getType());
4529  }
4530 
4531  return nullptr;
4532 }
4533 
4535  const SimplifyQuery &Q) {
4536  return ::SimplifyFRemInst(Op0, Op1, FMF, Q, RecursionLimit);
4537 }
4538 
4539 //=== Helper functions for higher up the class hierarchy.
4540 
4541 /// Given operands for a BinaryOperator, see if we can fold the result.
4542 /// If not, this returns null.
4543 static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
4544  const SimplifyQuery &Q, unsigned MaxRecurse) {
4545  switch (Opcode) {
4546  case Instruction::Add:
4547  return SimplifyAddInst(LHS, RHS, false, false, Q, MaxRecurse);
4548  case Instruction::Sub:
4549  return SimplifySubInst(LHS, RHS, false, false, Q, MaxRecurse);
4550  case Instruction::Mul:
4551  return SimplifyMulInst(LHS, RHS, Q, MaxRecurse);
4552  case Instruction::SDiv:
4553  return SimplifySDivInst(LHS, RHS, Q, MaxRecurse);
4554  case Instruction::UDiv:
4555  return SimplifyUDivInst(LHS, RHS, Q, MaxRecurse);
4556  case Instruction::SRem:
4557  return SimplifySRemInst(LHS, RHS, Q, MaxRecurse);
4558  case Instruction::URem:
4559  return SimplifyURemInst(LHS, RHS, Q, MaxRecurse);
4560  case Instruction::Shl:
4561  return SimplifyShlInst(LHS, RHS, false, false, Q, MaxRecurse);
4562  case Instruction::LShr:
4563  return SimplifyLShrInst(LHS, RHS, false, Q, MaxRecurse);
4564  case Instruction::AShr:
4565  return SimplifyAShrInst(LHS, RHS, false, Q, MaxRecurse);
4566  case Instruction::And:
4567  return SimplifyAndInst(LHS, RHS, Q, MaxRecurse);
4568  case Instruction::Or:
4569  return SimplifyOrInst(LHS, RHS, Q, MaxRecurse);
4570  case Instruction::Xor:
4571  return SimplifyXorInst(LHS, RHS, Q, MaxRecurse);
4572  case Instruction::FAdd:
4573  return SimplifyFAddInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
4574  case Instruction::FSub:
4575  return SimplifyFSubInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
4576  case Instruction::FMul:
4577  return SimplifyFMulInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
4578  case Instruction::FDiv:
4579  return SimplifyFDivInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
4580  case Instruction::FRem:
4581  return SimplifyFRemInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
4582  default:
4583  llvm_unreachable("Unexpected opcode");
4584  }
4585 }
4586 
4587 /// Given operands for a BinaryOperator, see if we can fold the result.
4588 /// If not, this returns null.
4589 /// In contrast to SimplifyBinOp, try to use FastMathFlag when folding the
4590 /// result. In case we don't need FastMathFlags, simply fall to SimplifyBinOp.
4591 static Value *SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
4592  const FastMathFlags &FMF, const SimplifyQuery &Q,
4593  unsigned MaxRecurse) {
4594  switch (Opcode) {
4595  case Instruction::FAdd:
4596  return SimplifyFAddInst(LHS, RHS, FMF, Q, MaxRecurse);
4597  case Instruction::FSub:
4598  return SimplifyFSubInst(LHS, RHS, FMF, Q, MaxRecurse);
4599  case Instruction::FMul:
4600  return SimplifyFMulInst(LHS, RHS, FMF, Q, MaxRecurse);
4601  case Instruction::FDiv:
4602  return SimplifyFDivInst(LHS, RHS, FMF, Q, MaxRecurse);
4603  default:
4604  return SimplifyBinOp(Opcode, LHS, RHS, Q, MaxRecurse);
4605  }
4606 }
4607 
4608 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
4609  const SimplifyQuery &Q) {
4610  return ::SimplifyBinOp(Opcode, LHS, RHS, Q, RecursionLimit);
4611 }
4612 
4613 Value *llvm::SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
4614  FastMathFlags FMF, const SimplifyQuery &Q) {
4615  return ::SimplifyFPBinOp(Opcode, LHS, RHS, FMF, Q, RecursionLimit);
4616 }
4617 
4618 /// Given operands for a CmpInst, see if we can fold the result.
4619 static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
4620  const SimplifyQuery &Q, unsigned MaxRecurse) {
4622  return SimplifyICmpInst(Predicate, LHS, RHS, Q, MaxRecurse);
4623  return SimplifyFCmpInst(Predicate, LHS, RHS, FastMathFlags(), Q, MaxRecurse);
4624 }
4625 
4626 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
4627  const SimplifyQuery &Q) {
4628  return ::SimplifyCmpInst(Predicate, LHS, RHS, Q, RecursionLimit);
4629 }
4630 
4632  switch (ID) {
4633  default: return false;
4634 
4635  // Unary idempotent: f(f(x)) = f(x)
4636  case Intrinsic::fabs:
4637  case Intrinsic::floor:
4638  case Intrinsic::ceil:
4639  case Intrinsic::trunc:
4640  case Intrinsic::rint:
4641  case Intrinsic::nearbyint:
4642  case Intrinsic::round:
4643  case Intrinsic::canonicalize:
4644  return true;
4645  }
4646 }
4647 
4649  const DataLayout &DL) {
4650  GlobalValue *PtrSym;
4651  APInt PtrOffset;
4652  if (!IsConstantOffsetFromGlobal(Ptr, PtrSym, PtrOffset, DL))
4653  return nullptr;
4654 
4655  Type *Int8PtrTy = Type::getInt8PtrTy(Ptr->getContext());
4657  Type *Int32PtrTy = Int32Ty->getPointerTo();
4658  Type *Int64Ty = Type::getInt64Ty(Ptr->getContext());
4659 
4660  auto *OffsetConstInt = dyn_cast<ConstantInt>(Offset);
4661  if (!OffsetConstInt || OffsetConstInt->getType()->getBitWidth() > 64)
4662  return nullptr;
4663 
4664  uint64_t OffsetInt = OffsetConstInt->getSExtValue();
4665  if (OffsetInt % 4 != 0)
4666  return nullptr;
4667 
4669  Int32Ty, ConstantExpr::getBitCast(Ptr, Int32PtrTy),
4670  ConstantInt::get(Int64Ty, OffsetInt / 4));
4671  Constant *Loaded = ConstantFoldLoadFromConstPtr(C, Int32Ty, DL);
4672  if (!Loaded)
4673  return nullptr;
4674 
4675  auto *LoadedCE = dyn_cast<ConstantExpr>(Loaded);
4676  if (!LoadedCE)
4677  return nullptr;
4678 
4679  if (LoadedCE->getOpcode() == Instruction::Trunc) {
4680  LoadedCE = dyn_cast<ConstantExpr>(LoadedCE->getOperand(0));
4681  if (!LoadedCE)
4682  return nullptr;
4683  }
4684 
4685  if (LoadedCE->getOpcode() != Instruction::Sub)
4686  return nullptr;
4687 
4688  auto *LoadedLHS = dyn_cast<ConstantExpr>(LoadedCE->getOperand(0));
4689  if (!LoadedLHS || LoadedLHS->getOpcode() != Instruction::PtrToInt)
4690  return nullptr;
4691  auto *LoadedLHSPtr = LoadedLHS->getOperand(0);
4692 
4693  Constant *LoadedRHS = LoadedCE->getOperand(1);
4694  GlobalValue *LoadedRHSSym;
4695  APInt LoadedRHSOffset;
4696  if (!IsConstantOffsetFromGlobal(LoadedRHS, LoadedRHSSym, LoadedRHSOffset,
4697  DL) ||
4698  PtrSym != LoadedRHSSym || PtrOffset != LoadedRHSOffset)
4699  return nullptr;
4700 
4701  return ConstantExpr::getBitCast(LoadedLHSPtr, Int8PtrTy);
4702 }
4703 
4705  auto *ConstMask = dyn_cast<Constant>(Mask);
4706  if (!ConstMask)
4707  return false;
4708  if (ConstMask->isNullValue() || isa<UndefValue>(ConstMask))
4709  return true;
4710  for (unsigned I = 0, E = ConstMask->getType()->getVectorNumElements(); I != E;
4711  ++I) {
4712  if (auto *MaskElt = ConstMask->getAggregateElement(I))
4713  if (MaskElt->isNullValue() || isa<UndefValue>(MaskElt))
4714  continue;
4715  return false;
4716  }
4717  return true;
4718 }
4719 
4721  const SimplifyQuery &Q) {
4722  // Idempotent functions return the same result when called repeatedly.
4723  Intrinsic::ID IID = F->getIntrinsicID();
4724  if (IsIdempotent(IID))
4725  if (auto *II = dyn_cast<IntrinsicInst>(Op0))
4726  if (II->getIntrinsicID() == IID)
4727  return II;
4728 
4729  Value *X;
4730  switch (IID) {
4731  case Intrinsic::fabs:
4732  if (SignBitMustBeZero(Op0, Q.TLI)) return Op0;
4733  break;
4734  case Intrinsic::bswap:
4735  // bswap(bswap(x)) -> x
4736  if (match(Op0, m_BSwap(m_Value(X)))) return X;
4737  break;
4738  case Intrinsic::bitreverse:
4739  // bitreverse(bitreverse(x)) -> x
4740  if (match(Op0, m_BitReverse(m_Value(X)))) return X;
4741  break;
4742  case Intrinsic::exp:
4743  // exp(log(x)) -> x
4744  if (Q.CxtI->hasAllowReassoc() &&
4745  match(Op0, m_Intrinsic<Intrinsic::log>(m_Value(X)))) return X;
4746  break;
4747  case Intrinsic::exp2:
4748  // exp2(log2(x)) -> x
4749  if (Q.CxtI->hasAllowReassoc() &&
4750  match(Op0, m_Intrinsic<Intrinsic::log2>(m_Value(X)))) return X;
4751  break;
4752  case Intrinsic::log:
4753  // log(exp(x)) -> x
4754  if (Q.CxtI->hasAllowReassoc() &&
4755  match(Op0, m_Intrinsic<Intrinsic::exp>(m_Value(X)))) return X;
4756  break;
4757  case Intrinsic::log2:
4758  // log2(exp2(x)) -> x
4759  if (Q.CxtI->hasAllowReassoc() &&
4760  match(Op0, m_Intrinsic<Intrinsic::exp2>(m_Value(X)))) return X;
4761  break;
4762  default:
4763  break;
4764  }
4765 
4766  return nullptr;
4767 }
4768 
4770  const SimplifyQuery &Q) {
4771  Intrinsic::ID IID = F->getIntrinsicID();
4772  Type *ReturnType = F->getReturnType();
4773  switch (IID) {
4774  case Intrinsic::usub_with_overflow:
4775  case Intrinsic::ssub_with_overflow:
4776  // X - X -> { 0, false }
4777  if (Op0 == Op1)
4778  return Constant::getNullValue(ReturnType);
4779  // X - undef -> undef
4780  // undef - X -> undef
4781  if (isa<UndefValue>(Op0) || isa<UndefValue>(Op1))
4782  return UndefValue::get(ReturnType);
4783  break;
4784  case Intrinsic::uadd_with_overflow:
4785  case Intrinsic::sadd_with_overflow:
4786  // X + undef -> undef
4787  if (isa<UndefValue>(Op0) || isa<UndefValue>(Op1))
4788  return UndefValue::get(ReturnType);
4789  break;
4790  case Intrinsic::umul_with_overflow:
4791  case Intrinsic::smul_with_overflow:
4792  // 0 * X -> { 0, false }
4793  // X * 0 -> { 0, false }
4794  if (match(Op0, m_Zero()) || match(Op1, m_Zero()))
4795  return Constant::getNullValue(ReturnType);
4796  // undef * X -> { 0, false }
4797  // X * undef -> { 0, false }
4798  if (match(Op0, m_Undef()) || match(Op1, m_Undef()))
4799  return Constant::getNullValue(ReturnType);
4800  break;
4801  case Intrinsic::load_relative:
4802  if (auto *C0 = dyn_cast<Constant>(Op0))
4803  if (auto *C1 = dyn_cast<Constant>(Op1))
4804  return SimplifyRelativeLoad(C0, C1, Q.DL);
4805  break;
4806  case Intrinsic::powi:
4807  if (auto *Power = dyn_cast<ConstantInt>(Op1)) {
4808  // powi(x, 0) -> 1.0
4809  if (Power->isZero())
4810  return ConstantFP::get(Op0->getType(), 1.0);
4811  // powi(x, 1) -> x
4812  if (Power->isOne())
4813  return Op0;
4814  }
4815  break;
4816  case Intrinsic::maxnum:
4817  case Intrinsic::minnum: {
4818  // If the arguments are the same, this is a no-op.
4819  if (Op0 == Op1) return Op0;
4820 
4821  // If one argument is NaN or undef, return the other argument.
4822  if (match(Op0, m_CombineOr(m_NaN(), m_Undef()))) return Op1;
4823  if (match(Op1, m_CombineOr(m_NaN(), m_Undef()))) return Op0;
4824 
4825  // Min/max of the same operation with common operand:
4826  // m(m(X, Y)), X --> m(X, Y) (4 commuted variants)
4827  if (auto *M0 = dyn_cast<IntrinsicInst>(Op0))
4828  if (M0->getIntrinsicID() == IID &&
4829  (M0->getOperand(0) == Op1 || M0->getOperand(1) == Op1))
4830  return Op0;
4831  if (auto *M1 = dyn_cast<IntrinsicInst>(Op1))
4832  if (M1->getIntrinsicID() == IID &&
4833  (M1->getOperand(0) == Op0 || M1->getOperand(1) == Op0))
4834  return Op1;
4835 
4836  // minnum(X, -Inf) --> -Inf (and commuted variant)
4837  // maxnum(X, +Inf) --> +Inf (and commuted variant)
4838  bool UseNegInf = IID == Intrinsic::minnum;
4839  const APFloat *C;
4840  if ((match(Op0, m_APFloat(C)) && C->isInfinity() &&
4841  C->isNegative() == UseNegInf) ||
4842  (match(Op1, m_APFloat(C)) && C->isInfinity() &&
4843  C->isNegative() == UseNegInf))
4844  return ConstantFP::getInfinity(ReturnType, UseNegInf);
4845 
4846  // TODO: minnum(nnan x, inf) -> x
4847  // TODO: minnum(nnan ninf x, flt_max) -> x