ConstantFold.cpp revision 9dec3a2c0ca8d59e50ffbf1c97b171c7d5f2d6ec
1//===- ConstantFolding.cpp - LLVM constant folder -------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements folding of constants for LLVM. This implements the 11// (internal) ConstantFolding.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// template-based folder for simple primitive constants like ConstantInt, and 16// the special case hackery that we use to symbolically evaluate expressions 17// that use ConstantExprs. 18// 19//===----------------------------------------------------------------------===// 20 21#include "ConstantFolding.h" 22#include "llvm/Constants.h" 23#include "llvm/Instructions.h" 24#include "llvm/DerivedTypes.h" 25#include "llvm/Function.h" 26#include "llvm/Support/Compiler.h" 27#include "llvm/Support/GetElementPtrTypeIterator.h" 28#include "llvm/Support/ManagedStatic.h" 29#include "llvm/Support/MathExtras.h" 30#include <limits> 31using namespace llvm; 32 33namespace { 34 struct VISIBILITY_HIDDEN ConstRules { 35 ConstRules() {} 36 virtual ~ConstRules() {} 37 38 // Binary Operators... 39 virtual Constant *add(const Constant *V1, const Constant *V2) const = 0; 40 virtual Constant *sub(const Constant *V1, const Constant *V2) const = 0; 41 virtual Constant *mul(const Constant *V1, const Constant *V2) const = 0; 42 virtual Constant *urem(const Constant *V1, const Constant *V2) const = 0; 43 virtual Constant *srem(const Constant *V1, const Constant *V2) const = 0; 44 virtual Constant *frem(const Constant *V1, const Constant *V2) const = 0; 45 virtual Constant *udiv(const Constant *V1, const Constant *V2) const = 0; 46 virtual Constant *sdiv(const Constant *V1, const Constant *V2) const = 0; 47 virtual Constant *fdiv(const Constant *V1, const Constant *V2) const = 0; 48 virtual Constant *op_and(const Constant *V1, const Constant *V2) const = 0; 49 virtual Constant *op_or (const Constant *V1, const Constant *V2) const = 0; 50 virtual Constant *op_xor(const Constant *V1, const Constant *V2) const = 0; 51 virtual Constant *shl(const Constant *V1, const Constant *V2) const = 0; 52 virtual Constant *lshr(const Constant *V1, const Constant *V2) const = 0; 53 virtual Constant *ashr(const Constant *V1, const Constant *V2) const = 0; 54 virtual Constant *lessthan(const Constant *V1, const Constant *V2) const =0; 55 virtual Constant *equalto(const Constant *V1, const Constant *V2) const = 0; 56 57 // Casting operators. 58 virtual Constant *castToBool (const Constant *V) const = 0; 59 virtual Constant *castToSByte (const Constant *V) const = 0; 60 virtual Constant *castToUByte (const Constant *V) const = 0; 61 virtual Constant *castToShort (const Constant *V) const = 0; 62 virtual Constant *castToUShort(const Constant *V) const = 0; 63 virtual Constant *castToInt (const Constant *V) const = 0; 64 virtual Constant *castToUInt (const Constant *V) const = 0; 65 virtual Constant *castToLong (const Constant *V) const = 0; 66 virtual Constant *castToULong (const Constant *V) const = 0; 67 virtual Constant *castToFloat (const Constant *V) const = 0; 68 virtual Constant *castToDouble(const Constant *V) const = 0; 69 virtual Constant *castToPointer(const Constant *V, 70 const PointerType *Ty) const = 0; 71 72 // ConstRules::get - Return an instance of ConstRules for the specified 73 // constant operands. 74 // 75 static ConstRules &get(const Constant *V1, const Constant *V2); 76 private: 77 ConstRules(const ConstRules &); // Do not implement 78 ConstRules &operator=(const ConstRules &); // Do not implement 79 }; 80} 81 82 83//===----------------------------------------------------------------------===// 84// TemplateRules Class 85//===----------------------------------------------------------------------===// 86// 87// TemplateRules - Implement a subclass of ConstRules that provides all 88// operations as noops. All other rules classes inherit from this class so 89// that if functionality is needed in the future, it can simply be added here 90// and to ConstRules without changing anything else... 91// 92// This class also provides subclasses with typesafe implementations of methods 93// so that don't have to do type casting. 94// 95namespace { 96template<class ArgType, class SubClassName> 97class VISIBILITY_HIDDEN TemplateRules : public ConstRules { 98 99 100 //===--------------------------------------------------------------------===// 101 // Redirecting functions that cast to the appropriate types 102 //===--------------------------------------------------------------------===// 103 104 virtual Constant *add(const Constant *V1, const Constant *V2) const { 105 return SubClassName::Add((const ArgType *)V1, (const ArgType *)V2); 106 } 107 virtual Constant *sub(const Constant *V1, const Constant *V2) const { 108 return SubClassName::Sub((const ArgType *)V1, (const ArgType *)V2); 109 } 110 virtual Constant *mul(const Constant *V1, const Constant *V2) const { 111 return SubClassName::Mul((const ArgType *)V1, (const ArgType *)V2); 112 } 113 virtual Constant *udiv(const Constant *V1, const Constant *V2) const { 114 return SubClassName::UDiv((const ArgType *)V1, (const ArgType *)V2); 115 } 116 virtual Constant *sdiv(const Constant *V1, const Constant *V2) const { 117 return SubClassName::SDiv((const ArgType *)V1, (const ArgType *)V2); 118 } 119 virtual Constant *fdiv(const Constant *V1, const Constant *V2) const { 120 return SubClassName::FDiv((const ArgType *)V1, (const ArgType *)V2); 121 } 122 virtual Constant *urem(const Constant *V1, const Constant *V2) const { 123 return SubClassName::URem((const ArgType *)V1, (const ArgType *)V2); 124 } 125 virtual Constant *srem(const Constant *V1, const Constant *V2) const { 126 return SubClassName::SRem((const ArgType *)V1, (const ArgType *)V2); 127 } 128 virtual Constant *frem(const Constant *V1, const Constant *V2) const { 129 return SubClassName::FRem((const ArgType *)V1, (const ArgType *)V2); 130 } 131 virtual Constant *op_and(const Constant *V1, const Constant *V2) const { 132 return SubClassName::And((const ArgType *)V1, (const ArgType *)V2); 133 } 134 virtual Constant *op_or(const Constant *V1, const Constant *V2) const { 135 return SubClassName::Or((const ArgType *)V1, (const ArgType *)V2); 136 } 137 virtual Constant *op_xor(const Constant *V1, const Constant *V2) const { 138 return SubClassName::Xor((const ArgType *)V1, (const ArgType *)V2); 139 } 140 virtual Constant *shl(const Constant *V1, const Constant *V2) const { 141 return SubClassName::Shl((const ArgType *)V1, (const ArgType *)V2); 142 } 143 virtual Constant *lshr(const Constant *V1, const Constant *V2) const { 144 return SubClassName::LShr((const ArgType *)V1, (const ArgType *)V2); 145 } 146 virtual Constant *ashr(const Constant *V1, const Constant *V2) const { 147 return SubClassName::AShr((const ArgType *)V1, (const ArgType *)V2); 148 } 149 150 virtual Constant *lessthan(const Constant *V1, const Constant *V2) const { 151 return SubClassName::LessThan((const ArgType *)V1, (const ArgType *)V2); 152 } 153 virtual Constant *equalto(const Constant *V1, const Constant *V2) const { 154 return SubClassName::EqualTo((const ArgType *)V1, (const ArgType *)V2); 155 } 156 157 // Casting operators. ick 158 virtual Constant *castToBool(const Constant *V) const { 159 return SubClassName::CastToBool((const ArgType*)V); 160 } 161 virtual Constant *castToSByte(const Constant *V) const { 162 return SubClassName::CastToSByte((const ArgType*)V); 163 } 164 virtual Constant *castToUByte(const Constant *V) const { 165 return SubClassName::CastToUByte((const ArgType*)V); 166 } 167 virtual Constant *castToShort(const Constant *V) const { 168 return SubClassName::CastToShort((const ArgType*)V); 169 } 170 virtual Constant *castToUShort(const Constant *V) const { 171 return SubClassName::CastToUShort((const ArgType*)V); 172 } 173 virtual Constant *castToInt(const Constant *V) const { 174 return SubClassName::CastToInt((const ArgType*)V); 175 } 176 virtual Constant *castToUInt(const Constant *V) const { 177 return SubClassName::CastToUInt((const ArgType*)V); 178 } 179 virtual Constant *castToLong(const Constant *V) const { 180 return SubClassName::CastToLong((const ArgType*)V); 181 } 182 virtual Constant *castToULong(const Constant *V) const { 183 return SubClassName::CastToULong((const ArgType*)V); 184 } 185 virtual Constant *castToFloat(const Constant *V) const { 186 return SubClassName::CastToFloat((const ArgType*)V); 187 } 188 virtual Constant *castToDouble(const Constant *V) const { 189 return SubClassName::CastToDouble((const ArgType*)V); 190 } 191 virtual Constant *castToPointer(const Constant *V, 192 const PointerType *Ty) const { 193 return SubClassName::CastToPointer((const ArgType*)V, Ty); 194 } 195 196 //===--------------------------------------------------------------------===// 197 // Default "noop" implementations 198 //===--------------------------------------------------------------------===// 199 200 static Constant *Add (const ArgType *V1, const ArgType *V2) { return 0; } 201 static Constant *Sub (const ArgType *V1, const ArgType *V2) { return 0; } 202 static Constant *Mul (const ArgType *V1, const ArgType *V2) { return 0; } 203 static Constant *SDiv(const ArgType *V1, const ArgType *V2) { return 0; } 204 static Constant *UDiv(const ArgType *V1, const ArgType *V2) { return 0; } 205 static Constant *FDiv(const ArgType *V1, const ArgType *V2) { return 0; } 206 static Constant *URem(const ArgType *V1, const ArgType *V2) { return 0; } 207 static Constant *SRem(const ArgType *V1, const ArgType *V2) { return 0; } 208 static Constant *FRem(const ArgType *V1, const ArgType *V2) { return 0; } 209 static Constant *And (const ArgType *V1, const ArgType *V2) { return 0; } 210 static Constant *Or (const ArgType *V1, const ArgType *V2) { return 0; } 211 static Constant *Xor (const ArgType *V1, const ArgType *V2) { return 0; } 212 static Constant *Shl (const ArgType *V1, const ArgType *V2) { return 0; } 213 static Constant *LShr(const ArgType *V1, const ArgType *V2) { return 0; } 214 static Constant *AShr(const ArgType *V1, const ArgType *V2) { return 0; } 215 static Constant *LessThan(const ArgType *V1, const ArgType *V2) { 216 return 0; 217 } 218 static Constant *EqualTo(const ArgType *V1, const ArgType *V2) { 219 return 0; 220 } 221 222 // Casting operators. ick 223 static Constant *CastToBool (const Constant *V) { return 0; } 224 static Constant *CastToSByte (const Constant *V) { return 0; } 225 static Constant *CastToUByte (const Constant *V) { return 0; } 226 static Constant *CastToShort (const Constant *V) { return 0; } 227 static Constant *CastToUShort(const Constant *V) { return 0; } 228 static Constant *CastToInt (const Constant *V) { return 0; } 229 static Constant *CastToUInt (const Constant *V) { return 0; } 230 static Constant *CastToLong (const Constant *V) { return 0; } 231 static Constant *CastToULong (const Constant *V) { return 0; } 232 static Constant *CastToFloat (const Constant *V) { return 0; } 233 static Constant *CastToDouble(const Constant *V) { return 0; } 234 static Constant *CastToPointer(const Constant *, 235 const PointerType *) {return 0;} 236 237public: 238 virtual ~TemplateRules() {} 239}; 240} // end anonymous namespace 241 242 243//===----------------------------------------------------------------------===// 244// EmptyRules Class 245//===----------------------------------------------------------------------===// 246// 247// EmptyRules provides a concrete base class of ConstRules that does nothing 248// 249namespace { 250struct VISIBILITY_HIDDEN EmptyRules 251 : public TemplateRules<Constant, EmptyRules> { 252 static Constant *EqualTo(const Constant *V1, const Constant *V2) { 253 if (V1 == V2) return ConstantBool::getTrue(); 254 return 0; 255 } 256}; 257} // end anonymous namespace 258 259 260 261//===----------------------------------------------------------------------===// 262// BoolRules Class 263//===----------------------------------------------------------------------===// 264// 265// BoolRules provides a concrete base class of ConstRules for the 'bool' type. 266// 267namespace { 268struct VISIBILITY_HIDDEN BoolRules 269 : public TemplateRules<ConstantBool, BoolRules> { 270 271 static Constant *LessThan(const ConstantBool *V1, const ConstantBool *V2) { 272 return ConstantBool::get(V1->getValue() < V2->getValue()); 273 } 274 275 static Constant *EqualTo(const Constant *V1, const Constant *V2) { 276 return ConstantBool::get(V1 == V2); 277 } 278 279 static Constant *And(const ConstantBool *V1, const ConstantBool *V2) { 280 return ConstantBool::get(V1->getValue() & V2->getValue()); 281 } 282 283 static Constant *Or(const ConstantBool *V1, const ConstantBool *V2) { 284 return ConstantBool::get(V1->getValue() | V2->getValue()); 285 } 286 287 static Constant *Xor(const ConstantBool *V1, const ConstantBool *V2) { 288 return ConstantBool::get(V1->getValue() ^ V2->getValue()); 289 } 290 291 // Casting operators. ick 292#define DEF_CAST(TYPE, CLASS, CTYPE) \ 293 static Constant *CastTo##TYPE (const ConstantBool *V) { \ 294 return CLASS::get(Type::TYPE##Ty, (CTYPE)(bool)V->getValue()); \ 295 } 296 297 DEF_CAST(Bool , ConstantBool, bool) 298 DEF_CAST(SByte , ConstantInt, signed char) 299 DEF_CAST(UByte , ConstantInt, unsigned char) 300 DEF_CAST(Short , ConstantInt, signed short) 301 DEF_CAST(UShort, ConstantInt, unsigned short) 302 DEF_CAST(Int , ConstantInt, signed int) 303 DEF_CAST(UInt , ConstantInt, unsigned int) 304 DEF_CAST(Long , ConstantInt, int64_t) 305 DEF_CAST(ULong , ConstantInt, uint64_t) 306 DEF_CAST(Float , ConstantFP , float) 307 DEF_CAST(Double, ConstantFP , double) 308#undef DEF_CAST 309}; 310} // end anonymous namespace 311 312 313//===----------------------------------------------------------------------===// 314// NullPointerRules Class 315//===----------------------------------------------------------------------===// 316// 317// NullPointerRules provides a concrete base class of ConstRules for null 318// pointers. 319// 320namespace { 321struct VISIBILITY_HIDDEN NullPointerRules 322 : public TemplateRules<ConstantPointerNull, NullPointerRules> { 323 static Constant *EqualTo(const Constant *V1, const Constant *V2) { 324 return ConstantBool::getTrue(); // Null pointers are always equal 325 } 326 static Constant *CastToBool(const Constant *V) { 327 return ConstantBool::getFalse(); 328 } 329 static Constant *CastToSByte (const Constant *V) { 330 return ConstantInt::get(Type::SByteTy, 0); 331 } 332 static Constant *CastToUByte (const Constant *V) { 333 return ConstantInt::get(Type::UByteTy, 0); 334 } 335 static Constant *CastToShort (const Constant *V) { 336 return ConstantInt::get(Type::ShortTy, 0); 337 } 338 static Constant *CastToUShort(const Constant *V) { 339 return ConstantInt::get(Type::UShortTy, 0); 340 } 341 static Constant *CastToInt (const Constant *V) { 342 return ConstantInt::get(Type::IntTy, 0); 343 } 344 static Constant *CastToUInt (const Constant *V) { 345 return ConstantInt::get(Type::UIntTy, 0); 346 } 347 static Constant *CastToLong (const Constant *V) { 348 return ConstantInt::get(Type::LongTy, 0); 349 } 350 static Constant *CastToULong (const Constant *V) { 351 return ConstantInt::get(Type::ULongTy, 0); 352 } 353 static Constant *CastToFloat (const Constant *V) { 354 return ConstantFP::get(Type::FloatTy, 0); 355 } 356 static Constant *CastToDouble(const Constant *V) { 357 return ConstantFP::get(Type::DoubleTy, 0); 358 } 359 360 static Constant *CastToPointer(const ConstantPointerNull *V, 361 const PointerType *PTy) { 362 return ConstantPointerNull::get(PTy); 363 } 364}; 365} // end anonymous namespace 366 367//===----------------------------------------------------------------------===// 368// ConstantPackedRules Class 369//===----------------------------------------------------------------------===// 370 371/// DoVectorOp - Given two packed constants and a function pointer, apply the 372/// function pointer to each element pair, producing a new ConstantPacked 373/// constant. 374static Constant *EvalVectorOp(const ConstantPacked *V1, 375 const ConstantPacked *V2, 376 Constant *(*FP)(Constant*, Constant*)) { 377 std::vector<Constant*> Res; 378 for (unsigned i = 0, e = V1->getNumOperands(); i != e; ++i) 379 Res.push_back(FP(const_cast<Constant*>(V1->getOperand(i)), 380 const_cast<Constant*>(V2->getOperand(i)))); 381 return ConstantPacked::get(Res); 382} 383 384/// PackedTypeRules provides a concrete base class of ConstRules for 385/// ConstantPacked operands. 386/// 387namespace { 388struct VISIBILITY_HIDDEN ConstantPackedRules 389 : public TemplateRules<ConstantPacked, ConstantPackedRules> { 390 391 static Constant *Add(const ConstantPacked *V1, const ConstantPacked *V2) { 392 return EvalVectorOp(V1, V2, ConstantExpr::getAdd); 393 } 394 static Constant *Sub(const ConstantPacked *V1, const ConstantPacked *V2) { 395 return EvalVectorOp(V1, V2, ConstantExpr::getSub); 396 } 397 static Constant *Mul(const ConstantPacked *V1, const ConstantPacked *V2) { 398 return EvalVectorOp(V1, V2, ConstantExpr::getMul); 399 } 400 static Constant *UDiv(const ConstantPacked *V1, const ConstantPacked *V2) { 401 return EvalVectorOp(V1, V2, ConstantExpr::getUDiv); 402 } 403 static Constant *SDiv(const ConstantPacked *V1, const ConstantPacked *V2) { 404 return EvalVectorOp(V1, V2, ConstantExpr::getSDiv); 405 } 406 static Constant *FDiv(const ConstantPacked *V1, const ConstantPacked *V2) { 407 return EvalVectorOp(V1, V2, ConstantExpr::getFDiv); 408 } 409 static Constant *URem(const ConstantPacked *V1, const ConstantPacked *V2) { 410 return EvalVectorOp(V1, V2, ConstantExpr::getURem); 411 } 412 static Constant *SRem(const ConstantPacked *V1, const ConstantPacked *V2) { 413 return EvalVectorOp(V1, V2, ConstantExpr::getSRem); 414 } 415 static Constant *FRem(const ConstantPacked *V1, const ConstantPacked *V2) { 416 return EvalVectorOp(V1, V2, ConstantExpr::getFRem); 417 } 418 static Constant *And(const ConstantPacked *V1, const ConstantPacked *V2) { 419 return EvalVectorOp(V1, V2, ConstantExpr::getAnd); 420 } 421 static Constant *Or (const ConstantPacked *V1, const ConstantPacked *V2) { 422 return EvalVectorOp(V1, V2, ConstantExpr::getOr); 423 } 424 static Constant *Xor(const ConstantPacked *V1, const ConstantPacked *V2) { 425 return EvalVectorOp(V1, V2, ConstantExpr::getXor); 426 } 427 static Constant *LessThan(const ConstantPacked *V1, const ConstantPacked *V2){ 428 return 0; 429 } 430 static Constant *EqualTo(const ConstantPacked *V1, const ConstantPacked *V2) { 431 for (unsigned i = 0, e = V1->getNumOperands(); i != e; ++i) { 432 Constant *C = 433 ConstantExpr::getSetEQ(const_cast<Constant*>(V1->getOperand(i)), 434 const_cast<Constant*>(V2->getOperand(i))); 435 if (ConstantBool *CB = dyn_cast<ConstantBool>(C)) 436 return CB; 437 } 438 // Otherwise, could not decide from any element pairs. 439 return 0; 440 } 441}; 442} // end anonymous namespace 443 444 445//===----------------------------------------------------------------------===// 446// GeneralPackedRules Class 447//===----------------------------------------------------------------------===// 448 449/// GeneralPackedRules provides a concrete base class of ConstRules for 450/// PackedType operands, where both operands are not ConstantPacked. The usual 451/// cause for this is that one operand is a ConstantAggregateZero. 452/// 453namespace { 454struct VISIBILITY_HIDDEN GeneralPackedRules 455 : public TemplateRules<Constant, GeneralPackedRules> { 456}; 457} // end anonymous namespace 458 459 460//===----------------------------------------------------------------------===// 461// DirectIntRules Class 462//===----------------------------------------------------------------------===// 463// 464// DirectIntRules provides implementations of functions that are valid on 465// integer types, but not all types in general. 466// 467namespace { 468template <class BuiltinType, Type **Ty> 469struct VISIBILITY_HIDDEN DirectIntRules 470 : public TemplateRules<ConstantInt, DirectIntRules<BuiltinType, Ty> > { 471 472 static Constant *Add(const ConstantInt *V1, const ConstantInt *V2) { 473 BuiltinType R = (BuiltinType)V1->getZExtValue() + 474 (BuiltinType)V2->getZExtValue(); 475 return ConstantInt::get(*Ty, R); 476 } 477 478 static Constant *Sub(const ConstantInt *V1, const ConstantInt *V2) { 479 BuiltinType R = (BuiltinType)V1->getZExtValue() - 480 (BuiltinType)V2->getZExtValue(); 481 return ConstantInt::get(*Ty, R); 482 } 483 484 static Constant *Mul(const ConstantInt *V1, const ConstantInt *V2) { 485 BuiltinType R = (BuiltinType)V1->getZExtValue() * 486 (BuiltinType)V2->getZExtValue(); 487 return ConstantInt::get(*Ty, R); 488 } 489 490 static Constant *LessThan(const ConstantInt *V1, const ConstantInt *V2) { 491 bool R = (BuiltinType)V1->getZExtValue() < (BuiltinType)V2->getZExtValue(); 492 return ConstantBool::get(R); 493 } 494 495 static Constant *EqualTo(const ConstantInt *V1, const ConstantInt *V2) { 496 bool R = (BuiltinType)V1->getZExtValue() == (BuiltinType)V2->getZExtValue(); 497 return ConstantBool::get(R); 498 } 499 500 static Constant *CastToPointer(const ConstantInt *V, 501 const PointerType *PTy) { 502 if (V->isNullValue()) // Is it a FP or Integral null value? 503 return ConstantPointerNull::get(PTy); 504 return 0; // Can't const prop other types of pointers 505 } 506 507 // Casting operators. ick 508#define DEF_CAST(TYPE, CLASS, CTYPE) \ 509 static Constant *CastTo##TYPE (const ConstantInt *V) { \ 510 return CLASS::get(Type::TYPE##Ty, (CTYPE)((BuiltinType)V->getZExtValue()));\ 511 } 512 513 DEF_CAST(Bool , ConstantBool, bool) 514 DEF_CAST(SByte , ConstantInt, signed char) 515 DEF_CAST(UByte , ConstantInt, unsigned char) 516 DEF_CAST(Short , ConstantInt, signed short) 517 DEF_CAST(UShort, ConstantInt, unsigned short) 518 DEF_CAST(Int , ConstantInt, signed int) 519 DEF_CAST(UInt , ConstantInt, unsigned int) 520 DEF_CAST(Long , ConstantInt, int64_t) 521 DEF_CAST(ULong , ConstantInt, uint64_t) 522 DEF_CAST(Float , ConstantFP , float) 523 DEF_CAST(Double, ConstantFP , double) 524#undef DEF_CAST 525 526 static Constant *UDiv(const ConstantInt *V1, const ConstantInt *V2) { 527 if (V2->isNullValue()) // X / 0 528 return 0; 529 BuiltinType R = (BuiltinType)(V1->getZExtValue() / V2->getZExtValue()); 530 return ConstantInt::get(*Ty, R); 531 } 532 533 static Constant *SDiv(const ConstantInt *V1, const ConstantInt *V2) { 534 if (V2->isNullValue()) // X / 0 535 return 0; 536 if (V2->isAllOnesValue() && // MIN_INT / -1 537 (BuiltinType)V1->getSExtValue() == -(BuiltinType)V1->getSExtValue()) 538 return 0; 539 BuiltinType R = (BuiltinType)(V1->getSExtValue() / V2->getSExtValue()); 540 return ConstantInt::get(*Ty, R); 541 } 542 543 static Constant *URem(const ConstantInt *V1, 544 const ConstantInt *V2) { 545 if (V2->isNullValue()) return 0; // X / 0 546 BuiltinType R = (BuiltinType)(V1->getZExtValue() % V2->getZExtValue()); 547 return ConstantInt::get(*Ty, R); 548 } 549 550 static Constant *SRem(const ConstantInt *V1, 551 const ConstantInt *V2) { 552 if (V2->isNullValue()) return 0; // X % 0 553 if (V2->isAllOnesValue() && // MIN_INT % -1 554 (BuiltinType)V1->getSExtValue() == -(BuiltinType)V1->getSExtValue()) 555 return 0; 556 BuiltinType R = (BuiltinType)(V1->getSExtValue() % V2->getSExtValue()); 557 return ConstantInt::get(*Ty, R); 558 } 559 560 static Constant *And(const ConstantInt *V1, const ConstantInt *V2) { 561 BuiltinType R = 562 (BuiltinType)V1->getZExtValue() & (BuiltinType)V2->getZExtValue(); 563 return ConstantInt::get(*Ty, R); 564 } 565 static Constant *Or(const ConstantInt *V1, const ConstantInt *V2) { 566 BuiltinType R = 567 (BuiltinType)V1->getZExtValue() | (BuiltinType)V2->getZExtValue(); 568 return ConstantInt::get(*Ty, R); 569 } 570 static Constant *Xor(const ConstantInt *V1, const ConstantInt *V2) { 571 BuiltinType R = 572 (BuiltinType)V1->getZExtValue() ^ (BuiltinType)V2->getZExtValue(); 573 return ConstantInt::get(*Ty, R); 574 } 575 576 static Constant *Shl(const ConstantInt *V1, const ConstantInt *V2) { 577 BuiltinType R = 578 (BuiltinType)V1->getZExtValue() << (BuiltinType)V2->getZExtValue(); 579 return ConstantInt::get(*Ty, R); 580 } 581 582 static Constant *LShr(const ConstantInt *V1, const ConstantInt *V2) { 583 BuiltinType R = BuiltinType(V1->getZExtValue() >> V2->getZExtValue()); 584 return ConstantInt::get(*Ty, R); 585 } 586 587 static Constant *AShr(const ConstantInt *V1, const ConstantInt *V2) { 588 BuiltinType R = BuiltinType(V1->getSExtValue() >> V2->getZExtValue()); 589 return ConstantInt::get(*Ty, R); 590 } 591}; 592} // end anonymous namespace 593 594 595//===----------------------------------------------------------------------===// 596// DirectFPRules Class 597//===----------------------------------------------------------------------===// 598// 599/// DirectFPRules provides implementations of functions that are valid on 600/// floating point types, but not all types in general. 601/// 602namespace { 603template <class BuiltinType, Type **Ty> 604struct VISIBILITY_HIDDEN DirectFPRules 605 : public TemplateRules<ConstantFP, DirectFPRules<BuiltinType, Ty> > { 606 607 static Constant *Add(const ConstantFP *V1, const ConstantFP *V2) { 608 BuiltinType R = (BuiltinType)V1->getValue() + 609 (BuiltinType)V2->getValue(); 610 return ConstantFP::get(*Ty, R); 611 } 612 613 static Constant *Sub(const ConstantFP *V1, const ConstantFP *V2) { 614 BuiltinType R = (BuiltinType)V1->getValue() - (BuiltinType)V2->getValue(); 615 return ConstantFP::get(*Ty, R); 616 } 617 618 static Constant *Mul(const ConstantFP *V1, const ConstantFP *V2) { 619 BuiltinType R = (BuiltinType)V1->getValue() * (BuiltinType)V2->getValue(); 620 return ConstantFP::get(*Ty, R); 621 } 622 623 static Constant *LessThan(const ConstantFP *V1, const ConstantFP *V2) { 624 bool R = (BuiltinType)V1->getValue() < (BuiltinType)V2->getValue(); 625 return ConstantBool::get(R); 626 } 627 628 static Constant *EqualTo(const ConstantFP *V1, const ConstantFP *V2) { 629 bool R = (BuiltinType)V1->getValue() == (BuiltinType)V2->getValue(); 630 return ConstantBool::get(R); 631 } 632 633 static Constant *CastToPointer(const ConstantFP *V, 634 const PointerType *PTy) { 635 if (V->isNullValue()) // Is it a FP or Integral null value? 636 return ConstantPointerNull::get(PTy); 637 return 0; // Can't const prop other types of pointers 638 } 639 640 // Casting operators. ick 641#define DEF_CAST(TYPE, CLASS, CTYPE) \ 642 static Constant *CastTo##TYPE (const ConstantFP *V) { \ 643 return CLASS::get(Type::TYPE##Ty, (CTYPE)(BuiltinType)V->getValue()); \ 644 } 645 646 DEF_CAST(Bool , ConstantBool, bool) 647 DEF_CAST(SByte , ConstantInt, signed char) 648 DEF_CAST(UByte , ConstantInt, unsigned char) 649 DEF_CAST(Short , ConstantInt, signed short) 650 DEF_CAST(UShort, ConstantInt, unsigned short) 651 DEF_CAST(Int , ConstantInt, signed int) 652 DEF_CAST(UInt , ConstantInt, unsigned int) 653 DEF_CAST(Long , ConstantInt, int64_t) 654 DEF_CAST(ULong , ConstantInt, uint64_t) 655 DEF_CAST(Float , ConstantFP , float) 656 DEF_CAST(Double, ConstantFP , double) 657#undef DEF_CAST 658 659 static Constant *FRem(const ConstantFP *V1, const ConstantFP *V2) { 660 if (V2->isNullValue()) return 0; 661 BuiltinType Result = std::fmod((BuiltinType)V1->getValue(), 662 (BuiltinType)V2->getValue()); 663 return ConstantFP::get(*Ty, Result); 664 } 665 static Constant *FDiv(const ConstantFP *V1, const ConstantFP *V2) { 666 BuiltinType inf = std::numeric_limits<BuiltinType>::infinity(); 667 if (V2->isExactlyValue(0.0)) return ConstantFP::get(*Ty, inf); 668 if (V2->isExactlyValue(-0.0)) return ConstantFP::get(*Ty, -inf); 669 BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue(); 670 return ConstantFP::get(*Ty, R); 671 } 672}; 673} // end anonymous namespace 674 675static ManagedStatic<EmptyRules> EmptyR; 676static ManagedStatic<BoolRules> BoolR; 677static ManagedStatic<NullPointerRules> NullPointerR; 678static ManagedStatic<ConstantPackedRules> ConstantPackedR; 679static ManagedStatic<GeneralPackedRules> GeneralPackedR; 680static ManagedStatic<DirectIntRules<signed char , &Type::SByteTy> > SByteR; 681static ManagedStatic<DirectIntRules<unsigned char , &Type::UByteTy> > UByteR; 682static ManagedStatic<DirectIntRules<signed short , &Type::ShortTy> > ShortR; 683static ManagedStatic<DirectIntRules<unsigned short, &Type::UShortTy> > UShortR; 684static ManagedStatic<DirectIntRules<signed int , &Type::IntTy> > IntR; 685static ManagedStatic<DirectIntRules<unsigned int , &Type::UIntTy> > UIntR; 686static ManagedStatic<DirectIntRules<int64_t , &Type::LongTy> > LongR; 687static ManagedStatic<DirectIntRules<uint64_t , &Type::ULongTy> > ULongR; 688static ManagedStatic<DirectFPRules <float , &Type::FloatTy> > FloatR; 689static ManagedStatic<DirectFPRules <double , &Type::DoubleTy> > DoubleR; 690 691/// ConstRules::get - This method returns the constant rules implementation that 692/// implements the semantics of the two specified constants. 693ConstRules &ConstRules::get(const Constant *V1, const Constant *V2) { 694 if (isa<ConstantExpr>(V1) || isa<ConstantExpr>(V2) || 695 isa<GlobalValue>(V1) || isa<GlobalValue>(V2) || 696 isa<UndefValue>(V1) || isa<UndefValue>(V2)) 697 return *EmptyR; 698 699 switch (V1->getType()->getTypeID()) { 700 default: assert(0 && "Unknown value type for constant folding!"); 701 case Type::BoolTyID: return *BoolR; 702 case Type::PointerTyID: return *NullPointerR; 703 case Type::SByteTyID: return *SByteR; 704 case Type::UByteTyID: return *UByteR; 705 case Type::ShortTyID: return *ShortR; 706 case Type::UShortTyID: return *UShortR; 707 case Type::IntTyID: return *IntR; 708 case Type::UIntTyID: return *UIntR; 709 case Type::LongTyID: return *LongR; 710 case Type::ULongTyID: return *ULongR; 711 case Type::FloatTyID: return *FloatR; 712 case Type::DoubleTyID: return *DoubleR; 713 case Type::PackedTyID: 714 if (isa<ConstantPacked>(V1) && isa<ConstantPacked>(V2)) 715 return *ConstantPackedR; 716 return *GeneralPackedR; // Constant folding rules for ConstantAggregateZero. 717 } 718} 719 720 721//===----------------------------------------------------------------------===// 722// ConstantFold*Instruction Implementations 723//===----------------------------------------------------------------------===// 724 725/// CastConstantPacked - Convert the specified ConstantPacked node to the 726/// specified packed type. At this point, we know that the elements of the 727/// input packed constant are all simple integer or FP values. 728static Constant *CastConstantPacked(ConstantPacked *CP, 729 const PackedType *DstTy) { 730 unsigned SrcNumElts = CP->getType()->getNumElements(); 731 unsigned DstNumElts = DstTy->getNumElements(); 732 const Type *SrcEltTy = CP->getType()->getElementType(); 733 const Type *DstEltTy = DstTy->getElementType(); 734 735 // If both vectors have the same number of elements (thus, the elements 736 // are the same size), perform the conversion now. 737 if (SrcNumElts == DstNumElts) { 738 std::vector<Constant*> Result; 739 740 // If the src and dest elements are both integers, or both floats, we can 741 // just BitCast each element because the elements are the same size. 742 if ((SrcEltTy->isIntegral() && DstEltTy->isIntegral()) || 743 (SrcEltTy->isFloatingPoint() && DstEltTy->isFloatingPoint())) { 744 for (unsigned i = 0; i != SrcNumElts; ++i) 745 Result.push_back( 746 ConstantExpr::getCast(Instruction::BitCast, CP->getOperand(i), 747 DstEltTy)); 748 return ConstantPacked::get(Result); 749 } 750 751 // If this is an int-to-fp cast .. 752 if (SrcEltTy->isIntegral()) { 753 // Ensure that it is int-to-fp cast 754 assert(DstEltTy->isFloatingPoint()); 755 if (DstEltTy->getTypeID() == Type::DoubleTyID) { 756 for (unsigned i = 0; i != SrcNumElts; ++i) { 757 double V = 758 BitsToDouble(cast<ConstantInt>(CP->getOperand(i))->getZExtValue()); 759 Result.push_back(ConstantFP::get(Type::DoubleTy, V)); 760 } 761 return ConstantPacked::get(Result); 762 } 763 assert(DstEltTy == Type::FloatTy && "Unknown fp type!"); 764 for (unsigned i = 0; i != SrcNumElts; ++i) { 765 float V = 766 BitsToFloat(cast<ConstantInt>(CP->getOperand(i))->getZExtValue()); 767 Result.push_back(ConstantFP::get(Type::FloatTy, V)); 768 } 769 return ConstantPacked::get(Result); 770 } 771 772 // Otherwise, this is an fp-to-int cast. 773 assert(SrcEltTy->isFloatingPoint() && DstEltTy->isIntegral()); 774 775 if (SrcEltTy->getTypeID() == Type::DoubleTyID) { 776 for (unsigned i = 0; i != SrcNumElts; ++i) { 777 uint64_t V = 778 DoubleToBits(cast<ConstantFP>(CP->getOperand(i))->getValue()); 779 Constant *C = ConstantInt::get(Type::ULongTy, V); 780 Result.push_back(ConstantExpr::getCast(C, DstEltTy)); 781 } 782 return ConstantPacked::get(Result); 783 } 784 785 assert(SrcEltTy->getTypeID() == Type::FloatTyID); 786 for (unsigned i = 0; i != SrcNumElts; ++i) { 787 uint32_t V = FloatToBits(cast<ConstantFP>(CP->getOperand(i))->getValue()); 788 Constant *C = ConstantInt::get(Type::UIntTy, V); 789 Result.push_back(ConstantExpr::getCast(C, DstEltTy)); 790 } 791 return ConstantPacked::get(Result); 792 } 793 794 // Otherwise, this is a cast that changes element count and size. Handle 795 // casts which shrink the elements here. 796 797 // FIXME: We need to know endianness to do this! 798 799 return 0; 800} 801 802/// This function determines which opcode to use to fold two constant cast 803/// expressions together. It uses CastInst::isEliminableCastPair to determine 804/// the opcode. Consequently its just a wrapper around that function. 805/// @Determine if it is valid to fold a cast of a cast 806static unsigned 807foldConstantCastPair( 808 unsigned opc, ///< opcode of the second cast constant expression 809 const ConstantExpr*Op, ///< the first cast constant expression 810 const Type *DstTy ///< desintation type of the first cast 811) { 812 assert(Op && Op->isCast() && "Can't fold cast of cast without a cast!"); 813 assert(DstTy && DstTy->isFirstClassType() && "Invalid cast destination type"); 814 assert(CastInst::isCast(opc) && "Invalid cast opcode"); 815 816 // The the types and opcodes for the two Cast constant expressions 817 const Type *SrcTy = Op->getOperand(0)->getType(); 818 const Type *MidTy = Op->getType(); 819 Instruction::CastOps firstOp = Instruction::CastOps(Op->getOpcode()); 820 Instruction::CastOps secondOp = Instruction::CastOps(opc); 821 822 // Let CastInst::isEliminableCastPair do the heavy lifting. 823 return CastInst::isEliminableCastPair(firstOp, secondOp, SrcTy, MidTy, DstTy, 824 Type::ULongTy); 825} 826 827Constant *llvm::ConstantFoldCastInstruction(unsigned opc, const Constant *V, 828 const Type *DestTy) { 829 const Type *SrcTy = V->getType(); 830 831 // Handle some simple cases 832 if (SrcTy == DestTy) 833 return (Constant*)V; // no-op cast 834 835 if (isa<UndefValue>(V)) 836 return UndefValue::get(DestTy); 837 838 // If the cast operand is a constant expression, there's a few things we can 839 // do to try to simplify it. 840 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 841 if (CE->isCast()) { 842 // Try hard to fold cast of cast because they are almost always 843 // eliminable. 844 if (unsigned newOpc = foldConstantCastPair(opc, CE, DestTy)) 845 return ConstantExpr::getCast(newOpc, CE->getOperand(0), DestTy); 846 } else if (CE->getOpcode() == Instruction::GetElementPtr) { 847 // If all of the indexes in the GEP are null values, there is no pointer 848 // adjustment going on. We might as well cast the source pointer. 849 bool isAllNull = true; 850 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i) 851 if (!CE->getOperand(i)->isNullValue()) { 852 isAllNull = false; 853 break; 854 } 855 if (isAllNull) 856 return ConstantExpr::getCast(CE->getOperand(0), DestTy); 857 } 858 } 859 860 // We actually have to do a cast now, but first, we might need to fix up 861 // the value of the operand. 862 switch (opc) { 863 case Instruction::PtrToInt: 864 case Instruction::FPTrunc: 865 case Instruction::FPExt: 866 break; 867 case Instruction::FPToUI: { 868 ConstRules &Rules = ConstRules::get(V, V); 869 V = Rules.castToULong(V); // make sure we get an unsigned value first 870 break; 871 } 872 case Instruction::FPToSI: { 873 ConstRules &Rules = ConstRules::get(V, V); 874 V = Rules.castToLong(V); // make sure we get a signed value first 875 break; 876 } 877 case Instruction::IntToPtr: //always treated as unsigned 878 case Instruction::UIToFP: 879 case Instruction::ZExt: 880 // A ZExt always produces an unsigned value so we need to cast the value 881 // now before we try to cast it to the destination type 882 if (isa<ConstantInt>(V)) 883 V = ConstantInt::get(SrcTy->getUnsignedVersion(), 884 cast<ConstantIntegral>(V)->getZExtValue()); 885 break; 886 case Instruction::SIToFP: 887 case Instruction::SExt: 888 // A SExt always produces a signed value so we need to cast the value 889 // now before we try to cast it to the destiniation type. 890 if (isa<ConstantInt>(V)) 891 V = ConstantInt::get(SrcTy->getSignedVersion(), 892 cast<ConstantIntegral>(V)->getSExtValue()); 893 else if (const ConstantBool *CB = dyn_cast<ConstantBool>(V)) 894 V = ConstantInt::get(Type::SByteTy, CB->getValue() ? -1 : 0); 895 896 break; 897 case Instruction::Trunc: 898 // We just handle trunc directly here. The code below doesn't work for 899 // trunc to bool. 900 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) 901 return ConstantIntegral::get(DestTy, CI->getZExtValue()); 902 return 0; 903 case Instruction::BitCast: 904 // Check to see if we are casting a pointer to an aggregate to a pointer to 905 // the first element. If so, return the appropriate GEP instruction. 906 if (const PointerType *PTy = dyn_cast<PointerType>(V->getType())) 907 if (const PointerType *DPTy = dyn_cast<PointerType>(DestTy)) { 908 std::vector<Value*> IdxList; 909 IdxList.push_back(Constant::getNullValue(Type::IntTy)); 910 const Type *ElTy = PTy->getElementType(); 911 while (ElTy != DPTy->getElementType()) { 912 if (const StructType *STy = dyn_cast<StructType>(ElTy)) { 913 if (STy->getNumElements() == 0) break; 914 ElTy = STy->getElementType(0); 915 IdxList.push_back(Constant::getNullValue(Type::UIntTy)); 916 } else if (const SequentialType *STy = 917 dyn_cast<SequentialType>(ElTy)) { 918 if (isa<PointerType>(ElTy)) break; // Can't index into pointers! 919 ElTy = STy->getElementType(); 920 IdxList.push_back(IdxList[0]); 921 } else { 922 break; 923 } 924 } 925 926 if (ElTy == DPTy->getElementType()) 927 return ConstantExpr::getGetElementPtr( 928 const_cast<Constant*>(V),IdxList); 929 } 930 931 // Handle casts from one packed constant to another. We know that the src 932 // and dest type have the same size (otherwise its an illegal cast). 933 if (const PackedType *DestPTy = dyn_cast<PackedType>(DestTy)) { 934 if (const PackedType *SrcTy = dyn_cast<PackedType>(V->getType())) { 935 assert(DestPTy->getBitWidth() == SrcTy->getBitWidth() && 936 "Not cast between same sized vectors!"); 937 // First, check for null and undef 938 if (isa<ConstantAggregateZero>(V)) 939 return Constant::getNullValue(DestTy); 940 if (isa<UndefValue>(V)) 941 return UndefValue::get(DestTy); 942 943 if (const ConstantPacked *CP = dyn_cast<ConstantPacked>(V)) { 944 // This is a cast from a ConstantPacked of one type to a 945 // ConstantPacked of another type. Check to see if all elements of 946 // the input are simple. 947 bool AllSimpleConstants = true; 948 for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) { 949 if (!isa<ConstantInt>(CP->getOperand(i)) && 950 !isa<ConstantFP>(CP->getOperand(i))) { 951 AllSimpleConstants = false; 952 break; 953 } 954 } 955 956 // If all of the elements are simple constants, we can fold this. 957 if (AllSimpleConstants) 958 return CastConstantPacked(const_cast<ConstantPacked*>(CP), DestPTy); 959 } 960 } 961 } 962 963 // Handle sign conversion for integer no-op casts. We need to cast the 964 // value to the correct signedness before we try to cast it to the 965 // destination type. Be careful to do this only for integer types. 966 if (isa<ConstantIntegral>(V) && SrcTy->isInteger()) { 967 if (SrcTy->isSigned()) 968 V = ConstantInt::get(SrcTy->getUnsignedVersion(), 969 cast<ConstantIntegral>(V)->getZExtValue()); 970 else 971 V = ConstantInt::get(SrcTy->getSignedVersion(), 972 cast<ConstantIntegral>(V)->getSExtValue()); 973 } 974 break; 975 default: 976 assert(!"Invalid CE CastInst opcode"); 977 break; 978 } 979 980 // Okay, no more folding possible, time to cast 981 ConstRules &Rules = ConstRules::get(V, V); 982 switch (DestTy->getTypeID()) { 983 case Type::BoolTyID: return Rules.castToBool(V); 984 case Type::UByteTyID: return Rules.castToUByte(V); 985 case Type::SByteTyID: return Rules.castToSByte(V); 986 case Type::UShortTyID: return Rules.castToUShort(V); 987 case Type::ShortTyID: return Rules.castToShort(V); 988 case Type::UIntTyID: return Rules.castToUInt(V); 989 case Type::IntTyID: return Rules.castToInt(V); 990 case Type::ULongTyID: return Rules.castToULong(V); 991 case Type::LongTyID: return Rules.castToLong(V); 992 case Type::FloatTyID: return Rules.castToFloat(V); 993 case Type::DoubleTyID: return Rules.castToDouble(V); 994 case Type::PointerTyID: 995 return Rules.castToPointer(V, cast<PointerType>(DestTy)); 996 // what about packed ? 997 default: return 0; 998 } 999} 1000 1001Constant *llvm::ConstantFoldSelectInstruction(const Constant *Cond, 1002 const Constant *V1, 1003 const Constant *V2) { 1004 if (const ConstantBool *CB = dyn_cast<ConstantBool>(Cond)) 1005 return const_cast<Constant*>(CB->getValue() ? V1 : V2); 1006 1007 if (isa<UndefValue>(V1)) return const_cast<Constant*>(V2); 1008 if (isa<UndefValue>(V2)) return const_cast<Constant*>(V1); 1009 if (isa<UndefValue>(Cond)) return const_cast<Constant*>(V1); 1010 if (V1 == V2) return const_cast<Constant*>(V1); 1011 return 0; 1012} 1013 1014Constant *llvm::ConstantFoldExtractElementInstruction(const Constant *Val, 1015 const Constant *Idx) { 1016 if (isa<UndefValue>(Val)) // ee(undef, x) -> undef 1017 return UndefValue::get(cast<PackedType>(Val->getType())->getElementType()); 1018 if (Val->isNullValue()) // ee(zero, x) -> zero 1019 return Constant::getNullValue( 1020 cast<PackedType>(Val->getType())->getElementType()); 1021 1022 if (const ConstantPacked *CVal = dyn_cast<ConstantPacked>(Val)) { 1023 if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Idx)) { 1024 return const_cast<Constant*>(CVal->getOperand(CIdx->getZExtValue())); 1025 } else if (isa<UndefValue>(Idx)) { 1026 // ee({w,x,y,z}, undef) -> w (an arbitrary value). 1027 return const_cast<Constant*>(CVal->getOperand(0)); 1028 } 1029 } 1030 return 0; 1031} 1032 1033Constant *llvm::ConstantFoldInsertElementInstruction(const Constant *Val, 1034 const Constant *Elt, 1035 const Constant *Idx) { 1036 const ConstantInt *CIdx = dyn_cast<ConstantInt>(Idx); 1037 if (!CIdx) return 0; 1038 uint64_t idxVal = CIdx->getZExtValue(); 1039 if (isa<UndefValue>(Val)) { 1040 // Insertion of scalar constant into packed undef 1041 // Optimize away insertion of undef 1042 if (isa<UndefValue>(Elt)) 1043 return const_cast<Constant*>(Val); 1044 // Otherwise break the aggregate undef into multiple undefs and do 1045 // the insertion 1046 unsigned numOps = 1047 cast<PackedType>(Val->getType())->getNumElements(); 1048 std::vector<Constant*> Ops; 1049 Ops.reserve(numOps); 1050 for (unsigned i = 0; i < numOps; ++i) { 1051 const Constant *Op = 1052 (i == idxVal) ? Elt : UndefValue::get(Elt->getType()); 1053 Ops.push_back(const_cast<Constant*>(Op)); 1054 } 1055 return ConstantPacked::get(Ops); 1056 } 1057 if (isa<ConstantAggregateZero>(Val)) { 1058 // Insertion of scalar constant into packed aggregate zero 1059 // Optimize away insertion of zero 1060 if (Elt->isNullValue()) 1061 return const_cast<Constant*>(Val); 1062 // Otherwise break the aggregate zero into multiple zeros and do 1063 // the insertion 1064 unsigned numOps = 1065 cast<PackedType>(Val->getType())->getNumElements(); 1066 std::vector<Constant*> Ops; 1067 Ops.reserve(numOps); 1068 for (unsigned i = 0; i < numOps; ++i) { 1069 const Constant *Op = 1070 (i == idxVal) ? Elt : Constant::getNullValue(Elt->getType()); 1071 Ops.push_back(const_cast<Constant*>(Op)); 1072 } 1073 return ConstantPacked::get(Ops); 1074 } 1075 if (const ConstantPacked *CVal = dyn_cast<ConstantPacked>(Val)) { 1076 // Insertion of scalar constant into packed constant 1077 std::vector<Constant*> Ops; 1078 Ops.reserve(CVal->getNumOperands()); 1079 for (unsigned i = 0; i < CVal->getNumOperands(); ++i) { 1080 const Constant *Op = 1081 (i == idxVal) ? Elt : cast<Constant>(CVal->getOperand(i)); 1082 Ops.push_back(const_cast<Constant*>(Op)); 1083 } 1084 return ConstantPacked::get(Ops); 1085 } 1086 return 0; 1087} 1088 1089Constant *llvm::ConstantFoldShuffleVectorInstruction(const Constant *V1, 1090 const Constant *V2, 1091 const Constant *Mask) { 1092 // TODO: 1093 return 0; 1094} 1095 1096 1097/// isZeroSizedType - This type is zero sized if its an array or structure of 1098/// zero sized types. The only leaf zero sized type is an empty structure. 1099static bool isMaybeZeroSizedType(const Type *Ty) { 1100 if (isa<OpaqueType>(Ty)) return true; // Can't say. 1101 if (const StructType *STy = dyn_cast<StructType>(Ty)) { 1102 1103 // If all of elements have zero size, this does too. 1104 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 1105 if (!isMaybeZeroSizedType(STy->getElementType(i))) return false; 1106 return true; 1107 1108 } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 1109 return isMaybeZeroSizedType(ATy->getElementType()); 1110 } 1111 return false; 1112} 1113 1114/// IdxCompare - Compare the two constants as though they were getelementptr 1115/// indices. This allows coersion of the types to be the same thing. 1116/// 1117/// If the two constants are the "same" (after coersion), return 0. If the 1118/// first is less than the second, return -1, if the second is less than the 1119/// first, return 1. If the constants are not integral, return -2. 1120/// 1121static int IdxCompare(Constant *C1, Constant *C2, const Type *ElTy) { 1122 if (C1 == C2) return 0; 1123 1124 // Ok, we found a different index. Are either of the operands ConstantExprs? 1125 // If so, we can't do anything with them. 1126 if (!isa<ConstantInt>(C1) || !isa<ConstantInt>(C2)) 1127 return -2; // don't know! 1128 1129 // Ok, we have two differing integer indices. Sign extend them to be the same 1130 // type. Long is always big enough, so we use it. 1131 if (C1->getType() != Type::LongTy && C1->getType() != Type::ULongTy) 1132 C1 = ConstantExpr::getSignExtend(C1, Type::LongTy); 1133 else 1134 C1 = ConstantExpr::getBitCast(C1, Type::LongTy); 1135 if (C2->getType() != Type::LongTy && C1->getType() != Type::ULongTy) 1136 C2 = ConstantExpr::getSignExtend(C2, Type::LongTy); 1137 else 1138 C2 = ConstantExpr::getBitCast(C2, Type::LongTy); 1139 1140 if (C1 == C2) return 0; // Are they just differing types? 1141 1142 // If the type being indexed over is really just a zero sized type, there is 1143 // no pointer difference being made here. 1144 if (isMaybeZeroSizedType(ElTy)) 1145 return -2; // dunno. 1146 1147 // If they are really different, now that they are the same type, then we 1148 // found a difference! 1149 if (cast<ConstantInt>(C1)->getSExtValue() < 1150 cast<ConstantInt>(C2)->getSExtValue()) 1151 return -1; 1152 else 1153 return 1; 1154} 1155 1156/// evaluateRelation - This function determines if there is anything we can 1157/// decide about the two constants provided. This doesn't need to handle simple 1158/// things like integer comparisons, but should instead handle ConstantExprs 1159/// and GlobalValuess. If we can determine that the two constants have a 1160/// particular relation to each other, we should return the corresponding SetCC 1161/// code, otherwise return Instruction::BinaryOpsEnd. 1162/// 1163/// To simplify this code we canonicalize the relation so that the first 1164/// operand is always the most "complex" of the two. We consider simple 1165/// constants (like ConstantInt) to be the simplest, followed by 1166/// GlobalValues, followed by ConstantExpr's (the most complex). 1167/// 1168static Instruction::BinaryOps evaluateRelation(Constant *V1, Constant *V2) { 1169 assert(V1->getType() == V2->getType() && 1170 "Cannot compare different types of values!"); 1171 if (V1 == V2) return Instruction::SetEQ; 1172 1173 if (!isa<ConstantExpr>(V1) && !isa<GlobalValue>(V1)) { 1174 if (!isa<GlobalValue>(V2) && !isa<ConstantExpr>(V2)) { 1175 // We distilled this down to a simple case, use the standard constant 1176 // folder. 1177 ConstantBool *R = dyn_cast<ConstantBool>(ConstantExpr::getSetEQ(V1, V2)); 1178 if (R && R->getValue()) return Instruction::SetEQ; 1179 R = dyn_cast<ConstantBool>(ConstantExpr::getSetLT(V1, V2)); 1180 if (R && R->getValue()) return Instruction::SetLT; 1181 R = dyn_cast<ConstantBool>(ConstantExpr::getSetGT(V1, V2)); 1182 if (R && R->getValue()) return Instruction::SetGT; 1183 1184 // If we couldn't figure it out, bail. 1185 return Instruction::BinaryOpsEnd; 1186 } 1187 1188 // If the first operand is simple, swap operands. 1189 Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1); 1190 if (SwappedRelation != Instruction::BinaryOpsEnd) 1191 return SetCondInst::getSwappedCondition(SwappedRelation); 1192 1193 } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(V1)) { 1194 if (isa<ConstantExpr>(V2)) { // Swap as necessary. 1195 Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1); 1196 if (SwappedRelation != Instruction::BinaryOpsEnd) 1197 return SetCondInst::getSwappedCondition(SwappedRelation); 1198 else 1199 return Instruction::BinaryOpsEnd; 1200 } 1201 1202 // Now we know that the RHS is a GlobalValue or simple constant, 1203 // which (since the types must match) means that it's a ConstantPointerNull. 1204 if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) { 1205 assert(CPR1 != CPR2 && 1206 "GVs for the same value exist at different addresses??"); 1207 // FIXME: If both globals are external weak, they might both be null! 1208 return Instruction::SetNE; 1209 } else { 1210 assert(isa<ConstantPointerNull>(V2) && "Canonicalization guarantee!"); 1211 // Global can never be null. FIXME: if we implement external weak 1212 // linkage, this is not necessarily true! 1213 return Instruction::SetNE; 1214 } 1215 1216 } else { 1217 // Ok, the LHS is known to be a constantexpr. The RHS can be any of a 1218 // constantexpr, a CPR, or a simple constant. 1219 ConstantExpr *CE1 = cast<ConstantExpr>(V1); 1220 Constant *CE1Op0 = CE1->getOperand(0); 1221 1222 switch (CE1->getOpcode()) { 1223 case Instruction::Trunc: 1224 case Instruction::FPTrunc: 1225 case Instruction::FPExt: 1226 case Instruction::FPToUI: 1227 case Instruction::FPToSI: 1228 break; // We don't do anything with floating point. 1229 case Instruction::ZExt: 1230 case Instruction::SExt: 1231 case Instruction::UIToFP: 1232 case Instruction::SIToFP: 1233 case Instruction::PtrToInt: 1234 case Instruction::IntToPtr: 1235 case Instruction::BitCast: 1236 // If the cast is not actually changing bits, and the second operand is a 1237 // null pointer, do the comparison with the pre-casted value. 1238 if (V2->isNullValue() && 1239 (isa<PointerType>(CE1->getType()) || CE1->getType()->isIntegral())) 1240 return evaluateRelation(CE1Op0, 1241 Constant::getNullValue(CE1Op0->getType())); 1242 1243 // If the dest type is a pointer type, and the RHS is a constantexpr cast 1244 // from the same type as the src of the LHS, evaluate the inputs. This is 1245 // important for things like "seteq (cast 4 to int*), (cast 5 to int*)", 1246 // which happens a lot in compilers with tagged integers. 1247 if (ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2)) 1248 if (isa<PointerType>(CE1->getType()) && CE2->isCast() && 1249 CE1->getOperand(0)->getType() == CE2->getOperand(0)->getType() && 1250 CE1->getOperand(0)->getType()->isIntegral()) { 1251 return evaluateRelation(CE1->getOperand(0), CE2->getOperand(0)); 1252 } 1253 break; 1254 1255 case Instruction::GetElementPtr: 1256 // Ok, since this is a getelementptr, we know that the constant has a 1257 // pointer type. Check the various cases. 1258 if (isa<ConstantPointerNull>(V2)) { 1259 // If we are comparing a GEP to a null pointer, check to see if the base 1260 // of the GEP equals the null pointer. 1261 if (isa<GlobalValue>(CE1Op0)) { 1262 // FIXME: this is not true when we have external weak references! 1263 // No offset can go from a global to a null pointer. 1264 return Instruction::SetGT; 1265 } else if (isa<ConstantPointerNull>(CE1Op0)) { 1266 // If we are indexing from a null pointer, check to see if we have any 1267 // non-zero indices. 1268 for (unsigned i = 1, e = CE1->getNumOperands(); i != e; ++i) 1269 if (!CE1->getOperand(i)->isNullValue()) 1270 // Offsetting from null, must not be equal. 1271 return Instruction::SetGT; 1272 // Only zero indexes from null, must still be zero. 1273 return Instruction::SetEQ; 1274 } 1275 // Otherwise, we can't really say if the first operand is null or not. 1276 } else if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) { 1277 if (isa<ConstantPointerNull>(CE1Op0)) { 1278 // FIXME: This is not true with external weak references. 1279 return Instruction::SetLT; 1280 } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(CE1Op0)) { 1281 if (CPR1 == CPR2) { 1282 // If this is a getelementptr of the same global, then it must be 1283 // different. Because the types must match, the getelementptr could 1284 // only have at most one index, and because we fold getelementptr's 1285 // with a single zero index, it must be nonzero. 1286 assert(CE1->getNumOperands() == 2 && 1287 !CE1->getOperand(1)->isNullValue() && 1288 "Suprising getelementptr!"); 1289 return Instruction::SetGT; 1290 } else { 1291 // If they are different globals, we don't know what the value is, 1292 // but they can't be equal. 1293 return Instruction::SetNE; 1294 } 1295 } 1296 } else { 1297 const ConstantExpr *CE2 = cast<ConstantExpr>(V2); 1298 const Constant *CE2Op0 = CE2->getOperand(0); 1299 1300 // There are MANY other foldings that we could perform here. They will 1301 // probably be added on demand, as they seem needed. 1302 switch (CE2->getOpcode()) { 1303 default: break; 1304 case Instruction::GetElementPtr: 1305 // By far the most common case to handle is when the base pointers are 1306 // obviously to the same or different globals. 1307 if (isa<GlobalValue>(CE1Op0) && isa<GlobalValue>(CE2Op0)) { 1308 if (CE1Op0 != CE2Op0) // Don't know relative ordering, but not equal 1309 return Instruction::SetNE; 1310 // Ok, we know that both getelementptr instructions are based on the 1311 // same global. From this, we can precisely determine the relative 1312 // ordering of the resultant pointers. 1313 unsigned i = 1; 1314 1315 // Compare all of the operands the GEP's have in common. 1316 gep_type_iterator GTI = gep_type_begin(CE1); 1317 for (;i != CE1->getNumOperands() && i != CE2->getNumOperands(); 1318 ++i, ++GTI) 1319 switch (IdxCompare(CE1->getOperand(i), CE2->getOperand(i), 1320 GTI.getIndexedType())) { 1321 case -1: return Instruction::SetLT; 1322 case 1: return Instruction::SetGT; 1323 case -2: return Instruction::BinaryOpsEnd; 1324 } 1325 1326 // Ok, we ran out of things they have in common. If any leftovers 1327 // are non-zero then we have a difference, otherwise we are equal. 1328 for (; i < CE1->getNumOperands(); ++i) 1329 if (!CE1->getOperand(i)->isNullValue()) 1330 if (isa<ConstantIntegral>(CE1->getOperand(i))) 1331 return Instruction::SetGT; 1332 else 1333 return Instruction::BinaryOpsEnd; // Might be equal. 1334 1335 for (; i < CE2->getNumOperands(); ++i) 1336 if (!CE2->getOperand(i)->isNullValue()) 1337 if (isa<ConstantIntegral>(CE2->getOperand(i))) 1338 return Instruction::SetLT; 1339 else 1340 return Instruction::BinaryOpsEnd; // Might be equal. 1341 return Instruction::SetEQ; 1342 } 1343 } 1344 } 1345 1346 default: 1347 break; 1348 } 1349 } 1350 1351 return Instruction::BinaryOpsEnd; 1352} 1353 1354Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode, 1355 const Constant *V1, 1356 const Constant *V2) { 1357 Constant *C = 0; 1358 switch (Opcode) { 1359 default: break; 1360 case Instruction::Add: C = ConstRules::get(V1, V2).add(V1, V2); break; 1361 case Instruction::Sub: C = ConstRules::get(V1, V2).sub(V1, V2); break; 1362 case Instruction::Mul: C = ConstRules::get(V1, V2).mul(V1, V2); break; 1363 case Instruction::UDiv: C = ConstRules::get(V1, V2).udiv(V1, V2); break; 1364 case Instruction::SDiv: C = ConstRules::get(V1, V2).sdiv(V1, V2); break; 1365 case Instruction::FDiv: C = ConstRules::get(V1, V2).fdiv(V1, V2); break; 1366 case Instruction::URem: C = ConstRules::get(V1, V2).urem(V1, V2); break; 1367 case Instruction::SRem: C = ConstRules::get(V1, V2).srem(V1, V2); break; 1368 case Instruction::FRem: C = ConstRules::get(V1, V2).frem(V1, V2); break; 1369 case Instruction::And: C = ConstRules::get(V1, V2).op_and(V1, V2); break; 1370 case Instruction::Or: C = ConstRules::get(V1, V2).op_or (V1, V2); break; 1371 case Instruction::Xor: C = ConstRules::get(V1, V2).op_xor(V1, V2); break; 1372 case Instruction::Shl: C = ConstRules::get(V1, V2).shl(V1, V2); break; 1373 case Instruction::LShr: C = ConstRules::get(V1, V2).lshr(V1, V2); break; 1374 case Instruction::AShr: C = ConstRules::get(V1, V2).ashr(V1, V2); break; 1375 case Instruction::SetEQ: 1376 // SetEQ(null,GV) -> false 1377 if (V1->isNullValue()) { 1378 if (const GlobalValue *GV = dyn_cast<GlobalValue>(V2)) 1379 if (!GV->hasExternalWeakLinkage()) 1380 return ConstantBool::getFalse(); 1381 // SetEQ(GV,null) -> false 1382 } else if (V2->isNullValue()) { 1383 if (const GlobalValue *GV = dyn_cast<GlobalValue>(V1)) 1384 if (!GV->hasExternalWeakLinkage()) 1385 return ConstantBool::getFalse(); 1386 } 1387 C = ConstRules::get(V1, V2).equalto(V1, V2); 1388 break; 1389 case Instruction::SetLT: C = ConstRules::get(V1, V2).lessthan(V1, V2);break; 1390 case Instruction::SetGT: C = ConstRules::get(V1, V2).lessthan(V2, V1);break; 1391 case Instruction::SetNE: 1392 // SetNE(null,GV) -> true 1393 if (V1->isNullValue()) { 1394 if (const GlobalValue *GV = dyn_cast<GlobalValue>(V2)) 1395 if (!GV->hasExternalWeakLinkage()) 1396 return ConstantBool::getTrue(); 1397 // SetNE(GV,null) -> true 1398 } else if (V2->isNullValue()) { 1399 if (const GlobalValue *GV = dyn_cast<GlobalValue>(V1)) 1400 if (!GV->hasExternalWeakLinkage()) 1401 return ConstantBool::getTrue(); 1402 } 1403 // V1 != V2 === !(V1 == V2) 1404 C = ConstRules::get(V1, V2).equalto(V1, V2); 1405 if (C) return ConstantExpr::getNot(C); 1406 break; 1407 case Instruction::SetLE: // V1 <= V2 === !(V2 < V1) 1408 C = ConstRules::get(V1, V2).lessthan(V2, V1); 1409 if (C) return ConstantExpr::getNot(C); 1410 break; 1411 case Instruction::SetGE: // V1 >= V2 === !(V1 < V2) 1412 C = ConstRules::get(V1, V2).lessthan(V1, V2); 1413 if (C) return ConstantExpr::getNot(C); 1414 break; 1415 } 1416 1417 // If we successfully folded the expression, return it now. 1418 if (C) return C; 1419 1420 if (SetCondInst::isComparison(Opcode)) { 1421 if (isa<UndefValue>(V1) || isa<UndefValue>(V2)) 1422 return UndefValue::get(Type::BoolTy); 1423 switch (evaluateRelation(const_cast<Constant*>(V1), 1424 const_cast<Constant*>(V2))) { 1425 default: assert(0 && "Unknown relational!"); 1426 case Instruction::BinaryOpsEnd: 1427 break; // Couldn't determine anything about these constants. 1428 case Instruction::SetEQ: // We know the constants are equal! 1429 // If we know the constants are equal, we can decide the result of this 1430 // computation precisely. 1431 return ConstantBool::get(Opcode == Instruction::SetEQ || 1432 Opcode == Instruction::SetLE || 1433 Opcode == Instruction::SetGE); 1434 case Instruction::SetLT: 1435 // If we know that V1 < V2, we can decide the result of this computation 1436 // precisely. 1437 return ConstantBool::get(Opcode == Instruction::SetLT || 1438 Opcode == Instruction::SetNE || 1439 Opcode == Instruction::SetLE); 1440 case Instruction::SetGT: 1441 // If we know that V1 > V2, we can decide the result of this computation 1442 // precisely. 1443 return ConstantBool::get(Opcode == Instruction::SetGT || 1444 Opcode == Instruction::SetNE || 1445 Opcode == Instruction::SetGE); 1446 case Instruction::SetLE: 1447 // If we know that V1 <= V2, we can only partially decide this relation. 1448 if (Opcode == Instruction::SetGT) return ConstantBool::getFalse(); 1449 if (Opcode == Instruction::SetLT) return ConstantBool::getTrue(); 1450 break; 1451 1452 case Instruction::SetGE: 1453 // If we know that V1 >= V2, we can only partially decide this relation. 1454 if (Opcode == Instruction::SetLT) return ConstantBool::getFalse(); 1455 if (Opcode == Instruction::SetGT) return ConstantBool::getTrue(); 1456 break; 1457 1458 case Instruction::SetNE: 1459 // If we know that V1 != V2, we can only partially decide this relation. 1460 if (Opcode == Instruction::SetEQ) return ConstantBool::getFalse(); 1461 if (Opcode == Instruction::SetNE) return ConstantBool::getTrue(); 1462 break; 1463 } 1464 } 1465 1466 if (isa<UndefValue>(V1) || isa<UndefValue>(V2)) { 1467 switch (Opcode) { 1468 case Instruction::Add: 1469 case Instruction::Sub: 1470 case Instruction::Xor: 1471 return UndefValue::get(V1->getType()); 1472 1473 case Instruction::Mul: 1474 case Instruction::And: 1475 return Constant::getNullValue(V1->getType()); 1476 case Instruction::UDiv: 1477 case Instruction::SDiv: 1478 case Instruction::FDiv: 1479 case Instruction::URem: 1480 case Instruction::SRem: 1481 case Instruction::FRem: 1482 if (!isa<UndefValue>(V2)) // undef / X -> 0 1483 return Constant::getNullValue(V1->getType()); 1484 return const_cast<Constant*>(V2); // X / undef -> undef 1485 case Instruction::Or: // X | undef -> -1 1486 return ConstantInt::getAllOnesValue(V1->getType()); 1487 case Instruction::LShr: 1488 if (isa<UndefValue>(V2) && isa<UndefValue>(V1)) 1489 return const_cast<Constant*>(V1); // undef lshr undef -> undef 1490 return Constant::getNullValue(V1->getType()); // X lshr undef -> 0 1491 // undef lshr X -> 0 1492 case Instruction::AShr: 1493 if (!isa<UndefValue>(V2)) 1494 return const_cast<Constant*>(V1); // undef ashr X --> undef 1495 else if (isa<UndefValue>(V1)) 1496 return const_cast<Constant*>(V1); // undef ashr undef -> undef 1497 else 1498 return const_cast<Constant*>(V1); // X ashr undef --> X 1499 case Instruction::Shl: 1500 // undef << X -> 0 or X << undef -> 0 1501 return Constant::getNullValue(V1->getType()); 1502 } 1503 } 1504 1505 if (const ConstantExpr *CE1 = dyn_cast<ConstantExpr>(V1)) { 1506 if (isa<ConstantExpr>(V2)) { 1507 // There are many possible foldings we could do here. We should probably 1508 // at least fold add of a pointer with an integer into the appropriate 1509 // getelementptr. This will improve alias analysis a bit. 1510 } else { 1511 // Just implement a couple of simple identities. 1512 switch (Opcode) { 1513 case Instruction::Add: 1514 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X + 0 == X 1515 break; 1516 case Instruction::Sub: 1517 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X - 0 == X 1518 break; 1519 case Instruction::Mul: 1520 if (V2->isNullValue()) return const_cast<Constant*>(V2); // X * 0 == 0 1521 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2)) 1522 if (CI->getZExtValue() == 1) 1523 return const_cast<Constant*>(V1); // X * 1 == X 1524 break; 1525 case Instruction::UDiv: 1526 case Instruction::SDiv: 1527 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2)) 1528 if (CI->getZExtValue() == 1) 1529 return const_cast<Constant*>(V1); // X / 1 == X 1530 break; 1531 case Instruction::URem: 1532 case Instruction::SRem: 1533 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2)) 1534 if (CI->getZExtValue() == 1) 1535 return Constant::getNullValue(CI->getType()); // X % 1 == 0 1536 break; 1537 case Instruction::And: 1538 if (cast<ConstantIntegral>(V2)->isAllOnesValue()) 1539 return const_cast<Constant*>(V1); // X & -1 == X 1540 if (V2->isNullValue()) return const_cast<Constant*>(V2); // X & 0 == 0 1541 if (CE1->isCast() && isa<GlobalValue>(CE1->getOperand(0))) { 1542 GlobalValue *CPR = cast<GlobalValue>(CE1->getOperand(0)); 1543 1544 // Functions are at least 4-byte aligned. If and'ing the address of a 1545 // function with a constant < 4, fold it to zero. 1546 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2)) 1547 if (CI->getZExtValue() < 4 && isa<Function>(CPR)) 1548 return Constant::getNullValue(CI->getType()); 1549 } 1550 break; 1551 case Instruction::Or: 1552 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X | 0 == X 1553 if (cast<ConstantIntegral>(V2)->isAllOnesValue()) 1554 return const_cast<Constant*>(V2); // X | -1 == -1 1555 break; 1556 case Instruction::Xor: 1557 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X ^ 0 == X 1558 break; 1559 } 1560 } 1561 1562 } else if (isa<ConstantExpr>(V2)) { 1563 // If V2 is a constant expr and V1 isn't, flop them around and fold the 1564 // other way if possible. 1565 switch (Opcode) { 1566 case Instruction::Add: 1567 case Instruction::Mul: 1568 case Instruction::And: 1569 case Instruction::Or: 1570 case Instruction::Xor: 1571 case Instruction::SetEQ: 1572 case Instruction::SetNE: 1573 // No change of opcode required. 1574 return ConstantFoldBinaryInstruction(Opcode, V2, V1); 1575 1576 case Instruction::SetLT: 1577 case Instruction::SetGT: 1578 case Instruction::SetLE: 1579 case Instruction::SetGE: 1580 // Change the opcode as necessary to swap the operands. 1581 Opcode = SetCondInst::getSwappedCondition((Instruction::BinaryOps)Opcode); 1582 return ConstantFoldBinaryInstruction(Opcode, V2, V1); 1583 1584 case Instruction::Shl: 1585 case Instruction::LShr: 1586 case Instruction::AShr: 1587 case Instruction::Sub: 1588 case Instruction::SDiv: 1589 case Instruction::UDiv: 1590 case Instruction::FDiv: 1591 case Instruction::URem: 1592 case Instruction::SRem: 1593 case Instruction::FRem: 1594 default: // These instructions cannot be flopped around. 1595 break; 1596 } 1597 } 1598 return 0; 1599} 1600 1601Constant *llvm::ConstantFoldGetElementPtr(const Constant *C, 1602 const std::vector<Value*> &IdxList) { 1603 if (IdxList.size() == 0 || 1604 (IdxList.size() == 1 && cast<Constant>(IdxList[0])->isNullValue())) 1605 return const_cast<Constant*>(C); 1606 1607 if (isa<UndefValue>(C)) { 1608 const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList, 1609 true); 1610 assert(Ty != 0 && "Invalid indices for GEP!"); 1611 return UndefValue::get(PointerType::get(Ty)); 1612 } 1613 1614 Constant *Idx0 = cast<Constant>(IdxList[0]); 1615 if (C->isNullValue()) { 1616 bool isNull = true; 1617 for (unsigned i = 0, e = IdxList.size(); i != e; ++i) 1618 if (!cast<Constant>(IdxList[i])->isNullValue()) { 1619 isNull = false; 1620 break; 1621 } 1622 if (isNull) { 1623 const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList, 1624 true); 1625 assert(Ty != 0 && "Invalid indices for GEP!"); 1626 return ConstantPointerNull::get(PointerType::get(Ty)); 1627 } 1628 1629 if (IdxList.size() == 1) { 1630 const Type *ElTy = cast<PointerType>(C->getType())->getElementType(); 1631 if (uint32_t ElSize = ElTy->getPrimitiveSize()) { 1632 // gep null, C is equal to C*sizeof(nullty). If nullty is a known llvm 1633 // type, we can statically fold this. 1634 Constant *R = ConstantInt::get(Type::UIntTy, ElSize); 1635 R = ConstantExpr::getCast(R, Idx0->getType()); 1636 R = ConstantExpr::getMul(R, Idx0); 1637 return ConstantExpr::getCast(R, C->getType()); 1638 } 1639 } 1640 } 1641 1642 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(const_cast<Constant*>(C))) { 1643 // Combine Indices - If the source pointer to this getelementptr instruction 1644 // is a getelementptr instruction, combine the indices of the two 1645 // getelementptr instructions into a single instruction. 1646 // 1647 if (CE->getOpcode() == Instruction::GetElementPtr) { 1648 const Type *LastTy = 0; 1649 for (gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE); 1650 I != E; ++I) 1651 LastTy = *I; 1652 1653 if ((LastTy && isa<ArrayType>(LastTy)) || Idx0->isNullValue()) { 1654 std::vector<Value*> NewIndices; 1655 NewIndices.reserve(IdxList.size() + CE->getNumOperands()); 1656 for (unsigned i = 1, e = CE->getNumOperands()-1; i != e; ++i) 1657 NewIndices.push_back(CE->getOperand(i)); 1658 1659 // Add the last index of the source with the first index of the new GEP. 1660 // Make sure to handle the case when they are actually different types. 1661 Constant *Combined = CE->getOperand(CE->getNumOperands()-1); 1662 // Otherwise it must be an array. 1663 if (!Idx0->isNullValue()) { 1664 const Type *IdxTy = Combined->getType(); 1665 if (IdxTy != Idx0->getType()) IdxTy = Type::LongTy; 1666 Combined = 1667 ConstantExpr::get(Instruction::Add, 1668 ConstantExpr::getCast(Idx0, IdxTy), 1669 ConstantExpr::getCast(Combined, IdxTy)); 1670 } 1671 1672 NewIndices.push_back(Combined); 1673 NewIndices.insert(NewIndices.end(), IdxList.begin()+1, IdxList.end()); 1674 return ConstantExpr::getGetElementPtr(CE->getOperand(0), NewIndices); 1675 } 1676 } 1677 1678 // Implement folding of: 1679 // int* getelementptr ([2 x int]* cast ([3 x int]* %X to [2 x int]*), 1680 // long 0, long 0) 1681 // To: int* getelementptr ([3 x int]* %X, long 0, long 0) 1682 // 1683 if (CE->isCast() && IdxList.size() > 1 && Idx0->isNullValue()) 1684 if (const PointerType *SPT = 1685 dyn_cast<PointerType>(CE->getOperand(0)->getType())) 1686 if (const ArrayType *SAT = dyn_cast<ArrayType>(SPT->getElementType())) 1687 if (const ArrayType *CAT = 1688 dyn_cast<ArrayType>(cast<PointerType>(C->getType())->getElementType())) 1689 if (CAT->getElementType() == SAT->getElementType()) 1690 return ConstantExpr::getGetElementPtr( 1691 (Constant*)CE->getOperand(0), IdxList); 1692 } 1693 return 0; 1694} 1695 1696