1 //===- ConstantFolding.cpp - LLVM constant folder -------------------------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
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.
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.
19 //===----------------------------------------------------------------------===//
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 "llvm/Support/MathExtras.h"
35 virtual ~ConstRules() {}
37 // Binary Operators...
38 virtual Constant *add(const Constant *V1, const Constant *V2) const = 0;
39 virtual Constant *sub(const Constant *V1, const Constant *V2) const = 0;
40 virtual Constant *mul(const Constant *V1, const Constant *V2) const = 0;
41 virtual Constant *div(const Constant *V1, const Constant *V2) const = 0;
42 virtual Constant *rem(const Constant *V1, const Constant *V2) const = 0;
43 virtual Constant *op_and(const Constant *V1, const Constant *V2) const = 0;
44 virtual Constant *op_or (const Constant *V1, const Constant *V2) const = 0;
45 virtual Constant *op_xor(const Constant *V1, const Constant *V2) const = 0;
46 virtual Constant *shl(const Constant *V1, const Constant *V2) const = 0;
47 virtual Constant *shr(const Constant *V1, const Constant *V2) const = 0;
48 virtual Constant *lessthan(const Constant *V1, const Constant *V2) const =0;
49 virtual Constant *equalto(const Constant *V1, const Constant *V2) const = 0;
52 virtual Constant *castToBool (const Constant *V) const = 0;
53 virtual Constant *castToSByte (const Constant *V) const = 0;
54 virtual Constant *castToUByte (const Constant *V) const = 0;
55 virtual Constant *castToShort (const Constant *V) const = 0;
56 virtual Constant *castToUShort(const Constant *V) const = 0;
57 virtual Constant *castToInt (const Constant *V) const = 0;
58 virtual Constant *castToUInt (const Constant *V) const = 0;
59 virtual Constant *castToLong (const Constant *V) const = 0;
60 virtual Constant *castToULong (const Constant *V) const = 0;
61 virtual Constant *castToFloat (const Constant *V) const = 0;
62 virtual Constant *castToDouble(const Constant *V) const = 0;
63 virtual Constant *castToPointer(const Constant *V,
64 const PointerType *Ty) const = 0;
66 // ConstRules::get - Return an instance of ConstRules for the specified
69 static ConstRules &get(const Constant *V1, const Constant *V2);
71 ConstRules(const ConstRules &); // Do not implement
72 ConstRules &operator=(const ConstRules &); // Do not implement
77 //===----------------------------------------------------------------------===//
78 // TemplateRules Class
79 //===----------------------------------------------------------------------===//
81 // TemplateRules - Implement a subclass of ConstRules that provides all
82 // operations as noops. All other rules classes inherit from this class so
83 // that if functionality is needed in the future, it can simply be added here
84 // and to ConstRules without changing anything else...
86 // This class also provides subclasses with typesafe implementations of methods
87 // so that don't have to do type casting.
90 template<class ArgType, class SubClassName>
91 class TemplateRules : public ConstRules {
94 //===--------------------------------------------------------------------===//
95 // Redirecting functions that cast to the appropriate types
96 //===--------------------------------------------------------------------===//
98 virtual Constant *add(const Constant *V1, const Constant *V2) const {
99 return SubClassName::Add((const ArgType *)V1, (const ArgType *)V2);
101 virtual Constant *sub(const Constant *V1, const Constant *V2) const {
102 return SubClassName::Sub((const ArgType *)V1, (const ArgType *)V2);
104 virtual Constant *mul(const Constant *V1, const Constant *V2) const {
105 return SubClassName::Mul((const ArgType *)V1, (const ArgType *)V2);
107 virtual Constant *div(const Constant *V1, const Constant *V2) const {
108 return SubClassName::Div((const ArgType *)V1, (const ArgType *)V2);
110 virtual Constant *rem(const Constant *V1, const Constant *V2) const {
111 return SubClassName::Rem((const ArgType *)V1, (const ArgType *)V2);
113 virtual Constant *op_and(const Constant *V1, const Constant *V2) const {
114 return SubClassName::And((const ArgType *)V1, (const ArgType *)V2);
116 virtual Constant *op_or(const Constant *V1, const Constant *V2) const {
117 return SubClassName::Or((const ArgType *)V1, (const ArgType *)V2);
119 virtual Constant *op_xor(const Constant *V1, const Constant *V2) const {
120 return SubClassName::Xor((const ArgType *)V1, (const ArgType *)V2);
122 virtual Constant *shl(const Constant *V1, const Constant *V2) const {
123 return SubClassName::Shl((const ArgType *)V1, (const ArgType *)V2);
125 virtual Constant *shr(const Constant *V1, const Constant *V2) const {
126 return SubClassName::Shr((const ArgType *)V1, (const ArgType *)V2);
129 virtual Constant *lessthan(const Constant *V1, const Constant *V2) const {
130 return SubClassName::LessThan((const ArgType *)V1, (const ArgType *)V2);
132 virtual Constant *equalto(const Constant *V1, const Constant *V2) const {
133 return SubClassName::EqualTo((const ArgType *)V1, (const ArgType *)V2);
136 // Casting operators. ick
137 virtual Constant *castToBool(const Constant *V) const {
138 return SubClassName::CastToBool((const ArgType*)V);
140 virtual Constant *castToSByte(const Constant *V) const {
141 return SubClassName::CastToSByte((const ArgType*)V);
143 virtual Constant *castToUByte(const Constant *V) const {
144 return SubClassName::CastToUByte((const ArgType*)V);
146 virtual Constant *castToShort(const Constant *V) const {
147 return SubClassName::CastToShort((const ArgType*)V);
149 virtual Constant *castToUShort(const Constant *V) const {
150 return SubClassName::CastToUShort((const ArgType*)V);
152 virtual Constant *castToInt(const Constant *V) const {
153 return SubClassName::CastToInt((const ArgType*)V);
155 virtual Constant *castToUInt(const Constant *V) const {
156 return SubClassName::CastToUInt((const ArgType*)V);
158 virtual Constant *castToLong(const Constant *V) const {
159 return SubClassName::CastToLong((const ArgType*)V);
161 virtual Constant *castToULong(const Constant *V) const {
162 return SubClassName::CastToULong((const ArgType*)V);
164 virtual Constant *castToFloat(const Constant *V) const {
165 return SubClassName::CastToFloat((const ArgType*)V);
167 virtual Constant *castToDouble(const Constant *V) const {
168 return SubClassName::CastToDouble((const ArgType*)V);
170 virtual Constant *castToPointer(const Constant *V,
171 const PointerType *Ty) const {
172 return SubClassName::CastToPointer((const ArgType*)V, Ty);
175 //===--------------------------------------------------------------------===//
176 // Default "noop" implementations
177 //===--------------------------------------------------------------------===//
179 static Constant *Add(const ArgType *V1, const ArgType *V2) { return 0; }
180 static Constant *Sub(const ArgType *V1, const ArgType *V2) { return 0; }
181 static Constant *Mul(const ArgType *V1, const ArgType *V2) { return 0; }
182 static Constant *Div(const ArgType *V1, const ArgType *V2) { return 0; }
183 static Constant *Rem(const ArgType *V1, const ArgType *V2) { return 0; }
184 static Constant *And(const ArgType *V1, const ArgType *V2) { return 0; }
185 static Constant *Or (const ArgType *V1, const ArgType *V2) { return 0; }
186 static Constant *Xor(const ArgType *V1, const ArgType *V2) { return 0; }
187 static Constant *Shl(const ArgType *V1, const ArgType *V2) { return 0; }
188 static Constant *Shr(const ArgType *V1, const ArgType *V2) { return 0; }
189 static Constant *LessThan(const ArgType *V1, const ArgType *V2) {
192 static Constant *EqualTo(const ArgType *V1, const ArgType *V2) {
196 // Casting operators. ick
197 static Constant *CastToBool (const Constant *V) { return 0; }
198 static Constant *CastToSByte (const Constant *V) { return 0; }
199 static Constant *CastToUByte (const Constant *V) { return 0; }
200 static Constant *CastToShort (const Constant *V) { return 0; }
201 static Constant *CastToUShort(const Constant *V) { return 0; }
202 static Constant *CastToInt (const Constant *V) { return 0; }
203 static Constant *CastToUInt (const Constant *V) { return 0; }
204 static Constant *CastToLong (const Constant *V) { return 0; }
205 static Constant *CastToULong (const Constant *V) { return 0; }
206 static Constant *CastToFloat (const Constant *V) { return 0; }
207 static Constant *CastToDouble(const Constant *V) { return 0; }
208 static Constant *CastToPointer(const Constant *,
209 const PointerType *) {return 0;}
212 virtual ~TemplateRules() {}
214 } // end anonymous namespace
217 //===----------------------------------------------------------------------===//
219 //===----------------------------------------------------------------------===//
221 // EmptyRules provides a concrete base class of ConstRules that does nothing
224 struct EmptyRules : public TemplateRules<Constant, EmptyRules> {
225 static Constant *EqualTo(const Constant *V1, const Constant *V2) {
226 if (V1 == V2) return ConstantBool::True;
230 } // end anonymous namespace
234 //===----------------------------------------------------------------------===//
236 //===----------------------------------------------------------------------===//
238 // BoolRules provides a concrete base class of ConstRules for the 'bool' type.
241 struct BoolRules : public TemplateRules<ConstantBool, BoolRules> {
243 static Constant *LessThan(const ConstantBool *V1, const ConstantBool *V2) {
244 return ConstantBool::get(V1->getValue() < V2->getValue());
247 static Constant *EqualTo(const Constant *V1, const Constant *V2) {
248 return ConstantBool::get(V1 == V2);
251 static Constant *And(const ConstantBool *V1, const ConstantBool *V2) {
252 return ConstantBool::get(V1->getValue() & V2->getValue());
255 static Constant *Or(const ConstantBool *V1, const ConstantBool *V2) {
256 return ConstantBool::get(V1->getValue() | V2->getValue());
259 static Constant *Xor(const ConstantBool *V1, const ConstantBool *V2) {
260 return ConstantBool::get(V1->getValue() ^ V2->getValue());
263 // Casting operators. ick
264 #define DEF_CAST(TYPE, CLASS, CTYPE) \
265 static Constant *CastTo##TYPE (const ConstantBool *V) { \
266 return CLASS::get(Type::TYPE##Ty, (CTYPE)(bool)V->getValue()); \
269 DEF_CAST(Bool , ConstantBool, bool)
270 DEF_CAST(SByte , ConstantSInt, signed char)
271 DEF_CAST(UByte , ConstantUInt, unsigned char)
272 DEF_CAST(Short , ConstantSInt, signed short)
273 DEF_CAST(UShort, ConstantUInt, unsigned short)
274 DEF_CAST(Int , ConstantSInt, signed int)
275 DEF_CAST(UInt , ConstantUInt, unsigned int)
276 DEF_CAST(Long , ConstantSInt, int64_t)
277 DEF_CAST(ULong , ConstantUInt, uint64_t)
278 DEF_CAST(Float , ConstantFP , float)
279 DEF_CAST(Double, ConstantFP , double)
282 } // end anonymous namespace
285 //===----------------------------------------------------------------------===//
286 // NullPointerRules Class
287 //===----------------------------------------------------------------------===//
289 // NullPointerRules provides a concrete base class of ConstRules for null
293 struct NullPointerRules : public TemplateRules<ConstantPointerNull,
295 static Constant *EqualTo(const Constant *V1, const Constant *V2) {
296 return ConstantBool::True; // Null pointers are always equal
298 static Constant *CastToBool(const Constant *V) {
299 return ConstantBool::False;
301 static Constant *CastToSByte (const Constant *V) {
302 return ConstantSInt::get(Type::SByteTy, 0);
304 static Constant *CastToUByte (const Constant *V) {
305 return ConstantUInt::get(Type::UByteTy, 0);
307 static Constant *CastToShort (const Constant *V) {
308 return ConstantSInt::get(Type::ShortTy, 0);
310 static Constant *CastToUShort(const Constant *V) {
311 return ConstantUInt::get(Type::UShortTy, 0);
313 static Constant *CastToInt (const Constant *V) {
314 return ConstantSInt::get(Type::IntTy, 0);
316 static Constant *CastToUInt (const Constant *V) {
317 return ConstantUInt::get(Type::UIntTy, 0);
319 static Constant *CastToLong (const Constant *V) {
320 return ConstantSInt::get(Type::LongTy, 0);
322 static Constant *CastToULong (const Constant *V) {
323 return ConstantUInt::get(Type::ULongTy, 0);
325 static Constant *CastToFloat (const Constant *V) {
326 return ConstantFP::get(Type::FloatTy, 0);
328 static Constant *CastToDouble(const Constant *V) {
329 return ConstantFP::get(Type::DoubleTy, 0);
332 static Constant *CastToPointer(const ConstantPointerNull *V,
333 const PointerType *PTy) {
334 return ConstantPointerNull::get(PTy);
337 } // end anonymous namespace
339 //===----------------------------------------------------------------------===//
340 // ConstantPackedRules Class
341 //===----------------------------------------------------------------------===//
343 /// DoVectorOp - Given two packed constants and a function pointer, apply the
344 /// function pointer to each element pair, producing a new ConstantPacked
346 static Constant *EvalVectorOp(const ConstantPacked *V1,
347 const ConstantPacked *V2,
348 Constant *(*FP)(Constant*, Constant*)) {
349 std::vector<Constant*> Res;
350 for (unsigned i = 0, e = V1->getNumOperands(); i != e; ++i)
351 Res.push_back(FP(const_cast<Constant*>(V1->getOperand(i)),
352 const_cast<Constant*>(V2->getOperand(i))));
353 return ConstantPacked::get(Res);
356 /// PackedTypeRules provides a concrete base class of ConstRules for
357 /// ConstantPacked operands.
360 struct ConstantPackedRules
361 : public TemplateRules<ConstantPacked, ConstantPackedRules> {
363 static Constant *Add(const ConstantPacked *V1, const ConstantPacked *V2) {
364 return EvalVectorOp(V1, V2, ConstantExpr::getAdd);
366 static Constant *Sub(const ConstantPacked *V1, const ConstantPacked *V2) {
367 return EvalVectorOp(V1, V2, ConstantExpr::getSub);
369 static Constant *Mul(const ConstantPacked *V1, const ConstantPacked *V2) {
370 return EvalVectorOp(V1, V2, ConstantExpr::getMul);
372 static Constant *Div(const ConstantPacked *V1, const ConstantPacked *V2) {
373 return EvalVectorOp(V1, V2, ConstantExpr::getDiv);
375 static Constant *Rem(const ConstantPacked *V1, const ConstantPacked *V2) {
376 return EvalVectorOp(V1, V2, ConstantExpr::getRem);
378 static Constant *And(const ConstantPacked *V1, const ConstantPacked *V2) {
379 return EvalVectorOp(V1, V2, ConstantExpr::getAnd);
381 static Constant *Or (const ConstantPacked *V1, const ConstantPacked *V2) {
382 return EvalVectorOp(V1, V2, ConstantExpr::getOr);
384 static Constant *Xor(const ConstantPacked *V1, const ConstantPacked *V2) {
385 return EvalVectorOp(V1, V2, ConstantExpr::getXor);
387 static Constant *Shl(const ConstantPacked *V1, const ConstantPacked *V2) {
388 return EvalVectorOp(V1, V2, ConstantExpr::getShl);
390 static Constant *Shr(const ConstantPacked *V1, const ConstantPacked *V2) {
391 return EvalVectorOp(V1, V2, ConstantExpr::getShr);
393 static Constant *LessThan(const ConstantPacked *V1, const ConstantPacked *V2){
396 static Constant *EqualTo(const ConstantPacked *V1, const ConstantPacked *V2) {
397 for (unsigned i = 0, e = V1->getNumOperands(); i != e; ++i) {
399 ConstantExpr::getSetEQ(const_cast<Constant*>(V1->getOperand(i)),
400 const_cast<Constant*>(V2->getOperand(i)));
401 if (ConstantBool *CB = dyn_cast<ConstantBool>(C))
404 // Otherwise, could not decide from any element pairs.
408 } // end anonymous namespace
411 //===----------------------------------------------------------------------===//
412 // GeneralPackedRules Class
413 //===----------------------------------------------------------------------===//
415 /// GeneralPackedRules provides a concrete base class of ConstRules for
416 /// PackedType operands, where both operands are not ConstantPacked. The usual
417 /// cause for this is that one operand is a ConstantAggregateZero.
420 struct GeneralPackedRules : public TemplateRules<Constant, GeneralPackedRules> {
422 } // end anonymous namespace
425 //===----------------------------------------------------------------------===//
427 //===----------------------------------------------------------------------===//
429 // DirectRules provides a concrete base classes of ConstRules for a variety of
430 // different types. This allows the C++ compiler to automatically generate our
431 // constant handling operations in a typesafe and accurate manner.
434 template<class ConstantClass, class BuiltinType, Type **Ty, class SuperClass>
435 struct DirectRules : public TemplateRules<ConstantClass, SuperClass> {
436 static Constant *Add(const ConstantClass *V1, const ConstantClass *V2) {
437 BuiltinType R = (BuiltinType)V1->getValue() + (BuiltinType)V2->getValue();
438 return ConstantClass::get(*Ty, R);
441 static Constant *Sub(const ConstantClass *V1, const ConstantClass *V2) {
442 BuiltinType R = (BuiltinType)V1->getValue() - (BuiltinType)V2->getValue();
443 return ConstantClass::get(*Ty, R);
446 static Constant *Mul(const ConstantClass *V1, const ConstantClass *V2) {
447 BuiltinType R = (BuiltinType)V1->getValue() * (BuiltinType)V2->getValue();
448 return ConstantClass::get(*Ty, R);
451 static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) {
452 if (V2->isNullValue()) return 0;
453 BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue();
454 return ConstantClass::get(*Ty, R);
457 static Constant *LessThan(const ConstantClass *V1, const ConstantClass *V2) {
458 bool R = (BuiltinType)V1->getValue() < (BuiltinType)V2->getValue();
459 return ConstantBool::get(R);
462 static Constant *EqualTo(const ConstantClass *V1, const ConstantClass *V2) {
463 bool R = (BuiltinType)V1->getValue() == (BuiltinType)V2->getValue();
464 return ConstantBool::get(R);
467 static Constant *CastToPointer(const ConstantClass *V,
468 const PointerType *PTy) {
469 if (V->isNullValue()) // Is it a FP or Integral null value?
470 return ConstantPointerNull::get(PTy);
471 return 0; // Can't const prop other types of pointers
474 // Casting operators. ick
475 #define DEF_CAST(TYPE, CLASS, CTYPE) \
476 static Constant *CastTo##TYPE (const ConstantClass *V) { \
477 return CLASS::get(Type::TYPE##Ty, (CTYPE)(BuiltinType)V->getValue()); \
480 DEF_CAST(Bool , ConstantBool, bool)
481 DEF_CAST(SByte , ConstantSInt, signed char)
482 DEF_CAST(UByte , ConstantUInt, unsigned char)
483 DEF_CAST(Short , ConstantSInt, signed short)
484 DEF_CAST(UShort, ConstantUInt, unsigned short)
485 DEF_CAST(Int , ConstantSInt, signed int)
486 DEF_CAST(UInt , ConstantUInt, unsigned int)
487 DEF_CAST(Long , ConstantSInt, int64_t)
488 DEF_CAST(ULong , ConstantUInt, uint64_t)
489 DEF_CAST(Float , ConstantFP , float)
490 DEF_CAST(Double, ConstantFP , double)
493 } // end anonymous namespace
496 //===----------------------------------------------------------------------===//
497 // DirectIntRules Class
498 //===----------------------------------------------------------------------===//
500 // DirectIntRules provides implementations of functions that are valid on
501 // integer types, but not all types in general.
504 template <class ConstantClass, class BuiltinType, Type **Ty>
505 struct DirectIntRules
506 : public DirectRules<ConstantClass, BuiltinType, Ty,
507 DirectIntRules<ConstantClass, BuiltinType, Ty> > {
509 static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) {
510 if (V2->isNullValue()) return 0;
511 if (V2->isAllOnesValue() && // MIN_INT / -1
512 (BuiltinType)V1->getValue() == -(BuiltinType)V1->getValue())
514 BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue();
515 return ConstantClass::get(*Ty, R);
518 static Constant *Rem(const ConstantClass *V1,
519 const ConstantClass *V2) {
520 if (V2->isNullValue()) return 0; // X / 0
521 if (V2->isAllOnesValue() && // MIN_INT / -1
522 (BuiltinType)V1->getValue() == -(BuiltinType)V1->getValue())
524 BuiltinType R = (BuiltinType)V1->getValue() % (BuiltinType)V2->getValue();
525 return ConstantClass::get(*Ty, R);
528 static Constant *And(const ConstantClass *V1, const ConstantClass *V2) {
529 BuiltinType R = (BuiltinType)V1->getValue() & (BuiltinType)V2->getValue();
530 return ConstantClass::get(*Ty, R);
532 static Constant *Or(const ConstantClass *V1, const ConstantClass *V2) {
533 BuiltinType R = (BuiltinType)V1->getValue() | (BuiltinType)V2->getValue();
534 return ConstantClass::get(*Ty, R);
536 static Constant *Xor(const ConstantClass *V1, const ConstantClass *V2) {
537 BuiltinType R = (BuiltinType)V1->getValue() ^ (BuiltinType)V2->getValue();
538 return ConstantClass::get(*Ty, R);
541 static Constant *Shl(const ConstantClass *V1, const ConstantClass *V2) {
542 BuiltinType R = (BuiltinType)V1->getValue() << (BuiltinType)V2->getValue();
543 return ConstantClass::get(*Ty, R);
546 static Constant *Shr(const ConstantClass *V1, const ConstantClass *V2) {
547 BuiltinType R = (BuiltinType)V1->getValue() >> (BuiltinType)V2->getValue();
548 return ConstantClass::get(*Ty, R);
551 } // end anonymous namespace
554 //===----------------------------------------------------------------------===//
555 // DirectFPRules Class
556 //===----------------------------------------------------------------------===//
558 /// DirectFPRules provides implementations of functions that are valid on
559 /// floating point types, but not all types in general.
562 template <class ConstantClass, class BuiltinType, Type **Ty>
564 : public DirectRules<ConstantClass, BuiltinType, Ty,
565 DirectFPRules<ConstantClass, BuiltinType, Ty> > {
566 static Constant *Rem(const ConstantClass *V1, const ConstantClass *V2) {
567 if (V2->isNullValue()) return 0;
568 BuiltinType Result = std::fmod((BuiltinType)V1->getValue(),
569 (BuiltinType)V2->getValue());
570 return ConstantClass::get(*Ty, Result);
572 static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) {
573 BuiltinType inf = std::numeric_limits<BuiltinType>::infinity();
574 if (V2->isExactlyValue(0.0)) return ConstantClass::get(*Ty, inf);
575 if (V2->isExactlyValue(-0.0)) return ConstantClass::get(*Ty, -inf);
576 BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue();
577 return ConstantClass::get(*Ty, R);
580 } // end anonymous namespace
583 /// ConstRules::get - This method returns the constant rules implementation that
584 /// implements the semantics of the two specified constants.
585 ConstRules &ConstRules::get(const Constant *V1, const Constant *V2) {
586 static EmptyRules EmptyR;
587 static BoolRules BoolR;
588 static NullPointerRules NullPointerR;
589 static ConstantPackedRules ConstantPackedR;
590 static GeneralPackedRules GeneralPackedR;
591 static DirectIntRules<ConstantSInt, signed char , &Type::SByteTy> SByteR;
592 static DirectIntRules<ConstantUInt, unsigned char , &Type::UByteTy> UByteR;
593 static DirectIntRules<ConstantSInt, signed short, &Type::ShortTy> ShortR;
594 static DirectIntRules<ConstantUInt, unsigned short, &Type::UShortTy> UShortR;
595 static DirectIntRules<ConstantSInt, signed int , &Type::IntTy> IntR;
596 static DirectIntRules<ConstantUInt, unsigned int , &Type::UIntTy> UIntR;
597 static DirectIntRules<ConstantSInt, int64_t , &Type::LongTy> LongR;
598 static DirectIntRules<ConstantUInt, uint64_t , &Type::ULongTy> ULongR;
599 static DirectFPRules <ConstantFP , float , &Type::FloatTy> FloatR;
600 static DirectFPRules <ConstantFP , double , &Type::DoubleTy> DoubleR;
602 if (isa<ConstantExpr>(V1) || isa<ConstantExpr>(V2) ||
603 isa<GlobalValue>(V1) || isa<GlobalValue>(V2) ||
604 isa<UndefValue>(V1) || isa<UndefValue>(V2))
607 switch (V1->getType()->getTypeID()) {
608 default: assert(0 && "Unknown value type for constant folding!");
609 case Type::BoolTyID: return BoolR;
610 case Type::PointerTyID: return NullPointerR;
611 case Type::SByteTyID: return SByteR;
612 case Type::UByteTyID: return UByteR;
613 case Type::ShortTyID: return ShortR;
614 case Type::UShortTyID: return UShortR;
615 case Type::IntTyID: return IntR;
616 case Type::UIntTyID: return UIntR;
617 case Type::LongTyID: return LongR;
618 case Type::ULongTyID: return ULongR;
619 case Type::FloatTyID: return FloatR;
620 case Type::DoubleTyID: return DoubleR;
621 case Type::PackedTyID:
622 if (isa<ConstantPacked>(V1) && isa<ConstantPacked>(V2))
623 return ConstantPackedR;
624 return GeneralPackedR; // Constant folding rules for ConstantAggregateZero.
629 //===----------------------------------------------------------------------===//
630 // ConstantFold*Instruction Implementations
631 //===----------------------------------------------------------------------===//
633 // These methods contain the special case hackery required to symbolically
634 // evaluate some constant expression cases, and use the ConstantRules class to
635 // evaluate normal constants.
637 static unsigned getSize(const Type *Ty) {
638 unsigned S = Ty->getPrimitiveSize();
639 return S ? S : 8; // Treat pointers at 8 bytes
642 /// CastConstantPacked - Convert the specified ConstantPacked node to the
643 /// specified packed type. At this point, we know that the elements of the
644 /// input packed constant are all simple integer or FP values.
645 static Constant *CastConstantPacked(ConstantPacked *CP,
646 const PackedType *DstTy) {
647 unsigned SrcNumElts = CP->getType()->getNumElements();
648 unsigned DstNumElts = DstTy->getNumElements();
649 const Type *SrcEltTy = CP->getType()->getElementType();
650 const Type *DstEltTy = DstTy->getElementType();
652 // If both vectors have the same number of elements (thus, the elements
653 // are the same size), perform the conversion now.
654 if (SrcNumElts == DstNumElts) {
655 std::vector<Constant*> Result;
657 // If the src and dest elements are both integers, just cast each one
658 // which will do the appropriate bit-convert.
659 if (SrcEltTy->isIntegral() && DstEltTy->isIntegral()) {
660 for (unsigned i = 0; i != SrcNumElts; ++i)
661 Result.push_back(ConstantExpr::getCast(CP->getOperand(i),
663 return ConstantPacked::get(Result);
666 if (SrcEltTy->isIntegral()) {
667 // Otherwise, this is an int-to-fp cast.
668 assert(DstEltTy->isFloatingPoint());
669 if (DstEltTy->getTypeID() == Type::DoubleTyID) {
670 for (unsigned i = 0; i != SrcNumElts; ++i) {
672 BitsToDouble(cast<ConstantInt>(CP->getOperand(i))->getRawValue());
673 Result.push_back(ConstantFP::get(Type::DoubleTy, V));
675 return ConstantPacked::get(Result);
677 assert(DstEltTy == Type::FloatTy && "Unknown fp type!");
678 for (unsigned i = 0; i != SrcNumElts; ++i) {
680 BitsToFloat(cast<ConstantInt>(CP->getOperand(i))->getRawValue());
681 Result.push_back(ConstantFP::get(Type::FloatTy, V));
683 return ConstantPacked::get(Result);
686 // Otherwise, this is an fp-to-int cast.
687 assert(SrcEltTy->isFloatingPoint() && DstEltTy->isIntegral());
689 if (SrcEltTy->getTypeID() == Type::DoubleTyID) {
690 for (unsigned i = 0; i != SrcNumElts; ++i) {
692 DoubleToBits(cast<ConstantFP>(CP->getOperand(i))->getValue());
693 Constant *C = ConstantUInt::get(Type::ULongTy, V);
694 Result.push_back(ConstantExpr::getCast(C, DstEltTy));
696 return ConstantPacked::get(Result);
699 assert(SrcEltTy->getTypeID() == Type::FloatTyID);
700 for (unsigned i = 0; i != SrcNumElts; ++i) {
701 unsigned V = FloatToBits(cast<ConstantFP>(CP->getOperand(i))->getValue());
702 Constant *C = ConstantUInt::get(Type::UIntTy, V);
703 Result.push_back(ConstantExpr::getCast(C, DstEltTy));
705 return ConstantPacked::get(Result);
708 // Otherwise, this is a cast that changes element count and size. Handle
709 // casts which shrink the elements here.
711 // FIXME: We need to know endianness to do this!
717 Constant *llvm::ConstantFoldCastInstruction(const Constant *V,
718 const Type *DestTy) {
719 if (V->getType() == DestTy) return (Constant*)V;
721 // Cast of a global address to boolean is always true.
722 if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
723 if (DestTy == Type::BoolTy)
724 // FIXME: When we support 'external weak' references, we have to prevent
725 // this transformation from happening. This code will need to be updated
726 // to ignore external weak symbols when we support it.
727 return ConstantBool::True;
728 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
729 if (CE->getOpcode() == Instruction::Cast) {
730 Constant *Op = const_cast<Constant*>(CE->getOperand(0));
731 // Try to not produce a cast of a cast, which is almost always redundant.
732 if (!Op->getType()->isFloatingPoint() &&
733 !CE->getType()->isFloatingPoint() &&
734 !DestTy->isFloatingPoint()) {
735 unsigned S1 = getSize(Op->getType()), S2 = getSize(CE->getType());
736 unsigned S3 = getSize(DestTy);
737 if (Op->getType() == DestTy && S3 >= S2)
739 if (S1 >= S2 && S2 >= S3)
740 return ConstantExpr::getCast(Op, DestTy);
741 if (S1 <= S2 && S2 >= S3 && S1 <= S3)
742 return ConstantExpr::getCast(Op, DestTy);
744 } else if (CE->getOpcode() == Instruction::GetElementPtr) {
745 // If all of the indexes in the GEP are null values, there is no pointer
746 // adjustment going on. We might as well cast the source pointer.
747 bool isAllNull = true;
748 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
749 if (!CE->getOperand(i)->isNullValue()) {
754 return ConstantExpr::getCast(CE->getOperand(0), DestTy);
756 } else if (isa<UndefValue>(V)) {
757 return UndefValue::get(DestTy);
760 // Check to see if we are casting an pointer to an aggregate to a pointer to
761 // the first element. If so, return the appropriate GEP instruction.
762 if (const PointerType *PTy = dyn_cast<PointerType>(V->getType()))
763 if (const PointerType *DPTy = dyn_cast<PointerType>(DestTy)) {
764 std::vector<Value*> IdxList;
765 IdxList.push_back(Constant::getNullValue(Type::IntTy));
766 const Type *ElTy = PTy->getElementType();
767 while (ElTy != DPTy->getElementType()) {
768 if (const StructType *STy = dyn_cast<StructType>(ElTy)) {
769 if (STy->getNumElements() == 0) break;
770 ElTy = STy->getElementType(0);
771 IdxList.push_back(Constant::getNullValue(Type::UIntTy));
772 } else if (const SequentialType *STy = dyn_cast<SequentialType>(ElTy)) {
773 if (isa<PointerType>(ElTy)) break; // Can't index into pointers!
774 ElTy = STy->getElementType();
775 IdxList.push_back(IdxList[0]);
781 if (ElTy == DPTy->getElementType())
782 return ConstantExpr::getGetElementPtr(const_cast<Constant*>(V),IdxList);
785 // Handle casts from one packed constant to another. We know that the src and
786 // dest type have the same size.
787 if (const PackedType *DestPTy = dyn_cast<PackedType>(DestTy)) {
788 if (const PackedType *SrcTy = dyn_cast<PackedType>(V->getType())) {
789 assert(DestPTy->getElementType()->getPrimitiveSizeInBits() *
790 DestPTy->getNumElements() ==
791 SrcTy->getElementType()->getPrimitiveSizeInBits() *
792 SrcTy->getNumElements() && "Not cast between same sized vectors!");
793 if (isa<ConstantAggregateZero>(V))
794 return Constant::getNullValue(DestTy);
795 if (isa<UndefValue>(V))
796 return UndefValue::get(DestTy);
797 if (const ConstantPacked *CP = dyn_cast<ConstantPacked>(V)) {
798 // This is a cast from a ConstantPacked of one type to a ConstantPacked
799 // of another type. Check to see if all elements of the input are
801 bool AllSimpleConstants = true;
802 for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) {
803 if (!isa<ConstantInt>(CP->getOperand(i)) &&
804 !isa<ConstantFP>(CP->getOperand(i))) {
805 AllSimpleConstants = false;
810 // If all of the elements are simple constants, we can fold this.
811 if (AllSimpleConstants)
812 return CastConstantPacked(const_cast<ConstantPacked*>(CP), DestPTy);
817 ConstRules &Rules = ConstRules::get(V, V);
819 switch (DestTy->getTypeID()) {
820 case Type::BoolTyID: return Rules.castToBool(V);
821 case Type::UByteTyID: return Rules.castToUByte(V);
822 case Type::SByteTyID: return Rules.castToSByte(V);
823 case Type::UShortTyID: return Rules.castToUShort(V);
824 case Type::ShortTyID: return Rules.castToShort(V);
825 case Type::UIntTyID: return Rules.castToUInt(V);
826 case Type::IntTyID: return Rules.castToInt(V);
827 case Type::ULongTyID: return Rules.castToULong(V);
828 case Type::LongTyID: return Rules.castToLong(V);
829 case Type::FloatTyID: return Rules.castToFloat(V);
830 case Type::DoubleTyID: return Rules.castToDouble(V);
831 case Type::PointerTyID:
832 return Rules.castToPointer(V, cast<PointerType>(DestTy));
837 Constant *llvm::ConstantFoldSelectInstruction(const Constant *Cond,
839 const Constant *V2) {
840 if (Cond == ConstantBool::True)
841 return const_cast<Constant*>(V1);
842 else if (Cond == ConstantBool::False)
843 return const_cast<Constant*>(V2);
845 if (isa<UndefValue>(V1)) return const_cast<Constant*>(V2);
846 if (isa<UndefValue>(V2)) return const_cast<Constant*>(V1);
847 if (isa<UndefValue>(Cond)) return const_cast<Constant*>(V1);
848 if (V1 == V2) return const_cast<Constant*>(V1);
852 Constant *llvm::ConstantFoldExtractElementInstruction(const Constant *Val,
853 const Constant *Idx) {
854 if (isa<UndefValue>(Val)) // ee(undef, x) -> undef
855 return UndefValue::get(cast<PackedType>(Val->getType())->getElementType());
856 if (Val->isNullValue()) // ee(zero, x) -> zero
857 return Constant::getNullValue(
858 cast<PackedType>(Val->getType())->getElementType());
860 if (const ConstantPacked *CVal = dyn_cast<ConstantPacked>(Val)) {
861 if (const ConstantUInt *CIdx = dyn_cast<ConstantUInt>(Idx)) {
862 return const_cast<Constant*>(CVal->getOperand(CIdx->getValue()));
863 } else if (isa<UndefValue>(Idx)) {
864 // ee({w,x,y,z}, undef) -> w (an arbitrary value).
865 return const_cast<Constant*>(CVal->getOperand(0));
871 Constant *llvm::ConstantFoldInsertElementInstruction(const Constant *Val,
873 const Constant *Idx) {
874 const ConstantUInt *CIdx = dyn_cast<ConstantUInt>(Idx);
876 unsigned idxVal = CIdx->getValue();
877 if (const UndefValue *UVal = dyn_cast<UndefValue>(Val)) {
878 // Insertion of scalar constant into packed undef
879 // Optimize away insertion of undef
880 if (isa<UndefValue>(Elt))
881 return const_cast<Constant*>(Val);
882 // Otherwise break the aggregate undef into multiple undefs and do
885 cast<PackedType>(Val->getType())->getNumElements();
886 std::vector<Constant*> Ops;
888 for (unsigned i = 0; i < numOps; ++i) {
890 (i == idxVal) ? Elt : UndefValue::get(Elt->getType());
891 Ops.push_back(const_cast<Constant*>(Op));
893 return ConstantPacked::get(Ops);
895 if (const ConstantAggregateZero *CVal =
896 dyn_cast<ConstantAggregateZero>(Val)) {
897 // Insertion of scalar constant into packed aggregate zero
898 // Optimize away insertion of zero
899 if (Elt->isNullValue())
900 return const_cast<Constant*>(Val);
901 // Otherwise break the aggregate zero into multiple zeros and do
904 cast<PackedType>(Val->getType())->getNumElements();
905 std::vector<Constant*> Ops;
907 for (unsigned i = 0; i < numOps; ++i) {
909 (i == idxVal) ? Elt : Constant::getNullValue(Elt->getType());
910 Ops.push_back(const_cast<Constant*>(Op));
912 return ConstantPacked::get(Ops);
914 if (const ConstantPacked *CVal = dyn_cast<ConstantPacked>(Val)) {
915 // Insertion of scalar constant into packed constant
916 std::vector<Constant*> Ops;
917 Ops.reserve(CVal->getNumOperands());
918 for (unsigned i = 0; i < CVal->getNumOperands(); ++i) {
920 (i == idxVal) ? Elt : cast<Constant>(CVal->getOperand(i));
921 Ops.push_back(const_cast<Constant*>(Op));
923 return ConstantPacked::get(Ops);
928 Constant *llvm::ConstantFoldShuffleVectorInstruction(const Constant *V1,
930 const Constant *Mask) {
936 /// isZeroSizedType - This type is zero sized if its an array or structure of
937 /// zero sized types. The only leaf zero sized type is an empty structure.
938 static bool isMaybeZeroSizedType(const Type *Ty) {
939 if (isa<OpaqueType>(Ty)) return true; // Can't say.
940 if (const StructType *STy = dyn_cast<StructType>(Ty)) {
942 // If all of elements have zero size, this does too.
943 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
944 if (!isMaybeZeroSizedType(STy->getElementType(i))) return false;
947 } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
948 return isMaybeZeroSizedType(ATy->getElementType());
953 /// IdxCompare - Compare the two constants as though they were getelementptr
954 /// indices. This allows coersion of the types to be the same thing.
956 /// If the two constants are the "same" (after coersion), return 0. If the
957 /// first is less than the second, return -1, if the second is less than the
958 /// first, return 1. If the constants are not integral, return -2.
960 static int IdxCompare(Constant *C1, Constant *C2, const Type *ElTy) {
961 if (C1 == C2) return 0;
963 // Ok, we found a different index. Are either of the operands
964 // ConstantExprs? If so, we can't do anything with them.
965 if (!isa<ConstantInt>(C1) || !isa<ConstantInt>(C2))
966 return -2; // don't know!
968 // Ok, we have two differing integer indices. Sign extend them to be the same
969 // type. Long is always big enough, so we use it.
970 C1 = ConstantExpr::getSignExtend(C1, Type::LongTy);
971 C2 = ConstantExpr::getSignExtend(C2, Type::LongTy);
972 if (C1 == C2) return 0; // Are they just differing types?
974 // If the type being indexed over is really just a zero sized type, there is
975 // no pointer difference being made here.
976 if (isMaybeZeroSizedType(ElTy))
979 // If they are really different, now that they are the same type, then we
980 // found a difference!
981 if (cast<ConstantSInt>(C1)->getValue() < cast<ConstantSInt>(C2)->getValue())
987 /// evaluateRelation - This function determines if there is anything we can
988 /// decide about the two constants provided. This doesn't need to handle simple
989 /// things like integer comparisons, but should instead handle ConstantExprs
990 /// and GlobalValuess. If we can determine that the two constants have a
991 /// particular relation to each other, we should return the corresponding SetCC
992 /// code, otherwise return Instruction::BinaryOpsEnd.
994 /// To simplify this code we canonicalize the relation so that the first
995 /// operand is always the most "complex" of the two. We consider simple
996 /// constants (like ConstantInt) to be the simplest, followed by
997 /// GlobalValues, followed by ConstantExpr's (the most complex).
999 static Instruction::BinaryOps evaluateRelation(Constant *V1, Constant *V2) {
1000 assert(V1->getType() == V2->getType() &&
1001 "Cannot compare different types of values!");
1002 if (V1 == V2) return Instruction::SetEQ;
1004 if (!isa<ConstantExpr>(V1) && !isa<GlobalValue>(V1)) {
1005 if (!isa<GlobalValue>(V2) && !isa<ConstantExpr>(V2)) {
1006 // We distilled this down to a simple case, use the standard constant
1008 ConstantBool *R = dyn_cast<ConstantBool>(ConstantExpr::getSetEQ(V1, V2));
1009 if (R == ConstantBool::True) return Instruction::SetEQ;
1010 R = dyn_cast<ConstantBool>(ConstantExpr::getSetLT(V1, V2));
1011 if (R == ConstantBool::True) return Instruction::SetLT;
1012 R = dyn_cast<ConstantBool>(ConstantExpr::getSetGT(V1, V2));
1013 if (R == ConstantBool::True) return Instruction::SetGT;
1015 // If we couldn't figure it out, bail.
1016 return Instruction::BinaryOpsEnd;
1019 // If the first operand is simple, swap operands.
1020 Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1);
1021 if (SwappedRelation != Instruction::BinaryOpsEnd)
1022 return SetCondInst::getSwappedCondition(SwappedRelation);
1024 } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(V1)) {
1025 if (isa<ConstantExpr>(V2)) { // Swap as necessary.
1026 Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1);
1027 if (SwappedRelation != Instruction::BinaryOpsEnd)
1028 return SetCondInst::getSwappedCondition(SwappedRelation);
1030 return Instruction::BinaryOpsEnd;
1033 // Now we know that the RHS is a GlobalValue or simple constant,
1034 // which (since the types must match) means that it's a ConstantPointerNull.
1035 if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) {
1036 assert(CPR1 != CPR2 &&
1037 "GVs for the same value exist at different addresses??");
1038 // FIXME: If both globals are external weak, they might both be null!
1039 return Instruction::SetNE;
1041 assert(isa<ConstantPointerNull>(V2) && "Canonicalization guarantee!");
1042 // Global can never be null. FIXME: if we implement external weak
1043 // linkage, this is not necessarily true!
1044 return Instruction::SetNE;
1048 // Ok, the LHS is known to be a constantexpr. The RHS can be any of a
1049 // constantexpr, a CPR, or a simple constant.
1050 ConstantExpr *CE1 = cast<ConstantExpr>(V1);
1051 Constant *CE1Op0 = CE1->getOperand(0);
1053 switch (CE1->getOpcode()) {
1054 case Instruction::Cast:
1055 // If the cast is not actually changing bits, and the second operand is a
1056 // null pointer, do the comparison with the pre-casted value.
1057 if (V2->isNullValue() &&
1058 (isa<PointerType>(CE1->getType()) || CE1->getType()->isIntegral()))
1059 return evaluateRelation(CE1Op0,
1060 Constant::getNullValue(CE1Op0->getType()));
1062 // If the dest type is a pointer type, and the RHS is a constantexpr cast
1063 // from the same type as the src of the LHS, evaluate the inputs. This is
1064 // important for things like "seteq (cast 4 to int*), (cast 5 to int*)",
1065 // which happens a lot in compilers with tagged integers.
1066 if (ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2))
1067 if (isa<PointerType>(CE1->getType()) &&
1068 CE2->getOpcode() == Instruction::Cast &&
1069 CE1->getOperand(0)->getType() == CE2->getOperand(0)->getType() &&
1070 CE1->getOperand(0)->getType()->isIntegral()) {
1071 return evaluateRelation(CE1->getOperand(0), CE2->getOperand(0));
1075 case Instruction::GetElementPtr:
1076 // Ok, since this is a getelementptr, we know that the constant has a
1077 // pointer type. Check the various cases.
1078 if (isa<ConstantPointerNull>(V2)) {
1079 // If we are comparing a GEP to a null pointer, check to see if the base
1080 // of the GEP equals the null pointer.
1081 if (isa<GlobalValue>(CE1Op0)) {
1082 // FIXME: this is not true when we have external weak references!
1083 // No offset can go from a global to a null pointer.
1084 return Instruction::SetGT;
1085 } else if (isa<ConstantPointerNull>(CE1Op0)) {
1086 // If we are indexing from a null pointer, check to see if we have any
1087 // non-zero indices.
1088 for (unsigned i = 1, e = CE1->getNumOperands(); i != e; ++i)
1089 if (!CE1->getOperand(i)->isNullValue())
1090 // Offsetting from null, must not be equal.
1091 return Instruction::SetGT;
1092 // Only zero indexes from null, must still be zero.
1093 return Instruction::SetEQ;
1095 // Otherwise, we can't really say if the first operand is null or not.
1096 } else if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) {
1097 if (isa<ConstantPointerNull>(CE1Op0)) {
1098 // FIXME: This is not true with external weak references.
1099 return Instruction::SetLT;
1100 } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(CE1Op0)) {
1102 // If this is a getelementptr of the same global, then it must be
1103 // different. Because the types must match, the getelementptr could
1104 // only have at most one index, and because we fold getelementptr's
1105 // with a single zero index, it must be nonzero.
1106 assert(CE1->getNumOperands() == 2 &&
1107 !CE1->getOperand(1)->isNullValue() &&
1108 "Suprising getelementptr!");
1109 return Instruction::SetGT;
1111 // If they are different globals, we don't know what the value is,
1112 // but they can't be equal.
1113 return Instruction::SetNE;
1117 const ConstantExpr *CE2 = cast<ConstantExpr>(V2);
1118 const Constant *CE2Op0 = CE2->getOperand(0);
1120 // There are MANY other foldings that we could perform here. They will
1121 // probably be added on demand, as they seem needed.
1122 switch (CE2->getOpcode()) {
1124 case Instruction::GetElementPtr:
1125 // By far the most common case to handle is when the base pointers are
1126 // obviously to the same or different globals.
1127 if (isa<GlobalValue>(CE1Op0) && isa<GlobalValue>(CE2Op0)) {
1128 if (CE1Op0 != CE2Op0) // Don't know relative ordering, but not equal
1129 return Instruction::SetNE;
1130 // Ok, we know that both getelementptr instructions are based on the
1131 // same global. From this, we can precisely determine the relative
1132 // ordering of the resultant pointers.
1135 // Compare all of the operands the GEP's have in common.
1136 gep_type_iterator GTI = gep_type_begin(CE1);
1137 for (;i != CE1->getNumOperands() && i != CE2->getNumOperands();
1139 switch (IdxCompare(CE1->getOperand(i), CE2->getOperand(i),
1140 GTI.getIndexedType())) {
1141 case -1: return Instruction::SetLT;
1142 case 1: return Instruction::SetGT;
1143 case -2: return Instruction::BinaryOpsEnd;
1146 // Ok, we ran out of things they have in common. If any leftovers
1147 // are non-zero then we have a difference, otherwise we are equal.
1148 for (; i < CE1->getNumOperands(); ++i)
1149 if (!CE1->getOperand(i)->isNullValue())
1150 if (isa<ConstantIntegral>(CE1->getOperand(i)))
1151 return Instruction::SetGT;
1153 return Instruction::BinaryOpsEnd; // Might be equal.
1155 for (; i < CE2->getNumOperands(); ++i)
1156 if (!CE2->getOperand(i)->isNullValue())
1157 if (isa<ConstantIntegral>(CE2->getOperand(i)))
1158 return Instruction::SetLT;
1160 return Instruction::BinaryOpsEnd; // Might be equal.
1161 return Instruction::SetEQ;
1171 return Instruction::BinaryOpsEnd;
1174 Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode,
1176 const Constant *V2) {
1180 case Instruction::Add: C = ConstRules::get(V1, V2).add(V1, V2); break;
1181 case Instruction::Sub: C = ConstRules::get(V1, V2).sub(V1, V2); break;
1182 case Instruction::Mul: C = ConstRules::get(V1, V2).mul(V1, V2); break;
1183 case Instruction::Div: C = ConstRules::get(V1, V2).div(V1, V2); break;
1184 case Instruction::Rem: C = ConstRules::get(V1, V2).rem(V1, V2); break;
1185 case Instruction::And: C = ConstRules::get(V1, V2).op_and(V1, V2); break;
1186 case Instruction::Or: C = ConstRules::get(V1, V2).op_or (V1, V2); break;
1187 case Instruction::Xor: C = ConstRules::get(V1, V2).op_xor(V1, V2); break;
1188 case Instruction::Shl: C = ConstRules::get(V1, V2).shl(V1, V2); break;
1189 case Instruction::Shr: C = ConstRules::get(V1, V2).shr(V1, V2); break;
1190 case Instruction::SetEQ: C = ConstRules::get(V1, V2).equalto(V1, V2); break;
1191 case Instruction::SetLT: C = ConstRules::get(V1, V2).lessthan(V1, V2);break;
1192 case Instruction::SetGT: C = ConstRules::get(V1, V2).lessthan(V2, V1);break;
1193 case Instruction::SetNE: // V1 != V2 === !(V1 == V2)
1194 C = ConstRules::get(V1, V2).equalto(V1, V2);
1195 if (C) return ConstantExpr::getNot(C);
1197 case Instruction::SetLE: // V1 <= V2 === !(V2 < V1)
1198 C = ConstRules::get(V1, V2).lessthan(V2, V1);
1199 if (C) return ConstantExpr::getNot(C);
1201 case Instruction::SetGE: // V1 >= V2 === !(V1 < V2)
1202 C = ConstRules::get(V1, V2).lessthan(V1, V2);
1203 if (C) return ConstantExpr::getNot(C);
1207 // If we successfully folded the expression, return it now.
1210 if (SetCondInst::isRelational(Opcode)) {
1211 if (isa<UndefValue>(V1) || isa<UndefValue>(V2))
1212 return UndefValue::get(Type::BoolTy);
1213 switch (evaluateRelation(const_cast<Constant*>(V1),
1214 const_cast<Constant*>(V2))) {
1215 default: assert(0 && "Unknown relational!");
1216 case Instruction::BinaryOpsEnd:
1217 break; // Couldn't determine anything about these constants.
1218 case Instruction::SetEQ: // We know the constants are equal!
1219 // If we know the constants are equal, we can decide the result of this
1220 // computation precisely.
1221 return ConstantBool::get(Opcode == Instruction::SetEQ ||
1222 Opcode == Instruction::SetLE ||
1223 Opcode == Instruction::SetGE);
1224 case Instruction::SetLT:
1225 // If we know that V1 < V2, we can decide the result of this computation
1227 return ConstantBool::get(Opcode == Instruction::SetLT ||
1228 Opcode == Instruction::SetNE ||
1229 Opcode == Instruction::SetLE);
1230 case Instruction::SetGT:
1231 // If we know that V1 > V2, we can decide the result of this computation
1233 return ConstantBool::get(Opcode == Instruction::SetGT ||
1234 Opcode == Instruction::SetNE ||
1235 Opcode == Instruction::SetGE);
1236 case Instruction::SetLE:
1237 // If we know that V1 <= V2, we can only partially decide this relation.
1238 if (Opcode == Instruction::SetGT) return ConstantBool::False;
1239 if (Opcode == Instruction::SetLT) return ConstantBool::True;
1242 case Instruction::SetGE:
1243 // If we know that V1 >= V2, we can only partially decide this relation.
1244 if (Opcode == Instruction::SetLT) return ConstantBool::False;
1245 if (Opcode == Instruction::SetGT) return ConstantBool::True;
1248 case Instruction::SetNE:
1249 // If we know that V1 != V2, we can only partially decide this relation.
1250 if (Opcode == Instruction::SetEQ) return ConstantBool::False;
1251 if (Opcode == Instruction::SetNE) return ConstantBool::True;
1256 if (isa<UndefValue>(V1) || isa<UndefValue>(V2)) {
1258 case Instruction::Add:
1259 case Instruction::Sub:
1260 case Instruction::Xor:
1261 return UndefValue::get(V1->getType());
1263 case Instruction::Mul:
1264 case Instruction::And:
1265 return Constant::getNullValue(V1->getType());
1266 case Instruction::Div:
1267 case Instruction::Rem:
1268 if (!isa<UndefValue>(V2)) // undef/X -> 0
1269 return Constant::getNullValue(V1->getType());
1270 return const_cast<Constant*>(V2); // X/undef -> undef
1271 case Instruction::Or: // X|undef -> -1
1272 return ConstantInt::getAllOnesValue(V1->getType());
1273 case Instruction::Shr:
1274 if (!isa<UndefValue>(V2)) {
1275 if (V1->getType()->isSigned())
1276 return const_cast<Constant*>(V1); // undef >>s X -> undef
1278 } else if (isa<UndefValue>(V1)) {
1279 return const_cast<Constant*>(V1); // undef >> undef -> undef
1281 if (V1->getType()->isSigned())
1282 return const_cast<Constant*>(V1); // X >>s undef -> X
1285 return Constant::getNullValue(V1->getType());
1287 case Instruction::Shl:
1288 // undef << X -> 0 X << undef -> 0
1289 return Constant::getNullValue(V1->getType());
1293 if (const ConstantExpr *CE1 = dyn_cast<ConstantExpr>(V1)) {
1294 if (const ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2)) {
1295 // There are many possible foldings we could do here. We should probably
1296 // at least fold add of a pointer with an integer into the appropriate
1297 // getelementptr. This will improve alias analysis a bit.
1303 // Just implement a couple of simple identities.
1305 case Instruction::Add:
1306 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X + 0 == X
1308 case Instruction::Sub:
1309 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X - 0 == X
1311 case Instruction::Mul:
1312 if (V2->isNullValue()) return const_cast<Constant*>(V2); // X * 0 == 0
1313 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1314 if (CI->getRawValue() == 1)
1315 return const_cast<Constant*>(V1); // X * 1 == X
1317 case Instruction::Div:
1318 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1319 if (CI->getRawValue() == 1)
1320 return const_cast<Constant*>(V1); // X / 1 == X
1322 case Instruction::Rem:
1323 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1324 if (CI->getRawValue() == 1)
1325 return Constant::getNullValue(CI->getType()); // X % 1 == 0
1327 case Instruction::And:
1328 if (cast<ConstantIntegral>(V2)->isAllOnesValue())
1329 return const_cast<Constant*>(V1); // X & -1 == X
1330 if (V2->isNullValue()) return const_cast<Constant*>(V2); // X & 0 == 0
1331 if (CE1->getOpcode() == Instruction::Cast &&
1332 isa<GlobalValue>(CE1->getOperand(0))) {
1333 GlobalValue *CPR = cast<GlobalValue>(CE1->getOperand(0));
1335 // Functions are at least 4-byte aligned. If and'ing the address of a
1336 // function with a constant < 4, fold it to zero.
1337 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1338 if (CI->getRawValue() < 4 && isa<Function>(CPR))
1339 return Constant::getNullValue(CI->getType());
1342 case Instruction::Or:
1343 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X | 0 == X
1344 if (cast<ConstantIntegral>(V2)->isAllOnesValue())
1345 return const_cast<Constant*>(V2); // X | -1 == -1
1347 case Instruction::Xor:
1348 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X ^ 0 == X
1353 } else if (const ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2)) {
1354 // If V2 is a constant expr and V1 isn't, flop them around and fold the
1355 // other way if possible.
1357 case Instruction::Add:
1358 case Instruction::Mul:
1359 case Instruction::And:
1360 case Instruction::Or:
1361 case Instruction::Xor:
1362 case Instruction::SetEQ:
1363 case Instruction::SetNE:
1364 // No change of opcode required.
1365 return ConstantFoldBinaryInstruction(Opcode, V2, V1);
1367 case Instruction::SetLT:
1368 case Instruction::SetGT:
1369 case Instruction::SetLE:
1370 case Instruction::SetGE:
1371 // Change the opcode as necessary to swap the operands.
1372 Opcode = SetCondInst::getSwappedCondition((Instruction::BinaryOps)Opcode);
1373 return ConstantFoldBinaryInstruction(Opcode, V2, V1);
1375 case Instruction::Shl:
1376 case Instruction::Shr:
1377 case Instruction::Sub:
1378 case Instruction::Div:
1379 case Instruction::Rem:
1380 default: // These instructions cannot be flopped around.
1387 Constant *llvm::ConstantFoldGetElementPtr(const Constant *C,
1388 const std::vector<Value*> &IdxList) {
1389 if (IdxList.size() == 0 ||
1390 (IdxList.size() == 1 && cast<Constant>(IdxList[0])->isNullValue()))
1391 return const_cast<Constant*>(C);
1393 if (isa<UndefValue>(C)) {
1394 const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList,
1396 assert(Ty != 0 && "Invalid indices for GEP!");
1397 return UndefValue::get(PointerType::get(Ty));
1400 Constant *Idx0 = cast<Constant>(IdxList[0]);
1401 if (C->isNullValue()) {
1403 for (unsigned i = 0, e = IdxList.size(); i != e; ++i)
1404 if (!cast<Constant>(IdxList[i])->isNullValue()) {
1409 const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList,
1411 assert(Ty != 0 && "Invalid indices for GEP!");
1412 return ConstantPointerNull::get(PointerType::get(Ty));
1415 if (IdxList.size() == 1) {
1416 const Type *ElTy = cast<PointerType>(C->getType())->getElementType();
1417 if (unsigned ElSize = ElTy->getPrimitiveSize()) {
1418 // gep null, C is equal to C*sizeof(nullty). If nullty is a known llvm
1419 // type, we can statically fold this.
1420 Constant *R = ConstantUInt::get(Type::UIntTy, ElSize);
1421 R = ConstantExpr::getCast(R, Idx0->getType());
1422 R = ConstantExpr::getMul(R, Idx0);
1423 return ConstantExpr::getCast(R, C->getType());
1428 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(const_cast<Constant*>(C))) {
1429 // Combine Indices - If the source pointer to this getelementptr instruction
1430 // is a getelementptr instruction, combine the indices of the two
1431 // getelementptr instructions into a single instruction.
1433 if (CE->getOpcode() == Instruction::GetElementPtr) {
1434 const Type *LastTy = 0;
1435 for (gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
1439 if ((LastTy && isa<ArrayType>(LastTy)) || Idx0->isNullValue()) {
1440 std::vector<Value*> NewIndices;
1441 NewIndices.reserve(IdxList.size() + CE->getNumOperands());
1442 for (unsigned i = 1, e = CE->getNumOperands()-1; i != e; ++i)
1443 NewIndices.push_back(CE->getOperand(i));
1445 // Add the last index of the source with the first index of the new GEP.
1446 // Make sure to handle the case when they are actually different types.
1447 Constant *Combined = CE->getOperand(CE->getNumOperands()-1);
1448 // Otherwise it must be an array.
1449 if (!Idx0->isNullValue()) {
1450 const Type *IdxTy = Combined->getType();
1451 if (IdxTy != Idx0->getType()) IdxTy = Type::LongTy;
1453 ConstantExpr::get(Instruction::Add,
1454 ConstantExpr::getCast(Idx0, IdxTy),
1455 ConstantExpr::getCast(Combined, IdxTy));
1458 NewIndices.push_back(Combined);
1459 NewIndices.insert(NewIndices.end(), IdxList.begin()+1, IdxList.end());
1460 return ConstantExpr::getGetElementPtr(CE->getOperand(0), NewIndices);
1464 // Implement folding of:
1465 // int* getelementptr ([2 x int]* cast ([3 x int]* %X to [2 x int]*),
1467 // To: int* getelementptr ([3 x int]* %X, long 0, long 0)
1469 if (CE->getOpcode() == Instruction::Cast && IdxList.size() > 1 &&
1470 Idx0->isNullValue())
1471 if (const PointerType *SPT =
1472 dyn_cast<PointerType>(CE->getOperand(0)->getType()))
1473 if (const ArrayType *SAT = dyn_cast<ArrayType>(SPT->getElementType()))
1474 if (const ArrayType *CAT =
1475 dyn_cast<ArrayType>(cast<PointerType>(C->getType())->getElementType()))
1476 if (CAT->getElementType() == SAT->getElementType())
1477 return ConstantExpr::getGetElementPtr(
1478 (Constant*)CE->getOperand(0), IdxList);