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 #ifndef V8_REGISTER_ALLOCATOR_H_ | 5 #ifndef V8_REGISTER_ALLOCATOR_H_ |
6 #define V8_REGISTER_ALLOCATOR_H_ | 6 #define V8_REGISTER_ALLOCATOR_H_ |
7 | 7 |
8 #include "src/compiler/instruction.h" | 8 #include "src/compiler/instruction.h" |
9 #include "src/zone-containers.h" | 9 #include "src/zone-containers.h" |
10 | 10 |
(...skipping 178 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
189 LifetimePosition end_; | 189 LifetimePosition end_; |
190 UseInterval* next_; | 190 UseInterval* next_; |
191 | 191 |
192 DISALLOW_COPY_AND_ASSIGN(UseInterval); | 192 DISALLOW_COPY_AND_ASSIGN(UseInterval); |
193 }; | 193 }; |
194 | 194 |
195 | 195 |
196 enum class UsePositionType : uint8_t { kAny, kRequiresRegister, kRequiresSlot }; | 196 enum class UsePositionType : uint8_t { kAny, kRequiresRegister, kRequiresSlot }; |
197 | 197 |
198 | 198 |
| 199 enum class UsePositionHintType : uint8_t { |
| 200 kNone, |
| 201 kOperand, |
| 202 kUsePos, |
| 203 kPhi, |
| 204 kUnresolved |
| 205 }; |
| 206 |
| 207 |
| 208 static const int32_t kUnassignedRegister = |
| 209 RegisterConfiguration::kMaxGeneralRegisters; |
| 210 |
| 211 |
| 212 static_assert(kUnassignedRegister <= RegisterConfiguration::kMaxDoubleRegisters, |
| 213 "kUnassignedRegister too small"); |
| 214 |
| 215 |
199 // Representation of a use position. | 216 // Representation of a use position. |
200 class UsePosition final : public ZoneObject { | 217 class UsePosition final : public ZoneObject { |
201 public: | 218 public: |
202 UsePosition(LifetimePosition pos, InstructionOperand* operand, | 219 UsePosition(LifetimePosition pos, InstructionOperand* operand, void* hint, |
203 InstructionOperand* hint); | 220 UsePositionHintType hint_type); |
204 | 221 |
205 InstructionOperand* operand() const { return operand_; } | 222 InstructionOperand* operand() const { return operand_; } |
206 bool HasOperand() const { return operand_ != nullptr; } | 223 bool HasOperand() const { return operand_ != nullptr; } |
207 | 224 |
208 InstructionOperand* hint() const { return hint_; } | |
209 bool HasHint() const; | |
210 bool RegisterIsBeneficial() const { | 225 bool RegisterIsBeneficial() const { |
211 return RegisterBeneficialField::decode(flags_); | 226 return RegisterBeneficialField::decode(flags_); |
212 } | 227 } |
213 UsePositionType type() const { return TypeField::decode(flags_); } | 228 UsePositionType type() const { return TypeField::decode(flags_); } |
| 229 void set_type(UsePositionType type, bool register_beneficial); |
214 | 230 |
215 LifetimePosition pos() const { return pos_; } | 231 LifetimePosition pos() const { return pos_; } |
| 232 |
216 UsePosition* next() const { return next_; } | 233 UsePosition* next() const { return next_; } |
| 234 void set_next(UsePosition* next) { next_ = next; } |
217 | 235 |
218 void set_next(UsePosition* next) { next_ = next; } | 236 // For hinting only. |
219 void set_type(UsePositionType type, bool register_beneficial); | 237 void set_assigned_register(int register_index) { |
| 238 flags_ = AssignedRegisterField::update(flags_, register_index); |
| 239 } |
| 240 |
| 241 UsePositionHintType hint_type() const { |
| 242 return HintTypeField::decode(flags_); |
| 243 } |
| 244 bool HasHint() const; |
| 245 bool HintRegister(int* register_index) const; |
| 246 void ResolveHint(UsePosition* use_pos); |
| 247 bool IsResolved() const { |
| 248 return hint_type() != UsePositionHintType::kUnresolved; |
| 249 } |
| 250 static UsePositionHintType HintTypeForOperand(const InstructionOperand& op); |
220 | 251 |
221 private: | 252 private: |
222 typedef BitField8<UsePositionType, 0, 2> TypeField; | 253 typedef BitField<UsePositionType, 0, 2> TypeField; |
223 typedef BitField8<bool, 2, 1> RegisterBeneficialField; | 254 typedef BitField<UsePositionHintType, 2, 3> HintTypeField; |
| 255 typedef BitField<bool, 5, 1> RegisterBeneficialField; |
| 256 typedef BitField<int32_t, 6, 6> AssignedRegisterField; |
224 | 257 |
225 InstructionOperand* const operand_; | 258 InstructionOperand* const operand_; |
226 InstructionOperand* const hint_; | 259 void* hint_; |
| 260 UsePosition* next_; |
227 LifetimePosition const pos_; | 261 LifetimePosition const pos_; |
228 UsePosition* next_; | 262 uint32_t flags_; |
229 uint8_t flags_; | |
230 | 263 |
231 DISALLOW_COPY_AND_ASSIGN(UsePosition); | 264 DISALLOW_COPY_AND_ASSIGN(UsePosition); |
232 }; | 265 }; |
233 | 266 |
| 267 |
234 class SpillRange; | 268 class SpillRange; |
235 | 269 |
236 | 270 |
237 // Representation of SSA values' live ranges as a collection of (continuous) | 271 // Representation of SSA values' live ranges as a collection of (continuous) |
238 // intervals over the instruction ordering. | 272 // intervals over the instruction ordering. |
239 class LiveRange final : public ZoneObject { | 273 class LiveRange final : public ZoneObject { |
240 public: | 274 public: |
241 static const int kInvalidAssignment = 0x7fffffff; | |
242 | |
243 explicit LiveRange(int id); | 275 explicit LiveRange(int id); |
244 | 276 |
245 UseInterval* first_interval() const { return first_interval_; } | 277 UseInterval* first_interval() const { return first_interval_; } |
246 UsePosition* first_pos() const { return first_pos_; } | 278 UsePosition* first_pos() const { return first_pos_; } |
247 LiveRange* parent() const { return parent_; } | 279 LiveRange* parent() const { return parent_; } |
248 LiveRange* TopLevel() { return (parent_ == nullptr) ? this : parent_; } | 280 LiveRange* TopLevel() { return (parent_ == nullptr) ? this : parent_; } |
249 const LiveRange* TopLevel() const { | 281 const LiveRange* TopLevel() const { |
250 return (parent_ == nullptr) ? this : parent_; | 282 return (parent_ == nullptr) ? this : parent_; |
251 } | 283 } |
252 LiveRange* next() const { return next_; } | 284 LiveRange* next() const { return next_; } |
253 bool IsChild() const { return parent() != nullptr; } | 285 bool IsChild() const { return parent() != nullptr; } |
254 int id() const { return id_; } | 286 int id() const { return id_; } |
255 bool IsFixed() const { return id_ < 0; } | 287 bool IsFixed() const { return id_ < 0; } |
256 bool IsEmpty() const { return first_interval() == nullptr; } | 288 bool IsEmpty() const { return first_interval() == nullptr; } |
257 InstructionOperand GetAssignedOperand() const; | 289 InstructionOperand GetAssignedOperand() const; |
258 int assigned_register() const { return assigned_register_; } | 290 int assigned_register() const { return assigned_register_; } |
259 int spill_start_index() const { return spill_start_index_; } | 291 int spill_start_index() const { return spill_start_index_; } |
260 void set_assigned_register(int reg); | 292 void set_assigned_register(int reg); |
| 293 void UnsetAssignedRegister(); |
261 void MakeSpilled(); | 294 void MakeSpilled(); |
262 bool is_phi() const { return is_phi_; } | 295 bool is_phi() const { return is_phi_; } |
263 void set_is_phi(bool is_phi) { is_phi_ = is_phi; } | 296 void set_is_phi(bool is_phi) { is_phi_ = is_phi; } |
264 bool is_non_loop_phi() const { return is_non_loop_phi_; } | 297 bool is_non_loop_phi() const { return is_non_loop_phi_; } |
265 void set_is_non_loop_phi(bool is_non_loop_phi) { | 298 void set_is_non_loop_phi(bool is_non_loop_phi) { |
266 is_non_loop_phi_ = is_non_loop_phi; | 299 is_non_loop_phi_ = is_non_loop_phi; |
267 } | 300 } |
268 bool has_slot_use() const { return has_slot_use_; } | 301 bool has_slot_use() const { return has_slot_use_; } |
269 void set_has_slot_use(bool has_slot_use) { has_slot_use_ = has_slot_use; } | 302 void set_has_slot_use(bool has_slot_use) { has_slot_use_ = has_slot_use; } |
270 | 303 |
(...skipping 19 matching lines...) Expand all Loading... |
290 bool CanBeSpilled(LifetimePosition pos) const; | 323 bool CanBeSpilled(LifetimePosition pos) const; |
291 | 324 |
292 // Split this live range at the given position which must follow the start of | 325 // Split this live range at the given position which must follow the start of |
293 // the range. | 326 // the range. |
294 // All uses following the given position will be moved from this | 327 // All uses following the given position will be moved from this |
295 // live range to the result live range. | 328 // live range to the result live range. |
296 void SplitAt(LifetimePosition position, LiveRange* result, Zone* zone); | 329 void SplitAt(LifetimePosition position, LiveRange* result, Zone* zone); |
297 | 330 |
298 RegisterKind Kind() const { return kind_; } | 331 RegisterKind Kind() const { return kind_; } |
299 bool HasRegisterAssigned() const { | 332 bool HasRegisterAssigned() const { |
300 return assigned_register_ != kInvalidAssignment; | 333 return assigned_register_ != kUnassignedRegister; |
301 } | 334 } |
302 bool IsSpilled() const { return spilled_; } | 335 bool IsSpilled() const { return spilled_; } |
303 | 336 |
304 InstructionOperand* current_hint_operand() const { | 337 // Returns nullptr when no register is hinted, otherwise sets register_index. |
305 DCHECK(current_hint_operand_ == FirstHint()); | 338 UsePosition* FirstHintPosition(int* register_index) const; |
306 return current_hint_operand_; | 339 UsePosition* FirstHintPosition() const { |
| 340 int register_index; |
| 341 return FirstHintPosition(®ister_index); |
307 } | 342 } |
308 InstructionOperand* FirstHint() const { | 343 |
309 UsePosition* pos = first_pos_; | 344 UsePosition* current_hint_position() const { |
310 while (pos != nullptr && !pos->HasHint()) pos = pos->next(); | 345 DCHECK(current_hint_position_ == FirstHintPosition()); |
311 if (pos != nullptr) return pos->hint(); | 346 return current_hint_position_; |
312 return nullptr; | |
313 } | 347 } |
314 | 348 |
315 LifetimePosition Start() const { | 349 LifetimePosition Start() const { |
316 DCHECK(!IsEmpty()); | 350 DCHECK(!IsEmpty()); |
317 return first_interval()->start(); | 351 return first_interval()->start(); |
318 } | 352 } |
319 | 353 |
320 LifetimePosition End() const { | 354 LifetimePosition End() const { |
321 DCHECK(!IsEmpty()); | 355 DCHECK(!IsEmpty()); |
322 return last_interval_->end(); | 356 return last_interval_->end(); |
(...skipping 29 matching lines...) Expand all Loading... |
352 } | 386 } |
353 | 387 |
354 bool ShouldBeAllocatedBefore(const LiveRange* other) const; | 388 bool ShouldBeAllocatedBefore(const LiveRange* other) const; |
355 bool CanCover(LifetimePosition position) const; | 389 bool CanCover(LifetimePosition position) const; |
356 bool Covers(LifetimePosition position) const; | 390 bool Covers(LifetimePosition position) const; |
357 LifetimePosition FirstIntersection(LiveRange* other) const; | 391 LifetimePosition FirstIntersection(LiveRange* other) const; |
358 | 392 |
359 // Add a new interval or a new use position to this live range. | 393 // Add a new interval or a new use position to this live range. |
360 void EnsureInterval(LifetimePosition start, LifetimePosition end, Zone* zone); | 394 void EnsureInterval(LifetimePosition start, LifetimePosition end, Zone* zone); |
361 void AddUseInterval(LifetimePosition start, LifetimePosition end, Zone* zone); | 395 void AddUseInterval(LifetimePosition start, LifetimePosition end, Zone* zone); |
362 void AddUsePosition(LifetimePosition pos, InstructionOperand* operand, | 396 void AddUsePosition(UsePosition* pos); |
363 InstructionOperand* hint, Zone* zone); | |
364 | 397 |
365 // Shorten the most recently added interval by setting a new start. | 398 // Shorten the most recently added interval by setting a new start. |
366 void ShortenTo(LifetimePosition start); | 399 void ShortenTo(LifetimePosition start); |
367 | 400 |
368 void Verify() const; | 401 void Verify() const; |
369 | 402 |
370 void ConvertUsesToOperand(const InstructionOperand& op, | 403 void ConvertUsesToOperand(const InstructionOperand& op, |
371 InstructionOperand* spill_op); | 404 InstructionOperand* spill_op); |
| 405 void SetUseHints(int register_index); |
| 406 void UnsetUseHints() { SetUseHints(kUnassignedRegister); } |
372 | 407 |
373 void set_kind(RegisterKind kind) { kind_ = kind; } | 408 void set_kind(RegisterKind kind) { kind_ = kind; } |
374 | 409 |
375 private: | 410 private: |
376 struct SpillAtDefinitionList; | 411 struct SpillAtDefinitionList; |
377 | 412 |
378 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; | 413 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; |
379 void AdvanceLastProcessedMarker(UseInterval* to_start_of, | 414 void AdvanceLastProcessedMarker(UseInterval* to_start_of, |
380 LifetimePosition but_not_past) const; | 415 LifetimePosition but_not_past) const; |
381 | 416 |
382 // TODO(dcarney): pack this structure better. | 417 // TODO(dcarney): pack this structure better. |
383 int id_; | 418 int id_; |
384 bool spilled_ : 1; | 419 bool spilled_ : 1; |
385 bool has_slot_use_ : 1; // Relevant only for parent. | 420 bool has_slot_use_ : 1; // Relevant only for parent. |
386 bool is_phi_ : 1; | 421 bool is_phi_ : 1; // Correct only for parent. |
387 bool is_non_loop_phi_ : 1; | 422 bool is_non_loop_phi_ : 1; // Correct only for parent. |
388 RegisterKind kind_; | 423 RegisterKind kind_; |
389 int assigned_register_; | 424 int assigned_register_; |
390 UseInterval* last_interval_; | 425 UseInterval* last_interval_; |
391 UseInterval* first_interval_; | 426 UseInterval* first_interval_; |
392 UsePosition* first_pos_; | 427 UsePosition* first_pos_; |
393 LiveRange* parent_; | 428 LiveRange* parent_; |
394 LiveRange* next_; | 429 LiveRange* next_; |
395 // This is used as a cache, it doesn't affect correctness. | 430 // This is used as a cache, it doesn't affect correctness. |
396 mutable UseInterval* current_interval_; | 431 mutable UseInterval* current_interval_; |
397 // This is used as a cache, it doesn't affect correctness. | 432 // This is used as a cache, it doesn't affect correctness. |
398 mutable UsePosition* last_processed_use_; | 433 mutable UsePosition* last_processed_use_; |
399 // This is used as a cache, it's invalid outside of BuildLiveRanges. | 434 // This is used as a cache, it's invalid outside of BuildLiveRanges. |
400 mutable InstructionOperand* current_hint_operand_; | 435 mutable UsePosition* current_hint_position_; |
401 int spill_start_index_; | 436 int spill_start_index_; |
402 SpillType spill_type_; | 437 SpillType spill_type_; |
403 union { | 438 union { |
404 InstructionOperand* spill_operand_; | 439 InstructionOperand* spill_operand_; |
405 SpillRange* spill_range_; | 440 SpillRange* spill_range_; |
406 }; | 441 }; |
407 SpillAtDefinitionList* spills_at_definition_; | 442 SpillAtDefinitionList* spills_at_definition_; |
408 | 443 |
409 DISALLOW_COPY_AND_ASSIGN(LiveRange); | 444 DISALLOW_COPY_AND_ASSIGN(LiveRange); |
410 }; | 445 }; |
(...skipping 21 matching lines...) Expand all Loading... |
432 LifetimePosition end_position_; | 467 LifetimePosition end_position_; |
433 | 468 |
434 DISALLOW_COPY_AND_ASSIGN(SpillRange); | 469 DISALLOW_COPY_AND_ASSIGN(SpillRange); |
435 }; | 470 }; |
436 | 471 |
437 | 472 |
438 class RegisterAllocationData final : public ZoneObject { | 473 class RegisterAllocationData final : public ZoneObject { |
439 public: | 474 public: |
440 class PhiMapValue : public ZoneObject { | 475 class PhiMapValue : public ZoneObject { |
441 public: | 476 public: |
442 PhiMapValue(PhiInstruction* phi, const InstructionBlock* block, Zone* zone) | 477 PhiMapValue(PhiInstruction* phi, const InstructionBlock* block, Zone* zone); |
443 : phi(phi), block(block), incoming_moves(zone) { | 478 |
444 incoming_moves.reserve(phi->operands().size()); | 479 const PhiInstruction* phi() const { return phi_; } |
| 480 const InstructionBlock* block() const { return block_; } |
| 481 |
| 482 // For hinting. |
| 483 int assigned_register() const { return assigned_register_; } |
| 484 void set_assigned_register(int register_index) { |
| 485 DCHECK_EQ(assigned_register_, kUnassignedRegister); |
| 486 assigned_register_ = register_index; |
445 } | 487 } |
446 PhiInstruction* const phi; | 488 void UnsetAssignedRegister() { assigned_register_ = kUnassignedRegister; } |
447 const InstructionBlock* const block; | 489 |
448 ZoneVector<MoveOperands*> incoming_moves; | 490 void AddOperand(InstructionOperand* operand); |
| 491 void CommitAssignment(const InstructionOperand& operand); |
| 492 |
| 493 private: |
| 494 PhiInstruction* const phi_; |
| 495 const InstructionBlock* const block_; |
| 496 ZoneVector<InstructionOperand*> incoming_operands_; |
| 497 int assigned_register_; |
449 }; | 498 }; |
450 typedef ZoneMap<int, PhiMapValue*> PhiMap; | 499 typedef ZoneMap<int, PhiMapValue*> PhiMap; |
451 | 500 |
452 RegisterAllocationData(const RegisterConfiguration* config, | 501 RegisterAllocationData(const RegisterConfiguration* config, |
453 Zone* allocation_zone, Frame* frame, | 502 Zone* allocation_zone, Frame* frame, |
454 InstructionSequence* code, | 503 InstructionSequence* code, |
455 const char* debug_name = nullptr); | 504 const char* debug_name = nullptr); |
456 | 505 |
457 const ZoneVector<LiveRange*>& live_ranges() const { return live_ranges_; } | 506 const ZoneVector<LiveRange*>& live_ranges() const { return live_ranges_; } |
458 ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; } | 507 ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; } |
459 const ZoneVector<LiveRange*>& fixed_live_ranges() const { | 508 const ZoneVector<LiveRange*>& fixed_live_ranges() const { |
460 return fixed_live_ranges_; | 509 return fixed_live_ranges_; |
461 } | 510 } |
462 ZoneVector<LiveRange*>& fixed_live_ranges() { return fixed_live_ranges_; } | 511 ZoneVector<LiveRange*>& fixed_live_ranges() { return fixed_live_ranges_; } |
463 ZoneVector<LiveRange*>& fixed_double_live_ranges() { | 512 ZoneVector<LiveRange*>& fixed_double_live_ranges() { |
464 return fixed_double_live_ranges_; | 513 return fixed_double_live_ranges_; |
465 } | 514 } |
466 const ZoneVector<LiveRange*>& fixed_double_live_ranges() const { | 515 const ZoneVector<LiveRange*>& fixed_double_live_ranges() const { |
467 return fixed_double_live_ranges_; | 516 return fixed_double_live_ranges_; |
468 } | 517 } |
469 ZoneVector<BitVector*>& live_in_sets() { return live_in_sets_; } | 518 ZoneVector<BitVector*>& live_in_sets() { return live_in_sets_; } |
470 ZoneVector<SpillRange*>& spill_ranges() { return spill_ranges_; } | 519 ZoneVector<SpillRange*>& spill_ranges() { return spill_ranges_; } |
471 InstructionSequence* code() const { return code_; } | 520 InstructionSequence* code() const { return code_; } |
472 // This zone is for datastructures only needed during register allocation | 521 // This zone is for datastructures only needed during register allocation |
473 // phases. | 522 // phases. |
474 Zone* allocation_zone() const { return allocation_zone_; } | 523 Zone* allocation_zone() const { return allocation_zone_; } |
475 // This zone is for InstructionOperands and moves that live beyond register | 524 // This zone is for InstructionOperands and moves that live beyond register |
476 // allocation. | 525 // allocation. |
477 Zone* code_zone() const { return code()->zone(); } | 526 Zone* code_zone() const { return code()->zone(); } |
478 const PhiMap& phi_map() const { return phi_map_; } | |
479 PhiMap& phi_map() { return phi_map_; } | |
480 Frame* frame() const { return frame_; } | 527 Frame* frame() const { return frame_; } |
481 const char* debug_name() const { return debug_name_; } | 528 const char* debug_name() const { return debug_name_; } |
482 const RegisterConfiguration* config() const { return config_; } | 529 const RegisterConfiguration* config() const { return config_; } |
483 | 530 |
484 void SetLiveRangeAssignedRegister(LiveRange* range, int reg); | |
485 LiveRange* LiveRangeFor(int index); | 531 LiveRange* LiveRangeFor(int index); |
486 | 532 |
487 void AssignPhiInput(LiveRange* range, const InstructionOperand& assignment); | |
488 SpillRange* AssignSpillRangeToLiveRange(LiveRange* range); | 533 SpillRange* AssignSpillRangeToLiveRange(LiveRange* range); |
489 | 534 |
490 MoveOperands* AddGapMove(int index, Instruction::GapPosition position, | 535 MoveOperands* AddGapMove(int index, Instruction::GapPosition position, |
491 const InstructionOperand& from, | 536 const InstructionOperand& from, |
492 const InstructionOperand& to); | 537 const InstructionOperand& to); |
493 | 538 |
494 bool IsReference(int virtual_register) const { | 539 bool IsReference(int virtual_register) const { |
495 return code()->IsReference(virtual_register); | 540 return code()->IsReference(virtual_register); |
496 } | 541 } |
497 | 542 |
498 bool ExistsUseWithoutDefinition(); | 543 bool ExistsUseWithoutDefinition(); |
499 | 544 |
500 // Creates a new live range. | 545 // Creates a new live range. |
501 LiveRange* NewLiveRange(int index); | 546 LiveRange* NewLiveRange(int index); |
502 | 547 |
| 548 void MarkAllocated(RegisterKind kind, int index); |
| 549 |
| 550 PhiMapValue* InitializePhiMap(const InstructionBlock* block, |
| 551 PhiInstruction* phi); |
| 552 PhiMapValue* GetPhiMapValueFor(int virtual_register); |
| 553 |
503 private: | 554 private: |
504 Zone* const allocation_zone_; | 555 Zone* const allocation_zone_; |
505 Frame* const frame_; | 556 Frame* const frame_; |
506 InstructionSequence* const code_; | 557 InstructionSequence* const code_; |
507 const char* const debug_name_; | 558 const char* const debug_name_; |
508 const RegisterConfiguration* const config_; | 559 const RegisterConfiguration* const config_; |
509 PhiMap phi_map_; | 560 PhiMap phi_map_; |
510 ZoneVector<BitVector*> live_in_sets_; | 561 ZoneVector<BitVector*> live_in_sets_; |
511 ZoneVector<LiveRange*> live_ranges_; | 562 ZoneVector<LiveRange*> live_ranges_; |
512 ZoneVector<LiveRange*> fixed_live_ranges_; | 563 ZoneVector<LiveRange*> fixed_live_ranges_; |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
551 void ResolvePhis(const InstructionBlock* block); | 602 void ResolvePhis(const InstructionBlock* block); |
552 | 603 |
553 RegisterAllocationData* const data_; | 604 RegisterAllocationData* const data_; |
554 | 605 |
555 DISALLOW_COPY_AND_ASSIGN(ConstraintBuilder); | 606 DISALLOW_COPY_AND_ASSIGN(ConstraintBuilder); |
556 }; | 607 }; |
557 | 608 |
558 | 609 |
559 class LiveRangeBuilder final : public ZoneObject { | 610 class LiveRangeBuilder final : public ZoneObject { |
560 public: | 611 public: |
561 explicit LiveRangeBuilder(RegisterAllocationData* data); | 612 explicit LiveRangeBuilder(RegisterAllocationData* data, Zone* local_zone); |
562 | 613 |
563 // Phase 3: compute liveness of all virtual register. | 614 // Phase 3: compute liveness of all virtual register. |
564 void BuildLiveRanges(); | 615 void BuildLiveRanges(); |
565 | 616 |
566 private: | 617 private: |
567 RegisterAllocationData* data() const { return data_; } | 618 RegisterAllocationData* data() const { return data_; } |
568 InstructionSequence* code() const { return data()->code(); } | 619 InstructionSequence* code() const { return data()->code(); } |
569 Zone* allocation_zone() const { return data()->allocation_zone(); } | 620 Zone* allocation_zone() const { return data()->allocation_zone(); } |
570 Zone* code_zone() const { return code()->zone(); } | 621 Zone* code_zone() const { return code()->zone(); } |
571 const RegisterConfiguration* config() const { return data()->config(); } | 622 const RegisterConfiguration* config() const { return data()->config(); } |
572 ZoneVector<BitVector*>& live_in_sets() const { | 623 ZoneVector<BitVector*>& live_in_sets() const { |
573 return data()->live_in_sets(); | 624 return data()->live_in_sets(); |
574 } | 625 } |
575 | 626 |
576 LiveRange* LiveRangeFor(int index) { return data()->LiveRangeFor(index); } | 627 LiveRange* LiveRangeFor(int index) { return data()->LiveRangeFor(index); } |
577 | 628 |
578 void Verify() const; | 629 void Verify() const; |
579 | 630 |
580 // Liveness analysis support. | 631 // Liveness analysis support. |
581 BitVector* ComputeLiveOut(const InstructionBlock* block); | 632 BitVector* ComputeLiveOut(const InstructionBlock* block); |
582 void AddInitialIntervals(const InstructionBlock* block, BitVector* live_out); | 633 void AddInitialIntervals(const InstructionBlock* block, BitVector* live_out); |
583 bool IsOutputRegisterOf(Instruction* instr, int index); | |
584 bool IsOutputDoubleRegisterOf(Instruction* instr, int index); | |
585 void ProcessInstructions(const InstructionBlock* block, BitVector* live); | 634 void ProcessInstructions(const InstructionBlock* block, BitVector* live); |
| 635 void ProcessPhis(const InstructionBlock* block, BitVector* live); |
| 636 void ProcessLoopHeader(const InstructionBlock* block, BitVector* live); |
586 | 637 |
587 static int FixedLiveRangeID(int index) { return -index - 1; } | 638 static int FixedLiveRangeID(int index) { return -index - 1; } |
588 int FixedDoubleLiveRangeID(int index); | 639 int FixedDoubleLiveRangeID(int index); |
589 LiveRange* FixedLiveRangeFor(int index); | 640 LiveRange* FixedLiveRangeFor(int index); |
590 LiveRange* FixedDoubleLiveRangeFor(int index); | 641 LiveRange* FixedDoubleLiveRangeFor(int index); |
591 | 642 |
| 643 void MapPhiHint(InstructionOperand* operand, UsePosition* use_pos); |
| 644 void ResolvePhiHint(InstructionOperand* operand, UsePosition* use_pos); |
| 645 |
592 // Returns the register kind required by the given virtual register. | 646 // Returns the register kind required by the given virtual register. |
593 RegisterKind RequiredRegisterKind(int virtual_register) const; | 647 RegisterKind RequiredRegisterKind(int virtual_register) const; |
594 | 648 |
| 649 UsePosition* NewUsePosition(LifetimePosition pos, InstructionOperand* operand, |
| 650 void* hint, UsePositionHintType hint_type); |
| 651 UsePosition* NewUsePosition(LifetimePosition pos) { |
| 652 return NewUsePosition(pos, nullptr, nullptr, UsePositionHintType::kNone); |
| 653 } |
| 654 LiveRange* LiveRangeFor(InstructionOperand* operand); |
595 // Helper methods for building intervals. | 655 // Helper methods for building intervals. |
596 LiveRange* LiveRangeFor(InstructionOperand* operand); | 656 UsePosition* Define(LifetimePosition position, InstructionOperand* operand, |
597 void Define(LifetimePosition position, InstructionOperand* operand, | 657 void* hint, UsePositionHintType hint_type); |
598 InstructionOperand* hint); | 658 void Define(LifetimePosition position, InstructionOperand* operand) { |
| 659 Define(position, operand, nullptr, UsePositionHintType::kNone); |
| 660 } |
| 661 UsePosition* Use(LifetimePosition block_start, LifetimePosition position, |
| 662 InstructionOperand* operand, void* hint, |
| 663 UsePositionHintType hint_type); |
599 void Use(LifetimePosition block_start, LifetimePosition position, | 664 void Use(LifetimePosition block_start, LifetimePosition position, |
600 InstructionOperand* operand, InstructionOperand* hint); | 665 InstructionOperand* operand) { |
| 666 Use(block_start, position, operand, nullptr, UsePositionHintType::kNone); |
| 667 } |
601 | 668 |
602 RegisterAllocationData* const data_; | 669 RegisterAllocationData* const data_; |
| 670 ZoneMap<InstructionOperand*, UsePosition*> phi_hints_; |
603 | 671 |
604 DISALLOW_COPY_AND_ASSIGN(LiveRangeBuilder); | 672 DISALLOW_COPY_AND_ASSIGN(LiveRangeBuilder); |
605 }; | 673 }; |
606 | 674 |
607 | 675 |
608 class RegisterAllocator : public ZoneObject { | 676 class RegisterAllocator : public ZoneObject { |
609 public: | 677 public: |
610 explicit RegisterAllocator(RegisterAllocationData* data, RegisterKind kind); | 678 explicit RegisterAllocator(RegisterAllocationData* data, RegisterKind kind); |
611 | 679 |
612 protected: | 680 protected: |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
665 const char* RegisterName(int allocation_index) const; | 733 const char* RegisterName(int allocation_index) const; |
666 | 734 |
667 ZoneVector<LiveRange*>& unhandled_live_ranges() { | 735 ZoneVector<LiveRange*>& unhandled_live_ranges() { |
668 return unhandled_live_ranges_; | 736 return unhandled_live_ranges_; |
669 } | 737 } |
670 ZoneVector<LiveRange*>& active_live_ranges() { return active_live_ranges_; } | 738 ZoneVector<LiveRange*>& active_live_ranges() { return active_live_ranges_; } |
671 ZoneVector<LiveRange*>& inactive_live_ranges() { | 739 ZoneVector<LiveRange*>& inactive_live_ranges() { |
672 return inactive_live_ranges_; | 740 return inactive_live_ranges_; |
673 } | 741 } |
674 | 742 |
| 743 void SetLiveRangeAssignedRegister(LiveRange* range, int reg); |
| 744 |
675 // Helper methods for updating the life range lists. | 745 // Helper methods for updating the life range lists. |
676 void AddToActive(LiveRange* range); | 746 void AddToActive(LiveRange* range); |
677 void AddToInactive(LiveRange* range); | 747 void AddToInactive(LiveRange* range); |
678 void AddToUnhandledSorted(LiveRange* range); | 748 void AddToUnhandledSorted(LiveRange* range); |
679 void AddToUnhandledUnsorted(LiveRange* range); | 749 void AddToUnhandledUnsorted(LiveRange* range); |
680 void SortUnhandled(); | 750 void SortUnhandled(); |
681 bool UnhandledIsSorted(); | 751 bool UnhandledIsSorted(); |
682 void ActiveToHandled(LiveRange* range); | 752 void ActiveToHandled(LiveRange* range); |
683 void ActiveToInactive(LiveRange* range); | 753 void ActiveToInactive(LiveRange* range); |
684 void InactiveToHandled(LiveRange* range); | 754 void InactiveToHandled(LiveRange* range); |
(...skipping 131 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
816 RegisterAllocationData* const data_; | 886 RegisterAllocationData* const data_; |
817 | 887 |
818 DISALLOW_COPY_AND_ASSIGN(LiveRangeConnector); | 888 DISALLOW_COPY_AND_ASSIGN(LiveRangeConnector); |
819 }; | 889 }; |
820 | 890 |
821 } // namespace compiler | 891 } // namespace compiler |
822 } // namespace internal | 892 } // namespace internal |
823 } // namespace v8 | 893 } // namespace v8 |
824 | 894 |
825 #endif // V8_REGISTER_ALLOCATOR_H_ | 895 #endif // V8_REGISTER_ALLOCATOR_H_ |
OLD | NEW |