1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 * vim: set ts=8 sts=2 et sw=2 tw=80:
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/UniquePtr.h"
17 #include "js/AllocPolicy.h"
18 #include "js/UbiNode.h"
19 #include "js/UbiNodePostOrder.h"
20 #include "js/Utility.h"
21 #include "js/Vector.h"
27 * In a directed graph with a root node `R`, a node `A` is said to "dominate" a
28 * node `B` iff every path from `R` to `B` contains `A`. A node `A` is said to
29 * be the "immediate dominator" of a node `B` iff it dominates `B`, is not `B`
30 * itself, and does not dominate any other nodes which also dominate `B` in
33 * If we take every node from a graph `G` and create a new graph `T` with edges
34 * to each node from its immediate dominator, then `T` is a tree (each node has
35 * only one immediate dominator, or none if it is the root). This tree is called
38 * This class represents a dominator tree constructed from a `JS::ubi::Node`
39 * heap graph. The domination relationship and dominator trees are useful tools
40 * for analyzing heap graphs because they tell you:
42 * - Exactly what could be reclaimed by the GC if some node `A` became
43 * unreachable: those nodes which are dominated by `A`,
45 * - The "retained size" of a node in the heap graph, in contrast to its
46 * "shallow size". The "shallow size" is the space taken by a node itself,
47 * not counting anything it references. The "retained size" of a node is its
48 * shallow size plus the size of all the things that would be collected if
49 * the original node wasn't (directly or indirectly) referencing them. In
50 * other words, the retained size is the shallow size of a node plus the
51 * shallow sizes of every other node it dominates. For example, the root
52 * node in a binary tree might have a small shallow size that does not take
53 * up much space itself, but it dominates the rest of the binary tree and
54 * its retained size is therefore significant (assuming no external
55 * references into the tree).
57 * The simple, engineered algorithm presented in "A Simple, Fast Dominance
58 * Algorithm" by Cooper el al[0] is used to find dominators and construct the
59 * dominator tree. This algorithm runs in O(n^2) time, but is faster in practice
60 * than alternative algorithms with better theoretical running times, such as
61 * Lengauer-Tarjan which runs in O(e * log(n)). The big caveat to that statement
62 * is that Cooper et al found it is faster in practice *on control flow graphs*
63 * and I'm not convinced that this property also holds on *heap* graphs. That
64 * said, the implementation of this algorithm is *much* simpler than
65 * Lengauer-Tarjan and has been found to be fast enough at least for the time
68 * [0]: http://www.cs.rice.edu/~keith/EMBED/dom.pdf
70 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
{
93 friend class DominatedSetRange
;
95 const JS::ubi::Vector
<Node
>& postOrder
;
98 DominatedNodePtr(const JS::ubi::Vector
<Node
>& postOrder
,
100 : postOrder(postOrder
), ptr(ptr
) {}
103 bool operator!=(const DominatedNodePtr
& rhs
) const {
104 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
{
117 friend class DominatedSets
;
119 const JS::ubi::Vector
<Node
>& postOrder
;
120 const uint32_t* beginPtr
;
121 const uint32_t* endPtr
;
123 DominatedSetRange(JS::ubi::Vector
<Node
>& postOrder
, const uint32_t* begin
,
125 : postOrder(postOrder
), beginPtr(begin
), endPtr(end
) {
126 MOZ_ASSERT(begin
<= end
);
130 DominatedNodePtr
begin() const {
131 MOZ_ASSERT(beginPtr
<= endPtr
);
132 return DominatedNodePtr(postOrder
, beginPtr
);
135 DominatedNodePtr
end() const { return DominatedNodePtr(postOrder
, endPtr
); }
137 size_t length() const {
138 MOZ_ASSERT(beginPtr
<= endPtr
);
139 return endPtr
- beginPtr
;
143 * Safely skip ahead `n` dominators in the range, in O(1) time.
147 * mozilla::Maybe<DominatedSetRange> range =
148 * myDominatorTree.getDominatedSet(myNode);
149 * if (range.isNothing()) {
150 * // Handle unknown nodes however you see fit...
154 * // Don't care about the first ten, for whatever reason.
156 * for (const JS::ubi::Node& dominatedNode : *range) {
160 void skip(size_t n
) {
162 if (beginPtr
> endPtr
) {
170 * The set of all dominated sets in a dominator tree.
172 * Internally stores the sets in a contiguous array, with a side table of
173 * indices into that contiguous array to denote the start index of each
176 class DominatedSets
{
177 JS::ubi::Vector
<uint32_t> dominated
;
178 JS::ubi::Vector
<uint32_t> indices
;
180 DominatedSets(JS::ubi::Vector
<uint32_t>&& dominated
,
181 JS::ubi::Vector
<uint32_t>&& indices
)
182 : dominated(std::move(dominated
)), indices(std::move(indices
)) {}
185 // DominatedSets is not copy-able.
186 DominatedSets(const DominatedSets
& rhs
) = delete;
187 DominatedSets
& operator=(const DominatedSets
& rhs
) = delete;
189 // DominatedSets is move-able.
190 DominatedSets(DominatedSets
&& rhs
)
191 : dominated(std::move(rhs
.dominated
)), indices(std::move(rhs
.indices
)) {
192 MOZ_ASSERT(this != &rhs
, "self-move not allowed");
194 DominatedSets
& operator=(DominatedSets
&& rhs
) {
195 this->~DominatedSets();
196 new (this) DominatedSets(std::move(rhs
));
201 * Create the DominatedSets given the mapping of a node index to its
202 * immediate dominator. Returns `Some` on success, `Nothing` on OOM
205 static mozilla::Maybe
<DominatedSets
> Create(
206 const JS::ubi::Vector
<uint32_t>& doms
) {
207 auto length
= doms
.length();
208 MOZ_ASSERT(length
< UINT32_MAX
);
210 // Create a vector `dominated` holding a flattened set of buckets of
211 // immediately dominated children nodes, with a lookup table
212 // `indices` mapping from each node to the beginning of its bucket.
214 // This has three phases:
216 // 1. Iterate over the full set of nodes and count up the size of
217 // each bucket. These bucket sizes are temporarily stored in the
220 // 2. Convert the `indices` vector to store the cumulative sum of
221 // the sizes of all buckets before each index, resulting in a
222 // mapping from node index to one past the end of that node's
225 // 3. Iterate over the full set of nodes again, filling in bucket
226 // entries from the end of the bucket's range to its
227 // beginning. This decrements each index as a bucket entry is
228 // filled in. After having filled in all of a bucket's entries,
229 // the index points to the start of the bucket.
231 JS::ubi::Vector
<uint32_t> dominated
;
232 JS::ubi::Vector
<uint32_t> indices
;
233 if (!dominated
.growBy(length
) || !indices
.growBy(length
)) {
234 return mozilla::Nothing();
238 memset(indices
.begin(), 0, length
* sizeof(uint32_t));
239 for (uint32_t i
= 0; i
< length
; i
++) {
244 uint32_t sumOfSizes
= 0;
245 for (uint32_t i
= 0; i
< length
; i
++) {
246 sumOfSizes
+= indices
[i
];
247 MOZ_ASSERT(sumOfSizes
<= length
);
248 indices
[i
] = sumOfSizes
;
252 for (uint32_t i
= 0; i
< length
; i
++) {
253 auto idxOfDom
= doms
[i
];
255 dominated
[indices
[idxOfDom
]] = i
;
259 // Assert that our buckets are non-overlapping and don't run off the
260 // end of the vector.
261 uint32_t lastIndex
= 0;
262 for (uint32_t i
= 0; i
< length
; i
++) {
263 MOZ_ASSERT(indices
[i
] >= lastIndex
);
264 MOZ_ASSERT(indices
[i
] < length
);
265 lastIndex
= indices
[i
];
269 return mozilla::Some(
270 DominatedSets(std::move(dominated
), std::move(indices
)));
274 * Get the set of nodes immediately dominated by the node at
275 * `postOrder[nodeIndex]`.
277 DominatedSetRange
dominatedSet(JS::ubi::Vector
<Node
>& postOrder
,
278 uint32_t nodeIndex
) const {
279 MOZ_ASSERT(postOrder
.length() == indices
.length());
280 MOZ_ASSERT(nodeIndex
< indices
.length());
281 auto end
= nodeIndex
== indices
.length() - 1
283 : &dominated
[indices
[nodeIndex
+ 1]];
284 return DominatedSetRange(postOrder
, &dominated
[indices
[nodeIndex
]], end
);
290 JS::ubi::Vector
<Node
> postOrder
;
291 NodeToIndexMap nodeToPostOrderIndex
;
292 JS::ubi::Vector
<uint32_t> doms
;
293 DominatedSets dominatedSets
;
294 mozilla::Maybe
<JS::ubi::Vector
<JS::ubi::Node::Size
>> retainedSizes
;
297 // We use `UNDEFINED` as a sentinel value in the `doms` vector to signal
298 // that we haven't found any dominators for the node at the corresponding
299 // index in `postOrder` yet.
300 static const uint32_t UNDEFINED
= UINT32_MAX
;
302 DominatorTree(JS::ubi::Vector
<Node
>&& postOrder
,
303 NodeToIndexMap
&& nodeToPostOrderIndex
,
304 JS::ubi::Vector
<uint32_t>&& doms
, DominatedSets
&& dominatedSets
)
305 : postOrder(std::move(postOrder
)),
306 nodeToPostOrderIndex(std::move(nodeToPostOrderIndex
)),
307 doms(std::move(doms
)),
308 dominatedSets(std::move(dominatedSets
)),
309 retainedSizes(mozilla::Nothing()) {}
311 static uint32_t intersect(JS::ubi::Vector
<uint32_t>& doms
, uint32_t finger1
,
313 while (finger1
!= finger2
) {
314 if (finger1
< finger2
) {
315 finger1
= doms
[finger1
];
316 } else if (finger2
< finger1
) {
317 finger2
= doms
[finger2
];
323 // Do the post order traversal of the heap graph and populate our
325 [[nodiscard
]] static bool doTraversal(JSContext
* cx
, AutoCheckCannotGC
& noGC
,
327 JS::ubi::Vector
<Node
>& postOrder
,
328 PredecessorSets
& predecessorSets
) {
329 uint32_t nodeCount
= 0;
330 auto onNode
= [&](const Node
& node
) {
332 if (MOZ_UNLIKELY(nodeCount
== UINT32_MAX
)) {
335 return postOrder
.append(node
);
338 auto onEdge
= [&](const Node
& origin
, const Edge
& edge
) {
339 auto p
= predecessorSets
.lookupForAdd(edge
.referent
);
341 mozilla::UniquePtr
<NodeSet
, DeletePolicy
<NodeSet
>> set(
343 if (!set
|| !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
.addStart(root
) && traversal
.traverse(onNode
, onEdge
);
355 // Populates the given `map` with an entry for each node to its index in
357 [[nodiscard
]] static bool mapNodesToTheirIndices(
358 JS::ubi::Vector
<Node
>& postOrder
, NodeToIndexMap
& map
) {
359 MOZ_ASSERT(map
.empty());
360 MOZ_ASSERT(postOrder
.length() < UINT32_MAX
);
361 uint32_t length
= postOrder
.length();
362 if (!map
.reserve(length
)) {
365 for (uint32_t i
= 0; i
< length
; i
++) {
366 map
.putNewInfallible(postOrder
[i
], i
);
371 // Convert the Node -> NodeSet predecessorSets to a index -> Vector<index>
373 [[nodiscard
]] static bool convertPredecessorSetsToVectors(
374 const Node
& root
, JS::ubi::Vector
<Node
>& postOrder
,
375 PredecessorSets
& predecessorSets
, NodeToIndexMap
& nodeToPostOrderIndex
,
376 JS::ubi::Vector
<JS::ubi::Vector
<uint32_t>>& predecessorVectors
) {
377 MOZ_ASSERT(postOrder
.length() < UINT32_MAX
);
378 uint32_t length
= postOrder
.length();
380 MOZ_ASSERT(predecessorVectors
.length() == 0);
381 if (!predecessorVectors
.growBy(length
)) {
385 for (uint32_t i
= 0; i
< length
- 1; i
++) {
386 auto& node
= postOrder
[i
];
387 MOZ_ASSERT(node
!= root
,
388 "Only the last node should be root, since this was a post "
391 auto ptr
= predecessorSets
.lookup(node
);
393 "Because this isn't the root, it had better have "
394 "predecessors, or else how "
395 "did we even find it.");
397 auto& predecessors
= ptr
->value();
398 if (!predecessorVectors
[i
].reserve(predecessors
->count())) {
401 for (auto range
= predecessors
->all(); !range
.empty(); range
.popFront()) {
402 auto ptr
= nodeToPostOrderIndex
.lookup(range
.front());
404 predecessorVectors
[i
].infallibleAppend(ptr
->value());
407 predecessorSets
.clearAndCompact();
411 // Initialize `doms` such that the immediate dominator of the `root` is the
412 // `root` itself and all others are `UNDEFINED`.
413 [[nodiscard
]] static bool initializeDominators(
414 JS::ubi::Vector
<uint32_t>& doms
, uint32_t length
) {
415 MOZ_ASSERT(doms
.length() == 0);
416 if (!doms
.growByUninitialized(length
)) {
419 doms
[length
- 1] = length
- 1;
420 for (uint32_t i
= 0; i
< length
- 1; i
++) {
426 void assertSanity() const {
427 MOZ_ASSERT(postOrder
.length() == doms
.length());
428 MOZ_ASSERT(postOrder
.length() == nodeToPostOrderIndex
.count());
429 MOZ_ASSERT_IF(retainedSizes
.isSome(),
430 postOrder
.length() == retainedSizes
->length());
433 [[nodiscard
]] bool computeRetainedSizes(mozilla::MallocSizeOf mallocSizeOf
) {
434 MOZ_ASSERT(retainedSizes
.isNothing());
435 auto length
= postOrder
.length();
437 retainedSizes
.emplace();
438 if (!retainedSizes
->growBy(length
)) {
439 retainedSizes
= mozilla::Nothing();
443 // Iterate in forward order so that we know all of a node's children in
444 // the dominator tree have already had their retained size
445 // computed. Then we can simply say that the retained size of a node is
446 // its shallow size (JS::ubi::Node::size) plus the retained sizes of its
447 // immediate children in the tree.
449 for (uint32_t i
= 0; i
< length
; i
++) {
450 auto size
= postOrder
[i
].size(mallocSizeOf
);
452 for (const auto& dominated
: dominatedSets
.dominatedSet(postOrder
, i
)) {
453 // The root node dominates itself, but shouldn't contribute to
454 // its own retained size.
455 if (dominated
== postOrder
[length
- 1]) {
456 MOZ_ASSERT(i
== length
- 1);
460 auto ptr
= nodeToPostOrderIndex
.lookup(dominated
);
462 auto idxOfDominated
= ptr
->value();
463 MOZ_ASSERT(idxOfDominated
< i
);
464 size
+= retainedSizes
.ref()[idxOfDominated
];
467 retainedSizes
.ref()[i
] = size
;
474 // DominatorTree is not copy-able.
475 DominatorTree(const DominatorTree
&) = delete;
476 DominatorTree
& operator=(const DominatorTree
&) = delete;
478 // DominatorTree is move-able.
479 DominatorTree(DominatorTree
&& rhs
)
480 : postOrder(std::move(rhs
.postOrder
)),
481 nodeToPostOrderIndex(std::move(rhs
.nodeToPostOrderIndex
)),
482 doms(std::move(rhs
.doms
)),
483 dominatedSets(std::move(rhs
.dominatedSets
)),
484 retainedSizes(std::move(rhs
.retainedSizes
)) {
485 MOZ_ASSERT(this != &rhs
, "self-move is not allowed");
487 DominatorTree
& operator=(DominatorTree
&& rhs
) {
488 this->~DominatorTree();
489 new (this) DominatorTree(std::move(rhs
));
494 * Construct a `DominatorTree` of the heap graph visible from `root`. The
495 * `root` is also used as the root of the resulting dominator tree.
497 * The resulting `DominatorTree` instance must not outlive the
498 * `JS::ubi::Node` graph it was constructed from.
500 * - For `JS::ubi::Node` graphs backed by the live heap graph, this means
501 * that the `DominatorTree`'s lifetime _must_ be contained within the
502 * scope of the provided `AutoCheckCannotGC` reference because a GC will
503 * invalidate the nodes.
505 * - For `JS::ubi::Node` graphs backed by some other offline structure
506 * provided by the embedder, the resulting `DominatorTree`'s lifetime is
507 * bounded by that offline structure's lifetime.
509 * In practice, this means that within SpiderMonkey we must treat
510 * `DominatorTree` as if it were backed by the live heap graph and trust
511 * that embedders with knowledge of the graph's implementation will do the
514 * Returns `mozilla::Nothing()` on OOM failure. It is the caller's
515 * responsibility to handle and report the OOM.
517 static mozilla::Maybe
<DominatorTree
> Create(JSContext
* cx
,
518 AutoCheckCannotGC
& noGC
,
520 JS::ubi::Vector
<Node
> postOrder
;
521 PredecessorSets predecessorSets
;
522 if (!doTraversal(cx
, noGC
, root
, postOrder
, predecessorSets
)) {
523 return mozilla::Nothing();
526 MOZ_ASSERT(postOrder
.length() < UINT32_MAX
);
527 uint32_t length
= postOrder
.length();
528 MOZ_ASSERT(postOrder
[length
- 1] == root
);
530 // From here on out we wish to avoid hash table lookups, and we use
531 // indices into `postOrder` instead of actual nodes wherever
532 // possible. This greatly improves the performance of this
533 // implementation, but we have to pay a little bit of upfront cost to
534 // convert our data structures to play along first.
536 NodeToIndexMap
nodeToPostOrderIndex(postOrder
.length());
537 if (!mapNodesToTheirIndices(postOrder
, nodeToPostOrderIndex
)) {
538 return mozilla::Nothing();
541 JS::ubi::Vector
<JS::ubi::Vector
<uint32_t>> predecessorVectors
;
542 if (!convertPredecessorSetsToVectors(root
, postOrder
, predecessorSets
,
543 nodeToPostOrderIndex
,
545 return mozilla::Nothing();
547 JS::ubi::Vector
<uint32_t> doms
;
548 if (!initializeDominators(doms
, length
)) {
549 return mozilla::Nothing();
556 // Iterate over the non-root nodes in reverse post order.
557 for (uint32_t indexPlusOne
= length
- 1; indexPlusOne
> 0;
559 MOZ_ASSERT(postOrder
[indexPlusOne
- 1] != root
);
561 // Take the intersection of every predecessor's dominator set;
562 // that is the current best guess at the immediate dominator for
565 uint32_t newIDomIdx
= UNDEFINED
;
567 auto& predecessors
= predecessorVectors
[indexPlusOne
- 1];
568 auto range
= predecessors
.all();
569 for (; !range
.empty(); range
.popFront()) {
570 auto idx
= range
.front();
571 if (doms
[idx
] != UNDEFINED
) {
577 MOZ_ASSERT(newIDomIdx
!= UNDEFINED
,
578 "Because the root is initialized to dominate itself and is "
580 "node in every path, there must exist a predecessor to this "
582 "also has a dominator.");
584 for (; !range
.empty(); range
.popFront()) {
585 auto idx
= range
.front();
586 if (doms
[idx
] != UNDEFINED
) {
587 newIDomIdx
= intersect(doms
, newIDomIdx
, idx
);
591 // If the immediate dominator changed, we will have to do
592 // another pass of the outer while loop to continue the forward
594 if (newIDomIdx
!= doms
[indexPlusOne
- 1]) {
595 doms
[indexPlusOne
- 1] = newIDomIdx
;
601 auto maybeDominatedSets
= DominatedSets::Create(doms
);
602 if (maybeDominatedSets
.isNothing()) {
603 return mozilla::Nothing();
606 return mozilla::Some(
607 DominatorTree(std::move(postOrder
), std::move(nodeToPostOrderIndex
),
608 std::move(doms
), std::move(*maybeDominatedSets
)));
612 * Get the root node for this dominator tree.
614 const Node
& root() const { return postOrder
[postOrder
.length() - 1]; }
617 * Return the immediate dominator of the given `node`. If `node` was not
618 * reachable from the `root` that this dominator tree was constructed from,
619 * then return the null `JS::ubi::Node`.
621 Node
getImmediateDominator(const Node
& node
) const {
623 auto ptr
= nodeToPostOrderIndex
.lookup(node
);
628 auto idx
= ptr
->value();
629 MOZ_ASSERT(idx
< postOrder
.length());
630 return postOrder
[doms
[idx
]];
634 * Get the set of nodes immediately dominated by the given `node`. If `node`
635 * is not a member of this dominator tree, return `Nothing`.
639 * mozilla::Maybe<DominatedSetRange> range =
640 * myDominatorTree.getDominatedSet(myNode);
641 * if (range.isNothing()) {
642 * // Handle unknown node however you see fit...
646 * for (const JS::ubi::Node& dominatedNode : *range) {
647 * // Do something with each immediately dominated node...
650 mozilla::Maybe
<DominatedSetRange
> getDominatedSet(const Node
& node
) {
652 auto ptr
= nodeToPostOrderIndex
.lookup(node
);
654 return mozilla::Nothing();
657 auto idx
= ptr
->value();
658 MOZ_ASSERT(idx
< postOrder
.length());
659 return mozilla::Some(dominatedSets
.dominatedSet(postOrder
, idx
));
663 * Get the retained size of the given `node`. The size is placed in
664 * `outSize`, or 0 if `node` is not a member of the dominator tree. Returns
665 * false on OOM failure, leaving `outSize` unchanged.
667 [[nodiscard
]] bool getRetainedSize(const Node
& node
,
668 mozilla::MallocSizeOf mallocSizeOf
,
669 Node::Size
& outSize
) {
671 auto ptr
= nodeToPostOrderIndex
.lookup(node
);
677 if (retainedSizes
.isNothing() && !computeRetainedSizes(mallocSizeOf
)) {
681 auto idx
= ptr
->value();
682 MOZ_ASSERT(idx
< postOrder
.length());
683 outSize
= retainedSizes
.ref()[idx
];
691 #endif // js_UbiNodeDominatorTree_h