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 |