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
3// found in the LICENSE file.
4
5#ifndef V8_LITHIUM_ALLOCATOR_H_
6#define V8_LITHIUM_ALLOCATOR_H_
7
8#include "src/v8.h"
9
10#include "src/allocation.h"
11#include "src/lithium.h"
12#include "src/zone.h"
13
14namespace v8 {
15namespace internal {
16
17// Forward declarations.
18class HBasicBlock;
19class HGraph;
20class HPhi;
21class HTracer;
22class HValue;
23class BitVector;
24class StringStream;
25
26class LPlatformChunk;
27class LOperand;
28class LUnallocated;
29class LGap;
30class LParallelMove;
31class LPointerMap;
32
33
34// This class represents a single point of a LOperand's lifetime.
35// For each lithium instruction there are exactly two lifetime positions:
36// the beginning and the end of the instruction. Lifetime positions for
37// different lithium instructions are disjoint.
38class LifetimePosition {
39 public:
40  // Return the lifetime position that corresponds to the beginning of
41  // the instruction with the given index.
42  static LifetimePosition FromInstructionIndex(int index) {
43    return LifetimePosition(index * kStep);
44  }
45
46  // Returns a numeric representation of this lifetime position.
47  int Value() const {
48    return value_;
49  }
50
51  // Returns the index of the instruction to which this lifetime position
52  // corresponds.
53  int InstructionIndex() const {
54    DCHECK(IsValid());
55    return value_ / kStep;
56  }
57
58  // Returns true if this lifetime position corresponds to the instruction
59  // start.
60  bool IsInstructionStart() const {
61    return (value_ & (kStep - 1)) == 0;
62  }
63
64  // Returns the lifetime position for the start of the instruction which
65  // corresponds to this lifetime position.
66  LifetimePosition InstructionStart() const {
67    DCHECK(IsValid());
68    return LifetimePosition(value_ & ~(kStep - 1));
69  }
70
71  // Returns the lifetime position for the end of the instruction which
72  // corresponds to this lifetime position.
73  LifetimePosition InstructionEnd() const {
74    DCHECK(IsValid());
75    return LifetimePosition(InstructionStart().Value() + kStep/2);
76  }
77
78  // Returns the lifetime position for the beginning of the next instruction.
79  LifetimePosition NextInstruction() const {
80    DCHECK(IsValid());
81    return LifetimePosition(InstructionStart().Value() + kStep);
82  }
83
84  // Returns the lifetime position for the beginning of the previous
85  // instruction.
86  LifetimePosition PrevInstruction() const {
87    DCHECK(IsValid());
88    DCHECK(value_ > 1);
89    return LifetimePosition(InstructionStart().Value() - kStep);
90  }
91
92  // Constructs the lifetime position which does not correspond to any
93  // instruction.
94  LifetimePosition() : value_(-1) {}
95
96  // Returns true if this lifetime positions corrensponds to some
97  // instruction.
98  bool IsValid() const { return value_ != -1; }
99
100  static inline LifetimePosition Invalid() { return LifetimePosition(); }
101
102  static inline LifetimePosition MaxPosition() {
103    // We have to use this kind of getter instead of static member due to
104    // crash bug in GDB.
105    return LifetimePosition(kMaxInt);
106  }
107
108 private:
109  static const int kStep = 2;
110
111  // Code relies on kStep being a power of two.
112  STATIC_ASSERT(IS_POWER_OF_TWO(kStep));
113
114  explicit LifetimePosition(int value) : value_(value) { }
115
116  int value_;
117};
118
119
120// Representation of the non-empty interval [start,end[.
121class UseInterval: public ZoneObject {
122 public:
123  UseInterval(LifetimePosition start, LifetimePosition end)
124      : start_(start), end_(end), next_(NULL) {
125    DCHECK(start.Value() < end.Value());
126  }
127
128  LifetimePosition start() const { return start_; }
129  LifetimePosition end() const { return end_; }
130  UseInterval* next() const { return next_; }
131
132  // Split this interval at the given position without effecting the
133  // live range that owns it. The interval must contain the position.
134  void SplitAt(LifetimePosition pos, Zone* zone);
135
136  // If this interval intersects with other return smallest position
137  // that belongs to both of them.
138  LifetimePosition Intersect(const UseInterval* other) const {
139    if (other->start().Value() < start_.Value()) return other->Intersect(this);
140    if (other->start().Value() < end_.Value()) return other->start();
141    return LifetimePosition::Invalid();
142  }
143
144  bool Contains(LifetimePosition point) const {
145    return start_.Value() <= point.Value() && point.Value() < end_.Value();
146  }
147
148 private:
149  void set_start(LifetimePosition start) { start_ = start; }
150  void set_next(UseInterval* next) { next_ = next; }
151
152  LifetimePosition start_;
153  LifetimePosition end_;
154  UseInterval* next_;
155
156  friend class LiveRange;  // Assigns to start_.
157};
158
159// Representation of a use position.
160class UsePosition: public ZoneObject {
161 public:
162  UsePosition(LifetimePosition pos, LOperand* operand, LOperand* hint);
163
164  LOperand* operand() const { return operand_; }
165  bool HasOperand() const { return operand_ != NULL; }
166
167  LOperand* hint() const { return hint_; }
168  bool HasHint() const;
169  bool RequiresRegister() const;
170  bool RegisterIsBeneficial() const;
171
172  LifetimePosition pos() const { return pos_; }
173  UsePosition* next() const { return next_; }
174
175 private:
176  void set_next(UsePosition* next) { next_ = next; }
177
178  LOperand* const operand_;
179  LOperand* const hint_;
180  LifetimePosition const pos_;
181  UsePosition* next_;
182  bool requires_reg_;
183  bool register_beneficial_;
184
185  friend class LiveRange;
186};
187
188// Representation of SSA values' live ranges as a collection of (continuous)
189// intervals over the instruction ordering.
190class LiveRange: public ZoneObject {
191 public:
192  static const int kInvalidAssignment = 0x7fffffff;
193
194  LiveRange(int id, Zone* zone);
195
196  UseInterval* first_interval() const { return first_interval_; }
197  UsePosition* first_pos() const { return first_pos_; }
198  LiveRange* parent() const { return parent_; }
199  LiveRange* TopLevel() { return (parent_ == NULL) ? this : parent_; }
200  LiveRange* next() const { return next_; }
201  bool IsChild() const { return parent() != NULL; }
202  int id() const { return id_; }
203  bool IsFixed() const { return id_ < 0; }
204  bool IsEmpty() const { return first_interval() == NULL; }
205  LOperand* CreateAssignedOperand(Zone* zone);
206  int assigned_register() const { return assigned_register_; }
207  int spill_start_index() const { return spill_start_index_; }
208  void set_assigned_register(int reg, Zone* zone);
209  void MakeSpilled(Zone* zone);
210
211  // Returns use position in this live range that follows both start
212  // and last processed use position.
213  // Modifies internal state of live range!
214  UsePosition* NextUsePosition(LifetimePosition start);
215
216  // Returns use position for which register is required in this live
217  // range and which follows both start and last processed use position
218  // Modifies internal state of live range!
219  UsePosition* NextRegisterPosition(LifetimePosition start);
220
221  // Returns use position for which register is beneficial in this live
222  // range and which follows both start and last processed use position
223  // Modifies internal state of live range!
224  UsePosition* NextUsePositionRegisterIsBeneficial(LifetimePosition start);
225
226  // Returns use position for which register is beneficial in this live
227  // range and which precedes start.
228  UsePosition* PreviousUsePositionRegisterIsBeneficial(LifetimePosition start);
229
230  // Can this live range be spilled at this position.
231  bool CanBeSpilled(LifetimePosition pos);
232
233  // Split this live range at the given position which must follow the start of
234  // the range.
235  // All uses following the given position will be moved from this
236  // live range to the result live range.
237  void SplitAt(LifetimePosition position, LiveRange* result, Zone* zone);
238
239  RegisterKind Kind() const { return kind_; }
240  bool HasRegisterAssigned() const {
241    return assigned_register_ != kInvalidAssignment;
242  }
243  bool IsSpilled() const { return spilled_; }
244
245  LOperand* current_hint_operand() const {
246    DCHECK(current_hint_operand_ == FirstHint());
247    return current_hint_operand_;
248  }
249  LOperand* FirstHint() const {
250    UsePosition* pos = first_pos_;
251    while (pos != NULL && !pos->HasHint()) pos = pos->next();
252    if (pos != NULL) return pos->hint();
253    return NULL;
254  }
255
256  LifetimePosition Start() const {
257    DCHECK(!IsEmpty());
258    return first_interval()->start();
259  }
260
261  LifetimePosition End() const {
262    DCHECK(!IsEmpty());
263    return last_interval_->end();
264  }
265
266  bool HasAllocatedSpillOperand() const;
267  LOperand* GetSpillOperand() const { return spill_operand_; }
268  void SetSpillOperand(LOperand* operand);
269
270  void SetSpillStartIndex(int start) {
271    spill_start_index_ = Min(start, spill_start_index_);
272  }
273
274  bool ShouldBeAllocatedBefore(const LiveRange* other) const;
275  bool CanCover(LifetimePosition position) const;
276  bool Covers(LifetimePosition position);
277  LifetimePosition FirstIntersection(LiveRange* other);
278
279  // Add a new interval or a new use position to this live range.
280  void EnsureInterval(LifetimePosition start,
281                      LifetimePosition end,
282                      Zone* zone);
283  void AddUseInterval(LifetimePosition start,
284                      LifetimePosition end,
285                      Zone* zone);
286  void AddUsePosition(LifetimePosition pos,
287                      LOperand* operand,
288                      LOperand* hint,
289                      Zone* zone);
290
291  // Shorten the most recently added interval by setting a new start.
292  void ShortenTo(LifetimePosition start);
293
294#ifdef DEBUG
295  // True if target overlaps an existing interval.
296  bool HasOverlap(UseInterval* target) const;
297  void Verify() const;
298#endif
299
300 private:
301  void ConvertOperands(Zone* zone);
302  UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const;
303  void AdvanceLastProcessedMarker(UseInterval* to_start_of,
304                                  LifetimePosition but_not_past) const;
305
306  int id_;
307  bool spilled_;
308  RegisterKind kind_;
309  int assigned_register_;
310  UseInterval* last_interval_;
311  UseInterval* first_interval_;
312  UsePosition* first_pos_;
313  LiveRange* parent_;
314  LiveRange* next_;
315  // This is used as a cache, it doesn't affect correctness.
316  mutable UseInterval* current_interval_;
317  UsePosition* last_processed_use_;
318  // This is used as a cache, it's invalid outside of BuildLiveRanges.
319  LOperand* current_hint_operand_;
320  LOperand* spill_operand_;
321  int spill_start_index_;
322
323  friend class LAllocator;  // Assigns to kind_.
324};
325
326
327class LAllocator BASE_EMBEDDED {
328 public:
329  LAllocator(int first_virtual_register, HGraph* graph);
330
331  static void TraceAlloc(const char* msg, ...);
332
333  // Checks whether the value of a given virtual register is tagged.
334  bool HasTaggedValue(int virtual_register) const;
335
336  // Returns the register kind required by the given virtual register.
337  RegisterKind RequiredRegisterKind(int virtual_register) const;
338
339  bool Allocate(LChunk* chunk);
340
341  const ZoneList<LiveRange*>* live_ranges() const { return &live_ranges_; }
342  const Vector<LiveRange*>* fixed_live_ranges() const {
343    return &fixed_live_ranges_;
344  }
345  const Vector<LiveRange*>* fixed_double_live_ranges() const {
346    return &fixed_double_live_ranges_;
347  }
348
349  LPlatformChunk* chunk() const { return chunk_; }
350  HGraph* graph() const { return graph_; }
351  Isolate* isolate() const { return graph_->isolate(); }
352  Zone* zone() { return &zone_; }
353
354  int GetVirtualRegister() {
355    if (next_virtual_register_ >= LUnallocated::kMaxVirtualRegisters) {
356      allocation_ok_ = false;
357      // Maintain the invariant that we return something below the maximum.
358      return 0;
359    }
360    return next_virtual_register_++;
361  }
362
363  bool AllocationOk() { return allocation_ok_; }
364
365  void MarkAsOsrEntry() {
366    // There can be only one.
367    DCHECK(!has_osr_entry_);
368    // Simply set a flag to find and process instruction later.
369    has_osr_entry_ = true;
370  }
371
372#ifdef DEBUG
373  void Verify() const;
374#endif
375
376  BitVector* assigned_registers() {
377    return assigned_registers_;
378  }
379  BitVector* assigned_double_registers() {
380    return assigned_double_registers_;
381  }
382
383 private:
384  void MeetRegisterConstraints();
385  void ResolvePhis();
386  void BuildLiveRanges();
387  void AllocateGeneralRegisters();
388  void AllocateDoubleRegisters();
389  void ConnectRanges();
390  void ResolveControlFlow();
391  void PopulatePointerMaps();
392  void AllocateRegisters();
393  bool CanEagerlyResolveControlFlow(HBasicBlock* block) const;
394  inline bool SafePointsAreInOrder() const;
395
396  // Liveness analysis support.
397  void InitializeLivenessAnalysis();
398  BitVector* ComputeLiveOut(HBasicBlock* block);
399  void AddInitialIntervals(HBasicBlock* block, BitVector* live_out);
400  void ProcessInstructions(HBasicBlock* block, BitVector* live);
401  void MeetRegisterConstraints(HBasicBlock* block);
402  void MeetConstraintsBetween(LInstruction* first,
403                              LInstruction* second,
404                              int gap_index);
405  void ResolvePhis(HBasicBlock* block);
406
407  // Helper methods for building intervals.
408  LOperand* AllocateFixed(LUnallocated* operand, int pos, bool is_tagged);
409  LiveRange* LiveRangeFor(LOperand* operand);
410  void Define(LifetimePosition position, LOperand* operand, LOperand* hint);
411  void Use(LifetimePosition block_start,
412           LifetimePosition position,
413           LOperand* operand,
414           LOperand* hint);
415  void AddConstraintsGapMove(int index, LOperand* from, LOperand* to);
416
417  // Helper methods for updating the life range lists.
418  void AddToActive(LiveRange* range);
419  void AddToInactive(LiveRange* range);
420  void AddToUnhandledSorted(LiveRange* range);
421  void AddToUnhandledUnsorted(LiveRange* range);
422  void SortUnhandled();
423  bool UnhandledIsSorted();
424  void ActiveToHandled(LiveRange* range);
425  void ActiveToInactive(LiveRange* range);
426  void InactiveToHandled(LiveRange* range);
427  void InactiveToActive(LiveRange* range);
428  void FreeSpillSlot(LiveRange* range);
429  LOperand* TryReuseSpillSlot(LiveRange* range);
430
431  // Helper methods for allocating registers.
432  bool TryAllocateFreeReg(LiveRange* range);
433  void AllocateBlockedReg(LiveRange* range);
434
435  // Live range splitting helpers.
436
437  // Split the given range at the given position.
438  // If range starts at or after the given position then the
439  // original range is returned.
440  // Otherwise returns the live range that starts at pos and contains
441  // all uses from the original range that follow pos. Uses at pos will
442  // still be owned by the original range after splitting.
443  LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos);
444
445  // Split the given range in a position from the interval [start, end].
446  LiveRange* SplitBetween(LiveRange* range,
447                          LifetimePosition start,
448                          LifetimePosition end);
449
450  // Find a lifetime position in the interval [start, end] which
451  // is optimal for splitting: it is either header of the outermost
452  // loop covered by this interval or the latest possible position.
453  LifetimePosition FindOptimalSplitPos(LifetimePosition start,
454                                       LifetimePosition end);
455
456  // Spill the given life range after position pos.
457  void SpillAfter(LiveRange* range, LifetimePosition pos);
458
459  // Spill the given life range after position [start] and up to position [end].
460  void SpillBetween(LiveRange* range,
461                    LifetimePosition start,
462                    LifetimePosition end);
463
464  // Spill the given life range after position [start] and up to position [end].
465  // Range is guaranteed to be spilled at least until position [until].
466  void SpillBetweenUntil(LiveRange* range,
467                         LifetimePosition start,
468                         LifetimePosition until,
469                         LifetimePosition end);
470
471  void SplitAndSpillIntersecting(LiveRange* range);
472
473  // If we are trying to spill a range inside the loop try to
474  // hoist spill position out to the point just before the loop.
475  LifetimePosition FindOptimalSpillingPos(LiveRange* range,
476                                          LifetimePosition pos);
477
478  void Spill(LiveRange* range);
479  bool IsBlockBoundary(LifetimePosition pos);
480
481  // Helper methods for resolving control flow.
482  void ResolveControlFlow(LiveRange* range,
483                          HBasicBlock* block,
484                          HBasicBlock* pred);
485
486  inline void SetLiveRangeAssignedRegister(LiveRange* range, int reg);
487
488  // Return parallel move that should be used to connect ranges split at the
489  // given position.
490  LParallelMove* GetConnectingParallelMove(LifetimePosition pos);
491
492  // Return the block which contains give lifetime position.
493  HBasicBlock* GetBlock(LifetimePosition pos);
494
495  // Helper methods for the fixed registers.
496  int RegisterCount() const;
497  static int FixedLiveRangeID(int index) { return -index - 1; }
498  static int FixedDoubleLiveRangeID(int index);
499  LiveRange* FixedLiveRangeFor(int index);
500  LiveRange* FixedDoubleLiveRangeFor(int index);
501  LiveRange* LiveRangeFor(int index);
502  HPhi* LookupPhi(LOperand* operand) const;
503  LGap* GetLastGap(HBasicBlock* block);
504
505  const char* RegisterName(int allocation_index);
506
507  inline bool IsGapAt(int index);
508
509  inline LInstruction* InstructionAt(int index);
510
511  inline LGap* GapAt(int index);
512
513  Zone zone_;
514
515  LPlatformChunk* chunk_;
516
517  // During liveness analysis keep a mapping from block id to live_in sets
518  // for blocks already analyzed.
519  ZoneList<BitVector*> live_in_sets_;
520
521  // Liveness analysis results.
522  ZoneList<LiveRange*> live_ranges_;
523
524  // Lists of live ranges
525  EmbeddedVector<LiveRange*, Register::kMaxNumAllocatableRegisters>
526      fixed_live_ranges_;
527  EmbeddedVector<LiveRange*, DoubleRegister::kMaxNumAllocatableRegisters>
528      fixed_double_live_ranges_;
529  ZoneList<LiveRange*> unhandled_live_ranges_;
530  ZoneList<LiveRange*> active_live_ranges_;
531  ZoneList<LiveRange*> inactive_live_ranges_;
532  ZoneList<LiveRange*> reusable_slots_;
533
534  // Next virtual register number to be assigned to temporaries.
535  int next_virtual_register_;
536  int first_artificial_register_;
537  GrowableBitVector double_artificial_registers_;
538
539  RegisterKind mode_;
540  int num_registers_;
541
542  BitVector* assigned_registers_;
543  BitVector* assigned_double_registers_;
544
545  HGraph* graph_;
546
547  bool has_osr_entry_;
548
549  // Indicates success or failure during register allocation.
550  bool allocation_ok_;
551
552#ifdef DEBUG
553  LifetimePosition allocation_finger_;
554#endif
555
556  DISALLOW_COPY_AND_ASSIGN(LAllocator);
557};
558
559
560class LAllocatorPhase : public CompilationPhase {
561 public:
562  LAllocatorPhase(const char* name, LAllocator* allocator);
563  ~LAllocatorPhase();
564
565 private:
566  LAllocator* allocator_;
567  unsigned allocator_zone_start_allocation_size_;
568
569  DISALLOW_COPY_AND_ASSIGN(LAllocatorPhase);
570};
571
572
573} }  // namespace v8::internal
574
575#endif  // V8_LITHIUM_ALLOCATOR_H_
576