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