ConstantFold.cpp revision 2c822cce61d151e934ab5f95b9511be206b5ebce 
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/Instructions.h"
24#include "llvm/DerivedTypes.h"
25#include "llvm/Function.h"
26#include "llvm/Support/GetElementPtrTypeIterator.h"
27#include <limits>
28#include <cmath>
29using namespace llvm;
30
31namespace {
32  struct ConstRules {
33    ConstRules() {}
34    virtual ~ConstRules() {}
35
36    // Binary Operators...
37    virtual Constant *add(const Constant *V1, const Constant *V2) const = 0;
38    virtual Constant *sub(const Constant *V1, const Constant *V2) const = 0;
39    virtual Constant *mul(const Constant *V1, const Constant *V2) const = 0;
40    virtual Constant *div(const Constant *V1, const Constant *V2) const = 0;
41    virtual Constant *rem(const Constant *V1, const Constant *V2) const = 0;
42    virtual Constant *op_and(const Constant *V1, const Constant *V2) const = 0;
43    virtual Constant *op_or (const Constant *V1, const Constant *V2) const = 0;
44    virtual Constant *op_xor(const Constant *V1, const Constant *V2) const = 0;
45    virtual Constant *shl(const Constant *V1, const Constant *V2) const = 0;
46    virtual Constant *shr(const Constant *V1, const Constant *V2) const = 0;
47    virtual Constant *lessthan(const Constant *V1, const Constant *V2) const =0;
48    virtual Constant *equalto(const Constant *V1, const Constant *V2) const = 0;
49
50    // Casting operators.
51    virtual Constant *castToBool  (const Constant *V) const = 0;
52    virtual Constant *castToSByte (const Constant *V) const = 0;
53    virtual Constant *castToUByte (const Constant *V) const = 0;
54    virtual Constant *castToShort (const Constant *V) const = 0;
55    virtual Constant *castToUShort(const Constant *V) const = 0;
56    virtual Constant *castToInt   (const Constant *V) const = 0;
57    virtual Constant *castToUInt  (const Constant *V) const = 0;
58    virtual Constant *castToLong  (const Constant *V) const = 0;
59    virtual Constant *castToULong (const Constant *V) const = 0;
60    virtual Constant *castToFloat (const Constant *V) const = 0;
61    virtual Constant *castToDouble(const Constant *V) const = 0;
62    virtual Constant *castToPointer(const Constant *V,
63                                    const PointerType *Ty) const = 0;
64
65    // ConstRules::get - Return an instance of ConstRules for the specified
66    // constant operands.
67    //
68    static ConstRules &get(const Constant *V1, const Constant *V2);
69  private:
70    ConstRules(const ConstRules &);             // Do not implement
71    ConstRules &operator=(const ConstRules &);  // Do not implement
72  };
73}
74
75
76//===----------------------------------------------------------------------===//
77//                             TemplateRules Class
78//===----------------------------------------------------------------------===//
79//
80// TemplateRules - Implement a subclass of ConstRules that provides all
81// operations as noops.  All other rules classes inherit from this class so
82// that if functionality is needed in the future, it can simply be added here
83// and to ConstRules without changing anything else...
84//
85// This class also provides subclasses with typesafe implementations of methods
86// so that don't have to do type casting.
87//
88template<class ArgType, class SubClassName>
89class TemplateRules : public ConstRules {
90
91
92  //===--------------------------------------------------------------------===//
93  // Redirecting functions that cast to the appropriate types
94  //===--------------------------------------------------------------------===//
95
96  virtual Constant *add(const Constant *V1, const Constant *V2) const {
97    return SubClassName::Add((const ArgType *)V1, (const ArgType *)V2);
98  }
99  virtual Constant *sub(const Constant *V1, const Constant *V2) const {
100    return SubClassName::Sub((const ArgType *)V1, (const ArgType *)V2);
101  }
102  virtual Constant *mul(const Constant *V1, const Constant *V2) const {
103    return SubClassName::Mul((const ArgType *)V1, (const ArgType *)V2);
104  }
105  virtual Constant *div(const Constant *V1, const Constant *V2) const {
106    return SubClassName::Div((const ArgType *)V1, (const ArgType *)V2);
107  }
108  virtual Constant *rem(const Constant *V1, const Constant *V2) const {
109    return SubClassName::Rem((const ArgType *)V1, (const ArgType *)V2);
110  }
111  virtual Constant *op_and(const Constant *V1, const Constant *V2) const {
112    return SubClassName::And((const ArgType *)V1, (const ArgType *)V2);
113  }
114  virtual Constant *op_or(const Constant *V1, const Constant *V2) const {
115    return SubClassName::Or((const ArgType *)V1, (const ArgType *)V2);
116  }
117  virtual Constant *op_xor(const Constant *V1, const Constant *V2) const {
118    return SubClassName::Xor((const ArgType *)V1, (const ArgType *)V2);
119  }
120  virtual Constant *shl(const Constant *V1, const Constant *V2) const {
121    return SubClassName::Shl((const ArgType *)V1, (const ArgType *)V2);
122  }
123  virtual Constant *shr(const Constant *V1, const Constant *V2) const {
124    return SubClassName::Shr((const ArgType *)V1, (const ArgType *)V2);
125  }
126
127  virtual Constant *lessthan(const Constant *V1, const Constant *V2) const {
128    return SubClassName::LessThan((const ArgType *)V1, (const ArgType *)V2);
129  }
130  virtual Constant *equalto(const Constant *V1, const Constant *V2) const {
131    return SubClassName::EqualTo((const ArgType *)V1, (const ArgType *)V2);
132  }
133
134  // Casting operators.  ick
135  virtual Constant *castToBool(const Constant *V) const {
136    return SubClassName::CastToBool((const ArgType*)V);
137  }
138  virtual Constant *castToSByte(const Constant *V) const {
139    return SubClassName::CastToSByte((const ArgType*)V);
140  }
141  virtual Constant *castToUByte(const Constant *V) const {
142    return SubClassName::CastToUByte((const ArgType*)V);
143  }
144  virtual Constant *castToShort(const Constant *V) const {
145    return SubClassName::CastToShort((const ArgType*)V);
146  }
147  virtual Constant *castToUShort(const Constant *V) const {
148    return SubClassName::CastToUShort((const ArgType*)V);
149  }
150  virtual Constant *castToInt(const Constant *V) const {
151    return SubClassName::CastToInt((const ArgType*)V);
152  }
153  virtual Constant *castToUInt(const Constant *V) const {
154    return SubClassName::CastToUInt((const ArgType*)V);
155  }
156  virtual Constant *castToLong(const Constant *V) const {
157    return SubClassName::CastToLong((const ArgType*)V);
158  }
159  virtual Constant *castToULong(const Constant *V) const {
160    return SubClassName::CastToULong((const ArgType*)V);
161  }
162  virtual Constant *castToFloat(const Constant *V) const {
163    return SubClassName::CastToFloat((const ArgType*)V);
164  }
165  virtual Constant *castToDouble(const Constant *V) const {
166    return SubClassName::CastToDouble((const ArgType*)V);
167  }
168  virtual Constant *castToPointer(const Constant *V,
169                                  const PointerType *Ty) const {
170    return SubClassName::CastToPointer((const ArgType*)V, Ty);
171  }
172
173  //===--------------------------------------------------------------------===//
174  // Default "noop" implementations
175  //===--------------------------------------------------------------------===//
176
177  static Constant *Add(const ArgType *V1, const ArgType *V2) { return 0; }
178  static Constant *Sub(const ArgType *V1, const ArgType *V2) { return 0; }
179  static Constant *Mul(const ArgType *V1, const ArgType *V2) { return 0; }
180  static Constant *Div(const ArgType *V1, const ArgType *V2) { return 0; }
181  static Constant *Rem(const ArgType *V1, const ArgType *V2) { return 0; }
182  static Constant *And(const ArgType *V1, const ArgType *V2) { return 0; }
183  static Constant *Or (const ArgType *V1, const ArgType *V2) { return 0; }
184  static Constant *Xor(const ArgType *V1, const ArgType *V2) { return 0; }
185  static Constant *Shl(const ArgType *V1, const ArgType *V2) { return 0; }
186  static Constant *Shr(const ArgType *V1, const ArgType *V2) { return 0; }
187  static Constant *LessThan(const ArgType *V1, const ArgType *V2) {
188    return 0;
189  }
190  static Constant *EqualTo(const ArgType *V1, const ArgType *V2) {
191    return 0;
192  }
193
194  // Casting operators.  ick
195  static Constant *CastToBool  (const Constant *V) { return 0; }
196  static Constant *CastToSByte (const Constant *V) { return 0; }
197  static Constant *CastToUByte (const Constant *V) { return 0; }
198  static Constant *CastToShort (const Constant *V) { return 0; }
199  static Constant *CastToUShort(const Constant *V) { return 0; }
200  static Constant *CastToInt   (const Constant *V) { return 0; }
201  static Constant *CastToUInt  (const Constant *V) { return 0; }
202  static Constant *CastToLong  (const Constant *V) { return 0; }
203  static Constant *CastToULong (const Constant *V) { return 0; }
204  static Constant *CastToFloat (const Constant *V) { return 0; }
205  static Constant *CastToDouble(const Constant *V) { return 0; }
206  static Constant *CastToPointer(const Constant *,
207                                 const PointerType *) {return 0;}
208
209public:
210  virtual ~TemplateRules() {}
211};
212
213
214
215//===----------------------------------------------------------------------===//
216//                             EmptyRules Class
217//===----------------------------------------------------------------------===//
218//
219// EmptyRules provides a concrete base class of ConstRules that does nothing
220//
221struct EmptyRules : public TemplateRules<Constant, EmptyRules> {
222  static Constant *EqualTo(const Constant *V1, const Constant *V2) {
223    if (V1 == V2) return ConstantBool::True;
224    return 0;
225  }
226};
227
228
229
230//===----------------------------------------------------------------------===//
231//                              BoolRules Class
232//===----------------------------------------------------------------------===//
233//
234// BoolRules provides a concrete base class of ConstRules for the 'bool' type.
235//
236struct BoolRules : public TemplateRules<ConstantBool, BoolRules> {
237
238  static Constant *LessThan(const ConstantBool *V1, const ConstantBool *V2) {
239    return ConstantBool::get(V1->getValue() < V2->getValue());
240  }
241
242  static Constant *EqualTo(const Constant *V1, const Constant *V2) {
243    return ConstantBool::get(V1 == V2);
244  }
245
246  static Constant *And(const ConstantBool *V1, const ConstantBool *V2) {
247    return ConstantBool::get(V1->getValue() & V2->getValue());
248  }
249
250  static Constant *Or(const ConstantBool *V1, const ConstantBool *V2) {
251    return ConstantBool::get(V1->getValue() | V2->getValue());
252  }
253
254  static Constant *Xor(const ConstantBool *V1, const ConstantBool *V2) {
255    return ConstantBool::get(V1->getValue() ^ V2->getValue());
256  }
257
258  // Casting operators.  ick
259#define DEF_CAST(TYPE, CLASS, CTYPE) \
260  static Constant *CastTo##TYPE  (const ConstantBool *V) {    \
261    return CLASS::get(Type::TYPE##Ty, (CTYPE)(bool)V->getValue()); \
262  }
263
264  DEF_CAST(Bool  , ConstantBool, bool)
265  DEF_CAST(SByte , ConstantSInt, signed char)
266  DEF_CAST(UByte , ConstantUInt, unsigned char)
267  DEF_CAST(Short , ConstantSInt, signed short)
268  DEF_CAST(UShort, ConstantUInt, unsigned short)
269  DEF_CAST(Int   , ConstantSInt, signed int)
270  DEF_CAST(UInt  , ConstantUInt, unsigned int)
271  DEF_CAST(Long  , ConstantSInt, int64_t)
272  DEF_CAST(ULong , ConstantUInt, uint64_t)
273  DEF_CAST(Float , ConstantFP  , float)
274  DEF_CAST(Double, ConstantFP  , double)
275#undef DEF_CAST
276};
277
278
279//===----------------------------------------------------------------------===//
280//                            NullPointerRules Class
281//===----------------------------------------------------------------------===//
282//
283// NullPointerRules provides a concrete base class of ConstRules for null
284// pointers.
285//
286struct NullPointerRules : public TemplateRules<ConstantPointerNull,
287                                               NullPointerRules> {
288  static Constant *EqualTo(const Constant *V1, const Constant *V2) {
289    return ConstantBool::True;  // Null pointers are always equal
290  }
291  static Constant *CastToBool(const Constant *V) {
292    return ConstantBool::False;
293  }
294  static Constant *CastToSByte (const Constant *V) {
295    return ConstantSInt::get(Type::SByteTy, 0);
296  }
297  static Constant *CastToUByte (const Constant *V) {
298    return ConstantUInt::get(Type::UByteTy, 0);
299  }
300  static Constant *CastToShort (const Constant *V) {
301    return ConstantSInt::get(Type::ShortTy, 0);
302  }
303  static Constant *CastToUShort(const Constant *V) {
304    return ConstantUInt::get(Type::UShortTy, 0);
305  }
306  static Constant *CastToInt   (const Constant *V) {
307    return ConstantSInt::get(Type::IntTy, 0);
308  }
309  static Constant *CastToUInt  (const Constant *V) {
310    return ConstantUInt::get(Type::UIntTy, 0);
311  }
312  static Constant *CastToLong  (const Constant *V) {
313    return ConstantSInt::get(Type::LongTy, 0);
314  }
315  static Constant *CastToULong (const Constant *V) {
316    return ConstantUInt::get(Type::ULongTy, 0);
317  }
318  static Constant *CastToFloat (const Constant *V) {
319    return ConstantFP::get(Type::FloatTy, 0);
320  }
321  static Constant *CastToDouble(const Constant *V) {
322    return ConstantFP::get(Type::DoubleTy, 0);
323  }
324
325  static Constant *CastToPointer(const ConstantPointerNull *V,
326                                 const PointerType *PTy) {
327    return ConstantPointerNull::get(PTy);
328  }
329};
330
331//===----------------------------------------------------------------------===//
332//                          ConstantPackedRules Class
333//===----------------------------------------------------------------------===//
334
335/// DoVectorOp - Given two packed constants and a function pointer, apply the
336/// function pointer to each element pair, producing a new ConstantPacked
337/// constant.
338static Constant *EvalVectorOp(const ConstantPacked *V1,
339                              const ConstantPacked *V2,
340                              Constant *(*FP)(Constant*, Constant*)) {
341  std::vector<Constant*> Res;
342  for (unsigned i = 0, e = V1->getNumOperands(); i != e; ++i)
343    Res.push_back(FP(const_cast<Constant*>(V1->getOperand(i)),
344                     const_cast<Constant*>(V2->getOperand(i))));
345  return ConstantPacked::get(Res);
346}
347
348/// PackedTypeRules provides a concrete base class of ConstRules for
349/// ConstantPacked operands.
350///
351struct ConstantPackedRules
352  : public TemplateRules<ConstantPacked, ConstantPackedRules> {
353
354  static Constant *Add(const ConstantPacked *V1, const ConstantPacked *V2) {
355    return EvalVectorOp(V1, V2, ConstantExpr::getAdd);
356  }
357  static Constant *Sub(const ConstantPacked *V1, const ConstantPacked *V2) {
358    return EvalVectorOp(V1, V2, ConstantExpr::getSub);
359  }
360  static Constant *Mul(const ConstantPacked *V1, const ConstantPacked *V2) {
361    return EvalVectorOp(V1, V2, ConstantExpr::getMul);
362  }
363  static Constant *Div(const ConstantPacked *V1, const ConstantPacked *V2) {
364    return EvalVectorOp(V1, V2, ConstantExpr::getDiv);
365  }
366  static Constant *Rem(const ConstantPacked *V1, const ConstantPacked *V2) {
367    return EvalVectorOp(V1, V2, ConstantExpr::getRem);
368  }
369  static Constant *And(const ConstantPacked *V1, const ConstantPacked *V2) {
370    return EvalVectorOp(V1, V2, ConstantExpr::getAnd);
371  }
372  static Constant *Or (const ConstantPacked *V1, const ConstantPacked *V2) {
373    return EvalVectorOp(V1, V2, ConstantExpr::getOr);
374  }
375  static Constant *Xor(const ConstantPacked *V1, const ConstantPacked *V2) {
376    return EvalVectorOp(V1, V2, ConstantExpr::getXor);
377  }
378  static Constant *Shl(const ConstantPacked *V1, const ConstantPacked *V2) {
379    return EvalVectorOp(V1, V2, ConstantExpr::getShl);
380  }
381  static Constant *Shr(const ConstantPacked *V1, const ConstantPacked *V2) {
382    return EvalVectorOp(V1, V2, ConstantExpr::getShr);
383  }
384  static Constant *LessThan(const ConstantPacked *V1, const ConstantPacked *V2){
385    return 0;
386  }
387  static Constant *EqualTo(const ConstantPacked *V1, const ConstantPacked *V2) {
388    for (unsigned i = 0, e = V1->getNumOperands(); i != e; ++i) {
389      Constant *C =
390        ConstantExpr::getSetEQ(const_cast<Constant*>(V1->getOperand(i)),
391                               const_cast<Constant*>(V2->getOperand(i)));
392      if (ConstantBool *CB = dyn_cast<ConstantBool>(C))
393        return CB;
394    }
395    // Otherwise, could not decide from any element pairs.
396    return 0;
397  }
398};
399
400
401//===----------------------------------------------------------------------===//
402//                          GeneralPackedRules Class
403//===----------------------------------------------------------------------===//
404
405/// GeneralPackedRules provides a concrete base class of ConstRules for
406/// PackedType operands, where both operands are not ConstantPacked.  The usual
407/// cause for this is that one operand is a ConstantAggregateZero.
408///
409struct GeneralPackedRules : public TemplateRules<Constant, GeneralPackedRules> {
410};
411
412
413//===----------------------------------------------------------------------===//
414//                             DirectRules Class
415//===----------------------------------------------------------------------===//
416//
417// DirectRules provides a concrete base classes of ConstRules for a variety of
418// different types.  This allows the C++ compiler to automatically generate our
419// constant handling operations in a typesafe and accurate manner.
420//
421template<class ConstantClass, class BuiltinType, Type **Ty, class SuperClass>
422struct DirectRules : public TemplateRules<ConstantClass, SuperClass> {
423  static Constant *Add(const ConstantClass *V1, const ConstantClass *V2) {
424    BuiltinType R = (BuiltinType)V1->getValue() + (BuiltinType)V2->getValue();
425    return ConstantClass::get(*Ty, R);
426  }
427
428  static Constant *Sub(const ConstantClass *V1, const ConstantClass *V2) {
429    BuiltinType R = (BuiltinType)V1->getValue() - (BuiltinType)V2->getValue();
430    return ConstantClass::get(*Ty, R);
431  }
432
433  static Constant *Mul(const ConstantClass *V1, const ConstantClass *V2) {
434    BuiltinType R = (BuiltinType)V1->getValue() * (BuiltinType)V2->getValue();
435    return ConstantClass::get(*Ty, R);
436  }
437
438  static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) {
439    if (V2->isNullValue()) return 0;
440    BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue();
441    return ConstantClass::get(*Ty, R);
442  }
443
444  static Constant *LessThan(const ConstantClass *V1, const ConstantClass *V2) {
445    bool R = (BuiltinType)V1->getValue() < (BuiltinType)V2->getValue();
446    return ConstantBool::get(R);
447  }
448
449  static Constant *EqualTo(const ConstantClass *V1, const ConstantClass *V2) {
450    bool R = (BuiltinType)V1->getValue() == (BuiltinType)V2->getValue();
451    return ConstantBool::get(R);
452  }
453
454  static Constant *CastToPointer(const ConstantClass *V,
455                                 const PointerType *PTy) {
456    if (V->isNullValue())    // Is it a FP or Integral null value?
457      return ConstantPointerNull::get(PTy);
458    return 0;  // Can't const prop other types of pointers
459  }
460
461  // Casting operators.  ick
462#define DEF_CAST(TYPE, CLASS, CTYPE) \
463  static Constant *CastTo##TYPE  (const ConstantClass *V) {    \
464    return CLASS::get(Type::TYPE##Ty, (CTYPE)(BuiltinType)V->getValue()); \
465  }
466
467  DEF_CAST(Bool  , ConstantBool, bool)
468  DEF_CAST(SByte , ConstantSInt, signed char)
469  DEF_CAST(UByte , ConstantUInt, unsigned char)
470  DEF_CAST(Short , ConstantSInt, signed short)
471  DEF_CAST(UShort, ConstantUInt, unsigned short)
472  DEF_CAST(Int   , ConstantSInt, signed int)
473  DEF_CAST(UInt  , ConstantUInt, unsigned int)
474  DEF_CAST(Long  , ConstantSInt, int64_t)
475  DEF_CAST(ULong , ConstantUInt, uint64_t)
476  DEF_CAST(Float , ConstantFP  , float)
477  DEF_CAST(Double, ConstantFP  , double)
478#undef DEF_CAST
479};
480
481
482//===----------------------------------------------------------------------===//
483//                           DirectIntRules Class
484//===----------------------------------------------------------------------===//
485//
486// DirectIntRules provides implementations of functions that are valid on
487// integer types, but not all types in general.
488//
489template <class ConstantClass, class BuiltinType, Type **Ty>
490struct DirectIntRules
491  : public DirectRules<ConstantClass, BuiltinType, Ty,
492                       DirectIntRules<ConstantClass, BuiltinType, Ty> > {
493
494  static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) {
495    if (V2->isNullValue()) return 0;
496    if (V2->isAllOnesValue() &&              // MIN_INT / -1
497        (BuiltinType)V1->getValue() == -(BuiltinType)V1->getValue())
498      return 0;
499    BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue();
500    return ConstantClass::get(*Ty, R);
501  }
502
503  static Constant *Rem(const ConstantClass *V1,
504                       const ConstantClass *V2) {
505    if (V2->isNullValue()) return 0;         // X / 0
506    if (V2->isAllOnesValue() &&              // MIN_INT / -1
507        (BuiltinType)V1->getValue() == -(BuiltinType)V1->getValue())
508      return 0;
509    BuiltinType R = (BuiltinType)V1->getValue() % (BuiltinType)V2->getValue();
510    return ConstantClass::get(*Ty, R);
511  }
512
513  static Constant *And(const ConstantClass *V1, const ConstantClass *V2) {
514    BuiltinType R = (BuiltinType)V1->getValue() & (BuiltinType)V2->getValue();
515    return ConstantClass::get(*Ty, R);
516  }
517  static Constant *Or(const ConstantClass *V1, const ConstantClass *V2) {
518    BuiltinType R = (BuiltinType)V1->getValue() | (BuiltinType)V2->getValue();
519    return ConstantClass::get(*Ty, R);
520  }
521  static Constant *Xor(const ConstantClass *V1, const ConstantClass *V2) {
522    BuiltinType R = (BuiltinType)V1->getValue() ^ (BuiltinType)V2->getValue();
523    return ConstantClass::get(*Ty, R);
524  }
525
526  static Constant *Shl(const ConstantClass *V1, const ConstantClass *V2) {
527    BuiltinType R = (BuiltinType)V1->getValue() << (BuiltinType)V2->getValue();
528    return ConstantClass::get(*Ty, R);
529  }
530
531  static Constant *Shr(const ConstantClass *V1, const ConstantClass *V2) {
532    BuiltinType R = (BuiltinType)V1->getValue() >> (BuiltinType)V2->getValue();
533    return ConstantClass::get(*Ty, R);
534  }
535};
536
537
538//===----------------------------------------------------------------------===//
539//                           DirectFPRules Class
540//===----------------------------------------------------------------------===//
541//
542/// DirectFPRules provides implementations of functions that are valid on
543/// floating point types, but not all types in general.
544///
545template <class ConstantClass, class BuiltinType, Type **Ty>
546struct DirectFPRules
547  : public DirectRules<ConstantClass, BuiltinType, Ty,
548                       DirectFPRules<ConstantClass, BuiltinType, Ty> > {
549  static Constant *Rem(const ConstantClass *V1, const ConstantClass *V2) {
550    if (V2->isNullValue()) return 0;
551    BuiltinType Result = std::fmod((BuiltinType)V1->getValue(),
552                                   (BuiltinType)V2->getValue());
553    return ConstantClass::get(*Ty, Result);
554  }
555  static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) {
556    BuiltinType inf = std::numeric_limits<BuiltinType>::infinity();
557    if (V2->isExactlyValue(0.0)) return ConstantClass::get(*Ty, inf);
558    if (V2->isExactlyValue(-0.0)) return ConstantClass::get(*Ty, -inf);
559    BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue();
560    return ConstantClass::get(*Ty, R);
561  }
562};
563
564
565/// ConstRules::get - This method returns the constant rules implementation that
566/// implements the semantics of the two specified constants.
567ConstRules &ConstRules::get(const Constant *V1, const Constant *V2) {
568  static EmptyRules       EmptyR;
569  static BoolRules        BoolR;
570  static NullPointerRules NullPointerR;
571  static ConstantPackedRules ConstantPackedR;
572  static GeneralPackedRules GeneralPackedR;
573  static DirectIntRules<ConstantSInt,   signed char , &Type::SByteTy>  SByteR;
574  static DirectIntRules<ConstantUInt, unsigned char , &Type::UByteTy>  UByteR;
575  static DirectIntRules<ConstantSInt,   signed short, &Type::ShortTy>  ShortR;
576  static DirectIntRules<ConstantUInt, unsigned short, &Type::UShortTy> UShortR;
577  static DirectIntRules<ConstantSInt,   signed int  , &Type::IntTy>    IntR;
578  static DirectIntRules<ConstantUInt, unsigned int  , &Type::UIntTy>   UIntR;
579  static DirectIntRules<ConstantSInt,  int64_t      , &Type::LongTy>   LongR;
580  static DirectIntRules<ConstantUInt, uint64_t      , &Type::ULongTy>  ULongR;
581  static DirectFPRules <ConstantFP  , float         , &Type::FloatTy>  FloatR;
582  static DirectFPRules <ConstantFP  , double        , &Type::DoubleTy> DoubleR;
583
584  if (isa<ConstantExpr>(V1) || isa<ConstantExpr>(V2) ||
585      isa<GlobalValue>(V1) || isa<GlobalValue>(V2) ||
586      isa<UndefValue>(V1) || isa<UndefValue>(V2))
587    return EmptyR;
588
589  switch (V1->getType()->getTypeID()) {
590  default: assert(0 && "Unknown value type for constant folding!");
591  case Type::BoolTyID:    return BoolR;
592  case Type::PointerTyID: return NullPointerR;
593  case Type::SByteTyID:   return SByteR;
594  case Type::UByteTyID:   return UByteR;
595  case Type::ShortTyID:   return ShortR;
596  case Type::UShortTyID:  return UShortR;
597  case Type::IntTyID:     return IntR;
598  case Type::UIntTyID:    return UIntR;
599  case Type::LongTyID:    return LongR;
600  case Type::ULongTyID:   return ULongR;
601  case Type::FloatTyID:   return FloatR;
602  case Type::DoubleTyID:  return DoubleR;
603  case Type::PackedTyID:
604    if (isa<ConstantPacked>(V1) && isa<ConstantPacked>(V2))
605      return ConstantPackedR;
606    return GeneralPackedR;  // Constant folding rules for ConstantAggregateZero.
607  }
608}
609
610
611//===----------------------------------------------------------------------===//
612//                ConstantFold*Instruction Implementations
613//===----------------------------------------------------------------------===//
614//
615// These methods contain the special case hackery required to symbolically
616// evaluate some constant expression cases, and use the ConstantRules class to
617// evaluate normal constants.
618//
619static unsigned getSize(const Type *Ty) {
620  unsigned S = Ty->getPrimitiveSize();
621  return S ? S : 8;  // Treat pointers at 8 bytes
622}
623
624Constant *llvm::ConstantFoldCastInstruction(const Constant *V,
625                                            const Type *DestTy) {
626  if (V->getType() == DestTy) return (Constant*)V;
627
628  // Cast of a global address to boolean is always true.
629  if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
630    if (DestTy == Type::BoolTy)
631      // FIXME: When we support 'external weak' references, we have to prevent
632      // this transformation from happening.  This code will need to be updated
633      // to ignore external weak symbols when we support it.
634      return ConstantBool::True;
635  } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
636    if (CE->getOpcode() == Instruction::Cast) {
637      Constant *Op = const_cast<Constant*>(CE->getOperand(0));
638      // Try to not produce a cast of a cast, which is almost always redundant.
639      if (!Op->getType()->isFloatingPoint() &&
640          !CE->getType()->isFloatingPoint() &&
641          !DestTy->isFloatingPoint()) {
642        unsigned S1 = getSize(Op->getType()), S2 = getSize(CE->getType());
643        unsigned S3 = getSize(DestTy);
644        if (Op->getType() == DestTy && S3 >= S2)
645          return Op;
646        if (S1 >= S2 && S2 >= S3)
647          return ConstantExpr::getCast(Op, DestTy);
648        if (S1 <= S2 && S2 >= S3 && S1 <= S3)
649          return ConstantExpr::getCast(Op, DestTy);
650      }
651    } else if (CE->getOpcode() == Instruction::GetElementPtr) {
652      // If all of the indexes in the GEP are null values, there is no pointer
653      // adjustment going on.  We might as well cast the source pointer.
654      bool isAllNull = true;
655      for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
656        if (!CE->getOperand(i)->isNullValue()) {
657          isAllNull = false;
658          break;
659        }
660      if (isAllNull)
661        return ConstantExpr::getCast(CE->getOperand(0), DestTy);
662    }
663  } else if (isa<UndefValue>(V)) {
664    return UndefValue::get(DestTy);
665  }
666
667  // Check to see if we are casting an pointer to an aggregate to a pointer to
668  // the first element.  If so, return the appropriate GEP instruction.
669  if (const PointerType *PTy = dyn_cast<PointerType>(V->getType()))
670    if (const PointerType *DPTy = dyn_cast<PointerType>(DestTy)) {
671      std::vector<Value*> IdxList;
672      IdxList.push_back(Constant::getNullValue(Type::IntTy));
673      const Type *ElTy = PTy->getElementType();
674      while (ElTy != DPTy->getElementType()) {
675        if (const StructType *STy = dyn_cast<StructType>(ElTy)) {
676          if (STy->getNumElements() == 0) break;
677          ElTy = STy->getElementType(0);
678          IdxList.push_back(Constant::getNullValue(Type::UIntTy));
679        } else if (const SequentialType *STy = dyn_cast<SequentialType>(ElTy)) {
680          if (isa<PointerType>(ElTy)) break;  // Can't index into pointers!
681          ElTy = STy->getElementType();
682          IdxList.push_back(IdxList[0]);
683        } else {
684          break;
685        }
686      }
687
688      if (ElTy == DPTy->getElementType())
689        return ConstantExpr::getGetElementPtr(const_cast<Constant*>(V),IdxList);
690    }
691
692  ConstRules &Rules = ConstRules::get(V, V);
693
694  switch (DestTy->getTypeID()) {
695  case Type::BoolTyID:    return Rules.castToBool(V);
696  case Type::UByteTyID:   return Rules.castToUByte(V);
697  case Type::SByteTyID:   return Rules.castToSByte(V);
698  case Type::UShortTyID:  return Rules.castToUShort(V);
699  case Type::ShortTyID:   return Rules.castToShort(V);
700  case Type::UIntTyID:    return Rules.castToUInt(V);
701  case Type::IntTyID:     return Rules.castToInt(V);
702  case Type::ULongTyID:   return Rules.castToULong(V);
703  case Type::LongTyID:    return Rules.castToLong(V);
704  case Type::FloatTyID:   return Rules.castToFloat(V);
705  case Type::DoubleTyID:  return Rules.castToDouble(V);
706  case Type::PointerTyID:
707    return Rules.castToPointer(V, cast<PointerType>(DestTy));
708  default: return 0;
709  }
710}
711
712Constant *llvm::ConstantFoldSelectInstruction(const Constant *Cond,
713                                              const Constant *V1,
714                                              const Constant *V2) {
715  if (Cond == ConstantBool::True)
716    return const_cast<Constant*>(V1);
717  else if (Cond == ConstantBool::False)
718    return const_cast<Constant*>(V2);
719
720  if (isa<UndefValue>(V1)) return const_cast<Constant*>(V2);
721  if (isa<UndefValue>(V2)) return const_cast<Constant*>(V1);
722  if (isa<UndefValue>(Cond)) return const_cast<Constant*>(V1);
723  return 0;
724}
725
726/// isZeroSizedType - This type is zero sized if its an array or structure of
727/// zero sized types.  The only leaf zero sized type is an empty structure.
728static bool isMaybeZeroSizedType(const Type *Ty) {
729  if (isa<OpaqueType>(Ty)) return true;  // Can't say.
730  if (const StructType *STy = dyn_cast<StructType>(Ty)) {
731
732    // If all of elements have zero size, this does too.
733    for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
734      if (!isMaybeZeroSizedType(STy->getElementType(i))) return false;
735    return true;
736
737  } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
738    return isMaybeZeroSizedType(ATy->getElementType());
739  }
740  return false;
741}
742
743/// IdxCompare - Compare the two constants as though they were getelementptr
744/// indices.  This allows coersion of the types to be the same thing.
745///
746/// If the two constants are the "same" (after coersion), return 0.  If the
747/// first is less than the second, return -1, if the second is less than the
748/// first, return 1.  If the constants are not integral, return -2.
749///
750static int IdxCompare(Constant *C1, Constant *C2, const Type *ElTy) {
751  if (C1 == C2) return 0;
752
753  // Ok, we found a different index.  Are either of the operands
754  // ConstantExprs?  If so, we can't do anything with them.
755  if (!isa<ConstantInt>(C1) || !isa<ConstantInt>(C2))
756    return -2; // don't know!
757
758  // Ok, we have two differing integer indices.  Sign extend them to be the same
759  // type.  Long is always big enough, so we use it.
760  C1 = ConstantExpr::getSignExtend(C1, Type::LongTy);
761  C2 = ConstantExpr::getSignExtend(C2, Type::LongTy);
762  if (C1 == C2) return 0;  // Are they just differing types?
763
764  // If the type being indexed over is really just a zero sized type, there is
765  // no pointer difference being made here.
766  if (isMaybeZeroSizedType(ElTy))
767    return -2; // dunno.
768
769  // If they are really different, now that they are the same type, then we
770  // found a difference!
771  if (cast<ConstantSInt>(C1)->getValue() < cast<ConstantSInt>(C2)->getValue())
772    return -1;
773  else
774    return 1;
775}
776
777/// evaluateRelation - This function determines if there is anything we can
778/// decide about the two constants provided.  This doesn't need to handle simple
779/// things like integer comparisons, but should instead handle ConstantExprs
780/// and GlobalValuess.  If we can determine that the two constants have a
781/// particular relation to each other, we should return the corresponding SetCC
782/// code, otherwise return Instruction::BinaryOpsEnd.
783///
784/// To simplify this code we canonicalize the relation so that the first
785/// operand is always the most "complex" of the two.  We consider simple
786/// constants (like ConstantInt) to be the simplest, followed by
787/// GlobalValues, followed by ConstantExpr's (the most complex).
788///
789static Instruction::BinaryOps evaluateRelation(const Constant *V1,
790                                               const Constant *V2) {
791  assert(V1->getType() == V2->getType() &&
792         "Cannot compare different types of values!");
793  if (V1 == V2) return Instruction::SetEQ;
794
795  if (!isa<ConstantExpr>(V1) && !isa<GlobalValue>(V1)) {
796    // If the first operand is simple, swap operands.
797    assert((isa<GlobalValue>(V2) || isa<ConstantExpr>(V2)) &&
798           "Simple cases should have been handled by caller!");
799    Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1);
800    if (SwappedRelation != Instruction::BinaryOpsEnd)
801      return SetCondInst::getSwappedCondition(SwappedRelation);
802
803  } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(V1)) {
804    if (isa<ConstantExpr>(V2)) {  // Swap as necessary.
805      Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1);
806      if (SwappedRelation != Instruction::BinaryOpsEnd)
807        return SetCondInst::getSwappedCondition(SwappedRelation);
808      else
809        return Instruction::BinaryOpsEnd;
810    }
811
812    // Now we know that the RHS is a GlobalValue or simple constant,
813    // which (since the types must match) means that it's a ConstantPointerNull.
814    if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) {
815      assert(CPR1 != CPR2 &&
816             "GVs for the same value exist at different addresses??");
817      // FIXME: If both globals are external weak, they might both be null!
818      return Instruction::SetNE;
819    } else {
820      assert(isa<ConstantPointerNull>(V2) && "Canonicalization guarantee!");
821      // Global can never be null.  FIXME: if we implement external weak
822      // linkage, this is not necessarily true!
823      return Instruction::SetNE;
824    }
825
826  } else {
827    // Ok, the LHS is known to be a constantexpr.  The RHS can be any of a
828    // constantexpr, a CPR, or a simple constant.
829    const ConstantExpr *CE1 = cast<ConstantExpr>(V1);
830    Constant *CE1Op0 = CE1->getOperand(0);
831
832    switch (CE1->getOpcode()) {
833    case Instruction::Cast:
834      // If the cast is not actually changing bits, and the second operand is a
835      // null pointer, do the comparison with the pre-casted value.
836      if (V2->isNullValue() &&
837          CE1->getType()->isLosslesslyConvertibleTo(CE1Op0->getType()))
838        return evaluateRelation(CE1Op0,
839                                Constant::getNullValue(CE1Op0->getType()));
840      break;
841
842    case Instruction::GetElementPtr:
843      // Ok, since this is a getelementptr, we know that the constant has a
844      // pointer type.  Check the various cases.
845      if (isa<ConstantPointerNull>(V2)) {
846        // If we are comparing a GEP to a null pointer, check to see if the base
847        // of the GEP equals the null pointer.
848        if (isa<GlobalValue>(CE1Op0)) {
849          // FIXME: this is not true when we have external weak references!
850          // No offset can go from a global to a null pointer.
851          return Instruction::SetGT;
852        } else if (isa<ConstantPointerNull>(CE1Op0)) {
853          // If we are indexing from a null pointer, check to see if we have any
854          // non-zero indices.
855          for (unsigned i = 1, e = CE1->getNumOperands(); i != e; ++i)
856            if (!CE1->getOperand(i)->isNullValue())
857              // Offsetting from null, must not be equal.
858              return Instruction::SetGT;
859          // Only zero indexes from null, must still be zero.
860          return Instruction::SetEQ;
861        }
862        // Otherwise, we can't really say if the first operand is null or not.
863      } else if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) {
864        if (isa<ConstantPointerNull>(CE1Op0)) {
865          // FIXME: This is not true with external weak references.
866          return Instruction::SetLT;
867        } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(CE1Op0)) {
868          if (CPR1 == CPR2) {
869            // If this is a getelementptr of the same global, then it must be
870            // different.  Because the types must match, the getelementptr could
871            // only have at most one index, and because we fold getelementptr's
872            // with a single zero index, it must be nonzero.
873            assert(CE1->getNumOperands() == 2 &&
874                   !CE1->getOperand(1)->isNullValue() &&
875                   "Suprising getelementptr!");
876            return Instruction::SetGT;
877          } else {
878            // If they are different globals, we don't know what the value is,
879            // but they can't be equal.
880            return Instruction::SetNE;
881          }
882        }
883      } else {
884        const ConstantExpr *CE2 = cast<ConstantExpr>(V2);
885        const Constant *CE2Op0 = CE2->getOperand(0);
886
887        // There are MANY other foldings that we could perform here.  They will
888        // probably be added on demand, as they seem needed.
889        switch (CE2->getOpcode()) {
890        default: break;
891        case Instruction::GetElementPtr:
892          // By far the most common case to handle is when the base pointers are
893          // obviously to the same or different globals.
894          if (isa<GlobalValue>(CE1Op0) && isa<GlobalValue>(CE2Op0)) {
895            if (CE1Op0 != CE2Op0) // Don't know relative ordering, but not equal
896              return Instruction::SetNE;
897            // Ok, we know that both getelementptr instructions are based on the
898            // same global.  From this, we can precisely determine the relative
899            // ordering of the resultant pointers.
900            unsigned i = 1;
901
902            // Compare all of the operands the GEP's have in common.
903            gep_type_iterator GTI = gep_type_begin(CE1);
904            for (;i != CE1->getNumOperands() && i != CE2->getNumOperands();
905                 ++i, ++GTI)
906              switch (IdxCompare(CE1->getOperand(i), CE2->getOperand(i),
907                                 GTI.getIndexedType())) {
908              case -1: return Instruction::SetLT;
909              case 1:  return Instruction::SetGT;
910              case -2: return Instruction::BinaryOpsEnd;
911              }
912
913            // Ok, we ran out of things they have in common.  If any leftovers
914            // are non-zero then we have a difference, otherwise we are equal.
915            for (; i < CE1->getNumOperands(); ++i)
916              if (!CE1->getOperand(i)->isNullValue())
917                if (isa<ConstantIntegral>(CE1->getOperand(i)))
918                  return Instruction::SetGT;
919                else
920                  return Instruction::BinaryOpsEnd; // Might be equal.
921
922            for (; i < CE2->getNumOperands(); ++i)
923              if (!CE2->getOperand(i)->isNullValue())
924                if (isa<ConstantIntegral>(CE2->getOperand(i)))
925                  return Instruction::SetLT;
926                else
927                  return Instruction::BinaryOpsEnd; // Might be equal.
928            return Instruction::SetEQ;
929          }
930        }
931      }
932
933    default:
934      break;
935    }
936  }
937
938  return Instruction::BinaryOpsEnd;
939}
940
941Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode,
942                                              const Constant *V1,
943                                              const Constant *V2) {
944  Constant *C = 0;
945  switch (Opcode) {
946  default:                   break;
947  case Instruction::Add:     C = ConstRules::get(V1, V2).add(V1, V2); break;
948  case Instruction::Sub:     C = ConstRules::get(V1, V2).sub(V1, V2); break;
949  case Instruction::Mul:     C = ConstRules::get(V1, V2).mul(V1, V2); break;
950  case Instruction::Div:     C = ConstRules::get(V1, V2).div(V1, V2); break;
951  case Instruction::Rem:     C = ConstRules::get(V1, V2).rem(V1, V2); break;
952  case Instruction::And:     C = ConstRules::get(V1, V2).op_and(V1, V2); break;
953  case Instruction::Or:      C = ConstRules::get(V1, V2).op_or (V1, V2); break;
954  case Instruction::Xor:     C = ConstRules::get(V1, V2).op_xor(V1, V2); break;
955  case Instruction::Shl:     C = ConstRules::get(V1, V2).shl(V1, V2); break;
956  case Instruction::Shr:     C = ConstRules::get(V1, V2).shr(V1, V2); break;
957  case Instruction::SetEQ:   C = ConstRules::get(V1, V2).equalto(V1, V2); break;
958  case Instruction::SetLT:   C = ConstRules::get(V1, V2).lessthan(V1, V2);break;
959  case Instruction::SetGT:   C = ConstRules::get(V1, V2).lessthan(V2, V1);break;
960  case Instruction::SetNE:   // V1 != V2  ===  !(V1 == V2)
961    C = ConstRules::get(V1, V2).equalto(V1, V2);
962    if (C) return ConstantExpr::getNot(C);
963    break;
964  case Instruction::SetLE:   // V1 <= V2  ===  !(V2 < V1)
965    C = ConstRules::get(V1, V2).lessthan(V2, V1);
966    if (C) return ConstantExpr::getNot(C);
967    break;
968  case Instruction::SetGE:   // V1 >= V2  ===  !(V1 < V2)
969    C = ConstRules::get(V1, V2).lessthan(V1, V2);
970    if (C) return ConstantExpr::getNot(C);
971    break;
972  }
973
974  // If we successfully folded the expression, return it now.
975  if (C) return C;
976
977  if (SetCondInst::isRelational(Opcode)) {
978    if (isa<UndefValue>(V1) || isa<UndefValue>(V2))
979      return UndefValue::get(Type::BoolTy);
980    switch (evaluateRelation(V1, V2)) {
981    default: assert(0 && "Unknown relational!");
982    case Instruction::BinaryOpsEnd:
983      break;  // Couldn't determine anything about these constants.
984    case Instruction::SetEQ:   // We know the constants are equal!
985      // If we know the constants are equal, we can decide the result of this
986      // computation precisely.
987      return ConstantBool::get(Opcode == Instruction::SetEQ ||
988                               Opcode == Instruction::SetLE ||
989                               Opcode == Instruction::SetGE);
990    case Instruction::SetLT:
991      // If we know that V1 < V2, we can decide the result of this computation
992      // precisely.
993      return ConstantBool::get(Opcode == Instruction::SetLT ||
994                               Opcode == Instruction::SetNE ||
995                               Opcode == Instruction::SetLE);
996    case Instruction::SetGT:
997      // If we know that V1 > V2, we can decide the result of this computation
998      // precisely.
999      return ConstantBool::get(Opcode == Instruction::SetGT ||
1000                               Opcode == Instruction::SetNE ||
1001                               Opcode == Instruction::SetGE);
1002    case Instruction::SetLE:
1003      // If we know that V1 <= V2, we can only partially decide this relation.
1004      if (Opcode == Instruction::SetGT) return ConstantBool::False;
1005      if (Opcode == Instruction::SetLT) return ConstantBool::True;
1006      break;
1007
1008    case Instruction::SetGE:
1009      // If we know that V1 >= V2, we can only partially decide this relation.
1010      if (Opcode == Instruction::SetLT) return ConstantBool::False;
1011      if (Opcode == Instruction::SetGT) return ConstantBool::True;
1012      break;
1013
1014    case Instruction::SetNE:
1015      // If we know that V1 != V2, we can only partially decide this relation.
1016      if (Opcode == Instruction::SetEQ) return ConstantBool::False;
1017      if (Opcode == Instruction::SetNE) return ConstantBool::True;
1018      break;
1019    }
1020  }
1021
1022  if (isa<UndefValue>(V1) || isa<UndefValue>(V2)) {
1023    switch (Opcode) {
1024    case Instruction::Add:
1025    case Instruction::Sub:
1026    case Instruction::Xor:
1027      return UndefValue::get(V1->getType());
1028
1029    case Instruction::Mul:
1030    case Instruction::And:
1031      return Constant::getNullValue(V1->getType());
1032    case Instruction::Div:
1033    case Instruction::Rem:
1034      if (!isa<UndefValue>(V2))     // undef/X -> 0
1035        return Constant::getNullValue(V1->getType());
1036      return const_cast<Constant*>(V2);                // X/undef -> undef
1037    case Instruction::Or:           // X|undef -> -1
1038      return ConstantInt::getAllOnesValue(V1->getType());
1039    case Instruction::Shr:
1040      if (!isa<UndefValue>(V2)) {
1041        if (V1->getType()->isSigned())
1042          return const_cast<Constant*>(V1);  // undef >>s X -> undef
1043        // undef >>u X -> 0
1044      } else if (isa<UndefValue>(V1)) {
1045        return const_cast<Constant*>(V1);   //  undef >> undef -> undef
1046      } else {
1047        if (V1->getType()->isSigned())
1048          return const_cast<Constant*>(V1);  // X >>s undef -> X
1049        // X >>u undef -> 0
1050      }
1051      return Constant::getNullValue(V1->getType());
1052
1053    case Instruction::Shl:
1054      // undef << X -> 0   X << undef -> 0
1055      return Constant::getNullValue(V1->getType());
1056    }
1057  }
1058
1059  if (const ConstantExpr *CE1 = dyn_cast<ConstantExpr>(V1)) {
1060    if (const ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2)) {
1061      // There are many possible foldings we could do here.  We should probably
1062      // at least fold add of a pointer with an integer into the appropriate
1063      // getelementptr.  This will improve alias analysis a bit.
1064
1065
1066
1067
1068    } else {
1069      // Just implement a couple of simple identities.
1070      switch (Opcode) {
1071      case Instruction::Add:
1072        if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X + 0 == X
1073        break;
1074      case Instruction::Sub:
1075        if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X - 0 == X
1076        break;
1077      case Instruction::Mul:
1078        if (V2->isNullValue()) return const_cast<Constant*>(V2);  // X * 0 == 0
1079        if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1080          if (CI->getRawValue() == 1)
1081            return const_cast<Constant*>(V1);                     // X * 1 == X
1082        break;
1083      case Instruction::Div:
1084        if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1085          if (CI->getRawValue() == 1)
1086            return const_cast<Constant*>(V1);                     // X / 1 == X
1087        break;
1088      case Instruction::Rem:
1089        if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1090          if (CI->getRawValue() == 1)
1091            return Constant::getNullValue(CI->getType()); // X % 1 == 0
1092        break;
1093      case Instruction::And:
1094        if (cast<ConstantIntegral>(V2)->isAllOnesValue())
1095          return const_cast<Constant*>(V1);                       // X & -1 == X
1096        if (V2->isNullValue()) return const_cast<Constant*>(V2);  // X & 0 == 0
1097        if (CE1->getOpcode() == Instruction::Cast &&
1098            isa<GlobalValue>(CE1->getOperand(0))) {
1099          GlobalValue *CPR = cast<GlobalValue>(CE1->getOperand(0));
1100
1101          // Functions are at least 4-byte aligned.  If and'ing the address of a
1102          // function with a constant < 4, fold it to zero.
1103          if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1104            if (CI->getRawValue() < 4 && isa<Function>(CPR))
1105              return Constant::getNullValue(CI->getType());
1106        }
1107        break;
1108      case Instruction::Or:
1109        if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X | 0 == X
1110        if (cast<ConstantIntegral>(V2)->isAllOnesValue())
1111          return const_cast<Constant*>(V2);  // X | -1 == -1
1112        break;
1113      case Instruction::Xor:
1114        if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X ^ 0 == X
1115        break;
1116      }
1117    }
1118
1119  } else if (const ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2)) {
1120    // If V2 is a constant expr and V1 isn't, flop them around and fold the
1121    // other way if possible.
1122    switch (Opcode) {
1123    case Instruction::Add:
1124    case Instruction::Mul:
1125    case Instruction::And:
1126    case Instruction::Or:
1127    case Instruction::Xor:
1128    case Instruction::SetEQ:
1129    case Instruction::SetNE:
1130      // No change of opcode required.
1131      return ConstantFoldBinaryInstruction(Opcode, V2, V1);
1132
1133    case Instruction::SetLT:
1134    case Instruction::SetGT:
1135    case Instruction::SetLE:
1136    case Instruction::SetGE:
1137      // Change the opcode as necessary to swap the operands.
1138      Opcode = SetCondInst::getSwappedCondition((Instruction::BinaryOps)Opcode);
1139      return ConstantFoldBinaryInstruction(Opcode, V2, V1);
1140
1141    case Instruction::Shl:
1142    case Instruction::Shr:
1143    case Instruction::Sub:
1144    case Instruction::Div:
1145    case Instruction::Rem:
1146    default:  // These instructions cannot be flopped around.
1147      break;
1148    }
1149  }
1150  return 0;
1151}
1152
1153Constant *llvm::ConstantFoldGetElementPtr(const Constant *C,
1154                                          const std::vector<Value*> &IdxList) {
1155  if (IdxList.size() == 0 ||
1156      (IdxList.size() == 1 && cast<Constant>(IdxList[0])->isNullValue()))
1157    return const_cast<Constant*>(C);
1158
1159  if (isa<UndefValue>(C)) {
1160    const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList,
1161                                                       true);
1162    assert(Ty != 0 && "Invalid indices for GEP!");
1163    return UndefValue::get(PointerType::get(Ty));
1164  }
1165
1166  Constant *Idx0 = cast<Constant>(IdxList[0]);
1167  if (C->isNullValue()) {
1168    bool isNull = true;
1169    for (unsigned i = 0, e = IdxList.size(); i != e; ++i)
1170      if (!cast<Constant>(IdxList[i])->isNullValue()) {
1171        isNull = false;
1172        break;
1173      }
1174    if (isNull) {
1175      const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList,
1176                                                         true);
1177      assert(Ty != 0 && "Invalid indices for GEP!");
1178      return ConstantPointerNull::get(PointerType::get(Ty));
1179    }
1180
1181    if (IdxList.size() == 1) {
1182      const Type *ElTy = cast<PointerType>(C->getType())->getElementType();
1183      if (unsigned ElSize = ElTy->getPrimitiveSize()) {
1184        // gep null, C is equal to C*sizeof(nullty).  If nullty is a known llvm
1185        // type, we can statically fold this.
1186        Constant *R = ConstantUInt::get(Type::UIntTy, ElSize);
1187        R = ConstantExpr::getCast(R, Idx0->getType());
1188        R = ConstantExpr::getMul(R, Idx0);
1189        return ConstantExpr::getCast(R, C->getType());
1190      }
1191    }
1192  }
1193
1194  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(const_cast<Constant*>(C))) {
1195    // Combine Indices - If the source pointer to this getelementptr instruction
1196    // is a getelementptr instruction, combine the indices of the two
1197    // getelementptr instructions into a single instruction.
1198    //
1199    if (CE->getOpcode() == Instruction::GetElementPtr) {
1200      const Type *LastTy = 0;
1201      for (gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
1202           I != E; ++I)
1203        LastTy = *I;
1204
1205      if ((LastTy && isa<ArrayType>(LastTy)) || Idx0->isNullValue()) {
1206        std::vector<Value*> NewIndices;
1207        NewIndices.reserve(IdxList.size() + CE->getNumOperands());
1208        for (unsigned i = 1, e = CE->getNumOperands()-1; i != e; ++i)
1209          NewIndices.push_back(CE->getOperand(i));
1210
1211        // Add the last index of the source with the first index of the new GEP.
1212        // Make sure to handle the case when they are actually different types.
1213        Constant *Combined = CE->getOperand(CE->getNumOperands()-1);
1214        // Otherwise it must be an array.
1215        if (!Idx0->isNullValue()) {
1216          const Type *IdxTy = Combined->getType();
1217          if (IdxTy != Idx0->getType()) IdxTy = Type::LongTy;
1218          Combined =
1219            ConstantExpr::get(Instruction::Add,
1220                              ConstantExpr::getCast(Idx0, IdxTy),
1221                              ConstantExpr::getCast(Combined, IdxTy));
1222        }
1223
1224        NewIndices.push_back(Combined);
1225        NewIndices.insert(NewIndices.end(), IdxList.begin()+1, IdxList.end());
1226        return ConstantExpr::getGetElementPtr(CE->getOperand(0), NewIndices);
1227      }
1228    }
1229
1230    // Implement folding of:
1231    //    int* getelementptr ([2 x int]* cast ([3 x int]* %X to [2 x int]*),
1232    //                        long 0, long 0)
1233    // To: int* getelementptr ([3 x int]* %X, long 0, long 0)
1234    //
1235    if (CE->getOpcode() == Instruction::Cast && IdxList.size() > 1 &&
1236        Idx0->isNullValue())
1237      if (const PointerType *SPT =
1238          dyn_cast<PointerType>(CE->getOperand(0)->getType()))
1239        if (const ArrayType *SAT = dyn_cast<ArrayType>(SPT->getElementType()))
1240          if (const ArrayType *CAT =
1241              dyn_cast<ArrayType>(cast<PointerType>(C->getType())->getElementType()))
1242            if (CAT->getElementType() == SAT->getElementType())
1243              return ConstantExpr::getGetElementPtr(
1244                      (Constant*)CE->getOperand(0), IdxList);
1245  }
1246  return 0;
1247}
1248
1249