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