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
28namespace llvm {
29
30class DataLayout;
31class Function;
32class 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.
38class Evaluator {
39public:
40 Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
41 : DL(DL), TLI(TLI) {
42 ValueStack.emplace_back();
43 }
44
45 ~Evaluator() {
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
60 const DenseMap<Constant *, Constant *> &getMutatedMemory() const {
61 return MutatedMemory;
62 }
63
64 const SmallPtrSetImpl<GlobalVariable *> &getInvariants() const {
65 return Invariants;
66 }
67
68private:
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
131