Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(26)

Side by Side Diff: src/compiler/scheduler.cc

Issue 687133003: Cleanup unscheduled use count for controls of coupled nodes. (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Addressed moar comments by Ben Titzer. Created 6 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « src/compiler/scheduler.h ('k') | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright 2013 the V8 project authors. All rights reserved. 1 // Copyright 2013 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be 2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. 3 // found in the LICENSE file.
4 4
5 #include <deque> 5 #include <deque>
6 #include <queue> 6 #include <queue>
7 7
8 #include "src/compiler/scheduler.h" 8 #include "src/compiler/scheduler.h"
9 9
10 #include "src/compiler/graph.h" 10 #include "src/compiler/graph.h"
(...skipping 104 matching lines...) Expand 10 before | Expand all | Expand 10 after
115 UNREACHABLE(); 115 UNREACHABLE();
116 break; 116 break;
117 case IrOpcode::kPhi: 117 case IrOpcode::kPhi:
118 case IrOpcode::kEffectPhi: { 118 case IrOpcode::kEffectPhi: {
119 // Phis and effect phis are coupled to their respective blocks. 119 // Phis and effect phis are coupled to their respective blocks.
120 DCHECK_EQ(Scheduler::kCoupled, data->placement_); 120 DCHECK_EQ(Scheduler::kCoupled, data->placement_);
121 DCHECK_EQ(Scheduler::kFixed, placement); 121 DCHECK_EQ(Scheduler::kFixed, placement);
122 Node* control = NodeProperties::GetControlInput(node); 122 Node* control = NodeProperties::GetControlInput(node);
123 BasicBlock* block = schedule_->block(control); 123 BasicBlock* block = schedule_->block(control);
124 schedule_->AddNode(block, node); 124 schedule_->AddNode(block, node);
125 // TODO(mstarzinger): Cheap hack to make sure unscheduled use count of
126 // control does not drop below zero. This might cause the control to be
127 // queued for scheduling more than once, which makes this ugly!
128 ++(GetData(control)->unscheduled_count_);
129 break; 125 break;
130 } 126 }
131 #define DEFINE_FLOATING_CONTROL_CASE(V) case IrOpcode::k##V: 127 #define DEFINE_FLOATING_CONTROL_CASE(V) case IrOpcode::k##V:
132 CONTROL_OP_LIST(DEFINE_FLOATING_CONTROL_CASE) 128 CONTROL_OP_LIST(DEFINE_FLOATING_CONTROL_CASE)
133 #undef DEFINE_FLOATING_CONTROL_CASE 129 #undef DEFINE_FLOATING_CONTROL_CASE
134 { 130 {
135 // Control nodes force coupled uses to be placed. 131 // Control nodes force coupled uses to be placed.
136 Node::Uses uses = node->uses(); 132 Node::Uses uses = node->uses();
137 for (Node::Uses::iterator i = uses.begin(); i != uses.end(); ++i) { 133 for (Node::Uses::iterator i = uses.begin(); i != uses.end(); ++i) {
138 if (GetPlacement(*i) == Scheduler::kCoupled) { 134 if (GetPlacement(*i) == Scheduler::kCoupled) {
139 DCHECK_EQ(node, NodeProperties::GetControlInput(*i)); 135 DCHECK_EQ(node, NodeProperties::GetControlInput(*i));
140 UpdatePlacement(*i, placement); 136 UpdatePlacement(*i, placement);
141 } 137 }
142 } 138 }
143 break; 139 break;
144 } 140 }
145 default: 141 default:
146 DCHECK_EQ(Scheduler::kSchedulable, data->placement_); 142 DCHECK_EQ(Scheduler::kSchedulable, data->placement_);
147 DCHECK_EQ(Scheduler::kScheduled, placement); 143 DCHECK_EQ(Scheduler::kScheduled, placement);
148 break; 144 break;
149 } 145 }
150 // Reduce the use count of the node's inputs to potentially make them 146 // Reduce the use count of the node's inputs to potentially make them
151 // schedulable. If all the uses of a node have been scheduled, then the node 147 // schedulable. If all the uses of a node have been scheduled, then the node
152 // itself can be scheduled. 148 // itself can be scheduled.
153 for (InputIter i = node->inputs().begin(); i != node->inputs().end(); ++i) { 149 for (InputIter i = node->inputs().begin(); i != node->inputs().end(); ++i) {
154 // TODO(mstarzinger): Another cheap hack for use counts. 150 // TODO(mstarzinger): Another cheap hack for use counts.
155 if (GetData(*i)->placement_ == kFixed) continue; 151 if (GetData(*i)->placement_ == kFixed) continue;
156 DecrementUnscheduledUseCount(*i, i.edge().from()); 152 DecrementUnscheduledUseCount(*i, i.index(), i.edge().from());
157 } 153 }
158 } 154 }
159 data->placement_ = placement; 155 data->placement_ = placement;
160 } 156 }
161 157
162 158
163 void Scheduler::IncrementUnscheduledUseCount(Node* node, Node* from) { 159 bool Scheduler::IsCoupledControlEdge(Node* node, int index) {
160 return GetPlacement(node) == kCoupled &&
161 NodeProperties::FirstControlIndex(node) == index;
162 }
163
164
165 void Scheduler::IncrementUnscheduledUseCount(Node* node, int index,
166 Node* from) {
167 // Make sure that control edges from coupled nodes are not counted.
168 if (IsCoupledControlEdge(from, index)) return;
169
170 // Use count for coupled nodes is summed up on their control.
164 if (GetPlacement(node) == kCoupled) { 171 if (GetPlacement(node) == kCoupled) {
165 // Use count for coupled nodes is summed up on their control.
166 Node* control = NodeProperties::GetControlInput(node); 172 Node* control = NodeProperties::GetControlInput(node);
167 return IncrementUnscheduledUseCount(control, from); 173 return IncrementUnscheduledUseCount(control, index, from);
168 } 174 }
175
169 ++(GetData(node)->unscheduled_count_); 176 ++(GetData(node)->unscheduled_count_);
170 if (FLAG_trace_turbo_scheduler) { 177 if (FLAG_trace_turbo_scheduler) {
171 Trace(" Use count of #%d:%s (used by #%d:%s)++ = %d\n", node->id(), 178 Trace(" Use count of #%d:%s (used by #%d:%s)++ = %d\n", node->id(),
172 node->op()->mnemonic(), from->id(), from->op()->mnemonic(), 179 node->op()->mnemonic(), from->id(), from->op()->mnemonic(),
173 GetData(node)->unscheduled_count_); 180 GetData(node)->unscheduled_count_);
174 } 181 }
175 } 182 }
176 183
177 184
178 void Scheduler::DecrementUnscheduledUseCount(Node* node, Node* from) { 185 void Scheduler::DecrementUnscheduledUseCount(Node* node, int index,
186 Node* from) {
187 // Make sure that control edges from coupled nodes are not counted.
188 if (IsCoupledControlEdge(from, index)) return;
189
190 // Use count for coupled nodes is summed up on their control.
179 if (GetPlacement(node) == kCoupled) { 191 if (GetPlacement(node) == kCoupled) {
180 // Use count for coupled nodes is summed up on their control.
181 Node* control = NodeProperties::GetControlInput(node); 192 Node* control = NodeProperties::GetControlInput(node);
182 return DecrementUnscheduledUseCount(control, from); 193 return DecrementUnscheduledUseCount(control, index, from);
183 } 194 }
195
184 DCHECK(GetData(node)->unscheduled_count_ > 0); 196 DCHECK(GetData(node)->unscheduled_count_ > 0);
185 --(GetData(node)->unscheduled_count_); 197 --(GetData(node)->unscheduled_count_);
186 if (FLAG_trace_turbo_scheduler) { 198 if (FLAG_trace_turbo_scheduler) {
187 Trace(" Use count of #%d:%s (used by #%d:%s)-- = %d\n", node->id(), 199 Trace(" Use count of #%d:%s (used by #%d:%s)-- = %d\n", node->id(),
188 node->op()->mnemonic(), from->id(), from->op()->mnemonic(), 200 node->op()->mnemonic(), from->id(), from->op()->mnemonic(),
189 GetData(node)->unscheduled_count_); 201 GetData(node)->unscheduled_count_);
190 } 202 }
191 if (GetData(node)->unscheduled_count_ == 0) { 203 if (GetData(node)->unscheduled_count_ == 0) {
192 Trace(" newly eligible #%d:%s\n", node->id(), node->op()->mnemonic()); 204 Trace(" newly eligible #%d:%s\n", node->id(), node->op()->mnemonic());
193 schedule_queue_.push(node); 205 schedule_queue_.push(node);
(...skipping 809 matching lines...) Expand 10 before | Expand all | Expand 10 after
1003 DCHECK(block != NULL); 1015 DCHECK(block != NULL);
1004 schedule_->AddNode(block, node); 1016 schedule_->AddNode(block, node);
1005 } 1017 }
1006 } 1018 }
1007 1019
1008 return GenericGraphVisit::CONTINUE; 1020 return GenericGraphVisit::CONTINUE;
1009 } 1021 }
1010 1022
1011 void PostEdge(Node* from, int index, Node* to) { 1023 void PostEdge(Node* from, int index, Node* to) {
1012 // If the edge is from an unscheduled node, then tally it in the use count 1024 // If the edge is from an unscheduled node, then tally it in the use count
1013 // for all of its inputs. Also make sure that control edges from coupled 1025 // for all of its inputs. The same criterion will be used in ScheduleLate
1014 // nodes are not counted. The same criterion will be used in ScheduleLate
1015 // for decrementing use counts. 1026 // for decrementing use counts.
1016 if (!schedule_->IsScheduled(from) && !IsCoupledControlEdge(from, index)) { 1027 if (!schedule_->IsScheduled(from)) {
1017 DCHECK_NE(Scheduler::kFixed, scheduler_->GetPlacement(from)); 1028 DCHECK_NE(Scheduler::kFixed, scheduler_->GetPlacement(from));
1018 scheduler_->IncrementUnscheduledUseCount(to, from); 1029 scheduler_->IncrementUnscheduledUseCount(to, index, from);
1019 } 1030 }
1020 } 1031 }
1021 1032
1022 bool IsCoupledControlEdge(Node* node, int index) {
1023 return scheduler_->GetPlacement(node) == Scheduler::kCoupled &&
1024 NodeProperties::FirstControlIndex(node) == index;
1025 }
1026
1027 private: 1033 private:
1028 Scheduler* scheduler_; 1034 Scheduler* scheduler_;
1029 Schedule* schedule_; 1035 Schedule* schedule_;
1030 }; 1036 };
1031 1037
1032 1038
1033 void Scheduler::PrepareUses() { 1039 void Scheduler::PrepareUses() {
1034 Trace("--- PREPARE USES -------------------------------------------\n"); 1040 Trace("--- PREPARE USES -------------------------------------------\n");
1035 1041
1036 // Count the uses of every node, it will be used to ensure that all of a 1042 // Count the uses of every node, it will be used to ensure that all of a
(...skipping 319 matching lines...) Expand 10 before | Expand all | Expand 10 after
1356 for (NodeVectorIter i = nodes->begin(); i != nodes->end(); ++i) { 1362 for (NodeVectorIter i = nodes->begin(); i != nodes->end(); ++i) {
1357 schedule_->SetBlockForNode(to, *i); 1363 schedule_->SetBlockForNode(to, *i);
1358 scheduled_nodes_[to->id().ToSize()].push_back(*i); 1364 scheduled_nodes_[to->id().ToSize()].push_back(*i);
1359 } 1365 }
1360 nodes->clear(); 1366 nodes->clear();
1361 } 1367 }
1362 1368
1363 } // namespace compiler 1369 } // namespace compiler
1364 } // namespace internal 1370 } // namespace internal
1365 } // namespace v8 1371 } // namespace v8
OLDNEW
« no previous file with comments | « src/compiler/scheduler.h ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698