This is an archive of the discontinued LLVM Phabricator instance.

Create the Reduction Tree Pass
ClosedPublic

Authored by msifontes on Jul 16 2020, 10:53 AM.

Details

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.

Diff Detail

Event Timeline

msifontes created this revision.Jul 16 2020, 10:53 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 16 2020, 10:53 AM
  1. Updating D83969: Create the Reduction Tree Pass #
  2. Enter a brief description of the changes included in this update.
  3. The first line is used as subject, next lines as comment. #
  4. If you intended to create a new revision, use:
  5. $ arc diff --create

Fix working directory HEAD

Add empty line to CMakeList file.

This comment was removed by msifontes.
tpopp added inline comments.Jul 17 2020, 9:38 AM
mlir/include/mlir/Reducer/Passes/OpReducer.h
8 ↗(On Diff #278553)

Include a /// \file on the line before the text (so line 8 and other text on line 9)

Also, for lines 9-12, 3 '/'s

34 ↗(On Diff #278553)

Maybe return the bool since you aren't returning anything right now?

mlir/include/mlir/Reducer/ReductionNode.h
9

/// \file again

21

I don't think this is needed in the header file.

50

Optional: Maybe just provide iterator implementations for begin/end. This might be safe now, but is rather risky in C++ because it requires that the object outlives the returned vector if someone captures the return as a reference.

mlir/include/mlir/Reducer/ReductionTreePass.h
9

\file

29

enums should start with an uppercase, so "TraversaMode". The values should also start capitalized.

49

I think the StringRef constructor here is unneeded

84

I think all of this deletion logic is unnecessary if you use std::vector<std::unique_ptr<ReductionNode>> and let it do all the deletion at the end.

85

micro-optimization doing this on one line. Right now this copies the vector.

103

2 if statements might be slightly more readable here. Otherwise you're missing a rare chance to use a do/while loop!!

117

I believe MLIR style wants something like golden.walk([&](auto *op) {opsToSwap.pushBack(op); } )

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

Can you leave a comment on what this is testing? It's surprising to see a 50 line test case with only 1 CHECK.

mlir/tools/mlir-reduce/Passes/OpReducer.cpp
22 ↗(On Diff #278553)

I think this might just return the number of Blocks unless you use module.getOps()?

mlir/tools/mlir-reduce/ReductionNode.cpp
53

I don't know if LLVM feels this way, but usually people want constructors to be fast, so it would be better to not have this in the construction step.

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

Do you need this print statement?

msifontes updated this revision to Diff 279375.EditedJul 20 2020, 4:20 PM
msifontes marked 15 inline comments as done.

Apply requested changes

  • Use of smart pointers
  • Simplify reduction node constructor by separating the testing and sorting
  • Add test description comment
  • Use getOps() to iterate over function operations
  • Doxygen formatted comments
  • Simplify updateGolden method
  • Replace getVariants() with getVariant(int index)
  • Eliminate reduction tree destructor
  • Capitalize enumerator options
  • Change variantGenerator() to type boolean
tpopp added inline comments.Jul 21 2020, 11:43 AM
mlir/include/mlir/Reducer/PassDetail.h
10

clang-tidy: warning: header guard does not follow preferred style [llvm-header-guard]

mlir/include/mlir/Reducer/Passes/OpReducer.h
15 ↗(On Diff #279375)

clang-tidy: warning: header guard does not follow preferred style [llvm-header-guard]

mlir/include/mlir/Reducer/ReductionNode.h
9

On the style guide, they show 3 slashes being used for this section.

18

clang-tidy: warning: header guard does not follow preferred style [llvm-header-guard]

44

I wouldn't have thought of this before your line above, but since you started it, let's make the other const methods const also :D

mlir/include/mlir/Reducer/ReductionTreePass.h
2

Probably this should be a header and C++ file?

18

clang-tidy: warning: header guard does not follow preferred style [llvm-header-guard]

42

generateVariants = Reducer(); maybe? If not, it's fine the way it is.

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

Try to keep comments under 80 lines (CHECK lines can be longer).

mlir/tools/mlir-reduce/Passes/OpReducer.cpp
23 ↗(On Diff #279375)

In theory you can ignore this, but in practice someone at Google will have to come correct this right after you land it, so try to handle unused variable notices with a (void) op; added in the for loop body.

33 ↗(On Diff #279375)

nit: constexpr int numVariants = 2;

34 ↗(On Diff #279375)

nit: const int for the next 2.

mlir/tools/mlir-reduce/ReductionNode.cpp
23

You don't need a shared_pointer at locations like these where your using it and not holding a reference to the object after the function call ends.

106

I think std::make_shared would work here also.

mehdi_amini added inline comments.Jul 21 2020, 7:57 PM
mlir/include/mlir/Reducer/ReductionNode.h
68

Why shared_ptr and not unique_ptr? It isn't clear to me why do we need refcounting here?

msifontes marked 15 inline comments as done.

Apply Requested changes

  • Comment formatting changes
  • Use unique_ptr to reference reduction nodes
  • Split reduction Tree Pass into header and .cpp file
  • Fix file header formatting
  • Fix header guard formatting
  • Use const where possible

NFC Changes

Remove duplicate Tester.cpp

Fix PassDetail.h header guard format

This comment was removed by msifontes.
This comment was removed by msifontes.
jpienaar added inline comments.Jul 22 2020, 1:28 PM
mlir/include/mlir/Reducer/Passes/OpReducer.h
1 ↗(On Diff #279920)

Missing c++ designator here

Could we perhaps reduce the file description?

Looking at the description too, perhaps the name is confusing :) This feels very general description, but if I look at the implementation then this is an instance of variant generation that tries to delete functions that are not interesting.

24 ↗(On Diff #279920)

I feel like these might be comments for the markdown doc: you are using a specific variant generation but then describiing it as if a general one.

30 ↗(On Diff #279920)

Why is this a public static method here? E.g., do we expect all reduction passes to implement this?

34 ↗(On Diff #279920)

Why static? Meaning, how would folks be able to track variants already pursued from within this static method. That seems like it would require tracking the space explored in the reductionnode's and some way not attempting things that have been done before.

mlir/include/mlir/Reducer/ReductionNode.h
2

Missing c++ indicator

59

Do we care about those that aren't interesting?

mlir/include/mlir/Reducer/ReductionTreePass.h
73

Why is this needed here? It seems the ReductionTreePass is independent of this

mlir/tools/mlir-reduce/ReductionNode.cpp
23

I'd just pass in const ReductionNode&, std::unique_ptr adds nothing here for me (means you need to dereference at call site sure, but inside you don't have to care if the unique_ptr is empty or not, and no ownership changes)

70

Why not just print to a std::string instead? (no need to create and write a file). Unless there is a reason (e.g., in case of crashes), that you'd want this

msifontes marked 2 inline comments as done.Jul 22 2020, 3:47 PM
msifontes added inline comments.
mlir/include/mlir/Reducer/ReductionTreePass.h
73

The linker was having trouble with the ReductionTreePass class because of the template. Two solutions I found was having the method definitions in the header file or defining this templated class. Is there a different way to solve this linker problem? I could also move this template class definition to the file handling the pass manager.

msifontes marked an inline comment as done.Jul 22 2020, 3:48 PM
msifontes added inline comments.
mlir/tools/mlir-reduce/ReductionNode.cpp
70

This is needed for running the interestingness script.

msifontes marked an inline comment as done.Jul 22 2020, 3:53 PM
msifontes added inline comments.
mlir/tools/mlir-reduce/ReductionNode.cpp
23

I believe this is needed because of the way std::sort is implemented. This function must accept two arguments of the same type as the members in the vector being sorted which is a unique_ptr vector.

rriddle added inline comments.Jul 22 2020, 4:13 PM
mlir/include/mlir/Reducer/PassDetail.h
2

This comment seems off.

mlir/include/mlir/Reducer/Passes.td
2

This line should be 80 characters long.

14

typo: REDUCER

20

nit: This looks like it is over 80 characters.

mlir/include/mlir/Reducer/Passes/OpReducer.h
15 ↗(On Diff #278541)

This path needs to be updated.

8 ↗(On Diff #278553)

nit: I would remove this, we don't use those directives anywhere else in the MLIR codebase.

mlir/include/mlir/Reducer/ReductionNode.h
9

We haven't used this anywhere else in MLIR, I'd rather just omit it.

26

Can you remove this?

64

Can you add comments to all of these? It isn't clear what they mean.

rriddle added inline comments.Jul 22 2020, 4:13 PM
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 added inline comments.Jul 22 2020, 8:04 PM
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 updated this revision to Diff 280011.EditedJul 22 2020, 8:07 PM
msifontes marked 30 inline comments as done.

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
msifontes updated this revision to Diff 280014.EditedJul 22 2020, 8:14 PM

NFC

Apply changes

  • Replace static method reference with Reducer member object in ReductionTreePas class
  • Use array_pod_sort instead of std::sort
msifontes updated this revision to Diff 280308.Jul 23 2020, 6:07 PM
This comment was removed by msifontes.
msifontes updated this revision to Diff 280310.Jul 23 2020, 6:49 PM

Fix Passes.h.inc dependency

msifontes updated this revision to Diff 280320.Jul 23 2020, 9:04 PM

Resolve clang-tidy error

msifontes updated this revision to Diff 280321.Jul 23 2020, 9:08 PM

NFC: Add ending namespace comment

msifontes updated this revision to Diff 280488.Jul 24 2020, 9:19 AM

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

Nice, thanks

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

FuncReducer

30

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
62

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)) { ... }

67

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 marked 6 inline comments as done.Jul 31 2020, 8:20 AM
msifontes added inline comments.
mlir/tools/mlir-reduce/Passes/FuncReducer.cpp
67

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 updated this revision to Diff 282228.Jul 31 2020, 8:25 AM
msifontes marked 2 inline comments as done.

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 added inline comments.Aug 5 2020, 2:46 AM
mlir/include/mlir/Reducer/ReductionTreePass.h
65

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

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

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

9

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

mlir/tools/mlir-reduce/ReductionNode.cpp
26

nit: Drop the trivial braces here.

50

test->isInteresting?

88

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

90

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

mlir/tools/mlir-reduce/ReductionTreePass.cpp
24

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?

36

nit: Spell out auto here and above.

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

nit: Inline the use of this variable.

msifontes updated this revision to Diff 283275.Aug 5 2020, 9:29 AM
msifontes marked 8 inline comments as done.

Apply requested changes

  • Simplify test and included CHECK-NOT tags
  • Simplify updateGoldenModule utility
  • Fix uninteresting variant removal
jpienaar accepted this revision.Aug 7 2020, 10:16 AM

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
2

s/Operation/Function/

29

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

35

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
33

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?

This revision is now accepted and ready to land.Aug 7 2020, 10:16 AM
msifontes marked 7 inline comments as done.Aug 7 2020, 1:30 PM
msifontes added inline comments.
mlir/tools/mlir-reduce/Passes/FuncReducer.cpp
33

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 updated this revision to Diff 284027.Aug 7 2020, 1:41 PM
msifontes marked an inline comment as done.

Apply requested changes

  • Simplify the removal of uninteresting nodes
  • Style and naming changes
msifontes updated this revision to Diff 284062.Aug 7 2020, 2:42 PM

Fix header formatting warning

msifontes updated this revision to Diff 284069.Aug 7 2020, 3:01 PM

NFC: clang format

This revision was automatically updated to reflect the committed changes.