Greedy allocator: perf work

src/compiler/register-allocator.h

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_REGISTER_ALLOCATOR_H_
 #define V8_REGISTER_ALLOCATOR_H_
 
 #include "src/compiler/instruction.h"
 #include "src/ostreams.h"
 #include "src/zone-containers.h"
@@ skipping 233 matching lines @@
   UsePositionHintType hint_type() const {
     return HintTypeField::decode(flags_);
   }
   bool HasHint() const;
   bool HintRegister(int* register_index) const;
   void ResolveHint(UsePosition* use_pos);
   bool IsResolved() const {
     return hint_type() != UsePositionHintType::kUnresolved;
   }
   static UsePositionHintType HintTypeForOperand(const InstructionOperand& op);
+  void dump_hint(std::ostream& os, const RegisterConfiguration* config);
 
  private:
   typedef BitField<UsePositionType, 0, 2> TypeField;
   typedef BitField<UsePositionHintType, 2, 3> HintTypeField;
   typedef BitField<bool, 5, 1> RegisterBeneficialField;
   typedef BitField<int32_t, 6, 6> AssignedRegisterField;
 
   InstructionOperand* const operand_;
   void* hint_;
   UsePosition* next_;
   LifetimePosition const pos_;
   uint32_t flags_;
 
   DISALLOW_COPY_AND_ASSIGN(UsePosition);
 };
 
 
 class SpillRange;
+class LiveRangeGroup;
 
 
 // Representation of SSA values' live ranges as a collection of (continuous)
 // intervals over the instruction ordering.
 class LiveRange final : public ZoneObject {
  public:
   explicit LiveRange(int id, MachineType machine_type);
 
   UseInterval* first_interval() const { return first_interval_; }
   UsePosition* first_pos() const { return first_pos_; }
@@ skipping 52 matching lines @@
   // range and which follows both start and last processed use position
   UsePosition* NextUsePositionRegisterIsBeneficial(
       LifetimePosition start) const;
 
   // Returns use position for which register is beneficial in this live
   // range and which precedes start.
   UsePosition* PreviousUsePositionRegisterIsBeneficial(
       LifetimePosition start) const;
 
   // Can this live range be spilled at this position.
-  bool CanBeSpilled(LifetimePosition pos) const;
+  bool CanBeSpilled(LifetimePosition pos) const { return CanBeSplit(pos); }
+
+  // Can this live range be split at this position.
+  bool CanBeSplit(LifetimePosition pos) const;
 
   // Split this live range at the given position which must follow the start of
   // the range.
   // All uses following the given position will be moved from this
   // live range to the result live range.
   void SplitAt(LifetimePosition position, LiveRange* result, Zone* zone);
 
   // Returns nullptr when no register is hinted, otherwise sets register_index.
   UsePosition* FirstHintPosition(int* register_index) const;
   UsePosition* FirstHintPosition() const {
@@ skipping 66 matching lines @@
                             const InstructionOperand& spill_op);
   void SetUseHints(int register_index);
   void UnsetUseHints() { SetUseHints(kUnassignedRegister); }
 
   struct SpillAtDefinitionList;
 
   SpillAtDefinitionList* spills_at_definition() const {
     return spills_at_definition_;
   }
 
+  LiveRangeGroup* group() { return group_; }

[Benedikt Meurer, 2015/06/11 05:30:29]

Nit: Make this method const.

[Mircea Trofin, 2015/06/11 07:19:36]

Done.

+  void SetGroup(LiveRangeGroup* grp) { group_ = grp; }
+
+  float weight() const {
+    DCHECK(weight_ >= 0.0f);

[Benedikt Meurer, 2015/06/11 05:30:29]

Trivial getters should not have DCHECK's in them. Check on assignment or
introduce a setter.

[Mircea Trofin, 2015/06/11 07:19:36]

The point is that I want to make sure no attempt to access weight is made
without pre-calculating it. I'll call it GetWeight then.

+    return weight_;
+  }
+
+  unsigned size() {

[Benedikt Meurer, 2015/06/11 05:30:30]

This getter does perform work, so it's not a simple getter, hence it must not
look like one. Please rename to GetSize().

[Mircea Trofin, 2015/06/11 07:19:36]

Done.

+    if (size_ < 0) RecalculateSize();
+    DCHECK(size_ > 0);
+    return static_cast<unsigned>(size_);
+  }
+
+  void InvalidateWeightAndSize() {
+    weight_ = kInvalidWeight;
+    size_ = kInvalidSize;
+  }
+  void RecalculateWeight(InstructionSequence* code);
+  LifetimePosition GetFirstSplittablePosition();
+
+  static const float kMaxWeight;
+
  private:
+  static const float kUseInLoopWeightMultiplier;
+  static const float kPreferredRegisterWeightMultiplier;
+  static const float kInvalidWeight;
+  static const int kInvalidSize = -1;
+
+  void RecalculateSize();
   void set_spill_type(SpillType value) {
     bits_ = SpillTypeField::update(bits_, value);
   }
 
   void set_spilled(bool value) { bits_ = SpilledField::update(bits_, value); }
 
   UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const;
   void AdvanceLastProcessedMarker(UseInterval* to_start_of,
                                   LifetimePosition but_not_past) const;
 
@@ skipping 19 matching lines @@
     SpillRange* spill_range_;
   };
   SpillAtDefinitionList* spills_at_definition_;
   // This is used as a cache, it doesn't affect correctness.
   mutable UseInterval* current_interval_;
   // This is used as a cache, it doesn't affect correctness.
   mutable UsePosition* last_processed_use_;
   // This is used as a cache, it's invalid outside of BuildLiveRanges.
   mutable UsePosition* current_hint_position_;
 
