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/Support/GetElementPtrTypeIterator.h"
33 // Binary Operators...
34 virtual Constant *add(const Constant *V1, const Constant *V2) const = 0;
35 virtual Constant *sub(const Constant *V1, const Constant *V2) const = 0;
36 virtual Constant *mul(const Constant *V1, const Constant *V2) const = 0;
37 virtual Constant *div(const Constant *V1, const Constant *V2) const = 0;
38 virtual Constant *rem(const Constant *V1, const Constant *V2) const = 0;
39 virtual Constant *op_and(const Constant *V1, const Constant *V2) const = 0;
40 virtual Constant *op_or (const Constant *V1, const Constant *V2) const = 0;
41 virtual Constant *op_xor(const Constant *V1, const Constant *V2) const = 0;
42 virtual Constant *shl(const Constant *V1, const Constant *V2) const = 0;
43 virtual Constant *shr(const Constant *V1, const Constant *V2) const = 0;
44 virtual Constant *lessthan(const Constant *V1, const Constant *V2) const =0;
45 virtual Constant *equalto(const Constant *V1, const Constant *V2) const = 0;
48 virtual Constant *castToBool (const Constant *V) const = 0;
49 virtual Constant *castToSByte (const Constant *V) const = 0;
50 virtual Constant *castToUByte (const Constant *V) const = 0;
51 virtual Constant *castToShort (const Constant *V) const = 0;
52 virtual Constant *castToUShort(const Constant *V) const = 0;
53 virtual Constant *castToInt (const Constant *V) const = 0;
54 virtual Constant *castToUInt (const Constant *V) const = 0;
55 virtual Constant *castToLong (const Constant *V) const = 0;
56 virtual Constant *castToULong (const Constant *V) const = 0;
57 virtual Constant *castToFloat (const Constant *V) const = 0;
58 virtual Constant *castToDouble(const Constant *V) const = 0;
59 virtual Constant *castToPointer(const Constant *V,
60 const PointerType *Ty) const = 0;
62 // ConstRules::get - Return an instance of ConstRules for the specified
65 static ConstRules &get(const Constant *V1, const Constant *V2);
67 ConstRules(const ConstRules &); // Do not implement
68 ConstRules &operator=(const ConstRules &); // Do not implement
73 //===----------------------------------------------------------------------===//
74 // TemplateRules Class
75 //===----------------------------------------------------------------------===//
77 // TemplateRules - Implement a subclass of ConstRules that provides all
78 // operations as noops. All other rules classes inherit from this class so
79 // that if functionality is needed in the future, it can simply be added here
80 // and to ConstRules without changing anything else...
82 // This class also provides subclasses with typesafe implementations of methods
83 // so that don't have to do type casting.
85 template<class ArgType, class SubClassName>
86 class TemplateRules : public ConstRules {
88 //===--------------------------------------------------------------------===//
89 // Redirecting functions that cast to the appropriate types
90 //===--------------------------------------------------------------------===//
92 virtual Constant *add(const Constant *V1, const Constant *V2) const {
93 return SubClassName::Add((const ArgType *)V1, (const ArgType *)V2);
95 virtual Constant *sub(const Constant *V1, const Constant *V2) const {
96 return SubClassName::Sub((const ArgType *)V1, (const ArgType *)V2);
98 virtual Constant *mul(const Constant *V1, const Constant *V2) const {
99 return SubClassName::Mul((const ArgType *)V1, (const ArgType *)V2);
101 virtual Constant *div(const Constant *V1, const Constant *V2) const {
102 return SubClassName::Div((const ArgType *)V1, (const ArgType *)V2);
104 virtual Constant *rem(const Constant *V1, const Constant *V2) const {
105 return SubClassName::Rem((const ArgType *)V1, (const ArgType *)V2);
107 virtual Constant *op_and(const Constant *V1, const Constant *V2) const {
108 return SubClassName::And((const ArgType *)V1, (const ArgType *)V2);
110 virtual Constant *op_or(const Constant *V1, const Constant *V2) const {
111 return SubClassName::Or((const ArgType *)V1, (const ArgType *)V2);
113 virtual Constant *op_xor(const Constant *V1, const Constant *V2) const {
114 return SubClassName::Xor((const ArgType *)V1, (const ArgType *)V2);
116 virtual Constant *shl(const Constant *V1, const Constant *V2) const {
117 return SubClassName::Shl((const ArgType *)V1, (const ArgType *)V2);
119 virtual Constant *shr(const Constant *V1, const Constant *V2) const {
120 return SubClassName::Shr((const ArgType *)V1, (const ArgType *)V2);
123 virtual Constant *lessthan(const Constant *V1, const Constant *V2) const {
124 return SubClassName::LessThan((const ArgType *)V1, (const ArgType *)V2);
126 virtual Constant *equalto(const Constant *V1, const Constant *V2) const {
127 return SubClassName::EqualTo((const ArgType *)V1, (const ArgType *)V2);
130 // Casting operators. ick
131 virtual Constant *castToBool(const Constant *V) const {
132 return SubClassName::CastToBool((const ArgType*)V);
134 virtual Constant *castToSByte(const Constant *V) const {
135 return SubClassName::CastToSByte((const ArgType*)V);
137 virtual Constant *castToUByte(const Constant *V) const {
138 return SubClassName::CastToUByte((const ArgType*)V);
140 virtual Constant *castToShort(const Constant *V) const {
141 return SubClassName::CastToShort((const ArgType*)V);
143 virtual Constant *castToUShort(const Constant *V) const {
144 return SubClassName::CastToUShort((const ArgType*)V);
146 virtual Constant *castToInt(const Constant *V) const {
147 return SubClassName::CastToInt((const ArgType*)V);
149 virtual Constant *castToUInt(const Constant *V) const {
150 return SubClassName::CastToUInt((const ArgType*)V);
152 virtual Constant *castToLong(const Constant *V) const {
153 return SubClassName::CastToLong((const ArgType*)V);
155 virtual Constant *castToULong(const Constant *V) const {
156 return SubClassName::CastToULong((const ArgType*)V);
158 virtual Constant *castToFloat(const Constant *V) const {
159 return SubClassName::CastToFloat((const ArgType*)V);
161 virtual Constant *castToDouble(const Constant *V) const {
162 return SubClassName::CastToDouble((const ArgType*)V);
164 virtual Constant *castToPointer(const Constant *V,
165 const PointerType *Ty) const {
166 return SubClassName::CastToPointer((const ArgType*)V, Ty);
169 //===--------------------------------------------------------------------===//
170 // Default "noop" implementations
171 //===--------------------------------------------------------------------===//
173 static Constant *Add(const ArgType *V1, const ArgType *V2) { return 0; }
174 static Constant *Sub(const ArgType *V1, const ArgType *V2) { return 0; }
175 static Constant *Mul(const ArgType *V1, const ArgType *V2) { return 0; }
176 static Constant *Div(const ArgType *V1, const ArgType *V2) { return 0; }
177 static Constant *Rem(const ArgType *V1, const ArgType *V2) { return 0; }
178 static Constant *And(const ArgType *V1, const ArgType *V2) { return 0; }
179 static Constant *Or (const ArgType *V1, const ArgType *V2) { return 0; }
180 static Constant *Xor(const ArgType *V1, const ArgType *V2) { return 0; }
181 static Constant *Shl(const ArgType *V1, const ArgType *V2) { return 0; }
182 static Constant *Shr(const ArgType *V1, const ArgType *V2) { return 0; }
183 static Constant *LessThan(const ArgType *V1, const ArgType *V2) {
186 static Constant *EqualTo(const ArgType *V1, const ArgType *V2) {
190 // Casting operators. ick
191 static Constant *CastToBool (const Constant *V) { return 0; }
192 static Constant *CastToSByte (const Constant *V) { return 0; }
193 static Constant *CastToUByte (const Constant *V) { return 0; }
194 static Constant *CastToShort (const Constant *V) { return 0; }
195 static Constant *CastToUShort(const Constant *V) { return 0; }
196 static Constant *CastToInt (const Constant *V) { return 0; }
197 static Constant *CastToUInt (const Constant *V) { return 0; }
198 static Constant *CastToLong (const Constant *V) { return 0; }
199 static Constant *CastToULong (const Constant *V) { return 0; }
200 static Constant *CastToFloat (const Constant *V) { return 0; }
201 static Constant *CastToDouble(const Constant *V) { return 0; }
202 static Constant *CastToPointer(const Constant *,
203 const PointerType *) {return 0;}
208 //===----------------------------------------------------------------------===//
210 //===----------------------------------------------------------------------===//
212 // EmptyRules provides a concrete base class of ConstRules that does nothing
214 struct EmptyRules : public TemplateRules<Constant, EmptyRules> {
215 static Constant *EqualTo(const Constant *V1, const Constant *V2) {
216 if (V1 == V2) return ConstantBool::True;
223 //===----------------------------------------------------------------------===//
225 //===----------------------------------------------------------------------===//
227 // BoolRules provides a concrete base class of ConstRules for the 'bool' type.
229 struct BoolRules : public TemplateRules<ConstantBool, BoolRules> {
231 static Constant *LessThan(const ConstantBool *V1, const ConstantBool *V2){
232 return ConstantBool::get(V1->getValue() < V2->getValue());
235 static Constant *EqualTo(const Constant *V1, const Constant *V2) {
236 return ConstantBool::get(V1 == V2);
239 static Constant *And(const ConstantBool *V1, const ConstantBool *V2) {
240 return ConstantBool::get(V1->getValue() & V2->getValue());
243 static Constant *Or(const ConstantBool *V1, const ConstantBool *V2) {
244 return ConstantBool::get(V1->getValue() | V2->getValue());
247 static Constant *Xor(const ConstantBool *V1, const ConstantBool *V2) {
248 return ConstantBool::get(V1->getValue() ^ V2->getValue());
251 // Casting operators. ick
252 #define DEF_CAST(TYPE, CLASS, CTYPE) \
253 static Constant *CastTo##TYPE (const ConstantBool *V) { \
254 return CLASS::get(Type::TYPE##Ty, (CTYPE)(bool)V->getValue()); \
257 DEF_CAST(Bool , ConstantBool, bool)
258 DEF_CAST(SByte , ConstantSInt, signed char)
259 DEF_CAST(UByte , ConstantUInt, unsigned char)
260 DEF_CAST(Short , ConstantSInt, signed short)
261 DEF_CAST(UShort, ConstantUInt, unsigned short)
262 DEF_CAST(Int , ConstantSInt, signed int)
263 DEF_CAST(UInt , ConstantUInt, unsigned int)
264 DEF_CAST(Long , ConstantSInt, int64_t)
265 DEF_CAST(ULong , ConstantUInt, uint64_t)
266 DEF_CAST(Float , ConstantFP , float)
267 DEF_CAST(Double, ConstantFP , double)
272 //===----------------------------------------------------------------------===//
273 // NullPointerRules Class
274 //===----------------------------------------------------------------------===//
276 // NullPointerRules provides a concrete base class of ConstRules for null
279 struct NullPointerRules : public TemplateRules<ConstantPointerNull,
281 static Constant *EqualTo(const Constant *V1, const Constant *V2) {
282 return ConstantBool::True; // Null pointers are always equal
284 static Constant *CastToBool(const Constant *V) {
285 return ConstantBool::False;
287 static Constant *CastToSByte (const Constant *V) {
288 return ConstantSInt::get(Type::SByteTy, 0);
290 static Constant *CastToUByte (const Constant *V) {
291 return ConstantUInt::get(Type::UByteTy, 0);
293 static Constant *CastToShort (const Constant *V) {
294 return ConstantSInt::get(Type::ShortTy, 0);
296 static Constant *CastToUShort(const Constant *V) {
297 return ConstantUInt::get(Type::UShortTy, 0);
299 static Constant *CastToInt (const Constant *V) {
300 return ConstantSInt::get(Type::IntTy, 0);
302 static Constant *CastToUInt (const Constant *V) {
303 return ConstantUInt::get(Type::UIntTy, 0);
305 static Constant *CastToLong (const Constant *V) {
306 return ConstantSInt::get(Type::LongTy, 0);
308 static Constant *CastToULong (const Constant *V) {
309 return ConstantUInt::get(Type::ULongTy, 0);
311 static Constant *CastToFloat (const Constant *V) {
312 return ConstantFP::get(Type::FloatTy, 0);
314 static Constant *CastToDouble(const Constant *V) {
315 return ConstantFP::get(Type::DoubleTy, 0);
318 static Constant *CastToPointer(const ConstantPointerNull *V,
319 const PointerType *PTy) {
320 return ConstantPointerNull::get(PTy);
325 //===----------------------------------------------------------------------===//
327 //===----------------------------------------------------------------------===//
329 // DirectRules provides a concrete base classes of ConstRules for a variety of
330 // different types. This allows the C++ compiler to automatically generate our
331 // constant handling operations in a typesafe and accurate manner.
333 template<class ConstantClass, class BuiltinType, Type **Ty, class SuperClass>
334 struct DirectRules : public TemplateRules<ConstantClass, SuperClass> {
335 static Constant *Add(const ConstantClass *V1, const ConstantClass *V2) {
336 BuiltinType R = (BuiltinType)V1->getValue() + (BuiltinType)V2->getValue();
337 return ConstantClass::get(*Ty, R);
340 static Constant *Sub(const ConstantClass *V1, const ConstantClass *V2) {
341 BuiltinType R = (BuiltinType)V1->getValue() - (BuiltinType)V2->getValue();
342 return ConstantClass::get(*Ty, R);
345 static Constant *Mul(const ConstantClass *V1, const ConstantClass *V2) {
346 BuiltinType R = (BuiltinType)V1->getValue() * (BuiltinType)V2->getValue();
347 return ConstantClass::get(*Ty, R);
350 static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) {
351 if (V2->isNullValue()) return 0;
352 BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue();
353 return ConstantClass::get(*Ty, R);
356 static Constant *LessThan(const ConstantClass *V1, const ConstantClass *V2) {
357 bool R = (BuiltinType)V1->getValue() < (BuiltinType)V2->getValue();
358 return ConstantBool::get(R);
361 static Constant *EqualTo(const ConstantClass *V1, const ConstantClass *V2) {
362 bool R = (BuiltinType)V1->getValue() == (BuiltinType)V2->getValue();
363 return ConstantBool::get(R);
366 static Constant *CastToPointer(const ConstantClass *V,
367 const PointerType *PTy) {
368 if (V->isNullValue()) // Is it a FP or Integral null value?
369 return ConstantPointerNull::get(PTy);
370 return 0; // Can't const prop other types of pointers
373 // Casting operators. ick
374 #define DEF_CAST(TYPE, CLASS, CTYPE) \
375 static Constant *CastTo##TYPE (const ConstantClass *V) { \
376 return CLASS::get(Type::TYPE##Ty, (CTYPE)(BuiltinType)V->getValue()); \
379 DEF_CAST(Bool , ConstantBool, bool)
380 DEF_CAST(SByte , ConstantSInt, signed char)
381 DEF_CAST(UByte , ConstantUInt, unsigned char)
382 DEF_CAST(Short , ConstantSInt, signed short)
383 DEF_CAST(UShort, ConstantUInt, unsigned short)
384 DEF_CAST(Int , ConstantSInt, signed int)
385 DEF_CAST(UInt , ConstantUInt, unsigned int)
386 DEF_CAST(Long , ConstantSInt, int64_t)
387 DEF_CAST(ULong , ConstantUInt, uint64_t)
388 DEF_CAST(Float , ConstantFP , float)
389 DEF_CAST(Double, ConstantFP , double)
394 //===----------------------------------------------------------------------===//
395 // DirectIntRules Class
396 //===----------------------------------------------------------------------===//
398 // DirectIntRules provides implementations of functions that are valid on
399 // integer types, but not all types in general.
401 template <class ConstantClass, class BuiltinType, Type **Ty>
402 struct DirectIntRules
403 : public DirectRules<ConstantClass, BuiltinType, Ty,
404 DirectIntRules<ConstantClass, BuiltinType, Ty> > {
406 static Constant *Div(const ConstantClass *V1, const ConstantClass *V2) {
407 if (V2->isNullValue()) return 0;
408 if (V2->isAllOnesValue() && // MIN_INT / -1
409 (BuiltinType)V1->getValue() == -(BuiltinType)V1->getValue())
411 BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue();
412 return ConstantClass::get(*Ty, R);
415 static Constant *Rem(const ConstantClass *V1,
416 const ConstantClass *V2) {
417 if (V2->isNullValue()) return 0; // X / 0
418 if (V2->isAllOnesValue() && // MIN_INT / -1
419 (BuiltinType)V1->getValue() == -(BuiltinType)V1->getValue())
421 BuiltinType R = (BuiltinType)V1->getValue() % (BuiltinType)V2->getValue();
422 return ConstantClass::get(*Ty, R);
425 static Constant *And(const ConstantClass *V1, const ConstantClass *V2) {
426 BuiltinType R = (BuiltinType)V1->getValue() & (BuiltinType)V2->getValue();
427 return ConstantClass::get(*Ty, R);
429 static Constant *Or(const ConstantClass *V1, const ConstantClass *V2) {
430 BuiltinType R = (BuiltinType)V1->getValue() | (BuiltinType)V2->getValue();
431 return ConstantClass::get(*Ty, R);
433 static Constant *Xor(const ConstantClass *V1, const ConstantClass *V2) {
434 BuiltinType R = (BuiltinType)V1->getValue() ^ (BuiltinType)V2->getValue();
435 return ConstantClass::get(*Ty, R);
438 static Constant *Shl(const ConstantClass *V1, const ConstantClass *V2) {
439 BuiltinType R = (BuiltinType)V1->getValue() << (BuiltinType)V2->getValue();
440 return ConstantClass::get(*Ty, R);
443 static Constant *Shr(const ConstantClass *V1, const ConstantClass *V2) {
444 BuiltinType R = (BuiltinType)V1->getValue() >> (BuiltinType)V2->getValue();
445 return ConstantClass::get(*Ty, R);
450 //===----------------------------------------------------------------------===//
451 // DirectFPRules Class
452 //===----------------------------------------------------------------------===//
454 /// DirectFPRules provides implementations of functions that are valid on
455 /// floating point types, but not all types in general.
457 template <class ConstantClass, class BuiltinType, Type **Ty>
459 : public DirectRules<ConstantClass, BuiltinType, Ty,
460 DirectFPRules<ConstantClass, BuiltinType, Ty> > {
461 static Constant *Rem(const ConstantClass *V1, const ConstantClass *V2) {
462 if (V2->isNullValue()) return 0;
463 BuiltinType Result = std::fmod((BuiltinType)V1->getValue(),
464 (BuiltinType)V2->getValue());
465 return ConstantClass::get(*Ty, Result);
470 /// ConstRules::get - This method returns the constant rules implementation that
471 /// implements the semantics of the two specified constants.
472 ConstRules &ConstRules::get(const Constant *V1, const Constant *V2) {
473 static EmptyRules EmptyR;
474 static BoolRules BoolR;
475 static NullPointerRules NullPointerR;
476 static DirectIntRules<ConstantSInt, signed char , &Type::SByteTy> SByteR;
477 static DirectIntRules<ConstantUInt, unsigned char , &Type::UByteTy> UByteR;
478 static DirectIntRules<ConstantSInt, signed short, &Type::ShortTy> ShortR;
479 static DirectIntRules<ConstantUInt, unsigned short, &Type::UShortTy> UShortR;
480 static DirectIntRules<ConstantSInt, signed int , &Type::IntTy> IntR;
481 static DirectIntRules<ConstantUInt, unsigned int , &Type::UIntTy> UIntR;
482 static DirectIntRules<ConstantSInt, int64_t , &Type::LongTy> LongR;
483 static DirectIntRules<ConstantUInt, uint64_t , &Type::ULongTy> ULongR;
484 static DirectFPRules <ConstantFP , float , &Type::FloatTy> FloatR;
485 static DirectFPRules <ConstantFP , double , &Type::DoubleTy> DoubleR;
487 if (isa<ConstantExpr>(V1) || isa<ConstantExpr>(V2) ||
488 isa<ConstantPointerRef>(V1) || isa<ConstantPointerRef>(V2))
491 switch (V1->getType()->getPrimitiveID()) {
492 default: assert(0 && "Unknown value type for constant folding!");
493 case Type::BoolTyID: return BoolR;
494 case Type::PointerTyID: return NullPointerR;
495 case Type::SByteTyID: return SByteR;
496 case Type::UByteTyID: return UByteR;
497 case Type::ShortTyID: return ShortR;
498 case Type::UShortTyID: return UShortR;
499 case Type::IntTyID: return IntR;
500 case Type::UIntTyID: return UIntR;
501 case Type::LongTyID: return LongR;
502 case Type::ULongTyID: return ULongR;
503 case Type::FloatTyID: return FloatR;
504 case Type::DoubleTyID: return DoubleR;
509 //===----------------------------------------------------------------------===//
510 // ConstantFold*Instruction Implementations
511 //===----------------------------------------------------------------------===//
513 // These methods contain the special case hackery required to symbolically
514 // evaluate some constant expression cases, and use the ConstantRules class to
515 // evaluate normal constants.
517 static unsigned getSize(const Type *Ty) {
518 unsigned S = Ty->getPrimitiveSize();
519 return S ? S : 8; // Treat pointers at 8 bytes
522 Constant *llvm::ConstantFoldCastInstruction(const Constant *V,
523 const Type *DestTy) {
524 if (V->getType() == DestTy) return (Constant*)V;
526 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
527 if (CE->getOpcode() == Instruction::Cast) {
528 Constant *Op = const_cast<Constant*>(CE->getOperand(0));
529 // Try to not produce a cast of a cast, which is almost always redundant.
530 if (!Op->getType()->isFloatingPoint() &&
531 !CE->getType()->isFloatingPoint() &&
532 !DestTy->getType()->isFloatingPoint()) {
533 unsigned S1 = getSize(Op->getType()), S2 = getSize(CE->getType());
534 unsigned S3 = getSize(DestTy);
535 if (Op->getType() == DestTy && S3 >= S2)
537 if (S1 >= S2 && S2 >= S3)
538 return ConstantExpr::getCast(Op, DestTy);
539 if (S1 <= S2 && S2 >= S3 && S1 <= S3)
540 return ConstantExpr::getCast(Op, DestTy);
542 } else if (CE->getOpcode() == Instruction::GetElementPtr) {
543 // If all of the indexes in the GEP are null values, there is no pointer
544 // adjustment going on. We might as well cast the source pointer.
545 bool isAllNull = true;
546 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
547 if (!CE->getOperand(i)->isNullValue()) {
552 return ConstantExpr::getCast(CE->getOperand(0), DestTy);
555 ConstRules &Rules = ConstRules::get(V, V);
557 switch (DestTy->getPrimitiveID()) {
558 case Type::BoolTyID: return Rules.castToBool(V);
559 case Type::UByteTyID: return Rules.castToUByte(V);
560 case Type::SByteTyID: return Rules.castToSByte(V);
561 case Type::UShortTyID: return Rules.castToUShort(V);
562 case Type::ShortTyID: return Rules.castToShort(V);
563 case Type::UIntTyID: return Rules.castToUInt(V);
564 case Type::IntTyID: return Rules.castToInt(V);
565 case Type::ULongTyID: return Rules.castToULong(V);
566 case Type::LongTyID: return Rules.castToLong(V);
567 case Type::FloatTyID: return Rules.castToFloat(V);
568 case Type::DoubleTyID: return Rules.castToDouble(V);
569 case Type::PointerTyID:
570 return Rules.castToPointer(V, cast<PointerType>(DestTy));
575 /// IdxCompare - Compare the two constants as though they were getelementptr
576 /// indices. This allows coersion of the types to be the same thing.
578 /// If the two constants are the "same" (after coersion), return 0. If the
579 /// first is less than the second, return -1, if the second is less than the
580 /// first, return 1. If the constants are not integral, return -2.
582 static int IdxCompare(Constant *C1, Constant *C2) {
583 if (C1 == C2) return 0;
585 // Ok, we found a different index. Are either of the operands
586 // ConstantExprs? If so, we can't do anything with them.
587 if (!isa<ConstantInt>(C1) || !isa<ConstantInt>(C2))
588 return -2; // don't know!
590 // Ok, we have two differing integer indices. Convert them to
591 // be the same type. Long is always big enough, so we use it.
592 C1 = ConstantExpr::getCast(C1, Type::LongTy);
593 C2 = ConstantExpr::getCast(C2, Type::LongTy);
594 if (C1 == C2) return 0; // Are they just differing types?
596 // If they are really different, now that they are the same type, then we
597 // found a difference!
598 if (cast<ConstantSInt>(C1)->getValue() < cast<ConstantSInt>(C2)->getValue())
604 /// evaluateRelation - This function determines if there is anything we can
605 /// decide about the two constants provided. This doesn't need to handle simple
606 /// things like integer comparisons, but should instead handle ConstantExpr's
607 /// and ConstantPointerRef's. If we can determine that the two constants have a
608 /// particular relation to each other, we should return the corresponding SetCC
609 /// code, otherwise return Instruction::BinaryOpsEnd.
611 /// To simplify this code we canonicalize the relation so that the first
612 /// operand is always the most "complex" of the two. We consider simple
613 /// constants (like ConstantInt) to be the simplest, followed by
614 /// ConstantPointerRef's, followed by ConstantExpr's (the most complex).
616 static Instruction::BinaryOps evaluateRelation(const Constant *V1,
617 const Constant *V2) {
618 assert(V1->getType() == V2->getType() &&
619 "Cannot compare different types of values!");
620 if (V1 == V2) return Instruction::SetEQ;
622 if (!isa<ConstantExpr>(V1) && !isa<ConstantPointerRef>(V1)) {
623 // If the first operand is simple, swap operands.
624 assert((isa<ConstantPointerRef>(V2) || isa<ConstantExpr>(V2)) &&
625 "Simple cases should have been handled by caller!");
626 Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1);
627 if (SwappedRelation != Instruction::BinaryOpsEnd)
628 return SetCondInst::getSwappedCondition(SwappedRelation);
630 } else if (const ConstantPointerRef *CPR1 = dyn_cast<ConstantPointerRef>(V1)){
631 if (isa<ConstantExpr>(V2)) { // Swap as necessary.
632 Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1);
633 if (SwappedRelation != Instruction::BinaryOpsEnd)
634 return SetCondInst::getSwappedCondition(SwappedRelation);
636 return Instruction::BinaryOpsEnd;
639 // Now we know that the RHS is a ConstantPointerRef or simple constant,
640 // which (since the types must match) means that it's a ConstantPointerNull.
641 if (const ConstantPointerRef *CPR2 = dyn_cast<ConstantPointerRef>(V2)) {
642 assert(CPR1->getValue() != CPR2->getValue() &&
643 "CPRs for the same value exist at different addresses??");
644 // FIXME: If both globals are external weak, they might both be null!
645 return Instruction::SetNE;
647 assert(isa<ConstantPointerNull>(V2) && "Canonicalization guarantee!");
648 // Global can never be null. FIXME: if we implement external weak
649 // linkage, this is not necessarily true!
650 return Instruction::SetNE;
654 // Ok, the LHS is known to be a constantexpr. The RHS can be any of a
655 // constantexpr, a CPR, or a simple constant.
656 const ConstantExpr *CE1 = cast<ConstantExpr>(V1);
657 Constant *CE1Op0 = CE1->getOperand(0);
659 switch (CE1->getOpcode()) {
660 case Instruction::Cast:
661 // If the cast is not actually changing bits, and the second operand is a
662 // null pointer, do the comparison with the pre-casted value.
663 if (V2->isNullValue() &&
664 CE1->getType()->isLosslesslyConvertibleTo(CE1Op0->getType()))
665 return evaluateRelation(CE1Op0,
666 Constant::getNullValue(CE1Op0->getType()));
668 case Instruction::GetElementPtr:
669 // Ok, since this is a getelementptr, we know that the constant has a
670 // pointer type. Check the various cases.
671 if (isa<ConstantPointerNull>(V2)) {
672 // If we are comparing a GEP to a null pointer, check to see if the base
673 // of the GEP equals the null pointer.
674 if (isa<ConstantPointerRef>(CE1Op0)) {
675 // FIXME: this is not true when we have external weak references!
676 // No offset can go from a global to a null pointer.
677 return Instruction::SetGT;
678 } else if (isa<ConstantPointerNull>(CE1Op0)) {
679 // If we are indexing from a null pointer, check to see if we have any
681 for (unsigned i = 1, e = CE1->getNumOperands(); i != e; ++i)
682 if (!CE1->getOperand(i)->isNullValue())
683 // Offsetting from null, must not be equal.
684 return Instruction::SetGT;
685 // Only zero indexes from null, must still be zero.
686 return Instruction::SetEQ;
688 // Otherwise, we can't really say if the first operand is null or not.
689 } else if (const ConstantPointerRef *CPR2 =
690 dyn_cast<ConstantPointerRef>(V2)) {
691 if (isa<ConstantPointerNull>(CE1Op0)) {
692 // FIXME: This is not true with external weak references.
693 return Instruction::SetLT;
694 } else if (const ConstantPointerRef *CPR1 =
695 dyn_cast<ConstantPointerRef>(CE1Op0)) {
697 // If this is a getelementptr of the same global, then it must be
698 // different. Because the types must match, the getelementptr could
699 // only have at most one index, and because we fold getelementptr's
700 // with a single zero index, it must be nonzero.
701 assert(CE1->getNumOperands() == 2 &&
702 !CE1->getOperand(1)->isNullValue() &&
703 "Suprising getelementptr!");
704 return Instruction::SetGT;
706 // If they are different globals, we don't know what the value is,
707 // but they can't be equal.
708 return Instruction::SetNE;
712 const ConstantExpr *CE2 = cast<ConstantExpr>(V2);
713 const Constant *CE2Op0 = CE2->getOperand(0);
715 // There are MANY other foldings that we could perform here. They will
716 // probably be added on demand, as they seem needed.
717 switch (CE2->getOpcode()) {
719 case Instruction::GetElementPtr:
720 // By far the most common case to handle is when the base pointers are
721 // obviously to the same or different globals.
722 if (isa<ConstantPointerRef>(CE1Op0) &&
723 isa<ConstantPointerRef>(CE2Op0)) {
724 if (CE1Op0 != CE2Op0) // Don't know relative ordering, but not equal
725 return Instruction::SetNE;
726 // Ok, we know that both getelementptr instructions are based on the
727 // same global. From this, we can precisely determine the relative
728 // ordering of the resultant pointers.
731 // Compare all of the operands the GEP's have in common.
732 for (;i != CE1->getNumOperands() && i != CE2->getNumOperands(); ++i)
733 switch (IdxCompare(CE1->getOperand(i), CE2->getOperand(i))) {
734 case -1: return Instruction::SetLT;
735 case 1: return Instruction::SetGT;
736 case -2: return Instruction::BinaryOpsEnd;
739 // Ok, we ran out of things they have in common. If any leftovers
740 // are non-zero then we have a difference, otherwise we are equal.
741 for (; i < CE1->getNumOperands(); ++i)
742 if (!CE1->getOperand(i)->isNullValue())
743 return Instruction::SetGT;
744 for (; i < CE2->getNumOperands(); ++i)
745 if (!CE2->getOperand(i)->isNullValue())
746 return Instruction::SetLT;
747 return Instruction::SetEQ;
757 return Instruction::BinaryOpsEnd;
760 Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode,
762 const Constant *V2) {
766 case Instruction::Add: C = ConstRules::get(V1, V2).add(V1, V2); break;
767 case Instruction::Sub: C = ConstRules::get(V1, V2).sub(V1, V2); break;
768 case Instruction::Mul: C = ConstRules::get(V1, V2).mul(V1, V2); break;
769 case Instruction::Div: C = ConstRules::get(V1, V2).div(V1, V2); break;
770 case Instruction::Rem: C = ConstRules::get(V1, V2).rem(V1, V2); break;
771 case Instruction::And: C = ConstRules::get(V1, V2).op_and(V1, V2); break;
772 case Instruction::Or: C = ConstRules::get(V1, V2).op_or (V1, V2); break;
773 case Instruction::Xor: C = ConstRules::get(V1, V2).op_xor(V1, V2); break;
774 case Instruction::Shl: C = ConstRules::get(V1, V2).shl(V1, V2); break;
775 case Instruction::Shr: C = ConstRules::get(V1, V2).shr(V1, V2); break;
776 case Instruction::SetEQ: C = ConstRules::get(V1, V2).equalto(V1, V2); break;
777 case Instruction::SetLT: C = ConstRules::get(V1, V2).lessthan(V1, V2);break;
778 case Instruction::SetGT: C = ConstRules::get(V1, V2).lessthan(V2, V1);break;
779 case Instruction::SetNE: // V1 != V2 === !(V1 == V2)
780 C = ConstRules::get(V1, V2).equalto(V1, V2);
781 if (C) return ConstantExpr::get(Instruction::Xor, C, ConstantBool::True);
783 case Instruction::SetLE: // V1 <= V2 === !(V2 < V1)
784 C = ConstRules::get(V1, V2).lessthan(V2, V1);
785 if (C) return ConstantExpr::get(Instruction::Xor, C, ConstantBool::True);
787 case Instruction::SetGE: // V1 >= V2 === !(V1 < V2)
788 C = ConstRules::get(V1, V2).lessthan(V1, V2);
789 if (C) return ConstantExpr::get(Instruction::Xor, C, ConstantBool::True);
793 // If we successfully folded the expression, return it now.
796 if (SetCondInst::isRelational(Opcode))
797 switch (evaluateRelation(V1, V2)) {
798 default: assert(0 && "Unknown relational!");
799 case Instruction::BinaryOpsEnd:
800 break; // Couldn't determine anything about these constants.
801 case Instruction::SetEQ: // We know the constants are equal!
802 // If we know the constants are equal, we can decide the result of this
803 // computation precisely.
804 return ConstantBool::get(Opcode == Instruction::SetEQ ||
805 Opcode == Instruction::SetLE ||
806 Opcode == Instruction::SetGE);
807 case Instruction::SetLT:
808 // If we know that V1 < V2, we can decide the result of this computation
810 return ConstantBool::get(Opcode == Instruction::SetLT ||
811 Opcode == Instruction::SetNE ||
812 Opcode == Instruction::SetLE);
813 case Instruction::SetGT:
814 // If we know that V1 > V2, we can decide the result of this computation
816 return ConstantBool::get(Opcode == Instruction::SetGT ||
817 Opcode == Instruction::SetNE ||
818 Opcode == Instruction::SetGE);
819 case Instruction::SetLE:
820 // If we know that V1 <= V2, we can only partially decide this relation.
821 if (Opcode == Instruction::SetGT) return ConstantBool::False;
822 if (Opcode == Instruction::SetLT) return ConstantBool::True;
825 case Instruction::SetGE:
826 // If we know that V1 >= V2, we can only partially decide this relation.
827 if (Opcode == Instruction::SetLT) return ConstantBool::False;
828 if (Opcode == Instruction::SetGT) return ConstantBool::True;
831 case Instruction::SetNE:
832 // If we know that V1 != V2, we can only partially decide this relation.
833 if (Opcode == Instruction::SetEQ) return ConstantBool::False;
834 if (Opcode == Instruction::SetNE) return ConstantBool::True;
838 if (const ConstantExpr *CE1 = dyn_cast<ConstantExpr>(V1)) {
839 if (const ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2)) {
840 // There are many possible foldings we could do here. We should probably
841 // at least fold add of a pointer with an integer into the appropriate
842 // getelementptr. This will improve alias analysis a bit.
848 // Just implement a couple of simple identities.
850 case Instruction::Add:
851 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X + 0 == X
853 case Instruction::Sub:
854 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X - 0 == X
856 case Instruction::Mul:
857 if (V2->isNullValue()) return const_cast<Constant*>(V2); // X * 0 == 0
858 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
859 if (CI->getRawValue() == 1)
860 return const_cast<Constant*>(V1); // X * 1 == X
862 case Instruction::Div:
863 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
864 if (CI->getRawValue() == 1)
865 return const_cast<Constant*>(V1); // X / 1 == X
867 case Instruction::Rem:
868 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
869 if (CI->getRawValue() == 1)
870 return Constant::getNullValue(CI->getType()); // X % 1 == 0
872 case Instruction::And:
873 if (cast<ConstantIntegral>(V2)->isAllOnesValue())
874 return const_cast<Constant*>(V1); // X & -1 == X
875 if (V2->isNullValue()) return const_cast<Constant*>(V2); // X & 0 == 0
877 case Instruction::Or:
878 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X | 0 == X
879 if (cast<ConstantIntegral>(V2)->isAllOnesValue())
880 return const_cast<Constant*>(V2); // X | -1 == -1
882 case Instruction::Xor:
883 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X ^ 0 == X
888 } else if (const ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2)) {
889 // If V2 is a constant expr and V1 isn't, flop them around and fold the
890 // other way if possible.
892 case Instruction::Add:
893 case Instruction::Mul:
894 case Instruction::And:
895 case Instruction::Or:
896 case Instruction::Xor:
897 case Instruction::SetEQ:
898 case Instruction::SetNE:
899 // No change of opcode required.
900 return ConstantFoldBinaryInstruction(Opcode, V2, V1);
902 case Instruction::SetLT:
903 case Instruction::SetGT:
904 case Instruction::SetLE:
905 case Instruction::SetGE:
906 // Change the opcode as necessary to swap the operands.
907 Opcode = SetCondInst::getSwappedCondition((Instruction::BinaryOps)Opcode);
908 return ConstantFoldBinaryInstruction(Opcode, V2, V1);
910 case Instruction::Shl:
911 case Instruction::Shr:
912 case Instruction::Sub:
913 case Instruction::Div:
914 case Instruction::Rem:
915 default: // These instructions cannot be flopped around.
922 Constant *llvm::ConstantFoldGetElementPtr(const Constant *C,
923 const std::vector<Constant*> &IdxList) {
924 if (IdxList.size() == 0 ||
925 (IdxList.size() == 1 && IdxList[0]->isNullValue()))
926 return const_cast<Constant*>(C);
928 if (C->isNullValue()) {
930 for (unsigned i = 0, e = IdxList.size(); i != e; ++i)
931 if (!IdxList[i]->isNullValue()) {
936 std::vector<Value*> VIdxList(IdxList.begin(), IdxList.end());
937 const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), VIdxList,
939 assert(Ty != 0 && "Invalid indices for GEP!");
940 return ConstantPointerNull::get(PointerType::get(Ty));
944 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(const_cast<Constant*>(C))) {
945 // Combine Indices - If the source pointer to this getelementptr instruction
946 // is a getelementptr instruction, combine the indices of the two
947 // getelementptr instructions into a single instruction.
949 if (CE->getOpcode() == Instruction::GetElementPtr) {
950 const Type *LastTy = 0;
951 for (gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
955 if ((LastTy && isa<ArrayType>(LastTy)) || IdxList[0]->isNullValue()) {
956 std::vector<Constant*> NewIndices;
957 NewIndices.reserve(IdxList.size() + CE->getNumOperands());
958 for (unsigned i = 1, e = CE->getNumOperands()-1; i != e; ++i)
959 NewIndices.push_back(cast<Constant>(CE->getOperand(i)));
961 // Add the last index of the source with the first index of the new GEP.
962 // Make sure to handle the case when they are actually different types.
963 Constant *Combined = CE->getOperand(CE->getNumOperands()-1);
964 if (!IdxList[0]->isNullValue()) // Otherwise it must be an array
966 ConstantExpr::get(Instruction::Add,
967 ConstantExpr::getCast(IdxList[0], Type::LongTy),
968 ConstantExpr::getCast(Combined, Type::LongTy));
970 NewIndices.push_back(Combined);
971 NewIndices.insert(NewIndices.end(), IdxList.begin()+1, IdxList.end());
972 return ConstantExpr::getGetElementPtr(CE->getOperand(0), NewIndices);
976 // Implement folding of:
977 // int* getelementptr ([2 x int]* cast ([3 x int]* %X to [2 x int]*),
979 // To: int* getelementptr ([3 x int]* %X, long 0, long 0)
981 if (CE->getOpcode() == Instruction::Cast && IdxList.size() > 1 &&
982 IdxList[0]->isNullValue())
983 if (const PointerType *SPT =
984 dyn_cast<PointerType>(CE->getOperand(0)->getType()))
985 if (const ArrayType *SAT = dyn_cast<ArrayType>(SPT->getElementType()))
986 if (const ArrayType *CAT =
987 dyn_cast<ArrayType>(cast<PointerType>(C->getType())->getElementType()))
988 if (CAT->getElementType() == SAT->getElementType())
989 return ConstantExpr::getGetElementPtr(
990 (Constant*)CE->getOperand(0), IdxList);