This is an archive of the discontinued LLVM Phabricator instance.

[RFC] StableHashTree Implementation.
Needs ReviewPublic

Authored by plotfi on Sep 23 2020, 1:20 PM.



This is a first pass at bringing some work that has been done on assisting the Machine Outliner with cross module outlining decisions. A lot of this work is inspired by or directly refactored from the Global Machine Outliner for ThinLTO talk from EuroLLVM 2020 (

In this diff however, there is no LTO: This diff enables a way to serialize a representation of the MachineOutliner suffix tree as a HashTree to disk. Serialized HashTrees can be read in and used to aid in making better outlining decisions for modules where a Candidate sequence only occurs once, but which have duplicate Candidates off module. This is a first step and I anticipate this will evolve a lot from its current form.

For now I have a single test case to showcase the mechanics, but am working on more test cases.

Diff Detail

Event Timeline

plotfi created this revision.Sep 23 2020, 1:20 PM
plotfi requested review of this revision.Sep 23 2020, 1:20 PM

@thegameg: @paquette tells be you might have some ideas on a better format than this json business going on here (based on work you've done on remarks). What do you think?

plotfi updated this revision to Diff 294195.Sep 24 2020, 4:34 PM
plotfi updated this revision to Diff 294211.Sep 24 2020, 6:20 PM

Cleaning up patch to be easier to understand.

plotfi updated this revision to Diff 294212.Sep 24 2020, 6:32 PM

spelling and grammar

plotfi updated this revision to Diff 294226.Sep 24 2020, 10:15 PM


plotfi updated this revision to Diff 294228.Sep 24 2020, 10:28 PM

comments added

I think it would make sense to put the StableHashTree implementation in its own patch. Then, in a follow up, you can plumb through the outliner support.

The data structure itself needs tests outside of the outliner, and I think it references the outliner itself a little too much in the comments.

I also feel like the outliner shouldn't be responsible for producing HashTree. That seems like a different thing which may have its own cost model and considerations. It might make sense to adapt the IRSimilarity framework to MIR and use that for the purposes of producing the tree.

Having the outliner consume the tree seems fine to me though.

185 ↗(On Diff #294228)

Variable name in comment should match the actual variable name.

(Included existing typo for clarity)

188 ↗(On Diff #294228)
  • Should say "Matches" or "Match", not "Matche"
  • Maybe a more succinct name?
190 ↗(On Diff #294228)


194 ↗(On Diff #294228)

If you use an Optional, you can differentiate between "it's just empty" and "it's not actually being used" in the type itself.

Also, would it make sense to use a SmallVector here?

However, SmallVector<T, 0> is often a better option due to the advantages listed [in the SmallVector section]. std::vector is still useful when you need to store more than UINT32_MAX elements or when interfacing with code that expects vectors


Might be worth fixing the filename here in a NFC commit?


remove unnecessary whitespace change


Why not both const?


Probably should have a documentation comment?


I think that this comment can describe what this actually does in a bit more detail. If this is intended to be a reusable data structure (as the comment implies), I think it'd make sense to address the following questions:

  • What does the stable hash tree actually do?
  • Why would you use it in a transformation?

Also "Global Machine Outlining" isn't defined anywhere.

In the patch description you have:

A lot of this work is inspired by or directly refactored from the Global Machine Outliner for ThinLTO talk from EuroLLVM 2020 (

So it'd be nice to include that somewhere, so people curious about that can take a look.

  • Should be a Doxygen comment
  • Try to use class names to make things clear

Move member variable documentation into the struct.


Move member variable documentation into the struct.


If you use a more meaningful name than "Data", it shouldn't be necessary to document this?


Could this just be a function that checks if the map is empty?


Would it be appropriate to use an IndexedMap here?

IndexedMap is a specialized container for mapping small dense integers (or values that can be mapped to small dense integers) to some other type. It is internally implemented as a vector with a mapping function that maps the keys to the dense integer range.

I suppose it depends on if stable_hash tends to be dense, by whatever measure of dense is being used here.


Match the name of the file?


I think that you can drop the part about walkEdges?

General documentation for the data structure and how it works would be better in the \file comment at the top.


These type names are pretty long.

Maybe it'd be good to reduce the cognitive overload by doing something like this somewhere:

/// Graph traversal callback types.
using EdgeCallbackFn = std::function<void(const HashNode *, const HashNode *)>;
using NodeCallbackFn = std::function<void(const HashNode *)>;

Although vertex and node are interchangeable terms, I think it'd be good to be consistent and just choose one?


Should be Doxygen


Documentation comments don't need to include implementation info; that can go out of date.


Use Doxygen stuff


No need to mention where this is called if you document the algorithm somewhere.


- Documentation should just say what the function does, not include implementation details.

  • Doxygen comment.

Probably good to not mention outlining here if this is supposed to be general-purpose?


Needs documentation.

114 ↗(On Diff #294228)

This is a long sentence. Split it up?

372 ↗(On Diff #294228)


596 ↗(On Diff #294228)

Can this go in a function?

611 ↗(On Diff #294228)

Do you have to use llvm:: here?

629 ↗(On Diff #294228)
668 ↗(On Diff #294228)

I'm not a fan of messing with the found candidates or cost model to make this work.

If you wanted to handle candidates that appear once across many modules, I think it would be best to pre-populate a hash tree with known beneficial candidates versus trying to guess/mess with stuff during outlining?

Since the tree is serialized to JSON, it should be possible to pre-populate it without using the outliner...

Maybe it'd make sense to adapt the IR similarity framework for this portion somehow versus putting all of this in the outliner? It seems like generating the hash tree is really outside the scope of the pass. Consuming and using it seems okay though.

848 ↗(On Diff #294228)

remove braces

946 ↗(On Diff #294228)

remove braces

plotfi updated this revision to Diff 301092.Oct 27 2020, 1:17 PM

Updated based on @paquette's feedback. This only includes the StableHashTree data structure and a unit test.

plotfi retitled this revision from [RFC] HashTree and MachineOutliner HashTree Serialization for cross module data sharing. to [RFC] StableHashTree Implementation..Oct 27 2020, 1:17 PM
plotfi marked 20 inline comments as done.Oct 27 2020, 1:25 PM
plotfi added inline comments.

I thought this myself, but you need an IsTerminal flag because you could have some sequence you want to hash like:


as well as


You need the terminal to know that even though you have a node with successors that that know can be the terminal node in a sequence that was added.


Can I add this as a post commit NFC commit? I am unsure on the tradeoffs here at the moment.

plotfi marked an inline comment as done.Oct 30 2020, 11:20 AM
plotfi marked an inline comment as not done.Nov 2 2020, 9:58 AM

If this data structure is a trie, is there any reason you can't just improve the existing SuffixTree to do all of this?

A suffix tree is just a compressed trie.


Should IsTerminal ever be modified outside of Insert and readFromBuffer?

Would it make sense to have it be a private member with a getter?


Should this be in StableHashTree.cpp?


Needs documentation?

What happens if something inserted was already in the tree?


Seems like this may be a bit nicer as an Optional which returns where the thing was found?

Optional<HashNode *> find(const StableHashSequence &Sequence) const;

That way you can also access the specific node if you need it.

Or, even better, if you had an iterator type for this data structure you could do something like this:

iterator find(const StableHashSequence &Sequence) const;

I feel like the iterator idea is probably better, since it's more consistent with the rest of the LLVM data types. You could even have an edge_iterator and a vertex_iterator for edge/vertex walks.


Should these functions be in StableHashTree.cpp?


Missing comment?




Should be consistent with how JSON is capitalized in things the a person might see on the command line.


Nit: It's a bit nicer to read if you put the simpler situations as the one you continue from. This lessens the indentation level of the more complicated case:

if (I != Current->Successors.end()) {
  Current = I->second.get();

// Didn't find the hash in the current node's successors. Create a new one.
std::unique_ptr<HashNode> Next = std::make_unique<HashNode>();
// ...