MLIR  21.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 dependence graph based on operations in `block'.
157  // Returns true on success, false otherwise.
158  bool init();
159 
160  // Returns the graph node for 'id'.
161  const Node *getNode(unsigned id) const;
162  Node *getNode(unsigned id) {
163  return const_cast<Node *>(
164  static_cast<const MemRefDependenceGraph *>(this)->getNode(id));
165  }
166 
167  // Returns true if the graph has node with ID `id`.
168  bool hasNode(unsigned id) const { return nodes.contains(id); }
169 
170  // Returns the graph node for 'forOp'.
171  const Node *getForOpNode(AffineForOp forOp) const;
172  Node *getForOpNode(AffineForOp forOp) {
173  return const_cast<Node *>(
174  static_cast<const MemRefDependenceGraph *>(this)->getForOpNode(forOp));
175  }
176 
177  // Adds a node with 'op' to the graph and returns its unique identifier.
178  unsigned addNode(Operation *op);
179 
180  // Remove node 'id' (and its associated edges) from graph.
181  void removeNode(unsigned id);
182 
183  // Returns true if node 'id' writes to any memref which escapes (or is an
184  // argument to) the block. Returns false otherwise.
185  bool writesToLiveInOrEscapingMemrefs(unsigned id) const;
186 
187  // Returns true iff there is an edge from node 'srcId' to node 'dstId' which
188  // is for 'value' if non-null, or for any value otherwise. Returns false
189  // otherwise.
190  bool hasEdge(unsigned srcId, unsigned dstId, Value value = nullptr) const;
191 
192  // Adds an edge from node 'srcId' to node 'dstId' for 'value'.
193  void addEdge(unsigned srcId, unsigned dstId, Value value);
194 
195  // Removes an edge from node 'srcId' to node 'dstId' for 'value'.
196  void removeEdge(unsigned srcId, unsigned dstId, Value value);
197 
198  // Returns true if there is a path in the dependence graph from node 'srcId'
199  // to node 'dstId'. Returns false otherwise. `srcId`, `dstId`, and the
200  // operations that the edges connected are expected to be from the same block.
201  bool hasDependencePath(unsigned srcId, unsigned dstId) const;
202 
203  // Returns the input edge count for node 'id' and 'memref' from src nodes
204  // which access 'memref' with a store operation.
205  unsigned getIncomingMemRefAccesses(unsigned id, Value memref) const;
206 
207  // Returns the output edge count for node 'id' and 'memref' (if non-null),
208  // otherwise returns the total output edge count from node 'id'.
209  unsigned getOutEdgeCount(unsigned id, Value memref = nullptr) const;
210 
211  /// Return all nodes which define SSA values used in node 'id'.
212  void gatherDefiningNodes(unsigned id,
213  DenseSet<unsigned> &definingNodes) const;
214 
215  // Computes and returns an insertion point operation, before which the
216  // the fused <srcId, dstId> loop nest can be inserted while preserving
217  // dependences. Returns nullptr if no such insertion point is found.
219  unsigned dstId) const;
220 
221  // Updates edge mappings from node 'srcId' to node 'dstId' after fusing them,
222  // taking into account that:
223  // *) if 'removeSrcId' is true, 'srcId' will be removed after fusion,
224  // *) memrefs in 'privateMemRefs' has been replaced in node at 'dstId' by a
225  // private memref.
226  void updateEdges(unsigned srcId, unsigned dstId,
227  const DenseSet<Value> &privateMemRefs, bool removeSrcId);
228 
229  // Update edge mappings for nodes 'sibId' and 'dstId' to reflect fusion
230  // of sibling node 'sibId' into node 'dstId'.
231  void updateEdges(unsigned sibId, unsigned dstId);
232 
233  // Adds the specified ops to lists of node at 'id'.
234  void addToNode(unsigned id, ArrayRef<Operation *> loads,
235  ArrayRef<Operation *> stores,
236  ArrayRef<Operation *> memrefLoads,
237  ArrayRef<Operation *> memrefStores,
238  ArrayRef<Operation *> memrefFrees);
239 
240  void clearNodeLoadAndStores(unsigned id);
241 
242  // Calls 'callback' for each input edge incident to node 'id' which carries a
243  // memref dependence.
244  void forEachMemRefInputEdge(unsigned id,
245  const std::function<void(Edge)> &callback);
246 
247  // Calls 'callback' for each output edge from node 'id' which carries a
248  // memref dependence.
249  void forEachMemRefOutputEdge(unsigned id,
250  const std::function<void(Edge)> &callback);
251 
252  // Calls 'callback' for each edge in 'edges' which carries a memref
253  // dependence.
255  const std::function<void(Edge)> &callback);
256 
257  void print(raw_ostream &os) const;
258 
259  void dump() const { print(llvm::errs()); }
260 
261  /// The block for which this graph is created to perform fusion.
263 };
264 
265 /// Populates 'loops' with IVs of the affine.for ops surrounding 'op' ordered
266 /// from the outermost 'affine.for' operation to the innermost one while not
267 /// traversing outside of the surrounding affine scope.
269 
270 /// Populates 'ivs' with IVs of the surrounding affine.for and affine.parallel
271 /// ops ordered from the outermost one to the innermost while not traversing
272 /// outside of the surrounding affine scope.
274 
275 /// Populates 'ops' with affine operations enclosing `op` ordered from outermost
276 /// to innermost while stopping at the boundary of the affine scope. affine.for,
277 /// affine.if, or affine.parallel ops comprise such surrounding affine ops.
278 /// `ops` is guaranteed by design to have a successive chain of affine parent
279 /// ops.
281 
282 /// Returns the nesting depth of this operation, i.e., the number of loops
283 /// surrounding this operation.
284 unsigned getNestingDepth(Operation *op);
285 
286 /// Returns whether a loop is a parallel loop and contains a reduction loop.
287 bool isLoopParallelAndContainsReduction(AffineForOp forOp);
288 
289 /// Returns in 'sequentialLoops' all sequential loops in loop nest rooted
290 /// at 'forOp'.
291 void getSequentialLoops(AffineForOp forOp,
292  llvm::SmallDenseSet<Value, 8> *sequentialLoops);
293 
294 /// Enumerates different result statuses of slice computation by
295 /// `computeSliceUnion`
296 // TODO: Identify and add different kinds of failures during slice computation.
298  enum ResultEnum {
300  IncorrectSliceFailure, // Slice is computed, but it is incorrect.
301  GenericFailure, // Unable to compute src loop computation slice.
302  } value;
304 };
305 
306 /// ComputationSliceState aggregates loop IVs, loop bound AffineMaps and their
307 /// associated operands for a set of loops within a loop nest (typically the
308 /// set of loops surrounding a store operation). Loop bound AffineMaps which
309 /// are non-null represent slices of that loop's iteration space.
311  // List of sliced loop IVs (ordered from outermost to innermost).
312  // EX: 'ivs[i]' has lower bound 'lbs[i]' and upper bound 'ubs[i]'.
314  // List of lower bound AffineMaps.
316  // List of upper bound AffineMaps.
318  // List of lower bound operands (lbOperands[i] are used by 'lbs[i]').
319  std::vector<SmallVector<Value, 4>> lbOperands;
320  // List of upper bound operands (ubOperands[i] are used by 'ubs[i]').
321  std::vector<SmallVector<Value, 4>> ubOperands;
322  // Slice loop nest insertion point in target loop nest.
324  // Adds to 'cst' with constraints which represent the slice bounds on 'ivs'
325  // in 'this'. Specifically, the values in 'ivs' are added to 'cst' as dim
326  // variables and the values in 'lb/ubOperands' are added as symbols.
327  // Constraints are added for all loop IV bounds (dim or symbol), and
328  // constraints are added for slice bounds in 'lbs'/'ubs'.
329  // Returns failure if we cannot add loop bounds because of unsupported cases.
330  LogicalResult getAsConstraints(FlatAffineValueConstraints *cst) const;
331 
332  /// Adds to 'cst' constraints which represent the original loop bounds on
333  /// 'ivs' in 'this'. This corresponds to the original domain of the loop nest
334  /// from which the slice is being computed. Returns failure if we cannot add
335  /// loop bounds because of unsupported cases.
336  LogicalResult getSourceAsConstraints(FlatAffineValueConstraints &cst) const;
337 
338  // Clears all bounds and operands in slice state.
339  void clearBounds();
340 
341  /// Returns true if the computation slice is empty.
342  bool isEmpty() const { return ivs.empty(); }
343 
344  /// Returns true if the computation slice encloses all the iterations of the
345  /// sliced loop nest. Returns false if it does not. Returns std::nullopt if it
346  /// cannot determine if the slice is maximal or not.
347  // TODO: Cache 'isMaximal' so that we don't recompute it when the slice
348  // information hasn't changed.
349  std::optional<bool> isMaximal() const;
350 
351  /// Checks the validity of the slice computed. This is done using the
352  /// following steps:
353  /// 1. Get the new domain of the slice that would be created if fusion
354  /// succeeds. This domain gets constructed with source loop IVS and
355  /// destination loop IVS as dimensions.
356  /// 2. Project out the dimensions of the destination loop from the domain
357  /// above calculated in step(1) to express it purely in terms of the source
358  /// loop IVs.
359  /// 3. Calculate a set difference between the iterations of the new domain and
360  /// the original domain of the source loop.
361  /// If this difference is empty, the slice is declared to be valid. Otherwise,
362  /// return false as it implies that the effective fusion results in at least
363  /// one iteration of the slice that was not originally in the source's domain.
364  /// If the validity cannot be determined, returns std::nullopt.
365  std::optional<bool> isSliceValid() const;
366 
367  void dump() const;
368 
369 private:
370  /// Fast check to determine if the computation slice is maximal. Returns true
371  /// if each slice dimension maps to an existing dst dimension and both the src
372  /// and the dst loops for those dimensions have the same bounds. Returns false
373  /// if both the src and the dst loops don't have the same bounds. Returns
374  /// std::nullopt if none of the above can be proven.
375  std::optional<bool> isSliceMaximalFastCheck() const;
376 };
377 
378 /// Computes the computation slice loop bounds for one loop nest as affine maps
379 /// of the other loop nest's IVs and symbols, using 'dependenceConstraints'
380 /// computed between 'depSourceAccess' and 'depSinkAccess'.
381 /// If 'isBackwardSlice' is true, a backwards slice is computed in which the
382 /// slice bounds of loop nest surrounding 'depSourceAccess' are computed in
383 /// terms of loop IVs and symbols of the loop nest surrounding 'depSinkAccess'
384 /// at 'loopDepth'.
385 /// If 'isBackwardSlice' is false, a forward slice is computed in which the
386 /// slice bounds of loop nest surrounding 'depSinkAccess' are computed in terms
387 /// of loop IVs and symbols of the loop nest surrounding 'depSourceAccess' at
388 /// 'loopDepth'.
389 /// The slice loop bounds and associated operands are returned in 'sliceState'.
390 //
391 // Backward slice example:
392 //
393 // affine.for %i0 = 0 to 10 {
394 // affine.store %cst, %0[%i0] : memref<100xf32> // 'depSourceAccess'
395 // }
396 // affine.for %i1 = 0 to 10 {
397 // %v = affine.load %0[%i1] : memref<100xf32> // 'depSinkAccess'
398 // }
399 //
400 // // Backward computation slice of loop nest '%i0'.
401 // affine.for %i0 = (d0) -> (d0)(%i1) to (d0) -> (d0 + 1)(%i1) {
402 // affine.store %cst, %0[%i0] : memref<100xf32> // 'depSourceAccess'
403 // }
404 //
405 // Forward slice example:
406 //
407 // affine.for %i0 = 0 to 10 {
408 // affine.store %cst, %0[%i0] : memref<100xf32> // 'depSourceAccess'
409 // }
410 // affine.for %i1 = 0 to 10 {
411 // %v = affine.load %0[%i1] : memref<100xf32> // 'depSinkAccess'
412 // }
413 //
414 // // Forward computation slice of loop nest '%i1'.
415 // affine.for %i1 = (d0) -> (d0)(%i0) to (d0) -> (d0 + 1)(%i0) {
416 // %v = affine.load %0[%i1] : memref<100xf32> // 'depSinkAccess'
417 // }
418 //
420  Operation *depSourceOp, Operation *depSinkOp,
421  const FlatAffineValueConstraints &dependenceConstraints, unsigned loopDepth,
422  bool isBackwardSlice, ComputationSliceState *sliceState);
423 
424 /// Return the number of iterations for the `slicetripCountMap` provided.
425 uint64_t getSliceIterationCount(
426  const llvm::SmallDenseMap<Operation *, uint64_t, 8> &sliceTripCountMap);
427 
428 /// Builds a map 'tripCountMap' from AffineForOp to constant trip count for
429 /// loop nest surrounding represented by slice loop bounds in 'slice'. Returns
430 /// true on success, false otherwise (if a non-constant trip count was
431 /// encountered).
433  const ComputationSliceState &slice,
434  llvm::SmallDenseMap<Operation *, uint64_t, 8> *tripCountMap);
435 
436 /// Computes in 'sliceUnion' the union of all slice bounds computed at
437 /// 'loopDepth' between all dependent pairs of ops in 'opsA' and 'opsB', and
438 /// then verifies if it is valid. The parameter 'numCommonLoops' is the number
439 /// of loops common to the operations in 'opsA' and 'opsB'. If 'isBackwardSlice'
440 /// is true, computes slice bounds for loop nest surrounding ops in 'opsA', as a
441 /// function of IVs and symbols of loop nest surrounding ops in 'opsB' at
442 /// 'loopDepth'. If 'isBackwardSlice' is false, computes slice bounds for loop
443 /// nest surrounding ops in 'opsB', as a function of IVs and symbols of loop
444 /// nest surrounding ops in 'opsA' at 'loopDepth'. Returns
445 /// 'SliceComputationResult::Success' if union was computed correctly, an
446 /// appropriate 'failure' otherwise.
447 SliceComputationResult
449  unsigned loopDepth, unsigned numCommonLoops,
450  bool isBackwardSlice, ComputationSliceState *sliceUnion);
451 
452 /// Creates a clone of the computation contained in the loop nest surrounding
453 /// 'srcOpInst', slices the iteration space of src loop based on slice bounds
454 /// in 'sliceState', and inserts the computation slice at the beginning of the
455 /// operation block of the loop at 'dstLoopDepth' in the loop nest surrounding
456 /// 'dstOpInst'. Returns the top-level loop of the computation slice on
457 /// success, returns nullptr otherwise.
458 // Loop depth is a crucial optimization choice that determines where to
459 // materialize the results of the backward slice - presenting a trade-off b/w
460 // storage and redundant computation in several cases.
461 // TODO: Support computation slices with common surrounding loops.
462 AffineForOp insertBackwardComputationSlice(Operation *srcOpInst,
463  Operation *dstOpInst,
464  unsigned dstLoopDepth,
465  ComputationSliceState *sliceState);
466 
467 /// A region of a memref's data space; this is typically constructed by
468 /// analyzing load/store op's on this memref and the index space of loops
469 /// surrounding such op's.
470 // For example, the memref region for a load operation at loop depth = 1:
471 //
472 // affine.for %i = 0 to 32 {
473 // affine.for %ii = %i to (d0) -> (d0 + 8) (%i) {
474 // affine.load %A[%ii]
475 // }
476 // }
477 //
478 // Region: {memref = %A, write = false, {%i <= m0 <= %i + 7} }
479 // The last field is a 2-d FlatAffineValueConstraints symbolic in %i.
480 //
481 struct MemRefRegion {
482  explicit MemRefRegion(Location loc) : loc(loc) {}
483 
484  /// Computes the memory region accessed by this memref with the region
485  /// represented as constraints symbolic/parametric in 'loopDepth' loops
486  /// surrounding opInst. The computed region's 'cst' field has exactly as many
487  /// dimensional variables as the rank of the memref, and *potentially*
488  /// additional symbolic variables which could include any of the loop IVs
489  /// surrounding opInst up until 'loopDepth' and another additional Function
490  /// symbols involved with the access (for eg., those appear in affine.apply's,
491  /// loop bounds, etc.). If 'sliceState' is non-null, operands from
492  /// 'sliceState' are added as symbols, and the following constraints are added
493  /// to the system:
494  /// *) Inequality constraints which represent loop bounds for 'sliceState'
495  /// operands which are loop IVS (these represent the destination loop IVs
496  /// of the slice, and are added as symbols to MemRefRegion's constraint
497  /// system).
498  /// *) Inequality constraints for the slice bounds in 'sliceState', which
499  /// represent the bounds on the loop IVs in this constraint system w.r.t
500  /// to slice operands (which correspond to symbols).
501  /// If 'addMemRefDimBounds' is true, constant upper/lower bounds
502  /// [0, memref.getDimSize(i)) are added for each MemRef dimension 'i'.
503  /// If `dropLocalVars` is true, all local variables in `cst` are projected
504  /// out.
505  ///
506  /// For example, the memref region for this operation at loopDepth = 1 will
507  /// be:
508  ///
509  /// affine.for %i = 0 to 32 {
510  /// affine.for %ii = %i to (d0) -> (d0 + 8) (%i) {
511  /// load %A[%ii]
512  /// }
513  /// }
514  ///
515  /// {memref = %A, write = false, {%i <= m0 <= %i + 7} }
516  /// The last field is a 2-d FlatAffineValueConstraints symbolic in %i.
517  ///
518  /// If `dropOuterIVs` is true, project out any IVs other than those among
519  /// `loopDepth` surrounding IVs, which would be symbols. If `dropOuterIVs`
520  /// is false, the IVs would be turned into local variables instead of being
521  /// projected out.
522  LogicalResult compute(Operation *op, unsigned loopDepth,
523  const ComputationSliceState *sliceState = nullptr,
524  bool addMemRefDimBounds = true,
525  bool dropLocalVars = true, bool dropOuterIVs = true);
526 
528  const FlatAffineValueConstraints *getConstraints() const { return &cst; }
529  bool isWrite() const { return write; }
530  void setWrite(bool flag) { write = flag; }
531 
532  /// Returns a constant upper bound on the number of elements in this region if
533  /// bounded by a known constant (always possible for static shapes),
534  /// std::nullopt otherwise. Note that the symbols of the region are treated
535  /// specially, i.e., the returned bounding constant holds for *any given*
536  /// value of the symbol variables. The 'shape' vector is set to the
537  /// corresponding dimension-wise bounds major to minor. The number of elements
538  /// and all the dimension-wise bounds are guaranteed to be non-negative. We
539  /// use int64_t instead of uint64_t since index types can be at most
540  /// int64_t. `lbs` are set to the lower bound maps for each of the rank
541  /// dimensions where each of these maps is purely symbolic in the constraints
542  /// set's symbols.
543  std::optional<int64_t> getConstantBoundingSizeAndShape(
544  SmallVectorImpl<int64_t> *shape = nullptr,
545  SmallVectorImpl<AffineMap> *lbs = nullptr) const;
546 
547  /// Gets the lower and upper bound map for the dimensional variable at
548  /// `pos`.
549  void getLowerAndUpperBound(unsigned pos, AffineMap &lbMap,
550  AffineMap &ubMap) const;
551 
552  /// Returns the size of this MemRefRegion in bytes.
553  std::optional<int64_t> getRegionSize();
554 
555  // Wrapper around FlatAffineValueConstraints::unionBoundingBox.
556  LogicalResult unionBoundingBox(const MemRefRegion &other);
557 
558  /// Returns the rank of the memref that this region corresponds to.
559  unsigned getRank() const;
560 
561  /// Memref that this region corresponds to.
563 
564  /// Read or write.
565  bool write = false;
566 
567  /// If there is more than one load/store op associated with the region, the
568  /// location information would correspond to one of those op's.
570 
571  /// Region (data space) of the memref accessed. This set will thus have at
572  /// least as many dimensional variables as the shape dimensionality of the
573  /// memref, and these are the leading dimensions of the set appearing in that
574  /// order (major to minor / outermost to innermost). There may be additional
575  /// variables since getMemRefRegion() is called with a specific loop depth,
576  /// and thus the region is symbolic in the outer surrounding loops at that
577  /// depth.
579 };
580 
581 /// Returns the size of a memref with element type int or float in bytes if it's
582 /// statically shaped, std::nullopt otherwise.
583 std::optional<uint64_t> getIntOrFloatMemRefSizeInBytes(MemRefType memRefType);
584 
585 /// Checks a load or store op for an out of bound access; returns failure if the
586 /// access is out of bounds along any of the dimensions, success otherwise.
587 /// Emits a diagnostic error (with location information) if emitError is true.
588 template <typename LoadOrStoreOpPointer>
589 LogicalResult boundCheckLoadOrStoreOp(LoadOrStoreOpPointer loadOrStoreOp,
590  bool emitError = true);
591 
592 /// Returns the number of surrounding loops common to both A and B.
594 
595 /// Gets the memory footprint of all data touched in the specified memory space
596 /// in bytes; if the memory space is unspecified, considers all memory spaces.
597 std::optional<int64_t> getMemoryFootprintBytes(AffineForOp forOp,
598  int memorySpace = -1);
599 
600 /// Returns the memref's element type's size in bytes where the elemental type
601 /// is an int or float or a vector of such types.
602 std::optional<int64_t> getMemRefIntOrFloatEltSizeInBytes(MemRefType memRefType);
603 
604 /// Simplify the integer set by simplifying the underlying affine expressions by
605 /// flattening and some simple inference. Also, drop any duplicate constraints.
606 /// Returns the simplified integer set. This method runs in time linear in the
607 /// number of constraints.
609 
610 /// Returns the innermost common loop depth for the set of operations in 'ops'.
613  SmallVectorImpl<AffineForOp> *surroundingLoops = nullptr);
614 
615 /// Try to simplify the given affine.min or affine.max op to an affine map with
616 /// a single result and operands, taking into account the specified constraint
617 /// set. Return failure if no simplified version could be found.
618 FailureOr<AffineValueMap>
620  FlatAffineValueConstraints constraints);
621 
622 /// Find the innermost common `Block` of `a` and `b` in the affine scope
623 /// that `a` and `b` are part of. Return nullptr if they belong to different
624 /// affine scopes. Also, return nullptr if they do not have a common `Block`
625 /// ancestor (for eg., when they are part of the `then` and `else` regions
626 /// of an op that itself starts an affine scope.
628  mlir::Operation *b);
629 
630 } // namespace affine
631 } // namespace mlir
632 
633 #endif // MLIR_DIALECT_AFFINE_ANALYSIS_UTILS_H
MemRefDependenceGraph::Node Node
Definition: Utils.cpp:39
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:66
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:2113
void getEnclosingAffineOps(Operation &op, SmallVectorImpl< Operation * > *ops)
Populates 'ops' with affine operations enclosing op ordered from outermost to innermost while stoppin...
Definition: Utils.cpp:776
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:1547
bool isLoopParallelAndContainsReduction(AffineForOp forOp)
Returns whether a loop is a parallel loop and contains a reduction loop.
Definition: Utils.cpp:2095
unsigned getNumCommonSurroundingLoops(Operation &a, Operation &b)
Returns the number of surrounding loops common to both A and B.
Definition: Utils.cpp:2024
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:2007
void getSequentialLoops(AffineForOp forOp, llvm::SmallDenseSet< Value, 8 > *sequentialLoops)
Returns in 'sequentialLoops' all sequential loops in loop nest rooted at 'forOp'.
Definition: Utils.cpp:2104
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:762
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:2086
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:1515
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:1786
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:1376
unsigned getNestingDepth(Operation *op)
Returns the nesting depth of this operation, i.e., the number of loops surrounding this operation.
Definition: Utils.cpp:1979
uint64_t getSliceIterationCount(const llvm::SmallDenseMap< Operation *, uint64_t, 8 > &sliceTripCountMap)
Return the number of iterations for the slicetripCountMap provided.
Definition: Utils.cpp:1772
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:2304
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:1734
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:1898
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:2199
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:1332
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:310
std::optional< bool > isSliceValid() const
Checks the validity of the slice computed.
Definition: Utils.cpp:947
SmallVector< Value, 4 > ivs
Definition: Utils.h:313
LogicalResult getAsConstraints(FlatAffineValueConstraints *cst) const
Definition: Utils.cpp:809
bool isEmpty() const
Returns true if the computation slice is empty.
Definition: Utils.h:342
LogicalResult getSourceAsConstraints(FlatAffineValueConstraints &cst) const
Adds to 'cst' constraints which represent the original loop bounds on 'ivs' in 'this'.
Definition: Utils.cpp:793
std::vector< SmallVector< Value, 4 > > ubOperands
Definition: Utils.h:321
SmallVector< AffineMap, 4 > ubs
Definition: Utils.h:317
std::optional< bool > isMaximal() const
Returns true if the computation slice encloses all the iterations of the sliced loop nest.
Definition: Utils.cpp:1017
SmallVector< AffineMap, 4 > lbs
Definition: Utils.h:315
std::vector< SmallVector< Value, 4 > > lbOperands
Definition: Utils.h:319
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:44
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:131
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:150
Node(unsigned id, Operation *op)
Definition: Utils.h:85
unsigned hasFree(Value memref) const
Definition: Utils.cpp:124
SmallVector< Operation *, 4 > memrefLoads
Definition: Utils.h:75
SmallVector< Operation *, 4 > memrefStores
Definition: Utils.h:79
unsigned getLoadOpCount(Value memref) const
Definition: Utils.cpp:79
unsigned getStoreOpCount(Value memref) const
Definition: Utils.cpp:94
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:110
void getLoadOpsForMemref(Value memref, SmallVectorImpl< Operation * > *loadOps) const
Definition: Utils.cpp:140
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:262
unsigned addNode(Operation *op)
Definition: Utils.cpp:374
bool writesToLiveInOrEscapingMemrefs(unsigned id) const
Definition: Utils.cpp:404
Node * getForOpNode(AffineForOp forOp)
Definition: Utils.h:172
void removeEdge(unsigned srcId, unsigned dstId, Value value)
Definition: Utils.cpp:450
void addEdge(unsigned srcId, unsigned dstId, Value value)
Definition: Utils.cpp:439
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:538
bool hasDependencePath(unsigned srcId, unsigned dstId) const
Definition: Utils.cpp:477
void clearNodeLoadAndStores(unsigned id)
Definition: Utils.cpp:705
const Node * getForOpNode(AffineForOp forOp) const
Definition: Utils.cpp:366
Operation * getFusedLoopNestInsertionPoint(unsigned srcId, unsigned dstId) const
Definition: Utils.cpp:552
void updateEdges(unsigned srcId, unsigned dstId, const DenseSet< Value > &privateMemRefs, bool removeSrcId)
Definition: Utils.cpp:628
bool hasNode(unsigned id) const
Definition: Utils.h:168
DenseMap< unsigned, SmallVector< Edge, 2 > > inEdges
Definition: Utils.h:144
void forEachMemRefInputEdge(unsigned id, const std::function< void(Edge)> &callback)
Definition: Utils.cpp:713
unsigned getOutEdgeCount(unsigned id, Value memref=nullptr) const
Definition: Utils.cpp:528
const Node * getNode(unsigned id) const
Definition: Utils.cpp:359
void removeNode(unsigned id)
Definition: Utils.cpp:381
void forEachMemRefOutputEdge(unsigned id, const std::function< void(Edge)> &callback)
Definition: Utils.cpp:721
void forEachMemRefEdge(ArrayRef< Edge > edges, const std::function< void(Edge)> &callback)
Definition: Utils.cpp:729
void addToNode(unsigned id, ArrayRef< Operation * > loads, ArrayRef< Operation * > stores, ArrayRef< Operation * > memrefLoads, ArrayRef< Operation * > memrefStores, ArrayRef< Operation * > memrefFrees)
Definition: Utils.cpp:692
Node * getNode(unsigned id)
Definition: Utils.h:162
unsigned getIncomingMemRefAccesses(unsigned id, Value memref) const
Definition: Utils.cpp:512
bool hasEdge(unsigned srcId, unsigned dstId, Value value=nullptr) const
Definition: Utils.cpp:424
void print(raw_ostream &os) const
Definition: Utils.cpp:744
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:481
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:1071
FlatAffineValueConstraints * getConstraints()
Definition: Utils.h:527
unsigned getRank() const
Returns the rank of the memref that this region corresponds to.
Definition: Utils.cpp:1067
FlatAffineValueConstraints cst
Region (data space) of the memref accessed.
Definition: Utils.h:578
bool isWrite() const
Definition: Utils.h:529
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:1168
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:1127
std::optional< int64_t > getRegionSize()
Returns the size of this MemRefRegion in bytes.
Definition: Utils.cpp:1351
LogicalResult unionBoundingBox(const MemRefRegion &other)
Definition: Utils.cpp:1146
bool write
Read or write.
Definition: Utils.h:565
const FlatAffineValueConstraints * getConstraints() const
Definition: Utils.h:528
void setWrite(bool flag)
Definition: Utils.h:530
Value memref
Memref that this region corresponds to.
Definition: Utils.h:562
MemRefRegion(Location loc)
Definition: Utils.h:482
Location loc
If there is more than one load/store op associated with the region, the location information would co...
Definition: Utils.h:569
Enumerates different result statuses of slice computation by computeSliceUnion
Definition: Utils.h:297
SliceComputationResult(ResultEnum v)
Definition: Utils.h:303
enum mlir::affine::SliceComputationResult::ResultEnum value