LLVM  15.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/Support/Casting.h"
22 #include <cassert>
23 #include <deque>
24 #include <memory>
25 
26 namespace llvm {
27 
28 class CallBase;
29 class DataLayout;
30 class Function;
31 class TargetLibraryInfo;
32 
33 /// This class evaluates LLVM IR, producing the Constant representing each SSA
34 /// instruction. Changes to global variables are stored in a mapping that can
35 /// be iterated over after the evaluation is complete. Once an evaluation call
36 /// fails, the evaluation object should not be reused.
37 class Evaluator {
38  struct MutableAggregate;
39 
40  /// The evaluator represents values either as a Constant*, or as a
41  /// MutableAggregate, which allows changing individual aggregate elements
42  /// without creating a new interned Constant.
43  class MutableValue {
45  void clear();
46  bool makeMutable();
47 
48  public:
49  MutableValue(Constant *C) { Val = C; }
50  MutableValue(const MutableValue &) = delete;
51  MutableValue(MutableValue &&Other) {
52  Val = Other.Val;
53  Other.Val = nullptr;
54  }
55  ~MutableValue() { clear(); }
56 
57  Type *getType() const {
58  if (auto *C = Val.dyn_cast<Constant *>())
59  return C->getType();
60  return Val.get<MutableAggregate *>()->Ty;
61  }
62 
63  Constant *toConstant() const {
64  if (auto *C = Val.dyn_cast<Constant *>())
65  return C;
66  return Val.get<MutableAggregate *>()->toConstant();
67  }
68 
69  Constant *read(Type *Ty, APInt Offset, const DataLayout &DL) const;
70  bool write(Constant *V, APInt Offset, const DataLayout &DL);
71  };
72 
73  struct MutableAggregate {
74  Type *Ty;
76 
77  MutableAggregate(Type *Ty) : Ty(Ty) {}
78  Constant *toConstant() const;
79  };
80 
81 public:
82  Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
83  : DL(DL), TLI(TLI) {
84  ValueStack.emplace_back();
85  }
86 
88  for (auto &Tmp : AllocaTmps)
89  // If there are still users of the alloca, the program is doing something
90  // silly, e.g. storing the address of the alloca somewhere and using it
91  // later. Since this is undefined, we'll just make it be null.
92  if (!Tmp->use_empty())
93  Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType()));
94  }
95 
96  /// Evaluate a call to function F, returning true if successful, false if we
97  /// can't evaluate it. ActualArgs contains the formal arguments for the
98  /// function.
99  bool EvaluateFunction(Function *F, Constant *&RetVal,
100  const SmallVectorImpl<Constant*> &ActualArgs);
101 
104  for (auto &Pair : MutatedMemory)
105  Result[Pair.first] = Pair.second.toConstant();
106  return Result;
107  }
108 
110  return Invariants;
111  }
112 
113 private:
114  bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB,
115  bool &StrippedPointerCastsForAliasAnalysis);
116 
117  Constant *getVal(Value *V) {
118  if (Constant *CV = dyn_cast<Constant>(V)) return CV;
119  Constant *R = ValueStack.back().lookup(V);
120  assert(R && "Reference to an uncomputed value!");
121  return R;
122  }
123 
124  void setVal(Value *V, Constant *C) {
125  ValueStack.back()[V] = C;
126  }
127 
128  /// Casts call result to a type of bitcast call expression
129  Constant *castCallResultIfNeeded(Type *ReturnType, Constant *RV);
130 
131  /// Given call site return callee and list of its formal arguments
132  Function *getCalleeWithFormalArgs(CallBase &CB,
133  SmallVectorImpl<Constant *> &Formals);
134 
135  /// Given call site and callee returns list of callee formal argument
136  /// values converting them when necessary
137  bool getFormalParams(CallBase &CB, Function *F,
138  SmallVectorImpl<Constant *> &Formals);
139 
140  Constant *ComputeLoadResult(Constant *P, Type *Ty);
141  Constant *ComputeLoadResult(GlobalVariable *GV, Type *Ty,
142  const APInt &Offset);
143 
144  /// As we compute SSA register values, we store their contents here. The back
145  /// of the deque contains the current function and the stack contains the
146  /// values in the calling frames.
147  std::deque<DenseMap<Value*, Constant*>> ValueStack;
148 
149  /// This is used to detect recursion. In pathological situations we could hit
150  /// exponential behavior, but at least there is nothing unbounded.
151  SmallVector<Function*, 4> CallStack;
152 
153  /// For each store we execute, we update this map. Loads check this to get
154  /// the most up-to-date value. If evaluation is successful, this state is
155  /// committed to the process.
156  DenseMap<GlobalVariable *, MutableValue> MutatedMemory;
157 
158  /// To 'execute' an alloca, we create a temporary global variable to represent
159  /// its body. This vector is needed so we can delete the temporary globals
160  /// when we are done.
161  SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps;
162 
163  /// These global variables have been marked invariant by the static
164  /// constructor.
165  SmallPtrSet<GlobalVariable*, 8> Invariants;
166 
167  /// These are constants we have checked and know to be simple enough to live
168  /// in a static initializer of a global.
169  SmallPtrSet<Constant*, 8> SimpleConstants;
170 
171  const DataLayout &DL;
172  const TargetLibraryInfo *TLI;
173 };
174 
175 } // end namespace llvm
176 
177 #endif // LLVM_TRANSFORMS_UTILS_EVALUATOR_H
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::Evaluator::EvaluateFunction
bool EvaluateFunction(Function *F, Constant *&RetVal, const SmallVectorImpl< Constant * > &ActualArgs)
Evaluate a call to function F, returning true if successful, false if we can't evaluate it.
Definition: Evaluator.cpp:656
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
llvm::Function
Definition: Function.h:60
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:536
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
llvm::PointerUnion::get
T get() const
Returns the value of the specified pointer type.
Definition: PointerUnion.h:155
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
clear
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:149
llvm::Intrinsic::getType
FunctionType * getType(LLVMContext &Context, ID id, ArrayRef< Type * > Tys=None)
Return the function type for an intrinsic.
Definition: Function.cpp:1374
llvm::ISD::Constant
@ Constant
Definition: ISDOpcodes.h:76
llvm::Evaluator::Evaluator
Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
Definition: Evaluator.h:82
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::Evaluator::getMutatedInitializers
DenseMap< GlobalVariable *, Constant * > getMutatedInitializers() const
Definition: Evaluator.h:102
SmallPtrSet.h
llvm::Evaluator::getInvariants
const SmallPtrSetImpl< GlobalVariable * > & getInvariants() const
Definition: Evaluator.h:109
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:162
llvm::DenseMap
Definition: DenseMap.h:716
llvm::Evaluator
This class evaluates LLVM IR, producing the Constant representing each SSA instruction.
Definition: Evaluator.h:37
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ARM::WinEH::ReturnType
ReturnType
Definition: ARMWinEH.h:25
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:112
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:350
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:222
SmallVector.h
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::Evaluator::~Evaluator
~Evaluator()
Definition: Evaluator.h:87
llvm::codeview::PublicSymFlags::Function
@ Function
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1236