1 //===- LazyValueInfo.h - Value constraint analysis --------------*- 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 // This file defines the interface for lazy computation of value constraint
10 // information.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_ANALYSIS_LAZYVALUEINFO_H
15 #define LLVM_ANALYSIS_LAZYVALUEINFO_H
16 
17 #include "llvm/IR/PassManager.h"
18 #include "llvm/Pass.h"
19 
20 namespace llvm {
21   class AssumptionCache;
22   class Constant;
23   class ConstantRange;
24   class DataLayout;
25   class DominatorTree;
26   class Instruction;
27   class TargetLibraryInfo;
28   class Value;
29   class LazyValueInfoImpl;
30   /// This pass computes, caches, and vends lazy value constraint information.
31   class LazyValueInfo {
32     friend class LazyValueInfoWrapperPass;
33     AssumptionCache *AC = nullptr;
34     const DataLayout *DL = nullptr;
35     LazyValueInfoImpl *PImpl = nullptr;
36     LazyValueInfo(const LazyValueInfo &) = delete;
37     void operator=(const LazyValueInfo &) = delete;
38 
39     LazyValueInfoImpl *getImpl();
40     LazyValueInfoImpl &getOrCreateImpl(const Module *M);
41 
42   public:
43     ~LazyValueInfo();
44     LazyValueInfo() = default;
LazyValueInfo(AssumptionCache * AC_,const DataLayout * DL_)45     LazyValueInfo(AssumptionCache *AC_, const DataLayout *DL_)
46         : AC(AC_), DL(DL_) {}
LazyValueInfo(LazyValueInfo && Arg)47     LazyValueInfo(LazyValueInfo &&Arg)
48         : AC(Arg.AC), DL(Arg.DL), PImpl(Arg.PImpl) {
49       Arg.PImpl = nullptr;
50     }
51     LazyValueInfo &operator=(LazyValueInfo &&Arg) {
52       releaseMemory();
53       AC = Arg.AC;
54       DL = Arg.DL;
55       PImpl = Arg.PImpl;
56       Arg.PImpl = nullptr;
57       return *this;
58     }
59 
60     /// This is used to return true/false/dunno results.
61     enum Tristate { Unknown = -1, False = 0, True = 1 };
62 
63     // Public query interface.
64 
65     /// Determine whether the specified value comparison with a constant is
66     /// known to be true or false on the specified CFG edge. Pred is a CmpInst
67     /// predicate.
68     Tristate getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
69                                 BasicBlock *FromBB, BasicBlock *ToBB,
70                                 Instruction *CxtI = nullptr);
71 
72     /// Determine whether the specified value comparison with a constant is
73     /// known to be true or false at the specified instruction. \p Pred is a
74     /// CmpInst predicate. If \p UseBlockValue is true, the block value is also
75     /// taken into account.
76     Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C,
77                             Instruction *CxtI, bool UseBlockValue);
78 
79     /// Determine whether the specified value comparison is known to be true
80     /// or false at the specified instruction. While this takes two Value's,
81     /// it still requires that one of them is a constant.
82     /// \p Pred is a CmpInst predicate.
83     /// If \p UseBlockValue is true, the block value is also taken into account.
84     Tristate getPredicateAt(unsigned Pred, Value *LHS, Value *RHS,
85                             Instruction *CxtI, bool UseBlockValue);
86 
87     /// Determine whether the specified value is known to be a constant at the
88     /// specified instruction. Return null if not.
89     Constant *getConstant(Value *V, Instruction *CxtI);
90 
91     /// Return the ConstantRange constraint that is known to hold for the
92     /// specified value at the specified instruction. This may only be called
93     /// on integer-typed Values.
94     ConstantRange getConstantRange(Value *V, Instruction *CxtI,
95                                    bool UndefAllowed);
96 
97     /// Return the ConstantRange constraint that is known to hold for the value
98     /// at a specific use-site.
99     ConstantRange getConstantRangeAtUse(const Use &U, bool UndefAllowed);
100 
101     /// Determine whether the specified value is known to be a
102     /// constant on the specified edge.  Return null if not.
103     Constant *getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
104                                 Instruction *CxtI = nullptr);
105 
106     /// Return the ConstantRage constraint that is known to hold for the
107     /// specified value on the specified edge. This may be only be called
108     /// on integer-typed Values.
109     ConstantRange getConstantRangeOnEdge(Value *V, BasicBlock *FromBB,
110                                          BasicBlock *ToBB,
111                                          Instruction *CxtI = nullptr);
112 
113     /// Inform the analysis cache that we have threaded an edge from
114     /// PredBB to OldSucc to be from PredBB to NewSucc instead.
115     void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
116                     BasicBlock *NewSucc);
117 
118     /// Remove information related to this value from the cache.
119     void forgetValue(Value *V);
120 
121     /// Inform the analysis cache that we have erased a block.
122     void eraseBlock(BasicBlock *BB);
123 
124     /// Complete flush all previously computed values
125     void clear();
126 
127     /// Print the \LazyValueInfo Analysis.
128     /// We pass in the DTree that is required for identifying which basic blocks
129     /// we can solve/print for, in the LVIPrinter.
130     void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS);
131 
132     // For old PM pass. Delete once LazyValueInfoWrapperPass is gone.
133     void releaseMemory();
134 
135     /// Handle invalidation events in the new pass manager.
136     bool invalidate(Function &F, const PreservedAnalyses &PA,
137                     FunctionAnalysisManager::Invalidator &Inv);
138   };
139 
140 /// Analysis to compute lazy value information.
141 class LazyValueAnalysis : public AnalysisInfoMixin<LazyValueAnalysis> {
142 public:
143   typedef LazyValueInfo Result;
144   Result run(Function &F, FunctionAnalysisManager &FAM);
145 
146 private:
147   static AnalysisKey Key;
148   friend struct AnalysisInfoMixin<LazyValueAnalysis>;
149 };
150 
151 /// Printer pass for the LazyValueAnalysis results.
152 class LazyValueInfoPrinterPass
153     : public PassInfoMixin<LazyValueInfoPrinterPass> {
154   raw_ostream &OS;
155 
156 public:
157   explicit LazyValueInfoPrinterPass(raw_ostream &OS) : OS(OS) {}
158 
159   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
160 
161   static bool isRequired() { return true; }
162 };
163 
164 /// Wrapper around LazyValueInfo.
165 class LazyValueInfoWrapperPass : public FunctionPass {
166   LazyValueInfoWrapperPass(const LazyValueInfoWrapperPass&) = delete;
167   void operator=(const LazyValueInfoWrapperPass&) = delete;
168 public:
169   static char ID;
170   LazyValueInfoWrapperPass();
171   ~LazyValueInfoWrapperPass() override {
172     assert(!Info.PImpl && "releaseMemory not called");
173   }
174 
175   LazyValueInfo &getLVI();
176 
177   void getAnalysisUsage(AnalysisUsage &AU) const override;
178   void releaseMemory() override;
179   bool runOnFunction(Function &F) override;
180 private:
181   LazyValueInfo Info;
182 };
183 
184 }  // end namespace llvm
185 
186 #endif
187 
188