lib/VMCore/ConstantFold.cpp

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