ConstantFold.cpp revision fdf15e1dc8f1c4cb48a16eb20c536072ca7188fd 
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/Compiler.h"
27#include "llvm/Support/GetElementPtrTypeIterator.h"
28#include "llvm/Support/ManagedStatic.h"
29#include "llvm/Support/MathExtras.h"
30#include <limits>
31using namespace llvm;
32
33namespace {
34  struct VISIBILITY_HIDDEN ConstRules {
35    ConstRules() {}
36    virtual ~ConstRules() {}
37
38    // Binary Operators...
39    virtual Constant *add(const Constant *V1, const Constant *V2) const = 0;
40    virtual Constant *sub(const Constant *V1, const Constant *V2) const = 0;
41    virtual Constant *mul(const Constant *V1, const Constant *V2) const = 0;
42    virtual Constant *urem(const Constant *V1, const Constant *V2) const = 0;
43    virtual Constant *srem(const Constant *V1, const Constant *V2) const = 0;
44    virtual Constant *frem(const Constant *V1, const Constant *V2) const = 0;
45    virtual Constant *udiv(const Constant *V1, const Constant *V2) const = 0;
46    virtual Constant *sdiv(const Constant *V1, const Constant *V2) const = 0;
47    virtual Constant *fdiv(const Constant *V1, const Constant *V2) const = 0;
48    virtual Constant *op_and(const Constant *V1, const Constant *V2) const = 0;
49    virtual Constant *op_or (const Constant *V1, const Constant *V2) const = 0;
50    virtual Constant *op_xor(const Constant *V1, const Constant *V2) const = 0;
51    virtual Constant *shl(const Constant *V1, const Constant *V2) const = 0;
52    virtual Constant *lshr(const Constant *V1, const Constant *V2) const = 0;
53    virtual Constant *ashr(const Constant *V1, const Constant *V2) const = 0;
54    virtual Constant *lessthan(const Constant *V1, const Constant *V2) const =0;
55    virtual Constant *equalto(const Constant *V1, const Constant *V2) const = 0;
56
57    // Casting operators.
58    virtual Constant *castToBool  (const Constant *V) const = 0;
59    virtual Constant *castToSByte (const Constant *V) const = 0;
60    virtual Constant *castToUByte (const Constant *V) const = 0;
61    virtual Constant *castToShort (const Constant *V) const = 0;
62    virtual Constant *castToUShort(const Constant *V) const = 0;
63    virtual Constant *castToInt   (const Constant *V) const = 0;
64    virtual Constant *castToUInt  (const Constant *V) const = 0;
65    virtual Constant *castToLong  (const Constant *V) const = 0;
66    virtual Constant *castToULong (const Constant *V) const = 0;
67    virtual Constant *castToFloat (const Constant *V) const = 0;
68    virtual Constant *castToDouble(const Constant *V) const = 0;
69    virtual Constant *castToPointer(const Constant *V,
70                                    const PointerType *Ty) const = 0;
71
72    // ConstRules::get - Return an instance of ConstRules for the specified
73    // constant operands.
74    //
75    static ConstRules &get(const Constant *V1, const Constant *V2);
76  private:
77    ConstRules(const ConstRules &);             // Do not implement
78    ConstRules &operator=(const ConstRules &);  // Do not implement
79  };
80}
81
82
83//===----------------------------------------------------------------------===//
84//                             TemplateRules Class
85//===----------------------------------------------------------------------===//
86//
87// TemplateRules - Implement a subclass of ConstRules that provides all
88// operations as noops.  All other rules classes inherit from this class so
89// that if functionality is needed in the future, it can simply be added here
90// and to ConstRules without changing anything else...
91//
92// This class also provides subclasses with typesafe implementations of methods
93// so that don't have to do type casting.
94//
95namespace {
96template<class ArgType, class SubClassName>
97class VISIBILITY_HIDDEN TemplateRules : public ConstRules {
98
99
100  //===--------------------------------------------------------------------===//
101  // Redirecting functions that cast to the appropriate types
102  //===--------------------------------------------------------------------===//
103
104  virtual Constant *add(const Constant *V1, const Constant *V2) const {
105    return SubClassName::Add((const ArgType *)V1, (const ArgType *)V2);
106  }
107  virtual Constant *sub(const Constant *V1, const Constant *V2) const {
108    return SubClassName::Sub((const ArgType *)V1, (const ArgType *)V2);
109  }
110  virtual Constant *mul(const Constant *V1, const Constant *V2) const {
111    return SubClassName::Mul((const ArgType *)V1, (const ArgType *)V2);
112  }
113  virtual Constant *udiv(const Constant *V1, const Constant *V2) const {
114    return SubClassName::UDiv((const ArgType *)V1, (const ArgType *)V2);
115  }
116  virtual Constant *sdiv(const Constant *V1, const Constant *V2) const {
117    return SubClassName::SDiv((const ArgType *)V1, (const ArgType *)V2);
118  }
119  virtual Constant *fdiv(const Constant *V1, const Constant *V2) const {
120    return SubClassName::FDiv((const ArgType *)V1, (const ArgType *)V2);
121  }
122  virtual Constant *urem(const Constant *V1, const Constant *V2) const {
123    return SubClassName::URem((const ArgType *)V1, (const ArgType *)V2);
124  }
125  virtual Constant *srem(const Constant *V1, const Constant *V2) const {
126    return SubClassName::SRem((const ArgType *)V1, (const ArgType *)V2);
127  }
128  virtual Constant *frem(const Constant *V1, const Constant *V2) const {
129    return SubClassName::FRem((const ArgType *)V1, (const ArgType *)V2);
130  }
131  virtual Constant *op_and(const Constant *V1, const Constant *V2) const {
132    return SubClassName::And((const ArgType *)V1, (const ArgType *)V2);
133  }
134  virtual Constant *op_or(const Constant *V1, const Constant *V2) const {
135    return SubClassName::Or((const ArgType *)V1, (const ArgType *)V2);
136  }
137  virtual Constant *op_xor(const Constant *V1, const Constant *V2) const {
138    return SubClassName::Xor((const ArgType *)V1, (const ArgType *)V2);
139  }
140  virtual Constant *shl(const Constant *V1, const Constant *V2) const {
141    return SubClassName::Shl((const ArgType *)V1, (const ArgType *)V2);
142  }
143  virtual Constant *lshr(const Constant *V1, const Constant *V2) const {
144    return SubClassName::LShr((const ArgType *)V1, (const ArgType *)V2);
145  }
146  virtual Constant *ashr(const Constant *V1, const Constant *V2) const {
147    return SubClassName::AShr((const ArgType *)V1, (const ArgType *)V2);
148  }
149
150  virtual Constant *lessthan(const Constant *V1, const Constant *V2) const {
151    return SubClassName::LessThan((const ArgType *)V1, (const ArgType *)V2);
152  }
153  virtual Constant *equalto(const Constant *V1, const Constant *V2) const {
154    return SubClassName::EqualTo((const ArgType *)V1, (const ArgType *)V2);
155  }
156
157  // Casting operators.  ick
158  virtual Constant *castToBool(const Constant *V) const {
159    return SubClassName::CastToBool((const ArgType*)V);
160  }
161  virtual Constant *castToSByte(const Constant *V) const {
162    return SubClassName::CastToSByte((const ArgType*)V);
163  }
164  virtual Constant *castToUByte(const Constant *V) const {
165    return SubClassName::CastToUByte((const ArgType*)V);
166  }
167  virtual Constant *castToShort(const Constant *V) const {
168    return SubClassName::CastToShort((const ArgType*)V);
169  }
170  virtual Constant *castToUShort(const Constant *V) const {
171    return SubClassName::CastToUShort((const ArgType*)V);
172  }
173  virtual Constant *castToInt(const Constant *V) const {
174    return SubClassName::CastToInt((const ArgType*)V);
175  }
176  virtual Constant *castToUInt(const Constant *V) const {
177    return SubClassName::CastToUInt((const ArgType*)V);
178  }
179  virtual Constant *castToLong(const Constant *V) const {
180    return SubClassName::CastToLong((const ArgType*)V);
181  }
182  virtual Constant *castToULong(const Constant *V) const {
183    return SubClassName::CastToULong((const ArgType*)V);
184  }
185  virtual Constant *castToFloat(const Constant *V) const {
186    return SubClassName::CastToFloat((const ArgType*)V);
187  }
188  virtual Constant *castToDouble(const Constant *V) const {
189    return SubClassName::CastToDouble((const ArgType*)V);
190  }
191  virtual Constant *castToPointer(const Constant *V,
192                                  const PointerType *Ty) const {
193    return SubClassName::CastToPointer((const ArgType*)V, Ty);
194  }
195
196  //===--------------------------------------------------------------------===//
197  // Default "noop" implementations
198  //===--------------------------------------------------------------------===//
199
200  static Constant *Add (const ArgType *V1, const ArgType *V2) { return 0; }
201  static Constant *Sub (const ArgType *V1, const ArgType *V2) { return 0; }
202  static Constant *Mul (const ArgType *V1, const ArgType *V2) { return 0; }
203  static Constant *SDiv(const ArgType *V1, const ArgType *V2) { return 0; }
204  static Constant *UDiv(const ArgType *V1, const ArgType *V2) { return 0; }
205  static Constant *FDiv(const ArgType *V1, const ArgType *V2) { return 0; }
206  static Constant *URem(const ArgType *V1, const ArgType *V2) { return 0; }
207  static Constant *SRem(const ArgType *V1, const ArgType *V2) { return 0; }
208  static Constant *FRem(const ArgType *V1, const ArgType *V2) { return 0; }
209  static Constant *And (const ArgType *V1, const ArgType *V2) { return 0; }
210  static Constant *Or  (const ArgType *V1, const ArgType *V2) { return 0; }
211  static Constant *Xor (const ArgType *V1, const ArgType *V2) { return 0; }
212  static Constant *Shl (const ArgType *V1, const ArgType *V2) { return 0; }
213  static Constant *LShr(const ArgType *V1, const ArgType *V2) { return 0; }
214  static Constant *AShr(const ArgType *V1, const ArgType *V2) { return 0; }
215  static Constant *LessThan(const ArgType *V1, const ArgType *V2) {
216    return 0;
217  }
218  static Constant *EqualTo(const ArgType *V1, const ArgType *V2) {
219    return 0;
220  }
221
222  // Casting operators.  ick
223  static Constant *CastToBool  (const Constant *V) { return 0; }
224  static Constant *CastToSByte (const Constant *V) { return 0; }
225  static Constant *CastToUByte (const Constant *V) { return 0; }
226  static Constant *CastToShort (const Constant *V) { return 0; }
227  static Constant *CastToUShort(const Constant *V) { return 0; }
228  static Constant *CastToInt   (const Constant *V) { return 0; }
229  static Constant *CastToUInt  (const Constant *V) { return 0; }
230  static Constant *CastToLong  (const Constant *V) { return 0; }
231  static Constant *CastToULong (const Constant *V) { return 0; }
232  static Constant *CastToFloat (const Constant *V) { return 0; }
233  static Constant *CastToDouble(const Constant *V) { return 0; }
234  static Constant *CastToPointer(const Constant *,
235                                 const PointerType *) {return 0;}
236
237public:
238  virtual ~TemplateRules() {}
239};
240}  // end anonymous namespace
241
242
243//===----------------------------------------------------------------------===//
244//                             EmptyRules Class
245//===----------------------------------------------------------------------===//
246//
247// EmptyRules provides a concrete base class of ConstRules that does nothing
248//
249namespace {
250struct VISIBILITY_HIDDEN EmptyRules
251  : public TemplateRules<Constant, EmptyRules> {
252  static Constant *EqualTo(const Constant *V1, const Constant *V2) {
253    if (V1 == V2) return ConstantBool::getTrue();
254    return 0;
255  }
256};
257}  // end anonymous namespace
258
259
260
261//===----------------------------------------------------------------------===//
262//                              BoolRules Class
263//===----------------------------------------------------------------------===//
264//
265// BoolRules provides a concrete base class of ConstRules for the 'bool' type.
266//
267namespace {
268struct VISIBILITY_HIDDEN BoolRules
269  : public TemplateRules<ConstantBool, BoolRules> {
270
271  static Constant *LessThan(const ConstantBool *V1, const ConstantBool *V2) {
272    return ConstantBool::get(V1->getValue() < V2->getValue());
273  }
274
275  static Constant *EqualTo(const Constant *V1, const Constant *V2) {
276    return ConstantBool::get(V1 == V2);
277  }
278
279  static Constant *And(const ConstantBool *V1, const ConstantBool *V2) {
280    return ConstantBool::get(V1->getValue() & V2->getValue());
281  }
282
283  static Constant *Or(const ConstantBool *V1, const ConstantBool *V2) {
284    return ConstantBool::get(V1->getValue() | V2->getValue());
285  }
286
287  static Constant *Xor(const ConstantBool *V1, const ConstantBool *V2) {
288    return ConstantBool::get(V1->getValue() ^ V2->getValue());
289  }
290
291  // Casting operators.  ick
292#define DEF_CAST(TYPE, CLASS, CTYPE) \
293  static Constant *CastTo##TYPE  (const ConstantBool *V) {    \
294    return CLASS::get(Type::TYPE##Ty, (CTYPE)(bool)V->getValue()); \
295  }
296
297  DEF_CAST(Bool  , ConstantBool, bool)
298  DEF_CAST(SByte , ConstantInt, signed char)
299  DEF_CAST(UByte , ConstantInt, unsigned char)
300  DEF_CAST(Short , ConstantInt, signed short)
301  DEF_CAST(UShort, ConstantInt, unsigned short)
302  DEF_CAST(Int   , ConstantInt, signed int)
303  DEF_CAST(UInt  , ConstantInt, unsigned int)
304  DEF_CAST(Long  , ConstantInt, int64_t)
305  DEF_CAST(ULong , ConstantInt, uint64_t)
306  DEF_CAST(Float , ConstantFP  , float)
307  DEF_CAST(Double, ConstantFP  , double)
308#undef DEF_CAST
309};
310}  // end anonymous namespace
311
312
313//===----------------------------------------------------------------------===//
314//                            NullPointerRules Class
315//===----------------------------------------------------------------------===//
316//
317// NullPointerRules provides a concrete base class of ConstRules for null
318// pointers.
319//
320namespace {
321struct VISIBILITY_HIDDEN NullPointerRules
322  : public TemplateRules<ConstantPointerNull, NullPointerRules> {
323  static Constant *EqualTo(const Constant *V1, const Constant *V2) {
324    return ConstantBool::getTrue();  // Null pointers are always equal
325  }
326  static Constant *CastToBool(const Constant *V) {
327    return ConstantBool::getFalse();
328  }
329  static Constant *CastToSByte (const Constant *V) {
330    return ConstantInt::get(Type::SByteTy, 0);
331  }
332  static Constant *CastToUByte (const Constant *V) {
333    return ConstantInt::get(Type::UByteTy, 0);
334  }
335  static Constant *CastToShort (const Constant *V) {
336    return ConstantInt::get(Type::ShortTy, 0);
337  }
338  static Constant *CastToUShort(const Constant *V) {
339    return ConstantInt::get(Type::UShortTy, 0);
340  }
341  static Constant *CastToInt   (const Constant *V) {
342    return ConstantInt::get(Type::IntTy, 0);
343  }
344  static Constant *CastToUInt  (const Constant *V) {
345    return ConstantInt::get(Type::UIntTy, 0);
346  }
347  static Constant *CastToLong  (const Constant *V) {
348    return ConstantInt::get(Type::LongTy, 0);
349  }
350  static Constant *CastToULong (const Constant *V) {
351    return ConstantInt::get(Type::ULongTy, 0);
352  }
353  static Constant *CastToFloat (const Constant *V) {
354    return ConstantFP::get(Type::FloatTy, 0);
355  }
356  static Constant *CastToDouble(const Constant *V) {
357    return ConstantFP::get(Type::DoubleTy, 0);
358  }
359
360  static Constant *CastToPointer(const ConstantPointerNull *V,
361                                 const PointerType *PTy) {
362    return ConstantPointerNull::get(PTy);
363  }
364};
365}  // end anonymous namespace
366
367//===----------------------------------------------------------------------===//
368//                          ConstantPackedRules Class
369//===----------------------------------------------------------------------===//
370
371/// DoVectorOp - Given two packed constants and a function pointer, apply the
372/// function pointer to each element pair, producing a new ConstantPacked
373/// constant.
374static Constant *EvalVectorOp(const ConstantPacked *V1,
375                              const ConstantPacked *V2,
376                              Constant *(*FP)(Constant*, Constant*)) {
377  std::vector<Constant*> Res;
378  for (unsigned i = 0, e = V1->getNumOperands(); i != e; ++i)
379    Res.push_back(FP(const_cast<Constant*>(V1->getOperand(i)),
380                     const_cast<Constant*>(V2->getOperand(i))));
381  return ConstantPacked::get(Res);
382}
383
384/// PackedTypeRules provides a concrete base class of ConstRules for
385/// ConstantPacked operands.
386///
387namespace {
388struct VISIBILITY_HIDDEN ConstantPackedRules
389  : public TemplateRules<ConstantPacked, ConstantPackedRules> {
390
391  static Constant *Add(const ConstantPacked *V1, const ConstantPacked *V2) {
392    return EvalVectorOp(V1, V2, ConstantExpr::getAdd);
393  }
394  static Constant *Sub(const ConstantPacked *V1, const ConstantPacked *V2) {
395    return EvalVectorOp(V1, V2, ConstantExpr::getSub);
396  }
397  static Constant *Mul(const ConstantPacked *V1, const ConstantPacked *V2) {
398    return EvalVectorOp(V1, V2, ConstantExpr::getMul);
399  }
400  static Constant *UDiv(const ConstantPacked *V1, const ConstantPacked *V2) {
401    return EvalVectorOp(V1, V2, ConstantExpr::getUDiv);
402  }
403  static Constant *SDiv(const ConstantPacked *V1, const ConstantPacked *V2) {
404    return EvalVectorOp(V1, V2, ConstantExpr::getSDiv);
405  }
406  static Constant *FDiv(const ConstantPacked *V1, const ConstantPacked *V2) {
407    return EvalVectorOp(V1, V2, ConstantExpr::getFDiv);
408  }
409  static Constant *URem(const ConstantPacked *V1, const ConstantPacked *V2) {
410    return EvalVectorOp(V1, V2, ConstantExpr::getURem);
411  }
412  static Constant *SRem(const ConstantPacked *V1, const ConstantPacked *V2) {
413    return EvalVectorOp(V1, V2, ConstantExpr::getSRem);
414  }
415  static Constant *FRem(const ConstantPacked *V1, const ConstantPacked *V2) {
416    return EvalVectorOp(V1, V2, ConstantExpr::getFRem);
417  }
418  static Constant *And(const ConstantPacked *V1, const ConstantPacked *V2) {
419    return EvalVectorOp(V1, V2, ConstantExpr::getAnd);
420  }
421  static Constant *Or (const ConstantPacked *V1, const ConstantPacked *V2) {
422    return EvalVectorOp(V1, V2, ConstantExpr::getOr);
423  }
424  static Constant *Xor(const ConstantPacked *V1, const ConstantPacked *V2) {
425    return EvalVectorOp(V1, V2, ConstantExpr::getXor);
426  }
427  static Constant *LessThan(const ConstantPacked *V1, const ConstantPacked *V2){
428    return 0;
429  }
430  static Constant *EqualTo(const ConstantPacked *V1, const ConstantPacked *V2) {
431    for (unsigned i = 0, e = V1->getNumOperands(); i != e; ++i) {
432      Constant *C =
433        ConstantExpr::getSetEQ(const_cast<Constant*>(V1->getOperand(i)),
434                               const_cast<Constant*>(V2->getOperand(i)));
435      if (ConstantBool *CB = dyn_cast<ConstantBool>(C))
436        return CB;
437    }
438    // Otherwise, could not decide from any element pairs.
439    return 0;
440  }
441};
442}  // end anonymous namespace
443
444
445//===----------------------------------------------------------------------===//
446//                          GeneralPackedRules Class
447//===----------------------------------------------------------------------===//
448
449/// GeneralPackedRules provides a concrete base class of ConstRules for
450/// PackedType operands, where both operands are not ConstantPacked.  The usual
451/// cause for this is that one operand is a ConstantAggregateZero.
452///
453namespace {
454struct VISIBILITY_HIDDEN GeneralPackedRules
455  : public TemplateRules<Constant, GeneralPackedRules> {
456};
457}  // end anonymous namespace
458
459
460//===----------------------------------------------------------------------===//
461//                           DirectIntRules Class
462//===----------------------------------------------------------------------===//
463//
464// DirectIntRules provides implementations of functions that are valid on
465// integer types, but not all types in general.
466//
467namespace {
468template <class BuiltinType, Type **Ty>
469struct VISIBILITY_HIDDEN DirectIntRules
470  : public TemplateRules<ConstantInt, DirectIntRules<BuiltinType, Ty> > {
471
472  static Constant *Add(const ConstantInt *V1, const ConstantInt *V2) {
473    BuiltinType R = (BuiltinType)V1->getZExtValue() +
474                    (BuiltinType)V2->getZExtValue();
475    return ConstantInt::get(*Ty, R);
476  }
477
478  static Constant *Sub(const ConstantInt *V1, const ConstantInt *V2) {
479    BuiltinType R = (BuiltinType)V1->getZExtValue() -
480                    (BuiltinType)V2->getZExtValue();
481    return ConstantInt::get(*Ty, R);
482  }
483
484  static Constant *Mul(const ConstantInt *V1, const ConstantInt *V2) {
485    BuiltinType R = (BuiltinType)V1->getZExtValue() *
486                    (BuiltinType)V2->getZExtValue();
487    return ConstantInt::get(*Ty, R);
488  }
489
490  static Constant *LessThan(const ConstantInt *V1, const ConstantInt *V2) {
491    bool R = (BuiltinType)V1->getZExtValue() < (BuiltinType)V2->getZExtValue();
492    return ConstantBool::get(R);
493  }
494
495  static Constant *EqualTo(const ConstantInt *V1, const ConstantInt *V2) {
496    bool R = (BuiltinType)V1->getZExtValue() == (BuiltinType)V2->getZExtValue();
497    return ConstantBool::get(R);
498  }
499
500  static Constant *CastToPointer(const ConstantInt *V,
501                                 const PointerType *PTy) {
502    if (V->isNullValue())    // Is it a FP or Integral null value?
503      return ConstantPointerNull::get(PTy);
504    return 0;  // Can't const prop other types of pointers
505  }
506
507  // Casting operators.  ick
508#define DEF_CAST(TYPE, CLASS, CTYPE) \
509  static Constant *CastTo##TYPE  (const ConstantInt *V) {    \
510    return CLASS::get(Type::TYPE##Ty, (CTYPE)((BuiltinType)V->getZExtValue()));\
511  }
512
513  DEF_CAST(Bool  , ConstantBool, bool)
514  DEF_CAST(SByte , ConstantInt, signed char)
515  DEF_CAST(UByte , ConstantInt, unsigned char)
516  DEF_CAST(Short , ConstantInt, signed short)
517  DEF_CAST(UShort, ConstantInt, unsigned short)
518  DEF_CAST(Int   , ConstantInt, signed int)
519  DEF_CAST(UInt  , ConstantInt, unsigned int)
520  DEF_CAST(Long  , ConstantInt, int64_t)
521  DEF_CAST(ULong , ConstantInt, uint64_t)
522  DEF_CAST(Float , ConstantFP , float)
523  DEF_CAST(Double, ConstantFP , double)
524#undef DEF_CAST
525
526  static Constant *UDiv(const ConstantInt *V1, const ConstantInt *V2) {
527    if (V2->isNullValue())                   // X / 0
528      return 0;
529    BuiltinType R = (BuiltinType)(V1->getZExtValue() / V2->getZExtValue());
530    return ConstantInt::get(*Ty, R);
531  }
532
533  static Constant *SDiv(const ConstantInt *V1, const ConstantInt *V2) {
534    if (V2->isNullValue())                   // X / 0
535      return 0;
536    if (V2->isAllOnesValue() &&              // MIN_INT / -1
537        (BuiltinType)V1->getSExtValue() == -(BuiltinType)V1->getSExtValue())
538      return 0;
539    BuiltinType R = (BuiltinType)(V1->getSExtValue() / V2->getSExtValue());
540    return ConstantInt::get(*Ty, R);
541  }
542
543  static Constant *URem(const ConstantInt *V1,
544                        const ConstantInt *V2) {
545    if (V2->isNullValue()) return 0;         // X / 0
546    BuiltinType R = (BuiltinType)(V1->getZExtValue() % V2->getZExtValue());
547    return ConstantInt::get(*Ty, R);
548  }
549
550  static Constant *SRem(const ConstantInt *V1,
551                        const ConstantInt *V2) {
552    if (V2->isNullValue()) return 0;         // X % 0
553    if (V2->isAllOnesValue() &&              // MIN_INT % -1
554        (BuiltinType)V1->getSExtValue() == -(BuiltinType)V1->getSExtValue())
555      return 0;
556    BuiltinType R = (BuiltinType)(V1->getSExtValue() % V2->getSExtValue());
557    return ConstantInt::get(*Ty, R);
558  }
559
560  static Constant *And(const ConstantInt *V1, const ConstantInt *V2) {
561    BuiltinType R =
562      (BuiltinType)V1->getZExtValue() & (BuiltinType)V2->getZExtValue();
563    return ConstantInt::get(*Ty, R);
564  }
565  static Constant *Or(const ConstantInt *V1, const ConstantInt *V2) {
566    BuiltinType R =
567      (BuiltinType)V1->getZExtValue() | (BuiltinType)V2->getZExtValue();
568    return ConstantInt::get(*Ty, R);
569  }
570  static Constant *Xor(const ConstantInt *V1, const ConstantInt *V2) {
571    BuiltinType R =
572      (BuiltinType)V1->getZExtValue() ^ (BuiltinType)V2->getZExtValue();
573    return ConstantInt::get(*Ty, R);
574  }
575
576  static Constant *Shl(const ConstantInt *V1, const ConstantInt *V2) {
577    BuiltinType R =
578      (BuiltinType)V1->getZExtValue() << (BuiltinType)V2->getZExtValue();
579    return ConstantInt::get(*Ty, R);
580  }
581
582  static Constant *LShr(const ConstantInt *V1, const ConstantInt *V2) {
583    BuiltinType R = BuiltinType(V1->getZExtValue() >> V2->getZExtValue());
584    return ConstantInt::get(*Ty, R);
585  }
586
587  static Constant *AShr(const ConstantInt *V1, const ConstantInt *V2) {
588    BuiltinType R = BuiltinType(V1->getSExtValue() >> V2->getZExtValue());
589    return ConstantInt::get(*Ty, R);
590  }
591};
592}  // end anonymous namespace
593
594
595//===----------------------------------------------------------------------===//
596//                           DirectFPRules Class
597//===----------------------------------------------------------------------===//
598//
599/// DirectFPRules provides implementations of functions that are valid on
600/// floating point types, but not all types in general.
601///
602namespace {
603template <class BuiltinType, Type **Ty>
604struct VISIBILITY_HIDDEN DirectFPRules
605  : public TemplateRules<ConstantFP, DirectFPRules<BuiltinType, Ty> > {
606
607  static Constant *Add(const ConstantFP *V1, const ConstantFP *V2) {
608    BuiltinType R = (BuiltinType)V1->getValue() +
609                    (BuiltinType)V2->getValue();
610    return ConstantFP::get(*Ty, R);
611  }
612
613  static Constant *Sub(const ConstantFP *V1, const ConstantFP *V2) {
614    BuiltinType R = (BuiltinType)V1->getValue() - (BuiltinType)V2->getValue();
615    return ConstantFP::get(*Ty, R);
616  }
617
618  static Constant *Mul(const ConstantFP *V1, const ConstantFP *V2) {
619    BuiltinType R = (BuiltinType)V1->getValue() * (BuiltinType)V2->getValue();
620    return ConstantFP::get(*Ty, R);
621  }
622
623  static Constant *LessThan(const ConstantFP *V1, const ConstantFP *V2) {
624    bool R = (BuiltinType)V1->getValue() < (BuiltinType)V2->getValue();
625    return ConstantBool::get(R);
626  }
627
628  static Constant *EqualTo(const ConstantFP *V1, const ConstantFP *V2) {
629    bool R = (BuiltinType)V1->getValue() == (BuiltinType)V2->getValue();
630    return ConstantBool::get(R);
631  }
632
633  static Constant *CastToPointer(const ConstantFP *V,
634                                 const PointerType *PTy) {
635    if (V->isNullValue())    // Is it a FP or Integral null value?
636      return ConstantPointerNull::get(PTy);
637    return 0;  // Can't const prop other types of pointers
638  }
639
640  // Casting operators.  ick
641#define DEF_CAST(TYPE, CLASS, CTYPE) \
642  static Constant *CastTo##TYPE  (const ConstantFP *V) {    \
643    return CLASS::get(Type::TYPE##Ty, (CTYPE)(BuiltinType)V->getValue()); \
644  }
645
646  DEF_CAST(Bool  , ConstantBool, bool)
647  DEF_CAST(SByte , ConstantInt, signed char)
648  DEF_CAST(UByte , ConstantInt, unsigned char)
649  DEF_CAST(Short , ConstantInt, signed short)
650  DEF_CAST(UShort, ConstantInt, unsigned short)
651  DEF_CAST(Int   , ConstantInt, signed int)
652  DEF_CAST(UInt  , ConstantInt, unsigned int)
653  DEF_CAST(Long  , ConstantInt, int64_t)
654  DEF_CAST(ULong , ConstantInt, uint64_t)
655  DEF_CAST(Float , ConstantFP , float)
656  DEF_CAST(Double, ConstantFP , double)
657#undef DEF_CAST
658
659  static Constant *FRem(const ConstantFP *V1, const ConstantFP *V2) {
660    if (V2->isNullValue()) return 0;
661    BuiltinType Result = std::fmod((BuiltinType)V1->getValue(),
662                                   (BuiltinType)V2->getValue());
663    return ConstantFP::get(*Ty, Result);
664  }
665  static Constant *FDiv(const ConstantFP *V1, const ConstantFP *V2) {
666    BuiltinType inf = std::numeric_limits<BuiltinType>::infinity();
667    if (V2->isExactlyValue(0.0)) return ConstantFP::get(*Ty, inf);
668    if (V2->isExactlyValue(-0.0)) return ConstantFP::get(*Ty, -inf);
669    BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue();
670    return ConstantFP::get(*Ty, R);
671  }
672};
673}  // end anonymous namespace
674
675static ManagedStatic<EmptyRules>       EmptyR;
676static ManagedStatic<BoolRules>        BoolR;
677static ManagedStatic<NullPointerRules> NullPointerR;
678static ManagedStatic<ConstantPackedRules> ConstantPackedR;
679static ManagedStatic<GeneralPackedRules> GeneralPackedR;
680static ManagedStatic<DirectIntRules<signed char   , &Type::SByteTy> > SByteR;
681static ManagedStatic<DirectIntRules<unsigned char , &Type::UByteTy> > UByteR;
682static ManagedStatic<DirectIntRules<signed short  , &Type::ShortTy> > ShortR;
683static ManagedStatic<DirectIntRules<unsigned short, &Type::UShortTy> > UShortR;
684static ManagedStatic<DirectIntRules<signed int    , &Type::IntTy> >   IntR;
685static ManagedStatic<DirectIntRules<unsigned int  , &Type::UIntTy> >  UIntR;
686static ManagedStatic<DirectIntRules<int64_t       , &Type::LongTy> >  LongR;
687static ManagedStatic<DirectIntRules<uint64_t      , &Type::ULongTy> > ULongR;
688static ManagedStatic<DirectFPRules <float         , &Type::FloatTy> > FloatR;
689static ManagedStatic<DirectFPRules <double        , &Type::DoubleTy> > DoubleR;
690
691/// ConstRules::get - This method returns the constant rules implementation that
692/// implements the semantics of the two specified constants.
693ConstRules &ConstRules::get(const Constant *V1, const Constant *V2) {
694  if (isa<ConstantExpr>(V1) || isa<ConstantExpr>(V2) ||
695      isa<GlobalValue>(V1) || isa<GlobalValue>(V2) ||
696      isa<UndefValue>(V1) || isa<UndefValue>(V2))
697    return *EmptyR;
698
699  switch (V1->getType()->getTypeID()) {
700  default: assert(0 && "Unknown value type for constant folding!");
701  case Type::BoolTyID:    return *BoolR;
702  case Type::PointerTyID: return *NullPointerR;
703  case Type::SByteTyID:   return *SByteR;
704  case Type::UByteTyID:   return *UByteR;
705  case Type::ShortTyID:   return *ShortR;
706  case Type::UShortTyID:  return *UShortR;
707  case Type::IntTyID:     return *IntR;
708  case Type::UIntTyID:    return *UIntR;
709  case Type::LongTyID:    return *LongR;
710  case Type::ULongTyID:   return *ULongR;
711  case Type::FloatTyID:   return *FloatR;
712  case Type::DoubleTyID:  return *DoubleR;
713  case Type::PackedTyID:
714    if (isa<ConstantPacked>(V1) && isa<ConstantPacked>(V2))
715      return *ConstantPackedR;
716    return *GeneralPackedR; // Constant folding rules for ConstantAggregateZero.
717  }
718}
719
720
721//===----------------------------------------------------------------------===//
722//                ConstantFold*Instruction Implementations
723//===----------------------------------------------------------------------===//
724
725/// CastConstantPacked - Convert the specified ConstantPacked node to the
726/// specified packed type.  At this point, we know that the elements of the
727/// input packed constant are all simple integer or FP values.
728static Constant *CastConstantPacked(ConstantPacked *CP,
729                                    const PackedType *DstTy) {
730  unsigned SrcNumElts = CP->getType()->getNumElements();
731  unsigned DstNumElts = DstTy->getNumElements();
732  const Type *SrcEltTy = CP->getType()->getElementType();
733  const Type *DstEltTy = DstTy->getElementType();
734
735  // If both vectors have the same number of elements (thus, the elements
736  // are the same size), perform the conversion now.
737  if (SrcNumElts == DstNumElts) {
738    std::vector<Constant*> Result;
739
740    // If the src and dest elements are both integers, or both floats, we can
741    // just BitCast each element because the elements are the same size.
742    if ((SrcEltTy->isIntegral() && DstEltTy->isIntegral()) ||
743        (SrcEltTy->isFloatingPoint() && DstEltTy->isFloatingPoint())) {
744      for (unsigned i = 0; i != SrcNumElts; ++i)
745        Result.push_back(
746          ConstantExpr::getBitCast(CP->getOperand(i), DstEltTy));
747      return ConstantPacked::get(Result);
748    }
749
750    // If this is an int-to-fp cast ..
751    if (SrcEltTy->isIntegral()) {
752      // Ensure that it is int-to-fp cast
753      assert(DstEltTy->isFloatingPoint());
754      if (DstEltTy->getTypeID() == Type::DoubleTyID) {
755        for (unsigned i = 0; i != SrcNumElts; ++i) {
756          double V =
757            BitsToDouble(cast<ConstantInt>(CP->getOperand(i))->getZExtValue());
758          Result.push_back(ConstantFP::get(Type::DoubleTy, V));
759        }
760        return ConstantPacked::get(Result);
761      }
762      assert(DstEltTy == Type::FloatTy && "Unknown fp type!");
763      for (unsigned i = 0; i != SrcNumElts; ++i) {
764        float V =
765        BitsToFloat(cast<ConstantInt>(CP->getOperand(i))->getZExtValue());
766        Result.push_back(ConstantFP::get(Type::FloatTy, V));
767      }
768      return ConstantPacked::get(Result);
769    }
770
771    // Otherwise, this is an fp-to-int cast.
772    assert(SrcEltTy->isFloatingPoint() && DstEltTy->isIntegral());
773
774    if (SrcEltTy->getTypeID() == Type::DoubleTyID) {
775      for (unsigned i = 0; i != SrcNumElts; ++i) {
776        uint64_t V =
777          DoubleToBits(cast<ConstantFP>(CP->getOperand(i))->getValue());
778        Constant *C = ConstantInt::get(Type::ULongTy, V);
779        Result.push_back(ConstantExpr::getBitCast(C, DstEltTy ));
780      }
781      return ConstantPacked::get(Result);
782    }
783
784    assert(SrcEltTy->getTypeID() == Type::FloatTyID);
785    for (unsigned i = 0; i != SrcNumElts; ++i) {
786      uint32_t V = FloatToBits(cast<ConstantFP>(CP->getOperand(i))->getValue());
787      Constant *C = ConstantInt::get(Type::UIntTy, V);
788      Result.push_back(ConstantExpr::getBitCast(C, DstEltTy));
789    }
790    return ConstantPacked::get(Result);
791  }
792
793  // Otherwise, this is a cast that changes element count and size.  Handle
794  // casts which shrink the elements here.
795
796  // FIXME: We need to know endianness to do this!
797
798  return 0;
799}
800
801/// This function determines which opcode to use to fold two constant cast
802/// expressions together. It uses CastInst::isEliminableCastPair to determine
803/// the opcode. Consequently its just a wrapper around that function.
804/// @Determine if it is valid to fold a cast of a cast
805static unsigned
806foldConstantCastPair(
807  unsigned opc,          ///< opcode of the second cast constant expression
808  const ConstantExpr*Op, ///< the first cast constant expression
809  const Type *DstTy      ///< desintation type of the first cast
810) {
811  assert(Op && Op->isCast() && "Can't fold cast of cast without a cast!");
812  assert(DstTy && DstTy->isFirstClassType() && "Invalid cast destination type");
813  assert(CastInst::isCast(opc) && "Invalid cast opcode");
814
815  // The the types and opcodes for the two Cast constant expressions
816  const Type *SrcTy = Op->getOperand(0)->getType();
817  const Type *MidTy = Op->getType();
818  Instruction::CastOps firstOp = Instruction::CastOps(Op->getOpcode());
819  Instruction::CastOps secondOp = Instruction::CastOps(opc);
820
821  // Let CastInst::isEliminableCastPair do the heavy lifting.
822  return CastInst::isEliminableCastPair(firstOp, secondOp, SrcTy, MidTy, DstTy,
823                                        Type::ULongTy);
824}
825
826Constant *llvm::ConstantFoldCastInstruction(unsigned opc, const Constant *V,
827                                            const Type *DestTy) {
828  const Type *SrcTy = V->getType();
829
830  if (isa<UndefValue>(V))
831    return UndefValue::get(DestTy);
832
833  // If the cast operand is a constant expression, there's a few things we can
834  // do to try to simplify it.
835  if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
836    if (CE->isCast()) {
837      // Try hard to fold cast of cast because they are often eliminable.
838      if (unsigned newOpc = foldConstantCastPair(opc, CE, DestTy))
839        return ConstantExpr::getCast(newOpc, CE->getOperand(0), DestTy);
840    } else if (CE->getOpcode() == Instruction::GetElementPtr) {
841      // If all of the indexes in the GEP are null values, there is no pointer
842      // adjustment going on.  We might as well cast the source pointer.
843      bool isAllNull = true;
844      for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
845        if (!CE->getOperand(i)->isNullValue()) {
846          isAllNull = false;
847          break;
848        }
849      if (isAllNull)
850        // This is casting one pointer type to another, always BitCast
851        return ConstantExpr::getPointerCast(CE->getOperand(0), DestTy);
852    }
853  }
854
855  // We actually have to do a cast now, but first, we might need to fix up
856  // the value of the operand.
857  switch (opc) {
858  case Instruction::PtrToInt:
859  case Instruction::FPTrunc:
860  case Instruction::FPExt:
861    break;
862  case Instruction::FPToUI: {
863    ConstRules &Rules = ConstRules::get(V, V);
864    V = Rules.castToULong(V); // make sure we get an unsigned value first
865    break;
866  }
867  case Instruction::FPToSI: {
868    ConstRules &Rules = ConstRules::get(V, V);
869    V = Rules.castToLong(V); // make sure we get a signed value first
870    break;
871  }
872  case Instruction::IntToPtr: //always treated as unsigned
873  case Instruction::UIToFP:
874  case Instruction::ZExt:
875    // A ZExt always produces an unsigned value so we need to cast the value
876    // now before we try to cast it to the destination type
877    if (isa<ConstantInt>(V))
878      V = ConstantInt::get(SrcTy->getUnsignedVersion(),
879                           cast<ConstantIntegral>(V)->getZExtValue());
880    break;
881  case Instruction::SIToFP:
882  case Instruction::SExt:
883    // A SExt always produces a signed value so we need to cast the value
884    // now before we try to cast it to the destiniation type.
885    if (isa<ConstantInt>(V))
886      V = ConstantInt::get(SrcTy->getSignedVersion(),
887                           cast<ConstantIntegral>(V)->getSExtValue());
888    else if (const ConstantBool *CB = dyn_cast<ConstantBool>(V))
889      V = ConstantInt::get(Type::SByteTy, CB->getValue() ? -1 : 0);
890
891    break;
892  case Instruction::Trunc:
893    // We just handle trunc directly here.  The code below doesn't work for
894    // trunc to bool.
895    if (const ConstantInt *CI = dyn_cast<ConstantInt>(V))
896      return ConstantIntegral::get(DestTy, CI->getZExtValue());
897    return 0;
898  case Instruction::BitCast:
899    if (SrcTy == DestTy) return (Constant*)V; // no-op cast
900
901    // Check to see if we are casting a pointer to an aggregate to a pointer to
902    // the first element.  If so, return the appropriate GEP instruction.
903    if (const PointerType *PTy = dyn_cast<PointerType>(V->getType()))
904      if (const PointerType *DPTy = dyn_cast<PointerType>(DestTy)) {
905        std::vector<Value*> IdxList;
906        IdxList.push_back(Constant::getNullValue(Type::IntTy));
907        const Type *ElTy = PTy->getElementType();
908        while (ElTy != DPTy->getElementType()) {
909          if (const StructType *STy = dyn_cast<StructType>(ElTy)) {
910            if (STy->getNumElements() == 0) break;
911            ElTy = STy->getElementType(0);
912            IdxList.push_back(Constant::getNullValue(Type::UIntTy));
913          } else if (const SequentialType *STy =
914                     dyn_cast<SequentialType>(ElTy)) {
915            if (isa<PointerType>(ElTy)) break;  // Can't index into pointers!
916            ElTy = STy->getElementType();
917            IdxList.push_back(IdxList[0]);
918          } else {
919            break;
920          }
921        }
922
923        if (ElTy == DPTy->getElementType())
924          return ConstantExpr::getGetElementPtr(
925              const_cast<Constant*>(V),IdxList);
926      }
927
928    // Handle casts from one packed constant to another.  We know that the src
929    // and dest type have the same size (otherwise its an illegal cast).
930    if (const PackedType *DestPTy = dyn_cast<PackedType>(DestTy)) {
931      if (const PackedType *SrcTy = dyn_cast<PackedType>(V->getType())) {
932        assert(DestPTy->getBitWidth() == SrcTy->getBitWidth() &&
933               "Not cast between same sized vectors!");
934        // First, check for null and undef
935        if (isa<ConstantAggregateZero>(V))
936          return Constant::getNullValue(DestTy);
937        if (isa<UndefValue>(V))
938          return UndefValue::get(DestTy);
939
940        if (const ConstantPacked *CP = dyn_cast<ConstantPacked>(V)) {
941          // This is a cast from a ConstantPacked of one type to a
942          // ConstantPacked of another type.  Check to see if all elements of
943          // the input are simple.
944          bool AllSimpleConstants = true;
945          for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) {
946            if (!isa<ConstantInt>(CP->getOperand(i)) &&
947                !isa<ConstantFP>(CP->getOperand(i))) {
948              AllSimpleConstants = false;
949              break;
950            }
951          }
952
953          // If all of the elements are simple constants, we can fold this.
954          if (AllSimpleConstants)
955            return CastConstantPacked(const_cast<ConstantPacked*>(CP), DestPTy);
956        }
957      }
958    }
959
960    // Finally, implement bitcast folding now.   The code below doesn't handle
961    // bitcast right.
962    if (isa<ConstantPointerNull>(V))  // ptr->ptr cast.
963      return ConstantPointerNull::get(cast<PointerType>(DestTy));
964
965    // Handle integral constant input.
966    if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
967      // Integral -> Integral, must be changing sign.
968      if (DestTy->isIntegral())
969        return ConstantInt::get(DestTy, CI->getZExtValue());
970
971      if (DestTy->isFloatingPoint()) {
972        if (DestTy == Type::FloatTy)
973          return ConstantFP::get(DestTy, BitsToFloat(CI->getZExtValue()));
974        assert(DestTy == Type::DoubleTy && "Unknown FP type!");
975        return ConstantFP::get(DestTy, BitsToDouble(CI->getZExtValue()));
976      }
977      // Otherwise, can't fold this (packed?)
978      return 0;
979    }
980
981    // Handle ConstantFP input.
982    if (const ConstantFP *FP = dyn_cast<ConstantFP>(V)) {
983      // FP -> Integral.
984      if (DestTy->isIntegral()) {
985        if (DestTy == Type::IntTy || DestTy == Type::UIntTy)
986          return ConstantInt::get(DestTy, FloatToBits(FP->getValue()));
987        assert((DestTy == Type::LongTy || DestTy == Type::ULongTy)
988               && "Incorrect integer  type for bitcast!");
989        return ConstantInt::get(DestTy, DoubleToBits(FP->getValue()));
990      }
991    }
992    return 0;
993  default:
994    assert(!"Invalid CE CastInst opcode");
995    break;
996  }
997
998  // Okay, no more folding possible, time to cast
999  ConstRules &Rules = ConstRules::get(V, V);
1000  switch (DestTy->getTypeID()) {
1001  case Type::BoolTyID:    return Rules.castToBool(V);
1002  case Type::UByteTyID:   return Rules.castToUByte(V);
1003  case Type::SByteTyID:   return Rules.castToSByte(V);
1004  case Type::UShortTyID:  return Rules.castToUShort(V);
1005  case Type::ShortTyID:   return Rules.castToShort(V);
1006  case Type::UIntTyID:    return Rules.castToUInt(V);
1007  case Type::IntTyID:     return Rules.castToInt(V);
1008  case Type::ULongTyID:   return Rules.castToULong(V);
1009  case Type::LongTyID:    return Rules.castToLong(V);
1010  case Type::FloatTyID:   return Rules.castToFloat(V);
1011  case Type::DoubleTyID:  return Rules.castToDouble(V);
1012  case Type::PointerTyID:
1013    return Rules.castToPointer(V, cast<PointerType>(DestTy));
1014  // what about packed ?
1015  default: return 0;
1016  }
1017}
1018
1019Constant *llvm::ConstantFoldSelectInstruction(const Constant *Cond,
1020                                              const Constant *V1,
1021                                              const Constant *V2) {
1022  if (const ConstantBool *CB = dyn_cast<ConstantBool>(Cond))
1023    return const_cast<Constant*>(CB->getValue() ? V1 : V2);
1024
1025  if (isa<UndefValue>(V1)) return const_cast<Constant*>(V2);
1026  if (isa<UndefValue>(V2)) return const_cast<Constant*>(V1);
1027  if (isa<UndefValue>(Cond)) return const_cast<Constant*>(V1);
1028  if (V1 == V2) return const_cast<Constant*>(V1);
1029  return 0;
1030}
1031
1032Constant *llvm::ConstantFoldExtractElementInstruction(const Constant *Val,
1033                                                      const Constant *Idx) {
1034  if (isa<UndefValue>(Val))  // ee(undef, x) -> undef
1035    return UndefValue::get(cast<PackedType>(Val->getType())->getElementType());
1036  if (Val->isNullValue())  // ee(zero, x) -> zero
1037    return Constant::getNullValue(
1038                          cast<PackedType>(Val->getType())->getElementType());
1039
1040  if (const ConstantPacked *CVal = dyn_cast<ConstantPacked>(Val)) {
1041    if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Idx)) {
1042      return const_cast<Constant*>(CVal->getOperand(CIdx->getZExtValue()));
1043    } else if (isa<UndefValue>(Idx)) {
1044      // ee({w,x,y,z}, undef) -> w (an arbitrary value).
1045      return const_cast<Constant*>(CVal->getOperand(0));
1046    }
1047  }
1048  return 0;
1049}
1050
1051Constant *llvm::ConstantFoldInsertElementInstruction(const Constant *Val,
1052                                                     const Constant *Elt,
1053                                                     const Constant *Idx) {
1054  const ConstantInt *CIdx = dyn_cast<ConstantInt>(Idx);
1055  if (!CIdx) return 0;
1056  uint64_t idxVal = CIdx->getZExtValue();
1057  if (isa<UndefValue>(Val)) {
1058    // Insertion of scalar constant into packed undef
1059    // Optimize away insertion of undef
1060    if (isa<UndefValue>(Elt))
1061      return const_cast<Constant*>(Val);
1062    // Otherwise break the aggregate undef into multiple undefs and do
1063    // the insertion
1064    unsigned numOps =
1065      cast<PackedType>(Val->getType())->getNumElements();
1066    std::vector<Constant*> Ops;
1067    Ops.reserve(numOps);
1068    for (unsigned i = 0; i < numOps; ++i) {
1069      const Constant *Op =
1070        (i == idxVal) ? Elt : UndefValue::get(Elt->getType());
1071      Ops.push_back(const_cast<Constant*>(Op));
1072    }
1073    return ConstantPacked::get(Ops);
1074  }
1075  if (isa<ConstantAggregateZero>(Val)) {
1076    // Insertion of scalar constant into packed aggregate zero
1077    // Optimize away insertion of zero
1078    if (Elt->isNullValue())
1079      return const_cast<Constant*>(Val);
1080    // Otherwise break the aggregate zero into multiple zeros and do
1081    // the insertion
1082    unsigned numOps =
1083      cast<PackedType>(Val->getType())->getNumElements();
1084    std::vector<Constant*> Ops;
1085    Ops.reserve(numOps);
1086    for (unsigned i = 0; i < numOps; ++i) {
1087      const Constant *Op =
1088        (i == idxVal) ? Elt : Constant::getNullValue(Elt->getType());
1089      Ops.push_back(const_cast<Constant*>(Op));
1090    }
1091    return ConstantPacked::get(Ops);
1092  }
1093  if (const ConstantPacked *CVal = dyn_cast<ConstantPacked>(Val)) {
1094    // Insertion of scalar constant into packed constant
1095    std::vector<Constant*> Ops;
1096    Ops.reserve(CVal->getNumOperands());
1097    for (unsigned i = 0; i < CVal->getNumOperands(); ++i) {
1098      const Constant *Op =
1099        (i == idxVal) ? Elt : cast<Constant>(CVal->getOperand(i));
1100      Ops.push_back(const_cast<Constant*>(Op));
1101    }
1102    return ConstantPacked::get(Ops);
1103  }
1104  return 0;
1105}
1106
1107Constant *llvm::ConstantFoldShuffleVectorInstruction(const Constant *V1,
1108                                                     const Constant *V2,
1109                                                     const Constant *Mask) {
1110  // TODO:
1111  return 0;
1112}
1113
1114
1115/// isZeroSizedType - This type is zero sized if its an array or structure of
1116/// zero sized types.  The only leaf zero sized type is an empty structure.
1117static bool isMaybeZeroSizedType(const Type *Ty) {
1118  if (isa<OpaqueType>(Ty)) return true;  // Can't say.
1119  if (const StructType *STy = dyn_cast<StructType>(Ty)) {
1120
1121    // If all of elements have zero size, this does too.
1122    for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1123      if (!isMaybeZeroSizedType(STy->getElementType(i))) return false;
1124    return true;
1125
1126  } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
1127    return isMaybeZeroSizedType(ATy->getElementType());
1128  }
1129  return false;
1130}
1131
1132/// IdxCompare - Compare the two constants as though they were getelementptr
1133/// indices.  This allows coersion of the types to be the same thing.
1134///
1135/// If the two constants are the "same" (after coersion), return 0.  If the
1136/// first is less than the second, return -1, if the second is less than the
1137/// first, return 1.  If the constants are not integral, return -2.
1138///
1139static int IdxCompare(Constant *C1, Constant *C2, const Type *ElTy) {
1140  if (C1 == C2) return 0;
1141
1142  // Ok, we found a different index.  Are either of the operands ConstantExprs?
1143  // If so, we can't do anything with them.
1144  if (!isa<ConstantInt>(C1) || !isa<ConstantInt>(C2))
1145    return -2; // don't know!
1146
1147  // Ok, we have two differing integer indices.  Sign extend them to be the same
1148  // type.  Long is always big enough, so we use it.
1149  if (C1->getType() != Type::LongTy && C1->getType() != Type::ULongTy)
1150    C1 = ConstantExpr::getSExt(C1, Type::LongTy);
1151  else
1152    C1 = ConstantExpr::getBitCast(C1, Type::LongTy);
1153  if (C2->getType() != Type::LongTy && C1->getType() != Type::ULongTy)
1154    C2 = ConstantExpr::getSExt(C2, Type::LongTy);
1155  else
1156    C2 = ConstantExpr::getBitCast(C2, Type::LongTy);
1157
1158  if (C1 == C2) return 0;  // Are they just differing types?
1159
1160  // If the type being indexed over is really just a zero sized type, there is
1161  // no pointer difference being made here.
1162  if (isMaybeZeroSizedType(ElTy))
1163    return -2; // dunno.
1164
1165  // If they are really different, now that they are the same type, then we
1166  // found a difference!
1167  if (cast<ConstantInt>(C1)->getSExtValue() <
1168      cast<ConstantInt>(C2)->getSExtValue())
1169    return -1;
1170  else
1171    return 1;
1172}
1173
1174/// evaluateRelation - This function determines if there is anything we can
1175/// decide about the two constants provided.  This doesn't need to handle simple
1176/// things like integer comparisons, but should instead handle ConstantExprs
1177/// and GlobalValues.  If we can determine that the two constants have a
1178/// particular relation to each other, we should return the corresponding SetCC
1179/// code, otherwise return Instruction::BinaryOpsEnd.
1180///
1181/// To simplify this code we canonicalize the relation so that the first
1182/// operand is always the most "complex" of the two.  We consider simple
1183/// constants (like ConstantInt) to be the simplest, followed by
1184/// GlobalValues, followed by ConstantExpr's (the most complex).
1185///
1186static Instruction::BinaryOps evaluateRelation(Constant *V1, Constant *V2) {
1187  assert(V1->getType() == V2->getType() &&
1188         "Cannot compare different types of values!");
1189  if (V1 == V2) return Instruction::SetEQ;
1190
1191  if (!isa<ConstantExpr>(V1) && !isa<GlobalValue>(V1)) {
1192    if (!isa<GlobalValue>(V2) && !isa<ConstantExpr>(V2)) {
1193      // We distilled this down to a simple case, use the standard constant
1194      // folder.
1195      ConstantBool *R = dyn_cast<ConstantBool>(ConstantExpr::getSetEQ(V1, V2));
1196      if (R && R->getValue()) return Instruction::SetEQ;
1197      R = dyn_cast<ConstantBool>(ConstantExpr::getSetLT(V1, V2));
1198      if (R && R->getValue()) return Instruction::SetLT;
1199      R = dyn_cast<ConstantBool>(ConstantExpr::getSetGT(V1, V2));
1200      if (R && R->getValue()) return Instruction::SetGT;
1201
1202      // If we couldn't figure it out, bail.
1203      return Instruction::BinaryOpsEnd;
1204    }
1205
1206    // If the first operand is simple, swap operands.
1207    Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1);
1208    if (SwappedRelation != Instruction::BinaryOpsEnd)
1209      return SetCondInst::getSwappedCondition(SwappedRelation);
1210
1211  } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(V1)) {
1212    if (isa<ConstantExpr>(V2)) {  // Swap as necessary.
1213      Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1);
1214      if (SwappedRelation != Instruction::BinaryOpsEnd)
1215        return SetCondInst::getSwappedCondition(SwappedRelation);
1216      else
1217        return Instruction::BinaryOpsEnd;
1218    }
1219
1220    // Now we know that the RHS is a GlobalValue or simple constant,
1221    // which (since the types must match) means that it's a ConstantPointerNull.
1222    if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) {
1223      if (!CPR1->hasExternalWeakLinkage() || !CPR2->hasExternalWeakLinkage())
1224        return Instruction::SetNE;
1225    } else {
1226      // GlobalVals can never be null.
1227      assert(isa<ConstantPointerNull>(V2) && "Canonicalization guarantee!");
1228      if (!CPR1->hasExternalWeakLinkage())
1229        return Instruction::SetNE;
1230    }
1231  } else {
1232    // Ok, the LHS is known to be a constantexpr.  The RHS can be any of a
1233    // constantexpr, a CPR, or a simple constant.
1234    ConstantExpr *CE1 = cast<ConstantExpr>(V1);
1235    Constant *CE1Op0 = CE1->getOperand(0);
1236
1237    switch (CE1->getOpcode()) {
1238    case Instruction::Trunc:
1239    case Instruction::FPTrunc:
1240    case Instruction::FPExt:
1241    case Instruction::FPToUI:
1242    case Instruction::FPToSI:
1243      break; // We don't do anything with floating point.
1244    case Instruction::ZExt:
1245    case Instruction::SExt:
1246    case Instruction::UIToFP:
1247    case Instruction::SIToFP:
1248    case Instruction::PtrToInt:
1249    case Instruction::IntToPtr:
1250    case Instruction::BitCast:
1251      // If the cast is not actually changing bits, and the second operand is a
1252      // null pointer, do the comparison with the pre-casted value.
1253      if (V2->isNullValue() &&
1254          (isa<PointerType>(CE1->getType()) || CE1->getType()->isIntegral()))
1255        return evaluateRelation(CE1Op0,
1256                                Constant::getNullValue(CE1Op0->getType()));
1257
1258      // If the dest type is a pointer type, and the RHS is a constantexpr cast
1259      // from the same type as the src of the LHS, evaluate the inputs.  This is
1260      // important for things like "seteq (cast 4 to int*), (cast 5 to int*)",
1261      // which happens a lot in compilers with tagged integers.
1262      if (ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2))
1263        if (isa<PointerType>(CE1->getType()) && CE2->isCast() &&
1264            CE1->getOperand(0)->getType() == CE2->getOperand(0)->getType() &&
1265            CE1->getOperand(0)->getType()->isIntegral()) {
1266          return evaluateRelation(CE1->getOperand(0), CE2->getOperand(0));
1267        }
1268      break;
1269
1270    case Instruction::GetElementPtr:
1271      // Ok, since this is a getelementptr, we know that the constant has a
1272      // pointer type.  Check the various cases.
1273      if (isa<ConstantPointerNull>(V2)) {
1274        // If we are comparing a GEP to a null pointer, check to see if the base
1275        // of the GEP equals the null pointer.
1276        if (GlobalValue *GV = dyn_cast<GlobalValue>(CE1Op0)) {
1277          if (GV->hasExternalWeakLinkage())
1278            // Weak linkage GVals could be zero or not. We're comparing that
1279            // to null pointer so its greater-or-equal
1280            return Instruction::SetGE;
1281          else
1282            // If its not weak linkage, the GVal must have a non-zero address
1283            // so the result is greater-than
1284            return Instruction::SetGT;
1285        } else if (isa<ConstantPointerNull>(CE1Op0)) {
1286          // If we are indexing from a null pointer, check to see if we have any
1287          // non-zero indices.
1288          for (unsigned i = 1, e = CE1->getNumOperands(); i != e; ++i)
1289            if (!CE1->getOperand(i)->isNullValue())
1290              // Offsetting from null, must not be equal.
1291              return Instruction::SetGT;
1292          // Only zero indexes from null, must still be zero.
1293          return Instruction::SetEQ;
1294        }
1295        // Otherwise, we can't really say if the first operand is null or not.
1296      } else if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) {
1297        if (isa<ConstantPointerNull>(CE1Op0)) {
1298          if (CPR2->hasExternalWeakLinkage())
1299            // Weak linkage GVals could be zero or not. We're comparing it to
1300            // a null pointer, so its less-or-equal
1301            return Instruction::SetLE;
1302          else
1303            // If its not weak linkage, the GVal must have a non-zero address
1304            // so the result is less-than
1305            return Instruction::SetLT;
1306        } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(CE1Op0)) {
1307          if (CPR1 == CPR2) {
1308            // If this is a getelementptr of the same global, then it must be
1309            // different.  Because the types must match, the getelementptr could
1310            // only have at most one index, and because we fold getelementptr's
1311            // with a single zero index, it must be nonzero.
1312            assert(CE1->getNumOperands() == 2 &&
1313                   !CE1->getOperand(1)->isNullValue() &&
1314                   "Suprising getelementptr!");
1315            return Instruction::SetGT;
1316          } else {
1317            // If they are different globals, we don't know what the value is,
1318            // but they can't be equal.
1319            return Instruction::SetNE;
1320          }
1321        }
1322      } else {
1323        const ConstantExpr *CE2 = cast<ConstantExpr>(V2);
1324        const Constant *CE2Op0 = CE2->getOperand(0);
1325
1326        // There are MANY other foldings that we could perform here.  They will
1327        // probably be added on demand, as they seem needed.
1328        switch (CE2->getOpcode()) {
1329        default: break;
1330        case Instruction::GetElementPtr:
1331          // By far the most common case to handle is when the base pointers are
1332          // obviously to the same or different globals.
1333          if (isa<GlobalValue>(CE1Op0) && isa<GlobalValue>(CE2Op0)) {
1334            if (CE1Op0 != CE2Op0) // Don't know relative ordering, but not equal
1335              return Instruction::SetNE;
1336            // Ok, we know that both getelementptr instructions are based on the
1337            // same global.  From this, we can precisely determine the relative
1338            // ordering of the resultant pointers.
1339            unsigned i = 1;
1340
1341            // Compare all of the operands the GEP's have in common.
1342            gep_type_iterator GTI = gep_type_begin(CE1);
1343            for (;i != CE1->getNumOperands() && i != CE2->getNumOperands();
1344                 ++i, ++GTI)
1345              switch (IdxCompare(CE1->getOperand(i), CE2->getOperand(i),
1346                                 GTI.getIndexedType())) {
1347              case -1: return Instruction::SetLT;
1348              case 1:  return Instruction::SetGT;
1349              case -2: return Instruction::BinaryOpsEnd;
1350              }
1351
1352            // Ok, we ran out of things they have in common.  If any leftovers
1353            // are non-zero then we have a difference, otherwise we are equal.
1354            for (; i < CE1->getNumOperands(); ++i)
1355              if (!CE1->getOperand(i)->isNullValue())
1356                if (isa<ConstantIntegral>(CE1->getOperand(i)))
1357                  return Instruction::SetGT;
1358                else
1359                  return Instruction::BinaryOpsEnd; // Might be equal.
1360
1361            for (; i < CE2->getNumOperands(); ++i)
1362              if (!CE2->getOperand(i)->isNullValue())
1363                if (isa<ConstantIntegral>(CE2->getOperand(i)))
1364                  return Instruction::SetLT;
1365                else
1366                  return Instruction::BinaryOpsEnd; // Might be equal.
1367            return Instruction::SetEQ;
1368          }
1369        }
1370      }
1371
1372    default:
1373      break;
1374    }
1375  }
1376
1377  return Instruction::BinaryOpsEnd;
1378}
1379
1380Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode,
1381                                              const Constant *V1,
1382                                              const Constant *V2) {
1383  Constant *C = 0;
1384  switch (Opcode) {
1385  default:                   break;
1386  case Instruction::Add:     C = ConstRules::get(V1, V2).add(V1, V2); break;
1387  case Instruction::Sub:     C = ConstRules::get(V1, V2).sub(V1, V2); break;
1388  case Instruction::Mul:     C = ConstRules::get(V1, V2).mul(V1, V2); break;
1389  case Instruction::UDiv:    C = ConstRules::get(V1, V2).udiv(V1, V2); break;
1390  case Instruction::SDiv:    C = ConstRules::get(V1, V2).sdiv(V1, V2); break;
1391  case Instruction::FDiv:    C = ConstRules::get(V1, V2).fdiv(V1, V2); break;
1392  case Instruction::URem:    C = ConstRules::get(V1, V2).urem(V1, V2); break;
1393  case Instruction::SRem:    C = ConstRules::get(V1, V2).srem(V1, V2); break;
1394  case Instruction::FRem:    C = ConstRules::get(V1, V2).frem(V1, V2); break;
1395  case Instruction::And:     C = ConstRules::get(V1, V2).op_and(V1, V2); break;
1396  case Instruction::Or:      C = ConstRules::get(V1, V2).op_or (V1, V2); break;
1397  case Instruction::Xor:     C = ConstRules::get(V1, V2).op_xor(V1, V2); break;
1398  case Instruction::Shl:     C = ConstRules::get(V1, V2).shl(V1, V2); break;
1399  case Instruction::LShr:    C = ConstRules::get(V1, V2).lshr(V1, V2); break;
1400  case Instruction::AShr:    C = ConstRules::get(V1, V2).ashr(V1, V2); break;
1401  case Instruction::SetEQ:
1402    // SetEQ(null,GV) -> false
1403    if (V1->isNullValue()) {
1404      if (const GlobalValue *GV = dyn_cast<GlobalValue>(V2))
1405        if (!GV->hasExternalWeakLinkage())
1406          return ConstantBool::getFalse();
1407    // SetEQ(GV,null) -> false
1408    } else if (V2->isNullValue()) {
1409      if (const GlobalValue *GV = dyn_cast<GlobalValue>(V1))
1410        if (!GV->hasExternalWeakLinkage())
1411          return ConstantBool::getFalse();
1412    }
1413    C = ConstRules::get(V1, V2).equalto(V1, V2);
1414    break;
1415  case Instruction::SetLT:   C = ConstRules::get(V1, V2).lessthan(V1, V2);break;
1416  case Instruction::SetGT:   C = ConstRules::get(V1, V2).lessthan(V2, V1);break;
1417  case Instruction::SetNE:
1418    // SetNE(null,GV) -> true
1419    if (V1->isNullValue()) {
1420      if (const GlobalValue *GV = dyn_cast<GlobalValue>(V2))
1421        if (!GV->hasExternalWeakLinkage())
1422          return ConstantBool::getTrue();
1423    // SetNE(GV,null) -> true
1424    } else if (V2->isNullValue()) {
1425      if (const GlobalValue *GV = dyn_cast<GlobalValue>(V1))
1426        if (!GV->hasExternalWeakLinkage())
1427          return ConstantBool::getTrue();
1428    }
1429    // V1 != V2  ===  !(V1 == V2)
1430    C = ConstRules::get(V1, V2).equalto(V1, V2);
1431    if (C) return ConstantExpr::getNot(C);
1432    break;
1433  case Instruction::SetLE:   // V1 <= V2  ===  !(V2 < V1)
1434    C = ConstRules::get(V1, V2).lessthan(V2, V1);
1435    if (C) return ConstantExpr::getNot(C);
1436    break;
1437  case Instruction::SetGE:   // V1 >= V2  ===  !(V1 < V2)
1438    C = ConstRules::get(V1, V2).lessthan(V1, V2);
1439    if (C) return ConstantExpr::getNot(C);
1440    break;
1441  }
1442
1443  // If we successfully folded the expression, return it now.
1444  if (C) return C;
1445
1446  if (SetCondInst::isComparison(Opcode)) {
1447    if (isa<UndefValue>(V1) || isa<UndefValue>(V2))
1448      return UndefValue::get(Type::BoolTy);
1449    switch (evaluateRelation(const_cast<Constant*>(V1),
1450                             const_cast<Constant*>(V2))) {
1451    default: assert(0 && "Unknown relational!");
1452    case Instruction::BinaryOpsEnd:
1453      break;  // Couldn't determine anything about these constants.
1454    case Instruction::SetEQ:   // We know the constants are equal!
1455      // If we know the constants are equal, we can decide the result of this
1456      // computation precisely.
1457      return ConstantBool::get(Opcode == Instruction::SetEQ ||
1458                               Opcode == Instruction::SetLE ||
1459                               Opcode == Instruction::SetGE);
1460    case Instruction::SetLT:
1461      // If we know that V1 < V2, we can decide the result of this computation
1462      // precisely.
1463      return ConstantBool::get(Opcode == Instruction::SetLT ||
1464                               Opcode == Instruction::SetNE ||
1465                               Opcode == Instruction::SetLE);
1466    case Instruction::SetGT:
1467      // If we know that V1 > V2, we can decide the result of this computation
1468      // precisely.
1469      return ConstantBool::get(Opcode == Instruction::SetGT ||
1470                               Opcode == Instruction::SetNE ||
1471                               Opcode == Instruction::SetGE);
1472    case Instruction::SetLE:
1473      // If we know that V1 <= V2, we can only partially decide this relation.
1474      if (Opcode == Instruction::SetGT) return ConstantBool::getFalse();
1475      if (Opcode == Instruction::SetLT) return ConstantBool::getTrue();
1476      break;
1477
1478    case Instruction::SetGE:
1479      // If we know that V1 >= V2, we can only partially decide this relation.
1480      if (Opcode == Instruction::SetLT) return ConstantBool::getFalse();
1481      if (Opcode == Instruction::SetGT) return ConstantBool::getTrue();
1482      break;
1483
1484    case Instruction::SetNE:
1485      // If we know that V1 != V2, we can only partially decide this relation.
1486      if (Opcode == Instruction::SetEQ) return ConstantBool::getFalse();
1487      if (Opcode == Instruction::SetNE) return ConstantBool::getTrue();
1488      break;
1489    }
1490  }
1491
1492  if (isa<UndefValue>(V1) || isa<UndefValue>(V2)) {
1493    switch (Opcode) {
1494    case Instruction::Add:
1495    case Instruction::Sub:
1496    case Instruction::Xor:
1497      return UndefValue::get(V1->getType());
1498
1499    case Instruction::Mul:
1500    case Instruction::And:
1501      return Constant::getNullValue(V1->getType());
1502    case Instruction::UDiv:
1503    case Instruction::SDiv:
1504    case Instruction::FDiv:
1505    case Instruction::URem:
1506    case Instruction::SRem:
1507    case Instruction::FRem:
1508      if (!isa<UndefValue>(V2))                    // undef / X -> 0
1509        return Constant::getNullValue(V1->getType());
1510      return const_cast<Constant*>(V2);            // X / undef -> undef
1511    case Instruction::Or:                          // X | undef -> -1
1512      return ConstantInt::getAllOnesValue(V1->getType());
1513    case Instruction::LShr:
1514      if (isa<UndefValue>(V2) && isa<UndefValue>(V1))
1515        return const_cast<Constant*>(V1);           // undef lshr undef -> undef
1516      return Constant::getNullValue(V1->getType()); // X lshr undef -> 0
1517                                                    // undef lshr X -> 0
1518    case Instruction::AShr:
1519      if (!isa<UndefValue>(V2))
1520        return const_cast<Constant*>(V1);           // undef ashr X --> undef
1521      else if (isa<UndefValue>(V1))
1522        return const_cast<Constant*>(V1);           // undef ashr undef -> undef
1523      else
1524        return const_cast<Constant*>(V1);           // X ashr undef --> X
1525    case Instruction::Shl:
1526      // undef << X -> 0   or   X << undef -> 0
1527      return Constant::getNullValue(V1->getType());
1528    }
1529  }
1530
1531  if (const ConstantExpr *CE1 = dyn_cast<ConstantExpr>(V1)) {
1532    if (isa<ConstantExpr>(V2)) {
1533      // There are many possible foldings we could do here.  We should probably
1534      // at least fold add of a pointer with an integer into the appropriate
1535      // getelementptr.  This will improve alias analysis a bit.
1536    } else {
1537      // Just implement a couple of simple identities.
1538      switch (Opcode) {
1539      case Instruction::Add:
1540        if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X + 0 == X
1541        break;
1542      case Instruction::Sub:
1543        if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X - 0 == X
1544        break;
1545      case Instruction::Mul:
1546        if (V2->isNullValue()) return const_cast<Constant*>(V2);  // X * 0 == 0
1547        if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1548          if (CI->getZExtValue() == 1)
1549            return const_cast<Constant*>(V1);                     // X * 1 == X
1550        break;
1551      case Instruction::UDiv:
1552      case Instruction::SDiv:
1553        if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1554          if (CI->getZExtValue() == 1)
1555            return const_cast<Constant*>(V1);                     // X / 1 == X
1556        break;
1557      case Instruction::URem:
1558      case Instruction::SRem:
1559        if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1560          if (CI->getZExtValue() == 1)
1561            return Constant::getNullValue(CI->getType());         // X % 1 == 0
1562        break;
1563      case Instruction::And:
1564        if (cast<ConstantIntegral>(V2)->isAllOnesValue())
1565          return const_cast<Constant*>(V1);                       // X & -1 == X
1566        if (V2->isNullValue()) return const_cast<Constant*>(V2);  // X & 0 == 0
1567        if (CE1->isCast() && isa<GlobalValue>(CE1->getOperand(0))) {
1568          GlobalValue *CPR = cast<GlobalValue>(CE1->getOperand(0));
1569
1570          // Functions are at least 4-byte aligned.  If and'ing the address of a
1571          // function with a constant < 4, fold it to zero.
1572          if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1573            if (CI->getZExtValue() < 4 && isa<Function>(CPR))
1574              return Constant::getNullValue(CI->getType());
1575        }
1576        break;
1577      case Instruction::Or:
1578        if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X | 0 == X
1579        if (cast<ConstantIntegral>(V2)->isAllOnesValue())
1580          return const_cast<Constant*>(V2);  // X | -1 == -1
1581        break;
1582      case Instruction::Xor:
1583        if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X ^ 0 == X
1584        break;
1585      }
1586    }
1587
1588  } else if (isa<ConstantExpr>(V2)) {
1589    // If V2 is a constant expr and V1 isn't, flop them around and fold the
1590    // other way if possible.
1591    switch (Opcode) {
1592    case Instruction::Add:
1593    case Instruction::Mul:
1594    case Instruction::And:
1595    case Instruction::Or:
1596    case Instruction::Xor:
1597    case Instruction::SetEQ:
1598    case Instruction::SetNE:
1599      // No change of opcode required.
1600      return ConstantFoldBinaryInstruction(Opcode, V2, V1);
1601
1602    case Instruction::SetLT:
1603    case Instruction::SetGT:
1604    case Instruction::SetLE:
1605    case Instruction::SetGE:
1606      // Change the opcode as necessary to swap the operands.
1607      Opcode = SetCondInst::getSwappedCondition((Instruction::BinaryOps)Opcode);
1608      return ConstantFoldBinaryInstruction(Opcode, V2, V1);
1609
1610    case Instruction::Shl:
1611    case Instruction::LShr:
1612    case Instruction::AShr:
1613    case Instruction::Sub:
1614    case Instruction::SDiv:
1615    case Instruction::UDiv:
1616    case Instruction::FDiv:
1617    case Instruction::URem:
1618    case Instruction::SRem:
1619    case Instruction::FRem:
1620    default:  // These instructions cannot be flopped around.
1621      break;
1622    }
1623  }
1624  return 0;
1625}
1626
1627Constant *llvm::ConstantFoldCompare(
1628    unsigned opcode, Constant *C1, Constant  *C2, unsigned short predicate)
1629{
1630  // Place holder for future folding of ICmp and FCmp instructions
1631  return 0;
1632}
1633
1634Constant *llvm::ConstantFoldGetElementPtr(const Constant *C,
1635                                          const std::vector<Value*> &IdxList) {
1636  if (IdxList.size() == 0 ||
1637      (IdxList.size() == 1 && cast<Constant>(IdxList[0])->isNullValue()))
1638    return const_cast<Constant*>(C);
1639
1640  if (isa<UndefValue>(C)) {
1641    const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList,
1642                                                       true);
1643    assert(Ty != 0 && "Invalid indices for GEP!");
1644    return UndefValue::get(PointerType::get(Ty));
1645  }
1646
1647  Constant *Idx0 = cast<Constant>(IdxList[0]);
1648  if (C->isNullValue()) {
1649    bool isNull = true;
1650    for (unsigned i = 0, e = IdxList.size(); i != e; ++i)
1651      if (!cast<Constant>(IdxList[i])->isNullValue()) {
1652        isNull = false;
1653        break;
1654      }
1655    if (isNull) {
1656      const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList,
1657                                                         true);
1658      assert(Ty != 0 && "Invalid indices for GEP!");
1659      return ConstantPointerNull::get(PointerType::get(Ty));
1660    }
1661
1662    if (IdxList.size() == 1) {
1663      const Type *ElTy = cast<PointerType>(C->getType())->getElementType();
1664      if (uint32_t ElSize = ElTy->getPrimitiveSize()) {
1665        // gep null, C is equal to C*sizeof(nullty).  If nullty is a known llvm
1666        // type, we can statically fold this.
1667        Constant *R = ConstantInt::get(Type::UIntTy, ElSize);
1668        // We know R is unsigned, Idx0 is signed because it must be an index
1669        // through a sequential type (gep pointer operand) which is always
1670        // signed.
1671        R = ConstantExpr::getSExtOrBitCast(R, Idx0->getType());
1672        R = ConstantExpr::getMul(R, Idx0); // signed multiply
1673        // R is a signed integer, C is the GEP pointer so -> IntToPtr
1674        return ConstantExpr::getIntToPtr(R, C->getType());
1675      }
1676    }
1677  }
1678
1679  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(const_cast<Constant*>(C))) {
1680    // Combine Indices - If the source pointer to this getelementptr instruction
1681    // is a getelementptr instruction, combine the indices of the two
1682    // getelementptr instructions into a single instruction.
1683    //
1684    if (CE->getOpcode() == Instruction::GetElementPtr) {
1685      const Type *LastTy = 0;
1686      for (gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
1687           I != E; ++I)
1688        LastTy = *I;
1689
1690      if ((LastTy && isa<ArrayType>(LastTy)) || Idx0->isNullValue()) {
1691        std::vector<Value*> NewIndices;
1692        NewIndices.reserve(IdxList.size() + CE->getNumOperands());
1693        for (unsigned i = 1, e = CE->getNumOperands()-1; i != e; ++i)
1694          NewIndices.push_back(CE->getOperand(i));
1695
1696        // Add the last index of the source with the first index of the new GEP.
1697        // Make sure to handle the case when they are actually different types.
1698        Constant *Combined = CE->getOperand(CE->getNumOperands()-1);
1699        // Otherwise it must be an array.
1700        if (!Idx0->isNullValue()) {
1701          const Type *IdxTy = Combined->getType();
1702          if (IdxTy != Idx0->getType()) {
1703            Constant *C1 = ConstantExpr::getSExtOrBitCast(Idx0, Type::LongTy);
1704            Constant *C2 = ConstantExpr::getSExtOrBitCast(Combined,
1705                                                          Type::LongTy);
1706            Combined = ConstantExpr::get(Instruction::Add, C1, C2);
1707          } else {
1708            Combined =
1709              ConstantExpr::get(Instruction::Add, Idx0, Combined);
1710          }
1711        }
1712
1713        NewIndices.push_back(Combined);
1714        NewIndices.insert(NewIndices.end(), IdxList.begin()+1, IdxList.end());
1715        return ConstantExpr::getGetElementPtr(CE->getOperand(0), NewIndices);
1716      }
1717    }
1718
1719    // Implement folding of:
1720    //    int* getelementptr ([2 x int]* cast ([3 x int]* %X to [2 x int]*),
1721    //                        long 0, long 0)
1722    // To: int* getelementptr ([3 x int]* %X, long 0, long 0)
1723    //
1724    if (CE->isCast() && IdxList.size() > 1 && Idx0->isNullValue())
1725      if (const PointerType *SPT =
1726          dyn_cast<PointerType>(CE->getOperand(0)->getType()))
1727        if (const ArrayType *SAT = dyn_cast<ArrayType>(SPT->getElementType()))
1728          if (const ArrayType *CAT =
1729        dyn_cast<ArrayType>(cast<PointerType>(C->getType())->getElementType()))
1730            if (CAT->getElementType() == SAT->getElementType())
1731              return ConstantExpr::getGetElementPtr(
1732                      (Constant*)CE->getOperand(0), IdxList);
1733  }
1734  return 0;
1735}
1736
1737