OLD | NEW |
1 // Copyright 2013 the V8 project authors. All rights reserved. | 1 // Copyright 2013 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/compiler/loop-analysis.h" | 5 #include "src/compiler/loop-analysis.h" |
6 | 6 |
7 #include "src/compiler/graph.h" | 7 #include "src/compiler/graph.h" |
8 #include "src/compiler/node.h" | 8 #include "src/compiler/node.h" |
9 #include "src/compiler/node-marker.h" | 9 #include "src/compiler/node-marker.h" |
10 #include "src/compiler/node-properties-inl.h" | 10 #include "src/compiler/node-properties-inl.h" |
(...skipping 134 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
145 // Propagate marks backward from loop headers. | 145 // Propagate marks backward from loop headers. |
146 void PropagateBackward() { | 146 void PropagateBackward() { |
147 PropagateBackward(end_, kVisited); | 147 PropagateBackward(end_, kVisited); |
148 | 148 |
149 while (!queue_.empty()) { | 149 while (!queue_.empty()) { |
150 Node* node = queue_.front(); | 150 Node* node = queue_.front(); |
151 queue_.pop_front(); | 151 queue_.pop_front(); |
152 queued_.Set(node, false); | 152 queued_.Set(node, false); |
153 | 153 |
154 // Setup loop headers first. | 154 // Setup loop headers first. |
| 155 NodeInfo& ni = info(node); |
155 if (node->opcode() == IrOpcode::kLoop) { | 156 if (node->opcode() == IrOpcode::kLoop) { |
156 // found the loop node first. | 157 // found the loop node first. |
157 CreateLoopInfo(node); | 158 CreateLoopInfo(node, ni); |
158 } else if (node->opcode() == IrOpcode::kPhi || | 159 } else if (node->opcode() == IrOpcode::kPhi || |
159 node->opcode() == IrOpcode::kEffectPhi) { | 160 node->opcode() == IrOpcode::kEffectPhi) { |
160 // found a phi first. | 161 // found a phi first. |
161 Node* merge = node->InputAt(node->InputCount() - 1); | 162 Node* merge = node->InputAt(node->InputCount() - 1); |
162 if (merge->opcode() == IrOpcode::kLoop) CreateLoopInfo(merge); | 163 if (merge->opcode() == IrOpcode::kLoop) { |
| 164 NodeInfo& mi = info(merge); |
| 165 CreateLoopInfo(merge, mi); |
| 166 ni.MarkBackward(mi.loop_mark); |
| 167 } |
163 } | 168 } |
164 | 169 |
165 // Propagate reachability marks backwards from this node. | 170 // Propagate reachability marks backwards from this node. |
166 NodeInfo& ni = info(node); | |
167 if (ni.IsLoopHeader()) { | 171 if (ni.IsLoopHeader()) { |
168 // Handle edges from loop header nodes specially. | 172 // Handle edges from loop header nodes specially. |
169 for (int i = 0; i < node->InputCount(); i++) { | 173 for (int i = 0; i < node->InputCount(); i++) { |
170 if (i == kAssumedLoopEntryIndex) { | 174 if (i == kAssumedLoopEntryIndex) { |
171 // Don't propagate the loop mark backwards on the entry edge. | 175 // Don't propagate the loop mark backwards on the entry edge. |
172 PropagateBackward(node->InputAt(0), | 176 PropagateBackward(node->InputAt(0), |
173 kVisited | (ni.backward & ~ni.loop_mark)); | 177 kVisited | (ni.backward & ~ni.loop_mark)); |
174 } else { | 178 } else { |
175 // Only propagate the loop mark on backedges. | 179 // Only propagate the loop mark on backedges. |
176 PropagateBackward(node->InputAt(i), ni.loop_mark); | 180 PropagateBackward(node->InputAt(i), ni.loop_mark); |
177 } | 181 } |
178 } | 182 } |
179 } else { | 183 } else { |
180 // Propagate all loop marks backwards for a normal node. | 184 // Propagate all loop marks backwards for a normal node. |
181 for (Node* const input : node->inputs()) { | 185 for (Node* const input : node->inputs()) { |
182 PropagateBackward(input, ni.backward); | 186 PropagateBackward(input, ni.backward); |
183 } | 187 } |
184 } | 188 } |
185 } | 189 } |
186 } | 190 } |
187 | 191 |
188 // Make a new loop header for the given node. | 192 // Make a new loop header for the given node. |
189 void CreateLoopInfo(Node* node) { | 193 void CreateLoopInfo(Node* node, NodeInfo& ni) { |
190 NodeInfo& ni = info(node); | |
191 if (ni.IsLoopHeader()) return; // loop already set up. | 194 if (ni.IsLoopHeader()) return; // loop already set up. |
192 | 195 |
193 loops_found_++; | 196 loops_found_++; |
194 size_t loop_num = loops_.size() + 1; | 197 size_t loop_num = loops_.size() + 1; |
195 CHECK(loops_found_ <= kMaxLoops); // TODO(titzer): don't crash. | 198 CHECK(loops_found_ <= kMaxLoops); // TODO(titzer): don't crash. |
196 // Create a new loop. | 199 // Create a new loop. |
197 loops_.push_back({node, nullptr, nullptr, nullptr}); | 200 loops_.push_back({node, nullptr, nullptr, nullptr}); |
198 loop_tree_->NewLoop(); | 201 loop_tree_->NewLoop(); |
199 LoopMarks loop_mark = kVisited | (1 << loop_num); | 202 LoopMarks loop_mark = kVisited | (1 << loop_num); |
200 ni.node = node; | |
201 ni.loop_mark = loop_mark; | 203 ni.loop_mark = loop_mark; |
202 | 204 |
203 // Setup loop mark for phis attached to loop header. | 205 // Setup loop mark for phis attached to loop header. |
204 for (Node* use : node->uses()) { | 206 for (Node* use : node->uses()) { |
205 if (use->opcode() == IrOpcode::kPhi || | 207 if (use->opcode() == IrOpcode::kPhi || |
206 use->opcode() == IrOpcode::kEffectPhi) { | 208 use->opcode() == IrOpcode::kEffectPhi) { |
207 info(use).loop_mark = loop_mark; | 209 info(use).loop_mark = loop_mark; |
208 } | 210 } |
209 } | 211 } |
210 } | 212 } |
(...skipping 193 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
404 finder.Run(); | 406 finder.Run(); |
405 if (FLAG_trace_turbo_graph) { | 407 if (FLAG_trace_turbo_graph) { |
406 finder.Print(); | 408 finder.Print(); |
407 } | 409 } |
408 return loop_tree; | 410 return loop_tree; |
409 } | 411 } |
410 | 412 |
411 } // namespace compiler | 413 } // namespace compiler |
412 } // namespace internal | 414 } // namespace internal |
413 } // namespace v8 | 415 } // namespace v8 |
OLD | NEW |