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