LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

ConstantFolding.cpp

Go to the documentation of this file.
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 <cmath>
00028 using namespace llvm;
00029 
00030 namespace {
00031   struct ConstRules {
00032     ConstRules() {}
00033     
00034     // Binary Operators...
00035     virtual Constant *add(const Constant *V1, const Constant *V2) const = 0;
00036     virtual Constant *sub(const Constant *V1, const Constant *V2) const = 0;
00037     virtual Constant *mul(const Constant *V1, const Constant *V2) const = 0;
00038     virtual Constant *div(const Constant *V1, const Constant *V2) const = 0;
00039     virtual Constant *rem(const Constant *V1, const Constant *V2) const = 0;
00040     virtual Constant *op_and(const Constant *V1, const Constant *V2) const = 0;
00041     virtual Constant *op_or (const Constant *V1, const Constant *V2) const = 0;
00042     virtual Constant *op_xor(const Constant *V1, const Constant *V2) const = 0;
00043     virtual Constant *shl(const Constant *V1, const Constant *V2) const = 0;
00044     virtual Constant *shr(const Constant *V1, const Constant *V2) const = 0;
00045     virtual Constant *lessthan(const Constant *V1, const Constant *V2) const =0;
00046     virtual Constant *equalto(const Constant *V1, const Constant *V2) const = 0;
00047 
00048     // Casting operators.
00049     virtual Constant *castToBool  (const Constant *V) const = 0;
00050     virtual Constant *castToSByte (const Constant *V) const = 0;
00051     virtual Constant *castToUByte (const Constant *V) const = 0;
00052     virtual Constant *castToShort (const Constant *V) const = 0;
00053     virtual Constant *castToUShort(const Constant *V) const = 0;
00054     virtual Constant *castToInt   (const Constant *V) const = 0;
00055     virtual Constant *castToUInt  (const Constant *V) const = 0;
00056     virtual Constant *castToLong  (const Constant *V) const = 0;
00057     virtual Constant *castToULong (const Constant *V) const = 0;
00058     virtual Constant *castToFloat (const Constant *V) const = 0;
00059     virtual Constant *castToDouble(const Constant *V) const = 0;
00060     virtual Constant *castToPointer(const Constant *V,
00061                                     const PointerType *Ty) const = 0;
00062     
00063     // ConstRules::get - Return an instance of ConstRules for the specified
00064     // constant operands.
00065     //
00066     static ConstRules &get(const Constant *V1, const Constant *V2);
00067   private:
00068     ConstRules(const ConstRules &);             // Do not implement
00069     ConstRules &operator=(const ConstRules &);  // Do not implement
00070   };
00071 }
00072 
00073 
00074 //===----------------------------------------------------------------------===//
00075 //                             TemplateRules Class
00076 //===----------------------------------------------------------------------===//
00077 //
00078 // TemplateRules - Implement a subclass of ConstRules that provides all 
00079 // operations as noops.  All other rules classes inherit from this class so 
00080 // that if functionality is needed in the future, it can simply be added here 
00081 // and to ConstRules without changing anything else...
00082 // 
00083 // This class also provides subclasses with typesafe implementations of methods
00084 // so that don't have to do type casting.
00085 //
00086 template<class ArgType, class SubClassName>
00087 class TemplateRules : public ConstRules {
00088 
00089   //===--------------------------------------------------------------------===//
00090   // Redirecting functions that cast to the appropriate types
00091   //===--------------------------------------------------------------------===//
00092 
00093   virtual Constant *add(const Constant *V1, const Constant *V2) const { 
00094     return SubClassName::Add((const ArgType *)V1, (const ArgType *)V2);  
00095   }
00096   virtual Constant *sub(const Constant *V1, const Constant *V2) const { 
00097     return SubClassName::Sub((const ArgType *)V1, (const ArgType *)V2);  
00098   }
00099   virtual Constant *mul(const Constant *V1, const Constant *V2) const { 
00100     return SubClassName::Mul((const ArgType *)V1, (const ArgType *)V2);  
00101   }
00102   virtual Constant *div(const Constant *V1, const Constant *V2) const { 
00103     return SubClassName::Div((const ArgType *)V1, (const ArgType *)V2);  
00104   }
00105   virtual Constant *rem(const Constant *V1, const Constant *V2) const { 
00106     return SubClassName::Rem((const ArgType *)V1, (const ArgType *)V2);  
00107   }
00108   virtual Constant *op_and(const Constant *V1, const Constant *V2) const { 
00109     return SubClassName::And((const ArgType *)V1, (const ArgType *)V2);  
00110   }
00111   virtual Constant *op_or(const Constant *V1, const Constant *V2) const { 
00112     return SubClassName::Or((const ArgType *)V1, (const ArgType *)V2);  
00113   }
00114   virtual Constant *op_xor(const Constant *V1, const Constant *V2) const { 
00115     return SubClassName::Xor((const ArgType *)V1, (const ArgType *)V2);  
00116   }
00117   virtual Constant *shl(const Constant *V1, const Constant *V2) const { 
00118     return SubClassName::Shl((const ArgType *)V1, (const ArgType *)V2);  
00119   }
00120   virtual Constant *shr(const Constant *V1, const Constant *V2) const { 
00121     return SubClassName::Shr((const ArgType *)V1, (const ArgType *)V2);  
00122   }
00123 
00124   virtual Constant *lessthan(const Constant *V1, const Constant *V2) const { 
00125     return SubClassName::LessThan((const ArgType *)V1, (const ArgType *)V2);
00126   }
00127   virtual Constant *equalto(const Constant *V1, const Constant *V2) const { 
00128     return SubClassName::EqualTo((const ArgType *)V1, (const ArgType *)V2);
00129   }
00130 
00131   // Casting operators.  ick
00132   virtual Constant *castToBool(const Constant *V) const {
00133     return SubClassName::CastToBool((const ArgType*)V);
00134   }
00135   virtual Constant *castToSByte(const Constant *V) const {
00136     return SubClassName::CastToSByte((const ArgType*)V);
00137   }
00138   virtual Constant *castToUByte(const Constant *V) const {
00139     return SubClassName::CastToUByte((const ArgType*)V);
00140   }
00141   virtual Constant *castToShort(const Constant *V) const {
00142     return SubClassName::CastToShort((const ArgType*)V);
00143   }
00144   virtual Constant *castToUShort(const Constant *V) const {
00145     return SubClassName::CastToUShort((const ArgType*)V);
00146   }
00147   virtual Constant *castToInt(const Constant *V) const {
00148     return SubClassName::CastToInt((const ArgType*)V);
00149   }
00150   virtual Constant *castToUInt(const Constant *V) const {
00151     return SubClassName::CastToUInt((const ArgType*)V);
00152   }
00153   virtual Constant *castToLong(const Constant *V) const {
00154     return SubClassName::CastToLong((const ArgType*)V);
00155   }
00156   virtual Constant *castToULong(const Constant *V) const {
00157     return SubClassName::CastToULong((const ArgType*)V);
00158   }
00159   virtual Constant *castToFloat(const Constant *V) const {
00160     return SubClassName::CastToFloat((const ArgType*)V);
00161   }
00162   virtual Constant *castToDouble(const Constant *V) const {
00163     return SubClassName::CastToDouble((const ArgType*)V);
00164   }
00165   virtual Constant *castToPointer(const Constant *V, 
00166                                   const PointerType *Ty) const {
00167     return SubClassName::CastToPointer((const ArgType*)V, Ty);
00168   }
00169 
00170   //===--------------------------------------------------------------------===//
00171   // Default "noop" implementations
00172   //===--------------------------------------------------------------------===//
00173 
00174   static Constant *Add(const ArgType *V1, const ArgType *V2) { return 0; }
00175   static Constant *Sub(const ArgType *V1, const ArgType *V2) { return 0; }
00176   static Constant *Mul(const ArgType *V1, const ArgType *V2) { return 0; }
00177   static Constant *Div(const ArgType *V1, const ArgType *V2) { return 0; }
00178   static Constant *Rem(const ArgType *V1, const ArgType *V2) { return 0; }
00179   static Constant *And(const ArgType *V1, const ArgType *V2) { return 0; }
00180   static Constant *Or (const ArgType *V1, const ArgType *V2) { return 0; }
00181   static Constant *Xor(const ArgType *V1, const ArgType *V2) { return 0; }
00182   static Constant *Shl(const ArgType *V1, const ArgType *V2) { return 0; }
00183   static Constant *Shr(const ArgType *V1, const ArgType *V2) { return 0; }
00184   static Constant *LessThan(const ArgType *V1, const ArgType *V2) {
00185     return 0;
00186   }
00187   static Constant *EqualTo(const ArgType *V1, const ArgType *V2) {
00188     return 0;
00189   }
00190 
00191   // Casting operators.  ick
00192   static Constant *CastToBool  (const Constant *V) { return 0; }
00193   static Constant *CastToSByte (const Constant *V) { return 0; }
00194   static Constant *CastToUByte (const Constant *V) { return 0; }
00195   static Constant *CastToShort (const Constant *V) { return 0; }
00196   static Constant *CastToUShort(const Constant *V) { return 0; }
00197   static Constant *CastToInt   (const Constant *V) { return 0; }
00198   static Constant *CastToUInt  (const Constant *V) { return 0; }
00199   static Constant *CastToLong  (const Constant *V) { return 0; }
00200   static Constant *CastToULong (const Constant *V) { return 0; }
00201   static Constant *CastToFloat (const Constant *V) { return 0; }
00202   static Constant *CastToDouble(const Constant *V) { return 0; }
00203   static Constant *CastToPointer(const Constant *,
00204                                  const PointerType *) {return 0;}
00205 };
00206 
00207 
00208 
00209 //===----------------------------------------------------------------------===//
00210 //                             EmptyRules Class
00211 //===----------------------------------------------------------------------===//
00212 //
00213 // EmptyRules provides a concrete base class of ConstRules that does nothing
00214 //
00215 struct EmptyRules : public TemplateRules<Constant, EmptyRules> {
00216   static Constant *EqualTo(const Constant *V1, const Constant *V2) {
00217     if (V1 == V2) return ConstantBool::True;
00218     return 0;
00219   }
00220 };
00221 
00222 
00223 
00224 //===----------------------------------------------------------------------===//
00225 //                              BoolRules Class
00226 //===----------------------------------------------------------------------===//
00227 //
00228 // BoolRules provides a concrete base class of ConstRules for the 'bool' type.
00229 //
00230 struct BoolRules : public TemplateRules<ConstantBool, BoolRules> {
00231 
00232   static Constant *LessThan(const ConstantBool *V1, const ConstantBool *V2){
00233     return ConstantBool::get(V1->getValue() < V2->getValue());
00234   }
00235 
00236   static Constant *EqualTo(const Constant *V1, const Constant *V2) {
00237     return ConstantBool::get(V1 == V2);
00238   }
00239 
00240   static Constant *And(const ConstantBool *V1, const ConstantBool *V2) {
00241     return ConstantBool::get(V1->getValue() & V2->getValue());
00242   }
00243 
00244   static Constant *Or(const ConstantBool *V1, const ConstantBool *V2) {
00245     return ConstantBool::get(V1->getValue() | V2->getValue());
00246   }
00247 
00248   static Constant *Xor(const ConstantBool *V1, const ConstantBool *V2) {
00249     return ConstantBool::get(V1->getValue() ^ V2->getValue());
00250   }
00251 
00252   // Casting operators.  ick
00253 #define DEF_CAST(TYPE, CLASS, CTYPE) \
00254   static Constant *CastTo##TYPE  (const ConstantBool *V) {    \
00255     return CLASS::get(Type::TYPE##Ty, (CTYPE)(bool)V->getValue()); \
00256   }
00257 
00258   DEF_CAST(Bool  , ConstantBool, bool)
00259   DEF_CAST(SByte , ConstantSInt, signed char)
00260   DEF_CAST(UByte , ConstantUInt, unsigned char)
00261   DEF_CAST(Short , ConstantSInt, signed short)
00262   DEF_CAST(UShort, ConstantUInt, unsigned short)
00263   DEF_CAST(Int   , ConstantSInt, signed int)
00264   DEF_CAST(UInt  , ConstantUInt, unsigned int)
00265   DEF_CAST(Long  , ConstantSInt, int64_t)
00266   DEF_CAST(ULong , ConstantUInt, uint64_t)
00267   DEF_CAST(Float , ConstantFP  , float)
00268   DEF_CAST(Double, ConstantFP  , double)
00269 #undef DEF_CAST
00270 };
00271 
00272 
00273 //===----------------------------------------------------------------------===//
00274 //                            NullPointerRules Class
00275 //===----------------------------------------------------------------------===//
00276 //
00277 // NullPointerRules provides a concrete base class of ConstRules for null
00278 // pointers.
00279 //
00280 struct NullPointerRules : public TemplateRules<ConstantPointerNull,
00281                                                NullPointerRules> {
00282   static Constant *EqualTo(const Constant *V1, const Constant *V2) {
00283     return ConstantBool::True;  // Null pointers are always equal
00284   }
00285   static Constant *CastToBool(const Constant *V) {
00286     return ConstantBool::False;
00287   }
00288   static Constant *CastToSByte (const Constant *V) {
00289     return ConstantSInt::get(Type::SByteTy, 0);
00290   }
00291   static Constant *CastToUByte (const Constant *V) {
00292     return ConstantUInt::get(Type::UByteTy, 0);
00293   }
00294   static Constant *CastToShort (const Constant *V) {
00295     return ConstantSInt::get(Type::ShortTy, 0);
00296   }
00297   static Constant *CastToUShort(const Constant *V) {
00298     return ConstantUInt::get(Type::UShortTy, 0);
00299   }
00300   static Constant *CastToInt   (const Constant *V) {
00301     return ConstantSInt::get(Type::IntTy, 0);
00302   }
00303   static Constant *CastToUInt  (const Constant *V) {
00304     return ConstantUInt::get(Type::UIntTy, 0);
00305   }
00306   static Constant *CastToLong  (const Constant *V) {
00307     return ConstantSInt::get(Type::LongTy, 0);
00308   }
00309   static Constant *CastToULong (const Constant *V) {
00310     return ConstantUInt::get(Type::ULongTy, 0);
00311   }
00312   static Constant *CastToFloat (const Constant *V) {
00313     return ConstantFP::get(Type::FloatTy, 0);
00314   }
00315   static Constant *CastToDouble(const Constant *V) {
00316     return ConstantFP::get(Type::DoubleTy, 0);
00317   }
00318 
00319   static Constant *CastToPointer(const ConstantPointerNull *V,
00320                                  const PointerType *PTy) {
00321     return ConstantPointerNull::get(PTy);
00322   }
00323 };
00324 
00325 
00326 //===----------------------------------------------------------------------===//
00327 //                             DirectRules Class
00328 //===----------------------------------------------------------------------===//
00329 //
00330 // DirectRules provides a concrete base classes of ConstRules for a variety of
00331 // different types.  This allows the C++ compiler to automatically generate our
00332 // constant handling operations in a typesafe and accurate manner.
00333 //
00334 template<class ConstantClass, class BuiltinType, Type **Ty, class SuperClass>
00335 struct DirectRules : public TemplateRules<ConstantClass, SuperClass> {
00336   static Constant *Add(const ConstantClass *V1, const ConstantClass *V2) {
00337     BuiltinType R = (BuiltinType)V1->getValue() + (BuiltinType)V2->getValue();
00338     return ConstantClass::get(*Ty, R);
00339   }
00340 
00341   static Constant *Sub(const ConstantClass *V1, const ConstantClass *V2) {
00342     BuiltinType R = (BuiltinType)V1->getValue() - (BuiltinType)V2->getValue();
00343     return ConstantClass::get(*Ty, R);
00344   }
00345 
00346   static Constant *Mul(const ConstantClass *V1, const ConstantClass *V2) {
00347     BuiltinType R = (BuiltinType)V1->getValue() * (BuiltinType)V2->getValue();
00348     return ConstantClass::get(*Ty, R);
00349   }
00350 
00351   static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) {
00352     if (V2->isNullValue()) return 0;
00353     BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue();
00354     return ConstantClass::get(*Ty, R);
00355   }
00356 
00357   static Constant *LessThan(const ConstantClass *V1, const ConstantClass *V2) {
00358     bool R = (BuiltinType)V1->getValue() < (BuiltinType)V2->getValue();
00359     return ConstantBool::get(R);
00360   } 
00361 
00362   static Constant *EqualTo(const ConstantClass *V1, const ConstantClass *V2) {
00363     bool R = (BuiltinType)V1->getValue() == (BuiltinType)V2->getValue();
00364     return ConstantBool::get(R);
00365   }
00366 
00367   static Constant *CastToPointer(const ConstantClass *V,
00368                                  const PointerType *PTy) {
00369     if (V->isNullValue())    // Is it a FP or Integral null value?
00370       return ConstantPointerNull::get(PTy);
00371     return 0;  // Can't const prop other types of pointers
00372   }
00373 
00374   // Casting operators.  ick
00375 #define DEF_CAST(TYPE, CLASS, CTYPE) \
00376   static Constant *CastTo##TYPE  (const ConstantClass *V) {    \
00377     return CLASS::get(Type::TYPE##Ty, (CTYPE)(BuiltinType)V->getValue()); \
00378   }
00379 
00380   DEF_CAST(Bool  , ConstantBool, bool)
00381   DEF_CAST(SByte , ConstantSInt, signed char)
00382   DEF_CAST(UByte , ConstantUInt, unsigned char)
00383   DEF_CAST(Short , ConstantSInt, signed short)
00384   DEF_CAST(UShort, ConstantUInt, unsigned short)
00385   DEF_CAST(Int   , ConstantSInt, signed int)
00386   DEF_CAST(UInt  , ConstantUInt, unsigned int)
00387   DEF_CAST(Long  , ConstantSInt, int64_t)
00388   DEF_CAST(ULong , ConstantUInt, uint64_t)
00389   DEF_CAST(Float , ConstantFP  , float)
00390   DEF_CAST(Double, ConstantFP  , double)
00391 #undef DEF_CAST
00392 };
00393 
00394 
00395 //===----------------------------------------------------------------------===//
00396 //                           DirectIntRules Class
00397 //===----------------------------------------------------------------------===//
00398 //
00399 // DirectIntRules provides implementations of functions that are valid on
00400 // integer types, but not all types in general.
00401 //
00402 template <class ConstantClass, class BuiltinType, Type **Ty>
00403 struct DirectIntRules
00404   : public DirectRules<ConstantClass, BuiltinType, Ty,
00405                        DirectIntRules<ConstantClass, BuiltinType, Ty> > {
00406 
00407   static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) {
00408     if (V2->isNullValue()) return 0;
00409     if (V2->isAllOnesValue() &&              // MIN_INT / -1
00410         (BuiltinType)V1->getValue() == -(BuiltinType)V1->getValue())
00411       return 0;
00412     BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue();
00413     return ConstantClass::get(*Ty, R);
00414   }
00415 
00416   static Constant *Rem(const ConstantClass *V1,
00417                        const ConstantClass *V2) {
00418     if (V2->isNullValue()) return 0;         // X / 0
00419     if (V2->isAllOnesValue() &&              // MIN_INT / -1
00420         (BuiltinType)V1->getValue() == -(BuiltinType)V1->getValue())
00421       return 0;
00422     BuiltinType R = (BuiltinType)V1->getValue() % (BuiltinType)V2->getValue();
00423     return ConstantClass::get(*Ty, R);
00424   }
00425 
00426   static Constant *And(const ConstantClass *V1, const ConstantClass *V2) {
00427     BuiltinType R = (BuiltinType)V1->getValue() & (BuiltinType)V2->getValue();
00428     return ConstantClass::get(*Ty, R);
00429   }
00430   static Constant *Or(const ConstantClass *V1, const ConstantClass *V2) {
00431     BuiltinType R = (BuiltinType)V1->getValue() | (BuiltinType)V2->getValue();
00432     return ConstantClass::get(*Ty, R);
00433   }
00434   static Constant *Xor(const ConstantClass *V1, const ConstantClass *V2) {
00435     BuiltinType R = (BuiltinType)V1->getValue() ^ (BuiltinType)V2->getValue();
00436     return ConstantClass::get(*Ty, R);
00437   }
00438 
00439   static Constant *Shl(const ConstantClass *V1, const ConstantClass *V2) {
00440     BuiltinType R = (BuiltinType)V1->getValue() << (BuiltinType)V2->getValue();
00441     return ConstantClass::get(*Ty, R);
00442   }
00443 
00444   static Constant *Shr(const ConstantClass *V1, const ConstantClass *V2) {
00445     BuiltinType R = (BuiltinType)V1->getValue() >> (BuiltinType)V2->getValue();
00446     return ConstantClass::get(*Ty, R);
00447   }
00448 };
00449 
00450 
00451 //===----------------------------------------------------------------------===//
00452 //                           DirectFPRules Class
00453 //===----------------------------------------------------------------------===//
00454 //
00455 /// DirectFPRules provides implementations of functions that are valid on
00456 /// floating point types, but not all types in general.
00457 ///
00458 template <class ConstantClass, class BuiltinType, Type **Ty>
00459 struct DirectFPRules
00460   : public DirectRules<ConstantClass, BuiltinType, Ty,
00461                        DirectFPRules<ConstantClass, BuiltinType, Ty> > {
00462   static Constant *Rem(const ConstantClass *V1, const ConstantClass *V2) {
00463     if (V2->isNullValue()) return 0;
00464     BuiltinType Result = std::fmod((BuiltinType)V1->getValue(),
00465                                    (BuiltinType)V2->getValue());
00466     return ConstantClass::get(*Ty, Result);
00467   }
00468 };
00469 
00470 
00471 /// ConstRules::get - This method returns the constant rules implementation that
00472 /// implements the semantics of the two specified constants.
00473 ConstRules &ConstRules::get(const Constant *V1, const Constant *V2) {
00474   static EmptyRules       EmptyR;
00475   static BoolRules        BoolR;
00476   static NullPointerRules NullPointerR;
00477   static DirectIntRules<ConstantSInt,   signed char , &Type::SByteTy>  SByteR;
00478   static DirectIntRules<ConstantUInt, unsigned char , &Type::UByteTy>  UByteR;
00479   static DirectIntRules<ConstantSInt,   signed short, &Type::ShortTy>  ShortR;
00480   static DirectIntRules<ConstantUInt, unsigned short, &Type::UShortTy> UShortR;
00481   static DirectIntRules<ConstantSInt,   signed int  , &Type::IntTy>    IntR;
00482   static DirectIntRules<ConstantUInt, unsigned int  , &Type::UIntTy>   UIntR;
00483   static DirectIntRules<ConstantSInt,  int64_t      , &Type::LongTy>   LongR;
00484   static DirectIntRules<ConstantUInt, uint64_t      , &Type::ULongTy>  ULongR;
00485   static DirectFPRules <ConstantFP  , float         , &Type::FloatTy>  FloatR;
00486   static DirectFPRules <ConstantFP  , double        , &Type::DoubleTy> DoubleR;
00487 
00488   if (isa<ConstantExpr>(V1) || isa<ConstantExpr>(V2) ||
00489       isa<GlobalValue>(V1) || isa<GlobalValue>(V2) ||
00490       isa<UndefValue>(V1) || isa<UndefValue>(V2))
00491     return EmptyR;
00492 
00493   switch (V1->getType()->getTypeID()) {
00494   default: assert(0 && "Unknown value type for constant folding!");
00495   case Type::BoolTyID:    return BoolR;
00496   case Type::PointerTyID: return NullPointerR;
00497   case Type::SByteTyID:   return SByteR;
00498   case Type::UByteTyID:   return UByteR;
00499   case Type::ShortTyID:   return ShortR;
00500   case Type::UShortTyID:  return UShortR;
00501   case Type::IntTyID:     return IntR;
00502   case Type::UIntTyID:    return UIntR;
00503   case Type::LongTyID:    return LongR;
00504   case Type::ULongTyID:   return ULongR;
00505   case Type::FloatTyID:   return FloatR;
00506   case Type::DoubleTyID:  return DoubleR;
00507   }
00508 }
00509 
00510 
00511 //===----------------------------------------------------------------------===//
00512 //                ConstantFold*Instruction Implementations
00513 //===----------------------------------------------------------------------===//
00514 //
00515 // These methods contain the special case hackery required to symbolically
00516 // evaluate some constant expression cases, and use the ConstantRules class to
00517 // evaluate normal constants.
00518 //
00519 static unsigned getSize(const Type *Ty) {
00520   unsigned S = Ty->getPrimitiveSize();
00521   return S ? S : 8;  // Treat pointers at 8 bytes
00522 }
00523 
00524 Constant *llvm::ConstantFoldCastInstruction(const Constant *V,
00525                                             const Type *DestTy) {
00526   if (V->getType() == DestTy) return (Constant*)V;
00527 
00528   // Cast of a global address to boolean is always true.
00529   if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
00530     if (DestTy == Type::BoolTy)
00531       // FIXME: When we support 'external weak' references, we have to prevent
00532       // this transformation from happening.  In the meantime we avoid folding
00533       // any cast of an external symbol.
00534       if (!GV->isExternal())
00535         return ConstantBool::True;
00536   } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
00537     if (CE->getOpcode() == Instruction::Cast) {
00538       Constant *Op = const_cast<Constant*>(CE->getOperand(0));
00539       // Try to not produce a cast of a cast, which is almost always redundant.
00540       if (!Op->getType()->isFloatingPoint() &&
00541           !CE->getType()->isFloatingPoint() &&
00542           !DestTy->isFloatingPoint()) {
00543         unsigned S1 = getSize(Op->getType()), S2 = getSize(CE->getType());
00544         unsigned S3 = getSize(DestTy);
00545         if (Op->getType() == DestTy && S3 >= S2)
00546           return Op;
00547         if (S1 >= S2 && S2 >= S3)
00548           return ConstantExpr::getCast(Op, DestTy);
00549         if (S1 <= S2 && S2 >= S3 && S1 <= S3)
00550           return ConstantExpr::getCast(Op, DestTy);
00551       }
00552     } else if (CE->getOpcode() == Instruction::GetElementPtr) {
00553       // If all of the indexes in the GEP are null values, there is no pointer
00554       // adjustment going on.  We might as well cast the source pointer.
00555       bool isAllNull = true;
00556       for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
00557         if (!CE->getOperand(i)->isNullValue()) {
00558           isAllNull = false;
00559           break;
00560         }
00561       if (isAllNull)
00562         return ConstantExpr::getCast(CE->getOperand(0), DestTy);
00563     }
00564   } else if (isa<UndefValue>(V)) {
00565     return UndefValue::get(DestTy);
00566   }
00567 
00568   // Check to see if we are casting an pointer to an aggregate to a pointer to
00569   // the first element.  If so, return the appropriate GEP instruction.
00570   if (const PointerType *PTy = dyn_cast<PointerType>(V->getType()))
00571     if (const PointerType *DPTy = dyn_cast<PointerType>(DestTy)) {
00572       std::vector<Value*> IdxList;
00573       IdxList.push_back(Constant::getNullValue(Type::IntTy));
00574       const Type *ElTy = PTy->getElementType();
00575       while (ElTy != DPTy->getElementType()) {
00576         if (const StructType *STy = dyn_cast<StructType>(ElTy)) {
00577           if (STy->getNumElements() == 0) break;
00578           ElTy = STy->getElementType(0);
00579           IdxList.push_back(Constant::getNullValue(Type::UIntTy));
00580         } else if (const SequentialType *STy = dyn_cast<SequentialType>(ElTy)) {
00581           if (isa<PointerType>(ElTy)) break;  // Can't index into pointers!
00582           ElTy = STy->getElementType();
00583           IdxList.push_back(IdxList[0]);
00584         } else {
00585           break;
00586         }
00587       }
00588 
00589       if (ElTy == DPTy->getElementType())
00590         return ConstantExpr::getGetElementPtr(const_cast<Constant*>(V),IdxList);
00591     }
00592 
00593   ConstRules &Rules = ConstRules::get(V, V);
00594 
00595   switch (DestTy->getTypeID()) {
00596   case Type::BoolTyID:    return Rules.castToBool(V);
00597   case Type::UByteTyID:   return Rules.castToUByte(V);
00598   case Type::SByteTyID:   return Rules.castToSByte(V);
00599   case Type::UShortTyID:  return Rules.castToUShort(V);
00600   case Type::ShortTyID:   return Rules.castToShort(V);
00601   case Type::UIntTyID:    return Rules.castToUInt(V);
00602   case Type::IntTyID:     return Rules.castToInt(V);
00603   case Type::ULongTyID:   return Rules.castToULong(V);
00604   case Type::LongTyID:    return Rules.castToLong(V);
00605   case Type::FloatTyID:   return Rules.castToFloat(V);
00606   case Type::DoubleTyID:  return Rules.castToDouble(V);
00607   case Type::PointerTyID:
00608     return Rules.castToPointer(V, cast<PointerType>(DestTy));
00609   default: return 0;
00610   }
00611 }
00612 
00613 Constant *llvm::ConstantFoldSelectInstruction(const Constant *Cond,
00614                                               const Constant *V1,
00615                                               const Constant *V2) {
00616   if (Cond == ConstantBool::True)
00617     return const_cast<Constant*>(V1);
00618   else if (Cond == ConstantBool::False)
00619     return const_cast<Constant*>(V2);
00620 
00621   if (isa<UndefValue>(V1)) return const_cast<Constant*>(V2);
00622   if (isa<UndefValue>(V2)) return const_cast<Constant*>(V1);
00623   if (isa<UndefValue>(Cond)) return const_cast<Constant*>(V1);
00624   return 0;
00625 }
00626 
00627 
00628 /// IdxCompare - Compare the two constants as though they were getelementptr
00629 /// indices.  This allows coersion of the types to be the same thing.
00630 ///
00631 /// If the two constants are the "same" (after coersion), return 0.  If the
00632 /// first is less than the second, return -1, if the second is less than the
00633 /// first, return 1.  If the constants are not integral, return -2.
00634 ///
00635 static int IdxCompare(Constant *C1, Constant *C2) {
00636   if (C1 == C2) return 0;
00637 
00638   // Ok, we found a different index.  Are either of the operands
00639   // ConstantExprs?  If so, we can't do anything with them.
00640   if (!isa<ConstantInt>(C1) || !isa<ConstantInt>(C2))
00641     return -2; // don't know!
00642   
00643   // Ok, we have two differing integer indices.  Sign extend them to be the same
00644   // type.  Long is always big enough, so we use it.
00645   C1 = ConstantExpr::getSignExtend(C1, Type::LongTy);
00646   C2 = ConstantExpr::getSignExtend(C2, Type::LongTy);
00647   if (C1 == C2) return 0;  // Are they just differing types?
00648 
00649   // If they are really different, now that they are the same type, then we
00650   // found a difference!
00651   if (cast<ConstantSInt>(C1)->getValue() < cast<ConstantSInt>(C2)->getValue())
00652     return -1;
00653   else
00654     return 1;
00655 }
00656 
00657 /// evaluateRelation - This function determines if there is anything we can
00658 /// decide about the two constants provided.  This doesn't need to handle simple
00659 /// things like integer comparisons, but should instead handle ConstantExprs
00660 /// and GlobalValuess.  If we can determine that the two constants have a
00661 /// particular relation to each other, we should return the corresponding SetCC
00662 /// code, otherwise return Instruction::BinaryOpsEnd.
00663 ///
00664 /// To simplify this code we canonicalize the relation so that the first
00665 /// operand is always the most "complex" of the two.  We consider simple
00666 /// constants (like ConstantInt) to be the simplest, followed by
00667 /// GlobalValues, followed by ConstantExpr's (the most complex).
00668 ///
00669 static Instruction::BinaryOps evaluateRelation(const Constant *V1,
00670                                                const Constant *V2) {
00671   assert(V1->getType() == V2->getType() &&
00672          "Cannot compare different types of values!");
00673   if (V1 == V2) return Instruction::SetEQ;
00674 
00675   if (!isa<ConstantExpr>(V1) && !isa<GlobalValue>(V1)) {
00676     // If the first operand is simple, swap operands.
00677     assert((isa<GlobalValue>(V2) || isa<ConstantExpr>(V2)) &&
00678            "Simple cases should have been handled by caller!");
00679     Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1);
00680     if (SwappedRelation != Instruction::BinaryOpsEnd)
00681       return SetCondInst::getSwappedCondition(SwappedRelation);
00682 
00683   } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(V1)){
00684     if (isa<ConstantExpr>(V2)) {  // Swap as necessary.
00685     Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1);
00686     if (SwappedRelation != Instruction::BinaryOpsEnd)
00687       return SetCondInst::getSwappedCondition(SwappedRelation);
00688     else
00689       return Instruction::BinaryOpsEnd;
00690     }
00691 
00692     // Now we know that the RHS is a GlobalValue or simple constant,
00693     // which (since the types must match) means that it's a ConstantPointerNull.
00694     if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) {
00695       assert(CPR1 != CPR2 &&
00696              "GVs for the same value exist at different addresses??");
00697       // FIXME: If both globals are external weak, they might both be null!
00698       return Instruction::SetNE;
00699     } else {
00700       assert(isa<ConstantPointerNull>(V2) && "Canonicalization guarantee!");
00701       // Global can never be null.  FIXME: if we implement external weak
00702       // linkage, this is not necessarily true!
00703       return Instruction::SetNE;
00704     }
00705 
00706   } else {
00707     // Ok, the LHS is known to be a constantexpr.  The RHS can be any of a
00708     // constantexpr, a CPR, or a simple constant.
00709     const ConstantExpr *CE1 = cast<ConstantExpr>(V1);
00710     Constant *CE1Op0 = CE1->getOperand(0);
00711 
00712     switch (CE1->getOpcode()) {
00713     case Instruction::Cast:
00714       // If the cast is not actually changing bits, and the second operand is a
00715       // null pointer, do the comparison with the pre-casted value.
00716       if (V2->isNullValue() &&
00717           CE1->getType()->isLosslesslyConvertibleTo(CE1Op0->getType()))
00718         return evaluateRelation(CE1Op0,
00719                                 Constant::getNullValue(CE1Op0->getType()));
00720       break;
00721 
00722     case Instruction::GetElementPtr:
00723       // Ok, since this is a getelementptr, we know that the constant has a
00724       // pointer type.  Check the various cases.
00725       if (isa<ConstantPointerNull>(V2)) {
00726         // If we are comparing a GEP to a null pointer, check to see if the base
00727         // of the GEP equals the null pointer.
00728         if (isa<GlobalValue>(CE1Op0)) {
00729           // FIXME: this is not true when we have external weak references!
00730           // No offset can go from a global to a null pointer.
00731           return Instruction::SetGT;
00732         } else if (isa<ConstantPointerNull>(CE1Op0)) {
00733           // If we are indexing from a null pointer, check to see if we have any
00734           // non-zero indices.
00735           for (unsigned i = 1, e = CE1->getNumOperands(); i != e; ++i)
00736             if (!CE1->getOperand(i)->isNullValue())
00737               // Offsetting from null, must not be equal.
00738               return Instruction::SetGT;
00739           // Only zero indexes from null, must still be zero.
00740           return Instruction::SetEQ;
00741         }
00742         // Otherwise, we can't really say if the first operand is null or not.
00743       } else if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) {
00744         if (isa<ConstantPointerNull>(CE1Op0)) {
00745           // FIXME: This is not true with external weak references.
00746           return Instruction::SetLT;
00747         } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(CE1Op0)) {
00748           if (CPR1 == CPR2) {
00749             // If this is a getelementptr of the same global, then it must be
00750             // different.  Because the types must match, the getelementptr could
00751             // only have at most one index, and because we fold getelementptr's
00752             // with a single zero index, it must be nonzero.
00753             assert(CE1->getNumOperands() == 2 &&
00754                    !CE1->getOperand(1)->isNullValue() &&
00755                    "Suprising getelementptr!");
00756             return Instruction::SetGT;
00757           } else {
00758             // If they are different globals, we don't know what the value is,
00759             // but they can't be equal.
00760             return Instruction::SetNE;
00761           }
00762         }
00763       } else {
00764         const ConstantExpr *CE2 = cast<ConstantExpr>(V2);
00765         const Constant *CE2Op0 = CE2->getOperand(0);
00766 
00767         // There are MANY other foldings that we could perform here.  They will
00768         // probably be added on demand, as they seem needed.
00769         switch (CE2->getOpcode()) {
00770         default: break;
00771         case Instruction::GetElementPtr:
00772           // By far the most common case to handle is when the base pointers are
00773           // obviously to the same or different globals.
00774           if (isa<GlobalValue>(CE1Op0) && isa<GlobalValue>(CE2Op0)) {
00775             if (CE1Op0 != CE2Op0) // Don't know relative ordering, but not equal
00776               return Instruction::SetNE;
00777             // Ok, we know that both getelementptr instructions are based on the
00778             // same global.  From this, we can precisely determine the relative
00779             // ordering of the resultant pointers.
00780             unsigned i = 1;
00781             
00782             // Compare all of the operands the GEP's have in common.
00783             for (;i != CE1->getNumOperands() && i != CE2->getNumOperands(); ++i)
00784               switch (IdxCompare(CE1->getOperand(i), CE2->getOperand(i))) {
00785               case -1: return Instruction::SetLT;
00786               case 1:  return Instruction::SetGT;
00787               case -2: return Instruction::BinaryOpsEnd;
00788               }
00789 
00790             // Ok, we ran out of things they have in common.  If any leftovers
00791             // are non-zero then we have a difference, otherwise we are equal.
00792             for (; i < CE1->getNumOperands(); ++i)
00793               if (!CE1->getOperand(i)->isNullValue())
00794                 return Instruction::SetGT;
00795             for (; i < CE2->getNumOperands(); ++i)
00796               if (!CE2->getOperand(i)->isNullValue())
00797                 return Instruction::SetLT;
00798             return Instruction::SetEQ;
00799           }
00800         }
00801       }
00802       
00803     default:
00804       break;
00805     }
00806   }
00807 
00808   return Instruction::BinaryOpsEnd;
00809 }
00810 
00811 Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode,
00812                                               const Constant *V1,
00813                                               const Constant *V2) {
00814   Constant *C = 0;
00815   switch (Opcode) {
00816   default:                   break;
00817   case Instruction::Add:     C = ConstRules::get(V1, V2).add(V1, V2); break;
00818   case Instruction::Sub:     C = ConstRules::get(V1, V2).sub(V1, V2); break;
00819   case Instruction::Mul:     C = ConstRules::get(V1, V2).mul(V1, V2); break;
00820   case Instruction::Div:     C = ConstRules::get(V1, V2).div(V1, V2); break;
00821   case Instruction::Rem:     C = ConstRules::get(V1, V2).rem(V1, V2); break;
00822   case Instruction::And:     C = ConstRules::get(V1, V2).op_and(V1, V2); break;
00823   case Instruction::Or:      C = ConstRules::get(V1, V2).op_or (V1, V2); break;
00824   case Instruction::Xor:     C = ConstRules::get(V1, V2).op_xor(V1, V2); break;
00825   case Instruction::Shl:     C = ConstRules::get(V1, V2).shl(V1, V2); break;
00826   case Instruction::Shr:     C = ConstRules::get(V1, V2).shr(V1, V2); break;
00827   case Instruction::SetEQ:   C = ConstRules::get(V1, V2).equalto(V1, V2); break;
00828   case Instruction::SetLT:   C = ConstRules::get(V1, V2).lessthan(V1, V2);break;
00829   case Instruction::SetGT:   C = ConstRules::get(V1, V2).lessthan(V2, V1);break;
00830   case Instruction::SetNE:   // V1 != V2  ===  !(V1 == V2)
00831     C = ConstRules::get(V1, V2).equalto(V1, V2);
00832     if (C) return ConstantExpr::get(Instruction::Xor, C, ConstantBool::True);
00833     break;
00834   case Instruction::SetLE:   // V1 <= V2  ===  !(V2 < V1)
00835     C = ConstRules::get(V1, V2).lessthan(V2, V1);
00836     if (C) return ConstantExpr::get(Instruction::Xor, C, ConstantBool::True);
00837     break;
00838   case Instruction::SetGE:   // V1 >= V2  ===  !(V1 < V2)
00839     C = ConstRules::get(V1, V2).lessthan(V1, V2);
00840     if (C) return ConstantExpr::get(Instruction::Xor, C, ConstantBool::True);
00841     break;
00842   }
00843 
00844   // If we successfully folded the expression, return it now.
00845   if (C) return C;
00846 
00847   if (SetCondInst::isRelational(Opcode)) {
00848     if (isa<UndefValue>(V1) || isa<UndefValue>(V2))
00849       return UndefValue::get(Type::BoolTy);
00850     switch (evaluateRelation(V1, V2)) {
00851     default: assert(0 && "Unknown relational!");
00852     case Instruction::BinaryOpsEnd:
00853       break;  // Couldn't determine anything about these constants.
00854     case Instruction::SetEQ:   // We know the constants are equal!
00855       // If we know the constants are equal, we can decide the result of this
00856       // computation precisely.
00857       return ConstantBool::get(Opcode == Instruction::SetEQ ||
00858                                Opcode == Instruction::SetLE ||
00859                                Opcode == Instruction::SetGE);
00860     case Instruction::SetLT:
00861       // If we know that V1 < V2, we can decide the result of this computation
00862       // precisely.
00863       return ConstantBool::get(Opcode == Instruction::SetLT ||
00864                                Opcode == Instruction::SetNE ||
00865                                Opcode == Instruction::SetLE);
00866     case Instruction::SetGT:
00867       // If we know that V1 > V2, we can decide the result of this computation
00868       // precisely.
00869       return ConstantBool::get(Opcode == Instruction::SetGT ||
00870                                Opcode == Instruction::SetNE ||
00871                                Opcode == Instruction::SetGE);
00872     case Instruction::SetLE:
00873       // If we know that V1 <= V2, we can only partially decide this relation.
00874       if (Opcode == Instruction::SetGT) return ConstantBool::False;
00875       if (Opcode == Instruction::SetLT) return ConstantBool::True;
00876       break;
00877 
00878     case Instruction::SetGE:
00879       // If we know that V1 >= V2, we can only partially decide this relation.
00880       if (Opcode == Instruction::SetLT) return ConstantBool::False;
00881       if (Opcode == Instruction::SetGT) return ConstantBool::True;
00882       break;
00883       
00884     case Instruction::SetNE:
00885       // If we know that V1 != V2, we can only partially decide this relation.
00886       if (Opcode == Instruction::SetEQ) return ConstantBool::False;
00887       if (Opcode == Instruction::SetNE) return ConstantBool::True;
00888       break;
00889     }
00890   }
00891 
00892   if (isa<UndefValue>(V1) || isa<UndefValue>(V2)) {
00893     switch (Opcode) {
00894     case Instruction::Add:
00895     case Instruction::Sub:
00896     case Instruction::Xor:
00897       return UndefValue::get(V1->getType());
00898 
00899     case Instruction::Mul:
00900     case Instruction::And:
00901       return Constant::getNullValue(V1->getType());
00902     case Instruction::Div:
00903     case Instruction::Rem:
00904       if (!isa<UndefValue>(V2))     // undef/X -> 0
00905         return Constant::getNullValue(V1->getType());
00906       return const_cast<Constant*>(V2);                // X/undef -> undef
00907     case Instruction::Or:           // X|undef -> -1
00908       return ConstantInt::getAllOnesValue(V1->getType());
00909     case Instruction::Shr:
00910       if (!isa<UndefValue>(V2)) {
00911         if (V1->getType()->isSigned())
00912           return const_cast<Constant*>(V1);  // undef >>s X -> undef
00913         // undef >>u X -> 0
00914       } else if (isa<UndefValue>(V1)) {
00915         return const_cast<Constant*>(V1);   //  undef >> undef -> undef
00916       } else {
00917         if (V1->getType()->isSigned())
00918           return const_cast<Constant*>(V1);  // X >>s undef -> X
00919         // X >>u undef -> 0
00920       }
00921       return Constant::getNullValue(V1->getType());
00922 
00923     case Instruction::Shl:
00924       // undef << X -> 0   X << undef -> 0
00925       return Constant::getNullValue(V1->getType());
00926     }
00927   }
00928 
00929   if (const ConstantExpr *CE1 = dyn_cast<ConstantExpr>(V1)) {
00930     if (const ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2)) {
00931       // There are many possible foldings we could do here.  We should probably
00932       // at least fold add of a pointer with an integer into the appropriate
00933       // getelementptr.  This will improve alias analysis a bit.
00934 
00935 
00936 
00937 
00938     } else {
00939       // Just implement a couple of simple identities.
00940       switch (Opcode) {
00941       case Instruction::Add:
00942         if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X + 0 == X
00943         break;
00944       case Instruction::Sub:
00945         if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X - 0 == X
00946         break;
00947       case Instruction::Mul:
00948         if (V2->isNullValue()) return const_cast<Constant*>(V2);  // X * 0 == 0
00949         if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
00950           if (CI->getRawValue() == 1)
00951             return const_cast<Constant*>(V1);                     // X * 1 == X
00952         break;
00953       case Instruction::Div:
00954         if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
00955           if (CI->getRawValue() == 1)
00956             return const_cast<Constant*>(V1);                     // X / 1 == X
00957         break;
00958       case Instruction::Rem:
00959         if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
00960           if (CI->getRawValue() == 1)
00961             return Constant::getNullValue(CI->getType()); // X % 1 == 0
00962         break;
00963       case Instruction::And:
00964         if (cast<ConstantIntegral>(V2)->isAllOnesValue())
00965           return const_cast<Constant*>(V1);                       // X & -1 == X
00966         if (V2->isNullValue()) return const_cast<Constant*>(V2);  // X & 0 == 0
00967         if (CE1->getOpcode() == Instruction::Cast &&
00968             isa<GlobalValue>(CE1->getOperand(0))) {
00969           GlobalValue *CPR = cast<GlobalValue>(CE1->getOperand(0));
00970 
00971           // Functions are at least 4-byte aligned.  If and'ing the address of a
00972           // function with a constant < 4, fold it to zero.
00973           if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
00974             if (CI->getRawValue() < 4 && isa<Function>(CPR))
00975               return Constant::getNullValue(CI->getType());
00976         }
00977         break;
00978       case Instruction::Or:
00979         if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X | 0 == X
00980         if (cast<ConstantIntegral>(V2)->isAllOnesValue())
00981           return const_cast<Constant*>(V2);  // X | -1 == -1
00982         break;
00983       case Instruction::Xor:
00984         if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X ^ 0 == X
00985         break;
00986       }
00987     }
00988 
00989   } else if (const ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2)) {
00990     // If V2 is a constant expr and V1 isn't, flop them around and fold the
00991     // other way if possible.
00992     switch (Opcode) {
00993     case Instruction::Add:
00994     case Instruction::Mul:
00995     case Instruction::And:
00996     case Instruction::Or:
00997     case Instruction::Xor:
00998     case Instruction::SetEQ:
00999     case Instruction::SetNE:
01000       // No change of opcode required.
01001       return ConstantFoldBinaryInstruction(Opcode, V2, V1);
01002 
01003     case Instruction::SetLT:
01004     case Instruction::SetGT:
01005     case Instruction::SetLE:
01006     case Instruction::SetGE:
01007       // Change the opcode as necessary to swap the operands.
01008       Opcode = SetCondInst::getSwappedCondition((Instruction::BinaryOps)Opcode);
01009       return ConstantFoldBinaryInstruction(Opcode, V2, V1);
01010 
01011     case Instruction::Shl:
01012     case Instruction::Shr:
01013     case Instruction::Sub:
01014     case Instruction::Div:
01015     case Instruction::Rem:
01016     default:  // These instructions cannot be flopped around.
01017       break;
01018     }
01019   }
01020   return 0;
01021 }
01022 
01023 Constant *llvm::ConstantFoldGetElementPtr(const Constant *C,
01024                                           const std::vector<Value*> &IdxList) {
01025   if (IdxList.size() == 0 ||
01026       (IdxList.size() == 1 && cast<Constant>(IdxList[0])->isNullValue()))
01027     return const_cast<Constant*>(C);
01028 
01029   if (isa<UndefValue>(C)) {
01030     const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList,
01031                                                        true);
01032     assert(Ty != 0 && "Invalid indices for GEP!");
01033     return UndefValue::get(PointerType::get(Ty));
01034   }
01035 
01036   Constant *Idx0 = cast<Constant>(IdxList[0]);
01037   if (C->isNullValue()) {
01038     bool isNull = true;
01039     for (unsigned i = 0, e = IdxList.size(); i != e; ++i)
01040       if (!cast<Constant>(IdxList[i])->isNullValue()) {
01041         isNull = false;
01042         break;
01043       }
01044     if (isNull) {
01045       const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList,
01046                                                          true);
01047       assert(Ty != 0 && "Invalid indices for GEP!");
01048       return ConstantPointerNull::get(PointerType::get(Ty));
01049     }
01050 
01051     if (IdxList.size() == 1) {
01052       const Type *ElTy = cast<PointerType>(C->getType())->getElementType();
01053       if (unsigned ElSize = ElTy->getPrimitiveSize()) {
01054         // gep null, C is equal to C*sizeof(nullty).  If nullty is a known llvm
01055         // type, we can statically fold this.
01056         Constant *R = ConstantUInt::get(Type::UIntTy, ElSize);
01057         R = ConstantExpr::getCast(R, Idx0->getType());
01058         R = ConstantExpr::getMul(R, Idx0);
01059         return ConstantExpr::getCast(R, C->getType());
01060       }
01061     }
01062   }
01063 
01064   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(const_cast<Constant*>(C))) {
01065     // Combine Indices - If the source pointer to this getelementptr instruction
01066     // is a getelementptr instruction, combine the indices of the two
01067     // getelementptr instructions into a single instruction.
01068     //
01069     if (CE->getOpcode() == Instruction::GetElementPtr) {
01070       const Type *LastTy = 0;
01071       for (gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
01072            I != E; ++I)
01073         LastTy = *I;
01074 
01075       if ((LastTy && isa<ArrayType>(LastTy)) || Idx0->isNullValue()) {
01076         std::vector<Value*> NewIndices;
01077         NewIndices.reserve(IdxList.size() + CE->getNumOperands());
01078         for (unsigned i = 1, e = CE->getNumOperands()-1; i != e; ++i)
01079           NewIndices.push_back(CE->getOperand(i));
01080 
01081         // Add the last index of the source with the first index of the new GEP.
01082         // Make sure to handle the case when they are actually different types.
01083         Constant *Combined = CE->getOperand(CE->getNumOperands()-1);
01084         // Otherwise it must be an array.
01085         if (!Idx0->isNullValue()) {
01086           const Type *IdxTy = Combined->getType();
01087           if (IdxTy != Idx0->getType()) IdxTy = Type::LongTy;
01088           Combined = 
01089             ConstantExpr::get(Instruction::Add,
01090                               ConstantExpr::getCast(Idx0, IdxTy),
01091                               ConstantExpr::getCast(Combined, IdxTy));
01092         }
01093         
01094         NewIndices.push_back(Combined);
01095         NewIndices.insert(NewIndices.end(), IdxList.begin()+1, IdxList.end());
01096         return ConstantExpr::getGetElementPtr(CE->getOperand(0), NewIndices);
01097       }
01098     }
01099 
01100     // Implement folding of:
01101     //    int* getelementptr ([2 x int]* cast ([3 x int]* %X to [2 x int]*),
01102     //                        long 0, long 0)
01103     // To: int* getelementptr ([3 x int]* %X, long 0, long 0)
01104     //
01105     if (CE->getOpcode() == Instruction::Cast && IdxList.size() > 1 &&
01106         Idx0->isNullValue())
01107       if (const PointerType *SPT = 
01108           dyn_cast<PointerType>(CE->getOperand(0)->getType()))
01109         if (const ArrayType *SAT = dyn_cast<ArrayType>(SPT->getElementType()))
01110           if (const ArrayType *CAT =
01111               dyn_cast<ArrayType>(cast<PointerType>(C->getType())->getElementType()))
01112             if (CAT->getElementType() == SAT->getElementType())
01113               return ConstantExpr::getGetElementPtr(
01114                       (Constant*)CE->getOperand(0), IdxList);
01115   }
01116   return 0;
01117 }
01118