src/v8/src/lithium-allocator.h

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