lib/VMCore/ConstantFold.cpp

   1 //===- ConstantHandling.cpp - Implement ConstantHandling.h ----------------===//
   2 //
   3 // This file implements the various intrinsic operations, on constant values.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "llvm/ConstantHandling.h"
   8 #include "llvm/iPHINode.h"
   9 #include <cmath>
  10
  11 AnnotationID ConstRules::AID(AnnotationManager::getID("opt::ConstRules",
  12                                                       &ConstRules::find));
  13
  14 // ConstantFoldInstruction - Attempt to constant fold the specified instruction.
  15 // If successful, the constant result is returned, if not, null is returned.
  16 //
  17 Constant *ConstantFoldInstruction(Instruction *I) {
  18   if (PHINode *PN = dyn_cast<PHINode>(I)) {
  19     if (PN->getNumIncomingValues() == 0)
  20       return Constant::getNullValue(PN->getType());
  21
  22     Constant *Result = dyn_cast<Constant>(PN->getIncomingValue(0));
  23     if (Result == 0) return 0;
  24
  25     // Handle PHI nodes specially here...
  26     for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i)
  27       if (PN->getIncomingValue(i) != Result)
  28         return 0;   // Not all the same incoming constants...
  29
  30     // If we reach here, all incoming values are the same constant.
  31     return Result;
  32   }
  33
  34   Constant *Op0 = 0;
  35   Constant *Op1 = 0;
  36
  37   if (I->getNumOperands() != 0) {    // Get first operand if it's a constant...
  38     Op0 = dyn_cast<Constant>(I->getOperand(0));
  39     if (Op0 == 0) return 0;          // Not a constant?, can't fold
  40
  41     if (I->getNumOperands() != 1) {  // Get second operand if it's a constant...
  42       Op1 = dyn_cast<Constant>(I->getOperand(1));
  43       if (Op1 == 0) return 0;        // Not a constant?, can't fold
  44     }
  45   }
  46
  47   switch (I->getOpcode()) {
  48   case Instruction::Cast:
  49     return ConstRules::get(*Op0)->castTo(Op0, I->getType());
  50   case Instruction::Add:     return *Op0 + *Op1;
  51   case Instruction::Sub:     return *Op0 - *Op1;
  52   case Instruction::Mul:     return *Op0 * *Op1;
  53   case Instruction::Div:     return *Op0 / *Op1;
  54   case Instruction::Rem:     return *Op0 % *Op1;
  55   case Instruction::And:     return *Op0 & *Op1;
  56   case Instruction::Or:      return *Op0 | *Op1;
  57   case Instruction::Xor:     return *Op0 ^ *Op1;
  58
  59   case Instruction::SetEQ:   return *Op0 == *Op1;
  60   case Instruction::SetNE:   return *Op0 != *Op1;
  61   case Instruction::SetLE:   return *Op0 <= *Op1;
  62   case Instruction::SetGE:   return *Op0 >= *Op1;
  63   case Instruction::SetLT:   return *Op0 <  *Op1;
  64   case Instruction::SetGT:   return *Op0 >  *Op1;
  65   case Instruction::Shl:     return *Op0 << *Op1;
  66   case Instruction::Shr:     return *Op0 >> *Op1;
  67   default:
  68     return 0;
  69   }
  70 }
  71
  72 Constant *ConstantFoldCastInstruction(const Constant *V, const Type *DestTy) {
  73   return ConstRules::get(*V)->castTo(V, DestTy);
  74 }
  75
  76 Constant *ConstantFoldBinaryInstruction(unsigned Opcode, const Constant *V1,
  77                                         const Constant *V2) {
  78   switch (Opcode) {
  79   case Instruction::Add:     return *V1 + *V2;
  80   case Instruction::Sub:     return *V1 - *V2;
  81   case Instruction::Mul:     return *V1 * *V2;
  82   case Instruction::Div:     return *V1 / *V2;
  83   case Instruction::Rem:     return *V1 % *V2;
  84   case Instruction::And:     return *V1 & *V2;
  85   case Instruction::Or:      return *V1 | *V2;
  86   case Instruction::Xor:     return *V1 ^ *V2;
  87
  88   case Instruction::SetEQ:   return *V1 == *V2;
  89   case Instruction::SetNE:   return *V1 != *V2;
  90   case Instruction::SetLE:   return *V1 <= *V2;
  91   case Instruction::SetGE:   return *V1 >= *V2;
  92   case Instruction::SetLT:   return *V1 <  *V2;
  93   case Instruction::SetGT:   return *V1 >  *V2;
  94   }
  95   return 0;
  96 }
  97
  98 Constant *ConstantFoldShiftInstruction(unsigned Opcode, const Constant *V1,
  99                                        const Constant *V2) {
 100   switch (Opcode) {
 101   case Instruction::Shl:     return *V1 << *V2;
 102   case Instruction::Shr:     return *V1 >> *V2;
 103   default:                   return 0;
 104   }
 105 }
 106
 107
 108 //===----------------------------------------------------------------------===//
 109 //                             TemplateRules Class
 110 //===----------------------------------------------------------------------===//
 111 //
 112 // TemplateRules - Implement a subclass of ConstRules that provides all
 113 // operations as noops.  All other rules classes inherit from this class so
 114 // that if functionality is needed in the future, it can simply be added here
 115 // and to ConstRules without changing anything else...
 116 //
 117 // This class also provides subclasses with typesafe implementations of methods
 118 // so that don't have to do type casting.
 119 //
 120 template<class ArgType, class SubClassName>
 121 class TemplateRules : public ConstRules {
 122
 123   //===--------------------------------------------------------------------===//
 124   // Redirecting functions that cast to the appropriate types
 125   //===--------------------------------------------------------------------===//
 126
 127   virtual Constant *add(const Constant *V1, const Constant *V2) const {
 128     return SubClassName::Add((const ArgType *)V1, (const ArgType *)V2);
 129   }
 130   virtual Constant *sub(const Constant *V1, const Constant *V2) const {
 131     return SubClassName::Sub((const ArgType *)V1, (const ArgType *)V2);
 132   }
 133   virtual Constant *mul(const Constant *V1, const Constant *V2) const {
 134     return SubClassName::Mul((const ArgType *)V1, (const ArgType *)V2);
 135   }
 136   virtual Constant *div(const Constant *V1, const Constant *V2) const {
 137     return SubClassName::Div((const ArgType *)V1, (const ArgType *)V2);
 138   }
 139   virtual Constant *rem(const Constant *V1, const Constant *V2) const {
 140     return SubClassName::Rem((const ArgType *)V1, (const ArgType *)V2);
 141   }
 142   virtual Constant *op_and(const Constant *V1, const Constant *V2) const {
 143     return SubClassName::And((const ArgType *)V1, (const ArgType *)V2);
 144   }
 145   virtual Constant *op_or(const Constant *V1, const Constant *V2) const {
 146     return SubClassName::Or((const ArgType *)V1, (const ArgType *)V2);
 147   }
 148   virtual Constant *op_xor(const Constant *V1, const Constant *V2) const {
 149     return SubClassName::Xor((const ArgType *)V1, (const ArgType *)V2);
 150   }
 151   virtual Constant *shl(const Constant *V1, const Constant *V2) const {
 152     return SubClassName::Shl((const ArgType *)V1, (const ArgType *)V2);
 153   }
 154   virtual Constant *shr(const Constant *V1, const Constant *V2) const {
 155     return SubClassName::Shr((const ArgType *)V1, (const ArgType *)V2);
 156   }
 157
 158   virtual ConstantBool *lessthan(const Constant *V1,
 159                                  const Constant *V2) const {
 160     return SubClassName::LessThan((const ArgType *)V1, (const ArgType *)V2);
 161   }
 162
 163   // Casting operators.  ick
 164   virtual ConstantBool *castToBool(const Constant *V) const {
 165     return SubClassName::CastToBool((const ArgType*)V);
 166   }
 167   virtual ConstantSInt *castToSByte(const Constant *V) const {
 168     return SubClassName::CastToSByte((const ArgType*)V);
 169   }
 170   virtual ConstantUInt *castToUByte(const Constant *V) const {
 171     return SubClassName::CastToUByte((const ArgType*)V);
 172   }
 173   virtual ConstantSInt *castToShort(const Constant *V) const {
 174     return SubClassName::CastToShort((const ArgType*)V);
 175   }
 176   virtual ConstantUInt *castToUShort(const Constant *V) const {
 177     return SubClassName::CastToUShort((const ArgType*)V);
 178   }
 179   virtual ConstantSInt *castToInt(const Constant *V) const {
 180     return SubClassName::CastToInt((const ArgType*)V);
 181   }
 182   virtual ConstantUInt *castToUInt(const Constant *V) const {
 183     return SubClassName::CastToUInt((const ArgType*)V);
 184   }
 185   virtual ConstantSInt *castToLong(const Constant *V) const {
 186     return SubClassName::CastToLong((const ArgType*)V);
 187   }
 188   virtual ConstantUInt *castToULong(const Constant *V) const {
 189     return SubClassName::CastToULong((const ArgType*)V);
 190   }
 191   virtual ConstantFP   *castToFloat(const Constant *V) const {
 192     return SubClassName::CastToFloat((const ArgType*)V);
 193   }
 194   virtual ConstantFP   *castToDouble(const Constant *V) const {
 195     return SubClassName::CastToDouble((const ArgType*)V);
 196   }
 197   virtual ConstantPointer *castToPointer(const Constant *V,
 198                                          const PointerType *Ty) const {
 199     return SubClassName::CastToPointer((const ArgType*)V, Ty);
 200   }
 201
 202   //===--------------------------------------------------------------------===//
 203   // Default "noop" implementations
 204   //===--------------------------------------------------------------------===//
 205
 206   static Constant *Add(const ArgType *V1, const ArgType *V2) { return 0; }
 207   static Constant *Sub(const ArgType *V1, const ArgType *V2) { return 0; }
 208   static Constant *Mul(const ArgType *V1, const ArgType *V2) { return 0; }
 209   static Constant *Div(const ArgType *V1, const ArgType *V2) { return 0; }
 210   static Constant *Rem(const ArgType *V1, const ArgType *V2) { return 0; }
 211   static Constant *And(const ArgType *V1, const ArgType *V2) { return 0; }
 212   static Constant *Or (const ArgType *V1, const ArgType *V2) { return 0; }
 213   static Constant *Xor(const ArgType *V1, const ArgType *V2) { return 0; }
 214   static Constant *Shl(const ArgType *V1, const ArgType *V2) { return 0; }
 215   static Constant *Shr(const ArgType *V1, const ArgType *V2) { return 0; }
 216   static ConstantBool *LessThan(const ArgType *V1, const ArgType *V2) {
 217     return 0;
 218   }
 219
 220   // Casting operators.  ick
 221   static ConstantBool *CastToBool  (const Constant *V) { return 0; }
 222   static ConstantSInt *CastToSByte (const Constant *V) { return 0; }
 223   static ConstantUInt *CastToUByte (const Constant *V) { return 0; }
 224   static ConstantSInt *CastToShort (const Constant *V) { return 0; }
 225   static ConstantUInt *CastToUShort(const Constant *V) { return 0; }
 226   static ConstantSInt *CastToInt   (const Constant *V) { return 0; }
 227   static ConstantUInt *CastToUInt  (const Constant *V) { return 0; }
 228   static ConstantSInt *CastToLong  (const Constant *V) { return 0; }
 229   static ConstantUInt *CastToULong (const Constant *V) { return 0; }
 230   static ConstantFP   *CastToFloat (const Constant *V) { return 0; }
 231   static ConstantFP   *CastToDouble(const Constant *V) { return 0; }
 232   static ConstantPointer *CastToPointer(const Constant *,
 233                                         const PointerType *) {return 0;}
 234 };
 235
 236
 237
 238 //===----------------------------------------------------------------------===//
 239 //                             EmptyRules Class
 240 //===----------------------------------------------------------------------===//
 241 //
 242 // EmptyRules provides a concrete base class of ConstRules that does nothing
 243 //
 244 struct EmptyRules : public TemplateRules<Constant, EmptyRules> {
 245 };
 246
 247
 248
 249 //===----------------------------------------------------------------------===//
 250 //                              BoolRules Class
 251 //===----------------------------------------------------------------------===//
 252 //
 253 // BoolRules provides a concrete base class of ConstRules for the 'bool' type.
 254 //
 255 struct BoolRules : public TemplateRules<ConstantBool, BoolRules> {
 256
 257   static Constant *And(const ConstantBool *V1, const ConstantBool *V2) {
 258     return ConstantBool::get(V1->getValue() & V2->getValue());
 259   }
 260
 261   static Constant *Or(const ConstantBool *V1, const ConstantBool *V2) {
 262     return ConstantBool::get(V1->getValue() | V2->getValue());
 263   }
 264
 265   static Constant *Xor(const ConstantBool *V1, const ConstantBool *V2) {
 266     return ConstantBool::get(V1->getValue() ^ V2->getValue());
 267   }
 268 };
 269
 270
 271 //===----------------------------------------------------------------------===//
 272 //                            PointerRules Class
 273 //===----------------------------------------------------------------------===//
 274 //
 275 // PointerRules provides a concrete base class of ConstRules for pointer types
 276 //
 277 struct PointerRules : public TemplateRules<ConstantPointer, PointerRules> {
 278   static ConstantBool *CastToBool  (const Constant *V) {
 279     if (V->isNullValue()) return ConstantBool::False;
 280     return 0;  // Can't const prop other types of pointers
 281   }
 282   static ConstantSInt *CastToSByte (const Constant *V) {
 283     if (V->isNullValue()) return ConstantSInt::get(Type::SByteTy, 0);
 284     return 0;  // Can't const prop other types of pointers
 285   }
 286   static ConstantUInt *CastToUByte (const Constant *V) {
 287     if (V->isNullValue()) return ConstantUInt::get(Type::UByteTy, 0);
 288     return 0;  // Can't const prop other types of pointers
 289   }
 290   static ConstantSInt *CastToShort (const Constant *V) {
 291     if (V->isNullValue()) return ConstantSInt::get(Type::ShortTy, 0);
 292     return 0;  // Can't const prop other types of pointers
 293   }
 294   static ConstantUInt *CastToUShort(const Constant *V) {
 295     if (V->isNullValue()) return ConstantUInt::get(Type::UShortTy, 0);
 296     return 0;  // Can't const prop other types of pointers
 297   }
 298   static ConstantSInt *CastToInt   (const Constant *V) {
 299     if (V->isNullValue()) return ConstantSInt::get(Type::IntTy, 0);
 300     return 0;  // Can't const prop other types of pointers
 301   }
 302   static ConstantUInt *CastToUInt  (const Constant *V) {
 303     if (V->isNullValue()) return ConstantUInt::get(Type::UIntTy, 0);
 304     return 0;  // Can't const prop other types of pointers
 305   }
 306   static ConstantSInt *CastToLong  (const Constant *V) {
 307     if (V->isNullValue()) return ConstantSInt::get(Type::LongTy, 0);
 308     return 0;  // Can't const prop other types of pointers
 309   }
 310   static ConstantUInt *CastToULong (const Constant *V) {
 311     if (V->isNullValue()) return ConstantUInt::get(Type::ULongTy, 0);
 312     return 0;  // Can't const prop other types of pointers
 313   }
 314   static ConstantFP   *CastToFloat (const Constant *V) {
 315     if (V->isNullValue()) return ConstantFP::get(Type::FloatTy, 0);
 316     return 0;  // Can't const prop other types of pointers
 317   }
 318   static ConstantFP   *CastToDouble(const Constant *V) {
 319     if (V->isNullValue()) return ConstantFP::get(Type::DoubleTy, 0);
 320     return 0;  // Can't const prop other types of pointers
 321   }
 322
 323   static ConstantPointer *CastToPointer(const ConstantPointer *V,
 324                                         const PointerType *PTy) {
 325     if (V->getType() == PTy)
 326       return const_cast<ConstantPointer*>(V);  // Allow cast %PTy %ptr to %PTy
 327     if (V->isNullValue())
 328       return ConstantPointerNull::get(PTy);
 329     return 0;  // Can't const prop other types of pointers
 330   }
 331 };
 332
 333
 334 //===----------------------------------------------------------------------===//
 335 //                             DirectRules Class
 336 //===----------------------------------------------------------------------===//
 337 //
 338 // DirectRules provides a concrete base classes of ConstRules for a variety of
 339 // different types.  This allows the C++ compiler to automatically generate our
 340 // constant handling operations in a typesafe and accurate manner.
 341 //
 342 template<class ConstantClass, class BuiltinType, Type **Ty, class SuperClass>
 343 struct DirectRules : public TemplateRules<ConstantClass, SuperClass> {
 344   static Constant *Add(const ConstantClass *V1, const ConstantClass *V2) {
 345     BuiltinType R = (BuiltinType)V1->getValue() + (BuiltinType)V2->getValue();
 346     return ConstantClass::get(*Ty, R);
 347   }
 348
 349   static Constant *Sub(const ConstantClass *V1, const ConstantClass *V2) {
 350     BuiltinType R = (BuiltinType)V1->getValue() - (BuiltinType)V2->getValue();
 351     return ConstantClass::get(*Ty, R);
 352   }
 353
 354   static Constant *Mul(const ConstantClass *V1, const ConstantClass *V2) {
 355     BuiltinType R = (BuiltinType)V1->getValue() * (BuiltinType)V2->getValue();
 356     return ConstantClass::get(*Ty, R);
 357   }
 358
 359   static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) {
 360     if (V2->isNullValue()) return 0;
 361     BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue();
 362     return ConstantClass::get(*Ty, R);
 363   }
 364
 365   static ConstantBool *LessThan(const ConstantClass *V1,
 366                                 const ConstantClass *V2) {
 367     bool R = (BuiltinType)V1->getValue() < (BuiltinType)V2->getValue();
 368     return ConstantBool::get(R);
 369   }
 370
 371   static ConstantPointer *CastToPointer(const ConstantClass *V,
 372                                         const PointerType *PTy) {
 373     if (V->isNullValue())    // Is it a FP or Integral null value?
 374       return ConstantPointerNull::get(PTy);
 375     return 0;  // Can't const prop other types of pointers
 376   }
 377
 378   // Casting operators.  ick
 379 #define DEF_CAST(TYPE, CLASS, CTYPE) \
 380   static CLASS *CastTo##TYPE  (const ConstantClass *V) {    \
 381     return CLASS::get(Type::TYPE##Ty, (CTYPE)(BuiltinType)V->getValue()); \
 382   }
 383
 384   DEF_CAST(Bool  , ConstantBool, bool)
 385   DEF_CAST(SByte , ConstantSInt, signed char)
 386   DEF_CAST(UByte , ConstantUInt, unsigned char)
 387   DEF_CAST(Short , ConstantSInt, signed short)
 388   DEF_CAST(UShort, ConstantUInt, unsigned short)
 389   DEF_CAST(Int   , ConstantSInt, signed int)
 390   DEF_CAST(UInt  , ConstantUInt, unsigned int)
 391   DEF_CAST(Long  , ConstantSInt, int64_t)
 392   DEF_CAST(ULong , ConstantUInt, uint64_t)
 393   DEF_CAST(Float , ConstantFP  , float)
 394   DEF_CAST(Double, ConstantFP  , double)
 395 #undef DEF_CAST
 396 };
 397
 398
 399 //===----------------------------------------------------------------------===//
 400 //                           DirectIntRules Class
 401 //===----------------------------------------------------------------------===//
 402 //
 403 // DirectIntRules provides implementations of functions that are valid on
 404 // integer types, but not all types in general.
 405 //
 406 template <class ConstantClass, class BuiltinType, Type **Ty>
 407 struct DirectIntRules
 408   : public DirectRules<ConstantClass, BuiltinType, Ty,
 409                        DirectIntRules<ConstantClass, BuiltinType, Ty> > {
 410
 411   static Constant *Rem(const ConstantClass *V1,
 412                        const ConstantClass *V2) {
 413     if (V2->isNullValue()) return 0;
 414     BuiltinType R = (BuiltinType)V1->getValue() % (BuiltinType)V2->getValue();
 415     return ConstantClass::get(*Ty, R);
 416   }
 417
 418   static Constant *And(const ConstantClass *V1, const ConstantClass *V2) {
 419     BuiltinType R = (BuiltinType)V1->getValue() & (BuiltinType)V2->getValue();
 420     return ConstantClass::get(*Ty, R);
 421   }
 422   static Constant *Or(const ConstantClass *V1, const ConstantClass *V2) {
 423     BuiltinType R = (BuiltinType)V1->getValue() | (BuiltinType)V2->getValue();
 424     return ConstantClass::get(*Ty, R);
 425   }
 426   static Constant *Xor(const ConstantClass *V1, const ConstantClass *V2) {
 427     BuiltinType R = (BuiltinType)V1->getValue() ^ (BuiltinType)V2->getValue();
 428     return ConstantClass::get(*Ty, R);
 429   }
 430
 431   static Constant *Shl(const ConstantClass *V1, const ConstantClass *V2) {
 432     BuiltinType R = (BuiltinType)V1->getValue() << (BuiltinType)V2->getValue();
 433     return ConstantClass::get(*Ty, R);
 434   }
 435
 436   static Constant *Shr(const ConstantClass *V1, const ConstantClass *V2) {
 437     BuiltinType R = (BuiltinType)V1->getValue() >> (BuiltinType)V2->getValue();
 438     return ConstantClass::get(*Ty, R);
 439   }
 440 };
 441
 442
 443 //===----------------------------------------------------------------------===//
 444 //                           DirectFPRules Class
 445 //===----------------------------------------------------------------------===//
 446 //
 447 // DirectFPRules provides implementations of functions that are valid on
 448 // floating point types, but not all types in general.
 449 //
 450 template <class ConstantClass, class BuiltinType, Type **Ty>
 451 struct DirectFPRules
 452   : public DirectRules<ConstantClass, BuiltinType, Ty,
 453                        DirectFPRules<ConstantClass, BuiltinType, Ty> > {
 454   static Constant *Rem(const ConstantClass *V1, const ConstantClass *V2) {
 455     if (V2->isNullValue()) return 0;
 456     BuiltinType Result = std::fmod((BuiltinType)V1->getValue(),
 457                                    (BuiltinType)V2->getValue());
 458     return ConstantClass::get(*Ty, Result);
 459   }
 460 };
 461
 462
 463 //===----------------------------------------------------------------------===//
 464 //                            DirectRules Subclasses
 465 //===----------------------------------------------------------------------===//
 466 //
 467 // Given the DirectRules class we can now implement lots of types with little
 468 // code.  Thank goodness C++ compilers are great at stomping out layers of
 469 // templates... can you imagine having to do this all by hand? (/me is lazy :)
 470 //
 471
 472 // ConstRules::find - Return the constant rules that take care of the specified
 473 // type.
 474 //
 475 Annotation *ConstRules::find(AnnotationID AID, const Annotable *TyA, void *) {
 476   assert(AID == ConstRules::AID && "Bad annotation for factory!");
 477   const Type *Ty = cast<Type>((const Value*)TyA);
 478
 479   switch (Ty->getPrimitiveID()) {
 480   case Type::BoolTyID:    return new BoolRules();
 481   case Type::PointerTyID: return new PointerRules();
 482   case Type::SByteTyID:
 483     return new DirectIntRules<ConstantSInt,   signed char , &Type::SByteTy>();
 484   case Type::UByteTyID:
 485     return new DirectIntRules<ConstantUInt, unsigned char , &Type::UByteTy>();
 486   case Type::ShortTyID:
 487     return new DirectIntRules<ConstantSInt,   signed short, &Type::ShortTy>();
 488   case Type::UShortTyID:
 489     return new DirectIntRules<ConstantUInt, unsigned short, &Type::UShortTy>();
 490   case Type::IntTyID:
 491     return new DirectIntRules<ConstantSInt,   signed int  , &Type::IntTy>();
 492   case Type::UIntTyID:
 493     return new DirectIntRules<ConstantUInt, unsigned int  , &Type::UIntTy>();
 494   case Type::LongTyID:
 495     return new DirectIntRules<ConstantSInt,  int64_t      , &Type::LongTy>();
 496   case Type::ULongTyID:
 497     return new DirectIntRules<ConstantUInt, uint64_t      , &Type::ULongTy>();
 498   case Type::FloatTyID:
 499     return new DirectFPRules<ConstantFP  , float         , &Type::FloatTy>();
 500   case Type::DoubleTyID:
 501     return new DirectFPRules<ConstantFP  , double        , &Type::DoubleTy>();
 502   default:
 503     return new EmptyRules();
 504   }
 505 }