Transforms/Utils/Evaluator.h

0001 //===- Evaluator.h - LLVM IR evaluator --------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // Function evaluator for LLVM IR.
0010 //
0011 //===----------------------------------------------------------------------===//
0012
0013 #ifndef LLVM_TRANSFORMS_UTILS_EVALUATOR_H
0014 #define LLVM_TRANSFORMS_UTILS_EVALUATOR_H
0015
0016 #include "llvm/ADT/DenseMap.h"
0017 #include "llvm/ADT/SmallPtrSet.h"
0018 #include "llvm/ADT/SmallVector.h"
0019 #include "llvm/IR/BasicBlock.h"
0020 #include "llvm/IR/GlobalVariable.h"
0021 #include "llvm/Support/Casting.h"
0022 #include <cassert>
0023 #include <deque>
0024 #include <memory>
0025
0026 namespace llvm {
0027
0028 class CallBase;
0029 class DataLayout;
0030 class Function;
0031 class TargetLibraryInfo;
0032
0033 /// This class evaluates LLVM IR, producing the Constant representing each SSA
0034 /// instruction.  Changes to global variables are stored in a mapping that can
0035 /// be iterated over after the evaluation is complete.  Once an evaluation call
0036 /// fails, the evaluation object should not be reused.
0037 class Evaluator {
0038   struct MutableAggregate;
0039
0040   /// The evaluator represents values either as a Constant*, or as a
0041   /// MutableAggregate, which allows changing individual aggregate elements
0042   /// without creating a new interned Constant.
0043   class MutableValue {
0044     PointerUnion<Constant *, MutableAggregate *> Val;
0045     void clear();
0046     bool makeMutable();
0047
0048   public:
0049     MutableValue(Constant *C) { Val = C; }
0050     MutableValue(const MutableValue &) = delete;
0051     MutableValue(MutableValue &&Other) {
0052       Val = Other.Val;
0053       Other.Val = nullptr;
0054     }
0055     ~MutableValue() { clear(); }
0056
0057     Type *getType() const {
0058       if (auto *C = dyn_cast_if_present<Constant *>(Val))
0059         return C->getType();
0060       return cast<MutableAggregate *>(Val)->Ty;
0061     }
0062
0063     Constant *toConstant() const {
0064       if (auto *C = dyn_cast_if_present<Constant *>(Val))
0065         return C;
0066       return cast<MutableAggregate *>(Val)->toConstant();
0067     }
0068
0069     Constant *read(Type *Ty, APInt Offset, const DataLayout &DL) const;
0070     bool write(Constant *V, APInt Offset, const DataLayout &DL);
0071   };
0072
0073   struct MutableAggregate {
0074     Type *Ty;
0075     SmallVector<MutableValue> Elements;
0076
0077     MutableAggregate(Type *Ty) : Ty(Ty) {}
0078     Constant *toConstant() const;
0079   };
0080
0081 public:
0082   Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
0083       : DL(DL), TLI(TLI) {
0084     ValueStack.emplace_back();
0085   }
0086
0087   ~Evaluator() {
0088     for (auto &Tmp : AllocaTmps)
0089       // If there are still users of the alloca, the program is doing something
0090       // silly, e.g. storing the address of the alloca somewhere and using it
0091       // later.  Since this is undefined, we'll just make it be null.
0092       if (!Tmp->use_empty())
0093         Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType()));
0094   }
0095
0096   /// Evaluate a call to function F, returning true if successful, false if we
0097   /// can't evaluate it.  ActualArgs contains the formal arguments for the
0098   /// function.
0099   bool EvaluateFunction(Function *F, Constant *&RetVal,
0100                         const SmallVectorImpl<Constant*> &ActualArgs);
0101
0102   DenseMap<GlobalVariable *, Constant *> getMutatedInitializers() const {
0103     DenseMap<GlobalVariable *, Constant *> Result;
0104     for (const auto &Pair : MutatedMemory)
0105       Result[Pair.first] = Pair.second.toConstant();
0106     return Result;
0107   }
0108
0109   const SmallPtrSetImpl<GlobalVariable *> &getInvariants() const {
0110     return Invariants;
0111   }
0112
0113 private:
0114   bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB,
0115                      bool &StrippedPointerCastsForAliasAnalysis);
0116
0117   Constant *getVal(Value *V) {
0118     if (Constant *CV = dyn_cast<Constant>(V)) return CV;
0119     Constant *R = ValueStack.back().lookup(V);
0120     assert(R && "Reference to an uncomputed value!");
0121     return R;
0122   }
0123
0124   void setVal(Value *V, Constant *C) {
0125     ValueStack.back()[V] = C;
0126   }
0127
0128   /// Given call site return callee and list of its formal arguments
0129   Function *getCalleeWithFormalArgs(CallBase &CB,
0130                                     SmallVectorImpl<Constant *> &Formals);
0131
0132   /// Given call site and callee returns list of callee formal argument
0133   /// values converting them when necessary
0134   bool getFormalParams(CallBase &CB, Function *F,
0135                        SmallVectorImpl<Constant *> &Formals);
0136
0137   Constant *ComputeLoadResult(Constant *P, Type *Ty);
0138   Constant *ComputeLoadResult(GlobalVariable *GV, Type *Ty,
0139                               const APInt &Offset);
0140
0141   /// As we compute SSA register values, we store their contents here. The back
0142   /// of the deque contains the current function and the stack contains the
0143   /// values in the calling frames.
0144   std::deque<DenseMap<Value*, Constant*>> ValueStack;
0145
0146   /// This is used to detect recursion.  In pathological situations we could hit
0147   /// exponential behavior, but at least there is nothing unbounded.
0148   SmallVector<Function*, 4> CallStack;
0149
0150   /// For each store we execute, we update this map.  Loads check this to get
0151   /// the most up-to-date value.  If evaluation is successful, this state is
0152   /// committed to the process.
0153   DenseMap<GlobalVariable *, MutableValue> MutatedMemory;
0154
0155   /// To 'execute' an alloca, we create a temporary global variable to represent
0156   /// its body.  This vector is needed so we can delete the temporary globals
0157   /// when we are done.
0158   SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps;
0159
0160   /// These global variables have been marked invariant by the static
0161   /// constructor.
0162   SmallPtrSet<GlobalVariable*, 8> Invariants;
0163
0164   /// These are constants we have checked and know to be simple enough to live
0165   /// in a static initializer of a global.
0166   SmallPtrSet<Constant*, 8> SimpleConstants;
0167
0168   const DataLayout &DL;
0169   const TargetLibraryInfo *TLI;
0170 };
0171
0172 } // end namespace llvm
0173
0174 #endif // LLVM_TRANSFORMS_UTILS_EVALUATOR_H