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

Side by Side Diff: src/compiler/register-allocator.cc

Issue 1087133004: [turbofan] make LifetimePostion comparable (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 5 years, 8 months 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
« no previous file with comments | « src/compiler/register-allocator.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 2014 the V8 project authors. All rights reserved. 1 // Copyright 2014 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 "src/base/adapters.h" 5 #include "src/base/adapters.h"
6 #include "src/compiler/linkage.h" 6 #include "src/compiler/linkage.h"
7 #include "src/compiler/register-allocator.h" 7 #include "src/compiler/register-allocator.h"
8 #include "src/string-stream.h" 8 #include "src/string-stream.h"
9 9
10 namespace v8 { 10 namespace v8 {
11 namespace internal { 11 namespace internal {
12 namespace compiler { 12 namespace compiler {
13 13
14 #define TRACE(...) \ 14 #define TRACE(...) \
15 do { \ 15 do { \
16 if (FLAG_trace_alloc) PrintF(__VA_ARGS__); \ 16 if (FLAG_trace_alloc) PrintF(__VA_ARGS__); \
17 } while (false) 17 } while (false)
18 18
19 19
20 namespace { 20 namespace {
21 21
22 inline LifetimePosition Min(LifetimePosition a, LifetimePosition b) {
23 return a.Value() < b.Value() ? a : b;
24 }
25
26
27 inline LifetimePosition Max(LifetimePosition a, LifetimePosition b) {
28 return a.Value() > b.Value() ? a : b;
29 }
30
31
32 void RemoveElement(ZoneVector<LiveRange*>* v, LiveRange* range) { 22 void RemoveElement(ZoneVector<LiveRange*>* v, LiveRange* range) {
33 auto it = std::find(v->begin(), v->end(), range); 23 auto it = std::find(v->begin(), v->end(), range);
34 DCHECK(it != v->end()); 24 DCHECK(it != v->end());
35 v->erase(it); 25 v->erase(it);
36 } 26 }
37 27
38 28
39 int GetRegisterCount(const RegisterConfiguration* cfg, RegisterKind kind) { 29 int GetRegisterCount(const RegisterConfiguration* cfg, RegisterKind kind) {
40 return kind == DOUBLE_REGISTERS ? cfg->num_aliased_double_registers() 30 return kind == DOUBLE_REGISTERS ? cfg->num_aliased_double_registers()
41 : cfg->num_general_registers(); 31 : cfg->num_general_registers();
(...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after
106 96
107 97
108 void UsePosition::set_type(UsePositionType type, bool register_beneficial) { 98 void UsePosition::set_type(UsePositionType type, bool register_beneficial) {
109 DCHECK_IMPLIES(type == UsePositionType::kRequiresSlot, !register_beneficial); 99 DCHECK_IMPLIES(type == UsePositionType::kRequiresSlot, !register_beneficial);
110 flags_ = TypeField::encode(type) | 100 flags_ = TypeField::encode(type) |
111 RegisterBeneficialField::encode(register_beneficial); 101 RegisterBeneficialField::encode(register_beneficial);
112 } 102 }
113 103
114 104
115 UseInterval* UseInterval::SplitAt(LifetimePosition pos, Zone* zone) { 105 UseInterval* UseInterval::SplitAt(LifetimePosition pos, Zone* zone) {
116 DCHECK(Contains(pos) && pos.Value() != start().Value()); 106 DCHECK(Contains(pos) && pos != start());
117 auto after = new (zone) UseInterval(pos, end_); 107 auto after = new (zone) UseInterval(pos, end_);
118 after->next_ = next_; 108 after->next_ = next_;
119 next_ = nullptr; 109 next_ = nullptr;
120 end_ = pos; 110 end_ = pos;
121 return after; 111 return after;
122 } 112 }
123 113
124 114
125 struct LiveRange::SpillAtDefinitionList : ZoneObject { 115 struct LiveRange::SpillAtDefinitionList : ZoneObject {
126 SpillAtDefinitionList(int gap_index, InstructionOperand* operand, 116 SpillAtDefinitionList(int gap_index, InstructionOperand* operand,
(...skipping 24 matching lines...) Expand all
151 spill_start_index_(kMaxInt), 141 spill_start_index_(kMaxInt),
152 spill_type_(SpillType::kNoSpillType), 142 spill_type_(SpillType::kNoSpillType),
153 spill_operand_(nullptr), 143 spill_operand_(nullptr),
154 spills_at_definition_(nullptr) {} 144 spills_at_definition_(nullptr) {}
155 145
156 146
157 void LiveRange::Verify() const { 147 void LiveRange::Verify() const {
158 // Walk the positions, verifying that each is in an interval. 148 // Walk the positions, verifying that each is in an interval.
159 auto interval = first_interval_; 149 auto interval = first_interval_;
160 for (auto pos = first_pos_; pos != nullptr; pos = pos->next()) { 150 for (auto pos = first_pos_; pos != nullptr; pos = pos->next()) {
161 CHECK(Start().Value() <= pos->pos().Value()); 151 CHECK(Start() <= pos->pos());
162 CHECK(pos->pos().Value() <= End().Value()); 152 CHECK(pos->pos() <= End());
163 CHECK(interval != nullptr); 153 CHECK(interval != nullptr);
164 while (!interval->Contains(pos->pos()) && 154 while (!interval->Contains(pos->pos()) && interval->end() != pos->pos()) {
165 interval->end().Value() != pos->pos().Value()) {
166 interval = interval->next(); 155 interval = interval->next();
167 CHECK(interval != nullptr); 156 CHECK(interval != nullptr);
168 } 157 }
169 } 158 }
170 } 159 }
171 160
172 161
173 void LiveRange::set_assigned_register(int reg) { 162 void LiveRange::set_assigned_register(int reg) {
174 DCHECK(!HasRegisterAssigned() && !IsSpilled()); 163 DCHECK(!HasRegisterAssigned() && !IsSpilled());
175 assigned_register_ = reg; 164 assigned_register_ = reg;
(...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after
240 void LiveRange::CommitSpillOperand(AllocatedOperand* operand) { 229 void LiveRange::CommitSpillOperand(AllocatedOperand* operand) {
241 DCHECK(HasSpillRange()); 230 DCHECK(HasSpillRange());
242 DCHECK(!IsChild()); 231 DCHECK(!IsChild());
243 spill_type_ = SpillType::kSpillOperand; 232 spill_type_ = SpillType::kSpillOperand;
244 spill_operand_ = operand; 233 spill_operand_ = operand;
245 } 234 }
246 235
247 236
248 UsePosition* LiveRange::NextUsePosition(LifetimePosition start) const { 237 UsePosition* LiveRange::NextUsePosition(LifetimePosition start) const {
249 UsePosition* use_pos = last_processed_use_; 238 UsePosition* use_pos = last_processed_use_;
250 if (use_pos == nullptr || use_pos->pos().Value() > start.Value()) { 239 if (use_pos == nullptr || use_pos->pos() > start) {
251 use_pos = first_pos(); 240 use_pos = first_pos();
252 } 241 }
253 while (use_pos != nullptr && use_pos->pos().Value() < start.Value()) { 242 while (use_pos != nullptr && use_pos->pos() < start) {
254 use_pos = use_pos->next(); 243 use_pos = use_pos->next();
255 } 244 }
256 last_processed_use_ = use_pos; 245 last_processed_use_ = use_pos;
257 return use_pos; 246 return use_pos;
258 } 247 }
259 248
260 249
261 UsePosition* LiveRange::NextUsePositionRegisterIsBeneficial( 250 UsePosition* LiveRange::NextUsePositionRegisterIsBeneficial(
262 LifetimePosition start) const { 251 LifetimePosition start) const {
263 UsePosition* pos = NextUsePosition(start); 252 UsePosition* pos = NextUsePosition(start);
264 while (pos != nullptr && !pos->RegisterIsBeneficial()) { 253 while (pos != nullptr && !pos->RegisterIsBeneficial()) {
265 pos = pos->next(); 254 pos = pos->next();
266 } 255 }
267 return pos; 256 return pos;
268 } 257 }
269 258
270 259
271 UsePosition* LiveRange::PreviousUsePositionRegisterIsBeneficial( 260 UsePosition* LiveRange::PreviousUsePositionRegisterIsBeneficial(
272 LifetimePosition start) const { 261 LifetimePosition start) const {
273 auto pos = first_pos(); 262 auto pos = first_pos();
274 UsePosition* prev = nullptr; 263 UsePosition* prev = nullptr;
275 while (pos != nullptr && pos->pos().Value() < start.Value()) { 264 while (pos != nullptr && pos->pos() < start) {
276 if (pos->RegisterIsBeneficial()) prev = pos; 265 if (pos->RegisterIsBeneficial()) prev = pos;
277 pos = pos->next(); 266 pos = pos->next();
278 } 267 }
279 return prev; 268 return prev;
280 } 269 }
281 270
282 271
283 UsePosition* LiveRange::NextRegisterPosition(LifetimePosition start) const { 272 UsePosition* LiveRange::NextRegisterPosition(LifetimePosition start) const {
284 UsePosition* pos = NextUsePosition(start); 273 UsePosition* pos = NextUsePosition(start);
285 while (pos != nullptr && pos->type() != UsePositionType::kRequiresRegister) { 274 while (pos != nullptr && pos->type() != UsePositionType::kRequiresRegister) {
286 pos = pos->next(); 275 pos = pos->next();
287 } 276 }
288 return pos; 277 return pos;
289 } 278 }
290 279
291 280
292 bool LiveRange::CanBeSpilled(LifetimePosition pos) const { 281 bool LiveRange::CanBeSpilled(LifetimePosition pos) const {
293 // We cannot spill a live range that has a use requiring a register 282 // We cannot spill a live range that has a use requiring a register
294 // at the current or the immediate next position. 283 // at the current or the immediate next position.
295 auto use_pos = NextRegisterPosition(pos); 284 auto use_pos = NextRegisterPosition(pos);
296 if (use_pos == nullptr) return true; 285 if (use_pos == nullptr) return true;
297 return use_pos->pos().Value() > pos.NextStart().End().Value(); 286 return use_pos->pos() > pos.NextStart().End();
298 } 287 }
299 288
300 289
301 InstructionOperand LiveRange::GetAssignedOperand() const { 290 InstructionOperand LiveRange::GetAssignedOperand() const {
302 if (HasRegisterAssigned()) { 291 if (HasRegisterAssigned()) {
303 DCHECK(!IsSpilled()); 292 DCHECK(!IsSpilled());
304 switch (Kind()) { 293 switch (Kind()) {
305 case GENERAL_REGISTERS: 294 case GENERAL_REGISTERS:
306 return RegisterOperand(assigned_register()); 295 return RegisterOperand(assigned_register());
307 case DOUBLE_REGISTERS: 296 case DOUBLE_REGISTERS:
308 return DoubleRegisterOperand(assigned_register()); 297 return DoubleRegisterOperand(assigned_register());
309 default: 298 default:
310 UNREACHABLE(); 299 UNREACHABLE();
311 } 300 }
312 } 301 }
313 DCHECK(IsSpilled()); 302 DCHECK(IsSpilled());
314 DCHECK(!HasRegisterAssigned()); 303 DCHECK(!HasRegisterAssigned());
315 auto op = TopLevel()->GetSpillOperand(); 304 auto op = TopLevel()->GetSpillOperand();
316 DCHECK(!op->IsUnallocated()); 305 DCHECK(!op->IsUnallocated());
317 return *op; 306 return *op;
318 } 307 }
319 308
320 309
321 UseInterval* LiveRange::FirstSearchIntervalForPosition( 310 UseInterval* LiveRange::FirstSearchIntervalForPosition(
322 LifetimePosition position) const { 311 LifetimePosition position) const {
323 if (current_interval_ == nullptr) return first_interval_; 312 if (current_interval_ == nullptr) return first_interval_;
324 if (current_interval_->start().Value() > position.Value()) { 313 if (current_interval_->start() > position) {
325 current_interval_ = nullptr; 314 current_interval_ = nullptr;
326 return first_interval_; 315 return first_interval_;
327 } 316 }
328 return current_interval_; 317 return current_interval_;
329 } 318 }
330 319
331 320
332 void LiveRange::AdvanceLastProcessedMarker( 321 void LiveRange::AdvanceLastProcessedMarker(
333 UseInterval* to_start_of, LifetimePosition but_not_past) const { 322 UseInterval* to_start_of, LifetimePosition but_not_past) const {
334 if (to_start_of == nullptr) return; 323 if (to_start_of == nullptr) return;
335 if (to_start_of->start().Value() > but_not_past.Value()) return; 324 if (to_start_of->start() > but_not_past) return;
336 auto start = current_interval_ == nullptr ? LifetimePosition::Invalid() 325 auto start = current_interval_ == nullptr ? LifetimePosition::Invalid()
337 : current_interval_->start(); 326 : current_interval_->start();
338 if (to_start_of->start().Value() > start.Value()) { 327 if (to_start_of->start() > start) {
339 current_interval_ = to_start_of; 328 current_interval_ = to_start_of;
340 } 329 }
341 } 330 }
342 331
343 332
344 void LiveRange::SplitAt(LifetimePosition position, LiveRange* result, 333 void LiveRange::SplitAt(LifetimePosition position, LiveRange* result,
345 Zone* zone) { 334 Zone* zone) {
346 DCHECK(Start().Value() < position.Value()); 335 DCHECK(Start() < position);
347 DCHECK(result->IsEmpty()); 336 DCHECK(result->IsEmpty());
348 // Find the last interval that ends before the position. If the 337 // Find the last interval that ends before the position. If the
349 // position is contained in one of the intervals in the chain, we 338 // position is contained in one of the intervals in the chain, we
350 // split that interval and use the first part. 339 // split that interval and use the first part.
351 auto current = FirstSearchIntervalForPosition(position); 340 auto current = FirstSearchIntervalForPosition(position);
352 341
353 // If the split position coincides with the beginning of a use interval 342 // If the split position coincides with the beginning of a use interval
354 // we need to split use positons in a special way. 343 // we need to split use positons in a special way.
355 bool split_at_start = false; 344 bool split_at_start = false;
356 345
357 if (current->start().Value() == position.Value()) { 346 if (current->start() == position) {
358 // When splitting at start we need to locate the previous use interval. 347 // When splitting at start we need to locate the previous use interval.
359 current = first_interval_; 348 current = first_interval_;
360 } 349 }
361 350
362 UseInterval* after = nullptr; 351 UseInterval* after = nullptr;
363 while (current != nullptr) { 352 while (current != nullptr) {
364 if (current->Contains(position)) { 353 if (current->Contains(position)) {
365 after = current->SplitAt(position, zone); 354 after = current->SplitAt(position, zone);
366 break; 355 break;
367 } 356 }
368 auto next = current->next(); 357 auto next = current->next();
369 if (next->start().Value() >= position.Value()) { 358 if (next->start() >= position) {
370 split_at_start = (next->start().Value() == position.Value()); 359 split_at_start = (next->start() == position);
371 break; 360 break;
372 } 361 }
373 current = next; 362 current = next;
374 } 363 }
375 364
376 // Partition original use intervals to the two live ranges. 365 // Partition original use intervals to the two live ranges.
377 auto before = current; 366 auto before = current;
378 if (after == nullptr) after = before->next(); 367 if (after == nullptr) after = before->next();
379 result->last_interval_ = 368 result->last_interval_ =
380 (last_interval_ == before) 369 (last_interval_ == before)
381 ? after // Only interval in the range after split. 370 ? after // Only interval in the range after split.
382 : last_interval_; // Last interval of the original range. 371 : last_interval_; // Last interval of the original range.
383 result->first_interval_ = after; 372 result->first_interval_ = after;
384 last_interval_ = before; 373 last_interval_ = before;
385 374
386 // Find the last use position before the split and the first use 375 // Find the last use position before the split and the first use
387 // position after it. 376 // position after it.
388 auto use_after = first_pos_; 377 auto use_after = first_pos_;
389 UsePosition* use_before = nullptr; 378 UsePosition* use_before = nullptr;
390 if (split_at_start) { 379 if (split_at_start) {
391 // The split position coincides with the beginning of a use interval (the 380 // The split position coincides with the beginning of a use interval (the
392 // end of a lifetime hole). Use at this position should be attributed to 381 // end of a lifetime hole). Use at this position should be attributed to
393 // the split child because split child owns use interval covering it. 382 // the split child because split child owns use interval covering it.
394 while (use_after != nullptr && 383 while (use_after != nullptr && use_after->pos() < position) {
395 use_after->pos().Value() < position.Value()) {
396 use_before = use_after; 384 use_before = use_after;
397 use_after = use_after->next(); 385 use_after = use_after->next();
398 } 386 }
399 } else { 387 } else {
400 while (use_after != nullptr && 388 while (use_after != nullptr && use_after->pos() <= position) {
401 use_after->pos().Value() <= position.Value()) {
402 use_before = use_after; 389 use_before = use_after;
403 use_after = use_after->next(); 390 use_after = use_after->next();
404 } 391 }
405 } 392 }
406 393
407 // Partition original use positions to the two live ranges. 394 // Partition original use positions to the two live ranges.
408 if (use_before != nullptr) { 395 if (use_before != nullptr) {
409 use_before->set_next(nullptr); 396 use_before->set_next(nullptr);
410 } else { 397 } else {
411 first_pos_ = nullptr; 398 first_pos_ = nullptr;
(...skipping 20 matching lines...) Expand all
432 419
433 420
434 // This implements an ordering on live ranges so that they are ordered by their 421 // This implements an ordering on live ranges so that they are ordered by their
435 // start positions. This is needed for the correctness of the register 422 // start positions. This is needed for the correctness of the register
436 // allocation algorithm. If two live ranges start at the same offset then there 423 // allocation algorithm. If two live ranges start at the same offset then there
437 // is a tie breaker based on where the value is first used. This part of the 424 // is a tie breaker based on where the value is first used. This part of the
438 // ordering is merely a heuristic. 425 // ordering is merely a heuristic.
439 bool LiveRange::ShouldBeAllocatedBefore(const LiveRange* other) const { 426 bool LiveRange::ShouldBeAllocatedBefore(const LiveRange* other) const {
440 LifetimePosition start = Start(); 427 LifetimePosition start = Start();
441 LifetimePosition other_start = other->Start(); 428 LifetimePosition other_start = other->Start();
442 if (start.Value() == other_start.Value()) { 429 if (start == other_start) {
443 UsePosition* pos = first_pos(); 430 UsePosition* pos = first_pos();
444 if (pos == nullptr) return false; 431 if (pos == nullptr) return false;
445 UsePosition* other_pos = other->first_pos(); 432 UsePosition* other_pos = other->first_pos();
446 if (other_pos == nullptr) return true; 433 if (other_pos == nullptr) return true;
447 return pos->pos().Value() < other_pos->pos().Value(); 434 return pos->pos() < other_pos->pos();
448 } 435 }
449 return start.Value() < other_start.Value(); 436 return start < other_start;
450 } 437 }
451 438
452 439
453 void LiveRange::ShortenTo(LifetimePosition start) { 440 void LiveRange::ShortenTo(LifetimePosition start) {
454 TRACE("Shorten live range %d to [%d\n", id_, start.Value()); 441 TRACE("Shorten live range %d to [%d\n", id_, start.value());
455 DCHECK(first_interval_ != nullptr); 442 DCHECK(first_interval_ != nullptr);
456 DCHECK(first_interval_->start().Value() <= start.Value()); 443 DCHECK(first_interval_->start() <= start);
457 DCHECK(start.Value() < first_interval_->end().Value()); 444 DCHECK(start < first_interval_->end());
458 first_interval_->set_start(start); 445 first_interval_->set_start(start);
459 } 446 }
460 447
461 448
462 void LiveRange::EnsureInterval(LifetimePosition start, LifetimePosition end, 449 void LiveRange::EnsureInterval(LifetimePosition start, LifetimePosition end,
463 Zone* zone) { 450 Zone* zone) {
464 TRACE("Ensure live range %d in interval [%d %d[\n", id_, start.Value(), 451 TRACE("Ensure live range %d in interval [%d %d[\n", id_, start.value(),
465 end.Value()); 452 end.value());
466 auto new_end = end; 453 auto new_end = end;
467 while (first_interval_ != nullptr && 454 while (first_interval_ != nullptr && first_interval_->start() <= end) {
468 first_interval_->start().Value() <= end.Value()) { 455 if (first_interval_->end() > end) {
469 if (first_interval_->end().Value() > end.Value()) {
470 new_end = first_interval_->end(); 456 new_end = first_interval_->end();
471 } 457 }
472 first_interval_ = first_interval_->next(); 458 first_interval_ = first_interval_->next();
473 } 459 }
474 460
475 auto new_interval = new (zone) UseInterval(start, new_end); 461 auto new_interval = new (zone) UseInterval(start, new_end);
476 new_interval->set_next(first_interval_); 462 new_interval->set_next(first_interval_);
477 first_interval_ = new_interval; 463 first_interval_ = new_interval;
478 if (new_interval->next() == nullptr) { 464 if (new_interval->next() == nullptr) {
479 last_interval_ = new_interval; 465 last_interval_ = new_interval;
480 } 466 }
481 } 467 }
482 468
483 469
484 void LiveRange::AddUseInterval(LifetimePosition start, LifetimePosition end, 470 void LiveRange::AddUseInterval(LifetimePosition start, LifetimePosition end,
485 Zone* zone) { 471 Zone* zone) {
486 TRACE("Add to live range %d interval [%d %d[\n", id_, start.Value(), 472 TRACE("Add to live range %d interval [%d %d[\n", id_, start.value(),
487 end.Value()); 473 end.value());
488 if (first_interval_ == nullptr) { 474 if (first_interval_ == nullptr) {
489 auto interval = new (zone) UseInterval(start, end); 475 auto interval = new (zone) UseInterval(start, end);
490 first_interval_ = interval; 476 first_interval_ = interval;
491 last_interval_ = interval; 477 last_interval_ = interval;
492 } else { 478 } else {
493 if (end.Value() == first_interval_->start().Value()) { 479 if (end == first_interval_->start()) {
494 first_interval_->set_start(start); 480 first_interval_->set_start(start);
495 } else if (end.Value() < first_interval_->start().Value()) { 481 } else if (end < first_interval_->start()) {
496 auto interval = new (zone) UseInterval(start, end); 482 auto interval = new (zone) UseInterval(start, end);
497 interval->set_next(first_interval_); 483 interval->set_next(first_interval_);
498 first_interval_ = interval; 484 first_interval_ = interval;
499 } else { 485 } else {
500 // Order of instruction's processing (see ProcessInstructions) guarantees 486 // Order of instruction's processing (see ProcessInstructions) guarantees
501 // that each new use interval either precedes or intersects with 487 // that each new use interval either precedes or intersects with
502 // last added interval. 488 // last added interval.
503 DCHECK(start.Value() < first_interval_->end().Value()); 489 DCHECK(start < first_interval_->end());
504 first_interval_->set_start(Min(start, first_interval_->start())); 490 first_interval_->set_start(Min(start, first_interval_->start()));
505 first_interval_->set_end(Max(end, first_interval_->end())); 491 first_interval_->set_end(Max(end, first_interval_->end()));
506 } 492 }
507 } 493 }
508 } 494 }
509 495
510 496
511 void LiveRange::AddUsePosition(LifetimePosition pos, 497 void LiveRange::AddUsePosition(LifetimePosition pos,
512 InstructionOperand* operand, 498 InstructionOperand* operand,
513 InstructionOperand* hint, Zone* zone) { 499 InstructionOperand* hint, Zone* zone) {
514 TRACE("Add to live range %d use position %d\n", id_, pos.Value()); 500 TRACE("Add to live range %d use position %d\n", id_, pos.value());
515 auto use_pos = new (zone) UsePosition(pos, operand, hint); 501 auto use_pos = new (zone) UsePosition(pos, operand, hint);
516 UsePosition* prev_hint = nullptr; 502 UsePosition* prev_hint = nullptr;
517 UsePosition* prev = nullptr; 503 UsePosition* prev = nullptr;
518 auto current = first_pos_; 504 auto current = first_pos_;
519 while (current != nullptr && current->pos().Value() < pos.Value()) { 505 while (current != nullptr && current->pos() < pos) {
520 prev_hint = current->HasHint() ? current : prev_hint; 506 prev_hint = current->HasHint() ? current : prev_hint;
521 prev = current; 507 prev = current;
522 current = current->next(); 508 current = current->next();
523 } 509 }
524 510
525 if (prev == nullptr) { 511 if (prev == nullptr) {
526 use_pos->set_next(first_pos_); 512 use_pos->set_next(first_pos_);
527 first_pos_ = use_pos; 513 first_pos_ = use_pos;
528 } else { 514 } else {
529 use_pos->set_next(prev->next()); 515 use_pos->set_next(prev->next());
530 prev->set_next(use_pos); 516 prev->set_next(use_pos);
531 } 517 }
532 518
533 if (prev_hint == nullptr && use_pos->HasHint()) { 519 if (prev_hint == nullptr && use_pos->HasHint()) {
534 current_hint_operand_ = hint; 520 current_hint_operand_ = hint;
535 } 521 }
536 } 522 }
537 523
538 524
539 void LiveRange::ConvertUsesToOperand(const InstructionOperand& op, 525 void LiveRange::ConvertUsesToOperand(const InstructionOperand& op,
540 InstructionOperand* spill_op) { 526 InstructionOperand* spill_op) {
541 for (auto pos = first_pos(); pos != nullptr; pos = pos->next()) { 527 for (auto pos = first_pos(); pos != nullptr; pos = pos->next()) {
542 DCHECK(Start().Value() <= pos->pos().Value() && 528 DCHECK(Start() <= pos->pos() && pos->pos() <= End());
543 pos->pos().Value() <= End().Value());
544 if (!pos->HasOperand()) { 529 if (!pos->HasOperand()) {
545 continue; 530 continue;
546 } 531 }
547 switch (pos->type()) { 532 switch (pos->type()) {
548 case UsePositionType::kRequiresSlot: 533 case UsePositionType::kRequiresSlot:
549 if (spill_op != nullptr) { 534 if (spill_op != nullptr) {
550 InstructionOperand::ReplaceWith(pos->operand(), spill_op); 535 InstructionOperand::ReplaceWith(pos->operand(), spill_op);
551 } 536 }
552 break; 537 break;
553 case UsePositionType::kRequiresRegister: 538 case UsePositionType::kRequiresRegister:
554 DCHECK(op.IsRegister() || op.IsDoubleRegister()); 539 DCHECK(op.IsRegister() || op.IsDoubleRegister());
555 // Fall through. 540 // Fall through.
556 case UsePositionType::kAny: 541 case UsePositionType::kAny:
557 InstructionOperand::ReplaceWith(pos->operand(), &op); 542 InstructionOperand::ReplaceWith(pos->operand(), &op);
558 break; 543 break;
559 } 544 }
560 } 545 }
561 } 546 }
562 547
563 548
564 bool LiveRange::CanCover(LifetimePosition position) const { 549 bool LiveRange::CanCover(LifetimePosition position) const {
565 if (IsEmpty()) return false; 550 if (IsEmpty()) return false;
566 return Start().Value() <= position.Value() && 551 return Start() <= position && position < End();
567 position.Value() < End().Value();
568 } 552 }
569 553
570 554
571 bool LiveRange::Covers(LifetimePosition position) const { 555 bool LiveRange::Covers(LifetimePosition position) const {
572 if (!CanCover(position)) return false; 556 if (!CanCover(position)) return false;
573 auto start_search = FirstSearchIntervalForPosition(position); 557 auto start_search = FirstSearchIntervalForPosition(position);
574 for (auto interval = start_search; interval != nullptr; 558 for (auto interval = start_search; interval != nullptr;
575 interval = interval->next()) { 559 interval = interval->next()) {
576 DCHECK(interval->next() == nullptr || 560 DCHECK(interval->next() == nullptr ||
577 interval->next()->start().Value() >= interval->start().Value()); 561 interval->next()->start() >= interval->start());
578 AdvanceLastProcessedMarker(interval, position); 562 AdvanceLastProcessedMarker(interval, position);
579 if (interval->Contains(position)) return true; 563 if (interval->Contains(position)) return true;
580 if (interval->start().Value() > position.Value()) return false; 564 if (interval->start() > position) return false;
581 } 565 }
582 return false; 566 return false;
583 } 567 }
584 568
585 569
586 LifetimePosition LiveRange::FirstIntersection(LiveRange* other) const { 570 LifetimePosition LiveRange::FirstIntersection(LiveRange* other) const {
587 auto b = other->first_interval(); 571 auto b = other->first_interval();
588 if (b == nullptr) return LifetimePosition::Invalid(); 572 if (b == nullptr) return LifetimePosition::Invalid();
589 auto advance_last_processed_up_to = b->start(); 573 auto advance_last_processed_up_to = b->start();
590 auto a = FirstSearchIntervalForPosition(b->start()); 574 auto a = FirstSearchIntervalForPosition(b->start());
591 while (a != nullptr && b != nullptr) { 575 while (a != nullptr && b != nullptr) {
592 if (a->start().Value() > other->End().Value()) break; 576 if (a->start() > other->End()) break;
593 if (b->start().Value() > End().Value()) break; 577 if (b->start() > End()) break;
594 auto cur_intersection = a->Intersect(b); 578 auto cur_intersection = a->Intersect(b);
595 if (cur_intersection.IsValid()) { 579 if (cur_intersection.IsValid()) {
596 return cur_intersection; 580 return cur_intersection;
597 } 581 }
598 if (a->start().Value() < b->start().Value()) { 582 if (a->start() < b->start()) {
599 a = a->next(); 583 a = a->next();
600 if (a == nullptr || a->start().Value() > other->End().Value()) break; 584 if (a == nullptr || a->start() > other->End()) break;
601 AdvanceLastProcessedMarker(a, advance_last_processed_up_to); 585 AdvanceLastProcessedMarker(a, advance_last_processed_up_to);
602 } else { 586 } else {
603 b = b->next(); 587 b = b->next();
604 } 588 }
605 } 589 }
606 return LifetimePosition::Invalid(); 590 return LifetimePosition::Invalid();
607 } 591 }
608 592
609 593
610 static bool AreUseIntervalsIntersecting(UseInterval* interval1, 594 static bool AreUseIntervalsIntersecting(UseInterval* interval1,
611 UseInterval* interval2) { 595 UseInterval* interval2) {
612 while (interval1 != nullptr && interval2 != nullptr) { 596 while (interval1 != nullptr && interval2 != nullptr) {
613 if (interval1->start().Value() < interval2->start().Value()) { 597 if (interval1->start() < interval2->start()) {
614 if (interval1->end().Value() > interval2->start().Value()) { 598 if (interval1->end() > interval2->start()) {
615 return true; 599 return true;
616 } 600 }
617 interval1 = interval1->next(); 601 interval1 = interval1->next();
618 } else { 602 } else {
619 if (interval2->end().Value() > interval1->start().Value()) { 603 if (interval2->end() > interval1->start()) {
620 return true; 604 return true;
621 } 605 }
622 interval2 = interval2->next(); 606 interval2 = interval2->next();
623 } 607 }
624 } 608 }
625 return false; 609 return false;
626 } 610 }
627 611
628 612
629 SpillRange::SpillRange(LiveRange* parent, Zone* zone) : live_ranges_(zone) { 613 SpillRange::SpillRange(LiveRange* parent, Zone* zone) : live_ranges_(zone) {
(...skipping 17 matching lines...) Expand all
647 use_interval_ = result; 631 use_interval_ = result;
648 live_ranges().push_back(parent); 632 live_ranges().push_back(parent);
649 end_position_ = node->end(); 633 end_position_ = node->end();
650 DCHECK(!parent->HasSpillRange()); 634 DCHECK(!parent->HasSpillRange());
651 parent->SetSpillRange(this); 635 parent->SetSpillRange(this);
652 } 636 }
653 637
654 638
655 bool SpillRange::IsIntersectingWith(SpillRange* other) const { 639 bool SpillRange::IsIntersectingWith(SpillRange* other) const {
656 if (this->use_interval_ == nullptr || other->use_interval_ == nullptr || 640 if (this->use_interval_ == nullptr || other->use_interval_ == nullptr ||
657 this->End().Value() <= other->use_interval_->start().Value() || 641 this->End() <= other->use_interval_->start() ||
658 other->End().Value() <= this->use_interval_->start().Value()) { 642 other->End() <= this->use_interval_->start()) {
659 return false; 643 return false;
660 } 644 }
661 return AreUseIntervalsIntersecting(use_interval_, other->use_interval_); 645 return AreUseIntervalsIntersecting(use_interval_, other->use_interval_);
662 } 646 }
663 647
664 648
665 bool SpillRange::TryMerge(SpillRange* other) { 649 bool SpillRange::TryMerge(SpillRange* other) {
666 if (Kind() != other->Kind() || IsIntersectingWith(other)) return false; 650 if (Kind() != other->Kind() || IsIntersectingWith(other)) return false;
667 651
668 auto max = LifetimePosition::MaxPosition(); 652 auto max = LifetimePosition::MaxPosition();
669 if (End().Value() < other->End().Value() && 653 if (End() < other->End() && other->End() != max) {
670 other->End().Value() != max.Value()) {
671 end_position_ = other->End(); 654 end_position_ = other->End();
672 } 655 }
673 other->end_position_ = max; 656 other->end_position_ = max;
674 657
675 MergeDisjointIntervals(other->use_interval_); 658 MergeDisjointIntervals(other->use_interval_);
676 other->use_interval_ = nullptr; 659 other->use_interval_ = nullptr;
677 660
678 for (auto range : other->live_ranges()) { 661 for (auto range : other->live_ranges()) {
679 DCHECK(range->GetSpillRange() == other); 662 DCHECK(range->GetSpillRange() == other);
680 range->SetSpillRange(this); 663 range->SetSpillRange(this);
(...skipping 13 matching lines...) Expand all
694 range->CommitSpillOperand(op); 677 range->CommitSpillOperand(op);
695 } 678 }
696 } 679 }
697 680
698 681
699 void SpillRange::MergeDisjointIntervals(UseInterval* other) { 682 void SpillRange::MergeDisjointIntervals(UseInterval* other) {
700 UseInterval* tail = nullptr; 683 UseInterval* tail = nullptr;
701 auto current = use_interval_; 684 auto current = use_interval_;
702 while (other != nullptr) { 685 while (other != nullptr) {
703 // Make sure the 'current' list starts first 686 // Make sure the 'current' list starts first
704 if (current == nullptr || 687 if (current == nullptr || current->start() > other->start()) {
705 current->start().Value() > other->start().Value()) {
706 std::swap(current, other); 688 std::swap(current, other);
707 } 689 }
708 // Check disjointness 690 // Check disjointness
709 DCHECK(other == nullptr || 691 DCHECK(other == nullptr || current->end() <= other->start());
710 current->end().Value() <= other->start().Value());
711 // Append the 'current' node to the result accumulator and move forward 692 // Append the 'current' node to the result accumulator and move forward
712 if (tail == nullptr) { 693 if (tail == nullptr) {
713 use_interval_ = current; 694 use_interval_ = current;
714 } else { 695 } else {
715 tail->set_next(current); 696 tail->set_next(current);
716 } 697 }
717 tail = current; 698 tail = current;
718 current = current->next(); 699 current = current->next();
719 } 700 }
720 // Other list is empty => we are done 701 // Other list is empty => we are done
(...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after
794 775
795 bool RegisterAllocationData::ExistsUseWithoutDefinition() { 776 bool RegisterAllocationData::ExistsUseWithoutDefinition() {
796 bool found = false; 777 bool found = false;
797 BitVector::Iterator iterator(live_in_sets()[0]); 778 BitVector::Iterator iterator(live_in_sets()[0]);
798 while (!iterator.Done()) { 779 while (!iterator.Done()) {
799 found = true; 780 found = true;
800 int operand_index = iterator.Current(); 781 int operand_index = iterator.Current();
801 PrintF("Register allocator error: live v%d reached first block.\n", 782 PrintF("Register allocator error: live v%d reached first block.\n",
802 operand_index); 783 operand_index);
803 LiveRange* range = LiveRangeFor(operand_index); 784 LiveRange* range = LiveRangeFor(operand_index);
804 PrintF(" (first use is at %d)\n", range->first_pos()->pos().Value()); 785 PrintF(" (first use is at %d)\n", range->first_pos()->pos().value());
805 if (debug_name() == nullptr) { 786 if (debug_name() == nullptr) {
806 PrintF("\n"); 787 PrintF("\n");
807 } else { 788 } else {
808 PrintF(" (function: %s)\n", debug_name()); 789 PrintF(" (function: %s)\n", debug_name());
809 } 790 }
810 iterator.Advance(); 791 iterator.Advance();
811 } 792 }
812 return found; 793 return found;
813 } 794 }
814 795
(...skipping 349 matching lines...) Expand 10 before | Expand all | Expand 10 after
1164 } 1145 }
1165 } 1146 }
1166 1147
1167 1148
1168 void LiveRangeBuilder::Define(LifetimePosition position, 1149 void LiveRangeBuilder::Define(LifetimePosition position,
1169 InstructionOperand* operand, 1150 InstructionOperand* operand,
1170 InstructionOperand* hint) { 1151 InstructionOperand* hint) {
1171 auto range = LiveRangeFor(operand); 1152 auto range = LiveRangeFor(operand);
1172 if (range == nullptr) return; 1153 if (range == nullptr) return;
1173 1154
1174 if (range->IsEmpty() || range->Start().Value() > position.Value()) { 1155 if (range->IsEmpty() || range->Start() > position) {
1175 // Can happen if there is a definition without use. 1156 // Can happen if there is a definition without use.
1176 range->AddUseInterval(position, position.NextStart(), allocation_zone()); 1157 range->AddUseInterval(position, position.NextStart(), allocation_zone());
1177 range->AddUsePosition(position.NextStart(), nullptr, nullptr, 1158 range->AddUsePosition(position.NextStart(), nullptr, nullptr,
1178 allocation_zone()); 1159 allocation_zone());
1179 } else { 1160 } else {
1180 range->ShortenTo(position); 1161 range->ShortenTo(position);
1181 } 1162 }
1182 1163
1183 if (operand->IsUnallocated()) { 1164 if (operand->IsUnallocated()) {
1184 auto unalloc_operand = UnallocatedOperand::cast(operand); 1165 auto unalloc_operand = UnallocatedOperand::cast(operand);
(...skipping 280 matching lines...) Expand 10 before | Expand all | Expand 10 after
1465 RegisterAllocator::RegisterAllocator(RegisterAllocationData* data, 1446 RegisterAllocator::RegisterAllocator(RegisterAllocationData* data,
1466 RegisterKind kind) 1447 RegisterKind kind)
1467 : data_(data), 1448 : data_(data),
1468 mode_(kind), 1449 mode_(kind),
1469 num_registers_(GetRegisterCount(data->config(), kind)) {} 1450 num_registers_(GetRegisterCount(data->config(), kind)) {}
1470 1451
1471 1452
1472 LiveRange* RegisterAllocator::SplitRangeAt(LiveRange* range, 1453 LiveRange* RegisterAllocator::SplitRangeAt(LiveRange* range,
1473 LifetimePosition pos) { 1454 LifetimePosition pos) {
1474 DCHECK(!range->IsFixed()); 1455 DCHECK(!range->IsFixed());
1475 TRACE("Splitting live range %d at %d\n", range->id(), pos.Value()); 1456 TRACE("Splitting live range %d at %d\n", range->id(), pos.value());
1476 1457
1477 if (pos.Value() <= range->Start().Value()) return range; 1458 if (pos <= range->Start()) return range;
1478 1459
1479 // We can't properly connect liveranges if splitting occurred at the end 1460 // We can't properly connect liveranges if splitting occurred at the end
1480 // a block. 1461 // a block.
1481 DCHECK(pos.IsStart() || pos.IsGapPosition() || 1462 DCHECK(pos.IsStart() || pos.IsGapPosition() ||
1482 (GetInstructionBlock(code(), pos)->last_instruction_index() != 1463 (GetInstructionBlock(code(), pos)->last_instruction_index() !=
1483 pos.ToInstructionIndex())); 1464 pos.ToInstructionIndex()));
1484 1465
1485 int vreg = code()->NextVirtualRegister(); 1466 int vreg = code()->NextVirtualRegister();
1486 auto result = LiveRangeFor(vreg); 1467 auto result = LiveRangeFor(vreg);
1487 range->SplitAt(pos, result, allocation_zone()); 1468 range->SplitAt(pos, result, allocation_zone());
1488 return result; 1469 return result;
1489 } 1470 }
1490 1471
1491 1472
1492 LiveRange* RegisterAllocator::SplitBetween(LiveRange* range, 1473 LiveRange* RegisterAllocator::SplitBetween(LiveRange* range,
1493 LifetimePosition start, 1474 LifetimePosition start,
1494 LifetimePosition end) { 1475 LifetimePosition end) {
1495 DCHECK(!range->IsFixed()); 1476 DCHECK(!range->IsFixed());
1496 TRACE("Splitting live range %d in position between [%d, %d]\n", range->id(), 1477 TRACE("Splitting live range %d in position between [%d, %d]\n", range->id(),
1497 start.Value(), end.Value()); 1478 start.value(), end.value());
1498 1479
1499 auto split_pos = FindOptimalSplitPos(start, end); 1480 auto split_pos = FindOptimalSplitPos(start, end);
1500 DCHECK(split_pos.Value() >= start.Value()); 1481 DCHECK(split_pos >= start);
1501 return SplitRangeAt(range, split_pos); 1482 return SplitRangeAt(range, split_pos);
1502 } 1483 }
1503 1484
1504 1485
1505 LifetimePosition RegisterAllocator::FindOptimalSplitPos(LifetimePosition start, 1486 LifetimePosition RegisterAllocator::FindOptimalSplitPos(LifetimePosition start,
1506 LifetimePosition end) { 1487 LifetimePosition end) {
1507 int start_instr = start.ToInstructionIndex(); 1488 int start_instr = start.ToInstructionIndex();
1508 int end_instr = end.ToInstructionIndex(); 1489 int end_instr = end.ToInstructionIndex();
1509 DCHECK(start_instr <= end_instr); 1490 DCHECK(start_instr <= end_instr);
1510 1491
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after
1549 auto prev_use = range->PreviousUsePositionRegisterIsBeneficial(pos); 1530 auto prev_use = range->PreviousUsePositionRegisterIsBeneficial(pos);
1550 1531
1551 while (loop_header != nullptr) { 1532 while (loop_header != nullptr) {
1552 // We are going to spill live range inside the loop. 1533 // We are going to spill live range inside the loop.
1553 // If possible try to move spilling position backwards to loop header. 1534 // If possible try to move spilling position backwards to loop header.
1554 // This will reduce number of memory moves on the back edge. 1535 // This will reduce number of memory moves on the back edge.
1555 auto loop_start = LifetimePosition::GapFromInstructionIndex( 1536 auto loop_start = LifetimePosition::GapFromInstructionIndex(
1556 loop_header->first_instruction_index()); 1537 loop_header->first_instruction_index());
1557 1538
1558 if (range->Covers(loop_start)) { 1539 if (range->Covers(loop_start)) {
1559 if (prev_use == nullptr || prev_use->pos().Value() < loop_start.Value()) { 1540 if (prev_use == nullptr || prev_use->pos() < loop_start) {
1560 // No register beneficial use inside the loop before the pos. 1541 // No register beneficial use inside the loop before the pos.
1561 pos = loop_start; 1542 pos = loop_start;
1562 } 1543 }
1563 } 1544 }
1564 1545
1565 // Try hoisting out to an outer loop. 1546 // Try hoisting out to an outer loop.
1566 loop_header = GetContainingLoop(code(), loop_header); 1547 loop_header = GetContainingLoop(code(), loop_header);
1567 } 1548 }
1568 1549
1569 return pos; 1550 return pos;
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after
1622 1603
1623 while (!unhandled_live_ranges().empty()) { 1604 while (!unhandled_live_ranges().empty()) {
1624 DCHECK(UnhandledIsSorted()); 1605 DCHECK(UnhandledIsSorted());
1625 auto current = unhandled_live_ranges().back(); 1606 auto current = unhandled_live_ranges().back();
1626 unhandled_live_ranges().pop_back(); 1607 unhandled_live_ranges().pop_back();
1627 DCHECK(UnhandledIsSorted()); 1608 DCHECK(UnhandledIsSorted());
1628 auto position = current->Start(); 1609 auto position = current->Start();
1629 #ifdef DEBUG 1610 #ifdef DEBUG
1630 allocation_finger_ = position; 1611 allocation_finger_ = position;
1631 #endif 1612 #endif
1632 TRACE("Processing interval %d start=%d\n", current->id(), position.Value()); 1613 TRACE("Processing interval %d start=%d\n", current->id(), position.value());
1633 1614
1634 if (!current->HasNoSpillType()) { 1615 if (!current->HasNoSpillType()) {
1635 TRACE("Live range %d already has a spill operand\n", current->id()); 1616 TRACE("Live range %d already has a spill operand\n", current->id());
1636 auto next_pos = position; 1617 auto next_pos = position;
1637 if (next_pos.IsGapPosition()) { 1618 if (next_pos.IsGapPosition()) {
1638 next_pos = next_pos.NextStart(); 1619 next_pos = next_pos.NextStart();
1639 } 1620 }
1640 auto pos = current->NextUsePositionRegisterIsBeneficial(next_pos); 1621 auto pos = current->NextUsePositionRegisterIsBeneficial(next_pos);
1641 // If the range already has a spill operand and it doesn't need a 1622 // If the range already has a spill operand and it doesn't need a
1642 // register immediately, split it and spill the first part of the range. 1623 // register immediately, split it and spill the first part of the range.
1643 if (pos == nullptr) { 1624 if (pos == nullptr) {
1644 Spill(current); 1625 Spill(current);
1645 continue; 1626 continue;
1646 } else if (pos->pos().Value() > current->Start().NextStart().Value()) { 1627 } else if (pos->pos() > current->Start().NextStart()) {
1647 // Do not spill live range eagerly if use position that can benefit from 1628 // Do not spill live range eagerly if use position that can benefit from
1648 // the register is too close to the start of live range. 1629 // the register is too close to the start of live range.
1649 SpillBetween(current, current->Start(), pos->pos()); 1630 SpillBetween(current, current->Start(), pos->pos());
1650 DCHECK(UnhandledIsSorted()); 1631 DCHECK(UnhandledIsSorted());
1651 continue; 1632 continue;
1652 } 1633 }
1653 } 1634 }
1654 1635
1655 if (TryReuseSpillForPhi(current)) continue; 1636 if (TryReuseSpillForPhi(current)) continue;
1656 1637
1657 for (size_t i = 0; i < active_live_ranges().size(); ++i) { 1638 for (size_t i = 0; i < active_live_ranges().size(); ++i) {
1658 auto cur_active = active_live_ranges()[i]; 1639 auto cur_active = active_live_ranges()[i];
1659 if (cur_active->End().Value() <= position.Value()) { 1640 if (cur_active->End() <= position) {
1660 ActiveToHandled(cur_active); 1641 ActiveToHandled(cur_active);
1661 --i; // The live range was removed from the list of active live ranges. 1642 --i; // The live range was removed from the list of active live ranges.
1662 } else if (!cur_active->Covers(position)) { 1643 } else if (!cur_active->Covers(position)) {
1663 ActiveToInactive(cur_active); 1644 ActiveToInactive(cur_active);
1664 --i; // The live range was removed from the list of active live ranges. 1645 --i; // The live range was removed from the list of active live ranges.
1665 } 1646 }
1666 } 1647 }
1667 1648
1668 for (size_t i = 0; i < inactive_live_ranges().size(); ++i) { 1649 for (size_t i = 0; i < inactive_live_ranges().size(); ++i) {
1669 auto cur_inactive = inactive_live_ranges()[i]; 1650 auto cur_inactive = inactive_live_ranges()[i];
1670 if (cur_inactive->End().Value() <= position.Value()) { 1651 if (cur_inactive->End() <= position) {
1671 InactiveToHandled(cur_inactive); 1652 InactiveToHandled(cur_inactive);
1672 --i; // Live range was removed from the list of inactive live ranges. 1653 --i; // Live range was removed from the list of inactive live ranges.
1673 } else if (cur_inactive->Covers(position)) { 1654 } else if (cur_inactive->Covers(position)) {
1674 InactiveToActive(cur_inactive); 1655 InactiveToActive(cur_inactive);
1675 --i; // Live range was removed from the list of inactive live ranges. 1656 --i; // Live range was removed from the list of inactive live ranges.
1676 } 1657 }
1677 } 1658 }
1678 1659
1679 DCHECK(!current->HasRegisterAssigned() && !current->IsSpilled()); 1660 DCHECK(!current->HasRegisterAssigned() && !current->IsSpilled());
1680 1661
(...skipping 23 matching lines...) Expand all
1704 1685
1705 void LinearScanAllocator::AddToInactive(LiveRange* range) { 1686 void LinearScanAllocator::AddToInactive(LiveRange* range) {
1706 TRACE("Add live range %d to inactive\n", range->id()); 1687 TRACE("Add live range %d to inactive\n", range->id());
1707 inactive_live_ranges().push_back(range); 1688 inactive_live_ranges().push_back(range);
1708 } 1689 }
1709 1690
1710 1691
1711 void LinearScanAllocator::AddToUnhandledSorted(LiveRange* range) { 1692 void LinearScanAllocator::AddToUnhandledSorted(LiveRange* range) {
1712 if (range == nullptr || range->IsEmpty()) return; 1693 if (range == nullptr || range->IsEmpty()) return;
1713 DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled()); 1694 DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled());
1714 DCHECK(allocation_finger_.Value() <= range->Start().Value()); 1695 DCHECK(allocation_finger_ <= range->Start());
1715 for (int i = static_cast<int>(unhandled_live_ranges().size() - 1); i >= 0; 1696 for (int i = static_cast<int>(unhandled_live_ranges().size() - 1); i >= 0;
1716 --i) { 1697 --i) {
1717 auto cur_range = unhandled_live_ranges().at(i); 1698 auto cur_range = unhandled_live_ranges().at(i);
1718 if (!range->ShouldBeAllocatedBefore(cur_range)) continue; 1699 if (!range->ShouldBeAllocatedBefore(cur_range)) continue;
1719 TRACE("Add live range %d to unhandled at %d\n", range->id(), i + 1); 1700 TRACE("Add live range %d to unhandled at %d\n", range->id(), i + 1);
1720 auto it = unhandled_live_ranges().begin() + (i + 1); 1701 auto it = unhandled_live_ranges().begin() + (i + 1);
1721 unhandled_live_ranges().insert(it, range); 1702 unhandled_live_ranges().insert(it, range);
1722 DCHECK(UnhandledIsSorted()); 1703 DCHECK(UnhandledIsSorted());
1723 return; 1704 return;
1724 } 1705 }
(...skipping 27 matching lines...) Expand all
1752 std::sort(unhandled_live_ranges().begin(), unhandled_live_ranges().end(), 1733 std::sort(unhandled_live_ranges().begin(), unhandled_live_ranges().end(),
1753 &UnhandledSortHelper); 1734 &UnhandledSortHelper);
1754 } 1735 }
1755 1736
1756 1737
1757 bool LinearScanAllocator::UnhandledIsSorted() { 1738 bool LinearScanAllocator::UnhandledIsSorted() {
1758 size_t len = unhandled_live_ranges().size(); 1739 size_t len = unhandled_live_ranges().size();
1759 for (size_t i = 1; i < len; i++) { 1740 for (size_t i = 1; i < len; i++) {
1760 auto a = unhandled_live_ranges().at(i - 1); 1741 auto a = unhandled_live_ranges().at(i - 1);
1761 auto b = unhandled_live_ranges().at(i); 1742 auto b = unhandled_live_ranges().at(i);
1762 if (a->Start().Value() < b->Start().Value()) return false; 1743 if (a->Start() < b->Start()) return false;
1763 } 1744 }
1764 return true; 1745 return true;
1765 } 1746 }
1766 1747
1767 1748
1768 void LinearScanAllocator::ActiveToHandled(LiveRange* range) { 1749 void LinearScanAllocator::ActiveToHandled(LiveRange* range) {
1769 RemoveElement(&active_live_ranges(), range); 1750 RemoveElement(&active_live_ranges(), range);
1770 TRACE("Moving live range %d from active to handled\n", range->id()); 1751 TRACE("Moving live range %d from active to handled\n", range->id());
1771 } 1752 }
1772 1753
(...skipping 24 matching lines...) Expand all
1797 for (int i = 0; i < num_registers(); i++) { 1778 for (int i = 0; i < num_registers(); i++) {
1798 free_until_pos[i] = LifetimePosition::MaxPosition(); 1779 free_until_pos[i] = LifetimePosition::MaxPosition();
1799 } 1780 }
1800 1781
1801 for (auto cur_active : active_live_ranges()) { 1782 for (auto cur_active : active_live_ranges()) {
1802 free_until_pos[cur_active->assigned_register()] = 1783 free_until_pos[cur_active->assigned_register()] =
1803 LifetimePosition::GapFromInstructionIndex(0); 1784 LifetimePosition::GapFromInstructionIndex(0);
1804 } 1785 }
1805 1786
1806 for (auto cur_inactive : inactive_live_ranges()) { 1787 for (auto cur_inactive : inactive_live_ranges()) {
1807 DCHECK(cur_inactive->End().Value() > current->Start().Value()); 1788 DCHECK(cur_inactive->End() > current->Start());
1808 auto next_intersection = cur_inactive->FirstIntersection(current); 1789 auto next_intersection = cur_inactive->FirstIntersection(current);
1809 if (!next_intersection.IsValid()) continue; 1790 if (!next_intersection.IsValid()) continue;
1810 int cur_reg = cur_inactive->assigned_register(); 1791 int cur_reg = cur_inactive->assigned_register();
1811 free_until_pos[cur_reg] = Min(free_until_pos[cur_reg], next_intersection); 1792 free_until_pos[cur_reg] = Min(free_until_pos[cur_reg], next_intersection);
1812 } 1793 }
1813 1794
1814 auto hint = current->FirstHint(); 1795 auto hint = current->FirstHint();
1815 if (hint != nullptr && (hint->IsRegister() || hint->IsDoubleRegister())) { 1796 if (hint != nullptr && (hint->IsRegister() || hint->IsDoubleRegister())) {
1816 int register_index = AllocatedOperand::cast(hint)->index(); 1797 int register_index = AllocatedOperand::cast(hint)->index();
1817 TRACE("Found reg hint %s (free until [%d) for live range %d (end %d[).\n", 1798 TRACE("Found reg hint %s (free until [%d) for live range %d (end %d[).\n",
1818 RegisterName(register_index), free_until_pos[register_index].Value(), 1799 RegisterName(register_index), free_until_pos[register_index].value(),
1819 current->id(), current->End().Value()); 1800 current->id(), current->End().value());
1820 1801
1821 // The desired register is free until the end of the current live range. 1802 // The desired register is free until the end of the current live range.
1822 if (free_until_pos[register_index].Value() >= current->End().Value()) { 1803 if (free_until_pos[register_index] >= current->End()) {
1823 TRACE("Assigning preferred reg %s to live range %d\n", 1804 TRACE("Assigning preferred reg %s to live range %d\n",
1824 RegisterName(register_index), current->id()); 1805 RegisterName(register_index), current->id());
1825 data()->SetLiveRangeAssignedRegister(current, register_index); 1806 data()->SetLiveRangeAssignedRegister(current, register_index);
1826 return true; 1807 return true;
1827 } 1808 }
1828 } 1809 }
1829 1810
1830 // Find the register which stays free for the longest time. 1811 // Find the register which stays free for the longest time.
1831 int reg = 0; 1812 int reg = 0;
1832 for (int i = 1; i < num_registers(); ++i) { 1813 for (int i = 1; i < num_registers(); ++i) {
1833 if (free_until_pos[i].Value() > free_until_pos[reg].Value()) { 1814 if (free_until_pos[i] > free_until_pos[reg]) {
1834 reg = i; 1815 reg = i;
1835 } 1816 }
1836 } 1817 }
1837 1818
1838 auto pos = free_until_pos[reg]; 1819 auto pos = free_until_pos[reg];
1839 1820
1840 if (pos.Value() <= current->Start().Value()) { 1821 if (pos <= current->Start()) {
1841 // All registers are blocked. 1822 // All registers are blocked.
1842 return false; 1823 return false;
1843 } 1824 }
1844 1825
1845 if (pos.Value() < current->End().Value()) { 1826 if (pos < current->End()) {
1846 // Register reg is available at the range start but becomes blocked before 1827 // Register reg is available at the range start but becomes blocked before
1847 // the range end. Split current at position where it becomes blocked. 1828 // the range end. Split current at position where it becomes blocked.
1848 auto tail = SplitRangeAt(current, pos); 1829 auto tail = SplitRangeAt(current, pos);
1849 AddToUnhandledSorted(tail); 1830 AddToUnhandledSorted(tail);
1850 } 1831 }
1851 1832
1852 // Register reg is available at the range start and is free until 1833 // Register reg is available at the range start and is free until
1853 // the range end. 1834 // the range end.
1854 DCHECK(pos.Value() >= current->End().Value()); 1835 DCHECK(pos >= current->End());
1855 TRACE("Assigning free reg %s to live range %d\n", RegisterName(reg), 1836 TRACE("Assigning free reg %s to live range %d\n", RegisterName(reg),
1856 current->id()); 1837 current->id());
1857 data()->SetLiveRangeAssignedRegister(current, reg); 1838 data()->SetLiveRangeAssignedRegister(current, reg);
1858 1839
1859 return true; 1840 return true;
1860 } 1841 }
1861 1842
1862 1843
1863 void LinearScanAllocator::AllocateBlockedReg(LiveRange* current) { 1844 void LinearScanAllocator::AllocateBlockedReg(LiveRange* current) {
1864 auto register_use = current->NextRegisterPosition(current->Start()); 1845 auto register_use = current->NextRegisterPosition(current->Start());
(...skipping 21 matching lines...) Expand all
1886 range->NextUsePositionRegisterIsBeneficial(current->Start()); 1867 range->NextUsePositionRegisterIsBeneficial(current->Start());
1887 if (next_use == nullptr) { 1868 if (next_use == nullptr) {
1888 use_pos[cur_reg] = range->End(); 1869 use_pos[cur_reg] = range->End();
1889 } else { 1870 } else {
1890 use_pos[cur_reg] = next_use->pos(); 1871 use_pos[cur_reg] = next_use->pos();
1891 } 1872 }
1892 } 1873 }
1893 } 1874 }
1894 1875
1895 for (auto range : inactive_live_ranges()) { 1876 for (auto range : inactive_live_ranges()) {
1896 DCHECK(range->End().Value() > current->Start().Value()); 1877 DCHECK(range->End() > current->Start());
1897 auto next_intersection = range->FirstIntersection(current); 1878 auto next_intersection = range->FirstIntersection(current);
1898 if (!next_intersection.IsValid()) continue; 1879 if (!next_intersection.IsValid()) continue;
1899 int cur_reg = range->assigned_register(); 1880 int cur_reg = range->assigned_register();
1900 if (range->IsFixed()) { 1881 if (range->IsFixed()) {
1901 block_pos[cur_reg] = Min(block_pos[cur_reg], next_intersection); 1882 block_pos[cur_reg] = Min(block_pos[cur_reg], next_intersection);
1902 use_pos[cur_reg] = Min(block_pos[cur_reg], use_pos[cur_reg]); 1883 use_pos[cur_reg] = Min(block_pos[cur_reg], use_pos[cur_reg]);
1903 } else { 1884 } else {
1904 use_pos[cur_reg] = Min(use_pos[cur_reg], next_intersection); 1885 use_pos[cur_reg] = Min(use_pos[cur_reg], next_intersection);
1905 } 1886 }
1906 } 1887 }
1907 1888
1908 int reg = 0; 1889 int reg = 0;
1909 for (int i = 1; i < num_registers(); ++i) { 1890 for (int i = 1; i < num_registers(); ++i) {
1910 if (use_pos[i].Value() > use_pos[reg].Value()) { 1891 if (use_pos[i] > use_pos[reg]) {
1911 reg = i; 1892 reg = i;
1912 } 1893 }
1913 } 1894 }
1914 1895
1915 auto pos = use_pos[reg]; 1896 auto pos = use_pos[reg];
1916 1897
1917 if (pos.Value() < register_use->pos().Value()) { 1898 if (pos < register_use->pos()) {
1918 // All registers are blocked before the first use that requires a register. 1899 // All registers are blocked before the first use that requires a register.
1919 // Spill starting part of live range up to that use. 1900 // Spill starting part of live range up to that use.
1920 SpillBetween(current, current->Start(), register_use->pos()); 1901 SpillBetween(current, current->Start(), register_use->pos());
1921 return; 1902 return;
1922 } 1903 }
1923 1904
1924 if (block_pos[reg].Value() < current->End().Value()) { 1905 if (block_pos[reg] < current->End()) {
1925 // Register becomes blocked before the current range end. Split before that 1906 // Register becomes blocked before the current range end. Split before that
1926 // position. 1907 // position.
1927 LiveRange* tail = 1908 LiveRange* tail =
1928 SplitBetween(current, current->Start(), block_pos[reg].Start()); 1909 SplitBetween(current, current->Start(), block_pos[reg].Start());
1929 AddToUnhandledSorted(tail); 1910 AddToUnhandledSorted(tail);
1930 } 1911 }
1931 1912
1932 // Register reg is not blocked for the whole range. 1913 // Register reg is not blocked for the whole range.
1933 DCHECK(block_pos[reg].Value() >= current->End().Value()); 1914 DCHECK(block_pos[reg] >= current->End());
1934 TRACE("Assigning blocked reg %s to live range %d\n", RegisterName(reg), 1915 TRACE("Assigning blocked reg %s to live range %d\n", RegisterName(reg),
1935 current->id()); 1916 current->id());
1936 data()->SetLiveRangeAssignedRegister(current, reg); 1917 data()->SetLiveRangeAssignedRegister(current, reg);
1937 1918
1938 // This register was not free. Thus we need to find and spill 1919 // This register was not free. Thus we need to find and spill
1939 // parts of active and inactive live regions that use the same register 1920 // parts of active and inactive live regions that use the same register
1940 // at the same lifetime positions as current. 1921 // at the same lifetime positions as current.
1941 SplitAndSpillIntersecting(current); 1922 SplitAndSpillIntersecting(current);
1942 } 1923 }
1943 1924
(...skipping 20 matching lines...) Expand all
1964 // current live-range is larger than their end. 1945 // current live-range is larger than their end.
1965 SpillBetweenUntil(range, spill_pos, current->Start(), next_pos->pos()); 1946 SpillBetweenUntil(range, spill_pos, current->Start(), next_pos->pos());
1966 } 1947 }
1967 ActiveToHandled(range); 1948 ActiveToHandled(range);
1968 --i; 1949 --i;
1969 } 1950 }
1970 } 1951 }
1971 1952
1972 for (size_t i = 0; i < inactive_live_ranges().size(); ++i) { 1953 for (size_t i = 0; i < inactive_live_ranges().size(); ++i) {
1973 auto range = inactive_live_ranges()[i]; 1954 auto range = inactive_live_ranges()[i];
1974 DCHECK(range->End().Value() > current->Start().Value()); 1955 DCHECK(range->End() > current->Start());
1975 if (range->assigned_register() == reg && !range->IsFixed()) { 1956 if (range->assigned_register() == reg && !range->IsFixed()) {
1976 LifetimePosition next_intersection = range->FirstIntersection(current); 1957 LifetimePosition next_intersection = range->FirstIntersection(current);
1977 if (next_intersection.IsValid()) { 1958 if (next_intersection.IsValid()) {
1978 UsePosition* next_pos = range->NextRegisterPosition(current->Start()); 1959 UsePosition* next_pos = range->NextRegisterPosition(current->Start());
1979 if (next_pos == nullptr) { 1960 if (next_pos == nullptr) {
1980 SpillAfter(range, split_pos); 1961 SpillAfter(range, split_pos);
1981 } else { 1962 } else {
1982 next_intersection = Min(next_intersection, next_pos->pos()); 1963 next_intersection = Min(next_intersection, next_pos->pos());
1983 SpillBetween(range, split_pos, next_intersection); 1964 SpillBetween(range, split_pos, next_intersection);
1984 } 1965 }
(...skipping 69 matching lines...) Expand 10 before | Expand all | Expand 10 after
2054 auto pos = range->NextUsePositionRegisterIsBeneficial(next_pos); 2035 auto pos = range->NextUsePositionRegisterIsBeneficial(next_pos);
2055 if (pos == nullptr) { 2036 if (pos == nullptr) {
2056 auto spill_range = 2037 auto spill_range =
2057 range->TopLevel()->HasSpillRange() 2038 range->TopLevel()->HasSpillRange()
2058 ? range->TopLevel()->GetSpillRange() 2039 ? range->TopLevel()->GetSpillRange()
2059 : data()->AssignSpillRangeToLiveRange(range->TopLevel()); 2040 : data()->AssignSpillRangeToLiveRange(range->TopLevel());
2060 bool merged = first_op_spill->TryMerge(spill_range); 2041 bool merged = first_op_spill->TryMerge(spill_range);
2061 CHECK(merged); 2042 CHECK(merged);
2062 Spill(range); 2043 Spill(range);
2063 return true; 2044 return true;
2064 } else if (pos->pos().Value() > range->Start().NextStart().Value()) { 2045 } else if (pos->pos() > range->Start().NextStart()) {
2065 auto spill_range = 2046 auto spill_range =
2066 range->TopLevel()->HasSpillRange() 2047 range->TopLevel()->HasSpillRange()
2067 ? range->TopLevel()->GetSpillRange() 2048 ? range->TopLevel()->GetSpillRange()
2068 : data()->AssignSpillRangeToLiveRange(range->TopLevel()); 2049 : data()->AssignSpillRangeToLiveRange(range->TopLevel());
2069 bool merged = first_op_spill->TryMerge(spill_range); 2050 bool merged = first_op_spill->TryMerge(spill_range);
2070 CHECK(merged); 2051 CHECK(merged);
2071 SpillBetween(range, range->Start(), pos->pos()); 2052 SpillBetween(range, range->Start(), pos->pos());
2072 DCHECK(UnhandledIsSorted()); 2053 DCHECK(UnhandledIsSorted());
2073 return true; 2054 return true;
2074 } 2055 }
(...skipping 10 matching lines...) Expand all
2085 void LinearScanAllocator::SpillBetween(LiveRange* range, LifetimePosition start, 2066 void LinearScanAllocator::SpillBetween(LiveRange* range, LifetimePosition start,
2086 LifetimePosition end) { 2067 LifetimePosition end) {
2087 SpillBetweenUntil(range, start, start, end); 2068 SpillBetweenUntil(range, start, start, end);
2088 } 2069 }
2089 2070
2090 2071
2091 void LinearScanAllocator::SpillBetweenUntil(LiveRange* range, 2072 void LinearScanAllocator::SpillBetweenUntil(LiveRange* range,
2092 LifetimePosition start, 2073 LifetimePosition start,
2093 LifetimePosition until, 2074 LifetimePosition until,
2094 LifetimePosition end) { 2075 LifetimePosition end) {
2095 CHECK(start.Value() < end.Value()); 2076 CHECK(start < end);
2096 auto second_part = SplitRangeAt(range, start); 2077 auto second_part = SplitRangeAt(range, start);
2097 2078
2098 if (second_part->Start().Value() < end.Value()) { 2079 if (second_part->Start() < end) {
2099 // The split result intersects with [start, end[. 2080 // The split result intersects with [start, end[.
2100 // Split it at position between ]start+1, end[, spill the middle part 2081 // Split it at position between ]start+1, end[, spill the middle part
2101 // and put the rest to unhandled. 2082 // and put the rest to unhandled.
2102 auto third_part_end = end.PrevStart().End(); 2083 auto third_part_end = end.PrevStart().End();
2103 if (IsBlockBoundary(code(), end.Start())) { 2084 if (IsBlockBoundary(code(), end.Start())) {
2104 third_part_end = end.Start(); 2085 third_part_end = end.Start();
2105 } 2086 }
2106 auto third_part = SplitBetween( 2087 auto third_part = SplitBetween(
2107 second_part, Max(second_part->Start().End(), until), third_part_end); 2088 second_part, Max(second_part->Start().End(), until), third_part_end);
2108 2089
(...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after
2162 static Value NoValue() { return nullptr; } 2143 static Value NoValue() { return nullptr; }
2163 static int Compare(const Key& a, const Key& b) { 2144 static int Compare(const Key& a, const Key& b) {
2164 if (a.second <= b.first) return -1; 2145 if (a.second <= b.first) return -1;
2165 if (a.first >= b.second) return 1; 2146 if (a.first >= b.second) return 1;
2166 return 0; 2147 return 0;
2167 } 2148 }
2168 }; 2149 };
2169 2150
2170 Config::Key GetKey(UseInterval* interval) { 2151 Config::Key GetKey(UseInterval* interval) {
2171 if (interval == nullptr) return std::make_pair(0, 0); 2152 if (interval == nullptr) return std::make_pair(0, 0);
2172 return std::make_pair(interval->start().Value(), interval->end().Value()); 2153 return std::make_pair(interval->start().value(), interval->end().value());
2173 } 2154 }
2174 2155
2175 // TODO(mtrofin): Change to void returning if we do not care if the interval 2156 // TODO(mtrofin): Change to void returning if we do not care if the interval
2176 // was previously added. 2157 // was previously added.
2177 bool Insert(UseInterval* interval, LiveRange* range) { 2158 bool Insert(UseInterval* interval, LiveRange* range) {
2178 ZoneSplayTree<Config>::Locator locator; 2159 ZoneSplayTree<Config>::Locator locator;
2179 bool ret = storage_.Insert(GetKey(interval), &locator); 2160 bool ret = storage_.Insert(GetKey(interval), &locator);
2180 if (ret) locator.set_value(range); 2161 if (ret) locator.set_value(range);
2181 return ret; 2162 return ret;
2182 } 2163 }
(...skipping 13 matching lines...) Expand all
2196 allocations_(local_zone), 2177 allocations_(local_zone),
2197 queue_(local_zone) {} 2178 queue_(local_zone) {}
2198 2179
2199 2180
2200 unsigned GreedyAllocator::GetLiveRangeSize(LiveRange* range) { 2181 unsigned GreedyAllocator::GetLiveRangeSize(LiveRange* range) {
2201 auto interval = range->first_interval(); 2182 auto interval = range->first_interval();
2202 if (interval == nullptr) return 0; 2183 if (interval == nullptr) return 0;
2203 2184
2204 unsigned size = 0; 2185 unsigned size = 0;
2205 while (interval != nullptr) { 2186 while (interval != nullptr) {
2206 size += (interval->end().Value() - interval->start().Value()); 2187 size += (interval->end().value() - interval->start().value());
2207 interval = interval->next(); 2188 interval = interval->next();
2208 } 2189 }
2209 2190
2210 return size; 2191 return size;
2211 } 2192 }
2212 2193
2213 2194
2214 void GreedyAllocator::AssignRangeToRegister(int reg_id, LiveRange* range) { 2195 void GreedyAllocator::AssignRangeToRegister(int reg_id, LiveRange* range) {
2215 allocations_[reg_id]->Insert(range); 2196 allocations_[reg_id]->Insert(range);
2216 if (range->HasRegisterAssigned()) { 2197 if (range->HasRegisterAssigned()) {
(...skipping 83 matching lines...) Expand 10 before | Expand all | Expand 10 after
2300 return true; 2281 return true;
2301 } 2282 }
2302 } 2283 }
2303 return false; 2284 return false;
2304 } 2285 }
2305 2286
2306 LiveRange* GreedyAllocator::SpillBetweenUntil(LiveRange* range, 2287 LiveRange* GreedyAllocator::SpillBetweenUntil(LiveRange* range,
2307 LifetimePosition start, 2288 LifetimePosition start,
2308 LifetimePosition until, 2289 LifetimePosition until,
2309 LifetimePosition end) { 2290 LifetimePosition end) {
2310 CHECK(start.Value() < end.Value()); 2291 CHECK(start < end);
2311 auto second_part = SplitRangeAt(range, start); 2292 auto second_part = SplitRangeAt(range, start);
2312 2293
2313 if (second_part->Start().Value() < end.Value()) { 2294 if (second_part->Start() < end) {
2314 // The split result intersects with [start, end[. 2295 // The split result intersects with [start, end[.
2315 // Split it at position between ]start+1, end[, spill the middle part 2296 // Split it at position between ]start+1, end[, spill the middle part
2316 // and put the rest to unhandled. 2297 // and put the rest to unhandled.
2317 auto third_part_end = end.PrevStart().End(); 2298 auto third_part_end = end.PrevStart().End();
2318 if (IsBlockBoundary(code(), end.Start())) { 2299 if (IsBlockBoundary(code(), end.Start())) {
2319 third_part_end = end.Start(); 2300 third_part_end = end.Start();
2320 } 2301 }
2321 auto third_part = SplitBetween( 2302 auto third_part = SplitBetween(
2322 second_part, Max(second_part->Start().End(), until), third_part_end); 2303 second_part, Max(second_part->Start().End(), until), third_part_end);
2323 2304
(...skipping 13 matching lines...) Expand all
2337 if (range == nullptr || range->IsEmpty()) return; 2318 if (range == nullptr || range->IsEmpty()) return;
2338 unsigned size = GetLiveRangeSize(range); 2319 unsigned size = GetLiveRangeSize(range);
2339 queue_.push(std::make_pair(size, range)); 2320 queue_.push(std::make_pair(size, range));
2340 } 2321 }
2341 2322
2342 2323
2343 // TODO(mtrofin): consolidate with identical code segment in 2324 // TODO(mtrofin): consolidate with identical code segment in
2344 // LinearScanAllocator::AllocateRegisters 2325 // LinearScanAllocator::AllocateRegisters
2345 bool GreedyAllocator::HandleSpillOperands(LiveRange* range) { 2326 bool GreedyAllocator::HandleSpillOperands(LiveRange* range) {
2346 auto position = range->Start(); 2327 auto position = range->Start();
2347 TRACE("Processing interval %d start=%d\n", range->id(), position.Value()); 2328 TRACE("Processing interval %d start=%d\n", range->id(), position.value());
2348 2329
2349 if (!range->HasNoSpillType()) { 2330 if (!range->HasNoSpillType()) {
2350 TRACE("Live range %d already has a spill operand\n", range->id()); 2331 TRACE("Live range %d already has a spill operand\n", range->id());
2351 auto next_pos = position; 2332 auto next_pos = position;
2352 if (next_pos.IsGapPosition()) { 2333 if (next_pos.IsGapPosition()) {
2353 next_pos = next_pos.NextStart(); 2334 next_pos = next_pos.NextStart();
2354 } 2335 }
2355 auto pos = range->NextUsePositionRegisterIsBeneficial(next_pos); 2336 auto pos = range->NextUsePositionRegisterIsBeneficial(next_pos);
2356 // If the range already has a spill operand and it doesn't need a 2337 // If the range already has a spill operand and it doesn't need a
2357 // register immediately, split it and spill the first part of the range. 2338 // register immediately, split it and spill the first part of the range.
2358 if (pos == nullptr) { 2339 if (pos == nullptr) {
2359 Spill(range); 2340 Spill(range);
2360 return true; 2341 return true;
2361 } else if (pos->pos().Value() > range->Start().NextStart().Value()) { 2342 } else if (pos->pos() > range->Start().NextStart()) {
2362 // Do not spill live range eagerly if use position that can benefit from 2343 // Do not spill live range eagerly if use position that can benefit from
2363 // the register is too close to the start of live range. 2344 // the register is too close to the start of live range.
2364 auto* reminder = SpillBetweenUntil(range, position, position, pos->pos()); 2345 auto* reminder = SpillBetweenUntil(range, position, position, pos->pos());
2365 Enqueue(reminder); 2346 Enqueue(reminder);
2366 return true; 2347 return true;
2367 } 2348 }
2368 } 2349 }
2369 return false; 2350 return false;
2370 // TODO(mtrofin): Do we need this? 2351 // TODO(mtrofin): Do we need this?
2371 // return (TryReuseSpillForPhi(range)); 2352 // return (TryReuseSpillForPhi(range));
(...skipping 206 matching lines...) Expand 10 before | Expand all | Expand 10 after
2578 !range->GetSpillOperand()->IsConstant()) { 2559 !range->GetSpillOperand()->IsConstant()) {
2579 TRACE("Pointer for range %d (spilled at %d) at safe point %d\n", 2560 TRACE("Pointer for range %d (spilled at %d) at safe point %d\n",
2580 range->id(), range->spill_start_index(), safe_point); 2561 range->id(), range->spill_start_index(), safe_point);
2581 map->RecordReference(*range->GetSpillOperand()); 2562 map->RecordReference(*range->GetSpillOperand());
2582 } 2563 }
2583 2564
2584 if (!cur->IsSpilled()) { 2565 if (!cur->IsSpilled()) {
2585 TRACE( 2566 TRACE(
2586 "Pointer in register for range %d (start at %d) " 2567 "Pointer in register for range %d (start at %d) "
2587 "at safe point %d\n", 2568 "at safe point %d\n",
2588 cur->id(), cur->Start().Value(), safe_point); 2569 cur->id(), cur->Start().value(), safe_point);
2589 auto operand = cur->GetAssignedOperand(); 2570 auto operand = cur->GetAssignedOperand();
2590 DCHECK(!operand.IsStackSlot()); 2571 DCHECK(!operand.IsStackSlot());
2591 map->RecordReference(operand); 2572 map->RecordReference(operand);
2592 } 2573 }
2593 } 2574 }
2594 } 2575 }
2595 } 2576 }
2596 2577
2597 2578
2598 namespace { 2579 namespace {
2599 2580
2600 class LiveRangeBound { 2581 class LiveRangeBound {
2601 public: 2582 public:
2602 explicit LiveRangeBound(const LiveRange* range) 2583 explicit LiveRangeBound(const LiveRange* range)
2603 : range_(range), start_(range->Start()), end_(range->End()) { 2584 : range_(range), start_(range->Start()), end_(range->End()) {
2604 DCHECK(!range->IsEmpty()); 2585 DCHECK(!range->IsEmpty());
2605 } 2586 }
2606 2587
2607 bool CanCover(LifetimePosition position) { 2588 bool CanCover(LifetimePosition position) {
2608 return start_.Value() <= position.Value() && 2589 return start_ <= position && position < end_;
2609 position.Value() < end_.Value();
2610 } 2590 }
2611 2591
2612 const LiveRange* const range_; 2592 const LiveRange* const range_;
2613 const LifetimePosition start_; 2593 const LifetimePosition start_;
2614 const LifetimePosition end_; 2594 const LifetimePosition end_;
2615 2595
2616 private: 2596 private:
2617 DISALLOW_COPY_AND_ASSIGN(LiveRangeBound); 2597 DISALLOW_COPY_AND_ASSIGN(LiveRangeBound);
2618 }; 2598 };
2619 2599
(...skipping 21 matching lines...) Expand all
2641 } 2621 }
2642 } 2622 }
2643 2623
2644 LiveRangeBound* Find(const LifetimePosition position) const { 2624 LiveRangeBound* Find(const LifetimePosition position) const {
2645 size_t left_index = 0; 2625 size_t left_index = 0;
2646 size_t right_index = length_; 2626 size_t right_index = length_;
2647 while (true) { 2627 while (true) {
2648 size_t current_index = left_index + (right_index - left_index) / 2; 2628 size_t current_index = left_index + (right_index - left_index) / 2;
2649 DCHECK(right_index > current_index); 2629 DCHECK(right_index > current_index);
2650 auto bound = &start_[current_index]; 2630 auto bound = &start_[current_index];
2651 if (bound->start_.Value() <= position.Value()) { 2631 if (bound->start_ <= position) {
2652 if (position.Value() < bound->end_.Value()) return bound; 2632 if (position < bound->end_) return bound;
2653 DCHECK(left_index < current_index); 2633 DCHECK(left_index < current_index);
2654 left_index = current_index; 2634 left_index = current_index;
2655 } else { 2635 } else {
2656 right_index = current_index; 2636 right_index = current_index;
2657 } 2637 }
2658 } 2638 }
2659 } 2639 }
2660 2640
2661 LiveRangeBound* FindPred(const InstructionBlock* pred) { 2641 LiveRangeBound* FindPred(const InstructionBlock* pred) {
2662 auto pred_end = LifetimePosition::InstructionFromInstructionIndex( 2642 auto pred_end = LifetimePosition::InstructionFromInstructionIndex(
(...skipping 132 matching lines...) Expand 10 before | Expand all | Expand 10 after
2795 ZoneMap<std::pair<ParallelMove*, InstructionOperand>, InstructionOperand> 2775 ZoneMap<std::pair<ParallelMove*, InstructionOperand>, InstructionOperand>
2796 delayed_insertion_map(local_zone); 2776 delayed_insertion_map(local_zone);
2797 for (auto first_range : data()->live_ranges()) { 2777 for (auto first_range : data()->live_ranges()) {
2798 if (first_range == nullptr || first_range->IsChild()) continue; 2778 if (first_range == nullptr || first_range->IsChild()) continue;
2799 for (auto second_range = first_range->next(); second_range != nullptr; 2779 for (auto second_range = first_range->next(); second_range != nullptr;
2800 first_range = second_range, second_range = second_range->next()) { 2780 first_range = second_range, second_range = second_range->next()) {
2801 auto pos = second_range->Start(); 2781 auto pos = second_range->Start();
2802 // Add gap move if the two live ranges touch and there is no block 2782 // Add gap move if the two live ranges touch and there is no block
2803 // boundary. 2783 // boundary.
2804 if (second_range->IsSpilled()) continue; 2784 if (second_range->IsSpilled()) continue;
2805 if (first_range->End().Value() != pos.Value()) continue; 2785 if (first_range->End() != pos) continue;
2806 if (IsBlockBoundary(code(), pos) && 2786 if (IsBlockBoundary(code(), pos) &&
2807 !CanEagerlyResolveControlFlow(GetInstructionBlock(code(), pos))) { 2787 !CanEagerlyResolveControlFlow(GetInstructionBlock(code(), pos))) {
2808 continue; 2788 continue;
2809 } 2789 }
2810 auto prev_operand = first_range->GetAssignedOperand(); 2790 auto prev_operand = first_range->GetAssignedOperand();
2811 auto cur_operand = second_range->GetAssignedOperand(); 2791 auto cur_operand = second_range->GetAssignedOperand();
2812 if (prev_operand == cur_operand) continue; 2792 if (prev_operand == cur_operand) continue;
2813 bool delay_insertion = false; 2793 bool delay_insertion = false;
2814 Instruction::GapPosition gap_pos; 2794 Instruction::GapPosition gap_pos;
2815 int gap_index = pos.ToInstructionIndex(); 2795 int gap_index = pos.ToInstructionIndex();
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after
2861 auto eliminate = moves->PrepareInsertAfter(move); 2841 auto eliminate = moves->PrepareInsertAfter(move);
2862 to_insert.push_back(move); 2842 to_insert.push_back(move);
2863 if (eliminate != nullptr) to_eliminate.push_back(eliminate); 2843 if (eliminate != nullptr) to_eliminate.push_back(eliminate);
2864 } 2844 }
2865 } 2845 }
2866 2846
2867 2847
2868 } // namespace compiler 2848 } // namespace compiler
2869 } // namespace internal 2849 } // namespace internal
2870 } // namespace v8 2850 } // namespace v8
OLDNEW
« no previous file with comments | « src/compiler/register-allocator.h ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698