| OLD | NEW |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 |
| OLD | NEW |