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 
126  if (auto *Agg = Val.dyn_cast<MutableAggregate *>())
127  delete Agg;
128  Val = nullptr;
129 }
130 
132  const DataLayout &DL) const {
133  TypeSize TySize = DL.getTypeStoreSize(Ty);
134  const MutableValue *V = this;
135  while (const auto *Agg = V->Val.dyn_cast<MutableAggregate *>()) {
136  Type *AggTy = Agg->Ty;
137  Optional<APInt> Index = DL.getGEPIndexForOffset(AggTy, Offset);
138  if (!Index || Index->uge(Agg->Elements.size()) ||
139  !TypeSize::isKnownLE(TySize, DL.getTypeStoreSize(AggTy)))
140  return nullptr;
141 
142  V = &Agg->Elements[Index->getZExtValue()];
143  }
144 
145  return ConstantFoldLoadFromConst(V->Val.get<Constant *>(), Ty, Offset, DL);
146 }
147 
148 bool Evaluator::MutableValue::makeMutable() {
149  Constant *C = Val.get<Constant *>();
150  Type *Ty = C->getType();
151  unsigned NumElements;
152  if (auto *VT = dyn_cast<FixedVectorType>(Ty)) {
153  NumElements = VT->getNumElements();
154  } else if (auto *AT = dyn_cast<ArrayType>(Ty))
155  NumElements = AT->getNumElements();
156  else if (auto *ST = dyn_cast<StructType>(Ty))
157  NumElements = ST->getNumElements();
158  else
159  return false;
160 
161  MutableAggregate *MA = new MutableAggregate(Ty);
162  MA->Elements.reserve(NumElements);
163  for (unsigned I = 0; I < NumElements; ++I)
164  MA->Elements.push_back(C->getAggregateElement(I));
165  Val = MA;
166  return true;
167 }
168 
170  const DataLayout &DL) {
171  Type *Ty = V->getType();
172  TypeSize TySize = DL.getTypeStoreSize(Ty);
173  MutableValue *MV = this;
174  while (Offset != 0 ||
175  !CastInst::isBitOrNoopPointerCastable(Ty, MV->getType(), DL)) {
176  if (MV->Val.is<Constant *>() && !MV->makeMutable())
177  return false;
178 
179  MutableAggregate *Agg = MV->Val.get<MutableAggregate *>();
180  Type *AggTy = Agg->Ty;
181  Optional<APInt> Index = DL.getGEPIndexForOffset(AggTy, Offset);
182  if (!Index || Index->uge(Agg->Elements.size()) ||
183  !TypeSize::isKnownLE(TySize, DL.getTypeStoreSize(AggTy)))
184  return false;
185 
186  MV = &Agg->Elements[Index->getZExtValue()];
187  }
188 
189  Type *MVType = MV->getType();
190  MV->clear();
191  if (Ty->isIntegerTy() && MVType->isPointerTy())
192  MV->Val = ConstantExpr::getIntToPtr(V, MVType);
193  else if (Ty->isPointerTy() && MVType->isIntegerTy())
194  MV->Val = ConstantExpr::getPtrToInt(V, MVType);
195  else if (Ty != MVType)
196  MV->Val = ConstantExpr::getBitCast(V, MVType);
197  else
198  MV->Val = V;
199  return true;
200 }
201 
202 Constant *Evaluator::MutableAggregate::toConstant() const {
204  for (const MutableValue &MV : Elements)
205  Consts.push_back(MV.toConstant());
206 
207  if (auto *ST = dyn_cast<StructType>(Ty))
208  return ConstantStruct::get(ST, Consts);
209  if (auto *AT = dyn_cast<ArrayType>(Ty))
210  return ConstantArray::get(AT, Consts);
211  assert(isa<FixedVectorType>(Ty) && "Must be vector");
212  return ConstantVector::get(Consts);
213 }
214 
215 /// Return the value that would be computed by a load from P after the stores
216 /// reflected by 'memory' have been performed. If we can't decide, return null.
217 Constant *Evaluator::ComputeLoadResult(Constant *P, Type *Ty) {
218  APInt Offset(DL.getIndexTypeSizeInBits(P->getType()), 0);
219  P = cast<Constant>(P->stripAndAccumulateConstantOffsets(
220  DL, Offset, /* AllowNonInbounds */ true));
221  Offset = Offset.sextOrTrunc(DL.getIndexTypeSizeInBits(P->getType()));
222  auto *GV = dyn_cast<GlobalVariable>(P);
223  if (!GV)
224  return nullptr;
225 
226  auto It = MutatedMemory.find(GV);
227  if (It != MutatedMemory.end())
228  return It->second.read(Ty, Offset, DL);
229 
230  if (!GV->hasDefinitiveInitializer())
231  return nullptr;
232  return ConstantFoldLoadFromConst(GV->getInitializer(), Ty, Offset, DL);
233 }
234 
236  if (auto *Fn = dyn_cast<Function>(C))
237  return Fn;
238 
239  if (auto *Alias = dyn_cast<GlobalAlias>(C))
240  if (auto *Fn = dyn_cast<Function>(Alias->getAliasee()))
241  return Fn;
242  return nullptr;
243 }
244 
245 Function *
246 Evaluator::getCalleeWithFormalArgs(CallBase &CB,
247  SmallVectorImpl<Constant *> &Formals) {
248  auto *V = CB.getCalledOperand();
249  if (auto *Fn = getFunction(getVal(V)))
250  return getFormalParams(CB, Fn, Formals) ? Fn : nullptr;
251 
252  auto *CE = dyn_cast<ConstantExpr>(V);
253  if (!CE || CE->getOpcode() != Instruction::BitCast ||
254  !getFormalParams(CB, getFunction(CE->getOperand(0)), Formals))
255  return nullptr;
256 
257  return dyn_cast<Function>(
258  ConstantFoldLoadThroughBitcast(CE, CE->getOperand(0)->getType(), DL));
259 }
260 
261 bool Evaluator::getFormalParams(CallBase &CB, Function *F,
262  SmallVectorImpl<Constant *> &Formals) {
263  if (!F)
264  return false;
265 
266  auto *FTy = F->getFunctionType();
267  if (FTy->getNumParams() > CB.arg_size()) {
268  LLVM_DEBUG(dbgs() << "Too few arguments for function.\n");
269  return false;
270  }
271 
272  auto ArgI = CB.arg_begin();
273  for (Type *PTy : FTy->params()) {
274  auto *ArgC = ConstantFoldLoadThroughBitcast(getVal(*ArgI), PTy, DL);
275  if (!ArgC) {
276  LLVM_DEBUG(dbgs() << "Can not convert function argument.\n");
277  return false;
278  }
279  Formals.push_back(ArgC);
280  ++ArgI;
281  }
282  return true;
283 }
284 
285 /// If call expression contains bitcast then we may need to cast
286 /// evaluated return value to a type of the call expression.
287 Constant *Evaluator::castCallResultIfNeeded(Value *CallExpr, Constant *RV) {
288  ConstantExpr *CE = dyn_cast<ConstantExpr>(CallExpr);
289  if (!RV || !CE || CE->getOpcode() != Instruction::BitCast)
290  return RV;
291 
292  if (auto *FT =
293  dyn_cast<FunctionType>(CE->getType()->getPointerElementType())) {
294  RV = ConstantFoldLoadThroughBitcast(RV, FT->getReturnType(), DL);
295  if (!RV)
296  LLVM_DEBUG(dbgs() << "Failed to fold bitcast call expr\n");
297  }
298  return RV;
299 }
300 
301 /// Evaluate all instructions in block BB, returning true if successful, false
302 /// if we can't evaluate it. NewBB returns the next BB that control flows into,
303 /// or null upon return. StrippedPointerCastsForAliasAnalysis is set to true if
304 /// we looked through pointer casts to evaluate something.
305 bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB,
306  bool &StrippedPointerCastsForAliasAnalysis) {
307  // This is the main evaluation loop.
308  while (true) {
309  Constant *InstResult = nullptr;
310 
311  LLVM_DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n");
312 
313  if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
314  if (!SI->isSimple()) {
315  LLVM_DEBUG(dbgs() << "Store is not simple! Can not evaluate.\n");
316  return false; // no volatile/atomic accesses.
317  }
318  Constant *Ptr = getVal(SI->getOperand(1));
319  Constant *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI);
320  if (Ptr != FoldedPtr) {
321  LLVM_DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr);
322  Ptr = FoldedPtr;
323  LLVM_DEBUG(dbgs() << "; To: " << *Ptr << "\n");
324  }
325 
326  APInt Offset(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
327  Ptr = cast<Constant>(Ptr->stripAndAccumulateConstantOffsets(
328  DL, Offset, /* AllowNonInbounds */ true));
329  Offset = Offset.sextOrTrunc(DL.getIndexTypeSizeInBits(Ptr->getType()));
330  auto *GV = dyn_cast<GlobalVariable>(Ptr);
331  if (!GV || !GV->hasUniqueInitializer()) {
332  LLVM_DEBUG(dbgs() << "Store is not to global with unique initializer: "
333  << *Ptr << "\n");
334  return false;
335  }
336 
337  // If this might be too difficult for the backend to handle (e.g. the addr
338  // of one global variable divided by another) then we can't commit it.
339  Constant *Val = getVal(SI->getOperand(0));
340  if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) {
341  LLVM_DEBUG(dbgs() << "Store value is too complex to evaluate store. "
342  << *Val << "\n");
343  return false;
344  }
345 
346  auto Res = MutatedMemory.try_emplace(GV, GV->getInitializer());
347  if (!Res.first->second.write(Val, Offset, DL))
348  return false;
349  } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) {
350  InstResult = ConstantExpr::get(BO->getOpcode(),
351  getVal(BO->getOperand(0)),
352  getVal(BO->getOperand(1)));
353  LLVM_DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: "
354  << *InstResult << "\n");
355  } else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) {
356  InstResult = ConstantExpr::getCompare(CI->getPredicate(),
357  getVal(CI->getOperand(0)),
358  getVal(CI->getOperand(1)));
359  LLVM_DEBUG(dbgs() << "Found a CmpInst! Simplifying: " << *InstResult
360  << "\n");
361  } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) {
362  InstResult = ConstantExpr::getCast(CI->getOpcode(),
363  getVal(CI->getOperand(0)),
364  CI->getType());
365  LLVM_DEBUG(dbgs() << "Found a Cast! Simplifying: " << *InstResult
366  << "\n");
367  } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) {
368  InstResult = ConstantExpr::getSelect(getVal(SI->getOperand(0)),
369  getVal(SI->getOperand(1)),
370  getVal(SI->getOperand(2)));
371  LLVM_DEBUG(dbgs() << "Found a Select! Simplifying: " << *InstResult
372  << "\n");
373  } else if (auto *EVI = dyn_cast<ExtractValueInst>(CurInst)) {
374  InstResult = ConstantExpr::getExtractValue(
375  getVal(EVI->getAggregateOperand()), EVI->getIndices());
376  LLVM_DEBUG(dbgs() << "Found an ExtractValueInst! Simplifying: "
377  << *InstResult << "\n");
378  } else if (auto *IVI = dyn_cast<InsertValueInst>(CurInst)) {
379  InstResult = ConstantExpr::getInsertValue(
380  getVal(IVI->getAggregateOperand()),
381  getVal(IVI->getInsertedValueOperand()), IVI->getIndices());
382  LLVM_DEBUG(dbgs() << "Found an InsertValueInst! Simplifying: "
383  << *InstResult << "\n");
384  } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) {
385  Constant *P = getVal(GEP->getOperand(0));
387  for (Use &Op : llvm::drop_begin(GEP->operands()))
388  GEPOps.push_back(getVal(Op));
389  InstResult =
390  ConstantExpr::getGetElementPtr(GEP->getSourceElementType(), P, GEPOps,
391  cast<GEPOperator>(GEP)->isInBounds());
392  LLVM_DEBUG(dbgs() << "Found a GEP! Simplifying: " << *InstResult << "\n");
393  } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
394  if (!LI->isSimple()) {
395  LLVM_DEBUG(
396  dbgs() << "Found a Load! Not a simple load, can not evaluate.\n");
397  return false; // no volatile/atomic accesses.
398  }
399 
400  Constant *Ptr = getVal(LI->getOperand(0));
401  Constant *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI);
402  if (Ptr != FoldedPtr) {
403  Ptr = FoldedPtr;
404  LLVM_DEBUG(dbgs() << "Found a constant pointer expression, constant "
405  "folding: "
406  << *Ptr << "\n");
407  }
408  InstResult = ComputeLoadResult(Ptr, LI->getType());
409  if (!InstResult) {
410  LLVM_DEBUG(
411  dbgs() << "Failed to compute load result. Can not evaluate load."
412  "\n");
413  return false; // Could not evaluate load.
414  }
415 
416  LLVM_DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n");
417  } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) {
418  if (AI->isArrayAllocation()) {
419  LLVM_DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n");
420  return false; // Cannot handle array allocs.
421  }
422  Type *Ty = AI->getAllocatedType();
423  AllocaTmps.push_back(std::make_unique<GlobalVariable>(
425  AI->getName(), /*TLMode=*/GlobalValue::NotThreadLocal,
426  AI->getType()->getPointerAddressSpace()));
427  InstResult = AllocaTmps.back().get();
428  LLVM_DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n");
429  } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) {
430  CallBase &CB = *cast<CallBase>(&*CurInst);
431 
432  // Debug info can safely be ignored here.
433  if (isa<DbgInfoIntrinsic>(CB)) {
434  LLVM_DEBUG(dbgs() << "Ignoring debug info.\n");
435  ++CurInst;
436  continue;
437  }
438 
439  // Cannot handle inline asm.
440  if (CB.isInlineAsm()) {
441  LLVM_DEBUG(dbgs() << "Found inline asm, can not evaluate.\n");
442  return false;
443  }
444 
445  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&CB)) {
446  if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) {
447  if (MSI->isVolatile()) {
448  LLVM_DEBUG(dbgs() << "Can not optimize a volatile memset "
449  << "intrinsic.\n");
450  return false;
451  }
452  Constant *Ptr = getVal(MSI->getDest());
453  Constant *Val = getVal(MSI->getValue());
454  Constant *DestVal =
455  ComputeLoadResult(getVal(Ptr), MSI->getValue()->getType());
456  if (Val->isNullValue() && DestVal && DestVal->isNullValue()) {
457  // This memset is a no-op.
458  LLVM_DEBUG(dbgs() << "Ignoring no-op memset.\n");
459  ++CurInst;
460  continue;
461  }
462  }
463 
464  if (II->isLifetimeStartOrEnd()) {
465  LLVM_DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
466  ++CurInst;
467  continue;
468  }
469 
470  if (II->getIntrinsicID() == Intrinsic::invariant_start) {
471  // We don't insert an entry into Values, as it doesn't have a
472  // meaningful return value.
473  if (!II->use_empty()) {
474  LLVM_DEBUG(dbgs()
475  << "Found unused invariant_start. Can't evaluate.\n");
476  return false;
477  }
478  ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0));
479  Value *PtrArg = getVal(II->getArgOperand(1));
480  Value *Ptr = PtrArg->stripPointerCasts();
481  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
482  Type *ElemTy = GV->getValueType();
483  if (!Size->isMinusOne() &&
484  Size->getValue().getLimitedValue() >=
485  DL.getTypeStoreSize(ElemTy)) {
486  Invariants.insert(GV);
487  LLVM_DEBUG(dbgs() << "Found a global var that is an invariant: "
488  << *GV << "\n");
489  } else {
490  LLVM_DEBUG(dbgs()
491  << "Found a global var, but can not treat it as an "
492  "invariant.\n");
493  }
494  }
495  // Continue even if we do nothing.
496  ++CurInst;
497  continue;
498  } else if (II->getIntrinsicID() == Intrinsic::assume) {
499  LLVM_DEBUG(dbgs() << "Skipping assume intrinsic.\n");
500  ++CurInst;
501  continue;
502  } else if (II->getIntrinsicID() == Intrinsic::sideeffect) {
503  LLVM_DEBUG(dbgs() << "Skipping sideeffect intrinsic.\n");
504  ++CurInst;
505  continue;
506  } else if (II->getIntrinsicID() == Intrinsic::pseudoprobe) {
507  LLVM_DEBUG(dbgs() << "Skipping pseudoprobe intrinsic.\n");
508  ++CurInst;
509  continue;
510  } else {
511  Value *Stripped = CurInst->stripPointerCastsForAliasAnalysis();
512  // Only attempt to getVal() if we've actually managed to strip
513  // anything away, or else we'll call getVal() on the current
514  // instruction.
515  if (Stripped != &*CurInst) {
516  InstResult = getVal(Stripped);
517  }
518  if (InstResult) {
519  LLVM_DEBUG(dbgs()
520  << "Stripped pointer casts for alias analysis for "
521  "intrinsic call.\n");
522  StrippedPointerCastsForAliasAnalysis = true;
523  InstResult = ConstantExpr::getBitCast(InstResult, II->getType());
524  } else {
525  LLVM_DEBUG(dbgs() << "Unknown intrinsic. Cannot evaluate.\n");
526  return false;
527  }
528  }
529  }
530 
531  if (!InstResult) {
532  // Resolve function pointers.
534  Function *Callee = getCalleeWithFormalArgs(CB, Formals);
535  if (!Callee || Callee->isInterposable()) {
536  LLVM_DEBUG(dbgs() << "Can not resolve function pointer.\n");
537  return false; // Cannot resolve.
538  }
539 
540  if (Callee->isDeclaration()) {
541  // If this is a function we can constant fold, do it.
542  if (Constant *C = ConstantFoldCall(&CB, Callee, Formals, TLI)) {
543  InstResult = castCallResultIfNeeded(CB.getCalledOperand(), C);
544  if (!InstResult)
545  return false;
546  LLVM_DEBUG(dbgs() << "Constant folded function call. Result: "
547  << *InstResult << "\n");
548  } else {
549  LLVM_DEBUG(dbgs() << "Can not constant fold function call.\n");
550  return false;
551  }
552  } else {
553  if (Callee->getFunctionType()->isVarArg()) {
554  LLVM_DEBUG(dbgs()
555  << "Can not constant fold vararg function call.\n");
556  return false;
557  }
558 
559  Constant *RetVal = nullptr;
560  // Execute the call, if successful, use the return value.
561  ValueStack.emplace_back();
562  if (!EvaluateFunction(Callee, RetVal, Formals)) {
563  LLVM_DEBUG(dbgs() << "Failed to evaluate function.\n");
564  return false;
565  }
566  ValueStack.pop_back();
567  InstResult = castCallResultIfNeeded(CB.getCalledOperand(), RetVal);
568  if (RetVal && !InstResult)
569  return false;
570 
571  if (InstResult) {
572  LLVM_DEBUG(dbgs() << "Successfully evaluated function. Result: "
573  << *InstResult << "\n\n");
574  } else {
575  LLVM_DEBUG(dbgs()
576  << "Successfully evaluated function. Result: 0\n\n");
577  }
578  }
579  }
580  } else if (CurInst->isTerminator()) {
581  LLVM_DEBUG(dbgs() << "Found a terminator instruction.\n");
582 
583  if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
584  if (BI->isUnconditional()) {
585  NextBB = BI->getSuccessor(0);
586  } else {
587  ConstantInt *Cond =
588  dyn_cast<ConstantInt>(getVal(BI->getCondition()));
589  if (!Cond) return false; // Cannot determine.
590 
591  NextBB = BI->getSuccessor(!Cond->getZExtValue());
592  }
593  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
594  ConstantInt *Val =
595  dyn_cast<ConstantInt>(getVal(SI->getCondition()));
596  if (!Val) return false; // Cannot determine.
597  NextBB = SI->findCaseValue(Val)->getCaseSuccessor();
598  } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
599  Value *Val = getVal(IBI->getAddress())->stripPointerCasts();
600  if (BlockAddress *BA = dyn_cast<BlockAddress>(Val))
601  NextBB = BA->getBasicBlock();
602  else
603  return false; // Cannot determine.
604  } else if (isa<ReturnInst>(CurInst)) {
605  NextBB = nullptr;
606  } else {
607  // invoke, unwind, resume, unreachable.
608  LLVM_DEBUG(dbgs() << "Can not handle terminator.");
609  return false; // Cannot handle this terminator.
610  }
611 
612  // We succeeded at evaluating this block!
613  LLVM_DEBUG(dbgs() << "Successfully evaluated block.\n");
614  return true;
615  } else {
616  // Did not know how to evaluate this!
617  LLVM_DEBUG(
618  dbgs() << "Failed to evaluate block due to unhandled instruction."
619  "\n");
620  return false;
621  }
622 
623  if (!CurInst->use_empty()) {
624  InstResult = ConstantFoldConstant(InstResult, DL, TLI);
625  setVal(&*CurInst, InstResult);
626  }
627 
628  // If we just processed an invoke, we finished evaluating the block.
629  if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
630  NextBB = II->getNormalDest();
631  LLVM_DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");
632  return true;
633  }
634 
635  // Advance program counter.
636  ++CurInst;
637  }
638 }
639 
640 /// Evaluate a call to function F, returning true if successful, false if we
641 /// can't evaluate it. ActualArgs contains the formal arguments for the
642 /// function.
644  const SmallVectorImpl<Constant*> &ActualArgs) {
645  // Check to see if this function is already executing (recursion). If so,
646  // bail out. TODO: we might want to accept limited recursion.
647  if (is_contained(CallStack, F))
648  return false;
649 
650  CallStack.push_back(F);
651 
652  // Initialize arguments to the incoming values specified.
653  unsigned ArgNo = 0;
654  for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
655  ++AI, ++ArgNo)
656  setVal(&*AI, ActualArgs[ArgNo]);
657 
658  // ExecutedBlocks - We only handle non-looping, non-recursive code. As such,
659  // we can only evaluate any one basic block at most once. This set keeps
660  // track of what we have executed so we can detect recursive cases etc.
661  SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
662 
663  // CurBB - The current basic block we're evaluating.
664  BasicBlock *CurBB = &F->front();
665 
666  BasicBlock::iterator CurInst = CurBB->begin();
667 
668  while (true) {
669  BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
670  LLVM_DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
671 
672  bool StrippedPointerCastsForAliasAnalysis = false;
673 
674  if (!EvaluateBlock(CurInst, NextBB, StrippedPointerCastsForAliasAnalysis))
675  return false;
676 
677  if (!NextBB) {
678  // Successfully running until there's no next block means that we found
679  // the return. Fill it the return value and pop the call stack.
680  ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator());
681  if (RI->getNumOperands()) {
682  // The Evaluator can look through pointer casts as long as alias
683  // analysis holds because it's just a simple interpreter and doesn't
684  // skip memory accesses due to invariant group metadata, but we can't
685  // let users of Evaluator use a value that's been gleaned looking
686  // through stripping pointer casts.
687  if (StrippedPointerCastsForAliasAnalysis &&
688  !RI->getReturnValue()->getType()->isVoidTy()) {
689  return false;
690  }
691  RetVal = getVal(RI->getOperand(0));
692  }
693  CallStack.pop_back();
694  return true;
695  }
696 
697  // Okay, we succeeded in evaluating this control flow. See if we have
698  // executed the new block before. If so, we have a looping function,
699  // which we cannot evaluate in reasonable time.
700  if (!ExecutedBlocks.insert(NextBB).second)
701  return false; // looped!
702 
703  // Okay, we have never been in this block before. Check to see if there
704  // are any PHI nodes. If so, evaluate them with information about where
705  // we came from.
706  PHINode *PN = nullptr;
707  for (CurInst = NextBB->begin();
708  (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)
709  setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB)));
710 
711  // Advance to the next block.
712  CurBB = NextBB;
713  }
714 }
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
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
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:643
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:321
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:3010
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:90
IntrinsicInst.h
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:217
llvm::Function
Definition: Function.h:62
getFunction
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:235
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:1360
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:3055
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1177
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:1463
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:39
llvm::ConstantExpr::getBitCast
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2260
llvm::ConstantExpr::getSelect
static Constant * getSelect(Constant *C, Constant *V1, Constant *V2, Type *OnlyIfReducedTy=nullptr)
Select constant expr.
Definition: Constants.cpp:2447
llvm::ConstantExpr::getInsertValue
static Constant * getInsertValue(Constant *Agg, Constant *Val, ArrayRef< unsigned > Idxs, Type *OnlyIfReducedTy=nullptr)
Definition: Constants.cpp:2650
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:1898
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.
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:80
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
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:1318
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:58
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:234
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
llvm::ConstantExpr::getIntToPtr
static Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2246
InstrTypes.h
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
llvm::ConstantExpr::getPtrToInt
static Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2232
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:3051
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2842
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1782
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:957
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:348
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3769
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:711
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:190
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:2425
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:309
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
Index
uint32_t Index
Definition: ELFObjHandler.cpp:83
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:2294
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:933
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:1714
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:2015
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
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1741
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::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::BlockAddress
The address of a basic block.
Definition: Constants.h:848
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:671
llvm::BinaryOperator
Definition: InstrTypes.h:190
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: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:3412
llvm::ConstantVector::get
static Constant * get(ArrayRef< Constant * > V)
Definition: Constants.cpp:1402
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:431
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:180
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:152
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:685
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:185
Constant.h
llvm::ConstantExpr
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:971
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:325
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:1341
GlobalVariable.h
llvm::TypeSize
Definition: TypeSize.h:416
Casting.h
Function.h
llvm::ConstantArray::get
static Constant * get(ArrayType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1295
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:1238
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
llvm::CallBase::getCalledOperand
Value * getCalledOperand() const
Definition: InstrTypes.h:1391
llvm::IndirectBrInst
Indirect Branch Instruction.
Definition: Instructions.h:3634
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:2657
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:1179
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1176
DerivedTypes.h
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3236
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:3092
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:2674
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
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:364