Upgrade V8 to version 4.9.385.28
https://chromium.googlesource.com/v8/v8/+/4.9.385.28
FPIIM-449
Change-Id: I4b2e74289d4bf3667f2f3dc8aa2e541f63e26eb4
diff --git a/src/compiler/control-equivalence.cc b/src/compiler/control-equivalence.cc
new file mode 100644
index 0000000..af1a115
--- /dev/null
+++ b/src/compiler/control-equivalence.cc
@@ -0,0 +1,237 @@
+// Copyright 2015 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "src/compiler/control-equivalence.h"
+#include "src/compiler/node-properties.h"
+
+#define TRACE(...) \
+ do { \
+ if (FLAG_trace_turbo_ceq) PrintF(__VA_ARGS__); \
+ } while (false)
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+void ControlEquivalence::Run(Node* exit) {
+ if (GetClass(exit) == kInvalidClass) {
+ DetermineParticipation(exit);
+ RunUndirectedDFS(exit);
+ }
+}
+
+
+// static
+STATIC_CONST_MEMBER_DEFINITION const size_t ControlEquivalence::kInvalidClass;
+
+
+void ControlEquivalence::VisitPre(Node* node) {
+ TRACE("CEQ: Pre-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
+
+ // Dispense a new pre-order number.
+ SetNumber(node, NewDFSNumber());
+ TRACE(" Assigned DFS number is %zu\n", GetNumber(node));
+}
+
+
+void ControlEquivalence::VisitMid(Node* node, DFSDirection direction) {
+ TRACE("CEQ: Mid-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
+ BracketList& blist = GetBracketList(node);
+
+ // Remove brackets pointing to this node [line:19].
+ BracketListDelete(blist, node, direction);
+
+ // Potentially introduce artificial dependency from start to end.
+ if (blist.empty()) {
+ DCHECK_EQ(kInputDirection, direction);
+ VisitBackedge(node, graph_->end(), kInputDirection);
+ }
+
+ // Potentially start a new equivalence class [line:37].
+ BracketListTRACE(blist);
+ Bracket* recent = &blist.back();
+ if (recent->recent_size != blist.size()) {
+ recent->recent_size = blist.size();
+ recent->recent_class = NewClassNumber();
+ }
+
+ // Assign equivalence class to node.
+ SetClass(node, recent->recent_class);
+ TRACE(" Assigned class number is %zu\n", GetClass(node));
+}
+
+
+void ControlEquivalence::VisitPost(Node* node, Node* parent_node,
+ DFSDirection direction) {
+ TRACE("CEQ: Post-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
+ BracketList& blist = GetBracketList(node);
+
+ // Remove brackets pointing to this node [line:19].
+ BracketListDelete(blist, node, direction);
+
+ // Propagate bracket list up the DFS tree [line:13].
+ if (parent_node != nullptr) {
+ BracketList& parent_blist = GetBracketList(parent_node);
+ parent_blist.splice(parent_blist.end(), blist);
+ }
+}
+
+
+void ControlEquivalence::VisitBackedge(Node* from, Node* to,
+ DFSDirection direction) {
+ TRACE("CEQ: Backedge from #%d:%s to #%d:%s\n", from->id(),
+ from->op()->mnemonic(), to->id(), to->op()->mnemonic());
+
+ // Push backedge onto the bracket list [line:25].
+ Bracket bracket = {direction, kInvalidClass, 0, from, to};
+ GetBracketList(from).push_back(bracket);
+}
+
+
+void ControlEquivalence::RunUndirectedDFS(Node* exit) {
+ ZoneStack<DFSStackEntry> stack(zone_);
+ DFSPush(stack, exit, nullptr, kInputDirection);
+ VisitPre(exit);
+
+ while (!stack.empty()) { // Undirected depth-first backwards traversal.
+ DFSStackEntry& entry = stack.top();
+ Node* node = entry.node;
+
+ if (entry.direction == kInputDirection) {
+ if (entry.input != node->input_edges().end()) {
+ Edge edge = *entry.input;
+ Node* input = edge.to();
+ ++(entry.input);
+ if (NodeProperties::IsControlEdge(edge)) {
+ // Visit next control input.
+ if (!GetData(input)->participates) continue;
+ if (GetData(input)->visited) continue;
+ if (GetData(input)->on_stack) {
+ // Found backedge if input is on stack.
+ if (input != entry.parent_node) {
+ VisitBackedge(node, input, kInputDirection);
+ }
+ } else {
+ // Push input onto stack.
+ DFSPush(stack, input, node, kInputDirection);
+ VisitPre(input);
+ }
+ }
+ continue;
+ }
+ if (entry.use != node->use_edges().end()) {
+ // Switch direction to uses.
+ entry.direction = kUseDirection;
+ VisitMid(node, kInputDirection);
+ continue;
+ }
+ }
+
+ if (entry.direction == kUseDirection) {
+ if (entry.use != node->use_edges().end()) {
+ Edge edge = *entry.use;
+ Node* use = edge.from();
+ ++(entry.use);
+ if (NodeProperties::IsControlEdge(edge)) {
+ // Visit next control use.
+ if (!GetData(use)->participates) continue;
+ if (GetData(use)->visited) continue;
+ if (GetData(use)->on_stack) {
+ // Found backedge if use is on stack.
+ if (use != entry.parent_node) {
+ VisitBackedge(node, use, kUseDirection);
+ }
+ } else {
+ // Push use onto stack.
+ DFSPush(stack, use, node, kUseDirection);
+ VisitPre(use);
+ }
+ }
+ continue;
+ }
+ if (entry.input != node->input_edges().end()) {
+ // Switch direction to inputs.
+ entry.direction = kInputDirection;
+ VisitMid(node, kUseDirection);
+ continue;
+ }
+ }
+
+ // Pop node from stack when done with all inputs and uses.
+ DCHECK(entry.input == node->input_edges().end());
+ DCHECK(entry.use == node->use_edges().end());
+ DFSPop(stack, node);
+ VisitPost(node, entry.parent_node, entry.direction);
+ }
+}
+
+void ControlEquivalence::DetermineParticipationEnqueue(ZoneQueue<Node*>& queue,
+ Node* node) {
+ if (!GetData(node)->participates) {
+ GetData(node)->participates = true;
+ queue.push(node);
+ }
+}
+
+
+void ControlEquivalence::DetermineParticipation(Node* exit) {
+ ZoneQueue<Node*> queue(zone_);
+ DetermineParticipationEnqueue(queue, exit);
+ while (!queue.empty()) { // Breadth-first backwards traversal.
+ Node* node = queue.front();
+ queue.pop();
+ int max = NodeProperties::PastControlIndex(node);
+ for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
+ DetermineParticipationEnqueue(queue, node->InputAt(i));
+ }
+ }
+}
+
+
+void ControlEquivalence::DFSPush(DFSStack& stack, Node* node, Node* from,
+ DFSDirection dir) {
+ DCHECK(GetData(node)->participates);
+ DCHECK(!GetData(node)->visited);
+ GetData(node)->on_stack = true;
+ Node::InputEdges::iterator input = node->input_edges().begin();
+ Node::UseEdges::iterator use = node->use_edges().begin();
+ stack.push({dir, input, use, from, node});
+}
+
+
+void ControlEquivalence::DFSPop(DFSStack& stack, Node* node) {
+ DCHECK_EQ(stack.top().node, node);
+ GetData(node)->on_stack = false;
+ GetData(node)->visited = true;
+ stack.pop();
+}
+
+
+void ControlEquivalence::BracketListDelete(BracketList& blist, Node* to,
+ DFSDirection direction) {
+ // TODO(mstarzinger): Optimize this to avoid linear search.
+ for (BracketList::iterator i = blist.begin(); i != blist.end(); /*nop*/) {
+ if (i->to == to && i->direction != direction) {
+ TRACE(" BList erased: {%d->%d}\n", i->from->id(), i->to->id());
+ i = blist.erase(i);
+ } else {
+ ++i;
+ }
+ }
+}
+
+
+void ControlEquivalence::BracketListTRACE(BracketList& blist) {
+ if (FLAG_trace_turbo_ceq) {
+ TRACE(" BList: ");
+ for (Bracket bracket : blist) {
+ TRACE("{%d->%d} ", bracket.from->id(), bracket.to->id());
+ }
+ TRACE("\n");
+ }
+}
+
+} // namespace compiler
+} // namespace internal
+} // namespace v8