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