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/ADT/SmallPtrSet.h" 19 #include "llvm/ADT/Statistic.h" 20 #include "llvm/Analysis/DomTreeUpdater.h" 21 #include "llvm/Transforms/Utils/PredicateInfo.h" 22 #include <vector> 23 24 namespace llvm { 25 class Argument; 26 class BasicBlock; 27 class CallInst; 28 class Constant; 29 class DataLayout; 30 class DominatorTree; 31 class Function; 32 class GlobalVariable; 33 class Instruction; 34 class LLVMContext; 35 class LoopInfo; 36 class PostDominatorTree; 37 class StructType; 38 class TargetLibraryInfo; 39 class Value; 40 class ValueLatticeElement; 41 42 /// Helper struct for bundling up the analysis results per function for IPSCCP. 43 struct AnalysisResultsForFn { 44 std::unique_ptr<PredicateInfo> PredInfo; 45 DominatorTree *DT; 46 PostDominatorTree *PDT; 47 LoopInfo *LI; 48 }; 49 50 /// Helper struct shared between Function Specialization and SCCP Solver. 51 struct ArgInfo { 52 Argument *Formal; // The Formal argument being analysed. 53 Constant *Actual; // A corresponding actual constant argument. 54 ArgInfoArgInfo55 ArgInfo(Argument *F, Constant *A) : Formal(F), Actual(A) {} 56 57 bool operator==(const ArgInfo &Other) const { 58 return Formal == Other.Formal && Actual == Other.Actual; 59 } 60 61 bool operator!=(const ArgInfo &Other) const { return !(*this == Other); } 62 hash_valueArgInfo63 friend hash_code hash_value(const ArgInfo &A) { 64 return hash_combine(hash_value(A.Formal), hash_value(A.Actual)); 65 } 66 }; 67 68 class SCCPInstVisitor; 69 70 //===----------------------------------------------------------------------===// 71 // 72 /// SCCPSolver - This interface class is a general purpose solver for Sparse 73 /// Conditional Constant Propagation (SCCP). 74 /// 75 class SCCPSolver { 76 std::unique_ptr<SCCPInstVisitor> Visitor; 77 78 public: 79 SCCPSolver(const DataLayout &DL, 80 std::function<const TargetLibraryInfo &(Function &)> GetTLI, 81 LLVMContext &Ctx); 82 83 ~SCCPSolver(); 84 85 void addAnalysis(Function &F, AnalysisResultsForFn A); 86 87 /// markBlockExecutable - This method can be used by clients to mark all of 88 /// the blocks that are known to be intrinsically live in the processed unit. 89 /// This returns true if the block was not considered live before. 90 bool markBlockExecutable(BasicBlock *BB); 91 92 const PredicateBase *getPredicateInfoFor(Instruction *I); 93 94 const LoopInfo &getLoopInfo(Function &F); 95 96 DomTreeUpdater getDTU(Function &F); 97 98 /// trackValueOfGlobalVariable - Clients can use this method to 99 /// inform the SCCPSolver that it should track loads and stores to the 100 /// specified global variable if it can. This is only legal to call if 101 /// performing Interprocedural SCCP. 102 void trackValueOfGlobalVariable(GlobalVariable *GV); 103 104 /// addTrackedFunction - If the SCCP solver is supposed to track calls into 105 /// and out of the specified function (which cannot have its address taken), 106 /// this method must be called. 107 void addTrackedFunction(Function *F); 108 109 /// Add function to the list of functions whose return cannot be modified. 110 void addToMustPreserveReturnsInFunctions(Function *F); 111 112 /// Returns true if the return of the given function cannot be modified. 113 bool mustPreserveReturn(Function *F); 114 115 void addArgumentTrackedFunction(Function *F); 116 117 /// Returns true if the given function is in the solver's set of 118 /// argument-tracked functions. 119 bool isArgumentTrackedFunction(Function *F); 120 121 /// Solve - Solve for constants and executable blocks. 122 void solve(); 123 124 /// resolvedUndefsIn - While solving the dataflow for a function, we assume 125 /// that branches on undef values cannot reach any of their successors. 126 /// However, this is not a safe assumption. After we solve dataflow, this 127 /// method should be use to handle this. If this returns true, the solver 128 /// should be rerun. 129 bool resolvedUndefsIn(Function &F); 130 131 void solveWhileResolvedUndefsIn(Module &M); 132 133 void solveWhileResolvedUndefsIn(SmallVectorImpl<Function *> &WorkList); 134 135 bool isBlockExecutable(BasicBlock *BB) const; 136 137 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic 138 // block to the 'To' basic block is currently feasible. 139 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const; 140 141 std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const; 142 143 void removeLatticeValueFor(Value *V); 144 145 const ValueLatticeElement &getLatticeValueFor(Value *V) const; 146 147 /// getTrackedRetVals - Get the inferred return value map. 148 const MapVector<Function *, ValueLatticeElement> &getTrackedRetVals(); 149 150 /// getTrackedGlobals - Get and return the set of inferred initializers for 151 /// global variables. 152 const DenseMap<GlobalVariable *, ValueLatticeElement> &getTrackedGlobals(); 153 154 /// getMRVFunctionsTracked - Get the set of functions which return multiple 155 /// values tracked by the pass. 156 const SmallPtrSet<Function *, 16> getMRVFunctionsTracked(); 157 158 /// markOverdefined - Mark the specified value overdefined. This 159 /// works with both scalars and structs. 160 void markOverdefined(Value *V); 161 162 // isStructLatticeConstant - Return true if all the lattice values 163 // corresponding to elements of the structure are constants, 164 // false otherwise. 165 bool isStructLatticeConstant(Function *F, StructType *STy); 166 167 /// Helper to return a Constant if \p LV is either a constant or a constant 168 /// range with a single element. 169 Constant *getConstant(const ValueLatticeElement &LV) const; 170 171 /// Return a reference to the set of argument tracked functions. 172 SmallPtrSetImpl<Function *> &getArgumentTrackedFunctions(); 173 174 /// Mark the constant arguments of a new function specialization. \p F points 175 /// to the cloned function and \p Args contains a list of constant arguments 176 /// represented as pairs of {formal,actual} values (the formal argument is 177 /// associated with the original function definition). All other arguments of 178 /// the specialization inherit the lattice state of their corresponding values 179 /// in the original function. 180 void markArgInFuncSpecialization(Function *F, 181 const SmallVectorImpl<ArgInfo> &Args); 182 183 /// Mark all of the blocks in function \p F non-executable. Clients can used 184 /// this method to erase a function from the module (e.g., if it has been 185 /// completely specialized and is no longer needed). 186 void markFunctionUnreachable(Function *F); 187 188 void visit(Instruction *I); 189 void visitCall(CallInst &I); 190 191 bool simplifyInstsInBlock(BasicBlock &BB, 192 SmallPtrSetImpl<Value *> &InsertedValues, 193 Statistic &InstRemovedStat, 194 Statistic &InstReplacedStat); 195 196 bool removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU, 197 BasicBlock *&NewUnreachableBB) const; 198 199 bool tryToReplaceWithConstant(Value *V); 200 201 // Helper to check if \p LV is either a constant or a constant 202 // range with a single element. This should cover exactly the same cases as 203 // the old ValueLatticeElement::isConstant() and is intended to be used in the 204 // transition to ValueLatticeElement. 205 static bool isConstant(const ValueLatticeElement &LV); 206 207 // Helper to check if \p LV is either overdefined or a constant range with 208 // more than a single element. This should cover exactly the same cases as the 209 // old ValueLatticeElement::isOverdefined() and is intended to be used in the 210 // transition to ValueLatticeElement. 211 static bool isOverdefined(const ValueLatticeElement &LV); 212 }; 213 } // namespace llvm 214 215 #endif // LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H 216