OLD | NEW |
1 // Copyright (c) 2016, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2016, 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/redundancy_elimination.h" | 5 #include "vm/redundancy_elimination.h" |
6 | 6 |
7 #include "vm/bit_vector.h" | 7 #include "vm/bit_vector.h" |
8 #include "vm/flow_graph.h" | 8 #include "vm/flow_graph.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" |
11 #include "vm/intermediate_language.h" | 11 #include "vm/intermediate_language.h" |
12 #include "vm/stack_frame.h" | 12 #include "vm/stack_frame.h" |
13 | 13 |
14 namespace dart { | 14 namespace dart { |
15 | 15 |
16 | |
17 DEFINE_FLAG(bool, dead_store_elimination, true, "Eliminate dead stores"); | 16 DEFINE_FLAG(bool, dead_store_elimination, true, "Eliminate dead stores"); |
18 DEFINE_FLAG(bool, load_cse, true, "Use redundant load elimination."); | 17 DEFINE_FLAG(bool, load_cse, true, "Use redundant load elimination."); |
19 DEFINE_FLAG(bool, | 18 DEFINE_FLAG(bool, |
20 trace_load_optimization, | 19 trace_load_optimization, |
21 false, | 20 false, |
22 "Print live sets for load optimization pass."); | 21 "Print live sets for load optimization pass."); |
23 | 22 |
24 // Quick access to the current zone. | 23 // Quick access to the current zone. |
25 #define Z (zone()) | 24 #define Z (zone()) |
26 | 25 |
27 | |
28 class CSEInstructionMap : public ValueObject { | 26 class CSEInstructionMap : public ValueObject { |
29 public: | 27 public: |
30 // Right now CSE and LICM track a single effect: possible externalization of | 28 // Right now CSE and LICM track a single effect: possible externalization of |
31 // strings. | 29 // strings. |
32 // Other effects like modifications of fields are tracked in a separate load | 30 // Other effects like modifications of fields are tracked in a separate load |
33 // forwarding pass via Alias structure. | 31 // forwarding pass via Alias structure. |
34 COMPILE_ASSERT(EffectSet::kLastEffect == 1); | 32 COMPILE_ASSERT(EffectSet::kLastEffect == 1); |
35 | 33 |
36 CSEInstructionMap() : independent_(), dependent_() {} | 34 CSEInstructionMap() : independent_(), dependent_() {} |
37 explicit CSEInstructionMap(const CSEInstructionMap& other) | 35 explicit CSEInstructionMap(const CSEInstructionMap& other) |
(...skipping 26 matching lines...) Expand all Loading... |
64 | 62 |
65 // All computations that are not affected by any side-effect. | 63 // All computations that are not affected by any side-effect. |
66 // Majority of computations are not affected by anything and will be in | 64 // Majority of computations are not affected by anything and will be in |
67 // this map. | 65 // this map. |
68 Map independent_; | 66 Map independent_; |
69 | 67 |
70 // All computations that are affected by side effect. | 68 // All computations that are affected by side effect. |
71 Map dependent_; | 69 Map dependent_; |
72 }; | 70 }; |
73 | 71 |
74 | |
75 // Place describes an abstract location (e.g. field) that IR can load | 72 // Place describes an abstract location (e.g. field) that IR can load |
76 // from or store to. | 73 // from or store to. |
77 // | 74 // |
78 // Places are also used to describe wild-card locations also known as aliases, | 75 // Places are also used to describe wild-card locations also known as aliases, |
79 // that essentially represent sets of places that alias each other. Places A | 76 // that essentially represent sets of places that alias each other. Places A |
80 // and B are said to alias each other if store into A can affect load from B. | 77 // and B are said to alias each other if store into A can affect load from B. |
81 // | 78 // |
82 // We distinguish the following aliases: | 79 // We distinguish the following aliases: |
83 // | 80 // |
84 // - for fields | 81 // - for fields |
(...skipping 239 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
324 // For example for X[9|kInt8] and target size kInt32 we would return | 321 // For example for X[9|kInt8] and target size kInt32 we would return |
325 // X[8|kInt32]. | 322 // X[8|kInt32]. |
326 Place ToLargerElement(ElementSize to) const { | 323 Place ToLargerElement(ElementSize to) const { |
327 ASSERT(kind() == kConstantIndexed); | 324 ASSERT(kind() == kConstantIndexed); |
328 ASSERT(element_size() != kNoSize); | 325 ASSERT(element_size() != kNoSize); |
329 ASSERT(element_size() < to); | 326 ASSERT(element_size() < to); |
330 return Place(ElementSizeBits::update(to, flags_), instance_, | 327 return Place(ElementSizeBits::update(to, flags_), instance_, |
331 RoundByteOffset(to, index_constant_)); | 328 RoundByteOffset(to, index_constant_)); |
332 } | 329 } |
333 | 330 |
334 | |
335 intptr_t id() const { return id_; } | 331 intptr_t id() const { return id_; } |
336 | 332 |
337 Kind kind() const { return KindBits::decode(flags_); } | 333 Kind kind() const { return KindBits::decode(flags_); } |
338 | 334 |
339 Representation representation() const { | 335 Representation representation() const { |
340 return RepresentationBits::decode(flags_); | 336 return RepresentationBits::decode(flags_); |
341 } | 337 } |
342 | 338 |
343 Definition* instance() const { | 339 Definition* instance() const { |
344 ASSERT(DependsOnInstance()); | 340 ASSERT(DependsOnInstance()); |
(...skipping 231 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
576 intptr_t raw_selector_; | 572 intptr_t raw_selector_; |
577 const Field* field_; | 573 const Field* field_; |
578 intptr_t offset_in_bytes_; | 574 intptr_t offset_in_bytes_; |
579 intptr_t index_constant_; | 575 intptr_t index_constant_; |
580 Definition* index_; | 576 Definition* index_; |
581 }; | 577 }; |
582 | 578 |
583 intptr_t id_; | 579 intptr_t id_; |
584 }; | 580 }; |
585 | 581 |
586 | |
587 class ZonePlace : public ZoneAllocated { | 582 class ZonePlace : public ZoneAllocated { |
588 public: | 583 public: |
589 explicit ZonePlace(const Place& place) : place_(place) {} | 584 explicit ZonePlace(const Place& place) : place_(place) {} |
590 | 585 |
591 Place* place() { return &place_; } | 586 Place* place() { return &place_; } |
592 | 587 |
593 private: | 588 private: |
594 Place place_; | 589 Place place_; |
595 }; | 590 }; |
596 | 591 |
597 | |
598 Place* Place::Wrap(Zone* zone, const Place& place, intptr_t id) { | 592 Place* Place::Wrap(Zone* zone, const Place& place, intptr_t id) { |
599 Place* wrapped = (new (zone) ZonePlace(place))->place(); | 593 Place* wrapped = (new (zone) ZonePlace(place))->place(); |
600 wrapped->id_ = id; | 594 wrapped->id_ = id; |
601 return wrapped; | 595 return wrapped; |
602 } | 596 } |
603 | 597 |
604 | |
605 // Correspondence between places connected through outgoing phi moves on the | 598 // Correspondence between places connected through outgoing phi moves on the |
606 // edge that targets join. | 599 // edge that targets join. |
607 class PhiPlaceMoves : public ZoneAllocated { | 600 class PhiPlaceMoves : public ZoneAllocated { |
608 public: | 601 public: |
609 // Record a move from the place with id |from| to the place with id |to| at | 602 // Record a move from the place with id |from| to the place with id |to| at |
610 // the given block. | 603 // the given block. |
611 void CreateOutgoingMove(Zone* zone, | 604 void CreateOutgoingMove(Zone* zone, |
612 BlockEntryInstr* block, | 605 BlockEntryInstr* block, |
613 intptr_t from, | 606 intptr_t from, |
614 intptr_t to) { | 607 intptr_t to) { |
(...skipping 25 matching lines...) Expand all Loading... |
640 | 633 |
641 MovesList GetOutgoingMoves(BlockEntryInstr* block) const { | 634 MovesList GetOutgoingMoves(BlockEntryInstr* block) const { |
642 const intptr_t block_num = block->preorder_number(); | 635 const intptr_t block_num = block->preorder_number(); |
643 return (block_num < moves_.length()) ? moves_[block_num] : NULL; | 636 return (block_num < moves_.length()) ? moves_[block_num] : NULL; |
644 } | 637 } |
645 | 638 |
646 private: | 639 private: |
647 GrowableArray<ZoneGrowableArray<Move>*> moves_; | 640 GrowableArray<ZoneGrowableArray<Move>*> moves_; |
648 }; | 641 }; |
649 | 642 |
650 | |
651 // A map from aliases to a set of places sharing the alias. Additionally | 643 // A map from aliases to a set of places sharing the alias. Additionally |
652 // carries a set of places that can be aliased by side-effects, essentially | 644 // carries a set of places that can be aliased by side-effects, essentially |
653 // those that are affected by calls. | 645 // those that are affected by calls. |
654 class AliasedSet : public ZoneAllocated { | 646 class AliasedSet : public ZoneAllocated { |
655 public: | 647 public: |
656 AliasedSet(Zone* zone, | 648 AliasedSet(Zone* zone, |
657 DirectChainedHashMap<PointerKeyValueTrait<Place> >* places_map, | 649 DirectChainedHashMap<PointerKeyValueTrait<Place> >* places_map, |
658 ZoneGrowableArray<Place*>* places, | 650 ZoneGrowableArray<Place*>* places, |
659 PhiPlaceMoves* phi_moves) | 651 PhiPlaceMoves* phi_moves) |
660 : zone_(zone), | 652 : zone_(zone), |
(...skipping 468 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1129 GrowableArray<Definition*> aliasing_worklist_; | 1121 GrowableArray<Definition*> aliasing_worklist_; |
1130 | 1122 |
1131 // List of definitions that had their identity set to Aliased. At the end | 1123 // List of definitions that had their identity set to Aliased. At the end |
1132 // of load optimization their identity will be rolled back to Unknown to | 1124 // of load optimization their identity will be rolled back to Unknown to |
1133 // avoid treating them as Aliased at later stages without checking first | 1125 // avoid treating them as Aliased at later stages without checking first |
1134 // as optimizations can potentially eliminate instructions leading to | 1126 // as optimizations can potentially eliminate instructions leading to |
1135 // aliasing. | 1127 // aliasing. |
1136 GrowableArray<Definition*> identity_rollback_; | 1128 GrowableArray<Definition*> identity_rollback_; |
1137 }; | 1129 }; |
1138 | 1130 |
1139 | |
1140 static Definition* GetStoredValue(Instruction* instr) { | 1131 static Definition* GetStoredValue(Instruction* instr) { |
1141 if (instr->IsStoreIndexed()) { | 1132 if (instr->IsStoreIndexed()) { |
1142 return instr->AsStoreIndexed()->value()->definition(); | 1133 return instr->AsStoreIndexed()->value()->definition(); |
1143 } | 1134 } |
1144 | 1135 |
1145 StoreInstanceFieldInstr* store_instance_field = instr->AsStoreInstanceField(); | 1136 StoreInstanceFieldInstr* store_instance_field = instr->AsStoreInstanceField(); |
1146 if (store_instance_field != NULL) { | 1137 if (store_instance_field != NULL) { |
1147 return store_instance_field->value()->definition(); | 1138 return store_instance_field->value()->definition(); |
1148 } | 1139 } |
1149 | 1140 |
1150 StoreStaticFieldInstr* store_static_field = instr->AsStoreStaticField(); | 1141 StoreStaticFieldInstr* store_static_field = instr->AsStoreStaticField(); |
1151 if (store_static_field != NULL) { | 1142 if (store_static_field != NULL) { |
1152 return store_static_field->value()->definition(); | 1143 return store_static_field->value()->definition(); |
1153 } | 1144 } |
1154 | 1145 |
1155 UNREACHABLE(); // Should only be called for supported store instructions. | 1146 UNREACHABLE(); // Should only be called for supported store instructions. |
1156 return NULL; | 1147 return NULL; |
1157 } | 1148 } |
1158 | 1149 |
1159 | |
1160 static bool IsPhiDependentPlace(Place* place) { | 1150 static bool IsPhiDependentPlace(Place* place) { |
1161 return ((place->kind() == Place::kField) || | 1151 return ((place->kind() == Place::kField) || |
1162 (place->kind() == Place::kVMField)) && | 1152 (place->kind() == Place::kVMField)) && |
1163 (place->instance() != NULL) && place->instance()->IsPhi(); | 1153 (place->instance() != NULL) && place->instance()->IsPhi(); |
1164 } | 1154 } |
1165 | 1155 |
1166 | |
1167 // For each place that depends on a phi ensure that equivalent places | 1156 // For each place that depends on a phi ensure that equivalent places |
1168 // corresponding to phi input are numbered and record outgoing phi moves | 1157 // corresponding to phi input are numbered and record outgoing phi moves |
1169 // for each block which establish correspondence between phi dependent place | 1158 // for each block which establish correspondence between phi dependent place |
1170 // and phi input's place that is flowing in. | 1159 // and phi input's place that is flowing in. |
1171 static PhiPlaceMoves* ComputePhiMoves( | 1160 static PhiPlaceMoves* ComputePhiMoves( |
1172 DirectChainedHashMap<PointerKeyValueTrait<Place> >* map, | 1161 DirectChainedHashMap<PointerKeyValueTrait<Place> >* map, |
1173 ZoneGrowableArray<Place*>* places) { | 1162 ZoneGrowableArray<Place*>* places) { |
1174 Thread* thread = Thread::Current(); | 1163 Thread* thread = Thread::Current(); |
1175 Zone* zone = thread->zone(); | 1164 Zone* zone = thread->zone(); |
1176 PhiPlaceMoves* phi_moves = new (zone) PhiPlaceMoves(); | 1165 PhiPlaceMoves* phi_moves = new (zone) PhiPlaceMoves(); |
(...skipping 25 matching lines...) Expand all Loading... |
1202 } | 1191 } |
1203 phi_moves->CreateOutgoingMove(zone, block->PredecessorAt(j), | 1192 phi_moves->CreateOutgoingMove(zone, block->PredecessorAt(j), |
1204 result->id(), place->id()); | 1193 result->id(), place->id()); |
1205 } | 1194 } |
1206 } | 1195 } |
1207 } | 1196 } |
1208 | 1197 |
1209 return phi_moves; | 1198 return phi_moves; |
1210 } | 1199 } |
1211 | 1200 |
1212 | |
1213 enum CSEMode { kOptimizeLoads, kOptimizeStores }; | 1201 enum CSEMode { kOptimizeLoads, kOptimizeStores }; |
1214 | 1202 |
1215 | |
1216 static AliasedSet* NumberPlaces( | 1203 static AliasedSet* NumberPlaces( |
1217 FlowGraph* graph, | 1204 FlowGraph* graph, |
1218 DirectChainedHashMap<PointerKeyValueTrait<Place> >* map, | 1205 DirectChainedHashMap<PointerKeyValueTrait<Place> >* map, |
1219 CSEMode mode) { | 1206 CSEMode mode) { |
1220 // Loads representing different expression ids will be collected and | 1207 // Loads representing different expression ids will be collected and |
1221 // used to build per offset kill sets. | 1208 // used to build per offset kill sets. |
1222 Zone* zone = graph->zone(); | 1209 Zone* zone = graph->zone(); |
1223 ZoneGrowableArray<Place*>* places = new (zone) ZoneGrowableArray<Place*>(10); | 1210 ZoneGrowableArray<Place*>* places = new (zone) ZoneGrowableArray<Place*>(10); |
1224 | 1211 |
1225 bool has_loads = false; | 1212 bool has_loads = false; |
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1258 if ((mode == kOptimizeStores) && !has_stores) { | 1245 if ((mode == kOptimizeStores) && !has_stores) { |
1259 return NULL; | 1246 return NULL; |
1260 } | 1247 } |
1261 | 1248 |
1262 PhiPlaceMoves* phi_moves = ComputePhiMoves(map, places); | 1249 PhiPlaceMoves* phi_moves = ComputePhiMoves(map, places); |
1263 | 1250 |
1264 // Build aliasing sets mapping aliases to loads. | 1251 // Build aliasing sets mapping aliases to loads. |
1265 return new (zone) AliasedSet(zone, map, places, phi_moves); | 1252 return new (zone) AliasedSet(zone, map, places, phi_moves); |
1266 } | 1253 } |
1267 | 1254 |
1268 | |
1269 // Load instructions handled by load elimination. | 1255 // Load instructions handled by load elimination. |
1270 static bool IsLoadEliminationCandidate(Instruction* instr) { | 1256 static bool IsLoadEliminationCandidate(Instruction* instr) { |
1271 return instr->IsLoadField() || instr->IsLoadIndexed() || | 1257 return instr->IsLoadField() || instr->IsLoadIndexed() || |
1272 instr->IsLoadStaticField(); | 1258 instr->IsLoadStaticField(); |
1273 } | 1259 } |
1274 | 1260 |
1275 | |
1276 static bool IsLoopInvariantLoad(ZoneGrowableArray<BitVector*>* sets, | 1261 static bool IsLoopInvariantLoad(ZoneGrowableArray<BitVector*>* sets, |
1277 intptr_t loop_header_index, | 1262 intptr_t loop_header_index, |
1278 Instruction* instr) { | 1263 Instruction* instr) { |
1279 return IsLoadEliminationCandidate(instr) && (sets != NULL) && | 1264 return IsLoadEliminationCandidate(instr) && (sets != NULL) && |
1280 instr->HasPlaceId() && ((*sets)[loop_header_index] != NULL) && | 1265 instr->HasPlaceId() && ((*sets)[loop_header_index] != NULL) && |
1281 (*sets)[loop_header_index]->Contains(instr->place_id()); | 1266 (*sets)[loop_header_index]->Contains(instr->place_id()); |
1282 } | 1267 } |
1283 | 1268 |
1284 | |
1285 LICM::LICM(FlowGraph* flow_graph) : flow_graph_(flow_graph) { | 1269 LICM::LICM(FlowGraph* flow_graph) : flow_graph_(flow_graph) { |
1286 ASSERT(flow_graph->is_licm_allowed()); | 1270 ASSERT(flow_graph->is_licm_allowed()); |
1287 } | 1271 } |
1288 | 1272 |
1289 | |
1290 void LICM::Hoist(ForwardInstructionIterator* it, | 1273 void LICM::Hoist(ForwardInstructionIterator* it, |
1291 BlockEntryInstr* pre_header, | 1274 BlockEntryInstr* pre_header, |
1292 Instruction* current) { | 1275 Instruction* current) { |
1293 if (current->IsCheckClass()) { | 1276 if (current->IsCheckClass()) { |
1294 current->AsCheckClass()->set_licm_hoisted(true); | 1277 current->AsCheckClass()->set_licm_hoisted(true); |
1295 } else if (current->IsCheckSmi()) { | 1278 } else if (current->IsCheckSmi()) { |
1296 current->AsCheckSmi()->set_licm_hoisted(true); | 1279 current->AsCheckSmi()->set_licm_hoisted(true); |
1297 } else if (current->IsCheckEitherNonSmi()) { | 1280 } else if (current->IsCheckEitherNonSmi()) { |
1298 current->AsCheckEitherNonSmi()->set_licm_hoisted(true); | 1281 current->AsCheckEitherNonSmi()->set_licm_hoisted(true); |
1299 } else if (current->IsCheckArrayBound()) { | 1282 } else if (current->IsCheckArrayBound()) { |
(...skipping 12 matching lines...) Expand all Loading... |
1312 it->RemoveCurrentFromGraph(); | 1295 it->RemoveCurrentFromGraph(); |
1313 } else { | 1296 } else { |
1314 current->RemoveFromGraph(); | 1297 current->RemoveFromGraph(); |
1315 } | 1298 } |
1316 GotoInstr* last = pre_header->last_instruction()->AsGoto(); | 1299 GotoInstr* last = pre_header->last_instruction()->AsGoto(); |
1317 // Using kind kEffect will not assign a fresh ssa temporary index. | 1300 // Using kind kEffect will not assign a fresh ssa temporary index. |
1318 flow_graph()->InsertBefore(last, current, last->env(), FlowGraph::kEffect); | 1301 flow_graph()->InsertBefore(last, current, last->env(), FlowGraph::kEffect); |
1319 current->CopyDeoptIdFrom(*last); | 1302 current->CopyDeoptIdFrom(*last); |
1320 } | 1303 } |
1321 | 1304 |
1322 | |
1323 void LICM::TrySpecializeSmiPhi(PhiInstr* phi, | 1305 void LICM::TrySpecializeSmiPhi(PhiInstr* phi, |
1324 BlockEntryInstr* header, | 1306 BlockEntryInstr* header, |
1325 BlockEntryInstr* pre_header) { | 1307 BlockEntryInstr* pre_header) { |
1326 if (phi->Type()->ToCid() == kSmiCid) { | 1308 if (phi->Type()->ToCid() == kSmiCid) { |
1327 return; | 1309 return; |
1328 } | 1310 } |
1329 | 1311 |
1330 // Check if there is only a single kDynamicCid input to the phi that | 1312 // Check if there is only a single kDynamicCid input to the phi that |
1331 // comes from the pre-header. | 1313 // comes from the pre-header. |
1332 const intptr_t kNotFound = -1; | 1314 const intptr_t kNotFound = -1; |
(...skipping 29 matching lines...) Expand all Loading... |
1362 | 1344 |
1363 // Host CheckSmi instruction and make this phi smi one. | 1345 // Host CheckSmi instruction and make this phi smi one. |
1364 Hoist(NULL, pre_header, check); | 1346 Hoist(NULL, pre_header, check); |
1365 | 1347 |
1366 // Replace value we are checking with phi's input. | 1348 // Replace value we are checking with phi's input. |
1367 check->value()->BindTo(phi->InputAt(non_smi_input)->definition()); | 1349 check->value()->BindTo(phi->InputAt(non_smi_input)->definition()); |
1368 | 1350 |
1369 phi->UpdateType(CompileType::FromCid(kSmiCid)); | 1351 phi->UpdateType(CompileType::FromCid(kSmiCid)); |
1370 } | 1352 } |
1371 | 1353 |
1372 | |
1373 void LICM::OptimisticallySpecializeSmiPhis() { | 1354 void LICM::OptimisticallySpecializeSmiPhis() { |
1374 if (!flow_graph()->function().allows_hoisting_check_class() || | 1355 if (!flow_graph()->function().allows_hoisting_check_class() || |
1375 FLAG_precompiled_mode) { | 1356 FLAG_precompiled_mode) { |
1376 // Do not hoist any: Either deoptimized on a hoisted check, | 1357 // Do not hoist any: Either deoptimized on a hoisted check, |
1377 // or compiling precompiled code where we can't do optimistic | 1358 // or compiling precompiled code where we can't do optimistic |
1378 // hoisting of checks. | 1359 // hoisting of checks. |
1379 return; | 1360 return; |
1380 } | 1361 } |
1381 | 1362 |
1382 const ZoneGrowableArray<BlockEntryInstr*>& loop_headers = | 1363 const ZoneGrowableArray<BlockEntryInstr*>& loop_headers = |
1383 flow_graph()->LoopHeaders(); | 1364 flow_graph()->LoopHeaders(); |
1384 | 1365 |
1385 for (intptr_t i = 0; i < loop_headers.length(); ++i) { | 1366 for (intptr_t i = 0; i < loop_headers.length(); ++i) { |
1386 JoinEntryInstr* header = loop_headers[i]->AsJoinEntry(); | 1367 JoinEntryInstr* header = loop_headers[i]->AsJoinEntry(); |
1387 // Skip loop that don't have a pre-header block. | 1368 // Skip loop that don't have a pre-header block. |
1388 BlockEntryInstr* pre_header = header->ImmediateDominator(); | 1369 BlockEntryInstr* pre_header = header->ImmediateDominator(); |
1389 if (pre_header == NULL) continue; | 1370 if (pre_header == NULL) continue; |
1390 | 1371 |
1391 for (PhiIterator it(header); !it.Done(); it.Advance()) { | 1372 for (PhiIterator it(header); !it.Done(); it.Advance()) { |
1392 TrySpecializeSmiPhi(it.Current(), header, pre_header); | 1373 TrySpecializeSmiPhi(it.Current(), header, pre_header); |
1393 } | 1374 } |
1394 } | 1375 } |
1395 } | 1376 } |
1396 | 1377 |
1397 | |
1398 void LICM::Optimize() { | 1378 void LICM::Optimize() { |
1399 if (!flow_graph()->function().allows_hoisting_check_class()) { | 1379 if (!flow_graph()->function().allows_hoisting_check_class()) { |
1400 // Do not hoist any. | 1380 // Do not hoist any. |
1401 return; | 1381 return; |
1402 } | 1382 } |
1403 | 1383 |
1404 const ZoneGrowableArray<BlockEntryInstr*>& loop_headers = | 1384 const ZoneGrowableArray<BlockEntryInstr*>& loop_headers = |
1405 flow_graph()->LoopHeaders(); | 1385 flow_graph()->LoopHeaders(); |
1406 | 1386 |
1407 ZoneGrowableArray<BitVector*>* loop_invariant_loads = | 1387 ZoneGrowableArray<BitVector*>* loop_invariant_loads = |
(...skipping 28 matching lines...) Expand all Loading... |
1436 // TODO(fschneider): Enable hoisting of Assert-instructions | 1416 // TODO(fschneider): Enable hoisting of Assert-instructions |
1437 // if it safe to do. | 1417 // if it safe to do. |
1438 Hoist(&it, pre_header, current); | 1418 Hoist(&it, pre_header, current); |
1439 } | 1419 } |
1440 } | 1420 } |
1441 } | 1421 } |
1442 } | 1422 } |
1443 } | 1423 } |
1444 } | 1424 } |
1445 | 1425 |
1446 | |
1447 class LoadOptimizer : public ValueObject { | 1426 class LoadOptimizer : public ValueObject { |
1448 public: | 1427 public: |
1449 LoadOptimizer(FlowGraph* graph, AliasedSet* aliased_set) | 1428 LoadOptimizer(FlowGraph* graph, AliasedSet* aliased_set) |
1450 : graph_(graph), | 1429 : graph_(graph), |
1451 aliased_set_(aliased_set), | 1430 aliased_set_(aliased_set), |
1452 in_(graph_->preorder().length()), | 1431 in_(graph_->preorder().length()), |
1453 out_(graph_->preorder().length()), | 1432 out_(graph_->preorder().length()), |
1454 gen_(graph_->preorder().length()), | 1433 gen_(graph_->preorder().length()), |
1455 kill_(graph_->preorder().length()), | 1434 kill_(graph_->preorder().length()), |
1456 exposed_values_(graph_->preorder().length()), | 1435 exposed_values_(graph_->preorder().length()), |
(...skipping 375 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1832 !block_it.Done(); block_it.Advance()) { | 1811 !block_it.Done(); block_it.Advance()) { |
1833 BlockEntryInstr* block = block_it.Current(); | 1812 BlockEntryInstr* block = block_it.Current(); |
1834 | 1813 |
1835 const bool can_merge_eagerly = CanMergeEagerly(block); | 1814 const bool can_merge_eagerly = CanMergeEagerly(block); |
1836 | 1815 |
1837 const intptr_t preorder_number = block->preorder_number(); | 1816 const intptr_t preorder_number = block->preorder_number(); |
1838 | 1817 |
1839 ZoneGrowableArray<Definition*>* block_out_values = | 1818 ZoneGrowableArray<Definition*>* block_out_values = |
1840 out_values_[preorder_number]; | 1819 out_values_[preorder_number]; |
1841 | 1820 |
1842 | |
1843 // If OUT set has changed then we have new values available out of | 1821 // If OUT set has changed then we have new values available out of |
1844 // the block. Compute these values creating phi where necessary. | 1822 // the block. Compute these values creating phi where necessary. |
1845 for (BitVector::Iterator it(out_[preorder_number]); !it.Done(); | 1823 for (BitVector::Iterator it(out_[preorder_number]); !it.Done(); |
1846 it.Advance()) { | 1824 it.Advance()) { |
1847 const intptr_t place_id = it.Current(); | 1825 const intptr_t place_id = it.Current(); |
1848 | 1826 |
1849 if (block_out_values == NULL) { | 1827 if (block_out_values == NULL) { |
1850 out_values_[preorder_number] = block_out_values = | 1828 out_values_[preorder_number] = block_out_values = |
1851 CreateBlockOutValues(); | 1829 CreateBlockOutValues(); |
1852 } | 1830 } |
(...skipping 492 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2345 // List of phis generated during ComputeOutValues and ForwardLoads. | 2323 // List of phis generated during ComputeOutValues and ForwardLoads. |
2346 // Some of these phis might be redundant and thus a separate pass is | 2324 // Some of these phis might be redundant and thus a separate pass is |
2347 // needed to emit only non-redundant ones. | 2325 // needed to emit only non-redundant ones. |
2348 GrowableArray<PhiInstr*> phis_; | 2326 GrowableArray<PhiInstr*> phis_; |
2349 | 2327 |
2350 // Auxiliary worklist used by redundant phi elimination. | 2328 // Auxiliary worklist used by redundant phi elimination. |
2351 GrowableArray<PhiInstr*> worklist_; | 2329 GrowableArray<PhiInstr*> worklist_; |
2352 GrowableArray<Definition*> congruency_worklist_; | 2330 GrowableArray<Definition*> congruency_worklist_; |
2353 BitVector* in_worklist_; | 2331 BitVector* in_worklist_; |
2354 | 2332 |
2355 | |
2356 // True if any load was eliminated. | 2333 // True if any load was eliminated. |
2357 bool forwarded_; | 2334 bool forwarded_; |
2358 | 2335 |
2359 DISALLOW_COPY_AND_ASSIGN(LoadOptimizer); | 2336 DISALLOW_COPY_AND_ASSIGN(LoadOptimizer); |
2360 }; | 2337 }; |
2361 | 2338 |
2362 | |
2363 bool DominatorBasedCSE::Optimize(FlowGraph* graph) { | 2339 bool DominatorBasedCSE::Optimize(FlowGraph* graph) { |
2364 bool changed = false; | 2340 bool changed = false; |
2365 if (FLAG_load_cse) { | 2341 if (FLAG_load_cse) { |
2366 changed = LoadOptimizer::OptimizeGraph(graph) || changed; | 2342 changed = LoadOptimizer::OptimizeGraph(graph) || changed; |
2367 } | 2343 } |
2368 | 2344 |
2369 CSEInstructionMap map; | 2345 CSEInstructionMap map; |
2370 changed = OptimizeRecursive(graph, graph->graph_entry(), &map) || changed; | 2346 changed = OptimizeRecursive(graph, graph->graph_entry(), &map) || changed; |
2371 | 2347 |
2372 return changed; | 2348 return changed; |
2373 } | 2349 } |
2374 | 2350 |
2375 | |
2376 bool DominatorBasedCSE::OptimizeRecursive(FlowGraph* graph, | 2351 bool DominatorBasedCSE::OptimizeRecursive(FlowGraph* graph, |
2377 BlockEntryInstr* block, | 2352 BlockEntryInstr* block, |
2378 CSEInstructionMap* map) { | 2353 CSEInstructionMap* map) { |
2379 bool changed = false; | 2354 bool changed = false; |
2380 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { | 2355 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { |
2381 Instruction* current = it.Current(); | 2356 Instruction* current = it.Current(); |
2382 if (current->AllowsCSE()) { | 2357 if (current->AllowsCSE()) { |
2383 Instruction* replacement = map->Lookup(current); | 2358 Instruction* replacement = map->Lookup(current); |
2384 if ((replacement != NULL) && | 2359 if ((replacement != NULL) && |
2385 graph->block_effects()->IsAvailableAt(replacement, block)) { | 2360 graph->block_effects()->IsAvailableAt(replacement, block)) { |
(...skipping 26 matching lines...) Expand all Loading... |
2412 CSEInstructionMap child_map(*map); | 2387 CSEInstructionMap child_map(*map); |
2413 changed = OptimizeRecursive(graph, child, &child_map) || changed; | 2388 changed = OptimizeRecursive(graph, child, &child_map) || changed; |
2414 } else { | 2389 } else { |
2415 // Reuse map for the last child. | 2390 // Reuse map for the last child. |
2416 changed = OptimizeRecursive(graph, child, map) || changed; | 2391 changed = OptimizeRecursive(graph, child, map) || changed; |
2417 } | 2392 } |
2418 } | 2393 } |
2419 return changed; | 2394 return changed; |
2420 } | 2395 } |
2421 | 2396 |
2422 | |
2423 class StoreOptimizer : public LivenessAnalysis { | 2397 class StoreOptimizer : public LivenessAnalysis { |
2424 public: | 2398 public: |
2425 StoreOptimizer(FlowGraph* graph, | 2399 StoreOptimizer(FlowGraph* graph, |
2426 AliasedSet* aliased_set, | 2400 AliasedSet* aliased_set, |
2427 DirectChainedHashMap<PointerKeyValueTrait<Place> >* map) | 2401 DirectChainedHashMap<PointerKeyValueTrait<Place> >* map) |
2428 : LivenessAnalysis(aliased_set->max_place_id(), graph->postorder()), | 2402 : LivenessAnalysis(aliased_set->max_place_id(), graph->postorder()), |
2429 graph_(graph), | 2403 graph_(graph), |
2430 map_(map), | 2404 map_(map), |
2431 aliased_set_(aliased_set), | 2405 aliased_set_(aliased_set), |
2432 exposed_stores_(graph_->postorder().length()) { | 2406 exposed_stores_(graph_->postorder().length()) { |
(...skipping 186 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2619 // Mapping between field offsets in words and expression ids of loads from | 2593 // Mapping between field offsets in words and expression ids of loads from |
2620 // that offset. | 2594 // that offset. |
2621 AliasedSet* aliased_set_; | 2595 AliasedSet* aliased_set_; |
2622 | 2596 |
2623 // Per block list of downward exposed stores. | 2597 // Per block list of downward exposed stores. |
2624 GrowableArray<ZoneGrowableArray<Instruction*>*> exposed_stores_; | 2598 GrowableArray<ZoneGrowableArray<Instruction*>*> exposed_stores_; |
2625 | 2599 |
2626 DISALLOW_COPY_AND_ASSIGN(StoreOptimizer); | 2600 DISALLOW_COPY_AND_ASSIGN(StoreOptimizer); |
2627 }; | 2601 }; |
2628 | 2602 |
2629 | |
2630 void DeadStoreElimination::Optimize(FlowGraph* graph) { | 2603 void DeadStoreElimination::Optimize(FlowGraph* graph) { |
2631 if (FLAG_dead_store_elimination) { | 2604 if (FLAG_dead_store_elimination) { |
2632 StoreOptimizer::OptimizeGraph(graph); | 2605 StoreOptimizer::OptimizeGraph(graph); |
2633 } | 2606 } |
2634 } | 2607 } |
2635 | 2608 |
2636 | |
2637 enum SafeUseCheck { kOptimisticCheck, kStrictCheck }; | 2609 enum SafeUseCheck { kOptimisticCheck, kStrictCheck }; |
2638 | 2610 |
2639 // Check if the use is safe for allocation sinking. Allocation sinking | 2611 // Check if the use is safe for allocation sinking. Allocation sinking |
2640 // candidates can only be used at store instructions: | 2612 // candidates can only be used at store instructions: |
2641 // | 2613 // |
2642 // - any store into the allocation candidate itself is unconditionally safe | 2614 // - any store into the allocation candidate itself is unconditionally safe |
2643 // as it just changes the rematerialization state of this candidate; | 2615 // as it just changes the rematerialization state of this candidate; |
2644 // - store into another object is only safe if another object is allocation | 2616 // - store into another object is only safe if another object is allocation |
2645 // candidate. | 2617 // candidate. |
2646 // | 2618 // |
(...skipping 21 matching lines...) Expand all Loading... |
2668 return instance->IsAllocateObject() && | 2640 return instance->IsAllocateObject() && |
2669 ((check_type == kOptimisticCheck) || | 2641 ((check_type == kOptimisticCheck) || |
2670 instance->Identity().IsAllocationSinkingCandidate()); | 2642 instance->Identity().IsAllocationSinkingCandidate()); |
2671 } | 2643 } |
2672 return true; | 2644 return true; |
2673 } | 2645 } |
2674 | 2646 |
2675 return false; | 2647 return false; |
2676 } | 2648 } |
2677 | 2649 |
2678 | |
2679 // Right now we are attempting to sink allocation only into | 2650 // Right now we are attempting to sink allocation only into |
2680 // deoptimization exit. So candidate should only be used in StoreInstanceField | 2651 // deoptimization exit. So candidate should only be used in StoreInstanceField |
2681 // instructions that write into fields of the allocated object. | 2652 // instructions that write into fields of the allocated object. |
2682 // We do not support materialization of the object that has type arguments. | 2653 // We do not support materialization of the object that has type arguments. |
2683 static bool IsAllocationSinkingCandidate(Definition* alloc, | 2654 static bool IsAllocationSinkingCandidate(Definition* alloc, |
2684 SafeUseCheck check_type) { | 2655 SafeUseCheck check_type) { |
2685 for (Value* use = alloc->input_use_list(); use != NULL; | 2656 for (Value* use = alloc->input_use_list(); use != NULL; |
2686 use = use->next_use()) { | 2657 use = use->next_use()) { |
2687 if (!IsSafeUse(use, check_type)) { | 2658 if (!IsSafeUse(use, check_type)) { |
2688 if (FLAG_support_il_printer && FLAG_trace_optimization) { | 2659 if (FLAG_support_il_printer && FLAG_trace_optimization) { |
2689 THR_Print("use of %s at %s is unsafe for allocation sinking\n", | 2660 THR_Print("use of %s at %s is unsafe for allocation sinking\n", |
2690 alloc->ToCString(), use->instruction()->ToCString()); | 2661 alloc->ToCString(), use->instruction()->ToCString()); |
2691 } | 2662 } |
2692 return false; | 2663 return false; |
2693 } | 2664 } |
2694 } | 2665 } |
2695 | 2666 |
2696 return true; | 2667 return true; |
2697 } | 2668 } |
2698 | 2669 |
2699 | |
2700 // If the given use is a store into an object then return an object we are | 2670 // If the given use is a store into an object then return an object we are |
2701 // storing into. | 2671 // storing into. |
2702 static Definition* StoreInto(Value* use) { | 2672 static Definition* StoreInto(Value* use) { |
2703 StoreInstanceFieldInstr* store = use->instruction()->AsStoreInstanceField(); | 2673 StoreInstanceFieldInstr* store = use->instruction()->AsStoreInstanceField(); |
2704 if (store != NULL) { | 2674 if (store != NULL) { |
2705 return store->instance()->definition(); | 2675 return store->instance()->definition(); |
2706 } | 2676 } |
2707 | 2677 |
2708 return NULL; | 2678 return NULL; |
2709 } | 2679 } |
2710 | 2680 |
2711 | |
2712 // Remove the given allocation from the graph. It is not observable. | 2681 // Remove the given allocation from the graph. It is not observable. |
2713 // If deoptimization occurs the object will be materialized. | 2682 // If deoptimization occurs the object will be materialized. |
2714 void AllocationSinking::EliminateAllocation(Definition* alloc) { | 2683 void AllocationSinking::EliminateAllocation(Definition* alloc) { |
2715 ASSERT(IsAllocationSinkingCandidate(alloc, kStrictCheck)); | 2684 ASSERT(IsAllocationSinkingCandidate(alloc, kStrictCheck)); |
2716 | 2685 |
2717 if (FLAG_trace_optimization) { | 2686 if (FLAG_trace_optimization) { |
2718 THR_Print("removing allocation from the graph: v%" Pd "\n", | 2687 THR_Print("removing allocation from the graph: v%" Pd "\n", |
2719 alloc->ssa_temp_index()); | 2688 alloc->ssa_temp_index()); |
2720 } | 2689 } |
2721 | 2690 |
(...skipping 14 matching lines...) Expand all Loading... |
2736 ASSERT(alloc->input_use_list() == NULL); | 2705 ASSERT(alloc->input_use_list() == NULL); |
2737 alloc->RemoveFromGraph(); | 2706 alloc->RemoveFromGraph(); |
2738 if (alloc->ArgumentCount() > 0) { | 2707 if (alloc->ArgumentCount() > 0) { |
2739 ASSERT(alloc->ArgumentCount() == 1); | 2708 ASSERT(alloc->ArgumentCount() == 1); |
2740 for (intptr_t i = 0; i < alloc->ArgumentCount(); ++i) { | 2709 for (intptr_t i = 0; i < alloc->ArgumentCount(); ++i) { |
2741 alloc->PushArgumentAt(i)->RemoveFromGraph(); | 2710 alloc->PushArgumentAt(i)->RemoveFromGraph(); |
2742 } | 2711 } |
2743 } | 2712 } |
2744 } | 2713 } |
2745 | 2714 |
2746 | |
2747 // Find allocation instructions that can be potentially eliminated and | 2715 // Find allocation instructions that can be potentially eliminated and |
2748 // rematerialized at deoptimization exits if needed. See IsSafeUse | 2716 // rematerialized at deoptimization exits if needed. See IsSafeUse |
2749 // for the description of algorithm used below. | 2717 // for the description of algorithm used below. |
2750 void AllocationSinking::CollectCandidates() { | 2718 void AllocationSinking::CollectCandidates() { |
2751 // Optimistically collect all potential candidates. | 2719 // Optimistically collect all potential candidates. |
2752 for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator(); | 2720 for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator(); |
2753 !block_it.Done(); block_it.Advance()) { | 2721 !block_it.Done(); block_it.Advance()) { |
2754 BlockEntryInstr* block = block_it.Current(); | 2722 BlockEntryInstr* block = block_it.Current(); |
2755 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { | 2723 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { |
2756 { | 2724 { |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2800 | 2768 |
2801 if (j != i) { | 2769 if (j != i) { |
2802 candidates_[j] = alloc; | 2770 candidates_[j] = alloc; |
2803 } | 2771 } |
2804 j++; | 2772 j++; |
2805 } | 2773 } |
2806 } | 2774 } |
2807 candidates_.TruncateTo(j); | 2775 candidates_.TruncateTo(j); |
2808 } | 2776 } |
2809 | 2777 |
2810 | |
2811 // If materialization references an allocation sinking candidate then replace | 2778 // If materialization references an allocation sinking candidate then replace |
2812 // this reference with a materialization which should have been computed for | 2779 // this reference with a materialization which should have been computed for |
2813 // this side-exit. CollectAllExits should have collected this exit. | 2780 // this side-exit. CollectAllExits should have collected this exit. |
2814 void AllocationSinking::NormalizeMaterializations() { | 2781 void AllocationSinking::NormalizeMaterializations() { |
2815 for (intptr_t i = 0; i < candidates_.length(); i++) { | 2782 for (intptr_t i = 0; i < candidates_.length(); i++) { |
2816 Definition* alloc = candidates_[i]; | 2783 Definition* alloc = candidates_[i]; |
2817 | 2784 |
2818 Value* next_use; | 2785 Value* next_use; |
2819 for (Value* use = alloc->input_use_list(); use != NULL; use = next_use) { | 2786 for (Value* use = alloc->input_use_list(); use != NULL; use = next_use) { |
2820 next_use = use->next_use(); | 2787 next_use = use->next_use(); |
2821 if (use->instruction()->IsMaterializeObject()) { | 2788 if (use->instruction()->IsMaterializeObject()) { |
2822 use->BindTo(MaterializationFor(alloc, use->instruction())); | 2789 use->BindTo(MaterializationFor(alloc, use->instruction())); |
2823 } | 2790 } |
2824 } | 2791 } |
2825 } | 2792 } |
2826 } | 2793 } |
2827 | 2794 |
2828 | |
2829 // We transitively insert materializations at each deoptimization exit that | 2795 // We transitively insert materializations at each deoptimization exit that |
2830 // might see the given allocation (see ExitsCollector). Some of this | 2796 // might see the given allocation (see ExitsCollector). Some of this |
2831 // materializations are not actually used and some fail to compute because | 2797 // materializations are not actually used and some fail to compute because |
2832 // they are inserted in the block that is not dominated by the allocation. | 2798 // they are inserted in the block that is not dominated by the allocation. |
2833 // Remove them unused materializations from the graph. | 2799 // Remove them unused materializations from the graph. |
2834 void AllocationSinking::RemoveUnusedMaterializations() { | 2800 void AllocationSinking::RemoveUnusedMaterializations() { |
2835 intptr_t j = 0; | 2801 intptr_t j = 0; |
2836 for (intptr_t i = 0; i < materializations_.length(); i++) { | 2802 for (intptr_t i = 0; i < materializations_.length(); i++) { |
2837 MaterializeObjectInstr* mat = materializations_[i]; | 2803 MaterializeObjectInstr* mat = materializations_[i]; |
2838 if ((mat->input_use_list() == NULL) && (mat->env_use_list() == NULL)) { | 2804 if ((mat->input_use_list() == NULL) && (mat->env_use_list() == NULL)) { |
(...skipping 13 matching lines...) Expand all Loading... |
2852 } else { | 2818 } else { |
2853 if (j != i) { | 2819 if (j != i) { |
2854 materializations_[j] = mat; | 2820 materializations_[j] = mat; |
2855 } | 2821 } |
2856 j++; | 2822 j++; |
2857 } | 2823 } |
2858 } | 2824 } |
2859 materializations_.TruncateTo(j); | 2825 materializations_.TruncateTo(j); |
2860 } | 2826 } |
2861 | 2827 |
2862 | |
2863 // Some candidates might stop being eligible for allocation sinking after | 2828 // Some candidates might stop being eligible for allocation sinking after |
2864 // the load forwarding because they flow into phis that load forwarding | 2829 // the load forwarding because they flow into phis that load forwarding |
2865 // inserts. Discover such allocations and remove them from the list | 2830 // inserts. Discover such allocations and remove them from the list |
2866 // of allocation sinking candidates undoing all changes that we did | 2831 // of allocation sinking candidates undoing all changes that we did |
2867 // in preparation for sinking these allocations. | 2832 // in preparation for sinking these allocations. |
2868 void AllocationSinking::DiscoverFailedCandidates() { | 2833 void AllocationSinking::DiscoverFailedCandidates() { |
2869 // Transitively unmark all candidates that are not strictly valid. | 2834 // Transitively unmark all candidates that are not strictly valid. |
2870 bool changed; | 2835 bool changed; |
2871 do { | 2836 do { |
2872 changed = false; | 2837 changed = false; |
(...skipping 65 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2938 } | 2903 } |
2939 k++; | 2904 k++; |
2940 } | 2905 } |
2941 } | 2906 } |
2942 materializations_.TruncateTo(k); | 2907 materializations_.TruncateTo(k); |
2943 } | 2908 } |
2944 | 2909 |
2945 candidates_.TruncateTo(j); | 2910 candidates_.TruncateTo(j); |
2946 } | 2911 } |
2947 | 2912 |
2948 | |
2949 void AllocationSinking::Optimize() { | 2913 void AllocationSinking::Optimize() { |
2950 CollectCandidates(); | 2914 CollectCandidates(); |
2951 | 2915 |
2952 // Insert MaterializeObject instructions that will describe the state of the | 2916 // Insert MaterializeObject instructions that will describe the state of the |
2953 // object at all deoptimization points. Each inserted materialization looks | 2917 // object at all deoptimization points. Each inserted materialization looks |
2954 // like this (where v_0 is allocation that we are going to eliminate): | 2918 // like this (where v_0 is allocation that we are going to eliminate): |
2955 // v_1 <- LoadField(v_0, field_1) | 2919 // v_1 <- LoadField(v_0, field_1) |
2956 // ... | 2920 // ... |
2957 // v_N <- LoadField(v_0, field_N) | 2921 // v_N <- LoadField(v_0, field_N) |
2958 // v_{N+1} <- MaterializeObject(field_1 = v_1, ..., field_N = v_{N}) | 2922 // v_{N+1} <- MaterializeObject(field_1 = v_1, ..., field_N = v_{N}) |
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2991 MaterializeObjectInstr* mat = materializations_[i]; | 2955 MaterializeObjectInstr* mat = materializations_[i]; |
2992 for (intptr_t j = 0; j < mat->InputCount(); j++) { | 2956 for (intptr_t j = 0; j < mat->InputCount(); j++) { |
2993 Definition* defn = mat->InputAt(j)->definition(); | 2957 Definition* defn = mat->InputAt(j)->definition(); |
2994 if (defn->IsBox()) { | 2958 if (defn->IsBox()) { |
2995 mat->InputAt(j)->BindTo(defn->InputAt(0)->definition()); | 2959 mat->InputAt(j)->BindTo(defn->InputAt(0)->definition()); |
2996 } | 2960 } |
2997 } | 2961 } |
2998 } | 2962 } |
2999 } | 2963 } |
3000 | 2964 |
3001 | |
3002 // Remove materializations from the graph. Register allocator will treat them | 2965 // Remove materializations from the graph. Register allocator will treat them |
3003 // as part of the environment not as a real instruction. | 2966 // as part of the environment not as a real instruction. |
3004 void AllocationSinking::DetachMaterializations() { | 2967 void AllocationSinking::DetachMaterializations() { |
3005 for (intptr_t i = 0; i < materializations_.length(); i++) { | 2968 for (intptr_t i = 0; i < materializations_.length(); i++) { |
3006 materializations_[i]->previous()->LinkTo(materializations_[i]->next()); | 2969 materializations_[i]->previous()->LinkTo(materializations_[i]->next()); |
3007 } | 2970 } |
3008 } | 2971 } |
3009 | 2972 |
3010 | |
3011 // Add a field/offset to the list of fields if it is not yet present there. | 2973 // Add a field/offset to the list of fields if it is not yet present there. |
3012 static bool AddSlot(ZoneGrowableArray<const Object*>* slots, | 2974 static bool AddSlot(ZoneGrowableArray<const Object*>* slots, |
3013 const Object& slot) { | 2975 const Object& slot) { |
3014 ASSERT(slot.IsSmi() || slot.IsField()); | 2976 ASSERT(slot.IsSmi() || slot.IsField()); |
3015 ASSERT(!slot.IsField() || Field::Cast(slot).IsOriginal()); | 2977 ASSERT(!slot.IsField() || Field::Cast(slot).IsOriginal()); |
3016 for (intptr_t i = 0; i < slots->length(); i++) { | 2978 for (intptr_t i = 0; i < slots->length(); i++) { |
3017 if ((*slots)[i]->raw() == slot.raw()) { | 2979 if ((*slots)[i]->raw() == slot.raw()) { |
3018 return false; | 2980 return false; |
3019 } | 2981 } |
3020 } | 2982 } |
3021 slots->Add(&slot); | 2983 slots->Add(&slot); |
3022 return true; | 2984 return true; |
3023 } | 2985 } |
3024 | 2986 |
3025 | |
3026 // Find deoptimization exit for the given materialization assuming that all | 2987 // Find deoptimization exit for the given materialization assuming that all |
3027 // materializations are emitted right before the instruction which is a | 2988 // materializations are emitted right before the instruction which is a |
3028 // deoptimization exit. | 2989 // deoptimization exit. |
3029 static Instruction* ExitForMaterialization(MaterializeObjectInstr* mat) { | 2990 static Instruction* ExitForMaterialization(MaterializeObjectInstr* mat) { |
3030 while (mat->next()->IsMaterializeObject()) { | 2991 while (mat->next()->IsMaterializeObject()) { |
3031 mat = mat->next()->AsMaterializeObject(); | 2992 mat = mat->next()->AsMaterializeObject(); |
3032 } | 2993 } |
3033 return mat->next(); | 2994 return mat->next(); |
3034 } | 2995 } |
3035 | 2996 |
3036 | |
3037 // Given the deoptimization exit find first materialization that was inserted | 2997 // Given the deoptimization exit find first materialization that was inserted |
3038 // before it. | 2998 // before it. |
3039 static Instruction* FirstMaterializationAt(Instruction* exit) { | 2999 static Instruction* FirstMaterializationAt(Instruction* exit) { |
3040 while (exit->previous()->IsMaterializeObject()) { | 3000 while (exit->previous()->IsMaterializeObject()) { |
3041 exit = exit->previous(); | 3001 exit = exit->previous(); |
3042 } | 3002 } |
3043 return exit; | 3003 return exit; |
3044 } | 3004 } |
3045 | 3005 |
3046 | |
3047 // Given the allocation and deoptimization exit try to find MaterializeObject | 3006 // Given the allocation and deoptimization exit try to find MaterializeObject |
3048 // instruction corresponding to this allocation at this exit. | 3007 // instruction corresponding to this allocation at this exit. |
3049 MaterializeObjectInstr* AllocationSinking::MaterializationFor( | 3008 MaterializeObjectInstr* AllocationSinking::MaterializationFor( |
3050 Definition* alloc, | 3009 Definition* alloc, |
3051 Instruction* exit) { | 3010 Instruction* exit) { |
3052 if (exit->IsMaterializeObject()) { | 3011 if (exit->IsMaterializeObject()) { |
3053 exit = ExitForMaterialization(exit->AsMaterializeObject()); | 3012 exit = ExitForMaterialization(exit->AsMaterializeObject()); |
3054 } | 3013 } |
3055 | 3014 |
3056 for (MaterializeObjectInstr* mat = exit->previous()->AsMaterializeObject(); | 3015 for (MaterializeObjectInstr* mat = exit->previous()->AsMaterializeObject(); |
3057 mat != NULL; mat = mat->previous()->AsMaterializeObject()) { | 3016 mat != NULL; mat = mat->previous()->AsMaterializeObject()) { |
3058 if (mat->allocation() == alloc) { | 3017 if (mat->allocation() == alloc) { |
3059 return mat; | 3018 return mat; |
3060 } | 3019 } |
3061 } | 3020 } |
3062 | 3021 |
3063 return NULL; | 3022 return NULL; |
3064 } | 3023 } |
3065 | 3024 |
3066 | |
3067 // Insert MaterializeObject instruction for the given allocation before | 3025 // Insert MaterializeObject instruction for the given allocation before |
3068 // the given instruction that can deoptimize. | 3026 // the given instruction that can deoptimize. |
3069 void AllocationSinking::CreateMaterializationAt( | 3027 void AllocationSinking::CreateMaterializationAt( |
3070 Instruction* exit, | 3028 Instruction* exit, |
3071 Definition* alloc, | 3029 Definition* alloc, |
3072 const ZoneGrowableArray<const Object*>& slots) { | 3030 const ZoneGrowableArray<const Object*>& slots) { |
3073 ZoneGrowableArray<Value*>* values = | 3031 ZoneGrowableArray<Value*>* values = |
3074 new (Z) ZoneGrowableArray<Value*>(slots.length()); | 3032 new (Z) ZoneGrowableArray<Value*>(slots.length()); |
3075 | 3033 |
3076 // All loads should be inserted before the first materialization so that | 3034 // All loads should be inserted before the first materialization so that |
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3122 // This will allow us to discover it when we are looking for deoptimization | 3080 // This will allow us to discover it when we are looking for deoptimization |
3123 // exits for another allocation that potentially flows into this one. | 3081 // exits for another allocation that potentially flows into this one. |
3124 Value* val = new (Z) Value(alloc); | 3082 Value* val = new (Z) Value(alloc); |
3125 val->set_instruction(mat); | 3083 val->set_instruction(mat); |
3126 alloc->AddEnvUse(val); | 3084 alloc->AddEnvUse(val); |
3127 | 3085 |
3128 // Record inserted materialization. | 3086 // Record inserted materialization. |
3129 materializations_.Add(mat); | 3087 materializations_.Add(mat); |
3130 } | 3088 } |
3131 | 3089 |
3132 | |
3133 // Add given instruction to the list of the instructions if it is not yet | 3090 // Add given instruction to the list of the instructions if it is not yet |
3134 // present there. | 3091 // present there. |
3135 template <typename T> | 3092 template <typename T> |
3136 void AddInstruction(GrowableArray<T*>* list, T* value) { | 3093 void AddInstruction(GrowableArray<T*>* list, T* value) { |
3137 ASSERT(!value->IsGraphEntry()); | 3094 ASSERT(!value->IsGraphEntry()); |
3138 for (intptr_t i = 0; i < list->length(); i++) { | 3095 for (intptr_t i = 0; i < list->length(); i++) { |
3139 if ((*list)[i] == value) { | 3096 if ((*list)[i] == value) { |
3140 return; | 3097 return; |
3141 } | 3098 } |
3142 } | 3099 } |
3143 list->Add(value); | 3100 list->Add(value); |
3144 } | 3101 } |
3145 | 3102 |
3146 | |
3147 // Transitively collect all deoptimization exits that might need this allocation | 3103 // Transitively collect all deoptimization exits that might need this allocation |
3148 // rematerialized. It is not enough to collect only environment uses of this | 3104 // rematerialized. It is not enough to collect only environment uses of this |
3149 // allocation because it can flow into other objects that will be | 3105 // allocation because it can flow into other objects that will be |
3150 // dematerialized and that are referenced by deopt environments that | 3106 // dematerialized and that are referenced by deopt environments that |
3151 // don't contain this allocation explicitly. | 3107 // don't contain this allocation explicitly. |
3152 void AllocationSinking::ExitsCollector::Collect(Definition* alloc) { | 3108 void AllocationSinking::ExitsCollector::Collect(Definition* alloc) { |
3153 for (Value* use = alloc->env_use_list(); use != NULL; use = use->next_use()) { | 3109 for (Value* use = alloc->env_use_list(); use != NULL; use = use->next_use()) { |
3154 if (use->instruction()->IsMaterializeObject()) { | 3110 if (use->instruction()->IsMaterializeObject()) { |
3155 AddInstruction(&exits_, ExitForMaterialization( | 3111 AddInstruction(&exits_, ExitForMaterialization( |
3156 use->instruction()->AsMaterializeObject())); | 3112 use->instruction()->AsMaterializeObject())); |
3157 } else { | 3113 } else { |
3158 AddInstruction(&exits_, use->instruction()); | 3114 AddInstruction(&exits_, use->instruction()); |
3159 } | 3115 } |
3160 } | 3116 } |
3161 | 3117 |
3162 // Check if this allocation is stored into any other allocation sinking | 3118 // Check if this allocation is stored into any other allocation sinking |
3163 // candidate and put it on worklist so that we conservatively collect all | 3119 // candidate and put it on worklist so that we conservatively collect all |
3164 // exits for that candidate as well because they potentially might see | 3120 // exits for that candidate as well because they potentially might see |
3165 // this object. | 3121 // this object. |
3166 for (Value* use = alloc->input_use_list(); use != NULL; | 3122 for (Value* use = alloc->input_use_list(); use != NULL; |
3167 use = use->next_use()) { | 3123 use = use->next_use()) { |
3168 Definition* obj = StoreInto(use); | 3124 Definition* obj = StoreInto(use); |
3169 if ((obj != NULL) && (obj != alloc)) { | 3125 if ((obj != NULL) && (obj != alloc)) { |
3170 AddInstruction(&worklist_, obj); | 3126 AddInstruction(&worklist_, obj); |
3171 } | 3127 } |
3172 } | 3128 } |
3173 } | 3129 } |
3174 | 3130 |
3175 | |
3176 void AllocationSinking::ExitsCollector::CollectTransitively(Definition* alloc) { | 3131 void AllocationSinking::ExitsCollector::CollectTransitively(Definition* alloc) { |
3177 exits_.TruncateTo(0); | 3132 exits_.TruncateTo(0); |
3178 worklist_.TruncateTo(0); | 3133 worklist_.TruncateTo(0); |
3179 | 3134 |
3180 worklist_.Add(alloc); | 3135 worklist_.Add(alloc); |
3181 | 3136 |
3182 // Note: worklist potentially will grow while we are iterating over it. | 3137 // Note: worklist potentially will grow while we are iterating over it. |
3183 // We are not removing allocations from the worklist not to waste space on | 3138 // We are not removing allocations from the worklist not to waste space on |
3184 // the side maintaining BitVector of already processed allocations: worklist | 3139 // the side maintaining BitVector of already processed allocations: worklist |
3185 // is expected to be very small thus linear search in it is just as efficient | 3140 // is expected to be very small thus linear search in it is just as efficient |
3186 // as a bitvector. | 3141 // as a bitvector. |
3187 for (intptr_t i = 0; i < worklist_.length(); i++) { | 3142 for (intptr_t i = 0; i < worklist_.length(); i++) { |
3188 Collect(worklist_[i]); | 3143 Collect(worklist_[i]); |
3189 } | 3144 } |
3190 } | 3145 } |
3191 | 3146 |
3192 | |
3193 void AllocationSinking::InsertMaterializations(Definition* alloc) { | 3147 void AllocationSinking::InsertMaterializations(Definition* alloc) { |
3194 // Collect all fields that are written for this instance. | 3148 // Collect all fields that are written for this instance. |
3195 ZoneGrowableArray<const Object*>* slots = | 3149 ZoneGrowableArray<const Object*>* slots = |
3196 new (Z) ZoneGrowableArray<const Object*>(5); | 3150 new (Z) ZoneGrowableArray<const Object*>(5); |
3197 | 3151 |
3198 for (Value* use = alloc->input_use_list(); use != NULL; | 3152 for (Value* use = alloc->input_use_list(); use != NULL; |
3199 use = use->next_use()) { | 3153 use = use->next_use()) { |
3200 StoreInstanceFieldInstr* store = use->instruction()->AsStoreInstanceField(); | 3154 StoreInstanceFieldInstr* store = use->instruction()->AsStoreInstanceField(); |
3201 if ((store != NULL) && (store->instance()->definition() == alloc)) { | 3155 if ((store != NULL) && (store->instance()->definition() == alloc)) { |
3202 if (!store->field().IsNull()) { | 3156 if (!store->field().IsNull()) { |
(...skipping 14 matching lines...) Expand all Loading... |
3217 | 3171 |
3218 // Collect all instructions that mention this object in the environment. | 3172 // Collect all instructions that mention this object in the environment. |
3219 exits_collector_.CollectTransitively(alloc); | 3173 exits_collector_.CollectTransitively(alloc); |
3220 | 3174 |
3221 // Insert materializations at environment uses. | 3175 // Insert materializations at environment uses. |
3222 for (intptr_t i = 0; i < exits_collector_.exits().length(); i++) { | 3176 for (intptr_t i = 0; i < exits_collector_.exits().length(); i++) { |
3223 CreateMaterializationAt(exits_collector_.exits()[i], alloc, *slots); | 3177 CreateMaterializationAt(exits_collector_.exits()[i], alloc, *slots); |
3224 } | 3178 } |
3225 } | 3179 } |
3226 | 3180 |
3227 | |
3228 void TryCatchAnalyzer::Optimize(FlowGraph* flow_graph) { | 3181 void TryCatchAnalyzer::Optimize(FlowGraph* flow_graph) { |
3229 // For every catch-block: Iterate over all call instructions inside the | 3182 // For every catch-block: Iterate over all call instructions inside the |
3230 // corresponding try-block and figure out for each environment value if it | 3183 // corresponding try-block and figure out for each environment value if it |
3231 // is the same constant at all calls. If yes, replace the initial definition | 3184 // is the same constant at all calls. If yes, replace the initial definition |
3232 // at the catch-entry with this constant. | 3185 // at the catch-entry with this constant. |
3233 const GrowableArray<CatchBlockEntryInstr*>& catch_entries = | 3186 const GrowableArray<CatchBlockEntryInstr*>& catch_entries = |
3234 flow_graph->graph_entry()->catch_entries(); | 3187 flow_graph->graph_entry()->catch_entries(); |
3235 intptr_t base = kFirstLocalSlotFromFp + flow_graph->num_non_copied_params(); | 3188 intptr_t base = kFirstLocalSlotFromFp + flow_graph->num_non_copied_params(); |
3236 for (intptr_t catch_idx = 0; catch_idx < catch_entries.length(); | 3189 for (intptr_t catch_idx = 0; catch_idx < catch_entries.length(); |
3237 ++catch_idx) { | 3190 ++catch_idx) { |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3290 ConstantInstr* copy = | 3243 ConstantInstr* copy = |
3291 new (flow_graph->zone()) ConstantInstr(orig->value()); | 3244 new (flow_graph->zone()) ConstantInstr(orig->value()); |
3292 copy->set_ssa_temp_index(flow_graph->alloc_ssa_temp_index()); | 3245 copy->set_ssa_temp_index(flow_graph->alloc_ssa_temp_index()); |
3293 old->ReplaceUsesWith(copy); | 3246 old->ReplaceUsesWith(copy); |
3294 (*idefs)[j] = copy; | 3247 (*idefs)[j] = copy; |
3295 } | 3248 } |
3296 } | 3249 } |
3297 } | 3250 } |
3298 } | 3251 } |
3299 | 3252 |
3300 | |
3301 // Returns true iff this definition is used in a non-phi instruction. | 3253 // Returns true iff this definition is used in a non-phi instruction. |
3302 static bool HasRealUse(Definition* def) { | 3254 static bool HasRealUse(Definition* def) { |
3303 // Environment uses are real (non-phi) uses. | 3255 // Environment uses are real (non-phi) uses. |
3304 if (def->env_use_list() != NULL) return true; | 3256 if (def->env_use_list() != NULL) return true; |
3305 | 3257 |
3306 for (Value::Iterator it(def->input_use_list()); !it.Done(); it.Advance()) { | 3258 for (Value::Iterator it(def->input_use_list()); !it.Done(); it.Advance()) { |
3307 if (!it.Current()->instruction()->IsPhi()) return true; | 3259 if (!it.Current()->instruction()->IsPhi()) return true; |
3308 } | 3260 } |
3309 return false; | 3261 return false; |
3310 } | 3262 } |
3311 | 3263 |
3312 | |
3313 void DeadCodeElimination::EliminateDeadPhis(FlowGraph* flow_graph) { | 3264 void DeadCodeElimination::EliminateDeadPhis(FlowGraph* flow_graph) { |
3314 GrowableArray<PhiInstr*> live_phis; | 3265 GrowableArray<PhiInstr*> live_phis; |
3315 for (BlockIterator b = flow_graph->postorder_iterator(); !b.Done(); | 3266 for (BlockIterator b = flow_graph->postorder_iterator(); !b.Done(); |
3316 b.Advance()) { | 3267 b.Advance()) { |
3317 JoinEntryInstr* join = b.Current()->AsJoinEntry(); | 3268 JoinEntryInstr* join = b.Current()->AsJoinEntry(); |
3318 if (join != NULL) { | 3269 if (join != NULL) { |
3319 for (PhiIterator it(join); !it.Done(); it.Advance()) { | 3270 for (PhiIterator it(join); !it.Done(); it.Advance()) { |
3320 PhiInstr* phi = it.Current(); | 3271 PhiInstr* phi = it.Current(); |
3321 // Phis that have uses and phis inside try blocks are | 3272 // Phis that have uses and phis inside try blocks are |
3322 // marked as live. | 3273 // marked as live. |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3375 } | 3326 } |
3376 if (to_index == 0) { | 3327 if (to_index == 0) { |
3377 join->phis_ = NULL; | 3328 join->phis_ = NULL; |
3378 } else { | 3329 } else { |
3379 join->phis_->TruncateTo(to_index); | 3330 join->phis_->TruncateTo(to_index); |
3380 } | 3331 } |
3381 } | 3332 } |
3382 } | 3333 } |
3383 } | 3334 } |
3384 | 3335 |
3385 | |
3386 } // namespace dart | 3336 } // namespace dart |
OLD | NEW |