LLVM API Documentation
00001 //===- ConstantFolding.cpp - LLVM constant folder -------------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements folding of constants for LLVM. This implements the 00011 // (internal) ConstantFolding.h interface, which is used by the 00012 // ConstantExpr::get* methods to automatically fold constants when possible. 00013 // 00014 // The current constant folding implementation is implemented in two pieces: the 00015 // template-based folder for simple primitive constants like ConstantInt, and 00016 // the special case hackery that we use to symbolically evaluate expressions 00017 // that use ConstantExprs. 00018 // 00019 //===----------------------------------------------------------------------===// 00020 00021 #include "ConstantFolding.h" 00022 #include "llvm/Constants.h" 00023 #include "llvm/Instructions.h" 00024 #include "llvm/DerivedTypes.h" 00025 #include "llvm/Function.h" 00026 #include "llvm/Support/GetElementPtrTypeIterator.h" 00027 #include "llvm/Support/MathExtras.h" 00028 #include "llvm/Support/Visibility.h" 00029 #include <limits> 00030 #include <cmath> 00031 using namespace llvm; 00032 00033 namespace { 00034 struct VISIBILITY_HIDDEN ConstRules { 00035 ConstRules() {} 00036 virtual ~ConstRules() {} 00037 00038 // Binary Operators... 00039 virtual Constant *add(const Constant *V1, const Constant *V2) const = 0; 00040 virtual Constant *sub(const Constant *V1, const Constant *V2) const = 0; 00041 virtual Constant *mul(const Constant *V1, const Constant *V2) const = 0; 00042 virtual Constant *div(const Constant *V1, const Constant *V2) const = 0; 00043 virtual Constant *rem(const Constant *V1, const Constant *V2) const = 0; 00044 virtual Constant *op_and(const Constant *V1, const Constant *V2) const = 0; 00045 virtual Constant *op_or (const Constant *V1, const Constant *V2) const = 0; 00046 virtual Constant *op_xor(const Constant *V1, const Constant *V2) const = 0; 00047 virtual Constant *shl(const Constant *V1, const Constant *V2) const = 0; 00048 virtual Constant *shr(const Constant *V1, const Constant *V2) const = 0; 00049 virtual Constant *lessthan(const Constant *V1, const Constant *V2) const =0; 00050 virtual Constant *equalto(const Constant *V1, const Constant *V2) const = 0; 00051 00052 // Casting operators. 00053 virtual Constant *castToBool (const Constant *V) const = 0; 00054 virtual Constant *castToSByte (const Constant *V) const = 0; 00055 virtual Constant *castToUByte (const Constant *V) const = 0; 00056 virtual Constant *castToShort (const Constant *V) const = 0; 00057 virtual Constant *castToUShort(const Constant *V) const = 0; 00058 virtual Constant *castToInt (const Constant *V) const = 0; 00059 virtual Constant *castToUInt (const Constant *V) const = 0; 00060 virtual Constant *castToLong (const Constant *V) const = 0; 00061 virtual Constant *castToULong (const Constant *V) const = 0; 00062 virtual Constant *castToFloat (const Constant *V) const = 0; 00063 virtual Constant *castToDouble(const Constant *V) const = 0; 00064 virtual Constant *castToPointer(const Constant *V, 00065 const PointerType *Ty) const = 0; 00066 00067 // ConstRules::get - Return an instance of ConstRules for the specified 00068 // constant operands. 00069 // 00070 static ConstRules &get(const Constant *V1, const Constant *V2); 00071 private: 00072 ConstRules(const ConstRules &); // Do not implement 00073 ConstRules &operator=(const ConstRules &); // Do not implement 00074 }; 00075 } 00076 00077 00078 //===----------------------------------------------------------------------===// 00079 // TemplateRules Class 00080 //===----------------------------------------------------------------------===// 00081 // 00082 // TemplateRules - Implement a subclass of ConstRules that provides all 00083 // operations as noops. All other rules classes inherit from this class so 00084 // that if functionality is needed in the future, it can simply be added here 00085 // and to ConstRules without changing anything else... 00086 // 00087 // This class also provides subclasses with typesafe implementations of methods 00088 // so that don't have to do type casting. 00089 // 00090 namespace { 00091 template<class ArgType, class SubClassName> 00092 class VISIBILITY_HIDDEN TemplateRules : public ConstRules { 00093 00094 00095 //===--------------------------------------------------------------------===// 00096 // Redirecting functions that cast to the appropriate types 00097 //===--------------------------------------------------------------------===// 00098 00099 virtual Constant *add(const Constant *V1, const Constant *V2) const { 00100 return SubClassName::Add((const ArgType *)V1, (const ArgType *)V2); 00101 } 00102 virtual Constant *sub(const Constant *V1, const Constant *V2) const { 00103 return SubClassName::Sub((const ArgType *)V1, (const ArgType *)V2); 00104 } 00105 virtual Constant *mul(const Constant *V1, const Constant *V2) const { 00106 return SubClassName::Mul((const ArgType *)V1, (const ArgType *)V2); 00107 } 00108 virtual Constant *div(const Constant *V1, const Constant *V2) const { 00109 return SubClassName::Div((const ArgType *)V1, (const ArgType *)V2); 00110 } 00111 virtual Constant *rem(const Constant *V1, const Constant *V2) const { 00112 return SubClassName::Rem((const ArgType *)V1, (const ArgType *)V2); 00113 } 00114 virtual Constant *op_and(const Constant *V1, const Constant *V2) const { 00115 return SubClassName::And((const ArgType *)V1, (const ArgType *)V2); 00116 } 00117 virtual Constant *op_or(const Constant *V1, const Constant *V2) const { 00118 return SubClassName::Or((const ArgType *)V1, (const ArgType *)V2); 00119 } 00120 virtual Constant *op_xor(const Constant *V1, const Constant *V2) const { 00121 return SubClassName::Xor((const ArgType *)V1, (const ArgType *)V2); 00122 } 00123 virtual Constant *shl(const Constant *V1, const Constant *V2) const { 00124 return SubClassName::Shl((const ArgType *)V1, (const ArgType *)V2); 00125 } 00126 virtual Constant *shr(const Constant *V1, const Constant *V2) const { 00127 return SubClassName::Shr((const ArgType *)V1, (const ArgType *)V2); 00128 } 00129 00130 virtual Constant *lessthan(const Constant *V1, const Constant *V2) const { 00131 return SubClassName::LessThan((const ArgType *)V1, (const ArgType *)V2); 00132 } 00133 virtual Constant *equalto(const Constant *V1, const Constant *V2) const { 00134 return SubClassName::EqualTo((const ArgType *)V1, (const ArgType *)V2); 00135 } 00136 00137 // Casting operators. ick 00138 virtual Constant *castToBool(const Constant *V) const { 00139 return SubClassName::CastToBool((const ArgType*)V); 00140 } 00141 virtual Constant *castToSByte(const Constant *V) const { 00142 return SubClassName::CastToSByte((const ArgType*)V); 00143 } 00144 virtual Constant *castToUByte(const Constant *V) const { 00145 return SubClassName::CastToUByte((const ArgType*)V); 00146 } 00147 virtual Constant *castToShort(const Constant *V) const { 00148 return SubClassName::CastToShort((const ArgType*)V); 00149 } 00150 virtual Constant *castToUShort(const Constant *V) const { 00151 return SubClassName::CastToUShort((const ArgType*)V); 00152 } 00153 virtual Constant *castToInt(const Constant *V) const { 00154 return SubClassName::CastToInt((const ArgType*)V); 00155 } 00156 virtual Constant *castToUInt(const Constant *V) const { 00157 return SubClassName::CastToUInt((const ArgType*)V); 00158 } 00159 virtual Constant *castToLong(const Constant *V) const { 00160 return SubClassName::CastToLong((const ArgType*)V); 00161 } 00162 virtual Constant *castToULong(const Constant *V) const { 00163 return SubClassName::CastToULong((const ArgType*)V); 00164 } 00165 virtual Constant *castToFloat(const Constant *V) const { 00166 return SubClassName::CastToFloat((const ArgType*)V); 00167 } 00168 virtual Constant *castToDouble(const Constant *V) const { 00169 return SubClassName::CastToDouble((const ArgType*)V); 00170 } 00171 virtual Constant *castToPointer(const Constant *V, 00172 const PointerType *Ty) const { 00173 return SubClassName::CastToPointer((const ArgType*)V, Ty); 00174 } 00175 00176 //===--------------------------------------------------------------------===// 00177 // Default "noop" implementations 00178 //===--------------------------------------------------------------------===// 00179 00180 static Constant *Add(const ArgType *V1, const ArgType *V2) { return 0; } 00181 static Constant *Sub(const ArgType *V1, const ArgType *V2) { return 0; } 00182 static Constant *Mul(const ArgType *V1, const ArgType *V2) { return 0; } 00183 static Constant *Div(const ArgType *V1, const ArgType *V2) { return 0; } 00184 static Constant *Rem(const ArgType *V1, const ArgType *V2) { return 0; } 00185 static Constant *And(const ArgType *V1, const ArgType *V2) { return 0; } 00186 static Constant *Or (const ArgType *V1, const ArgType *V2) { return 0; } 00187 static Constant *Xor(const ArgType *V1, const ArgType *V2) { return 0; } 00188 static Constant *Shl(const ArgType *V1, const ArgType *V2) { return 0; } 00189 static Constant *Shr(const ArgType *V1, const ArgType *V2) { return 0; } 00190 static Constant *LessThan(const ArgType *V1, const ArgType *V2) { 00191 return 0; 00192 } 00193 static Constant *EqualTo(const ArgType *V1, const ArgType *V2) { 00194 return 0; 00195 } 00196 00197 // Casting operators. ick 00198 static Constant *CastToBool (const Constant *V) { return 0; } 00199 static Constant *CastToSByte (const Constant *V) { return 0; } 00200 static Constant *CastToUByte (const Constant *V) { return 0; } 00201 static Constant *CastToShort (const Constant *V) { return 0; } 00202 static Constant *CastToUShort(const Constant *V) { return 0; } 00203 static Constant *CastToInt (const Constant *V) { return 0; } 00204 static Constant *CastToUInt (const Constant *V) { return 0; } 00205 static Constant *CastToLong (const Constant *V) { return 0; } 00206 static Constant *CastToULong (const Constant *V) { return 0; } 00207 static Constant *CastToFloat (const Constant *V) { return 0; } 00208 static Constant *CastToDouble(const Constant *V) { return 0; } 00209 static Constant *CastToPointer(const Constant *, 00210 const PointerType *) {return 0;} 00211 00212 public: 00213 virtual ~TemplateRules() {} 00214 }; 00215 } // end anonymous namespace 00216 00217 00218 //===----------------------------------------------------------------------===// 00219 // EmptyRules Class 00220 //===----------------------------------------------------------------------===// 00221 // 00222 // EmptyRules provides a concrete base class of ConstRules that does nothing 00223 // 00224 namespace { 00225 struct VISIBILITY_HIDDEN EmptyRules 00226 : public TemplateRules<Constant, EmptyRules> { 00227 static Constant *EqualTo(const Constant *V1, const Constant *V2) { 00228 if (V1 == V2) return ConstantBool::True; 00229 return 0; 00230 } 00231 }; 00232 } // end anonymous namespace 00233 00234 00235 00236 //===----------------------------------------------------------------------===// 00237 // BoolRules Class 00238 //===----------------------------------------------------------------------===// 00239 // 00240 // BoolRules provides a concrete base class of ConstRules for the 'bool' type. 00241 // 00242 namespace { 00243 struct VISIBILITY_HIDDEN BoolRules 00244 : public TemplateRules<ConstantBool, BoolRules> { 00245 00246 static Constant *LessThan(const ConstantBool *V1, const ConstantBool *V2) { 00247 return ConstantBool::get(V1->getValue() < V2->getValue()); 00248 } 00249 00250 static Constant *EqualTo(const Constant *V1, const Constant *V2) { 00251 return ConstantBool::get(V1 == V2); 00252 } 00253 00254 static Constant *And(const ConstantBool *V1, const ConstantBool *V2) { 00255 return ConstantBool::get(V1->getValue() & V2->getValue()); 00256 } 00257 00258 static Constant *Or(const ConstantBool *V1, const ConstantBool *V2) { 00259 return ConstantBool::get(V1->getValue() | V2->getValue()); 00260 } 00261 00262 static Constant *Xor(const ConstantBool *V1, const ConstantBool *V2) { 00263 return ConstantBool::get(V1->getValue() ^ V2->getValue()); 00264 } 00265 00266 // Casting operators. ick 00267 #define DEF_CAST(TYPE, CLASS, CTYPE) \ 00268 static Constant *CastTo##TYPE (const ConstantBool *V) { \ 00269 return CLASS::get(Type::TYPE##Ty, (CTYPE)(bool)V->getValue()); \ 00270 } 00271 00272 DEF_CAST(Bool , ConstantBool, bool) 00273 DEF_CAST(SByte , ConstantSInt, signed char) 00274 DEF_CAST(UByte , ConstantUInt, unsigned char) 00275 DEF_CAST(Short , ConstantSInt, signed short) 00276 DEF_CAST(UShort, ConstantUInt, unsigned short) 00277 DEF_CAST(Int , ConstantSInt, signed int) 00278 DEF_CAST(UInt , ConstantUInt, unsigned int) 00279 DEF_CAST(Long , ConstantSInt, int64_t) 00280 DEF_CAST(ULong , ConstantUInt, uint64_t) 00281 DEF_CAST(Float , ConstantFP , float) 00282 DEF_CAST(Double, ConstantFP , double) 00283 #undef DEF_CAST 00284 }; 00285 } // end anonymous namespace 00286 00287 00288 //===----------------------------------------------------------------------===// 00289 // NullPointerRules Class 00290 //===----------------------------------------------------------------------===// 00291 // 00292 // NullPointerRules provides a concrete base class of ConstRules for null 00293 // pointers. 00294 // 00295 namespace { 00296 struct VISIBILITY_HIDDEN NullPointerRules 00297 : public TemplateRules<ConstantPointerNull, NullPointerRules> { 00298 static Constant *EqualTo(const Constant *V1, const Constant *V2) { 00299 return ConstantBool::True; // Null pointers are always equal 00300 } 00301 static Constant *CastToBool(const Constant *V) { 00302 return ConstantBool::False; 00303 } 00304 static Constant *CastToSByte (const Constant *V) { 00305 return ConstantSInt::get(Type::SByteTy, 0); 00306 } 00307 static Constant *CastToUByte (const Constant *V) { 00308 return ConstantUInt::get(Type::UByteTy, 0); 00309 } 00310 static Constant *CastToShort (const Constant *V) { 00311 return ConstantSInt::get(Type::ShortTy, 0); 00312 } 00313 static Constant *CastToUShort(const Constant *V) { 00314 return ConstantUInt::get(Type::UShortTy, 0); 00315 } 00316 static Constant *CastToInt (const Constant *V) { 00317 return ConstantSInt::get(Type::IntTy, 0); 00318 } 00319 static Constant *CastToUInt (const Constant *V) { 00320 return ConstantUInt::get(Type::UIntTy, 0); 00321 } 00322 static Constant *CastToLong (const Constant *V) { 00323 return ConstantSInt::get(Type::LongTy, 0); 00324 } 00325 static Constant *CastToULong (const Constant *V) { 00326 return ConstantUInt::get(Type::ULongTy, 0); 00327 } 00328 static Constant *CastToFloat (const Constant *V) { 00329 return ConstantFP::get(Type::FloatTy, 0); 00330 } 00331 static Constant *CastToDouble(const Constant *V) { 00332 return ConstantFP::get(Type::DoubleTy, 0); 00333 } 00334 00335 static Constant *CastToPointer(const ConstantPointerNull *V, 00336 const PointerType *PTy) { 00337 return ConstantPointerNull::get(PTy); 00338 } 00339 }; 00340 } // end anonymous namespace 00341 00342 //===----------------------------------------------------------------------===// 00343 // ConstantPackedRules Class 00344 //===----------------------------------------------------------------------===// 00345 00346 /// DoVectorOp - Given two packed constants and a function pointer, apply the 00347 /// function pointer to each element pair, producing a new ConstantPacked 00348 /// constant. 00349 static Constant *EvalVectorOp(const ConstantPacked *V1, 00350 const ConstantPacked *V2, 00351 Constant *(*FP)(Constant*, Constant*)) { 00352 std::vector<Constant*> Res; 00353 for (unsigned i = 0, e = V1->getNumOperands(); i != e; ++i) 00354 Res.push_back(FP(const_cast<Constant*>(V1->getOperand(i)), 00355 const_cast<Constant*>(V2->getOperand(i)))); 00356 return ConstantPacked::get(Res); 00357 } 00358 00359 /// PackedTypeRules provides a concrete base class of ConstRules for 00360 /// ConstantPacked operands. 00361 /// 00362 namespace { 00363 struct VISIBILITY_HIDDEN ConstantPackedRules 00364 : public TemplateRules<ConstantPacked, ConstantPackedRules> { 00365 00366 static Constant *Add(const ConstantPacked *V1, const ConstantPacked *V2) { 00367 return EvalVectorOp(V1, V2, ConstantExpr::getAdd); 00368 } 00369 static Constant *Sub(const ConstantPacked *V1, const ConstantPacked *V2) { 00370 return EvalVectorOp(V1, V2, ConstantExpr::getSub); 00371 } 00372 static Constant *Mul(const ConstantPacked *V1, const ConstantPacked *V2) { 00373 return EvalVectorOp(V1, V2, ConstantExpr::getMul); 00374 } 00375 static Constant *Div(const ConstantPacked *V1, const ConstantPacked *V2) { 00376 return EvalVectorOp(V1, V2, ConstantExpr::getDiv); 00377 } 00378 static Constant *Rem(const ConstantPacked *V1, const ConstantPacked *V2) { 00379 return EvalVectorOp(V1, V2, ConstantExpr::getRem); 00380 } 00381 static Constant *And(const ConstantPacked *V1, const ConstantPacked *V2) { 00382 return EvalVectorOp(V1, V2, ConstantExpr::getAnd); 00383 } 00384 static Constant *Or (const ConstantPacked *V1, const ConstantPacked *V2) { 00385 return EvalVectorOp(V1, V2, ConstantExpr::getOr); 00386 } 00387 static Constant *Xor(const ConstantPacked *V1, const ConstantPacked *V2) { 00388 return EvalVectorOp(V1, V2, ConstantExpr::getXor); 00389 } 00390 static Constant *Shl(const ConstantPacked *V1, const ConstantPacked *V2) { 00391 return EvalVectorOp(V1, V2, ConstantExpr::getShl); 00392 } 00393 static Constant *Shr(const ConstantPacked *V1, const ConstantPacked *V2) { 00394 return EvalVectorOp(V1, V2, ConstantExpr::getShr); 00395 } 00396 static Constant *LessThan(const ConstantPacked *V1, const ConstantPacked *V2){ 00397 return 0; 00398 } 00399 static Constant *EqualTo(const ConstantPacked *V1, const ConstantPacked *V2) { 00400 for (unsigned i = 0, e = V1->getNumOperands(); i != e; ++i) { 00401 Constant *C = 00402 ConstantExpr::getSetEQ(const_cast<Constant*>(V1->getOperand(i)), 00403 const_cast<Constant*>(V2->getOperand(i))); 00404 if (ConstantBool *CB = dyn_cast<ConstantBool>(C)) 00405 return CB; 00406 } 00407 // Otherwise, could not decide from any element pairs. 00408 return 0; 00409 } 00410 }; 00411 } // end anonymous namespace 00412 00413 00414 //===----------------------------------------------------------------------===// 00415 // GeneralPackedRules Class 00416 //===----------------------------------------------------------------------===// 00417 00418 /// GeneralPackedRules provides a concrete base class of ConstRules for 00419 /// PackedType operands, where both operands are not ConstantPacked. The usual 00420 /// cause for this is that one operand is a ConstantAggregateZero. 00421 /// 00422 namespace { 00423 struct VISIBILITY_HIDDEN GeneralPackedRules 00424 : public TemplateRules<Constant, GeneralPackedRules> { 00425 }; 00426 } // end anonymous namespace 00427 00428 00429 //===----------------------------------------------------------------------===// 00430 // DirectRules Class 00431 //===----------------------------------------------------------------------===// 00432 // 00433 // DirectRules provides a concrete base classes of ConstRules for a variety of 00434 // different types. This allows the C++ compiler to automatically generate our 00435 // constant handling operations in a typesafe and accurate manner. 00436 // 00437 namespace { 00438 template<class ConstantClass, class BuiltinType, Type **Ty, class SuperClass> 00439 struct VISIBILITY_HIDDEN DirectRules 00440 : public TemplateRules<ConstantClass, SuperClass> { 00441 static Constant *Add(const ConstantClass *V1, const ConstantClass *V2) { 00442 BuiltinType R = (BuiltinType)V1->getValue() + (BuiltinType)V2->getValue(); 00443 return ConstantClass::get(*Ty, R); 00444 } 00445 00446 static Constant *Sub(const ConstantClass *V1, const ConstantClass *V2) { 00447 BuiltinType R = (BuiltinType)V1->getValue() - (BuiltinType)V2->getValue(); 00448 return ConstantClass::get(*Ty, R); 00449 } 00450 00451 static Constant *Mul(const ConstantClass *V1, const ConstantClass *V2) { 00452 BuiltinType R = (BuiltinType)V1->getValue() * (BuiltinType)V2->getValue(); 00453 return ConstantClass::get(*Ty, R); 00454 } 00455 00456 static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) { 00457 if (V2->isNullValue()) return 0; 00458 BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue(); 00459 return ConstantClass::get(*Ty, R); 00460 } 00461 00462 static Constant *LessThan(const ConstantClass *V1, const ConstantClass *V2) { 00463 bool R = (BuiltinType)V1->getValue() < (BuiltinType)V2->getValue(); 00464 return ConstantBool::get(R); 00465 } 00466 00467 static Constant *EqualTo(const ConstantClass *V1, const ConstantClass *V2) { 00468 bool R = (BuiltinType)V1->getValue() == (BuiltinType)V2->getValue(); 00469 return ConstantBool::get(R); 00470 } 00471 00472 static Constant *CastToPointer(const ConstantClass *V, 00473 const PointerType *PTy) { 00474 if (V->isNullValue()) // Is it a FP or Integral null value? 00475 return ConstantPointerNull::get(PTy); 00476 return 0; // Can't const prop other types of pointers 00477 } 00478 00479 // Casting operators. ick 00480 #define DEF_CAST(TYPE, CLASS, CTYPE) \ 00481 static Constant *CastTo##TYPE (const ConstantClass *V) { \ 00482 return CLASS::get(Type::TYPE##Ty, (CTYPE)(BuiltinType)V->getValue()); \ 00483 } 00484 00485 DEF_CAST(Bool , ConstantBool, bool) 00486 DEF_CAST(SByte , ConstantSInt, signed char) 00487 DEF_CAST(UByte , ConstantUInt, unsigned char) 00488 DEF_CAST(Short , ConstantSInt, signed short) 00489 DEF_CAST(UShort, ConstantUInt, unsigned short) 00490 DEF_CAST(Int , ConstantSInt, signed int) 00491 DEF_CAST(UInt , ConstantUInt, unsigned int) 00492 DEF_CAST(Long , ConstantSInt, int64_t) 00493 DEF_CAST(ULong , ConstantUInt, uint64_t) 00494 DEF_CAST(Float , ConstantFP , float) 00495 DEF_CAST(Double, ConstantFP , double) 00496 #undef DEF_CAST 00497 }; 00498 } // end anonymous namespace 00499 00500 00501 //===----------------------------------------------------------------------===// 00502 // DirectIntRules Class 00503 //===----------------------------------------------------------------------===// 00504 // 00505 // DirectIntRules provides implementations of functions that are valid on 00506 // integer types, but not all types in general. 00507 // 00508 namespace { 00509 template <class ConstantClass, class BuiltinType, Type **Ty> 00510 struct VISIBILITY_HIDDEN DirectIntRules 00511 : public DirectRules<ConstantClass, BuiltinType, Ty, 00512 DirectIntRules<ConstantClass, BuiltinType, Ty> > { 00513 00514 static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) { 00515 if (V2->isNullValue()) return 0; 00516 if (V2->isAllOnesValue() && // MIN_INT / -1 00517 (BuiltinType)V1->getValue() == -(BuiltinType)V1->getValue()) 00518 return 0; 00519 BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue(); 00520 return ConstantClass::get(*Ty, R); 00521 } 00522 00523 static Constant *Rem(const ConstantClass *V1, 00524 const ConstantClass *V2) { 00525 if (V2->isNullValue()) return 0; // X / 0 00526 if (V2->isAllOnesValue() && // MIN_INT / -1 00527 (BuiltinType)V1->getValue() == -(BuiltinType)V1->getValue()) 00528 return 0; 00529 BuiltinType R = (BuiltinType)V1->getValue() % (BuiltinType)V2->getValue(); 00530 return ConstantClass::get(*Ty, R); 00531 } 00532 00533 static Constant *And(const ConstantClass *V1, const ConstantClass *V2) { 00534 BuiltinType R = (BuiltinType)V1->getValue() & (BuiltinType)V2->getValue(); 00535 return ConstantClass::get(*Ty, R); 00536 } 00537 static Constant *Or(const ConstantClass *V1, const ConstantClass *V2) { 00538 BuiltinType R = (BuiltinType)V1->getValue() | (BuiltinType)V2->getValue(); 00539 return ConstantClass::get(*Ty, R); 00540 } 00541 static Constant *Xor(const ConstantClass *V1, const ConstantClass *V2) { 00542 BuiltinType R = (BuiltinType)V1->getValue() ^ (BuiltinType)V2->getValue(); 00543 return ConstantClass::get(*Ty, R); 00544 } 00545 00546 static Constant *Shl(const ConstantClass *V1, const ConstantClass *V2) { 00547 BuiltinType R = (BuiltinType)V1->getValue() << (BuiltinType)V2->getValue(); 00548 return ConstantClass::get(*Ty, R); 00549 } 00550 00551 static Constant *Shr(const ConstantClass *V1, const ConstantClass *V2) { 00552 BuiltinType R = (BuiltinType)V1->getValue() >> (BuiltinType)V2->getValue(); 00553 return ConstantClass::get(*Ty, R); 00554 } 00555 }; 00556 } // end anonymous namespace 00557 00558 00559 //===----------------------------------------------------------------------===// 00560 // DirectFPRules Class 00561 //===----------------------------------------------------------------------===// 00562 // 00563 /// DirectFPRules provides implementations of functions that are valid on 00564 /// floating point types, but not all types in general. 00565 /// 00566 namespace { 00567 template <class ConstantClass, class BuiltinType, Type **Ty> 00568 struct VISIBILITY_HIDDEN DirectFPRules 00569 : public DirectRules<ConstantClass, BuiltinType, Ty, 00570 DirectFPRules<ConstantClass, BuiltinType, Ty> > { 00571 static Constant *Rem(const ConstantClass *V1, const ConstantClass *V2) { 00572 if (V2->isNullValue()) return 0; 00573 BuiltinType Result = std::fmod((BuiltinType)V1->getValue(), 00574 (BuiltinType)V2->getValue()); 00575 return ConstantClass::get(*Ty, Result); 00576 } 00577 static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) { 00578 BuiltinType inf = std::numeric_limits<BuiltinType>::infinity(); 00579 if (V2->isExactlyValue(0.0)) return ConstantClass::get(*Ty, inf); 00580 if (V2->isExactlyValue(-0.0)) return ConstantClass::get(*Ty, -inf); 00581 BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue(); 00582 return ConstantClass::get(*Ty, R); 00583 } 00584 }; 00585 } // end anonymous namespace 00586 00587 00588 /// ConstRules::get - This method returns the constant rules implementation that 00589 /// implements the semantics of the two specified constants. 00590 ConstRules &ConstRules::get(const Constant *V1, const Constant *V2) { 00591 static EmptyRules EmptyR; 00592 static BoolRules BoolR; 00593 static NullPointerRules NullPointerR; 00594 static ConstantPackedRules ConstantPackedR; 00595 static GeneralPackedRules GeneralPackedR; 00596 static DirectIntRules<ConstantSInt, signed char , &Type::SByteTy> SByteR; 00597 static DirectIntRules<ConstantUInt, unsigned char , &Type::UByteTy> UByteR; 00598 static DirectIntRules<ConstantSInt, signed short, &Type::ShortTy> ShortR; 00599 static DirectIntRules<ConstantUInt, unsigned short, &Type::UShortTy> UShortR; 00600 static DirectIntRules<ConstantSInt, signed int , &Type::IntTy> IntR; 00601 static DirectIntRules<ConstantUInt, unsigned int , &Type::UIntTy> UIntR; 00602 static DirectIntRules<ConstantSInt, int64_t , &Type::LongTy> LongR; 00603 static DirectIntRules<ConstantUInt, uint64_t , &Type::ULongTy> ULongR; 00604 static DirectFPRules <ConstantFP , float , &Type::FloatTy> FloatR; 00605 static DirectFPRules <ConstantFP , double , &Type::DoubleTy> DoubleR; 00606 00607 if (isa<ConstantExpr>(V1) || isa<ConstantExpr>(V2) || 00608 isa<GlobalValue>(V1) || isa<GlobalValue>(V2) || 00609 isa<UndefValue>(V1) || isa<UndefValue>(V2)) 00610 return EmptyR; 00611 00612 switch (V1->getType()->getTypeID()) { 00613 default: assert(0 && "Unknown value type for constant folding!"); 00614 case Type::BoolTyID: return BoolR; 00615 case Type::PointerTyID: return NullPointerR; 00616 case Type::SByteTyID: return SByteR; 00617 case Type::UByteTyID: return UByteR; 00618 case Type::ShortTyID: return ShortR; 00619 case Type::UShortTyID: return UShortR; 00620 case Type::IntTyID: return IntR; 00621 case Type::UIntTyID: return UIntR; 00622 case Type::LongTyID: return LongR; 00623 case Type::ULongTyID: return ULongR; 00624 case Type::FloatTyID: return FloatR; 00625 case Type::DoubleTyID: return DoubleR; 00626 case Type::PackedTyID: 00627 if (isa<ConstantPacked>(V1) && isa<ConstantPacked>(V2)) 00628 return ConstantPackedR; 00629 return GeneralPackedR; // Constant folding rules for ConstantAggregateZero. 00630 } 00631 } 00632 00633 00634 //===----------------------------------------------------------------------===// 00635 // ConstantFold*Instruction Implementations 00636 //===----------------------------------------------------------------------===// 00637 // 00638 // These methods contain the special case hackery required to symbolically 00639 // evaluate some constant expression cases, and use the ConstantRules class to 00640 // evaluate normal constants. 00641 // 00642 static unsigned getSize(const Type *Ty) { 00643 unsigned S = Ty->getPrimitiveSize(); 00644 return S ? S : 8; // Treat pointers at 8 bytes 00645 } 00646 00647 /// CastConstantPacked - Convert the specified ConstantPacked node to the 00648 /// specified packed type. At this point, we know that the elements of the 00649 /// input packed constant are all simple integer or FP values. 00650 static Constant *CastConstantPacked(ConstantPacked *CP, 00651 const PackedType *DstTy) { 00652 unsigned SrcNumElts = CP->getType()->getNumElements(); 00653 unsigned DstNumElts = DstTy->getNumElements(); 00654 const Type *SrcEltTy = CP->getType()->getElementType(); 00655 const Type *DstEltTy = DstTy->getElementType(); 00656 00657 // If both vectors have the same number of elements (thus, the elements 00658 // are the same size), perform the conversion now. 00659 if (SrcNumElts == DstNumElts) { 00660 std::vector<Constant*> Result; 00661 00662 // If the src and dest elements are both integers, just cast each one 00663 // which will do the appropriate bit-convert. 00664 if (SrcEltTy->isIntegral() && DstEltTy->isIntegral()) { 00665 for (unsigned i = 0; i != SrcNumElts; ++i) 00666 Result.push_back(ConstantExpr::getCast(CP->getOperand(i), 00667 DstEltTy)); 00668 return ConstantPacked::get(Result); 00669 } 00670 00671 if (SrcEltTy->isIntegral()) { 00672 // Otherwise, this is an int-to-fp cast. 00673 assert(DstEltTy->isFloatingPoint()); 00674 if (DstEltTy->getTypeID() == Type::DoubleTyID) { 00675 for (unsigned i = 0; i != SrcNumElts; ++i) { 00676 double V = 00677 BitsToDouble(cast<ConstantInt>(CP->getOperand(i))->getRawValue()); 00678 Result.push_back(ConstantFP::get(Type::DoubleTy, V)); 00679 } 00680 return ConstantPacked::get(Result); 00681 } 00682 assert(DstEltTy == Type::FloatTy && "Unknown fp type!"); 00683 for (unsigned i = 0; i != SrcNumElts; ++i) { 00684 float V = 00685 BitsToFloat(cast<ConstantInt>(CP->getOperand(i))->getRawValue()); 00686 Result.push_back(ConstantFP::get(Type::FloatTy, V)); 00687 } 00688 return ConstantPacked::get(Result); 00689 } 00690 00691 // Otherwise, this is an fp-to-int cast. 00692 assert(SrcEltTy->isFloatingPoint() && DstEltTy->isIntegral()); 00693 00694 if (SrcEltTy->getTypeID() == Type::DoubleTyID) { 00695 for (unsigned i = 0; i != SrcNumElts; ++i) { 00696 uint64_t V = 00697 DoubleToBits(cast<ConstantFP>(CP->getOperand(i))->getValue()); 00698 Constant *C = ConstantUInt::get(Type::ULongTy, V); 00699 Result.push_back(ConstantExpr::getCast(C, DstEltTy)); 00700 } 00701 return ConstantPacked::get(Result); 00702 } 00703 00704 assert(SrcEltTy->getTypeID() == Type::FloatTyID); 00705 for (unsigned i = 0; i != SrcNumElts; ++i) { 00706 unsigned V = FloatToBits(cast<ConstantFP>(CP->getOperand(i))->getValue()); 00707 Constant *C = ConstantUInt::get(Type::UIntTy, V); 00708 Result.push_back(ConstantExpr::getCast(C, DstEltTy)); 00709 } 00710 return ConstantPacked::get(Result); 00711 } 00712 00713 // Otherwise, this is a cast that changes element count and size. Handle 00714 // casts which shrink the elements here. 00715 00716 // FIXME: We need to know endianness to do this! 00717 00718 return 0; 00719 } 00720 00721 00722 Constant *llvm::ConstantFoldCastInstruction(const Constant *V, 00723 const Type *DestTy) { 00724 if (V->getType() == DestTy) return (Constant*)V; 00725 00726 // Cast of a global address to boolean is always true. 00727 if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 00728 if (DestTy == Type::BoolTy) 00729 // FIXME: When we support 'external weak' references, we have to prevent 00730 // this transformation from happening. This code will need to be updated 00731 // to ignore external weak symbols when we support it. 00732 return ConstantBool::True; 00733 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 00734 if (CE->getOpcode() == Instruction::Cast) { 00735 Constant *Op = const_cast<Constant*>(CE->getOperand(0)); 00736 // Try to not produce a cast of a cast, which is almost always redundant. 00737 if (!Op->getType()->isFloatingPoint() && 00738 !CE->getType()->isFloatingPoint() && 00739 !DestTy->isFloatingPoint()) { 00740 unsigned S1 = getSize(Op->getType()), S2 = getSize(CE->getType()); 00741 unsigned S3 = getSize(DestTy); 00742 if (Op->getType() == DestTy && S3 >= S2) 00743 return Op; 00744 if (S1 >= S2 && S2 >= S3) 00745 return ConstantExpr::getCast(Op, DestTy); 00746 if (S1 <= S2 && S2 >= S3 && S1 <= S3) 00747 return ConstantExpr::getCast(Op, DestTy); 00748 } 00749 } else if (CE->getOpcode() == Instruction::GetElementPtr) { 00750 // If all of the indexes in the GEP are null values, there is no pointer 00751 // adjustment going on. We might as well cast the source pointer. 00752 bool isAllNull = true; 00753 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i) 00754 if (!CE->getOperand(i)->isNullValue()) { 00755 isAllNull = false; 00756 break; 00757 } 00758 if (isAllNull) 00759 return ConstantExpr::getCast(CE->getOperand(0), DestTy); 00760 } 00761 } else if (isa<UndefValue>(V)) { 00762 return UndefValue::get(DestTy); 00763 } 00764 00765 // Check to see if we are casting an pointer to an aggregate to a pointer to 00766 // the first element. If so, return the appropriate GEP instruction. 00767 if (const PointerType *PTy = dyn_cast<PointerType>(V->getType())) 00768 if (const PointerType *DPTy = dyn_cast<PointerType>(DestTy)) { 00769 std::vector<Value*> IdxList; 00770 IdxList.push_back(Constant::getNullValue(Type::IntTy)); 00771 const Type *ElTy = PTy->getElementType(); 00772 while (ElTy != DPTy->getElementType()) { 00773 if (const StructType *STy = dyn_cast<StructType>(ElTy)) { 00774 if (STy->getNumElements() == 0) break; 00775 ElTy = STy->getElementType(0); 00776 IdxList.push_back(Constant::getNullValue(Type::UIntTy)); 00777 } else if (const SequentialType *STy = dyn_cast<SequentialType>(ElTy)) { 00778 if (isa<PointerType>(ElTy)) break; // Can't index into pointers! 00779 ElTy = STy->getElementType(); 00780 IdxList.push_back(IdxList[0]); 00781 } else { 00782 break; 00783 } 00784 } 00785 00786 if (ElTy == DPTy->getElementType()) 00787 return ConstantExpr::getGetElementPtr(const_cast<Constant*>(V),IdxList); 00788 } 00789 00790 // Handle casts from one packed constant to another. We know that the src and 00791 // dest type have the same size. 00792 if (const PackedType *DestPTy = dyn_cast<PackedType>(DestTy)) { 00793 if (const PackedType *SrcTy = dyn_cast<PackedType>(V->getType())) { 00794 assert(DestPTy->getElementType()->getPrimitiveSizeInBits() * 00795 DestPTy->getNumElements() == 00796 SrcTy->getElementType()->getPrimitiveSizeInBits() * 00797 SrcTy->getNumElements() && "Not cast between same sized vectors!"); 00798 if (isa<ConstantAggregateZero>(V)) 00799 return Constant::getNullValue(DestTy); 00800 if (isa<UndefValue>(V)) 00801 return UndefValue::get(DestTy); 00802 if (const ConstantPacked *CP = dyn_cast<ConstantPacked>(V)) { 00803 // This is a cast from a ConstantPacked of one type to a ConstantPacked 00804 // of another type. Check to see if all elements of the input are 00805 // simple. 00806 bool AllSimpleConstants = true; 00807 for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) { 00808 if (!isa<ConstantInt>(CP->getOperand(i)) && 00809 !isa<ConstantFP>(CP->getOperand(i))) { 00810 AllSimpleConstants = false; 00811 break; 00812 } 00813 } 00814 00815 // If all of the elements are simple constants, we can fold this. 00816 if (AllSimpleConstants) 00817 return CastConstantPacked(const_cast<ConstantPacked*>(CP), DestPTy); 00818 } 00819 } 00820 } 00821 00822 ConstRules &Rules = ConstRules::get(V, V); 00823 00824 switch (DestTy->getTypeID()) { 00825 case Type::BoolTyID: return Rules.castToBool(V); 00826 case Type::UByteTyID: return Rules.castToUByte(V); 00827 case Type::SByteTyID: return Rules.castToSByte(V); 00828 case Type::UShortTyID: return Rules.castToUShort(V); 00829 case Type::ShortTyID: return Rules.castToShort(V); 00830 case Type::UIntTyID: return Rules.castToUInt(V); 00831 case Type::IntTyID: return Rules.castToInt(V); 00832 case Type::ULongTyID: return Rules.castToULong(V); 00833 case Type::LongTyID: return Rules.castToLong(V); 00834 case Type::FloatTyID: return Rules.castToFloat(V); 00835 case Type::DoubleTyID: return Rules.castToDouble(V); 00836 case Type::PointerTyID: 00837 return Rules.castToPointer(V, cast<PointerType>(DestTy)); 00838 default: return 0; 00839 } 00840 } 00841 00842 Constant *llvm::ConstantFoldSelectInstruction(const Constant *Cond, 00843 const Constant *V1, 00844 const Constant *V2) { 00845 if (Cond == ConstantBool::True) 00846 return const_cast<Constant*>(V1); 00847 else if (Cond == ConstantBool::False) 00848 return const_cast<Constant*>(V2); 00849 00850 if (isa<UndefValue>(V1)) return const_cast<Constant*>(V2); 00851 if (isa<UndefValue>(V2)) return const_cast<Constant*>(V1); 00852 if (isa<UndefValue>(Cond)) return const_cast<Constant*>(V1); 00853 if (V1 == V2) return const_cast<Constant*>(V1); 00854 return 0; 00855 } 00856 00857 Constant *llvm::ConstantFoldExtractElementInstruction(const Constant *Val, 00858 const Constant *Idx) { 00859 if (isa<UndefValue>(Val)) // ee(undef, x) -> undef 00860 return UndefValue::get(cast<PackedType>(Val->getType())->getElementType()); 00861 if (Val->isNullValue()) // ee(zero, x) -> zero 00862 return Constant::getNullValue( 00863 cast<PackedType>(Val->getType())->getElementType()); 00864 00865 if (const ConstantPacked *CVal = dyn_cast<ConstantPacked>(Val)) { 00866 if (const ConstantUInt *CIdx = dyn_cast<ConstantUInt>(Idx)) { 00867 return const_cast<Constant*>(CVal->getOperand(CIdx->getValue())); 00868 } else if (isa<UndefValue>(Idx)) { 00869 // ee({w,x,y,z}, undef) -> w (an arbitrary value). 00870 return const_cast<Constant*>(CVal->getOperand(0)); 00871 } 00872 } 00873 return 0; 00874 } 00875 00876 Constant *llvm::ConstantFoldInsertElementInstruction(const Constant *Val, 00877 const Constant *Elt, 00878 const Constant *Idx) { 00879 const ConstantUInt *CIdx = dyn_cast<ConstantUInt>(Idx); 00880 if (!CIdx) return 0; 00881 unsigned idxVal = CIdx->getValue(); 00882 if (const UndefValue *UVal = dyn_cast<UndefValue>(Val)) { 00883 // Insertion of scalar constant into packed undef 00884 // Optimize away insertion of undef 00885 if (isa<UndefValue>(Elt)) 00886 return const_cast<Constant*>(Val); 00887 // Otherwise break the aggregate undef into multiple undefs and do 00888 // the insertion 00889 unsigned numOps = 00890 cast<PackedType>(Val->getType())->getNumElements(); 00891 std::vector<Constant*> Ops; 00892 Ops.reserve(numOps); 00893 for (unsigned i = 0; i < numOps; ++i) { 00894 const Constant *Op = 00895 (i == idxVal) ? Elt : UndefValue::get(Elt->getType()); 00896 Ops.push_back(const_cast<Constant*>(Op)); 00897 } 00898 return ConstantPacked::get(Ops); 00899 } 00900 if (const ConstantAggregateZero *CVal = 00901 dyn_cast<ConstantAggregateZero>(Val)) { 00902 // Insertion of scalar constant into packed aggregate zero 00903 // Optimize away insertion of zero 00904 if (Elt->isNullValue()) 00905 return const_cast<Constant*>(Val); 00906 // Otherwise break the aggregate zero into multiple zeros and do 00907 // the insertion 00908 unsigned numOps = 00909 cast<PackedType>(Val->getType())->getNumElements(); 00910 std::vector<Constant*> Ops; 00911 Ops.reserve(numOps); 00912 for (unsigned i = 0; i < numOps; ++i) { 00913 const Constant *Op = 00914 (i == idxVal) ? Elt : Constant::getNullValue(Elt->getType()); 00915 Ops.push_back(const_cast<Constant*>(Op)); 00916 } 00917 return ConstantPacked::get(Ops); 00918 } 00919 if (const ConstantPacked *CVal = dyn_cast<ConstantPacked>(Val)) { 00920 // Insertion of scalar constant into packed constant 00921 std::vector<Constant*> Ops; 00922 Ops.reserve(CVal->getNumOperands()); 00923 for (unsigned i = 0; i < CVal->getNumOperands(); ++i) { 00924 const Constant *Op = 00925 (i == idxVal) ? Elt : cast<Constant>(CVal->getOperand(i)); 00926 Ops.push_back(const_cast<Constant*>(Op)); 00927 } 00928 return ConstantPacked::get(Ops); 00929 } 00930 return 0; 00931 } 00932 00933 Constant *llvm::ConstantFoldShuffleVectorInstruction(const Constant *V1, 00934 const Constant *V2, 00935 const Constant *Mask) { 00936 // TODO: 00937 return 0; 00938 } 00939 00940 00941 /// isZeroSizedType - This type is zero sized if its an array or structure of 00942 /// zero sized types. The only leaf zero sized type is an empty structure. 00943 static bool isMaybeZeroSizedType(const Type *Ty) { 00944 if (isa<OpaqueType>(Ty)) return true; // Can't say. 00945 if (const StructType *STy = dyn_cast<StructType>(Ty)) { 00946 00947 // If all of elements have zero size, this does too. 00948 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 00949 if (!isMaybeZeroSizedType(STy->getElementType(i))) return false; 00950 return true; 00951 00952 } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 00953 return isMaybeZeroSizedType(ATy->getElementType()); 00954 } 00955 return false; 00956 } 00957 00958 /// IdxCompare - Compare the two constants as though they were getelementptr 00959 /// indices. This allows coersion of the types to be the same thing. 00960 /// 00961 /// If the two constants are the "same" (after coersion), return 0. If the 00962 /// first is less than the second, return -1, if the second is less than the 00963 /// first, return 1. If the constants are not integral, return -2. 00964 /// 00965 static int IdxCompare(Constant *C1, Constant *C2, const Type *ElTy) { 00966 if (C1 == C2) return 0; 00967 00968 // Ok, we found a different index. Are either of the operands 00969 // ConstantExprs? If so, we can't do anything with them. 00970 if (!isa<ConstantInt>(C1) || !isa<ConstantInt>(C2)) 00971 return -2; // don't know! 00972 00973 // Ok, we have two differing integer indices. Sign extend them to be the same 00974 // type. Long is always big enough, so we use it. 00975 C1 = ConstantExpr::getSignExtend(C1, Type::LongTy); 00976 C2 = ConstantExpr::getSignExtend(C2, Type::LongTy); 00977 if (C1 == C2) return 0; // Are they just differing types? 00978 00979 // If the type being indexed over is really just a zero sized type, there is 00980 // no pointer difference being made here. 00981 if (isMaybeZeroSizedType(ElTy)) 00982 return -2; // dunno. 00983 00984 // If they are really different, now that they are the same type, then we 00985 // found a difference! 00986 if (cast<ConstantSInt>(C1)->getValue() < cast<ConstantSInt>(C2)->getValue()) 00987 return -1; 00988 else 00989 return 1; 00990 } 00991 00992 /// evaluateRelation - This function determines if there is anything we can 00993 /// decide about the two constants provided. This doesn't need to handle simple 00994 /// things like integer comparisons, but should instead handle ConstantExprs 00995 /// and GlobalValuess. If we can determine that the two constants have a 00996 /// particular relation to each other, we should return the corresponding SetCC 00997 /// code, otherwise return Instruction::BinaryOpsEnd. 00998 /// 00999 /// To simplify this code we canonicalize the relation so that the first 01000 /// operand is always the most "complex" of the two. We consider simple 01001 /// constants (like ConstantInt) to be the simplest, followed by 01002 /// GlobalValues, followed by ConstantExpr's (the most complex). 01003 /// 01004 static Instruction::BinaryOps evaluateRelation(Constant *V1, Constant *V2) { 01005 assert(V1->getType() == V2->getType() && 01006 "Cannot compare different types of values!"); 01007 if (V1 == V2) return Instruction::SetEQ; 01008 01009 if (!isa<ConstantExpr>(V1) && !isa<GlobalValue>(V1)) { 01010 if (!isa<GlobalValue>(V2) && !isa<ConstantExpr>(V2)) { 01011 // We distilled this down to a simple case, use the standard constant 01012 // folder. 01013 ConstantBool *R = dyn_cast<ConstantBool>(ConstantExpr::getSetEQ(V1, V2)); 01014 if (R == ConstantBool::True) return Instruction::SetEQ; 01015 R = dyn_cast<ConstantBool>(ConstantExpr::getSetLT(V1, V2)); 01016 if (R == ConstantBool::True) return Instruction::SetLT; 01017 R = dyn_cast<ConstantBool>(ConstantExpr::getSetGT(V1, V2)); 01018 if (R == ConstantBool::True) return Instruction::SetGT; 01019 01020 // If we couldn't figure it out, bail. 01021 return Instruction::BinaryOpsEnd; 01022 } 01023 01024 // If the first operand is simple, swap operands. 01025 Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1); 01026 if (SwappedRelation != Instruction::BinaryOpsEnd) 01027 return SetCondInst::getSwappedCondition(SwappedRelation); 01028 01029 } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(V1)) { 01030 if (isa<ConstantExpr>(V2)) { // Swap as necessary. 01031 Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1); 01032 if (SwappedRelation != Instruction::BinaryOpsEnd) 01033 return SetCondInst::getSwappedCondition(SwappedRelation); 01034 else 01035 return Instruction::BinaryOpsEnd; 01036 } 01037 01038 // Now we know that the RHS is a GlobalValue or simple constant, 01039 // which (since the types must match) means that it's a ConstantPointerNull. 01040 if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) { 01041 assert(CPR1 != CPR2 && 01042 "GVs for the same value exist at different addresses??"); 01043 // FIXME: If both globals are external weak, they might both be null! 01044 return Instruction::SetNE; 01045 } else { 01046 assert(isa<ConstantPointerNull>(V2) && "Canonicalization guarantee!"); 01047 // Global can never be null. FIXME: if we implement external weak 01048 // linkage, this is not necessarily true! 01049 return Instruction::SetNE; 01050 } 01051 01052 } else { 01053 // Ok, the LHS is known to be a constantexpr. The RHS can be any of a 01054 // constantexpr, a CPR, or a simple constant. 01055 ConstantExpr *CE1 = cast<ConstantExpr>(V1); 01056 Constant *CE1Op0 = CE1->getOperand(0); 01057 01058 switch (CE1->getOpcode()) { 01059 case Instruction::Cast: 01060 // If the cast is not actually changing bits, and the second operand is a 01061 // null pointer, do the comparison with the pre-casted value. 01062 if (V2->isNullValue() && 01063 (isa<PointerType>(CE1->getType()) || CE1->getType()->isIntegral())) 01064 return evaluateRelation(CE1Op0, 01065 Constant::getNullValue(CE1Op0->getType())); 01066 01067 // If the dest type is a pointer type, and the RHS is a constantexpr cast 01068 // from the same type as the src of the LHS, evaluate the inputs. This is 01069 // important for things like "seteq (cast 4 to int*), (cast 5 to int*)", 01070 // which happens a lot in compilers with tagged integers. 01071 if (ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2)) 01072 if (isa<PointerType>(CE1->getType()) && 01073 CE2->getOpcode() == Instruction::Cast && 01074 CE1->getOperand(0)->getType() == CE2->getOperand(0)->getType() && 01075 CE1->getOperand(0)->getType()->isIntegral()) { 01076 return evaluateRelation(CE1->getOperand(0), CE2->getOperand(0)); 01077 } 01078 break; 01079 01080 case Instruction::GetElementPtr: 01081 // Ok, since this is a getelementptr, we know that the constant has a 01082 // pointer type. Check the various cases. 01083 if (isa<ConstantPointerNull>(V2)) { 01084 // If we are comparing a GEP to a null pointer, check to see if the base 01085 // of the GEP equals the null pointer. 01086 if (isa<GlobalValue>(CE1Op0)) { 01087 // FIXME: this is not true when we have external weak references! 01088 // No offset can go from a global to a null pointer. 01089 return Instruction::SetGT; 01090 } else if (isa<ConstantPointerNull>(CE1Op0)) { 01091 // If we are indexing from a null pointer, check to see if we have any 01092 // non-zero indices. 01093 for (unsigned i = 1, e = CE1->getNumOperands(); i != e; ++i) 01094 if (!CE1->getOperand(i)->isNullValue()) 01095 // Offsetting from null, must not be equal. 01096 return Instruction::SetGT; 01097 // Only zero indexes from null, must still be zero. 01098 return Instruction::SetEQ; 01099 } 01100 // Otherwise, we can't really say if the first operand is null or not. 01101 } else if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) { 01102 if (isa<ConstantPointerNull>(CE1Op0)) { 01103 // FIXME: This is not true with external weak references. 01104 return Instruction::SetLT; 01105 } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(CE1Op0)) { 01106 if (CPR1 == CPR2) { 01107 // If this is a getelementptr of the same global, then it must be 01108 // different. Because the types must match, the getelementptr could 01109 // only have at most one index, and because we fold getelementptr's 01110 // with a single zero index, it must be nonzero. 01111 assert(CE1->getNumOperands() == 2 && 01112 !CE1->getOperand(1)->isNullValue() && 01113 "Suprising getelementptr!"); 01114 return Instruction::SetGT; 01115 } else { 01116 // If they are different globals, we don't know what the value is, 01117 // but they can't be equal. 01118 return Instruction::SetNE; 01119 } 01120 } 01121 } else { 01122 const ConstantExpr *CE2 = cast<ConstantExpr>(V2); 01123 const Constant *CE2Op0 = CE2->getOperand(0); 01124 01125 // There are MANY other foldings that we could perform here. They will 01126 // probably be added on demand, as they seem needed. 01127 switch (CE2->getOpcode()) { 01128 default: break; 01129 case Instruction::GetElementPtr: 01130 // By far the most common case to handle is when the base pointers are 01131 // obviously to the same or different globals. 01132 if (isa<GlobalValue>(CE1Op0) && isa<GlobalValue>(CE2Op0)) { 01133 if (CE1Op0 != CE2Op0) // Don't know relative ordering, but not equal 01134 return Instruction::SetNE; 01135 // Ok, we know that both getelementptr instructions are based on the 01136 // same global. From this, we can precisely determine the relative 01137 // ordering of the resultant pointers. 01138 unsigned i = 1; 01139 01140 // Compare all of the operands the GEP's have in common. 01141 gep_type_iterator GTI = gep_type_begin(CE1); 01142 for (;i != CE1->getNumOperands() && i != CE2->getNumOperands(); 01143 ++i, ++GTI) 01144 switch (IdxCompare(CE1->getOperand(i), CE2->getOperand(i), 01145 GTI.getIndexedType())) { 01146 case -1: return Instruction::SetLT; 01147 case 1: return Instruction::SetGT; 01148 case -2: return Instruction::BinaryOpsEnd; 01149 } 01150 01151 // Ok, we ran out of things they have in common. If any leftovers 01152 // are non-zero then we have a difference, otherwise we are equal. 01153 for (; i < CE1->getNumOperands(); ++i) 01154 if (!CE1->getOperand(i)->isNullValue()) 01155 if (isa<ConstantIntegral>(CE1->getOperand(i))) 01156 return Instruction::SetGT; 01157 else 01158 return Instruction::BinaryOpsEnd; // Might be equal. 01159 01160 for (; i < CE2->getNumOperands(); ++i) 01161 if (!CE2->getOperand(i)->isNullValue()) 01162 if (isa<ConstantIntegral>(CE2->getOperand(i))) 01163 return Instruction::SetLT; 01164 else 01165 return Instruction::BinaryOpsEnd; // Might be equal. 01166 return Instruction::SetEQ; 01167 } 01168 } 01169 } 01170 01171 default: 01172 break; 01173 } 01174 } 01175 01176 return Instruction::BinaryOpsEnd; 01177 } 01178 01179 Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode, 01180 const Constant *V1, 01181 const Constant *V2) { 01182 Constant *C = 0; 01183 switch (Opcode) { 01184 default: break; 01185 case Instruction::Add: C = ConstRules::get(V1, V2).add(V1, V2); break; 01186 case Instruction::Sub: C = ConstRules::get(V1, V2).sub(V1, V2); break; 01187 case Instruction::Mul: C = ConstRules::get(V1, V2).mul(V1, V2); break; 01188 case Instruction::Div: C = ConstRules::get(V1, V2).div(V1, V2); break; 01189 case Instruction::Rem: C = ConstRules::get(V1, V2).rem(V1, V2); break; 01190 case Instruction::And: C = ConstRules::get(V1, V2).op_and(V1, V2); break; 01191 case Instruction::Or: C = ConstRules::get(V1, V2).op_or (V1, V2); break; 01192 case Instruction::Xor: C = ConstRules::get(V1, V2).op_xor(V1, V2); break; 01193 case Instruction::Shl: C = ConstRules::get(V1, V2).shl(V1, V2); break; 01194 case Instruction::Shr: C = ConstRules::get(V1, V2).shr(V1, V2); break; 01195 case Instruction::SetEQ: C = ConstRules::get(V1, V2).equalto(V1, V2); break; 01196 case Instruction::SetLT: C = ConstRules::get(V1, V2).lessthan(V1, V2);break; 01197 case Instruction::SetGT: C = ConstRules::get(V1, V2).lessthan(V2, V1);break; 01198 case Instruction::SetNE: // V1 != V2 === !(V1 == V2) 01199 C = ConstRules::get(V1, V2).equalto(V1, V2); 01200 if (C) return ConstantExpr::getNot(C); 01201 break; 01202 case Instruction::SetLE: // V1 <= V2 === !(V2 < V1) 01203 C = ConstRules::get(V1, V2).lessthan(V2, V1); 01204 if (C) return ConstantExpr::getNot(C); 01205 break; 01206 case Instruction::SetGE: // V1 >= V2 === !(V1 < V2) 01207 C = ConstRules::get(V1, V2).lessthan(V1, V2); 01208 if (C) return ConstantExpr::getNot(C); 01209 break; 01210 } 01211 01212 // If we successfully folded the expression, return it now. 01213 if (C) return C; 01214 01215 if (SetCondInst::isRelational(Opcode)) { 01216 if (isa<UndefValue>(V1) || isa<UndefValue>(V2)) 01217 return UndefValue::get(Type::BoolTy); 01218 switch (evaluateRelation(const_cast<Constant*>(V1), 01219 const_cast<Constant*>(V2))) { 01220 default: assert(0 && "Unknown relational!"); 01221 case Instruction::BinaryOpsEnd: 01222 break; // Couldn't determine anything about these constants. 01223 case Instruction::SetEQ: // We know the constants are equal! 01224 // If we know the constants are equal, we can decide the result of this 01225 // computation precisely. 01226 return ConstantBool::get(Opcode == Instruction::SetEQ || 01227 Opcode == Instruction::SetLE || 01228 Opcode == Instruction::SetGE); 01229 case Instruction::SetLT: 01230 // If we know that V1 < V2, we can decide the result of this computation 01231 // precisely. 01232 return ConstantBool::get(Opcode == Instruction::SetLT || 01233 Opcode == Instruction::SetNE || 01234 Opcode == Instruction::SetLE); 01235 case Instruction::SetGT: 01236 // If we know that V1 > V2, we can decide the result of this computation 01237 // precisely. 01238 return ConstantBool::get(Opcode == Instruction::SetGT || 01239 Opcode == Instruction::SetNE || 01240 Opcode == Instruction::SetGE); 01241 case Instruction::SetLE: 01242 // If we know that V1 <= V2, we can only partially decide this relation. 01243 if (Opcode == Instruction::SetGT) return ConstantBool::False; 01244 if (Opcode == Instruction::SetLT) return ConstantBool::True; 01245 break; 01246 01247 case Instruction::SetGE: 01248 // If we know that V1 >= V2, we can only partially decide this relation. 01249 if (Opcode == Instruction::SetLT) return ConstantBool::False; 01250 if (Opcode == Instruction::SetGT) return ConstantBool::True; 01251 break; 01252 01253 case Instruction::SetNE: 01254 // If we know that V1 != V2, we can only partially decide this relation. 01255 if (Opcode == Instruction::SetEQ) return ConstantBool::False; 01256 if (Opcode == Instruction::SetNE) return ConstantBool::True; 01257 break; 01258 } 01259 } 01260 01261 if (isa<UndefValue>(V1) || isa<UndefValue>(V2)) { 01262 switch (Opcode) { 01263 case Instruction::Add: 01264 case Instruction::Sub: 01265 case Instruction::Xor: 01266 return UndefValue::get(V1->getType()); 01267 01268 case Instruction::Mul: 01269 case Instruction::And: 01270 return Constant::getNullValue(V1->getType()); 01271 case Instruction::Div: 01272 case Instruction::Rem: 01273 if (!isa<UndefValue>(V2)) // undef/X -> 0 01274 return Constant::getNullValue(V1->getType()); 01275 return const_cast<Constant*>(V2); // X/undef -> undef 01276 case Instruction::Or: // X|undef -> -1 01277 return ConstantInt::getAllOnesValue(V1->getType()); 01278 case Instruction::Shr: 01279 if (!isa<UndefValue>(V2)) { 01280 if (V1->getType()->isSigned()) 01281 return const_cast<Constant*>(V1); // undef >>s X -> undef 01282 // undef >>u X -> 0 01283 } else if (isa<UndefValue>(V1)) { 01284 return const_cast<Constant*>(V1); // undef >> undef -> undef 01285 } else { 01286 if (V1->getType()->isSigned()) 01287 return const_cast<Constant*>(V1); // X >>s undef -> X 01288 // X >>u undef -> 0 01289 } 01290 return Constant::getNullValue(V1->getType()); 01291 01292 case Instruction::Shl: 01293 // undef << X -> 0 X << undef -> 0 01294 return Constant::getNullValue(V1->getType()); 01295 } 01296 } 01297 01298 if (const ConstantExpr *CE1 = dyn_cast<ConstantExpr>(V1)) { 01299 if (const ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2)) { 01300 // There are many possible foldings we could do here. We should probably 01301 // at least fold add of a pointer with an integer into the appropriate 01302 // getelementptr. This will improve alias analysis a bit. 01303 01304 01305 01306 01307 } else { 01308 // Just implement a couple of simple identities. 01309 switch (Opcode) { 01310 case Instruction::Add: 01311 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X + 0 == X 01312 break; 01313 case Instruction::Sub: 01314 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X - 0 == X 01315 break; 01316 case Instruction::Mul: 01317 if (V2->isNullValue()) return const_cast<Constant*>(V2); // X * 0 == 0 01318 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2)) 01319 if (CI->getRawValue() == 1) 01320 return const_cast<Constant*>(V1); // X * 1 == X 01321 break; 01322 case Instruction::Div: 01323 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2)) 01324 if (CI->getRawValue() == 1) 01325 return const_cast<Constant*>(V1); // X / 1 == X 01326 break; 01327 case Instruction::Rem: 01328 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2)) 01329 if (CI->getRawValue() == 1) 01330 return Constant::getNullValue(CI->getType()); // X % 1 == 0 01331 break; 01332 case Instruction::And: 01333 if (cast<ConstantIntegral>(V2)->isAllOnesValue()) 01334 return const_cast<Constant*>(V1); // X & -1 == X 01335 if (V2->isNullValue()) return const_cast<Constant*>(V2); // X & 0 == 0 01336 if (CE1->getOpcode() == Instruction::Cast && 01337 isa<GlobalValue>(CE1->getOperand(0))) { 01338 GlobalValue *CPR = cast<GlobalValue>(CE1->getOperand(0)); 01339 01340 // Functions are at least 4-byte aligned. If and'ing the address of a 01341 // function with a constant < 4, fold it to zero. 01342 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2)) 01343 if (CI->getRawValue() < 4 && isa<Function>(CPR)) 01344 return Constant::getNullValue(CI->getType()); 01345 } 01346 break; 01347 case Instruction::Or: 01348 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X | 0 == X 01349 if (cast<ConstantIntegral>(V2)->isAllOnesValue()) 01350 return const_cast<Constant*>(V2); // X | -1 == -1 01351 break; 01352 case Instruction::Xor: 01353 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X ^ 0 == X 01354 break; 01355 } 01356 } 01357 01358 } else if (const ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2)) { 01359 // If V2 is a constant expr and V1 isn't, flop them around and fold the 01360 // other way if possible. 01361 switch (Opcode) { 01362 case Instruction::Add: 01363 case Instruction::Mul: 01364 case Instruction::And: 01365 case Instruction::Or: 01366 case Instruction::Xor: 01367 case Instruction::SetEQ: 01368 case Instruction::SetNE: 01369 // No change of opcode required. 01370 return ConstantFoldBinaryInstruction(Opcode, V2, V1); 01371 01372 case Instruction::SetLT: 01373 case Instruction::SetGT: 01374 case Instruction::SetLE: 01375 case Instruction::SetGE: 01376 // Change the opcode as necessary to swap the operands. 01377 Opcode = SetCondInst::getSwappedCondition((Instruction::BinaryOps)Opcode); 01378 return ConstantFoldBinaryInstruction(Opcode, V2, V1); 01379 01380 case Instruction::Shl: 01381 case Instruction::Shr: 01382 case Instruction::Sub: 01383 case Instruction::Div: 01384 case Instruction::Rem: 01385 default: // These instructions cannot be flopped around. 01386 break; 01387 } 01388 } 01389 return 0; 01390 } 01391 01392 Constant *llvm::ConstantFoldGetElementPtr(const Constant *C, 01393 const std::vector<Value*> &IdxList) { 01394 if (IdxList.size() == 0 || 01395 (IdxList.size() == 1 && cast<Constant>(IdxList[0])->isNullValue())) 01396 return const_cast<Constant*>(C); 01397 01398 if (isa<UndefValue>(C)) { 01399 const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList, 01400 true); 01401 assert(Ty != 0 && "Invalid indices for GEP!"); 01402 return UndefValue::get(PointerType::get(Ty)); 01403 } 01404 01405 Constant *Idx0 = cast<Constant>(IdxList[0]); 01406 if (C->isNullValue()) { 01407 bool isNull = true; 01408 for (unsigned i = 0, e = IdxList.size(); i != e; ++i) 01409 if (!cast<Constant>(IdxList[i])->isNullValue()) { 01410 isNull = false; 01411 break; 01412 } 01413 if (isNull) { 01414 const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList, 01415 true); 01416 assert(Ty != 0 && "Invalid indices for GEP!"); 01417 return ConstantPointerNull::get(PointerType::get(Ty)); 01418 } 01419 01420 if (IdxList.size() == 1) { 01421 const Type *ElTy = cast<PointerType>(C->getType())->getElementType(); 01422 if (unsigned ElSize = ElTy->getPrimitiveSize()) { 01423 // gep null, C is equal to C*sizeof(nullty). If nullty is a known llvm 01424 // type, we can statically fold this. 01425 Constant *R = ConstantUInt::get(Type::UIntTy, ElSize); 01426 R = ConstantExpr::getCast(R, Idx0->getType()); 01427 R = ConstantExpr::getMul(R, Idx0); 01428 return ConstantExpr::getCast(R, C->getType()); 01429 } 01430 } 01431 } 01432 01433 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(const_cast<Constant*>(C))) { 01434 // Combine Indices - If the source pointer to this getelementptr instruction 01435 // is a getelementptr instruction, combine the indices of the two 01436 // getelementptr instructions into a single instruction. 01437 // 01438 if (CE->getOpcode() == Instruction::GetElementPtr) { 01439 const Type *LastTy = 0; 01440 for (gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE); 01441 I != E; ++I) 01442 LastTy = *I; 01443 01444 if ((LastTy && isa<ArrayType>(LastTy)) || Idx0->isNullValue()) { 01445 std::vector<Value*> NewIndices; 01446 NewIndices.reserve(IdxList.size() + CE->getNumOperands()); 01447 for (unsigned i = 1, e = CE->getNumOperands()-1; i != e; ++i) 01448 NewIndices.push_back(CE->getOperand(i)); 01449 01450 // Add the last index of the source with the first index of the new GEP. 01451 // Make sure to handle the case when they are actually different types. 01452 Constant *Combined = CE->getOperand(CE->getNumOperands()-1); 01453 // Otherwise it must be an array. 01454 if (!Idx0->isNullValue()) { 01455 const Type *IdxTy = Combined->getType(); 01456 if (IdxTy != Idx0->getType()) IdxTy = Type::LongTy; 01457 Combined = 01458 ConstantExpr::get(Instruction::Add, 01459 ConstantExpr::getCast(Idx0, IdxTy), 01460 ConstantExpr::getCast(Combined, IdxTy)); 01461 } 01462 01463 NewIndices.push_back(Combined); 01464 NewIndices.insert(NewIndices.end(), IdxList.begin()+1, IdxList.end()); 01465 return ConstantExpr::getGetElementPtr(CE->getOperand(0), NewIndices); 01466 } 01467 } 01468 01469 // Implement folding of: 01470 // int* getelementptr ([2 x int]* cast ([3 x int]* %X to [2 x int]*), 01471 // long 0, long 0) 01472 // To: int* getelementptr ([3 x int]* %X, long 0, long 0) 01473 // 01474 if (CE->getOpcode() == Instruction::Cast && IdxList.size() > 1 && 01475 Idx0->isNullValue()) 01476 if (const PointerType *SPT = 01477 dyn_cast<PointerType>(CE->getOperand(0)->getType())) 01478 if (const ArrayType *SAT = dyn_cast<ArrayType>(SPT->getElementType())) 01479 if (const ArrayType *CAT = 01480 dyn_cast<ArrayType>(cast<PointerType>(C->getType())->getElementType())) 01481 if (CAT->getElementType() == SAT->getElementType()) 01482 return ConstantExpr::getGetElementPtr( 01483 (Constant*)CE->getOperand(0), IdxList); 01484 } 01485 return 0; 01486 } 01487