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