[turbofan] Deferred blocks splintering.

src/compiler/register-allocator.h

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_REGISTER_ALLOCATOR_H_
 #define V8_REGISTER_ALLOCATOR_H_
 
 #include "src/compiler/instruction.h"
 #include "src/ostreams.h"
 #include "src/zone-containers.h"
@@ skipping 255 matching lines @@
   void* hint_;
   UsePosition* next_;
   LifetimePosition const pos_;
   uint32_t flags_;
 
   DISALLOW_COPY_AND_ASSIGN(UsePosition);
 };
 
 
 class SpillRange;
-
+class RegisterAllocationData;
 
 // Representation of SSA values' live ranges as a collection of (continuous)
 // intervals over the instruction ordering.
 class LiveRange final : public ZoneObject {
  public:
   explicit LiveRange(int id, MachineType machine_type);
 
   UseInterval* first_interval() const { return first_interval_; }
   UsePosition* first_pos() const { return first_pos_; }
   LiveRange* parent() const { return parent_; }
@@ skipping 61 matching lines @@
       LifetimePosition start) const;
 
   // Can this live range be spilled at this position.
   bool CanBeSpilled(LifetimePosition pos) const;
 
   // Split this live range at the given position which must follow the start of
   // the range.
   // All uses following the given position will be moved from this
   // live range to the result live range.
   void SplitAt(LifetimePosition position, LiveRange* result, Zone* zone);
+  void Splinter(LifetimePosition start, LifetimePosition end, LiveRange* result,
+                Zone* zone);
+  void Merge(LiveRange* other, RegisterAllocationData* data);
 
   // Returns nullptr when no register is hinted, otherwise sets register_index.
   UsePosition* FirstHintPosition(int* register_index) const;
   UsePosition* FirstHintPosition() const {
     int register_index;
     return FirstHintPosition(&register_index);
   }
 
   UsePosition* current_hint_position() const {
     DCHECK(current_hint_position_ == FirstHintPosition());
     return current_hint_position_;
   }
 
   LifetimePosition Start() const {
     DCHECK(!IsEmpty());
     return first_interval()->start();
   }
 
   LifetimePosition End() const {
     DCHECK(!IsEmpty());
     return last_interval_->end();
   }
 
   enum class SpillType { kNoSpillType, kSpillOperand, kSpillRange };
   SpillType spill_type() const { return SpillTypeField::decode(bits_); }
   InstructionOperand* GetSpillOperand() const {
     DCHECK(spill_type() == SpillType::kSpillOperand);
     return spill_operand_;
   }
+
+  SpillRange* GetAllocatedSpillRange() const {
+    DCHECK(spill_type() != SpillType::kSpillOperand);
+    return spill_range_;
+  }
+
   SpillRange* GetSpillRange() const {
     DCHECK(spill_type() == SpillType::kSpillRange);
     return spill_range_;
   }
   bool HasNoSpillType() const {
     return spill_type() == SpillType::kNoSpillType;
   }
   bool HasSpillOperand() const {
     return spill_type() == SpillType::kSpillOperand;
   }
   bool HasSpillRange() const { return spill_type() == SpillType::kSpillRange; }
+  bool MayRequireSpillRange() const {
+    DCHECK(!IsChild() && !IsSplinter());
+    return !HasSpillOperand() && spill_range_ == nullptr;
+  }
+
   AllocatedOperand GetSpillRangeOperand() const;
 
   void SpillAtDefinition(Zone* zone, int gap_index,
                          InstructionOperand* operand);
   void SetSpillOperand(InstructionOperand* operand);
   void SetSpillRange(SpillRange* spill_range);
   void CommitSpillsAtDefinition(InstructionSequence* sequence,
                                 const InstructionOperand& operand,
                                 bool might_be_duplicated);
   // This must be applied on top level ranges.
@@ skipping 43 matching lines @@
   void set_weight(float weight) { weight_ = weight; }
 
   bool IsSpilledOnlyInDeferredBlocks() const {
     return spilled_in_deferred_block_;
   }
 
   static const int kInvalidSize = -1;
   static const float kInvalidWeight;
   static const float kMaxWeight;
 
- private:
+  LiveRange* splintered_from() const {
+    DCHECK(!IsChild());
+    return splintered_from_;
+  }
+  bool IsSplinter() const {
+    DCHECK(!IsChild());
+    return splintered_from_ != nullptr;
+  }
+
   void set_spill_type(SpillType value) {
     bits_ = SpillTypeField::update(bits_, value);
   }
 
