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