[turbofan] remove hint aliasing

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/zone-containers.h"
 
@@ skipping 178 matching lines @@
   LifetimePosition end_;
   UseInterval* next_;
 
   DISALLOW_COPY_AND_ASSIGN(UseInterval);
 };
 
 
 enum class UsePositionType : uint8_t { kAny, kRequiresRegister, kRequiresSlot };
 
 
+enum class UsePositionHintType : uint8_t {
+  kNone,
+  kOperand,
+  kUsePos,
+  kPhi,
+  kUnresolved
+};
+
+
+static const int32_t kUnassignedRegister =
+    RegisterConfiguration::kMaxGeneralRegisters;
+
+
+static_assert(kUnassignedRegister <= RegisterConfiguration::kMaxDoubleRegisters,
+              "kUnassignedRegister too small");
+
+
 // Representation of a use position.
 class UsePosition final : public ZoneObject {
  public:
-  UsePosition(LifetimePosition pos, InstructionOperand* operand,
-              InstructionOperand* hint);
+  UsePosition(LifetimePosition pos, InstructionOperand* operand, void* hint,
+              UsePositionHintType hint_type);
 
   InstructionOperand* operand() const { return operand_; }
   bool HasOperand() const { return operand_ != nullptr; }
 
-  InstructionOperand* hint() const { return hint_; }
-  bool HasHint() const;
   bool RegisterIsBeneficial() const {
     return RegisterBeneficialField::decode(flags_);
   }
   UsePositionType type() const { return TypeField::decode(flags_); }
+  void set_type(UsePositionType type, bool register_beneficial);
 
   LifetimePosition pos() const { return pos_; }
+
   UsePosition* next() const { return next_; }
+  void set_next(UsePosition* next) { next_ = next; }
 
-  void set_next(UsePosition* next) { next_ = next; }
-  void set_type(UsePositionType type, bool register_beneficial);
+  // For hinting only.
+  void set_assigned_register(int register_index) {
+    flags_ = AssignedRegisterField::update(flags_, register_index);
+  }
+
+  UsePositionHintType hint_type() const {
+    return HintTypeField::decode(flags_);
+  }
+  bool HasHint() const;
+  bool HintRegister(int* register_index) const;
+  void ResolveHint(UsePosition* use_pos);
+  bool IsResolved() const {
+    return hint_type() != UsePositionHintType::kUnresolved;
+  }
+  static UsePositionHintType HintTypeForOperand(const InstructionOperand& op);
 
  private:
-  typedef BitField8<UsePositionType, 0, 2> TypeField;
-  typedef BitField8<bool, 2, 1> RegisterBeneficialField;
+  typedef BitField<UsePositionType, 0, 2> TypeField;
+  typedef BitField<UsePositionHintType, 2, 3> HintTypeField;
+  typedef BitField<bool, 5, 1> RegisterBeneficialField;
+  typedef BitField<int32_t, 6, 6> AssignedRegisterField;
 
   InstructionOperand* const operand_;
-  InstructionOperand* const hint_;
+  void* hint_;
+  UsePosition* next_;
   LifetimePosition const pos_;
-  UsePosition* next_;
-  uint8_t flags_;
+  uint32_t flags_;
 
   DISALLOW_COPY_AND_ASSIGN(UsePosition);
 };
 
+
 class SpillRange;
 
 
 // Representation of SSA values' live ranges as a collection of (continuous)
 // intervals over the instruction ordering.
 class LiveRange final : public ZoneObject {
  public:
-  static const int kInvalidAssignment = 0x7fffffff;
-
   explicit LiveRange(int id);
 
   UseInterval* first_interval() const { return first_interval_; }
   UsePosition* first_pos() const { return first_pos_; }
   LiveRange* parent() const { return parent_; }
   LiveRange* TopLevel() { return (parent_ == nullptr) ? this : parent_; }
   const LiveRange* TopLevel() const {
     return (parent_ == nullptr) ? this : parent_;
   }
   LiveRange* next() const { return next_; }
   bool IsChild() const { return parent() != nullptr; }
   int id() const { return id_; }
   bool IsFixed() const { return id_ < 0; }
   bool IsEmpty() const { return first_interval() == nullptr; }
   InstructionOperand GetAssignedOperand() const;
   int assigned_register() const { return assigned_register_; }
   int spill_start_index() const { return spill_start_index_; }
   void set_assigned_register(int reg);
+  void UnsetAssignedRegister();
   void MakeSpilled();
   bool is_phi() const { return is_phi_; }
   void set_is_phi(bool is_phi) { is_phi_ = is_phi; }
   bool is_non_loop_phi() const { return is_non_loop_phi_; }
   void set_is_non_loop_phi(bool is_non_loop_phi) {
     is_non_loop_phi_ = is_non_loop_phi;
   }
   bool has_slot_use() const { return has_slot_use_; }
   void set_has_slot_use(bool has_slot_use) { has_slot_use_ = has_slot_use; }
 
@@ skipping 19 matching lines @@
   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);
 
   RegisterKind Kind() const { return kind_; }
   bool HasRegisterAssigned() const {
-    return assigned_register_ != kInvalidAssignment;
+    return assigned_register_ != kUnassignedRegister;
   }
   bool IsSpilled() const { return spilled_; }
 
