LLVM  14.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  GV->getInitializer(), CE,
162  cast<GEPOperator>(CE)->getResultElementType(), DL);
163  } else if (CE->getOpcode() == Instruction::BitCast &&
164  isa<GlobalVariable>(CE->getOperand(0))) {
165  // A constantexpr bitcast from a pointer to another pointer is a no-op,
166  // and we know how to evaluate it by moving the bitcast from the pointer
167  // operand to the value operand.
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 \p TryLoad to Ptr. If this returns \p nullptr, introspect the
178 /// pointer's type and walk down through the initial elements to obtain
179 /// additional pointers to try. Returns the first non-null return value from
180 /// \p TryLoad, or \p nullptr if the type can't be introspected further.
181 static Constant *
183  const TargetLibraryInfo *TLI,
184  std::function<Constant *(Constant *)> TryLoad) {
185  Constant *Val;
186  while (!(Val = TryLoad(Ptr))) {
187  // If Ty is a non-opaque 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) || cast<StructType>(Ty)->isOpaque())
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  Ptr = ConstantFoldConstant(Ptr, DL, TLI);
200  }
201  return Val;
202 }
203 
205  auto *GV = dyn_cast<GlobalVariable>(C);
206  return GV && GV->hasDefinitiveInitializer() ? GV->getInitializer() : nullptr;
207 }
208 
209 /// Return the value that would be computed by a load from P after the stores
210 /// reflected by 'memory' have been performed. If we can't decide, return null.
211 Constant *Evaluator::ComputeLoadResult(Constant *P, Type *Ty) {
212  // If this memory location has been recently stored, use the stored value: it
213  // is the most up-to-date.
214  auto TryFindMemLoc = [this](Constant *Ptr) {
215  return MutatedMemory.lookup(Ptr);
216  };
217 
218  if (Constant *Val = TryFindMemLoc(P))
219  return Val;
220 
221  // Access it.
222  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) {
223  if (GV->hasDefinitiveInitializer())
224  return GV->getInitializer();
225  return nullptr;
226  }
227 
228  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P)) {
229  switch (CE->getOpcode()) {
230  // Handle a constantexpr getelementptr.
231  case Instruction::GetElementPtr:
232  if (auto *I = getInitializer(CE->getOperand(0)))
233  return ConstantFoldLoadThroughGEPConstantExpr(I, CE, Ty, DL);
234  break;
235  // Handle a constantexpr bitcast.
236  case Instruction::BitCast:
237  // We're evaluating a load through a pointer that was bitcast to a
238  // different type. See if the "from" pointer has recently been stored.
239  // If it hasn't, we may still be able to find a stored pointer by
240  // introspecting the type.
241  Constant *Val =
242  evaluateBitcastFromPtr(CE->getOperand(0), DL, TLI, TryFindMemLoc);
243  if (!Val)
244  Val = getInitializer(CE->getOperand(0));
245  if (Val)
247  Val, P->getType()->getPointerElementType(), DL);
248  break;
249  }
250  }
251 
252  return nullptr; // don't know how to evaluate.
253 }
254 
256  if (auto *Fn = dyn_cast<Function>(C))
257  return Fn;
258 
259  if (auto *Alias = dyn_cast<GlobalAlias>(C))
260  if (auto *Fn = dyn_cast<Function>(Alias->getAliasee()))
261  return Fn;
262  return nullptr;
263 }
264 
265 Function *
266 Evaluator::getCalleeWithFormalArgs(CallBase &CB,
267  SmallVectorImpl<Constant *> &Formals) {
268  auto *V = CB.getCalledOperand();
269  if (auto *Fn = getFunction(getVal(V)))
270  return getFormalParams(CB, Fn, Formals) ? Fn : nullptr;
271 
272  auto *CE = dyn_cast<ConstantExpr>(V);
273  if (!CE || CE->getOpcode() != Instruction::BitCast ||
274  !getFormalParams(CB, getFunction(CE->getOperand(0)), Formals))
275  return nullptr;
276 
277  return dyn_cast<Function>(
278  ConstantFoldLoadThroughBitcast(CE, CE->getOperand(0)->getType(), DL));
279 }
280 
281 bool Evaluator::getFormalParams(CallBase &CB, Function *F,
282  SmallVectorImpl<Constant *> &Formals) {
283  if (!F)
284  return false;
285 
286  auto *FTy = F->getFunctionType();
287  if (FTy->getNumParams() > CB.getNumArgOperands()) {
288  LLVM_DEBUG(dbgs() << "Too few arguments for function.\n");
289  return false;
290  }
291 
292  auto ArgI = CB.arg_begin();
293  for (auto ParI = FTy->param_begin(), ParE = FTy->param_end(); ParI != ParE;
294  ++ParI) {
295  auto *ArgC = ConstantFoldLoadThroughBitcast(getVal(*ArgI), *ParI, DL);
296  if (!ArgC) {
297  LLVM_DEBUG(dbgs() << "Can not convert function argument.\n");
298  return false;
299  }
300  Formals.push_back(ArgC);
301  ++ArgI;
302  }
303  return true;
304 }
305 
306 /// If call expression contains bitcast then we may need to cast
307 /// evaluated return value to a type of the call expression.
308 Constant *Evaluator::castCallResultIfNeeded(Value *CallExpr, Constant *RV) {
309  ConstantExpr *CE = dyn_cast<ConstantExpr>(CallExpr);
310  if (!RV || !CE || CE->getOpcode() != Instruction::BitCast)
311  return RV;
312 
313  if (auto *FT =
314  dyn_cast<FunctionType>(CE->getType()->getPointerElementType())) {
315  RV = ConstantFoldLoadThroughBitcast(RV, FT->getReturnType(), DL);
316  if (!RV)
317  LLVM_DEBUG(dbgs() << "Failed to fold bitcast call expr\n");
318  }
319  return RV;
320 }
321 
322 /// Evaluate all instructions in block BB, returning true if successful, false
323 /// if we can't evaluate it. NewBB returns the next BB that control flows into,
324 /// or null upon return. StrippedPointerCastsForAliasAnalysis is set to true if
325 /// we looked through pointer casts to evaluate something.
326 bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB,
327  bool &StrippedPointerCastsForAliasAnalysis) {
328  // This is the main evaluation loop.
329  while (true) {
330  Constant *InstResult = nullptr;
331 
332  LLVM_DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n");
333 
334  if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
335  if (!SI->isSimple()) {
336  LLVM_DEBUG(dbgs() << "Store is not simple! Can not evaluate.\n");
337  return false; // no volatile/atomic accesses.
338  }
339  Constant *Ptr = getVal(SI->getOperand(1));
340  Constant *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI);
341  if (Ptr != FoldedPtr) {
342  LLVM_DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr);
343  Ptr = FoldedPtr;
344  LLVM_DEBUG(dbgs() << "; To: " << *Ptr << "\n");
345  }
346  if (!isSimpleEnoughPointerToCommit(Ptr, DL)) {
347  // If this is too complex for us to commit, reject it.
348  LLVM_DEBUG(
349  dbgs() << "Pointer is too complex for us to evaluate store.");
350  return false;
351  }
352 
353  Constant *Val = getVal(SI->getOperand(0));
354 
355  // If this might be too difficult for the backend to handle (e.g. the addr
356  // of one global variable divided by another) then we can't commit it.
357  if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) {
358  LLVM_DEBUG(dbgs() << "Store value is too complex to evaluate store. "
359  << *Val << "\n");
360  return false;
361  }
362 
363  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) {
364  if (CE->getOpcode() == Instruction::BitCast) {
365  LLVM_DEBUG(dbgs()
366  << "Attempting to resolve bitcast on constant ptr.\n");
367  // If we're evaluating a store through a bitcast, then we need
368  // to pull the bitcast off the pointer type and push it onto the
369  // stored value. In order to push the bitcast onto the stored value,
370  // a bitcast from the pointer's element type to Val's type must be
371  // legal. If it's not, we can try introspecting the type to find a
372  // legal conversion.
373 
374  auto TryCastValTy = [&](Constant *P) -> Constant * {
375  // The conversion is illegal if the store is wider than the
376  // pointee proposed by `evaluateBitcastFromPtr`, since that would
377  // drop stores to other struct elements when the caller attempts to
378  // look through a struct's 0th element.
379  Type *NewTy = cast<PointerType>(P->getType())->getElementType();
380  Type *STy = Val->getType();
381  if (DL.getTypeSizeInBits(NewTy) < DL.getTypeSizeInBits(STy))
382  return nullptr;
383 
384  if (Constant *FV = ConstantFoldLoadThroughBitcast(Val, NewTy, DL)) {
385  Ptr = P;
386  return FV;
387  }
388  return nullptr;
389  };
390 
391  Constant *NewVal =
392  evaluateBitcastFromPtr(CE->getOperand(0), DL, TLI, TryCastValTy);
393  if (!NewVal) {
394  LLVM_DEBUG(dbgs() << "Failed to bitcast constant ptr, can not "
395  "evaluate.\n");
396  return false;
397  }
398 
399  Val = NewVal;
400  LLVM_DEBUG(dbgs() << "Evaluated bitcast: " << *Val << "\n");
401  }
402  }
403 
404  MutatedMemory[Ptr] = Val;
405  } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) {
406  InstResult = ConstantExpr::get(BO->getOpcode(),
407  getVal(BO->getOperand(0)),
408  getVal(BO->getOperand(1)));
409  LLVM_DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: "
410  << *InstResult << "\n");
411  } else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) {
412  InstResult = ConstantExpr::getCompare(CI->getPredicate(),
413  getVal(CI->getOperand(0)),
414  getVal(CI->getOperand(1)));
415  LLVM_DEBUG(dbgs() << "Found a CmpInst! Simplifying: " << *InstResult
416  << "\n");
417  } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) {
418  InstResult = ConstantExpr::getCast(CI->getOpcode(),
419  getVal(CI->getOperand(0)),
420  CI->getType());
421  LLVM_DEBUG(dbgs() << "Found a Cast! Simplifying: " << *InstResult
422  << "\n");
423  } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) {
424  InstResult = ConstantExpr::getSelect(getVal(SI->getOperand(0)),
425  getVal(SI->getOperand(1)),
426  getVal(SI->getOperand(2)));
427  LLVM_DEBUG(dbgs() << "Found a Select! Simplifying: " << *InstResult
428  << "\n");
429  } else if (auto *EVI = dyn_cast<ExtractValueInst>(CurInst)) {
430  InstResult = ConstantExpr::getExtractValue(
431  getVal(EVI->getAggregateOperand()), EVI->getIndices());
432  LLVM_DEBUG(dbgs() << "Found an ExtractValueInst! Simplifying: "
433  << *InstResult << "\n");
434  } else if (auto *IVI = dyn_cast<InsertValueInst>(CurInst)) {
435  InstResult = ConstantExpr::getInsertValue(
436  getVal(IVI->getAggregateOperand()),
437  getVal(IVI->getInsertedValueOperand()), IVI->getIndices());
438  LLVM_DEBUG(dbgs() << "Found an InsertValueInst! Simplifying: "
439  << *InstResult << "\n");
440  } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) {
441  Constant *P = getVal(GEP->getOperand(0));
443  for (Use &Op : llvm::drop_begin(GEP->operands()))
444  GEPOps.push_back(getVal(Op));
445  InstResult =
446  ConstantExpr::getGetElementPtr(GEP->getSourceElementType(), P, GEPOps,
447  cast<GEPOperator>(GEP)->isInBounds());
448  LLVM_DEBUG(dbgs() << "Found a GEP! Simplifying: " << *InstResult << "\n");
449  } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
450  if (!LI->isSimple()) {
451  LLVM_DEBUG(
452  dbgs() << "Found a Load! Not a simple load, can not evaluate.\n");
453  return false; // no volatile/atomic accesses.
454  }
455 
456  Constant *Ptr = getVal(LI->getOperand(0));
457  Constant *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI);
458  if (Ptr != FoldedPtr) {
459  Ptr = FoldedPtr;
460  LLVM_DEBUG(dbgs() << "Found a constant pointer expression, constant "
461  "folding: "
462  << *Ptr << "\n");
463  }
464  InstResult = ComputeLoadResult(Ptr, LI->getType());
465  if (!InstResult) {
466  LLVM_DEBUG(
467  dbgs() << "Failed to compute load result. Can not evaluate load."
468  "\n");
469  return false; // Could not evaluate load.
470  }
471 
472  LLVM_DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n");
473  } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) {
474  if (AI->isArrayAllocation()) {
475  LLVM_DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n");
476  return false; // Cannot handle array allocs.
477  }
478  Type *Ty = AI->getAllocatedType();
479  AllocaTmps.push_back(std::make_unique<GlobalVariable>(
481  AI->getName(), /*TLMode=*/GlobalValue::NotThreadLocal,
482  AI->getType()->getPointerAddressSpace()));
483  InstResult = AllocaTmps.back().get();
484  LLVM_DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n");
485  } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) {
486  CallBase &CB = *cast<CallBase>(&*CurInst);
487 
488  // Debug info can safely be ignored here.
489  if (isa<DbgInfoIntrinsic>(CB)) {
490  LLVM_DEBUG(dbgs() << "Ignoring debug info.\n");
491  ++CurInst;
492  continue;
493  }
494 
495  // Cannot handle inline asm.
496  if (CB.isInlineAsm()) {
497  LLVM_DEBUG(dbgs() << "Found inline asm, can not evaluate.\n");
498  return false;
499  }
500 
501  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&CB)) {
502  if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) {
503  if (MSI->isVolatile()) {
504  LLVM_DEBUG(dbgs() << "Can not optimize a volatile memset "
505  << "intrinsic.\n");
506  return false;
507  }
508  Constant *Ptr = getVal(MSI->getDest());
509  Constant *Val = getVal(MSI->getValue());
510  Constant *DestVal =
511  ComputeLoadResult(getVal(Ptr), MSI->getValue()->getType());
512  if (Val->isNullValue() && DestVal && DestVal->isNullValue()) {
513  // This memset is a no-op.
514  LLVM_DEBUG(dbgs() << "Ignoring no-op memset.\n");
515  ++CurInst;
516  continue;
517  }
518  }
519 
520  if (II->isLifetimeStartOrEnd()) {
521  LLVM_DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
522  ++CurInst;
523  continue;
524  }
525 
526  if (II->getIntrinsicID() == Intrinsic::invariant_start) {
527  // We don't insert an entry into Values, as it doesn't have a
528  // meaningful return value.
529  if (!II->use_empty()) {
530  LLVM_DEBUG(dbgs()
531  << "Found unused invariant_start. Can't evaluate.\n");
532  return false;
533  }
534  ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0));
535  Value *PtrArg = getVal(II->getArgOperand(1));
536  Value *Ptr = PtrArg->stripPointerCasts();
537  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
538  Type *ElemTy = GV->getValueType();
539  if (!Size->isMinusOne() &&
540  Size->getValue().getLimitedValue() >=
541  DL.getTypeStoreSize(ElemTy)) {
542  Invariants.insert(GV);
543  LLVM_DEBUG(dbgs() << "Found a global var that is an invariant: "
544  << *GV << "\n");
545  } else {
546  LLVM_DEBUG(dbgs()
547  << "Found a global var, but can not treat it as an "
548  "invariant.\n");
549  }
550  }
551  // Continue even if we do nothing.
552  ++CurInst;
553  continue;
554  } else if (II->getIntrinsicID() == Intrinsic::assume) {
555  LLVM_DEBUG(dbgs() << "Skipping assume intrinsic.\n");
556  ++CurInst;
557  continue;
558  } else if (II->getIntrinsicID() == Intrinsic::sideeffect) {
559  LLVM_DEBUG(dbgs() << "Skipping sideeffect intrinsic.\n");
560  ++CurInst;
561  continue;
562  } else if (II->getIntrinsicID() == Intrinsic::pseudoprobe) {
563  LLVM_DEBUG(dbgs() << "Skipping pseudoprobe intrinsic.\n");
564  ++CurInst;
565  continue;
566  } else {
567  Value *Stripped = CurInst->stripPointerCastsForAliasAnalysis();
568  // Only attempt to getVal() if we've actually managed to strip
569  // anything away, or else we'll call getVal() on the current
570  // instruction.
571  if (Stripped != &*CurInst) {
572  InstResult = getVal(Stripped);
573  }
574  if (InstResult) {
575  LLVM_DEBUG(dbgs()
576  << "Stripped pointer casts for alias analysis for "
577  "intrinsic call.\n");
578  StrippedPointerCastsForAliasAnalysis = true;
579  InstResult = ConstantExpr::getBitCast(InstResult, II->getType());
580  } else {
581  LLVM_DEBUG(dbgs() << "Unknown intrinsic. Cannot evaluate.\n");
582  return false;
583  }
584  }
585  }
586 
587  if (!InstResult) {
588  // Resolve function pointers.
590  Function *Callee = getCalleeWithFormalArgs(CB, Formals);
591  if (!Callee || Callee->isInterposable()) {
592  LLVM_DEBUG(dbgs() << "Can not resolve function pointer.\n");
593  return false; // Cannot resolve.
594  }
595 
596  if (Callee->isDeclaration()) {
597  // If this is a function we can constant fold, do it.
598  if (Constant *C = ConstantFoldCall(&CB, Callee, Formals, TLI)) {
599  InstResult = castCallResultIfNeeded(CB.getCalledOperand(), C);
600  if (!InstResult)
601  return false;
602  LLVM_DEBUG(dbgs() << "Constant folded function call. Result: "
603  << *InstResult << "\n");
604  } else {
605  LLVM_DEBUG(dbgs() << "Can not constant fold function call.\n");
606  return false;
607  }
608  } else {
609  if (Callee->getFunctionType()->isVarArg()) {
610  LLVM_DEBUG(dbgs()
611  << "Can not constant fold vararg function call.\n");
612  return false;
613  }
614 
615  Constant *RetVal = nullptr;
616  // Execute the call, if successful, use the return value.
617  ValueStack.emplace_back();
618  if (!EvaluateFunction(Callee, RetVal, Formals)) {
619  LLVM_DEBUG(dbgs() << "Failed to evaluate function.\n");
620  return false;
621  }
622  ValueStack.pop_back();
623  InstResult = castCallResultIfNeeded(CB.getCalledOperand(), RetVal);
624  if (RetVal && !InstResult)
625  return false;
626 
627  if (InstResult) {
628  LLVM_DEBUG(dbgs() << "Successfully evaluated function. Result: "
629  << *InstResult << "\n\n");
630  } else {
631  LLVM_DEBUG(dbgs()
632  << "Successfully evaluated function. Result: 0\n\n");
633  }
634  }
635  }
636  } else if (CurInst->isTerminator()) {
637  LLVM_DEBUG(dbgs() << "Found a terminator instruction.\n");
638 
639  if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
640  if (BI->isUnconditional()) {
641  NextBB = BI->getSuccessor(0);
642  } else {
643  ConstantInt *Cond =
644  dyn_cast<ConstantInt>(getVal(BI->getCondition()));
645  if (!Cond) return false; // Cannot determine.
646 
647  NextBB = BI->getSuccessor(!Cond->getZExtValue());
648  }
649  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
650  ConstantInt *Val =
651  dyn_cast<ConstantInt>(getVal(SI->getCondition()));
652  if (!Val) return false; // Cannot determine.
653  NextBB = SI->findCaseValue(Val)->getCaseSuccessor();
654  } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
655  Value *Val = getVal(IBI->getAddress())->stripPointerCasts();
656  if (BlockAddress *BA = dyn_cast<BlockAddress>(Val))
657  NextBB = BA->getBasicBlock();
658  else
659  return false; // Cannot determine.
660  } else if (isa<ReturnInst>(CurInst)) {
661  NextBB = nullptr;
662  } else {
663  // invoke, unwind, resume, unreachable.
664  LLVM_DEBUG(dbgs() << "Can not handle terminator.");
665  return false; // Cannot handle this terminator.
666  }
667 
668  // We succeeded at evaluating this block!
669  LLVM_DEBUG(dbgs() << "Successfully evaluated block.\n");
670  return true;
671  } else {
672  // Did not know how to evaluate this!
673  LLVM_DEBUG(
674  dbgs() << "Failed to evaluate block due to unhandled instruction."
675  "\n");
676  return false;
677  }
678 
679  if (!CurInst->use_empty()) {
680  InstResult = ConstantFoldConstant(InstResult, DL, TLI);
681  setVal(&*CurInst, InstResult);
682  }
683 
684  // If we just processed an invoke, we finished evaluating the block.
685  if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
686  NextBB = II->getNormalDest();
687  LLVM_DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");
688  return true;
689  }
690 
691  // Advance program counter.
692  ++CurInst;
693  }
694 }
695 
696 /// Evaluate a call to function F, returning true if successful, false if we
697 /// can't evaluate it. ActualArgs contains the formal arguments for the
698 /// function.
700  const SmallVectorImpl<Constant*> &ActualArgs) {
701  // Check to see if this function is already executing (recursion). If so,
702  // bail out. TODO: we might want to accept limited recursion.
703  if (is_contained(CallStack, F))
704  return false;
705 
706  CallStack.push_back(F);
707 
708  // Initialize arguments to the incoming values specified.
709  unsigned ArgNo = 0;
710  for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
711  ++AI, ++ArgNo)
712  setVal(&*AI, ActualArgs[ArgNo]);
713 
714  // ExecutedBlocks - We only handle non-looping, non-recursive code. As such,
715  // we can only evaluate any one basic block at most once. This set keeps
716  // track of what we have executed so we can detect recursive cases etc.
717  SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
718 
719  // CurBB - The current basic block we're evaluating.
720  BasicBlock *CurBB = &F->front();
721 
722  BasicBlock::iterator CurInst = CurBB->begin();
723 
724  while (true) {
725  BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
726  LLVM_DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
727 
728  bool StrippedPointerCastsForAliasAnalysis = false;
729 
730  if (!EvaluateBlock(CurInst, NextBB, StrippedPointerCastsForAliasAnalysis))
731  return false;
732 
733  if (!NextBB) {
734  // Successfully running until there's no next block means that we found
735  // the return. Fill it the return value and pop the call stack.
736  ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator());
737  if (RI->getNumOperands()) {
738  // The Evaluator can look through pointer casts as long as alias
739  // analysis holds because it's just a simple interpreter and doesn't
740  // skip memory accesses due to invariant group metadata, but we can't
741  // let users of Evaluator use a value that's been gleaned looking
742  // through stripping pointer casts.
743  if (StrippedPointerCastsForAliasAnalysis &&
744  !RI->getReturnValue()->getType()->isVoidTy()) {
745  return false;
746  }
747  RetVal = getVal(RI->getOperand(0));
748  }
749  CallStack.pop_back();
750  return true;
751  }
752 
753  // Okay, we succeeded in evaluating this control flow. See if we have
754  // executed the new block before. If so, we have a looping function,
755  // which we cannot evaluate in reasonable time.
756  if (!ExecutedBlocks.insert(NextBB).second)
757  return false; // looped!
758 
759  // Okay, we have never been in this block before. Check to see if there
760  // are any PHI nodes. If so, evaluate them with information about where
761  // we came from.
762  PHINode *PN = nullptr;
763  for (CurInst = NextBB->begin();
764  (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)
765  setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB)));
766 
767  // Advance to the next block.
768  CurBB = NextBB;
769  }
770 }
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
llvm
---------------------— PointerInfo ------------------------------------—
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:699
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:266
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:2986
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
getFunction
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:255
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:3031
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:1458
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::getBitCast
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2208
llvm::ConstantExpr::getSelect
static Constant * getSelect(Constant *C, Constant *V1, Constant *V2, Type *OnlyIfReducedTy=nullptr)
Select constant expr.
Definition: Constants.cpp:2395
llvm::ConstantExpr::getInsertValue
static Constant * getInsertValue(Constant *Agg, Constant *Val, ArrayRef< unsigned > Idxs, Type *OnlyIfReducedTy=nullptr)
Definition: Constants.cpp:2598
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
CallExpr
Definition: ItaniumDemangle.h:1894
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:1336
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:1303
ConstantFolding.h
evaluateBitcastFromPtr
static Constant * evaluateBitcastFromPtr(Constant *Ptr, const DataLayout &DL, const TargetLibraryInfo *TLI, std::function< Constant *(Constant *)> TryLoad)
Apply TryLoad to Ptr.
Definition: Evaluator.cpp:182
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::FunctionType::isVarArg
bool isVarArg() const
Definition: DerivedTypes.h:123
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:163
Instruction.h
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
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:74
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
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:3114
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2818
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1771
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:900
llvm::FunctionCallee::getFunctionType
FunctionType * getFunctionType()
Definition: DerivedTypes.h:182
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:905
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:356
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3749
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:710
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:2373
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:304
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:2242
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:928
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:1616
SI
StandardInstrumentations SI(Debug, VerifyEach)
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:1963
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:703
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1738
getInitializer
static Constant * getInitializer(Constant *C)
Definition: Evaluator.cpp:204
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:138
llvm::WinEH::EncodingType::CE
@ CE
Windows NT (Windows on ARM)
llvm::BlockAddress
The address of a basic block.
Definition: Constants.h:848
llvm::BinaryOperator
Definition: InstrTypes.h:189
DataLayout.h
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
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:194
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:430
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
llvm::Type::getContext
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:127
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
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:687
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:206
llvm::ConstantFoldLoadThroughGEPConstantExpr
Constant * ConstantFoldLoadThroughGEPConstantExpr(Constant *C, ConstantExpr *CE, Type *Ty, const DataLayout &DL)
ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a getelementptr constantexpr,...
Definition: ConstantFolding.cpp:1402
Constant.h
llvm::ConstantExpr
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:936
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
GlobalVariable.h
Casting.h
Function.h
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:219
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:1210
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
llvm::CallBase::getCalledOperand
Value * getCalledOperand() const
Definition: InstrTypes.h:1386
llvm::IndirectBrInst
Indirect Branch Instruction.
Definition: Instructions.h:3614
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:2633
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:1223
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
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:275
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3212
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:62
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3068
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:2622
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
isSimpleEnoughPointerToCommit
static bool isSimpleEnoughPointerToCommit(Constant *C, const DataLayout &DL)
Return true if this constant is simple enough for us to understand.
Definition: Evaluator.cpp:130
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