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

RESOLVED FIXED in Firefox 44

Status

()

defect
RESOLVED FIXED
4 years ago
4 years ago

People

(Reporter: fitzgen, Assigned: fitzgen)

Tracking

unspecified
mozilla44
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox44 fixed)

Details

Attachments

(2 attachments, 3 obsolete attachments)

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

We should make this reusable, similar to JS::ubi::BreadthFirst.
Depends on: 1182653
Attachment #8664522 - Attachment is obsolete: true
Attachment #8664522 - Flags: review?(sphink)
Attachment #8664907 - Flags: review?(sphink)
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
Attachment #8664907 - Attachment is obsolete: true
Attachment #8664907 - Flags: review?(sphink)
Attachment #8665160 - Flags: review?(sphink)
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
Attachment #8664521 - Flags: review?(sphink) → review+
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.
Attachment #8665160 - Flags: review?(sphink) → review+
Added the missing header include. Assert that traverse() is only called once.
Keywords: checkin-needed
https://hg.mozilla.org/mozilla-central/rev/b9b74d5bd423
https://hg.mozilla.org/mozilla-central/rev/8bdf0fb54af3
Status: ASSIGNED → RESOLVED
Closed: 4 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla44
You need to log in before you can comment on or make changes to this bug.