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