ConstantFold.cpp revision 2e9bb1a88e806644e96b2a73bf8c2eb540d68ede 
1//===- ConstantFolding.cpp - LLVM constant folder -------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by the LLVM research group and is distributed under
6// the University of Illinois Open Source License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements folding of constants for LLVM.  This implements the
11// (internal) ConstantFolding.h interface, which is used by the
12// ConstantExpr::get* methods to automatically fold constants when possible.
13//
14// The current constant folding implementation is implemented in two pieces: the
15// template-based folder for simple primitive constants like ConstantInt, and
16// the special case hackery that we use to symbolically evaluate expressions
17// that use ConstantExprs.
18//
19//===----------------------------------------------------------------------===//
20
21#include "ConstantFolding.h"
22#include "llvm/Constants.h"
23#include "llvm/iPHINode.h"
24#include "llvm/iOperators.h"
25#include "llvm/InstrTypes.h"
26#include "llvm/DerivedTypes.h"
27#include "llvm/Support/GetElementPtrTypeIterator.h"
28#include <cmath>
29using namespace llvm;
30
31namespace {
32  struct ConstRules {
33    ConstRules() {}
34
35    // Binary Operators...
36    virtual Constant *add(const Constant *V1, const Constant *V2) const = 0;
37    virtual Constant *sub(const Constant *V1, const Constant *V2) const = 0;
38    virtual Constant *mul(const Constant *V1, const Constant *V2) const = 0;
39    virtual Constant *div(const Constant *V1, const Constant *V2) const = 0;
40    virtual Constant *rem(const Constant *V1, const Constant *V2) const = 0;
41    virtual Constant *op_and(const Constant *V1, const Constant *V2) const = 0;
42    virtual Constant *op_or (const Constant *V1, const Constant *V2) const = 0;
43    virtual Constant *op_xor(const Constant *V1, const Constant *V2) const = 0;
44    virtual Constant *shl(const Constant *V1, const Constant *V2) const = 0;
45    virtual Constant *shr(const Constant *V1, const Constant *V2) const = 0;
46    virtual Constant *lessthan(const Constant *V1, const Constant *V2) const =0;
47    virtual Constant *equalto(const Constant *V1, const Constant *V2) const = 0;
48
49    // Casting operators.
50    virtual Constant *castToBool  (const Constant *V) const = 0;
51    virtual Constant *castToSByte (const Constant *V) const = 0;
52    virtual Constant *castToUByte (const Constant *V) const = 0;
53    virtual Constant *castToShort (const Constant *V) const = 0;
54    virtual Constant *castToUShort(const Constant *V) const = 0;
55    virtual Constant *castToInt   (const Constant *V) const = 0;
56    virtual Constant *castToUInt  (const Constant *V) const = 0;
57    virtual Constant *castToLong  (const Constant *V) const = 0;
58    virtual Constant *castToULong (const Constant *V) const = 0;
59    virtual Constant *castToFloat (const Constant *V) const = 0;
60    virtual Constant *castToDouble(const Constant *V) const = 0;
61    virtual Constant *castToPointer(const Constant *V,
62                                    const PointerType *Ty) const = 0;
63
64    // ConstRules::get - Return an instance of ConstRules for the specified
65    // constant operands.
66    //
67    static ConstRules &get(const Constant *V1, const Constant *V2);
68  private:
69    ConstRules(const ConstRules &);             // Do not implement
70    ConstRules &operator=(const ConstRules &);  // Do not implement
71  };
72}
73
74
75//===----------------------------------------------------------------------===//
76//                             TemplateRules Class
77//===----------------------------------------------------------------------===//
78//
79// TemplateRules - Implement a subclass of ConstRules that provides all
80// operations as noops.  All other rules classes inherit from this class so
81// that if functionality is needed in the future, it can simply be added here
82// and to ConstRules without changing anything else...
83//
84// This class also provides subclasses with typesafe implementations of methods
85// so that don't have to do type casting.
86//
87template<class ArgType, class SubClassName>
88class TemplateRules : public ConstRules {
89
90  //===--------------------------------------------------------------------===//
91  // Redirecting functions that cast to the appropriate types
92  //===--------------------------------------------------------------------===//
93
94  virtual Constant *add(const Constant *V1, const Constant *V2) const {
95    return SubClassName::Add((const ArgType *)V1, (const ArgType *)V2);
96  }
97  virtual Constant *sub(const Constant *V1, const Constant *V2) const {
98    return SubClassName::Sub((const ArgType *)V1, (const ArgType *)V2);
99  }
100  virtual Constant *mul(const Constant *V1, const Constant *V2) const {
101    return SubClassName::Mul((const ArgType *)V1, (const ArgType *)V2);
102  }
103  virtual Constant *div(const Constant *V1, const Constant *V2) const {
104    return SubClassName::Div((const ArgType *)V1, (const ArgType *)V2);
105  }
106  virtual Constant *rem(const Constant *V1, const Constant *V2) const {
107    return SubClassName::Rem((const ArgType *)V1, (const ArgType *)V2);
108  }
109  virtual Constant *op_and(const Constant *V1, const Constant *V2) const {
110    return SubClassName::And((const ArgType *)V1, (const ArgType *)V2);
111  }
112  virtual Constant *op_or(const Constant *V1, const Constant *V2) const {
113    return SubClassName::Or((const ArgType *)V1, (const ArgType *)V2);
114  }
115  virtual Constant *op_xor(const Constant *V1, const Constant *V2) const {
116    return SubClassName::Xor((const ArgType *)V1, (const ArgType *)V2);
117  }
118  virtual Constant *shl(const Constant *V1, const Constant *V2) const {
119    return SubClassName::Shl((const ArgType *)V1, (const ArgType *)V2);
120  }
121  virtual Constant *shr(const Constant *V1, const Constant *V2) const {
122    return SubClassName::Shr((const ArgType *)V1, (const ArgType *)V2);
123  }
124
125  virtual Constant *lessthan(const Constant *V1, const Constant *V2) const {
126    return SubClassName::LessThan((const ArgType *)V1, (const ArgType *)V2);
127  }
128  virtual Constant *equalto(const Constant *V1, const Constant *V2) const {
129    return SubClassName::EqualTo((const ArgType *)V1, (const ArgType *)V2);
130  }
131
132  // Casting operators.  ick
133  virtual Constant *castToBool(const Constant *V) const {
134    return SubClassName::CastToBool((const ArgType*)V);
135  }
136  virtual Constant *castToSByte(const Constant *V) const {
137    return SubClassName::CastToSByte((const ArgType*)V);
138  }
139  virtual Constant *castToUByte(const Constant *V) const {
140    return SubClassName::CastToUByte((const ArgType*)V);
141  }
142  virtual Constant *castToShort(const Constant *V) const {
143    return SubClassName::CastToShort((const ArgType*)V);
144  }
145  virtual Constant *castToUShort(const Constant *V) const {
146    return SubClassName::CastToUShort((const ArgType*)V);
147  }
148  virtual Constant *castToInt(const Constant *V) const {
149    return SubClassName::CastToInt((const ArgType*)V);
150  }
151  virtual Constant *castToUInt(const Constant *V) const {
152    return SubClassName::CastToUInt((const ArgType*)V);
153  }
154  virtual Constant *castToLong(const Constant *V) const {
155    return SubClassName::CastToLong((const ArgType*)V);
156  }
157  virtual Constant *castToULong(const Constant *V) const {
158    return SubClassName::CastToULong((const ArgType*)V);
159  }
160  virtual Constant *castToFloat(const Constant *V) const {
161    return SubClassName::CastToFloat((const ArgType*)V);
162  }
163  virtual Constant *castToDouble(const Constant *V) const {
164    return SubClassName::CastToDouble((const ArgType*)V);
165  }
166  virtual Constant *castToPointer(const Constant *V,
167                                  const PointerType *Ty) const {
168    return SubClassName::CastToPointer((const ArgType*)V, Ty);
169  }
170
171  //===--------------------------------------------------------------------===//
172  // Default "noop" implementations
173  //===--------------------------------------------------------------------===//
174
175  static Constant *Add(const ArgType *V1, const ArgType *V2) { return 0; }
176  static Constant *Sub(const ArgType *V1, const ArgType *V2) { return 0; }
177  static Constant *Mul(const ArgType *V1, const ArgType *V2) { return 0; }
178  static Constant *Div(const ArgType *V1, const ArgType *V2) { return 0; }
179  static Constant *Rem(const ArgType *V1, const ArgType *V2) { return 0; }
180  static Constant *And(const ArgType *V1, const ArgType *V2) { return 0; }
181  static Constant *Or (const ArgType *V1, const ArgType *V2) { return 0; }
182  static Constant *Xor(const ArgType *V1, const ArgType *V2) { return 0; }
183  static Constant *Shl(const ArgType *V1, const ArgType *V2) { return 0; }
184  static Constant *Shr(const ArgType *V1, const ArgType *V2) { return 0; }
185  static Constant *LessThan(const ArgType *V1, const ArgType *V2) {
186    return 0;
187  }
188  static Constant *EqualTo(const ArgType *V1, const ArgType *V2) {
189    return 0;
190  }
191
192  // Casting operators.  ick
193  static Constant *CastToBool  (const Constant *V) { return 0; }
194  static Constant *CastToSByte (const Constant *V) { return 0; }
195  static Constant *CastToUByte (const Constant *V) { return 0; }
196  static Constant *CastToShort (const Constant *V) { return 0; }
197  static Constant *CastToUShort(const Constant *V) { return 0; }
198  static Constant *CastToInt   (const Constant *V) { return 0; }
199  static Constant *CastToUInt  (const Constant *V) { return 0; }
200  static Constant *CastToLong  (const Constant *V) { return 0; }
201  static Constant *CastToULong (const Constant *V) { return 0; }
202  static Constant *CastToFloat (const Constant *V) { return 0; }
203  static Constant *CastToDouble(const Constant *V) { return 0; }
204  static Constant *CastToPointer(const Constant *,
205                                 const PointerType *) {return 0;}
206};
207
208
209
210//===----------------------------------------------------------------------===//
211//                             EmptyRules Class
212//===----------------------------------------------------------------------===//
213//
214// EmptyRules provides a concrete base class of ConstRules that does nothing
215//
216struct EmptyRules : public TemplateRules<Constant, EmptyRules> {
217  static Constant *EqualTo(const Constant *V1, const Constant *V2) {
218    if (V1 == V2) return ConstantBool::True;
219    return 0;
220  }
221};
222
223
224
225//===----------------------------------------------------------------------===//
226//                              BoolRules Class
227//===----------------------------------------------------------------------===//
228//
229// BoolRules provides a concrete base class of ConstRules for the 'bool' type.
230//
231struct BoolRules : public TemplateRules<ConstantBool, BoolRules> {
232
233  static Constant *LessThan(const ConstantBool *V1, const ConstantBool *V2){
234    return ConstantBool::get(V1->getValue() < V2->getValue());
235  }
236
237  static Constant *EqualTo(const Constant *V1, const Constant *V2) {
238    return ConstantBool::get(V1 == V2);
239  }
240
241  static Constant *And(const ConstantBool *V1, const ConstantBool *V2) {
242    return ConstantBool::get(V1->getValue() & V2->getValue());
243  }
244
245  static Constant *Or(const ConstantBool *V1, const ConstantBool *V2) {
246    return ConstantBool::get(V1->getValue() | V2->getValue());
247  }
248
249  static Constant *Xor(const ConstantBool *V1, const ConstantBool *V2) {
250    return ConstantBool::get(V1->getValue() ^ V2->getValue());
251  }
252
253  // Casting operators.  ick
254#define DEF_CAST(TYPE, CLASS, CTYPE) \
255  static Constant *CastTo##TYPE  (const ConstantBool *V) {    \
256    return CLASS::get(Type::TYPE##Ty, (CTYPE)(bool)V->getValue()); \
257  }
258
259  DEF_CAST(Bool  , ConstantBool, bool)
260  DEF_CAST(SByte , ConstantSInt, signed char)
261  DEF_CAST(UByte , ConstantUInt, unsigned char)
262  DEF_CAST(Short , ConstantSInt, signed short)
263  DEF_CAST(UShort, ConstantUInt, unsigned short)
264  DEF_CAST(Int   , ConstantSInt, signed int)
265  DEF_CAST(UInt  , ConstantUInt, unsigned int)
266  DEF_CAST(Long  , ConstantSInt, int64_t)
267  DEF_CAST(ULong , ConstantUInt, uint64_t)
268  DEF_CAST(Float , ConstantFP  , float)
269  DEF_CAST(Double, ConstantFP  , double)
270#undef DEF_CAST
271};
272
273
274//===----------------------------------------------------------------------===//
275//                            NullPointerRules Class
276//===----------------------------------------------------------------------===//
277//
278// NullPointerRules provides a concrete base class of ConstRules for null
279// pointers.
280//
281struct NullPointerRules : public TemplateRules<ConstantPointerNull,
282                                               NullPointerRules> {
283  static Constant *EqualTo(const Constant *V1, const Constant *V2) {
284    return ConstantBool::True;  // Null pointers are always equal
285  }
286  static Constant *CastToBool(const Constant *V) {
287    return ConstantBool::False;
288  }
289  static Constant *CastToSByte (const Constant *V) {
290    return ConstantSInt::get(Type::SByteTy, 0);
291  }
292  static Constant *CastToUByte (const Constant *V) {
293    return ConstantUInt::get(Type::UByteTy, 0);
294  }
295  static Constant *CastToShort (const Constant *V) {
296    return ConstantSInt::get(Type::ShortTy, 0);
297  }
298  static Constant *CastToUShort(const Constant *V) {
299    return ConstantUInt::get(Type::UShortTy, 0);
300  }
301  static Constant *CastToInt   (const Constant *V) {
302    return ConstantSInt::get(Type::IntTy, 0);
303  }
304  static Constant *CastToUInt  (const Constant *V) {
305    return ConstantUInt::get(Type::UIntTy, 0);
306  }
307  static Constant *CastToLong  (const Constant *V) {
308    return ConstantSInt::get(Type::LongTy, 0);
309  }
310  static Constant *CastToULong (const Constant *V) {
311    return ConstantUInt::get(Type::ULongTy, 0);
312  }
313  static Constant *CastToFloat (const Constant *V) {
314    return ConstantFP::get(Type::FloatTy, 0);
315  }
316  static Constant *CastToDouble(const Constant *V) {
317    return ConstantFP::get(Type::DoubleTy, 0);
318  }
319
320  static Constant *CastToPointer(const ConstantPointerNull *V,
321                                 const PointerType *PTy) {
322    return ConstantPointerNull::get(PTy);
323  }
324};
325
326
327//===----------------------------------------------------------------------===//
328//                             DirectRules Class
329//===----------------------------------------------------------------------===//
330//
331// DirectRules provides a concrete base classes of ConstRules for a variety of
332// different types.  This allows the C++ compiler to automatically generate our
333// constant handling operations in a typesafe and accurate manner.
334//
335template<class ConstantClass, class BuiltinType, Type **Ty, class SuperClass>
336struct DirectRules : public TemplateRules<ConstantClass, SuperClass> {
337  static Constant *Add(const ConstantClass *V1, const ConstantClass *V2) {
338    BuiltinType R = (BuiltinType)V1->getValue() + (BuiltinType)V2->getValue();
339    return ConstantClass::get(*Ty, R);
340  }
341
342  static Constant *Sub(const ConstantClass *V1, const ConstantClass *V2) {
343    BuiltinType R = (BuiltinType)V1->getValue() - (BuiltinType)V2->getValue();
344    return ConstantClass::get(*Ty, R);
345  }
346
347  static Constant *Mul(const ConstantClass *V1, const ConstantClass *V2) {
348    BuiltinType R = (BuiltinType)V1->getValue() * (BuiltinType)V2->getValue();
349    return ConstantClass::get(*Ty, R);
350  }
351
352  static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) {
353    if (V2->isNullValue()) return 0;
354    BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue();
355    return ConstantClass::get(*Ty, R);
356  }
357
358  static Constant *LessThan(const ConstantClass *V1, const ConstantClass *V2) {
359    bool R = (BuiltinType)V1->getValue() < (BuiltinType)V2->getValue();
360    return ConstantBool::get(R);
361  }
362
363  static Constant *EqualTo(const ConstantClass *V1, const ConstantClass *V2) {
364    bool R = (BuiltinType)V1->getValue() == (BuiltinType)V2->getValue();
365    return ConstantBool::get(R);
366  }
367
368  static Constant *CastToPointer(const ConstantClass *V,
369                                 const PointerType *PTy) {
370    if (V->isNullValue())    // Is it a FP or Integral null value?
371      return ConstantPointerNull::get(PTy);
372    return 0;  // Can't const prop other types of pointers
373  }
374
375  // Casting operators.  ick
376#define DEF_CAST(TYPE, CLASS, CTYPE) \
377  static Constant *CastTo##TYPE  (const ConstantClass *V) {    \
378    return CLASS::get(Type::TYPE##Ty, (CTYPE)(BuiltinType)V->getValue()); \
379  }
380
381  DEF_CAST(Bool  , ConstantBool, bool)
382  DEF_CAST(SByte , ConstantSInt, signed char)
383  DEF_CAST(UByte , ConstantUInt, unsigned char)
384  DEF_CAST(Short , ConstantSInt, signed short)
385  DEF_CAST(UShort, ConstantUInt, unsigned short)
386  DEF_CAST(Int   , ConstantSInt, signed int)
387  DEF_CAST(UInt  , ConstantUInt, unsigned int)
388  DEF_CAST(Long  , ConstantSInt, int64_t)
389  DEF_CAST(ULong , ConstantUInt, uint64_t)
390  DEF_CAST(Float , ConstantFP  , float)
391  DEF_CAST(Double, ConstantFP  , double)
392#undef DEF_CAST
393};
394
395
396//===----------------------------------------------------------------------===//
397//                           DirectIntRules Class
398//===----------------------------------------------------------------------===//
399//
400// DirectIntRules provides implementations of functions that are valid on
401// integer types, but not all types in general.
402//
403template <class ConstantClass, class BuiltinType, Type **Ty>
404struct DirectIntRules
405  : public DirectRules<ConstantClass, BuiltinType, Ty,
406                       DirectIntRules<ConstantClass, BuiltinType, Ty> > {
407
408  static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) {
409    if (V2->isNullValue()) return 0;
410    if (V2->isAllOnesValue() &&              // MIN_INT / -1
411        (BuiltinType)V1->getValue() == -(BuiltinType)V1->getValue())
412      return 0;
413    BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue();
414    return ConstantClass::get(*Ty, R);
415  }
416
417  static Constant *Rem(const ConstantClass *V1,
418                       const ConstantClass *V2) {
419    if (V2->isNullValue()) return 0;         // X / 0
420    if (V2->isAllOnesValue() &&              // MIN_INT / -1
421        (BuiltinType)V1->getValue() == -(BuiltinType)V1->getValue())
422      return 0;
423    BuiltinType R = (BuiltinType)V1->getValue() % (BuiltinType)V2->getValue();
424    return ConstantClass::get(*Ty, R);
425  }
426
427  static Constant *And(const ConstantClass *V1, const ConstantClass *V2) {
428    BuiltinType R = (BuiltinType)V1->getValue() & (BuiltinType)V2->getValue();
429    return ConstantClass::get(*Ty, R);
430  }
431  static Constant *Or(const ConstantClass *V1, const ConstantClass *V2) {
432    BuiltinType R = (BuiltinType)V1->getValue() | (BuiltinType)V2->getValue();
433    return ConstantClass::get(*Ty, R);
434  }
435  static Constant *Xor(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 *Shl(const ConstantClass *V1, const ConstantClass *V2) {
441    BuiltinType R = (BuiltinType)V1->getValue() << (BuiltinType)V2->getValue();
442    return ConstantClass::get(*Ty, R);
443  }
444
445  static Constant *Shr(const ConstantClass *V1, const ConstantClass *V2) {
446    BuiltinType R = (BuiltinType)V1->getValue() >> (BuiltinType)V2->getValue();
447    return ConstantClass::get(*Ty, R);
448  }
449};
450
451
452//===----------------------------------------------------------------------===//
453//                           DirectFPRules Class
454//===----------------------------------------------------------------------===//
455//
456/// DirectFPRules provides implementations of functions that are valid on
457/// floating point types, but not all types in general.
458///
459template <class ConstantClass, class BuiltinType, Type **Ty>
460struct DirectFPRules
461  : public DirectRules<ConstantClass, BuiltinType, Ty,
462                       DirectFPRules<ConstantClass, BuiltinType, Ty> > {
463  static Constant *Rem(const ConstantClass *V1, const ConstantClass *V2) {
464    if (V2->isNullValue()) return 0;
465    BuiltinType Result = std::fmod((BuiltinType)V1->getValue(),
466                                   (BuiltinType)V2->getValue());
467    return ConstantClass::get(*Ty, Result);
468  }
469};
470
471
472/// ConstRules::get - This method returns the constant rules implementation that
473/// implements the semantics of the two specified constants.
474ConstRules &ConstRules::get(const Constant *V1, const Constant *V2) {
475  static EmptyRules       EmptyR;
476  static BoolRules        BoolR;
477  static NullPointerRules NullPointerR;
478  static DirectIntRules<ConstantSInt,   signed char , &Type::SByteTy>  SByteR;
479  static DirectIntRules<ConstantUInt, unsigned char , &Type::UByteTy>  UByteR;
480  static DirectIntRules<ConstantSInt,   signed short, &Type::ShortTy>  ShortR;
481  static DirectIntRules<ConstantUInt, unsigned short, &Type::UShortTy> UShortR;
482  static DirectIntRules<ConstantSInt,   signed int  , &Type::IntTy>    IntR;
483  static DirectIntRules<ConstantUInt, unsigned int  , &Type::UIntTy>   UIntR;
484  static DirectIntRules<ConstantSInt,  int64_t      , &Type::LongTy>   LongR;
485  static DirectIntRules<ConstantUInt, uint64_t      , &Type::ULongTy>  ULongR;
486  static DirectFPRules <ConstantFP  , float         , &Type::FloatTy>  FloatR;
487  static DirectFPRules <ConstantFP  , double        , &Type::DoubleTy> DoubleR;
488
489  if (isa<ConstantExpr>(V1) || isa<ConstantExpr>(V2) ||
490      isa<ConstantPointerRef>(V1) || isa<ConstantPointerRef>(V2))
491    return EmptyR;
492
493  switch (V1->getType()->getPrimitiveID()) {
494  default: assert(0 && "Unknown value type for constant folding!");
495  case Type::BoolTyID:    return BoolR;
496  case Type::PointerTyID: return NullPointerR;
497  case Type::SByteTyID:   return SByteR;
498  case Type::UByteTyID:   return UByteR;
499  case Type::ShortTyID:   return ShortR;
500  case Type::UShortTyID:  return UShortR;
501  case Type::IntTyID:     return IntR;
502  case Type::UIntTyID:    return UIntR;
503  case Type::LongTyID:    return LongR;
504  case Type::ULongTyID:   return ULongR;
505  case Type::FloatTyID:   return FloatR;
506  case Type::DoubleTyID:  return DoubleR;
507  }
508}
509
510
511//===----------------------------------------------------------------------===//
512//                ConstantFold*Instruction Implementations
513//===----------------------------------------------------------------------===//
514//
515// These methods contain the special case hackery required to symbolically
516// evaluate some constant expression cases, and use the ConstantRules class to
517// evaluate normal constants.
518//
519static unsigned getSize(const Type *Ty) {
520  unsigned S = Ty->getPrimitiveSize();
521  return S ? S : 8;  // Treat pointers at 8 bytes
522}
523
524Constant *llvm::ConstantFoldCastInstruction(const Constant *V,
525                                            const Type *DestTy) {
526  if (V->getType() == DestTy) return (Constant*)V;
527
528  if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
529    if (CE->getOpcode() == Instruction::Cast) {
530      Constant *Op = const_cast<Constant*>(CE->getOperand(0));
531      // Try to not produce a cast of a cast, which is almost always redundant.
532      if (!Op->getType()->isFloatingPoint() &&
533          !CE->getType()->isFloatingPoint() &&
534          !DestTy->getType()->isFloatingPoint()) {
535        unsigned S1 = getSize(Op->getType()), S2 = getSize(CE->getType());
536        unsigned S3 = getSize(DestTy);
537        if (Op->getType() == DestTy && S3 >= S2)
538          return Op;
539        if (S1 >= S2 && S2 >= S3)
540          return ConstantExpr::getCast(Op, DestTy);
541        if (S1 <= S2 && S2 >= S3 && S1 <= S3)
542          return ConstantExpr::getCast(Op, DestTy);
543      }
544    } else if (CE->getOpcode() == Instruction::GetElementPtr) {
545      // If all of the indexes in the GEP are null values, there is no pointer
546      // adjustment going on.  We might as well cast the source pointer.
547      bool isAllNull = true;
548      for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
549        if (!CE->getOperand(i)->isNullValue()) {
550          isAllNull = false;
551          break;
552        }
553      if (isAllNull)
554        return ConstantExpr::getCast(CE->getOperand(0), DestTy);
555    }
556
557  ConstRules &Rules = ConstRules::get(V, V);
558
559  switch (DestTy->getPrimitiveID()) {
560  case Type::BoolTyID:    return Rules.castToBool(V);
561  case Type::UByteTyID:   return Rules.castToUByte(V);
562  case Type::SByteTyID:   return Rules.castToSByte(V);
563  case Type::UShortTyID:  return Rules.castToUShort(V);
564  case Type::ShortTyID:   return Rules.castToShort(V);
565  case Type::UIntTyID:    return Rules.castToUInt(V);
566  case Type::IntTyID:     return Rules.castToInt(V);
567  case Type::ULongTyID:   return Rules.castToULong(V);
568  case Type::LongTyID:    return Rules.castToLong(V);
569  case Type::FloatTyID:   return Rules.castToFloat(V);
570  case Type::DoubleTyID:  return Rules.castToDouble(V);
571  case Type::PointerTyID:
572    return Rules.castToPointer(V, cast<PointerType>(DestTy));
573  default: return 0;
574  }
575}
576
577/// IdxCompare - Compare the two constants as though they were getelementptr
578/// indices.  This allows coersion of the types to be the same thing.
579///
580/// If the two constants are the "same" (after coersion), return 0.  If the
581/// first is less than the second, return -1, if the second is less than the
582/// first, return 1.  If the constants are not integral, return -2.
583///
584static int IdxCompare(Constant *C1, Constant *C2) {
585  if (C1 == C2) return 0;
586
587  // Ok, we found a different index.  Are either of the operands
588  // ConstantExprs?  If so, we can't do anything with them.
589  if (!isa<ConstantInt>(C1) || !isa<ConstantInt>(C2))
590    return -2; // don't know!
591
592  // Ok, we have two differing integer indices.  Convert them to
593  // be the same type.  Long is always big enough, so we use it.
594  C1 = ConstantExpr::getCast(C1, Type::LongTy);
595  C2 = ConstantExpr::getCast(C2, Type::LongTy);
596  if (C1 == C2) return 0;  // Are they just differing types?
597
598  // If they are really different, now that they are the same type, then we
599  // found a difference!
600  if (cast<ConstantSInt>(C1)->getValue() < cast<ConstantSInt>(C2)->getValue())
601    return -1;
602  else
603    return 1;
604}
605
606/// evaluateRelation - This function determines if there is anything we can
607/// decide about the two constants provided.  This doesn't need to handle simple
608/// things like integer comparisons, but should instead handle ConstantExpr's
609/// and ConstantPointerRef's.  If we can determine that the two constants have a
610/// particular relation to each other, we should return the corresponding SetCC
611/// code, otherwise return Instruction::BinaryOpsEnd.
612///
613/// To simplify this code we canonicalize the relation so that the first
614/// operand is always the most "complex" of the two.  We consider simple
615/// constants (like ConstantInt) to be the simplest, followed by
616/// ConstantPointerRef's, followed by ConstantExpr's (the most complex).
617///
618static Instruction::BinaryOps evaluateRelation(const Constant *V1,
619                                               const Constant *V2) {
620  assert(V1->getType() == V2->getType() &&
621         "Cannot compare different types of values!");
622  if (V1 == V2) return Instruction::SetEQ;
623
624  if (!isa<ConstantExpr>(V1) && !isa<ConstantPointerRef>(V1)) {
625    // If the first operand is simple, swap operands.
626    assert((isa<ConstantPointerRef>(V2) || isa<ConstantExpr>(V2)) &&
627           "Simple cases should have been handled by caller!");
628    Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1);
629    if (SwappedRelation != Instruction::BinaryOpsEnd)
630      return SetCondInst::getSwappedCondition(SwappedRelation);
631
632  } else if (const ConstantPointerRef *CPR1 = dyn_cast<ConstantPointerRef>(V1)){
633    if (isa<ConstantExpr>(V2)) {  // Swap as necessary.
634    Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1);
635    if (SwappedRelation != Instruction::BinaryOpsEnd)
636      return SetCondInst::getSwappedCondition(SwappedRelation);
637    else
638      return Instruction::BinaryOpsEnd;
639    }
640
641    // Now we know that the RHS is a ConstantPointerRef or simple constant,
642    // which (since the types must match) means that it's a ConstantPointerNull.
643    if (const ConstantPointerRef *CPR2 = dyn_cast<ConstantPointerRef>(V2)) {
644      assert(CPR1->getValue() != CPR2->getValue() &&
645             "CPRs for the same value exist at different addresses??");
646      // FIXME: If both globals are external weak, they might both be null!
647      return Instruction::SetNE;
648    } else {
649      assert(isa<ConstantPointerNull>(V2) && "Canonicalization guarantee!");
650      // Global can never be null.  FIXME: if we implement external weak
651      // linkage, this is not necessarily true!
652      return Instruction::SetNE;
653    }
654
655  } else {
656    // Ok, the LHS is known to be a constantexpr.  The RHS can be any of a
657    // constantexpr, a CPR, or a simple constant.
658    const ConstantExpr *CE1 = cast<ConstantExpr>(V1);
659    Constant *CE1Op0 = CE1->getOperand(0);
660
661    switch (CE1->getOpcode()) {
662    case Instruction::Cast:
663      // If the cast is not actually changing bits, and the second operand is a
664      // null pointer, do the comparison with the pre-casted value.
665      if (V2->isNullValue() &&
666          CE1->getType()->isLosslesslyConvertibleTo(CE1Op0->getType()))
667        return evaluateRelation(CE1Op0,
668                                Constant::getNullValue(CE1Op0->getType()));
669
670    case Instruction::GetElementPtr:
671      // Ok, since this is a getelementptr, we know that the constant has a
672      // pointer type.  Check the various cases.
673      if (isa<ConstantPointerNull>(V2)) {
674        // If we are comparing a GEP to a null pointer, check to see if the base
675        // of the GEP equals the null pointer.
676        if (isa<ConstantPointerRef>(CE1Op0)) {
677          // FIXME: this is not true when we have external weak references!
678          // No offset can go from a global to a null pointer.
679          return Instruction::SetGT;
680        } else if (isa<ConstantPointerNull>(CE1Op0)) {
681          // If we are indexing from a null pointer, check to see if we have any
682          // non-zero indices.
683          for (unsigned i = 1, e = CE1->getNumOperands(); i != e; ++i)
684            if (!CE1->getOperand(i)->isNullValue())
685              // Offsetting from null, must not be equal.
686              return Instruction::SetGT;
687          // Only zero indexes from null, must still be zero.
688          return Instruction::SetEQ;
689        }
690        // Otherwise, we can't really say if the first operand is null or not.
691      } else if (const ConstantPointerRef *CPR2 =
692                                             dyn_cast<ConstantPointerRef>(V2)) {
693        if (isa<ConstantPointerNull>(CE1Op0)) {
694          // FIXME: This is not true with external weak references.
695          return Instruction::SetLT;
696        } else if (const ConstantPointerRef *CPR1 =
697                   dyn_cast<ConstantPointerRef>(CE1Op0)) {
698          if (CPR1 == CPR2) {
699            // If this is a getelementptr of the same global, then it must be
700            // different.  Because the types must match, the getelementptr could
701            // only have at most one index, and because we fold getelementptr's
702            // with a single zero index, it must be nonzero.
703            assert(CE1->getNumOperands() == 2 &&
704                   !CE1->getOperand(1)->isNullValue() &&
705                   "Suprising getelementptr!");
706            return Instruction::SetGT;
707          } else {
708            // If they are different globals, we don't know what the value is,
709            // but they can't be equal.
710            return Instruction::SetNE;
711          }
712        }
713      } else {
714        const ConstantExpr *CE2 = cast<ConstantExpr>(V2);
715        const Constant *CE2Op0 = CE2->getOperand(0);
716
717        // There are MANY other foldings that we could perform here.  They will
718        // probably be added on demand, as they seem needed.
719        switch (CE2->getOpcode()) {
720        default: break;
721        case Instruction::GetElementPtr:
722          // By far the most common case to handle is when the base pointers are
723          // obviously to the same or different globals.
724          if (isa<ConstantPointerRef>(CE1Op0) &&
725              isa<ConstantPointerRef>(CE2Op0)) {
726            if (CE1Op0 != CE2Op0) // Don't know relative ordering, but not equal
727              return Instruction::SetNE;
728            // Ok, we know that both getelementptr instructions are based on the
729            // same global.  From this, we can precisely determine the relative
730            // ordering of the resultant pointers.
731            unsigned i = 1;
732
733            // Compare all of the operands the GEP's have in common.
734            for (;i != CE1->getNumOperands() && i != CE2->getNumOperands(); ++i)
735              switch (IdxCompare(CE1->getOperand(i), CE2->getOperand(i))) {
736              case -1: return Instruction::SetLT;
737              case 1:  return Instruction::SetGT;
738              case -2: return Instruction::BinaryOpsEnd;
739              }
740
741            // Ok, we ran out of things they have in common.  If any leftovers
742            // are non-zero then we have a difference, otherwise we are equal.
743            for (; i < CE1->getNumOperands(); ++i)
744              if (!CE1->getOperand(i)->isNullValue())
745                return Instruction::SetGT;
746            for (; i < CE2->getNumOperands(); ++i)
747              if (!CE2->getOperand(i)->isNullValue())
748                return Instruction::SetLT;
749            return Instruction::SetEQ;
750          }
751        }
752      }
753
754    default:
755      break;
756    }
757  }
758
759  return Instruction::BinaryOpsEnd;
760}
761
762Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode,
763                                              const Constant *V1,
764                                              const Constant *V2) {
765  Constant *C = 0;
766  switch (Opcode) {
767  default:                   break;
768  case Instruction::Add:     C = ConstRules::get(V1, V2).add(V1, V2); break;
769  case Instruction::Sub:     C = ConstRules::get(V1, V2).sub(V1, V2); break;
770  case Instruction::Mul:     C = ConstRules::get(V1, V2).mul(V1, V2); break;
771  case Instruction::Div:     C = ConstRules::get(V1, V2).div(V1, V2); break;
772  case Instruction::Rem:     C = ConstRules::get(V1, V2).rem(V1, V2); break;
773  case Instruction::And:     C = ConstRules::get(V1, V2).op_and(V1, V2); break;
774  case Instruction::Or:      C = ConstRules::get(V1, V2).op_or (V1, V2); break;
775  case Instruction::Xor:     C = ConstRules::get(V1, V2).op_xor(V1, V2); break;
776  case Instruction::Shl:     C = ConstRules::get(V1, V2).shl(V1, V2); break;
777  case Instruction::Shr:     C = ConstRules::get(V1, V2).shr(V1, V2); break;
778  case Instruction::SetEQ:   C = ConstRules::get(V1, V2).equalto(V1, V2); break;
779  case Instruction::SetLT:   C = ConstRules::get(V1, V2).lessthan(V1, V2);break;
780  case Instruction::SetGT:   C = ConstRules::get(V1, V2).lessthan(V2, V1);break;
781  case Instruction::SetNE:   // V1 != V2  ===  !(V1 == V2)
782    C = ConstRules::get(V1, V2).equalto(V1, V2);
783    if (C) return ConstantExpr::get(Instruction::Xor, C, ConstantBool::True);
784    break;
785  case Instruction::SetLE:   // V1 <= V2  ===  !(V2 < V1)
786    C = ConstRules::get(V1, V2).lessthan(V2, V1);
787    if (C) return ConstantExpr::get(Instruction::Xor, C, ConstantBool::True);
788    break;
789  case Instruction::SetGE:   // V1 >= V2  ===  !(V1 < V2)
790    C = ConstRules::get(V1, V2).lessthan(V1, V2);
791    if (C) return ConstantExpr::get(Instruction::Xor, C, ConstantBool::True);
792    break;
793  }
794
795  // If we successfully folded the expression, return it now.
796  if (C) return C;
797
798  if (SetCondInst::isRelational(Opcode))
799    switch (evaluateRelation(V1, V2)) {
800    default: assert(0 && "Unknown relational!");
801    case Instruction::BinaryOpsEnd:
802      break;  // Couldn't determine anything about these constants.
803    case Instruction::SetEQ:   // We know the constants are equal!
804      // If we know the constants are equal, we can decide the result of this
805      // computation precisely.
806      return ConstantBool::get(Opcode == Instruction::SetEQ ||
807                               Opcode == Instruction::SetLE ||
808                               Opcode == Instruction::SetGE);
809    case Instruction::SetLT:
810      // If we know that V1 < V2, we can decide the result of this computation
811      // precisely.
812      return ConstantBool::get(Opcode == Instruction::SetLT ||
813                               Opcode == Instruction::SetNE ||
814                               Opcode == Instruction::SetLE);
815    case Instruction::SetGT:
816      // If we know that V1 > V2, we can decide the result of this computation
817      // precisely.
818      return ConstantBool::get(Opcode == Instruction::SetGT ||
819                               Opcode == Instruction::SetNE ||
820                               Opcode == Instruction::SetGE);
821    case Instruction::SetLE:
822      // If we know that V1 <= V2, we can only partially decide this relation.
823      if (Opcode == Instruction::SetGT) return ConstantBool::False;
824      if (Opcode == Instruction::SetLT) return ConstantBool::True;
825      break;
826
827    case Instruction::SetGE:
828      // If we know that V1 >= V2, we can only partially decide this relation.
829      if (Opcode == Instruction::SetLT) return ConstantBool::False;
830      if (Opcode == Instruction::SetGT) return ConstantBool::True;
831      break;
832
833    case Instruction::SetNE:
834      // If we know that V1 != V2, we can only partially decide this relation.
835      if (Opcode == Instruction::SetEQ) return ConstantBool::False;
836      if (Opcode == Instruction::SetNE) return ConstantBool::True;
837      break;
838    }
839
840  if (const ConstantExpr *CE1 = dyn_cast<ConstantExpr>(V1)) {
841    if (const ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2)) {
842      // There are many possible foldings we could do here.  We should probably
843      // at least fold add of a pointer with an integer into the appropriate
844      // getelementptr.  This will improve alias analysis a bit.
845
846
847
848
849    } else {
850      // Just implement a couple of simple identities.
851      switch (Opcode) {
852      case Instruction::Add:
853        if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X + 0 == X
854        break;
855      case Instruction::Sub:
856        if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X - 0 == X
857        break;
858      case Instruction::Mul:
859        if (V2->isNullValue()) return const_cast<Constant*>(V2);  // X * 0 == 0
860        if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
861          if (CI->getRawValue() == 1)
862            return const_cast<Constant*>(V1);                     // X * 1 == X
863        break;
864      case Instruction::Div:
865        if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
866          if (CI->getRawValue() == 1)
867            return const_cast<Constant*>(V1);                     // X / 1 == X
868        break;
869      case Instruction::Rem:
870        if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
871          if (CI->getRawValue() == 1)
872            return Constant::getNullValue(CI->getType()); // X % 1 == 0
873        break;
874      case Instruction::And:
875        if (cast<ConstantIntegral>(V2)->isAllOnesValue())
876          return const_cast<Constant*>(V1);                       // X & -1 == X
877        if (V2->isNullValue()) return const_cast<Constant*>(V2);  // X & 0 == 0
878        break;
879      case Instruction::Or:
880        if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X | 0 == X
881        if (cast<ConstantIntegral>(V2)->isAllOnesValue())
882          return const_cast<Constant*>(V2);  // X | -1 == -1
883        break;
884      case Instruction::Xor:
885        if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X ^ 0 == X
886        break;
887      }
888    }
889
890  } else if (const ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2)) {
891    // If V2 is a constant expr and V1 isn't, flop them around and fold the
892    // other way if possible.
893    switch (Opcode) {
894    case Instruction::Add:
895    case Instruction::Mul:
896    case Instruction::And:
897    case Instruction::Or:
898    case Instruction::Xor:
899    case Instruction::SetEQ:
900    case Instruction::SetNE:
901      // No change of opcode required.
902      return ConstantFoldBinaryInstruction(Opcode, V2, V1);
903
904    case Instruction::SetLT:
905    case Instruction::SetGT:
906    case Instruction::SetLE:
907    case Instruction::SetGE:
908      // Change the opcode as necessary to swap the operands.
909      Opcode = SetCondInst::getSwappedCondition((Instruction::BinaryOps)Opcode);
910      return ConstantFoldBinaryInstruction(Opcode, V2, V1);
911
912    case Instruction::Shl:
913    case Instruction::Shr:
914    case Instruction::Sub:
915    case Instruction::Div:
916    case Instruction::Rem:
917    default:  // These instructions cannot be flopped around.
918      break;
919    }
920  }
921  return 0;
922}
923
924Constant *llvm::ConstantFoldGetElementPtr(const Constant *C,
925                                        const std::vector<Constant*> &IdxList) {
926  if (IdxList.size() == 0 ||
927      (IdxList.size() == 1 && IdxList[0]->isNullValue()))
928    return const_cast<Constant*>(C);
929
930  if (C->isNullValue()) {
931    bool isNull = true;
932    for (unsigned i = 0, e = IdxList.size(); i != e; ++i)
933      if (!IdxList[i]->isNullValue()) {
934        isNull = false;
935        break;
936      }
937    if (isNull) {
938      std::vector<Value*> VIdxList(IdxList.begin(), IdxList.end());
939      const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), VIdxList,
940                                                         true);
941      assert(Ty != 0 && "Invalid indices for GEP!");
942      return ConstantPointerNull::get(PointerType::get(Ty));
943    }
944  }
945
946  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(const_cast<Constant*>(C))) {
947    // Combine Indices - If the source pointer to this getelementptr instruction
948    // is a getelementptr instruction, combine the indices of the two
949    // getelementptr instructions into a single instruction.
950    //
951    if (CE->getOpcode() == Instruction::GetElementPtr) {
952      const Type *LastTy = 0;
953      for (gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
954           I != E; ++I)
955        LastTy = *I;
956
957      if ((LastTy && isa<ArrayType>(LastTy)) || IdxList[0]->isNullValue()) {
958        std::vector<Constant*> NewIndices;
959        NewIndices.reserve(IdxList.size() + CE->getNumOperands());
960        for (unsigned i = 1, e = CE->getNumOperands()-1; i != e; ++i)
961          NewIndices.push_back(cast<Constant>(CE->getOperand(i)));
962
963        // Add the last index of the source with the first index of the new GEP.
964        // Make sure to handle the case when they are actually different types.
965        Constant *Combined = CE->getOperand(CE->getNumOperands()-1);
966        if (!IdxList[0]->isNullValue())   // Otherwise it must be an array
967          Combined =
968            ConstantExpr::get(Instruction::Add,
969                              ConstantExpr::getCast(IdxList[0], Type::LongTy),
970                              ConstantExpr::getCast(Combined, Type::LongTy));
971
972        NewIndices.push_back(Combined);
973        NewIndices.insert(NewIndices.end(), IdxList.begin()+1, IdxList.end());
974        return ConstantExpr::getGetElementPtr(CE->getOperand(0), NewIndices);
975      }
976    }
977
978    // Implement folding of:
979    //    int* getelementptr ([2 x int]* cast ([3 x int]* %X to [2 x int]*),
980    //                        long 0, long 0)
981    // To: int* getelementptr ([3 x int]* %X, long 0, long 0)
982    //
983    if (CE->getOpcode() == Instruction::Cast && IdxList.size() > 1 &&
984        IdxList[0]->isNullValue())
985      if (const PointerType *SPT =
986          dyn_cast<PointerType>(CE->getOperand(0)->getType()))
987        if (const ArrayType *SAT = dyn_cast<ArrayType>(SPT->getElementType()))
988          if (const ArrayType *CAT =
989              dyn_cast<ArrayType>(cast<PointerType>(C->getType())->getElementType()))
990            if (CAT->getElementType() == SAT->getElementType())
991              return ConstantExpr::getGetElementPtr(
992                      (Constant*)CE->getOperand(0), IdxList);
993  }
994  return 0;
995}
996
997