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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // This file defines a utility to analyze and schedule the evaluation of 9 // of hlfir::OrderedAssignmentTreeOpInterface trees that represent Fortran 10 // Forall, Where, user defined assignments and assignments to vector 11 // subscripted entities. 12 //===----------------------------------------------------------------------===// 13 14 #ifndef OPTIMIZER_HLFIR_TRANSFORM_SCHEDULEORDEREDASSIGNMENTS_H 15 #define OPTIMIZER_HLFIR_TRANSFORM_SCHEDULEORDEREDASSIGNMENTS_H 16 17 #include "flang/Optimizer/HLFIR/HLFIROps.h" 18 19 namespace hlfir { 20 21 /// Structure to represent that the value yielded by some region 22 /// must be fully evaluated and saved for all index values at 23 /// a given point of the ordered assignment tree evaluation. 24 /// All subsequent evaluation depending on the value yielded 25 /// by this region will use the value that was saved. 26 struct 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 tree 33 /// that can be done in the same loop nest. 34 /// The actions can evaluate and saves element values into temporary or evaluate 35 /// assignments. 36 /// The evaluation of an action in a run will cause the evaluation of all the 37 /// regions that yield entities required to implement the action, except if the 38 /// region was saved in a previous run, in which case it will use the previously 39 /// saved value. 40 struct Run { 41 /// An action is either saving the values yielded by a region, or evaluating 42 /// 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. 49 using 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_addr 59 /// hlfir.yield %yi 60 /// } to { 61 /// %xi = hlfir.designate %x(%i) 62 /// hlfir.yield %xi 63 /// } 64 /// } 65 /// 66 /// If the scheduling analysis cannot prove that %x and %y do not overlap, it 67 /// will generate 2 runs for the schdule. The first containing 68 /// SaveEntity{rhs_region}, and the second one containing the 69 /// 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 %i 74 /// 2. create a loop nest for the forall, evaluate the %yi and save them 75 /// 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 the 78 /// 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 will 82 /// generate only one run with the hlfir.region_assign, which will be 83 /// implemented as a single loop that evaluate %xi, %yi and does %xi = %yi in 84 /// the loop body. 85 86 /// Core function that analyzes an ordered assignment tree and builds a 87 /// schedule for its evaluation. 88 /// The main goal of the scheduler is to avoid creating temporary storage 89 /// (required for SaveEntity). But it can optionally be asked to fuse Forall 90 /// and Where assignments in the same loop nests when possible since it has the 91 /// memory effects analysis at hand. 92 Schedule buildEvaluationSchedule(hlfir::OrderedAssignmentTreeOpInterface root, 93 bool tryFusingAssignments); 94 95 } // namespace hlfir 96 #endif // OPTIMIZER_HLFIR_TRANSFORM_SCHEDULEORDERASSIGNMENTS_H 97