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 , ConstantSInt, signed char)
 275   DEF_CAST(UByte , ConstantUInt, unsigned char)
 276   DEF_CAST(Short , ConstantSInt, signed short)
 277   DEF_CAST(UShort, ConstantUInt, unsigned short)
 278   DEF_CAST(Int   , ConstantSInt, signed int)
 279   DEF_CAST(UInt  , ConstantUInt, unsigned int)
 280   DEF_CAST(Long  , ConstantSInt, int64_t)
 281   DEF_CAST(ULong , ConstantUInt, 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 ConstantSInt::get(Type::SByteTy, 0);
 307   }
 308   static Constant *CastToUByte (const Constant *V) {
 309     return ConstantUInt::get(Type::UByteTy, 0);
 310   }
 311   static Constant *CastToShort (const Constant *V) {
 312     return ConstantSInt::get(Type::ShortTy, 0);
 313   }
 314   static Constant *CastToUShort(const Constant *V) {
 315     return ConstantUInt::get(Type::UShortTy, 0);
 316   }
 317   static Constant *CastToInt   (const Constant *V) {
 318     return ConstantSInt::get(Type::IntTy, 0);
 319   }
 320   static Constant *CastToUInt  (const Constant *V) {
 321     return ConstantUInt::get(Type::UIntTy, 0);
 322   }
 323   static Constant *CastToLong  (const Constant *V) {
 324     return ConstantSInt::get(Type::LongTy, 0);
 325   }
 326   static Constant *CastToULong (const Constant *V) {
 327     return ConstantUInt::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 //                             DirectRules Class
 432 //===----------------------------------------------------------------------===//
 433 //
 434 // DirectRules provides a concrete base classes of ConstRules for a variety of
 435 // different types.  This allows the C++ compiler to automatically generate our
 436 // constant handling operations in a typesafe and accurate manner.
 437 //
 438 namespace {
 439 template<class ConstantClass, class BuiltinType, Type **Ty, class SuperClass>
 440 struct VISIBILITY_HIDDEN DirectRules
 441   : public TemplateRules<ConstantClass, SuperClass> {
 442   static Constant *Add(const ConstantClass *V1, const ConstantClass *V2) {
 443     BuiltinType R = (BuiltinType)V1->getValue() + (BuiltinType)V2->getValue();
 444     return ConstantClass::get(*Ty, R);
 445   }
 446
 447   static Constant *Sub(const ConstantClass *V1, const ConstantClass *V2) {
 448     BuiltinType R = (BuiltinType)V1->getValue() - (BuiltinType)V2->getValue();
 449     return ConstantClass::get(*Ty, R);
 450   }
 451
 452   static Constant *Mul(const ConstantClass *V1, const ConstantClass *V2) {
 453     BuiltinType R = (BuiltinType)V1->getValue() * (BuiltinType)V2->getValue();
 454     return ConstantClass::get(*Ty, R);
 455   }
 456
 457   static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) {
 458     if (V2->isNullValue()) return 0;
 459     BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue();
 460     return ConstantClass::get(*Ty, R);
 461   }
 462
 463   static Constant *LessThan(const ConstantClass *V1, const ConstantClass *V2) {
 464     bool R = (BuiltinType)V1->getValue() < (BuiltinType)V2->getValue();
 465     return ConstantBool::get(R);
 466   }
 467
 468   static Constant *EqualTo(const ConstantClass *V1, const ConstantClass *V2) {
 469     bool R = (BuiltinType)V1->getValue() == (BuiltinType)V2->getValue();
 470     return ConstantBool::get(R);
 471   }
 472
 473   static Constant *CastToPointer(const ConstantClass *V,
 474                                  const PointerType *PTy) {
 475     if (V->isNullValue())    // Is it a FP or Integral null value?
 476       return ConstantPointerNull::get(PTy);
 477     return 0;  // Can't const prop other types of pointers
 478   }
 479
 480   // Casting operators.  ick
 481 #define DEF_CAST(TYPE, CLASS, CTYPE) \
 482   static Constant *CastTo##TYPE  (const ConstantClass *V) {    \
 483     return CLASS::get(Type::TYPE##Ty, (CTYPE)(BuiltinType)V->getValue()); \
 484   }
 485
 486   DEF_CAST(Bool  , ConstantBool, bool)
 487   DEF_CAST(SByte , ConstantSInt, signed char)
 488   DEF_CAST(UByte , ConstantUInt, unsigned char)
 489   DEF_CAST(Short , ConstantSInt, signed short)
 490   DEF_CAST(UShort, ConstantUInt, unsigned short)
 491   DEF_CAST(Int   , ConstantSInt, signed int)
 492   DEF_CAST(UInt  , ConstantUInt, unsigned int)
 493   DEF_CAST(Long  , ConstantSInt, int64_t)
 494   DEF_CAST(ULong , ConstantUInt, uint64_t)
 495   DEF_CAST(Float , ConstantFP  , float)
 496   DEF_CAST(Double, ConstantFP  , double)
 497 #undef DEF_CAST
 498 };
 499 }  // end anonymous namespace
 500
 501
 502 //===----------------------------------------------------------------------===//
 503 //                           DirectIntRules Class
 504 //===----------------------------------------------------------------------===//
 505 //
 506 // DirectIntRules provides implementations of functions that are valid on
 507 // integer types, but not all types in general.
 508 //
 509 namespace {
 510 template <class ConstantClass, class BuiltinType, Type **Ty>
 511 struct VISIBILITY_HIDDEN DirectIntRules
 512   : public DirectRules<ConstantClass, BuiltinType, Ty,
 513                        DirectIntRules<ConstantClass, BuiltinType, Ty> > {
 514
 515   static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) {
 516     if (V2->isNullValue()) return 0;
 517     if (V2->isAllOnesValue() &&              // MIN_INT / -1
 518         (BuiltinType)V1->getValue() == -(BuiltinType)V1->getValue())
 519       return 0;
 520     BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue();
 521     return ConstantClass::get(*Ty, R);
 522   }
 523
 524   static Constant *Rem(const ConstantClass *V1,
 525                        const ConstantClass *V2) {
 526     if (V2->isNullValue()) return 0;         // X / 0
 527     if (V2->isAllOnesValue() &&              // MIN_INT / -1
 528         (BuiltinType)V1->getValue() == -(BuiltinType)V1->getValue())
 529       return 0;
 530     BuiltinType R = (BuiltinType)V1->getValue() % (BuiltinType)V2->getValue();
 531     return ConstantClass::get(*Ty, R);
 532   }
 533
 534   static Constant *And(const ConstantClass *V1, const ConstantClass *V2) {
 535     BuiltinType R = (BuiltinType)V1->getValue() & (BuiltinType)V2->getValue();
 536     return ConstantClass::get(*Ty, R);
 537   }
 538   static Constant *Or(const ConstantClass *V1, const ConstantClass *V2) {
 539     BuiltinType R = (BuiltinType)V1->getValue() | (BuiltinType)V2->getValue();
 540     return ConstantClass::get(*Ty, R);
 541   }
 542   static Constant *Xor(const ConstantClass *V1, const ConstantClass *V2) {
 543     BuiltinType R = (BuiltinType)V1->getValue() ^ (BuiltinType)V2->getValue();
 544     return ConstantClass::get(*Ty, R);
 545   }
 546
 547   static Constant *Shl(const ConstantClass *V1, const ConstantClass *V2) {
 548     BuiltinType R = (BuiltinType)V1->getValue() << (BuiltinType)V2->getValue();
 549     return ConstantClass::get(*Ty, R);
 550   }
 551
 552   static Constant *Shr(const ConstantClass *V1, const ConstantClass *V2) {
 553     BuiltinType R = (BuiltinType)V1->getValue() >> (BuiltinType)V2->getValue();
 554     return ConstantClass::get(*Ty, R);
 555   }
 556 };
 557 }  // end anonymous namespace
 558
 559
 560 //===----------------------------------------------------------------------===//
 561 //                           DirectFPRules Class
 562 //===----------------------------------------------------------------------===//
 563 //
 564 /// DirectFPRules provides implementations of functions that are valid on
 565 /// floating point types, but not all types in general.
 566 ///
 567 namespace {
 568 template <class ConstantClass, class BuiltinType, Type **Ty>
 569 struct VISIBILITY_HIDDEN DirectFPRules
 570   : public DirectRules<ConstantClass, BuiltinType, Ty,
 571                        DirectFPRules<ConstantClass, BuiltinType, Ty> > {
 572   static Constant *Rem(const ConstantClass *V1, const ConstantClass *V2) {
 573     if (V2->isNullValue()) return 0;
 574     BuiltinType Result = std::fmod((BuiltinType)V1->getValue(),
 575                                    (BuiltinType)V2->getValue());
 576     return ConstantClass::get(*Ty, Result);
 577   }
 578   static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) {
 579     BuiltinType inf = std::numeric_limits<BuiltinType>::infinity();
 580     if (V2->isExactlyValue(0.0)) return ConstantClass::get(*Ty, inf);
 581     if (V2->isExactlyValue(-0.0)) return ConstantClass::get(*Ty, -inf);
 582     BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue();
 583     return ConstantClass::get(*Ty, R);
 584   }
 585 };
 586 }  // end anonymous namespace
 587
 588 static ManagedStatic<EmptyRules>       EmptyR;
 589 static ManagedStatic<BoolRules>        BoolR;
 590 static ManagedStatic<NullPointerRules> NullPointerR;
 591 static ManagedStatic<ConstantPackedRules> ConstantPackedR;
 592 static ManagedStatic<GeneralPackedRules> GeneralPackedR;
 593 static ManagedStatic<DirectIntRules<ConstantSInt,   signed char ,
 594                                     &Type::SByteTy> > SByteR;
 595 static ManagedStatic<DirectIntRules<ConstantUInt, unsigned char ,
 596                                     &Type::UByteTy> > UByteR;
 597 static ManagedStatic<DirectIntRules<ConstantSInt,   signed short,
 598                                     &Type::ShortTy> > ShortR;
 599 static ManagedStatic<DirectIntRules<ConstantUInt, unsigned short,
 600                                     &Type::UShortTy> > UShortR;
 601 static ManagedStatic<DirectIntRules<ConstantSInt,   signed int  ,
 602                                     &Type::IntTy> >   IntR;
 603 static ManagedStatic<DirectIntRules<ConstantUInt, unsigned int  ,
 604                                     &Type::UIntTy> >  UIntR;
 605 static ManagedStatic<DirectIntRules<ConstantSInt,  int64_t      ,
 606                                     &Type::LongTy> >  LongR;
 607 static ManagedStatic<DirectIntRules<ConstantUInt, uint64_t      ,
 608                                     &Type::ULongTy> > ULongR;
 609 static ManagedStatic<DirectFPRules <ConstantFP  , float         ,
 610                                     &Type::FloatTy> > FloatR;
 611 static ManagedStatic<DirectFPRules <ConstantFP  , double        ,
 612                                     &Type::DoubleTy> > DoubleR;
 613
 614 /// ConstRules::get - This method returns the constant rules implementation that
 615 /// implements the semantics of the two specified constants.
 616 ConstRules &ConstRules::get(const Constant *V1, const Constant *V2) {
 617   if (isa<ConstantExpr>(V1) || isa<ConstantExpr>(V2) ||
 618       isa<GlobalValue>(V1) || isa<GlobalValue>(V2) ||
 619       isa<UndefValue>(V1) || isa<UndefValue>(V2))
 620     return *EmptyR;
 621
 622   switch (V1->getType()->getTypeID()) {
 623   default: assert(0 && "Unknown value type for constant folding!");
 624   case Type::BoolTyID:    return *BoolR;
 625   case Type::PointerTyID: return *NullPointerR;
 626   case Type::SByteTyID:   return *SByteR;
 627   case Type::UByteTyID:   return *UByteR;
 628   case Type::ShortTyID:   return *ShortR;
 629   case Type::UShortTyID:  return *UShortR;
 630   case Type::IntTyID:     return *IntR;
 631   case Type::UIntTyID:    return *UIntR;
 632   case Type::LongTyID:    return *LongR;
 633   case Type::ULongTyID:   return *ULongR;
 634   case Type::FloatTyID:   return *FloatR;
 635   case Type::DoubleTyID:  return *DoubleR;
 636   case Type::PackedTyID:
 637     if (isa<ConstantPacked>(V1) && isa<ConstantPacked>(V2))
 638       return *ConstantPackedR;
 639     return *GeneralPackedR; // Constant folding rules for ConstantAggregateZero.
 640   }
 641 }
 642
 643
 644 //===----------------------------------------------------------------------===//
 645 //                ConstantFold*Instruction Implementations
 646 //===----------------------------------------------------------------------===//
 647 //
 648 // These methods contain the special case hackery required to symbolically
 649 // evaluate some constant expression cases, and use the ConstantRules class to
 650 // evaluate normal constants.
 651 //
 652 static unsigned getSize(const Type *Ty) {
 653   unsigned S = Ty->getPrimitiveSize();
 654   return S ? S : 8;  // Treat pointers at 8 bytes
 655 }
 656
 657 /// CastConstantPacked - Convert the specified ConstantPacked node to the
 658 /// specified packed type.  At this point, we know that the elements of the
 659 /// input packed constant are all simple integer or FP values.
 660 static Constant *CastConstantPacked(ConstantPacked *CP,
 661                                     const PackedType *DstTy) {
 662   unsigned SrcNumElts = CP->getType()->getNumElements();
 663   unsigned DstNumElts = DstTy->getNumElements();
 664   const Type *SrcEltTy = CP->getType()->getElementType();
 665   const Type *DstEltTy = DstTy->getElementType();
 666
 667   // If both vectors have the same number of elements (thus, the elements
 668   // are the same size), perform the conversion now.
 669   if (SrcNumElts == DstNumElts) {
 670     std::vector<Constant*> Result;
 671
 672     // If the src and dest elements are both integers, just cast each one
 673     // which will do the appropriate bit-convert.
 674     if (SrcEltTy->isIntegral() && DstEltTy->isIntegral()) {
 675       for (unsigned i = 0; i != SrcNumElts; ++i)
 676         Result.push_back(ConstantExpr::getCast(CP->getOperand(i),
 677                                                DstEltTy));
 678       return ConstantPacked::get(Result);
 679     }
 680
 681     if (SrcEltTy->isIntegral()) {
 682       // Otherwise, this is an int-to-fp cast.
 683       assert(DstEltTy->isFloatingPoint());
 684       if (DstEltTy->getTypeID() == Type::DoubleTyID) {
 685         for (unsigned i = 0; i != SrcNumElts; ++i) {
 686           double V =
 687             BitsToDouble(cast<ConstantInt>(CP->getOperand(i))->getRawValue());
 688           Result.push_back(ConstantFP::get(Type::DoubleTy, V));
 689         }
 690         return ConstantPacked::get(Result);
 691       }
 692       assert(DstEltTy == Type::FloatTy && "Unknown fp type!");
 693       for (unsigned i = 0; i != SrcNumElts; ++i) {
 694         float V =
 695         BitsToFloat(cast<ConstantInt>(CP->getOperand(i))->getRawValue());
 696         Result.push_back(ConstantFP::get(Type::FloatTy, V));
 697       }
 698       return ConstantPacked::get(Result);
 699     }
 700
 701     // Otherwise, this is an fp-to-int cast.
 702     assert(SrcEltTy->isFloatingPoint() && DstEltTy->isIntegral());
 703
 704     if (SrcEltTy->getTypeID() == Type::DoubleTyID) {
 705       for (unsigned i = 0; i != SrcNumElts; ++i) {
 706         uint64_t V =
 707           DoubleToBits(cast<ConstantFP>(CP->getOperand(i))->getValue());
 708         Constant *C = ConstantUInt::get(Type::ULongTy, V);
 709         Result.push_back(ConstantExpr::getCast(C, DstEltTy));
 710       }
 711       return ConstantPacked::get(Result);
 712     }
 713
 714     assert(SrcEltTy->getTypeID() == Type::FloatTyID);
 715     for (unsigned i = 0; i != SrcNumElts; ++i) {
 716       unsigned V = FloatToBits(cast<ConstantFP>(CP->getOperand(i))->getValue());
 717       Constant *C = ConstantUInt::get(Type::UIntTy, V);
 718       Result.push_back(ConstantExpr::getCast(C, DstEltTy));
 719     }
 720     return ConstantPacked::get(Result);
 721   }
 722
 723   // Otherwise, this is a cast that changes element count and size.  Handle
 724   // casts which shrink the elements here.
 725
 726   // FIXME: We need to know endianness to do this!
 727
 728   return 0;
 729 }
 730
 731
 732 Constant *llvm::ConstantFoldCastInstruction(const Constant *V,
 733                                             const Type *DestTy) {
 734   if (V->getType() == DestTy) return (Constant*)V;
 735
 736   // Cast of a global address to boolean is always true.
 737   if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
 738     if (DestTy == Type::BoolTy)
 739       // FIXME: When we support 'external weak' references, we have to prevent
 740       // this transformation from happening.  This code will need to be updated
 741       // to ignore external weak symbols when we support it.
 742       return ConstantBool::getTrue();
 743   } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
 744     if (CE->getOpcode() == Instruction::Cast) {
 745       Constant *Op = const_cast<Constant*>(CE->getOperand(0));
 746       // Try to not produce a cast of a cast, which is almost always redundant.
 747       if (!Op->getType()->isFloatingPoint() &&
 748           !CE->getType()->isFloatingPoint() &&
 749           !DestTy->isFloatingPoint()) {
 750         unsigned S1 = getSize(Op->getType()), S2 = getSize(CE->getType());
 751         unsigned S3 = getSize(DestTy);
 752         if (Op->getType() == DestTy && S3 >= S2)
 753           return Op;
 754         if (S1 >= S2 && S2 >= S3)
 755           return ConstantExpr::getCast(Op, DestTy);
 756         if (S1 <= S2 && S2 >= S3 && S1 <= S3)
 757           return ConstantExpr::getCast(Op, DestTy);
 758       }
 759     } else if (CE->getOpcode() == Instruction::GetElementPtr) {
 760       // If all of the indexes in the GEP are null values, there is no pointer
 761       // adjustment going on.  We might as well cast the source pointer.
 762       bool isAllNull = true;
 763       for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
 764         if (!CE->getOperand(i)->isNullValue()) {
 765           isAllNull = false;
 766           break;
 767         }
 768       if (isAllNull)
 769         return ConstantExpr::getCast(CE->getOperand(0), DestTy);
 770     }
 771   } else if (isa<UndefValue>(V)) {
 772     return UndefValue::get(DestTy);
 773   }
 774
 775   // Check to see if we are casting an pointer to an aggregate to a pointer to
 776   // the first element.  If so, return the appropriate GEP instruction.
 777   if (const PointerType *PTy = dyn_cast<PointerType>(V->getType()))
 778     if (const PointerType *DPTy = dyn_cast<PointerType>(DestTy)) {
 779       std::vector<Value*> IdxList;
 780       IdxList.push_back(Constant::getNullValue(Type::IntTy));
 781       const Type *ElTy = PTy->getElementType();
 782       while (ElTy != DPTy->getElementType()) {
 783         if (const StructType *STy = dyn_cast<StructType>(ElTy)) {
 784           if (STy->getNumElements() == 0) break;
 785           ElTy = STy->getElementType(0);
 786           IdxList.push_back(Constant::getNullValue(Type::UIntTy));
 787         } else if (const SequentialType *STy = dyn_cast<SequentialType>(ElTy)) {
 788           if (isa<PointerType>(ElTy)) break;  // Can't index into pointers!
 789           ElTy = STy->getElementType();
 790           IdxList.push_back(IdxList[0]);
 791         } else {
 792           break;
 793         }
 794       }
 795
 796       if (ElTy == DPTy->getElementType())
 797         return ConstantExpr::getGetElementPtr(const_cast<Constant*>(V),IdxList);
 798     }
 799
 800   // Handle casts from one packed constant to another.  We know that the src and
 801   // dest type have the same size.
 802   if (const PackedType *DestPTy = dyn_cast<PackedType>(DestTy)) {
 803     if (const PackedType *SrcTy = dyn_cast<PackedType>(V->getType())) {
 804       assert(DestPTy->getElementType()->getPrimitiveSizeInBits() *
 805                  DestPTy->getNumElements()  ==
 806              SrcTy->getElementType()->getPrimitiveSizeInBits() *
 807              SrcTy->getNumElements() && "Not cast between same sized vectors!");
 808       if (isa<ConstantAggregateZero>(V))
 809         return Constant::getNullValue(DestTy);
 810       if (isa<UndefValue>(V))
 811         return UndefValue::get(DestTy);
 812       if (const ConstantPacked *CP = dyn_cast<ConstantPacked>(V)) {
 813         // This is a cast from a ConstantPacked of one type to a ConstantPacked
 814         // of another type.  Check to see if all elements of the input are
 815         // simple.
 816         bool AllSimpleConstants = true;
 817         for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) {
 818           if (!isa<ConstantInt>(CP->getOperand(i)) &&
 819               !isa<ConstantFP>(CP->getOperand(i))) {
 820             AllSimpleConstants = false;
 821             break;
 822           }
 823         }
 824
 825         // If all of the elements are simple constants, we can fold this.
 826         if (AllSimpleConstants)
 827           return CastConstantPacked(const_cast<ConstantPacked*>(CP), DestPTy);
 828       }
 829     }
 830   }
 831
 832   ConstRules &Rules = ConstRules::get(V, V);
 833
 834   switch (DestTy->getTypeID()) {
 835   case Type::BoolTyID:    return Rules.castToBool(V);
 836   case Type::UByteTyID:   return Rules.castToUByte(V);
 837   case Type::SByteTyID:   return Rules.castToSByte(V);
 838   case Type::UShortTyID:  return Rules.castToUShort(V);
 839   case Type::ShortTyID:   return Rules.castToShort(V);
 840   case Type::UIntTyID:    return Rules.castToUInt(V);
 841   case Type::IntTyID:     return Rules.castToInt(V);
 842   case Type::ULongTyID:   return Rules.castToULong(V);
 843   case Type::LongTyID:    return Rules.castToLong(V);
 844   case Type::FloatTyID:   return Rules.castToFloat(V);
 845   case Type::DoubleTyID:  return Rules.castToDouble(V);
 846   case Type::PointerTyID:
 847     return Rules.castToPointer(V, cast<PointerType>(DestTy));
 848   default: return 0;
 849   }
 850 }
 851
 852 Constant *llvm::ConstantFoldSelectInstruction(const Constant *Cond,
 853                                               const Constant *V1,
 854                                               const Constant *V2) {
 855   if (const ConstantBool *CB = dyn_cast<ConstantBool>(Cond))
 856     return const_cast<Constant*>(CB->getValue() ? V1 : V2);
 857
 858   if (isa<UndefValue>(V1)) return const_cast<Constant*>(V2);
 859   if (isa<UndefValue>(V2)) return const_cast<Constant*>(V1);
 860   if (isa<UndefValue>(Cond)) return const_cast<Constant*>(V1);
 861   if (V1 == V2) return const_cast<Constant*>(V1);
 862   return 0;
 863 }
 864
 865 Constant *llvm::ConstantFoldExtractElementInstruction(const Constant *Val,
 866                                                       const Constant *Idx) {
 867   if (isa<UndefValue>(Val))  // ee(undef, x) -> undef
 868     return UndefValue::get(cast<PackedType>(Val->getType())->getElementType());
 869   if (Val->isNullValue())  // ee(zero, x) -> zero
 870     return Constant::getNullValue(
 871                           cast<PackedType>(Val->getType())->getElementType());
 872
 873   if (const ConstantPacked *CVal = dyn_cast<ConstantPacked>(Val)) {
 874     if (const ConstantUInt *CIdx = dyn_cast<ConstantUInt>(Idx)) {
 875       return const_cast<Constant*>(CVal->getOperand(CIdx->getValue()));
 876     } else if (isa<UndefValue>(Idx)) {
 877       // ee({w,x,y,z}, undef) -> w (an arbitrary value).
 878       return const_cast<Constant*>(CVal->getOperand(0));
 879     }
 880   }
 881   return 0;
 882 }
 883
 884 Constant *llvm::ConstantFoldInsertElementInstruction(const Constant *Val,
 885                                                      const Constant *Elt,
 886                                                      const Constant *Idx) {
 887   const ConstantUInt *CIdx = dyn_cast<ConstantUInt>(Idx);
 888   if (!CIdx) return 0;
 889   unsigned idxVal = CIdx->getValue();
 890   if (const UndefValue *UVal = dyn_cast<UndefValue>(Val)) {
 891     // Insertion of scalar constant into packed undef
 892     // Optimize away insertion of undef
 893     if (isa<UndefValue>(Elt))
 894       return const_cast<Constant*>(Val);
 895     // Otherwise break the aggregate undef into multiple undefs and do
 896     // the insertion
 897     unsigned numOps =
 898       cast<PackedType>(Val->getType())->getNumElements();
 899     std::vector<Constant*> Ops;
 900     Ops.reserve(numOps);
 901     for (unsigned i = 0; i < numOps; ++i) {
 902       const Constant *Op =
 903         (i == idxVal) ? Elt : UndefValue::get(Elt->getType());
 904       Ops.push_back(const_cast<Constant*>(Op));
 905     }
 906     return ConstantPacked::get(Ops);
 907   }
 908   if (const ConstantAggregateZero *CVal =
 909       dyn_cast<ConstantAggregateZero>(Val)) {
 910     // Insertion of scalar constant into packed aggregate zero
 911     // Optimize away insertion of zero
 912     if (Elt->isNullValue())
 913       return const_cast<Constant*>(Val);
 914     // Otherwise break the aggregate zero into multiple zeros and do
 915     // the insertion
 916     unsigned numOps =
 917       cast<PackedType>(Val->getType())->getNumElements();
 918     std::vector<Constant*> Ops;
 919     Ops.reserve(numOps);
 920     for (unsigned i = 0; i < numOps; ++i) {
 921       const Constant *Op =
 922         (i == idxVal) ? Elt : Constant::getNullValue(Elt->getType());
 923       Ops.push_back(const_cast<Constant*>(Op));
 924     }
 925     return ConstantPacked::get(Ops);
 926   }
 927   if (const ConstantPacked *CVal = dyn_cast<ConstantPacked>(Val)) {
 928     // Insertion of scalar constant into packed constant
 929     std::vector<Constant*> Ops;
 930     Ops.reserve(CVal->getNumOperands());
 931     for (unsigned i = 0; i < CVal->getNumOperands(); ++i) {
 932       const Constant *Op =
 933         (i == idxVal) ? Elt : cast<Constant>(CVal->getOperand(i));
 934       Ops.push_back(const_cast<Constant*>(Op));
 935     }
 936     return ConstantPacked::get(Ops);
 937   }
 938   return 0;
 939 }
 940
 941 Constant *llvm::ConstantFoldShuffleVectorInstruction(const Constant *V1,
 942                                                      const Constant *V2,
 943                                                      const Constant *Mask) {
 944   // TODO:
 945   return 0;
 946 }
 947
 948
 949 /// isZeroSizedType - This type is zero sized if its an array or structure of
 950 /// zero sized types.  The only leaf zero sized type is an empty structure.
 951 static bool isMaybeZeroSizedType(const Type *Ty) {
 952   if (isa<OpaqueType>(Ty)) return true;  // Can't say.
 953   if (const StructType *STy = dyn_cast<StructType>(Ty)) {
 954
 955     // If all of elements have zero size, this does too.
 956     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
 957       if (!isMaybeZeroSizedType(STy->getElementType(i))) return false;
 958     return true;
 959
 960   } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
 961     return isMaybeZeroSizedType(ATy->getElementType());
 962   }
 963   return false;
 964 }
 965
 966 /// IdxCompare - Compare the two constants as though they were getelementptr
 967 /// indices.  This allows coersion of the types to be the same thing.
 968 ///
 969 /// If the two constants are the "same" (after coersion), return 0.  If the
 970 /// first is less than the second, return -1, if the second is less than the
 971 /// first, return 1.  If the constants are not integral, return -2.
 972 ///
 973 static int IdxCompare(Constant *C1, Constant *C2, const Type *ElTy) {
 974   if (C1 == C2) return 0;
 975
 976   // Ok, we found a different index.  Are either of the operands
 977   // ConstantExprs?  If so, we can't do anything with them.
 978   if (!isa<ConstantInt>(C1) || !isa<ConstantInt>(C2))
 979     return -2; // don't know!
 980
 981   // Ok, we have two differing integer indices.  Sign extend them to be the same
 982   // type.  Long is always big enough, so we use it.
 983   C1 = ConstantExpr::getSignExtend(C1, Type::LongTy);
 984   C2 = ConstantExpr::getSignExtend(C2, Type::LongTy);
 985   if (C1 == C2) return 0;  // Are they just differing types?
 986
 987   // If the type being indexed over is really just a zero sized type, there is
 988   // no pointer difference being made here.
 989   if (isMaybeZeroSizedType(ElTy))
 990     return -2; // dunno.
 991
 992   // If they are really different, now that they are the same type, then we
 993   // found a difference!
 994   if (cast<ConstantSInt>(C1)->getValue() < cast<ConstantSInt>(C2)->getValue())
 995     return -1;
 996   else
 997     return 1;
 998 }
 999
