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 // Representation of SSA values' live ranges as a collection of (continuous)
 177 // intervals over the instruction ordering.
 178 class LiveRange FINAL : public ZoneObject {
 179  public:
 180   static const int kInvalidAssignment = 0x7fffffff;
 181
 182   LiveRange(int id, Zone* zone);
 183
 184   UseInterval* first_interval() const { return first_interval_; }
 185   UsePosition* first_pos() const { return first_pos_; }
 186   LiveRange* parent() const { return parent_; }
 187   LiveRange* TopLevel() { return (parent_ == nullptr) ? this : parent_; }
 188   const LiveRange* TopLevel() const {
 189     return (parent_ == nullptr) ? this : parent_;
 190   }
 191   LiveRange* next() const { return next_; }
 192   bool IsChild() const { return parent() != nullptr; }
 193   int id() const { return id_; }
 194   bool IsFixed() const { return id_ < 0; }
 195   bool IsEmpty() const { return first_interval() == nullptr; }
 196   InstructionOperand* CreateAssignedOperand(Zone* zone) const;
 197   int assigned_register() const { return assigned_register_; }
 198   int spill_start_index() const { return spill_start_index_; }
 199   void set_assigned_register(int reg, Zone* zone);
 200   void MakeSpilled();
 201   bool is_phi() const { return is_phi_; }
 202   void set_is_phi(bool is_phi) { is_phi_ = is_phi; }
 203   bool is_non_loop_phi() const { return is_non_loop_phi_; }
 204   void set_is_non_loop_phi(bool is_non_loop_phi) {
 205     is_non_loop_phi_ = is_non_loop_phi;
 206   }
 207
 208   // Returns use position in this live range that follows both start
 209   // and last processed use position.
 210   // Modifies internal state of live range!
 211   UsePosition* NextUsePosition(LifetimePosition start);
 212
 213   // Returns use position for which register is required in this live
 214   // range and which follows both start and last processed use position
 215   // Modifies internal state of live range!
 216   UsePosition* NextRegisterPosition(LifetimePosition start);
 217
 218   // Returns use position for which register is beneficial in this live
 219   // range and which follows both start and last processed use position
 220   // Modifies internal state of live range!
 221   UsePosition* NextUsePositionRegisterIsBeneficial(LifetimePosition start);
 222
 223   // Returns use position for which register is beneficial in this live
 224   // range and which precedes start.
 225   UsePosition* PreviousUsePositionRegisterIsBeneficial(LifetimePosition start);
 226
 227   // Can this live range be spilled at this position.
 228   bool CanBeSpilled(LifetimePosition pos);
 229
 230   // Split this live range at the given position which must follow the start of
 231   // the range.
 232   // All uses following the given position will be moved from this
 233   // live range to the result live range.
 234   void SplitAt(LifetimePosition position, LiveRange* result, Zone* zone);
 235
 236   RegisterKind Kind() const { return kind_; }
 237   bool HasRegisterAssigned() const {
 238     return assigned_register_ != kInvalidAssignment;
 239   }
 240   bool IsSpilled() const { return spilled_; }
 241
 242   InstructionOperand* current_hint_operand() const {
 243     DCHECK(current_hint_operand_ == FirstHint());
 244     return current_hint_operand_;
 245   }
 246   InstructionOperand* FirstHint() const {
 247     UsePosition* pos = first_pos_;
 248     while (pos != nullptr && !pos->HasHint()) pos = pos->next();
 249     if (pos != nullptr) return pos->hint();
 250     return nullptr;
 251   }
 252
 253   LifetimePosition Start() const {
 254     DCHECK(!IsEmpty());
 255     return first_interval()->start();
 256   }
 257
 258   LifetimePosition End() const {
 259     DCHECK(!IsEmpty());
 260     return last_interval_->end();
 261   }
 262
 263   enum class SpillType { kNoSpillType, kSpillOperand, kSpillRange };
 264   SpillType spill_type() const { return spill_type_; }
 265   InstructionOperand* GetSpillOperand() const {
 266     return spill_type_ == SpillType::kSpillOperand ? spill_operand_ : nullptr;
 267   }
 268   SpillRange* GetSpillRange() const {
 269     return spill_type_ == SpillType::kSpillRange ? spill_range_ : nullptr;
 270   }
 271   bool HasNoSpillType() const { return spill_type_ == SpillType::kNoSpillType; }
 272   bool HasSpillOperand() const {
 273     return spill_type_ == SpillType::kSpillOperand;
 274   }
 275   bool HasSpillRange() const { return spill_type_ == SpillType::kSpillRange; }
 276
 277   void SpillAtDefinition(Zone* zone, int gap_index,
 278                          InstructionOperand* operand);
 279   void SetSpillOperand(InstructionOperand* operand);
 280   void SetSpillRange(SpillRange* spill_range);
 281   void CommitSpillOperand(InstructionOperand* operand);
 282   void CommitSpillsAtDefinition(InstructionSequence* sequence,
 283                                 InstructionOperand* operand);
 284
 285   void SetSpillStartIndex(int start) {
 286     spill_start_index_ = Min(start, spill_start_index_);
 287   }
 288
 289   bool ShouldBeAllocatedBefore(const LiveRange* other) const;
 290   bool CanCover(LifetimePosition position) const;
 291   bool Covers(LifetimePosition position);
 292   LifetimePosition FirstIntersection(LiveRange* other);
 293
 294   // Add a new interval or a new use position to this live range.
 295   void EnsureInterval(LifetimePosition start, LifetimePosition end, Zone* zone);
 296   void AddUseInterval(LifetimePosition start, LifetimePosition end, Zone* zone);
 297   void AddUsePosition(LifetimePosition pos, InstructionOperand* operand,
 298                       InstructionOperand* hint, Zone* zone);
 299
 300   // Shorten the most recently added interval by setting a new start.
 301   void ShortenTo(LifetimePosition start);
 302
 303 #ifdef DEBUG
 304   // True if target overlaps an existing interval.
 305   bool HasOverlap(UseInterval* target) const;
 306   void Verify() const;
 307 #endif
 308
 309  private:
 310   struct SpillAtDefinitionList;
 311
 312   void ConvertUsesToOperand(InstructionOperand* op);
 313   UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const;
 314   void AdvanceLastProcessedMarker(UseInterval* to_start_of,
 315                                   LifetimePosition but_not_past) const;
 316
 317   // TODO(dcarney): pack this structure better.
 318   int id_;
 319   bool spilled_;
 320   bool is_phi_;
 321   bool is_non_loop_phi_;
 322   RegisterKind kind_;
 323   int assigned_register_;
 324   UseInterval* last_interval_;
 325   UseInterval* first_interval_;
 326   UsePosition* first_pos_;
 327   LiveRange* parent_;
 328   LiveRange* next_;
 329   // This is used as a cache, it doesn't affect correctness.
 330   mutable UseInterval* current_interval_;
 331   UsePosition* last_processed_use_;
 332   // This is used as a cache, it's invalid outside of BuildLiveRanges.
 333   InstructionOperand* current_hint_operand_;
 334   int spill_start_index_;
 335   SpillType spill_type_;
 336   union {
 337     InstructionOperand* spill_operand_;
 338     SpillRange* spill_range_;
 339   };
 340   SpillAtDefinitionList* spills_at_definition_;
 341
 342   friend class RegisterAllocator;  // Assigns to kind_.
 343
 344   DISALLOW_COPY_AND_ASSIGN(LiveRange);
 345 };
 346
 347
 348 class SpillRange FINAL : public ZoneObject {
 349  public:
 350   SpillRange(LiveRange* range, Zone* zone);
 351
 352   UseInterval* interval() const { return use_interval_; }
 353   RegisterKind Kind() const { return live_ranges_[0]->Kind(); }
 354   bool IsEmpty() const { return live_ranges_.empty(); }
 355   bool TryMerge(SpillRange* other);
 356   void SetOperand(InstructionOperand* op);
 357
 358  private:
 359   LifetimePosition End() const { return end_position_; }
 360   ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; }
 361   bool IsIntersectingWith(SpillRange* other) const;
 362   // Merge intervals, making sure the use intervals are sorted
 363   void MergeDisjointIntervals(UseInterval* other);
 364
 365   ZoneVector<LiveRange*> live_ranges_;
 366   UseInterval* use_interval_;
 367   LifetimePosition end_position_;
 368
 369   DISALLOW_COPY_AND_ASSIGN(SpillRange);
 370 };
 371
 372
 373 class RegisterAllocator FINAL : public ZoneObject {
 374  public:
 375   explicit RegisterAllocator(const RegisterConfiguration* config,
 376                              Zone* local_zone, Frame* frame,
 377                              InstructionSequence* code,
 378                              const char* debug_name = nullptr);
 379
 380   bool AllocationOk() { return allocation_ok_; }
 381
 382   const ZoneVector<LiveRange*>& live_ranges() const { return live_ranges_; }
 383   const ZoneVector<LiveRange*>& fixed_live_ranges() const {
 384     return fixed_live_ranges_;
 385   }
 386   const ZoneVector<LiveRange*>& fixed_double_live_ranges() const {
 387     return fixed_double_live_ranges_;
 388   }
 389   InstructionSequence* code() const { return code_; }
 390   // This zone is for datastructures only needed during register allocation.
 391   Zone* local_zone() const { return local_zone_; }
 392
 393   // Phase 1 : insert moves to account for fixed register operands.
 394   void MeetRegisterConstraints();
 395
 396   // Phase 2: deconstruct SSA by inserting moves in successors and the headers
 397   // of blocks containing phis.
 398   void ResolvePhis();
 399
 400   // Phase 3: compute liveness of all virtual register.
 401   void BuildLiveRanges();
 402   bool ExistsUseWithoutDefinition();
 403
 404   // Phase 4: compute register assignments.
 405   void AllocateGeneralRegisters();
 406   void AllocateDoubleRegisters();
 407
 408   // Phase 5: reassign spill splots for maximal reuse.
 409   void ReuseSpillSlots();
 410
 411   // Phase 6: commit assignment.
 412   void CommitAssignment();
 413
 414   // Phase 7: compute values for pointer maps.
 415   void PopulatePointerMaps();  // TODO(titzer): rename to PopulateReferenceMaps.
 416
 417   // Phase 8: reconnect split ranges with moves.
 418   void ConnectRanges();
 419
 420   // Phase 9: insert moves to connect ranges across basic blocks.
 421   void ResolveControlFlow();
 422
 423  private:
 424   int GetVirtualRegister() {
 425     int vreg = code()->NextVirtualRegister();
 426     if (vreg >= UnallocatedOperand::kMaxVirtualRegisters) {
 427       allocation_ok_ = false;
 428       // Maintain the invariant that we return something below the maximum.
 429       return 0;
 430     }
 431     return vreg;
 432   }
 433
 434   // Checks whether the value of a given virtual register is a reference.
 435   // TODO(titzer): rename this to IsReference.
 436   bool HasTaggedValue(int virtual_register) const;
 437
 438   // Returns the register kind required by the given virtual register.
 439   RegisterKind RequiredRegisterKind(int virtual_register) const;
 440
 441   // This zone is for InstructionOperands and moves that live beyond register
 442   // allocation.
 443   Zone* code_zone() const { return code()->zone(); }
 444
 445   BitVector* assigned_registers() { return assigned_registers_; }
 446   BitVector* assigned_double_registers() { return assigned_double_registers_; }
 447
 448 #ifdef DEBUG
 449   void Verify() const;
 450 #endif
 451
 452   void AllocateRegisters();
 453   bool CanEagerlyResolveControlFlow(const InstructionBlock* block) const;
 454   bool SafePointsAreInOrder() const;
 455
 456   // Liveness analysis support.
 457   BitVector* ComputeLiveOut(const InstructionBlock* block);
 458   void AddInitialIntervals(const InstructionBlock* block, BitVector* live_out);
 459   bool IsOutputRegisterOf(Instruction* instr, int index);
 460   bool IsOutputDoubleRegisterOf(Instruction* instr, int index);
 461   void ProcessInstructions(const InstructionBlock* block, BitVector* live);
 462   void MeetRegisterConstraints(const InstructionBlock* block);
 463   void MeetConstraintsBetween(Instruction* first, Instruction* second,
 464                               int gap_index);
 465   void MeetRegisterConstraintsForLastInstructionInBlock(
 466       const InstructionBlock* block);
 467   void ResolvePhis(const InstructionBlock* block);
 468
 469   // Helper methods for building intervals.
 470   InstructionOperand* AllocateFixed(UnallocatedOperand* operand, int pos,
 471                                     bool is_tagged);
 472   LiveRange* LiveRangeFor(InstructionOperand* operand);
 473   void Define(LifetimePosition position, InstructionOperand* operand,
 474               InstructionOperand* hint);
 475   void Use(LifetimePosition block_start, LifetimePosition position,
 476            InstructionOperand* operand, InstructionOperand* hint);
 477   void AddGapMove(int index, GapInstruction::InnerPosition position,
 478                   InstructionOperand* from, InstructionOperand* to);
 479
 480   // Helper methods for updating the life range lists.
 481   void AddToActive(LiveRange* range);
 482   void AddToInactive(LiveRange* range);
 483   void AddToUnhandledSorted(LiveRange* range);
 484   void AddToUnhandledUnsorted(LiveRange* range);
 485   void SortUnhandled();
 486   bool UnhandledIsSorted();
 487   void ActiveToHandled(LiveRange* range);
 488   void ActiveToInactive(LiveRange* range);
 489   void InactiveToHandled(LiveRange* range);
 490   void InactiveToActive(LiveRange* range);
 491
 492   // Helper methods for allocating registers.
 493   bool TryReuseSpillForPhi(LiveRange* range);
 494   bool TryAllocateFreeReg(LiveRange* range);
 495   void AllocateBlockedReg(LiveRange* range);
 496   SpillRange* AssignSpillRangeToLiveRange(LiveRange* range);
 497   void FreeSpillSlot(LiveRange* range);
 498   InstructionOperand* TryReuseSpillSlot(LiveRange* range);
 499
 500   // Live range splitting helpers.
 501
 502   // Split the given range at the given position.
 503   // If range starts at or after the given position then the
 504   // original range is returned.
 505   // Otherwise returns the live range that starts at pos and contains
 506   // all uses from the original range that follow pos. Uses at pos will
 507   // still be owned by the original range after splitting.
 508   LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos);
 509
 510   // Split the given range in a position from the interval [start, end].
 511   LiveRange* SplitBetween(LiveRange* range, LifetimePosition start,
 512                           LifetimePosition end);
 513
 514   // Find a lifetime position in the interval [start, end] which
 515   // is optimal for splitting: it is either header of the outermost
 516   // loop covered by this interval or the latest possible position.
 517   LifetimePosition FindOptimalSplitPos(LifetimePosition start,
 518                                        LifetimePosition end);
 519
 520   // Spill the given life range after position pos.
 521   void SpillAfter(LiveRange* range, LifetimePosition pos);
 522
 523   // Spill the given life range after position [start] and up to position [end].
 524   void SpillBetween(LiveRange* range, LifetimePosition start,
 525                     LifetimePosition end);
 526
 527   // Spill the given life range after position [start] and up to position [end].
 528   // Range is guaranteed to be spilled at least until position [until].
 529   void SpillBetweenUntil(LiveRange* range, LifetimePosition start,
 530                          LifetimePosition until, LifetimePosition end);
 531
 532   void SplitAndSpillIntersecting(LiveRange* range);
 533
 534   // If we are trying to spill a range inside the loop try to
 535   // hoist spill position out to the point just before the loop.
 536   LifetimePosition FindOptimalSpillingPos(LiveRange* range,
 537                                           LifetimePosition pos);
 538
 539   void Spill(LiveRange* range);
 540   bool IsBlockBoundary(LifetimePosition pos);
 541
 542   // Helper methods for resolving control flow.
 543   void ResolveControlFlow(const InstructionBlock* block,
 544                           InstructionOperand* cur_op,
 545                           const InstructionBlock* pred,
 546                           InstructionOperand* pred_op);
 547
 548   void SetLiveRangeAssignedRegister(LiveRange* range, int reg);
 549
 550   // Return parallel move that should be used to connect ranges split at the
 551   // given position.
 552   ParallelMove* GetConnectingParallelMove(LifetimePosition pos);
 553
 554   // Return the block which contains give lifetime position.
 555   const InstructionBlock* GetInstructionBlock(LifetimePosition pos);
 556
 557   // Helper methods for the fixed registers.
 558   int RegisterCount() const;
 559   static int FixedLiveRangeID(int index) { return -index - 1; }
 560   int FixedDoubleLiveRangeID(int index);
 561   LiveRange* FixedLiveRangeFor(int index);
 562   LiveRange* FixedDoubleLiveRangeFor(int index);
 563   LiveRange* LiveRangeFor(int index);
 564   GapInstruction* GetLastGap(const InstructionBlock* block);
 565
 566   const char* RegisterName(int allocation_index);
 567
 568   Instruction* InstructionAt(int index) { return code()->InstructionAt(index); }
 569
 570   Frame* frame() const { return frame_; }
 571   const char* debug_name() const { return debug_name_; }
 572   const RegisterConfiguration* config() const { return config_; }
 573   ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; }
 574   ZoneVector<LiveRange*>& fixed_live_ranges() { return fixed_live_ranges_; }
 575   ZoneVector<LiveRange*>& fixed_double_live_ranges() {
 576     return fixed_double_live_ranges_;
 577   }
 578   ZoneVector<LiveRange*>& unhandled_live_ranges() {
 579     return unhandled_live_ranges_;
 580   }
 581   ZoneVector<LiveRange*>& active_live_ranges() { return active_live_ranges_; }
 582   ZoneVector<LiveRange*>& inactive_live_ranges() {
 583     return inactive_live_ranges_;
 584   }
 585   ZoneVector<LiveRange*>& reusable_slots() { return reusable_slots_; }
 586   ZoneVector<SpillRange*>& spill_ranges() { return spill_ranges_; }
 587
 588   struct PhiMapValue {
 589     PhiMapValue(PhiInstruction* phi, const InstructionBlock* block)
 590         : phi(phi), block(block) {}
 591     PhiInstruction* const phi;
 592     const InstructionBlock* const block;
 593   };
 594   typedef std::map<int, PhiMapValue, std::less<int>,
 595                    zone_allocator<std::pair<int, PhiMapValue>>> PhiMap;
 596
 597   Zone* const local_zone_;
 598   Frame* const frame_;
 599   InstructionSequence* const code_;
 600   const char* const debug_name_;
 601
 602   const RegisterConfiguration* config_;
 603
 604   PhiMap phi_map_;
 605
 606   // During liveness analysis keep a mapping from block id to live_in sets
 607   // for blocks already analyzed.
 608   ZoneVector<BitVector*> live_in_sets_;
 609
 610   // Liveness analysis results.
 611   ZoneVector<LiveRange*> live_ranges_;
 612
 613   // Lists of live ranges
 614   ZoneVector<LiveRange*> fixed_live_ranges_;
 615   ZoneVector<LiveRange*> fixed_double_live_ranges_;
 616   ZoneVector<LiveRange*> unhandled_live_ranges_;
 617   ZoneVector<LiveRange*> active_live_ranges_;
 618   ZoneVector<LiveRange*> inactive_live_ranges_;
 619   ZoneVector<LiveRange*> reusable_slots_;
 620   ZoneVector<SpillRange*> spill_ranges_;
 621
 622   RegisterKind mode_;
 623   int num_registers_;
 624
 625   BitVector* assigned_registers_;
 626   BitVector* assigned_double_registers_;
 627
 628   // Indicates success or failure during register allocation.
 629   bool allocation_ok_;
 630
 631 #ifdef DEBUG
 632   LifetimePosition allocation_finger_;
 633 #endif
 634
 635   DISALLOW_COPY_AND_ASSIGN(RegisterAllocator);
 636 };
 637
 638 }  // namespace compiler
 639 }  // namespace internal
 640 }  // namespace v8
 641
 642 #endif  // V8_REGISTER_ALLOCATOR_H_