Use -Wl,-x instead of -s: it is more portable, and in particular,
[oota-llvm.git] / 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 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 //
281 struct 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 //
346 template<class ConstantClass, class BuiltinType, Type **Ty, class SuperClass>
347 struct 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 //
410 template <class ConstantClass, class BuiltinType, Type **Ty>
411 struct 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 //
454 template <class ConstantClass, class BuiltinType, Type **Ty>
455 struct 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 //
479 Annotation *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 }