+  // Used only by the greedy allocator.
+  float weight_;
+  int size_;
+  LiveRangeGroup* group_;
   DISALLOW_COPY_AND_ASSIGN(LiveRange);
 };
 
 
+class LiveRangeGroup final : public ZoneObject {
+ public:
+  explicit LiveRangeGroup(Zone* zone) : ranges_(zone) {}
+  ZoneSet<LiveRange*>& ranges() { return ranges_; }
+  bool CanAdd(LiveRange* r);
+  void TryMerge(LiveRangeGroup* other);
+
+ private:
+  ZoneSet<LiveRange*> ranges_;

[Benedikt Meurer, 2015/06/11 05:30:30]

I'm not sure ZoneSet is such a great datastructure for this purpose.

[Mircea Trofin, 2015/06/11 07:19:36]

What would you propose as an alternative?

Full disclosure, I did consider a R x I matrix - where "R" is the number of
physical registers and "I" is the number of positions. That would simplify a
number of things, especially the conflict iterator. Lookup would be O(1), too -
rather than O(log(n)) right now. 

However, the memory cost could be high. Using some codebases we compile with
subzero - so a similar in spirit scenario (C code - if you squint and think of
asm.js as really "C"), we saw programs with 100K IR instructions coming into the
allocator. Granted, different IR language, but I feel we could use it as a
reasonable hint. So for that scenario, since we here have 4 positions per
instruction, it'd mean ~400K per register, so then a few megs just for this
structure.

That worried me a bit. I didn't continue with the analysis - there is a cutoff
point after which a set may also become more expensive than a dumb matrix. My
priority still is getting the codegen to a good place where it shows the value
of the algorithm, so I postponed these decisions, and I think the APIs through
which the rest of the allocator uses this storage are abstract enough for me to
swap implementations later and analyze this area better.

The alternative I had with the initial checkin before was inspired by Mozilla
and turned out to be *really* bad. Mozilla uses a splay tree, but then they
chance on there being no more than 1 or 2 conflicts per candidate live range. If
that's not the case, the range loses automatically. Seemed suboptimal to me, and
also a choice that makes understanding the effects of the algorithm on large
programs hard - you can't rely on "best choice wins", it is rather "best choice,
or sometimes not, if more than a few worse choices are conflicting" :) Using
that implementation choice, compile time for programs like zlib ballooned to
over 5 minutes (!!) from a few hundred ms.

I was planning actually to talk to the author (on the Mozilla side), at our last
social, to get a better understanding of the tradeoffs he found - but he had a
conflict, so next time.

I haven't analyzed much LLVM's, they call it a Matrix though, interestingly
enough.

At the end of the day, with this structure, I get a compile time in the
neighborhood of what linear does - for complicated programs (like zlib), the
difference is noticeable (100 vs 148 ms spent in the turbofan pipeline, with
regalloc alone being 3x more expensive - from 18ms to 66ms), but it's not 5
minutes, and at this stage, all I care about is codegen quality - gathering data
to allow us to analyse the value of this allocator, for a scenario that's mainly
AoT compilation. Not saying compile time doesn't matter - just prioritizing it
after we feel happy enough with the codegen.

Sorry for the long rant :) But if you have suggestions for improvements here,
let's chat, but I'd prefer separating that from this particular CL - I need to
land this to unblock more changes in the code quality side of things - but this
structure, I feel, will be the battleground for faster compile time, so I care
about it quite a lot.

