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 |