contrib/llvm-project/llvm/include/llvm/Transforms/Utils/SCCPSolver.h

   1 //===- SCCPSolver.h - SCCP Utility ----------------------------- *- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // \file
  10 // This file implements Sparse Conditional Constant Propagation (SCCP) utility.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H
  15 #define LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H
  16
  17 #include "llvm/ADT/MapVector.h"
  18 #include "llvm/Analysis/DomTreeUpdater.h"
  19 #include "llvm/Transforms/Utils/PredicateInfo.h"
  20 #include <vector>
  21
  22 namespace llvm {
  23 class Argument;
  24 class BasicBlock;
  25 class CallInst;
  26 class Constant;
  27 class DataLayout;
  28 class DominatorTree;
  29 class Function;
  30 class GlobalVariable;
  31 class Instruction;
  32 class LLVMContext;
  33 class PostDominatorTree;
  34 class StructType;
  35 class TargetLibraryInfo;
  36 class Value;
  37 class ValueLatticeElement;
  38
  39 /// Helper struct for bundling up the analysis results per function for IPSCCP.
  40 struct AnalysisResultsForFn {
  41   std::unique_ptr<PredicateInfo> PredInfo;
  42   DominatorTree *DT;
  43   PostDominatorTree *PDT;
  44 };
  45
  46 /// Helper struct shared between Function Specialization and SCCP Solver.
  47 struct ArgInfo {
  48   Argument *Formal; // The Formal argument being analysed.
  49   Constant *Actual; // A corresponding actual constant argument.
  50
  51   ArgInfo(Argument *F, Constant *A) : Formal(F), Actual(A){};
  52 };
  53
  54 class SCCPInstVisitor;
  55
  56 //===----------------------------------------------------------------------===//
  57 //
  58 /// SCCPSolver - This interface class is a general purpose solver for Sparse
  59 /// Conditional Constant Propagation (SCCP).
  60 ///
  61 class SCCPSolver {
  62   std::unique_ptr<SCCPInstVisitor> Visitor;
  63
  64 public:
  65   SCCPSolver(const DataLayout &DL,
  66              std::function<const TargetLibraryInfo &(Function &)> GetTLI,
  67              LLVMContext &Ctx);
  68
  69   ~SCCPSolver();
  70
  71   void addAnalysis(Function &F, AnalysisResultsForFn A);
  72
  73   /// markBlockExecutable - This method can be used by clients to mark all of
  74   /// the blocks that are known to be intrinsically live in the processed unit.
  75   /// This returns true if the block was not considered live before.
  76   bool markBlockExecutable(BasicBlock *BB);
  77
  78   const PredicateBase *getPredicateInfoFor(Instruction *I);
  79
  80   DomTreeUpdater getDTU(Function &F);
  81
  82   /// trackValueOfGlobalVariable - Clients can use this method to
  83   /// inform the SCCPSolver that it should track loads and stores to the
  84   /// specified global variable if it can.  This is only legal to call if
  85   /// performing Interprocedural SCCP.
  86   void trackValueOfGlobalVariable(GlobalVariable *GV);
  87
  88   /// addTrackedFunction - If the SCCP solver is supposed to track calls into
  89   /// and out of the specified function (which cannot have its address taken),
  90   /// this method must be called.
  91   void addTrackedFunction(Function *F);
  92
  93   /// Add function to the list of functions whose return cannot be modified.
  94   void addToMustPreserveReturnsInFunctions(Function *F);
  95
  96   /// Returns true if the return of the given function cannot be modified.
  97   bool mustPreserveReturn(Function *F);
  98
  99   void addArgumentTrackedFunction(Function *F);
 100
 101   /// Returns true if the given function is in the solver's set of
 102   /// argument-tracked functions.
 103   bool isArgumentTrackedFunction(Function *F);
 104
 105   /// Solve - Solve for constants and executable blocks.
 106   void solve();
 107
 108   /// resolvedUndefsIn - While solving the dataflow for a function, we assume
 109   /// that branches on undef values cannot reach any of their successors.
 110   /// However, this is not a safe assumption.  After we solve dataflow, this
 111   /// method should be use to handle this.  If this returns true, the solver
 112   /// should be rerun.
 113   bool resolvedUndefsIn(Function &F);
 114
 115   bool isBlockExecutable(BasicBlock *BB) const;
 116
 117   // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
 118   // block to the 'To' basic block is currently feasible.
 119   bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
 120
 121   std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const;
 122
 123   void removeLatticeValueFor(Value *V);
 124
 125   const ValueLatticeElement &getLatticeValueFor(Value *V) const;
 126
 127   /// getTrackedRetVals - Get the inferred return value map.
 128   const MapVector<Function *, ValueLatticeElement> &getTrackedRetVals();
 129
 130   /// getTrackedGlobals - Get and return the set of inferred initializers for
 131   /// global variables.
 132   const DenseMap<GlobalVariable *, ValueLatticeElement> &getTrackedGlobals();
 133
 134   /// getMRVFunctionsTracked - Get the set of functions which return multiple
 135   /// values tracked by the pass.
 136   const SmallPtrSet<Function *, 16> getMRVFunctionsTracked();
 137
 138   /// markOverdefined - Mark the specified value overdefined.  This
 139   /// works with both scalars and structs.
 140   void markOverdefined(Value *V);
 141
 142   // isStructLatticeConstant - Return true if all the lattice values
 143   // corresponding to elements of the structure are constants,
 144   // false otherwise.
 145   bool isStructLatticeConstant(Function *F, StructType *STy);
 146
 147   /// Helper to return a Constant if \p LV is either a constant or a constant
 148   /// range with a single element.
 149   Constant *getConstant(const ValueLatticeElement &LV) const;
 150
 151   /// Return a reference to the set of argument tracked functions.
 152   SmallPtrSetImpl<Function *> &getArgumentTrackedFunctions();
 153
 154   /// Mark the constant arguments of a new function specialization. \p F points
 155   /// to the cloned function and \p Args contains a list of constant arguments
 156   /// represented as pairs of {formal,actual} values (the formal argument is
 157   /// associated with the original function definition). All other arguments of
 158   /// the specialization inherit the lattice state of their corresponding values
 159   /// in the original function.
 160   void markArgInFuncSpecialization(Function *F,
 161                                    const SmallVectorImpl<ArgInfo> &Args);
 162
 163   /// Mark all of the blocks in function \p F non-executable. Clients can used
 164   /// this method to erase a function from the module (e.g., if it has been
 165   /// completely specialized and is no longer needed).
 166   void markFunctionUnreachable(Function *F);
 167
 168   void visit(Instruction *I);
 169   void visitCall(CallInst &I);
 170 };
 171
 172 } // namespace llvm
 173
 174 #endif // LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H