1// Copyright 2015 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/compiler/control-equivalence.h"
6#include "src/compiler/node-properties.h"
7
8#define TRACE(...)                                 \
9  do {                                             \
10    if (FLAG_trace_turbo_ceq) PrintF(__VA_ARGS__); \
11  } while (false)
12
13namespace v8 {
14namespace internal {
15namespace compiler {
16
17void ControlEquivalence::Run(Node* exit) {
18  if (!Participates(exit) || GetClass(exit) == kInvalidClass) {
19    DetermineParticipation(exit);
20    RunUndirectedDFS(exit);
21  }
22}
23
24
25// static
26STATIC_CONST_MEMBER_DEFINITION const size_t ControlEquivalence::kInvalidClass;
27
28
29void ControlEquivalence::VisitPre(Node* node) {
30  TRACE("CEQ: Pre-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
31}
32
33
34void ControlEquivalence::VisitMid(Node* node, DFSDirection direction) {
35  TRACE("CEQ: Mid-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
36  BracketList& blist = GetBracketList(node);
37
38  // Remove brackets pointing to this node [line:19].
39  BracketListDelete(blist, node, direction);
40
41  // Potentially introduce artificial dependency from start to end.
42  if (blist.empty()) {
43    DCHECK_EQ(kInputDirection, direction);
44    VisitBackedge(node, graph_->end(), kInputDirection);
45  }
46
47  // Potentially start a new equivalence class [line:37].
48  BracketListTRACE(blist);
49  Bracket* recent = &blist.back();
50  if (recent->recent_size != blist.size()) {
51    recent->recent_size = blist.size();
52    recent->recent_class = NewClassNumber();
53  }
54
55  // Assign equivalence class to node.
56  SetClass(node, recent->recent_class);
57  TRACE("  Assigned class number is %zu\n", GetClass(node));
58}
59
60
61void ControlEquivalence::VisitPost(Node* node, Node* parent_node,
62                                   DFSDirection direction) {
63  TRACE("CEQ: Post-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
64  BracketList& blist = GetBracketList(node);
65
66  // Remove brackets pointing to this node [line:19].
67  BracketListDelete(blist, node, direction);
68
69  // Propagate bracket list up the DFS tree [line:13].
70  if (parent_node != nullptr) {
71    BracketList& parent_blist = GetBracketList(parent_node);
72    parent_blist.splice(parent_blist.end(), blist);
73  }
74}
75
76
77void ControlEquivalence::VisitBackedge(Node* from, Node* to,
78                                       DFSDirection direction) {
79  TRACE("CEQ: Backedge from #%d:%s to #%d:%s\n", from->id(),
80        from->op()->mnemonic(), to->id(), to->op()->mnemonic());
81
82  // Push backedge onto the bracket list [line:25].
83  Bracket bracket = {direction, kInvalidClass, 0, from, to};
84  GetBracketList(from).push_back(bracket);
85}
86
87
88void ControlEquivalence::RunUndirectedDFS(Node* exit) {
89  ZoneStack<DFSStackEntry> stack(zone_);
90  DFSPush(stack, exit, nullptr, kInputDirection);
91  VisitPre(exit);
92
93  while (!stack.empty()) {  // Undirected depth-first backwards traversal.
94    DFSStackEntry& entry = stack.top();
95    Node* node = entry.node;
96
97    if (entry.direction == kInputDirection) {
98      if (entry.input != node->input_edges().end()) {
99        Edge edge = *entry.input;
100        Node* input = edge.to();
101        ++(entry.input);
102        if (NodeProperties::IsControlEdge(edge)) {
103          // Visit next control input.
104          if (!Participates(input)) continue;
105          if (GetData(input)->visited) continue;
106          if (GetData(input)->on_stack) {
107            // Found backedge if input is on stack.
108            if (input != entry.parent_node) {
109              VisitBackedge(node, input, kInputDirection);
110            }
111          } else {
112            // Push input onto stack.
113            DFSPush(stack, input, node, kInputDirection);
114            VisitPre(input);
115          }
116        }
117        continue;
118      }
119      if (entry.use != node->use_edges().end()) {
120        // Switch direction to uses.
121        entry.direction = kUseDirection;
122        VisitMid(node, kInputDirection);
123        continue;
124      }
125    }
126
127    if (entry.direction == kUseDirection) {
128      if (entry.use != node->use_edges().end()) {
129        Edge edge = *entry.use;
130        Node* use = edge.from();
131        ++(entry.use);
132        if (NodeProperties::IsControlEdge(edge)) {
133          // Visit next control use.
134          if (!Participates(use)) continue;
135          if (GetData(use)->visited) continue;
136          if (GetData(use)->on_stack) {
137            // Found backedge if use is on stack.
138            if (use != entry.parent_node) {
139              VisitBackedge(node, use, kUseDirection);
140            }
141          } else {
142            // Push use onto stack.
143            DFSPush(stack, use, node, kUseDirection);
144            VisitPre(use);
145          }
146        }
147        continue;
148      }
149      if (entry.input != node->input_edges().end()) {
150        // Switch direction to inputs.
151        entry.direction = kInputDirection;
152        VisitMid(node, kUseDirection);
153        continue;
154      }
155    }
156
157    // Pop node from stack when done with all inputs and uses.
158    DCHECK(entry.input == node->input_edges().end());
159    DCHECK(entry.use == node->use_edges().end());
160    DFSPop(stack, node);
161    VisitPost(node, entry.parent_node, entry.direction);
162  }
163}
164
165void ControlEquivalence::DetermineParticipationEnqueue(ZoneQueue<Node*>& queue,
166                                                       Node* node) {
167  if (!Participates(node)) {
168    AllocateData(node);
169    queue.push(node);
170  }
171}
172
173
174void ControlEquivalence::DetermineParticipation(Node* exit) {
175  ZoneQueue<Node*> queue(zone_);
176  DetermineParticipationEnqueue(queue, exit);
177  while (!queue.empty()) {  // Breadth-first backwards traversal.
178    Node* node = queue.front();
179    queue.pop();
180    int max = NodeProperties::PastControlIndex(node);
181    for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
182      DetermineParticipationEnqueue(queue, node->InputAt(i));
183    }
184  }
185}
186
187
188void ControlEquivalence::DFSPush(DFSStack& stack, Node* node, Node* from,
189                                 DFSDirection dir) {
190  DCHECK(Participates(node));
191  DCHECK(!GetData(node)->visited);
192  GetData(node)->on_stack = true;
193  Node::InputEdges::iterator input = node->input_edges().begin();
194  Node::UseEdges::iterator use = node->use_edges().begin();
195  stack.push({dir, input, use, from, node});
196}
197
198
199void ControlEquivalence::DFSPop(DFSStack& stack, Node* node) {
200  DCHECK_EQ(stack.top().node, node);
201  GetData(node)->on_stack = false;
202  GetData(node)->visited = true;
203  stack.pop();
204}
205
206
207void ControlEquivalence::BracketListDelete(BracketList& blist, Node* to,
208                                           DFSDirection direction) {
209  // TODO(turbofan): Optimize this to avoid linear search.
210  for (BracketList::iterator i = blist.begin(); i != blist.end(); /*nop*/) {
211    if (i->to == to && i->direction != direction) {
212      TRACE("  BList erased: {%d->%d}\n", i->from->id(), i->to->id());
213      i = blist.erase(i);
214    } else {
215      ++i;
216    }
217  }
218}
219
220
221void ControlEquivalence::BracketListTRACE(BracketList& blist) {
222  if (FLAG_trace_turbo_ceq) {
223    TRACE("  BList: ");
224    for (Bracket bracket : blist) {
225      TRACE("{%d->%d} ", bracket.from->id(), bracket.to->id());
226    }
227    TRACE("\n");
228  }
229}
230
231#undef TRACE
232
233}  // namespace compiler
234}  // namespace internal
235}  // namespace v8
236