Reviewers: Michael Starzinger,
Description:
Fix O(n^2) successor traversal in ControlReducer.
[email protected]
BUG=
Please review this at https://codereview.chromium.org/703163002/
Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Affected files (+15, -7 lines):
M src/compiler/control-reducer.cc
Index: src/compiler/control-reducer.cc
diff --git a/src/compiler/control-reducer.cc
b/src/compiler/control-reducer.cc
index
89b05d0c079c735cca34c10c9ceb5f4b09b911b2..1d8310316e7219bdc518fd465c9eab43052b7b43
100644
--- a/src/compiler/control-reducer.cc
+++ b/src/compiler/control-reducer.cc
@@ -80,33 +80,41 @@ class ControlReducerImpl {
Node* start = graph()->start();
ZoneVector<byte> fw_reachability(graph()->NodeCount(), 0, zone_);
fw_reachability[start->id()] = kFromStart | kOnStack;
- stack_.push_back(start);
- while (!stack_.empty()) {
- Node* node = stack_.back();
+ // We use a stack of (Node, UseIter) pairs to avoid O(n^2) traversal.
+ typedef std::pair<Node*, UseIter> FwIter;
+ ZoneDeque<FwIter> fw_stack(zone_);
+ fw_stack.push_back(FwIter(start, start->uses().begin()));
+
+ while (!fw_stack.empty()) {
+ Node* node = fw_stack.back().first;
TRACE(("ControlFw: #%d:%s\n", node->id(), node->op()->mnemonic()));
bool pop = true;
- for (Node* const succ : node->uses()) {
+ while (fw_stack.back().second != node->uses().end()) {
+ Node* succ = *(fw_stack.back().second);
byte reach = fw_reachability[succ->id()];
if ((reach & kOnStack) != 0 && state_[succ->id()] != kVisited) {
// {succ} is on stack and not reachable from end.
ConnectNTL(nodes, succ);
fw_reachability.resize(graph()->NodeCount(), 0);
- pop = false; // continue traversing inputs to this node.
+ // The use list of {succ} might have changed.
+ fw_stack[fw_stack.size() - 1] = FwIter(succ,
succ->uses().begin());
+ pop = false; // restart traversing successors of this node.
break;
}
if ((reach & kFromStart) == 0 &&
IrOpcode::IsControlOpcode(succ->opcode())) {
// {succ} is a control node and not yet reached from start.
fw_reachability[succ->id()] |= kFromStart | kOnStack;
- stack_.push_back(succ);
+ fw_stack.push_back(FwIter(succ, succ->uses().begin()));
pop = false; // "recurse" into successor control node.
break;
}
+ ++fw_stack.back().second;
}
if (pop) {
fw_reachability[node->id()] &= ~kOnStack;
- stack_.pop_back();
+ fw_stack.pop_back();
}
}
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
