LLVM 19.0.0git
InstCombineCompares.cpp
Go to the documentation of this file.
1//===- InstCombineCompares.cpp --------------------------------------------===//
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 the visitICmp and visitFCmp functions.
10//
11//===----------------------------------------------------------------------===//
12
13#include "InstCombineInternal.h"
14#include "llvm/ADT/APSInt.h"
15#include "llvm/ADT/ScopeExit.h"
16#include "llvm/ADT/SetVector.h"
17#include "llvm/ADT/Statistic.h"
25#include "llvm/IR/DataLayout.h"
26#include "llvm/IR/InstrTypes.h"
31#include <bitset>
32
33using namespace llvm;
34using namespace PatternMatch;
35
36#define DEBUG_TYPE "instcombine"
37
38// How many times is a select replaced by one of its operands?
39STATISTIC(NumSel, "Number of select opts");
40
41
42/// Compute Result = In1+In2, returning true if the result overflowed for this
43/// type.
44static bool addWithOverflow(APInt &Result, const APInt &In1,
45 const APInt &In2, bool IsSigned = false) {
46 bool Overflow;
47 if (IsSigned)
48 Result = In1.sadd_ov(In2, Overflow);
49 else
50 Result = In1.uadd_ov(In2, Overflow);
51
52 return Overflow;
53}
54
55/// Compute Result = In1-In2, returning true if the result overflowed for this
56/// type.
57static bool subWithOverflow(APInt &Result, const APInt &In1,
58 const APInt &In2, bool IsSigned = false) {
59 bool Overflow;
60 if (IsSigned)
61 Result = In1.ssub_ov(In2, Overflow);
62 else
63 Result = In1.usub_ov(In2, Overflow);
64
65 return Overflow;
66}
67
68/// Given an icmp instruction, return true if any use of this comparison is a
69/// branch on sign bit comparison.
70static bool hasBranchUse(ICmpInst &I) {
71 for (auto *U : I.users())
72 if (isa<BranchInst>(U))
73 return true;
74 return false;
75}
76
77/// Returns true if the exploded icmp can be expressed as a signed comparison
78/// to zero and updates the predicate accordingly.
79/// The signedness of the comparison is preserved.
80/// TODO: Refactor with decomposeBitTestICmp()?
81static bool isSignTest(ICmpInst::Predicate &Pred, const APInt &C) {
82 if (!ICmpInst::isSigned(Pred))
83 return false;
84
85 if (C.isZero())
86 return ICmpInst::isRelational(Pred);
87
88 if (C.isOne()) {
89 if (Pred == ICmpInst::ICMP_SLT) {
90 Pred = ICmpInst::ICMP_SLE;
91 return true;
92 }
93 } else if (C.isAllOnes()) {
94 if (Pred == ICmpInst::ICMP_SGT) {
95 Pred = ICmpInst::ICMP_SGE;
96 return true;
97 }
98 }
99
100 return false;
101}
102
103/// This is called when we see this pattern:
104/// cmp pred (load (gep GV, ...)), cmpcst
105/// where GV is a global variable with a constant initializer. Try to simplify
106/// this into some simple computation that does not need the load. For example
107/// we can optimize "icmp eq (load (gep "foo", 0, i)), 0" into "icmp eq i, 3".
108///
109/// If AndCst is non-null, then the loaded value is masked with that constant
110/// before doing the comparison. This handles cases like "A[i]&4 == 0".
113 ConstantInt *AndCst) {
114 if (LI->isVolatile() || LI->getType() != GEP->getResultElementType() ||
115 GV->getValueType() != GEP->getSourceElementType() || !GV->isConstant() ||
117 return nullptr;
118
120 if (!isa<ConstantArray>(Init) && !isa<ConstantDataArray>(Init))
121 return nullptr;
122
123 uint64_t ArrayElementCount = Init->getType()->getArrayNumElements();
124 // Don't blow up on huge arrays.
125 if (ArrayElementCount > MaxArraySizeForCombine)
126 return nullptr;
127
128 // There are many forms of this optimization we can handle, for now, just do
129 // the simple index into a single-dimensional array.
130 //
131 // Require: GEP GV, 0, i {{, constant indices}}
132 if (GEP->getNumOperands() < 3 || !isa<ConstantInt>(GEP->getOperand(1)) ||
133 !cast<ConstantInt>(GEP->getOperand(1))->isZero() ||
134 isa<Constant>(GEP->getOperand(2)))
135 return nullptr;
136
137 // Check that indices after the variable are constants and in-range for the
138 // type they index. Collect the indices. This is typically for arrays of
139 // structs.
140 SmallVector<unsigned, 4> LaterIndices;
141
142 Type *EltTy = Init->getType()->getArrayElementType();
143 for (unsigned i = 3, e = GEP->getNumOperands(); i != e; ++i) {
144 ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(i));
145 if (!Idx)
146 return nullptr; // Variable index.
147
148 uint64_t IdxVal = Idx->getZExtValue();
149 if ((unsigned)IdxVal != IdxVal)
150 return nullptr; // Too large array index.
151
152 if (StructType *STy = dyn_cast<StructType>(EltTy))
153 EltTy = STy->getElementType(IdxVal);
154 else if (ArrayType *ATy = dyn_cast<ArrayType>(EltTy)) {
155 if (IdxVal >= ATy->getNumElements())
156 return nullptr;
157 EltTy = ATy->getElementType();
158 } else {
159 return nullptr; // Unknown type.
160 }
161
162 LaterIndices.push_back(IdxVal);
163 }
164
165 enum { Overdefined = -3, Undefined = -2 };
166
167 // Variables for our state machines.
168
169 // FirstTrueElement/SecondTrueElement - Used to emit a comparison of the form
170 // "i == 47 | i == 87", where 47 is the first index the condition is true for,
171 // and 87 is the second (and last) index. FirstTrueElement is -2 when
172 // undefined, otherwise set to the first true element. SecondTrueElement is
173 // -2 when undefined, -3 when overdefined and >= 0 when that index is true.
174 int FirstTrueElement = Undefined, SecondTrueElement = Undefined;
175
176 // FirstFalseElement/SecondFalseElement - Used to emit a comparison of the
177 // form "i != 47 & i != 87". Same state transitions as for true elements.
178 int FirstFalseElement = Undefined, SecondFalseElement = Undefined;
179
180 /// TrueRangeEnd/FalseRangeEnd - In conjunction with First*Element, these
181 /// define a state machine that triggers for ranges of values that the index
182 /// is true or false for. This triggers on things like "abbbbc"[i] == 'b'.
183 /// This is -2 when undefined, -3 when overdefined, and otherwise the last
184 /// index in the range (inclusive). We use -2 for undefined here because we
185 /// use relative comparisons and don't want 0-1 to match -1.
186 int TrueRangeEnd = Undefined, FalseRangeEnd = Undefined;
187
188 // MagicBitvector - This is a magic bitvector where we set a bit if the
189 // comparison is true for element 'i'. If there are 64 elements or less in
190 // the array, this will fully represent all the comparison results.
191 uint64_t MagicBitvector = 0;
192
193 // Scan the array and see if one of our patterns matches.
194 Constant *CompareRHS = cast<Constant>(ICI.getOperand(1));
195 for (unsigned i = 0, e = ArrayElementCount; i != e; ++i) {
196 Constant *Elt = Init->getAggregateElement(i);
197 if (!Elt)
198 return nullptr;
199
200 // If this is indexing an array of structures, get the structure element.
201 if (!LaterIndices.empty()) {
202 Elt = ConstantFoldExtractValueInstruction(Elt, LaterIndices);
203 if (!Elt)
204 return nullptr;
205 }
206
207 // If the element is masked, handle it.
208 if (AndCst) {
209 Elt = ConstantFoldBinaryOpOperands(Instruction::And, Elt, AndCst, DL);
210 if (!Elt)
211 return nullptr;
212 }
213
214 // Find out if the comparison would be true or false for the i'th element.
216 CompareRHS, DL, &TLI);
217 if (!C)
218 return nullptr;
219
220 // If the result is undef for this element, ignore it.
221 if (isa<UndefValue>(C)) {
222 // Extend range state machines to cover this element in case there is an
223 // undef in the middle of the range.
224 if (TrueRangeEnd == (int)i - 1)
225 TrueRangeEnd = i;
226 if (FalseRangeEnd == (int)i - 1)
227 FalseRangeEnd = i;
228 continue;
229 }
230
231 // If we can't compute the result for any of the elements, we have to give
232 // up evaluating the entire conditional.
233 if (!isa<ConstantInt>(C))
234 return nullptr;
235
236 // Otherwise, we know if the comparison is true or false for this element,
237 // update our state machines.
238 bool IsTrueForElt = !cast<ConstantInt>(C)->isZero();
239
240 // State machine for single/double/range index comparison.
241 if (IsTrueForElt) {
242 // Update the TrueElement state machine.
243 if (FirstTrueElement == Undefined)
244 FirstTrueElement = TrueRangeEnd = i; // First true element.
245 else {
246 // Update double-compare state machine.
247 if (SecondTrueElement == Undefined)
248 SecondTrueElement = i;
249 else
250 SecondTrueElement = Overdefined;
251
252 // Update range state machine.
253 if (TrueRangeEnd == (int)i - 1)
254 TrueRangeEnd = i;
255 else
256 TrueRangeEnd = Overdefined;
257 }
258 } else {
259 // Update the FalseElement state machine.
260 if (FirstFalseElement == Undefined)
261 FirstFalseElement = FalseRangeEnd = i; // First false element.
262 else {
263 // Update double-compare state machine.
264 if (SecondFalseElement == Undefined)
265 SecondFalseElement = i;
266 else
267 SecondFalseElement = Overdefined;
268
269 // Update range state machine.
270 if (FalseRangeEnd == (int)i - 1)
271 FalseRangeEnd = i;
272 else
273 FalseRangeEnd = Overdefined;
274 }
275 }
276
277 // If this element is in range, update our magic bitvector.
278 if (i < 64 && IsTrueForElt)
279 MagicBitvector |= 1ULL << i;
280
281 // If all of our states become overdefined, bail out early. Since the
282 // predicate is expensive, only check it every 8 elements. This is only
283 // really useful for really huge arrays.
284 if ((i & 8) == 0 && i >= 64 && SecondTrueElement == Overdefined &&
285 SecondFalseElement == Overdefined && TrueRangeEnd == Overdefined &&
286 FalseRangeEnd == Overdefined)
287 return nullptr;
288 }
289
290 // Now that we've scanned the entire array, emit our new comparison(s). We
291 // order the state machines in complexity of the generated code.
292 Value *Idx = GEP->getOperand(2);
293
294 // If the index is larger than the pointer offset size of the target, truncate
295 // the index down like the GEP would do implicitly. We don't have to do this
296 // for an inbounds GEP because the index can't be out of range.
297 if (!GEP->isInBounds()) {
298 Type *PtrIdxTy = DL.getIndexType(GEP->getType());
299 unsigned OffsetSize = PtrIdxTy->getIntegerBitWidth();
300 if (Idx->getType()->getPrimitiveSizeInBits().getFixedValue() > OffsetSize)
301 Idx = Builder.CreateTrunc(Idx, PtrIdxTy);
302 }
303
304 // If inbounds keyword is not present, Idx * ElementSize can overflow.
305 // Let's assume that ElementSize is 2 and the wanted value is at offset 0.
306 // Then, there are two possible values for Idx to match offset 0:
307 // 0x00..00, 0x80..00.
308 // Emitting 'icmp eq Idx, 0' isn't correct in this case because the
309 // comparison is false if Idx was 0x80..00.
310 // We need to erase the highest countTrailingZeros(ElementSize) bits of Idx.
311 unsigned ElementSize =
312 DL.getTypeAllocSize(Init->getType()->getArrayElementType());
313 auto MaskIdx = [&](Value *Idx) {
314 if (!GEP->isInBounds() && llvm::countr_zero(ElementSize) != 0) {
315 Value *Mask = ConstantInt::get(Idx->getType(), -1);
316 Mask = Builder.CreateLShr(Mask, llvm::countr_zero(ElementSize));
317 Idx = Builder.CreateAnd(Idx, Mask);
318 }
319 return Idx;
320 };
321
322 // If the comparison is only true for one or two elements, emit direct
323 // comparisons.
324 if (SecondTrueElement != Overdefined) {
325 Idx = MaskIdx(Idx);
326 // None true -> false.
327 if (FirstTrueElement == Undefined)
328 return replaceInstUsesWith(ICI, Builder.getFalse());
329
330 Value *FirstTrueIdx = ConstantInt::get(Idx->getType(), FirstTrueElement);
331
332 // True for one element -> 'i == 47'.
333 if (SecondTrueElement == Undefined)
334 return new ICmpInst(ICmpInst::ICMP_EQ, Idx, FirstTrueIdx);
335
336 // True for two elements -> 'i == 47 | i == 72'.
337 Value *C1 = Builder.CreateICmpEQ(Idx, FirstTrueIdx);
338 Value *SecondTrueIdx = ConstantInt::get(Idx->getType(), SecondTrueElement);
339 Value *C2 = Builder.CreateICmpEQ(Idx, SecondTrueIdx);
340 return BinaryOperator::CreateOr(C1, C2);
341 }
342
343 // If the comparison is only false for one or two elements, emit direct
344 // comparisons.
345 if (SecondFalseElement != Overdefined) {
346 Idx = MaskIdx(Idx);
347 // None false -> true.
348 if (FirstFalseElement == Undefined)
349 return replaceInstUsesWith(ICI, Builder.getTrue());
350
351 Value *FirstFalseIdx = ConstantInt::get(Idx->getType(), FirstFalseElement);
352
353 // False for one element -> 'i != 47'.
354 if (SecondFalseElement == Undefined)
355 return new ICmpInst(ICmpInst::ICMP_NE, Idx, FirstFalseIdx);
356
357 // False for two elements -> 'i != 47 & i != 72'.
358 Value *C1 = Builder.CreateICmpNE(Idx, FirstFalseIdx);
359 Value *SecondFalseIdx =
360 ConstantInt::get(Idx->getType(), SecondFalseElement);
361 Value *C2 = Builder.CreateICmpNE(Idx, SecondFalseIdx);
362 return BinaryOperator::CreateAnd(C1, C2);
363 }
364
365 // If the comparison can be replaced with a range comparison for the elements
366 // where it is true, emit the range check.
367 if (TrueRangeEnd != Overdefined) {
368 assert(TrueRangeEnd != FirstTrueElement && "Should emit single compare");
369 Idx = MaskIdx(Idx);
370
371 // Generate (i-FirstTrue) <u (TrueRangeEnd-FirstTrue+1).
372 if (FirstTrueElement) {
373 Value *Offs = ConstantInt::get(Idx->getType(), -FirstTrueElement);
374 Idx = Builder.CreateAdd(Idx, Offs);
375 }
376
377 Value *End =
378 ConstantInt::get(Idx->getType(), TrueRangeEnd - FirstTrueElement + 1);
379 return new ICmpInst(ICmpInst::ICMP_ULT, Idx, End);
380 }
381
382 // False range check.
383 if (FalseRangeEnd != Overdefined) {
384 assert(FalseRangeEnd != FirstFalseElement && "Should emit single compare");
385 Idx = MaskIdx(Idx);
386 // Generate (i-FirstFalse) >u (FalseRangeEnd-FirstFalse).
387 if (FirstFalseElement) {
388 Value *Offs = ConstantInt::get(Idx->getType(), -FirstFalseElement);
389 Idx = Builder.CreateAdd(Idx, Offs);
390 }
391
392 Value *End =
393 ConstantInt::get(Idx->getType(), FalseRangeEnd - FirstFalseElement);
394 return new ICmpInst(ICmpInst::ICMP_UGT, Idx, End);
395 }
396
397 // If a magic bitvector captures the entire comparison state
398 // of this load, replace it with computation that does:
399 // ((magic_cst >> i) & 1) != 0
400 {
401 Type *Ty = nullptr;
402
403 // Look for an appropriate type:
404 // - The type of Idx if the magic fits
405 // - The smallest fitting legal type
406 if (ArrayElementCount <= Idx->getType()->getIntegerBitWidth())
407 Ty = Idx->getType();
408 else
409 Ty = DL.getSmallestLegalIntType(Init->getContext(), ArrayElementCount);
410
411 if (Ty) {
412 Idx = MaskIdx(Idx);
413 Value *V = Builder.CreateIntCast(Idx, Ty, false);
414 V = Builder.CreateLShr(ConstantInt::get(Ty, MagicBitvector), V);
415 V = Builder.CreateAnd(ConstantInt::get(Ty, 1), V);
416 return new ICmpInst(ICmpInst::ICMP_NE, V, ConstantInt::get(Ty, 0));
417 }
418 }
419
420 return nullptr;
421}
422
423/// Returns true if we can rewrite Start as a GEP with pointer Base
424/// and some integer offset. The nodes that need to be re-written
425/// for this transformation will be added to Explored.
427 const DataLayout &DL,
428 SetVector<Value *> &Explored) {
429 SmallVector<Value *, 16> WorkList(1, Start);
430 Explored.insert(Base);
431
432 // The following traversal gives us an order which can be used
433 // when doing the final transformation. Since in the final
434 // transformation we create the PHI replacement instructions first,
435 // we don't have to get them in any particular order.
436 //
437 // However, for other instructions we will have to traverse the
438 // operands of an instruction first, which means that we have to
439 // do a post-order traversal.
440 while (!WorkList.empty()) {
442
443 while (!WorkList.empty()) {
444 if (Explored.size() >= 100)
445 return false;
446
447 Value *V = WorkList.back();
448
449 if (Explored.contains(V)) {
450 WorkList.pop_back();
451 continue;
452 }
453
454 if (!isa<GetElementPtrInst>(V) && !isa<PHINode>(V))
455 // We've found some value that we can't explore which is different from
456 // the base. Therefore we can't do this transformation.
457 return false;
458
459 if (auto *GEP = dyn_cast<GEPOperator>(V)) {
460 // Only allow inbounds GEPs with at most one variable offset.
461 auto IsNonConst = [](Value *V) { return !isa<ConstantInt>(V); };
462 if (!GEP->isInBounds() || count_if(GEP->indices(), IsNonConst) > 1)
463 return false;
464
465 if (!Explored.contains(GEP->getOperand(0)))
466 WorkList.push_back(GEP->getOperand(0));
467 }
468
469 if (WorkList.back() == V) {
470 WorkList.pop_back();
471 // We've finished visiting this node, mark it as such.
472 Explored.insert(V);
473 }
474
475 if (auto *PN = dyn_cast<PHINode>(V)) {
476 // We cannot transform PHIs on unsplittable basic blocks.
477 if (isa<CatchSwitchInst>(PN->getParent()->getTerminator()))
478 return false;
479 Explored.insert(PN);
480 PHIs.insert(PN);
481 }
482 }
483
484 // Explore the PHI nodes further.
485 for (auto *PN : PHIs)
486 for (Value *Op : PN->incoming_values())
487 if (!Explored.contains(Op))
488 WorkList.push_back(Op);
489 }
490
491 // Make sure that we can do this. Since we can't insert GEPs in a basic
492 // block before a PHI node, we can't easily do this transformation if
493 // we have PHI node users of transformed instructions.
494 for (Value *Val : Explored) {
495 for (Value *Use : Val->uses()) {
496
497 auto *PHI = dyn_cast<PHINode>(Use);
498 auto *Inst = dyn_cast<Instruction>(Val);
499
500 if (Inst == Base || Inst == PHI || !Inst || !PHI ||
501 !Explored.contains(PHI))
502 continue;
503
504 if (PHI->getParent() == Inst->getParent())
505 return false;
506 }
507 }
508 return true;
509}
510
511// Sets the appropriate insert point on Builder where we can add
512// a replacement Instruction for V (if that is possible).
513static void setInsertionPoint(IRBuilder<> &Builder, Value *V,
514 bool Before = true) {
515 if (auto *PHI = dyn_cast<PHINode>(V)) {
516 BasicBlock *Parent = PHI->getParent();
517 Builder.SetInsertPoint(Parent, Parent->getFirstInsertionPt());
518 return;
519 }
520 if (auto *I = dyn_cast<Instruction>(V)) {
521 if (!Before)
522 I = &*std::next(I->getIterator());
523 Builder.SetInsertPoint(I);
524 return;
525 }
526 if (auto *A = dyn_cast<Argument>(V)) {
527 // Set the insertion point in the entry block.
528 BasicBlock &Entry = A->getParent()->getEntryBlock();
529 Builder.SetInsertPoint(&Entry, Entry.getFirstInsertionPt());
530 return;
531 }
532 // Otherwise, this is a constant and we don't need to set a new
533 // insertion point.
534 assert(isa<Constant>(V) && "Setting insertion point for unknown value!");
535}
536
537/// Returns a re-written value of Start as an indexed GEP using Base as a
538/// pointer.
540 const DataLayout &DL,
541 SetVector<Value *> &Explored,
542 InstCombiner &IC) {
543 // Perform all the substitutions. This is a bit tricky because we can
544 // have cycles in our use-def chains.
545 // 1. Create the PHI nodes without any incoming values.
546 // 2. Create all the other values.
547 // 3. Add the edges for the PHI nodes.
548 // 4. Emit GEPs to get the original pointers.
549 // 5. Remove the original instructions.
550 Type *IndexType = IntegerType::get(
551 Base->getContext(), DL.getIndexTypeSizeInBits(Start->getType()));
552
554 NewInsts[Base] = ConstantInt::getNullValue(IndexType);
555
556 // Create the new PHI nodes, without adding any incoming values.
557 for (Value *Val : Explored) {
558 if (Val == Base)
559 continue;
560 // Create empty phi nodes. This avoids cyclic dependencies when creating
561 // the remaining instructions.
562 if (auto *PHI = dyn_cast<PHINode>(Val))
563 NewInsts[PHI] =
564 PHINode::Create(IndexType, PHI->getNumIncomingValues(),
565 PHI->getName() + ".idx", PHI->getIterator());
566 }
567 IRBuilder<> Builder(Base->getContext());
568
569 // Create all the other instructions.
570 for (Value *Val : Explored) {
571 if (NewInsts.contains(Val))
572 continue;
573
574 if (auto *GEP = dyn_cast<GEPOperator>(Val)) {
575 setInsertionPoint(Builder, GEP);
576 Value *Op = NewInsts[GEP->getOperand(0)];
577 Value *OffsetV = emitGEPOffset(&Builder, DL, GEP);
578 if (isa<ConstantInt>(Op) && cast<ConstantInt>(Op)->isZero())
579 NewInsts[GEP] = OffsetV;
580 else
581 NewInsts[GEP] = Builder.CreateNSWAdd(
582 Op, OffsetV, GEP->getOperand(0)->getName() + ".add");
583 continue;
584 }
585 if (isa<PHINode>(Val))
586 continue;
587
588 llvm_unreachable("Unexpected instruction type");
589 }
590
591 // Add the incoming values to the PHI nodes.
592 for (Value *Val : Explored) {
593 if (Val == Base)
594 continue;
595 // All the instructions have been created, we can now add edges to the
596 // phi nodes.
597 if (auto *PHI = dyn_cast<PHINode>(Val)) {
598 PHINode *NewPhi = static_cast<PHINode *>(NewInsts[PHI]);
599 for (unsigned I = 0, E = PHI->getNumIncomingValues(); I < E; ++I) {
600 Value *NewIncoming = PHI->getIncomingValue(I);
601
602 if (NewInsts.contains(NewIncoming))
603 NewIncoming = NewInsts[NewIncoming];
604
605 NewPhi->addIncoming(NewIncoming, PHI->getIncomingBlock(I));
606 }
607 }
608 }
609
610 for (Value *Val : Explored) {
611 if (Val == Base)
612 continue;
613
614 setInsertionPoint(Builder, Val, false);
615 // Create GEP for external users.
616 Value *NewVal = Builder.CreateInBoundsGEP(
617 Builder.getInt8Ty(), Base, NewInsts[Val], Val->getName() + ".ptr");
618 IC.replaceInstUsesWith(*cast<Instruction>(Val), NewVal);
619 // Add old instruction to worklist for DCE. We don't directly remove it
620 // here because the original compare is one of the users.
621 IC.addToWorklist(cast<Instruction>(Val));
622 }
623
624 return NewInsts[Start];
625}
626
627/// Converts (CMP GEPLHS, RHS) if this change would make RHS a constant.
628/// We can look through PHIs, GEPs and casts in order to determine a common base
629/// between GEPLHS and RHS.
632 const DataLayout &DL,
633 InstCombiner &IC) {
634 // FIXME: Support vector of pointers.
635 if (GEPLHS->getType()->isVectorTy())
636 return nullptr;
637
638 if (!GEPLHS->hasAllConstantIndices())
639 return nullptr;
640
641 APInt Offset(DL.getIndexTypeSizeInBits(GEPLHS->getType()), 0);
642 Value *PtrBase =
644 /*AllowNonInbounds*/ false);
645
646 // Bail if we looked through addrspacecast.
647 if (PtrBase->getType() != GEPLHS->getType())
648 return nullptr;
649
650 // The set of nodes that will take part in this transformation.
651 SetVector<Value *> Nodes;
652
653 if (!canRewriteGEPAsOffset(RHS, PtrBase, DL, Nodes))
654 return nullptr;
655
656 // We know we can re-write this as
657 // ((gep Ptr, OFFSET1) cmp (gep Ptr, OFFSET2)
658 // Since we've only looked through inbouds GEPs we know that we
659 // can't have overflow on either side. We can therefore re-write
660 // this as:
661 // OFFSET1 cmp OFFSET2
662 Value *NewRHS = rewriteGEPAsOffset(RHS, PtrBase, DL, Nodes, IC);
663
664 // RewriteGEPAsOffset has replaced RHS and all of its uses with a re-written
665 // GEP having PtrBase as the pointer base, and has returned in NewRHS the
666 // offset. Since Index is the offset of LHS to the base pointer, we will now
667 // compare the offsets instead of comparing the pointers.
669 IC.Builder.getInt(Offset), NewRHS);
670}
671
672/// Fold comparisons between a GEP instruction and something else. At this point
673/// we know that the GEP is on the LHS of the comparison.
676 Instruction &I) {
677 // Don't transform signed compares of GEPs into index compares. Even if the
678 // GEP is inbounds, the final add of the base pointer can have signed overflow
679 // and would change the result of the icmp.
680 // e.g. "&foo[0] <s &foo[1]" can't be folded to "true" because "foo" could be
681 // the maximum signed value for the pointer type.
683 return nullptr;
684
685 // Look through bitcasts and addrspacecasts. We do not however want to remove
686 // 0 GEPs.
687 if (!isa<GetElementPtrInst>(RHS))
689
690 Value *PtrBase = GEPLHS->getOperand(0);
691 if (PtrBase == RHS && (GEPLHS->isInBounds() || ICmpInst::isEquality(Cond))) {
692 // ((gep Ptr, OFFSET) cmp Ptr) ---> (OFFSET cmp 0).
693 Value *Offset = EmitGEPOffset(GEPLHS);
695 Constant::getNullValue(Offset->getType()));
696 }
697
698 if (GEPLHS->isInBounds() && ICmpInst::isEquality(Cond) &&
699 isa<Constant>(RHS) && cast<Constant>(RHS)->isNullValue() &&
700 !NullPointerIsDefined(I.getFunction(),
702 // For most address spaces, an allocation can't be placed at null, but null
703 // itself is treated as a 0 size allocation in the in bounds rules. Thus,
704 // the only valid inbounds address derived from null, is null itself.
705 // Thus, we have four cases to consider:
706 // 1) Base == nullptr, Offset == 0 -> inbounds, null
707 // 2) Base == nullptr, Offset != 0 -> poison as the result is out of bounds
708 // 3) Base != nullptr, Offset == (-base) -> poison (crossing allocations)
709 // 4) Base != nullptr, Offset != (-base) -> nonnull (and possibly poison)
710 //
711 // (Note if we're indexing a type of size 0, that simply collapses into one
712 // of the buckets above.)
713 //
714 // In general, we're allowed to make values less poison (i.e. remove
715 // sources of full UB), so in this case, we just select between the two
716 // non-poison cases (1 and 4 above).
717 //
718 // For vectors, we apply the same reasoning on a per-lane basis.
719 auto *Base = GEPLHS->getPointerOperand();
720 if (GEPLHS->getType()->isVectorTy() && Base->getType()->isPointerTy()) {
721 auto EC = cast<VectorType>(GEPLHS->getType())->getElementCount();
723 }
724 return new ICmpInst(Cond, Base,
726 cast<Constant>(RHS), Base->getType()));
727 } else if (GEPOperator *GEPRHS = dyn_cast<GEPOperator>(RHS)) {
728 // If the base pointers are different, but the indices are the same, just
729 // compare the base pointer.
730 if (PtrBase != GEPRHS->getOperand(0)) {
731 bool IndicesTheSame =
732 GEPLHS->getNumOperands() == GEPRHS->getNumOperands() &&
733 GEPLHS->getPointerOperand()->getType() ==
734 GEPRHS->getPointerOperand()->getType() &&
735 GEPLHS->getSourceElementType() == GEPRHS->getSourceElementType();
736 if (IndicesTheSame)
737 for (unsigned i = 1, e = GEPLHS->getNumOperands(); i != e; ++i)
738 if (GEPLHS->getOperand(i) != GEPRHS->getOperand(i)) {
739 IndicesTheSame = false;
740 break;
741 }
742
743 // If all indices are the same, just compare the base pointers.
744 Type *BaseType = GEPLHS->getOperand(0)->getType();
745 if (IndicesTheSame && CmpInst::makeCmpResultType(BaseType) == I.getType())
746 return new ICmpInst(Cond, GEPLHS->getOperand(0), GEPRHS->getOperand(0));
747
748 // If we're comparing GEPs with two base pointers that only differ in type
749 // and both GEPs have only constant indices or just one use, then fold
750 // the compare with the adjusted indices.
751 // FIXME: Support vector of pointers.
752 if (GEPLHS->isInBounds() && GEPRHS->isInBounds() &&
753 (GEPLHS->hasAllConstantIndices() || GEPLHS->hasOneUse()) &&
754 (GEPRHS->hasAllConstantIndices() || GEPRHS->hasOneUse()) &&
755 PtrBase->stripPointerCasts() ==
756 GEPRHS->getOperand(0)->stripPointerCasts() &&
757 !GEPLHS->getType()->isVectorTy()) {
758 Value *LOffset = EmitGEPOffset(GEPLHS);
759 Value *ROffset = EmitGEPOffset(GEPRHS);
760
761 // If we looked through an addrspacecast between different sized address
762 // spaces, the LHS and RHS pointers are different sized
763 // integers. Truncate to the smaller one.
764 Type *LHSIndexTy = LOffset->getType();
765 Type *RHSIndexTy = ROffset->getType();
766 if (LHSIndexTy != RHSIndexTy) {
767 if (LHSIndexTy->getPrimitiveSizeInBits().getFixedValue() <
768 RHSIndexTy->getPrimitiveSizeInBits().getFixedValue()) {
769 ROffset = Builder.CreateTrunc(ROffset, LHSIndexTy);
770 } else
771 LOffset = Builder.CreateTrunc(LOffset, RHSIndexTy);
772 }
773
775 LOffset, ROffset);
776 return replaceInstUsesWith(I, Cmp);
777 }
778
779 // Otherwise, the base pointers are different and the indices are
780 // different. Try convert this to an indexed compare by looking through
781 // PHIs/casts.
782 return transformToIndexedCompare(GEPLHS, RHS, Cond, DL, *this);
783 }
784
785 bool GEPsInBounds = GEPLHS->isInBounds() && GEPRHS->isInBounds();
786 if (GEPLHS->getNumOperands() == GEPRHS->getNumOperands() &&
787 GEPLHS->getSourceElementType() == GEPRHS->getSourceElementType()) {
788 // If the GEPs only differ by one index, compare it.
789 unsigned NumDifferences = 0; // Keep track of # differences.
790 unsigned DiffOperand = 0; // The operand that differs.
791 for (unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
792 if (GEPLHS->getOperand(i) != GEPRHS->getOperand(i)) {
793 Type *LHSType = GEPLHS->getOperand(i)->getType();
794 Type *RHSType = GEPRHS->getOperand(i)->getType();
795 // FIXME: Better support for vector of pointers.
796 if (LHSType->getPrimitiveSizeInBits() !=
797 RHSType->getPrimitiveSizeInBits() ||
798 (GEPLHS->getType()->isVectorTy() &&
799 (!LHSType->isVectorTy() || !RHSType->isVectorTy()))) {
800 // Irreconcilable differences.
801 NumDifferences = 2;
802 break;
803 }
804
805 if (NumDifferences++) break;
806 DiffOperand = i;
807 }
808
809 if (NumDifferences == 0) // SAME GEP?
810 return replaceInstUsesWith(I, // No comparison is needed here.
811 ConstantInt::get(I.getType(), ICmpInst::isTrueWhenEqual(Cond)));
812
813 else if (NumDifferences == 1 && GEPsInBounds) {
814 Value *LHSV = GEPLHS->getOperand(DiffOperand);
815 Value *RHSV = GEPRHS->getOperand(DiffOperand);
816 // Make sure we do a signed comparison here.
817 return new ICmpInst(ICmpInst::getSignedPredicate(Cond), LHSV, RHSV);
818 }
819 }
820
821 if (GEPsInBounds || CmpInst::isEquality(Cond)) {
822 // ((gep Ptr, OFFSET1) cmp (gep Ptr, OFFSET2) ---> (OFFSET1 cmp OFFSET2)
823 Value *L = EmitGEPOffset(GEPLHS, /*RewriteGEP=*/true);
824 Value *R = EmitGEPOffset(GEPRHS, /*RewriteGEP=*/true);
825 return new ICmpInst(ICmpInst::getSignedPredicate(Cond), L, R);
826 }
827 }
828
829 // Try convert this to an indexed compare by looking through PHIs/casts as a
830 // last resort.
831 return transformToIndexedCompare(GEPLHS, RHS, Cond, DL, *this);
832}
833
835 // It would be tempting to fold away comparisons between allocas and any
836 // pointer not based on that alloca (e.g. an argument). However, even
837 // though such pointers cannot alias, they can still compare equal.
838 //
839 // But LLVM doesn't specify where allocas get their memory, so if the alloca
840 // doesn't escape we can argue that it's impossible to guess its value, and we
841 // can therefore act as if any such guesses are wrong.
842 //
843 // However, we need to ensure that this folding is consistent: We can't fold
844 // one comparison to false, and then leave a different comparison against the
845 // same value alone (as it might evaluate to true at runtime, leading to a
846 // contradiction). As such, this code ensures that all comparisons are folded
847 // at the same time, and there are no other escapes.
848
849 struct CmpCaptureTracker : public CaptureTracker {
850 AllocaInst *Alloca;
851 bool Captured = false;
852 /// The value of the map is a bit mask of which icmp operands the alloca is
853 /// used in.
855
856 CmpCaptureTracker(AllocaInst *Alloca) : Alloca(Alloca) {}
857
858 void tooManyUses() override { Captured = true; }
859
860 bool captured(const Use *U) override {
861 auto *ICmp = dyn_cast<ICmpInst>(U->getUser());
862 // We need to check that U is based *only* on the alloca, and doesn't
863 // have other contributions from a select/phi operand.
864 // TODO: We could check whether getUnderlyingObjects() reduces to one
865 // object, which would allow looking through phi nodes.
866 if (ICmp && ICmp->isEquality() && getUnderlyingObject(*U) == Alloca) {
867 // Collect equality icmps of the alloca, and don't treat them as
868 // captures.
869 auto Res = ICmps.insert({ICmp, 0});
870 Res.first->second |= 1u << U->getOperandNo();
871 return false;
872 }
873
874 Captured = true;
875 return true;
876 }
877 };
878
879 CmpCaptureTracker Tracker(Alloca);
880 PointerMayBeCaptured(Alloca, &Tracker);
881 if (Tracker.Captured)
882 return false;
883
884 bool Changed = false;
885 for (auto [ICmp, Operands] : Tracker.ICmps) {
886 switch (Operands) {
887 case 1:
888 case 2: {
889 // The alloca is only used in one icmp operand. Assume that the
890 // equality is false.
891 auto *Res = ConstantInt::get(
892 ICmp->getType(), ICmp->getPredicate() == ICmpInst::ICMP_NE);
893 replaceInstUsesWith(*ICmp, Res);
895 Changed = true;
896 break;
897 }
898 case 3:
899 // Both icmp operands are based on the alloca, so this is comparing
900 // pointer offsets, without leaking any information about the address
901 // of the alloca. Ignore such comparisons.
902 break;
903 default:
904 llvm_unreachable("Cannot happen");
905 }
906 }
907
908 return Changed;
909}
910
911/// Fold "icmp pred (X+C), X".
913 ICmpInst::Predicate Pred) {
914 // From this point on, we know that (X+C <= X) --> (X+C < X) because C != 0,
915 // so the values can never be equal. Similarly for all other "or equals"
916 // operators.
917 assert(!!C && "C should not be zero!");
918
919 // (X+1) <u X --> X >u (MAXUINT-1) --> X == 255
920 // (X+2) <u X --> X >u (MAXUINT-2) --> X > 253
921 // (X+MAXUINT) <u X --> X >u (MAXUINT-MAXUINT) --> X != 0
922 if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE) {
923 Constant *R = ConstantInt::get(X->getType(),
924 APInt::getMaxValue(C.getBitWidth()) - C);
925 return new ICmpInst(ICmpInst::ICMP_UGT, X, R);
926 }
927
928 // (X+1) >u X --> X <u (0-1) --> X != 255
929 // (X+2) >u X --> X <u (0-2) --> X <u 254
930 // (X+MAXUINT) >u X --> X <u (0-MAXUINT) --> X <u 1 --> X == 0
931 if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE)
932 return new ICmpInst(ICmpInst::ICMP_ULT, X,
933 ConstantInt::get(X->getType(), -C));
934
935 APInt SMax = APInt::getSignedMaxValue(C.getBitWidth());
936
937 // (X+ 1) <s X --> X >s (MAXSINT-1) --> X == 127
938 // (X+ 2) <s X --> X >s (MAXSINT-2) --> X >s 125
939 // (X+MAXSINT) <s X --> X >s (MAXSINT-MAXSINT) --> X >s 0
940 // (X+MINSINT) <s X --> X >s (MAXSINT-MINSINT) --> X >s -1
941 // (X+ -2) <s X --> X >s (MAXSINT- -2) --> X >s 126
942 // (X+ -1) <s X --> X >s (MAXSINT- -1) --> X != 127
943 if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE)
944 return new ICmpInst(ICmpInst::ICMP_SGT, X,
945 ConstantInt::get(X->getType(), SMax - C));
946
947 // (X+ 1) >s X --> X <s (MAXSINT-(1-1)) --> X != 127
948 // (X+ 2) >s X --> X <s (MAXSINT-(2-1)) --> X <s 126
949 // (X+MAXSINT) >s X --> X <s (MAXSINT-(MAXSINT-1)) --> X <s 1
950 // (X+MINSINT) >s X --> X <s (MAXSINT-(MINSINT-1)) --> X <s -2
951 // (X+ -2) >s X --> X <s (MAXSINT-(-2-1)) --> X <s -126
952 // (X+ -1) >s X --> X <s (MAXSINT-(-1-1)) --> X == -128
953
954 assert(Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE);
955 return new ICmpInst(ICmpInst::ICMP_SLT, X,
956 ConstantInt::get(X->getType(), SMax - (C - 1)));
957}
958
959/// Handle "(icmp eq/ne (ashr/lshr AP2, A), AP1)" ->
960/// (icmp eq/ne A, Log2(AP2/AP1)) ->
961/// (icmp eq/ne A, Log2(AP2) - Log2(AP1)).
963 const APInt &AP1,
964 const APInt &AP2) {
965 assert(I.isEquality() && "Cannot fold icmp gt/lt");
966
967 auto getICmp = [&I](CmpInst::Predicate Pred, Value *LHS, Value *RHS) {
968 if (I.getPredicate() == I.ICMP_NE)
969 Pred = CmpInst::getInversePredicate(Pred);
970 return new ICmpInst(Pred, LHS, RHS);
971 };
972
973 // Don't bother doing any work for cases which InstSimplify handles.
974 if (AP2.isZero())
975 return nullptr;
976
977 bool IsAShr = isa<AShrOperator>(I.getOperand(0));
978 if (IsAShr) {
979 if (AP2.isAllOnes())
980 return nullptr;
981 if (AP2.isNegative() != AP1.isNegative())
982 return nullptr;
983 if (AP2.sgt(AP1))
984 return nullptr;
985 }
986
987 if (!AP1)
988 // 'A' must be large enough to shift out the highest set bit.
989 return getICmp(I.ICMP_UGT, A,
990 ConstantInt::get(A->getType(), AP2.logBase2()));
991
992 if (AP1 == AP2)
993 return getICmp(I.ICMP_EQ, A, ConstantInt::getNullValue(A->getType()));
994
995 int Shift;
996 if (IsAShr && AP1.isNegative())
997 Shift = AP1.countl_one() - AP2.countl_one();
998 else
999 Shift = AP1.countl_zero() - AP2.countl_zero();
1000
1001 if (Shift > 0) {
1002 if (IsAShr && AP1 == AP2.ashr(Shift)) {
1003 // There are multiple solutions if we are comparing against -1 and the LHS
1004 // of the ashr is not a power of two.
1005 if (AP1.isAllOnes() && !AP2.isPowerOf2())
1006 return getICmp(I.ICMP_UGE, A, ConstantInt::get(A->getType(), Shift));
1007 return getICmp(I.ICMP_EQ, A, ConstantInt::get(A->getType(), Shift));
1008 } else if (AP1 == AP2.lshr(Shift)) {
1009 return getICmp(I.ICMP_EQ, A, ConstantInt::get(A->getType(), Shift));
1010 }
1011 }
1012
1013 // Shifting const2 will never be equal to const1.
1014 // FIXME: This should always be handled by InstSimplify?
1015 auto *TorF = ConstantInt::get(I.getType(), I.getPredicate() == I.ICMP_NE);
1016 return replaceInstUsesWith(I, TorF);
1017}
1018
1019/// Handle "(icmp eq/ne (shl AP2, A), AP1)" ->
1020/// (icmp eq/ne A, TrailingZeros(AP1) - TrailingZeros(AP2)).
1022 const APInt &AP1,
1023 const APInt &AP2) {
1024 assert(I.isEquality() && "Cannot fold icmp gt/lt");
1025
1026 auto getICmp = [&I](CmpInst::Predicate Pred, Value *LHS, Value *RHS) {
1027 if (I.getPredicate() == I.ICMP_NE)
1028 Pred = CmpInst::getInversePredicate(Pred);
1029 return new ICmpInst(Pred, LHS, RHS);
1030 };
1031
1032 // Don't bother doing any work for cases which InstSimplify handles.
1033 if (AP2.isZero())
1034 return nullptr;
1035
1036 unsigned AP2TrailingZeros = AP2.countr_zero();
1037
1038 if (!AP1 && AP2TrailingZeros != 0)
1039 return getICmp(
1040 I.ICMP_UGE, A,
1041 ConstantInt::get(A->getType(), AP2.getBitWidth() - AP2TrailingZeros));
1042
1043 if (AP1 == AP2)
1044 return getICmp(I.ICMP_EQ, A, ConstantInt::getNullValue(A->getType()));
1045
1046 // Get the distance between the lowest bits that are set.
1047 int Shift = AP1.countr_zero() - AP2TrailingZeros;
1048
1049 if (Shift > 0 && AP2.shl(Shift) == AP1)
1050 return getICmp(I.ICMP_EQ, A, ConstantInt::get(A->getType(), Shift));
1051
1052 // Shifting const2 will never be equal to const1.
1053 // FIXME: This should always be handled by InstSimplify?
1054 auto *TorF = ConstantInt::get(I.getType(), I.getPredicate() == I.ICMP_NE);
1055 return replaceInstUsesWith(I, TorF);
1056}
1057
1058/// The caller has matched a pattern of the form:
1059/// I = icmp ugt (add (add A, B), CI2), CI1
1060/// If this is of the form:
1061/// sum = a + b
1062/// if (sum+128 >u 255)
1063/// Then replace it with llvm.sadd.with.overflow.i8.
1064///
1066 ConstantInt *CI2, ConstantInt *CI1,
1067 InstCombinerImpl &IC) {
1068 // The transformation we're trying to do here is to transform this into an
1069 // llvm.sadd.with.overflow. To do this, we have to replace the original add
1070 // with a narrower add, and discard the add-with-constant that is part of the
1071 // range check (if we can't eliminate it, this isn't profitable).
1072
1073 // In order to eliminate the add-with-constant, the compare can be its only
1074 // use.
1075 Instruction *AddWithCst = cast<Instruction>(I.getOperand(0));
1076 if (!AddWithCst->hasOneUse())
1077 return nullptr;
1078
1079 // If CI2 is 2^7, 2^15, 2^31, then it might be an sadd.with.overflow.
1080 if (!CI2->getValue().isPowerOf2())
1081 return nullptr;
1082 unsigned NewWidth = CI2->getValue().countr_zero();
1083 if (NewWidth != 7 && NewWidth != 15 && NewWidth != 31)
1084 return nullptr;
1085
1086 // The width of the new add formed is 1 more than the bias.
1087 ++NewWidth;
1088
1089 // Check to see that CI1 is an all-ones value with NewWidth bits.
1090 if (CI1->getBitWidth() == NewWidth ||
1091 CI1->getValue() != APInt::getLowBitsSet(CI1->getBitWidth(), NewWidth))
1092 return nullptr;
1093
1094 // This is only really a signed overflow check if the inputs have been
1095 // sign-extended; check for that condition. For example, if CI2 is 2^31 and
1096 // the operands of the add are 64 bits wide, we need at least 33 sign bits.
1097 if (IC.ComputeMaxSignificantBits(A, 0, &I) > NewWidth ||
1098 IC.ComputeMaxSignificantBits(B, 0, &I) > NewWidth)
1099 return nullptr;
1100
1101 // In order to replace the original add with a narrower
1102 // llvm.sadd.with.overflow, the only uses allowed are the add-with-constant
1103 // and truncates that discard the high bits of the add. Verify that this is
1104 // the case.
1105 Instruction *OrigAdd = cast<Instruction>(AddWithCst->getOperand(0));
1106 for (User *U : OrigAdd->users()) {
1107 if (U == AddWithCst)
1108 continue;
1109
1110 // Only accept truncates for now. We would really like a nice recursive
1111 // predicate like SimplifyDemandedBits, but which goes downwards the use-def
1112 // chain to see which bits of a value are actually demanded. If the
1113 // original add had another add which was then immediately truncated, we
1114 // could still do the transformation.
1115 TruncInst *TI = dyn_cast<TruncInst>(U);
1116 if (!TI || TI->getType()->getPrimitiveSizeInBits() > NewWidth)
1117 return nullptr;
1118 }
1119
1120 // If the pattern matches, truncate the inputs to the narrower type and
1121 // use the sadd_with_overflow intrinsic to efficiently compute both the
1122 // result and the overflow bit.
1123 Type *NewType = IntegerType::get(OrigAdd->getContext(), NewWidth);
1125 I.getModule(), Intrinsic::sadd_with_overflow, NewType);
1126
1127 InstCombiner::BuilderTy &Builder = IC.Builder;
1128
1129 // Put the new code above the original add, in case there are any uses of the
1130 // add between the add and the compare.
1131 Builder.SetInsertPoint(OrigAdd);
1132
1133 Value *TruncA = Builder.CreateTrunc(A, NewType, A->getName() + ".trunc");
1134 Value *TruncB = Builder.CreateTrunc(B, NewType, B->getName() + ".trunc");
1135 CallInst *Call = Builder.CreateCall(F, {TruncA, TruncB}, "sadd");
1136 Value *Add = Builder.CreateExtractValue(Call, 0, "sadd.result");
1137 Value *ZExt = Builder.CreateZExt(Add, OrigAdd->getType());
1138
1139 // The inner add was the result of the narrow add, zero extended to the
1140 // wider type. Replace it with the result computed by the intrinsic.
1141 IC.replaceInstUsesWith(*OrigAdd, ZExt);
1142 IC.eraseInstFromFunction(*OrigAdd);
1143
1144 // The original icmp gets replaced with the overflow value.
1145 return ExtractValueInst::Create(Call, 1, "sadd.overflow");
1146}
1147
1148/// If we have:
1149/// icmp eq/ne (urem/srem %x, %y), 0
1150/// iff %y is a power-of-two, we can replace this with a bit test:
1151/// icmp eq/ne (and %x, (add %y, -1)), 0
1153 // This fold is only valid for equality predicates.
1154 if (!I.isEquality())
1155 return nullptr;
1157 Value *X, *Y, *Zero;
1158 if (!match(&I, m_ICmp(Pred, m_OneUse(m_IRem(m_Value(X), m_Value(Y))),
1159 m_CombineAnd(m_Zero(), m_Value(Zero)))))
1160 return nullptr;
1161 if (!isKnownToBeAPowerOfTwo(Y, /*OrZero*/ true, 0, &I))
1162 return nullptr;
1163 // This may increase instruction count, we don't enforce that Y is a constant.
1164 Value *Mask = Builder.CreateAdd(Y, Constant::getAllOnesValue(Y->getType()));
1165 Value *Masked = Builder.CreateAnd(X, Mask);
1166 return ICmpInst::Create(Instruction::ICmp, Pred, Masked, Zero);
1167}
1168
1169/// Fold equality-comparison between zero and any (maybe truncated) right-shift
1170/// by one-less-than-bitwidth into a sign test on the original value.
1172 Instruction *Val;
1174 if (!I.isEquality() || !match(&I, m_ICmp(Pred, m_Instruction(Val), m_Zero())))
1175 return nullptr;
1176
1177 Value *X;
1178 Type *XTy;
1179
1180 Constant *C;
1181 if (match(Val, m_TruncOrSelf(m_Shr(m_Value(X), m_Constant(C))))) {
1182 XTy = X->getType();
1183 unsigned XBitWidth = XTy->getScalarSizeInBits();
1185 APInt(XBitWidth, XBitWidth - 1))))
1186 return nullptr;
1187 } else if (isa<BinaryOperator>(Val) &&
1189 cast<BinaryOperator>(Val), SQ.getWithInstruction(Val),
1190 /*AnalyzeForSignBitExtraction=*/true))) {
1191 XTy = X->getType();
1192 } else
1193 return nullptr;
1194
1195 return ICmpInst::Create(Instruction::ICmp,
1199}
1200
1201// Handle icmp pred X, 0
1203 CmpInst::Predicate Pred = Cmp.getPredicate();
1204 if (!match(Cmp.getOperand(1), m_Zero()))
1205 return nullptr;
1206
1207 // (icmp sgt smin(PosA, B) 0) -> (icmp sgt B 0)
1208 if (Pred == ICmpInst::ICMP_SGT) {
1209 Value *A, *B;
1210 if (match(Cmp.getOperand(0), m_SMin(m_Value(A), m_Value(B)))) {
1212 return new ICmpInst(Pred, B, Cmp.getOperand(1));
1214 return new ICmpInst(Pred, A, Cmp.getOperand(1));
1215 }
1216 }
1217
1219 return New;
1220
1221 // Given:
1222 // icmp eq/ne (urem %x, %y), 0
1223 // Iff %x has 0 or 1 bits set, and %y has at least 2 bits set, omit 'urem':
1224 // icmp eq/ne %x, 0
1225 Value *X, *Y;
1226 if (match(Cmp.getOperand(0), m_URem(m_Value(X), m_Value(Y))) &&
1227 ICmpInst::isEquality(Pred)) {
1228 KnownBits XKnown = computeKnownBits(X, 0, &Cmp);
1229 KnownBits YKnown = computeKnownBits(Y, 0, &Cmp);
1230 if (XKnown.countMaxPopulation() == 1 && YKnown.countMinPopulation() >= 2)
1231 return new ICmpInst(Pred, X, Cmp.getOperand(1));
1232 }
1233
1234 // (icmp eq/ne (mul X Y)) -> (icmp eq/ne X/Y) if we know about whether X/Y are
1235 // odd/non-zero/there is no overflow.
1236 if (match(Cmp.getOperand(0), m_Mul(m_Value(X), m_Value(Y))) &&
1237 ICmpInst::isEquality(Pred)) {
1238
1239 KnownBits XKnown = computeKnownBits(X, 0, &Cmp);
1240 // if X % 2 != 0
1241 // (icmp eq/ne Y)
1242 if (XKnown.countMaxTrailingZeros() == 0)
1243 return new ICmpInst(Pred, Y, Cmp.getOperand(1));
1244
1245 KnownBits YKnown = computeKnownBits(Y, 0, &Cmp);
1246 // if Y % 2 != 0
1247 // (icmp eq/ne X)
1248 if (YKnown.countMaxTrailingZeros() == 0)
1249 return new ICmpInst(Pred, X, Cmp.getOperand(1));
1250
1251 auto *BO0 = cast<OverflowingBinaryOperator>(Cmp.getOperand(0));
1252 if (BO0->hasNoUnsignedWrap() || BO0->hasNoSignedWrap()) {
1253 const SimplifyQuery Q = SQ.getWithInstruction(&Cmp);
1254 // `isKnownNonZero` does more analysis than just `!KnownBits.One.isZero()`
1255 // but to avoid unnecessary work, first just if this is an obvious case.
1256
1257 // if X non-zero and NoOverflow(X * Y)
1258 // (icmp eq/ne Y)
1259 if (!XKnown.One.isZero() || isKnownNonZero(X, Q))
1260 return new ICmpInst(Pred, Y, Cmp.getOperand(1));
1261
1262 // if Y non-zero and NoOverflow(X * Y)
1263 // (icmp eq/ne X)
1264 if (!YKnown.One.isZero() || isKnownNonZero(Y, Q))
1265 return new ICmpInst(Pred, X, Cmp.getOperand(1));
1266 }
1267 // Note, we are skipping cases:
1268 // if Y % 2 != 0 AND X % 2 != 0
1269 // (false/true)
1270 // if X non-zero and Y non-zero and NoOverflow(X * Y)
1271 // (false/true)
1272 // Those can be simplified later as we would have already replaced the (icmp
1273 // eq/ne (mul X, Y)) with (icmp eq/ne X/Y) and if X/Y is known non-zero that
1274 // will fold to a constant elsewhere.
1275 }
1276 return nullptr;
1277}
1278
1279/// Fold icmp Pred X, C.
1280/// TODO: This code structure does not make sense. The saturating add fold
1281/// should be moved to some other helper and extended as noted below (it is also
1282/// possible that code has been made unnecessary - do we canonicalize IR to
1283/// overflow/saturating intrinsics or not?).
1285 // Match the following pattern, which is a common idiom when writing
1286 // overflow-safe integer arithmetic functions. The source performs an addition
1287 // in wider type and explicitly checks for overflow using comparisons against
1288 // INT_MIN and INT_MAX. Simplify by using the sadd_with_overflow intrinsic.
1289 //
1290 // TODO: This could probably be generalized to handle other overflow-safe
1291 // operations if we worked out the formulas to compute the appropriate magic
1292 // constants.
1293 //
1294 // sum = a + b
1295 // if (sum+128 >u 255) ... -> llvm.sadd.with.overflow.i8
1296 CmpInst::Predicate Pred = Cmp.getPredicate();
1297 Value *Op0 = Cmp.getOperand(0), *Op1 = Cmp.getOperand(1);
1298 Value *A, *B;
1299 ConstantInt *CI, *CI2; // I = icmp ugt (add (add A, B), CI2), CI
1300 if (Pred == ICmpInst::ICMP_UGT && match(Op1, m_ConstantInt(CI)) &&
1301 match(Op0, m_Add(m_Add(m_Value(A), m_Value(B)), m_ConstantInt(CI2))))
1302 if (Instruction *Res = processUGT_ADDCST_ADD(Cmp, A, B, CI2, CI, *this))
1303 return Res;
1304
1305 // icmp(phi(C1, C2, ...), C) -> phi(icmp(C1, C), icmp(C2, C), ...).
1306 Constant *C = dyn_cast<Constant>(Op1);
1307 if (!C)
1308 return nullptr;
1309
1310 if (auto *Phi = dyn_cast<PHINode>(Op0))
1311 if (all_of(Phi->operands(), [](Value *V) { return isa<Constant>(V); })) {
1313 for (Value *V : Phi->incoming_values()) {
1314 Constant *Res =
1315 ConstantFoldCompareInstOperands(Pred, cast<Constant>(V), C, DL);
1316 if (!Res)
1317 return nullptr;
1318 Ops.push_back(Res);
1319 }
1321 PHINode *NewPhi = Builder.CreatePHI(Cmp.getType(), Phi->getNumOperands());
1322 for (auto [V, Pred] : zip(Ops, Phi->blocks()))
1323 NewPhi->addIncoming(V, Pred);
1324 return replaceInstUsesWith(Cmp, NewPhi);
1325 }
1326
1328 return R;
1329
1330 return nullptr;
1331}
1332
1333/// Canonicalize icmp instructions based on dominating conditions.
1335 // We already checked simple implication in InstSimplify, only handle complex
1336 // cases here.
1337 Value *X = Cmp.getOperand(0), *Y = Cmp.getOperand(1);
1338 const APInt *C;
1339 if (!match(Y, m_APInt(C)))
1340 return nullptr;
1341
1342 CmpInst::Predicate Pred = Cmp.getPredicate();
1344
1345 auto handleDomCond = [&](ICmpInst::Predicate DomPred,
1346 const APInt *DomC) -> Instruction * {
1347 // We have 2 compares of a variable with constants. Calculate the constant
1348 // ranges of those compares to see if we can transform the 2nd compare:
1349 // DomBB:
1350 // DomCond = icmp DomPred X, DomC
1351 // br DomCond, CmpBB, FalseBB
1352 // CmpBB:
1353 // Cmp = icmp Pred X, C
1354 ConstantRange DominatingCR =
1355 ConstantRange::makeExactICmpRegion(DomPred, *DomC);
1356 ConstantRange Intersection = DominatingCR.intersectWith(CR);
1357 ConstantRange Difference = DominatingCR.difference(CR);
1358 if (Intersection.isEmptySet())
1359 return replaceInstUsesWith(Cmp, Builder.getFalse());
1360 if (Difference.isEmptySet())
1361 return replaceInstUsesWith(Cmp, Builder.getTrue());
1362
1363 // Canonicalizing a sign bit comparison that gets used in a branch,
1364 // pessimizes codegen by generating branch on zero instruction instead
1365 // of a test and branch. So we avoid canonicalizing in such situations
1366 // because test and branch instruction has better branch displacement
1367 // than compare and branch instruction.
1368 bool UnusedBit;
1369 bool IsSignBit = isSignBitCheck(Pred, *C, UnusedBit);
1370 if (Cmp.isEquality() || (IsSignBit && hasBranchUse(Cmp)))
1371 return nullptr;
1372
1373 // Avoid an infinite loop with min/max canonicalization.
1374 // TODO: This will be unnecessary if we canonicalize to min/max intrinsics.
1375 if (Cmp.hasOneUse() &&
1376 match(Cmp.user_back(), m_MaxOrMin(m_Value(), m_Value())))
1377 return nullptr;
1378
1379 if (const APInt *EqC = Intersection.getSingleElement())
1380 return new ICmpInst(ICmpInst::ICMP_EQ, X, Builder.getInt(*EqC));
1381 if (const APInt *NeC = Difference.getSingleElement())
1382 return new ICmpInst(ICmpInst::ICMP_NE, X, Builder.getInt(*NeC));
1383 return nullptr;
1384 };
1385
1386 for (BranchInst *BI : DC.conditionsFor(X)) {
1387 ICmpInst::Predicate DomPred;
1388 const APInt *DomC;
1389 if (!match(BI->getCondition(),
1390 m_ICmp(DomPred, m_Specific(X), m_APInt(DomC))))
1391 continue;
1392
1393 BasicBlockEdge Edge0(BI->getParent(), BI->getSuccessor(0));
1394 if (DT.dominates(Edge0, Cmp.getParent())) {
1395 if (auto *V = handleDomCond(DomPred, DomC))
1396 return V;
1397 } else {
1398 BasicBlockEdge Edge1(BI->getParent(), BI->getSuccessor(1));
1399 if (DT.dominates(Edge1, Cmp.getParent()))
1400 if (auto *V =
1401 handleDomCond(CmpInst::getInversePredicate(DomPred), DomC))
1402 return V;
1403 }
1404 }
1405
1406 return nullptr;
1407}
1408
1409/// Fold icmp (trunc X), C.
1411 TruncInst *Trunc,
1412 const APInt &C) {
1413 ICmpInst::Predicate Pred = Cmp.getPredicate();
1414 Value *X = Trunc->getOperand(0);
1415 Type *SrcTy = X->getType();
1416 unsigned DstBits = Trunc->getType()->getScalarSizeInBits(),
1417 SrcBits = SrcTy->getScalarSizeInBits();
1418
1419 // Match (icmp pred (trunc nuw/nsw X), C)
1420 // Which we can convert to (icmp pred X, (sext/zext C))
1421 if (shouldChangeType(Trunc->getType(), SrcTy)) {
1422 if (Trunc->hasNoSignedWrap())
1423 return new ICmpInst(Pred, X, ConstantInt::get(SrcTy, C.sext(SrcBits)));
1424 if (!Cmp.isSigned() && Trunc->hasNoUnsignedWrap())
1425 return new ICmpInst(Pred, X, ConstantInt::get(SrcTy, C.zext(SrcBits)));
1426 }
1427
1428 if (C.isOne() && C.getBitWidth() > 1) {
1429 // icmp slt trunc(signum(V)) 1 --> icmp slt V, 1
1430 Value *V = nullptr;
1431 if (Pred == ICmpInst::ICMP_SLT && match(X, m_Signum(m_Value(V))))
1432 return new ICmpInst(ICmpInst::ICMP_SLT, V,
1433 ConstantInt::get(V->getType(), 1));
1434 }
1435
1436 // TODO: Handle any shifted constant by subtracting trailing zeros.
1437 // TODO: Handle non-equality predicates.
1438 Value *Y;
1439 if (Cmp.isEquality() && match(X, m_Shl(m_One(), m_Value(Y)))) {
1440 // (trunc (1 << Y) to iN) == 0 --> Y u>= N
1441 // (trunc (1 << Y) to iN) != 0 --> Y u< N
1442 if (C.isZero()) {
1443 auto NewPred = (Pred == Cmp.ICMP_EQ) ? Cmp.ICMP_UGE : Cmp.ICMP_ULT;
1444 return new ICmpInst(NewPred, Y, ConstantInt::get(SrcTy, DstBits));
1445 }
1446 // (trunc (1 << Y) to iN) == 2**C --> Y == C
1447 // (trunc (1 << Y) to iN) != 2**C --> Y != C
1448 if (C.isPowerOf2())
1449 return new ICmpInst(Pred, Y, ConstantInt::get(SrcTy, C.logBase2()));
1450 }
1451
1452 if (Cmp.isEquality() && Trunc->hasOneUse()) {
1453 // Canonicalize to a mask and wider compare if the wide type is suitable:
1454 // (trunc X to i8) == C --> (X & 0xff) == (zext C)
1455 if (!SrcTy->isVectorTy() && shouldChangeType(DstBits, SrcBits)) {
1456 Constant *Mask =
1457 ConstantInt::get(SrcTy, APInt::getLowBitsSet(SrcBits, DstBits));
1458 Value *And = Builder.CreateAnd(X, Mask);
1459 Constant *WideC = ConstantInt::get(SrcTy, C.zext(SrcBits));
1460 return new ICmpInst(Pred, And, WideC);
1461 }
1462
1463 // Simplify icmp eq (trunc x to i8), 42 -> icmp eq x, 42|highbits if all
1464 // of the high bits truncated out of x are known.
1465 KnownBits Known = computeKnownBits(X, 0, &Cmp);
1466
1467 // If all the high bits are known, we can do this xform.
1468 if ((Known.Zero | Known.One).countl_one() >= SrcBits - DstBits) {
1469 // Pull in the high bits from known-ones set.
1470 APInt NewRHS = C.zext(SrcBits);
1471 NewRHS |= Known.One & APInt::getHighBitsSet(SrcBits, SrcBits - DstBits);
1472 return new ICmpInst(Pred, X, ConstantInt::get(SrcTy, NewRHS));
1473 }
1474 }
1475
1476 // Look through truncated right-shift of the sign-bit for a sign-bit check:
1477 // trunc iN (ShOp >> ShAmtC) to i[N - ShAmtC] < 0 --> ShOp < 0
1478 // trunc iN (ShOp >> ShAmtC) to i[N - ShAmtC] > -1 --> ShOp > -1
1479 Value *ShOp;
1480 const APInt *ShAmtC;
1481 bool TrueIfSigned;
1482 if (isSignBitCheck(Pred, C, TrueIfSigned) &&
1483 match(X, m_Shr(m_Value(ShOp), m_APInt(ShAmtC))) &&
1484 DstBits == SrcBits - ShAmtC->getZExtValue()) {
1485 return TrueIfSigned ? new ICmpInst(ICmpInst::ICMP_SLT, ShOp,
1487 : new ICmpInst(ICmpInst::ICMP_SGT, ShOp,
1489 }
1490
1491 return nullptr;
1492}
1493
1494/// Fold icmp (trunc nuw/nsw X), (trunc nuw/nsw Y).
1495/// Fold icmp (trunc nuw/nsw X), (zext/sext Y).
1498 const SimplifyQuery &Q) {
1499 Value *X, *Y;
1501 bool YIsSExt = false;
1502 // Try to match icmp (trunc X), (trunc Y)
1503 if (match(&Cmp, m_ICmp(Pred, m_Trunc(m_Value(X)), m_Trunc(m_Value(Y))))) {
1504 unsigned NoWrapFlags = cast<TruncInst>(Cmp.getOperand(0))->getNoWrapKind() &
1505 cast<TruncInst>(Cmp.getOperand(1))->getNoWrapKind();
1506 if (Cmp.isSigned()) {
1507 // For signed comparisons, both truncs must be nsw.
1508 if (!(NoWrapFlags & TruncInst::NoSignedWrap))
1509 return nullptr;
1510 } else {
1511 // For unsigned and equality comparisons, either both must be nuw or
1512 // both must be nsw, we don't care which.
1513 if (!NoWrapFlags)
1514 return nullptr;
1515 }
1516
1517 if (X->getType() != Y->getType() &&
1518 (!Cmp.getOperand(0)->hasOneUse() || !Cmp.getOperand(1)->hasOneUse()))
1519 return nullptr;
1520 if (!isDesirableIntType(X->getType()->getScalarSizeInBits()) &&
1521 isDesirableIntType(Y->getType()->getScalarSizeInBits())) {
1522 std::swap(X, Y);
1523 Pred = Cmp.getSwappedPredicate(Pred);
1524 }
1525 YIsSExt = !(NoWrapFlags & TruncInst::NoUnsignedWrap);
1526 }
1527 // Try to match icmp (trunc nuw X), (zext Y)
1528 else if (!Cmp.isSigned() &&
1529 match(&Cmp, m_c_ICmp(Pred, m_NUWTrunc(m_Value(X)),
1530 m_OneUse(m_ZExt(m_Value(Y)))))) {
1531 // Can fold trunc nuw + zext for unsigned and equality predicates.
1532 }
1533 // Try to match icmp (trunc nsw X), (sext Y)
1534 else if (match(&Cmp, m_c_ICmp(Pred, m_NSWTrunc(m_Value(X)),
1536 // Can fold trunc nsw + zext/sext for all predicates.
1537 YIsSExt =
1538 isa<SExtInst>(Cmp.getOperand(0)) || isa<SExtInst>(Cmp.getOperand(1));
1539 } else
1540 return nullptr;
1541
1542 Type *TruncTy = Cmp.getOperand(0)->getType();
1543 unsigned TruncBits = TruncTy->getScalarSizeInBits();
1544
1545 // If this transform will end up changing from desirable types -> undesirable
1546 // types skip it.
1547 if (isDesirableIntType(TruncBits) &&
1548 !isDesirableIntType(X->getType()->getScalarSizeInBits()))
1549 return nullptr;
1550
1551 Value *NewY = Builder.CreateIntCast(Y, X->getType(), YIsSExt);
1552 return new ICmpInst(Pred, X, NewY);
1553}
1554
1555/// Fold icmp (xor X, Y), C.
1558 const APInt &C) {
1559 if (Instruction *I = foldICmpXorShiftConst(Cmp, Xor, C))
1560 return I;
1561
1562 Value *X = Xor->getOperand(0);
1563 Value *Y = Xor->getOperand(1);
1564 const APInt *XorC;
1565 if (!match(Y, m_APInt(XorC)))
1566 return nullptr;
1567
1568 // If this is a comparison that tests the signbit (X < 0) or (x > -1),
1569 // fold the xor.
1570 ICmpInst::Predicate Pred = Cmp.getPredicate();
1571 bool TrueIfSigned = false;
1572 if (isSignBitCheck(Cmp.getPredicate(), C, TrueIfSigned)) {
1573
1574 // If the sign bit of the XorCst is not set, there is no change to
1575 // the operation, just stop using the Xor.
1576 if (!XorC->isNegative())
1577 return replaceOperand(Cmp, 0, X);
1578
1579 // Emit the opposite comparison.
1580 if (TrueIfSigned)
1581 return new ICmpInst(ICmpInst::ICMP_SGT, X,
1582 ConstantInt::getAllOnesValue(X->getType()));
1583 else
1584 return new ICmpInst(ICmpInst::ICMP_SLT, X,
1585 ConstantInt::getNullValue(X->getType()));
1586 }
1587
1588 if (Xor->hasOneUse()) {
1589 // (icmp u/s (xor X SignMask), C) -> (icmp s/u X, (xor C SignMask))
1590 if (!Cmp.isEquality() && XorC->isSignMask()) {
1591 Pred = Cmp.getFlippedSignednessPredicate();
1592 return new ICmpInst(Pred, X, ConstantInt::get(X->getType(), C ^ *XorC));
1593 }
1594
1595 // (icmp u/s (xor X ~SignMask), C) -> (icmp s/u X, (xor C ~SignMask))
1596 if (!Cmp.isEquality() && XorC->isMaxSignedValue()) {
1597 Pred = Cmp.getFlippedSignednessPredicate();
1598 Pred = Cmp.getSwappedPredicate(Pred);
1599 return new ICmpInst(Pred, X, ConstantInt::get(X->getType(), C ^ *XorC));
1600 }
1601 }
1602
1603 // Mask constant magic can eliminate an 'xor' with unsigned compares.
1604 if (Pred == ICmpInst::ICMP_UGT) {
1605 // (xor X, ~C) >u C --> X <u ~C (when C+1 is a power of 2)
1606 if (*XorC == ~C && (C + 1).isPowerOf2())
1607 return new ICmpInst(ICmpInst::ICMP_ULT, X, Y);
1608 // (xor X, C) >u C --> X >u C (when C+1 is a power of 2)
1609 if (*XorC == C && (C + 1).isPowerOf2())
1610 return new ICmpInst(ICmpInst::ICMP_UGT, X, Y);
1611 }
1612 if (Pred == ICmpInst::ICMP_ULT) {
1613 // (xor X, -C) <u C --> X >u ~C (when C is a power of 2)
1614 if (*XorC == -C && C.isPowerOf2())
1615 return new ICmpInst(ICmpInst::ICMP_UGT, X,
1616 ConstantInt::get(X->getType(), ~C));
1617 // (xor X, C) <u C --> X >u ~C (when -C is a power of 2)
1618 if (*XorC == C && (-C).isPowerOf2())
1619 return new ICmpInst(ICmpInst::ICMP_UGT, X,
1620 ConstantInt::get(X->getType(), ~C));
1621 }
1622 return nullptr;
1623}
1624
1625/// For power-of-2 C:
1626/// ((X s>> ShiftC) ^ X) u< C --> (X + C) u< (C << 1)
1627/// ((X s>> ShiftC) ^ X) u> (C - 1) --> (X + C) u> ((C << 1) - 1)
1630 const APInt &C) {
1631 CmpInst::Predicate Pred = Cmp.getPredicate();
1632 APInt PowerOf2;
1633 if (Pred == ICmpInst::ICMP_ULT)
1634 PowerOf2 = C;
1635 else if (Pred == ICmpInst::ICMP_UGT && !C.isMaxValue())
1636 PowerOf2 = C + 1;
1637 else
1638 return nullptr;
1639 if (!PowerOf2.isPowerOf2())
1640 return nullptr;
1641 Value *X;
1642 const APInt *ShiftC;
1644 m_AShr(m_Deferred(X), m_APInt(ShiftC))))))
1645 return nullptr;
1646 uint64_t Shift = ShiftC->getLimitedValue();
1647 Type *XType = X->getType();
1648 if (Shift == 0 || PowerOf2.isMinSignedValue())
1649 return nullptr;
1650 Value *Add = Builder.CreateAdd(X, ConstantInt::get(XType, PowerOf2));
1651 APInt Bound =
1652 Pred == ICmpInst::ICMP_ULT ? PowerOf2 << 1 : ((PowerOf2 << 1) - 1);
1653 return new ICmpInst(Pred, Add, ConstantInt::get(XType, Bound));
1654}
1655
1656/// Fold icmp (and (sh X, Y), C2), C1.
1659 const APInt &C1,
1660 const APInt &C2) {
1661 BinaryOperator *Shift = dyn_cast<BinaryOperator>(And->getOperand(0));
1662 if (!Shift || !Shift->isShift())
1663 return nullptr;
1664
1665 // If this is: (X >> C3) & C2 != C1 (where any shift and any compare could
1666 // exist), turn it into (X & (C2 << C3)) != (C1 << C3). This happens a LOT in
1667 // code produced by the clang front-end, for bitfield access.
1668 // This seemingly simple opportunity to fold away a shift turns out to be
1669 // rather complicated. See PR17827 for details.
1670 unsigned ShiftOpcode = Shift->getOpcode();
1671 bool IsShl = ShiftOpcode == Instruction::Shl;
1672 const APInt *C3;
1673 if (match(Shift->getOperand(1), m_APInt(C3))) {
1674 APInt NewAndCst, NewCmpCst;
1675 bool AnyCmpCstBitsShiftedOut;
1676 if (ShiftOpcode == Instruction::Shl) {
1677 // For a left shift, we can fold if the comparison is not signed. We can
1678 // also fold a signed comparison if the mask value and comparison value
1679 // are not negative. These constraints may not be obvious, but we can
1680 // prove that they are correct using an SMT solver.
1681 if (Cmp.isSigned() && (C2.isNegative() || C1.isNegative()))
1682 return nullptr;
1683
1684 NewCmpCst = C1.lshr(*C3);
1685 NewAndCst = C2.lshr(*C3);
1686 AnyCmpCstBitsShiftedOut = NewCmpCst.shl(*C3) != C1;
1687 } else if (ShiftOpcode == Instruction::LShr) {
1688 // For a logical right shift, we can fold if the comparison is not signed.
1689 // We can also fold a signed comparison if the shifted mask value and the
1690 // shifted comparison value are not negative. These constraints may not be
1691 // obvious, but we can prove that they are correct using an SMT solver.
1692 NewCmpCst = C1.shl(*C3);
1693 NewAndCst = C2.shl(*C3);
1694 AnyCmpCstBitsShiftedOut = NewCmpCst.lshr(*C3) != C1;
1695 if (Cmp.isSigned() && (NewAndCst.isNegative() || NewCmpCst.isNegative()))
1696 return nullptr;
1697 } else {
1698 // For an arithmetic shift, check that both constants don't use (in a
1699 // signed sense) the top bits being shifted out.
1700 assert(ShiftOpcode == Instruction::AShr && "Unknown shift opcode");
1701 NewCmpCst = C1.shl(*C3);
1702 NewAndCst = C2.shl(*C3);
1703 AnyCmpCstBitsShiftedOut = NewCmpCst.ashr(*C3) != C1;
1704 if (NewAndCst.ashr(*C3) != C2)
1705 return nullptr;
1706 }
1707
1708 if (AnyCmpCstBitsShiftedOut) {
1709 // If we shifted bits out, the fold is not going to work out. As a
1710 // special case, check to see if this means that the result is always
1711 // true or false now.
1712 if (Cmp.getPredicate() == ICmpInst::ICMP_EQ)
1713 return replaceInstUsesWith(Cmp, ConstantInt::getFalse(Cmp.getType()));
1714 if (Cmp.getPredicate() == ICmpInst::ICMP_NE)
1715 return replaceInstUsesWith(Cmp, ConstantInt::getTrue(Cmp.getType()));
1716 } else {
1717 Value *NewAnd = Builder.CreateAnd(
1718 Shift->getOperand(0), ConstantInt::get(And->getType(), NewAndCst));
1719 return new ICmpInst(Cmp.getPredicate(),
1720 NewAnd, ConstantInt::get(And->getType(), NewCmpCst));
1721 }
1722 }
1723
1724 // Turn ((X >> Y) & C2) == 0 into (X & (C2 << Y)) == 0. The latter is
1725 // preferable because it allows the C2 << Y expression to be hoisted out of a
1726 // loop if Y is invariant and X is not.
1727 if (Shift->hasOneUse() && C1.isZero() && Cmp.isEquality() &&
1728 !Shift->isArithmeticShift() && !isa<Constant>(Shift->getOperand(0))) {
1729 // Compute C2 << Y.
1730 Value *NewShift =
1731 IsShl ? Builder.CreateLShr(And->getOperand(1), Shift->getOperand(1))
1732 : Builder.CreateShl(And->getOperand(1), Shift->getOperand(1));
1733
1734 // Compute X & (C2 << Y).
1735 Value *NewAnd = Builder.CreateAnd(Shift->getOperand(0), NewShift);
1736 return replaceOperand(Cmp, 0, NewAnd);
1737 }
1738
1739 return nullptr;
1740}
1741
1742/// Fold icmp (and X, C2), C1.
1745 const APInt &C1) {
1746 bool isICMP_NE = Cmp.getPredicate() == ICmpInst::ICMP_NE;
1747
1748 // For vectors: icmp ne (and X, 1), 0 --> trunc X to N x i1
1749 // TODO: We canonicalize to the longer form for scalars because we have
1750 // better analysis/folds for icmp, and codegen may be better with icmp.
1751 if (isICMP_NE && Cmp.getType()->isVectorTy() && C1.isZero() &&
1752 match(And->getOperand(1), m_One()))
1753 return new TruncInst(And->getOperand(0), Cmp.getType());
1754
1755 const APInt *C2;
1756 Value *X;
1757 if (!match(And, m_And(m_Value(X), m_APInt(C2))))
1758 return nullptr;
1759
1760 // Don't perform the following transforms if the AND has multiple uses
1761 if (!And->hasOneUse())
1762 return nullptr;
1763
1764 if (Cmp.isEquality() && C1.isZero()) {
1765 // Restrict this fold to single-use 'and' (PR10267).
1766 // Replace (and X, (1 << size(X)-1) != 0) with X s< 0
1767 if (C2->isSignMask()) {
1768 Constant *Zero = Constant::getNullValue(X->getType());
1769 auto NewPred = isICMP_NE ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_SGE;
1770 return new ICmpInst(NewPred, X, Zero);
1771 }
1772
1773 APInt NewC2 = *C2;
1774 KnownBits Know = computeKnownBits(And->getOperand(0), 0, And);
1775 // Set high zeros of C2 to allow matching negated power-of-2.
1776 NewC2 = *C2 | APInt::getHighBitsSet(C2->getBitWidth(),
1777 Know.countMinLeadingZeros());
1778
1779 // Restrict this fold only for single-use 'and' (PR10267).
1780 // ((%x & C) == 0) --> %x u< (-C) iff (-C) is power of two.
1781 if (NewC2.isNegatedPowerOf2()) {
1782 Constant *NegBOC = ConstantInt::get(And->getType(), -NewC2);
1783 auto NewPred = isICMP_NE ? ICmpInst::ICMP_UGE : ICmpInst::ICMP_ULT;
1784 return new ICmpInst(NewPred, X, NegBOC);
1785 }
1786 }
1787
1788 // If the LHS is an 'and' of a truncate and we can widen the and/compare to
1789 // the input width without changing the value produced, eliminate the cast:
1790 //
1791 // icmp (and (trunc W), C2), C1 -> icmp (and W, C2'), C1'
1792 //
1793 // We can do this transformation if the constants do not have their sign bits
1794 // set or if it is an equality comparison. Extending a relational comparison
1795 // when we're checking the sign bit would not work.
1796 Value *W;
1797 if (match(And->getOperand(0), m_OneUse(m_Trunc(m_Value(W)))) &&
1798 (Cmp.isEquality() || (!C1.isNegative() && !C2->isNegative()))) {
1799 // TODO: Is this a good transform for vectors? Wider types may reduce
1800 // throughput. Should this transform be limited (even for scalars) by using
1801 // shouldChangeType()?
1802 if (!Cmp.getType()->isVectorTy()) {
1803 Type *WideType = W->getType();
1804 unsigned WideScalarBits = WideType->getScalarSizeInBits();
1805 Constant *ZextC1 = ConstantInt::get(WideType, C1.zext(WideScalarBits));
1806 Constant *ZextC2 = ConstantInt::get(WideType, C2->zext(WideScalarBits));
1807 Value *NewAnd = Builder.CreateAnd(W, ZextC2, And->getName());
1808 return new ICmpInst(Cmp.getPredicate(), NewAnd, ZextC1);
1809 }
1810 }
1811
1812 if (Instruction *I = foldICmpAndShift(Cmp, And, C1, *C2))
1813 return I;
1814
1815 // (icmp pred (and (or (lshr A, B), A), 1), 0) -->
1816 // (icmp pred (and A, (or (shl 1, B), 1), 0))
1817 //
1818 // iff pred isn't signed
1819 if (!Cmp.isSigned() && C1.isZero() && And->getOperand(0)->hasOneUse() &&
1820 match(And->getOperand(1), m_One())) {
1821 Constant *One = cast<Constant>(And->getOperand(1));
1822 Value *Or = And->getOperand(0);
1823 Value *A, *B, *LShr;
1824 if (match(Or, m_Or(m_Value(LShr), m_Value(A))) &&
1825 match(LShr, m_LShr(m_Specific(A), m_Value(B)))) {
1826 unsigned UsesRemoved = 0;
1827 if (And->hasOneUse())
1828 ++UsesRemoved;
1829 if (Or->hasOneUse())
1830 ++UsesRemoved;
1831 if (LShr->hasOneUse())
1832 ++UsesRemoved;
1833
1834 // Compute A & ((1 << B) | 1)
1835 unsigned RequireUsesRemoved = match(B, m_ImmConstant()) ? 1 : 3;
1836 if (UsesRemoved >= RequireUsesRemoved) {
1837 Value *NewOr =
1838 Builder.CreateOr(Builder.CreateShl(One, B, LShr->getName(),
1839 /*HasNUW=*/true),
1840 One, Or->getName());
1841 Value *NewAnd = Builder.CreateAnd(A, NewOr, And->getName());
1842 return replaceOperand(Cmp, 0, NewAnd);
1843 }
1844 }
1845 }
1846
1847 // (icmp eq (and (bitcast X to int), ExponentMask), ExponentMask) -->
1848 // llvm.is.fpclass(X, fcInf|fcNan)
1849 // (icmp ne (and (bitcast X to int), ExponentMask), ExponentMask) -->
1850 // llvm.is.fpclass(X, ~(fcInf|fcNan))
1851 Value *V;
1852 if (!Cmp.getParent()->getParent()->hasFnAttribute(
1853 Attribute::NoImplicitFloat) &&
1854 Cmp.isEquality() &&
1856 Type *FPType = V->getType()->getScalarType();
1857 if (FPType->isIEEELikeFPTy() && C1 == *C2) {
1858 APInt ExponentMask =
1860 if (C1 == ExponentMask) {
1861 unsigned Mask = FPClassTest::fcNan | FPClassTest::fcInf;
1862 if (isICMP_NE)
1863 Mask = ~Mask & fcAllFlags;
1864 return replaceInstUsesWith(Cmp, Builder.createIsFPClass(V, Mask));
1865 }
1866 }
1867 }
1868
1869 return nullptr;
1870}
1871
1872/// Fold icmp (and X, Y), C.
1875 const APInt &C) {
1876 if (Instruction *I = foldICmpAndConstConst(Cmp, And, C))
1877 return I;
1878
1879 const ICmpInst::Predicate Pred = Cmp.getPredicate();
1880 bool TrueIfNeg;
1881 if (isSignBitCheck(Pred, C, TrueIfNeg)) {
1882 // ((X - 1) & ~X) < 0 --> X == 0
1883 // ((X - 1) & ~X) >= 0 --> X != 0
1884 Value *X;
1885 if (match(And->getOperand(0), m_Add(m_Value(X), m_AllOnes())) &&
1886 match(And->getOperand(1), m_Not(m_Specific(X)))) {
1887 auto NewPred = TrueIfNeg ? CmpInst::ICMP_EQ : CmpInst::ICMP_NE;
1888 return new ICmpInst(NewPred, X, ConstantInt::getNullValue(X->getType()));
1889 }
1890 // (X & -X) < 0 --> X == MinSignedC
1891 // (X & -X) > -1 --> X != MinSignedC
1892 if (match(And, m_c_And(m_Neg(m_Value(X)), m_Deferred(X)))) {
1893 Constant *MinSignedC = ConstantInt::get(
1894 X->getType(),
1895 APInt::getSignedMinValue(X->getType()->getScalarSizeInBits()));
1896 auto NewPred = TrueIfNeg ? CmpInst::ICMP_EQ : CmpInst::ICMP_NE;
1897 return new ICmpInst(NewPred, X, MinSignedC);
1898 }
1899 }
1900
1901 // TODO: These all require that Y is constant too, so refactor with the above.
1902
1903 // Try to optimize things like "A[i] & 42 == 0" to index computations.
1904 Value *X = And->getOperand(0);
1905 Value *Y = And->getOperand(1);
1906 if (auto *C2 = dyn_cast<ConstantInt>(Y))
1907 if (auto *LI = dyn_cast<LoadInst>(X))
1908 if (auto *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0)))
1909 if (auto *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)))
1910 if (Instruction *Res =
1911 foldCmpLoadFromIndexedGlobal(LI, GEP, GV, Cmp, C2))
1912 return Res;
1913
1914 if (!Cmp.isEquality())
1915 return nullptr;
1916
1917 // X & -C == -C -> X > u ~C
1918 // X & -C != -C -> X <= u ~C
1919 // iff C is a power of 2
1920 if (Cmp.getOperand(1) == Y && C.isNegatedPowerOf2()) {
1921 auto NewPred =
1923 return new ICmpInst(NewPred, X, SubOne(cast<Constant>(Cmp.getOperand(1))));
1924 }
1925
1926 // If we are testing the intersection of 2 select-of-nonzero-constants with no
1927 // common bits set, it's the same as checking if exactly one select condition
1928 // is set:
1929 // ((A ? TC : FC) & (B ? TC : FC)) == 0 --> xor A, B
1930 // ((A ? TC : FC) & (B ? TC : FC)) != 0 --> not(xor A, B)
1931 // TODO: Generalize for non-constant values.
1932 // TODO: Handle signed/unsigned predicates.
1933 // TODO: Handle other bitwise logic connectors.
1934 // TODO: Extend to handle a non-zero compare constant.
1935 if (C.isZero() && (Pred == CmpInst::ICMP_EQ || And->hasOneUse())) {
1936 assert(Cmp.isEquality() && "Not expecting non-equality predicates");
1937 Value *A, *B;
1938 const APInt *TC, *FC;
1939 if (match(X, m_Select(m_Value(A), m_APInt(TC), m_APInt(FC))) &&
1940 match(Y,
1941 m_Select(m_Value(B), m_SpecificInt(*TC), m_SpecificInt(*FC))) &&
1942 !TC->isZero() && !FC->isZero() && !TC->intersects(*FC)) {
1943 Value *R = Builder.CreateXor(A, B);
1944 if (Pred == CmpInst::ICMP_NE)
1945 R = Builder.CreateNot(R);
1946 return replaceInstUsesWith(Cmp, R);
1947 }
1948 }
1949
1950 // ((zext i1 X) & Y) == 0 --> !((trunc Y) & X)
1951 // ((zext i1 X) & Y) != 0 --> ((trunc Y) & X)
1952 // ((zext i1 X) & Y) == 1 --> ((trunc Y) & X)
1953 // ((zext i1 X) & Y) != 1 --> !((trunc Y) & X)
1955 X->getType()->isIntOrIntVectorTy(1) && (C.isZero() || C.isOne())) {
1956 Value *TruncY = Builder.CreateTrunc(Y, X->getType());
1957 if (C.isZero() ^ (Pred == CmpInst::ICMP_NE)) {
1958 Value *And = Builder.CreateAnd(TruncY, X);
1960 }
1961 return BinaryOperator::CreateAnd(TruncY, X);
1962 }
1963
1964 // (icmp eq/ne (and (shl -1, X), Y), 0)
1965 // -> (icmp eq/ne (lshr Y, X), 0)
1966 // We could technically handle any C == 0 or (C < 0 && isOdd(C)) but it seems
1967 // highly unlikely the non-zero case will ever show up in code.
1968 if (C.isZero() &&
1970 m_Value(Y))))) {
1971 Value *LShr = Builder.CreateLShr(Y, X);
1972 return new ICmpInst(Pred, LShr, Constant::getNullValue(LShr->getType()));
1973 }
1974
1975 return nullptr;
1976}
1977
1978/// Fold icmp eq/ne (or (xor/sub (X1, X2), xor/sub (X3, X4))), 0.
1980 InstCombiner::BuilderTy &Builder) {
1981 // Are we using xors or subs to bitwise check for a pair or pairs of
1982 // (in)equalities? Convert to a shorter form that has more potential to be
1983 // folded even further.
1984 // ((X1 ^/- X2) || (X3 ^/- X4)) == 0 --> (X1 == X2) && (X3 == X4)
1985 // ((X1 ^/- X2) || (X3 ^/- X4)) != 0 --> (X1 != X2) || (X3 != X4)
1986 // ((X1 ^/- X2) || (X3 ^/- X4) || (X5 ^/- X6)) == 0 -->
1987 // (X1 == X2) && (X3 == X4) && (X5 == X6)
1988 // ((X1 ^/- X2) || (X3 ^/- X4) || (X5 ^/- X6)) != 0 -->
1989 // (X1 != X2) || (X3 != X4) || (X5 != X6)
1991 SmallVector<Value *, 16> WorkList(1, Or);
1992
1993 while (!WorkList.empty()) {
1994 auto MatchOrOperatorArgument = [&](Value *OrOperatorArgument) {
1995 Value *Lhs, *Rhs;
1996
1997 if (match(OrOperatorArgument,
1998 m_OneUse(m_Xor(m_Value(Lhs), m_Value(Rhs))))) {
1999 CmpValues.emplace_back(Lhs, Rhs);
2000 return;
2001 }
2002
2003 if (match(OrOperatorArgument,
2004 m_OneUse(m_Sub(m_Value(Lhs), m_Value(Rhs))))) {
2005 CmpValues.emplace_back(Lhs, Rhs);
2006 return;
2007 }
2008
2009 WorkList.push_back(OrOperatorArgument);
2010 };
2011
2012 Value *CurrentValue = WorkList.pop_back_val();
2013 Value *OrOperatorLhs, *OrOperatorRhs;
2014
2015 if (!match(CurrentValue,
2016 m_Or(m_Value(OrOperatorLhs), m_Value(OrOperatorRhs)))) {
2017 return nullptr;
2018 }
2019
2020 MatchOrOperatorArgument(OrOperatorRhs);
2021 MatchOrOperatorArgument(OrOperatorLhs);
2022 }
2023
2024 ICmpInst::Predicate Pred = Cmp.getPredicate();
2025 auto BOpc = Pred == CmpInst::ICMP_EQ ? Instruction::And : Instruction::Or;
2026 Value *LhsCmp = Builder.CreateICmp(Pred, CmpValues.rbegin()->first,
2027 CmpValues.rbegin()->second);
2028
2029 for (auto It = CmpValues.rbegin() + 1; It != CmpValues.rend(); ++It) {
2030 Value *RhsCmp = Builder.CreateICmp(Pred, It->first, It->second);
2031 LhsCmp = Builder.CreateBinOp(BOpc, LhsCmp, RhsCmp);
2032 }
2033
2034 return LhsCmp;
2035}
2036
2037/// Fold icmp (or X, Y), C.
2040 const APInt &C) {
2041 ICmpInst::Predicate Pred = Cmp.getPredicate();
2042 if (C.isOne()) {
2043 // icmp slt signum(V) 1 --> icmp slt V, 1
2044 Value *V = nullptr;
2045 if (Pred == ICmpInst::ICMP_SLT && match(Or, m_Signum(m_Value(V))))
2046 return new ICmpInst(ICmpInst::ICMP_SLT, V,
2047 ConstantInt::get(V->getType(), 1));
2048 }
2049
2050 Value *OrOp0 = Or->getOperand(0), *OrOp1 = Or->getOperand(1);
2051
2052 // (icmp eq/ne (or disjoint x, C0), C1)
2053 // -> (icmp eq/ne x, C0^C1)
2054 if (Cmp.isEquality() && match(OrOp1, m_ImmConstant()) &&
2055 cast<PossiblyDisjointInst>(Or)->isDisjoint()) {
2056 Value *NewC =
2057 Builder.CreateXor(OrOp1, ConstantInt::get(OrOp1->getType(), C));
2058 return new ICmpInst(Pred, OrOp0, NewC);
2059 }
2060
2061 const APInt *MaskC;
2062 if (match(OrOp1, m_APInt(MaskC)) && Cmp.isEquality()) {
2063 if (*MaskC == C && (C + 1).isPowerOf2()) {
2064 // X | C == C --> X <=u C
2065 // X | C != C --> X >u C
2066 // iff C+1 is a power of 2 (C is a bitmask of the low bits)
2068 return new ICmpInst(Pred, OrOp0, OrOp1);
2069 }
2070
2071 // More general: canonicalize 'equality with set bits mask' to
2072 // 'equality with clear bits mask'.
2073 // (X | MaskC) == C --> (X & ~MaskC) == C ^ MaskC
2074 // (X | MaskC) != C --> (X & ~MaskC) != C ^ MaskC
2075 if (Or->hasOneUse()) {
2076 Value *And = Builder.CreateAnd(OrOp0, ~(*MaskC));
2077 Constant *NewC = ConstantInt::get(Or->getType(), C ^ (*MaskC));
2078 return new ICmpInst(Pred, And, NewC);
2079 }
2080 }
2081
2082 // (X | (X-1)) s< 0 --> X s< 1
2083 // (X | (X-1)) s> -1 --> X s> 0
2084 Value *X;
2085 bool TrueIfSigned;
2086 if (isSignBitCheck(Pred, C, TrueIfSigned) &&
2088 auto NewPred = TrueIfSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_SGT;
2089 Constant *NewC = ConstantInt::get(X->getType(), TrueIfSigned ? 1 : 0);
2090 return new ICmpInst(NewPred, X, NewC);
2091 }
2092
2093 const APInt *OrC;
2094 // icmp(X | OrC, C) --> icmp(X, 0)
2095 if (C.isNonNegative() && match(Or, m_Or(m_Value(X), m_APInt(OrC)))) {
2096 switch (Pred) {
2097 // X | OrC s< C --> X s< 0 iff OrC s>= C s>= 0
2098 case ICmpInst::ICMP_SLT:
2099 // X | OrC s>= C --> X s>= 0 iff OrC s>= C s>= 0
2100 case ICmpInst::ICMP_SGE:
2101 if (OrC->sge(C))
2102 return new ICmpInst(Pred, X, ConstantInt::getNullValue(X->getType()));
2103 break;
2104 // X | OrC s<= C --> X s< 0 iff OrC s> C s>= 0
2105 case ICmpInst::ICMP_SLE:
2106 // X | OrC s> C --> X s>= 0 iff OrC s> C s>= 0
2107 case ICmpInst::ICMP_SGT:
2108 if (OrC->sgt(C))
2110 ConstantInt::getNullValue(X->getType()));
2111 break;
2112 default:
2113 break;
2114 }
2115 }
2116
2117 if (!Cmp.isEquality() || !C.isZero() || !Or->hasOneUse())
2118 return nullptr;
2119
2120 Value *P, *Q;
2122 // Simplify icmp eq (or (ptrtoint P), (ptrtoint Q)), 0
2123 // -> and (icmp eq P, null), (icmp eq Q, null).
2124 Value *CmpP =
2125 Builder.CreateICmp(Pred, P, ConstantInt::getNullValue(P->getType()));
2126 Value *CmpQ =
2128 auto BOpc = Pred == CmpInst::ICMP_EQ ? Instruction::And : Instruction::Or;
2129 return BinaryOperator::Create(BOpc, CmpP, CmpQ);
2130 }
2131
2132 if (Value *V = foldICmpOrXorSubChain(Cmp, Or, Builder))
2133 return replaceInstUsesWith(Cmp, V);
2134
2135 return nullptr;
2136}
2137
2138/// Fold icmp (mul X, Y), C.
2141 const APInt &C) {
2142 ICmpInst::Predicate Pred = Cmp.getPredicate();
2143 Type *MulTy = Mul->getType();
2144 Value *X = Mul->getOperand(0);
2145
2146 // If there's no overflow:
2147 // X * X == 0 --> X == 0
2148 // X * X != 0 --> X != 0
2149 if (Cmp.isEquality() && C.isZero() && X == Mul->getOperand(1) &&
2150 (Mul->hasNoUnsignedWrap() || Mul->hasNoSignedWrap()))
2151 return new ICmpInst(Pred, X, ConstantInt::getNullValue(MulTy));
2152
2153 const APInt *MulC;
2154 if (!match(Mul->getOperand(1), m_APInt(MulC)))
2155 return nullptr;
2156
2157 // If this is a test of the sign bit and the multiply is sign-preserving with
2158 // a constant operand, use the multiply LHS operand instead:
2159 // (X * +MulC) < 0 --> X < 0
2160 // (X * -MulC) < 0 --> X > 0
2161 if (isSignTest(Pred, C) && Mul->hasNoSignedWrap()) {
2162 if (MulC->isNegative())
2163 Pred = ICmpInst::getSwappedPredicate(Pred);
2164 return new ICmpInst(Pred, X, ConstantInt::getNullValue(MulTy));
2165 }
2166
2167 if (MulC->isZero())
2168 return nullptr;
2169
2170 // If the multiply does not wrap or the constant is odd, try to divide the
2171 // compare constant by the multiplication factor.
2172 if (Cmp.isEquality()) {
2173 // (mul nsw X, MulC) eq/ne C --> X eq/ne C /s MulC
2174 if (Mul->hasNoSignedWrap() && C.srem(*MulC).isZero()) {
2175 Constant *NewC = ConstantInt::get(MulTy, C.sdiv(*MulC));
2176 return new ICmpInst(Pred, X, NewC);
2177 }
2178
2179 // C % MulC == 0 is weaker than we could use if MulC is odd because it
2180 // correct to transform if MulC * N == C including overflow. I.e with i8
2181 // (icmp eq (mul X, 5), 101) -> (icmp eq X, 225) but since 101 % 5 != 0, we
2182 // miss that case.
2183 if (C.urem(*MulC).isZero()) {
2184 // (mul nuw X, MulC) eq/ne C --> X eq/ne C /u MulC
2185 // (mul X, OddC) eq/ne N * C --> X eq/ne N
2186 if ((*MulC & 1).isOne() || Mul->hasNoUnsignedWrap()) {
2187 Constant *NewC = ConstantInt::get(MulTy, C.udiv(*MulC));
2188 return new ICmpInst(Pred, X, NewC);
2189 }
2190 }
2191 }
2192
2193 // With a matching no-overflow guarantee, fold the constants:
2194 // (X * MulC) < C --> X < (C / MulC)
2195 // (X * MulC) > C --> X > (C / MulC)
2196 // TODO: Assert that Pred is not equal to SGE, SLE, UGE, ULE?
2197 Constant *NewC = nullptr;
2198 if (Mul->hasNoSignedWrap() && ICmpInst::isSigned(Pred)) {
2199 // MININT / -1 --> overflow.
2200 if (C.isMinSignedValue() && MulC->isAllOnes())
2201 return nullptr;
2202 if (MulC->isNegative())
2203 Pred = ICmpInst::getSwappedPredicate(Pred);
2204
2205 if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE) {
2206 NewC = ConstantInt::get(
2208 } else {
2209 assert((Pred == ICmpInst::ICMP_SLE || Pred == ICmpInst::ICMP_SGT) &&
2210 "Unexpected predicate");
2211 NewC = ConstantInt::get(
2213 }
2214 } else if (Mul->hasNoUnsignedWrap() && ICmpInst::isUnsigned(Pred)) {
2215 if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_UGE) {
2216 NewC = ConstantInt::get(
2218 } else {
2219 assert((Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_UGT) &&
2220 "Unexpected predicate");
2221 NewC = ConstantInt::get(
2223 }
2224 }
2225
2226 return NewC ? new ICmpInst(Pred, X, NewC) : nullptr;
2227}
2228
2229/// Fold icmp (shl 1, Y), C.
2231 const APInt &C) {
2232 Value *Y;
2233 if (!match(Shl, m_Shl(m_One(), m_Value(Y))))
2234 return nullptr;
2235
2236 Type *ShiftType = Shl->getType();
2237 unsigned TypeBits = C.getBitWidth();
2238 bool CIsPowerOf2 = C.isPowerOf2();
2239 ICmpInst::Predicate Pred = Cmp.getPredicate();
2240 if (Cmp.isUnsigned()) {
2241 // (1 << Y) pred C -> Y pred Log2(C)
2242 if (!CIsPowerOf2) {
2243 // (1 << Y) < 30 -> Y <= 4
2244 // (1 << Y) <= 30 -> Y <= 4
2245 // (1 << Y) >= 30 -> Y > 4
2246 // (1 << Y) > 30 -> Y > 4
2247 if (Pred == ICmpInst::ICMP_ULT)
2248 Pred = ICmpInst::ICMP_ULE;
2249 else if (Pred == ICmpInst::ICMP_UGE)
2250 Pred = ICmpInst::ICMP_UGT;
2251 }
2252
2253 unsigned CLog2 = C.logBase2();
2254 return new ICmpInst(Pred, Y, ConstantInt::get(ShiftType, CLog2));
2255 } else if (Cmp.isSigned()) {
2256 Constant *BitWidthMinusOne = ConstantInt::get(ShiftType, TypeBits - 1);
2257 // (1 << Y) > 0 -> Y != 31
2258 // (1 << Y) > C -> Y != 31 if C is negative.
2259 if (Pred == ICmpInst::ICMP_SGT && C.sle(0))
2260 return new ICmpInst(ICmpInst::ICMP_NE, Y, BitWidthMinusOne);
2261
2262 // (1 << Y) < 0 -> Y == 31
2263 // (1 << Y) < 1 -> Y == 31
2264 // (1 << Y) < C -> Y == 31 if C is negative and not signed min.
2265 // Exclude signed min by subtracting 1 and lower the upper bound to 0.
2266 if (Pred == ICmpInst::ICMP_SLT && (C-1).sle(0))
2267 return new ICmpInst(ICmpInst::ICMP_EQ, Y, BitWidthMinusOne);
2268 }
2269
2270 return nullptr;
2271}
2272
2273/// Fold icmp (shl X, Y), C.
2275 BinaryOperator *Shl,
2276 const APInt &C) {
2277 const APInt *ShiftVal;
2278 if (Cmp.isEquality() && match(Shl->getOperand(0), m_APInt(ShiftVal)))
2279 return foldICmpShlConstConst(Cmp, Shl->getOperand(1), C, *ShiftVal);
2280
2281 ICmpInst::Predicate Pred = Cmp.getPredicate();
2282 // (icmp pred (shl nuw&nsw X, Y), Csle0)
2283 // -> (icmp pred X, Csle0)
2284 //
2285 // The idea is the nuw/nsw essentially freeze the sign bit for the shift op
2286 // so X's must be what is used.
2287 if (C.sle(0) && Shl->hasNoUnsignedWrap() && Shl->hasNoSignedWrap())
2288 return new ICmpInst(Pred, Shl->getOperand(0), Cmp.getOperand(1));
2289
2290 // (icmp eq/ne (shl nuw|nsw X, Y), 0)
2291 // -> (icmp eq/ne X, 0)
2292 if (ICmpInst::isEquality(Pred) && C.isZero() &&
2293 (Shl->hasNoUnsignedWrap() || Shl->hasNoSignedWrap()))
2294 return new ICmpInst(Pred, Shl->getOperand(0), Cmp.getOperand(1));
2295
2296 // (icmp slt (shl nsw X, Y), 0/1)
2297 // -> (icmp slt X, 0/1)
2298 // (icmp sgt (shl nsw X, Y), 0/-1)
2299 // -> (icmp sgt X, 0/-1)
2300 //
2301 // NB: sge/sle with a constant will canonicalize to sgt/slt.
2302 if (Shl->hasNoSignedWrap() &&
2303 (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLT))
2304 if (C.isZero() || (Pred == ICmpInst::ICMP_SGT ? C.isAllOnes() : C.isOne()))
2305 return new ICmpInst(Pred, Shl->getOperand(0), Cmp.getOperand(1));
2306
2307 const APInt *ShiftAmt;
2308 if (!match(Shl->getOperand(1), m_APInt(ShiftAmt)))
2309 return foldICmpShlOne(Cmp, Shl, C);
2310
2311 // Check that the shift amount is in range. If not, don't perform undefined
2312 // shifts. When the shift is visited, it will be simplified.
2313 unsigned TypeBits = C.getBitWidth();
2314 if (ShiftAmt->uge(TypeBits))
2315 return nullptr;
2316
2317 Value *X = Shl->getOperand(0);
2318 Type *ShType = Shl->getType();
2319
2320 // NSW guarantees that we are only shifting out sign bits from the high bits,
2321 // so we can ASHR the compare constant without needing a mask and eliminate
2322 // the shift.
2323 if (Shl->hasNoSignedWrap()) {
2324 if (Pred == ICmpInst::ICMP_SGT) {
2325 // icmp Pred (shl nsw X, ShiftAmt), C --> icmp Pred X, (C >>s ShiftAmt)
2326 APInt ShiftedC = C.ashr(*ShiftAmt);
2327 return new ICmpInst(Pred, X, ConstantInt::get(ShType, ShiftedC));
2328 }
2329 if ((Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE) &&
2330 C.ashr(*ShiftAmt).shl(*ShiftAmt) == C) {
2331 APInt ShiftedC = C.ashr(*ShiftAmt);
2332 return new ICmpInst(Pred, X, ConstantInt::get(ShType, ShiftedC));
2333 }
2334 if (Pred == ICmpInst::ICMP_SLT) {
2335 // SLE is the same as above, but SLE is canonicalized to SLT, so convert:
2336 // (X << S) <=s C is equiv to X <=s (C >> S) for all C
2337 // (X << S) <s (C + 1) is equiv to X <s (C >> S) + 1 if C <s SMAX
2338 // (X << S) <s C is equiv to X <s ((C - 1) >> S) + 1 if C >s SMIN
2339 assert(!C.isMinSignedValue() && "Unexpected icmp slt");
2340 APInt ShiftedC = (C - 1).ashr(*ShiftAmt) + 1;
2341 return new ICmpInst(Pred, X, ConstantInt::get(ShType, ShiftedC));
2342 }
2343 }
2344
2345 // NUW guarantees that we are only shifting out zero bits from the high bits,
2346 // so we can LSHR the compare constant without needing a mask and eliminate
2347 // the shift.
2348 if (Shl->hasNoUnsignedWrap()) {
2349 if (Pred == ICmpInst::ICMP_UGT) {
2350 // icmp Pred (shl nuw X, ShiftAmt), C --> icmp Pred X, (C >>u ShiftAmt)
2351 APInt ShiftedC = C.lshr(*ShiftAmt);
2352 return new ICmpInst(Pred, X, ConstantInt::get(ShType, ShiftedC));
2353 }
2354 if ((Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE) &&
2355 C.lshr(*ShiftAmt).shl(*ShiftAmt) == C) {
2356 APInt ShiftedC = C.lshr(*ShiftAmt);
2357 return new ICmpInst(Pred, X, ConstantInt::get(ShType, ShiftedC));
2358 }
2359 if (Pred == ICmpInst::ICMP_ULT) {
2360 // ULE is the same as above, but ULE is canonicalized to ULT, so convert:
2361 // (X << S) <=u C is equiv to X <=u (C >> S) for all C
2362 // (X << S) <u (C + 1) is equiv to X <u (C >> S) + 1 if C <u ~0u
2363 // (X << S) <u C is equiv to X <u ((C - 1) >> S) + 1 if C >u 0
2364 assert(C.ugt(0) && "ult 0 should have been eliminated");
2365 APInt ShiftedC = (C - 1).lshr(*ShiftAmt) + 1;
2366 return new ICmpInst(Pred, X, ConstantInt::get(ShType, ShiftedC));
2367 }
2368 }
2369
2370 if (Cmp.isEquality() && Shl->hasOneUse()) {
2371 // Strength-reduce the shift into an 'and'.
2372 Constant *Mask = ConstantInt::get(
2373 ShType,
2374 APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt->getZExtValue()));
2375 Value *And = Builder.CreateAnd(X, Mask, Shl->getName() + ".mask");
2376 Constant *LShrC = ConstantInt::get(ShType, C.lshr(*ShiftAmt));
2377 return new ICmpInst(Pred, And, LShrC);
2378 }
2379
2380 // Otherwise, if this is a comparison of the sign bit, simplify to and/test.
2381 bool TrueIfSigned = false;
2382 if (Shl->hasOneUse() && isSignBitCheck(Pred, C, TrueIfSigned)) {
2383 // (X << 31) <s 0 --> (X & 1) != 0
2384 Constant *Mask = ConstantInt::get(
2385 ShType,
2386 APInt::getOneBitSet(TypeBits, TypeBits - ShiftAmt->getZExtValue() - 1));
2387 Value *And = Builder.CreateAnd(X, Mask, Shl->getName() + ".mask");
2388 return new ICmpInst(TrueIfSigned ? ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ,
2389 And, Constant::getNullValue(ShType));
2390 }
2391
2392 // Simplify 'shl' inequality test into 'and' equality test.
2393 if (Cmp.isUnsigned() && Shl->hasOneUse()) {
2394 // (X l<< C2) u<=/u> C1 iff C1+1 is power of two -> X & (~C1 l>> C2) ==/!= 0
2395 if ((C + 1).isPowerOf2() &&
2396 (Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_UGT)) {
2397 Value *And = Builder.CreateAnd(X, (~C).lshr(ShiftAmt->getZExtValue()));
2398 return new ICmpInst(Pred == ICmpInst::ICMP_ULE ? ICmpInst::ICMP_EQ
2400 And, Constant::getNullValue(ShType));
2401 }
2402 // (X l<< C2) u</u>= C1 iff C1 is power of two -> X & (-C1 l>> C2) ==/!= 0
2403 if (C.isPowerOf2() &&
2404 (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_UGE)) {
2405 Value *And =
2406 Builder.CreateAnd(X, (~(C - 1)).lshr(ShiftAmt->getZExtValue()));
2407 return new ICmpInst(Pred == ICmpInst::ICMP_ULT ? ICmpInst::ICMP_EQ
2409 And, Constant::getNullValue(ShType));
2410 }
2411 }
2412
2413 // Transform (icmp pred iM (shl iM %v, N), C)
2414 // -> (icmp pred i(M-N) (trunc %v iM to i(M-N)), (trunc (C>>N))
2415 // Transform the shl to a trunc if (trunc (C>>N)) has no loss and M-N.
2416 // This enables us to get rid of the shift in favor of a trunc that may be
2417 // free on the target. It has the additional benefit of comparing to a
2418 // smaller constant that may be more target-friendly.
2419 unsigned Amt = ShiftAmt->getLimitedValue(TypeBits - 1);
2420 if (Shl->hasOneUse() && Amt != 0 &&
2421 shouldChangeType(ShType->getScalarSizeInBits(), TypeBits - Amt)) {
2422 ICmpInst::Predicate CmpPred = Pred;
2423 APInt RHSC = C;
2424
2425 if (RHSC.countr_zero() < Amt && ICmpInst::isStrictPredicate(CmpPred)) {
2426 // Try the flipped strictness predicate.
2427 // e.g.:
2428 // icmp ult i64 (shl X, 32), 8589934593 ->
2429 // icmp ule i64 (shl X, 32), 8589934592 ->
2430 // icmp ule i32 (trunc X, i32), 2 ->
2431 // icmp ult i32 (trunc X, i32), 3
2432 if (auto FlippedStrictness =
2434 Pred, ConstantInt::get(ShType->getContext(), C))) {
2435 CmpPred = FlippedStrictness->first;
2436 RHSC = cast<ConstantInt>(FlippedStrictness->second)->getValue();
2437 }
2438 }
2439
2440 if (RHSC.countr_zero() >= Amt) {
2441 Type *TruncTy = ShType->getWithNewBitWidth(TypeBits - Amt);
2442 Constant *NewC =
2443 ConstantInt::get(TruncTy, RHSC.ashr(*ShiftAmt).trunc(TypeBits - Amt));
2444 return new ICmpInst(CmpPred,
2445 Builder.CreateTrunc(X, TruncTy, "", /*IsNUW=*/false,
2446 Shl->hasNoSignedWrap()),
2447 NewC);
2448 }
2449 }
2450
2451 return nullptr;
2452}
2453
2454/// Fold icmp ({al}shr X, Y), C.
2456 BinaryOperator *Shr,
2457 const APInt &C) {
2458 // An exact shr only shifts out zero bits, so:
2459 // icmp eq/ne (shr X, Y), 0 --> icmp eq/ne X, 0
2460 Value *X = Shr->getOperand(0);
2461 CmpInst::Predicate Pred = Cmp.getPredicate();
2462 if (Cmp.isEquality() && Shr->isExact() && C.isZero())
2463 return new ICmpInst(Pred, X, Cmp.getOperand(1));
2464
2465 bool IsAShr = Shr->getOpcode() == Instruction::AShr;
2466 const APInt *ShiftValC;
2467 if (match(X, m_APInt(ShiftValC))) {
2468 if (Cmp.isEquality())
2469 return foldICmpShrConstConst(Cmp, Shr->getOperand(1), C, *ShiftValC);
2470
2471 // (ShiftValC >> Y) >s -1 --> Y != 0 with ShiftValC < 0
2472 // (ShiftValC >> Y) <s 0 --> Y == 0 with ShiftValC < 0
2473 bool TrueIfSigned;
2474 if (!IsAShr && ShiftValC->isNegative() &&
2475 isSignBitCheck(Pred, C, TrueIfSigned))
2476 return new ICmpInst(TrueIfSigned ? CmpInst::ICMP_EQ : CmpInst::ICMP_NE,
2477 Shr->getOperand(1),
2478 ConstantInt::getNullValue(X->getType()));
2479
2480 // If the shifted constant is a power-of-2, test the shift amount directly:
2481 // (ShiftValC >> Y) >u C --> X <u (LZ(C) - LZ(ShiftValC))
2482 // (ShiftValC >> Y) <u C --> X >=u (LZ(C-1) - LZ(ShiftValC))
2483 if (!IsAShr && ShiftValC->isPowerOf2() &&
2484 (Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_ULT)) {
2485 bool IsUGT = Pred == CmpInst::ICMP_UGT;
2486 assert(ShiftValC->uge(C) && "Expected simplify of compare");
2487 assert((IsUGT || !C.isZero()) && "Expected X u< 0 to simplify");
2488
2489 unsigned CmpLZ = IsUGT ? C.countl_zero() : (C - 1).countl_zero();
2490 unsigned ShiftLZ = ShiftValC->countl_zero();
2491 Constant *NewC = ConstantInt::get(Shr->getType(), CmpLZ - ShiftLZ);
2492 auto NewPred = IsUGT ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
2493 return new ICmpInst(NewPred, Shr->getOperand(1), NewC);
2494 }
2495 }
2496
2497 const APInt *ShiftAmtC;
2498 if (!match(Shr->getOperand(1), m_APInt(ShiftAmtC)))
2499 return nullptr;
2500
2501 // Check that the shift amount is in range. If not, don't perform undefined
2502 // shifts. When the shift is visited it will be simplified.
2503 unsigned TypeBits = C.getBitWidth();
2504 unsigned ShAmtVal = ShiftAmtC->getLimitedValue(TypeBits);
2505 if (ShAmtVal >= TypeBits || ShAmtVal == 0)
2506 return nullptr;
2507
2508 bool IsExact = Shr->isExact();
2509 Type *ShrTy = Shr->getType();
2510 // TODO: If we could guarantee that InstSimplify would handle all of the
2511 // constant-value-based preconditions in the folds below, then we could assert
2512 // those conditions rather than checking them. This is difficult because of
2513 // undef/poison (PR34838).
2514 if (IsAShr && Shr->hasOneUse()) {
2515 if (IsExact && (Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_ULT) &&
2516 (C - 1).isPowerOf2() && C.countLeadingZeros() > ShAmtVal) {
2517 // When C - 1 is a power of two and the transform can be legally
2518 // performed, prefer this form so the produced constant is close to a
2519 // power of two.
2520 // icmp slt/ult (ashr exact X, ShAmtC), C
2521 // --> icmp slt/ult X, (C - 1) << ShAmtC) + 1
2522 APInt ShiftedC = (C - 1).shl(ShAmtVal) + 1;
2523 return new ICmpInst(Pred, X, ConstantInt::get(ShrTy, ShiftedC));
2524 }
2525 if (IsExact || Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_ULT) {
2526 // When ShAmtC can be shifted losslessly:
2527 // icmp PRED (ashr exact X, ShAmtC), C --> icmp PRED X, (C << ShAmtC)
2528 // icmp slt/ult (ashr X, ShAmtC), C --> icmp slt/ult X, (C << ShAmtC)
2529 APInt ShiftedC = C.shl(ShAmtVal);
2530 if (ShiftedC.ashr(ShAmtVal) == C)
2531 return new ICmpInst(Pred, X, ConstantInt::get(ShrTy, ShiftedC));
2532 }
2533 if (Pred == CmpInst::ICMP_SGT) {
2534 // icmp sgt (ashr X, ShAmtC), C --> icmp sgt X, ((C + 1) << ShAmtC) - 1
2535 APInt ShiftedC = (C + 1).shl(ShAmtVal) - 1;
2536 if (!C.isMaxSignedValue() && !(C + 1).shl(ShAmtVal).isMinSignedValue() &&
2537 (ShiftedC + 1).ashr(ShAmtVal) == (C + 1))
2538 return new ICmpInst(Pred, X, ConstantInt::get(ShrTy, ShiftedC));
2539 }
2540 if (Pred == CmpInst::ICMP_UGT) {
2541 // icmp ugt (ashr X, ShAmtC), C --> icmp ugt X, ((C + 1) << ShAmtC) - 1
2542 // 'C + 1 << ShAmtC' can overflow as a signed number, so the 2nd
2543 // clause accounts for that pattern.
2544 APInt ShiftedC = (C + 1).shl(ShAmtVal) - 1;
2545 if ((ShiftedC + 1).ashr(ShAmtVal) == (C + 1) ||
2546 (C + 1).shl(ShAmtVal).isMinSignedValue())
2547 return new ICmpInst(Pred, X, ConstantInt::get(ShrTy, ShiftedC));
2548 }
2549
2550 // If the compare constant has significant bits above the lowest sign-bit,
2551 // then convert an unsigned cmp to a test of the sign-bit:
2552 // (ashr X, ShiftC) u> C --> X s< 0
2553 // (ashr X, ShiftC) u< C --> X s> -1
2554 if (C.getBitWidth() > 2 && C.getNumSignBits() <= ShAmtVal) {
2555 if (Pred == CmpInst::ICMP_UGT) {
2556 return new ICmpInst(CmpInst::ICMP_SLT, X,
2558 }
2559 if (Pred == CmpInst::ICMP_ULT) {
2560 return new ICmpInst(CmpInst::ICMP_SGT, X,
2562 }
2563 }
2564 } else if (!IsAShr) {
2565 if (Pred == CmpInst::ICMP_ULT || (Pred == CmpInst::ICMP_UGT && IsExact)) {
2566 // icmp ult (lshr X, ShAmtC), C --> icmp ult X, (C << ShAmtC)
2567 // icmp ugt (lshr exact X, ShAmtC), C --> icmp ugt X, (C << ShAmtC)
2568 APInt ShiftedC = C.shl(ShAmtVal);
2569 if (ShiftedC.lshr(ShAmtVal) == C)
2570 return new ICmpInst(Pred, X, ConstantInt::get(ShrTy, ShiftedC));
2571 }
2572 if (Pred == CmpInst::ICMP_UGT) {
2573 // icmp ugt (lshr X, ShAmtC), C --> icmp ugt X, ((C + 1) << ShAmtC) - 1
2574 APInt ShiftedC = (C + 1).shl(ShAmtVal) - 1;
2575 if ((ShiftedC + 1).lshr(ShAmtVal) == (C + 1))
2576 return new ICmpInst(Pred, X, ConstantInt::get(ShrTy, ShiftedC));
2577 }
2578 }
2579
2580 if (!Cmp.isEquality())
2581 return nullptr;
2582
2583 // Handle equality comparisons of shift-by-constant.
2584
2585 // If the comparison constant changes with the shift, the comparison cannot
2586 // succeed (bits of the comparison constant cannot match the shifted value).
2587 // This should be known by InstSimplify and already be folded to true/false.
2588 assert(((IsAShr && C.shl(ShAmtVal).ashr(ShAmtVal) == C) ||
2589 (!IsAShr && C.shl(ShAmtVal).lshr(ShAmtVal) == C)) &&
2590 "Expected icmp+shr simplify did not occur.");
2591
2592 // If the bits shifted out are known zero, compare the unshifted value:
2593 // (X & 4) >> 1 == 2 --> (X & 4) == 4.
2594 if (Shr->isExact())
2595 return new ICmpInst(Pred, X, ConstantInt::get(ShrTy, C << ShAmtVal));
2596
2597 if (C.isZero()) {
2598 // == 0 is u< 1.
2599 if (Pred == CmpInst::ICMP_EQ)
2600 return new ICmpInst(CmpInst::ICMP_ULT, X,
2601 ConstantInt::get(ShrTy, (C + 1).shl(ShAmtVal)));
2602 else
2603 return new ICmpInst(CmpInst::ICMP_UGT, X,
2604 ConstantInt::get(ShrTy, (C + 1).shl(ShAmtVal) - 1));
2605 }
2606
2607 if (Shr->hasOneUse()) {
2608 // Canonicalize the shift into an 'and':
2609 // icmp eq/ne (shr X, ShAmt), C --> icmp eq/ne (and X, HiMask), (C << ShAmt)
2610 APInt Val(APInt::getHighBitsSet(TypeBits, TypeBits - ShAmtVal));
2611 Constant *Mask = ConstantInt::get(ShrTy, Val);
2612 Value *And = Builder.CreateAnd(X, Mask, Shr->getName() + ".mask");
2613 return new ICmpInst(Pred, And, ConstantInt::get(ShrTy, C << ShAmtVal));
2614 }
2615
2616 return nullptr;
2617}
2618
2620 BinaryOperator *SRem,
2621 const APInt &C) {
2622 // Match an 'is positive' or 'is negative' comparison of remainder by a
2623 // constant power-of-2 value:
2624 // (X % pow2C) sgt/slt 0
2625 const ICmpInst::Predicate Pred = Cmp.getPredicate();
2626 if (Pred != ICmpInst::ICMP_SGT && Pred != ICmpInst::ICMP_SLT &&
2627 Pred != ICmpInst::ICMP_EQ && Pred != ICmpInst::ICMP_NE)
2628 return nullptr;
2629
2630 // TODO: The one-use check is standard because we do not typically want to
2631 // create longer instruction sequences, but this might be a special-case
2632 // because srem is not good for analysis or codegen.
2633 if (!SRem->hasOneUse())
2634 return nullptr;
2635
2636 const APInt *DivisorC;
2637 if (!match(SRem->getOperand(1), m_Power2(DivisorC)))
2638 return nullptr;
2639
2640 // For cmp_sgt/cmp_slt only zero valued C is handled.
2641 // For cmp_eq/cmp_ne only positive valued C is handled.
2642 if (((Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLT) &&
2643 !C.isZero()) ||
2644 ((Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE) &&
2645 !C.isStrictlyPositive()))
2646 return nullptr;
2647
2648 // Mask off the sign bit and the modulo bits (low-bits).
2649 Type *Ty = SRem->getType();
2651 Constant *MaskC = ConstantInt::get(Ty, SignMask | (*DivisorC - 1));
2652 Value *And = Builder.CreateAnd(SRem->getOperand(0), MaskC);
2653
2654 if (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE)
2655 return new ICmpInst(Pred, And, ConstantInt::get(Ty, C));
2656
2657 // For 'is positive?' check that the sign-bit is clear and at least 1 masked
2658 // bit is set. Example:
2659 // (i8 X % 32) s> 0 --> (X & 159) s> 0
2660 if (Pred == ICmpInst::ICMP_SGT)
2662
2663 // For 'is negative?' check that the sign-bit is set and at least 1 masked
2664 // bit is set. Example:
2665 // (i16 X % 4) s< 0 --> (X & 32771) u> 32768
2666 return new ICmpInst(ICmpInst::ICMP_UGT, And, ConstantInt::get(Ty, SignMask));
2667}
2668
2669/// Fold icmp (udiv X, Y), C.
2671 BinaryOperator *UDiv,
2672 const APInt &C) {
2673 ICmpInst::Predicate Pred = Cmp.getPredicate();
2674 Value *X = UDiv->getOperand(0);
2675 Value *Y = UDiv->getOperand(1);
2676 Type *Ty = UDiv->getType();
2677
2678 const APInt *C2;
2679 if (!match(X, m_APInt(C2)))
2680 return nullptr;
2681
2682 assert(*C2 != 0 && "udiv 0, X should have been simplified already.");
2683
2684 // (icmp ugt (udiv C2, Y), C) -> (icmp ule Y, C2/(C+1))
2685 if (Pred == ICmpInst::ICMP_UGT) {
2686 assert(!C.isMaxValue() &&
2687 "icmp ugt X, UINT_MAX should have been simplified already.");
2688 return new ICmpInst(ICmpInst::ICMP_ULE, Y,
2689 ConstantInt::get(Ty, C2->udiv(C + 1)));
2690 }
2691
2692 // (icmp ult (udiv C2, Y), C) -> (icmp ugt Y, C2/C)
2693 if (Pred == ICmpInst::ICMP_ULT) {
2694 assert(C != 0 && "icmp ult X, 0 should have been simplified already.");
2695 return new ICmpInst(ICmpInst::ICMP_UGT, Y,
2696 ConstantInt::get(Ty, C2->udiv(C)));
2697 }
2698
2699 return nullptr;
2700}
2701
2702/// Fold icmp ({su}div X, Y), C.
2704 BinaryOperator *Div,
2705 const APInt &C) {
2706 ICmpInst::Predicate Pred = Cmp.getPredicate();
2707 Value *X = Div->getOperand(0);
2708 Value *Y = Div->getOperand(1);
2709 Type *Ty = Div->getType();
2710 bool DivIsSigned = Div->getOpcode() == Instruction::SDiv;
2711
2712 // If unsigned division and the compare constant is bigger than
2713 // UMAX/2 (negative), there's only one pair of values that satisfies an
2714 // equality check, so eliminate the division:
2715 // (X u/ Y) == C --> (X == C) && (Y == 1)
2716 // (X u/ Y) != C --> (X != C) || (Y != 1)
2717 // Similarly, if signed division and the compare constant is exactly SMIN:
2718 // (X s/ Y) == SMIN --> (X == SMIN) && (Y == 1)
2719 // (X s/ Y) != SMIN --> (X != SMIN) || (Y != 1)
2720 if (Cmp.isEquality() && Div->hasOneUse() && C.isSignBitSet() &&
2721 (!DivIsSigned || C.isMinSignedValue())) {
2722 Value *XBig = Builder.CreateICmp(Pred, X, ConstantInt::get(Ty, C));
2723 Value *YOne = Builder.CreateICmp(Pred, Y, ConstantInt::get(Ty, 1));
2724 auto Logic = Pred == ICmpInst::ICMP_EQ ? Instruction::And : Instruction::Or;
2725 return BinaryOperator::Create(Logic, XBig, YOne);
2726 }
2727
2728 // Fold: icmp pred ([us]div X, C2), C -> range test
2729 // Fold this div into the comparison, producing a range check.
2730 // Determine, based on the divide type, what the range is being
2731 // checked. If there is an overflow on the low or high side, remember
2732 // it, otherwise compute the range [low, hi) bounding the new value.
2733 // See: InsertRangeTest above for the kinds of replacements possible.
2734 const APInt *C2;
2735 if (!match(Y, m_APInt(C2)))
2736 return nullptr;
2737
2738 // FIXME: If the operand types don't match the type of the divide
2739 // then don't attempt this transform. The code below doesn't have the
2740 // logic to deal with a signed divide and an unsigned compare (and
2741 // vice versa). This is because (x /s C2) <s C produces different
2742 // results than (x /s C2) <u C or (x /u C2) <s C or even
2743 // (x /u C2) <u C. Simply casting the operands and result won't
2744 // work. :( The if statement below tests that condition and bails
2745 // if it finds it.
2746 if (!Cmp.isEquality() && DivIsSigned != Cmp.isSigned())
2747 return nullptr;
2748
2749 // The ProdOV computation fails on divide by 0 and divide by -1. Cases with
2750 // INT_MIN will also fail if the divisor is 1. Although folds of all these
2751 // division-by-constant cases should be present, we can not assert that they
2752 // have happened before we reach this icmp instruction.
2753 if (C2->isZero() || C2->isOne() || (DivIsSigned && C2->isAllOnes()))
2754 return nullptr;
2755
2756 // Compute Prod = C * C2. We are essentially solving an equation of
2757 // form X / C2 = C. We solve for X by multiplying C2 and C.
2758 // By solving for X, we can turn this into a range check instead of computing
2759 // a divide.
2760 APInt Prod = C * *C2;
2761
2762 // Determine if the product overflows by seeing if the product is not equal to
2763 // the divide. Make sure we do the same kind of divide as in the LHS
2764 // instruction that we're folding.
2765 bool ProdOV = (DivIsSigned ? Prod.sdiv(*C2) : Prod.udiv(*C2)) != C;
2766
2767 // If the division is known to be exact, then there is no remainder from the
2768 // divide, so the covered range size is unit, otherwise it is the divisor.
2769 APInt RangeSize = Div->isExact() ? APInt(C2->getBitWidth(), 1) : *C2;
2770
2771 // Figure out the interval that is being checked. For example, a comparison
2772 // like "X /u 5 == 0" is really checking that X is in the interval [0, 5).
2773 // Compute this interval based on the constants involved and the signedness of
2774 // the compare/divide. This computes a half-open interval, keeping track of
2775 // whether either value in the interval overflows. After analysis each
2776 // overflow variable is set to 0 if it's corresponding bound variable is valid
2777 // -1 if overflowed off the bottom end, or +1 if overflowed off the top end.
2778 int LoOverflow = 0, HiOverflow = 0;
2779 APInt LoBound, HiBound;
2780
2781 if (!DivIsSigned) { // udiv
2782 // e.g. X/5 op 3 --> [15, 20)
2783 LoBound = Prod;
2784 HiOverflow = LoOverflow = ProdOV;
2785 if (!HiOverflow) {
2786 // If this is not an exact divide, then many values in the range collapse
2787 // to the same result value.
2788 HiOverflow = addWithOverflow(HiBound, LoBound, RangeSize, false);
2789 }
2790 } else if (C2->isStrictlyPositive()) { // Divisor is > 0.
2791 if (C.isZero()) { // (X / pos) op 0
2792 // Can't overflow. e.g. X/2 op 0 --> [-1, 2)
2793 LoBound = -(RangeSize - 1);
2794 HiBound = RangeSize;
2795 } else if (C.isStrictlyPositive()) { // (X / pos) op pos
2796 LoBound = Prod; // e.g. X/5 op 3 --> [15, 20)
2797 HiOverflow = LoOverflow = ProdOV;
2798 if (!HiOverflow)
2799 HiOverflow = addWithOverflow(HiBound, Prod, RangeSize, true);
2800 } else { // (X / pos) op neg
2801 // e.g. X/5 op -3 --> [-15-4, -15+1) --> [-19, -14)
2802 HiBound = Prod + 1;
2803 LoOverflow = HiOverflow = ProdOV ? -1 : 0;
2804 if (!LoOverflow) {
2805 APInt DivNeg = -RangeSize;
2806 LoOverflow = addWithOverflow(LoBound, HiBound, DivNeg, true) ? -1 : 0;
2807 }
2808 }
2809 } else if (C2->isNegative()) { // Divisor is < 0.
2810 if (Div->isExact())
2811 RangeSize.negate();
2812 if (C.isZero()) { // (X / neg) op 0
2813 // e.g. X/-5 op 0 --> [-4, 5)
2814 LoBound = RangeSize + 1;
2815 HiBound = -RangeSize;
2816 if (HiBound == *C2) { // -INTMIN = INTMIN
2817 HiOverflow = 1; // [INTMIN+1, overflow)
2818 HiBound = APInt(); // e.g. X/INTMIN = 0 --> X > INTMIN
2819 }
2820 } else if (C.isStrictlyPositive()) { // (X / neg) op pos
2821 // e.g. X/-5 op 3 --> [-19, -14)
2822 HiBound = Prod + 1;
2823 HiOverflow = LoOverflow = ProdOV ? -1 : 0;
2824 if (!LoOverflow)
2825 LoOverflow =
2826 addWithOverflow(LoBound, HiBound, RangeSize, true) ? -1 : 0;
2827 } else { // (X / neg) op neg
2828 LoBound = Prod; // e.g. X/-5 op -3 --> [15, 20)
2829 LoOverflow = HiOverflow = ProdOV;
2830 if (!HiOverflow)
2831 HiOverflow = subWithOverflow(HiBound, Prod, RangeSize, true);
2832 }
2833
2834 // Dividing by a negative swaps the condition. LT <-> GT
2835 Pred = ICmpInst::getSwappedPredicate(Pred);
2836 }
2837
2838 switch (Pred) {
2839 default:
2840 llvm_unreachable("Unhandled icmp predicate!");
2841 case ICmpInst::ICMP_EQ:
2842 if (LoOverflow && HiOverflow)
2843 return replaceInstUsesWith(Cmp, Builder.getFalse());
2844 if (HiOverflow)
2845 return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE,
2846 X, ConstantInt::get(Ty, LoBound));
2847 if (LoOverflow)
2848 return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
2849 X, ConstantInt::get(Ty, HiBound));
2850 return replaceInstUsesWith(
2851 Cmp, insertRangeTest(X, LoBound, HiBound, DivIsSigned, true));
2852 case ICmpInst::ICMP_NE:
2853 if (LoOverflow && HiOverflow)
2854 return replaceInstUsesWith(Cmp, Builder.getTrue());
2855 if (HiOverflow)
2856 return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
2857 X, ConstantInt::get(Ty, LoBound));
2858 if (LoOverflow)
2859 return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE,
2860 X, ConstantInt::get(Ty, HiBound));
2861 return replaceInstUsesWith(
2862 Cmp, insertRangeTest(X, LoBound, HiBound, DivIsSigned, false));
2863 case ICmpInst::ICMP_ULT:
2864 case ICmpInst::ICMP_SLT:
2865 if (LoOverflow == +1) // Low bound is greater than input range.
2866 return replaceInstUsesWith(Cmp, Builder.getTrue());
2867 if (LoOverflow == -1) // Low bound is less than input range.
2868 return replaceInstUsesWith(Cmp, Builder.getFalse());
2869 return new ICmpInst(Pred, X, ConstantInt::get(Ty, LoBound));
2870 case ICmpInst::ICMP_UGT:
2871 case ICmpInst::ICMP_SGT:
2872 if (HiOverflow == +1) // High bound greater than input range.
2873 return replaceInstUsesWith(Cmp, Builder.getFalse());
2874 if (HiOverflow == -1) // High bound less than input range.
2875 return replaceInstUsesWith(Cmp, Builder.getTrue());
2876 if (Pred == ICmpInst::ICMP_UGT)
2877 return new ICmpInst(ICmpInst::ICMP_UGE, X, ConstantInt::get(Ty, HiBound));
2878 return new ICmpInst(ICmpInst::ICMP_SGE, X, ConstantInt::get(Ty, HiBound));
2879 }
2880
2881 return nullptr;
2882}
2883
2884/// Fold icmp (sub X, Y), C.
2886 BinaryOperator *Sub,
2887 const APInt &C) {
2888 Value *X = Sub->getOperand(0), *Y = Sub->getOperand(1);
2889 ICmpInst::Predicate Pred = Cmp.getPredicate();
2890 Type *Ty = Sub->getType();
2891
2892 // (SubC - Y) == C) --> Y == (SubC - C)
2893 // (SubC - Y) != C) --> Y != (SubC - C)
2894 Constant *SubC;
2895 if (Cmp.isEquality() && match(X, m_ImmConstant(SubC))) {
2896 return new ICmpInst(Pred, Y,
2897 ConstantExpr::getSub(SubC, ConstantInt::get(Ty, C)));
2898 }
2899
2900 // (icmp P (sub nuw|nsw C2, Y), C) -> (icmp swap(P) Y, C2-C)
2901 const APInt *C2;
2902 APInt SubResult;
2903 ICmpInst::Predicate SwappedPred = Cmp.getSwappedPredicate();
2904 bool HasNSW = Sub->hasNoSignedWrap();
2905 bool HasNUW = Sub->hasNoUnsignedWrap();
2906 if (match(X, m_APInt(C2)) &&
2907 ((Cmp.isUnsigned() && HasNUW) || (Cmp.isSigned() && HasNSW)) &&
2908 !subWithOverflow(SubResult, *C2, C, Cmp.isSigned()))
2909 return new ICmpInst(SwappedPred, Y, ConstantInt::get(Ty, SubResult));
2910
2911 // X - Y == 0 --> X == Y.
2912 // X - Y != 0 --> X != Y.
2913 // TODO: We allow this with multiple uses as long as the other uses are not
2914 // in phis. The phi use check is guarding against a codegen regression
2915 // for a loop test. If the backend could undo this (and possibly
2916 // subsequent transforms), we would not need this hack.
2917 if (Cmp.isEquality() && C.isZero() &&
2918 none_of((Sub->users()), [](const User *U) { return isa<PHINode>(U); }))
2919 return new ICmpInst(Pred, X, Y);
2920
2921 // The following transforms are only worth it if the only user of the subtract
2922 // is the icmp.
2923 // TODO: This is an artificial restriction for all of the transforms below
2924 // that only need a single replacement icmp. Can these use the phi test
2925 // like the transform above here?
2926 if (!Sub->hasOneUse())
2927 return nullptr;
2928
2929 if (Sub->hasNoSignedWrap()) {
2930 // (icmp sgt (sub nsw X, Y), -1) -> (icmp sge X, Y)
2931 if (Pred == ICmpInst::ICMP_SGT && C.isAllOnes())
2932 return new ICmpInst(ICmpInst::ICMP_SGE, X, Y);
2933
2934 // (icmp sgt (sub nsw X, Y), 0) -> (icmp sgt X, Y)
2935 if (Pred == ICmpInst::ICMP_SGT && C.isZero())
2936 return new ICmpInst(ICmpInst::ICMP_SGT, X, Y);
2937
2938 // (icmp slt (sub nsw X, Y), 0) -> (icmp slt X, Y)
2939 if (Pred == ICmpInst::ICMP_SLT && C.isZero())
2940 return new ICmpInst(ICmpInst::ICMP_SLT, X, Y);
2941
2942 // (icmp slt (sub nsw X, Y), 1) -> (icmp sle X, Y)
2943 if (Pred == ICmpInst::ICMP_SLT && C.isOne())
2944 return new ICmpInst(ICmpInst::ICMP_SLE, X, Y);
2945 }
2946
2947 if (!match(X, m_APInt(C2)))
2948 return nullptr;
2949
2950 // C2 - Y <u C -> (Y | (C - 1)) == C2
2951 // iff (C2 & (C - 1)) == C - 1 and C is a power of 2
2952 if (Pred == ICmpInst::ICMP_ULT && C.isPowerOf2() &&
2953 (*C2 & (C - 1)) == (C - 1))
2954 return new ICmpInst(ICmpInst::ICMP_EQ, Builder.CreateOr(Y, C - 1), X);
2955
2956 // C2 - Y >u C -> (Y | C) != C2
2957 // iff C2 & C == C and C + 1 is a power of 2
2958 if (Pred == ICmpInst::ICMP_UGT && (C + 1).isPowerOf2() && (*C2 & C) == C)
2959 return new ICmpInst(ICmpInst::ICMP_NE, Builder.CreateOr(Y, C), X);
2960
2961 // We have handled special cases that reduce.
2962 // Canonicalize any remaining sub to add as:
2963 // (C2 - Y) > C --> (Y + ~C2) < ~C
2964 Value *Add = Builder.CreateAdd(Y, ConstantInt::get(Ty, ~(*C2)), "notsub",
2965 HasNUW, HasNSW);
2966 return new ICmpInst(SwappedPred, Add, ConstantInt::get(Ty, ~C));
2967}
2968
2969static Value *createLogicFromTable(const std::bitset<4> &Table, Value *Op0,
2970 Value *Op1, IRBuilderBase &Builder,
2971 bool HasOneUse) {
2972 auto FoldConstant = [&](bool Val) {
2973 Constant *Res = Val ? Builder.getTrue() : Builder.getFalse();
2974 if (Op0->getType()->isVectorTy())
2976 cast<VectorType>(Op0->getType())->getElementCount(), Res);
2977 return Res;
2978 };
2979
2980 switch (Table.to_ulong()) {
2981 case 0: // 0 0 0 0
2982 return FoldConstant(false);
2983 case 1: // 0 0 0 1
2984 return HasOneUse ? Builder.CreateNot(Builder.CreateOr(Op0, Op1)) : nullptr;
2985 case 2: // 0 0 1 0
2986 return HasOneUse ? Builder.CreateAnd(Builder.CreateNot(Op0), Op1) : nullptr;
2987 case 3: // 0 0 1 1
2988 return Builder.CreateNot(Op0);
2989 case 4: // 0 1 0 0
2990 return HasOneUse ? Builder.CreateAnd(Op0, Builder.CreateNot(Op1)) : nullptr;
2991 case 5: // 0 1 0 1
2992 return Builder.CreateNot(Op1);
2993 case 6: // 0 1 1 0
2994 return Builder.CreateXor(Op0, Op1);
2995 case 7: // 0 1 1 1
2996 return HasOneUse ? Builder.CreateNot(Builder.CreateAnd(Op0, Op1)) : nullptr;
2997 case 8: // 1 0 0 0
2998 return Builder.CreateAnd(Op0, Op1);
2999 case 9: // 1 0 0 1
3000 return HasOneUse ? Builder.CreateNot(Builder.CreateXor(Op0, Op1)) : nullptr;
3001 case 10: // 1 0 1 0
3002 return Op1;
3003 case 11: // 1 0 1 1
3004 return HasOneUse ? Builder.CreateOr(Builder.CreateNot(Op0), Op1) : nullptr;
3005 case 12: // 1 1 0 0
3006 return Op0;
3007 case 13: // 1 1 0 1
3008 return HasOneUse ? Builder.CreateOr(Op0, Builder.CreateNot(Op1)) : nullptr;
3009 case 14: // 1 1 1 0
3010 return Builder.CreateOr(Op0, Op1);
3011 case 15: // 1 1 1 1
3012 return FoldConstant(true);
3013 default:
3014 llvm_unreachable("Invalid Operation");
3015 }
3016 return nullptr;
3017}
3018
3019/// Fold icmp (add X, Y), C.
3022 const APInt &C) {
3023 Value *Y = Add->getOperand(1);
3024 Value *X = Add->getOperand(0);
3025
3026 Value *Op0, *Op1;
3027 Instruction *Ext0, *Ext1;
3028 const CmpInst::Predicate Pred = Cmp.getPredicate();
3029 if (match(Add,
3032 m_ZExtOrSExt(m_Value(Op1))))) &&
3033 Op0->getType()->isIntOrIntVectorTy(1) &&
3034 Op1->getType()->isIntOrIntVectorTy(1)) {
3035 unsigned BW = C.getBitWidth();
3036 std::bitset<4> Table;
3037 auto ComputeTable = [&](bool Op0Val, bool Op1Val) {
3038 int Res = 0;
3039 if (Op0Val)
3040 Res += isa<ZExtInst>(Ext0) ? 1 : -1;
3041 if (Op1Val)
3042 Res += isa<ZExtInst>(Ext1) ? 1 : -1;
3043 return ICmpInst::compare(APInt(BW, Res, true), C, Pred);
3044 };
3045
3046 Table[0] = ComputeTable(false, false);
3047 Table[1] = ComputeTable(false, true);
3048 Table[2] = ComputeTable(true, false);
3049 Table[3] = ComputeTable(true, true);
3050 if (auto *Cond =
3051 createLogicFromTable(Table, Op0, Op1, Builder, Add->hasOneUse()))
3052 return replaceInstUsesWith(Cmp, Cond);
3053 }
3054 const APInt *C2;
3055 if (Cmp.isEquality() || !match(Y, m_APInt(C2)))
3056 return nullptr;
3057
3058 // Fold icmp pred (add X, C2), C.
3059 Type *Ty = Add->getType();
3060
3061 // If the add does not wrap, we can always adjust the compare by subtracting
3062 // the constants. Equality comparisons are handled elsewhere. SGE/SLE/UGE/ULE
3063 // are canonicalized to SGT/SLT/UGT/ULT.
3064 if ((Add->hasNoSignedWrap() &&
3065 (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLT)) ||
3066 (Add->hasNoUnsignedWrap() &&
3067 (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_ULT))) {
3068 bool Overflow;
3069 APInt NewC =
3070 Cmp.isSigned() ? C.ssub_ov(*C2, Overflow) : C.usub_ov(*C2, Overflow);
3071 // If there is overflow, the result must be true or false.
3072 // TODO: Can we assert there is no overflow because InstSimplify always
3073 // handles those cases?
3074 if (!Overflow)
3075 // icmp Pred (add nsw X, C2), C --> icmp Pred X, (C - C2)
3076 return new ICmpInst(Pred, X, ConstantInt::get(Ty, NewC));
3077 }
3078
3079 auto CR = ConstantRange::makeExactICmpRegion(Pred, C).subtract(*C2);
3080 const APInt &Upper = CR.getUpper();
3081 const APInt &Lower = CR.getLower();
3082 if (Cmp.isSigned()) {
3083 if (Lower.isSignMask())
3084 return new ICmpInst(ICmpInst::ICMP_SLT, X, ConstantInt::get(Ty, Upper));
3085 if (Upper.isSignMask())
3086 return new ICmpInst(ICmpInst::ICMP_SGE, X, ConstantInt::get(Ty, Lower));
3087 } else {
3088 if (Lower.isMinValue())
3089 return new ICmpInst(ICmpInst::ICMP_ULT, X, ConstantInt::get(Ty, Upper));
3090 if (Upper.isMinValue())
3091 return new ICmpInst(ICmpInst::ICMP_UGE, X, ConstantInt::get(Ty, Lower));
3092 }
3093
3094 // This set of folds is intentionally placed after folds that use no-wrapping
3095 // flags because those folds are likely better for later analysis/codegen.
3098
3099 // Fold compare with offset to opposite sign compare if it eliminates offset:
3100 // (X + C2) >u C --> X <s -C2 (if C == C2 + SMAX)
3101 if (Pred == CmpInst::ICMP_UGT && C == *C2 + SMax)
3102 return new ICmpInst(ICmpInst::ICMP_SLT, X, ConstantInt::get(Ty, -(*C2)));
3103
3104 // (X + C2) <u C --> X >s ~C2 (if C == C2 + SMIN)
3105 if (Pred == CmpInst::ICMP_ULT && C == *C2 + SMin)
3106 return new ICmpInst(ICmpInst::ICMP_SGT, X, ConstantInt::get(Ty, ~(*C2)));
3107
3108 // (X + C2) >s C --> X <u (SMAX - C) (if C == C2 - 1)
3109 if (Pred == CmpInst::ICMP_SGT && C == *C2 - 1)
3110 return new ICmpInst(ICmpInst::ICMP_ULT, X, ConstantInt::get(Ty, SMax - C));
3111
3112 // (X + C2) <s C --> X >u (C ^ SMAX) (if C == C2)
3113 if (Pred == CmpInst::ICMP_SLT && C == *C2)
3114 return new ICmpInst(ICmpInst::ICMP_UGT, X, ConstantInt::get(Ty, C ^ SMax));
3115
3116 // (X + -1) <u C --> X <=u C (if X is never null)
3117 if (Pred == CmpInst::ICMP_ULT && C2->isAllOnes()) {
3118 const SimplifyQuery Q = SQ.getWithInstruction(&Cmp);
3119 if (llvm::isKnownNonZero(X, Q))
3120 return new ICmpInst(ICmpInst::ICMP_ULE, X, ConstantInt::get(Ty, C));
3121 }
3122
3123 if (!Add->hasOneUse())
3124 return nullptr;
3125
3126 // X+C <u C2 -> (X & -C2) == C
3127 // iff C & (C2-1) == 0
3128 // C2 is a power of 2
3129 if (Pred == ICmpInst::ICMP_ULT && C.isPowerOf2() && (*C2 & (C - 1)) == 0)
3131 ConstantExpr::getNeg(cast<Constant>(Y)));
3132
3133 // X+C2 <u C -> (X & C) == 2C
3134 // iff C == -(C2)
3135 // C2 is a power of 2
3136 if (Pred == ICmpInst::ICMP_ULT && C2->isPowerOf2() && C == -*C2)
3138 ConstantInt::get(Ty, C * 2));
3139
3140 // X+C >u C2 -> (X & ~C2) != C
3141 // iff C & C2 == 0
3142 // C2+1 is a power of 2
3143 if (Pred == ICmpInst::ICMP_UGT && (C + 1).isPowerOf2() && (*C2 & C) == 0)
3145 ConstantExpr::getNeg(cast<Constant>(Y)));
3146
3147 // The range test idiom can use either ult or ugt. Arbitrarily canonicalize
3148 // to the ult form.
3149 // X+C2 >u C -> X+(C2-C-1) <u ~C
3150 if (Pred == ICmpInst::ICMP_UGT)
3151 return new ICmpInst(ICmpInst::ICMP_ULT,
3152 Builder.CreateAdd(X, ConstantInt::get(Ty, *C2 - C - 1)),
3153 ConstantInt::get(Ty, ~C));
3154
3155 return nullptr;
3156}
3157
3159 Value *&RHS, ConstantInt *&Less,
3160 ConstantInt *&Equal,
3161 ConstantInt *&Greater) {
3162 // TODO: Generalize this to work with other comparison idioms or ensure
3163 // they get canonicalized into this form.
3164
3165 // select i1 (a == b),
3166 // i32 Equal,
3167 // i32 (select i1 (a < b), i32 Less, i32 Greater)
3168 // where Equal, Less and Greater are placeholders for any three constants.
3169 ICmpInst::Predicate PredA;
3170 if (!match(SI->getCondition(), m_ICmp(PredA, m_Value(LHS), m_Value(RHS))) ||
3171 !ICmpInst::isEquality(PredA))
3172 return false;
3173 Value *EqualVal = SI->getTrueValue();
3174 Value *UnequalVal = SI->getFalseValue();
3175 // We still can get non-canonical predicate here, so canonicalize.
3176 if (PredA == ICmpInst::ICMP_NE)
3177 std::swap(EqualVal, UnequalVal);
3178 if (!match(EqualVal, m_ConstantInt(Equal)))
3179 return false;
3180 ICmpInst::Predicate PredB;
3181 Value *LHS2, *RHS2;
3182 if (!match(UnequalVal, m_Select(m_ICmp(PredB, m_Value(LHS2), m_Value(RHS2)),
3183 m_ConstantInt(Less), m_ConstantInt(Greater))))
3184 return false;
3185 // We can get predicate mismatch here, so canonicalize if possible:
3186 // First, ensure that 'LHS' match.
3187 if (LHS2 != LHS) {
3188 // x sgt y <--> y slt x
3189 std::swap(LHS2, RHS2);
3190 PredB = ICmpInst::getSwappedPredicate(PredB);
3191 }
3192 if (LHS2 != LHS)
3193 return false;
3194 // We also need to canonicalize 'RHS'.
3195 if (PredB == ICmpInst::ICMP_SGT && isa<Constant>(RHS2)) {
3196 // x sgt C-1 <--> x sge C <--> not(x slt C)
3197 auto FlippedStrictness =
3199 PredB, cast<Constant>(RHS2));
3200 if (!FlippedStrictness)
3201 return false;
3202 assert(FlippedStrictness->first == ICmpInst::ICMP_SGE &&
3203 "basic correctness failure");
3204 RHS2 = FlippedStrictness->second;
3205 // And kind-of perform the result swap.
3206 std::swap(Less, Greater);
3207 PredB = ICmpInst::ICMP_SLT;
3208 }
3209 return PredB == ICmpInst::ICMP_SLT && RHS == RHS2;
3210}
3211
3214 ConstantInt *C) {
3215
3216 assert(C && "Cmp RHS should be a constant int!");
3217 // If we're testing a constant value against the result of a three way
3218 // comparison, the result can be expressed directly in terms of the
3219 // original values being compared. Note: We could possibly be more
3220 // aggressive here and remove the hasOneUse test. The original select is
3221 // really likely to simplify or sink when we remove a test of the result.
3222 Value *OrigLHS, *OrigRHS;
3223 ConstantInt *C1LessThan, *C2Equal, *C3GreaterThan;
3224 if (Cmp.hasOneUse() &&
3225 matchThreeWayIntCompare(Select, OrigLHS, OrigRHS, C1LessThan, C2Equal,
3226 C3GreaterThan)) {
3227 assert(C1LessThan && C2Equal && C3GreaterThan);
3228
3229 bool TrueWhenLessThan = ICmpInst::compare(
3230 C1LessThan->getValue(), C->getValue(), Cmp.getPredicate());
3231 bool TrueWhenEqual = ICmpInst::compare(C2Equal->getValue(), C->getValue(),
3232 Cmp.getPredicate());
3233 bool TrueWhenGreaterThan = ICmpInst::compare(
3234 C3GreaterThan->getValue(), C->getValue(), Cmp.getPredicate());
3235
3236 // This generates the new instruction that will replace the original Cmp
3237 // Instruction. Instead of enumerating the various combinations when
3238 // TrueWhenLessThan, TrueWhenEqual and TrueWhenGreaterThan are true versus
3239 // false, we rely on chaining of ORs and future passes of InstCombine to
3240 // simplify the OR further (i.e. a s< b || a == b becomes a s<= b).
3241
3242 // When none of the three constants satisfy the predicate for the RHS (C),
3243 // the entire original Cmp can be simplified to a false.
3245 if (TrueWhenLessThan)
3247 OrigLHS, OrigRHS));
3248 if (TrueWhenEqual)
3250 OrigLHS, OrigRHS));
3251 if (TrueWhenGreaterThan)
3253 OrigLHS, OrigRHS));
3254
3255 return replaceInstUsesWith(Cmp, Cond);
3256 }
3257 return nullptr;
3258}
3259
3261 auto *Bitcast = dyn_cast<BitCastInst>(Cmp.getOperand(0));
3262 if (!Bitcast)
3263 return nullptr;
3264
3265 ICmpInst::Predicate Pred = Cmp.getPredicate();
3266 Value *Op1 = Cmp.getOperand(1);
3267 Value *BCSrcOp = Bitcast->getOperand(0);
3268 Type *SrcType = Bitcast->getSrcTy();
3269 Type *DstType = Bitcast->getType();
3270
3271 // Make sure the bitcast doesn't change between scalar and vector and
3272 // doesn't change the number of vector elements.
3273 if (SrcType->isVectorTy() == DstType->isVectorTy() &&
3274 SrcType->getScalarSizeInBits() == DstType->getScalarSizeInBits()) {
3275 // Zero-equality and sign-bit checks are preserved through sitofp + bitcast.
3276 Value *X;
3277 if (match(BCSrcOp, m_SIToFP(m_Value(X)))) {
3278 // icmp eq (bitcast (sitofp X)), 0 --> icmp eq X, 0
3279 // icmp ne (bitcast (sitofp X)), 0 --> icmp ne X, 0
3280 // icmp slt (bitcast (sitofp X)), 0 --> icmp slt X, 0
3281 // icmp sgt (bitcast (sitofp X)), 0 --> icmp sgt X, 0
3282 if ((Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_SLT ||
3283 Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_SGT) &&
3284 match(Op1, m_Zero()))
3285 return new ICmpInst(Pred, X, ConstantInt::getNullValue(X->getType()));
3286
3287 // icmp slt (bitcast (sitofp X)), 1 --> icmp slt X, 1
3288 if (Pred == ICmpInst::ICMP_SLT && match(Op1, m_One()))
3289 return new ICmpInst(Pred, X, ConstantInt::get(X->getType(), 1));
3290
3291 // icmp sgt (bitcast (sitofp X)), -1 --> icmp sgt X, -1
3292 if (Pred == ICmpInst::ICMP_SGT && match(Op1, m_AllOnes()))
3293 return new ICmpInst(Pred, X,
3294 ConstantInt::getAllOnesValue(X->getType()));
3295 }
3296
3297 // Zero-equality checks are preserved through unsigned floating-point casts:
3298 // icmp eq (bitcast (uitofp X)), 0 --> icmp eq X, 0
3299 // icmp ne (bitcast (uitofp X)), 0 --> icmp ne X, 0
3300 if (match(BCSrcOp, m_UIToFP(m_Value(X))))
3301 if (Cmp.isEquality() && match(Op1, m_Zero()))
3302 return new ICmpInst(Pred, X, ConstantInt::getNullValue(X->getType()));
3303
3304 const APInt *C;
3305 bool TrueIfSigned;
3306 if (match(Op1, m_APInt(C)) && Bitcast->hasOneUse()) {
3307 // If this is a sign-bit test of a bitcast of a casted FP value, eliminate
3308 // the FP extend/truncate because that cast does not change the sign-bit.
3309 // This is true for all standard IEEE-754 types and the X86 80-bit type.
3310 // The sign-bit is always the most significant bit in those types.
3311 if (isSignBitCheck(Pred, *C, TrueIfSigned) &&
3312 (match(BCSrcOp, m_FPExt(m_Value(X))) ||
3313 match(BCSrcOp, m_FPTrunc(m_Value(X))))) {
3314 // (bitcast (fpext/fptrunc X)) to iX) < 0 --> (bitcast X to iY) < 0
3315 // (bitcast (fpext/fptrunc X)) to iX) > -1 --> (bitcast X to iY) > -1
3316 Type *XType = X->getType();
3317
3318 // We can't currently handle Power style floating point operations here.
3319 if (!(XType->isPPC_FP128Ty() || SrcType->isPPC_FP128Ty())) {
3320 Type *NewType = Builder.getIntNTy(XType->getScalarSizeInBits());
3321 if (auto *XVTy = dyn_cast<VectorType>(XType))
3322 NewType = VectorType::get(NewType, XVTy->getElementCount());
3323 Value *NewBitcast = Builder.CreateBitCast(X, NewType);
3324 if (TrueIfSigned)
3325 return new ICmpInst(ICmpInst::ICMP_SLT, NewBitcast,
3326 ConstantInt::getNullValue(NewType));
3327 else
3328 return new ICmpInst(ICmpInst::ICMP_SGT, NewBitcast,
3330 }
3331 }
3332
3333 // icmp eq/ne (bitcast X to int), special fp -> llvm.is.fpclass(X, class)
3334 Type *FPType = SrcType->getScalarType();
3335 if (!Cmp.getParent()->getParent()->hasFnAttribute(
3336 Attribute::NoImplicitFloat) &&
3337 Cmp.isEquality() && FPType->isIEEELikeFPTy()) {
3338 FPClassTest Mask = APFloat(FPType->getFltSemantics(), *C).classify();
3339 if (Mask & (fcInf | fcZero)) {
3340 if (Pred == ICmpInst::ICMP_NE)
3341 Mask = ~Mask;
3342 return replaceInstUsesWith(Cmp,
3343 Builder.createIsFPClass(BCSrcOp, Mask));
3344 }
3345 }
3346 }
3347 }
3348
3349 const APInt *C;
3350 if (!match(Cmp.getOperand(1), m_APInt(C)) || !DstType->isIntegerTy() ||
3351 !SrcType->isIntOrIntVectorTy())
3352 return nullptr;
3353
3354 // If this is checking if all elements of a vector compare are set or not,
3355 // invert the casted vector equality compare and test if all compare
3356 // elements are clear or not. Compare against zero is generally easier for
3357 // analysis and codegen.
3358 // icmp eq/ne (bitcast (not X) to iN), -1 --> icmp eq/ne (bitcast X to iN), 0
3359 // Example: are all elements equal? --> are zero elements not equal?
3360 // TODO: Try harder to reduce compare of 2 freely invertible operands?
3361 if (Cmp.isEquality() && C->isAllOnes() && Bitcast->hasOneUse()) {
3362 if (Value *NotBCSrcOp =
3363 getFreelyInverted(BCSrcOp, BCSrcOp->hasOneUse(), &Builder)) {
3364 Value *Cast = Builder.CreateBitCast(NotBCSrcOp, DstType);
3365 return new ICmpInst(Pred, Cast, ConstantInt::getNullValue(DstType));
3366 }
3367 }
3368
3369 // If this is checking if all elements of an extended vector are clear or not,
3370 // compare in a narrow type to eliminate the extend:
3371 // icmp eq/ne (bitcast (ext X) to iN), 0 --> icmp eq/ne (bitcast X to iM), 0
3372 Value *X;
3373 if (Cmp.isEquality() && C->isZero() && Bitcast->hasOneUse() &&
3374 match(BCSrcOp, m_ZExtOrSExt(m_Value(X)))) {
3375 if (auto *VecTy = dyn_cast<FixedVectorType>(X->getType())) {
3376 Type *NewType = Builder.getIntNTy(VecTy->getPrimitiveSizeInBits());
3377 Value *NewCast = Builder.CreateBitCast(X, NewType);
3378 return new ICmpInst(Pred, NewCast, ConstantInt::getNullValue(NewType));
3379 }
3380 }
3381
3382 // Folding: icmp <pred> iN X, C
3383 // where X = bitcast <M x iK> (shufflevector <M x iK> %vec, undef, SC)) to iN
3384 // and C is a splat of a K-bit pattern
3385 // and SC is a constant vector = <C', C', C', ..., C'>
3386 // Into:
3387 // %E = extractelement <M x iK> %vec, i32 C'
3388 // icmp <pred> iK %E, trunc(C)
3389 Value *Vec;
3390 ArrayRef<int> Mask;
3391 if (match(BCSrcOp, m_Shuffle(m_Value(Vec), m_Undef(), m_Mask(Mask)))) {
3392 // Check whether every element of Mask is the same constant
3393 if (all_equal(Mask)) {
3394 auto *VecTy = cast<VectorType>(SrcType);
3395 auto *EltTy = cast<IntegerType>(VecTy->getElementType());
3396 if (C->isSplat(EltTy->getBitWidth())) {
3397 // Fold the icmp based on the value of C
3398 // If C is M copies of an iK sized bit pattern,
3399 // then:
3400 // => %E = extractelement <N x iK> %vec, i32 Elem
3401 // icmp <pred> iK %SplatVal, <pattern>
3402 Value *Elem = Builder.getInt32(Mask[0]);
3403 Value *Extract = Builder.CreateExtractElement(Vec, Elem);
3404 Value *NewC = ConstantInt::get(EltTy, C->trunc(EltTy->getBitWidth()));
3405 return new ICmpInst(Pred, Extract, NewC);
3406 }
3407 }
3408 }
3409 return nullptr;
3410}
3411
3412/// Try to fold integer comparisons with a constant operand: icmp Pred X, C
3413/// where X is some kind of instruction.
3415 const APInt *C;
3416
3417 if (match(Cmp.getOperand(1), m_APInt(C))) {
3418 if (auto *BO = dyn_cast<BinaryOperator>(Cmp.getOperand(0)))
3419 if (Instruction *I = foldICmpBinOpWithConstant(Cmp, BO, *C))
3420 return I;
3421
3422 if (auto *SI = dyn_cast<SelectInst>(Cmp.getOperand(0)))
3423 // For now, we only support constant integers while folding the
3424 // ICMP(SELECT)) pattern. We can extend this to support vector of integers
3425 // similar to the cases handled by binary ops above.
3426 if (auto *ConstRHS = dyn_cast<ConstantInt>(Cmp.getOperand(1)))
3427 if (Instruction *I = foldICmpSelectConstant(Cmp, SI, ConstRHS))
3428 return I;
3429
3430 if (auto *TI = dyn_cast<TruncInst>(Cmp.getOperand(0)))
3431 if (Instruction *I = foldICmpTruncConstant(Cmp, TI, *C))
3432 return I;
3433
3434 if (auto *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0)))
3436 return I;
3437
3438 // (extractval ([s/u]subo X, Y), 0) == 0 --> X == Y
3439 // (extractval ([s/u]subo X, Y), 0) != 0 --> X != Y
3440 // TODO: This checks one-use, but that is not strictly necessary.
3441 Value *Cmp0 = Cmp.getOperand(0);
3442 Value *X, *Y;
3443 if (C->isZero() && Cmp.isEquality() && Cmp0->hasOneUse() &&
3444 (match(Cmp0,
3445 m_ExtractValue<0>(m_Intrinsic<Intrinsic::ssub_with_overflow>(
3446 m_Value(X), m_Value(Y)))) ||
3447 match(Cmp0,
3448 m_ExtractValue<0>(m_Intrinsic<Intrinsic::usub_with_overflow>(
3449 m_Value(X), m_Value(Y))))))
3450 return new ICmpInst(Cmp.getPredicate(), X, Y);
3451 }
3452
3453 if (match(Cmp.getOperand(1), m_APIntAllowPoison(C)))
3455
3456 return nullptr;
3457}
3458
3459/// Fold an icmp equality instruction with binary operator LHS and constant RHS:
3460/// icmp eq/ne BO, C.
3462 ICmpInst &Cmp, BinaryOperator *BO, const APInt &C) {
3463 // TODO: Some of these folds could work with arbitrary constants, but this
3464 // function is limited to scalar and vector splat constants.
3465 if (!Cmp.isEquality())
3466 return nullptr;
3467
3468 ICmpInst::Predicate Pred = Cmp.getPredicate();
3469 bool isICMP_NE = Pred == ICmpInst::ICMP_NE;
3470 Constant *RHS = cast<Constant>(Cmp.getOperand(1));
3471 Value *BOp0 = BO->getOperand(0), *BOp1 = BO->getOperand(1);
3472
3473 switch (BO->getOpcode()) {
3474 case Instruction::SRem:
3475 // If we have a signed (X % (2^c)) == 0, turn it into an unsigned one.
3476 if (C.isZero() && BO->hasOneUse()) {
3477 const APInt *BOC;
3478 if (match(BOp1, m_APInt(BOC)) && BOC->sgt(1) && BOC->isPowerOf2()) {
3479 Value *NewRem = Builder.CreateURem(BOp0, BOp1, BO->getName());
3480 return new ICmpInst(Pred, NewRem,
3482 }
3483 }
3484 break;
3485 case Instruction::Add: {
3486 // (A + C2) == C --> A == (C - C2)
3487 // (A + C2) != C --> A != (C - C2)
3488 // TODO: Remove the one-use limitation? See discussion in D58633.
3489 if (Constant *C2 = dyn_cast<Constant>(BOp1)) {
3490 if (BO->hasOneUse())
3491 return new ICmpInst(Pred, BOp0, ConstantExpr::getSub(RHS, C2));
3492 } else if (C.isZero()) {
3493 // Replace ((add A, B) != 0) with (A != -B) if A or B is
3494 // efficiently invertible, or if the add has just this one use.
3495 if (Value *NegVal = dyn_castNegVal(BOp1))
3496 return new ICmpInst(Pred, BOp0, NegVal);
3497 if (Value *NegVal = dyn_castNegVal(BOp0))
3498 return new ICmpInst(Pred, NegVal, BOp1);
3499 if (BO->hasOneUse()) {
3500 // (add nuw A, B) != 0 -> (or A, B) != 0
3501 if (match(BO, m_NUWAdd(m_Value(), m_Value()))) {
3502 Value *Or = Builder.CreateOr(BOp0, BOp1);
3503 return new ICmpInst(Pred, Or, Constant::getNullValue(BO->getType()));
3504 }
3505 Value *Neg = Builder.CreateNeg(BOp1);
3506 Neg->takeName(BO);
3507 return new ICmpInst(Pred, BOp0, Neg);
3508 }
3509 }
3510 break;
3511 }
3512 case Instruction::Xor:
3513 if (Constant *BOC = dyn_cast<Constant>(BOp1)) {
3514 // For the xor case, we can xor two constants together, eliminating
3515 // the explicit xor.
3516 return new ICmpInst(Pred, BOp0, ConstantExpr::getXor(RHS, BOC));
3517 } else if (C.isZero()) {
3518 // Replace ((xor A, B) != 0) with (A != B)
3519 return new ICmpInst(Pred, BOp0, BOp1);
3520 }
3521 break;
3522 case Instruction::Or: {
3523 const APInt *BOC;
3524 if (match(BOp1, m_APInt(BOC)) && BO->hasOneUse() && RHS->isAllOnesValue()) {
3525 // Comparing if all bits outside of a constant mask are set?
3526 // Replace (X | C) == -1 with (X & ~C) == ~C.
3527 // This removes the -1 constant.
3528 Constant *NotBOC = ConstantExpr::getNot(cast<Constant>(BOp1));
3529 Value *And = Builder.CreateAnd(BOp0, NotBOC);
3530 return new ICmpInst(Pred, And, NotBOC);
3531 }
3532 break;
3533 }
3534 case Instruction::UDiv:
3535 case Instruction::SDiv:
3536 if (BO->isExact()) {
3537 // div exact X, Y eq/ne 0 -> X eq/ne 0
3538 // div exact X, Y eq/ne 1 -> X eq/ne Y
3539 // div exact X, Y eq/ne C ->
3540 // if Y * C never-overflow && OneUse:
3541 // -> Y * C eq/ne X
3542 if (C.isZero())
3543 return new ICmpInst(Pred, BOp0, Constant::getNullValue(BO->getType()));
3544 else if (C.isOne())
3545 return new ICmpInst(Pred, BOp0, BOp1);
3546 else if (BO->hasOneUse()) {
3548 Instruction::Mul, BO->getOpcode() == Instruction::SDiv, BOp1,
3549 Cmp.getOperand(1), BO);
3551 Value *YC =
3552 Builder.CreateMul(BOp1, ConstantInt::get(BO->getType(), C));
3553 return new ICmpInst(Pred, YC, BOp0);
3554 }
3555 }
3556 }
3557 if (BO->getOpcode() == Instruction::UDiv && C.isZero()) {
3558 // (icmp eq/ne (udiv A, B), 0) -> (icmp ugt/ule i32 B, A)
3559 auto NewPred = isICMP_NE ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_UGT;
3560 return new ICmpInst(NewPred, BOp1, BOp0);
3561 }
3562 break;
3563 default:
3564 break;
3565 }
3566 return nullptr;
3567}
3568
3570 const APInt &CRhs,
3571 InstCombiner::BuilderTy &Builder,
3572 const SimplifyQuery &Q) {
3573 assert(CtpopLhs->getIntrinsicID() == Intrinsic::ctpop &&
3574 "Non-ctpop intrin in ctpop fold");
3575 if (!CtpopLhs->hasOneUse())
3576 return nullptr;
3577
3578 // Power of 2 test:
3579 // isPow2OrZero : ctpop(X) u< 2
3580 // isPow2 : ctpop(X) == 1
3581 // NotPow2OrZero: ctpop(X) u> 1
3582 // NotPow2 : ctpop(X) != 1
3583 // If we know any bit of X can be folded to:
3584 // IsPow2 : X & (~Bit) == 0
3585 // NotPow2 : X & (~Bit) != 0
3586 const ICmpInst::Predicate Pred = I.getPredicate();
3587 if (((I.isEquality() || Pred == ICmpInst::ICMP_UGT) && CRhs == 1) ||
3588 (Pred == ICmpInst::ICMP_ULT && CRhs == 2)) {
3589 Value *Op = CtpopLhs->getArgOperand(0);
3590 KnownBits OpKnown = computeKnownBits(Op, Q.DL,
3591 /*Depth*/ 0, Q.AC, Q.CxtI, Q.DT);
3592 // No need to check for count > 1, that should be already constant folded.
3593 if (OpKnown.countMinPopulation() == 1) {
3594 Value *And = Builder.CreateAnd(
3595 Op, Constant::getIntegerValue(Op->getType(), ~(OpKnown.One)));
3596 return new ICmpInst(
3597 (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_ULT)
3600 And, Constant::getNullValue(Op->getType()));
3601 }
3602 }
3603
3604 return nullptr;
3605}
3606
3607/// Fold an equality icmp with LLVM intrinsic and constant operand.
3609 ICmpInst &Cmp, IntrinsicInst *II, const APInt &C) {
3610 Type *Ty = II->getType();
3611 unsigned BitWidth = C.getBitWidth();
3612 const ICmpInst::Predicate Pred = Cmp.getPredicate();
3613
3614 switch (II->getIntrinsicID()) {
3615 case Intrinsic::abs:
3616 // abs(A) == 0 -> A == 0
3617 // abs(A) == INT_MIN -> A == INT_MIN
3618 if (C.isZero() || C.isMinSignedValue())
3619 return new ICmpInst(Pred, II->getArgOperand(0), ConstantInt::get(Ty, C));
3620 break;
3621
3622 case Intrinsic::bswap:
3623 // bswap(A) == C -> A == bswap(C)
3624 return new ICmpInst(Pred, II->getArgOperand(0),
3625 ConstantInt::get(Ty, C.byteSwap()));
3626
3627 case Intrinsic::bitreverse:
3628 // bitreverse(A) == C -> A == bitreverse(C)
3629 return new ICmpInst(Pred, II->getArgOperand(0),
3630 ConstantInt::get(Ty, C.reverseBits()));
3631
3632 case Intrinsic::ctlz:
3633 case Intrinsic::cttz: {
3634 // ctz(A) == bitwidth(A) -> A == 0 and likewise for !=
3635 if (C == BitWidth)
3636 return new ICmpInst(Pred, II->getArgOperand(0),
3638
3639 // ctz(A) == C -> A & Mask1 == Mask2, where Mask2 only has bit C set
3640 // and Mask1 has bits 0..C+1 set. Similar for ctl, but for high bits.
3641 // Limit to one use to ensure we don't increase instruction count.
3642 unsigned Num = C.getLimitedValue(BitWidth);
3643 if (Num != BitWidth && II->hasOneUse()) {
3644 bool IsTrailing = II->getIntrinsicID() == Intrinsic::cttz;
3645 APInt Mask1 = IsTrailing ? APInt::getLowBitsSet(BitWidth, Num + 1)
3646 : APInt::getHighBitsSet(BitWidth, Num + 1);
3647 APInt Mask2 = IsTrailing
3650 return new ICmpInst(Pred, Builder.CreateAnd(II->getArgOperand(0), Mask1),
3651 ConstantInt::get(Ty, Mask2));
3652 }
3653 break;
3654 }
3655
3656 case Intrinsic::ctpop: {
3657 // popcount(A) == 0 -> A == 0 and likewise for !=
3658 // popcount(A) == bitwidth(A) -> A == -1 and likewise for !=
3659 bool IsZero = C.isZero();
3660 if (IsZero || C == BitWidth)
3661 return new ICmpInst(Pred, II->getArgOperand(0),
3662 IsZero ? Constant::getNullValue(Ty)
3664
3665 break;
3666 }
3667
3668 case Intrinsic::fshl:
3669 case Intrinsic::fshr:
3670 if (II->getArgOperand(0) == II->getArgOperand(1)) {
3671 const APInt *RotAmtC;
3672 // ror(X, RotAmtC) == C --> X == rol(C, RotAmtC)
3673 // rol(X, RotAmtC) == C --> X == ror(C, RotAmtC)
3674 if (match(II->getArgOperand(2), m_APInt(RotAmtC)))
3675 return new ICmpInst(Pred, II->getArgOperand(0),
3676 II->getIntrinsicID() == Intrinsic::fshl
3677 ? ConstantInt::get(Ty, C.rotr(*RotAmtC))
3678 : ConstantInt::get(Ty, C.rotl(*RotAmtC)));
3679 }
3680 break;
3681
3682 case Intrinsic::umax:
3683 case Intrinsic::uadd_sat: {
3684 // uadd.sat(a, b) == 0 -> (a | b) == 0
3685 // umax(a, b) == 0 -> (a | b) == 0
3686 if (C.isZero() && II->hasOneUse()) {
3687 Value *Or = Builder.CreateOr(II->getArgOperand(0), II->getArgOperand(1));
3688 return new ICmpInst(Pred, Or, Constant::getNullValue(Ty));
3689 }
3690 break;
3691 }
3692
3693 case Intrinsic::ssub_sat:
3694 // ssub.sat(a, b) == 0 -> a == b
3695 if (C.isZero())
3696 return new ICmpInst(Pred, II->getArgOperand(0), II->getArgOperand(1));
3697 break;
3698 case Intrinsic::usub_sat: {
3699 // usub.sat(a, b) == 0 -> a <= b
3700 if (C.isZero()) {
3701 ICmpInst::Predicate NewPred =
3703 return new ICmpInst(NewPred, II->getArgOperand(0), II->getArgOperand(1));
3704 }
3705 break;
3706 }
3707 default:
3708 break;
3709 }
3710
3711 return nullptr;
3712}
3713
3714/// Fold an icmp with LLVM intrinsics
3715static Instruction *
3717 InstCombiner::BuilderTy &Builder) {
3718 assert(Cmp.isEquality());
3719
3720 ICmpInst::Predicate Pred = Cmp.getPredicate();
3721 Value *Op0 = Cmp.getOperand(0);
3722 Value *Op1 = Cmp.getOperand(1);
3723 const auto *IIOp0 = dyn_cast<IntrinsicInst>(Op0);
3724 const auto *IIOp1 = dyn_cast<IntrinsicInst>(Op1);
3725 if (!IIOp0 || !IIOp1 || IIOp0->getIntrinsicID() != IIOp1->getIntrinsicID())
3726 return nullptr;
3727
3728 switch (IIOp0->getIntrinsicID()) {
3729 case Intrinsic::bswap:
3730 case Intrinsic::bitreverse:
3731 // If both operands are byte-swapped or bit-reversed, just compare the
3732 // original values.
3733 return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
3734 case Intrinsic::fshl:
3735 case Intrinsic::fshr: {
3736 // If both operands are rotated by same amount, just compare the
3737 // original values.
3738 if (IIOp0->getOperand(0) != IIOp0->getOperand(1))
3739 break;
3740 if (IIOp1->getOperand(0) != IIOp1->getOperand(1))
3741 break;
3742 if (IIOp0->getOperand(2) == IIOp1->getOperand(2))
3743 return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
3744
3745 // rotate(X, AmtX) == rotate(Y, AmtY)
3746 // -> rotate(X, AmtX - AmtY) == Y
3747 // Do this if either both rotates have one use or if only one has one use
3748 // and AmtX/AmtY are constants.
3749 unsigned OneUses = IIOp0->hasOneUse() + IIOp1->hasOneUse();
3750 if (OneUses == 2 ||
3751 (OneUses == 1 && match(IIOp0->getOperand(2), m_ImmConstant()) &&
3752 match(IIOp1->getOperand(2), m_ImmConstant()))) {
3753 Value *SubAmt =
3754 Builder.CreateSub(IIOp0->getOperand(2), IIOp1->getOperand(2));
3755 Value *CombinedRotate = Builder.CreateIntrinsic(
3756 Op0->getType(), IIOp0->getIntrinsicID(),
3757 {IIOp0->getOperand(0), IIOp0->getOperand(0), SubAmt});
3758 return new ICmpInst(Pred, IIOp1->getOperand(0), CombinedRotate);
3759 }
3760 } break;
3761 default:
3762 break;
3763 }
3764
3765 return nullptr;
3766}
3767
3768/// Try to fold integer comparisons with a constant operand: icmp Pred X, C
3769/// where X is some kind of instruction and C is AllowPoison.
3770/// TODO: Move more folds which allow poison to this function.
3773 const APInt &C) {
3774 const ICmpInst::Predicate Pred = Cmp.getPredicate();
3775 if (auto *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0))) {
3776 switch (II->getIntrinsicID()) {
3777 default:
3778 break;
3779 case Intrinsic::fshl:
3780 case Intrinsic::fshr:
3781 if (Cmp.isEquality() && II->getArgOperand(0) == II->getArgOperand(1)) {
3782 // (rot X, ?) == 0/-1 --> X == 0/-1
3783 if (C.isZero() || C.isAllOnes())
3784 return new ICmpInst(Pred, II->getArgOperand(0), Cmp.getOperand(1));
3785 }
3786 break;
3787 }
3788 }
3789
3790 return nullptr;
3791}
3792
3793/// Fold an icmp with BinaryOp and constant operand: icmp Pred BO, C.
3795 BinaryOperator *BO,
3796 const APInt &C) {
3797 switch (BO->getOpcode()) {
3798 case Instruction::Xor:
3799 if (Instruction *I = foldICmpXorConstant(Cmp, BO, C))
3800 return I;
3801 break;
3802 case Instruction::And:
3803 if (Instruction *I = foldICmpAndConstant(Cmp, BO, C))
3804 return I;
3805 break;
3806 case Instruction::Or:
3807 if (Instruction *I = foldICmpOrConstant(Cmp, BO, C))
3808 return I;
3809 break;
3810 case Instruction::Mul:
3811 if (Instruction *I = foldICmpMulConstant(Cmp, BO, C))
3812 return I;
3813 break;
3814 case Instruction::Shl:
3815 if (Instruction *I = foldICmpShlConstant(Cmp, BO, C))
3816 return I;
3817 break;
3818 case Instruction::LShr:
3819 case Instruction::AShr:
3820 if (Instruction *I = foldICmpShrConstant(Cmp, BO, C))
3821 return I;
3822 break;
3823 case Instruction::SRem:
3824 if (Instruction *I = foldICmpSRemConstant(Cmp, BO, C))
3825 return I;
3826 break;
3827 case Instruction::UDiv:
3828 if (Instruction *I = foldICmpUDivConstant(Cmp, BO, C))
3829 return I;
3830 [[fallthrough]];
3831 case Instruction::SDiv:
3832 if (Instruction *I = foldICmpDivConstant(Cmp, BO, C))
3833 return I;
3834 break;
3835 case Instruction::Sub:
3836 if (Instruction *I = foldICmpSubConstant(Cmp, BO, C))
3837 return I;
3838 break;
3839 case Instruction::Add:
3840 if (Instruction *I = foldICmpAddConstant(Cmp, BO, C))
3841 return I;
3842 break;
3843 default:
3844 break;
3845 }
3846
3847 // TODO: These folds could be refactored to be part of the above calls.
3848 return foldICmpBinOpEqualityWithConstant(Cmp, BO, C);
3849}
3850
3851static Instruction *
3853 SaturatingInst *II, const APInt &C,
3854 InstCombiner::BuilderTy &Builder) {
3855 // This transform may end up producing more than one instruction for the
3856 // intrinsic, so limit it to one user of the intrinsic.
3857 if (!II->hasOneUse())
3858 return nullptr;
3859
3860 // Let Y = [add/sub]_sat(X, C) pred C2
3861 // SatVal = The saturating value for the operation
3862 // WillWrap = Whether or not the operation will underflow / overflow
3863 // => Y = (WillWrap ? SatVal : (X binop C)) pred C2
3864 // => Y = WillWrap ? (SatVal pred C2) : ((X binop C) pred C2)
3865 //
3866 // When (SatVal pred C2) is true, then
3867 // Y = WillWrap ? true : ((X binop C) pred C2)
3868 // => Y = WillWrap || ((X binop C) pred C2)
3869 // else
3870 // Y = WillWrap ? false : ((X binop C) pred C2)
3871 // => Y = !WillWrap ? ((X binop C) pred C2) : false
3872 // => Y = !WillWrap && ((X binop C) pred C2)
3873 Value *Op0 = II->getOperand(0);
3874 Value *Op1 = II->getOperand(1);
3875
3876 const APInt *COp1;
3877 // This transform only works when the intrinsic has an integral constant or
3878 // splat vector as the second operand.
3879 if (!match(Op1, m_APInt(COp1)))
3880 return nullptr;
3881
3882 APInt SatVal;
3883 switch (II->getIntrinsicID()) {
3884 default:
3886 "This function only works with usub_sat and uadd_sat for now!");
3887 case Intrinsic::uadd_sat:
3888 SatVal = APInt::getAllOnes(C.getBitWidth());
3889 break;
3890 case Intrinsic::usub_sat:
3891 SatVal = APInt::getZero(C.getBitWidth());
3892 break;
3893 }
3894
3895 // Check (SatVal pred C2)
3896 bool SatValCheck = ICmpInst::compare(SatVal, C, Pred);
3897
3898 // !WillWrap.
3900 II->getBinaryOp(), *COp1, II->getNoWrapKind());
3901
3902 // WillWrap.
3903 if (SatValCheck)
3904 C1 = C1.inverse();
3905
3907 if (II->getBinaryOp() == Instruction::Add)
3908 C2 = C2.sub(*COp1);
3909 else
3910 C2 = C2.add(*COp1);
3911
3912 Instruction::BinaryOps CombiningOp =
3913 SatValCheck ? Instruction::BinaryOps::Or : Instruction::BinaryOps::And;
3914
3915 std::optional<ConstantRange> Combination;
3916 if (CombiningOp == Instruction::BinaryOps::Or)
3917 Combination = C1.exactUnionWith(C2);
3918 else /* CombiningOp == Instruction::BinaryOps::And */
3919 Combination = C1.exactIntersectWith(C2);
3920
3921 if (!Combination)
3922 return nullptr;
3923
3924 CmpInst::Predicate EquivPred;
3925 APInt EquivInt;
3926 APInt EquivOffset;
3927
3928 Combination->getEquivalentICmp(EquivPred, EquivInt, EquivOffset);
3929
3930 return new ICmpInst(
3931 EquivPred,
3932 Builder.CreateAdd(Op0, ConstantInt::get(Op1->getType(), EquivOffset)),
3933 ConstantInt::get(Op1->getType(), EquivInt));
3934}
3935
3936static Instruction *
3938 const APInt &C,
3939 InstCombiner::BuilderTy &Builder) {
3940 std::optional<ICmpInst::Predicate> NewPredicate = std::nullopt;
3941 switch (Pred) {
3942 case ICmpInst::ICMP_EQ:
3943 case ICmpInst::ICMP_NE:
3944 if (C.isZero())
3945 NewPredicate = Pred;
3946 else if (C.isOne())
3947 NewPredicate =
3949 else if (C.isAllOnes())
3950 NewPredicate =
3952 break;
3953
3954 case ICmpInst::ICMP_SGT:
3955 if (C.isAllOnes())
3956 NewPredicate = ICmpInst::ICMP_UGE;
3957 else if (C.isZero())
3958 NewPredicate = ICmpInst::ICMP_UGT;
3959 break;
3960
3961 case ICmpInst::ICMP_SLT:
3962 if (C.isZero())
3963 NewPredicate = ICmpInst::ICMP_ULT;
3964 else if (C.isOne())
3965 NewPredicate = ICmpInst::ICMP_ULE;
3966 break;
3967
3968 default:
3969 break;
3970 }
3971
3972 if (!NewPredicate)
3973 return nullptr;
3974
3975 if (I->getIntrinsicID() == Intrinsic::scmp)
3976 NewPredicate = ICmpInst::getSignedPredicate(*NewPredicate);
3977 Value *LHS = I->getOperand(0);
3978 Value *RHS = I->getOperand(1);
3979 return new ICmpInst(*NewPredicate, LHS, RHS);
3980}
3981
3982/// Fold an icmp with LLVM intrinsic and constant operand: icmp Pred II, C.
3985 const APInt &C) {
3986 ICmpInst::Predicate Pred = Cmp.getPredicate();
3987
3988 // Handle folds that apply for any kind of icmp.
3989 switch (II->getIntrinsicID()) {
3990 default:
3991 break;
3992 case Intrinsic::uadd_sat:
3993 case Intrinsic::usub_sat:
3994 if (auto *Folded = foldICmpUSubSatOrUAddSatWithConstant(
3995 Pred, cast<SaturatingInst>(II), C, Builder))
3996 return Folded;
3997 break;
3998 case Intrinsic::ctpop: {
3999 const SimplifyQuery Q = SQ.getWithInstruction(&Cmp);
4000 if (Instruction *R = foldCtpopPow2Test(Cmp, II, C, Builder, Q))
4001 return R;
4002 } break;
4003 case Intrinsic::scmp:
4004 case Intrinsic::ucmp:
4005 if (auto *Folded = foldICmpOfCmpIntrinsicWithConstant(Pred, II, C, Builder))
4006 return Folded;
4007 break;
4008 }
4009
4010 if (Cmp.isEquality())
4011 return foldICmpEqIntrinsicWithConstant(Cmp, II, C);
4012
4013 Type *Ty = II->getType();
4014 unsigned BitWidth = C.getBitWidth();
4015 switch (II->getIntrinsicID()) {
4016 case Intrinsic::ctpop: {
4017 // (ctpop X > BitWidth - 1) --> X == -1
4018 Value *X = II->getArgOperand(0);
4019 if (C == BitWidth - 1 && Pred == ICmpInst::ICMP_UGT)
4020 return CmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_EQ, X,
4022 // (ctpop X < BitWidth) --> X != -1
4023 if (C == BitWidth && Pred == ICmpInst::ICMP_ULT)
4024 return CmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_NE, X,
4026 break;
4027 }
4028 case Intrinsic::ctlz: {
4029 // ctlz(0bXXXXXXXX) > 3 -> 0bXXXXXXXX < 0b00010000
4030 if (Pred == ICmpInst::ICMP_UGT && C.ult(BitWidth)) {
4031 unsigned Num = C.getLimitedValue();
4032 APInt Limit = APInt::getOneBitSet(BitWidth, BitWidth - Num - 1);
4033 return CmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_ULT,
4034 II->getArgOperand(0), ConstantInt::get(Ty, Limit));
4035 }
4036
4037 // ctlz(0bXXXXXXXX) < 3 -> 0bXXXXXXXX > 0b00011111
4038 if (Pred == ICmpInst::ICMP_ULT && C.uge(1) && C.ule(BitWidth)) {
4039 unsigned Num = C.getLimitedValue();
4041 return CmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_UGT,
4042 II->getArgOperand(0), ConstantInt::get(Ty, Limit));
4043 }
4044 break;
4045 }
4046 case Intrinsic::cttz: {
4047 // Limit to one use to ensure we don't increase instruction count.
4048 if (!II->hasOneUse())
4049 return nullptr;
4050
4051 // cttz(0bXXXXXXXX) > 3 -> 0bXXXXXXXX & 0b00001111 == 0
4052 if (Pred == ICmpInst::ICMP_UGT && C.ult(BitWidth)) {
4053 APInt Mask = APInt::getLowBitsSet(BitWidth, C.getLimitedValue() + 1);
4054 return CmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_EQ,
4055 Builder.CreateAnd(II->getArgOperand(0), Mask),
4057 }
4058
4059 // cttz(0bXXXXXXXX) < 3 -> 0bXXXXXXXX & 0b00000111 != 0
4060 if (Pred == ICmpInst::ICMP_ULT && C.uge(1) && C.ule(BitWidth)) {
4061 APInt Mask = APInt::getLowBitsSet(BitWidth, C.getLimitedValue());
4062 return CmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_NE,
4063 Builder.CreateAnd(II->getArgOperand(0), Mask),
4065 }
4066 break;
4067 }
4068 case Intrinsic::ssub_sat:
4069 // ssub.sat(a, b) spred 0 -> a spred b
4070 if (ICmpInst::isSigned(Pred)) {
4071 if (C.isZero())
4072 return new ICmpInst(Pred, II->getArgOperand(0), II->getArgOperand(1));
4073 // X s<= 0 is cannonicalized to X s< 1
4074 if (Pred == ICmpInst::ICMP_SLT && C.isOne())
4075 return new ICmpInst(ICmpInst::ICMP_SLE, II->getArgOperand(0),
4076 II->getArgOperand(1));
4077 // X s>= 0 is cannonicalized to X s> -1
4078 if (Pred == ICmpInst::ICMP_SGT && C.isAllOnes())
4079 return new ICmpInst(ICmpInst::ICMP_SGE, II->getArgOperand(0),
4080 II->getArgOperand(1));
4081 }
4082 break;
4083 default:
4084 break;
4085 }
4086
4087 return nullptr;
4088}
4089
4090/// Handle icmp with constant (but not simple integer constant) RHS.
4092 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
4093 Constant *RHSC = dyn_cast<Constant>(Op1);
4094 Instruction *LHSI = dyn_cast<Instruction>(Op0);
4095 if (!RHSC || !LHSI)
4096 return nullptr;
4097
4098 switch (LHSI->getOpcode()) {
4099 case Instruction::PHI:
4100 if (Instruction *NV = foldOpIntoPhi(I, cast<PHINode>(LHSI)))
4101 return NV;
4102 break;
4103 case Instruction::IntToPtr:
4104 // icmp pred inttoptr(X), null -> icmp pred X, 0
4105 if (RHSC->isNullValue() &&
4106 DL.getIntPtrType(RHSC->getType()) == LHSI->getOperand(0)->getType())
4107 return new ICmpInst(
4108 I.getPredicate(), LHSI->getOperand(0),
4110 break;
4111
4112 case Instruction::Load:
4113 // Try to optimize things like "A[i] > 4" to index computations.
4114 if (GetElementPtrInst *GEP =
4115 dyn_cast<GetElementPtrInst>(LHSI->getOperand(0)))
4116 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)))
4117 if (Instruction *Res =
4118 foldCmpLoadFromIndexedGlobal(cast<LoadInst>(LHSI), GEP, GV, I))
4119 return Res;
4120 break;
4121 }
4122
4123 return nullptr;
4124}
4125
4127 SelectInst *SI, Value *RHS,
4128 const ICmpInst &I) {
4129 // Try to fold the comparison into the select arms, which will cause the
4130 // select to be converted into a logical and/or.
4131 auto SimplifyOp = [&](Value *Op, bool SelectCondIsTrue) -> Value * {
4132 if (Value *Res = simplifyICmpInst(Pred, Op, RHS, SQ))
4133 return Res;
4134 if (std::optional<bool> Impl = isImpliedCondition(
4135 SI->getCondition(), Pred, Op, RHS, DL, SelectCondIsTrue))
4136 return ConstantInt::get(I.getType(), *Impl);
4137 return nullptr;
4138 };
4139
4140 ConstantInt *CI = nullptr;
4141 Value *Op1 = SimplifyOp(SI->getOperand(1), true);
4142 if (Op1)
4143 CI = dyn_cast<ConstantInt>(Op1);
4144
4145 Value *Op2 = SimplifyOp(SI->getOperand(2), false);
4146 if (Op2)
4147 CI = dyn_cast<ConstantInt>(Op2);
4148
4149 // We only want to perform this transformation if it will not lead to
4150 // additional code. This is true if either both sides of the select
4151 // fold to a constant (in which case the icmp is replaced with a select
4152 // which will usually simplify) or this is the only user of the
4153 // select (in which case we are trading a select+icmp for a simpler
4154 // select+icmp) or all uses of the select can be replaced based on
4155 // dominance information ("Global cases").
4156 bool Transform = false;
4157 if (Op1 && Op2)
4158 Transform = true;
4159 else if (Op1 || Op2) {
4160 // Local case
4161 if (SI->hasOneUse())
4162 Transform = true;
4163 // Global cases
4164 else if (CI && !CI->isZero())
4165 // When Op1 is constant try replacing select with second operand.
4166 // Otherwise Op2 is constant and try replacing select with first
4167 // operand.
4168 Transform = replacedSelectWithOperand(SI, &I, Op1 ? 2 : 1);
4169 }
4170 if (Transform) {
4171 if (!Op1)
4172 Op1 = Builder.CreateICmp(Pred, SI->getOperand(1), RHS, I.getName());
4173 if (!Op2)
4174 Op2 = Builder.CreateICmp(Pred, SI->getOperand(2), RHS, I.getName());
4175 return SelectInst::Create(SI->getOperand(0), Op1, Op2);
4176 }
4177
4178 return nullptr;
4179}
4180
4181// Returns whether V is a Mask ((X + 1) & X == 0) or ~Mask (-Pow2OrZero)
4182static bool isMaskOrZero(const Value *V, bool Not, const SimplifyQuery &Q,
4183 unsigned Depth = 0) {
4184 if (Not ? match(V, m_NegatedPower2OrZero()) : match(V, m_LowBitMaskOrZero()))
4185 return true;
4186 if (V->getType()->getScalarSizeInBits() == 1)
4187 return true;
4189 return false;
4190 Value *X;
4191 const Instruction *I = dyn_cast<Instruction>(V);
4192 if (!I)
4193 return false;
4194 switch (I->getOpcode()) {
4195 case Instruction::ZExt:
4196 // ZExt(Mask) is a Mask.
4197 return !Not && isMaskOrZero(I->getOperand(0), Not, Q, Depth);
4198 case Instruction::SExt:
4199 // SExt(Mask) is a Mask.
4200 // SExt(~Mask) is a ~Mask.
4201 return isMaskOrZero(I->getOperand(0), Not, Q, Depth);
4202 case Instruction::And:
4203 case Instruction::Or:
4204 // Mask0 | Mask1 is a Mask.
4205 // Mask0 & Mask1 is a Mask.
4206 // ~Mask0 | ~Mask1 is a ~Mask.
4207 // ~Mask0 & ~Mask1 is a ~Mask.
4208 return isMaskOrZero(I->getOperand(1), Not, Q, Depth) &&
4209 isMaskOrZero(I->getOperand(0), Not, Q, Depth);
4210 case Instruction::Xor:
4211 if (match(V, m_Not(m_Value(X))))
4212 return isMaskOrZero(X, !Not, Q, Depth);
4213
4214 // (X ^ -X) is a ~Mask
4215 if (Not)
4216 return match(V, m_c_Xor(m_Value(X), m_Neg(m_Deferred(X))));
4217 // (X ^ (X - 1)) is a Mask
4218 else
4219 return match(V, m_c_Xor(m_Value(X), m_Add(m_Deferred(X), m_AllOnes())));
4220 case Instruction::Select:
4221 // c ? Mask0 : Mask1 is a Mask.
4222 return isMaskOrZero(I->getOperand(1), Not, Q, Depth) &&
4223 isMaskOrZero(I->getOperand(2), Not, Q, Depth);
4224 case Instruction::Shl:
4225 // (~Mask) << X is a ~Mask.
4226 return Not && isMaskOrZero(I->getOperand(0), Not, Q, Depth);
4227 case Instruction::LShr:
4228 // Mask >> X is a Mask.
4229 return !Not && isMaskOrZero(I->getOperand(0), Not, Q, Depth);
4230 case Instruction::AShr:
4231 // Mask s>> X is a Mask.
4232 // ~Mask s>> X is a ~Mask.
4233 return isMaskOrZero(I->getOperand(0), Not, Q, Depth);
4234 case Instruction::Add:
4235 // Pow2 - 1 is a Mask.
4236 if (!Not && match(I->getOperand(1), m_AllOnes()))
4237 return isKnownToBeAPowerOfTwo(I->getOperand(0), Q.DL, /*OrZero*/ true,
4238 Depth, Q.AC, Q.CxtI, Q.DT);
4239 break;
4240 case Instruction::Sub:
4241 // -Pow2 is a ~Mask.
4242 if (Not && match(I->getOperand(0), m_Zero()))
4243 return isKnownToBeAPowerOfTwo(I->getOperand(1), Q.DL, /*OrZero*/ true,
4244 Depth, Q.AC, Q.CxtI, Q.DT);
4245 break;
4246 case Instruction::Call: {
4247 if (auto *II = dyn_cast<IntrinsicInst>(I)) {
4248 switch (II->getIntrinsicID()) {
4249 // min/max(Mask0, Mask1) is a Mask.
4250 // min/max(~Mask0, ~Mask1) is a ~Mask.
4251 case Intrinsic::umax:
4252 case Intrinsic::smax:
4253 case Intrinsic::umin:
4254 case Intrinsic::smin:
4255 return isMaskOrZero(II->getArgOperand(1), Not, Q, Depth) &&
4256 isMaskOrZero(II->getArgOperand(0), Not, Q, Depth);
4257
4258 // In the context of masks, bitreverse(Mask) == ~Mask
4259 case Intrinsic::bitreverse:
4260 return isMaskOrZero(II->getArgOperand(0), !Not, Q, Depth);
4261 default:
4262 break;
4263 }
4264 }
4265 break;
4266 }
4267 default:
4268 break;
4269 }
4270 return false;
4271}
4272
4273/// Some comparisons can be simplified.
4274/// In this case, we are looking for comparisons that look like
4275/// a check for a lossy truncation.
4276/// Folds:
4277/// icmp SrcPred (x & Mask), x to icmp DstPred x, Mask
4278/// icmp SrcPred (x & ~Mask), ~Mask to icmp DstPred x, ~Mask
4279/// icmp eq/ne (x & ~Mask), 0 to icmp DstPred x, Mask
4280/// icmp eq/ne (~x | Mask), -1 to icmp DstPred x, Mask
<