1//===- ScheduleOrderedAssignments.cpp -- Ordered Assignment Scheduling ----===//
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#include "ScheduleOrderedAssignments.h"
10#include "flang/Optimizer/Analysis/AliasAnalysis.h"
11#include "flang/Optimizer/Builder/FIRBuilder.h"
12#include "flang/Optimizer/Builder/Todo.h"
13#include "flang/Optimizer/Dialect/Support/FIRContext.h"
14#include "llvm/ADT/SmallSet.h"
15#include "llvm/Support/Debug.h"
16
17#define DEBUG_TYPE "flang-ordered-assignment"
18
19//===----------------------------------------------------------------------===//
20// Scheduling logging utilities for debug and test
21//===----------------------------------------------------------------------===//
22
23/// Log RAW or WAW conflict.
24static void LLVM_ATTRIBUTE_UNUSED logConflict(llvm::raw_ostream &os,
25 mlir::Value writtenOrReadVarA,
26 mlir::Value writtenVarB);
27/// Log when an expression evaluation must be saved.
28static void LLVM_ATTRIBUTE_UNUSED logSaveEvaluation(llvm::raw_ostream &os,
29 unsigned runid,
30 mlir::Region &yieldRegion,
31 bool anyWrite);
32/// Log when an assignment is scheduled.
33static void LLVM_ATTRIBUTE_UNUSED logAssignmentEvaluation(
34 llvm::raw_ostream &os, unsigned runid, hlfir::RegionAssignOp assign);
35/// Log when starting to schedule an order assignment tree.
36static void LLVM_ATTRIBUTE_UNUSED logStartScheduling(
37 llvm::raw_ostream &os, hlfir::OrderedAssignmentTreeOpInterface root);
38/// Log op if effect value is not known.
39static void LLVM_ATTRIBUTE_UNUSED logIfUnkownEffectValue(
40 llvm::raw_ostream &os, mlir::MemoryEffects::EffectInstance effect,
41 mlir::Operation &op);
42
43//===----------------------------------------------------------------------===//
44// Scheduling Implementation
45//===----------------------------------------------------------------------===//
46
47namespace {
48/// Structure that is in charge of building the schedule. For each
49/// hlfir.region_assign inside an ordered assignment tree, it is walked through
50/// the parent operations and their "leaf" regions (that contain expression
51/// evaluations). The Scheduler analyze the memory effects of these regions
52/// against the effect of the current assignment, and if any conflict is found,
53/// it will create an action to save the value computed by the region before the
54/// assignment evaluation.
55class Scheduler {
56public:
57 Scheduler(bool tryFusingAssignments)
58 : tryFusingAssignments{tryFusingAssignments} {}
59
60 /// Start scheduling an assignment. Gather the write side effect from the
61 /// assignment.
62 void startSchedulingAssignment(hlfir::RegionAssignOp assign,
63 bool leafRegionsMayOnlyRead);
64
65 /// Start analysing a set of evaluation regions that can be evaluated in
66 /// any order between themselves according to Fortran rules (like the controls
67 /// of forall). The point of this is to avoid adding the side effects of
68 /// independent evaluations to a run that would save only one of the control.
69 void startIndependentEvaluationGroup() {
70 assert(independentEvaluationEffects.empty() &&
71 "previous group was not finished");
72 };
73
74 /// Analyze the memory effects of a region containing an expression
75 /// evaluation. If any conflict is found with the current assignment, or if
76 /// the expression has write effects (which is possible outside of forall),
77 /// create an action in the schedule to save the value in the schedule before
78 /// evaluating the current assignment. For expression with write effect,
79 /// saving them ensures they are evaluated only once. A region whose value
80 /// was saved in a previous run is considered to have no side effects with the
81 /// current assignment: the saved value will be used.
82 void saveEvaluationIfConflict(mlir::Region &yieldRegion,
83 bool leafRegionsMayOnlyRead,
84 bool yieldIsImplicitRead = true,
85 bool evaluationsMayConflict = false);
86
87 /// Finish evaluating a group of independent regions. The current independent
88 /// regions effects are added to the "parent" effect list since evaluating the
89 /// next analyzed region would require evaluating the current independent
90 /// regions.
91 void finishIndependentEvaluationGroup() {
92 parentEvaluationEffects.append(independentEvaluationEffects.begin(),
93 independentEvaluationEffects.end());
94 independentEvaluationEffects.clear();
95 }
96
97 /// After all the dependent evaluation regions have been analyzed, create the
98 /// action to evaluate the assignment that was being analyzed.
99 void finishSchedulingAssignment(hlfir::RegionAssignOp assign);
100
101 /// Once all the assignments have been analyzed and scheduled, return the
102 /// schedule. The scheduler object should not be used after this call.
103 hlfir::Schedule moveSchedule() { return std::move(schedule); }
104
105private:
106 /// Save a conflicting region that is evaluating an expression that is
107 /// controlling or masking the current assignment, or is evaluating the
108 /// RHS/LHS.
109 void
110 saveEvaluation(mlir::Region &yieldRegion,
111 llvm::ArrayRef<mlir::MemoryEffects::EffectInstance> effects,
112 bool anyWrite);
113
114 /// Can the current assignment be schedule with the previous run. This is
115 /// only possible if the assignment and all of its dependencies have no side
116 /// effects conflicting with the previous run.
117 bool canFuseAssignmentWithPreviousRun();
118
119 /// Memory effects of the assignments being lowered.
120 llvm::SmallVector<mlir::MemoryEffects::EffectInstance> assignEffects;
121 /// Memory effects of the evaluations implied by the assignments
122 /// being lowered. They do not include the implicit writes
123 /// to the LHS of the assignments.
124 llvm::SmallVector<mlir::MemoryEffects::EffectInstance> assignEvaluateEffects;
125 /// Memory effects of the unsaved evaluation region that are controlling or
126 /// masking the current assignments.
127 llvm::SmallVector<mlir::MemoryEffects::EffectInstance>
128 parentEvaluationEffects;
129 /// Same as parentEvaluationEffects, but for the current "leaf group" being
130 /// analyzed scheduled.
131 llvm::SmallVector<mlir::MemoryEffects::EffectInstance>
132 independentEvaluationEffects;
133
134 /// Were any region saved for the current assignment?
135 bool savedAnyRegionForCurrentAssignment = false;
136
137 // Schedule being built.
138 hlfir::Schedule schedule;
139 /// Leaf regions that have been saved so far.
140 llvm::SmallSet<mlir::Region *, 16> savedRegions;
141 /// Is schedule.back() a schedule that is only saving region with read
142 /// effects?
143 bool currentRunIsReadOnly = false;
144
145 /// Option to tell if the scheduler should try fusing to assignments in the
146 /// same loops.
147 const bool tryFusingAssignments;
148};
149} // namespace
150
151//===----------------------------------------------------------------------===//
152// Scheduling Implementation : gathering memory effects of nodes.
153//===----------------------------------------------------------------------===//
154
155/// Is \p var the result of a ForallIndexOp?
156/// Read effects to forall index can be ignored since forall
157/// indices cannot be assigned to.
158static bool isForallIndex(mlir::Value var) {
159 return var &&
160 mlir::isa_and_nonnull<hlfir::ForallIndexOp>(var.getDefiningOp());
161}
162
163/// Gather the memory effects of the operations contained in a region.
164/// \p mayOnlyRead can be given to exclude some potential write effects that
165/// cannot affect the current scheduling problem because it is known that the
166/// regions are evaluating pure expressions from a Fortran point of view. It is
167/// useful because low level IR in the region may contain operation that lacks
168/// side effect interface, or that are writing temporary variables that may be
169/// hard to identify as such (one would have to prove the write is "local" to
170/// the region even when the alloca may be outside of the region).
171static void gatherMemoryEffects(
172 mlir::Region &region, bool mayOnlyRead,
173 llvm::SmallVectorImpl<mlir::MemoryEffects::EffectInstance> &effects) {
174 /// This analysis is a simple walk of all the operations of the region that is
175 /// evaluating and yielding a value. This is a lot simpler and safer than
176 /// trying to walk back the SSA DAG from the yielded value. But if desired,
177 /// this could be changed.
178 for (mlir::Operation &op : region.getOps()) {
179 if (op.hasTrait<mlir::OpTrait::HasRecursiveMemoryEffects>()) {
180 for (mlir::Region &subRegion : op.getRegions())
181 gatherMemoryEffects(subRegion, mayOnlyRead, effects);
182 // In MLIR, RecursiveMemoryEffects can be combined with
183 // MemoryEffectOpInterface to describe extra effects on top of the
184 // effects of the nested operations. However, the presence of
185 // RecursiveMemoryEffects and the absence of MemoryEffectOpInterface
186 // implies the operation has no other memory effects than the one of its
187 // nested operations.
188 if (!mlir::isa<mlir::MemoryEffectOpInterface>(op))
189 continue;
190 }
191 mlir::MemoryEffectOpInterface interface =
192 mlir::dyn_cast<mlir::MemoryEffectOpInterface>(op);
193 if (!interface) {
194 LLVM_DEBUG(llvm::dbgs() << "unknown effect: " << op << "\n";);
195 // There is no generic way to know what this operation is reading/writing
196 // to. Assume the worst. No need to continue analyzing the code any
197 // further.
198 effects.emplace_back(mlir::MemoryEffects::Read::get());
199 if (!mayOnlyRead)
200 effects.emplace_back(mlir::MemoryEffects::Write::get());
201 return;
202 }
203 // Collect read/write effects. Alloc/Free effects do not matter, they
204 // are either local to the evaluation region and can be repeated, or, if
205 // they are allocatable/pointer allocation/deallocation, they are conveyed
206 // via the write that is updating the descriptor/allocatable (and there
207 // cannot be any indirect allocatable/pointer allocation/deallocation if
208 // mayOnlyRead is set). When mayOnlyRead is set, local write effects are
209 // also ignored.
210 llvm::SmallVector<mlir::MemoryEffects::EffectInstance> opEffects;
211 interface.getEffects(opEffects);
212 for (auto &effect : opEffects)
213 if (!isForallIndex(effect.getValue())) {
214 if (mlir::isa<mlir::MemoryEffects::Read>(effect.getEffect())) {
215 LLVM_DEBUG(logIfUnkownEffectValue(llvm::dbgs(), effect, op););
216 effects.push_back(effect);
217 } else if (!mayOnlyRead &&
218 mlir::isa<mlir::MemoryEffects::Write>(effect.getEffect())) {
219 LLVM_DEBUG(logIfUnkownEffectValue(llvm::dbgs(), effect, op););
220 effects.push_back(effect);
221 }
222 }
223 }
224}
225
226/// Return the entity yielded by a region, or a null value if the region
227/// is not terminated by a yield.
228static mlir::OpOperand *getYieldedEntity(mlir::Region &region) {
229 if (region.empty() || region.back().empty())
230 return nullptr;
231 if (auto yield = mlir::dyn_cast<hlfir::YieldOp>(region.back().back()))
232 return &yield.getEntityMutable();
233 if (auto elementalAddr =
234 mlir::dyn_cast<hlfir::ElementalAddrOp>(region.back().back()))
235 return &elementalAddr.getYieldOp().getEntityMutable();
236 return nullptr;
237}
238
239/// Gather the effect of an assignment. This is the implicit write to the LHS
240/// of an assignment. This also includes the effects of the user defined
241/// assignment, if any, but this does not include the effects of evaluating the
242/// RHS and LHS, which occur before the assignment effects in Fortran.
243static void gatherAssignEffects(
244 hlfir::RegionAssignOp regionAssign,
245 bool userDefAssignmentMayOnlyWriteToAssignedVariable,
246 llvm::SmallVectorImpl<mlir::MemoryEffects::EffectInstance> &assignEffects) {
247 mlir::OpOperand *assignedVar = getYieldedEntity(regionAssign.getLhsRegion());
248 assert(assignedVar && "lhs cannot be an empty region");
249 assignEffects.emplace_back(mlir::MemoryEffects::Write::get(), assignedVar);
250
251 if (!regionAssign.getUserDefinedAssignment().empty()) {
252 // The write effect on the INTENT(OUT) LHS argument is already taken
253 // into account above.
254 // This side effects are "defensive" and could be improved.
255 // On top of the passed RHS argument, user defined assignments (even when
256 // pure) may also read host/used/common variable. Impure user defined
257 // assignments may write to host/used/common variables not passed via
258 // arguments. For now, simply assume the worst. Once fir.call side effects
259 // analysis is improved, it would best to let the call side effects be used
260 // directly.
261 if (userDefAssignmentMayOnlyWriteToAssignedVariable)
262 assignEffects.emplace_back(mlir::MemoryEffects::Read::get());
263 else
264 assignEffects.emplace_back(mlir::MemoryEffects::Write::get());
265 }
266}
267
268/// Gather the effects of evaluations implied by the given assignment.
269/// These are the effects of operations from LHS and RHS.
270static void gatherAssignEvaluationEffects(
271 hlfir::RegionAssignOp regionAssign,
272 bool userDefAssignmentMayOnlyWriteToAssignedVariable,
273 llvm::SmallVectorImpl<mlir::MemoryEffects::EffectInstance> &assignEffects) {
274 gatherMemoryEffects(regionAssign.getLhsRegion(),
275 userDefAssignmentMayOnlyWriteToAssignedVariable,
276 assignEffects);
277 gatherMemoryEffects(regionAssign.getRhsRegion(),
278 userDefAssignmentMayOnlyWriteToAssignedVariable,
279 assignEffects);
280}
281
282//===----------------------------------------------------------------------===//
283// Scheduling Implementation : finding conflicting memory effects.
284//===----------------------------------------------------------------------===//
285
286/// Follow addressing and declare like operation to the storage source.
287/// This allows using FIR alias analysis that otherwise does not know
288/// about those operations. This is correct, but ignoring the designate
289/// and declare info may yield false positive regarding aliasing (e.g,
290/// if it could be proved that the variable are different sub-part of
291/// an array).
292static mlir::Value getStorageSource(mlir::Value var) {
293 // TODO: define some kind of View interface for Fortran in FIR,
294 // and use it in the FIR alias analysis.
295 mlir::Value source = var;
296 while (auto *op = source.getDefiningOp()) {
297 if (auto designate = mlir::dyn_cast<hlfir::DesignateOp>(op)) {
298 source = designate.getMemref();
299 } else if (auto declare = mlir::dyn_cast<hlfir::DeclareOp>(op)) {
300 source = declare.getMemref();
301 } else {
302 break;
303 }
304 }
305 return source;
306}
307
308/// Could there be any read or write in effectsA on a variable written to in
309/// effectsB?
310static bool
311anyRAWorWAW(llvm::ArrayRef<mlir::MemoryEffects::EffectInstance> effectsA,
312 llvm::ArrayRef<mlir::MemoryEffects::EffectInstance> effectsB,
313 fir::AliasAnalysis &aliasAnalysis) {
314 for (const auto &effectB : effectsB)
315 if (mlir::isa<mlir::MemoryEffects::Write>(effectB.getEffect())) {
316 mlir::Value writtenVarB = effectB.getValue();
317 if (writtenVarB)
318 writtenVarB = getStorageSource(writtenVarB);
319 for (const auto &effectA : effectsA)
320 if (mlir::isa<mlir::MemoryEffects::Write, mlir::MemoryEffects::Read>(
321 effectA.getEffect())) {
322 mlir::Value writtenOrReadVarA = effectA.getValue();
323 if (!writtenVarB || !writtenOrReadVarA) {
324 LLVM_DEBUG(
325 logConflict(llvm::dbgs(), writtenOrReadVarA, writtenVarB););
326 return true; // unknown conflict.
327 }
328 writtenOrReadVarA = getStorageSource(writtenOrReadVarA);
329 if (!aliasAnalysis.alias(writtenOrReadVarA, writtenVarB).isNo()) {
330 LLVM_DEBUG(
331 logConflict(llvm::dbgs(), writtenOrReadVarA, writtenVarB););
332 return true;
333 }
334 }
335 }
336 return false;
337}
338
339/// Could there be any read or write in effectsA on a variable written to in
340/// effectsB, or any read in effectsB on a variable written to in effectsA?
341static bool
342conflict(llvm::ArrayRef<mlir::MemoryEffects::EffectInstance> effectsA,
343 llvm::ArrayRef<mlir::MemoryEffects::EffectInstance> effectsB) {
344 fir::AliasAnalysis aliasAnalysis;
345 // (RAW || WAW) || (WAR || WAW).
346 return anyRAWorWAW(effectsA, effectsB, aliasAnalysis) ||
347 anyRAWorWAW(effectsB, effectsA, aliasAnalysis);
348}
349
350/// Could there be any write effects in "effects" affecting memory storages
351/// that are not local to the current region.
352static bool
353anyNonLocalWrite(llvm::ArrayRef<mlir::MemoryEffects::EffectInstance> effects,
354 mlir::Region &region) {
355 return llvm::any_of(
356 effects, [&region](const mlir::MemoryEffects::EffectInstance &effect) {
357 if (mlir::isa<mlir::MemoryEffects::Write>(effect.getEffect())) {
358 if (mlir::Value v = effect.getValue()) {
359 v = getStorageSource(v);
360 if (v.getDefiningOp<fir::AllocaOp>() ||
361 v.getDefiningOp<fir::AllocMemOp>())
362 return !region.isAncestor(v.getParentRegion());
363 }
364 return true;
365 }
366 return false;
367 });
368}
369
370//===----------------------------------------------------------------------===//
371// Scheduling Implementation : Scheduler class implementation
372//===----------------------------------------------------------------------===//
373
374void Scheduler::startSchedulingAssignment(hlfir::RegionAssignOp assign,
375 bool leafRegionsMayOnlyRead) {
376 gatherAssignEffects(assign, leafRegionsMayOnlyRead, assignEffects);
377 // Unconditionally collect effects of the evaluations of LHS and RHS
378 // in case they need to be analyzed for any parent that might be
379 // affected by conflicts of these evaluations.
380 // This collection might be skipped, if there are no such parents,
381 // but for the time being we run it always.
382 gatherAssignEvaluationEffects(assign, leafRegionsMayOnlyRead,
383 assignEvaluateEffects);
384}
385
386void Scheduler::saveEvaluationIfConflict(mlir::Region &yieldRegion,
387 bool leafRegionsMayOnlyRead,
388 bool yieldIsImplicitRead,
389 bool evaluationsMayConflict) {
390 // If the region evaluation was previously executed and saved, the saved
391 // value will be used when evaluating the current assignment and this has
392 // no effects in the current assignment evaluation.
393 if (savedRegions.contains(&yieldRegion))
394 return;
395 llvm::SmallVector<mlir::MemoryEffects::EffectInstance> effects;
396 gatherMemoryEffects(yieldRegion, leafRegionsMayOnlyRead, effects);
397 // Yield has no effect as such, but in the context of order assignments.
398 // The order assignments will usually read the yielded entity (except for
399 // the yielded assignments LHS that is only read if this is an assignment
400 // with a finalizer, or a user defined assignment where the LHS is
401 // intent(inout)).
402 if (yieldIsImplicitRead) {
403 mlir::OpOperand *entity = getYieldedEntity(yieldRegion);
404 if (entity && hlfir::isFortranVariableType(entity->get().getType()))
405 effects.emplace_back(mlir::MemoryEffects::Read::get(), entity);
406 }
407 if (!leafRegionsMayOnlyRead && anyNonLocalWrite(effects, yieldRegion)) {
408 // Region with write effect must be executed only once (unless all writes
409 // affect storages allocated inside the region): save it the first time it
410 // is encountered.
411 LLVM_DEBUG(llvm::dbgs()
412 << "saving eval because write effect prevents re-evaluation"
413 << "\n";);
414 saveEvaluation(yieldRegion, effects, /*anyWrite=*/true);
415 } else if (conflict(effects, assignEffects)) {
416 // Region that conflicts with the current assignments must be fully
417 // evaluated and saved before doing the assignment (Note that it may
418 // have already have been evaluated without saving it before, but this
419 // implies that it never conflicted with a prior assignment, so its value
420 // should be the same.)
421 saveEvaluation(yieldRegion, effects, /*anyWrite=*/false);
422 } else if (evaluationsMayConflict &&
423 conflict(effects, assignEvaluateEffects)) {
424 // If evaluations of the assignment may conflict with the yield
425 // evaluations, we have to save yield evaluation.
426 // For example, a WHERE mask might be written by the masked assignment
427 // evaluations, and it has to be saved in this case:
428 // where (mask) r = f() ! function f modifies mask
429 saveEvaluation(yieldRegion, effects,
430 anyNonLocalWrite(effects, yieldRegion));
431 } else {
432 // Can be executed while doing the assignment.
433 independentEvaluationEffects.append(effects.begin(), effects.end());
434 }
435}
436
437void Scheduler::saveEvaluation(
438 mlir::Region &yieldRegion,
439 llvm::ArrayRef<mlir::MemoryEffects::EffectInstance> effects,
440 bool anyWrite) {
441 savedAnyRegionForCurrentAssignment = true;
442 if (anyWrite) {
443 // Create a new run just for regions with side effect. Further analysis
444 // could try to prove the effects do not conflict with the previous
445 // schedule.
446 schedule.emplace_back(hlfir::Run{});
447 currentRunIsReadOnly = false;
448 } else if (!currentRunIsReadOnly) {
449 // For now, do not try to fuse an evaluation with a previous
450 // run that contains any write effects. One could try to prove
451 // that "effects" do not conflict with the current run assignments.
452 schedule.emplace_back(hlfir::Run{});
453 currentRunIsReadOnly = true;
454 }
455 // Otherwise, save the yielded entity in the current run, that already
456 // saving other read only entities.
457 schedule.back().actions.emplace_back(hlfir::SaveEntity{&yieldRegion});
458 // The run to save the yielded entity will need to evaluate all the unsaved
459 // parent control or masks. Note that these effects may already be in the
460 // current run memoryEffects, but it is just easier always add them, even if
461 // this may add them again.
462 schedule.back().memoryEffects.append(parentEvaluationEffects.begin(),
463 parentEvaluationEffects.end());
464 schedule.back().memoryEffects.append(effects.begin(), effects.end());
465 savedRegions.insert(&yieldRegion);
466 LLVM_DEBUG(
467 logSaveEvaluation(llvm::dbgs(), schedule.size(), yieldRegion, anyWrite););
468}
469
470bool Scheduler::canFuseAssignmentWithPreviousRun() {
471 // If a region was saved for the current assignment, the previous
472 // run is already known to conflict. Skip the analysis.
473 if (savedAnyRegionForCurrentAssignment || schedule.empty())
474 return false;
475 auto &previousRunEffects = schedule.back().memoryEffects;
476 return !conflict(previousRunEffects, assignEffects) &&
477 !conflict(previousRunEffects, parentEvaluationEffects) &&
478 !conflict(previousRunEffects, independentEvaluationEffects);
479}
480
481void Scheduler::finishSchedulingAssignment(hlfir::RegionAssignOp assign) {
482 // For now, always schedule each assignment in its own run. They could
483 // be done as part of previous assignment runs if it is proven they have
484 // no conflicting effects.
485 currentRunIsReadOnly = false;
486 if (!tryFusingAssignments || !canFuseAssignmentWithPreviousRun())
487 schedule.emplace_back(hlfir::Run{});
488 schedule.back().actions.emplace_back(assign);
489 // TODO: when fusing, it would probably be best to filter the
490 // parentEvaluationEffects that already in the previous run effects (since
491 // assignments may share the same parents), otherwise, this can make the
492 // conflict() calls more and more expensive.
493 schedule.back().memoryEffects.append(parentEvaluationEffects.begin(),
494 parentEvaluationEffects.end());
495 schedule.back().memoryEffects.append(assignEffects.begin(),
496 assignEffects.end());
497 assignEffects.clear();
498 assignEvaluateEffects.clear();
499 parentEvaluationEffects.clear();
500 independentEvaluationEffects.clear();
501 savedAnyRegionForCurrentAssignment = false;
502 LLVM_DEBUG(logAssignmentEvaluation(llvm::dbgs(), schedule.size(), assign));
503}
504
505//===----------------------------------------------------------------------===//
506// Scheduling Implementation : driving the Scheduler in the assignment tree.
507//===----------------------------------------------------------------------===//
508
509/// Gather the hlfir.region_assign nested directly and indirectly inside root in
510/// execution order.
511static void
512gatherAssignments(hlfir::OrderedAssignmentTreeOpInterface root,
513 llvm::SmallVector<hlfir::RegionAssignOp> &assignments) {
514 llvm::SmallVector<mlir::Operation *> nodeStack{root.getOperation()};
515 while (!nodeStack.empty()) {
516 mlir::Operation *node = nodeStack.pop_back_val();
517 if (auto regionAssign = mlir::dyn_cast<hlfir::RegionAssignOp>(node)) {
518 assignments.push_back(regionAssign);
519 continue;
520 }
521 auto nodeIface =
522 mlir::dyn_cast<hlfir::OrderedAssignmentTreeOpInterface>(node);
523 if (nodeIface)
524 if (mlir::Block *block = nodeIface.getSubTreeBlock())
525 for (mlir::Operation &op : llvm::reverse(block->getOperations()))
526 nodeStack.push_back(&op);
527 }
528}
529
530/// Gather the parents of (not included) \p node in reverse execution order.
531static void gatherParents(
532 hlfir::OrderedAssignmentTreeOpInterface node,
533 llvm::SmallVectorImpl<hlfir::OrderedAssignmentTreeOpInterface> &parents) {
534 while (node) {
535 auto parent =
536 mlir::dyn_cast_or_null<hlfir::OrderedAssignmentTreeOpInterface>(
537 node->getParentOp());
538 if (parent && parent.getSubTreeRegion() == node->getParentRegion()) {
539 parents.push_back(parent);
540 node = parent;
541 } else {
542 break;
543 }
544 }
545}
546
547// Build the list of the parent nodes for this assignment. The list is built
548// from the closest parent until the ordered assignment tree root (this is the
549// revere of their execution order).
550static void gatherAssignmentParents(
551 hlfir::RegionAssignOp assign,
552 llvm::SmallVectorImpl<hlfir::OrderedAssignmentTreeOpInterface> &parents) {
553 gatherParents(mlir::cast<hlfir::OrderedAssignmentTreeOpInterface>(
554 assign.getOperation()),
555 parents);
556}
557
558hlfir::Schedule
559hlfir::buildEvaluationSchedule(hlfir::OrderedAssignmentTreeOpInterface root,
560 bool tryFusingAssignments) {
561 LLVM_DEBUG(logStartScheduling(llvm::dbgs(), root););
562 // The expressions inside an hlfir.forall must be pure (with the Fortran
563 // definition of pure). This is not a commitment that there are no operation
564 // with write effect in the regions: entities local to the region may still
565 // be written to (e.g., a temporary accumulator implementing SUM). This is
566 // a commitment that no write effect will affect the scheduling problem, and
567 // that all write effect caught by MLIR analysis can be ignored for the
568 // current problem.
569 const bool leafRegionsMayOnlyRead =
570 mlir::isa<hlfir::ForallOp>(root.getOperation());
571
572 // Loop through the assignments and schedule them.
573 Scheduler scheduler(tryFusingAssignments);
574 llvm::SmallVector<hlfir::RegionAssignOp> assignments;
575 gatherAssignments(root, assignments);
576 for (hlfir::RegionAssignOp assign : assignments) {
577 scheduler.startSchedulingAssignment(assign, leafRegionsMayOnlyRead);
578 // Go through the list of parents (not including the current
579 // hlfir.region_assign) in Fortran execution order so that any parent leaf
580 // region that must be saved is saved in order.
581 llvm::SmallVector<hlfir::OrderedAssignmentTreeOpInterface> parents;
582 gatherAssignmentParents(assign, parents);
583 for (hlfir::OrderedAssignmentTreeOpInterface parent :
584 llvm::reverse(parents)) {
585 scheduler.startIndependentEvaluationGroup();
586 llvm::SmallVector<mlir::Region *, 4> yieldRegions;
587 parent.getLeafRegions(yieldRegions);
588 // TODO: is this really limited to WHERE/ELSEWHERE?
589 bool evaluationsMayConflict = mlir::isa<hlfir::WhereOp>(parent) ||
590 mlir::isa<hlfir::ElseWhereOp>(parent);
591 for (mlir::Region *yieldRegion : yieldRegions)
592 scheduler.saveEvaluationIfConflict(*yieldRegion, leafRegionsMayOnlyRead,
593 /*yieldIsImplicitRead=*/true,
594 evaluationsMayConflict);
595 scheduler.finishIndependentEvaluationGroup();
596 }
597 // Look for conflicts between the RHS/LHS evaluation and the assignments.
598 // The LHS yield has no implicit read effect on the produced variable (the
599 // variable is not read before the assignment).
600 // During pointer assignments, the RHS data is not read, only the address
601 // is taken.
602 scheduler.startIndependentEvaluationGroup();
603 scheduler.saveEvaluationIfConflict(
604 assign.getRhsRegion(), leafRegionsMayOnlyRead,
605 /*yieldIsImplicitRead=*/!assign.isPointerAssignment());
606 // There is no point to save the LHS outside of Forall and assignment to a
607 // vector subscripted LHS because the LHS is already fully evaluated and
608 // saved in the resulting SSA address value (that may be a descriptor or
609 // descriptor address).
610 if (mlir::isa<hlfir::ForallOp>(root.getOperation()) ||
611 mlir::isa<hlfir::ElementalAddrOp>(assign.getLhsRegion().back().back()))
612 scheduler.saveEvaluationIfConflict(assign.getLhsRegion(),
613 leafRegionsMayOnlyRead,
614 /*yieldIsImplicitRead=*/false);
615 scheduler.finishIndependentEvaluationGroup();
616 scheduler.finishSchedulingAssignment(assign);
617 }
618 return scheduler.moveSchedule();
619}
620
621mlir::Value hlfir::SaveEntity::getSavedValue() {
622 mlir::OpOperand *saved = getYieldedEntity(*yieldRegion);
623 assert(saved && "SaveEntity must contain region terminated by YieldOp");
624 return saved->get();
625}
626
627//===----------------------------------------------------------------------===//
628// Debug and test logging implementation
629//===----------------------------------------------------------------------===//
630
631static llvm::raw_ostream &printRegionId(llvm::raw_ostream &os,
632 mlir::Region &yieldRegion) {
633 mlir::Operation *parent = yieldRegion.getParentOp();
634 if (auto forall = mlir::dyn_cast<hlfir::ForallOp>(parent)) {
635 if (&forall.getLbRegion() == &yieldRegion)
636 os << "lb";
637 else if (&forall.getUbRegion() == &yieldRegion)
638 os << "ub";
639 else if (&forall.getStepRegion() == &yieldRegion)
640 os << "step";
641 } else if (auto assign = mlir::dyn_cast<hlfir::ForallMaskOp>(parent)) {
642 if (&assign.getMaskRegion() == &yieldRegion)
643 os << "mask";
644 } else if (auto assign = mlir::dyn_cast<hlfir::RegionAssignOp>(parent)) {
645 if (&assign.getRhsRegion() == &yieldRegion)
646 os << "rhs";
647 else if (&assign.getLhsRegion() == &yieldRegion)
648 os << "lhs";
649 } else if (auto where = mlir::dyn_cast<hlfir::WhereOp>(parent)) {
650 if (&where.getMaskRegion() == &yieldRegion)
651 os << "mask";
652 } else if (auto elseWhereOp = mlir::dyn_cast<hlfir::ElseWhereOp>(parent)) {
653 if (&elseWhereOp.getMaskRegion() == &yieldRegion)
654 os << "mask";
655 } else {
656 os << "unknown";
657 }
658 return os;
659}
660
661static llvm::raw_ostream &
662printNodeIndexInBody(llvm::raw_ostream &os,
663 hlfir::OrderedAssignmentTreeOpInterface node,
664 hlfir::OrderedAssignmentTreeOpInterface parent) {
665 if (!parent || !parent.getSubTreeRegion())
666 return os;
667 mlir::Operation *nodeOp = node.getOperation();
668 unsigned index = 1;
669 for (mlir::Operation &op : parent.getSubTreeRegion()->getOps())
670 if (nodeOp == &op) {
671 return os << index;
672 } else if (nodeOp->getName() == op.getName()) {
673 ++index;
674 }
675 return os;
676}
677
678static llvm::raw_ostream &printNodePath(llvm::raw_ostream &os,
679 mlir::Operation *op) {
680 auto node =
681 mlir::dyn_cast_or_null<hlfir::OrderedAssignmentTreeOpInterface>(op);
682 if (!node) {
683 os << "unknown node";
684 return os;
685 }
686 llvm::SmallVector<hlfir::OrderedAssignmentTreeOpInterface> parents;
687 gatherParents(node, parents);
688 hlfir::OrderedAssignmentTreeOpInterface previousParent;
689 for (auto parent : llvm::reverse(parents)) {
690 os << parent->getName().stripDialect();
691 printNodeIndexInBody(os, parent, previousParent) << "/";
692 previousParent = parent;
693 }
694 os << node->getName().stripDialect();
695 return printNodeIndexInBody(os, node, previousParent);
696}
697
698static llvm::raw_ostream &printRegionPath(llvm::raw_ostream &os,
699 mlir::Region &yieldRegion) {
700 printNodePath(os, yieldRegion.getParentOp()) << "/";
701 return printRegionId(os, yieldRegion);
702}
703
704static void LLVM_ATTRIBUTE_UNUSED logSaveEvaluation(llvm::raw_ostream &os,
705 unsigned runid,
706 mlir::Region &yieldRegion,
707 bool anyWrite) {
708 os << "run " << runid << " save " << (anyWrite ? "(w)" : " ") << ": ";
709 printRegionPath(os, yieldRegion) << "\n";
710}
711
712static void LLVM_ATTRIBUTE_UNUSED logAssignmentEvaluation(
713 llvm::raw_ostream &os, unsigned runid, hlfir::RegionAssignOp assign) {
714 os << "run " << runid << " evaluate: ";
715 printNodePath(os, assign.getOperation()) << "\n";
716}
717
718static void LLVM_ATTRIBUTE_UNUSED logConflict(llvm::raw_ostream &os,
719 mlir::Value writtenOrReadVarA,
720 mlir::Value writtenVarB) {
721 auto printIfValue = [&](mlir::Value var) -> llvm::raw_ostream & {
722 if (!var)
723 return os << "<unknown>";
724 return os << var;
725 };
726 os << "conflict: R/W: ";
727 printIfValue(writtenOrReadVarA) << " W:";
728 printIfValue(writtenVarB) << "\n";
729}
730
731static void LLVM_ATTRIBUTE_UNUSED logStartScheduling(
732 llvm::raw_ostream &os, hlfir::OrderedAssignmentTreeOpInterface root) {
733 os << "------------ scheduling ";
734 printNodePath(os, root.getOperation());
735 if (auto funcOp = root->getParentOfType<mlir::func::FuncOp>())
736 os << " in " << funcOp.getSymName() << " ";
737 os << "------------\n";
738}
739
740static void LLVM_ATTRIBUTE_UNUSED logIfUnkownEffectValue(
741 llvm::raw_ostream &os, mlir::MemoryEffects::EffectInstance effect,
742 mlir::Operation &op) {
743 if (effect.getValue() != nullptr)
744 return;
745 os << "unknown effected value (";
746 os << (mlir::isa<mlir::MemoryEffects::Read>(effect.getEffect()) ? "R" : "W");
747 os << "): " << op << "\n";
748}
749

source code of flang/lib/Optimizer/HLFIR/Transforms/ScheduleOrderedAssignments.cpp