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  /// Evaluate all instructions in block BB, returning true if successful, false
61  /// if we can't evaluate it.  NewBB returns the next BB that control flows
62  /// into, or null upon return.
63  bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB);
64
65  Constant *getVal(Value *V) {
66    if (Constant *CV = dyn_cast<Constant>(V)) return CV;
67    Constant *R = ValueStack.back().lookup(V);
68    assert(R && "Reference to an uncomputed value!");
69    return R;
70  }
71
72  void setVal(Value *V, Constant *C) {
73    ValueStack.back()[V] = C;
74  }
75
76  /// Casts call result to a type of bitcast call expression
77  Constant *castCallResultIfNeeded(Value *CallExpr, Constant *RV);
78
79  const DenseMap<Constant*, Constant*> &getMutatedMemory() const {
80    return MutatedMemory;
81  }
82
83  const SmallPtrSetImpl<GlobalVariable*> &getInvariants() const {
84    return Invariants;
85  }
86
87private:
88  /// Given call site return callee and list of its formal arguments
89  Function *getCalleeWithFormalArgs(CallBase &CB,
90                                    SmallVectorImpl<Constant *> &Formals);
91
92  /// Given call site and callee returns list of callee formal argument
93  /// values converting them when necessary
94  bool getFormalParams(CallBase &CB, Function *F,
95                       SmallVectorImpl<Constant *> &Formals);
96
97  Constant *ComputeLoadResult(Constant *P);
98
99  /// As we compute SSA register values, we store their contents here. The back
100  /// of the deque contains the current function and the stack contains the
101  /// values in the calling frames.
102  std::deque<DenseMap<Value*, Constant*>> ValueStack;
103
104  /// This is used to detect recursion.  In pathological situations we could hit
105  /// exponential behavior, but at least there is nothing unbounded.
106  SmallVector<Function*, 4> CallStack;
107
108  /// For each store we execute, we update this map.  Loads check this to get
109  /// the most up-to-date value.  If evaluation is successful, this state is
110  /// committed to the process.
111  DenseMap<Constant*, Constant*> MutatedMemory;
112
113  /// To 'execute' an alloca, we create a temporary global variable to represent
114  /// its body.  This vector is needed so we can delete the temporary globals
115  /// when we are done.
116  SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps;
117
118  /// These global variables have been marked invariant by the static
119  /// constructor.
120  SmallPtrSet<GlobalVariable*, 8> Invariants;
121
122  /// These are constants we have checked and know to be simple enough to live
123  /// in a static initializer of a global.
124  SmallPtrSet<Constant*, 8> SimpleConstants;
125
126  const DataLayout &DL;
127  const TargetLibraryInfo *TLI;
128};
129
130} // end namespace llvm
131
132#endif // LLVM_TRANSFORMS_UTILS_EVALUATOR_H
133