1
//===- InstCombineCompares.cpp --------------------------------------------===//
3
// The LLVM Compiler Infrastructure
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
8
//===----------------------------------------------------------------------===//
10
// This file implements the visitICmp and visitFCmp functions.
12
//===----------------------------------------------------------------------===//
14
#include "InstCombine.h"
15
#include "llvm/IntrinsicInst.h"
16
#include "llvm/Analysis/InstructionSimplify.h"
17
#include "llvm/Analysis/MemoryBuiltins.h"
18
#include "llvm/Target/TargetData.h"
19
#include "llvm/Support/ConstantRange.h"
20
#include "llvm/Support/GetElementPtrTypeIterator.h"
21
#include "llvm/Support/PatternMatch.h"
23
using namespace PatternMatch;
25
/// AddOne - Add one to a ConstantInt
26
static Constant *AddOne(Constant *C) {
27
return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
29
/// SubOne - Subtract one from a ConstantInt
30
static Constant *SubOne(ConstantInt *C) {
31
return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1));
34
static ConstantInt *ExtractElement(Constant *V, Constant *Idx) {
35
return cast<ConstantInt>(ConstantExpr::getExtractElement(V, Idx));
38
static bool HasAddOverflow(ConstantInt *Result,
39
ConstantInt *In1, ConstantInt *In2,
42
if (In2->getValue().isNegative())
43
return Result->getValue().sgt(In1->getValue());
45
return Result->getValue().slt(In1->getValue());
47
return Result->getValue().ult(In1->getValue());
50
/// AddWithOverflow - Compute Result = In1+In2, returning true if the result
51
/// overflowed for this type.
52
static bool AddWithOverflow(Constant *&Result, Constant *In1,
53
Constant *In2, bool IsSigned = false) {
54
Result = ConstantExpr::getAdd(In1, In2);
56
if (const VectorType *VTy = dyn_cast<VectorType>(In1->getType())) {
57
for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
58
Constant *Idx = ConstantInt::get(Type::getInt32Ty(In1->getContext()), i);
59
if (HasAddOverflow(ExtractElement(Result, Idx),
60
ExtractElement(In1, Idx),
61
ExtractElement(In2, Idx),
68
return HasAddOverflow(cast<ConstantInt>(Result),
69
cast<ConstantInt>(In1), cast<ConstantInt>(In2),
73
static bool HasSubOverflow(ConstantInt *Result,
74
ConstantInt *In1, ConstantInt *In2,
77
if (In2->getValue().isNegative())
78
return Result->getValue().slt(In1->getValue());
80
return Result->getValue().sgt(In1->getValue());
82
return Result->getValue().ugt(In1->getValue());
85
/// SubWithOverflow - Compute Result = In1-In2, returning true if the result
86
/// overflowed for this type.
87
static bool SubWithOverflow(Constant *&Result, Constant *In1,
88
Constant *In2, bool IsSigned = false) {
89
Result = ConstantExpr::getSub(In1, In2);
91
if (const VectorType *VTy = dyn_cast<VectorType>(In1->getType())) {
92
for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
93
Constant *Idx = ConstantInt::get(Type::getInt32Ty(In1->getContext()), i);
94
if (HasSubOverflow(ExtractElement(Result, Idx),
95
ExtractElement(In1, Idx),
96
ExtractElement(In2, Idx),
103
return HasSubOverflow(cast<ConstantInt>(Result),
104
cast<ConstantInt>(In1), cast<ConstantInt>(In2),
108
/// isSignBitCheck - Given an exploded icmp instruction, return true if the
109
/// comparison only checks the sign bit. If it only checks the sign bit, set
110
/// TrueIfSigned if the result of the comparison is true when the input value is
112
static bool isSignBitCheck(ICmpInst::Predicate pred, ConstantInt *RHS,
113
bool &TrueIfSigned) {
115
case ICmpInst::ICMP_SLT: // True if LHS s< 0
117
return RHS->isZero();
118
case ICmpInst::ICMP_SLE: // True if LHS s<= RHS and RHS == -1
120
return RHS->isAllOnesValue();
121
case ICmpInst::ICMP_SGT: // True if LHS s> -1
122
TrueIfSigned = false;
123
return RHS->isAllOnesValue();
124
case ICmpInst::ICMP_UGT:
125
// True if LHS u> RHS and RHS == high-bit-mask - 1
127
return RHS->getValue() ==
128
APInt::getSignedMaxValue(RHS->getType()->getPrimitiveSizeInBits());
129
case ICmpInst::ICMP_UGE:
130
// True if LHS u>= RHS and RHS == high-bit-mask (2^7, 2^15, 2^31, etc)
132
return RHS->getValue().isSignBit();
138
// isHighOnes - Return true if the constant is of the form 1+0+.
139
// This is the same as lowones(~X).
140
static bool isHighOnes(const ConstantInt *CI) {
141
return (~CI->getValue() + 1).isPowerOf2();
144
/// ComputeSignedMinMaxValuesFromKnownBits - Given a signed integer type and a
145
/// set of known zero and one bits, compute the maximum and minimum values that
146
/// could have the specified known zero and known one bits, returning them in
148
static void ComputeSignedMinMaxValuesFromKnownBits(const APInt& KnownZero,
149
const APInt& KnownOne,
150
APInt& Min, APInt& Max) {
151
assert(KnownZero.getBitWidth() == KnownOne.getBitWidth() &&
152
KnownZero.getBitWidth() == Min.getBitWidth() &&
153
KnownZero.getBitWidth() == Max.getBitWidth() &&
154
"KnownZero, KnownOne and Min, Max must have equal bitwidth.");
155
APInt UnknownBits = ~(KnownZero|KnownOne);
157
// The minimum value is when all unknown bits are zeros, EXCEPT for the sign
158
// bit if it is unknown.
160
Max = KnownOne|UnknownBits;
162
if (UnknownBits.isNegative()) { // Sign bit is unknown
163
Min.set(Min.getBitWidth()-1);
164
Max.clear(Max.getBitWidth()-1);
168
// ComputeUnsignedMinMaxValuesFromKnownBits - Given an unsigned integer type and
169
// a set of known zero and one bits, compute the maximum and minimum values that
170
// could have the specified known zero and known one bits, returning them in
172
static void ComputeUnsignedMinMaxValuesFromKnownBits(const APInt &KnownZero,
173
const APInt &KnownOne,
174
APInt &Min, APInt &Max) {
175
assert(KnownZero.getBitWidth() == KnownOne.getBitWidth() &&
176
KnownZero.getBitWidth() == Min.getBitWidth() &&
177
KnownZero.getBitWidth() == Max.getBitWidth() &&
178
"Ty, KnownZero, KnownOne and Min, Max must have equal bitwidth.");
179
APInt UnknownBits = ~(KnownZero|KnownOne);
181
// The minimum value is when the unknown bits are all zeros.
183
// The maximum value is when the unknown bits are all ones.
184
Max = KnownOne|UnknownBits;
189
/// FoldCmpLoadFromIndexedGlobal - Called we see this pattern:
190
/// cmp pred (load (gep GV, ...)), cmpcst
191
/// where GV is a global variable with a constant initializer. Try to simplify
192
/// this into some simple computation that does not need the load. For example
193
/// we can optimize "icmp eq (load (gep "foo", 0, i)), 0" into "icmp eq i, 3".
195
/// If AndCst is non-null, then the loaded value is masked with that constant
196
/// before doing the comparison. This handles cases like "A[i]&4 == 0".
197
Instruction *InstCombiner::
198
FoldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP, GlobalVariable *GV,
199
CmpInst &ICI, ConstantInt *AndCst) {
200
// We need TD information to know the pointer size unless this is inbounds.
201
if (!GEP->isInBounds() && TD == 0) return 0;
203
ConstantArray *Init = dyn_cast<ConstantArray>(GV->getInitializer());
204
if (Init == 0 || Init->getNumOperands() > 1024) return 0;
206
// There are many forms of this optimization we can handle, for now, just do
207
// the simple index into a single-dimensional array.
209
// Require: GEP GV, 0, i {{, constant indices}}
210
if (GEP->getNumOperands() < 3 ||
211
!isa<ConstantInt>(GEP->getOperand(1)) ||
212
!cast<ConstantInt>(GEP->getOperand(1))->isZero() ||
213
isa<Constant>(GEP->getOperand(2)))
216
// Check that indices after the variable are constants and in-range for the
217
// type they index. Collect the indices. This is typically for arrays of
219
SmallVector<unsigned, 4> LaterIndices;
221
const Type *EltTy = cast<ArrayType>(Init->getType())->getElementType();
222
for (unsigned i = 3, e = GEP->getNumOperands(); i != e; ++i) {
223
ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(i));
224
if (Idx == 0) return 0; // Variable index.
226
uint64_t IdxVal = Idx->getZExtValue();
227
if ((unsigned)IdxVal != IdxVal) return 0; // Too large array index.
229
if (const StructType *STy = dyn_cast<StructType>(EltTy))
230
EltTy = STy->getElementType(IdxVal);
231
else if (const ArrayType *ATy = dyn_cast<ArrayType>(EltTy)) {
232
if (IdxVal >= ATy->getNumElements()) return 0;
233
EltTy = ATy->getElementType();
235
return 0; // Unknown type.
238
LaterIndices.push_back(IdxVal);
241
enum { Overdefined = -3, Undefined = -2 };
243
// Variables for our state machines.
245
// FirstTrueElement/SecondTrueElement - Used to emit a comparison of the form
246
// "i == 47 | i == 87", where 47 is the first index the condition is true for,
247
// and 87 is the second (and last) index. FirstTrueElement is -2 when
248
// undefined, otherwise set to the first true element. SecondTrueElement is
249
// -2 when undefined, -3 when overdefined and >= 0 when that index is true.
250
int FirstTrueElement = Undefined, SecondTrueElement = Undefined;
252
// FirstFalseElement/SecondFalseElement - Used to emit a comparison of the
253
// form "i != 47 & i != 87". Same state transitions as for true elements.
254
int FirstFalseElement = Undefined, SecondFalseElement = Undefined;
256
/// TrueRangeEnd/FalseRangeEnd - In conjunction with First*Element, these
257
/// define a state machine that triggers for ranges of values that the index
258
/// is true or false for. This triggers on things like "abbbbc"[i] == 'b'.
259
/// This is -2 when undefined, -3 when overdefined, and otherwise the last
260
/// index in the range (inclusive). We use -2 for undefined here because we
261
/// use relative comparisons and don't want 0-1 to match -1.
262
int TrueRangeEnd = Undefined, FalseRangeEnd = Undefined;
264
// MagicBitvector - This is a magic bitvector where we set a bit if the
265
// comparison is true for element 'i'. If there are 64 elements or less in
266
// the array, this will fully represent all the comparison results.
267
uint64_t MagicBitvector = 0;
270
// Scan the array and see if one of our patterns matches.
271
Constant *CompareRHS = cast<Constant>(ICI.getOperand(1));
272
for (unsigned i = 0, e = Init->getNumOperands(); i != e; ++i) {
273
Constant *Elt = Init->getOperand(i);
275
// If this is indexing an array of structures, get the structure element.
276
if (!LaterIndices.empty())
277
Elt = ConstantExpr::getExtractValue(Elt, LaterIndices.data(),
278
LaterIndices.size());
280
// If the element is masked, handle it.
281
if (AndCst) Elt = ConstantExpr::getAnd(Elt, AndCst);
283
// Find out if the comparison would be true or false for the i'th element.
284
Constant *C = ConstantFoldCompareInstOperands(ICI.getPredicate(), Elt,
286
// If the result is undef for this element, ignore it.
287
if (isa<UndefValue>(C)) {
288
// Extend range state machines to cover this element in case there is an
289
// undef in the middle of the range.
290
if (TrueRangeEnd == (int)i-1)
292
if (FalseRangeEnd == (int)i-1)
297
// If we can't compute the result for any of the elements, we have to give
298
// up evaluating the entire conditional.
299
if (!isa<ConstantInt>(C)) return 0;
301
// Otherwise, we know if the comparison is true or false for this element,
302
// update our state machines.
303
bool IsTrueForElt = !cast<ConstantInt>(C)->isZero();
305
// State machine for single/double/range index comparison.
307
// Update the TrueElement state machine.
308
if (FirstTrueElement == Undefined)
309
FirstTrueElement = TrueRangeEnd = i; // First true element.
311
// Update double-compare state machine.
312
if (SecondTrueElement == Undefined)
313
SecondTrueElement = i;
315
SecondTrueElement = Overdefined;
317
// Update range state machine.
318
if (TrueRangeEnd == (int)i-1)
321
TrueRangeEnd = Overdefined;
324
// Update the FalseElement state machine.
325
if (FirstFalseElement == Undefined)
326
FirstFalseElement = FalseRangeEnd = i; // First false element.
328
// Update double-compare state machine.
329
if (SecondFalseElement == Undefined)
330
SecondFalseElement = i;
332
SecondFalseElement = Overdefined;
334
// Update range state machine.
335
if (FalseRangeEnd == (int)i-1)
338
FalseRangeEnd = Overdefined;
343
// If this element is in range, update our magic bitvector.
344
if (i < 64 && IsTrueForElt)
345
MagicBitvector |= 1ULL << i;
347
// If all of our states become overdefined, bail out early. Since the
348
// predicate is expensive, only check it every 8 elements. This is only
349
// really useful for really huge arrays.
350
if ((i & 8) == 0 && i >= 64 && SecondTrueElement == Overdefined &&
351
SecondFalseElement == Overdefined && TrueRangeEnd == Overdefined &&
352
FalseRangeEnd == Overdefined)
356
// Now that we've scanned the entire array, emit our new comparison(s). We
357
// order the state machines in complexity of the generated code.
358
Value *Idx = GEP->getOperand(2);
360
// If the index is larger than the pointer size of the target, truncate the
361
// index down like the GEP would do implicitly. We don't have to do this for
362
// an inbounds GEP because the index can't be out of range.
363
if (!GEP->isInBounds() &&
364
Idx->getType()->getPrimitiveSizeInBits() > TD->getPointerSizeInBits())
365
Idx = Builder->CreateTrunc(Idx, TD->getIntPtrType(Idx->getContext()));
367
// If the comparison is only true for one or two elements, emit direct
369
if (SecondTrueElement != Overdefined) {
370
// None true -> false.
371
if (FirstTrueElement == Undefined)
372
return ReplaceInstUsesWith(ICI, ConstantInt::getFalse(GEP->getContext()));
374
Value *FirstTrueIdx = ConstantInt::get(Idx->getType(), FirstTrueElement);
376
// True for one element -> 'i == 47'.
377
if (SecondTrueElement == Undefined)
378
return new ICmpInst(ICmpInst::ICMP_EQ, Idx, FirstTrueIdx);
380
// True for two elements -> 'i == 47 | i == 72'.
381
Value *C1 = Builder->CreateICmpEQ(Idx, FirstTrueIdx);
382
Value *SecondTrueIdx = ConstantInt::get(Idx->getType(), SecondTrueElement);
383
Value *C2 = Builder->CreateICmpEQ(Idx, SecondTrueIdx);
384
return BinaryOperator::CreateOr(C1, C2);
387
// If the comparison is only false for one or two elements, emit direct
389
if (SecondFalseElement != Overdefined) {
390
// None false -> true.
391
if (FirstFalseElement == Undefined)
392
return ReplaceInstUsesWith(ICI, ConstantInt::getTrue(GEP->getContext()));
394
Value *FirstFalseIdx = ConstantInt::get(Idx->getType(), FirstFalseElement);
396
// False for one element -> 'i != 47'.
397
if (SecondFalseElement == Undefined)
398
return new ICmpInst(ICmpInst::ICMP_NE, Idx, FirstFalseIdx);
400
// False for two elements -> 'i != 47 & i != 72'.
401
Value *C1 = Builder->CreateICmpNE(Idx, FirstFalseIdx);
402
Value *SecondFalseIdx = ConstantInt::get(Idx->getType(),SecondFalseElement);
403
Value *C2 = Builder->CreateICmpNE(Idx, SecondFalseIdx);
404
return BinaryOperator::CreateAnd(C1, C2);
407
// If the comparison can be replaced with a range comparison for the elements
408
// where it is true, emit the range check.
409
if (TrueRangeEnd != Overdefined) {
410
assert(TrueRangeEnd != FirstTrueElement && "Should emit single compare");
412
// Generate (i-FirstTrue) <u (TrueRangeEnd-FirstTrue+1).
413
if (FirstTrueElement) {
414
Value *Offs = ConstantInt::get(Idx->getType(), -FirstTrueElement);
415
Idx = Builder->CreateAdd(Idx, Offs);
418
Value *End = ConstantInt::get(Idx->getType(),
419
TrueRangeEnd-FirstTrueElement+1);
420
return new ICmpInst(ICmpInst::ICMP_ULT, Idx, End);
423
// False range check.
424
if (FalseRangeEnd != Overdefined) {
425
assert(FalseRangeEnd != FirstFalseElement && "Should emit single compare");
426
// Generate (i-FirstFalse) >u (FalseRangeEnd-FirstFalse).
427
if (FirstFalseElement) {
428
Value *Offs = ConstantInt::get(Idx->getType(), -FirstFalseElement);
429
Idx = Builder->CreateAdd(Idx, Offs);
432
Value *End = ConstantInt::get(Idx->getType(),
433
FalseRangeEnd-FirstFalseElement);
434
return new ICmpInst(ICmpInst::ICMP_UGT, Idx, End);
438
// If a 32-bit or 64-bit magic bitvector captures the entire comparison state
439
// of this load, replace it with computation that does:
440
// ((magic_cst >> i) & 1) != 0
441
if (Init->getNumOperands() <= 32 ||
442
(TD && Init->getNumOperands() <= 64 && TD->isLegalInteger(64))) {
444
if (Init->getNumOperands() <= 32)
445
Ty = Type::getInt32Ty(Init->getContext());
447
Ty = Type::getInt64Ty(Init->getContext());
448
Value *V = Builder->CreateIntCast(Idx, Ty, false);
449
V = Builder->CreateLShr(ConstantInt::get(Ty, MagicBitvector), V);
450
V = Builder->CreateAnd(ConstantInt::get(Ty, 1), V);
451
return new ICmpInst(ICmpInst::ICMP_NE, V, ConstantInt::get(Ty, 0));
458
/// EvaluateGEPOffsetExpression - Return a value that can be used to compare
459
/// the *offset* implied by a GEP to zero. For example, if we have &A[i], we
460
/// want to return 'i' for "icmp ne i, 0". Note that, in general, indices can
461
/// be complex, and scales are involved. The above expression would also be
462
/// legal to codegen as "icmp ne (i*4), 0" (assuming A is a pointer to i32).
463
/// This later form is less amenable to optimization though, and we are allowed
464
/// to generate the first by knowing that pointer arithmetic doesn't overflow.
466
/// If we can't emit an optimized form for this expression, this returns null.
468
static Value *EvaluateGEPOffsetExpression(User *GEP, Instruction &I,
470
TargetData &TD = *IC.getTargetData();
471
gep_type_iterator GTI = gep_type_begin(GEP);
473
// Check to see if this gep only has a single variable index. If so, and if
474
// any constant indices are a multiple of its scale, then we can compute this
475
// in terms of the scale of the variable index. For example, if the GEP
476
// implies an offset of "12 + i*4", then we can codegen this as "3 + i",
477
// because the expression will cross zero at the same point.
478
unsigned i, e = GEP->getNumOperands();
480
for (i = 1; i != e; ++i, ++GTI) {
481
if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) {
482
// Compute the aggregate offset of constant indices.
483
if (CI->isZero()) continue;
485
// Handle a struct index, which adds its field offset to the pointer.
486
if (const StructType *STy = dyn_cast<StructType>(*GTI)) {
487
Offset += TD.getStructLayout(STy)->getElementOffset(CI->getZExtValue());
489
uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType());
490
Offset += Size*CI->getSExtValue();
493
// Found our variable index.
498
// If there are no variable indices, we must have a constant offset, just
499
// evaluate it the general way.
500
if (i == e) return 0;
502
Value *VariableIdx = GEP->getOperand(i);
503
// Determine the scale factor of the variable element. For example, this is
504
// 4 if the variable index is into an array of i32.
505
uint64_t VariableScale = TD.getTypeAllocSize(GTI.getIndexedType());
507
// Verify that there are no other variable indices. If so, emit the hard way.
508
for (++i, ++GTI; i != e; ++i, ++GTI) {
509
ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i));
512
// Compute the aggregate offset of constant indices.
513
if (CI->isZero()) continue;
515
// Handle a struct index, which adds its field offset to the pointer.
516
if (const StructType *STy = dyn_cast<StructType>(*GTI)) {
517
Offset += TD.getStructLayout(STy)->getElementOffset(CI->getZExtValue());
519
uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType());
520
Offset += Size*CI->getSExtValue();
524
// Okay, we know we have a single variable index, which must be a
525
// pointer/array/vector index. If there is no offset, life is simple, return
527
unsigned IntPtrWidth = TD.getPointerSizeInBits();
529
// Cast to intptrty in case a truncation occurs. If an extension is needed,
530
// we don't need to bother extending: the extension won't affect where the
531
// computation crosses zero.
532
if (VariableIdx->getType()->getPrimitiveSizeInBits() > IntPtrWidth)
533
VariableIdx = new TruncInst(VariableIdx,
534
TD.getIntPtrType(VariableIdx->getContext()),
535
VariableIdx->getName(), &I);
539
// Otherwise, there is an index. The computation we will do will be modulo
540
// the pointer size, so get it.
541
uint64_t PtrSizeMask = ~0ULL >> (64-IntPtrWidth);
543
Offset &= PtrSizeMask;
544
VariableScale &= PtrSizeMask;
546
// To do this transformation, any constant index must be a multiple of the
547
// variable scale factor. For example, we can evaluate "12 + 4*i" as "3 + i",
548
// but we can't evaluate "10 + 3*i" in terms of i. Check that the offset is a
549
// multiple of the variable scale.
550
int64_t NewOffs = Offset / (int64_t)VariableScale;
551
if (Offset != NewOffs*(int64_t)VariableScale)
554
// Okay, we can do this evaluation. Start by converting the index to intptr.
555
const Type *IntPtrTy = TD.getIntPtrType(VariableIdx->getContext());
556
if (VariableIdx->getType() != IntPtrTy)
557
VariableIdx = CastInst::CreateIntegerCast(VariableIdx, IntPtrTy,
559
VariableIdx->getName(), &I);
560
Constant *OffsetVal = ConstantInt::get(IntPtrTy, NewOffs);
561
return BinaryOperator::CreateAdd(VariableIdx, OffsetVal, "offset", &I);
564
/// FoldGEPICmp - Fold comparisons between a GEP instruction and something
565
/// else. At this point we know that the GEP is on the LHS of the comparison.
566
Instruction *InstCombiner::FoldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
567
ICmpInst::Predicate Cond,
569
// Look through bitcasts.
570
if (BitCastInst *BCI = dyn_cast<BitCastInst>(RHS))
571
RHS = BCI->getOperand(0);
573
Value *PtrBase = GEPLHS->getOperand(0);
574
if (TD && PtrBase == RHS && GEPLHS->isInBounds()) {
575
// ((gep Ptr, OFFSET) cmp Ptr) ---> (OFFSET cmp 0).
576
// This transformation (ignoring the base and scales) is valid because we
577
// know pointers can't overflow since the gep is inbounds. See if we can
578
// output an optimized form.
579
Value *Offset = EvaluateGEPOffsetExpression(GEPLHS, I, *this);
581
// If not, synthesize the offset the hard way.
583
Offset = EmitGEPOffset(GEPLHS);
584
return new ICmpInst(ICmpInst::getSignedPredicate(Cond), Offset,
585
Constant::getNullValue(Offset->getType()));
586
} else if (GEPOperator *GEPRHS = dyn_cast<GEPOperator>(RHS)) {
587
// If the base pointers are different, but the indices are the same, just
588
// compare the base pointer.
589
if (PtrBase != GEPRHS->getOperand(0)) {
590
bool IndicesTheSame = GEPLHS->getNumOperands()==GEPRHS->getNumOperands();
591
IndicesTheSame &= GEPLHS->getOperand(0)->getType() ==
592
GEPRHS->getOperand(0)->getType();
594
for (unsigned i = 1, e = GEPLHS->getNumOperands(); i != e; ++i)
595
if (GEPLHS->getOperand(i) != GEPRHS->getOperand(i)) {
596
IndicesTheSame = false;
600
// If all indices are the same, just compare the base pointers.
602
return new ICmpInst(ICmpInst::getSignedPredicate(Cond),
603
GEPLHS->getOperand(0), GEPRHS->getOperand(0));
605
// Otherwise, the base pointers are different and the indices are
606
// different, bail out.
610
// If one of the GEPs has all zero indices, recurse.
611
bool AllZeros = true;
612
for (unsigned i = 1, e = GEPLHS->getNumOperands(); i != e; ++i)
613
if (!isa<Constant>(GEPLHS->getOperand(i)) ||
614
!cast<Constant>(GEPLHS->getOperand(i))->isNullValue()) {
619
return FoldGEPICmp(GEPRHS, GEPLHS->getOperand(0),
620
ICmpInst::getSwappedPredicate(Cond), I);
622
// If the other GEP has all zero indices, recurse.
624
for (unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
625
if (!isa<Constant>(GEPRHS->getOperand(i)) ||
626
!cast<Constant>(GEPRHS->getOperand(i))->isNullValue()) {
631
return FoldGEPICmp(GEPLHS, GEPRHS->getOperand(0), Cond, I);
633
if (GEPLHS->getNumOperands() == GEPRHS->getNumOperands()) {
634
// If the GEPs only differ by one index, compare it.
635
unsigned NumDifferences = 0; // Keep track of # differences.
636
unsigned DiffOperand = 0; // The operand that differs.
637
for (unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
638
if (GEPLHS->getOperand(i) != GEPRHS->getOperand(i)) {
639
if (GEPLHS->getOperand(i)->getType()->getPrimitiveSizeInBits() !=
640
GEPRHS->getOperand(i)->getType()->getPrimitiveSizeInBits()) {
641
// Irreconcilable differences.
645
if (NumDifferences++) break;
650
if (NumDifferences == 0) // SAME GEP?
651
return ReplaceInstUsesWith(I, // No comparison is needed here.
652
ConstantInt::get(Type::getInt1Ty(I.getContext()),
653
ICmpInst::isTrueWhenEqual(Cond)));
655
else if (NumDifferences == 1) {
656
Value *LHSV = GEPLHS->getOperand(DiffOperand);
657
Value *RHSV = GEPRHS->getOperand(DiffOperand);
658
// Make sure we do a signed comparison here.
659
return new ICmpInst(ICmpInst::getSignedPredicate(Cond), LHSV, RHSV);
663
// Only lower this if the icmp is the only user of the GEP or if we expect
664
// the result to fold to a constant!
666
(isa<ConstantExpr>(GEPLHS) || GEPLHS->hasOneUse()) &&
667
(isa<ConstantExpr>(GEPRHS) || GEPRHS->hasOneUse())) {
668
// ((gep Ptr, OFFSET1) cmp (gep Ptr, OFFSET2) ---> (OFFSET1 cmp OFFSET2)
669
Value *L = EmitGEPOffset(GEPLHS);
670
Value *R = EmitGEPOffset(GEPRHS);
671
return new ICmpInst(ICmpInst::getSignedPredicate(Cond), L, R);
677
/// FoldICmpAddOpCst - Fold "icmp pred (X+CI), X".
678
Instruction *InstCombiner::FoldICmpAddOpCst(ICmpInst &ICI,
679
Value *X, ConstantInt *CI,
680
ICmpInst::Predicate Pred,
682
// If we have X+0, exit early (simplifying logic below) and let it get folded
683
// elsewhere. icmp X+0, X -> icmp X, X
685
bool isTrue = ICmpInst::isTrueWhenEqual(Pred);
686
return ReplaceInstUsesWith(ICI, ConstantInt::get(ICI.getType(), isTrue));
689
// (X+4) == X -> false.
690
if (Pred == ICmpInst::ICMP_EQ)
691
return ReplaceInstUsesWith(ICI, ConstantInt::getFalse(X->getContext()));
693
// (X+4) != X -> true.
694
if (Pred == ICmpInst::ICMP_NE)
695
return ReplaceInstUsesWith(ICI, ConstantInt::getTrue(X->getContext()));
697
// If this is an instruction (as opposed to constantexpr) get NUW/NSW info.
698
bool isNUW = false, isNSW = false;
699
if (BinaryOperator *Add = dyn_cast<BinaryOperator>(TheAdd)) {
700
isNUW = Add->hasNoUnsignedWrap();
701
isNSW = Add->hasNoSignedWrap();
704
// From this point on, we know that (X+C <= X) --> (X+C < X) because C != 0,
705
// so the values can never be equal. Similiarly for all other "or equals"
708
// (X+1) <u X --> X >u (MAXUINT-1) --> X == 255
709
// (X+2) <u X --> X >u (MAXUINT-2) --> X > 253
710
// (X+MAXUINT) <u X --> X >u (MAXUINT-MAXUINT) --> X != 0
711
if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE) {
712
// If this is an NUW add, then this is always false.
714
return ReplaceInstUsesWith(ICI, ConstantInt::getFalse(X->getContext()));
717
ConstantExpr::getSub(ConstantInt::getAllOnesValue(CI->getType()), CI);
718
return new ICmpInst(ICmpInst::ICMP_UGT, X, R);
721
// (X+1) >u X --> X <u (0-1) --> X != 255
722
// (X+2) >u X --> X <u (0-2) --> X <u 254
723
// (X+MAXUINT) >u X --> X <u (0-MAXUINT) --> X <u 1 --> X == 0
724
if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE) {
725
// If this is an NUW add, then this is always true.
727
return ReplaceInstUsesWith(ICI, ConstantInt::getTrue(X->getContext()));
728
return new ICmpInst(ICmpInst::ICMP_ULT, X, ConstantExpr::getNeg(CI));
731
unsigned BitWidth = CI->getType()->getPrimitiveSizeInBits();
732
ConstantInt *SMax = ConstantInt::get(X->getContext(),
733
APInt::getSignedMaxValue(BitWidth));
735
// (X+ 1) <s X --> X >s (MAXSINT-1) --> X == 127
736
// (X+ 2) <s X --> X >s (MAXSINT-2) --> X >s 125
737
// (X+MAXSINT) <s X --> X >s (MAXSINT-MAXSINT) --> X >s 0
738
// (X+MINSINT) <s X --> X >s (MAXSINT-MINSINT) --> X >s -1
739
// (X+ -2) <s X --> X >s (MAXSINT- -2) --> X >s 126
740
// (X+ -1) <s X --> X >s (MAXSINT- -1) --> X != 127
741
if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE) {
742
// If this is an NSW add, then we have two cases: if the constant is
743
// positive, then this is always false, if negative, this is always true.
745
bool isTrue = CI->getValue().isNegative();
746
return ReplaceInstUsesWith(ICI, ConstantInt::get(ICI.getType(), isTrue));
749
return new ICmpInst(ICmpInst::ICMP_SGT, X, ConstantExpr::getSub(SMax, CI));
752
// (X+ 1) >s X --> X <s (MAXSINT-(1-1)) --> X != 127
753
// (X+ 2) >s X --> X <s (MAXSINT-(2-1)) --> X <s 126
754
// (X+MAXSINT) >s X --> X <s (MAXSINT-(MAXSINT-1)) --> X <s 1
755
// (X+MINSINT) >s X --> X <s (MAXSINT-(MINSINT-1)) --> X <s -2
756
// (X+ -2) >s X --> X <s (MAXSINT-(-2-1)) --> X <s -126
757
// (X+ -1) >s X --> X <s (MAXSINT-(-1-1)) --> X == -128
759
// If this is an NSW add, then we have two cases: if the constant is
760
// positive, then this is always true, if negative, this is always false.
762
bool isTrue = !CI->getValue().isNegative();
763
return ReplaceInstUsesWith(ICI, ConstantInt::get(ICI.getType(), isTrue));
766
assert(Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE);
767
Constant *C = ConstantInt::get(X->getContext(), CI->getValue()-1);
768
return new ICmpInst(ICmpInst::ICMP_SLT, X, ConstantExpr::getSub(SMax, C));
771
/// FoldICmpDivCst - Fold "icmp pred, ([su]div X, DivRHS), CmpRHS" where DivRHS
772
/// and CmpRHS are both known to be integer constants.
773
Instruction *InstCombiner::FoldICmpDivCst(ICmpInst &ICI, BinaryOperator *DivI,
774
ConstantInt *DivRHS) {
775
ConstantInt *CmpRHS = cast<ConstantInt>(ICI.getOperand(1));
776
const APInt &CmpRHSV = CmpRHS->getValue();
778
// FIXME: If the operand types don't match the type of the divide
779
// then don't attempt this transform. The code below doesn't have the
780
// logic to deal with a signed divide and an unsigned compare (and
781
// vice versa). This is because (x /s C1) <s C2 produces different
782
// results than (x /s C1) <u C2 or (x /u C1) <s C2 or even
783
// (x /u C1) <u C2. Simply casting the operands and result won't
784
// work. :( The if statement below tests that condition and bails
786
bool DivIsSigned = DivI->getOpcode() == Instruction::SDiv;
787
if (!ICI.isEquality() && DivIsSigned != ICI.isSigned())
789
if (DivRHS->isZero())
790
return 0; // The ProdOV computation fails on divide by zero.
791
if (DivIsSigned && DivRHS->isAllOnesValue())
792
return 0; // The overflow computation also screws up here
794
return 0; // Not worth bothering, and eliminates some funny cases
797
// Compute Prod = CI * DivRHS. We are essentially solving an equation
798
// of form X/C1=C2. We solve for X by multiplying C1 (DivRHS) and
799
// C2 (CI). By solving for X we can turn this into a range check
800
// instead of computing a divide.
801
Constant *Prod = ConstantExpr::getMul(CmpRHS, DivRHS);
803
// Determine if the product overflows by seeing if the product is
804
// not equal to the divide. Make sure we do the same kind of divide
805
// as in the LHS instruction that we're folding.
806
bool ProdOV = (DivIsSigned ? ConstantExpr::getSDiv(Prod, DivRHS) :
807
ConstantExpr::getUDiv(Prod, DivRHS)) != CmpRHS;
809
// Get the ICmp opcode
810
ICmpInst::Predicate Pred = ICI.getPredicate();
812
// Figure out the interval that is being checked. For example, a comparison
813
// like "X /u 5 == 0" is really checking that X is in the interval [0, 5).
814
// Compute this interval based on the constants involved and the signedness of
815
// the compare/divide. This computes a half-open interval, keeping track of
816
// whether either value in the interval overflows. After analysis each
817
// overflow variable is set to 0 if it's corresponding bound variable is valid
818
// -1 if overflowed off the bottom end, or +1 if overflowed off the top end.
819
int LoOverflow = 0, HiOverflow = 0;
820
Constant *LoBound = 0, *HiBound = 0;
822
if (!DivIsSigned) { // udiv
823
// e.g. X/5 op 3 --> [15, 20)
825
HiOverflow = LoOverflow = ProdOV;
827
HiOverflow = AddWithOverflow(HiBound, LoBound, DivRHS, false);
828
} else if (DivRHS->getValue().isStrictlyPositive()) { // Divisor is > 0.
829
if (CmpRHSV == 0) { // (X / pos) op 0
830
// Can't overflow. e.g. X/2 op 0 --> [-1, 2)
831
LoBound = cast<ConstantInt>(ConstantExpr::getNeg(SubOne(DivRHS)));
833
} else if (CmpRHSV.isStrictlyPositive()) { // (X / pos) op pos
834
LoBound = Prod; // e.g. X/5 op 3 --> [15, 20)
835
HiOverflow = LoOverflow = ProdOV;
837
HiOverflow = AddWithOverflow(HiBound, Prod, DivRHS, true);
838
} else { // (X / pos) op neg
839
// e.g. X/5 op -3 --> [-15-4, -15+1) --> [-19, -14)
840
HiBound = AddOne(Prod);
841
LoOverflow = HiOverflow = ProdOV ? -1 : 0;
843
ConstantInt* DivNeg =
844
cast<ConstantInt>(ConstantExpr::getNeg(DivRHS));
845
LoOverflow = AddWithOverflow(LoBound, HiBound, DivNeg, true) ? -1 : 0;
848
} else if (DivRHS->getValue().isNegative()) { // Divisor is < 0.
849
if (CmpRHSV == 0) { // (X / neg) op 0
850
// e.g. X/-5 op 0 --> [-4, 5)
851
LoBound = AddOne(DivRHS);
852
HiBound = cast<ConstantInt>(ConstantExpr::getNeg(DivRHS));
853
if (HiBound == DivRHS) { // -INTMIN = INTMIN
854
HiOverflow = 1; // [INTMIN+1, overflow)
855
HiBound = 0; // e.g. X/INTMIN = 0 --> X > INTMIN
857
} else if (CmpRHSV.isStrictlyPositive()) { // (X / neg) op pos
858
// e.g. X/-5 op 3 --> [-19, -14)
859
HiBound = AddOne(Prod);
860
HiOverflow = LoOverflow = ProdOV ? -1 : 0;
862
LoOverflow = AddWithOverflow(LoBound, HiBound, DivRHS, true) ? -1 : 0;
863
} else { // (X / neg) op neg
864
LoBound = Prod; // e.g. X/-5 op -3 --> [15, 20)
865
LoOverflow = HiOverflow = ProdOV;
867
HiOverflow = SubWithOverflow(HiBound, Prod, DivRHS, true);
870
// Dividing by a negative swaps the condition. LT <-> GT
871
Pred = ICmpInst::getSwappedPredicate(Pred);
874
Value *X = DivI->getOperand(0);
876
default: llvm_unreachable("Unhandled icmp opcode!");
877
case ICmpInst::ICMP_EQ:
878
if (LoOverflow && HiOverflow)
879
return ReplaceInstUsesWith(ICI, ConstantInt::getFalse(ICI.getContext()));
881
return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE :
882
ICmpInst::ICMP_UGE, X, LoBound);
884
return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT :
885
ICmpInst::ICMP_ULT, X, HiBound);
886
return ReplaceInstUsesWith(ICI,
887
InsertRangeTest(X, LoBound, HiBound, DivIsSigned,
889
case ICmpInst::ICMP_NE:
890
if (LoOverflow && HiOverflow)
891
return ReplaceInstUsesWith(ICI, ConstantInt::getTrue(ICI.getContext()));
893
return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT :
894
ICmpInst::ICMP_ULT, X, LoBound);
896
return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE :
897
ICmpInst::ICMP_UGE, X, HiBound);
898
return ReplaceInstUsesWith(ICI, InsertRangeTest(X, LoBound, HiBound,
899
DivIsSigned, false));
900
case ICmpInst::ICMP_ULT:
901
case ICmpInst::ICMP_SLT:
902
if (LoOverflow == +1) // Low bound is greater than input range.
903
return ReplaceInstUsesWith(ICI, ConstantInt::getTrue(ICI.getContext()));
904
if (LoOverflow == -1) // Low bound is less than input range.
905
return ReplaceInstUsesWith(ICI, ConstantInt::getFalse(ICI.getContext()));
906
return new ICmpInst(Pred, X, LoBound);
907
case ICmpInst::ICMP_UGT:
908
case ICmpInst::ICMP_SGT:
909
if (HiOverflow == +1) // High bound greater than input range.
910
return ReplaceInstUsesWith(ICI, ConstantInt::getFalse(ICI.getContext()));
911
else if (HiOverflow == -1) // High bound less than input range.
912
return ReplaceInstUsesWith(ICI, ConstantInt::getTrue(ICI.getContext()));
913
if (Pred == ICmpInst::ICMP_UGT)
914
return new ICmpInst(ICmpInst::ICMP_UGE, X, HiBound);
916
return new ICmpInst(ICmpInst::ICMP_SGE, X, HiBound);
921
/// visitICmpInstWithInstAndIntCst - Handle "icmp (instr, intcst)".
923
Instruction *InstCombiner::visitICmpInstWithInstAndIntCst(ICmpInst &ICI,
926
const APInt &RHSV = RHS->getValue();
928
switch (LHSI->getOpcode()) {
929
case Instruction::Trunc:
930
if (ICI.isEquality() && LHSI->hasOneUse()) {
931
// Simplify icmp eq (trunc x to i8), 42 -> icmp eq x, 42|highbits if all
932
// of the high bits truncated out of x are known.
933
unsigned DstBits = LHSI->getType()->getPrimitiveSizeInBits(),
934
SrcBits = LHSI->getOperand(0)->getType()->getPrimitiveSizeInBits();
935
APInt Mask(APInt::getHighBitsSet(SrcBits, SrcBits-DstBits));
936
APInt KnownZero(SrcBits, 0), KnownOne(SrcBits, 0);
937
ComputeMaskedBits(LHSI->getOperand(0), Mask, KnownZero, KnownOne);
939
// If all the high bits are known, we can do this xform.
940
if ((KnownZero|KnownOne).countLeadingOnes() >= SrcBits-DstBits) {
941
// Pull in the high bits from known-ones set.
942
APInt NewRHS(RHS->getValue());
943
NewRHS.zext(SrcBits);
945
return new ICmpInst(ICI.getPredicate(), LHSI->getOperand(0),
946
ConstantInt::get(ICI.getContext(), NewRHS));
951
case Instruction::Xor: // (icmp pred (xor X, XorCST), CI)
952
if (ConstantInt *XorCST = dyn_cast<ConstantInt>(LHSI->getOperand(1))) {
953
// If this is a comparison that tests the signbit (X < 0) or (x > -1),
955
if ((ICI.getPredicate() == ICmpInst::ICMP_SLT && RHSV == 0) ||
956
(ICI.getPredicate() == ICmpInst::ICMP_SGT && RHSV.isAllOnesValue())) {
957
Value *CompareVal = LHSI->getOperand(0);
959
// If the sign bit of the XorCST is not set, there is no change to
960
// the operation, just stop using the Xor.
961
if (!XorCST->getValue().isNegative()) {
962
ICI.setOperand(0, CompareVal);
967
// Was the old condition true if the operand is positive?
968
bool isTrueIfPositive = ICI.getPredicate() == ICmpInst::ICMP_SGT;
970
// If so, the new one isn't.
971
isTrueIfPositive ^= true;
973
if (isTrueIfPositive)
974
return new ICmpInst(ICmpInst::ICMP_SGT, CompareVal,
977
return new ICmpInst(ICmpInst::ICMP_SLT, CompareVal,
981
if (LHSI->hasOneUse()) {
982
// (icmp u/s (xor A SignBit), C) -> (icmp s/u A, (xor C SignBit))
983
if (!ICI.isEquality() && XorCST->getValue().isSignBit()) {
984
const APInt &SignBit = XorCST->getValue();
985
ICmpInst::Predicate Pred = ICI.isSigned()
986
? ICI.getUnsignedPredicate()
987
: ICI.getSignedPredicate();
988
return new ICmpInst(Pred, LHSI->getOperand(0),
989
ConstantInt::get(ICI.getContext(),
993
// (icmp u/s (xor A ~SignBit), C) -> (icmp s/u (xor C ~SignBit), A)
994
if (!ICI.isEquality() && XorCST->getValue().isMaxSignedValue()) {
995
const APInt &NotSignBit = XorCST->getValue();
996
ICmpInst::Predicate Pred = ICI.isSigned()
997
? ICI.getUnsignedPredicate()
998
: ICI.getSignedPredicate();
999
Pred = ICI.getSwappedPredicate(Pred);
1000
return new ICmpInst(Pred, LHSI->getOperand(0),
1001
ConstantInt::get(ICI.getContext(),
1002
RHSV ^ NotSignBit));
1007
case Instruction::And: // (icmp pred (and X, AndCST), RHS)
1008
if (LHSI->hasOneUse() && isa<ConstantInt>(LHSI->getOperand(1)) &&
1009
LHSI->getOperand(0)->hasOneUse()) {
1010
ConstantInt *AndCST = cast<ConstantInt>(LHSI->getOperand(1));
1012
// If the LHS is an AND of a truncating cast, we can widen the
1013
// and/compare to be the input width without changing the value
1014
// produced, eliminating a cast.
1015
if (TruncInst *Cast = dyn_cast<TruncInst>(LHSI->getOperand(0))) {
1016
// We can do this transformation if either the AND constant does not
1017
// have its sign bit set or if it is an equality comparison.
1018
// Extending a relational comparison when we're checking the sign
1019
// bit would not work.
1020
if (Cast->hasOneUse() &&
1021
(ICI.isEquality() ||
1022
(AndCST->getValue().isNonNegative() && RHSV.isNonNegative()))) {
1024
cast<IntegerType>(Cast->getOperand(0)->getType())->getBitWidth();
1025
APInt NewCST = AndCST->getValue();
1026
NewCST.zext(BitWidth);
1028
NewCI.zext(BitWidth);
1030
Builder->CreateAnd(Cast->getOperand(0),
1031
ConstantInt::get(ICI.getContext(), NewCST),
1033
return new ICmpInst(ICI.getPredicate(), NewAnd,
1034
ConstantInt::get(ICI.getContext(), NewCI));
1038
// If this is: (X >> C1) & C2 != C3 (where any shift and any compare
1039
// could exist), turn it into (X & (C2 << C1)) != (C3 << C1). This
1040
// happens a LOT in code produced by the C front-end, for bitfield
1042
BinaryOperator *Shift = dyn_cast<BinaryOperator>(LHSI->getOperand(0));
1043
if (Shift && !Shift->isShift())
1047
ShAmt = Shift ? dyn_cast<ConstantInt>(Shift->getOperand(1)) : 0;
1048
const Type *Ty = Shift ? Shift->getType() : 0; // Type of the shift.
1049
const Type *AndTy = AndCST->getType(); // Type of the and.
1051
// We can fold this as long as we can't shift unknown bits
1052
// into the mask. This can only happen with signed shift
1053
// rights, as they sign-extend.
1055
bool CanFold = Shift->isLogicalShift();
1057
// To test for the bad case of the signed shr, see if any
1058
// of the bits shifted in could be tested after the mask.
1059
uint32_t TyBits = Ty->getPrimitiveSizeInBits();
1060
int ShAmtVal = TyBits - ShAmt->getLimitedValue(TyBits);
1062
uint32_t BitWidth = AndTy->getPrimitiveSizeInBits();
1063
if ((APInt::getHighBitsSet(BitWidth, BitWidth-ShAmtVal) &
1064
AndCST->getValue()) == 0)
1070
if (Shift->getOpcode() == Instruction::Shl)
1071
NewCst = ConstantExpr::getLShr(RHS, ShAmt);
1073
NewCst = ConstantExpr::getShl(RHS, ShAmt);
1075
// Check to see if we are shifting out any of the bits being
1077
if (ConstantExpr::get(Shift->getOpcode(),
1078
NewCst, ShAmt) != RHS) {
1079
// If we shifted bits out, the fold is not going to work out.
1080
// As a special case, check to see if this means that the
1081
// result is always true or false now.
1082
if (ICI.getPredicate() == ICmpInst::ICMP_EQ)
1083
return ReplaceInstUsesWith(ICI,
1084
ConstantInt::getFalse(ICI.getContext()));
1085
if (ICI.getPredicate() == ICmpInst::ICMP_NE)
1086
return ReplaceInstUsesWith(ICI,
1087
ConstantInt::getTrue(ICI.getContext()));
1089
ICI.setOperand(1, NewCst);
1090
Constant *NewAndCST;
1091
if (Shift->getOpcode() == Instruction::Shl)
1092
NewAndCST = ConstantExpr::getLShr(AndCST, ShAmt);
1094
NewAndCST = ConstantExpr::getShl(AndCST, ShAmt);
1095
LHSI->setOperand(1, NewAndCST);
1096
LHSI->setOperand(0, Shift->getOperand(0));
1097
Worklist.Add(Shift); // Shift is dead.
1103
// Turn ((X >> Y) & C) == 0 into (X & (C << Y)) == 0. The later is
1104
// preferable because it allows the C<<Y expression to be hoisted out
1105
// of a loop if Y is invariant and X is not.
1106
if (Shift && Shift->hasOneUse() && RHSV == 0 &&
1107
ICI.isEquality() && !Shift->isArithmeticShift() &&
1108
!isa<Constant>(Shift->getOperand(0))) {
1111
if (Shift->getOpcode() == Instruction::LShr) {
1112
NS = Builder->CreateShl(AndCST, Shift->getOperand(1), "tmp");
1114
// Insert a logical shift.
1115
NS = Builder->CreateLShr(AndCST, Shift->getOperand(1), "tmp");
1118
// Compute X & (C << Y).
1120
Builder->CreateAnd(Shift->getOperand(0), NS, LHSI->getName());
1122
ICI.setOperand(0, NewAnd);
1127
// Try to optimize things like "A[i]&42 == 0" to index computations.
1128
if (LoadInst *LI = dyn_cast<LoadInst>(LHSI->getOperand(0))) {
1129
if (GetElementPtrInst *GEP =
1130
dyn_cast<GetElementPtrInst>(LI->getOperand(0)))
1131
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)))
1132
if (GV->isConstant() && GV->hasDefinitiveInitializer() &&
1133
!LI->isVolatile() && isa<ConstantInt>(LHSI->getOperand(1))) {
1134
ConstantInt *C = cast<ConstantInt>(LHSI->getOperand(1));
1135
if (Instruction *Res = FoldCmpLoadFromIndexedGlobal(GEP, GV,ICI, C))
1141
case Instruction::Or: {
1142
if (!ICI.isEquality() || !RHS->isNullValue() || !LHSI->hasOneUse())
1145
if (match(LHSI, m_Or(m_PtrToInt(m_Value(P)), m_PtrToInt(m_Value(Q))))) {
1146
// Simplify icmp eq (or (ptrtoint P), (ptrtoint Q)), 0
1147
// -> and (icmp eq P, null), (icmp eq Q, null).
1149
Value *ICIP = Builder->CreateICmp(ICI.getPredicate(), P,
1150
Constant::getNullValue(P->getType()));
1151
Value *ICIQ = Builder->CreateICmp(ICI.getPredicate(), Q,
1152
Constant::getNullValue(Q->getType()));
1154
if (ICI.getPredicate() == ICmpInst::ICMP_EQ)
1155
Op = BinaryOperator::CreateAnd(ICIP, ICIQ);
1157
Op = BinaryOperator::CreateOr(ICIP, ICIQ);
1163
case Instruction::Shl: { // (icmp pred (shl X, ShAmt), CI)
1164
ConstantInt *ShAmt = dyn_cast<ConstantInt>(LHSI->getOperand(1));
1167
uint32_t TypeBits = RHSV.getBitWidth();
1169
// Check that the shift amount is in range. If not, don't perform
1170
// undefined shifts. When the shift is visited it will be
1172
if (ShAmt->uge(TypeBits))
1175
if (ICI.isEquality()) {
1176
// If we are comparing against bits always shifted out, the
1177
// comparison cannot succeed.
1179
ConstantExpr::getShl(ConstantExpr::getLShr(RHS, ShAmt),
1181
if (Comp != RHS) {// Comparing against a bit that we know is zero.
1182
bool IsICMP_NE = ICI.getPredicate() == ICmpInst::ICMP_NE;
1184
ConstantInt::get(Type::getInt1Ty(ICI.getContext()), IsICMP_NE);
1185
return ReplaceInstUsesWith(ICI, Cst);
1188
if (LHSI->hasOneUse()) {
1189
// Otherwise strength reduce the shift into an and.
1190
uint32_t ShAmtVal = (uint32_t)ShAmt->getLimitedValue(TypeBits);
1192
ConstantInt::get(ICI.getContext(), APInt::getLowBitsSet(TypeBits,
1193
TypeBits-ShAmtVal));
1196
Builder->CreateAnd(LHSI->getOperand(0),Mask, LHSI->getName()+".mask");
1197
return new ICmpInst(ICI.getPredicate(), And,
1198
ConstantInt::get(ICI.getContext(),
1199
RHSV.lshr(ShAmtVal)));
1203
// Otherwise, if this is a comparison of the sign bit, simplify to and/test.
1204
bool TrueIfSigned = false;
1205
if (LHSI->hasOneUse() &&
1206
isSignBitCheck(ICI.getPredicate(), RHS, TrueIfSigned)) {
1207
// (X << 31) <s 0 --> (X&1) != 0
1208
Constant *Mask = ConstantInt::get(ICI.getContext(), APInt(TypeBits, 1) <<
1209
(TypeBits-ShAmt->getZExtValue()-1));
1211
Builder->CreateAnd(LHSI->getOperand(0), Mask, LHSI->getName()+".mask");
1212
return new ICmpInst(TrueIfSigned ? ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ,
1213
And, Constant::getNullValue(And->getType()));
1218
case Instruction::LShr: // (icmp pred (shr X, ShAmt), CI)
1219
case Instruction::AShr: {
1220
// Only handle equality comparisons of shift-by-constant.
1221
ConstantInt *ShAmt = dyn_cast<ConstantInt>(LHSI->getOperand(1));
1222
if (!ShAmt || !ICI.isEquality()) break;
1224
// Check that the shift amount is in range. If not, don't perform
1225
// undefined shifts. When the shift is visited it will be
1227
uint32_t TypeBits = RHSV.getBitWidth();
1228
if (ShAmt->uge(TypeBits))
1231
uint32_t ShAmtVal = (uint32_t)ShAmt->getLimitedValue(TypeBits);
1233
// If we are comparing against bits always shifted out, the
1234
// comparison cannot succeed.
1235
APInt Comp = RHSV << ShAmtVal;
1236
if (LHSI->getOpcode() == Instruction::LShr)
1237
Comp = Comp.lshr(ShAmtVal);
1239
Comp = Comp.ashr(ShAmtVal);
1241
if (Comp != RHSV) { // Comparing against a bit that we know is zero.
1242
bool IsICMP_NE = ICI.getPredicate() == ICmpInst::ICMP_NE;
1243
Constant *Cst = ConstantInt::get(Type::getInt1Ty(ICI.getContext()),
1245
return ReplaceInstUsesWith(ICI, Cst);
1248
// Otherwise, check to see if the bits shifted out are known to be zero.
1249
// If so, we can compare against the unshifted value:
1250
// (X & 4) >> 1 == 2 --> (X & 4) == 4.
1251
if (LHSI->hasOneUse() &&
1252
MaskedValueIsZero(LHSI->getOperand(0),
1253
APInt::getLowBitsSet(Comp.getBitWidth(), ShAmtVal))) {
1254
return new ICmpInst(ICI.getPredicate(), LHSI->getOperand(0),
1255
ConstantExpr::getShl(RHS, ShAmt));
1258
if (LHSI->hasOneUse()) {
1259
// Otherwise strength reduce the shift into an and.
1260
APInt Val(APInt::getHighBitsSet(TypeBits, TypeBits - ShAmtVal));
1261
Constant *Mask = ConstantInt::get(ICI.getContext(), Val);
1263
Value *And = Builder->CreateAnd(LHSI->getOperand(0),
1264
Mask, LHSI->getName()+".mask");
1265
return new ICmpInst(ICI.getPredicate(), And,
1266
ConstantExpr::getShl(RHS, ShAmt));
1271
case Instruction::SDiv:
1272
case Instruction::UDiv:
1273
// Fold: icmp pred ([us]div X, C1), C2 -> range test
1274
// Fold this div into the comparison, producing a range check.
1275
// Determine, based on the divide type, what the range is being
1276
// checked. If there is an overflow on the low or high side, remember
1277
// it, otherwise compute the range [low, hi) bounding the new value.
1278
// See: InsertRangeTest above for the kinds of replacements possible.
1279
if (ConstantInt *DivRHS = dyn_cast<ConstantInt>(LHSI->getOperand(1)))
1280
if (Instruction *R = FoldICmpDivCst(ICI, cast<BinaryOperator>(LHSI),
1285
case Instruction::Add:
1286
// Fold: icmp pred (add X, C1), C2
1287
if (!ICI.isEquality()) {
1288
ConstantInt *LHSC = dyn_cast<ConstantInt>(LHSI->getOperand(1));
1290
const APInt &LHSV = LHSC->getValue();
1292
ConstantRange CR = ICI.makeConstantRange(ICI.getPredicate(), RHSV)
1295
if (ICI.isSigned()) {
1296
if (CR.getLower().isSignBit()) {
1297
return new ICmpInst(ICmpInst::ICMP_SLT, LHSI->getOperand(0),
1298
ConstantInt::get(ICI.getContext(),CR.getUpper()));
1299
} else if (CR.getUpper().isSignBit()) {
1300
return new ICmpInst(ICmpInst::ICMP_SGE, LHSI->getOperand(0),
1301
ConstantInt::get(ICI.getContext(),CR.getLower()));
1304
if (CR.getLower().isMinValue()) {
1305
return new ICmpInst(ICmpInst::ICMP_ULT, LHSI->getOperand(0),
1306
ConstantInt::get(ICI.getContext(),CR.getUpper()));
1307
} else if (CR.getUpper().isMinValue()) {
1308
return new ICmpInst(ICmpInst::ICMP_UGE, LHSI->getOperand(0),
1309
ConstantInt::get(ICI.getContext(),CR.getLower()));
1316
// Simplify icmp_eq and icmp_ne instructions with integer constant RHS.
1317
if (ICI.isEquality()) {
1318
bool isICMP_NE = ICI.getPredicate() == ICmpInst::ICMP_NE;
1320
// If the first operand is (add|sub|and|or|xor|rem) with a constant, and
1321
// the second operand is a constant, simplify a bit.
1322
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(LHSI)) {
1323
switch (BO->getOpcode()) {
1324
case Instruction::SRem:
1325
// If we have a signed (X % (2^c)) == 0, turn it into an unsigned one.
1326
if (RHSV == 0 && isa<ConstantInt>(BO->getOperand(1)) &&BO->hasOneUse()){
1327
const APInt &V = cast<ConstantInt>(BO->getOperand(1))->getValue();
1328
if (V.sgt(APInt(V.getBitWidth(), 1)) && V.isPowerOf2()) {
1330
Builder->CreateURem(BO->getOperand(0), BO->getOperand(1),
1332
return new ICmpInst(ICI.getPredicate(), NewRem,
1333
Constant::getNullValue(BO->getType()));
1337
case Instruction::Add:
1338
// Replace ((add A, B) != C) with (A != C-B) if B & C are constants.
1339
if (ConstantInt *BOp1C = dyn_cast<ConstantInt>(BO->getOperand(1))) {
1340
if (BO->hasOneUse())
1341
return new ICmpInst(ICI.getPredicate(), BO->getOperand(0),
1342
ConstantExpr::getSub(RHS, BOp1C));
1343
} else if (RHSV == 0) {
1344
// Replace ((add A, B) != 0) with (A != -B) if A or B is
1345
// efficiently invertible, or if the add has just this one use.
1346
Value *BOp0 = BO->getOperand(0), *BOp1 = BO->getOperand(1);
1348
if (Value *NegVal = dyn_castNegVal(BOp1))
1349
return new ICmpInst(ICI.getPredicate(), BOp0, NegVal);
1350
else if (Value *NegVal = dyn_castNegVal(BOp0))
1351
return new ICmpInst(ICI.getPredicate(), NegVal, BOp1);
1352
else if (BO->hasOneUse()) {
1353
Value *Neg = Builder->CreateNeg(BOp1);
1355
return new ICmpInst(ICI.getPredicate(), BOp0, Neg);
1359
case Instruction::Xor:
1360
// For the xor case, we can xor two constants together, eliminating
1361
// the explicit xor.
1362
if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1)))
1363
return new ICmpInst(ICI.getPredicate(), BO->getOperand(0),
1364
ConstantExpr::getXor(RHS, BOC));
1367
case Instruction::Sub:
1368
// Replace (([sub|xor] A, B) != 0) with (A != B)
1370
return new ICmpInst(ICI.getPredicate(), BO->getOperand(0),
1374
case Instruction::Or:
1375
// If bits are being or'd in that are not present in the constant we
1376
// are comparing against, then the comparison could never succeed!
1377
if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1))) {
1378
Constant *NotCI = ConstantExpr::getNot(RHS);
1379
if (!ConstantExpr::getAnd(BOC, NotCI)->isNullValue())
1380
return ReplaceInstUsesWith(ICI,
1381
ConstantInt::get(Type::getInt1Ty(ICI.getContext()),
1386
case Instruction::And:
1387
if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) {
1388
// If bits are being compared against that are and'd out, then the
1389
// comparison can never succeed!
1390
if ((RHSV & ~BOC->getValue()) != 0)
1391
return ReplaceInstUsesWith(ICI,
1392
ConstantInt::get(Type::getInt1Ty(ICI.getContext()),
1395
// If we have ((X & C) == C), turn it into ((X & C) != 0).
1396
if (RHS == BOC && RHSV.isPowerOf2())
1397
return new ICmpInst(isICMP_NE ? ICmpInst::ICMP_EQ :
1398
ICmpInst::ICMP_NE, LHSI,
1399
Constant::getNullValue(RHS->getType()));
1401
// Replace (and X, (1 << size(X)-1) != 0) with x s< 0
1402
if (BOC->getValue().isSignBit()) {
1403
Value *X = BO->getOperand(0);
1404
Constant *Zero = Constant::getNullValue(X->getType());
1405
ICmpInst::Predicate pred = isICMP_NE ?
1406
ICmpInst::ICMP_SLT : ICmpInst::ICMP_SGE;
1407
return new ICmpInst(pred, X, Zero);
1410
// ((X & ~7) == 0) --> X < 8
1411
if (RHSV == 0 && isHighOnes(BOC)) {
1412
Value *X = BO->getOperand(0);
1413
Constant *NegX = ConstantExpr::getNeg(BOC);
1414
ICmpInst::Predicate pred = isICMP_NE ?
1415
ICmpInst::ICMP_UGE : ICmpInst::ICMP_ULT;
1416
return new ICmpInst(pred, X, NegX);
1421
} else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(LHSI)) {
1422
// Handle icmp {eq|ne} <intrinsic>, intcst.
1423
switch (II->getIntrinsicID()) {
1424
case Intrinsic::bswap:
1426
ICI.setOperand(0, II->getOperand(1));
1427
ICI.setOperand(1, ConstantInt::get(II->getContext(), RHSV.byteSwap()));
1429
case Intrinsic::ctlz:
1430
case Intrinsic::cttz:
1431
// ctz(A) == bitwidth(a) -> A == 0 and likewise for !=
1432
if (RHSV == RHS->getType()->getBitWidth()) {
1434
ICI.setOperand(0, II->getOperand(1));
1435
ICI.setOperand(1, ConstantInt::get(RHS->getType(), 0));
1439
case Intrinsic::ctpop:
1440
// popcount(A) == 0 -> A == 0 and likewise for !=
1441
if (RHS->isZero()) {
1443
ICI.setOperand(0, II->getOperand(1));
1444
ICI.setOperand(1, RHS);
1456
/// visitICmpInstWithCastAndCast - Handle icmp (cast x to y), (cast/cst).
1457
/// We only handle extending casts so far.
1459
Instruction *InstCombiner::visitICmpInstWithCastAndCast(ICmpInst &ICI) {
1460
const CastInst *LHSCI = cast<CastInst>(ICI.getOperand(0));
1461
Value *LHSCIOp = LHSCI->getOperand(0);
1462
const Type *SrcTy = LHSCIOp->getType();
1463
const Type *DestTy = LHSCI->getType();
1466
// Turn icmp (ptrtoint x), (ptrtoint/c) into a compare of the input if the
1467
// integer type is the same size as the pointer type.
1468
if (TD && LHSCI->getOpcode() == Instruction::PtrToInt &&
1469
TD->getPointerSizeInBits() ==
1470
cast<IntegerType>(DestTy)->getBitWidth()) {
1472
if (Constant *RHSC = dyn_cast<Constant>(ICI.getOperand(1))) {
1473
RHSOp = ConstantExpr::getIntToPtr(RHSC, SrcTy);
1474
} else if (PtrToIntInst *RHSC = dyn_cast<PtrToIntInst>(ICI.getOperand(1))) {
1475
RHSOp = RHSC->getOperand(0);
1476
// If the pointer types don't match, insert a bitcast.
1477
if (LHSCIOp->getType() != RHSOp->getType())
1478
RHSOp = Builder->CreateBitCast(RHSOp, LHSCIOp->getType());
1482
return new ICmpInst(ICI.getPredicate(), LHSCIOp, RHSOp);
1485
// The code below only handles extension cast instructions, so far.
1487
if (LHSCI->getOpcode() != Instruction::ZExt &&
1488
LHSCI->getOpcode() != Instruction::SExt)
1491
bool isSignedExt = LHSCI->getOpcode() == Instruction::SExt;
1492
bool isSignedCmp = ICI.isSigned();
1494
if (CastInst *CI = dyn_cast<CastInst>(ICI.getOperand(1))) {
1495
// Not an extension from the same type?
1496
RHSCIOp = CI->getOperand(0);
1497
if (RHSCIOp->getType() != LHSCIOp->getType())
1500
// If the signedness of the two casts doesn't agree (i.e. one is a sext
1501
// and the other is a zext), then we can't handle this.
1502
if (CI->getOpcode() != LHSCI->getOpcode())
1505
// Deal with equality cases early.
1506
if (ICI.isEquality())
1507
return new ICmpInst(ICI.getPredicate(), LHSCIOp, RHSCIOp);
1509
// A signed comparison of sign extended values simplifies into a
1510
// signed comparison.
1511
if (isSignedCmp && isSignedExt)
1512
return new ICmpInst(ICI.getPredicate(), LHSCIOp, RHSCIOp);
1514
// The other three cases all fold into an unsigned comparison.
1515
return new ICmpInst(ICI.getUnsignedPredicate(), LHSCIOp, RHSCIOp);
1518
// If we aren't dealing with a constant on the RHS, exit early
1519
ConstantInt *CI = dyn_cast<ConstantInt>(ICI.getOperand(1));
1523
// Compute the constant that would happen if we truncated to SrcTy then
1524
// reextended to DestTy.
1525
Constant *Res1 = ConstantExpr::getTrunc(CI, SrcTy);
1526
Constant *Res2 = ConstantExpr::getCast(LHSCI->getOpcode(),
1529
// If the re-extended constant didn't change...
1531
// Deal with equality cases early.
1532
if (ICI.isEquality())
1533
return new ICmpInst(ICI.getPredicate(), LHSCIOp, Res1);
1535
// A signed comparison of sign extended values simplifies into a
1536
// signed comparison.
1537
if (isSignedExt && isSignedCmp)
1538
return new ICmpInst(ICI.getPredicate(), LHSCIOp, Res1);
1540
// The other three cases all fold into an unsigned comparison.
1541
return new ICmpInst(ICI.getUnsignedPredicate(), LHSCIOp, Res1);
1544
// The re-extended constant changed so the constant cannot be represented
1545
// in the shorter type. Consequently, we cannot emit a simple comparison.
1547
// First, handle some easy cases. We know the result cannot be equal at this
1548
// point so handle the ICI.isEquality() cases
1549
if (ICI.getPredicate() == ICmpInst::ICMP_EQ)
1550
return ReplaceInstUsesWith(ICI, ConstantInt::getFalse(ICI.getContext()));
1551
if (ICI.getPredicate() == ICmpInst::ICMP_NE)
1552
return ReplaceInstUsesWith(ICI, ConstantInt::getTrue(ICI.getContext()));
1554
// Evaluate the comparison for LT (we invert for GT below). LE and GE cases
1555
// should have been folded away previously and not enter in here.
1558
// We're performing a signed comparison.
1559
if (cast<ConstantInt>(CI)->getValue().isNegative())
1560
Result = ConstantInt::getFalse(ICI.getContext()); // X < (small) --> false
1562
Result = ConstantInt::getTrue(ICI.getContext()); // X < (large) --> true
1564
// We're performing an unsigned comparison.
1566
// We're performing an unsigned comp with a sign extended value.
1567
// This is true if the input is >= 0. [aka >s -1]
1568
Constant *NegOne = Constant::getAllOnesValue(SrcTy);
1569
Result = Builder->CreateICmpSGT(LHSCIOp, NegOne, ICI.getName());
1571
// Unsigned extend & unsigned compare -> always true.
1572
Result = ConstantInt::getTrue(ICI.getContext());
1576
// Finally, return the value computed.
1577
if (ICI.getPredicate() == ICmpInst::ICMP_ULT ||
1578
ICI.getPredicate() == ICmpInst::ICMP_SLT)
1579
return ReplaceInstUsesWith(ICI, Result);
1581
assert((ICI.getPredicate()==ICmpInst::ICMP_UGT ||
1582
ICI.getPredicate()==ICmpInst::ICMP_SGT) &&
1583
"ICmp should be folded!");
1584
if (Constant *CI = dyn_cast<Constant>(Result))
1585
return ReplaceInstUsesWith(ICI, ConstantExpr::getNot(CI));
1586
return BinaryOperator::CreateNot(Result);
1591
Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
1592
bool Changed = false;
1593
Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1595
/// Orders the operands of the compare so that they are listed from most
1596
/// complex to least complex. This puts constants before unary operators,
1597
/// before binary operators.
1598
if (getComplexity(Op0) < getComplexity(Op1)) {
1600
std::swap(Op0, Op1);
1604
if (Value *V = SimplifyICmpInst(I.getPredicate(), Op0, Op1, TD))
1605
return ReplaceInstUsesWith(I, V);
1607
const Type *Ty = Op0->getType();
1609
// icmp's with boolean values can always be turned into bitwise operations
1610
if (Ty->isIntegerTy(1)) {
1611
switch (I.getPredicate()) {
1612
default: llvm_unreachable("Invalid icmp instruction!");
1613
case ICmpInst::ICMP_EQ: { // icmp eq i1 A, B -> ~(A^B)
1614
Value *Xor = Builder->CreateXor(Op0, Op1, I.getName()+"tmp");
1615
return BinaryOperator::CreateNot(Xor);
1617
case ICmpInst::ICMP_NE: // icmp eq i1 A, B -> A^B
1618
return BinaryOperator::CreateXor(Op0, Op1);
1620
case ICmpInst::ICMP_UGT:
1621
std::swap(Op0, Op1); // Change icmp ugt -> icmp ult
1623
case ICmpInst::ICMP_ULT:{ // icmp ult i1 A, B -> ~A & B
1624
Value *Not = Builder->CreateNot(Op0, I.getName()+"tmp");
1625
return BinaryOperator::CreateAnd(Not, Op1);
1627
case ICmpInst::ICMP_SGT:
1628
std::swap(Op0, Op1); // Change icmp sgt -> icmp slt
1630
case ICmpInst::ICMP_SLT: { // icmp slt i1 A, B -> A & ~B
1631
Value *Not = Builder->CreateNot(Op1, I.getName()+"tmp");
1632
return BinaryOperator::CreateAnd(Not, Op0);
1634
case ICmpInst::ICMP_UGE:
1635
std::swap(Op0, Op1); // Change icmp uge -> icmp ule
1637
case ICmpInst::ICMP_ULE: { // icmp ule i1 A, B -> ~A | B
1638
Value *Not = Builder->CreateNot(Op0, I.getName()+"tmp");
1639
return BinaryOperator::CreateOr(Not, Op1);
1641
case ICmpInst::ICMP_SGE:
1642
std::swap(Op0, Op1); // Change icmp sge -> icmp sle
1644
case ICmpInst::ICMP_SLE: { // icmp sle i1 A, B -> A | ~B
1645
Value *Not = Builder->CreateNot(Op1, I.getName()+"tmp");
1646
return BinaryOperator::CreateOr(Not, Op0);
1651
unsigned BitWidth = 0;
1653
BitWidth = TD->getTypeSizeInBits(Ty->getScalarType());
1654
else if (Ty->isIntOrIntVectorTy())
1655
BitWidth = Ty->getScalarSizeInBits();
1657
bool isSignBit = false;
1659
// See if we are doing a comparison with a constant.
1660
if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
1661
Value *A = 0, *B = 0;
1663
// (icmp ne/eq (sub A B) 0) -> (icmp ne/eq A, B)
1664
if (I.isEquality() && CI->isZero() &&
1665
match(Op0, m_Sub(m_Value(A), m_Value(B)))) {
1666
// (icmp cond A B) if cond is equality
1667
return new ICmpInst(I.getPredicate(), A, B);
1670
// If we have an icmp le or icmp ge instruction, turn it into the
1671
// appropriate icmp lt or icmp gt instruction. This allows us to rely on
1672
// them being folded in the code below. The SimplifyICmpInst code has
1673
// already handled the edge cases for us, so we just assert on them.
1674
switch (I.getPredicate()) {
1676
case ICmpInst::ICMP_ULE:
1677
assert(!CI->isMaxValue(false)); // A <=u MAX -> TRUE
1678
return new ICmpInst(ICmpInst::ICMP_ULT, Op0,
1679
ConstantInt::get(CI->getContext(), CI->getValue()+1));
1680
case ICmpInst::ICMP_SLE:
1681
assert(!CI->isMaxValue(true)); // A <=s MAX -> TRUE
1682
return new ICmpInst(ICmpInst::ICMP_SLT, Op0,
1683
ConstantInt::get(CI->getContext(), CI->getValue()+1));
1684
case ICmpInst::ICMP_UGE:
1685
assert(!CI->isMinValue(false)); // A >=u MIN -> TRUE
1686
return new ICmpInst(ICmpInst::ICMP_UGT, Op0,
1687
ConstantInt::get(CI->getContext(), CI->getValue()-1));
1688
case ICmpInst::ICMP_SGE:
1689
assert(!CI->isMinValue(true)); // A >=s MIN -> TRUE
1690
return new ICmpInst(ICmpInst::ICMP_SGT, Op0,
1691
ConstantInt::get(CI->getContext(), CI->getValue()-1));
1694
// If this comparison is a normal comparison, it demands all
1695
// bits, if it is a sign bit comparison, it only demands the sign bit.
1697
isSignBit = isSignBitCheck(I.getPredicate(), CI, UnusedBit);
1700
// See if we can fold the comparison based on range information we can get
1701
// by checking whether bits are known to be zero or one in the input.
1702
if (BitWidth != 0) {
1703
APInt Op0KnownZero(BitWidth, 0), Op0KnownOne(BitWidth, 0);
1704
APInt Op1KnownZero(BitWidth, 0), Op1KnownOne(BitWidth, 0);
1706
if (SimplifyDemandedBits(I.getOperandUse(0),
1707
isSignBit ? APInt::getSignBit(BitWidth)
1708
: APInt::getAllOnesValue(BitWidth),
1709
Op0KnownZero, Op0KnownOne, 0))
1711
if (SimplifyDemandedBits(I.getOperandUse(1),
1712
APInt::getAllOnesValue(BitWidth),
1713
Op1KnownZero, Op1KnownOne, 0))
1716
// Given the known and unknown bits, compute a range that the LHS could be
1717
// in. Compute the Min, Max and RHS values based on the known bits. For the
1718
// EQ and NE we use unsigned values.
1719
APInt Op0Min(BitWidth, 0), Op0Max(BitWidth, 0);
1720
APInt Op1Min(BitWidth, 0), Op1Max(BitWidth, 0);
1722
ComputeSignedMinMaxValuesFromKnownBits(Op0KnownZero, Op0KnownOne,
1724
ComputeSignedMinMaxValuesFromKnownBits(Op1KnownZero, Op1KnownOne,
1727
ComputeUnsignedMinMaxValuesFromKnownBits(Op0KnownZero, Op0KnownOne,
1729
ComputeUnsignedMinMaxValuesFromKnownBits(Op1KnownZero, Op1KnownOne,
1733
// If Min and Max are known to be the same, then SimplifyDemandedBits
1734
// figured out that the LHS is a constant. Just constant fold this now so
1735
// that code below can assume that Min != Max.
1736
if (!isa<Constant>(Op0) && Op0Min == Op0Max)
1737
return new ICmpInst(I.getPredicate(),
1738
ConstantInt::get(I.getContext(), Op0Min), Op1);
1739
if (!isa<Constant>(Op1) && Op1Min == Op1Max)
1740
return new ICmpInst(I.getPredicate(), Op0,
1741
ConstantInt::get(I.getContext(), Op1Min));
1743
// Based on the range information we know about the LHS, see if we can
1744
// simplify this comparison. For example, (x&4) < 8 is always true.
1745
switch (I.getPredicate()) {
1746
default: llvm_unreachable("Unknown icmp opcode!");
1747
case ICmpInst::ICMP_EQ:
1748
if (Op0Max.ult(Op1Min) || Op0Min.ugt(Op1Max))
1749
return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
1751
case ICmpInst::ICMP_NE:
1752
if (Op0Max.ult(Op1Min) || Op0Min.ugt(Op1Max))
1753
return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
1755
case ICmpInst::ICMP_ULT:
1756
if (Op0Max.ult(Op1Min)) // A <u B -> true if max(A) < min(B)
1757
return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
1758
if (Op0Min.uge(Op1Max)) // A <u B -> false if min(A) >= max(B)
1759
return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
1760
if (Op1Min == Op0Max) // A <u B -> A != B if max(A) == min(B)
1761
return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
1762
if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
1763
if (Op1Max == Op0Min+1) // A <u C -> A == C-1 if min(A)+1 == C
1764
return new ICmpInst(ICmpInst::ICMP_EQ, Op0,
1765
ConstantInt::get(CI->getContext(), CI->getValue()-1));
1767
// (x <u 2147483648) -> (x >s -1) -> true if sign bit clear
1768
if (CI->isMinValue(true))
1769
return new ICmpInst(ICmpInst::ICMP_SGT, Op0,
1770
Constant::getAllOnesValue(Op0->getType()));
1773
case ICmpInst::ICMP_UGT:
1774
if (Op0Min.ugt(Op1Max)) // A >u B -> true if min(A) > max(B)
1775
return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
1776
if (Op0Max.ule(Op1Min)) // A >u B -> false if max(A) <= max(B)
1777
return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
1779
if (Op1Max == Op0Min) // A >u B -> A != B if min(A) == max(B)
1780
return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
1781
if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
1782
if (Op1Min == Op0Max-1) // A >u C -> A == C+1 if max(a)-1 == C
1783
return new ICmpInst(ICmpInst::ICMP_EQ, Op0,
1784
ConstantInt::get(CI->getContext(), CI->getValue()+1));
1786
// (x >u 2147483647) -> (x <s 0) -> true if sign bit set
1787
if (CI->isMaxValue(true))
1788
return new ICmpInst(ICmpInst::ICMP_SLT, Op0,
1789
Constant::getNullValue(Op0->getType()));
1792
case ICmpInst::ICMP_SLT:
1793
if (Op0Max.slt(Op1Min)) // A <s B -> true if max(A) < min(C)
1794
return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
1795
if (Op0Min.sge(Op1Max)) // A <s B -> false if min(A) >= max(C)
1796
return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
1797
if (Op1Min == Op0Max) // A <s B -> A != B if max(A) == min(B)
1798
return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
1799
if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
1800
if (Op1Max == Op0Min+1) // A <s C -> A == C-1 if min(A)+1 == C
1801
return new ICmpInst(ICmpInst::ICMP_EQ, Op0,
1802
ConstantInt::get(CI->getContext(), CI->getValue()-1));
1805
case ICmpInst::ICMP_SGT:
1806
if (Op0Min.sgt(Op1Max)) // A >s B -> true if min(A) > max(B)
1807
return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
1808
if (Op0Max.sle(Op1Min)) // A >s B -> false if max(A) <= min(B)
1809
return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
1811
if (Op1Max == Op0Min) // A >s B -> A != B if min(A) == max(B)
1812
return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
1813
if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
1814
if (Op1Min == Op0Max-1) // A >s C -> A == C+1 if max(A)-1 == C
1815
return new ICmpInst(ICmpInst::ICMP_EQ, Op0,
1816
ConstantInt::get(CI->getContext(), CI->getValue()+1));
1819
case ICmpInst::ICMP_SGE:
1820
assert(!isa<ConstantInt>(Op1) && "ICMP_SGE with ConstantInt not folded!");
1821
if (Op0Min.sge(Op1Max)) // A >=s B -> true if min(A) >= max(B)
1822
return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
1823
if (Op0Max.slt(Op1Min)) // A >=s B -> false if max(A) < min(B)
1824
return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
1826
case ICmpInst::ICMP_SLE:
1827
assert(!isa<ConstantInt>(Op1) && "ICMP_SLE with ConstantInt not folded!");
1828
if (Op0Max.sle(Op1Min)) // A <=s B -> true if max(A) <= min(B)
1829
return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
1830
if (Op0Min.sgt(Op1Max)) // A <=s B -> false if min(A) > max(B)
1831
return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
1833
case ICmpInst::ICMP_UGE:
1834
assert(!isa<ConstantInt>(Op1) && "ICMP_UGE with ConstantInt not folded!");
1835
if (Op0Min.uge(Op1Max)) // A >=u B -> true if min(A) >= max(B)
1836
return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
1837
if (Op0Max.ult(Op1Min)) // A >=u B -> false if max(A) < min(B)
1838
return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
1840
case ICmpInst::ICMP_ULE:
1841
assert(!isa<ConstantInt>(Op1) && "ICMP_ULE with ConstantInt not folded!");
1842
if (Op0Max.ule(Op1Min)) // A <=u B -> true if max(A) <= min(B)
1843
return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
1844
if (Op0Min.ugt(Op1Max)) // A <=u B -> false if min(A) > max(B)
1845
return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
1849
// Turn a signed comparison into an unsigned one if both operands
1850
// are known to have the same sign.
1852
((Op0KnownZero.isNegative() && Op1KnownZero.isNegative()) ||
1853
(Op0KnownOne.isNegative() && Op1KnownOne.isNegative())))
1854
return new ICmpInst(I.getUnsignedPredicate(), Op0, Op1);
1857
// Test if the ICmpInst instruction is used exclusively by a select as
1858
// part of a minimum or maximum operation. If so, refrain from doing
1859
// any other folding. This helps out other analyses which understand
1860
// non-obfuscated minimum and maximum idioms, such as ScalarEvolution
1861
// and CodeGen. And in this case, at least one of the comparison
1862
// operands has at least one user besides the compare (the select),
1863
// which would often largely negate the benefit of folding anyway.
1865
if (SelectInst *SI = dyn_cast<SelectInst>(*I.use_begin()))
1866
if ((SI->getOperand(1) == Op0 && SI->getOperand(2) == Op1) ||
1867
(SI->getOperand(2) == Op0 && SI->getOperand(1) == Op1))
1870
// See if we are doing a comparison between a constant and an instruction that
1871
// can be folded into the comparison.
1872
if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
1873
// Since the RHS is a ConstantInt (CI), if the left hand side is an
1874
// instruction, see if that instruction also has constants so that the
1875
// instruction can be folded into the icmp
1876
if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
1877
if (Instruction *Res = visitICmpInstWithInstAndIntCst(I, LHSI, CI))
1881
// Handle icmp with constant (but not simple integer constant) RHS
1882
if (Constant *RHSC = dyn_cast<Constant>(Op1)) {
1883
if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
1884
switch (LHSI->getOpcode()) {
1885
case Instruction::GetElementPtr:
1886
// icmp pred GEP (P, int 0, int 0, int 0), null -> icmp pred P, null
1887
if (RHSC->isNullValue() &&
1888
cast<GetElementPtrInst>(LHSI)->hasAllZeroIndices())
1889
return new ICmpInst(I.getPredicate(), LHSI->getOperand(0),
1890
Constant::getNullValue(LHSI->getOperand(0)->getType()));
1892
case Instruction::PHI:
1893
// Only fold icmp into the PHI if the phi and icmp are in the same
1894
// block. If in the same block, we're encouraging jump threading. If
1895
// not, we are just pessimizing the code by making an i1 phi.
1896
if (LHSI->getParent() == I.getParent())
1897
if (Instruction *NV = FoldOpIntoPhi(I, true))
1900
case Instruction::Select: {
1901
// If either operand of the select is a constant, we can fold the
1902
// comparison into the select arms, which will cause one to be
1903
// constant folded and the select turned into a bitwise or.
1904
Value *Op1 = 0, *Op2 = 0;
1905
if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(1)))
1906
Op1 = ConstantExpr::getICmp(I.getPredicate(), C, RHSC);
1907
if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(2)))
1908
Op2 = ConstantExpr::getICmp(I.getPredicate(), C, RHSC);
1910
// We only want to perform this transformation if it will not lead to
1911
// additional code. This is true if either both sides of the select
1912
// fold to a constant (in which case the icmp is replaced with a select
1913
// which will usually simplify) or this is the only user of the
1914
// select (in which case we are trading a select+icmp for a simpler
1916
if ((Op1 && Op2) || (LHSI->hasOneUse() && (Op1 || Op2))) {
1918
Op1 = Builder->CreateICmp(I.getPredicate(), LHSI->getOperand(1),
1921
Op2 = Builder->CreateICmp(I.getPredicate(), LHSI->getOperand(2),
1923
return SelectInst::Create(LHSI->getOperand(0), Op1, Op2);
1927
case Instruction::Call:
1928
// If we have (malloc != null), and if the malloc has a single use, we
1929
// can assume it is successful and remove the malloc.
1930
if (isMalloc(LHSI) && LHSI->hasOneUse() &&
1931
isa<ConstantPointerNull>(RHSC)) {
1932
// Need to explicitly erase malloc call here, instead of adding it to
1933
// Worklist, because it won't get DCE'd from the Worklist since
1934
// isInstructionTriviallyDead() returns false for function calls.
1935
// It is OK to replace LHSI/MallocCall with Undef because the
1936
// instruction that uses it will be erased via Worklist.
1937
if (extractMallocCall(LHSI)) {
1938
LHSI->replaceAllUsesWith(UndefValue::get(LHSI->getType()));
1939
EraseInstFromFunction(*LHSI);
1940
return ReplaceInstUsesWith(I,
1941
ConstantInt::get(Type::getInt1Ty(I.getContext()),
1942
!I.isTrueWhenEqual()));
1944
if (CallInst* MallocCall = extractMallocCallFromBitCast(LHSI))
1945
if (MallocCall->hasOneUse()) {
1946
MallocCall->replaceAllUsesWith(
1947
UndefValue::get(MallocCall->getType()));
1948
EraseInstFromFunction(*MallocCall);
1949
Worklist.Add(LHSI); // The malloc's bitcast use.
1950
return ReplaceInstUsesWith(I,
1951
ConstantInt::get(Type::getInt1Ty(I.getContext()),
1952
!I.isTrueWhenEqual()));
1956
case Instruction::IntToPtr:
1957
// icmp pred inttoptr(X), null -> icmp pred X, 0
1958
if (RHSC->isNullValue() && TD &&
1959
TD->getIntPtrType(RHSC->getContext()) ==
1960
LHSI->getOperand(0)->getType())
1961
return new ICmpInst(I.getPredicate(), LHSI->getOperand(0),
1962
Constant::getNullValue(LHSI->getOperand(0)->getType()));
1965
case Instruction::Load:
1966
// Try to optimize things like "A[i] > 4" to index computations.
1967
if (GetElementPtrInst *GEP =
1968
dyn_cast<GetElementPtrInst>(LHSI->getOperand(0))) {
1969
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)))
1970
if (GV->isConstant() && GV->hasDefinitiveInitializer() &&
1971
!cast<LoadInst>(LHSI)->isVolatile())
1972
if (Instruction *Res = FoldCmpLoadFromIndexedGlobal(GEP, GV, I))
1979
// If we can optimize a 'icmp GEP, P' or 'icmp P, GEP', do so now.
1980
if (GEPOperator *GEP = dyn_cast<GEPOperator>(Op0))
1981
if (Instruction *NI = FoldGEPICmp(GEP, Op1, I.getPredicate(), I))
1983
if (GEPOperator *GEP = dyn_cast<GEPOperator>(Op1))
1984
if (Instruction *NI = FoldGEPICmp(GEP, Op0,
1985
ICmpInst::getSwappedPredicate(I.getPredicate()), I))
1988
// Test to see if the operands of the icmp are casted versions of other
1989
// values. If the ptr->ptr cast can be stripped off both arguments, we do so
1991
if (BitCastInst *CI = dyn_cast<BitCastInst>(Op0)) {
1992
if (Op0->getType()->isPointerTy() &&
1993
(isa<Constant>(Op1) || isa<BitCastInst>(Op1))) {
1994
// We keep moving the cast from the left operand over to the right
1995
// operand, where it can often be eliminated completely.
1996
Op0 = CI->getOperand(0);
1998
// If operand #1 is a bitcast instruction, it must also be a ptr->ptr cast
1999
// so eliminate it as well.
2000
if (BitCastInst *CI2 = dyn_cast<BitCastInst>(Op1))
2001
Op1 = CI2->getOperand(0);
2003
// If Op1 is a constant, we can fold the cast into the constant.
2004
if (Op0->getType() != Op1->getType()) {
2005
if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
2006
Op1 = ConstantExpr::getBitCast(Op1C, Op0->getType());
2008
// Otherwise, cast the RHS right before the icmp
2009
Op1 = Builder->CreateBitCast(Op1, Op0->getType());
2012
return new ICmpInst(I.getPredicate(), Op0, Op1);
2016
if (isa<CastInst>(Op0)) {
2017
// Handle the special case of: icmp (cast bool to X), <cst>
2018
// This comes up when you have code like
2021
// For generality, we handle any zero-extension of any operand comparison
2022
// with a constant or another cast from the same type.
2023
if (isa<Constant>(Op1) || isa<CastInst>(Op1))
2024
if (Instruction *R = visitICmpInstWithCastAndCast(I))
2028
// See if it's the same type of instruction on the left and right.
2029
if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
2030
if (BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1)) {
2031
if (Op0I->getOpcode() == Op1I->getOpcode() && Op0I->hasOneUse() &&
2032
Op1I->hasOneUse() && Op0I->getOperand(1) == Op1I->getOperand(1)) {
2033
switch (Op0I->getOpcode()) {
2035
case Instruction::Add:
2036
case Instruction::Sub:
2037
case Instruction::Xor:
2038
if (I.isEquality()) // a+x icmp eq/ne b+x --> a icmp b
2039
return new ICmpInst(I.getPredicate(), Op0I->getOperand(0),
2040
Op1I->getOperand(0));
2041
// icmp u/s (a ^ signbit), (b ^ signbit) --> icmp s/u a, b
2042
if (ConstantInt *CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
2043
if (CI->getValue().isSignBit()) {
2044
ICmpInst::Predicate Pred = I.isSigned()
2045
? I.getUnsignedPredicate()
2046
: I.getSignedPredicate();
2047
return new ICmpInst(Pred, Op0I->getOperand(0),
2048
Op1I->getOperand(0));
2051
if (CI->getValue().isMaxSignedValue()) {
2052
ICmpInst::Predicate Pred = I.isSigned()
2053
? I.getUnsignedPredicate()
2054
: I.getSignedPredicate();
2055
Pred = I.getSwappedPredicate(Pred);
2056
return new ICmpInst(Pred, Op0I->getOperand(0),
2057
Op1I->getOperand(0));
2061
case Instruction::Mul:
2062
if (!I.isEquality())
2065
if (ConstantInt *CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
2066
// a * Cst icmp eq/ne b * Cst --> a & Mask icmp b & Mask
2067
// Mask = -1 >> count-trailing-zeros(Cst).
2068
if (!CI->isZero() && !CI->isOne()) {
2069
const APInt &AP = CI->getValue();
2070
ConstantInt *Mask = ConstantInt::get(I.getContext(),
2071
APInt::getLowBitsSet(AP.getBitWidth(),
2073
AP.countTrailingZeros()));
2074
Value *And1 = Builder->CreateAnd(Op0I->getOperand(0), Mask);
2075
Value *And2 = Builder->CreateAnd(Op1I->getOperand(0), Mask);
2076
return new ICmpInst(I.getPredicate(), And1, And2);
2085
// ~x < ~y --> y < x
2087
if (match(Op0, m_Not(m_Value(A))) &&
2088
match(Op1, m_Not(m_Value(B))))
2089
return new ICmpInst(I.getPredicate(), B, A);
2092
if (I.isEquality()) {
2093
Value *A, *B, *C, *D;
2095
// -x == -y --> x == y
2096
if (match(Op0, m_Neg(m_Value(A))) &&
2097
match(Op1, m_Neg(m_Value(B))))
2098
return new ICmpInst(I.getPredicate(), A, B);
2100
if (match(Op0, m_Xor(m_Value(A), m_Value(B)))) {
2101
if (A == Op1 || B == Op1) { // (A^B) == A -> B == 0
2102
Value *OtherVal = A == Op1 ? B : A;
2103
return new ICmpInst(I.getPredicate(), OtherVal,
2104
Constant::getNullValue(A->getType()));
2107
if (match(Op1, m_Xor(m_Value(C), m_Value(D)))) {
2108
// A^c1 == C^c2 --> A == C^(c1^c2)
2109
ConstantInt *C1, *C2;
2110
if (match(B, m_ConstantInt(C1)) &&
2111
match(D, m_ConstantInt(C2)) && Op1->hasOneUse()) {
2112
Constant *NC = ConstantInt::get(I.getContext(),
2113
C1->getValue() ^ C2->getValue());
2114
Value *Xor = Builder->CreateXor(C, NC, "tmp");
2115
return new ICmpInst(I.getPredicate(), A, Xor);
2118
// A^B == A^D -> B == D
2119
if (A == C) return new ICmpInst(I.getPredicate(), B, D);
2120
if (A == D) return new ICmpInst(I.getPredicate(), B, C);
2121
if (B == C) return new ICmpInst(I.getPredicate(), A, D);
2122
if (B == D) return new ICmpInst(I.getPredicate(), A, C);
2126
if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
2127
(A == Op0 || B == Op0)) {
2128
// A == (A^B) -> B == 0
2129
Value *OtherVal = A == Op0 ? B : A;
2130
return new ICmpInst(I.getPredicate(), OtherVal,
2131
Constant::getNullValue(A->getType()));
2134
// (A-B) == A -> B == 0
2135
if (match(Op0, m_Sub(m_Specific(Op1), m_Value(B))))
2136
return new ICmpInst(I.getPredicate(), B,
2137
Constant::getNullValue(B->getType()));
2139
// A == (A-B) -> B == 0
2140
if (match(Op1, m_Sub(m_Specific(Op0), m_Value(B))))
2141
return new ICmpInst(I.getPredicate(), B,
2142
Constant::getNullValue(B->getType()));
2144
// (X&Z) == (Y&Z) -> (X^Y) & Z == 0
2145
if (Op0->hasOneUse() && Op1->hasOneUse() &&
2146
match(Op0, m_And(m_Value(A), m_Value(B))) &&
2147
match(Op1, m_And(m_Value(C), m_Value(D)))) {
2148
Value *X = 0, *Y = 0, *Z = 0;
2151
X = B; Y = D; Z = A;
2152
} else if (A == D) {
2153
X = B; Y = C; Z = A;
2154
} else if (B == C) {
2155
X = A; Y = D; Z = B;
2156
} else if (B == D) {
2157
X = A; Y = C; Z = B;
2160
if (X) { // Build (X^Y) & Z
2161
Op1 = Builder->CreateXor(X, Y, "tmp");
2162
Op1 = Builder->CreateAnd(Op1, Z, "tmp");
2163
I.setOperand(0, Op1);
2164
I.setOperand(1, Constant::getNullValue(Op1->getType()));
2171
Value *X; ConstantInt *Cst;
2173
if (match(Op0, m_Add(m_Value(X), m_ConstantInt(Cst))) && Op1 == X)
2174
return FoldICmpAddOpCst(I, X, Cst, I.getPredicate(), Op0);
2177
if (match(Op1, m_Add(m_Value(X), m_ConstantInt(Cst))) && Op0 == X)
2178
return FoldICmpAddOpCst(I, X, Cst, I.getSwappedPredicate(), Op1);
2180
return Changed ? &I : 0;
2188
/// FoldFCmp_IntToFP_Cst - Fold fcmp ([us]itofp x, cst) if possible.
2190
Instruction *InstCombiner::FoldFCmp_IntToFP_Cst(FCmpInst &I,
2193
if (!isa<ConstantFP>(RHSC)) return 0;
2194
const APFloat &RHS = cast<ConstantFP>(RHSC)->getValueAPF();
2196
// Get the width of the mantissa. We don't want to hack on conversions that
2197
// might lose information from the integer, e.g. "i64 -> float"
2198
int MantissaWidth = LHSI->getType()->getFPMantissaWidth();
2199
if (MantissaWidth == -1) return 0; // Unknown.
2201
// Check to see that the input is converted from an integer type that is small
2202
// enough that preserves all bits. TODO: check here for "known" sign bits.
2203
// This would allow us to handle (fptosi (x >>s 62) to float) if x is i64 f.e.
2204
unsigned InputSize = LHSI->getOperand(0)->getType()->getScalarSizeInBits();
2206
// If this is a uitofp instruction, we need an extra bit to hold the sign.
2207
bool LHSUnsigned = isa<UIToFPInst>(LHSI);
2211
// If the conversion would lose info, don't hack on this.
2212
if ((int)InputSize > MantissaWidth)
2215
// Otherwise, we can potentially simplify the comparison. We know that it
2216
// will always come through as an integer value and we know the constant is
2217
// not a NAN (it would have been previously simplified).
2218
assert(!RHS.isNaN() && "NaN comparison not already folded!");
2220
ICmpInst::Predicate Pred;
2221
switch (I.getPredicate()) {
2222
default: llvm_unreachable("Unexpected predicate!");
2223
case FCmpInst::FCMP_UEQ:
2224
case FCmpInst::FCMP_OEQ:
2225
Pred = ICmpInst::ICMP_EQ;
2227
case FCmpInst::FCMP_UGT:
2228
case FCmpInst::FCMP_OGT:
2229
Pred = LHSUnsigned ? ICmpInst::ICMP_UGT : ICmpInst::ICMP_SGT;
2231
case FCmpInst::FCMP_UGE:
2232
case FCmpInst::FCMP_OGE:
2233
Pred = LHSUnsigned ? ICmpInst::ICMP_UGE : ICmpInst::ICMP_SGE;
2235
case FCmpInst::FCMP_ULT:
2236
case FCmpInst::FCMP_OLT:
2237
Pred = LHSUnsigned ? ICmpInst::ICMP_ULT : ICmpInst::ICMP_SLT;
2239
case FCmpInst::FCMP_ULE:
2240
case FCmpInst::FCMP_OLE:
2241
Pred = LHSUnsigned ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_SLE;
2243
case FCmpInst::FCMP_UNE:
2244
case FCmpInst::FCMP_ONE:
2245
Pred = ICmpInst::ICMP_NE;
2247
case FCmpInst::FCMP_ORD:
2248
return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
2249
case FCmpInst::FCMP_UNO:
2250
return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
2253
const IntegerType *IntTy = cast<IntegerType>(LHSI->getOperand(0)->getType());
2255
// Now we know that the APFloat is a normal number, zero or inf.
2257
// See if the FP constant is too large for the integer. For example,
2258
// comparing an i8 to 300.0.
2259
unsigned IntWidth = IntTy->getScalarSizeInBits();
2262
// If the RHS value is > SignedMax, fold the comparison. This handles +INF
2263
// and large values.
2264
APFloat SMax(RHS.getSemantics(), APFloat::fcZero, false);
2265
SMax.convertFromAPInt(APInt::getSignedMaxValue(IntWidth), true,
2266
APFloat::rmNearestTiesToEven);
2267
if (SMax.compare(RHS) == APFloat::cmpLessThan) { // smax < 13123.0
2268
if (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_SLT ||
2269
Pred == ICmpInst::ICMP_SLE)
2270
return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
2271
return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
2274
// If the RHS value is > UnsignedMax, fold the comparison. This handles
2275
// +INF and large values.
2276
APFloat UMax(RHS.getSemantics(), APFloat::fcZero, false);
2277
UMax.convertFromAPInt(APInt::getMaxValue(IntWidth), false,
2278
APFloat::rmNearestTiesToEven);
2279
if (UMax.compare(RHS) == APFloat::cmpLessThan) { // umax < 13123.0
2280
if (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_ULT ||
2281
Pred == ICmpInst::ICMP_ULE)
2282
return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
2283
return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
2288
// See if the RHS value is < SignedMin.
2289
APFloat SMin(RHS.getSemantics(), APFloat::fcZero, false);
2290
SMin.convertFromAPInt(APInt::getSignedMinValue(IntWidth), true,
2291
APFloat::rmNearestTiesToEven);
2292
if (SMin.compare(RHS) == APFloat::cmpGreaterThan) { // smin > 12312.0
2293
if (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_SGT ||
2294
Pred == ICmpInst::ICMP_SGE)
2295
return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
2296
return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
2300
// Okay, now we know that the FP constant fits in the range [SMIN, SMAX] or
2301
// [0, UMAX], but it may still be fractional. See if it is fractional by
2302
// casting the FP value to the integer value and back, checking for equality.
2303
// Don't do this for zero, because -0.0 is not fractional.
2304
Constant *RHSInt = LHSUnsigned
2305
? ConstantExpr::getFPToUI(RHSC, IntTy)
2306
: ConstantExpr::getFPToSI(RHSC, IntTy);
2307
if (!RHS.isZero()) {
2308
bool Equal = LHSUnsigned
2309
? ConstantExpr::getUIToFP(RHSInt, RHSC->getType()) == RHSC
2310
: ConstantExpr::getSIToFP(RHSInt, RHSC->getType()) == RHSC;
2312
// If we had a comparison against a fractional value, we have to adjust
2313
// the compare predicate and sometimes the value. RHSC is rounded towards
2314
// zero at this point.
2316
default: llvm_unreachable("Unexpected integer comparison!");
2317
case ICmpInst::ICMP_NE: // (float)int != 4.4 --> true
2318
return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
2319
case ICmpInst::ICMP_EQ: // (float)int == 4.4 --> false
2320
return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
2321
case ICmpInst::ICMP_ULE:
2322
// (float)int <= 4.4 --> int <= 4
2323
// (float)int <= -4.4 --> false
2324
if (RHS.isNegative())
2325
return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
2327
case ICmpInst::ICMP_SLE:
2328
// (float)int <= 4.4 --> int <= 4
2329
// (float)int <= -4.4 --> int < -4
2330
if (RHS.isNegative())
2331
Pred = ICmpInst::ICMP_SLT;
2333
case ICmpInst::ICMP_ULT:
2334
// (float)int < -4.4 --> false
2335
// (float)int < 4.4 --> int <= 4
2336
if (RHS.isNegative())
2337
return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
2338
Pred = ICmpInst::ICMP_ULE;
2340
case ICmpInst::ICMP_SLT:
2341
// (float)int < -4.4 --> int < -4
2342
// (float)int < 4.4 --> int <= 4
2343
if (!RHS.isNegative())
2344
Pred = ICmpInst::ICMP_SLE;
2346
case ICmpInst::ICMP_UGT:
2347
// (float)int > 4.4 --> int > 4
2348
// (float)int > -4.4 --> true
2349
if (RHS.isNegative())
2350
return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
2352
case ICmpInst::ICMP_SGT:
2353
// (float)int > 4.4 --> int > 4
2354
// (float)int > -4.4 --> int >= -4
2355
if (RHS.isNegative())
2356
Pred = ICmpInst::ICMP_SGE;
2358
case ICmpInst::ICMP_UGE:
2359
// (float)int >= -4.4 --> true
2360
// (float)int >= 4.4 --> int > 4
2361
if (!RHS.isNegative())
2362
return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
2363
Pred = ICmpInst::ICMP_UGT;
2365
case ICmpInst::ICMP_SGE:
2366
// (float)int >= -4.4 --> int >= -4
2367
// (float)int >= 4.4 --> int > 4
2368
if (!RHS.isNegative())
2369
Pred = ICmpInst::ICMP_SGT;
2375
// Lower this FP comparison into an appropriate integer version of the
2377
return new ICmpInst(Pred, LHSI->getOperand(0), RHSInt);
2380
Instruction *InstCombiner::visitFCmpInst(FCmpInst &I) {
2381
bool Changed = false;
2383
/// Orders the operands of the compare so that they are listed from most
2384
/// complex to least complex. This puts constants before unary operators,
2385
/// before binary operators.
2386
if (getComplexity(I.getOperand(0)) < getComplexity(I.getOperand(1))) {
2391
Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2393
if (Value *V = SimplifyFCmpInst(I.getPredicate(), Op0, Op1, TD))
2394
return ReplaceInstUsesWith(I, V);
2396
// Simplify 'fcmp pred X, X'
2398
switch (I.getPredicate()) {
2399
default: llvm_unreachable("Unknown predicate!");
2400
case FCmpInst::FCMP_UNO: // True if unordered: isnan(X) | isnan(Y)
2401
case FCmpInst::FCMP_ULT: // True if unordered or less than
2402
case FCmpInst::FCMP_UGT: // True if unordered or greater than
2403
case FCmpInst::FCMP_UNE: // True if unordered or not equal
2404
// Canonicalize these to be 'fcmp uno %X, 0.0'.
2405
I.setPredicate(FCmpInst::FCMP_UNO);
2406
I.setOperand(1, Constant::getNullValue(Op0->getType()));
2409
case FCmpInst::FCMP_ORD: // True if ordered (no nans)
2410
case FCmpInst::FCMP_OEQ: // True if ordered and equal
2411
case FCmpInst::FCMP_OGE: // True if ordered and greater than or equal
2412
case FCmpInst::FCMP_OLE: // True if ordered and less than or equal
2413
// Canonicalize these to be 'fcmp ord %X, 0.0'.
2414
I.setPredicate(FCmpInst::FCMP_ORD);
2415
I.setOperand(1, Constant::getNullValue(Op0->getType()));
2420
// Handle fcmp with constant RHS
2421
if (Constant *RHSC = dyn_cast<Constant>(Op1)) {
2422
if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
2423
switch (LHSI->getOpcode()) {
2424
case Instruction::PHI:
2425
// Only fold fcmp into the PHI if the phi and fcmp are in the same
2426
// block. If in the same block, we're encouraging jump threading. If
2427
// not, we are just pessimizing the code by making an i1 phi.
2428
if (LHSI->getParent() == I.getParent())
2429
if (Instruction *NV = FoldOpIntoPhi(I, true))
2432
case Instruction::SIToFP:
2433
case Instruction::UIToFP:
2434
if (Instruction *NV = FoldFCmp_IntToFP_Cst(I, LHSI, RHSC))
2437
case Instruction::Select: {
2438
// If either operand of the select is a constant, we can fold the
2439
// comparison into the select arms, which will cause one to be
2440
// constant folded and the select turned into a bitwise or.
2441
Value *Op1 = 0, *Op2 = 0;
2442
if (LHSI->hasOneUse()) {
2443
if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(1))) {
2444
// Fold the known value into the constant operand.
2445
Op1 = ConstantExpr::getCompare(I.getPredicate(), C, RHSC);
2446
// Insert a new FCmp of the other select operand.
2447
Op2 = Builder->CreateFCmp(I.getPredicate(),
2448
LHSI->getOperand(2), RHSC, I.getName());
2449
} else if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(2))) {
2450
// Fold the known value into the constant operand.
2451
Op2 = ConstantExpr::getCompare(I.getPredicate(), C, RHSC);
2452
// Insert a new FCmp of the other select operand.
2453
Op1 = Builder->CreateFCmp(I.getPredicate(), LHSI->getOperand(1),
2459
return SelectInst::Create(LHSI->getOperand(0), Op1, Op2);
2462
case Instruction::Load:
2463
if (GetElementPtrInst *GEP =
2464
dyn_cast<GetElementPtrInst>(LHSI->getOperand(0))) {
2465
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)))
2466
if (GV->isConstant() && GV->hasDefinitiveInitializer() &&
2467
!cast<LoadInst>(LHSI)->isVolatile())
2468
if (Instruction *Res = FoldCmpLoadFromIndexedGlobal(GEP, GV, I))
2475
return Changed ? &I : 0;
added
removed
libclamav/c++/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
