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/Analysis/TargetLibraryInfo.h" 20 #include "llvm/Analysis/ValueLattice.h" 21 #include "llvm/Analysis/ValueLatticeUtils.h" 22 #include "llvm/IR/InstVisitor.h" 23 #include "llvm/Transforms/Utils/PredicateInfo.h" 24 #include <cassert> 25 #include <utility> 26 #include <vector> 27 28 namespace llvm { 29 30 /// Helper struct for bundling up the analysis results per function for IPSCCP. 31 struct AnalysisResultsForFn { 32 std::unique_ptr<PredicateInfo> PredInfo; 33 DominatorTree *DT; 34 PostDominatorTree *PDT; 35 }; 36 37 class SCCPInstVisitor; 38 39 //===----------------------------------------------------------------------===// 40 // 41 /// SCCPSolver - This interface class is a general purpose solver for Sparse 42 /// Conditional Constant Propagation (SCCP). 43 /// 44 class SCCPSolver { 45 std::unique_ptr<SCCPInstVisitor> Visitor; 46 47 public: 48 SCCPSolver(const DataLayout &DL, 49 std::function<const TargetLibraryInfo &(Function &)> GetTLI, 50 LLVMContext &Ctx); 51 52 ~SCCPSolver(); 53 54 void addAnalysis(Function &F, AnalysisResultsForFn A); 55 56 /// markBlockExecutable - This method can be used by clients to mark all of 57 /// the blocks that are known to be intrinsically live in the processed unit. 58 /// This returns true if the block was not considered live before. 59 bool markBlockExecutable(BasicBlock *BB); 60 61 const PredicateBase *getPredicateInfoFor(Instruction *I); 62 63 DomTreeUpdater getDTU(Function &F); 64 65 /// trackValueOfGlobalVariable - Clients can use this method to 66 /// inform the SCCPSolver that it should track loads and stores to the 67 /// specified global variable if it can. This is only legal to call if 68 /// performing Interprocedural SCCP. 69 void trackValueOfGlobalVariable(GlobalVariable *GV); 70 71 /// addTrackedFunction - If the SCCP solver is supposed to track calls into 72 /// and out of the specified function (which cannot have its address taken), 73 /// this method must be called. 74 void addTrackedFunction(Function *F); 75 76 /// Add function to the list of functions whose return cannot be modified. 77 void addToMustPreserveReturnsInFunctions(Function *F); 78 79 /// Returns true if the return of the given function cannot be modified. 80 bool mustPreserveReturn(Function *F); 81 82 void addArgumentTrackedFunction(Function *F); 83 84 /// Returns true if the given function is in the solver's set of 85 /// argument-tracked functions. 86 bool isArgumentTrackedFunction(Function *F); 87 88 /// Solve - Solve for constants and executable blocks. 89 void solve(); 90 91 /// resolvedUndefsIn - While solving the dataflow for a function, we assume 92 /// that branches on undef values cannot reach any of their successors. 93 /// However, this is not a safe assumption. After we solve dataflow, this 94 /// method should be use to handle this. If this returns true, the solver 95 /// should be rerun. 96 bool resolvedUndefsIn(Function &F); 97 98 bool isBlockExecutable(BasicBlock *BB) const; 99 100 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic 101 // block to the 'To' basic block is currently feasible. 102 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const; 103 104 std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const; 105 106 void removeLatticeValueFor(Value *V); 107 108 const ValueLatticeElement &getLatticeValueFor(Value *V) const; 109 110 /// getTrackedRetVals - Get the inferred return value map. 111 const MapVector<Function *, ValueLatticeElement> &getTrackedRetVals(); 112 113 /// getTrackedGlobals - Get and return the set of inferred initializers for 114 /// global variables. 115 const DenseMap<GlobalVariable *, ValueLatticeElement> &getTrackedGlobals(); 116 117 /// getMRVFunctionsTracked - Get the set of functions which return multiple 118 /// values tracked by the pass. 119 const SmallPtrSet<Function *, 16> getMRVFunctionsTracked(); 120 121 /// markOverdefined - Mark the specified value overdefined. This 122 /// works with both scalars and structs. 123 void markOverdefined(Value *V); 124 125 // isStructLatticeConstant - Return true if all the lattice values 126 // corresponding to elements of the structure are constants, 127 // false otherwise. 128 bool isStructLatticeConstant(Function *F, StructType *STy); 129 130 /// Helper to return a Constant if \p LV is either a constant or a constant 131 /// range with a single element. 132 Constant *getConstant(const ValueLatticeElement &LV) const; 133 134 /// Return a reference to the set of argument tracked functions. 135 SmallPtrSetImpl<Function *> &getArgumentTrackedFunctions(); 136 137 /// Mark argument \p A constant with value \p C in a new function 138 /// specialization. The argument's parent function is a specialization of the 139 /// original function \p F. All other arguments of the specialization inherit 140 /// the lattice state of their corresponding values in the original function. 141 void markArgInFuncSpecialization(Function *F, Argument *A, Constant *C); 142 143 /// Mark all of the blocks in function \p F non-executable. Clients can used 144 /// this method to erase a function from the module (e.g., if it has been 145 /// completely specialized and is no longer needed). 146 void markFunctionUnreachable(Function *F); 147 148 void visit(Instruction *I); 149 void visitCall(CallInst &I); 150 }; 151 152 } // namespace llvm 153 154 #endif // LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H 155