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