Index: mlir/include/mlir/Dialect/Affine/Utils.h =================================================================== --- mlir/include/mlir/Dialect/Affine/Utils.h +++ mlir/include/mlir/Dialect/Affine/Utils.h @@ -13,7 +13,11 @@ #ifndef MLIR_DIALECT_AFFINE_UTILS_H #define MLIR_DIALECT_AFFINE_UTILS_H +#include #include "mlir/Dialect/Affine/Analysis/AffineAnalysis.h" +#include "mlir/Dialect/Affine/Analysis/Utils.h" +#include "mlir/Dialect/Affine/IR/AffineOps.h" +#include "llvm/ADT/SmallPtrSet.h" namespace mlir { @@ -319,6 +323,191 @@ Value linearIndex, ArrayRef basis); +/// Ensure that all operations that could be executed after `start` +/// (noninclusive) and prior to `memOp` (e.g. on a control flow/op path +/// between the operations) do not have the potential memory effect +/// `EffectType` on `memOp`. `memOp` is an operation that reads or writes to +/// a memref. For example, if `EffectType` is MemoryEffects::Write, this method +/// will check if there is no write to the memory between `start` and `memOp` +/// that would change the read within `memOp`. +template +bool hasNoInterveningEffect(Operation *start, T memOp) { + auto isLocallyAllocated = [](Value memref) { + auto *defOp = memref.getDefiningOp(); + return defOp && hasSingleEffect(defOp, memref); + }; + + // A boolean representing whether an intervening operation could have impacted + // memOp. + bool hasSideEffect = false; + + // Check whether the effect on memOp can be caused by a given operation op. + Value memref = memOp.getMemRef(); + std::function checkOperation = [&](Operation *op) { + // If the effect has alreay been found, early exit, + if (hasSideEffect) + return; + + if (auto memEffect = dyn_cast(op)) { + SmallVector effects; + memEffect.getEffects(effects); + + bool opMayHaveEffect = false; + for (auto effect : effects) { + // If op causes EffectType on a potentially aliasing location for + // memOp, mark as having the effect. + if (isa(effect.getEffect())) { + // TODO: This should be replaced with a check for no aliasing. + // Aliasing information should be passed to this method. + if (effect.getValue() && effect.getValue() != memref && + isLocallyAllocated(memref) && + isLocallyAllocated(effect.getValue())) + continue; + opMayHaveEffect = true; + break; + } + } + + if (!opMayHaveEffect) + return; + + // If the side effect comes from an affine read or write, try to + // prove the side effecting `op` cannot reach `memOp`. + if (isa(op)) { + MemRefAccess srcAccess(op); + MemRefAccess destAccess(memOp); + // Affine dependence analysis here is applicable only if both ops + // operate on the same memref and if `op`, `memOp`, and `start` are in + // the same AffineScope. + if (srcAccess.memref == destAccess.memref && + getAffineScope(op) == getAffineScope(memOp) && + getAffineScope(op) == getAffineScope(start)) { + // Number of loops containing the start op and the ending operation. + unsigned minSurroundingLoops = + getNumCommonSurroundingLoops(*start, *memOp); + + // Number of loops containing the operation `op` which has the + // potential memory side effect and can occur on a path between + // `start` and `memOp`. + unsigned nsLoops = getNumCommonSurroundingLoops(*op, *memOp); + + // For ease, let's consider the case that `op` is a store and we're + // looking for other potential stores (e.g `op`) that overwrite memory + // after `start`, and before being read in `memOp`. In this case, we + // only need to consider other potential stores with depth > + // minSurrounding loops since `start` would overwrite any store with a + // smaller number of surrounding loops before. + unsigned d; + FlatAffineValueConstraints dependenceConstraints; + for (d = nsLoops + 1; d > minSurroundingLoops; d--) { + DependenceResult result = checkMemrefAccessDependence( + srcAccess, destAccess, d, &dependenceConstraints, + /*dependenceComponents=*/nullptr); + // A dependence failure or the presence of a dependence implies a + // side effect. + if (!noDependence(result)) { + hasSideEffect = true; + return; + } + } + + // No side effect was seen, simply return. + return; + } + // TODO: Check here if the memrefs alias: there is no side effect if + // `srcAccess.memref` and `destAccess.memref` don't alias. + } + // We have an op with a memory effect and we cannot prove if it + // intervenes. + hasSideEffect = true; + return; + } + + if (op->hasTrait()) { + // Recurse into the regions for this op and check whether the internal + // operations may have the side effect `EffectType` on memOp. + for (Region ®ion : op->getRegions()) + for (Block &block : region) + for (Operation &op : block) + checkOperation(&op); + return; + } + + // Otherwise, conservatively assume generic operations have the effect + // on the operation + hasSideEffect = true; + }; + + // Check all paths from ancestor op `parent` to the operation `to` for the + // effect. It is known that `to` must be contained within `parent`. + auto until = [&](Operation *parent, Operation *to) { + // TODO check only the paths from `parent` to `to`. + // Currently we fallback and check the entire parent op, rather than + // just the paths from the parent path, stopping after reaching `to`. + // This is conservatively correct, but could be made more aggressive. + assert(parent->isAncestor(to)); + checkOperation(parent); + }; + + // Check for all paths from operation `from` to operation `untilOp` for the + // given memory effect. + std::function recur = + [&](Operation *from, Operation *untilOp) { + assert( + from->getParentRegion()->isAncestor(untilOp->getParentRegion()) && + "Checking for side effect between two operations without a common " + "ancestor"); + + // If the operations are in different regions, recursively consider all + // path from `from` to the parent of `to` and all paths from the parent + // of `to` to `to`. + if (from->getParentRegion() != untilOp->getParentRegion()) { + recur(from, untilOp->getParentOp()); + until(untilOp->getParentOp(), untilOp); + return; + } + + // Now, assuming that `from` and `to` exist in the same region, perform + // a CFG traversal to check all the relevant operations. + + // Additional blocks to consider. + SmallVector todoBlocks; + { + // First consider the parent block of `from` an check all operations + // after `from`. + for (auto iter = ++from->getIterator(), end = from->getBlock()->end(); + iter != end && &*iter != untilOp; ++iter) { + checkOperation(&*iter); + } + + // If the parent of `from` doesn't contain `to`, add the successors + // to the list of blocks to check. + if (untilOp->getBlock() != from->getBlock()) + for (Block *succ : from->getBlock()->getSuccessors()) + todoBlocks.push_back(succ); + } + + SmallPtrSet done; + // Traverse the CFG until hitting `to`. + while (!todoBlocks.empty()) { + Block *blk = todoBlocks.pop_back_val(); + if (done.count(blk)) + continue; + done.insert(blk); + for (auto &op : *blk) { + if (&op == untilOp) + break; + checkOperation(&op); + if (&op == blk->getTerminator()) + for (Block *succ : blk->getSuccessors()) + todoBlocks.push_back(succ); + } + } + }; + recur(start, memOp); + return !hasSideEffect; +} + } // namespace mlir #endif // MLIR_DIALECT_AFFINE_UTILS_H Index: mlir/lib/Dialect/Affine/Utils/Utils.cpp =================================================================== --- mlir/lib/Dialect/Affine/Utils/Utils.cpp +++ mlir/lib/Dialect/Affine/Utils/Utils.cpp @@ -650,191 +650,6 @@ return success(); } -/// Ensure that all operations that could be executed after `start` -/// (noninclusive) and prior to `memOp` (e.g. on a control flow/op path -/// between the operations) do not have the potential memory effect -/// `EffectType` on `memOp`. `memOp` is an operation that reads or writes to -/// a memref. For example, if `EffectType` is MemoryEffects::Write, this method -/// will check if there is no write to the memory between `start` and `memOp` -/// that would change the read within `memOp`. -template -static bool hasNoInterveningEffect(Operation *start, T memOp) { - auto isLocallyAllocated = [](Value memref) { - auto *defOp = memref.getDefiningOp(); - return defOp && hasSingleEffect(defOp, memref); - }; - - // A boolean representing whether an intervening operation could have impacted - // memOp. - bool hasSideEffect = false; - - // Check whether the effect on memOp can be caused by a given operation op. - Value memref = memOp.getMemRef(); - std::function checkOperation = [&](Operation *op) { - // If the effect has alreay been found, early exit, - if (hasSideEffect) - return; - - if (auto memEffect = dyn_cast(op)) { - SmallVector effects; - memEffect.getEffects(effects); - - bool opMayHaveEffect = false; - for (auto effect : effects) { - // If op causes EffectType on a potentially aliasing location for - // memOp, mark as having the effect. - if (isa(effect.getEffect())) { - // TODO: This should be replaced with a check for no aliasing. - // Aliasing information should be passed to this method. - if (effect.getValue() && effect.getValue() != memref && - isLocallyAllocated(memref) && - isLocallyAllocated(effect.getValue())) - continue; - opMayHaveEffect = true; - break; - } - } - - if (!opMayHaveEffect) - return; - - // If the side effect comes from an affine read or write, try to - // prove the side effecting `op` cannot reach `memOp`. - if (isa(op)) { - MemRefAccess srcAccess(op); - MemRefAccess destAccess(memOp); - // Affine dependence analysis here is applicable only if both ops - // operate on the same memref and if `op`, `memOp`, and `start` are in - // the same AffineScope. - if (srcAccess.memref == destAccess.memref && - getAffineScope(op) == getAffineScope(memOp) && - getAffineScope(op) == getAffineScope(start)) { - // Number of loops containing the start op and the ending operation. - unsigned minSurroundingLoops = - getNumCommonSurroundingLoops(*start, *memOp); - - // Number of loops containing the operation `op` which has the - // potential memory side effect and can occur on a path between - // `start` and `memOp`. - unsigned nsLoops = getNumCommonSurroundingLoops(*op, *memOp); - - // For ease, let's consider the case that `op` is a store and we're - // looking for other potential stores (e.g `op`) that overwrite memory - // after `start`, and before being read in `memOp`. In this case, we - // only need to consider other potential stores with depth > - // minSurrounding loops since `start` would overwrite any store with a - // smaller number of surrounding loops before. - unsigned d; - FlatAffineValueConstraints dependenceConstraints; - for (d = nsLoops + 1; d > minSurroundingLoops; d--) { - DependenceResult result = checkMemrefAccessDependence( - srcAccess, destAccess, d, &dependenceConstraints, - /*dependenceComponents=*/nullptr); - // A dependence failure or the presence of a dependence implies a - // side effect. - if (!noDependence(result)) { - hasSideEffect = true; - return; - } - } - - // No side effect was seen, simply return. - return; - } - // TODO: Check here if the memrefs alias: there is no side effect if - // `srcAccess.memref` and `destAccess.memref` don't alias. - } - // We have an op with a memory effect and we cannot prove if it - // intervenes. - hasSideEffect = true; - return; - } - - if (op->hasTrait()) { - // Recurse into the regions for this op and check whether the internal - // operations may have the side effect `EffectType` on memOp. - for (Region ®ion : op->getRegions()) - for (Block &block : region) - for (Operation &op : block) - checkOperation(&op); - return; - } - - // Otherwise, conservatively assume generic operations have the effect - // on the operation - hasSideEffect = true; - }; - - // Check all paths from ancestor op `parent` to the operation `to` for the - // effect. It is known that `to` must be contained within `parent`. - auto until = [&](Operation *parent, Operation *to) { - // TODO check only the paths from `parent` to `to`. - // Currently we fallback and check the entire parent op, rather than - // just the paths from the parent path, stopping after reaching `to`. - // This is conservatively correct, but could be made more aggressive. - assert(parent->isAncestor(to)); - checkOperation(parent); - }; - - // Check for all paths from operation `from` to operation `untilOp` for the - // given memory effect. - std::function recur = - [&](Operation *from, Operation *untilOp) { - assert( - from->getParentRegion()->isAncestor(untilOp->getParentRegion()) && - "Checking for side effect between two operations without a common " - "ancestor"); - - // If the operations are in different regions, recursively consider all - // path from `from` to the parent of `to` and all paths from the parent - // of `to` to `to`. - if (from->getParentRegion() != untilOp->getParentRegion()) { - recur(from, untilOp->getParentOp()); - until(untilOp->getParentOp(), untilOp); - return; - } - - // Now, assuming that `from` and `to` exist in the same region, perform - // a CFG traversal to check all the relevant operations. - - // Additional blocks to consider. - SmallVector todoBlocks; - { - // First consider the parent block of `from` an check all operations - // after `from`. - for (auto iter = ++from->getIterator(), end = from->getBlock()->end(); - iter != end && &*iter != untilOp; ++iter) { - checkOperation(&*iter); - } - - // If the parent of `from` doesn't contain `to`, add the successors - // to the list of blocks to check. - if (untilOp->getBlock() != from->getBlock()) - for (Block *succ : from->getBlock()->getSuccessors()) - todoBlocks.push_back(succ); - } - - SmallPtrSet done; - // Traverse the CFG until hitting `to`. - while (!todoBlocks.empty()) { - Block *blk = todoBlocks.pop_back_val(); - if (done.count(blk)) - continue; - done.insert(blk); - for (auto &op : *blk) { - if (&op == untilOp) - break; - checkOperation(&op); - if (&op == blk->getTerminator()) - for (Block *succ : blk->getSuccessors()) - todoBlocks.push_back(succ); - } - } - }; - recur(start, memOp); - return !hasSideEffect; -} - /// Attempt to eliminate loadOp by replacing it with a value stored into memory /// which the load is guaranteed to retrieve. This check involves three /// components: 1) The store and load must be on the same location 2) The store