Page MenuHomePhabricator

Implementation of the root ordering algorithm

Authored by sfuniak on Aug 23 2021, 5:31 AM.



This is commit 3 of 4 for the multi-root matching in PDL, discussed in (topic flagged for review).

We form a graph over the specified roots, provided in pdl.rewrite, where two roots are connected by a directed edge if the target root can be connected (via a chain of operations) in the underlying pattern to the source root. We place a restriction that the path connecting the two candidate roots must only contain the nodes in the subgraphs underneath these two roots. The cost of an edge is the smallest number of upward traversals (edges) required to go from the source to the target root, and the connector is a Value in the intersection of the two subtrees rooted at the source and target root that results in that smallest number of such upward traversals. Optimal root ordering is then formulated as the problem of finding a spanning arborescence (i.e., a directed spanning tree) of minimal weight.

In order to determine the spanning arborescence (directed spanning tree) of minimum weight, we use the Edmonds' algorithm. The worst-case computational complexity of this algorithm is O(_N_^3) for a single root, where _N_ is the number of specified roots. The pdl-to-pdl_interp lowering calls this algorithm as a subroutine _N_ times (once for each candidate root), so the overall complexity of root ordering is O(_N_^4). If needed, this complexity could be reduced to O(_N_^3) with a more efficient algorithm. However, note that the underlying implementation is very efficient, and _N_ in our instances tends to be very small (<10). Therefore, we believe that the proposed (asymptotically suboptimal) implementation will suffice for now.

Testing: a unit test of the algorithm

Diff Detail

Event Timeline

sfuniak created this revision.Aug 23 2021, 5:31 AM
sfuniak requested review of this revision.Aug 23 2021, 5:31 AM
Mogball added a subscriber: Mogball.Oct 7 2021, 8:23 PM
Mogball added inline comments.

nit: e = graph.end(); outer != e


Can you estimate a required size for reserve? Depending on the STL implementation, the initializer_list constructor will guarantee that the first insertion will need to re-allocate.

sfuniak updated this revision to Diff 378559.Oct 10 2021, 8:47 PM

Addressed review feedback.

rriddle added inline comments.Oct 12 2021, 12:01 AM
1–3 ↗(On Diff #378559)

We generally don't expose implementation headers via the public include/ directory. Unit tests for these types of components generally just use relative include to the necessary header in the implementation folder, e.g.

32 ↗(On Diff #378559)

Is this still the case? Or are the roots selected from the match part of a pdl.pattern?

Also, do we have verification that all of the operations are connected in some form with a pdl.pattern? (i.e. when the root to the pdl.rewrite isn't provided)

62 ↗(On Diff #378559)
78 ↗(On Diff #378559)

Is there a benefit to using double map vs something like DenseMap<std::pair<Value, Value>, RootOrderingCost>?

96 ↗(On Diff #378559)

nit: Drop the explicit for multi-parameter constructors.

98–99 ↗(On Diff #378559)

Can you document the result value here?


nit: assert messages should start with lower case


Can you document the cost update here.


Won't this invalidate your current iterator? Could you switch this loop to use llvm::make_early_inc_range instead?


Can you move most of this documentation to the header instead?


Given that this is always true for the first iteration, switch to a do/while?


nit: Can you spell out auto here?


nit: Drop the std:: from size_t


Feel free to just inline this into the header.


Thanks, I will make the changes suggested.

32 ↗(On Diff #378559)

Stale comment, will fix.

In general, the operations in the pdl.pattern must form a connected tree for this algorithm to succeed, whether we detect the root automatically or the user provides it explicitly. In the latter case, we still call this algorithm, on the provided root, in order to determine the best way to connect the roots. I believe the code asserts if the tree is not connected, but you are right in saying that we should verify this explicitly in the pdl.pattern. I will add the check to the last stack diff.

78 ↗(On Diff #378559)

Yes, it is quite important that these are stored as nested maps, so that you can iterate the in-neighbors of a single vertex efficiently.


You are right, thanks for pointing this out. I will make the change you suggested.

sfuniak marked 9 inline comments as done.Oct 17 2021, 5:24 PM
sfuniak added inline comments.

On the second thought, I find the llvm::make_early_inc_range too magical and (assuming we use range-based for loop) somewhat less performant, because we'd erase by the key rather than iterator. I will fix the bug differently.


parents is a DenseMap, and its value type is an implementation detail llvm::detail::DenseMapPair<KeyT, ValueT>. will add some more documentation instead.

sfuniak updated this revision to Diff 380913.Oct 20 2021, 5:41 AM

Addressed review feedback.

rriddle accepted this revision.Oct 28 2021, 11:27 AM

LG, thanks.

This revision is now accepted and ready to land.Oct 28 2021, 11:27 AM
sfuniak updated this revision to Diff 384963.Thu, Nov 4, 9:51 PM


This revision was automatically updated to reflect the committed changes.

The unit-tests seems leaky:

You should be able to reproduce locally with '-DLLVM_USE_SANITIZER=Address;Undefined' (and using clang as host compiler)

I am not able to reproduce the leak on Apple clang version 12.0.5 (running on M1). Will try on a different machine tomorrow.