+ private:
+  void AppendChild(LiveRange* other);
+  void UpdateParentForAllChildren(LiveRange* new_parent);
+  void UpdateSpillRangePostMerge(LiveRange* merged);
+
+  void SetSplinteredFrom(LiveRange* splinter_parent);
+
+
   void set_spilled(bool value) { bits_ = SpilledField::update(bits_, value); }
 
   UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const;
   void AdvanceLastProcessedMarker(UseInterval* to_start_of,
                                   LifetimePosition but_not_past) const;
 
+  LiveRange* GetLastChild();
+
   typedef BitField<bool, 0, 1> SpilledField;
   typedef BitField<bool, 1, 1> HasSlotUseField;
   typedef BitField<bool, 2, 1> IsPhiField;
   typedef BitField<bool, 3, 1> IsNonLoopPhiField;
   typedef BitField<SpillType, 4, 2> SpillTypeField;
   typedef BitField<int32_t, 6, 6> AssignedRegisterField;
   typedef BitField<MachineType, 12, 15> MachineTypeField;
 
   int id_;
   int spill_start_index_;
   uint32_t bits_;
   UseInterval* last_interval_;
   UseInterval* first_interval_;
   UsePosition* first_pos_;
   LiveRange* parent_;
   LiveRange* next_;
+  LiveRange* splintered_from_;
   union {
     // Correct value determined by spill_type()
     InstructionOperand* spill_operand_;
     SpillRange* spill_range_;
   };
   SpillAtDefinitionList* spills_at_definition_;
   // This is used as a cache, it doesn't affect correctness.
   mutable UseInterval* current_interval_;
   // This is used as a cache, it doesn't affect correctness.
   mutable UsePosition* last_processed_use_;
@@ skipping 38 matching lines @@
   bool TryMerge(SpillRange* other);
 
   void set_assigned_slot(int index) {
     DCHECK_EQ(kUnassignedSlot, assigned_slot_);
     assigned_slot_ = index;
   }
   int assigned_slot() {
     DCHECK_NE(kUnassignedSlot, assigned_slot_);
     return assigned_slot_;
   }
+  const ZoneVector<LiveRange*>& live_ranges() const { return live_ranges_; }
+  ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; }
+  int byte_width() const { return byte_width_; }
+  RegisterKind kind() const { return kind_; }
 
  private:
   LifetimePosition End() const { return end_position_; }
-  ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; }
   bool IsIntersectingWith(SpillRange* other) const;
   // Merge intervals, making sure the use intervals are sorted
   void MergeDisjointIntervals(UseInterval* other);
 
   ZoneVector<LiveRange*> live_ranges_;
   UseInterval* use_interval_;
   LifetimePosition end_position_;
   int assigned_slot_;
