Evaluator.h 4.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143
  1. #pragma once
  2. #ifdef __GNUC__
  3. #pragma GCC diagnostic push
  4. #pragma GCC diagnostic ignored "-Wunused-parameter"
  5. #endif
  6. //===- Evaluator.h - LLVM IR evaluator --------------------------*- C++ -*-===//
  7. //
  8. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  9. // See https://llvm.org/LICENSE.txt for license information.
  10. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  11. //
  12. //===----------------------------------------------------------------------===//
  13. //
  14. // Function evaluator for LLVM IR.
  15. //
  16. //===----------------------------------------------------------------------===//
  17. #ifndef LLVM_TRANSFORMS_UTILS_EVALUATOR_H
  18. #define LLVM_TRANSFORMS_UTILS_EVALUATOR_H
  19. #include "llvm/ADT/DenseMap.h"
  20. #include "llvm/ADT/SmallPtrSet.h"
  21. #include "llvm/ADT/SmallVector.h"
  22. #include "llvm/IR/BasicBlock.h"
  23. #include "llvm/IR/GlobalVariable.h"
  24. #include "llvm/IR/Instructions.h"
  25. #include "llvm/IR/Value.h"
  26. #include "llvm/Support/Casting.h"
  27. #include <cassert>
  28. #include <deque>
  29. #include <memory>
  30. namespace llvm {
  31. class DataLayout;
  32. class Function;
  33. class TargetLibraryInfo;
  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.
  38. class Evaluator {
  39. public:
  40. Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
  41. : DL(DL), TLI(TLI) {
  42. ValueStack.emplace_back();
  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. /// Evaluate a call to function F, returning true if successful, false if we
  53. /// can't evaluate it. ActualArgs contains the formal arguments for the
  54. /// function.
  55. bool EvaluateFunction(Function *F, Constant *&RetVal,
  56. const SmallVectorImpl<Constant*> &ActualArgs);
  57. /// Evaluate all instructions in block BB, returning true if successful, false
  58. /// if we can't evaluate it. NewBB returns the next BB that control flows
  59. /// into, or null upon return.
  60. bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB);
  61. Constant *getVal(Value *V) {
  62. if (Constant *CV = dyn_cast<Constant>(V)) return CV;
  63. Constant *R = ValueStack.back().lookup(V);
  64. assert(R && "Reference to an uncomputed value!");
  65. return R;
  66. }
  67. void setVal(Value *V, Constant *C) {
  68. ValueStack.back()[V] = C;
  69. }
  70. /// Casts call result to a type of bitcast call expression
  71. Constant *castCallResultIfNeeded(Value *CallExpr, Constant *RV);
  72. const DenseMap<Constant*, Constant*> &getMutatedMemory() const {
  73. return MutatedMemory;
  74. }
  75. const SmallPtrSetImpl<GlobalVariable*> &getInvariants() const {
  76. return Invariants;
  77. }
  78. private:
  79. /// Given call site return callee and list of its formal arguments
  80. Function *getCalleeWithFormalArgs(CallBase &CB,
  81. SmallVectorImpl<Constant *> &Formals);
  82. /// Given call site and callee returns list of callee formal argument
  83. /// values converting them when necessary
  84. bool getFormalParams(CallBase &CB, Function *F,
  85. SmallVectorImpl<Constant *> &Formals);
  86. Constant *ComputeLoadResult(Constant *P);
  87. /// As we compute SSA register values, we store their contents here. The back
  88. /// of the deque contains the current function and the stack contains the
  89. /// values in the calling frames.
  90. std::deque<DenseMap<Value*, Constant*>> ValueStack;
  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. /// For each store we execute, we update this map. Loads check this to get
  95. /// the most up-to-date value. If evaluation is successful, this state is
  96. /// committed to the process.
  97. DenseMap<Constant*, Constant*> MutatedMemory;
  98. /// To 'execute' an alloca, we create a temporary global variable to represent
  99. /// its body. This vector is needed so we can delete the temporary globals
  100. /// when we are done.
  101. SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps;
  102. /// These global variables have been marked invariant by the static
  103. /// constructor.
  104. SmallPtrSet<GlobalVariable*, 8> Invariants;
  105. /// These are constants we have checked and know to be simple enough to live
  106. /// in a static initializer of a global.
  107. SmallPtrSet<Constant*, 8> SimpleConstants;
  108. const DataLayout &DL;
  109. const TargetLibraryInfo *TLI;
  110. };
  111. } // end namespace llvm
  112. #endif // LLVM_TRANSFORMS_UTILS_EVALUATOR_H
  113. #ifdef __GNUC__
  114. #pragma GCC diagnostic pop
  115. #endif