| 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/flow_graph_builder.h" | 7 #include "vm/flow_graph_builder.h" |
| 8 #include "vm/il_printer.h" | 8 #include "vm/il_printer.h" |
| 9 #include "vm/object_store.h" | 9 #include "vm/object_store.h" |
| 10 | 10 |
| (...skipping 19 matching lines...) Expand all Loading... |
| 30 // Optimize all successors until an exit, branch, or a block entry. | 30 // Optimize all successors until an exit, branch, or a block entry. |
| 31 while ((instr != NULL) && !instr->IsBlockEntry()) { | 31 while ((instr != NULL) && !instr->IsBlockEntry()) { |
| 32 instr = instr->Accept(this); | 32 instr = instr->Accept(this); |
| 33 } | 33 } |
| 34 } | 34 } |
| 35 } | 35 } |
| 36 | 36 |
| 37 | 37 |
| 38 static bool ICDataHasReceiverClass(const ICData& ic_data, intptr_t class_id) { | 38 static bool ICDataHasReceiverClass(const ICData& ic_data, intptr_t class_id) { |
| 39 ASSERT(ic_data.num_args_tested() > 0); | 39 ASSERT(ic_data.num_args_tested() > 0); |
| 40 Class& test_class = Class::Handle(); | |
| 41 Function& target = Function::Handle(); | 40 Function& target = Function::Handle(); |
| 42 for (intptr_t i = 0; i < ic_data.NumberOfChecks(); i++) { | 41 for (intptr_t i = 0; i < ic_data.NumberOfChecks(); i++) { |
| 43 ic_data.GetOneClassCheckAt(i, &test_class, &target); | 42 intptr_t test_class_id; |
| 44 if (test_class.id() == class_id) { | 43 ic_data.GetOneClassCheckAt(i, &test_class_id, &target); |
| 44 if (test_class_id == class_id) { |
| 45 return true; | 45 return true; |
| 46 } | 46 } |
| 47 } | 47 } |
| 48 return false; | 48 return false; |
| 49 } | 49 } |
| 50 | 50 |
| 51 | 51 |
| 52 static bool ICDataHasReceiverArgumentClasses(const ICData& ic_data, | 52 static bool ICDataHasReceiverArgumentClasses(const ICData& ic_data, |
| 53 intptr_t receiver_class_id, | 53 intptr_t receiver_class_id, |
| 54 intptr_t argument_class_id) { | 54 intptr_t argument_class_id) { |
| 55 if (ic_data.num_args_tested() != 2) { | 55 if (ic_data.num_args_tested() != 2) { |
| 56 return false; | 56 return false; |
| 57 } | 57 } |
| 58 Function& target = Function::Handle(); | 58 Function& target = Function::Handle(); |
| 59 for (intptr_t i = 0; i < ic_data.NumberOfChecks(); i++) { | 59 for (intptr_t i = 0; i < ic_data.NumberOfChecks(); i++) { |
| 60 GrowableArray<const Class*> classes; | 60 GrowableArray<intptr_t> class_ids; |
| 61 ic_data.GetCheckAt(i, &classes, &target); | 61 ic_data.GetCheckAt(i, &class_ids, &target); |
| 62 ASSERT(classes.length() == 2); | 62 ASSERT(class_ids.length() == 2); |
| 63 if (classes[0]->id() == receiver_class_id) { | 63 if (class_ids[0] == receiver_class_id) { |
| 64 if (classes[1]->id() == argument_class_id) { | 64 if (class_ids[1] == argument_class_id) { |
| 65 return true; | 65 return true; |
| 66 } | 66 } |
| 67 } | 67 } |
| 68 } | 68 } |
| 69 return false; | 69 return false; |
| 70 } | 70 } |
| 71 | 71 |
| 72 | 72 |
| 73 static bool HasOneSmi(const ICData& ic_data) { | 73 static bool HasOneSmi(const ICData& ic_data) { |
| 74 return ICDataHasReceiverClass(ic_data, kSmi); | 74 return ICDataHasReceiverClass(ic_data, kSmi); |
| (...skipping 100 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 175 } | 175 } |
| 176 return false; | 176 return false; |
| 177 } | 177 } |
| 178 | 178 |
| 179 | 179 |
| 180 // Returns true if all targets are the same. | 180 // Returns true if all targets are the same. |
| 181 // TODO(srdjan): if targets are native use their C_function to compare. | 181 // TODO(srdjan): if targets are native use their C_function to compare. |
| 182 static bool HasOneTarget(const ICData& ic_data) { | 182 static bool HasOneTarget(const ICData& ic_data) { |
| 183 ASSERT(ic_data.NumberOfChecks() > 0); | 183 ASSERT(ic_data.NumberOfChecks() > 0); |
| 184 Function& prev_target = Function::Handle(); | 184 Function& prev_target = Function::Handle(); |
| 185 GrowableArray<const Class*> classes; | 185 GrowableArray<intptr_t> class_ids; |
| 186 ic_data.GetCheckAt(0, &classes, &prev_target); | 186 ic_data.GetCheckAt(0, &class_ids, &prev_target); |
| 187 ASSERT(!prev_target.IsNull()); | 187 ASSERT(!prev_target.IsNull()); |
| 188 Function& target = Function::Handle(); | 188 Function& target = Function::Handle(); |
| 189 for (intptr_t i = 1; i < ic_data.NumberOfChecks(); i++) { | 189 for (intptr_t i = 1; i < ic_data.NumberOfChecks(); i++) { |
| 190 ic_data.GetCheckAt(i, &classes, &target); | 190 ic_data.GetCheckAt(i, &class_ids, &target); |
| 191 ASSERT(!target.IsNull()); | 191 ASSERT(!target.IsNull()); |
| 192 if (prev_target.raw() != target.raw()) { | 192 if (prev_target.raw() != target.raw()) { |
| 193 return false; | 193 return false; |
| 194 } | 194 } |
| 195 prev_target = target.raw(); | 195 prev_target = target.raw(); |
| 196 } | 196 } |
| 197 return true; | 197 return true; |
| 198 } | 198 } |
| 199 | 199 |
| 200 | 200 |
| 201 // Using field class | 201 // Using field class |
| 202 static RawField* GetField(const Class& field_class, const String& field_name) { | 202 static RawField* GetField(intptr_t class_id, const String& field_name) { |
| 203 Class& cls = Class::Handle(field_class.raw()); | 203 Class& cls = Class::Handle(Isolate::Current()->class_table()->At(class_id)); |
| 204 Field& field = Field::Handle(); | 204 Field& field = Field::Handle(); |
| 205 while (!cls.IsNull()) { | 205 while (!cls.IsNull()) { |
| 206 field = cls.LookupInstanceField(field_name); | 206 field = cls.LookupInstanceField(field_name); |
| 207 if (!field.IsNull()) { | 207 if (!field.IsNull()) { |
| 208 return field.raw(); | 208 return field.raw(); |
| 209 } | 209 } |
| 210 cls = cls.SuperClass(); | 210 cls = cls.SuperClass(); |
| 211 } | 211 } |
| 212 return Field::null(); | 212 return Field::null(); |
| 213 } | 213 } |
| 214 | 214 |
| 215 | 215 |
| 216 // Returns all receiver class-ids and corresponding tagets for the given | 216 // Returns all receiver class-ids and corresponding tagets for the given |
| 217 // 'ic_data', sorted so that a smi class id is at index[0] if it exists. | 217 // 'ic_data', sorted so that a smi class id is at index[0] if it exists. |
| 218 // 'targets' can be NULL in which case it is not collected, | 218 // 'targets' can be NULL in which case it is not collected, |
| 219 static void ExtractClassIdsAndTargets(const ICData& ic_data, | 219 static void ExtractClassIdsAndTargets(const ICData& ic_data, |
| 220 ZoneGrowableArray<intptr_t>* class_ids, | 220 ZoneGrowableArray<intptr_t>* class_ids, |
| 221 ZoneGrowableArray<Function*>* targets) { | 221 ZoneGrowableArray<Function*>* targets) { |
| 222 ASSERT(class_ids != NULL); | 222 ASSERT(class_ids != NULL); |
| 223 class_ids->Clear(); | 223 class_ids->Clear(); |
| 224 if (targets != NULL) { | 224 if (targets != NULL) { |
| 225 targets->Clear(); | 225 targets->Clear(); |
| 226 } | 226 } |
| 227 intptr_t smi_index = -1; | 227 intptr_t smi_index = -1; |
| 228 Function& target = Function::Handle(); | 228 Function& target = Function::Handle(); |
| 229 GrowableArray<const Class*> classes; | 229 GrowableArray<intptr_t> unsorted_class_ids; |
| 230 for (intptr_t i = 0; i < ic_data.NumberOfChecks(); i++) { | 230 for (intptr_t i = 0; i < ic_data.NumberOfChecks(); i++) { |
| 231 ic_data.GetCheckAt(i, &classes, &target); | 231 ic_data.GetCheckAt(i, &unsorted_class_ids, &target); |
| 232 // Collect receiver class only. | 232 // Collect receiver class only. |
| 233 const intptr_t class_id = (*classes[0]).id(); | 233 const intptr_t class_id = unsorted_class_ids[0]; |
| 234 if (ic_data.num_args_tested() > 1) { | 234 if (ic_data.num_args_tested() > 1) { |
| 235 // Check if we have not already entered the class-id. | 235 // Check if we have not already entered the class-id. |
| 236 intptr_t duplicate_class_id = -1; | 236 intptr_t duplicate_class_id = -1; |
| 237 for (intptr_t k = 0; k < class_ids->length(); k++) { | 237 for (intptr_t k = 0; k < class_ids->length(); k++) { |
| 238 if ((*class_ids)[k] == class_id) { | 238 if ((*class_ids)[k] == class_id) { |
| 239 duplicate_class_id = k; | 239 duplicate_class_id = k; |
| 240 break; | 240 break; |
| 241 } | 241 } |
| 242 } | 242 } |
| 243 if (duplicate_class_id >= 0) { | 243 if (duplicate_class_id >= 0) { |
| (...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 282 | 282 |
| 283 // Only unique implicit instance getters can be currently handled. | 283 // Only unique implicit instance getters can be currently handled. |
| 284 bool FlowGraphOptimizer::TryInlineInstanceGetter(InstanceCallComp* comp) { | 284 bool FlowGraphOptimizer::TryInlineInstanceGetter(InstanceCallComp* comp) { |
| 285 ASSERT(comp->HasICData()); | 285 ASSERT(comp->HasICData()); |
| 286 const ICData& ic_data = *comp->ic_data(); | 286 const ICData& ic_data = *comp->ic_data(); |
| 287 if (ic_data.NumberOfChecks() == 0) { | 287 if (ic_data.NumberOfChecks() == 0) { |
| 288 // No type feedback collected. | 288 // No type feedback collected. |
| 289 return false; | 289 return false; |
| 290 } | 290 } |
| 291 Function& target = Function::Handle(); | 291 Function& target = Function::Handle(); |
| 292 GrowableArray<const Class*> classes; | 292 GrowableArray<intptr_t> class_ids; |
| 293 ic_data.GetCheckAt(0, &classes, &target); | 293 ic_data.GetCheckAt(0, &class_ids, &target); |
| 294 ASSERT(classes.length() == 1); | 294 ASSERT(class_ids.length() == 1); |
| 295 | 295 |
| 296 if (target.kind() == RawFunction::kImplicitGetter) { | 296 if (target.kind() == RawFunction::kImplicitGetter) { |
| 297 if (!HasOneTarget(ic_data)) { | 297 if (!HasOneTarget(ic_data)) { |
| 298 // TODO(srdjan): Implement for mutiple targets. | 298 // TODO(srdjan): Implement for mutiple targets. |
| 299 return false; | 299 return false; |
| 300 } | 300 } |
| 301 // Inline implicit instance getter. | 301 // Inline implicit instance getter. |
| 302 const String& field_name = | 302 const String& field_name = |
| 303 String::Handle(Field::NameFromGetter(comp->function_name())); | 303 String::Handle(Field::NameFromGetter(comp->function_name())); |
| 304 const Field& field = Field::Handle(GetField(*classes[0], field_name)); | 304 const Field& field = Field::Handle(GetField(class_ids[0], field_name)); |
| 305 ASSERT(!field.IsNull()); | 305 ASSERT(!field.IsNull()); |
| 306 LoadInstanceFieldComp* load = new LoadInstanceFieldComp( | 306 LoadInstanceFieldComp* load = new LoadInstanceFieldComp( |
| 307 field, comp->InputAt(0), comp, ExtractClassIds(ic_data)); | 307 field, comp->InputAt(0), comp, ExtractClassIds(ic_data)); |
| 308 comp->ReplaceWith(load); | 308 comp->ReplaceWith(load); |
| 309 return true; | 309 return true; |
| 310 } | 310 } |
| 311 | 311 |
| 312 // Not an implicit getter. | 312 // Not an implicit getter. |
| 313 MethodRecognizer::Kind recognized_kind = | 313 MethodRecognizer::Kind recognized_kind = |
| 314 MethodRecognizer::RecognizeKind(target); | 314 MethodRecognizer::RecognizeKind(target); |
| (...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 360 | 360 |
| 361 // Inline only simple, frequently called core library methods. | 361 // Inline only simple, frequently called core library methods. |
| 362 bool FlowGraphOptimizer::TryInlineInstanceMethod(InstanceCallComp* comp) { | 362 bool FlowGraphOptimizer::TryInlineInstanceMethod(InstanceCallComp* comp) { |
| 363 ASSERT(comp->HasICData()); | 363 ASSERT(comp->HasICData()); |
| 364 const ICData& ic_data = *comp->ic_data(); | 364 const ICData& ic_data = *comp->ic_data(); |
| 365 if ((ic_data.NumberOfChecks() == 0) || !HasOneTarget(ic_data)) { | 365 if ((ic_data.NumberOfChecks() == 0) || !HasOneTarget(ic_data)) { |
| 366 // No type feedback collected. | 366 // No type feedback collected. |
| 367 return false; | 367 return false; |
| 368 } | 368 } |
| 369 Function& target = Function::Handle(); | 369 Function& target = Function::Handle(); |
| 370 GrowableArray<const Class*> classes; | 370 GrowableArray<intptr_t> class_ids; |
| 371 ic_data.GetCheckAt(0, &classes, &target); | 371 ic_data.GetCheckAt(0, &class_ids, &target); |
| 372 MethodRecognizer::Kind recognized_kind = | 372 MethodRecognizer::Kind recognized_kind = |
| 373 MethodRecognizer::RecognizeKind(target); | 373 MethodRecognizer::RecognizeKind(target); |
| 374 | 374 |
| 375 ObjectKind from_kind; | 375 ObjectKind from_kind; |
| 376 if (recognized_kind == MethodRecognizer::kDoubleToDouble) { | 376 if (recognized_kind == MethodRecognizer::kDoubleToDouble) { |
| 377 from_kind = kDouble; | 377 from_kind = kDouble; |
| 378 } else if (recognized_kind == MethodRecognizer::kIntegerToDouble) { | 378 } else if (recognized_kind == MethodRecognizer::kIntegerToDouble) { |
| 379 from_kind = kSmi; | 379 from_kind = kSmi; |
| 380 } else { | 380 } else { |
| 381 return false; | 381 return false; |
| 382 } | 382 } |
| 383 | 383 |
| 384 if (classes[0]->id() != from_kind) { | 384 if (class_ids[0] != from_kind) { |
| 385 return false; | 385 return false; |
| 386 } | 386 } |
| 387 ToDoubleComp* coerce = new ToDoubleComp( | 387 ToDoubleComp* coerce = new ToDoubleComp( |
| 388 comp->InputAt(0), from_kind, comp); | 388 comp->InputAt(0), from_kind, comp); |
| 389 coerce->set_instr(comp->instr()); | 389 coerce->set_instr(comp->instr()); |
| 390 comp->instr()->replace_computation(coerce); | 390 comp->instr()->replace_computation(coerce); |
| 391 return true; | 391 return true; |
| 392 } | 392 } |
| 393 | 393 |
| 394 | 394 |
| (...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 439 const ICData& ic_data = *comp->ic_data(); | 439 const ICData& ic_data = *comp->ic_data(); |
| 440 if (ic_data.NumberOfChecks() == 0) { | 440 if (ic_data.NumberOfChecks() == 0) { |
| 441 // No type feedback collected. | 441 // No type feedback collected. |
| 442 return false; | 442 return false; |
| 443 } | 443 } |
| 444 if (!HasOneTarget(ic_data)) { | 444 if (!HasOneTarget(ic_data)) { |
| 445 // TODO(srdjan): Implement when not all targets are the sa,e. | 445 // TODO(srdjan): Implement when not all targets are the sa,e. |
| 446 return false; | 446 return false; |
| 447 } | 447 } |
| 448 Function& target = Function::Handle(); | 448 Function& target = Function::Handle(); |
| 449 Class& cls = Class::Handle(); | 449 intptr_t class_id; |
| 450 ic_data.GetOneClassCheckAt(0, &cls, &target); | 450 ic_data.GetOneClassCheckAt(0, &class_id, &target); |
| 451 if (target.kind() != RawFunction::kImplicitSetter) { | 451 if (target.kind() != RawFunction::kImplicitSetter) { |
| 452 // Not an implicit setter. | 452 // Not an implicit setter. |
| 453 // TODO(srdjan): Inline special setters. | 453 // TODO(srdjan): Inline special setters. |
| 454 return false; | 454 return false; |
| 455 } | 455 } |
| 456 // Inline implicit instance setter. | 456 // Inline implicit instance setter. |
| 457 const Field& field = Field::Handle(GetField(cls, comp->field_name())); | 457 const Field& field = Field::Handle(GetField(class_id, comp->field_name())); |
| 458 ASSERT(!field.IsNull()); | 458 ASSERT(!field.IsNull()); |
| 459 StoreInstanceFieldComp* store = new StoreInstanceFieldComp( | 459 StoreInstanceFieldComp* store = new StoreInstanceFieldComp( |
| 460 field, | 460 field, |
| 461 comp->InputAt(0), | 461 comp->InputAt(0), |
| 462 comp->InputAt(1), | 462 comp->InputAt(1), |
| 463 comp, | 463 comp, |
| 464 ExtractClassIds(ic_data)); | 464 ExtractClassIds(ic_data)); |
| 465 comp->ReplaceWith(store); | 465 comp->ReplaceWith(store); |
| 466 return true; | 466 return true; |
| 467 } | 467 } |
| (...skipping 18 matching lines...) Expand all Loading... |
| 486 if (!comp->HasICData()) return kIllegalObjectKind; | 486 if (!comp->HasICData()) return kIllegalObjectKind; |
| 487 | 487 |
| 488 const ICData& ic_data = *comp->ic_data(); | 488 const ICData& ic_data = *comp->ic_data(); |
| 489 | 489 |
| 490 if (ic_data.NumberOfChecks() == 0) return kIllegalObjectKind; | 490 if (ic_data.NumberOfChecks() == 0) return kIllegalObjectKind; |
| 491 // TODO(vegorov): Add multiple receiver type support. | 491 // TODO(vegorov): Add multiple receiver type support. |
| 492 if (ic_data.NumberOfChecks() != 1) return kIllegalObjectKind; | 492 if (ic_data.NumberOfChecks() != 1) return kIllegalObjectKind; |
| 493 ASSERT(HasOneTarget(ic_data)); | 493 ASSERT(HasOneTarget(ic_data)); |
| 494 | 494 |
| 495 Function& target = Function::Handle(); | 495 Function& target = Function::Handle(); |
| 496 Class& cls = Class::Handle(); | 496 intptr_t class_id; |
| 497 ic_data.GetOneClassCheckAt(0, &cls, &target); | 497 ic_data.GetOneClassCheckAt(0, &class_id, &target); |
| 498 | 498 return class_id; |
| 499 return cls.id(); | |
| 500 } | 499 } |
| 501 | 500 |
| 502 | 501 |
| 503 void FlowGraphOptimizer::VisitLoadIndexed(LoadIndexedComp* comp) { | 502 void FlowGraphOptimizer::VisitLoadIndexed(LoadIndexedComp* comp) { |
| 504 const intptr_t class_id = ReceiverClassId(comp); | 503 const intptr_t class_id = ReceiverClassId(comp); |
| 505 switch (class_id) { | 504 switch (class_id) { |
| 506 case kArray: | 505 case kArray: |
| 507 case kImmutableArray: | 506 case kImmutableArray: |
| 508 case kGrowableObjectArray: | 507 case kGrowableObjectArray: |
| 509 comp->set_receiver_type(static_cast<ObjectKind>(class_id)); | 508 comp->set_receiver_type(static_cast<ObjectKind>(class_id)); |
| (...skipping 81 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 591 instr->computation()->Accept(this); | 590 instr->computation()->Accept(this); |
| 592 } | 591 } |
| 593 | 592 |
| 594 | 593 |
| 595 void FlowGraphOptimizer::VisitBind(BindInstr* instr) { | 594 void FlowGraphOptimizer::VisitBind(BindInstr* instr) { |
| 596 instr->computation()->Accept(this); | 595 instr->computation()->Accept(this); |
| 597 } | 596 } |
| 598 | 597 |
| 599 | 598 |
| 600 } // namespace dart | 599 } // namespace dart |
| OLD | NEW |