1//===-- Evaluator.h - LLVM IR evaluator -------------------------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// Function evaluator for LLVM IR.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_TRANSFORMS_UTILS_EVALUATOR_H
15#define LLVM_TRANSFORMS_UTILS_EVALUATOR_H
16
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/SmallPtrSet.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/IR/BasicBlock.h"
21#include "llvm/IR/Constant.h"
22#include "llvm/IR/GlobalVariable.h"
23
24#include <deque>
25#include <memory>
26
27namespace llvm {
28
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 {
38public:
39  Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
40      : DL(DL), TLI(TLI) {
41    ValueStack.emplace_back();
42  }
43
44  ~Evaluator() {
45    for (auto &Tmp : AllocaTmps)
46      // If there are still users of the alloca, the program is doing something
47      // silly, e.g. storing the address of the alloca somewhere and using it
48      // later.  Since this is undefined, we'll just make it be null.
49      if (!Tmp->use_empty())
50        Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType()));
51  }
52
53  /// Evaluate a call to function F, returning true if successful, false if we
54  /// can't evaluate it.  ActualArgs contains the formal arguments for the
55  /// function.
56  bool EvaluateFunction(Function *F, Constant *&RetVal,
57                        const SmallVectorImpl<Constant*> &ActualArgs);
58
59  /// Evaluate all instructions in block BB, returning true if successful, false
60  /// if we can't evaluate it.  NewBB returns the next BB that control flows
61  /// into, or null upon return.
62  bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB);
63
64  Constant *getVal(Value *V) {
65    if (Constant *CV = dyn_cast<Constant>(V)) return CV;
66    Constant *R = ValueStack.back().lookup(V);
67    assert(R && "Reference to an uncomputed value!");
68    return R;
69  }
70
71  void setVal(Value *V, Constant *C) {
72    ValueStack.back()[V] = C;
73  }
74
75  const DenseMap<Constant*, Constant*> &getMutatedMemory() const {
76    return MutatedMemory;
77  }
78
79  const SmallPtrSetImpl<GlobalVariable*> &getInvariants() const {
80    return Invariants;
81  }
82
83private:
84  Constant *ComputeLoadResult(Constant *P);
85
86  /// As we compute SSA register values, we store their contents here. The back
87  /// of the deque contains the current function and the stack contains the
88  /// values in the calling frames.
89  std::deque<DenseMap<Value*, Constant*>> ValueStack;
90
91  /// This is used to detect recursion.  In pathological situations we could hit
92  /// exponential behavior, but at least there is nothing unbounded.
93  SmallVector<Function*, 4> CallStack;
94
95  /// For each store we execute, we update this map.  Loads check this to get
96  /// the most up-to-date value.  If evaluation is successful, this state is
97  /// committed to the process.
98  DenseMap<Constant*, Constant*> MutatedMemory;
99
100  /// To 'execute' an alloca, we create a temporary global variable to represent
101  /// its body.  This vector is needed so we can delete the temporary globals
102  /// when we are done.
103  SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps;
104
105  /// These global variables have been marked invariant by the static
106  /// constructor.
107  SmallPtrSet<GlobalVariable*, 8> Invariants;
108
109  /// These are constants we have checked and know to be simple enough to live
110  /// in a static initializer of a global.
111  SmallPtrSet<Constant*, 8> SimpleConstants;
112
113  const DataLayout &DL;
114  const TargetLibraryInfo *TLI;
115};
116
117}
118
119#endif
120