LLVM  13.0.0git
Evaluator.h
Go to the documentation of this file.
1 //===- Evaluator.h - LLVM IR evaluator --------------------------*- C++ -*-===//
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 
13 #ifndef LLVM_TRANSFORMS_UTILS_EVALUATOR_H
14 #define LLVM_TRANSFORMS_UTILS_EVALUATOR_H
15 
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/IR/BasicBlock.h"
20 #include "llvm/IR/GlobalVariable.h"
21 #include "llvm/IR/Instructions.h"
22 #include "llvm/IR/Value.h"
23 #include "llvm/Support/Casting.h"
24 #include <cassert>
25 #include <deque>
26 #include <memory>
27 
28 namespace llvm {
29 
30 class DataLayout;
31 class Function;
32 class TargetLibraryInfo;
33 
34 /// This class evaluates LLVM IR, producing the Constant representing each SSA
35 /// instruction. Changes to global variables are stored in a mapping that can
36 /// be iterated over after the evaluation is complete. Once an evaluation call
37 /// fails, the evaluation object should not be reused.
38 class Evaluator {
39 public:
40  Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
41  : DL(DL), TLI(TLI) {
42  ValueStack.emplace_back();
43  }
44 
46  for (auto &Tmp : AllocaTmps)
47  // If there are still users of the alloca, the program is doing something
48  // silly, e.g. storing the address of the alloca somewhere and using it
49  // later. Since this is undefined, we'll just make it be null.
50  if (!Tmp->use_empty())
51  Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType()));
52  }
53 
54  /// Evaluate a call to function F, returning true if successful, false if we
55  /// can't evaluate it. ActualArgs contains the formal arguments for the
56  /// function.
57  bool EvaluateFunction(Function *F, Constant *&RetVal,
58  const SmallVectorImpl<Constant*> &ActualArgs);
59 
61  return MutatedMemory;
62  }
63 
65  return Invariants;
66  }
67 
68 private:
69  bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB,
70  bool &StrippedPointerCastsForAliasAnalysis);
71 
72  Constant *getVal(Value *V) {
73  if (Constant *CV = dyn_cast<Constant>(V)) return CV;
74  Constant *R = ValueStack.back().lookup(V);
75  assert(R && "Reference to an uncomputed value!");
76  return R;
77  }
78 
79  void setVal(Value *V, Constant *C) {
80  ValueStack.back()[V] = C;
81  }
82 
83  /// Casts call result to a type of bitcast call expression
84  Constant *castCallResultIfNeeded(Value *CallExpr, Constant *RV);
85 
86  /// Given call site return callee and list of its formal arguments
87  Function *getCalleeWithFormalArgs(CallBase &CB,
88  SmallVectorImpl<Constant *> &Formals);
89 
90  /// Given call site and callee returns list of callee formal argument
91  /// values converting them when necessary
92  bool getFormalParams(CallBase &CB, Function *F,
93  SmallVectorImpl<Constant *> &Formals);
94 
95  Constant *ComputeLoadResult(Constant *P, Type *Ty);
96 
97  /// As we compute SSA register values, we store their contents here. The back
98  /// of the deque contains the current function and the stack contains the
99  /// values in the calling frames.
100  std::deque<DenseMap<Value*, Constant*>> ValueStack;
101 
102  /// This is used to detect recursion. In pathological situations we could hit
103  /// exponential behavior, but at least there is nothing unbounded.
104  SmallVector<Function*, 4> CallStack;
105 
106  /// For each store we execute, we update this map. Loads check this to get
107  /// the most up-to-date value. If evaluation is successful, this state is
108  /// committed to the process.
109  DenseMap<Constant*, Constant*> MutatedMemory;
110 
111  /// To 'execute' an alloca, we create a temporary global variable to represent
112  /// its body. This vector is needed so we can delete the temporary globals
113  /// when we are done.
114  SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps;
115 
116  /// These global variables have been marked invariant by the static
117  /// constructor.
118  SmallPtrSet<GlobalVariable*, 8> Invariants;
119 
120  /// These are constants we have checked and know to be simple enough to live
121  /// in a static initializer of a global.
122  SmallPtrSet<Constant*, 8> SimpleConstants;
123 
124  const DataLayout &DL;
125  const TargetLibraryInfo *TLI;
126 };
127 
128 } // end namespace llvm
129 
130 #endif // LLVM_TRANSFORMS_UTILS_EVALUATOR_H
llvm
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:689
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::Function
Definition: Function.h:61
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
DenseMap.h
CallExpr
Definition: ItaniumDemangle.h:1755
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::ISD::Constant
@ Constant
Definition: ISDOpcodes.h:69
llvm::Evaluator::Evaluator
Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
Definition: Evaluator.h:40
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
SmallPtrSet.h
llvm::Evaluator::getInvariants
const SmallPtrSetImpl< GlobalVariable * > & getInvariants() const
Definition: Evaluator.h:64
BasicBlock.h
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::DenseMap
Definition: DenseMap.h:714
llvm::Evaluator
This class evaluates LLVM IR, producing the Constant representing each SSA instruction.
Definition: Evaluator.h:38
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:347
llvm::Evaluator::getMutatedMemory
const DenseMap< Constant *, Constant * > & getMutatedMemory() const
Definition: Evaluator.h:60
GlobalVariable.h
Casting.h
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:207
Instructions.h
SmallVector.h
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
Value.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::Evaluator::~Evaluator
~Evaluator()
Definition: Evaluator.h:45
llvm::codeview::PublicSymFlags::Function
@ Function