LLVM  10.0.0svn
IVUsers.h
Go to the documentation of this file.
1 //===- llvm/Analysis/IVUsers.h - Induction Variable Users -------*- 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 implements bookkeeping for "interesting" users of expressions
10 // computed from induction variables.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_ANALYSIS_IVUSERS_H
15 #define LLVM_ANALYSIS_IVUSERS_H
16 
18 #include "llvm/Analysis/LoopPass.h"
20 #include "llvm/IR/ValueHandle.h"
21 
22 namespace llvm {
23 
24 class AssumptionCache;
25 class DominatorTree;
26 class Instruction;
27 class Value;
28 class ScalarEvolution;
29 class SCEV;
30 class IVUsers;
31 class DataLayout;
32 
33 /// IVStrideUse - Keep track of one use of a strided induction variable.
34 /// The Expr member keeps track of the expression, User is the actual user
35 /// instruction of the operand, and 'OperandValToReplace' is the operand of
36 /// the User that is the use.
37 class IVStrideUse final : public CallbackVH, public ilist_node<IVStrideUse> {
38  friend class IVUsers;
39 public:
41  : CallbackVH(U), Parent(P), OperandValToReplace(O) {
42  }
43 
44  /// getUser - Return the user instruction for this use.
45  Instruction *getUser() const {
46  return cast<Instruction>(getValPtr());
47  }
48 
49  /// setUser - Assign a new user instruction for this use.
50  void setUser(Instruction *NewUser) {
51  setValPtr(NewUser);
52  }
53 
54  /// getOperandValToReplace - Return the Value of the operand in the user
55  /// instruction that this IVStrideUse is representing.
57  return OperandValToReplace;
58  }
59 
60  /// setOperandValToReplace - Assign a new Value as the operand value
61  /// to replace.
63  OperandValToReplace = Op;
64  }
65 
66  /// getPostIncLoops - Return the set of loops for which the expression has
67  /// been adjusted to use post-inc mode.
69  return PostIncLoops;
70  }
71 
72  /// transformToPostInc - Transform the expression to post-inc form for the
73  /// given loop.
74  void transformToPostInc(const Loop *L);
75 
76 private:
77  /// Parent - a pointer to the IVUsers that owns this IVStrideUse.
78  IVUsers *Parent;
79 
80  /// OperandValToReplace - The Value of the operand in the user instruction
81  /// that this IVStrideUse is representing.
82  WeakTrackingVH OperandValToReplace;
83 
84  /// PostIncLoops - The set of loops for which Expr has been adjusted to
85  /// use post-inc mode. This corresponds with SCEVExpander's post-inc concept.
86  PostIncLoopSet PostIncLoops;
87 
88  /// Deleted - Implementation of CallbackVH virtual function to
89  /// receive notification when the User is deleted.
90  void deleted() override;
91 };
92 
93 class IVUsers {
94  friend class IVStrideUse;
95  Loop *L;
96  AssumptionCache *AC;
97  LoopInfo *LI;
98  DominatorTree *DT;
99  ScalarEvolution *SE;
101 
102  /// IVUses - A list of all tracked IV uses of induction variable expressions
103  /// we are interested in.
104  ilist<IVStrideUse> IVUses;
105 
106  // Ephemeral values used by @llvm.assume in this function.
108 
109 public:
111  ScalarEvolution *SE);
112 
114  : L(std::move(X.L)), AC(std::move(X.AC)), DT(std::move(X.DT)),
115  SE(std::move(X.SE)), Processed(std::move(X.Processed)),
116  IVUses(std::move(X.IVUses)), EphValues(std::move(X.EphValues)) {
117  for (IVStrideUse &U : IVUses)
118  U.Parent = this;
119  }
120  IVUsers(const IVUsers &) = delete;
121  IVUsers &operator=(IVUsers &&) = delete;
122  IVUsers &operator=(const IVUsers &) = delete;
123 
124  Loop *getLoop() const { return L; }
125 
126  /// AddUsersIfInteresting - Inspect the specified Instruction. If it is a
127  /// reducible SCEV, recursively add its users to the IVUsesByStride set and
128  /// return true. Otherwise, return false.
129  bool AddUsersIfInteresting(Instruction *I);
130 
131  IVStrideUse &AddUser(Instruction *User, Value *Operand);
132 
133  /// getReplacementExpr - Return a SCEV expression which computes the
134  /// value of the OperandValToReplace of the given IVStrideUse.
135  const SCEV *getReplacementExpr(const IVStrideUse &IU) const;
136 
137  /// getExpr - Return the expression for the use.
138  const SCEV *getExpr(const IVStrideUse &IU) const;
139 
140  const SCEV *getStride(const IVStrideUse &IU, const Loop *L) const;
141 
144  iterator begin() { return IVUses.begin(); }
145  iterator end() { return IVUses.end(); }
146  const_iterator begin() const { return IVUses.begin(); }
147  const_iterator end() const { return IVUses.end(); }
148  bool empty() const { return IVUses.empty(); }
149 
150  bool isIVUserOrOperand(Instruction *Inst) const {
151  return Processed.count(Inst);
152  }
153 
154  void releaseMemory();
155 
156  void print(raw_ostream &OS, const Module * = nullptr) const;
157 
158  /// dump - This method is used for debugging.
159  void dump() const;
160 
161 protected:
162  bool AddUsersImpl(Instruction *I, SmallPtrSetImpl<Loop*> &SimpleLoopNests);
163 };
164 
166 
167 class IVUsersWrapperPass : public LoopPass {
168  std::unique_ptr<IVUsers> IU;
169 
170 public:
171  static char ID;
172 
174 
175  IVUsers &getIU() { return *IU; }
176  const IVUsers &getIU() const { return *IU; }
177 
178  void getAnalysisUsage(AnalysisUsage &AU) const override;
179 
180  bool runOnLoop(Loop *L, LPPassManager &LPM) override;
181 
182  void releaseMemory() override;
183 
184  void print(raw_ostream &OS, const Module * = nullptr) const override;
185 };
186 
187 /// Analysis pass that exposes the \c IVUsers for a loop.
188 class IVUsersAnalysis : public AnalysisInfoMixin<IVUsersAnalysis> {
190  static AnalysisKey Key;
191 
192 public:
193  typedef IVUsers Result;
194 
195  IVUsers run(Loop &L, LoopAnalysisManager &AM,
197 };
198 
199 }
200 
201 #endif
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
iterator begin()
Definition: IVUsers.h:144
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
Pass * createIVUsersPass()
Definition: IVUsers.cpp:54
The main scalar evolution driver.
CallbackVH & operator=(const CallbackVH &)=default
void setOperandValToReplace(Value *Op)
setOperandValToReplace - Assign a new Value as the operand value to replace.
Definition: IVUsers.h:62
A cache of @llvm.assume calls within a function.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
bool isIVUserOrOperand(Instruction *Inst) const
Definition: IVUsers.h:150
const IVUsers & getIU() const
Definition: IVUsers.h:176
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
void setValPtr(Value *P)
Definition: ValueHandle.h:386
Definition: BitVector.h:937
friend class IVUsers
Definition: IVUsers.h:38
Key
PAL metadata keys.
Value handle that is nullable, but tries to track the Value.
Definition: ValueHandle.h:181
This header provides classes for managing per-loop analyses.
iterator end()
Definition: IVUsers.h:145
ilist< IVStrideUse >::const_iterator const_iterator
Definition: IVUsers.h:143
Loop * getLoop() const
Definition: IVUsers.h:124
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
bool empty() const
Definition: IVUsers.h:148
#define P(N)
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
void setUser(Instruction *NewUser)
setUser - Assign a new user instruction for this use.
Definition: IVUsers.h:50
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:389
Represent the analysis usage information of a pass.
ilist< IVStrideUse >::iterator iterator
Definition: IVUsers.h:142
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
const PostIncLoopSet & getPostIncLoops() const
getPostIncLoops - Return the set of loops for which the expression has been adjusted to use post-inc ...
Definition: IVUsers.h:68
An intrusive list with ownership and callbacks specified/controlled by ilist_traits, only with API safe for polymorphic types.
Definition: ilist.h:388
Iterator for intrusive lists based on ilist_node.
IVStrideUse(IVUsers *P, Instruction *U, Value *O)
Definition: IVUsers.h:40
MCExpr const & getExpr(MCExpr const &Expr)
This class represents an analyzed expression in the program.
Analysis pass that exposes the IVUsers for a loop.
Definition: IVUsers.h:188
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:506
Value * getOperandValToReplace() const
getOperandValToReplace - Return the Value of the operand in the user instruction that this IVStrideUs...
Definition: IVUsers.h:56
#define I(x, y, z)
Definition: MD5.cpp:58
const_iterator begin() const
Definition: IVUsers.h:146
void transformToPostInc(const Loop *L)
transformToPostInc - Transform the expression to post-inc form for the given loop.
Definition: IVUsers.cpp:417
IVUsers(IVUsers &&X)
Definition: IVUsers.h:113
LLVM Value Representation.
Definition: Value.h:72
const_iterator end() const
Definition: IVUsers.h:147
IVStrideUse - Keep track of one use of a strided induction variable.
Definition: IVUsers.h:37
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:379
A container for analyses that lazily runs them and caches their results.
Instruction * getUser() const
getUser - Return the user instruction for this use.
Definition: IVUsers.h:45
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
Value * getValPtr() const
Definition: ValueHandle.h:95