-  InstructionOperand* current_hint_operand() const {
-    DCHECK(current_hint_operand_ == FirstHint());
-    return current_hint_operand_;
+  // 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);
   }
-  InstructionOperand* FirstHint() const {
-    UsePosition* pos = first_pos_;
-    while (pos != nullptr && !pos->HasHint()) pos = pos->next();
-    if (pos != nullptr) return pos->hint();
-    return nullptr;
+
+  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();
@@ skipping 29 matching lines @@
   }
 
   bool ShouldBeAllocatedBefore(const LiveRange* other) const;
   bool CanCover(LifetimePosition position) const;
   bool Covers(LifetimePosition position) const;
   LifetimePosition FirstIntersection(LiveRange* other) const;
 
   // Add a new interval or a new use position to this live range.
   void EnsureInterval(LifetimePosition start, LifetimePosition end, Zone* zone);
   void AddUseInterval(LifetimePosition start, LifetimePosition end, Zone* zone);
-  void AddUsePosition(LifetimePosition pos, InstructionOperand* operand,
-                      InstructionOperand* hint, Zone* zone);
+  void AddUsePosition(UsePosition* pos);
 
   // Shorten the most recently added interval by setting a new start.
   void ShortenTo(LifetimePosition start);
 
   void Verify() const;
 
   void ConvertUsesToOperand(const InstructionOperand& op,
                             InstructionOperand* spill_op);
+  void SetUseHints(int register_index);
+  void UnsetUseHints() { SetUseHints(kUnassignedRegister); }
 
   void set_kind(RegisterKind kind) { kind_ = kind; }
 
  private:
   struct SpillAtDefinitionList;
 
   UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const;
   void AdvanceLastProcessedMarker(UseInterval* to_start_of,
                                   LifetimePosition but_not_past) const;
 
   // TODO(dcarney): pack this structure better.
   int id_;
   bool spilled_ : 1;
   bool has_slot_use_ : 1;  // Relevant only for parent.
-  bool is_phi_ : 1;
-  bool is_non_loop_phi_ : 1;
+  bool is_phi_ : 1;           // Correct only for parent.
+  bool is_non_loop_phi_ : 1;  // Correct only for parent.
   RegisterKind kind_;
   int assigned_register_;
   UseInterval* last_interval_;
   UseInterval* first_interval_;
   UsePosition* first_pos_;
   LiveRange* parent_;
   LiveRange* next_;
   // 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_;
   // This is used as a cache, it's invalid outside of BuildLiveRanges.
-  mutable InstructionOperand* current_hint_operand_;
+  mutable UsePosition* current_hint_position_;
   int spill_start_index_;
   SpillType spill_type_;
   union {
     InstructionOperand* spill_operand_;
     SpillRange* spill_range_;
   };
   SpillAtDefinitionList* spills_at_definition_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRange);
 };
@@ skipping 21 matching lines @@
   LifetimePosition end_position_;
 
   DISALLOW_COPY_AND_ASSIGN(SpillRange);
 };
 
 
 class RegisterAllocationData final : public ZoneObject {
  public:
   class PhiMapValue : public ZoneObject {
    public:
-    PhiMapValue(PhiInstruction* phi, const InstructionBlock* block, Zone* zone)
-        : phi(phi), block(block), incoming_moves(zone) {
-      incoming_moves.reserve(phi->operands().size());
+    PhiMapValue(PhiInstruction* phi, const InstructionBlock* block, Zone* zone);
+
+    const PhiInstruction* phi() const { return phi_; }
+    const InstructionBlock* block() const { return block_; }
+
+    // For hinting.
+    int assigned_register() const { return assigned_register_; }
+    void set_assigned_register(int register_index) {
+      DCHECK_EQ(assigned_register_, kUnassignedRegister);
+      assigned_register_ = register_index;
     }
-    PhiInstruction* const phi;
-    const InstructionBlock* const block;
-    ZoneVector<MoveOperands*> incoming_moves;
+    void UnsetAssignedRegister() { assigned_register_ = kUnassignedRegister; }
+
+    void AddOperand(InstructionOperand* operand);
+    void CommitAssignment(const InstructionOperand& operand);
+
+   private:
+    PhiInstruction* const phi_;
+    const InstructionBlock* const block_;
+    ZoneVector<InstructionOperand*> incoming_operands_;
+    int assigned_register_;
   };
   typedef ZoneMap<int, PhiMapValue*> PhiMap;
 
   RegisterAllocationData(const RegisterConfiguration* config,
                          Zone* allocation_zone, Frame* frame,
                          InstructionSequence* code,
                          const char* debug_name = nullptr);
 
   const ZoneVector<LiveRange*>& live_ranges() const { return live_ranges_; }
   ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; }
   const ZoneVector<LiveRange*>& fixed_live_ranges() const {
     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_; }
   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(); }
