LLVM API Documentation

VMCore/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 "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