1*4f30a63cSJean Perier //===- ScheduleOrderedAssignments.h --- Assignment scheduling ---*- C++ -*-===// 2*4f30a63cSJean Perier // 3*4f30a63cSJean Perier // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4*4f30a63cSJean Perier // See https://llvm.org/LICENSE.txt for license information. 5*4f30a63cSJean Perier // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6*4f30a63cSJean Perier // 7*4f30a63cSJean Perier //===----------------------------------------------------------------------===// 8*4f30a63cSJean Perier // This file defines a utility to analyze and schedule the evaluation of 9*4f30a63cSJean Perier // of hlfir::OrderedAssignmentTreeOpInterface trees that represent Fortran 10*4f30a63cSJean Perier // Forall, Where, user defined assignments and assignments to vector 11*4f30a63cSJean Perier // subscripted entities. 12*4f30a63cSJean Perier //===----------------------------------------------------------------------===// 13*4f30a63cSJean Perier 14*4f30a63cSJean Perier #ifndef OPTIMIZER_HLFIR_TRANSFORM_SCHEDULEORDEREDASSIGNMENTS_H 15*4f30a63cSJean Perier #define OPTIMIZER_HLFIR_TRANSFORM_SCHEDULEORDEREDASSIGNMENTS_H 16*4f30a63cSJean Perier 17*4f30a63cSJean Perier #include "flang/Optimizer/HLFIR/HLFIROps.h" 18*4f30a63cSJean Perier 19*4f30a63cSJean Perier namespace hlfir { 20*4f30a63cSJean Perier 21*4f30a63cSJean Perier /// Structure to represent that the value yielded by some region 22*4f30a63cSJean Perier /// must be fully evaluated and saved for all index values at 23*4f30a63cSJean Perier /// a given point of the ordered assignment tree evaluation. 24*4f30a63cSJean Perier /// All subsequent evaluation depending on the value yielded 25*4f30a63cSJean Perier /// by this region will use the value that was saved. 26*4f30a63cSJean Perier struct SaveEntity { 27*4f30a63cSJean Perier mlir::Region *yieldRegion; 28*4f30a63cSJean Perier /// Returns the hlfir.yield op argument. 29*4f30a63cSJean Perier mlir::Value getSavedValue(); 30*4f30a63cSJean Perier }; 31*4f30a63cSJean Perier 32*4f30a63cSJean Perier /// A run is a list of actions required to evaluate an ordered assignment tree 33*4f30a63cSJean Perier /// that can be done in the same loop nest. 34*4f30a63cSJean Perier /// The actions can evaluate and saves element values into temporary or evaluate 35*4f30a63cSJean Perier /// assignments. 36*4f30a63cSJean Perier /// The evaluation of an action in a run will cause the evaluation of all the 37*4f30a63cSJean Perier /// regions that yield entities required to implement the action, except if the 38*4f30a63cSJean Perier /// region was saved in a previous run, in which case it will use the previously 39*4f30a63cSJean Perier /// saved value. 40*4f30a63cSJean Perier struct Run { 41*4f30a63cSJean Perier /// An action is either saving the values yielded by a region, or evaluating 42*4f30a63cSJean Perier /// the assignment part of an hlfir::RegionAssignOp. 43*4f30a63cSJean Perier using Action = std::variant<hlfir::RegionAssignOp, SaveEntity>; 44*4f30a63cSJean Perier llvm::SmallVector<Action> actions; 45*4f30a63cSJean Perier llvm::SmallVector<mlir::MemoryEffects::EffectInstance> memoryEffects; 46*4f30a63cSJean Perier }; 47*4f30a63cSJean Perier 48*4f30a63cSJean Perier /// List of runs to be executed in order to evaluate an order assignment tree. 49*4f30a63cSJean Perier using Schedule = llvm::SmallVector<Run>; 50*4f30a63cSJean Perier 51*4f30a63cSJean Perier /// Example of schedules and run, and what they mean: 52*4f30a63cSJean Perier /// Fortran: forall (i=i:10) x(i) = y(i) 53*4f30a63cSJean Perier /// 54*4f30a63cSJean Perier /// hlfir.forall lb { hlfir.yield %c1} ub { hlfir.yield %c10} do { 55*4f30a63cSJean Perier /// ^bb1(%i: index) 56*4f30a63cSJean Perier /// hlfir.region_assign { 57*4f30a63cSJean Perier /// %yi_addr = hlfir.designate %y(%i) 58*4f30a63cSJean Perier /// %yi = fir.load %yi_addr 59*4f30a63cSJean Perier /// hlfir.yield %yi 60*4f30a63cSJean Perier /// } to { 61*4f30a63cSJean Perier /// %xi = hlfir.designate %x(%i) 62*4f30a63cSJean Perier /// hlfir.yield %xi 63*4f30a63cSJean Perier /// } 64*4f30a63cSJean Perier /// } 65*4f30a63cSJean Perier /// 66*4f30a63cSJean Perier /// If the scheduling analysis cannot prove that %x and %y do not overlap, it 67*4f30a63cSJean Perier /// will generate 2 runs for the schdule. The first containing 68*4f30a63cSJean Perier /// SaveEntity{rhs_region}, and the second one containing the 69*4f30a63cSJean Perier /// hlfir.region_assign. 70*4f30a63cSJean Perier /// 71*4f30a63cSJean Perier /// The lowering of that schedule will have to: 72*4f30a63cSJean Perier /// For the first run: 73*4f30a63cSJean Perier /// 1. create a temporary to contain all the %yi for all %i 74*4f30a63cSJean Perier /// 2. create a loop nest for the forall, evaluate the %yi and save them 75*4f30a63cSJean Perier /// inside the loop, but do not evaluate the LHS or assignment. 76*4f30a63cSJean Perier /// For the second run: 77*4f30a63cSJean Perier /// 3. create a loop nest again for the forall, evaluate the LHS, get the 78*4f30a63cSJean Perier /// saved %yi, and evaluate %yi to %xi. After all runs: 79*4f30a63cSJean Perier /// 4. clean the temporary for the %yi. 80*4f30a63cSJean Perier /// 81*4f30a63cSJean Perier /// If the scheduling analysis can prove %x and %y do not overlap, it will 82*4f30a63cSJean Perier /// generate only one run with the hlfir.region_assign, which will be 83*4f30a63cSJean Perier /// implemented as a single loop that evaluate %xi, %yi and does %xi = %yi in 84*4f30a63cSJean Perier /// the loop body. 85*4f30a63cSJean Perier 86*4f30a63cSJean Perier /// Core function that analyzes an ordered assignment tree and builds a 87*4f30a63cSJean Perier /// schedule for its evaluation. 88*4f30a63cSJean Perier /// The main goal of the scheduler is to avoid creating temporary storage 89*4f30a63cSJean Perier /// (required for SaveEntity). But it can optionally be asked to fuse Forall 90*4f30a63cSJean Perier /// and Where assignments in the same loop nests when possible since it has the 91*4f30a63cSJean Perier /// memory effects analysis at hand. 92*4f30a63cSJean Perier Schedule buildEvaluationSchedule(hlfir::OrderedAssignmentTreeOpInterface root, 93*4f30a63cSJean Perier bool tryFusingAssignments); 94*4f30a63cSJean Perier 95*4f30a63cSJean Perier } // namespace hlfir 96*4f30a63cSJean Perier #endif // OPTIMIZER_HLFIR_TRANSFORM_SCHEDULEORDERASSIGNMENTS_H 97