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