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