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 
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   class TargetLibraryInfo *TLI = nullptr;
36   void *PImpl = nullptr;
37   LazyValueInfo(const LazyValueInfo&) = delete;
38   void operator=(const LazyValueInfo&) = delete;
39 public:
40   ~LazyValueInfo();
41   LazyValueInfo() = default;
42   LazyValueInfo(AssumptionCache *AC_, const DataLayout *DL_,
43                 TargetLibraryInfo *TLI_)
44       : AC(AC_), DL(DL_), TLI(TLI_) {}
45   LazyValueInfo(LazyValueInfo &&Arg)
46       : AC(Arg.AC), DL(Arg.DL), TLI(Arg.TLI), PImpl(Arg.PImpl) {
47     Arg.PImpl = nullptr;
48   }
49   LazyValueInfo &operator=(LazyValueInfo &&Arg) {
50     releaseMemory();
51     AC = Arg.AC;
52     DL = Arg.DL;
53     TLI = Arg.TLI;
54     PImpl = Arg.PImpl;
55     Arg.PImpl = nullptr;
56     return *this;
57   }
58 
59   /// This is used to return true/false/dunno results.
60   enum Tristate {
61     Unknown = -1, False = 0, True = 1
62   };
63 
64   // Public query interface.
65 
66   /// Determine whether the specified value comparison with a constant is known
67   /// to be true or false on the specified CFG edge.
68   /// Pred is a CmpInst predicate.
69   Tristate getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
70                               BasicBlock *FromBB, BasicBlock *ToBB,
71                               Instruction *CxtI = nullptr);
72 
73   /// Determine whether the specified value comparison with a constant is known
74   /// to be true or false at the specified instruction.
75   /// \p Pred is a CmpInst predicate. If \p UseBlockValue is true, the block
76   /// value is also taken into account.
77   Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C,
78                           Instruction *CxtI, bool UseBlockValue);
79 
80   /// Determine whether the specified value comparison is known to be true
81   /// or false at the specified instruction. While this takes two Value's,
82   /// it still requires that one of them is a constant.
83   /// \p Pred is a CmpInst predicate.
84   /// If \p UseBlockValue is true, the block value is also taken into account.
85   Tristate getPredicateAt(unsigned Pred, Value *LHS, Value *RHS,
86                           Instruction *CxtI, bool UseBlockValue);
87 
88   /// Determine whether the specified value is known to be a constant at the
89   /// specified instruction. Return null if not.
90   Constant *getConstant(Value *V, Instruction *CxtI);
91 
92   /// Return the ConstantRange constraint that is known to hold for the
93   /// specified value at the specified instruction. This may only be called
94   /// on integer-typed Values.
95   ConstantRange getConstantRange(Value *V, Instruction *CxtI,
96                                  bool UndefAllowed = true);
97 
98   /// Return the ConstantRange constraint that is known to hold for the value
99   /// at a specific use-site.
100   ConstantRange getConstantRangeAtUse(const Use &U, bool UndefAllowed = true);
101 
102   /// Determine whether the specified value is known to be a
103   /// constant on the specified edge.  Return null if not.
104   Constant *getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
105                               Instruction *CxtI = nullptr);
106 
107   /// Return the ConstantRage constraint that is known to hold for the
108   /// specified value on the specified edge. This may be only be called
109   /// on integer-typed Values.
110   ConstantRange getConstantRangeOnEdge(Value *V, BasicBlock *FromBB,
111                                        BasicBlock *ToBB,
112                                        Instruction *CxtI = nullptr);
113 
114   /// Inform the analysis cache that we have threaded an edge from
115   /// PredBB to OldSucc to be from PredBB to NewSucc instead.
116   void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, 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(const Module *M);
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 /// Wrapper around LazyValueInfo.
152 class LazyValueInfoWrapperPass : public FunctionPass {
153   LazyValueInfoWrapperPass(const LazyValueInfoWrapperPass&) = delete;
154   void operator=(const LazyValueInfoWrapperPass&) = delete;
155 public:
156   static char ID;
157   LazyValueInfoWrapperPass();
158   ~LazyValueInfoWrapperPass() override {
159     assert(!Info.PImpl && "releaseMemory not called");
160   }
161 
162   LazyValueInfo &getLVI();
163 
164   void getAnalysisUsage(AnalysisUsage &AU) const override;
165   void releaseMemory() override;
166   bool runOnFunction(Function &F) override;
167 private:
168   LazyValueInfo Info;
169 };
170 
171 }  // end namespace llvm
172 
173 #endif
174 
175