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 45 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 53 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 const SmallPtrSetImpl<Function *> &getArgumentTrackedFunctions() const; 108 109 /// Solve - Solve for constants and executable blocks. 110 void solve(); 111 112 /// resolvedUndefsIn - While solving the dataflow for a function, we assume 113 /// that branches on undef values cannot reach any of their successors. 114 /// However, this is not a safe assumption. After we solve dataflow, this 115 /// method should be use to handle this. If this returns true, the solver 116 /// should be rerun. 117 bool resolvedUndefsIn(Function &F); 118 119 void solveWhileResolvedUndefsIn(Module &M); 120 121 void solveWhileResolvedUndefsIn(SmallVectorImpl<Function *> &WorkList); 122 123 void solveWhileResolvedUndefs(); 124 125 bool isBlockExecutable(BasicBlock *BB) const; 126 127 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic 128 // block to the 'To' basic block is currently feasible. 129 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const; 130 131 std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const; 132 133 void removeLatticeValueFor(Value *V); 134 135 /// Invalidate the Lattice Value of \p Call and its users after specializing 136 /// the call. Then recompute it. 137 void resetLatticeValueFor(CallBase *Call); 138 139 const ValueLatticeElement &getLatticeValueFor(Value *V) const; 140 141 /// getTrackedRetVals - Get the inferred return value map. 142 const MapVector<Function *, ValueLatticeElement> &getTrackedRetVals() const; 143 144 /// getTrackedGlobals - Get and return the set of inferred initializers for 145 /// global variables. 146 const DenseMap<GlobalVariable *, ValueLatticeElement> &getTrackedGlobals(); 147 148 /// getMRVFunctionsTracked - Get the set of functions which return multiple 149 /// values tracked by the pass. 150 const SmallPtrSet<Function *, 16> getMRVFunctionsTracked(); 151 152 /// markOverdefined - Mark the specified value overdefined. This 153 /// works with both scalars and structs. 154 void markOverdefined(Value *V); 155 156 /// trackValueOfArgument - Mark the specified argument overdefined unless it 157 /// have range attribute. This works with both scalars and structs. 158 void trackValueOfArgument(Argument *V); 159 160 // isStructLatticeConstant - Return true if all the lattice values 161 // corresponding to elements of the structure are constants, 162 // false otherwise. 163 bool isStructLatticeConstant(Function *F, StructType *STy); 164 165 /// Helper to return a Constant if \p LV is either a constant or a constant 166 /// range with a single element. 167 Constant *getConstant(const ValueLatticeElement &LV, Type *Ty) const; 168 169 /// Return either a Constant or nullptr for a given Value. 170 Constant *getConstantOrNull(Value *V) const; 171 172 /// Set the Lattice Value for the arguments of a specialization \p F. 173 /// If an argument is Constant then its lattice value is marked with the 174 /// corresponding actual argument in \p Args. Otherwise, its lattice value 175 /// is inherited (copied) from the corresponding formal argument in \p Args. 176 void setLatticeValueForSpecializationArguments(Function *F, 177 const SmallVectorImpl<ArgInfo> &Args); 178 179 /// Mark all of the blocks in function \p F non-executable. Clients can used 180 /// this method to erase a function from the module (e.g., if it has been 181 /// completely specialized and is no longer needed). 182 void markFunctionUnreachable(Function *F); 183 184 void visit(Instruction *I); 185 void visitCall(CallInst &I); 186 187 bool simplifyInstsInBlock(BasicBlock &BB, 188 SmallPtrSetImpl<Value *> &InsertedValues, 189 Statistic &InstRemovedStat, 190 Statistic &InstReplacedStat); 191 192 bool removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU, 193 BasicBlock *&NewUnreachableBB) const; 194 195 void inferReturnAttributes() const; 196 void inferArgAttributes() const; 197 198 bool tryToReplaceWithConstant(Value *V); 199 200 // Helper to check if \p LV is either a constant or a constant 201 // range with a single element. This should cover exactly the same cases as 202 // the old ValueLatticeElement::isConstant() and is intended to be used in the 203 // transition to ValueLatticeElement. 204 static bool isConstant(const ValueLatticeElement &LV); 205 206 // Helper to check if \p LV is either overdefined or a constant range with 207 // more than a single element. This should cover exactly the same cases as the 208 // old ValueLatticeElement::isOverdefined() and is intended to be used in the 209 // transition to ValueLatticeElement. 210 static bool isOverdefined(const ValueLatticeElement &LV); 211 }; 212 } // namespace llvm 213 214 #endif // LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H 215