MLIR  20.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.
42  bool hasNonAffineRegionOp = false;
43 
44  // Collects load and store operations, and whether or not a region holding op
45  // other than ForOp and IfOp was encountered in the loop nest.
46  void collect(Operation *opToWalk);
47 };
48 
49 // MemRefDependenceGraph is a graph data structure where graph nodes are
50 // top-level operations in a `Block` which contain load/store ops, and edges
51 // are memref dependences between the nodes.
52 // TODO: Add a more flexible dependence graph representation.
54 public:
55  // Node represents a node in the graph. A Node is either an entire loop nest
56  // rooted at the top level which contains loads/stores, or a top level
57  // load/store.
58  struct Node {
59  // The unique identifier of this node in the graph.
60  unsigned id;
61  // The top-level statement which is (or contains) a load/store.
63  // List of load operations.
65  // List of store op insts.
67 
68  Node(unsigned id, Operation *op) : id(id), op(op) {}
69 
70  // Returns the load op count for 'memref'.
71  unsigned getLoadOpCount(Value memref) const;
72 
73  // Returns the store op count for 'memref'.
74  unsigned getStoreOpCount(Value memref) const;
75 
76  // Returns all store ops in 'storeOps' which access 'memref'.
77  void getStoreOpsForMemref(Value memref,
78  SmallVectorImpl<Operation *> *storeOps) const;
79 
80  // Returns all load ops in 'loadOps' which access 'memref'.
81  void getLoadOpsForMemref(Value memref,
82  SmallVectorImpl<Operation *> *loadOps) const;
83 
84  // Returns all memrefs in 'loadAndStoreMemrefSet' for which this node
85  // has at least one load and store operation.
86  void getLoadAndStoreMemrefSet(DenseSet<Value> *loadAndStoreMemrefSet) const;
87  };
88 
89  // Edge represents a data dependence between nodes in the graph.
90  struct Edge {
91  // The id of the node at the other end of the edge.
92  // If this edge is stored in Edge = Node.inEdges[i], then
93  // 'Node.inEdges[i].id' is the identifier of the source node of the edge.
94  // If this edge is stored in Edge = Node.outEdges[i], then
95  // 'Node.outEdges[i].id' is the identifier of the dest node of the edge.
96  unsigned id;
97  // The SSA value on which this edge represents a dependence.
98  // If the value is a memref, then the dependence is between graph nodes
99  // which contain accesses to the same memref 'value'. If the value is a
100  // non-memref value, then the dependence is between a graph node which
101  // defines an SSA value and another graph node which uses the SSA value
102  // (e.g. a constant or load operation defining a value which is used inside
103  // a loop nest).
105  };
106 
107  // Map from node id to Node.
109  // Map from node id to list of input edges.
111  // Map from node id to list of output edges.
113  // Map from memref to a count on the dependence edges associated with that
114  // memref.
116  // The next unique identifier to use for newly created graph nodes.
117  unsigned nextNodeId = 0;
118 
120 
121  // Initializes the dependence graph based on operations in `block'.
122  // Returns true on success, false otherwise.
123  bool init();
124 
125  // Returns the graph node for 'id'.
126  Node *getNode(unsigned id);
127 
128  // Returns the graph node for 'forOp'.
129  Node *getForOpNode(AffineForOp forOp);
130 
131  // Adds a node with 'op' to the graph and returns its unique identifier.
132  unsigned addNode(Operation *op);
133 
134  // Remove node 'id' (and its associated edges) from graph.
135  void removeNode(unsigned id);
136 
137  // Returns true if node 'id' writes to any memref which escapes (or is an
138  // argument to) the block. Returns false otherwise.
139  bool writesToLiveInOrEscapingMemrefs(unsigned id);
140 
141  // Returns true iff there is an edge from node 'srcId' to node 'dstId' which
142  // is for 'value' if non-null, or for any value otherwise. Returns false
143  // otherwise.
144  bool hasEdge(unsigned srcId, unsigned dstId, Value value = nullptr);
145 
146  // Adds an edge from node 'srcId' to node 'dstId' for 'value'.
147  void addEdge(unsigned srcId, unsigned dstId, Value value);
148 
149  // Removes an edge from node 'srcId' to node 'dstId' for 'value'.
150  void removeEdge(unsigned srcId, unsigned dstId, Value value);
151 
152  // Returns true if there is a path in the dependence graph from node 'srcId'
153  // to node 'dstId'. Returns false otherwise. `srcId`, `dstId`, and the
154  // operations that the edges connected are expected to be from the same block.
155  bool hasDependencePath(unsigned srcId, unsigned dstId);
156 
157  // Returns the input edge count for node 'id' and 'memref' from src nodes
158  // which access 'memref' with a store operation.
159  unsigned getIncomingMemRefAccesses(unsigned id, Value memref);
160 
161  // Returns the output edge count for node 'id' and 'memref' (if non-null),
162  // otherwise returns the total output edge count from node 'id'.
163  unsigned getOutEdgeCount(unsigned id, Value memref = nullptr);
164 
165  /// Return all nodes which define SSA values used in node 'id'.
166  void gatherDefiningNodes(unsigned id, DenseSet<unsigned> &definingNodes);
167 
168  // Computes and returns an insertion point operation, before which the
169  // the fused <srcId, dstId> loop nest can be inserted while preserving
170  // dependences. Returns nullptr if no such insertion point is found.
171  Operation *getFusedLoopNestInsertionPoint(unsigned srcId, unsigned dstId);
172 
173  // Updates edge mappings from node 'srcId' to node 'dstId' after fusing them,
174  // taking into account that:
175  // *) if 'removeSrcId' is true, 'srcId' will be removed after fusion,
176  // *) memrefs in 'privateMemRefs' has been replaced in node at 'dstId' by a
177  // private memref.
178  void updateEdges(unsigned srcId, unsigned dstId,
179  const DenseSet<Value> &privateMemRefs, bool removeSrcId);
180 
181  // Update edge mappings for nodes 'sibId' and 'dstId' to reflect fusion
182  // of sibling node 'sibId' into node 'dstId'.
183  void updateEdges(unsigned sibId, unsigned dstId);
184 
185  // Adds ops in 'loads' and 'stores' to node at 'id'.
186  void addToNode(unsigned id, const SmallVectorImpl<Operation *> &loads,
187  const SmallVectorImpl<Operation *> &stores);
188 
189  void clearNodeLoadAndStores(unsigned id);
190 
191  // Calls 'callback' for each input edge incident to node 'id' which carries a
192  // memref dependence.
193  void forEachMemRefInputEdge(unsigned id,
194  const std::function<void(Edge)> &callback);
195 
196  // Calls 'callback' for each output edge from node 'id' which carries a
197  // memref dependence.
198  void forEachMemRefOutputEdge(unsigned id,
199  const std::function<void(Edge)> &callback);
200 
201  // Calls 'callback' for each edge in 'edges' which carries a memref
202  // dependence.
204  const std::function<void(Edge)> &callback);
205 
206  void print(raw_ostream &os) const;
207 
208  void dump() const { print(llvm::errs()); }
209 
210  /// The block for which this graph is created to perform fusion.
212 };
213 
214 /// Populates 'loops' with IVs of the affine.for ops surrounding 'op' ordered
215 /// from the outermost 'affine.for' operation to the innermost one while not
216 /// traversing outside of the surrounding affine scope.
218 
219 /// Populates 'ivs' with IVs of the surrounding affine.for and affine.parallel
220 /// ops ordered from the outermost one to the innermost while not traversing
221 /// outside of the surrounding affine scope.
223 
224 /// Populates 'ops' with affine operations enclosing `op` ordered from outermost
225 /// to innermost while stopping at the boundary of the affine scope. affine.for,
226 /// affine.if, or affine.parallel ops comprise such surrounding affine ops.
227 /// `ops` is guaranteed by design to have a successive chain of affine parent
228 /// ops.
230 
231 /// Returns the nesting depth of this operation, i.e., the number of loops
232 /// surrounding this operation.
233 unsigned getNestingDepth(Operation *op);
234 
235 /// Returns whether a loop is a parallel loop and contains a reduction loop.
236 bool isLoopParallelAndContainsReduction(AffineForOp forOp);
237 
238 /// Returns in 'sequentialLoops' all sequential loops in loop nest rooted
239 /// at 'forOp'.
240 void getSequentialLoops(AffineForOp forOp,
241  llvm::SmallDenseSet<Value, 8> *sequentialLoops);
242 
243 /// Enumerates different result statuses of slice computation by
244 /// `computeSliceUnion`
245 // TODO: Identify and add different kinds of failures during slice computation.
247  enum ResultEnum {
249  IncorrectSliceFailure, // Slice is computed, but it is incorrect.
250  GenericFailure, // Unable to compute src loop computation slice.
251  } value;
253 };
254 
255 /// ComputationSliceState aggregates loop IVs, loop bound AffineMaps and their
256 /// associated operands for a set of loops within a loop nest (typically the
257 /// set of loops surrounding a store operation). Loop bound AffineMaps which
258 /// are non-null represent slices of that loop's iteration space.
260  // List of sliced loop IVs (ordered from outermost to innermost).
261  // EX: 'ivs[i]' has lower bound 'lbs[i]' and upper bound 'ubs[i]'.
263  // List of lower bound AffineMaps.
265  // List of upper bound AffineMaps.
267  // List of lower bound operands (lbOperands[i] are used by 'lbs[i]').
268  std::vector<SmallVector<Value, 4>> lbOperands;
269  // List of upper bound operands (ubOperands[i] are used by 'ubs[i]').
270  std::vector<SmallVector<Value, 4>> ubOperands;
271  // Slice loop nest insertion point in target loop nest.
273  // Adds to 'cst' with constraints which represent the slice bounds on 'ivs'
274  // in 'this'. Specifically, the values in 'ivs' are added to 'cst' as dim
275  // variables and the values in 'lb/ubOperands' are added as symbols.
276  // Constraints are added for all loop IV bounds (dim or symbol), and
277  // constraints are added for slice bounds in 'lbs'/'ubs'.
278  // Returns failure if we cannot add loop bounds because of unsupported cases.
279  LogicalResult getAsConstraints(FlatAffineValueConstraints *cst) const;
280 
281  /// Adds to 'cst' constraints which represent the original loop bounds on
282  /// 'ivs' in 'this'. This corresponds to the original domain of the loop nest
283  /// from which the slice is being computed. Returns failure if we cannot add
284  /// loop bounds because of unsupported cases.
285  LogicalResult getSourceAsConstraints(FlatAffineValueConstraints &cst) const;
286 
287  // Clears all bounds and operands in slice state.
288  void clearBounds();
289 
290  /// Returns true if the computation slice is empty.
291  bool isEmpty() const { return ivs.empty(); }
292 
293  /// Returns true if the computation slice encloses all the iterations of the
294  /// sliced loop nest. Returns false if it does not. Returns std::nullopt if it
295  /// cannot determine if the slice is maximal or not.
296  // TODO: Cache 'isMaximal' so that we don't recompute it when the slice
297  // information hasn't changed.
298  std::optional<bool> isMaximal() const;
299 
300  /// Checks the validity of the slice computed. This is done using the
301  /// following steps:
302  /// 1. Get the new domain of the slice that would be created if fusion
303  /// succeeds. This domain gets constructed with source loop IVS and
304  /// destination loop IVS as dimensions.
305  /// 2. Project out the dimensions of the destination loop from the domain
306  /// above calculated in step(1) to express it purely in terms of the source
307  /// loop IVs.
308  /// 3. Calculate a set difference between the iterations of the new domain and
309  /// the original domain of the source loop.
310  /// If this difference is empty, the slice is declared to be valid. Otherwise,
311  /// return false as it implies that the effective fusion results in at least
312  /// one iteration of the slice that was not originally in the source's domain.
313  /// If the validity cannot be determined, returns std::nullopt.
314  std::optional<bool> isSliceValid() const;
315 
316  void dump() const;
317 
318 private:
319  /// Fast check to determine if the computation slice is maximal. Returns true
320  /// if each slice dimension maps to an existing dst dimension and both the src
321  /// and the dst loops for those dimensions have the same bounds. Returns false
322  /// if both the src and the dst loops don't have the same bounds. Returns
323  /// std::nullopt if none of the above can be proven.
324  std::optional<bool> isSliceMaximalFastCheck() const;
325 };
326 
327 /// Computes the computation slice loop bounds for one loop nest as affine maps
328 /// of the other loop nest's IVs and symbols, using 'dependenceConstraints'
329 /// computed between 'depSourceAccess' and 'depSinkAccess'.
330 /// If 'isBackwardSlice' is true, a backwards slice is computed in which the
331 /// slice bounds of loop nest surrounding 'depSourceAccess' are computed in
332 /// terms of loop IVs and symbols of the loop nest surrounding 'depSinkAccess'
333 /// at 'loopDepth'.
334 /// If 'isBackwardSlice' is false, a forward slice is computed in which the
335 /// slice bounds of loop nest surrounding 'depSinkAccess' are computed in terms
336 /// of loop IVs and symbols of the loop nest surrounding 'depSourceAccess' at
337 /// 'loopDepth'.
338 /// The slice loop bounds and associated operands are returned in 'sliceState'.
339 //
340 // Backward slice example:
341 //
342 // affine.for %i0 = 0 to 10 {
343 // affine.store %cst, %0[%i0] : memref<100xf32> // 'depSourceAccess'
344 // }
345 // affine.for %i1 = 0 to 10 {
346 // %v = affine.load %0[%i1] : memref<100xf32> // 'depSinkAccess'
347 // }
348 //
349 // // Backward computation slice of loop nest '%i0'.
350 // affine.for %i0 = (d0) -> (d0)(%i1) to (d0) -> (d0 + 1)(%i1) {
351 // affine.store %cst, %0[%i0] : memref<100xf32> // 'depSourceAccess'
352 // }
353 //
354 // Forward slice example:
355 //
356 // affine.for %i0 = 0 to 10 {
357 // affine.store %cst, %0[%i0] : memref<100xf32> // 'depSourceAccess'
358 // }
359 // affine.for %i1 = 0 to 10 {
360 // %v = affine.load %0[%i1] : memref<100xf32> // 'depSinkAccess'
361 // }
362 //
363 // // Forward computation slice of loop nest '%i1'.
364 // affine.for %i1 = (d0) -> (d0)(%i0) to (d0) -> (d0 + 1)(%i0) {
365 // %v = affine.load %0[%i1] : memref<100xf32> // 'depSinkAccess'
366 // }
367 //
368 void getComputationSliceState(Operation *depSourceOp, Operation *depSinkOp,
369  FlatAffineValueConstraints *dependenceConstraints,
370  unsigned loopDepth, bool isBackwardSlice,
371  ComputationSliceState *sliceState);
372 
373 /// Return the number of iterations for the `slicetripCountMap` provided.
374 uint64_t getSliceIterationCount(
375  const llvm::SmallDenseMap<Operation *, uint64_t, 8> &sliceTripCountMap);
376 
377 /// Builds a map 'tripCountMap' from AffineForOp to constant trip count for
378 /// loop nest surrounding represented by slice loop bounds in 'slice'. Returns
379 /// true on success, false otherwise (if a non-constant trip count was
380 /// encountered).
382  const ComputationSliceState &slice,
383  llvm::SmallDenseMap<Operation *, uint64_t, 8> *tripCountMap);
384 
385 /// Computes in 'sliceUnion' the union of all slice bounds computed at
386 /// 'loopDepth' between all dependent pairs of ops in 'opsA' and 'opsB', and
387 /// then verifies if it is valid. The parameter 'numCommonLoops' is the number
388 /// of loops common to the operations in 'opsA' and 'opsB'. If 'isBackwardSlice'
389 /// is true, computes slice bounds for loop nest surrounding ops in 'opsA', as a
390 /// function of IVs and symbols of loop nest surrounding ops in 'opsB' at
391 /// 'loopDepth'. If 'isBackwardSlice' is false, computes slice bounds for loop
392 /// nest surrounding ops in 'opsB', as a function of IVs and symbols of loop
393 /// nest surrounding ops in 'opsA' at 'loopDepth'. Returns
394 /// 'SliceComputationResult::Success' if union was computed correctly, an
395 /// appropriate 'failure' otherwise.
396 SliceComputationResult
398  unsigned loopDepth, unsigned numCommonLoops,
399  bool isBackwardSlice, ComputationSliceState *sliceUnion);
400 
401 /// Creates a clone of the computation contained in the loop nest surrounding
402 /// 'srcOpInst', slices the iteration space of src loop based on slice bounds
403 /// in 'sliceState', and inserts the computation slice at the beginning of the
404 /// operation block of the loop at 'dstLoopDepth' in the loop nest surrounding
405 /// 'dstOpInst'. Returns the top-level loop of the computation slice on
406 /// success, returns nullptr otherwise.
407 // Loop depth is a crucial optimization choice that determines where to
408 // materialize the results of the backward slice - presenting a trade-off b/w
409 // storage and redundant computation in several cases.
410 // TODO: Support computation slices with common surrounding loops.
411 AffineForOp insertBackwardComputationSlice(Operation *srcOpInst,
412  Operation *dstOpInst,
413  unsigned dstLoopDepth,
414  ComputationSliceState *sliceState);
415 
416 /// A region of a memref's data space; this is typically constructed by
417 /// analyzing load/store op's on this memref and the index space of loops
418 /// surrounding such op's.
419 // For example, the memref region for a load operation at loop depth = 1:
420 //
421 // affine.for %i = 0 to 32 {
422 // affine.for %ii = %i to (d0) -> (d0 + 8) (%i) {
423 // affine.load %A[%ii]
424 // }
425 // }
426 //
427 // Region: {memref = %A, write = false, {%i <= m0 <= %i + 7} }
428 // The last field is a 2-d FlatAffineValueConstraints symbolic in %i.
429 //
430 struct MemRefRegion {
431  explicit MemRefRegion(Location loc) : loc(loc) {}
432 
433  /// Computes the memory region accessed by this memref with the region
434  /// represented as constraints symbolic/parametric in 'loopDepth' loops
435  /// surrounding opInst. The computed region's 'cst' field has exactly as many
436  /// dimensional variables as the rank of the memref, and *potentially*
437  /// additional symbolic variables which could include any of the loop IVs
438  /// surrounding opInst up until 'loopDepth' and another additional Function
439  /// symbols involved with the access (for eg., those appear in affine.apply's,
440  /// loop bounds, etc.). If 'sliceState' is non-null, operands from
441  /// 'sliceState' are added as symbols, and the following constraints are added
442  /// to the system:
443  /// *) Inequality constraints which represent loop bounds for 'sliceState'
444  /// operands which are loop IVS (these represent the destination loop IVs
445  /// of the slice, and are added as symbols to MemRefRegion's constraint
446  /// system).
447  /// *) Inequality constraints for the slice bounds in 'sliceState', which
448  /// represent the bounds on the loop IVs in this constraint system w.r.t
449  /// to slice operands (which correspond to symbols).
450  /// If 'addMemRefDimBounds' is true, constant upper/lower bounds
451  /// [0, memref.getDimSize(i)) are added for each MemRef dimension 'i'.
452  ///
453  /// For example, the memref region for this operation at loopDepth = 1 will
454  /// be:
455  ///
456  /// affine.for %i = 0 to 32 {
457  /// affine.for %ii = %i to (d0) -> (d0 + 8) (%i) {
458  /// load %A[%ii]
459  /// }
460  /// }
461  ///
462  /// {memref = %A, write = false, {%i <= m0 <= %i + 7} }
463  /// The last field is a 2-d FlatAffineValueConstraints symbolic in %i.
464  ///
465  LogicalResult compute(Operation *op, unsigned loopDepth,
466  const ComputationSliceState *sliceState = nullptr,
467  bool addMemRefDimBounds = true);
468 
470  const FlatAffineValueConstraints *getConstraints() const { return &cst; }
471  bool isWrite() const { return write; }
472  void setWrite(bool flag) { write = flag; }
473 
474  /// Returns a constant upper bound on the number of elements in this region if
475  /// bounded by a known constant (always possible for static shapes),
476  /// std::nullopt otherwise. Note that the symbols of the region are treated
477  /// specially, i.e., the returned bounding constant holds for *any given*
478  /// value of the symbol variables. The 'shape' vector is set to the
479  /// corresponding dimension-wise bounds major to minor. The number of elements
480  /// and all the dimension-wise bounds are guaranteed to be non-negative. We
481  /// use int64_t instead of uint64_t since index types can be at most
482  /// int64_t. `lbs` are set to the lower bounds for each of the rank
483  /// dimensions, and lbDivisors contains the corresponding denominators for
484  /// floorDivs.
485  std::optional<int64_t> getConstantBoundingSizeAndShape(
486  SmallVectorImpl<int64_t> *shape = nullptr,
487  std::vector<SmallVector<int64_t, 4>> *lbs = nullptr,
488  SmallVectorImpl<int64_t> *lbDivisors = nullptr) const;
489 
490  /// Gets the lower and upper bound map for the dimensional variable at
491  /// `pos`.
492  void getLowerAndUpperBound(unsigned pos, AffineMap &lbMap,
493  AffineMap &ubMap) const;
494 
495  /// A wrapper around FlatAffineValueConstraints::getConstantBoundOnDimSize().
496  /// 'pos' corresponds to the position of the memref shape's dimension (major
497  /// to minor) which matches 1:1 with the dimensional variable positions in
498  /// 'cst'.
499  std::optional<int64_t>
501  SmallVectorImpl<int64_t> *lb = nullptr,
502  int64_t *lbFloorDivisor = nullptr) const {
503  assert(pos < getRank() && "invalid position");
504  return cst.getConstantBoundOnDimSize64(pos, lb);
505  }
506 
507  /// Returns the size of this MemRefRegion in bytes.
508  std::optional<int64_t> getRegionSize();
509 
510  // Wrapper around FlatAffineValueConstraints::unionBoundingBox.
511  LogicalResult unionBoundingBox(const MemRefRegion &other);
512 
513  /// Returns the rank of the memref that this region corresponds to.
514  unsigned getRank() const;
515 
516  /// Memref that this region corresponds to.
518 
519  /// Read or write.
520  bool write = false;
521 
522  /// If there is more than one load/store op associated with the region, the
523  /// location information would correspond to one of those op's.
525 
526  /// Region (data space) of the memref accessed. This set will thus have at
527  /// least as many dimensional variables as the shape dimensionality of the
528  /// memref, and these are the leading dimensions of the set appearing in that
529  /// order (major to minor / outermost to innermost). There may be additional
530  /// variables since getMemRefRegion() is called with a specific loop depth,
531  /// and thus the region is symbolic in the outer surrounding loops at that
532  /// depth.
534 };
535 
536 /// Returns the size of a memref with element type int or float in bytes if it's
537 /// statically shaped, std::nullopt otherwise.
538 std::optional<uint64_t> getIntOrFloatMemRefSizeInBytes(MemRefType memRefType);
539 
540 /// Checks a load or store op for an out of bound access; returns failure if the
541 /// access is out of bounds along any of the dimensions, success otherwise.
542 /// Emits a diagnostic error (with location information) if emitError is true.
543 template <typename LoadOrStoreOpPointer>
544 LogicalResult boundCheckLoadOrStoreOp(LoadOrStoreOpPointer loadOrStoreOp,
545  bool emitError = true);
546 
547 /// Returns the number of surrounding loops common to both A and B.
549 
550 /// Gets the memory footprint of all data touched in the specified memory space
551 /// in bytes; if the memory space is unspecified, considers all memory spaces.
552 std::optional<int64_t> getMemoryFootprintBytes(AffineForOp forOp,
553  int memorySpace = -1);
554 
555 /// Returns the memref's element type's size in bytes where the elemental type
556 /// is an int or float or a vector of such types.
557 std::optional<int64_t> getMemRefIntOrFloatEltSizeInBytes(MemRefType memRefType);
558 
559 /// Simplify the integer set by simplifying the underlying affine expressions by
560 /// flattening and some simple inference. Also, drop any duplicate constraints.
561 /// Returns the simplified integer set. This method runs in time linear in the
562 /// number of constraints.
564 
565 /// Returns the innermost common loop depth for the set of operations in 'ops'.
568  SmallVectorImpl<AffineForOp> *surroundingLoops = nullptr);
569 
570 /// Try to simplify the given affine.min or affine.max op to an affine map with
571 /// a single result and operands, taking into account the specified constraint
572 /// set. Return failure if no simplified version could be found.
573 FailureOr<AffineValueMap>
575  FlatAffineValueConstraints constraints);
576 
577 } // namespace affine
578 } // namespace mlir
579 
580 #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:31
OpListType::iterator iterator
Definition: Block.h:138
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...
std::optional< int64_t > getConstantBoundOnDimSize64(unsigned pos, SmallVectorImpl< int64_t > *lb=nullptr, int64_t *boundFloorDivisor=nullptr, SmallVectorImpl< int64_t > *ub=nullptr, unsigned *minLbPos=nullptr, unsigned *minUbPos=nullptr) const
The same, but casts to int64_t.
IntegerSet simplifyIntegerSet(IntegerSet set)
Simplify the integer set by simplifying the underlying affine expressions by flattening and some simp...
Definition: Utils.cpp:1980
void getEnclosingAffineOps(Operation &op, SmallVectorImpl< Operation * > *ops)
Populates 'ops' with affine operations enclosing op ordered from outermost to innermost while stoppin...
Definition: Utils.cpp:647
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:1417
bool isLoopParallelAndContainsReduction(AffineForOp forOp)
Returns whether a loop is a parallel loop and contains a reduction loop.
Definition: Utils.cpp:1962
unsigned getNumCommonSurroundingLoops(Operation &a, Operation &b)
Returns the number of surrounding loops common to both A and B.
Definition: Utils.cpp:1893
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:1876
void getComputationSliceState(Operation *depSourceOp, Operation *depSinkOp, 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:1653
void getSequentialLoops(AffineForOp forOp, llvm::SmallDenseSet< Value, 8 > *sequentialLoops)
Returns in 'sequentialLoops' all sequential loops in loop nest rooted at 'forOp'.
Definition: Utils.cpp:1971
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:633
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:1953
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:1385
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:1246
unsigned getNestingDepth(Operation *op)
Returns the nesting depth of this operation, i.e., the number of loops surrounding this operation.
Definition: Utils.cpp:1848
uint64_t getSliceIterationCount(const llvm::SmallDenseMap< Operation *, uint64_t, 8 > &sliceTripCountMap)
Return the number of iterations for the slicetripCountMap provided.
Definition: Utils.cpp:1639
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 ...
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:1601
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:1767
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:2066
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:1196
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:259
std::optional< bool > isSliceValid() const
Checks the validity of the slice computed.
Definition: Utils.cpp:818
SmallVector< Value, 4 > ivs
Definition: Utils.h:262
LogicalResult getAsConstraints(FlatAffineValueConstraints *cst) const
Definition: Utils.cpp:680
bool isEmpty() const
Returns true if the computation slice is empty.
Definition: Utils.h:291
LogicalResult getSourceAsConstraints(FlatAffineValueConstraints &cst) const
Adds to 'cst' constraints which represent the original loop bounds on 'ivs' in 'this'.
Definition: Utils.cpp:664
std::vector< SmallVector< Value, 4 > > ubOperands
Definition: Utils.h:270
SmallVector< AffineMap, 4 > ubs
Definition: Utils.h:266
std::optional< bool > isMaximal() const
Returns true if the computation slice encloses all the iterations of the sliced loop nest.
Definition: Utils.cpp:888
SmallVector< AffineMap, 4 > lbs
Definition: Utils.h:264
std::vector< SmallVector< Value, 4 > > lbOperands
Definition: Utils.h:268
SmallVector< AffineForOp, 4 > forOps
Definition: Utils.h:39
SmallVector< Operation *, 4 > loadOpInsts
Definition: Utils.h:40
void collect(Operation *opToWalk)
Definition: Utils.cpp:43
SmallVector< Operation *, 4 > storeOpInsts
Definition: Utils.h:41
void getStoreOpsForMemref(Value memref, SmallVectorImpl< Operation * > *storeOps) const
Definition: Utils.cpp:77
SmallVector< Operation *, 4 > loads
Definition: Utils.h:64
SmallVector< Operation *, 4 > stores
Definition: Utils.h:66
void getLoadAndStoreMemrefSet(DenseSet< Value > *loadAndStoreMemrefSet) const
Definition: Utils.cpp:96
Node(unsigned id, Operation *op)
Definition: Utils.h:68
unsigned getLoadOpCount(Value memref) const
Definition: Utils.cpp:57
unsigned getStoreOpCount(Value memref) const
Definition: Utils.cpp:67
void getLoadOpsForMemref(Value memref, SmallVectorImpl< Operation * > *loadOps) const
Definition: Utils.cpp:86
DenseMap< unsigned, SmallVector< Edge, 2 > > outEdges
Definition: Utils.h:112
Block & block
The block for which this graph is created to perform fusion.
Definition: Utils.h:211
unsigned addNode(Operation *op)
Definition: Utils.cpp:251
unsigned getIncomingMemRefAccesses(unsigned id, Value memref)
Definition: Utils.cpp:388
void removeEdge(unsigned srcId, unsigned dstId, Value value)
Definition: Utils.cpp:327
void addEdge(unsigned srcId, unsigned dstId, Value value)
Definition: Utils.cpp:316
Node * getForOpNode(AffineForOp forOp)
Definition: Utils.cpp:243
MemRefDependenceGraph(Block &block)
Definition: Utils.h:119
DenseMap< unsigned, Node > nodes
Definition: Utils.h:108
bool hasDependencePath(unsigned srcId, unsigned dstId)
Definition: Utils.cpp:354
void clearNodeLoadAndStores(unsigned id)
Definition: Utils.cpp:576
void updateEdges(unsigned srcId, unsigned dstId, const DenseSet< Value > &privateMemRefs, bool removeSrcId)
Definition: Utils.cpp:504
DenseMap< unsigned, SmallVector< Edge, 2 > > inEdges
Definition: Utils.h:110
bool writesToLiveInOrEscapingMemrefs(unsigned id)
Definition: Utils.cpp:281
void addToNode(unsigned id, const SmallVectorImpl< Operation * > &loads, const SmallVectorImpl< Operation * > &stores)
Definition: Utils.cpp:568
void forEachMemRefInputEdge(unsigned id, const std::function< void(Edge)> &callback)
Definition: Utils.cpp:584
unsigned getOutEdgeCount(unsigned id, Value memref=nullptr)
Definition: Utils.cpp:404
void removeNode(unsigned id)
Definition: Utils.cpp:258
Operation * getFusedLoopNestInsertionPoint(unsigned srcId, unsigned dstId)
Definition: Utils.cpp:428
void forEachMemRefOutputEdge(unsigned id, const std::function< void(Edge)> &callback)
Definition: Utils.cpp:592
void forEachMemRefEdge(ArrayRef< Edge > edges, const std::function< void(Edge)> &callback)
Definition: Utils.cpp:600
bool hasEdge(unsigned srcId, unsigned dstId, Value value=nullptr)
Definition: Utils.cpp:301
void gatherDefiningNodes(unsigned id, DenseSet< unsigned > &definingNodes)
Return all nodes which define SSA values used in node 'id'.
Definition: Utils.cpp:414
Node * getNode(unsigned id)
Definition: Utils.cpp:236
void print(raw_ostream &os) const
Definition: Utils.cpp:615
DenseMap< Value, unsigned > memrefEdgeCount
Definition: Utils.h:115
A region of a memref's data space; this is typically constructed by analyzing load/store op's on this...
Definition: Utils.h:430
FlatAffineValueConstraints * getConstraints()
Definition: Utils.h:469
unsigned getRank() const
Returns the rank of the memref that this region corresponds to.
Definition: Utils.cpp:938
FlatAffineValueConstraints cst
Region (data space) of the memref accessed.
Definition: Utils.h:533
bool isWrite() const
Definition: Utils.h:471
std::optional< int64_t > getConstantBoundOnDimSize(unsigned pos, SmallVectorImpl< int64_t > *lb=nullptr, int64_t *lbFloorDivisor=nullptr) const
A wrapper around FlatAffineValueConstraints::getConstantBoundOnDimSize().
Definition: Utils.h:500
std::optional< int64_t > getConstantBoundingSizeAndShape(SmallVectorImpl< int64_t > *shape=nullptr, std::vector< SmallVector< int64_t, 4 >> *lbs=nullptr, SmallVectorImpl< int64_t > *lbDivisors=nullptr) const
Returns a constant upper bound on the number of elements in this region if bounded by a known constan...
Definition: Utils.cpp:942
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:1003
std::optional< int64_t > getRegionSize()
Returns the size of this MemRefRegion in bytes.
Definition: Utils.cpp:1215
LogicalResult unionBoundingBox(const MemRefRegion &other)
Definition: Utils.cpp:1022
bool write
Read or write.
Definition: Utils.h:520
const FlatAffineValueConstraints * getConstraints() const
Definition: Utils.h:470
void setWrite(bool flag)
Definition: Utils.h:472
Value memref
Memref that this region corresponds to.
Definition: Utils.h:517
MemRefRegion(Location loc)
Definition: Utils.h:431
LogicalResult compute(Operation *op, unsigned loopDepth, const ComputationSliceState *sliceState=nullptr, bool addMemRefDimBounds=true)
Computes the memory region accessed by this memref with the region represented as constraints symboli...
Definition: Utils.cpp:1044
Location loc
If there is more than one load/store op associated with the region, the location information would co...
Definition: Utils.h:524
Enumerates different result statuses of slice computation by computeSliceUnion
Definition: Utils.h:246
SliceComputationResult(ResultEnum v)
Definition: Utils.h:252
enum mlir::affine::SliceComputationResult::ResultEnum value