LLVM  14.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  struct MutableAggregate;
40 
41  /// The evaluator represents values either as a Constant*, or as a
42  /// MutableAggregate, which allows changing individual aggregate elements
43  /// without creating a new interned Constant.
44  class MutableValue {
46  void clear();
47  bool makeMutable();
48 
49  public:
50  MutableValue(Constant *C) { Val = C; }
51  MutableValue(const MutableValue &) = delete;
52  MutableValue(MutableValue &&Other) {
53  Val = Other.Val;
54  Other.Val = nullptr;
55  }
56  ~MutableValue() { clear(); }
57 
58  Type *getType() const {
59  if (auto *C = Val.dyn_cast<Constant *>())
60  return C->getType();
61  return Val.get<MutableAggregate *>()->Ty;
62  }
63 
64  Constant *toConstant() const {
65  if (auto *C = Val.dyn_cast<Constant *>())
66  return C;
67  return Val.get<MutableAggregate *>()->toConstant();
68  }
69 
70  Constant *read(Type *Ty, APInt Offset, const DataLayout &DL) const;
71  bool write(Constant *V, APInt Offset, const DataLayout &DL);
72  };
73 
74  struct MutableAggregate {
75  Type *Ty;
77 
78  MutableAggregate(Type *Ty) : Ty(Ty) {}
79  Constant *toConstant() const;
80  };
81 
82 public:
83  Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
84  : DL(DL), TLI(TLI) {
85  ValueStack.emplace_back();
86  }
87 
89  for (auto &Tmp : AllocaTmps)
90  // If there are still users of the alloca, the program is doing something
91  // silly, e.g. storing the address of the alloca somewhere and using it
92  // later. Since this is undefined, we'll just make it be null.
93  if (!Tmp->use_empty())
94  Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType()));
95  }
96 
97  /// Evaluate a call to function F, returning true if successful, false if we
98  /// can't evaluate it. ActualArgs contains the formal arguments for the
99  /// function.
100  bool EvaluateFunction(Function *F, Constant *&RetVal,
101  const SmallVectorImpl<Constant*> &ActualArgs);
102 
105  for (auto &Pair : MutatedMemory)
106  Result[Pair.first] = Pair.second.toConstant();
107  return Result;
108  }
109 
111  return Invariants;
112  }
113 
114 private:
115  bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB,
116  bool &StrippedPointerCastsForAliasAnalysis);
117 
118  Constant *getVal(Value *V) {
119  if (Constant *CV = dyn_cast<Constant>(V)) return CV;
120  Constant *R = ValueStack.back().lookup(V);
121  assert(R && "Reference to an uncomputed value!");
122  return R;
123  }
124 
125  void setVal(Value *V, Constant *C) {
126  ValueStack.back()[V] = C;
127  }
128 
129  /// Casts call result to a type of bitcast call expression
130  Constant *castCallResultIfNeeded(Value *CallExpr, Constant *RV);
131 
132  /// Given call site return callee and list of its formal arguments
133  Function *getCalleeWithFormalArgs(CallBase &CB,
134  SmallVectorImpl<Constant *> &Formals);
135 
136  /// Given call site and callee returns list of callee formal argument
137  /// values converting them when necessary
138  bool getFormalParams(CallBase &CB, Function *F,
139  SmallVectorImpl<Constant *> &Formals);
140 
141  Constant *ComputeLoadResult(Constant *P, Type *Ty);
142 
143  /// As we compute SSA register values, we store their contents here. The back
144  /// of the deque contains the current function and the stack contains the
145  /// values in the calling frames.
146  std::deque<DenseMap<Value*, Constant*>> ValueStack;
147 
148  /// This is used to detect recursion. In pathological situations we could hit
149  /// exponential behavior, but at least there is nothing unbounded.
150  SmallVector<Function*, 4> CallStack;
151 
152  /// For each store we execute, we update this map. Loads check this to get
153  /// the most up-to-date value. If evaluation is successful, this state is
154  /// committed to the process.
155  DenseMap<GlobalVariable *, MutableValue> MutatedMemory;
156 
157  /// To 'execute' an alloca, we create a temporary global variable to represent
158  /// its body. This vector is needed so we can delete the temporary globals
159  /// when we are done.
160  SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps;
161 
162  /// These global variables have been marked invariant by the static
163  /// constructor.
164  SmallPtrSet<GlobalVariable*, 8> Invariants;
165 
166  /// These are constants we have checked and know to be simple enough to live
167  /// in a static initializer of a global.
168  SmallPtrSet<Constant*, 8> SimpleConstants;
169 
170  const DataLayout &DL;
171  const TargetLibraryInfo *TLI;
172 };
173 
174 } // end namespace llvm
175 
176 #endif // LLVM_TRANSFORMS_UTILS_EVALUATOR_H
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::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
llvm::Function
Definition: Function.h:62
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::write
Error write(MCStreamer &Out, ArrayRef< std::string > Inputs)
Definition: DWP.cpp:535
llvm::SmallVector< MutableValue >
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
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:80
llvm::PointerUnion::get
T get() const
Returns the value of the specified pointer type.
Definition: PointerUnion.h:144
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
clear
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:233
llvm::Intrinsic::getType
FunctionType * getType(LLVMContext &Context, ID id, ArrayRef< Type * > Tys=None)
Return the function type for an intrinsic.
Definition: Function.cpp:1355
llvm::ISD::Constant
@ Constant
Definition: ISDOpcodes.h:76
llvm::Evaluator::Evaluator
Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
Definition: Evaluator.h:83
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::Evaluator::getMutatedInitializers
DenseMap< GlobalVariable *, Constant * > getMutatedInitializers() const
Definition: Evaluator.h:103
SmallPtrSet.h
llvm::Evaluator::getInvariants
const SmallPtrSetImpl< GlobalVariable * > & getInvariants() const
Definition: Evaluator.h:110
BasicBlock.h
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::PointerUnion::dyn_cast
T dyn_cast() const
Returns the current pointer if it is of the specified pointer type, otherwise returns null.
Definition: PointerUnion.h:151
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())
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::PointerUnion
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
Definition: PointerUnion.h:107
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp: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
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:221
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:74
llvm::Evaluator::~Evaluator
~Evaluator()
Definition: Evaluator.h:88
llvm::codeview::PublicSymFlags::Function
@ Function
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1198