ConstantFold.cpp revision 589fda514c4977ac936354f5a1c0226bbf409c86 
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
11AnnotationID 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//
17Constant *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
72Constant *ConstantFoldCastInstruction(const Constant *V, const Type *DestTy) {
73  return ConstRules::get(*V)->castTo(V, DestTy);
74}
75
76Constant *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
98Constant *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//
120template<class ArgType, class SubClassName>
121class 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//
244struct 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//
255struct 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//
277struct 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//
342template<class ConstantClass, class BuiltinType, Type **Ty, class SuperClass>
343struct 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//
406template <class ConstantClass, class BuiltinType, Type **Ty>
407struct 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//
450template <class ConstantClass, class BuiltinType, Type **Ty>
451struct 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//
475Annotation *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}
506