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