LLVM  9.0.0svn
Evaluator.cpp
Go to the documentation of this file.
1 //===- Evaluator.cpp - LLVM IR evaluator ----------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Function evaluator for LLVM IR.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "llvm/ADT/DenseMap.h"
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/SmallPtrSet.h"
17 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/IR/BasicBlock.h"
20 #include "llvm/IR/CallSite.h"
21 #include "llvm/IR/Constant.h"
22 #include "llvm/IR/Constants.h"
23 #include "llvm/IR/DataLayout.h"
24 #include "llvm/IR/DerivedTypes.h"
25 #include "llvm/IR/Function.h"
26 #include "llvm/IR/GlobalAlias.h"
27 #include "llvm/IR/GlobalValue.h"
28 #include "llvm/IR/GlobalVariable.h"
29 #include "llvm/IR/InstrTypes.h"
30 #include "llvm/IR/Instruction.h"
31 #include "llvm/IR/Instructions.h"
32 #include "llvm/IR/IntrinsicInst.h"
33 #include "llvm/IR/Intrinsics.h"
34 #include "llvm/IR/Operator.h"
35 #include "llvm/IR/Type.h"
36 #include "llvm/IR/User.h"
37 #include "llvm/IR/Value.h"
38 #include "llvm/Support/Casting.h"
39 #include "llvm/Support/Debug.h"
41 #include <iterator>
42 
43 #define DEBUG_TYPE "evaluator"
44 
45 using namespace llvm;
46 
47 static inline bool
49  SmallPtrSetImpl<Constant *> &SimpleConstants,
50  const DataLayout &DL);
51 
52 /// Return true if the specified constant can be handled by the code generator.
53 /// We don't want to generate something like:
54 /// void *X = &X/42;
55 /// because the code generator doesn't have a relocation that can handle that.
56 ///
57 /// This function should be called if C was not found (but just got inserted)
58 /// in SimpleConstants to avoid having to rescan the same constants all the
59 /// time.
60 static bool
62  SmallPtrSetImpl<Constant *> &SimpleConstants,
63  const DataLayout &DL) {
64  // Simple global addresses are supported, do not allow dllimport or
65  // thread-local globals.
66  if (auto *GV = dyn_cast<GlobalValue>(C))
67  return !GV->hasDLLImportStorageClass() && !GV->isThreadLocal();
68 
69  // Simple integer, undef, constant aggregate zero, etc are all supported.
70  if (C->getNumOperands() == 0 || isa<BlockAddress>(C))
71  return true;
72 
73  // Aggregate values are safe if all their elements are.
74  if (isa<ConstantAggregate>(C)) {
75  for (Value *Op : C->operands())
76  if (!isSimpleEnoughValueToCommit(cast<Constant>(Op), SimpleConstants, DL))
77  return false;
78  return true;
79  }
80 
81  // We don't know exactly what relocations are allowed in constant expressions,
82  // so we allow &global+constantoffset, which is safe and uniformly supported
83  // across targets.
84  ConstantExpr *CE = cast<ConstantExpr>(C);
85  switch (CE->getOpcode()) {
86  case Instruction::BitCast:
87  // Bitcast is fine if the casted value is fine.
88  return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
89 
90  case Instruction::IntToPtr:
91  case Instruction::PtrToInt:
92  // int <=> ptr is fine if the int type is the same size as the
93  // pointer type.
94  if (DL.getTypeSizeInBits(CE->getType()) !=
95  DL.getTypeSizeInBits(CE->getOperand(0)->getType()))
96  return false;
97  return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
98 
99  // GEP is fine if it is simple + constant offset.
100  case Instruction::GetElementPtr:
101  for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
102  if (!isa<ConstantInt>(CE->getOperand(i)))
103  return false;
104  return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
105 
106  case Instruction::Add:
107  // We allow simple+cst.
108  if (!isa<ConstantInt>(CE->getOperand(1)))
109  return false;
110  return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
111  }
112  return false;
113 }
114 
115 static inline bool
117  SmallPtrSetImpl<Constant *> &SimpleConstants,
118  const DataLayout &DL) {
119  // If we already checked this constant, we win.
120  if (!SimpleConstants.insert(C).second)
121  return true;
122  // Check the constant.
123  return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, DL);
124 }
125 
126 /// Return true if this constant is simple enough for us to understand. In
127 /// particular, if it is a cast to anything other than from one pointer type to
128 /// another pointer type, we punt. We basically just support direct accesses to
129 /// globals and GEP's of globals. This should be kept up to date with
130 /// CommitValueTo.
132  // Conservatively, avoid aggregate types. This is because we don't
133  // want to worry about them partially overlapping other stores.
134  if (!cast<PointerType>(C->getType())->getElementType()->isSingleValueType())
135  return false;
136 
137  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C))
138  // Do not allow weak/*_odr/linkonce linkage or external globals.
139  return GV->hasUniqueInitializer();
140 
141  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
142  // Handle a constantexpr gep.
143  if (CE->getOpcode() == Instruction::GetElementPtr &&
144  isa<GlobalVariable>(CE->getOperand(0)) &&
145  cast<GEPOperator>(CE)->isInBounds()) {
146  GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
147  // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
148  // external globals.
149  if (!GV->hasUniqueInitializer())
150  return false;
151 
152  // The first index must be zero.
153  ConstantInt *CI = dyn_cast<ConstantInt>(*std::next(CE->op_begin()));
154  if (!CI || !CI->isZero()) return false;
155 
156  // The remaining indices must be compile-time known integers within the
157  // notional bounds of the corresponding static array types.
158  if (!CE->isGEPWithNoNotionalOverIndexing())
159  return false;
160 
162 
163  // A constantexpr bitcast from a pointer to another pointer is a no-op,
164  // and we know how to evaluate it by moving the bitcast from the pointer
165  // operand to the value operand.
166  } else if (CE->getOpcode() == Instruction::BitCast &&
167  isa<GlobalVariable>(CE->getOperand(0))) {
168  // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
169  // external globals.
170  return cast<GlobalVariable>(CE->getOperand(0))->hasUniqueInitializer();
171  }
172  }
173 
174  return false;
175 }
176 
177 /// Apply 'Func' to Ptr. If this returns nullptr, introspect the pointer's
178 /// type and walk down through the initial elements to obtain additional
179 /// pointers to try. Returns the first non-null return value from Func, or
180 /// nullptr if the type can't be introspected further.
181 static Constant *
183  const TargetLibraryInfo *TLI,
184  std::function<Constant *(Constant *)> Func) {
185  Constant *Val;
186  while (!(Val = Func(Ptr))) {
187  // If Ty is a struct, we can convert the pointer to the struct
188  // into a pointer to its first member.
189  // FIXME: This could be extended to support arrays as well.
190  Type *Ty = cast<PointerType>(Ptr->getType())->getElementType();
191  if (!isa<StructType>(Ty))
192  break;
193 
194  IntegerType *IdxTy = IntegerType::get(Ty->getContext(), 32);
195  Constant *IdxZero = ConstantInt::get(IdxTy, 0, false);
196  Constant *const IdxList[] = {IdxZero, IdxZero};
197 
198  Ptr = ConstantExpr::getGetElementPtr(Ty, Ptr, IdxList);
199  if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI))
200  Ptr = FoldedPtr;
201  }
202  return Val;
203 }
204 
206  auto *GV = dyn_cast<GlobalVariable>(C);
207  return GV && GV->hasDefinitiveInitializer() ? GV->getInitializer() : nullptr;
208 }
209 
210 /// Return the value that would be computed by a load from P after the stores
211 /// reflected by 'memory' have been performed. If we can't decide, return null.
212 Constant *Evaluator::ComputeLoadResult(Constant *P) {
213  // If this memory location has been recently stored, use the stored value: it
214  // is the most up-to-date.
215  auto findMemLoc = [this](Constant *Ptr) {
217  MutatedMemory.find(Ptr);
218  return I != MutatedMemory.end() ? I->second : nullptr;
219  };
220 
221  if (Constant *Val = findMemLoc(P))
222  return Val;
223 
224  // Access it.
225  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) {
226  if (GV->hasDefinitiveInitializer())
227  return GV->getInitializer();
228  return nullptr;
229  }
230 
231  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P)) {
232  switch (CE->getOpcode()) {
233  // Handle a constantexpr getelementptr.
234  case Instruction::GetElementPtr:
235  if (auto *I = getInitializer(CE->getOperand(0)))
237  break;
238  // Handle a constantexpr bitcast.
239  case Instruction::BitCast:
240  // We're evaluating a load through a pointer that was bitcast to a
241  // different type. See if the "from" pointer has recently been stored.
242  // If it hasn't, we may still be able to find a stored pointer by
243  // introspecting the type.
244  Constant *Val =
245  evaluateBitcastFromPtr(CE->getOperand(0), DL, TLI, findMemLoc);
246  if (!Val)
247  Val = getInitializer(CE->getOperand(0));
248  if (Val)
250  Val, P->getType()->getPointerElementType(), DL);
251  break;
252  }
253  }
254 
255  return nullptr; // don't know how to evaluate.
256 }
257 
259  if (auto *Fn = dyn_cast<Function>(C))
260  return Fn;
261 
262  if (auto *Alias = dyn_cast<GlobalAlias>(C))
263  if (auto *Fn = dyn_cast<Function>(Alias->getAliasee()))
264  return Fn;
265  return nullptr;
266 }
267 
268 Function *
270  SmallVector<Constant *, 8> &Formals) {
271  auto *V = CS.getCalledValue();
272  if (auto *Fn = getFunction(getVal(V)))
273  return getFormalParams(CS, Fn, Formals) ? Fn : nullptr;
274 
275  auto *CE = dyn_cast<ConstantExpr>(V);
276  if (!CE || CE->getOpcode() != Instruction::BitCast ||
277  !getFormalParams(CS, getFunction(CE->getOperand(0)), Formals))
278  return nullptr;
279 
280  return dyn_cast<Function>(
281  ConstantFoldLoadThroughBitcast(CE, CE->getOperand(0)->getType(), DL));
282 }
283 
285  SmallVector<Constant *, 8> &Formals) {
286  if (!F)
287  return false;
288 
289  auto *FTy = F->getFunctionType();
290  if (FTy->getNumParams() > CS.getNumArgOperands()) {
291  LLVM_DEBUG(dbgs() << "Too few arguments for function.\n");
292  return false;
293  }
294 
295  auto ArgI = CS.arg_begin();
296  for (auto ParI = FTy->param_begin(), ParE = FTy->param_end(); ParI != ParE;
297  ++ParI) {
298  auto *ArgC = ConstantFoldLoadThroughBitcast(getVal(*ArgI), *ParI, DL);
299  if (!ArgC) {
300  LLVM_DEBUG(dbgs() << "Can not convert function argument.\n");
301  return false;
302  }
303  Formals.push_back(ArgC);
304  ++ArgI;
305  }
306  return true;
307 }
308 
309 /// If call expression contains bitcast then we may need to cast
310 /// evaluated return value to a type of the call expression.
312  ConstantExpr *CE = dyn_cast<ConstantExpr>(CallExpr);
313  if (!RV || !CE || CE->getOpcode() != Instruction::BitCast)
314  return RV;
315 
316  if (auto *FT =
317  dyn_cast<FunctionType>(CE->getType()->getPointerElementType())) {
318  RV = ConstantFoldLoadThroughBitcast(RV, FT->getReturnType(), DL);
319  if (!RV)
320  LLVM_DEBUG(dbgs() << "Failed to fold bitcast call expr\n");
321  }
322  return RV;
323 }
324 
325 /// Evaluate all instructions in block BB, returning true if successful, false
326 /// if we can't evaluate it. NewBB returns the next BB that control flows into,
327 /// or null upon return.
329  BasicBlock *&NextBB) {
330  // This is the main evaluation loop.
331  while (true) {
332  Constant *InstResult = nullptr;
333 
334  LLVM_DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n");
335 
336  if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
337  if (!SI->isSimple()) {
338  LLVM_DEBUG(dbgs() << "Store is not simple! Can not evaluate.\n");
339  return false; // no volatile/atomic accesses.
340  }
341  Constant *Ptr = getVal(SI->getOperand(1));
342  if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI)) {
343  LLVM_DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr);
344  Ptr = FoldedPtr;
345  LLVM_DEBUG(dbgs() << "; To: " << *Ptr << "\n");
346  }
347  if (!isSimpleEnoughPointerToCommit(Ptr)) {
348  // If this is too complex for us to commit, reject it.
349  LLVM_DEBUG(
350  dbgs() << "Pointer is too complex for us to evaluate store.");
351  return false;
352  }
353 
354  Constant *Val = getVal(SI->getOperand(0));
355 
356  // If this might be too difficult for the backend to handle (e.g. the addr
357  // of one global variable divided by another) then we can't commit it.
358  if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) {
359  LLVM_DEBUG(dbgs() << "Store value is too complex to evaluate store. "
360  << *Val << "\n");
361  return false;
362  }
363 
364  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) {
365  if (CE->getOpcode() == Instruction::BitCast) {
366  LLVM_DEBUG(dbgs()
367  << "Attempting to resolve bitcast on constant ptr.\n");
368  // If we're evaluating a store through a bitcast, then we need
369  // to pull the bitcast off the pointer type and push it onto the
370  // stored value. In order to push the bitcast onto the stored value,
371  // a bitcast from the pointer's element type to Val's type must be
372  // legal. If it's not, we can try introspecting the type to find a
373  // legal conversion.
374 
375  auto castValTy = [&](Constant *P) -> Constant * {
376  Type *Ty = cast<PointerType>(P->getType())->getElementType();
377  if (Constant *FV = ConstantFoldLoadThroughBitcast(Val, Ty, DL)) {
378  Ptr = P;
379  return FV;
380  }
381  return nullptr;
382  };
383 
384  Constant *NewVal =
385  evaluateBitcastFromPtr(CE->getOperand(0), DL, TLI, castValTy);
386  if (!NewVal) {
387  LLVM_DEBUG(dbgs() << "Failed to bitcast constant ptr, can not "
388  "evaluate.\n");
389  return false;
390  }
391 
392  Val = NewVal;
393  LLVM_DEBUG(dbgs() << "Evaluated bitcast: " << *Val << "\n");
394  }
395  }
396 
397  MutatedMemory[Ptr] = Val;
398  } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) {
399  InstResult = ConstantExpr::get(BO->getOpcode(),
400  getVal(BO->getOperand(0)),
401  getVal(BO->getOperand(1)));
402  LLVM_DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: "
403  << *InstResult << "\n");
404  } else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) {
405  InstResult = ConstantExpr::getCompare(CI->getPredicate(),
406  getVal(CI->getOperand(0)),
407  getVal(CI->getOperand(1)));
408  LLVM_DEBUG(dbgs() << "Found a CmpInst! Simplifying: " << *InstResult
409  << "\n");
410  } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) {
411  InstResult = ConstantExpr::getCast(CI->getOpcode(),
412  getVal(CI->getOperand(0)),
413  CI->getType());
414  LLVM_DEBUG(dbgs() << "Found a Cast! Simplifying: " << *InstResult
415  << "\n");
416  } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) {
417  InstResult = ConstantExpr::getSelect(getVal(SI->getOperand(0)),
418  getVal(SI->getOperand(1)),
419  getVal(SI->getOperand(2)));
420  LLVM_DEBUG(dbgs() << "Found a Select! Simplifying: " << *InstResult
421  << "\n");
422  } else if (auto *EVI = dyn_cast<ExtractValueInst>(CurInst)) {
423  InstResult = ConstantExpr::getExtractValue(
424  getVal(EVI->getAggregateOperand()), EVI->getIndices());
425  LLVM_DEBUG(dbgs() << "Found an ExtractValueInst! Simplifying: "
426  << *InstResult << "\n");
427  } else if (auto *IVI = dyn_cast<InsertValueInst>(CurInst)) {
428  InstResult = ConstantExpr::getInsertValue(
429  getVal(IVI->getAggregateOperand()),
430  getVal(IVI->getInsertedValueOperand()), IVI->getIndices());
431  LLVM_DEBUG(dbgs() << "Found an InsertValueInst! Simplifying: "
432  << *InstResult << "\n");
433  } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) {
434  Constant *P = getVal(GEP->getOperand(0));
436  for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end();
437  i != e; ++i)
438  GEPOps.push_back(getVal(*i));
439  InstResult =
440  ConstantExpr::getGetElementPtr(GEP->getSourceElementType(), P, GEPOps,
441  cast<GEPOperator>(GEP)->isInBounds());
442  LLVM_DEBUG(dbgs() << "Found a GEP! Simplifying: " << *InstResult << "\n");
443  } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
444  if (!LI->isSimple()) {
445  LLVM_DEBUG(
446  dbgs() << "Found a Load! Not a simple load, can not evaluate.\n");
447  return false; // no volatile/atomic accesses.
448  }
449 
450  Constant *Ptr = getVal(LI->getOperand(0));
451  if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI)) {
452  Ptr = FoldedPtr;
453  LLVM_DEBUG(dbgs() << "Found a constant pointer expression, constant "
454  "folding: "
455  << *Ptr << "\n");
456  }
457  InstResult = ComputeLoadResult(Ptr);
458  if (!InstResult) {
459  LLVM_DEBUG(
460  dbgs() << "Failed to compute load result. Can not evaluate load."
461  "\n");
462  return false; // Could not evaluate load.
463  }
464 
465  LLVM_DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n");
466  } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) {
467  if (AI->isArrayAllocation()) {
468  LLVM_DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n");
469  return false; // Cannot handle array allocs.
470  }
471  Type *Ty = AI->getAllocatedType();
472  AllocaTmps.push_back(llvm::make_unique<GlobalVariable>(
474  AI->getName(), /*TLMode=*/GlobalValue::NotThreadLocal,
475  AI->getType()->getPointerAddressSpace()));
476  InstResult = AllocaTmps.back().get();
477  LLVM_DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n");
478  } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) {
479  CallSite CS(&*CurInst);
480 
481  // Debug info can safely be ignored here.
482  if (isa<DbgInfoIntrinsic>(CS.getInstruction())) {
483  LLVM_DEBUG(dbgs() << "Ignoring debug info.\n");
484  ++CurInst;
485  continue;
486  }
487 
488  // Cannot handle inline asm.
489  if (isa<InlineAsm>(CS.getCalledValue())) {
490  LLVM_DEBUG(dbgs() << "Found inline asm, can not evaluate.\n");
491  return false;
492  }
493 
494  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
495  if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) {
496  if (MSI->isVolatile()) {
497  LLVM_DEBUG(dbgs() << "Can not optimize a volatile memset "
498  << "intrinsic.\n");
499  return false;
500  }
501  Constant *Ptr = getVal(MSI->getDest());
502  Constant *Val = getVal(MSI->getValue());
503  Constant *DestVal = ComputeLoadResult(getVal(Ptr));
504  if (Val->isNullValue() && DestVal && DestVal->isNullValue()) {
505  // This memset is a no-op.
506  LLVM_DEBUG(dbgs() << "Ignoring no-op memset.\n");
507  ++CurInst;
508  continue;
509  }
510  }
511 
512  if (II->isLifetimeStartOrEnd()) {
513  LLVM_DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
514  ++CurInst;
515  continue;
516  }
517 
518  if (II->getIntrinsicID() == Intrinsic::invariant_start) {
519  // We don't insert an entry into Values, as it doesn't have a
520  // meaningful return value.
521  if (!II->use_empty()) {
522  LLVM_DEBUG(dbgs()
523  << "Found unused invariant_start. Can't evaluate.\n");
524  return false;
525  }
526  ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0));
527  Value *PtrArg = getVal(II->getArgOperand(1));
528  Value *Ptr = PtrArg->stripPointerCasts();
529  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
530  Type *ElemTy = GV->getValueType();
531  if (!Size->isMinusOne() &&
532  Size->getValue().getLimitedValue() >=
533  DL.getTypeStoreSize(ElemTy)) {
534  Invariants.insert(GV);
535  LLVM_DEBUG(dbgs() << "Found a global var that is an invariant: "
536  << *GV << "\n");
537  } else {
538  LLVM_DEBUG(dbgs()
539  << "Found a global var, but can not treat it as an "
540  "invariant.\n");
541  }
542  }
543  // Continue even if we do nothing.
544  ++CurInst;
545  continue;
546  } else if (II->getIntrinsicID() == Intrinsic::assume) {
547  LLVM_DEBUG(dbgs() << "Skipping assume intrinsic.\n");
548  ++CurInst;
549  continue;
550  } else if (II->getIntrinsicID() == Intrinsic::sideeffect) {
551  LLVM_DEBUG(dbgs() << "Skipping sideeffect intrinsic.\n");
552  ++CurInst;
553  continue;
554  }
555 
556  LLVM_DEBUG(dbgs() << "Unknown intrinsic. Can not evaluate.\n");
557  return false;
558  }
559 
560  // Resolve function pointers.
562  Function *Callee = getCalleeWithFormalArgs(CS, Formals);
563  if (!Callee || Callee->isInterposable()) {
564  LLVM_DEBUG(dbgs() << "Can not resolve function pointer.\n");
565  return false; // Cannot resolve.
566  }
567 
568  if (Callee->isDeclaration()) {
569  // If this is a function we can constant fold, do it.
570  if (Constant *C = ConstantFoldCall(cast<CallBase>(CS.getInstruction()),
571  Callee, Formals, TLI)) {
572  InstResult = castCallResultIfNeeded(CS.getCalledValue(), C);
573  if (!InstResult)
574  return false;
575  LLVM_DEBUG(dbgs() << "Constant folded function call. Result: "
576  << *InstResult << "\n");
577  } else {
578  LLVM_DEBUG(dbgs() << "Can not constant fold function call.\n");
579  return false;
580  }
581  } else {
582  if (Callee->getFunctionType()->isVarArg()) {
583  LLVM_DEBUG(dbgs() << "Can not constant fold vararg function call.\n");
584  return false;
585  }
586 
587  Constant *RetVal = nullptr;
588  // Execute the call, if successful, use the return value.
589  ValueStack.emplace_back();
590  if (!EvaluateFunction(Callee, RetVal, Formals)) {
591  LLVM_DEBUG(dbgs() << "Failed to evaluate function.\n");
592  return false;
593  }
594  ValueStack.pop_back();
595  InstResult = castCallResultIfNeeded(CS.getCalledValue(), RetVal);
596  if (RetVal && !InstResult)
597  return false;
598 
599  if (InstResult) {
600  LLVM_DEBUG(dbgs() << "Successfully evaluated function. Result: "
601  << *InstResult << "\n\n");
602  } else {
603  LLVM_DEBUG(dbgs()
604  << "Successfully evaluated function. Result: 0\n\n");
605  }
606  }
607  } else if (CurInst->isTerminator()) {
608  LLVM_DEBUG(dbgs() << "Found a terminator instruction.\n");
609 
610  if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
611  if (BI->isUnconditional()) {
612  NextBB = BI->getSuccessor(0);
613  } else {
614  ConstantInt *Cond =
615  dyn_cast<ConstantInt>(getVal(BI->getCondition()));
616  if (!Cond) return false; // Cannot determine.
617 
618  NextBB = BI->getSuccessor(!Cond->getZExtValue());
619  }
620  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
621  ConstantInt *Val =
622  dyn_cast<ConstantInt>(getVal(SI->getCondition()));
623  if (!Val) return false; // Cannot determine.
624  NextBB = SI->findCaseValue(Val)->getCaseSuccessor();
625  } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
626  Value *Val = getVal(IBI->getAddress())->stripPointerCasts();
627  if (BlockAddress *BA = dyn_cast<BlockAddress>(Val))
628  NextBB = BA->getBasicBlock();
629  else
630  return false; // Cannot determine.
631  } else if (isa<ReturnInst>(CurInst)) {
632  NextBB = nullptr;
633  } else {
634  // invoke, unwind, resume, unreachable.
635  LLVM_DEBUG(dbgs() << "Can not handle terminator.");
636  return false; // Cannot handle this terminator.
637  }
638 
639  // We succeeded at evaluating this block!
640  LLVM_DEBUG(dbgs() << "Successfully evaluated block.\n");
641  return true;
642  } else {
643  // Did not know how to evaluate this!
644  LLVM_DEBUG(
645  dbgs() << "Failed to evaluate block due to unhandled instruction."
646  "\n");
647  return false;
648  }
649 
650  if (!CurInst->use_empty()) {
651  if (auto *FoldedInstResult = ConstantFoldConstant(InstResult, DL, TLI))
652  InstResult = FoldedInstResult;
653 
654  setVal(&*CurInst, InstResult);
655  }
656 
657  // If we just processed an invoke, we finished evaluating the block.
658  if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
659  NextBB = II->getNormalDest();
660  LLVM_DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");
661  return true;
662  }
663 
664  // Advance program counter.
665  ++CurInst;
666  }
667 }
668 
669 /// Evaluate a call to function F, returning true if successful, false if we
670 /// can't evaluate it. ActualArgs contains the formal arguments for the
671 /// function.
673  const SmallVectorImpl<Constant*> &ActualArgs) {
674  // Check to see if this function is already executing (recursion). If so,
675  // bail out. TODO: we might want to accept limited recursion.
676  if (is_contained(CallStack, F))
677  return false;
678 
679  CallStack.push_back(F);
680 
681  // Initialize arguments to the incoming values specified.
682  unsigned ArgNo = 0;
683  for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
684  ++AI, ++ArgNo)
685  setVal(&*AI, ActualArgs[ArgNo]);
686 
687  // ExecutedBlocks - We only handle non-looping, non-recursive code. As such,
688  // we can only evaluate any one basic block at most once. This set keeps
689  // track of what we have executed so we can detect recursive cases etc.
690  SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
691 
692  // CurBB - The current basic block we're evaluating.
693  BasicBlock *CurBB = &F->front();
694 
695  BasicBlock::iterator CurInst = CurBB->begin();
696 
697  while (true) {
698  BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
699  LLVM_DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
700 
701  if (!EvaluateBlock(CurInst, NextBB))
702  return false;
703 
704  if (!NextBB) {
705  // Successfully running until there's no next block means that we found
706  // the return. Fill it the return value and pop the call stack.
707  ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator());
708  if (RI->getNumOperands())
709  RetVal = getVal(RI->getOperand(0));
710  CallStack.pop_back();
711  return true;
712  }
713 
714  // Okay, we succeeded in evaluating this control flow. See if we have
715  // executed the new block before. If so, we have a looping function,
716  // which we cannot evaluate in reasonable time.
717  if (!ExecutedBlocks.insert(NextBB).second)
718  return false; // looped!
719 
720  // Okay, we have never been in this block before. Check to see if there
721  // are any PHI nodes. If so, evaluate them with information about where
722  // we came from.
723  PHINode *PN = nullptr;
724  for (CurInst = NextBB->begin();
725  (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)
726  setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB)));
727 
728  // Advance to the next block.
729  CurBB = NextBB;
730  }
731 }
uint64_t CallInst * C
Return a value (possibly void), from a function.
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:722
bool hasDefinitiveInitializer() const
hasDefinitiveInitializer - Whether the global variable has an initializer, and any other instances of...
unsigned getOpcode() const
Return the opcode at the root of this constant expression.
Definition: Constants.h:1209
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
IterTy arg_begin() const
Definition: CallSite.h:584
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Constant * ConstantFoldLoadThroughGEPConstantExpr(Constant *C, ConstantExpr *CE)
ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a getelementptr constantexpr, return the constant value being addressed by the constant expression, or null if something is funny and we can&#39;t decide.
static Constant * getGetElementPtr(Type *Ty, Constant *C, ArrayRef< Constant *> IdxList, bool InBounds=false, Optional< unsigned > InRangeIndex=None, Type *OnlyIfReducedTy=nullptr)
Getelementptr form.
Definition: Constants.h:1153
Constant * ConstantFoldCall(const CallBase *Call, Function *F, ArrayRef< Constant *> Operands, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldCall - Attempt to constant fold a call to the specified function with the specified argum...
bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB)
Evaluate all instructions in block BB, returning true if successful, false if we can&#39;t evaluate it...
Definition: Evaluator.cpp:328
bool getFormalParams(CallSite &CS, Function *F, SmallVector< Constant *, 8 > &Formals)
Given call site and callee returns list of callee formal argument values converting them when necessa...
Definition: Evaluator.cpp:284
bool isInterposable() const
Return true if this global&#39;s definition can be substituted with an arbitrary definition at link time...
Definition: GlobalValue.h:429
This class wraps the llvm.memset intrinsic.
arg_iterator arg_end()
Definition: Function.h:704
F(f)
An instruction for reading from memory.
Definition: Instructions.h:167
static Constant * getCompare(unsigned short pred, Constant *C1, Constant *C2, bool OnlyIfReduced=false)
Return an ICmp or FCmp comparison operator constant expression.
Definition: Constants.cpp:1946
Hexagon Common GEP
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
bool EvaluateFunction(Function *F, Constant *&RetVal, const SmallVectorImpl< Constant *> &ActualArgs)
Evaluate a call to function F, returning true if successful, false if we can&#39;t evaluate it...
Definition: Evaluator.cpp:672
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:129
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
The address of a basic block.
Definition: Constants.h:839
This class represents the LLVM &#39;select&#39; instruction.
Type * getPointerElementType() const
Definition: Type.h:376
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:439
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
ValTy * getCalledValue() const
Return the pointer to function that is being called.
Definition: CallSite.h:104
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
InstrTy * getInstruction() const
Definition: CallSite.h:96
Constant * ConstantFoldConstant(const Constant *C, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldConstant - Attempt to fold the constant using the specified DataLayout.
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:888
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
static Constant * evaluateBitcastFromPtr(Constant *Ptr, const DataLayout &DL, const TargetLibraryInfo *TLI, std::function< Constant *(Constant *)> Func)
Apply &#39;Func&#39; to Ptr.
Definition: Evaluator.cpp:182
static Constant * getSelect(Constant *C, Constant *V1, Constant *V2, Type *OnlyIfReducedTy=nullptr)
Select constant expr.
Definition: Constants.cpp:1968
bool isVarArg() const
Definition: DerivedTypes.h:123
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:137
An instruction for storing to memory.
Definition: Instructions.h:320
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
Definition: Constants.h:208
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:258
Value * getOperand(unsigned i) const
Definition: User.h:169
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:875
static Constant * getInsertValue(Constant *Agg, Constant *Val, ArrayRef< unsigned > Idxs, Type *OnlyIfReducedTy=nullptr)
Definition: Constants.cpp:2161
#define P(N)
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:148
unsigned getNumArgOperands() const
Definition: CallSite.h:303
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
Conditional or Unconditional Branch instruction.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:41
void setVal(Value *V, Constant *C)
Definition: Evaluator.h:72
Value * getIncomingValueForBlock(const BasicBlock *BB) const
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Indirect Branch Instruction.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
bool hasUniqueInitializer() const
hasUniqueInitializer - Whether the global variable has an initializer, and any changes made to the in...
static bool isSimpleEnoughValueToCommit(Constant *C, SmallPtrSetImpl< Constant *> &SimpleConstants, const DataLayout &DL)
Definition: Evaluator.cpp:116
static bool isSimpleEnoughValueToCommitHelper(Constant *C, SmallPtrSetImpl< Constant *> &SimpleConstants, const DataLayout &DL)
Return true if the specified constant can be handled by the code generator.
Definition: Evaluator.cpp:61
op_range operands()
Definition: User.h:237
arg_iterator arg_begin()
Definition: Function.h:695
Class to represent integer types.
Definition: DerivedTypes.h:40
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1424
const Constant * stripPointerCasts() const
Definition: Constant.h:177
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:239
unsigned getNumOperands() const
Definition: User.h:191
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
Constant * getVal(Value *V)
Definition: Evaluator.h:65
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Provides information about what library functions are available for the current target.
static Constant * getInitializer(Constant *C)
Definition: Evaluator.cpp:205
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:631
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Definition: Function.h:163
amdgpu Simplify well known AMD library false FunctionCallee Callee
static bool isSimpleEnoughPointerToCommit(Constant *C)
Return true if this constant is simple enough for us to understand.
Definition: Evaluator.cpp:131
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:89
static Constant * getCast(unsigned ops, Constant *C, Type *Ty, bool OnlyIfReduced=false)
Convenience function for getting a Cast operation.
Definition: Constants.cpp:1539
uint64_t getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:601
Function * getCalleeWithFormalArgs(CallSite &CS, SmallVector< Constant *, 8 > &Formals)
Given call site return callee and list of its formal arguments.
Definition: Evaluator.cpp:269
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value...
Definition: APInt.h:481
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
#define I(x, y, z)
Definition: MD5.cpp:58
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:192
Constant * castCallResultIfNeeded(Value *CallExpr, Constant *RV)
Casts call result to a type of bitcast call expression.
Definition: Evaluator.cpp:311
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
uint32_t Size
Definition: Profile.cpp:46
Rename collisions when linking (static functions).
Definition: GlobalValue.h:55
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:227
Multiway switch.
const BasicBlock & front() const
Definition: Function.h:687
LLVM Value Representation.
Definition: Value.h:72
uint64_t getTypeStoreSize(Type *Ty) const
Returns the maximum number of bytes that may be overwritten by storing the specified type...
Definition: DataLayout.h:444
Constant * ConstantFoldLoadThroughBitcast(Constant *C, Type *DestTy, const DataLayout &DL)
ConstantFoldLoadThroughBitcast - try to cast constant to destination type returning null if unsuccess...
Invoke instruction.
print Print MemDeps of function
static Constant * getExtractValue(Constant *Agg, ArrayRef< unsigned > Idxs, Type *OnlyIfReducedTy=nullptr)
Definition: Constants.cpp:2185
#define LLVM_DEBUG(X)
Definition: Debug.h:122
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:43
an instruction to allocate memory on the stack
Definition: Instructions.h:59
static Constant * get(unsigned Opcode, Constant *C1, unsigned Flags=0, Type *OnlyIfReducedTy=nullptr)
get - Return a unary operator constant expression, folding if possible.
Definition: Constants.cpp:1815
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1251