ConstantFold.cpp revision 78ee7b78c3c47b71c4b7a1475438d6574216a64b
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::getCast(Instruction::BitCast, CP->getOperand(1),
747                                DstEltTy));
748      return ConstantPacked::get(Result);
749    }
750
751    // If this is an int-to-fp cast ..
752    if (SrcEltTy->isIntegral()) {
753      // Ensure that it is int-to-fp cast
754      assert(DstEltTy->isFloatingPoint());
755      if (DstEltTy->getTypeID() == Type::DoubleTyID) {
756        for (unsigned i = 0; i != SrcNumElts; ++i) {
757          double V =
758            BitsToDouble(cast<ConstantInt>(CP->getOperand(i))->getZExtValue());
759          Result.push_back(ConstantFP::get(Type::DoubleTy, V));
760        }
761        return ConstantPacked::get(Result);
762      }
763      assert(DstEltTy == Type::FloatTy && "Unknown fp type!");
764      for (unsigned i = 0; i != SrcNumElts; ++i) {
765        float V =
766        BitsToFloat(cast<ConstantInt>(CP->getOperand(i))->getZExtValue());
767        Result.push_back(ConstantFP::get(Type::FloatTy, V));
768      }
769      return ConstantPacked::get(Result);
770    }
771
772    // Otherwise, this is an fp-to-int cast.
773    assert(SrcEltTy->isFloatingPoint() && DstEltTy->isIntegral());
774
775    if (SrcEltTy->getTypeID() == Type::DoubleTyID) {
776      for (unsigned i = 0; i != SrcNumElts; ++i) {
777        uint64_t V =
778          DoubleToBits(cast<ConstantFP>(CP->getOperand(i))->getValue());
779        Constant *C = ConstantInt::get(Type::ULongTy, V);
780        Result.push_back(ConstantExpr::getCast(C, DstEltTy));
781      }
782      return ConstantPacked::get(Result);
783    }
784
785    assert(SrcEltTy->getTypeID() == Type::FloatTyID);
786    for (unsigned i = 0; i != SrcNumElts; ++i) {
787      uint32_t V = FloatToBits(cast<ConstantFP>(CP->getOperand(i))->getValue());
788      Constant *C = ConstantInt::get(Type::UIntTy, V);
789      Result.push_back(ConstantExpr::getCast(C, DstEltTy));
790    }
791    return ConstantPacked::get(Result);
792  }
793
794  // Otherwise, this is a cast that changes element count and size.  Handle
795  // casts which shrink the elements here.
796
797  // FIXME: We need to know endianness to do this!
798
799  return 0;
800}
801
802/// This function determines which opcode to use to fold two constant cast
803/// expressions together. It uses CastInst::isEliminableCastPair to determine
804/// the opcode. Consequently its just a wrapper around that function.
805/// @Determine if it is valid to fold a cast of a cast
806static unsigned
807foldConstantCastPair(
808  unsigned opc,          ///< opcode of the second cast constant expression
809  const ConstantExpr*Op, ///< the first cast constant expression
810  const Type *DstTy      ///< desintation type of the first cast
811) {
812  assert(Op && Op->isCast() && "Can't fold cast of cast without a cast!");
813  assert(DstTy && DstTy->isFirstClassType() && "Invalid cast destination type");
814  assert(CastInst::isCast(opc) && "Invalid cast opcode");
815
816  // The the types and opcodes for the two Cast constant expressions
817  const Type *SrcTy = Op->getOperand(0)->getType();
818  const Type *MidTy = Op->getType();
819  Instruction::CastOps firstOp = Instruction::CastOps(Op->getOpcode());
820  Instruction::CastOps secondOp = Instruction::CastOps(opc);
821
822  // Let CastInst::isEliminableCastPair do the heavy lifting.
823  return CastInst::isEliminableCastPair(firstOp, secondOp, SrcTy, MidTy, DstTy,
824                                        Type::ULongTy);
825}
826
827Constant *llvm::ConstantFoldCastInstruction(unsigned opc, const Constant *V,
828                                            const Type *DestTy) {
829  const Type *SrcTy = V->getType();
830
831  // Handle some simple cases
832  if (SrcTy == DestTy)
833    return (Constant*)V; // no-op cast
834
835  if (isa<UndefValue>(V))
836    return UndefValue::get(DestTy);
837
838  // If the cast operand is a constant expression, there's a few things we can
839  // do to try to simplify it.
840  if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
841    if (CE->isCast()) {
842      // Try hard to fold cast of cast because they are almost always
843      // eliminable.
844      if (unsigned newOpc = foldConstantCastPair(opc, CE, DestTy))
845        return ConstantExpr::getCast(newOpc, CE->getOperand(0), DestTy);
846    } else if (CE->getOpcode() == Instruction::GetElementPtr) {
847      // If all of the indexes in the GEP are null values, there is no pointer
848      // adjustment going on.  We might as well cast the source pointer.
849      bool isAllNull = true;
850      for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
851        if (!CE->getOperand(i)->isNullValue()) {
852          isAllNull = false;
853          break;
854        }
855      if (isAllNull)
856        return ConstantExpr::getCast(CE->getOperand(0), DestTy);
857    }
858  }
859
860  // We actually have to do a cast now, but first, we might need to fix up
861  // the value of the operand.
862  switch (opc) {
863  case Instruction::FPTrunc:
864  case Instruction::Trunc:
865  case Instruction::FPExt:
866    break; // floating point input & output, no fixup needed
867  case Instruction::FPToUI: {
868    ConstRules &Rules = ConstRules::get(V, V);
869    V = Rules.castToULong(V); // make sure we get an unsigned value first
870    break;
871  }
872  case Instruction::FPToSI: {
873    ConstRules &Rules = ConstRules::get(V, V);
874    V = Rules.castToLong(V); // make sure we get a signed value first
875    break;
876  }
877  case Instruction::IntToPtr: //always treated as unsigned
878  case Instruction::UIToFP:
879  case Instruction::ZExt:
880    // A ZExt always produces an unsigned value so we need to cast the value
881    // now before we try to cast it to the destination type
882    if (isa<ConstantInt>(V))
883      V = ConstantInt::get(SrcTy->getUnsignedVersion(),
884                           cast<ConstantIntegral>(V)->getZExtValue());
885    break;
886  case Instruction::SIToFP:
887  case Instruction::SExt:
888    // A SExt always produces a signed value so we need to cast the value
889    // now before we try to cast it to the destiniation type.
890    if (isa<ConstantInt>(V))
891      V = ConstantInt::get(SrcTy->getSignedVersion(),
892                           cast<ConstantIntegral>(V)->getSExtValue());
893    break;
894
895  case Instruction::PtrToInt:
896    // Cast of a global address to boolean is always true.
897    if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
898      if (DestTy == Type::BoolTy && !GV->hasExternalWeakLinkage())
899        return ConstantBool::getTrue();
900    }
901    break;
902  case Instruction::BitCast:
903    // Check to see if we are casting a pointer to an aggregate to a pointer to
904    // the first element.  If so, return the appropriate GEP instruction.
905    if (const PointerType *PTy = dyn_cast<PointerType>(V->getType()))
906      if (const PointerType *DPTy = dyn_cast<PointerType>(DestTy)) {
907        std::vector<Value*> IdxList;
908        IdxList.push_back(Constant::getNullValue(Type::IntTy));
909        const Type *ElTy = PTy->getElementType();
910        while (ElTy != DPTy->getElementType()) {
911          if (const StructType *STy = dyn_cast<StructType>(ElTy)) {
912            if (STy->getNumElements() == 0) break;
913            ElTy = STy->getElementType(0);
914            IdxList.push_back(Constant::getNullValue(Type::UIntTy));
915          } else if (const SequentialType *STy =
916                     dyn_cast<SequentialType>(ElTy)) {
917            if (isa<PointerType>(ElTy)) break;  // Can't index into pointers!
918            ElTy = STy->getElementType();
919            IdxList.push_back(IdxList[0]);
920          } else {
921            break;
922          }
923        }
924
925        if (ElTy == DPTy->getElementType())
926          return ConstantExpr::getGetElementPtr(
927              const_cast<Constant*>(V),IdxList);
928      }
929
930    // Handle casts from one packed constant to another.  We know that the src
931    // and dest type have the same size (otherwise its an illegal cast).
932    if (const PackedType *DestPTy = dyn_cast<PackedType>(DestTy)) {
933      if (const PackedType *SrcTy = dyn_cast<PackedType>(V->getType())) {
934        assert(DestPTy->getBitWidth() == SrcTy->getBitWidth() &&
935               "Not cast between same sized vectors!");
936        // First, check for null and undef
937        if (isa<ConstantAggregateZero>(V))
938          return Constant::getNullValue(DestTy);
939        if (isa<UndefValue>(V))
940          return UndefValue::get(DestTy);
941
942        if (const ConstantPacked *CP = dyn_cast<ConstantPacked>(V)) {
943          // This is a cast from a ConstantPacked of one type to a
944          // ConstantPacked of another type.  Check to see if all elements of
945          // the input are simple.
946          bool AllSimpleConstants = true;
947          for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) {
948            if (!isa<ConstantInt>(CP->getOperand(i)) &&
949                !isa<ConstantFP>(CP->getOperand(i))) {
950              AllSimpleConstants = false;
951              break;
952            }
953          }
954
955          // If all of the elements are simple constants, we can fold this.
956          if (AllSimpleConstants)
957            return CastConstantPacked(const_cast<ConstantPacked*>(CP), DestPTy);
958        }
959      }
960    }
961
962    // Handle sign conversion for integer no-op casts. We need to cast the
963    // value to the correct signedness before we try to cast it to the
964    // destination type. Be careful to do this only for integer types.
965    if (isa<ConstantIntegral>(V) && SrcTy->isInteger()) {
966      if (SrcTy->isSigned())
967        V = ConstantInt::get(SrcTy->getUnsignedVersion(),
968                             cast<ConstantIntegral>(V)->getZExtValue());
969       else
970        V = ConstantInt::get(SrcTy->getSignedVersion(),
971                             cast<ConstantIntegral>(V)->getSExtValue());
972    }
973    break;
974  default:
975    assert(!"Invalid CE CastInst opcode");
976    break;
977  }
978
979  // Okay, no more folding possible, time to cast
980  ConstRules &Rules = ConstRules::get(V, V);
981  switch (DestTy->getTypeID()) {
982  case Type::BoolTyID:    return Rules.castToBool(V);
983  case Type::UByteTyID:   return Rules.castToUByte(V);
984  case Type::SByteTyID:   return Rules.castToSByte(V);
985  case Type::UShortTyID:  return Rules.castToUShort(V);
986  case Type::ShortTyID:   return Rules.castToShort(V);
987  case Type::UIntTyID:    return Rules.castToUInt(V);
988  case Type::IntTyID:     return Rules.castToInt(V);
989  case Type::ULongTyID:   return Rules.castToULong(V);
990  case Type::LongTyID:    return Rules.castToLong(V);
991  case Type::FloatTyID:   return Rules.castToFloat(V);
992  case Type::DoubleTyID:  return Rules.castToDouble(V);
993  case Type::PointerTyID:
994    return Rules.castToPointer(V, cast<PointerType>(DestTy));
995  // what about packed ?
996  default: return 0;
997  }
998}
999
1000Constant *llvm::ConstantFoldSelectInstruction(const Constant *Cond,
1001                                              const Constant *V1,
1002                                              const Constant *V2) {
1003  if (const ConstantBool *CB = dyn_cast<ConstantBool>(Cond))
1004    return const_cast<Constant*>(CB->getValue() ? V1 : V2);
1005
1006  if (isa<UndefValue>(V1)) return const_cast<Constant*>(V2);
1007  if (isa<UndefValue>(V2)) return const_cast<Constant*>(V1);
1008  if (isa<UndefValue>(Cond)) return const_cast<Constant*>(V1);
1009  if (V1 == V2) return const_cast<Constant*>(V1);
1010  return 0;
1011}
1012
1013Constant *llvm::ConstantFoldExtractElementInstruction(const Constant *Val,
1014                                                      const Constant *Idx) {
1015  if (isa<UndefValue>(Val))  // ee(undef, x) -> undef
1016    return UndefValue::get(cast<PackedType>(Val->getType())->getElementType());
1017  if (Val->isNullValue())  // ee(zero, x) -> zero
1018    return Constant::getNullValue(
1019                          cast<PackedType>(Val->getType())->getElementType());
1020
1021  if (const ConstantPacked *CVal = dyn_cast<ConstantPacked>(Val)) {
1022    if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Idx)) {
1023      return const_cast<Constant*>(CVal->getOperand(CIdx->getZExtValue()));
1024    } else if (isa<UndefValue>(Idx)) {
1025      // ee({w,x,y,z}, undef) -> w (an arbitrary value).
1026      return const_cast<Constant*>(CVal->getOperand(0));
1027    }
1028  }
1029  return 0;
1030}
1031
1032Constant *llvm::ConstantFoldInsertElementInstruction(const Constant *Val,
1033                                                     const Constant *Elt,
1034                                                     const Constant *Idx) {
1035  const ConstantInt *CIdx = dyn_cast<ConstantInt>(Idx);
1036  if (!CIdx) return 0;
1037  uint64_t idxVal = CIdx->getZExtValue();
1038  if (isa<UndefValue>(Val)) {
1039    // Insertion of scalar constant into packed undef
1040    // Optimize away insertion of undef
1041    if (isa<UndefValue>(Elt))
1042      return const_cast<Constant*>(Val);
1043    // Otherwise break the aggregate undef into multiple undefs and do
1044    // the insertion
1045    unsigned numOps =
1046      cast<PackedType>(Val->getType())->getNumElements();
1047    std::vector<Constant*> Ops;
1048    Ops.reserve(numOps);
1049    for (unsigned i = 0; i < numOps; ++i) {
1050      const Constant *Op =
1051        (i == idxVal) ? Elt : UndefValue::get(Elt->getType());
1052      Ops.push_back(const_cast<Constant*>(Op));
1053    }
1054    return ConstantPacked::get(Ops);
1055  }
1056  if (isa<ConstantAggregateZero>(Val)) {
1057    // Insertion of scalar constant into packed aggregate zero
1058    // Optimize away insertion of zero
1059    if (Elt->isNullValue())
1060      return const_cast<Constant*>(Val);
1061    // Otherwise break the aggregate zero into multiple zeros and do
1062    // the insertion
1063    unsigned numOps =
1064      cast<PackedType>(Val->getType())->getNumElements();
1065    std::vector<Constant*> Ops;
1066    Ops.reserve(numOps);
1067    for (unsigned i = 0; i < numOps; ++i) {
1068      const Constant *Op =
1069        (i == idxVal) ? Elt : Constant::getNullValue(Elt->getType());
1070      Ops.push_back(const_cast<Constant*>(Op));
1071    }
1072    return ConstantPacked::get(Ops);
1073  }
1074  if (const ConstantPacked *CVal = dyn_cast<ConstantPacked>(Val)) {
1075    // Insertion of scalar constant into packed constant
1076    std::vector<Constant*> Ops;
1077    Ops.reserve(CVal->getNumOperands());
1078    for (unsigned i = 0; i < CVal->getNumOperands(); ++i) {
1079      const Constant *Op =
1080        (i == idxVal) ? Elt : cast<Constant>(CVal->getOperand(i));
1081      Ops.push_back(const_cast<Constant*>(Op));
1082    }
1083    return ConstantPacked::get(Ops);
1084  }
1085  return 0;
1086}
1087
1088Constant *llvm::ConstantFoldShuffleVectorInstruction(const Constant *V1,
1089                                                     const Constant *V2,
1090                                                     const Constant *Mask) {
1091  // TODO:
1092  return 0;
1093}
1094
1095
1096/// isZeroSizedType - This type is zero sized if its an array or structure of
1097/// zero sized types.  The only leaf zero sized type is an empty structure.
1098static bool isMaybeZeroSizedType(const Type *Ty) {
1099  if (isa<OpaqueType>(Ty)) return true;  // Can't say.
1100  if (const StructType *STy = dyn_cast<StructType>(Ty)) {
1101
1102    // If all of elements have zero size, this does too.
1103    for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1104      if (!isMaybeZeroSizedType(STy->getElementType(i))) return false;
1105    return true;
1106
1107  } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
1108    return isMaybeZeroSizedType(ATy->getElementType());
1109  }
1110  return false;
1111}
1112
1113/// IdxCompare - Compare the two constants as though they were getelementptr
1114/// indices.  This allows coersion of the types to be the same thing.
1115///
1116/// If the two constants are the "same" (after coersion), return 0.  If the
1117/// first is less than the second, return -1, if the second is less than the
1118/// first, return 1.  If the constants are not integral, return -2.
1119///
1120static int IdxCompare(Constant *C1, Constant *C2, const Type *ElTy) {
1121  if (C1 == C2) return 0;
1122
1123  // Ok, we found a different index.  Are either of the operands ConstantExprs?
1124  // If so, we can't do anything with them.
1125  if (!isa<ConstantInt>(C1) || !isa<ConstantInt>(C2))
1126    return -2; // don't know!
1127
1128  // Ok, we have two differing integer indices.  Sign extend them to be the same
1129  // type.  Long is always big enough, so we use it.
1130  if (C1->getType() != Type::LongTy && C1->getType() != Type::ULongTy)
1131    C1 = ConstantExpr::getSignExtend(C1, Type::LongTy);
1132  else
1133    C1 = ConstantExpr::getBitCast(C1, Type::LongTy);
1134  if (C2->getType() != Type::LongTy && C1->getType() != Type::ULongTy)
1135    C2 = ConstantExpr::getSignExtend(C2, Type::LongTy);
1136  else
1137    C2 = ConstantExpr::getBitCast(C2, Type::LongTy);
1138
1139  if (C1 == C2) return 0;  // Are they just differing types?
1140
1141  // If the type being indexed over is really just a zero sized type, there is
1142  // no pointer difference being made here.
1143  if (isMaybeZeroSizedType(ElTy))
1144    return -2; // dunno.
1145
1146  // If they are really different, now that they are the same type, then we
1147  // found a difference!
1148  if (cast<ConstantInt>(C1)->getSExtValue() <
1149      cast<ConstantInt>(C2)->getSExtValue())
1150    return -1;
1151  else
1152    return 1;
1153}
1154
1155/// evaluateRelation - This function determines if there is anything we can
1156/// decide about the two constants provided.  This doesn't need to handle simple
1157/// things like integer comparisons, but should instead handle ConstantExprs
1158/// and GlobalValuess.  If we can determine that the two constants have a
1159/// particular relation to each other, we should return the corresponding SetCC
1160/// code, otherwise return Instruction::BinaryOpsEnd.
1161///
1162/// To simplify this code we canonicalize the relation so that the first
1163/// operand is always the most "complex" of the two.  We consider simple
1164/// constants (like ConstantInt) to be the simplest, followed by
1165/// GlobalValues, followed by ConstantExpr's (the most complex).
1166///
1167static Instruction::BinaryOps evaluateRelation(Constant *V1, Constant *V2) {
1168  assert(V1->getType() == V2->getType() &&
1169         "Cannot compare different types of values!");
1170  if (V1 == V2) return Instruction::SetEQ;
1171
1172  if (!isa<ConstantExpr>(V1) && !isa<GlobalValue>(V1)) {
1173    if (!isa<GlobalValue>(V2) && !isa<ConstantExpr>(V2)) {
1174      // We distilled this down to a simple case, use the standard constant
1175      // folder.
1176      ConstantBool *R = dyn_cast<ConstantBool>(ConstantExpr::getSetEQ(V1, V2));
1177      if (R && R->getValue()) return Instruction::SetEQ;
1178      R = dyn_cast<ConstantBool>(ConstantExpr::getSetLT(V1, V2));
1179      if (R && R->getValue()) return Instruction::SetLT;
1180      R = dyn_cast<ConstantBool>(ConstantExpr::getSetGT(V1, V2));
1181      if (R && R->getValue()) return Instruction::SetGT;
1182
1183      // If we couldn't figure it out, bail.
1184      return Instruction::BinaryOpsEnd;
1185    }
1186
1187    // If the first operand is simple, swap operands.
1188    Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1);
1189    if (SwappedRelation != Instruction::BinaryOpsEnd)
1190      return SetCondInst::getSwappedCondition(SwappedRelation);
1191
1192  } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(V1)) {
1193    if (isa<ConstantExpr>(V2)) {  // Swap as necessary.
1194      Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1);
1195      if (SwappedRelation != Instruction::BinaryOpsEnd)
1196        return SetCondInst::getSwappedCondition(SwappedRelation);
1197      else
1198        return Instruction::BinaryOpsEnd;
1199    }
1200
1201    // Now we know that the RHS is a GlobalValue or simple constant,
1202    // which (since the types must match) means that it's a ConstantPointerNull.
1203    if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) {
1204      assert(CPR1 != CPR2 &&
1205             "GVs for the same value exist at different addresses??");
1206      // FIXME: If both globals are external weak, they might both be null!
1207      return Instruction::SetNE;
1208    } else {
1209      assert(isa<ConstantPointerNull>(V2) && "Canonicalization guarantee!");
1210      // Global can never be null.  FIXME: if we implement external weak
1211      // linkage, this is not necessarily true!
1212      return Instruction::SetNE;
1213    }
1214
1215  } else {
1216    // Ok, the LHS is known to be a constantexpr.  The RHS can be any of a
1217    // constantexpr, a CPR, or a simple constant.
1218    ConstantExpr *CE1 = cast<ConstantExpr>(V1);
1219    Constant *CE1Op0 = CE1->getOperand(0);
1220
1221    switch (CE1->getOpcode()) {
1222    case Instruction::Trunc:
1223    case Instruction::FPTrunc:
1224    case Instruction::FPExt:
1225    case Instruction::FPToUI:
1226    case Instruction::FPToSI:
1227      break; // We don't do anything with floating point.
1228    case Instruction::ZExt:
1229    case Instruction::SExt:
1230    case Instruction::UIToFP:
1231    case Instruction::SIToFP:
1232    case Instruction::PtrToInt:
1233    case Instruction::IntToPtr:
1234    case Instruction::BitCast:
1235      // If the cast is not actually changing bits, and the second operand is a
1236      // null pointer, do the comparison with the pre-casted value.
1237      if (V2->isNullValue() &&
1238          (isa<PointerType>(CE1->getType()) || CE1->getType()->isIntegral()))
1239        return evaluateRelation(CE1Op0,
1240                                Constant::getNullValue(CE1Op0->getType()));
1241
1242      // If the dest type is a pointer type, and the RHS is a constantexpr cast
1243      // from the same type as the src of the LHS, evaluate the inputs.  This is
1244      // important for things like "seteq (cast 4 to int*), (cast 5 to int*)",
1245      // which happens a lot in compilers with tagged integers.
1246      if (ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2))
1247        if (isa<PointerType>(CE1->getType()) && CE2->isCast() &&
1248            CE1->getOperand(0)->getType() == CE2->getOperand(0)->getType() &&
1249            CE1->getOperand(0)->getType()->isIntegral()) {
1250          return evaluateRelation(CE1->getOperand(0), CE2->getOperand(0));
1251        }
1252      break;
1253
1254    case Instruction::GetElementPtr:
1255      // Ok, since this is a getelementptr, we know that the constant has a
1256      // pointer type.  Check the various cases.
1257      if (isa<ConstantPointerNull>(V2)) {
1258        // If we are comparing a GEP to a null pointer, check to see if the base
1259        // of the GEP equals the null pointer.
1260        if (isa<GlobalValue>(CE1Op0)) {
1261          // FIXME: this is not true when we have external weak references!
1262          // No offset can go from a global to a null pointer.
1263          return Instruction::SetGT;
1264        } else if (isa<ConstantPointerNull>(CE1Op0)) {
1265          // If we are indexing from a null pointer, check to see if we have any
1266          // non-zero indices.
1267          for (unsigned i = 1, e = CE1->getNumOperands(); i != e; ++i)
1268            if (!CE1->getOperand(i)->isNullValue())
1269              // Offsetting from null, must not be equal.
1270              return Instruction::SetGT;
1271          // Only zero indexes from null, must still be zero.
1272          return Instruction::SetEQ;
1273        }
1274        // Otherwise, we can't really say if the first operand is null or not.
1275      } else if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) {
1276        if (isa<ConstantPointerNull>(CE1Op0)) {
1277          // FIXME: This is not true with external weak references.
1278          return Instruction::SetLT;
1279        } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(CE1Op0)) {
1280          if (CPR1 == CPR2) {
1281            // If this is a getelementptr of the same global, then it must be
1282            // different.  Because the types must match, the getelementptr could
1283            // only have at most one index, and because we fold getelementptr's
1284            // with a single zero index, it must be nonzero.
1285            assert(CE1->getNumOperands() == 2 &&
1286                   !CE1->getOperand(1)->isNullValue() &&
1287                   "Suprising getelementptr!");
1288            return Instruction::SetGT;
1289          } else {
1290            // If they are different globals, we don't know what the value is,
1291            // but they can't be equal.
1292            return Instruction::SetNE;
1293          }
1294        }
1295      } else {
1296        const ConstantExpr *CE2 = cast<ConstantExpr>(V2);
1297        const Constant *CE2Op0 = CE2->getOperand(0);
1298
1299        // There are MANY other foldings that we could perform here.  They will
1300        // probably be added on demand, as they seem needed.
1301        switch (CE2->getOpcode()) {
1302        default: break;
1303        case Instruction::GetElementPtr:
1304          // By far the most common case to handle is when the base pointers are
1305          // obviously to the same or different globals.
1306          if (isa<GlobalValue>(CE1Op0) && isa<GlobalValue>(CE2Op0)) {
1307            if (CE1Op0 != CE2Op0) // Don't know relative ordering, but not equal
1308              return Instruction::SetNE;
1309            // Ok, we know that both getelementptr instructions are based on the
1310            // same global.  From this, we can precisely determine the relative
1311            // ordering of the resultant pointers.
1312            unsigned i = 1;
1313
1314            // Compare all of the operands the GEP's have in common.
1315            gep_type_iterator GTI = gep_type_begin(CE1);
1316            for (;i != CE1->getNumOperands() && i != CE2->getNumOperands();
1317                 ++i, ++GTI)
1318              switch (IdxCompare(CE1->getOperand(i), CE2->getOperand(i),
1319                                 GTI.getIndexedType())) {
1320              case -1: return Instruction::SetLT;
1321              case 1:  return Instruction::SetGT;
1322              case -2: return Instruction::BinaryOpsEnd;
1323              }
1324
1325            // Ok, we ran out of things they have in common.  If any leftovers
1326            // are non-zero then we have a difference, otherwise we are equal.
1327            for (; i < CE1->getNumOperands(); ++i)
1328              if (!CE1->getOperand(i)->isNullValue())
1329                if (isa<ConstantIntegral>(CE1->getOperand(i)))
1330                  return Instruction::SetGT;
1331                else
1332                  return Instruction::BinaryOpsEnd; // Might be equal.
1333
1334            for (; i < CE2->getNumOperands(); ++i)
1335              if (!CE2->getOperand(i)->isNullValue())
1336                if (isa<ConstantIntegral>(CE2->getOperand(i)))
1337                  return Instruction::SetLT;
1338                else
1339                  return Instruction::BinaryOpsEnd; // Might be equal.
1340            return Instruction::SetEQ;
1341          }
1342        }
1343      }
1344
1345    default:
1346      break;
1347    }
1348  }
1349
1350  return Instruction::BinaryOpsEnd;
1351}
1352
1353Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode,
1354                                              const Constant *V1,
1355                                              const Constant *V2) {
1356  Constant *C = 0;
1357  switch (Opcode) {
1358  default:                   break;
1359  case Instruction::Add:     C = ConstRules::get(V1, V2).add(V1, V2); break;
1360  case Instruction::Sub:     C = ConstRules::get(V1, V2).sub(V1, V2); break;
1361  case Instruction::Mul:     C = ConstRules::get(V1, V2).mul(V1, V2); break;
1362  case Instruction::UDiv:    C = ConstRules::get(V1, V2).udiv(V1, V2); break;
1363  case Instruction::SDiv:    C = ConstRules::get(V1, V2).sdiv(V1, V2); break;
1364  case Instruction::FDiv:    C = ConstRules::get(V1, V2).fdiv(V1, V2); break;
1365  case Instruction::URem:    C = ConstRules::get(V1, V2).urem(V1, V2); break;
1366  case Instruction::SRem:    C = ConstRules::get(V1, V2).srem(V1, V2); break;
1367  case Instruction::FRem:    C = ConstRules::get(V1, V2).frem(V1, V2); break;
1368  case Instruction::And:     C = ConstRules::get(V1, V2).op_and(V1, V2); break;
1369  case Instruction::Or:      C = ConstRules::get(V1, V2).op_or (V1, V2); break;
1370  case Instruction::Xor:     C = ConstRules::get(V1, V2).op_xor(V1, V2); break;
1371  case Instruction::Shl:     C = ConstRules::get(V1, V2).shl(V1, V2); break;
1372  case Instruction::LShr:    C = ConstRules::get(V1, V2).lshr(V1, V2); break;
1373  case Instruction::AShr:    C = ConstRules::get(V1, V2).ashr(V1, V2); break;
1374  case Instruction::SetEQ:   C = ConstRules::get(V1, V2).equalto(V1, V2); break;
1375  case Instruction::SetLT:   C = ConstRules::get(V1, V2).lessthan(V1, V2);break;
1376  case Instruction::SetGT:   C = ConstRules::get(V1, V2).lessthan(V2, V1);break;
1377  case Instruction::SetNE:   // V1 != V2  ===  !(V1 == V2)
1378    C = ConstRules::get(V1, V2).equalto(V1, V2);
1379    if (C) return ConstantExpr::getNot(C);
1380    break;
1381  case Instruction::SetLE:   // V1 <= V2  ===  !(V2 < V1)
1382    C = ConstRules::get(V1, V2).lessthan(V2, V1);
1383    if (C) return ConstantExpr::getNot(C);
1384    break;
1385  case Instruction::SetGE:   // V1 >= V2  ===  !(V1 < V2)
1386    C = ConstRules::get(V1, V2).lessthan(V1, V2);
1387    if (C) return ConstantExpr::getNot(C);
1388    break;
1389  }
1390
1391  // If we successfully folded the expression, return it now.
1392  if (C) return C;
1393
1394  if (SetCondInst::isComparison(Opcode)) {
1395    if (isa<UndefValue>(V1) || isa<UndefValue>(V2))
1396      return UndefValue::get(Type::BoolTy);
1397    switch (evaluateRelation(const_cast<Constant*>(V1),
1398                             const_cast<Constant*>(V2))) {
1399    default: assert(0 && "Unknown relational!");
1400    case Instruction::BinaryOpsEnd:
1401      break;  // Couldn't determine anything about these constants.
1402    case Instruction::SetEQ:   // We know the constants are equal!
1403      // If we know the constants are equal, we can decide the result of this
1404      // computation precisely.
1405      return ConstantBool::get(Opcode == Instruction::SetEQ ||
1406                               Opcode == Instruction::SetLE ||
1407                               Opcode == Instruction::SetGE);
1408    case Instruction::SetLT:
1409      // If we know that V1 < V2, we can decide the result of this computation
1410      // precisely.
1411      return ConstantBool::get(Opcode == Instruction::SetLT ||
1412                               Opcode == Instruction::SetNE ||
1413                               Opcode == Instruction::SetLE);
1414    case Instruction::SetGT:
1415      // If we know that V1 > V2, we can decide the result of this computation
1416      // precisely.
1417      return ConstantBool::get(Opcode == Instruction::SetGT ||
1418                               Opcode == Instruction::SetNE ||
1419                               Opcode == Instruction::SetGE);
1420    case Instruction::SetLE:
1421      // If we know that V1 <= V2, we can only partially decide this relation.
1422      if (Opcode == Instruction::SetGT) return ConstantBool::getFalse();
1423      if (Opcode == Instruction::SetLT) return ConstantBool::getTrue();
1424      break;
1425
1426    case Instruction::SetGE:
1427      // If we know that V1 >= V2, we can only partially decide this relation.
1428      if (Opcode == Instruction::SetLT) return ConstantBool::getFalse();
1429      if (Opcode == Instruction::SetGT) return ConstantBool::getTrue();
1430      break;
1431
1432    case Instruction::SetNE:
1433      // If we know that V1 != V2, we can only partially decide this relation.
1434      if (Opcode == Instruction::SetEQ) return ConstantBool::getFalse();
1435      if (Opcode == Instruction::SetNE) return ConstantBool::getTrue();
1436      break;
1437    }
1438  }
1439
1440  if (isa<UndefValue>(V1) || isa<UndefValue>(V2)) {
1441    switch (Opcode) {
1442    case Instruction::Add:
1443    case Instruction::Sub:
1444    case Instruction::Xor:
1445      return UndefValue::get(V1->getType());
1446
1447    case Instruction::Mul:
1448    case Instruction::And:
1449      return Constant::getNullValue(V1->getType());
1450    case Instruction::UDiv:
1451    case Instruction::SDiv:
1452    case Instruction::FDiv:
1453    case Instruction::URem:
1454    case Instruction::SRem:
1455    case Instruction::FRem:
1456      if (!isa<UndefValue>(V2))                    // undef / X -> 0
1457        return Constant::getNullValue(V1->getType());
1458      return const_cast<Constant*>(V2);            // X / undef -> undef
1459    case Instruction::Or:                          // X | undef -> -1
1460      return ConstantInt::getAllOnesValue(V1->getType());
1461    case Instruction::LShr:
1462      if (isa<UndefValue>(V2) && isa<UndefValue>(V1))
1463        return const_cast<Constant*>(V1);           // undef lshr undef -> undef
1464      return Constant::getNullValue(V1->getType()); // X lshr undef -> 0
1465                                                    // undef lshr X -> 0
1466    case Instruction::AShr:
1467      if (!isa<UndefValue>(V2))
1468        return const_cast<Constant*>(V1);           // undef ashr X --> undef
1469      else if (isa<UndefValue>(V1))
1470        return const_cast<Constant*>(V1);           // undef ashr undef -> undef
1471      else
1472        return const_cast<Constant*>(V1);           // X ashr undef --> X
1473    case Instruction::Shl:
1474      // undef << X -> 0   or   X << undef -> 0
1475      return Constant::getNullValue(V1->getType());
1476    }
1477  }
1478
1479  if (const ConstantExpr *CE1 = dyn_cast<ConstantExpr>(V1)) {
1480    if (isa<ConstantExpr>(V2)) {
1481      // There are many possible foldings we could do here.  We should probably
1482      // at least fold add of a pointer with an integer into the appropriate
1483      // getelementptr.  This will improve alias analysis a bit.
1484    } else {
1485      // Just implement a couple of simple identities.
1486      switch (Opcode) {
1487      case Instruction::Add:
1488        if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X + 0 == X
1489        break;
1490      case Instruction::Sub:
1491        if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X - 0 == X
1492        break;
1493      case Instruction::Mul:
1494        if (V2->isNullValue()) return const_cast<Constant*>(V2);  // X * 0 == 0
1495        if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1496          if (CI->getZExtValue() == 1)
1497            return const_cast<Constant*>(V1);                     // X * 1 == X
1498        break;
1499      case Instruction::UDiv:
1500      case Instruction::SDiv:
1501        if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1502          if (CI->getZExtValue() == 1)
1503            return const_cast<Constant*>(V1);                     // X / 1 == X
1504        break;
1505      case Instruction::URem:
1506      case Instruction::SRem:
1507        if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1508          if (CI->getZExtValue() == 1)
1509            return Constant::getNullValue(CI->getType());         // X % 1 == 0
1510        break;
1511      case Instruction::And:
1512        if (cast<ConstantIntegral>(V2)->isAllOnesValue())
1513          return const_cast<Constant*>(V1);                       // X & -1 == X
1514        if (V2->isNullValue()) return const_cast<Constant*>(V2);  // X & 0 == 0
1515        if (CE1->isCast() && isa<GlobalValue>(CE1->getOperand(0))) {
1516          GlobalValue *CPR = cast<GlobalValue>(CE1->getOperand(0));
1517
1518          // Functions are at least 4-byte aligned.  If and'ing the address of a
1519          // function with a constant < 4, fold it to zero.
1520          if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1521            if (CI->getZExtValue() < 4 && isa<Function>(CPR))
1522              return Constant::getNullValue(CI->getType());
1523        }
1524        break;
1525      case Instruction::Or:
1526        if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X | 0 == X
1527        if (cast<ConstantIntegral>(V2)->isAllOnesValue())
1528          return const_cast<Constant*>(V2);  // X | -1 == -1
1529        break;
1530      case Instruction::Xor:
1531        if (V2->isNullValue()) return const_cast<Constant*>(V1);  // X ^ 0 == X
1532        break;
1533      }
1534    }
1535
1536  } else if (isa<ConstantExpr>(V2)) {
1537    // If V2 is a constant expr and V1 isn't, flop them around and fold the
1538    // other way if possible.
1539    switch (Opcode) {
1540    case Instruction::Add:
1541    case Instruction::Mul:
1542    case Instruction::And:
1543    case Instruction::Or:
1544    case Instruction::Xor:
1545    case Instruction::SetEQ:
1546    case Instruction::SetNE:
1547      // No change of opcode required.
1548      return ConstantFoldBinaryInstruction(Opcode, V2, V1);
1549
1550    case Instruction::SetLT:
1551    case Instruction::SetGT:
1552    case Instruction::SetLE:
1553    case Instruction::SetGE:
1554      // Change the opcode as necessary to swap the operands.
1555      Opcode = SetCondInst::getSwappedCondition((Instruction::BinaryOps)Opcode);
1556      return ConstantFoldBinaryInstruction(Opcode, V2, V1);
1557
1558    case Instruction::Shl:
1559    case Instruction::LShr:
1560    case Instruction::AShr:
1561    case Instruction::Sub:
1562    case Instruction::SDiv:
1563    case Instruction::UDiv:
1564    case Instruction::FDiv:
1565    case Instruction::URem:
1566    case Instruction::SRem:
1567    case Instruction::FRem:
1568    default:  // These instructions cannot be flopped around.
1569      break;
1570    }
1571  }
1572  return 0;
1573}
1574
1575Constant *llvm::ConstantFoldGetElementPtr(const Constant *C,
1576                                          const std::vector<Value*> &IdxList) {
1577  if (IdxList.size() == 0 ||
1578      (IdxList.size() == 1 && cast<Constant>(IdxList[0])->isNullValue()))
1579    return const_cast<Constant*>(C);
1580
1581  if (isa<UndefValue>(C)) {
1582    const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList,
1583                                                       true);
1584    assert(Ty != 0 && "Invalid indices for GEP!");
1585    return UndefValue::get(PointerType::get(Ty));
1586  }
1587
1588  Constant *Idx0 = cast<Constant>(IdxList[0]);
1589  if (C->isNullValue()) {
1590    bool isNull = true;
1591    for (unsigned i = 0, e = IdxList.size(); i != e; ++i)
1592      if (!cast<Constant>(IdxList[i])->isNullValue()) {
1593        isNull = false;
1594        break;
1595      }
1596    if (isNull) {
1597      const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList,
1598                                                         true);
1599      assert(Ty != 0 && "Invalid indices for GEP!");
1600      return ConstantPointerNull::get(PointerType::get(Ty));
1601    }
1602
1603    if (IdxList.size() == 1) {
1604      const Type *ElTy = cast<PointerType>(C->getType())->getElementType();
1605      if (uint32_t ElSize = ElTy->getPrimitiveSize()) {
1606        // gep null, C is equal to C*sizeof(nullty).  If nullty is a known llvm
1607        // type, we can statically fold this.
1608        Constant *R = ConstantInt::get(Type::UIntTy, ElSize);
1609        R = ConstantExpr::getCast(R, Idx0->getType());
1610        R = ConstantExpr::getMul(R, Idx0);
1611        return ConstantExpr::getCast(R, C->getType());
1612      }
1613    }
1614  }
1615
1616  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(const_cast<Constant*>(C))) {
1617    // Combine Indices - If the source pointer to this getelementptr instruction
1618    // is a getelementptr instruction, combine the indices of the two
1619    // getelementptr instructions into a single instruction.
1620    //
1621    if (CE->getOpcode() == Instruction::GetElementPtr) {
1622      const Type *LastTy = 0;
1623      for (gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
1624           I != E; ++I)
1625        LastTy = *I;
1626
1627      if ((LastTy && isa<ArrayType>(LastTy)) || Idx0->isNullValue()) {
1628        std::vector<Value*> NewIndices;
1629        NewIndices.reserve(IdxList.size() + CE->getNumOperands());
1630        for (unsigned i = 1, e = CE->getNumOperands()-1; i != e; ++i)
1631          NewIndices.push_back(CE->getOperand(i));
1632
1633        // Add the last index of the source with the first index of the new GEP.
1634        // Make sure to handle the case when they are actually different types.
1635        Constant *Combined = CE->getOperand(CE->getNumOperands()-1);
1636        // Otherwise it must be an array.
1637        if (!Idx0->isNullValue()) {
1638          const Type *IdxTy = Combined->getType();
1639          if (IdxTy != Idx0->getType()) IdxTy = Type::LongTy;
1640          Combined =
1641            ConstantExpr::get(Instruction::Add,
1642                              ConstantExpr::getCast(Idx0, IdxTy),
1643                              ConstantExpr::getCast(Combined, IdxTy));
1644        }
1645
1646        NewIndices.push_back(Combined);
1647        NewIndices.insert(NewIndices.end(), IdxList.begin()+1, IdxList.end());
1648        return ConstantExpr::getGetElementPtr(CE->getOperand(0), NewIndices);
1649      }
1650    }
1651
1652    // Implement folding of:
1653    //    int* getelementptr ([2 x int]* cast ([3 x int]* %X to [2 x int]*),
1654    //                        long 0, long 0)
1655    // To: int* getelementptr ([3 x int]* %X, long 0, long 0)
1656    //
1657    if (CE->isCast() && IdxList.size() > 1 && Idx0->isNullValue())
1658      if (const PointerType *SPT =
1659          dyn_cast<PointerType>(CE->getOperand(0)->getType()))
1660        if (const ArrayType *SAT = dyn_cast<ArrayType>(SPT->getElementType()))
1661          if (const ArrayType *CAT =
1662        dyn_cast<ArrayType>(cast<PointerType>(C->getType())->getElementType()))
1663            if (CAT->getElementType() == SAT->getElementType())
1664              return ConstantExpr::getGetElementPtr(
1665                      (Constant*)CE->getOperand(0), IdxList);
1666  }
1667  return 0;
1668}
1669
1670