+  int byte_width_;
+  RegisterKind kind_;
 
   DISALLOW_COPY_AND_ASSIGN(SpillRange);
 };
 
 
 class RegisterAllocationData final : public ZoneObject {
  public:
   class PhiMapValue : public ZoneObject {
    public:
     PhiMapValue(PhiInstruction* phi, const InstructionBlock* block, Zone* zone);
@@ skipping 37 matching lines @@
     return fixed_live_ranges_;
   }
   ZoneVector<LiveRange*>& fixed_live_ranges() { return fixed_live_ranges_; }
   ZoneVector<LiveRange*>& fixed_double_live_ranges() {
     return fixed_double_live_ranges_;
   }
   const ZoneVector<LiveRange*>& fixed_double_live_ranges() const {
     return fixed_double_live_ranges_;
   }
   ZoneVector<BitVector*>& live_in_sets() { return live_in_sets_; }
-  ZoneVector<SpillRange*>& spill_ranges() { return spill_ranges_; }
+  ZoneSet<SpillRange*>& spill_ranges() { return spill_ranges_; }
   DelayedReferences& delayed_references() { return delayed_references_; }
   InstructionSequence* code() const { return code_; }
   // This zone is for datastructures only needed during register allocation
   // phases.
   Zone* allocation_zone() const { return allocation_zone_; }
   // This zone is for InstructionOperands and moves that live beyond register
   // allocation.
   Zone* code_zone() const { return code()->zone(); }
   Frame* frame() const { return frame_; }
   const char* debug_name() const { return debug_name_; }
   const RegisterConfiguration* config() const { return config_; }
 
   MachineType MachineTypeFor(int virtual_register);
 
   LiveRange* LiveRangeFor(int index);
   // Creates a new live range.
   LiveRange* NewLiveRange(int index, MachineType machine_type);
+  LiveRange* NextLiveRange(MachineType machine_type);
   LiveRange* NewChildRangeFor(LiveRange* range);
 
   SpillRange* AssignSpillRangeToLiveRange(LiveRange* range);
+  SpillRange* CreateSpillRangeForLiveRange(LiveRange* range);
 
   MoveOperands* AddGapMove(int index, Instruction::GapPosition position,
                            const InstructionOperand& from,
                            const InstructionOperand& to);
 
   bool IsReference(int virtual_register) const {
     return code()->IsReference(virtual_register);
   }
 
   bool ExistsUseWithoutDefinition();
 
   void MarkAllocated(RegisterKind kind, int index);
 
   PhiMapValue* InitializePhiMap(const InstructionBlock* block,
                                 PhiInstruction* phi);
   PhiMapValue* GetPhiMapValueFor(int virtual_register);
   bool IsBlockBoundary(LifetimePosition pos) const;
 
   void Print(const InstructionSequence* instructionSequence);
   void Print(const Instruction* instruction);
   void Print(const LiveRange* range, bool with_children = false);
   void Print(const InstructionOperand& op);
   void Print(const MoveOperands* move);
+  void Print(const SpillRange* spill_range);
 
  private:
   Zone* const allocation_zone_;
   Frame* const frame_;
   InstructionSequence* const code_;
   const char* const debug_name_;
   const RegisterConfiguration* const config_;
   PhiMap phi_map_;
   ZoneVector<BitVector*> live_in_sets_;
   ZoneVector<LiveRange*> live_ranges_;
   ZoneVector<LiveRange*> fixed_live_ranges_;
   ZoneVector<LiveRange*> fixed_double_live_ranges_;
-  ZoneVector<SpillRange*> spill_ranges_;
+  ZoneSet<SpillRange*> spill_ranges_;
   DelayedReferences delayed_references_;
   BitVector* assigned_registers_;
   BitVector* assigned_double_registers_;
   int virtual_register_count_;
 
   DISALLOW_COPY_AND_ASSIGN(RegisterAllocationData);
 };
 
 
 class ConstraintBuilder final : public ZoneObject {
@@ skipping 32 matching lines @@
   DISALLOW_COPY_AND_ASSIGN(ConstraintBuilder);
 };
 
 
 class LiveRangeBuilder final : public ZoneObject {
  public:
   explicit LiveRangeBuilder(RegisterAllocationData* data, Zone* local_zone);
 
   // Phase 3: compute liveness of all virtual register.
   void BuildLiveRanges();
+  static BitVector* ComputeLiveOut(const InstructionBlock* block,
+                                   RegisterAllocationData* data);
 
  private:
   RegisterAllocationData* data() const { return data_; }
   InstructionSequence* code() const { return data()->code(); }
   Zone* allocation_zone() const { return data()->allocation_zone(); }
   Zone* code_zone() const { return code()->zone(); }
   const RegisterConfiguration* config() const { return data()->config(); }
   ZoneVector<BitVector*>& live_in_sets() const {
     return data()->live_in_sets();
   }
 
   LiveRange* LiveRangeFor(int index) { return data()->LiveRangeFor(index); }
 
   void Verify() const;
 
   // Liveness analysis support.
-  BitVector* ComputeLiveOut(const InstructionBlock* block);
   void AddInitialIntervals(const InstructionBlock* block, BitVector* live_out);
   void ProcessInstructions(const InstructionBlock* block, BitVector* live);
   void ProcessPhis(const InstructionBlock* block, BitVector* live);
   void ProcessLoopHeader(const InstructionBlock* block, BitVector* live);
 
   static int FixedLiveRangeID(int index) { return -index - 1; }
   int FixedDoubleLiveRangeID(int index);
   LiveRange* FixedLiveRangeFor(int index);
   LiveRange* FixedDoubleLiveRangeFor(int index);
 
@@ skipping 227 matching lines @@
   RegisterAllocationData* const data_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRangeConnector);
 };
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_REGISTER_ALLOCATOR_H_