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" |
(...skipping 13 matching lines...) Expand all Loading... |
24 #define Z (zone()) | 24 #define Z (zone()) |
25 | 25 |
26 class CSEInstructionMap : public ValueObject { | 26 class CSEInstructionMap : public ValueObject { |
27 public: | 27 public: |
28 CSEInstructionMap() : map_() {} | 28 CSEInstructionMap() : map_() {} |
29 explicit CSEInstructionMap(const CSEInstructionMap& other) | 29 explicit CSEInstructionMap(const CSEInstructionMap& other) |
30 : ValueObject(), map_(other.map_) {} | 30 : ValueObject(), map_(other.map_) {} |
31 | 31 |
32 Instruction* Lookup(Instruction* other) const { | 32 Instruction* Lookup(Instruction* other) const { |
33 ASSERT(other->AllowsCSE()); | 33 ASSERT(other->AllowsCSE()); |
34 ASSERT(other->Dependencies().IsNone()); | |
35 return map_.LookupValue(other); | 34 return map_.LookupValue(other); |
36 } | 35 } |
37 | 36 |
38 void Insert(Instruction* instr) { | 37 void Insert(Instruction* instr) { |
39 ASSERT(instr->AllowsCSE()); | 38 ASSERT(instr->AllowsCSE()); |
40 ASSERT(instr->Dependencies().IsNone()); | |
41 return map_.Insert(instr); | 39 return map_.Insert(instr); |
42 } | 40 } |
43 | 41 |
44 private: | 42 private: |
45 typedef DirectChainedHashMap<PointerKeyValueTrait<Instruction> > Map; | 43 typedef DirectChainedHashMap<PointerKeyValueTrait<Instruction> > Map; |
46 | 44 |
47 Map map_; | 45 Map map_; |
48 }; | 46 }; |
49 | 47 |
50 // Place describes an abstract location (e.g. field) that IR can load | 48 // Place describes an abstract location (e.g. field) that IR can load |
(...skipping 1307 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1358 // Do not hoist any. | 1356 // Do not hoist any. |
1359 return; | 1357 return; |
1360 } | 1358 } |
1361 | 1359 |
1362 const ZoneGrowableArray<BlockEntryInstr*>& loop_headers = | 1360 const ZoneGrowableArray<BlockEntryInstr*>& loop_headers = |
1363 flow_graph()->LoopHeaders(); | 1361 flow_graph()->LoopHeaders(); |
1364 | 1362 |
1365 ZoneGrowableArray<BitVector*>* loop_invariant_loads = | 1363 ZoneGrowableArray<BitVector*>* loop_invariant_loads = |
1366 flow_graph()->loop_invariant_loads(); | 1364 flow_graph()->loop_invariant_loads(); |
1367 | 1365 |
1368 BlockEffects* block_effects = flow_graph()->block_effects(); | |
1369 | |
1370 for (intptr_t i = 0; i < loop_headers.length(); ++i) { | 1366 for (intptr_t i = 0; i < loop_headers.length(); ++i) { |
1371 BlockEntryInstr* header = loop_headers[i]; | 1367 BlockEntryInstr* header = loop_headers[i]; |
1372 // Skip loop that don't have a pre-header block. | 1368 // Skip loop that don't have a pre-header block. |
1373 BlockEntryInstr* pre_header = header->ImmediateDominator(); | 1369 BlockEntryInstr* pre_header = header->ImmediateDominator(); |
1374 if (pre_header == NULL) continue; | 1370 if (pre_header == NULL) continue; |
1375 | 1371 |
1376 for (BitVector::Iterator loop_it(header->loop_info()); !loop_it.Done(); | 1372 for (BitVector::Iterator loop_it(header->loop_info()); !loop_it.Done(); |
1377 loop_it.Advance()) { | 1373 loop_it.Advance()) { |
1378 BlockEntryInstr* block = flow_graph()->preorder()[loop_it.Current()]; | 1374 BlockEntryInstr* block = flow_graph()->preorder()[loop_it.Current()]; |
1379 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { | 1375 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { |
1380 Instruction* current = it.Current(); | 1376 Instruction* current = it.Current(); |
1381 if ((current->AllowsCSE() && | 1377 if (current->AllowsCSE() || |
1382 block_effects->CanBeMovedTo(current, pre_header)) || | |
1383 IsLoopInvariantLoad(loop_invariant_loads, i, current)) { | 1378 IsLoopInvariantLoad(loop_invariant_loads, i, current)) { |
1384 bool inputs_loop_invariant = true; | 1379 bool inputs_loop_invariant = true; |
1385 for (int i = 0; i < current->InputCount(); ++i) { | 1380 for (int i = 0; i < current->InputCount(); ++i) { |
1386 Definition* input_def = current->InputAt(i)->definition(); | 1381 Definition* input_def = current->InputAt(i)->definition(); |
1387 if (!input_def->GetBlock()->Dominates(pre_header)) { | 1382 if (!input_def->GetBlock()->Dominates(pre_header)) { |
1388 inputs_loop_invariant = false; | 1383 inputs_loop_invariant = false; |
1389 break; | 1384 break; |
1390 } | 1385 } |
1391 } | 1386 } |
1392 if (inputs_loop_invariant && !current->IsAssertAssignable() && | 1387 if (inputs_loop_invariant && !current->IsAssertAssignable() && |
(...skipping 691 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2084 } | 2079 } |
2085 | 2080 |
2086 return true; | 2081 return true; |
2087 } | 2082 } |
2088 | 2083 |
2089 // Returns true if definitions are congruent assuming their inputs | 2084 // Returns true if definitions are congruent assuming their inputs |
2090 // are congruent. | 2085 // are congruent. |
2091 bool CanBeCongruent(Definition* a, Definition* b) { | 2086 bool CanBeCongruent(Definition* a, Definition* b) { |
2092 return (a->tag() == b->tag()) && | 2087 return (a->tag() == b->tag()) && |
2093 ((a->IsPhi() && (a->GetBlock() == b->GetBlock())) || | 2088 ((a->IsPhi() && (a->GetBlock() == b->GetBlock())) || |
2094 (a->AllowsCSE() && a->Dependencies().IsNone() && | 2089 (a->AllowsCSE() && a->AttributesEqual(b))); |
2095 a->AttributesEqual(b))); | |
2096 } | 2090 } |
2097 | 2091 |
2098 // Given two definitions check if they are congruent under assumption that | 2092 // Given two definitions check if they are congruent under assumption that |
2099 // their inputs will be proven congruent. If they are - add them to the | 2093 // their inputs will be proven congruent. If they are - add them to the |
2100 // worklist to check their inputs' congruency. | 2094 // worklist to check their inputs' congruency. |
2101 // Returns true if pair was added to the worklist or is already in the | 2095 // Returns true if pair was added to the worklist or is already in the |
2102 // worklist and false if a and b are not congruent. | 2096 // worklist and false if a and b are not congruent. |
2103 bool AddPairToCongruencyWorklist(Definition* a, Definition* b) { | 2097 bool AddPairToCongruencyWorklist(Definition* a, Definition* b) { |
2104 if (!CanBeCongruent(a, b)) { | 2098 if (!CanBeCongruent(a, b)) { |
2105 return false; | 2099 return false; |
(...skipping 221 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2327 } | 2321 } |
2328 | 2322 |
2329 bool DominatorBasedCSE::OptimizeRecursive(FlowGraph* graph, | 2323 bool DominatorBasedCSE::OptimizeRecursive(FlowGraph* graph, |
2330 BlockEntryInstr* block, | 2324 BlockEntryInstr* block, |
2331 CSEInstructionMap* map) { | 2325 CSEInstructionMap* map) { |
2332 bool changed = false; | 2326 bool changed = false; |
2333 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { | 2327 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { |
2334 Instruction* current = it.Current(); | 2328 Instruction* current = it.Current(); |
2335 if (current->AllowsCSE()) { | 2329 if (current->AllowsCSE()) { |
2336 Instruction* replacement = map->Lookup(current); | 2330 Instruction* replacement = map->Lookup(current); |
2337 ASSERT((replacement == NULL) || replacement->AllowsCSE()); | 2331 |
2338 if ((replacement != NULL) && | 2332 if (replacement != NULL) { |
2339 graph->block_effects()->IsAvailableAt(replacement, block)) { | |
2340 // Replace current with lookup result. | 2333 // Replace current with lookup result. |
| 2334 ASSERT(replacement->AllowsCSE()); |
2341 graph->ReplaceCurrentInstruction(&it, current, replacement); | 2335 graph->ReplaceCurrentInstruction(&it, current, replacement); |
2342 changed = true; | 2336 changed = true; |
2343 continue; | 2337 continue; |
2344 } | 2338 } |
2345 | 2339 |
2346 // For simplicity we assume that instruction either does not depend on | |
2347 // anything or does not affect anything. If this is not the case then | |
2348 // we should first remove affected instructions from the map and | |
2349 // then add instruction to the map so that it does not kill itself. | |
2350 ASSERT(!current->HasUnknownSideEffects() || | |
2351 current->Dependencies().IsNone()); | |
2352 map->Insert(current); | 2340 map->Insert(current); |
2353 } | 2341 } |
2354 } | 2342 } |
2355 | 2343 |
2356 // Process children in the dominator tree recursively. | 2344 // Process children in the dominator tree recursively. |
2357 intptr_t num_children = block->dominated_blocks().length(); | 2345 intptr_t num_children = block->dominated_blocks().length(); |
2358 if (num_children != 0) { | 2346 if (num_children != 0) { |
2359 graph->thread()->CheckForSafepoint(); | 2347 graph->thread()->CheckForSafepoint(); |
2360 } | 2348 } |
2361 for (intptr_t i = 0; i < num_children; ++i) { | 2349 for (intptr_t i = 0; i < num_children; ++i) { |
(...skipping 943 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3305 if (to_index == 0) { | 3293 if (to_index == 0) { |
3306 join->phis_ = NULL; | 3294 join->phis_ = NULL; |
3307 } else { | 3295 } else { |
3308 join->phis_->TruncateTo(to_index); | 3296 join->phis_->TruncateTo(to_index); |
3309 } | 3297 } |
3310 } | 3298 } |
3311 } | 3299 } |
3312 } | 3300 } |
3313 | 3301 |
3314 } // namespace dart | 3302 } // namespace dart |
OLD | NEW |