+
+  DISALLOW_COPY_AND_ASSIGN(LiveRangeGroup);
+};
+
 struct PrintableLiveRange {
   const RegisterConfiguration* register_configuration_;
   const LiveRange* range_;
 };
 
 
 std::ostream& operator<<(std::ostream& os,
                          const PrintableLiveRange& printable_range);
 
 
 class SpillRange final : public ZoneObject {
  public:
   static const int kUnassignedSlot = -1;
   SpillRange(LiveRange* range, Zone* zone);
 
   UseInterval* interval() const { return use_interval_; }
   // Currently, only 4 or 8 byte slots are supported.
   int ByteWidth() const;
   bool IsEmpty() const { return live_ranges_.empty(); }
   bool TryMerge(SpillRange* other);
 
   void set_assigned_slot(int index) {
     DCHECK_EQ(kUnassignedSlot, assigned_slot_);
     assigned_slot_ = index;
   }
+  bool IsSlotAssigned() const { return assigned_slot_ != kUnassignedSlot; }
   int assigned_slot() {
     DCHECK_NE(kUnassignedSlot, assigned_slot_);
     return assigned_slot_;
   }
 
  private:
   LifetimePosition End() const { return end_position_; }
   ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; }
   bool IsIntersectingWith(SpillRange* other) const;
   // Merge intervals, making sure the use intervals are sorted
   void MergeDisjointIntervals(UseInterval* other);
 
   ZoneVector<LiveRange*> live_ranges_;
   UseInterval* use_interval_;
   LifetimePosition end_position_;
   int assigned_slot_;
 
   DISALLOW_COPY_AND_ASSIGN(SpillRange);
 };
 
 
+std::ostream& operator<<(std::ostream& os, SpillRange* range);
+
+
 class RegisterAllocationData final : public ZoneObject {
  public:
   class PhiMapValue : public ZoneObject {
    public:
     PhiMapValue(PhiInstruction* phi, const InstructionBlock* block, Zone* zone);
 
     const PhiInstruction* phi() const { return phi_; }
     const InstructionBlock* block() const { return block_; }
 
     // For hinting.
@@ skipping 190 matching lines @@
            InstructionOperand* operand) {
     Use(block_start, position, operand, nullptr, UsePositionHintType::kNone);
   }
 
   RegisterAllocationData* const data_;
   ZoneMap<InstructionOperand*, UsePosition*> phi_hints_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRangeBuilder);
 };
 
