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 175