llvm / llvm-project / 746e632dafbec2277c62164b3e63da4bee1d8553 / . / mlir / include / mlir / Analysis / LoopAnalysis.h

//===- LoopAnalysis.h - loop analysis methods -------------------*- C++ -*-===// | |

// | |

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |

// See https://llvm.org/LICENSE.txt for license information. | |

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |

// | |

//===----------------------------------------------------------------------===// | |

// | |

// This header file defines prototypes for methods to analyze loops. | |

// | |

//===----------------------------------------------------------------------===// | |

#ifndef MLIR_ANALYSIS_LOOP_ANALYSIS_H | |

#define MLIR_ANALYSIS_LOOP_ANALYSIS_H | |

#include "mlir/Support/LLVM.h" | |

#include "llvm/ADT/ArrayRef.h" | |

#include "llvm/ADT/Optional.h" | |

namespace mlir { | |

class AffineExpr; | |

class AffineForOp; | |

class AffineMap; | |

class BlockArgument; | |

class MemRefType; | |

class NestedPattern; | |

class Operation; | |

class Value; | |

/// Returns the trip count of the loop as an affine map with its corresponding | |

/// operands if the latter is expressible as an affine expression, and nullptr | |

/// otherwise. This method always succeeds as long as the lower bound is not a | |

/// multi-result map. The trip count expression is simplified before returning. | |

/// This method only utilizes map composition to construct lower and upper | |

/// bounds before computing the trip count expressions | |

void getTripCountMapAndOperands(AffineForOp forOp, AffineMap *map, | |

SmallVectorImpl<Value> *operands); | |

/// Returns the trip count of the loop if it's a constant, None otherwise. This | |

/// uses affine expression analysis and is able to determine constant trip count | |

/// in non-trivial cases. | |

Optional<uint64_t> getConstantTripCount(AffineForOp forOp); | |

/// Returns the greatest known integral divisor of the trip count. Affine | |

/// expression analysis is used (indirectly through getTripCount), and | |

/// this method is thus able to determine non-trivial divisors. | |

uint64_t getLargestDivisorOfTripCount(AffineForOp forOp); | |

/// Given an induction variable `iv` of type AffineForOp and `indices` of type | |

/// IndexType, returns the set of `indices` that are independent of `iv`. | |

/// | |

/// Prerequisites (inherited from `isAccessInvariant` above): | |

/// 1. `iv` and `indices` of the proper type; | |

/// 2. at most one affine.apply is reachable from each index in `indices`; | |

/// | |

/// Emits a note if it encounters a chain of affine.apply and conservatively | |

/// those cases. | |

DenseSet<Value, DenseMapInfo<Value>> | |

getInvariantAccesses(Value iv, ArrayRef<Value> indices); | |

using VectorizableLoopFun = std::function<bool(AffineForOp)>; | |

/// Checks whether the loop is structurally vectorizable; i.e.: | |

/// 1. no conditionals are nested under the loop; | |

/// 2. all nested load/stores are to scalar MemRefs. | |

/// TODO: relax the no-conditionals restriction | |

bool isVectorizableLoopBody(AffineForOp loop, | |

NestedPattern &vectorTransferMatcher); | |

/// Checks whether the loop is structurally vectorizable and that all the LoadOp | |

/// and StoreOp matched have access indexing functions that are are either: | |

/// 1. invariant along the loop induction variable created by 'loop'; | |

/// 2. varying along at most one memory dimension. If such a unique dimension | |

/// is found, it is written into `memRefDim`. | |

bool isVectorizableLoopBody(AffineForOp loop, int *memRefDim, | |

NestedPattern &vectorTransferMatcher); | |

/// Checks where SSA dominance would be violated if a for op's body | |

/// operations are shifted by the specified shifts. This method checks if a | |

/// 'def' and all its uses have the same shift factor. | |

// TODO: extend this to check for memory-based dependence violation when we have | |

// the support. | |

bool isOpwiseShiftValid(AffineForOp forOp, ArrayRef<uint64_t> shifts); | |

/// Utility to match a generic reduction given a list of iteration-carried | |

/// arguments, `iterCarriedArgs` and the position of the potential reduction | |

/// argument within the list, `redPos`. If a reduction is matched, returns the | |

/// reduced value and the topologically-sorted list of combiner operations | |

/// involved in the reduction. Otherwise, returns a null value. | |

/// | |

/// The matching algorithm relies on the following invariants, which are subject | |

/// to change: | |

/// 1. The first combiner operation must be a binary operation with the | |

/// iteration-carried value and the reduced value as operands. | |

/// 2. The iteration-carried value and combiner operations must be side | |

/// effect-free, have single result and a single use. | |

/// 3. Combiner operations must be immediately nested in the region op | |

/// performing the reduction. | |

/// 4. Reduction def-use chain must end in a terminator op that yields the | |

/// next iteration/output values in the same order as the iteration-carried | |

/// values in `iterCarriedArgs`. | |

/// 5. `iterCarriedArgs` must contain all the iteration-carried/output values | |

/// of the region op performing the reduction. | |

/// | |

/// This utility is generic enough to detect reductions involving multiple | |

/// combiner operations (disabled for now) across multiple dialects, including | |

/// Linalg, Affine and SCF. For the sake of genericity, it does not return | |

/// specific enum values for the combiner operations since its goal is also | |

/// matching reductions without pre-defined semantics in core MLIR. It's up to | |

/// each client to make sense out of the list of combiner operations. It's also | |

/// up to each client to check for additional invariants on the expected | |

/// reductions not covered by this generic matching. | |

Value matchReduction(ArrayRef<BlockArgument> iterCarriedArgs, unsigned redPos, | |

SmallVectorImpl<Operation *> &combinerOps); | |

} // end namespace mlir | |

#endif // MLIR_ANALYSIS_LOOP_ANALYSIS_H |