xref: /llvm-project/flang/lib/Optimizer/HLFIR/Transforms/ScheduleOrderedAssignments.h (revision 4f30a63ca2a6cbc16beaa49df16373d020118e92)
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