deps/v8/src/compiler/register-allocator.h

   1 // Copyright 2014 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_REGISTER_ALLOCATOR_H_
   6 #define V8_REGISTER_ALLOCATOR_H_
   7
   8 #include "src/compiler/instruction.h"
   9 #include "src/zone-containers.h"
  10
  11 namespace v8 {
  12 namespace internal {
  13 namespace compiler {
  14
  15 enum RegisterKind {
  16   UNALLOCATED_REGISTERS,
  17   GENERAL_REGISTERS,
  18   DOUBLE_REGISTERS
  19 };
  20
  21
  22 // This class represents a single point of a InstructionOperand's lifetime. For
  23 // each instruction there are exactly two lifetime positions: the beginning and
  24 // the end of the instruction. Lifetime positions for different instructions are
  25 // disjoint.
  26 class LifetimePosition FINAL {
  27  public:
  28   // Return the lifetime position that corresponds to the beginning of
  29   // the instruction with the given index.
  30   static LifetimePosition FromInstructionIndex(int index) {
  31     return LifetimePosition(index * kStep);
  32   }
  33
  34   // Returns a numeric representation of this lifetime position.
  35   int Value() const { return value_; }
  36
  37   // Returns the index of the instruction to which this lifetime position
  38   // corresponds.
  39   int InstructionIndex() const {
  40     DCHECK(IsValid());
  41     return value_ / kStep;
  42   }
  43
  44   // Returns true if this lifetime position corresponds to the instruction
  45   // start.
  46   bool IsInstructionStart() const { return (value_ & (kStep - 1)) == 0; }
  47
  48   // Returns the lifetime position for the start of the instruction which
  49   // corresponds to this lifetime position.
  50   LifetimePosition InstructionStart() const {
  51     DCHECK(IsValid());
  52     return LifetimePosition(value_ & ~(kStep - 1));
  53   }
  54
  55   // Returns the lifetime position for the end of the instruction which
  56   // corresponds to this lifetime position.
  57   LifetimePosition InstructionEnd() const {
  58     DCHECK(IsValid());
  59     return LifetimePosition(InstructionStart().Value() + kStep / 2);
  60   }
  61
  62   // Returns the lifetime position for the beginning of the next instruction.
  63   LifetimePosition NextInstruction() const {
  64     DCHECK(IsValid());
  65     return LifetimePosition(InstructionStart().Value() + kStep);
  66   }
  67
  68   // Returns the lifetime position for the beginning of the previous
  69   // instruction.
  70   LifetimePosition PrevInstruction() const {
  71     DCHECK(IsValid());
  72     DCHECK(value_ > 1);
  73     return LifetimePosition(InstructionStart().Value() - kStep);
  74   }
  75
  76   // Constructs the lifetime position which does not correspond to any
  77   // instruction.
  78   LifetimePosition() : value_(-1) {}
  79
  80   // Returns true if this lifetime positions corrensponds to some
  81   // instruction.
  82   bool IsValid() const { return value_ != -1; }
  83
  84   static inline LifetimePosition Invalid() { return LifetimePosition(); }
  85
  86   static inline LifetimePosition MaxPosition() {
  87     // We have to use this kind of getter instead of static member due to
  88     // crash bug in GDB.
  89     return LifetimePosition(kMaxInt);
  90   }
  91
  92  private:
  93   static const int kStep = 2;
  94
  95   // Code relies on kStep being a power of two.
  96   STATIC_ASSERT(IS_POWER_OF_TWO(kStep));
  97
  98   explicit LifetimePosition(int value) : value_(value) {}
  99
 100   int value_;
 101 };
 102
 103
 104 // Representation of the non-empty interval [start,end[.
 105 class UseInterval FINAL : public ZoneObject {
 106  public:
 107   UseInterval(LifetimePosition start, LifetimePosition end)
 108       : start_(start), end_(end), next_(nullptr) {
 109     DCHECK(start.Value() < end.Value());
 110   }
 111
 112   LifetimePosition start() const { return start_; }
 113   LifetimePosition end() const { return end_; }
 114   UseInterval* next() const { return next_; }
 115
 116   // Split this interval at the given position without effecting the
 117   // live range that owns it. The interval must contain the position.
 118   void SplitAt(LifetimePosition pos, Zone* zone);
 119
 120   // If this interval intersects with other return smallest position
 121   // that belongs to both of them.
 122   LifetimePosition Intersect(const UseInterval* other) const {
 123     if (other->start().Value() < start_.Value()) return other->Intersect(this);
 124     if (other->start().Value() < end_.Value()) return other->start();
 125     return LifetimePosition::Invalid();
 126   }
 127
 128   bool Contains(LifetimePosition point) const {
 129     return start_.Value() <= point.Value() && point.Value() < end_.Value();
 130   }
 131
 132   void set_start(LifetimePosition start) { start_ = start; }
 133   void set_next(UseInterval* next) { next_ = next; }
 134
 135   LifetimePosition start_;
 136   LifetimePosition end_;
 137   UseInterval* next_;
 138
 139  private:
 140   DISALLOW_COPY_AND_ASSIGN(UseInterval);
 141 };
 142
 143
 144 // Representation of a use position.
 145 class UsePosition FINAL : public ZoneObject {
 146  public:
 147   UsePosition(LifetimePosition pos, InstructionOperand* operand,
 148               InstructionOperand* hint);
 149
 150   InstructionOperand* operand() const { return operand_; }
 151   bool HasOperand() const { return operand_ != nullptr; }
 152
 153   InstructionOperand* hint() const { return hint_; }
 154   bool HasHint() const;
 155   bool RequiresRegister() const;
 156   bool RegisterIsBeneficial() const;
 157
 158   LifetimePosition pos() const { return pos_; }
 159   UsePosition* next() const { return next_; }
 160
 161   void set_next(UsePosition* next) { next_ = next; }
 162
 163   InstructionOperand* const operand_;
 164   InstructionOperand* const hint_;
 165   LifetimePosition const pos_;
 166   UsePosition* next_;
 167   bool requires_reg_ : 1;
 168   bool register_beneficial_ : 1;
 169
 170  private:
 171   DISALLOW_COPY_AND_ASSIGN(UsePosition);
 172 };
 173
 174 class SpillRange;
 175
 176
 177 // TODO(dcarney): remove this cache.
 178 class InstructionOperandCache FINAL : public ZoneObject {
 179  public:
 180   InstructionOperandCache();
 181
 182   InstructionOperand* RegisterOperand(int index) {
 183     DCHECK(index >= 0 &&
 184            index < static_cast<int>(arraysize(general_register_operands_)));
 185     return &general_register_operands_[index];
 186   }
 187   InstructionOperand* DoubleRegisterOperand(int index) {
 188     DCHECK(index >= 0 &&
 189            index < static_cast<int>(arraysize(double_register_operands_)));
 190     return &double_register_operands_[index];
 191   }
 192
 193  private:
 194   InstructionOperand
 195       general_register_operands_[RegisterConfiguration::kMaxGeneralRegisters];
 196   InstructionOperand
 197       double_register_operands_[RegisterConfiguration::kMaxDoubleRegisters];
 198
 199   DISALLOW_COPY_AND_ASSIGN(InstructionOperandCache);
 200 };
 201
 202
 203 // Representation of SSA values' live ranges as a collection of (continuous)
 204 // intervals over the instruction ordering.
 205 class LiveRange FINAL : public ZoneObject {
 206  public:
 207   static const int kInvalidAssignment = 0x7fffffff;
 208
 209   LiveRange(int id, Zone* zone);
 210
 211   UseInterval* first_interval() const { return first_interval_; }
 212   UsePosition* first_pos() const { return first_pos_; }
 213   LiveRange* parent() const { return parent_; }
 214   LiveRange* TopLevel() { return (parent_ == nullptr) ? this : parent_; }
 215   const LiveRange* TopLevel() const {
 216     return (parent_ == nullptr) ? this : parent_;
 217   }
 218   LiveRange* next() const { return next_; }
 219   bool IsChild() const { return parent() != nullptr; }
 220   int id() const { return id_; }
 221   bool IsFixed() const { return id_ < 0; }
 222   bool IsEmpty() const { return first_interval() == nullptr; }
 223   // TODO(dcarney): remove this.
 224   InstructionOperand* GetAssignedOperand(InstructionOperandCache* cache) const;
 225   InstructionOperand GetAssignedOperand() const;
 226   int assigned_register() const { return assigned_register_; }
 227   int spill_start_index() const { return spill_start_index_; }
 228   void set_assigned_register(int reg, InstructionOperandCache* cache);
 229   void MakeSpilled();
 230   bool is_phi() const { return is_phi_; }
 231   void set_is_phi(bool is_phi) { is_phi_ = is_phi; }
 232   bool is_non_loop_phi() const { return is_non_loop_phi_; }
 233   void set_is_non_loop_phi(bool is_non_loop_phi) {
 234     is_non_loop_phi_ = is_non_loop_phi;
 235   }
 236
 237   // Returns use position in this live range that follows both start
 238   // and last processed use position.
 239   // Modifies internal state of live range!
 240   UsePosition* NextUsePosition(LifetimePosition start);
 241
 242   // Returns use position for which register is required in this live
 243   // range and which follows both start and last processed use position
 244   // Modifies internal state of live range!
 245   UsePosition* NextRegisterPosition(LifetimePosition start);
 246
 247   // Returns use position for which register is beneficial in this live
 248   // range and which follows both start and last processed use position
 249   // Modifies internal state of live range!
 250   UsePosition* NextUsePositionRegisterIsBeneficial(LifetimePosition start);
 251
 252   // Returns use position for which register is beneficial in this live
 253   // range and which precedes start.
 254   UsePosition* PreviousUsePositionRegisterIsBeneficial(LifetimePosition start);
 255
 256   // Can this live range be spilled at this position.
 257   bool CanBeSpilled(LifetimePosition pos);
 258
 259   // Split this live range at the given position which must follow the start of
 260   // the range.
 261   // All uses following the given position will be moved from this
 262   // live range to the result live range.
 263   void SplitAt(LifetimePosition position, LiveRange* result, Zone* zone);
 264
 265   RegisterKind Kind() const { return kind_; }
 266   bool HasRegisterAssigned() const {
 267     return assigned_register_ != kInvalidAssignment;
 268   }
 269   bool IsSpilled() const { return spilled_; }
 270
 271   InstructionOperand* current_hint_operand() const {
 272     DCHECK(current_hint_operand_ == FirstHint());
 273     return current_hint_operand_;
 274   }
 275   InstructionOperand* FirstHint() const {
 276     UsePosition* pos = first_pos_;
 277     while (pos != nullptr && !pos->HasHint()) pos = pos->next();
 278     if (pos != nullptr) return pos->hint();
 279     return nullptr;
 280   }
 281
 282   LifetimePosition Start() const {
 283     DCHECK(!IsEmpty());
 284     return first_interval()->start();
 285   }
 286
 287   LifetimePosition End() const {
 288     DCHECK(!IsEmpty());
 289     return last_interval_->end();
 290   }
 291
 292   enum class SpillType { kNoSpillType, kSpillOperand, kSpillRange };
 293   SpillType spill_type() const { return spill_type_; }
 294   InstructionOperand* GetSpillOperand() const {
 295     return spill_type_ == SpillType::kSpillOperand ? spill_operand_ : nullptr;
 296   }
 297   SpillRange* GetSpillRange() const {
 298     return spill_type_ == SpillType::kSpillRange ? spill_range_ : nullptr;
 299   }
 300   bool HasNoSpillType() const { return spill_type_ == SpillType::kNoSpillType; }
 301   bool HasSpillOperand() const {
 302     return spill_type_ == SpillType::kSpillOperand;
 303   }
 304   bool HasSpillRange() const { return spill_type_ == SpillType::kSpillRange; }
 305
 306   void SpillAtDefinition(Zone* zone, int gap_index,
 307                          InstructionOperand* operand);
 308   void SetSpillOperand(InstructionOperand* operand);
 309   void SetSpillRange(SpillRange* spill_range);
 310   void CommitSpillOperand(InstructionOperand* operand);
 311   void CommitSpillsAtDefinition(InstructionSequence* sequence,
 312                                 InstructionOperand* operand);
 313
 314   void SetSpillStartIndex(int start) {
 315     spill_start_index_ = Min(start, spill_start_index_);
 316   }
 317
 318   bool ShouldBeAllocatedBefore(const LiveRange* other) const;
 319   bool CanCover(LifetimePosition position) const;
 320   bool Covers(LifetimePosition position);
 321   LifetimePosition FirstIntersection(LiveRange* other);
 322
 323   // Add a new interval or a new use position to this live range.
 324   void EnsureInterval(LifetimePosition start, LifetimePosition end, Zone* zone);
 325   void AddUseInterval(LifetimePosition start, LifetimePosition end, Zone* zone);
 326   void AddUsePosition(LifetimePosition pos, InstructionOperand* operand,
 327                       InstructionOperand* hint, Zone* zone);
 328
 329   // Shorten the most recently added interval by setting a new start.
 330   void ShortenTo(LifetimePosition start);
 331
 332 #ifdef DEBUG
 333   // True if target overlaps an existing interval.
 334   bool HasOverlap(UseInterval* target) const;
 335   void Verify() const;
 336 #endif
 337
 338  private:
 339   struct SpillAtDefinitionList;
 340
 341   void ConvertUsesToOperand(InstructionOperand* op);
 342   UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const;
 343   void AdvanceLastProcessedMarker(UseInterval* to_start_of,
 344                                   LifetimePosition but_not_past) const;
 345
 346   // TODO(dcarney): pack this structure better.
 347   int id_;
 348   bool spilled_;
 349   bool is_phi_;
 350   bool is_non_loop_phi_;
 351   RegisterKind kind_;
 352   int assigned_register_;
 353   UseInterval* last_interval_;
 354   UseInterval* first_interval_;
 355   UsePosition* first_pos_;
 356   LiveRange* parent_;
 357   LiveRange* next_;
 358   // This is used as a cache, it doesn't affect correctness.
 359   mutable UseInterval* current_interval_;
 360   UsePosition* last_processed_use_;
 361   // This is used as a cache, it's invalid outside of BuildLiveRanges.
 362   InstructionOperand* current_hint_operand_;
 363   int spill_start_index_;
 364   SpillType spill_type_;
 365   union {
 366     InstructionOperand* spill_operand_;
 367     SpillRange* spill_range_;
 368   };
 369   SpillAtDefinitionList* spills_at_definition_;
 370
 371   friend class RegisterAllocator;  // Assigns to kind_.
 372
 373   DISALLOW_COPY_AND_ASSIGN(LiveRange);
 374 };
 375
 376
 377 class SpillRange FINAL : public ZoneObject {
 378  public:
 379   SpillRange(LiveRange* range, Zone* zone);
 380
 381   UseInterval* interval() const { return use_interval_; }
 382   RegisterKind Kind() const { return live_ranges_[0]->Kind(); }
 383   bool IsEmpty() const { return live_ranges_.empty(); }
 384   bool TryMerge(SpillRange* other);
 385   void SetOperand(InstructionOperand* op);
 386
 387  private:
 388   LifetimePosition End() const { return end_position_; }
 389   ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; }
 390   bool IsIntersectingWith(SpillRange* other) const;
 391   // Merge intervals, making sure the use intervals are sorted
 392   void MergeDisjointIntervals(UseInterval* other);
 393
 394   ZoneVector<LiveRange*> live_ranges_;
 395   UseInterval* use_interval_;
 396   LifetimePosition end_position_;
 397
 398   DISALLOW_COPY_AND_ASSIGN(SpillRange);
 399 };
 400
 401
 402 class RegisterAllocator FINAL : public ZoneObject {
 403  public:
 404   explicit RegisterAllocator(const RegisterConfiguration* config,
 405                              Zone* local_zone, Frame* frame,
 406                              InstructionSequence* code,
 407                              const char* debug_name = nullptr);
 408
 409   const ZoneVector<LiveRange*>& live_ranges() const { return live_ranges_; }
 410   const ZoneVector<LiveRange*>& fixed_live_ranges() const {
 411     return fixed_live_ranges_;
 412   }
 413   const ZoneVector<LiveRange*>& fixed_double_live_ranges() const {
 414     return fixed_double_live_ranges_;
 415   }
 416   InstructionSequence* code() const { return code_; }
 417   // This zone is for datastructures only needed during register allocation.
 418   Zone* local_zone() const { return local_zone_; }
 419
 420   // Phase 1 : insert moves to account for fixed register operands.
 421   void MeetRegisterConstraints();
 422
 423   // Phase 2: deconstruct SSA by inserting moves in successors and the headers
 424   // of blocks containing phis.
 425   void ResolvePhis();
 426
 427   // Phase 3: compute liveness of all virtual register.
 428   void BuildLiveRanges();
 429   bool ExistsUseWithoutDefinition();
 430
 431   // Phase 4: compute register assignments.
 432   void AllocateGeneralRegisters();
 433   void AllocateDoubleRegisters();
 434
 435   // Phase 5: assign spill splots.
 436   void AssignSpillSlots();
 437
 438   // Phase 6: commit assignment.
 439   void CommitAssignment();
 440
 441   // Phase 7: compute values for pointer maps.
 442   void PopulatePointerMaps();  // TODO(titzer): rename to PopulateReferenceMaps.
 443
 444   // Phase 8: reconnect split ranges with moves.
 445   void ConnectRanges();
 446
 447   // Phase 9: insert moves to connect ranges across basic blocks.
 448   void ResolveControlFlow();
 449
 450  private:
 451   int GetVirtualRegister() { return code()->NextVirtualRegister(); }
 452
 453   // Checks whether the value of a given virtual register is a reference.
 454   // TODO(titzer): rename this to IsReference.
 455   bool HasTaggedValue(int virtual_register) const;
 456
 457   // Returns the register kind required by the given virtual register.
 458   RegisterKind RequiredRegisterKind(int virtual_register) const;
 459
 460   // This zone is for InstructionOperands and moves that live beyond register
 461   // allocation.
 462   Zone* code_zone() const { return code()->zone(); }
 463
 464   BitVector* assigned_registers() { return assigned_registers_; }
 465   BitVector* assigned_double_registers() { return assigned_double_registers_; }
 466
 467 #ifdef DEBUG
 468   void Verify() const;
 469 #endif
 470
 471   void AllocateRegisters();
 472   bool CanEagerlyResolveControlFlow(const InstructionBlock* block) const;
 473   bool SafePointsAreInOrder() const;
 474
 475   // Liveness analysis support.
 476   BitVector* ComputeLiveOut(const InstructionBlock* block);
 477   void AddInitialIntervals(const InstructionBlock* block, BitVector* live_out);
 478   bool IsOutputRegisterOf(Instruction* instr, int index);
 479   bool IsOutputDoubleRegisterOf(Instruction* instr, int index);
 480   void ProcessInstructions(const InstructionBlock* block, BitVector* live);
 481   void MeetRegisterConstraints(const InstructionBlock* block);
 482   void MeetConstraintsBetween(Instruction* first, Instruction* second,
 483                               int gap_index);
 484   void MeetRegisterConstraintsForLastInstructionInBlock(
 485       const InstructionBlock* block);
 486   void ResolvePhis(const InstructionBlock* block);
 487
 488   // Helper methods for building intervals.
 489   InstructionOperand* AllocateFixed(UnallocatedOperand* operand, int pos,
 490                                     bool is_tagged);
 491   LiveRange* LiveRangeFor(InstructionOperand* operand);
 492   void Define(LifetimePosition position, InstructionOperand* operand,
 493               InstructionOperand* hint);
 494   void Use(LifetimePosition block_start, LifetimePosition position,
 495            InstructionOperand* operand, InstructionOperand* hint);
 496   void AddGapMove(int index, GapInstruction::InnerPosition position,
 497                   InstructionOperand* from, InstructionOperand* to);
 498
 499   // Helper methods for updating the life range lists.
 500   void AddToActive(LiveRange* range);
 501   void AddToInactive(LiveRange* range);
 502   void AddToUnhandledSorted(LiveRange* range);
 503   void AddToUnhandledUnsorted(LiveRange* range);
 504   void SortUnhandled();
 505   bool UnhandledIsSorted();
 506   void ActiveToHandled(LiveRange* range);
 507   void ActiveToInactive(LiveRange* range);
 508   void InactiveToHandled(LiveRange* range);
 509   void InactiveToActive(LiveRange* range);
 510
 511   // Helper methods for allocating registers.
 512   bool TryReuseSpillForPhi(LiveRange* range);
 513   bool TryAllocateFreeReg(LiveRange* range);
 514   void AllocateBlockedReg(LiveRange* range);
 515   SpillRange* AssignSpillRangeToLiveRange(LiveRange* range);
 516
 517   // Live range splitting helpers.
 518
 519   // Split the given range at the given position.
 520   // If range starts at or after the given position then the
 521   // original range is returned.
 522   // Otherwise returns the live range that starts at pos and contains
 523   // all uses from the original range that follow pos. Uses at pos will
 524   // still be owned by the original range after splitting.
 525   LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos);
 526
 527   // Split the given range in a position from the interval [start, end].
 528   LiveRange* SplitBetween(LiveRange* range, LifetimePosition start,
 529                           LifetimePosition end);
 530
 531   // Find a lifetime position in the interval [start, end] which
 532   // is optimal for splitting: it is either header of the outermost
 533   // loop covered by this interval or the latest possible position.
 534   LifetimePosition FindOptimalSplitPos(LifetimePosition start,
 535                                        LifetimePosition end);
 536
 537   // Spill the given life range after position pos.
 538   void SpillAfter(LiveRange* range, LifetimePosition pos);
 539
 540   // Spill the given life range after position [start] and up to position [end].
 541   void SpillBetween(LiveRange* range, LifetimePosition start,
 542                     LifetimePosition end);
 543
 544   // Spill the given life range after position [start] and up to position [end].
 545   // Range is guaranteed to be spilled at least until position [until].
 546   void SpillBetweenUntil(LiveRange* range, LifetimePosition start,
 547                          LifetimePosition until, LifetimePosition end);
 548
 549   void SplitAndSpillIntersecting(LiveRange* range);
 550
 551   // If we are trying to spill a range inside the loop try to
 552   // hoist spill position out to the point just before the loop.
 553   LifetimePosition FindOptimalSpillingPos(LiveRange* range,
 554                                           LifetimePosition pos);
 555
 556   void Spill(LiveRange* range);
 557   bool IsBlockBoundary(LifetimePosition pos);
 558
 559   // Helper methods for resolving control flow.
 560   void ResolveControlFlow(const InstructionBlock* block,
 561                           InstructionOperand* cur_op,
 562                           const InstructionBlock* pred,
 563                           InstructionOperand* pred_op);
 564
 565   void SetLiveRangeAssignedRegister(LiveRange* range, int reg);
 566
 567   // Return parallel move that should be used to connect ranges split at the
 568   // given position.
 569   ParallelMove* GetConnectingParallelMove(LifetimePosition pos);
 570
 571   // Return the block which contains give lifetime position.
 572   const InstructionBlock* GetInstructionBlock(LifetimePosition pos);
 573
 574   // Helper methods for the fixed registers.
 575   int RegisterCount() const;
 576   static int FixedLiveRangeID(int index) { return -index - 1; }
 577   int FixedDoubleLiveRangeID(int index);
 578   LiveRange* FixedLiveRangeFor(int index);
 579   LiveRange* FixedDoubleLiveRangeFor(int index);
 580   LiveRange* LiveRangeFor(int index);
 581   GapInstruction* GetLastGap(const InstructionBlock* block);
 582
 583   const char* RegisterName(int allocation_index);
 584
 585   Instruction* InstructionAt(int index) { return code()->InstructionAt(index); }
 586
 587   Frame* frame() const { return frame_; }
 588   const char* debug_name() const { return debug_name_; }
 589   const RegisterConfiguration* config() const { return config_; }
 590   InstructionOperandCache* operand_cache() const { return operand_cache_; }
 591   ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; }
 592   ZoneVector<LiveRange*>& fixed_live_ranges() { return fixed_live_ranges_; }
 593   ZoneVector<LiveRange*>& fixed_double_live_ranges() {
 594     return fixed_double_live_ranges_;
 595   }
 596   ZoneVector<LiveRange*>& unhandled_live_ranges() {
 597     return unhandled_live_ranges_;
 598   }
 599   ZoneVector<LiveRange*>& active_live_ranges() { return active_live_ranges_; }
 600   ZoneVector<LiveRange*>& inactive_live_ranges() {
 601     return inactive_live_ranges_;
 602   }
 603   ZoneVector<SpillRange*>& spill_ranges() { return spill_ranges_; }
 604
 605   struct PhiMapValue {
 606     PhiMapValue(PhiInstruction* phi, const InstructionBlock* block)
 607         : phi(phi), block(block) {}
 608     PhiInstruction* const phi;
 609     const InstructionBlock* const block;
 610   };
 611   typedef ZoneMap<int, PhiMapValue> PhiMap;
 612
 613   Zone* const local_zone_;
 614   Frame* const frame_;
 615   InstructionSequence* const code_;
 616   const char* const debug_name_;
 617
 618   const RegisterConfiguration* config_;
 619   InstructionOperandCache* const operand_cache_;
 620   PhiMap phi_map_;
 621
 622   // During liveness analysis keep a mapping from block id to live_in sets
 623   // for blocks already analyzed.
 624   ZoneVector<BitVector*> live_in_sets_;
 625
 626   // Liveness analysis results.
 627   ZoneVector<LiveRange*> live_ranges_;
 628
 629   // Lists of live ranges
 630   ZoneVector<LiveRange*> fixed_live_ranges_;
 631   ZoneVector<LiveRange*> fixed_double_live_ranges_;
 632   ZoneVector<LiveRange*> unhandled_live_ranges_;
 633   ZoneVector<LiveRange*> active_live_ranges_;
 634   ZoneVector<LiveRange*> inactive_live_ranges_;
 635   ZoneVector<SpillRange*> spill_ranges_;
 636
 637   RegisterKind mode_;
 638   int num_registers_;
 639
 640   BitVector* assigned_registers_;
 641   BitVector* assigned_double_registers_;
 642
 643 #ifdef DEBUG
 644   LifetimePosition allocation_finger_;
 645 #endif
 646
 647   DISALLOW_COPY_AND_ASSIGN(RegisterAllocator);
 648 };
 649
 650 }  // namespace compiler
 651 }  // namespace internal
 652 }  // namespace v8
 653
 654 #endif  // V8_REGISTER_ALLOCATOR_H_