LLVM  15.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/Operator.h"
33 #include "llvm/IR/Type.h"
34 #include "llvm/IR/User.h"
35 #include "llvm/IR/Value.h"
36 #include "llvm/Support/Casting.h"
37 #include "llvm/Support/Debug.h"
39 
40 #define DEBUG_TYPE "evaluator"
41 
42 using namespace llvm;
43 
44 static inline bool
46  SmallPtrSetImpl<Constant *> &SimpleConstants,
47  const DataLayout &DL);
48 
49 /// Return true if the specified constant can be handled by the code generator.
50 /// We don't want to generate something like:
51 /// void *X = &X/42;
52 /// because the code generator doesn't have a relocation that can handle that.
53 ///
54 /// This function should be called if C was not found (but just got inserted)
55 /// in SimpleConstants to avoid having to rescan the same constants all the
56 /// time.
57 static bool
59  SmallPtrSetImpl<Constant *> &SimpleConstants,
60  const DataLayout &DL) {
61  // Simple global addresses are supported, do not allow dllimport or
62  // thread-local globals.
63  if (auto *GV = dyn_cast<GlobalValue>(C))
64  return !GV->hasDLLImportStorageClass() && !GV->isThreadLocal();
65 
66  // Simple integer, undef, constant aggregate zero, etc are all supported.
67  if (C->getNumOperands() == 0 || isa<BlockAddress>(C))
68  return true;
69 
70  // Aggregate values are safe if all their elements are.
71  if (isa<ConstantAggregate>(C)) {
72  for (Value *Op : C->operands())
73  if (!isSimpleEnoughValueToCommit(cast<Constant>(Op), SimpleConstants, DL))
74  return false;
75  return true;
76  }
77 
78  // We don't know exactly what relocations are allowed in constant expressions,
79  // so we allow &global+constantoffset, which is safe and uniformly supported
80  // across targets.
81  ConstantExpr *CE = cast<ConstantExpr>(C);
82  switch (CE->getOpcode()) {
83  case Instruction::BitCast:
84  // Bitcast is fine if the casted value is fine.
85  return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
86 
87  case Instruction::IntToPtr:
88  case Instruction::PtrToInt:
89  // int <=> ptr is fine if the int type is the same size as the
90  // pointer type.
91  if (DL.getTypeSizeInBits(CE->getType()) !=
92  DL.getTypeSizeInBits(CE->getOperand(0)->getType()))
93  return false;
94  return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
95 
96  // GEP is fine if it is simple + constant offset.
97  case Instruction::GetElementPtr:
98  for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
99  if (!isa<ConstantInt>(CE->getOperand(i)))
100  return false;
101  return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
102 
103  case Instruction::Add:
104  // We allow simple+cst.
105  if (!isa<ConstantInt>(CE->getOperand(1)))
106  return false;
107  return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
108  }
109  return false;
110 }
111 
112 static inline bool
114  SmallPtrSetImpl<Constant *> &SimpleConstants,
115  const DataLayout &DL) {
116  // If we already checked this constant, we win.
117  if (!SimpleConstants.insert(C).second)
118  return true;
119  // Check the constant.
120  return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, DL);
121 }
122 
124  if (auto *Agg = Val.dyn_cast<MutableAggregate *>())
125  delete Agg;
126  Val = nullptr;
127 }
128 
130  const DataLayout &DL) const {
131  TypeSize TySize = DL.getTypeStoreSize(Ty);
132  const MutableValue *V = this;
133  while (const auto *Agg = V->Val.dyn_cast<MutableAggregate *>()) {
134  Type *AggTy = Agg->Ty;
135  Optional<APInt> Index = DL.getGEPIndexForOffset(AggTy, Offset);
136  if (!Index || Index->uge(Agg->Elements.size()) ||
137  !TypeSize::isKnownLE(TySize, DL.getTypeStoreSize(AggTy)))
138  return nullptr;
139 
140  V = &Agg->Elements[Index->getZExtValue()];
141  }
142 
143  return ConstantFoldLoadFromConst(V->Val.get<Constant *>(), Ty, Offset, DL);
144 }
145 
146 bool Evaluator::MutableValue::makeMutable() {
147  Constant *C = Val.get<Constant *>();
148  Type *Ty = C->getType();
149  unsigned NumElements;
150  if (auto *VT = dyn_cast<FixedVectorType>(Ty)) {
151  NumElements = VT->getNumElements();
152  } else if (auto *AT = dyn_cast<ArrayType>(Ty))
153  NumElements = AT->getNumElements();
154  else if (auto *ST = dyn_cast<StructType>(Ty))
155  NumElements = ST->getNumElements();
156  else
157  return false;
158 
159  MutableAggregate *MA = new MutableAggregate(Ty);
160  MA->Elements.reserve(NumElements);
161  for (unsigned I = 0; I < NumElements; ++I)
162  MA->Elements.push_back(C->getAggregateElement(I));
163  Val = MA;
164  return true;
165 }
166 
168  const DataLayout &DL) {
169  Type *Ty = V->getType();
170  TypeSize TySize = DL.getTypeStoreSize(Ty);
171  MutableValue *MV = this;
172  while (Offset != 0 ||
173  !CastInst::isBitOrNoopPointerCastable(Ty, MV->getType(), DL)) {
174  if (MV->Val.is<Constant *>() && !MV->makeMutable())
175  return false;
176 
177  MutableAggregate *Agg = MV->Val.get<MutableAggregate *>();
178  Type *AggTy = Agg->Ty;
179  Optional<APInt> Index = DL.getGEPIndexForOffset(AggTy, Offset);
180  if (!Index || Index->uge(Agg->Elements.size()) ||
181  !TypeSize::isKnownLE(TySize, DL.getTypeStoreSize(AggTy)))
182  return false;
183 
184  MV = &Agg->Elements[Index->getZExtValue()];
185  }
186 
187  Type *MVType = MV->getType();
188  MV->clear();
189  if (Ty->isIntegerTy() && MVType->isPointerTy())
190  MV->Val = ConstantExpr::getIntToPtr(V, MVType);
191  else if (Ty->isPointerTy() && MVType->isIntegerTy())
192  MV->Val = ConstantExpr::getPtrToInt(V, MVType);
193  else if (Ty != MVType)
194  MV->Val = ConstantExpr::getBitCast(V, MVType);
195  else
196  MV->Val = V;
197  return true;
198 }
199 
200 Constant *Evaluator::MutableAggregate::toConstant() const {
202  for (const MutableValue &MV : Elements)
203  Consts.push_back(MV.toConstant());
204 
205  if (auto *ST = dyn_cast<StructType>(Ty))
206  return ConstantStruct::get(ST, Consts);
207  if (auto *AT = dyn_cast<ArrayType>(Ty))
208  return ConstantArray::get(AT, Consts);
209  assert(isa<FixedVectorType>(Ty) && "Must be vector");
210  return ConstantVector::get(Consts);
211 }
212 
213 /// Return the value that would be computed by a load from P after the stores
214 /// reflected by 'memory' have been performed. If we can't decide, return null.
215 Constant *Evaluator::ComputeLoadResult(Constant *P, Type *Ty) {
216  APInt Offset(DL.getIndexTypeSizeInBits(P->getType()), 0);
217  P = cast<Constant>(P->stripAndAccumulateConstantOffsets(
218  DL, Offset, /* AllowNonInbounds */ true));
219  Offset = Offset.sextOrTrunc(DL.getIndexTypeSizeInBits(P->getType()));
220  auto *GV = dyn_cast<GlobalVariable>(P);
221  if (!GV)
222  return nullptr;
223 
224  auto It = MutatedMemory.find(GV);
225  if (It != MutatedMemory.end())
226  return It->second.read(Ty, Offset, DL);
227 
228  if (!GV->hasDefinitiveInitializer())
229  return nullptr;
230  return ConstantFoldLoadFromConst(GV->getInitializer(), Ty, Offset, DL);
231 }
232 
234  if (auto *Fn = dyn_cast<Function>(C))
235  return Fn;
236 
237  if (auto *Alias = dyn_cast<GlobalAlias>(C))
238  if (auto *Fn = dyn_cast<Function>(Alias->getAliasee()))
239  return Fn;
240  return nullptr;
241 }
242 
243 Function *
244 Evaluator::getCalleeWithFormalArgs(CallBase &CB,
245  SmallVectorImpl<Constant *> &Formals) {
246  auto *V = CB.getCalledOperand()->stripPointerCasts();
247  if (auto *Fn = getFunction(getVal(V)))
248  return getFormalParams(CB, Fn, Formals) ? Fn : nullptr;
249  return nullptr;
250 }
251 
252 bool Evaluator::getFormalParams(CallBase &CB, Function *F,
253  SmallVectorImpl<Constant *> &Formals) {
254  if (!F)
255  return false;
256 
257  auto *FTy = F->getFunctionType();
258  if (FTy->getNumParams() > CB.arg_size()) {
259  LLVM_DEBUG(dbgs() << "Too few arguments for function.\n");
260  return false;
261  }
262 
263  auto ArgI = CB.arg_begin();
264  for (Type *PTy : FTy->params()) {
265  auto *ArgC = ConstantFoldLoadThroughBitcast(getVal(*ArgI), PTy, DL);
266  if (!ArgC) {
267  LLVM_DEBUG(dbgs() << "Can not convert function argument.\n");
268  return false;
269  }
270  Formals.push_back(ArgC);
271  ++ArgI;
272  }
273  return true;
274 }
275 
276 /// If call expression contains bitcast then we may need to cast
277 /// evaluated return value to a type of the call expression.
278 Constant *Evaluator::castCallResultIfNeeded(Type *ReturnType, Constant *RV) {
279  if (!RV || RV->getType() == ReturnType)
280  return RV;
281 
283  if (!RV)
284  LLVM_DEBUG(dbgs() << "Failed to fold bitcast call expr\n");
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. StrippedPointerCastsForAliasAnalysis is set to true if
291 /// we looked through pointer casts to evaluate something.
292 bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB,
293  bool &StrippedPointerCastsForAliasAnalysis) {
294  // This is the main evaluation loop.
295  while (true) {
296  Constant *InstResult = nullptr;
297 
298  LLVM_DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n");
299 
300  if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
301  if (!SI->isSimple()) {
302  LLVM_DEBUG(dbgs() << "Store is not simple! Can not evaluate.\n");
303  return false; // no volatile/atomic accesses.
304  }
305  Constant *Ptr = getVal(SI->getOperand(1));
306  Constant *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI);
307  if (Ptr != FoldedPtr) {
308  LLVM_DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr);
309  Ptr = FoldedPtr;
310  LLVM_DEBUG(dbgs() << "; To: " << *Ptr << "\n");
311  }
312 
313  APInt Offset(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
314  Ptr = cast<Constant>(Ptr->stripAndAccumulateConstantOffsets(
315  DL, Offset, /* AllowNonInbounds */ true));
316  Offset = Offset.sextOrTrunc(DL.getIndexTypeSizeInBits(Ptr->getType()));
317  auto *GV = dyn_cast<GlobalVariable>(Ptr);
318  if (!GV || !GV->hasUniqueInitializer()) {
319  LLVM_DEBUG(dbgs() << "Store is not to global with unique initializer: "
320  << *Ptr << "\n");
321  return false;
322  }
323 
324  // If this might be too difficult for the backend to handle (e.g. the addr
325  // of one global variable divided by another) then we can't commit it.
326  Constant *Val = getVal(SI->getOperand(0));
327  if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) {
328  LLVM_DEBUG(dbgs() << "Store value is too complex to evaluate store. "
329  << *Val << "\n");
330  return false;
331  }
332 
333  auto Res = MutatedMemory.try_emplace(GV, GV->getInitializer());
334  if (!Res.first->second.write(Val, Offset, DL))
335  return false;
336  } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) {
337  InstResult = ConstantExpr::get(BO->getOpcode(),
338  getVal(BO->getOperand(0)),
339  getVal(BO->getOperand(1)));
340  LLVM_DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: "
341  << *InstResult << "\n");
342  } else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) {
343  InstResult = ConstantExpr::getCompare(CI->getPredicate(),
344  getVal(CI->getOperand(0)),
345  getVal(CI->getOperand(1)));
346  LLVM_DEBUG(dbgs() << "Found a CmpInst! Simplifying: " << *InstResult
347  << "\n");
348  } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) {
349  InstResult = ConstantExpr::getCast(CI->getOpcode(),
350  getVal(CI->getOperand(0)),
351  CI->getType());
352  LLVM_DEBUG(dbgs() << "Found a Cast! Simplifying: " << *InstResult
353  << "\n");
354  } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) {
355  InstResult = ConstantExpr::getSelect(getVal(SI->getOperand(0)),
356  getVal(SI->getOperand(1)),
357  getVal(SI->getOperand(2)));
358  LLVM_DEBUG(dbgs() << "Found a Select! Simplifying: " << *InstResult
359  << "\n");
360  } else if (auto *EVI = dyn_cast<ExtractValueInst>(CurInst)) {
361  InstResult = ConstantExpr::getExtractValue(
362  getVal(EVI->getAggregateOperand()), EVI->getIndices());
363  LLVM_DEBUG(dbgs() << "Found an ExtractValueInst! Simplifying: "
364  << *InstResult << "\n");
365  } else if (auto *IVI = dyn_cast<InsertValueInst>(CurInst)) {
366  InstResult = ConstantExpr::getInsertValue(
367  getVal(IVI->getAggregateOperand()),
368  getVal(IVI->getInsertedValueOperand()), IVI->getIndices());
369  LLVM_DEBUG(dbgs() << "Found an InsertValueInst! Simplifying: "
370  << *InstResult << "\n");
371  } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) {
372  Constant *P = getVal(GEP->getOperand(0));
374  for (Use &Op : llvm::drop_begin(GEP->operands()))
375  GEPOps.push_back(getVal(Op));
376  InstResult =
377  ConstantExpr::getGetElementPtr(GEP->getSourceElementType(), P, GEPOps,
378  cast<GEPOperator>(GEP)->isInBounds());
379  LLVM_DEBUG(dbgs() << "Found a GEP! Simplifying: " << *InstResult << "\n");
380  } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
381  if (!LI->isSimple()) {
382  LLVM_DEBUG(
383  dbgs() << "Found a Load! Not a simple load, can not evaluate.\n");
384  return false; // no volatile/atomic accesses.
385  }
386 
387  Constant *Ptr = getVal(LI->getOperand(0));
388  Constant *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI);
389  if (Ptr != FoldedPtr) {
390  Ptr = FoldedPtr;
391  LLVM_DEBUG(dbgs() << "Found a constant pointer expression, constant "
392  "folding: "
393  << *Ptr << "\n");
394  }
395  InstResult = ComputeLoadResult(Ptr, LI->getType());
396  if (!InstResult) {
397  LLVM_DEBUG(
398  dbgs() << "Failed to compute load result. Can not evaluate load."
399  "\n");
400  return false; // Could not evaluate load.
401  }
402 
403  LLVM_DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n");
404  } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) {
405  if (AI->isArrayAllocation()) {
406  LLVM_DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n");
407  return false; // Cannot handle array allocs.
408  }
409  Type *Ty = AI->getAllocatedType();
410  AllocaTmps.push_back(std::make_unique<GlobalVariable>(
412  AI->getName(), /*TLMode=*/GlobalValue::NotThreadLocal,
413  AI->getType()->getPointerAddressSpace()));
414  InstResult = AllocaTmps.back().get();
415  LLVM_DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n");
416  } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) {
417  CallBase &CB = *cast<CallBase>(&*CurInst);
418 
419  // Debug info can safely be ignored here.
420  if (isa<DbgInfoIntrinsic>(CB)) {
421  LLVM_DEBUG(dbgs() << "Ignoring debug info.\n");
422  ++CurInst;
423  continue;
424  }
425 
426  // Cannot handle inline asm.
427  if (CB.isInlineAsm()) {
428  LLVM_DEBUG(dbgs() << "Found inline asm, can not evaluate.\n");
429  return false;
430  }
431 
432  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&CB)) {
433  if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) {
434  if (MSI->isVolatile()) {
435  LLVM_DEBUG(dbgs() << "Can not optimize a volatile memset "
436  << "intrinsic.\n");
437  return false;
438  }
439  Constant *Ptr = getVal(MSI->getDest());
440  Constant *Val = getVal(MSI->getValue());
441  Constant *DestVal =
442  ComputeLoadResult(getVal(Ptr), MSI->getValue()->getType());
443  if (Val->isNullValue() && DestVal && DestVal->isNullValue()) {
444  // This memset is a no-op.
445  LLVM_DEBUG(dbgs() << "Ignoring no-op memset.\n");
446  ++CurInst;
447  continue;
448  }
449  }
450 
451  if (II->isLifetimeStartOrEnd()) {
452  LLVM_DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
453  ++CurInst;
454  continue;
455  }
456 
457  if (II->getIntrinsicID() == Intrinsic::invariant_start) {
458  // We don't insert an entry into Values, as it doesn't have a
459  // meaningful return value.
460  if (!II->use_empty()) {
461  LLVM_DEBUG(dbgs()
462  << "Found unused invariant_start. Can't evaluate.\n");
463  return false;
464  }
465  ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0));
466  Value *PtrArg = getVal(II->getArgOperand(1));
467  Value *Ptr = PtrArg->stripPointerCasts();
468  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
469  Type *ElemTy = GV->getValueType();
470  if (!Size->isMinusOne() &&
471  Size->getValue().getLimitedValue() >=
472  DL.getTypeStoreSize(ElemTy)) {
473  Invariants.insert(GV);
474  LLVM_DEBUG(dbgs() << "Found a global var that is an invariant: "
475  << *GV << "\n");
476  } else {
477  LLVM_DEBUG(dbgs()
478  << "Found a global var, but can not treat it as an "
479  "invariant.\n");
480  }
481  }
482  // Continue even if we do nothing.
483  ++CurInst;
484  continue;
485  } else if (II->getIntrinsicID() == Intrinsic::assume) {
486  LLVM_DEBUG(dbgs() << "Skipping assume intrinsic.\n");
487  ++CurInst;
488  continue;
489  } else if (II->getIntrinsicID() == Intrinsic::sideeffect) {
490  LLVM_DEBUG(dbgs() << "Skipping sideeffect intrinsic.\n");
491  ++CurInst;
492  continue;
493  } else if (II->getIntrinsicID() == Intrinsic::pseudoprobe) {
494  LLVM_DEBUG(dbgs() << "Skipping pseudoprobe intrinsic.\n");
495  ++CurInst;
496  continue;
497  } else {
498  Value *Stripped = CurInst->stripPointerCastsForAliasAnalysis();
499  // Only attempt to getVal() if we've actually managed to strip
500  // anything away, or else we'll call getVal() on the current
501  // instruction.
502  if (Stripped != &*CurInst) {
503  InstResult = getVal(Stripped);
504  }
505  if (InstResult) {
506  LLVM_DEBUG(dbgs()
507  << "Stripped pointer casts for alias analysis for "
508  "intrinsic call.\n");
509  StrippedPointerCastsForAliasAnalysis = true;
510  InstResult = ConstantExpr::getBitCast(InstResult, II->getType());
511  } else {
512  LLVM_DEBUG(dbgs() << "Unknown intrinsic. Cannot evaluate.\n");
513  return false;
514  }
515  }
516  }
517 
518  if (!InstResult) {
519  // Resolve function pointers.
521  Function *Callee = getCalleeWithFormalArgs(CB, Formals);
522  if (!Callee || Callee->isInterposable()) {
523  LLVM_DEBUG(dbgs() << "Can not resolve function pointer.\n");
524  return false; // Cannot resolve.
525  }
526 
527  if (Callee->isDeclaration()) {
528  // If this is a function we can constant fold, do it.
529  if (Constant *C = ConstantFoldCall(&CB, Callee, Formals, TLI)) {
530  InstResult = castCallResultIfNeeded(CB.getType(), C);
531  if (!InstResult)
532  return false;
533  LLVM_DEBUG(dbgs() << "Constant folded function call. Result: "
534  << *InstResult << "\n");
535  } else {
536  LLVM_DEBUG(dbgs() << "Can not constant fold function call.\n");
537  return false;
538  }
539  } else {
540  if (Callee->getFunctionType()->isVarArg()) {
541  LLVM_DEBUG(dbgs()
542  << "Can not constant fold vararg function call.\n");
543  return false;
544  }
545 
546  Constant *RetVal = nullptr;
547  // Execute the call, if successful, use the return value.
548  ValueStack.emplace_back();
549  if (!EvaluateFunction(Callee, RetVal, Formals)) {
550  LLVM_DEBUG(dbgs() << "Failed to evaluate function.\n");
551  return false;
552  }
553  ValueStack.pop_back();
554  InstResult = castCallResultIfNeeded(CB.getType(), RetVal);
555  if (RetVal && !InstResult)
556  return false;
557 
558  if (InstResult) {
559  LLVM_DEBUG(dbgs() << "Successfully evaluated function. Result: "
560  << *InstResult << "\n\n");
561  } else {
562  LLVM_DEBUG(dbgs()
563  << "Successfully evaluated function. Result: 0\n\n");
564  }
565  }
566  }
567  } else if (CurInst->isTerminator()) {
568  LLVM_DEBUG(dbgs() << "Found a terminator instruction.\n");
569 
570  if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
571  if (BI->isUnconditional()) {
572  NextBB = BI->getSuccessor(0);
573  } else {
574  ConstantInt *Cond =
575  dyn_cast<ConstantInt>(getVal(BI->getCondition()));
576  if (!Cond) return false; // Cannot determine.
577 
578  NextBB = BI->getSuccessor(!Cond->getZExtValue());
579  }
580  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
581  ConstantInt *Val =
582  dyn_cast<ConstantInt>(getVal(SI->getCondition()));
583  if (!Val) return false; // Cannot determine.
584  NextBB = SI->findCaseValue(Val)->getCaseSuccessor();
585  } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
586  Value *Val = getVal(IBI->getAddress())->stripPointerCasts();
587  if (BlockAddress *BA = dyn_cast<BlockAddress>(Val))
588  NextBB = BA->getBasicBlock();
589  else
590  return false; // Cannot determine.
591  } else if (isa<ReturnInst>(CurInst)) {
592  NextBB = nullptr;
593  } else {
594  // invoke, unwind, resume, unreachable.
595  LLVM_DEBUG(dbgs() << "Can not handle terminator.");
596  return false; // Cannot handle this terminator.
597  }
598 
599  // We succeeded at evaluating this block!
600  LLVM_DEBUG(dbgs() << "Successfully evaluated block.\n");
601  return true;
602  } else {
603  // Did not know how to evaluate this!
604  LLVM_DEBUG(
605  dbgs() << "Failed to evaluate block due to unhandled instruction."
606  "\n");
607  return false;
608  }
609 
610  if (!CurInst->use_empty()) {
611  InstResult = ConstantFoldConstant(InstResult, DL, TLI);
612  setVal(&*CurInst, InstResult);
613  }
614 
615  // If we just processed an invoke, we finished evaluating the block.
616  if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
617  NextBB = II->getNormalDest();
618  LLVM_DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");
619  return true;
620  }
621 
622  // Advance program counter.
623  ++CurInst;
624  }
625 }
626 
627 /// Evaluate a call to function F, returning true if successful, false if we
628 /// can't evaluate it. ActualArgs contains the formal arguments for the
629 /// function.
631  const SmallVectorImpl<Constant*> &ActualArgs) {
632  assert(ActualArgs.size() == F->arg_size() && "wrong number of arguments");
633 
634  // Check to see if this function is already executing (recursion). If so,
635  // bail out. TODO: we might want to accept limited recursion.
636  if (is_contained(CallStack, F))
637  return false;
638 
639  CallStack.push_back(F);
640 
641  // Initialize arguments to the incoming values specified.
642  unsigned ArgNo = 0;
643  for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
644  ++AI, ++ArgNo)
645  setVal(&*AI, ActualArgs[ArgNo]);
646 
647  // ExecutedBlocks - We only handle non-looping, non-recursive code. As such,
648  // we can only evaluate any one basic block at most once. This set keeps
649  // track of what we have executed so we can detect recursive cases etc.
650  SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
651 
652  // CurBB - The current basic block we're evaluating.
653  BasicBlock *CurBB = &F->front();
654 
655  BasicBlock::iterator CurInst = CurBB->begin();
656 
657  while (true) {
658  BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
659  LLVM_DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
660 
661  bool StrippedPointerCastsForAliasAnalysis = false;
662 
663  if (!EvaluateBlock(CurInst, NextBB, StrippedPointerCastsForAliasAnalysis))
664  return false;
665 
666  if (!NextBB) {
667  // Successfully running until there's no next block means that we found
668  // the return. Fill it the return value and pop the call stack.
669  ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator());
670  if (RI->getNumOperands()) {
671  // The Evaluator can look through pointer casts as long as alias
672  // analysis holds because it's just a simple interpreter and doesn't
673  // skip memory accesses due to invariant group metadata, but we can't
674  // let users of Evaluator use a value that's been gleaned looking
675  // through stripping pointer casts.
676  if (StrippedPointerCastsForAliasAnalysis &&
677  !RI->getReturnValue()->getType()->isVoidTy()) {
678  return false;
679  }
680  RetVal = getVal(RI->getOperand(0));
681  }
682  CallStack.pop_back();
683  return true;
684  }
685 
686  // Okay, we succeeded in evaluating this control flow. See if we have
687  // executed the new block before. If so, we have a looping function,
688  // which we cannot evaluate in reasonable time.
689  if (!ExecutedBlocks.insert(NextBB).second)
690  return false; // looped!
691 
692  // Okay, we have never been in this block before. Check to see if there
693  // are any PHI nodes. If so, evaluate them with information about where
694  // we came from.
695  PHINode *PN = nullptr;
696  for (CurInst = NextBB->begin();
697  (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)
698  setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB)));
699 
700  // Advance to the next block.
701  CurBB = NextBB;
702  }
703 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:77
i
i
Definition: README.txt:29
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:630
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:280
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:3004
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
IntrinsicInst.h
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:218
llvm::Function
Definition: Function.h:60
getFunction
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:233
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::ConstantStruct::get
static Constant * get(StructType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1355
llvm::GlobalValue::NotThreadLocal
@ NotThreadLocal
Definition: GlobalValue.h:184
llvm::ReturnInst::getReturnValue
Value * getReturnValue() const
Convenience accessor. Returns null if there is no return value.
Definition: Instructions.h:3049
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::LinearPolySize< TypeSize >::isKnownLE
static bool isKnownLE(const LinearPolySize &LHS, const LinearPolySize &RHS)
Definition: TypeSize.h:340
llvm::CallBase::isInlineAsm
bool isInlineAsm() const
Check if this call is an inline asm statement.
Definition: InstrTypes.h:1464
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:58
llvm::GlobalVariable
Definition: GlobalVariable.h:39
llvm::ConstantExpr::getBitCast
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2266
llvm::ConstantExpr::getSelect
static Constant * getSelect(Constant *C, Constant *V1, Constant *V2, Type *OnlyIfReducedTy=nullptr)
Select constant expr.
Definition: Constants.cpp:2453
llvm::ConstantExpr::getInsertValue
static Constant * getInsertValue(Constant *Agg, Constant *Val, ArrayRef< unsigned > Idxs, Type *OnlyIfReducedTy=nullptr)
Definition: Constants.cpp:2656
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::Optional
Definition: APInt.h:33
llvm::Value::stripAndAccumulateConstantOffsets
const Value * stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset, bool AllowNonInbounds, bool AllowInvariantGroup=false, function_ref< bool(Value &Value, APInt &Offset)> ExternalAnalysis=nullptr) const
Accumulate the constant offset this value has compared to a base pointer.
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
Operator.h
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:1316
ConstantFolding.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::FunctionType::isVarArg
bool isVarArg() const
Definition: DerivedTypes.h:123
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
clear
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:149
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:76
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::ConstantExpr::getIntToPtr
static Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2252
InstrTypes.h
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:297
llvm::ConstantExpr::getPtrToInt
static Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2238
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:3186
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2836
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1777
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 and llvm.memset.inline intrinsics.
Definition: IntrinsicInst.h:989
Evaluator.h
isSimpleEnoughValueToCommit
static bool isSimpleEnoughValueToCommit(Constant *C, SmallPtrSetImpl< Constant * > &SimpleConstants, const DataLayout &DL)
Definition: Evaluator.cpp:113
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:347
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3763
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:709
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:191
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:2431
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:297
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::AMDGPU::Hwreg::Offset
Offset
Definition: SIDefines.h:413
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
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:2300
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:916
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:1682
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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:2010
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:698
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1724
llvm::Type::isVoidTy
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:139
llvm::ARM::WinEH::ReturnType
ReturnType
Definition: ARMWinEH.h:25
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::BlockAddress
The address of a basic block.
Definition: Constants.h:849
llvm::ConstantFoldLoadFromConst
Constant * ConstantFoldLoadFromConst(Constant *C, Type *Ty, const APInt &Offset, const DataLayout &DL)
Extract value of C at the given Offset reinterpreted as Ty.
Definition: ConstantFolding.cpp:697
llvm::BinaryOperator
Definition: InstrTypes.h:188
DataLayout.h
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::CastInst::isBitOrNoopPointerCastable
static bool isBitOrNoopPointerCastable(Type *SrcTy, Type *DestTy, const DataLayout &DL)
Check whether a bitcast, inttoptr, or ptrtoint cast between these types is valid and a no-op.
Definition: Instructions.cpp:3442
llvm::ConstantVector::get
static Constant * get(ArrayRef< Constant * > V)
Definition: Constants.cpp:1397
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:429
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:305
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:173
llvm::Constant::stripPointerCasts
const Constant * stripPointerCasts() const
Definition: Constant.h:213
llvm::Value::stripPointerCasts
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:682
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:186
Constant.h
llvm::ConstantExpr
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:972
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:345
llvm::support::endian::read
value_type read(const void *memory, endianness endian)
Read a value of a particular endianness from memory.
Definition: Endian.h:63
llvm::CallBase::arg_size
unsigned arg_size() const
Definition: InstrTypes.h:1339
GlobalVariable.h
llvm::TypeSize
Definition: TypeSize.h:435
Casting.h
Function.h
llvm::ConstantArray::get
static Constant * get(ArrayType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1290
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:1247
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:185
llvm::CallBase::getCalledOperand
Value * getCalledOperand() const
Definition: InstrTypes.h:1389
llvm::IndirectBrInst
Indirect Branch Instruction.
Definition: Instructions.h:3628
GlobalAlias.h
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
Instructions.h
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
SmallVector.h
User.h
llvm::PHINode
Definition: Instructions.h:2651
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.h:119
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
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:1206
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1174
DerivedTypes.h
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3230
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:58
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3086
raw_ostream.h
Value.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::ConstantExpr::getExtractValue
static Constant * getExtractValue(Constant *Agg, ArrayRef< unsigned > Idxs, Type *OnlyIfReducedTy=nullptr)
Definition: Constants.cpp:2680
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
write
static void write(bool isBE, void *P, T V)
Definition: RuntimeDyldELF.cpp:37
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:365