1000 /// evaluateRelation - This function determines if there is anything we can
1001 /// decide about the two constants provided.  This doesn't need to handle simple
1002 /// things like integer comparisons, but should instead handle ConstantExprs
1003 /// and GlobalValuess.  If we can determine that the two constants have a
1004 /// particular relation to each other, we should return the corresponding SetCC
1005 /// code, otherwise return Instruction::BinaryOpsEnd.
1006 ///
1007 /// To simplify this code we canonicalize the relation so that the first
1008 /// operand is always the most "complex" of the two.  We consider simple
1009 /// constants (like ConstantInt) to be the simplest, followed by
1010 /// GlobalValues, followed by ConstantExpr's (the most complex).
1011 ///
1012 static Instruction::BinaryOps evaluateRelation(Constant *V1, Constant *V2) {
1013   assert(V1->getType() == V2->getType() &&
1014          "Cannot compare different types of values!");
1015   if (V1 == V2) return Instruction::SetEQ;
1016
1017   if (!isa<ConstantExpr>(V1) && !isa<GlobalValue>(V1)) {
1018     if (!isa<GlobalValue>(V2) && !isa<ConstantExpr>(V2)) {
1019       // We distilled this down to a simple case, use the standard constant
1020       // folder.
1021       ConstantBool *R = dyn_cast<ConstantBool>(ConstantExpr::getSetEQ(V1, V2));
1022       if (R && R->getValue()) return Instruction::SetEQ;
1023       R = dyn_cast<ConstantBool>(ConstantExpr::getSetLT(V1, V2));
1024       if (R && R->getValue()) return Instruction::SetLT;
1025       R = dyn_cast<ConstantBool>(ConstantExpr::getSetGT(V1, V2));
1026       if (R && R->getValue()) return Instruction::SetGT;
1027
1028       // If we couldn't figure it out, bail.
1029       return Instruction::BinaryOpsEnd;
1030     }
1031
1032     // If the first operand is simple, swap operands.
1033     Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1);
1034     if (SwappedRelation != Instruction::BinaryOpsEnd)
1035       return SetCondInst::getSwappedCondition(SwappedRelation);
1036
1037   } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(V1)) {
1038     if (isa<ConstantExpr>(V2)) {  // Swap as necessary.
1039       Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1);
1040       if (SwappedRelation != Instruction::BinaryOpsEnd)
1041         return SetCondInst::getSwappedCondition(SwappedRelation);
1042       else
1043         return Instruction::BinaryOpsEnd;
1044     }
1045
1046     // Now we know that the RHS is a GlobalValue or simple constant,
1047     // which (since the types must match) means that it's a ConstantPointerNull.
1048     if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) {
1049       assert(CPR1 != CPR2 &&
1050              "GVs for the same value exist at different addresses??");
1051       // FIXME: If both globals are external weak, they might both be null!
1052       return Instruction::SetNE;
1053     } else {
1054       assert(isa<ConstantPointerNull>(V2) && "Canonicalization guarantee!");
1055       // Global can never be null.  FIXME: if we implement external weak
1056       // linkage, this is not necessarily true!
1057       return Instruction::SetNE;
1058     }
1059
1060   } else {
1061     // Ok, the LHS is known to be a constantexpr.  The RHS can be any of a
1062     // constantexpr, a CPR, or a simple constant.
1063     ConstantExpr *CE1 = cast<ConstantExpr>(V1);
1064     Constant *CE1Op0 = CE1->getOperand(0);
1065
1066     switch (CE1->getOpcode()) {
1067     case Instruction::Cast:
1068       // If the cast is not actually changing bits, and the second operand is a
1069       // null pointer, do the comparison with the pre-casted value.
1070       if (V2->isNullValue() &&
1071           (isa<PointerType>(CE1->getType()) || CE1->getType()->isIntegral()))
1072         return evaluateRelation(CE1Op0,
1073                                 Constant::getNullValue(CE1Op0->getType()));
1074
1075       // If the dest type is a pointer type, and the RHS is a constantexpr cast
1076       // from the same type as the src of the LHS, evaluate the inputs.  This is
1077       // important for things like "seteq (cast 4 to int*), (cast 5 to int*)",
1078       // which happens a lot in compilers with tagged integers.
1079       if (ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2))
1080         if (isa<PointerType>(CE1->getType()) &&
1081             CE2->getOpcode() == Instruction::Cast &&
1082             CE1->getOperand(0)->getType() == CE2->getOperand(0)->getType() &&
1083             CE1->getOperand(0)->getType()->isIntegral()) {
1084           return evaluateRelation(CE1->getOperand(0), CE2->getOperand(0));
1085         }
1086       break;
1087
1088     case Instruction::GetElementPtr:
1089       // Ok, since this is a getelementptr, we know that the constant has a
1090       // pointer type.  Check the various cases.
1091       if (isa<ConstantPointerNull>(V2)) {
1092         // If we are comparing a GEP to a null pointer, check to see if the base
1093         // of the GEP equals the null pointer.
1094         if (isa<GlobalValue>(CE1Op0)) {
1095           // FIXME: this is not true when we have external weak references!
1096           // No offset can go from a global to a null pointer.
1097           return Instruction::SetGT;
1098         } else if (isa<ConstantPointerNull>(CE1Op0)) {
1099           // If we are indexing from a null pointer, check to see if we have any
1100           // non-zero indices.
1101           for (unsigned i = 1, e = CE1->getNumOperands(); i != e; ++i)
1102             if (!CE1->getOperand(i)->isNullValue())
1103               // Offsetting from null, must not be equal.
1104               return Instruction::SetGT;
1105           // Only zero indexes from null, must still be zero.
1106           return Instruction::SetEQ;
1107         }
1108         // Otherwise, we can't really say if the first operand is null or not.
1109       } else if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) {
1110         if (isa<ConstantPointerNull>(CE1Op0)) {
1111           // FIXME: This is not true with external weak references.
1112           return Instruction::SetLT;
1113         } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(CE1Op0)) {
1114           if (CPR1 == CPR2) {
1115             // If this is a getelementptr of the same global, then it must be
1116             // different.  Because the types must match, the getelementptr could
1117             // only have at most one index, and because we fold getelementptr's
1118             // with a single zero index, it must be nonzero.
1119             assert(CE1->getNumOperands() == 2 &&
1120                    !CE1->getOperand(1)->isNullValue() &&
1121                    "Suprising getelementptr!");
1122             return Instruction::SetGT;
1123           } else {
1124             // If they are different globals, we don't know what the value is,
1125             // but they can't be equal.
1126             return Instruction::SetNE;
1127           }
1128         }
1129       } else {
1130         const ConstantExpr *CE2 = cast<ConstantExpr>(V2);
1131         const Constant *CE2Op0 = CE2->getOperand(0);
1132
1133         // There are MANY other foldings that we could perform here.  They will
1134         // probably be added on demand, as they seem needed.
1135         switch (CE2->getOpcode()) {
1136         default: break;
1137         case Instruction::GetElementPtr:
1138           // By far the most common case to handle is when the base pointers are
1139           // obviously to the same or different globals.
1140           if (isa<GlobalValue>(CE1Op0) && isa<GlobalValue>(CE2Op0)) {
1141             if (CE1Op0 != CE2Op0) // Don't know relative ordering, but not equal
1142               return Instruction::SetNE;
1143             // Ok, we know that both getelementptr instructions are based on the
1144             // same global.  From this, we can precisely determine the relative
1145             // ordering of the resultant pointers.
1146             unsigned i = 1;
1147
1148             // Compare all of the operands the GEP's have in common.
1149             gep_type_iterator GTI = gep_type_begin(CE1);
1150             for (;i != CE1->getNumOperands() && i != CE2->getNumOperands();
1151                  ++i, ++GTI)
1152               switch (IdxCompare(CE1->getOperand(i), CE2->getOperand(i),
1153                                  GTI.getIndexedType())) {
1154               case -1: return Instruction::SetLT;
1155               case 1:  return Instruction::SetGT;
1156               case -2: return Instruction::BinaryOpsEnd;
1157               }
1158
1159             // Ok, we ran out of things they have in common.  If any leftovers
1160             // are non-zero then we have a difference, otherwise we are equal.
1161             for (; i < CE1->getNumOperands(); ++i)
1162               if (!CE1->getOperand(i)->isNullValue())
1163                 if (isa<ConstantIntegral>(CE1->getOperand(i)))
1164                   return Instruction::SetGT;
1165                 else
1166                   return Instruction::BinaryOpsEnd; // Might be equal.
1167
1168             for (; i < CE2->getNumOperands(); ++i)
1169               if (!CE2->getOperand(i)->isNullValue())
1170                 if (isa<ConstantIntegral>(CE2->getOperand(i)))
1171                   return Instruction::SetLT;
1172                 else
1173                   return Instruction::BinaryOpsEnd; // Might be equal.
1174             return Instruction::SetEQ;
1175           }
1176         }
1177       }
1178
1179     default:
1180       break;
1181     }
1182   }
1183
1184   return Instruction::BinaryOpsEnd;
1185 }
1186
1187 Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode,
1188                                               const Constant *V1,
1189                                               const Constant *V2) {
1190   Constant *C = 0;
1191   switch (Opcode) {
1192   default:                   break;
1193   case Instruction::Add:     C = ConstRules::get(V1, V2).add(V1, V2); break;
1194   case Instruction::Sub:     C = ConstRules::get(V1, V2).sub(V1, V2); break;
1195   case Instruction::Mul:     C = ConstRules::get(V1, V2).mul(V1, V2); break;
1196   case Instruction::Div:     C = ConstRules::get(V1, V2).div(V1, V2); break;
1197   case Instruction::Rem:     C = ConstRules::get(V1, V2).rem(V1, V2); break;
1198   case Instruction::And:     C = ConstRules::get(V1, V2).op_and(V1, V2); break;
1199   case Instruction::Or:      C = ConstRules::get(V1, V2).op_or (V1, V2); break;
1200   case Instruction::Xor:     C = ConstRules::get(V1, V2).op_xor(V1, V2); break;
1201   case Instruction::Shl:     C = ConstRules::get(V1, V2).shl(V1, V2); break;
1202   case Instruction::Shr:     C = ConstRules::get(V1, V2).shr(V1, V2); break;
1203   case Instruction::SetEQ:   C = ConstRules::get(V1, V2).equalto(V1, V2); break;
1204   case Instruction::SetLT:   C = ConstRules::get(V1, V2).lessthan(V1, V2);break;
1205   case Instruction::SetGT:   C = ConstRules::get(V1, V2).lessthan(V2, V1);break;
1206   case Instruction::SetNE:   // V1 != V2  ===  !(V1 == V2)
1207     C = ConstRules::get(V1, V2).equalto(V1, V2);
1208     if (C) return ConstantExpr::getNot(C);
1209     break;
1210   case Instruction::SetLE:   // V1 <= V2  ===  !(V2 < V1)
1211     C = ConstRules::get(V1, V2).lessthan(V2, V1);
1212     if (C) return ConstantExpr::getNot(C);
1213     break;
1214   case Instruction::SetGE:   // V1 >= V2  ===  !(V1 < V2)
1215     C = ConstRules::get(V1, V2).lessthan(V1, V2);
1216     if (C) return ConstantExpr::getNot(C);
1217     break;
1218   }
1219
1220   // If we successfully folded the expression, return it now.
1221   if (C) return C;
1222
1223   if (SetCondInst::isComparison(Opcode)) {
1224     if (isa<UndefValue>(V1) || isa<UndefValue>(V2))
1225       return UndefValue::get(Type::BoolTy);
1226     switch (evaluateRelation(const_cast<Constant*>(V1),
1227                              const_cast<Constant*>(V2))) {
1228     default: assert(0 && "Unknown relational!");
1229     case Instruction::BinaryOpsEnd:
1230       break;  // Couldn't determine anything about these constants.
1231     case Instruction::SetEQ:   // We know the constants are equal!
1232       // If we know the constants are equal, we can decide the result of this
1233       // computation precisely.
1234       return ConstantBool::get(Opcode == Instruction::SetEQ ||
1235                                Opcode == Instruction::SetLE ||
1236                                Opcode == Instruction::SetGE);
1237     case Instruction::SetLT:
1238       // If we know that V1 < V2, we can decide the result of this computation
1239       // precisely.
1240       return ConstantBool::get(Opcode == Instruction::SetLT ||
1241                                Opcode == Instruction::SetNE ||
1242                                Opcode == Instruction::SetLE);
1243     case Instruction::SetGT:
1244       // If we know that V1 > V2, we can decide the result of this computation
1245       // precisely.
1246       return ConstantBool::get(Opcode == Instruction::SetGT ||
1247                                Opcode == Instruction::SetNE ||
1248                                Opcode == Instruction::SetGE);
1249     case Instruction::SetLE:
1250       // If we know that V1 <= V2, we can only partially decide this relation.
1251       if (Opcode == Instruction::SetGT) return ConstantBool::getFalse();
1252       if (Opcode == Instruction::SetLT) return ConstantBool::getTrue();
1253       break;
1254
1255     case Instruction::SetGE:
1256       // If we know that V1 >= V2, we can only partially decide this relation.
1257       if (Opcode == Instruction::SetLT) return ConstantBool::getFalse();
1258       if (Opcode == Instruction::SetGT) return ConstantBool::getTrue();
1259       break;
1260
1261     case Instruction::SetNE:
1262       // If we know that V1 != V2, we can only partially decide this relation.
1263       if (Opcode == Instruction::SetEQ) return ConstantBool::getFalse();
1264       if (Opcode == Instruction::SetNE) return ConstantBool::getTrue();
1265       break;
1266     }
1267   }
1268
1269   if (isa<UndefValue>(V1) || isa<UndefValue>(V2)) {
1270     switch (Opcode) {
1271     case Instruction::Add:
1272     case Instruction::Sub:
1273     case Instruction::Xor:
1274       return UndefValue::get(V1->getType());
1275
1276     case Instruction::Mul:
1277     case Instruction::And:
1278       return Constant::getNullValue(V1->getType());
1279     case Instruction::Div:
1280     case Instruction::Rem:
1281       if (!isa<UndefValue>(V2))     // undef/X -> 0
1282         return Constant::getNullValue(V1->getType());
1283       return const_cast<Constant*>(V2);                // X/undef -> undef
1284     case Instruction::Or:           // X|undef -> -1
1285       return ConstantInt::getAllOnesValue(V1->getType());
1286     case Instruction::Shr:
1287       if (!isa<UndefValue>(V2)) {
1288         if (V1->getType()->isSigned())
1289           return const_cast<Constant*>(V1);  // undef >>s X -> undef
1290         // undef >>u X -> 0
1291       } else if (isa<UndefValue>(V1)) {
1292         return const_cast<Constant*>(V1);   //  undef >> undef -> undef
1293       } else {
1294         if (V1->getType()->isSigned())
1295           return const_cast<Constant*>(V1);  // X >>s undef -> X
1296         // X >>u undef -> 0
1297       }
1298       return Constant::getNullValue(V1->getType());
1299
1300     case Instruction::Shl:
1301       // undef << X -> 0   X << undef -> 0
1302       return Constant::getNullValue(V1->getType());
1303     }
1304   }
1305
1306   if (const ConstantExpr *CE1 = dyn_cast<ConstantExpr>(V1)) {
1307     if (const ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2)) {
1308       // There are many possible foldings we could do here.  We should probably
1309       // at least fold add of a pointer with an integer into the appropriate
1310       // getelementptr.  This will improve alias analysis a bit.
1311
1312
1313
1314
1315     } else {
1316       // Just implement a couple of simple identities.
1317       switch (Opcode) {
1318       case Instruction::Add:
1319         if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X + 0 == X
1320         break;
1321       case Instruction::Sub:
1322         if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X - 0 == X
1323         break;
1324       case Instruction::Mul:
1325         if (V2->isNullValue()) return const_cast<Constant*>(V2);  // X * 0 == 0
1326         if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1327           if (CI->getRawValue() == 1)
1328             return const_cast<Constant*>(V1);                     // X * 1 == X
1329         break;
1330       case Instruction::Div:
1331         if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1332           if (CI->getRawValue() == 1)
1333             return const_cast<Constant*>(V1);                     // X / 1 == X
1334         break;
1335       case Instruction::Rem:
1336         if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1337           if (CI->getRawValue() == 1)
1338             return Constant::getNullValue(CI->getType()); // X % 1 == 0
1339         break;
1340       case Instruction::And:
1341         if (cast<ConstantIntegral>(V2)->isAllOnesValue())
1342           return const_cast<Constant*>(V1);                       // X & -1 == X
1343         if (V2->isNullValue()) return const_cast<Constant*>(V2);  // X & 0 == 0
1344         if (CE1->getOpcode() == Instruction::Cast &&
1345             isa<GlobalValue>(CE1->getOperand(0))) {
1346           GlobalValue *CPR = cast<GlobalValue>(CE1->getOperand(0));
1347
1348           // Functions are at least 4-byte aligned.  If and'ing the address of a
1349           // function with a constant < 4, fold it to zero.
1350           if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1351             if (CI->getRawValue() < 4 && isa<Function>(CPR))
1352               return Constant::getNullValue(CI->getType());
1353         }
1354         break;
1355       case Instruction::Or:
1356         if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X | 0 == X
1357         if (cast<ConstantIntegral>(V2)->isAllOnesValue())
1358           return const_cast<Constant*>(V2);  // X | -1 == -1
1359         break;
1360       case Instruction::Xor:
1361         if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X ^ 0 == X
1362         break;
1363       }
1364     }
1365
1366   } else if (const ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2)) {
1367     // If V2 is a constant expr and V1 isn't, flop them around and fold the
1368     // other way if possible.
1369     switch (Opcode) {
1370     case Instruction::Add:
1371     case Instruction::Mul:
1372     case Instruction::And:
1373     case Instruction::Or:
1374     case Instruction::Xor:
1375     case Instruction::SetEQ:
1376     case Instruction::SetNE:
1377       // No change of opcode required.
1378       return ConstantFoldBinaryInstruction(Opcode, V2, V1);
1379
1380     case Instruction::SetLT:
1381     case Instruction::SetGT:
1382     case Instruction::SetLE:
1383     case Instruction::SetGE:
1384       // Change the opcode as necessary to swap the operands.
1385       Opcode = SetCondInst::getSwappedCondition((Instruction::BinaryOps)Opcode);
1386       return ConstantFoldBinaryInstruction(Opcode, V2, V1);
1387
1388     case Instruction::Shl:
1389     case Instruction::Shr:
1390     case Instruction::Sub:
1391     case Instruction::Div:
1392     case Instruction::Rem:
1393     default:  // These instructions cannot be flopped around.
1394       break;
1395     }
1396   }
1397   return 0;
1398 }
1399
1400 Constant *llvm::ConstantFoldGetElementPtr(const Constant *C,
1401                                           const std::vector<Value*> &IdxList) {
1402   if (IdxList.size() == 0 ||
1403       (IdxList.size() == 1 && cast<Constant>(IdxList[0])->isNullValue()))
1404     return const_cast<Constant*>(C);
1405
1406   if (isa<UndefValue>(C)) {
1407     const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList,
1408                                                        true);
1409     assert(Ty != 0 && "Invalid indices for GEP!");
1410     return UndefValue::get(PointerType::get(Ty));
1411   }
1412
1413   Constant *Idx0 = cast<Constant>(IdxList[0]);
1414   if (C->isNullValue()) {
1415     bool isNull = true;
1416     for (unsigned i = 0, e = IdxList.size(); i != e; ++i)
1417       if (!cast<Constant>(IdxList[i])->isNullValue()) {
1418         isNull = false;
1419         break;
1420       }
1421     if (isNull) {
1422       const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList,
1423                                                          true);
1424       assert(Ty != 0 && "Invalid indices for GEP!");
1425       return ConstantPointerNull::get(PointerType::get(Ty));
1426     }
1427
1428     if (IdxList.size() == 1) {
1429       const Type *ElTy = cast<PointerType>(C->getType())->getElementType();
1430       if (unsigned ElSize = ElTy->getPrimitiveSize()) {
1431         // gep null, C is equal to C*sizeof(nullty).  If nullty is a known llvm
1432         // type, we can statically fold this.
1433         Constant *R = ConstantUInt::get(Type::UIntTy, ElSize);
1434         R = ConstantExpr::getCast(R, Idx0->getType());
1435         R = ConstantExpr::getMul(R, Idx0);
1436         return ConstantExpr::getCast(R, C->getType());
1437       }
1438     }
1439   }
1440
1441   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(const_cast<Constant*>(C))) {
1442     // Combine Indices - If the source pointer to this getelementptr instruction
1443     // is a getelementptr instruction, combine the indices of the two
1444     // getelementptr instructions into a single instruction.
1445     //
1446     if (CE->getOpcode() == Instruction::GetElementPtr) {
1447       const Type *LastTy = 0;
1448       for (gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
1449            I != E; ++I)
1450         LastTy = *I;
1451
1452       if ((LastTy && isa<ArrayType>(LastTy)) || Idx0->isNullValue()) {
1453         std::vector<Value*> NewIndices;
1454         NewIndices.reserve(IdxList.size() + CE->getNumOperands());
1455         for (unsigned i = 1, e = CE->getNumOperands()-1; i != e; ++i)
1456           NewIndices.push_back(CE->getOperand(i));
1457
1458         // Add the last index of the source with the first index of the new GEP.
1459         // Make sure to handle the case when they are actually different types.
1460         Constant *Combined = CE->getOperand(CE->getNumOperands()-1);
1461         // Otherwise it must be an array.
1462         if (!Idx0->isNullValue()) {
1463           const Type *IdxTy = Combined->getType();
1464           if (IdxTy != Idx0->getType()) IdxTy = Type::LongTy;
1465           Combined =
1466             ConstantExpr::get(Instruction::Add,
1467                               ConstantExpr::getCast(Idx0, IdxTy),
1468                               ConstantExpr::getCast(Combined, IdxTy));
1469         }
1470
1471         NewIndices.push_back(Combined);
1472         NewIndices.insert(NewIndices.end(), IdxList.begin()+1, IdxList.end());
1473         return ConstantExpr::getGetElementPtr(CE->getOperand(0), NewIndices);
1474       }
1475     }
1476
1477     // Implement folding of:
1478     //    int* getelementptr ([2 x int]* cast ([3 x int]* %X to [2 x int]*),
1479     //                        long 0, long 0)
1480     // To: int* getelementptr ([3 x int]* %X, long 0, long 0)
1481     //
1482     if (CE->getOpcode() == Instruction::Cast && IdxList.size() > 1 &&
1483         Idx0->isNullValue())
1484       if (const PointerType *SPT =
1485           dyn_cast<PointerType>(CE->getOperand(0)->getType()))
1486         if (const ArrayType *SAT = dyn_cast<ArrayType>(SPT->getElementType()))
1487           if (const ArrayType *CAT =
1488         dyn_cast<ArrayType>(cast<PointerType>(C->getType())->getElementType()))
1489             if (CAT->getElementType() == SAT->getElementType())
1490               return ConstantExpr::getGetElementPtr(
1491                       (Constant*)CE->getOperand(0), IdxList);
1492   }
1493   return 0;
1494 }
1495