Line data Source code
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/. */
6 :
7 : #ifndef js_UbiNodeDominatorTree_h
8 : #define js_UbiNodeDominatorTree_h
9 :
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"
15 :
16 : #include "jsalloc.h"
17 :
18 : #include "js/UbiNode.h"
19 : #include "js/UbiNodePostOrder.h"
20 : #include "js/Utility.h"
21 : #include "js/Vector.h"
22 :
23 : namespace JS {
24 : namespace ubi {
25 :
26 : /**
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
31 : * turn.
32 : *
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
36 : * a "dominator tree".
37 : *
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:
41 : *
42 : * - Exactly what could be reclaimed by the GC if some node `A` became
43 : * unreachable: those nodes which are dominated by `A`,
44 : *
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).
56 : *
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
66 : * being.
67 : *
68 : * [0]: http://www.cs.rice.edu/~keith/EMBED/dom.pdf
69 : */
70 0 : class JS_PUBLIC_API(DominatorTree)
71 : {
72 : private:
73 : // Types.
74 :
75 : using PredecessorSets = js::HashMap<Node, NodeSetPtr, js::DefaultHasher<Node>,
76 : js::SystemAllocPolicy>;
77 : using NodeToIndexMap = js::HashMap<Node, uint32_t, js::DefaultHasher<Node>,
78 : js::SystemAllocPolicy>;
79 : class DominatedSets;
80 :
81 : public:
82 : class DominatedSetRange;
83 :
84 : /**
85 : * A pointer to an immediately dominated node.
86 : *
87 : * Don't use this type directly; it is no safer than regular pointers. This
88 : * is only for use indirectly with range-based for loops and
89 : * `DominatedSetRange`.
90 : *
91 : * @see JS::ubi::DominatorTree::getDominatedSet
92 : */
93 : class DominatedNodePtr
94 : {
95 : friend class DominatedSetRange;
96 :
97 : const JS::ubi::Vector<Node>& postOrder;
98 : const uint32_t* ptr;
99 :
100 0 : DominatedNodePtr(const JS::ubi::Vector<Node>& postOrder, const uint32_t* ptr)
101 0 : : postOrder(postOrder)
102 0 : , ptr(ptr)
103 0 : { }
104 :
105 : public:
106 0 : bool operator!=(const DominatedNodePtr& rhs) const { return ptr != rhs.ptr; }
107 0 : void operator++() { ptr++; }
108 0 : const Node& operator*() const { return postOrder[*ptr]; }
109 : };
110 :
111 : /**
112 : * A range of immediately dominated `JS::ubi::Node`s for use with
113 : * range-based for loops.
114 : *
115 : * @see JS::ubi::DominatorTree::getDominatedSet
116 : */
117 : class DominatedSetRange
118 : {
119 : friend class DominatedSets;
120 :
121 : const JS::ubi::Vector<Node>& postOrder;
122 : const uint32_t* beginPtr;
123 : const uint32_t* endPtr;
124 :
125 0 : DominatedSetRange(JS::ubi::Vector<Node>& postOrder, const uint32_t* begin, const uint32_t* end)
126 0 : : postOrder(postOrder)
127 : , beginPtr(begin)
128 0 : , endPtr(end)
129 : {
130 0 : MOZ_ASSERT(begin <= end);
131 0 : }
132 :
133 : public:
134 0 : DominatedNodePtr begin() const {
135 0 : MOZ_ASSERT(beginPtr <= endPtr);
136 0 : return DominatedNodePtr(postOrder, beginPtr);
137 : }
138 :
139 0 : DominatedNodePtr end() const {
140 0 : return DominatedNodePtr(postOrder, endPtr);
141 : }
142 :
143 0 : size_t length() const {
144 0 : MOZ_ASSERT(beginPtr <= endPtr);
145 0 : return endPtr - beginPtr;
146 : }
147 :
148 : /**
149 : * Safely skip ahead `n` dominators in the range, in O(1) time.
150 : *
151 : * Example usage:
152 : *
153 : * mozilla::Maybe<DominatedSetRange> range = myDominatorTree.getDominatedSet(myNode);
154 : * if (range.isNothing()) {
155 : * // Handle unknown nodes however you see fit...
156 : * return false;
157 : * }
158 : *
159 : * // Don't care about the first ten, for whatever reason.
160 : * range->skip(10);
161 : * for (const JS::ubi::Node& dominatedNode : *range) {
162 : * // ...
163 : * }
164 : */
165 : void skip(size_t n) {
166 : beginPtr += n;
167 : if (beginPtr > endPtr)
168 : beginPtr = endPtr;
169 : }
170 : };
171 :
172 : private:
173 : /**
174 : * The set of all dominated sets in a dominator tree.
175 : *
176 : * Internally stores the sets in a contiguous array, with a side table of
177 : * indices into that contiguous array to denote the start index of each
178 : * individual set.
179 : */
180 0 : class DominatedSets
181 : {
182 : JS::ubi::Vector<uint32_t> dominated;
183 : JS::ubi::Vector<uint32_t> indices;
184 :
185 0 : DominatedSets(JS::ubi::Vector<uint32_t>&& dominated, JS::ubi::Vector<uint32_t>&& indices)
186 0 : : dominated(mozilla::Move(dominated))
187 0 : , indices(mozilla::Move(indices))
188 0 : { }
189 :
190 : public:
191 : // DominatedSets is not copy-able.
192 : DominatedSets(const DominatedSets& rhs) = delete;
193 : DominatedSets& operator=(const DominatedSets& rhs) = delete;
194 :
195 : // DominatedSets is move-able.
196 0 : DominatedSets(DominatedSets&& rhs)
197 0 : : dominated(mozilla::Move(rhs.dominated))
198 0 : , indices(mozilla::Move(rhs.indices))
199 : {
200 0 : MOZ_ASSERT(this != &rhs, "self-move not allowed");
201 0 : }
202 : DominatedSets& operator=(DominatedSets&& rhs) {
203 : this->~DominatedSets();
204 : new (this) DominatedSets(mozilla::Move(rhs));
205 : return *this;
206 : }
207 :
208 : /**
209 : * Create the DominatedSets given the mapping of a node index to its
210 : * immediate dominator. Returns `Some` on success, `Nothing` on OOM
211 : * failure.
212 : */
213 0 : static mozilla::Maybe<DominatedSets> Create(const JS::ubi::Vector<uint32_t>& doms) {
214 0 : auto length = doms.length();
215 0 : MOZ_ASSERT(length < UINT32_MAX);
216 :
217 : // Create a vector `dominated` holding a flattened set of buckets of
218 : // immediately dominated children nodes, with a lookup table
219 : // `indices` mapping from each node to the beginning of its bucket.
220 : //
221 : // This has three phases:
222 : //
223 : // 1. Iterate over the full set of nodes and count up the size of
224 : // each bucket. These bucket sizes are temporarily stored in the
225 : // `indices` vector.
226 : //
227 : // 2. Convert the `indices` vector to store the cumulative sum of
228 : // the sizes of all buckets before each index, resulting in a
229 : // mapping from node index to one past the end of that node's
230 : // bucket.
231 : //
232 : // 3. Iterate over the full set of nodes again, filling in bucket
233 : // entries from the end of the bucket's range to its
234 : // beginning. This decrements each index as a bucket entry is
235 : // filled in. After having filled in all of a bucket's entries,
236 : // the index points to the start of the bucket.
237 :
238 0 : JS::ubi::Vector<uint32_t> dominated;
239 0 : JS::ubi::Vector<uint32_t> indices;
240 0 : if (!dominated.growBy(length) || !indices.growBy(length))
241 0 : return mozilla::Nothing();
242 :
243 : // 1
244 0 : memset(indices.begin(), 0, length * sizeof(uint32_t));
245 0 : for (uint32_t i = 0; i < length; i++)
246 0 : indices[doms[i]]++;
247 :
248 : // 2
249 0 : uint32_t sumOfSizes = 0;
250 0 : for (uint32_t i = 0; i < length; i++) {
251 0 : sumOfSizes += indices[i];
252 0 : MOZ_ASSERT(sumOfSizes <= length);
253 0 : indices[i] = sumOfSizes;
254 : }
255 :
256 : // 3
257 0 : for (uint32_t i = 0; i < length; i++) {
258 0 : auto idxOfDom = doms[i];
259 0 : indices[idxOfDom]--;
260 0 : dominated[indices[idxOfDom]] = i;
261 : }
262 :
263 : #ifdef DEBUG
264 : // Assert that our buckets are non-overlapping and don't run off the
265 : // end of the vector.
266 0 : uint32_t lastIndex = 0;
267 0 : for (uint32_t i = 0; i < length; i++) {
268 0 : MOZ_ASSERT(indices[i] >= lastIndex);
269 0 : MOZ_ASSERT(indices[i] < length);
270 0 : lastIndex = indices[i];
271 : }
272 : #endif
273 :
274 0 : return mozilla::Some(DominatedSets(mozilla::Move(dominated), mozilla::Move(indices)));
275 : }
276 :
277 : /**
278 : * Get the set of nodes immediately dominated by the node at
279 : * `postOrder[nodeIndex]`.
280 : */
281 0 : DominatedSetRange dominatedSet(JS::ubi::Vector<Node>& postOrder, uint32_t nodeIndex) const {
282 0 : MOZ_ASSERT(postOrder.length() == indices.length());
283 0 : MOZ_ASSERT(nodeIndex < indices.length());
284 0 : auto end = nodeIndex == indices.length() - 1
285 0 : ? dominated.end()
286 0 : : &dominated[indices[nodeIndex + 1]];
287 0 : return DominatedSetRange(postOrder, &dominated[indices[nodeIndex]], end);
288 : }
289 : };
290 :
291 : private:
292 : // Data members.
293 : JS::ubi::Vector<Node> postOrder;
294 : NodeToIndexMap nodeToPostOrderIndex;
295 : JS::ubi::Vector<uint32_t> doms;
296 : DominatedSets dominatedSets;
297 : mozilla::Maybe<JS::ubi::Vector<JS::ubi::Node::Size>> retainedSizes;
298 :
299 : private:
300 : // We use `UNDEFINED` as a sentinel value in the `doms` vector to signal
301 : // that we haven't found any dominators for the node at the corresponding
302 : // index in `postOrder` yet.
303 : static const uint32_t UNDEFINED = UINT32_MAX;
304 :
305 0 : DominatorTree(JS::ubi::Vector<Node>&& postOrder, NodeToIndexMap&& nodeToPostOrderIndex,
306 : JS::ubi::Vector<uint32_t>&& doms, DominatedSets&& dominatedSets)
307 0 : : postOrder(mozilla::Move(postOrder))
308 0 : , nodeToPostOrderIndex(mozilla::Move(nodeToPostOrderIndex))
309 0 : , doms(mozilla::Move(doms))
310 0 : , dominatedSets(mozilla::Move(dominatedSets))
311 0 : , retainedSizes(mozilla::Nothing())
312 0 : { }
313 :
314 0 : static uint32_t intersect(JS::ubi::Vector<uint32_t>& doms, uint32_t finger1, uint32_t finger2) {
315 0 : while (finger1 != finger2) {
316 0 : if (finger1 < finger2)
317 0 : finger1 = doms[finger1];
318 0 : else if (finger2 < finger1)
319 0 : finger2 = doms[finger2];
320 : }
321 0 : return finger1;
322 : }
323 :
324 : // Do the post order traversal of the heap graph and populate our
325 : // predecessor sets.
326 0 : static MOZ_MUST_USE bool doTraversal(JSContext* cx, AutoCheckCannotGC& noGC, const Node& root,
327 : JS::ubi::Vector<Node>& postOrder,
328 : PredecessorSets& predecessorSets) {
329 0 : uint32_t nodeCount = 0;
330 0 : auto onNode = [&](const Node& node) {
331 0 : nodeCount++;
332 0 : if (MOZ_UNLIKELY(nodeCount == UINT32_MAX))
333 0 : return false;
334 0 : return postOrder.append(node);
335 0 : };
336 :
337 0 : auto onEdge = [&](const Node& origin, const Edge& edge) {
338 0 : auto p = predecessorSets.lookupForAdd(edge.referent);
339 0 : if (!p) {
340 0 : mozilla::UniquePtr<NodeSet, DeletePolicy<NodeSet>> set(js_new<NodeSet>());
341 0 : if (!set ||
342 0 : !set->init() ||
343 0 : !predecessorSets.add(p, edge.referent, mozilla::Move(set)))
344 : {
345 0 : return false;
346 : }
347 : }
348 0 : MOZ_ASSERT(p && p->value());
349 0 : return p->value()->put(origin);
350 0 : };
351 :
352 0 : PostOrder traversal(cx, noGC);
353 0 : return traversal.init() &&
354 0 : traversal.addStart(root) &&
355 0 : traversal.traverse(onNode, onEdge);
356 : }
357 :
358 : // Populates the given `map` with an entry for each node to its index in
359 : // `postOrder`.
360 0 : static MOZ_MUST_USE bool mapNodesToTheirIndices(JS::ubi::Vector<Node>& postOrder,
361 : NodeToIndexMap& map) {
362 0 : MOZ_ASSERT(!map.initialized());
363 0 : MOZ_ASSERT(postOrder.length() < UINT32_MAX);
364 0 : uint32_t length = postOrder.length();
365 0 : if (!map.init(length))
366 0 : return false;
367 0 : for (uint32_t i = 0; i < length; i++)
368 0 : map.putNewInfallible(postOrder[i], i);
369 0 : return true;
370 : }
371 :
372 : // Convert the Node -> NodeSet predecessorSets to a index -> Vector<index>
373 : // form.
374 0 : static MOZ_MUST_USE bool convertPredecessorSetsToVectors(
375 : const Node& root,
376 : JS::ubi::Vector<Node>& postOrder,
377 : PredecessorSets& predecessorSets,
378 : NodeToIndexMap& nodeToPostOrderIndex,
379 : JS::ubi::Vector<JS::ubi::Vector<uint32_t>>& predecessorVectors)
380 : {
381 0 : MOZ_ASSERT(postOrder.length() < UINT32_MAX);
382 0 : uint32_t length = postOrder.length();
383 :
384 0 : MOZ_ASSERT(predecessorVectors.length() == 0);
385 0 : if (!predecessorVectors.growBy(length))
386 0 : return false;
387 :
388 0 : for (uint32_t i = 0; i < length - 1; i++) {
389 0 : auto& node = postOrder[i];
390 0 : MOZ_ASSERT(node != root,
391 : "Only the last node should be root, since this was a post order traversal.");
392 :
393 0 : auto ptr = predecessorSets.lookup(node);
394 0 : MOZ_ASSERT(ptr,
395 : "Because this isn't the root, it had better have predecessors, or else how "
396 : "did we even find it.");
397 :
398 0 : auto& predecessors = ptr->value();
399 0 : if (!predecessorVectors[i].reserve(predecessors->count()))
400 0 : return false;
401 0 : for (auto range = predecessors->all(); !range.empty(); range.popFront()) {
402 0 : auto ptr = nodeToPostOrderIndex.lookup(range.front());
403 0 : MOZ_ASSERT(ptr);
404 0 : predecessorVectors[i].infallibleAppend(ptr->value());
405 : }
406 : }
407 0 : predecessorSets.finish();
408 0 : return true;
409 : }
410 :
411 : // Initialize `doms` such that the immediate dominator of the `root` is the
412 : // `root` itself and all others are `UNDEFINED`.
413 0 : static MOZ_MUST_USE bool initializeDominators(JS::ubi::Vector<uint32_t>& doms,
414 : uint32_t length) {
415 0 : MOZ_ASSERT(doms.length() == 0);
416 0 : if (!doms.growByUninitialized(length))
417 0 : return false;
418 0 : doms[length - 1] = length - 1;
419 0 : for (uint32_t i = 0; i < length - 1; i++)
420 0 : doms[i] = UNDEFINED;
421 0 : return true;
422 : }
423 :
424 0 : void assertSanity() const {
425 0 : MOZ_ASSERT(postOrder.length() == doms.length());
426 0 : MOZ_ASSERT(postOrder.length() == nodeToPostOrderIndex.count());
427 0 : MOZ_ASSERT_IF(retainedSizes.isSome(), postOrder.length() == retainedSizes->length());
428 0 : }
429 :
430 0 : MOZ_MUST_USE bool computeRetainedSizes(mozilla::MallocSizeOf mallocSizeOf) {
431 0 : MOZ_ASSERT(retainedSizes.isNothing());
432 0 : auto length = postOrder.length();
433 :
434 0 : retainedSizes.emplace();
435 0 : if (!retainedSizes->growBy(length)) {
436 0 : retainedSizes = mozilla::Nothing();
437 0 : return false;
438 : }
439 :
440 : // Iterate in forward order so that we know all of a node's children in
441 : // the dominator tree have already had their retained size
442 : // computed. Then we can simply say that the retained size of a node is
443 : // its shallow size (JS::ubi::Node::size) plus the retained sizes of its
444 : // immediate children in the tree.
445 :
446 0 : for (uint32_t i = 0; i < length; i++) {
447 0 : auto size = postOrder[i].size(mallocSizeOf);
448 :
449 0 : for (const auto& dominated : dominatedSets.dominatedSet(postOrder, i)) {
450 : // The root node dominates itself, but shouldn't contribute to
451 : // its own retained size.
452 0 : if (dominated == postOrder[length - 1]) {
453 0 : MOZ_ASSERT(i == length - 1);
454 0 : continue;
455 : }
456 :
457 0 : auto ptr = nodeToPostOrderIndex.lookup(dominated);
458 0 : MOZ_ASSERT(ptr);
459 0 : auto idxOfDominated = ptr->value();
460 0 : MOZ_ASSERT(idxOfDominated < i);
461 0 : size += retainedSizes.ref()[idxOfDominated];
462 : }
463 :
464 0 : retainedSizes.ref()[i] = size;
465 : }
466 :
467 0 : return true;
468 : }
469 :
470 : public:
471 : // DominatorTree is not copy-able.
472 : DominatorTree(const DominatorTree&) = delete;
473 : DominatorTree& operator=(const DominatorTree&) = delete;
474 :
475 : // DominatorTree is move-able.
476 0 : DominatorTree(DominatorTree&& rhs)
477 0 : : postOrder(mozilla::Move(rhs.postOrder))
478 0 : , nodeToPostOrderIndex(mozilla::Move(rhs.nodeToPostOrderIndex))
479 0 : , doms(mozilla::Move(rhs.doms))
480 0 : , dominatedSets(mozilla::Move(rhs.dominatedSets))
481 0 : , retainedSizes(mozilla::Move(rhs.retainedSizes))
482 : {
483 0 : MOZ_ASSERT(this != &rhs, "self-move is not allowed");
484 0 : }
485 0 : DominatorTree& operator=(DominatorTree&& rhs) {
486 0 : this->~DominatorTree();
487 0 : new (this) DominatorTree(mozilla::Move(rhs));
488 0 : return *this;
489 : }
490 :
491 : /**
492 : * Construct a `DominatorTree` of the heap graph visible from `root`. The
493 : * `root` is also used as the root of the resulting dominator tree.
494 : *
495 : * The resulting `DominatorTree` instance must not outlive the
496 : * `JS::ubi::Node` graph it was constructed from.
497 : *
498 : * - For `JS::ubi::Node` graphs backed by the live heap graph, this means
499 : * that the `DominatorTree`'s lifetime _must_ be contained within the
500 : * scope of the provided `AutoCheckCannotGC` reference because a GC will
501 : * invalidate the nodes.
502 : *
503 : * - For `JS::ubi::Node` graphs backed by some other offline structure
504 : * provided by the embedder, the resulting `DominatorTree`'s lifetime is
505 : * bounded by that offline structure's lifetime.
506 : *
507 : * In practice, this means that within SpiderMonkey we must treat
508 : * `DominatorTree` as if it were backed by the live heap graph and trust
509 : * that embedders with knowledge of the graph's implementation will do the
510 : * Right Thing.
511 : *
512 : * Returns `mozilla::Nothing()` on OOM failure. It is the caller's
513 : * responsibility to handle and report the OOM.
514 : */
515 : static mozilla::Maybe<DominatorTree>
516 0 : Create(JSContext* cx, AutoCheckCannotGC& noGC, const Node& root) {
517 0 : JS::ubi::Vector<Node> postOrder;
518 0 : PredecessorSets predecessorSets;
519 0 : if (!predecessorSets.init() || !doTraversal(cx, noGC, root, postOrder, predecessorSets))
520 0 : return mozilla::Nothing();
521 :
522 0 : MOZ_ASSERT(postOrder.length() < UINT32_MAX);
523 0 : uint32_t length = postOrder.length();
524 0 : MOZ_ASSERT(postOrder[length - 1] == root);
525 :
526 : // From here on out we wish to avoid hash table lookups, and we use
527 : // indices into `postOrder` instead of actual nodes wherever
528 : // possible. This greatly improves the performance of this
529 : // implementation, but we have to pay a little bit of upfront cost to
530 : // convert our data structures to play along first.
531 :
532 0 : NodeToIndexMap nodeToPostOrderIndex;
533 0 : if (!mapNodesToTheirIndices(postOrder, nodeToPostOrderIndex))
534 0 : return mozilla::Nothing();
535 :
536 0 : JS::ubi::Vector<JS::ubi::Vector<uint32_t>> predecessorVectors;
537 0 : if (!convertPredecessorSetsToVectors(root, postOrder, predecessorSets, nodeToPostOrderIndex,
538 : predecessorVectors))
539 0 : return mozilla::Nothing();
540 :
541 0 : JS::ubi::Vector<uint32_t> doms;
542 0 : if (!initializeDominators(doms, length))
543 0 : return mozilla::Nothing();
544 :
545 0 : bool changed = true;
546 0 : while (changed) {
547 0 : changed = false;
548 :
549 : // Iterate over the non-root nodes in reverse post order.
550 0 : for (uint32_t indexPlusOne = length - 1; indexPlusOne > 0; indexPlusOne--) {
551 0 : MOZ_ASSERT(postOrder[indexPlusOne - 1] != root);
552 :
553 : // Take the intersection of every predecessor's dominator set;
554 : // that is the current best guess at the immediate dominator for
555 : // this node.
556 :
557 0 : uint32_t newIDomIdx = UNDEFINED;
558 :
559 0 : auto& predecessors = predecessorVectors[indexPlusOne - 1];
560 0 : auto range = predecessors.all();
561 0 : for ( ; !range.empty(); range.popFront()) {
562 0 : auto idx = range.front();
563 0 : if (doms[idx] != UNDEFINED) {
564 0 : newIDomIdx = idx;
565 0 : break;
566 : }
567 : }
568 :
569 0 : MOZ_ASSERT(newIDomIdx != UNDEFINED,
570 : "Because the root is initialized to dominate itself and is the first "
571 : "node in every path, there must exist a predecessor to this node that "
572 : "also has a dominator.");
573 :
574 0 : for ( ; !range.empty(); range.popFront()) {
575 0 : auto idx = range.front();
576 0 : if (doms[idx] != UNDEFINED)
577 0 : newIDomIdx = intersect(doms, newIDomIdx, idx);
578 : }
579 :
580 : // If the immediate dominator changed, we will have to do
581 : // another pass of the outer while loop to continue the forward
582 : // dataflow.
583 0 : if (newIDomIdx != doms[indexPlusOne - 1]) {
584 0 : doms[indexPlusOne - 1] = newIDomIdx;
585 0 : changed = true;
586 : }
587 : }
588 : }
589 :
590 0 : auto maybeDominatedSets = DominatedSets::Create(doms);
591 0 : if (maybeDominatedSets.isNothing())
592 0 : return mozilla::Nothing();
593 :
594 0 : return mozilla::Some(DominatorTree(mozilla::Move(postOrder),
595 0 : mozilla::Move(nodeToPostOrderIndex),
596 0 : mozilla::Move(doms),
597 0 : mozilla::Move(*maybeDominatedSets)));
598 : }
599 :
600 : /**
601 : * Get the root node for this dominator tree.
602 : */
603 0 : const Node& root() const {
604 0 : return postOrder[postOrder.length() - 1];
605 : }
606 :
607 : /**
608 : * Return the immediate dominator of the given `node`. If `node` was not
609 : * reachable from the `root` that this dominator tree was constructed from,
610 : * then return the null `JS::ubi::Node`.
611 : */
612 0 : Node getImmediateDominator(const Node& node) const {
613 0 : assertSanity();
614 0 : auto ptr = nodeToPostOrderIndex.lookup(node);
615 0 : if (!ptr)
616 0 : return Node();
617 :
618 0 : auto idx = ptr->value();
619 0 : MOZ_ASSERT(idx < postOrder.length());
620 0 : return postOrder[doms[idx]];
621 : }
622 :
623 : /**
624 : * Get the set of nodes immediately dominated by the given `node`. If `node`
625 : * is not a member of this dominator tree, return `Nothing`.
626 : *
627 : * Example usage:
628 : *
629 : * mozilla::Maybe<DominatedSetRange> range = myDominatorTree.getDominatedSet(myNode);
630 : * if (range.isNothing()) {
631 : * // Handle unknown node however you see fit...
632 : * return false;
633 : * }
634 : *
635 : * for (const JS::ubi::Node& dominatedNode : *range) {
636 : * // Do something with each immediately dominated node...
637 : * }
638 : */
639 0 : mozilla::Maybe<DominatedSetRange> getDominatedSet(const Node& node) {
640 0 : assertSanity();
641 0 : auto ptr = nodeToPostOrderIndex.lookup(node);
642 0 : if (!ptr)
643 0 : return mozilla::Nothing();
644 :
645 0 : auto idx = ptr->value();
646 0 : MOZ_ASSERT(idx < postOrder.length());
647 0 : return mozilla::Some(dominatedSets.dominatedSet(postOrder, idx));
648 : }
649 :
650 : /**
651 : * Get the retained size of the given `node`. The size is placed in
652 : * `outSize`, or 0 if `node` is not a member of the dominator tree. Returns
653 : * false on OOM failure, leaving `outSize` unchanged.
654 : */
655 0 : MOZ_MUST_USE bool getRetainedSize(const Node& node, mozilla::MallocSizeOf mallocSizeOf,
656 : Node::Size& outSize) {
657 0 : assertSanity();
658 0 : auto ptr = nodeToPostOrderIndex.lookup(node);
659 0 : if (!ptr) {
660 0 : outSize = 0;
661 0 : return true;
662 : }
663 :
664 0 : if (retainedSizes.isNothing() && !computeRetainedSizes(mallocSizeOf))
665 0 : return false;
666 :
667 0 : auto idx = ptr->value();
668 0 : MOZ_ASSERT(idx < postOrder.length());
669 0 : outSize = retainedSizes.ref()[idx];
670 0 : return true;
671 : }
672 : };
673 :
674 : } // namespace ubi
675 : } // namespace JS
676 :
677 : #endif // js_UbiNodeDominatorTree_h
|
