1//===- ForwardOpTree.h ------------------------------------------*- 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// Move instructions between statements.
10//
11//===----------------------------------------------------------------------===//
12
13#include "polly/ForwardOpTree.h"
14#include "polly/Options.h"
15#include "polly/ScopBuilder.h"
16#include "polly/ScopInfo.h"
17#include "polly/ScopPass.h"
18#include "polly/Support/GICHelper.h"
19#include "polly/Support/ISLOStream.h"
20#include "polly/Support/ISLTools.h"
21#include "polly/Support/VirtualInstruction.h"
22#include "polly/ZoneAlgo.h"
23#include "llvm/ADT/STLExtras.h"
24#include "llvm/ADT/SmallVector.h"
25#include "llvm/ADT/Statistic.h"
26#include "llvm/Analysis/LoopInfo.h"
27#include "llvm/Analysis/ValueTracking.h"
28#include "llvm/IR/Instruction.h"
29#include "llvm/IR/Instructions.h"
30#include "llvm/IR/Value.h"
31#include "llvm/InitializePasses.h"
32#include "llvm/Support/Casting.h"
33#include "llvm/Support/CommandLine.h"
34#include "llvm/Support/Compiler.h"
35#include "llvm/Support/Debug.h"
36#include "llvm/Support/ErrorHandling.h"
37#include "llvm/Support/raw_ostream.h"
38#include "isl/ctx.h"
39#include "isl/isl-noexceptions.h"
40#include <cassert>
41#include <memory>
42
43#include "polly/Support/PollyDebug.h"
44#define DEBUG_TYPE "polly-optree"
45
46using namespace llvm;
47using namespace polly;
48
49static cl::opt<bool>
50 AnalyzeKnown("polly-optree-analyze-known",
51 cl::desc("Analyze array contents for load forwarding"),
52 cl::cat(PollyCategory), cl::init(Val: true), cl::Hidden);
53
54static cl::opt<bool>
55 NormalizePHIs("polly-optree-normalize-phi",
56 cl::desc("Replace PHIs by their incoming values"),
57 cl::cat(PollyCategory), cl::init(Val: false), cl::Hidden);
58
59static cl::opt<unsigned>
60 MaxOps("polly-optree-max-ops",
61 cl::desc("Maximum number of ISL operations to invest for known "
62 "analysis; 0=no limit"),
63 cl::init(Val: 1000000), cl::cat(PollyCategory), cl::Hidden);
64
65STATISTIC(KnownAnalyzed, "Number of successfully analyzed SCoPs");
66STATISTIC(KnownOutOfQuota,
67 "Analyses aborted because max_operations was reached");
68
69STATISTIC(TotalInstructionsCopied, "Number of copied instructions");
70STATISTIC(TotalKnownLoadsForwarded,
71 "Number of forwarded loads because their value was known");
72STATISTIC(TotalReloads, "Number of reloaded values");
73STATISTIC(TotalReadOnlyCopied, "Number of copied read-only accesses");
74STATISTIC(TotalForwardedTrees, "Number of forwarded operand trees");
75STATISTIC(TotalModifiedStmts,
76 "Number of statements with at least one forwarded tree");
77
78STATISTIC(ScopsModified, "Number of SCoPs with at least one forwarded tree");
79
80STATISTIC(NumValueWrites, "Number of scalar value writes after OpTree");
81STATISTIC(NumValueWritesInLoops,
82 "Number of scalar value writes nested in affine loops after OpTree");
83STATISTIC(NumPHIWrites, "Number of scalar phi writes after OpTree");
84STATISTIC(NumPHIWritesInLoops,
85 "Number of scalar phi writes nested in affine loops after OpTree");
86STATISTIC(NumSingletonWrites, "Number of singleton writes after OpTree");
87STATISTIC(NumSingletonWritesInLoops,
88 "Number of singleton writes nested in affine loops after OpTree");
89
90namespace {
91
92/// The state of whether an operand tree was/can be forwarded.
93///
94/// The items apply to an instructions and its operand tree with the instruction
95/// as the root element. If the value in question is not an instruction in the
96/// SCoP, it can be a leaf of an instruction's operand tree.
97enum ForwardingDecision {
98 /// An uninitialized value.
99 FD_Unknown,
100
101 /// The root instruction or value cannot be forwarded at all.
102 FD_CannotForward,
103
104 /// The root instruction or value can be forwarded as a leaf of a larger
105 /// operand tree.
106 /// It does not make sense to move the value itself, it would just replace it
107 /// by a use of itself. For instance, a constant "5" used in a statement can
108 /// be forwarded, but it would just replace it by the same constant "5".
109 /// However, it makes sense to move as an operand of
110 ///
111 /// %add = add 5, 5
112 ///
113 /// where "5" is moved as part of a larger operand tree. "5" would be placed
114 /// (disregarding for a moment that literal constants don't have a location
115 /// and can be used anywhere) into the same statement as %add would.
116 FD_CanForwardLeaf,
117
118 /// The root instruction can be forwarded and doing so avoids a scalar
119 /// dependency.
120 ///
121 /// This can be either because the operand tree can be moved to the target
122 /// statement, or a memory access is redirected to read from a different
123 /// location.
124 FD_CanForwardProfitably,
125
126 /// A forwarding method cannot be applied to the operand tree.
127 /// The difference to FD_CannotForward is that there might be other methods
128 /// that can handle it.
129 FD_NotApplicable
130};
131
132/// Represents the evaluation of and action to taken when forwarding a value
133/// from an operand tree.
134struct ForwardingAction {
135 using KeyTy = std::pair<Value *, ScopStmt *>;
136
137 /// Evaluation of forwarding a value.
138 ForwardingDecision Decision = FD_Unknown;
139
140 /// Callback to execute the forwarding.
141 /// Returning true allows deleting the polly::MemoryAccess if the value is the
142 /// root of the operand tree (and its elimination the reason why the
143 /// forwarding is done). Return false if the MemoryAccess is reused or there
144 /// might be other users of the read accesses. In the letter case the
145 /// polly::SimplifyPass can remove dead MemoryAccesses.
146 std::function<bool()> Execute = []() -> bool {
147 llvm_unreachable("unspecified how to forward");
148 };
149
150 /// Other values that need to be forwarded if this action is executed. Their
151 /// actions are executed after this one.
152 SmallVector<KeyTy, 4> Depends;
153
154 /// Named ctor: The method creating this object does not apply to the kind of
155 /// value, but other methods may.
156 static ForwardingAction notApplicable() {
157 ForwardingAction Result;
158 Result.Decision = FD_NotApplicable;
159 return Result;
160 }
161
162 /// Named ctor: The value cannot be forwarded.
163 static ForwardingAction cannotForward() {
164 ForwardingAction Result;
165 Result.Decision = FD_CannotForward;
166 return Result;
167 }
168
169 /// Named ctor: The value can just be used without any preparation.
170 static ForwardingAction triviallyForwardable(bool IsProfitable, Value *Val) {
171 ForwardingAction Result;
172 Result.Decision =
173 IsProfitable ? FD_CanForwardProfitably : FD_CanForwardLeaf;
174 Result.Execute = [=]() {
175 POLLY_DEBUG(dbgs() << " trivially forwarded: " << *Val << "\n");
176 return true;
177 };
178 return Result;
179 }
180
181 /// Name ctor: The value can be forwarded by executing an action.
182 static ForwardingAction canForward(std::function<bool()> Execute,
183 ArrayRef<KeyTy> Depends,
184 bool IsProfitable) {
185 ForwardingAction Result;
186 Result.Decision =
187 IsProfitable ? FD_CanForwardProfitably : FD_CanForwardLeaf;
188 Result.Execute = std::move(Execute);
189 Result.Depends.append(in_start: Depends.begin(), in_end: Depends.end());
190 return Result;
191 }
192};
193
194/// Implementation of operand tree forwarding for a specific SCoP.
195///
196/// For a statement that requires a scalar value (through a value read
197/// MemoryAccess), see if its operand can be moved into the statement. If so,
198/// the MemoryAccess is removed and the all the operand tree instructions are
199/// moved into the statement. All original instructions are left in the source
200/// statements. The simplification pass can clean these up.
201class ForwardOpTreeImpl final : ZoneAlgorithm {
202private:
203 using MemoizationTy = DenseMap<ForwardingAction::KeyTy, ForwardingAction>;
204
205 /// Scope guard to limit the number of isl operations for this pass.
206 IslMaxOperationsGuard &MaxOpGuard;
207
208 /// How many instructions have been copied to other statements.
209 int NumInstructionsCopied = 0;
210
211 /// Number of loads forwarded because their value was known.
212 int NumKnownLoadsForwarded = 0;
213
214 /// Number of values reloaded from known array elements.
215 int NumReloads = 0;
216
217 /// How many read-only accesses have been copied.
218 int NumReadOnlyCopied = 0;
219
220 /// How many operand trees have been forwarded.
221 int NumForwardedTrees = 0;
222
223 /// Number of statements with at least one forwarded operand tree.
224 int NumModifiedStmts = 0;
225
226 /// Whether we carried out at least one change to the SCoP.
227 bool Modified = false;
228
229 /// Cache of how to forward values.
230 /// The key of this map is the llvm::Value to be forwarded and the
231 /// polly::ScopStmt it is forwarded from. This is because the same llvm::Value
232 /// can evaluate differently depending on where it is evaluate. For instance,
233 /// a synthesizable Scev represents a recurrence with an loop but the loop's
234 /// exit value if evaluated after the loop.
235 /// The cached results are only valid for the current TargetStmt.
236 /// CHECKME: ScalarEvolution::getScevAtScope should take care for getting the
237 /// exit value when instantiated outside of the loop. The primary concern is
238 /// ambiguity when crossing PHI nodes, which currently is not supported.
239 MemoizationTy ForwardingActions;
240
241 /// Contains the zones where array elements are known to contain a specific
242 /// value.
243 /// { [Element[] -> Zone[]] -> ValInst[] }
244 /// @see computeKnown()
245 isl::union_map Known;
246
247 /// Translator for newly introduced ValInsts to already existing ValInsts such
248 /// that new introduced load instructions can reuse the Known analysis of its
249 /// original load. { ValInst[] -> ValInst[] }
250 isl::union_map Translator;
251
252 /// Get list of array elements that do contain the same ValInst[] at Domain[].
253 ///
254 /// @param ValInst { Domain[] -> ValInst[] }
255 /// The values for which we search for alternative locations,
256 /// per statement instance.
257 ///
258 /// @return { Domain[] -> Element[] }
259 /// For each statement instance, the array elements that contain the
260 /// same ValInst.
261 isl::union_map findSameContentElements(isl::union_map ValInst) {
262 assert(!ValInst.is_single_valued().is_false());
263
264 // { Domain[] }
265 isl::union_set Domain = ValInst.domain();
266
267 // { Domain[] -> Scatter[] }
268 isl::union_map Schedule = getScatterFor(Domain);
269
270 // { Element[] -> [Scatter[] -> ValInst[]] }
271 isl::union_map MustKnownCurried =
272 convertZoneToTimepoints(Zone: Known, Dim: isl::dim::in, InclStart: false, InclEnd: true).curry();
273
274 // { [Domain[] -> ValInst[]] -> Scatter[] }
275 isl::union_map DomValSched = ValInst.domain_map().apply_range(umap2: Schedule);
276
277 // { [Scatter[] -> ValInst[]] -> [Domain[] -> ValInst[]] }
278 isl::union_map SchedValDomVal =
279 DomValSched.range_product(umap2: ValInst.range_map()).reverse();
280
281 // { Element[] -> [Domain[] -> ValInst[]] }
282 isl::union_map MustKnownInst = MustKnownCurried.apply_range(umap2: SchedValDomVal);
283
284 // { Domain[] -> Element[] }
285 isl::union_map MustKnownMap =
286 MustKnownInst.uncurry().domain().unwrap().reverse();
287 simplify(UMap&: MustKnownMap);
288
289 return MustKnownMap;
290 }
291
292 /// Find a single array element for each statement instance, within a single
293 /// array.
294 ///
295 /// @param MustKnown { Domain[] -> Element[] }
296 /// Set of candidate array elements.
297 /// @param Domain { Domain[] }
298 /// The statement instance for which we need elements for.
299 ///
300 /// @return { Domain[] -> Element[] }
301 /// For each statement instance, an array element out of @p MustKnown.
302 /// All array elements must be in the same array (Polly does not yet
303 /// support reading from different accesses using the same
304 /// MemoryAccess). If no mapping for all of @p Domain exists, returns
305 /// null.
306 isl::map singleLocation(isl::union_map MustKnown, isl::set Domain) {
307 // { Domain[] -> Element[] }
308 isl::map Result;
309
310 // Make irrelevant elements not interfere.
311 Domain = Domain.intersect_params(params: S->getContext());
312
313 // MemoryAccesses can read only elements from a single array
314 // (i.e. not: { Dom[0] -> A[0]; Dom[1] -> B[1] }).
315 // Look through all spaces until we find one that contains at least the
316 // wanted statement instance.s
317 for (isl::map Map : MustKnown.get_map_list()) {
318 // Get the array this is accessing.
319 isl::id ArrayId = Map.get_tuple_id(type: isl::dim::out);
320 ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(ArrayId.get_user());
321
322 // No support for generation of indirect array accesses.
323 if (SAI->getBasePtrOriginSAI())
324 continue;
325
326 // Determine whether this map contains all wanted values.
327 isl::set MapDom = Map.domain();
328 if (!Domain.is_subset(set2: MapDom).is_true())
329 continue;
330
331 // There might be multiple array elements that contain the same value, but
332 // choose only one of them. lexmin is used because it returns a one-value
333 // mapping, we do not care about which one.
334 // TODO: Get the simplest access function.
335 Result = Map.lexmin();
336 break;
337 }
338
339 return Result;
340 }
341
342public:
343 ForwardOpTreeImpl(Scop *S, LoopInfo *LI, IslMaxOperationsGuard &MaxOpGuard)
344 : ZoneAlgorithm("polly-optree", S, LI), MaxOpGuard(MaxOpGuard) {}
345
346 /// Compute the zones of known array element contents.
347 ///
348 /// @return True if the computed #Known is usable.
349 bool computeKnownValues() {
350 isl::union_map MustKnown, KnownFromLoad, KnownFromInit;
351
352 // Check that nothing strange occurs.
353 collectCompatibleElts();
354
355 {
356 IslQuotaScope QuotaScope = MaxOpGuard.enter();
357
358 computeCommon();
359 if (NormalizePHIs)
360 computeNormalizedPHIs();
361 Known = computeKnown(FromWrite: true, FromRead: true);
362
363 // Preexisting ValInsts use the known content analysis of themselves.
364 Translator = makeIdentityMap(USet: Known.range(), RestrictDomain: false);
365 }
366
367 if (Known.is_null() || Translator.is_null() || NormalizeMap.is_null()) {
368 assert(isl_ctx_last_error(IslCtx.get()) == isl_error_quota);
369 Known = {};
370 Translator = {};
371 NormalizeMap = {};
372 POLLY_DEBUG(dbgs() << "Known analysis exceeded max_operations\n");
373 return false;
374 }
375
376 KnownAnalyzed++;
377 POLLY_DEBUG(dbgs() << "All known: " << Known << "\n");
378
379 return true;
380 }
381
382 void printStatistics(raw_ostream &OS, int Indent = 0) {
383 OS.indent(NumSpaces: Indent) << "Statistics {\n";
384 OS.indent(NumSpaces: Indent + 4) << "Instructions copied: " << NumInstructionsCopied
385 << '\n';
386 OS.indent(NumSpaces: Indent + 4) << "Known loads forwarded: " << NumKnownLoadsForwarded
387 << '\n';
388 OS.indent(NumSpaces: Indent + 4) << "Reloads: " << NumReloads << '\n';
389 OS.indent(NumSpaces: Indent + 4) << "Read-only accesses copied: " << NumReadOnlyCopied
390 << '\n';
391 OS.indent(NumSpaces: Indent + 4) << "Operand trees forwarded: " << NumForwardedTrees
392 << '\n';
393 OS.indent(NumSpaces: Indent + 4) << "Statements with forwarded operand trees: "
394 << NumModifiedStmts << '\n';
395 OS.indent(NumSpaces: Indent) << "}\n";
396 }
397
398 void printStatements(raw_ostream &OS, int Indent = 0) const {
399 OS.indent(NumSpaces: Indent) << "After statements {\n";
400 for (auto &Stmt : *S) {
401 OS.indent(NumSpaces: Indent + 4) << Stmt.getBaseName() << "\n";
402 for (auto *MA : Stmt)
403 MA->print(OS);
404
405 OS.indent(NumSpaces: Indent + 12);
406 Stmt.printInstructions(OS);
407 }
408 OS.indent(NumSpaces: Indent) << "}\n";
409 }
410
411 /// Create a new MemoryAccess of type read and MemoryKind::Array.
412 ///
413 /// @param Stmt The statement in which the access occurs.
414 /// @param LI The instruction that does the access.
415 /// @param AccessRelation The array element that each statement instance
416 /// accesses.
417 ///
418 /// @param The newly created access.
419 MemoryAccess *makeReadArrayAccess(ScopStmt *Stmt, LoadInst *LI,
420 isl::map AccessRelation) {
421 isl::id ArrayId = AccessRelation.get_tuple_id(type: isl::dim::out);
422 ScopArrayInfo *SAI = reinterpret_cast<ScopArrayInfo *>(ArrayId.get_user());
423
424 // Create a dummy SCEV access, to be replaced anyway.
425 SmallVector<const SCEV *, 4> Sizes;
426 Sizes.reserve(N: SAI->getNumberOfDimensions());
427 SmallVector<const SCEV *, 4> Subscripts;
428 Subscripts.reserve(N: SAI->getNumberOfDimensions());
429 for (unsigned i = 0; i < SAI->getNumberOfDimensions(); i += 1) {
430 Sizes.push_back(Elt: SAI->getDimensionSize(Dim: i));
431 Subscripts.push_back(Elt: nullptr);
432 }
433
434 MemoryAccess *Access =
435 new MemoryAccess(Stmt, LI, MemoryAccess::READ, SAI->getBasePtr(),
436 LI->getType(), true, {}, Sizes, LI, MemoryKind::Array);
437 S->addAccessFunction(Access);
438 Stmt->addAccess(Access, Prepend: true);
439
440 Access->setNewAccessRelation(AccessRelation);
441
442 return Access;
443 }
444
445 /// Forward a load by reading from an array element that contains the same
446 /// value. Typically the location it was loaded from.
447 ///
448 /// @param TargetStmt The statement the operand tree will be copied to.
449 /// @param Inst The (possibly speculatable) instruction to forward.
450 /// @param UseStmt The statement that uses @p Inst.
451 /// @param UseLoop The loop @p Inst is used in.
452 /// @param DefStmt The statement @p Inst is defined in.
453 /// @param DefLoop The loop which contains @p Inst.
454 ///
455 /// @return A ForwardingAction object describing the feasibility and
456 /// profitability evaluation and the callback carrying-out the value
457 /// forwarding.
458 ForwardingAction forwardKnownLoad(ScopStmt *TargetStmt, Instruction *Inst,
459 ScopStmt *UseStmt, Loop *UseLoop,
460 ScopStmt *DefStmt, Loop *DefLoop) {
461 // Cannot do anything without successful known analysis.
462 if (Known.is_null() || Translator.is_null() ||
463 MaxOpGuard.hasQuotaExceeded())
464 return ForwardingAction::notApplicable();
465
466 LoadInst *LI = dyn_cast<LoadInst>(Val: Inst);
467 if (!LI)
468 return ForwardingAction::notApplicable();
469
470 ForwardingDecision OpDecision =
471 forwardTree(TargetStmt, UseVal: LI->getPointerOperand(), UseStmt: DefStmt, UseLoop: DefLoop);
472 switch (OpDecision) {
473 case FD_CanForwardProfitably:
474 case FD_CanForwardLeaf:
475 break;
476 case FD_CannotForward:
477 return ForwardingAction::cannotForward();
478 default:
479 llvm_unreachable("Shouldn't return this");
480 }
481
482 MemoryAccess *Access = TargetStmt->getArrayAccessOrNULLFor(Inst: LI);
483 if (Access) {
484 // If the load is already in the statement, no forwarding is necessary.
485 // However, it might happen that the LoadInst is already present in the
486 // statement's instruction list. In that case we do as follows:
487 // - For the evaluation, we can trivially forward it as it is
488 // benefit of forwarding an already present instruction.
489 // - For the execution, prepend the instruction (to make it
490 // available to all instructions following in the instruction list), but
491 // do not add another MemoryAccess.
492 auto ExecAction = [this, TargetStmt, LI, Access]() -> bool {
493 TargetStmt->prependInstruction(Inst: LI);
494 POLLY_DEBUG(
495 dbgs() << " forwarded known load with preexisting MemoryAccess"
496 << Access << "\n");
497 (void)Access;
498
499 NumKnownLoadsForwarded++;
500 TotalKnownLoadsForwarded++;
501 return true;
502 };
503 return ForwardingAction::canForward(
504 Execute: ExecAction, Depends: {{LI->getPointerOperand(), DefStmt}}, IsProfitable: true);
505 }
506
507 // Allow the following Isl calculations (until we return the
508 // ForwardingAction, excluding the code inside the lambda that will be
509 // executed later) to fail.
510 IslQuotaScope QuotaScope = MaxOpGuard.enter();
511
512 // { DomainDef[] -> ValInst[] }
513 isl::map ExpectedVal = makeValInst(Val: Inst, UserStmt: UseStmt, Scope: UseLoop);
514 assert(!isNormalized(ExpectedVal).is_false() &&
515 "LoadInsts are always normalized");
516
517 // { DomainUse[] -> DomainTarget[] }
518 isl::map UseToTarget = getDefToTarget(DefStmt: UseStmt, TargetStmt);
519
520 // { DomainTarget[] -> ValInst[] }
521 isl::map TargetExpectedVal = ExpectedVal.apply_domain(map2: UseToTarget);
522 isl::union_map TranslatedExpectedVal =
523 isl::union_map(TargetExpectedVal).apply_range(umap2: Translator);
524
525 // { DomainTarget[] -> Element[] }
526 isl::union_map Candidates = findSameContentElements(ValInst: TranslatedExpectedVal);
527
528 isl::map SameVal = singleLocation(MustKnown: Candidates, Domain: getDomainFor(Stmt: TargetStmt));
529 if (SameVal.is_null())
530 return ForwardingAction::notApplicable();
531
532 POLLY_DEBUG(dbgs() << " expected values where " << TargetExpectedVal
533 << "\n");
534 POLLY_DEBUG(dbgs() << " candidate elements where " << Candidates
535 << "\n");
536
537 // { ValInst[] }
538 isl::space ValInstSpace = ExpectedVal.get_space().range();
539
540 // After adding a new load to the SCoP, also update the Known content
541 // about it. The new load will have a known ValInst of
542 // { [DomainTarget[] -> Value[]] }
543 // but which -- because it is a copy of it -- has same value as the
544 // { [DomainDef[] -> Value[]] }
545 // that it replicates. Instead of cloning the known content of
546 // [DomainDef[] -> Value[]]
547 // for DomainTarget[], we add a 'translator' that maps
548 // [DomainTarget[] -> Value[]] to [DomainDef[] -> Value[]]
549 // before comparing to the known content.
550 // TODO: 'Translator' could also be used to map PHINodes to their incoming
551 // ValInsts.
552 isl::map LocalTranslator;
553 if (!ValInstSpace.is_wrapping().is_false()) {
554 // { DefDomain[] -> Value[] }
555 isl::map ValInsts = ExpectedVal.range().unwrap();
556
557 // { DefDomain[] }
558 isl::set DefDomain = ValInsts.domain();
559
560 // { Value[] }
561 isl::space ValSpace = ValInstSpace.unwrap().range();
562
563 // { Value[] -> Value[] }
564 isl::map ValToVal =
565 isl::map::identity(space: ValSpace.map_from_domain_and_range(range: ValSpace));
566
567 // { DomainDef[] -> DomainTarget[] }
568 isl::map DefToTarget = getDefToTarget(DefStmt, TargetStmt);
569
570 // { [TargetDomain[] -> Value[]] -> [DefDomain[] -> Value] }
571 LocalTranslator = DefToTarget.reverse().product(map2: ValToVal);
572 POLLY_DEBUG(dbgs() << " local translator is " << LocalTranslator
573 << "\n");
574
575 if (LocalTranslator.is_null())
576 return ForwardingAction::notApplicable();
577 }
578
579 auto ExecAction = [this, TargetStmt, LI, SameVal,
580 LocalTranslator]() -> bool {
581 TargetStmt->prependInstruction(Inst: LI);
582 MemoryAccess *Access = makeReadArrayAccess(Stmt: TargetStmt, LI, AccessRelation: SameVal);
583 POLLY_DEBUG(dbgs() << " forwarded known load with new MemoryAccess"
584 << Access << "\n");
585 (void)Access;
586
587 if (!LocalTranslator.is_null())
588 Translator = Translator.unite(umap2: LocalTranslator);
589
590 NumKnownLoadsForwarded++;
591 TotalKnownLoadsForwarded++;
592 return true;
593 };
594 return ForwardingAction::canForward(
595 Execute: ExecAction, Depends: {{LI->getPointerOperand(), DefStmt}}, IsProfitable: true);
596 }
597
598 /// Forward a scalar by redirecting the access to an array element that stores
599 /// the same value.
600 ///
601 /// @param TargetStmt The statement the operand tree will be copied to.
602 /// @param Inst The scalar to forward.
603 /// @param UseStmt The statement that uses @p Inst.
604 /// @param UseLoop The loop @p Inst is used in.
605 /// @param DefStmt The statement @p Inst is defined in.
606 /// @param DefLoop The loop which contains @p Inst.
607 ///
608 /// @return A ForwardingAction object describing the feasibility and
609 /// profitability evaluation and the callback carrying-out the value
610 /// forwarding.
611 ForwardingAction reloadKnownContent(ScopStmt *TargetStmt, Instruction *Inst,
612 ScopStmt *UseStmt, Loop *UseLoop,
613 ScopStmt *DefStmt, Loop *DefLoop) {
614 // Cannot do anything without successful known analysis.
615 if (Known.is_null() || Translator.is_null() ||
616 MaxOpGuard.hasQuotaExceeded())
617 return ForwardingAction::notApplicable();
618
619 // Don't spend too much time analyzing whether it can be reloaded.
620 IslQuotaScope QuotaScope = MaxOpGuard.enter();
621
622 // { DomainDef[] -> ValInst[] }
623 isl::union_map ExpectedVal = makeNormalizedValInst(Val: Inst, UserStmt: UseStmt, Scope: UseLoop);
624
625 // { DomainUse[] -> DomainTarget[] }
626 isl::map UseToTarget = getDefToTarget(DefStmt: UseStmt, TargetStmt);
627
628 // { DomainTarget[] -> ValInst[] }
629 isl::union_map TargetExpectedVal = ExpectedVal.apply_domain(umap2: UseToTarget);
630 isl::union_map TranslatedExpectedVal =
631 TargetExpectedVal.apply_range(umap2: Translator);
632
633 // { DomainTarget[] -> Element[] }
634 isl::union_map Candidates = findSameContentElements(ValInst: TranslatedExpectedVal);
635
636 isl::map SameVal = singleLocation(MustKnown: Candidates, Domain: getDomainFor(Stmt: TargetStmt));
637 simplify(Map&: SameVal);
638 if (SameVal.is_null())
639 return ForwardingAction::notApplicable();
640
641 auto ExecAction = [this, TargetStmt, Inst, SameVal]() {
642 MemoryAccess *Access = TargetStmt->lookupInputAccessOf(Val: Inst);
643 if (!Access)
644 Access = TargetStmt->ensureValueRead(V: Inst);
645 Access->setNewAccessRelation(SameVal);
646
647 POLLY_DEBUG(dbgs() << " forwarded known content of " << *Inst
648 << " which is " << SameVal << "\n");
649 TotalReloads++;
650 NumReloads++;
651 return false;
652 };
653
654 return ForwardingAction::canForward(Execute: ExecAction, Depends: {}, IsProfitable: true);
655 }
656
657 /// Forwards a speculatively executable instruction.
658 ///
659 /// @param TargetStmt The statement the operand tree will be copied to.
660 /// @param UseInst The (possibly speculatable) instruction to forward.
661 /// @param DefStmt The statement @p UseInst is defined in.
662 /// @param DefLoop The loop which contains @p UseInst.
663 ///
664 /// @return A ForwardingAction object describing the feasibility and
665 /// profitability evaluation and the callback carrying-out the value
666 /// forwarding.
667 ForwardingAction forwardSpeculatable(ScopStmt *TargetStmt,
668 Instruction *UseInst, ScopStmt *DefStmt,
669 Loop *DefLoop) {
670 // PHIs, unless synthesizable, are not yet supported.
671 if (isa<PHINode>(Val: UseInst))
672 return ForwardingAction::notApplicable();
673
674 // Compatible instructions must satisfy the following conditions:
675 // 1. Idempotent (instruction will be copied, not moved; although its
676 // original instance might be removed by simplification)
677 // 2. Not access memory (There might be memory writes between)
678 // 3. Not cause undefined behaviour (we might copy to a location when the
679 // original instruction was no executed; this is currently not possible
680 // because we do not forward PHINodes)
681 // 4. Not leak memory if executed multiple times (i.e. malloc)
682 //
683 // Instruction::mayHaveSideEffects is not sufficient because it considers
684 // malloc to not have side-effects. llvm::isSafeToSpeculativelyExecute is
685 // not sufficient because it allows memory accesses.
686 if (mayHaveNonDefUseDependency(I: *UseInst))
687 return ForwardingAction::notApplicable();
688
689 SmallVector<ForwardingAction::KeyTy, 4> Depends;
690 Depends.reserve(N: UseInst->getNumOperands());
691 for (Value *OpVal : UseInst->operand_values()) {
692 ForwardingDecision OpDecision =
693 forwardTree(TargetStmt, UseVal: OpVal, UseStmt: DefStmt, UseLoop: DefLoop);
694 switch (OpDecision) {
695 case FD_CannotForward:
696 return ForwardingAction::cannotForward();
697
698 case FD_CanForwardLeaf:
699 case FD_CanForwardProfitably:
700 Depends.emplace_back(Args&: OpVal, Args&: DefStmt);
701 break;
702
703 case FD_NotApplicable:
704 case FD_Unknown:
705 llvm_unreachable(
706 "forwardTree should never return FD_NotApplicable/FD_Unknown");
707 }
708 }
709
710 auto ExecAction = [this, TargetStmt, UseInst]() {
711 // To ensure the right order, prepend this instruction before its
712 // operands. This ensures that its operands are inserted before the
713 // instruction using them.
714 TargetStmt->prependInstruction(Inst: UseInst);
715
716 POLLY_DEBUG(dbgs() << " forwarded speculable instruction: " << *UseInst
717 << "\n");
718 NumInstructionsCopied++;
719 TotalInstructionsCopied++;
720 return true;
721 };
722 return ForwardingAction::canForward(Execute: ExecAction, Depends, IsProfitable: true);
723 }
724
725 /// Determines whether an operand tree can be forwarded and returns
726 /// instructions how to do so in the form of a ForwardingAction object.
727 ///
728 /// @param TargetStmt The statement the operand tree will be copied to.
729 /// @param UseVal The value (usually an instruction) which is root of an
730 /// operand tree.
731 /// @param UseStmt The statement that uses @p UseVal.
732 /// @param UseLoop The loop @p UseVal is used in.
733 ///
734 /// @return A ForwardingAction object describing the feasibility and
735 /// profitability evaluation and the callback carrying-out the value
736 /// forwarding.
737 ForwardingAction forwardTreeImpl(ScopStmt *TargetStmt, Value *UseVal,
738 ScopStmt *UseStmt, Loop *UseLoop) {
739 ScopStmt *DefStmt = nullptr;
740 Loop *DefLoop = nullptr;
741
742 // { DefDomain[] -> TargetDomain[] }
743 isl::map DefToTarget;
744
745 VirtualUse VUse = VirtualUse::create(UserStmt: UseStmt, UserScope: UseLoop, Val: UseVal, Virtual: true);
746 switch (VUse.getKind()) {
747 case VirtualUse::Constant:
748 case VirtualUse::Block:
749 case VirtualUse::Hoisted:
750 // These can be used anywhere without special considerations.
751 return ForwardingAction::triviallyForwardable(IsProfitable: false, Val: UseVal);
752
753 case VirtualUse::Synthesizable: {
754 // Check if the value is synthesizable at the new location as well. This
755 // might be possible when leaving a loop for which ScalarEvolution is
756 // unable to derive the exit value for.
757 // TODO: If there is a LCSSA PHI at the loop exit, use that one.
758 // If the SCEV contains a SCEVAddRecExpr, we currently depend on that we
759 // do not forward past its loop header. This would require us to use a
760 // previous loop induction variable instead the current one. We currently
761 // do not allow forwarding PHI nodes, thus this should never occur (the
762 // only exception where no phi is necessary being an unreachable loop
763 // without edge from the outside).
764 VirtualUse TargetUse = VirtualUse::create(
765 S, UserStmt: TargetStmt, UserScope: TargetStmt->getSurroundingLoop(), Val: UseVal, Virtual: true);
766 if (TargetUse.getKind() == VirtualUse::Synthesizable)
767 return ForwardingAction::triviallyForwardable(IsProfitable: false, Val: UseVal);
768
769 POLLY_DEBUG(
770 dbgs() << " Synthesizable would not be synthesizable anymore: "
771 << *UseVal << "\n");
772 return ForwardingAction::cannotForward();
773 }
774
775 case VirtualUse::ReadOnly: {
776 if (!ModelReadOnlyScalars)
777 return ForwardingAction::triviallyForwardable(IsProfitable: false, Val: UseVal);
778
779 // If we model read-only scalars, we need to create a MemoryAccess for it.
780 auto ExecAction = [this, TargetStmt, UseVal]() {
781 TargetStmt->ensureValueRead(V: UseVal);
782
783 POLLY_DEBUG(dbgs() << " forwarded read-only value " << *UseVal
784 << "\n");
785 NumReadOnlyCopied++;
786 TotalReadOnlyCopied++;
787
788 // Note that we cannot return true here. With a operand tree
789 // depth of 0, UseVal is the use in TargetStmt that we try to replace.
790 // With -polly-analyze-read-only-scalars=true we would ensure the
791 // existence of a MemoryAccess (which already exists for a leaf) and be
792 // removed again by tryForwardTree because it's goal is to remove this
793 // scalar MemoryAccess. It interprets FD_CanForwardTree as the
794 // permission to do so.
795 return false;
796 };
797 return ForwardingAction::canForward(Execute: ExecAction, Depends: {}, IsProfitable: false);
798 }
799
800 case VirtualUse::Intra:
801 // Knowing that UseStmt and DefStmt are the same statement instance, just
802 // reuse the information about UseStmt for DefStmt
803 DefStmt = UseStmt;
804
805 [[fallthrough]];
806 case VirtualUse::Inter:
807 Instruction *Inst = cast<Instruction>(Val: UseVal);
808
809 if (!DefStmt) {
810 DefStmt = S->getStmtFor(Inst);
811 if (!DefStmt)
812 return ForwardingAction::cannotForward();
813 }
814
815 DefLoop = LI->getLoopFor(BB: Inst->getParent());
816
817 ForwardingAction SpeculativeResult =
818 forwardSpeculatable(TargetStmt, UseInst: Inst, DefStmt, DefLoop);
819 if (SpeculativeResult.Decision != FD_NotApplicable)
820 return SpeculativeResult;
821
822 ForwardingAction KnownResult = forwardKnownLoad(
823 TargetStmt, Inst, UseStmt, UseLoop, DefStmt, DefLoop);
824 if (KnownResult.Decision != FD_NotApplicable)
825 return KnownResult;
826
827 ForwardingAction ReloadResult = reloadKnownContent(
828 TargetStmt, Inst, UseStmt, UseLoop, DefStmt, DefLoop);
829 if (ReloadResult.Decision != FD_NotApplicable)
830 return ReloadResult;
831
832 // When no method is found to forward the operand tree, we effectively
833 // cannot handle it.
834 POLLY_DEBUG(dbgs() << " Cannot forward instruction: " << *Inst
835 << "\n");
836 return ForwardingAction::cannotForward();
837 }
838
839 llvm_unreachable("Case unhandled");
840 }
841
842 /// Determines whether an operand tree can be forwarded. Previous evaluations
843 /// are cached.
844 ///
845 /// @param TargetStmt The statement the operand tree will be copied to.
846 /// @param UseVal The value (usually an instruction) which is root of an
847 /// operand tree.
848 /// @param UseStmt The statement that uses @p UseVal.
849 /// @param UseLoop The loop @p UseVal is used in.
850 ///
851 /// @return FD_CannotForward if @p UseVal cannot be forwarded.
852 /// FD_CanForwardLeaf if @p UseVal is forwardable, but not
853 /// profitable.
854 /// FD_CanForwardProfitably if @p UseVal is forwardable and useful to
855 /// do.
856 ForwardingDecision forwardTree(ScopStmt *TargetStmt, Value *UseVal,
857 ScopStmt *UseStmt, Loop *UseLoop) {
858 // Lookup any cached evaluation.
859 auto It = ForwardingActions.find(Val: {UseVal, UseStmt});
860 if (It != ForwardingActions.end())
861 return It->second.Decision;
862
863 // Make a new evaluation.
864 ForwardingAction Action =
865 forwardTreeImpl(TargetStmt, UseVal, UseStmt, UseLoop);
866 ForwardingDecision Result = Action.Decision;
867
868 // Remember for the next time.
869 assert(!ForwardingActions.count({UseVal, UseStmt}) &&
870 "circular dependency?");
871 ForwardingActions.insert(KV: {{UseVal, UseStmt}, std::move(Action)});
872
873 return Result;
874 }
875
876 /// Forward an operand tree using cached actions.
877 ///
878 /// @param Stmt Statement the operand tree is moved into.
879 /// @param UseVal Root of the operand tree within @p Stmt.
880 /// @param RA The MemoryAccess for @p UseVal that the forwarding intends
881 /// to remove.
882 void applyForwardingActions(ScopStmt *Stmt, Value *UseVal, MemoryAccess *RA) {
883 using ChildItTy =
884 decltype(std::declval<ForwardingAction>().Depends.begin());
885 using EdgeTy = std::pair<ForwardingAction *, ChildItTy>;
886
887 DenseSet<ForwardingAction::KeyTy> Visited;
888 SmallVector<EdgeTy, 32> Stack;
889 SmallVector<ForwardingAction *, 32> Ordered;
890
891 // Seed the tree search using the root value.
892 assert(ForwardingActions.count({UseVal, Stmt}));
893 ForwardingAction *RootAction = &ForwardingActions[{UseVal, Stmt}];
894 Stack.emplace_back(Args&: RootAction, Args: RootAction->Depends.begin());
895
896 // Compute the postorder of the operand tree: all operands of an instruction
897 // must be visited before the instruction itself. As an additional
898 // requirement, the topological ordering must be 'compact': Any subtree node
899 // must not be interleaved with nodes from a non-shared subtree. This is
900 // because the same llvm::Instruction can be materialized multiple times as
901 // used at different ScopStmts which might be different values. Intersecting
902 // these lifetimes may result in miscompilations.
903 // FIXME: Intersecting lifetimes might still be possible for the roots
904 // themselves, since instructions are just prepended to a ScopStmt's
905 // instruction list.
906 while (!Stack.empty()) {
907 EdgeTy &Top = Stack.back();
908 ForwardingAction *TopAction = Top.first;
909 ChildItTy &TopEdge = Top.second;
910
911 if (TopEdge == TopAction->Depends.end()) {
912 // Postorder sorting
913 Ordered.push_back(Elt: TopAction);
914 Stack.pop_back();
915 continue;
916 }
917 ForwardingAction::KeyTy Key = *TopEdge;
918
919 // Next edge for this level
920 ++TopEdge;
921
922 auto VisitIt = Visited.insert(V: Key);
923 if (!VisitIt.second)
924 continue;
925
926 assert(ForwardingActions.count(Key) &&
927 "Must not insert new actions during execution phase");
928 ForwardingAction *ChildAction = &ForwardingActions[Key];
929 Stack.emplace_back(Args&: ChildAction, Args: ChildAction->Depends.begin());
930 }
931
932 // Actually, we need the reverse postorder because actions prepend new
933 // instructions. Therefore, the first one will always be the action for the
934 // operand tree's root.
935 assert(Ordered.back() == RootAction);
936 if (RootAction->Execute())
937 Stmt->removeSingleMemoryAccess(MA: RA);
938 Ordered.pop_back();
939 for (auto DepAction : reverse(C&: Ordered)) {
940 assert(DepAction->Decision != FD_Unknown &&
941 DepAction->Decision != FD_CannotForward);
942 assert(DepAction != RootAction);
943 DepAction->Execute();
944 }
945 }
946
947 /// Try to forward an operand tree rooted in @p RA.
948 bool tryForwardTree(MemoryAccess *RA) {
949 assert(RA->isLatestScalarKind());
950 POLLY_DEBUG(dbgs() << "Trying to forward operand tree " << RA << "...\n");
951
952 ScopStmt *Stmt = RA->getStatement();
953 Loop *InLoop = Stmt->getSurroundingLoop();
954
955 isl::map TargetToUse;
956 if (!Known.is_null()) {
957 isl::space DomSpace = Stmt->getDomainSpace();
958 TargetToUse =
959 isl::map::identity(space: DomSpace.map_from_domain_and_range(range: DomSpace));
960 }
961
962 ForwardingDecision Assessment =
963 forwardTree(TargetStmt: Stmt, UseVal: RA->getAccessValue(), UseStmt: Stmt, UseLoop: InLoop);
964
965 // If considered feasible and profitable, forward it.
966 bool Changed = false;
967 if (Assessment == FD_CanForwardProfitably) {
968 applyForwardingActions(Stmt, UseVal: RA->getAccessValue(), RA);
969 Changed = true;
970 }
971
972 ForwardingActions.clear();
973 return Changed;
974 }
975
976 /// Return which SCoP this instance is processing.
977 Scop *getScop() const { return S; }
978
979 /// Run the algorithm: Use value read accesses as operand tree roots and try
980 /// to forward them into the statement.
981 bool forwardOperandTrees() {
982 for (ScopStmt &Stmt : *S) {
983 bool StmtModified = false;
984
985 // Because we are modifying the MemoryAccess list, collect them first to
986 // avoid iterator invalidation.
987 SmallVector<MemoryAccess *, 16> Accs(Stmt.begin(), Stmt.end());
988
989 for (MemoryAccess *RA : Accs) {
990 if (!RA->isRead())
991 continue;
992 if (!RA->isLatestScalarKind())
993 continue;
994
995 if (tryForwardTree(RA)) {
996 Modified = true;
997 StmtModified = true;
998 NumForwardedTrees++;
999 TotalForwardedTrees++;
1000 }
1001 }
1002
1003 if (StmtModified) {
1004 NumModifiedStmts++;
1005 TotalModifiedStmts++;
1006 }
1007 }
1008
1009 if (Modified) {
1010 ScopsModified++;
1011 S->realignParams();
1012 }
1013 return Modified;
1014 }
1015
1016 /// Print the pass result, performed transformations and the SCoP after the
1017 /// transformation.
1018 void print(raw_ostream &OS, int Indent = 0) {
1019 printStatistics(OS, Indent);
1020
1021 if (!Modified) {
1022 // This line can easily be checked in regression tests.
1023 OS << "ForwardOpTree executed, but did not modify anything\n";
1024 return;
1025 }
1026
1027 printStatements(OS, Indent);
1028 }
1029
1030 bool isModified() const { return Modified; }
1031};
1032
1033static std::unique_ptr<ForwardOpTreeImpl> runForwardOpTree(Scop &S,
1034 LoopInfo &LI) {
1035 std::unique_ptr<ForwardOpTreeImpl> Impl;
1036 {
1037 IslMaxOperationsGuard MaxOpGuard(S.getIslCtx().get(), MaxOps, false);
1038 Impl = std::make_unique<ForwardOpTreeImpl>(args: &S, args: &LI, args&: MaxOpGuard);
1039
1040 if (AnalyzeKnown) {
1041 POLLY_DEBUG(dbgs() << "Prepare forwarders...\n");
1042 Impl->computeKnownValues();
1043 }
1044
1045 POLLY_DEBUG(dbgs() << "Forwarding operand trees...\n");
1046 Impl->forwardOperandTrees();
1047
1048 if (MaxOpGuard.hasQuotaExceeded()) {
1049 POLLY_DEBUG(dbgs() << "Not all operations completed because of "
1050 "max_operations exceeded\n");
1051 KnownOutOfQuota++;
1052 }
1053 }
1054
1055 POLLY_DEBUG(dbgs() << "\nFinal Scop:\n");
1056 POLLY_DEBUG(dbgs() << S);
1057
1058 // Update statistics
1059 Scop::ScopStatistics ScopStats = S.getStatistics();
1060 NumValueWrites += ScopStats.NumValueWrites;
1061 NumValueWritesInLoops += ScopStats.NumValueWritesInLoops;
1062 NumPHIWrites += ScopStats.NumPHIWrites;
1063 NumPHIWritesInLoops += ScopStats.NumPHIWritesInLoops;
1064 NumSingletonWrites += ScopStats.NumSingletonWrites;
1065 NumSingletonWritesInLoops += ScopStats.NumSingletonWritesInLoops;
1066
1067 return Impl;
1068}
1069
1070static PreservedAnalyses
1071runForwardOpTreeUsingNPM(Scop &S, ScopAnalysisManager &SAM,
1072 ScopStandardAnalysisResults &SAR, SPMUpdater &U,
1073 raw_ostream *OS) {
1074 LoopInfo &LI = SAR.LI;
1075
1076 std::unique_ptr<ForwardOpTreeImpl> Impl = runForwardOpTree(S, LI);
1077 if (OS) {
1078 *OS << "Printing analysis 'Polly - Forward operand tree' for region: '"
1079 << S.getName() << "' in function '" << S.getFunction().getName()
1080 << "':\n";
1081 if (Impl) {
1082 assert(Impl->getScop() == &S);
1083
1084 Impl->print(OS&: *OS);
1085 }
1086 }
1087
1088 if (!Impl->isModified())
1089 return PreservedAnalyses::all();
1090
1091 PreservedAnalyses PA;
1092 PA.preserveSet<AllAnalysesOn<Module>>();
1093 PA.preserveSet<AllAnalysesOn<Function>>();
1094 PA.preserveSet<AllAnalysesOn<Loop>>();
1095 return PA;
1096}
1097
1098/// Pass that redirects scalar reads to array elements that are known to contain
1099/// the same value.
1100///
1101/// This reduces the number of scalar accesses and therefore potentially
1102/// increases the freedom of the scheduler. In the ideal case, all reads of a
1103/// scalar definition are redirected (We currently do not care about removing
1104/// the write in this case). This is also useful for the main DeLICM pass as
1105/// there are less scalars to be mapped.
1106class ForwardOpTreeWrapperPass final : public ScopPass {
1107private:
1108 /// The pass implementation, also holding per-scop data.
1109 std::unique_ptr<ForwardOpTreeImpl> Impl;
1110
1111public:
1112 static char ID;
1113
1114 explicit ForwardOpTreeWrapperPass() : ScopPass(ID) {}
1115 ForwardOpTreeWrapperPass(const ForwardOpTreeWrapperPass &) = delete;
1116 ForwardOpTreeWrapperPass &
1117 operator=(const ForwardOpTreeWrapperPass &) = delete;
1118
1119 void getAnalysisUsage(AnalysisUsage &AU) const override {
1120 AU.addRequiredTransitive<ScopInfoRegionPass>();
1121 AU.addRequired<LoopInfoWrapperPass>();
1122 AU.setPreservesAll();
1123 }
1124
1125 bool runOnScop(Scop &S) override {
1126 // Free resources for previous SCoP's computation, if not yet done.
1127 releaseMemory();
1128
1129 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1130
1131 Impl = runForwardOpTree(S, LI);
1132
1133 return false;
1134 }
1135
1136 void printScop(raw_ostream &OS, Scop &S) const override {
1137 if (!Impl)
1138 return;
1139
1140 assert(Impl->getScop() == &S);
1141 Impl->print(OS);
1142 }
1143
1144 void releaseMemory() override { Impl.reset(); }
1145}; // class ForwardOpTree
1146
1147char ForwardOpTreeWrapperPass::ID;
1148
1149/// Print result from ForwardOpTreeWrapperPass.
1150class ForwardOpTreePrinterLegacyPass final : public ScopPass {
1151public:
1152 static char ID;
1153
1154 ForwardOpTreePrinterLegacyPass() : ForwardOpTreePrinterLegacyPass(outs()) {}
1155 explicit ForwardOpTreePrinterLegacyPass(llvm::raw_ostream &OS)
1156 : ScopPass(ID), OS(OS) {}
1157
1158 bool runOnScop(Scop &S) override {
1159 ForwardOpTreeWrapperPass &P = getAnalysis<ForwardOpTreeWrapperPass>();
1160
1161 OS << "Printing analysis '" << P.getPassName() << "' for region: '"
1162 << S.getRegion().getNameStr() << "' in function '"
1163 << S.getFunction().getName() << "':\n";
1164 P.printScop(OS, S);
1165
1166 return false;
1167 }
1168
1169 void getAnalysisUsage(AnalysisUsage &AU) const override {
1170 ScopPass::getAnalysisUsage(AU);
1171 AU.addRequired<ForwardOpTreeWrapperPass>();
1172 AU.setPreservesAll();
1173 }
1174
1175private:
1176 llvm::raw_ostream &OS;
1177};
1178
1179char ForwardOpTreePrinterLegacyPass::ID = 0;
1180} // namespace
1181
1182Pass *polly::createForwardOpTreeWrapperPass() {
1183 return new ForwardOpTreeWrapperPass();
1184}
1185
1186Pass *polly::createForwardOpTreePrinterLegacyPass(llvm::raw_ostream &OS) {
1187 return new ForwardOpTreePrinterLegacyPass(OS);
1188}
1189
1190llvm::PreservedAnalyses ForwardOpTreePass::run(Scop &S,
1191 ScopAnalysisManager &SAM,
1192 ScopStandardAnalysisResults &SAR,
1193 SPMUpdater &U) {
1194 return runForwardOpTreeUsingNPM(S, SAM, SAR, U, OS: nullptr);
1195}
1196
1197llvm::PreservedAnalyses
1198ForwardOpTreePrinterPass::run(Scop &S, ScopAnalysisManager &SAM,
1199 ScopStandardAnalysisResults &SAR, SPMUpdater &U) {
1200 return runForwardOpTreeUsingNPM(S, SAM, SAR, U, OS: &OS);
1201}
1202
1203INITIALIZE_PASS_BEGIN(ForwardOpTreeWrapperPass, "polly-optree",
1204 "Polly - Forward operand tree", false, false)
1205INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
1206INITIALIZE_PASS_END(ForwardOpTreeWrapperPass, "polly-optree",
1207 "Polly - Forward operand tree", false, false)
1208
1209INITIALIZE_PASS_BEGIN(ForwardOpTreePrinterLegacyPass, "polly-print-optree",
1210 "Polly - Print forward operand tree result", false, false)
1211INITIALIZE_PASS_DEPENDENCY(ForwardOpTreeWrapperPass)
1212INITIALIZE_PASS_END(ForwardOpTreePrinterLegacyPass, "polly-print-optree",
1213 "Polly - Print forward operand tree result", false, false)
1214

source code of polly/lib/Transform/ForwardOpTree.cpp