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