OLD | NEW |
1 // Copyright 2010 the V8 project authors. All rights reserved. | 1 // Copyright 2010 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 13 matching lines...) Expand all Loading... |
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | 27 |
28 #ifndef V8_LITHIUM_ALLOCATOR_H_ | 28 #ifndef V8_LITHIUM_ALLOCATOR_H_ |
29 #define V8_LITHIUM_ALLOCATOR_H_ | 29 #define V8_LITHIUM_ALLOCATOR_H_ |
30 | 30 |
31 #include "v8.h" | 31 #include "v8.h" |
32 | 32 |
33 #include "data-flow.h" | 33 #include "data-flow.h" |
| 34 #include "lithium.h" |
34 #include "zone.h" | 35 #include "zone.h" |
35 | 36 |
36 namespace v8 { | 37 namespace v8 { |
37 namespace internal { | 38 namespace internal { |
38 | 39 |
39 // Forward declarations. | 40 // Forward declarations. |
40 class HBasicBlock; | 41 class HBasicBlock; |
41 class HGraph; | 42 class HGraph; |
42 class HInstruction; | 43 class HInstruction; |
43 class HPhi; | 44 class HPhi; |
(...skipping 102 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
146 | 147 |
147 enum RegisterKind { | 148 enum RegisterKind { |
148 NONE, | 149 NONE, |
149 GENERAL_REGISTERS, | 150 GENERAL_REGISTERS, |
150 DOUBLE_REGISTERS | 151 DOUBLE_REGISTERS |
151 }; | 152 }; |
152 | 153 |
153 | 154 |
154 // A register-allocator view of a Lithium instruction. It contains the id of | 155 // A register-allocator view of a Lithium instruction. It contains the id of |
155 // the output operand and a list of input operand uses. | 156 // the output operand and a list of input operand uses. |
156 class InstructionSummary: public ZoneObject { | 157 |
| 158 class LInstruction; |
| 159 class LEnvironment; |
| 160 |
| 161 // Iterator for non-null temp operands. |
| 162 class TempIterator BASE_EMBEDDED { |
157 public: | 163 public: |
158 InstructionSummary() | 164 inline explicit TempIterator(LInstruction* instr); |
159 : output_operand_(NULL), | 165 inline bool HasNext(); |
160 input_count_(0), | 166 inline LOperand* Next(); |
161 operands_(4), | 167 inline void Advance(); |
162 is_call_(false), | |
163 is_save_doubles_(false) {} | |
164 | |
165 // Output operands. | |
166 LOperand* Output() const { return output_operand_; } | |
167 void SetOutput(LOperand* output) { | |
168 ASSERT(output_operand_ == NULL); | |
169 output_operand_ = output; | |
170 } | |
171 | |
172 // Input operands. | |
173 int InputCount() const { return input_count_; } | |
174 LOperand* InputAt(int i) const { | |
175 ASSERT(i < input_count_); | |
176 return operands_[i]; | |
177 } | |
178 void AddInput(LOperand* input) { | |
179 operands_.InsertAt(input_count_, input); | |
180 input_count_++; | |
181 } | |
182 | |
183 // Temporary operands. | |
184 int TempCount() const { return operands_.length() - input_count_; } | |
185 LOperand* TempAt(int i) const { return operands_[i + input_count_]; } | |
186 void AddTemp(LOperand* temp) { operands_.Add(temp); } | |
187 | |
188 void MarkAsCall() { is_call_ = true; } | |
189 bool IsCall() const { return is_call_; } | |
190 | |
191 void MarkAsSaveDoubles() { is_save_doubles_ = true; } | |
192 bool IsSaveDoubles() const { return is_save_doubles_; } | |
193 | 168 |
194 private: | 169 private: |
195 LOperand* output_operand_; | 170 inline int AdvanceToNext(int start); |
196 int input_count_; | 171 LInstruction* instr_; |
197 ZoneList<LOperand*> operands_; | 172 int limit_; |
198 bool is_call_; | 173 int current_; |
199 bool is_save_doubles_; | |
200 }; | 174 }; |
201 | 175 |
| 176 |
| 177 // Iterator for non-constant input operands. |
| 178 class InputIterator BASE_EMBEDDED { |
| 179 public: |
| 180 inline explicit InputIterator(LInstruction* instr); |
| 181 inline bool HasNext(); |
| 182 inline LOperand* Next(); |
| 183 inline void Advance(); |
| 184 |
| 185 private: |
| 186 inline int AdvanceToNext(int start); |
| 187 LInstruction* instr_; |
| 188 int limit_; |
| 189 int current_; |
| 190 }; |
| 191 |
| 192 |
| 193 class UseIterator BASE_EMBEDDED { |
| 194 public: |
| 195 inline explicit UseIterator(LInstruction* instr); |
| 196 inline bool HasNext(); |
| 197 inline LOperand* Next(); |
| 198 inline void Advance(); |
| 199 |
| 200 private: |
| 201 InputIterator input_iterator_; |
| 202 DeepIterator env_iterator_; |
| 203 }; |
| 204 |
| 205 |
202 // Representation of the non-empty interval [start,end[. | 206 // Representation of the non-empty interval [start,end[. |
203 class UseInterval: public ZoneObject { | 207 class UseInterval: public ZoneObject { |
204 public: | 208 public: |
205 UseInterval(LifetimePosition start, LifetimePosition end) | 209 UseInterval(LifetimePosition start, LifetimePosition end) |
206 : start_(start), end_(end), next_(NULL) { | 210 : start_(start), end_(end), next_(NULL) { |
207 ASSERT(start.Value() < end.Value()); | 211 ASSERT(start.Value() < end.Value()); |
208 } | 212 } |
209 | 213 |
210 LifetimePosition start() const { return start_; } | 214 LifetimePosition start() const { return start_; } |
211 LifetimePosition end() const { return end_; } | 215 LifetimePosition end() const { return end_; } |
(...skipping 209 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
421 } | 425 } |
422 | 426 |
423 BitVector* bits_; | 427 BitVector* bits_; |
424 }; | 428 }; |
425 | 429 |
426 | 430 |
427 class LAllocator BASE_EMBEDDED { | 431 class LAllocator BASE_EMBEDDED { |
428 public: | 432 public: |
429 explicit LAllocator(int first_virtual_register, HGraph* graph) | 433 explicit LAllocator(int first_virtual_register, HGraph* graph) |
430 : chunk_(NULL), | 434 : chunk_(NULL), |
431 summaries_(0), | |
432 next_summary_(NULL), | |
433 summary_stack_(2), | |
434 live_in_sets_(0), | 435 live_in_sets_(0), |
435 live_ranges_(16), | 436 live_ranges_(16), |
436 fixed_live_ranges_(8), | 437 fixed_live_ranges_(8), |
437 fixed_double_live_ranges_(8), | 438 fixed_double_live_ranges_(8), |
438 unhandled_live_ranges_(8), | 439 unhandled_live_ranges_(8), |
439 active_live_ranges_(8), | 440 active_live_ranges_(8), |
440 inactive_live_ranges_(8), | 441 inactive_live_ranges_(8), |
441 reusable_slots_(8), | 442 reusable_slots_(8), |
442 next_virtual_register_(first_virtual_register), | 443 next_virtual_register_(first_virtual_register), |
443 first_artificial_register_(first_virtual_register), | 444 first_artificial_register_(first_virtual_register), |
444 mode_(NONE), | 445 mode_(NONE), |
445 num_registers_(-1), | 446 num_registers_(-1), |
446 graph_(graph), | 447 graph_(graph), |
447 has_osr_entry_(false) {} | 448 has_osr_entry_(false) {} |
448 | 449 |
449 static void Setup(); | 450 static void Setup(); |
450 static void TraceAlloc(const char* msg, ...); | 451 static void TraceAlloc(const char* msg, ...); |
451 | 452 |
452 // Lithium translation support. | 453 // Lithium translation support. |
453 // Record a use of an input operand in the current instruction. | 454 // Record a use of an input operand in the current instruction. |
454 void RecordUse(HValue* value, LUnallocated* operand); | 455 void RecordUse(HValue* value, LUnallocated* operand); |
455 // Record the definition of the output operand. | 456 // Record the definition of the output operand. |
456 void RecordDefinition(HInstruction* instr, LUnallocated* operand); | 457 void RecordDefinition(HInstruction* instr, LUnallocated* operand); |
457 // Record a temporary operand. | 458 // Record a temporary operand. |
458 void RecordTemporary(LUnallocated* operand); | 459 void RecordTemporary(LUnallocated* operand); |
459 | 460 |
460 // Marks the current instruction as a call. | |
461 void MarkAsCall(); | |
462 | |
463 // Marks the current instruction as requiring saving double registers. | |
464 void MarkAsSaveDoubles(); | |
465 | |
466 // Checks whether the value of a given virtual register is tagged. | 461 // Checks whether the value of a given virtual register is tagged. |
467 bool HasTaggedValue(int virtual_register) const; | 462 bool HasTaggedValue(int virtual_register) const; |
468 | 463 |
469 // Returns the register kind required by the given virtual register. | 464 // Returns the register kind required by the given virtual register. |
470 RegisterKind RequiredRegisterKind(int virtual_register) const; | 465 RegisterKind RequiredRegisterKind(int virtual_register) const; |
471 | 466 |
472 // Begin a new instruction. | |
473 void BeginInstruction(); | |
474 | |
475 // Summarize the current instruction. | |
476 void SummarizeInstruction(int index); | |
477 | |
478 // Summarize the current instruction. | |
479 void OmitInstruction(); | |
480 | |
481 // Control max function size. | 467 // Control max function size. |
482 static int max_initial_value_ids(); | 468 static int max_initial_value_ids(); |
483 | 469 |
484 void Allocate(LChunk* chunk); | 470 void Allocate(LChunk* chunk); |
485 | 471 |
486 const ZoneList<LiveRange*>* live_ranges() const { return &live_ranges_; } | 472 const ZoneList<LiveRange*>* live_ranges() const { return &live_ranges_; } |
487 const ZoneList<LiveRange*>* fixed_live_ranges() const { | 473 const ZoneList<LiveRange*>* fixed_live_ranges() const { |
488 return &fixed_live_ranges_; | 474 return &fixed_live_ranges_; |
489 } | 475 } |
490 const ZoneList<LiveRange*>* fixed_double_live_ranges() const { | 476 const ZoneList<LiveRange*>* fixed_double_live_ranges() const { |
(...skipping 27 matching lines...) Expand all Loading... |
518 void AllocateRegisters(); | 504 void AllocateRegisters(); |
519 bool CanEagerlyResolveControlFlow(HBasicBlock* block) const; | 505 bool CanEagerlyResolveControlFlow(HBasicBlock* block) const; |
520 inline bool SafePointsAreInOrder() const; | 506 inline bool SafePointsAreInOrder() const; |
521 | 507 |
522 // Liveness analysis support. | 508 // Liveness analysis support. |
523 void InitializeLivenessAnalysis(); | 509 void InitializeLivenessAnalysis(); |
524 BitVector* ComputeLiveOut(HBasicBlock* block); | 510 BitVector* ComputeLiveOut(HBasicBlock* block); |
525 void AddInitialIntervals(HBasicBlock* block, BitVector* live_out); | 511 void AddInitialIntervals(HBasicBlock* block, BitVector* live_out); |
526 void ProcessInstructions(HBasicBlock* block, BitVector* live); | 512 void ProcessInstructions(HBasicBlock* block, BitVector* live); |
527 void MeetRegisterConstraints(HBasicBlock* block); | 513 void MeetRegisterConstraints(HBasicBlock* block); |
528 void MeetConstraintsBetween(InstructionSummary* first, | 514 void MeetConstraintsBetween(LInstruction* first, |
529 InstructionSummary* second, | 515 LInstruction* second, |
530 int gap_index); | 516 int gap_index); |
531 void ResolvePhis(HBasicBlock* block); | 517 void ResolvePhis(HBasicBlock* block); |
532 | 518 |
533 // Helper methods for building intervals. | 519 // Helper methods for building intervals. |
534 LOperand* AllocateFixed(LUnallocated* operand, int pos, bool is_tagged); | 520 LOperand* AllocateFixed(LUnallocated* operand, int pos, bool is_tagged); |
535 LiveRange* LiveRangeFor(LOperand* operand); | 521 LiveRange* LiveRangeFor(LOperand* operand); |
536 void Define(LifetimePosition position, LOperand* operand, LOperand* hint); | 522 void Define(LifetimePosition position, LOperand* operand, LOperand* hint); |
537 void Use(LifetimePosition block_start, | 523 void Use(LifetimePosition block_start, |
538 LifetimePosition position, | 524 LifetimePosition position, |
539 LOperand* operand, | 525 LOperand* operand, |
(...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
597 HBasicBlock* block, | 583 HBasicBlock* block, |
598 HBasicBlock* pred); | 584 HBasicBlock* pred); |
599 | 585 |
600 // Return parallel move that should be used to connect ranges split at the | 586 // Return parallel move that should be used to connect ranges split at the |
601 // given position. | 587 // given position. |
602 LParallelMove* GetConnectingParallelMove(LifetimePosition pos); | 588 LParallelMove* GetConnectingParallelMove(LifetimePosition pos); |
603 | 589 |
604 // Return the block which contains give lifetime position. | 590 // Return the block which contains give lifetime position. |
605 HBasicBlock* GetBlock(LifetimePosition pos); | 591 HBasicBlock* GetBlock(LifetimePosition pos); |
606 | 592 |
607 // Current active summary. | |
608 InstructionSummary* current_summary() const { return summary_stack_.last(); } | |
609 | |
610 // Get summary for given instruction index. | |
611 InstructionSummary* GetSummary(int index) const { return summaries_[index]; } | |
612 | |
613 // Helper methods for the fixed registers. | 593 // Helper methods for the fixed registers. |
614 int RegisterCount() const; | 594 int RegisterCount() const; |
615 static int FixedLiveRangeID(int index) { return -index - 1; } | 595 static int FixedLiveRangeID(int index) { return -index - 1; } |
616 static int FixedDoubleLiveRangeID(int index); | 596 static int FixedDoubleLiveRangeID(int index); |
617 LiveRange* FixedLiveRangeFor(int index); | 597 LiveRange* FixedLiveRangeFor(int index); |
618 LiveRange* FixedDoubleLiveRangeFor(int index); | 598 LiveRange* FixedDoubleLiveRangeFor(int index); |
619 LiveRange* LiveRangeFor(int index); | 599 LiveRange* LiveRangeFor(int index); |
620 HPhi* LookupPhi(LOperand* operand) const; | 600 HPhi* LookupPhi(LOperand* operand) const; |
621 LGap* GetLastGap(HBasicBlock* block) const; | 601 LGap* GetLastGap(HBasicBlock* block); |
622 | 602 |
623 const char* RegisterName(int allocation_index); | 603 const char* RegisterName(int allocation_index); |
624 | 604 |
| 605 inline bool IsGapAt(int index); |
| 606 |
| 607 inline LInstruction* InstructionAt(int index); |
| 608 |
| 609 inline LGap* GapAt(int index); |
| 610 |
625 LChunk* chunk_; | 611 LChunk* chunk_; |
626 ZoneList<InstructionSummary*> summaries_; | |
627 InstructionSummary* next_summary_; | |
628 | |
629 ZoneList<InstructionSummary*> summary_stack_; | |
630 | 612 |
631 // During liveness analysis keep a mapping from block id to live_in sets | 613 // During liveness analysis keep a mapping from block id to live_in sets |
632 // for blocks already analyzed. | 614 // for blocks already analyzed. |
633 ZoneList<BitVector*> live_in_sets_; | 615 ZoneList<BitVector*> live_in_sets_; |
634 | 616 |
635 // Liveness analysis results. | 617 // Liveness analysis results. |
636 ZoneList<LiveRange*> live_ranges_; | 618 ZoneList<LiveRange*> live_ranges_; |
637 | 619 |
638 // Lists of live ranges | 620 // Lists of live ranges |
639 ZoneList<LiveRange*> fixed_live_ranges_; | 621 ZoneList<LiveRange*> fixed_live_ranges_; |
(...skipping 15 matching lines...) Expand all Loading... |
655 | 637 |
656 bool has_osr_entry_; | 638 bool has_osr_entry_; |
657 | 639 |
658 DISALLOW_COPY_AND_ASSIGN(LAllocator); | 640 DISALLOW_COPY_AND_ASSIGN(LAllocator); |
659 }; | 641 }; |
660 | 642 |
661 | 643 |
662 } } // namespace v8::internal | 644 } } // namespace v8::internal |
663 | 645 |
664 #endif // V8_LITHIUM_ALLOCATOR_H_ | 646 #endif // V8_LITHIUM_ALLOCATOR_H_ |
OLD | NEW |