Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- SCCPSolver.h - SCCP Utility ----------------------------- *- 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

//

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

//

// \file

// This file implements Sparse Conditional Constant Propagation (SCCP) utility.

//

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

#ifndef LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H

#define LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H

#include "llvm/ADT/MapVector.h"

#include "llvm/ADT/SmallPtrSet.h"

#include "llvm/ADT/Statistic.h"

#include "llvm/Analysis/DomTreeUpdater.h"

#include "llvm/Transforms/Utils/PredicateInfo.h"

#include <vector>

namespace llvm {

class Argument;

class BasicBlock;

class CallInst;

class Constant;

class DataLayout;

class DominatorTree;

class Function;

class GlobalVariable;

class Instruction;

class LLVMContext;

class LoopInfo;

class PostDominatorTree;

class StructType;

class TargetLibraryInfo;

class Value;

class ValueLatticeElement;

/// Helper struct for bundling up the analysis results per function for IPSCCP.

struct AnalysisResultsForFn {

  std::unique_ptr<PredicateInfo> PredInfo;

  DominatorTree *DT;

  PostDominatorTree *PDT;

  LoopInfo *LI;

};

/// Helper struct shared between Function Specialization and SCCP Solver.

struct ArgInfo {

  Argument *Formal; // The Formal argument being analysed.

  Constant *Actual; // A corresponding actual constant argument.

  ArgInfo(Argument *F, Constant *A) : Formal(F), Actual(A) {}

  bool operator==(const ArgInfo &Other) const {

    return Formal == Other.Formal && Actual == Other.Actual;

  }

  bool operator!=(const ArgInfo &Other) const { return !(*this == Other); }

  friend hash_code hash_value(const ArgInfo &A) {

    return hash_combine(hash_value(A.Formal), hash_value(A.Actual));

  }

};

class SCCPInstVisitor;

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

//

/// SCCPSolver - This interface class is a general purpose solver for Sparse

/// Conditional Constant Propagation (SCCP).

///

class SCCPSolver {

  std::unique_ptr<SCCPInstVisitor> Visitor;

public:

  SCCPSolver(const DataLayout &DL,

             std::function<const TargetLibraryInfo &(Function &)> GetTLI,

             LLVMContext &Ctx);

  ~SCCPSolver();

  void addAnalysis(Function &F, AnalysisResultsForFn A);

  /// markBlockExecutable - This method can be used by clients to mark all of

  /// the blocks that are known to be intrinsically live in the processed unit.

  /// This returns true if the block was not considered live before.

  bool markBlockExecutable(BasicBlock *BB);

  const PredicateBase *getPredicateInfoFor(Instruction *I);

  const LoopInfo &getLoopInfo(Function &F);

  DomTreeUpdater getDTU(Function &F);

  /// trackValueOfGlobalVariable - Clients can use this method to

  /// inform the SCCPSolver that it should track loads and stores to the

  /// specified global variable if it can.  This is only legal to call if

  /// performing Interprocedural SCCP.

  void trackValueOfGlobalVariable(GlobalVariable *GV);

  /// addTrackedFunction - If the SCCP solver is supposed to track calls into

  /// and out of the specified function (which cannot have its address taken),

  /// this method must be called.

  void addTrackedFunction(Function *F);

  /// Add function to the list of functions whose return cannot be modified.

  void addToMustPreserveReturnsInFunctions(Function *F);

  /// Returns true if the return of the given function cannot be modified.

  bool mustPreserveReturn(Function *F);

  void addArgumentTrackedFunction(Function *F);

  /// Returns true if the given function is in the solver's set of

  /// argument-tracked functions.

  bool isArgumentTrackedFunction(Function *F);

  /// Solve - Solve for constants and executable blocks.

  void solve();

  /// resolvedUndefsIn - While solving the dataflow for a function, we assume

  /// that branches on undef values cannot reach any of their successors.

  /// However, this is not a safe assumption.  After we solve dataflow, this

  /// method should be use to handle this.  If this returns true, the solver

  /// should be rerun.

  bool resolvedUndefsIn(Function &F);

  void solveWhileResolvedUndefsIn(Module &M);

  void solveWhileResolvedUndefsIn(SmallVectorImpl<Function *> &WorkList);

  bool isBlockExecutable(BasicBlock *BB) const;

  // isEdgeFeasible - Return true if the control flow edge from the 'From' basic

  // block to the 'To' basic block is currently feasible.

  bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;

  std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const;

  void removeLatticeValueFor(Value *V);

  const ValueLatticeElement &getLatticeValueFor(Value *V) const;

  /// getTrackedRetVals - Get the inferred return value map.

  const MapVector<Function *, ValueLatticeElement> &getTrackedRetVals();

  /// getTrackedGlobals - Get and return the set of inferred initializers for

  /// global variables.

  const DenseMap<GlobalVariable *, ValueLatticeElement> &getTrackedGlobals();

  /// getMRVFunctionsTracked - Get the set of functions which return multiple

  /// values tracked by the pass.

  const SmallPtrSet<Function *, 16> getMRVFunctionsTracked();

  /// markOverdefined - Mark the specified value overdefined.  This

  /// works with both scalars and structs.

  void markOverdefined(Value *V);

  // isStructLatticeConstant - Return true if all the lattice values

  // corresponding to elements of the structure are constants,

  // false otherwise.

  bool isStructLatticeConstant(Function *F, StructType *STy);

  /// Helper to return a Constant if \p LV is either a constant or a constant

  /// range with a single element.

  Constant *getConstant(const ValueLatticeElement &LV) const;

  /// Return a reference to the set of argument tracked functions.

  SmallPtrSetImpl<Function *> &getArgumentTrackedFunctions();

  /// Mark the constant arguments of a new function specialization. \p F points

  /// to the cloned function and \p Args contains a list of constant arguments

  /// represented as pairs of {formal,actual} values (the formal argument is

  /// associated with the original function definition). All other arguments of

  /// the specialization inherit the lattice state of their corresponding values

  /// in the original function.

  void markArgInFuncSpecialization(Function *F,

                                   const SmallVectorImpl<ArgInfo> &Args);

  /// Mark all of the blocks in function \p F non-executable. Clients can used

  /// this method to erase a function from the module (e.g., if it has been

  /// completely specialized and is no longer needed).

  void markFunctionUnreachable(Function *F);

  void visit(Instruction *I);

  void visitCall(CallInst &I);

  bool simplifyInstsInBlock(BasicBlock &BB,

                            SmallPtrSetImpl<Value *> &InsertedValues,

                            Statistic &InstRemovedStat,

                            Statistic &InstReplacedStat);

  bool removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU,

                              BasicBlock *&NewUnreachableBB) const;

  bool tryToReplaceWithConstant(Value *V);

  // Helper to check if \p LV is either a constant or a constant

  // range with a single element. This should cover exactly the same cases as

  // the old ValueLatticeElement::isConstant() and is intended to be used in the

  // transition to ValueLatticeElement.

  static bool isConstant(const ValueLatticeElement &LV);

  // Helper to check if \p LV is either overdefined or a constant range with

  // more than a single element. This should cover exactly the same cases as the

  // old ValueLatticeElement::isOverdefined() and is intended to be used in the

  // transition to ValueLatticeElement.

  static bool isOverdefined(const ValueLatticeElement &LV);

};

} // namespace llvm

#endif // LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H