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