InstCombineCompares.cpp revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f
1//===- InstCombineCompares.cpp --------------------------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the visitICmp and visitFCmp functions. 11// 12//===----------------------------------------------------------------------===// 13 14#include "InstCombine.h" 15#include "llvm/Analysis/ConstantFolding.h" 16#include "llvm/Analysis/InstructionSimplify.h" 17#include "llvm/Analysis/MemoryBuiltins.h" 18#include "llvm/IR/ConstantRange.h" 19#include "llvm/IR/DataLayout.h" 20#include "llvm/IR/GetElementPtrTypeIterator.h" 21#include "llvm/IR/IntrinsicInst.h" 22#include "llvm/IR/PatternMatch.h" 23#include "llvm/Target/TargetLibraryInfo.h" 24using namespace llvm; 25using namespace PatternMatch; 26 27#define DEBUG_TYPE "instcombine" 28 29static ConstantInt *getOne(Constant *C) { 30 return ConstantInt::get(cast<IntegerType>(C->getType()), 1); 31} 32 33static ConstantInt *ExtractElement(Constant *V, Constant *Idx) { 34 return cast<ConstantInt>(ConstantExpr::getExtractElement(V, Idx)); 35} 36 37static bool HasAddOverflow(ConstantInt *Result, 38 ConstantInt *In1, ConstantInt *In2, 39 bool IsSigned) { 40 if (!IsSigned) 41 return Result->getValue().ult(In1->getValue()); 42 43 if (In2->isNegative()) 44 return Result->getValue().sgt(In1->getValue()); 45 return Result->getValue().slt(In1->getValue()); 46} 47 48/// AddWithOverflow - Compute Result = In1+In2, returning true if the result 49/// overflowed for this type. 50static bool AddWithOverflow(Constant *&Result, Constant *In1, 51 Constant *In2, bool IsSigned = false) { 52 Result = ConstantExpr::getAdd(In1, In2); 53 54 if (VectorType *VTy = dyn_cast<VectorType>(In1->getType())) { 55 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 56 Constant *Idx = ConstantInt::get(Type::getInt32Ty(In1->getContext()), i); 57 if (HasAddOverflow(ExtractElement(Result, Idx), 58 ExtractElement(In1, Idx), 59 ExtractElement(In2, Idx), 60 IsSigned)) 61 return true; 62 } 63 return false; 64 } 65 66 return HasAddOverflow(cast<ConstantInt>(Result), 67 cast<ConstantInt>(In1), cast<ConstantInt>(In2), 68 IsSigned); 69} 70 71static bool HasSubOverflow(ConstantInt *Result, 72 ConstantInt *In1, ConstantInt *In2, 73 bool IsSigned) { 74 if (!IsSigned) 75 return Result->getValue().ugt(In1->getValue()); 76 77 if (In2->isNegative()) 78 return Result->getValue().slt(In1->getValue()); 79 80 return Result->getValue().sgt(In1->getValue()); 81} 82 83/// SubWithOverflow - Compute Result = In1-In2, returning true if the result 84/// overflowed for this type. 85static bool SubWithOverflow(Constant *&Result, Constant *In1, 86 Constant *In2, bool IsSigned = false) { 87 Result = ConstantExpr::getSub(In1, In2); 88 89 if (VectorType *VTy = dyn_cast<VectorType>(In1->getType())) { 90 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 91 Constant *Idx = ConstantInt::get(Type::getInt32Ty(In1->getContext()), i); 92 if (HasSubOverflow(ExtractElement(Result, Idx), 93 ExtractElement(In1, Idx), 94 ExtractElement(In2, Idx), 95 IsSigned)) 96 return true; 97 } 98 return false; 99 } 100 101 return HasSubOverflow(cast<ConstantInt>(Result), 102 cast<ConstantInt>(In1), cast<ConstantInt>(In2), 103 IsSigned); 104} 105 106/// isSignBitCheck - Given an exploded icmp instruction, return true if the 107/// comparison only checks the sign bit. If it only checks the sign bit, set 108/// TrueIfSigned if the result of the comparison is true when the input value is 109/// signed. 110static bool isSignBitCheck(ICmpInst::Predicate pred, ConstantInt *RHS, 111 bool &TrueIfSigned) { 112 switch (pred) { 113 case ICmpInst::ICMP_SLT: // True if LHS s< 0 114 TrueIfSigned = true; 115 return RHS->isZero(); 116 case ICmpInst::ICMP_SLE: // True if LHS s<= RHS and RHS == -1 117 TrueIfSigned = true; 118 return RHS->isAllOnesValue(); 119 case ICmpInst::ICMP_SGT: // True if LHS s> -1 120 TrueIfSigned = false; 121 return RHS->isAllOnesValue(); 122 case ICmpInst::ICMP_UGT: 123 // True if LHS u> RHS and RHS == high-bit-mask - 1 124 TrueIfSigned = true; 125 return RHS->isMaxValue(true); 126 case ICmpInst::ICMP_UGE: 127 // True if LHS u>= RHS and RHS == high-bit-mask (2^7, 2^15, 2^31, etc) 128 TrueIfSigned = true; 129 return RHS->getValue().isSignBit(); 130 default: 131 return false; 132 } 133} 134 135/// Returns true if the exploded icmp can be expressed as a signed comparison 136/// to zero and updates the predicate accordingly. 137/// The signedness of the comparison is preserved. 138static bool isSignTest(ICmpInst::Predicate &pred, const ConstantInt *RHS) { 139 if (!ICmpInst::isSigned(pred)) 140 return false; 141 142 if (RHS->isZero()) 143 return ICmpInst::isRelational(pred); 144 145 if (RHS->isOne()) { 146 if (pred == ICmpInst::ICMP_SLT) { 147 pred = ICmpInst::ICMP_SLE; 148 return true; 149 } 150 } else if (RHS->isAllOnesValue()) { 151 if (pred == ICmpInst::ICMP_SGT) { 152 pred = ICmpInst::ICMP_SGE; 153 return true; 154 } 155 } 156 157 return false; 158} 159 160// isHighOnes - Return true if the constant is of the form 1+0+. 161// This is the same as lowones(~X). 162static bool isHighOnes(const ConstantInt *CI) { 163 return (~CI->getValue() + 1).isPowerOf2(); 164} 165 166/// ComputeSignedMinMaxValuesFromKnownBits - Given a signed integer type and a 167/// set of known zero and one bits, compute the maximum and minimum values that 168/// could have the specified known zero and known one bits, returning them in 169/// min/max. 170static void ComputeSignedMinMaxValuesFromKnownBits(const APInt& KnownZero, 171 const APInt& KnownOne, 172 APInt& Min, APInt& Max) { 173 assert(KnownZero.getBitWidth() == KnownOne.getBitWidth() && 174 KnownZero.getBitWidth() == Min.getBitWidth() && 175 KnownZero.getBitWidth() == Max.getBitWidth() && 176 "KnownZero, KnownOne and Min, Max must have equal bitwidth."); 177 APInt UnknownBits = ~(KnownZero|KnownOne); 178 179 // The minimum value is when all unknown bits are zeros, EXCEPT for the sign 180 // bit if it is unknown. 181 Min = KnownOne; 182 Max = KnownOne|UnknownBits; 183 184 if (UnknownBits.isNegative()) { // Sign bit is unknown 185 Min.setBit(Min.getBitWidth()-1); 186 Max.clearBit(Max.getBitWidth()-1); 187 } 188} 189 190// ComputeUnsignedMinMaxValuesFromKnownBits - Given an unsigned integer type and 191// a set of known zero and one bits, compute the maximum and minimum values that 192// could have the specified known zero and known one bits, returning them in 193// min/max. 194static void ComputeUnsignedMinMaxValuesFromKnownBits(const APInt &KnownZero, 195 const APInt &KnownOne, 196 APInt &Min, APInt &Max) { 197 assert(KnownZero.getBitWidth() == KnownOne.getBitWidth() && 198 KnownZero.getBitWidth() == Min.getBitWidth() && 199 KnownZero.getBitWidth() == Max.getBitWidth() && 200 "Ty, KnownZero, KnownOne and Min, Max must have equal bitwidth."); 201 APInt UnknownBits = ~(KnownZero|KnownOne); 202 203 // The minimum value is when the unknown bits are all zeros. 204 Min = KnownOne; 205 // The maximum value is when the unknown bits are all ones. 206 Max = KnownOne|UnknownBits; 207} 208 209 210 211/// FoldCmpLoadFromIndexedGlobal - Called we see this pattern: 212/// cmp pred (load (gep GV, ...)), cmpcst 213/// where GV is a global variable with a constant initializer. Try to simplify 214/// this into some simple computation that does not need the load. For example 215/// we can optimize "icmp eq (load (gep "foo", 0, i)), 0" into "icmp eq i, 3". 216/// 217/// If AndCst is non-null, then the loaded value is masked with that constant 218/// before doing the comparison. This handles cases like "A[i]&4 == 0". 219Instruction *InstCombiner:: 220FoldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP, GlobalVariable *GV, 221 CmpInst &ICI, ConstantInt *AndCst) { 222 // We need TD information to know the pointer size unless this is inbounds. 223 if (!GEP->isInBounds() && !DL) 224 return nullptr; 225 226 Constant *Init = GV->getInitializer(); 227 if (!isa<ConstantArray>(Init) && !isa<ConstantDataArray>(Init)) 228 return nullptr; 229 230 uint64_t ArrayElementCount = Init->getType()->getArrayNumElements(); 231 if (ArrayElementCount > 1024) return nullptr; // Don't blow up on huge arrays. 232 233 // There are many forms of this optimization we can handle, for now, just do 234 // the simple index into a single-dimensional array. 235 // 236 // Require: GEP GV, 0, i {{, constant indices}} 237 if (GEP->getNumOperands() < 3 || 238 !isa<ConstantInt>(GEP->getOperand(1)) || 239 !cast<ConstantInt>(GEP->getOperand(1))->isZero() || 240 isa<Constant>(GEP->getOperand(2))) 241 return nullptr; 242 243 // Check that indices after the variable are constants and in-range for the 244 // type they index. Collect the indices. This is typically for arrays of 245 // structs. 246 SmallVector<unsigned, 4> LaterIndices; 247 248 Type *EltTy = Init->getType()->getArrayElementType(); 249 for (unsigned i = 3, e = GEP->getNumOperands(); i != e; ++i) { 250 ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(i)); 251 if (!Idx) return nullptr; // Variable index. 252 253 uint64_t IdxVal = Idx->getZExtValue(); 254 if ((unsigned)IdxVal != IdxVal) return nullptr; // Too large array index. 255 256 if (StructType *STy = dyn_cast<StructType>(EltTy)) 257 EltTy = STy->getElementType(IdxVal); 258 else if (ArrayType *ATy = dyn_cast<ArrayType>(EltTy)) { 259 if (IdxVal >= ATy->getNumElements()) return nullptr; 260 EltTy = ATy->getElementType(); 261 } else { 262 return nullptr; // Unknown type. 263 } 264 265 LaterIndices.push_back(IdxVal); 266 } 267 268 enum { Overdefined = -3, Undefined = -2 }; 269 270 // Variables for our state machines. 271 272 // FirstTrueElement/SecondTrueElement - Used to emit a comparison of the form 273 // "i == 47 | i == 87", where 47 is the first index the condition is true for, 274 // and 87 is the second (and last) index. FirstTrueElement is -2 when 275 // undefined, otherwise set to the first true element. SecondTrueElement is 276 // -2 when undefined, -3 when overdefined and >= 0 when that index is true. 277 int FirstTrueElement = Undefined, SecondTrueElement = Undefined; 278 279 // FirstFalseElement/SecondFalseElement - Used to emit a comparison of the 280 // form "i != 47 & i != 87". Same state transitions as for true elements. 281 int FirstFalseElement = Undefined, SecondFalseElement = Undefined; 282 283 /// TrueRangeEnd/FalseRangeEnd - In conjunction with First*Element, these 284 /// define a state machine that triggers for ranges of values that the index 285 /// is true or false for. This triggers on things like "abbbbc"[i] == 'b'. 286 /// This is -2 when undefined, -3 when overdefined, and otherwise the last 287 /// index in the range (inclusive). We use -2 for undefined here because we 288 /// use relative comparisons and don't want 0-1 to match -1. 289 int TrueRangeEnd = Undefined, FalseRangeEnd = Undefined; 290 291 // MagicBitvector - This is a magic bitvector where we set a bit if the 292 // comparison is true for element 'i'. If there are 64 elements or less in 293 // the array, this will fully represent all the comparison results. 294 uint64_t MagicBitvector = 0; 295 296 297 // Scan the array and see if one of our patterns matches. 298 Constant *CompareRHS = cast<Constant>(ICI.getOperand(1)); 299 for (unsigned i = 0, e = ArrayElementCount; i != e; ++i) { 300 Constant *Elt = Init->getAggregateElement(i); 301 if (!Elt) return nullptr; 302 303 // If this is indexing an array of structures, get the structure element. 304 if (!LaterIndices.empty()) 305 Elt = ConstantExpr::getExtractValue(Elt, LaterIndices); 306 307 // If the element is masked, handle it. 308 if (AndCst) Elt = ConstantExpr::getAnd(Elt, AndCst); 309 310 // Find out if the comparison would be true or false for the i'th element. 311 Constant *C = ConstantFoldCompareInstOperands(ICI.getPredicate(), Elt, 312 CompareRHS, DL, TLI); 313 // If the result is undef for this element, ignore it. 314 if (isa<UndefValue>(C)) { 315 // Extend range state machines to cover this element in case there is an 316 // undef in the middle of the range. 317 if (TrueRangeEnd == (int)i-1) 318 TrueRangeEnd = i; 319 if (FalseRangeEnd == (int)i-1) 320 FalseRangeEnd = i; 321 continue; 322 } 323 324 // If we can't compute the result for any of the elements, we have to give 325 // up evaluating the entire conditional. 326 if (!isa<ConstantInt>(C)) return nullptr; 327 328 // Otherwise, we know if the comparison is true or false for this element, 329 // update our state machines. 330 bool IsTrueForElt = !cast<ConstantInt>(C)->isZero(); 331 332 // State machine for single/double/range index comparison. 333 if (IsTrueForElt) { 334 // Update the TrueElement state machine. 335 if (FirstTrueElement == Undefined) 336 FirstTrueElement = TrueRangeEnd = i; // First true element. 337 else { 338 // Update double-compare state machine. 339 if (SecondTrueElement == Undefined) 340 SecondTrueElement = i; 341 else 342 SecondTrueElement = Overdefined; 343 344 // Update range state machine. 345 if (TrueRangeEnd == (int)i-1) 346 TrueRangeEnd = i; 347 else 348 TrueRangeEnd = Overdefined; 349 } 350 } else { 351 // Update the FalseElement state machine. 352 if (FirstFalseElement == Undefined) 353 FirstFalseElement = FalseRangeEnd = i; // First false element. 354 else { 355 // Update double-compare state machine. 356 if (SecondFalseElement == Undefined) 357 SecondFalseElement = i; 358 else 359 SecondFalseElement = Overdefined; 360 361 // Update range state machine. 362 if (FalseRangeEnd == (int)i-1) 363 FalseRangeEnd = i; 364 else 365 FalseRangeEnd = Overdefined; 366 } 367 } 368 369 370 // If this element is in range, update our magic bitvector. 371 if (i < 64 && IsTrueForElt) 372 MagicBitvector |= 1ULL << i; 373 374 // If all of our states become overdefined, bail out early. Since the 375 // predicate is expensive, only check it every 8 elements. This is only 376 // really useful for really huge arrays. 377 if ((i & 8) == 0 && i >= 64 && SecondTrueElement == Overdefined && 378 SecondFalseElement == Overdefined && TrueRangeEnd == Overdefined && 379 FalseRangeEnd == Overdefined) 380 return nullptr; 381 } 382 383 // Now that we've scanned the entire array, emit our new comparison(s). We 384 // order the state machines in complexity of the generated code. 385 Value *Idx = GEP->getOperand(2); 386 387 // If the index is larger than the pointer size of the target, truncate the 388 // index down like the GEP would do implicitly. We don't have to do this for 389 // an inbounds GEP because the index can't be out of range. 390 if (!GEP->isInBounds()) { 391 Type *IntPtrTy = DL->getIntPtrType(GEP->getType()); 392 unsigned PtrSize = IntPtrTy->getIntegerBitWidth(); 393 if (Idx->getType()->getPrimitiveSizeInBits() > PtrSize) 394 Idx = Builder->CreateTrunc(Idx, IntPtrTy); 395 } 396 397 // If the comparison is only true for one or two elements, emit direct 398 // comparisons. 399 if (SecondTrueElement != Overdefined) { 400 // None true -> false. 401 if (FirstTrueElement == Undefined) 402 return ReplaceInstUsesWith(ICI, Builder->getFalse()); 403 404 Value *FirstTrueIdx = ConstantInt::get(Idx->getType(), FirstTrueElement); 405 406 // True for one element -> 'i == 47'. 407 if (SecondTrueElement == Undefined) 408 return new ICmpInst(ICmpInst::ICMP_EQ, Idx, FirstTrueIdx); 409 410 // True for two elements -> 'i == 47 | i == 72'. 411 Value *C1 = Builder->CreateICmpEQ(Idx, FirstTrueIdx); 412 Value *SecondTrueIdx = ConstantInt::get(Idx->getType(), SecondTrueElement); 413 Value *C2 = Builder->CreateICmpEQ(Idx, SecondTrueIdx); 414 return BinaryOperator::CreateOr(C1, C2); 415 } 416 417 // If the comparison is only false for one or two elements, emit direct 418 // comparisons. 419 if (SecondFalseElement != Overdefined) { 420 // None false -> true. 421 if (FirstFalseElement == Undefined) 422 return ReplaceInstUsesWith(ICI, Builder->getTrue()); 423 424 Value *FirstFalseIdx = ConstantInt::get(Idx->getType(), FirstFalseElement); 425 426 // False for one element -> 'i != 47'. 427 if (SecondFalseElement == Undefined) 428 return new ICmpInst(ICmpInst::ICMP_NE, Idx, FirstFalseIdx); 429 430 // False for two elements -> 'i != 47 & i != 72'. 431 Value *C1 = Builder->CreateICmpNE(Idx, FirstFalseIdx); 432 Value *SecondFalseIdx = ConstantInt::get(Idx->getType(),SecondFalseElement); 433 Value *C2 = Builder->CreateICmpNE(Idx, SecondFalseIdx); 434 return BinaryOperator::CreateAnd(C1, C2); 435 } 436 437 // If the comparison can be replaced with a range comparison for the elements 438 // where it is true, emit the range check. 439 if (TrueRangeEnd != Overdefined) { 440 assert(TrueRangeEnd != FirstTrueElement && "Should emit single compare"); 441 442 // Generate (i-FirstTrue) <u (TrueRangeEnd-FirstTrue+1). 443 if (FirstTrueElement) { 444 Value *Offs = ConstantInt::get(Idx->getType(), -FirstTrueElement); 445 Idx = Builder->CreateAdd(Idx, Offs); 446 } 447 448 Value *End = ConstantInt::get(Idx->getType(), 449 TrueRangeEnd-FirstTrueElement+1); 450 return new ICmpInst(ICmpInst::ICMP_ULT, Idx, End); 451 } 452 453 // False range check. 454 if (FalseRangeEnd != Overdefined) { 455 assert(FalseRangeEnd != FirstFalseElement && "Should emit single compare"); 456 // Generate (i-FirstFalse) >u (FalseRangeEnd-FirstFalse). 457 if (FirstFalseElement) { 458 Value *Offs = ConstantInt::get(Idx->getType(), -FirstFalseElement); 459 Idx = Builder->CreateAdd(Idx, Offs); 460 } 461 462 Value *End = ConstantInt::get(Idx->getType(), 463 FalseRangeEnd-FirstFalseElement); 464 return new ICmpInst(ICmpInst::ICMP_UGT, Idx, End); 465 } 466 467 468 // If a magic bitvector captures the entire comparison state 469 // of this load, replace it with computation that does: 470 // ((magic_cst >> i) & 1) != 0 471 { 472 Type *Ty = nullptr; 473 474 // Look for an appropriate type: 475 // - The type of Idx if the magic fits 476 // - The smallest fitting legal type if we have a DataLayout 477 // - Default to i32 478 if (ArrayElementCount <= Idx->getType()->getIntegerBitWidth()) 479 Ty = Idx->getType(); 480 else if (DL) 481 Ty = DL->getSmallestLegalIntType(Init->getContext(), ArrayElementCount); 482 else if (ArrayElementCount <= 32) 483 Ty = Type::getInt32Ty(Init->getContext()); 484 485 if (Ty) { 486 Value *V = Builder->CreateIntCast(Idx, Ty, false); 487 V = Builder->CreateLShr(ConstantInt::get(Ty, MagicBitvector), V); 488 V = Builder->CreateAnd(ConstantInt::get(Ty, 1), V); 489 return new ICmpInst(ICmpInst::ICMP_NE, V, ConstantInt::get(Ty, 0)); 490 } 491 } 492 493 return nullptr; 494} 495 496 497/// EvaluateGEPOffsetExpression - Return a value that can be used to compare 498/// the *offset* implied by a GEP to zero. For example, if we have &A[i], we 499/// want to return 'i' for "icmp ne i, 0". Note that, in general, indices can 500/// be complex, and scales are involved. The above expression would also be 501/// legal to codegen as "icmp ne (i*4), 0" (assuming A is a pointer to i32). 502/// This later form is less amenable to optimization though, and we are allowed 503/// to generate the first by knowing that pointer arithmetic doesn't overflow. 504/// 505/// If we can't emit an optimized form for this expression, this returns null. 506/// 507static Value *EvaluateGEPOffsetExpression(User *GEP, InstCombiner &IC) { 508 const DataLayout &DL = *IC.getDataLayout(); 509 gep_type_iterator GTI = gep_type_begin(GEP); 510 511 // Check to see if this gep only has a single variable index. If so, and if 512 // any constant indices are a multiple of its scale, then we can compute this 513 // in terms of the scale of the variable index. For example, if the GEP 514 // implies an offset of "12 + i*4", then we can codegen this as "3 + i", 515 // because the expression will cross zero at the same point. 516 unsigned i, e = GEP->getNumOperands(); 517 int64_t Offset = 0; 518 for (i = 1; i != e; ++i, ++GTI) { 519 if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) { 520 // Compute the aggregate offset of constant indices. 521 if (CI->isZero()) continue; 522 523 // Handle a struct index, which adds its field offset to the pointer. 524 if (StructType *STy = dyn_cast<StructType>(*GTI)) { 525 Offset += DL.getStructLayout(STy)->getElementOffset(CI->getZExtValue()); 526 } else { 527 uint64_t Size = DL.getTypeAllocSize(GTI.getIndexedType()); 528 Offset += Size*CI->getSExtValue(); 529 } 530 } else { 531 // Found our variable index. 532 break; 533 } 534 } 535 536 // If there are no variable indices, we must have a constant offset, just 537 // evaluate it the general way. 538 if (i == e) return nullptr; 539 540 Value *VariableIdx = GEP->getOperand(i); 541 // Determine the scale factor of the variable element. For example, this is 542 // 4 if the variable index is into an array of i32. 543 uint64_t VariableScale = DL.getTypeAllocSize(GTI.getIndexedType()); 544 545 // Verify that there are no other variable indices. If so, emit the hard way. 546 for (++i, ++GTI; i != e; ++i, ++GTI) { 547 ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i)); 548 if (!CI) return nullptr; 549 550 // Compute the aggregate offset of constant indices. 551 if (CI->isZero()) continue; 552 553 // Handle a struct index, which adds its field offset to the pointer. 554 if (StructType *STy = dyn_cast<StructType>(*GTI)) { 555 Offset += DL.getStructLayout(STy)->getElementOffset(CI->getZExtValue()); 556 } else { 557 uint64_t Size = DL.getTypeAllocSize(GTI.getIndexedType()); 558 Offset += Size*CI->getSExtValue(); 559 } 560 } 561 562 563 564 // Okay, we know we have a single variable index, which must be a 565 // pointer/array/vector index. If there is no offset, life is simple, return 566 // the index. 567 Type *IntPtrTy = DL.getIntPtrType(GEP->getOperand(0)->getType()); 568 unsigned IntPtrWidth = IntPtrTy->getIntegerBitWidth(); 569 if (Offset == 0) { 570 // Cast to intptrty in case a truncation occurs. If an extension is needed, 571 // we don't need to bother extending: the extension won't affect where the 572 // computation crosses zero. 573 if (VariableIdx->getType()->getPrimitiveSizeInBits() > IntPtrWidth) { 574 VariableIdx = IC.Builder->CreateTrunc(VariableIdx, IntPtrTy); 575 } 576 return VariableIdx; 577 } 578 579 // Otherwise, there is an index. The computation we will do will be modulo 580 // the pointer size, so get it. 581 uint64_t PtrSizeMask = ~0ULL >> (64-IntPtrWidth); 582 583 Offset &= PtrSizeMask; 584 VariableScale &= PtrSizeMask; 585 586 // To do this transformation, any constant index must be a multiple of the 587 // variable scale factor. For example, we can evaluate "12 + 4*i" as "3 + i", 588 // but we can't evaluate "10 + 3*i" in terms of i. Check that the offset is a 589 // multiple of the variable scale. 590 int64_t NewOffs = Offset / (int64_t)VariableScale; 591 if (Offset != NewOffs*(int64_t)VariableScale) 592 return nullptr; 593 594 // Okay, we can do this evaluation. Start by converting the index to intptr. 595 if (VariableIdx->getType() != IntPtrTy) 596 VariableIdx = IC.Builder->CreateIntCast(VariableIdx, IntPtrTy, 597 true /*Signed*/); 598 Constant *OffsetVal = ConstantInt::get(IntPtrTy, NewOffs); 599 return IC.Builder->CreateAdd(VariableIdx, OffsetVal, "offset"); 600} 601 602/// FoldGEPICmp - Fold comparisons between a GEP instruction and something 603/// else. At this point we know that the GEP is on the LHS of the comparison. 604Instruction *InstCombiner::FoldGEPICmp(GEPOperator *GEPLHS, Value *RHS, 605 ICmpInst::Predicate Cond, 606 Instruction &I) { 607 // Don't transform signed compares of GEPs into index compares. Even if the 608 // GEP is inbounds, the final add of the base pointer can have signed overflow 609 // and would change the result of the icmp. 610 // e.g. "&foo[0] <s &foo[1]" can't be folded to "true" because "foo" could be 611 // the maximum signed value for the pointer type. 612 if (ICmpInst::isSigned(Cond)) 613 return nullptr; 614 615 // Look through bitcasts. 616 if (BitCastInst *BCI = dyn_cast<BitCastInst>(RHS)) 617 RHS = BCI->getOperand(0); 618 619 Value *PtrBase = GEPLHS->getOperand(0); 620 if (DL && PtrBase == RHS && GEPLHS->isInBounds()) { 621 // ((gep Ptr, OFFSET) cmp Ptr) ---> (OFFSET cmp 0). 622 // This transformation (ignoring the base and scales) is valid because we 623 // know pointers can't overflow since the gep is inbounds. See if we can 624 // output an optimized form. 625 Value *Offset = EvaluateGEPOffsetExpression(GEPLHS, *this); 626 627 // If not, synthesize the offset the hard way. 628 if (!Offset) 629 Offset = EmitGEPOffset(GEPLHS); 630 return new ICmpInst(ICmpInst::getSignedPredicate(Cond), Offset, 631 Constant::getNullValue(Offset->getType())); 632 } else if (GEPOperator *GEPRHS = dyn_cast<GEPOperator>(RHS)) { 633 // If the base pointers are different, but the indices are the same, just 634 // compare the base pointer. 635 if (PtrBase != GEPRHS->getOperand(0)) { 636 bool IndicesTheSame = GEPLHS->getNumOperands()==GEPRHS->getNumOperands(); 637 IndicesTheSame &= GEPLHS->getOperand(0)->getType() == 638 GEPRHS->getOperand(0)->getType(); 639 if (IndicesTheSame) 640 for (unsigned i = 1, e = GEPLHS->getNumOperands(); i != e; ++i) 641 if (GEPLHS->getOperand(i) != GEPRHS->getOperand(i)) { 642 IndicesTheSame = false; 643 break; 644 } 645 646 // If all indices are the same, just compare the base pointers. 647 if (IndicesTheSame) 648 return new ICmpInst(Cond, GEPLHS->getOperand(0), GEPRHS->getOperand(0)); 649 650 // If we're comparing GEPs with two base pointers that only differ in type 651 // and both GEPs have only constant indices or just one use, then fold 652 // the compare with the adjusted indices. 653 if (DL && GEPLHS->isInBounds() && GEPRHS->isInBounds() && 654 (GEPLHS->hasAllConstantIndices() || GEPLHS->hasOneUse()) && 655 (GEPRHS->hasAllConstantIndices() || GEPRHS->hasOneUse()) && 656 PtrBase->stripPointerCasts() == 657 GEPRHS->getOperand(0)->stripPointerCasts()) { 658 Value *Cmp = Builder->CreateICmp(ICmpInst::getSignedPredicate(Cond), 659 EmitGEPOffset(GEPLHS), 660 EmitGEPOffset(GEPRHS)); 661 return ReplaceInstUsesWith(I, Cmp); 662 } 663 664 // Otherwise, the base pointers are different and the indices are 665 // different, bail out. 666 return nullptr; 667 } 668 669 // If one of the GEPs has all zero indices, recurse. 670 bool AllZeros = true; 671 for (unsigned i = 1, e = GEPLHS->getNumOperands(); i != e; ++i) 672 if (!isa<Constant>(GEPLHS->getOperand(i)) || 673 !cast<Constant>(GEPLHS->getOperand(i))->isNullValue()) { 674 AllZeros = false; 675 break; 676 } 677 if (AllZeros) 678 return FoldGEPICmp(GEPRHS, GEPLHS->getOperand(0), 679 ICmpInst::getSwappedPredicate(Cond), I); 680 681 // If the other GEP has all zero indices, recurse. 682 AllZeros = true; 683 for (unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i) 684 if (!isa<Constant>(GEPRHS->getOperand(i)) || 685 !cast<Constant>(GEPRHS->getOperand(i))->isNullValue()) { 686 AllZeros = false; 687 break; 688 } 689 if (AllZeros) 690 return FoldGEPICmp(GEPLHS, GEPRHS->getOperand(0), Cond, I); 691 692 bool GEPsInBounds = GEPLHS->isInBounds() && GEPRHS->isInBounds(); 693 if (GEPLHS->getNumOperands() == GEPRHS->getNumOperands()) { 694 // If the GEPs only differ by one index, compare it. 695 unsigned NumDifferences = 0; // Keep track of # differences. 696 unsigned DiffOperand = 0; // The operand that differs. 697 for (unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i) 698 if (GEPLHS->getOperand(i) != GEPRHS->getOperand(i)) { 699 if (GEPLHS->getOperand(i)->getType()->getPrimitiveSizeInBits() != 700 GEPRHS->getOperand(i)->getType()->getPrimitiveSizeInBits()) { 701 // Irreconcilable differences. 702 NumDifferences = 2; 703 break; 704 } else { 705 if (NumDifferences++) break; 706 DiffOperand = i; 707 } 708 } 709 710 if (NumDifferences == 0) // SAME GEP? 711 return ReplaceInstUsesWith(I, // No comparison is needed here. 712 Builder->getInt1(ICmpInst::isTrueWhenEqual(Cond))); 713 714 else if (NumDifferences == 1 && GEPsInBounds) { 715 Value *LHSV = GEPLHS->getOperand(DiffOperand); 716 Value *RHSV = GEPRHS->getOperand(DiffOperand); 717 // Make sure we do a signed comparison here. 718 return new ICmpInst(ICmpInst::getSignedPredicate(Cond), LHSV, RHSV); 719 } 720 } 721 722 // Only lower this if the icmp is the only user of the GEP or if we expect 723 // the result to fold to a constant! 724 if (DL && 725 GEPsInBounds && 726 (isa<ConstantExpr>(GEPLHS) || GEPLHS->hasOneUse()) && 727 (isa<ConstantExpr>(GEPRHS) || GEPRHS->hasOneUse())) { 728 // ((gep Ptr, OFFSET1) cmp (gep Ptr, OFFSET2) ---> (OFFSET1 cmp OFFSET2) 729 Value *L = EmitGEPOffset(GEPLHS); 730 Value *R = EmitGEPOffset(GEPRHS); 731 return new ICmpInst(ICmpInst::getSignedPredicate(Cond), L, R); 732 } 733 } 734 return nullptr; 735} 736 737/// FoldICmpAddOpCst - Fold "icmp pred (X+CI), X". 738Instruction *InstCombiner::FoldICmpAddOpCst(Instruction &ICI, 739 Value *X, ConstantInt *CI, 740 ICmpInst::Predicate Pred) { 741 // If we have X+0, exit early (simplifying logic below) and let it get folded 742 // elsewhere. icmp X+0, X -> icmp X, X 743 if (CI->isZero()) { 744 bool isTrue = ICmpInst::isTrueWhenEqual(Pred); 745 return ReplaceInstUsesWith(ICI, ConstantInt::get(ICI.getType(), isTrue)); 746 } 747 748 // (X+4) == X -> false. 749 if (Pred == ICmpInst::ICMP_EQ) 750 return ReplaceInstUsesWith(ICI, Builder->getFalse()); 751 752 // (X+4) != X -> true. 753 if (Pred == ICmpInst::ICMP_NE) 754 return ReplaceInstUsesWith(ICI, Builder->getTrue()); 755 756 // From this point on, we know that (X+C <= X) --> (X+C < X) because C != 0, 757 // so the values can never be equal. Similarly for all other "or equals" 758 // operators. 759 760 // (X+1) <u X --> X >u (MAXUINT-1) --> X == 255 761 // (X+2) <u X --> X >u (MAXUINT-2) --> X > 253 762 // (X+MAXUINT) <u X --> X >u (MAXUINT-MAXUINT) --> X != 0 763 if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE) { 764 Value *R = 765 ConstantExpr::getSub(ConstantInt::getAllOnesValue(CI->getType()), CI); 766 return new ICmpInst(ICmpInst::ICMP_UGT, X, R); 767 } 768 769 // (X+1) >u X --> X <u (0-1) --> X != 255 770 // (X+2) >u X --> X <u (0-2) --> X <u 254 771 // (X+MAXUINT) >u X --> X <u (0-MAXUINT) --> X <u 1 --> X == 0 772 if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE) 773 return new ICmpInst(ICmpInst::ICMP_ULT, X, ConstantExpr::getNeg(CI)); 774 775 unsigned BitWidth = CI->getType()->getPrimitiveSizeInBits(); 776 ConstantInt *SMax = ConstantInt::get(X->getContext(), 777 APInt::getSignedMaxValue(BitWidth)); 778 779 // (X+ 1) <s X --> X >s (MAXSINT-1) --> X == 127 780 // (X+ 2) <s X --> X >s (MAXSINT-2) --> X >s 125 781 // (X+MAXSINT) <s X --> X >s (MAXSINT-MAXSINT) --> X >s 0 782 // (X+MINSINT) <s X --> X >s (MAXSINT-MINSINT) --> X >s -1 783 // (X+ -2) <s X --> X >s (MAXSINT- -2) --> X >s 126 784 // (X+ -1) <s X --> X >s (MAXSINT- -1) --> X != 127 785 if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE) 786 return new ICmpInst(ICmpInst::ICMP_SGT, X, ConstantExpr::getSub(SMax, CI)); 787 788 // (X+ 1) >s X --> X <s (MAXSINT-(1-1)) --> X != 127 789 // (X+ 2) >s X --> X <s (MAXSINT-(2-1)) --> X <s 126 790 // (X+MAXSINT) >s X --> X <s (MAXSINT-(MAXSINT-1)) --> X <s 1 791 // (X+MINSINT) >s X --> X <s (MAXSINT-(MINSINT-1)) --> X <s -2 792 // (X+ -2) >s X --> X <s (MAXSINT-(-2-1)) --> X <s -126 793 // (X+ -1) >s X --> X <s (MAXSINT-(-1-1)) --> X == -128 794 795 assert(Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE); 796 Constant *C = Builder->getInt(CI->getValue()-1); 797 return new ICmpInst(ICmpInst::ICMP_SLT, X, ConstantExpr::getSub(SMax, C)); 798} 799 800/// FoldICmpDivCst - Fold "icmp pred, ([su]div X, DivRHS), CmpRHS" where DivRHS 801/// and CmpRHS are both known to be integer constants. 802Instruction *InstCombiner::FoldICmpDivCst(ICmpInst &ICI, BinaryOperator *DivI, 803 ConstantInt *DivRHS) { 804 ConstantInt *CmpRHS = cast<ConstantInt>(ICI.getOperand(1)); 805 const APInt &CmpRHSV = CmpRHS->getValue(); 806 807 // FIXME: If the operand types don't match the type of the divide 808 // then don't attempt this transform. The code below doesn't have the 809 // logic to deal with a signed divide and an unsigned compare (and 810 // vice versa). This is because (x /s C1) <s C2 produces different 811 // results than (x /s C1) <u C2 or (x /u C1) <s C2 or even 812 // (x /u C1) <u C2. Simply casting the operands and result won't 813 // work. :( The if statement below tests that condition and bails 814 // if it finds it. 815 bool DivIsSigned = DivI->getOpcode() == Instruction::SDiv; 816 if (!ICI.isEquality() && DivIsSigned != ICI.isSigned()) 817 return nullptr; 818 if (DivRHS->isZero()) 819 return nullptr; // The ProdOV computation fails on divide by zero. 820 if (DivIsSigned && DivRHS->isAllOnesValue()) 821 return nullptr; // The overflow computation also screws up here 822 if (DivRHS->isOne()) { 823 // This eliminates some funny cases with INT_MIN. 824 ICI.setOperand(0, DivI->getOperand(0)); // X/1 == X. 825 return &ICI; 826 } 827 828 // Compute Prod = CI * DivRHS. We are essentially solving an equation 829 // of form X/C1=C2. We solve for X by multiplying C1 (DivRHS) and 830 // C2 (CI). By solving for X we can turn this into a range check 831 // instead of computing a divide. 832 Constant *Prod = ConstantExpr::getMul(CmpRHS, DivRHS); 833 834 // Determine if the product overflows by seeing if the product is 835 // not equal to the divide. Make sure we do the same kind of divide 836 // as in the LHS instruction that we're folding. 837 bool ProdOV = (DivIsSigned ? ConstantExpr::getSDiv(Prod, DivRHS) : 838 ConstantExpr::getUDiv(Prod, DivRHS)) != CmpRHS; 839 840 // Get the ICmp opcode 841 ICmpInst::Predicate Pred = ICI.getPredicate(); 842 843 /// If the division is known to be exact, then there is no remainder from the 844 /// divide, so the covered range size is unit, otherwise it is the divisor. 845 ConstantInt *RangeSize = DivI->isExact() ? getOne(Prod) : DivRHS; 846 847 // Figure out the interval that is being checked. For example, a comparison 848 // like "X /u 5 == 0" is really checking that X is in the interval [0, 5). 849 // Compute this interval based on the constants involved and the signedness of 850 // the compare/divide. This computes a half-open interval, keeping track of 851 // whether either value in the interval overflows. After analysis each 852 // overflow variable is set to 0 if it's corresponding bound variable is valid 853 // -1 if overflowed off the bottom end, or +1 if overflowed off the top end. 854 int LoOverflow = 0, HiOverflow = 0; 855 Constant *LoBound = nullptr, *HiBound = nullptr; 856 857 if (!DivIsSigned) { // udiv 858 // e.g. X/5 op 3 --> [15, 20) 859 LoBound = Prod; 860 HiOverflow = LoOverflow = ProdOV; 861 if (!HiOverflow) { 862 // If this is not an exact divide, then many values in the range collapse 863 // to the same result value. 864 HiOverflow = AddWithOverflow(HiBound, LoBound, RangeSize, false); 865 } 866 867 } else if (DivRHS->getValue().isStrictlyPositive()) { // Divisor is > 0. 868 if (CmpRHSV == 0) { // (X / pos) op 0 869 // Can't overflow. e.g. X/2 op 0 --> [-1, 2) 870 LoBound = ConstantExpr::getNeg(SubOne(RangeSize)); 871 HiBound = RangeSize; 872 } else if (CmpRHSV.isStrictlyPositive()) { // (X / pos) op pos 873 LoBound = Prod; // e.g. X/5 op 3 --> [15, 20) 874 HiOverflow = LoOverflow = ProdOV; 875 if (!HiOverflow) 876 HiOverflow = AddWithOverflow(HiBound, Prod, RangeSize, true); 877 } else { // (X / pos) op neg 878 // e.g. X/5 op -3 --> [-15-4, -15+1) --> [-19, -14) 879 HiBound = AddOne(Prod); 880 LoOverflow = HiOverflow = ProdOV ? -1 : 0; 881 if (!LoOverflow) { 882 ConstantInt *DivNeg =cast<ConstantInt>(ConstantExpr::getNeg(RangeSize)); 883 LoOverflow = AddWithOverflow(LoBound, HiBound, DivNeg, true) ? -1 : 0; 884 } 885 } 886 } else if (DivRHS->isNegative()) { // Divisor is < 0. 887 if (DivI->isExact()) 888 RangeSize = cast<ConstantInt>(ConstantExpr::getNeg(RangeSize)); 889 if (CmpRHSV == 0) { // (X / neg) op 0 890 // e.g. X/-5 op 0 --> [-4, 5) 891 LoBound = AddOne(RangeSize); 892 HiBound = cast<ConstantInt>(ConstantExpr::getNeg(RangeSize)); 893 if (HiBound == DivRHS) { // -INTMIN = INTMIN 894 HiOverflow = 1; // [INTMIN+1, overflow) 895 HiBound = nullptr; // e.g. X/INTMIN = 0 --> X > INTMIN 896 } 897 } else if (CmpRHSV.isStrictlyPositive()) { // (X / neg) op pos 898 // e.g. X/-5 op 3 --> [-19, -14) 899 HiBound = AddOne(Prod); 900 HiOverflow = LoOverflow = ProdOV ? -1 : 0; 901 if (!LoOverflow) 902 LoOverflow = AddWithOverflow(LoBound, HiBound, RangeSize, true) ? -1:0; 903 } else { // (X / neg) op neg 904 LoBound = Prod; // e.g. X/-5 op -3 --> [15, 20) 905 LoOverflow = HiOverflow = ProdOV; 906 if (!HiOverflow) 907 HiOverflow = SubWithOverflow(HiBound, Prod, RangeSize, true); 908 } 909 910 // Dividing by a negative swaps the condition. LT <-> GT 911 Pred = ICmpInst::getSwappedPredicate(Pred); 912 } 913 914 Value *X = DivI->getOperand(0); 915 switch (Pred) { 916 default: llvm_unreachable("Unhandled icmp opcode!"); 917 case ICmpInst::ICMP_EQ: 918 if (LoOverflow && HiOverflow) 919 return ReplaceInstUsesWith(ICI, Builder->getFalse()); 920 if (HiOverflow) 921 return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE : 922 ICmpInst::ICMP_UGE, X, LoBound); 923 if (LoOverflow) 924 return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT : 925 ICmpInst::ICMP_ULT, X, HiBound); 926 return ReplaceInstUsesWith(ICI, InsertRangeTest(X, LoBound, HiBound, 927 DivIsSigned, true)); 928 case ICmpInst::ICMP_NE: 929 if (LoOverflow && HiOverflow) 930 return ReplaceInstUsesWith(ICI, Builder->getTrue()); 931 if (HiOverflow) 932 return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT : 933 ICmpInst::ICMP_ULT, X, LoBound); 934 if (LoOverflow) 935 return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE : 936 ICmpInst::ICMP_UGE, X, HiBound); 937 return ReplaceInstUsesWith(ICI, InsertRangeTest(X, LoBound, HiBound, 938 DivIsSigned, false)); 939 case ICmpInst::ICMP_ULT: 940 case ICmpInst::ICMP_SLT: 941 if (LoOverflow == +1) // Low bound is greater than input range. 942 return ReplaceInstUsesWith(ICI, Builder->getTrue()); 943 if (LoOverflow == -1) // Low bound is less than input range. 944 return ReplaceInstUsesWith(ICI, Builder->getFalse()); 945 return new ICmpInst(Pred, X, LoBound); 946 case ICmpInst::ICMP_UGT: 947 case ICmpInst::ICMP_SGT: 948 if (HiOverflow == +1) // High bound greater than input range. 949 return ReplaceInstUsesWith(ICI, Builder->getFalse()); 950 if (HiOverflow == -1) // High bound less than input range. 951 return ReplaceInstUsesWith(ICI, Builder->getTrue()); 952 if (Pred == ICmpInst::ICMP_UGT) 953 return new ICmpInst(ICmpInst::ICMP_UGE, X, HiBound); 954 return new ICmpInst(ICmpInst::ICMP_SGE, X, HiBound); 955 } 956} 957 958/// FoldICmpShrCst - Handle "icmp(([al]shr X, cst1), cst2)". 959Instruction *InstCombiner::FoldICmpShrCst(ICmpInst &ICI, BinaryOperator *Shr, 960 ConstantInt *ShAmt) { 961 const APInt &CmpRHSV = cast<ConstantInt>(ICI.getOperand(1))->getValue(); 962 963 // Check that the shift amount is in range. If not, don't perform 964 // undefined shifts. When the shift is visited it will be 965 // simplified. 966 uint32_t TypeBits = CmpRHSV.getBitWidth(); 967 uint32_t ShAmtVal = (uint32_t)ShAmt->getLimitedValue(TypeBits); 968 if (ShAmtVal >= TypeBits || ShAmtVal == 0) 969 return nullptr; 970 971 if (!ICI.isEquality()) { 972 // If we have an unsigned comparison and an ashr, we can't simplify this. 973 // Similarly for signed comparisons with lshr. 974 if (ICI.isSigned() != (Shr->getOpcode() == Instruction::AShr)) 975 return nullptr; 976 977 // Otherwise, all lshr and most exact ashr's are equivalent to a udiv/sdiv 978 // by a power of 2. Since we already have logic to simplify these, 979 // transform to div and then simplify the resultant comparison. 980 if (Shr->getOpcode() == Instruction::AShr && 981 (!Shr->isExact() || ShAmtVal == TypeBits - 1)) 982 return nullptr; 983 984 // Revisit the shift (to delete it). 985 Worklist.Add(Shr); 986 987 Constant *DivCst = 988 ConstantInt::get(Shr->getType(), APInt::getOneBitSet(TypeBits, ShAmtVal)); 989 990 Value *Tmp = 991 Shr->getOpcode() == Instruction::AShr ? 992 Builder->CreateSDiv(Shr->getOperand(0), DivCst, "", Shr->isExact()) : 993 Builder->CreateUDiv(Shr->getOperand(0), DivCst, "", Shr->isExact()); 994 995 ICI.setOperand(0, Tmp); 996 997 // If the builder folded the binop, just return it. 998 BinaryOperator *TheDiv = dyn_cast<BinaryOperator>(Tmp); 999 if (!TheDiv) 1000 return &ICI; 1001 1002 // Otherwise, fold this div/compare. 1003 assert(TheDiv->getOpcode() == Instruction::SDiv || 1004 TheDiv->getOpcode() == Instruction::UDiv); 1005 1006 Instruction *Res = FoldICmpDivCst(ICI, TheDiv, cast<ConstantInt>(DivCst)); 1007 assert(Res && "This div/cst should have folded!"); 1008 return Res; 1009 } 1010 1011 1012 // If we are comparing against bits always shifted out, the 1013 // comparison cannot succeed. 1014 APInt Comp = CmpRHSV << ShAmtVal; 1015 ConstantInt *ShiftedCmpRHS = Builder->getInt(Comp); 1016 if (Shr->getOpcode() == Instruction::LShr) 1017 Comp = Comp.lshr(ShAmtVal); 1018 else 1019 Comp = Comp.ashr(ShAmtVal); 1020 1021 if (Comp != CmpRHSV) { // Comparing against a bit that we know is zero. 1022 bool IsICMP_NE = ICI.getPredicate() == ICmpInst::ICMP_NE; 1023 Constant *Cst = Builder->getInt1(IsICMP_NE); 1024 return ReplaceInstUsesWith(ICI, Cst); 1025 } 1026 1027 // Otherwise, check to see if the bits shifted out are known to be zero. 1028 // If so, we can compare against the unshifted value: 1029 // (X & 4) >> 1 == 2 --> (X & 4) == 4. 1030 if (Shr->hasOneUse() && Shr->isExact()) 1031 return new ICmpInst(ICI.getPredicate(), Shr->getOperand(0), ShiftedCmpRHS); 1032 1033 if (Shr->hasOneUse()) { 1034 // Otherwise strength reduce the shift into an and. 1035 APInt Val(APInt::getHighBitsSet(TypeBits, TypeBits - ShAmtVal)); 1036 Constant *Mask = Builder->getInt(Val); 1037 1038 Value *And = Builder->CreateAnd(Shr->getOperand(0), 1039 Mask, Shr->getName()+".mask"); 1040 return new ICmpInst(ICI.getPredicate(), And, ShiftedCmpRHS); 1041 } 1042 return nullptr; 1043} 1044 1045 1046/// visitICmpInstWithInstAndIntCst - Handle "icmp (instr, intcst)". 1047/// 1048Instruction *InstCombiner::visitICmpInstWithInstAndIntCst(ICmpInst &ICI, 1049 Instruction *LHSI, 1050 ConstantInt *RHS) { 1051 const APInt &RHSV = RHS->getValue(); 1052 1053 switch (LHSI->getOpcode()) { 1054 case Instruction::Trunc: 1055 if (ICI.isEquality() && LHSI->hasOneUse()) { 1056 // Simplify icmp eq (trunc x to i8), 42 -> icmp eq x, 42|highbits if all 1057 // of the high bits truncated out of x are known. 1058 unsigned DstBits = LHSI->getType()->getPrimitiveSizeInBits(), 1059 SrcBits = LHSI->getOperand(0)->getType()->getPrimitiveSizeInBits(); 1060 APInt KnownZero(SrcBits, 0), KnownOne(SrcBits, 0); 1061 computeKnownBits(LHSI->getOperand(0), KnownZero, KnownOne); 1062 1063 // If all the high bits are known, we can do this xform. 1064 if ((KnownZero|KnownOne).countLeadingOnes() >= SrcBits-DstBits) { 1065 // Pull in the high bits from known-ones set. 1066 APInt NewRHS = RHS->getValue().zext(SrcBits); 1067 NewRHS |= KnownOne & APInt::getHighBitsSet(SrcBits, SrcBits-DstBits); 1068 return new ICmpInst(ICI.getPredicate(), LHSI->getOperand(0), 1069 Builder->getInt(NewRHS)); 1070 } 1071 } 1072 break; 1073 1074 case Instruction::Xor: // (icmp pred (xor X, XorCst), CI) 1075 if (ConstantInt *XorCst = dyn_cast<ConstantInt>(LHSI->getOperand(1))) { 1076 // If this is a comparison that tests the signbit (X < 0) or (x > -1), 1077 // fold the xor. 1078 if ((ICI.getPredicate() == ICmpInst::ICMP_SLT && RHSV == 0) || 1079 (ICI.getPredicate() == ICmpInst::ICMP_SGT && RHSV.isAllOnesValue())) { 1080 Value *CompareVal = LHSI->getOperand(0); 1081 1082 // If the sign bit of the XorCst is not set, there is no change to 1083 // the operation, just stop using the Xor. 1084 if (!XorCst->isNegative()) { 1085 ICI.setOperand(0, CompareVal); 1086 Worklist.Add(LHSI); 1087 return &ICI; 1088 } 1089 1090 // Was the old condition true if the operand is positive? 1091 bool isTrueIfPositive = ICI.getPredicate() == ICmpInst::ICMP_SGT; 1092 1093 // If so, the new one isn't. 1094 isTrueIfPositive ^= true; 1095 1096 if (isTrueIfPositive) 1097 return new ICmpInst(ICmpInst::ICMP_SGT, CompareVal, 1098 SubOne(RHS)); 1099 else 1100 return new ICmpInst(ICmpInst::ICMP_SLT, CompareVal, 1101 AddOne(RHS)); 1102 } 1103 1104 if (LHSI->hasOneUse()) { 1105 // (icmp u/s (xor A SignBit), C) -> (icmp s/u A, (xor C SignBit)) 1106 if (!ICI.isEquality() && XorCst->getValue().isSignBit()) { 1107 const APInt &SignBit = XorCst->getValue(); 1108 ICmpInst::Predicate Pred = ICI.isSigned() 1109 ? ICI.getUnsignedPredicate() 1110 : ICI.getSignedPredicate(); 1111 return new ICmpInst(Pred, LHSI->getOperand(0), 1112 Builder->getInt(RHSV ^ SignBit)); 1113 } 1114 1115 // (icmp u/s (xor A ~SignBit), C) -> (icmp s/u (xor C ~SignBit), A) 1116 if (!ICI.isEquality() && XorCst->isMaxValue(true)) { 1117 const APInt &NotSignBit = XorCst->getValue(); 1118 ICmpInst::Predicate Pred = ICI.isSigned() 1119 ? ICI.getUnsignedPredicate() 1120 : ICI.getSignedPredicate(); 1121 Pred = ICI.getSwappedPredicate(Pred); 1122 return new ICmpInst(Pred, LHSI->getOperand(0), 1123 Builder->getInt(RHSV ^ NotSignBit)); 1124 } 1125 } 1126 1127 // (icmp ugt (xor X, C), ~C) -> (icmp ult X, C) 1128 // iff -C is a power of 2 1129 if (ICI.getPredicate() == ICmpInst::ICMP_UGT && 1130 XorCst->getValue() == ~RHSV && (RHSV + 1).isPowerOf2()) 1131 return new ICmpInst(ICmpInst::ICMP_ULT, LHSI->getOperand(0), XorCst); 1132 1133 // (icmp ult (xor X, C), -C) -> (icmp uge X, C) 1134 // iff -C is a power of 2 1135 if (ICI.getPredicate() == ICmpInst::ICMP_ULT && 1136 XorCst->getValue() == -RHSV && RHSV.isPowerOf2()) 1137 return new ICmpInst(ICmpInst::ICMP_UGE, LHSI->getOperand(0), XorCst); 1138 } 1139 break; 1140 case Instruction::And: // (icmp pred (and X, AndCst), RHS) 1141 if (LHSI->hasOneUse() && isa<ConstantInt>(LHSI->getOperand(1)) && 1142 LHSI->getOperand(0)->hasOneUse()) { 1143 ConstantInt *AndCst = cast<ConstantInt>(LHSI->getOperand(1)); 1144 1145 // If the LHS is an AND of a truncating cast, we can widen the 1146 // and/compare to be the input width without changing the value 1147 // produced, eliminating a cast. 1148 if (TruncInst *Cast = dyn_cast<TruncInst>(LHSI->getOperand(0))) { 1149 // We can do this transformation if either the AND constant does not 1150 // have its sign bit set or if it is an equality comparison. 1151 // Extending a relational comparison when we're checking the sign 1152 // bit would not work. 1153 if (ICI.isEquality() || 1154 (!AndCst->isNegative() && RHSV.isNonNegative())) { 1155 Value *NewAnd = 1156 Builder->CreateAnd(Cast->getOperand(0), 1157 ConstantExpr::getZExt(AndCst, Cast->getSrcTy())); 1158 NewAnd->takeName(LHSI); 1159 return new ICmpInst(ICI.getPredicate(), NewAnd, 1160 ConstantExpr::getZExt(RHS, Cast->getSrcTy())); 1161 } 1162 } 1163 1164 // If the LHS is an AND of a zext, and we have an equality compare, we can 1165 // shrink the and/compare to the smaller type, eliminating the cast. 1166 if (ZExtInst *Cast = dyn_cast<ZExtInst>(LHSI->getOperand(0))) { 1167 IntegerType *Ty = cast<IntegerType>(Cast->getSrcTy()); 1168 // Make sure we don't compare the upper bits, SimplifyDemandedBits 1169 // should fold the icmp to true/false in that case. 1170 if (ICI.isEquality() && RHSV.getActiveBits() <= Ty->getBitWidth()) { 1171 Value *NewAnd = 1172 Builder->CreateAnd(Cast->getOperand(0), 1173 ConstantExpr::getTrunc(AndCst, Ty)); 1174 NewAnd->takeName(LHSI); 1175 return new ICmpInst(ICI.getPredicate(), NewAnd, 1176 ConstantExpr::getTrunc(RHS, Ty)); 1177 } 1178 } 1179 1180 // If this is: (X >> C1) & C2 != C3 (where any shift and any compare 1181 // could exist), turn it into (X & (C2 << C1)) != (C3 << C1). This 1182 // happens a LOT in code produced by the C front-end, for bitfield 1183 // access. 1184 BinaryOperator *Shift = dyn_cast<BinaryOperator>(LHSI->getOperand(0)); 1185 if (Shift && !Shift->isShift()) 1186 Shift = nullptr; 1187 1188 ConstantInt *ShAmt; 1189 ShAmt = Shift ? dyn_cast<ConstantInt>(Shift->getOperand(1)) : nullptr; 1190 1191 // This seemingly simple opportunity to fold away a shift turns out to 1192 // be rather complicated. See PR17827 1193 // ( http://llvm.org/bugs/show_bug.cgi?id=17827 ) for details. 1194 if (ShAmt) { 1195 bool CanFold = false; 1196 unsigned ShiftOpcode = Shift->getOpcode(); 1197 if (ShiftOpcode == Instruction::AShr) { 1198 // There may be some constraints that make this possible, 1199 // but nothing simple has been discovered yet. 1200 CanFold = false; 1201 } else if (ShiftOpcode == Instruction::Shl) { 1202 // For a left shift, we can fold if the comparison is not signed. 1203 // We can also fold a signed comparison if the mask value and 1204 // comparison value are not negative. These constraints may not be 1205 // obvious, but we can prove that they are correct using an SMT 1206 // solver. 1207 if (!ICI.isSigned() || (!AndCst->isNegative() && !RHS->isNegative())) 1208 CanFold = true; 1209 } else if (ShiftOpcode == Instruction::LShr) { 1210 // For a logical right shift, we can fold if the comparison is not 1211 // signed. We can also fold a signed comparison if the shifted mask 1212 // value and the shifted comparison value are not negative. 1213 // These constraints may not be obvious, but we can prove that they 1214 // are correct using an SMT solver. 1215 if (!ICI.isSigned()) 1216 CanFold = true; 1217 else { 1218 ConstantInt *ShiftedAndCst = 1219 cast<ConstantInt>(ConstantExpr::getShl(AndCst, ShAmt)); 1220 ConstantInt *ShiftedRHSCst = 1221 cast<ConstantInt>(ConstantExpr::getShl(RHS, ShAmt)); 1222 1223 if (!ShiftedAndCst->isNegative() && !ShiftedRHSCst->isNegative()) 1224 CanFold = true; 1225 } 1226 } 1227 1228 if (CanFold) { 1229 Constant *NewCst; 1230 if (ShiftOpcode == Instruction::Shl) 1231 NewCst = ConstantExpr::getLShr(RHS, ShAmt); 1232 else 1233 NewCst = ConstantExpr::getShl(RHS, ShAmt); 1234 1235 // Check to see if we are shifting out any of the bits being 1236 // compared. 1237 if (ConstantExpr::get(ShiftOpcode, NewCst, ShAmt) != RHS) { 1238 // If we shifted bits out, the fold is not going to work out. 1239 // As a special case, check to see if this means that the 1240 // result is always true or false now. 1241 if (ICI.getPredicate() == ICmpInst::ICMP_EQ) 1242 return ReplaceInstUsesWith(ICI, Builder->getFalse()); 1243 if (ICI.getPredicate() == ICmpInst::ICMP_NE) 1244 return ReplaceInstUsesWith(ICI, Builder->getTrue()); 1245 } else { 1246 ICI.setOperand(1, NewCst); 1247 Constant *NewAndCst; 1248 if (ShiftOpcode == Instruction::Shl) 1249 NewAndCst = ConstantExpr::getLShr(AndCst, ShAmt); 1250 else 1251 NewAndCst = ConstantExpr::getShl(AndCst, ShAmt); 1252 LHSI->setOperand(1, NewAndCst); 1253 LHSI->setOperand(0, Shift->getOperand(0)); 1254 Worklist.Add(Shift); // Shift is dead. 1255 return &ICI; 1256 } 1257 } 1258 } 1259 1260 // Turn ((X >> Y) & C) == 0 into (X & (C << Y)) == 0. The later is 1261 // preferable because it allows the C<<Y expression to be hoisted out 1262 // of a loop if Y is invariant and X is not. 1263 if (Shift && Shift->hasOneUse() && RHSV == 0 && 1264 ICI.isEquality() && !Shift->isArithmeticShift() && 1265 !isa<Constant>(Shift->getOperand(0))) { 1266 // Compute C << Y. 1267 Value *NS; 1268 if (Shift->getOpcode() == Instruction::LShr) { 1269 NS = Builder->CreateShl(AndCst, Shift->getOperand(1)); 1270 } else { 1271 // Insert a logical shift. 1272 NS = Builder->CreateLShr(AndCst, Shift->getOperand(1)); 1273 } 1274 1275 // Compute X & (C << Y). 1276 Value *NewAnd = 1277 Builder->CreateAnd(Shift->getOperand(0), NS, LHSI->getName()); 1278 1279 ICI.setOperand(0, NewAnd); 1280 return &ICI; 1281 } 1282 1283 // Replace ((X & AndCst) > RHSV) with ((X & AndCst) != 0), if any 1284 // bit set in (X & AndCst) will produce a result greater than RHSV. 1285 if (ICI.getPredicate() == ICmpInst::ICMP_UGT) { 1286 unsigned NTZ = AndCst->getValue().countTrailingZeros(); 1287 if ((NTZ < AndCst->getBitWidth()) && 1288 APInt::getOneBitSet(AndCst->getBitWidth(), NTZ).ugt(RHSV)) 1289 return new ICmpInst(ICmpInst::ICMP_NE, LHSI, 1290 Constant::getNullValue(RHS->getType())); 1291 } 1292 } 1293 1294 // Try to optimize things like "A[i]&42 == 0" to index computations. 1295 if (LoadInst *LI = dyn_cast<LoadInst>(LHSI->getOperand(0))) { 1296 if (GetElementPtrInst *GEP = 1297 dyn_cast<GetElementPtrInst>(LI->getOperand(0))) 1298 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0))) 1299 if (GV->isConstant() && GV->hasDefinitiveInitializer() && 1300 !LI->isVolatile() && isa<ConstantInt>(LHSI->getOperand(1))) { 1301 ConstantInt *C = cast<ConstantInt>(LHSI->getOperand(1)); 1302 if (Instruction *Res = FoldCmpLoadFromIndexedGlobal(GEP, GV,ICI, C)) 1303 return Res; 1304 } 1305 } 1306 1307 // X & -C == -C -> X > u ~C 1308 // X & -C != -C -> X <= u ~C 1309 // iff C is a power of 2 1310 if (ICI.isEquality() && RHS == LHSI->getOperand(1) && (-RHSV).isPowerOf2()) 1311 return new ICmpInst( 1312 ICI.getPredicate() == ICmpInst::ICMP_EQ ? ICmpInst::ICMP_UGT 1313 : ICmpInst::ICMP_ULE, 1314 LHSI->getOperand(0), SubOne(RHS)); 1315 break; 1316 1317 case Instruction::Or: { 1318 if (!ICI.isEquality() || !RHS->isNullValue() || !LHSI->hasOneUse()) 1319 break; 1320 Value *P, *Q; 1321 if (match(LHSI, m_Or(m_PtrToInt(m_Value(P)), m_PtrToInt(m_Value(Q))))) { 1322 // Simplify icmp eq (or (ptrtoint P), (ptrtoint Q)), 0 1323 // -> and (icmp eq P, null), (icmp eq Q, null). 1324 Value *ICIP = Builder->CreateICmp(ICI.getPredicate(), P, 1325 Constant::getNullValue(P->getType())); 1326 Value *ICIQ = Builder->CreateICmp(ICI.getPredicate(), Q, 1327 Constant::getNullValue(Q->getType())); 1328 Instruction *Op; 1329 if (ICI.getPredicate() == ICmpInst::ICMP_EQ) 1330 Op = BinaryOperator::CreateAnd(ICIP, ICIQ); 1331 else 1332 Op = BinaryOperator::CreateOr(ICIP, ICIQ); 1333 return Op; 1334 } 1335 break; 1336 } 1337 1338 case Instruction::Mul: { // (icmp pred (mul X, Val), CI) 1339 ConstantInt *Val = dyn_cast<ConstantInt>(LHSI->getOperand(1)); 1340 if (!Val) break; 1341 1342 // If this is a signed comparison to 0 and the mul is sign preserving, 1343 // use the mul LHS operand instead. 1344 ICmpInst::Predicate pred = ICI.getPredicate(); 1345 if (isSignTest(pred, RHS) && !Val->isZero() && 1346 cast<BinaryOperator>(LHSI)->hasNoSignedWrap()) 1347 return new ICmpInst(Val->isNegative() ? 1348 ICmpInst::getSwappedPredicate(pred) : pred, 1349 LHSI->getOperand(0), 1350 Constant::getNullValue(RHS->getType())); 1351 1352 break; 1353 } 1354 1355 case Instruction::Shl: { // (icmp pred (shl X, ShAmt), CI) 1356 uint32_t TypeBits = RHSV.getBitWidth(); 1357 ConstantInt *ShAmt = dyn_cast<ConstantInt>(LHSI->getOperand(1)); 1358 if (!ShAmt) { 1359 Value *X; 1360 // (1 << X) pred P2 -> X pred Log2(P2) 1361 if (match(LHSI, m_Shl(m_One(), m_Value(X)))) { 1362 bool RHSVIsPowerOf2 = RHSV.isPowerOf2(); 1363 ICmpInst::Predicate Pred = ICI.getPredicate(); 1364 if (ICI.isUnsigned()) { 1365 if (!RHSVIsPowerOf2) { 1366 // (1 << X) < 30 -> X <= 4 1367 // (1 << X) <= 30 -> X <= 4 1368 // (1 << X) >= 30 -> X > 4 1369 // (1 << X) > 30 -> X > 4 1370 if (Pred == ICmpInst::ICMP_ULT) 1371 Pred = ICmpInst::ICMP_ULE; 1372 else if (Pred == ICmpInst::ICMP_UGE) 1373 Pred = ICmpInst::ICMP_UGT; 1374 } 1375 unsigned RHSLog2 = RHSV.logBase2(); 1376 1377 // (1 << X) >= 2147483648 -> X >= 31 -> X == 31 1378 // (1 << X) > 2147483648 -> X > 31 -> false 1379 // (1 << X) <= 2147483648 -> X <= 31 -> true 1380 // (1 << X) < 2147483648 -> X < 31 -> X != 31 1381 if (RHSLog2 == TypeBits-1) { 1382 if (Pred == ICmpInst::ICMP_UGE) 1383 Pred = ICmpInst::ICMP_EQ; 1384 else if (Pred == ICmpInst::ICMP_UGT) 1385 return ReplaceInstUsesWith(ICI, Builder->getFalse()); 1386 else if (Pred == ICmpInst::ICMP_ULE) 1387 return ReplaceInstUsesWith(ICI, Builder->getTrue()); 1388 else if (Pred == ICmpInst::ICMP_ULT) 1389 Pred = ICmpInst::ICMP_NE; 1390 } 1391 1392 return new ICmpInst(Pred, X, 1393 ConstantInt::get(RHS->getType(), RHSLog2)); 1394 } else if (ICI.isSigned()) { 1395 if (RHSV.isAllOnesValue()) { 1396 // (1 << X) <= -1 -> X == 31 1397 if (Pred == ICmpInst::ICMP_SLE) 1398 return new ICmpInst(ICmpInst::ICMP_EQ, X, 1399 ConstantInt::get(RHS->getType(), TypeBits-1)); 1400 1401 // (1 << X) > -1 -> X != 31 1402 if (Pred == ICmpInst::ICMP_SGT) 1403 return new ICmpInst(ICmpInst::ICMP_NE, X, 1404 ConstantInt::get(RHS->getType(), TypeBits-1)); 1405 } else if (!RHSV) { 1406 // (1 << X) < 0 -> X == 31 1407 // (1 << X) <= 0 -> X == 31 1408 if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE) 1409 return new ICmpInst(ICmpInst::ICMP_EQ, X, 1410 ConstantInt::get(RHS->getType(), TypeBits-1)); 1411 1412 // (1 << X) >= 0 -> X != 31 1413 // (1 << X) > 0 -> X != 31 1414 if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE) 1415 return new ICmpInst(ICmpInst::ICMP_NE, X, 1416 ConstantInt::get(RHS->getType(), TypeBits-1)); 1417 } 1418 } else if (ICI.isEquality()) { 1419 if (RHSVIsPowerOf2) 1420 return new ICmpInst( 1421 Pred, X, ConstantInt::get(RHS->getType(), RHSV.logBase2())); 1422 1423 return ReplaceInstUsesWith( 1424 ICI, Pred == ICmpInst::ICMP_EQ ? Builder->getFalse() 1425 : Builder->getTrue()); 1426 } 1427 } 1428 break; 1429 } 1430 1431 // Check that the shift amount is in range. If not, don't perform 1432 // undefined shifts. When the shift is visited it will be 1433 // simplified. 1434 if (ShAmt->uge(TypeBits)) 1435 break; 1436 1437 if (ICI.isEquality()) { 1438 // If we are comparing against bits always shifted out, the 1439 // comparison cannot succeed. 1440 Constant *Comp = 1441 ConstantExpr::getShl(ConstantExpr::getLShr(RHS, ShAmt), 1442 ShAmt); 1443 if (Comp != RHS) {// Comparing against a bit that we know is zero. 1444 bool IsICMP_NE = ICI.getPredicate() == ICmpInst::ICMP_NE; 1445 Constant *Cst = Builder->getInt1(IsICMP_NE); 1446 return ReplaceInstUsesWith(ICI, Cst); 1447 } 1448 1449 // If the shift is NUW, then it is just shifting out zeros, no need for an 1450 // AND. 1451 if (cast<BinaryOperator>(LHSI)->hasNoUnsignedWrap()) 1452 return new ICmpInst(ICI.getPredicate(), LHSI->getOperand(0), 1453 ConstantExpr::getLShr(RHS, ShAmt)); 1454 1455 // If the shift is NSW and we compare to 0, then it is just shifting out 1456 // sign bits, no need for an AND either. 1457 if (cast<BinaryOperator>(LHSI)->hasNoSignedWrap() && RHSV == 0) 1458 return new ICmpInst(ICI.getPredicate(), LHSI->getOperand(0), 1459 ConstantExpr::getLShr(RHS, ShAmt)); 1460 1461 if (LHSI->hasOneUse()) { 1462 // Otherwise strength reduce the shift into an and. 1463 uint32_t ShAmtVal = (uint32_t)ShAmt->getLimitedValue(TypeBits); 1464 Constant *Mask = Builder->getInt(APInt::getLowBitsSet(TypeBits, 1465 TypeBits - ShAmtVal)); 1466 1467 Value *And = 1468 Builder->CreateAnd(LHSI->getOperand(0),Mask, LHSI->getName()+".mask"); 1469 return new ICmpInst(ICI.getPredicate(), And, 1470 ConstantExpr::getLShr(RHS, ShAmt)); 1471 } 1472 } 1473 1474 // If this is a signed comparison to 0 and the shift is sign preserving, 1475 // use the shift LHS operand instead. 1476 ICmpInst::Predicate pred = ICI.getPredicate(); 1477 if (isSignTest(pred, RHS) && 1478 cast<BinaryOperator>(LHSI)->hasNoSignedWrap()) 1479 return new ICmpInst(pred, 1480 LHSI->getOperand(0), 1481 Constant::getNullValue(RHS->getType())); 1482 1483 // Otherwise, if this is a comparison of the sign bit, simplify to and/test. 1484 bool TrueIfSigned = false; 1485 if (LHSI->hasOneUse() && 1486 isSignBitCheck(ICI.getPredicate(), RHS, TrueIfSigned)) { 1487 // (X << 31) <s 0 --> (X&1) != 0 1488 Constant *Mask = ConstantInt::get(LHSI->getOperand(0)->getType(), 1489 APInt::getOneBitSet(TypeBits, 1490 TypeBits-ShAmt->getZExtValue()-1)); 1491 Value *And = 1492 Builder->CreateAnd(LHSI->getOperand(0), Mask, LHSI->getName()+".mask"); 1493 return new ICmpInst(TrueIfSigned ? ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ, 1494 And, Constant::getNullValue(And->getType())); 1495 } 1496 1497 // Transform (icmp pred iM (shl iM %v, N), CI) 1498 // -> (icmp pred i(M-N) (trunc %v iM to i(M-N)), (trunc (CI>>N)) 1499 // Transform the shl to a trunc if (trunc (CI>>N)) has no loss and M-N. 1500 // This enables to get rid of the shift in favor of a trunc which can be 1501 // free on the target. It has the additional benefit of comparing to a 1502 // smaller constant, which will be target friendly. 1503 unsigned Amt = ShAmt->getLimitedValue(TypeBits-1); 1504 if (LHSI->hasOneUse() && 1505 Amt != 0 && RHSV.countTrailingZeros() >= Amt) { 1506 Type *NTy = IntegerType::get(ICI.getContext(), TypeBits - Amt); 1507 Constant *NCI = ConstantExpr::getTrunc( 1508 ConstantExpr::getAShr(RHS, 1509 ConstantInt::get(RHS->getType(), Amt)), 1510 NTy); 1511 return new ICmpInst(ICI.getPredicate(), 1512 Builder->CreateTrunc(LHSI->getOperand(0), NTy), 1513 NCI); 1514 } 1515 1516 break; 1517 } 1518 1519 case Instruction::LShr: // (icmp pred (shr X, ShAmt), CI) 1520 case Instruction::AShr: { 1521 // Handle equality comparisons of shift-by-constant. 1522 BinaryOperator *BO = cast<BinaryOperator>(LHSI); 1523 if (ConstantInt *ShAmt = dyn_cast<ConstantInt>(LHSI->getOperand(1))) { 1524 if (Instruction *Res = FoldICmpShrCst(ICI, BO, ShAmt)) 1525 return Res; 1526 } 1527 1528 // Handle exact shr's. 1529 if (ICI.isEquality() && BO->isExact() && BO->hasOneUse()) { 1530 if (RHSV.isMinValue()) 1531 return new ICmpInst(ICI.getPredicate(), BO->getOperand(0), RHS); 1532 } 1533 break; 1534 } 1535 1536 case Instruction::SDiv: 1537 case Instruction::UDiv: 1538 // Fold: icmp pred ([us]div X, C1), C2 -> range test 1539 // Fold this div into the comparison, producing a range check. 1540 // Determine, based on the divide type, what the range is being 1541 // checked. If there is an overflow on the low or high side, remember 1542 // it, otherwise compute the range [low, hi) bounding the new value. 1543 // See: InsertRangeTest above for the kinds of replacements possible. 1544 if (ConstantInt *DivRHS = dyn_cast<ConstantInt>(LHSI->getOperand(1))) 1545 if (Instruction *R = FoldICmpDivCst(ICI, cast<BinaryOperator>(LHSI), 1546 DivRHS)) 1547 return R; 1548 break; 1549 1550 case Instruction::Sub: { 1551 ConstantInt *LHSC = dyn_cast<ConstantInt>(LHSI->getOperand(0)); 1552 if (!LHSC) break; 1553 const APInt &LHSV = LHSC->getValue(); 1554 1555 // C1-X <u C2 -> (X|(C2-1)) == C1 1556 // iff C1 & (C2-1) == C2-1 1557 // C2 is a power of 2 1558 if (ICI.getPredicate() == ICmpInst::ICMP_ULT && LHSI->hasOneUse() && 1559 RHSV.isPowerOf2() && (LHSV & (RHSV - 1)) == (RHSV - 1)) 1560 return new ICmpInst(ICmpInst::ICMP_EQ, 1561 Builder->CreateOr(LHSI->getOperand(1), RHSV - 1), 1562 LHSC); 1563 1564 // C1-X >u C2 -> (X|C2) != C1 1565 // iff C1 & C2 == C2 1566 // C2+1 is a power of 2 1567 if (ICI.getPredicate() == ICmpInst::ICMP_UGT && LHSI->hasOneUse() && 1568 (RHSV + 1).isPowerOf2() && (LHSV & RHSV) == RHSV) 1569 return new ICmpInst(ICmpInst::ICMP_NE, 1570 Builder->CreateOr(LHSI->getOperand(1), RHSV), LHSC); 1571 break; 1572 } 1573 1574 case Instruction::Add: 1575 // Fold: icmp pred (add X, C1), C2 1576 if (!ICI.isEquality()) { 1577 ConstantInt *LHSC = dyn_cast<ConstantInt>(LHSI->getOperand(1)); 1578 if (!LHSC) break; 1579 const APInt &LHSV = LHSC->getValue(); 1580 1581 ConstantRange CR = ICI.makeConstantRange(ICI.getPredicate(), RHSV) 1582 .subtract(LHSV); 1583 1584 if (ICI.isSigned()) { 1585 if (CR.getLower().isSignBit()) { 1586 return new ICmpInst(ICmpInst::ICMP_SLT, LHSI->getOperand(0), 1587 Builder->getInt(CR.getUpper())); 1588 } else if (CR.getUpper().isSignBit()) { 1589 return new ICmpInst(ICmpInst::ICMP_SGE, LHSI->getOperand(0), 1590 Builder->getInt(CR.getLower())); 1591 } 1592 } else { 1593 if (CR.getLower().isMinValue()) { 1594 return new ICmpInst(ICmpInst::ICMP_ULT, LHSI->getOperand(0), 1595 Builder->getInt(CR.getUpper())); 1596 } else if (CR.getUpper().isMinValue()) { 1597 return new ICmpInst(ICmpInst::ICMP_UGE, LHSI->getOperand(0), 1598 Builder->getInt(CR.getLower())); 1599 } 1600 } 1601 1602 // X-C1 <u C2 -> (X & -C2) == C1 1603 // iff C1 & (C2-1) == 0 1604 // C2 is a power of 2 1605 if (ICI.getPredicate() == ICmpInst::ICMP_ULT && LHSI->hasOneUse() && 1606 RHSV.isPowerOf2() && (LHSV & (RHSV - 1)) == 0) 1607 return new ICmpInst(ICmpInst::ICMP_EQ, 1608 Builder->CreateAnd(LHSI->getOperand(0), -RHSV), 1609 ConstantExpr::getNeg(LHSC)); 1610 1611 // X-C1 >u C2 -> (X & ~C2) != C1 1612 // iff C1 & C2 == 0 1613 // C2+1 is a power of 2 1614 if (ICI.getPredicate() == ICmpInst::ICMP_UGT && LHSI->hasOneUse() && 1615 (RHSV + 1).isPowerOf2() && (LHSV & RHSV) == 0) 1616 return new ICmpInst(ICmpInst::ICMP_NE, 1617 Builder->CreateAnd(LHSI->getOperand(0), ~RHSV), 1618 ConstantExpr::getNeg(LHSC)); 1619 } 1620 break; 1621 } 1622 1623 // Simplify icmp_eq and icmp_ne instructions with integer constant RHS. 1624 if (ICI.isEquality()) { 1625 bool isICMP_NE = ICI.getPredicate() == ICmpInst::ICMP_NE; 1626 1627 // If the first operand is (add|sub|and|or|xor|rem) with a constant, and 1628 // the second operand is a constant, simplify a bit. 1629 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(LHSI)) { 1630 switch (BO->getOpcode()) { 1631 case Instruction::SRem: 1632 // If we have a signed (X % (2^c)) == 0, turn it into an unsigned one. 1633 if (RHSV == 0 && isa<ConstantInt>(BO->getOperand(1)) &&BO->hasOneUse()){ 1634 const APInt &V = cast<ConstantInt>(BO->getOperand(1))->getValue(); 1635 if (V.sgt(1) && V.isPowerOf2()) { 1636 Value *NewRem = 1637 Builder->CreateURem(BO->getOperand(0), BO->getOperand(1), 1638 BO->getName()); 1639 return new ICmpInst(ICI.getPredicate(), NewRem, 1640 Constant::getNullValue(BO->getType())); 1641 } 1642 } 1643 break; 1644 case Instruction::Add: 1645 // Replace ((add A, B) != C) with (A != C-B) if B & C are constants. 1646 if (ConstantInt *BOp1C = dyn_cast<ConstantInt>(BO->getOperand(1))) { 1647 if (BO->hasOneUse()) 1648 return new ICmpInst(ICI.getPredicate(), BO->getOperand(0), 1649 ConstantExpr::getSub(RHS, BOp1C)); 1650 } else if (RHSV == 0) { 1651 // Replace ((add A, B) != 0) with (A != -B) if A or B is 1652 // efficiently invertible, or if the add has just this one use. 1653 Value *BOp0 = BO->getOperand(0), *BOp1 = BO->getOperand(1); 1654 1655 if (Value *NegVal = dyn_castNegVal(BOp1)) 1656 return new ICmpInst(ICI.getPredicate(), BOp0, NegVal); 1657 if (Value *NegVal = dyn_castNegVal(BOp0)) 1658 return new ICmpInst(ICI.getPredicate(), NegVal, BOp1); 1659 if (BO->hasOneUse()) { 1660 Value *Neg = Builder->CreateNeg(BOp1); 1661 Neg->takeName(BO); 1662 return new ICmpInst(ICI.getPredicate(), BOp0, Neg); 1663 } 1664 } 1665 break; 1666 case Instruction::Xor: 1667 // For the xor case, we can xor two constants together, eliminating 1668 // the explicit xor. 1669 if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1))) { 1670 return new ICmpInst(ICI.getPredicate(), BO->getOperand(0), 1671 ConstantExpr::getXor(RHS, BOC)); 1672 } else if (RHSV == 0) { 1673 // Replace ((xor A, B) != 0) with (A != B) 1674 return new ICmpInst(ICI.getPredicate(), BO->getOperand(0), 1675 BO->getOperand(1)); 1676 } 1677 break; 1678 case Instruction::Sub: 1679 // Replace ((sub A, B) != C) with (B != A-C) if A & C are constants. 1680 if (ConstantInt *BOp0C = dyn_cast<ConstantInt>(BO->getOperand(0))) { 1681 if (BO->hasOneUse()) 1682 return new ICmpInst(ICI.getPredicate(), BO->getOperand(1), 1683 ConstantExpr::getSub(BOp0C, RHS)); 1684 } else if (RHSV == 0) { 1685 // Replace ((sub A, B) != 0) with (A != B) 1686 return new ICmpInst(ICI.getPredicate(), BO->getOperand(0), 1687 BO->getOperand(1)); 1688 } 1689 break; 1690 case Instruction::Or: 1691 // If bits are being or'd in that are not present in the constant we 1692 // are comparing against, then the comparison could never succeed! 1693 if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) { 1694 Constant *NotCI = ConstantExpr::getNot(RHS); 1695 if (!ConstantExpr::getAnd(BOC, NotCI)->isNullValue()) 1696 return ReplaceInstUsesWith(ICI, Builder->getInt1(isICMP_NE)); 1697 } 1698 break; 1699 1700 case Instruction::And: 1701 if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) { 1702 // If bits are being compared against that are and'd out, then the 1703 // comparison can never succeed! 1704 if ((RHSV & ~BOC->getValue()) != 0) 1705 return ReplaceInstUsesWith(ICI, Builder->getInt1(isICMP_NE)); 1706 1707 // If we have ((X & C) == C), turn it into ((X & C) != 0). 1708 if (RHS == BOC && RHSV.isPowerOf2()) 1709 return new ICmpInst(isICMP_NE ? ICmpInst::ICMP_EQ : 1710 ICmpInst::ICMP_NE, LHSI, 1711 Constant::getNullValue(RHS->getType())); 1712 1713 // Don't perform the following transforms if the AND has multiple uses 1714 if (!BO->hasOneUse()) 1715 break; 1716 1717 // Replace (and X, (1 << size(X)-1) != 0) with x s< 0 1718 if (BOC->getValue().isSignBit()) { 1719 Value *X = BO->getOperand(0); 1720 Constant *Zero = Constant::getNullValue(X->getType()); 1721 ICmpInst::Predicate pred = isICMP_NE ? 1722 ICmpInst::ICMP_SLT : ICmpInst::ICMP_SGE; 1723 return new ICmpInst(pred, X, Zero); 1724 } 1725 1726 // ((X & ~7) == 0) --> X < 8 1727 if (RHSV == 0 && isHighOnes(BOC)) { 1728 Value *X = BO->getOperand(0); 1729 Constant *NegX = ConstantExpr::getNeg(BOC); 1730 ICmpInst::Predicate pred = isICMP_NE ? 1731 ICmpInst::ICMP_UGE : ICmpInst::ICMP_ULT; 1732 return new ICmpInst(pred, X, NegX); 1733 } 1734 } 1735 break; 1736 case Instruction::Mul: 1737 if (RHSV == 0 && BO->hasNoSignedWrap()) { 1738 if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) { 1739 // The trivial case (mul X, 0) is handled by InstSimplify 1740 // General case : (mul X, C) != 0 iff X != 0 1741 // (mul X, C) == 0 iff X == 0 1742 if (!BOC->isZero()) 1743 return new ICmpInst(ICI.getPredicate(), BO->getOperand(0), 1744 Constant::getNullValue(RHS->getType())); 1745 } 1746 } 1747 break; 1748 default: break; 1749 } 1750 } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(LHSI)) { 1751 // Handle icmp {eq|ne} <intrinsic>, intcst. 1752 switch (II->getIntrinsicID()) { 1753 case Intrinsic::bswap: 1754 Worklist.Add(II); 1755 ICI.setOperand(0, II->getArgOperand(0)); 1756 ICI.setOperand(1, Builder->getInt(RHSV.byteSwap())); 1757 return &ICI; 1758 case Intrinsic::ctlz: 1759 case Intrinsic::cttz: 1760 // ctz(A) == bitwidth(a) -> A == 0 and likewise for != 1761 if (RHSV == RHS->getType()->getBitWidth()) { 1762 Worklist.Add(II); 1763 ICI.setOperand(0, II->getArgOperand(0)); 1764 ICI.setOperand(1, ConstantInt::get(RHS->getType(), 0)); 1765 return &ICI; 1766 } 1767 break; 1768 case Intrinsic::ctpop: 1769 // popcount(A) == 0 -> A == 0 and likewise for != 1770 if (RHS->isZero()) { 1771 Worklist.Add(II); 1772 ICI.setOperand(0, II->getArgOperand(0)); 1773 ICI.setOperand(1, RHS); 1774 return &ICI; 1775 } 1776 break; 1777 default: 1778 break; 1779 } 1780 } 1781 } 1782 return nullptr; 1783} 1784 1785/// visitICmpInstWithCastAndCast - Handle icmp (cast x to y), (cast/cst). 1786/// We only handle extending casts so far. 1787/// 1788Instruction *InstCombiner::visitICmpInstWithCastAndCast(ICmpInst &ICI) { 1789 const CastInst *LHSCI = cast<CastInst>(ICI.getOperand(0)); 1790 Value *LHSCIOp = LHSCI->getOperand(0); 1791 Type *SrcTy = LHSCIOp->getType(); 1792 Type *DestTy = LHSCI->getType(); 1793 Value *RHSCIOp; 1794 1795 // Turn icmp (ptrtoint x), (ptrtoint/c) into a compare of the input if the 1796 // integer type is the same size as the pointer type. 1797 if (DL && LHSCI->getOpcode() == Instruction::PtrToInt && 1798 DL->getPointerTypeSizeInBits(SrcTy) == DestTy->getIntegerBitWidth()) { 1799 Value *RHSOp = nullptr; 1800 if (Constant *RHSC = dyn_cast<Constant>(ICI.getOperand(1))) { 1801 RHSOp = ConstantExpr::getIntToPtr(RHSC, SrcTy); 1802 } else if (PtrToIntInst *RHSC = dyn_cast<PtrToIntInst>(ICI.getOperand(1))) { 1803 RHSOp = RHSC->getOperand(0); 1804 // If the pointer types don't match, insert a bitcast. 1805 if (LHSCIOp->getType() != RHSOp->getType()) 1806 RHSOp = Builder->CreateBitCast(RHSOp, LHSCIOp->getType()); 1807 } 1808 1809 if (RHSOp) 1810 return new ICmpInst(ICI.getPredicate(), LHSCIOp, RHSOp); 1811 } 1812 1813 // The code below only handles extension cast instructions, so far. 1814 // Enforce this. 1815 if (LHSCI->getOpcode() != Instruction::ZExt && 1816 LHSCI->getOpcode() != Instruction::SExt) 1817 return nullptr; 1818 1819 bool isSignedExt = LHSCI->getOpcode() == Instruction::SExt; 1820 bool isSignedCmp = ICI.isSigned(); 1821 1822 if (CastInst *CI = dyn_cast<CastInst>(ICI.getOperand(1))) { 1823 // Not an extension from the same type? 1824 RHSCIOp = CI->getOperand(0); 1825 if (RHSCIOp->getType() != LHSCIOp->getType()) 1826 return nullptr; 1827 1828 // If the signedness of the two casts doesn't agree (i.e. one is a sext 1829 // and the other is a zext), then we can't handle this. 1830 if (CI->getOpcode() != LHSCI->getOpcode()) 1831 return nullptr; 1832 1833 // Deal with equality cases early. 1834 if (ICI.isEquality()) 1835 return new ICmpInst(ICI.getPredicate(), LHSCIOp, RHSCIOp); 1836 1837 // A signed comparison of sign extended values simplifies into a 1838 // signed comparison. 1839 if (isSignedCmp && isSignedExt) 1840 return new ICmpInst(ICI.getPredicate(), LHSCIOp, RHSCIOp); 1841 1842 // The other three cases all fold into an unsigned comparison. 1843 return new ICmpInst(ICI.getUnsignedPredicate(), LHSCIOp, RHSCIOp); 1844 } 1845 1846 // If we aren't dealing with a constant on the RHS, exit early 1847 ConstantInt *CI = dyn_cast<ConstantInt>(ICI.getOperand(1)); 1848 if (!CI) 1849 return nullptr; 1850 1851 // Compute the constant that would happen if we truncated to SrcTy then 1852 // reextended to DestTy. 1853 Constant *Res1 = ConstantExpr::getTrunc(CI, SrcTy); 1854 Constant *Res2 = ConstantExpr::getCast(LHSCI->getOpcode(), 1855 Res1, DestTy); 1856 1857 // If the re-extended constant didn't change... 1858 if (Res2 == CI) { 1859 // Deal with equality cases early. 1860 if (ICI.isEquality()) 1861 return new ICmpInst(ICI.getPredicate(), LHSCIOp, Res1); 1862 1863 // A signed comparison of sign extended values simplifies into a 1864 // signed comparison. 1865 if (isSignedExt && isSignedCmp) 1866 return new ICmpInst(ICI.getPredicate(), LHSCIOp, Res1); 1867 1868 // The other three cases all fold into an unsigned comparison. 1869 return new ICmpInst(ICI.getUnsignedPredicate(), LHSCIOp, Res1); 1870 } 1871 1872 // The re-extended constant changed so the constant cannot be represented 1873 // in the shorter type. Consequently, we cannot emit a simple comparison. 1874 // All the cases that fold to true or false will have already been handled 1875 // by SimplifyICmpInst, so only deal with the tricky case. 1876 1877 if (isSignedCmp || !isSignedExt) 1878 return nullptr; 1879 1880 // Evaluate the comparison for LT (we invert for GT below). LE and GE cases 1881 // should have been folded away previously and not enter in here. 1882 1883 // We're performing an unsigned comp with a sign extended value. 1884 // This is true if the input is >= 0. [aka >s -1] 1885 Constant *NegOne = Constant::getAllOnesValue(SrcTy); 1886 Value *Result = Builder->CreateICmpSGT(LHSCIOp, NegOne, ICI.getName()); 1887 1888 // Finally, return the value computed. 1889 if (ICI.getPredicate() == ICmpInst::ICMP_ULT) 1890 return ReplaceInstUsesWith(ICI, Result); 1891 1892 assert(ICI.getPredicate() == ICmpInst::ICMP_UGT && "ICmp should be folded!"); 1893 return BinaryOperator::CreateNot(Result); 1894} 1895 1896/// ProcessUGT_ADDCST_ADD - The caller has matched a pattern of the form: 1897/// I = icmp ugt (add (add A, B), CI2), CI1 1898/// If this is of the form: 1899/// sum = a + b 1900/// if (sum+128 >u 255) 1901/// Then replace it with llvm.sadd.with.overflow.i8. 1902/// 1903static Instruction *ProcessUGT_ADDCST_ADD(ICmpInst &I, Value *A, Value *B, 1904 ConstantInt *CI2, ConstantInt *CI1, 1905 InstCombiner &IC) { 1906 // The transformation we're trying to do here is to transform this into an 1907 // llvm.sadd.with.overflow. To do this, we have to replace the original add 1908 // with a narrower add, and discard the add-with-constant that is part of the 1909 // range check (if we can't eliminate it, this isn't profitable). 1910 1911 // In order to eliminate the add-with-constant, the compare can be its only 1912 // use. 1913 Instruction *AddWithCst = cast<Instruction>(I.getOperand(0)); 1914 if (!AddWithCst->hasOneUse()) return nullptr; 1915 1916 // If CI2 is 2^7, 2^15, 2^31, then it might be an sadd.with.overflow. 1917 if (!CI2->getValue().isPowerOf2()) return nullptr; 1918 unsigned NewWidth = CI2->getValue().countTrailingZeros(); 1919 if (NewWidth != 7 && NewWidth != 15 && NewWidth != 31) return nullptr; 1920 1921 // The width of the new add formed is 1 more than the bias. 1922 ++NewWidth; 1923 1924 // Check to see that CI1 is an all-ones value with NewWidth bits. 1925 if (CI1->getBitWidth() == NewWidth || 1926 CI1->getValue() != APInt::getLowBitsSet(CI1->getBitWidth(), NewWidth)) 1927 return nullptr; 1928 1929 // This is only really a signed overflow check if the inputs have been 1930 // sign-extended; check for that condition. For example, if CI2 is 2^31 and 1931 // the operands of the add are 64 bits wide, we need at least 33 sign bits. 1932 unsigned NeededSignBits = CI1->getBitWidth() - NewWidth + 1; 1933 if (IC.ComputeNumSignBits(A) < NeededSignBits || 1934 IC.ComputeNumSignBits(B) < NeededSignBits) 1935 return nullptr; 1936 1937 // In order to replace the original add with a narrower 1938 // llvm.sadd.with.overflow, the only uses allowed are the add-with-constant 1939 // and truncates that discard the high bits of the add. Verify that this is 1940 // the case. 1941 Instruction *OrigAdd = cast<Instruction>(AddWithCst->getOperand(0)); 1942 for (User *U : OrigAdd->users()) { 1943 if (U == AddWithCst) continue; 1944 1945 // Only accept truncates for now. We would really like a nice recursive 1946 // predicate like SimplifyDemandedBits, but which goes downwards the use-def 1947 // chain to see which bits of a value are actually demanded. If the 1948 // original add had another add which was then immediately truncated, we 1949 // could still do the transformation. 1950 TruncInst *TI = dyn_cast<TruncInst>(U); 1951 if (!TI || TI->getType()->getPrimitiveSizeInBits() > NewWidth) 1952 return nullptr; 1953 } 1954 1955 // If the pattern matches, truncate the inputs to the narrower type and 1956 // use the sadd_with_overflow intrinsic to efficiently compute both the 1957 // result and the overflow bit. 1958 Module *M = I.getParent()->getParent()->getParent(); 1959 1960 Type *NewType = IntegerType::get(OrigAdd->getContext(), NewWidth); 1961 Value *F = Intrinsic::getDeclaration(M, Intrinsic::sadd_with_overflow, 1962 NewType); 1963 1964 InstCombiner::BuilderTy *Builder = IC.Builder; 1965 1966 // Put the new code above the original add, in case there are any uses of the 1967 // add between the add and the compare. 1968 Builder->SetInsertPoint(OrigAdd); 1969 1970 Value *TruncA = Builder->CreateTrunc(A, NewType, A->getName()+".trunc"); 1971 Value *TruncB = Builder->CreateTrunc(B, NewType, B->getName()+".trunc"); 1972 CallInst *Call = Builder->CreateCall2(F, TruncA, TruncB, "sadd"); 1973 Value *Add = Builder->CreateExtractValue(Call, 0, "sadd.result"); 1974 Value *ZExt = Builder->CreateZExt(Add, OrigAdd->getType()); 1975 1976 // The inner add was the result of the narrow add, zero extended to the 1977 // wider type. Replace it with the result computed by the intrinsic. 1978 IC.ReplaceInstUsesWith(*OrigAdd, ZExt); 1979 1980 // The original icmp gets replaced with the overflow value. 1981 return ExtractValueInst::Create(Call, 1, "sadd.overflow"); 1982} 1983 1984static Instruction *ProcessUAddIdiom(Instruction &I, Value *OrigAddV, 1985 InstCombiner &IC) { 1986 // Don't bother doing this transformation for pointers, don't do it for 1987 // vectors. 1988 if (!isa<IntegerType>(OrigAddV->getType())) return nullptr; 1989 1990 // If the add is a constant expr, then we don't bother transforming it. 1991 Instruction *OrigAdd = dyn_cast<Instruction>(OrigAddV); 1992 if (!OrigAdd) return nullptr; 1993 1994 Value *LHS = OrigAdd->getOperand(0), *RHS = OrigAdd->getOperand(1); 1995 1996 // Put the new code above the original add, in case there are any uses of the 1997 // add between the add and the compare. 1998 InstCombiner::BuilderTy *Builder = IC.Builder; 1999 Builder->SetInsertPoint(OrigAdd); 2000 2001 Module *M = I.getParent()->getParent()->getParent(); 2002 Type *Ty = LHS->getType(); 2003 Value *F = Intrinsic::getDeclaration(M, Intrinsic::uadd_with_overflow, Ty); 2004 CallInst *Call = Builder->CreateCall2(F, LHS, RHS, "uadd"); 2005 Value *Add = Builder->CreateExtractValue(Call, 0); 2006 2007 IC.ReplaceInstUsesWith(*OrigAdd, Add); 2008 2009 // The original icmp gets replaced with the overflow value. 2010 return ExtractValueInst::Create(Call, 1, "uadd.overflow"); 2011} 2012 2013/// \brief Recognize and process idiom involving test for multiplication 2014/// overflow. 2015/// 2016/// The caller has matched a pattern of the form: 2017/// I = cmp u (mul(zext A, zext B), V 2018/// The function checks if this is a test for overflow and if so replaces 2019/// multiplication with call to 'mul.with.overflow' intrinsic. 2020/// 2021/// \param I Compare instruction. 2022/// \param MulVal Result of 'mult' instruction. It is one of the arguments of 2023/// the compare instruction. Must be of integer type. 2024/// \param OtherVal The other argument of compare instruction. 2025/// \returns Instruction which must replace the compare instruction, NULL if no 2026/// replacement required. 2027static Instruction *ProcessUMulZExtIdiom(ICmpInst &I, Value *MulVal, 2028 Value *OtherVal, InstCombiner &IC) { 2029 assert(I.getOperand(0) == MulVal || I.getOperand(1) == MulVal); 2030 assert(I.getOperand(0) == OtherVal || I.getOperand(1) == OtherVal); 2031 assert(isa<IntegerType>(MulVal->getType())); 2032 Instruction *MulInstr = cast<Instruction>(MulVal); 2033 assert(MulInstr->getOpcode() == Instruction::Mul); 2034 2035 Instruction *LHS = cast<Instruction>(MulInstr->getOperand(0)), 2036 *RHS = cast<Instruction>(MulInstr->getOperand(1)); 2037 assert(LHS->getOpcode() == Instruction::ZExt); 2038 assert(RHS->getOpcode() == Instruction::ZExt); 2039 Value *A = LHS->getOperand(0), *B = RHS->getOperand(0); 2040 2041 // Calculate type and width of the result produced by mul.with.overflow. 2042 Type *TyA = A->getType(), *TyB = B->getType(); 2043 unsigned WidthA = TyA->getPrimitiveSizeInBits(), 2044 WidthB = TyB->getPrimitiveSizeInBits(); 2045 unsigned MulWidth; 2046 Type *MulType; 2047 if (WidthB > WidthA) { 2048 MulWidth = WidthB; 2049 MulType = TyB; 2050 } else { 2051 MulWidth = WidthA; 2052 MulType = TyA; 2053 } 2054 2055 // In order to replace the original mul with a narrower mul.with.overflow, 2056 // all uses must ignore upper bits of the product. The number of used low 2057 // bits must be not greater than the width of mul.with.overflow. 2058 if (MulVal->hasNUsesOrMore(2)) 2059 for (User *U : MulVal->users()) { 2060 if (U == &I) 2061 continue; 2062 if (TruncInst *TI = dyn_cast<TruncInst>(U)) { 2063 // Check if truncation ignores bits above MulWidth. 2064 unsigned TruncWidth = TI->getType()->getPrimitiveSizeInBits(); 2065 if (TruncWidth > MulWidth) 2066 return nullptr; 2067 } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(U)) { 2068 // Check if AND ignores bits above MulWidth. 2069 if (BO->getOpcode() != Instruction::And) 2070 return nullptr; 2071 if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) { 2072 const APInt &CVal = CI->getValue(); 2073 if (CVal.getBitWidth() - CVal.countLeadingZeros() > MulWidth) 2074 return nullptr; 2075 } 2076 } else { 2077 // Other uses prohibit this transformation. 2078 return nullptr; 2079 } 2080 } 2081 2082 // Recognize patterns 2083 switch (I.getPredicate()) { 2084 case ICmpInst::ICMP_EQ: 2085 case ICmpInst::ICMP_NE: 2086 // Recognize pattern: 2087 // mulval = mul(zext A, zext B) 2088 // cmp eq/neq mulval, zext trunc mulval 2089 if (ZExtInst *Zext = dyn_cast<ZExtInst>(OtherVal)) 2090 if (Zext->hasOneUse()) { 2091 Value *ZextArg = Zext->getOperand(0); 2092 if (TruncInst *Trunc = dyn_cast<TruncInst>(ZextArg)) 2093 if (Trunc->getType()->getPrimitiveSizeInBits() == MulWidth) 2094 break; //Recognized 2095 } 2096 2097 // Recognize pattern: 2098 // mulval = mul(zext A, zext B) 2099 // cmp eq/neq mulval, and(mulval, mask), mask selects low MulWidth bits. 2100 ConstantInt *CI; 2101 Value *ValToMask; 2102 if (match(OtherVal, m_And(m_Value(ValToMask), m_ConstantInt(CI)))) { 2103 if (ValToMask != MulVal) 2104 return nullptr; 2105 const APInt &CVal = CI->getValue() + 1; 2106 if (CVal.isPowerOf2()) { 2107 unsigned MaskWidth = CVal.logBase2(); 2108 if (MaskWidth == MulWidth) 2109 break; // Recognized 2110 } 2111 } 2112 return nullptr; 2113 2114 case ICmpInst::ICMP_UGT: 2115 // Recognize pattern: 2116 // mulval = mul(zext A, zext B) 2117 // cmp ugt mulval, max 2118 if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) { 2119 APInt MaxVal = APInt::getMaxValue(MulWidth); 2120 MaxVal = MaxVal.zext(CI->getBitWidth()); 2121 if (MaxVal.eq(CI->getValue())) 2122 break; // Recognized 2123 } 2124 return nullptr; 2125 2126 case ICmpInst::ICMP_UGE: 2127 // Recognize pattern: 2128 // mulval = mul(zext A, zext B) 2129 // cmp uge mulval, max+1 2130 if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) { 2131 APInt MaxVal = APInt::getOneBitSet(CI->getBitWidth(), MulWidth); 2132 if (MaxVal.eq(CI->getValue())) 2133 break; // Recognized 2134 } 2135 return nullptr; 2136 2137 case ICmpInst::ICMP_ULE: 2138 // Recognize pattern: 2139 // mulval = mul(zext A, zext B) 2140 // cmp ule mulval, max 2141 if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) { 2142 APInt MaxVal = APInt::getMaxValue(MulWidth); 2143 MaxVal = MaxVal.zext(CI->getBitWidth()); 2144 if (MaxVal.eq(CI->getValue())) 2145 break; // Recognized 2146 } 2147 return nullptr; 2148 2149 case ICmpInst::ICMP_ULT: 2150 // Recognize pattern: 2151 // mulval = mul(zext A, zext B) 2152 // cmp ule mulval, max + 1 2153 if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) { 2154 APInt MaxVal = APInt::getOneBitSet(CI->getBitWidth(), MulWidth); 2155 if (MaxVal.eq(CI->getValue())) 2156 break; // Recognized 2157 } 2158 return nullptr; 2159 2160 default: 2161 return nullptr; 2162 } 2163 2164 InstCombiner::BuilderTy *Builder = IC.Builder; 2165 Builder->SetInsertPoint(MulInstr); 2166 Module *M = I.getParent()->getParent()->getParent(); 2167 2168 // Replace: mul(zext A, zext B) --> mul.with.overflow(A, B) 2169 Value *MulA = A, *MulB = B; 2170 if (WidthA < MulWidth) 2171 MulA = Builder->CreateZExt(A, MulType); 2172 if (WidthB < MulWidth) 2173 MulB = Builder->CreateZExt(B, MulType); 2174 Value *F = 2175 Intrinsic::getDeclaration(M, Intrinsic::umul_with_overflow, MulType); 2176 CallInst *Call = Builder->CreateCall2(F, MulA, MulB, "umul"); 2177 IC.Worklist.Add(MulInstr); 2178 2179 // If there are uses of mul result other than the comparison, we know that 2180 // they are truncation or binary AND. Change them to use result of 2181 // mul.with.overflow and adjust properly mask/size. 2182 if (MulVal->hasNUsesOrMore(2)) { 2183 Value *Mul = Builder->CreateExtractValue(Call, 0, "umul.value"); 2184 for (User *U : MulVal->users()) { 2185 if (U == &I || U == OtherVal) 2186 continue; 2187 if (TruncInst *TI = dyn_cast<TruncInst>(U)) { 2188 if (TI->getType()->getPrimitiveSizeInBits() == MulWidth) 2189 IC.ReplaceInstUsesWith(*TI, Mul); 2190 else 2191 TI->setOperand(0, Mul); 2192 } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(U)) { 2193 assert(BO->getOpcode() == Instruction::And); 2194 // Replace (mul & mask) --> zext (mul.with.overflow & short_mask) 2195 ConstantInt *CI = cast<ConstantInt>(BO->getOperand(1)); 2196 APInt ShortMask = CI->getValue().trunc(MulWidth); 2197 Value *ShortAnd = Builder->CreateAnd(Mul, ShortMask); 2198 Instruction *Zext = 2199 cast<Instruction>(Builder->CreateZExt(ShortAnd, BO->getType())); 2200 IC.Worklist.Add(Zext); 2201 IC.ReplaceInstUsesWith(*BO, Zext); 2202 } else { 2203 llvm_unreachable("Unexpected Binary operation"); 2204 } 2205 IC.Worklist.Add(cast<Instruction>(U)); 2206 } 2207 } 2208 if (isa<Instruction>(OtherVal)) 2209 IC.Worklist.Add(cast<Instruction>(OtherVal)); 2210 2211 // The original icmp gets replaced with the overflow value, maybe inverted 2212 // depending on predicate. 2213 bool Inverse = false; 2214 switch (I.getPredicate()) { 2215 case ICmpInst::ICMP_NE: 2216 break; 2217 case ICmpInst::ICMP_EQ: 2218 Inverse = true; 2219 break; 2220 case ICmpInst::ICMP_UGT: 2221 case ICmpInst::ICMP_UGE: 2222 if (I.getOperand(0) == MulVal) 2223 break; 2224 Inverse = true; 2225 break; 2226 case ICmpInst::ICMP_ULT: 2227 case ICmpInst::ICMP_ULE: 2228 if (I.getOperand(1) == MulVal) 2229 break; 2230 Inverse = true; 2231 break; 2232 default: 2233 llvm_unreachable("Unexpected predicate"); 2234 } 2235 if (Inverse) { 2236 Value *Res = Builder->CreateExtractValue(Call, 1); 2237 return BinaryOperator::CreateNot(Res); 2238 } 2239 2240 return ExtractValueInst::Create(Call, 1); 2241} 2242 2243// DemandedBitsLHSMask - When performing a comparison against a constant, 2244// it is possible that not all the bits in the LHS are demanded. This helper 2245// method computes the mask that IS demanded. 2246static APInt DemandedBitsLHSMask(ICmpInst &I, 2247 unsigned BitWidth, bool isSignCheck) { 2248 if (isSignCheck) 2249 return APInt::getSignBit(BitWidth); 2250 2251 ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(1)); 2252 if (!CI) return APInt::getAllOnesValue(BitWidth); 2253 const APInt &RHS = CI->getValue(); 2254 2255 switch (I.getPredicate()) { 2256 // For a UGT comparison, we don't care about any bits that 2257 // correspond to the trailing ones of the comparand. The value of these 2258 // bits doesn't impact the outcome of the comparison, because any value 2259 // greater than the RHS must differ in a bit higher than these due to carry. 2260 case ICmpInst::ICMP_UGT: { 2261 unsigned trailingOnes = RHS.countTrailingOnes(); 2262 APInt lowBitsSet = APInt::getLowBitsSet(BitWidth, trailingOnes); 2263 return ~lowBitsSet; 2264 } 2265 2266 // Similarly, for a ULT comparison, we don't care about the trailing zeros. 2267 // Any value less than the RHS must differ in a higher bit because of carries. 2268 case ICmpInst::ICMP_ULT: { 2269 unsigned trailingZeros = RHS.countTrailingZeros(); 2270 APInt lowBitsSet = APInt::getLowBitsSet(BitWidth, trailingZeros); 2271 return ~lowBitsSet; 2272 } 2273 2274 default: 2275 return APInt::getAllOnesValue(BitWidth); 2276 } 2277 2278} 2279 2280/// \brief Check if the order of \p Op0 and \p Op1 as operand in an ICmpInst 2281/// should be swapped. 2282/// The decision is based on how many times these two operands are reused 2283/// as subtract operands and their positions in those instructions. 2284/// The rational is that several architectures use the same instruction for 2285/// both subtract and cmp, thus it is better if the order of those operands 2286/// match. 2287/// \return true if Op0 and Op1 should be swapped. 2288static bool swapMayExposeCSEOpportunities(const Value * Op0, 2289 const Value * Op1) { 2290 // Filter out pointer value as those cannot appears directly in subtract. 2291 // FIXME: we may want to go through inttoptrs or bitcasts. 2292 if (Op0->getType()->isPointerTy()) 2293 return false; 2294 // Count every uses of both Op0 and Op1 in a subtract. 2295 // Each time Op0 is the first operand, count -1: swapping is bad, the 2296 // subtract has already the same layout as the compare. 2297 // Each time Op0 is the second operand, count +1: swapping is good, the 2298 // subtract has a different layout as the compare. 2299 // At the end, if the benefit is greater than 0, Op0 should come second to 2300 // expose more CSE opportunities. 2301 int GlobalSwapBenefits = 0; 2302 for (const User *U : Op0->users()) { 2303 const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(U); 2304 if (!BinOp || BinOp->getOpcode() != Instruction::Sub) 2305 continue; 2306 // If Op0 is the first argument, this is not beneficial to swap the 2307 // arguments. 2308 int LocalSwapBenefits = -1; 2309 unsigned Op1Idx = 1; 2310 if (BinOp->getOperand(Op1Idx) == Op0) { 2311 Op1Idx = 0; 2312 LocalSwapBenefits = 1; 2313 } 2314 if (BinOp->getOperand(Op1Idx) != Op1) 2315 continue; 2316 GlobalSwapBenefits += LocalSwapBenefits; 2317 } 2318 return GlobalSwapBenefits > 0; 2319} 2320 2321Instruction *InstCombiner::visitICmpInst(ICmpInst &I) { 2322 bool Changed = false; 2323 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 2324 unsigned Op0Cplxity = getComplexity(Op0); 2325 unsigned Op1Cplxity = getComplexity(Op1); 2326 2327 /// Orders the operands of the compare so that they are listed from most 2328 /// complex to least complex. This puts constants before unary operators, 2329 /// before binary operators. 2330 if (Op0Cplxity < Op1Cplxity || 2331 (Op0Cplxity == Op1Cplxity && 2332 swapMayExposeCSEOpportunities(Op0, Op1))) { 2333 I.swapOperands(); 2334 std::swap(Op0, Op1); 2335 Changed = true; 2336 } 2337 2338 if (Value *V = SimplifyICmpInst(I.getPredicate(), Op0, Op1, DL)) 2339 return ReplaceInstUsesWith(I, V); 2340 2341 // comparing -val or val with non-zero is the same as just comparing val 2342 // ie, abs(val) != 0 -> val != 0 2343 if (I.getPredicate() == ICmpInst::ICMP_NE && match(Op1, m_Zero())) 2344 { 2345 Value *Cond, *SelectTrue, *SelectFalse; 2346 if (match(Op0, m_Select(m_Value(Cond), m_Value(SelectTrue), 2347 m_Value(SelectFalse)))) { 2348 if (Value *V = dyn_castNegVal(SelectTrue)) { 2349 if (V == SelectFalse) 2350 return CmpInst::Create(Instruction::ICmp, I.getPredicate(), V, Op1); 2351 } 2352 else if (Value *V = dyn_castNegVal(SelectFalse)) { 2353 if (V == SelectTrue) 2354 return CmpInst::Create(Instruction::ICmp, I.getPredicate(), V, Op1); 2355 } 2356 } 2357 } 2358 2359 Type *Ty = Op0->getType(); 2360 2361 // icmp's with boolean values can always be turned into bitwise operations 2362 if (Ty->isIntegerTy(1)) { 2363 switch (I.getPredicate()) { 2364 default: llvm_unreachable("Invalid icmp instruction!"); 2365 case ICmpInst::ICMP_EQ: { // icmp eq i1 A, B -> ~(A^B) 2366 Value *Xor = Builder->CreateXor(Op0, Op1, I.getName()+"tmp"); 2367 return BinaryOperator::CreateNot(Xor); 2368 } 2369 case ICmpInst::ICMP_NE: // icmp eq i1 A, B -> A^B 2370 return BinaryOperator::CreateXor(Op0, Op1); 2371 2372 case ICmpInst::ICMP_UGT: 2373 std::swap(Op0, Op1); // Change icmp ugt -> icmp ult 2374 // FALL THROUGH 2375 case ICmpInst::ICMP_ULT:{ // icmp ult i1 A, B -> ~A & B 2376 Value *Not = Builder->CreateNot(Op0, I.getName()+"tmp"); 2377 return BinaryOperator::CreateAnd(Not, Op1); 2378 } 2379 case ICmpInst::ICMP_SGT: 2380 std::swap(Op0, Op1); // Change icmp sgt -> icmp slt 2381 // FALL THROUGH 2382 case ICmpInst::ICMP_SLT: { // icmp slt i1 A, B -> A & ~B 2383 Value *Not = Builder->CreateNot(Op1, I.getName()+"tmp"); 2384 return BinaryOperator::CreateAnd(Not, Op0); 2385 } 2386 case ICmpInst::ICMP_UGE: 2387 std::swap(Op0, Op1); // Change icmp uge -> icmp ule 2388 // FALL THROUGH 2389 case ICmpInst::ICMP_ULE: { // icmp ule i1 A, B -> ~A | B 2390 Value *Not = Builder->CreateNot(Op0, I.getName()+"tmp"); 2391 return BinaryOperator::CreateOr(Not, Op1); 2392 } 2393 case ICmpInst::ICMP_SGE: 2394 std::swap(Op0, Op1); // Change icmp sge -> icmp sle 2395 // FALL THROUGH 2396 case ICmpInst::ICMP_SLE: { // icmp sle i1 A, B -> A | ~B 2397 Value *Not = Builder->CreateNot(Op1, I.getName()+"tmp"); 2398 return BinaryOperator::CreateOr(Not, Op0); 2399 } 2400 } 2401 } 2402 2403 unsigned BitWidth = 0; 2404 if (Ty->isIntOrIntVectorTy()) 2405 BitWidth = Ty->getScalarSizeInBits(); 2406 else if (DL) // Pointers require DL info to get their size. 2407 BitWidth = DL->getTypeSizeInBits(Ty->getScalarType()); 2408 2409 bool isSignBit = false; 2410 2411 // See if we are doing a comparison with a constant. 2412 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) { 2413 Value *A = nullptr, *B = nullptr; 2414 2415 // Match the following pattern, which is a common idiom when writing 2416 // overflow-safe integer arithmetic function. The source performs an 2417 // addition in wider type, and explicitly checks for overflow using 2418 // comparisons against INT_MIN and INT_MAX. Simplify this by using the 2419 // sadd_with_overflow intrinsic. 2420 // 2421 // TODO: This could probably be generalized to handle other overflow-safe 2422 // operations if we worked out the formulas to compute the appropriate 2423 // magic constants. 2424 // 2425 // sum = a + b 2426 // if (sum+128 >u 255) ... -> llvm.sadd.with.overflow.i8 2427 { 2428 ConstantInt *CI2; // I = icmp ugt (add (add A, B), CI2), CI 2429 if (I.getPredicate() == ICmpInst::ICMP_UGT && 2430 match(Op0, m_Add(m_Add(m_Value(A), m_Value(B)), m_ConstantInt(CI2)))) 2431 if (Instruction *Res = ProcessUGT_ADDCST_ADD(I, A, B, CI2, CI, *this)) 2432 return Res; 2433 } 2434 2435 // (icmp ne/eq (sub A B) 0) -> (icmp ne/eq A, B) 2436 if (I.isEquality() && CI->isZero() && 2437 match(Op0, m_Sub(m_Value(A), m_Value(B)))) { 2438 // (icmp cond A B) if cond is equality 2439 return new ICmpInst(I.getPredicate(), A, B); 2440 } 2441 2442 // If we have an icmp le or icmp ge instruction, turn it into the 2443 // appropriate icmp lt or icmp gt instruction. This allows us to rely on 2444 // them being folded in the code below. The SimplifyICmpInst code has 2445 // already handled the edge cases for us, so we just assert on them. 2446 switch (I.getPredicate()) { 2447 default: break; 2448 case ICmpInst::ICMP_ULE: 2449 assert(!CI->isMaxValue(false)); // A <=u MAX -> TRUE 2450 return new ICmpInst(ICmpInst::ICMP_ULT, Op0, 2451 Builder->getInt(CI->getValue()+1)); 2452 case ICmpInst::ICMP_SLE: 2453 assert(!CI->isMaxValue(true)); // A <=s MAX -> TRUE 2454 return new ICmpInst(ICmpInst::ICMP_SLT, Op0, 2455 Builder->getInt(CI->getValue()+1)); 2456 case ICmpInst::ICMP_UGE: 2457 assert(!CI->isMinValue(false)); // A >=u MIN -> TRUE 2458 return new ICmpInst(ICmpInst::ICMP_UGT, Op0, 2459 Builder->getInt(CI->getValue()-1)); 2460 case ICmpInst::ICMP_SGE: 2461 assert(!CI->isMinValue(true)); // A >=s MIN -> TRUE 2462 return new ICmpInst(ICmpInst::ICMP_SGT, Op0, 2463 Builder->getInt(CI->getValue()-1)); 2464 } 2465 2466 // If this comparison is a normal comparison, it demands all 2467 // bits, if it is a sign bit comparison, it only demands the sign bit. 2468 bool UnusedBit; 2469 isSignBit = isSignBitCheck(I.getPredicate(), CI, UnusedBit); 2470 } 2471 2472 // See if we can fold the comparison based on range information we can get 2473 // by checking whether bits are known to be zero or one in the input. 2474 if (BitWidth != 0) { 2475 APInt Op0KnownZero(BitWidth, 0), Op0KnownOne(BitWidth, 0); 2476 APInt Op1KnownZero(BitWidth, 0), Op1KnownOne(BitWidth, 0); 2477 2478 if (SimplifyDemandedBits(I.getOperandUse(0), 2479 DemandedBitsLHSMask(I, BitWidth, isSignBit), 2480 Op0KnownZero, Op0KnownOne, 0)) 2481 return &I; 2482 if (SimplifyDemandedBits(I.getOperandUse(1), 2483 APInt::getAllOnesValue(BitWidth), 2484 Op1KnownZero, Op1KnownOne, 0)) 2485 return &I; 2486 2487 // Given the known and unknown bits, compute a range that the LHS could be 2488 // in. Compute the Min, Max and RHS values based on the known bits. For the 2489 // EQ and NE we use unsigned values. 2490 APInt Op0Min(BitWidth, 0), Op0Max(BitWidth, 0); 2491 APInt Op1Min(BitWidth, 0), Op1Max(BitWidth, 0); 2492 if (I.isSigned()) { 2493 ComputeSignedMinMaxValuesFromKnownBits(Op0KnownZero, Op0KnownOne, 2494 Op0Min, Op0Max); 2495 ComputeSignedMinMaxValuesFromKnownBits(Op1KnownZero, Op1KnownOne, 2496 Op1Min, Op1Max); 2497 } else { 2498 ComputeUnsignedMinMaxValuesFromKnownBits(Op0KnownZero, Op0KnownOne, 2499 Op0Min, Op0Max); 2500 ComputeUnsignedMinMaxValuesFromKnownBits(Op1KnownZero, Op1KnownOne, 2501 Op1Min, Op1Max); 2502 } 2503 2504 // If Min and Max are known to be the same, then SimplifyDemandedBits 2505 // figured out that the LHS is a constant. Just constant fold this now so 2506 // that code below can assume that Min != Max. 2507 if (!isa<Constant>(Op0) && Op0Min == Op0Max) 2508 return new ICmpInst(I.getPredicate(), 2509 ConstantInt::get(Op0->getType(), Op0Min), Op1); 2510 if (!isa<Constant>(Op1) && Op1Min == Op1Max) 2511 return new ICmpInst(I.getPredicate(), Op0, 2512 ConstantInt::get(Op1->getType(), Op1Min)); 2513 2514 // Based on the range information we know about the LHS, see if we can 2515 // simplify this comparison. For example, (x&4) < 8 is always true. 2516 switch (I.getPredicate()) { 2517 default: llvm_unreachable("Unknown icmp opcode!"); 2518 case ICmpInst::ICMP_EQ: { 2519 if (Op0Max.ult(Op1Min) || Op0Min.ugt(Op1Max)) 2520 return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType())); 2521 2522 // If all bits are known zero except for one, then we know at most one 2523 // bit is set. If the comparison is against zero, then this is a check 2524 // to see if *that* bit is set. 2525 APInt Op0KnownZeroInverted = ~Op0KnownZero; 2526 if (~Op1KnownZero == 0 && Op0KnownZeroInverted.isPowerOf2()) { 2527 // If the LHS is an AND with the same constant, look through it. 2528 Value *LHS = nullptr; 2529 ConstantInt *LHSC = nullptr; 2530 if (!match(Op0, m_And(m_Value(LHS), m_ConstantInt(LHSC))) || 2531 LHSC->getValue() != Op0KnownZeroInverted) 2532 LHS = Op0; 2533 2534 // If the LHS is 1 << x, and we know the result is a power of 2 like 8, 2535 // then turn "((1 << x)&8) == 0" into "x != 3". 2536 Value *X = nullptr; 2537 if (match(LHS, m_Shl(m_One(), m_Value(X)))) { 2538 unsigned CmpVal = Op0KnownZeroInverted.countTrailingZeros(); 2539 return new ICmpInst(ICmpInst::ICMP_NE, X, 2540 ConstantInt::get(X->getType(), CmpVal)); 2541 } 2542 2543 // If the LHS is 8 >>u x, and we know the result is a power of 2 like 1, 2544 // then turn "((8 >>u x)&1) == 0" into "x != 3". 2545 const APInt *CI; 2546 if (Op0KnownZeroInverted == 1 && 2547 match(LHS, m_LShr(m_Power2(CI), m_Value(X)))) 2548 return new ICmpInst(ICmpInst::ICMP_NE, X, 2549 ConstantInt::get(X->getType(), 2550 CI->countTrailingZeros())); 2551 } 2552 2553 break; 2554 } 2555 case ICmpInst::ICMP_NE: { 2556 if (Op0Max.ult(Op1Min) || Op0Min.ugt(Op1Max)) 2557 return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType())); 2558 2559 // If all bits are known zero except for one, then we know at most one 2560 // bit is set. If the comparison is against zero, then this is a check 2561 // to see if *that* bit is set. 2562 APInt Op0KnownZeroInverted = ~Op0KnownZero; 2563 if (~Op1KnownZero == 0 && Op0KnownZeroInverted.isPowerOf2()) { 2564 // If the LHS is an AND with the same constant, look through it. 2565 Value *LHS = nullptr; 2566 ConstantInt *LHSC = nullptr; 2567 if (!match(Op0, m_And(m_Value(LHS), m_ConstantInt(LHSC))) || 2568 LHSC->getValue() != Op0KnownZeroInverted) 2569 LHS = Op0; 2570 2571 // If the LHS is 1 << x, and we know the result is a power of 2 like 8, 2572 // then turn "((1 << x)&8) != 0" into "x == 3". 2573 Value *X = nullptr; 2574 if (match(LHS, m_Shl(m_One(), m_Value(X)))) { 2575 unsigned CmpVal = Op0KnownZeroInverted.countTrailingZeros(); 2576 return new ICmpInst(ICmpInst::ICMP_EQ, X, 2577 ConstantInt::get(X->getType(), CmpVal)); 2578 } 2579 2580 // If the LHS is 8 >>u x, and we know the result is a power of 2 like 1, 2581 // then turn "((8 >>u x)&1) != 0" into "x == 3". 2582 const APInt *CI; 2583 if (Op0KnownZeroInverted == 1 && 2584 match(LHS, m_LShr(m_Power2(CI), m_Value(X)))) 2585 return new ICmpInst(ICmpInst::ICMP_EQ, X, 2586 ConstantInt::get(X->getType(), 2587 CI->countTrailingZeros())); 2588 } 2589 2590 break; 2591 } 2592 case ICmpInst::ICMP_ULT: 2593 if (Op0Max.ult(Op1Min)) // A <u B -> true if max(A) < min(B) 2594 return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType())); 2595 if (Op0Min.uge(Op1Max)) // A <u B -> false if min(A) >= max(B) 2596 return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType())); 2597 if (Op1Min == Op0Max) // A <u B -> A != B if max(A) == min(B) 2598 return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1); 2599 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) { 2600 if (Op1Max == Op0Min+1) // A <u C -> A == C-1 if min(A)+1 == C 2601 return new ICmpInst(ICmpInst::ICMP_EQ, Op0, 2602 Builder->getInt(CI->getValue()-1)); 2603 2604 // (x <u 2147483648) -> (x >s -1) -> true if sign bit clear 2605 if (CI->isMinValue(true)) 2606 return new ICmpInst(ICmpInst::ICMP_SGT, Op0, 2607 Constant::getAllOnesValue(Op0->getType())); 2608 } 2609 break; 2610 case ICmpInst::ICMP_UGT: 2611 if (Op0Min.ugt(Op1Max)) // A >u B -> true if min(A) > max(B) 2612 return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType())); 2613 if (Op0Max.ule(Op1Min)) // A >u B -> false if max(A) <= max(B) 2614 return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType())); 2615 2616 if (Op1Max == Op0Min) // A >u B -> A != B if min(A) == max(B) 2617 return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1); 2618 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) { 2619 if (Op1Min == Op0Max-1) // A >u C -> A == C+1 if max(a)-1 == C 2620 return new ICmpInst(ICmpInst::ICMP_EQ, Op0, 2621 Builder->getInt(CI->getValue()+1)); 2622 2623 // (x >u 2147483647) -> (x <s 0) -> true if sign bit set 2624 if (CI->isMaxValue(true)) 2625 return new ICmpInst(ICmpInst::ICMP_SLT, Op0, 2626 Constant::getNullValue(Op0->getType())); 2627 } 2628 break; 2629 case ICmpInst::ICMP_SLT: 2630 if (Op0Max.slt(Op1Min)) // A <s B -> true if max(A) < min(C) 2631 return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType())); 2632 if (Op0Min.sge(Op1Max)) // A <s B -> false if min(A) >= max(C) 2633 return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType())); 2634 if (Op1Min == Op0Max) // A <s B -> A != B if max(A) == min(B) 2635 return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1); 2636 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) { 2637 if (Op1Max == Op0Min+1) // A <s C -> A == C-1 if min(A)+1 == C 2638 return new ICmpInst(ICmpInst::ICMP_EQ, Op0, 2639 Builder->getInt(CI->getValue()-1)); 2640 } 2641 break; 2642 case ICmpInst::ICMP_SGT: 2643 if (Op0Min.sgt(Op1Max)) // A >s B -> true if min(A) > max(B) 2644 return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType())); 2645 if (Op0Max.sle(Op1Min)) // A >s B -> false if max(A) <= min(B) 2646 return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType())); 2647 2648 if (Op1Max == Op0Min) // A >s B -> A != B if min(A) == max(B) 2649 return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1); 2650 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) { 2651 if (Op1Min == Op0Max-1) // A >s C -> A == C+1 if max(A)-1 == C 2652 return new ICmpInst(ICmpInst::ICMP_EQ, Op0, 2653 Builder->getInt(CI->getValue()+1)); 2654 } 2655 break; 2656 case ICmpInst::ICMP_SGE: 2657 assert(!isa<ConstantInt>(Op1) && "ICMP_SGE with ConstantInt not folded!"); 2658 if (Op0Min.sge(Op1Max)) // A >=s B -> true if min(A) >= max(B) 2659 return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType())); 2660 if (Op0Max.slt(Op1Min)) // A >=s B -> false if max(A) < min(B) 2661 return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType())); 2662 break; 2663 case ICmpInst::ICMP_SLE: 2664 assert(!isa<ConstantInt>(Op1) && "ICMP_SLE with ConstantInt not folded!"); 2665 if (Op0Max.sle(Op1Min)) // A <=s B -> true if max(A) <= min(B) 2666 return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType())); 2667 if (Op0Min.sgt(Op1Max)) // A <=s B -> false if min(A) > max(B) 2668 return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType())); 2669 break; 2670 case ICmpInst::ICMP_UGE: 2671 assert(!isa<ConstantInt>(Op1) && "ICMP_UGE with ConstantInt not folded!"); 2672 if (Op0Min.uge(Op1Max)) // A >=u B -> true if min(A) >= max(B) 2673 return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType())); 2674 if (Op0Max.ult(Op1Min)) // A >=u B -> false if max(A) < min(B) 2675 return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType())); 2676 break; 2677 case ICmpInst::ICMP_ULE: 2678 assert(!isa<ConstantInt>(Op1) && "ICMP_ULE with ConstantInt not folded!"); 2679 if (Op0Max.ule(Op1Min)) // A <=u B -> true if max(A) <= min(B) 2680 return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType())); 2681 if (Op0Min.ugt(Op1Max)) // A <=u B -> false if min(A) > max(B) 2682 return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType())); 2683 break; 2684 } 2685 2686 // Turn a signed comparison into an unsigned one if both operands 2687 // are known to have the same sign. 2688 if (I.isSigned() && 2689 ((Op0KnownZero.isNegative() && Op1KnownZero.isNegative()) || 2690 (Op0KnownOne.isNegative() && Op1KnownOne.isNegative()))) 2691 return new ICmpInst(I.getUnsignedPredicate(), Op0, Op1); 2692 } 2693 2694 // Test if the ICmpInst instruction is used exclusively by a select as 2695 // part of a minimum or maximum operation. If so, refrain from doing 2696 // any other folding. This helps out other analyses which understand 2697 // non-obfuscated minimum and maximum idioms, such as ScalarEvolution 2698 // and CodeGen. And in this case, at least one of the comparison 2699 // operands has at least one user besides the compare (the select), 2700 // which would often largely negate the benefit of folding anyway. 2701 if (I.hasOneUse()) 2702 if (SelectInst *SI = dyn_cast<SelectInst>(*I.user_begin())) 2703 if ((SI->getOperand(1) == Op0 && SI->getOperand(2) == Op1) || 2704 (SI->getOperand(2) == Op0 && SI->getOperand(1) == Op1)) 2705 return nullptr; 2706 2707 // See if we are doing a comparison between a constant and an instruction that 2708 // can be folded into the comparison. 2709 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) { 2710 // Since the RHS is a ConstantInt (CI), if the left hand side is an 2711 // instruction, see if that instruction also has constants so that the 2712 // instruction can be folded into the icmp 2713 if (Instruction *LHSI = dyn_cast<Instruction>(Op0)) 2714 if (Instruction *Res = visitICmpInstWithInstAndIntCst(I, LHSI, CI)) 2715 return Res; 2716 } 2717 2718 // Handle icmp with constant (but not simple integer constant) RHS 2719 if (Constant *RHSC = dyn_cast<Constant>(Op1)) { 2720 if (Instruction *LHSI = dyn_cast<Instruction>(Op0)) 2721 switch (LHSI->getOpcode()) { 2722 case Instruction::GetElementPtr: 2723 // icmp pred GEP (P, int 0, int 0, int 0), null -> icmp pred P, null 2724 if (RHSC->isNullValue() && 2725 cast<GetElementPtrInst>(LHSI)->hasAllZeroIndices()) 2726 return new ICmpInst(I.getPredicate(), LHSI->getOperand(0), 2727 Constant::getNullValue(LHSI->getOperand(0)->getType())); 2728 break; 2729 case Instruction::PHI: 2730 // Only fold icmp into the PHI if the phi and icmp are in the same 2731 // block. If in the same block, we're encouraging jump threading. If 2732 // not, we are just pessimizing the code by making an i1 phi. 2733 if (LHSI->getParent() == I.getParent()) 2734 if (Instruction *NV = FoldOpIntoPhi(I)) 2735 return NV; 2736 break; 2737 case Instruction::Select: { 2738 // If either operand of the select is a constant, we can fold the 2739 // comparison into the select arms, which will cause one to be 2740 // constant folded and the select turned into a bitwise or. 2741 Value *Op1 = nullptr, *Op2 = nullptr; 2742 if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(1))) 2743 Op1 = ConstantExpr::getICmp(I.getPredicate(), C, RHSC); 2744 if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(2))) 2745 Op2 = ConstantExpr::getICmp(I.getPredicate(), C, RHSC); 2746 2747 // We only want to perform this transformation if it will not lead to 2748 // additional code. This is true if either both sides of the select 2749 // fold to a constant (in which case the icmp is replaced with a select 2750 // which will usually simplify) or this is the only user of the 2751 // select (in which case we are trading a select+icmp for a simpler 2752 // select+icmp). 2753 if ((Op1 && Op2) || (LHSI->hasOneUse() && (Op1 || Op2))) { 2754 if (!Op1) 2755 Op1 = Builder->CreateICmp(I.getPredicate(), LHSI->getOperand(1), 2756 RHSC, I.getName()); 2757 if (!Op2) 2758 Op2 = Builder->CreateICmp(I.getPredicate(), LHSI->getOperand(2), 2759 RHSC, I.getName()); 2760 return SelectInst::Create(LHSI->getOperand(0), Op1, Op2); 2761 } 2762 break; 2763 } 2764 case Instruction::IntToPtr: 2765 // icmp pred inttoptr(X), null -> icmp pred X, 0 2766 if (RHSC->isNullValue() && DL && 2767 DL->getIntPtrType(RHSC->getType()) == 2768 LHSI->getOperand(0)->getType()) 2769 return new ICmpInst(I.getPredicate(), LHSI->getOperand(0), 2770 Constant::getNullValue(LHSI->getOperand(0)->getType())); 2771 break; 2772 2773 case Instruction::Load: 2774 // Try to optimize things like "A[i] > 4" to index computations. 2775 if (GetElementPtrInst *GEP = 2776 dyn_cast<GetElementPtrInst>(LHSI->getOperand(0))) { 2777 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0))) 2778 if (GV->isConstant() && GV->hasDefinitiveInitializer() && 2779 !cast<LoadInst>(LHSI)->isVolatile()) 2780 if (Instruction *Res = FoldCmpLoadFromIndexedGlobal(GEP, GV, I)) 2781 return Res; 2782 } 2783 break; 2784 } 2785 } 2786 2787 // If we can optimize a 'icmp GEP, P' or 'icmp P, GEP', do so now. 2788 if (GEPOperator *GEP = dyn_cast<GEPOperator>(Op0)) 2789 if (Instruction *NI = FoldGEPICmp(GEP, Op1, I.getPredicate(), I)) 2790 return NI; 2791 if (GEPOperator *GEP = dyn_cast<GEPOperator>(Op1)) 2792 if (Instruction *NI = FoldGEPICmp(GEP, Op0, 2793 ICmpInst::getSwappedPredicate(I.getPredicate()), I)) 2794 return NI; 2795 2796 // Test to see if the operands of the icmp are casted versions of other 2797 // values. If the ptr->ptr cast can be stripped off both arguments, we do so 2798 // now. 2799 if (BitCastInst *CI = dyn_cast<BitCastInst>(Op0)) { 2800 if (Op0->getType()->isPointerTy() && 2801 (isa<Constant>(Op1) || isa<BitCastInst>(Op1))) { 2802 // We keep moving the cast from the left operand over to the right 2803 // operand, where it can often be eliminated completely. 2804 Op0 = CI->getOperand(0); 2805 2806 // If operand #1 is a bitcast instruction, it must also be a ptr->ptr cast 2807 // so eliminate it as well. 2808 if (BitCastInst *CI2 = dyn_cast<BitCastInst>(Op1)) 2809 Op1 = CI2->getOperand(0); 2810 2811 // If Op1 is a constant, we can fold the cast into the constant. 2812 if (Op0->getType() != Op1->getType()) { 2813 if (Constant *Op1C = dyn_cast<Constant>(Op1)) { 2814 Op1 = ConstantExpr::getBitCast(Op1C, Op0->getType()); 2815 } else { 2816 // Otherwise, cast the RHS right before the icmp 2817 Op1 = Builder->CreateBitCast(Op1, Op0->getType()); 2818 } 2819 } 2820 return new ICmpInst(I.getPredicate(), Op0, Op1); 2821 } 2822 } 2823 2824 if (isa<CastInst>(Op0)) { 2825 // Handle the special case of: icmp (cast bool to X), <cst> 2826 // This comes up when you have code like 2827 // int X = A < B; 2828 // if (X) ... 2829 // For generality, we handle any zero-extension of any operand comparison 2830 // with a constant or another cast from the same type. 2831 if (isa<Constant>(Op1) || isa<CastInst>(Op1)) 2832 if (Instruction *R = visitICmpInstWithCastAndCast(I)) 2833 return R; 2834 } 2835 2836 // Special logic for binary operators. 2837 BinaryOperator *BO0 = dyn_cast<BinaryOperator>(Op0); 2838 BinaryOperator *BO1 = dyn_cast<BinaryOperator>(Op1); 2839 if (BO0 || BO1) { 2840 CmpInst::Predicate Pred = I.getPredicate(); 2841 bool NoOp0WrapProblem = false, NoOp1WrapProblem = false; 2842 if (BO0 && isa<OverflowingBinaryOperator>(BO0)) 2843 NoOp0WrapProblem = ICmpInst::isEquality(Pred) || 2844 (CmpInst::isUnsigned(Pred) && BO0->hasNoUnsignedWrap()) || 2845 (CmpInst::isSigned(Pred) && BO0->hasNoSignedWrap()); 2846 if (BO1 && isa<OverflowingBinaryOperator>(BO1)) 2847 NoOp1WrapProblem = ICmpInst::isEquality(Pred) || 2848 (CmpInst::isUnsigned(Pred) && BO1->hasNoUnsignedWrap()) || 2849 (CmpInst::isSigned(Pred) && BO1->hasNoSignedWrap()); 2850 2851 // Analyze the case when either Op0 or Op1 is an add instruction. 2852 // Op0 = A + B (or A and B are null); Op1 = C + D (or C and D are null). 2853 Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr; 2854 if (BO0 && BO0->getOpcode() == Instruction::Add) 2855 A = BO0->getOperand(0), B = BO0->getOperand(1); 2856 if (BO1 && BO1->getOpcode() == Instruction::Add) 2857 C = BO1->getOperand(0), D = BO1->getOperand(1); 2858 2859 // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow. 2860 if ((A == Op1 || B == Op1) && NoOp0WrapProblem) 2861 return new ICmpInst(Pred, A == Op1 ? B : A, 2862 Constant::getNullValue(Op1->getType())); 2863 2864 // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow. 2865 if ((C == Op0 || D == Op0) && NoOp1WrapProblem) 2866 return new ICmpInst(Pred, Constant::getNullValue(Op0->getType()), 2867 C == Op0 ? D : C); 2868 2869 // icmp (X+Y), (X+Z) -> icmp Y, Z for equalities or if there is no overflow. 2870 if (A && C && (A == C || A == D || B == C || B == D) && 2871 NoOp0WrapProblem && NoOp1WrapProblem && 2872 // Try not to increase register pressure. 2873 BO0->hasOneUse() && BO1->hasOneUse()) { 2874 // Determine Y and Z in the form icmp (X+Y), (X+Z). 2875 Value *Y, *Z; 2876 if (A == C) { 2877 // C + B == C + D -> B == D 2878 Y = B; 2879 Z = D; 2880 } else if (A == D) { 2881 // D + B == C + D -> B == C 2882 Y = B; 2883 Z = C; 2884 } else if (B == C) { 2885 // A + C == C + D -> A == D 2886 Y = A; 2887 Z = D; 2888 } else { 2889 assert(B == D); 2890 // A + D == C + D -> A == C 2891 Y = A; 2892 Z = C; 2893 } 2894 return new ICmpInst(Pred, Y, Z); 2895 } 2896 2897 // icmp slt (X + -1), Y -> icmp sle X, Y 2898 if (A && NoOp0WrapProblem && Pred == CmpInst::ICMP_SLT && 2899 match(B, m_AllOnes())) 2900 return new ICmpInst(CmpInst::ICMP_SLE, A, Op1); 2901 2902 // icmp sge (X + -1), Y -> icmp sgt X, Y 2903 if (A && NoOp0WrapProblem && Pred == CmpInst::ICMP_SGE && 2904 match(B, m_AllOnes())) 2905 return new ICmpInst(CmpInst::ICMP_SGT, A, Op1); 2906 2907 // icmp sle (X + 1), Y -> icmp slt X, Y 2908 if (A && NoOp0WrapProblem && Pred == CmpInst::ICMP_SLE && 2909 match(B, m_One())) 2910 return new ICmpInst(CmpInst::ICMP_SLT, A, Op1); 2911 2912 // icmp sgt (X + 1), Y -> icmp sge X, Y 2913 if (A && NoOp0WrapProblem && Pred == CmpInst::ICMP_SGT && 2914 match(B, m_One())) 2915 return new ICmpInst(CmpInst::ICMP_SGE, A, Op1); 2916 2917 // if C1 has greater magnitude than C2: 2918 // icmp (X + C1), (Y + C2) -> icmp (X + C3), Y 2919 // s.t. C3 = C1 - C2 2920 // 2921 // if C2 has greater magnitude than C1: 2922 // icmp (X + C1), (Y + C2) -> icmp X, (Y + C3) 2923 // s.t. C3 = C2 - C1 2924 if (A && C && NoOp0WrapProblem && NoOp1WrapProblem && 2925 (BO0->hasOneUse() || BO1->hasOneUse()) && !I.isUnsigned()) 2926 if (ConstantInt *C1 = dyn_cast<ConstantInt>(B)) 2927 if (ConstantInt *C2 = dyn_cast<ConstantInt>(D)) { 2928 const APInt &AP1 = C1->getValue(); 2929 const APInt &AP2 = C2->getValue(); 2930 if (AP1.isNegative() == AP2.isNegative()) { 2931 APInt AP1Abs = C1->getValue().abs(); 2932 APInt AP2Abs = C2->getValue().abs(); 2933 if (AP1Abs.uge(AP2Abs)) { 2934 ConstantInt *C3 = Builder->getInt(AP1 - AP2); 2935 Value *NewAdd = Builder->CreateNSWAdd(A, C3); 2936 return new ICmpInst(Pred, NewAdd, C); 2937 } else { 2938 ConstantInt *C3 = Builder->getInt(AP2 - AP1); 2939 Value *NewAdd = Builder->CreateNSWAdd(C, C3); 2940 return new ICmpInst(Pred, A, NewAdd); 2941 } 2942 } 2943 } 2944 2945 2946 // Analyze the case when either Op0 or Op1 is a sub instruction. 2947 // Op0 = A - B (or A and B are null); Op1 = C - D (or C and D are null). 2948 A = nullptr; B = nullptr; C = nullptr; D = nullptr; 2949 if (BO0 && BO0->getOpcode() == Instruction::Sub) 2950 A = BO0->getOperand(0), B = BO0->getOperand(1); 2951 if (BO1 && BO1->getOpcode() == Instruction::Sub) 2952 C = BO1->getOperand(0), D = BO1->getOperand(1); 2953 2954 // icmp (X-Y), X -> icmp 0, Y for equalities or if there is no overflow. 2955 if (A == Op1 && NoOp0WrapProblem) 2956 return new ICmpInst(Pred, Constant::getNullValue(Op1->getType()), B); 2957 2958 // icmp X, (X-Y) -> icmp Y, 0 for equalities or if there is no overflow. 2959 if (C == Op0 && NoOp1WrapProblem) 2960 return new ICmpInst(Pred, D, Constant::getNullValue(Op0->getType())); 2961 2962 // icmp (Y-X), (Z-X) -> icmp Y, Z for equalities or if there is no overflow. 2963 if (B && D && B == D && NoOp0WrapProblem && NoOp1WrapProblem && 2964 // Try not to increase register pressure. 2965 BO0->hasOneUse() && BO1->hasOneUse()) 2966 return new ICmpInst(Pred, A, C); 2967 2968 // icmp (X-Y), (X-Z) -> icmp Z, Y for equalities or if there is no overflow. 2969 if (A && C && A == C && NoOp0WrapProblem && NoOp1WrapProblem && 2970 // Try not to increase register pressure. 2971 BO0->hasOneUse() && BO1->hasOneUse()) 2972 return new ICmpInst(Pred, D, B); 2973 2974 // icmp (0-X) < cst --> x > -cst 2975 if (NoOp0WrapProblem && ICmpInst::isSigned(Pred)) { 2976 Value *X; 2977 if (match(BO0, m_Neg(m_Value(X)))) 2978 if (ConstantInt *RHSC = dyn_cast<ConstantInt>(Op1)) 2979 if (!RHSC->isMinValue(/*isSigned=*/true)) 2980 return new ICmpInst(I.getSwappedPredicate(), X, 2981 ConstantExpr::getNeg(RHSC)); 2982 } 2983 2984 BinaryOperator *SRem = nullptr; 2985 // icmp (srem X, Y), Y 2986 if (BO0 && BO0->getOpcode() == Instruction::SRem && 2987 Op1 == BO0->getOperand(1)) 2988 SRem = BO0; 2989 // icmp Y, (srem X, Y) 2990 else if (BO1 && BO1->getOpcode() == Instruction::SRem && 2991 Op0 == BO1->getOperand(1)) 2992 SRem = BO1; 2993 if (SRem) { 2994 // We don't check hasOneUse to avoid increasing register pressure because 2995 // the value we use is the same value this instruction was already using. 2996 switch (SRem == BO0 ? ICmpInst::getSwappedPredicate(Pred) : Pred) { 2997 default: break; 2998 case ICmpInst::ICMP_EQ: 2999 return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType())); 3000 case ICmpInst::ICMP_NE: 3001 return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType())); 3002 case ICmpInst::ICMP_SGT: 3003 case ICmpInst::ICMP_SGE: 3004 return new ICmpInst(ICmpInst::ICMP_SGT, SRem->getOperand(1), 3005 Constant::getAllOnesValue(SRem->getType())); 3006 case ICmpInst::ICMP_SLT: 3007 case ICmpInst::ICMP_SLE: 3008 return new ICmpInst(ICmpInst::ICMP_SLT, SRem->getOperand(1), 3009 Constant::getNullValue(SRem->getType())); 3010 } 3011 } 3012 3013 if (BO0 && BO1 && BO0->getOpcode() == BO1->getOpcode() && 3014 BO0->hasOneUse() && BO1->hasOneUse() && 3015 BO0->getOperand(1) == BO1->getOperand(1)) { 3016 switch (BO0->getOpcode()) { 3017 default: break; 3018 case Instruction::Add: 3019 case Instruction::Sub: 3020 case Instruction::Xor: 3021 if (I.isEquality()) // a+x icmp eq/ne b+x --> a icmp b 3022 return new ICmpInst(I.getPredicate(), BO0->getOperand(0), 3023 BO1->getOperand(0)); 3024 // icmp u/s (a ^ signbit), (b ^ signbit) --> icmp s/u a, b 3025 if (ConstantInt *CI = dyn_cast<ConstantInt>(BO0->getOperand(1))) { 3026 if (CI->getValue().isSignBit()) { 3027 ICmpInst::Predicate Pred = I.isSigned() 3028 ? I.getUnsignedPredicate() 3029 : I.getSignedPredicate(); 3030 return new ICmpInst(Pred, BO0->getOperand(0), 3031 BO1->getOperand(0)); 3032 } 3033 3034 if (CI->isMaxValue(true)) { 3035 ICmpInst::Predicate Pred = I.isSigned() 3036 ? I.getUnsignedPredicate() 3037 : I.getSignedPredicate(); 3038 Pred = I.getSwappedPredicate(Pred); 3039 return new ICmpInst(Pred, BO0->getOperand(0), 3040 BO1->getOperand(0)); 3041 } 3042 } 3043 break; 3044 case Instruction::Mul: 3045 if (!I.isEquality()) 3046 break; 3047 3048 if (ConstantInt *CI = dyn_cast<ConstantInt>(BO0->getOperand(1))) { 3049 // a * Cst icmp eq/ne b * Cst --> a & Mask icmp b & Mask 3050 // Mask = -1 >> count-trailing-zeros(Cst). 3051 if (!CI->isZero() && !CI->isOne()) { 3052 const APInt &AP = CI->getValue(); 3053 ConstantInt *Mask = ConstantInt::get(I.getContext(), 3054 APInt::getLowBitsSet(AP.getBitWidth(), 3055 AP.getBitWidth() - 3056 AP.countTrailingZeros())); 3057 Value *And1 = Builder->CreateAnd(BO0->getOperand(0), Mask); 3058 Value *And2 = Builder->CreateAnd(BO1->getOperand(0), Mask); 3059 return new ICmpInst(I.getPredicate(), And1, And2); 3060 } 3061 } 3062 break; 3063 case Instruction::UDiv: 3064 case Instruction::LShr: 3065 if (I.isSigned()) 3066 break; 3067 // fall-through 3068 case Instruction::SDiv: 3069 case Instruction::AShr: 3070 if (!BO0->isExact() || !BO1->isExact()) 3071 break; 3072 return new ICmpInst(I.getPredicate(), BO0->getOperand(0), 3073 BO1->getOperand(0)); 3074 case Instruction::Shl: { 3075 bool NUW = BO0->hasNoUnsignedWrap() && BO1->hasNoUnsignedWrap(); 3076 bool NSW = BO0->hasNoSignedWrap() && BO1->hasNoSignedWrap(); 3077 if (!NUW && !NSW) 3078 break; 3079 if (!NSW && I.isSigned()) 3080 break; 3081 return new ICmpInst(I.getPredicate(), BO0->getOperand(0), 3082 BO1->getOperand(0)); 3083 } 3084 } 3085 } 3086 } 3087 3088 { Value *A, *B; 3089 // Transform (A & ~B) == 0 --> (A & B) != 0 3090 // and (A & ~B) != 0 --> (A & B) == 0 3091 // if A is a power of 2. 3092 if (match(Op0, m_And(m_Value(A), m_Not(m_Value(B)))) && 3093 match(Op1, m_Zero()) && isKnownToBeAPowerOfTwo(A) && I.isEquality()) 3094 return new ICmpInst(I.getInversePredicate(), 3095 Builder->CreateAnd(A, B), 3096 Op1); 3097 3098 // ~x < ~y --> y < x 3099 // ~x < cst --> ~cst < x 3100 if (match(Op0, m_Not(m_Value(A)))) { 3101 if (match(Op1, m_Not(m_Value(B)))) 3102 return new ICmpInst(I.getPredicate(), B, A); 3103 if (ConstantInt *RHSC = dyn_cast<ConstantInt>(Op1)) 3104 return new ICmpInst(I.getPredicate(), ConstantExpr::getNot(RHSC), A); 3105 } 3106 3107 // (a+b) <u a --> llvm.uadd.with.overflow. 3108 // (a+b) <u b --> llvm.uadd.with.overflow. 3109 if (I.getPredicate() == ICmpInst::ICMP_ULT && 3110 match(Op0, m_Add(m_Value(A), m_Value(B))) && 3111 (Op1 == A || Op1 == B)) 3112 if (Instruction *R = ProcessUAddIdiom(I, Op0, *this)) 3113 return R; 3114 3115 // a >u (a+b) --> llvm.uadd.with.overflow. 3116 // b >u (a+b) --> llvm.uadd.with.overflow. 3117 if (I.getPredicate() == ICmpInst::ICMP_UGT && 3118 match(Op1, m_Add(m_Value(A), m_Value(B))) && 3119 (Op0 == A || Op0 == B)) 3120 if (Instruction *R = ProcessUAddIdiom(I, Op1, *this)) 3121 return R; 3122 3123 // (zext a) * (zext b) --> llvm.umul.with.overflow. 3124 if (match(Op0, m_Mul(m_ZExt(m_Value(A)), m_ZExt(m_Value(B))))) { 3125 if (Instruction *R = ProcessUMulZExtIdiom(I, Op0, Op1, *this)) 3126 return R; 3127 } 3128 if (match(Op1, m_Mul(m_ZExt(m_Value(A)), m_ZExt(m_Value(B))))) { 3129 if (Instruction *R = ProcessUMulZExtIdiom(I, Op1, Op0, *this)) 3130 return R; 3131 } 3132 } 3133 3134 if (I.isEquality()) { 3135 Value *A, *B, *C, *D; 3136 3137 if (match(Op0, m_Xor(m_Value(A), m_Value(B)))) { 3138 if (A == Op1 || B == Op1) { // (A^B) == A -> B == 0 3139 Value *OtherVal = A == Op1 ? B : A; 3140 return new ICmpInst(I.getPredicate(), OtherVal, 3141 Constant::getNullValue(A->getType())); 3142 } 3143 3144 if (match(Op1, m_Xor(m_Value(C), m_Value(D)))) { 3145 // A^c1 == C^c2 --> A == C^(c1^c2) 3146 ConstantInt *C1, *C2; 3147 if (match(B, m_ConstantInt(C1)) && 3148 match(D, m_ConstantInt(C2)) && Op1->hasOneUse()) { 3149 Constant *NC = Builder->getInt(C1->getValue() ^ C2->getValue()); 3150 Value *Xor = Builder->CreateXor(C, NC); 3151 return new ICmpInst(I.getPredicate(), A, Xor); 3152 } 3153 3154 // A^B == A^D -> B == D 3155 if (A == C) return new ICmpInst(I.getPredicate(), B, D); 3156 if (A == D) return new ICmpInst(I.getPredicate(), B, C); 3157 if (B == C) return new ICmpInst(I.getPredicate(), A, D); 3158 if (B == D) return new ICmpInst(I.getPredicate(), A, C); 3159 } 3160 } 3161 3162 if (match(Op1, m_Xor(m_Value(A), m_Value(B))) && 3163 (A == Op0 || B == Op0)) { 3164 // A == (A^B) -> B == 0 3165 Value *OtherVal = A == Op0 ? B : A; 3166 return new ICmpInst(I.getPredicate(), OtherVal, 3167 Constant::getNullValue(A->getType())); 3168 } 3169 3170 // (X&Z) == (Y&Z) -> (X^Y) & Z == 0 3171 if (match(Op0, m_OneUse(m_And(m_Value(A), m_Value(B)))) && 3172 match(Op1, m_OneUse(m_And(m_Value(C), m_Value(D))))) { 3173 Value *X = nullptr, *Y = nullptr, *Z = nullptr; 3174 3175 if (A == C) { 3176 X = B; Y = D; Z = A; 3177 } else if (A == D) { 3178 X = B; Y = C; Z = A; 3179 } else if (B == C) { 3180 X = A; Y = D; Z = B; 3181 } else if (B == D) { 3182 X = A; Y = C; Z = B; 3183 } 3184 3185 if (X) { // Build (X^Y) & Z 3186 Op1 = Builder->CreateXor(X, Y); 3187 Op1 = Builder->CreateAnd(Op1, Z); 3188 I.setOperand(0, Op1); 3189 I.setOperand(1, Constant::getNullValue(Op1->getType())); 3190 return &I; 3191 } 3192 } 3193 3194 // Transform (zext A) == (B & (1<<X)-1) --> A == (trunc B) 3195 // and (B & (1<<X)-1) == (zext A) --> A == (trunc B) 3196 ConstantInt *Cst1; 3197 if ((Op0->hasOneUse() && 3198 match(Op0, m_ZExt(m_Value(A))) && 3199 match(Op1, m_And(m_Value(B), m_ConstantInt(Cst1)))) || 3200 (Op1->hasOneUse() && 3201 match(Op0, m_And(m_Value(B), m_ConstantInt(Cst1))) && 3202 match(Op1, m_ZExt(m_Value(A))))) { 3203 APInt Pow2 = Cst1->getValue() + 1; 3204 if (Pow2.isPowerOf2() && isa<IntegerType>(A->getType()) && 3205 Pow2.logBase2() == cast<IntegerType>(A->getType())->getBitWidth()) 3206 return new ICmpInst(I.getPredicate(), A, 3207 Builder->CreateTrunc(B, A->getType())); 3208 } 3209 3210 // (A >> C) == (B >> C) --> (A^B) u< (1 << C) 3211 // For lshr and ashr pairs. 3212 if ((match(Op0, m_OneUse(m_LShr(m_Value(A), m_ConstantInt(Cst1)))) && 3213 match(Op1, m_OneUse(m_LShr(m_Value(B), m_Specific(Cst1))))) || 3214 (match(Op0, m_OneUse(m_AShr(m_Value(A), m_ConstantInt(Cst1)))) && 3215 match(Op1, m_OneUse(m_AShr(m_Value(B), m_Specific(Cst1)))))) { 3216 unsigned TypeBits = Cst1->getBitWidth(); 3217 unsigned ShAmt = (unsigned)Cst1->getLimitedValue(TypeBits); 3218 if (ShAmt < TypeBits && ShAmt != 0) { 3219 ICmpInst::Predicate Pred = I.getPredicate() == ICmpInst::ICMP_NE 3220 ? ICmpInst::ICMP_UGE 3221 : ICmpInst::ICMP_ULT; 3222 Value *Xor = Builder->CreateXor(A, B, I.getName() + ".unshifted"); 3223 APInt CmpVal = APInt::getOneBitSet(TypeBits, ShAmt); 3224 return new ICmpInst(Pred, Xor, Builder->getInt(CmpVal)); 3225 } 3226 } 3227 3228 // Transform "icmp eq (trunc (lshr(X, cst1)), cst" to 3229 // "icmp (and X, mask), cst" 3230 uint64_t ShAmt = 0; 3231 if (Op0->hasOneUse() && 3232 match(Op0, m_Trunc(m_OneUse(m_LShr(m_Value(A), 3233 m_ConstantInt(ShAmt))))) && 3234 match(Op1, m_ConstantInt(Cst1)) && 3235 // Only do this when A has multiple uses. This is most important to do 3236 // when it exposes other optimizations. 3237 !A->hasOneUse()) { 3238 unsigned ASize =cast<IntegerType>(A->getType())->getPrimitiveSizeInBits(); 3239 3240 if (ShAmt < ASize) { 3241 APInt MaskV = 3242 APInt::getLowBitsSet(ASize, Op0->getType()->getPrimitiveSizeInBits()); 3243 MaskV <<= ShAmt; 3244 3245 APInt CmpV = Cst1->getValue().zext(ASize); 3246 CmpV <<= ShAmt; 3247 3248 Value *Mask = Builder->CreateAnd(A, Builder->getInt(MaskV)); 3249 return new ICmpInst(I.getPredicate(), Mask, Builder->getInt(CmpV)); 3250 } 3251 } 3252 } 3253 3254 { 3255 Value *X; ConstantInt *Cst; 3256 // icmp X+Cst, X 3257 if (match(Op0, m_Add(m_Value(X), m_ConstantInt(Cst))) && Op1 == X) 3258 return FoldICmpAddOpCst(I, X, Cst, I.getPredicate()); 3259 3260 // icmp X, X+Cst 3261 if (match(Op1, m_Add(m_Value(X), m_ConstantInt(Cst))) && Op0 == X) 3262 return FoldICmpAddOpCst(I, X, Cst, I.getSwappedPredicate()); 3263 } 3264 return Changed ? &I : nullptr; 3265} 3266 3267/// FoldFCmp_IntToFP_Cst - Fold fcmp ([us]itofp x, cst) if possible. 3268/// 3269Instruction *InstCombiner::FoldFCmp_IntToFP_Cst(FCmpInst &I, 3270 Instruction *LHSI, 3271 Constant *RHSC) { 3272 if (!isa<ConstantFP>(RHSC)) return nullptr; 3273 const APFloat &RHS = cast<ConstantFP>(RHSC)->getValueAPF(); 3274 3275 // Get the width of the mantissa. We don't want to hack on conversions that 3276 // might lose information from the integer, e.g. "i64 -> float" 3277 int MantissaWidth = LHSI->getType()->getFPMantissaWidth(); 3278 if (MantissaWidth == -1) return nullptr; // Unknown. 3279 3280 // Check to see that the input is converted from an integer type that is small 3281 // enough that preserves all bits. TODO: check here for "known" sign bits. 3282 // This would allow us to handle (fptosi (x >>s 62) to float) if x is i64 f.e. 3283 unsigned InputSize = LHSI->getOperand(0)->getType()->getScalarSizeInBits(); 3284 3285 // If this is a uitofp instruction, we need an extra bit to hold the sign. 3286 bool LHSUnsigned = isa<UIToFPInst>(LHSI); 3287 if (LHSUnsigned) 3288 ++InputSize; 3289 3290 // If the conversion would lose info, don't hack on this. 3291 if ((int)InputSize > MantissaWidth) 3292 return nullptr; 3293 3294 // Otherwise, we can potentially simplify the comparison. We know that it 3295 // will always come through as an integer value and we know the constant is 3296 // not a NAN (it would have been previously simplified). 3297 assert(!RHS.isNaN() && "NaN comparison not already folded!"); 3298 3299 ICmpInst::Predicate Pred; 3300 switch (I.getPredicate()) { 3301 default: llvm_unreachable("Unexpected predicate!"); 3302 case FCmpInst::FCMP_UEQ: 3303 case FCmpInst::FCMP_OEQ: 3304 Pred = ICmpInst::ICMP_EQ; 3305 break; 3306 case FCmpInst::FCMP_UGT: 3307 case FCmpInst::FCMP_OGT: 3308 Pred = LHSUnsigned ? ICmpInst::ICMP_UGT : ICmpInst::ICMP_SGT; 3309 break; 3310 case FCmpInst::FCMP_UGE: 3311 case FCmpInst::FCMP_OGE: 3312 Pred = LHSUnsigned ? ICmpInst::ICMP_UGE : ICmpInst::ICMP_SGE; 3313 break; 3314 case FCmpInst::FCMP_ULT: 3315 case FCmpInst::FCMP_OLT: 3316 Pred = LHSUnsigned ? ICmpInst::ICMP_ULT : ICmpInst::ICMP_SLT; 3317 break; 3318 case FCmpInst::FCMP_ULE: 3319 case FCmpInst::FCMP_OLE: 3320 Pred = LHSUnsigned ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_SLE; 3321 break; 3322 case FCmpInst::FCMP_UNE: 3323 case FCmpInst::FCMP_ONE: 3324 Pred = ICmpInst::ICMP_NE; 3325 break; 3326 case FCmpInst::FCMP_ORD: 3327 return ReplaceInstUsesWith(I, Builder->getTrue()); 3328 case FCmpInst::FCMP_UNO: 3329 return ReplaceInstUsesWith(I, Builder->getFalse()); 3330 } 3331 3332 IntegerType *IntTy = cast<IntegerType>(LHSI->getOperand(0)->getType()); 3333 3334 // Now we know that the APFloat is a normal number, zero or inf. 3335 3336 // See if the FP constant is too large for the integer. For example, 3337 // comparing an i8 to 300.0. 3338 unsigned IntWidth = IntTy->getScalarSizeInBits(); 3339 3340 if (!LHSUnsigned) { 3341 // If the RHS value is > SignedMax, fold the comparison. This handles +INF 3342 // and large values. 3343 APFloat SMax(RHS.getSemantics()); 3344 SMax.convertFromAPInt(APInt::getSignedMaxValue(IntWidth), true, 3345 APFloat::rmNearestTiesToEven); 3346 if (SMax.compare(RHS) == APFloat::cmpLessThan) { // smax < 13123.0 3347 if (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_SLT || 3348 Pred == ICmpInst::ICMP_SLE) 3349 return ReplaceInstUsesWith(I, Builder->getTrue()); 3350 return ReplaceInstUsesWith(I, Builder->getFalse()); 3351 } 3352 } else { 3353 // If the RHS value is > UnsignedMax, fold the comparison. This handles 3354 // +INF and large values. 3355 APFloat UMax(RHS.getSemantics()); 3356 UMax.convertFromAPInt(APInt::getMaxValue(IntWidth), false, 3357 APFloat::rmNearestTiesToEven); 3358 if (UMax.compare(RHS) == APFloat::cmpLessThan) { // umax < 13123.0 3359 if (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_ULT || 3360 Pred == ICmpInst::ICMP_ULE) 3361 return ReplaceInstUsesWith(I, Builder->getTrue()); 3362 return ReplaceInstUsesWith(I, Builder->getFalse()); 3363 } 3364 } 3365 3366 if (!LHSUnsigned) { 3367 // See if the RHS value is < SignedMin. 3368 APFloat SMin(RHS.getSemantics()); 3369 SMin.convertFromAPInt(APInt::getSignedMinValue(IntWidth), true, 3370 APFloat::rmNearestTiesToEven); 3371 if (SMin.compare(RHS) == APFloat::cmpGreaterThan) { // smin > 12312.0 3372 if (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_SGT || 3373 Pred == ICmpInst::ICMP_SGE) 3374 return ReplaceInstUsesWith(I, Builder->getTrue()); 3375 return ReplaceInstUsesWith(I, Builder->getFalse()); 3376 } 3377 } else { 3378 // See if the RHS value is < UnsignedMin. 3379 APFloat SMin(RHS.getSemantics()); 3380 SMin.convertFromAPInt(APInt::getMinValue(IntWidth), true, 3381 APFloat::rmNearestTiesToEven); 3382 if (SMin.compare(RHS) == APFloat::cmpGreaterThan) { // umin > 12312.0 3383 if (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_UGT || 3384 Pred == ICmpInst::ICMP_UGE) 3385 return ReplaceInstUsesWith(I, Builder->getTrue()); 3386 return ReplaceInstUsesWith(I, Builder->getFalse()); 3387 } 3388 } 3389 3390 // Okay, now we know that the FP constant fits in the range [SMIN, SMAX] or 3391 // [0, UMAX], but it may still be fractional. See if it is fractional by 3392 // casting the FP value to the integer value and back, checking for equality. 3393 // Don't do this for zero, because -0.0 is not fractional. 3394 Constant *RHSInt = LHSUnsigned 3395 ? ConstantExpr::getFPToUI(RHSC, IntTy) 3396 : ConstantExpr::getFPToSI(RHSC, IntTy); 3397 if (!RHS.isZero()) { 3398 bool Equal = LHSUnsigned 3399 ? ConstantExpr::getUIToFP(RHSInt, RHSC->getType()) == RHSC 3400 : ConstantExpr::getSIToFP(RHSInt, RHSC->getType()) == RHSC; 3401 if (!Equal) { 3402 // If we had a comparison against a fractional value, we have to adjust 3403 // the compare predicate and sometimes the value. RHSC is rounded towards 3404 // zero at this point. 3405 switch (Pred) { 3406 default: llvm_unreachable("Unexpected integer comparison!"); 3407 case ICmpInst::ICMP_NE: // (float)int != 4.4 --> true 3408 return ReplaceInstUsesWith(I, Builder->getTrue()); 3409 case ICmpInst::ICMP_EQ: // (float)int == 4.4 --> false 3410 return ReplaceInstUsesWith(I, Builder->getFalse()); 3411 case ICmpInst::ICMP_ULE: 3412 // (float)int <= 4.4 --> int <= 4 3413 // (float)int <= -4.4 --> false 3414 if (RHS.isNegative()) 3415 return ReplaceInstUsesWith(I, Builder->getFalse()); 3416 break; 3417 case ICmpInst::ICMP_SLE: 3418 // (float)int <= 4.4 --> int <= 4 3419 // (float)int <= -4.4 --> int < -4 3420 if (RHS.isNegative()) 3421 Pred = ICmpInst::ICMP_SLT; 3422 break; 3423 case ICmpInst::ICMP_ULT: 3424 // (float)int < -4.4 --> false 3425 // (float)int < 4.4 --> int <= 4 3426 if (RHS.isNegative()) 3427 return ReplaceInstUsesWith(I, Builder->getFalse()); 3428 Pred = ICmpInst::ICMP_ULE; 3429 break; 3430 case ICmpInst::ICMP_SLT: 3431 // (float)int < -4.4 --> int < -4 3432 // (float)int < 4.4 --> int <= 4 3433 if (!RHS.isNegative()) 3434 Pred = ICmpInst::ICMP_SLE; 3435 break; 3436 case ICmpInst::ICMP_UGT: 3437 // (float)int > 4.4 --> int > 4 3438 // (float)int > -4.4 --> true 3439 if (RHS.isNegative()) 3440 return ReplaceInstUsesWith(I, Builder->getTrue()); 3441 break; 3442 case ICmpInst::ICMP_SGT: 3443 // (float)int > 4.4 --> int > 4 3444 // (float)int > -4.4 --> int >= -4 3445 if (RHS.isNegative()) 3446 Pred = ICmpInst::ICMP_SGE; 3447 break; 3448 case ICmpInst::ICMP_UGE: 3449 // (float)int >= -4.4 --> true 3450 // (float)int >= 4.4 --> int > 4 3451 if (RHS.isNegative()) 3452 return ReplaceInstUsesWith(I, Builder->getTrue()); 3453 Pred = ICmpInst::ICMP_UGT; 3454 break; 3455 case ICmpInst::ICMP_SGE: 3456 // (float)int >= -4.4 --> int >= -4 3457 // (float)int >= 4.4 --> int > 4 3458 if (!RHS.isNegative()) 3459 Pred = ICmpInst::ICMP_SGT; 3460 break; 3461 } 3462 } 3463 } 3464 3465 // Lower this FP comparison into an appropriate integer version of the 3466 // comparison. 3467 return new ICmpInst(Pred, LHSI->getOperand(0), RHSInt); 3468} 3469 3470Instruction *InstCombiner::visitFCmpInst(FCmpInst &I) { 3471 bool Changed = false; 3472 3473 /// Orders the operands of the compare so that they are listed from most 3474 /// complex to least complex. This puts constants before unary operators, 3475 /// before binary operators. 3476 if (getComplexity(I.getOperand(0)) < getComplexity(I.getOperand(1))) { 3477 I.swapOperands(); 3478 Changed = true; 3479 } 3480 3481 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 3482 3483 if (Value *V = SimplifyFCmpInst(I.getPredicate(), Op0, Op1, DL)) 3484 return ReplaceInstUsesWith(I, V); 3485 3486 // Simplify 'fcmp pred X, X' 3487 if (Op0 == Op1) { 3488 switch (I.getPredicate()) { 3489 default: llvm_unreachable("Unknown predicate!"); 3490 case FCmpInst::FCMP_UNO: // True if unordered: isnan(X) | isnan(Y) 3491 case FCmpInst::FCMP_ULT: // True if unordered or less than 3492 case FCmpInst::FCMP_UGT: // True if unordered or greater than 3493 case FCmpInst::FCMP_UNE: // True if unordered or not equal 3494 // Canonicalize these to be 'fcmp uno %X, 0.0'. 3495 I.setPredicate(FCmpInst::FCMP_UNO); 3496 I.setOperand(1, Constant::getNullValue(Op0->getType())); 3497 return &I; 3498 3499 case FCmpInst::FCMP_ORD: // True if ordered (no nans) 3500 case FCmpInst::FCMP_OEQ: // True if ordered and equal 3501 case FCmpInst::FCMP_OGE: // True if ordered and greater than or equal 3502 case FCmpInst::FCMP_OLE: // True if ordered and less than or equal 3503 // Canonicalize these to be 'fcmp ord %X, 0.0'. 3504 I.setPredicate(FCmpInst::FCMP_ORD); 3505 I.setOperand(1, Constant::getNullValue(Op0->getType())); 3506 return &I; 3507 } 3508 } 3509 3510 // Handle fcmp with constant RHS 3511 if (Constant *RHSC = dyn_cast<Constant>(Op1)) { 3512 if (Instruction *LHSI = dyn_cast<Instruction>(Op0)) 3513 switch (LHSI->getOpcode()) { 3514 case Instruction::FPExt: { 3515 // fcmp (fpext x), C -> fcmp x, (fptrunc C) if fptrunc is lossless 3516 FPExtInst *LHSExt = cast<FPExtInst>(LHSI); 3517 ConstantFP *RHSF = dyn_cast<ConstantFP>(RHSC); 3518 if (!RHSF) 3519 break; 3520 3521 const fltSemantics *Sem; 3522 // FIXME: This shouldn't be here. 3523 if (LHSExt->getSrcTy()->isHalfTy()) 3524 Sem = &APFloat::IEEEhalf; 3525 else if (LHSExt->getSrcTy()->isFloatTy()) 3526 Sem = &APFloat::IEEEsingle; 3527 else if (LHSExt->getSrcTy()->isDoubleTy()) 3528 Sem = &APFloat::IEEEdouble; 3529 else if (LHSExt->getSrcTy()->isFP128Ty()) 3530 Sem = &APFloat::IEEEquad; 3531 else if (LHSExt->getSrcTy()->isX86_FP80Ty()) 3532 Sem = &APFloat::x87DoubleExtended; 3533 else if (LHSExt->getSrcTy()->isPPC_FP128Ty()) 3534 Sem = &APFloat::PPCDoubleDouble; 3535 else 3536 break; 3537 3538 bool Lossy; 3539 APFloat F = RHSF->getValueAPF(); 3540 F.convert(*Sem, APFloat::rmNearestTiesToEven, &Lossy); 3541 3542 // Avoid lossy conversions and denormals. Zero is a special case 3543 // that's OK to convert. 3544 APFloat Fabs = F; 3545 Fabs.clearSign(); 3546 if (!Lossy && 3547 ((Fabs.compare(APFloat::getSmallestNormalized(*Sem)) != 3548 APFloat::cmpLessThan) || Fabs.isZero())) 3549 3550 return new FCmpInst(I.getPredicate(), LHSExt->getOperand(0), 3551 ConstantFP::get(RHSC->getContext(), F)); 3552 break; 3553 } 3554 case Instruction::PHI: 3555 // Only fold fcmp into the PHI if the phi and fcmp are in the same 3556 // block. If in the same block, we're encouraging jump threading. If 3557 // not, we are just pessimizing the code by making an i1 phi. 3558 if (LHSI->getParent() == I.getParent()) 3559 if (Instruction *NV = FoldOpIntoPhi(I)) 3560 return NV; 3561 break; 3562 case Instruction::SIToFP: 3563 case Instruction::UIToFP: 3564 if (Instruction *NV = FoldFCmp_IntToFP_Cst(I, LHSI, RHSC)) 3565 return NV; 3566 break; 3567 case Instruction::FSub: { 3568 // fcmp pred (fneg x), C -> fcmp swap(pred) x, -C 3569 Value *Op; 3570 if (match(LHSI, m_FNeg(m_Value(Op)))) 3571 return new FCmpInst(I.getSwappedPredicate(), Op, 3572 ConstantExpr::getFNeg(RHSC)); 3573 break; 3574 } 3575 case Instruction::Load: 3576 if (GetElementPtrInst *GEP = 3577 dyn_cast<GetElementPtrInst>(LHSI->getOperand(0))) { 3578 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0))) 3579 if (GV->isConstant() && GV->hasDefinitiveInitializer() && 3580 !cast<LoadInst>(LHSI)->isVolatile()) 3581 if (Instruction *Res = FoldCmpLoadFromIndexedGlobal(GEP, GV, I)) 3582 return Res; 3583 } 3584 break; 3585 case Instruction::Call: { 3586 CallInst *CI = cast<CallInst>(LHSI); 3587 LibFunc::Func Func; 3588 // Various optimization for fabs compared with zero. 3589 if (RHSC->isNullValue() && CI->getCalledFunction() && 3590 TLI->getLibFunc(CI->getCalledFunction()->getName(), Func) && 3591 TLI->has(Func)) { 3592 if (Func == LibFunc::fabs || Func == LibFunc::fabsf || 3593 Func == LibFunc::fabsl) { 3594 switch (I.getPredicate()) { 3595 default: break; 3596 // fabs(x) < 0 --> false 3597 case FCmpInst::FCMP_OLT: 3598 return ReplaceInstUsesWith(I, Builder->getFalse()); 3599 // fabs(x) > 0 --> x != 0 3600 case FCmpInst::FCMP_OGT: 3601 return new FCmpInst(FCmpInst::FCMP_ONE, CI->getArgOperand(0), 3602 RHSC); 3603 // fabs(x) <= 0 --> x == 0 3604 case FCmpInst::FCMP_OLE: 3605 return new FCmpInst(FCmpInst::FCMP_OEQ, CI->getArgOperand(0), 3606 RHSC); 3607 // fabs(x) >= 0 --> !isnan(x) 3608 case FCmpInst::FCMP_OGE: 3609 return new FCmpInst(FCmpInst::FCMP_ORD, CI->getArgOperand(0), 3610 RHSC); 3611 // fabs(x) == 0 --> x == 0 3612 // fabs(x) != 0 --> x != 0 3613 case FCmpInst::FCMP_OEQ: 3614 case FCmpInst::FCMP_UEQ: 3615 case FCmpInst::FCMP_ONE: 3616 case FCmpInst::FCMP_UNE: 3617 return new FCmpInst(I.getPredicate(), CI->getArgOperand(0), 3618 RHSC); 3619 } 3620 } 3621 } 3622 } 3623 } 3624 } 3625 3626 // fcmp pred (fneg x), (fneg y) -> fcmp swap(pred) x, y 3627 Value *X, *Y; 3628 if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_FNeg(m_Value(Y)))) 3629 return new FCmpInst(I.getSwappedPredicate(), X, Y); 3630 3631 // fcmp (fpext x), (fpext y) -> fcmp x, y 3632 if (FPExtInst *LHSExt = dyn_cast<FPExtInst>(Op0)) 3633 if (FPExtInst *RHSExt = dyn_cast<FPExtInst>(Op1)) 3634 if (LHSExt->getSrcTy() == RHSExt->getSrcTy()) 3635 return new FCmpInst(I.getPredicate(), LHSExt->getOperand(0), 3636 RHSExt->getOperand(0)); 3637 3638 return Changed ? &I : nullptr; 3639} 3640