LLVM  15.0.0git
InstructionSimplify.cpp
Go to the documentation of this file.
1 //===- InstructionSimplify.cpp - Fold instruction operands ----------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements routines for folding instructions into simpler forms
10 // that do not require creating new instructions. This does constant folding
11 // ("add i32 1, 1" -> "2") but can also handle non-constant operands, either
12 // returning a constant ("and i32 %x, 0" -> "0") or an already existing value
13 // ("and i32 %x, %x" -> "%x"). All operands are assumed to have already been
14 // simplified: This is usually true and assuming it simplifies the logic (if
15 // they have not been simplified then results are correct but maybe suboptimal).
16 //
17 //===----------------------------------------------------------------------===//
18 
20 
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/ADT/SetVector.h"
23 #include "llvm/ADT/Statistic.h"
35 #include "llvm/IR/ConstantRange.h"
36 #include "llvm/IR/DataLayout.h"
37 #include "llvm/IR/Dominators.h"
38 #include "llvm/IR/InstrTypes.h"
39 #include "llvm/IR/Instructions.h"
40 #include "llvm/IR/Operator.h"
41 #include "llvm/IR/PatternMatch.h"
42 #include "llvm/Support/KnownBits.h"
43 #include <algorithm>
44 using namespace llvm;
45 using namespace llvm::PatternMatch;
46 
47 #define DEBUG_TYPE "instsimplify"
48 
49 enum { RecursionLimit = 3 };
50 
51 STATISTIC(NumExpand, "Number of expansions");
52 STATISTIC(NumReassoc, "Number of reassociations");
53 
54 static Value *simplifyAndInst(Value *, Value *, const SimplifyQuery &,
55  unsigned);
56 static Value *simplifyUnOp(unsigned, Value *, const SimplifyQuery &, unsigned);
57 static Value *simplifyFPUnOp(unsigned, Value *, const FastMathFlags &,
58  const SimplifyQuery &, unsigned);
59 static Value *simplifyBinOp(unsigned, Value *, Value *, const SimplifyQuery &,
60  unsigned);
61 static Value *simplifyBinOp(unsigned, Value *, Value *, const FastMathFlags &,
62  const SimplifyQuery &, unsigned);
63 static Value *simplifyCmpInst(unsigned, Value *, Value *, const SimplifyQuery &,
64  unsigned);
65 static Value *simplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
66  const SimplifyQuery &Q, unsigned MaxRecurse);
67 static Value *simplifyOrInst(Value *, Value *, const SimplifyQuery &, unsigned);
68 static Value *simplifyXorInst(Value *, Value *, const SimplifyQuery &,
69  unsigned);
70 static Value *simplifyCastInst(unsigned, Value *, Type *, const SimplifyQuery &,
71  unsigned);
73  const SimplifyQuery &, unsigned);
74 static Value *simplifySelectInst(Value *, Value *, Value *,
75  const SimplifyQuery &, unsigned);
76 
78  Value *FalseVal) {
79  BinaryOperator::BinaryOps BinOpCode;
80  if (auto *BO = dyn_cast<BinaryOperator>(Cond))
81  BinOpCode = BO->getOpcode();
82  else
83  return nullptr;
84 
85  CmpInst::Predicate ExpectedPred, Pred1, Pred2;
86  if (BinOpCode == BinaryOperator::Or) {
87  ExpectedPred = ICmpInst::ICMP_NE;
88  } else if (BinOpCode == BinaryOperator::And) {
89  ExpectedPred = ICmpInst::ICMP_EQ;
90  } else
91  return nullptr;
92 
93  // %A = icmp eq %TV, %FV
94  // %B = icmp eq %X, %Y (and one of these is a select operand)
95  // %C = and %A, %B
96  // %D = select %C, %TV, %FV
97  // -->
98  // %FV
99 
100  // %A = icmp ne %TV, %FV
101  // %B = icmp ne %X, %Y (and one of these is a select operand)
102  // %C = or %A, %B
103  // %D = select %C, %TV, %FV
104  // -->
105  // %TV
106  Value *X, *Y;
109  m_ICmp(Pred2, m_Value(X), m_Value(Y)))) ||
110  Pred1 != Pred2 || Pred1 != ExpectedPred)
111  return nullptr;
112 
113  if (X == TrueVal || X == FalseVal || Y == TrueVal || Y == FalseVal)
114  return BinOpCode == BinaryOperator::Or ? TrueVal : FalseVal;
115 
116  return nullptr;
117 }
118 
119 /// For a boolean type or a vector of boolean type, return false or a vector
120 /// with every element false.
121 static Constant *getFalse(Type *Ty) { return ConstantInt::getFalse(Ty); }
122 
123 /// For a boolean type or a vector of boolean type, return true or a vector
124 /// with every element true.
125 static Constant *getTrue(Type *Ty) { return ConstantInt::getTrue(Ty); }
126 
127 /// isSameCompare - Is V equivalent to the comparison "LHS Pred RHS"?
129  Value *RHS) {
130  CmpInst *Cmp = dyn_cast<CmpInst>(V);
131  if (!Cmp)
132  return false;
133  CmpInst::Predicate CPred = Cmp->getPredicate();
134  Value *CLHS = Cmp->getOperand(0), *CRHS = Cmp->getOperand(1);
135  if (CPred == Pred && CLHS == LHS && CRHS == RHS)
136  return true;
137  return CPred == CmpInst::getSwappedPredicate(Pred) && CLHS == RHS &&
138  CRHS == LHS;
139 }
140 
141 /// Simplify comparison with true or false branch of select:
142 /// %sel = select i1 %cond, i32 %tv, i32 %fv
143 /// %cmp = icmp sle i32 %sel, %rhs
144 /// Compose new comparison by substituting %sel with either %tv or %fv
145 /// and see if it simplifies.
147  Value *RHS, Value *Cond,
148  const SimplifyQuery &Q, unsigned MaxRecurse,
149  Constant *TrueOrFalse) {
150  Value *SimplifiedCmp = simplifyCmpInst(Pred, LHS, RHS, Q, MaxRecurse);
151  if (SimplifiedCmp == Cond) {
152  // %cmp simplified to the select condition (%cond).
153  return TrueOrFalse;
154  } else if (!SimplifiedCmp && isSameCompare(Cond, Pred, LHS, RHS)) {
155  // It didn't simplify. However, if composed comparison is equivalent
156  // to the select condition (%cond) then we can replace it.
157  return TrueOrFalse;
158  }
159  return SimplifiedCmp;
160 }
161 
162 /// Simplify comparison with true branch of select
164  Value *RHS, Value *Cond,
165  const SimplifyQuery &Q,
166  unsigned MaxRecurse) {
167  return simplifyCmpSelCase(Pred, LHS, RHS, Cond, Q, MaxRecurse,
168  getTrue(Cond->getType()));
169 }
170 
171 /// Simplify comparison with false branch of select
173  Value *RHS, Value *Cond,
174  const SimplifyQuery &Q,
175  unsigned MaxRecurse) {
176  return simplifyCmpSelCase(Pred, LHS, RHS, Cond, Q, MaxRecurse,
177  getFalse(Cond->getType()));
178 }
179 
180 /// We know comparison with both branches of select can be simplified, but they
181 /// are not equal. This routine handles some logical simplifications.
183  Value *Cond,
184  const SimplifyQuery &Q,
185  unsigned MaxRecurse) {
186  // If the false value simplified to false, then the result of the compare
187  // is equal to "Cond && TCmp". This also catches the case when the false
188  // value simplified to false and the true value to true, returning "Cond".
189  // Folding select to and/or isn't poison-safe in general; impliesPoison
190  // checks whether folding it does not convert a well-defined value into
191  // poison.
192  if (match(FCmp, m_Zero()) && impliesPoison(TCmp, Cond))
193  if (Value *V = simplifyAndInst(Cond, TCmp, Q, MaxRecurse))
194  return V;
195  // If the true value simplified to true, then the result of the compare
196  // is equal to "Cond || FCmp".
197  if (match(TCmp, m_One()) && impliesPoison(FCmp, Cond))
198  if (Value *V = simplifyOrInst(Cond, FCmp, Q, MaxRecurse))
199  return V;
200  // Finally, if the false value simplified to true and the true value to
201  // false, then the result of the compare is equal to "!Cond".
202  if (match(FCmp, m_One()) && match(TCmp, m_Zero()))
203  if (Value *V = simplifyXorInst(
204  Cond, Constant::getAllOnesValue(Cond->getType()), Q, MaxRecurse))
205  return V;
206  return nullptr;
207 }
208 
209 /// Does the given value dominate the specified phi node?
210 static bool valueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
211  Instruction *I = dyn_cast<Instruction>(V);
212  if (!I)
213  // Arguments and constants dominate all instructions.
214  return true;
215 
216  // If we are processing instructions (and/or basic blocks) that have not been
217  // fully added to a function, the parent nodes may still be null. Simply
218  // return the conservative answer in these cases.
219  if (!I->getParent() || !P->getParent() || !I->getFunction())
220  return false;
221 
222  // If we have a DominatorTree then do a precise test.
223  if (DT)
224  return DT->dominates(I, P);
225 
226  // Otherwise, if the instruction is in the entry block and is not an invoke,
227  // then it obviously dominates all phi nodes.
228  if (I->getParent()->isEntryBlock() && !isa<InvokeInst>(I) &&
229  !isa<CallBrInst>(I))
230  return true;
231 
232  return false;
233 }
234 
235 /// Try to simplify a binary operator of form "V op OtherOp" where V is
236 /// "(B0 opex B1)" by distributing 'op' across 'opex' as
237 /// "(B0 op OtherOp) opex (B1 op OtherOp)".
239  Value *OtherOp, Instruction::BinaryOps OpcodeToExpand,
240  const SimplifyQuery &Q, unsigned MaxRecurse) {
241  auto *B = dyn_cast<BinaryOperator>(V);
242  if (!B || B->getOpcode() != OpcodeToExpand)
243  return nullptr;
244  Value *B0 = B->getOperand(0), *B1 = B->getOperand(1);
245  Value *L =
246  simplifyBinOp(Opcode, B0, OtherOp, Q.getWithoutUndef(), MaxRecurse);
247  if (!L)
248  return nullptr;
249  Value *R =
250  simplifyBinOp(Opcode, B1, OtherOp, Q.getWithoutUndef(), MaxRecurse);
251  if (!R)
252  return nullptr;
253 
254  // Does the expanded pair of binops simplify to the existing binop?
255  if ((L == B0 && R == B1) ||
256  (Instruction::isCommutative(OpcodeToExpand) && L == B1 && R == B0)) {
257  ++NumExpand;
258  return B;
259  }
260 
261  // Otherwise, return "L op' R" if it simplifies.
262  Value *S = simplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse);
263  if (!S)
264  return nullptr;
265 
266  ++NumExpand;
267  return S;
268 }
269 
270 /// Try to simplify binops of form "A op (B op' C)" or the commuted variant by
271 /// distributing op over op'.
273  Value *R,
274  Instruction::BinaryOps OpcodeToExpand,
275  const SimplifyQuery &Q,
276  unsigned MaxRecurse) {
277  // Recursion is always used, so bail out at once if we already hit the limit.
278  if (!MaxRecurse--)
279  return nullptr;
280 
281  if (Value *V = expandBinOp(Opcode, L, R, OpcodeToExpand, Q, MaxRecurse))
282  return V;
283  if (Value *V = expandBinOp(Opcode, R, L, OpcodeToExpand, Q, MaxRecurse))
284  return V;
285  return nullptr;
286 }
287 
288 /// Generic simplifications for associative binary operations.
289 /// Returns the simpler value, or null if none was found.
291  Value *LHS, Value *RHS,
292  const SimplifyQuery &Q,
293  unsigned MaxRecurse) {
294  assert(Instruction::isAssociative(Opcode) && "Not an associative operation!");
295 
296  // Recursion is always used, so bail out at once if we already hit the limit.
297  if (!MaxRecurse--)
298  return nullptr;
299 
300  BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
301  BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
302 
303  // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely.
304  if (Op0 && Op0->getOpcode() == Opcode) {
305  Value *A = Op0->getOperand(0);
306  Value *B = Op0->getOperand(1);
307  Value *C = RHS;
308 
309  // Does "B op C" simplify?
310  if (Value *V = simplifyBinOp(Opcode, B, C, Q, MaxRecurse)) {
311  // It does! Return "A op V" if it simplifies or is already available.
312  // If V equals B then "A op V" is just the LHS.
313  if (V == B)
314  return LHS;
315  // Otherwise return "A op V" if it simplifies.
316  if (Value *W = simplifyBinOp(Opcode, A, V, Q, MaxRecurse)) {
317  ++NumReassoc;
318  return W;
319  }
320  }
321  }
322 
323  // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely.
324  if (Op1 && Op1->getOpcode() == Opcode) {
325  Value *A = LHS;
326  Value *B = Op1->getOperand(0);
327  Value *C = Op1->getOperand(1);
328 
329  // Does "A op B" simplify?
330  if (Value *V = simplifyBinOp(Opcode, A, B, Q, MaxRecurse)) {
331  // It does! Return "V op C" if it simplifies or is already available.
332  // If V equals B then "V op C" is just the RHS.
333  if (V == B)
334  return RHS;
335  // Otherwise return "V op C" if it simplifies.
336  if (Value *W = simplifyBinOp(Opcode, V, C, Q, MaxRecurse)) {
337  ++NumReassoc;
338  return W;
339  }
340  }
341  }
342 
343  // The remaining transforms require commutativity as well as associativity.
344  if (!Instruction::isCommutative(Opcode))
345  return nullptr;
346 
347  // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely.
348  if (Op0 && Op0->getOpcode() == Opcode) {
349  Value *A = Op0->getOperand(0);
350  Value *B = Op0->getOperand(1);
351  Value *C = RHS;
352 
353  // Does "C op A" simplify?
354  if (Value *V = simplifyBinOp(Opcode, C, A, Q, MaxRecurse)) {
355  // It does! Return "V op B" if it simplifies or is already available.
356  // If V equals A then "V op B" is just the LHS.
357  if (V == A)
358  return LHS;
359  // Otherwise return "V op B" if it simplifies.
360  if (Value *W = simplifyBinOp(Opcode, V, B, Q, MaxRecurse)) {
361  ++NumReassoc;
362  return W;
363  }
364  }
365  }
366 
367  // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely.
368  if (Op1 && Op1->getOpcode() == Opcode) {
369  Value *A = LHS;
370  Value *B = Op1->getOperand(0);
371  Value *C = Op1->getOperand(1);
372 
373  // Does "C op A" simplify?
374  if (Value *V = simplifyBinOp(Opcode, C, A, Q, MaxRecurse)) {
375  // It does! Return "B op V" if it simplifies or is already available.
376  // If V equals C then "B op V" is just the RHS.
377  if (V == C)
378  return RHS;
379  // Otherwise return "B op V" if it simplifies.
380  if (Value *W = simplifyBinOp(Opcode, B, V, Q, MaxRecurse)) {
381  ++NumReassoc;
382  return W;
383  }
384  }
385  }
386 
387  return nullptr;
388 }
389 
390 /// In the case of a binary operation with a select instruction as an operand,
391 /// try to simplify the binop by seeing whether evaluating it on both branches
392 /// of the select results in the same value. Returns the common value if so,
393 /// otherwise returns null.
395  Value *RHS, const SimplifyQuery &Q,
396  unsigned MaxRecurse) {
397  // Recursion is always used, so bail out at once if we already hit the limit.
398  if (!MaxRecurse--)
399  return nullptr;
400 
401  SelectInst *SI;
402  if (isa<SelectInst>(LHS)) {
403  SI = cast<SelectInst>(LHS);
404  } else {
405  assert(isa<SelectInst>(RHS) && "No select instruction operand!");
406  SI = cast<SelectInst>(RHS);
407  }
408 
409  // Evaluate the BinOp on the true and false branches of the select.
410  Value *TV;
411  Value *FV;
412  if (SI == LHS) {
413  TV = simplifyBinOp(Opcode, SI->getTrueValue(), RHS, Q, MaxRecurse);
414  FV = simplifyBinOp(Opcode, SI->getFalseValue(), RHS, Q, MaxRecurse);
415  } else {
416  TV = simplifyBinOp(Opcode, LHS, SI->getTrueValue(), Q, MaxRecurse);
417  FV = simplifyBinOp(Opcode, LHS, SI->getFalseValue(), Q, MaxRecurse);
418  }
419 
420  // If they simplified to the same value, then return the common value.
421  // If they both failed to simplify then return null.
422  if (TV == FV)
423  return TV;
424 
425  // If one branch simplified to undef, return the other one.
426  if (TV && Q.isUndefValue(TV))
427  return FV;
428  if (FV && Q.isUndefValue(FV))
429  return TV;
430 
431  // If applying the operation did not change the true and false select values,
432  // then the result of the binop is the select itself.
433  if (TV == SI->getTrueValue() && FV == SI->getFalseValue())
434  return SI;
435 
436  // If one branch simplified and the other did not, and the simplified
437  // value is equal to the unsimplified one, return the simplified value.
438  // For example, select (cond, X, X & Z) & Z -> X & Z.
439  if ((FV && !TV) || (TV && !FV)) {
440  // Check that the simplified value has the form "X op Y" where "op" is the
441  // same as the original operation.
442  Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV);
443  if (Simplified && Simplified->getOpcode() == unsigned(Opcode)) {
444  // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS".
445  // We already know that "op" is the same as for the simplified value. See
446  // if the operands match too. If so, return the simplified value.
447  Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue();
448  Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS;
449  Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch;
450  if (Simplified->getOperand(0) == UnsimplifiedLHS &&
451  Simplified->getOperand(1) == UnsimplifiedRHS)
452  return Simplified;
453  if (Simplified->isCommutative() &&
454  Simplified->getOperand(1) == UnsimplifiedLHS &&
455  Simplified->getOperand(0) == UnsimplifiedRHS)
456  return Simplified;
457  }
458  }
459 
460  return nullptr;
461 }
462 
463 /// In the case of a comparison with a select instruction, try to simplify the
464 /// comparison by seeing whether both branches of the select result in the same
465 /// value. Returns the common value if so, otherwise returns null.
466 /// For example, if we have:
467 /// %tmp = select i1 %cmp, i32 1, i32 2
468 /// %cmp1 = icmp sle i32 %tmp, 3
469 /// We can simplify %cmp1 to true, because both branches of select are
470 /// less than 3. We compose new comparison by substituting %tmp with both
471 /// branches of select and see if it can be simplified.
473  Value *RHS, const SimplifyQuery &Q,
474  unsigned MaxRecurse) {
475  // Recursion is always used, so bail out at once if we already hit the limit.
476  if (!MaxRecurse--)
477  return nullptr;
478 
479  // Make sure the select is on the LHS.
480  if (!isa<SelectInst>(LHS)) {
481  std::swap(LHS, RHS);
482  Pred = CmpInst::getSwappedPredicate(Pred);
483  }
484  assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!");
485  SelectInst *SI = cast<SelectInst>(LHS);
486  Value *Cond = SI->getCondition();
487  Value *TV = SI->getTrueValue();
488  Value *FV = SI->getFalseValue();
489 
490  // Now that we have "cmp select(Cond, TV, FV), RHS", analyse it.
491  // Does "cmp TV, RHS" simplify?
492  Value *TCmp = simplifyCmpSelTrueCase(Pred, TV, RHS, Cond, Q, MaxRecurse);
493  if (!TCmp)
494  return nullptr;
495 
496  // Does "cmp FV, RHS" simplify?
497  Value *FCmp = simplifyCmpSelFalseCase(Pred, FV, RHS, Cond, Q, MaxRecurse);
498  if (!FCmp)
499  return nullptr;
500 
501  // If both sides simplified to the same value, then use it as the result of
502  // the original comparison.
503  if (TCmp == FCmp)
504  return TCmp;
505 
506  // The remaining cases only make sense if the select condition has the same
507  // type as the result of the comparison, so bail out if this is not so.
508  if (Cond->getType()->isVectorTy() == RHS->getType()->isVectorTy())
509  return handleOtherCmpSelSimplifications(TCmp, FCmp, Cond, Q, MaxRecurse);
510 
511  return nullptr;
512 }
513 
514 /// In the case of a binary operation with an operand that is a PHI instruction,
515 /// try to simplify the binop by seeing whether evaluating it on the incoming
516 /// phi values yields the same result for every value. If so returns the common
517 /// value, otherwise returns null.
519  Value *RHS, const SimplifyQuery &Q,
520  unsigned MaxRecurse) {
521  // Recursion is always used, so bail out at once if we already hit the limit.
522  if (!MaxRecurse--)
523  return nullptr;
524 
525  PHINode *PI;
526  if (isa<PHINode>(LHS)) {
527  PI = cast<PHINode>(LHS);
528  // Bail out if RHS and the phi may be mutually interdependent due to a loop.
529  if (!valueDominatesPHI(RHS, PI, Q.DT))
530  return nullptr;
531  } else {
532  assert(isa<PHINode>(RHS) && "No PHI instruction operand!");
533  PI = cast<PHINode>(RHS);
534  // Bail out if LHS and the phi may be mutually interdependent due to a loop.
535  if (!valueDominatesPHI(LHS, PI, Q.DT))
536  return nullptr;
537  }
538 
539  // Evaluate the BinOp on the incoming phi values.
540  Value *CommonValue = nullptr;
541  for (Value *Incoming : PI->incoming_values()) {
542  // If the incoming value is the phi node itself, it can safely be skipped.
543  if (Incoming == PI)
544  continue;
545  Value *V = PI == LHS ? simplifyBinOp(Opcode, Incoming, RHS, Q, MaxRecurse)
546  : simplifyBinOp(Opcode, LHS, Incoming, Q, MaxRecurse);
547  // If the operation failed to simplify, or simplified to a different value
548  // to previously, then give up.
549  if (!V || (CommonValue && V != CommonValue))
550  return nullptr;
551  CommonValue = V;
552  }
553 
554  return CommonValue;
555 }
556 
557 /// In the case of a comparison with a PHI instruction, try to simplify the
558 /// comparison by seeing whether comparing with all of the incoming phi values
559 /// yields the same result every time. If so returns the common result,
560 /// otherwise returns null.
562  const SimplifyQuery &Q, unsigned MaxRecurse) {
563  // Recursion is always used, so bail out at once if we already hit the limit.
564  if (!MaxRecurse--)
565  return nullptr;
566 
567  // Make sure the phi is on the LHS.
568  if (!isa<PHINode>(LHS)) {
569  std::swap(LHS, RHS);
570  Pred = CmpInst::getSwappedPredicate(Pred);
571  }
572  assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!");
573  PHINode *PI = cast<PHINode>(LHS);
574 
575  // Bail out if RHS and the phi may be mutually interdependent due to a loop.
576  if (!valueDominatesPHI(RHS, PI, Q.DT))
577  return nullptr;
578 
579  // Evaluate the BinOp on the incoming phi values.
580  Value *CommonValue = nullptr;
581  for (unsigned u = 0, e = PI->getNumIncomingValues(); u < e; ++u) {
582  Value *Incoming = PI->getIncomingValue(u);
583  Instruction *InTI = PI->getIncomingBlock(u)->getTerminator();
584  // If the incoming value is the phi node itself, it can safely be skipped.
585  if (Incoming == PI)
586  continue;
587  // Change the context instruction to the "edge" that flows into the phi.
588  // This is important because that is where incoming is actually "evaluated"
589  // even though it is used later somewhere else.
590  Value *V = simplifyCmpInst(Pred, Incoming, RHS, Q.getWithInstruction(InTI),
591  MaxRecurse);
592  // If the operation failed to simplify, or simplified to a different value
593  // to previously, then give up.
594  if (!V || (CommonValue && V != CommonValue))
595  return nullptr;
596  CommonValue = V;
597  }
598 
599  return CommonValue;
600 }
601 
603  Value *&Op0, Value *&Op1,
604  const SimplifyQuery &Q) {
605  if (auto *CLHS = dyn_cast<Constant>(Op0)) {
606  if (auto *CRHS = dyn_cast<Constant>(Op1)) {
607  switch (Opcode) {
608  default:
609  break;
610  case Instruction::FAdd:
611  case Instruction::FSub:
612  case Instruction::FMul:
613  case Instruction::FDiv:
614  case Instruction::FRem:
615  if (Q.CxtI != nullptr)
616  return ConstantFoldFPInstOperands(Opcode, CLHS, CRHS, Q.DL, Q.CxtI);
617  }
618  return ConstantFoldBinaryOpOperands(Opcode, CLHS, CRHS, Q.DL);
619  }
620 
621  // Canonicalize the constant to the RHS if this is a commutative operation.
622  if (Instruction::isCommutative(Opcode))
623  std::swap(Op0, Op1);
624  }
625  return nullptr;
626 }
627 
628 /// Given operands for an Add, see if we can fold the result.
629 /// If not, this returns null.
630 static Value *simplifyAddInst(Value *Op0, Value *Op1, bool IsNSW, bool IsNUW,
631  const SimplifyQuery &Q, unsigned MaxRecurse) {
632  if (Constant *C = foldOrCommuteConstant(Instruction::Add, Op0, Op1, Q))
633  return C;
634 
635  // X + poison -> poison
636  if (isa<PoisonValue>(Op1))
637  return Op1;
638 
639  // X + undef -> undef
640  if (Q.isUndefValue(Op1))
641  return Op1;
642 
643  // X + 0 -> X
644  if (match(Op1, m_Zero()))
645  return Op0;
646 
647  // If two operands are negative, return 0.
648  if (isKnownNegation(Op0, Op1))
649  return Constant::getNullValue(Op0->getType());
650 
651  // X + (Y - X) -> Y
652  // (Y - X) + X -> Y
653  // Eg: X + -X -> 0
654  Value *Y = nullptr;
655  if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) ||
656  match(Op0, m_Sub(m_Value(Y), m_Specific(Op1))))
657  return Y;
658 
659  // X + ~X -> -1 since ~X = -X-1
660  Type *Ty = Op0->getType();
661  if (match(Op0, m_Not(m_Specific(Op1))) || match(Op1, m_Not(m_Specific(Op0))))
662  return Constant::getAllOnesValue(Ty);
663 
664  // add nsw/nuw (xor Y, signmask), signmask --> Y
665  // The no-wrapping add guarantees that the top bit will be set by the add.
666  // Therefore, the xor must be clearing the already set sign bit of Y.
667  if ((IsNSW || IsNUW) && match(Op1, m_SignMask()) &&
668  match(Op0, m_Xor(m_Value(Y), m_SignMask())))
669  return Y;
670 
671  // add nuw %x, -1 -> -1, because %x can only be 0.
672  if (IsNUW && match(Op1, m_AllOnes()))
673  return Op1; // Which is -1.
674 
675  /// i1 add -> xor.
676  if (MaxRecurse && Op0->getType()->isIntOrIntVectorTy(1))
677  if (Value *V = simplifyXorInst(Op0, Op1, Q, MaxRecurse - 1))
678  return V;
679 
680  // Try some generic simplifications for associative operations.
681  if (Value *V =
682  simplifyAssociativeBinOp(Instruction::Add, Op0, Op1, Q, MaxRecurse))
683  return V;
684 
685  // Threading Add over selects and phi nodes is pointless, so don't bother.
686  // Threading over the select in "A + select(cond, B, C)" means evaluating
687  // "A+B" and "A+C" and seeing if they are equal; but they are equal if and
688  // only if B and C are equal. If B and C are equal then (since we assume
689  // that operands have already been simplified) "select(cond, B, C)" should
690  // have been simplified to the common value of B and C already. Analysing
691  // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly
692  // for threading over phi nodes.
693 
694  return nullptr;
695 }
696 
697 Value *llvm::simplifyAddInst(Value *Op0, Value *Op1, bool IsNSW, bool IsNUW,
698  const SimplifyQuery &Query) {
699  return ::simplifyAddInst(Op0, Op1, IsNSW, IsNUW, Query, RecursionLimit);
700 }
701 
702 /// Compute the base pointer and cumulative constant offsets for V.
703 ///
704 /// This strips all constant offsets off of V, leaving it the base pointer, and
705 /// accumulates the total constant offset applied in the returned constant.
706 /// It returns zero if there are no constant offsets applied.
707 ///
708 /// This is very similar to stripAndAccumulateConstantOffsets(), except it
709 /// normalizes the offset bitwidth to the stripped pointer type, not the
710 /// original pointer type.
712  bool AllowNonInbounds = false) {
714 
715  APInt Offset = APInt::getZero(DL.getIndexTypeSizeInBits(V->getType()));
716  V = V->stripAndAccumulateConstantOffsets(DL, Offset, AllowNonInbounds);
717  // As that strip may trace through `addrspacecast`, need to sext or trunc
718  // the offset calculated.
719  return Offset.sextOrTrunc(DL.getIndexTypeSizeInBits(V->getType()));
720 }
721 
722 /// Compute the constant difference between two pointer values.
723 /// If the difference is not a constant, returns zero.
725  Value *RHS) {
728 
729  // If LHS and RHS are not related via constant offsets to the same base
730  // value, there is nothing we can do here.
731  if (LHS != RHS)
732  return nullptr;
733 
734  // Otherwise, the difference of LHS - RHS can be computed as:
735  // LHS - RHS
736  // = (LHSOffset + Base) - (RHSOffset + Base)
737  // = LHSOffset - RHSOffset
738  Constant *Res = ConstantInt::get(LHS->getContext(), LHSOffset - RHSOffset);
739  if (auto *VecTy = dyn_cast<VectorType>(LHS->getType()))
740  Res = ConstantVector::getSplat(VecTy->getElementCount(), Res);
741  return Res;
742 }
743 
744 /// Given operands for a Sub, see if we can fold the result.
745 /// If not, this returns null.
746 static Value *simplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
747  const SimplifyQuery &Q, unsigned MaxRecurse) {
748  if (Constant *C = foldOrCommuteConstant(Instruction::Sub, Op0, Op1, Q))
749  return C;
750 
751  // X - poison -> poison
752  // poison - X -> poison
753  if (isa<PoisonValue>(Op0) || isa<PoisonValue>(Op1))
754  return PoisonValue::get(Op0->getType());
755 
756  // X - undef -> undef
757  // undef - X -> undef
758  if (Q.isUndefValue(Op0) || Q.isUndefValue(Op1))
759  return UndefValue::get(Op0->getType());
760 
761  // X - 0 -> X
762  if (match(Op1, m_Zero()))
763  return Op0;
764 
765  // X - X -> 0
766  if (Op0 == Op1)
767  return Constant::getNullValue(Op0->getType());
768 
769  // Is this a negation?
770  if (match(Op0, m_Zero())) {
771  // 0 - X -> 0 if the sub is NUW.
772  if (isNUW)
773  return Constant::getNullValue(Op0->getType());
774 
775  KnownBits Known = computeKnownBits(Op1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
776  if (Known.Zero.isMaxSignedValue()) {
777  // Op1 is either 0 or the minimum signed value. If the sub is NSW, then
778  // Op1 must be 0 because negating the minimum signed value is undefined.
779  if (isNSW)
780  return Constant::getNullValue(Op0->getType());
781 
782  // 0 - X -> X if X is 0 or the minimum signed value.
783  return Op1;
784  }
785  }
786 
787  // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies.
788  // For example, (X + Y) - Y -> X; (Y + X) - Y -> X
789  Value *X = nullptr, *Y = nullptr, *Z = Op1;
790  if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z
791  // See if "V === Y - Z" simplifies.
792  if (Value *V = simplifyBinOp(Instruction::Sub, Y, Z, Q, MaxRecurse - 1))
793  // It does! Now see if "X + V" simplifies.
794  if (Value *W = simplifyBinOp(Instruction::Add, X, V, Q, MaxRecurse - 1)) {
795  // It does, we successfully reassociated!
796  ++NumReassoc;
797  return W;
798  }
799  // See if "V === X - Z" simplifies.
800  if (Value *V = simplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse - 1))
801  // It does! Now see if "Y + V" simplifies.
802  if (Value *W = simplifyBinOp(Instruction::Add, Y, V, Q, MaxRecurse - 1)) {
803  // It does, we successfully reassociated!
804  ++NumReassoc;
805  return W;
806  }
807  }
808 
809  // X - (Y + Z) -> (X - Y) - Z or (X - Z) - Y if everything simplifies.
810  // For example, X - (X + 1) -> -1
811  X = Op0;
812  if (MaxRecurse && match(Op1, m_Add(m_Value(Y), m_Value(Z)))) { // X - (Y + Z)
813  // See if "V === X - Y" simplifies.
814  if (Value *V = simplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse - 1))
815  // It does! Now see if "V - Z" simplifies.
816  if (Value *W = simplifyBinOp(Instruction::Sub, V, Z, Q, MaxRecurse - 1)) {
817  // It does, we successfully reassociated!
818  ++NumReassoc;
819  return W;
820  }
821  // See if "V === X - Z" simplifies.
822  if (Value *V = simplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse - 1))
823  // It does! Now see if "V - Y" simplifies.
824  if (Value *W = simplifyBinOp(Instruction::Sub, V, Y, Q, MaxRecurse - 1)) {
825  // It does, we successfully reassociated!
826  ++NumReassoc;
827  return W;
828  }
829  }
830 
831  // Z - (X - Y) -> (Z - X) + Y if everything simplifies.
832  // For example, X - (X - Y) -> Y.
833  Z = Op0;
834  if (MaxRecurse && match(Op1, m_Sub(m_Value(X), m_Value(Y)))) // Z - (X - Y)
835  // See if "V === Z - X" simplifies.
836  if (Value *V = simplifyBinOp(Instruction::Sub, Z, X, Q, MaxRecurse - 1))
837  // It does! Now see if "V + Y" simplifies.
838  if (Value *W = simplifyBinOp(Instruction::Add, V, Y, Q, MaxRecurse - 1)) {
839  // It does, we successfully reassociated!
840  ++NumReassoc;
841  return W;
842  }
843 
844  // trunc(X) - trunc(Y) -> trunc(X - Y) if everything simplifies.
845  if (MaxRecurse && match(Op0, m_Trunc(m_Value(X))) &&
846  match(Op1, m_Trunc(m_Value(Y))))
847  if (X->getType() == Y->getType())
848  // See if "V === X - Y" simplifies.
849  if (Value *V = simplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse - 1))
850  // It does! Now see if "trunc V" simplifies.
851  if (Value *W = simplifyCastInst(Instruction::Trunc, V, Op0->getType(),
852  Q, MaxRecurse - 1))
853  // It does, return the simplified "trunc V".
854  return W;
855 
856  // Variations on GEP(base, I, ...) - GEP(base, i, ...) -> GEP(null, I-i, ...).
857  if (match(Op0, m_PtrToInt(m_Value(X))) && match(Op1, m_PtrToInt(m_Value(Y))))
858  if (Constant *Result = computePointerDifference(Q.DL, X, Y))
859  return ConstantExpr::getIntegerCast(Result, Op0->getType(), true);
860 
861  // i1 sub -> xor.
862  if (MaxRecurse && Op0->getType()->isIntOrIntVectorTy(1))
863  if (Value *V = simplifyXorInst(Op0, Op1, Q, MaxRecurse - 1))
864  return V;
865 
866  // Threading Sub over selects and phi nodes is pointless, so don't bother.
867  // Threading over the select in "A - select(cond, B, C)" means evaluating
868  // "A-B" and "A-C" and seeing if they are equal; but they are equal if and
869  // only if B and C are equal. If B and C are equal then (since we assume
870  // that operands have already been simplified) "select(cond, B, C)" should
871  // have been simplified to the common value of B and C already. Analysing
872  // "A-B" and "A-C" thus gains nothing, but costs compile time. Similarly
873  // for threading over phi nodes.
874 
875  return nullptr;
876 }
877 
878 Value *llvm::simplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
879  const SimplifyQuery &Q) {
880  return ::simplifySubInst(Op0, Op1, isNSW, isNUW, Q, RecursionLimit);
881 }
882 
883 /// Given operands for a Mul, see if we can fold the result.
884 /// If not, this returns null.
885 static Value *simplifyMulInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
886  unsigned MaxRecurse) {
887  if (Constant *C = foldOrCommuteConstant(Instruction::Mul, Op0, Op1, Q))
888  return C;
889 
890  // X * poison -> poison
891  if (isa<PoisonValue>(Op1))
892  return Op1;
893 
894  // X * undef -> 0
895  // X * 0 -> 0
896  if (Q.isUndefValue(Op1) || match(Op1, m_Zero()))
897  return Constant::getNullValue(Op0->getType());
898 
899  // X * 1 -> X
900  if (match(Op1, m_One()))
901  return Op0;
902 
903  // (X / Y) * Y -> X if the division is exact.
904  Value *X = nullptr;
905  if (Q.IIQ.UseInstrInfo &&
906  (match(Op0,
907  m_Exact(m_IDiv(m_Value(X), m_Specific(Op1)))) || // (X / Y) * Y
908  match(Op1, m_Exact(m_IDiv(m_Value(X), m_Specific(Op0)))))) // Y * (X / Y)
909  return X;
910 
911  // i1 mul -> and.
912  if (MaxRecurse && Op0->getType()->isIntOrIntVectorTy(1))
913  if (Value *V = simplifyAndInst(Op0, Op1, Q, MaxRecurse - 1))
914  return V;
915 
916  // Try some generic simplifications for associative operations.
917  if (Value *V =
918  simplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, Q, MaxRecurse))
919  return V;
920 
921  // Mul distributes over Add. Try some generic simplifications based on this.
922  if (Value *V = expandCommutativeBinOp(Instruction::Mul, Op0, Op1,
923  Instruction::Add, Q, MaxRecurse))
924  return V;
925 
926  // If the operation is with the result of a select instruction, check whether
927  // operating on either branch of the select always yields the same value.
928  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
929  if (Value *V =
930  threadBinOpOverSelect(Instruction::Mul, Op0, Op1, Q, MaxRecurse))
931  return V;
932 
933  // If the operation is with the result of a phi instruction, check whether
934  // operating on all incoming values of the phi always yields the same value.
935  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
936  if (Value *V =
937  threadBinOpOverPHI(Instruction::Mul, Op0, Op1, Q, MaxRecurse))
938  return V;
939 
940  return nullptr;
941 }
942 
945 }
946 
947 /// Check for common or similar folds of integer division or integer remainder.
948 /// This applies to all 4 opcodes (sdiv/udiv/srem/urem).
950  Value *Op1, const SimplifyQuery &Q) {
951  bool IsDiv = (Opcode == Instruction::SDiv || Opcode == Instruction::UDiv);
952  bool IsSigned = (Opcode == Instruction::SDiv || Opcode == Instruction::SRem);
953 
954  Type *Ty = Op0->getType();
955 
956  // X / undef -> poison
957  // X % undef -> poison
958  if (Q.isUndefValue(Op1) || isa<PoisonValue>(Op1))
959  return PoisonValue::get(Ty);
960 
961  // X / 0 -> poison
962  // X % 0 -> poison
963  // We don't need to preserve faults!
964  if (match(Op1, m_Zero()))
965  return PoisonValue::get(Ty);
966 
967  // If any element of a constant divisor fixed width vector is zero or undef
968  // the behavior is undefined and we can fold the whole op to poison.
969  auto *Op1C = dyn_cast<Constant>(Op1);
970  auto *VTy = dyn_cast<FixedVectorType>(Ty);
971  if (Op1C && VTy) {
972  unsigned NumElts = VTy->getNumElements();
973  for (unsigned i = 0; i != NumElts; ++i) {
974  Constant *Elt = Op1C->getAggregateElement(i);
975  if (Elt && (Elt->isNullValue() || Q.isUndefValue(Elt)))
976  return PoisonValue::get(Ty);
977  }
978  }
979 
980  // poison / X -> poison
981  // poison % X -> poison
982  if (isa<PoisonValue>(Op0))
983  return Op0;
984 
985  // undef / X -> 0
986  // undef % X -> 0
987  if (Q.isUndefValue(Op0))
988  return Constant::getNullValue(Ty);
989 
990  // 0 / X -> 0
991  // 0 % X -> 0
992  if (match(Op0, m_Zero()))
993  return Constant::getNullValue(Op0->getType());
994 
995  // X / X -> 1
996  // X % X -> 0
997  if (Op0 == Op1)
998  return IsDiv ? ConstantInt::get(Ty, 1) : Constant::getNullValue(Ty);
999 
1000  // X / 1 -> X
1001  // X % 1 -> 0
1002  // If this is a boolean op (single-bit element type), we can't have
1003  // division-by-zero or remainder-by-zero, so assume the divisor is 1.
1004  // Similarly, if we're zero-extending a boolean divisor, then assume it's a 1.
1005  Value *X;
1006  if (match(Op1, m_One()) || Ty->isIntOrIntVectorTy(1) ||
1007  (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)))
1008  return IsDiv ? Op0 : Constant::getNullValue(Ty);
1009 
1010  // If X * Y does not overflow, then:
1011  // X * Y / Y -> X
1012  // X * Y % Y -> 0
1013  if (match(Op0, m_c_Mul(m_Value(X), m_Specific(Op1)))) {
1014  auto *Mul = cast<OverflowingBinaryOperator>(Op0);
1015  // The multiplication can't overflow if it is defined not to, or if
1016  // X == A / Y for some A.
1017  if ((IsSigned && Q.IIQ.hasNoSignedWrap(Mul)) ||
1018  (!IsSigned && Q.IIQ.hasNoUnsignedWrap(Mul)) ||
1019  (IsSigned && match(X, m_SDiv(m_Value(), m_Specific(Op1)))) ||
1020  (!IsSigned && match(X, m_UDiv(m_Value(), m_Specific(Op1))))) {
1021  return IsDiv ? X : Constant::getNullValue(Op0->getType());
1022  }
1023  }
1024 
1025  return nullptr;
1026 }
1027 
1028 /// Given a predicate and two operands, return true if the comparison is true.
1029 /// This is a helper for div/rem simplification where we return some other value
1030 /// when we can prove a relationship between the operands.
1032  const SimplifyQuery &Q, unsigned MaxRecurse) {
1033  Value *V = simplifyICmpInst(Pred, LHS, RHS, Q, MaxRecurse);
1034  Constant *C = dyn_cast_or_null<Constant>(V);
1035  return (C && C->isAllOnesValue());
1036 }
1037 
1038 /// Return true if we can simplify X / Y to 0. Remainder can adapt that answer
1039 /// to simplify X % Y to X.
1040 static bool isDivZero(Value *X, Value *Y, const SimplifyQuery &Q,
1041  unsigned MaxRecurse, bool IsSigned) {
1042  // Recursion is always used, so bail out at once if we already hit the limit.
1043  if (!MaxRecurse--)
1044  return false;
1045 
1046  if (IsSigned) {
1047  // |X| / |Y| --> 0
1048  //
1049  // We require that 1 operand is a simple constant. That could be extended to
1050  // 2 variables if we computed the sign bit for each.
1051  //
1052  // Make sure that a constant is not the minimum signed value because taking
1053  // the abs() of that is undefined.
1054  Type *Ty = X->getType();
1055  const APInt *C;
1056  if (match(X, m_APInt(C)) && !C->isMinSignedValue()) {
1057  // Is the variable divisor magnitude always greater than the constant
1058  // dividend magnitude?
1059  // |Y| > |C| --> Y < -abs(C) or Y > abs(C)
1060  Constant *PosDividendC = ConstantInt::get(Ty, C->abs());
1061  Constant *NegDividendC = ConstantInt::get(Ty, -C->abs());
1062  if (isICmpTrue(CmpInst::ICMP_SLT, Y, NegDividendC, Q, MaxRecurse) ||
1063  isICmpTrue(CmpInst::ICMP_SGT, Y, PosDividendC, Q, MaxRecurse))
1064  return true;
1065  }
1066  if (match(Y, m_APInt(C))) {
1067  // Special-case: we can't take the abs() of a minimum signed value. If
1068  // that's the divisor, then all we have to do is prove that the dividend
1069  // is also not the minimum signed value.
1070  if (C->isMinSignedValue())
1071  return isICmpTrue(CmpInst::ICMP_NE, X, Y, Q, MaxRecurse);
1072 
1073  // Is the variable dividend magnitude always less than the constant
1074  // divisor magnitude?
1075  // |X| < |C| --> X > -abs(C) and X < abs(C)
1076  Constant *PosDivisorC = ConstantInt::get(Ty, C->abs());
1077  Constant *NegDivisorC = ConstantInt::get(Ty, -C->abs());
1078  if (isICmpTrue(CmpInst::ICMP_SGT, X, NegDivisorC, Q, MaxRecurse) &&
1079  isICmpTrue(CmpInst::ICMP_SLT, X, PosDivisorC, Q, MaxRecurse))
1080  return true;
1081  }
1082  return false;
1083  }
1084 
1085  // IsSigned == false.
1086 
1087  // Is the unsigned dividend known to be less than a constant divisor?
1088  // TODO: Convert this (and above) to range analysis
1089  // ("computeConstantRangeIncludingKnownBits")?
1090  const APInt *C;
1091  if (match(Y, m_APInt(C)) &&
1092  computeKnownBits(X, Q.DL, 0, Q.AC, Q.CxtI, Q.DT).getMaxValue().ult(*C))
1093  return true;
1094 
1095  // Try again for any divisor:
1096  // Is the dividend unsigned less than the divisor?
1097  return isICmpTrue(ICmpInst::ICMP_ULT, X, Y, Q, MaxRecurse);
1098 }
1099 
1100 /// These are simplifications common to SDiv and UDiv.
1102  const SimplifyQuery &Q, unsigned MaxRecurse) {
1103  if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
1104  return C;
1105 
1106  if (Value *V = simplifyDivRem(Opcode, Op0, Op1, Q))
1107  return V;
1108 
1109  bool IsSigned = Opcode == Instruction::SDiv;
1110 
1111  // (X rem Y) / Y -> 0
1112  if ((IsSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) ||
1113  (!IsSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
1114  return Constant::getNullValue(Op0->getType());
1115 
1116  // (X /u C1) /u C2 -> 0 if C1 * C2 overflow
1117  ConstantInt *C1, *C2;
1118  if (!IsSigned && match(Op0, m_UDiv(m_Value(), m_ConstantInt(C1))) &&
1119  match(Op1, m_ConstantInt(C2))) {
1120  bool Overflow;
1121  (void)C1->getValue().umul_ov(C2->getValue(), Overflow);
1122  if (Overflow)
1123  return Constant::getNullValue(Op0->getType());
1124  }
1125 
1126  // If the operation is with the result of a select instruction, check whether
1127  // operating on either branch of the select always yields the same value.
1128  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1129  if (Value *V = threadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
1130  return V;
1131 
1132  // If the operation is with the result of a phi instruction, check whether
1133  // operating on all incoming values of the phi always yields the same value.
1134  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1135  if (Value *V = threadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
1136  return V;
1137 
1138  if (isDivZero(Op0, Op1, Q, MaxRecurse, IsSigned))
1139  return Constant::getNullValue(Op0->getType());
1140 
1141  return nullptr;
1142 }
1143 
1144 /// These are simplifications common to SRem and URem.
1146  const SimplifyQuery &Q, unsigned MaxRecurse) {
1147  if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
1148  return C;
1149 
1150  if (Value *V = simplifyDivRem(Opcode, Op0, Op1, Q))
1151  return V;
1152 
1153  // (X % Y) % Y -> X % Y
1154  if ((Opcode == Instruction::SRem &&
1155  match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) ||
1156  (Opcode == Instruction::URem &&
1157  match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
1158  return Op0;
1159 
1160  // (X << Y) % X -> 0
1161  if (Q.IIQ.UseInstrInfo &&
1162  ((Opcode == Instruction::SRem &&
1163  match(Op0, m_NSWShl(m_Specific(Op1), m_Value()))) ||
1164  (Opcode == Instruction::URem &&
1165  match(Op0, m_NUWShl(m_Specific(Op1), m_Value())))))
1166  return Constant::getNullValue(Op0->getType());
1167 
1168  // If the operation is with the result of a select instruction, check whether
1169  // operating on either branch of the select always yields the same value.
1170  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1171  if (Value *V = threadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
1172  return V;
1173 
1174  // If the operation is with the result of a phi instruction, check whether
1175  // operating on all incoming values of the phi always yields the same value.
1176  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1177  if (Value *V = threadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
1178  return V;
1179 
1180  // If X / Y == 0, then X % Y == X.
1181  if (isDivZero(Op0, Op1, Q, MaxRecurse, Opcode == Instruction::SRem))
1182  return Op0;
1183 
1184  return nullptr;
1185 }
1186 
1187 /// Given operands for an SDiv, see if we can fold the result.
1188 /// If not, this returns null.
1189 static Value *simplifySDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1190  unsigned MaxRecurse) {
1191  // If two operands are negated and no signed overflow, return -1.
1192  if (isKnownNegation(Op0, Op1, /*NeedNSW=*/true))
1193  return Constant::getAllOnesValue(Op0->getType());
1194 
1195  return simplifyDiv(Instruction::SDiv, Op0, Op1, Q, MaxRecurse);
1196 }
1197 
1200 }
1201 
1202 /// Given operands for a UDiv, see if we can fold the result.
1203 /// If not, this returns null.
1204 static Value *simplifyUDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1205  unsigned MaxRecurse) {
1206  return simplifyDiv(Instruction::UDiv, Op0, Op1, Q, MaxRecurse);
1207 }
1208 
1211 }
1212 
1213 /// Given operands for an SRem, see if we can fold the result.
1214 /// If not, this returns null.
1215 static Value *simplifySRemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1216  unsigned MaxRecurse) {
1217  // If the divisor is 0, the result is undefined, so assume the divisor is -1.
1218  // srem Op0, (sext i1 X) --> srem Op0, -1 --> 0
1219  Value *X;
1220  if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
1221  return ConstantInt::getNullValue(Op0->getType());
1222 
1223  // If the two operands are negated, return 0.
1224  if (isKnownNegation(Op0, Op1))
1225  return ConstantInt::getNullValue(Op0->getType());
1226 
1227  return simplifyRem(Instruction::SRem, Op0, Op1, Q, MaxRecurse);
1228 }
1229 
1232 }
1233 
1234 /// Given operands for a URem, see if we can fold the result.
1235 /// If not, this returns null.
1236 static Value *simplifyURemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1237  unsigned MaxRecurse) {
1238  return simplifyRem(Instruction::URem, Op0, Op1, Q, MaxRecurse);
1239 }
1240 
1243 }
1244 
1245 /// Returns true if a shift by \c Amount always yields poison.
1246 static bool isPoisonShift(Value *Amount, const SimplifyQuery &Q) {
1247  Constant *C = dyn_cast<Constant>(Amount);
1248  if (!C)
1249  return false;
1250 
1251  // X shift by undef -> poison because it may shift by the bitwidth.
1252  if (Q.isUndefValue(C))
1253  return true;
1254 
1255  // Shifting by the bitwidth or more is undefined.
1256  if (ConstantInt *CI = dyn_cast<ConstantInt>(C))
1257  if (CI->getValue().uge(CI->getType()->getScalarSizeInBits()))
1258  return true;
1259 
1260  // If all lanes of a vector shift are undefined the whole shift is.
1261  if (isa<ConstantVector>(C) || isa<ConstantDataVector>(C)) {
1262  for (unsigned I = 0,
1263  E = cast<FixedVectorType>(C->getType())->getNumElements();
1264  I != E; ++I)
1265  if (!isPoisonShift(C->getAggregateElement(I), Q))
1266  return false;
1267  return true;
1268  }
1269 
1270  return false;
1271 }
1272 
1273 /// Given operands for an Shl, LShr or AShr, see if we can fold the result.
1274 /// If not, this returns null.
1276  Value *Op1, bool IsNSW, const SimplifyQuery &Q,
1277  unsigned MaxRecurse) {
1278  if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
1279  return C;
1280 
1281  // poison shift by X -> poison
1282  if (isa<PoisonValue>(Op0))
1283  return Op0;
1284 
1285  // 0 shift by X -> 0
1286  if (match(Op0, m_Zero()))
1287  return Constant::getNullValue(Op0->getType());
1288 
1289  // X shift by 0 -> X
1290  // Shift-by-sign-extended bool must be shift-by-0 because shift-by-all-ones
1291  // would be poison.
1292  Value *X;
1293  if (match(Op1, m_Zero()) ||
1294  (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)))
1295  return Op0;
1296 
1297  // Fold undefined shifts.
1298  if (isPoisonShift(Op1, Q))
1299  return PoisonValue::get(Op0->getType());
1300 
1301  // If the operation is with the result of a select instruction, check whether
1302  // operating on either branch of the select always yields the same value.
1303  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1304  if (Value *V = threadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
1305  return V;
1306 
1307  // If the operation is with the result of a phi instruction, check whether
1308  // operating on all incoming values of the phi always yields the same value.
1309  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1310  if (Value *V = threadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
1311  return V;
1312 
1313  // If any bits in the shift amount make that value greater than or equal to
1314  // the number of bits in the type, the shift is undefined.
1315  KnownBits KnownAmt = computeKnownBits(Op1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
1316  if (KnownAmt.getMinValue().uge(KnownAmt.getBitWidth()))
1317  return PoisonValue::get(Op0->getType());
1318 
1319  // If all valid bits in the shift amount are known zero, the first operand is
1320  // unchanged.
1321  unsigned NumValidShiftBits = Log2_32_Ceil(KnownAmt.getBitWidth());
1322  if (KnownAmt.countMinTrailingZeros() >= NumValidShiftBits)
1323  return Op0;
1324 
1325  // Check for nsw shl leading to a poison value.
1326  if (IsNSW) {
1327  assert(Opcode == Instruction::Shl && "Expected shl for nsw instruction");
1328  KnownBits KnownVal = computeKnownBits(Op0, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
1329  KnownBits KnownShl = KnownBits::shl(KnownVal, KnownAmt);
1330 
1331  if (KnownVal.Zero.isSignBitSet())
1332  KnownShl.Zero.setSignBit();
1333  if (KnownVal.One.isSignBitSet())
1334  KnownShl.One.setSignBit();
1335 
1336  if (KnownShl.hasConflict())
1337  return PoisonValue::get(Op0->getType());
1338  }
1339 
1340  return nullptr;
1341 }
1342 
1343 /// Given operands for an Shl, LShr or AShr, see if we can
1344 /// fold the result. If not, this returns null.
1346  Value *Op1, bool isExact,
1347  const SimplifyQuery &Q, unsigned MaxRecurse) {
1348  if (Value *V =
1349  simplifyShift(Opcode, Op0, Op1, /*IsNSW*/ false, Q, MaxRecurse))
1350  return V;
1351 
1352  // X >> X -> 0
1353  if (Op0 == Op1)
1354  return Constant::getNullValue(Op0->getType());
1355 
1356  // undef >> X -> 0
1357  // undef >> X -> undef (if it's exact)
1358  if (Q.isUndefValue(Op0))
1359  return isExact ? Op0 : Constant::getNullValue(Op0->getType());
1360 
1361  // The low bit cannot be shifted out of an exact shift if it is set.
1362  if (isExact) {
1363  KnownBits Op0Known =
1364  computeKnownBits(Op0, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT);
1365  if (Op0Known.One[0])
1366  return Op0;
1367  }
1368 
1369  return nullptr;
1370 }
1371 
1372 /// Given operands for an Shl, see if we can fold the result.
1373 /// If not, this returns null.
1374 static Value *simplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
1375  const SimplifyQuery &Q, unsigned MaxRecurse) {
1376  if (Value *V =
1377  simplifyShift(Instruction::Shl, Op0, Op1, isNSW, Q, MaxRecurse))
1378  return V;
1379 
1380  // undef << X -> 0
1381  // undef << X -> undef if (if it's NSW/NUW)
1382  if (Q.isUndefValue(Op0))
1383  return isNSW || isNUW ? Op0 : Constant::getNullValue(Op0->getType());
1384 
1385  // (X >> A) << A -> X
1386  Value *X;
1387  if (Q.IIQ.UseInstrInfo &&
1388  match(Op0, m_Exact(m_Shr(m_Value(X), m_Specific(Op1)))))
1389  return X;
1390 
1391  // shl nuw i8 C, %x -> C iff C has sign bit set.
1392  if (isNUW && match(Op0, m_Negative()))
1393  return Op0;
1394  // NOTE: could use computeKnownBits() / LazyValueInfo,
1395  // but the cost-benefit analysis suggests it isn't worth it.
1396 
1397  return nullptr;
1398 }
1399 
1400 Value *llvm::simplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
1401  const SimplifyQuery &Q) {
1402  return ::simplifyShlInst(Op0, Op1, isNSW, isNUW, Q, RecursionLimit);
1403 }
1404 
1405 /// Given operands for an LShr, see if we can fold the result.
1406 /// If not, this returns null.
1407 static Value *simplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
1408  const SimplifyQuery &Q, unsigned MaxRecurse) {
1409  if (Value *V = simplifyRightShift(Instruction::LShr, Op0, Op1, isExact, Q,
1410  MaxRecurse))
1411  return V;
1412 
1413  // (X << A) >> A -> X
1414  Value *X;
1415  if (match(Op0, m_NUWShl(m_Value(X), m_Specific(Op1))))
1416  return X;
1417 
1418  // ((X << A) | Y) >> A -> X if effective width of Y is not larger than A.
1419  // We can return X as we do in the above case since OR alters no bits in X.
1420  // SimplifyDemandedBits in InstCombine can do more general optimization for
1421  // bit manipulation. This pattern aims to provide opportunities for other
1422  // optimizers by supporting a simple but common case in InstSimplify.
1423  Value *Y;
1424  const APInt *ShRAmt, *ShLAmt;
1425  if (match(Op1, m_APInt(ShRAmt)) &&
1426  match(Op0, m_c_Or(m_NUWShl(m_Value(X), m_APInt(ShLAmt)), m_Value(Y))) &&
1427  *ShRAmt == *ShLAmt) {
1428  const KnownBits YKnown = computeKnownBits(Y, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
1429  const unsigned EffWidthY = YKnown.countMaxActiveBits();
1430  if (ShRAmt->uge(EffWidthY))
1431  return X;
1432  }
1433 
1434  return nullptr;
1435 }
1436 
1437 Value *llvm::simplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
1438  const SimplifyQuery &Q) {
1439  return ::simplifyLShrInst(Op0, Op1, isExact, Q, RecursionLimit);
1440 }
1441 
1442 /// Given operands for an AShr, see if we can fold the result.
1443 /// If not, this returns null.
1444 static Value *simplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
1445  const SimplifyQuery &Q, unsigned MaxRecurse) {
1446  if (Value *V = simplifyRightShift(Instruction::AShr, Op0, Op1, isExact, Q,
1447  MaxRecurse))
1448  return V;
1449 
1450  // -1 >>a X --> -1
1451  // (-1 << X) a>> X --> -1
1452  // Do not return Op0 because it may contain undef elements if it's a vector.
1453  if (match(Op0, m_AllOnes()) ||
1454  match(Op0, m_Shl(m_AllOnes(), m_Specific(Op1))))
1455  return Constant::getAllOnesValue(Op0->getType());
1456 
1457  // (X << A) >> A -> X
1458  Value *X;
1459  if (Q.IIQ.UseInstrInfo && match(Op0, m_NSWShl(m_Value(X), m_Specific(Op1))))
1460  return X;
1461 
1462  // Arithmetic shifting an all-sign-bit value is a no-op.
1463  unsigned NumSignBits = ComputeNumSignBits(Op0, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
1464  if (NumSignBits == Op0->getType()->getScalarSizeInBits())
1465  return Op0;
1466 
1467  return nullptr;
1468 }
1469 
1470 Value *llvm::simplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
1471  const SimplifyQuery &Q) {
1472  return ::simplifyAShrInst(Op0, Op1, isExact, Q, RecursionLimit);
1473 }
1474 
1475 /// Commuted variants are assumed to be handled by calling this function again
1476 /// with the parameters swapped.
1478  ICmpInst *UnsignedICmp, bool IsAnd,
1479  const SimplifyQuery &Q) {
1480  Value *X, *Y;
1481 
1482  ICmpInst::Predicate EqPred;
1483  if (!match(ZeroICmp, m_ICmp(EqPred, m_Value(Y), m_Zero())) ||
1484  !ICmpInst::isEquality(EqPred))
1485  return nullptr;
1486 
1487  ICmpInst::Predicate UnsignedPred;
1488 
1489  Value *A, *B;
1490  // Y = (A - B);
1491  if (match(Y, m_Sub(m_Value(A), m_Value(B)))) {
1492  if (match(UnsignedICmp,
1493  m_c_ICmp(UnsignedPred, m_Specific(A), m_Specific(B))) &&
1494  ICmpInst::isUnsigned(UnsignedPred)) {
1495  // A >=/<= B || (A - B) != 0 <--> true
1496  if ((UnsignedPred == ICmpInst::ICMP_UGE ||
1497  UnsignedPred == ICmpInst::ICMP_ULE) &&
1498  EqPred == ICmpInst::ICMP_NE && !IsAnd)
1499  return ConstantInt::getTrue(UnsignedICmp->getType());
1500  // A </> B && (A - B) == 0 <--> false
1501  if ((UnsignedPred == ICmpInst::ICMP_ULT ||
1502  UnsignedPred == ICmpInst::ICMP_UGT) &&
1503  EqPred == ICmpInst::ICMP_EQ && IsAnd)
1504  return ConstantInt::getFalse(UnsignedICmp->getType());
1505 
1506  // A </> B && (A - B) != 0 <--> A </> B
1507  // A </> B || (A - B) != 0 <--> (A - B) != 0
1508  if (EqPred == ICmpInst::ICMP_NE && (UnsignedPred == ICmpInst::ICMP_ULT ||
1509  UnsignedPred == ICmpInst::ICMP_UGT))
1510  return IsAnd ? UnsignedICmp : ZeroICmp;
1511 
1512  // A <=/>= B && (A - B) == 0 <--> (A - B) == 0
1513  // A <=/>= B || (A - B) == 0 <--> A <=/>= B
1514  if (EqPred == ICmpInst::ICMP_EQ && (UnsignedPred == ICmpInst::ICMP_ULE ||
1515  UnsignedPred == ICmpInst::ICMP_UGE))
1516  return IsAnd ? ZeroICmp : UnsignedICmp;
1517  }
1518 
1519  // Given Y = (A - B)
1520  // Y >= A && Y != 0 --> Y >= A iff B != 0
1521  // Y < A || Y == 0 --> Y < A iff B != 0
1522  if (match(UnsignedICmp,
1523  m_c_ICmp(UnsignedPred, m_Specific(Y), m_Specific(A)))) {
1524  if (UnsignedPred == ICmpInst::ICMP_UGE && IsAnd &&
1525  EqPred == ICmpInst::ICMP_NE &&
1526  isKnownNonZero(B, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT))
1527  return UnsignedICmp;
1528  if (UnsignedPred == ICmpInst::ICMP_ULT && !IsAnd &&
1529  EqPred == ICmpInst::ICMP_EQ &&
1530  isKnownNonZero(B, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT))
1531  return UnsignedICmp;
1532  }
1533  }
1534 
1535  if (match(UnsignedICmp, m_ICmp(UnsignedPred, m_Value(X), m_Specific(Y))) &&
1536  ICmpInst::isUnsigned(UnsignedPred))
1537  ;
1538  else if (match(UnsignedICmp,
1539  m_ICmp(UnsignedPred, m_Specific(Y), m_Value(X))) &&
1540  ICmpInst::isUnsigned(UnsignedPred))
1541  UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred);
1542  else
1543  return nullptr;
1544 
1545  // X > Y && Y == 0 --> Y == 0 iff X != 0
1546  // X > Y || Y == 0 --> X > Y iff X != 0
1547  if (UnsignedPred == ICmpInst::ICMP_UGT && EqPred == ICmpInst::ICMP_EQ &&
1548  isKnownNonZero(X, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT))
1549  return IsAnd ? ZeroICmp : UnsignedICmp;
1550 
1551  // X <= Y && Y != 0 --> X <= Y iff X != 0
1552  // X <= Y || Y != 0 --> Y != 0 iff X != 0
1553  if (UnsignedPred == ICmpInst::ICMP_ULE && EqPred == ICmpInst::ICMP_NE &&
1554  isKnownNonZero(X, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT))
1555  return IsAnd ? UnsignedICmp : ZeroICmp;
1556 
1557  // The transforms below here are expected to be handled more generally with
1558  // simplifyAndOrOfICmpsWithLimitConst() or in InstCombine's
1559  // foldAndOrOfICmpsWithConstEq(). If we are looking to trim optimizer overlap,
1560  // these are candidates for removal.
1561 
1562  // X < Y && Y != 0 --> X < Y
1563  // X < Y || Y != 0 --> Y != 0
1564  if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_NE)
1565  return IsAnd ? UnsignedICmp : ZeroICmp;
1566 
1567  // X >= Y && Y == 0 --> Y == 0
1568  // X >= Y || Y == 0 --> X >= Y
1569  if (UnsignedPred == ICmpInst::ICMP_UGE && EqPred == ICmpInst::ICMP_EQ)
1570  return IsAnd ? ZeroICmp : UnsignedICmp;
1571 
1572  // X < Y && Y == 0 --> false
1573  if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_EQ &&
1574  IsAnd)
1575  return getFalse(UnsignedICmp->getType());
1576 
1577  // X >= Y || Y != 0 --> true
1578  if (UnsignedPred == ICmpInst::ICMP_UGE && EqPred == ICmpInst::ICMP_NE &&
1579  !IsAnd)
1580  return getTrue(UnsignedICmp->getType());
1581 
1582  return nullptr;
1583 }
1584 
1585 /// Commuted variants are assumed to be handled by calling this function again
1586 /// with the parameters swapped.
1588  ICmpInst::Predicate Pred0, Pred1;
1589  Value *A, *B;
1590  if (!match(Op0, m_ICmp(Pred0, m_Value(A), m_Value(B))) ||
1591  !match(Op1, m_ICmp(Pred1, m_Specific(A), m_Specific(B))))
1592  return nullptr;
1593 
1594  // We have (icmp Pred0, A, B) & (icmp Pred1, A, B).
1595  // If Op1 is always implied true by Op0, then Op0 is a subset of Op1, and we
1596  // can eliminate Op1 from this 'and'.
1597  if (ICmpInst::isImpliedTrueByMatchingCmp(Pred0, Pred1))
1598  return Op0;
1599 
1600  // Check for any combination of predicates that are guaranteed to be disjoint.
1601  if ((Pred0 == ICmpInst::getInversePredicate(Pred1)) ||
1602  (Pred0 == ICmpInst::ICMP_EQ && ICmpInst::isFalseWhenEqual(Pred1)) ||
1603  (Pred0 == ICmpInst::ICMP_SLT && Pred1 == ICmpInst::ICMP_SGT) ||
1604  (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_UGT))
1605  return getFalse(Op0->getType());
1606 
1607  return nullptr;
1608 }
1609 
1610 /// Commuted variants are assumed to be handled by calling this function again
1611 /// with the parameters swapped.
1613  ICmpInst::Predicate Pred0, Pred1;
1614  Value *A, *B;
1615  if (!match(Op0, m_ICmp(Pred0, m_Value(A), m_Value(B))) ||
1616  !match(Op1, m_ICmp(Pred1, m_Specific(A), m_Specific(B))))
1617  return nullptr;
1618 
1619  // We have (icmp Pred0, A, B) | (icmp Pred1, A, B).
1620  // If Op1 is always implied true by Op0, then Op0 is a subset of Op1, and we
1621  // can eliminate Op0 from this 'or'.
1622  if (ICmpInst::isImpliedTrueByMatchingCmp(Pred0, Pred1))
1623  return Op1;
1624 
1625  // Check for any combination of predicates that cover the entire range of
1626  // possibilities.
1627  if ((Pred0 == ICmpInst::getInversePredicate(Pred1)) ||
1628  (Pred0 == ICmpInst::ICMP_NE && ICmpInst::isTrueWhenEqual(Pred1)) ||
1629  (Pred0 == ICmpInst::ICMP_SLE && Pred1 == ICmpInst::ICMP_SGE) ||
1630  (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_UGE))
1631  return getTrue(Op0->getType());
1632 
1633  return nullptr;
1634 }
1635 
1636 /// Test if a pair of compares with a shared operand and 2 constants has an
1637 /// empty set intersection, full set union, or if one compare is a superset of
1638 /// the other.
1640  bool IsAnd) {
1641  // Look for this pattern: {and/or} (icmp X, C0), (icmp X, C1)).
1642  if (Cmp0->getOperand(0) != Cmp1->getOperand(0))
1643  return nullptr;
1644 
1645  const APInt *C0, *C1;
1646  if (!match(Cmp0->getOperand(1), m_APInt(C0)) ||
1647  !match(Cmp1->getOperand(1), m_APInt(C1)))
1648  return nullptr;
1649 
1650  auto Range0 = ConstantRange::makeExactICmpRegion(Cmp0->getPredicate(), *C0);
1651  auto Range1 = ConstantRange::makeExactICmpRegion(Cmp1->getPredicate(), *C1);
1652 
1653  // For and-of-compares, check if the intersection is empty:
1654  // (icmp X, C0) && (icmp X, C1) --> empty set --> false
1655  if (IsAnd && Range0.intersectWith(Range1).isEmptySet())
1656  return getFalse(Cmp0->getType());
1657 
1658  // For or-of-compares, check if the union is full:
1659  // (icmp X, C0) || (icmp X, C1) --> full set --> true
1660  if (!IsAnd && Range0.unionWith(Range1).isFullSet())
1661  return getTrue(Cmp0->getType());
1662 
1663  // Is one range a superset of the other?
1664  // If this is and-of-compares, take the smaller set:
1665  // (icmp sgt X, 4) && (icmp sgt X, 42) --> icmp sgt X, 42
1666  // If this is or-of-compares, take the larger set:
1667  // (icmp sgt X, 4) || (icmp sgt X, 42) --> icmp sgt X, 4
1668  if (Range0.contains(Range1))
1669  return IsAnd ? Cmp1 : Cmp0;
1670  if (Range1.contains(Range0))
1671  return IsAnd ? Cmp0 : Cmp1;
1672 
1673  return nullptr;
1674 }
1675 
1677  bool IsAnd) {
1678  ICmpInst::Predicate P0 = Cmp0->getPredicate(), P1 = Cmp1->getPredicate();
1679  if (!match(Cmp0->getOperand(1), m_Zero()) ||
1680  !match(Cmp1->getOperand(1), m_Zero()) || P0 != P1)
1681  return nullptr;
1682 
1683  if ((IsAnd && P0 != ICmpInst::ICMP_NE) || (!IsAnd && P1 != ICmpInst::ICMP_EQ))
1684  return nullptr;
1685 
1686  // We have either "(X == 0 || Y == 0)" or "(X != 0 && Y != 0)".
1687  Value *X = Cmp0->getOperand(0);
1688  Value *Y = Cmp1->getOperand(0);
1689 
1690  // If one of the compares is a masked version of a (not) null check, then
1691  // that compare implies the other, so we eliminate the other. Optionally, look
1692  // through a pointer-to-int cast to match a null check of a pointer type.
1693 
1694  // (X == 0) || (([ptrtoint] X & ?) == 0) --> ([ptrtoint] X & ?) == 0
1695  // (X == 0) || ((? & [ptrtoint] X) == 0) --> (? & [ptrtoint] X) == 0
1696  // (X != 0) && (([ptrtoint] X & ?) != 0) --> ([ptrtoint] X & ?) != 0
1697  // (X != 0) && ((? & [ptrtoint] X) != 0) --> (? & [ptrtoint] X) != 0
1698  if (match(Y, m_c_And(m_Specific(X), m_Value())) ||
1700  return Cmp1;
1701 
1702  // (([ptrtoint] Y & ?) == 0) || (Y == 0) --> ([ptrtoint] Y & ?) == 0
1703  // ((? & [ptrtoint] Y) == 0) || (Y == 0) --> (? & [ptrtoint] Y) == 0
1704  // (([ptrtoint] Y & ?) != 0) && (Y != 0) --> ([ptrtoint] Y & ?) != 0
1705  // ((? & [ptrtoint] Y) != 0) && (Y != 0) --> (? & [ptrtoint] Y) != 0
1706  if (match(X, m_c_And(m_Specific(Y), m_Value())) ||
1708  return Cmp0;
1709 
1710  return nullptr;
1711 }
1712 
1714  const InstrInfoQuery &IIQ) {
1715  // (icmp (add V, C0), C1) & (icmp V, C0)
1716  ICmpInst::Predicate Pred0, Pred1;
1717  const APInt *C0, *C1;
1718  Value *V;
1719  if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_APInt(C0)), m_APInt(C1))))
1720  return nullptr;
1721 
1722  if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Value())))
1723  return nullptr;
1724 
1725  auto *AddInst = cast<OverflowingBinaryOperator>(Op0->getOperand(0));
1726  if (AddInst->getOperand(1) != Op1->getOperand(1))
1727  return nullptr;
1728 
1729  Type *ITy = Op0->getType();
1730  bool isNSW = IIQ.hasNoSignedWrap(AddInst);
1731  bool isNUW = IIQ.hasNoUnsignedWrap(AddInst);
1732 
1733  const APInt Delta = *C1 - *C0;
1734  if (C0->isStrictlyPositive()) {
1735  if (Delta == 2) {
1736  if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_SGT)
1737  return getFalse(ITy);
1738  if (Pred0 == ICmpInst::ICMP_SLT && Pred1 == ICmpInst::ICMP_SGT && isNSW)
1739  return getFalse(ITy);
1740  }
1741  if (Delta == 1) {
1742  if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_SGT)
1743  return getFalse(ITy);
1744  if (Pred0 == ICmpInst::ICMP_SLE && Pred1 == ICmpInst::ICMP_SGT && isNSW)
1745  return getFalse(ITy);
1746  }
1747  }
1748  if (C0->getBoolValue() && isNUW) {
1749  if (Delta == 2)
1750  if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_UGT)
1751  return getFalse(ITy);
1752  if (Delta == 1)
1753  if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_UGT)
1754  return getFalse(ITy);
1755  }
1756 
1757  return nullptr;
1758 }
1759 
1760 /// Try to eliminate compares with signed or unsigned min/max constants.
1762  bool IsAnd) {
1763  // Canonicalize an equality compare as Cmp0.
1764  if (Cmp1->isEquality())
1765  std::swap(Cmp0, Cmp1);
1766  if (!Cmp0->isEquality())
1767  return nullptr;
1768 
1769  // The non-equality compare must include a common operand (X). Canonicalize
1770  // the common operand as operand 0 (the predicate is swapped if the common
1771  // operand was operand 1).
1772  ICmpInst::Predicate Pred0 = Cmp0->getPredicate();
1773  Value *X = Cmp0->getOperand(0);
1774  ICmpInst::Predicate Pred1;
1775  bool HasNotOp = match(Cmp1, m_c_ICmp(Pred1, m_Not(m_Specific(X)), m_Value()));
1776  if (!HasNotOp && !match(Cmp1, m_c_ICmp(Pred1, m_Specific(X), m_Value())))
1777  return nullptr;
1778  if (ICmpInst::isEquality(Pred1))
1779  return nullptr;
1780 
1781  // The equality compare must be against a constant. Flip bits if we matched
1782  // a bitwise not. Convert a null pointer constant to an integer zero value.
1783  APInt MinMaxC;
1784  const APInt *C;
1785  if (match(Cmp0->getOperand(1), m_APInt(C)))
1786  MinMaxC = HasNotOp ? ~*C : *C;
1787  else if (isa<ConstantPointerNull>(Cmp0->getOperand(1)))
1788  MinMaxC = APInt::getZero(8);
1789  else
1790  return nullptr;
1791 
1792  // DeMorganize if this is 'or': P0 || P1 --> !P0 && !P1.
1793  if (!IsAnd) {
1794  Pred0 = ICmpInst::getInversePredicate(Pred0);
1795  Pred1 = ICmpInst::getInversePredicate(Pred1);
1796  }
1797 
1798  // Normalize to unsigned compare and unsigned min/max value.
1799  // Example for 8-bit: -128 + 128 -> 0; 127 + 128 -> 255
1800  if (ICmpInst::isSigned(Pred1)) {
1801  Pred1 = ICmpInst::getUnsignedPredicate(Pred1);
1802  MinMaxC += APInt::getSignedMinValue(MinMaxC.getBitWidth());
1803  }
1804 
1805  // (X != MAX) && (X < Y) --> X < Y
1806  // (X == MAX) || (X >= Y) --> X >= Y
1807  if (MinMaxC.isMaxValue())
1808  if (Pred0 == ICmpInst::ICMP_NE && Pred1 == ICmpInst::ICMP_ULT)
1809  return Cmp1;
1810 
1811  // (X != MIN) && (X > Y) --> X > Y
1812  // (X == MIN) || (X <= Y) --> X <= Y
1813  if (MinMaxC.isMinValue())
1814  if (Pred0 == ICmpInst::ICMP_NE && Pred1 == ICmpInst::ICMP_UGT)
1815  return Cmp1;
1816 
1817  return nullptr;
1818 }
1819 
1820 /// Try to simplify and/or of icmp with ctpop intrinsic.
1822  bool IsAnd) {
1823  ICmpInst::Predicate Pred0, Pred1;
1824  Value *X;
1825  const APInt *C;
1826  if (!match(Cmp0, m_ICmp(Pred0, m_Intrinsic<Intrinsic::ctpop>(m_Value(X)),
1827  m_APInt(C))) ||
1828  !match(Cmp1, m_ICmp(Pred1, m_Specific(X), m_ZeroInt())) || C->isZero())
1829  return nullptr;
1830 
1831  // (ctpop(X) == C) || (X != 0) --> X != 0 where C > 0
1832  if (!IsAnd && Pred0 == ICmpInst::ICMP_EQ && Pred1 == ICmpInst::ICMP_NE)
1833  return Cmp1;
1834  // (ctpop(X) != C) && (X == 0) --> X == 0 where C > 0
1835  if (IsAnd && Pred0 == ICmpInst::ICMP_NE && Pred1 == ICmpInst::ICMP_EQ)
1836  return Cmp1;
1837 
1838  return nullptr;
1839 }
1840 
1842  const SimplifyQuery &Q) {
1843  if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/true, Q))
1844  return X;
1845  if (Value *X = simplifyUnsignedRangeCheck(Op1, Op0, /*IsAnd=*/true, Q))
1846  return X;
1847 
1848  if (Value *X = simplifyAndOfICmpsWithSameOperands(Op0, Op1))
1849  return X;
1850  if (Value *X = simplifyAndOfICmpsWithSameOperands(Op1, Op0))
1851  return X;
1852 
1853  if (Value *X = simplifyAndOrOfICmpsWithConstants(Op0, Op1, true))
1854  return X;
1855 
1856  if (Value *X = simplifyAndOrOfICmpsWithLimitConst(Op0, Op1, true))
1857  return X;
1858 
1859  if (Value *X = simplifyAndOrOfICmpsWithZero(Op0, Op1, true))
1860  return X;
1861 
1862  if (Value *X = simplifyAndOrOfICmpsWithCtpop(Op0, Op1, true))
1863  return X;
1864  if (Value *X = simplifyAndOrOfICmpsWithCtpop(Op1, Op0, true))
1865  return X;
1866 
1867  if (Value *X = simplifyAndOfICmpsWithAdd(Op0, Op1, Q.IIQ))
1868  return X;
1869  if (Value *X = simplifyAndOfICmpsWithAdd(Op1, Op0, Q.IIQ))
1870  return X;
1871 
1872  return nullptr;
1873 }
1874 
1876  const InstrInfoQuery &IIQ) {
1877  // (icmp (add V, C0), C1) | (icmp V, C0)
1878  ICmpInst::Predicate Pred0, Pred1;
1879  const APInt *C0, *C1;
1880  Value *V;
1881  if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_APInt(C0)), m_APInt(C1))))
1882  return nullptr;
1883 
1884  if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Value())))
1885  return nullptr;
1886 
1887  auto *AddInst = cast<BinaryOperator>(Op0->getOperand(0));
1888  if (AddInst->getOperand(1) != Op1->getOperand(1))
1889  return nullptr;
1890 
1891  Type *ITy = Op0->getType();
1892  bool isNSW = IIQ.hasNoSignedWrap(AddInst);
1893  bool isNUW = IIQ.hasNoUnsignedWrap(AddInst);
1894 
1895  const APInt Delta = *C1 - *C0;
1896  if (C0->isStrictlyPositive()) {
1897  if (Delta == 2) {
1898  if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_SLE)
1899  return getTrue(ITy);
1900  if (Pred0 == ICmpInst::ICMP_SGE && Pred1 == ICmpInst::ICMP_SLE && isNSW)
1901  return getTrue(ITy);
1902  }
1903  if (Delta == 1) {
1904  if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_SLE)
1905  return getTrue(ITy);
1906  if (Pred0 == ICmpInst::ICMP_SGT && Pred1 == ICmpInst::ICMP_SLE && isNSW)
1907  return getTrue(ITy);
1908  }
1909  }
1910  if (C0->getBoolValue() && isNUW) {
1911  if (Delta == 2)
1912  if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_ULE)
1913  return getTrue(ITy);
1914  if (Delta == 1)
1915  if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_ULE)
1916  return getTrue(ITy);
1917  }
1918 
1919  return nullptr;
1920 }
1921 
1923  const SimplifyQuery &Q) {
1924  if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/false, Q))
1925  return X;
1926  if (Value *X = simplifyUnsignedRangeCheck(Op1, Op0, /*IsAnd=*/false, Q))
1927  return X;
1928 
1929  if (Value *X = simplifyOrOfICmpsWithSameOperands(Op0, Op1))
1930  return X;
1931  if (Value *X = simplifyOrOfICmpsWithSameOperands(Op1, Op0))
1932  return X;
1933 
1934  if (Value *X = simplifyAndOrOfICmpsWithConstants(Op0, Op1, false))
1935  return X;
1936 
1937  if (Value *X = simplifyAndOrOfICmpsWithLimitConst(Op0, Op1, false))
1938  return X;
1939 
1940  if (Value *X = simplifyAndOrOfICmpsWithZero(Op0, Op1, false))
1941  return X;
1942 
1943  if (Value *X = simplifyAndOrOfICmpsWithCtpop(Op0, Op1, false))
1944  return X;
1945  if (Value *X = simplifyAndOrOfICmpsWithCtpop(Op1, Op0, false))
1946  return X;
1947 
1948  if (Value *X = simplifyOrOfICmpsWithAdd(Op0, Op1, Q.IIQ))
1949  return X;
1950  if (Value *X = simplifyOrOfICmpsWithAdd(Op1, Op0, Q.IIQ))
1951  return X;
1952 
1953  return nullptr;
1954 }
1955 
1957  FCmpInst *RHS, bool IsAnd) {
1958  Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1);
1959  Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1);
1960  if (LHS0->getType() != RHS0->getType())
1961  return nullptr;
1962 
1963  FCmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
1964  if ((PredL == FCmpInst::FCMP_ORD && PredR == FCmpInst::FCMP_ORD && IsAnd) ||
1965  (PredL == FCmpInst::FCMP_UNO && PredR == FCmpInst::FCMP_UNO && !IsAnd)) {
1966  // (fcmp ord NNAN, X) & (fcmp ord X, Y) --> fcmp ord X, Y
1967  // (fcmp ord NNAN, X) & (fcmp ord Y, X) --> fcmp ord Y, X
1968  // (fcmp ord X, NNAN) & (fcmp ord X, Y) --> fcmp ord X, Y
1969  // (fcmp ord X, NNAN) & (fcmp ord Y, X) --> fcmp ord Y, X
1970  // (fcmp uno NNAN, X) | (fcmp uno X, Y) --> fcmp uno X, Y
1971  // (fcmp uno NNAN, X) | (fcmp uno Y, X) --> fcmp uno Y, X
1972  // (fcmp uno X, NNAN) | (fcmp uno X, Y) --> fcmp uno X, Y
1973  // (fcmp uno X, NNAN) | (fcmp uno Y, X) --> fcmp uno Y, X
1974  if ((isKnownNeverNaN(LHS0, TLI) && (LHS1 == RHS0 || LHS1 == RHS1)) ||
1975  (isKnownNeverNaN(LHS1, TLI) && (LHS0 == RHS0 || LHS0 == RHS1)))
1976  return RHS;
1977 
1978  // (fcmp ord X, Y) & (fcmp ord NNAN, X) --> fcmp ord X, Y
1979  // (fcmp ord Y, X) & (fcmp ord NNAN, X) --> fcmp ord Y, X
1980  // (fcmp ord X, Y) & (fcmp ord X, NNAN) --> fcmp ord X, Y
1981  // (fcmp ord Y, X) & (fcmp ord X, NNAN) --> fcmp ord Y, X
1982  // (fcmp uno X, Y) | (fcmp uno NNAN, X) --> fcmp uno X, Y
1983  // (fcmp uno Y, X) | (fcmp uno NNAN, X) --> fcmp uno Y, X
1984  // (fcmp uno X, Y) | (fcmp uno X, NNAN) --> fcmp uno X, Y
1985  // (fcmp uno Y, X) | (fcmp uno X, NNAN) --> fcmp uno Y, X
1986  if ((isKnownNeverNaN(RHS0, TLI) && (RHS1 == LHS0 || RHS1 == LHS1)) ||
1987  (isKnownNeverNaN(RHS1, TLI) && (RHS0 == LHS0 || RHS0 == LHS1)))
1988  return LHS;
1989  }
1990 
1991  return nullptr;
1992 }
1993 
1995  Value *Op1, bool IsAnd) {
1996  // Look through casts of the 'and' operands to find compares.
1997  auto *Cast0 = dyn_cast<CastInst>(Op0);
1998  auto *Cast1 = dyn_cast<CastInst>(Op1);
1999  if (Cast0 && Cast1 && Cast0->getOpcode() == Cast1->getOpcode() &&
2000  Cast0->getSrcTy() == Cast1->getSrcTy()) {
2001  Op0 = Cast0->getOperand(0);
2002  Op1 = Cast1->getOperand(0);
2003  }
2004 
2005  Value *V = nullptr;
2006  auto *ICmp0 = dyn_cast<ICmpInst>(Op0);
2007  auto *ICmp1 = dyn_cast<ICmpInst>(Op1);
2008  if (ICmp0 && ICmp1)
2009  V = IsAnd ? simplifyAndOfICmps(ICmp0, ICmp1, Q)
2010  : simplifyOrOfICmps(ICmp0, ICmp1, Q);
2011 
2012  auto *FCmp0 = dyn_cast<FCmpInst>(Op0);
2013  auto *FCmp1 = dyn_cast<FCmpInst>(Op1);
2014  if (FCmp0 && FCmp1)
2015  V = simplifyAndOrOfFCmps(Q.TLI, FCmp0, FCmp1, IsAnd);
2016 
2017  if (!V)
2018  return nullptr;
2019  if (!Cast0)
2020  return V;
2021 
2022  // If we looked through casts, we can only handle a constant simplification
2023  // because we are not allowed to create a cast instruction here.
2024  if (auto *C = dyn_cast<Constant>(V))
2025  return ConstantExpr::getCast(Cast0->getOpcode(), C, Cast0->getType());
2026 
2027  return nullptr;
2028 }
2029 
2030 /// Given a bitwise logic op, check if the operands are add/sub with a common
2031 /// source value and inverted constant (identity: C - X -> ~(X + ~C)).
2033  Instruction::BinaryOps Opcode) {
2034  assert(Op0->getType() == Op1->getType() && "Mismatched binop types");
2035  assert(BinaryOperator::isBitwiseLogicOp(Opcode) && "Expected logic op");
2036  Value *X;
2037  Constant *C1, *C2;
2038  if ((match(Op0, m_Add(m_Value(X), m_Constant(C1))) &&
2039  match(Op1, m_Sub(m_Constant(C2), m_Specific(X)))) ||
2040  (match(Op1, m_Add(m_Value(X), m_Constant(C1))) &&
2041  match(Op0, m_Sub(m_Constant(C2), m_Specific(X))))) {
2042  if (ConstantExpr::getNot(C1) == C2) {
2043  // (X + C) & (~C - X) --> (X + C) & ~(X + C) --> 0
2044  // (X + C) | (~C - X) --> (X + C) | ~(X + C) --> -1
2045  // (X + C) ^ (~C - X) --> (X + C) ^ ~(X + C) --> -1
2046  Type *Ty = Op0->getType();
2047  return Opcode == Instruction::And ? ConstantInt::getNullValue(Ty)
2049  }
2050  }
2051  return nullptr;
2052 }
2053 
2054 /// Given operands for an And, see if we can fold the result.
2055 /// If not, this returns null.
2056 static Value *simplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
2057  unsigned MaxRecurse) {
2058  if (Constant *C = foldOrCommuteConstant(Instruction::And, Op0, Op1, Q))
2059  return C;
2060 
2061  // X & poison -> poison
2062  if (isa<PoisonValue>(Op1))
2063  return Op1;
2064 
2065  // X & undef -> 0
2066  if (Q.isUndefValue(Op1))
2067  return Constant::getNullValue(Op0->getType());
2068 
2069  // X & X = X
2070  if (Op0 == Op1)
2071  return Op0;
2072 
2073  // X & 0 = 0
2074  if (match(Op1, m_Zero()))
2075  return Constant::getNullValue(Op0->getType());
2076 
2077  // X & -1 = X
2078  if (match(Op1, m_AllOnes()))
2079  return Op0;
2080 
2081  // A & ~A = ~A & A = 0
2082  if (match(Op0, m_Not(m_Specific(Op1))) || match(Op1, m_Not(m_Specific(Op0))))
2083  return Constant::getNullValue(Op0->getType());
2084 
2085  // (A | ?) & A = A
2086  if (match(Op0, m_c_Or(m_Specific(Op1), m_Value())))
2087  return Op1;
2088 
2089  // A & (A | ?) = A
2090  if (match(Op1, m_c_Or(m_Specific(Op0), m_Value())))
2091  return Op0;
2092 
2093  // (X | Y) & (X | ~Y) --> X (commuted 8 ways)
2094  Value *X, *Y;
2095  if (match(Op0, m_c_Or(m_Value(X), m_Not(m_Value(Y)))) &&
2096  match(Op1, m_c_Or(m_Deferred(X), m_Deferred(Y))))
2097  return X;
2098  if (match(Op1, m_c_Or(m_Value(X), m_Not(m_Value(Y)))) &&
2099  match(Op0, m_c_Or(m_Deferred(X), m_Deferred(Y))))
2100  return X;
2101 
2102  if (Value *V = simplifyLogicOfAddSub(Op0, Op1, Instruction::And))
2103  return V;
2104 
2105  // A mask that only clears known zeros of a shifted value is a no-op.
2106  const APInt *Mask;
2107  const APInt *ShAmt;
2108  if (match(Op1, m_APInt(Mask))) {
2109  // If all bits in the inverted and shifted mask are clear:
2110  // and (shl X, ShAmt), Mask --> shl X, ShAmt
2111  if (match(Op0, m_Shl(m_Value(X), m_APInt(ShAmt))) &&
2112  (~(*Mask)).lshr(*ShAmt).isZero())
2113  return Op0;
2114 
2115  // If all bits in the inverted and shifted mask are clear:
2116  // and (lshr X, ShAmt), Mask --> lshr X, ShAmt
2117  if (match(Op0, m_LShr(m_Value(X), m_APInt(ShAmt))) &&
2118  (~(*Mask)).shl(*ShAmt).isZero())
2119  return Op0;
2120  }
2121 
2122  // If we have a multiplication overflow check that is being 'and'ed with a
2123  // check that one of the multipliers is not zero, we can omit the 'and', and
2124  // only keep the overflow check.
2125  if (isCheckForZeroAndMulWithOverflow(Op0, Op1, true))
2126  return Op1;
2127  if (isCheckForZeroAndMulWithOverflow(Op1, Op0, true))
2128  return Op0;
2129 
2130  // A & (-A) = A if A is a power of two or zero.
2131  if (match(Op0, m_Neg(m_Specific(Op1))) ||
2132  match(Op1, m_Neg(m_Specific(Op0)))) {
2133  if (isKnownToBeAPowerOfTwo(Op0, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI,
2134  Q.DT))
2135  return Op0;
2136  if (isKnownToBeAPowerOfTwo(Op1, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI,
2137  Q.DT))
2138  return Op1;
2139  }
2140 
2141  // This is a similar pattern used for checking if a value is a power-of-2:
2142  // (A - 1) & A --> 0 (if A is a power-of-2 or 0)
2143  // A & (A - 1) --> 0 (if A is a power-of-2 or 0)
2144  if (match(Op0, m_Add(m_Specific(Op1), m_AllOnes())) &&
2145  isKnownToBeAPowerOfTwo(Op1, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI, Q.DT))
2146  return Constant::getNullValue(Op1->getType());
2147  if (match(Op1, m_Add(m_Specific(Op0), m_AllOnes())) &&
2148  isKnownToBeAPowerOfTwo(Op0, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI, Q.DT))
2149  return Constant::getNullValue(Op0->getType());
2150 
2151  if (Value *V = simplifyAndOrOfCmps(Q, Op0, Op1, true))
2152  return V;
2153 
2154  // Try some generic simplifications for associative operations.
2155  if (Value *V =
2156  simplifyAssociativeBinOp(Instruction::And, Op0, Op1, Q, MaxRecurse))
2157  return V;
2158 
2159  // And distributes over Or. Try some generic simplifications based on this.
2160  if (Value *V = expandCommutativeBinOp(Instruction::And, Op0, Op1,
2161  Instruction::Or, Q, MaxRecurse))
2162  return V;
2163 
2164  // And distributes over Xor. Try some generic simplifications based on this.
2165  if (Value *V = expandCommutativeBinOp(Instruction::And, Op0, Op1,
2166  Instruction::Xor, Q, MaxRecurse))
2167  return V;
2168 
2169  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) {
2170  if (Op0->getType()->isIntOrIntVectorTy(1)) {
2171  // A & (A && B) -> A && B
2172  if (match(Op1, m_Select(m_Specific(Op0), m_Value(), m_Zero())))
2173  return Op1;
2174  else if (match(Op0, m_Select(m_Specific(Op1), m_Value(), m_Zero())))
2175  return Op0;
2176  }
2177  // If the operation is with the result of a select instruction, check
2178  // whether operating on either branch of the select always yields the same
2179  // value.
2180  if (Value *V =
2181  threadBinOpOverSelect(Instruction::And, Op0, Op1, Q, MaxRecurse))
2182  return V;
2183  }
2184 
2185  // If the operation is with the result of a phi instruction, check whether
2186  // operating on all incoming values of the phi always yields the same value.
2187  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
2188  if (Value *V =
2189  threadBinOpOverPHI(Instruction::And, Op0, Op1, Q, MaxRecurse))
2190  return V;
2191 
2192  // Assuming the effective width of Y is not larger than A, i.e. all bits
2193  // from X and Y are disjoint in (X << A) | Y,
2194  // if the mask of this AND op covers all bits of X or Y, while it covers
2195  // no bits from the other, we can bypass this AND op. E.g.,
2196  // ((X << A) | Y) & Mask -> Y,
2197  // if Mask = ((1 << effective_width_of(Y)) - 1)
2198  // ((X << A) | Y) & Mask -> X << A,
2199  // if Mask = ((1 << effective_width_of(X)) - 1) << A
2200  // SimplifyDemandedBits in InstCombine can optimize the general case.
2201  // This pattern aims to help other passes for a common case.
2202  Value *XShifted;
2203  if (match(Op1, m_APInt(Mask)) &&
2205  m_Value(XShifted)),
2206  m_Value(Y)))) {
2207  const unsigned Width = Op0->getType()->getScalarSizeInBits();
2208  const unsigned ShftCnt = ShAmt->getLimitedValue(Width);
2209  const KnownBits YKnown = computeKnownBits(Y, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2210  const unsigned EffWidthY = YKnown.countMaxActiveBits();
2211  if (EffWidthY <= ShftCnt) {
2212  const KnownBits XKnown = computeKnownBits(X, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2213  const unsigned EffWidthX = XKnown.countMaxActiveBits();
2214  const APInt EffBitsY = APInt::getLowBitsSet(Width, EffWidthY);
2215  const APInt EffBitsX = APInt::getLowBitsSet(Width, EffWidthX) << ShftCnt;
2216  // If the mask is extracting all bits from X or Y as is, we can skip
2217  // this AND op.
2218  if (EffBitsY.isSubsetOf(*Mask) && !EffBitsX.intersects(*Mask))
2219  return Y;
2220  if (EffBitsX.isSubsetOf(*Mask) && !EffBitsY.intersects(*Mask))
2221  return XShifted;
2222  }
2223  }
2224 
2225  // ((X | Y) ^ X ) & ((X | Y) ^ Y) --> 0
2226  // ((X | Y) ^ Y ) & ((X | Y) ^ X) --> 0
2227  BinaryOperator *Or;
2228  if (match(Op0, m_c_Xor(m_Value(X),
2230  m_c_Or(m_Deferred(X), m_Value(Y))))) &&
2231  match(Op1, m_c_Xor(m_Specific(Or), m_Specific(Y))))
2232  return Constant::getNullValue(Op0->getType());
2233 
2234  if (Op0->getType()->isIntOrIntVectorTy(1)) {
2235  // Op0&Op1 -> Op0 where Op0 implies Op1
2236  if (isImpliedCondition(Op0, Op1, Q.DL).value_or(false))
2237  return Op0;
2238  // Op0&Op1 -> Op1 where Op1 implies Op0
2239  if (isImpliedCondition(Op1, Op0, Q.DL).value_or(false))
2240  return Op1;
2241  }
2242 
2243  return nullptr;
2244 }
2245 
2248 }
2249 
2251  assert(X->getType() == Y->getType() && "Expected same type for 'or' ops");
2252  Type *Ty = X->getType();
2253 
2254  // X | ~X --> -1
2255  if (match(Y, m_Not(m_Specific(X))))
2256  return ConstantInt::getAllOnesValue(Ty);
2257 
2258  // X | ~(X & ?) = -1
2259  if (match(Y, m_Not(m_c_And(m_Specific(X), m_Value()))))
2260  return ConstantInt::getAllOnesValue(Ty);
2261 
2262  // X | (X & ?) --> X
2263  if (match(Y, m_c_And(m_Specific(X), m_Value())))
2264  return X;
2265 
2266  Value *A, *B;
2267 
2268  // (A ^ B) | (A | B) --> A | B
2269  // (A ^ B) | (B | A) --> B | A
2270  if (match(X, m_Xor(m_Value(A), m_Value(B))) &&
2271  match(Y, m_c_Or(m_Specific(A), m_Specific(B))))
2272  return Y;
2273 
2274  // ~(A ^ B) | (A | B) --> -1
2275  // ~(A ^ B) | (B | A) --> -1
2276  if (match(X, m_Not(m_Xor(m_Value(A), m_Value(B)))) &&
2277  match(Y, m_c_Or(m_Specific(A), m_Specific(B))))
2278  return ConstantInt::getAllOnesValue(Ty);
2279 
2280  // (A & ~B) | (A ^ B) --> A ^ B
2281  // (~B & A) | (A ^ B) --> A ^ B
2282  // (A & ~B) | (B ^ A) --> B ^ A
2283  // (~B & A) | (B ^ A) --> B ^ A
2284  if (match(X, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
2286  return Y;
2287 
2288  // (~A ^ B) | (A & B) --> ~A ^ B
2289  // (B ^ ~A) | (A & B) --> B ^ ~A
2290  // (~A ^ B) | (B & A) --> ~A ^ B
2291  // (B ^ ~A) | (B & A) --> B ^ ~A
2292  if (match(X, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
2294  return X;
2295 
2296  // (~A | B) | (A ^ B) --> -1
2297  // (~A | B) | (B ^ A) --> -1
2298  // (B | ~A) | (A ^ B) --> -1
2299  // (B | ~A) | (B ^ A) --> -1
2300  if (match(X, m_c_Or(m_Not(m_Value(A)), m_Value(B))) &&
2302  return ConstantInt::getAllOnesValue(Ty);
2303 
2304  // (~A & B) | ~(A | B) --> ~A
2305  // (~A & B) | ~(B | A) --> ~A
2306  // (B & ~A) | ~(A | B) --> ~A
2307  // (B & ~A) | ~(B | A) --> ~A
2308  Value *NotA;
2309  if (match(X,
2311  m_Value(B))) &&
2313  return NotA;
2314 
2315  // ~(A ^ B) | (A & B) --> ~(A ^ B)
2316  // ~(A ^ B) | (B & A) --> ~(A ^ B)
2317  Value *NotAB;
2319  m_Value(NotAB))) &&
2321  return NotAB;
2322 
2323  // ~(A & B) | (A ^ B) --> ~(A & B)
2324  // ~(A & B) | (B ^ A) --> ~(A & B)
2326  m_Value(NotAB))) &&
2328  return NotAB;
2329 
2330  return nullptr;
2331 }
2332 
2333 /// Given operands for an Or, see if we can fold the result.
2334 /// If not, this returns null.
2335 static Value *simplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
2336  unsigned MaxRecurse) {
2337  if (Constant *C = foldOrCommuteConstant(Instruction::Or, Op0, Op1, Q))
2338  return C;
2339 
2340  // X | poison -> poison
2341  if (isa<PoisonValue>(Op1))
2342  return Op1;
2343 
2344  // X | undef -> -1
2345  // X | -1 = -1
2346  // Do not return Op1 because it may contain undef elements if it's a vector.
2347  if (Q.isUndefValue(Op1) || match(Op1, m_AllOnes()))
2348  return Constant::getAllOnesValue(Op0->getType());
2349 
2350  // X | X = X
2351  // X | 0 = X
2352  if (Op0 == Op1 || match(Op1, m_Zero()))
2353  return Op0;
2354 
2355  if (Value *R = simplifyOrLogic(Op0, Op1))
2356  return R;
2357  if (Value *R = simplifyOrLogic(Op1, Op0))
2358  return R;
2359 
2360  if (Value *V = simplifyLogicOfAddSub(Op0, Op1, Instruction::Or))
2361  return V;
2362 
2363  // Rotated -1 is still -1:
2364  // (-1 << X) | (-1 >> (C - X)) --> -1
2365  // (-1 >> X) | (-1 << (C - X)) --> -1
2366  // ...with C <= bitwidth (and commuted variants).
2367  Value *X, *Y;
2368  if ((match(Op0, m_Shl(m_AllOnes(), m_Value(X))) &&
2369  match(Op1, m_LShr(m_AllOnes(), m_Value(Y)))) ||
2370  (match(Op1, m_Shl(m_AllOnes(), m_Value(X))) &&
2371  match(Op0, m_LShr(m_AllOnes(), m_Value(Y))))) {
2372  const APInt *C;
2373  if ((match(X, m_Sub(m_APInt(C), m_Specific(Y))) ||
2374  match(Y, m_Sub(m_APInt(C), m_Specific(X)))) &&
2375  C->ule(X->getType()->getScalarSizeInBits())) {
2376  return ConstantInt::getAllOnesValue(X->getType());
2377  }
2378  }
2379 
2380  // A funnel shift (rotate) can be decomposed into simpler shifts. See if we
2381  // are mixing in another shift that is redundant with the funnel shift.
2382 
2383  // (fshl X, ?, Y) | (shl X, Y) --> fshl X, ?, Y
2384  // (shl X, Y) | (fshl X, ?, Y) --> fshl X, ?, Y
2385  if (match(Op0,
2386  m_Intrinsic<Intrinsic::fshl>(m_Value(X), m_Value(), m_Value(Y))) &&
2387  match(Op1, m_Shl(m_Specific(X), m_Specific(Y))))
2388  return Op0;
2389  if (match(Op1,
2390  m_Intrinsic<Intrinsic::fshl>(m_Value(X), m_Value(), m_Value(Y))) &&
2391  match(Op0, m_Shl(m_Specific(X), m_Specific(Y))))
2392  return Op1;
2393 
2394  // (fshr ?, X, Y) | (lshr X, Y) --> fshr ?, X, Y
2395  // (lshr X, Y) | (fshr ?, X, Y) --> fshr ?, X, Y
2396  if (match(Op0,
2397  m_Intrinsic<Intrinsic::fshr>(m_Value(), m_Value(X), m_Value(Y))) &&
2398  match(Op1, m_LShr(m_Specific(X), m_Specific(Y))))
2399  return Op0;
2400  if (match(Op1,
2401  m_Intrinsic<Intrinsic::fshr>(m_Value(), m_Value(X), m_Value(Y))) &&
2402  match(Op0, m_LShr(m_Specific(X), m_Specific(Y))))
2403  return Op1;
2404 
2405  if (Value *V = simplifyAndOrOfCmps(Q, Op0, Op1, false))
2406  return V;
2407 
2408  // If we have a multiplication overflow check that is being 'and'ed with a
2409  // check that one of the multipliers is not zero, we can omit the 'and', and
2410  // only keep the overflow check.
2411  if (isCheckForZeroAndMulWithOverflow(Op0, Op1, false))
2412  return Op1;
2413  if (isCheckForZeroAndMulWithOverflow(Op1, Op0, false))
2414  return Op0;
2415 
2416  // Try some generic simplifications for associative operations.
2417  if (Value *V =
2418  simplifyAssociativeBinOp(Instruction::Or, Op0, Op1, Q, MaxRecurse))
2419  return V;
2420 
2421  // Or distributes over And. Try some generic simplifications based on this.
2422  if (Value *V = expandCommutativeBinOp(Instruction::Or, Op0, Op1,
2423  Instruction::And, Q, MaxRecurse))
2424  return V;
2425 
2426  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) {
2427  if (Op0->getType()->isIntOrIntVectorTy(1)) {
2428  // A | (A || B) -> A || B
2429  if (match(Op1, m_Select(m_Specific(Op0), m_One(), m_Value())))
2430  return Op1;
2431  else if (match(Op0, m_Select(m_Specific(Op1), m_One(), m_Value())))
2432  return Op0;
2433  }
2434  // If the operation is with the result of a select instruction, check
2435  // whether operating on either branch of the select always yields the same
2436  // value.
2437  if (Value *V =
2438  threadBinOpOverSelect(Instruction::Or, Op0, Op1, Q, MaxRecurse))
2439  return V;
2440  }
2441 
2442  // (A & C1)|(B & C2)
2443  Value *A, *B;
2444  const APInt *C1, *C2;
2445  if (match(Op0, m_And(m_Value(A), m_APInt(C1))) &&
2446  match(Op1, m_And(m_Value(B), m_APInt(C2)))) {
2447  if (*C1 == ~*C2) {
2448  // (A & C1)|(B & C2)
2449  // If we have: ((V + N) & C1) | (V & C2)
2450  // .. and C2 = ~C1 and C2 is 0+1+ and (N & C2) == 0
2451  // replace with V+N.
2452  Value *N;
2453  if (C2->isMask() && // C2 == 0+1+
2454  match(A, m_c_Add(m_Specific(B), m_Value(N)))) {
2455  // Add commutes, try both ways.
2456  if (MaskedValueIsZero(N, *C2, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2457  return A;
2458  }
2459  // Or commutes, try both ways.
2460  if (C1->isMask() && match(B, m_c_Add(m_Specific(A), m_Value(N)))) {
2461  // Add commutes, try both ways.
2462  if (MaskedValueIsZero(N, *C1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2463  return B;
2464  }
2465  }
2466  }
2467 
2468  // If the operation is with the result of a phi instruction, check whether
2469  // operating on all incoming values of the phi always yields the same value.
2470  if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
2471  if (Value *V = threadBinOpOverPHI(Instruction::Or, Op0, Op1, Q, MaxRecurse))
2472  return V;
2473 
2474  if (Op0->getType()->isIntOrIntVectorTy(1)) {
2475  // Op0|Op1 -> Op1 where Op0 implies Op1
2476  if (isImpliedCondition(Op0, Op1, Q.DL).value_or(false))
2477  return Op1;
2478  // Op0|Op1 -> Op0 where Op1 implies Op0
2479  if (isImpliedCondition(Op1, Op0, Q.DL).value_or(false))
2480  return Op0;
2481  }
2482 
2483  return nullptr;
2484 }
2485 
2488 }
2489 
2490 /// Given operands for a Xor, see if we can fold the result.
2491 /// If not, this returns null.
2492 static Value *simplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
2493  unsigned MaxRecurse) {
2494  if (Constant *C = foldOrCommuteConstant(Instruction::Xor, Op0, Op1, Q))
2495  return C;
2496 
2497  // X ^ poison -> poison
2498  if (isa<PoisonValue>(Op1))
2499  return Op1;
2500 
2501  // A ^ undef -> undef
2502  if (Q.isUndefValue(Op1))
2503  return Op1;
2504 
2505  // A ^ 0 = A
2506  if (match(Op1, m_Zero()))
2507  return Op0;
2508 
2509  // A ^ A = 0
2510  if (Op0 == Op1)
2511  return Constant::getNullValue(Op0->getType());
2512 
2513  // A ^ ~A = ~A ^ A = -1
2514  if (match(Op0, m_Not(m_Specific(Op1))) || match(Op1, m_Not(m_Specific(Op0))))
2515  return Constant::getAllOnesValue(Op0->getType());
2516 
2517  auto foldAndOrNot = [](Value *X, Value *Y) -> Value * {
2518  Value *A, *B;
2519  // (~A & B) ^ (A | B) --> A -- There are 8 commuted variants.
2520  if (match(X, m_c_And(m_Not(m_Value(A)), m_Value(B))) &&
2521  match(Y, m_c_Or(m_Specific(A), m_Specific(B))))
2522  return A;
2523 
2524  // (~A | B) ^ (A & B) --> ~A -- There are 8 commuted variants.
2525  // The 'not' op must contain a complete -1 operand (no undef elements for
2526  // vector) for the transform to be safe.
2527  Value *NotA;
2528  if (match(X,
2530  m_Value(B))) &&
2532  return NotA;
2533 
2534  return nullptr;
2535  };
2536  if (Value *R = foldAndOrNot(Op0, Op1))
2537  return R;
2538  if (Value *R = foldAndOrNot(Op1, Op0))
2539  return R;
2540 
2541  if (Value *V = simplifyLogicOfAddSub(Op0, Op1, Instruction::Xor))
2542  return V;
2543 
2544  // Try some generic simplifications for associative operations.
2545  if (Value *V =
2546  simplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, Q, MaxRecurse))
2547  return V;
2548 
2549  // Threading Xor over selects and phi nodes is pointless, so don't bother.
2550  // Threading over the select in "A ^ select(cond, B, C)" means evaluating
2551  // "A^B" and "A^C" and seeing if they are equal; but they are equal if and
2552  // only if B and C are equal. If B and C are equal then (since we assume
2553  // that operands have already been simplified) "select(cond, B, C)" should
2554  // have been simplified to the common value of B and C already. Analysing
2555  // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly
2556  // for threading over phi nodes.
2557 
2558  return nullptr;
2559 }
2560 
2563 }
2564 
2566  return CmpInst::makeCmpResultType(Op->getType());
2567 }
2568 
2569 /// Rummage around inside V looking for something equivalent to the comparison
2570 /// "LHS Pred RHS". Return such a value if found, otherwise return null.
2571 /// Helper function for analyzing max/min idioms.
2573  Value *LHS, Value *RHS) {
2574  SelectInst *SI = dyn_cast<SelectInst>(V);
2575  if (!SI)
2576  return nullptr;
2577  CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
2578  if (!Cmp)
2579  return nullptr;
2580  Value *CmpLHS = Cmp->getOperand(0), *CmpRHS = Cmp->getOperand(1);
2581  if (Pred == Cmp->getPredicate() && LHS == CmpLHS && RHS == CmpRHS)
2582  return Cmp;
2583  if (Pred == CmpInst::getSwappedPredicate(Cmp->getPredicate()) &&
2584  LHS == CmpRHS && RHS == CmpLHS)
2585  return Cmp;
2586  return nullptr;
2587 }
2588 
2589 /// Return true if the underlying object (storage) must be disjoint from
2590 /// storage returned by any noalias return call.
2591 static bool isAllocDisjoint(const Value *V) {
2592  // For allocas, we consider only static ones (dynamic
2593  // allocas might be transformed into calls to malloc not simultaneously
2594  // live with the compared-to allocation). For globals, we exclude symbols
2595  // that might be resolve lazily to symbols in another dynamically-loaded
2596  // library (and, thus, could be malloc'ed by the implementation).
2597  if (const AllocaInst *AI = dyn_cast<AllocaInst>(V))
2598  return AI->getParent() && AI->getFunction() && AI->isStaticAlloca();
2599  if (const GlobalValue *GV = dyn_cast<GlobalValue>(V))
2600  return (GV->hasLocalLinkage() || GV->hasHiddenVisibility() ||
2601  GV->hasProtectedVisibility() || GV->hasGlobalUnnamedAddr()) &&
2602  !GV->isThreadLocal();
2603  if (const Argument *A = dyn_cast<Argument>(V))
2604  return A->hasByValAttr();
2605  return false;
2606 }
2607 
2608 /// Return true if V1 and V2 are each the base of some distict storage region
2609 /// [V, object_size(V)] which do not overlap. Note that zero sized regions
2610 /// *are* possible, and that zero sized regions do not overlap with any other.
2611 static bool haveNonOverlappingStorage(const Value *V1, const Value *V2) {
2612  // Global variables always exist, so they always exist during the lifetime
2613  // of each other and all allocas. Global variables themselves usually have
2614  // non-overlapping storage, but since their addresses are constants, the
2615  // case involving two globals does not reach here and is instead handled in
2616  // constant folding.
2617  //
2618  // Two different allocas usually have different addresses...
2619  //
2620  // However, if there's an @llvm.stackrestore dynamically in between two
2621  // allocas, they may have the same address. It's tempting to reduce the
2622  // scope of the problem by only looking at *static* allocas here. That would
2623  // cover the majority of allocas while significantly reducing the likelihood
2624  // of having an @llvm.stackrestore pop up in the middle. However, it's not
2625  // actually impossible for an @llvm.stackrestore to pop up in the middle of
2626  // an entry block. Also, if we have a block that's not attached to a
2627  // function, we can't tell if it's "static" under the current definition.
2628  // Theoretically, this problem could be fixed by creating a new kind of
2629  // instruction kind specifically for static allocas. Such a new instruction
2630  // could be required to be at the top of the entry block, thus preventing it
2631  // from being subject to a @llvm.stackrestore. Instcombine could even
2632  // convert regular allocas into these special allocas. It'd be nifty.
2633  // However, until then, this problem remains open.
2634  //
2635  // So, we'll assume that two non-empty allocas have different addresses
2636  // for now.
2637  auto isByValArg = [](const Value *V) {
2638  const Argument *A = dyn_cast<Argument>(V);
2639  return A && A->hasByValAttr();
2640  };
2641 
2642  // Byval args are backed by store which does not overlap with each other,
2643  // allocas, or globals.
2644  if (isByValArg(V1))
2645  return isa<AllocaInst>(V2) || isa<GlobalVariable>(V2) || isByValArg(V2);
2646  if (isByValArg(V2))
2647  return isa<AllocaInst>(V1) || isa<GlobalVariable>(V1) || isByValArg(V1);
2648 
2649  return isa<AllocaInst>(V1) &&
2650  (isa<AllocaInst>(V2) || isa<GlobalVariable>(V2));
2651 }
2652 
2653 // A significant optimization not implemented here is assuming that alloca
2654 // addresses are not equal to incoming argument values. They don't *alias*,
2655 // as we say, but that doesn't mean they aren't equal, so we take a
2656 // conservative approach.
2657 //
2658 // This is inspired in part by C++11 5.10p1:
2659 // "Two pointers of the same type compare equal if and only if they are both
2660 // null, both point to the same function, or both represent the same
2661 // address."
2662 //
2663 // This is pretty permissive.
2664 //
2665 // It's also partly due to C11 6.5.9p6:
2666 // "Two pointers compare equal if and only if both are null pointers, both are
2667 // pointers to the same object (including a pointer to an object and a
2668 // subobject at its beginning) or function, both are pointers to one past the
2669 // last element of the same array object, or one is a pointer to one past the
2670 // end of one array object and the other is a pointer to the start of a
2671 // different array object that happens to immediately follow the first array
2672 // object in the address space.)
2673 //
2674 // C11's version is more restrictive, however there's no reason why an argument
2675 // couldn't be a one-past-the-end value for a stack object in the caller and be
2676 // equal to the beginning of a stack object in the callee.
2677 //
2678 // If the C and C++ standards are ever made sufficiently restrictive in this
2679 // area, it may be possible to update LLVM's semantics accordingly and reinstate
2680 // this optimization.
2682  Value *RHS, const SimplifyQuery &Q) {
2683  const DataLayout &DL = Q.DL;
2684  const TargetLibraryInfo *TLI = Q.TLI;
2685  const DominatorTree *DT = Q.DT;
2686  const Instruction *CxtI = Q.CxtI;
2687  const InstrInfoQuery &IIQ = Q.IIQ;
2688 
2689  // First, skip past any trivial no-ops.
2690  LHS = LHS->stripPointerCasts();
2691  RHS = RHS->stripPointerCasts();
2692 
2693  // A non-null pointer is not equal to a null pointer.
2694  if (isa<ConstantPointerNull>(RHS) && ICmpInst::isEquality(Pred) &&
2695  llvm::isKnownNonZero(LHS, DL, 0, nullptr, nullptr, nullptr,
2696  IIQ.UseInstrInfo))
2698 
2699  // We can only fold certain predicates on pointer comparisons.
2700  switch (Pred) {
2701  default:
2702  return nullptr;
2703 
2704  // Equality comaprisons are easy to fold.
2705  case CmpInst::ICMP_EQ:
2706  case CmpInst::ICMP_NE:
2707  break;
2708 
2709  // We can only handle unsigned relational comparisons because 'inbounds' on
2710  // a GEP only protects against unsigned wrapping.
2711  case CmpInst::ICMP_UGT:
2712  case CmpInst::ICMP_UGE:
2713  case CmpInst::ICMP_ULT:
2714  case CmpInst::ICMP_ULE:
2715  // However, we have to switch them to their signed variants to handle
2716  // negative indices from the base pointer.
2717  Pred = ICmpInst::getSignedPredicate(Pred);
2718  break;
2719  }
2720 
2721  // Strip off any constant offsets so that we can reason about them.
2722  // It's tempting to use getUnderlyingObject or even just stripInBoundsOffsets
2723  // here and compare base addresses like AliasAnalysis does, however there are
2724  // numerous hazards. AliasAnalysis and its utilities rely on special rules
2725  // governing loads and stores which don't apply to icmps. Also, AliasAnalysis
2726  // doesn't need to guarantee pointer inequality when it says NoAlias.
2727 
2728  // Even if an non-inbounds GEP occurs along the path we can still optimize
2729  // equality comparisons concerning the result.
2730  bool AllowNonInbounds = ICmpInst::isEquality(Pred);
2731  APInt LHSOffset = stripAndComputeConstantOffsets(DL, LHS, AllowNonInbounds);
2732  APInt RHSOffset = stripAndComputeConstantOffsets(DL, RHS, AllowNonInbounds);
2733 
2734  // If LHS and RHS are related via constant offsets to the same base
2735  // value, we can replace it with an icmp which just compares the offsets.
2736  if (LHS == RHS)
2738  ICmpInst::compare(LHSOffset, RHSOffset, Pred));
2739 
2740  // Various optimizations for (in)equality comparisons.
2741  if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) {
2742  // Different non-empty allocations that exist at the same time have
2743  // different addresses (if the program can tell). If the offsets are
2744  // within the bounds of their allocations (and not one-past-the-end!
2745  // so we can't use inbounds!), and their allocations aren't the same,
2746  // the pointers are not equal.
2748  uint64_t LHSSize, RHSSize;
2749  ObjectSizeOpts Opts;
2751  auto *F = [](Value *V) -> Function * {
2752  if (auto *I = dyn_cast<Instruction>(V))
2753  return I->getFunction();
2754  if (auto *A = dyn_cast<Argument>(V))
2755  return A->getParent();
2756  return nullptr;
2757  }(LHS);
2758  Opts.NullIsUnknownSize = F ? NullPointerIsDefined(F) : true;
2759  if (getObjectSize(LHS, LHSSize, DL, TLI, Opts) &&
2760  getObjectSize(RHS, RHSSize, DL, TLI, Opts) &&
2761  !LHSOffset.isNegative() && !RHSOffset.isNegative() &&
2762  LHSOffset.ult(LHSSize) && RHSOffset.ult(RHSSize)) {
2764  !CmpInst::isTrueWhenEqual(Pred));
2765  }
2766  }
2767 
2768  // If one side of the equality comparison must come from a noalias call
2769  // (meaning a system memory allocation function), and the other side must
2770  // come from a pointer that cannot overlap with dynamically-allocated
2771  // memory within the lifetime of the current function (allocas, byval
2772  // arguments, globals), then determine the comparison result here.
2773  SmallVector<const Value *, 8> LHSUObjs, RHSUObjs;
2774  getUnderlyingObjects(LHS, LHSUObjs);
2775  getUnderlyingObjects(RHS, RHSUObjs);
2776 
2777  // Is the set of underlying objects all noalias calls?
2778  auto IsNAC = [](ArrayRef<const Value *> Objects) {
2779  return all_of(Objects, isNoAliasCall);
2780  };
2781 
2782  // Is the set of underlying objects all things which must be disjoint from
2783  // noalias calls. We assume that indexing from such disjoint storage
2784  // into the heap is undefined, and thus offsets can be safely ignored.
2785  auto IsAllocDisjoint = [](ArrayRef<const Value *> Objects) {
2786  return all_of(Objects, ::isAllocDisjoint);
2787  };
2788 
2789  if ((IsNAC(LHSUObjs) && IsAllocDisjoint(RHSUObjs)) ||
2790  (IsNAC(RHSUObjs) && IsAllocDisjoint(LHSUObjs)))
2792  !CmpInst::isTrueWhenEqual(Pred));
2793 
2794  // Fold comparisons for non-escaping pointer even if the allocation call
2795  // cannot be elided. We cannot fold malloc comparison to null. Also, the
2796  // dynamic allocation call could be either of the operands. Note that
2797  // the other operand can not be based on the alloc - if it were, then
2798  // the cmp itself would be a capture.
2799  Value *MI = nullptr;
2800  if (isAllocLikeFn(LHS, TLI) &&
2801  llvm::isKnownNonZero(RHS, DL, 0, nullptr, CxtI, DT))
2802  MI = LHS;
2803  else if (isAllocLikeFn(RHS, TLI) &&
2804  llvm::isKnownNonZero(LHS, DL, 0, nullptr, CxtI, DT))
2805  MI = RHS;
2806  // FIXME: We should also fold the compare when the pointer escapes, but the
2807  // compare dominates the pointer escape
2808  if (MI && !PointerMayBeCaptured(MI, true, true))
2811  }
2812 
2813  // Otherwise, fail.
2814  return nullptr;
2815 }
2816 
2817 /// Fold an icmp when its operands have i1 scalar type.
2819  Value *RHS, const SimplifyQuery &Q) {
2820  Type *ITy = getCompareTy(LHS); // The return type.
2821  Type *OpTy = LHS->getType(); // The operand type.
2822  if (!OpTy->isIntOrIntVectorTy(1))
2823  return nullptr;
2824 
2825  // A boolean compared to true/false can be reduced in 14 out of the 20
2826  // (10 predicates * 2 constants) possible combinations. The other
2827  // 6 cases require a 'not' of the LHS.
2828 
2829  auto ExtractNotLHS = [](Value *V) -> Value * {
2830  Value *X;
2831  if (match(V, m_Not(m_Value(X))))
2832  return X;
2833  return nullptr;
2834  };
2835 
2836  if (match(RHS, m_Zero())) {
2837  switch (Pred) {
2838  case CmpInst::ICMP_NE: // X != 0 -> X
2839  case CmpInst::ICMP_UGT: // X >u 0 -> X
2840  case CmpInst::ICMP_SLT: // X <s 0 -> X
2841  return LHS;
2842 
2843  case CmpInst::ICMP_EQ: // not(X) == 0 -> X != 0 -> X
2844  case CmpInst::ICMP_ULE: // not(X) <=u 0 -> X >u 0 -> X
2845  case CmpInst::ICMP_SGE: // not(X) >=s 0 -> X <s 0 -> X
2846  if (Value *X = ExtractNotLHS(LHS))
2847  return X;
2848  break;
2849 
2850  case CmpInst::ICMP_ULT: // X <u 0 -> false
2851  case CmpInst::ICMP_SGT: // X >s 0 -> false
2852  return getFalse(ITy);
2853 
2854  case CmpInst::ICMP_UGE: // X >=u 0 -> true
2855  case CmpInst::ICMP_SLE: // X <=s 0 -> true
2856  return getTrue(ITy);
2857 
2858  default:
2859  break;
2860  }
2861  } else if (match(RHS, m_One())) {
2862  switch (Pred) {
2863  case CmpInst::ICMP_EQ: // X == 1 -> X
2864  case CmpInst::ICMP_UGE: // X >=u 1 -> X
2865  case CmpInst::ICMP_SLE: // X <=s -1 -> X
2866  return LHS;
2867 
2868  case CmpInst::ICMP_NE: // not(X) != 1 -> X == 1 -> X
2869  case CmpInst::ICMP_ULT: // not(X) <=u 1 -> X >=u 1 -> X
2870  case CmpInst::ICMP_SGT: // not(X) >s 1 -> X <=s -1 -> X
2871  if (Value *X = ExtractNotLHS(LHS))
2872  return X;
2873  break;
2874 
2875  case CmpInst::ICMP_UGT: // X >u 1 -> false
2876  case CmpInst::ICMP_SLT: // X <s -1 -> false
2877  return getFalse(ITy);
2878 
2879  case CmpInst::ICMP_ULE: // X <=u 1 -> true
2880  case CmpInst::ICMP_SGE: // X >=s -1 -> true
2881  return getTrue(ITy);
2882 
2883  default:
2884  break;
2885  }
2886  }
2887 
2888  switch (Pred) {
2889  default:
2890  break;
2891  case ICmpInst::ICMP_UGE:
2892  if (isImpliedCondition(RHS, LHS, Q.DL).value_or(false))
2893  return getTrue(ITy);
2894  break;
2895  case ICmpInst::ICMP_SGE:
2896  /// For signed comparison, the values for an i1 are 0 and -1
2897  /// respectively. This maps into a truth table of:
2898  /// LHS | RHS | LHS >=s RHS | LHS implies RHS
2899  /// 0 | 0 | 1 (0 >= 0) | 1
2900  /// 0 | 1 | 1 (0 >= -1) | 1
2901  /// 1 | 0 | 0 (-1 >= 0) | 0
2902  /// 1 | 1 | 1 (-1 >= -1) | 1
2903  if (isImpliedCondition(LHS, RHS, Q.DL).value_or(false))
2904  return getTrue(ITy);
2905  break;
2906  case ICmpInst::ICMP_ULE:
2907  if (isImpliedCondition(LHS, RHS, Q.DL).value_or(false))
2908  return getTrue(ITy);
2909  break;
2910  }
2911 
2912  return nullptr;
2913 }
2914 
2915 /// Try hard to fold icmp with zero RHS because this is a common case.
2917  Value *RHS, const SimplifyQuery &Q) {
2918  if (!match(RHS, m_Zero()))
2919  return nullptr;
2920 
2921  Type *ITy = getCompareTy(LHS); // The return type.
2922  switch (Pred) {
2923  default:
2924  llvm_unreachable("Unknown ICmp predicate!");
2925  case ICmpInst::ICMP_ULT:
2926  return getFalse(ITy);
2927  case ICmpInst::ICMP_UGE:
2928  return getTrue(ITy);
2929  case ICmpInst::ICMP_EQ:
2930  case ICmpInst::ICMP_ULE:
2931  if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT, Q.IIQ.UseInstrInfo))
2932  return getFalse(ITy);
2933  break;
2934  case ICmpInst::ICMP_NE:
2935  case ICmpInst::ICMP_UGT:
2936  if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT, Q.IIQ.UseInstrInfo))
2937  return getTrue(ITy);
2938  break;
2939  case ICmpInst::ICMP_SLT: {
2940  KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2941  if (LHSKnown.isNegative())
2942  return getTrue(ITy);
2943  if (LHSKnown.isNonNegative())
2944  return getFalse(ITy);
2945  break;
2946  }
2947  case ICmpInst::ICMP_SLE: {
2948  KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2949  if (LHSKnown.isNegative())
2950  return getTrue(ITy);
2951  if (LHSKnown.isNonNegative() &&
2952  isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2953  return getFalse(ITy);
2954  break;
2955  }
2956  case ICmpInst::ICMP_SGE: {
2957  KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2958  if (LHSKnown.isNegative())
2959  return getFalse(ITy);
2960  if (LHSKnown.isNonNegative())
2961  return getTrue(ITy);
2962  break;
2963  }
2964  case ICmpInst::ICMP_SGT: {
2965  KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2966  if (LHSKnown.isNegative())
2967  return getFalse(ITy);
2968  if (LHSKnown.isNonNegative() &&
2969  isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2970  return getTrue(ITy);
2971  break;
2972  }
2973  }
2974 
2975  return nullptr;
2976 }
2977 
2979  Value *RHS, const InstrInfoQuery &IIQ) {
2980  Type *ITy = getCompareTy(RHS); // The return type.
2981 
2982  Value *X;
2983  // Sign-bit checks can be optimized to true/false after unsigned
2984  // floating-point casts:
2985  // icmp slt (bitcast (uitofp X)), 0 --> false
2986  // icmp sgt (bitcast (uitofp X)), -1 --> true
2987  if (match(LHS, m_BitCast(m_UIToFP(m_Value(X))))) {
2988  if (Pred == ICmpInst::ICMP_SLT && match(RHS, m_Zero()))
2989  return ConstantInt::getFalse(ITy);
2990  if (Pred == ICmpInst::ICMP_SGT && match(RHS, m_AllOnes()))
2991  return ConstantInt::getTrue(ITy);
2992  }
2993 
2994  const APInt *C;
2995  if (!match(RHS, m_APIntAllowUndef(C)))
2996  return nullptr;
2997 
2998  // Rule out tautological comparisons (eg., ult 0 or uge 0).
3000  if (RHS_CR.isEmptySet())
3001  return ConstantInt::getFalse(ITy);
3002  if (RHS_CR.isFullSet())
3003  return ConstantInt::getTrue(ITy);
3004 
3005  ConstantRange LHS_CR =
3007  if (!LHS_CR.isFullSet()) {
3008  if (RHS_CR.contains(LHS_CR))
3009  return ConstantInt::getTrue(ITy);
3010  if (RHS_CR.inverse().contains(LHS_CR))
3011  return ConstantInt::getFalse(ITy);
3012  }
3013 
3014  // (mul nuw/nsw X, MulC) != C --> true (if C is not a multiple of MulC)
3015  // (mul nuw/nsw X, MulC) == C --> false (if C is not a multiple of MulC)
3016  const APInt *MulC;
3017  if (ICmpInst::isEquality(Pred) &&
3018  ((match(LHS, m_NUWMul(m_Value(), m_APIntAllowUndef(MulC))) &&
3019  *MulC != 0 && C->urem(*MulC) != 0) ||
3020  (match(LHS, m_NSWMul(m_Value(), m_APIntAllowUndef(MulC))) &&
3021  *MulC != 0 && C->srem(*MulC) != 0)))
3022  return ConstantInt::get(ITy, Pred == ICmpInst::ICMP_NE);
3023 
3024  return nullptr;
3025 }
3026 
3028  BinaryOperator *LBO, Value *RHS,
3029  const SimplifyQuery &Q,
3030  unsigned MaxRecurse) {
3031  Type *ITy = getCompareTy(RHS); // The return type.
3032 
3033  Value *Y = nullptr;
3034  // icmp pred (or X, Y), X
3035  if (match(LBO, m_c_Or(m_Value(Y), m_Specific(RHS)))) {
3036  if (Pred == ICmpInst::ICMP_ULT)
3037  return getFalse(ITy);
3038  if (Pred == ICmpInst::ICMP_UGE)
3039  return getTrue(ITy);
3040 
3041  if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE) {
3042  KnownBits RHSKnown = computeKnownBits(RHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
3043  KnownBits YKnown = computeKnownBits(Y, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
3044  if (RHSKnown.isNonNegative() && YKnown.isNegative())
3045  return Pred == ICmpInst::ICMP_SLT ? getTrue(ITy) : getFalse(ITy);
3046  if (RHSKnown.isNegative() || YKnown.isNonNegative())
3047  return Pred == ICmpInst::ICMP_SLT ? getFalse(ITy) : getTrue(ITy);
3048  }
3049  }
3050 
3051  // icmp pred (and X, Y), X
3052  if (match(LBO, m_c_And(m_Value(), m_Specific(RHS)))) {
3053  if (Pred == ICmpInst::ICMP_UGT)
3054  return getFalse(ITy);
3055  if (Pred == ICmpInst::ICMP_ULE)
3056  return getTrue(ITy);
3057  }
3058 
3059  // icmp pred (urem X, Y), Y
3060  if (match(LBO, m_URem(m_Value(), m_Specific(RHS)))) {
3061  switch (Pred) {
3062  default:
3063  break;
3064  case ICmpInst::ICMP_SGT:
3065  case ICmpInst::ICMP_SGE: {
3066  KnownBits Known = computeKnownBits(RHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
3067  if (!Known.isNonNegative())
3068  break;
3070  }
3071  case ICmpInst::ICMP_EQ:
3072  case ICmpInst::ICMP_UGT:
3073  case ICmpInst::ICMP_UGE:
3074  return getFalse(ITy);
3075  case ICmpInst::ICMP_SLT:
3076  case ICmpInst::ICMP_SLE: {
3077  KnownBits Known = computeKnownBits(RHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
3078  if (!Known.isNonNegative())
3079  break;
3081  }
3082  case ICmpInst::ICMP_NE:
3083  case ICmpInst::ICMP_ULT:
3084  case ICmpInst::ICMP_ULE:
3085  return getTrue(ITy);
3086  }
3087  }
3088 
3089  // icmp pred (urem X, Y), X
3090  if (match(LBO, m_URem(m_Specific(RHS), m_Value()))) {
3091  if (Pred == ICmpInst::ICMP_ULE)
3092  return getTrue(ITy);
3093  if (Pred == ICmpInst::ICMP_UGT)
3094  return getFalse(ITy);
3095  }
3096 
3097  // x >>u y <=u x --> true.
3098  // x >>u y >u x --> false.
3099  // x udiv y <=u x --> true.
3100  // x udiv y >u x --> false.
3101  if (match(LBO, m_LShr(m_Specific(RHS), m_Value())) ||
3102  match(LBO, m_UDiv(m_Specific(RHS), m_Value()))) {
3103  // icmp pred (X op Y), X
3104  if (Pred == ICmpInst::ICMP_UGT)
3105  return getFalse(ITy);
3106  if (Pred == ICmpInst::ICMP_ULE)
3107  return getTrue(ITy);
3108  }
3109 
3110  // If x is nonzero:
3111  // x >>u C <u x --> true for C != 0.
3112  // x >>u C != x --> true for C != 0.
3113  // x >>u C >=u x --> false for C != 0.
3114  // x >>u C == x --> false for C != 0.
3115  // x udiv C <u x --> true for C != 1.
3116  // x udiv C != x --> true for C != 1.
3117  // x udiv C >=u x --> false for C != 1.
3118  // x udiv C == x --> false for C != 1.
3119  // TODO: allow non-constant shift amount/divisor
3120  const APInt *C;
3121  if ((match(LBO, m_LShr(m_Specific(RHS), m_APInt(C))) && *C != 0) ||
3122  (match(LBO, m_UDiv(m_Specific(RHS), m_APInt(C))) && *C != 1)) {
3123  if (isKnownNonZero(RHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) {
3124  switch (Pred) {
3125  default:
3126  break;
3127  case ICmpInst::ICMP_EQ:
3128  case ICmpInst::ICMP_UGE:
3129  return getFalse(ITy);
3130  case ICmpInst::ICMP_NE:
3131  case ICmpInst::ICMP_ULT:
3132  return getTrue(ITy);
3133  case ICmpInst::ICMP_UGT:
3134  case ICmpInst::ICMP_ULE:
3135  // UGT/ULE are handled by the more general case just above
3136  llvm_unreachable("Unexpected UGT/ULE, should have been handled");
3137  }
3138  }
3139  }
3140 
3141  // (x*C1)/C2 <= x for C1 <= C2.
3142  // This holds even if the multiplication overflows: Assume that x != 0 and
3143  // arithmetic is modulo M. For overflow to occur we must have C1 >= M/x and
3144  // thus C2 >= M/x. It follows that (x*C1)/C2 <= (M-1)/C2 <= ((M-1)*x)/M < x.
3145  //
3146  // Additionally, either the multiplication and division might be represented
3147  // as shifts:
3148  // (x*C1)>>C2 <= x for C1 < 2**C2.
3149  // (x<<C1)/C2 <= x for 2**C1 < C2.
3150  const APInt *C1, *C2;
3151  if ((match(LBO, m_UDiv(m_Mul(m_Specific(RHS), m_APInt(C1)), m_APInt(C2))) &&
3152  C1->ule(*C2)) ||
3153  (match(LBO, m_LShr(m_Mul(m_Specific(RHS), m_APInt(C1)), m_APInt(C2))) &&
3154  C1->ule(APInt(C2->getBitWidth(), 1) << *C2)) ||
3155  (match(LBO, m_UDiv(m_Shl(m_Specific(RHS), m_APInt(C1)), m_APInt(C2))) &&
3156  (APInt(C1->getBitWidth(), 1) << *C1).ule(*C2))) {
3157  if (Pred == ICmpInst::ICMP_UGT)
3158  return getFalse(ITy);
3159  if (Pred == ICmpInst::ICMP_ULE)
3160  return getTrue(ITy);
3161  }
3162 
3163  return nullptr;
3164 }
3165 
3166 // If only one of the icmp's operands has NSW flags, try to prove that:
3167 //
3168 // icmp slt (x + C1), (x +nsw C2)
3169 //
3170 // is equivalent to:
3171 //
3172 // icmp slt C1, C2
3173 //
3174 // which is true if x + C2 has the NSW flags set and:
3175 // *) C1 < C2 && C1 >= 0, or
3176 // *) C2 < C1 && C1 <= 0.
3177 //
3179  Value *RHS) {
3180  // TODO: only support icmp slt for now.
3181  if (Pred != CmpInst::ICMP_SLT)
3182  return false;
3183 
3184  // Canonicalize nsw add as RHS.
3185  if (!match(RHS, m_NSWAdd(m_Value(), m_Value())))
3186  std::swap(LHS, RHS);
3187  if (!match(RHS, m_NSWAdd(m_Value(), m_Value())))
3188  return false;
3189 
3190  Value *X;
3191  const APInt *C1, *C2;
3192  if (!match(LHS, m_c_Add(m_Value(X), m_APInt(C1))) ||
3193  !match(RHS, m_c_Add(m_Specific(X), m_APInt(C2))))
3194  return false;
3195 
3196  return (C1->slt(*C2) && C1->isNonNegative()) ||
3197  (C2->slt(*C1) && C1->isNonPositive());
3198 }
3199 
3200 /// TODO: A large part of this logic is duplicated in InstCombine's
3201 /// foldICmpBinOp(). We should be able to share that and avoid the code
3202 /// duplication.
3204  Value *RHS, const SimplifyQuery &Q,
3205  unsigned MaxRecurse) {
3206  BinaryOperator *LBO = dyn_cast<BinaryOperator>(LHS);
3207  BinaryOperator *RBO = dyn_cast<BinaryOperator>(RHS);
3208  if (MaxRecurse && (LBO || RBO)) {
3209  // Analyze the case when either LHS or RHS is an add instruction.
3210  Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr;
3211  // LHS = A + B (or A and B are null); RHS = C + D (or C and D are null).
3212  bool NoLHSWrapProblem = false, NoRHSWrapProblem = false;
3213  if (LBO && LBO->getOpcode() == Instruction::Add) {
3214  A = LBO->getOperand(0);
3215  B = LBO->getOperand(1);
3216  NoLHSWrapProblem =
3217  ICmpInst::isEquality(Pred) ||
3218  (CmpInst::isUnsigned(Pred) &&
3219  Q.IIQ.hasNoUnsignedWrap(cast<OverflowingBinaryOperator>(LBO))) ||
3220  (CmpInst::isSigned(Pred) &&
3221  Q.IIQ.hasNoSignedWrap(cast<OverflowingBinaryOperator>(LBO)));
3222  }
3223  if (RBO && RBO->getOpcode() == Instruction::Add) {
3224  C = RBO->getOperand(0);
3225  D = RBO->getOperand(1);
3226  NoRHSWrapProblem =
3227  ICmpInst::isEquality(Pred) ||
3228  (CmpInst::isUnsigned(Pred) &&
3229  Q.IIQ.hasNoUnsignedWrap(cast<OverflowingBinaryOperator>(RBO))) ||
3230  (CmpInst::isSigned(Pred) &&
3231  Q.IIQ.hasNoSignedWrap(cast<OverflowingBinaryOperator>(RBO)));
3232  }
3233 
3234  // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow.
3235  if ((A == RHS || B == RHS) && NoLHSWrapProblem)
3236  if (Value *V = simplifyICmpInst(Pred, A == RHS ? B : A,
3238  MaxRecurse - 1))
3239  return V;
3240 
3241  // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow.
3242  if ((C == LHS || D == LHS) && NoRHSWrapProblem)
3243  if (Value *V =
3245  C == LHS ? D : C, Q, MaxRecurse - 1))
3246  return V;
3247 
3248  // icmp (X+Y), (X+Z) -> icmp Y,Z for equalities or if there is no overflow.
3249  bool CanSimplify = (NoLHSWrapProblem && NoRHSWrapProblem) ||
3251  if (A && C && (A == C || A == D || B == C || B == D) && CanSimplify) {
3252  // Determine Y and Z in the form icmp (X+Y), (X+Z).
3253  Value *Y, *Z;
3254  if (A == C) {
3255  // C + B == C + D -> B == D
3256  Y = B;
3257  Z = D;
3258  } else if (A == D) {
3259  // D + B == C + D -> B == C
3260  Y = B;
3261  Z = C;
3262  } else if (B == C) {
3263  // A + C == C + D -> A == D
3264  Y = A;
3265  Z = D;
3266  } else {
3267  assert(B == D);
3268  // A + D == C + D -> A == C
3269  Y = A;
3270  Z = C;
3271  }
3272  if (Value *V = simplifyICmpInst(Pred, Y, Z, Q, MaxRecurse - 1))
3273  return V;
3274  }
3275  }
3276 
3277  if (LBO)
3278  if (Value *V = simplifyICmpWithBinOpOnLHS(Pred, LBO, RHS, Q, MaxRecurse))
3279  return V;
3280 
3281  if (RBO)
3283  ICmpInst::getSwappedPredicate(Pred), RBO, LHS, Q, MaxRecurse))
3284  return V;
3285 
3286  // 0 - (zext X) pred C
3287  if (!CmpInst::isUnsigned(Pred) && match(LHS, m_Neg(m_ZExt(m_Value())))) {
3288  const APInt *C;
3289  if (match(RHS, m_APInt(C))) {
3290  if (C->isStrictlyPositive()) {
3291  if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_NE)
3293  if (Pred == ICmpInst::ICMP_SGE || Pred == ICmpInst::ICMP_EQ)
3295  }
3296  if (C->isNonNegative()) {
3297  if (Pred == ICmpInst::ICMP_SLE)
3299  if (Pred == ICmpInst::ICMP_SGT)
3301  }
3302  }
3303  }
3304 
3305  // If C2 is a power-of-2 and C is not:
3306  // (C2 << X) == C --> false
3307  // (C2 << X) != C --> true
3308  const APInt *C;
3309  if (match(LHS, m_Shl(m_Power2(), m_Value())) &&
3310  match(RHS, m_APIntAllowUndef(C)) && !C->isPowerOf2()) {
3311  // C2 << X can equal zero in some circumstances.
3312  // This simplification might be unsafe if C is zero.
3313  //
3314  // We know it is safe if:
3315  // - The shift is nsw. We can't shift out the one bit.
3316  // - The shift is nuw. We can't shift out the one bit.
3317  // - C2 is one.
3318  // - C isn't zero.
3319  if (Q.IIQ.hasNoSignedWrap(cast<OverflowingBinaryOperator>(LBO)) ||
3320  Q.IIQ.hasNoUnsignedWrap(cast<OverflowingBinaryOperator>(LBO)) ||
3321  match(LHS, m_Shl(m_One(), m_Value())) || !C->isZero()) {
3322  if (Pred == ICmpInst::ICMP_EQ)
3324  if (Pred == ICmpInst::ICMP_NE)
3326  }
3327  }
3328 
3329  // TODO: This is overly constrained. LHS can be any power-of-2.
3330  // (1 << X) >u 0x8000 --> false
3331  // (1 << X) <=u 0x8000 --> true
3332  if (match(LHS, m_Shl(m_One(), m_Value())) && match(RHS, m_SignMask())) {
3333  if (Pred == ICmpInst::ICMP_UGT)
3335  if (Pred == ICmpInst::ICMP_ULE)
3337  }
3338 
3339  if (MaxRecurse && LBO && RBO && LBO->getOpcode() == RBO->getOpcode() &&
3340  LBO->getOperand(1) == RBO->getOperand(1)) {
3341  switch (LBO->getOpcode()) {
3342  default:
3343  break;
3344  case Instruction::UDiv:
3345  case Instruction::LShr:
3346  if (ICmpInst::isSigned(Pred) || !Q.IIQ.isExact(LBO) ||
3347  !Q.IIQ.isExact(RBO))
3348  break;
3349  if (Value *V = simplifyICmpInst(Pred, LBO->getOperand(0),
3350  RBO->getOperand(0), Q, MaxRecurse - 1))
3351  return V;
3352  break;
3353  case Instruction::SDiv:
3354  if (!ICmpInst::isEquality(Pred) || !Q.IIQ.isExact(LBO) ||
3355  !Q.IIQ.isExact(RBO))
3356  break;
3357  if (Value *V = simplifyICmpInst(Pred, LBO->getOperand(0),
3358  RBO->getOperand(0), Q, MaxRecurse - 1))
3359  return V;
3360  break;
3361  case Instruction::AShr:
3362  if (!Q.IIQ.isExact(LBO) || !Q.IIQ.isExact(RBO))
3363  break;
3364  if (Value *V = simplifyICmpInst(Pred, LBO->getOperand(0),
3365  RBO->getOperand(0), Q, MaxRecurse - 1))
3366  return V;
3367  break;
3368  case Instruction::Shl: {
3369  bool NUW = Q.IIQ.hasNoUnsignedWrap(LBO) && Q.IIQ.hasNoUnsignedWrap(RBO);
3370  bool NSW = Q.IIQ.hasNoSignedWrap(LBO) && Q.IIQ.hasNoSignedWrap(RBO);
3371  if (!NUW && !NSW)
3372  break;
3373  if (!NSW && ICmpInst::isSigned(Pred))
3374  break;
3375  if (Value *V = simplifyICmpInst(Pred, LBO->getOperand(0),
3376  RBO->getOperand(0), Q, MaxRecurse - 1))
3377  return V;
3378  break;
3379  }
3380  }
3381  }
3382  return nullptr;
3383 }
3384 
3385 /// simplify integer comparisons where at least one operand of the compare
3386 /// matches an integer min/max idiom.
3388  Value *RHS, const SimplifyQuery &Q,
3389  unsigned MaxRecurse) {
3390  Type *ITy = getCompareTy(LHS); // The return type.
3391  Value *A, *B;
3393  CmpInst::Predicate EqP; // Chosen so that "A == max/min(A,B)" iff "A EqP B".
3394 
3395  // Signed variants on "max(a,b)>=a -> true".
3396  if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) {
3397  if (A != RHS)
3398  std::swap(A, B); // smax(A, B) pred A.
3399  EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B".
3400  // We analyze this as smax(A, B) pred A.
3401  P = Pred;
3402  } else if (match(RHS, m_SMax(m_Value(A), m_Value(B))) &&
3403  (A == LHS || B == LHS)) {
3404  if (A != LHS)
3405  std::swap(A, B); // A pred smax(A, B).
3406  EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B".
3407  // We analyze this as smax(A, B) swapped-pred A.
3409  } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) &&
3410  (A == RHS || B == RHS)) {
3411  if (A != RHS)
3412  std::swap(A, B); // smin(A, B) pred A.
3413  EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B".
3414  // We analyze this as smax(-A, -B) swapped-pred -A.
3415  // Note that we do not need to actually form -A or -B thanks to EqP.
3417  } else if (match(RHS, m_SMin(m_Value(A), m_Value(B))) &&
3418  (A == LHS || B == LHS)) {
3419  if (A != LHS)
3420  std::swap(A, B); // A pred smin(A, B).
3421  EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B".
3422  // We analyze this as smax(-A, -B) pred -A.
3423  // Note that we do not need to actually form -A or -B thanks to EqP.
3424  P = Pred;
3425  }
3426  if (P != CmpInst::BAD_ICMP_PREDICATE) {
3427  // Cases correspond to "max(A, B) p A".
3428  switch (P) {
3429  default:
3430  break;
3431  case CmpInst::ICMP_EQ:
3432  case CmpInst::ICMP_SLE:
3433  // Equivalent to "A EqP B". This may be the same as the condition tested
3434  // in the max/min; if so, we can just return that.
3435  if (Value *V = extractEquivalentCondition(LHS, EqP, A, B))
3436  return V;
3437  if (Value *V = extractEquivalentCondition(RHS, EqP, A, B))
3438  return V;
3439  // Otherwise, see if "A EqP B" simplifies.
3440  if (MaxRecurse)
3441  if (Value *V = simplifyICmpInst(EqP, A, B, Q, MaxRecurse - 1))
3442  return V;
3443  break;
3444  case CmpInst::ICMP_NE:
3445  case CmpInst::ICMP_SGT: {
3447  // Equivalent to "A InvEqP B". This may be the same as the condition
3448  // tested in the max/min; if so, we can just return that.
3449  if (Value *V = extractEquivalentCondition(LHS, InvEqP, A, B))
3450  return V;
3451  if (Value *V = extractEquivalentCondition(RHS, InvEqP, A, B))
3452  return V;
3453  // Otherwise, see if "A InvEqP B" simplifies.
3454  if (MaxRecurse)
3455  if (Value *V = simplifyICmpInst(InvEqP, A, B, Q, MaxRecurse - 1))
3456  return V;
3457  break;
3458  }
3459  case CmpInst::ICMP_SGE:
3460  // Always true.
3461  return getTrue(ITy);
3462  case CmpInst::ICMP_SLT:
3463  // Always false.
3464  return getFalse(ITy);
3465  }
3466  }
3467 
3468  // Unsigned variants on "max(a,b)>=a -> true".
3470  if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) {
3471  if (A != RHS)
3472  std::swap(A, B); // umax(A, B) pred A.
3473  EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B".
3474  // We analyze this as umax(A, B) pred A.
3475  P = Pred;
3476  } else if (match(RHS, m_UMax(m_Value(A), m_Value(B))) &&
3477  (A == LHS || B == LHS)) {
3478  if (A != LHS)
3479  std::swap(A, B); // A pred umax(A, B).
3480  EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B".
3481  // We analyze this as umax(A, B) swapped-pred A.
3483  } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) &&
3484  (A == RHS || B == RHS)) {
3485  if (A != RHS)
3486  std::swap(A, B); // umin(A, B) pred A.
3487  EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B".
3488  // We analyze this as umax(-A, -B) swapped-pred -A.
3489  // Note that we do not need to actually form -A or -B thanks to EqP.
3491  } else if (match(RHS, m_UMin(m_Value(A), m_Value(B))) &&
3492  (A == LHS || B == LHS)) {
3493  if (A != LHS)
3494  std::swap(A, B); // A pred umin(A, B).
3495  EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B".
3496  // We analyze this as umax(-A, -B) pred -A.
3497  // Note that we do not need to actually form -A or -B thanks to EqP.
3498  P = Pred;
3499  }
3500  if (P != CmpInst::BAD_ICMP_PREDICATE) {
3501  // Cases correspond to "max(A, B) p A".
3502  switch (P) {
3503  default:
3504  break;
3505  case CmpInst::ICMP_EQ:
3506  case CmpInst::ICMP_ULE:
3507  // Equivalent to "A EqP B". This may be the same as the condition tested
3508  // in the max/min; if so, we can just return that.
3509  if (Value *V = extractEquivalentCondition(LHS, EqP, A, B))
3510  return V;
3511  if (Value *V = extractEquivalentCondition(RHS, EqP, A, B))
3512  return V;
3513  // Otherwise, see if "A EqP B" simplifies.
3514  if (MaxRecurse)
3515  if (Value *V = simplifyICmpInst(EqP, A, B, Q, MaxRecurse - 1))
3516  return V;
3517  break;
3518  case CmpInst::ICMP_NE:
3519  case CmpInst::ICMP_UGT: {
3521  // Equivalent to "A InvEqP B". This may be the same as the condition
3522  // tested in the max/min; if so, we can just return that.
3523  if (Value *V = extractEquivalentCondition(LHS, InvEqP, A, B))
3524  return V;
3525  if (Value *V = extractEquivalentCondition(RHS, InvEqP, A, B))
3526  return V;
3527  // Otherwise, see if "A InvEqP B" simplifies.
3528  if (MaxRecurse)
3529  if (Value *V = simplifyICmpInst(InvEqP, A, B, Q, MaxRecurse - 1))
3530  return V;
3531  break;
3532  }
3533  case CmpInst::ICMP_UGE:
3534  return getTrue(ITy);
3535  case CmpInst::ICMP_ULT:
3536  return getFalse(ITy);
3537  }
3538  }
3539 
3540  // Comparing 1 each of min/max with a common operand?
3541  // Canonicalize min operand to RHS.
3542  if (match(LHS, m_UMin(m_Value(), m_Value())) ||
3543  match(LHS, m_SMin(m_Value(), m_Value()))) {
3544  std::swap(LHS, RHS);
3545  Pred = ICmpInst::getSwappedPredicate(Pred);
3546  }
3547 
3548  Value *C, *D;
3549  if (match(LHS, m_SMax(m_Value(A), m_Value(B))) &&
3550  match(RHS, m_SMin(m_Value(C), m_Value(D))) &&
3551  (A == C || A == D || B == C || B == D)) {
3552  // smax(A, B) >=s smin(A, D) --> true
3553  if (Pred == CmpInst::ICMP_SGE)
3554  return getTrue(ITy);
3555  // smax(A, B) <s smin(A, D) --> false
3556  if (Pred == CmpInst::ICMP_SLT)
3557  return getFalse(ITy);
3558  } else if (match(LHS, m_UMax(m_Value(A), m_Value(B))) &&
3559  match(RHS, m_UMin(m_Value(C), m_Value(D))) &&
3560  (A == C || A == D || B == C || B == D)) {
3561  // umax(A, B) >=u umin(A, D) --> true
3562  if (Pred == CmpInst::ICMP_UGE)
3563  return getTrue(ITy);
3564  // umax(A, B) <u umin(A, D) --> false
3565  if (Pred == CmpInst::ICMP_ULT)
3566  return getFalse(ITy);
3567  }
3568 
3569  return nullptr;
3570 }
3571 
3573  Value *LHS, Value *RHS,
3574  const SimplifyQuery &Q) {
3575  // Gracefully handle instructions that have not been inserted yet.
3576  if (!Q.AC || !Q.CxtI || !Q.CxtI->getParent())
3577  return nullptr;
3578 
3579  for (Value *AssumeBaseOp : {LHS, RHS}) {
3580  for (auto &AssumeVH : Q.AC->assumptionsFor(AssumeBaseOp)) {
3581  if (!AssumeVH)
3582  continue;
3583 
3584  CallInst *Assume = cast<CallInst>(AssumeVH);
3585  if (Optional<bool> Imp = isImpliedCondition(Assume->getArgOperand(0),
3586  Predicate, LHS, RHS, Q.DL))
3587  if (isValidAssumeForContext(Assume, Q.CxtI, Q.DT))
3588  return ConstantInt::get(getCompareTy(LHS), *Imp);
3589  }
3590  }
3591 
3592  return nullptr;
3593 }
3594 
3595 /// Given operands for an ICmpInst, see if we can fold the result.
3596 /// If not, this returns null.
3598  const SimplifyQuery &Q, unsigned MaxRecurse) {
3600  assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
3601 
3602  if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
3603  if (Constant *CRHS = dyn_cast<Constant>(RHS))
3604  return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI);
3605 
3606  // If we have a constant, make sure it is on the RHS.
3607  std::swap(LHS, RHS);
3608  Pred = CmpInst::getSwappedPredicate(Pred);
3609  }
3610  assert(!isa<UndefValue>(LHS) && "Unexpected icmp undef,%X");
3611 
3612  Type *ITy = getCompareTy(LHS); // The return type.
3613 
3614  // icmp poison, X -> poison
3615  if (isa<PoisonValue>(RHS))
3616  return PoisonValue::get(ITy);
3617 
3618  // For EQ and NE, we can always pick a value for the undef to make the
3619  // predicate pass or fail, so we can return undef.
3620  // Matches behavior in llvm::ConstantFoldCompareInstruction.
3621  if (Q.isUndefValue(RHS) && ICmpInst::isEquality(Pred))
3622  return UndefValue::get(ITy);
3623 
3624  // icmp X, X -> true/false
3625  // icmp X, undef -> true/false because undef could be X.
3626  if (LHS == RHS || Q.isUndefValue(RHS))
3627  return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
3628 
3629  if (Value *V = simplifyICmpOfBools(Pred, LHS, RHS, Q))
3630  return V;
3631 
3632  // TODO: Sink/common this with other potentially expensive calls that use
3633  // ValueTracking? See comment below for isKnownNonEqual().
3634  if (Value *V = simplifyICmpWithZero(Pred, LHS, RHS, Q))
3635  return V;
3636 
3637  if (Value *V = simplifyICmpWithConstant(Pred, LHS, RHS, Q.IIQ))
3638  return V;
3639 
3640  // If both operands have range metadata, use the metadata
3641  // to simplify the comparison.
3642  if (isa<Instruction>(RHS) && isa<Instruction>(LHS)) {
3643  auto RHS_Instr = cast<Instruction>(RHS);
3644  auto LHS_Instr = cast<Instruction>(LHS);
3645 
3646  if (Q.IIQ.getMetadata(RHS_Instr, LLVMContext::MD_range) &&
3647  Q.IIQ.getMetadata(LHS_Instr, LLVMContext::MD_range)) {
3648  auto RHS_CR = getConstantRangeFromMetadata(
3649  *RHS_Instr->getMetadata(LLVMContext::MD_range));
3650  auto LHS_CR = getConstantRangeFromMetadata(
3651  *LHS_Instr->getMetadata(LLVMContext::MD_range));
3652 
3653  if (LHS_CR.icmp(Pred, RHS_CR))
3654  return ConstantInt::getTrue(RHS->getContext());
3655 
3656  if (LHS_CR.icmp(CmpInst::getInversePredicate(Pred), RHS_CR))
3658  }
3659  }
3660 
3661  // Compare of cast, for example (zext X) != 0 -> X != 0
3662  if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) {
3663  Instruction *LI = cast<CastInst>(LHS);
3664  Value *SrcOp = LI->getOperand(0);
3665  Type *SrcTy = SrcOp->getType();
3666  Type *DstTy = LI->getType();
3667 
3668  // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input
3669  // if the integer type is the same size as the pointer type.
3670  if (MaxRecurse && isa<PtrToIntInst>(LI) &&
3671  Q.DL.getTypeSizeInBits(SrcTy) == DstTy->getPrimitiveSizeInBits()) {
3672  if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
3673  // Transfer the cast to the constant.
3674  if (Value *V = simplifyICmpInst(Pred, SrcOp,
3675  ConstantExpr::getIntToPtr(RHSC, SrcTy),
3676  Q, MaxRecurse - 1))
3677  return V;
3678  } else if (PtrToIntInst *RI = dyn_cast<PtrToIntInst>(RHS)) {
3679  if (RI->getOperand(0)->getType() == SrcTy)
3680  // Compare without the cast.
3681  if (Value *V = simplifyICmpInst(Pred, SrcOp, RI->getOperand(0), Q,
3682  MaxRecurse - 1))
3683  return V;
3684  }
3685  }
3686 
3687  if (isa<ZExtInst>(LHS)) {
3688  // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the
3689  // same type.
3690  if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) {
3691  if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
3692  // Compare X and Y. Note that signed predicates become unsigned.
3693  if (Value *V =
3695  RI->getOperand(0), Q, MaxRecurse - 1))
3696  return V;
3697  }
3698  // Fold (zext X) ule (sext X), (zext X) sge (sext X) to true.
3699  else if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) {
3700  if (SrcOp == RI->getOperand(0)) {
3701  if (Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_SGE)
3702  return ConstantInt::getTrue(ITy);
3703  if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_SLT)
3704  return ConstantInt::getFalse(ITy);
3705  }
3706  }
3707  // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended
3708  // too. If not, then try to deduce the result of the comparison.
3709  else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
3710  // Compute the constant that would happen if we truncated to SrcTy then
3711  // reextended to DstTy.
3712  Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
3713  Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy);
3714 
3715  // If the re-extended constant didn't change then this is effectively
3716  // also a case of comparing two zero-extended values.
3717  if (RExt == CI && MaxRecurse)
3719  SrcOp, Trunc, Q, MaxRecurse - 1))
3720  return V;
3721 
3722  // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit
3723  // there. Use this to work out the result of the comparison.
3724  if (RExt != CI) {
3725  switch (Pred) {
3726  default:
3727  llvm_unreachable("Unknown ICmp predicate!");
3728  // LHS <u RHS.
3729  case ICmpInst::ICMP_EQ:
3730  case ICmpInst::ICMP_UGT:
3731  case ICmpInst::ICMP_UGE:
3732  return ConstantInt::getFalse(CI->getContext());
3733 
3734  case ICmpInst::ICMP_NE:
3735  case ICmpInst::ICMP_ULT:
3736  case ICmpInst::ICMP_ULE:
3737  return ConstantInt::getTrue(CI->getContext());
3738 
3739  // LHS is non-negative. If RHS is negative then LHS >s LHS. If RHS
3740  // is non-negative then LHS <s RHS.
3741  case ICmpInst::ICMP_SGT:
3742  case ICmpInst::ICMP_SGE:
3743  return CI->getValue().isNegative()
3744  ? ConstantInt::getTrue(CI->getContext())
3745  : ConstantInt::getFalse(CI->getContext());
3746 
3747  case ICmpInst::ICMP_SLT:
3748  case ICmpInst::ICMP_SLE:
3749  return CI->getValue().isNegative()
3750  ? ConstantInt::getFalse(CI->getContext())
3751  : ConstantInt::getTrue(CI->getContext());
3752  }
3753  }
3754  }
3755  }
3756 
3757  if (isa<SExtInst>(LHS)) {
3758  // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the
3759  // same type.
3760  if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) {
3761  if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
3762  // Compare X and Y. Note that the predicate does not change.
3763  if (Value *V = simplifyICmpInst(Pred, SrcOp, RI->getOperand(0), Q,
3764  MaxRecurse - 1))
3765  return V;
3766  }
3767  // Fold (sext X) uge (zext X), (sext X) sle (zext X) to true.
3768  else if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) {
3769  if (SrcOp == RI->getOperand(0)) {
3770  if (Pred == ICmpInst::ICMP_UGE || Pred == ICmpInst::ICMP_SLE)
3771  return ConstantInt::getTrue(ITy);
3772  if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_SGT)
3773  return ConstantInt::getFalse(ITy);
3774  }
3775  }
3776  // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended
3777  // too. If not, then try to deduce the result of the comparison.
3778  else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
3779  // Compute the constant that would happen if we truncated to SrcTy then
3780  // reextended to DstTy.
3781  Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
3782  Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy);
3783 
3784  // If the re-extended constant didn't change then this is effectively
3785  // also a case of comparing two sign-extended values.
3786  if (RExt == CI && MaxRecurse)
3787  if (Value *V =
3788  simplifyICmpInst(Pred, SrcOp, Trunc, Q, MaxRecurse - 1))
3789  return V;
3790 
3791  // Otherwise the upper bits of LHS are all equal, while RHS has varying
3792  // bits there. Use this to work out the result of the comparison.
3793  if (RExt != CI) {
3794  switch (Pred) {
3795  default:
3796  llvm_unreachable("Unknown ICmp predicate!");
3797  case ICmpInst::ICMP_EQ:
3798  return ConstantInt::getFalse(CI->getContext());
3799  case ICmpInst::ICMP_NE:
3800  return ConstantInt::getTrue(CI->getContext());
3801 
3802  // If RHS is non-negative then LHS <s RHS. If RHS is negative then
3803  // LHS >s RHS.
3804  case ICmpInst::ICMP_SGT:
3805  case ICmpInst::ICMP_SGE:
3806  return CI->getValue().isNegative()
3807  ? ConstantInt::getTrue(CI->getContext())
3808  : ConstantInt::getFalse(CI->getContext());
3809  case ICmpInst::ICMP_SLT:
3810  case ICmpInst::ICMP_SLE:
3811  return CI->getValue().isNegative()
3812  ? ConstantInt::getFalse(CI->getContext())
3813  : ConstantInt::getTrue(CI->getContext());
3814 
3815  // If LHS is non-negative then LHS <u RHS. If LHS is negative then
3816  // LHS >u RHS.
3817  case ICmpInst::ICMP_UGT:
3818  case ICmpInst::ICMP_UGE:
3819  // Comparison is true iff the LHS <s 0.
3820  if (MaxRecurse)
3822  Constant::getNullValue(SrcTy), Q,
3823  MaxRecurse - 1))
3824  return V;
3825  break;
3826  case ICmpInst::ICMP_ULT:
3827  case ICmpInst::ICMP_ULE:
3828  // Comparison is true iff the LHS >=s 0.
3829  if (MaxRecurse)
3831  Constant::getNullValue(SrcTy), Q,
3832  MaxRecurse - 1))
3833  return V;
3834  break;
3835  }
3836  }
3837  }
3838  }
3839  }
3840 
3841  // icmp eq|ne X, Y -> false|true if X != Y
3842  // This is potentially expensive, and we have already computedKnownBits for
3843  // compares with 0 above here, so only try this for a non-zero compare.
3844  if (ICmpInst::isEquality(Pred) && !match(RHS, m_Zero()) &&
3845  isKnownNonEqual(LHS, RHS, Q.DL, Q.AC, Q.CxtI, Q.DT, Q.IIQ.UseInstrInfo)) {
3846  return Pred == ICmpInst::ICMP_NE ? getTrue(ITy) : getFalse(ITy);
3847  }
3848 
3849  if (Value *V = simplifyICmpWithBinOp(Pred, LHS, RHS, Q, MaxRecurse))
3850  return V;
3851 
3852  if (Value *V = simplifyICmpWithMinMax(Pred, LHS, RHS, Q, MaxRecurse))
3853  return V;
3854 
3855  if (Value *V = simplifyICmpWithDominatingAssume(Pred, LHS, RHS, Q))
3856  return V;
3857 
3858  // Simplify comparisons of related pointers using a powerful, recursive
3859  // GEP-walk when we have target data available..
3860  if (LHS->getType()->isPointerTy())
3861  if (auto *C = computePointerICmp(Pred, LHS, RHS, Q))
3862  return C;
3863  if (auto *CLHS = dyn_cast<PtrToIntOperator>(LHS))
3864  if (auto *CRHS = dyn_cast<PtrToIntOperator>(RHS))
3865  if (Q.DL.getTypeSizeInBits(CLHS->getPointerOperandType()) ==
3866  Q.DL.getTypeSizeInBits(CLHS->getType()) &&
3867  Q.DL.getTypeSizeInBits(CRHS->getPointerOperandType()) ==
3868  Q.DL.getTypeSizeInBits(CRHS->getType()))
3869  if (auto *C = computePointerICmp(Pred, CLHS->getPointerOperand(),
3870  CRHS->getPointerOperand(), Q))
3871  return C;
3872 
3873  // If the comparison is with the result of a select instruction, check whether
3874  // comparing with either branch of the select always yields the same value.
3875  if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
3876  if (Value *V = threadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse))
3877  return V;
3878 
3879  // If the comparison is with the result of a phi instruction, check whether
3880  // doing the compare with each incoming phi value yields a common result.
3881  if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
3882  if (Value *V = threadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse))
3883  return V;
3884 
3885  return nullptr;
3886 }
3887 
3889  const SimplifyQuery &Q) {
3891 }
3892 
3893 /// Given operands for an FCmpInst, see if we can fold the result.
3894 /// If not, this returns null.
3896  FastMathFlags FMF, const SimplifyQuery &Q,
3897  unsigned MaxRecurse) {
3899  assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
3900 
3901  if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
3902  if (Constant *CRHS = dyn_cast<Constant>(RHS))
3903  return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI);
3904 
3905  // If we have a constant, make sure it is on the RHS.
3906  std::swap(LHS, RHS);
3907  Pred = CmpInst::getSwappedPredicate(Pred);
3908  }
3909 
3910  // Fold trivial predicates.
3911  Type *RetTy = getCompareTy(LHS);
3912  if (Pred == FCmpInst::FCMP_FALSE)
3913  return getFalse(RetTy);
3914  if (Pred == FCmpInst::FCMP_TRUE)
3915  return getTrue(RetTy);
3916 
3917  // Fold (un)ordered comparison if we can determine there are no NaNs.
3918  if (Pred == FCmpInst::FCMP_UNO || Pred == FCmpInst::FCMP_ORD)
3919  if (FMF.noNaNs() ||
3921  return ConstantInt::get(RetTy, Pred == FCmpInst::FCMP_ORD);
3922 
3923  // NaN is unordered; NaN is not ordered.
3925  "Comparison must be either ordered or unordered");
3926  if (match(RHS, m_NaN()))
3927  return ConstantInt::get(RetTy, CmpInst::isUnordered(Pred));
3928 
3929  // fcmp pred x, poison and fcmp pred poison, x
3930  // fold to poison
3931  if (isa<PoisonValue>(LHS) || isa<PoisonValue>(RHS))
3932  return PoisonValue::get(RetTy);
3933 
3934  // fcmp pred x, undef and fcmp pred undef, x
3935  // fold to true if unordered, false if ordered
3936  if (Q.isUndefValue(LHS) || Q.isUndefValue(RHS)) {
3937  // Choosing NaN for the undef will always make unordered comparison succeed
3938  // and ordered comparison fail.
3939  return ConstantInt::get(RetTy, CmpInst::isUnordered(Pred));
3940  }
3941 
3942  // fcmp x,x -> true/false. Not all compares are foldable.
3943  if (LHS == RHS) {
3944  if (CmpInst::isTrueWhenEqual(Pred))
3945  return getTrue(RetTy);
3946  if (CmpInst::isFalseWhenEqual(Pred))
3947  return getFalse(RetTy);
3948  }
3949 
3950  // Handle fcmp with constant RHS.
3951  // TODO: Use match with a specific FP value, so these work with vectors with
3952  // undef lanes.
3953  const APFloat *C;
3954  if (match(RHS, m_APFloat(C))) {
3955  // Check whether the constant is an infinity.
3956  if (C->isInfinity()) {
3957  if (C->isNegative()) {
3958  switch (Pred) {
3959  case FCmpInst::FCMP_OLT:
3960  // No value is ordered and less than negative infinity.
3961  return getFalse(RetTy);
3962  case FCmpInst::FCMP_UGE:
3963  // All values are unordered with or at least negative infinity.
3964  return getTrue(RetTy);
3965  default:
3966  break;
3967  }
3968  } else {
3969  switch (Pred) {
3970  case FCmpInst::FCMP_OGT:
3971  // No value is ordered and greater than infinity.
3972  return getFalse(RetTy);
3973  case FCmpInst::FCMP_ULE:
3974  // All values are unordered with and at most infinity.
3975  return getTrue(RetTy);
3976  default:
3977  break;
3978  }
3979  }
3980 
3981  // LHS == Inf
3982  if (Pred == FCmpInst::FCMP_OEQ && isKnownNeverInfinity(LHS, Q.TLI))
3983  return getFalse(RetTy);
3984  // LHS != Inf
3985  if (Pred == FCmpInst::FCMP_UNE && isKnownNeverInfinity(LHS, Q.TLI))
3986  return getTrue(RetTy);
3987  // LHS == Inf || LHS == NaN
3988  if (Pred == FCmpInst::FCMP_UEQ && isKnownNeverInfinity(LHS, Q.TLI) &&
3989  isKnownNeverNaN(LHS, Q.TLI))
3990  return getFalse(RetTy);
3991  // LHS != Inf && LHS != NaN
3992  if (Pred == FCmpInst::FCMP_ONE && isKnownNeverInfinity(LHS, Q.TLI) &&
3993  isKnownNeverNaN(LHS, Q.TLI))
3994  return getTrue(RetTy);
3995  }
3996  if (C->isNegative() && !C->isNegZero()) {
3997  assert(!C->isNaN() && "Unexpected NaN constant!");
3998  // TODO: We can catch more cases by using a range check rather than
3999  // relying on CannotBeOrderedLessThanZero.
4000  switch (Pred) {
4001  case FCmpInst::FCMP_UGE:
4002  case FCmpInst::FCMP_UGT:
4003  case FCmpInst::FCMP_UNE:
4004  // (X >= 0) implies (X > C) when (C < 0)
4006  return getTrue(RetTy);
4007  break;
4008  case FCmpInst::FCMP_OEQ:
4009  case FCmpInst::FCMP_OLE:
4010  case FCmpInst::FCMP_OLT:
4011  // (X >= 0) implies !(X < C) when (C < 0)
4013  return getFalse(RetTy);
4014  break;
4015  default:
4016  break;
4017  }
4018  }
4019 
4020  // Check comparison of [minnum/maxnum with constant] with other constant.
4021  const APFloat *C2;
4022  if ((match(LHS, m_Intrinsic<Intrinsic::minnum>(m_Value(), m_APFloat(C2))) &&
4023  *C2 < *C) ||
4024  (match(LHS, m_Intrinsic<Intrinsic::maxnum>(m_Value(), m_APFloat(C2))) &&
4025  *C2 > *C)) {
4026  bool IsMaxNum =
4027  cast<IntrinsicInst>(LHS)->getIntrinsicID() == Intrinsic::maxnum;
4028  // The ordered relationship and minnum/maxnum guarantee that we do not
4029  // have NaN constants, so ordered/unordered preds are handled the same.
4030  switch (Pred) {
4031  case FCmpInst::FCMP_OEQ:
4032  case FCmpInst::FCMP_UEQ:
4033  // minnum(X, LesserC) == C --> false
4034  // maxnum(X, GreaterC) == C --> false
4035  return getFalse(RetTy);
4036  case FCmpInst::FCMP_ONE:
4037  case FCmpInst::FCMP_UNE:
4038  // minnum(X, LesserC) != C --> true
4039  // maxnum(X, GreaterC) != C --> true
4040  return getTrue(RetTy);
4041  case FCmpInst::FCMP_OGE:
4042  case FCmpInst::FCMP_UGE:
4043  case FCmpInst::FCMP_OGT:
4044  case FCmpInst::FCMP_UGT:
4045  // minnum(X, LesserC) >= C --> false
4046  // minnum(X, LesserC) > C --> false
4047  // maxnum(X, GreaterC) >= C --> true
4048  // maxnum(X, GreaterC) > C --> true
4049  return ConstantInt::get(RetTy, IsMaxNum);
4050  case FCmpInst::FCMP_OLE:
4051  case FCmpInst::FCMP_ULE:
4052  case FCmpInst::FCMP_OLT:
4053  case FCmpInst::FCMP_ULT:
4054  // minnum(X, LesserC) <= C --> true
4055  // minnum(X, LesserC) < C --> true
4056  // maxnum(X, GreaterC) <= C --> false
4057  // maxnum(X, GreaterC) < C --> false
4058  return ConstantInt::get(RetTy, !IsMaxNum);
4059  default:
4060  // TRUE/FALSE/ORD/UNO should be handled before this.
4061  llvm_unreachable("Unexpected fcmp predicate");
4062  }
4063  }
4064  }
4065 
4066  if (match(RHS, m_AnyZeroFP())) {
4067  switch (Pred) {
4068  case FCmpInst::FCMP_OGE:
4069  case FCmpInst::FCMP_ULT:
4070  // Positive or zero X >= 0.0 --> true
4071  // Positive or zero X < 0.0 --> false
4072  if ((FMF.noNaNs() || isKnownNeverNaN(LHS, Q.TLI)) &&
4074  return Pred == FCmpInst::FCMP_OGE ? getTrue(RetTy) : getFalse(RetTy);
4075  break;
4076  case FCmpInst::FCMP_UGE:
4077  case FCmpInst::FCMP_OLT:
4078  // Positive or zero or nan X >= 0.0 --> true
4079  // Positive or zero or nan X < 0.0 --> false
4081  return Pred == FCmpInst::FCMP_UGE ? getTrue(RetTy) : getFalse(RetTy);
4082  break;
4083  default:
4084  break;
4085  }
4086  }
4087 
4088  // If the comparison is with the result of a select instruction, check whether
4089  // comparing with either branch of the select always yields the same value.
4090  if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
4091  if (Value *V = threadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse))
4092  return V;
4093 
4094  // If the comparison is with the result of a phi instruction, check whether
4095  // doing the compare with each incoming phi value yields a common result.
4096  if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
4097  if (Value *V = threadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse))
4098  return V;
4099 
4100  return nullptr;
4101 }
4102 
4104  FastMathFlags FMF, const SimplifyQuery &Q) {
4106 }
4107 
4109  const SimplifyQuery &Q,
4110  bool AllowRefinement,
4111  unsigned MaxRecurse) {
4112  assert(!Op->getType()->isVectorTy() && "This is not safe for vectors");
4113 
4114  // Trivial replacement.
4115  if (V == Op)
4116  return RepOp;
4117 
4118  // We cannot replace a constant, and shouldn't even try.
4119  if (isa<Constant>(Op))
4120  return nullptr;
4121 
4122  auto *I = dyn_cast<Instruction>(V);
4123  if (!I || !is_contained(I->operands(), Op))
4124  return nullptr;
4125 
4126  // Replace Op with RepOp in instruction operands.
4127  SmallVector<Value *, 8> NewOps(I->getNumOperands());
4128  transform(I->operands(), NewOps.begin(),
4129  [&](Value *V) { return V == Op ? RepOp : V; });
4130 
4131  if (!AllowRefinement) {
4132  // General InstSimplify functions may refine the result, e.g. by returning
4133  // a constant for a potentially poison value. To avoid this, implement only
4134  // a few non-refining but profitable transforms here.
4135 
4136  if (auto *BO = dyn_cast<BinaryOperator>(I)) {
4137  unsigned Opcode = BO->getOpcode();
4138  // id op x -> x, x op id -> x
4139  if (NewOps[0] == ConstantExpr::getBinOpIdentity(Opcode, I->getType()))
4140  return NewOps[1];
4141  if (NewOps[1] == ConstantExpr::getBinOpIdentity(Opcode, I->getType(),
4142  /* RHS */ true))
4143  return NewOps[0];
4144 
4145  // x & x -> x, x | x -> x
4146  if ((Opcode == Instruction::And || Opcode == Instruction::Or) &&
4147  NewOps[0] == NewOps[1])
4148  return NewOps[0];
4149  }
4150 
4151  if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
4152  // getelementptr x, 0 -> x
4153  if (NewOps.size() == 2 && match(NewOps[1], m_Zero()) &&
4154  !GEP->isInBounds())
4155  return NewOps[0];
4156  }
4157  } else if (MaxRecurse) {
4158  // The simplification queries below may return the original value. Consider:
4159  // %div = udiv i32 %arg, %arg2
4160  // %mul = mul nsw i32 %div, %arg2
4161  // %cmp = icmp eq i32 %mul, %arg
4162  // %sel = select i1 %cmp, i32 %div, i32 undef
4163  // Replacing %arg by %mul, %div becomes "udiv i32 %mul, %arg2", which
4164  // simplifies back to %arg. This can only happen because %mul does not
4165  // dominate %div. To ensure a consistent return value contract, we make sure
4166  // that this case returns nullptr as well.
4167  auto PreventSelfSimplify = [V](Value *Simplified) {
4168  return Simplified != V ? Simplified : nullptr;
4169  };
4170 
4171  if (auto *B = dyn_cast<BinaryOperator>(I))
4172  return PreventSelfSimplify(simplifyBinOp(B->getOpcode(), NewOps[0],
4173  NewOps[1], Q, MaxRecurse - 1));
4174 
4175  if (CmpInst *C = dyn_cast<CmpInst>(I))
4176  return PreventSelfSimplify(simplifyCmpInst(C->getPredicate(), NewOps[0],
4177  NewOps[1], Q, MaxRecurse - 1));
4178 
4179  if (auto *GEP = dyn_cast<GetElementPtrInst>(I))
4180  return PreventSelfSimplify(simplifyGEPInst(
4181  GEP->getSourceElementType(), NewOps[0], makeArrayRef(NewOps).slice(1),
4182  GEP->isInBounds(), Q, MaxRecurse - 1));
4183 
4184  if (isa<SelectInst>(I))
4185  return PreventSelfSimplify(simplifySelectInst(
4186  NewOps[0], NewOps[1], NewOps[2], Q, MaxRecurse - 1));
4187  // TODO: We could hand off more cases to instsimplify here.
4188  }
4189 
4190  // If all operands are constant after substituting Op for RepOp then we can
4191  // constant fold the instruction.
4192  SmallVector<Constant *, 8> ConstOps;
4193  for (Value *NewOp : NewOps) {
4194  if (Constant *ConstOp = dyn_cast<Constant>(NewOp))
4195  ConstOps.push_back(ConstOp);
4196  else
4197  return nullptr;
4198  }
4199 
4200  // Consider:
4201  // %cmp = icmp eq i32 %x, 2147483647
4202  // %add = add nsw i32 %x, 1
4203  // %sel = select i1 %cmp, i32 -2147483648, i32 %add
4204  //
4205  // We can't replace %sel with %add unless we strip away the flags (which
4206  // will be done in InstCombine).
4207  // TODO: This may be unsound, because it only catches some forms of
4208  // refinement.
4209  if (!AllowRefinement && canCreatePoison(cast<Operator>(I)))
4210  return nullptr;
4211 
4212  if (CmpInst *C = dyn_cast<CmpInst>(I))
4213  return ConstantFoldCompareInstOperands(C->getPredicate(), ConstOps[0],
4214  ConstOps[1], Q.DL, Q.TLI);
4215 
4216  if (LoadInst *LI = dyn_cast<LoadInst>(I))
4217  if (!LI->isVolatile())
4218  return ConstantFoldLoadFromConstPtr(ConstOps[0], LI->getType(), Q.DL);
4219 
4220  return ConstantFoldInstOperands(I, ConstOps, Q.DL, Q.TLI);
4221 }
4222 
4224  const SimplifyQuery &Q,
4225  bool AllowRefinement) {
4226  return ::simplifyWithOpReplaced(V, Op, RepOp, Q, AllowRefinement,
4227  RecursionLimit);
4228 }
4229 
4230 /// Try to simplify a select instruction when its condition operand is an
4231 /// integer comparison where one operand of the compare is a constant.
4233  const APInt *Y, bool TrueWhenUnset) {
4234  const APInt *C;
4235 
4236  // (X & Y) == 0 ? X & ~Y : X --> X
4237  // (X & Y) != 0 ? X & ~Y : X --> X & ~Y
4238  if (FalseVal == X && match(TrueVal, m_And(m_Specific(X), m_APInt(C))) &&
4239  *Y == ~*C)
4240  return TrueWhenUnset ? FalseVal : TrueVal;
4241 
4242  // (X & Y) == 0 ? X : X & ~Y --> X & ~Y
4243  // (X & Y) != 0 ? X : X & ~Y --> X
4244  if (TrueVal == X && match(FalseVal, m_And(m_Specific(X), m_APInt(C))) &&
4245  *Y == ~*C)
4246  return TrueWhenUnset ? FalseVal : TrueVal;
4247 
4248  if (Y->isPowerOf2()) {
4249  // (X & Y) == 0 ? X | Y : X --> X | Y
4250  // (X & Y) != 0 ? X | Y : X --> X
4251  if (FalseVal == X && match(TrueVal, m_Or(m_Specific(X), m_APInt(C))) &&
4252  *Y == *C)
4253  return TrueWhenUnset ? TrueVal : FalseVal;
4254 
4255  // (X & Y) == 0 ? X : X | Y --> X
4256  // (X & Y) != 0 ? X : X | Y --> X | Y
4257  if (TrueVal == X && match(FalseVal, m_Or(m_Specific(X), m_APInt(C))) &&
4258  *Y == *C)
4259  return TrueWhenUnset ? TrueVal : FalseVal;
4260  }
4261 
4262  return nullptr;
4263 }
4264 
4265 /// An alternative way to test if a bit is set or not uses sgt/slt instead of
4266 /// eq/ne.
4268  ICmpInst::Predicate Pred,
4269  Value *TrueVal, Value *FalseVal) {
4270  Value *X;
4271  APInt Mask;
4272  if (!decomposeBitTestICmp(CmpLHS, CmpRHS, Pred, X, Mask))
4273  return nullptr;
4274 
4276  Pred == ICmpInst::ICMP_EQ);
4277 }
4278 
4279 /// Try to simplify a select instruction when its condition operand is an
4280 /// integer comparison.
4282  Value *FalseVal,
4283  const SimplifyQuery &Q,
4284  unsigned MaxRecurse) {
4285  ICmpInst::Predicate Pred;
4286  Value *CmpLHS, *CmpRHS;
4287  if (!match(CondVal, m_ICmp(Pred, m_Value(CmpLHS), m_Value(CmpRHS))))
4288  return nullptr;
4289 
4290  // Canonicalize ne to eq predicate.
4291  if (Pred == ICmpInst::ICMP_NE) {
4292  Pred = ICmpInst::ICMP_EQ;
4294  }
4295 
4296  // Check for integer min/max with a limit constant:
4297  // X > MIN_INT ? X : MIN_INT --> X
4298  // X < MAX_INT ? X : MAX_INT --> X
4299  if (TrueVal->getType()->isIntOrIntVectorTy()) {
4300  Value *X, *Y;
4301  SelectPatternFlavor SPF =
4302  matchDecomposedSelectPattern(cast<ICmpInst>(CondVal), TrueVal, FalseVal,
4303  X, Y)
4304  .Flavor;
4305  if (SelectPatternResult::isMinOrMax(SPF) && Pred == getMinMaxPred(SPF)) {
4307  X->getType()->getScalarSizeInBits());
4308  if (match(Y, m_SpecificInt(LimitC)))
4309  return X;
4310  }
4311  }
4312 
4313  if (Pred == ICmpInst::ICMP_EQ && match(CmpRHS, m_Zero())) {
4314  Value *X;
4315  const APInt *Y;
4316  if (match(CmpLHS, m_And(m_Value(X), m_APInt(Y))))
4318  /*TrueWhenUnset=*/true))
4319  return V;
4320 
4321  // Test for a bogus zero-shift-guard-op around funnel-shift or rotate.
4322  Value *ShAmt;
4323  auto isFsh = m_CombineOr(m_FShl(m_Value(X), m_Value(), m_Value(ShAmt)),
4324  m_FShr(m_Value(), m_Value(X), m_Value(ShAmt)));
4325  // (ShAmt == 0) ? fshl(X, *, ShAmt) : X --> X
4326  // (ShAmt == 0) ? fshr(*, X, ShAmt) : X --> X
4327  if (match(TrueVal, isFsh) && FalseVal == X && CmpLHS == ShAmt)
4328  return X;
4329 
4330  // Test for a zero-shift-guard-op around rotates. These are used to
4331  // avoid UB from oversized shifts in raw IR rotate patterns, but the
4332  // intrinsics do not have that problem.
4333  // We do not allow this transform for the general funnel shift case because
4334  // that would not preserve the poison safety of the original code.
4335  auto isRotate =
4337  m_FShr(m_Value(X), m_Deferred(X), m_Value(ShAmt)));
4338  // (ShAmt == 0) ? X : fshl(X, X, ShAmt) --> fshl(X, X, ShAmt)
4339  // (ShAmt == 0) ? X : fshr(X, X, ShAmt) --> fshr(X, X, ShAmt)
4340  if (match(FalseVal, isRotate) && TrueVal == X && CmpLHS == ShAmt &&
4341  Pred == ICmpInst::ICMP_EQ)
4342  return FalseVal;
4343 
4344  // X == 0 ? abs(X) : -abs(X) --> -abs(X)
4345  // X == 0 ? -abs(X) : abs(X) --> abs(X)
4346