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