OLD | NEW |
(Empty) | |
| 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/effect-control-linearizer.h" |
| 6 |
| 7 #include "src/code-factory.h" |
| 8 #include "src/compiler/access-builder.h" |
| 9 #include "src/compiler/js-graph.h" |
| 10 #include "src/compiler/linkage.h" |
| 11 #include "src/compiler/node-properties.h" |
| 12 #include "src/compiler/node.h" |
| 13 #include "src/compiler/schedule.h" |
| 14 |
| 15 namespace v8 { |
| 16 namespace internal { |
| 17 namespace compiler { |
| 18 |
| 19 EffectControlLinearizer::EffectControlLinearizer(JSGraph* js_graph, |
| 20 Schedule* schedule, |
| 21 Zone* temp_zone) |
| 22 : js_graph_(js_graph), schedule_(schedule), temp_zone_(temp_zone) {} |
| 23 |
| 24 Graph* EffectControlLinearizer::graph() const { return js_graph_->graph(); } |
| 25 CommonOperatorBuilder* EffectControlLinearizer::common() const { |
| 26 return js_graph_->common(); |
| 27 } |
| 28 SimplifiedOperatorBuilder* EffectControlLinearizer::simplified() const { |
| 29 return js_graph_->simplified(); |
| 30 } |
| 31 MachineOperatorBuilder* EffectControlLinearizer::machine() const { |
| 32 return js_graph_->machine(); |
| 33 } |
| 34 |
| 35 namespace { |
| 36 |
| 37 struct BlockEffectData { |
| 38 Node* current_effect = nullptr; // New effect. |
| 39 }; |
| 40 |
| 41 // Effect phis that need to be updated after the first pass. |
| 42 struct PendingEffectPhi { |
| 43 Node* effect_phi; |
| 44 BasicBlock* block; |
| 45 |
| 46 PendingEffectPhi(Node* effect_phi, BasicBlock* block) |
| 47 : effect_phi(effect_phi), block(block) {} |
| 48 }; |
| 49 |
| 50 void UpdateEffectPhi(Node* node, BasicBlock* block, |
| 51 ZoneVector<BlockEffectData>* block_effects) { |
| 52 // Update all inputs to an effect phi with the effects from the given |
| 53 // block->effect map. |
| 54 DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode()); |
| 55 DCHECK_EQ(node->op()->EffectInputCount(), block->PredecessorCount()); |
| 56 for (int i = 0; i < node->op()->EffectInputCount(); i++) { |
| 57 Node* input = node->InputAt(i); |
| 58 BasicBlock* predecessor = block->PredecessorAt(static_cast<size_t>(i)); |
| 59 Node* input_effect = |
| 60 (*block_effects)[predecessor->rpo_number()].current_effect; |
| 61 if (input != input_effect) { |
| 62 node->ReplaceInput(i, input_effect); |
| 63 } |
| 64 } |
| 65 } |
| 66 |
| 67 bool HasIncomingBackEdges(BasicBlock* block) { |
| 68 for (BasicBlock* pred : block->predecessors()) { |
| 69 if (pred->rpo_number() >= block->rpo_number()) { |
| 70 return true; |
| 71 } |
| 72 } |
| 73 return false; |
| 74 } |
| 75 |
| 76 void RemoveRegionNode(Node* node) { |
| 77 DCHECK(IrOpcode::kFinishRegion == node->opcode() || |
| 78 IrOpcode::kBeginRegion == node->opcode()); |
| 79 // Update the value/context uses to the value input of the finish node and |
| 80 // the effect uses to the effect input. |
| 81 for (Edge edge : node->use_edges()) { |
| 82 DCHECK(!edge.from()->IsDead()); |
| 83 if (NodeProperties::IsEffectEdge(edge)) { |
| 84 edge.UpdateTo(NodeProperties::GetEffectInput(node)); |
| 85 } else { |
| 86 DCHECK(!NodeProperties::IsControlEdge(edge)); |
| 87 DCHECK(!NodeProperties::IsFrameStateEdge(edge)); |
| 88 edge.UpdateTo(node->InputAt(0)); |
| 89 } |
| 90 } |
| 91 node->Kill(); |
| 92 } |
| 93 |
| 94 } // namespace |
| 95 |
| 96 void EffectControlLinearizer::Run() { |
| 97 ZoneVector<BlockEffectData> block_effects(temp_zone()); |
| 98 ZoneVector<PendingEffectPhi> pending_effect_phis(temp_zone()); |
| 99 block_effects.resize(schedule()->RpoBlockCount()); |
| 100 NodeVector inputs_buffer(temp_zone()); |
| 101 |
| 102 for (BasicBlock* block : *(schedule()->rpo_order())) { |
| 103 size_t instr = 0; |
| 104 |
| 105 // The control node should be the first. |
| 106 Node* control = block->NodeAt(instr); |
| 107 DCHECK(NodeProperties::IsControl(control)); |
| 108 instr++; |
| 109 |
| 110 // Iterate over the phis and update the effect phis. |
| 111 Node* effect = nullptr; |
| 112 Node* terminate = nullptr; |
| 113 for (; instr < block->NodeCount(); instr++) { |
| 114 Node* node = block->NodeAt(instr); |
| 115 // Only go through the phis and effect phis. |
| 116 if (node->opcode() == IrOpcode::kEffectPhi) { |
| 117 // There should be at most one effect phi in a block. |
| 118 DCHECK_NULL(effect); |
| 119 // IfException blocks should not have effect phis. |
| 120 DCHECK_NE(IrOpcode::kIfException, control->opcode()); |
| 121 effect = node; |
| 122 |
| 123 // Make sure we update the inputs to the incoming blocks' effects. |
| 124 if (HasIncomingBackEdges(block)) { |
| 125 // In case of loops, we do not update the effect phi immediately |
| 126 // because the back predecessor has not been handled yet. We just |
| 127 // record the effect phi for later processing. |
| 128 pending_effect_phis.push_back(PendingEffectPhi(node, block)); |
| 129 } else { |
| 130 UpdateEffectPhi(node, block, &block_effects); |
| 131 } |
| 132 } else if (node->opcode() == IrOpcode::kPhi) { |
| 133 // Just skip phis. |
| 134 } else if (node->opcode() == IrOpcode::kTerminate) { |
| 135 DCHECK(terminate == nullptr); |
| 136 terminate = node; |
| 137 } else { |
| 138 break; |
| 139 } |
| 140 } |
| 141 |
| 142 if (effect == nullptr) { |
| 143 // There was no effect phi. |
| 144 DCHECK(!HasIncomingBackEdges(block)); |
| 145 if (block == schedule()->start()) { |
| 146 // Start block => effect is start. |
| 147 DCHECK_EQ(graph()->start(), control); |
| 148 effect = graph()->start(); |
| 149 } else if (control->opcode() == IrOpcode::kEnd) { |
| 150 // End block is just a dummy, no effect needed. |
| 151 DCHECK_EQ(BasicBlock::kNone, block->control()); |
| 152 DCHECK_EQ(1u, block->size()); |
| 153 effect = nullptr; |
| 154 } else { |
| 155 // If all the predecessors have the same effect, we can use it |
| 156 // as our current effect. |
| 157 int rpo_number = block->PredecessorAt(0)->rpo_number(); |
| 158 effect = block_effects[rpo_number].current_effect; |
| 159 for (size_t i = 1; i < block->PredecessorCount(); i++) { |
| 160 int rpo_number = block->PredecessorAt(i)->rpo_number(); |
| 161 if (block_effects[rpo_number].current_effect != effect) { |
| 162 effect = nullptr; |
| 163 break; |
| 164 } |
| 165 } |
| 166 if (effect == nullptr) { |
| 167 DCHECK_NE(IrOpcode::kIfException, control->opcode()); |
| 168 // The input blocks do not have the same effect. We have |
| 169 // to create an effect phi node. |
| 170 inputs_buffer.clear(); |
| 171 inputs_buffer.resize(block->PredecessorCount(), graph()->start()); |
| 172 inputs_buffer.push_back(control); |
| 173 effect = graph()->NewNode( |
| 174 common()->EffectPhi(static_cast<int>(block->PredecessorCount())), |
| 175 static_cast<int>(inputs_buffer.size()), &(inputs_buffer.front())); |
| 176 // Let us update the effect phi node later. |
| 177 pending_effect_phis.push_back(PendingEffectPhi(effect, block)); |
| 178 } else if (control->opcode() == IrOpcode::kIfException) { |
| 179 // The IfException is connected into the effect chain, so we need |
| 180 // to process it here. |
| 181 ProcessNode(control, &effect, &control); |
| 182 } |
| 183 } |
| 184 } |
| 185 |
| 186 // Fixup the Terminate node. |
| 187 if (terminate != nullptr) { |
| 188 NodeProperties::ReplaceEffectInput(terminate, effect); |
| 189 } |
| 190 |
| 191 // Process the ordinary instructions. |
| 192 for (; instr < block->NodeCount(); instr++) { |
| 193 Node* node = block->NodeAt(instr); |
| 194 ProcessNode(node, &effect, &control); |
| 195 } |
| 196 |
| 197 switch (block->control()) { |
| 198 case BasicBlock::kGoto: |
| 199 case BasicBlock::kNone: |
| 200 break; |
| 201 |
| 202 case BasicBlock::kCall: |
| 203 case BasicBlock::kTailCall: |
| 204 case BasicBlock::kBranch: |
| 205 case BasicBlock::kSwitch: |
| 206 case BasicBlock::kReturn: |
| 207 case BasicBlock::kDeoptimize: |
| 208 case BasicBlock::kThrow: |
| 209 ProcessNode(block->control_input(), &effect, &control); |
| 210 break; |
| 211 } |
| 212 |
| 213 // Store the effect for later use. |
| 214 block_effects[block->rpo_number()].current_effect = effect; |
| 215 } |
| 216 |
| 217 // 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). |
| 219 for (const PendingEffectPhi& pending_effect_phi : pending_effect_phis) { |
| 220 UpdateEffectPhi(pending_effect_phi.effect_phi, pending_effect_phi.block, |
| 221 &block_effects); |
| 222 } |
| 223 } |
| 224 |
| 225 void EffectControlLinearizer::ProcessNode(Node* node, Node** effect, |
| 226 Node** control) { |
| 227 // If the node needs to be wired into the effect/control chain, do this |
| 228 // here. |
| 229 if (TryWireInStateEffect(node, effect, control)) { |
| 230 return; |
| 231 } |
| 232 |
| 233 // Remove the end markers of 'atomic' allocation region because the |
| 234 // region should be wired-in now. |
| 235 if (node->opcode() == IrOpcode::kFinishRegion || |
| 236 node->opcode() == IrOpcode::kBeginRegion) { |
| 237 // Update the value uses to the value input of the finish node and |
| 238 // the effect uses to the effect input. |
| 239 |
| 240 // TODO(jarin) Enable this once we make sure everything with side effects |
| 241 // is marked as effectful. |
| 242 if (false) { |
| 243 return RemoveRegionNode(node); |
| 244 } |
| 245 } |
| 246 |
| 247 // If the node takes an effect, replace with the current one. |
| 248 if (node->op()->EffectInputCount() > 0) { |
| 249 DCHECK_EQ(1, node->op()->EffectInputCount()); |
| 250 Node* input_effect = NodeProperties::GetEffectInput(node); |
| 251 |
| 252 if (input_effect != *effect) { |
| 253 NodeProperties::ReplaceEffectInput(node, *effect); |
| 254 } |
| 255 |
| 256 // If the node produces an effect, update our current effect. (However, |
| 257 // ignore new effect chains started with ValueEffect.) |
| 258 if (node->op()->EffectOutputCount() > 0) { |
| 259 DCHECK_EQ(1, node->op()->EffectOutputCount()); |
| 260 *effect = node; |
| 261 } |
| 262 } else { |
| 263 // New effect chain is only started with a Start or ValueEffect node. |
| 264 DCHECK(node->op()->EffectOutputCount() == 0 || |
| 265 node->opcode() == IrOpcode::kStart); |
| 266 } |
| 267 } |
| 268 |
| 269 bool EffectControlLinearizer::TryWireInStateEffect(Node* node, Node** effect, |
| 270 Node** control) { |
| 271 ValueEffectControl state(nullptr, nullptr, nullptr); |
| 272 switch (node->opcode()) { |
| 273 case IrOpcode::kChangeInt32ToTagged: |
| 274 state = LowerChangeInt32ToTagged(node, *effect, *control); |
| 275 break; |
| 276 case IrOpcode::kChangeUint32ToTagged: |
| 277 state = LowerChangeUint32ToTagged(node, *effect, *control); |
| 278 break; |
| 279 case IrOpcode::kChangeFloat64ToTagged: |
| 280 state = LowerChangeFloat64ToTagged(node, *effect, *control); |
| 281 break; |
| 282 default: |
| 283 return false; |
| 284 } |
| 285 NodeProperties::ReplaceUses(node, state.value); |
| 286 *effect = state.effect; |
| 287 *control = state.control; |
| 288 return true; |
| 289 } |
| 290 |
| 291 EffectControlLinearizer::ValueEffectControl |
| 292 EffectControlLinearizer::LowerChangeFloat64ToTagged(Node* node, Node* effect, |
| 293 Node* control) { |
| 294 Node* value = node->InputAt(0); |
| 295 |
| 296 Type* const value_type = NodeProperties::GetType(value); |
| 297 Node* const value32 = graph()->NewNode( |
| 298 machine()->TruncateFloat64ToInt32(TruncationMode::kRoundToZero), value); |
| 299 // TODO(bmeurer): This fast case must be disabled until we kill the asm.js |
| 300 // support in the generic JavaScript pipeline, because LoadBuffer is lying |
| 301 // about its result. |
| 302 // if (value_type->Is(Type::Signed32())) { |
| 303 // return ChangeInt32ToTagged(value32, control); |
| 304 // } |
| 305 Node* check_same = graph()->NewNode( |
| 306 machine()->Float64Equal(), value, |
| 307 graph()->NewNode(machine()->ChangeInt32ToFloat64(), value32)); |
| 308 Node* branch_same = graph()->NewNode(common()->Branch(), check_same, control); |
| 309 |
| 310 Node* if_smi = graph()->NewNode(common()->IfTrue(), branch_same); |
| 311 Node* vsmi; |
| 312 Node* if_box = graph()->NewNode(common()->IfFalse(), branch_same); |
| 313 |
| 314 // We only need to check for -0 if the {value} can potentially contain -0. |
| 315 if (value_type->Maybe(Type::MinusZero())) { |
| 316 Node* check_zero = graph()->NewNode(machine()->Word32Equal(), value32, |
| 317 jsgraph()->Int32Constant(0)); |
| 318 Node* branch_zero = graph()->NewNode(common()->Branch(BranchHint::kFalse), |
| 319 check_zero, if_smi); |
| 320 |
| 321 Node* if_zero = graph()->NewNode(common()->IfTrue(), branch_zero); |
| 322 Node* if_notzero = graph()->NewNode(common()->IfFalse(), branch_zero); |
| 323 |
| 324 // In case of 0, we need to check the high bits for the IEEE -0 pattern. |
| 325 Node* check_negative = graph()->NewNode( |
| 326 machine()->Int32LessThan(), |
| 327 graph()->NewNode(machine()->Float64ExtractHighWord32(), value), |
| 328 jsgraph()->Int32Constant(0)); |
| 329 Node* branch_negative = graph()->NewNode( |
| 330 common()->Branch(BranchHint::kFalse), check_negative, if_zero); |
| 331 |
| 332 Node* if_negative = graph()->NewNode(common()->IfTrue(), branch_negative); |
| 333 Node* if_notnegative = |
| 334 graph()->NewNode(common()->IfFalse(), branch_negative); |
| 335 |
| 336 // We need to create a box for negative 0. |
| 337 if_smi = graph()->NewNode(common()->Merge(2), if_notzero, if_notnegative); |
| 338 if_box = graph()->NewNode(common()->Merge(2), if_box, if_negative); |
| 339 } |
| 340 |
| 341 // On 64-bit machines we can just wrap the 32-bit integer in a smi, for 32-bit |
| 342 // machines we need to deal with potential overflow and fallback to boxing. |
| 343 if (machine()->Is64() || value_type->Is(Type::SignedSmall())) { |
| 344 vsmi = ChangeInt32ToSmi(value32); |
| 345 } else { |
| 346 Node* smi_tag = |
| 347 graph()->NewNode(machine()->Int32AddWithOverflow(), value32, value32); |
| 348 |
| 349 Node* check_ovf = graph()->NewNode(common()->Projection(1), smi_tag); |
| 350 Node* branch_ovf = graph()->NewNode(common()->Branch(BranchHint::kFalse), |
| 351 check_ovf, if_smi); |
| 352 |
| 353 Node* if_ovf = graph()->NewNode(common()->IfTrue(), branch_ovf); |
| 354 if_box = graph()->NewNode(common()->Merge(2), if_ovf, if_box); |
| 355 |
| 356 if_smi = graph()->NewNode(common()->IfFalse(), branch_ovf); |
| 357 vsmi = graph()->NewNode(common()->Projection(0), smi_tag); |
| 358 } |
| 359 |
| 360 // Allocate the box for the {value}. |
| 361 ValueEffectControl box = AllocateHeapNumberWithValue(value, effect, if_box); |
| 362 |
| 363 control = graph()->NewNode(common()->Merge(2), if_smi, box.control); |
| 364 value = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2), |
| 365 vsmi, box.value, control); |
| 366 effect = |
| 367 graph()->NewNode(common()->EffectPhi(2), effect, box.effect, control); |
| 368 return ValueEffectControl(value, effect, control); |
| 369 } |
| 370 |
| 371 EffectControlLinearizer::ValueEffectControl |
| 372 EffectControlLinearizer::LowerChangeInt32ToTagged(Node* node, Node* effect, |
| 373 Node* control) { |
| 374 Node* value = node->InputAt(0); |
| 375 |
| 376 if (machine()->Is64() || |
| 377 NodeProperties::GetType(value)->Is(Type::SignedSmall())) { |
| 378 return ValueEffectControl(ChangeInt32ToSmi(value), effect, control); |
| 379 } |
| 380 |
| 381 Node* add = graph()->NewNode(machine()->Int32AddWithOverflow(), value, value); |
| 382 |
| 383 Node* ovf = graph()->NewNode(common()->Projection(1), add); |
| 384 Node* branch = |
| 385 graph()->NewNode(common()->Branch(BranchHint::kFalse), ovf, control); |
| 386 |
| 387 Node* if_true = graph()->NewNode(common()->IfTrue(), branch); |
| 388 ValueEffectControl alloc = |
| 389 AllocateHeapNumberWithValue(ChangeInt32ToFloat64(value), effect, if_true); |
| 390 |
| 391 Node* if_false = graph()->NewNode(common()->IfFalse(), branch); |
| 392 Node* vfalse = graph()->NewNode(common()->Projection(0), add); |
| 393 |
| 394 Node* merge = graph()->NewNode(common()->Merge(2), alloc.control, if_false); |
| 395 Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2), |
| 396 alloc.value, vfalse, merge); |
| 397 Node* ephi = |
| 398 graph()->NewNode(common()->EffectPhi(2), alloc.effect, effect, merge); |
| 399 |
| 400 return ValueEffectControl(phi, ephi, merge); |
| 401 } |
| 402 |
| 403 EffectControlLinearizer::ValueEffectControl |
| 404 EffectControlLinearizer::LowerChangeUint32ToTagged(Node* node, Node* effect, |
| 405 Node* control) { |
| 406 Node* value = node->InputAt(0); |
| 407 |
| 408 if (NodeProperties::GetType(value)->Is(Type::UnsignedSmall())) { |
| 409 return ValueEffectControl(ChangeUint32ToSmi(value), effect, control); |
| 410 } |
| 411 |
| 412 Node* check = graph()->NewNode(machine()->Uint32LessThanOrEqual(), value, |
| 413 SmiMaxValueConstant()); |
| 414 Node* branch = |
| 415 graph()->NewNode(common()->Branch(BranchHint::kTrue), check, control); |
| 416 |
| 417 Node* if_true = graph()->NewNode(common()->IfTrue(), branch); |
| 418 Node* vtrue = ChangeUint32ToSmi(value); |
| 419 |
| 420 Node* if_false = graph()->NewNode(common()->IfFalse(), branch); |
| 421 ValueEffectControl alloc = AllocateHeapNumberWithValue( |
| 422 ChangeUint32ToFloat64(value), effect, if_false); |
| 423 |
| 424 Node* merge = graph()->NewNode(common()->Merge(2), if_true, alloc.control); |
| 425 Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2), |
| 426 vtrue, alloc.value, merge); |
| 427 Node* ephi = |
| 428 graph()->NewNode(common()->EffectPhi(2), effect, alloc.effect, merge); |
| 429 |
| 430 return ValueEffectControl(phi, ephi, merge); |
| 431 } |
| 432 |
| 433 EffectControlLinearizer::ValueEffectControl |
| 434 EffectControlLinearizer::AllocateHeapNumberWithValue(Node* value, Node* effect, |
| 435 Node* control) { |
| 436 // The AllocateHeapNumberStub does not use the context, so we can safely pass |
| 437 // in Smi zero here. |
| 438 Callable callable = CodeFactory::AllocateHeapNumber(jsgraph()->isolate()); |
| 439 Node* target = jsgraph()->HeapConstant(callable.code()); |
| 440 Node* context = jsgraph()->NoContextConstant(); |
| 441 if (!allocate_heap_number_operator_.is_set()) { |
| 442 CallDescriptor* descriptor = Linkage::GetStubCallDescriptor( |
| 443 jsgraph()->isolate(), jsgraph()->zone(), callable.descriptor(), 0, |
| 444 CallDescriptor::kNoFlags, Operator::kNoThrow); |
| 445 allocate_heap_number_operator_.set(common()->Call(descriptor)); |
| 446 } |
| 447 Node* heap_number = graph()->NewNode(allocate_heap_number_operator_.get(), |
| 448 target, context, effect, control); |
| 449 Node* store = graph()->NewNode( |
| 450 machine()->Store(StoreRepresentation(MachineRepresentation::kFloat64, |
| 451 kNoWriteBarrier)), |
| 452 heap_number, HeapNumberValueIndexConstant(), value, heap_number, control); |
| 453 return ValueEffectControl(heap_number, store, control); |
| 454 } |
| 455 |
| 456 Node* EffectControlLinearizer::ChangeInt32ToSmi(Node* value) { |
| 457 if (machine()->Is64()) { |
| 458 value = graph()->NewNode(machine()->ChangeInt32ToInt64(), value); |
| 459 } |
| 460 return graph()->NewNode(machine()->WordShl(), value, SmiShiftBitsConstant()); |
| 461 } |
| 462 |
| 463 Node* EffectControlLinearizer::ChangeUint32ToSmi(Node* value) { |
| 464 if (machine()->Is64()) { |
| 465 value = graph()->NewNode(machine()->ChangeUint32ToUint64(), value); |
| 466 } |
| 467 return graph()->NewNode(machine()->WordShl(), value, SmiShiftBitsConstant()); |
| 468 } |
| 469 |
| 470 Node* EffectControlLinearizer::ChangeInt32ToFloat64(Node* value) { |
| 471 return graph()->NewNode(machine()->ChangeInt32ToFloat64(), value); |
| 472 } |
| 473 |
| 474 Node* EffectControlLinearizer::ChangeUint32ToFloat64(Node* value) { |
| 475 return graph()->NewNode(machine()->ChangeUint32ToFloat64(), value); |
| 476 } |
| 477 |
| 478 Node* EffectControlLinearizer::HeapNumberValueIndexConstant() { |
| 479 return jsgraph()->IntPtrConstant(HeapNumber::kValueOffset - kHeapObjectTag); |
| 480 } |
| 481 |
| 482 Node* EffectControlLinearizer::SmiMaxValueConstant() { |
| 483 return jsgraph()->Int32Constant(Smi::kMaxValue); |
| 484 } |
| 485 |
| 486 Node* EffectControlLinearizer::SmiShiftBitsConstant() { |
| 487 return jsgraph()->IntPtrConstant(kSmiShiftSize + kSmiTagSize); |
| 488 } |
| 489 |
| 490 } // namespace compiler |
| 491 } // namespace internal |
| 492 } // namespace v8 |
OLD | NEW |