Page MenuHomePhabricator

Create the Reduction Tree Pass

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



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

There are a very large number of changes, so older changes are hidden. Show Older Changes
rriddle added inline comments.Jul 22 2020, 4:13 PM

Please move this down into the namespace.


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


nit: Please add comments to these.


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


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.

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.


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


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

mehdi_amini added inline comments.Jul 22 2020, 8:04 PM

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


  • pimpl template class refactoring
  • Making the variantGenerator method non-static
  • dependency error
  • Replace std::sort
msifontes updated this revision to Diff 280014.EditedJul 22 2020, 8:14 PM


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 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

23 ↗(On Diff #280488)


29 ↗(On Diff #280488)



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


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


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


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

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


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


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.


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.
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 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

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


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


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


nit: Drop the trivial braces here.




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


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


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?


nit: Spell out auto here and above.


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)

1 ↗(On Diff #283275)


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?


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


Nit: I'd follow methods before data


Missing * c++ * part in header

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.


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.
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.


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.