[MLIR][Affine] Make fusion helper check method significantly more efficient
authorUday Bondhugula <uday@polymagelabs.com>
Wed, 28 Dec 2022 20:06:21 +0000 (01:36 +0530)
committerUday Bondhugula <uday@polymagelabs.com>
Wed, 28 Dec 2022 20:20:29 +0000 (01:50 +0530)
commit4b9e2f8fe0fcb1d104fd10a149372aaf7ca99af2
tree53ed60ad564c925ee70f83eb7fa8d9a33bcbdf6b
parent27751bed60bcb0a05c5e85608ea03ff6f55cb14b
[MLIR][Affine] Make fusion helper check method significantly more efficient

The `hasDependencePath` method in affine fusion is quite inefficient as
it does a DFS on the complete graph for what is a small part of the
checks before fusion can be performed. Make this efficient by using the
fact that the nodes involved are all at the top-level of the same block.
With this change, for large graphs with about 10,000 nodes, the check
runs in a few seconds instead of not terminating even in a few hours.

This is NFC from a functionality standpoint; it only leads to an
improvement in pass running time on large IR.

Differential Revision: https://reviews.llvm.org/D140522
mlir/lib/Dialect/Affine/Transforms/LoopFusion.cpp