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/flow_graph.h" | 9 #include "vm/flow_graph.h" |
10 | 10 |
11 namespace dart { | 11 namespace dart { |
12 | 12 |
13 DEFINE_FLAG(bool, emit_edge_counters, true, "Emit edge counters at targets."); | 13 DEFINE_FLAG(bool, emit_edge_counters, true, "Emit edge counters at targets."); |
14 | 14 |
15 // Compute the edge count at the deopt id of a TargetEntry or Goto. | 15 // Compute the edge count at the deopt id of a TargetEntry or Goto. |
16 static intptr_t ComputeEdgeCount(const Code& unoptimized_code, | 16 static intptr_t ComputeEdgeCount( |
17 intptr_t deopt_id) { | 17 const Code& unoptimized_code, |
| 18 const ZoneGrowableArray<uword>& deopt_id_pc_pairs, |
| 19 intptr_t deopt_id) { |
18 ASSERT(deopt_id != Isolate::kNoDeoptId); | 20 ASSERT(deopt_id != Isolate::kNoDeoptId); |
19 | 21 |
20 if (!FLAG_emit_edge_counters) { | 22 if (!FLAG_emit_edge_counters) { |
21 // Assume everything was visited once. | 23 // Assume everything was visited once. |
22 return 1; | 24 return 1; |
23 } | 25 } |
24 const uword pc = | 26 |
25 unoptimized_code.GetPcForDeoptId(deopt_id, RawPcDescriptors::kDeopt); | 27 for (intptr_t i = 0; i < deopt_id_pc_pairs.length(); i += 2) { |
26 Array& array = Array::Handle(); | 28 intptr_t deopt_id_entry = static_cast<intptr_t>(deopt_id_pc_pairs[i]); |
27 array ^= CodePatcher::GetEdgeCounterAt(pc, unoptimized_code); | 29 uword pc = deopt_id_pc_pairs[i + 1]; |
28 ASSERT(!array.IsNull()); | 30 if (deopt_id_entry == deopt_id) { |
29 return Smi::Value(Smi::RawCast(array.At(0))); | 31 Array& array = Array::Handle(); |
| 32 array ^= CodePatcher::GetEdgeCounterAt(pc, unoptimized_code); |
| 33 ASSERT(!array.IsNull()); |
| 34 return Smi::Value(Smi::RawCast(array.At(0))); |
| 35 } |
| 36 } |
| 37 |
| 38 UNREACHABLE(); |
| 39 return 1; |
30 } | 40 } |
31 | 41 |
32 | 42 |
33 // There is an edge from instruction->successor. Set its weight (edge count | 43 // There is an edge from instruction->successor. Set its weight (edge count |
34 // per function entry). | 44 // per function entry). |
35 static void SetEdgeWeight(Instruction* instruction, | 45 static void SetEdgeWeight(Instruction* instruction, |
36 BlockEntryInstr* successor, | 46 BlockEntryInstr* successor, |
37 const Code& unoptimized_code, | 47 const Code& unoptimized_code, |
| 48 const ZoneGrowableArray<uword>& deopt_id_pc_pairs, |
38 intptr_t entry_count) { | 49 intptr_t entry_count) { |
39 TargetEntryInstr* target = successor->AsTargetEntry(); | 50 TargetEntryInstr* target = successor->AsTargetEntry(); |
40 if (target != NULL) { | 51 if (target != NULL) { |
41 // If this block ends in a goto, the edge count of this edge is the same | 52 // If this block ends in a goto, the edge count of this edge is the same |
42 // as the count on the single outgoing edge. This is true as long as the | 53 // as the count on the single outgoing edge. This is true as long as the |
43 // block does not throw an exception. | 54 // block does not throw an exception. |
44 GotoInstr* jump = target->last_instruction()->AsGoto(); | 55 GotoInstr* jump = target->last_instruction()->AsGoto(); |
45 const intptr_t deopt_id = | 56 const intptr_t deopt_id = |
46 (jump != NULL) ? jump->deopt_id() : target->deopt_id(); | 57 (jump != NULL) ? jump->deopt_id() : target->deopt_id(); |
47 intptr_t count = ComputeEdgeCount(unoptimized_code, deopt_id); | 58 intptr_t count = ComputeEdgeCount(unoptimized_code, |
| 59 deopt_id_pc_pairs, |
| 60 deopt_id); |
48 if ((count >= 0) && (entry_count != 0)) { | 61 if ((count >= 0) && (entry_count != 0)) { |
49 double weight = | 62 double weight = |
50 static_cast<double>(count) / static_cast<double>(entry_count); | 63 static_cast<double>(count) / static_cast<double>(entry_count); |
51 target->set_edge_weight(weight); | 64 target->set_edge_weight(weight); |
52 } | 65 } |
53 } else { | 66 } else { |
54 GotoInstr* jump = instruction->AsGoto(); | 67 GotoInstr* jump = instruction->AsGoto(); |
55 if (jump != NULL) { | 68 if (jump != NULL) { |
56 intptr_t count = ComputeEdgeCount(unoptimized_code, jump->deopt_id()); | 69 intptr_t count = ComputeEdgeCount(unoptimized_code, |
| 70 deopt_id_pc_pairs, |
| 71 jump->deopt_id()); |
57 if ((count >= 0) && (entry_count != 0)) { | 72 if ((count >= 0) && (entry_count != 0)) { |
58 double weight = | 73 double weight = |
59 static_cast<double>(count) / static_cast<double>(entry_count); | 74 static_cast<double>(count) / static_cast<double>(entry_count); |
60 jump->set_edge_weight(weight); | 75 jump->set_edge_weight(weight); |
61 } | 76 } |
62 } | 77 } |
63 } | 78 } |
64 } | 79 } |
65 | 80 |
66 | 81 |
67 void BlockScheduler::AssignEdgeWeights() const { | 82 void BlockScheduler::AssignEdgeWeights() const { |
68 const Code& unoptimized_code = flow_graph()->parsed_function().code(); | 83 const Code& unoptimized_code = flow_graph()->parsed_function().code(); |
69 ASSERT(!unoptimized_code.IsNull()); | 84 ASSERT(!unoptimized_code.IsNull()); |
70 | 85 |
| 86 ZoneGrowableArray<uword>* deopt_id_pc_pairs = new ZoneGrowableArray<uword>(); |
| 87 const PcDescriptors& descriptors = |
| 88 PcDescriptors::Handle(unoptimized_code.pc_descriptors()); |
| 89 PcDescriptors::Iterator iter(descriptors, RawPcDescriptors::kDeopt); |
| 90 uword entry = unoptimized_code.EntryPoint(); |
| 91 while (iter.MoveNext()) { |
| 92 intptr_t deopt_id = iter.DeoptId(); |
| 93 ASSERT(deopt_id != Isolate::kNoDeoptId); |
| 94 uint32_t pc_offset = iter.PcOffset(); |
| 95 deopt_id_pc_pairs->Add(static_cast<uword>(deopt_id)); |
| 96 deopt_id_pc_pairs->Add(entry + pc_offset); |
| 97 } |
| 98 |
71 intptr_t entry_count = | 99 intptr_t entry_count = |
72 ComputeEdgeCount(unoptimized_code, | 100 ComputeEdgeCount(unoptimized_code, |
| 101 *deopt_id_pc_pairs, |
73 flow_graph()->graph_entry()->normal_entry()->deopt_id()); | 102 flow_graph()->graph_entry()->normal_entry()->deopt_id()); |
74 flow_graph()->graph_entry()->set_entry_count(entry_count); | 103 flow_graph()->graph_entry()->set_entry_count(entry_count); |
75 | 104 |
76 for (BlockIterator it = flow_graph()->reverse_postorder_iterator(); | 105 for (BlockIterator it = flow_graph()->reverse_postorder_iterator(); |
77 !it.Done(); | 106 !it.Done(); |
78 it.Advance()) { | 107 it.Advance()) { |
79 BlockEntryInstr* block = it.Current(); | 108 BlockEntryInstr* block = it.Current(); |
80 Instruction* last = block->last_instruction(); | 109 Instruction* last = block->last_instruction(); |
81 for (intptr_t i = 0; i < last->SuccessorCount(); ++i) { | 110 for (intptr_t i = 0; i < last->SuccessorCount(); ++i) { |
82 BlockEntryInstr* succ = last->SuccessorAt(i); | 111 BlockEntryInstr* succ = last->SuccessorAt(i); |
83 SetEdgeWeight(last, succ, unoptimized_code, entry_count); | 112 SetEdgeWeight(last, succ, |
| 113 unoptimized_code, *deopt_id_pc_pairs, entry_count); |
84 } | 114 } |
85 } | 115 } |
86 } | 116 } |
87 | 117 |
88 | 118 |
89 // A weighted control-flow graph edge. | 119 // A weighted control-flow graph edge. |
90 struct Edge { | 120 struct Edge { |
91 Edge(BlockEntryInstr* source, BlockEntryInstr* target, double weight) | 121 Edge(BlockEntryInstr* source, BlockEntryInstr* target, double weight) |
92 : source(source), target(target), weight(weight) { } | 122 : source(source), target(target), weight(weight) { } |
93 | 123 |
(...skipping 115 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
209 for (intptr_t i = block_count - 1; i >= 0; --i) { | 239 for (intptr_t i = block_count - 1; i >= 0; --i) { |
210 if (chains[i]->first->block == flow_graph()->postorder()[i]) { | 240 if (chains[i]->first->block == flow_graph()->postorder()[i]) { |
211 for (Link* link = chains[i]->first; link != NULL; link = link->next) { | 241 for (Link* link = chains[i]->first; link != NULL; link = link->next) { |
212 flow_graph()->CodegenBlockOrder(true)->Add(link->block); | 242 flow_graph()->CodegenBlockOrder(true)->Add(link->block); |
213 } | 243 } |
214 } | 244 } |
215 } | 245 } |
216 } | 246 } |
217 | 247 |
218 } // namespace dart | 248 } // namespace dart |
OLD | NEW |