Create the Reduction Tree Pass

[msifontes]

Summary

Implement the Reduction Tree Pass framework as part of the MLIR Reduce tool. This is a parametarizable pass that allows for the implementation of custom reductions passes in the tool.
Implement the OpReducer class as an example of a 'Reducer' parameter for the instantiation of a Reduction Tree Pass.
Create a pass pipeline with a Reduction Tree Pass with the OpReducer class specified as parameter.

[rriddle]

mlir/include/mlir/Reducer/ReductionTreePass.h

31

Please move this down into the namespace.

52

I would expect this to already be provided for you by the base class.

58

nit: Please add comments to these.

60

nit: Drop the llvm::, it is re-exported in the mlir namespace.

73

Can you switch this to using pImpl techniques instead? That would allow for this to be templated while specifying the implementation within the .cpp file.

mlir/tools/mlir-reduce/Passes/OpReducer.cpp

23 ↗

(On Diff #279920)

Why are you counting functions? That doesn't match up with the method name or comments.

Also, I'd just do something like:

auto ops = module.getOps<FuncOp>();
return std::distance(ops.begin(), ops.end());

33 ↗

(On Diff #279920)

What is the result of this supposed to mean? It isn't documented in the method comments.

35 ↗

(On Diff #279920)

nit: Drop the constexpr here, and the const below. We don't attach those to integers/simple types in MLIR.

48 ↗

(On Diff #279920)

Use llvm::enumerate to have an index and a value.

54 ↗

(On Diff #279920)

nit: Spell out auto here.

57 ↗

(On Diff #279920)

This seems weird from an API perspective, it isn't clear what the ownership is. Can you refactor to make the ownership explicit? e.g. by using a static method instead of the constructor.

mlir/tools/mlir-reduce/ReductionNode.cpp

42

Where are you getting this function from? I don't expect this would work well on windows, can you use something from LLVM instead?

113

nit: Can you use llvm::array_pod_sort instead? It is generally preferred over std::sort.

https://github.com/llvm/llvm-project/blob/1890a65ca17504cab4032d3c8cc0c4c568d44717/llvm/include/llvm/ADT/STLExtras.h#L1367

[mehdi_amini]

mlir/tools/mlir-reduce/ReductionNode.cpp

113

I thoughts array_pod_sort relies on the element being sorted using std::less? There is a custom function here.

[msifontes]

Apply requested changes

• Add missing c++ designators
• Remove uninteresting nodes when sorting
• Create testing script to test new functionality
• Comment formatting changes
• Add class member descriptions
• Reformatted OpReducer class to FuncReducer class with the objective of reducing the number of functions.
• Remove ClonePass()
• Use of llvm::enumerate where possible
• Modify ReductioNode constructor to split the functionality of linking a child node to a parent
• Change module measurement to character measurement using ifstream and the temporary file

Pending:

• pimpl template class refactoring
• Making the variantGenerator method non-static
• Passes.h.inc dependency error
• Replace std::sort

[rriddle]

mlir/tools/mlir-reduce/ReductionNode.cpp

113

You can provide your own functor, it just defaults to std::less for convenience:

https://github.com/llvm/llvm-project/blob/873b79b8675d0c8eca6055ae8a874fe52b033c28/mlir/tools/mlir-tblgen/PassDocGen.cpp#L66
https://github.com/llvm/llvm-project/blob/ff6a0b6a8ee74693e9711973028a8a327adf9cd5/llvm/lib/Object/SymbolSize.cpp#L81
https://github.com/llvm/llvm-project/blob/308571074c13ea2a0758aa085aa02f72150f891e/mlir/tools/mlir-tblgen/mlir-tblgen.cpp#L46

[msifontes]

NFC

[msifontes]

Apply changes

• Replace static method reference with Reducer member object in ReductionTreePas class
• Use array_pod_sort instead of std::sort

[msifontes]

This comment was removed by msifontes.

[msifontes]

Fix Passes.h.inc dependency

[msifontes]

Resolve clang-tidy error

[msifontes]

NFC: Add ending namespace comment

[msifontes]

Move ReductionTreePass non-templated members to ReductionTreeUtils class in order to move some of the implementation to the .cpp file.

[jpienaar]

Nice, thanks

mlir/include/mlir/Reducer/Passes/FuncReducer.h

23 ↗

(On Diff #280488)

FuncReducer

29 ↗

(On Diff #280488)

children

mlir/include/mlir/Reducer/ReductionNode.h

21

I don't think this include is needed in this header

62

Link how? I'd have thought the parent linkage would be via construction.

mlir/include/mlir/Reducer/ReductionTreePass.h

82

Are we modifying Tester along the way? Seems like we could pass const ref version everyewhere

84

This description makes me think this shouldn't be a class member.

mlir/tools/mlir-reduce/Passes/FuncReducer.cpp

61 ↗

(On Diff #280488)

Nit: prefer (int)op.index() as that is more common here, else I'd say go for

int index = op.index();
if (index >= sectionSize*i && index < sectionSize*(i+1)) { ... }

66 ↗

(On Diff #280488)

So the functions are deleted but the symbol table is not changed, so what happens in the case where the function is invoked from a function not inside the deleted section? (would this be possible to tickle in a test? Perhaps one with 2 functions and on function calls the other).

mlir/tools/mlir-reduce/ReductionNode.cpp

54

s/bitcode/IR/ ? (or just s/bitcode//)

56

If you did out.os().tell() above, give you the same size? It seems to be counting chars written too which could avoid re-reading it.

104

Could this simply be a return? Also should this be lhs->get()->getSize() < rhs->get()->getSize()?

[msifontes]

mlir/tools/mlir-reduce/Passes/FuncReducer.cpp

66 ↗

(On Diff #280488)

I tested this by calling another function from the interesting function and the output was the interesting function along with the function it calls. I can look into dropping the calls in the OpReducer class I am working on which will allow for the removal of any function or MLIR dialect function like operation and would therefore replace this class.

[msifontes]

Apply requested changes

• Link children Reduction Nodes from constructor
• Use constant ref tester throughout
• Use out.os().tell() to measure files
• Simplify array_pod_sort return statement

[rriddle]

mlir/include/mlir/Reducer/ReductionTreePass.h

66

nit: You shouldn't need a break here, report_fatal_error doesn't return.

mlir/test/mlir-reduce/reduction-tree-pass.mlir

7

Can you add a few CHECK-NOTs to ensure the other functions aren't present?

10

Do you actually need anything inside of these functions for this test?

mlir/tools/mlir-reduce/ReductionNode.cpp

27

nit: Drop the trivial braces here.

51

test->isInteresting?

89

nit: Add braces here as the body is non-trivial.

91

The iterator would be invalidated after the erase, given that this is a vector.

mlir/tools/mlir-reduce/ReductionTreePass.cpp

25

You can access the raw operation list of a block via getOperations. That list can allow for erasing a range of operation, and splicing a range of operations from one list to another. Can you use that to simplify this?

37

nit: Spell out auto here and above.

mlir/tools/mlir-reduce/mlir-reduce.cpp

89

nit: Inline the use of this variable.

[msifontes]

Apply requested changes

• Simplify test and included CHECK-NOT tags
• Simplify updateGoldenModule utility
• Fix uninteresting variant removal

[jpienaar]

I think we can iterate from here, just a couple of things to fix and consider adding a few test cases for the edge cases (e.g., ops < variants, non multiple divisors)

mlir/include/mlir/Reducer/Passes/FuncReducer.h

1 ↗

(On Diff #283275)

s/Operation/Function/

28 ↗

(On Diff #283275)

Do you want to specialize these to correspond to what they do in this pass?

34 ↗

(On Diff #283275)

Does this just care about functions or any general op? Also does this need to be a class member vs a static function in the CC file?

mlir/include/mlir/Reducer/ReductionNode.h

58

Why is this needed on the public interface? Meaning, this seems like something that is called as part of "getInterestingVariants()" call. Could also be revised in follow up

84

Nit: I'd follow methods before data

mlir/include/mlir/Reducer/ReductionTreePass.h

2

Missing * c++ * part in header

mlir/tools/mlir-reduce/Passes/FuncReducer.cpp

32 ↗

(On Diff #283275)

Do you have a test where it doesn't evenly divide? (this would seem to round down and then we could miss terms on the end)

Also if we had 10 ops but 100 variants, this doesn't seem to work.

mlir/tools/mlir-reduce/ReductionNode.cpp

90

Instead of this, why not sort it based on (!interesting, size) pair and then just resizing the uninteresting end out?

[msifontes]

mlir/tools/mlir-reduce/Passes/FuncReducer.cpp

32 ↗

(On Diff #283275)

I have significantly refactored this so that the number of variants never exceeds the number of indices but it depends on the utilities I will be including in the next revision. I will be replacing this FunctionReducer file with the general OpReducer in the next revision which will be capable of performing the same reduction.

My thought process when it doesn't evenly split is to not remove any remainder Functions/indices that don't fit in the partitions since eventually variants will be created that attempt to remove these further down the tree. I could also look into including the removal of these remainder ops in the last variant generated at the level.

mlir/tools/mlir-reduce/ReductionNode.cpp

90

Implementing this approach.

[msifontes]

Apply requested changes

• Simplify the removal of uninteresting nodes
• Style and naming changes

[msifontes]

Fix header formatting warning

[msifontes]

NFC: clang format