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