Source code
Revision control
Copy as Markdown
Other Tools
/* -*- 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
#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.
*
*/
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