Line data Source code
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 :
13 : namespace v8 {
14 : namespace internal {
15 : namespace compiler {
16 :
17 215041 : void ControlEquivalence::Run(Node* exit) {
18 215043 : if (!Participates(exit) || GetClass(exit) == kInvalidClass) {
19 215039 : DetermineParticipation(exit);
20 215039 : RunUndirectedDFS(exit);
21 : }
22 215041 : }
23 :
24 :
25 : // static
26 : STATIC_CONST_MEMBER_DEFINITION const size_t ControlEquivalence::kInvalidClass;
27 :
28 :
29 5423007 : void ControlEquivalence::VisitPre(Node* node) {
30 5423007 : TRACE("CEQ: Pre-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
31 5423007 : }
32 :
33 :
34 5422995 : void ControlEquivalence::VisitMid(Node* node, DFSDirection direction) {
35 5422995 : TRACE("CEQ: Mid-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
36 5422999 : BracketList& blist = GetBracketList(node);
37 :
38 : // Remove brackets pointing to this node [line:19].
39 5422999 : BracketListDelete(blist, node, direction);
40 :
41 : // Potentially introduce artificial dependency from start to end.
42 5423008 : if (blist.empty()) {
43 : DCHECK_EQ(kInputDirection, direction);
44 268724 : VisitBackedge(node, graph_->end(), kInputDirection);
45 : }
46 :
47 : // Potentially start a new equivalence class [line:37].
48 5423008 : BracketListTRACE(blist);
49 : Bracket* recent = &blist.back();
50 10846018 : if (recent->recent_size != blist.size()) {
51 2616861 : recent->recent_size = blist.size();
52 2616861 : recent->recent_class = NewClassNumber();
53 : }
54 :
55 : // Assign equivalence class to node.
56 5423009 : SetClass(node, recent->recent_class);
57 5423002 : TRACE(" Assigned class number is %zu\n", GetClass(node));
58 5423002 : }
59 :
60 :
61 5422996 : void ControlEquivalence::VisitPost(Node* node, Node* parent_node,
62 : DFSDirection direction) {
63 5422996 : TRACE("CEQ: Post-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
64 5422989 : BracketList& blist = GetBracketList(node);
65 :
66 : // Remove brackets pointing to this node [line:19].
67 5422989 : BracketListDelete(blist, node, direction);
68 :
69 : // Propagate bracket list up the DFS tree [line:13].
70 5423004 : if (parent_node != nullptr) {
71 : BracketList& parent_blist = GetBracketList(parent_node);
72 10415918 : parent_blist.splice(parent_blist.end(), blist);
73 : }
74 5422998 : }
75 :
76 :
77 1349923 : void ControlEquivalence::VisitBackedge(Node* from, Node* to,
78 : DFSDirection direction) {
79 1349923 : 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 1349923 : Bracket bracket = {direction, kInvalidClass, 0, from, to};
84 1349923 : GetBracketList(from).push_back(bracket);
85 1349923 : }
86 :
87 :
88 215037 : void ControlEquivalence::RunUndirectedDFS(Node* exit) {
89 215037 : ZoneStack<DFSStackEntry> stack(zone_);
90 215037 : DFSPush(stack, exit, nullptr, kInputDirection);
91 215037 : VisitPre(exit);
92 :
93 40138407 : while (!stack.empty()) { // Undirected depth-first backwards traversal.
94 : DFSStackEntry& entry = stack.top();
95 39708288 : Node* node = entry.node;
96 :
97 39708288 : if (entry.direction == kInputDirection) {
98 18806528 : if (entry.input != node->input_edges().end()) {
99 13383537 : Edge edge = *entry.input;
100 : Node* input = edge.to();
101 : ++(entry.input);
102 13383537 : if (NodeProperties::IsControlEdge(edge)) {
103 : // Visit next control input.
104 6437121 : if (!Participates(input)) continue;
105 6437124 : if (GetData(input)->visited) continue;
106 5443534 : if (GetData(input)->on_stack) {
107 : // Found backedge if input is on stack.
108 2130262 : if (input != entry.parent_node) {
109 235569 : VisitBackedge(node, input, kInputDirection);
110 : }
111 : } else {
112 : // Push input onto stack.
113 3313285 : DFSPush(stack, input, node, kInputDirection);
114 3313289 : VisitPre(input);
115 : }
116 : }
117 : continue;
118 : }
119 5422991 : if (entry.use != node->use_edges().end()) {
120 : // Switch direction to uses.
121 3528317 : entry.direction = kUseDirection;
122 3528317 : VisitMid(node, kInputDirection);
123 3528319 : continue;
124 : }
125 : }
126 :
127 22796434 : if (entry.direction == kUseDirection) {
128 20902769 : if (entry.use != node->use_edges().end()) {
129 15479772 : Edge edge = *entry.use;
130 : Node* use = edge.from();
131 : ++(entry.use);
132 15479772 : if (NodeProperties::IsControlEdge(edge)) {
133 : // Visit next control use.
134 10654164 : if (!Participates(use)) continue;
135 6289161 : if (GetData(use)->visited) continue;
136 6053588 : if (GetData(use)->on_stack) {
137 : // Found backedge if use is on stack.
138 4158904 : if (use != entry.parent_node) {
139 845633 : VisitBackedge(node, use, kUseDirection);
140 : }
141 : } else {
142 : // Push use onto stack.
143 1894692 : DFSPush(stack, use, node, kUseDirection);
144 1894692 : VisitPre(use);
145 : }
146 : }
147 : continue;
148 : }
149 5422997 : if (entry.input != node->input_edges().end()) {
150 : // Switch direction to inputs.
151 1894693 : entry.direction = kInputDirection;
152 1894693 : VisitMid(node, kUseDirection);
153 1894695 : 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 5421969 : DFSPop(stack, node);
161 5422996 : VisitPost(node, entry.parent_node, entry.direction);
162 : }
163 215039 : }
164 :
165 6652113 : void ControlEquivalence::DetermineParticipationEnqueue(ZoneQueue<Node*>& queue,
166 : Node* node) {
167 13304231 : if (!Participates(node)) {
168 5422980 : AllocateData(node);
169 : queue.push(node);
170 : }
171 6652113 : }
172 :
173 :
174 215039 : void ControlEquivalence::DetermineParticipation(Node* exit) {
175 215039 : ZoneQueue<Node*> queue(zone_);
176 215039 : DetermineParticipationEnqueue(queue, exit);
177 5853044 : while (!queue.empty()) { // Breadth-first backwards traversal.
178 5422974 : Node* node = queue.front();
179 : queue.pop();
180 5422976 : int max = NodeProperties::PastControlIndex(node);
181 11860059 : for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
182 6437077 : DetermineParticipationEnqueue(queue, node->InputAt(i));
183 : }
184 : }
185 215039 : }
186 :
187 :
188 5423004 : void ControlEquivalence::DFSPush(DFSStack& stack, Node* node, Node* from,
189 : DFSDirection dir) {
190 : DCHECK(Participates(node));
191 : DCHECK(!GetData(node)->visited);
192 5423004 : GetData(node)->on_stack = true;
193 : Node::InputEdges::iterator input = node->input_edges().begin();
194 : Node::UseEdges::iterator use = node->use_edges().begin();
195 16269022 : stack.push({dir, input, use, from, node});
196 5423006 : }
197 :
198 :
199 5422995 : void ControlEquivalence::DFSPop(DFSStack& stack, Node* node) {
200 : DCHECK_EQ(stack.top().node, node);
201 5422995 : GetData(node)->on_stack = false;
202 5422994 : GetData(node)->visited = true;
203 : stack.pop();
204 5423000 : }
205 :
206 :
207 10845945 : void ControlEquivalence::BracketListDelete(BracketList& blist, Node* to,
208 : DFSDirection direction) {
209 : // TODO(mstarzinger): Optimize this to avoid linear search.
210 59814815 : for (BracketList::iterator i = blist.begin(); i != blist.end(); /*nop*/) {
211 38122918 : if (i->to == to && i->direction != direction) {
212 1081176 : TRACE(" BList erased: {%d->%d}\n", i->from->id(), i->to->id());
213 : i = blist.erase(i);
214 : } else {
215 : ++i;
216 : }
217 : }
218 10845952 : }
219 :
220 :
221 5423006 : void ControlEquivalence::BracketListTRACE(BracketList& blist) {
222 5423006 : if (FLAG_trace_turbo_ceq) {
223 0 : TRACE(" BList: ");
224 0 : for (Bracket bracket : blist) {
225 0 : TRACE("{%d->%d} ", bracket.from->id(), bracket.to->id());
226 : }
227 0 : TRACE("\n");
228 : }
229 5423006 : }
230 :
231 : } // namespace compiler
232 : } // namespace internal
233 : } // namespace v8
|
