diff options
Diffstat (limited to 'js/public/UbiNodeDominatorTree.h')
| -rw-r--r-- | js/public/UbiNodeDominatorTree.h | 691 |
1 files changed, 691 insertions, 0 deletions
diff --git a/js/public/UbiNodeDominatorTree.h b/js/public/UbiNodeDominatorTree.h new file mode 100644 index 0000000000..7b534aa11c --- /dev/null +++ b/js/public/UbiNodeDominatorTree.h @@ -0,0 +1,691 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- + * vim: set ts=8 sts=2 et sw=2 tw=80: + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#ifndef js_UbiNodeDominatorTree_h +#define js_UbiNodeDominatorTree_h + +#include "mozilla/Attributes.h" +#include "mozilla/DebugOnly.h" +#include "mozilla/Maybe.h" +#include "mozilla/UniquePtr.h" + +#include <utility> + +#include "js/AllocPolicy.h" +#include "js/UbiNode.h" +#include "js/UbiNodePostOrder.h" +#include "js/Utility.h" +#include "js/Vector.h" + +namespace JS { +namespace ubi { + +/** + * In a directed graph with a root node `R`, a node `A` is said to "dominate" a + * node `B` iff every path from `R` to `B` contains `A`. A node `A` is said to + * be the "immediate dominator" of a node `B` iff it dominates `B`, is not `B` + * itself, and does not dominate any other nodes which also dominate `B` in + * turn. + * + * If we take every node from a graph `G` and create a new graph `T` with edges + * to each node from its immediate dominator, then `T` is a tree (each node has + * only one immediate dominator, or none if it is the root). This tree is called + * a "dominator tree". + * + * This class represents a dominator tree constructed from a `JS::ubi::Node` + * heap graph. The domination relationship and dominator trees are useful tools + * for analyzing heap graphs because they tell you: + * + * - Exactly what could be reclaimed by the GC if some node `A` became + * unreachable: those nodes which are dominated by `A`, + * + * - The "retained size" of a node in the heap graph, in contrast to its + * "shallow size". The "shallow size" is the space taken by a node itself, + * not counting anything it references. The "retained size" of a node is its + * shallow size plus the size of all the things that would be collected if + * the original node wasn't (directly or indirectly) referencing them. In + * other words, the retained size is the shallow size of a node plus the + * shallow sizes of every other node it dominates. For example, the root + * node in a binary tree might have a small shallow size that does not take + * up much space itself, but it dominates the rest of the binary tree and + * its retained size is therefore significant (assuming no external + * references into the tree). + * + * The simple, engineered algorithm presented in "A Simple, Fast Dominance + * Algorithm" by Cooper el al[0] is used to find dominators and construct the + * dominator tree. This algorithm runs in O(n^2) time, but is faster in practice + * than alternative algorithms with better theoretical running times, such as + * Lengauer-Tarjan which runs in O(e * log(n)). The big caveat to that statement + * is that Cooper et al found it is faster in practice *on control flow graphs* + * and I'm not convinced that this property also holds on *heap* graphs. That + * said, the implementation of this algorithm is *much* simpler than + * Lengauer-Tarjan and has been found to be fast enough at least for the time + * being. + * + * [0]: http://www.cs.rice.edu/~keith/EMBED/dom.pdf + */ +class JS_PUBLIC_API DominatorTree { + private: + // Types. + + using PredecessorSets = js::HashMap<Node, NodeSetPtr, js::DefaultHasher<Node>, + js::SystemAllocPolicy>; + using NodeToIndexMap = js::HashMap<Node, uint32_t, js::DefaultHasher<Node>, + js::SystemAllocPolicy>; + class DominatedSets; + + public: + class DominatedSetRange; + + /** + * A pointer to an immediately dominated node. + * + * Don't use this type directly; it is no safer than regular pointers. This + * is only for use indirectly with range-based for loops and + * `DominatedSetRange`. + * + * @see JS::ubi::DominatorTree::getDominatedSet + */ + class DominatedNodePtr { + friend class DominatedSetRange; + + const JS::ubi::Vector<Node>& postOrder; + const uint32_t* ptr; + + DominatedNodePtr(const JS::ubi::Vector<Node>& postOrder, + const uint32_t* ptr) + : postOrder(postOrder), ptr(ptr) {} + + public: + bool operator!=(const DominatedNodePtr& rhs) const { + return ptr != rhs.ptr; + } + void operator++() { ptr++; } + const Node& operator*() const { return postOrder[*ptr]; } + }; + + /** + * A range of immediately dominated `JS::ubi::Node`s for use with + * range-based for loops. + * + * @see JS::ubi::DominatorTree::getDominatedSet + */ + class DominatedSetRange { + friend class DominatedSets; + + const JS::ubi::Vector<Node>& postOrder; + const uint32_t* beginPtr; + const uint32_t* endPtr; + + DominatedSetRange(JS::ubi::Vector<Node>& postOrder, const uint32_t* begin, + const uint32_t* end) + : postOrder(postOrder), beginPtr(begin), endPtr(end) { + MOZ_ASSERT(begin <= end); + } + + public: + DominatedNodePtr begin() const { + MOZ_ASSERT(beginPtr <= endPtr); + return DominatedNodePtr(postOrder, beginPtr); + } + + DominatedNodePtr end() const { return DominatedNodePtr(postOrder, endPtr); } + + size_t length() const { + MOZ_ASSERT(beginPtr <= endPtr); + return endPtr - beginPtr; + } + + /** + * Safely skip ahead `n` dominators in the range, in O(1) time. + * + * Example usage: + * + * mozilla::Maybe<DominatedSetRange> range = + * myDominatorTree.getDominatedSet(myNode); + * if (range.isNothing()) { + * // Handle unknown nodes however you see fit... + * return false; + * } + * + * // Don't care about the first ten, for whatever reason. + * range->skip(10); + * for (const JS::ubi::Node& dominatedNode : *range) { + * // ... + * } + */ + void skip(size_t n) { + beginPtr += n; + if (beginPtr > endPtr) { + beginPtr = endPtr; + } + } + }; + + private: + /** + * The set of all dominated sets in a dominator tree. + * + * Internally stores the sets in a contiguous array, with a side table of + * indices into that contiguous array to denote the start index of each + * individual set. + */ + class DominatedSets { + JS::ubi::Vector<uint32_t> dominated; + JS::ubi::Vector<uint32_t> indices; + + DominatedSets(JS::ubi::Vector<uint32_t>&& dominated, + JS::ubi::Vector<uint32_t>&& indices) + : dominated(std::move(dominated)), indices(std::move(indices)) {} + + public: + // DominatedSets is not copy-able. + DominatedSets(const DominatedSets& rhs) = delete; + DominatedSets& operator=(const DominatedSets& rhs) = delete; + + // DominatedSets is move-able. + DominatedSets(DominatedSets&& rhs) + : dominated(std::move(rhs.dominated)), indices(std::move(rhs.indices)) { + MOZ_ASSERT(this != &rhs, "self-move not allowed"); + } + DominatedSets& operator=(DominatedSets&& rhs) { + this->~DominatedSets(); + new (this) DominatedSets(std::move(rhs)); + return *this; + } + + /** + * Create the DominatedSets given the mapping of a node index to its + * immediate dominator. Returns `Some` on success, `Nothing` on OOM + * failure. + */ + static mozilla::Maybe<DominatedSets> Create( + const JS::ubi::Vector<uint32_t>& doms) { + auto length = doms.length(); + MOZ_ASSERT(length < UINT32_MAX); + + // Create a vector `dominated` holding a flattened set of buckets of + // immediately dominated children nodes, with a lookup table + // `indices` mapping from each node to the beginning of its bucket. + // + // This has three phases: + // + // 1. Iterate over the full set of nodes and count up the size of + // each bucket. These bucket sizes are temporarily stored in the + // `indices` vector. + // + // 2. Convert the `indices` vector to store the cumulative sum of + // the sizes of all buckets before each index, resulting in a + // mapping from node index to one past the end of that node's + // bucket. + // + // 3. Iterate over the full set of nodes again, filling in bucket + // entries from the end of the bucket's range to its + // beginning. This decrements each index as a bucket entry is + // filled in. After having filled in all of a bucket's entries, + // the index points to the start of the bucket. + + JS::ubi::Vector<uint32_t> dominated; + JS::ubi::Vector<uint32_t> indices; + if (!dominated.growBy(length) || !indices.growBy(length)) { + return mozilla::Nothing(); + } + + // 1 + memset(indices.begin(), 0, length * sizeof(uint32_t)); + for (uint32_t i = 0; i < length; i++) { + indices[doms[i]]++; + } + + // 2 + uint32_t sumOfSizes = 0; + for (uint32_t i = 0; i < length; i++) { + sumOfSizes += indices[i]; + MOZ_ASSERT(sumOfSizes <= length); + indices[i] = sumOfSizes; + } + + // 3 + for (uint32_t i = 0; i < length; i++) { + auto idxOfDom = doms[i]; + indices[idxOfDom]--; + dominated[indices[idxOfDom]] = i; + } + +#ifdef DEBUG + // Assert that our buckets are non-overlapping and don't run off the + // end of the vector. + uint32_t lastIndex = 0; + for (uint32_t i = 0; i < length; i++) { + MOZ_ASSERT(indices[i] >= lastIndex); + MOZ_ASSERT(indices[i] < length); + lastIndex = indices[i]; + } +#endif + + return mozilla::Some( + DominatedSets(std::move(dominated), std::move(indices))); + } + + /** + * Get the set of nodes immediately dominated by the node at + * `postOrder[nodeIndex]`. + */ + DominatedSetRange dominatedSet(JS::ubi::Vector<Node>& postOrder, + uint32_t nodeIndex) const { + MOZ_ASSERT(postOrder.length() == indices.length()); + MOZ_ASSERT(nodeIndex < indices.length()); + auto end = nodeIndex == indices.length() - 1 + ? dominated.end() + : &dominated[indices[nodeIndex + 1]]; + return DominatedSetRange(postOrder, &dominated[indices[nodeIndex]], end); + } + }; + + private: + // Data members. + JS::ubi::Vector<Node> postOrder; + NodeToIndexMap nodeToPostOrderIndex; + JS::ubi::Vector<uint32_t> doms; + DominatedSets dominatedSets; + mozilla::Maybe<JS::ubi::Vector<JS::ubi::Node::Size>> retainedSizes; + + private: + // We use `UNDEFINED` as a sentinel value in the `doms` vector to signal + // that we haven't found any dominators for the node at the corresponding + // index in `postOrder` yet. + static const uint32_t UNDEFINED = UINT32_MAX; + + DominatorTree(JS::ubi::Vector<Node>&& postOrder, + NodeToIndexMap&& nodeToPostOrderIndex, + JS::ubi::Vector<uint32_t>&& doms, DominatedSets&& dominatedSets) + : postOrder(std::move(postOrder)), + nodeToPostOrderIndex(std::move(nodeToPostOrderIndex)), + doms(std::move(doms)), + dominatedSets(std::move(dominatedSets)), + retainedSizes(mozilla::Nothing()) {} + + static uint32_t intersect(JS::ubi::Vector<uint32_t>& doms, uint32_t finger1, + uint32_t finger2) { + while (finger1 != finger2) { + if (finger1 < finger2) { + finger1 = doms[finger1]; + } else if (finger2 < finger1) { + finger2 = doms[finger2]; + } + } + return finger1; + } + + // Do the post order traversal of the heap graph and populate our + // predecessor sets. + [[nodiscard]] static bool doTraversal(JSContext* cx, AutoCheckCannotGC& noGC, + const Node& root, + JS::ubi::Vector<Node>& postOrder, + PredecessorSets& predecessorSets) { + uint32_t nodeCount = 0; + auto onNode = [&](const Node& node) { + nodeCount++; + if (MOZ_UNLIKELY(nodeCount == UINT32_MAX)) { + return false; + } + return postOrder.append(node); + }; + + auto onEdge = [&](const Node& origin, const Edge& edge) { + auto p = predecessorSets.lookupForAdd(edge.referent); + if (!p) { + mozilla::UniquePtr<NodeSet, DeletePolicy<NodeSet>> set( + js_new<NodeSet>()); + if (!set || !predecessorSets.add(p, edge.referent, std::move(set))) { + return false; + } + } + MOZ_ASSERT(p && p->value()); + return p->value()->put(origin); + }; + + PostOrder traversal(cx, noGC); + return traversal.addStart(root) && traversal.traverse(onNode, onEdge); + } + + // Populates the given `map` with an entry for each node to its index in + // `postOrder`. + [[nodiscard]] static bool mapNodesToTheirIndices( + JS::ubi::Vector<Node>& postOrder, NodeToIndexMap& map) { + MOZ_ASSERT(map.empty()); + MOZ_ASSERT(postOrder.length() < UINT32_MAX); + uint32_t length = postOrder.length(); + if (!map.reserve(length)) { + return false; + } + for (uint32_t i = 0; i < length; i++) { + map.putNewInfallible(postOrder[i], i); + } + return true; + } + + // Convert the Node -> NodeSet predecessorSets to a index -> Vector<index> + // form. + [[nodiscard]] static bool convertPredecessorSetsToVectors( + const Node& root, JS::ubi::Vector<Node>& postOrder, + PredecessorSets& predecessorSets, NodeToIndexMap& nodeToPostOrderIndex, + JS::ubi::Vector<JS::ubi::Vector<uint32_t>>& predecessorVectors) { + MOZ_ASSERT(postOrder.length() < UINT32_MAX); + uint32_t length = postOrder.length(); + + MOZ_ASSERT(predecessorVectors.length() == 0); + if (!predecessorVectors.growBy(length)) { + return false; + } + + for (uint32_t i = 0; i < length - 1; i++) { + auto& node = postOrder[i]; + MOZ_ASSERT(node != root, + "Only the last node should be root, since this was a post " + "order traversal."); + + auto ptr = predecessorSets.lookup(node); + MOZ_ASSERT(ptr, + "Because this isn't the root, it had better have " + "predecessors, or else how " + "did we even find it."); + + auto& predecessors = ptr->value(); + if (!predecessorVectors[i].reserve(predecessors->count())) { + return false; + } + for (auto range = predecessors->all(); !range.empty(); range.popFront()) { + auto ptr = nodeToPostOrderIndex.lookup(range.front()); + MOZ_ASSERT(ptr); + predecessorVectors[i].infallibleAppend(ptr->value()); + } + } + predecessorSets.clearAndCompact(); + return true; + } + + // Initialize `doms` such that the immediate dominator of the `root` is the + // `root` itself and all others are `UNDEFINED`. + [[nodiscard]] static bool initializeDominators( + JS::ubi::Vector<uint32_t>& doms, uint32_t length) { + MOZ_ASSERT(doms.length() == 0); + if (!doms.growByUninitialized(length)) { + return false; + } + doms[length - 1] = length - 1; + for (uint32_t i = 0; i < length - 1; i++) { + doms[i] = UNDEFINED; + } + return true; + } + + void assertSanity() const { + MOZ_ASSERT(postOrder.length() == doms.length()); + MOZ_ASSERT(postOrder.length() == nodeToPostOrderIndex.count()); + MOZ_ASSERT_IF(retainedSizes.isSome(), + postOrder.length() == retainedSizes->length()); + } + + [[nodiscard]] bool computeRetainedSizes(mozilla::MallocSizeOf mallocSizeOf) { + MOZ_ASSERT(retainedSizes.isNothing()); + auto length = postOrder.length(); + + retainedSizes.emplace(); + if (!retainedSizes->growBy(length)) { + retainedSizes = mozilla::Nothing(); + return false; + } + + // Iterate in forward order so that we know all of a node's children in + // the dominator tree have already had their retained size + // computed. Then we can simply say that the retained size of a node is + // its shallow size (JS::ubi::Node::size) plus the retained sizes of its + // immediate children in the tree. + + for (uint32_t i = 0; i < length; i++) { + auto size = postOrder[i].size(mallocSizeOf); + + for (const auto& dominated : dominatedSets.dominatedSet(postOrder, i)) { + // The root node dominates itself, but shouldn't contribute to + // its own retained size. + if (dominated == postOrder[length - 1]) { + MOZ_ASSERT(i == length - 1); + continue; + } + + auto ptr = nodeToPostOrderIndex.lookup(dominated); + MOZ_ASSERT(ptr); + auto idxOfDominated = ptr->value(); + MOZ_ASSERT(idxOfDominated < i); + size += retainedSizes.ref()[idxOfDominated]; + } + + retainedSizes.ref()[i] = size; + } + + return true; + } + + public: + // DominatorTree is not copy-able. + DominatorTree(const DominatorTree&) = delete; + DominatorTree& operator=(const DominatorTree&) = delete; + + // DominatorTree is move-able. + DominatorTree(DominatorTree&& rhs) + : postOrder(std::move(rhs.postOrder)), + nodeToPostOrderIndex(std::move(rhs.nodeToPostOrderIndex)), + doms(std::move(rhs.doms)), + dominatedSets(std::move(rhs.dominatedSets)), + retainedSizes(std::move(rhs.retainedSizes)) { + MOZ_ASSERT(this != &rhs, "self-move is not allowed"); + } + DominatorTree& operator=(DominatorTree&& rhs) { + this->~DominatorTree(); + new (this) DominatorTree(std::move(rhs)); + return *this; + } + + /** + * Construct a `DominatorTree` of the heap graph visible from `root`. The + * `root` is also used as the root of the resulting dominator tree. + * + * The resulting `DominatorTree` instance must not outlive the + * `JS::ubi::Node` graph it was constructed from. + * + * - For `JS::ubi::Node` graphs backed by the live heap graph, this means + * that the `DominatorTree`'s lifetime _must_ be contained within the + * scope of the provided `AutoCheckCannotGC` reference because a GC will + * invalidate the nodes. + * + * - For `JS::ubi::Node` graphs backed by some other offline structure + * provided by the embedder, the resulting `DominatorTree`'s lifetime is + * bounded by that offline structure's lifetime. + * + * In practice, this means that within SpiderMonkey we must treat + * `DominatorTree` as if it were backed by the live heap graph and trust + * that embedders with knowledge of the graph's implementation will do the + * Right Thing. + * + * Returns `mozilla::Nothing()` on OOM failure. It is the caller's + * responsibility to handle and report the OOM. + */ + static mozilla::Maybe<DominatorTree> Create(JSContext* cx, + AutoCheckCannotGC& noGC, + const Node& root) { + JS::ubi::Vector<Node> postOrder; + PredecessorSets predecessorSets; + if (!doTraversal(cx, noGC, root, postOrder, predecessorSets)) { + return mozilla::Nothing(); + } + + MOZ_ASSERT(postOrder.length() < UINT32_MAX); + uint32_t length = postOrder.length(); + MOZ_ASSERT(postOrder[length - 1] == root); + + // From here on out we wish to avoid hash table lookups, and we use + // indices into `postOrder` instead of actual nodes wherever + // possible. This greatly improves the performance of this + // implementation, but we have to pay a little bit of upfront cost to + // convert our data structures to play along first. + + NodeToIndexMap nodeToPostOrderIndex(postOrder.length()); + if (!mapNodesToTheirIndices(postOrder, nodeToPostOrderIndex)) { + return mozilla::Nothing(); + } + + JS::ubi::Vector<JS::ubi::Vector<uint32_t>> predecessorVectors; + if (!convertPredecessorSetsToVectors(root, postOrder, predecessorSets, + nodeToPostOrderIndex, + predecessorVectors)) + return mozilla::Nothing(); + + JS::ubi::Vector<uint32_t> doms; + if (!initializeDominators(doms, length)) { + return mozilla::Nothing(); + } + + bool changed = true; + while (changed) { + changed = false; + + // Iterate over the non-root nodes in reverse post order. + for (uint32_t indexPlusOne = length - 1; indexPlusOne > 0; + indexPlusOne--) { + MOZ_ASSERT(postOrder[indexPlusOne - 1] != root); + + // Take the intersection of every predecessor's dominator set; + // that is the current best guess at the immediate dominator for + // this node. + + uint32_t newIDomIdx = UNDEFINED; + + auto& predecessors = predecessorVectors[indexPlusOne - 1]; + auto range = predecessors.all(); + for (; !range.empty(); range.popFront()) { + auto idx = range.front(); + if (doms[idx] != UNDEFINED) { + newIDomIdx = idx; + break; + } + } + + MOZ_ASSERT(newIDomIdx != UNDEFINED, + "Because the root is initialized to dominate itself and is " + "the first " + "node in every path, there must exist a predecessor to this " + "node that " + "also has a dominator."); + + for (; !range.empty(); range.popFront()) { + auto idx = range.front(); + if (doms[idx] != UNDEFINED) { + newIDomIdx = intersect(doms, newIDomIdx, idx); + } + } + + // If the immediate dominator changed, we will have to do + // another pass of the outer while loop to continue the forward + // dataflow. + if (newIDomIdx != doms[indexPlusOne - 1]) { + doms[indexPlusOne - 1] = newIDomIdx; + changed = true; + } + } + } + + auto maybeDominatedSets = DominatedSets::Create(doms); + if (maybeDominatedSets.isNothing()) { + return mozilla::Nothing(); + } + + return mozilla::Some( + DominatorTree(std::move(postOrder), std::move(nodeToPostOrderIndex), + std::move(doms), std::move(*maybeDominatedSets))); + } + + /** + * Get the root node for this dominator tree. + */ + const Node& root() const { return postOrder[postOrder.length() - 1]; } + + /** + * Return the immediate dominator of the given `node`. If `node` was not + * reachable from the `root` that this dominator tree was constructed from, + * then return the null `JS::ubi::Node`. + */ + Node getImmediateDominator(const Node& node) const { + assertSanity(); + auto ptr = nodeToPostOrderIndex.lookup(node); + if (!ptr) { + return Node(); + } + + auto idx = ptr->value(); + MOZ_ASSERT(idx < postOrder.length()); + return postOrder[doms[idx]]; + } + + /** + * Get the set of nodes immediately dominated by the given `node`. If `node` + * is not a member of this dominator tree, return `Nothing`. + * + * Example usage: + * + * mozilla::Maybe<DominatedSetRange> range = + * myDominatorTree.getDominatedSet(myNode); + * if (range.isNothing()) { + * // Handle unknown node however you see fit... + * return false; + * } + * + * for (const JS::ubi::Node& dominatedNode : *range) { + * // Do something with each immediately dominated node... + * } + */ + mozilla::Maybe<DominatedSetRange> getDominatedSet(const Node& node) { + assertSanity(); + auto ptr = nodeToPostOrderIndex.lookup(node); + if (!ptr) { + return mozilla::Nothing(); + } + + auto idx = ptr->value(); + MOZ_ASSERT(idx < postOrder.length()); + return mozilla::Some(dominatedSets.dominatedSet(postOrder, idx)); + } + + /** + * Get the retained size of the given `node`. The size is placed in + * `outSize`, or 0 if `node` is not a member of the dominator tree. Returns + * false on OOM failure, leaving `outSize` unchanged. + */ + [[nodiscard]] bool getRetainedSize(const Node& node, + mozilla::MallocSizeOf mallocSizeOf, + Node::Size& outSize) { + assertSanity(); + auto ptr = nodeToPostOrderIndex.lookup(node); + if (!ptr) { + outSize = 0; + return true; + } + + if (retainedSizes.isNothing() && !computeRetainedSizes(mallocSizeOf)) { + return false; + } + + auto idx = ptr->value(); + MOZ_ASSERT(idx < postOrder.length()); + outSize = retainedSizes.ref()[idx]; + return true; + } +}; + +} // namespace ubi +} // namespace JS + +#endif // js_UbiNodeDominatorTree_h |