1 //===------ ForwardOpTree.h -------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Move instructions between statements.
12 //===----------------------------------------------------------------------===//
14 #include "polly/ForwardOpTree.h"
16 #include "polly/ScopInfo.h"
17 #include "polly/ScopPass.h"
18 #include "polly/Support/GICHelper.h"
19 #include "polly/Support/VirtualInstruction.h"
20 #include "llvm/Analysis/ValueTracking.h"
22 #define DEBUG_TYPE "polly-delicm"
24 using namespace polly
;
27 STATISTIC(TotalInstructionsCopied
, "Number of copied instructions");
28 STATISTIC(TotalForwardedTrees
, "Number of forwarded operand trees");
29 STATISTIC(TotalModifiedStmts
,
30 "Number of statements with at least one forwarded tree");
32 STATISTIC(ScopsModified
, "Number of SCoPs with at least one forwarded tree");
36 /// The state of whether an operand tree was/can be forwarded.
37 enum ForwardingDecision
{
43 /// Implementation of operand tree forwarding for a specific SCoP.
45 /// For a statement that requires a scalar value (through a value read
46 /// MemoryAccess), see if its operand can be moved into the statement. If so,
47 /// the MemoryAccess is removed and the all the operand tree instructions are
48 /// moved into the statement. All original instructions are left in the source
49 /// statements. The simplification pass can clean these up.
50 class ForwardOpTreeImpl
{
52 /// The SCoP we are currently processing.
55 /// LoopInfo is required for VirtualUse.
58 /// How many instructions have been copied to other statements.
59 int NumInstructionsCopied
= 0;
61 /// How many operand trees have been forwarded.
62 int NumForwardedTrees
= 0;
64 /// Number of statements with at least one forwarded operand tree.
65 int NumModifiedStmts
= 0;
67 /// Whether we carried out at least one change to the SCoP.
68 bool Modified
= false;
70 void printStatistics(raw_ostream
&OS
, int Indent
= 0) {
71 OS
.indent(Indent
) << "Statistics {\n";
72 OS
.indent(Indent
+ 4) << "Instructions copied: " << NumInstructionsCopied
74 OS
.indent(Indent
+ 4) << "Operand trees forwarded: " << NumForwardedTrees
76 OS
.indent(Indent
+ 4) << "Statements with forwarded operand trees: "
77 << NumModifiedStmts
<< '\n';
78 OS
.indent(Indent
) << "}\n";
81 void printStatements(llvm::raw_ostream
&OS
, int Indent
= 0) const {
82 OS
.indent(Indent
) << "After statements {\n";
83 for (auto &Stmt
: *S
) {
84 OS
.indent(Indent
+ 4) << Stmt
.getBaseName() << "\n";
88 OS
.indent(Indent
+ 12);
89 Stmt
.printInstructions(OS
);
91 OS
.indent(Indent
) << "}\n";
94 /// Determines whether an operand tree can be forwarded or carries out a
95 /// forwarding, depending on the @p DoIt flag.
97 /// @param TargetStmt The statement the operand tree will be copied to.
98 /// @param UseVal The value (usually an instruction) which is root of an
100 /// @param UseStmt The statement that uses @p UseVal.
101 /// @param UseLoop The loop @p UseVal is used in.
102 /// @param DoIt If false, only determine whether an operand tree can be
103 /// forwarded. If true, carry out the forwarding. Do not use
104 /// DoIt==true if an operand tree is not known to be
107 /// @return When DoIt==true, return whether the operand tree can be forwarded.
108 /// When DoIt==false, return FD_DidForward.
109 ForwardingDecision
canForwardTree(ScopStmt
*TargetStmt
, Value
*UseVal
,
110 ScopStmt
*UseStmt
, Loop
*UseLoop
,
113 // PHis are not yet supported.
114 if (isa
<PHINode
>(UseVal
)) {
115 DEBUG(dbgs() << " Cannot forward PHI: " << *UseVal
<< "\n");
116 return FD_CannotForward
;
119 VirtualUse VUse
= VirtualUse::create(UseStmt
, UseLoop
, UseVal
, true);
120 switch (VUse
.getKind()) {
121 case VirtualUse::Constant
:
122 case VirtualUse::Block
:
123 // These can be used anywhere without special considerations.
125 return FD_DidForward
;
126 return FD_CanForward
;
128 case VirtualUse::Synthesizable
:
129 // Not supported yet.
130 DEBUG(dbgs() << " Cannot forward synthesizable: " << *UseVal
<< "\n");
131 return FD_CannotForward
;
133 case VirtualUse::Hoisted
:
134 // Not supported yet.
135 DEBUG(dbgs() << " Cannot forward hoisted load: " << *UseVal
<< "\n");
136 return FD_CannotForward
;
138 case VirtualUse::ReadOnly
:
139 // Not supported yet.
140 DEBUG(dbgs() << " Cannot forward read-only val: " << *UseVal
<< "\n");
141 return FD_CannotForward
;
143 case VirtualUse::Intra
:
144 case VirtualUse::Inter
:
145 auto Inst
= cast
<Instruction
>(UseVal
);
147 // Compatible instructions must satisfy the following conditions:
148 // 1. Idempotent (instruction will be copied, not moved; although its
149 // original instance might be removed by simplification)
150 // 2. Not access memory (There might be memory writes between)
151 // 3. Not cause undefined behaviour (we might copy to a location when the
152 // original instruction was no executed; this is currently not possible
153 // because we do not forward PHINodes)
154 // 4. Not leak memory if executed multiple times (I am looking at you,
157 // Instruction::mayHaveSideEffects is not sufficient because it considers
158 // malloc to not have side-effects. llvm::isSafeToSpeculativelyExecute is
159 // not sufficient because it allows memory accesses.
160 if (mayBeMemoryDependent(*Inst
)) {
161 DEBUG(dbgs() << " Cannot forward side-effect instruction: " << *Inst
163 return FD_CannotForward
;
166 Loop
*DefLoop
= LI
->getLoopFor(Inst
->getParent());
167 ScopStmt
*DefStmt
= S
->getStmtFor(Inst
);
168 assert(DefStmt
&& "Value must be defined somewhere");
171 // To ensure the right order, prepend this instruction before its
172 // operands. This ensures that its operands are inserted before the
173 // instruction using them.
174 // TODO: The operand tree is not really a tree, but a DAG. We should be
175 // able to handle DAGs without duplication.
176 TargetStmt
->prependInstrunction(Inst
);
177 NumInstructionsCopied
++;
178 TotalInstructionsCopied
++;
181 for (Value
*OpVal
: Inst
->operand_values()) {
182 ForwardingDecision OpDecision
=
183 canForwardTree(TargetStmt
, OpVal
, DefStmt
, DefLoop
, DoIt
);
184 switch (OpDecision
) {
185 case FD_CannotForward
:
187 return FD_CannotForward
;
200 return FD_DidForward
;
201 return FD_CanForward
;
204 llvm_unreachable("Case unhandled");
207 /// Try to forward an operand tree rooted in @p RA.
208 bool tryForwardTree(MemoryAccess
*RA
) {
209 assert(RA
->isLatestScalarKind());
210 DEBUG(dbgs() << "Trying to forward operand tree " << RA
<< "...\n");
212 ScopStmt
*Stmt
= RA
->getStatement();
213 Loop
*InLoop
= Stmt
->getSurroundingLoop();
215 ForwardingDecision Assessment
=
216 canForwardTree(Stmt
, RA
->getAccessValue(), Stmt
, InLoop
, false);
217 assert(Assessment
!= FD_DidForward
);
218 if (Assessment
== FD_CannotForward
)
221 ForwardingDecision Execution
=
222 canForwardTree(Stmt
, RA
->getAccessValue(), Stmt
, InLoop
, true);
223 assert(Execution
== FD_DidForward
);
225 Stmt
->removeSingleMemoryAccess(RA
);
230 ForwardOpTreeImpl(Scop
*S
, LoopInfo
*LI
) : S(S
), LI(LI
) {}
232 /// Return which SCoP this instance is processing.
233 Scop
*getScop() const { return S
; }
235 /// Run the algorithm: Use value read accesses as operand tree roots and try
236 /// to forward them into the statement.
237 bool forwardOperandTrees() {
238 for (ScopStmt
&Stmt
: *S
) {
239 // Currently we cannot modify the instruction list of region statements.
240 if (!Stmt
.isBlockStmt())
243 bool StmtModified
= false;
245 // Because we are modifying the MemoryAccess list, collect them first to
246 // avoid iterator invalidation.
247 SmallVector
<MemoryAccess
*, 16> Accs
;
248 for (MemoryAccess
*RA
: Stmt
) {
251 if (!RA
->isLatestScalarKind())
257 for (MemoryAccess
*RA
: Accs
) {
258 if (tryForwardTree(RA
)) {
262 TotalForwardedTrees
++;
268 TotalModifiedStmts
++;
277 /// Print the pass result, performed transformations and the SCoP after the
279 void print(llvm::raw_ostream
&OS
, int Indent
= 0) {
280 printStatistics(OS
, Indent
);
283 // This line can easily be checked in regression tests.
284 OS
<< "ForwardOpTree executed, but did not modify anything\n";
288 printStatements(OS
, Indent
);
292 /// Pass that redirects scalar reads to array elements that are known to contain
295 /// This reduces the number of scalar accesses and therefore potentially
296 /// increases the freedom of the scheduler. In the ideal case, all reads of a
297 /// scalar definition are redirected (We currently do not care about removing
298 /// the write in this case). This is also useful for the main DeLICM pass as
299 /// there are less scalars to be mapped.
300 class ForwardOpTree
: public ScopPass
{
302 ForwardOpTree(const ForwardOpTree
&) = delete;
303 const ForwardOpTree
&operator=(const ForwardOpTree
&) = delete;
305 /// The pass implementation, also holding per-scop data.
306 std::unique_ptr
<ForwardOpTreeImpl
> Impl
;
311 explicit ForwardOpTree() : ScopPass(ID
) {}
313 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const override
{
314 AU
.addRequiredTransitive
<ScopInfoRegionPass
>();
315 AU
.addRequired
<LoopInfoWrapperPass
>();
316 AU
.setPreservesAll();
319 virtual bool runOnScop(Scop
&S
) override
{
320 // Free resources for previous SCoP's computation, if not yet done.
323 LoopInfo
&LI
= getAnalysis
<LoopInfoWrapperPass
>().getLoopInfo();
324 Impl
= make_unique
<ForwardOpTreeImpl
>(&S
, &LI
);
326 DEBUG(dbgs() << "Forwarding operand trees...\n");
327 Impl
->forwardOperandTrees();
329 DEBUG(dbgs() << "\nFinal Scop:\n");
335 virtual void printScop(raw_ostream
&OS
, Scop
&S
) const override
{
339 assert(Impl
->getScop() == &S
);
343 virtual void releaseMemory() override
{ Impl
.reset(); }
345 }; // class ForwardOpTree
347 char ForwardOpTree::ID
;
348 } // anonymous namespace
350 ScopPass
*polly::createForwardOpTreePass() { return new ForwardOpTree(); }
352 INITIALIZE_PASS_BEGIN(ForwardOpTree
, "polly-optree",
353 "Polly - Forward operand tree", false, false)
354 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass
)
355 INITIALIZE_PASS_END(ForwardOpTree
, "polly-optree",
356 "Polly - Forward operand tree", false, false)