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