1 //===- ConstantFold.cpp - LLVM constant folder ----------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements folding of constants for LLVM. This implements the 10 // (internal) ConstantFold.h interface, which is used by the 11 // ConstantExpr::get* methods to automatically fold constants when possible. 12 // 13 // The current constant folding implementation is implemented in two pieces: the 14 // pieces that don't need DataLayout, and the pieces that do. This is to avoid 15 // a dependence in IR on Target. 16 // 17 //===----------------------------------------------------------------------===// 18 19 #include "ConstantFold.h" 20 #include "llvm/ADT/APSInt.h" 21 #include "llvm/ADT/SmallVector.h" 22 #include "llvm/IR/Constants.h" 23 #include "llvm/IR/DerivedTypes.h" 24 #include "llvm/IR/Function.h" 25 #include "llvm/IR/GetElementPtrTypeIterator.h" 26 #include "llvm/IR/GlobalAlias.h" 27 #include "llvm/IR/GlobalVariable.h" 28 #include "llvm/IR/Instructions.h" 29 #include "llvm/IR/Module.h" 30 #include "llvm/IR/Operator.h" 31 #include "llvm/IR/PatternMatch.h" 32 #include "llvm/Support/ErrorHandling.h" 33 #include "llvm/Support/ManagedStatic.h" 34 #include "llvm/Support/MathExtras.h" 35 using namespace llvm; 36 using namespace llvm::PatternMatch; 37 38 //===----------------------------------------------------------------------===// 39 // ConstantFold*Instruction Implementations 40 //===----------------------------------------------------------------------===// 41 42 /// Convert the specified vector Constant node to the specified vector type. 43 /// At this point, we know that the elements of the input vector constant are 44 /// all simple integer or FP values. 45 static Constant *BitCastConstantVector(Constant *CV, VectorType *DstTy) { 46 47 if (CV->isAllOnesValue()) return Constant::getAllOnesValue(DstTy); 48 if (CV->isNullValue()) return Constant::getNullValue(DstTy); 49 50 // Do not iterate on scalable vector. The num of elements is unknown at 51 // compile-time. 52 if (isa<ScalableVectorType>(DstTy)) 53 return nullptr; 54 55 // If this cast changes element count then we can't handle it here: 56 // doing so requires endianness information. This should be handled by 57 // Analysis/ConstantFolding.cpp 58 unsigned NumElts = cast<FixedVectorType>(DstTy)->getNumElements(); 59 if (NumElts != cast<FixedVectorType>(CV->getType())->getNumElements()) 60 return nullptr; 61 62 Type *DstEltTy = DstTy->getElementType(); 63 // Fast path for splatted constants. 64 if (Constant *Splat = CV->getSplatValue()) { 65 return ConstantVector::getSplat(DstTy->getElementCount(), 66 ConstantExpr::getBitCast(Splat, DstEltTy)); 67 } 68 69 SmallVector<Constant*, 16> Result; 70 Type *Ty = IntegerType::get(CV->getContext(), 32); 71 for (unsigned i = 0; i != NumElts; ++i) { 72 Constant *C = 73 ConstantExpr::getExtractElement(CV, ConstantInt::get(Ty, i)); 74 C = ConstantExpr::getBitCast(C, DstEltTy); 75 Result.push_back(C); 76 } 77 78 return ConstantVector::get(Result); 79 } 80 81 /// This function determines which opcode to use to fold two constant cast 82 /// expressions together. It uses CastInst::isEliminableCastPair to determine 83 /// the opcode. Consequently its just a wrapper around that function. 84 /// Determine if it is valid to fold a cast of a cast 85 static unsigned 86 foldConstantCastPair( 87 unsigned opc, ///< opcode of the second cast constant expression 88 ConstantExpr *Op, ///< the first cast constant expression 89 Type *DstTy ///< destination type of the first cast 90 ) { 91 assert(Op && Op->isCast() && "Can't fold cast of cast without a cast!"); 92 assert(DstTy && DstTy->isFirstClassType() && "Invalid cast destination type"); 93 assert(CastInst::isCast(opc) && "Invalid cast opcode"); 94 95 // The types and opcodes for the two Cast constant expressions 96 Type *SrcTy = Op->getOperand(0)->getType(); 97 Type *MidTy = Op->getType(); 98 Instruction::CastOps firstOp = Instruction::CastOps(Op->getOpcode()); 99 Instruction::CastOps secondOp = Instruction::CastOps(opc); 100 101 // Assume that pointers are never more than 64 bits wide, and only use this 102 // for the middle type. Otherwise we could end up folding away illegal 103 // bitcasts between address spaces with different sizes. 104 IntegerType *FakeIntPtrTy = Type::getInt64Ty(DstTy->getContext()); 105 106 // Let CastInst::isEliminableCastPair do the heavy lifting. 107 return CastInst::isEliminableCastPair(firstOp, secondOp, SrcTy, MidTy, DstTy, 108 nullptr, FakeIntPtrTy, nullptr); 109 } 110 111 static Constant *FoldBitCast(Constant *V, Type *DestTy) { 112 Type *SrcTy = V->getType(); 113 if (SrcTy == DestTy) 114 return V; // no-op cast 115 116 // Check to see if we are casting a pointer to an aggregate to a pointer to 117 // the first element. If so, return the appropriate GEP instruction. 118 if (PointerType *PTy = dyn_cast<PointerType>(V->getType())) 119 if (PointerType *DPTy = dyn_cast<PointerType>(DestTy)) 120 if (PTy->getAddressSpace() == DPTy->getAddressSpace() 121 && PTy->getElementType()->isSized()) { 122 SmallVector<Value*, 8> IdxList; 123 Value *Zero = 124 Constant::getNullValue(Type::getInt32Ty(DPTy->getContext())); 125 IdxList.push_back(Zero); 126 Type *ElTy = PTy->getElementType(); 127 while (ElTy && ElTy != DPTy->getElementType()) { 128 ElTy = GetElementPtrInst::getTypeAtIndex(ElTy, (uint64_t)0); 129 IdxList.push_back(Zero); 130 } 131 132 if (ElTy == DPTy->getElementType()) 133 // This GEP is inbounds because all indices are zero. 134 return ConstantExpr::getInBoundsGetElementPtr(PTy->getElementType(), 135 V, IdxList); 136 } 137 138 // Handle casts from one vector constant to another. We know that the src 139 // and dest type have the same size (otherwise its an illegal cast). 140 if (VectorType *DestPTy = dyn_cast<VectorType>(DestTy)) { 141 if (VectorType *SrcTy = dyn_cast<VectorType>(V->getType())) { 142 assert(DestPTy->getPrimitiveSizeInBits() == 143 SrcTy->getPrimitiveSizeInBits() && 144 "Not cast between same sized vectors!"); 145 SrcTy = nullptr; 146 // First, check for null. Undef is already handled. 147 if (isa<ConstantAggregateZero>(V)) 148 return Constant::getNullValue(DestTy); 149 150 // Handle ConstantVector and ConstantAggregateVector. 151 return BitCastConstantVector(V, DestPTy); 152 } 153 154 // Canonicalize scalar-to-vector bitcasts into vector-to-vector bitcasts 155 // This allows for other simplifications (although some of them 156 // can only be handled by Analysis/ConstantFolding.cpp). 157 if (isa<ConstantInt>(V) || isa<ConstantFP>(V)) 158 return ConstantExpr::getBitCast(ConstantVector::get(V), DestPTy); 159 } 160 161 // Finally, implement bitcast folding now. The code below doesn't handle 162 // bitcast right. 163 if (isa<ConstantPointerNull>(V)) // ptr->ptr cast. 164 return ConstantPointerNull::get(cast<PointerType>(DestTy)); 165 166 // Handle integral constant input. 167 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 168 if (DestTy->isIntegerTy()) 169 // Integral -> Integral. This is a no-op because the bit widths must 170 // be the same. Consequently, we just fold to V. 171 return V; 172 173 // See note below regarding the PPC_FP128 restriction. 174 if (DestTy->isFloatingPointTy() && !DestTy->isPPC_FP128Ty()) 175 return ConstantFP::get(DestTy->getContext(), 176 APFloat(DestTy->getFltSemantics(), 177 CI->getValue())); 178 179 // Otherwise, can't fold this (vector?) 180 return nullptr; 181 } 182 183 // Handle ConstantFP input: FP -> Integral. 184 if (ConstantFP *FP = dyn_cast<ConstantFP>(V)) { 185 // PPC_FP128 is really the sum of two consecutive doubles, where the first 186 // double is always stored first in memory, regardless of the target 187 // endianness. The memory layout of i128, however, depends on the target 188 // endianness, and so we can't fold this without target endianness 189 // information. This should instead be handled by 190 // Analysis/ConstantFolding.cpp 191 if (FP->getType()->isPPC_FP128Ty()) 192 return nullptr; 193 194 // Make sure dest type is compatible with the folded integer constant. 195 if (!DestTy->isIntegerTy()) 196 return nullptr; 197 198 return ConstantInt::get(FP->getContext(), 199 FP->getValueAPF().bitcastToAPInt()); 200 } 201 202 return nullptr; 203 } 204 205 206 /// V is an integer constant which only has a subset of its bytes used. 207 /// The bytes used are indicated by ByteStart (which is the first byte used, 208 /// counting from the least significant byte) and ByteSize, which is the number 209 /// of bytes used. 210 /// 211 /// This function analyzes the specified constant to see if the specified byte 212 /// range can be returned as a simplified constant. If so, the constant is 213 /// returned, otherwise null is returned. 214 static Constant *ExtractConstantBytes(Constant *C, unsigned ByteStart, 215 unsigned ByteSize) { 216 assert(C->getType()->isIntegerTy() && 217 (cast<IntegerType>(C->getType())->getBitWidth() & 7) == 0 && 218 "Non-byte sized integer input"); 219 unsigned CSize = cast<IntegerType>(C->getType())->getBitWidth()/8; 220 assert(ByteSize && "Must be accessing some piece"); 221 assert(ByteStart+ByteSize <= CSize && "Extracting invalid piece from input"); 222 assert(ByteSize != CSize && "Should not extract everything"); 223 224 // Constant Integers are simple. 225 if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) { 226 APInt V = CI->getValue(); 227 if (ByteStart) 228 V.lshrInPlace(ByteStart*8); 229 V = V.trunc(ByteSize*8); 230 return ConstantInt::get(CI->getContext(), V); 231 } 232 233 // In the input is a constant expr, we might be able to recursively simplify. 234 // If not, we definitely can't do anything. 235 ConstantExpr *CE = dyn_cast<ConstantExpr>(C); 236 if (!CE) return nullptr; 237 238 switch (CE->getOpcode()) { 239 default: return nullptr; 240 case Instruction::Or: { 241 Constant *RHS = ExtractConstantBytes(CE->getOperand(1), ByteStart,ByteSize); 242 if (!RHS) 243 return nullptr; 244 245 // X | -1 -> -1. 246 if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) 247 if (RHSC->isMinusOne()) 248 return RHSC; 249 250 Constant *LHS = ExtractConstantBytes(CE->getOperand(0), ByteStart,ByteSize); 251 if (!LHS) 252 return nullptr; 253 return ConstantExpr::getOr(LHS, RHS); 254 } 255 case Instruction::And: { 256 Constant *RHS = ExtractConstantBytes(CE->getOperand(1), ByteStart,ByteSize); 257 if (!RHS) 258 return nullptr; 259 260 // X & 0 -> 0. 261 if (RHS->isNullValue()) 262 return RHS; 263 264 Constant *LHS = ExtractConstantBytes(CE->getOperand(0), ByteStart,ByteSize); 265 if (!LHS) 266 return nullptr; 267 return ConstantExpr::getAnd(LHS, RHS); 268 } 269 case Instruction::LShr: { 270 ConstantInt *Amt = dyn_cast<ConstantInt>(CE->getOperand(1)); 271 if (!Amt) 272 return nullptr; 273 APInt ShAmt = Amt->getValue(); 274 // Cannot analyze non-byte shifts. 275 if ((ShAmt & 7) != 0) 276 return nullptr; 277 ShAmt.lshrInPlace(3); 278 279 // If the extract is known to be all zeros, return zero. 280 if (ShAmt.uge(CSize - ByteStart)) 281 return Constant::getNullValue( 282 IntegerType::get(CE->getContext(), ByteSize * 8)); 283 // If the extract is known to be fully in the input, extract it. 284 if (ShAmt.ule(CSize - (ByteStart + ByteSize))) 285 return ExtractConstantBytes(CE->getOperand(0), 286 ByteStart + ShAmt.getZExtValue(), ByteSize); 287 288 // TODO: Handle the 'partially zero' case. 289 return nullptr; 290 } 291 292 case Instruction::Shl: { 293 ConstantInt *Amt = dyn_cast<ConstantInt>(CE->getOperand(1)); 294 if (!Amt) 295 return nullptr; 296 APInt ShAmt = Amt->getValue(); 297 // Cannot analyze non-byte shifts. 298 if ((ShAmt & 7) != 0) 299 return nullptr; 300 ShAmt.lshrInPlace(3); 301 302 // If the extract is known to be all zeros, return zero. 303 if (ShAmt.uge(ByteStart + ByteSize)) 304 return Constant::getNullValue( 305 IntegerType::get(CE->getContext(), ByteSize * 8)); 306 // If the extract is known to be fully in the input, extract it. 307 if (ShAmt.ule(ByteStart)) 308 return ExtractConstantBytes(CE->getOperand(0), 309 ByteStart - ShAmt.getZExtValue(), ByteSize); 310 311 // TODO: Handle the 'partially zero' case. 312 return nullptr; 313 } 314 315 case Instruction::ZExt: { 316 unsigned SrcBitSize = 317 cast<IntegerType>(CE->getOperand(0)->getType())->getBitWidth(); 318 319 // If extracting something that is completely zero, return 0. 320 if (ByteStart*8 >= SrcBitSize) 321 return Constant::getNullValue(IntegerType::get(CE->getContext(), 322 ByteSize*8)); 323 324 // If exactly extracting the input, return it. 325 if (ByteStart == 0 && ByteSize*8 == SrcBitSize) 326 return CE->getOperand(0); 327 328 // If extracting something completely in the input, if the input is a 329 // multiple of 8 bits, recurse. 330 if ((SrcBitSize&7) == 0 && (ByteStart+ByteSize)*8 <= SrcBitSize) 331 return ExtractConstantBytes(CE->getOperand(0), ByteStart, ByteSize); 332 333 // Otherwise, if extracting a subset of the input, which is not multiple of 334 // 8 bits, do a shift and trunc to get the bits. 335 if ((ByteStart+ByteSize)*8 < SrcBitSize) { 336 assert((SrcBitSize&7) && "Shouldn't get byte sized case here"); 337 Constant *Res = CE->getOperand(0); 338 if (ByteStart) 339 Res = ConstantExpr::getLShr(Res, 340 ConstantInt::get(Res->getType(), ByteStart*8)); 341 return ConstantExpr::getTrunc(Res, IntegerType::get(C->getContext(), 342 ByteSize*8)); 343 } 344 345 // TODO: Handle the 'partially zero' case. 346 return nullptr; 347 } 348 } 349 } 350 351 /// Return a ConstantExpr with type DestTy for sizeof on Ty, with any known 352 /// factors factored out. If Folded is false, return null if no factoring was 353 /// possible, to avoid endlessly bouncing an unfoldable expression back into the 354 /// top-level folder. 355 static Constant *getFoldedSizeOf(Type *Ty, Type *DestTy, bool Folded) { 356 if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 357 Constant *N = ConstantInt::get(DestTy, ATy->getNumElements()); 358 Constant *E = getFoldedSizeOf(ATy->getElementType(), DestTy, true); 359 return ConstantExpr::getNUWMul(E, N); 360 } 361 362 if (StructType *STy = dyn_cast<StructType>(Ty)) 363 if (!STy->isPacked()) { 364 unsigned NumElems = STy->getNumElements(); 365 // An empty struct has size zero. 366 if (NumElems == 0) 367 return ConstantExpr::getNullValue(DestTy); 368 // Check for a struct with all members having the same size. 369 Constant *MemberSize = 370 getFoldedSizeOf(STy->getElementType(0), DestTy, true); 371 bool AllSame = true; 372 for (unsigned i = 1; i != NumElems; ++i) 373 if (MemberSize != 374 getFoldedSizeOf(STy->getElementType(i), DestTy, true)) { 375 AllSame = false; 376 break; 377 } 378 if (AllSame) { 379 Constant *N = ConstantInt::get(DestTy, NumElems); 380 return ConstantExpr::getNUWMul(MemberSize, N); 381 } 382 } 383 384 // Pointer size doesn't depend on the pointee type, so canonicalize them 385 // to an arbitrary pointee. 386 if (PointerType *PTy = dyn_cast<PointerType>(Ty)) 387 if (!PTy->getElementType()->isIntegerTy(1)) 388 return 389 getFoldedSizeOf(PointerType::get(IntegerType::get(PTy->getContext(), 1), 390 PTy->getAddressSpace()), 391 DestTy, true); 392 393 // If there's no interesting folding happening, bail so that we don't create 394 // a constant that looks like it needs folding but really doesn't. 395 if (!Folded) 396 return nullptr; 397 398 // Base case: Get a regular sizeof expression. 399 Constant *C = ConstantExpr::getSizeOf(Ty); 400 C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, 401 DestTy, false), 402 C, DestTy); 403 return C; 404 } 405 406 /// Return a ConstantExpr with type DestTy for alignof on Ty, with any known 407 /// factors factored out. If Folded is false, return null if no factoring was 408 /// possible, to avoid endlessly bouncing an unfoldable expression back into the 409 /// top-level folder. 410 static Constant *getFoldedAlignOf(Type *Ty, Type *DestTy, bool Folded) { 411 // The alignment of an array is equal to the alignment of the 412 // array element. Note that this is not always true for vectors. 413 if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 414 Constant *C = ConstantExpr::getAlignOf(ATy->getElementType()); 415 C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, 416 DestTy, 417 false), 418 C, DestTy); 419 return C; 420 } 421 422 if (StructType *STy = dyn_cast<StructType>(Ty)) { 423 // Packed structs always have an alignment of 1. 424 if (STy->isPacked()) 425 return ConstantInt::get(DestTy, 1); 426 427 // Otherwise, struct alignment is the maximum alignment of any member. 428 // Without target data, we can't compare much, but we can check to see 429 // if all the members have the same alignment. 430 unsigned NumElems = STy->getNumElements(); 431 // An empty struct has minimal alignment. 432 if (NumElems == 0) 433 return ConstantInt::get(DestTy, 1); 434 // Check for a struct with all members having the same alignment. 435 Constant *MemberAlign = 436 getFoldedAlignOf(STy->getElementType(0), DestTy, true); 437 bool AllSame = true; 438 for (unsigned i = 1; i != NumElems; ++i) 439 if (MemberAlign != getFoldedAlignOf(STy->getElementType(i), DestTy, true)) { 440 AllSame = false; 441 break; 442 } 443 if (AllSame) 444 return MemberAlign; 445 } 446 447 // Pointer alignment doesn't depend on the pointee type, so canonicalize them 448 // to an arbitrary pointee. 449 if (PointerType *PTy = dyn_cast<PointerType>(Ty)) 450 if (!PTy->getElementType()->isIntegerTy(1)) 451 return 452 getFoldedAlignOf(PointerType::get(IntegerType::get(PTy->getContext(), 453 1), 454 PTy->getAddressSpace()), 455 DestTy, true); 456 457 // If there's no interesting folding happening, bail so that we don't create 458 // a constant that looks like it needs folding but really doesn't. 459 if (!Folded) 460 return nullptr; 461 462 // Base case: Get a regular alignof expression. 463 Constant *C = ConstantExpr::getAlignOf(Ty); 464 C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, 465 DestTy, false), 466 C, DestTy); 467 return C; 468 } 469 470 /// Return a ConstantExpr with type DestTy for offsetof on Ty and FieldNo, with 471 /// any known factors factored out. If Folded is false, return null if no 472 /// factoring was possible, to avoid endlessly bouncing an unfoldable expression 473 /// back into the top-level folder. 474 static Constant *getFoldedOffsetOf(Type *Ty, Constant *FieldNo, Type *DestTy, 475 bool Folded) { 476 if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 477 Constant *N = ConstantExpr::getCast(CastInst::getCastOpcode(FieldNo, false, 478 DestTy, false), 479 FieldNo, DestTy); 480 Constant *E = getFoldedSizeOf(ATy->getElementType(), DestTy, true); 481 return ConstantExpr::getNUWMul(E, N); 482 } 483 484 if (StructType *STy = dyn_cast<StructType>(Ty)) 485 if (!STy->isPacked()) { 486 unsigned NumElems = STy->getNumElements(); 487 // An empty struct has no members. 488 if (NumElems == 0) 489 return nullptr; 490 // Check for a struct with all members having the same size. 491 Constant *MemberSize = 492 getFoldedSizeOf(STy->getElementType(0), DestTy, true); 493 bool AllSame = true; 494 for (unsigned i = 1; i != NumElems; ++i) 495 if (MemberSize != 496 getFoldedSizeOf(STy->getElementType(i), DestTy, true)) { 497 AllSame = false; 498 break; 499 } 500 if (AllSame) { 501 Constant *N = ConstantExpr::getCast(CastInst::getCastOpcode(FieldNo, 502 false, 503 DestTy, 504 false), 505 FieldNo, DestTy); 506 return ConstantExpr::getNUWMul(MemberSize, N); 507 } 508 } 509 510 // If there's no interesting folding happening, bail so that we don't create 511 // a constant that looks like it needs folding but really doesn't. 512 if (!Folded) 513 return nullptr; 514 515 // Base case: Get a regular offsetof expression. 516 Constant *C = ConstantExpr::getOffsetOf(Ty, FieldNo); 517 C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, 518 DestTy, false), 519 C, DestTy); 520 return C; 521 } 522 523 Constant *llvm::ConstantFoldCastInstruction(unsigned opc, Constant *V, 524 Type *DestTy) { 525 if (isa<PoisonValue>(V)) 526 return PoisonValue::get(DestTy); 527 528 if (isa<UndefValue>(V)) { 529 // zext(undef) = 0, because the top bits will be zero. 530 // sext(undef) = 0, because the top bits will all be the same. 531 // [us]itofp(undef) = 0, because the result value is bounded. 532 if (opc == Instruction::ZExt || opc == Instruction::SExt || 533 opc == Instruction::UIToFP || opc == Instruction::SIToFP) 534 return Constant::getNullValue(DestTy); 535 return UndefValue::get(DestTy); 536 } 537 538 if (V->isNullValue() && !DestTy->isX86_MMXTy() && !DestTy->isX86_AMXTy() && 539 opc != Instruction::AddrSpaceCast) 540 return Constant::getNullValue(DestTy); 541 542 // If the cast operand is a constant expression, there's a few things we can 543 // do to try to simplify it. 544 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 545 if (CE->isCast()) { 546 // Try hard to fold cast of cast because they are often eliminable. 547 if (unsigned newOpc = foldConstantCastPair(opc, CE, DestTy)) 548 return ConstantExpr::getCast(newOpc, CE->getOperand(0), DestTy); 549 } else if (CE->getOpcode() == Instruction::GetElementPtr && 550 // Do not fold addrspacecast (gep 0, .., 0). It might make the 551 // addrspacecast uncanonicalized. 552 opc != Instruction::AddrSpaceCast && 553 // Do not fold bitcast (gep) with inrange index, as this loses 554 // information. 555 !cast<GEPOperator>(CE)->getInRangeIndex().hasValue() && 556 // Do not fold if the gep type is a vector, as bitcasting 557 // operand 0 of a vector gep will result in a bitcast between 558 // different sizes. 559 !CE->getType()->isVectorTy()) { 560 // If all of the indexes in the GEP are null values, there is no pointer 561 // adjustment going on. We might as well cast the source pointer. 562 bool isAllNull = true; 563 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i) 564 if (!CE->getOperand(i)->isNullValue()) { 565 isAllNull = false; 566 break; 567 } 568 if (isAllNull) 569 // This is casting one pointer type to another, always BitCast 570 return ConstantExpr::getPointerCast(CE->getOperand(0), DestTy); 571 } 572 } 573 574 // If the cast operand is a constant vector, perform the cast by 575 // operating on each element. In the cast of bitcasts, the element 576 // count may be mismatched; don't attempt to handle that here. 577 if ((isa<ConstantVector>(V) || isa<ConstantDataVector>(V)) && 578 DestTy->isVectorTy() && 579 cast<FixedVectorType>(DestTy)->getNumElements() == 580 cast<FixedVectorType>(V->getType())->getNumElements()) { 581 VectorType *DestVecTy = cast<VectorType>(DestTy); 582 Type *DstEltTy = DestVecTy->getElementType(); 583 // Fast path for splatted constants. 584 if (Constant *Splat = V->getSplatValue()) { 585 return ConstantVector::getSplat( 586 cast<VectorType>(DestTy)->getElementCount(), 587 ConstantExpr::getCast(opc, Splat, DstEltTy)); 588 } 589 SmallVector<Constant *, 16> res; 590 Type *Ty = IntegerType::get(V->getContext(), 32); 591 for (unsigned i = 0, 592 e = cast<FixedVectorType>(V->getType())->getNumElements(); 593 i != e; ++i) { 594 Constant *C = 595 ConstantExpr::getExtractElement(V, ConstantInt::get(Ty, i)); 596 res.push_back(ConstantExpr::getCast(opc, C, DstEltTy)); 597 } 598 return ConstantVector::get(res); 599 } 600 601 // We actually have to do a cast now. Perform the cast according to the 602 // opcode specified. 603 switch (opc) { 604 default: 605 llvm_unreachable("Failed to cast constant expression"); 606 case Instruction::FPTrunc: 607 case Instruction::FPExt: 608 if (ConstantFP *FPC = dyn_cast<ConstantFP>(V)) { 609 bool ignored; 610 APFloat Val = FPC->getValueAPF(); 611 Val.convert(DestTy->isHalfTy() ? APFloat::IEEEhalf() : 612 DestTy->isFloatTy() ? APFloat::IEEEsingle() : 613 DestTy->isDoubleTy() ? APFloat::IEEEdouble() : 614 DestTy->isX86_FP80Ty() ? APFloat::x87DoubleExtended() : 615 DestTy->isFP128Ty() ? APFloat::IEEEquad() : 616 DestTy->isPPC_FP128Ty() ? APFloat::PPCDoubleDouble() : 617 APFloat::Bogus(), 618 APFloat::rmNearestTiesToEven, &ignored); 619 return ConstantFP::get(V->getContext(), Val); 620 } 621 return nullptr; // Can't fold. 622 case Instruction::FPToUI: 623 case Instruction::FPToSI: 624 if (ConstantFP *FPC = dyn_cast<ConstantFP>(V)) { 625 const APFloat &V = FPC->getValueAPF(); 626 bool ignored; 627 uint32_t DestBitWidth = cast<IntegerType>(DestTy)->getBitWidth(); 628 APSInt IntVal(DestBitWidth, opc == Instruction::FPToUI); 629 if (APFloat::opInvalidOp == 630 V.convertToInteger(IntVal, APFloat::rmTowardZero, &ignored)) { 631 // Undefined behavior invoked - the destination type can't represent 632 // the input constant. 633 return PoisonValue::get(DestTy); 634 } 635 return ConstantInt::get(FPC->getContext(), IntVal); 636 } 637 return nullptr; // Can't fold. 638 case Instruction::IntToPtr: //always treated as unsigned 639 if (V->isNullValue()) // Is it an integral null value? 640 return ConstantPointerNull::get(cast<PointerType>(DestTy)); 641 return nullptr; // Other pointer types cannot be casted 642 case Instruction::PtrToInt: // always treated as unsigned 643 // Is it a null pointer value? 644 if (V->isNullValue()) 645 return ConstantInt::get(DestTy, 0); 646 // If this is a sizeof-like expression, pull out multiplications by 647 // known factors to expose them to subsequent folding. If it's an 648 // alignof-like expression, factor out known factors. 649 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 650 if (CE->getOpcode() == Instruction::GetElementPtr && 651 CE->getOperand(0)->isNullValue()) { 652 // FIXME: Looks like getFoldedSizeOf(), getFoldedOffsetOf() and 653 // getFoldedAlignOf() don't handle the case when DestTy is a vector of 654 // pointers yet. We end up in asserts in CastInst::getCastOpcode (see 655 // test/Analysis/ConstantFolding/cast-vector.ll). I've only seen this 656 // happen in one "real" C-code test case, so it does not seem to be an 657 // important optimization to handle vectors here. For now, simply bail 658 // out. 659 if (DestTy->isVectorTy()) 660 return nullptr; 661 GEPOperator *GEPO = cast<GEPOperator>(CE); 662 Type *Ty = GEPO->getSourceElementType(); 663 if (CE->getNumOperands() == 2) { 664 // Handle a sizeof-like expression. 665 Constant *Idx = CE->getOperand(1); 666 bool isOne = isa<ConstantInt>(Idx) && cast<ConstantInt>(Idx)->isOne(); 667 if (Constant *C = getFoldedSizeOf(Ty, DestTy, !isOne)) { 668 Idx = ConstantExpr::getCast(CastInst::getCastOpcode(Idx, true, 669 DestTy, false), 670 Idx, DestTy); 671 return ConstantExpr::getMul(C, Idx); 672 } 673 } else if (CE->getNumOperands() == 3 && 674 CE->getOperand(1)->isNullValue()) { 675 // Handle an alignof-like expression. 676 if (StructType *STy = dyn_cast<StructType>(Ty)) 677 if (!STy->isPacked()) { 678 ConstantInt *CI = cast<ConstantInt>(CE->getOperand(2)); 679 if (CI->isOne() && 680 STy->getNumElements() == 2 && 681 STy->getElementType(0)->isIntegerTy(1)) { 682 return getFoldedAlignOf(STy->getElementType(1), DestTy, false); 683 } 684 } 685 // Handle an offsetof-like expression. 686 if (Ty->isStructTy() || Ty->isArrayTy()) { 687 if (Constant *C = getFoldedOffsetOf(Ty, CE->getOperand(2), 688 DestTy, false)) 689 return C; 690 } 691 } 692 } 693 // Other pointer types cannot be casted 694 return nullptr; 695 case Instruction::UIToFP: 696 case Instruction::SIToFP: 697 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 698 const APInt &api = CI->getValue(); 699 APFloat apf(DestTy->getFltSemantics(), 700 APInt::getNullValue(DestTy->getPrimitiveSizeInBits())); 701 apf.convertFromAPInt(api, opc==Instruction::SIToFP, 702 APFloat::rmNearestTiesToEven); 703 return ConstantFP::get(V->getContext(), apf); 704 } 705 return nullptr; 706 case Instruction::ZExt: 707 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 708 uint32_t BitWidth = cast<IntegerType>(DestTy)->getBitWidth(); 709 return ConstantInt::get(V->getContext(), 710 CI->getValue().zext(BitWidth)); 711 } 712 return nullptr; 713 case Instruction::SExt: 714 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 715 uint32_t BitWidth = cast<IntegerType>(DestTy)->getBitWidth(); 716 return ConstantInt::get(V->getContext(), 717 CI->getValue().sext(BitWidth)); 718 } 719 return nullptr; 720 case Instruction::Trunc: { 721 if (V->getType()->isVectorTy()) 722 return nullptr; 723 724 uint32_t DestBitWidth = cast<IntegerType>(DestTy)->getBitWidth(); 725 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 726 return ConstantInt::get(V->getContext(), 727 CI->getValue().trunc(DestBitWidth)); 728 } 729 730 // The input must be a constantexpr. See if we can simplify this based on 731 // the bytes we are demanding. Only do this if the source and dest are an 732 // even multiple of a byte. 733 if ((DestBitWidth & 7) == 0 && 734 (cast<IntegerType>(V->getType())->getBitWidth() & 7) == 0) 735 if (Constant *Res = ExtractConstantBytes(V, 0, DestBitWidth / 8)) 736 return Res; 737 738 return nullptr; 739 } 740 case Instruction::BitCast: 741 return FoldBitCast(V, DestTy); 742 case Instruction::AddrSpaceCast: 743 return nullptr; 744 } 745 } 746 747 Constant *llvm::ConstantFoldSelectInstruction(Constant *Cond, 748 Constant *V1, Constant *V2) { 749 // Check for i1 and vector true/false conditions. 750 if (Cond->isNullValue()) return V2; 751 if (Cond->isAllOnesValue()) return V1; 752 753 // If the condition is a vector constant, fold the result elementwise. 754 if (ConstantVector *CondV = dyn_cast<ConstantVector>(Cond)) { 755 auto *V1VTy = CondV->getType(); 756 SmallVector<Constant*, 16> Result; 757 Type *Ty = IntegerType::get(CondV->getContext(), 32); 758 for (unsigned i = 0, e = V1VTy->getNumElements(); i != e; ++i) { 759 Constant *V; 760 Constant *V1Element = ConstantExpr::getExtractElement(V1, 761 ConstantInt::get(Ty, i)); 762 Constant *V2Element = ConstantExpr::getExtractElement(V2, 763 ConstantInt::get(Ty, i)); 764 auto *Cond = cast<Constant>(CondV->getOperand(i)); 765 if (isa<PoisonValue>(Cond)) { 766 V = PoisonValue::get(V1Element->getType()); 767 } else if (V1Element == V2Element) { 768 V = V1Element; 769 } else if (isa<UndefValue>(Cond)) { 770 V = isa<UndefValue>(V1Element) ? V1Element : V2Element; 771 } else { 772 if (!isa<ConstantInt>(Cond)) break; 773 V = Cond->isNullValue() ? V2Element : V1Element; 774 } 775 Result.push_back(V); 776 } 777 778 // If we were able to build the vector, return it. 779 if (Result.size() == V1VTy->getNumElements()) 780 return ConstantVector::get(Result); 781 } 782 783 if (isa<PoisonValue>(Cond)) 784 return PoisonValue::get(V1->getType()); 785 786 if (isa<UndefValue>(Cond)) { 787 if (isa<UndefValue>(V1)) return V1; 788 return V2; 789 } 790 791 if (V1 == V2) return V1; 792 793 if (isa<PoisonValue>(V1)) 794 return V2; 795 if (isa<PoisonValue>(V2)) 796 return V1; 797 798 // If the true or false value is undef, we can fold to the other value as 799 // long as the other value isn't poison. 800 auto NotPoison = [](Constant *C) { 801 if (isa<PoisonValue>(C)) 802 return false; 803 804 // TODO: We can analyze ConstExpr by opcode to determine if there is any 805 // possibility of poison. 806 if (isa<ConstantExpr>(C)) 807 return false; 808 809 if (isa<ConstantInt>(C) || isa<GlobalVariable>(C) || isa<ConstantFP>(C) || 810 isa<ConstantPointerNull>(C) || isa<Function>(C)) 811 return true; 812 813 if (C->getType()->isVectorTy()) 814 return !C->containsPoisonElement() && !C->containsConstantExpression(); 815 816 // TODO: Recursively analyze aggregates or other constants. 817 return false; 818 }; 819 if (isa<UndefValue>(V1) && NotPoison(V2)) return V2; 820 if (isa<UndefValue>(V2) && NotPoison(V1)) return V1; 821 822 if (ConstantExpr *TrueVal = dyn_cast<ConstantExpr>(V1)) { 823 if (TrueVal->getOpcode() == Instruction::Select) 824 if (TrueVal->getOperand(0) == Cond) 825 return ConstantExpr::getSelect(Cond, TrueVal->getOperand(1), V2); 826 } 827 if (ConstantExpr *FalseVal = dyn_cast<ConstantExpr>(V2)) { 828 if (FalseVal->getOpcode() == Instruction::Select) 829 if (FalseVal->getOperand(0) == Cond) 830 return ConstantExpr::getSelect(Cond, V1, FalseVal->getOperand(2)); 831 } 832 833 return nullptr; 834 } 835 836 Constant *llvm::ConstantFoldExtractElementInstruction(Constant *Val, 837 Constant *Idx) { 838 auto *ValVTy = cast<VectorType>(Val->getType()); 839 840 // extractelt poison, C -> poison 841 // extractelt C, undef -> poison 842 if (isa<PoisonValue>(Val) || isa<UndefValue>(Idx)) 843 return PoisonValue::get(ValVTy->getElementType()); 844 845 // extractelt undef, C -> undef 846 if (isa<UndefValue>(Val)) 847 return UndefValue::get(ValVTy->getElementType()); 848 849 auto *CIdx = dyn_cast<ConstantInt>(Idx); 850 if (!CIdx) 851 return nullptr; 852 853 if (auto *ValFVTy = dyn_cast<FixedVectorType>(Val->getType())) { 854 // ee({w,x,y,z}, wrong_value) -> poison 855 if (CIdx->uge(ValFVTy->getNumElements())) 856 return PoisonValue::get(ValFVTy->getElementType()); 857 } 858 859 // ee (gep (ptr, idx0, ...), idx) -> gep (ee (ptr, idx), ee (idx0, idx), ...) 860 if (auto *CE = dyn_cast<ConstantExpr>(Val)) { 861 if (CE->getOpcode() == Instruction::GetElementPtr) { 862 SmallVector<Constant *, 8> Ops; 863 Ops.reserve(CE->getNumOperands()); 864 for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i) { 865 Constant *Op = CE->getOperand(i); 866 if (Op->getType()->isVectorTy()) { 867 Constant *ScalarOp = ConstantExpr::getExtractElement(Op, Idx); 868 if (!ScalarOp) 869 return nullptr; 870 Ops.push_back(ScalarOp); 871 } else 872 Ops.push_back(Op); 873 } 874 return CE->getWithOperands(Ops, ValVTy->getElementType(), false, 875 Ops[0]->getType()->getPointerElementType()); 876 } else if (CE->getOpcode() == Instruction::InsertElement) { 877 if (const auto *IEIdx = dyn_cast<ConstantInt>(CE->getOperand(2))) { 878 if (APSInt::isSameValue(APSInt(IEIdx->getValue()), 879 APSInt(CIdx->getValue()))) { 880 return CE->getOperand(1); 881 } else { 882 return ConstantExpr::getExtractElement(CE->getOperand(0), CIdx); 883 } 884 } 885 } 886 } 887 888 // CAZ of type ScalableVectorType and n < CAZ->getMinNumElements() => 889 // extractelt CAZ, n -> 0 890 if (auto *ValSVTy = dyn_cast<ScalableVectorType>(Val->getType())) { 891 if (!CIdx->uge(ValSVTy->getMinNumElements())) { 892 if (auto *CAZ = dyn_cast<ConstantAggregateZero>(Val)) 893 return CAZ->getElementValue(CIdx->getZExtValue()); 894 } 895 return nullptr; 896 } 897 898 return Val->getAggregateElement(CIdx); 899 } 900 901 Constant *llvm::ConstantFoldInsertElementInstruction(Constant *Val, 902 Constant *Elt, 903 Constant *Idx) { 904 if (isa<UndefValue>(Idx)) 905 return PoisonValue::get(Val->getType()); 906 907 ConstantInt *CIdx = dyn_cast<ConstantInt>(Idx); 908 if (!CIdx) return nullptr; 909 910 // Do not iterate on scalable vector. The num of elements is unknown at 911 // compile-time. 912 if (isa<ScalableVectorType>(Val->getType())) 913 return nullptr; 914 915 auto *ValTy = cast<FixedVectorType>(Val->getType()); 916 917 unsigned NumElts = ValTy->getNumElements(); 918 if (CIdx->uge(NumElts)) 919 return PoisonValue::get(Val->getType()); 920 921 SmallVector<Constant*, 16> Result; 922 Result.reserve(NumElts); 923 auto *Ty = Type::getInt32Ty(Val->getContext()); 924 uint64_t IdxVal = CIdx->getZExtValue(); 925 for (unsigned i = 0; i != NumElts; ++i) { 926 if (i == IdxVal) { 927 Result.push_back(Elt); 928 continue; 929 } 930 931 Constant *C = ConstantExpr::getExtractElement(Val, ConstantInt::get(Ty, i)); 932 Result.push_back(C); 933 } 934 935 return ConstantVector::get(Result); 936 } 937 938 Constant *llvm::ConstantFoldShuffleVectorInstruction(Constant *V1, Constant *V2, 939 ArrayRef<int> Mask) { 940 auto *V1VTy = cast<VectorType>(V1->getType()); 941 unsigned MaskNumElts = Mask.size(); 942 auto MaskEltCount = 943 ElementCount::get(MaskNumElts, isa<ScalableVectorType>(V1VTy)); 944 Type *EltTy = V1VTy->getElementType(); 945 946 // Undefined shuffle mask -> undefined value. 947 if (all_of(Mask, [](int Elt) { return Elt == UndefMaskElem; })) { 948 return UndefValue::get(FixedVectorType::get(EltTy, MaskNumElts)); 949 } 950 951 // If the mask is all zeros this is a splat, no need to go through all 952 // elements. 953 if (all_of(Mask, [](int Elt) { return Elt == 0; }) && 954 !MaskEltCount.isScalable()) { 955 Type *Ty = IntegerType::get(V1->getContext(), 32); 956 Constant *Elt = 957 ConstantExpr::getExtractElement(V1, ConstantInt::get(Ty, 0)); 958 return ConstantVector::getSplat(MaskEltCount, Elt); 959 } 960 // Do not iterate on scalable vector. The num of elements is unknown at 961 // compile-time. 962 if (isa<ScalableVectorType>(V1VTy)) 963 return nullptr; 964 965 unsigned SrcNumElts = V1VTy->getElementCount().getKnownMinValue(); 966 967 // Loop over the shuffle mask, evaluating each element. 968 SmallVector<Constant*, 32> Result; 969 for (unsigned i = 0; i != MaskNumElts; ++i) { 970 int Elt = Mask[i]; 971 if (Elt == -1) { 972 Result.push_back(UndefValue::get(EltTy)); 973 continue; 974 } 975 Constant *InElt; 976 if (unsigned(Elt) >= SrcNumElts*2) 977 InElt = UndefValue::get(EltTy); 978 else if (unsigned(Elt) >= SrcNumElts) { 979 Type *Ty = IntegerType::get(V2->getContext(), 32); 980 InElt = 981 ConstantExpr::getExtractElement(V2, 982 ConstantInt::get(Ty, Elt - SrcNumElts)); 983 } else { 984 Type *Ty = IntegerType::get(V1->getContext(), 32); 985 InElt = ConstantExpr::getExtractElement(V1, ConstantInt::get(Ty, Elt)); 986 } 987 Result.push_back(InElt); 988 } 989 990 return ConstantVector::get(Result); 991 } 992 993 Constant *llvm::ConstantFoldExtractValueInstruction(Constant *Agg, 994 ArrayRef<unsigned> Idxs) { 995 // Base case: no indices, so return the entire value. 996 if (Idxs.empty()) 997 return Agg; 998 999 if (Constant *C = Agg->getAggregateElement(Idxs[0])) 1000 return ConstantFoldExtractValueInstruction(C, Idxs.slice(1)); 1001 1002 return nullptr; 1003 } 1004 1005 Constant *llvm::ConstantFoldInsertValueInstruction(Constant *Agg, 1006 Constant *Val, 1007 ArrayRef<unsigned> Idxs) { 1008 // Base case: no indices, so replace the entire value. 1009 if (Idxs.empty()) 1010 return Val; 1011 1012 unsigned NumElts; 1013 if (StructType *ST = dyn_cast<StructType>(Agg->getType())) 1014 NumElts = ST->getNumElements(); 1015 else 1016 NumElts = cast<ArrayType>(Agg->getType())->getNumElements(); 1017 1018 SmallVector<Constant*, 32> Result; 1019 for (unsigned i = 0; i != NumElts; ++i) { 1020 Constant *C = Agg->getAggregateElement(i); 1021 if (!C) return nullptr; 1022 1023 if (Idxs[0] == i) 1024 C = ConstantFoldInsertValueInstruction(C, Val, Idxs.slice(1)); 1025 1026 Result.push_back(C); 1027 } 1028 1029 if (StructType *ST = dyn_cast<StructType>(Agg->getType())) 1030 return ConstantStruct::get(ST, Result); 1031 return ConstantArray::get(cast<ArrayType>(Agg->getType()), Result); 1032 } 1033 1034 Constant *llvm::ConstantFoldUnaryInstruction(unsigned Opcode, Constant *C) { 1035 assert(Instruction::isUnaryOp(Opcode) && "Non-unary instruction detected"); 1036 1037 // Handle scalar UndefValue and scalable vector UndefValue. Fixed-length 1038 // vectors are always evaluated per element. 1039 bool IsScalableVector = isa<ScalableVectorType>(C->getType()); 1040 bool HasScalarUndefOrScalableVectorUndef = 1041 (!C->getType()->isVectorTy() || IsScalableVector) && isa<UndefValue>(C); 1042 1043 if (HasScalarUndefOrScalableVectorUndef) { 1044 switch (static_cast<Instruction::UnaryOps>(Opcode)) { 1045 case Instruction::FNeg: 1046 return C; // -undef -> undef 1047 case Instruction::UnaryOpsEnd: 1048 llvm_unreachable("Invalid UnaryOp"); 1049 } 1050 } 1051 1052 // Constant should not be UndefValue, unless these are vector constants. 1053 assert(!HasScalarUndefOrScalableVectorUndef && "Unexpected UndefValue"); 1054 // We only have FP UnaryOps right now. 1055 assert(!isa<ConstantInt>(C) && "Unexpected Integer UnaryOp"); 1056 1057 if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) { 1058 const APFloat &CV = CFP->getValueAPF(); 1059 switch (Opcode) { 1060 default: 1061 break; 1062 case Instruction::FNeg: 1063 return ConstantFP::get(C->getContext(), neg(CV)); 1064 } 1065 } else if (auto *VTy = dyn_cast<FixedVectorType>(C->getType())) { 1066 1067 Type *Ty = IntegerType::get(VTy->getContext(), 32); 1068 // Fast path for splatted constants. 1069 if (Constant *Splat = C->getSplatValue()) { 1070 Constant *Elt = ConstantExpr::get(Opcode, Splat); 1071 return ConstantVector::getSplat(VTy->getElementCount(), Elt); 1072 } 1073 1074 // Fold each element and create a vector constant from those constants. 1075 SmallVector<Constant *, 16> Result; 1076 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 1077 Constant *ExtractIdx = ConstantInt::get(Ty, i); 1078 Constant *Elt = ConstantExpr::getExtractElement(C, ExtractIdx); 1079 1080 Result.push_back(ConstantExpr::get(Opcode, Elt)); 1081 } 1082 1083 return ConstantVector::get(Result); 1084 } 1085 1086 // We don't know how to fold this. 1087 return nullptr; 1088 } 1089 1090 Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode, Constant *C1, 1091 Constant *C2) { 1092 assert(Instruction::isBinaryOp(Opcode) && "Non-binary instruction detected"); 1093 1094 // Simplify BinOps with their identity values first. They are no-ops and we 1095 // can always return the other value, including undef or poison values. 1096 // FIXME: remove unnecessary duplicated identity patterns below. 1097 // FIXME: Use AllowRHSConstant with getBinOpIdentity to handle additional ops, 1098 // like X << 0 = X. 1099 Constant *Identity = ConstantExpr::getBinOpIdentity(Opcode, C1->getType()); 1100 if (Identity) { 1101 if (C1 == Identity) 1102 return C2; 1103 if (C2 == Identity) 1104 return C1; 1105 } 1106 1107 // Binary operations propagate poison. 1108 // FIXME: Currently, or/and i1 poison aren't folded into poison because 1109 // it causes miscompilation when combined with another optimization in 1110 // InstCombine (select i1 -> and/or). The select fold is wrong, but 1111 // fixing it requires an effort, so temporarily disable this until it is 1112 // fixed. 1113 bool PoisonFold = !C1->getType()->isIntegerTy(1) || 1114 (Opcode != Instruction::Or && Opcode != Instruction::And); 1115 if (PoisonFold && (isa<PoisonValue>(C1) || isa<PoisonValue>(C2))) 1116 return PoisonValue::get(C1->getType()); 1117 1118 // Handle scalar UndefValue and scalable vector UndefValue. Fixed-length 1119 // vectors are always evaluated per element. 1120 bool IsScalableVector = isa<ScalableVectorType>(C1->getType()); 1121 bool HasScalarUndefOrScalableVectorUndef = 1122 (!C1->getType()->isVectorTy() || IsScalableVector) && 1123 (isa<UndefValue>(C1) || isa<UndefValue>(C2)); 1124 if (HasScalarUndefOrScalableVectorUndef) { 1125 switch (static_cast<Instruction::BinaryOps>(Opcode)) { 1126 case Instruction::Xor: 1127 if (isa<UndefValue>(C1) && isa<UndefValue>(C2)) 1128 // Handle undef ^ undef -> 0 special case. This is a common 1129 // idiom (misuse). 1130 return Constant::getNullValue(C1->getType()); 1131 LLVM_FALLTHROUGH; 1132 case Instruction::Add: 1133 case Instruction::Sub: 1134 return UndefValue::get(C1->getType()); 1135 case Instruction::And: 1136 if (isa<UndefValue>(C1) && isa<UndefValue>(C2)) // undef & undef -> undef 1137 return C1; 1138 return Constant::getNullValue(C1->getType()); // undef & X -> 0 1139 case Instruction::Mul: { 1140 // undef * undef -> undef 1141 if (isa<UndefValue>(C1) && isa<UndefValue>(C2)) 1142 return C1; 1143 const APInt *CV; 1144 // X * undef -> undef if X is odd 1145 if (match(C1, m_APInt(CV)) || match(C2, m_APInt(CV))) 1146 if ((*CV)[0]) 1147 return UndefValue::get(C1->getType()); 1148 1149 // X * undef -> 0 otherwise 1150 return Constant::getNullValue(C1->getType()); 1151 } 1152 case Instruction::SDiv: 1153 case Instruction::UDiv: 1154 // X / undef -> poison 1155 // X / 0 -> poison 1156 if (match(C2, m_CombineOr(m_Undef(), m_Zero()))) 1157 return PoisonValue::get(C2->getType()); 1158 // undef / 1 -> undef 1159 if (match(C2, m_One())) 1160 return C1; 1161 // undef / X -> 0 otherwise 1162 return Constant::getNullValue(C1->getType()); 1163 case Instruction::URem: 1164 case Instruction::SRem: 1165 // X % undef -> poison 1166 // X % 0 -> poison 1167 if (match(C2, m_CombineOr(m_Undef(), m_Zero()))) 1168 return PoisonValue::get(C2->getType()); 1169 // undef % X -> 0 otherwise 1170 return Constant::getNullValue(C1->getType()); 1171 case Instruction::Or: // X | undef -> -1 1172 if (isa<UndefValue>(C1) && isa<UndefValue>(C2)) // undef | undef -> undef 1173 return C1; 1174 return Constant::getAllOnesValue(C1->getType()); // undef | X -> ~0 1175 case Instruction::LShr: 1176 // X >>l undef -> poison 1177 if (isa<UndefValue>(C2)) 1178 return PoisonValue::get(C2->getType()); 1179 // undef >>l 0 -> undef 1180 if (match(C2, m_Zero())) 1181 return C1; 1182 // undef >>l X -> 0 1183 return Constant::getNullValue(C1->getType()); 1184 case Instruction::AShr: 1185 // X >>a undef -> poison 1186 if (isa<UndefValue>(C2)) 1187 return PoisonValue::get(C2->getType()); 1188 // undef >>a 0 -> undef 1189 if (match(C2, m_Zero())) 1190 return C1; 1191 // TODO: undef >>a X -> poison if the shift is exact 1192 // undef >>a X -> 0 1193 return Constant::getNullValue(C1->getType()); 1194 case Instruction::Shl: 1195 // X << undef -> undef 1196 if (isa<UndefValue>(C2)) 1197 return PoisonValue::get(C2->getType()); 1198 // undef << 0 -> undef 1199 if (match(C2, m_Zero())) 1200 return C1; 1201 // undef << X -> 0 1202 return Constant::getNullValue(C1->getType()); 1203 case Instruction::FSub: 1204 // -0.0 - undef --> undef (consistent with "fneg undef") 1205 if (match(C1, m_NegZeroFP()) && isa<UndefValue>(C2)) 1206 return C2; 1207 LLVM_FALLTHROUGH; 1208 case Instruction::FAdd: 1209 case Instruction::FMul: 1210 case Instruction::FDiv: 1211 case Instruction::FRem: 1212 // [any flop] undef, undef -> undef 1213 if (isa<UndefValue>(C1) && isa<UndefValue>(C2)) 1214 return C1; 1215 // [any flop] C, undef -> NaN 1216 // [any flop] undef, C -> NaN 1217 // We could potentially specialize NaN/Inf constants vs. 'normal' 1218 // constants (possibly differently depending on opcode and operand). This 1219 // would allow returning undef sometimes. But it is always safe to fold to 1220 // NaN because we can choose the undef operand as NaN, and any FP opcode 1221 // with a NaN operand will propagate NaN. 1222 return ConstantFP::getNaN(C1->getType()); 1223 case Instruction::BinaryOpsEnd: 1224 llvm_unreachable("Invalid BinaryOp"); 1225 } 1226 } 1227 1228 // Neither constant should be UndefValue, unless these are vector constants. 1229 assert((!HasScalarUndefOrScalableVectorUndef) && "Unexpected UndefValue"); 1230 1231 // Handle simplifications when the RHS is a constant int. 1232 if (ConstantInt *CI2 = dyn_cast<ConstantInt>(C2)) { 1233 switch (Opcode) { 1234 case Instruction::Add: 1235 if (CI2->isZero()) return C1; // X + 0 == X 1236 break; 1237 case Instruction::Sub: 1238 if (CI2->isZero()) return C1; // X - 0 == X 1239 break; 1240 case Instruction::Mul: 1241 if (CI2->isZero()) return C2; // X * 0 == 0 1242 if (CI2->isOne()) 1243 return C1; // X * 1 == X 1244 break; 1245 case Instruction::UDiv: 1246 case Instruction::SDiv: 1247 if (CI2->isOne()) 1248 return C1; // X / 1 == X 1249 if (CI2->isZero()) 1250 return PoisonValue::get(CI2->getType()); // X / 0 == poison 1251 break; 1252 case Instruction::URem: 1253 case Instruction::SRem: 1254 if (CI2->isOne()) 1255 return Constant::getNullValue(CI2->getType()); // X % 1 == 0 1256 if (CI2->isZero()) 1257 return PoisonValue::get(CI2->getType()); // X % 0 == poison 1258 break; 1259 case Instruction::And: 1260 if (CI2->isZero()) return C2; // X & 0 == 0 1261 if (CI2->isMinusOne()) 1262 return C1; // X & -1 == X 1263 1264 if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1)) { 1265 // (zext i32 to i64) & 4294967295 -> (zext i32 to i64) 1266 if (CE1->getOpcode() == Instruction::ZExt) { 1267 unsigned DstWidth = CI2->getType()->getBitWidth(); 1268 unsigned SrcWidth = 1269 CE1->getOperand(0)->getType()->getPrimitiveSizeInBits(); 1270 APInt PossiblySetBits(APInt::getLowBitsSet(DstWidth, SrcWidth)); 1271 if ((PossiblySetBits & CI2->getValue()) == PossiblySetBits) 1272 return C1; 1273 } 1274 1275 // If and'ing the address of a global with a constant, fold it. 1276 if (CE1->getOpcode() == Instruction::PtrToInt && 1277 isa<GlobalValue>(CE1->getOperand(0))) { 1278 GlobalValue *GV = cast<GlobalValue>(CE1->getOperand(0)); 1279 1280 MaybeAlign GVAlign; 1281 1282 if (Module *TheModule = GV->getParent()) { 1283 const DataLayout &DL = TheModule->getDataLayout(); 1284 GVAlign = GV->getPointerAlignment(DL); 1285 1286 // If the function alignment is not specified then assume that it 1287 // is 4. 1288 // This is dangerous; on x86, the alignment of the pointer 1289 // corresponds to the alignment of the function, but might be less 1290 // than 4 if it isn't explicitly specified. 1291 // However, a fix for this behaviour was reverted because it 1292 // increased code size (see https://reviews.llvm.org/D55115) 1293 // FIXME: This code should be deleted once existing targets have 1294 // appropriate defaults 1295 if (isa<Function>(GV) && !DL.getFunctionPtrAlign()) 1296 GVAlign = Align(4); 1297 } else if (isa<Function>(GV)) { 1298 // Without a datalayout we have to assume the worst case: that the 1299 // function pointer isn't aligned at all. 1300 GVAlign = llvm::None; 1301 } else if (isa<GlobalVariable>(GV)) { 1302 GVAlign = cast<GlobalVariable>(GV)->getAlign(); 1303 } 1304 1305 if (GVAlign && *GVAlign > 1) { 1306 unsigned DstWidth = CI2->getType()->getBitWidth(); 1307 unsigned SrcWidth = std::min(DstWidth, Log2(*GVAlign)); 1308 APInt BitsNotSet(APInt::getLowBitsSet(DstWidth, SrcWidth)); 1309 1310 // If checking bits we know are clear, return zero. 1311 if ((CI2->getValue() & BitsNotSet) == CI2->getValue()) 1312 return Constant::getNullValue(CI2->getType()); 1313 } 1314 } 1315 } 1316 break; 1317 case Instruction::Or: 1318 if (CI2->isZero()) return C1; // X | 0 == X 1319 if (CI2->isMinusOne()) 1320 return C2; // X | -1 == -1 1321 break; 1322 case Instruction::Xor: 1323 if (CI2->isZero()) return C1; // X ^ 0 == X 1324 1325 if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1)) { 1326 switch (CE1->getOpcode()) { 1327 default: break; 1328 case Instruction::ICmp: 1329 case Instruction::FCmp: 1330 // cmp pred ^ true -> cmp !pred 1331 assert(CI2->isOne()); 1332 CmpInst::Predicate pred = (CmpInst::Predicate)CE1->getPredicate(); 1333 pred = CmpInst::getInversePredicate(pred); 1334 return ConstantExpr::getCompare(pred, CE1->getOperand(0), 1335 CE1->getOperand(1)); 1336 } 1337 } 1338 break; 1339 case Instruction::AShr: 1340 // ashr (zext C to Ty), C2 -> lshr (zext C, CSA), C2 1341 if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1)) 1342 if (CE1->getOpcode() == Instruction::ZExt) // Top bits known zero. 1343 return ConstantExpr::getLShr(C1, C2); 1344 break; 1345 } 1346 } else if (isa<ConstantInt>(C1)) { 1347 // If C1 is a ConstantInt and C2 is not, swap the operands. 1348 if (Instruction::isCommutative(Opcode)) 1349 return ConstantExpr::get(Opcode, C2, C1); 1350 } 1351 1352 if (ConstantInt *CI1 = dyn_cast<ConstantInt>(C1)) { 1353 if (ConstantInt *CI2 = dyn_cast<ConstantInt>(C2)) { 1354 const APInt &C1V = CI1->getValue(); 1355 const APInt &C2V = CI2->getValue(); 1356 switch (Opcode) { 1357 default: 1358 break; 1359 case Instruction::Add: 1360 return ConstantInt::get(CI1->getContext(), C1V + C2V); 1361 case Instruction::Sub: 1362 return ConstantInt::get(CI1->getContext(), C1V - C2V); 1363 case Instruction::Mul: 1364 return ConstantInt::get(CI1->getContext(), C1V * C2V); 1365 case Instruction::UDiv: 1366 assert(!CI2->isZero() && "Div by zero handled above"); 1367 return ConstantInt::get(CI1->getContext(), C1V.udiv(C2V)); 1368 case Instruction::SDiv: 1369 assert(!CI2->isZero() && "Div by zero handled above"); 1370 if (C2V.isAllOnesValue() && C1V.isMinSignedValue()) 1371 return PoisonValue::get(CI1->getType()); // MIN_INT / -1 -> poison 1372 return ConstantInt::get(CI1->getContext(), C1V.sdiv(C2V)); 1373 case Instruction::URem: 1374 assert(!CI2->isZero() && "Div by zero handled above"); 1375 return ConstantInt::get(CI1->getContext(), C1V.urem(C2V)); 1376 case Instruction::SRem: 1377 assert(!CI2->isZero() && "Div by zero handled above"); 1378 if (C2V.isAllOnesValue() && C1V.isMinSignedValue()) 1379 return PoisonValue::get(CI1->getType()); // MIN_INT % -1 -> poison 1380 return ConstantInt::get(CI1->getContext(), C1V.srem(C2V)); 1381 case Instruction::And: 1382 return ConstantInt::get(CI1->getContext(), C1V & C2V); 1383 case Instruction::Or: 1384 return ConstantInt::get(CI1->getContext(), C1V | C2V); 1385 case Instruction::Xor: 1386 return ConstantInt::get(CI1->getContext(), C1V ^ C2V); 1387 case Instruction::Shl: 1388 if (C2V.ult(C1V.getBitWidth())) 1389 return ConstantInt::get(CI1->getContext(), C1V.shl(C2V)); 1390 return PoisonValue::get(C1->getType()); // too big shift is poison 1391 case Instruction::LShr: 1392 if (C2V.ult(C1V.getBitWidth())) 1393 return ConstantInt::get(CI1->getContext(), C1V.lshr(C2V)); 1394 return PoisonValue::get(C1->getType()); // too big shift is poison 1395 case Instruction::AShr: 1396 if (C2V.ult(C1V.getBitWidth())) 1397 return ConstantInt::get(CI1->getContext(), C1V.ashr(C2V)); 1398 return PoisonValue::get(C1->getType()); // too big shift is poison 1399 } 1400 } 1401 1402 switch (Opcode) { 1403 case Instruction::SDiv: 1404 case Instruction::UDiv: 1405 case Instruction::URem: 1406 case Instruction::SRem: 1407 case Instruction::LShr: 1408 case Instruction::AShr: 1409 case Instruction::Shl: 1410 if (CI1->isZero()) return C1; 1411 break; 1412 default: 1413 break; 1414 } 1415 } else if (ConstantFP *CFP1 = dyn_cast<ConstantFP>(C1)) { 1416 if (ConstantFP *CFP2 = dyn_cast<ConstantFP>(C2)) { 1417 const APFloat &C1V = CFP1->getValueAPF(); 1418 const APFloat &C2V = CFP2->getValueAPF(); 1419 APFloat C3V = C1V; // copy for modification 1420 switch (Opcode) { 1421 default: 1422 break; 1423 case Instruction::FAdd: 1424 (void)C3V.add(C2V, APFloat::rmNearestTiesToEven); 1425 return ConstantFP::get(C1->getContext(), C3V); 1426 case Instruction::FSub: 1427 (void)C3V.subtract(C2V, APFloat::rmNearestTiesToEven); 1428 return ConstantFP::get(C1->getContext(), C3V); 1429 case Instruction::FMul: 1430 (void)C3V.multiply(C2V, APFloat::rmNearestTiesToEven); 1431 return ConstantFP::get(C1->getContext(), C3V); 1432 case Instruction::FDiv: 1433 (void)C3V.divide(C2V, APFloat::rmNearestTiesToEven); 1434 return ConstantFP::get(C1->getContext(), C3V); 1435 case Instruction::FRem: 1436 (void)C3V.mod(C2V); 1437 return ConstantFP::get(C1->getContext(), C3V); 1438 } 1439 } 1440 } else if (auto *VTy = dyn_cast<VectorType>(C1->getType())) { 1441 // Fast path for splatted constants. 1442 if (Constant *C2Splat = C2->getSplatValue()) { 1443 if (Instruction::isIntDivRem(Opcode) && C2Splat->isNullValue()) 1444 return PoisonValue::get(VTy); 1445 if (Constant *C1Splat = C1->getSplatValue()) { 1446 return ConstantVector::getSplat( 1447 VTy->getElementCount(), 1448 ConstantExpr::get(Opcode, C1Splat, C2Splat)); 1449 } 1450 } 1451 1452 if (auto *FVTy = dyn_cast<FixedVectorType>(VTy)) { 1453 // Fold each element and create a vector constant from those constants. 1454 SmallVector<Constant*, 16> Result; 1455 Type *Ty = IntegerType::get(FVTy->getContext(), 32); 1456 for (unsigned i = 0, e = FVTy->getNumElements(); i != e; ++i) { 1457 Constant *ExtractIdx = ConstantInt::get(Ty, i); 1458 Constant *LHS = ConstantExpr::getExtractElement(C1, ExtractIdx); 1459 Constant *RHS = ConstantExpr::getExtractElement(C2, ExtractIdx); 1460 1461 // If any element of a divisor vector is zero, the whole op is poison. 1462 if (Instruction::isIntDivRem(Opcode) && RHS->isNullValue()) 1463 return PoisonValue::get(VTy); 1464 1465 Result.push_back(ConstantExpr::get(Opcode, LHS, RHS)); 1466 } 1467 1468 return ConstantVector::get(Result); 1469 } 1470 } 1471 1472 if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1)) { 1473 // There are many possible foldings we could do here. We should probably 1474 // at least fold add of a pointer with an integer into the appropriate 1475 // getelementptr. This will improve alias analysis a bit. 1476 1477 // Given ((a + b) + c), if (b + c) folds to something interesting, return 1478 // (a + (b + c)). 1479 if (Instruction::isAssociative(Opcode) && CE1->getOpcode() == Opcode) { 1480 Constant *T = ConstantExpr::get(Opcode, CE1->getOperand(1), C2); 1481 if (!isa<ConstantExpr>(T) || cast<ConstantExpr>(T)->getOpcode() != Opcode) 1482 return ConstantExpr::get(Opcode, CE1->getOperand(0), T); 1483 } 1484 } else if (isa<ConstantExpr>(C2)) { 1485 // If C2 is a constant expr and C1 isn't, flop them around and fold the 1486 // other way if possible. 1487 if (Instruction::isCommutative(Opcode)) 1488 return ConstantFoldBinaryInstruction(Opcode, C2, C1); 1489 } 1490 1491 // i1 can be simplified in many cases. 1492 if (C1->getType()->isIntegerTy(1)) { 1493 switch (Opcode) { 1494 case Instruction::Add: 1495 case Instruction::Sub: 1496 return ConstantExpr::getXor(C1, C2); 1497 case Instruction::Mul: 1498 return ConstantExpr::getAnd(C1, C2); 1499 case Instruction::Shl: 1500 case Instruction::LShr: 1501 case Instruction::AShr: 1502 // We can assume that C2 == 0. If it were one the result would be 1503 // undefined because the shift value is as large as the bitwidth. 1504 return C1; 1505 case Instruction::SDiv: 1506 case Instruction::UDiv: 1507 // We can assume that C2 == 1. If it were zero the result would be 1508 // undefined through division by zero. 1509 return C1; 1510 case Instruction::URem: 1511 case Instruction::SRem: 1512 // We can assume that C2 == 1. If it were zero the result would be 1513 // undefined through division by zero. 1514 return ConstantInt::getFalse(C1->getContext()); 1515 default: 1516 break; 1517 } 1518 } 1519 1520 // We don't know how to fold this. 1521 return nullptr; 1522 } 1523 1524 /// This type is zero-sized if it's an array or structure of zero-sized types. 1525 /// The only leaf zero-sized type is an empty structure. 1526 static bool isMaybeZeroSizedType(Type *Ty) { 1527 if (StructType *STy = dyn_cast<StructType>(Ty)) { 1528 if (STy->isOpaque()) return true; // Can't say. 1529 1530 // If all of elements have zero size, this does too. 1531 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 1532 if (!isMaybeZeroSizedType(STy->getElementType(i))) return false; 1533 return true; 1534 1535 } else if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 1536 return isMaybeZeroSizedType(ATy->getElementType()); 1537 } 1538 return false; 1539 } 1540 1541 /// Compare the two constants as though they were getelementptr indices. 1542 /// This allows coercion of the types to be the same thing. 1543 /// 1544 /// If the two constants are the "same" (after coercion), return 0. If the 1545 /// first is less than the second, return -1, if the second is less than the 1546 /// first, return 1. If the constants are not integral, return -2. 1547 /// 1548 static int IdxCompare(Constant *C1, Constant *C2, Type *ElTy) { 1549 if (C1 == C2) return 0; 1550 1551 // Ok, we found a different index. If they are not ConstantInt, we can't do 1552 // anything with them. 1553 if (!isa<ConstantInt>(C1) || !isa<ConstantInt>(C2)) 1554 return -2; // don't know! 1555 1556 // We cannot compare the indices if they don't fit in an int64_t. 1557 if (cast<ConstantInt>(C1)->getValue().getActiveBits() > 64 || 1558 cast<ConstantInt>(C2)->getValue().getActiveBits() > 64) 1559 return -2; // don't know! 1560 1561 // Ok, we have two differing integer indices. Sign extend them to be the same 1562 // type. 1563 int64_t C1Val = cast<ConstantInt>(C1)->getSExtValue(); 1564 int64_t C2Val = cast<ConstantInt>(C2)->getSExtValue(); 1565 1566 if (C1Val == C2Val) return 0; // They are equal 1567 1568 // If the type being indexed over is really just a zero sized type, there is 1569 // no pointer difference being made here. 1570 if (isMaybeZeroSizedType(ElTy)) 1571 return -2; // dunno. 1572 1573 // If they are really different, now that they are the same type, then we 1574 // found a difference! 1575 if (C1Val < C2Val) 1576 return -1; 1577 else 1578 return 1; 1579 } 1580 1581 /// This function determines if there is anything we can decide about the two 1582 /// constants provided. This doesn't need to handle simple things like 1583 /// ConstantFP comparisons, but should instead handle ConstantExprs. 1584 /// If we can determine that the two constants have a particular relation to 1585 /// each other, we should return the corresponding FCmpInst predicate, 1586 /// otherwise return FCmpInst::BAD_FCMP_PREDICATE. This is used below in 1587 /// ConstantFoldCompareInstruction. 1588 /// 1589 /// To simplify this code we canonicalize the relation so that the first 1590 /// operand is always the most "complex" of the two. We consider ConstantFP 1591 /// to be the simplest, and ConstantExprs to be the most complex. 1592 static FCmpInst::Predicate evaluateFCmpRelation(Constant *V1, Constant *V2) { 1593 assert(V1->getType() == V2->getType() && 1594 "Cannot compare values of different types!"); 1595 1596 // We do not know if a constant expression will evaluate to a number or NaN. 1597 // Therefore, we can only say that the relation is unordered or equal. 1598 if (V1 == V2) return FCmpInst::FCMP_UEQ; 1599 1600 if (!isa<ConstantExpr>(V1)) { 1601 if (!isa<ConstantExpr>(V2)) { 1602 // Simple case, use the standard constant folder. 1603 ConstantInt *R = nullptr; 1604 R = dyn_cast<ConstantInt>( 1605 ConstantExpr::getFCmp(FCmpInst::FCMP_OEQ, V1, V2)); 1606 if (R && !R->isZero()) 1607 return FCmpInst::FCMP_OEQ; 1608 R = dyn_cast<ConstantInt>( 1609 ConstantExpr::getFCmp(FCmpInst::FCMP_OLT, V1, V2)); 1610 if (R && !R->isZero()) 1611 return FCmpInst::FCMP_OLT; 1612 R = dyn_cast<ConstantInt>( 1613 ConstantExpr::getFCmp(FCmpInst::FCMP_OGT, V1, V2)); 1614 if (R && !R->isZero()) 1615 return FCmpInst::FCMP_OGT; 1616 1617 // Nothing more we can do 1618 return FCmpInst::BAD_FCMP_PREDICATE; 1619 } 1620 1621 // If the first operand is simple and second is ConstantExpr, swap operands. 1622 FCmpInst::Predicate SwappedRelation = evaluateFCmpRelation(V2, V1); 1623 if (SwappedRelation != FCmpInst::BAD_FCMP_PREDICATE) 1624 return FCmpInst::getSwappedPredicate(SwappedRelation); 1625 } else { 1626 // Ok, the LHS is known to be a constantexpr. The RHS can be any of a 1627 // constantexpr or a simple constant. 1628 ConstantExpr *CE1 = cast<ConstantExpr>(V1); 1629 switch (CE1->getOpcode()) { 1630 case Instruction::FPTrunc: 1631 case Instruction::FPExt: 1632 case Instruction::UIToFP: 1633 case Instruction::SIToFP: 1634 // We might be able to do something with these but we don't right now. 1635 break; 1636 default: 1637 break; 1638 } 1639 } 1640 // There are MANY other foldings that we could perform here. They will 1641 // probably be added on demand, as they seem needed. 1642 return FCmpInst::BAD_FCMP_PREDICATE; 1643 } 1644 1645 static ICmpInst::Predicate areGlobalsPotentiallyEqual(const GlobalValue *GV1, 1646 const GlobalValue *GV2) { 1647 auto isGlobalUnsafeForEquality = [](const GlobalValue *GV) { 1648 if (GV->isInterposable() || GV->hasGlobalUnnamedAddr()) 1649 return true; 1650 if (const auto *GVar = dyn_cast<GlobalVariable>(GV)) { 1651 Type *Ty = GVar->getValueType(); 1652 // A global with opaque type might end up being zero sized. 1653 if (!Ty->isSized()) 1654 return true; 1655 // A global with an empty type might lie at the address of any other 1656 // global. 1657 if (Ty->isEmptyTy()) 1658 return true; 1659 } 1660 return false; 1661 }; 1662 // Don't try to decide equality of aliases. 1663 if (!isa<GlobalAlias>(GV1) && !isa<GlobalAlias>(GV2)) 1664 if (!isGlobalUnsafeForEquality(GV1) && !isGlobalUnsafeForEquality(GV2)) 1665 return ICmpInst::ICMP_NE; 1666 return ICmpInst::BAD_ICMP_PREDICATE; 1667 } 1668 1669 /// This function determines if there is anything we can decide about the two 1670 /// constants provided. This doesn't need to handle simple things like integer 1671 /// comparisons, but should instead handle ConstantExprs and GlobalValues. 1672 /// If we can determine that the two constants have a particular relation to 1673 /// each other, we should return the corresponding ICmp predicate, otherwise 1674 /// return ICmpInst::BAD_ICMP_PREDICATE. 1675 /// 1676 /// To simplify this code we canonicalize the relation so that the first 1677 /// operand is always the most "complex" of the two. We consider simple 1678 /// constants (like ConstantInt) to be the simplest, followed by 1679 /// GlobalValues, followed by ConstantExpr's (the most complex). 1680 /// 1681 static ICmpInst::Predicate evaluateICmpRelation(Constant *V1, Constant *V2, 1682 bool isSigned) { 1683 assert(V1->getType() == V2->getType() && 1684 "Cannot compare different types of values!"); 1685 if (V1 == V2) return ICmpInst::ICMP_EQ; 1686 1687 if (!isa<ConstantExpr>(V1) && !isa<GlobalValue>(V1) && 1688 !isa<BlockAddress>(V1)) { 1689 if (!isa<GlobalValue>(V2) && !isa<ConstantExpr>(V2) && 1690 !isa<BlockAddress>(V2)) { 1691 // We distilled this down to a simple case, use the standard constant 1692 // folder. 1693 ConstantInt *R = nullptr; 1694 ICmpInst::Predicate pred = ICmpInst::ICMP_EQ; 1695 R = dyn_cast<ConstantInt>(ConstantExpr::getICmp(pred, V1, V2)); 1696 if (R && !R->isZero()) 1697 return pred; 1698 pred = isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; 1699 R = dyn_cast<ConstantInt>(ConstantExpr::getICmp(pred, V1, V2)); 1700 if (R && !R->isZero()) 1701 return pred; 1702 pred = isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; 1703 R = dyn_cast<ConstantInt>(ConstantExpr::getICmp(pred, V1, V2)); 1704 if (R && !R->isZero()) 1705 return pred; 1706 1707 // If we couldn't figure it out, bail. 1708 return ICmpInst::BAD_ICMP_PREDICATE; 1709 } 1710 1711 // If the first operand is simple, swap operands. 1712 ICmpInst::Predicate SwappedRelation = 1713 evaluateICmpRelation(V2, V1, isSigned); 1714 if (SwappedRelation != ICmpInst::BAD_ICMP_PREDICATE) 1715 return ICmpInst::getSwappedPredicate(SwappedRelation); 1716 1717 } else if (const GlobalValue *GV = dyn_cast<GlobalValue>(V1)) { 1718 if (isa<ConstantExpr>(V2)) { // Swap as necessary. 1719 ICmpInst::Predicate SwappedRelation = 1720 evaluateICmpRelation(V2, V1, isSigned); 1721 if (SwappedRelation != ICmpInst::BAD_ICMP_PREDICATE) 1722 return ICmpInst::getSwappedPredicate(SwappedRelation); 1723 return ICmpInst::BAD_ICMP_PREDICATE; 1724 } 1725 1726 // Now we know that the RHS is a GlobalValue, BlockAddress or simple 1727 // constant (which, since the types must match, means that it's a 1728 // ConstantPointerNull). 1729 if (const GlobalValue *GV2 = dyn_cast<GlobalValue>(V2)) { 1730 return areGlobalsPotentiallyEqual(GV, GV2); 1731 } else if (isa<BlockAddress>(V2)) { 1732 return ICmpInst::ICMP_NE; // Globals never equal labels. 1733 } else { 1734 assert(isa<ConstantPointerNull>(V2) && "Canonicalization guarantee!"); 1735 // GlobalVals can never be null unless they have external weak linkage. 1736 // We don't try to evaluate aliases here. 1737 // NOTE: We should not be doing this constant folding if null pointer 1738 // is considered valid for the function. But currently there is no way to 1739 // query it from the Constant type. 1740 if (!GV->hasExternalWeakLinkage() && !isa<GlobalAlias>(GV) && 1741 !NullPointerIsDefined(nullptr /* F */, 1742 GV->getType()->getAddressSpace())) 1743 return ICmpInst::ICMP_NE; 1744 } 1745 } else if (const BlockAddress *BA = dyn_cast<BlockAddress>(V1)) { 1746 if (isa<ConstantExpr>(V2)) { // Swap as necessary. 1747 ICmpInst::Predicate SwappedRelation = 1748 evaluateICmpRelation(V2, V1, isSigned); 1749 if (SwappedRelation != ICmpInst::BAD_ICMP_PREDICATE) 1750 return ICmpInst::getSwappedPredicate(SwappedRelation); 1751 return ICmpInst::BAD_ICMP_PREDICATE; 1752 } 1753 1754 // Now we know that the RHS is a GlobalValue, BlockAddress or simple 1755 // constant (which, since the types must match, means that it is a 1756 // ConstantPointerNull). 1757 if (const BlockAddress *BA2 = dyn_cast<BlockAddress>(V2)) { 1758 // Block address in another function can't equal this one, but block 1759 // addresses in the current function might be the same if blocks are 1760 // empty. 1761 if (BA2->getFunction() != BA->getFunction()) 1762 return ICmpInst::ICMP_NE; 1763 } else { 1764 // Block addresses aren't null, don't equal the address of globals. 1765 assert((isa<ConstantPointerNull>(V2) || isa<GlobalValue>(V2)) && 1766 "Canonicalization guarantee!"); 1767 return ICmpInst::ICMP_NE; 1768 } 1769 } else { 1770 // Ok, the LHS is known to be a constantexpr. The RHS can be any of a 1771 // constantexpr, a global, block address, or a simple constant. 1772 ConstantExpr *CE1 = cast<ConstantExpr>(V1); 1773 Constant *CE1Op0 = CE1->getOperand(0); 1774 1775 switch (CE1->getOpcode()) { 1776 case Instruction::Trunc: 1777 case Instruction::FPTrunc: 1778 case Instruction::FPExt: 1779 case Instruction::FPToUI: 1780 case Instruction::FPToSI: 1781 break; // We can't evaluate floating point casts or truncations. 1782 1783 case Instruction::BitCast: 1784 // If this is a global value cast, check to see if the RHS is also a 1785 // GlobalValue. 1786 if (const GlobalValue *GV = dyn_cast<GlobalValue>(CE1Op0)) 1787 if (const GlobalValue *GV2 = dyn_cast<GlobalValue>(V2)) 1788 return areGlobalsPotentiallyEqual(GV, GV2); 1789 LLVM_FALLTHROUGH; 1790 case Instruction::UIToFP: 1791 case Instruction::SIToFP: 1792 case Instruction::ZExt: 1793 case Instruction::SExt: 1794 // We can't evaluate floating point casts or truncations. 1795 if (CE1Op0->getType()->isFPOrFPVectorTy()) 1796 break; 1797 1798 // If the cast is not actually changing bits, and the second operand is a 1799 // null pointer, do the comparison with the pre-casted value. 1800 if (V2->isNullValue() && CE1->getType()->isIntOrPtrTy()) { 1801 if (CE1->getOpcode() == Instruction::ZExt) isSigned = false; 1802 if (CE1->getOpcode() == Instruction::SExt) isSigned = true; 1803 return evaluateICmpRelation(CE1Op0, 1804 Constant::getNullValue(CE1Op0->getType()), 1805 isSigned); 1806 } 1807 break; 1808 1809 case Instruction::GetElementPtr: { 1810 GEPOperator *CE1GEP = cast<GEPOperator>(CE1); 1811 // Ok, since this is a getelementptr, we know that the constant has a 1812 // pointer type. Check the various cases. 1813 if (isa<ConstantPointerNull>(V2)) { 1814 // If we are comparing a GEP to a null pointer, check to see if the base 1815 // of the GEP equals the null pointer. 1816 if (const GlobalValue *GV = dyn_cast<GlobalValue>(CE1Op0)) { 1817 if (GV->hasExternalWeakLinkage()) 1818 // Weak linkage GVals could be zero or not. We're comparing that 1819 // to null pointer so its greater-or-equal 1820 return isSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE; 1821 else 1822 // If its not weak linkage, the GVal must have a non-zero address 1823 // so the result is greater-than 1824 return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; 1825 } else if (isa<ConstantPointerNull>(CE1Op0)) { 1826 // If we are indexing from a null pointer, check to see if we have any 1827 // non-zero indices. 1828 for (unsigned i = 1, e = CE1->getNumOperands(); i != e; ++i) 1829 if (!CE1->getOperand(i)->isNullValue()) 1830 // Offsetting from null, must not be equal. 1831 return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; 1832 // Only zero indexes from null, must still be zero. 1833 return ICmpInst::ICMP_EQ; 1834 } 1835 // Otherwise, we can't really say if the first operand is null or not. 1836 } else if (const GlobalValue *GV2 = dyn_cast<GlobalValue>(V2)) { 1837 if (isa<ConstantPointerNull>(CE1Op0)) { 1838 if (GV2->hasExternalWeakLinkage()) 1839 // Weak linkage GVals could be zero or not. We're comparing it to 1840 // a null pointer, so its less-or-equal 1841 return isSigned ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; 1842 else 1843 // If its not weak linkage, the GVal must have a non-zero address 1844 // so the result is less-than 1845 return isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; 1846 } else if (const GlobalValue *GV = dyn_cast<GlobalValue>(CE1Op0)) { 1847 if (GV == GV2) { 1848 // If this is a getelementptr of the same global, then it must be 1849 // different. Because the types must match, the getelementptr could 1850 // only have at most one index, and because we fold getelementptr's 1851 // with a single zero index, it must be nonzero. 1852 assert(CE1->getNumOperands() == 2 && 1853 !CE1->getOperand(1)->isNullValue() && 1854 "Surprising getelementptr!"); 1855 return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; 1856 } else { 1857 if (CE1GEP->hasAllZeroIndices()) 1858 return areGlobalsPotentiallyEqual(GV, GV2); 1859 return ICmpInst::BAD_ICMP_PREDICATE; 1860 } 1861 } 1862 } else { 1863 ConstantExpr *CE2 = cast<ConstantExpr>(V2); 1864 Constant *CE2Op0 = CE2->getOperand(0); 1865 1866 // There are MANY other foldings that we could perform here. They will 1867 // probably be added on demand, as they seem needed. 1868 switch (CE2->getOpcode()) { 1869 default: break; 1870 case Instruction::GetElementPtr: 1871 // By far the most common case to handle is when the base pointers are 1872 // obviously to the same global. 1873 if (isa<GlobalValue>(CE1Op0) && isa<GlobalValue>(CE2Op0)) { 1874 // Don't know relative ordering, but check for inequality. 1875 if (CE1Op0 != CE2Op0) { 1876 GEPOperator *CE2GEP = cast<GEPOperator>(CE2); 1877 if (CE1GEP->hasAllZeroIndices() && CE2GEP->hasAllZeroIndices()) 1878 return areGlobalsPotentiallyEqual(cast<GlobalValue>(CE1Op0), 1879 cast<GlobalValue>(CE2Op0)); 1880 return ICmpInst::BAD_ICMP_PREDICATE; 1881 } 1882 // Ok, we know that both getelementptr instructions are based on the 1883 // same global. From this, we can precisely determine the relative 1884 // ordering of the resultant pointers. 1885 unsigned i = 1; 1886 1887 // The logic below assumes that the result of the comparison 1888 // can be determined by finding the first index that differs. 1889 // This doesn't work if there is over-indexing in any 1890 // subsequent indices, so check for that case first. 1891 if (!CE1->isGEPWithNoNotionalOverIndexing() || 1892 !CE2->isGEPWithNoNotionalOverIndexing()) 1893 return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal. 1894 1895 // Compare all of the operands the GEP's have in common. 1896 gep_type_iterator GTI = gep_type_begin(CE1); 1897 for (;i != CE1->getNumOperands() && i != CE2->getNumOperands(); 1898 ++i, ++GTI) 1899 switch (IdxCompare(CE1->getOperand(i), 1900 CE2->getOperand(i), GTI.getIndexedType())) { 1901 case -1: return isSigned ? ICmpInst::ICMP_SLT:ICmpInst::ICMP_ULT; 1902 case 1: return isSigned ? ICmpInst::ICMP_SGT:ICmpInst::ICMP_UGT; 1903 case -2: return ICmpInst::BAD_ICMP_PREDICATE; 1904 } 1905 1906 // Ok, we ran out of things they have in common. If any leftovers 1907 // are non-zero then we have a difference, otherwise we are equal. 1908 for (; i < CE1->getNumOperands(); ++i) 1909 if (!CE1->getOperand(i)->isNullValue()) { 1910 if (isa<ConstantInt>(CE1->getOperand(i))) 1911 return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; 1912 else 1913 return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal. 1914 } 1915 1916 for (; i < CE2->getNumOperands(); ++i) 1917 if (!CE2->getOperand(i)->isNullValue()) { 1918 if (isa<ConstantInt>(CE2->getOperand(i))) 1919 return isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; 1920 else 1921 return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal. 1922 } 1923 return ICmpInst::ICMP_EQ; 1924 } 1925 } 1926 } 1927 break; 1928 } 1929 default: 1930 break; 1931 } 1932 } 1933 1934 return ICmpInst::BAD_ICMP_PREDICATE; 1935 } 1936 1937 Constant *llvm::ConstantFoldCompareInstruction(unsigned short pred, 1938 Constant *C1, Constant *C2) { 1939 Type *ResultTy; 1940 if (VectorType *VT = dyn_cast<VectorType>(C1->getType())) 1941 ResultTy = VectorType::get(Type::getInt1Ty(C1->getContext()), 1942 VT->getElementCount()); 1943 else 1944 ResultTy = Type::getInt1Ty(C1->getContext()); 1945 1946 // Fold FCMP_FALSE/FCMP_TRUE unconditionally. 1947 if (pred == FCmpInst::FCMP_FALSE) 1948 return Constant::getNullValue(ResultTy); 1949 1950 if (pred == FCmpInst::FCMP_TRUE) 1951 return Constant::getAllOnesValue(ResultTy); 1952 1953 // Handle some degenerate cases first 1954 if (isa<PoisonValue>(C1) || isa<PoisonValue>(C2)) 1955 return PoisonValue::get(ResultTy); 1956 1957 if (isa<UndefValue>(C1) || isa<UndefValue>(C2)) { 1958 CmpInst::Predicate Predicate = CmpInst::Predicate(pred); 1959 bool isIntegerPredicate = ICmpInst::isIntPredicate(Predicate); 1960 // For EQ and NE, we can always pick a value for the undef to make the 1961 // predicate pass or fail, so we can return undef. 1962 // Also, if both operands are undef, we can return undef for int comparison. 1963 if (ICmpInst::isEquality(Predicate) || (isIntegerPredicate && C1 == C2)) 1964 return UndefValue::get(ResultTy); 1965 1966 // Otherwise, for integer compare, pick the same value as the non-undef 1967 // operand, and fold it to true or false. 1968 if (isIntegerPredicate) 1969 return ConstantInt::get(ResultTy, CmpInst::isTrueWhenEqual(Predicate)); 1970 1971 // Choosing NaN for the undef will always make unordered comparison succeed 1972 // and ordered comparison fails. 1973 return ConstantInt::get(ResultTy, CmpInst::isUnordered(Predicate)); 1974 } 1975 1976 // icmp eq/ne(null,GV) -> false/true 1977 if (C1->isNullValue()) { 1978 if (const GlobalValue *GV = dyn_cast<GlobalValue>(C2)) 1979 // Don't try to evaluate aliases. External weak GV can be null. 1980 if (!isa<GlobalAlias>(GV) && !GV->hasExternalWeakLinkage() && 1981 !NullPointerIsDefined(nullptr /* F */, 1982 GV->getType()->getAddressSpace())) { 1983 if (pred == ICmpInst::ICMP_EQ) 1984 return ConstantInt::getFalse(C1->getContext()); 1985 else if (pred == ICmpInst::ICMP_NE) 1986 return ConstantInt::getTrue(C1->getContext()); 1987 } 1988 // icmp eq/ne(GV,null) -> false/true 1989 } else if (C2->isNullValue()) { 1990 if (const GlobalValue *GV = dyn_cast<GlobalValue>(C1)) 1991 // Don't try to evaluate aliases. External weak GV can be null. 1992 if (!isa<GlobalAlias>(GV) && !GV->hasExternalWeakLinkage() && 1993 !NullPointerIsDefined(nullptr /* F */, 1994 GV->getType()->getAddressSpace())) { 1995 if (pred == ICmpInst::ICMP_EQ) 1996 return ConstantInt::getFalse(C1->getContext()); 1997 else if (pred == ICmpInst::ICMP_NE) 1998 return ConstantInt::getTrue(C1->getContext()); 1999 } 2000 } 2001 2002 // If the comparison is a comparison between two i1's, simplify it. 2003 if (C1->getType()->isIntegerTy(1)) { 2004 switch(pred) { 2005 case ICmpInst::ICMP_EQ: 2006 if (isa<ConstantInt>(C2)) 2007 return ConstantExpr::getXor(C1, ConstantExpr::getNot(C2)); 2008 return ConstantExpr::getXor(ConstantExpr::getNot(C1), C2); 2009 case ICmpInst::ICMP_NE: 2010 return ConstantExpr::getXor(C1, C2); 2011 default: 2012 break; 2013 } 2014 } 2015 2016 if (isa<ConstantInt>(C1) && isa<ConstantInt>(C2)) { 2017 const APInt &V1 = cast<ConstantInt>(C1)->getValue(); 2018 const APInt &V2 = cast<ConstantInt>(C2)->getValue(); 2019 switch (pred) { 2020 default: llvm_unreachable("Invalid ICmp Predicate"); 2021 case ICmpInst::ICMP_EQ: return ConstantInt::get(ResultTy, V1 == V2); 2022 case ICmpInst::ICMP_NE: return ConstantInt::get(ResultTy, V1 != V2); 2023 case ICmpInst::ICMP_SLT: return ConstantInt::get(ResultTy, V1.slt(V2)); 2024 case ICmpInst::ICMP_SGT: return ConstantInt::get(ResultTy, V1.sgt(V2)); 2025 case ICmpInst::ICMP_SLE: return ConstantInt::get(ResultTy, V1.sle(V2)); 2026 case ICmpInst::ICMP_SGE: return ConstantInt::get(ResultTy, V1.sge(V2)); 2027 case ICmpInst::ICMP_ULT: return ConstantInt::get(ResultTy, V1.ult(V2)); 2028 case ICmpInst::ICMP_UGT: return ConstantInt::get(ResultTy, V1.ugt(V2)); 2029 case ICmpInst::ICMP_ULE: return ConstantInt::get(ResultTy, V1.ule(V2)); 2030 case ICmpInst::ICMP_UGE: return ConstantInt::get(ResultTy, V1.uge(V2)); 2031 } 2032 } else if (isa<ConstantFP>(C1) && isa<ConstantFP>(C2)) { 2033 const APFloat &C1V = cast<ConstantFP>(C1)->getValueAPF(); 2034 const APFloat &C2V = cast<ConstantFP>(C2)->getValueAPF(); 2035 APFloat::cmpResult R = C1V.compare(C2V); 2036 switch (pred) { 2037 default: llvm_unreachable("Invalid FCmp Predicate"); 2038 case FCmpInst::FCMP_FALSE: return Constant::getNullValue(ResultTy); 2039 case FCmpInst::FCMP_TRUE: return Constant::getAllOnesValue(ResultTy); 2040 case FCmpInst::FCMP_UNO: 2041 return ConstantInt::get(ResultTy, R==APFloat::cmpUnordered); 2042 case FCmpInst::FCMP_ORD: 2043 return ConstantInt::get(ResultTy, R!=APFloat::cmpUnordered); 2044 case FCmpInst::FCMP_UEQ: 2045 return ConstantInt::get(ResultTy, R==APFloat::cmpUnordered || 2046 R==APFloat::cmpEqual); 2047 case FCmpInst::FCMP_OEQ: 2048 return ConstantInt::get(ResultTy, R==APFloat::cmpEqual); 2049 case FCmpInst::FCMP_UNE: 2050 return ConstantInt::get(ResultTy, R!=APFloat::cmpEqual); 2051 case FCmpInst::FCMP_ONE: 2052 return ConstantInt::get(ResultTy, R==APFloat::cmpLessThan || 2053 R==APFloat::cmpGreaterThan); 2054 case FCmpInst::FCMP_ULT: 2055 return ConstantInt::get(ResultTy, R==APFloat::cmpUnordered || 2056 R==APFloat::cmpLessThan); 2057 case FCmpInst::FCMP_OLT: 2058 return ConstantInt::get(ResultTy, R==APFloat::cmpLessThan); 2059 case FCmpInst::FCMP_UGT: 2060 return ConstantInt::get(ResultTy, R==APFloat::cmpUnordered || 2061 R==APFloat::cmpGreaterThan); 2062 case FCmpInst::FCMP_OGT: 2063 return ConstantInt::get(ResultTy, R==APFloat::cmpGreaterThan); 2064 case FCmpInst::FCMP_ULE: 2065 return ConstantInt::get(ResultTy, R!=APFloat::cmpGreaterThan); 2066 case FCmpInst::FCMP_OLE: 2067 return ConstantInt::get(ResultTy, R==APFloat::cmpLessThan || 2068 R==APFloat::cmpEqual); 2069 case FCmpInst::FCMP_UGE: 2070 return ConstantInt::get(ResultTy, R!=APFloat::cmpLessThan); 2071 case FCmpInst::FCMP_OGE: 2072 return ConstantInt::get(ResultTy, R==APFloat::cmpGreaterThan || 2073 R==APFloat::cmpEqual); 2074 } 2075 } else if (auto *C1VTy = dyn_cast<VectorType>(C1->getType())) { 2076 2077 // Fast path for splatted constants. 2078 if (Constant *C1Splat = C1->getSplatValue()) 2079 if (Constant *C2Splat = C2->getSplatValue()) 2080 return ConstantVector::getSplat( 2081 C1VTy->getElementCount(), 2082 ConstantExpr::getCompare(pred, C1Splat, C2Splat)); 2083 2084 // Do not iterate on scalable vector. The number of elements is unknown at 2085 // compile-time. 2086 if (isa<ScalableVectorType>(C1VTy)) 2087 return nullptr; 2088 2089 // If we can constant fold the comparison of each element, constant fold 2090 // the whole vector comparison. 2091 SmallVector<Constant*, 4> ResElts; 2092 Type *Ty = IntegerType::get(C1->getContext(), 32); 2093 // Compare the elements, producing an i1 result or constant expr. 2094 for (unsigned I = 0, E = C1VTy->getElementCount().getKnownMinValue(); 2095 I != E; ++I) { 2096 Constant *C1E = 2097 ConstantExpr::getExtractElement(C1, ConstantInt::get(Ty, I)); 2098 Constant *C2E = 2099 ConstantExpr::getExtractElement(C2, ConstantInt::get(Ty, I)); 2100 2101 ResElts.push_back(ConstantExpr::getCompare(pred, C1E, C2E)); 2102 } 2103 2104 return ConstantVector::get(ResElts); 2105 } 2106 2107 if (C1->getType()->isFloatingPointTy() && 2108 // Only call evaluateFCmpRelation if we have a constant expr to avoid 2109 // infinite recursive loop 2110 (isa<ConstantExpr>(C1) || isa<ConstantExpr>(C2))) { 2111 int Result = -1; // -1 = unknown, 0 = known false, 1 = known true. 2112 switch (evaluateFCmpRelation(C1, C2)) { 2113 default: llvm_unreachable("Unknown relation!"); 2114 case FCmpInst::FCMP_UNO: 2115 case FCmpInst::FCMP_ORD: 2116 case FCmpInst::FCMP_UNE: 2117 case FCmpInst::FCMP_ULT: 2118 case FCmpInst::FCMP_UGT: 2119 case FCmpInst::FCMP_ULE: 2120 case FCmpInst::FCMP_UGE: 2121 case FCmpInst::FCMP_TRUE: 2122 case FCmpInst::FCMP_FALSE: 2123 case FCmpInst::BAD_FCMP_PREDICATE: 2124 break; // Couldn't determine anything about these constants. 2125 case FCmpInst::FCMP_OEQ: // We know that C1 == C2 2126 Result = (pred == FCmpInst::FCMP_UEQ || pred == FCmpInst::FCMP_OEQ || 2127 pred == FCmpInst::FCMP_ULE || pred == FCmpInst::FCMP_OLE || 2128 pred == FCmpInst::FCMP_UGE || pred == FCmpInst::FCMP_OGE); 2129 break; 2130 case FCmpInst::FCMP_OLT: // We know that C1 < C2 2131 Result = (pred == FCmpInst::FCMP_UNE || pred == FCmpInst::FCMP_ONE || 2132 pred == FCmpInst::FCMP_ULT || pred == FCmpInst::FCMP_OLT || 2133 pred == FCmpInst::FCMP_ULE || pred == FCmpInst::FCMP_OLE); 2134 break; 2135 case FCmpInst::FCMP_OGT: // We know that C1 > C2 2136 Result = (pred == FCmpInst::FCMP_UNE || pred == FCmpInst::FCMP_ONE || 2137 pred == FCmpInst::FCMP_UGT || pred == FCmpInst::FCMP_OGT || 2138 pred == FCmpInst::FCMP_UGE || pred == FCmpInst::FCMP_OGE); 2139 break; 2140 case FCmpInst::FCMP_OLE: // We know that C1 <= C2 2141 // We can only partially decide this relation. 2142 if (pred == FCmpInst::FCMP_UGT || pred == FCmpInst::FCMP_OGT) 2143 Result = 0; 2144 else if (pred == FCmpInst::FCMP_ULT || pred == FCmpInst::FCMP_OLT) 2145 Result = 1; 2146 break; 2147 case FCmpInst::FCMP_OGE: // We known that C1 >= C2 2148 // We can only partially decide this relation. 2149 if (pred == FCmpInst::FCMP_ULT || pred == FCmpInst::FCMP_OLT) 2150 Result = 0; 2151 else if (pred == FCmpInst::FCMP_UGT || pred == FCmpInst::FCMP_OGT) 2152 Result = 1; 2153 break; 2154 case FCmpInst::FCMP_ONE: // We know that C1 != C2 2155 // We can only partially decide this relation. 2156 if (pred == FCmpInst::FCMP_OEQ || pred == FCmpInst::FCMP_UEQ) 2157 Result = 0; 2158 else if (pred == FCmpInst::FCMP_ONE || pred == FCmpInst::FCMP_UNE) 2159 Result = 1; 2160 break; 2161 case FCmpInst::FCMP_UEQ: // We know that C1 == C2 || isUnordered(C1, C2). 2162 // We can only partially decide this relation. 2163 if (pred == FCmpInst::FCMP_ONE) 2164 Result = 0; 2165 else if (pred == FCmpInst::FCMP_UEQ) 2166 Result = 1; 2167 break; 2168 } 2169 2170 // If we evaluated the result, return it now. 2171 if (Result != -1) 2172 return ConstantInt::get(ResultTy, Result); 2173 2174 } else { 2175 // Evaluate the relation between the two constants, per the predicate. 2176 int Result = -1; // -1 = unknown, 0 = known false, 1 = known true. 2177 switch (evaluateICmpRelation(C1, C2, 2178 CmpInst::isSigned((CmpInst::Predicate)pred))) { 2179 default: llvm_unreachable("Unknown relational!"); 2180 case ICmpInst::BAD_ICMP_PREDICATE: 2181 break; // Couldn't determine anything about these constants. 2182 case ICmpInst::ICMP_EQ: // We know the constants are equal! 2183 // If we know the constants are equal, we can decide the result of this 2184 // computation precisely. 2185 Result = ICmpInst::isTrueWhenEqual((ICmpInst::Predicate)pred); 2186 break; 2187 case ICmpInst::ICMP_ULT: 2188 switch (pred) { 2189 case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_ULE: 2190 Result = 1; break; 2191 case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_UGE: 2192 Result = 0; break; 2193 } 2194 break; 2195 case ICmpInst::ICMP_SLT: 2196 switch (pred) { 2197 case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_SLE: 2198 Result = 1; break; 2199 case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_SGE: 2200 Result = 0; break; 2201 } 2202 break; 2203 case ICmpInst::ICMP_UGT: 2204 switch (pred) { 2205 case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_UGE: 2206 Result = 1; break; 2207 case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_ULE: 2208 Result = 0; break; 2209 } 2210 break; 2211 case ICmpInst::ICMP_SGT: 2212 switch (pred) { 2213 case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_SGE: 2214 Result = 1; break; 2215 case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_SLE: 2216 Result = 0; break; 2217 } 2218 break; 2219 case ICmpInst::ICMP_ULE: 2220 if (pred == ICmpInst::ICMP_UGT) Result = 0; 2221 if (pred == ICmpInst::ICMP_ULT || pred == ICmpInst::ICMP_ULE) Result = 1; 2222 break; 2223 case ICmpInst::ICMP_SLE: 2224 if (pred == ICmpInst::ICMP_SGT) Result = 0; 2225 if (pred == ICmpInst::ICMP_SLT || pred == ICmpInst::ICMP_SLE) Result = 1; 2226 break; 2227 case ICmpInst::ICMP_UGE: 2228 if (pred == ICmpInst::ICMP_ULT) Result = 0; 2229 if (pred == ICmpInst::ICMP_UGT || pred == ICmpInst::ICMP_UGE) Result = 1; 2230 break; 2231 case ICmpInst::ICMP_SGE: 2232 if (pred == ICmpInst::ICMP_SLT) Result = 0; 2233 if (pred == ICmpInst::ICMP_SGT || pred == ICmpInst::ICMP_SGE) Result = 1; 2234 break; 2235 case ICmpInst::ICMP_NE: 2236 if (pred == ICmpInst::ICMP_EQ) Result = 0; 2237 if (pred == ICmpInst::ICMP_NE) Result = 1; 2238 break; 2239 } 2240 2241 // If we evaluated the result, return it now. 2242 if (Result != -1) 2243 return ConstantInt::get(ResultTy, Result); 2244 2245 // If the right hand side is a bitcast, try using its inverse to simplify 2246 // it by moving it to the left hand side. We can't do this if it would turn 2247 // a vector compare into a scalar compare or visa versa, or if it would turn 2248 // the operands into FP values. 2249 if (ConstantExpr *CE2 = dyn_cast<ConstantExpr>(C2)) { 2250 Constant *CE2Op0 = CE2->getOperand(0); 2251 if (CE2->getOpcode() == Instruction::BitCast && 2252 CE2->getType()->isVectorTy() == CE2Op0->getType()->isVectorTy() && 2253 !CE2Op0->getType()->isFPOrFPVectorTy()) { 2254 Constant *Inverse = ConstantExpr::getBitCast(C1, CE2Op0->getType()); 2255 return ConstantExpr::getICmp(pred, Inverse, CE2Op0); 2256 } 2257 } 2258 2259 // If the left hand side is an extension, try eliminating it. 2260 if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1)) { 2261 if ((CE1->getOpcode() == Instruction::SExt && 2262 ICmpInst::isSigned((ICmpInst::Predicate)pred)) || 2263 (CE1->getOpcode() == Instruction::ZExt && 2264 !ICmpInst::isSigned((ICmpInst::Predicate)pred))){ 2265 Constant *CE1Op0 = CE1->getOperand(0); 2266 Constant *CE1Inverse = ConstantExpr::getTrunc(CE1, CE1Op0->getType()); 2267 if (CE1Inverse == CE1Op0) { 2268 // Check whether we can safely truncate the right hand side. 2269 Constant *C2Inverse = ConstantExpr::getTrunc(C2, CE1Op0->getType()); 2270 if (ConstantExpr::getCast(CE1->getOpcode(), C2Inverse, 2271 C2->getType()) == C2) 2272 return ConstantExpr::getICmp(pred, CE1Inverse, C2Inverse); 2273 } 2274 } 2275 } 2276 2277 if ((!isa<ConstantExpr>(C1) && isa<ConstantExpr>(C2)) || 2278 (C1->isNullValue() && !C2->isNullValue())) { 2279 // If C2 is a constant expr and C1 isn't, flip them around and fold the 2280 // other way if possible. 2281 // Also, if C1 is null and C2 isn't, flip them around. 2282 pred = ICmpInst::getSwappedPredicate((ICmpInst::Predicate)pred); 2283 return ConstantExpr::getICmp(pred, C2, C1); 2284 } 2285 } 2286 return nullptr; 2287 } 2288 2289 /// Test whether the given sequence of *normalized* indices is "inbounds". 2290 template<typename IndexTy> 2291 static bool isInBoundsIndices(ArrayRef<IndexTy> Idxs) { 2292 // No indices means nothing that could be out of bounds. 2293 if (Idxs.empty()) return true; 2294 2295 // If the first index is zero, it's in bounds. 2296 if (cast<Constant>(Idxs[0])->isNullValue()) return true; 2297 2298 // If the first index is one and all the rest are zero, it's in bounds, 2299 // by the one-past-the-end rule. 2300 if (auto *CI = dyn_cast<ConstantInt>(Idxs[0])) { 2301 if (!CI->isOne()) 2302 return false; 2303 } else { 2304 auto *CV = cast<ConstantDataVector>(Idxs[0]); 2305 CI = dyn_cast_or_null<ConstantInt>(CV->getSplatValue()); 2306 if (!CI || !CI->isOne()) 2307 return false; 2308 } 2309 2310 for (unsigned i = 1, e = Idxs.size(); i != e; ++i) 2311 if (!cast<Constant>(Idxs[i])->isNullValue()) 2312 return false; 2313 return true; 2314 } 2315 2316 /// Test whether a given ConstantInt is in-range for a SequentialType. 2317 static bool isIndexInRangeOfArrayType(uint64_t NumElements, 2318 const ConstantInt *CI) { 2319 // We cannot bounds check the index if it doesn't fit in an int64_t. 2320 if (CI->getValue().getMinSignedBits() > 64) 2321 return false; 2322 2323 // A negative index or an index past the end of our sequential type is 2324 // considered out-of-range. 2325 int64_t IndexVal = CI->getSExtValue(); 2326 if (IndexVal < 0 || (NumElements > 0 && (uint64_t)IndexVal >= NumElements)) 2327 return false; 2328 2329 // Otherwise, it is in-range. 2330 return true; 2331 } 2332 2333 Constant *llvm::ConstantFoldGetElementPtr(Type *PointeeTy, Constant *C, 2334 bool InBounds, 2335 Optional<unsigned> InRangeIndex, 2336 ArrayRef<Value *> Idxs) { 2337 if (Idxs.empty()) return C; 2338 2339 Type *GEPTy = GetElementPtrInst::getGEPReturnType( 2340 PointeeTy, C, makeArrayRef((Value *const *)Idxs.data(), Idxs.size())); 2341 2342 if (isa<PoisonValue>(C)) 2343 return PoisonValue::get(GEPTy); 2344 2345 if (isa<UndefValue>(C)) 2346 // If inbounds, we can choose an out-of-bounds pointer as a base pointer. 2347 return InBounds ? PoisonValue::get(GEPTy) : UndefValue::get(GEPTy); 2348 2349 Constant *Idx0 = cast<Constant>(Idxs[0]); 2350 if (Idxs.size() == 1 && (Idx0->isNullValue() || isa<UndefValue>(Idx0))) 2351 return GEPTy->isVectorTy() && !C->getType()->isVectorTy() 2352 ? ConstantVector::getSplat( 2353 cast<VectorType>(GEPTy)->getElementCount(), C) 2354 : C; 2355 2356 if (C->isNullValue()) { 2357 bool isNull = true; 2358 for (unsigned i = 0, e = Idxs.size(); i != e; ++i) 2359 if (!isa<UndefValue>(Idxs[i]) && 2360 !cast<Constant>(Idxs[i])->isNullValue()) { 2361 isNull = false; 2362 break; 2363 } 2364 if (isNull) { 2365 PointerType *PtrTy = cast<PointerType>(C->getType()->getScalarType()); 2366 Type *Ty = GetElementPtrInst::getIndexedType(PointeeTy, Idxs); 2367 2368 assert(Ty && "Invalid indices for GEP!"); 2369 Type *OrigGEPTy = PointerType::get(Ty, PtrTy->getAddressSpace()); 2370 Type *GEPTy = PointerType::get(Ty, PtrTy->getAddressSpace()); 2371 if (VectorType *VT = dyn_cast<VectorType>(C->getType())) 2372 GEPTy = VectorType::get(OrigGEPTy, VT->getElementCount()); 2373 2374 // The GEP returns a vector of pointers when one of more of 2375 // its arguments is a vector. 2376 for (unsigned i = 0, e = Idxs.size(); i != e; ++i) { 2377 if (auto *VT = dyn_cast<VectorType>(Idxs[i]->getType())) { 2378 assert((!isa<VectorType>(GEPTy) || isa<ScalableVectorType>(GEPTy) == 2379 isa<ScalableVectorType>(VT)) && 2380 "Mismatched GEPTy vector types"); 2381 GEPTy = VectorType::get(OrigGEPTy, VT->getElementCount()); 2382 break; 2383 } 2384 } 2385 2386 return Constant::getNullValue(GEPTy); 2387 } 2388 } 2389 2390 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { 2391 // Combine Indices - If the source pointer to this getelementptr instruction 2392 // is a getelementptr instruction, combine the indices of the two 2393 // getelementptr instructions into a single instruction. 2394 // 2395 if (CE->getOpcode() == Instruction::GetElementPtr) { 2396 gep_type_iterator LastI = gep_type_end(CE); 2397 for (gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE); 2398 I != E; ++I) 2399 LastI = I; 2400 2401 // We cannot combine indices if doing so would take us outside of an 2402 // array or vector. Doing otherwise could trick us if we evaluated such a 2403 // GEP as part of a load. 2404 // 2405 // e.g. Consider if the original GEP was: 2406 // i8* getelementptr ({ [2 x i8], i32, i8, [3 x i8] }* @main.c, 2407 // i32 0, i32 0, i64 0) 2408 // 2409 // If we then tried to offset it by '8' to get to the third element, 2410 // an i8, we should *not* get: 2411 // i8* getelementptr ({ [2 x i8], i32, i8, [3 x i8] }* @main.c, 2412 // i32 0, i32 0, i64 8) 2413 // 2414 // This GEP tries to index array element '8 which runs out-of-bounds. 2415 // Subsequent evaluation would get confused and produce erroneous results. 2416 // 2417 // The following prohibits such a GEP from being formed by checking to see 2418 // if the index is in-range with respect to an array. 2419 // TODO: This code may be extended to handle vectors as well. 2420 bool PerformFold = false; 2421 if (Idx0->isNullValue()) 2422 PerformFold = true; 2423 else if (LastI.isSequential()) 2424 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx0)) 2425 PerformFold = (!LastI.isBoundedSequential() || 2426 isIndexInRangeOfArrayType( 2427 LastI.getSequentialNumElements(), CI)) && 2428 !CE->getOperand(CE->getNumOperands() - 1) 2429 ->getType() 2430 ->isVectorTy(); 2431 2432 if (PerformFold) { 2433 SmallVector<Value*, 16> NewIndices; 2434 NewIndices.reserve(Idxs.size() + CE->getNumOperands()); 2435 NewIndices.append(CE->op_begin() + 1, CE->op_end() - 1); 2436 2437 // Add the last index of the source with the first index of the new GEP. 2438 // Make sure to handle the case when they are actually different types. 2439 Constant *Combined = CE->getOperand(CE->getNumOperands()-1); 2440 // Otherwise it must be an array. 2441 if (!Idx0->isNullValue()) { 2442 Type *IdxTy = Combined->getType(); 2443 if (IdxTy != Idx0->getType()) { 2444 unsigned CommonExtendedWidth = 2445 std::max(IdxTy->getIntegerBitWidth(), 2446 Idx0->getType()->getIntegerBitWidth()); 2447 CommonExtendedWidth = std::max(CommonExtendedWidth, 64U); 2448 2449 Type *CommonTy = 2450 Type::getIntNTy(IdxTy->getContext(), CommonExtendedWidth); 2451 Constant *C1 = ConstantExpr::getSExtOrBitCast(Idx0, CommonTy); 2452 Constant *C2 = ConstantExpr::getSExtOrBitCast(Combined, CommonTy); 2453 Combined = ConstantExpr::get(Instruction::Add, C1, C2); 2454 } else { 2455 Combined = 2456 ConstantExpr::get(Instruction::Add, Idx0, Combined); 2457 } 2458 } 2459 2460 NewIndices.push_back(Combined); 2461 NewIndices.append(Idxs.begin() + 1, Idxs.end()); 2462 2463 // The combined GEP normally inherits its index inrange attribute from 2464 // the inner GEP, but if the inner GEP's last index was adjusted by the 2465 // outer GEP, any inbounds attribute on that index is invalidated. 2466 Optional<unsigned> IRIndex = cast<GEPOperator>(CE)->getInRangeIndex(); 2467 if (IRIndex && *IRIndex == CE->getNumOperands() - 2 && !Idx0->isNullValue()) 2468 IRIndex = None; 2469 2470 return ConstantExpr::getGetElementPtr( 2471 cast<GEPOperator>(CE)->getSourceElementType(), CE->getOperand(0), 2472 NewIndices, InBounds && cast<GEPOperator>(CE)->isInBounds(), 2473 IRIndex); 2474 } 2475 } 2476 2477 // Attempt to fold casts to the same type away. For example, folding: 2478 // 2479 // i32* getelementptr ([2 x i32]* bitcast ([3 x i32]* %X to [2 x i32]*), 2480 // i64 0, i64 0) 2481 // into: 2482 // 2483 // i32* getelementptr ([3 x i32]* %X, i64 0, i64 0) 2484 // 2485 // Don't fold if the cast is changing address spaces. 2486 if (CE->isCast() && Idxs.size() > 1 && Idx0->isNullValue()) { 2487 PointerType *SrcPtrTy = 2488 dyn_cast<PointerType>(CE->getOperand(0)->getType()); 2489 PointerType *DstPtrTy = dyn_cast<PointerType>(CE->getType()); 2490 if (SrcPtrTy && DstPtrTy) { 2491 ArrayType *SrcArrayTy = 2492 dyn_cast<ArrayType>(SrcPtrTy->getElementType()); 2493 ArrayType *DstArrayTy = 2494 dyn_cast<ArrayType>(DstPtrTy->getElementType()); 2495 if (SrcArrayTy && DstArrayTy 2496 && SrcArrayTy->getElementType() == DstArrayTy->getElementType() 2497 && SrcPtrTy->getAddressSpace() == DstPtrTy->getAddressSpace()) 2498 return ConstantExpr::getGetElementPtr(SrcArrayTy, 2499 (Constant *)CE->getOperand(0), 2500 Idxs, InBounds, InRangeIndex); 2501 } 2502 } 2503 } 2504 2505 // Check to see if any array indices are not within the corresponding 2506 // notional array or vector bounds. If so, try to determine if they can be 2507 // factored out into preceding dimensions. 2508 SmallVector<Constant *, 8> NewIdxs; 2509 Type *Ty = PointeeTy; 2510 Type *Prev = C->getType(); 2511 auto GEPIter = gep_type_begin(PointeeTy, Idxs); 2512 bool Unknown = 2513 !isa<ConstantInt>(Idxs[0]) && !isa<ConstantDataVector>(Idxs[0]); 2514 for (unsigned i = 1, e = Idxs.size(); i != e; 2515 Prev = Ty, Ty = (++GEPIter).getIndexedType(), ++i) { 2516 if (!isa<ConstantInt>(Idxs[i]) && !isa<ConstantDataVector>(Idxs[i])) { 2517 // We don't know if it's in range or not. 2518 Unknown = true; 2519 continue; 2520 } 2521 if (!isa<ConstantInt>(Idxs[i - 1]) && !isa<ConstantDataVector>(Idxs[i - 1])) 2522 // Skip if the type of the previous index is not supported. 2523 continue; 2524 if (InRangeIndex && i == *InRangeIndex + 1) { 2525 // If an index is marked inrange, we cannot apply this canonicalization to 2526 // the following index, as that will cause the inrange index to point to 2527 // the wrong element. 2528 continue; 2529 } 2530 if (isa<StructType>(Ty)) { 2531 // The verify makes sure that GEPs into a struct are in range. 2532 continue; 2533 } 2534 if (isa<VectorType>(Ty)) { 2535 // There can be awkward padding in after a non-power of two vector. 2536 Unknown = true; 2537 continue; 2538 } 2539 auto *STy = cast<ArrayType>(Ty); 2540 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idxs[i])) { 2541 if (isIndexInRangeOfArrayType(STy->getNumElements(), CI)) 2542 // It's in range, skip to the next index. 2543 continue; 2544 if (CI->getSExtValue() < 0) { 2545 // It's out of range and negative, don't try to factor it. 2546 Unknown = true; 2547 continue; 2548 } 2549 } else { 2550 auto *CV = cast<ConstantDataVector>(Idxs[i]); 2551 bool InRange = true; 2552 for (unsigned I = 0, E = CV->getNumElements(); I != E; ++I) { 2553 auto *CI = cast<ConstantInt>(CV->getElementAsConstant(I)); 2554 InRange &= isIndexInRangeOfArrayType(STy->getNumElements(), CI); 2555 if (CI->getSExtValue() < 0) { 2556 Unknown = true; 2557 break; 2558 } 2559 } 2560 if (InRange || Unknown) 2561 // It's in range, skip to the next index. 2562 // It's out of range and negative, don't try to factor it. 2563 continue; 2564 } 2565 if (isa<StructType>(Prev)) { 2566 // It's out of range, but the prior dimension is a struct 2567 // so we can't do anything about it. 2568 Unknown = true; 2569 continue; 2570 } 2571 // It's out of range, but we can factor it into the prior 2572 // dimension. 2573 NewIdxs.resize(Idxs.size()); 2574 // Determine the number of elements in our sequential type. 2575 uint64_t NumElements = STy->getArrayNumElements(); 2576 2577 // Expand the current index or the previous index to a vector from a scalar 2578 // if necessary. 2579 Constant *CurrIdx = cast<Constant>(Idxs[i]); 2580 auto *PrevIdx = 2581 NewIdxs[i - 1] ? NewIdxs[i - 1] : cast<Constant>(Idxs[i - 1]); 2582 bool IsCurrIdxVector = CurrIdx->getType()->isVectorTy(); 2583 bool IsPrevIdxVector = PrevIdx->getType()->isVectorTy(); 2584 bool UseVector = IsCurrIdxVector || IsPrevIdxVector; 2585 2586 if (!IsCurrIdxVector && IsPrevIdxVector) 2587 CurrIdx = ConstantDataVector::getSplat( 2588 cast<FixedVectorType>(PrevIdx->getType())->getNumElements(), CurrIdx); 2589 2590 if (!IsPrevIdxVector && IsCurrIdxVector) 2591 PrevIdx = ConstantDataVector::getSplat( 2592 cast<FixedVectorType>(CurrIdx->getType())->getNumElements(), PrevIdx); 2593 2594 Constant *Factor = 2595 ConstantInt::get(CurrIdx->getType()->getScalarType(), NumElements); 2596 if (UseVector) 2597 Factor = ConstantDataVector::getSplat( 2598 IsPrevIdxVector 2599 ? cast<FixedVectorType>(PrevIdx->getType())->getNumElements() 2600 : cast<FixedVectorType>(CurrIdx->getType())->getNumElements(), 2601 Factor); 2602 2603 NewIdxs[i] = ConstantExpr::getSRem(CurrIdx, Factor); 2604 2605 Constant *Div = ConstantExpr::getSDiv(CurrIdx, Factor); 2606 2607 unsigned CommonExtendedWidth = 2608 std::max(PrevIdx->getType()->getScalarSizeInBits(), 2609 Div->getType()->getScalarSizeInBits()); 2610 CommonExtendedWidth = std::max(CommonExtendedWidth, 64U); 2611 2612 // Before adding, extend both operands to i64 to avoid 2613 // overflow trouble. 2614 Type *ExtendedTy = Type::getIntNTy(Div->getContext(), CommonExtendedWidth); 2615 if (UseVector) 2616 ExtendedTy = FixedVectorType::get( 2617 ExtendedTy, 2618 IsPrevIdxVector 2619 ? cast<FixedVectorType>(PrevIdx->getType())->getNumElements() 2620 : cast<FixedVectorType>(CurrIdx->getType())->getNumElements()); 2621 2622 if (!PrevIdx->getType()->isIntOrIntVectorTy(CommonExtendedWidth)) 2623 PrevIdx = ConstantExpr::getSExt(PrevIdx, ExtendedTy); 2624 2625 if (!Div->getType()->isIntOrIntVectorTy(CommonExtendedWidth)) 2626 Div = ConstantExpr::getSExt(Div, ExtendedTy); 2627 2628 NewIdxs[i - 1] = ConstantExpr::getAdd(PrevIdx, Div); 2629 } 2630 2631 // If we did any factoring, start over with the adjusted indices. 2632 if (!NewIdxs.empty()) { 2633 for (unsigned i = 0, e = Idxs.size(); i != e; ++i) 2634 if (!NewIdxs[i]) NewIdxs[i] = cast<Constant>(Idxs[i]); 2635 return ConstantExpr::getGetElementPtr(PointeeTy, C, NewIdxs, InBounds, 2636 InRangeIndex); 2637 } 2638 2639 // If all indices are known integers and normalized, we can do a simple 2640 // check for the "inbounds" property. 2641 if (!Unknown && !InBounds) 2642 if (auto *GV = dyn_cast<GlobalVariable>(C)) 2643 if (!GV->hasExternalWeakLinkage() && isInBoundsIndices(Idxs)) 2644 return ConstantExpr::getGetElementPtr(PointeeTy, C, Idxs, 2645 /*InBounds=*/true, InRangeIndex); 2646 2647 return nullptr; 2648 } 2649