Differential D3143 Diff 14286 ps/trunk/libraries/source/spidermonkey/include-win32-debug/js/UbiNodeDominatorTree.h
Changeset View
Changeset View
Standalone View
Standalone View
ps/trunk/libraries/source/spidermonkey/include-win32-debug/js/UbiNodeDominatorTree.h
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- | /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- | ||||
* vim: set ts=8 sts=4 et sw=4 tw=99: | * vim: set ts=8 sts=2 et sw=2 tw=80: | ||||
* This Source Code Form is subject to the terms of the Mozilla Public | * 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 | * 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/. */ | * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | ||||
#ifndef js_UbiNodeDominatorTree_h | #ifndef js_UbiNodeDominatorTree_h | ||||
#define js_UbiNodeDominatorTree_h | #define js_UbiNodeDominatorTree_h | ||||
#include "mozilla/Attributes.h" | #include "mozilla/Attributes.h" | ||||
▲ Show 20 Lines • Show All 142 Lines • ▼ Show 20 Lines | public: | ||||
* // Don't care about the first ten, for whatever reason. | * // Don't care about the first ten, for whatever reason. | ||||
* range->skip(10); | * range->skip(10); | ||||
* for (const JS::ubi::Node& dominatedNode : *range) { | * for (const JS::ubi::Node& dominatedNode : *range) { | ||||
* // ... | * // ... | ||||
* } | * } | ||||
*/ | */ | ||||
void skip(size_t n) { | void skip(size_t n) { | ||||
beginPtr += n; | beginPtr += n; | ||||
if (beginPtr > endPtr) beginPtr = endPtr; | if (beginPtr > endPtr) { | ||||
beginPtr = endPtr; | |||||
} | |||||
} | } | ||||
}; | }; | ||||
private: | private: | ||||
/** | /** | ||||
* The set of all dominated sets in a dominator tree. | * The set of all dominated sets in a dominator tree. | ||||
* | * | ||||
* Internally stores the sets in a contiguous array, with a side table of | * 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 | * indices into that contiguous array to denote the start index of each | ||||
* individual set. | * individual set. | ||||
*/ | */ | ||||
class DominatedSets { | class DominatedSets { | ||||
JS::ubi::Vector<uint32_t> dominated; | JS::ubi::Vector<uint32_t> dominated; | ||||
JS::ubi::Vector<uint32_t> indices; | JS::ubi::Vector<uint32_t> indices; | ||||
DominatedSets(JS::ubi::Vector<uint32_t>&& dominated, | DominatedSets(JS::ubi::Vector<uint32_t>&& dominated, | ||||
JS::ubi::Vector<uint32_t>&& indices) | JS::ubi::Vector<uint32_t>&& indices) | ||||
: dominated(mozilla::Move(dominated)), | : dominated(std::move(dominated)), indices(std::move(indices)) {} | ||||
indices(mozilla::Move(indices)) {} | |||||
public: | public: | ||||
// DominatedSets is not copy-able. | // DominatedSets is not copy-able. | ||||
DominatedSets(const DominatedSets& rhs) = delete; | DominatedSets(const DominatedSets& rhs) = delete; | ||||
DominatedSets& operator=(const DominatedSets& rhs) = delete; | DominatedSets& operator=(const DominatedSets& rhs) = delete; | ||||
// DominatedSets is move-able. | // DominatedSets is move-able. | ||||
DominatedSets(DominatedSets&& rhs) | DominatedSets(DominatedSets&& rhs) | ||||
: dominated(mozilla::Move(rhs.dominated)), | : dominated(std::move(rhs.dominated)), indices(std::move(rhs.indices)) { | ||||
indices(mozilla::Move(rhs.indices)) { | |||||
MOZ_ASSERT(this != &rhs, "self-move not allowed"); | MOZ_ASSERT(this != &rhs, "self-move not allowed"); | ||||
} | } | ||||
DominatedSets& operator=(DominatedSets&& rhs) { | DominatedSets& operator=(DominatedSets&& rhs) { | ||||
this->~DominatedSets(); | this->~DominatedSets(); | ||||
new (this) DominatedSets(mozilla::Move(rhs)); | new (this) DominatedSets(std::move(rhs)); | ||||
return *this; | return *this; | ||||
} | } | ||||
/** | /** | ||||
* Create the DominatedSets given the mapping of a node index to its | * Create the DominatedSets given the mapping of a node index to its | ||||
* immediate dominator. Returns `Some` on success, `Nothing` on OOM | * immediate dominator. Returns `Some` on success, `Nothing` on OOM | ||||
* failure. | * failure. | ||||
*/ | */ | ||||
Show All 20 Lines | static mozilla::Maybe<DominatedSets> Create( | ||||
// 3. Iterate over the full set of nodes again, filling in bucket | // 3. Iterate over the full set of nodes again, filling in bucket | ||||
// entries from the end of the bucket's range to its | // entries from the end of the bucket's range to its | ||||
// beginning. This decrements each index as a bucket entry is | // beginning. This decrements each index as a bucket entry is | ||||
// filled in. After having filled in all of a bucket's entries, | // filled in. After having filled in all of a bucket's entries, | ||||
// the index points to the start of the bucket. | // the index points to the start of the bucket. | ||||
JS::ubi::Vector<uint32_t> dominated; | JS::ubi::Vector<uint32_t> dominated; | ||||
JS::ubi::Vector<uint32_t> indices; | JS::ubi::Vector<uint32_t> indices; | ||||
if (!dominated.growBy(length) || !indices.growBy(length)) | if (!dominated.growBy(length) || !indices.growBy(length)) { | ||||
return mozilla::Nothing(); | return mozilla::Nothing(); | ||||
} | |||||
// 1 | // 1 | ||||
memset(indices.begin(), 0, length * sizeof(uint32_t)); | memset(indices.begin(), 0, length * sizeof(uint32_t)); | ||||
for (uint32_t i = 0; i < length; i++) indices[doms[i]]++; | for (uint32_t i = 0; i < length; i++) { | ||||
indices[doms[i]]++; | |||||
} | |||||
// 2 | // 2 | ||||
uint32_t sumOfSizes = 0; | uint32_t sumOfSizes = 0; | ||||
for (uint32_t i = 0; i < length; i++) { | for (uint32_t i = 0; i < length; i++) { | ||||
sumOfSizes += indices[i]; | sumOfSizes += indices[i]; | ||||
MOZ_ASSERT(sumOfSizes <= length); | MOZ_ASSERT(sumOfSizes <= length); | ||||
indices[i] = sumOfSizes; | indices[i] = sumOfSizes; | ||||
} | } | ||||
Show All 12 Lines | #ifdef DEBUG | ||||
for (uint32_t i = 0; i < length; i++) { | for (uint32_t i = 0; i < length; i++) { | ||||
MOZ_ASSERT(indices[i] >= lastIndex); | MOZ_ASSERT(indices[i] >= lastIndex); | ||||
MOZ_ASSERT(indices[i] < length); | MOZ_ASSERT(indices[i] < length); | ||||
lastIndex = indices[i]; | lastIndex = indices[i]; | ||||
} | } | ||||
#endif | #endif | ||||
return mozilla::Some( | return mozilla::Some( | ||||
DominatedSets(mozilla::Move(dominated), mozilla::Move(indices))); | DominatedSets(std::move(dominated), std::move(indices))); | ||||
} | } | ||||
/** | /** | ||||
* Get the set of nodes immediately dominated by the node at | * Get the set of nodes immediately dominated by the node at | ||||
* `postOrder[nodeIndex]`. | * `postOrder[nodeIndex]`. | ||||
*/ | */ | ||||
DominatedSetRange dominatedSet(JS::ubi::Vector<Node>& postOrder, | DominatedSetRange dominatedSet(JS::ubi::Vector<Node>& postOrder, | ||||
uint32_t nodeIndex) const { | uint32_t nodeIndex) const { | ||||
Show All 18 Lines | private: | ||||
// We use `UNDEFINED` as a sentinel value in the `doms` vector to signal | // 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 | // that we haven't found any dominators for the node at the corresponding | ||||
// index in `postOrder` yet. | // index in `postOrder` yet. | ||||
static const uint32_t UNDEFINED = UINT32_MAX; | static const uint32_t UNDEFINED = UINT32_MAX; | ||||
DominatorTree(JS::ubi::Vector<Node>&& postOrder, | DominatorTree(JS::ubi::Vector<Node>&& postOrder, | ||||
NodeToIndexMap&& nodeToPostOrderIndex, | NodeToIndexMap&& nodeToPostOrderIndex, | ||||
JS::ubi::Vector<uint32_t>&& doms, DominatedSets&& dominatedSets) | JS::ubi::Vector<uint32_t>&& doms, DominatedSets&& dominatedSets) | ||||
: postOrder(mozilla::Move(postOrder)), | : postOrder(std::move(postOrder)), | ||||
nodeToPostOrderIndex(mozilla::Move(nodeToPostOrderIndex)), | nodeToPostOrderIndex(std::move(nodeToPostOrderIndex)), | ||||
doms(mozilla::Move(doms)), | doms(std::move(doms)), | ||||
dominatedSets(mozilla::Move(dominatedSets)), | dominatedSets(std::move(dominatedSets)), | ||||
retainedSizes(mozilla::Nothing()) {} | retainedSizes(mozilla::Nothing()) {} | ||||
static uint32_t intersect(JS::ubi::Vector<uint32_t>& doms, uint32_t finger1, | static uint32_t intersect(JS::ubi::Vector<uint32_t>& doms, uint32_t finger1, | ||||
uint32_t finger2) { | uint32_t finger2) { | ||||
while (finger1 != finger2) { | while (finger1 != finger2) { | ||||
if (finger1 < finger2) | if (finger1 < finger2) { | ||||
finger1 = doms[finger1]; | finger1 = doms[finger1]; | ||||
else if (finger2 < finger1) | } else if (finger2 < finger1) { | ||||
finger2 = doms[finger2]; | finger2 = doms[finger2]; | ||||
} | } | ||||
} | |||||
return finger1; | return finger1; | ||||
} | } | ||||
// Do the post order traversal of the heap graph and populate our | // Do the post order traversal of the heap graph and populate our | ||||
// predecessor sets. | // predecessor sets. | ||||
static MOZ_MUST_USE bool doTraversal(JSContext* cx, AutoCheckCannotGC& noGC, | static MOZ_MUST_USE bool doTraversal(JSContext* cx, AutoCheckCannotGC& noGC, | ||||
const Node& root, | const Node& root, | ||||
JS::ubi::Vector<Node>& postOrder, | JS::ubi::Vector<Node>& postOrder, | ||||
PredecessorSets& predecessorSets) { | PredecessorSets& predecessorSets) { | ||||
uint32_t nodeCount = 0; | uint32_t nodeCount = 0; | ||||
auto onNode = [&](const Node& node) { | auto onNode = [&](const Node& node) { | ||||
nodeCount++; | nodeCount++; | ||||
if (MOZ_UNLIKELY(nodeCount == UINT32_MAX)) return false; | if (MOZ_UNLIKELY(nodeCount == UINT32_MAX)) { | ||||
return false; | |||||
} | |||||
return postOrder.append(node); | return postOrder.append(node); | ||||
}; | }; | ||||
auto onEdge = [&](const Node& origin, const Edge& edge) { | auto onEdge = [&](const Node& origin, const Edge& edge) { | ||||
auto p = predecessorSets.lookupForAdd(edge.referent); | auto p = predecessorSets.lookupForAdd(edge.referent); | ||||
if (!p) { | if (!p) { | ||||
mozilla::UniquePtr<NodeSet, DeletePolicy<NodeSet>> set( | mozilla::UniquePtr<NodeSet, DeletePolicy<NodeSet>> set( | ||||
js_new<NodeSet>()); | js_new<NodeSet>()); | ||||
if (!set || !set->init() || | if (!set || !predecessorSets.add(p, edge.referent, std::move(set))) { | ||||
!predecessorSets.add(p, edge.referent, mozilla::Move(set))) { | |||||
return false; | return false; | ||||
} | } | ||||
} | } | ||||
MOZ_ASSERT(p && p->value()); | MOZ_ASSERT(p && p->value()); | ||||
return p->value()->put(origin); | return p->value()->put(origin); | ||||
}; | }; | ||||
PostOrder traversal(cx, noGC); | PostOrder traversal(cx, noGC); | ||||
return traversal.init() && traversal.addStart(root) && | return traversal.addStart(root) && traversal.traverse(onNode, onEdge); | ||||
traversal.traverse(onNode, onEdge); | |||||
} | } | ||||
// Populates the given `map` with an entry for each node to its index in | // Populates the given `map` with an entry for each node to its index in | ||||
// `postOrder`. | // `postOrder`. | ||||
static MOZ_MUST_USE bool mapNodesToTheirIndices( | static MOZ_MUST_USE bool mapNodesToTheirIndices( | ||||
JS::ubi::Vector<Node>& postOrder, NodeToIndexMap& map) { | JS::ubi::Vector<Node>& postOrder, NodeToIndexMap& map) { | ||||
MOZ_ASSERT(!map.initialized()); | MOZ_ASSERT(map.empty()); | ||||
MOZ_ASSERT(postOrder.length() < UINT32_MAX); | MOZ_ASSERT(postOrder.length() < UINT32_MAX); | ||||
uint32_t length = postOrder.length(); | uint32_t length = postOrder.length(); | ||||
if (!map.init(length)) return false; | if (!map.reserve(length)) { | ||||
for (uint32_t i = 0; i < length; i++) map.putNewInfallible(postOrder[i], i); | return false; | ||||
} | |||||
for (uint32_t i = 0; i < length; i++) { | |||||
map.putNewInfallible(postOrder[i], i); | |||||
} | |||||
return true; | return true; | ||||
} | } | ||||
// Convert the Node -> NodeSet predecessorSets to a index -> Vector<index> | // Convert the Node -> NodeSet predecessorSets to a index -> Vector<index> | ||||
// form. | // form. | ||||
static MOZ_MUST_USE bool convertPredecessorSetsToVectors( | static MOZ_MUST_USE bool convertPredecessorSetsToVectors( | ||||
const Node& root, JS::ubi::Vector<Node>& postOrder, | const Node& root, JS::ubi::Vector<Node>& postOrder, | ||||
PredecessorSets& predecessorSets, NodeToIndexMap& nodeToPostOrderIndex, | PredecessorSets& predecessorSets, NodeToIndexMap& nodeToPostOrderIndex, | ||||
JS::ubi::Vector<JS::ubi::Vector<uint32_t>>& predecessorVectors) { | JS::ubi::Vector<JS::ubi::Vector<uint32_t>>& predecessorVectors) { | ||||
MOZ_ASSERT(postOrder.length() < UINT32_MAX); | MOZ_ASSERT(postOrder.length() < UINT32_MAX); | ||||
uint32_t length = postOrder.length(); | uint32_t length = postOrder.length(); | ||||
MOZ_ASSERT(predecessorVectors.length() == 0); | MOZ_ASSERT(predecessorVectors.length() == 0); | ||||
if (!predecessorVectors.growBy(length)) return false; | if (!predecessorVectors.growBy(length)) { | ||||
return false; | |||||
} | |||||
for (uint32_t i = 0; i < length - 1; i++) { | for (uint32_t i = 0; i < length - 1; i++) { | ||||
auto& node = postOrder[i]; | auto& node = postOrder[i]; | ||||
MOZ_ASSERT(node != root, | MOZ_ASSERT(node != root, | ||||
"Only the last node should be root, since this was a post " | "Only the last node should be root, since this was a post " | ||||
"order traversal."); | "order traversal."); | ||||
auto ptr = predecessorSets.lookup(node); | auto ptr = predecessorSets.lookup(node); | ||||
MOZ_ASSERT(ptr, | MOZ_ASSERT(ptr, | ||||
"Because this isn't the root, it had better have " | "Because this isn't the root, it had better have " | ||||
"predecessors, or else how " | "predecessors, or else how " | ||||
"did we even find it."); | "did we even find it."); | ||||
auto& predecessors = ptr->value(); | auto& predecessors = ptr->value(); | ||||
if (!predecessorVectors[i].reserve(predecessors->count())) return false; | if (!predecessorVectors[i].reserve(predecessors->count())) { | ||||
return false; | |||||
} | |||||
for (auto range = predecessors->all(); !range.empty(); range.popFront()) { | for (auto range = predecessors->all(); !range.empty(); range.popFront()) { | ||||
auto ptr = nodeToPostOrderIndex.lookup(range.front()); | auto ptr = nodeToPostOrderIndex.lookup(range.front()); | ||||
MOZ_ASSERT(ptr); | MOZ_ASSERT(ptr); | ||||
predecessorVectors[i].infallibleAppend(ptr->value()); | predecessorVectors[i].infallibleAppend(ptr->value()); | ||||
} | } | ||||
} | } | ||||
predecessorSets.finish(); | predecessorSets.clearAndCompact(); | ||||
return true; | return true; | ||||
} | } | ||||
// Initialize `doms` such that the immediate dominator of the `root` is the | // Initialize `doms` such that the immediate dominator of the `root` is the | ||||
// `root` itself and all others are `UNDEFINED`. | // `root` itself and all others are `UNDEFINED`. | ||||
static MOZ_MUST_USE bool initializeDominators(JS::ubi::Vector<uint32_t>& doms, | static MOZ_MUST_USE bool initializeDominators(JS::ubi::Vector<uint32_t>& doms, | ||||
uint32_t length) { | uint32_t length) { | ||||
MOZ_ASSERT(doms.length() == 0); | MOZ_ASSERT(doms.length() == 0); | ||||
if (!doms.growByUninitialized(length)) return false; | if (!doms.growByUninitialized(length)) { | ||||
return false; | |||||
} | |||||
doms[length - 1] = length - 1; | doms[length - 1] = length - 1; | ||||
for (uint32_t i = 0; i < length - 1; i++) doms[i] = UNDEFINED; | for (uint32_t i = 0; i < length - 1; i++) { | ||||
doms[i] = UNDEFINED; | |||||
} | |||||
return true; | return true; | ||||
} | } | ||||
void assertSanity() const { | void assertSanity() const { | ||||
MOZ_ASSERT(postOrder.length() == doms.length()); | MOZ_ASSERT(postOrder.length() == doms.length()); | ||||
MOZ_ASSERT(postOrder.length() == nodeToPostOrderIndex.count()); | MOZ_ASSERT(postOrder.length() == nodeToPostOrderIndex.count()); | ||||
MOZ_ASSERT_IF(retainedSizes.isSome(), | MOZ_ASSERT_IF(retainedSizes.isSome(), | ||||
postOrder.length() == retainedSizes->length()); | postOrder.length() == retainedSizes->length()); | ||||
▲ Show 20 Lines • Show All 41 Lines • ▼ Show 20 Lines | |||||
public: | public: | ||||
// DominatorTree is not copy-able. | // DominatorTree is not copy-able. | ||||
DominatorTree(const DominatorTree&) = delete; | DominatorTree(const DominatorTree&) = delete; | ||||
DominatorTree& operator=(const DominatorTree&) = delete; | DominatorTree& operator=(const DominatorTree&) = delete; | ||||
// DominatorTree is move-able. | // DominatorTree is move-able. | ||||
DominatorTree(DominatorTree&& rhs) | DominatorTree(DominatorTree&& rhs) | ||||
: postOrder(mozilla::Move(rhs.postOrder)), | : postOrder(std::move(rhs.postOrder)), | ||||
nodeToPostOrderIndex(mozilla::Move(rhs.nodeToPostOrderIndex)), | nodeToPostOrderIndex(std::move(rhs.nodeToPostOrderIndex)), | ||||
doms(mozilla::Move(rhs.doms)), | doms(std::move(rhs.doms)), | ||||
dominatedSets(mozilla::Move(rhs.dominatedSets)), | dominatedSets(std::move(rhs.dominatedSets)), | ||||
retainedSizes(mozilla::Move(rhs.retainedSizes)) { | retainedSizes(std::move(rhs.retainedSizes)) { | ||||
MOZ_ASSERT(this != &rhs, "self-move is not allowed"); | MOZ_ASSERT(this != &rhs, "self-move is not allowed"); | ||||
} | } | ||||
DominatorTree& operator=(DominatorTree&& rhs) { | DominatorTree& operator=(DominatorTree&& rhs) { | ||||
this->~DominatorTree(); | this->~DominatorTree(); | ||||
new (this) DominatorTree(mozilla::Move(rhs)); | new (this) DominatorTree(std::move(rhs)); | ||||
return *this; | return *this; | ||||
} | } | ||||
/** | /** | ||||
* Construct a `DominatorTree` of the heap graph visible from `root`. The | * Construct a `DominatorTree` of the heap graph visible from `root`. The | ||||
* `root` is also used as the root of the resulting dominator tree. | * `root` is also used as the root of the resulting dominator tree. | ||||
* | * | ||||
* The resulting `DominatorTree` instance must not outlive the | * The resulting `DominatorTree` instance must not outlive the | ||||
Show All 16 Lines | public: | ||||
* Returns `mozilla::Nothing()` on OOM failure. It is the caller's | * Returns `mozilla::Nothing()` on OOM failure. It is the caller's | ||||
* responsibility to handle and report the OOM. | * responsibility to handle and report the OOM. | ||||
*/ | */ | ||||
static mozilla::Maybe<DominatorTree> Create(JSContext* cx, | static mozilla::Maybe<DominatorTree> Create(JSContext* cx, | ||||
AutoCheckCannotGC& noGC, | AutoCheckCannotGC& noGC, | ||||
const Node& root) { | const Node& root) { | ||||
JS::ubi::Vector<Node> postOrder; | JS::ubi::Vector<Node> postOrder; | ||||
PredecessorSets predecessorSets; | PredecessorSets predecessorSets; | ||||
if (!predecessorSets.init() || | if (!doTraversal(cx, noGC, root, postOrder, predecessorSets)) { | ||||
!doTraversal(cx, noGC, root, postOrder, predecessorSets)) | |||||
return mozilla::Nothing(); | return mozilla::Nothing(); | ||||
} | |||||
MOZ_ASSERT(postOrder.length() < UINT32_MAX); | MOZ_ASSERT(postOrder.length() < UINT32_MAX); | ||||
uint32_t length = postOrder.length(); | uint32_t length = postOrder.length(); | ||||
MOZ_ASSERT(postOrder[length - 1] == root); | MOZ_ASSERT(postOrder[length - 1] == root); | ||||
// From here on out we wish to avoid hash table lookups, and we use | // From here on out we wish to avoid hash table lookups, and we use | ||||
// indices into `postOrder` instead of actual nodes wherever | // indices into `postOrder` instead of actual nodes wherever | ||||
// possible. This greatly improves the performance of this | // possible. This greatly improves the performance of this | ||||
// implementation, but we have to pay a little bit of upfront cost to | // implementation, but we have to pay a little bit of upfront cost to | ||||
// convert our data structures to play along first. | // convert our data structures to play along first. | ||||
NodeToIndexMap nodeToPostOrderIndex; | NodeToIndexMap nodeToPostOrderIndex(postOrder.length()); | ||||
if (!mapNodesToTheirIndices(postOrder, nodeToPostOrderIndex)) | if (!mapNodesToTheirIndices(postOrder, nodeToPostOrderIndex)) { | ||||
return mozilla::Nothing(); | return mozilla::Nothing(); | ||||
} | |||||
JS::ubi::Vector<JS::ubi::Vector<uint32_t>> predecessorVectors; | JS::ubi::Vector<JS::ubi::Vector<uint32_t>> predecessorVectors; | ||||
if (!convertPredecessorSetsToVectors(root, postOrder, predecessorSets, | if (!convertPredecessorSetsToVectors(root, postOrder, predecessorSets, | ||||
nodeToPostOrderIndex, | nodeToPostOrderIndex, | ||||
predecessorVectors)) | predecessorVectors)) | ||||
return mozilla::Nothing(); | return mozilla::Nothing(); | ||||
JS::ubi::Vector<uint32_t> doms; | JS::ubi::Vector<uint32_t> doms; | ||||
if (!initializeDominators(doms, length)) return mozilla::Nothing(); | if (!initializeDominators(doms, length)) { | ||||
return mozilla::Nothing(); | |||||
} | |||||
bool changed = true; | bool changed = true; | ||||
while (changed) { | while (changed) { | ||||
changed = false; | changed = false; | ||||
// Iterate over the non-root nodes in reverse post order. | // Iterate over the non-root nodes in reverse post order. | ||||
for (uint32_t indexPlusOne = length - 1; indexPlusOne > 0; | for (uint32_t indexPlusOne = length - 1; indexPlusOne > 0; | ||||
indexPlusOne--) { | indexPlusOne--) { | ||||
Show All 19 Lines | while (changed) { | ||||
"Because the root is initialized to dominate itself and is " | "Because the root is initialized to dominate itself and is " | ||||
"the first " | "the first " | ||||
"node in every path, there must exist a predecessor to this " | "node in every path, there must exist a predecessor to this " | ||||
"node that " | "node that " | ||||
"also has a dominator."); | "also has a dominator."); | ||||
for (; !range.empty(); range.popFront()) { | for (; !range.empty(); range.popFront()) { | ||||
auto idx = range.front(); | auto idx = range.front(); | ||||
if (doms[idx] != UNDEFINED) | if (doms[idx] != UNDEFINED) { | ||||
newIDomIdx = intersect(doms, newIDomIdx, idx); | newIDomIdx = intersect(doms, newIDomIdx, idx); | ||||
} | } | ||||
} | |||||
// If the immediate dominator changed, we will have to do | // If the immediate dominator changed, we will have to do | ||||
// another pass of the outer while loop to continue the forward | // another pass of the outer while loop to continue the forward | ||||
// dataflow. | // dataflow. | ||||
if (newIDomIdx != doms[indexPlusOne - 1]) { | if (newIDomIdx != doms[indexPlusOne - 1]) { | ||||
doms[indexPlusOne - 1] = newIDomIdx; | doms[indexPlusOne - 1] = newIDomIdx; | ||||
changed = true; | changed = true; | ||||
} | } | ||||
} | } | ||||
} | } | ||||
auto maybeDominatedSets = DominatedSets::Create(doms); | auto maybeDominatedSets = DominatedSets::Create(doms); | ||||
if (maybeDominatedSets.isNothing()) return mozilla::Nothing(); | if (maybeDominatedSets.isNothing()) { | ||||
return mozilla::Nothing(); | |||||
} | |||||
return mozilla::Some(DominatorTree( | return mozilla::Some( | ||||
mozilla::Move(postOrder), mozilla::Move(nodeToPostOrderIndex), | DominatorTree(std::move(postOrder), std::move(nodeToPostOrderIndex), | ||||
mozilla::Move(doms), mozilla::Move(*maybeDominatedSets))); | std::move(doms), std::move(*maybeDominatedSets))); | ||||
} | } | ||||
/** | /** | ||||
* Get the root node for this dominator tree. | * Get the root node for this dominator tree. | ||||
*/ | */ | ||||
const Node& root() const { return postOrder[postOrder.length() - 1]; } | const Node& root() const { return postOrder[postOrder.length() - 1]; } | ||||
/** | /** | ||||
* Return the immediate dominator of the given `node`. If `node` was not | * Return the immediate dominator of the given `node`. If `node` was not | ||||
* reachable from the `root` that this dominator tree was constructed from, | * reachable from the `root` that this dominator tree was constructed from, | ||||
* then return the null `JS::ubi::Node`. | * then return the null `JS::ubi::Node`. | ||||
*/ | */ | ||||
Node getImmediateDominator(const Node& node) const { | Node getImmediateDominator(const Node& node) const { | ||||
assertSanity(); | assertSanity(); | ||||
auto ptr = nodeToPostOrderIndex.lookup(node); | auto ptr = nodeToPostOrderIndex.lookup(node); | ||||
if (!ptr) return Node(); | if (!ptr) { | ||||
return Node(); | |||||
} | |||||
auto idx = ptr->value(); | auto idx = ptr->value(); | ||||
MOZ_ASSERT(idx < postOrder.length()); | MOZ_ASSERT(idx < postOrder.length()); | ||||
return postOrder[doms[idx]]; | return postOrder[doms[idx]]; | ||||
} | } | ||||
/** | /** | ||||
* Get the set of nodes immediately dominated by the given `node`. If `node` | * Get the set of nodes immediately dominated by the given `node`. If `node` | ||||
Show All 10 Lines | public: | ||||
* | * | ||||
* for (const JS::ubi::Node& dominatedNode : *range) { | * for (const JS::ubi::Node& dominatedNode : *range) { | ||||
* // Do something with each immediately dominated node... | * // Do something with each immediately dominated node... | ||||
* } | * } | ||||
*/ | */ | ||||
mozilla::Maybe<DominatedSetRange> getDominatedSet(const Node& node) { | mozilla::Maybe<DominatedSetRange> getDominatedSet(const Node& node) { | ||||
assertSanity(); | assertSanity(); | ||||
auto ptr = nodeToPostOrderIndex.lookup(node); | auto ptr = nodeToPostOrderIndex.lookup(node); | ||||
if (!ptr) return mozilla::Nothing(); | if (!ptr) { | ||||
return mozilla::Nothing(); | |||||
} | |||||
auto idx = ptr->value(); | auto idx = ptr->value(); | ||||
MOZ_ASSERT(idx < postOrder.length()); | MOZ_ASSERT(idx < postOrder.length()); | ||||
return mozilla::Some(dominatedSets.dominatedSet(postOrder, idx)); | return mozilla::Some(dominatedSets.dominatedSet(postOrder, idx)); | ||||
} | } | ||||
/** | /** | ||||
* Get the retained size of the given `node`. The size is placed in | * 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 | * `outSize`, or 0 if `node` is not a member of the dominator tree. Returns | ||||
* false on OOM failure, leaving `outSize` unchanged. | * false on OOM failure, leaving `outSize` unchanged. | ||||
*/ | */ | ||||
MOZ_MUST_USE bool getRetainedSize(const Node& node, | MOZ_MUST_USE bool getRetainedSize(const Node& node, | ||||
mozilla::MallocSizeOf mallocSizeOf, | mozilla::MallocSizeOf mallocSizeOf, | ||||
Node::Size& outSize) { | Node::Size& outSize) { | ||||
assertSanity(); | assertSanity(); | ||||
auto ptr = nodeToPostOrderIndex.lookup(node); | auto ptr = nodeToPostOrderIndex.lookup(node); | ||||
if (!ptr) { | if (!ptr) { | ||||
outSize = 0; | outSize = 0; | ||||
return true; | return true; | ||||
} | } | ||||
if (retainedSizes.isNothing() && !computeRetainedSizes(mallocSizeOf)) | if (retainedSizes.isNothing() && !computeRetainedSizes(mallocSizeOf)) { | ||||
return false; | return false; | ||||
} | |||||
auto idx = ptr->value(); | auto idx = ptr->value(); | ||||
MOZ_ASSERT(idx < postOrder.length()); | MOZ_ASSERT(idx < postOrder.length()); | ||||
outSize = retainedSizes.ref()[idx]; | outSize = retainedSizes.ref()[idx]; | ||||
return true; | return true; | ||||
} | } | ||||
}; | }; | ||||
} // namespace ubi | } // namespace ubi | ||||
} // namespace JS | } // namespace JS | ||||
#endif // js_UbiNodeDominatorTree_h | #endif // js_UbiNodeDominatorTree_h |
Wildfire Games · Phabricator