-  const PhiMap& phi_map() const { return phi_map_; }
-  PhiMap& phi_map() { return phi_map_; }
   Frame* frame() const { return frame_; }
   const char* debug_name() const { return debug_name_; }
   const RegisterConfiguration* config() const { return config_; }
 
-  void SetLiveRangeAssignedRegister(LiveRange* range, int reg);
   LiveRange* LiveRangeFor(int index);
 
-  void AssignPhiInput(LiveRange* range, const InstructionOperand& assignment);
   SpillRange* AssignSpillRangeToLiveRange(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();
 
   // Creates a new live range.
   LiveRange* NewLiveRange(int index);
 
+  void MarkAllocated(RegisterKind kind, int index);
+
+  PhiMapValue* InitializePhiMap(const InstructionBlock* block,
+                                PhiInstruction* phi);
+  PhiMapValue* GetPhiMapValueFor(int virtual_register);
+
  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_;
@@ skipping 38 matching lines @@
   void ResolvePhis(const InstructionBlock* block);
 
   RegisterAllocationData* const data_;
 
   DISALLOW_COPY_AND_ASSIGN(ConstraintBuilder);
 };
 
 
 class LiveRangeBuilder final : public ZoneObject {
  public:
-  explicit LiveRangeBuilder(RegisterAllocationData* data);
+  explicit LiveRangeBuilder(RegisterAllocationData* data, Zone* local_zone);
 
   // Phase 3: compute liveness of all virtual register.
   void BuildLiveRanges();
 
  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);
-  bool IsOutputRegisterOf(Instruction* instr, int index);
-  bool IsOutputDoubleRegisterOf(Instruction* instr, int index);
   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);
 
+  void MapPhiHint(InstructionOperand* operand, UsePosition* use_pos);
+  void ResolvePhiHint(InstructionOperand* operand, UsePosition* use_pos);
+
   // Returns the register kind required by the given virtual register.
   RegisterKind RequiredRegisterKind(int virtual_register) const;
 
+  UsePosition* NewUsePosition(LifetimePosition pos, InstructionOperand* operand,
+                              void* hint, UsePositionHintType hint_type);
+  UsePosition* NewUsePosition(LifetimePosition pos) {
+    return NewUsePosition(pos, nullptr, nullptr, UsePositionHintType::kNone);
+  }
+  LiveRange* LiveRangeFor(InstructionOperand* operand);
   // Helper methods for building intervals.
-  LiveRange* LiveRangeFor(InstructionOperand* operand);
-  void Define(LifetimePosition position, InstructionOperand* operand,
-              InstructionOperand* hint);
+  UsePosition* Define(LifetimePosition position, InstructionOperand* operand,
+                      void* hint, UsePositionHintType hint_type);
+  void Define(LifetimePosition position, InstructionOperand* operand) {
+    Define(position, operand, nullptr, UsePositionHintType::kNone);
+  }
+  UsePosition* Use(LifetimePosition block_start, LifetimePosition position,
+                   InstructionOperand* operand, void* hint,
+                   UsePositionHintType hint_type);
   void Use(LifetimePosition block_start, LifetimePosition position,
-           InstructionOperand* operand, InstructionOperand* hint);
+           InstructionOperand* operand) {
+    Use(block_start, position, operand, nullptr, UsePositionHintType::kNone);
+  }
 
   RegisterAllocationData* const data_;
+  ZoneMap<InstructionOperand*, UsePosition*> phi_hints_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRangeBuilder);
 };
 
 
 class RegisterAllocator : public ZoneObject {
  public:
   explicit RegisterAllocator(RegisterAllocationData* data, RegisterKind kind);
 
  protected:
@@ skipping 52 matching lines @@
   const char* RegisterName(int allocation_index) const;
 
   ZoneVector<LiveRange*>& unhandled_live_ranges() {
     return unhandled_live_ranges_;
   }
   ZoneVector<LiveRange*>& active_live_ranges() { return active_live_ranges_; }
   ZoneVector<LiveRange*>& inactive_live_ranges() {
     return inactive_live_ranges_;
   }
 
+  void SetLiveRangeAssignedRegister(LiveRange* range, int reg);
+
   // Helper methods for updating the life range lists.
   void AddToActive(LiveRange* range);
   void AddToInactive(LiveRange* range);
   void AddToUnhandledSorted(LiveRange* range);
   void AddToUnhandledUnsorted(LiveRange* range);
   void SortUnhandled();
   bool UnhandledIsSorted();
   void ActiveToHandled(LiveRange* range);
   void ActiveToInactive(LiveRange* range);
   void InactiveToHandled(LiveRange* range);
@@ skipping 131 matching lines @@
   RegisterAllocationData* const data_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRangeConnector);
 };
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_REGISTER_ALLOCATOR_H_