| OLD | NEW |
| 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 #include "vm/flow_graph_optimizer.h" | 5 #include "vm/flow_graph_optimizer.h" |
| 6 | 6 |
| 7 #include "vm/cha.h" | 7 #include "vm/cha.h" |
| 8 #include "vm/flow_graph_builder.h" | 8 #include "vm/flow_graph_builder.h" |
| 9 #include "vm/hash_map.h" | 9 #include "vm/hash_map.h" |
| 10 #include "vm/il_printer.h" | 10 #include "vm/il_printer.h" |
| (...skipping 83 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 94 instr->AsPhi()->block()->PredecessorAt(use->use_index()); | 94 instr->AsPhi()->block()->PredecessorAt(use->use_index()); |
| 95 instr = pred->last_instruction(); | 95 instr = pred->last_instruction(); |
| 96 } else { | 96 } else { |
| 97 deopt_target = instr; | 97 deopt_target = instr; |
| 98 } | 98 } |
| 99 | 99 |
| 100 BindInstr* converted = InsertBefore( | 100 BindInstr* converted = InsertBefore( |
| 101 instr, | 101 instr, |
| 102 CreateConversion(from_rep, to_rep, def, deopt_target), | 102 CreateConversion(from_rep, to_rep, def, deopt_target), |
| 103 use->instruction()->env(), | 103 use->instruction()->env(), |
| 104 BindInstr::kUsed); | 104 Definition::kValue); |
| 105 | 105 |
| 106 use->set_definition(converted); | 106 use->set_definition(converted); |
| 107 } | 107 } |
| 108 } | 108 } |
| 109 | 109 |
| 110 void FlowGraphOptimizer::SelectRepresentations() { | 110 void FlowGraphOptimizer::SelectRepresentations() { |
| 111 // Convervatively unbox all phis that were proven to be of type Double. | 111 // Convervatively unbox all phis that were proven to be of type Double. |
| 112 for (intptr_t i = 0; i < block_order_.length(); ++i) { | 112 for (intptr_t i = 0; i < block_order_.length(); ++i) { |
| 113 JoinEntryInstr* join_entry = block_order_[i]->AsJoinEntry(); | 113 JoinEntryInstr* join_entry = block_order_[i]->AsJoinEntry(); |
| 114 if (join_entry == NULL) continue; | 114 if (join_entry == NULL) continue; |
| (...skipping 193 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 308 } | 308 } |
| 309 | 309 |
| 310 | 310 |
| 311 void FlowGraphOptimizer::AddCheckClass(BindInstr* instr, | 311 void FlowGraphOptimizer::AddCheckClass(BindInstr* instr, |
| 312 InstanceCallComp* comp, | 312 InstanceCallComp* comp, |
| 313 Value* value) { | 313 Value* value) { |
| 314 // Type propagation has not run yet, we cannot eliminate the check. | 314 // Type propagation has not run yet, we cannot eliminate the check. |
| 315 const ICData& unary_checks = | 315 const ICData& unary_checks = |
| 316 ICData::ZoneHandle(comp->ic_data()->AsUnaryClassChecks()); | 316 ICData::ZoneHandle(comp->ic_data()->AsUnaryClassChecks()); |
| 317 CheckClassComp* check = new CheckClassComp(value, comp, unary_checks); | 317 CheckClassComp* check = new CheckClassComp(value, comp, unary_checks); |
| 318 InsertBefore(instr, check, instr->env(), BindInstr::kUnused); | 318 InsertBefore(instr, check, instr->env(), Definition::kEffect); |
| 319 } | 319 } |
| 320 | 320 |
| 321 | 321 |
| 322 bool FlowGraphOptimizer::TryReplaceWithArrayOp(BindInstr* instr, | 322 bool FlowGraphOptimizer::TryReplaceWithArrayOp(BindInstr* instr, |
| 323 InstanceCallComp* comp, | 323 InstanceCallComp* comp, |
| 324 Token::Kind op_kind) { | 324 Token::Kind op_kind) { |
| 325 // TODO(fschneider): Optimize []= operator in checked mode as well. | 325 // TODO(fschneider): Optimize []= operator in checked mode as well. |
| 326 if (op_kind == Token::kASSIGN_INDEX && FLAG_enable_type_checks) return false; | 326 if (op_kind == Token::kASSIGN_INDEX && FLAG_enable_type_checks) return false; |
| 327 | 327 |
| 328 const intptr_t class_id = ReceiverClassId(comp); | 328 const intptr_t class_id = ReceiverClassId(comp); |
| 329 switch (class_id) { | 329 switch (class_id) { |
| 330 case kImmutableArrayCid: | 330 case kImmutableArrayCid: |
| 331 // Stores are only specialized for Array and GrowableObjectArray, | 331 // Stores are only specialized for Array and GrowableObjectArray, |
| 332 // not for ImmutableArray. | 332 // not for ImmutableArray. |
| 333 if (op_kind == Token::kASSIGN_INDEX) return false; | 333 if (op_kind == Token::kASSIGN_INDEX) return false; |
| 334 // Fall through. | 334 // Fall through. |
| 335 case kArrayCid: | 335 case kArrayCid: |
| 336 case kGrowableObjectArrayCid: { | 336 case kGrowableObjectArrayCid: { |
| 337 Value* array = comp->ArgumentAt(0)->value(); | 337 Value* array = comp->ArgumentAt(0)->value(); |
| 338 Value* index = comp->ArgumentAt(1)->value(); | 338 Value* index = comp->ArgumentAt(1)->value(); |
| 339 // Insert class check and index smi checks and attach a copy of the | 339 // Insert class check and index smi checks and attach a copy of the |
| 340 // original environment because the operation can still deoptimize. | 340 // original environment because the operation can still deoptimize. |
| 341 AddCheckClass(instr, comp, array->Copy()); | 341 AddCheckClass(instr, comp, array->Copy()); |
| 342 InsertBefore(instr, | 342 InsertBefore(instr, |
| 343 new CheckSmiComp(index->Copy(), comp->deopt_id()), | 343 new CheckSmiComp(index->Copy(), comp->deopt_id()), |
| 344 instr->env(), | 344 instr->env(), |
| 345 BindInstr::kUnused); | 345 Definition::kEffect); |
| 346 // Insert array bounds check. | 346 // Insert array bounds check. |
| 347 InsertBefore(instr, | 347 InsertBefore(instr, |
| 348 new CheckArrayBoundComp(array->Copy(), | 348 new CheckArrayBoundComp(array->Copy(), |
| 349 index->Copy(), | 349 index->Copy(), |
| 350 class_id, | 350 class_id, |
| 351 comp), | 351 comp), |
| 352 instr->env(), | 352 instr->env(), |
| 353 BindInstr::kUnused); | 353 Definition::kEffect); |
| 354 Computation* array_op = NULL; | 354 Computation* array_op = NULL; |
| 355 if (op_kind == Token::kINDEX) { | 355 if (op_kind == Token::kINDEX) { |
| 356 array_op = new LoadIndexedComp(array, index, class_id); | 356 array_op = new LoadIndexedComp(array, index, class_id); |
| 357 } else { | 357 } else { |
| 358 Value* value = comp->ArgumentAt(2)->value(); | 358 Value* value = comp->ArgumentAt(2)->value(); |
| 359 array_op = new StoreIndexedComp(array, index, value, class_id); | 359 array_op = new StoreIndexedComp(array, index, value, class_id); |
| 360 } | 360 } |
| 361 instr->set_computation(array_op); | 361 instr->set_computation(array_op); |
| 362 RemovePushArguments(comp); | 362 RemovePushArguments(comp); |
| 363 return true; | 363 return true; |
| 364 } | 364 } |
| 365 default: | 365 default: |
| 366 return false; | 366 return false; |
| 367 } | 367 } |
| 368 } | 368 } |
| 369 | 369 |
| 370 | 370 |
| 371 BindInstr* FlowGraphOptimizer::InsertBefore(Instruction* instr, | 371 BindInstr* FlowGraphOptimizer::InsertBefore(Instruction* instr, |
| 372 Computation* comp, | 372 Computation* comp, |
| 373 Environment* env, | 373 Environment* env, |
| 374 BindInstr::UseKind use_kind) { | 374 BindInstr::UseKind use_kind) { |
| 375 BindInstr* bind = new BindInstr(use_kind, comp); | 375 BindInstr* bind = new BindInstr(use_kind, comp); |
| 376 if (env != NULL) env->CopyTo(bind); | 376 if (env != NULL) env->CopyTo(bind); |
| 377 if (use_kind == BindInstr::kUsed) { | 377 if (use_kind == Definition::kValue) { |
| 378 bind->set_ssa_temp_index(flow_graph_->alloc_ssa_temp_index()); | 378 bind->set_ssa_temp_index(flow_graph_->alloc_ssa_temp_index()); |
| 379 } | 379 } |
| 380 bind->InsertBefore(instr); | 380 bind->InsertBefore(instr); |
| 381 return bind; | 381 return bind; |
| 382 } | 382 } |
| 383 | 383 |
| 384 | 384 |
| 385 BindInstr* FlowGraphOptimizer::InsertAfter(Instruction* instr, | 385 BindInstr* FlowGraphOptimizer::InsertAfter(Instruction* instr, |
| 386 Computation* comp, | 386 Computation* comp, |
| 387 Environment* env, | 387 Environment* env, |
| 388 BindInstr::UseKind use_kind) { | 388 BindInstr::UseKind use_kind) { |
| 389 BindInstr* bind = new BindInstr(use_kind, comp); | 389 BindInstr* bind = new BindInstr(use_kind, comp); |
| 390 if (env != NULL) env->CopyTo(bind); | 390 if (env != NULL) env->CopyTo(bind); |
| 391 if (use_kind == BindInstr::kUsed) { | 391 if (use_kind == Definition::kValue) { |
| 392 bind->set_ssa_temp_index(flow_graph_->alloc_ssa_temp_index()); | 392 bind->set_ssa_temp_index(flow_graph_->alloc_ssa_temp_index()); |
| 393 } | 393 } |
| 394 bind->InsertAfter(instr); | 394 bind->InsertAfter(instr); |
| 395 return bind; | 395 return bind; |
| 396 } | 396 } |
| 397 | 397 |
| 398 | 398 |
| 399 bool FlowGraphOptimizer::TryReplaceWithBinaryOp(BindInstr* instr, | 399 bool FlowGraphOptimizer::TryReplaceWithBinaryOp(BindInstr* instr, |
| 400 InstanceCallComp* comp, | 400 InstanceCallComp* comp, |
| 401 Token::Kind op_kind) { | 401 Token::Kind op_kind) { |
| (...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 454 Value* left = comp->ArgumentAt(0)->value(); | 454 Value* left = comp->ArgumentAt(0)->value(); |
| 455 Value* right = comp->ArgumentAt(1)->value(); | 455 Value* right = comp->ArgumentAt(1)->value(); |
| 456 | 456 |
| 457 // Check that either left or right are not a smi. Result or a | 457 // Check that either left or right are not a smi. Result or a |
| 458 // binary operation with two smis is a smi not a double. | 458 // binary operation with two smis is a smi not a double. |
| 459 InsertBefore(instr, | 459 InsertBefore(instr, |
| 460 new CheckEitherNonSmiComp(left->Copy(), | 460 new CheckEitherNonSmiComp(left->Copy(), |
| 461 right->Copy(), | 461 right->Copy(), |
| 462 comp), | 462 comp), |
| 463 instr->env(), | 463 instr->env(), |
| 464 BindInstr::kUnused); | 464 Definition::kEffect); |
| 465 | 465 |
| 466 UnboxedDoubleBinaryOpComp* double_bin_op = | 466 UnboxedDoubleBinaryOpComp* double_bin_op = |
| 467 new UnboxedDoubleBinaryOpComp(op_kind, | 467 new UnboxedDoubleBinaryOpComp(op_kind, |
| 468 left->Copy(), | 468 left->Copy(), |
| 469 right->Copy(), | 469 right->Copy(), |
| 470 comp); | 470 comp); |
| 471 instr->set_computation(double_bin_op); | 471 instr->set_computation(double_bin_op); |
| 472 | 472 |
| 473 RemovePushArguments(comp); | 473 RemovePushArguments(comp); |
| 474 } else { | 474 } else { |
| (...skipping 11 matching lines...) Expand all Loading... |
| 486 RemovePushArguments(comp); | 486 RemovePushArguments(comp); |
| 487 } else { | 487 } else { |
| 488 ASSERT(operands_type == kSmiCid); | 488 ASSERT(operands_type == kSmiCid); |
| 489 Value* left = comp->ArgumentAt(0)->value(); | 489 Value* left = comp->ArgumentAt(0)->value(); |
| 490 Value* right = comp->ArgumentAt(1)->value(); | 490 Value* right = comp->ArgumentAt(1)->value(); |
| 491 // Insert two smi checks and attach a copy of the original | 491 // Insert two smi checks and attach a copy of the original |
| 492 // environment because the smi operation can still deoptimize. | 492 // environment because the smi operation can still deoptimize. |
| 493 InsertBefore(instr, | 493 InsertBefore(instr, |
| 494 new CheckSmiComp(left->Copy(), comp->deopt_id()), | 494 new CheckSmiComp(left->Copy(), comp->deopt_id()), |
| 495 instr->env(), | 495 instr->env(), |
| 496 BindInstr::kUnused); | 496 Definition::kEffect); |
| 497 InsertBefore(instr, | 497 InsertBefore(instr, |
| 498 new CheckSmiComp(right->Copy(), comp->deopt_id()), | 498 new CheckSmiComp(right->Copy(), comp->deopt_id()), |
| 499 instr->env(), | 499 instr->env(), |
| 500 BindInstr::kUnused); | 500 Definition::kEffect); |
| 501 BinarySmiOpComp* bin_op = new BinarySmiOpComp(op_kind, | 501 BinarySmiOpComp* bin_op = new BinarySmiOpComp(op_kind, |
| 502 comp, | 502 comp, |
| 503 left, | 503 left, |
| 504 right); | 504 right); |
| 505 instr->set_computation(bin_op); | 505 instr->set_computation(bin_op); |
| 506 RemovePushArguments(comp); | 506 RemovePushArguments(comp); |
| 507 } | 507 } |
| 508 return true; | 508 return true; |
| 509 } | 509 } |
| 510 | 510 |
| 511 | 511 |
| 512 bool FlowGraphOptimizer::TryReplaceWithUnaryOp(BindInstr* instr, | 512 bool FlowGraphOptimizer::TryReplaceWithUnaryOp(BindInstr* instr, |
| 513 InstanceCallComp* comp, | 513 InstanceCallComp* comp, |
| 514 Token::Kind op_kind) { | 514 Token::Kind op_kind) { |
| 515 if (comp->ic_data()->NumberOfChecks() != 1) { | 515 if (comp->ic_data()->NumberOfChecks() != 1) { |
| 516 // TODO(srdjan): Not yet supported. | 516 // TODO(srdjan): Not yet supported. |
| 517 return false; | 517 return false; |
| 518 } | 518 } |
| 519 ASSERT(comp->ArgumentCount() == 1); | 519 ASSERT(comp->ArgumentCount() == 1); |
| 520 Computation* unary_op = NULL; | 520 Computation* unary_op = NULL; |
| 521 if (HasOneSmi(*comp->ic_data())) { | 521 if (HasOneSmi(*comp->ic_data())) { |
| 522 Value* value = comp->ArgumentAt(0)->value(); | 522 Value* value = comp->ArgumentAt(0)->value(); |
| 523 InsertBefore(instr, | 523 InsertBefore(instr, |
| 524 new CheckSmiComp(value->Copy(), comp->deopt_id()), | 524 new CheckSmiComp(value->Copy(), comp->deopt_id()), |
| 525 instr->env(), | 525 instr->env(), |
| 526 BindInstr::kUnused); | 526 Definition::kEffect); |
| 527 unary_op = new UnarySmiOpComp(op_kind, | 527 unary_op = new UnarySmiOpComp(op_kind, |
| 528 (op_kind == Token::kNEGATE) ? comp : NULL, | 528 (op_kind == Token::kNEGATE) ? comp : NULL, |
| 529 value); | 529 value); |
| 530 } else if (HasOneDouble(*comp->ic_data()) && (op_kind == Token::kNEGATE)) { | 530 } else if (HasOneDouble(*comp->ic_data()) && (op_kind == Token::kNEGATE)) { |
| 531 unary_op = new NumberNegateComp(comp, comp->ArgumentAt(0)->value()); | 531 unary_op = new NumberNegateComp(comp, comp->ArgumentAt(0)->value()); |
| 532 } | 532 } |
| 533 if (unary_op == NULL) return false; | 533 if (unary_op == NULL) return false; |
| 534 | 534 |
| 535 instr->set_computation(unary_op); | 535 instr->set_computation(unary_op); |
| 536 RemovePushArguments(comp); | 536 RemovePushArguments(comp); |
| (...skipping 263 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 800 if (ic_data.NumberOfChecks() == 0) return; | 800 if (ic_data.NumberOfChecks() == 0) return; |
| 801 // TODO(srdjan): Add multiple receiver type support. | 801 // TODO(srdjan): Add multiple receiver type support. |
| 802 if (ic_data.NumberOfChecks() != 1) return; | 802 if (ic_data.NumberOfChecks() != 1) return; |
| 803 ASSERT(HasOneTarget(ic_data)); | 803 ASSERT(HasOneTarget(ic_data)); |
| 804 | 804 |
| 805 if (HasOnlyTwoSmi(ic_data)) { | 805 if (HasOnlyTwoSmi(ic_data)) { |
| 806 optimizer->InsertBefore( | 806 optimizer->InsertBefore( |
| 807 instr, | 807 instr, |
| 808 new CheckSmiComp(comp->left()->Copy(), comp->deopt_id()), | 808 new CheckSmiComp(comp->left()->Copy(), comp->deopt_id()), |
| 809 instr->env(), | 809 instr->env(), |
| 810 BindInstr::kUnused); | 810 Definition::kEffect); |
| 811 optimizer->InsertBefore( | 811 optimizer->InsertBefore( |
| 812 instr, | 812 instr, |
| 813 new CheckSmiComp(comp->right()->Copy(), comp->deopt_id()), | 813 new CheckSmiComp(comp->right()->Copy(), comp->deopt_id()), |
| 814 instr->env(), | 814 instr->env(), |
| 815 BindInstr::kUnused); | 815 Definition::kEffect); |
| 816 comp->set_operands_class_id(kSmiCid); | 816 comp->set_operands_class_id(kSmiCid); |
| 817 } else if (ShouldSpecializeForDouble(ic_data)) { | 817 } else if (ShouldSpecializeForDouble(ic_data)) { |
| 818 comp->set_operands_class_id(kDoubleCid); | 818 comp->set_operands_class_id(kDoubleCid); |
| 819 } else if (comp->ic_data()->AllReceiversAreNumbers()) { | 819 } else if (comp->ic_data()->AllReceiversAreNumbers()) { |
| 820 comp->set_operands_class_id(kNumberCid); | 820 comp->set_operands_class_id(kNumberCid); |
| 821 } | 821 } |
| 822 } | 822 } |
| 823 | 823 |
| 824 void FlowGraphOptimizer::VisitRelationalOp(RelationalOpComp* comp, | 824 void FlowGraphOptimizer::VisitRelationalOp(RelationalOpComp* comp, |
| 825 BindInstr* instr) { | 825 BindInstr* instr) { |
| (...skipping 22 matching lines...) Expand all Loading... |
| 848 ASSERT(comp->ic_data()->num_args_tested() == 2); | 848 ASSERT(comp->ic_data()->num_args_tested() == 2); |
| 849 GrowableArray<intptr_t> class_ids; | 849 GrowableArray<intptr_t> class_ids; |
| 850 Function& target = Function::Handle(); | 850 Function& target = Function::Handle(); |
| 851 comp->ic_data()->GetCheckAt(0, &class_ids, &target); | 851 comp->ic_data()->GetCheckAt(0, &class_ids, &target); |
| 852 // TODO(srdjan): allow for mixed mode comparison. | 852 // TODO(srdjan): allow for mixed mode comparison. |
| 853 if ((class_ids[0] == kSmiCid) && (class_ids[1] == kSmiCid)) { | 853 if ((class_ids[0] == kSmiCid) && (class_ids[1] == kSmiCid)) { |
| 854 optimizer->InsertBefore( | 854 optimizer->InsertBefore( |
| 855 instr, | 855 instr, |
| 856 new CheckSmiComp(comp->left()->Copy(), comp->deopt_id()), | 856 new CheckSmiComp(comp->left()->Copy(), comp->deopt_id()), |
| 857 instr->env(), | 857 instr->env(), |
| 858 BindInstr::kUnused); | 858 Definition::kEffect); |
| 859 optimizer->InsertBefore( | 859 optimizer->InsertBefore( |
| 860 instr, | 860 instr, |
| 861 new CheckSmiComp(comp->right()->Copy(), comp->deopt_id()), | 861 new CheckSmiComp(comp->right()->Copy(), comp->deopt_id()), |
| 862 instr->env(), | 862 instr->env(), |
| 863 BindInstr::kUnused); | 863 Definition::kEffect); |
| 864 comp->set_receiver_class_id(kSmiCid); | 864 comp->set_receiver_class_id(kSmiCid); |
| 865 } else if ((class_ids[0] == kDoubleCid) && (class_ids[1] == kDoubleCid)) { | 865 } else if ((class_ids[0] == kDoubleCid) && (class_ids[1] == kDoubleCid)) { |
| 866 comp->set_receiver_class_id(kDoubleCid); | 866 comp->set_receiver_class_id(kDoubleCid); |
| 867 } else { | 867 } else { |
| 868 ASSERT(comp->receiver_class_id() == kIllegalCid); | 868 ASSERT(comp->receiver_class_id() == kIllegalCid); |
| 869 } | 869 } |
| 870 } else if (comp->ic_data()->AllReceiversAreNumbers()) { | 870 } else if (comp->ic_data()->AllReceiversAreNumbers()) { |
| 871 comp->set_receiver_class_id(kNumberCid); | 871 comp->set_receiver_class_id(kNumberCid); |
| 872 } | 872 } |
| 873 } | 873 } |
| (...skipping 331 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1205 DirectChainedHashMap<BindInstr*> child_map(*map); // Copy map. | 1205 DirectChainedHashMap<BindInstr*> child_map(*map); // Copy map. |
| 1206 OptimizeRecursive(child, &child_map); | 1206 OptimizeRecursive(child, &child_map); |
| 1207 } else { | 1207 } else { |
| 1208 OptimizeRecursive(child, map); // Reuse map for the last child. | 1208 OptimizeRecursive(child, map); // Reuse map for the last child. |
| 1209 } | 1209 } |
| 1210 } | 1210 } |
| 1211 } | 1211 } |
| 1212 | 1212 |
| 1213 | 1213 |
| 1214 } // namespace dart | 1214 } // namespace dart |
| OLD | NEW |