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