This is an archive of the discontinued LLVM Phabricator instance.

[MLIR] Implemented iterative topological sorting
ClosedPublic

Authored by georgemitenkov on Sep 30 2020, 2:02 AM.

Details

Summary

Implemented an iterative preorder DFS topological sort
instead of the previous recursive version.

Diff Detail

Event Timeline

georgemitenkov created this revision.Sep 30 2020, 2:02 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 30 2020, 2:02 AM
georgemitenkov requested review of this revision.Sep 30 2020, 2:02 AM
rriddle added inline comments.Sep 30 2020, 11:01 AM
mlir/lib/Target/LLVMIR/ModuleTranslation.cpp
364–365

nit: You could just use llvm::ReversePostOrderTraversal to get the topological sort.

365

nit: Drop the llvm:: here, SmallVector is re-exported into the mlir namespace.

369

Why the move here? Also, you can you pop_back_val instead.

Thanks for working on this!

Thanks for working on this.

mlir/lib/Target/LLVMIR/ModuleTranslation.cpp
364–365

Can this be inlined into topologicalSort?

georgemitenkov marked 4 inline comments as done.

Addressed comments and reused llvm::ReversePostOrderTraversal for topological sorting.

mlir/lib/Target/LLVMIR/ModuleTranslation.cpp
373

Nit: MLIR adopts camelBack convention for names. Switch from RPOT-> rpot?
https://mlir.llvm.org/getting_started/DeveloperGuide/

rriddle accepted this revision.Oct 1 2020, 7:36 PM

LGTM after resolving the remaining comments. You might want to clarify the commit title and description a bit more, it is very broad for what you are fixing here.

mlir/lib/Target/LLVMIR/ModuleTranslation.cpp
374

nit: Use the range based insert instead.

Also in the future, please cache the end iterator in loops when it is unchanged within the loop.

This revision is now accepted and ready to land.Oct 1 2020, 7:36 PM
georgemitenkov marked 2 inline comments as done.

Rebased and addressed comments.

Hey! Thanks for the patch! I wondered if it would make sense to move this utility to a public utility header. I found myself needing it locally and I wouldn't like to just copy-paste it. There is another topological sort for ops under 'include/mlir/Analysis/SliceAnalysis.h'. Maybe we could move them both to 'include/mlir/IR/Utils.h'? WDYT?

Hey! Thanks for the patch! I wondered if it would make sense to move this utility to a public utility header. I found myself needing it locally and I wouldn't like to just copy-paste it. There is another topological sort for ops under 'include/mlir/Analysis/SliceAnalysis.h'. Maybe we could move them both to 'include/mlir/IR/Utils.h'? WDYT?

I think that if this functionality is needed elsewhere, then it should make sense to publicly expose it. Having 'include/mlir/IR/Utils.h' sounds reasonable - maybe we can have something similar to LLVM's ADT with MLIR specific utilities/algorithms built on top (I guess this is not only the case of topological sorting)? @rriddle, @mehdi_amini, @ftynse WDYT?