1//===- Utils.cpp ---- Misc utilities for analysis -------------------------===//
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 miscellaneous analysis routines for non-loop IR
10// structures.
11//
12//===----------------------------------------------------------------------===//
13
14#include "mlir/Dialect/Affine/Analysis/Utils.h"
15
16#include "mlir/Analysis/Presburger/PresburgerRelation.h"
17#include "mlir/Dialect/Affine/Analysis/AffineAnalysis.h"
18#include "mlir/Dialect/Affine/Analysis/LoopAnalysis.h"
19#include "mlir/Dialect/Affine/IR/AffineOps.h"
20#include "mlir/Dialect/Affine/IR/AffineValueMap.h"
21#include "mlir/Dialect/MemRef/IR/MemRef.h"
22#include "mlir/Dialect/Utils/StaticValueUtils.h"
23#include "mlir/IR/IntegerSet.h"
24#include "llvm/ADT/SetVector.h"
25#include "llvm/ADT/SmallVectorExtras.h"
26#include "llvm/Support/Debug.h"
27#include "llvm/Support/DebugLog.h"
28#include "llvm/Support/raw_ostream.h"
29#include <optional>
30
31#define DEBUG_TYPE "analysis-utils"
32
33using namespace mlir;
34using namespace affine;
35using namespace presburger;
36
37using llvm::SmallDenseMap;
38
39using Node = MemRefDependenceGraph::Node;
40
41// LoopNestStateCollector walks loop nests and collects load and store
42// operations, and whether or not a region holding op other than ForOp and IfOp
43// was encountered in the loop nest.
44void LoopNestStateCollector::collect(Operation *opToWalk) {
45 opToWalk->walk(callback: [&](Operation *op) {
46 if (auto forOp = dyn_cast<AffineForOp>(Val: op)) {
47 forOps.push_back(Elt: forOp);
48 } else if (isa<AffineReadOpInterface>(Val: op)) {
49 loadOpInsts.push_back(Elt: op);
50 } else if (isa<AffineWriteOpInterface>(Val: op)) {
51 storeOpInsts.push_back(Elt: op);
52 } else {
53 auto memInterface = dyn_cast<MemoryEffectOpInterface>(Val: op);
54 if (!memInterface) {
55 if (op->hasTrait<OpTrait::HasRecursiveMemoryEffects>())
56 // This op itself is memory-effect free.
57 return;
58 // Check operands. Eg. ops like the `call` op are handled here.
59 for (Value v : op->getOperands()) {
60 if (!isa<MemRefType>(Val: v.getType()))
61 continue;
62 // Conservatively, we assume the memref is read and written to.
63 memrefLoads.push_back(Elt: op);
64 memrefStores.push_back(Elt: op);
65 }
66 } else {
67 // Non-affine loads and stores.
68 if (hasEffect<MemoryEffects::Read>(op))
69 memrefLoads.push_back(Elt: op);
70 if (hasEffect<MemoryEffects::Write>(op))
71 memrefStores.push_back(Elt: op);
72 if (hasEffect<MemoryEffects::Free>(op))
73 memrefFrees.push_back(Elt: op);
74 }
75 }
76 });
77}
78
79unsigned Node::getLoadOpCount(Value memref) const {
80 unsigned loadOpCount = 0;
81 for (Operation *loadOp : loads) {
82 // Common case: affine reads.
83 if (auto affineLoad = dyn_cast<AffineReadOpInterface>(Val: loadOp)) {
84 if (memref == affineLoad.getMemRef())
85 ++loadOpCount;
86 } else if (hasEffect<MemoryEffects::Read>(op: loadOp, value: memref)) {
87 ++loadOpCount;
88 }
89 }
90 return loadOpCount;
91}
92
93// Returns the store op count for 'memref'.
94unsigned Node::getStoreOpCount(Value memref) const {
95 unsigned storeOpCount = 0;
96 for (auto *storeOp : llvm::concat<Operation *const>(Ranges: stores, Ranges: memrefStores)) {
97 // Common case: affine writes.
98 if (auto affineStore = dyn_cast<AffineWriteOpInterface>(Val: storeOp)) {
99 if (memref == affineStore.getMemRef())
100 ++storeOpCount;
101 } else if (hasEffect<MemoryEffects::Write>(op: const_cast<Operation *>(storeOp),
102 value: memref)) {
103 ++storeOpCount;
104 }
105 }
106 return storeOpCount;
107}
108
109// Returns the store op count for 'memref'.
110unsigned Node::hasStore(Value memref) const {
111 return llvm::any_of(
112 Range: llvm::concat<Operation *const>(Ranges: stores, Ranges: memrefStores),
113 P: [&](Operation *storeOp) {
114 if (auto affineStore = dyn_cast<AffineWriteOpInterface>(Val: storeOp)) {
115 if (memref == affineStore.getMemRef())
116 return true;
117 } else if (hasEffect<MemoryEffects::Write>(op: storeOp, value: memref)) {
118 return true;
119 }
120 return false;
121 });
122}
123
124unsigned Node::hasFree(Value memref) const {
125 return llvm::any_of(Range: memrefFrees, P: [&](Operation *freeOp) {
126 return hasEffect<MemoryEffects::Free>(op: freeOp, value: memref);
127 });
128}
129
130// Returns all store ops in 'storeOps' which access 'memref'.
131void Node::getStoreOpsForMemref(Value memref,
132 SmallVectorImpl<Operation *> *storeOps) const {
133 for (Operation *storeOp : stores) {
134 if (memref == cast<AffineWriteOpInterface>(Val: storeOp).getMemRef())
135 storeOps->push_back(Elt: storeOp);
136 }
137}
138
139// Returns all load ops in 'loadOps' which access 'memref'.
140void Node::getLoadOpsForMemref(Value memref,
141 SmallVectorImpl<Operation *> *loadOps) const {
142 for (Operation *loadOp : loads) {
143 if (memref == cast<AffineReadOpInterface>(Val: loadOp).getMemRef())
144 loadOps->push_back(Elt: loadOp);
145 }
146}
147
148// Returns all memrefs in 'loadAndStoreMemrefSet' for which this node
149// has at least one load and store operation.
150void Node::getLoadAndStoreMemrefSet(
151 DenseSet<Value> *loadAndStoreMemrefSet) const {
152 llvm::SmallDenseSet<Value, 2> loadMemrefs;
153 for (Operation *loadOp : loads) {
154 loadMemrefs.insert(V: cast<AffineReadOpInterface>(Val: loadOp).getMemRef());
155 }
156 for (Operation *storeOp : stores) {
157 auto memref = cast<AffineWriteOpInterface>(Val: storeOp).getMemRef();
158 if (loadMemrefs.count(V: memref) > 0)
159 loadAndStoreMemrefSet->insert(V: memref);
160 }
161}
162
163/// Returns the values that this op has a memref effect of type `EffectTys` on,
164/// not considering recursive effects.
165template <typename... EffectTys>
166static void getEffectedValues(Operation *op, SmallVectorImpl<Value> &values) {
167 auto memOp = dyn_cast<MemoryEffectOpInterface>(Val: op);
168 if (!memOp) {
169 if (op->hasTrait<OpTrait::HasRecursiveMemoryEffects>())
170 // No effects.
171 return;
172 // Memref operands have to be considered as being affected.
173 for (Value operand : op->getOperands()) {
174 if (isa<MemRefType>(Val: operand.getType()))
175 values.push_back(Elt: operand);
176 }
177 return;
178 }
179 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;
180 memOp.getEffects(effects);
181 for (auto &effect : effects) {
182 Value effectVal = effect.getValue();
183 if (isa<EffectTys...>(effect.getEffect()) && effectVal &&
184 isa<MemRefType>(Val: effectVal.getType()))
185 values.push_back(Elt: effectVal);
186 };
187}
188
189/// Add `op` to MDG creating a new node and adding its memory accesses (affine
190/// or non-affine to memrefAccesses (memref -> list of nodes with accesses) map.
191static Node *
192addNodeToMDG(Operation *nodeOp, MemRefDependenceGraph &mdg,
193 DenseMap<Value, SetVector<unsigned>> &memrefAccesses) {
194 auto &nodes = mdg.nodes;
195 // Create graph node 'id' to represent top-level 'forOp' and record
196 // all loads and store accesses it contains.
197 LoopNestStateCollector collector;
198 collector.collect(opToWalk: nodeOp);
199 unsigned newNodeId = mdg.nextNodeId++;
200 Node &node = nodes.insert(KV: {newNodeId, Node(newNodeId, nodeOp)}).first->second;
201 for (Operation *op : collector.loadOpInsts) {
202 node.loads.push_back(Elt: op);
203 auto memref = cast<AffineReadOpInterface>(Val: op).getMemRef();
204 memrefAccesses[memref].insert(X: node.id);
205 }
206 for (Operation *op : collector.storeOpInsts) {
207 node.stores.push_back(Elt: op);
208 auto memref = cast<AffineWriteOpInterface>(Val: op).getMemRef();
209 memrefAccesses[memref].insert(X: node.id);
210 }
211 for (Operation *op : collector.memrefLoads) {
212 SmallVector<Value> effectedValues;
213 getEffectedValues<MemoryEffects::Read>(op, values&: effectedValues);
214 if (llvm::any_of(Range: ((ValueRange)effectedValues).getTypes(),
215 P: [](Type type) { return !isa<MemRefType>(Val: type); }))
216 // We do not know the interaction here.
217 return nullptr;
218 for (Value memref : effectedValues)
219 memrefAccesses[memref].insert(X: node.id);
220 node.memrefLoads.push_back(Elt: op);
221 }
222 for (Operation *op : collector.memrefStores) {
223 SmallVector<Value> effectedValues;
224 getEffectedValues<MemoryEffects::Write>(op, values&: effectedValues);
225 if (llvm::any_of(Range: (ValueRange(effectedValues)).getTypes(),
226 P: [](Type type) { return !isa<MemRefType>(Val: type); }))
227 return nullptr;
228 for (Value memref : effectedValues)
229 memrefAccesses[memref].insert(X: node.id);
230 node.memrefStores.push_back(Elt: op);
231 }
232 for (Operation *op : collector.memrefFrees) {
233 SmallVector<Value> effectedValues;
234 getEffectedValues<MemoryEffects::Free>(op, values&: effectedValues);
235 if (llvm::any_of(Range: (ValueRange(effectedValues)).getTypes(),
236 P: [](Type type) { return !isa<MemRefType>(Val: type); }))
237 return nullptr;
238 for (Value memref : effectedValues)
239 memrefAccesses[memref].insert(X: node.id);
240 node.memrefFrees.push_back(Elt: op);
241 }
242
243 return &node;
244}
245
246/// Returns true if `op` may read from or write to `memref`.
247static bool mayAccessMemRef(Operation *op, Value memref) {
248 SmallVector<Value> effectedValues;
249 getEffectedValues<MemoryEffects::Read, MemoryEffects::Write>(op,
250 values&: effectedValues);
251 if (llvm::is_contained(Range&: effectedValues, Element: memref))
252 return true;
253
254 auto memoryEffectOp = dyn_cast<MemoryEffectOpInterface>(Val: op);
255 if (!memoryEffectOp)
256 return false;
257
258 SmallVector<MemoryEffects::EffectInstance> effects;
259 memoryEffectOp.getEffects(effects);
260 return llvm::any_of(Range&: effects, P: [](const auto &effect) {
261 if (!isa<MemoryEffects::Read, MemoryEffects::Write>(effect.getEffect()))
262 return false;
263
264 // Value-less read/write effects may target unknown memory. Since this is a
265 // may-analysis, conservatively assume they may access the memref.
266 return !effect.getValue();
267 });
268}
269
270/// Returns true if there may be a dependence on `memref` from srcNode's
271/// memory ops to dstNode's memory ops, while using the affine memory
272/// dependence analysis checks. The method assumes that there is at least one
273/// memory op in srcNode's loads and stores on `memref`, and similarly for
274/// `dstNode`. `srcNode.op` and `destNode.op` are expected to be nested in the
275/// same block and so the dependences are tested at the depth of that block.
276static bool mayDependence(const Node &srcNode, const Node &dstNode,
277 Value memref) {
278 assert(srcNode.op->getBlock() == dstNode.op->getBlock());
279 if (!isa<AffineForOp>(Val: srcNode.op) || !isa<AffineForOp>(Val: dstNode.op))
280 return true;
281
282 // Conservatively handle dependences involving non-affine load/stores. Return
283 // true if there exists a conflicting read/write access involving such.
284
285 // Check whether there is a dependence from a source read/write op to a
286 // destination read/write op on `memref`.
287 auto hasNonAffineDep = [&](ArrayRef<Operation *> srcMemOps,
288 ArrayRef<Operation *> dstMemOps) {
289 return llvm::any_of(Range&: srcMemOps,
290 P: [&](Operation *srcOp) {
291 return mayAccessMemRef(op: srcOp, memref);
292 }) &&
293 llvm::any_of(Range&: dstMemOps, P: [&](Operation *dstOp) {
294 return mayAccessMemRef(op: dstOp, memref);
295 });
296 };
297
298 SmallVector<Operation *> dstOps;
299 // Between non-affine src stores and dst load/store.
300 llvm::append_range(C&: dstOps, R: llvm::concat<Operation *const>(
301 Ranges: dstNode.loads, Ranges: dstNode.stores,
302 Ranges: dstNode.memrefLoads, Ranges: dstNode.memrefStores));
303 if (hasNonAffineDep(srcNode.memrefStores, dstOps))
304 return true;
305 // Between non-affine loads and dst stores.
306 dstOps.clear();
307 llvm::append_range(C&: dstOps, R: llvm::concat<Operation *const>(
308 Ranges: dstNode.stores, Ranges: dstNode.memrefStores));
309 if (hasNonAffineDep(srcNode.memrefLoads, dstOps))
310 return true;
311 // Between affine stores and memref load/stores.
312 dstOps.clear();
313 llvm::append_range(C&: dstOps, R: llvm::concat<Operation *const>(
314 Ranges: dstNode.memrefLoads, Ranges: dstNode.memrefStores));
315 if (hasNonAffineDep(srcNode.stores, dstOps))
316 return true;
317 // Between affine loads and memref stores.
318 dstOps.clear();
319 llvm::append_range(C&: dstOps, R: dstNode.memrefStores);
320 if (hasNonAffineDep(srcNode.loads, dstOps))
321 return true;
322
323 // Affine load/store pairs. We don't need to check for locally allocated
324 // memrefs since the dependence analysis here is between mem ops from
325 // srcNode's for op to dstNode's for op at the depth at which those
326 // `affine.for` ops are nested, i.e., dependences at depth `d + 1` where
327 // `d` is the number of common surrounding loops.
328 for (auto *srcMemOp :
329 llvm::concat<Operation *const>(Ranges: srcNode.stores, Ranges: srcNode.loads)) {
330 MemRefAccess srcAcc(srcMemOp);
331 if (srcAcc.memref != memref)
332 continue;
333 for (auto *destMemOp :
334 llvm::concat<Operation *const>(Ranges: dstNode.stores, Ranges: dstNode.loads)) {
335 MemRefAccess destAcc(destMemOp);
336 if (destAcc.memref != memref)
337 continue;
338 // Check for a top-level dependence between srcNode and destNode's ops.
339 if (!noDependence(result: checkMemrefAccessDependence(
340 srcAccess: srcAcc, dstAccess: destAcc, loopDepth: getNestingDepth(op: srcNode.op) + 1)))
341 return true;
342 }
343 }
344 return false;
345}
346
347bool MemRefDependenceGraph::init(bool fullAffineDependences) {
348 LDBG() << "--- Initializing MDG ---";
349 // Map from a memref to the set of ids of the nodes that have ops accessing
350 // the memref.
351 DenseMap<Value, SetVector<unsigned>> memrefAccesses;
352
353 // Create graph nodes.
354 DenseMap<Operation *, unsigned> forToNodeMap;
355 for (Operation &op : block) {
356 if (auto forOp = dyn_cast<AffineForOp>(Val&: op)) {
357 Node *node = addNodeToMDG(nodeOp: &op, mdg&: *this, memrefAccesses);
358 if (!node)
359 return false;
360 forToNodeMap[&op] = node->id;
361 } else if (isa<AffineReadOpInterface>(Val: op)) {
362 // Create graph node for top-level load op.
363 Node node(nextNodeId++, &op);
364 node.loads.push_back(Elt: &op);
365 auto memref = cast<AffineReadOpInterface>(Val&: op).getMemRef();
366 memrefAccesses[memref].insert(X: node.id);
367 nodes.insert(KV: {node.id, node});
368 } else if (isa<AffineWriteOpInterface>(Val: op)) {
369 // Create graph node for top-level store op.
370 Node node(nextNodeId++, &op);
371 node.stores.push_back(Elt: &op);
372 auto memref = cast<AffineWriteOpInterface>(Val&: op).getMemRef();
373 memrefAccesses[memref].insert(X: node.id);
374 nodes.insert(KV: {node.id, node});
375 } else if (op.getNumResults() > 0 && !op.use_empty()) {
376 // Create graph node for top-level producer of SSA values, which
377 // could be used by loop nest nodes.
378 Node *node = addNodeToMDG(nodeOp: &op, mdg&: *this, memrefAccesses);
379 if (!node)
380 return false;
381 } else if (!isMemoryEffectFree(op: &op) &&
382 (op.getNumRegions() == 0 || isa<RegionBranchOpInterface>(Val: op))) {
383 // Create graph node for top-level op unless it is known to be
384 // memory-effect free. This covers all unknown/unregistered ops,
385 // non-affine ops with memory effects, and region-holding ops with a
386 // well-defined control flow. During the fusion validity checks, edges
387 // to/from these ops get looked at.
388 Node *node = addNodeToMDG(nodeOp: &op, mdg&: *this, memrefAccesses);
389 if (!node)
390 return false;
391 } else if (op.getNumRegions() != 0 && !isa<RegionBranchOpInterface>(Val: op)) {
392 // Return false if non-handled/unknown region-holding ops are found. We
393 // won't know what such ops do or what its regions mean; for e.g., it may
394 // not be an imperative op.
395 LDBG() << "MDG init failed; unknown region-holding op found!";
396 return false;
397 }
398 // We aren't creating nodes for memory-effect free ops either with no
399 // regions (unless it has results being used) or those with branch op
400 // interface.
401 }
402
403 LDBG() << "Created " << nodes.size() << " nodes";
404
405 // Add dependence edges between nodes which produce SSA values and their
406 // users. Load ops can be considered as the ones producing SSA values.
407 for (auto &idAndNode : nodes) {
408 const Node &node = idAndNode.second;
409 // Stores don't define SSA values, skip them.
410 if (!node.stores.empty())
411 continue;
412 Operation *opInst = node.op;
413 for (Value value : opInst->getResults()) {
414 for (Operation *user : value.getUsers()) {
415 // Ignore users outside of the block.
416 if (block.getParent()->findAncestorOpInRegion(op&: *user)->getBlock() !=
417 &block)
418 continue;
419 SmallVector<AffineForOp, 4> loops;
420 getAffineForIVs(op&: *user, loops: &loops);
421 // Find the surrounding affine.for nested immediately within the
422 // block.
423 auto *it = llvm::find_if(Range&: loops, P: [&](AffineForOp loop) {
424 return loop->getBlock() == &block;
425 });
426 if (it == loops.end())
427 continue;
428 assert(forToNodeMap.count(*it) > 0 && "missing mapping");
429 unsigned userLoopNestId = forToNodeMap[*it];
430 addEdge(srcId: node.id, dstId: userLoopNestId, value);
431 }
432 }
433 }
434
435 // Walk memref access lists and add graph edges between dependent nodes.
436 for (auto &memrefAndList : memrefAccesses) {
437 unsigned n = memrefAndList.second.size();
438 Value srcMemRef = memrefAndList.first;
439 // Add edges between all dependent pairs among the node IDs on this memref.
440 for (unsigned i = 0; i < n; ++i) {
441 unsigned srcId = memrefAndList.second[i];
442 Node *srcNode = getNode(id: srcId);
443 bool srcHasStoreOrFree =
444 srcNode->hasStore(memref: srcMemRef) || srcNode->hasFree(memref: srcMemRef);
445 for (unsigned j = i + 1; j < n; ++j) {
446 unsigned dstId = memrefAndList.second[j];
447 Node *dstNode = getNode(id: dstId);
448 bool dstHasStoreOrFree =
449 dstNode->hasStore(memref: srcMemRef) || dstNode->hasFree(memref: srcMemRef);
450 if ((srcHasStoreOrFree || dstHasStoreOrFree)) {
451 // Check precise affine deps if asked for; otherwise, conservative.
452 if (!fullAffineDependences ||
453 mayDependence(srcNode: *srcNode, dstNode: *dstNode, memref: srcMemRef))
454 addEdge(srcId, dstId, value: srcMemRef);
455 }
456 }
457 }
458 }
459 return true;
460}
461
462// Returns the graph node for 'id'.
463const Node *MemRefDependenceGraph::getNode(unsigned id) const {
464 auto it = nodes.find(Val: id);
465 assert(it != nodes.end());
466 return &it->second;
467}
468
469// Returns the graph node for 'forOp'.
470const Node *MemRefDependenceGraph::getForOpNode(AffineForOp forOp) const {
471 for (auto &idAndNode : nodes)
472 if (idAndNode.second.op == forOp)
473 return &idAndNode.second;
474 return nullptr;
475}
476
477// Adds a node with 'op' to the graph and returns its unique identifier.
478unsigned MemRefDependenceGraph::addNode(Operation *op) {
479 Node node(nextNodeId++, op);
480 nodes.insert(KV: {node.id, node});
481 return node.id;
482}
483
484// Remove node 'id' (and its associated edges) from graph.
485void MemRefDependenceGraph::removeNode(unsigned id) {
486 // Remove each edge in 'inEdges[id]'.
487 if (inEdges.count(Val: id) > 0) {
488 SmallVector<Edge, 2> oldInEdges = inEdges[id];
489 for (auto &inEdge : oldInEdges) {
490 removeEdge(srcId: inEdge.id, dstId: id, value: inEdge.value);
491 }
492 }
493 // Remove each edge in 'outEdges[id]'.
494 if (outEdges.contains(Val: id)) {
495 SmallVector<Edge, 2> oldOutEdges = outEdges[id];
496 for (auto &outEdge : oldOutEdges) {
497 removeEdge(srcId: id, dstId: outEdge.id, value: outEdge.value);
498 }
499 }
500 // Erase remaining node state.
501 inEdges.erase(Val: id);
502 outEdges.erase(Val: id);
503 nodes.erase(Val: id);
504}
505
506// Returns true if node 'id' writes to any memref which escapes (or is an
507// argument to) the block. Returns false otherwise.
508bool MemRefDependenceGraph::writesToLiveInOrEscapingMemrefs(unsigned id) const {
509 const Node *node = getNode(id);
510 for (auto *storeOpInst : node->stores) {
511 auto memref = cast<AffineWriteOpInterface>(Val: storeOpInst).getMemRef();
512 auto *op = memref.getDefiningOp();
513 // Return true if 'memref' is a block argument.
514 if (!op)
515 return true;
516 // Return true if any use of 'memref' does not deference it in an affine
517 // way.
518 for (auto *user : memref.getUsers())
519 if (!isa<AffineMapAccessInterface>(Val: *user))
520 return true;
521 }
522 return false;
523}
524
525// Returns true iff there is an edge from node 'srcId' to node 'dstId' which
526// is for 'value' if non-null, or for any value otherwise. Returns false
527// otherwise.
528bool MemRefDependenceGraph::hasEdge(unsigned srcId, unsigned dstId,
529 Value value) const {
530 if (!outEdges.contains(Val: srcId) || !inEdges.contains(Val: dstId)) {
531 return false;
532 }
533 bool hasOutEdge = llvm::any_of(Range: outEdges.lookup(Val: srcId), P: [=](const Edge &edge) {
534 return edge.id == dstId && (!value || edge.value == value);
535 });
536 bool hasInEdge = llvm::any_of(Range: inEdges.lookup(Val: dstId), P: [=](const Edge &edge) {
537 return edge.id == srcId && (!value || edge.value == value);
538 });
539 return hasOutEdge && hasInEdge;
540}
541
542// Adds an edge from node 'srcId' to node 'dstId' for 'value'.
543void MemRefDependenceGraph::addEdge(unsigned srcId, unsigned dstId,
544 Value value) {
545 if (!hasEdge(srcId, dstId, value)) {
546 outEdges[srcId].push_back(Elt: {.id: dstId, .value: value});
547 inEdges[dstId].push_back(Elt: {.id: srcId, .value: value});
548 if (isa<MemRefType>(Val: value.getType()))
549 memrefEdgeCount[value]++;
550 }
551}
552
553// Removes an edge from node 'srcId' to node 'dstId' for 'value'.
554void MemRefDependenceGraph::removeEdge(unsigned srcId, unsigned dstId,
555 Value value) {
556 assert(inEdges.count(dstId) > 0);
557 assert(outEdges.count(srcId) > 0);
558 if (isa<MemRefType>(Val: value.getType())) {
559 assert(memrefEdgeCount.count(value) > 0);
560 memrefEdgeCount[value]--;
561 }
562 // Remove 'srcId' from 'inEdges[dstId]'.
563 for (auto *it = inEdges[dstId].begin(); it != inEdges[dstId].end(); ++it) {
564 if ((*it).id == srcId && (*it).value == value) {
565 inEdges[dstId].erase(CI: it);
566 break;
567 }
568 }
569 // Remove 'dstId' from 'outEdges[srcId]'.
570 for (auto *it = outEdges[srcId].begin(); it != outEdges[srcId].end(); ++it) {
571 if ((*it).id == dstId && (*it).value == value) {
572 outEdges[srcId].erase(CI: it);
573 break;
574 }
575 }
576}
577
578// Returns true if there is a path in the dependence graph from node 'srcId'
579// to node 'dstId'. Returns false otherwise. `srcId`, `dstId`, and the
580// operations that the edges connected are expected to be from the same block.
581bool MemRefDependenceGraph::hasDependencePath(unsigned srcId,
582 unsigned dstId) const {
583 // Worklist state is: <node-id, next-output-edge-index-to-visit>
584 SmallVector<std::pair<unsigned, unsigned>, 4> worklist;
585 worklist.push_back(Elt: {srcId, 0});
586 Operation *dstOp = getNode(id: dstId)->op;
587 // Run DFS traversal to see if 'dstId' is reachable from 'srcId'.
588 while (!worklist.empty()) {
589 auto &idAndIndex = worklist.back();
590 // Return true if we have reached 'dstId'.
591 if (idAndIndex.first == dstId)
592 return true;
593 // Pop and continue if node has no out edges, or if all out edges have
594 // already been visited.
595 if (!outEdges.contains(Val: idAndIndex.first) ||
596 idAndIndex.second == outEdges.lookup(Val: idAndIndex.first).size()) {
597 worklist.pop_back();
598 continue;
599 }
600 // Get graph edge to traverse.
601 const Edge edge = outEdges.lookup(Val: idAndIndex.first)[idAndIndex.second];
602 // Increment next output edge index for 'idAndIndex'.
603 ++idAndIndex.second;
604 // Add node at 'edge.id' to the worklist. We don't need to consider
605 // nodes that are "after" dstId in the containing block; one can't have a
606 // path to `dstId` from any of those nodes.
607 bool afterDst = dstOp->isBeforeInBlock(other: getNode(id: edge.id)->op);
608 if (!afterDst && edge.id != idAndIndex.first)
609 worklist.push_back(Elt: {edge.id, 0});
610 }
611 return false;
612}
613
614// Returns the input edge count for node 'id' and 'memref' from src nodes
615// which access 'memref' with a store operation.
616unsigned MemRefDependenceGraph::getIncomingMemRefAccesses(unsigned id,
617 Value memref) const {
618 unsigned inEdgeCount = 0;
619 for (const Edge &inEdge : inEdges.lookup(Val: id)) {
620 if (inEdge.value == memref) {
621 const Node *srcNode = getNode(id: inEdge.id);
622 // Only count in edges from 'srcNode' if 'srcNode' accesses 'memref'
623 if (srcNode->getStoreOpCount(memref) > 0)
624 ++inEdgeCount;
625 }
626 }
627 return inEdgeCount;
628}
629
630// Returns the output edge count for node 'id' and 'memref' (if non-null),
631// otherwise returns the total output edge count from node 'id'.
632unsigned MemRefDependenceGraph::getOutEdgeCount(unsigned id,
633 Value memref) const {
634 unsigned outEdgeCount = 0;
635 for (const auto &outEdge : outEdges.lookup(Val: id))
636 if (!memref || outEdge.value == memref)
637 ++outEdgeCount;
638 return outEdgeCount;
639}
640
641/// Return all nodes which define SSA values used in node 'id'.
642void MemRefDependenceGraph::gatherDefiningNodes(
643 unsigned id, DenseSet<unsigned> &definingNodes) const {
644 for (const Edge &edge : inEdges.lookup(Val: id))
645 // By definition of edge, if the edge value is a non-memref value,
646 // then the dependence is between a graph node which defines an SSA value
647 // and another graph node which uses the SSA value.
648 if (!isa<MemRefType>(Val: edge.value.getType()))
649 definingNodes.insert(V: edge.id);
650}
651
652// Computes and returns an insertion point operation, before which the
653// the fused <srcId, dstId> loop nest can be inserted while preserving
654// dependences. Returns nullptr if no such insertion point is found.
655Operation *
656MemRefDependenceGraph::getFusedLoopNestInsertionPoint(unsigned srcId,
657 unsigned dstId) const {
658 if (!outEdges.contains(Val: srcId))
659 return getNode(id: dstId)->op;
660
661 // Skip if there is any defining node of 'dstId' that depends on 'srcId'.
662 DenseSet<unsigned> definingNodes;
663 gatherDefiningNodes(id: dstId, definingNodes);
664 if (llvm::any_of(Range&: definingNodes,
665 P: [&](unsigned id) { return hasDependencePath(srcId, dstId: id); })) {
666 LDBG() << "Can't fuse: a defining op with a user in the dst "
667 << "loop has dependence from the src loop";
668 return nullptr;
669 }
670
671 // Build set of insts in range (srcId, dstId) which depend on 'srcId'.
672 llvm::SmallPtrSet<Operation *, 2> srcDepInsts;
673 for (auto &outEdge : outEdges.lookup(Val: srcId))
674 if (outEdge.id != dstId)
675 srcDepInsts.insert(Ptr: getNode(id: outEdge.id)->op);
676
677 // Build set of insts in range (srcId, dstId) on which 'dstId' depends.
678 llvm::SmallPtrSet<Operation *, 2> dstDepInsts;
679 for (auto &inEdge : inEdges.lookup(Val: dstId))
680 if (inEdge.id != srcId)
681 dstDepInsts.insert(Ptr: getNode(id: inEdge.id)->op);
682
683 Operation *srcNodeInst = getNode(id: srcId)->op;
684 Operation *dstNodeInst = getNode(id: dstId)->op;
685
686 // Computing insertion point:
687 // *) Walk all operation positions in Block operation list in the
688 // range (src, dst). For each operation 'op' visited in this search:
689 // *) Store in 'firstSrcDepPos' the first position where 'op' has a
690 // dependence edge from 'srcNode'.
691 // *) Store in 'lastDstDepPost' the last position where 'op' has a
692 // dependence edge to 'dstNode'.
693 // *) Compare 'firstSrcDepPos' and 'lastDstDepPost' to determine the
694 // operation insertion point (or return null pointer if no such
695 // insertion point exists: 'firstSrcDepPos' <= 'lastDstDepPos').
696 SmallVector<Operation *, 2> depInsts;
697 std::optional<unsigned> firstSrcDepPos;
698 std::optional<unsigned> lastDstDepPos;
699 unsigned pos = 0;
700 for (Block::iterator it = std::next(x: Block::iterator(srcNodeInst));
701 it != Block::iterator(dstNodeInst); ++it) {
702 Operation *op = &(*it);
703 if (srcDepInsts.count(Ptr: op) > 0 && firstSrcDepPos == std::nullopt)
704 firstSrcDepPos = pos;
705 if (dstDepInsts.count(Ptr: op) > 0)
706 lastDstDepPos = pos;
707 depInsts.push_back(Elt: op);
708 ++pos;
709 }
710
711 if (firstSrcDepPos.has_value()) {
712 if (lastDstDepPos.has_value()) {
713 if (*firstSrcDepPos <= *lastDstDepPos) {
714 // No valid insertion point exists which preserves dependences.
715 return nullptr;
716 }
717 }
718 // Return the insertion point at 'firstSrcDepPos'.
719 return depInsts[*firstSrcDepPos];
720 }
721 // No dependence targets in range (or only dst deps in range), return
722 // 'dstNodInst' insertion point.
723 return dstNodeInst;
724}
725
726// Updates edge mappings from node 'srcId' to node 'dstId' after fusing them,
727// taking into account that:
728// *) if 'removeSrcId' is true, 'srcId' will be removed after fusion,
729// *) memrefs in 'privateMemRefs' has been replaced in node at 'dstId' by a
730// private memref.
731void MemRefDependenceGraph::updateEdges(unsigned srcId, unsigned dstId,
732 const DenseSet<Value> &privateMemRefs,
733 bool removeSrcId) {
734 // For each edge in 'inEdges[srcId]': add new edge remapping to 'dstId'.
735 if (inEdges.count(Val: srcId) > 0) {
736 SmallVector<Edge, 2> oldInEdges = inEdges[srcId];
737 for (auto &inEdge : oldInEdges) {
738 // Add edge from 'inEdge.id' to 'dstId' if it's not a private memref.
739 if (!privateMemRefs.contains(V: inEdge.value))
740 addEdge(srcId: inEdge.id, dstId, value: inEdge.value);
741 }
742 }
743 // For each edge in 'outEdges[srcId]': remove edge from 'srcId' to 'dstId'.
744 // If 'srcId' is going to be removed, remap all the out edges to 'dstId'.
745 if (outEdges.count(Val: srcId) > 0) {
746 SmallVector<Edge, 2> oldOutEdges = outEdges[srcId];
747 for (auto &outEdge : oldOutEdges) {
748 // Remove any out edges from 'srcId' to 'dstId' across memrefs.
749 if (outEdge.id == dstId)
750 removeEdge(srcId, dstId: outEdge.id, value: outEdge.value);
751 else if (removeSrcId) {
752 addEdge(srcId: dstId, dstId: outEdge.id, value: outEdge.value);
753 removeEdge(srcId, dstId: outEdge.id, value: outEdge.value);
754 }
755 }
756 }
757 // Remove any edges in 'inEdges[dstId]' on 'oldMemRef' (which is being
758 // replaced by a private memref). These edges could come from nodes
759 // other than 'srcId' which were removed in the previous step.
760 if (inEdges.count(Val: dstId) > 0 && !privateMemRefs.empty()) {
761 SmallVector<Edge, 2> oldInEdges = inEdges[dstId];
762 for (auto &inEdge : oldInEdges)
763 if (privateMemRefs.count(V: inEdge.value) > 0)
764 removeEdge(srcId: inEdge.id, dstId, value: inEdge.value);
765 }
766}
767
768// Update edge mappings for nodes 'sibId' and 'dstId' to reflect fusion
769// of sibling node 'sibId' into node 'dstId'.
770void MemRefDependenceGraph::updateEdges(unsigned sibId, unsigned dstId) {
771 // For each edge in 'inEdges[sibId]':
772 // *) Add new edge from source node 'inEdge.id' to 'dstNode'.
773 // *) Remove edge from source node 'inEdge.id' to 'sibNode'.
774 if (inEdges.count(Val: sibId) > 0) {
775 SmallVector<Edge, 2> oldInEdges = inEdges[sibId];
776 for (auto &inEdge : oldInEdges) {
777 addEdge(srcId: inEdge.id, dstId, value: inEdge.value);
778 removeEdge(srcId: inEdge.id, dstId: sibId, value: inEdge.value);
779 }
780 }
781
782 // For each edge in 'outEdges[sibId]' to node 'id'
783 // *) Add new edge from 'dstId' to 'outEdge.id'.
784 // *) Remove edge from 'sibId' to 'outEdge.id'.
785 if (outEdges.count(Val: sibId) > 0) {
786 SmallVector<Edge, 2> oldOutEdges = outEdges[sibId];
787 for (auto &outEdge : oldOutEdges) {
788 addEdge(srcId: dstId, dstId: outEdge.id, value: outEdge.value);
789 removeEdge(srcId: sibId, dstId: outEdge.id, value: outEdge.value);
790 }
791 }
792}
793
794// Adds ops in 'loads' and 'stores' to node at 'id'.
795void MemRefDependenceGraph::addToNode(unsigned id, ArrayRef<Operation *> loads,
796 ArrayRef<Operation *> stores,
797 ArrayRef<Operation *> memrefLoads,
798 ArrayRef<Operation *> memrefStores,
799 ArrayRef<Operation *> memrefFrees) {
800 Node *node = getNode(id);
801 llvm::append_range(C&: node->loads, R&: loads);
802 llvm::append_range(C&: node->stores, R&: stores);
803 llvm::append_range(C&: node->memrefLoads, R&: memrefLoads);
804 llvm::append_range(C&: node->memrefStores, R&: memrefStores);
805 llvm::append_range(C&: node->memrefFrees, R&: memrefFrees);
806}
807
808void MemRefDependenceGraph::clearNodeLoadAndStores(unsigned id) {
809 Node *node = getNode(id);
810 node->loads.clear();
811 node->stores.clear();
812}
813
814// Calls 'callback' for each input edge incident to node 'id' which carries a
815// memref dependence.
816void MemRefDependenceGraph::forEachMemRefInputEdge(
817 unsigned id, const std::function<void(Edge)> &callback) {
818 if (inEdges.count(Val: id) > 0)
819 forEachMemRefEdge(edges: inEdges.at(Val: id), callback);
820}
821
822// Calls 'callback' for each output edge from node 'id' which carries a
823// memref dependence.
824void MemRefDependenceGraph::forEachMemRefOutputEdge(
825 unsigned id, const std::function<void(Edge)> &callback) {
826 if (outEdges.count(Val: id) > 0)
827 forEachMemRefEdge(edges: outEdges.at(Val: id), callback);
828}
829
830// Calls 'callback' for each edge in 'edges' which carries a memref
831// dependence.
832void MemRefDependenceGraph::forEachMemRefEdge(
833 ArrayRef<Edge> edges, const std::function<void(Edge)> &callback) {
834 for (const auto &edge : edges) {
835 // Skip if 'edge' is not a memref dependence edge.
836 if (!isa<MemRefType>(Val: edge.value.getType()))
837 continue;
838 assert(nodes.count(edge.id) > 0);
839 // Visit current input edge 'edge'.
840 callback(edge);
841 }
842}
843
844void MemRefDependenceGraph::print(raw_ostream &os) const {
845 os << "\nMemRefDependenceGraph\n";
846 os << "\nNodes:\n";
847 for (const auto &idAndNode : nodes) {
848 os << "Node: " << idAndNode.first << "\n";
849 auto it = inEdges.find(Val: idAndNode.first);
850 if (it != inEdges.end()) {
851 for (const auto &e : it->second)
852 os << " InEdge: " << e.id << " " << e.value << "\n";
853 }
854 it = outEdges.find(Val: idAndNode.first);
855 if (it != outEdges.end()) {
856 for (const auto &e : it->second)
857 os << " OutEdge: " << e.id << " " << e.value << "\n";
858 }
859 }
860}
861
862#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
863void MemRefDependenceGraph::dump() const { print(llvm::errs()); }
864#endif
865
866void mlir::affine::getAffineForIVs(Operation &op,
867 SmallVectorImpl<AffineForOp> *loops) {
868 auto *currOp = op.getParentOp();
869 AffineForOp currAffineForOp;
870 // Traverse up the hierarchy collecting all 'affine.for' operation while
871 // skipping over 'affine.if' operations.
872 while (currOp && !currOp->hasTrait<OpTrait::AffineScope>()) {
873 if (auto currAffineForOp = dyn_cast<AffineForOp>(Val: currOp))
874 loops->push_back(Elt: currAffineForOp);
875 currOp = currOp->getParentOp();
876 }
877 std::reverse(first: loops->begin(), last: loops->end());
878}
879
880void mlir::affine::getEnclosingAffineOps(Operation &op,
881 SmallVectorImpl<Operation *> *ops) {
882 ops->clear();
883 Operation *currOp = op.getParentOp();
884
885 // Traverse up the hierarchy collecting all `affine.for`, `affine.if`, and
886 // affine.parallel operations.
887 while (currOp && !currOp->hasTrait<OpTrait::AffineScope>()) {
888 if (isa<AffineIfOp, AffineForOp, AffineParallelOp>(Val: currOp))
889 ops->push_back(Elt: currOp);
890 currOp = currOp->getParentOp();
891 }
892 std::reverse(first: ops->begin(), last: ops->end());
893}
894
895// Populates 'cst' with FlatAffineValueConstraints which represent original
896// domain of the loop bounds that define 'ivs'.
897LogicalResult ComputationSliceState::getSourceAsConstraints(
898 FlatAffineValueConstraints &cst) const {
899 assert(!ivs.empty() && "Cannot have a slice without its IVs");
900 cst = FlatAffineValueConstraints(/*numDims=*/ivs.size(), /*numSymbols=*/0,
901 /*numLocals=*/0, ivs);
902 for (Value iv : ivs) {
903 AffineForOp loop = getForInductionVarOwner(val: iv);
904 assert(loop && "Expected affine for");
905 if (failed(Result: cst.addAffineForOpDomain(forOp: loop)))
906 return failure();
907 }
908 return success();
909}
910
911// Populates 'cst' with FlatAffineValueConstraints which represent slice bounds.
912LogicalResult
913ComputationSliceState::getAsConstraints(FlatAffineValueConstraints *cst) const {
914 assert(!lbOperands.empty());
915 // Adds src 'ivs' as dimension variables in 'cst'.
916 unsigned numDims = ivs.size();
917 // Adds operands (dst ivs and symbols) as symbols in 'cst'.
918 unsigned numSymbols = lbOperands[0].size();
919
920 SmallVector<Value, 4> values(ivs);
921 // Append 'ivs' then 'operands' to 'values'.
922 values.append(in_start: lbOperands[0].begin(), in_end: lbOperands[0].end());
923 *cst = FlatAffineValueConstraints(numDims, numSymbols, 0, values);
924
925 // Add loop bound constraints for values which are loop IVs of the destination
926 // of fusion and equality constraints for symbols which are constants.
927 for (unsigned i = numDims, end = values.size(); i < end; ++i) {
928 Value value = values[i];
929 assert(cst->containsVar(value) && "value expected to be present");
930 if (isValidSymbol(value)) {
931 // Check if the symbol is a constant.
932 if (std::optional<int64_t> cOp = getConstantIntValue(ofr: value))
933 cst->addBound(type: BoundType::EQ, val: value, value: cOp.value());
934 } else if (auto loop = getForInductionVarOwner(val: value)) {
935 if (failed(Result: cst->addAffineForOpDomain(forOp: loop)))
936 return failure();
937 }
938 }
939
940 // Add slices bounds on 'ivs' using maps 'lbs'/'ubs' with 'lbOperands[0]'
941 LogicalResult ret = cst->addSliceBounds(values: ivs, lbMaps: lbs, ubMaps: ubs, operands: lbOperands[0]);
942 assert(succeeded(ret) &&
943 "should not fail as we never have semi-affine slice maps");
944 (void)ret;
945 return success();
946}
947
948// Clears state bounds and operand state.
949void ComputationSliceState::clearBounds() {
950 lbs.clear();
951 ubs.clear();
952 lbOperands.clear();
953 ubOperands.clear();
954}
955
956#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
957void ComputationSliceState::dump() const {
958 llvm::errs() << "\tIVs:\n";
959 for (Value iv : ivs)
960 llvm::errs() << "\t\t" << iv << "\n";
961
962 llvm::errs() << "\tLBs:\n";
963 for (auto en : llvm::enumerate(lbs)) {
964 llvm::errs() << "\t\t" << en.value() << "\n";
965 llvm::errs() << "\t\tOperands:\n";
966 for (Value lbOp : lbOperands[en.index()])
967 llvm::errs() << "\t\t\t" << lbOp << "\n";
968 }
969
970 llvm::errs() << "\tUBs:\n";
971 for (auto en : llvm::enumerate(ubs)) {
972 llvm::errs() << "\t\t" << en.value() << "\n";
973 llvm::errs() << "\t\tOperands:\n";
974 for (Value ubOp : ubOperands[en.index()])
975 llvm::errs() << "\t\t\t" << ubOp << "\n";
976 }
977}
978#endif
979
980/// Fast check to determine if the computation slice is maximal. Returns true if
981/// each slice dimension maps to an existing dst dimension and both the src
982/// and the dst loops for those dimensions have the same bounds. Returns false
983/// if both the src and the dst loops don't have the same bounds. Returns
984/// std::nullopt if none of the above can be proven.
985std::optional<bool> ComputationSliceState::isSliceMaximalFastCheck() const {
986 assert(lbs.size() == ubs.size() && !lbs.empty() && !ivs.empty() &&
987 "Unexpected number of lbs, ubs and ivs in slice");
988
989 for (unsigned i = 0, end = lbs.size(); i < end; ++i) {
990 AffineMap lbMap = lbs[i];
991 AffineMap ubMap = ubs[i];
992
993 // Check if this slice is just an equality along this dimension.
994 if (!lbMap || !ubMap || lbMap.getNumResults() != 1 ||
995 ubMap.getNumResults() != 1 ||
996 lbMap.getResult(idx: 0) + 1 != ubMap.getResult(idx: 0) ||
997 // The condition above will be true for maps describing a single
998 // iteration (e.g., lbMap.getResult(0) = 0, ubMap.getResult(0) = 1).
999 // Make sure we skip those cases by checking that the lb result is not
1000 // just a constant.
1001 isa<AffineConstantExpr>(Val: lbMap.getResult(idx: 0)))
1002 return std::nullopt;
1003
1004 // Limited support: we expect the lb result to be just a loop dimension for
1005 // now.
1006 AffineDimExpr result = dyn_cast<AffineDimExpr>(Val: lbMap.getResult(idx: 0));
1007 if (!result)
1008 return std::nullopt;
1009
1010 // Retrieve dst loop bounds.
1011 AffineForOp dstLoop =
1012 getForInductionVarOwner(val: lbOperands[i][result.getPosition()]);
1013 if (!dstLoop)
1014 return std::nullopt;
1015 AffineMap dstLbMap = dstLoop.getLowerBoundMap();
1016 AffineMap dstUbMap = dstLoop.getUpperBoundMap();
1017
1018 // Retrieve src loop bounds.
1019 AffineForOp srcLoop = getForInductionVarOwner(val: ivs[i]);
1020 assert(srcLoop && "Expected affine for");
1021 AffineMap srcLbMap = srcLoop.getLowerBoundMap();
1022 AffineMap srcUbMap = srcLoop.getUpperBoundMap();
1023
1024 // Limited support: we expect simple src and dst loops with a single
1025 // constant component per bound for now.
1026 if (srcLbMap.getNumResults() != 1 || srcUbMap.getNumResults() != 1 ||
1027 dstLbMap.getNumResults() != 1 || dstUbMap.getNumResults() != 1)
1028 return std::nullopt;
1029
1030 AffineExpr srcLbResult = srcLbMap.getResult(idx: 0);
1031 AffineExpr dstLbResult = dstLbMap.getResult(idx: 0);
1032 AffineExpr srcUbResult = srcUbMap.getResult(idx: 0);
1033 AffineExpr dstUbResult = dstUbMap.getResult(idx: 0);
1034 if (!isa<AffineConstantExpr>(Val: srcLbResult) ||
1035 !isa<AffineConstantExpr>(Val: srcUbResult) ||
1036 !isa<AffineConstantExpr>(Val: dstLbResult) ||
1037 !isa<AffineConstantExpr>(Val: dstUbResult))
1038 return std::nullopt;
1039
1040 // Check if src and dst loop bounds are the same. If not, we can guarantee
1041 // that the slice is not maximal.
1042 if (srcLbResult != dstLbResult || srcUbResult != dstUbResult ||
1043 srcLoop.getStep() != dstLoop.getStep())
1044 return false;
1045 }
1046
1047 return true;
1048}
1049
1050/// Returns true if it is deterministically verified that the original iteration
1051/// space of the slice is contained within the new iteration space that is
1052/// created after fusing 'this' slice into its destination.
1053std::optional<bool> ComputationSliceState::isSliceValid() const {
1054 // Fast check to determine if the slice is valid. If the following conditions
1055 // are verified to be true, slice is declared valid by the fast check:
1056 // 1. Each slice loop is a single iteration loop bound in terms of a single
1057 // destination loop IV.
1058 // 2. Loop bounds of the destination loop IV (from above) and those of the
1059 // source loop IV are exactly the same.
1060 // If the fast check is inconclusive or false, we proceed with a more
1061 // expensive analysis.
1062 // TODO: Store the result of the fast check, as it might be used again in
1063 // `canRemoveSrcNodeAfterFusion`.
1064 std::optional<bool> isValidFastCheck = isSliceMaximalFastCheck();
1065 if (isValidFastCheck && *isValidFastCheck)
1066 return true;
1067
1068 // Create constraints for the source loop nest using which slice is computed.
1069 FlatAffineValueConstraints srcConstraints;
1070 // TODO: Store the source's domain to avoid computation at each depth.
1071 if (failed(Result: getSourceAsConstraints(cst&: srcConstraints))) {
1072 LDBG() << "Unable to compute source's domain";
1073 return std::nullopt;
1074 }
1075 // TODO: Handle local vars in the source domains while using the 'projectOut'
1076 // utility below. Currently, aligning is not done assuming that there will be
1077 // no local vars in the source domain.
1078 if (srcConstraints.getNumLocalVars() != 0) {
1079 LDBG() << "Cannot handle locals in source domain";
1080 return std::nullopt;
1081 }
1082
1083 // Create constraints for the slice loop nest that would be created if the
1084 // fusion succeeds.
1085 FlatAffineValueConstraints sliceConstraints;
1086 if (failed(Result: getAsConstraints(cst: &sliceConstraints))) {
1087 LDBG() << "Unable to compute slice's domain";
1088 return std::nullopt;
1089 }
1090
1091 // Projecting out every dimension other than the 'ivs' to express slice's
1092 // domain completely in terms of source's IVs.
1093 sliceConstraints.projectOut(pos: ivs.size(),
1094 num: sliceConstraints.getNumVars() - ivs.size());
1095 srcConstraints.projectOut(pos: ivs.size(),
1096 num: srcConstraints.getNumVars() - ivs.size());
1097
1098 LDBG() << "Domain of the source of the slice:\n"
1099 << "Source constraints:" << srcConstraints
1100 << "\nDomain of the slice if this fusion succeeds "
1101 << "(expressed in terms of its source's IVs):\n"
1102 << "Slice constraints:" << sliceConstraints;
1103
1104 // TODO: Store 'srcSet' to avoid recalculating for each depth.
1105 PresburgerSet srcSet(srcConstraints);
1106 PresburgerSet sliceSet(sliceConstraints);
1107 PresburgerSet diffSet = sliceSet.subtract(set: srcSet);
1108
1109 if (!diffSet.isIntegerEmpty()) {
1110 LDBG() << "Incorrect slice";
1111 return false;
1112 }
1113 return true;
1114}
1115
1116/// Returns true if the computation slice encloses all the iterations of the
1117/// sliced loop nest. Returns false if it does not. Returns std::nullopt if it
1118/// cannot determine if the slice is maximal or not.
1119std::optional<bool> ComputationSliceState::isMaximal() const {
1120 // Fast check to determine if the computation slice is maximal. If the result
1121 // is inconclusive, we proceed with a more expensive analysis.
1122 std::optional<bool> isMaximalFastCheck = isSliceMaximalFastCheck();
1123 if (isMaximalFastCheck)
1124 return isMaximalFastCheck;
1125
1126 // Create constraints for the src loop nest being sliced.
1127 FlatAffineValueConstraints srcConstraints(/*numDims=*/ivs.size(),
1128 /*numSymbols=*/0,
1129 /*numLocals=*/0, ivs);
1130 for (Value iv : ivs) {
1131 AffineForOp loop = getForInductionVarOwner(val: iv);
1132 assert(loop && "Expected affine for");
1133 if (failed(Result: srcConstraints.addAffineForOpDomain(forOp: loop)))
1134 return std::nullopt;
1135 }
1136
1137 // Create constraints for the slice using the dst loop nest information. We
1138 // retrieve existing dst loops from the lbOperands.
1139 SmallVector<Value> consumerIVs;
1140 for (Value lbOp : lbOperands[0])
1141 if (getForInductionVarOwner(val: lbOp))
1142 consumerIVs.push_back(Elt: lbOp);
1143
1144 // Add empty IV Values for those new loops that are not equalities and,
1145 // therefore, are not yet materialized in the IR.
1146 for (int i = consumerIVs.size(), end = ivs.size(); i < end; ++i)
1147 consumerIVs.push_back(Elt: Value());
1148
1149 FlatAffineValueConstraints sliceConstraints(/*numDims=*/consumerIVs.size(),
1150 /*numSymbols=*/0,
1151 /*numLocals=*/0, consumerIVs);
1152
1153 if (failed(Result: sliceConstraints.addDomainFromSliceMaps(lbMaps: lbs, ubMaps: ubs, operands: lbOperands[0])))
1154 return std::nullopt;
1155
1156 if (srcConstraints.getNumDimVars() != sliceConstraints.getNumDimVars())
1157 // Constraint dims are different. The integer set difference can't be
1158 // computed so we don't know if the slice is maximal.
1159 return std::nullopt;
1160
1161 // Compute the difference between the src loop nest and the slice integer
1162 // sets.
1163 PresburgerSet srcSet(srcConstraints);
1164 PresburgerSet sliceSet(sliceConstraints);
1165 PresburgerSet diffSet = srcSet.subtract(set: sliceSet);
1166 return diffSet.isIntegerEmpty();
1167}
1168
1169unsigned MemRefRegion::getRank() const {
1170 return cast<MemRefType>(Val: memref.getType()).getRank();
1171}
1172
1173std::optional<int64_t> MemRefRegion::getConstantBoundingSizeAndShape(
1174 SmallVectorImpl<int64_t> *shape, SmallVectorImpl<AffineMap> *lbs) const {
1175 auto memRefType = cast<MemRefType>(Val: memref.getType());
1176 MLIRContext *context = memref.getContext();
1177 unsigned rank = memRefType.getRank();
1178 if (shape)
1179 shape->reserve(N: rank);
1180
1181 assert(rank == cst.getNumDimVars() && "inconsistent memref region");
1182
1183 // Use a copy of the region constraints that has upper/lower bounds for each
1184 // memref dimension with static size added to guard against potential
1185 // over-approximation from projection or union bounding box. We may not add
1186 // this on the region itself since they might just be redundant constraints
1187 // that will need non-trivials means to eliminate.
1188 FlatLinearValueConstraints cstWithShapeBounds(cst);
1189 for (unsigned r = 0; r < rank; r++) {
1190 cstWithShapeBounds.addBound(type: BoundType::LB, pos: r, value: 0);
1191 int64_t dimSize = memRefType.getDimSize(idx: r);
1192 if (ShapedType::isDynamic(dValue: dimSize))
1193 continue;
1194 cstWithShapeBounds.addBound(type: BoundType::UB, pos: r, value: dimSize - 1);
1195 }
1196
1197 // Find a constant upper bound on the extent of this memref region along
1198 // each dimension.
1199 int64_t numElements = 1;
1200 int64_t diffConstant;
1201 for (unsigned d = 0; d < rank; d++) {
1202 AffineMap lb;
1203 std::optional<int64_t> diff =
1204 cstWithShapeBounds.getConstantBoundOnDimSize(context, pos: d, lb: &lb);
1205 if (diff.has_value()) {
1206 diffConstant = *diff;
1207 assert(diffConstant >= 0 && "dim size bound cannot be negative");
1208 } else {
1209 // If no constant bound is found, then it can always be bound by the
1210 // memref's dim size if the latter has a constant size along this dim.
1211 auto dimSize = memRefType.getDimSize(idx: d);
1212 if (ShapedType::isDynamic(dValue: dimSize))
1213 return std::nullopt;
1214 diffConstant = dimSize;
1215 // Lower bound becomes 0.
1216 lb = AffineMap::get(/*dimCount=*/0, symbolCount: cstWithShapeBounds.getNumSymbolVars(),
1217 /*result=*/getAffineConstantExpr(constant: 0, context));
1218 }
1219 numElements *= diffConstant;
1220 // Populate outputs if available.
1221 if (lbs)
1222 lbs->push_back(Elt: lb);
1223 if (shape)
1224 shape->push_back(Elt: diffConstant);
1225 }
1226 return numElements;
1227}
1228
1229void MemRefRegion::getLowerAndUpperBound(unsigned pos, AffineMap &lbMap,
1230 AffineMap &ubMap) const {
1231 assert(pos < cst.getNumDimVars() && "invalid position");
1232 auto memRefType = cast<MemRefType>(Val: memref.getType());
1233 unsigned rank = memRefType.getRank();
1234
1235 assert(rank == cst.getNumDimVars() && "inconsistent memref region");
1236
1237 auto boundPairs = cst.getLowerAndUpperBound(
1238 pos, /*offset=*/0, /*num=*/rank, symStartPos: cst.getNumDimAndSymbolVars(),
1239 /*localExprs=*/{}, context: memRefType.getContext());
1240 lbMap = boundPairs.first;
1241 ubMap = boundPairs.second;
1242 assert(lbMap && "lower bound for a region must exist");
1243 assert(ubMap && "upper bound for a region must exist");
1244 assert(lbMap.getNumInputs() == cst.getNumDimAndSymbolVars() - rank);
1245 assert(ubMap.getNumInputs() == cst.getNumDimAndSymbolVars() - rank);
1246}
1247
1248LogicalResult MemRefRegion::unionBoundingBox(const MemRefRegion &other) {
1249 assert(memref == other.memref);
1250 return cst.unionBoundingBox(other: *other.getConstraints());
1251}
1252
1253/// Computes the memory region accessed by this memref with the region
1254/// represented as constraints symbolic/parametric in 'loopDepth' loops
1255/// surrounding opInst and any additional Function symbols.
1256// For example, the memref region for this load operation at loopDepth = 1 will
1257// be as below:
1258//
1259// affine.for %i = 0 to 32 {
1260// affine.for %ii = %i to (d0) -> (d0 + 8) (%i) {
1261// load %A[%ii]
1262// }
1263// }
1264//
1265// region: {memref = %A, write = false, {%i <= m0 <= %i + 7} }
1266// The last field is a 2-d FlatAffineValueConstraints symbolic in %i.
1267//
1268// TODO: extend this to any other memref dereferencing ops
1269// (dma_start, dma_wait).
1270LogicalResult MemRefRegion::compute(Operation *op, unsigned loopDepth,
1271 const ComputationSliceState *sliceState,
1272 bool addMemRefDimBounds, bool dropLocalVars,
1273 bool dropOuterIvs) {
1274 assert((isa<AffineReadOpInterface, AffineWriteOpInterface>(op)) &&
1275 "affine read/write op expected");
1276
1277 MemRefAccess access(op);
1278 memref = access.memref;
1279 write = access.isStore();
1280
1281 unsigned rank = access.getRank();
1282
1283 LDBG() << "MemRefRegion::compute: " << *op << " depth: " << loopDepth;
1284
1285 // 0-d memrefs.
1286 if (rank == 0) {
1287 SmallVector<Value, 4> ivs;
1288 getAffineIVs(op&: *op, ivs);
1289 assert(loopDepth <= ivs.size() && "invalid 'loopDepth'");
1290 // The first 'loopDepth' IVs are symbols for this region.
1291 ivs.resize(N: loopDepth);
1292 // A 0-d memref has a 0-d region.
1293 cst = FlatAffineValueConstraints(rank, loopDepth, /*numLocals=*/0, ivs);
1294 return success();
1295 }
1296
1297 // Build the constraints for this region.
1298 AffineValueMap accessValueMap;
1299 access.getAccessMap(accessMap: &accessValueMap);
1300 AffineMap accessMap = accessValueMap.getAffineMap();
1301
1302 unsigned numDims = accessMap.getNumDims();
1303 unsigned numSymbols = accessMap.getNumSymbols();
1304 unsigned numOperands = accessValueMap.getNumOperands();
1305 // Merge operands with slice operands.
1306 SmallVector<Value, 4> operands;
1307 operands.resize(N: numOperands);
1308 for (unsigned i = 0; i < numOperands; ++i)
1309 operands[i] = accessValueMap.getOperand(i);
1310
1311 if (sliceState != nullptr) {
1312 operands.reserve(N: operands.size() + sliceState->lbOperands[0].size());
1313 // Append slice operands to 'operands' as symbols.
1314 for (auto extraOperand : sliceState->lbOperands[0]) {
1315 if (!llvm::is_contained(Range&: operands, Element: extraOperand)) {
1316 operands.push_back(Elt: extraOperand);
1317 numSymbols++;
1318 }
1319 }
1320 }
1321 // We'll first associate the dims and symbols of the access map to the dims
1322 // and symbols resp. of cst. This will change below once cst is
1323 // fully constructed out.
1324 cst = FlatAffineValueConstraints(numDims, numSymbols, 0, operands);
1325
1326 // Add equality constraints.
1327 // Add inequalities for loop lower/upper bounds.
1328 for (unsigned i = 0; i < numDims + numSymbols; ++i) {
1329 auto operand = operands[i];
1330 if (auto affineFor = getForInductionVarOwner(val: operand)) {
1331 // Note that cst can now have more dimensions than accessMap if the
1332 // bounds expressions involve outer loops or other symbols.
1333 // TODO: rewrite this to use getInstIndexSet; this way
1334 // conditionals will be handled when the latter supports it.
1335 if (failed(Result: cst.addAffineForOpDomain(forOp: affineFor)))
1336 return failure();
1337 } else if (auto parallelOp = getAffineParallelInductionVarOwner(val: operand)) {
1338 if (failed(Result: cst.addAffineParallelOpDomain(parallelOp)))
1339 return failure();
1340 } else if (isValidSymbol(value: operand)) {
1341 // Check if the symbol is a constant.
1342 Value symbol = operand;
1343 if (auto constVal = getConstantIntValue(ofr: symbol))
1344 cst.addBound(type: BoundType::EQ, val: symbol, value: constVal.value());
1345 } else {
1346 LDBG() << "unknown affine dimensional value";
1347 return failure();
1348 }
1349 }
1350
1351 // Add lower/upper bounds on loop IVs using bounds from 'sliceState'.
1352 if (sliceState != nullptr) {
1353 // Add dim and symbol slice operands.
1354 for (auto operand : sliceState->lbOperands[0]) {
1355 if (failed(Result: cst.addInductionVarOrTerminalSymbol(val: operand)))
1356 return failure();
1357 }
1358 // Add upper/lower bounds from 'sliceState' to 'cst'.
1359 LogicalResult ret =
1360 cst.addSliceBounds(values: sliceState->ivs, lbMaps: sliceState->lbs, ubMaps: sliceState->ubs,
1361 operands: sliceState->lbOperands[0]);
1362 assert(succeeded(ret) &&
1363 "should not fail as we never have semi-affine slice maps");
1364 (void)ret;
1365 }
1366
1367 // Add access function equalities to connect loop IVs to data dimensions.
1368 if (failed(Result: cst.composeMap(vMap: &accessValueMap))) {
1369 op->emitError(message: "getMemRefRegion: compose affine map failed");
1370 LDBG() << "Access map: " << accessValueMap.getAffineMap();
1371 return failure();
1372 }
1373
1374 // Set all variables appearing after the first 'rank' variables as
1375 // symbolic variables - so that the ones corresponding to the memref
1376 // dimensions are the dimensional variables for the memref region.
1377 cst.setDimSymbolSeparation(cst.getNumDimAndSymbolVars() - rank);
1378
1379 // Eliminate any loop IVs other than the outermost 'loopDepth' IVs, on which
1380 // this memref region is symbolic.
1381 SmallVector<Value, 4> enclosingIVs;
1382 getAffineIVs(op&: *op, ivs&: enclosingIVs);
1383 assert(loopDepth <= enclosingIVs.size() && "invalid loop depth");
1384 enclosingIVs.resize(N: loopDepth);
1385 SmallVector<Value, 4> vars;
1386 cst.getValues(start: cst.getNumDimVars(), end: cst.getNumDimAndSymbolVars(), values: &vars);
1387 for (auto en : llvm::enumerate(First&: vars)) {
1388 if ((isAffineInductionVar(val: en.value())) &&
1389 !llvm::is_contained(Range&: enclosingIVs, Element: en.value())) {
1390 if (dropOuterIvs) {
1391 cst.projectOut(val: en.value());
1392 } else {
1393 unsigned varPosition;
1394 cst.findVar(val: en.value(), pos: &varPosition);
1395 auto varKind = cst.getVarKindAt(pos: varPosition);
1396 varPosition -= cst.getNumDimVars();
1397 cst.convertToLocal(kind: varKind, varStart: varPosition, varLimit: varPosition + 1);
1398 }
1399 }
1400 }
1401
1402 // Project out any local variables (these would have been added for any
1403 // mod/divs) if specified.
1404 if (dropLocalVars)
1405 cst.projectOut(pos: cst.getNumDimAndSymbolVars(), num: cst.getNumLocalVars());
1406
1407 // Constant fold any symbolic variables.
1408 cst.constantFoldVarRange(/*pos=*/cst.getNumDimVars(),
1409 /*num=*/cst.getNumSymbolVars());
1410
1411 assert(cst.getNumDimVars() == rank && "unexpected MemRefRegion format");
1412
1413 // Add upper/lower bounds for each memref dimension with static size
1414 // to guard against potential over-approximation from projection.
1415 // TODO: Support dynamic memref dimensions.
1416 if (addMemRefDimBounds) {
1417 auto memRefType = cast<MemRefType>(Val: memref.getType());
1418 for (unsigned r = 0; r < rank; r++) {
1419 cst.addBound(type: BoundType::LB, /*pos=*/r, /*value=*/0);
1420 if (memRefType.isDynamicDim(idx: r))
1421 continue;
1422 cst.addBound(type: BoundType::UB, /*pos=*/r, value: memRefType.getDimSize(idx: r) - 1);
1423 }
1424 }
1425 cst.removeTrivialRedundancy();
1426
1427 LDBG() << "Memory region: " << cst;
1428 return success();
1429}
1430
1431std::optional<int64_t>
1432mlir::affine::getMemRefIntOrFloatEltSizeInBytes(MemRefType memRefType) {
1433 auto elementType = memRefType.getElementType();
1434
1435 unsigned sizeInBits;
1436 if (elementType.isIntOrFloat()) {
1437 sizeInBits = elementType.getIntOrFloatBitWidth();
1438 } else if (auto vectorType = dyn_cast<VectorType>(Val&: elementType)) {
1439 if (vectorType.getElementType().isIntOrFloat())
1440 sizeInBits =
1441 vectorType.getElementTypeBitWidth() * vectorType.getNumElements();
1442 else
1443 return std::nullopt;
1444 } else {
1445 return std::nullopt;
1446 }
1447 return llvm::divideCeil(Numerator: sizeInBits, Denominator: 8);
1448}
1449
1450// Returns the size of the region.
1451std::optional<int64_t> MemRefRegion::getRegionSize() {
1452 auto memRefType = cast<MemRefType>(Val: memref.getType());
1453
1454 if (!memRefType.getLayout().isIdentity()) {
1455 LDBG() << "Non-identity layout map not yet supported";
1456 return false;
1457 }
1458
1459 // Compute the extents of the buffer.
1460 std::optional<int64_t> numElements = getConstantBoundingSizeAndShape();
1461 if (!numElements) {
1462 LDBG() << "Dynamic shapes not yet supported";
1463 return std::nullopt;
1464 }
1465 auto eltSize = getMemRefIntOrFloatEltSizeInBytes(memRefType);
1466 if (!eltSize)
1467 return std::nullopt;
1468 return *eltSize * *numElements;
1469}
1470
1471/// Returns the size of memref data in bytes if it's statically shaped,
1472/// std::nullopt otherwise. If the element of the memref has vector type, takes
1473/// into account size of the vector as well.
1474// TODO: improve/complete this when we have target data.
1475std::optional<uint64_t>
1476mlir::affine::getIntOrFloatMemRefSizeInBytes(MemRefType memRefType) {
1477 if (!memRefType.hasStaticShape())
1478 return std::nullopt;
1479 auto elementType = memRefType.getElementType();
1480 if (!elementType.isIntOrFloat() && !isa<VectorType>(Val: elementType))
1481 return std::nullopt;
1482
1483 auto sizeInBytes = getMemRefIntOrFloatEltSizeInBytes(memRefType);
1484 if (!sizeInBytes)
1485 return std::nullopt;
1486 for (unsigned i = 0, e = memRefType.getRank(); i < e; i++) {
1487 sizeInBytes = *sizeInBytes * memRefType.getDimSize(idx: i);
1488 }
1489 return sizeInBytes;
1490}
1491
1492template <typename LoadOrStoreOp>
1493LogicalResult mlir::affine::boundCheckLoadOrStoreOp(LoadOrStoreOp loadOrStoreOp,
1494 bool emitError) {
1495 static_assert(llvm::is_one_of<LoadOrStoreOp, AffineReadOpInterface,
1496 AffineWriteOpInterface>::value,
1497 "argument should be either a AffineReadOpInterface or a "
1498 "AffineWriteOpInterface");
1499
1500 Operation *op = loadOrStoreOp.getOperation();
1501 MemRefRegion region(op->getLoc());
1502 if (failed(Result: region.compute(op, /*loopDepth=*/0, /*sliceState=*/nullptr,
1503 /*addMemRefDimBounds=*/false)))
1504 return success();
1505
1506 LDBG() << "Memory region: " << region.getConstraints();
1507
1508 bool outOfBounds = false;
1509 unsigned rank = loadOrStoreOp.getMemRefType().getRank();
1510
1511 // For each dimension, check for out of bounds.
1512 for (unsigned r = 0; r < rank; r++) {
1513 FlatAffineValueConstraints ucst(*region.getConstraints());
1514
1515 // Intersect memory region with constraint capturing out of bounds (both out
1516 // of upper and out of lower), and check if the constraint system is
1517 // feasible. If it is, there is at least one point out of bounds.
1518 SmallVector<int64_t, 4> ineq(rank + 1, 0);
1519 int64_t dimSize = loadOrStoreOp.getMemRefType().getDimSize(r);
1520 // TODO: handle dynamic dim sizes.
1521 if (dimSize == -1)
1522 continue;
1523
1524 // Check for overflow: d_i >= memref dim size.
1525 ucst.addBound(type: BoundType::LB, pos: r, value: dimSize);
1526 outOfBounds = !ucst.isEmpty();
1527 if (outOfBounds && emitError) {
1528 loadOrStoreOp.emitOpError()
1529 << "memref out of upper bound access along dimension #" << (r + 1);
1530 }
1531
1532 // Check for a negative index.
1533 FlatAffineValueConstraints lcst(*region.getConstraints());
1534 llvm::fill(Range&: ineq, Value: 0);
1535 // d_i <= -1;
1536 lcst.addBound(type: BoundType::UB, pos: r, value: -1);
1537 outOfBounds = !lcst.isEmpty();
1538 if (outOfBounds && emitError) {
1539 loadOrStoreOp.emitOpError()
1540 << "memref out of lower bound access along dimension #" << (r + 1);
1541 }
1542 }
1543 return failure(IsFailure: outOfBounds);
1544}
1545
1546// Explicitly instantiate the template so that the compiler knows we need them!
1547template LogicalResult
1548mlir::affine::boundCheckLoadOrStoreOp(AffineReadOpInterface loadOp,
1549 bool emitError);
1550template LogicalResult
1551mlir::affine::boundCheckLoadOrStoreOp(AffineWriteOpInterface storeOp,
1552 bool emitError);
1553
1554// Returns in 'positions' the Block positions of 'op' in each ancestor
1555// Block from the Block containing operation, stopping at 'limitBlock'.
1556static void findInstPosition(Operation *op, Block *limitBlock,
1557 SmallVectorImpl<unsigned> *positions) {
1558 Block *block = op->getBlock();
1559 while (block != limitBlock) {
1560 // FIXME: This algorithm is unnecessarily O(n) and should be improved to not
1561 // rely on linear scans.
1562 int instPosInBlock = std::distance(first: block->begin(), last: op->getIterator());
1563 positions->push_back(Elt: instPosInBlock);
1564 op = block->getParentOp();
1565 block = op->getBlock();
1566 }
1567 std::reverse(first: positions->begin(), last: positions->end());
1568}
1569
1570// Returns the Operation in a possibly nested set of Blocks, where the
1571// position of the operation is represented by 'positions', which has a
1572// Block position for each level of nesting.
1573static Operation *getInstAtPosition(ArrayRef<unsigned> positions,
1574 unsigned level, Block *block) {
1575 unsigned i = 0;
1576 for (auto &op : *block) {
1577 if (i != positions[level]) {
1578 ++i;
1579 continue;
1580 }
1581 if (level == positions.size() - 1)
1582 return &op;
1583 if (auto childAffineForOp = dyn_cast<AffineForOp>(Val&: op))
1584 return getInstAtPosition(positions, level: level + 1,
1585 block: childAffineForOp.getBody());
1586
1587 for (auto &region : op.getRegions()) {
1588 for (auto &b : region)
1589 if (auto *ret = getInstAtPosition(positions, level: level + 1, block: &b))
1590 return ret;
1591 }
1592 return nullptr;
1593 }
1594 return nullptr;
1595}
1596
1597// Adds loop IV bounds to 'cst' for loop IVs not found in 'ivs'.
1598static LogicalResult addMissingLoopIVBounds(SmallPtrSet<Value, 8> &ivs,
1599 FlatAffineValueConstraints *cst) {
1600 for (unsigned i = 0, e = cst->getNumDimVars(); i < e; ++i) {
1601 auto value = cst->getValue(pos: i);
1602 if (ivs.count(Ptr: value) == 0) {
1603 assert(isAffineForInductionVar(value));
1604 auto loop = getForInductionVarOwner(val: value);
1605 if (failed(Result: cst->addAffineForOpDomain(forOp: loop)))
1606 return failure();
1607 }
1608 }
1609 return success();
1610}
1611
1612/// Returns the innermost common loop depth for the set of operations in 'ops'.
1613// TODO: Move this to LoopUtils.
1614unsigned mlir::affine::getInnermostCommonLoopDepth(
1615 ArrayRef<Operation *> ops, SmallVectorImpl<AffineForOp> *surroundingLoops) {
1616 unsigned numOps = ops.size();
1617 assert(numOps > 0 && "Expected at least one operation");
1618
1619 std::vector<SmallVector<AffineForOp, 4>> loops(numOps);
1620 unsigned loopDepthLimit = std::numeric_limits<unsigned>::max();
1621 for (unsigned i = 0; i < numOps; ++i) {
1622 getAffineForIVs(op&: *ops[i], loops: &loops[i]);
1623 loopDepthLimit = std::min(a: loopDepthLimit, b: (unsigned)loops[i].size());
1624 }
1625
1626 unsigned loopDepth = 0;
1627 for (unsigned d = 0; d < loopDepthLimit; ++d) {
1628 unsigned i;
1629 for (i = 1; i < numOps; ++i) {
1630 if (loops[i - 1][d] != loops[i][d])
1631 return loopDepth;
1632 }
1633 if (surroundingLoops)
1634 surroundingLoops->push_back(Elt: loops[i - 1][d]);
1635 ++loopDepth;
1636 }
1637 return loopDepth;
1638}
1639
1640/// Computes in 'sliceUnion' the union of all slice bounds computed at
1641/// 'loopDepth' between all dependent pairs of ops in 'opsA' and 'opsB', and
1642/// then verifies if it is valid. Returns 'SliceComputationResult::Success' if
1643/// union was computed correctly, an appropriate failure otherwise.
1644SliceComputationResult
1645mlir::affine::computeSliceUnion(ArrayRef<Operation *> opsA,
1646 ArrayRef<Operation *> opsB, unsigned loopDepth,
1647 unsigned numCommonLoops, bool isBackwardSlice,
1648 ComputationSliceState *sliceUnion) {
1649 // Compute the union of slice bounds between all pairs in 'opsA' and
1650 // 'opsB' in 'sliceUnionCst'.
1651 FlatAffineValueConstraints sliceUnionCst;
1652 assert(sliceUnionCst.getNumDimAndSymbolVars() == 0);
1653 std::vector<std::pair<Operation *, Operation *>> dependentOpPairs;
1654 MemRefAccess srcAccess;
1655 MemRefAccess dstAccess;
1656 for (Operation *a : opsA) {
1657 srcAccess = MemRefAccess(a);
1658 for (Operation *b : opsB) {
1659 dstAccess = MemRefAccess(b);
1660 if (srcAccess.memref != dstAccess.memref)
1661 continue;
1662 // Check if 'loopDepth' exceeds nesting depth of src/dst ops.
1663 if ((!isBackwardSlice && loopDepth > getNestingDepth(op: a)) ||
1664 (isBackwardSlice && loopDepth > getNestingDepth(op: b))) {
1665 LDBG() << "Invalid loop depth";
1666 return SliceComputationResult::GenericFailure;
1667 }
1668
1669 bool readReadAccesses = isa<AffineReadOpInterface>(Val: srcAccess.opInst) &&
1670 isa<AffineReadOpInterface>(Val: dstAccess.opInst);
1671 FlatAffineValueConstraints dependenceConstraints;
1672 // Check dependence between 'srcAccess' and 'dstAccess'.
1673 DependenceResult result = checkMemrefAccessDependence(
1674 srcAccess, dstAccess, /*loopDepth=*/numCommonLoops + 1,
1675 dependenceConstraints: &dependenceConstraints, /*dependenceComponents=*/nullptr,
1676 /*allowRAR=*/readReadAccesses);
1677 if (result.value == DependenceResult::Failure) {
1678 LDBG() << "Dependence check failed";
1679 return SliceComputationResult::GenericFailure;
1680 }
1681 if (result.value == DependenceResult::NoDependence)
1682 continue;
1683 dependentOpPairs.emplace_back(args&: a, args&: b);
1684
1685 // Compute slice bounds for 'srcAccess' and 'dstAccess'.
1686 ComputationSliceState tmpSliceState;
1687 getComputationSliceState(depSourceOp: a, depSinkOp: b, dependenceConstraints, loopDepth,
1688 isBackwardSlice, sliceState: &tmpSliceState);
1689
1690 if (sliceUnionCst.getNumDimAndSymbolVars() == 0) {
1691 // Initialize 'sliceUnionCst' with the bounds computed in previous step.
1692 if (failed(Result: tmpSliceState.getAsConstraints(cst: &sliceUnionCst))) {
1693 LDBG() << "Unable to compute slice bound constraints";
1694 return SliceComputationResult::GenericFailure;
1695 }
1696 assert(sliceUnionCst.getNumDimAndSymbolVars() > 0);
1697 continue;
1698 }
1699
1700 // Compute constraints for 'tmpSliceState' in 'tmpSliceCst'.
1701 FlatAffineValueConstraints tmpSliceCst;
1702 if (failed(Result: tmpSliceState.getAsConstraints(cst: &tmpSliceCst))) {
1703 LDBG() << "Unable to compute slice bound constraints";
1704 return SliceComputationResult::GenericFailure;
1705 }
1706
1707 // Align coordinate spaces of 'sliceUnionCst' and 'tmpSliceCst' if needed.
1708 if (!sliceUnionCst.areVarsAlignedWithOther(other: tmpSliceCst)) {
1709
1710 // Pre-constraint var alignment: record loop IVs used in each constraint
1711 // system.
1712 SmallPtrSet<Value, 8> sliceUnionIVs;
1713 for (unsigned k = 0, l = sliceUnionCst.getNumDimVars(); k < l; ++k)
1714 sliceUnionIVs.insert(Ptr: sliceUnionCst.getValue(pos: k));
1715 SmallPtrSet<Value, 8> tmpSliceIVs;
1716 for (unsigned k = 0, l = tmpSliceCst.getNumDimVars(); k < l; ++k)
1717 tmpSliceIVs.insert(Ptr: tmpSliceCst.getValue(pos: k));
1718
1719 sliceUnionCst.mergeAndAlignVarsWithOther(/*offset=*/0, other: &tmpSliceCst);
1720
1721 // Post-constraint var alignment: add loop IV bounds missing after
1722 // var alignment to constraint systems. This can occur if one constraint
1723 // system uses an loop IV that is not used by the other. The call
1724 // to unionBoundingBox below expects constraints for each Loop IV, even
1725 // if they are the unsliced full loop bounds added here.
1726 if (failed(Result: addMissingLoopIVBounds(ivs&: sliceUnionIVs, cst: &sliceUnionCst)))
1727 return SliceComputationResult::GenericFailure;
1728 if (failed(Result: addMissingLoopIVBounds(ivs&: tmpSliceIVs, cst: &tmpSliceCst)))
1729 return SliceComputationResult::GenericFailure;
1730 }
1731 // Compute union bounding box of 'sliceUnionCst' and 'tmpSliceCst'.
1732 if (sliceUnionCst.getNumLocalVars() > 0 ||
1733 tmpSliceCst.getNumLocalVars() > 0 ||
1734 failed(Result: sliceUnionCst.unionBoundingBox(other: tmpSliceCst))) {
1735 LDBG() << "Unable to compute union bounding box of slice bounds";
1736 return SliceComputationResult::GenericFailure;
1737 }
1738 }
1739 }
1740
1741 // Empty union.
1742 if (sliceUnionCst.getNumDimAndSymbolVars() == 0) {
1743 LDBG() << "empty slice union - unexpected";
1744 return SliceComputationResult::GenericFailure;
1745 }
1746
1747 // Gather loops surrounding ops from loop nest where slice will be inserted.
1748 SmallVector<Operation *, 4> ops;
1749 for (auto &dep : dependentOpPairs) {
1750 ops.push_back(Elt: isBackwardSlice ? dep.second : dep.first);
1751 }
1752 SmallVector<AffineForOp, 4> surroundingLoops;
1753 unsigned innermostCommonLoopDepth =
1754 getInnermostCommonLoopDepth(ops, surroundingLoops: &surroundingLoops);
1755 if (loopDepth > innermostCommonLoopDepth) {
1756 LDBG() << "Exceeds max loop depth";
1757 return SliceComputationResult::GenericFailure;
1758 }
1759
1760 // Store 'numSliceLoopIVs' before converting dst loop IVs to dims.
1761 unsigned numSliceLoopIVs = sliceUnionCst.getNumDimVars();
1762
1763 // Convert any dst loop IVs which are symbol variables to dim variables.
1764 sliceUnionCst.convertLoopIVSymbolsToDims();
1765 sliceUnion->clearBounds();
1766 sliceUnion->lbs.resize(N: numSliceLoopIVs, NV: AffineMap());
1767 sliceUnion->ubs.resize(N: numSliceLoopIVs, NV: AffineMap());
1768
1769 // Get slice bounds from slice union constraints 'sliceUnionCst'.
1770 sliceUnionCst.getSliceBounds(/*offset=*/0, num: numSliceLoopIVs,
1771 context: opsA[0]->getContext(), lbMaps: &sliceUnion->lbs,
1772 ubMaps: &sliceUnion->ubs, /*closedUb=*/closedUB: false,
1773 /*allowMultiResultUb=*/allowMultiResultUB: true);
1774
1775 // Add slice bound operands of union.
1776 SmallVector<Value, 4> sliceBoundOperands;
1777 sliceUnionCst.getValues(start: numSliceLoopIVs,
1778 end: sliceUnionCst.getNumDimAndSymbolVars(),
1779 values: &sliceBoundOperands);
1780
1781 // Copy src loop IVs from 'sliceUnionCst' to 'sliceUnion'.
1782 sliceUnion->ivs.clear();
1783 sliceUnionCst.getValues(start: 0, end: numSliceLoopIVs, values: &sliceUnion->ivs);
1784
1785 // Set loop nest insertion point to block start at 'loopDepth' for forward
1786 // slices, while at the end for backward slices.
1787 sliceUnion->insertPoint =
1788 isBackwardSlice
1789 ? surroundingLoops[loopDepth - 1].getBody()->begin()
1790 : std::prev(x: surroundingLoops[loopDepth - 1].getBody()->end());
1791
1792 // Give each bound its own copy of 'sliceBoundOperands' for subsequent
1793 // canonicalization.
1794 sliceUnion->lbOperands.resize(new_size: numSliceLoopIVs, x: sliceBoundOperands);
1795 sliceUnion->ubOperands.resize(new_size: numSliceLoopIVs, x: sliceBoundOperands);
1796
1797 // Check if the slice computed is valid. Return success only if it is verified
1798 // that the slice is valid, otherwise return appropriate failure status.
1799 std::optional<bool> isSliceValid = sliceUnion->isSliceValid();
1800 if (!isSliceValid) {
1801 LDBG() << "Cannot determine if the slice is valid";
1802 return SliceComputationResult::GenericFailure;
1803 }
1804 if (!*isSliceValid)
1805 return SliceComputationResult::IncorrectSliceFailure;
1806
1807 return SliceComputationResult::Success;
1808}
1809
1810/// Returns the number of iterations the slice bounded below by `lbMap` and
1811/// above by `ubMap` runs for, where that is a constant.
1812///
1813/// An upper bound of several results is the min of them, so each result taken
1814/// against the lower bound bounds the count from above and the smallest of
1815/// those that comes out constant is the tightest constant bound there is. A
1816/// tiled loop clamped at the end of the data has exactly this shape --
1817/// `min(%i * 64 + 64, 1000)` over `%i * 64` -- where the tile-relative result
1818/// gives the 64 and the extent gives nothing constant at all.
1819static std::optional<uint64_t> getConstDifference(AffineMap lbMap,
1820 AffineMap ubMap) {
1821 assert(lbMap.getNumResults() == 1 && "expected single result lower bound");
1822 assert(ubMap.getNumResults() >= 1 && "expected at least one upper bound");
1823 assert(lbMap.getNumDims() == ubMap.getNumDims());
1824 assert(lbMap.getNumSymbols() == ubMap.getNumSymbols());
1825 AffineExpr lbExpr(lbMap.getResult(idx: 0));
1826 std::optional<uint64_t> tripCount;
1827 for (AffineExpr ubExpr : ubMap.getResults()) {
1828 AffineExpr loopSpanExpr = simplifyAffineExpr(
1829 expr: ubExpr - lbExpr, numDims: lbMap.getNumDims(), numSymbols: lbMap.getNumSymbols());
1830 auto cExpr = dyn_cast<AffineConstantExpr>(Val&: loopSpanExpr);
1831 if (!cExpr)
1832 continue;
1833 if (cExpr.getValue() < 0)
1834 return 0;
1835 tripCount =
1836 std::min(a: tripCount.value_or(u: std::numeric_limits<uint64_t>::max()),
1837 b: (uint64_t)cExpr.getValue());
1838 }
1839 return tripCount;
1840}
1841
1842// Builds a map 'tripCountMap' from AffineForOp to constant trip count for loop
1843// nest surrounding represented by slice loop bounds in 'slice'. Returns true
1844// on success, false otherwise (if a non-constant trip count was encountered).
1845// TODO: Make this work with non-unit step loops.
1846bool mlir::affine::buildSliceTripCountMap(
1847 const ComputationSliceState &slice,
1848 llvm::SmallDenseMap<Operation *, uint64_t, 8> *tripCountMap) {
1849 unsigned numSrcLoopIVs = slice.ivs.size();
1850 // Populate map from AffineForOp -> trip count
1851 for (unsigned i = 0; i < numSrcLoopIVs; ++i) {
1852 AffineForOp forOp = getForInductionVarOwner(val: slice.ivs[i]);
1853 auto *op = forOp.getOperation();
1854 AffineMap lbMap = slice.lbs[i];
1855 AffineMap ubMap = slice.ubs[i];
1856 // If lower or upper bound maps are null or provide no results, it implies
1857 // that source loop was not at all sliced, and the entire loop will be a
1858 // part of the slice.
1859 if (!lbMap || lbMap.getNumResults() == 0 || !ubMap ||
1860 ubMap.getNumResults() == 0) {
1861 // The iteration of src loop IV 'i' was not sliced. Use full loop bounds.
1862 if (forOp.hasConstantLowerBound() && forOp.hasConstantUpperBound()) {
1863 (*tripCountMap)[op] =
1864 forOp.getConstantUpperBound() - forOp.getConstantLowerBound();
1865 continue;
1866 }
1867 std::optional<APInt> maybeConstTripCount = forOp.getStaticTripCount();
1868 if (maybeConstTripCount.has_value()) {
1869 (*tripCountMap)[op] = maybeConstTripCount->getZExtValue();
1870 continue;
1871 }
1872 return false;
1873 }
1874 std::optional<uint64_t> tripCount = getConstDifference(lbMap, ubMap);
1875 // Slice bounds are created with a constant ub - lb difference.
1876 if (!tripCount.has_value())
1877 return false;
1878 (*tripCountMap)[op] = *tripCount;
1879 }
1880 return true;
1881}
1882
1883// Return the number of iterations in the given slice.
1884uint64_t mlir::affine::getSliceIterationCount(
1885 const llvm::SmallDenseMap<Operation *, uint64_t, 8> &sliceTripCountMap) {
1886 uint64_t iterCount = 1;
1887 for (const auto &count : sliceTripCountMap) {
1888 iterCount *= count.second;
1889 }
1890 return iterCount;
1891}
1892
1893const char *const kSliceFusionBarrierAttrName = "slice_fusion_barrier";
1894// Computes slice bounds by projecting out any loop IVs from
1895// 'dependenceConstraints' at depth greater than 'loopDepth', and computes slice
1896// bounds in 'sliceState' which represent the one loop nest's IVs in terms of
1897// the other loop nest's IVs, symbols and constants (using 'isBackwardsSlice').
1898void mlir::affine::getComputationSliceState(
1899 Operation *depSourceOp, Operation *depSinkOp,
1900 const FlatAffineValueConstraints &dependenceConstraints, unsigned loopDepth,
1901 bool isBackwardSlice, ComputationSliceState *sliceState) {
1902 // Get loop nest surrounding src operation.
1903 SmallVector<AffineForOp, 4> srcLoopIVs;
1904 getAffineForIVs(op&: *depSourceOp, loops: &srcLoopIVs);
1905 unsigned numSrcLoopIVs = srcLoopIVs.size();
1906
1907 // Get loop nest surrounding dst operation.
1908 SmallVector<AffineForOp, 4> dstLoopIVs;
1909 getAffineForIVs(op&: *depSinkOp, loops: &dstLoopIVs);
1910 unsigned numDstLoopIVs = dstLoopIVs.size();
1911
1912 assert((!isBackwardSlice && loopDepth <= numSrcLoopIVs) ||
1913 (isBackwardSlice && loopDepth <= numDstLoopIVs));
1914
1915 // Project out dimensions other than those up to 'loopDepth'.
1916 unsigned pos = isBackwardSlice ? numSrcLoopIVs + loopDepth : loopDepth;
1917 unsigned num =
1918 isBackwardSlice ? numDstLoopIVs - loopDepth : numSrcLoopIVs - loopDepth;
1919 FlatAffineValueConstraints sliceCst(dependenceConstraints);
1920 sliceCst.projectOut(pos, num);
1921
1922 // Add slice loop IV values to 'sliceState'.
1923 unsigned offset = isBackwardSlice ? 0 : loopDepth;
1924 unsigned numSliceLoopIVs = isBackwardSlice ? numSrcLoopIVs : numDstLoopIVs;
1925 sliceCst.getValues(start: offset, end: offset + numSliceLoopIVs, values: &sliceState->ivs);
1926
1927 // Set up lower/upper bound affine maps for the slice.
1928 sliceState->lbs.resize(N: numSliceLoopIVs, NV: AffineMap());
1929 sliceState->ubs.resize(N: numSliceLoopIVs, NV: AffineMap());
1930
1931 // Get bounds for slice IVs in terms of other IVs, symbols, and constants.
1932 sliceCst.getSliceBounds(offset, num: numSliceLoopIVs, context: depSourceOp->getContext(),
1933 lbMaps: &sliceState->lbs, ubMaps: &sliceState->ubs,
1934 /*closedUb=*/closedUB: false, /*allowMultiResultUb=*/allowMultiResultUB: true);
1935
1936 // Set up bound operands for the slice's lower and upper bounds.
1937 SmallVector<Value, 4> sliceBoundOperands;
1938 unsigned numDimsAndSymbols = sliceCst.getNumDimAndSymbolVars();
1939 for (unsigned i = 0; i < numDimsAndSymbols; ++i) {
1940 if (i < offset || i >= offset + numSliceLoopIVs)
1941 sliceBoundOperands.push_back(Elt: sliceCst.getValue(pos: i));
1942 }
1943
1944 // Give each bound its own copy of 'sliceBoundOperands' for subsequent
1945 // canonicalization.
1946 sliceState->lbOperands.resize(new_size: numSliceLoopIVs, x: sliceBoundOperands);
1947 sliceState->ubOperands.resize(new_size: numSliceLoopIVs, x: sliceBoundOperands);
1948
1949 // Set destination loop nest insertion point to block start at 'dstLoopDepth'.
1950 sliceState->insertPoint =
1951 isBackwardSlice ? dstLoopIVs[loopDepth - 1].getBody()->begin()
1952 : std::prev(x: srcLoopIVs[loopDepth - 1].getBody()->end());
1953
1954 llvm::SmallDenseSet<Value, 8> sequentialLoops;
1955 if (isa<AffineReadOpInterface>(Val: depSourceOp) &&
1956 isa<AffineReadOpInterface>(Val: depSinkOp)) {
1957 // For read-read access pairs, clear any slice bounds on sequential loops.
1958 // Get sequential loops in loop nest rooted at 'srcLoopIVs[0]'.
1959 getSequentialLoops(forOp: isBackwardSlice ? srcLoopIVs[0] : dstLoopIVs[0],
1960 sequentialLoops: &sequentialLoops);
1961 }
1962 auto getSliceLoop = [&](unsigned i) {
1963 return isBackwardSlice ? srcLoopIVs[i] : dstLoopIVs[i];
1964 };
1965 auto isInnermostInsertion = [&]() {
1966 return (isBackwardSlice ? loopDepth >= srcLoopIVs.size()
1967 : loopDepth >= dstLoopIVs.size());
1968 };
1969 llvm::SmallDenseMap<Operation *, uint64_t, 8> sliceTripCountMap;
1970 auto srcIsUnitSlice = [&]() {
1971 return (buildSliceTripCountMap(slice: *sliceState, tripCountMap: &sliceTripCountMap) &&
1972 (getSliceIterationCount(sliceTripCountMap) == 1));
1973 };
1974 // Clear all sliced loop bounds beginning at the first sequential loop, or
1975 // first loop with a slice fusion barrier attribute..
1976
1977 for (unsigned i = 0; i < numSliceLoopIVs; ++i) {
1978 Value iv = getSliceLoop(i).getInductionVar();
1979 if (sequentialLoops.count(V: iv) == 0 &&
1980 getSliceLoop(i)->getDiscardableAttr(name: kSliceFusionBarrierAttrName) ==
1981 nullptr)
1982 continue;
1983 // Skip reset of bounds of reduction loop inserted in the destination loop
1984 // that meets the following conditions:
1985 // 1. Slice is single trip count.
1986 // 2. Loop bounds of the source and destination match.
1987 // 3. Is being inserted at the innermost insertion point.
1988 std::optional<bool> isMaximal = sliceState->isMaximal();
1989 if (isLoopParallelAndContainsReduction(forOp: getSliceLoop(i)) &&
1990 isInnermostInsertion() && srcIsUnitSlice() && isMaximal && *isMaximal)
1991 continue;
1992 for (unsigned j = i; j < numSliceLoopIVs; ++j) {
1993 sliceState->lbs[j] = AffineMap();
1994 sliceState->ubs[j] = AffineMap();
1995 }
1996 break;
1997 }
1998}
1999
2000/// Creates a computation slice of the loop nest surrounding 'srcOpInst',
2001/// updates the slice loop bounds with any non-null bound maps specified in
2002/// 'sliceState', and inserts this slice into the loop nest surrounding
2003/// 'dstOpInst' at loop depth 'dstLoopDepth'.
2004// TODO: extend the slicing utility to compute slices that
2005// aren't necessarily a one-to-one relation b/w the source and destination. The
2006// relation between the source and destination could be many-to-many in general.
2007// TODO: the slice computation is incorrect in the cases
2008// where the dependence from the source to the destination does not cover the
2009// entire destination index set. Subtract out the dependent destination
2010// iterations from destination index set and check for emptiness --- this is one
2011// solution.
2012AffineForOp mlir::affine::insertBackwardComputationSlice(
2013 Operation *srcOpInst, Operation *dstOpInst, unsigned dstLoopDepth,
2014 ComputationSliceState *sliceState) {
2015 // Get loop nest surrounding src operation.
2016 SmallVector<AffineForOp, 4> srcLoopIVs;
2017 getAffineForIVs(op&: *srcOpInst, loops: &srcLoopIVs);
2018 unsigned numSrcLoopIVs = srcLoopIVs.size();
2019
2020 // Get loop nest surrounding dst operation.
2021 SmallVector<AffineForOp, 4> dstLoopIVs;
2022 getAffineForIVs(op&: *dstOpInst, loops: &dstLoopIVs);
2023 unsigned dstLoopIVsSize = dstLoopIVs.size();
2024 if (dstLoopDepth > dstLoopIVsSize) {
2025 dstOpInst->emitError(message: "invalid destination loop depth");
2026 return AffineForOp();
2027 }
2028
2029 // Find the op block positions of 'srcOpInst' within 'srcLoopIVs'.
2030 SmallVector<unsigned, 4> positions;
2031 // TODO: This code is incorrect since srcLoopIVs can be 0-d.
2032 findInstPosition(op: srcOpInst, limitBlock: srcLoopIVs[0]->getBlock(), positions: &positions);
2033
2034 // Clone src loop nest and insert it a the beginning of the operation block
2035 // of the loop at 'dstLoopDepth' in 'dstLoopIVs'.
2036 auto dstAffineForOp = dstLoopIVs[dstLoopDepth - 1];
2037 OpBuilder b(dstAffineForOp.getBody(), dstAffineForOp.getBody()->begin());
2038 auto sliceLoopNest =
2039 cast<AffineForOp>(Val: b.clone(op&: *srcLoopIVs[0].getOperation()));
2040
2041 Operation *sliceInst =
2042 getInstAtPosition(positions, /*level=*/0, block: sliceLoopNest.getBody());
2043 // Get loop nest surrounding 'sliceInst'.
2044 SmallVector<AffineForOp, 4> sliceSurroundingLoops;
2045 getAffineForIVs(op&: *sliceInst, loops: &sliceSurroundingLoops);
2046
2047 // Sanity check.
2048 unsigned sliceSurroundingLoopsSize = sliceSurroundingLoops.size();
2049 (void)sliceSurroundingLoopsSize;
2050 assert(dstLoopDepth + numSrcLoopIVs >= sliceSurroundingLoopsSize);
2051 unsigned sliceLoopLimit = dstLoopDepth + numSrcLoopIVs;
2052 (void)sliceLoopLimit;
2053 assert(sliceLoopLimit >= sliceSurroundingLoopsSize);
2054
2055 // Update loop bounds for loops in 'sliceLoopNest'.
2056 for (unsigned i = 0; i < numSrcLoopIVs; ++i) {
2057 auto forOp = sliceSurroundingLoops[dstLoopDepth + i];
2058 if (AffineMap lbMap = sliceState->lbs[i])
2059 forOp.setLowerBound(operands: sliceState->lbOperands[i], map: lbMap);
2060 if (AffineMap ubMap = sliceState->ubs[i])
2061 forOp.setUpperBound(operands: sliceState->ubOperands[i], map: ubMap);
2062 }
2063 return sliceLoopNest;
2064}
2065
2066// Constructs MemRefAccess populating it with the memref, its indices and
2067// opinst from 'loadOrStoreOpInst'.
2068MemRefAccess::MemRefAccess(Operation *memOp) {
2069 if (auto loadOp = dyn_cast<AffineReadOpInterface>(Val: memOp)) {
2070 memref = loadOp.getMemRef();
2071 opInst = memOp;
2072 llvm::append_range(C&: indices, R: loadOp.getMapOperands());
2073 } else {
2074 assert(isa<AffineWriteOpInterface>(memOp) &&
2075 "Affine read/write op expected");
2076 auto storeOp = cast<AffineWriteOpInterface>(Val: memOp);
2077 opInst = memOp;
2078 memref = storeOp.getMemRef();
2079 llvm::append_range(C&: indices, R: storeOp.getMapOperands());
2080 }
2081}
2082
2083unsigned MemRefAccess::getRank() const {
2084 return cast<MemRefType>(Val: memref.getType()).getRank();
2085}
2086
2087bool MemRefAccess::isStore() const {
2088 return isa<AffineWriteOpInterface>(Val: opInst);
2089}
2090
2091/// Returns the nesting depth of this statement, i.e., the number of loops
2092/// surrounding this statement.
2093unsigned mlir::affine::getNestingDepth(Operation *op) {
2094 Operation *currOp = op;
2095 unsigned depth = 0;
2096 while ((currOp = currOp->getParentOp())) {
2097 if (isa<AffineForOp>(Val: currOp))
2098 depth++;
2099 if (auto parOp = dyn_cast<AffineParallelOp>(Val: currOp))
2100 depth += parOp.getNumDims();
2101 }
2102 return depth;
2103}
2104
2105/// Equal if both affine accesses are provably equivalent (at compile
2106/// time) when considering the memref, the affine maps and their respective
2107/// operands. The equality of access functions + operands is checked by
2108/// subtracting fully composed value maps, and then simplifying the difference
2109/// using the expression flattener.
2110/// TODO: this does not account for aliasing of memrefs.
2111bool MemRefAccess::operator==(const MemRefAccess &rhs) const {
2112 if (memref != rhs.memref)
2113 return false;
2114
2115 AffineValueMap diff, thisMap, rhsMap;
2116 getAccessMap(accessMap: &thisMap);
2117 rhs.getAccessMap(accessMap: &rhsMap);
2118 return thisMap == rhsMap;
2119}
2120
2121void mlir::affine::getAffineIVs(Operation &op, SmallVectorImpl<Value> &ivs) {
2122 auto *currOp = op.getParentOp();
2123 AffineForOp currAffineForOp;
2124 // Traverse up the hierarchy collecting all 'affine.for' and affine.parallel
2125 // operation while skipping over 'affine.if' operations.
2126 while (currOp) {
2127 if (AffineForOp currAffineForOp = dyn_cast<AffineForOp>(Val: currOp))
2128 ivs.push_back(Elt: currAffineForOp.getInductionVar());
2129 else if (auto parOp = dyn_cast<AffineParallelOp>(Val: currOp))
2130 llvm::append_range(C&: ivs, R: parOp.getIVs());
2131 currOp = currOp->getParentOp();
2132 }
2133 std::reverse(first: ivs.begin(), last: ivs.end());
2134}
2135
2136/// Returns the number of surrounding loops common to 'loopsA' and 'loopsB',
2137/// where each lists loops from outer-most to inner-most in loop nest.
2138unsigned mlir::affine::getNumCommonSurroundingLoops(Operation &a,
2139 Operation &b) {
2140 SmallVector<Value, 4> loopsA, loopsB;
2141 getAffineIVs(op&: a, ivs&: loopsA);
2142 getAffineIVs(op&: b, ivs&: loopsB);
2143
2144 unsigned minNumLoops = std::min(a: loopsA.size(), b: loopsB.size());
2145 unsigned numCommonLoops = 0;
2146 for (unsigned i = 0; i < minNumLoops; ++i) {
2147 if (loopsA[i] != loopsB[i])
2148 break;
2149 ++numCommonLoops;
2150 }
2151 return numCommonLoops;
2152}
2153
2154static std::optional<int64_t> getMemoryFootprintBytes(Block &block,
2155 Block::iterator start,
2156 Block::iterator end,
2157 int memorySpace) {
2158 SmallDenseMap<Value, std::unique_ptr<MemRefRegion>, 4> regions;
2159
2160 // Walk this 'affine.for' operation to gather all memory regions.
2161 auto result = block.walk(begin: start, end, callback: [&](Operation *opInst) -> WalkResult {
2162 if (!isa<AffineReadOpInterface, AffineWriteOpInterface>(Val: opInst)) {
2163 // Neither load nor a store op.
2164 return WalkResult::advance();
2165 }
2166
2167 // Compute the memref region symbolic in any IVs enclosing this block.
2168 auto region = std::make_unique<MemRefRegion>(args: opInst->getLoc());
2169 if (failed(
2170 Result: region->compute(op: opInst,
2171 /*loopDepth=*/getNestingDepth(op: &*block.begin())))) {
2172 LDBG() << "Error obtaining memory region";
2173 opInst->emitError(message: "error obtaining memory region");
2174 return failure();
2175 }
2176
2177 auto [it, inserted] = regions.try_emplace(Key: region->memref);
2178 if (inserted) {
2179 it->second = std::move(region);
2180 } else if (failed(Result: it->second->unionBoundingBox(other: *region))) {
2181 LDBG() << "getMemoryFootprintBytes: unable to perform a union on a "
2182 "memory region";
2183 opInst->emitWarning(
2184 message: "getMemoryFootprintBytes: unable to perform a union on a memory "
2185 "region");
2186 return failure();
2187 }
2188 return WalkResult::advance();
2189 });
2190 if (result.wasInterrupted())
2191 return std::nullopt;
2192
2193 int64_t totalSizeInBytes = 0;
2194 for (const auto &region : regions) {
2195 std::optional<int64_t> size = region.second->getRegionSize();
2196 if (!size.has_value())
2197 return std::nullopt;
2198 totalSizeInBytes += *size;
2199 }
2200 return totalSizeInBytes;
2201}
2202
2203std::optional<int64_t> mlir::affine::getMemoryFootprintBytes(AffineForOp forOp,
2204 int memorySpace) {
2205 auto *forInst = forOp.getOperation();
2206 return ::getMemoryFootprintBytes(
2207 block&: *forInst->getBlock(), start: Block::iterator(forInst),
2208 end: std::next(x: Block::iterator(forInst)), memorySpace);
2209}
2210
2211/// Returns whether a loop is parallel and contains a reduction loop.
2212bool mlir::affine::isLoopParallelAndContainsReduction(AffineForOp forOp) {
2213 SmallVector<LoopReduction> reductions;
2214 if (!isLoopParallel(forOp, parallelReductions: &reductions))
2215 return false;
2216 return !reductions.empty();
2217}
2218
2219/// Returns in 'sequentialLoops' all sequential loops in loop nest rooted
2220/// at 'forOp'.
2221void mlir::affine::getSequentialLoops(
2222 AffineForOp forOp, llvm::SmallDenseSet<Value, 8> *sequentialLoops) {
2223 forOp->walk(callback: [&](Operation *op) {
2224 if (auto innerFor = dyn_cast<AffineForOp>(Val: op))
2225 if (!isLoopParallel(forOp: innerFor))
2226 sequentialLoops->insert(V: innerFor.getInductionVar());
2227 });
2228}
2229
2230IntegerSet mlir::affine::simplifyIntegerSet(IntegerSet set) {
2231 FailureOr<FlatAffineValueConstraints> fac =
2232 FlatAffineValueConstraints::create(set);
2233 // Semi-affine sets can't be flattened; return them as is.
2234 if (failed(Result: fac))
2235 return set;
2236 if (fac->isEmpty())
2237 return IntegerSet::getEmptySet(numDims: set.getNumDims(), numSymbols: set.getNumSymbols(),
2238 context: set.getContext());
2239 fac->removeTrivialRedundancy();
2240
2241 auto simplifiedSet = fac->getAsIntegerSet(context: set.getContext());
2242 assert(simplifiedSet && "guaranteed to succeed while roundtripping");
2243 return simplifiedSet;
2244}
2245
2246static void unpackOptionalValues(ArrayRef<std::optional<Value>> source,
2247 SmallVector<Value> &target) {
2248 target = llvm::map_to_vector<4>(C&: source, F: [](std::optional<Value> val) {
2249 return val.has_value() ? *val : Value();
2250 });
2251}
2252
2253/// Bound an identifier `pos` in a given FlatAffineValueConstraints with
2254/// constraints drawn from an affine map. Before adding the constraint, the
2255/// dimensions/symbols of the affine map are aligned with `constraints`.
2256/// `operands` are the SSA Value operands used with the affine map.
2257/// Note: This function adds a new symbol column to the `constraints` for each
2258/// dimension/symbol that exists in the affine map but not in `constraints`.
2259static LogicalResult alignAndAddBound(FlatAffineValueConstraints &constraints,
2260 BoundType type, unsigned pos,
2261 AffineMap map, ValueRange operands) {
2262 SmallVector<Value> dims, syms, newSyms;
2263 unpackOptionalValues(source: constraints.getMaybeValues(kind: VarKind::SetDim), target&: dims);
2264 unpackOptionalValues(source: constraints.getMaybeValues(kind: VarKind::Symbol), target&: syms);
2265
2266 AffineMap alignedMap =
2267 alignAffineMapWithValues(map, operands, dims, syms, newSyms: &newSyms);
2268 for (unsigned i = syms.size(); i < newSyms.size(); ++i)
2269 constraints.appendSymbolVar(vals: newSyms[i]);
2270 return constraints.addBound(type, pos, boundMap: alignedMap);
2271}
2272
2273/// Add `val` to each result of `map`.
2274static AffineMap addConstToResults(AffineMap map, int64_t val) {
2275 SmallVector<AffineExpr> newResults;
2276 for (AffineExpr r : map.getResults())
2277 newResults.push_back(Elt: r + val);
2278 return AffineMap::get(dimCount: map.getNumDims(), symbolCount: map.getNumSymbols(), results: newResults,
2279 context: map.getContext());
2280}
2281
2282// Attempt to simplify the given min/max operation by proving that its value is
2283// bounded by the same lower and upper bound.
2284//
2285// Bounds are computed by FlatAffineValueConstraints. Invariants required for
2286// finding/proving bounds should be supplied via `constraints`.
2287//
2288// 1. Add dimensions for `op` and `opBound` (lower or upper bound of `op`).
2289// 2. Compute an upper bound of `op` (in case of `isMin`) or a lower bound (in
2290// case of `!isMin`) and bind it to `opBound`. SSA values that are used in
2291// `op` but are not part of `constraints`, are added as extra symbols.
2292// 3. For each result of `op`: Add result as a dimension `r_i`. Prove that:
2293// * If `isMin`: r_i >= opBound
2294// * If `isMax`: r_i <= opBound
2295// If this is the case, ub(op) == lb(op).
2296// 4. Replace `op` with `opBound`.
2297//
2298// In summary, the following constraints are added throughout this function.
2299// Note: `invar` are dimensions added by the caller to express the invariants.
2300// (Showing only the case where `isMin`.)
2301//
2302// invar | op | opBound | r_i | extra syms... | const | eq/ineq
2303// ------+-------+---------+-----+---------------+-------+-------------------
2304// (various eq./ineq. constraining `invar`, added by the caller)
2305// ... | 0 | 0 | 0 | 0 | ... | ...
2306// ------+-------+---------+-----+---------------+-------+-------------------
2307// (various ineq. constraining `op` in terms of `op` operands (`invar` and
2308// extra `op` operands "extra syms" that are not in `invar`)).
2309// ... | -1 | 0 | 0 | ... | ... | >= 0
2310// ------+-------+---------+-----+---------------+-------+-------------------
2311// (set `opBound` to `op` upper bound in terms of `invar` and "extra syms")
2312// ... | 0 | -1 | 0 | ... | ... | = 0
2313// ------+-------+---------+-----+---------------+-------+-------------------
2314// (for each `op` map result r_i: set r_i to corresponding map result,
2315// prove that r_i >= minOpUb via contradiction)
2316// ... | 0 | 0 | -1 | ... | ... | = 0
2317// 0 | 0 | 1 | -1 | 0 | -1 | >= 0
2318//
2319FailureOr<AffineValueMap> mlir::affine::simplifyConstrainedMinMaxOp(
2320 Operation *op, FlatAffineValueConstraints constraints) {
2321 bool isMin = isa<AffineMinOp>(Val: op);
2322 assert((isMin || isa<AffineMaxOp>(op)) && "expect AffineMin/MaxOp");
2323 MLIRContext *ctx = op->getContext();
2324 Builder builder(ctx);
2325 AffineMap map =
2326 isMin ? cast<AffineMinOp>(Val: op).getMap() : cast<AffineMaxOp>(Val: op).getMap();
2327 ValueRange operands = op->getOperands();
2328 unsigned numResults = map.getNumResults();
2329
2330 // Add a few extra dimensions.
2331 unsigned dimOp = constraints.appendDimVar(); // `op`
2332 unsigned dimOpBound = constraints.appendDimVar(); // `op` lower/upper bound
2333 unsigned resultDimStart = constraints.appendDimVar(/*num=*/numResults);
2334
2335 // Add an inequality for each result expr_i of map:
2336 // isMin: op <= expr_i, !isMin: op >= expr_i
2337 auto boundType = isMin ? BoundType::UB : BoundType::LB;
2338 // Upper bounds are exclusive, so add 1. (`affine.min` ops are inclusive.)
2339 AffineMap mapLbUb = isMin ? addConstToResults(map, val: 1) : map;
2340 if (failed(
2341 Result: alignAndAddBound(constraints, type: boundType, pos: dimOp, map: mapLbUb, operands)))
2342 return failure();
2343
2344 // Try to compute a lower/upper bound for op, expressed in terms of the other
2345 // `dims` and extra symbols.
2346 SmallVector<AffineMap> opLb(1), opUb(1);
2347 constraints.getSliceBounds(offset: dimOp, num: 1, context: ctx, lbMaps: &opLb, ubMaps: &opUb);
2348 AffineMap sliceBound = isMin ? opUb[0] : opLb[0];
2349 // TODO: `getSliceBounds` may return multiple bounds at the moment. This is
2350 // a TODO of `getSliceBounds` and not handled here.
2351 if (!sliceBound || sliceBound.getNumResults() != 1)
2352 return failure(); // No or multiple bounds found.
2353 // Recover the inclusive UB in the case of an `affine.min`.
2354 AffineMap boundMap = isMin ? addConstToResults(map: sliceBound, val: -1) : sliceBound;
2355
2356 // Add an equality: Set dimOpBound to computed bound.
2357 // Add back dimension for op. (Was removed by `getSliceBounds`.)
2358 AffineMap alignedBoundMap = boundMap.shiftDims(/*shift=*/1, /*offset=*/dimOp);
2359 if (failed(Result: constraints.addBound(type: BoundType::EQ, pos: dimOpBound, boundMap: alignedBoundMap)))
2360 return failure();
2361
2362 // If the constraint system is empty, there is an inconsistency. (E.g., this
2363 // can happen if loop lb > ub.)
2364 if (constraints.isEmpty())
2365 return failure();
2366
2367 // In the case of `isMin` (`!isMin` is inversed):
2368 // Prove that each result of `map` has a lower bound that is equal to (or
2369 // greater than) the upper bound of `op` (`dimOpBound`). In that case, `op`
2370 // can be replaced with the bound. I.e., prove that for each result
2371 // expr_i (represented by dimension r_i):
2372 //
2373 // r_i >= opBound
2374 //
2375 // To prove this inequality, add its negation to the constraint set and prove
2376 // that the constraint set is empty.
2377 for (unsigned i = resultDimStart; i < resultDimStart + numResults; ++i) {
2378 FlatAffineValueConstraints newConstr(constraints);
2379
2380 // Add an equality: r_i = expr_i
2381 // Note: These equalities could have been added earlier and used to express
2382 // minOp <= expr_i. However, then we run the risk that `getSliceBounds`
2383 // computes minOpUb in terms of r_i dims, which is not desired.
2384 if (failed(Result: alignAndAddBound(constraints&: newConstr, type: BoundType::EQ, pos: i,
2385 map: map.getSubMap(resultPos: {i - resultDimStart}), operands)))
2386 return failure();
2387
2388 // If `isMin`: Add inequality: r_i < opBound
2389 // equiv.: opBound - r_i - 1 >= 0
2390 // If `!isMin`: Add inequality: r_i > opBound
2391 // equiv.: -opBound + r_i - 1 >= 0
2392 SmallVector<int64_t> ineq(newConstr.getNumCols(), 0);
2393 ineq[dimOpBound] = isMin ? 1 : -1;
2394 ineq[i] = isMin ? -1 : 1;
2395 ineq[newConstr.getNumCols() - 1] = -1;
2396 newConstr.addInequality(inEq: ineq);
2397 if (!newConstr.isEmpty())
2398 return failure();
2399 }
2400
2401 // Lower and upper bound of `op` are equal. Replace `minOp` with its bound.
2402 AffineMap newMap = alignedBoundMap;
2403 SmallVector<Value> newOperands;
2404 unpackOptionalValues(source: constraints.getMaybeValues(), target&: newOperands);
2405 // If dims/symbols have known constant values, use those in order to simplify
2406 // the affine map further.
2407 for (int64_t i = 0, e = constraints.getNumDimAndSymbolVars(); i < e; ++i) {
2408 // Skip unused operands and operands that are already constants.
2409 if (!newOperands[i] || getConstantIntValue(ofr: newOperands[i]))
2410 continue;
2411 if (auto bound = constraints.getConstantBound64(type: BoundType::EQ, pos: i)) {
2412 AffineExpr expr =
2413 i < newMap.getNumDims()
2414 ? builder.getAffineDimExpr(position: i)
2415 : builder.getAffineSymbolExpr(position: i - newMap.getNumDims());
2416 newMap = newMap.replace(expr, replacement: builder.getAffineConstantExpr(constant: *bound),
2417 numResultDims: newMap.getNumDims(), numResultSyms: newMap.getNumSymbols());
2418 }
2419 }
2420
2421 // Internal constraint variables (dimOp, dimOpBound, resultDimStart, etc.)
2422 // have no associated SSA values (null Value()). Replace their corresponding
2423 // dim/symbol positions in newMap with constant 0 and compact newOperands.
2424 // These positions should be unreferenced in newMap (the bound was computed
2425 // in terms of the original operands only), so replacing with 0 is safe.
2426 // This prevents canonicalizeMapAndOperands from using null Values as
2427 // DenseMap keys, which would cause undefined behavior.
2428 {
2429 unsigned numDims = newMap.getNumDims();
2430 unsigned numSyms = newMap.getNumSymbols();
2431 SmallVector<AffineExpr> dimReplacements(numDims), symReplacements(numSyms);
2432 SmallVector<Value> filteredOperands;
2433 filteredOperands.reserve(N: newOperands.size());
2434 unsigned newDim = 0;
2435 for (unsigned i = 0; i < numDims; ++i) {
2436 if (newOperands[i]) {
2437 dimReplacements[i] = getAffineDimExpr(position: newDim++, context: ctx);
2438 filteredOperands.push_back(Elt: newOperands[i]);
2439 } else {
2440 assert(!newMap.isFunctionOfDim(i) &&
2441 "null-valued dim operand referenced in bound map");
2442 dimReplacements[i] = getAffineConstantExpr(constant: 0, context: ctx);
2443 }
2444 }
2445 unsigned newSym = 0;
2446 for (unsigned i = 0; i < numSyms; ++i) {
2447 if (newOperands[numDims + i]) {
2448 symReplacements[i] = getAffineSymbolExpr(position: newSym++, context: ctx);
2449 filteredOperands.push_back(Elt: newOperands[numDims + i]);
2450 } else {
2451 assert(!newMap.isFunctionOfSymbol(i) &&
2452 "null-valued symbol operand referenced in bound map");
2453 symReplacements[i] = getAffineConstantExpr(constant: 0, context: ctx);
2454 }
2455 }
2456 newMap = newMap.replaceDimsAndSymbols(dimReplacements, symReplacements,
2457 numResultDims: newDim, numResultSyms: newSym);
2458 newOperands = std::move(filteredOperands);
2459 }
2460
2461 affine::canonicalizeMapAndOperands(map: &newMap, operands: &newOperands);
2462 return AffineValueMap(newMap, newOperands);
2463}
2464
2465Block *mlir::affine::findInnermostCommonBlockInScope(Operation *a,
2466 Operation *b) {
2467 Region *aScope = getAffineAnalysisScope(op: a);
2468 Region *bScope = getAffineAnalysisScope(op: b);
2469 if (aScope != bScope)
2470 return nullptr;
2471
2472 // Get the block ancestry of `op` while stopping at the affine scope `aScope`
2473 // and store them in `ancestry`.
2474 auto getBlockAncestry = [&](Operation *op,
2475 SmallVectorImpl<Block *> &ancestry) {
2476 Operation *curOp = op;
2477 do {
2478 ancestry.push_back(Elt: curOp->getBlock());
2479 if (curOp->getParentRegion() == aScope)
2480 break;
2481 curOp = curOp->getParentOp();
2482 } while (curOp);
2483 assert(curOp && "can't reach root op without passing through affine scope");
2484 std::reverse(first: ancestry.begin(), last: ancestry.end());
2485 };
2486
2487 SmallVector<Block *, 4> aAncestors, bAncestors;
2488 getBlockAncestry(a, aAncestors);
2489 getBlockAncestry(b, bAncestors);
2490 assert(!aAncestors.empty() && !bAncestors.empty() &&
2491 "at least one Block ancestor expected");
2492
2493 Block *innermostCommonBlock = nullptr;
2494 for (unsigned a = 0, b = 0, e = aAncestors.size(), f = bAncestors.size();
2495 a < e && b < f; ++a, ++b) {
2496 if (aAncestors[a] != bAncestors[b])
2497 break;
2498 innermostCommonBlock = aAncestors[a];
2499 }
2500 return innermostCommonBlock;
2501}
2502