1 //===- llvm/Analysis/IVUsers.h - Induction Variable Users -------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This file implements bookkeeping for "interesting" users of expressions
10 // computed from induction variables.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ANALYSIS_IVUSERS_H
15 #define LLVM_ANALYSIS_IVUSERS_H
17 #include "llvm/Analysis/LoopAnalysisManager.h"
18 #include "llvm/Analysis/LoopPass.h"
19 #include "llvm/Analysis/ScalarEvolutionNormalization.h"
20 #include "llvm/IR/ValueHandle.h"
24 class AssumptionCache
;
28 class ScalarEvolution
;
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
> {
40 IVStrideUse(IVUsers
*P
, Instruction
* U
, Value
*O
)
41 : CallbackVH(U
), Parent(P
), OperandValToReplace(O
) {
44 /// getUser - Return the user instruction for this use.
45 Instruction
*getUser() const {
46 return cast
<Instruction
>(getValPtr());
49 /// setUser - Assign a new user instruction for this use.
50 void setUser(Instruction
*NewUser
) {
54 /// getOperandValToReplace - Return the Value of the operand in the user
55 /// instruction that this IVStrideUse is representing.
56 Value
*getOperandValToReplace() const {
57 return OperandValToReplace
;
60 /// setOperandValToReplace - Assign a new Value as the operand value
62 void setOperandValToReplace(Value
*Op
) {
63 OperandValToReplace
= Op
;
66 /// getPostIncLoops - Return the set of loops for which the expression has
67 /// been adjusted to use post-inc mode.
68 const PostIncLoopSet
&getPostIncLoops() const {
72 /// transformToPostInc - Transform the expression to post-inc form for the
74 void transformToPostInc(const Loop
*L
);
77 /// Parent - a pointer to the IVUsers that owns this IVStrideUse.
80 /// OperandValToReplace - The Value of the operand in the user instruction
81 /// that this IVStrideUse is representing.
82 WeakTrackingVH OperandValToReplace
;
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
;
88 /// Deleted - Implementation of CallbackVH virtual function to
89 /// receive notification when the User is deleted.
90 void deleted() override
;
94 friend class IVStrideUse
;
100 SmallPtrSet
<Instruction
*, 16> Processed
;
102 /// IVUses - A list of all tracked IV uses of induction variable expressions
103 /// we are interested in.
104 ilist
<IVStrideUse
> IVUses
;
106 // Ephemeral values used by @llvm.assume in this function.
107 SmallPtrSet
<const Value
*, 32> EphValues
;
110 IVUsers(Loop
*L
, AssumptionCache
*AC
, LoopInfo
*LI
, DominatorTree
*DT
,
111 ScalarEvolution
*SE
);
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
)
120 IVUsers(const IVUsers
&) = delete;
121 IVUsers
&operator=(IVUsers
&&) = delete;
122 IVUsers
&operator=(const IVUsers
&) = delete;
124 Loop
*getLoop() const { return L
; }
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
);
131 IVStrideUse
&AddUser(Instruction
*User
, Value
*Operand
);
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;
137 /// getExpr - Return the expression for the use.
138 const SCEV
*getExpr(const IVStrideUse
&IU
) const;
140 const SCEV
*getStride(const IVStrideUse
&IU
, const Loop
*L
) const;
142 typedef ilist
<IVStrideUse
>::iterator iterator
;
143 typedef ilist
<IVStrideUse
>::const_iterator const_iterator
;
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(); }
150 bool isIVUserOrOperand(Instruction
*Inst
) const {
151 return Processed
.count(Inst
);
154 void releaseMemory();
156 void print(raw_ostream
&OS
, const Module
* = nullptr) const;
158 /// dump - This method is used for debugging.
162 bool AddUsersImpl(Instruction
*I
, SmallPtrSetImpl
<Loop
*> &SimpleLoopNests
);
165 Pass
*createIVUsersPass();
167 class IVUsersWrapperPass
: public LoopPass
{
168 std::unique_ptr
<IVUsers
> IU
;
173 IVUsersWrapperPass();
175 IVUsers
&getIU() { return *IU
; }
176 const IVUsers
&getIU() const { return *IU
; }
178 void getAnalysisUsage(AnalysisUsage
&AU
) const override
;
180 bool runOnLoop(Loop
*L
, LPPassManager
&LPM
) override
;
182 void releaseMemory() override
;
184 void print(raw_ostream
&OS
, const Module
* = nullptr) const override
;
187 /// Analysis pass that exposes the \c IVUsers for a loop.
188 class IVUsersAnalysis
: public AnalysisInfoMixin
<IVUsersAnalysis
> {
189 friend AnalysisInfoMixin
<IVUsersAnalysis
>;
190 static AnalysisKey Key
;
193 typedef IVUsers Result
;
195 IVUsers
run(Loop
&L
, LoopAnalysisManager
&AM
,
196 LoopStandardAnalysisResults
&AR
);