diff --git a/mlir/include/mlir/Dialect/Affine/LoopUtils.h b/mlir/include/mlir/Dialect/Affine/LoopUtils.h --- a/mlir/include/mlir/Dialect/Affine/LoopUtils.h +++ b/mlir/include/mlir/Dialect/Affine/LoopUtils.h @@ -104,7 +104,8 @@ std::vector> *bands); /// Tiles the specified band of perfectly nested loops creating tile-space loops -/// and intra-tile loops. A band is a contiguous set of loops. +/// and intra-tile loops. A band is a contiguous set of loops. This utility +/// doesn't check for the validity of tiling itself, but just performs it. LogicalResult tilePerfectlyNested(MutableArrayRef input, ArrayRef tileSizes, diff --git a/mlir/lib/Dialect/Affine/Transforms/LoopTiling.cpp b/mlir/lib/Dialect/Affine/Transforms/LoopTiling.cpp --- a/mlir/lib/Dialect/Affine/Transforms/LoopTiling.cpp +++ b/mlir/lib/Dialect/Affine/Transforms/LoopTiling.cpp @@ -89,6 +89,70 @@ } } +/// Checks whether hyper-rectangular loop tiling of the nest represented by +/// `origLoops` is valid. The validity condition is from Irigoin and Triolet, +/// which states that two tiles cannot depend on each other. We simplify such +/// condition to just checking whether there is any negative dependence +/// direction, since we have the prior knowledge that the tiling results will be +/// hyper-rectangles, which are scheduled in the lexicographically increasing +/// order on the vector of loop indices. This function will return failure when +/// any dependence component is negative along any of `origLoops`. +static bool checkTilingLegality(MutableArrayRef origLoops) { + assert(!origLoops.empty() && "no original loops provided"); + + // We first find out all dependences we intend to check. + SmallVector loadAndStoreOps; + origLoops[0]->walk([&](Operation *op) { + if (isa(op)) + loadAndStoreOps.push_back(op); + }); + + unsigned numOps = loadAndStoreOps.size(); + unsigned numLoops = origLoops.size(); + for (unsigned d = 1; d <= numLoops + 1; ++d) { + for (unsigned i = 0; i < numOps; ++i) { + Operation *srcOp = loadAndStoreOps[i]; + MemRefAccess srcAccess(srcOp); + for (unsigned j = 0; j < numOps; ++j) { + Operation *dstOp = loadAndStoreOps[j]; + MemRefAccess dstAccess(dstOp); + + SmallVector depComps; + DependenceResult result = checkMemrefAccessDependence( + srcAccess, dstAccess, d, /*dependenceConstraints=*/nullptr, + &depComps); + + // Skip if there is no dependence in this case. + if (!hasDependence(result)) + continue; + + // Check whether there is any negative direction vector in the + // dependence components found above, which means that dependence is + // violated by the default hyper-rect tiling method. + LLVM_DEBUG(llvm::dbgs() << "Checking whether tiling legality violated " + "for dependence at depth: " + << Twine(d) << " between:\n";); + LLVM_DEBUG(srcAccess.opInst->dump();); + LLVM_DEBUG(dstAccess.opInst->dump();); + for (unsigned k = 0, e = depComps.size(); k < e; k++) { + DependenceComponent depComp = depComps[k]; + if (depComp.lb.has_value() && depComp.ub.has_value() && + *depComp.lb < *depComp.ub && *depComp.ub < 0) { + LLVM_DEBUG(llvm::dbgs() + << "Dependence component lb = " << Twine(*depComp.lb) + << " ub = " << Twine(*depComp.ub) + << " is negative at depth: " << Twine(d) + << " and thus violates the legality rule.\n"); + return false; + } + } + } + } + } + + return true; +} + // Returns tile sizes to use. Checks CL options; if none are specified, sets it // based on a simple model that looks at the memory footprint and determines // tile sizes assuming identity accesses / 1:1 tile size proportional footprint @@ -175,6 +239,11 @@ // Tile each band. for (auto &band : bands) { + if (!checkTilingLegality(band)) { + band.front().emitRemark("tiling code is illegal due to dependences"); + continue; + } + // Set up tile sizes; fill missing tile sizes at the end with default tile // size or tileSize if one was provided. SmallVector tileSizes; diff --git a/mlir/lib/Dialect/Affine/Utils/LoopUtils.cpp b/mlir/lib/Dialect/Affine/Utils/LoopUtils.cpp --- a/mlir/lib/Dialect/Affine/Utils/LoopUtils.cpp +++ b/mlir/lib/Dialect/Affine/Utils/LoopUtils.cpp @@ -362,80 +362,6 @@ return success(); } -/// Checks the legality of tiling of a hyper-rectangular loop nest by simply -/// checking if there is a 'negative' dependence in the memrefs present in -/// the loop nest. If yes then tiling is invalid. -static bool -checkTilingLegalityImpl(MutableArrayRef origLoops) { - assert(!origLoops.empty() && "no original loops provided"); - - // We first find out all dependences we intend to check. - SmallVector loadAndStoreOps; - origLoops[0]->walk([&](Operation *op) { - if (isa(op)) - loadAndStoreOps.push_back(op); - }); - - unsigned numOps = loadAndStoreOps.size(); - unsigned numLoops = origLoops.size(); - for (unsigned d = 1; d <= numLoops + 1; ++d) { - for (unsigned i = 0; i < numOps; ++i) { - Operation *srcOp = loadAndStoreOps[i]; - MemRefAccess srcAccess(srcOp); - for (unsigned j = 0; j < numOps; ++j) { - Operation *dstOp = loadAndStoreOps[j]; - MemRefAccess dstAccess(dstOp); - - SmallVector depComps; - DependenceResult result = checkMemrefAccessDependence( - srcAccess, dstAccess, d, /*dependenceConstraints=*/nullptr, - &depComps); - - // Skip if there is no dependence in this case. - if (!hasDependence(result)) - continue; - - // Check whether there is any negative direction vector in the - // dependence components found above, which means that dependence is - // violated by the default hyper-rect tiling method. - LLVM_DEBUG(llvm::dbgs() << "Checking whether tiling legality violated " - "for dependence at depth: " - << Twine(d) << " between:\n";); - LLVM_DEBUG(srcAccess.opInst->dump();); - LLVM_DEBUG(dstAccess.opInst->dump();); - for (unsigned k = 0, e = depComps.size(); k < e; k++) { - DependenceComponent depComp = depComps[k]; - if (depComp.lb.has_value() && depComp.ub.has_value() && - *depComp.lb < *depComp.ub && *depComp.ub < 0) { - LLVM_DEBUG(llvm::dbgs() - << "Dependence component lb = " << Twine(*depComp.lb) - << " ub = " << Twine(*depComp.ub) - << " is negative at depth: " << Twine(d) - << " and thus violates the legality rule.\n"); - return false; - } - } - } - } - } - - return true; -} - -/// Checks whether hyper-rectangular loop tiling of the nest -/// represented by `origLoops` is valid. The validity condition is from Irigoin -/// and Triolet, which states that two tiles cannot depend on each other. We -/// simplify such condition to just checking whether there is any negative -/// dependence direction, since we have the prior knowledge that the tiling -/// results will be hyper-rectangles, which are scheduled in the -/// lexicographically increasing order on the vector of loop indices. This -/// function will return failure when any dependence component is negative along -/// any of `origLoops`. -LogicalResult -checkTilingLegality(MutableArrayRef origLoops) { - return success(checkTilingLegalityImpl(origLoops)); -} - /// Checks whether a loop nest is hyper-rectangular or not. LogicalResult checkIfHyperRectangular(MutableArrayRef input) { FlatAffineValueConstraints cst; @@ -478,12 +404,6 @@ if (failed(checkIfHyperRectangular(input))) return failure(); - // Check if tiling is legal. - if (failed(checkTilingLegality(input))) { - input[0].emitRemark("tiling code is illegal due to dependences"); - return failure(); - } - return success(); } @@ -852,9 +772,6 @@ } } -/// Tiles the specified band of perfectly nested loops creating tile-space loops -/// and intra-tile loops. A band is a contiguous set of loops. -// TODO: handle non hyper-rectangular spaces. LogicalResult mlir::tilePerfectlyNested(MutableArrayRef input, ArrayRef tileSizes,