LLVM API Documentation

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