+struct AllocatorStats {
+  unsigned spills;
+  unsigned wins;
+  unsigned losses_no_eviction;
+  unsigned losses_after_eviction;
+  unsigned good_split_attempts;
+  unsigned good_split_successes;
+  unsigned good_split_smart_above;
+  unsigned good_split_smart_below;
+  unsigned good_split_above;
+  unsigned good_split_below;
+  unsigned groups_attempted;
+  unsigned groups_succeeded;
+  unsigned groups_allocated;
+  void reset() { *this = {0}; }
+};
+
+
+std::ostream& operator<<(std::ostream& os, const AllocatorStats& stats);
+
 
 class RegisterAllocator : public ZoneObject {
  public:
   explicit RegisterAllocator(RegisterAllocationData* data, RegisterKind kind);
 
  protected:
+  AllocatorStats stats_;
   RegisterAllocationData* data() const { return data_; }
   InstructionSequence* code() const { return data()->code(); }
   RegisterKind mode() const { return mode_; }
   int num_registers() const { return num_registers_; }
 
   Zone* allocation_zone() const { return data()->allocation_zone(); }
 
   LiveRange* LiveRangeFor(int index) { return data()->LiveRangeFor(index); }
 
   // Split the given range at the given position.
@@ skipping 13 matching lines @@
   // loop covered by this interval or the latest possible position.
   LifetimePosition FindOptimalSplitPos(LifetimePosition start,
                                        LifetimePosition end);
 
   void Spill(LiveRange* range);
 
   // If we are trying to spill a range inside the loop try to
   // hoist spill position out to the point just before the loop.
   LifetimePosition FindOptimalSpillingPos(LiveRange* range,
                                           LifetimePosition pos);
+  const char* RegisterName(int allocation_index) const;
 
  private:
   RegisterAllocationData* const data_;
   const RegisterKind mode_;
   const int num_registers_;
 
   DISALLOW_COPY_AND_ASSIGN(RegisterAllocator);
 };
 
 
 class LinearScanAllocator final : public RegisterAllocator {
  public:
   LinearScanAllocator(RegisterAllocationData* data, RegisterKind kind,
                       Zone* local_zone);
 
   // Phase 4: compute register assignments.
   void AllocateRegisters();
 
  private:
-  const char* RegisterName(int allocation_index) const;
-
   ZoneVector<LiveRange*>& unhandled_live_ranges() {
     return unhandled_live_ranges_;
   }
   ZoneVector<LiveRange*>& active_live_ranges() { return active_live_ranges_; }
   ZoneVector<LiveRange*>& inactive_live_ranges() {
     return inactive_live_ranges_;
   }
 
   void SetLiveRangeAssignedRegister(LiveRange* range, int reg);
 
@@ skipping 32 matching lines @@
   ZoneVector<LiveRange*> active_live_ranges_;
   ZoneVector<LiveRange*> inactive_live_ranges_;
 
 #ifdef DEBUG
   LifetimePosition allocation_finger_;
 #endif
 
   DISALLOW_COPY_AND_ASSIGN(LinearScanAllocator);
 };
 
+
+// Storage detail for CoalescedLiveRanges.
+struct AllocatedInterval {
+  LifetimePosition start;
+  LifetimePosition end;
+  LiveRange* range;
+  struct Comparer : public std::binary_function<AllocatedInterval,

[Benedikt Meurer, 2015/06/11 05:30:30]

Why do you need this Comparer class? Can't you just define operator< on
AllocatedInterval directly?

[Mircea Trofin, 2015/06/11 07:19:36]

Oh, I see - because std::less would then just use that? Sure - this way though I
could have other intrinsic comparers to AllocatedInterval, while in the scenario
of the storage, I want this one. I admit, that's all hypothetical, though. At
the same time, I see no inefficiency with the current design, and, subjectively,
I find it clearer.

+                                                AllocatedInterval, bool> {
+    bool operator()(const AllocatedInterval& x,
+                    const AllocatedInterval& y) const {
+      return x.start < y.start;
+    }
+  };
+};
+
+
 class CoalescedLiveRanges;
 
 
+// Iterator over allocated live ranges (CoalescedLiveRanges) that conflict with

[Benedikt Meurer, 2015/06/11 05:30:29]

This whole iterator looks quite complex. Maybe we should have a better data
structure that does not require such a complex iterator instead?

[Mircea Trofin, 2015/06/11 07:19:36]

Possibly, please see long rant above :)

+// a given one. See CoalescedLiveRanges::first_conflict.
+// Note that iterating may produce non-consecutively repeating live ranges.
+struct conflict_iterator {
+  friend class CoalescedLiveRanges;

[Benedikt Meurer, 2015/06/11 05:30:30]

friend classes should be listed in the private section.

[Mircea Trofin, 2015/06/11 07:19:36]

Done.

+  conflict_iterator() : storage_(nullptr) {}
+  friend bool operator==(const conflict_iterator& first,
+                         const conflict_iterator& second);
+  LiveRange* operator->() { return pos_->range; }
+
+  LiveRange* operator*() { return pos_->range; }

[Benedikt Meurer, 2015/06/11 05:30:29]

This should return a LiveRange&, not a LiveRange*.

[Mircea Trofin, 2015/06/11 07:19:36]

The element of the set if "LiveRange*", so dereferencing the iterator produces a
value typed as that. It's akin to how for a std::set<LiveRange*>, dereferencing
the iterator also returns LiveRange*.

+
+  conflict_iterator& operator++();
+  bool IsEnd() const {

[Benedikt Meurer, 2015/06/11 05:30:29]

STL iterators compare against some end. Don't try to add a wrapper for that,
which might get out of sync.

[Mircea Trofin, 2015/06/11 07:19:36]

I'm not sure how it could it get out of sync (and what it's sync-ed to).

The trade-off here is: similarity with reusable collections, vs some code
simplicity savings in a few places. If we removed IsEnd, we'd have to carry
around the "right" end, however all scenarios we're using this iterator use it
in a very constrained manner - no mutations for example. But, if we feel
similarity with STL trumps that, happy to change it accordingly (removing
IsEnd). I went back and forth on this one, so any nudge will do :)

