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   /// Inform the analysis cache that we have erased a block.
119   void eraseBlock(BasicBlock *BB);
120 
121   /// Complete flush all previously computed values
122   void clear(const Module *M);
123 
124   /// Print the \LazyValueInfo Analysis.
125   /// We pass in the DTree that is required for identifying which basic blocks
126   /// we can solve/print for, in the LVIPrinter.
127   void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS);
128 
129   // For old PM pass. Delete once LazyValueInfoWrapperPass is gone.
130   void releaseMemory();
131 
132   /// Handle invalidation events in the new pass manager.
133   bool invalidate(Function &F, const PreservedAnalyses &PA,
134                   FunctionAnalysisManager::Invalidator &Inv);
135 };
136 
137 /// Analysis to compute lazy value information.
138 class LazyValueAnalysis : public AnalysisInfoMixin<LazyValueAnalysis> {
139 public:
140   typedef LazyValueInfo Result;
141   Result run(Function &F, FunctionAnalysisManager &FAM);
142 
143 private:
144   static AnalysisKey Key;
145   friend struct AnalysisInfoMixin<LazyValueAnalysis>;
146 };
147 
148 /// Wrapper around LazyValueInfo.
149 class LazyValueInfoWrapperPass : public FunctionPass {
150   LazyValueInfoWrapperPass(const LazyValueInfoWrapperPass&) = delete;
151   void operator=(const LazyValueInfoWrapperPass&) = delete;
152 public:
153   static char ID;
154   LazyValueInfoWrapperPass();
155   ~LazyValueInfoWrapperPass() override {
156     assert(!Info.PImpl && "releaseMemory not called");
157   }
158 
159   LazyValueInfo &getLVI();
160 
161   void getAnalysisUsage(AnalysisUsage &AU) const override;
162   void releaseMemory() override;
163   bool runOnFunction(Function &F) override;
164 private:
165   LazyValueInfo Info;
166 };
167 
168 }  // end namespace llvm
169 
170 #endif
171 
172