xref: /openbsd-src/gnu/llvm/llvm/include/llvm/Transforms/Utils/SCCPSolver.h (revision d415bd752c734aee168c4ee86ff32e8cc249eb16)
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