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