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/Compiler.h"
27 #include "llvm/Support/GetElementPtrTypeIterator.h"
28 #include "llvm/Support/ManagedStatic.h"
29 #include "llvm/Support/MathExtras.h"
35 struct VISIBILITY_HIDDEN ConstRules {
37 virtual ~ConstRules() {}
39 // Binary Operators...
40 virtual Constant *add(const Constant *V1, const Constant *V2) const = 0;
41 virtual Constant *sub(const Constant *V1, const Constant *V2) const = 0;
42 virtual Constant *mul(const Constant *V1, const Constant *V2) const = 0;
43 virtual Constant *urem(const Constant *V1, const Constant *V2) const = 0;
44 virtual Constant *srem(const Constant *V1, const Constant *V2) const = 0;
45 virtual Constant *frem(const Constant *V1, const Constant *V2) const = 0;
46 virtual Constant *udiv(const Constant *V1, const Constant *V2) const = 0;
47 virtual Constant *sdiv(const Constant *V1, const Constant *V2) const = 0;
48 virtual Constant *fdiv(const Constant *V1, const Constant *V2) const = 0;
49 virtual Constant *op_and(const Constant *V1, const Constant *V2) const = 0;
50 virtual Constant *op_or (const Constant *V1, const Constant *V2) const = 0;
51 virtual Constant *op_xor(const Constant *V1, const Constant *V2) const = 0;
52 virtual Constant *shl(const Constant *V1, const Constant *V2) const = 0;
53 virtual Constant *shr(const Constant *V1, const Constant *V2) const = 0;
54 virtual Constant *lessthan(const Constant *V1, const Constant *V2) const =0;
55 virtual Constant *equalto(const Constant *V1, const Constant *V2) const = 0;
58 virtual Constant *castToBool (const Constant *V) const = 0;
59 virtual Constant *castToSByte (const Constant *V) const = 0;
60 virtual Constant *castToUByte (const Constant *V) const = 0;
61 virtual Constant *castToShort (const Constant *V) const = 0;
62 virtual Constant *castToUShort(const Constant *V) const = 0;
63 virtual Constant *castToInt (const Constant *V) const = 0;
64 virtual Constant *castToUInt (const Constant *V) const = 0;
65 virtual Constant *castToLong (const Constant *V) const = 0;
66 virtual Constant *castToULong (const Constant *V) const = 0;
67 virtual Constant *castToFloat (const Constant *V) const = 0;
68 virtual Constant *castToDouble(const Constant *V) const = 0;
69 virtual Constant *castToPointer(const Constant *V,
70 const PointerType *Ty) const = 0;
72 // ConstRules::get - Return an instance of ConstRules for the specified
75 static ConstRules &get(const Constant *V1, const Constant *V2);
77 ConstRules(const ConstRules &); // Do not implement
78 ConstRules &operator=(const ConstRules &); // Do not implement
83 //===----------------------------------------------------------------------===//
84 // TemplateRules Class
85 //===----------------------------------------------------------------------===//
87 // TemplateRules - Implement a subclass of ConstRules that provides all
88 // operations as noops. All other rules classes inherit from this class so
89 // that if functionality is needed in the future, it can simply be added here
90 // and to ConstRules without changing anything else...
92 // This class also provides subclasses with typesafe implementations of methods
93 // so that don't have to do type casting.
96 template<class ArgType, class SubClassName>
97 class VISIBILITY_HIDDEN TemplateRules : public ConstRules {
100 //===--------------------------------------------------------------------===//
101 // Redirecting functions that cast to the appropriate types
102 //===--------------------------------------------------------------------===//
104 virtual Constant *add(const Constant *V1, const Constant *V2) const {
105 return SubClassName::Add((const ArgType *)V1, (const ArgType *)V2);
107 virtual Constant *sub(const Constant *V1, const Constant *V2) const {
108 return SubClassName::Sub((const ArgType *)V1, (const ArgType *)V2);
110 virtual Constant *mul(const Constant *V1, const Constant *V2) const {
111 return SubClassName::Mul((const ArgType *)V1, (const ArgType *)V2);
113 virtual Constant *udiv(const Constant *V1, const Constant *V2) const {
114 return SubClassName::UDiv((const ArgType *)V1, (const ArgType *)V2);
116 virtual Constant *sdiv(const Constant *V1, const Constant *V2) const {
117 return SubClassName::SDiv((const ArgType *)V1, (const ArgType *)V2);
119 virtual Constant *fdiv(const Constant *V1, const Constant *V2) const {
120 return SubClassName::FDiv((const ArgType *)V1, (const ArgType *)V2);
122 virtual Constant *urem(const Constant *V1, const Constant *V2) const {
123 return SubClassName::URem((const ArgType *)V1, (const ArgType *)V2);
125 virtual Constant *srem(const Constant *V1, const Constant *V2) const {
126 return SubClassName::SRem((const ArgType *)V1, (const ArgType *)V2);
128 virtual Constant *frem(const Constant *V1, const Constant *V2) const {
129 return SubClassName::FRem((const ArgType *)V1, (const ArgType *)V2);
131 virtual Constant *op_and(const Constant *V1, const Constant *V2) const {
132 return SubClassName::And((const ArgType *)V1, (const ArgType *)V2);
134 virtual Constant *op_or(const Constant *V1, const Constant *V2) const {
135 return SubClassName::Or((const ArgType *)V1, (const ArgType *)V2);
137 virtual Constant *op_xor(const Constant *V1, const Constant *V2) const {
138 return SubClassName::Xor((const ArgType *)V1, (const ArgType *)V2);
140 virtual Constant *shl(const Constant *V1, const Constant *V2) const {
141 return SubClassName::Shl((const ArgType *)V1, (const ArgType *)V2);
143 virtual Constant *shr(const Constant *V1, const Constant *V2) const {
144 return SubClassName::Shr((const ArgType *)V1, (const ArgType *)V2);
147 virtual Constant *lessthan(const Constant *V1, const Constant *V2) const {
148 return SubClassName::LessThan((const ArgType *)V1, (const ArgType *)V2);
150 virtual Constant *equalto(const Constant *V1, const Constant *V2) const {
151 return SubClassName::EqualTo((const ArgType *)V1, (const ArgType *)V2);
154 // Casting operators. ick
155 virtual Constant *castToBool(const Constant *V) const {
156 return SubClassName::CastToBool((const ArgType*)V);
158 virtual Constant *castToSByte(const Constant *V) const {
159 return SubClassName::CastToSByte((const ArgType*)V);
161 virtual Constant *castToUByte(const Constant *V) const {
162 return SubClassName::CastToUByte((const ArgType*)V);
164 virtual Constant *castToShort(const Constant *V) const {
165 return SubClassName::CastToShort((const ArgType*)V);
167 virtual Constant *castToUShort(const Constant *V) const {
168 return SubClassName::CastToUShort((const ArgType*)V);
170 virtual Constant *castToInt(const Constant *V) const {
171 return SubClassName::CastToInt((const ArgType*)V);
173 virtual Constant *castToUInt(const Constant *V) const {
174 return SubClassName::CastToUInt((const ArgType*)V);
176 virtual Constant *castToLong(const Constant *V) const {
177 return SubClassName::CastToLong((const ArgType*)V);
179 virtual Constant *castToULong(const Constant *V) const {
180 return SubClassName::CastToULong((const ArgType*)V);
182 virtual Constant *castToFloat(const Constant *V) const {
183 return SubClassName::CastToFloat((const ArgType*)V);
185 virtual Constant *castToDouble(const Constant *V) const {
186 return SubClassName::CastToDouble((const ArgType*)V);
188 virtual Constant *castToPointer(const Constant *V,
189 const PointerType *Ty) const {
190 return SubClassName::CastToPointer((const ArgType*)V, Ty);
193 //===--------------------------------------------------------------------===//
194 // Default "noop" implementations
195 //===--------------------------------------------------------------------===//
197 static Constant *Add (const ArgType *V1, const ArgType *V2) { return 0; }
198 static Constant *Sub (const ArgType *V1, const ArgType *V2) { return 0; }
199 static Constant *Mul (const ArgType *V1, const ArgType *V2) { return 0; }
200 static Constant *SDiv(const ArgType *V1, const ArgType *V2) { return 0; }
201 static Constant *UDiv(const ArgType *V1, const ArgType *V2) { return 0; }
202 static Constant *FDiv(const ArgType *V1, const ArgType *V2) { return 0; }
203 static Constant *URem(const ArgType *V1, const ArgType *V2) { return 0; }
204 static Constant *SRem(const ArgType *V1, const ArgType *V2) { return 0; }
205 static Constant *FRem(const ArgType *V1, const ArgType *V2) { return 0; }
206 static Constant *And (const ArgType *V1, const ArgType *V2) { return 0; }
207 static Constant *Or (const ArgType *V1, const ArgType *V2) { return 0; }
208 static Constant *Xor (const ArgType *V1, const ArgType *V2) { return 0; }
209 static Constant *Shl (const ArgType *V1, const ArgType *V2) { return 0; }
210 static Constant *Shr (const ArgType *V1, const ArgType *V2) { return 0; }
211 static Constant *LessThan(const ArgType *V1, const ArgType *V2) {
214 static Constant *EqualTo(const ArgType *V1, const ArgType *V2) {
218 // Casting operators. ick
219 static Constant *CastToBool (const Constant *V) { return 0; }
220 static Constant *CastToSByte (const Constant *V) { return 0; }
221 static Constant *CastToUByte (const Constant *V) { return 0; }
222 static Constant *CastToShort (const Constant *V) { return 0; }
223 static Constant *CastToUShort(const Constant *V) { return 0; }
224 static Constant *CastToInt (const Constant *V) { return 0; }
225 static Constant *CastToUInt (const Constant *V) { return 0; }
226 static Constant *CastToLong (const Constant *V) { return 0; }
227 static Constant *CastToULong (const Constant *V) { return 0; }
228 static Constant *CastToFloat (const Constant *V) { return 0; }
229 static Constant *CastToDouble(const Constant *V) { return 0; }
230 static Constant *CastToPointer(const Constant *,
231 const PointerType *) {return 0;}
234 virtual ~TemplateRules() {}
236 } // end anonymous namespace
239 //===----------------------------------------------------------------------===//
241 //===----------------------------------------------------------------------===//
243 // EmptyRules provides a concrete base class of ConstRules that does nothing
246 struct VISIBILITY_HIDDEN EmptyRules
247 : public TemplateRules<Constant, EmptyRules> {
248 static Constant *EqualTo(const Constant *V1, const Constant *V2) {
249 if (V1 == V2) return ConstantBool::getTrue();
253 } // end anonymous namespace
257 //===----------------------------------------------------------------------===//
259 //===----------------------------------------------------------------------===//
261 // BoolRules provides a concrete base class of ConstRules for the 'bool' type.
264 struct VISIBILITY_HIDDEN BoolRules
265 : public TemplateRules<ConstantBool, BoolRules> {
267 static Constant *LessThan(const ConstantBool *V1, const ConstantBool *V2) {
268 return ConstantBool::get(V1->getValue() < V2->getValue());
271 static Constant *EqualTo(const Constant *V1, const Constant *V2) {
272 return ConstantBool::get(V1 == V2);
275 static Constant *And(const ConstantBool *V1, const ConstantBool *V2) {
276 return ConstantBool::get(V1->getValue() & V2->getValue());
279 static Constant *Or(const ConstantBool *V1, const ConstantBool *V2) {
280 return ConstantBool::get(V1->getValue() | V2->getValue());
283 static Constant *Xor(const ConstantBool *V1, const ConstantBool *V2) {
284 return ConstantBool::get(V1->getValue() ^ V2->getValue());
287 // Casting operators. ick
288 #define DEF_CAST(TYPE, CLASS, CTYPE) \
289 static Constant *CastTo##TYPE (const ConstantBool *V) { \
290 return CLASS::get(Type::TYPE##Ty, (CTYPE)(bool)V->getValue()); \
293 DEF_CAST(Bool , ConstantBool, bool)
294 DEF_CAST(SByte , ConstantInt, signed char)
295 DEF_CAST(UByte , ConstantInt, unsigned char)
296 DEF_CAST(Short , ConstantInt, signed short)
297 DEF_CAST(UShort, ConstantInt, unsigned short)
298 DEF_CAST(Int , ConstantInt, signed int)
299 DEF_CAST(UInt , ConstantInt, unsigned int)
300 DEF_CAST(Long , ConstantInt, int64_t)
301 DEF_CAST(ULong , ConstantInt, uint64_t)
302 DEF_CAST(Float , ConstantFP , float)
303 DEF_CAST(Double, ConstantFP , double)
306 } // end anonymous namespace
309 //===----------------------------------------------------------------------===//
310 // NullPointerRules Class
311 //===----------------------------------------------------------------------===//
313 // NullPointerRules provides a concrete base class of ConstRules for null
317 struct VISIBILITY_HIDDEN NullPointerRules
318 : public TemplateRules<ConstantPointerNull, NullPointerRules> {
319 static Constant *EqualTo(const Constant *V1, const Constant *V2) {
320 return ConstantBool::getTrue(); // Null pointers are always equal
322 static Constant *CastToBool(const Constant *V) {
323 return ConstantBool::getFalse();
325 static Constant *CastToSByte (const Constant *V) {
326 return ConstantInt::get(Type::SByteTy, 0);
328 static Constant *CastToUByte (const Constant *V) {
329 return ConstantInt::get(Type::UByteTy, 0);
331 static Constant *CastToShort (const Constant *V) {
332 return ConstantInt::get(Type::ShortTy, 0);
334 static Constant *CastToUShort(const Constant *V) {
335 return ConstantInt::get(Type::UShortTy, 0);
337 static Constant *CastToInt (const Constant *V) {
338 return ConstantInt::get(Type::IntTy, 0);
340 static Constant *CastToUInt (const Constant *V) {
341 return ConstantInt::get(Type::UIntTy, 0);
343 static Constant *CastToLong (const Constant *V) {
344 return ConstantInt::get(Type::LongTy, 0);
346 static Constant *CastToULong (const Constant *V) {
347 return ConstantInt::get(Type::ULongTy, 0);
349 static Constant *CastToFloat (const Constant *V) {
350 return ConstantFP::get(Type::FloatTy, 0);
352 static Constant *CastToDouble(const Constant *V) {
353 return ConstantFP::get(Type::DoubleTy, 0);
356 static Constant *CastToPointer(const ConstantPointerNull *V,
357 const PointerType *PTy) {
358 return ConstantPointerNull::get(PTy);
361 } // end anonymous namespace
363 //===----------------------------------------------------------------------===//
364 // ConstantPackedRules Class
365 //===----------------------------------------------------------------------===//
367 /// DoVectorOp - Given two packed constants and a function pointer, apply the
368 /// function pointer to each element pair, producing a new ConstantPacked
370 static Constant *EvalVectorOp(const ConstantPacked *V1,
371 const ConstantPacked *V2,
372 Constant *(*FP)(Constant*, Constant*)) {
373 std::vector<Constant*> Res;
374 for (unsigned i = 0, e = V1->getNumOperands(); i != e; ++i)
375 Res.push_back(FP(const_cast<Constant*>(V1->getOperand(i)),
376 const_cast<Constant*>(V2->getOperand(i))));
377 return ConstantPacked::get(Res);
380 /// PackedTypeRules provides a concrete base class of ConstRules for
381 /// ConstantPacked operands.
384 struct VISIBILITY_HIDDEN ConstantPackedRules
385 : public TemplateRules<ConstantPacked, ConstantPackedRules> {
387 static Constant *Add(const ConstantPacked *V1, const ConstantPacked *V2) {
388 return EvalVectorOp(V1, V2, ConstantExpr::getAdd);
390 static Constant *Sub(const ConstantPacked *V1, const ConstantPacked *V2) {
391 return EvalVectorOp(V1, V2, ConstantExpr::getSub);
393 static Constant *Mul(const ConstantPacked *V1, const ConstantPacked *V2) {
394 return EvalVectorOp(V1, V2, ConstantExpr::getMul);
396 static Constant *UDiv(const ConstantPacked *V1, const ConstantPacked *V2) {
397 return EvalVectorOp(V1, V2, ConstantExpr::getUDiv);
399 static Constant *SDiv(const ConstantPacked *V1, const ConstantPacked *V2) {
400 return EvalVectorOp(V1, V2, ConstantExpr::getSDiv);
402 static Constant *FDiv(const ConstantPacked *V1, const ConstantPacked *V2) {
403 return EvalVectorOp(V1, V2, ConstantExpr::getFDiv);
405 static Constant *URem(const ConstantPacked *V1, const ConstantPacked *V2) {
406 return EvalVectorOp(V1, V2, ConstantExpr::getURem);
408 static Constant *SRem(const ConstantPacked *V1, const ConstantPacked *V2) {
409 return EvalVectorOp(V1, V2, ConstantExpr::getSRem);
411 static Constant *FRem(const ConstantPacked *V1, const ConstantPacked *V2) {
412 return EvalVectorOp(V1, V2, ConstantExpr::getFRem);
414 static Constant *And(const ConstantPacked *V1, const ConstantPacked *V2) {
415 return EvalVectorOp(V1, V2, ConstantExpr::getAnd);
417 static Constant *Or (const ConstantPacked *V1, const ConstantPacked *V2) {
418 return EvalVectorOp(V1, V2, ConstantExpr::getOr);
420 static Constant *Xor(const ConstantPacked *V1, const ConstantPacked *V2) {
421 return EvalVectorOp(V1, V2, ConstantExpr::getXor);
423 static Constant *Shl(const ConstantPacked *V1, const ConstantPacked *V2) {
424 return EvalVectorOp(V1, V2, ConstantExpr::getShl);
426 static Constant *Shr(const ConstantPacked *V1, const ConstantPacked *V2) {
427 return EvalVectorOp(V1, V2, ConstantExpr::getShr);
429 static Constant *LessThan(const ConstantPacked *V1, const ConstantPacked *V2){
432 static Constant *EqualTo(const ConstantPacked *V1, const ConstantPacked *V2) {
433 for (unsigned i = 0, e = V1->getNumOperands(); i != e; ++i) {
435 ConstantExpr::getSetEQ(const_cast<Constant*>(V1->getOperand(i)),
436 const_cast<Constant*>(V2->getOperand(i)));
437 if (ConstantBool *CB = dyn_cast<ConstantBool>(C))
440 // Otherwise, could not decide from any element pairs.
444 } // end anonymous namespace
447 //===----------------------------------------------------------------------===//
448 // GeneralPackedRules Class
449 //===----------------------------------------------------------------------===//
451 /// GeneralPackedRules provides a concrete base class of ConstRules for
452 /// PackedType operands, where both operands are not ConstantPacked. The usual
453 /// cause for this is that one operand is a ConstantAggregateZero.
456 struct VISIBILITY_HIDDEN GeneralPackedRules
457 : public TemplateRules<Constant, GeneralPackedRules> {
459 } // end anonymous namespace
462 //===----------------------------------------------------------------------===//
463 // DirectIntRules Class
464 //===----------------------------------------------------------------------===//
466 // DirectIntRules provides implementations of functions that are valid on
467 // integer types, but not all types in general.
470 template <class BuiltinType, Type **Ty>
471 struct VISIBILITY_HIDDEN DirectIntRules
472 : public TemplateRules<ConstantInt, DirectIntRules<BuiltinType, Ty> > {
474 static Constant *Add(const ConstantInt *V1, const ConstantInt *V2) {
475 BuiltinType R = (BuiltinType)V1->getZExtValue() +
476 (BuiltinType)V2->getZExtValue();
477 return ConstantInt::get(*Ty, R);
480 static Constant *Sub(const ConstantInt *V1, const ConstantInt *V2) {
481 BuiltinType R = (BuiltinType)V1->getZExtValue() -
482 (BuiltinType)V2->getZExtValue();
483 return ConstantInt::get(*Ty, R);
486 static Constant *Mul(const ConstantInt *V1, const ConstantInt *V2) {
487 BuiltinType R = (BuiltinType)V1->getZExtValue() *
488 (BuiltinType)V2->getZExtValue();
489 return ConstantInt::get(*Ty, R);
492 static Constant *LessThan(const ConstantInt *V1, const ConstantInt *V2) {
493 bool R = (BuiltinType)V1->getZExtValue() < (BuiltinType)V2->getZExtValue();
494 return ConstantBool::get(R);
497 static Constant *EqualTo(const ConstantInt *V1, const ConstantInt *V2) {
498 bool R = (BuiltinType)V1->getZExtValue() == (BuiltinType)V2->getZExtValue();
499 return ConstantBool::get(R);
502 static Constant *CastToPointer(const ConstantInt *V,
503 const PointerType *PTy) {
504 if (V->isNullValue()) // Is it a FP or Integral null value?
505 return ConstantPointerNull::get(PTy);
506 return 0; // Can't const prop other types of pointers
509 // Casting operators. ick
510 #define DEF_CAST(TYPE, CLASS, CTYPE) \
511 static Constant *CastTo##TYPE (const ConstantInt *V) { \
512 return CLASS::get(Type::TYPE##Ty, (CTYPE)(BuiltinType)V->getZExtValue()); \
515 DEF_CAST(Bool , ConstantBool, bool)
516 DEF_CAST(SByte , ConstantInt, signed char)
517 DEF_CAST(UByte , ConstantInt, unsigned char)
518 DEF_CAST(Short , ConstantInt, signed short)
519 DEF_CAST(UShort, ConstantInt, unsigned short)
520 DEF_CAST(Int , ConstantInt, signed int)
521 DEF_CAST(UInt , ConstantInt, unsigned int)
522 DEF_CAST(Long , ConstantInt, int64_t)
523 DEF_CAST(ULong , ConstantInt, uint64_t)
524 DEF_CAST(Float , ConstantFP , float)
525 DEF_CAST(Double, ConstantFP , double)
528 static Constant *UDiv(const ConstantInt *V1, const ConstantInt *V2) {
529 if (V2->isNullValue()) // X / 0
531 BuiltinType R = (BuiltinType)(V1->getZExtValue() / V2->getZExtValue());
532 return ConstantInt::get(*Ty, R);
535 static Constant *SDiv(const ConstantInt *V1, const ConstantInt *V2) {
536 if (V2->isNullValue()) // X / 0
538 if (V2->isAllOnesValue() && // MIN_INT / -1
539 (BuiltinType)V1->getSExtValue() == -(BuiltinType)V1->getSExtValue())
541 BuiltinType R = (BuiltinType)(V1->getSExtValue() / V2->getSExtValue());
542 return ConstantInt::get(*Ty, R);
545 static Constant *URem(const ConstantInt *V1,
546 const ConstantInt *V2) {
547 if (V2->isNullValue()) return 0; // X / 0
548 BuiltinType R = (BuiltinType)(V1->getZExtValue() % V2->getZExtValue());
549 return ConstantInt::get(*Ty, R);
552 static Constant *SRem(const ConstantInt *V1,
553 const ConstantInt *V2) {
554 if (V2->isNullValue()) return 0; // X % 0
555 if (V2->isAllOnesValue() && // MIN_INT % -1
556 (BuiltinType)V1->getSExtValue() == -(BuiltinType)V1->getSExtValue())
558 BuiltinType R = (BuiltinType)(V1->getSExtValue() % V2->getSExtValue());
559 return ConstantInt::get(*Ty, R);
562 static Constant *And(const ConstantInt *V1, const ConstantInt *V2) {
564 (BuiltinType)V1->getZExtValue() & (BuiltinType)V2->getZExtValue();
565 return ConstantInt::get(*Ty, R);
567 static Constant *Or(const ConstantInt *V1, const ConstantInt *V2) {
569 (BuiltinType)V1->getZExtValue() | (BuiltinType)V2->getZExtValue();
570 return ConstantInt::get(*Ty, R);
572 static Constant *Xor(const ConstantInt *V1, const ConstantInt *V2) {
574 (BuiltinType)V1->getZExtValue() ^ (BuiltinType)V2->getZExtValue();
575 return ConstantInt::get(*Ty, R);
578 static Constant *Shl(const ConstantInt *V1, const ConstantInt *V2) {
580 (BuiltinType)V1->getZExtValue() << (BuiltinType)V2->getZExtValue();
581 return ConstantInt::get(*Ty, R);
584 static Constant *Shr(const ConstantInt *V1, const ConstantInt *V2) {
586 (BuiltinType)V1->getZExtValue() >> (BuiltinType)V2->getZExtValue();
587 return ConstantInt::get(*Ty, R);
590 } // end anonymous namespace
593 //===----------------------------------------------------------------------===//
594 // DirectFPRules Class
595 //===----------------------------------------------------------------------===//
597 /// DirectFPRules provides implementations of functions that are valid on
598 /// floating point types, but not all types in general.
601 template <class BuiltinType, Type **Ty>
602 struct VISIBILITY_HIDDEN DirectFPRules
603 : public TemplateRules<ConstantFP, DirectFPRules<BuiltinType, Ty> > {
605 static Constant *Add(const ConstantFP *V1, const ConstantFP *V2) {
606 BuiltinType R = (BuiltinType)V1->getValue() +
607 (BuiltinType)V2->getValue();
608 return ConstantFP::get(*Ty, R);
611 static Constant *Sub(const ConstantFP *V1, const ConstantFP *V2) {
612 BuiltinType R = (BuiltinType)V1->getValue() - (BuiltinType)V2->getValue();
613 return ConstantFP::get(*Ty, R);
616 static Constant *Mul(const ConstantFP *V1, const ConstantFP *V2) {
617 BuiltinType R = (BuiltinType)V1->getValue() * (BuiltinType)V2->getValue();
618 return ConstantFP::get(*Ty, R);
621 static Constant *LessThan(const ConstantFP *V1, const ConstantFP *V2) {
622 bool R = (BuiltinType)V1->getValue() < (BuiltinType)V2->getValue();
623 return ConstantBool::get(R);
626 static Constant *EqualTo(const ConstantFP *V1, const ConstantFP *V2) {
627 bool R = (BuiltinType)V1->getValue() == (BuiltinType)V2->getValue();
628 return ConstantBool::get(R);
631 static Constant *CastToPointer(const ConstantFP *V,
632 const PointerType *PTy) {
633 if (V->isNullValue()) // Is it a FP or Integral null value?
634 return ConstantPointerNull::get(PTy);
635 return 0; // Can't const prop other types of pointers
638 // Casting operators. ick
639 #define DEF_CAST(TYPE, CLASS, CTYPE) \
640 static Constant *CastTo##TYPE (const ConstantFP *V) { \
641 return CLASS::get(Type::TYPE##Ty, (CTYPE)(BuiltinType)V->getValue()); \
644 DEF_CAST(Bool , ConstantBool, bool)
645 DEF_CAST(SByte , ConstantInt, signed char)
646 DEF_CAST(UByte , ConstantInt, unsigned char)
647 DEF_CAST(Short , ConstantInt, signed short)
648 DEF_CAST(UShort, ConstantInt, unsigned short)
649 DEF_CAST(Int , ConstantInt, signed int)
650 DEF_CAST(UInt , ConstantInt, unsigned int)
651 DEF_CAST(Long , ConstantInt, int64_t)
652 DEF_CAST(ULong , ConstantInt, uint64_t)
653 DEF_CAST(Float , ConstantFP , float)
654 DEF_CAST(Double, ConstantFP , double)
657 static Constant *FRem(const ConstantFP *V1, const ConstantFP *V2) {
658 if (V2->isNullValue()) return 0;
659 BuiltinType Result = std::fmod((BuiltinType)V1->getValue(),
660 (BuiltinType)V2->getValue());
661 return ConstantFP::get(*Ty, Result);
663 static Constant *FDiv(const ConstantFP *V1, const ConstantFP *V2) {
664 BuiltinType inf = std::numeric_limits<BuiltinType>::infinity();
665 if (V2->isExactlyValue(0.0)) return ConstantFP::get(*Ty, inf);
666 if (V2->isExactlyValue(-0.0)) return ConstantFP::get(*Ty, -inf);
667 BuiltinType R = (BuiltinType)V1->getValue() / (BuiltinType)V2->getValue();
668 return ConstantFP::get(*Ty, R);
671 } // end anonymous namespace
673 static ManagedStatic<EmptyRules> EmptyR;
674 static ManagedStatic<BoolRules> BoolR;
675 static ManagedStatic<NullPointerRules> NullPointerR;
676 static ManagedStatic<ConstantPackedRules> ConstantPackedR;
677 static ManagedStatic<GeneralPackedRules> GeneralPackedR;
678 static ManagedStatic<DirectIntRules<signed char , &Type::SByteTy> > SByteR;
679 static ManagedStatic<DirectIntRules<unsigned char , &Type::UByteTy> > UByteR;
680 static ManagedStatic<DirectIntRules<signed short , &Type::ShortTy> > ShortR;
681 static ManagedStatic<DirectIntRules<unsigned short, &Type::UShortTy> > UShortR;
682 static ManagedStatic<DirectIntRules<signed int , &Type::IntTy> > IntR;
683 static ManagedStatic<DirectIntRules<unsigned int , &Type::UIntTy> > UIntR;
684 static ManagedStatic<DirectIntRules<int64_t , &Type::LongTy> > LongR;
685 static ManagedStatic<DirectIntRules<uint64_t , &Type::ULongTy> > ULongR;
686 static ManagedStatic<DirectFPRules <float , &Type::FloatTy> > FloatR;
687 static ManagedStatic<DirectFPRules <double , &Type::DoubleTy> > DoubleR;
689 /// ConstRules::get - This method returns the constant rules implementation that
690 /// implements the semantics of the two specified constants.
691 ConstRules &ConstRules::get(const Constant *V1, const Constant *V2) {
692 if (isa<ConstantExpr>(V1) || isa<ConstantExpr>(V2) ||
693 isa<GlobalValue>(V1) || isa<GlobalValue>(V2) ||
694 isa<UndefValue>(V1) || isa<UndefValue>(V2))
697 switch (V1->getType()->getTypeID()) {
698 default: assert(0 && "Unknown value type for constant folding!");
699 case Type::BoolTyID: return *BoolR;
700 case Type::PointerTyID: return *NullPointerR;
701 case Type::SByteTyID: return *SByteR;
702 case Type::UByteTyID: return *UByteR;
703 case Type::ShortTyID: return *ShortR;
704 case Type::UShortTyID: return *UShortR;
705 case Type::IntTyID: return *IntR;
706 case Type::UIntTyID: return *UIntR;
707 case Type::LongTyID: return *LongR;
708 case Type::ULongTyID: return *ULongR;
709 case Type::FloatTyID: return *FloatR;
710 case Type::DoubleTyID: return *DoubleR;
711 case Type::PackedTyID:
712 if (isa<ConstantPacked>(V1) && isa<ConstantPacked>(V2))
713 return *ConstantPackedR;
714 return *GeneralPackedR; // Constant folding rules for ConstantAggregateZero.
719 //===----------------------------------------------------------------------===//
720 // ConstantFold*Instruction Implementations
721 //===----------------------------------------------------------------------===//
723 // These methods contain the special case hackery required to symbolically
724 // evaluate some constant expression cases, and use the ConstantRules class to
725 // evaluate normal constants.
727 static unsigned getSize(const Type *Ty) {
728 unsigned S = Ty->getPrimitiveSize();
729 return S ? S : 8; // Treat pointers at 8 bytes
732 /// CastConstantPacked - Convert the specified ConstantPacked node to the
733 /// specified packed type. At this point, we know that the elements of the
734 /// input packed constant are all simple integer or FP values.
735 static Constant *CastConstantPacked(ConstantPacked *CP,
736 const PackedType *DstTy) {
737 unsigned SrcNumElts = CP->getType()->getNumElements();
738 unsigned DstNumElts = DstTy->getNumElements();
739 const Type *SrcEltTy = CP->getType()->getElementType();
740 const Type *DstEltTy = DstTy->getElementType();
742 // If both vectors have the same number of elements (thus, the elements
743 // are the same size), perform the conversion now.
744 if (SrcNumElts == DstNumElts) {
745 std::vector<Constant*> Result;
747 // If the src and dest elements are both integers, just cast each one
748 // which will do the appropriate bit-convert.
749 if (SrcEltTy->isIntegral() && DstEltTy->isIntegral()) {
750 for (unsigned i = 0; i != SrcNumElts; ++i)
751 Result.push_back(ConstantExpr::getCast(CP->getOperand(i),
753 return ConstantPacked::get(Result);
756 if (SrcEltTy->isIntegral()) {
757 // Otherwise, this is an int-to-fp cast.
758 assert(DstEltTy->isFloatingPoint());
759 if (DstEltTy->getTypeID() == Type::DoubleTyID) {
760 for (unsigned i = 0; i != SrcNumElts; ++i) {
762 BitsToDouble(cast<ConstantInt>(CP->getOperand(i))->getZExtValue());
763 Result.push_back(ConstantFP::get(Type::DoubleTy, V));
765 return ConstantPacked::get(Result);
767 assert(DstEltTy == Type::FloatTy && "Unknown fp type!");
768 for (unsigned i = 0; i != SrcNumElts; ++i) {
770 BitsToFloat(cast<ConstantInt>(CP->getOperand(i))->getZExtValue());
771 Result.push_back(ConstantFP::get(Type::FloatTy, V));
773 return ConstantPacked::get(Result);
776 // Otherwise, this is an fp-to-int cast.
777 assert(SrcEltTy->isFloatingPoint() && DstEltTy->isIntegral());
779 if (SrcEltTy->getTypeID() == Type::DoubleTyID) {
780 for (unsigned i = 0; i != SrcNumElts; ++i) {
782 DoubleToBits(cast<ConstantFP>(CP->getOperand(i))->getValue());
783 Constant *C = ConstantInt::get(Type::ULongTy, V);
784 Result.push_back(ConstantExpr::getCast(C, DstEltTy));
786 return ConstantPacked::get(Result);
789 assert(SrcEltTy->getTypeID() == Type::FloatTyID);
790 for (unsigned i = 0; i != SrcNumElts; ++i) {
791 uint32_t V = FloatToBits(cast<ConstantFP>(CP->getOperand(i))->getValue());
792 Constant *C = ConstantInt::get(Type::UIntTy, V);
793 Result.push_back(ConstantExpr::getCast(C, DstEltTy));
795 return ConstantPacked::get(Result);
798 // Otherwise, this is a cast that changes element count and size. Handle
799 // casts which shrink the elements here.
801 // FIXME: We need to know endianness to do this!
807 Constant *llvm::ConstantFoldCastInstruction(const Constant *V,
808 const Type *DestTy) {
809 if (V->getType() == DestTy) return (Constant*)V;
811 // Cast of a global address to boolean is always true.
812 if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
813 if (DestTy == Type::BoolTy)
814 // FIXME: When we support 'external weak' references, we have to prevent
815 // this transformation from happening. This code will need to be updated
816 // to ignore external weak symbols when we support it.
817 return ConstantBool::getTrue();
818 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
819 if (CE->getOpcode() == Instruction::Cast) {
820 Constant *Op = const_cast<Constant*>(CE->getOperand(0));
821 // Try to not produce a cast of a cast, which is almost always redundant.
822 if (!Op->getType()->isFloatingPoint() &&
823 !CE->getType()->isFloatingPoint() &&
824 !DestTy->isFloatingPoint()) {
825 unsigned S1 = getSize(Op->getType()), S2 = getSize(CE->getType());
826 unsigned S3 = getSize(DestTy);
827 if (Op->getType() == DestTy && S3 >= S2)
829 if (S1 >= S2 && S2 >= S3)
830 return ConstantExpr::getCast(Op, DestTy);
831 if (S1 <= S2 && S2 >= S3 && S1 <= S3)
832 return ConstantExpr::getCast(Op, DestTy);
834 } else if (CE->getOpcode() == Instruction::GetElementPtr) {
835 // If all of the indexes in the GEP are null values, there is no pointer
836 // adjustment going on. We might as well cast the source pointer.
837 bool isAllNull = true;
838 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
839 if (!CE->getOperand(i)->isNullValue()) {
844 return ConstantExpr::getCast(CE->getOperand(0), DestTy);
846 } else if (isa<UndefValue>(V)) {
847 return UndefValue::get(DestTy);
850 // Check to see if we are casting an pointer to an aggregate to a pointer to
851 // the first element. If so, return the appropriate GEP instruction.
852 if (const PointerType *PTy = dyn_cast<PointerType>(V->getType()))
853 if (const PointerType *DPTy = dyn_cast<PointerType>(DestTy)) {
854 std::vector<Value*> IdxList;
855 IdxList.push_back(Constant::getNullValue(Type::IntTy));
856 const Type *ElTy = PTy->getElementType();
857 while (ElTy != DPTy->getElementType()) {
858 if (const StructType *STy = dyn_cast<StructType>(ElTy)) {
859 if (STy->getNumElements() == 0) break;
860 ElTy = STy->getElementType(0);
861 IdxList.push_back(Constant::getNullValue(Type::UIntTy));
862 } else if (const SequentialType *STy = dyn_cast<SequentialType>(ElTy)) {
863 if (isa<PointerType>(ElTy)) break; // Can't index into pointers!
864 ElTy = STy->getElementType();
865 IdxList.push_back(IdxList[0]);
871 if (ElTy == DPTy->getElementType())
872 return ConstantExpr::getGetElementPtr(const_cast<Constant*>(V),IdxList);
875 // Handle casts from one packed constant to another. We know that the src and
876 // dest type have the same size.
877 if (const PackedType *DestPTy = dyn_cast<PackedType>(DestTy)) {
878 if (const PackedType *SrcTy = dyn_cast<PackedType>(V->getType())) {
879 assert(DestPTy->getElementType()->getPrimitiveSizeInBits() *
880 DestPTy->getNumElements() ==
881 SrcTy->getElementType()->getPrimitiveSizeInBits() *
882 SrcTy->getNumElements() && "Not cast between same sized vectors!");
883 if (isa<ConstantAggregateZero>(V))
884 return Constant::getNullValue(DestTy);
885 if (isa<UndefValue>(V))
886 return UndefValue::get(DestTy);
887 if (const ConstantPacked *CP = dyn_cast<ConstantPacked>(V)) {
888 // This is a cast from a ConstantPacked of one type to a ConstantPacked
889 // of another type. Check to see if all elements of the input are
891 bool AllSimpleConstants = true;
892 for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) {
893 if (!isa<ConstantInt>(CP->getOperand(i)) &&
894 !isa<ConstantFP>(CP->getOperand(i))) {
895 AllSimpleConstants = false;
900 // If all of the elements are simple constants, we can fold this.
901 if (AllSimpleConstants)
902 return CastConstantPacked(const_cast<ConstantPacked*>(CP), DestPTy);
907 ConstRules &Rules = ConstRules::get(V, V);
909 switch (DestTy->getTypeID()) {
910 case Type::BoolTyID: return Rules.castToBool(V);
911 case Type::UByteTyID: return Rules.castToUByte(V);
912 case Type::SByteTyID: return Rules.castToSByte(V);
913 case Type::UShortTyID: return Rules.castToUShort(V);
914 case Type::ShortTyID: return Rules.castToShort(V);
915 case Type::UIntTyID: return Rules.castToUInt(V);
916 case Type::IntTyID: return Rules.castToInt(V);
917 case Type::ULongTyID: return Rules.castToULong(V);
918 case Type::LongTyID: return Rules.castToLong(V);
919 case Type::FloatTyID: return Rules.castToFloat(V);
920 case Type::DoubleTyID: return Rules.castToDouble(V);
921 case Type::PointerTyID:
922 return Rules.castToPointer(V, cast<PointerType>(DestTy));
927 Constant *llvm::ConstantFoldSelectInstruction(const Constant *Cond,
929 const Constant *V2) {
930 if (const ConstantBool *CB = dyn_cast<ConstantBool>(Cond))
931 return const_cast<Constant*>(CB->getValue() ? V1 : V2);
933 if (isa<UndefValue>(V1)) return const_cast<Constant*>(V2);
934 if (isa<UndefValue>(V2)) return const_cast<Constant*>(V1);
935 if (isa<UndefValue>(Cond)) return const_cast<Constant*>(V1);
936 if (V1 == V2) return const_cast<Constant*>(V1);
940 Constant *llvm::ConstantFoldExtractElementInstruction(const Constant *Val,
941 const Constant *Idx) {
942 if (isa<UndefValue>(Val)) // ee(undef, x) -> undef
943 return UndefValue::get(cast<PackedType>(Val->getType())->getElementType());
944 if (Val->isNullValue()) // ee(zero, x) -> zero
945 return Constant::getNullValue(
946 cast<PackedType>(Val->getType())->getElementType());
948 if (const ConstantPacked *CVal = dyn_cast<ConstantPacked>(Val)) {
949 if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Idx)) {
950 return const_cast<Constant*>(CVal->getOperand(CIdx->getZExtValue()));
951 } else if (isa<UndefValue>(Idx)) {
952 // ee({w,x,y,z}, undef) -> w (an arbitrary value).
953 return const_cast<Constant*>(CVal->getOperand(0));
959 Constant *llvm::ConstantFoldInsertElementInstruction(const Constant *Val,
961 const Constant *Idx) {
962 const ConstantInt *CIdx = dyn_cast<ConstantInt>(Idx);
964 uint64_t idxVal = CIdx->getZExtValue();
965 if (const UndefValue *UVal = dyn_cast<UndefValue>(Val)) {
966 // Insertion of scalar constant into packed undef
967 // Optimize away insertion of undef
968 if (isa<UndefValue>(Elt))
969 return const_cast<Constant*>(Val);
970 // Otherwise break the aggregate undef into multiple undefs and do
973 cast<PackedType>(Val->getType())->getNumElements();
974 std::vector<Constant*> Ops;
976 for (unsigned i = 0; i < numOps; ++i) {
978 (i == idxVal) ? Elt : UndefValue::get(Elt->getType());
979 Ops.push_back(const_cast<Constant*>(Op));
981 return ConstantPacked::get(Ops);
983 if (const ConstantAggregateZero *CVal =
984 dyn_cast<ConstantAggregateZero>(Val)) {
985 // Insertion of scalar constant into packed aggregate zero
986 // Optimize away insertion of zero
987 if (Elt->isNullValue())
988 return const_cast<Constant*>(Val);
989 // Otherwise break the aggregate zero into multiple zeros and do
992 cast<PackedType>(Val->getType())->getNumElements();
993 std::vector<Constant*> Ops;
995 for (unsigned i = 0; i < numOps; ++i) {
997 (i == idxVal) ? Elt : Constant::getNullValue(Elt->getType());
998 Ops.push_back(const_cast<Constant*>(Op));
1000 return ConstantPacked::get(Ops);
1002 if (const ConstantPacked *CVal = dyn_cast<ConstantPacked>(Val)) {
1003 // Insertion of scalar constant into packed constant
1004 std::vector<Constant*> Ops;
1005 Ops.reserve(CVal->getNumOperands());
1006 for (unsigned i = 0; i < CVal->getNumOperands(); ++i) {
1007 const Constant *Op =
1008 (i == idxVal) ? Elt : cast<Constant>(CVal->getOperand(i));
1009 Ops.push_back(const_cast<Constant*>(Op));
1011 return ConstantPacked::get(Ops);
1016 Constant *llvm::ConstantFoldShuffleVectorInstruction(const Constant *V1,
1018 const Constant *Mask) {
1024 /// isZeroSizedType - This type is zero sized if its an array or structure of
1025 /// zero sized types. The only leaf zero sized type is an empty structure.
1026 static bool isMaybeZeroSizedType(const Type *Ty) {
1027 if (isa<OpaqueType>(Ty)) return true; // Can't say.
1028 if (const StructType *STy = dyn_cast<StructType>(Ty)) {
1030 // If all of elements have zero size, this does too.
1031 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1032 if (!isMaybeZeroSizedType(STy->getElementType(i))) return false;
1035 } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
1036 return isMaybeZeroSizedType(ATy->getElementType());
1041 /// IdxCompare - Compare the two constants as though they were getelementptr
1042 /// indices. This allows coersion of the types to be the same thing.
1044 /// If the two constants are the "same" (after coersion), return 0. If the
1045 /// first is less than the second, return -1, if the second is less than the
1046 /// first, return 1. If the constants are not integral, return -2.
1048 static int IdxCompare(Constant *C1, Constant *C2, const Type *ElTy) {
1049 if (C1 == C2) return 0;
1051 // Ok, we found a different index. Are either of the operands
1052 // ConstantExprs? If so, we can't do anything with them.
1053 if (!isa<ConstantInt>(C1) || !isa<ConstantInt>(C2))
1054 return -2; // don't know!
1056 // Ok, we have two differing integer indices. Sign extend them to be the same
1057 // type. Long is always big enough, so we use it.
1058 C1 = ConstantExpr::getSignExtend(C1, Type::LongTy);
1059 C2 = ConstantExpr::getSignExtend(C2, Type::LongTy);
1060 if (C1 == C2) return 0; // Are they just differing types?
1062 // If the type being indexed over is really just a zero sized type, there is
1063 // no pointer difference being made here.
1064 if (isMaybeZeroSizedType(ElTy))
1065 return -2; // dunno.
1067 // If they are really different, now that they are the same type, then we
1068 // found a difference!
1069 if (cast<ConstantInt>(C1)->getSExtValue() <
1070 cast<ConstantInt>(C2)->getSExtValue())
1076 /// evaluateRelation - This function determines if there is anything we can
1077 /// decide about the two constants provided. This doesn't need to handle simple
1078 /// things like integer comparisons, but should instead handle ConstantExprs
1079 /// and GlobalValuess. If we can determine that the two constants have a
1080 /// particular relation to each other, we should return the corresponding SetCC
1081 /// code, otherwise return Instruction::BinaryOpsEnd.
1083 /// To simplify this code we canonicalize the relation so that the first
1084 /// operand is always the most "complex" of the two. We consider simple
1085 /// constants (like ConstantInt) to be the simplest, followed by
1086 /// GlobalValues, followed by ConstantExpr's (the most complex).
1088 static Instruction::BinaryOps evaluateRelation(Constant *V1, Constant *V2) {
1089 assert(V1->getType() == V2->getType() &&
1090 "Cannot compare different types of values!");
1091 if (V1 == V2) return Instruction::SetEQ;
1093 if (!isa<ConstantExpr>(V1) && !isa<GlobalValue>(V1)) {
1094 if (!isa<GlobalValue>(V2) && !isa<ConstantExpr>(V2)) {
1095 // We distilled this down to a simple case, use the standard constant
1097 ConstantBool *R = dyn_cast<ConstantBool>(ConstantExpr::getSetEQ(V1, V2));
1098 if (R && R->getValue()) return Instruction::SetEQ;
1099 R = dyn_cast<ConstantBool>(ConstantExpr::getSetLT(V1, V2));
1100 if (R && R->getValue()) return Instruction::SetLT;
1101 R = dyn_cast<ConstantBool>(ConstantExpr::getSetGT(V1, V2));
1102 if (R && R->getValue()) return Instruction::SetGT;
1104 // If we couldn't figure it out, bail.
1105 return Instruction::BinaryOpsEnd;
1108 // If the first operand is simple, swap operands.
1109 Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1);
1110 if (SwappedRelation != Instruction::BinaryOpsEnd)
1111 return SetCondInst::getSwappedCondition(SwappedRelation);
1113 } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(V1)) {
1114 if (isa<ConstantExpr>(V2)) { // Swap as necessary.
1115 Instruction::BinaryOps SwappedRelation = evaluateRelation(V2, V1);
1116 if (SwappedRelation != Instruction::BinaryOpsEnd)
1117 return SetCondInst::getSwappedCondition(SwappedRelation);
1119 return Instruction::BinaryOpsEnd;
1122 // Now we know that the RHS is a GlobalValue or simple constant,
1123 // which (since the types must match) means that it's a ConstantPointerNull.
1124 if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) {
1125 assert(CPR1 != CPR2 &&
1126 "GVs for the same value exist at different addresses??");
1127 // FIXME: If both globals are external weak, they might both be null!
1128 return Instruction::SetNE;
1130 assert(isa<ConstantPointerNull>(V2) && "Canonicalization guarantee!");
1131 // Global can never be null. FIXME: if we implement external weak
1132 // linkage, this is not necessarily true!
1133 return Instruction::SetNE;
1137 // Ok, the LHS is known to be a constantexpr. The RHS can be any of a
1138 // constantexpr, a CPR, or a simple constant.
1139 ConstantExpr *CE1 = cast<ConstantExpr>(V1);
1140 Constant *CE1Op0 = CE1->getOperand(0);
1142 switch (CE1->getOpcode()) {
1143 case Instruction::Cast:
1144 // If the cast is not actually changing bits, and the second operand is a
1145 // null pointer, do the comparison with the pre-casted value.
1146 if (V2->isNullValue() &&
1147 (isa<PointerType>(CE1->getType()) || CE1->getType()->isIntegral()))
1148 return evaluateRelation(CE1Op0,
1149 Constant::getNullValue(CE1Op0->getType()));
1151 // If the dest type is a pointer type, and the RHS is a constantexpr cast
1152 // from the same type as the src of the LHS, evaluate the inputs. This is
1153 // important for things like "seteq (cast 4 to int*), (cast 5 to int*)",
1154 // which happens a lot in compilers with tagged integers.
1155 if (ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2))
1156 if (isa<PointerType>(CE1->getType()) &&
1157 CE2->getOpcode() == Instruction::Cast &&
1158 CE1->getOperand(0)->getType() == CE2->getOperand(0)->getType() &&
1159 CE1->getOperand(0)->getType()->isIntegral()) {
1160 return evaluateRelation(CE1->getOperand(0), CE2->getOperand(0));
1164 case Instruction::GetElementPtr:
1165 // Ok, since this is a getelementptr, we know that the constant has a
1166 // pointer type. Check the various cases.
1167 if (isa<ConstantPointerNull>(V2)) {
1168 // If we are comparing a GEP to a null pointer, check to see if the base
1169 // of the GEP equals the null pointer.
1170 if (isa<GlobalValue>(CE1Op0)) {
1171 // FIXME: this is not true when we have external weak references!
1172 // No offset can go from a global to a null pointer.
1173 return Instruction::SetGT;
1174 } else if (isa<ConstantPointerNull>(CE1Op0)) {
1175 // If we are indexing from a null pointer, check to see if we have any
1176 // non-zero indices.
1177 for (unsigned i = 1, e = CE1->getNumOperands(); i != e; ++i)
1178 if (!CE1->getOperand(i)->isNullValue())
1179 // Offsetting from null, must not be equal.
1180 return Instruction::SetGT;
1181 // Only zero indexes from null, must still be zero.
1182 return Instruction::SetEQ;
1184 // Otherwise, we can't really say if the first operand is null or not.
1185 } else if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) {
1186 if (isa<ConstantPointerNull>(CE1Op0)) {
1187 // FIXME: This is not true with external weak references.
1188 return Instruction::SetLT;
1189 } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(CE1Op0)) {
1191 // If this is a getelementptr of the same global, then it must be
1192 // different. Because the types must match, the getelementptr could
1193 // only have at most one index, and because we fold getelementptr's
1194 // with a single zero index, it must be nonzero.
1195 assert(CE1->getNumOperands() == 2 &&
1196 !CE1->getOperand(1)->isNullValue() &&
1197 "Suprising getelementptr!");
1198 return Instruction::SetGT;
1200 // If they are different globals, we don't know what the value is,
1201 // but they can't be equal.
1202 return Instruction::SetNE;
1206 const ConstantExpr *CE2 = cast<ConstantExpr>(V2);
1207 const Constant *CE2Op0 = CE2->getOperand(0);
1209 // There are MANY other foldings that we could perform here. They will
1210 // probably be added on demand, as they seem needed.
1211 switch (CE2->getOpcode()) {
1213 case Instruction::GetElementPtr:
1214 // By far the most common case to handle is when the base pointers are
1215 // obviously to the same or different globals.
1216 if (isa<GlobalValue>(CE1Op0) && isa<GlobalValue>(CE2Op0)) {
1217 if (CE1Op0 != CE2Op0) // Don't know relative ordering, but not equal
1218 return Instruction::SetNE;
1219 // Ok, we know that both getelementptr instructions are based on the
1220 // same global. From this, we can precisely determine the relative
1221 // ordering of the resultant pointers.
1224 // Compare all of the operands the GEP's have in common.
1225 gep_type_iterator GTI = gep_type_begin(CE1);
1226 for (;i != CE1->getNumOperands() && i != CE2->getNumOperands();
1228 switch (IdxCompare(CE1->getOperand(i), CE2->getOperand(i),
1229 GTI.getIndexedType())) {
1230 case -1: return Instruction::SetLT;
1231 case 1: return Instruction::SetGT;
1232 case -2: return Instruction::BinaryOpsEnd;
1235 // Ok, we ran out of things they have in common. If any leftovers
1236 // are non-zero then we have a difference, otherwise we are equal.
1237 for (; i < CE1->getNumOperands(); ++i)
1238 if (!CE1->getOperand(i)->isNullValue())
1239 if (isa<ConstantIntegral>(CE1->getOperand(i)))
1240 return Instruction::SetGT;
1242 return Instruction::BinaryOpsEnd; // Might be equal.
1244 for (; i < CE2->getNumOperands(); ++i)
1245 if (!CE2->getOperand(i)->isNullValue())
1246 if (isa<ConstantIntegral>(CE2->getOperand(i)))
1247 return Instruction::SetLT;
1249 return Instruction::BinaryOpsEnd; // Might be equal.
1250 return Instruction::SetEQ;
1260 return Instruction::BinaryOpsEnd;
1263 Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode,
1265 const Constant *V2) {
1269 case Instruction::Add: C = ConstRules::get(V1, V2).add(V1, V2); break;
1270 case Instruction::Sub: C = ConstRules::get(V1, V2).sub(V1, V2); break;
1271 case Instruction::Mul: C = ConstRules::get(V1, V2).mul(V1, V2); break;
1272 case Instruction::UDiv: C = ConstRules::get(V1, V2).udiv(V1, V2); break;
1273 case Instruction::SDiv: C = ConstRules::get(V1, V2).sdiv(V1, V2); break;
1274 case Instruction::FDiv: C = ConstRules::get(V1, V2).fdiv(V1, V2); break;
1275 case Instruction::URem: C = ConstRules::get(V1, V2).urem(V1, V2); break;
1276 case Instruction::SRem: C = ConstRules::get(V1, V2).srem(V1, V2); break;
1277 case Instruction::FRem: C = ConstRules::get(V1, V2).frem(V1, V2); break;
1278 case Instruction::And: C = ConstRules::get(V1, V2).op_and(V1, V2); break;
1279 case Instruction::Or: C = ConstRules::get(V1, V2).op_or (V1, V2); break;
1280 case Instruction::Xor: C = ConstRules::get(V1, V2).op_xor(V1, V2); break;
1281 case Instruction::Shl: C = ConstRules::get(V1, V2).shl(V1, V2); break;
1282 case Instruction::Shr: C = ConstRules::get(V1, V2).shr(V1, V2); break;
1283 case Instruction::SetEQ: C = ConstRules::get(V1, V2).equalto(V1, V2); break;
1284 case Instruction::SetLT: C = ConstRules::get(V1, V2).lessthan(V1, V2);break;
1285 case Instruction::SetGT: C = ConstRules::get(V1, V2).lessthan(V2, V1);break;
1286 case Instruction::SetNE: // V1 != V2 === !(V1 == V2)
1287 C = ConstRules::get(V1, V2).equalto(V1, V2);
1288 if (C) return ConstantExpr::getNot(C);
1290 case Instruction::SetLE: // V1 <= V2 === !(V2 < V1)
1291 C = ConstRules::get(V1, V2).lessthan(V2, V1);
1292 if (C) return ConstantExpr::getNot(C);
1294 case Instruction::SetGE: // V1 >= V2 === !(V1 < V2)
1295 C = ConstRules::get(V1, V2).lessthan(V1, V2);
1296 if (C) return ConstantExpr::getNot(C);
1300 // If we successfully folded the expression, return it now.
1303 if (SetCondInst::isComparison(Opcode)) {
1304 if (isa<UndefValue>(V1) || isa<UndefValue>(V2))
1305 return UndefValue::get(Type::BoolTy);
1306 switch (evaluateRelation(const_cast<Constant*>(V1),
1307 const_cast<Constant*>(V2))) {
1308 default: assert(0 && "Unknown relational!");
1309 case Instruction::BinaryOpsEnd:
1310 break; // Couldn't determine anything about these constants.
1311 case Instruction::SetEQ: // We know the constants are equal!
1312 // If we know the constants are equal, we can decide the result of this
1313 // computation precisely.
1314 return ConstantBool::get(Opcode == Instruction::SetEQ ||
1315 Opcode == Instruction::SetLE ||
1316 Opcode == Instruction::SetGE);
1317 case Instruction::SetLT:
1318 // If we know that V1 < V2, we can decide the result of this computation
1320 return ConstantBool::get(Opcode == Instruction::SetLT ||
1321 Opcode == Instruction::SetNE ||
1322 Opcode == Instruction::SetLE);
1323 case Instruction::SetGT:
1324 // If we know that V1 > V2, we can decide the result of this computation
1326 return ConstantBool::get(Opcode == Instruction::SetGT ||
1327 Opcode == Instruction::SetNE ||
1328 Opcode == Instruction::SetGE);
1329 case Instruction::SetLE:
1330 // If we know that V1 <= V2, we can only partially decide this relation.
1331 if (Opcode == Instruction::SetGT) return ConstantBool::getFalse();
1332 if (Opcode == Instruction::SetLT) return ConstantBool::getTrue();
1335 case Instruction::SetGE:
1336 // If we know that V1 >= V2, we can only partially decide this relation.
1337 if (Opcode == Instruction::SetLT) return ConstantBool::getFalse();
1338 if (Opcode == Instruction::SetGT) return ConstantBool::getTrue();
1341 case Instruction::SetNE:
1342 // If we know that V1 != V2, we can only partially decide this relation.
1343 if (Opcode == Instruction::SetEQ) return ConstantBool::getFalse();
1344 if (Opcode == Instruction::SetNE) return ConstantBool::getTrue();
1349 if (isa<UndefValue>(V1) || isa<UndefValue>(V2)) {
1351 case Instruction::Add:
1352 case Instruction::Sub:
1353 case Instruction::Xor:
1354 return UndefValue::get(V1->getType());
1356 case Instruction::Mul:
1357 case Instruction::And:
1358 return Constant::getNullValue(V1->getType());
1359 case Instruction::UDiv:
1360 case Instruction::SDiv:
1361 case Instruction::FDiv:
1362 case Instruction::URem:
1363 case Instruction::SRem:
1364 case Instruction::FRem:
1365 if (!isa<UndefValue>(V2)) // undef / X -> 0
1366 return Constant::getNullValue(V1->getType());
1367 return const_cast<Constant*>(V2); // X / undef -> undef
1368 case Instruction::Or: // X | undef -> -1
1369 return ConstantInt::getAllOnesValue(V1->getType());
1370 case Instruction::Shr:
1371 if (!isa<UndefValue>(V2)) {
1372 if (V1->getType()->isSigned())
1373 return const_cast<Constant*>(V1); // undef >>s X -> undef
1375 } else if (isa<UndefValue>(V1)) {
1376 return const_cast<Constant*>(V1); // undef >> undef -> undef
1378 if (V1->getType()->isSigned())
1379 return const_cast<Constant*>(V1); // X >>s undef -> X
1381 return Constant::getNullValue(V1->getType());// X >>u undef -> 0
1383 case Instruction::Shl:
1384 // undef << X -> 0 X << undef -> 0
1385 return Constant::getNullValue(V1->getType());
1389 if (const ConstantExpr *CE1 = dyn_cast<ConstantExpr>(V1)) {
1390 if (const ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2)) {
1391 // There are many possible foldings we could do here. We should probably
1392 // at least fold add of a pointer with an integer into the appropriate
1393 // getelementptr. This will improve alias analysis a bit.
1395 // Just implement a couple of simple identities.
1397 case Instruction::Add:
1398 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X + 0 == X
1400 case Instruction::Sub:
1401 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X - 0 == X
1403 case Instruction::Mul:
1404 if (V2->isNullValue()) return const_cast<Constant*>(V2); // X * 0 == 0
1405 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1406 if (CI->getZExtValue() == 1)
1407 return const_cast<Constant*>(V1); // X * 1 == X
1409 case Instruction::UDiv:
1410 case Instruction::SDiv:
1411 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1412 if (CI->getZExtValue() == 1)
1413 return const_cast<Constant*>(V1); // X / 1 == X
1415 case Instruction::URem:
1416 case Instruction::SRem:
1417 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1418 if (CI->getZExtValue() == 1)
1419 return Constant::getNullValue(CI->getType()); // X % 1 == 0
1421 case Instruction::And:
1422 if (cast<ConstantIntegral>(V2)->isAllOnesValue())
1423 return const_cast<Constant*>(V1); // X & -1 == X
1424 if (V2->isNullValue()) return const_cast<Constant*>(V2); // X & 0 == 0
1425 if (CE1->getOpcode() == Instruction::Cast &&
1426 isa<GlobalValue>(CE1->getOperand(0))) {
1427 GlobalValue *CPR = cast<GlobalValue>(CE1->getOperand(0));
1429 // Functions are at least 4-byte aligned. If and'ing the address of a
1430 // function with a constant < 4, fold it to zero.
1431 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V2))
1432 if (CI->getZExtValue() < 4 && isa<Function>(CPR))
1433 return Constant::getNullValue(CI->getType());
1436 case Instruction::Or:
1437 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X | 0 == X
1438 if (cast<ConstantIntegral>(V2)->isAllOnesValue())
1439 return const_cast<Constant*>(V2); // X | -1 == -1
1441 case Instruction::Xor:
1442 if (V2->isNullValue()) return const_cast<Constant*>(V1); // X ^ 0 == X
1447 } else if (const ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2)) {
1448 // If V2 is a constant expr and V1 isn't, flop them around and fold the
1449 // other way if possible.
1451 case Instruction::Add:
1452 case Instruction::Mul:
1453 case Instruction::And:
1454 case Instruction::Or:
1455 case Instruction::Xor:
1456 case Instruction::SetEQ:
1457 case Instruction::SetNE:
1458 // No change of opcode required.
1459 return ConstantFoldBinaryInstruction(Opcode, V2, V1);
1461 case Instruction::SetLT:
1462 case Instruction::SetGT:
1463 case Instruction::SetLE:
1464 case Instruction::SetGE:
1465 // Change the opcode as necessary to swap the operands.
1466 Opcode = SetCondInst::getSwappedCondition((Instruction::BinaryOps)Opcode);
1467 return ConstantFoldBinaryInstruction(Opcode, V2, V1);
1469 case Instruction::Shl:
1470 case Instruction::Shr:
1471 case Instruction::Sub:
1472 case Instruction::SDiv:
1473 case Instruction::UDiv:
1474 case Instruction::FDiv:
1475 case Instruction::URem:
1476 case Instruction::SRem:
1477 case Instruction::FRem:
1478 default: // These instructions cannot be flopped around.
1485 Constant *llvm::ConstantFoldGetElementPtr(const Constant *C,
1486 const std::vector<Value*> &IdxList) {
1487 if (IdxList.size() == 0 ||
1488 (IdxList.size() == 1 && cast<Constant>(IdxList[0])->isNullValue()))
1489 return const_cast<Constant*>(C);
1491 if (isa<UndefValue>(C)) {
1492 const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList,
1494 assert(Ty != 0 && "Invalid indices for GEP!");
1495 return UndefValue::get(PointerType::get(Ty));
1498 Constant *Idx0 = cast<Constant>(IdxList[0]);
1499 if (C->isNullValue()) {
1501 for (unsigned i = 0, e = IdxList.size(); i != e; ++i)
1502 if (!cast<Constant>(IdxList[i])->isNullValue()) {
1507 const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList,
1509 assert(Ty != 0 && "Invalid indices for GEP!");
1510 return ConstantPointerNull::get(PointerType::get(Ty));
1513 if (IdxList.size() == 1) {
1514 const Type *ElTy = cast<PointerType>(C->getType())->getElementType();
1515 if (uint32_t ElSize = ElTy->getPrimitiveSize()) {
1516 // gep null, C is equal to C*sizeof(nullty). If nullty is a known llvm
1517 // type, we can statically fold this.
1518 Constant *R = ConstantInt::get(Type::UIntTy, ElSize);
1519 R = ConstantExpr::getCast(R, Idx0->getType());
1520 R = ConstantExpr::getMul(R, Idx0);
1521 return ConstantExpr::getCast(R, C->getType());
1526 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(const_cast<Constant*>(C))) {
1527 // Combine Indices - If the source pointer to this getelementptr instruction
1528 // is a getelementptr instruction, combine the indices of the two
1529 // getelementptr instructions into a single instruction.
1531 if (CE->getOpcode() == Instruction::GetElementPtr) {
1532 const Type *LastTy = 0;
1533 for (gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
1537 if ((LastTy && isa<ArrayType>(LastTy)) || Idx0->isNullValue()) {
1538 std::vector<Value*> NewIndices;
1539 NewIndices.reserve(IdxList.size() + CE->getNumOperands());
1540 for (unsigned i = 1, e = CE->getNumOperands()-1; i != e; ++i)
1541 NewIndices.push_back(CE->getOperand(i));
1543 // Add the last index of the source with the first index of the new GEP.
1544 // Make sure to handle the case when they are actually different types.
1545 Constant *Combined = CE->getOperand(CE->getNumOperands()-1);
1546 // Otherwise it must be an array.
1547 if (!Idx0->isNullValue()) {
1548 const Type *IdxTy = Combined->getType();
1549 if (IdxTy != Idx0->getType()) IdxTy = Type::LongTy;
1551 ConstantExpr::get(Instruction::Add,
1552 ConstantExpr::getCast(Idx0, IdxTy),
1553 ConstantExpr::getCast(Combined, IdxTy));
1556 NewIndices.push_back(Combined);
1557 NewIndices.insert(NewIndices.end(), IdxList.begin()+1, IdxList.end());
1558 return ConstantExpr::getGetElementPtr(CE->getOperand(0), NewIndices);
1562 // Implement folding of:
1563 // int* getelementptr ([2 x int]* cast ([3 x int]* %X to [2 x int]*),
1565 // To: int* getelementptr ([3 x int]* %X, long 0, long 0)
1567 if (CE->getOpcode() == Instruction::Cast && IdxList.size() > 1 &&
1568 Idx0->isNullValue())
1569 if (const PointerType *SPT =
1570 dyn_cast<PointerType>(CE->getOperand(0)->getType()))
1571 if (const ArrayType *SAT = dyn_cast<ArrayType>(SPT->getElementType()))
1572 if (const ArrayType *CAT =
1573 dyn_cast<ArrayType>(cast<PointerType>(C->getType())->getElementType()))
1574 if (CAT->getElementType() == SAT->getElementType())
1575 return ConstantExpr::getGetElementPtr(
1576 (Constant*)CE->getOperand(0), IdxList);