ConstantFolding.cpp revision 9ee17208115482441953127615231c59a2f4d052
1//===-- ConstantFolding.cpp - Fold instructions into constants ------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines routines for folding instructions into constants.
11//
12// Also, to supplement the basic VMCore ConstantExpr simplifications,
13// this file defines some additional folding routines that can make use of
14// TargetData information. These functions cannot go in VMCore due to library
15// dependency issues.
16//
17//===----------------------------------------------------------------------===//
18
19#include "llvm/Analysis/ConstantFolding.h"
20#include "llvm/Constants.h"
21#include "llvm/DerivedTypes.h"
22#include "llvm/Function.h"
23#include "llvm/GlobalVariable.h"
24#include "llvm/Instructions.h"
25#include "llvm/Intrinsics.h"
26#include "llvm/Analysis/ValueTracking.h"
27#include "llvm/Target/TargetData.h"
28#include "llvm/ADT/SmallVector.h"
29#include "llvm/ADT/StringMap.h"
30#include "llvm/Support/ErrorHandling.h"
31#include "llvm/Support/GetElementPtrTypeIterator.h"
32#include "llvm/Support/MathExtras.h"
33#include <cerrno>
34#include <cmath>
35using namespace llvm;
36
37//===----------------------------------------------------------------------===//
38// Constant Folding internal helper functions
39//===----------------------------------------------------------------------===//
40
41/// FoldBitCast - Constant fold bitcast, symbolically evaluating it with
42/// TargetData.  This always returns a non-null constant, but it may be a
43/// ConstantExpr if unfoldable.
44static Constant *FoldBitCast(Constant *C, const Type *DestTy,
45                             const TargetData &TD) {
46
47  // This only handles casts to vectors currently.
48  const VectorType *DestVTy = dyn_cast<VectorType>(DestTy);
49  if (DestVTy == 0)
50    return ConstantExpr::getBitCast(C, DestTy);
51
52  // If this is a scalar -> vector cast, convert the input into a <1 x scalar>
53  // vector so the code below can handle it uniformly.
54  if (isa<ConstantFP>(C) || isa<ConstantInt>(C)) {
55    Constant *Ops = C; // don't take the address of C!
56    return FoldBitCast(ConstantVector::get(&Ops, 1), DestTy, TD);
57  }
58
59  // If this is a bitcast from constant vector -> vector, fold it.
60  ConstantVector *CV = dyn_cast<ConstantVector>(C);
61  if (CV == 0)
62    return ConstantExpr::getBitCast(C, DestTy);
63
64  // If the element types match, VMCore can fold it.
65  unsigned NumDstElt = DestVTy->getNumElements();
66  unsigned NumSrcElt = CV->getNumOperands();
67  if (NumDstElt == NumSrcElt)
68    return ConstantExpr::getBitCast(C, DestTy);
69
70  const Type *SrcEltTy = CV->getType()->getElementType();
71  const Type *DstEltTy = DestVTy->getElementType();
72
73  // Otherwise, we're changing the number of elements in a vector, which
74  // requires endianness information to do the right thing.  For example,
75  //    bitcast (<2 x i64> <i64 0, i64 1> to <4 x i32>)
76  // folds to (little endian):
77  //    <4 x i32> <i32 0, i32 0, i32 1, i32 0>
78  // and to (big endian):
79  //    <4 x i32> <i32 0, i32 0, i32 0, i32 1>
80
81  // First thing is first.  We only want to think about integer here, so if
82  // we have something in FP form, recast it as integer.
83  if (DstEltTy->isFloatingPointTy()) {
84    // Fold to an vector of integers with same size as our FP type.
85    unsigned FPWidth = DstEltTy->getPrimitiveSizeInBits();
86    const Type *DestIVTy =
87      VectorType::get(IntegerType::get(C->getContext(), FPWidth), NumDstElt);
88    // Recursively handle this integer conversion, if possible.
89    C = FoldBitCast(C, DestIVTy, TD);
90    if (!C) return ConstantExpr::getBitCast(C, DestTy);
91
92    // Finally, VMCore can handle this now that #elts line up.
93    return ConstantExpr::getBitCast(C, DestTy);
94  }
95
96  // Okay, we know the destination is integer, if the input is FP, convert
97  // it to integer first.
98  if (SrcEltTy->isFloatingPointTy()) {
99    unsigned FPWidth = SrcEltTy->getPrimitiveSizeInBits();
100    const Type *SrcIVTy =
101      VectorType::get(IntegerType::get(C->getContext(), FPWidth), NumSrcElt);
102    // Ask VMCore to do the conversion now that #elts line up.
103    C = ConstantExpr::getBitCast(C, SrcIVTy);
104    CV = dyn_cast<ConstantVector>(C);
105    if (!CV)  // If VMCore wasn't able to fold it, bail out.
106      return C;
107  }
108
109  // Now we know that the input and output vectors are both integer vectors
110  // of the same size, and that their #elements is not the same.  Do the
111  // conversion here, which depends on whether the input or output has
112  // more elements.
113  bool isLittleEndian = TD.isLittleEndian();
114
115  SmallVector<Constant*, 32> Result;
116  if (NumDstElt < NumSrcElt) {
117    // Handle: bitcast (<4 x i32> <i32 0, i32 1, i32 2, i32 3> to <2 x i64>)
118    Constant *Zero = Constant::getNullValue(DstEltTy);
119    unsigned Ratio = NumSrcElt/NumDstElt;
120    unsigned SrcBitSize = SrcEltTy->getPrimitiveSizeInBits();
121    unsigned SrcElt = 0;
122    for (unsigned i = 0; i != NumDstElt; ++i) {
123      // Build each element of the result.
124      Constant *Elt = Zero;
125      unsigned ShiftAmt = isLittleEndian ? 0 : SrcBitSize*(Ratio-1);
126      for (unsigned j = 0; j != Ratio; ++j) {
127        Constant *Src = dyn_cast<ConstantInt>(CV->getOperand(SrcElt++));
128        if (!Src)  // Reject constantexpr elements.
129          return ConstantExpr::getBitCast(C, DestTy);
130
131        // Zero extend the element to the right size.
132        Src = ConstantExpr::getZExt(Src, Elt->getType());
133
134        // Shift it to the right place, depending on endianness.
135        Src = ConstantExpr::getShl(Src,
136                                   ConstantInt::get(Src->getType(), ShiftAmt));
137        ShiftAmt += isLittleEndian ? SrcBitSize : -SrcBitSize;
138
139        // Mix it in.
140        Elt = ConstantExpr::getOr(Elt, Src);
141      }
142      Result.push_back(Elt);
143    }
144  } else {
145    // Handle: bitcast (<2 x i64> <i64 0, i64 1> to <4 x i32>)
146    unsigned Ratio = NumDstElt/NumSrcElt;
147    unsigned DstBitSize = DstEltTy->getPrimitiveSizeInBits();
148
149    // Loop over each source value, expanding into multiple results.
150    for (unsigned i = 0; i != NumSrcElt; ++i) {
151      Constant *Src = dyn_cast<ConstantInt>(CV->getOperand(i));
152      if (!Src)  // Reject constantexpr elements.
153        return ConstantExpr::getBitCast(C, DestTy);
154
155      unsigned ShiftAmt = isLittleEndian ? 0 : DstBitSize*(Ratio-1);
156      for (unsigned j = 0; j != Ratio; ++j) {
157        // Shift the piece of the value into the right place, depending on
158        // endianness.
159        Constant *Elt = ConstantExpr::getLShr(Src,
160                                    ConstantInt::get(Src->getType(), ShiftAmt));
161        ShiftAmt += isLittleEndian ? DstBitSize : -DstBitSize;
162
163        // Truncate and remember this piece.
164        Result.push_back(ConstantExpr::getTrunc(Elt, DstEltTy));
165      }
166    }
167  }
168
169  return ConstantVector::get(Result.data(), Result.size());
170}
171
172
173/// IsConstantOffsetFromGlobal - If this constant is actually a constant offset
174/// from a global, return the global and the constant.  Because of
175/// constantexprs, this function is recursive.
176static bool IsConstantOffsetFromGlobal(Constant *C, GlobalValue *&GV,
177                                       int64_t &Offset, const TargetData &TD) {
178  // Trivial case, constant is the global.
179  if ((GV = dyn_cast<GlobalValue>(C))) {
180    Offset = 0;
181    return true;
182  }
183
184  // Otherwise, if this isn't a constant expr, bail out.
185  ConstantExpr *CE = dyn_cast<ConstantExpr>(C);
186  if (!CE) return false;
187
188  // Look through ptr->int and ptr->ptr casts.
189  if (CE->getOpcode() == Instruction::PtrToInt ||
190      CE->getOpcode() == Instruction::BitCast)
191    return IsConstantOffsetFromGlobal(CE->getOperand(0), GV, Offset, TD);
192
193  // i32* getelementptr ([5 x i32]* @a, i32 0, i32 5)
194  if (CE->getOpcode() == Instruction::GetElementPtr) {
195    // Cannot compute this if the element type of the pointer is missing size
196    // info.
197    if (!cast<PointerType>(CE->getOperand(0)->getType())
198                 ->getElementType()->isSized())
199      return false;
200
201    // If the base isn't a global+constant, we aren't either.
202    if (!IsConstantOffsetFromGlobal(CE->getOperand(0), GV, Offset, TD))
203      return false;
204
205    // Otherwise, add any offset that our operands provide.
206    gep_type_iterator GTI = gep_type_begin(CE);
207    for (User::const_op_iterator i = CE->op_begin() + 1, e = CE->op_end();
208         i != e; ++i, ++GTI) {
209      ConstantInt *CI = dyn_cast<ConstantInt>(*i);
210      if (!CI) return false;  // Index isn't a simple constant?
211      if (CI->getZExtValue() == 0) continue;  // Not adding anything.
212
213      if (const StructType *ST = dyn_cast<StructType>(*GTI)) {
214        // N = N + Offset
215        Offset += TD.getStructLayout(ST)->getElementOffset(CI->getZExtValue());
216      } else {
217        const SequentialType *SQT = cast<SequentialType>(*GTI);
218        Offset += TD.getTypeAllocSize(SQT->getElementType())*CI->getSExtValue();
219      }
220    }
221    return true;
222  }
223
224  return false;
225}
226
227/// ReadDataFromGlobal - Recursive helper to read bits out of global.  C is the
228/// constant being copied out of. ByteOffset is an offset into C.  CurPtr is the
229/// pointer to copy results into and BytesLeft is the number of bytes left in
230/// the CurPtr buffer.  TD is the target data.
231static bool ReadDataFromGlobal(Constant *C, uint64_t ByteOffset,
232                               unsigned char *CurPtr, unsigned BytesLeft,
233                               const TargetData &TD) {
234  assert(ByteOffset <= TD.getTypeAllocSize(C->getType()) &&
235         "Out of range access");
236
237  // If this element is zero or undefined, we can just return since *CurPtr is
238  // zero initialized.
239  if (isa<ConstantAggregateZero>(C) || isa<UndefValue>(C))
240    return true;
241
242  if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) {
243    if (CI->getBitWidth() > 64 ||
244        (CI->getBitWidth() & 7) != 0)
245      return false;
246
247    uint64_t Val = CI->getZExtValue();
248    unsigned IntBytes = unsigned(CI->getBitWidth()/8);
249
250    for (unsigned i = 0; i != BytesLeft && ByteOffset != IntBytes; ++i) {
251      CurPtr[i] = (unsigned char)(Val >> (ByteOffset * 8));
252      ++ByteOffset;
253    }
254    return true;
255  }
256
257  if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
258    if (CFP->getType()->isDoubleTy()) {
259      C = FoldBitCast(C, Type::getInt64Ty(C->getContext()), TD);
260      return ReadDataFromGlobal(C, ByteOffset, CurPtr, BytesLeft, TD);
261    }
262    if (CFP->getType()->isFloatTy()){
263      C = FoldBitCast(C, Type::getInt32Ty(C->getContext()), TD);
264      return ReadDataFromGlobal(C, ByteOffset, CurPtr, BytesLeft, TD);
265    }
266    return false;
267  }
268
269  if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
270    const StructLayout *SL = TD.getStructLayout(CS->getType());
271    unsigned Index = SL->getElementContainingOffset(ByteOffset);
272    uint64_t CurEltOffset = SL->getElementOffset(Index);
273    ByteOffset -= CurEltOffset;
274
275    while (1) {
276      // If the element access is to the element itself and not to tail padding,
277      // read the bytes from the element.
278      uint64_t EltSize = TD.getTypeAllocSize(CS->getOperand(Index)->getType());
279
280      if (ByteOffset < EltSize &&
281          !ReadDataFromGlobal(CS->getOperand(Index), ByteOffset, CurPtr,
282                              BytesLeft, TD))
283        return false;
284
285      ++Index;
286
287      // Check to see if we read from the last struct element, if so we're done.
288      if (Index == CS->getType()->getNumElements())
289        return true;
290
291      // If we read all of the bytes we needed from this element we're done.
292      uint64_t NextEltOffset = SL->getElementOffset(Index);
293
294      if (BytesLeft <= NextEltOffset-CurEltOffset-ByteOffset)
295        return true;
296
297      // Move to the next element of the struct.
298      CurPtr += NextEltOffset-CurEltOffset-ByteOffset;
299      BytesLeft -= NextEltOffset-CurEltOffset-ByteOffset;
300      ByteOffset = 0;
301      CurEltOffset = NextEltOffset;
302    }
303    // not reached.
304  }
305
306  if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) {
307    uint64_t EltSize = TD.getTypeAllocSize(CA->getType()->getElementType());
308    uint64_t Index = ByteOffset / EltSize;
309    uint64_t Offset = ByteOffset - Index * EltSize;
310    for (; Index != CA->getType()->getNumElements(); ++Index) {
311      if (!ReadDataFromGlobal(CA->getOperand(Index), Offset, CurPtr,
312                              BytesLeft, TD))
313        return false;
314      if (EltSize >= BytesLeft)
315        return true;
316
317      Offset = 0;
318      BytesLeft -= EltSize;
319      CurPtr += EltSize;
320    }
321    return true;
322  }
323
324  if (ConstantVector *CV = dyn_cast<ConstantVector>(C)) {
325    uint64_t EltSize = TD.getTypeAllocSize(CV->getType()->getElementType());
326    uint64_t Index = ByteOffset / EltSize;
327    uint64_t Offset = ByteOffset - Index * EltSize;
328    for (; Index != CV->getType()->getNumElements(); ++Index) {
329      if (!ReadDataFromGlobal(CV->getOperand(Index), Offset, CurPtr,
330                              BytesLeft, TD))
331        return false;
332      if (EltSize >= BytesLeft)
333        return true;
334
335      Offset = 0;
336      BytesLeft -= EltSize;
337      CurPtr += EltSize;
338    }
339    return true;
340  }
341
342  // Otherwise, unknown initializer type.
343  return false;
344}
345
346static Constant *FoldReinterpretLoadFromConstPtr(Constant *C,
347                                                 const TargetData &TD) {
348  const Type *LoadTy = cast<PointerType>(C->getType())->getElementType();
349  const IntegerType *IntType = dyn_cast<IntegerType>(LoadTy);
350
351  // If this isn't an integer load we can't fold it directly.
352  if (!IntType) {
353    // If this is a float/double load, we can try folding it as an int32/64 load
354    // and then bitcast the result.  This can be useful for union cases.  Note
355    // that address spaces don't matter here since we're not going to result in
356    // an actual new load.
357    const Type *MapTy;
358    if (LoadTy->isFloatTy())
359      MapTy = Type::getInt32PtrTy(C->getContext());
360    else if (LoadTy->isDoubleTy())
361      MapTy = Type::getInt64PtrTy(C->getContext());
362    else if (LoadTy->isVectorTy()) {
363      MapTy = IntegerType::get(C->getContext(),
364                               TD.getTypeAllocSizeInBits(LoadTy));
365      MapTy = PointerType::getUnqual(MapTy);
366    } else
367      return 0;
368
369    C = FoldBitCast(C, MapTy, TD);
370    if (Constant *Res = FoldReinterpretLoadFromConstPtr(C, TD))
371      return FoldBitCast(Res, LoadTy, TD);
372    return 0;
373  }
374
375  unsigned BytesLoaded = (IntType->getBitWidth() + 7) / 8;
376  if (BytesLoaded > 32 || BytesLoaded == 0) return 0;
377
378  GlobalValue *GVal;
379  int64_t Offset;
380  if (!IsConstantOffsetFromGlobal(C, GVal, Offset, TD))
381    return 0;
382
383  GlobalVariable *GV = dyn_cast<GlobalVariable>(GVal);
384  if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer() ||
385      !GV->getInitializer()->getType()->isSized())
386    return 0;
387
388  // If we're loading off the beginning of the global, some bytes may be valid,
389  // but we don't try to handle this.
390  if (Offset < 0) return 0;
391
392  // If we're not accessing anything in this constant, the result is undefined.
393  if (uint64_t(Offset) >= TD.getTypeAllocSize(GV->getInitializer()->getType()))
394    return UndefValue::get(IntType);
395
396  unsigned char RawBytes[32] = {0};
397  if (!ReadDataFromGlobal(GV->getInitializer(), Offset, RawBytes,
398                          BytesLoaded, TD))
399    return 0;
400
401  APInt ResultVal = APInt(IntType->getBitWidth(), RawBytes[BytesLoaded-1]);
402  for (unsigned i = 1; i != BytesLoaded; ++i) {
403    ResultVal <<= 8;
404    ResultVal |= RawBytes[BytesLoaded-1-i];
405  }
406
407  return ConstantInt::get(IntType->getContext(), ResultVal);
408}
409
410/// ConstantFoldLoadFromConstPtr - Return the value that a load from C would
411/// produce if it is constant and determinable.  If this is not determinable,
412/// return null.
413Constant *llvm::ConstantFoldLoadFromConstPtr(Constant *C,
414                                             const TargetData *TD) {
415  // First, try the easy cases:
416  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C))
417    if (GV->isConstant() && GV->hasDefinitiveInitializer())
418      return GV->getInitializer();
419
420  // If the loaded value isn't a constant expr, we can't handle it.
421  ConstantExpr *CE = dyn_cast<ConstantExpr>(C);
422  if (!CE) return 0;
423
424  if (CE->getOpcode() == Instruction::GetElementPtr) {
425    if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0)))
426      if (GV->isConstant() && GV->hasDefinitiveInitializer())
427        if (Constant *V =
428             ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE))
429          return V;
430  }
431
432  // Instead of loading constant c string, use corresponding integer value
433  // directly if string length is small enough.
434  std::string Str;
435  if (TD && GetConstantStringInfo(CE, Str) && !Str.empty()) {
436    unsigned StrLen = Str.length();
437    const Type *Ty = cast<PointerType>(CE->getType())->getElementType();
438    unsigned NumBits = Ty->getPrimitiveSizeInBits();
439    // Replace LI with immediate integer store.
440    if ((NumBits >> 3) == StrLen + 1) {
441      APInt StrVal(NumBits, 0);
442      APInt SingleChar(NumBits, 0);
443      if (TD->isLittleEndian()) {
444        for (signed i = StrLen-1; i >= 0; i--) {
445          SingleChar = (uint64_t) Str[i] & UCHAR_MAX;
446          StrVal = (StrVal << 8) | SingleChar;
447        }
448      } else {
449        for (unsigned i = 0; i < StrLen; i++) {
450          SingleChar = (uint64_t) Str[i] & UCHAR_MAX;
451          StrVal = (StrVal << 8) | SingleChar;
452        }
453        // Append NULL at the end.
454        SingleChar = 0;
455        StrVal = (StrVal << 8) | SingleChar;
456      }
457      return ConstantInt::get(CE->getContext(), StrVal);
458    }
459  }
460
461  // If this load comes from anywhere in a constant global, and if the global
462  // is all undef or zero, we know what it loads.
463  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getUnderlyingObject())){
464    if (GV->isConstant() && GV->hasDefinitiveInitializer()) {
465      const Type *ResTy = cast<PointerType>(C->getType())->getElementType();
466      if (GV->getInitializer()->isNullValue())
467        return Constant::getNullValue(ResTy);
468      if (isa<UndefValue>(GV->getInitializer()))
469        return UndefValue::get(ResTy);
470    }
471  }
472
473  // Try hard to fold loads from bitcasted strange and non-type-safe things.  We
474  // currently don't do any of this for big endian systems.  It can be
475  // generalized in the future if someone is interested.
476  if (TD && TD->isLittleEndian())
477    return FoldReinterpretLoadFromConstPtr(CE, *TD);
478  return 0;
479}
480
481static Constant *ConstantFoldLoadInst(const LoadInst *LI, const TargetData *TD){
482  if (LI->isVolatile()) return 0;
483
484  if (Constant *C = dyn_cast<Constant>(LI->getOperand(0)))
485    return ConstantFoldLoadFromConstPtr(C, TD);
486
487  return 0;
488}
489
490/// SymbolicallyEvaluateBinop - One of Op0/Op1 is a constant expression.
491/// Attempt to symbolically evaluate the result of a binary operator merging
492/// these together.  If target data info is available, it is provided as TD,
493/// otherwise TD is null.
494static Constant *SymbolicallyEvaluateBinop(unsigned Opc, Constant *Op0,
495                                           Constant *Op1, const TargetData *TD){
496  // SROA
497
498  // Fold (and 0xffffffff00000000, (shl x, 32)) -> shl.
499  // Fold (lshr (or X, Y), 32) -> (lshr [X/Y], 32) if one doesn't contribute
500  // bits.
501
502
503  // If the constant expr is something like &A[123] - &A[4].f, fold this into a
504  // constant.  This happens frequently when iterating over a global array.
505  if (Opc == Instruction::Sub && TD) {
506    GlobalValue *GV1, *GV2;
507    int64_t Offs1, Offs2;
508
509    if (IsConstantOffsetFromGlobal(Op0, GV1, Offs1, *TD))
510      if (IsConstantOffsetFromGlobal(Op1, GV2, Offs2, *TD) &&
511          GV1 == GV2) {
512        // (&GV+C1) - (&GV+C2) -> C1-C2, pointer arithmetic cannot overflow.
513        return ConstantInt::get(Op0->getType(), Offs1-Offs2);
514      }
515  }
516
517  return 0;
518}
519
520/// CastGEPIndices - If array indices are not pointer-sized integers,
521/// explicitly cast them so that they aren't implicitly casted by the
522/// getelementptr.
523static Constant *CastGEPIndices(Constant *const *Ops, unsigned NumOps,
524                                const Type *ResultTy,
525                                const TargetData *TD) {
526  if (!TD) return 0;
527  const Type *IntPtrTy = TD->getIntPtrType(ResultTy->getContext());
528
529  bool Any = false;
530  SmallVector<Constant*, 32> NewIdxs;
531  for (unsigned i = 1; i != NumOps; ++i) {
532    if ((i == 1 ||
533         !isa<StructType>(GetElementPtrInst::getIndexedType(Ops[0]->getType(),
534                                                            reinterpret_cast<Value *const *>(Ops+1),
535                                                            i-1))) &&
536        Ops[i]->getType() != IntPtrTy) {
537      Any = true;
538      NewIdxs.push_back(ConstantExpr::getCast(CastInst::getCastOpcode(Ops[i],
539                                                                      true,
540                                                                      IntPtrTy,
541                                                                      true),
542                                              Ops[i], IntPtrTy));
543    } else
544      NewIdxs.push_back(Ops[i]);
545  }
546  if (!Any) return 0;
547
548  Constant *C =
549    ConstantExpr::getGetElementPtr(Ops[0], &NewIdxs[0], NewIdxs.size());
550  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
551    if (Constant *Folded = ConstantFoldConstantExpression(CE, TD))
552      C = Folded;
553  return C;
554}
555
556/// SymbolicallyEvaluateGEP - If we can symbolically evaluate the specified GEP
557/// constant expression, do so.
558static Constant *SymbolicallyEvaluateGEP(Constant *const *Ops, unsigned NumOps,
559                                         const Type *ResultTy,
560                                         const TargetData *TD) {
561  Constant *Ptr = Ops[0];
562  if (!TD || !cast<PointerType>(Ptr->getType())->getElementType()->isSized())
563    return 0;
564
565  unsigned BitWidth =
566    TD->getTypeSizeInBits(TD->getIntPtrType(Ptr->getContext()));
567
568  // If this is a constant expr gep that is effectively computing an
569  // "offsetof", fold it into 'cast int Size to T*' instead of 'gep 0, 0, 12'
570  for (unsigned i = 1; i != NumOps; ++i)
571    if (!isa<ConstantInt>(Ops[i]))
572      return 0;
573
574  APInt Offset = APInt(BitWidth,
575                       TD->getIndexedOffset(Ptr->getType(),
576                                            (Value**)Ops+1, NumOps-1));
577  Ptr = cast<Constant>(Ptr->stripPointerCasts());
578
579  // If this is a GEP of a GEP, fold it all into a single GEP.
580  while (GEPOperator *GEP = dyn_cast<GEPOperator>(Ptr)) {
581    SmallVector<Value *, 4> NestedOps(GEP->op_begin()+1, GEP->op_end());
582
583    // Do not try the incorporate the sub-GEP if some index is not a number.
584    bool AllConstantInt = true;
585    for (unsigned i = 0, e = NestedOps.size(); i != e; ++i)
586      if (!isa<ConstantInt>(NestedOps[i])) {
587        AllConstantInt = false;
588        break;
589      }
590    if (!AllConstantInt)
591      break;
592
593    Ptr = cast<Constant>(GEP->getOperand(0));
594    Offset += APInt(BitWidth,
595                    TD->getIndexedOffset(Ptr->getType(),
596                                         (Value**)NestedOps.data(),
597                                         NestedOps.size()));
598    Ptr = cast<Constant>(Ptr->stripPointerCasts());
599  }
600
601  // If the base value for this address is a literal integer value, fold the
602  // getelementptr to the resulting integer value casted to the pointer type.
603  APInt BasePtr(BitWidth, 0);
604  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr))
605    if (CE->getOpcode() == Instruction::IntToPtr)
606      if (ConstantInt *Base = dyn_cast<ConstantInt>(CE->getOperand(0))) {
607        BasePtr = Base->getValue();
608        BasePtr.zextOrTrunc(BitWidth);
609      }
610  if (Ptr->isNullValue() || BasePtr != 0) {
611    Constant *C = ConstantInt::get(Ptr->getContext(), Offset+BasePtr);
612    return ConstantExpr::getIntToPtr(C, ResultTy);
613  }
614
615  // Otherwise form a regular getelementptr. Recompute the indices so that
616  // we eliminate over-indexing of the notional static type array bounds.
617  // This makes it easy to determine if the getelementptr is "inbounds".
618  // Also, this helps GlobalOpt do SROA on GlobalVariables.
619  const Type *Ty = Ptr->getType();
620  SmallVector<Constant*, 32> NewIdxs;
621  do {
622    if (const SequentialType *ATy = dyn_cast<SequentialType>(Ty)) {
623      if (ATy->isPointerTy()) {
624        // The only pointer indexing we'll do is on the first index of the GEP.
625        if (!NewIdxs.empty())
626          break;
627
628        // Only handle pointers to sized types, not pointers to functions.
629        if (!ATy->getElementType()->isSized())
630          return 0;
631      }
632
633      // Determine which element of the array the offset points into.
634      APInt ElemSize(BitWidth, TD->getTypeAllocSize(ATy->getElementType()));
635      if (ElemSize == 0)
636        return 0;
637      APInt NewIdx = Offset.udiv(ElemSize);
638      Offset -= NewIdx * ElemSize;
639      NewIdxs.push_back(ConstantInt::get(TD->getIntPtrType(Ty->getContext()),
640                                         NewIdx));
641      Ty = ATy->getElementType();
642    } else if (const StructType *STy = dyn_cast<StructType>(Ty)) {
643      // Determine which field of the struct the offset points into. The
644      // getZExtValue is at least as safe as the StructLayout API because we
645      // know the offset is within the struct at this point.
646      const StructLayout &SL = *TD->getStructLayout(STy);
647      unsigned ElIdx = SL.getElementContainingOffset(Offset.getZExtValue());
648      NewIdxs.push_back(ConstantInt::get(Type::getInt32Ty(Ty->getContext()),
649                                         ElIdx));
650      Offset -= APInt(BitWidth, SL.getElementOffset(ElIdx));
651      Ty = STy->getTypeAtIndex(ElIdx);
652    } else {
653      // We've reached some non-indexable type.
654      break;
655    }
656  } while (Ty != cast<PointerType>(ResultTy)->getElementType());
657
658  // If we haven't used up the entire offset by descending the static
659  // type, then the offset is pointing into the middle of an indivisible
660  // member, so we can't simplify it.
661  if (Offset != 0)
662    return 0;
663
664  // Create a GEP.
665  Constant *C =
666    ConstantExpr::getGetElementPtr(Ptr, &NewIdxs[0], NewIdxs.size());
667  assert(cast<PointerType>(C->getType())->getElementType() == Ty &&
668         "Computed GetElementPtr has unexpected type!");
669
670  // If we ended up indexing a member with a type that doesn't match
671  // the type of what the original indices indexed, add a cast.
672  if (Ty != cast<PointerType>(ResultTy)->getElementType())
673    C = FoldBitCast(C, ResultTy, *TD);
674
675  return C;
676}
677
678
679
680//===----------------------------------------------------------------------===//
681// Constant Folding public APIs
682//===----------------------------------------------------------------------===//
683
684
685/// ConstantFoldInstruction - Attempt to constant fold the specified
686/// instruction.  If successful, the constant result is returned, if not, null
687/// is returned.  Note that this function can only fail when attempting to fold
688/// instructions like loads and stores, which have no constant expression form.
689///
690Constant *llvm::ConstantFoldInstruction(Instruction *I, const TargetData *TD) {
691  if (PHINode *PN = dyn_cast<PHINode>(I)) {
692    if (PN->getNumIncomingValues() == 0)
693      return UndefValue::get(PN->getType());
694
695    Constant *Result = dyn_cast<Constant>(PN->getIncomingValue(0));
696    if (Result == 0) return 0;
697
698    // Handle PHI nodes specially here...
699    for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i)
700      if (PN->getIncomingValue(i) != Result && PN->getIncomingValue(i) != PN)
701        return 0;   // Not all the same incoming constants...
702
703    // If we reach here, all incoming values are the same constant.
704    return Result;
705  }
706
707  // Scan the operand list, checking to see if they are all constants, if so,
708  // hand off to ConstantFoldInstOperands.
709  SmallVector<Constant*, 8> Ops;
710  for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i)
711    if (Constant *Op = dyn_cast<Constant>(*i))
712      Ops.push_back(Op);
713    else
714      return 0;  // All operands not constant!
715
716  if (const CmpInst *CI = dyn_cast<CmpInst>(I))
717    return ConstantFoldCompareInstOperands(CI->getPredicate(), Ops[0], Ops[1],
718                                           TD);
719
720  if (const LoadInst *LI = dyn_cast<LoadInst>(I))
721    return ConstantFoldLoadInst(LI, TD);
722
723  return ConstantFoldInstOperands(I->getOpcode(), I->getType(),
724                                  Ops.data(), Ops.size(), TD);
725}
726
727/// ConstantFoldConstantExpression - Attempt to fold the constant expression
728/// using the specified TargetData.  If successful, the constant result is
729/// result is returned, if not, null is returned.
730Constant *llvm::ConstantFoldConstantExpression(const ConstantExpr *CE,
731                                               const TargetData *TD) {
732  SmallVector<Constant*, 8> Ops;
733  for (User::const_op_iterator i = CE->op_begin(), e = CE->op_end(); i != e; ++i) {
734    Constant *NewC = cast<Constant>(*i);
735    // Recursively fold the ConstantExpr's operands.
736    if (ConstantExpr *NewCE = dyn_cast<ConstantExpr>(NewC))
737      NewC = ConstantFoldConstantExpression(NewCE, TD);
738    Ops.push_back(NewC);
739  }
740
741  if (CE->isCompare())
742    return ConstantFoldCompareInstOperands(CE->getPredicate(), Ops[0], Ops[1],
743                                           TD);
744  return ConstantFoldInstOperands(CE->getOpcode(), CE->getType(),
745                                  Ops.data(), Ops.size(), TD);
746}
747
748/// ConstantFoldInstOperands - Attempt to constant fold an instruction with the
749/// specified opcode and operands.  If successful, the constant result is
750/// returned, if not, null is returned.  Note that this function can fail when
751/// attempting to fold instructions like loads and stores, which have no
752/// constant expression form.
753///
754/// TODO: This function neither utilizes nor preserves nsw/nuw/inbounds/etc
755/// information, due to only being passed an opcode and operands. Constant
756/// folding using this function strips this information.
757///
758Constant *llvm::ConstantFoldInstOperands(unsigned Opcode, const Type *DestTy,
759                                         Constant* const* Ops, unsigned NumOps,
760                                         const TargetData *TD) {
761  // Handle easy binops first.
762  if (Instruction::isBinaryOp(Opcode)) {
763    if (isa<ConstantExpr>(Ops[0]) || isa<ConstantExpr>(Ops[1]))
764      if (Constant *C = SymbolicallyEvaluateBinop(Opcode, Ops[0], Ops[1], TD))
765        return C;
766
767    return ConstantExpr::get(Opcode, Ops[0], Ops[1]);
768  }
769
770  switch (Opcode) {
771  default: return 0;
772  case Instruction::ICmp:
773  case Instruction::FCmp: assert(0 && "Invalid for compares");
774  case Instruction::Call:
775    if (Function *F = dyn_cast<Function>(Ops[0]))
776      if (canConstantFoldCallTo(F))
777        return ConstantFoldCall(F, Ops+1, NumOps-1);
778    return 0;
779  case Instruction::PtrToInt:
780    // If the input is a inttoptr, eliminate the pair.  This requires knowing
781    // the width of a pointer, so it can't be done in ConstantExpr::getCast.
782    if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ops[0])) {
783      if (TD && CE->getOpcode() == Instruction::IntToPtr) {
784        Constant *Input = CE->getOperand(0);
785        unsigned InWidth = Input->getType()->getScalarSizeInBits();
786        if (TD->getPointerSizeInBits() < InWidth) {
787          Constant *Mask =
788            ConstantInt::get(CE->getContext(), APInt::getLowBitsSet(InWidth,
789                                                  TD->getPointerSizeInBits()));
790          Input = ConstantExpr::getAnd(Input, Mask);
791        }
792        // Do a zext or trunc to get to the dest size.
793        return ConstantExpr::getIntegerCast(Input, DestTy, false);
794      }
795    }
796    return ConstantExpr::getCast(Opcode, Ops[0], DestTy);
797  case Instruction::IntToPtr:
798    // If the input is a ptrtoint, turn the pair into a ptr to ptr bitcast if
799    // the int size is >= the ptr size.  This requires knowing the width of a
800    // pointer, so it can't be done in ConstantExpr::getCast.
801    if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ops[0]))
802      if (TD &&
803          TD->getPointerSizeInBits() <= CE->getType()->getScalarSizeInBits() &&
804          CE->getOpcode() == Instruction::PtrToInt)
805        return FoldBitCast(CE->getOperand(0), DestTy, *TD);
806
807    return ConstantExpr::getCast(Opcode, Ops[0], DestTy);
808  case Instruction::Trunc:
809  case Instruction::ZExt:
810  case Instruction::SExt:
811  case Instruction::FPTrunc:
812  case Instruction::FPExt:
813  case Instruction::UIToFP:
814  case Instruction::SIToFP:
815  case Instruction::FPToUI:
816  case Instruction::FPToSI:
817      return ConstantExpr::getCast(Opcode, Ops[0], DestTy);
818  case Instruction::BitCast:
819    if (TD)
820      return FoldBitCast(Ops[0], DestTy, *TD);
821    return ConstantExpr::getBitCast(Ops[0], DestTy);
822  case Instruction::Select:
823    return ConstantExpr::getSelect(Ops[0], Ops[1], Ops[2]);
824  case Instruction::ExtractElement:
825    return ConstantExpr::getExtractElement(Ops[0], Ops[1]);
826  case Instruction::InsertElement:
827    return ConstantExpr::getInsertElement(Ops[0], Ops[1], Ops[2]);
828  case Instruction::ShuffleVector:
829    return ConstantExpr::getShuffleVector(Ops[0], Ops[1], Ops[2]);
830  case Instruction::GetElementPtr:
831    if (Constant *C = CastGEPIndices(Ops, NumOps, DestTy, TD))
832      return C;
833    if (Constant *C = SymbolicallyEvaluateGEP(Ops, NumOps, DestTy, TD))
834      return C;
835
836    return ConstantExpr::getGetElementPtr(Ops[0], Ops+1, NumOps-1);
837  }
838}
839
840/// ConstantFoldCompareInstOperands - Attempt to constant fold a compare
841/// instruction (icmp/fcmp) with the specified operands.  If it fails, it
842/// returns a constant expression of the specified operands.
843///
844Constant *llvm::ConstantFoldCompareInstOperands(unsigned Predicate,
845                                                Constant *Ops0, Constant *Ops1,
846                                                const TargetData *TD) {
847  // fold: icmp (inttoptr x), null         -> icmp x, 0
848  // fold: icmp (ptrtoint x), 0            -> icmp x, null
849  // fold: icmp (inttoptr x), (inttoptr y) -> icmp trunc/zext x, trunc/zext y
850  // fold: icmp (ptrtoint x), (ptrtoint y) -> icmp x, y
851  //
852  // ConstantExpr::getCompare cannot do this, because it doesn't have TD
853  // around to know if bit truncation is happening.
854  if (ConstantExpr *CE0 = dyn_cast<ConstantExpr>(Ops0)) {
855    if (TD && Ops1->isNullValue()) {
856      const Type *IntPtrTy = TD->getIntPtrType(CE0->getContext());
857      if (CE0->getOpcode() == Instruction::IntToPtr) {
858        // Convert the integer value to the right size to ensure we get the
859        // proper extension or truncation.
860        Constant *C = ConstantExpr::getIntegerCast(CE0->getOperand(0),
861                                                   IntPtrTy, false);
862        Constant *Null = Constant::getNullValue(C->getType());
863        return ConstantFoldCompareInstOperands(Predicate, C, Null, TD);
864      }
865
866      // Only do this transformation if the int is intptrty in size, otherwise
867      // there is a truncation or extension that we aren't modeling.
868      if (CE0->getOpcode() == Instruction::PtrToInt &&
869          CE0->getType() == IntPtrTy) {
870        Constant *C = CE0->getOperand(0);
871        Constant *Null = Constant::getNullValue(C->getType());
872        return ConstantFoldCompareInstOperands(Predicate, C, Null, TD);
873      }
874    }
875
876    if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(Ops1)) {
877      if (TD && CE0->getOpcode() == CE1->getOpcode()) {
878        const Type *IntPtrTy = TD->getIntPtrType(CE0->getContext());
879
880        if (CE0->getOpcode() == Instruction::IntToPtr) {
881          // Convert the integer value to the right size to ensure we get the
882          // proper extension or truncation.
883          Constant *C0 = ConstantExpr::getIntegerCast(CE0->getOperand(0),
884                                                      IntPtrTy, false);
885          Constant *C1 = ConstantExpr::getIntegerCast(CE1->getOperand(0),
886                                                      IntPtrTy, false);
887          return ConstantFoldCompareInstOperands(Predicate, C0, C1, TD);
888        }
889
890        // Only do this transformation if the int is intptrty in size, otherwise
891        // there is a truncation or extension that we aren't modeling.
892        if ((CE0->getOpcode() == Instruction::PtrToInt &&
893             CE0->getType() == IntPtrTy &&
894             CE0->getOperand(0)->getType() == CE1->getOperand(0)->getType()))
895          return ConstantFoldCompareInstOperands(Predicate, CE0->getOperand(0),
896                                                 CE1->getOperand(0), TD);
897      }
898    }
899
900    // icmp eq (or x, y), 0 -> (icmp eq x, 0) & (icmp eq y, 0)
901    // icmp ne (or x, y), 0 -> (icmp ne x, 0) | (icmp ne y, 0)
902    if ((Predicate == ICmpInst::ICMP_EQ || Predicate == ICmpInst::ICMP_NE) &&
903        CE0->getOpcode() == Instruction::Or && Ops1->isNullValue()) {
904      Constant *LHS =
905        ConstantFoldCompareInstOperands(Predicate, CE0->getOperand(0), Ops1,TD);
906      Constant *RHS =
907        ConstantFoldCompareInstOperands(Predicate, CE0->getOperand(1), Ops1,TD);
908      unsigned OpC =
909        Predicate == ICmpInst::ICMP_EQ ? Instruction::And : Instruction::Or;
910      Constant *Ops[] = { LHS, RHS };
911      return ConstantFoldInstOperands(OpC, LHS->getType(), Ops, 2, TD);
912    }
913  }
914
915  return ConstantExpr::getCompare(Predicate, Ops0, Ops1);
916}
917
918
919/// ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a
920/// getelementptr constantexpr, return the constant value being addressed by the
921/// constant expression, or null if something is funny and we can't decide.
922Constant *llvm::ConstantFoldLoadThroughGEPConstantExpr(Constant *C,
923                                                       ConstantExpr *CE) {
924  if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType()))
925    return 0;  // Do not allow stepping over the value!
926
927  // Loop over all of the operands, tracking down which value we are
928  // addressing...
929  gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
930  for (++I; I != E; ++I)
931    if (const StructType *STy = dyn_cast<StructType>(*I)) {
932      ConstantInt *CU = cast<ConstantInt>(I.getOperand());
933      assert(CU->getZExtValue() < STy->getNumElements() &&
934             "Struct index out of range!");
935      unsigned El = (unsigned)CU->getZExtValue();
936      if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
937        C = CS->getOperand(El);
938      } else if (isa<ConstantAggregateZero>(C)) {
939        C = Constant::getNullValue(STy->getElementType(El));
940      } else if (isa<UndefValue>(C)) {
941        C = UndefValue::get(STy->getElementType(El));
942      } else {
943        return 0;
944      }
945    } else if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) {
946      if (const ArrayType *ATy = dyn_cast<ArrayType>(*I)) {
947        if (CI->getZExtValue() >= ATy->getNumElements())
948         return 0;
949        if (ConstantArray *CA = dyn_cast<ConstantArray>(C))
950          C = CA->getOperand(CI->getZExtValue());
951        else if (isa<ConstantAggregateZero>(C))
952          C = Constant::getNullValue(ATy->getElementType());
953        else if (isa<UndefValue>(C))
954          C = UndefValue::get(ATy->getElementType());
955        else
956          return 0;
957      } else if (const VectorType *VTy = dyn_cast<VectorType>(*I)) {
958        if (CI->getZExtValue() >= VTy->getNumElements())
959          return 0;
960        if (ConstantVector *CP = dyn_cast<ConstantVector>(C))
961          C = CP->getOperand(CI->getZExtValue());
962        else if (isa<ConstantAggregateZero>(C))
963          C = Constant::getNullValue(VTy->getElementType());
964        else if (isa<UndefValue>(C))
965          C = UndefValue::get(VTy->getElementType());
966        else
967          return 0;
968      } else {
969        return 0;
970      }
971    } else {
972      return 0;
973    }
974  return C;
975}
976
977
978//===----------------------------------------------------------------------===//
979//  Constant Folding for Calls
980//
981
982/// canConstantFoldCallTo - Return true if its even possible to fold a call to
983/// the specified function.
984bool
985llvm::canConstantFoldCallTo(const Function *F) {
986  switch (F->getIntrinsicID()) {
987  case Intrinsic::sqrt:
988  case Intrinsic::powi:
989  case Intrinsic::bswap:
990  case Intrinsic::ctpop:
991  case Intrinsic::ctlz:
992  case Intrinsic::cttz:
993  case Intrinsic::uadd_with_overflow:
994  case Intrinsic::usub_with_overflow:
995  case Intrinsic::sadd_with_overflow:
996  case Intrinsic::ssub_with_overflow:
997  case Intrinsic::convert_from_fp16:
998  case Intrinsic::convert_to_fp16:
999    return true;
1000  default:
1001    return false;
1002  case 0: break;
1003  }
1004
1005  if (!F->hasName()) return false;
1006  StringRef Name = F->getName();
1007
1008  // In these cases, the check of the length is required.  We don't want to
1009  // return true for a name like "cos\0blah" which strcmp would return equal to
1010  // "cos", but has length 8.
1011  switch (Name[0]) {
1012  default: return false;
1013  case 'a':
1014    return Name == "acos" || Name == "asin" ||
1015      Name == "atan" || Name == "atan2";
1016  case 'c':
1017    return Name == "cos" || Name == "ceil" || Name == "cosf" || Name == "cosh";
1018  case 'e':
1019    return Name == "exp";
1020  case 'f':
1021    return Name == "fabs" || Name == "fmod" || Name == "floor";
1022  case 'l':
1023    return Name == "log" || Name == "log10";
1024  case 'p':
1025    return Name == "pow";
1026  case 's':
1027    return Name == "sin" || Name == "sinh" || Name == "sqrt" ||
1028      Name == "sinf" || Name == "sqrtf";
1029  case 't':
1030    return Name == "tan" || Name == "tanh";
1031  }
1032}
1033
1034static Constant *ConstantFoldFP(double (*NativeFP)(double), double V,
1035                                const Type *Ty) {
1036  errno = 0;
1037  V = NativeFP(V);
1038  if (errno != 0) {
1039    errno = 0;
1040    return 0;
1041  }
1042
1043  if (Ty->isFloatTy())
1044    return ConstantFP::get(Ty->getContext(), APFloat((float)V));
1045  if (Ty->isDoubleTy())
1046    return ConstantFP::get(Ty->getContext(), APFloat(V));
1047  llvm_unreachable("Can only constant fold float/double");
1048  return 0; // dummy return to suppress warning
1049}
1050
1051static Constant *ConstantFoldBinaryFP(double (*NativeFP)(double, double),
1052                                      double V, double W, const Type *Ty) {
1053  errno = 0;
1054  V = NativeFP(V, W);
1055  if (errno != 0) {
1056    errno = 0;
1057    return 0;
1058  }
1059
1060  if (Ty->isFloatTy())
1061    return ConstantFP::get(Ty->getContext(), APFloat((float)V));
1062  if (Ty->isDoubleTy())
1063    return ConstantFP::get(Ty->getContext(), APFloat(V));
1064  llvm_unreachable("Can only constant fold float/double");
1065  return 0; // dummy return to suppress warning
1066}
1067
1068/// ConstantFoldCall - Attempt to constant fold a call to the specified function
1069/// with the specified arguments, returning null if unsuccessful.
1070Constant *
1071llvm::ConstantFoldCall(Function *F,
1072                       Constant *const *Operands, unsigned NumOperands) {
1073  if (!F->hasName()) return 0;
1074  StringRef Name = F->getName();
1075
1076  const Type *Ty = F->getReturnType();
1077  if (NumOperands == 1) {
1078    if (ConstantFP *Op = dyn_cast<ConstantFP>(Operands[0])) {
1079      if (Name == "llvm.convert.to.fp16") {
1080        APFloat Val(Op->getValueAPF());
1081
1082        bool lost = false;
1083        Val.convert(APFloat::IEEEhalf, APFloat::rmNearestTiesToEven, &lost);
1084
1085        return ConstantInt::get(F->getContext(), Val.bitcastToAPInt());
1086      }
1087
1088      if (!Ty->isFloatTy() && !Ty->isDoubleTy())
1089        return 0;
1090      /// Currently APFloat versions of these functions do not exist, so we use
1091      /// the host native double versions.  Float versions are not called
1092      /// directly but for all these it is true (float)(f((double)arg)) ==
1093      /// f(arg).  Long double not supported yet.
1094      double V = Ty->isFloatTy() ? (double)Op->getValueAPF().convertToFloat() :
1095                                     Op->getValueAPF().convertToDouble();
1096      switch (Name[0]) {
1097      case 'a':
1098        if (Name == "acos")
1099          return ConstantFoldFP(acos, V, Ty);
1100        else if (Name == "asin")
1101          return ConstantFoldFP(asin, V, Ty);
1102        else if (Name == "atan")
1103          return ConstantFoldFP(atan, V, Ty);
1104        break;
1105      case 'c':
1106        if (Name == "ceil")
1107          return ConstantFoldFP(ceil, V, Ty);
1108        else if (Name == "cos")
1109          return ConstantFoldFP(cos, V, Ty);
1110        else if (Name == "cosh")
1111          return ConstantFoldFP(cosh, V, Ty);
1112        else if (Name == "cosf")
1113          return ConstantFoldFP(cos, V, Ty);
1114        break;
1115      case 'e':
1116        if (Name == "exp")
1117          return ConstantFoldFP(exp, V, Ty);
1118        break;
1119      case 'f':
1120        if (Name == "fabs")
1121          return ConstantFoldFP(fabs, V, Ty);
1122        else if (Name == "floor")
1123          return ConstantFoldFP(floor, V, Ty);
1124        break;
1125      case 'l':
1126        if (Name == "log" && V > 0)
1127          return ConstantFoldFP(log, V, Ty);
1128        else if (Name == "log10" && V > 0)
1129          return ConstantFoldFP(log10, V, Ty);
1130        else if (Name == "llvm.sqrt.f32" ||
1131                 Name == "llvm.sqrt.f64") {
1132          if (V >= -0.0)
1133            return ConstantFoldFP(sqrt, V, Ty);
1134          else // Undefined
1135            return Constant::getNullValue(Ty);
1136        }
1137        break;
1138      case 's':
1139        if (Name == "sin")
1140          return ConstantFoldFP(sin, V, Ty);
1141        else if (Name == "sinh")
1142          return ConstantFoldFP(sinh, V, Ty);
1143        else if (Name == "sqrt" && V >= 0)
1144          return ConstantFoldFP(sqrt, V, Ty);
1145        else if (Name == "sqrtf" && V >= 0)
1146          return ConstantFoldFP(sqrt, V, Ty);
1147        else if (Name == "sinf")
1148          return ConstantFoldFP(sin, V, Ty);
1149        break;
1150      case 't':
1151        if (Name == "tan")
1152          return ConstantFoldFP(tan, V, Ty);
1153        else if (Name == "tanh")
1154          return ConstantFoldFP(tanh, V, Ty);
1155        break;
1156      default:
1157        break;
1158      }
1159      return 0;
1160    }
1161
1162
1163    if (ConstantInt *Op = dyn_cast<ConstantInt>(Operands[0])) {
1164      if (Name.startswith("llvm.bswap"))
1165        return ConstantInt::get(F->getContext(), Op->getValue().byteSwap());
1166      else if (Name.startswith("llvm.ctpop"))
1167        return ConstantInt::get(Ty, Op->getValue().countPopulation());
1168      else if (Name.startswith("llvm.cttz"))
1169        return ConstantInt::get(Ty, Op->getValue().countTrailingZeros());
1170      else if (Name.startswith("llvm.ctlz"))
1171        return ConstantInt::get(Ty, Op->getValue().countLeadingZeros());
1172      else if (Name == "llvm.convert.from.fp16") {
1173        APFloat Val(Op->getValue());
1174
1175        bool lost = false;
1176        APFloat::opStatus status =
1177          Val.convert(APFloat::IEEEsingle, APFloat::rmNearestTiesToEven, &lost);
1178
1179        // Conversion is always precise.
1180        status = status;
1181        assert(status == APFloat::opOK && !lost &&
1182               "Precision lost during fp16 constfolding");
1183
1184        return ConstantFP::get(F->getContext(), Val);
1185      }
1186      return 0;
1187    }
1188
1189    if (isa<UndefValue>(Operands[0])) {
1190      if (Name.startswith("llvm.bswap"))
1191        return Operands[0];
1192      return 0;
1193    }
1194
1195    return 0;
1196  }
1197
1198  if (NumOperands == 2) {
1199    if (ConstantFP *Op1 = dyn_cast<ConstantFP>(Operands[0])) {
1200      if (!Ty->isFloatTy() && !Ty->isDoubleTy())
1201        return 0;
1202      double Op1V = Ty->isFloatTy() ?
1203                      (double)Op1->getValueAPF().convertToFloat() :
1204                      Op1->getValueAPF().convertToDouble();
1205      if (ConstantFP *Op2 = dyn_cast<ConstantFP>(Operands[1])) {
1206        if (Op2->getType() != Op1->getType())
1207          return 0;
1208
1209        double Op2V = Ty->isFloatTy() ?
1210                      (double)Op2->getValueAPF().convertToFloat():
1211                      Op2->getValueAPF().convertToDouble();
1212
1213        if (Name == "pow")
1214          return ConstantFoldBinaryFP(pow, Op1V, Op2V, Ty);
1215        if (Name == "fmod")
1216          return ConstantFoldBinaryFP(fmod, Op1V, Op2V, Ty);
1217        if (Name == "atan2")
1218          return ConstantFoldBinaryFP(atan2, Op1V, Op2V, Ty);
1219      } else if (ConstantInt *Op2C = dyn_cast<ConstantInt>(Operands[1])) {
1220        if (Name == "llvm.powi.f32")
1221          return ConstantFP::get(F->getContext(),
1222                                 APFloat((float)std::pow((float)Op1V,
1223                                                 (int)Op2C->getZExtValue())));
1224        if (Name == "llvm.powi.f64")
1225          return ConstantFP::get(F->getContext(),
1226                                 APFloat((double)std::pow((double)Op1V,
1227                                                   (int)Op2C->getZExtValue())));
1228      }
1229      return 0;
1230    }
1231
1232
1233    if (ConstantInt *Op1 = dyn_cast<ConstantInt>(Operands[0])) {
1234      if (ConstantInt *Op2 = dyn_cast<ConstantInt>(Operands[1])) {
1235        switch (F->getIntrinsicID()) {
1236        default: break;
1237        case Intrinsic::uadd_with_overflow: {
1238          Constant *Res = ConstantExpr::getAdd(Op1, Op2);           // result.
1239          Constant *Ops[] = {
1240            Res, ConstantExpr::getICmp(CmpInst::ICMP_ULT, Res, Op1) // overflow.
1241          };
1242          return ConstantStruct::get(F->getContext(), Ops, 2, false);
1243        }
1244        case Intrinsic::usub_with_overflow: {
1245          Constant *Res = ConstantExpr::getSub(Op1, Op2);           // result.
1246          Constant *Ops[] = {
1247            Res, ConstantExpr::getICmp(CmpInst::ICMP_UGT, Res, Op1) // overflow.
1248          };
1249          return ConstantStruct::get(F->getContext(), Ops, 2, false);
1250        }
1251        case Intrinsic::sadd_with_overflow: {
1252          Constant *Res = ConstantExpr::getAdd(Op1, Op2);           // result.
1253          Constant *Overflow = ConstantExpr::getSelect(
1254              ConstantExpr::getICmp(CmpInst::ICMP_SGT,
1255                ConstantInt::get(Op1->getType(), 0), Op1),
1256              ConstantExpr::getICmp(CmpInst::ICMP_SGT, Res, Op2),
1257              ConstantExpr::getICmp(CmpInst::ICMP_SLT, Res, Op2)); // overflow.
1258
1259          Constant *Ops[] = { Res, Overflow };
1260          return ConstantStruct::get(F->getContext(), Ops, 2, false);
1261        }
1262        case Intrinsic::ssub_with_overflow: {
1263          Constant *Res = ConstantExpr::getSub(Op1, Op2);           // result.
1264          Constant *Overflow = ConstantExpr::getSelect(
1265              ConstantExpr::getICmp(CmpInst::ICMP_SGT,
1266                ConstantInt::get(Op2->getType(), 0), Op2),
1267              ConstantExpr::getICmp(CmpInst::ICMP_SLT, Res, Op1),
1268              ConstantExpr::getICmp(CmpInst::ICMP_SGT, Res, Op1)); // overflow.
1269
1270          Constant *Ops[] = { Res, Overflow };
1271          return ConstantStruct::get(F->getContext(), Ops, 2, false);
1272        }
1273        }
1274      }
1275
1276      return 0;
1277    }
1278    return 0;
1279  }
1280  return 0;
1281}
1282
1283