OLD | NEW |
1 // Copyright 2012 the V8 project authors. All rights reserved. | 1 // Copyright 2012 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_LITHIUM_ALLOCATOR_H_ | 5 #ifndef V8_LITHIUM_ALLOCATOR_H_ |
6 #define V8_LITHIUM_ALLOCATOR_H_ | 6 #define V8_LITHIUM_ALLOCATOR_H_ |
7 | 7 |
8 #include "src/v8.h" | 8 #include "src/v8.h" |
9 | 9 |
10 #include "src/allocation.h" | 10 #include "src/allocation.h" |
(...skipping 135 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
146 } | 146 } |
147 | 147 |
148 private: | 148 private: |
149 void set_start(LifetimePosition start) { start_ = start; } | 149 void set_start(LifetimePosition start) { start_ = start; } |
150 void set_next(UseInterval* next) { next_ = next; } | 150 void set_next(UseInterval* next) { next_ = next; } |
151 | 151 |
152 LifetimePosition start_; | 152 LifetimePosition start_; |
153 LifetimePosition end_; | 153 LifetimePosition end_; |
154 UseInterval* next_; | 154 UseInterval* next_; |
155 | 155 |
156 friend class LAllocator; // Assigns to next_. | |
157 friend class SpillRange; // Assigns to next_. | |
158 friend class LiveRange; // Assigns to start_. | 156 friend class LiveRange; // Assigns to start_. |
159 }; | 157 }; |
160 | 158 |
161 // Representation of a use position. | 159 // Representation of a use position. |
162 class UsePosition: public ZoneObject { | 160 class UsePosition: public ZoneObject { |
163 public: | 161 public: |
164 UsePosition(LifetimePosition pos, LOperand* operand, LOperand* hint); | 162 UsePosition(LifetimePosition pos, LOperand* operand, LOperand* hint); |
165 | 163 |
166 LOperand* operand() const { return operand_; } | 164 LOperand* operand() const { return operand_; } |
167 bool HasOperand() const { return operand_ != NULL; } | 165 bool HasOperand() const { return operand_ != NULL; } |
(...skipping 12 matching lines...) Expand all Loading... |
180 LOperand* const operand_; | 178 LOperand* const operand_; |
181 LOperand* const hint_; | 179 LOperand* const hint_; |
182 LifetimePosition const pos_; | 180 LifetimePosition const pos_; |
183 UsePosition* next_; | 181 UsePosition* next_; |
184 bool requires_reg_; | 182 bool requires_reg_; |
185 bool register_beneficial_; | 183 bool register_beneficial_; |
186 | 184 |
187 friend class LiveRange; | 185 friend class LiveRange; |
188 }; | 186 }; |
189 | 187 |
190 class SpillRange; | |
191 | |
192 // Representation of SSA values' live ranges as a collection of (continuous) | 188 // Representation of SSA values' live ranges as a collection of (continuous) |
193 // intervals over the instruction ordering. | 189 // intervals over the instruction ordering. |
194 class LiveRange: public ZoneObject { | 190 class LiveRange: public ZoneObject { |
195 public: | 191 public: |
196 static const int kInvalidAssignment = 0x7fffffff; | 192 static const int kInvalidAssignment = 0x7fffffff; |
197 | 193 |
198 LiveRange(int id, Zone* zone); | 194 LiveRange(int id, Zone* zone); |
199 | 195 |
200 UseInterval* first_interval() const { return first_interval_; } | 196 UseInterval* first_interval() const { return first_interval_; } |
201 UsePosition* first_pos() const { return first_pos_; } | 197 UsePosition* first_pos() const { return first_pos_; } |
(...skipping 62 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
264 | 260 |
265 LifetimePosition End() const { | 261 LifetimePosition End() const { |
266 DCHECK(!IsEmpty()); | 262 DCHECK(!IsEmpty()); |
267 return last_interval_->end(); | 263 return last_interval_->end(); |
268 } | 264 } |
269 | 265 |
270 bool HasAllocatedSpillOperand() const; | 266 bool HasAllocatedSpillOperand() const; |
271 LOperand* GetSpillOperand() const { return spill_operand_; } | 267 LOperand* GetSpillOperand() const { return spill_operand_; } |
272 void SetSpillOperand(LOperand* operand); | 268 void SetSpillOperand(LOperand* operand); |
273 | 269 |
274 void SetSpillRange(SpillRange* spill_range) { spill_range_ = spill_range; } | |
275 SpillRange* GetSpillRange() const { return spill_range_; } | |
276 void CommitSpillOperand(LOperand* operand); | |
277 | |
278 void SetSpillStartIndex(int start) { | 270 void SetSpillStartIndex(int start) { |
279 spill_start_index_ = Min(start, spill_start_index_); | 271 spill_start_index_ = Min(start, spill_start_index_); |
280 } | 272 } |
281 | 273 |
282 bool ShouldBeAllocatedBefore(const LiveRange* other) const; | 274 bool ShouldBeAllocatedBefore(const LiveRange* other) const; |
283 bool CanCover(LifetimePosition position) const; | 275 bool CanCover(LifetimePosition position) const; |
284 bool Covers(LifetimePosition position); | 276 bool Covers(LifetimePosition position); |
285 LifetimePosition FirstIntersection(LiveRange* other); | 277 LifetimePosition FirstIntersection(LiveRange* other); |
286 | 278 |
287 // Add a new interval or a new use position to this live range. | 279 // Add a new interval or a new use position to this live range. |
(...skipping 12 matching lines...) Expand all Loading... |
300 void ShortenTo(LifetimePosition start); | 292 void ShortenTo(LifetimePosition start); |
301 | 293 |
302 #ifdef DEBUG | 294 #ifdef DEBUG |
303 // True if target overlaps an existing interval. | 295 // True if target overlaps an existing interval. |
304 bool HasOverlap(UseInterval* target) const; | 296 bool HasOverlap(UseInterval* target) const; |
305 void Verify() const; | 297 void Verify() const; |
306 #endif | 298 #endif |
307 | 299 |
308 private: | 300 private: |
309 void ConvertOperands(Zone* zone); | 301 void ConvertOperands(Zone* zone); |
310 void ConvertUsesToOperand(LOperand* op); | |
311 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; | 302 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; |
312 void AdvanceLastProcessedMarker(UseInterval* to_start_of, | 303 void AdvanceLastProcessedMarker(UseInterval* to_start_of, |
313 LifetimePosition but_not_past) const; | 304 LifetimePosition but_not_past) const; |
314 | 305 |
315 int id_; | 306 int id_; |
316 bool spilled_; | 307 bool spilled_; |
317 RegisterKind kind_; | 308 RegisterKind kind_; |
318 int assigned_register_; | 309 int assigned_register_; |
319 UseInterval* last_interval_; | 310 UseInterval* last_interval_; |
320 UseInterval* first_interval_; | 311 UseInterval* first_interval_; |
321 UsePosition* first_pos_; | 312 UsePosition* first_pos_; |
322 LiveRange* parent_; | 313 LiveRange* parent_; |
323 LiveRange* next_; | 314 LiveRange* next_; |
324 // This is used as a cache, it doesn't affect correctness. | 315 // This is used as a cache, it doesn't affect correctness. |
325 mutable UseInterval* current_interval_; | 316 mutable UseInterval* current_interval_; |
326 UsePosition* last_processed_use_; | 317 UsePosition* last_processed_use_; |
327 // This is used as a cache, it's invalid outside of BuildLiveRanges. | 318 // This is used as a cache, it's invalid outside of BuildLiveRanges. |
328 LOperand* current_hint_operand_; | 319 LOperand* current_hint_operand_; |
329 LOperand* spill_operand_; | 320 LOperand* spill_operand_; |
330 int spill_start_index_; | 321 int spill_start_index_; |
331 SpillRange* spill_range_; | |
332 | 322 |
333 friend class LAllocator; // Assigns to kind_. | 323 friend class LAllocator; // Assigns to kind_. |
334 }; | 324 }; |
335 | 325 |
336 | 326 |
337 class SpillRange : public ZoneObject { | |
338 public: | |
339 SpillRange(LiveRange* range, int id, Zone* zone); | |
340 | |
341 bool TryMerge(SpillRange* other, Zone* zone); | |
342 void SetOperand(LOperand* op); | |
343 bool IsEmpty() { return live_ranges_.length() == 0; } | |
344 int id() const { return id_; } | |
345 UseInterval* interval() { return use_interval_; } | |
346 RegisterKind Kind() const { return live_ranges_.at(0)->Kind(); } | |
347 LifetimePosition End() const { return end_position_; } | |
348 bool IsIntersectingWith(SpillRange* other); | |
349 | |
350 private: | |
351 int id_; | |
352 ZoneList<LiveRange*> live_ranges_; | |
353 UseInterval* use_interval_; | |
354 LifetimePosition end_position_; | |
355 | |
356 // Merge intervals, making sure the use intervals are sorted | |
357 void MergeDisjointIntervals(UseInterval* other, Zone* zone); | |
358 }; | |
359 | |
360 | |
361 class LAllocator BASE_EMBEDDED { | 327 class LAllocator BASE_EMBEDDED { |
362 public: | 328 public: |
363 LAllocator(int first_virtual_register, HGraph* graph); | 329 LAllocator(int first_virtual_register, HGraph* graph); |
364 | 330 |
365 static void TraceAlloc(const char* msg, ...); | 331 static void TraceAlloc(const char* msg, ...); |
366 | 332 |
367 // Checks whether the value of a given virtual register is tagged. | 333 // Checks whether the value of a given virtual register is tagged. |
368 bool HasTaggedValue(int virtual_register) const; | 334 bool HasTaggedValue(int virtual_register) const; |
369 | 335 |
370 // Returns the register kind required by the given virtual register. | 336 // Returns the register kind required by the given virtual register. |
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
417 private: | 383 private: |
418 void MeetRegisterConstraints(); | 384 void MeetRegisterConstraints(); |
419 void ResolvePhis(); | 385 void ResolvePhis(); |
420 void BuildLiveRanges(); | 386 void BuildLiveRanges(); |
421 void AllocateGeneralRegisters(); | 387 void AllocateGeneralRegisters(); |
422 void AllocateDoubleRegisters(); | 388 void AllocateDoubleRegisters(); |
423 void ConnectRanges(); | 389 void ConnectRanges(); |
424 void ResolveControlFlow(); | 390 void ResolveControlFlow(); |
425 void PopulatePointerMaps(); | 391 void PopulatePointerMaps(); |
426 void AllocateRegisters(); | 392 void AllocateRegisters(); |
427 void ReuseSpillSlots(); | |
428 bool CanEagerlyResolveControlFlow(HBasicBlock* block) const; | 393 bool CanEagerlyResolveControlFlow(HBasicBlock* block) const; |
429 inline bool SafePointsAreInOrder() const; | 394 inline bool SafePointsAreInOrder() const; |
430 | 395 |
431 // Liveness analysis support. | 396 // Liveness analysis support. |
432 void InitializeLivenessAnalysis(); | 397 void InitializeLivenessAnalysis(); |
433 BitVector* ComputeLiveOut(HBasicBlock* block); | 398 BitVector* ComputeLiveOut(HBasicBlock* block); |
434 void AddInitialIntervals(HBasicBlock* block, BitVector* live_out); | 399 void AddInitialIntervals(HBasicBlock* block, BitVector* live_out); |
435 void ProcessInstructions(HBasicBlock* block, BitVector* live); | 400 void ProcessInstructions(HBasicBlock* block, BitVector* live); |
436 void MeetRegisterConstraints(HBasicBlock* block); | 401 void MeetRegisterConstraints(HBasicBlock* block); |
437 void MeetConstraintsBetween(LInstruction* first, | 402 void MeetConstraintsBetween(LInstruction* first, |
(...skipping 15 matching lines...) Expand all Loading... |
453 void AddToActive(LiveRange* range); | 418 void AddToActive(LiveRange* range); |
454 void AddToInactive(LiveRange* range); | 419 void AddToInactive(LiveRange* range); |
455 void AddToUnhandledSorted(LiveRange* range); | 420 void AddToUnhandledSorted(LiveRange* range); |
456 void AddToUnhandledUnsorted(LiveRange* range); | 421 void AddToUnhandledUnsorted(LiveRange* range); |
457 void SortUnhandled(); | 422 void SortUnhandled(); |
458 bool UnhandledIsSorted(); | 423 bool UnhandledIsSorted(); |
459 void ActiveToHandled(LiveRange* range); | 424 void ActiveToHandled(LiveRange* range); |
460 void ActiveToInactive(LiveRange* range); | 425 void ActiveToInactive(LiveRange* range); |
461 void InactiveToHandled(LiveRange* range); | 426 void InactiveToHandled(LiveRange* range); |
462 void InactiveToActive(LiveRange* range); | 427 void InactiveToActive(LiveRange* range); |
463 SpillRange* AssignSpillRangeToLiveRange(LiveRange* range); | 428 void FreeSpillSlot(LiveRange* range); |
| 429 LOperand* TryReuseSpillSlot(LiveRange* range); |
464 | 430 |
465 // Helper methods for allocating registers. | 431 // Helper methods for allocating registers. |
466 bool TryAllocateFreeReg(LiveRange* range); | 432 bool TryAllocateFreeReg(LiveRange* range); |
467 void AllocateBlockedReg(LiveRange* range); | 433 void AllocateBlockedReg(LiveRange* range); |
468 bool TryReuseSpillForPhi(LiveRange* range); | |
469 | 434 |
470 // Live range splitting helpers. | 435 // Live range splitting helpers. |
471 | 436 |
472 // Split the given range at the given position. | 437 // Split the given range at the given position. |
473 // If range starts at or after the given position then the | 438 // If range starts at or after the given position then the |
474 // original range is returned. | 439 // original range is returned. |
475 // Otherwise returns the live range that starts at pos and contains | 440 // Otherwise returns the live range that starts at pos and contains |
476 // all uses from the original range that follow pos. Uses at pos will | 441 // all uses from the original range that follow pos. Uses at pos will |
477 // still be owned by the original range after splitting. | 442 // still be owned by the original range after splitting. |
478 LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos); | 443 LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos); |
(...skipping 79 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
558 | 523 |
559 // Lists of live ranges | 524 // Lists of live ranges |
560 EmbeddedVector<LiveRange*, Register::kMaxNumAllocatableRegisters> | 525 EmbeddedVector<LiveRange*, Register::kMaxNumAllocatableRegisters> |
561 fixed_live_ranges_; | 526 fixed_live_ranges_; |
562 EmbeddedVector<LiveRange*, DoubleRegister::kMaxNumAllocatableRegisters> | 527 EmbeddedVector<LiveRange*, DoubleRegister::kMaxNumAllocatableRegisters> |
563 fixed_double_live_ranges_; | 528 fixed_double_live_ranges_; |
564 ZoneList<LiveRange*> unhandled_live_ranges_; | 529 ZoneList<LiveRange*> unhandled_live_ranges_; |
565 ZoneList<LiveRange*> active_live_ranges_; | 530 ZoneList<LiveRange*> active_live_ranges_; |
566 ZoneList<LiveRange*> inactive_live_ranges_; | 531 ZoneList<LiveRange*> inactive_live_ranges_; |
567 ZoneList<LiveRange*> reusable_slots_; | 532 ZoneList<LiveRange*> reusable_slots_; |
568 ZoneList<SpillRange*> spill_ranges_; | |
569 | 533 |
570 // Next virtual register number to be assigned to temporaries. | 534 // Next virtual register number to be assigned to temporaries. |
571 int next_virtual_register_; | 535 int next_virtual_register_; |
572 int first_artificial_register_; | 536 int first_artificial_register_; |
573 GrowableBitVector double_artificial_registers_; | 537 GrowableBitVector double_artificial_registers_; |
574 | 538 |
575 RegisterKind mode_; | 539 RegisterKind mode_; |
576 int num_registers_; | 540 int num_registers_; |
577 | 541 |
578 BitVector* assigned_registers_; | 542 BitVector* assigned_registers_; |
(...skipping 23 matching lines...) Expand all Loading... |
602 LAllocator* allocator_; | 566 LAllocator* allocator_; |
603 unsigned allocator_zone_start_allocation_size_; | 567 unsigned allocator_zone_start_allocation_size_; |
604 | 568 |
605 DISALLOW_COPY_AND_ASSIGN(LAllocatorPhase); | 569 DISALLOW_COPY_AND_ASSIGN(LAllocatorPhase); |
606 }; | 570 }; |
607 | 571 |
608 | 572 |
609 } } // namespace v8::internal | 573 } } // namespace v8::internal |
610 | 574 |
611 #endif // V8_LITHIUM_ALLOCATOR_H_ | 575 #endif // V8_LITHIUM_ALLOCATOR_H_ |
OLD | NEW |