OLD | NEW |
---|---|
1 // Copyright 2015 the V8 project authors. All rights reserved. | 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 | 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/effect-control-linearizer.h" | 5 #include "src/compiler/effect-control-linearizer.h" |
6 | 6 |
7 #include "src/code-factory.h" | 7 #include "src/code-factory.h" |
8 #include "src/compiler/access-builder.h" | 8 #include "src/compiler/access-builder.h" |
9 #include "src/compiler/js-graph.h" | 9 #include "src/compiler/js-graph.h" |
10 #include "src/compiler/linkage.h" | 10 #include "src/compiler/linkage.h" |
(...skipping 16 matching lines...) Expand all Loading... | |
27 } | 27 } |
28 SimplifiedOperatorBuilder* EffectControlLinearizer::simplified() const { | 28 SimplifiedOperatorBuilder* EffectControlLinearizer::simplified() const { |
29 return js_graph_->simplified(); | 29 return js_graph_->simplified(); |
30 } | 30 } |
31 MachineOperatorBuilder* EffectControlLinearizer::machine() const { | 31 MachineOperatorBuilder* EffectControlLinearizer::machine() const { |
32 return js_graph_->machine(); | 32 return js_graph_->machine(); |
33 } | 33 } |
34 | 34 |
35 namespace { | 35 namespace { |
36 | 36 |
37 struct BlockEffectData { | 37 struct BlockEffectControlData { |
38 Node* current_effect = nullptr; // New effect. | 38 Node* current_effect = nullptr; // New effect. |
39 Node* current_control = nullptr; // New control. | |
39 }; | 40 }; |
40 | 41 |
41 // Effect phis that need to be updated after the first pass. | 42 // Effect phis that need to be updated after the first pass. |
42 struct PendingEffectPhi { | 43 struct PendingEffectPhi { |
43 Node* effect_phi; | 44 Node* effect_phi; |
44 BasicBlock* block; | 45 BasicBlock* block; |
45 | 46 |
46 PendingEffectPhi(Node* effect_phi, BasicBlock* block) | 47 PendingEffectPhi(Node* effect_phi, BasicBlock* block) |
47 : effect_phi(effect_phi), block(block) {} | 48 : effect_phi(effect_phi), block(block) {} |
48 }; | 49 }; |
49 | 50 |
50 void UpdateEffectPhi(Node* node, BasicBlock* block, | 51 void UpdateEffectPhi(Node* node, BasicBlock* block, |
51 ZoneVector<BlockEffectData>* block_effects) { | 52 ZoneVector<BlockEffectControlData>* block_effects) { |
52 // Update all inputs to an effect phi with the effects from the given | 53 // Update all inputs to an effect phi with the effects from the given |
53 // block->effect map. | 54 // block->effect map. |
54 DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode()); | 55 DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode()); |
55 DCHECK_EQ(node->op()->EffectInputCount(), block->PredecessorCount()); | 56 DCHECK_EQ(node->op()->EffectInputCount(), block->PredecessorCount()); |
56 for (int i = 0; i < node->op()->EffectInputCount(); i++) { | 57 for (int i = 0; i < node->op()->EffectInputCount(); i++) { |
57 Node* input = node->InputAt(i); | 58 Node* input = node->InputAt(i); |
58 BasicBlock* predecessor = block->PredecessorAt(static_cast<size_t>(i)); | 59 BasicBlock* predecessor = block->PredecessorAt(static_cast<size_t>(i)); |
59 Node* input_effect = | 60 Node* input_effect = |
60 (*block_effects)[predecessor->rpo_number()].current_effect; | 61 (*block_effects)[predecessor->rpo_number()].current_effect; |
61 if (input != input_effect) { | 62 if (input != input_effect) { |
62 node->ReplaceInput(i, input_effect); | 63 node->ReplaceInput(i, input_effect); |
63 } | 64 } |
64 } | 65 } |
65 } | 66 } |
66 | 67 |
68 void UpdateBlockControl(BasicBlock* block, | |
69 ZoneVector<BlockEffectControlData>* block_effects) { | |
70 Node* control = block->NodeAt(0); | |
71 DCHECK(NodeProperties::IsControl(control)); | |
72 | |
73 // Do not rewire the end node. | |
74 if (control->opcode() == IrOpcode::kEnd) return; | |
75 | |
76 // Update all inputs to the given control node with the correct control. | |
77 DCHECK_EQ(control->op()->ControlInputCount(), block->PredecessorCount()); | |
78 for (int i = 0; i < control->op()->ControlInputCount(); i++) { | |
79 Node* input = NodeProperties::GetControlInput(control, i); | |
80 BasicBlock* predecessor = block->PredecessorAt(static_cast<size_t>(i)); | |
81 Node* input_control = | |
82 (*block_effects)[predecessor->rpo_number()].current_control; | |
83 if (input != input_control) { | |
84 NodeProperties::ReplaceControlInput(control, input_control, i); | |
85 } | |
86 } | |
87 } | |
88 | |
67 bool HasIncomingBackEdges(BasicBlock* block) { | 89 bool HasIncomingBackEdges(BasicBlock* block) { |
68 for (BasicBlock* pred : block->predecessors()) { | 90 for (BasicBlock* pred : block->predecessors()) { |
69 if (pred->rpo_number() >= block->rpo_number()) { | 91 if (pred->rpo_number() >= block->rpo_number()) { |
70 return true; | 92 return true; |
71 } | 93 } |
72 } | 94 } |
73 return false; | 95 return false; |
74 } | 96 } |
75 | 97 |
76 void RemoveRegionNode(Node* node) { | 98 void RemoveRegionNode(Node* node) { |
(...skipping 10 matching lines...) Expand all Loading... | |
87 DCHECK(!NodeProperties::IsFrameStateEdge(edge)); | 109 DCHECK(!NodeProperties::IsFrameStateEdge(edge)); |
88 edge.UpdateTo(node->InputAt(0)); | 110 edge.UpdateTo(node->InputAt(0)); |
89 } | 111 } |
90 } | 112 } |
91 node->Kill(); | 113 node->Kill(); |
92 } | 114 } |
93 | 115 |
94 } // namespace | 116 } // namespace |
95 | 117 |
96 void EffectControlLinearizer::Run() { | 118 void EffectControlLinearizer::Run() { |
97 ZoneVector<BlockEffectData> block_effects(temp_zone()); | 119 ZoneVector<BlockEffectControlData> block_effects(temp_zone()); |
98 ZoneVector<PendingEffectPhi> pending_effect_phis(temp_zone()); | 120 ZoneVector<PendingEffectPhi> pending_effect_phis(temp_zone()); |
121 ZoneVector<BasicBlock*> pending_block_controls(temp_zone()); | |
99 block_effects.resize(schedule()->RpoBlockCount()); | 122 block_effects.resize(schedule()->RpoBlockCount()); |
100 NodeVector inputs_buffer(temp_zone()); | 123 NodeVector inputs_buffer(temp_zone()); |
101 | 124 |
102 for (BasicBlock* block : *(schedule()->rpo_order())) { | 125 for (BasicBlock* block : *(schedule()->rpo_order())) { |
103 size_t instr = 0; | 126 size_t instr = 0; |
104 | 127 |
105 // The control node should be the first. | 128 // The control node should be the first. |
106 Node* control = block->NodeAt(instr); | 129 Node* control = block->NodeAt(instr); |
107 DCHECK(NodeProperties::IsControl(control)); | 130 DCHECK(NodeProperties::IsControl(control)); |
131 // Update the control inputs. | |
132 if (HasIncomingBackEdges(block)) { | |
133 // If there are back edges, we need to update later because we have not | |
134 // computed the control yet. This should only happen for loops. | |
135 DCHECK_EQ(IrOpcode::kLoop, control->opcode()); | |
136 pending_block_controls.push_back(block); | |
137 } else { | |
138 // If there are no back edges, we can update now. | |
139 UpdateBlockControl(block, &block_effects); | |
140 } | |
108 instr++; | 141 instr++; |
109 | 142 |
110 // Iterate over the phis and update the effect phis. | 143 // Iterate over the phis and update the effect phis. |
111 Node* effect = nullptr; | 144 Node* effect = nullptr; |
112 Node* terminate = nullptr; | 145 Node* terminate = nullptr; |
113 for (; instr < block->NodeCount(); instr++) { | 146 for (; instr < block->NodeCount(); instr++) { |
114 Node* node = block->NodeAt(instr); | 147 Node* node = block->NodeAt(instr); |
115 // Only go through the phis and effect phis. | 148 // Only go through the phis and effect phis. |
116 if (node->opcode() == IrOpcode::kEffectPhi) { | 149 if (node->opcode() == IrOpcode::kEffectPhi) { |
117 // There should be at most one effect phi in a block. | 150 // There should be at most one effect phi in a block. |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
170 inputs_buffer.clear(); | 203 inputs_buffer.clear(); |
171 inputs_buffer.resize(block->PredecessorCount(), graph()->start()); | 204 inputs_buffer.resize(block->PredecessorCount(), graph()->start()); |
172 inputs_buffer.push_back(control); | 205 inputs_buffer.push_back(control); |
173 effect = graph()->NewNode( | 206 effect = graph()->NewNode( |
174 common()->EffectPhi(static_cast<int>(block->PredecessorCount())), | 207 common()->EffectPhi(static_cast<int>(block->PredecessorCount())), |
175 static_cast<int>(inputs_buffer.size()), &(inputs_buffer.front())); | 208 static_cast<int>(inputs_buffer.size()), &(inputs_buffer.front())); |
176 // Let us update the effect phi node later. | 209 // Let us update the effect phi node later. |
177 pending_effect_phis.push_back(PendingEffectPhi(effect, block)); | 210 pending_effect_phis.push_back(PendingEffectPhi(effect, block)); |
178 } else if (control->opcode() == IrOpcode::kIfException) { | 211 } else if (control->opcode() == IrOpcode::kIfException) { |
179 // The IfException is connected into the effect chain, so we need | 212 // The IfException is connected into the effect chain, so we need |
180 // to process it here. | 213 // to update the effect here. |
181 ProcessNode(control, &effect, &control); | 214 NodeProperties::ReplaceEffectInput(control, effect); |
215 effect = control; | |
182 } | 216 } |
183 } | 217 } |
184 } | 218 } |
185 | 219 |
186 // Fixup the Terminate node. | 220 // Fixup the Terminate node. |
187 if (terminate != nullptr) { | 221 if (terminate != nullptr) { |
188 NodeProperties::ReplaceEffectInput(terminate, effect); | 222 NodeProperties::ReplaceEffectInput(terminate, effect); |
189 } | 223 } |
190 | 224 |
191 // Process the ordinary instructions. | 225 // Process the ordinary instructions. |
(...skipping 13 matching lines...) Expand all Loading... | |
205 case BasicBlock::kSwitch: | 239 case BasicBlock::kSwitch: |
206 case BasicBlock::kReturn: | 240 case BasicBlock::kReturn: |
207 case BasicBlock::kDeoptimize: | 241 case BasicBlock::kDeoptimize: |
208 case BasicBlock::kThrow: | 242 case BasicBlock::kThrow: |
209 ProcessNode(block->control_input(), &effect, &control); | 243 ProcessNode(block->control_input(), &effect, &control); |
210 break; | 244 break; |
211 } | 245 } |
212 | 246 |
213 // Store the effect for later use. | 247 // Store the effect for later use. |
214 block_effects[block->rpo_number()].current_effect = effect; | 248 block_effects[block->rpo_number()].current_effect = effect; |
249 block_effects[block->rpo_number()].current_control = control; | |
215 } | 250 } |
216 | 251 |
217 // Update the incoming edges of the effect phis that could not be processed | 252 // Update the incoming edges of the effect phis that could not be processed |
218 // during the first pass (because they could have incoming back edges). | 253 // during the first pass (because they could have incoming back edges). |
219 for (const PendingEffectPhi& pending_effect_phi : pending_effect_phis) { | 254 for (const PendingEffectPhi& pending_effect_phi : pending_effect_phis) { |
220 UpdateEffectPhi(pending_effect_phi.effect_phi, pending_effect_phi.block, | 255 UpdateEffectPhi(pending_effect_phi.effect_phi, pending_effect_phi.block, |
221 &block_effects); | 256 &block_effects); |
222 } | 257 } |
258 for (BasicBlock* pending_block_control : pending_block_controls) { | |
259 UpdateBlockControl(pending_block_control, &block_effects); | |
260 } | |
223 } | 261 } |
224 | 262 |
225 void EffectControlLinearizer::ProcessNode(Node* node, Node** effect, | 263 void EffectControlLinearizer::ProcessNode(Node* node, Node** effect, |
226 Node** control) { | 264 Node** control) { |
227 // If the node needs to be wired into the effect/control chain, do this | 265 // If the node needs to be wired into the effect/control chain, do this |
228 // here. | 266 // here. |
229 if (TryWireInStateEffect(node, effect, control)) { | 267 if (TryWireInStateEffect(node, effect, control)) { |
230 return; | 268 return; |
231 } | 269 } |
232 | 270 |
233 // Remove the end markers of 'atomic' allocation region because the | 271 // Remove the end markers of 'atomic' allocation region because the |
234 // region should be wired-in now. | 272 // region should be wired-in now. |
235 if (node->opcode() == IrOpcode::kFinishRegion || | 273 if (node->opcode() == IrOpcode::kFinishRegion || |
236 node->opcode() == IrOpcode::kBeginRegion) { | 274 node->opcode() == IrOpcode::kBeginRegion) { |
237 // Update the value uses to the value input of the finish node and | 275 // Update the value uses to the value input of the finish node and |
238 // the effect uses to the effect input. | 276 // the effect uses to the effect input. |
239 | 277 |
240 // TODO(jarin) Enable this once we make sure everything with side effects | 278 // TODO(jarin) Enable this once we make sure everything with side effects |
241 // is marked as effectful. | 279 // is marked as effectful. |
242 if (false) { | 280 if (false) { |
243 return RemoveRegionNode(node); | 281 return RemoveRegionNode(node); |
244 } | 282 } |
245 } | 283 } |
246 | 284 |
285 if (node->opcode() == IrOpcode::kIfSuccess) { | |
286 Node* success_input = NodeProperties::GetControlInput(node, 0); | |
287 if (*control == success_input) { | |
288 // The IfSuccess node refers to the last control node in the schedule, | |
289 // so we just update the current control. | |
290 *control = node; | |
291 } else { | |
292 // Some other intervening control has been scheduled after call, | |
293 // we need to insert the IfSuccess node just after the call. | |
294 for (Edge edge : success_input->use_edges()) { | |
Benedikt Meurer
2016/04/24 18:12:49
Not sure I really get this one: This tries to upda
Jarin
2016/04/24 19:21:23
I have changed this to keep the wiring of IfSucces
| |
295 if (NodeProperties::IsControlEdge(edge) && edge.from() != node && | |
296 edge.from()->op()->ControlOutputCount() > 0) { | |
297 edge.UpdateTo(node); | |
298 } | |
299 } | |
300 } | |
301 return; | |
302 } | |
303 | |
247 // If the node takes an effect, replace with the current one. | 304 // If the node takes an effect, replace with the current one. |
248 if (node->op()->EffectInputCount() > 0) { | 305 if (node->op()->EffectInputCount() > 0) { |
249 DCHECK_EQ(1, node->op()->EffectInputCount()); | 306 DCHECK_EQ(1, node->op()->EffectInputCount()); |
250 Node* input_effect = NodeProperties::GetEffectInput(node); | 307 Node* input_effect = NodeProperties::GetEffectInput(node); |
251 | 308 |
252 if (input_effect != *effect) { | 309 if (input_effect != *effect) { |
253 NodeProperties::ReplaceEffectInput(node, *effect); | 310 NodeProperties::ReplaceEffectInput(node, *effect); |
254 } | 311 } |
255 | 312 |
256 // If the node produces an effect, update our current effect. (However, | 313 // If the node produces an effect, update our current effect. (However, |
257 // ignore new effect chains started with ValueEffect.) | 314 // ignore new effect chains started with ValueEffect.) |
258 if (node->op()->EffectOutputCount() > 0) { | 315 if (node->op()->EffectOutputCount() > 0) { |
259 DCHECK_EQ(1, node->op()->EffectOutputCount()); | 316 DCHECK_EQ(1, node->op()->EffectOutputCount()); |
260 *effect = node; | 317 *effect = node; |
261 } | 318 } |
262 } else { | 319 } else { |
263 // New effect chain is only started with a Start or ValueEffect node. | 320 // New effect chain is only started with a Start or ValueEffect node. |
264 DCHECK(node->op()->EffectOutputCount() == 0 || | 321 DCHECK(node->op()->EffectOutputCount() == 0 || |
265 node->opcode() == IrOpcode::kStart); | 322 node->opcode() == IrOpcode::kStart); |
266 } | 323 } |
324 // Rewire control inputs of control nodes, and update the current control | |
325 // input. | |
326 if (node->op()->ControlOutputCount() > 0) { | |
327 DCHECK_EQ(1, node->op()->ControlInputCount()); | |
328 NodeProperties::ReplaceControlInput(node, *control); | |
329 *control = node; | |
330 } | |
267 } | 331 } |
268 | 332 |
269 bool EffectControlLinearizer::TryWireInStateEffect(Node* node, Node** effect, | 333 bool EffectControlLinearizer::TryWireInStateEffect(Node* node, Node** effect, |
270 Node** control) { | 334 Node** control) { |
271 ValueEffectControl state(nullptr, nullptr, nullptr); | 335 ValueEffectControl state(nullptr, nullptr, nullptr); |
272 switch (node->opcode()) { | 336 switch (node->opcode()) { |
273 case IrOpcode::kChangeInt32ToTagged: | 337 case IrOpcode::kChangeInt32ToTagged: |
274 state = LowerChangeInt32ToTagged(node, *effect, *control); | 338 state = LowerChangeInt32ToTagged(node, *effect, *control); |
275 break; | 339 break; |
276 case IrOpcode::kChangeUint32ToTagged: | 340 case IrOpcode::kChangeUint32ToTagged: |
(...skipping 180 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
457 return jsgraph()->Int32Constant(Smi::kMaxValue); | 521 return jsgraph()->Int32Constant(Smi::kMaxValue); |
458 } | 522 } |
459 | 523 |
460 Node* EffectControlLinearizer::SmiShiftBitsConstant() { | 524 Node* EffectControlLinearizer::SmiShiftBitsConstant() { |
461 return jsgraph()->IntPtrConstant(kSmiShiftSize + kSmiTagSize); | 525 return jsgraph()->IntPtrConstant(kSmiShiftSize + kSmiTagSize); |
462 } | 526 } |
463 | 527 |
464 } // namespace compiler | 528 } // namespace compiler |
465 } // namespace internal | 529 } // namespace internal |
466 } // namespace v8 | 530 } // namespace v8 |
OLD | NEW |