+    DCHECK(storage_ != nullptr);
+    return pos_ == storage_->end();
+  }
+
+ private:
+  typedef ZoneSet<AllocatedInterval, AllocatedInterval::Comparer> IntervalStore;
+  typedef IntervalStore::const_iterator interval_iterator;
+
+  void Invalidate() {
+    DCHECK(storage_ != nullptr);
+    pos_ = storage_->end();
+    query_ = nullptr;
+  }
+
+  static bool Intersects(LifetimePosition a_start, LifetimePosition a_end,
+                         LifetimePosition b_start, LifetimePosition b_end) {
+    if (a_start == b_start) return true;
+    if (a_start < b_start) return a_end > b_start;
+    return Intersects(b_start, b_end, a_start, a_end);
+  }
+
+  bool QueryIntersectsAllocatedInterval() {
+    DCHECK(query_ != nullptr);
+    return Intersects(query_->start(), query_->end(), pos_->start, pos_->end);
+  }
+
+  bool NextQueryIntersectsAllocatedInterval() {
+    DCHECK(query_->next() != nullptr);
+    return Intersects(query_->next()->start(), query_->next()->end(),
+                      pos_->start, pos_->end);
+  }
+
+  conflict_iterator(UseInterval* query, IntervalStore* storage)
+      : query_(query), storage_(storage) {
+    InitializeForNewQuery();
+  }
+
+  explicit conflict_iterator(IntervalStore* storage) : storage_(storage) {
+    Invalidate();

[Benedikt Meurer, 2015/06/11 05:30:29]

Initialize properly instead of calling Invalidate in the constructor.

[Mircea Trofin, 2015/06/11 07:19:36]

Not sure what you mean by "proper" initialization, but the goal here is to have
an "end" constructor for a given storage. I'm using "Invalidate" as a canonical
way of achieving that. What trade-offs am I missing?

+  }
+
+  static conflict_iterator EndIteratorForStorage(IntervalStore* storage) {
+    conflict_iterator ret(storage);
+    return ret;
+  }
+
+  void InitializeForNewQuery();
+  void SkipMatchedQueries();
+
+  AllocatedInterval AsAllocatedInterval(LifetimePosition pos) {
+    return {pos, LifetimePosition::Invalid(), nullptr};
+  }
+
+  UseInterval* query_;
+  IntervalStore* storage_;
+  interval_iterator pos_;
+};
+
+bool operator==(const conflict_iterator& first,
+                const conflict_iterator& second);
+bool operator!=(const conflict_iterator& first,
+                const conflict_iterator& second);
+
+
 // A variant of the LLVM Greedy Register Allocator. See
 // http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html
 class GreedyAllocator final : public RegisterAllocator {
  public:
   explicit GreedyAllocator(RegisterAllocationData* data, RegisterKind kind,
                            Zone* local_zone);
 
   void AllocateRegisters();
 
  private:
-  LifetimePosition GetSplittablePos(LifetimePosition pos);
+  void AllocateRange(LiveRange* current);
+  void AllocateGroup(LiveRangeGroup* grp);
+  bool TryAllocateGroup(LiveRangeGroup* grp);
+  bool TryAllocateGroupAtRegister(unsigned reg, LiveRangeGroup* grp);

[Jarin, 2015/06/12 04:09:10]

grp -> group

+
+  struct PQueueElem {
+    bool IsGroup() { return is_grp_; }

[Jarin, 2015/06/12 04:09:10]

is_grp_ -> is_group_

+    explicit PQueueElem(LiveRange* range) : is_grp_(false) {
+      storage_.range_ = range;
+    }
+
+    explicit PQueueElem(LiveRangeGroup* grp) : is_grp_(true) {
+      storage_.grp_ = grp;
+    }
+
+
+    LiveRange* get_range() {
+      if (is_grp_) return nullptr;
+      return storage_.range_;
+    }
+
+
+    LiveRangeGroup* get_group() {
+      if (is_grp_) return storage_.grp_;
+      return nullptr;
+    }
+
+   private:
+    bool is_grp_;
+    union {
+      LiveRange* range_;
+      LiveRangeGroup* grp_;
+    } storage_;
+  };
+
+  void GroupAndEnqueue();
   const RegisterConfiguration* config() const { return data()->config(); }
   Zone* local_zone() const { return local_zone_; }
-  bool TryReuseSpillForPhi(LiveRange* range);
-  int GetHintedRegister(LiveRange* range);
 
-  typedef ZonePriorityQueue<std::pair<unsigned, LiveRange*>> PQueue;
+  struct PQueueElemComparer
+      : public std::binary_function<std::pair<unsigned, PQueueElem>,
+                                    std::pair<unsigned, PQueueElem>, bool> {
+    bool operator()(const std::pair<unsigned, PQueueElem>& x,
+                    const std::pair<unsigned, PQueueElem>& y) const {
+      return x.first < y.first;
+    }
+  };
 
-  unsigned GetLiveRangeSize(LiveRange* range);
+  typedef ZonePriorityQueue<std::pair<unsigned, PQueueElem>, PQueueElemComparer>
+      PQueue;
+
   void Enqueue(LiveRange* range);
+  void Enqueue(LiveRangeGroup* group);
 
   void Evict(LiveRange* range);
-  float CalculateSpillWeight(LiveRange* range);
-  float CalculateMaxSpillWeight(const ZoneSet<LiveRange*>& ranges);
+  void EvictAll(int reg, const conflict_iterator& first_conflict);
 
+  // Find the register with the minimum spill weight. If that is still higher
+  // or equal to competing, return -1.
+  int FindRegisterToEvictForRange(
+      conflict_iterator
+          all_conflicts[RegisterConfiguration::kMaxDoubleRegisters],
+      float competing);
 
-  bool TryAllocate(LiveRange* current, ZoneSet<LiveRange*>* conflicting);
-  bool TryAllocatePhysicalRegister(unsigned reg_id, LiveRange* range,
-                                   ZoneSet<LiveRange*>* conflicting);
-  bool HandleSpillOperands(LiveRange* range);
-  void AllocateBlockedRange(LiveRange* current, LifetimePosition pos,
-                            bool spill);
+  // Same as above, for all the registers in a group.
+  int FindRegisterToEvictForGroup(LiveRangeGroup* grp, float competing);
+
+  template <typename TIter>
+  float CalculateMaxSpillWeight(const TIter& begin, const TIter& end);
+
+  bool HandleSpillOperands(LiveRange* range, LiveRange** remaining);
+  void HandleBlockedRange(LiveRange* current);
+  bool TrySplitBeforeLoops(LiveRange* current);
+  bool TrySplitAfterLoops(LiveRange* current);
+  bool TrySplitAroundCalls(LiveRange* range);
 
   LiveRange* SpillBetweenUntil(LiveRange* range, LifetimePosition start,
                                LifetimePosition until, LifetimePosition end);
   void AssignRangeToRegister(int reg_id, LiveRange* range);
 
-  LifetimePosition FindProgressingSplitPosition(LiveRange* range,
-                                                bool* is_spill_pos);
-
   Zone* local_zone_;
   ZoneVector<CoalescedLiveRanges*> allocations_;
   PQueue queue_;
   DISALLOW_COPY_AND_ASSIGN(GreedyAllocator);
 };
 
 
 class SpillSlotLocator final : public ZoneObject {
  public:
   explicit SpillSlotLocator(RegisterAllocationData* data);
@@ skipping 70 matching lines @@
   RegisterAllocationData* const data_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRangeConnector);
 };
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_REGISTER_ALLOCATOR_H_