ConstantFolding.cpp revision 5520732b24a5a321140dd79af70d321c7ff3dec9 
1//===-- ConstantFolding.cpp - Analyze constant folding possibilities ------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by the LLVM research group and is distributed under
6// the University of Illinois Open Source License. See LICENSE.TXT for details.
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/Support/GetElementPtrTypeIterator.h"
23#include "llvm/Support/MathExtras.h"
24#include <cerrno>
25#include <cmath>
26using namespace llvm;
27
28/// ConstantFoldInstruction - Attempt to constant fold the specified
29/// instruction.  If successful, the constant result is returned, if not, null
30/// is returned.  Note that this function can only fail when attempting to fold
31/// instructions like loads and stores, which have no constant expression form.
32///
33Constant *llvm::ConstantFoldInstruction(Instruction *I, const TargetData *TD) {
34  if (PHINode *PN = dyn_cast<PHINode>(I)) {
35    if (PN->getNumIncomingValues() == 0)
36      return Constant::getNullValue(PN->getType());
37
38    Constant *Result = dyn_cast<Constant>(PN->getIncomingValue(0));
39    if (Result == 0) return 0;
40
41    // Handle PHI nodes specially here...
42    for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i)
43      if (PN->getIncomingValue(i) != Result && PN->getIncomingValue(i) != PN)
44        return 0;   // Not all the same incoming constants...
45
46    // If we reach here, all incoming values are the same constant.
47    return Result;
48  }
49
50  // Scan the operand list, checking to see if they are all constants, if so,
51  // hand off to ConstantFoldInstOperands.
52  SmallVector<Constant*, 8> Ops;
53  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
54    if (Constant *Op = dyn_cast<Constant>(I->getOperand(i)))
55      Ops.push_back(Op);
56    else
57      return 0;  // All operands not constant!
58
59  return ConstantFoldInstOperands(I, &Ops[0], Ops.size());
60}
61
62/// ConstantFoldInstOperands - Attempt to constant fold an instruction with the
63/// specified opcode and operands.  If successful, the constant result is
64/// returned, if not, null is returned.  Note that this function can fail when
65/// attempting to fold instructions like loads and stores, which have no
66/// constant expression form.
67///
68Constant *llvm::ConstantFoldInstOperands(const Instruction* I,
69                                         Constant** Ops, unsigned NumOps,
70                                         const TargetData *TD) {
71  unsigned Opc = I->getOpcode();
72  const Type *DestTy = I->getType();
73
74  // Handle easy binops first
75  if (isa<BinaryOperator>(I))
76    return ConstantExpr::get(Opc, Ops[0], Ops[1]);
77
78  switch (Opc) {
79  default: return 0;
80  case Instruction::Call:
81    if (Function *F = dyn_cast<Function>(Ops[0]))
82      if (canConstantFoldCallTo(F))
83        return ConstantFoldCall(F, Ops+1, NumOps);
84    return 0;
85  case Instruction::ICmp:
86  case Instruction::FCmp:
87    return ConstantExpr::getCompare(cast<CmpInst>(I)->getPredicate(), Ops[0],
88                                    Ops[1]);
89  case Instruction::Shl:
90  case Instruction::LShr:
91  case Instruction::AShr:
92    return ConstantExpr::get(Opc, Ops[0], Ops[1]);
93  case Instruction::Trunc:
94  case Instruction::ZExt:
95  case Instruction::SExt:
96  case Instruction::FPTrunc:
97  case Instruction::FPExt:
98  case Instruction::UIToFP:
99  case Instruction::SIToFP:
100  case Instruction::FPToUI:
101  case Instruction::FPToSI:
102  case Instruction::PtrToInt:
103  case Instruction::IntToPtr:
104  case Instruction::BitCast:
105    return ConstantExpr::getCast(Opc, Ops[0], DestTy);
106  case Instruction::Select:
107    return ConstantExpr::getSelect(Ops[0], Ops[1], Ops[2]);
108  case Instruction::ExtractElement:
109    return ConstantExpr::getExtractElement(Ops[0], Ops[1]);
110  case Instruction::InsertElement:
111    return ConstantExpr::getInsertElement(Ops[0], Ops[1], Ops[2]);
112  case Instruction::ShuffleVector:
113    return ConstantExpr::getShuffleVector(Ops[0], Ops[1], Ops[2]);
114  case Instruction::GetElementPtr:
115    return ConstantExpr::getGetElementPtr(Ops[0],
116                                          std::vector<Constant*>(Ops+1,
117                                                                 Ops+NumOps));
118  }
119}
120
121/// ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a
122/// getelementptr constantexpr, return the constant value being addressed by the
123/// constant expression, or null if something is funny and we can't decide.
124Constant *llvm::ConstantFoldLoadThroughGEPConstantExpr(Constant *C,
125                                                       ConstantExpr *CE) {
126  if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType()))
127    return 0;  // Do not allow stepping over the value!
128
129  // Loop over all of the operands, tracking down which value we are
130  // addressing...
131  gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
132  for (++I; I != E; ++I)
133    if (const StructType *STy = dyn_cast<StructType>(*I)) {
134      ConstantInt *CU = cast<ConstantInt>(I.getOperand());
135      assert(CU->getZExtValue() < STy->getNumElements() &&
136             "Struct index out of range!");
137      unsigned El = (unsigned)CU->getZExtValue();
138      if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
139        C = CS->getOperand(El);
140      } else if (isa<ConstantAggregateZero>(C)) {
141        C = Constant::getNullValue(STy->getElementType(El));
142      } else if (isa<UndefValue>(C)) {
143        C = UndefValue::get(STy->getElementType(El));
144      } else {
145        return 0;
146      }
147    } else if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) {
148      if (const ArrayType *ATy = dyn_cast<ArrayType>(*I)) {
149        if (CI->getZExtValue() >= ATy->getNumElements())
150         return 0;
151        if (ConstantArray *CA = dyn_cast<ConstantArray>(C))
152          C = CA->getOperand(CI->getZExtValue());
153        else if (isa<ConstantAggregateZero>(C))
154          C = Constant::getNullValue(ATy->getElementType());
155        else if (isa<UndefValue>(C))
156          C = UndefValue::get(ATy->getElementType());
157        else
158          return 0;
159      } else if (const PackedType *PTy = dyn_cast<PackedType>(*I)) {
160        if (CI->getZExtValue() >= PTy->getNumElements())
161          return 0;
162        if (ConstantPacked *CP = dyn_cast<ConstantPacked>(C))
163          C = CP->getOperand(CI->getZExtValue());
164        else if (isa<ConstantAggregateZero>(C))
165          C = Constant::getNullValue(PTy->getElementType());
166        else if (isa<UndefValue>(C))
167          C = UndefValue::get(PTy->getElementType());
168        else
169          return 0;
170      } else {
171        return 0;
172      }
173    } else {
174      return 0;
175    }
176  return C;
177}
178
179
180//===----------------------------------------------------------------------===//
181//  Constant Folding for Calls
182//
183
184/// canConstantFoldCallTo - Return true if its even possible to fold a call to
185/// the specified function.
186bool
187llvm::canConstantFoldCallTo(Function *F) {
188  const std::string &Name = F->getName();
189
190  switch (F->getIntrinsicID()) {
191  case Intrinsic::sqrt_f32:
192  case Intrinsic::sqrt_f64:
193  case Intrinsic::bswap_i16:
194  case Intrinsic::bswap_i32:
195  case Intrinsic::bswap_i64:
196  case Intrinsic::powi_f32:
197  case Intrinsic::powi_f64:
198  // FIXME: these should be constant folded as well
199  //case Intrinsic::ctpop_i8:
200  //case Intrinsic::ctpop_i16:
201  //case Intrinsic::ctpop_i32:
202  //case Intrinsic::ctpop_i64:
203  //case Intrinsic::ctlz_i8:
204  //case Intrinsic::ctlz_i16:
205  //case Intrinsic::ctlz_i32:
206  //case Intrinsic::ctlz_i64:
207  //case Intrinsic::cttz_i8:
208  //case Intrinsic::cttz_i16:
209  //case Intrinsic::cttz_i32:
210  //case Intrinsic::cttz_i64:
211    return true;
212  default: break;
213  }
214
215  switch (Name[0])
216  {
217    case 'a':
218      return Name == "acos" || Name == "asin" || Name == "atan" ||
219             Name == "atan2";
220    case 'c':
221      return Name == "ceil" || Name == "cos" || Name == "cosf" ||
222             Name == "cosh";
223    case 'e':
224      return Name == "exp";
225    case 'f':
226      return Name == "fabs" || Name == "fmod" || Name == "floor";
227    case 'l':
228      return Name == "log" || Name == "log10";
229    case 'p':
230      return Name == "pow";
231    case 's':
232      return Name == "sin" || Name == "sinh" ||
233             Name == "sqrt" || Name == "sqrtf";
234    case 't':
235      return Name == "tan" || Name == "tanh";
236    default:
237      return false;
238  }
239}
240
241static Constant *ConstantFoldFP(double (*NativeFP)(double), double V,
242                                const Type *Ty) {
243  errno = 0;
244  V = NativeFP(V);
245  if (errno == 0)
246    return ConstantFP::get(Ty, V);
247  errno = 0;
248  return 0;
249}
250
251/// ConstantFoldCall - Attempt to constant fold a call to the specified function
252/// with the specified arguments, returning null if unsuccessful.
253Constant *
254llvm::ConstantFoldCall(Function *F, Constant** Operands, unsigned NumOperands) {
255  const std::string &Name = F->getName();
256  const Type *Ty = F->getReturnType();
257
258  if (NumOperands == 1) {
259    if (ConstantFP *Op = dyn_cast<ConstantFP>(Operands[0])) {
260      double V = Op->getValue();
261      switch (Name[0])
262      {
263        case 'a':
264          if (Name == "acos")
265            return ConstantFoldFP(acos, V, Ty);
266          else if (Name == "asin")
267            return ConstantFoldFP(asin, V, Ty);
268          else if (Name == "atan")
269            return ConstantFP::get(Ty, atan(V));
270          break;
271        case 'c':
272          if (Name == "ceil")
273            return ConstantFoldFP(ceil, V, Ty);
274          else if (Name == "cos")
275            return ConstantFP::get(Ty, cos(V));
276          else if (Name == "cosh")
277            return ConstantFP::get(Ty, cosh(V));
278          break;
279        case 'e':
280          if (Name == "exp")
281            return ConstantFP::get(Ty, exp(V));
282          break;
283        case 'f':
284          if (Name == "fabs")
285            return ConstantFP::get(Ty, fabs(V));
286          else if (Name == "floor")
287            return ConstantFoldFP(floor, V, Ty);
288          break;
289        case 'l':
290          if (Name == "log" && V > 0)
291            return ConstantFP::get(Ty, log(V));
292          else if (Name == "log10" && V > 0)
293            return ConstantFoldFP(log10, V, Ty);
294          else if (Name == "llvm.sqrt.f32" || Name == "llvm.sqrt.f64") {
295            if (V >= -0.0)
296              return ConstantFP::get(Ty, sqrt(V));
297            else // Undefined
298              return ConstantFP::get(Ty, 0.0);
299          }
300          break;
301        case 's':
302          if (Name == "sin")
303            return ConstantFP::get(Ty, sin(V));
304          else if (Name == "sinh")
305            return ConstantFP::get(Ty, sinh(V));
306          else if (Name == "sqrt" && V >= 0)
307            return ConstantFP::get(Ty, sqrt(V));
308          else if (Name == "sqrtf" && V >= 0)
309            return ConstantFP::get(Ty, sqrt((float)V));
310          break;
311        case 't':
312          if (Name == "tan")
313            return ConstantFP::get(Ty, tan(V));
314          else if (Name == "tanh")
315            return ConstantFP::get(Ty, tanh(V));
316          break;
317        default:
318          break;
319      }
320    } else if (ConstantInt *Op = dyn_cast<ConstantInt>(Operands[0])) {
321      uint64_t V = Op->getZExtValue();
322      if (Name == "llvm.bswap.i16")
323        return ConstantInt::get(Ty, ByteSwap_16(V));
324      else if (Name == "llvm.bswap.i32")
325        return ConstantInt::get(Ty, ByteSwap_32(V));
326      else if (Name == "llvm.bswap.i64")
327        return ConstantInt::get(Ty, ByteSwap_64(V));
328    }
329  } else if (NumOperands == 2) {
330    if (ConstantFP *Op1 = dyn_cast<ConstantFP>(Operands[0])) {
331      double Op1V = Op1->getValue();
332      if (ConstantFP *Op2 = dyn_cast<ConstantFP>(Operands[1])) {
333        double Op2V = Op2->getValue();
334
335        if (Name == "pow") {
336          errno = 0;
337          double V = pow(Op1V, Op2V);
338          if (errno == 0)
339            return ConstantFP::get(Ty, V);
340        } else if (Name == "fmod") {
341          errno = 0;
342          double V = fmod(Op1V, Op2V);
343          if (errno == 0)
344            return ConstantFP::get(Ty, V);
345        } else if (Name == "atan2") {
346          return ConstantFP::get(Ty, atan2(Op1V,Op2V));
347        }
348      } else if (ConstantInt *Op2C = dyn_cast<ConstantInt>(Operands[1])) {
349        if (Name == "llvm.powi.f32") {
350          return ConstantFP::get(Ty, std::pow((float)Op1V,
351                                              (int)Op2C->getZExtValue()));
352        } else if (Name == "llvm.powi.f64") {
353          return ConstantFP::get(Ty, std::pow((double)Op1V,
354                                              (int)Op2C->getZExtValue()));
355        }
356      }
357    }
358  }
359  return 0;
360}
361
362