LLVM  16.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  if (auto *GV = dyn_cast<GlobalVariable>(P))
221  return ComputeLoadResult(GV, Ty, Offset);
222  return nullptr;
223 }
224 
225 Constant *Evaluator::ComputeLoadResult(GlobalVariable *GV, Type *Ty,
226  const APInt &Offset) {
227  auto It = MutatedMemory.find(GV);
228  if (It != MutatedMemory.end())
229  return It->second.read(Ty, Offset, DL);
230 
231  if (!GV->hasDefinitiveInitializer())
232  return nullptr;
233  return ConstantFoldLoadFromConst(GV->getInitializer(), Ty, Offset, DL);
234 }
235 
237  if (auto *Fn = dyn_cast<Function>(C))
238  return Fn;
239 
240  if (auto *Alias = dyn_cast<GlobalAlias>(C))
241  if (auto *Fn = dyn_cast<Function>(Alias->getAliasee()))
242  return Fn;
243  return nullptr;
244 }
245 
246 Function *
247 Evaluator::getCalleeWithFormalArgs(CallBase &CB,
248  SmallVectorImpl<Constant *> &Formals) {
249  auto *V = CB.getCalledOperand()->stripPointerCasts();
250  if (auto *Fn = getFunction(getVal(V)))
251  return getFormalParams(CB, Fn, Formals) ? Fn : nullptr;
252  return nullptr;
253 }
254 
255 bool Evaluator::getFormalParams(CallBase &CB, Function *F,
256  SmallVectorImpl<Constant *> &Formals) {
257  if (!F)
258  return false;
259 
260  auto *FTy = F->getFunctionType();
261  if (FTy->getNumParams() > CB.arg_size()) {
262  LLVM_DEBUG(dbgs() << "Too few arguments for function.\n");
263  return false;
264  }
265 
266  auto ArgI = CB.arg_begin();
267  for (Type *PTy : FTy->params()) {
268  auto *ArgC = ConstantFoldLoadThroughBitcast(getVal(*ArgI), PTy, DL);
269  if (!ArgC) {
270  LLVM_DEBUG(dbgs() << "Can not convert function argument.\n");
271  return false;
272  }
273  Formals.push_back(ArgC);
274  ++ArgI;
275  }
276  return true;
277 }
278 
279 /// If call expression contains bitcast then we may need to cast
280 /// evaluated return value to a type of the call expression.
281 Constant *Evaluator::castCallResultIfNeeded(Type *ReturnType, Constant *RV) {
282  if (!RV || RV->getType() == ReturnType)
283  return RV;
284 
286  if (!RV)
287  LLVM_DEBUG(dbgs() << "Failed to fold bitcast call expr\n");
288  return RV;
289 }
290 
291 /// Evaluate all instructions in block BB, returning true if successful, false
292 /// if we can't evaluate it. NewBB returns the next BB that control flows into,
293 /// or null upon return. StrippedPointerCastsForAliasAnalysis is set to true if
294 /// we looked through pointer casts to evaluate something.
295 bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB,
296  bool &StrippedPointerCastsForAliasAnalysis) {
297  // This is the main evaluation loop.
298  while (true) {
299  Constant *InstResult = nullptr;
300 
301  LLVM_DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n");
302 
303  if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
304  if (SI->isVolatile()) {
305  LLVM_DEBUG(dbgs() << "Store is volatile! Can not evaluate.\n");
306  return false; // no volatile accesses.
307  }
308  Constant *Ptr = getVal(SI->getOperand(1));
309  Constant *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI);
310  if (Ptr != FoldedPtr) {
311  LLVM_DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr);
312  Ptr = FoldedPtr;
313  LLVM_DEBUG(dbgs() << "; To: " << *Ptr << "\n");
314  }
315 
316  APInt Offset(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
317  Ptr = cast<Constant>(Ptr->stripAndAccumulateConstantOffsets(
318  DL, Offset, /* AllowNonInbounds */ true));
319  Offset = Offset.sextOrTrunc(DL.getIndexTypeSizeInBits(Ptr->getType()));
320  auto *GV = dyn_cast<GlobalVariable>(Ptr);
321  if (!GV || !GV->hasUniqueInitializer()) {
322  LLVM_DEBUG(dbgs() << "Store is not to global with unique initializer: "
323  << *Ptr << "\n");
324  return false;
325  }
326 
327  // If this might be too difficult for the backend to handle (e.g. the addr
328  // of one global variable divided by another) then we can't commit it.
329  Constant *Val = getVal(SI->getOperand(0));
330  if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) {
331  LLVM_DEBUG(dbgs() << "Store value is too complex to evaluate store. "
332  << *Val << "\n");
333  return false;
334  }
335 
336  auto Res = MutatedMemory.try_emplace(GV, GV->getInitializer());
337  if (!Res.first->second.write(Val, Offset, DL))
338  return false;
339  } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
340  if (LI->isVolatile()) {
341  LLVM_DEBUG(
342  dbgs() << "Found a Load! Volatile load, can not evaluate.\n");
343  return false; // no volatile accesses.
344  }
345 
346  Constant *Ptr = getVal(LI->getOperand(0));
347  Constant *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI);
348  if (Ptr != FoldedPtr) {
349  Ptr = FoldedPtr;
350  LLVM_DEBUG(dbgs() << "Found a constant pointer expression, constant "
351  "folding: "
352  << *Ptr << "\n");
353  }
354  InstResult = ComputeLoadResult(Ptr, LI->getType());
355  if (!InstResult) {
356  LLVM_DEBUG(
357  dbgs() << "Failed to compute load result. Can not evaluate load."
358  "\n");
359  return false; // Could not evaluate load.
360  }
361 
362  LLVM_DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n");
363  } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) {
364  if (AI->isArrayAllocation()) {
365  LLVM_DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n");
366  return false; // Cannot handle array allocs.
367  }
368  Type *Ty = AI->getAllocatedType();
369  AllocaTmps.push_back(std::make_unique<GlobalVariable>(
371  AI->getName(), /*TLMode=*/GlobalValue::NotThreadLocal,
372  AI->getType()->getPointerAddressSpace()));
373  InstResult = AllocaTmps.back().get();
374  LLVM_DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n");
375  } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) {
376  CallBase &CB = *cast<CallBase>(&*CurInst);
377 
378  // Debug info can safely be ignored here.
379  if (isa<DbgInfoIntrinsic>(CB)) {
380  LLVM_DEBUG(dbgs() << "Ignoring debug info.\n");
381  ++CurInst;
382  continue;
383  }
384 
385  // Cannot handle inline asm.
386  if (CB.isInlineAsm()) {
387  LLVM_DEBUG(dbgs() << "Found inline asm, can not evaluate.\n");
388  return false;
389  }
390 
391  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&CB)) {
392  if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) {
393  if (MSI->isVolatile()) {
394  LLVM_DEBUG(dbgs() << "Can not optimize a volatile memset "
395  << "intrinsic.\n");
396  return false;
397  }
398 
399  auto *LenC = dyn_cast<ConstantInt>(getVal(MSI->getLength()));
400  if (!LenC) {
401  LLVM_DEBUG(dbgs() << "Memset with unknown length.\n");
402  return false;
403  }
404 
405  Constant *Ptr = getVal(MSI->getDest());
406  APInt Offset(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
407  Ptr = cast<Constant>(Ptr->stripAndAccumulateConstantOffsets(
408  DL, Offset, /* AllowNonInbounds */ true));
409  auto *GV = dyn_cast<GlobalVariable>(Ptr);
410  if (!GV) {
411  LLVM_DEBUG(dbgs() << "Memset with unknown base.\n");
412  return false;
413  }
414 
415  Constant *Val = getVal(MSI->getValue());
416  APInt Len = LenC->getValue();
417  while (Len != 0) {
418  Constant *DestVal = ComputeLoadResult(GV, Val->getType(), Offset);
419  if (DestVal != Val) {
420  LLVM_DEBUG(dbgs() << "Memset is not a no-op at offset "
421  << Offset << " of " << *GV << ".\n");
422  return false;
423  }
424  ++Offset;
425  --Len;
426  }
427 
428  LLVM_DEBUG(dbgs() << "Ignoring no-op memset.\n");
429  ++CurInst;
430  continue;
431  }
432 
433  if (II->isLifetimeStartOrEnd()) {
434  LLVM_DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
435  ++CurInst;
436  continue;
437  }
438 
439  if (II->getIntrinsicID() == Intrinsic::invariant_start) {
440  // We don't insert an entry into Values, as it doesn't have a
441  // meaningful return value.
442  if (!II->use_empty()) {
443  LLVM_DEBUG(dbgs()
444  << "Found unused invariant_start. Can't evaluate.\n");
445  return false;
446  }
447  ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0));
448  Value *PtrArg = getVal(II->getArgOperand(1));
449  Value *Ptr = PtrArg->stripPointerCasts();
450  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
451  Type *ElemTy = GV->getValueType();
452  if (!Size->isMinusOne() &&
453  Size->getValue().getLimitedValue() >=
454  DL.getTypeStoreSize(ElemTy)) {
455  Invariants.insert(GV);
456  LLVM_DEBUG(dbgs() << "Found a global var that is an invariant: "
457  << *GV << "\n");
458  } else {
459  LLVM_DEBUG(dbgs()
460  << "Found a global var, but can not treat it as an "
461  "invariant.\n");
462  }
463  }
464  // Continue even if we do nothing.
465  ++CurInst;
466  continue;
467  } else if (II->getIntrinsicID() == Intrinsic::assume) {
468  LLVM_DEBUG(dbgs() << "Skipping assume intrinsic.\n");
469  ++CurInst;
470  continue;
471  } else if (II->getIntrinsicID() == Intrinsic::sideeffect) {
472  LLVM_DEBUG(dbgs() << "Skipping sideeffect intrinsic.\n");
473  ++CurInst;
474  continue;
475  } else if (II->getIntrinsicID() == Intrinsic::pseudoprobe) {
476  LLVM_DEBUG(dbgs() << "Skipping pseudoprobe intrinsic.\n");
477  ++CurInst;
478  continue;
479  } else {
480  Value *Stripped = CurInst->stripPointerCastsForAliasAnalysis();
481  // Only attempt to getVal() if we've actually managed to strip
482  // anything away, or else we'll call getVal() on the current
483  // instruction.
484  if (Stripped != &*CurInst) {
485  InstResult = getVal(Stripped);
486  }
487  if (InstResult) {
488  LLVM_DEBUG(dbgs()
489  << "Stripped pointer casts for alias analysis for "
490  "intrinsic call.\n");
491  StrippedPointerCastsForAliasAnalysis = true;
492  InstResult = ConstantExpr::getBitCast(InstResult, II->getType());
493  } else {
494  LLVM_DEBUG(dbgs() << "Unknown intrinsic. Cannot evaluate.\n");
495  return false;
496  }
497  }
498  }
499 
500  if (!InstResult) {
501  // Resolve function pointers.
503  Function *Callee = getCalleeWithFormalArgs(CB, Formals);
504  if (!Callee || Callee->isInterposable()) {
505  LLVM_DEBUG(dbgs() << "Can not resolve function pointer.\n");
506  return false; // Cannot resolve.
507  }
508 
509  if (Callee->isDeclaration()) {
510  // If this is a function we can constant fold, do it.
511  if (Constant *C = ConstantFoldCall(&CB, Callee, Formals, TLI)) {
512  InstResult = castCallResultIfNeeded(CB.getType(), C);
513  if (!InstResult)
514  return false;
515  LLVM_DEBUG(dbgs() << "Constant folded function call. Result: "
516  << *InstResult << "\n");
517  } else {
518  LLVM_DEBUG(dbgs() << "Can not constant fold function call.\n");
519  return false;
520  }
521  } else {
522  if (Callee->getFunctionType()->isVarArg()) {
523  LLVM_DEBUG(dbgs()
524  << "Can not constant fold vararg function call.\n");
525  return false;
526  }
527 
528  Constant *RetVal = nullptr;
529  // Execute the call, if successful, use the return value.
530  ValueStack.emplace_back();
531  if (!EvaluateFunction(Callee, RetVal, Formals)) {
532  LLVM_DEBUG(dbgs() << "Failed to evaluate function.\n");
533  return false;
534  }
535  ValueStack.pop_back();
536  InstResult = castCallResultIfNeeded(CB.getType(), RetVal);
537  if (RetVal && !InstResult)
538  return false;
539 
540  if (InstResult) {
541  LLVM_DEBUG(dbgs() << "Successfully evaluated function. Result: "
542  << *InstResult << "\n\n");
543  } else {
544  LLVM_DEBUG(dbgs()
545  << "Successfully evaluated function. Result: 0\n\n");
546  }
547  }
548  }
549  } else if (CurInst->isTerminator()) {
550  LLVM_DEBUG(dbgs() << "Found a terminator instruction.\n");
551 
552  if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
553  if (BI->isUnconditional()) {
554  NextBB = BI->getSuccessor(0);
555  } else {
556  ConstantInt *Cond =
557  dyn_cast<ConstantInt>(getVal(BI->getCondition()));
558  if (!Cond) return false; // Cannot determine.
559 
560  NextBB = BI->getSuccessor(!Cond->getZExtValue());
561  }
562  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
563  ConstantInt *Val =
564  dyn_cast<ConstantInt>(getVal(SI->getCondition()));
565  if (!Val) return false; // Cannot determine.
566  NextBB = SI->findCaseValue(Val)->getCaseSuccessor();
567  } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
568  Value *Val = getVal(IBI->getAddress())->stripPointerCasts();
569  if (BlockAddress *BA = dyn_cast<BlockAddress>(Val))
570  NextBB = BA->getBasicBlock();
571  else
572  return false; // Cannot determine.
573  } else if (isa<ReturnInst>(CurInst)) {
574  NextBB = nullptr;
575  } else {
576  // invoke, unwind, resume, unreachable.
577  LLVM_DEBUG(dbgs() << "Can not handle terminator.");
578  return false; // Cannot handle this terminator.
579  }
580 
581  // We succeeded at evaluating this block!
582  LLVM_DEBUG(dbgs() << "Successfully evaluated block.\n");
583  return true;
584  } else {
586  for (Value *Op : CurInst->operands())
587  Ops.push_back(getVal(Op));
588  InstResult = ConstantFoldInstOperands(&*CurInst, Ops, DL, TLI);
589  if (!InstResult) {
590  LLVM_DEBUG(dbgs() << "Cannot fold instruction: " << *CurInst << "\n");
591  return false;
592  }
593  LLVM_DEBUG(dbgs() << "Folded instruction " << *CurInst << " to "
594  << *InstResult << "\n");
595  }
596 
597  if (!CurInst->use_empty()) {
598  InstResult = ConstantFoldConstant(InstResult, DL, TLI);
599  setVal(&*CurInst, InstResult);
600  }
601 
602  // If we just processed an invoke, we finished evaluating the block.
603  if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
604  NextBB = II->getNormalDest();
605  LLVM_DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");
606  return true;
607  }
608 
609  // Advance program counter.
610  ++CurInst;
611  }
612 }
613 
614 /// Evaluate a call to function F, returning true if successful, false if we
615 /// can't evaluate it. ActualArgs contains the formal arguments for the
616 /// function.
618  const SmallVectorImpl<Constant*> &ActualArgs) {
619  assert(ActualArgs.size() == F->arg_size() && "wrong number of arguments");
620 
621  // Check to see if this function is already executing (recursion). If so,
622  // bail out. TODO: we might want to accept limited recursion.
623  if (is_contained(CallStack, F))
624  return false;
625 
626  CallStack.push_back(F);
627 
628  // Initialize arguments to the incoming values specified.
629  for (const auto &[ArgNo, Arg] : llvm::enumerate(F->args()))
630  setVal(&Arg, ActualArgs[ArgNo]);
631 
632  // ExecutedBlocks - We only handle non-looping, non-recursive code. As such,
633  // we can only evaluate any one basic block at most once. This set keeps
634  // track of what we have executed so we can detect recursive cases etc.
635  SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
636 
637  // CurBB - The current basic block we're evaluating.
638  BasicBlock *CurBB = &F->front();
639 
640  BasicBlock::iterator CurInst = CurBB->begin();
641 
642  while (true) {
643  BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
644  LLVM_DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
645 
646  bool StrippedPointerCastsForAliasAnalysis = false;
647 
648  if (!EvaluateBlock(CurInst, NextBB, StrippedPointerCastsForAliasAnalysis))
649  return false;
650 
651  if (!NextBB) {
652  // Successfully running until there's no next block means that we found
653  // the return. Fill it the return value and pop the call stack.
654  ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator());
655  if (RI->getNumOperands()) {
656  // The Evaluator can look through pointer casts as long as alias
657  // analysis holds because it's just a simple interpreter and doesn't
658  // skip memory accesses due to invariant group metadata, but we can't
659  // let users of Evaluator use a value that's been gleaned looking
660  // through stripping pointer casts.
661  if (StrippedPointerCastsForAliasAnalysis &&
662  !RI->getReturnValue()->getType()->isVoidTy()) {
663  return false;
664  }
665  RetVal = getVal(RI->getOperand(0));
666  }
667  CallStack.pop_back();
668  return true;
669  }
670 
671  // Okay, we succeeded in evaluating this control flow. See if we have
672  // executed the new block before. If so, we have a looping function,
673  // which we cannot evaluate in reasonable time.
674  if (!ExecutedBlocks.insert(NextBB).second)
675  return false; // looped!
676 
677  // Okay, we have never been in this block before. Check to see if there
678  // are any PHI nodes. If so, evaluate them with information about where
679  // we came from.
680  PHINode *PN = nullptr;
681  for (CurInst = NextBB->begin();
682  (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)
683  setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB)));
684 
685  // Advance to the next block.
686  CurBB = NextBB;
687  }
688 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:77
i
i
Definition: README.txt:29
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::GlobalVariable::hasUniqueInitializer
bool hasUniqueInitializer() const
hasUniqueInitializer - Whether the global variable has an initializer, and any changes made to the in...
Definition: GlobalVariable.h:121
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:617
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:3051
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:237
llvm::Function
Definition: Function.h:60
getFunction
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:236
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:1306
llvm::GlobalValue::NotThreadLocal
@ NotThreadLocal
Definition: GlobalValue.h:192
llvm::ReturnInst::getReturnValue
Value * getReturnValue() const
Convenience accessor. Returns null if there is no return value.
Definition: Instructions.h:3096
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::LinearPolySize< TypeSize >::isKnownLE
static bool isKnownLE(const LinearPolySize &LHS, const LinearPolySize &RHS)
Definition: TypeSize.h:340
llvm::enumerate
detail::enumerator< R > enumerate(R &&TheRange)
Given an input range, returns a new range whose values are are pair (A,B) such that A is the 0-based ...
Definition: STLExtras.h:2238
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:2202
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::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
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:187
Instruction.h
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
GlobalValue.h
Constants.h
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:2188
InstrTypes.h
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:306
SI
@ SI
Definition: SIInstrInfo.cpp:7882
llvm::ConstantExpr::getPtrToInt
static Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2174
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:3245
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2883
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1713
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::omp::RTLDependInfoFields::Len
@ Len
llvm::MemSetInst
This class wraps the llvm.memset and llvm.memset.inline intrinsics.
Definition: IntrinsicInst.h:1073
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:348
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3810
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:210
BasicBlock.h
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:297
llvm::GlobalVariable::getInitializer
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
Definition: GlobalVariable.h:135
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::AMDGPU::Hwreg::Offset
Offset
Definition: SIDefines.h:416
llvm::GlobalVariable::hasDefinitiveInitializer
bool hasDefinitiveInitializer() const
hasDefinitiveInitializer - Whether the global variable has an initializer, and any other instances of...
Definition: GlobalVariable.h:109
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
I
#define I(x, y, z)
Definition: MD5.cpp:58
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:1843
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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:701
Ptr
@ Ptr
Definition: TargetLibraryInfo.cpp:60
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::ConstantFoldInstOperands
Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
Definition: ConstantFolding.cpp:1213
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:698
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:3600
llvm::ConstantVector::get
static Constant * get(ArrayRef< Constant * > V)
Definition: Constants.cpp:1348
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:173
llvm::Constant::stripPointerCasts
const Constant * stripPointerCasts() const
Definition: Constant.h:209
llvm::Value::stripPointerCasts
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:685
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:187
Constant.h
llvm::AArch64::Alias
StringRef Alias
Definition: AArch64TargetParser.h:135
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:348
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:1241
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:3675
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:2698
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:1207
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
llvm::GlobalValue::getValueType
Type * getValueType() const
Definition: GlobalValue.h:290
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3277
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:3133
raw_ostream.h
Value.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
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