1// Copyright 2012 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
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.
27
28#ifndef V8_LITHIUM_ALLOCATOR_H_
29#define V8_LITHIUM_ALLOCATOR_H_
30
31#include "v8.h"
32
33#include "allocation.h"
34#include "lithium.h"
35#include "zone.h"
36
37namespace v8 {
38namespace internal {
39
40// Forward declarations.
41class HBasicBlock;
42class HGraph;
43class HInstruction;
44class HPhi;
45class HTracer;
46class HValue;
47class BitVector;
48class StringStream;
49
50class LArgument;
51class LChunk;
52class LOperand;
53class LUnallocated;
54class LConstantOperand;
55class LGap;
56class LParallelMove;
57class LPointerMap;
58class LStackSlot;
59class LRegister;
60
61
62// This class represents a single point of a LOperand's lifetime.
63// For each lithium instruction there are exactly two lifetime positions:
64// the beginning and the end of the instruction. Lifetime positions for
65// different lithium instructions are disjoint.
66class LifetimePosition {
67 public:
68  // Return the lifetime position that corresponds to the beginning of
69  // the instruction with the given index.
70  static LifetimePosition FromInstructionIndex(int index) {
71    return LifetimePosition(index * kStep);
72  }
73
74  // Returns a numeric representation of this lifetime position.
75  int Value() const {
76    return value_;
77  }
78
79  // Returns the index of the instruction to which this lifetime position
80  // corresponds.
81  int InstructionIndex() const {
82    ASSERT(IsValid());
83    return value_ / kStep;
84  }
85
86  // Returns true if this lifetime position corresponds to the instruction
87  // start.
88  bool IsInstructionStart() const {
89    return (value_ & (kStep - 1)) == 0;
90  }
91
92  // Returns the lifetime position for the start of the instruction which
93  // corresponds to this lifetime position.
94  LifetimePosition InstructionStart() const {
95    ASSERT(IsValid());
96    return LifetimePosition(value_ & ~(kStep - 1));
97  }
98
99  // Returns the lifetime position for the end of the instruction which
100  // corresponds to this lifetime position.
101  LifetimePosition InstructionEnd() const {
102    ASSERT(IsValid());
103    return LifetimePosition(InstructionStart().Value() + kStep/2);
104  }
105
106  // Returns the lifetime position for the beginning of the next instruction.
107  LifetimePosition NextInstruction() const {
108    ASSERT(IsValid());
109    return LifetimePosition(InstructionStart().Value() + kStep);
110  }
111
112  // Returns the lifetime position for the beginning of the previous
113  // instruction.
114  LifetimePosition PrevInstruction() const {
115    ASSERT(IsValid());
116    ASSERT(value_ > 1);
117    return LifetimePosition(InstructionStart().Value() - kStep);
118  }
119
120  // Constructs the lifetime position which does not correspond to any
121  // instruction.
122  LifetimePosition() : value_(-1) {}
123
124  // Returns true if this lifetime positions corrensponds to some
125  // instruction.
126  bool IsValid() const { return value_ != -1; }
127
128  static inline LifetimePosition Invalid() { return LifetimePosition(); }
129
130  static inline LifetimePosition MaxPosition() {
131    // We have to use this kind of getter instead of static member due to
132    // crash bug in GDB.
133    return LifetimePosition(kMaxInt);
134  }
135
136 private:
137  static const int kStep = 2;
138
139  // Code relies on kStep being a power of two.
140  STATIC_ASSERT(IS_POWER_OF_TWO(kStep));
141
142  explicit LifetimePosition(int value) : value_(value) { }
143
144  int value_;
145};
146
147
148enum RegisterKind {
149  GENERAL_REGISTERS,
150  DOUBLE_REGISTERS
151};
152
153
154// 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
157class LInstruction;
158class LEnvironment;
159
160// Iterator for non-null temp operands.
161class TempIterator BASE_EMBEDDED {
162 public:
163  inline explicit TempIterator(LInstruction* instr);
164  inline bool Done();
165  inline LOperand* Current();
166  inline void Advance();
167
168 private:
169  inline void SkipUninteresting();
170  LInstruction* instr_;
171  int limit_;
172  int current_;
173};
174
175
176// Iterator for non-constant input operands.
177class InputIterator BASE_EMBEDDED {
178 public:
179  inline explicit InputIterator(LInstruction* instr);
180  inline bool Done();
181  inline LOperand* Current();
182  inline void Advance();
183
184 private:
185  inline void SkipUninteresting();
186  LInstruction* instr_;
187  int limit_;
188  int current_;
189};
190
191
192class UseIterator BASE_EMBEDDED {
193 public:
194  inline explicit UseIterator(LInstruction* instr);
195  inline bool Done();
196  inline LOperand* Current();
197  inline void Advance();
198
199 private:
200  InputIterator input_iterator_;
201  DeepIterator env_iterator_;
202};
203
204
205// Representation of the non-empty interval [start,end[.
206class UseInterval: public ZoneObject {
207 public:
208  UseInterval(LifetimePosition start, LifetimePosition end)
209      : start_(start), end_(end), next_(NULL) {
210    ASSERT(start.Value() < end.Value());
211  }
212
213  LifetimePosition start() const { return start_; }
214  LifetimePosition end() const { return end_; }
215  UseInterval* next() const { return next_; }
216
217  // Split this interval at the given position without effecting the
218  // live range that owns it. The interval must contain the position.
219  void SplitAt(LifetimePosition pos, Zone* zone);
220
221  // If this interval intersects with other return smallest position
222  // that belongs to both of them.
223  LifetimePosition Intersect(const UseInterval* other) const {
224    if (other->start().Value() < start_.Value()) return other->Intersect(this);
225    if (other->start().Value() < end_.Value()) return other->start();
226    return LifetimePosition::Invalid();
227  }
228
229  bool Contains(LifetimePosition point) const {
230    return start_.Value() <= point.Value() && point.Value() < end_.Value();
231  }
232
233 private:
234  void set_start(LifetimePosition start) { start_ = start; }
235  void set_next(UseInterval* next) { next_ = next; }
236
237  LifetimePosition start_;
238  LifetimePosition end_;
239  UseInterval* next_;
240
241  friend class LiveRange;  // Assigns to start_.
242};
243
244// Representation of a use position.
245class UsePosition: public ZoneObject {
246 public:
247  UsePosition(LifetimePosition pos, LOperand* operand);
248
249  LOperand* operand() const { return operand_; }
250  bool HasOperand() const { return operand_ != NULL; }
251
252  LOperand* hint() const { return hint_; }
253  void set_hint(LOperand* hint) { hint_ = hint; }
254  bool HasHint() const;
255  bool RequiresRegister() const;
256  bool RegisterIsBeneficial() const;
257
258  LifetimePosition pos() const { return pos_; }
259  UsePosition* next() const { return next_; }
260
261 private:
262  void set_next(UsePosition* next) { next_ = next; }
263
264  LOperand* operand_;
265  LOperand* hint_;
266  LifetimePosition pos_;
267  UsePosition* next_;
268  bool requires_reg_;
269  bool register_beneficial_;
270
271  friend class LiveRange;
272};
273
274// Representation of SSA values' live ranges as a collection of (continuous)
275// intervals over the instruction ordering.
276class LiveRange: public ZoneObject {
277 public:
278  static const int kInvalidAssignment = 0x7fffffff;
279
280  LiveRange(int id, Zone* zone);
281
282  UseInterval* first_interval() const { return first_interval_; }
283  UsePosition* first_pos() const { return first_pos_; }
284  LiveRange* parent() const { return parent_; }
285  LiveRange* TopLevel() { return (parent_ == NULL) ? this : parent_; }
286  LiveRange* next() const { return next_; }
287  bool IsChild() const { return parent() != NULL; }
288  int id() const { return id_; }
289  bool IsFixed() const { return id_ < 0; }
290  bool IsEmpty() const { return first_interval() == NULL; }
291  LOperand* CreateAssignedOperand(Zone* zone);
292  int assigned_register() const { return assigned_register_; }
293  int spill_start_index() const { return spill_start_index_; }
294  void set_assigned_register(int reg,
295                             RegisterKind register_kind,
296                             Zone* zone);
297  void MakeSpilled(Zone* zone);
298
299  // Returns use position in this live range that follows both start
300  // and last processed use position.
301  // Modifies internal state of live range!
302  UsePosition* NextUsePosition(LifetimePosition start);
303
304  // Returns use position for which register is required in this live
305  // range and which follows both start and last processed use position
306  // Modifies internal state of live range!
307  UsePosition* NextRegisterPosition(LifetimePosition start);
308
309  // Returns use position for which register is beneficial in this live
310  // range and which follows both start and last processed use position
311  // Modifies internal state of live range!
312  UsePosition* NextUsePositionRegisterIsBeneficial(LifetimePosition start);
313
314  // Can this live range be spilled at this position.
315  bool CanBeSpilled(LifetimePosition pos);
316
317  // Split this live range at the given position which must follow the start of
318  // the range.
319  // All uses following the given position will be moved from this
320  // live range to the result live range.
321  void SplitAt(LifetimePosition position, LiveRange* result, Zone* zone);
322
323  bool IsDouble() const { return is_double_; }
324  bool HasRegisterAssigned() const {
325    return assigned_register_ != kInvalidAssignment;
326  }
327  bool IsSpilled() const { return spilled_; }
328  UsePosition* FirstPosWithHint() const;
329
330  LOperand* FirstHint() const {
331    UsePosition* pos = FirstPosWithHint();
332    if (pos != NULL) return pos->hint();
333    return NULL;
334  }
335
336  LifetimePosition Start() const {
337    ASSERT(!IsEmpty());
338    return first_interval()->start();
339  }
340
341  LifetimePosition End() const {
342    ASSERT(!IsEmpty());
343    return last_interval_->end();
344  }
345
346  bool HasAllocatedSpillOperand() const;
347  LOperand* GetSpillOperand() const { return spill_operand_; }
348  void SetSpillOperand(LOperand* operand);
349
350  void SetSpillStartIndex(int start) {
351    spill_start_index_ = Min(start, spill_start_index_);
352  }
353
354  bool ShouldBeAllocatedBefore(const LiveRange* other) const;
355  bool CanCover(LifetimePosition position) const;
356  bool Covers(LifetimePosition position);
357  LifetimePosition FirstIntersection(LiveRange* other);
358
359  // Add a new interval or a new use position to this live range.
360  void EnsureInterval(LifetimePosition start,
361                      LifetimePosition end,
362                      Zone* zone);
363  void AddUseInterval(LifetimePosition start,
364                      LifetimePosition end,
365                      Zone* zone);
366  UsePosition* AddUsePosition(LifetimePosition pos,
367                              LOperand* operand,
368                              Zone* zone);
369
370  // Shorten the most recently added interval by setting a new start.
371  void ShortenTo(LifetimePosition start);
372
373#ifdef DEBUG
374  // True if target overlaps an existing interval.
375  bool HasOverlap(UseInterval* target) const;
376  void Verify() const;
377#endif
378
379 private:
380  void ConvertOperands(Zone* zone);
381  UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const;
382  void AdvanceLastProcessedMarker(UseInterval* to_start_of,
383                                  LifetimePosition but_not_past) const;
384
385  int id_;
386  bool spilled_;
387  bool is_double_;
388  int assigned_register_;
389  UseInterval* last_interval_;
390  UseInterval* first_interval_;
391  UsePosition* first_pos_;
392  LiveRange* parent_;
393  LiveRange* next_;
394  // This is used as a cache, it doesn't affect correctness.
395  mutable UseInterval* current_interval_;
396  UsePosition* last_processed_use_;
397  LOperand* spill_operand_;
398  int spill_start_index_;
399};
400
401
402class GrowableBitVector BASE_EMBEDDED {
403 public:
404  GrowableBitVector() : bits_(NULL) { }
405
406  bool Contains(int value) const {
407    if (!InBitsRange(value)) return false;
408    return bits_->Contains(value);
409  }
410
411  void Add(int value, Zone* zone) {
412    EnsureCapacity(value, zone);
413    bits_->Add(value);
414  }
415
416 private:
417  static const int kInitialLength = 1024;
418
419  bool InBitsRange(int value) const {
420    return bits_ != NULL && bits_->length() > value;
421  }
422
423  void EnsureCapacity(int value, Zone* zone) {
424    if (InBitsRange(value)) return;
425    int new_length = bits_ == NULL ? kInitialLength : bits_->length();
426    while (new_length <= value) new_length *= 2;
427    BitVector* new_bits = new(zone) BitVector(new_length, zone);
428    if (bits_ != NULL) new_bits->CopyFrom(*bits_);
429    bits_ = new_bits;
430  }
431
432  BitVector* bits_;
433};
434
435
436class LAllocator BASE_EMBEDDED {
437 public:
438  LAllocator(int first_virtual_register, HGraph* graph);
439
440  static void TraceAlloc(const char* msg, ...);
441
442  // Checks whether the value of a given virtual register is tagged.
443  bool HasTaggedValue(int virtual_register) const;
444
445  // Returns the register kind required by the given virtual register.
446  RegisterKind RequiredRegisterKind(int virtual_register) const;
447
448  bool Allocate(LChunk* chunk);
449
450  const ZoneList<LiveRange*>* live_ranges() const { return &live_ranges_; }
451  const Vector<LiveRange*>* fixed_live_ranges() const {
452    return &fixed_live_ranges_;
453  }
454  const Vector<LiveRange*>* fixed_double_live_ranges() const {
455    return &fixed_double_live_ranges_;
456  }
457
458  LChunk* chunk() const { return chunk_; }
459  HGraph* graph() const { return graph_; }
460
461  int GetVirtualRegister() {
462    if (next_virtual_register_ > LUnallocated::kMaxVirtualRegisters) {
463      allocation_ok_ = false;
464    }
465    return next_virtual_register_++;
466  }
467
468  bool AllocationOk() { return allocation_ok_; }
469
470  void MarkAsOsrEntry() {
471    // There can be only one.
472    ASSERT(!has_osr_entry_);
473    // Simply set a flag to find and process instruction later.
474    has_osr_entry_ = true;
475  }
476
477#ifdef DEBUG
478  void Verify() const;
479#endif
480
481 private:
482  void MeetRegisterConstraints();
483  void ResolvePhis();
484  void BuildLiveRanges();
485  void AllocateGeneralRegisters();
486  void AllocateDoubleRegisters();
487  void ConnectRanges();
488  void ResolveControlFlow();
489  void PopulatePointerMaps();
490  void ProcessOsrEntry();
491  void AllocateRegisters();
492  bool CanEagerlyResolveControlFlow(HBasicBlock* block) const;
493  inline bool SafePointsAreInOrder() const;
494
495  // Liveness analysis support.
496  void InitializeLivenessAnalysis();
497  BitVector* ComputeLiveOut(HBasicBlock* block);
498  void AddInitialIntervals(HBasicBlock* block, BitVector* live_out);
499  void ProcessInstructions(HBasicBlock* block, BitVector* live);
500  void MeetRegisterConstraints(HBasicBlock* block);
501  void MeetConstraintsBetween(LInstruction* first,
502                              LInstruction* second,
503                              int gap_index);
504  void ResolvePhis(HBasicBlock* block);
505
506  // Helper methods for building intervals.
507  LOperand* AllocateFixed(LUnallocated* operand, int pos, bool is_tagged);
508  LiveRange* LiveRangeFor(LOperand* operand);
509  void Define(LifetimePosition position, LOperand* operand, LOperand* hint);
510  void Use(LifetimePosition block_start,
511           LifetimePosition position,
512           LOperand* operand,
513           LOperand* hint);
514  void AddConstraintsGapMove(int index, LOperand* from, LOperand* to);
515
516  // Helper methods for updating the life range lists.
517  void AddToActive(LiveRange* range);
518  void AddToInactive(LiveRange* range);
519  void AddToUnhandledSorted(LiveRange* range);
520  void AddToUnhandledUnsorted(LiveRange* range);
521  void SortUnhandled();
522  bool UnhandledIsSorted();
523  void ActiveToHandled(LiveRange* range);
524  void ActiveToInactive(LiveRange* range);
525  void InactiveToHandled(LiveRange* range);
526  void InactiveToActive(LiveRange* range);
527  void FreeSpillSlot(LiveRange* range);
528  LOperand* TryReuseSpillSlot(LiveRange* range);
529
530  // Helper methods for allocating registers.
531  bool TryAllocateFreeReg(LiveRange* range);
532  void AllocateBlockedReg(LiveRange* range);
533
534  // Live range splitting helpers.
535
536  // Split the given range at the given position.
537  // If range starts at or after the given position then the
538  // original range is returned.
539  // Otherwise returns the live range that starts at pos and contains
540  // all uses from the original range that follow pos. Uses at pos will
541  // still be owned by the original range after splitting.
542  LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos);
543
544  // Split the given range in a position from the interval [start, end].
545  LiveRange* SplitBetween(LiveRange* range,
546                          LifetimePosition start,
547                          LifetimePosition end);
548
549  // Find a lifetime position in the interval [start, end] which
550  // is optimal for splitting: it is either header of the outermost
551  // loop covered by this interval or the latest possible position.
552  LifetimePosition FindOptimalSplitPos(LifetimePosition start,
553                                       LifetimePosition end);
554
555  // Spill the given life range after position pos.
556  void SpillAfter(LiveRange* range, LifetimePosition pos);
557
558  // Spill the given life range after position start and up to position end.
559  void SpillBetween(LiveRange* range,
560                    LifetimePosition start,
561                    LifetimePosition end);
562
563  void SplitAndSpillIntersecting(LiveRange* range);
564
565  void Spill(LiveRange* range);
566  bool IsBlockBoundary(LifetimePosition pos);
567
568  // Helper methods for resolving control flow.
569  void ResolveControlFlow(LiveRange* range,
570                          HBasicBlock* block,
571                          HBasicBlock* pred);
572
573  // Return parallel move that should be used to connect ranges split at the
574  // given position.
575  LParallelMove* GetConnectingParallelMove(LifetimePosition pos);
576
577  // Return the block which contains give lifetime position.
578  HBasicBlock* GetBlock(LifetimePosition pos);
579
580  // Helper methods for the fixed registers.
581  int RegisterCount() const;
582  static int FixedLiveRangeID(int index) { return -index - 1; }
583  static int FixedDoubleLiveRangeID(int index);
584  LiveRange* FixedLiveRangeFor(int index);
585  LiveRange* FixedDoubleLiveRangeFor(int index);
586  LiveRange* LiveRangeFor(int index);
587  HPhi* LookupPhi(LOperand* operand) const;
588  LGap* GetLastGap(HBasicBlock* block);
589
590  const char* RegisterName(int allocation_index);
591
592  inline bool IsGapAt(int index);
593
594  inline LInstruction* InstructionAt(int index);
595
596  inline LGap* GapAt(int index);
597
598  Zone* zone_;
599
600  LChunk* chunk_;
601
602  // During liveness analysis keep a mapping from block id to live_in sets
603  // for blocks already analyzed.
604  ZoneList<BitVector*> live_in_sets_;
605
606  // Liveness analysis results.
607  ZoneList<LiveRange*> live_ranges_;
608
609  // Lists of live ranges
610  EmbeddedVector<LiveRange*, Register::kNumAllocatableRegisters>
611      fixed_live_ranges_;
612  EmbeddedVector<LiveRange*, DoubleRegister::kNumAllocatableRegisters>
613      fixed_double_live_ranges_;
614  ZoneList<LiveRange*> unhandled_live_ranges_;
615  ZoneList<LiveRange*> active_live_ranges_;
616  ZoneList<LiveRange*> inactive_live_ranges_;
617  ZoneList<LiveRange*> reusable_slots_;
618
619  // Next virtual register number to be assigned to temporaries.
620  int next_virtual_register_;
621  int first_artificial_register_;
622  GrowableBitVector double_artificial_registers_;
623
624  RegisterKind mode_;
625  int num_registers_;
626
627  HGraph* graph_;
628
629  bool has_osr_entry_;
630
631  // Indicates success or failure during register allocation.
632  bool allocation_ok_;
633
634  DISALLOW_COPY_AND_ASSIGN(LAllocator);
635};
636
637
638} }  // namespace v8::internal
639
640#endif  // V8_LITHIUM_ALLOCATOR_H_
641