ConstantFold.cpp revision 252030e86b4cd252eadf702356ff3a7951247276 
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 ConstantBool *LessThan(const ConstantBool *V1, const ConstantBool *V2){
258    return ConstantBool::get(V1->getValue() < V2->getValue());
259  }
260
261  static Constant *And(const ConstantBool *V1, const ConstantBool *V2) {
262    return ConstantBool::get(V1->getValue() & V2->getValue());
263  }
264
265  static Constant *Or(const ConstantBool *V1, const ConstantBool *V2) {
266    return ConstantBool::get(V1->getValue() | V2->getValue());
267  }
268
269  static Constant *Xor(const ConstantBool *V1, const ConstantBool *V2) {
270    return ConstantBool::get(V1->getValue() ^ V2->getValue());
271  }
272};
273
274
275//===----------------------------------------------------------------------===//
276//                            PointerRules Class
277//===----------------------------------------------------------------------===//
278//
279// PointerRules provides a concrete base class of ConstRules for pointer types
280//
281struct PointerRules : public TemplateRules<ConstantPointer, PointerRules> {
282  static ConstantBool *CastToBool  (const Constant *V) {
283    if (V->isNullValue()) return ConstantBool::False;
284    return 0;  // Can't const prop other types of pointers
285  }
286  static ConstantSInt *CastToSByte (const Constant *V) {
287    if (V->isNullValue()) return ConstantSInt::get(Type::SByteTy, 0);
288    return 0;  // Can't const prop other types of pointers
289  }
290  static ConstantUInt *CastToUByte (const Constant *V) {
291    if (V->isNullValue()) return ConstantUInt::get(Type::UByteTy, 0);
292    return 0;  // Can't const prop other types of pointers
293  }
294  static ConstantSInt *CastToShort (const Constant *V) {
295    if (V->isNullValue()) return ConstantSInt::get(Type::ShortTy, 0);
296    return 0;  // Can't const prop other types of pointers
297  }
298  static ConstantUInt *CastToUShort(const Constant *V) {
299    if (V->isNullValue()) return ConstantUInt::get(Type::UShortTy, 0);
300    return 0;  // Can't const prop other types of pointers
301  }
302  static ConstantSInt *CastToInt   (const Constant *V) {
303    if (V->isNullValue()) return ConstantSInt::get(Type::IntTy, 0);
304    return 0;  // Can't const prop other types of pointers
305  }
306  static ConstantUInt *CastToUInt  (const Constant *V) {
307    if (V->isNullValue()) return ConstantUInt::get(Type::UIntTy, 0);
308    return 0;  // Can't const prop other types of pointers
309  }
310  static ConstantSInt *CastToLong  (const Constant *V) {
311    if (V->isNullValue()) return ConstantSInt::get(Type::LongTy, 0);
312    return 0;  // Can't const prop other types of pointers
313  }
314  static ConstantUInt *CastToULong (const Constant *V) {
315    if (V->isNullValue()) return ConstantUInt::get(Type::ULongTy, 0);
316    return 0;  // Can't const prop other types of pointers
317  }
318  static ConstantFP   *CastToFloat (const Constant *V) {
319    if (V->isNullValue()) return ConstantFP::get(Type::FloatTy, 0);
320    return 0;  // Can't const prop other types of pointers
321  }
322  static ConstantFP   *CastToDouble(const Constant *V) {
323    if (V->isNullValue()) return ConstantFP::get(Type::DoubleTy, 0);
324    return 0;  // Can't const prop other types of pointers
325  }
326
327  static ConstantPointer *CastToPointer(const ConstantPointer *V,
328                                        const PointerType *PTy) {
329    if (V->getType() == PTy)
330      return const_cast<ConstantPointer*>(V);  // Allow cast %PTy %ptr to %PTy
331    if (V->isNullValue())
332      return ConstantPointerNull::get(PTy);
333    return 0;  // Can't const prop other types of pointers
334  }
335};
336
337
338//===----------------------------------------------------------------------===//
339//                             DirectRules Class
340//===----------------------------------------------------------------------===//
341//
342// DirectRules provides a concrete base classes of ConstRules for a variety of
343// different types.  This allows the C++ compiler to automatically generate our
344// constant handling operations in a typesafe and accurate manner.
345//
346template<class ConstantClass, class BuiltinType, Type **Ty, class SuperClass>
347struct DirectRules : public TemplateRules<ConstantClass, SuperClass> {
348  static Constant *Add(const ConstantClass *V1, const ConstantClass *V2) {
349    BuiltinType R = (BuiltinType)V1->getValue() + (BuiltinType)V2->getValue();
350    return ConstantClass::get(*Ty, R);
351  }
352
353  static Constant *Sub(const ConstantClass *V1, const ConstantClass *V2) {
354    BuiltinType R = (BuiltinType)V1->getValue() - (BuiltinType)V2->getValue();
355    return ConstantClass::get(*Ty, R);
356  }
357
358  static Constant *Mul(const ConstantClass *V1, const ConstantClass *V2) {
359    BuiltinType R = (BuiltinType)V1->getValue() * (BuiltinType)V2->getValue();
360    return ConstantClass::get(*Ty, R);
361  }
362
363  static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) {
364    if (V2->isNullValue()) return 0;
365    BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue();
366    return ConstantClass::get(*Ty, R);
367  }
368
369  static ConstantBool *LessThan(const ConstantClass *V1,
370                                const ConstantClass *V2) {
371    bool R = (BuiltinType)V1->getValue() < (BuiltinType)V2->getValue();
372    return ConstantBool::get(R);
373  }
374
375  static ConstantPointer *CastToPointer(const ConstantClass *V,
376                                        const PointerType *PTy) {
377    if (V->isNullValue())    // Is it a FP or Integral null value?
378      return ConstantPointerNull::get(PTy);
379    return 0;  // Can't const prop other types of pointers
380  }
381
382  // Casting operators.  ick
383#define DEF_CAST(TYPE, CLASS, CTYPE) \
384  static CLASS *CastTo##TYPE  (const ConstantClass *V) {    \
385    return CLASS::get(Type::TYPE##Ty, (CTYPE)(BuiltinType)V->getValue()); \
386  }
387
388  DEF_CAST(Bool  , ConstantBool, bool)
389  DEF_CAST(SByte , ConstantSInt, signed char)
390  DEF_CAST(UByte , ConstantUInt, unsigned char)
391  DEF_CAST(Short , ConstantSInt, signed short)
392  DEF_CAST(UShort, ConstantUInt, unsigned short)
393  DEF_CAST(Int   , ConstantSInt, signed int)
394  DEF_CAST(UInt  , ConstantUInt, unsigned int)
395  DEF_CAST(Long  , ConstantSInt, int64_t)
396  DEF_CAST(ULong , ConstantUInt, uint64_t)
397  DEF_CAST(Float , ConstantFP  , float)
398  DEF_CAST(Double, ConstantFP  , double)
399#undef DEF_CAST
400};
401
402
403//===----------------------------------------------------------------------===//
404//                           DirectIntRules Class
405//===----------------------------------------------------------------------===//
406//
407// DirectIntRules provides implementations of functions that are valid on
408// integer types, but not all types in general.
409//
410template <class ConstantClass, class BuiltinType, Type **Ty>
411struct DirectIntRules
412  : public DirectRules<ConstantClass, BuiltinType, Ty,
413                       DirectIntRules<ConstantClass, BuiltinType, Ty> > {
414
415  static Constant *Rem(const ConstantClass *V1,
416                       const ConstantClass *V2) {
417    if (V2->isNullValue()) return 0;
418    BuiltinType R = (BuiltinType)V1->getValue() % (BuiltinType)V2->getValue();
419    return ConstantClass::get(*Ty, R);
420  }
421
422  static Constant *And(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 *Or(const ConstantClass *V1, const ConstantClass *V2) {
427    BuiltinType R = (BuiltinType)V1->getValue() | (BuiltinType)V2->getValue();
428    return ConstantClass::get(*Ty, R);
429  }
430  static Constant *Xor(const ConstantClass *V1, const ConstantClass *V2) {
431    BuiltinType R = (BuiltinType)V1->getValue() ^ (BuiltinType)V2->getValue();
432    return ConstantClass::get(*Ty, R);
433  }
434
435  static Constant *Shl(const ConstantClass *V1, const ConstantClass *V2) {
436    BuiltinType R = (BuiltinType)V1->getValue() << (BuiltinType)V2->getValue();
437    return ConstantClass::get(*Ty, R);
438  }
439
440  static Constant *Shr(const ConstantClass *V1, const ConstantClass *V2) {
441    BuiltinType R = (BuiltinType)V1->getValue() >> (BuiltinType)V2->getValue();
442    return ConstantClass::get(*Ty, R);
443  }
444};
445
446
447//===----------------------------------------------------------------------===//
448//                           DirectFPRules Class
449//===----------------------------------------------------------------------===//
450//
451// DirectFPRules provides implementations of functions that are valid on
452// floating point types, but not all types in general.
453//
454template <class ConstantClass, class BuiltinType, Type **Ty>
455struct DirectFPRules
456  : public DirectRules<ConstantClass, BuiltinType, Ty,
457                       DirectFPRules<ConstantClass, BuiltinType, Ty> > {
458  static Constant *Rem(const ConstantClass *V1, const ConstantClass *V2) {
459    if (V2->isNullValue()) return 0;
460    BuiltinType Result = std::fmod((BuiltinType)V1->getValue(),
461                                   (BuiltinType)V2->getValue());
462    return ConstantClass::get(*Ty, Result);
463  }
464};
465
466
467//===----------------------------------------------------------------------===//
468//                            DirectRules Subclasses
469//===----------------------------------------------------------------------===//
470//
471// Given the DirectRules class we can now implement lots of types with little
472// code.  Thank goodness C++ compilers are great at stomping out layers of
473// templates... can you imagine having to do this all by hand? (/me is lazy :)
474//
475
476// ConstRules::find - Return the constant rules that take care of the specified
477// type.
478//
479Annotation *ConstRules::find(AnnotationID AID, const Annotable *TyA, void *) {
480  assert(AID == ConstRules::AID && "Bad annotation for factory!");
481  const Type *Ty = cast<Type>((const Value*)TyA);
482
483  switch (Ty->getPrimitiveID()) {
484  case Type::BoolTyID:    return new BoolRules();
485  case Type::PointerTyID: return new PointerRules();
486  case Type::SByteTyID:
487    return new DirectIntRules<ConstantSInt,   signed char , &Type::SByteTy>();
488  case Type::UByteTyID:
489    return new DirectIntRules<ConstantUInt, unsigned char , &Type::UByteTy>();
490  case Type::ShortTyID:
491    return new DirectIntRules<ConstantSInt,   signed short, &Type::ShortTy>();
492  case Type::UShortTyID:
493    return new DirectIntRules<ConstantUInt, unsigned short, &Type::UShortTy>();
494  case Type::IntTyID:
495    return new DirectIntRules<ConstantSInt,   signed int  , &Type::IntTy>();
496  case Type::UIntTyID:
497    return new DirectIntRules<ConstantUInt, unsigned int  , &Type::UIntTy>();
498  case Type::LongTyID:
499    return new DirectIntRules<ConstantSInt,  int64_t      , &Type::LongTy>();
500  case Type::ULongTyID:
501    return new DirectIntRules<ConstantUInt, uint64_t      , &Type::ULongTy>();
502  case Type::FloatTyID:
503    return new DirectFPRules<ConstantFP  , float         , &Type::FloatTy>();
504  case Type::DoubleTyID:
505    return new DirectFPRules<ConstantFP  , double        , &Type::DoubleTy>();
506  default:
507    return new EmptyRules();
508  }
509}
510