97 lines · c
1//===- ScheduleOrderedAssignments.h --- Assignment scheduling ---*- 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-exception6//7//===----------------------------------------------------------------------===//8// This file defines a utility to analyze and schedule the evaluation of9// of hlfir::OrderedAssignmentTreeOpInterface trees that represent Fortran10// Forall, Where, user defined assignments and assignments to vector11// subscripted entities.12//===----------------------------------------------------------------------===//13 14#ifndef OPTIMIZER_HLFIR_TRANSFORM_SCHEDULEORDEREDASSIGNMENTS_H15#define OPTIMIZER_HLFIR_TRANSFORM_SCHEDULEORDEREDASSIGNMENTS_H16 17#include "flang/Optimizer/HLFIR/HLFIROps.h"18 19namespace hlfir {20 21/// Structure to represent that the value yielded by some region22/// must be fully evaluated and saved for all index values at23/// a given point of the ordered assignment tree evaluation.24/// All subsequent evaluation depending on the value yielded25/// by this region will use the value that was saved.26struct SaveEntity {27 mlir::Region *yieldRegion;28 /// Returns the hlfir.yield op argument.29 mlir::Value getSavedValue();30};31 32/// A run is a list of actions required to evaluate an ordered assignment tree33/// that can be done in the same loop nest.34/// The actions can evaluate and saves element values into temporary or evaluate35/// assignments.36/// The evaluation of an action in a run will cause the evaluation of all the37/// regions that yield entities required to implement the action, except if the38/// region was saved in a previous run, in which case it will use the previously39/// saved value.40struct Run {41 /// An action is either saving the values yielded by a region, or evaluating42 /// the assignment part of an hlfir::RegionAssignOp.43 using Action = std::variant<hlfir::RegionAssignOp, SaveEntity>;44 llvm::SmallVector<Action> actions;45 llvm::SmallVector<mlir::MemoryEffects::EffectInstance> memoryEffects;46};47 48/// List of runs to be executed in order to evaluate an order assignment tree.49using Schedule = llvm::SmallVector<Run>;50 51/// Example of schedules and run, and what they mean:52/// Fortran: forall (i=i:10) x(i) = y(i)53///54/// hlfir.forall lb { hlfir.yield %c1} ub { hlfir.yield %c10} do {55/// ^bb1(%i: index)56/// hlfir.region_assign {57/// %yi_addr = hlfir.designate %y(%i)58/// %yi = fir.load %yi_addr59/// hlfir.yield %yi60/// } to {61/// %xi = hlfir.designate %x(%i)62/// hlfir.yield %xi63/// }64/// }65///66/// If the scheduling analysis cannot prove that %x and %y do not overlap, it67/// will generate 2 runs for the schdule. The first containing68/// SaveEntity{rhs_region}, and the second one containing the69/// hlfir.region_assign.70///71/// The lowering of that schedule will have to:72/// For the first run:73/// 1. create a temporary to contain all the %yi for all %i74/// 2. create a loop nest for the forall, evaluate the %yi and save them75/// inside the loop, but do not evaluate the LHS or assignment.76/// For the second run:77/// 3. create a loop nest again for the forall, evaluate the LHS, get the78/// saved %yi, and evaluate %yi to %xi. After all runs:79/// 4. clean the temporary for the %yi.80///81/// If the scheduling analysis can prove %x and %y do not overlap, it will82/// generate only one run with the hlfir.region_assign, which will be83/// implemented as a single loop that evaluate %xi, %yi and does %xi = %yi in84/// the loop body.85 86/// Core function that analyzes an ordered assignment tree and builds a87/// schedule for its evaluation.88/// The main goal of the scheduler is to avoid creating temporary storage89/// (required for SaveEntity). But it can optionally be asked to fuse Forall90/// and Where assignments in the same loop nests when possible since it has the91/// memory effects analysis at hand.92Schedule buildEvaluationSchedule(hlfir::OrderedAssignmentTreeOpInterface root,93 bool tryFusingAssignments);94 95} // namespace hlfir96#endif // OPTIMIZER_HLFIR_TRANSFORM_SCHEDULEORDERASSIGNMENTS_H97