1206290 - Implement a JS::ubi::PostOrder depth first traversal

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

To compute dominator trees, we need to do post order traversals.

We should make this reusable, similar to JS::ubi::BreadthFirst.

Comment 1

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: Part 0: Move js/UbiNodeTraverse.h to js/UbiNodeBreadthFirst.h

Comment 2

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: Part 1: Implement a JS::ubi::PostOrder depth first traversal

Comment 3

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Try push: https://treeherder.mozilla.org/#/jobs?repo=try&revision=2b888e6e0297

Comment 4

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: Part 1: Implement a JS::ubi::PostOrder depth first traversal

Comment 5

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

warnings-as-errors really didn't like that I specialized JS::ubi::Concrete outside of the JS::ubi namespace :-/

New try push: https://treeherder.mozilla.org/#/jobs?repo=try&revision=54d7965acfa1

Comment 6

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: Part 1: Implement a JS::ubi::PostOrder depth first traversal

Comment 7

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Sorry for the bug spam. This version has a fix for the bad header include order and make OriginAndEdges' move construction/assignment explicit since msvc won't create defaults for them.

New try push: https://treeherder.mozilla.org/#/jobs?repo=try&revision=e7680389dfee

Comment 8

[Steve Fink [:sfink] [:s:]]

Comment on attachment 8665160 [details] [diff] [review]
Part 1: Implement a JS::ubi::PostOrder depth first traversal

Review of attachment 8665160 [details] [diff] [review]:
-----------------------------------------------------------------

lgtm

::: js/public/UbiNodePostOrder.h
@@ +11,5 @@
> +
> +#include "js/UbiNode.h"
> +#include "js/Utility.h"
> +#include "js/Vector.h"
> +

#include "mozilla/Move.h"

@@ +75,5 @@
> +  private:
> +    bool fillEdgesFromRange(EdgeVector& edges, UniquePtr<EdgeRange>& range) {
> +        MOZ_ASSERT(range);
> +        for ( ; !range->empty(); range->popFront()) {
> +            if (!edges.append(mozilla::Move(range->front())))

isn't this Move() redundant?

@@ +117,5 @@
> +    // Traverse the graph in post-order, starting with the set of nodes passed
> +    // to `addStart` and applying `visitor::operator()` for each node in
> +    // the graph, as described above.
> +    //
> +    // This should be called only once per instance of this class.

That's funky. I guess the only reason you have an object at all here is so you can split out the addStart calls from everything else? It seems like this should be asserted. Or let it happen, and define the semantics -- as long as you don't mutate the graph, you can call addStart again and find out what is only reachable from that node (or nodes). But that doesn't seem very useful.

Comment 9

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: Part 1: Implement a JS::ubi::PostOrder depth first traversal

Comment 10

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Added the missing header include. Assert that traverse() is only called once.

Comment 11

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/b9b74d5bd423
https://hg.mozilla.org/integration/mozilla-inbound/rev/8bdf0fb54af3

Comment 12

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/b9b74d5bd423
https://hg.mozilla.org/mozilla-central/rev/8bdf0fb54af3