LLVM 19.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"
19#include "llvm/IR/BasicBlock.h"
22#include <cassert>
23#include <deque>
24#include <memory>
25
26namespace llvm {
27
28class CallBase;
29class DataLayout;
30class Function;
31class 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.
37class 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 = dyn_cast_if_present<Constant *>(Val))
59 return C->getType();
60 return cast<MutableAggregate *>(Val)->Ty;
61 }
62
63 Constant *toConstant() const {
64 if (auto *C = dyn_cast_if_present<Constant *>(Val))
65 return C;
66 return cast<MutableAggregate *>(Val)->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
81public:
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 (const auto &Pair : MutatedMemory)
105 Result[Pair.first] = Pair.second.toConstant();
106 return Result;
107 }
108
110 return Invariants;
111 }
112
113private:
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
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file defines the DenseMap class.
#define F(x, y, z)
Definition: MD5.cpp:55
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Class for arbitrary precision integers.
Definition: APInt.h:76
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:164
This is an important base class in LLVM.
Definition: Constant.h:41
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:370
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
This class evaluates LLVM IR, producing the Constant representing each SSA instruction.
Definition: Evaluator.h:37
DenseMap< GlobalVariable *, Constant * > getMutatedInitializers() const
Definition: Evaluator.h:102
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:629
const SmallPtrSetImpl< GlobalVariable * > & getInvariants() const
Definition: Evaluator.h:109
Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
Definition: Evaluator.h:82
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
Definition: PointerUnion.h:118
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:321
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
LLVM Value Representation.
Definition: Value.h:74
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:456
Error write(MCStreamer &Out, ArrayRef< std::string > Inputs, OnCuIndexOverflow OverflowOptValue)
Definition: DWP.cpp:601
@ Other
Any other memory.