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