1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set ts=8 sts=4 et sw=4 tw=99:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7 #ifndef js_UbiNodeDominatorTree_h
8 #define js_UbiNodeDominatorTree_h
10 #include "mozilla/Attributes.h"
11 #include "mozilla/DebugOnly.h"
12 #include "mozilla/Maybe.h"
13 #include "mozilla/Move.h"
14 #include "mozilla/UniquePtr.h"
16 #include "js/AllocPolicy.h"
17 #include "js/UbiNode.h"
18 #include "js/UbiNodePostOrder.h"
19 #include "js/Utility.h"
20 #include "js/Vector.h"
26 * In a directed graph with a root node `R`, a node `A` is said to "dominate" a
27 * node `B` iff every path from `R` to `B` contains `A`. A node `A` is said to
28 * be the "immediate dominator" of a node `B` iff it dominates `B`, is not `B`
29 * itself, and does not dominate any other nodes which also dominate `B` in
32 * If we take every node from a graph `G` and create a new graph `T` with edges
33 * to each node from its immediate dominator, then `T` is a tree (each node has
34 * only one immediate dominator, or none if it is the root). This tree is called
37 * This class represents a dominator tree constructed from a `JS::ubi::Node`
38 * heap graph. The domination relationship and dominator trees are useful tools
39 * for analyzing heap graphs because they tell you:
41 * - Exactly what could be reclaimed by the GC if some node `A` became
42 * unreachable: those nodes which are dominated by `A`,
44 * - The "retained size" of a node in the heap graph, in contrast to its
45 * "shallow size". The "shallow size" is the space taken by a node itself,
46 * not counting anything it references. The "retained size" of a node is its
47 * shallow size plus the size of all the things that would be collected if
48 * the original node wasn't (directly or indirectly) referencing them. In
49 * other words, the retained size is the shallow size of a node plus the
50 * shallow sizes of every other node it dominates. For example, the root
51 * node in a binary tree might have a small shallow size that does not take
52 * up much space itself, but it dominates the rest of the binary tree and
53 * its retained size is therefore significant (assuming no external
54 * references into the tree).
56 * The simple, engineered algorithm presented in "A Simple, Fast Dominance
57 * Algorithm" by Cooper el al[0] is used to find dominators and construct the
58 * dominator tree. This algorithm runs in O(n^2) time, but is faster in practice
59 * than alternative algorithms with better theoretical running times, such as
60 * Lengauer-Tarjan which runs in O(e * log(n)). The big caveat to that statement
61 * is that Cooper et al found it is faster in practice *on control flow graphs*
62 * and I'm not convinced that this property also holds on *heap* graphs. That
63 * said, the implementation of this algorithm is *much* simpler than
64 * Lengauer-Tarjan and has been found to be fast enough at least for the time
67 * [0]: http://www.cs.rice.edu/~keith/EMBED/dom.pdf
69 class JS_PUBLIC_API(DominatorTree
)
74 using PredecessorSets
= js::HashMap
<Node
, NodeSetPtr
, js::DefaultHasher
<Node
>,
75 js::SystemAllocPolicy
>;
76 using NodeToIndexMap
= js::HashMap
<Node
, uint32_t, js::DefaultHasher
<Node
>,
77 js::SystemAllocPolicy
>;
81 class DominatedSetRange
;
84 * A pointer to an immediately dominated node.
86 * Don't use this type directly; it is no safer than regular pointers. This
87 * is only for use indirectly with range-based for loops and
88 * `DominatedSetRange`.
90 * @see JS::ubi::DominatorTree::getDominatedSet
92 class DominatedNodePtr
94 friend class DominatedSetRange
;
96 const JS::ubi::Vector
<Node
>& postOrder
;
99 DominatedNodePtr(const JS::ubi::Vector
<Node
>& postOrder
, const uint32_t* ptr
)
100 : postOrder(postOrder
)
105 bool operator!=(const DominatedNodePtr
& rhs
) const { return ptr
!= rhs
.ptr
; }
106 void operator++() { ptr
++; }
107 const Node
& operator*() const { return postOrder
[*ptr
]; }
111 * A range of immediately dominated `JS::ubi::Node`s for use with
112 * range-based for loops.
114 * @see JS::ubi::DominatorTree::getDominatedSet
116 class DominatedSetRange
118 friend class DominatedSets
;
120 const JS::ubi::Vector
<Node
>& postOrder
;
121 const uint32_t* beginPtr
;
122 const uint32_t* endPtr
;
124 DominatedSetRange(JS::ubi::Vector
<Node
>& postOrder
, const uint32_t* begin
, const uint32_t* end
)
125 : postOrder(postOrder
)
129 MOZ_ASSERT(begin
<= end
);
133 DominatedNodePtr
begin() const {
134 MOZ_ASSERT(beginPtr
<= endPtr
);
135 return DominatedNodePtr(postOrder
, beginPtr
);
138 DominatedNodePtr
end() const {
139 return DominatedNodePtr(postOrder
, endPtr
);
142 size_t length() const {
143 MOZ_ASSERT(beginPtr
<= endPtr
);
144 return endPtr
- beginPtr
;
148 * Safely skip ahead `n` dominators in the range, in O(1) time.
152 * mozilla::Maybe<DominatedSetRange> range = myDominatorTree.getDominatedSet(myNode);
153 * if (range.isNothing()) {
154 * // Handle unknown nodes however you see fit...
158 * // Don't care about the first ten, for whatever reason.
160 * for (const JS::ubi::Node& dominatedNode : *range) {
164 void skip(size_t n
) {
166 if (beginPtr
> endPtr
)
173 * The set of all dominated sets in a dominator tree.
175 * Internally stores the sets in a contiguous array, with a side table of
176 * indices into that contiguous array to denote the start index of each
181 JS::ubi::Vector
<uint32_t> dominated
;
182 JS::ubi::Vector
<uint32_t> indices
;
184 DominatedSets(JS::ubi::Vector
<uint32_t>&& dominated
, JS::ubi::Vector
<uint32_t>&& indices
)
185 : dominated(std::move(dominated
))
186 , indices(std::move(indices
))
190 // DominatedSets is not copy-able.
191 DominatedSets(const DominatedSets
& rhs
) = delete;
192 DominatedSets
& operator=(const DominatedSets
& rhs
) = delete;
194 // DominatedSets is move-able.
195 DominatedSets(DominatedSets
&& rhs
)
196 : dominated(std::move(rhs
.dominated
))
197 , indices(std::move(rhs
.indices
))
199 MOZ_ASSERT(this != &rhs
, "self-move not allowed");
201 DominatedSets
& operator=(DominatedSets
&& rhs
) {
202 this->~DominatedSets();
203 new (this) DominatedSets(std::move(rhs
));
208 * Create the DominatedSets given the mapping of a node index to its
209 * immediate dominator. Returns `Some` on success, `Nothing` on OOM
212 static mozilla::Maybe
<DominatedSets
> Create(const JS::ubi::Vector
<uint32_t>& doms
) {
213 auto length
= doms
.length();
214 MOZ_ASSERT(length
< UINT32_MAX
);
216 // Create a vector `dominated` holding a flattened set of buckets of
217 // immediately dominated children nodes, with a lookup table
218 // `indices` mapping from each node to the beginning of its bucket.
220 // This has three phases:
222 // 1. Iterate over the full set of nodes and count up the size of
223 // each bucket. These bucket sizes are temporarily stored in the
226 // 2. Convert the `indices` vector to store the cumulative sum of
227 // the sizes of all buckets before each index, resulting in a
228 // mapping from node index to one past the end of that node's
231 // 3. Iterate over the full set of nodes again, filling in bucket
232 // entries from the end of the bucket's range to its
233 // beginning. This decrements each index as a bucket entry is
234 // filled in. After having filled in all of a bucket's entries,
235 // the index points to the start of the bucket.
237 JS::ubi::Vector
<uint32_t> dominated
;
238 JS::ubi::Vector
<uint32_t> indices
;
239 if (!dominated
.growBy(length
) || !indices
.growBy(length
))
240 return mozilla::Nothing();
243 memset(indices
.begin(), 0, length
* sizeof(uint32_t));
244 for (uint32_t i
= 0; i
< length
; i
++)
248 uint32_t sumOfSizes
= 0;
249 for (uint32_t i
= 0; i
< length
; i
++) {
250 sumOfSizes
+= indices
[i
];
251 MOZ_ASSERT(sumOfSizes
<= length
);
252 indices
[i
] = sumOfSizes
;
256 for (uint32_t i
= 0; i
< length
; i
++) {
257 auto idxOfDom
= doms
[i
];
259 dominated
[indices
[idxOfDom
]] = i
;
263 // Assert that our buckets are non-overlapping and don't run off the
264 // end of the vector.
265 uint32_t lastIndex
= 0;
266 for (uint32_t i
= 0; i
< length
; i
++) {
267 MOZ_ASSERT(indices
[i
] >= lastIndex
);
268 MOZ_ASSERT(indices
[i
] < length
);
269 lastIndex
= indices
[i
];
273 return mozilla::Some(DominatedSets(std::move(dominated
), std::move(indices
)));
277 * Get the set of nodes immediately dominated by the node at
278 * `postOrder[nodeIndex]`.
280 DominatedSetRange
dominatedSet(JS::ubi::Vector
<Node
>& postOrder
, uint32_t nodeIndex
) const {
281 MOZ_ASSERT(postOrder
.length() == indices
.length());
282 MOZ_ASSERT(nodeIndex
< indices
.length());
283 auto end
= nodeIndex
== indices
.length() - 1
285 : &dominated
[indices
[nodeIndex
+ 1]];
286 return DominatedSetRange(postOrder
, &dominated
[indices
[nodeIndex
]], end
);
292 JS::ubi::Vector
<Node
> postOrder
;
293 NodeToIndexMap nodeToPostOrderIndex
;
294 JS::ubi::Vector
<uint32_t> doms
;
295 DominatedSets dominatedSets
;
296 mozilla::Maybe
<JS::ubi::Vector
<JS::ubi::Node::Size
>> retainedSizes
;
299 // We use `UNDEFINED` as a sentinel value in the `doms` vector to signal
300 // that we haven't found any dominators for the node at the corresponding
301 // index in `postOrder` yet.
302 static const uint32_t UNDEFINED
= UINT32_MAX
;
304 DominatorTree(JS::ubi::Vector
<Node
>&& postOrder
, NodeToIndexMap
&& nodeToPostOrderIndex
,
305 JS::ubi::Vector
<uint32_t>&& doms
, DominatedSets
&& dominatedSets
)
306 : postOrder(std::move(postOrder
))
307 , nodeToPostOrderIndex(std::move(nodeToPostOrderIndex
))
308 , doms(std::move(doms
))
309 , dominatedSets(std::move(dominatedSets
))
310 , retainedSizes(mozilla::Nothing())
313 static uint32_t intersect(JS::ubi::Vector
<uint32_t>& doms
, uint32_t finger1
, uint32_t finger2
) {
314 while (finger1
!= finger2
) {
315 if (finger1
< finger2
)
316 finger1
= doms
[finger1
];
317 else if (finger2
< finger1
)
318 finger2
= doms
[finger2
];
323 // Do the post order traversal of the heap graph and populate our
325 static MOZ_MUST_USE
bool doTraversal(JSContext
* cx
, AutoCheckCannotGC
& noGC
, const Node
& root
,
326 JS::ubi::Vector
<Node
>& postOrder
,
327 PredecessorSets
& predecessorSets
) {
328 uint32_t nodeCount
= 0;
329 auto onNode
= [&](const Node
& node
) {
331 if (MOZ_UNLIKELY(nodeCount
== UINT32_MAX
))
333 return postOrder
.append(node
);
336 auto onEdge
= [&](const Node
& origin
, const Edge
& edge
) {
337 auto p
= predecessorSets
.lookupForAdd(edge
.referent
);
339 mozilla::UniquePtr
<NodeSet
, DeletePolicy
<NodeSet
>> set(js_new
<NodeSet
>());
342 !predecessorSets
.add(p
, edge
.referent
, std::move(set
)))
347 MOZ_ASSERT(p
&& p
->value());
348 return p
->value()->put(origin
);
351 PostOrder
traversal(cx
, noGC
);
352 return traversal
.init() &&
353 traversal
.addStart(root
) &&
354 traversal
.traverse(onNode
, onEdge
);
357 // Populates the given `map` with an entry for each node to its index in
359 static MOZ_MUST_USE
bool mapNodesToTheirIndices(JS::ubi::Vector
<Node
>& postOrder
,
360 NodeToIndexMap
& map
) {
361 MOZ_ASSERT(!map
.initialized());
362 MOZ_ASSERT(postOrder
.length() < UINT32_MAX
);
363 uint32_t length
= postOrder
.length();
364 if (!map
.init(length
))
366 for (uint32_t i
= 0; i
< length
; i
++)
367 map
.putNewInfallible(postOrder
[i
], i
);
371 // Convert the Node -> NodeSet predecessorSets to a index -> Vector<index>
373 static MOZ_MUST_USE
bool convertPredecessorSetsToVectors(
375 JS::ubi::Vector
<Node
>& postOrder
,
376 PredecessorSets
& predecessorSets
,
377 NodeToIndexMap
& nodeToPostOrderIndex
,
378 JS::ubi::Vector
<JS::ubi::Vector
<uint32_t>>& predecessorVectors
)
380 MOZ_ASSERT(postOrder
.length() < UINT32_MAX
);
381 uint32_t length
= postOrder
.length();
383 MOZ_ASSERT(predecessorVectors
.length() == 0);
384 if (!predecessorVectors
.growBy(length
))
387 for (uint32_t i
= 0; i
< length
- 1; i
++) {
388 auto& node
= postOrder
[i
];
389 MOZ_ASSERT(node
!= root
,
390 "Only the last node should be root, since this was a post order traversal.");
392 auto ptr
= predecessorSets
.lookup(node
);
394 "Because this isn't the root, it had better have predecessors, or else how "
395 "did we even find it.");
397 auto& predecessors
= ptr
->value();
398 if (!predecessorVectors
[i
].reserve(predecessors
->count()))
400 for (auto range
= predecessors
->all(); !range
.empty(); range
.popFront()) {
401 auto ptr
= nodeToPostOrderIndex
.lookup(range
.front());
403 predecessorVectors
[i
].infallibleAppend(ptr
->value());
406 predecessorSets
.finish();
410 // Initialize `doms` such that the immediate dominator of the `root` is the
411 // `root` itself and all others are `UNDEFINED`.
412 static MOZ_MUST_USE
bool initializeDominators(JS::ubi::Vector
<uint32_t>& doms
,
414 MOZ_ASSERT(doms
.length() == 0);
415 if (!doms
.growByUninitialized(length
))
417 doms
[length
- 1] = length
- 1;
418 for (uint32_t i
= 0; i
< length
- 1; i
++)
423 void assertSanity() const {
424 MOZ_ASSERT(postOrder
.length() == doms
.length());
425 MOZ_ASSERT(postOrder
.length() == nodeToPostOrderIndex
.count());
426 MOZ_ASSERT_IF(retainedSizes
.isSome(), postOrder
.length() == retainedSizes
->length());
429 MOZ_MUST_USE
bool computeRetainedSizes(mozilla::MallocSizeOf mallocSizeOf
) {
430 MOZ_ASSERT(retainedSizes
.isNothing());
431 auto length
= postOrder
.length();
433 retainedSizes
.emplace();
434 if (!retainedSizes
->growBy(length
)) {
435 retainedSizes
= mozilla::Nothing();
439 // Iterate in forward order so that we know all of a node's children in
440 // the dominator tree have already had their retained size
441 // computed. Then we can simply say that the retained size of a node is
442 // its shallow size (JS::ubi::Node::size) plus the retained sizes of its
443 // immediate children in the tree.
445 for (uint32_t i
= 0; i
< length
; i
++) {
446 auto size
= postOrder
[i
].size(mallocSizeOf
);
448 for (const auto& dominated
: dominatedSets
.dominatedSet(postOrder
, i
)) {
449 // The root node dominates itself, but shouldn't contribute to
450 // its own retained size.
451 if (dominated
== postOrder
[length
- 1]) {
452 MOZ_ASSERT(i
== length
- 1);
456 auto ptr
= nodeToPostOrderIndex
.lookup(dominated
);
458 auto idxOfDominated
= ptr
->value();
459 MOZ_ASSERT(idxOfDominated
< i
);
460 size
+= retainedSizes
.ref()[idxOfDominated
];
463 retainedSizes
.ref()[i
] = size
;
470 // DominatorTree is not copy-able.
471 DominatorTree(const DominatorTree
&) = delete;
472 DominatorTree
& operator=(const DominatorTree
&) = delete;
474 // DominatorTree is move-able.
475 DominatorTree(DominatorTree
&& rhs
)
476 : postOrder(std::move(rhs
.postOrder
))
477 , nodeToPostOrderIndex(std::move(rhs
.nodeToPostOrderIndex
))
478 , doms(std::move(rhs
.doms
))
479 , dominatedSets(std::move(rhs
.dominatedSets
))
480 , retainedSizes(std::move(rhs
.retainedSizes
))
482 MOZ_ASSERT(this != &rhs
, "self-move is not allowed");
484 DominatorTree
& operator=(DominatorTree
&& rhs
) {
485 this->~DominatorTree();
486 new (this) DominatorTree(std::move(rhs
));
491 * Construct a `DominatorTree` of the heap graph visible from `root`. The
492 * `root` is also used as the root of the resulting dominator tree.
494 * The resulting `DominatorTree` instance must not outlive the
495 * `JS::ubi::Node` graph it was constructed from.
497 * - For `JS::ubi::Node` graphs backed by the live heap graph, this means
498 * that the `DominatorTree`'s lifetime _must_ be contained within the
499 * scope of the provided `AutoCheckCannotGC` reference because a GC will
500 * invalidate the nodes.
502 * - For `JS::ubi::Node` graphs backed by some other offline structure
503 * provided by the embedder, the resulting `DominatorTree`'s lifetime is
504 * bounded by that offline structure's lifetime.
506 * In practice, this means that within SpiderMonkey we must treat
507 * `DominatorTree` as if it were backed by the live heap graph and trust
508 * that embedders with knowledge of the graph's implementation will do the
511 * Returns `mozilla::Nothing()` on OOM failure. It is the caller's
512 * responsibility to handle and report the OOM.
514 static mozilla::Maybe
<DominatorTree
>
515 Create(JSContext
* cx
, AutoCheckCannotGC
& noGC
, const Node
& root
) {
516 JS::ubi::Vector
<Node
> postOrder
;
517 PredecessorSets predecessorSets
;
518 if (!predecessorSets
.init() || !doTraversal(cx
, noGC
, root
, postOrder
, predecessorSets
))
519 return mozilla::Nothing();
521 MOZ_ASSERT(postOrder
.length() < UINT32_MAX
);
522 uint32_t length
= postOrder
.length();
523 MOZ_ASSERT(postOrder
[length
- 1] == root
);
525 // From here on out we wish to avoid hash table lookups, and we use
526 // indices into `postOrder` instead of actual nodes wherever
527 // possible. This greatly improves the performance of this
528 // implementation, but we have to pay a little bit of upfront cost to
529 // convert our data structures to play along first.
531 NodeToIndexMap nodeToPostOrderIndex
;
532 if (!mapNodesToTheirIndices(postOrder
, nodeToPostOrderIndex
))
533 return mozilla::Nothing();
535 JS::ubi::Vector
<JS::ubi::Vector
<uint32_t>> predecessorVectors
;
536 if (!convertPredecessorSetsToVectors(root
, postOrder
, predecessorSets
, nodeToPostOrderIndex
,
538 return mozilla::Nothing();
540 JS::ubi::Vector
<uint32_t> doms
;
541 if (!initializeDominators(doms
, length
))
542 return mozilla::Nothing();
548 // Iterate over the non-root nodes in reverse post order.
549 for (uint32_t indexPlusOne
= length
- 1; indexPlusOne
> 0; indexPlusOne
--) {
550 MOZ_ASSERT(postOrder
[indexPlusOne
- 1] != root
);
552 // Take the intersection of every predecessor's dominator set;
553 // that is the current best guess at the immediate dominator for
556 uint32_t newIDomIdx
= UNDEFINED
;
558 auto& predecessors
= predecessorVectors
[indexPlusOne
- 1];
559 auto range
= predecessors
.all();
560 for ( ; !range
.empty(); range
.popFront()) {
561 auto idx
= range
.front();
562 if (doms
[idx
] != UNDEFINED
) {
568 MOZ_ASSERT(newIDomIdx
!= UNDEFINED
,
569 "Because the root is initialized to dominate itself and is the first "
570 "node in every path, there must exist a predecessor to this node that "
571 "also has a dominator.");
573 for ( ; !range
.empty(); range
.popFront()) {
574 auto idx
= range
.front();
575 if (doms
[idx
] != UNDEFINED
)
576 newIDomIdx
= intersect(doms
, newIDomIdx
, idx
);
579 // If the immediate dominator changed, we will have to do
580 // another pass of the outer while loop to continue the forward
582 if (newIDomIdx
!= doms
[indexPlusOne
- 1]) {
583 doms
[indexPlusOne
- 1] = newIDomIdx
;
589 auto maybeDominatedSets
= DominatedSets::Create(doms
);
590 if (maybeDominatedSets
.isNothing())
591 return mozilla::Nothing();
593 return mozilla::Some(DominatorTree(std::move(postOrder
),
594 std::move(nodeToPostOrderIndex
),
596 std::move(*maybeDominatedSets
)));
600 * Get the root node for this dominator tree.
602 const Node
& root() const {
603 return postOrder
[postOrder
.length() - 1];
607 * Return the immediate dominator of the given `node`. If `node` was not
608 * reachable from the `root` that this dominator tree was constructed from,
609 * then return the null `JS::ubi::Node`.
611 Node
getImmediateDominator(const Node
& node
) const {
613 auto ptr
= nodeToPostOrderIndex
.lookup(node
);
617 auto idx
= ptr
->value();
618 MOZ_ASSERT(idx
< postOrder
.length());
619 return postOrder
[doms
[idx
]];
623 * Get the set of nodes immediately dominated by the given `node`. If `node`
624 * is not a member of this dominator tree, return `Nothing`.
628 * mozilla::Maybe<DominatedSetRange> range = myDominatorTree.getDominatedSet(myNode);
629 * if (range.isNothing()) {
630 * // Handle unknown node however you see fit...
634 * for (const JS::ubi::Node& dominatedNode : *range) {
635 * // Do something with each immediately dominated node...
638 mozilla::Maybe
<DominatedSetRange
> getDominatedSet(const Node
& node
) {
640 auto ptr
= nodeToPostOrderIndex
.lookup(node
);
642 return mozilla::Nothing();
644 auto idx
= ptr
->value();
645 MOZ_ASSERT(idx
< postOrder
.length());
646 return mozilla::Some(dominatedSets
.dominatedSet(postOrder
, idx
));
650 * Get the retained size of the given `node`. The size is placed in
651 * `outSize`, or 0 if `node` is not a member of the dominator tree. Returns
652 * false on OOM failure, leaving `outSize` unchanged.
654 MOZ_MUST_USE
bool getRetainedSize(const Node
& node
, mozilla::MallocSizeOf mallocSizeOf
,
655 Node::Size
& outSize
) {
657 auto ptr
= nodeToPostOrderIndex
.lookup(node
);
663 if (retainedSizes
.isNothing() && !computeRetainedSizes(mallocSizeOf
))
666 auto idx
= ptr
->value();
667 MOZ_ASSERT(idx
< postOrder
.length());
668 outSize
= retainedSizes
.ref()[idx
];
676 #endif // js_UbiNodeDominatorTree_h