Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- Evaluator.h - LLVM IR evaluator --------------------------*- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

// Function evaluator for LLVM IR.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_UTILS_EVALUATOR_H

#define LLVM_TRANSFORMS_UTILS_EVALUATOR_H

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/SmallPtrSet.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/IR/BasicBlock.h"

#include "llvm/IR/GlobalVariable.h"

#include "llvm/Support/Casting.h"

#include <cassert>

#include <deque>

#include <memory>

namespace llvm {

class CallBase;

class DataLayout;

class Function;

class TargetLibraryInfo;

/// This class evaluates LLVM IR, producing the Constant representing each SSA

/// instruction.  Changes to global variables are stored in a mapping that can

/// be iterated over after the evaluation is complete.  Once an evaluation call

/// fails, the evaluation object should not be reused.

class Evaluator {

  struct MutableAggregate;

  /// The evaluator represents values either as a Constant*, or as a

  /// MutableAggregate, which allows changing individual aggregate elements

  /// without creating a new interned Constant.

  class MutableValue {

    PointerUnion<Constant *, MutableAggregate *> Val;

    void clear();

    bool makeMutable();

  public:

    MutableValue(Constant *C) { Val = C; }

    MutableValue(const MutableValue &) = delete;

    MutableValue(MutableValue &&Other) {

      Val = Other.Val;

      Other.Val = nullptr;

    }

    ~MutableValue() { clear(); }

    Type *getType() const {

      if (auto *C = Val.dyn_cast<Constant *>())

        return C->getType();

      return Val.get<MutableAggregate *>()->Ty;

    }

    Constant *toConstant() const {

      if (auto *C = Val.dyn_cast<Constant *>())

        return C;

      return Val.get<MutableAggregate *>()->toConstant();

    }

    Constant *read(Type *Ty, APInt Offset, const DataLayout &DL) const;

    bool write(Constant *V, APInt Offset, const DataLayout &DL);

  };

  struct MutableAggregate {

    Type *Ty;

    SmallVector<MutableValue> Elements;

    MutableAggregate(Type *Ty) : Ty(Ty) {}

    Constant *toConstant() const;

  };

public:

  Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)

      : DL(DL), TLI(TLI) {

    ValueStack.emplace_back();

  }

  ~Evaluator() {

    for (auto &Tmp : AllocaTmps)

      // If there are still users of the alloca, the program is doing something

      // silly, e.g. storing the address of the alloca somewhere and using it

      // later.  Since this is undefined, we'll just make it be null.

      if (!Tmp->use_empty())

        Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType()));

  }

  /// Evaluate a call to function F, returning true if successful, false if we

  /// can't evaluate it.  ActualArgs contains the formal arguments for the

  /// function.

  bool EvaluateFunction(Function *F, Constant *&RetVal,

                        const SmallVectorImpl<Constant*> &ActualArgs);

  DenseMap<GlobalVariable *, Constant *> getMutatedInitializers() const {

    DenseMap<GlobalVariable *, Constant *> Result;

    for (const auto &Pair : MutatedMemory)

      Result[Pair.first] = Pair.second.toConstant();

    return Result;

  }

  const SmallPtrSetImpl<GlobalVariable *> &getInvariants() const {

    return Invariants;

  }

private:

  bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB,

                     bool &StrippedPointerCastsForAliasAnalysis);

  Constant *getVal(Value *V) {

    if (Constant *CV = dyn_cast<Constant>(V)) return CV;

    Constant *R = ValueStack.back().lookup(V);

    assert(R && "Reference to an uncomputed value!");

    return R;

  }

  void setVal(Value *V, Constant *C) {

    ValueStack.back()[V] = C;

  }

  /// Casts call result to a type of bitcast call expression

  Constant *castCallResultIfNeeded(Type *ReturnType, Constant *RV);

  /// Given call site return callee and list of its formal arguments

  Function *getCalleeWithFormalArgs(CallBase &CB,

                                    SmallVectorImpl<Constant *> &Formals);

  /// Given call site and callee returns list of callee formal argument

  /// values converting them when necessary

  bool getFormalParams(CallBase &CB, Function *F,

                       SmallVectorImpl<Constant *> &Formals);

  Constant *ComputeLoadResult(Constant *P, Type *Ty);

  Constant *ComputeLoadResult(GlobalVariable *GV, Type *Ty,

                              const APInt &Offset);

  /// As we compute SSA register values, we store their contents here. The back

  /// of the deque contains the current function and the stack contains the

  /// values in the calling frames.

  std::deque<DenseMap<Value*, Constant*>> ValueStack;

  /// This is used to detect recursion.  In pathological situations we could hit

  /// exponential behavior, but at least there is nothing unbounded.

  SmallVector<Function*, 4> CallStack;

  /// For each store we execute, we update this map.  Loads check this to get

  /// the most up-to-date value.  If evaluation is successful, this state is

  /// committed to the process.

  DenseMap<GlobalVariable *, MutableValue> MutatedMemory;

  /// To 'execute' an alloca, we create a temporary global variable to represent

  /// its body.  This vector is needed so we can delete the temporary globals

  /// when we are done.

  SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps;

  /// These global variables have been marked invariant by the static

  /// constructor.

  SmallPtrSet<GlobalVariable*, 8> Invariants;

  /// These are constants we have checked and know to be simple enough to live

  /// in a static initializer of a global.

  SmallPtrSet<Constant*, 8> SimpleConstants;

  const DataLayout &DL;

  const TargetLibraryInfo *TLI;

};

} // end namespace llvm

#endif // LLVM_TRANSFORMS_UTILS_EVALUATOR_H