lib/Analysis/ConstantFolding.cpp

   1 //===-- ConstantFolding.cpp - Analyze constant folding possibilities ------===//
   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 family of functions determines the possibility of performing constant
  11 // folding.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Analysis/ConstantFolding.h"
  16 #include "llvm/Constants.h"
  17 #include "llvm/DerivedTypes.h"
  18 #include "llvm/Function.h"
  19 #include "llvm/Instructions.h"
  20 #include "llvm/Intrinsics.h"
  21 #include "llvm/ADT/SmallVector.h"
  22 #include "llvm/ADT/StringMap.h"
  23 #include "llvm/Target/TargetData.h"
  24 #include "llvm/Support/GetElementPtrTypeIterator.h"
  25 #include "llvm/Support/MathExtras.h"
  26 #include <cerrno>
  27 #include <cmath>
  28 using namespace llvm;
  29
  30 //===----------------------------------------------------------------------===//
  31 // Constant Folding internal helper functions
  32 //===----------------------------------------------------------------------===//
  33
  34 /// IsConstantOffsetFromGlobal - If this constant is actually a constant offset
  35 /// from a global, return the global and the constant.  Because of
  36 /// constantexprs, this function is recursive.
  37 static bool IsConstantOffsetFromGlobal(Constant *C, GlobalValue *&GV,
  38                                        int64_t &Offset, const TargetData &TD) {
  39   // Trivial case, constant is the global.
  40   if ((GV = dyn_cast<GlobalValue>(C))) {
  41     Offset = 0;
  42     return true;
  43   }
  44
  45   // Otherwise, if this isn't a constant expr, bail out.
  46   ConstantExpr *CE = dyn_cast<ConstantExpr>(C);
  47   if (!CE) return false;
  48
  49   // Look through ptr->int and ptr->ptr casts.
  50   if (CE->getOpcode() == Instruction::PtrToInt ||
  51       CE->getOpcode() == Instruction::BitCast)
  52     return IsConstantOffsetFromGlobal(CE->getOperand(0), GV, Offset, TD);
  53
  54   // i32* getelementptr ([5 x i32]* @a, i32 0, i32 5)
  55   if (CE->getOpcode() == Instruction::GetElementPtr) {
  56     // Cannot compute this if the element type of the pointer is missing size
  57     // info.
  58     if (!cast<PointerType>(CE->getOperand(0)->getType())
  59                  ->getElementType()->isSized())
  60       return false;
  61
  62     // If the base isn't a global+constant, we aren't either.
  63     if (!IsConstantOffsetFromGlobal(CE->getOperand(0), GV, Offset, TD))
  64       return false;
  65
  66     // Otherwise, add any offset that our operands provide.
  67     gep_type_iterator GTI = gep_type_begin(CE);
  68     for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i, ++GTI) {
  69       ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(i));
  70       if (!CI) return false;  // Index isn't a simple constant?
  71       if (CI->getZExtValue() == 0) continue;  // Not adding anything.
  72
  73       if (const StructType *ST = dyn_cast<StructType>(*GTI)) {
  74         // N = N + Offset
  75         Offset += TD.getStructLayout(ST)->getElementOffset(CI->getZExtValue());
  76       } else {
  77         const SequentialType *SQT = cast<SequentialType>(*GTI);
  78         Offset += TD.getABITypeSize(SQT->getElementType())*CI->getSExtValue();
  79       }
  80     }
  81     return true;
  82   }
  83
  84   return false;
  85 }
  86
  87
  88 /// SymbolicallyEvaluateBinop - One of Op0/Op1 is a constant expression.
  89 /// Attempt to symbolically evaluate the result of  a binary operator merging
  90 /// these together.  If target data info is available, it is provided as TD,
  91 /// otherwise TD is null.
  92 static Constant *SymbolicallyEvaluateBinop(unsigned Opc, Constant *Op0,
  93                                            Constant *Op1, const TargetData *TD){
  94   // SROA
  95
  96   // Fold (and 0xffffffff00000000, (shl x, 32)) -> shl.
  97   // Fold (lshr (or X, Y), 32) -> (lshr [X/Y], 32) if one doesn't contribute
  98   // bits.
  99
 100
 101   // If the constant expr is something like &A[123] - &A[4].f, fold this into a
 102   // constant.  This happens frequently when iterating over a global array.
 103   if (Opc == Instruction::Sub && TD) {
 104     GlobalValue *GV1, *GV2;
 105     int64_t Offs1, Offs2;
 106
 107     if (IsConstantOffsetFromGlobal(Op0, GV1, Offs1, *TD))
 108       if (IsConstantOffsetFromGlobal(Op1, GV2, Offs2, *TD) &&
 109           GV1 == GV2) {
 110         // (&GV+C1) - (&GV+C2) -> C1-C2, pointer arithmetic cannot overflow.
 111         return ConstantInt::get(Op0->getType(), Offs1-Offs2);
 112       }
 113   }
 114
 115   // TODO: Fold icmp setne/seteq as well.
 116   return 0;
 117 }
 118
 119 /// SymbolicallyEvaluateGEP - If we can symbolically evaluate the specified GEP
 120 /// constant expression, do so.
 121 static Constant *SymbolicallyEvaluateGEP(Constant* const* Ops, unsigned NumOps,
 122                                          const Type *ResultTy,
 123                                          const TargetData *TD) {
 124   Constant *Ptr = Ops[0];
 125   if (!cast<PointerType>(Ptr->getType())->getElementType()->isSized())
 126     return 0;
 127
 128   if (TD && Ptr->isNullValue()) {
 129     // If this is a constant expr gep that is effectively computing an
 130     // "offsetof", fold it into 'cast int Size to T*' instead of 'gep 0, 0, 12'
 131     bool isFoldableGEP = true;
 132     for (unsigned i = 1; i != NumOps; ++i)
 133       if (!isa<ConstantInt>(Ops[i])) {
 134         isFoldableGEP = false;
 135         break;
 136       }
 137     if (isFoldableGEP) {
 138       uint64_t Offset = TD->getIndexedOffset(Ptr->getType(),
 139                                              (Value**)Ops+1, NumOps-1);
 140       Constant *C = ConstantInt::get(TD->getIntPtrType(), Offset);
 141       return ConstantExpr::getIntToPtr(C, ResultTy);
 142     }
 143   }
 144
 145   return 0;
 146 }
 147
 148 /// FoldBitCast - Constant fold bitcast, symbolically evaluating it with
 149 /// targetdata.  Return 0 if unfoldable.
 150 static Constant *FoldBitCast(Constant *C, const Type *DestTy,
 151                              const TargetData &TD) {
 152   // If this is a bitcast from constant vector -> vector, fold it.
 153   if (ConstantVector *CV = dyn_cast<ConstantVector>(C)) {
 154     if (const VectorType *DestVTy = dyn_cast<VectorType>(DestTy)) {
 155       // If the element types match, VMCore can fold it.
 156       unsigned NumDstElt = DestVTy->getNumElements();
 157       unsigned NumSrcElt = CV->getNumOperands();
 158       if (NumDstElt == NumSrcElt)
 159         return 0;
 160
 161       const Type *SrcEltTy = CV->getType()->getElementType();
 162       const Type *DstEltTy = DestVTy->getElementType();
 163
 164       // Otherwise, we're changing the number of elements in a vector, which
 165       // requires endianness information to do the right thing.  For example,
 166       //    bitcast (<2 x i64> <i64 0, i64 1> to <4 x i32>)
 167       // folds to (little endian):
 168       //    <4 x i32> <i32 0, i32 0, i32 1, i32 0>
 169       // and to (big endian):
 170       //    <4 x i32> <i32 0, i32 0, i32 0, i32 1>
 171
 172       // First thing is first.  We only want to think about integer here, so if
 173       // we have something in FP form, recast it as integer.
 174       if (DstEltTy->isFloatingPoint()) {
 175         // Fold to an vector of integers with same size as our FP type.
 176         unsigned FPWidth = DstEltTy->getPrimitiveSizeInBits();
 177         const Type *DestIVTy = VectorType::get(IntegerType::get(FPWidth),
 178                                                NumDstElt);
 179         // Recursively handle this integer conversion, if possible.
 180         C = FoldBitCast(C, DestIVTy, TD);
 181         if (!C) return 0;
 182
 183         // Finally, VMCore can handle this now that #elts line up.
 184         return ConstantExpr::getBitCast(C, DestTy);
 185       }
 186
 187       // Okay, we know the destination is integer, if the input is FP, convert
 188       // it to integer first.
 189       if (SrcEltTy->isFloatingPoint()) {
 190         unsigned FPWidth = SrcEltTy->getPrimitiveSizeInBits();
 191         const Type *SrcIVTy = VectorType::get(IntegerType::get(FPWidth),
 192                                               NumSrcElt);
 193         // Ask VMCore to do the conversion now that #elts line up.
 194         C = ConstantExpr::getBitCast(C, SrcIVTy);
 195         CV = dyn_cast<ConstantVector>(C);
 196         if (!CV) return 0;  // If VMCore wasn't able to fold it, bail out.
 197       }
 198
 199       // Now we know that the input and output vectors are both integer vectors
 200       // of the same size, and that their #elements is not the same.  Do the
 201       // conversion here, which depends on whether the input or output has
 202       // more elements.
 203       bool isLittleEndian = TD.isLittleEndian();
 204
 205       SmallVector<Constant*, 32> Result;
 206       if (NumDstElt < NumSrcElt) {
 207         // Handle: bitcast (<4 x i32> <i32 0, i32 1, i32 2, i32 3> to <2 x i64>)
 208         Constant *Zero = Constant::getNullValue(DstEltTy);
 209         unsigned Ratio = NumSrcElt/NumDstElt;
 210         unsigned SrcBitSize = SrcEltTy->getPrimitiveSizeInBits();
 211         unsigned SrcElt = 0;
 212         for (unsigned i = 0; i != NumDstElt; ++i) {
 213           // Build each element of the result.
 214           Constant *Elt = Zero;
 215           unsigned ShiftAmt = isLittleEndian ? 0 : SrcBitSize*(Ratio-1);
 216           for (unsigned j = 0; j != Ratio; ++j) {
 217             Constant *Src = dyn_cast<ConstantInt>(CV->getOperand(SrcElt++));
 218             if (!Src) return 0;  // Reject constantexpr elements.
 219
 220             // Zero extend the element to the right size.
 221             Src = ConstantExpr::getZExt(Src, Elt->getType());
 222
 223             // Shift it to the right place, depending on endianness.
 224             Src = ConstantExpr::getShl(Src,
 225                                     ConstantInt::get(Src->getType(), ShiftAmt));
 226             ShiftAmt += isLittleEndian ? SrcBitSize : -SrcBitSize;
 227
 228             // Mix it in.
 229             Elt = ConstantExpr::getOr(Elt, Src);
 230           }
 231           Result.push_back(Elt);
 232         }
 233       } else {
 234         // Handle: bitcast (<2 x i64> <i64 0, i64 1> to <4 x i32>)
 235         unsigned Ratio = NumDstElt/NumSrcElt;
 236         unsigned DstBitSize = DstEltTy->getPrimitiveSizeInBits();
 237
 238         // Loop over each source value, expanding into multiple results.
 239         for (unsigned i = 0; i != NumSrcElt; ++i) {
 240           Constant *Src = dyn_cast<ConstantInt>(CV->getOperand(i));
 241           if (!Src) return 0;  // Reject constantexpr elements.
 242
 243           unsigned ShiftAmt = isLittleEndian ? 0 : DstBitSize*(Ratio-1);
 244           for (unsigned j = 0; j != Ratio; ++j) {
 245             // Shift the piece of the value into the right place, depending on
 246             // endianness.
 247             Constant *Elt = ConstantExpr::getLShr(Src,
 248                                 ConstantInt::get(Src->getType(), ShiftAmt));
 249             ShiftAmt += isLittleEndian ? DstBitSize : -DstBitSize;
 250
 251             // Truncate and remember this piece.
 252             Result.push_back(ConstantExpr::getTrunc(Elt, DstEltTy));
 253           }
 254         }
 255       }
 256
 257       return ConstantVector::get(&Result[0], Result.size());
 258     }
 259   }
 260
 261   return 0;
 262 }
 263
 264
 265 //===----------------------------------------------------------------------===//
 266 // Constant Folding public APIs
 267 //===----------------------------------------------------------------------===//
 268
 269
 270 /// ConstantFoldInstruction - Attempt to constant fold the specified
 271 /// instruction.  If successful, the constant result is returned, if not, null
 272 /// is returned.  Note that this function can only fail when attempting to fold
 273 /// instructions like loads and stores, which have no constant expression form.
 274 ///
 275 Constant *llvm::ConstantFoldInstruction(Instruction *I, const TargetData *TD) {
 276   if (PHINode *PN = dyn_cast<PHINode>(I)) {
 277     if (PN->getNumIncomingValues() == 0)
 278       return Constant::getNullValue(PN->getType());
 279
 280     Constant *Result = dyn_cast<Constant>(PN->getIncomingValue(0));
 281     if (Result == 0) return 0;
 282
 283     // Handle PHI nodes specially here...
 284     for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i)
 285       if (PN->getIncomingValue(i) != Result && PN->getIncomingValue(i) != PN)
 286         return 0;   // Not all the same incoming constants...
 287
 288     // If we reach here, all incoming values are the same constant.
 289     return Result;
 290   }
 291
 292   // Scan the operand list, checking to see if they are all constants, if so,
 293   // hand off to ConstantFoldInstOperands.
 294   SmallVector<Constant*, 8> Ops;
 295   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
 296     if (Constant *Op = dyn_cast<Constant>(I->getOperand(i)))
 297       Ops.push_back(Op);
 298     else
 299       return 0;  // All operands not constant!
 300
 301   if (const CmpInst *CI = dyn_cast<CmpInst>(I))
 302     return ConstantFoldCompareInstOperands(CI->getPredicate(),
 303                                            &Ops[0], Ops.size(), TD);
 304   else
 305     return ConstantFoldInstOperands(I->getOpcode(), I->getType(),
 306                                     &Ops[0], Ops.size(), TD);
 307 }
 308
 309 /// ConstantFoldInstOperands - Attempt to constant fold an instruction with the
 310 /// specified opcode and operands.  If successful, the constant result is
 311 /// returned, if not, null is returned.  Note that this function can fail when
 312 /// attempting to fold instructions like loads and stores, which have no
 313 /// constant expression form.
 314 ///
 315 Constant *llvm::ConstantFoldInstOperands(unsigned Opcode, const Type *DestTy,
 316                                          Constant* const* Ops, unsigned NumOps,
 317                                          const TargetData *TD) {
 318   // Handle easy binops first.
 319   if (Instruction::isBinaryOp(Opcode)) {
 320     if (isa<ConstantExpr>(Ops[0]) || isa<ConstantExpr>(Ops[1]))
 321       if (Constant *C = SymbolicallyEvaluateBinop(Opcode, Ops[0], Ops[1], TD))
 322         return C;
 323
 324     return ConstantExpr::get(Opcode, Ops[0], Ops[1]);
 325   }
 326
 327   switch (Opcode) {
 328   default: return 0;
 329   case Instruction::Call:
 330     if (Function *F = dyn_cast<Function>(Ops[0]))
 331       if (canConstantFoldCallTo(F))
 332         return ConstantFoldCall(F, Ops+1, NumOps-1);
 333     return 0;
 334   case Instruction::ICmp:
 335   case Instruction::FCmp:
 336     assert(0 &&"This function is invalid for compares: no predicate specified");
 337   case Instruction::PtrToInt:
 338     // If the input is a inttoptr, eliminate the pair.  This requires knowing
 339     // the width of a pointer, so it can't be done in ConstantExpr::getCast.
 340     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ops[0])) {
 341       if (TD && CE->getOpcode() == Instruction::IntToPtr) {
 342         Constant *Input = CE->getOperand(0);
 343         unsigned InWidth = Input->getType()->getPrimitiveSizeInBits();
 344         Constant *Mask =
 345           ConstantInt::get(APInt::getLowBitsSet(InWidth,
 346                                                 TD->getPointerSizeInBits()));
 347         Input = ConstantExpr::getAnd(Input, Mask);
 348         // Do a zext or trunc to get to the dest size.
 349         return ConstantExpr::getIntegerCast(Input, DestTy, false);
 350       }
 351     }
 352     return ConstantExpr::getCast(Opcode, Ops[0], DestTy);
 353   case Instruction::IntToPtr:
 354   case Instruction::Trunc:
 355   case Instruction::ZExt:
 356   case Instruction::SExt:
 357   case Instruction::FPTrunc:
 358   case Instruction::FPExt:
 359   case Instruction::UIToFP:
 360   case Instruction::SIToFP:
 361   case Instruction::FPToUI:
 362   case Instruction::FPToSI:
 363       return ConstantExpr::getCast(Opcode, Ops[0], DestTy);
 364   case Instruction::BitCast:
 365     if (TD)
 366       if (Constant *C = FoldBitCast(Ops[0], DestTy, *TD))
 367         return C;
 368     return ConstantExpr::getBitCast(Ops[0], DestTy);
 369   case Instruction::Select:
 370     return ConstantExpr::getSelect(Ops[0], Ops[1], Ops[2]);
 371   case Instruction::ExtractElement:
 372     return ConstantExpr::getExtractElement(Ops[0], Ops[1]);
 373   case Instruction::InsertElement:
 374     return ConstantExpr::getInsertElement(Ops[0], Ops[1], Ops[2]);
 375   case Instruction::ShuffleVector:
 376     return ConstantExpr::getShuffleVector(Ops[0], Ops[1], Ops[2]);
 377   case Instruction::GetElementPtr:
 378     if (Constant *C = SymbolicallyEvaluateGEP(Ops, NumOps, DestTy, TD))
 379       return C;
 380
 381     return ConstantExpr::getGetElementPtr(Ops[0], Ops+1, NumOps-1);
 382   }
 383 }
 384
 385 /// ConstantFoldCompareInstOperands - Attempt to constant fold a compare
 386 /// instruction (icmp/fcmp) with the specified operands.  If it fails, it
 387 /// returns a constant expression of the specified operands.
 388 ///
 389 Constant *llvm::ConstantFoldCompareInstOperands(unsigned Predicate,
 390                                                 Constant*const * Ops,
 391                                                 unsigned NumOps,
 392                                                 const TargetData *TD) {
 393   // fold: icmp (inttoptr x), null         -> icmp x, 0
 394   // fold: icmp (ptrtoint x), 0            -> icmp x, null
 395   // fold: icmp (inttoptr x), (inttoptr y) -> icmp x, y
 396   // fold: icmp (ptrtoint x), (ptrtoint y) -> icmp x, y
 397   //
 398   // ConstantExpr::getCompare cannot do this, because it doesn't have TD
 399   // around to know if bit truncation is happening.
 400   if (ConstantExpr *CE0 = dyn_cast<ConstantExpr>(Ops[0])) {
 401     if (TD && Ops[1]->isNullValue()) {
 402       const Type *IntPtrTy = TD->getIntPtrType();
 403       if (CE0->getOpcode() == Instruction::IntToPtr) {
 404         // Convert the integer value to the right size to ensure we get the
 405         // proper extension or truncation.
 406         Constant *C = ConstantExpr::getIntegerCast(CE0->getOperand(0),
 407                                                    IntPtrTy, false);
 408         Constant *NewOps[] = { C, Constant::getNullValue(C->getType()) };
 409         return ConstantFoldCompareInstOperands(Predicate, NewOps, 2, TD);
 410       }
 411
 412       // Only do this transformation if the int is intptrty in size, otherwise
 413       // there is a truncation or extension that we aren't modeling.
 414       if (CE0->getOpcode() == Instruction::PtrToInt &&
 415           CE0->getType() == IntPtrTy) {
 416         Constant *C = CE0->getOperand(0);
 417         Constant *NewOps[] = { C, Constant::getNullValue(C->getType()) };
 418         // FIXME!
 419         return ConstantFoldCompareInstOperands(Predicate, NewOps, 2, TD);
 420       }
 421     }
 422
 423     if (TD && isa<ConstantExpr>(Ops[1]) &&
 424         cast<ConstantExpr>(Ops[1])->getOpcode() == CE0->getOpcode()) {
 425       const Type *IntPtrTy = TD->getIntPtrType();
 426       // Only do this transformation if the int is intptrty in size, otherwise
 427       // there is a truncation or extension that we aren't modeling.
 428       if ((CE0->getOpcode() == Instruction::IntToPtr &&
 429            CE0->getOperand(0)->getType() == IntPtrTy &&
 430            Ops[1]->getOperand(0)->getType() == IntPtrTy) ||
 431           (CE0->getOpcode() == Instruction::PtrToInt &&
 432            CE0->getType() == IntPtrTy &&
 433            CE0->getOperand(0)->getType() == Ops[1]->getOperand(0)->getType())) {
 434         Constant *NewOps[] = {
 435           CE0->getOperand(0), cast<ConstantExpr>(Ops[1])->getOperand(0)
 436         };
 437         return ConstantFoldCompareInstOperands(Predicate, NewOps, 2, TD);
 438       }
 439     }
 440   }
 441   return ConstantExpr::getCompare(Predicate, Ops[0], Ops[1]);
 442 }
 443
 444
 445 /// ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a
 446 /// getelementptr constantexpr, return the constant value being addressed by the
 447 /// constant expression, or null if something is funny and we can't decide.
 448 Constant *llvm::ConstantFoldLoadThroughGEPConstantExpr(Constant *C,
 449                                                        ConstantExpr *CE) {
 450   if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType()))
 451     return 0;  // Do not allow stepping over the value!
 452
 453   // Loop over all of the operands, tracking down which value we are
 454   // addressing...
 455   gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
 456   for (++I; I != E; ++I)
 457     if (const StructType *STy = dyn_cast<StructType>(*I)) {
 458       ConstantInt *CU = cast<ConstantInt>(I.getOperand());
 459       assert(CU->getZExtValue() < STy->getNumElements() &&
 460              "Struct index out of range!");
 461       unsigned El = (unsigned)CU->getZExtValue();
 462       if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
 463         C = CS->getOperand(El);
 464       } else if (isa<ConstantAggregateZero>(C)) {
 465         C = Constant::getNullValue(STy->getElementType(El));
 466       } else if (isa<UndefValue>(C)) {
 467         C = UndefValue::get(STy->getElementType(El));
 468       } else {
 469         return 0;
 470       }
 471     } else if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) {
 472       if (const ArrayType *ATy = dyn_cast<ArrayType>(*I)) {
 473         if (CI->getZExtValue() >= ATy->getNumElements())
 474          return 0;
 475         if (ConstantArray *CA = dyn_cast<ConstantArray>(C))
 476           C = CA->getOperand(CI->getZExtValue());
 477         else if (isa<ConstantAggregateZero>(C))
 478           C = Constant::getNullValue(ATy->getElementType());
 479         else if (isa<UndefValue>(C))
 480           C = UndefValue::get(ATy->getElementType());
 481         else
 482           return 0;
 483       } else if (const VectorType *PTy = dyn_cast<VectorType>(*I)) {
 484         if (CI->getZExtValue() >= PTy->getNumElements())
 485           return 0;
 486         if (ConstantVector *CP = dyn_cast<ConstantVector>(C))
 487           C = CP->getOperand(CI->getZExtValue());
 488         else if (isa<ConstantAggregateZero>(C))
 489           C = Constant::getNullValue(PTy->getElementType());
 490         else if (isa<UndefValue>(C))
 491           C = UndefValue::get(PTy->getElementType());
 492         else
 493           return 0;
 494       } else {
 495         return 0;
 496       }
 497     } else {
 498       return 0;
 499     }
 500   return C;
 501 }
 502
 503
 504 //===----------------------------------------------------------------------===//
 505 //  Constant Folding for Calls
 506 //
 507
 508 /// canConstantFoldCallTo - Return true if its even possible to fold a call to
 509 /// the specified function.
 510 bool
 511 llvm::canConstantFoldCallTo(Function *F) {
 512   switch (F->getIntrinsicID()) {
 513   case Intrinsic::sqrt:
 514   case Intrinsic::powi:
 515   case Intrinsic::bswap:
 516   case Intrinsic::ctpop:
 517   case Intrinsic::ctlz:
 518   case Intrinsic::cttz:
 519     return true;
 520   default: break;
 521   }
 522
 523   const ValueName *NameVal = F->getValueName();
 524   if (NameVal == 0) return false;
 525   const char *Str = NameVal->getKeyData();
 526   unsigned Len = NameVal->getKeyLength();
 527
 528   // In these cases, the check of the length is required.  We don't want to
 529   // return true for a name like "cos\0blah" which strcmp would return equal to
 530   // "cos", but has length 8.
 531   switch (Str[0]) {
 532   default: return false;
 533   case 'a':
 534     if (Len == 4)
 535       return !strcmp(Str, "acos") || !strcmp(Str, "asin") ||
 536              !strcmp(Str, "atan");
 537     else if (Len == 5)
 538       return !strcmp(Str, "atan2");
 539     return false;
 540   case 'c':
 541     if (Len == 3)
 542       return !strcmp(Str, "cos");
 543     else if (Len == 4)
 544       return !strcmp(Str, "ceil") || !strcmp(Str, "cosf") ||
 545              !strcmp(Str, "cosh");
 546     return false;
 547   case 'e':
 548     if (Len == 3)
 549       return !strcmp(Str, "exp");
 550     return false;
 551   case 'f':
 552     if (Len == 4)
 553       return !strcmp(Str, "fabs") || !strcmp(Str, "fmod");
 554     else if (Len == 5)
 555       return !strcmp(Str, "floor");
 556     return false;
 557     break;
 558   case 'l':
 559     if (Len == 3 && !strcmp(Str, "log"))
 560       return true;
 561     if (Len == 5 && !strcmp(Str, "log10"))
 562       return true;
 563     return false;
 564   case 'p':
 565     if (Len == 3 && !strcmp(Str, "pow"))
 566       return true;
 567     return false;
 568   case 's':
 569     if (Len == 3)
 570       return !strcmp(Str, "sin");
 571     if (Len == 4)
 572       return !strcmp(Str, "sinh") || !strcmp(Str, "sqrt");
 573     if (Len == 5)
 574       return !strcmp(Str, "sqrtf");
 575     return false;
 576   case 't':
 577     if (Len == 3 && !strcmp(Str, "tan"))
 578       return true;
 579     else if (Len == 4 && !strcmp(Str, "tanh"))
 580       return true;
 581     return false;
 582   }
 583 }
 584
 585 static Constant *ConstantFoldFP(double (*NativeFP)(double), double V,
 586                                 const Type *Ty) {
 587   errno = 0;
 588   V = NativeFP(V);
 589   if (errno == 0) {
 590     if (Ty==Type::FloatTy)
 591       return ConstantFP::get(Ty, APFloat((float)V));
 592     else if (Ty==Type::DoubleTy)
 593       return ConstantFP::get(Ty, APFloat(V));
 594     else
 595       assert(0);
 596   }
 597   errno = 0;
 598   return 0;
 599 }
 600
 601 static Constant *ConstantFoldBinaryFP(double (*NativeFP)(double, double),
 602                                       double V, double W,
 603                                       const Type *Ty) {
 604   errno = 0;
 605   V = NativeFP(V, W);
 606   if (errno == 0) {
 607     if (Ty==Type::FloatTy)
 608       return ConstantFP::get(Ty, APFloat((float)V));
 609     else if (Ty==Type::DoubleTy)
 610       return ConstantFP::get(Ty, APFloat(V));
 611     else
 612       assert(0);
 613   }
 614   errno = 0;
 615   return 0;
 616 }
 617
 618 /// ConstantFoldCall - Attempt to constant fold a call to the specified function
 619 /// with the specified arguments, returning null if unsuccessful.
 620
 621 Constant *
 622 llvm::ConstantFoldCall(Function *F,
 623                        Constant* const* Operands, unsigned NumOperands) {
 624   const ValueName *NameVal = F->getValueName();
 625   if (NameVal == 0) return 0;
 626   const char *Str = NameVal->getKeyData();
 627   unsigned Len = NameVal->getKeyLength();
 628
 629   const Type *Ty = F->getReturnType();
 630   if (NumOperands == 1) {
 631     if (ConstantFP *Op = dyn_cast<ConstantFP>(Operands[0])) {
 632       if (Ty!=Type::FloatTy && Ty!=Type::DoubleTy)
 633         return 0;
 634       /// Currently APFloat versions of these functions do not exist, so we use
 635       /// the host native double versions.  Float versions are not called
 636       /// directly but for all these it is true (float)(f((double)arg)) ==
 637       /// f(arg).  Long double not supported yet.
 638       double V = Ty==Type::FloatTy ? (double)Op->getValueAPF().convertToFloat():
 639                                      Op->getValueAPF().convertToDouble();
 640       switch (Str[0]) {
 641       case 'a':
 642         if (Len == 4 && !strcmp(Str, "acos"))
 643           return ConstantFoldFP(acos, V, Ty);
 644         else if (Len == 4 && !strcmp(Str, "asin"))
 645           return ConstantFoldFP(asin, V, Ty);
 646         else if (Len == 4 && !strcmp(Str, "atan"))
 647           return ConstantFoldFP(atan, V, Ty);
 648         break;
 649       case 'c':
 650         if (Len == 4 && !strcmp(Str, "ceil"))
 651           return ConstantFoldFP(ceil, V, Ty);
 652         else if (Len == 3 && !strcmp(Str, "cos"))
 653           return ConstantFoldFP(cos, V, Ty);
 654         else if (Len == 4 && !strcmp(Str, "cosh"))
 655           return ConstantFoldFP(cosh, V, Ty);
 656         break;
 657       case 'e':
 658         if (Len == 3 && !strcmp(Str, "exp"))
 659           return ConstantFoldFP(exp, V, Ty);
 660         break;
 661       case 'f':
 662         if (Len == 4 && !strcmp(Str, "fabs"))
 663           return ConstantFoldFP(fabs, V, Ty);
 664         else if (Len == 5 && !strcmp(Str, "floor"))
 665           return ConstantFoldFP(floor, V, Ty);
 666         break;
 667       case 'l':
 668         if (Len == 3 && !strcmp(Str, "log") && V > 0)
 669           return ConstantFoldFP(log, V, Ty);
 670         else if (Len == 5 && !strcmp(Str, "log10") && V > 0)
 671           return ConstantFoldFP(log10, V, Ty);
 672         else if (!strcmp(Str, "llvm.sqrt.f32") ||
 673                  !strcmp(Str, "llvm.sqrt.f64")) {
 674           if (V >= -0.0)
 675             return ConstantFoldFP(sqrt, V, Ty);
 676           else // Undefined
 677             return ConstantFP::get(Ty, Ty==Type::FloatTy ? APFloat(0.0f) :
 678                                        APFloat(0.0));
 679         }
 680         break;
 681       case 's':
 682         if (Len == 3 && !strcmp(Str, "sin"))
 683           return ConstantFoldFP(sin, V, Ty);
 684         else if (Len == 4 && !strcmp(Str, "sinh"))
 685           return ConstantFoldFP(sinh, V, Ty);
 686         else if (Len == 4 && !strcmp(Str, "sqrt") && V >= 0)
 687           return ConstantFoldFP(sqrt, V, Ty);
 688         else if (Len == 5 && !strcmp(Str, "sqrtf") && V >= 0)
 689           return ConstantFoldFP(sqrt, V, Ty);
 690         break;
 691       case 't':
 692         if (Len == 3 && !strcmp(Str, "tan"))
 693           return ConstantFoldFP(tan, V, Ty);
 694         else if (Len == 4 && !strcmp(Str, "tanh"))
 695           return ConstantFoldFP(tanh, V, Ty);
 696         break;
 697       default:
 698         break;
 699       }
 700     } else if (ConstantInt *Op = dyn_cast<ConstantInt>(Operands[0])) {
 701       if (Len > 11 && !memcmp(Str, "llvm.bswap", 10))
 702         return ConstantInt::get(Op->getValue().byteSwap());
 703       else if (Len > 11 && !memcmp(Str, "llvm.ctpop", 10))
 704         return ConstantInt::get(Ty, Op->getValue().countPopulation());
 705       else if (Len > 10 && !memcmp(Str, "llvm.cttz", 9))
 706         return ConstantInt::get(Ty, Op->getValue().countTrailingZeros());
 707       else if (Len > 10 && !memcmp(Str, "llvm.ctlz", 9))
 708         return ConstantInt::get(Ty, Op->getValue().countLeadingZeros());
 709     }
 710   } else if (NumOperands == 2) {
 711     if (ConstantFP *Op1 = dyn_cast<ConstantFP>(Operands[0])) {
 712       if (Ty!=Type::FloatTy && Ty!=Type::DoubleTy)
 713         return 0;
 714       double Op1V = Ty==Type::FloatTy ?
 715                       (double)Op1->getValueAPF().convertToFloat():
 716                       Op1->getValueAPF().convertToDouble();
 717       if (ConstantFP *Op2 = dyn_cast<ConstantFP>(Operands[1])) {
 718         double Op2V = Ty==Type::FloatTy ?
 719                       (double)Op2->getValueAPF().convertToFloat():
 720                       Op2->getValueAPF().convertToDouble();
 721
 722         if (Len == 3 && !strcmp(Str, "pow")) {
 723           return ConstantFoldBinaryFP(pow, Op1V, Op2V, Ty);
 724         } else if (Len == 4 && !strcmp(Str, "fmod")) {
 725           return ConstantFoldBinaryFP(fmod, Op1V, Op2V, Ty);
 726         } else if (Len == 5 && !strcmp(Str, "atan2")) {
 727           return ConstantFoldBinaryFP(atan2, Op1V, Op2V, Ty);
 728         }
 729       } else if (ConstantInt *Op2C = dyn_cast<ConstantInt>(Operands[1])) {
 730         if (!strcmp(Str, "llvm.powi.f32")) {
 731           return ConstantFP::get(Ty, APFloat((float)std::pow((float)Op1V,
 732                                               (int)Op2C->getZExtValue())));
 733         } else if (!strcmp(Str, "llvm.powi.f64")) {
 734           return ConstantFP::get(Ty, APFloat((double)std::pow((double)Op1V,
 735                                               (int)Op2C->getZExtValue())));
 736         }
 737       }
 738     }
 739   }
 740   return 0;
 741 }
 742