MLIR  22.0.0git
Utils.h
Go to the documentation of this file.
1 //===- Utils.h - General analysis utilities ---------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This header file defines prototypes for various transformation utilities for
10 // memref's and non-loop IR structures. These are not passes by themselves but
11 // are used either by passes, optimization sequences, or in turn by other
12 // transformation utilities.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef MLIR_DIALECT_AFFINE_ANALYSIS_UTILS_H
17 #define MLIR_DIALECT_AFFINE_ANALYSIS_UTILS_H
18 
21 #include <memory>
22 #include <optional>
23 
24 namespace mlir {
25 class Block;
26 class Location;
27 class Operation;
28 class Value;
29 
30 namespace affine {
31 class AffineForOp;
32 class AffineValueMap;
33 struct MemRefAccess;
34 
35 // LoopNestStateCollector walks loop nests and collects load and store
36 // operations, and whether or not a region holding op other than ForOp and IfOp
37 // was encountered in the loop nest.
40  // Affine loads.
42  // Affine stores.
44  // Non-affine loads.
46  // Non-affine stores.
48  // Free operations.
50 
51  // Collects load and store operations, and whether or not a region holding op
52  // other than ForOp and IfOp was encountered in the loop nest.
53  void collect(Operation *opToWalk);
54 };
55 
56 // MemRefDependenceGraph is a graph data structure where graph nodes are
57 // top-level operations in a `Block` and edges are memref dependences or SSA
58 // dependences (on memrefs) between the nodes. Nodes are created for all
59 // top-level operations except in certain cases (see `init` method). Edges are
60 // created between nodes with a dependence (see `Edge` documentation). Edges
61 // aren't created from/to nodes that have no memory effects.
63 public:
64  // Node represents a node in the graph. A Node is either an entire loop nest
65  // rooted at the top level which contains loads/stores, or a top level
66  // load/store.
67  struct Node {
68  // The unique identifier of this node in the graph.
69  unsigned id;
70  // The top-level statement which is (or contains) a load/store.
72  // List of affine loads.
74  // List of non-affine loads.
76  // List of affine store ops.
78  // List of non-affine stores.
80  // List of free operations.
82  // Set of private memrefs used in this node.
84 
85  Node(unsigned id, Operation *op) : id(id), op(op) {}
86 
87  // Returns the load op count for 'memref'.
88  unsigned getLoadOpCount(Value memref) const;
89 
90  // Returns the store op count for 'memref'.
91  unsigned getStoreOpCount(Value memref) const;
92 
93  /// Returns true if there exists an operation with a write memory effect to
94  /// `memref` in this node.
95  unsigned hasStore(Value memref) const;
96 
97  // Returns true if the node has a free op on `memref`.
98  unsigned hasFree(Value memref) const;
99 
100  // Returns all store ops in 'storeOps' which access 'memref'.
101  void getStoreOpsForMemref(Value memref,
102  SmallVectorImpl<Operation *> *storeOps) const;
103 
104  // Returns all load ops in 'loadOps' which access 'memref'.
105  void getLoadOpsForMemref(Value memref,
106  SmallVectorImpl<Operation *> *loadOps) const;
107 
108  // Returns all memrefs in 'loadAndStoreMemrefSet' for which this node
109  // has at least one load and store operation.
110  void getLoadAndStoreMemrefSet(DenseSet<Value> *loadAndStoreMemrefSet) const;
111  };
112 
113  // Edge represents a data dependence between nodes in the graph. It can either
114  // be a memory dependence or an SSA dependence. In the former case, it
115  // corresponds to a pair of memory accesses to the same memref or aliasing
116  // memrefs where at least one of them has a write or free memory effect. The
117  // memory accesses need not be affine load/store operations. Operations are
118  // checked for read/write effects and edges may be added conservatively. Edges
119  // are not created to/from nodes that have no memory effect. An exception to
120  // this are SSA dependences between operations that define memrefs (like
121  // alloc's, view-like ops) and their memory-effecting users that are enclosed
122  // in loops.
123  struct Edge {
124  // The id of the node at the other end of the edge.
125  // If this edge is stored in Edge = Node.inEdges[i], then
126  // 'Node.inEdges[i].id' is the identifier of the source node of the edge.
127  // If this edge is stored in Edge = Node.outEdges[i], then
128  // 'Node.outEdges[i].id' is the identifier of the dest node of the edge.
129  unsigned id;
130  // The SSA value on which this edge represents a dependence.
131  // If the value is a memref, then the dependence is between graph nodes
132  // which contain accesses to the same memref 'value'. If the value is a
133  // non-memref value, then the dependence is between a graph node which
134  // defines an SSA value and another graph node which uses the SSA value
135  // (e.g. a constant or load operation defining a value which is used inside
136  // a loop nest).
138  };
139 
140  // Map from node id to Node.
142  // Map from node id to list of input edges. The absence of an entry for a key
143  // is also equivalent to the absence of any edges.
145  // Map from node id to list of output edges. The absence of an entry for a
146  // node is also equivalent to the absence of any edges.
148  // Map from memref to a count on the dependence edges associated with that
149  // memref.
151  // The next unique identifier to use for newly created graph nodes.
152  unsigned nextNodeId = 0;
153 
155 
156  // Initializes the data dependence graph by iterating over the operations of
157  // the MDG's `block`. A `Node` is created for every top-level op except for
158  // side-effect-free operations with zero results and no regions. Assigns each
159  // node in the graph a node id based on the order in block. Fails if certain
160  // kinds of operations, for which `Node` creation isn't supported, are
161  // encountered (unknown region holding ops). If `fullAffineDependences` is
162  // set, affine memory dependence analysis is performed before concluding that
163  // conflicting affine memory accesses lead to a dependence check; otherwise, a
164  // pair of conflicting affine memory accesses (where one of them is a store
165  // and they are to the same memref) always leads to an edge (conservatively).
166  bool init(bool fullAffineDependences = true);
167 
168  // Returns the graph node for 'id'.
169  const Node *getNode(unsigned id) const;
170  Node *getNode(unsigned id) {
171  return const_cast<Node *>(
172  static_cast<const MemRefDependenceGraph *>(this)->getNode(id));
173  }
174 
175  // Returns true if the graph has node with ID `id`.
176  bool hasNode(unsigned id) const { return nodes.contains(id); }
177 
178  // Returns the graph node for 'forOp'.
179  const Node *getForOpNode(AffineForOp forOp) const;
180  Node *getForOpNode(AffineForOp forOp) {
181  return const_cast<Node *>(
182  static_cast<const MemRefDependenceGraph *>(this)->getForOpNode(forOp));
183  }
184 
185  // Adds a node with 'op' to the graph and returns its unique identifier.
186  unsigned addNode(Operation *op);
187 
188  // Remove node 'id' (and its associated edges) from graph.
189  void removeNode(unsigned id);
190 
191  // Returns true if node 'id' writes to any memref which escapes (or is an
192  // argument to) the block. Returns false otherwise.
193  bool writesToLiveInOrEscapingMemrefs(unsigned id) const;
194 
195  // Returns true iff there is an edge from node 'srcId' to node 'dstId' which
196  // is for 'value' if non-null, or for any value otherwise. Returns false
197  // otherwise.
198  bool hasEdge(unsigned srcId, unsigned dstId, Value value = nullptr) const;
199 
200  // Adds an edge from node 'srcId' to node 'dstId' for 'value'.
201  void addEdge(unsigned srcId, unsigned dstId, Value value);
202 
203  // Removes an edge from node 'srcId' to node 'dstId' for 'value'.
204  void removeEdge(unsigned srcId, unsigned dstId, Value value);
205 
206  // Returns true if there is a path in the dependence graph from node 'srcId'
207  // to node 'dstId'. Returns false otherwise. `srcId`, `dstId`, and the
208  // operations that the edges connected are expected to be from the same block.
209  bool hasDependencePath(unsigned srcId, unsigned dstId) const;
210 
211  // Returns the input edge count for node 'id' and 'memref' from src nodes
212  // which access 'memref' with a store operation.
213  unsigned getIncomingMemRefAccesses(unsigned id, Value memref) const;
214 
215  // Returns the output edge count for node 'id' and 'memref' (if non-null),
216  // otherwise returns the total output edge count from node 'id'.
217  unsigned getOutEdgeCount(unsigned id, Value memref = nullptr) const;
218 
219  /// Return all nodes which define SSA values used in node 'id'.
220  void gatherDefiningNodes(unsigned id,
221  DenseSet<unsigned> &definingNodes) const;
222 
223  // Computes and returns an insertion point operation, before which the
224  // the fused <srcId, dstId> loop nest can be inserted while preserving
225  // dependences. Returns nullptr if no such insertion point is found.
227  unsigned dstId) const;
228 
229  // Updates edge mappings from node 'srcId' to node 'dstId' after fusing them,
230  // taking into account that:
231  // *) if 'removeSrcId' is true, 'srcId' will be removed after fusion,
232  // *) memrefs in 'privateMemRefs' has been replaced in node at 'dstId' by a
233  // private memref.
234  void updateEdges(unsigned srcId, unsigned dstId,
235  const DenseSet<Value> &privateMemRefs, bool removeSrcId);
236 
237  // Update edge mappings for nodes 'sibId' and 'dstId' to reflect fusion
238  // of sibling node 'sibId' into node 'dstId'.
239  void updateEdges(unsigned sibId, unsigned dstId);
240 
241  // Adds the specified ops to lists of node at 'id'.
242  void addToNode(unsigned id, ArrayRef<Operation *> loads,
243  ArrayRef<Operation *> stores,
244  ArrayRef<Operation *> memrefLoads,
245  ArrayRef<Operation *> memrefStores,
246  ArrayRef<Operation *> memrefFrees);
247 
248  void clearNodeLoadAndStores(unsigned id);
249 
250  // Calls 'callback' for each input edge incident to node 'id' which carries a
251  // memref dependence.
252  void forEachMemRefInputEdge(unsigned id,
253  const std::function<void(Edge)> &callback);
254 
255  // Calls 'callback' for each output edge from node 'id' which carries a
256  // memref dependence.
257  void forEachMemRefOutputEdge(unsigned id,
258  const std::function<void(Edge)> &callback);
259 
260  // Calls 'callback' for each edge in 'edges' which carries a memref
261  // dependence.
263  const std::function<void(Edge)> &callback);
264 
265  void print(raw_ostream &os) const;
266 
267  void dump() const { print(llvm::errs()); }
268 
269  /// The block for which this graph is created to perform fusion.
271 };
272 
273 /// Populates 'loops' with IVs of the affine.for ops surrounding 'op' ordered
274 /// from the outermost 'affine.for' operation to the innermost one while not
275 /// traversing outside of the surrounding affine scope.
277 
278 /// Populates 'ivs' with IVs of the surrounding affine.for and affine.parallel
279 /// ops ordered from the outermost one to the innermost while not traversing
280 /// outside of the surrounding affine scope.
282 
283 /// Populates 'ops' with affine operations enclosing `op` ordered from outermost
284 /// to innermost while stopping at the boundary of the affine scope. affine.for,
285 /// affine.if, or affine.parallel ops comprise such surrounding affine ops.
286 /// `ops` is guaranteed by design to have a successive chain of affine parent
287 /// ops.
289 
290 /// Returns the nesting depth of this operation, i.e., the number of loops
291 /// surrounding this operation.
292 unsigned getNestingDepth(Operation *op);
293 
294 /// Returns whether a loop is a parallel loop and contains a reduction loop.
295 bool isLoopParallelAndContainsReduction(AffineForOp forOp);
296 
297 /// Returns in 'sequentialLoops' all sequential loops in loop nest rooted
298 /// at 'forOp'.
299 void getSequentialLoops(AffineForOp forOp,
300  llvm::SmallDenseSet<Value, 8> *sequentialLoops);
301 
302 /// Enumerates different result statuses of slice computation by
303 /// `computeSliceUnion`
304 // TODO: Identify and add different kinds of failures during slice computation.
306  enum ResultEnum {
308  IncorrectSliceFailure, // Slice is computed, but it is incorrect.
309  GenericFailure, // Unable to compute src loop computation slice.
310  } value;
312 };
313 
314 /// ComputationSliceState aggregates loop IVs, loop bound AffineMaps and their
315 /// associated operands for a set of loops within a loop nest (typically the
316 /// set of loops surrounding a store operation). Loop bound AffineMaps which
317 /// are non-null represent slices of that loop's iteration space.
319  // List of sliced loop IVs (ordered from outermost to innermost).
320  // EX: 'ivs[i]' has lower bound 'lbs[i]' and upper bound 'ubs[i]'.
322  // List of lower bound AffineMaps.
324  // List of upper bound AffineMaps.
326  // List of lower bound operands (lbOperands[i] are used by 'lbs[i]').
327  std::vector<SmallVector<Value, 4>> lbOperands;
328  // List of upper bound operands (ubOperands[i] are used by 'ubs[i]').
329  std::vector<SmallVector<Value, 4>> ubOperands;
330  // Slice loop nest insertion point in target loop nest.
332  // Adds to 'cst' with constraints which represent the slice bounds on 'ivs'
333  // in 'this'. Specifically, the values in 'ivs' are added to 'cst' as dim
334  // variables and the values in 'lb/ubOperands' are added as symbols.
335  // Constraints are added for all loop IV bounds (dim or symbol), and
336  // constraints are added for slice bounds in 'lbs'/'ubs'.
337  // Returns failure if we cannot add loop bounds because of unsupported cases.
338  LogicalResult getAsConstraints(FlatAffineValueConstraints *cst) const;
339 
340  /// Adds to 'cst' constraints which represent the original loop bounds on
341  /// 'ivs' in 'this'. This corresponds to the original domain of the loop nest
342  /// from which the slice is being computed. Returns failure if we cannot add
343  /// loop bounds because of unsupported cases.
344  LogicalResult getSourceAsConstraints(FlatAffineValueConstraints &cst) const;
345 
346  // Clears all bounds and operands in slice state.
347  void clearBounds();
348 
349  /// Returns true if the computation slice is empty.
350  bool isEmpty() const { return ivs.empty(); }
351 
352  /// Returns true if the computation slice encloses all the iterations of the
353  /// sliced loop nest. Returns false if it does not. Returns std::nullopt if it
354  /// cannot determine if the slice is maximal or not.
355  // TODO: Cache 'isMaximal' so that we don't recompute it when the slice
356  // information hasn't changed.
357  std::optional<bool> isMaximal() const;
358 
359  /// Checks the validity of the slice computed. This is done using the
360  /// following steps:
361  /// 1. Get the new domain of the slice that would be created if fusion
362  /// succeeds. This domain gets constructed with source loop IVS and
363  /// destination loop IVS as dimensions.
364  /// 2. Project out the dimensions of the destination loop from the domain
365  /// above calculated in step(1) to express it purely in terms of the source
366  /// loop IVs.
367  /// 3. Calculate a set difference between the iterations of the new domain and
368  /// the original domain of the source loop.
369  /// If this difference is empty, the slice is declared to be valid. Otherwise,
370  /// return false as it implies that the effective fusion results in at least
371  /// one iteration of the slice that was not originally in the source's domain.
372  /// If the validity cannot be determined, returns std::nullopt.
373  std::optional<bool> isSliceValid() const;
374 
375  void dump() const;
376 
377 private:
378  /// Fast check to determine if the computation slice is maximal. Returns true
379  /// if each slice dimension maps to an existing dst dimension and both the src
380  /// and the dst loops for those dimensions have the same bounds. Returns false
381  /// if both the src and the dst loops don't have the same bounds. Returns
382  /// std::nullopt if none of the above can be proven.
383  std::optional<bool> isSliceMaximalFastCheck() const;
384 };
385 
386 /// Computes the computation slice loop bounds for one loop nest as affine maps
387 /// of the other loop nest's IVs and symbols, using 'dependenceConstraints'
388 /// computed between 'depSourceAccess' and 'depSinkAccess'.
389 /// If 'isBackwardSlice' is true, a backwards slice is computed in which the
390 /// slice bounds of loop nest surrounding 'depSourceAccess' are computed in
391 /// terms of loop IVs and symbols of the loop nest surrounding 'depSinkAccess'
392 /// at 'loopDepth'.
393 /// If 'isBackwardSlice' is false, a forward slice is computed in which the
394 /// slice bounds of loop nest surrounding 'depSinkAccess' are computed in terms
395 /// of loop IVs and symbols of the loop nest surrounding 'depSourceAccess' at
396 /// 'loopDepth'.
397 /// The slice loop bounds and associated operands are returned in 'sliceState'.
398 //
399 // Backward slice example:
400 //
401 // affine.for %i0 = 0 to 10 {
402 // affine.store %cst, %0[%i0] : memref<100xf32> // 'depSourceAccess'
403 // }
404 // affine.for %i1 = 0 to 10 {
405 // %v = affine.load %0[%i1] : memref<100xf32> // 'depSinkAccess'
406 // }
407 //
408 // // Backward computation slice of loop nest '%i0'.
409 // affine.for %i0 = (d0) -> (d0)(%i1) to (d0) -> (d0 + 1)(%i1) {
410 // affine.store %cst, %0[%i0] : memref<100xf32> // 'depSourceAccess'
411 // }
412 //
413 // Forward slice example:
414 //
415 // affine.for %i0 = 0 to 10 {
416 // affine.store %cst, %0[%i0] : memref<100xf32> // 'depSourceAccess'
417 // }
418 // affine.for %i1 = 0 to 10 {
419 // %v = affine.load %0[%i1] : memref<100xf32> // 'depSinkAccess'
420 // }
421 //
422 // // Forward computation slice of loop nest '%i1'.
423 // affine.for %i1 = (d0) -> (d0)(%i0) to (d0) -> (d0 + 1)(%i0) {
424 // %v = affine.load %0[%i1] : memref<100xf32> // 'depSinkAccess'
425 // }
426 //
428  Operation *depSourceOp, Operation *depSinkOp,
429  const FlatAffineValueConstraints &dependenceConstraints, unsigned loopDepth,
430  bool isBackwardSlice, ComputationSliceState *sliceState);
431 
432 /// Return the number of iterations for the `slicetripCountMap` provided.
433 uint64_t getSliceIterationCount(
434  const llvm::SmallDenseMap<Operation *, uint64_t, 8> &sliceTripCountMap);
435 
436 /// Builds a map 'tripCountMap' from AffineForOp to constant trip count for
437 /// loop nest surrounding represented by slice loop bounds in 'slice'. Returns
438 /// true on success, false otherwise (if a non-constant trip count was
439 /// encountered).
441  const ComputationSliceState &slice,
442  llvm::SmallDenseMap<Operation *, uint64_t, 8> *tripCountMap);
443 
444 /// Computes in 'sliceUnion' the union of all slice bounds computed at
445 /// 'loopDepth' between all dependent pairs of ops in 'opsA' and 'opsB', and
446 /// then verifies if it is valid. The parameter 'numCommonLoops' is the number
447 /// of loops common to the operations in 'opsA' and 'opsB'. If 'isBackwardSlice'
448 /// is true, computes slice bounds for loop nest surrounding ops in 'opsA', as a
449 /// function of IVs and symbols of loop nest surrounding ops in 'opsB' at
450 /// 'loopDepth'. If 'isBackwardSlice' is false, computes slice bounds for loop
451 /// nest surrounding ops in 'opsB', as a function of IVs and symbols of loop
452 /// nest surrounding ops in 'opsA' at 'loopDepth'. Returns
453 /// 'SliceComputationResult::Success' if union was computed correctly, an
454 /// appropriate 'failure' otherwise.
455 SliceComputationResult
457  unsigned loopDepth, unsigned numCommonLoops,
458  bool isBackwardSlice, ComputationSliceState *sliceUnion);
459 
460 /// Creates a clone of the computation contained in the loop nest surrounding
461 /// 'srcOpInst', slices the iteration space of src loop based on slice bounds
462 /// in 'sliceState', and inserts the computation slice at the beginning of the
463 /// operation block of the loop at 'dstLoopDepth' in the loop nest surrounding
464 /// 'dstOpInst'. Returns the top-level loop of the computation slice on
465 /// success, returns nullptr otherwise.
466 // Loop depth is a crucial optimization choice that determines where to
467 // materialize the results of the backward slice - presenting a trade-off b/w
468 // storage and redundant computation in several cases.
469 // TODO: Support computation slices with common surrounding loops.
470 AffineForOp insertBackwardComputationSlice(Operation *srcOpInst,
471  Operation *dstOpInst,
472  unsigned dstLoopDepth,
473  ComputationSliceState *sliceState);
474 
475 /// A region of a memref's data space; this is typically constructed by
476 /// analyzing load/store op's on this memref and the index space of loops
477 /// surrounding such op's.
478 // For example, the memref region for a load operation at loop depth = 1:
479 //
480 // affine.for %i = 0 to 32 {
481 // affine.for %ii = %i to (d0) -> (d0 + 8) (%i) {
482 // affine.load %A[%ii]
483 // }
484 // }
485 //
486 // Region: {memref = %A, write = false, {%i <= m0 <= %i + 7} }
487 // The last field is a 2-d FlatAffineValueConstraints symbolic in %i.
488 //
489 struct MemRefRegion {
490  explicit MemRefRegion(Location loc) : loc(loc) {}
491 
492  /// Computes the memory region accessed by this memref with the region
493  /// represented as constraints symbolic/parametric in 'loopDepth' loops
494  /// surrounding opInst. The computed region's 'cst' field has exactly as many
495  /// dimensional variables as the rank of the memref, and *potentially*
496  /// additional symbolic variables which could include any of the loop IVs
497  /// surrounding opInst up until 'loopDepth' and another additional Function
498  /// symbols involved with the access (for eg., those appear in affine.apply's,
499  /// loop bounds, etc.). If 'sliceState' is non-null, operands from
500  /// 'sliceState' are added as symbols, and the following constraints are added
501  /// to the system:
502  /// *) Inequality constraints which represent loop bounds for 'sliceState'
503  /// operands which are loop IVS (these represent the destination loop IVs
504  /// of the slice, and are added as symbols to MemRefRegion's constraint
505  /// system).
506  /// *) Inequality constraints for the slice bounds in 'sliceState', which
507  /// represent the bounds on the loop IVs in this constraint system w.r.t
508  /// to slice operands (which correspond to symbols).
509  /// If 'addMemRefDimBounds' is true, constant upper/lower bounds
510  /// [0, memref.getDimSize(i)) are added for each MemRef dimension 'i'.
511  /// If `dropLocalVars` is true, all local variables in `cst` are projected
512  /// out.
513  ///
514  /// For example, the memref region for this operation at loopDepth = 1 will
515  /// be:
516  ///
517  /// affine.for %i = 0 to 32 {
518  /// affine.for %ii = %i to (d0) -> (d0 + 8) (%i) {
519  /// load %A[%ii]
520  /// }
521  /// }
522  ///
523  /// {memref = %A, write = false, {%i <= m0 <= %i + 7} }
524  /// The last field is a 2-d FlatAffineValueConstraints symbolic in %i.
525  ///
526  /// If `dropOuterIVs` is true, project out any IVs other than those among
527  /// `loopDepth` surrounding IVs, which would be symbols. If `dropOuterIVs`
528  /// is false, the IVs would be turned into local variables instead of being
529  /// projected out.
530  LogicalResult compute(Operation *op, unsigned loopDepth,
531  const ComputationSliceState *sliceState = nullptr,
532  bool addMemRefDimBounds = true,
533  bool dropLocalVars = true, bool dropOuterIVs = true);
534 
536  const FlatAffineValueConstraints *getConstraints() const { return &cst; }
537  bool isWrite() const { return write; }
538  void setWrite(bool flag) { write = flag; }
539 
540  /// Returns a constant upper bound on the number of elements in this region if
541  /// bounded by a known constant (always possible for static shapes),
542  /// std::nullopt otherwise. Note that the symbols of the region are treated
543  /// specially, i.e., the returned bounding constant holds for *any given*
544  /// value of the symbol variables. The 'shape' vector is set to the
545  /// corresponding dimension-wise bounds major to minor. The number of elements
546  /// and all the dimension-wise bounds are guaranteed to be non-negative. We
547  /// use int64_t instead of uint64_t since index types can be at most
548  /// int64_t. `lbs` are set to the lower bound maps for each of the rank
549  /// dimensions where each of these maps is purely symbolic in the constraints
550  /// set's symbols.
551  std::optional<int64_t> getConstantBoundingSizeAndShape(
552  SmallVectorImpl<int64_t> *shape = nullptr,
553  SmallVectorImpl<AffineMap> *lbs = nullptr) const;
554 
555  /// Gets the lower and upper bound map for the dimensional variable at
556  /// `pos`.
557  void getLowerAndUpperBound(unsigned pos, AffineMap &lbMap,
558  AffineMap &ubMap) const;
559 
560  /// Returns the size of this MemRefRegion in bytes.
561  std::optional<int64_t> getRegionSize();
562 
563  // Wrapper around FlatAffineValueConstraints::unionBoundingBox.
564  LogicalResult unionBoundingBox(const MemRefRegion &other);
565 
566  /// Returns the rank of the memref that this region corresponds to.
567  unsigned getRank() const;
568 
569  /// Memref that this region corresponds to.
571 
572  /// Read or write.
573  bool write = false;
574 
575  /// If there is more than one load/store op associated with the region, the
576  /// location information would correspond to one of those op's.
578 
579  /// Region (data space) of the memref accessed. This set will thus have at
580  /// least as many dimensional variables as the shape dimensionality of the
581  /// memref, and these are the leading dimensions of the set appearing in that
582  /// order (major to minor / outermost to innermost). There may be additional
583  /// variables since getMemRefRegion() is called with a specific loop depth,
584  /// and thus the region is symbolic in the outer surrounding loops at that
585  /// depth.
587 };
588 
589 /// Returns the size of a memref with element type int or float in bytes if it's
590 /// statically shaped, std::nullopt otherwise.
591 std::optional<uint64_t> getIntOrFloatMemRefSizeInBytes(MemRefType memRefType);
592 
593 /// Checks a load or store op for an out of bound access; returns failure if the
594 /// access is out of bounds along any of the dimensions, success otherwise.
595 /// Emits a diagnostic error (with location information) if emitError is true.
596 template <typename LoadOrStoreOpPointer>
597 LogicalResult boundCheckLoadOrStoreOp(LoadOrStoreOpPointer loadOrStoreOp,
598  bool emitError = true);
599 
600 /// Returns the number of surrounding loops common to both A and B.
602 
603 /// Gets the memory footprint of all data touched in the specified memory space
604 /// in bytes; if the memory space is unspecified, considers all memory spaces.
605 std::optional<int64_t> getMemoryFootprintBytes(AffineForOp forOp,
606  int memorySpace = -1);
607 
608 /// Returns the memref's element type's size in bytes where the elemental type
609 /// is an int or float or a vector of such types.
610 std::optional<int64_t> getMemRefIntOrFloatEltSizeInBytes(MemRefType memRefType);
611 
612 /// Simplify the integer set by simplifying the underlying affine expressions by
613 /// flattening and some simple inference. Also, drop any duplicate constraints.
614 /// Returns the simplified integer set. This method runs in time linear in the
615 /// number of constraints.
617 
618 /// Returns the innermost common loop depth for the set of operations in 'ops'.
621  SmallVectorImpl<AffineForOp> *surroundingLoops = nullptr);
622 
623 /// Try to simplify the given affine.min or affine.max op to an affine map with
624 /// a single result and operands, taking into account the specified constraint
625 /// set. Return failure if no simplified version could be found.
626 FailureOr<AffineValueMap>
628  FlatAffineValueConstraints constraints);
629 
630 /// Find the innermost common `Block` of `a` and `b` in the affine scope
631 /// that `a` and `b` are part of. Return nullptr if they belong to different
632 /// affine scopes. Also, return nullptr if they do not have a common `Block`
633 /// ancestor (for eg., when they are part of the `then` and `else` regions
634 /// of an op that itself starts an affine scope.
636  mlir::Operation *b);
637 
638 } // namespace affine
639 } // namespace mlir
640 
641 #endif // MLIR_DIALECT_AFFINE_ANALYSIS_UTILS_H
MemRefDependenceGraph::Node Node
Definition: Utils.cpp:38
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
Definition: AffineMap.h:46
Block represents an ordered list of Operations.
Definition: Block.h:33
OpListType::iterator iterator
Definition: Block.h:140
An integer set representing a conjunction of one or more affine equalities and inequalities.
Definition: IntegerSet.h:44
This class defines the main interface for locations in MLIR and acts as a non-nullable wrapper around...
Definition: Location.h:76
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
FlatAffineValueConstraints is an extension of FlatLinearValueConstraints with helper functions for Af...
IntegerSet simplifyIntegerSet(IntegerSet set)
Simplify the integer set by simplifying the underlying affine expressions by flattening and some simp...
Definition: Utils.cpp:2200
void getEnclosingAffineOps(Operation &op, SmallVectorImpl< Operation * > *ops)
Populates 'ops' with affine operations enclosing op ordered from outermost to innermost while stoppin...
Definition: Utils.cpp:865
SliceComputationResult computeSliceUnion(ArrayRef< Operation * > opsA, ArrayRef< Operation * > opsB, unsigned loopDepth, unsigned numCommonLoops, bool isBackwardSlice, ComputationSliceState *sliceUnion)
Computes in 'sliceUnion' the union of all slice bounds computed at 'loopDepth' between all dependent ...
Definition: Utils.cpp:1633
bool isLoopParallelAndContainsReduction(AffineForOp forOp)
Returns whether a loop is a parallel loop and contains a reduction loop.
Definition: Utils.cpp:2182
unsigned getNumCommonSurroundingLoops(Operation &a, Operation &b)
Returns the number of surrounding loops common to both A and B.
Definition: Utils.cpp:2108
void getAffineIVs(Operation &op, SmallVectorImpl< Value > &ivs)
Populates 'ivs' with IVs of the surrounding affine.for and affine.parallel ops ordered from the outer...
Definition: Utils.cpp:2091
void getSequentialLoops(AffineForOp forOp, llvm::SmallDenseSet< Value, 8 > *sequentialLoops)
Returns in 'sequentialLoops' all sequential loops in loop nest rooted at 'forOp'.
Definition: Utils.cpp:2191
void getAffineForIVs(Operation &op, SmallVectorImpl< AffineForOp > *loops)
Populates 'loops' with IVs of the affine.for ops surrounding 'op' ordered from the outermost 'affine....
Definition: Utils.cpp:851
std::optional< int64_t > getMemoryFootprintBytes(AffineForOp forOp, int memorySpace=-1)
Gets the memory footprint of all data touched in the specified memory space in bytes; if the memory s...
Definition: Utils.cpp:2173
unsigned getInnermostCommonLoopDepth(ArrayRef< Operation * > ops, SmallVectorImpl< AffineForOp > *surroundingLoops=nullptr)
Returns the innermost common loop depth for the set of operations in 'ops'.
Definition: Utils.cpp:1601
void getComputationSliceState(Operation *depSourceOp, Operation *depSinkOp, const FlatAffineValueConstraints &dependenceConstraints, unsigned loopDepth, bool isBackwardSlice, ComputationSliceState *sliceState)
Computes the computation slice loop bounds for one loop nest as affine maps of the other loop nest's ...
Definition: Utils.cpp:1870
std::optional< uint64_t > getIntOrFloatMemRefSizeInBytes(MemRefType memRefType)
Returns the size of a memref with element type int or float in bytes if it's statically shaped,...
Definition: Utils.cpp:1463
unsigned getNestingDepth(Operation *op)
Returns the nesting depth of this operation, i.e., the number of loops surrounding this operation.
Definition: Utils.cpp:2063
uint64_t getSliceIterationCount(const llvm::SmallDenseMap< Operation *, uint64_t, 8 > &sliceTripCountMap)
Return the number of iterations for the slicetripCountMap provided.
Definition: Utils.cpp:1856
LogicalResult boundCheckLoadOrStoreOp(LoadOrStoreOpPointer loadOrStoreOp, bool emitError=true)
Checks a load or store op for an out of bound access; returns failure if the access is out of bounds ...
mlir::Block * findInnermostCommonBlockInScope(mlir::Operation *a, mlir::Operation *b)
Find the innermost common Block of a and b in the affine scope that a and b are part of.
Definition: Utils.cpp:2391
bool buildSliceTripCountMap(const ComputationSliceState &slice, llvm::SmallDenseMap< Operation *, uint64_t, 8 > *tripCountMap)
Builds a map 'tripCountMap' from AffineForOp to constant trip count for loop nest surrounding represe...
Definition: Utils.cpp:1818
AffineForOp insertBackwardComputationSlice(Operation *srcOpInst, Operation *dstOpInst, unsigned dstLoopDepth, ComputationSliceState *sliceState)
Creates a clone of the computation contained in the loop nest surrounding 'srcOpInst',...
Definition: Utils.cpp:1982
FailureOr< AffineValueMap > simplifyConstrainedMinMaxOp(Operation *op, FlatAffineValueConstraints constraints)
Try to simplify the given affine.min or affine.max op to an affine map with a single result and opera...
Definition: Utils.cpp:2286
std::optional< int64_t > getMemRefIntOrFloatEltSizeInBytes(MemRefType memRefType)
Returns the memref's element type's size in bytes where the elemental type is an int or float or a ve...
Definition: Utils.cpp:1419
Include the generated interface declarations.
InFlightDiagnostic emitError(Location loc)
Utility method to emit an error message using this location.
ComputationSliceState aggregates loop IVs, loop bound AffineMaps and their associated operands for a ...
Definition: Utils.h:318
std::optional< bool > isSliceValid() const
Checks the validity of the slice computed.
Definition: Utils.cpp:1036
SmallVector< Value, 4 > ivs
Definition: Utils.h:321
LogicalResult getAsConstraints(FlatAffineValueConstraints *cst) const
Definition: Utils.cpp:898
bool isEmpty() const
Returns true if the computation slice is empty.
Definition: Utils.h:350
LogicalResult getSourceAsConstraints(FlatAffineValueConstraints &cst) const
Adds to 'cst' constraints which represent the original loop bounds on 'ivs' in 'this'.
Definition: Utils.cpp:882
std::vector< SmallVector< Value, 4 > > ubOperands
Definition: Utils.h:329
SmallVector< AffineMap, 4 > ubs
Definition: Utils.h:325
std::optional< bool > isMaximal() const
Returns true if the computation slice encloses all the iterations of the sliced loop nest.
Definition: Utils.cpp:1106
SmallVector< AffineMap, 4 > lbs
Definition: Utils.h:323
std::vector< SmallVector< Value, 4 > > lbOperands
Definition: Utils.h:327
SmallVector< Operation *, 4 > memrefFrees
Definition: Utils.h:49
SmallVector< AffineForOp, 4 > forOps
Definition: Utils.h:39
SmallVector< Operation *, 4 > loadOpInsts
Definition: Utils.h:41
SmallVector< Operation *, 4 > memrefStores
Definition: Utils.h:47
void collect(Operation *opToWalk)
Definition: Utils.cpp:43
SmallVector< Operation *, 4 > memrefLoads
Definition: Utils.h:45
SmallVector< Operation *, 4 > storeOpInsts
Definition: Utils.h:43
void getStoreOpsForMemref(Value memref, SmallVectorImpl< Operation * > *storeOps) const
Definition: Utils.cpp:130
SmallVector< Operation *, 4 > loads
Definition: Utils.h:73
SmallVector< Operation *, 4 > stores
Definition: Utils.h:77
void getLoadAndStoreMemrefSet(DenseSet< Value > *loadAndStoreMemrefSet) const
Definition: Utils.cpp:149
Node(unsigned id, Operation *op)
Definition: Utils.h:85
unsigned hasFree(Value memref) const
Definition: Utils.cpp:123
SmallVector< Operation *, 4 > memrefLoads
Definition: Utils.h:75
SmallVector< Operation *, 4 > memrefStores
Definition: Utils.h:79
unsigned getLoadOpCount(Value memref) const
Definition: Utils.cpp:78
unsigned getStoreOpCount(Value memref) const
Definition: Utils.cpp:93
unsigned hasStore(Value memref) const
Returns true if there exists an operation with a write memory effect to memref in this node.
Definition: Utils.cpp:109
void getLoadOpsForMemref(Value memref, SmallVectorImpl< Operation * > *loadOps) const
Definition: Utils.cpp:139
SmallVector< Operation *, 4 > memrefFrees
Definition: Utils.h:81
DenseMap< unsigned, SmallVector< Edge, 2 > > outEdges
Definition: Utils.h:147
Block & block
The block for which this graph is created to perform fusion.
Definition: Utils.h:270
unsigned addNode(Operation *op)
Definition: Utils.cpp:467
bool writesToLiveInOrEscapingMemrefs(unsigned id) const
Definition: Utils.cpp:497
Node * getForOpNode(AffineForOp forOp)
Definition: Utils.h:180
void removeEdge(unsigned srcId, unsigned dstId, Value value)
Definition: Utils.cpp:543
void addEdge(unsigned srcId, unsigned dstId, Value value)
Definition: Utils.cpp:532
MemRefDependenceGraph(Block &block)
Definition: Utils.h:154
DenseMap< unsigned, Node > nodes
Definition: Utils.h:141
void gatherDefiningNodes(unsigned id, DenseSet< unsigned > &definingNodes) const
Return all nodes which define SSA values used in node 'id'.
Definition: Utils.cpp:631
bool hasDependencePath(unsigned srcId, unsigned dstId) const
Definition: Utils.cpp:570
void clearNodeLoadAndStores(unsigned id)
Definition: Utils.cpp:797
const Node * getForOpNode(AffineForOp forOp) const
Definition: Utils.cpp:459
Operation * getFusedLoopNestInsertionPoint(unsigned srcId, unsigned dstId) const
Definition: Utils.cpp:645
void updateEdges(unsigned srcId, unsigned dstId, const DenseSet< Value > &privateMemRefs, bool removeSrcId)
Definition: Utils.cpp:720
bool hasNode(unsigned id) const
Definition: Utils.h:176
DenseMap< unsigned, SmallVector< Edge, 2 > > inEdges
Definition: Utils.h:144
void forEachMemRefInputEdge(unsigned id, const std::function< void(Edge)> &callback)
Definition: Utils.cpp:805
bool init(bool fullAffineDependences=true)
Definition: Utils.cpp:336
unsigned getOutEdgeCount(unsigned id, Value memref=nullptr) const
Definition: Utils.cpp:621
const Node * getNode(unsigned id) const
Definition: Utils.cpp:452
void removeNode(unsigned id)
Definition: Utils.cpp:474
void forEachMemRefOutputEdge(unsigned id, const std::function< void(Edge)> &callback)
Definition: Utils.cpp:813
void forEachMemRefEdge(ArrayRef< Edge > edges, const std::function< void(Edge)> &callback)
Definition: Utils.cpp:821
void addToNode(unsigned id, ArrayRef< Operation * > loads, ArrayRef< Operation * > stores, ArrayRef< Operation * > memrefLoads, ArrayRef< Operation * > memrefStores, ArrayRef< Operation * > memrefFrees)
Definition: Utils.cpp:784
Node * getNode(unsigned id)
Definition: Utils.h:170
unsigned getIncomingMemRefAccesses(unsigned id, Value memref) const
Definition: Utils.cpp:605
bool hasEdge(unsigned srcId, unsigned dstId, Value value=nullptr) const
Definition: Utils.cpp:517
void print(raw_ostream &os) const
Definition: Utils.cpp:833
DenseMap< Value, unsigned > memrefEdgeCount
Definition: Utils.h:150
A region of a memref's data space; this is typically constructed by analyzing load/store op's on this...
Definition: Utils.h:489
std::optional< int64_t > getConstantBoundingSizeAndShape(SmallVectorImpl< int64_t > *shape=nullptr, SmallVectorImpl< AffineMap > *lbs=nullptr) const
Returns a constant upper bound on the number of elements in this region if bounded by a known constan...
Definition: Utils.cpp:1160
FlatAffineValueConstraints * getConstraints()
Definition: Utils.h:535
unsigned getRank() const
Returns the rank of the memref that this region corresponds to.
Definition: Utils.cpp:1156
FlatAffineValueConstraints cst
Region (data space) of the memref accessed.
Definition: Utils.h:586
bool isWrite() const
Definition: Utils.h:537
LogicalResult compute(Operation *op, unsigned loopDepth, const ComputationSliceState *sliceState=nullptr, bool addMemRefDimBounds=true, bool dropLocalVars=true, bool dropOuterIVs=true)
Computes the memory region accessed by this memref with the region represented as constraints symboli...
Definition: Utils.cpp:1257
void getLowerAndUpperBound(unsigned pos, AffineMap &lbMap, AffineMap &ubMap) const
Gets the lower and upper bound map for the dimensional variable at pos.
Definition: Utils.cpp:1216
std::optional< int64_t > getRegionSize()
Returns the size of this MemRefRegion in bytes.
Definition: Utils.cpp:1438
LogicalResult unionBoundingBox(const MemRefRegion &other)
Definition: Utils.cpp:1235
bool write
Read or write.
Definition: Utils.h:573
const FlatAffineValueConstraints * getConstraints() const
Definition: Utils.h:536
void setWrite(bool flag)
Definition: Utils.h:538
Value memref
Memref that this region corresponds to.
Definition: Utils.h:570
MemRefRegion(Location loc)
Definition: Utils.h:490
Location loc
If there is more than one load/store op associated with the region, the location information would co...
Definition: Utils.h:577
Enumerates different result statuses of slice computation by computeSliceUnion
Definition: Utils.h:305
SliceComputationResult(ResultEnum v)
Definition: Utils.h:311
enum mlir::affine::SliceComputationResult::ResultEnum value