Implement strategy for loop ordering choice (true compiler starter)

[aartbik]

Bugzilla Link	52309
Version	unspecified
OS	Linux
CC	@joker-eph

Extended Description

The sparse compiler uses a topsort to find a suitable loop ordering (following the sparse constraints always, and possibly adding in the dense constraints if this does not yield cycles). However, often we still have an ordering choice, and the way we currently go from conservative ordering to relaxed ordering can possibly be improved. The bug requests investigating and implementing a good strategy for picking a loop order.

Relevant code to start looking at:

Method computeIterationGraph() in https://github.com/llvm/llvm-project/blob/main/mlir/lib/Dialect/SparseTensor/Transforms/Sparsification.cpp

[aartbik]

assigned to @aartbik

[Johan511]

Hi, has there been any progress made on this issue? Is there is scholarly work I could look into for a better strategy for picking loop order.

[aartbik]

Changes have been made to computeIterationGraph() to deal with some very obvious performance issues, but no foundational approach yet that picks the right order given the computation (parallel/reduction loops) and sparsity properties of the tensor operands (dense, sparse, what kind of sparse).

[PeimingLiu]

Also, see https://reviews.llvm.org/D144932 as a our recent attempt.

[streichgeorg]

I tried to improve this a bit in https://reviews.llvm.org/D150061

[llvmbot]

Hi!

This issue may be a good introductory issue for people new to working on LLVM. If you would like to work on this issue, your first steps are:

1. Assign the issue to you.
2. Fix the issue locally.
3. Run the test suite locally.
   3.1) Remember that the subdirectories under test/ create fine-grained testing targets, so you can
   e.g. use make check-clang-ast to only run Clang's AST tests.
4. Create a git commit
5. Run git clang-format HEAD~1 to format your changes.
6. Submit the patch to Phabricator.
   6.1) Detailed instructions can be found here

For more instructions on how to submit a patch to LLVM, see our documentation.

If you have any further questions about this issue, don't hesitate to ask via a comment on this Github issue.

@llvm/issue-subscribers-good-first-issue