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 shared between Function Specialization and SCCP Solver. 43 struct ArgInfo { 44 Argument *Formal; // The Formal argument being analysed. 45 Constant *Actual; // A corresponding actual constant argument. 46 47 ArgInfo(Argument *F, Constant *A) : Formal(F), Actual(A) {} 48 49 bool operator==(const ArgInfo &Other) const { 50 return Formal == Other.Formal && Actual == Other.Actual; 51 } 52 53 bool operator!=(const ArgInfo &Other) const { return !(*this == Other); } 54 55 friend hash_code hash_value(const ArgInfo &A) { 56 return hash_combine(hash_value(A.Formal), hash_value(A.Actual)); 57 } 58 }; 59 60 class SCCPInstVisitor; 61 62 //===----------------------------------------------------------------------===// 63 // 64 /// SCCPSolver - This interface class is a general purpose solver for Sparse 65 /// Conditional Constant Propagation (SCCP). 66 /// 67 class SCCPSolver { 68 std::unique_ptr<SCCPInstVisitor> Visitor; 69 70 public: 71 SCCPSolver(const DataLayout &DL, 72 std::function<const TargetLibraryInfo &(Function &)> GetTLI, 73 LLVMContext &Ctx); 74 75 ~SCCPSolver(); 76 77 void addPredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC); 78 79 /// markBlockExecutable - This method can be used by clients to mark all of 80 /// the blocks that are known to be intrinsically live in the processed unit. 81 /// This returns true if the block was not considered live before. 82 bool markBlockExecutable(BasicBlock *BB); 83 84 const PredicateBase *getPredicateInfoFor(Instruction *I); 85 86 /// trackValueOfGlobalVariable - Clients can use this method to 87 /// inform the SCCPSolver that it should track loads and stores to the 88 /// specified global variable if it can. This is only legal to call if 89 /// performing Interprocedural SCCP. 90 void trackValueOfGlobalVariable(GlobalVariable *GV); 91 92 /// addTrackedFunction - If the SCCP solver is supposed to track calls into 93 /// and out of the specified function (which cannot have its address taken), 94 /// this method must be called. 95 void addTrackedFunction(Function *F); 96 97 /// Add function to the list of functions whose return cannot be modified. 98 void addToMustPreserveReturnsInFunctions(Function *F); 99 100 /// Returns true if the return of the given function cannot be modified. 101 bool mustPreserveReturn(Function *F); 102 103 void addArgumentTrackedFunction(Function *F); 104 105 /// Returns true if the given function is in the solver's set of 106 /// argument-tracked functions. 107 bool isArgumentTrackedFunction(Function *F); 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(); 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 // isStructLatticeConstant - Return true if all the lattice values 157 // corresponding to elements of the structure are constants, 158 // false otherwise. 159 bool isStructLatticeConstant(Function *F, StructType *STy); 160 161 /// Helper to return a Constant if \p LV is either a constant or a constant 162 /// range with a single element. 163 Constant *getConstant(const ValueLatticeElement &LV, Type *Ty) const; 164 165 /// Return either a Constant or nullptr for a given Value. 166 Constant *getConstantOrNull(Value *V) const; 167 168 /// Return a reference to the set of argument tracked functions. 169 SmallPtrSetImpl<Function *> &getArgumentTrackedFunctions(); 170 171 /// Set the Lattice Value for the arguments of a specialization \p F. 172 /// If an argument is Constant then its lattice value is marked with the 173 /// corresponding actual argument in \p Args. Otherwise, its lattice value 174 /// is inherited (copied) from the corresponding formal argument in \p Args. 175 void setLatticeValueForSpecializationArguments(Function *F, 176 const SmallVectorImpl<ArgInfo> &Args); 177 178 /// Mark all of the blocks in function \p F non-executable. Clients can used 179 /// this method to erase a function from the module (e.g., if it has been 180 /// completely specialized and is no longer needed). 181 void markFunctionUnreachable(Function *F); 182 183 void visit(Instruction *I); 184 void visitCall(CallInst &I); 185 186 bool simplifyInstsInBlock(BasicBlock &BB, 187 SmallPtrSetImpl<Value *> &InsertedValues, 188 Statistic &InstRemovedStat, 189 Statistic &InstReplacedStat); 190 191 bool removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU, 192 BasicBlock *&NewUnreachableBB) const; 193 194 bool tryToReplaceWithConstant(Value *V); 195 196 // Helper to check if \p LV is either a constant or a constant 197 // range with a single element. This should cover exactly the same cases as 198 // the old ValueLatticeElement::isConstant() and is intended to be used in the 199 // transition to ValueLatticeElement. 200 static bool isConstant(const ValueLatticeElement &LV); 201 202 // Helper to check if \p LV is either overdefined or a constant range with 203 // more than a single element. This should cover exactly the same cases as the 204 // old ValueLatticeElement::isOverdefined() and is intended to be used in the 205 // transition to ValueLatticeElement. 206 static bool isOverdefined(const ValueLatticeElement &LV); 207 }; 208 } // namespace llvm 209 210 #endif // LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H 211