CIRCT  19.0.0git
SchedulingAnalysis.cpp
Go to the documentation of this file.
1 //===- SchedulingAnalysis.cpp - scheduling analyses -----------------------===//
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 //
9 // This file implements methods that perform analysis involving scheduling.
10 //
11 //===----------------------------------------------------------------------===//
12 
16 #include "mlir/Dialect/Affine/IR/AffineOps.h"
17 #include "mlir/Dialect/Affine/LoopUtils.h"
18 #include "mlir/Dialect/Func/IR/FuncOps.h"
19 #include "mlir/Dialect/MemRef/IR/MemRef.h"
20 #include "mlir/Dialect/SCF/IR/SCF.h"
21 #include "mlir/IR/BuiltinOps.h"
22 #include "mlir/Pass/AnalysisManager.h"
23 #include <limits>
24 
25 using namespace mlir;
26 using namespace mlir::affine;
27 
28 /// CyclicSchedulingAnalysis constructs a CyclicProblem for each AffineForOp by
29 /// performing a memory dependence analysis and inserting dependences into the
30 /// problem. The client should retrieve the partially complete problem to add
31 /// and associate operator types.
33  Operation *op, AnalysisManager &am) {
34  auto funcOp = cast<func::FuncOp>(op);
35 
36  MemoryDependenceAnalysis &memoryAnalysis =
37  am.getAnalysis<MemoryDependenceAnalysis>();
38 
39  // Only consider innermost loops of perfectly nested AffineForOps.
40  for (auto root : funcOp.getOps<AffineForOp>()) {
41  SmallVector<AffineForOp> nestedLoops;
42  getPerfectlyNestedLoops(nestedLoops, root);
43  analyzeForOp(nestedLoops.back(), memoryAnalysis);
44  }
45 }
46 
48  AffineForOp forOp, MemoryDependenceAnalysis memoryAnalysis) {
49  // Create a cyclic scheduling problem.
50  CyclicProblem problem = CyclicProblem::get(forOp);
51 
52  // Insert memory dependences into the problem.
53  forOp.getBody()->walk([&](Operation *op) {
54  // Insert every operation into the problem.
55  problem.insertOperation(op);
56 
57  ArrayRef<MemoryDependence> dependences = memoryAnalysis.getDependences(op);
58  if (dependences.empty())
59  return;
60 
61  for (MemoryDependence memoryDep : dependences) {
62  // Don't insert a dependence into the problem if there is no dependence.
63  if (!hasDependence(memoryDep.dependenceType))
64  continue;
65 
66  // Insert a dependence into the problem.
67  Problem::Dependence dep(memoryDep.source, op);
68  auto depInserted = problem.insertDependence(dep);
69  assert(succeeded(depInserted));
70  (void)depInserted;
71 
72  // Use the lower bound of the innermost loop for this dependence. This
73  // assumes outer loops execute sequentially, i.e. one iteration of the
74  // inner loop completes before the next iteration is initiated. With
75  // proper analysis and lowerings, this can be relaxed.
76  unsigned distance = *memoryDep.dependenceComponents.back().lb;
77  if (distance > 0)
78  problem.setDistance(dep, distance);
79  }
80  });
81 
82  // Insert conditional dependences into the problem.
83  forOp.getBody()->walk([&](Operation *op) {
84  Block *thenBlock = nullptr;
85  Block *elseBlock = nullptr;
86  if (auto ifOp = dyn_cast<scf::IfOp>(op)) {
87  thenBlock = ifOp.thenBlock();
88  elseBlock = ifOp.elseBlock();
89  } else if (auto ifOp = dyn_cast<AffineIfOp>(op)) {
90  thenBlock = ifOp.getThenBlock();
91  if (ifOp.hasElse())
92  elseBlock = ifOp.getElseBlock();
93  } else {
94  return WalkResult::advance();
95  }
96 
97  // No special handling required for control-only `if`s.
98  if (op->getNumResults() == 0)
99  return WalkResult::skip();
100 
101  // Model the implicit value flow from the `yield` to the `if`'s result(s).
102  Problem::Dependence depThen(thenBlock->getTerminator(), op);
103  auto depInserted = problem.insertDependence(depThen);
104  assert(succeeded(depInserted));
105  (void)depInserted;
106 
107  if (elseBlock) {
108  Problem::Dependence depElse(elseBlock->getTerminator(), op);
109  depInserted = problem.insertDependence(depElse);
110  assert(succeeded(depInserted));
111  (void)depInserted;
112  }
113 
114  return WalkResult::advance();
115  });
116 
117  // Set the anchor for scheduling. Insert dependences from all stores to the
118  // terminator to ensure the problem schedules them before the terminator.
119  auto *anchor = forOp.getBody()->getTerminator();
120  forOp.getBody()->walk([&](Operation *op) {
121  if (!isa<AffineStoreOp, memref::StoreOp>(op))
122  return;
123  Problem::Dependence dep(op, anchor);
124  auto depInserted = problem.insertDependence(dep);
125  assert(succeeded(depInserted));
126  (void)depInserted;
127  });
128 
129  // Handle explicitly computed loop-carried values, i.e. excluding the
130  // induction variable. Insert inter-iteration dependences from the definers of
131  // "iter_args" to their users.
132  if (unsigned nIterArgs = anchor->getNumOperands(); nIterArgs > 0) {
133  auto iterArgs = forOp.getRegionIterArgs();
134  for (unsigned i = 0; i < nIterArgs; ++i) {
135  Operation *iterArgDefiner = anchor->getOperand(i).getDefiningOp();
136  // If it's not an operation, we don't need to model the dependence.
137  if (!iterArgDefiner)
138  continue;
139 
140  for (Operation *iterArgUser : iterArgs[i].getUsers()) {
141  Problem::Dependence dep(iterArgDefiner, iterArgUser);
142  auto depInserted = problem.insertDependence(dep);
143  assert(succeeded(depInserted));
144  (void)depInserted;
145 
146  // Values always flow between subsequent iterations.
147  problem.setDistance(dep, 1);
148  }
149  }
150  }
151 
152  // Store the partially complete problem.
153  problems.insert(std::pair<Operation *, CyclicProblem>(forOp, problem));
154 }
155 
158  auto problem = problems.find(forOp);
159  assert(problem != problems.end() && "expected problem to exist");
160  return problem->second;
161 }
assert(baseType &&"element must be base type")
This class models a cyclic scheduling problem.
Definition: Problems.h:292
void setDistance(Dependence dep, unsigned val)
Definition: Problems.h:305
void insertOperation(Operation *op)
Include op in this scheduling problem.
Definition: Problems.h:152
LogicalResult insertDependence(Dependence dep)
Include dep in the scheduling problem.
Definition: Problems.cpp:26
A wrapper class to uniformly handle def-use and auxiliary dependence edges.
Direction get(bool isOutput)
Returns an output direction if isOutput is true, otherwise returns an input direction.
Definition: CalyxOps.cpp:53
CyclicProblem & getProblem(affine::AffineForOp forOp)
CyclicSchedulingAnalysis(Operation *funcOp, AnalysisManager &am)
CyclicSchedulingAnalysis constructs a CyclicProblem for each AffineForOp by performing a memory depen...
void analyzeForOp(affine::AffineForOp forOp, MemoryDependenceAnalysis memoryAnalysis)
MemoryDependenceAnalysis traverses any AffineForOps in the FuncOp body and checks for affine memory a...
ArrayRef< MemoryDependence > getDependences(Operation *)
Returns the dependences, if any, that the given Operation depends on.
MemoryDependence captures a dependence from one memory operation to another.