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