| OLD | NEW |
| 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, 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/block_scheduler.h" | 5 #include "vm/block_scheduler.h" |
| 6 | 6 |
| 7 #include "vm/allocation.h" | 7 #include "vm/allocation.h" |
| 8 #include "vm/code_patcher.h" | 8 #include "vm/code_patcher.h" |
| 9 #include "vm/compiler.h" | 9 #include "vm/compiler.h" |
| 10 #include "vm/flow_graph.h" | 10 #include "vm/flow_graph.h" |
| (...skipping 22 matching lines...) Expand all Loading... |
| 33 // block does not throw an exception. | 33 // block does not throw an exception. |
| 34 intptr_t count = GetEdgeCount(edge_counters, target->preorder_number()); | 34 intptr_t count = GetEdgeCount(edge_counters, target->preorder_number()); |
| 35 if ((count >= 0) && (entry_count != 0)) { | 35 if ((count >= 0) && (entry_count != 0)) { |
| 36 double weight = | 36 double weight = |
| 37 static_cast<double>(count) / static_cast<double>(entry_count); | 37 static_cast<double>(count) / static_cast<double>(entry_count); |
| 38 target->set_edge_weight(weight); | 38 target->set_edge_weight(weight); |
| 39 } | 39 } |
| 40 } else { | 40 } else { |
| 41 GotoInstr* jump = block->last_instruction()->AsGoto(); | 41 GotoInstr* jump = block->last_instruction()->AsGoto(); |
| 42 if (jump != NULL) { | 42 if (jump != NULL) { |
| 43 intptr_t count = | 43 intptr_t count = GetEdgeCount(edge_counters, block->preorder_number()); |
| 44 GetEdgeCount(edge_counters, block->preorder_number()); | |
| 45 if ((count >= 0) && (entry_count != 0)) { | 44 if ((count >= 0) && (entry_count != 0)) { |
| 46 double weight = | 45 double weight = |
| 47 static_cast<double>(count) / static_cast<double>(entry_count); | 46 static_cast<double>(count) / static_cast<double>(entry_count); |
| 48 jump->set_edge_weight(weight); | 47 jump->set_edge_weight(weight); |
| 49 } | 48 } |
| 50 } | 49 } |
| 51 } | 50 } |
| 52 } | 51 } |
| 53 | 52 |
| 54 | 53 |
| 55 void BlockScheduler::AssignEdgeWeights() const { | 54 void BlockScheduler::AssignEdgeWeights() const { |
| 56 if (!FLAG_reorder_basic_blocks) { | 55 if (!FLAG_reorder_basic_blocks) { |
| 57 return; | 56 return; |
| 58 } | 57 } |
| 59 | 58 |
| 60 const Array& ic_data_array = Array::Handle(flow_graph()->zone(), | 59 const Array& ic_data_array = |
| 61 flow_graph()->parsed_function().function().ic_data_array()); | 60 Array::Handle(flow_graph()->zone(), |
| 61 flow_graph()->parsed_function().function().ic_data_array()); |
| 62 if (Compiler::IsBackgroundCompilation() && ic_data_array.IsNull()) { | 62 if (Compiler::IsBackgroundCompilation() && ic_data_array.IsNull()) { |
| 63 // Deferred loading cleared ic_data_array. | 63 // Deferred loading cleared ic_data_array. |
| 64 Compiler::AbortBackgroundCompilation(Thread::kNoDeoptId, | 64 Compiler::AbortBackgroundCompilation( |
| 65 "BlockScheduler: ICData array cleared"); | 65 Thread::kNoDeoptId, "BlockScheduler: ICData array cleared"); |
| 66 } | 66 } |
| 67 if (ic_data_array.IsNull()) { | 67 if (ic_data_array.IsNull()) { |
| 68 ASSERT(Isolate::Current()->HasAttemptedReload()); | 68 ASSERT(Isolate::Current()->HasAttemptedReload()); |
| 69 return; | 69 return; |
| 70 } | 70 } |
| 71 Array& edge_counters = Array::Handle(); | 71 Array& edge_counters = Array::Handle(); |
| 72 edge_counters ^= ic_data_array.At(0); | 72 edge_counters ^= ic_data_array.At(0); |
| 73 | 73 |
| 74 intptr_t entry_count = GetEdgeCount( | 74 intptr_t entry_count = GetEdgeCount( |
| 75 edge_counters, | 75 edge_counters, |
| 76 flow_graph()->graph_entry()->normal_entry()->preorder_number()); | 76 flow_graph()->graph_entry()->normal_entry()->preorder_number()); |
| 77 flow_graph()->graph_entry()->set_entry_count(entry_count); | 77 flow_graph()->graph_entry()->set_entry_count(entry_count); |
| 78 | 78 |
| 79 for (BlockIterator it = flow_graph()->reverse_postorder_iterator(); | 79 for (BlockIterator it = flow_graph()->reverse_postorder_iterator(); |
| 80 !it.Done(); | 80 !it.Done(); it.Advance()) { |
| 81 it.Advance()) { | |
| 82 BlockEntryInstr* block = it.Current(); | 81 BlockEntryInstr* block = it.Current(); |
| 83 Instruction* last = block->last_instruction(); | 82 Instruction* last = block->last_instruction(); |
| 84 for (intptr_t i = 0; i < last->SuccessorCount(); ++i) { | 83 for (intptr_t i = 0; i < last->SuccessorCount(); ++i) { |
| 85 BlockEntryInstr* succ = last->SuccessorAt(i); | 84 BlockEntryInstr* succ = last->SuccessorAt(i); |
| 86 SetEdgeWeight(block, succ, edge_counters, entry_count); | 85 SetEdgeWeight(block, succ, edge_counters, entry_count); |
| 87 } | 86 } |
| 88 } | 87 } |
| 89 } | 88 } |
| 90 | 89 |
| 91 | 90 |
| 92 // A weighted control-flow graph edge. | 91 // A weighted control-flow graph edge. |
| 93 struct Edge { | 92 struct Edge { |
| 94 Edge(BlockEntryInstr* source, BlockEntryInstr* target, double weight) | 93 Edge(BlockEntryInstr* source, BlockEntryInstr* target, double weight) |
| 95 : source(source), target(target), weight(weight) { } | 94 : source(source), target(target), weight(weight) {} |
| 96 | 95 |
| 97 static int LowestWeightFirst(const Edge* a, const Edge* b); | 96 static int LowestWeightFirst(const Edge* a, const Edge* b); |
| 98 | 97 |
| 99 BlockEntryInstr* source; | 98 BlockEntryInstr* source; |
| 100 BlockEntryInstr* target; | 99 BlockEntryInstr* target; |
| 101 double weight; | 100 double weight; |
| 102 }; | 101 }; |
| 103 | 102 |
| 104 | 103 |
| 105 // A linked list node in a chain of blocks. | 104 // A linked list node in a chain of blocks. |
| 106 struct Link : public ZoneAllocated { | 105 struct Link : public ZoneAllocated { |
| 107 Link(BlockEntryInstr* block, Link* next) : block(block), next(next) { } | 106 Link(BlockEntryInstr* block, Link* next) : block(block), next(next) {} |
| 108 | 107 |
| 109 BlockEntryInstr* block; | 108 BlockEntryInstr* block; |
| 110 Link* next; | 109 Link* next; |
| 111 }; | 110 }; |
| 112 | 111 |
| 113 | 112 |
| 114 // A chain of blocks with first and last pointers for fast concatenation and | 113 // A chain of blocks with first and last pointers for fast concatenation and |
| 115 // a length to support adding a shorter chain's links to a longer chain. | 114 // a length to support adding a shorter chain's links to a longer chain. |
| 116 struct Chain : public ZoneAllocated { | 115 struct Chain : public ZoneAllocated { |
| 117 explicit Chain(BlockEntryInstr* block) | 116 explicit Chain(BlockEntryInstr* block) |
| 118 : first(new Link(block, NULL)), last(first), length(1) { } | 117 : first(new Link(block, NULL)), last(first), length(1) {} |
| 119 | 118 |
| 120 Link* first; | 119 Link* first; |
| 121 Link* last; | 120 Link* last; |
| 122 intptr_t length; | 121 intptr_t length; |
| 123 }; | 122 }; |
| 124 | 123 |
| 125 | 124 |
| 126 int Edge::LowestWeightFirst(const Edge* a, const Edge* b) { | 125 int Edge::LowestWeightFirst(const Edge* a, const Edge* b) { |
| 127 if (a->weight < b->weight) { | 126 if (a->weight < b->weight) { |
| 128 return -1; | 127 return -1; |
| (...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 161 // sorted by weight. | 160 // sorted by weight. |
| 162 intptr_t block_count = flow_graph()->preorder().length(); | 161 intptr_t block_count = flow_graph()->preorder().length(); |
| 163 GrowableArray<Edge> edges(2 * block_count); | 162 GrowableArray<Edge> edges(2 * block_count); |
| 164 | 163 |
| 165 // A map from a block's postorder number to the chain it is in. Used to | 164 // A map from a block's postorder number to the chain it is in. Used to |
| 166 // implement a simple (ordered) union-find data structure. Chains are | 165 // implement a simple (ordered) union-find data structure. Chains are |
| 167 // stored by pointer so that they are aliased (mutating one mutates all | 166 // stored by pointer so that they are aliased (mutating one mutates all |
| 168 // shared ones). Find(n) is simply chains[n]. | 167 // shared ones). Find(n) is simply chains[n]. |
| 169 GrowableArray<Chain*> chains(block_count); | 168 GrowableArray<Chain*> chains(block_count); |
| 170 | 169 |
| 171 for (BlockIterator it = flow_graph()->postorder_iterator(); | 170 for (BlockIterator it = flow_graph()->postorder_iterator(); !it.Done(); |
| 172 !it.Done(); | |
| 173 it.Advance()) { | 171 it.Advance()) { |
| 174 BlockEntryInstr* block = it.Current(); | 172 BlockEntryInstr* block = it.Current(); |
| 175 chains.Add(new Chain(block)); | 173 chains.Add(new Chain(block)); |
| 176 | 174 |
| 177 Instruction* last = block->last_instruction(); | 175 Instruction* last = block->last_instruction(); |
| 178 for (intptr_t i = 0; i < last->SuccessorCount(); ++i) { | 176 for (intptr_t i = 0; i < last->SuccessorCount(); ++i) { |
| 179 BlockEntryInstr* succ = last->SuccessorAt(i); | 177 BlockEntryInstr* succ = last->SuccessorAt(i); |
| 180 double weight = 0.0; | 178 double weight = 0.0; |
| 181 if (succ->IsTargetEntry()) { | 179 if (succ->IsTargetEntry()) { |
| 182 weight = succ->AsTargetEntry()->edge_weight(); | 180 weight = succ->AsTargetEntry()->edge_weight(); |
| (...skipping 29 matching lines...) Expand all Loading... |
| 212 for (intptr_t i = block_count - 1; i >= 0; --i) { | 210 for (intptr_t i = block_count - 1; i >= 0; --i) { |
| 213 if (chains[i]->first->block == flow_graph()->postorder()[i]) { | 211 if (chains[i]->first->block == flow_graph()->postorder()[i]) { |
| 214 for (Link* link = chains[i]->first; link != NULL; link = link->next) { | 212 for (Link* link = chains[i]->first; link != NULL; link = link->next) { |
| 215 flow_graph()->CodegenBlockOrder(true)->Add(link->block); | 213 flow_graph()->CodegenBlockOrder(true)->Add(link->block); |
| 216 } | 214 } |
| 217 } | 215 } |
| 218 } | 216 } |
| 219 } | 217 } |
| 220 | 218 |
| 221 } // namespace dart | 219 } // namespace dart |
| OLD | NEW |