Land the Fan (disabled)

src/compiler/register-allocator.h

Index: src/compiler/register-allocator.h
diff --git a/src/lithium-allocator.h b/src/compiler/register-allocator.h
similarity index 68%
copy from src/lithium-allocator.h
copy to src/compiler/register-allocator.h
index 1d313a5a54825e890981cd0ddab90317fb2d37a4..1d50aec3ef2eac6086137218be48d568cfc7d843 100644
--- a/src/lithium-allocator.h
+++ b/src/compiler/register-allocator.h
@@ -1,41 +1,40 @@
-// Copyright 2012 the V8 project authors. All rights reserved.
+// 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_LITHIUM_ALLOCATOR_H_
-#define V8_LITHIUM_ALLOCATOR_H_
-
-#include "src/v8.h"
+#ifndef V8_REGISTER_ALLOCATOR_H_
+#define V8_REGISTER_ALLOCATOR_H_
 
 #include "src/allocation.h"
-#include "src/lithium.h"
+#include "src/compiler/instruction.h"
+#include "src/compiler/node.h"
+#include "src/compiler/schedule.h"
+#include "src/macro-assembler.h"
 #include "src/zone.h"
 
 namespace v8 {
 namespace internal {
 
 // Forward declarations.
-class HBasicBlock;
-class HGraph;
-class HInstruction;
-class HPhi;
-class HTracer;
-class HValue;
 class BitVector;
-class StringStream;
+class InstructionOperand;
+class UnallocatedOperand;
+class ParallelMove;
+class PointerMap;
+
+namespace compiler {
 
-class LPlatformChunk;
-class LOperand;
-class LUnallocated;
-class LGap;
-class LParallelMove;
-class LPointerMap;
+enum RegisterKind {
+  UNALLOCATED_REGISTERS,
+  GENERAL_REGISTERS,
+  DOUBLE_REGISTERS
+};
 
 
-// This class represents a single point of a LOperand's lifetime.
-// For each lithium instruction there are exactly two lifetime positions:
-// the beginning and the end of the instruction. Lifetime positions for
-// different lithium instructions are disjoint.
+// This class represents a single point of a InstructionOperand's lifetime. For
+// each instruction there are exactly two lifetime positions: the beginning and
+// the end of the instruction. Lifetime positions for different instructions are
+// disjoint.
 class LifetimePosition {
  public:
   // Return the lifetime position that corresponds to the beginning of
@@ -45,9 +44,7 @@ class LifetimePosition {
   }
 
   // Returns a numeric representation of this lifetime position.
-  int Value() const {
-    return value_;
-  }
+  int Value() const { return value_; }
 
   // Returns the index of the instruction to which this lifetime position
   // corresponds.
@@ -58,9 +55,7 @@ class LifetimePosition {
 
   // Returns true if this lifetime position corresponds to the instruction
   // start.
-  bool IsInstructionStart() const {
-    return (value_ & (kStep - 1)) == 0;
-  }
+  bool IsInstructionStart() const { return (value_ & (kStep - 1)) == 0; }
 
   // Returns the lifetime position for the start of the instruction which
   // corresponds to this lifetime position.
@@ -73,7 +68,7 @@ class LifetimePosition {
   // corresponds to this lifetime position.
   LifetimePosition InstructionEnd() const {
     ASSERT(IsValid());
-    return LifetimePosition(InstructionStart().Value() + kStep/2);
+    return LifetimePosition(InstructionStart().Value() + kStep / 2);
   }
 
   // Returns the lifetime position for the beginning of the next instruction.
@@ -112,72 +107,14 @@ class LifetimePosition {
   // Code relies on kStep being a power of two.
   STATIC_ASSERT(IS_POWER_OF_TWO(kStep));
 
-  explicit LifetimePosition(int value) : value_(value) { }
+  explicit LifetimePosition(int value) : value_(value) {}
 
   int value_;
 };
 
 
-enum RegisterKind {
-  UNALLOCATED_REGISTERS,
-  GENERAL_REGISTERS,
-  DOUBLE_REGISTERS
-};
-
-
-// A register-allocator view of a Lithium instruction. It contains the id of
-// the output operand and a list of input operand uses.
-
-class LInstruction;
-class LEnvironment;
-
-// Iterator for non-null temp operands.
-class TempIterator BASE_EMBEDDED {
- public:
-  inline explicit TempIterator(LInstruction* instr);
-  inline bool Done();
-  inline LOperand* Current();
-  inline void Advance();
-
- private:
-  inline void SkipUninteresting();
-  LInstruction* instr_;
-  int limit_;
-  int current_;
-};
-
-
-// Iterator for non-constant input operands.
-class InputIterator BASE_EMBEDDED {
- public:
-  inline explicit InputIterator(LInstruction* instr);
-  inline bool Done();
-  inline LOperand* Current();
-  inline void Advance();
-
- private:
-  inline void SkipUninteresting();
-  LInstruction* instr_;
-  int limit_;
-  int current_;
-};
-
-
-class UseIterator BASE_EMBEDDED {
- public:
-  inline explicit UseIterator(LInstruction* instr);
-  inline bool Done();
-  inline LOperand* Current();
-  inline void Advance();
-
- private:
-  InputIterator input_iterator_;
-  DeepIterator env_iterator_;
-};
-
-
 // Representation of the non-empty interval [start,end[.
-class UseInterval: public ZoneObject {
+class UseInterval : public ZoneObject {
  public:
   UseInterval(LifetimePosition start, LifetimePosition end)
       : start_(start), end_(end), next_(NULL) {
@@ -204,26 +141,24 @@ class UseInterval: public ZoneObject {
     return start_.Value() <= point.Value() && point.Value() < end_.Value();
   }
 
- private:
   void set_start(LifetimePosition start) { start_ = start; }
   void set_next(UseInterval* next) { next_ = next; }
 
   LifetimePosition start_;
   LifetimePosition end_;
   UseInterval* next_;
-
-  friend class LiveRange;  // Assigns to start_.
 };
 
 // Representation of a use position.
-class UsePosition: public ZoneObject {
+class UsePosition : public ZoneObject {
  public:
-  UsePosition(LifetimePosition pos, LOperand* operand, LOperand* hint);
+  UsePosition(LifetimePosition pos, InstructionOperand* operand,
+              InstructionOperand* hint);
 
-  LOperand* operand() const { return operand_; }
+  InstructionOperand* operand() const { return operand_; }
   bool HasOperand() const { return operand_ != NULL; }
 
-  LOperand* hint() const { return hint_; }
+  InstructionOperand* hint() const { return hint_; }
   bool HasHint() const;
   bool RequiresRegister() const;
   bool RegisterIsBeneficial() const;
@@ -231,22 +166,19 @@ class UsePosition: public ZoneObject {
   LifetimePosition pos() const { return pos_; }
   UsePosition* next() const { return next_; }
 
- private:
   void set_next(UsePosition* next) { next_ = next; }
 
-  LOperand* const operand_;
-  LOperand* const hint_;
+  InstructionOperand* const operand_;
+  InstructionOperand* const hint_;
   LifetimePosition const pos_;
   UsePosition* next_;
   bool requires_reg_;
   bool register_beneficial_;
-
-  friend class LiveRange;
 };
 
 // Representation of SSA values' live ranges as a collection of (continuous)
 // intervals over the instruction ordering.
-class LiveRange: public ZoneObject {
+class LiveRange : public ZoneObject {
  public:
   static const int kInvalidAssignment = 0x7fffffff;
 
@@ -261,11 +193,17 @@ class LiveRange: public ZoneObject {
   int id() const { return id_; }
   bool IsFixed() const { return id_ < 0; }
   bool IsEmpty() const { return first_interval() == NULL; }
-  LOperand* CreateAssignedOperand(Zone* zone);
+  InstructionOperand* CreateAssignedOperand(Zone* zone);
   int assigned_register() const { return assigned_register_; }
   int spill_start_index() const { return spill_start_index_; }
   void set_assigned_register(int reg, Zone* zone);
   void MakeSpilled(Zone* zone);
+  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;
+  }
 
   // Returns use position in this live range that follows both start
   // and last processed use position.
@@ -301,11 +239,11 @@ class LiveRange: public ZoneObject {
   }
   bool IsSpilled() const { return spilled_; }
 
-  LOperand* current_hint_operand() const {
+  InstructionOperand* current_hint_operand() const {
     ASSERT(current_hint_operand_ == FirstHint());
     return current_hint_operand_;
   }
-  LOperand* FirstHint() const {
+  InstructionOperand* FirstHint() const {
     UsePosition* pos = first_pos_;
     while (pos != NULL && !pos->HasHint()) pos = pos->next();
     if (pos != NULL) return pos->hint();
@@ -323,8 +261,8 @@ class LiveRange: public ZoneObject {
   }
 
   bool HasAllocatedSpillOperand() const;
-  LOperand* GetSpillOperand() const { return spill_operand_; }
-  void SetSpillOperand(LOperand* operand);
+  InstructionOperand* GetSpillOperand() const { return spill_operand_; }
+  void SetSpillOperand(InstructionOperand* operand);
 
   void SetSpillStartIndex(int start) {
     spill_start_index_ = Min(start, spill_start_index_);
@@ -336,16 +274,10 @@ class LiveRange: public ZoneObject {
   LifetimePosition FirstIntersection(LiveRange* other);
 
   // 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,
-                      LOperand* operand,
-                      LOperand* hint,
-                      Zone* zone);
+  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);
 
   // Shorten the most recently added interval by setting a new start.
   void ShortenTo(LifetimePosition start);
@@ -364,6 +296,8 @@ class LiveRange: public ZoneObject {
 
   int id_;
   bool spilled_;
+  bool is_phi_;
+  bool is_non_loop_phi_;
   RegisterKind kind_;
   int assigned_register_;
   UseInterval* last_interval_;
@@ -375,27 +309,28 @@ class LiveRange: public ZoneObject {
   mutable UseInterval* current_interval_;
   UsePosition* last_processed_use_;
   // This is used as a cache, it's invalid outside of BuildLiveRanges.
-  LOperand* current_hint_operand_;
-  LOperand* spill_operand_;
+  InstructionOperand* current_hint_operand_;
+  InstructionOperand* spill_operand_;
   int spill_start_index_;
 
-  friend class LAllocator;  // Assigns to kind_.
+  friend class RegisterAllocator;  // Assigns to kind_.
 };
 
 
-class LAllocator BASE_EMBEDDED {
+class RegisterAllocator BASE_EMBEDDED {
  public:
-  LAllocator(int first_virtual_register, HGraph* graph);
+  explicit RegisterAllocator(InstructionSequence* code);
 
   static void TraceAlloc(const char* msg, ...);
 
-  // Checks whether the value of a given virtual register is tagged.
+  // Checks whether the value of a given virtual register is a reference.
+  // TODO(titzer): rename this to IsReference.
   bool HasTaggedValue(int virtual_register) const;
 
   // Returns the register kind required by the given virtual register.
   RegisterKind RequiredRegisterKind(int virtual_register) const;
 
-  bool Allocate(LChunk* chunk);
+  bool Allocate();
 
   const ZoneList<LiveRange*>* live_ranges() const { return &live_ranges_; }
   const Vector<LiveRange*>* fixed_live_ranges() const {
@@ -405,39 +340,33 @@ class LAllocator BASE_EMBEDDED {
     return &fixed_double_live_ranges_;
   }
 
-  LPlatformChunk* chunk() const { return chunk_; }
-  HGraph* graph() const { return graph_; }
-  Isolate* isolate() const { return graph_->isolate(); }
-  Zone* zone() { return &zone_; }
+  inline InstructionSequence* code() const { return code_; }
+
+  // This zone is for datastructures only needed during register allocation.
+  inline Zone* zone() { return &zone_; }
+
+  // This zone is for InstructionOperands and moves that live beyond register
+  // allocation.
+  inline Zone* code_zone() { return code()->zone(); }
 
   int GetVirtualRegister() {
-    if (next_virtual_register_ >= LUnallocated::kMaxVirtualRegisters) {
+    int vreg = code()->NextVirtualRegister();
+    if (vreg >= UnallocatedOperand::kMaxVirtualRegisters) {
       allocation_ok_ = false;
       // Maintain the invariant that we return something below the maximum.
       return 0;
     }
-    return next_virtual_register_++;
+    return vreg;
   }
 
   bool AllocationOk() { return allocation_ok_; }
 
-  void MarkAsOsrEntry() {
-    // There can be only one.
-    ASSERT(!has_osr_entry_);
-    // Simply set a flag to find and process instruction later.
-    has_osr_entry_ = true;
-  }
-
 #ifdef DEBUG
   void Verify() const;
 #endif
 
-  BitVector* assigned_registers() {
-    return assigned_registers_;
-  }
-  BitVector* assigned_double_registers() {
-    return assigned_double_registers_;
-  }
+  BitVector* assigned_registers() { return assigned_registers_; }
+  BitVector* assigned_double_registers() { return assigned_double_registers_; }
 
  private:
   void MeetRegisterConstraints();
@@ -447,31 +376,33 @@ class LAllocator BASE_EMBEDDED {
   void AllocateDoubleRegisters();
   void ConnectRanges();
   void ResolveControlFlow();
-  void PopulatePointerMaps();
+  void PopulatePointerMaps();  // TODO(titzer): rename to PopulateReferenceMaps.
   void AllocateRegisters();
-  bool CanEagerlyResolveControlFlow(HBasicBlock* block) const;
+  bool CanEagerlyResolveControlFlow(BasicBlock* block) const;
   inline bool SafePointsAreInOrder() const;
 
   // Liveness analysis support.
   void InitializeLivenessAnalysis();
-  BitVector* ComputeLiveOut(HBasicBlock* block);
-  void AddInitialIntervals(HBasicBlock* block, BitVector* live_out);
-  void ProcessInstructions(HBasicBlock* block, BitVector* live);
-  void MeetRegisterConstraints(HBasicBlock* block);
-  void MeetConstraintsBetween(LInstruction* first,
-                              LInstruction* second,
+  BitVector* ComputeLiveOut(BasicBlock* block);
+  void AddInitialIntervals(BasicBlock* block, BitVector* live_out);
+  bool IsOutputRegisterOf(Instruction* instr, int index);
+  bool IsOutputDoubleRegisterOf(Instruction* instr, int index);
+  void ProcessInstructions(BasicBlock* block, BitVector* live);
+  void MeetRegisterConstraints(BasicBlock* block);
+  void MeetConstraintsBetween(Instruction* first, Instruction* second,
                               int gap_index);
-  void ResolvePhis(HBasicBlock* block);
+  void ResolvePhis(BasicBlock* block);
 
   // Helper methods for building intervals.
-  LOperand* AllocateFixed(LUnallocated* operand, int pos, bool is_tagged);
-  LiveRange* LiveRangeFor(LOperand* operand);
-  void Define(LifetimePosition position, LOperand* operand, LOperand* hint);
-  void Use(LifetimePosition block_start,
-           LifetimePosition position,
-           LOperand* operand,
-           LOperand* hint);
-  void AddConstraintsGapMove(int index, LOperand* from, LOperand* to);
+  InstructionOperand* AllocateFixed(UnallocatedOperand* operand, int pos,
+                                    bool is_tagged);
+  LiveRange* LiveRangeFor(InstructionOperand* operand);
+  void Define(LifetimePosition position, InstructionOperand* operand,
+              InstructionOperand* hint);
+  void Use(LifetimePosition block_start, LifetimePosition position,
+           InstructionOperand* operand, InstructionOperand* hint);
+  void AddConstraintsGapMove(int index, InstructionOperand* from,
+                             InstructionOperand* to);
 
   // Helper methods for updating the life range lists.
   void AddToActive(LiveRange* range);
@@ -485,7 +416,7 @@ class LAllocator BASE_EMBEDDED {
   void InactiveToHandled(LiveRange* range);
   void InactiveToActive(LiveRange* range);
   void FreeSpillSlot(LiveRange* range);
-  LOperand* TryReuseSpillSlot(LiveRange* range);
+  InstructionOperand* TryReuseSpillSlot(LiveRange* range);
 
   // Helper methods for allocating registers.
   bool TryAllocateFreeReg(LiveRange* range);
@@ -502,8 +433,7 @@ class LAllocator BASE_EMBEDDED {
   LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos);
 
   // Split the given range in a position from the interval [start, end].
-  LiveRange* SplitBetween(LiveRange* range,
-                          LifetimePosition start,
+  LiveRange* SplitBetween(LiveRange* range, LifetimePosition start,
                           LifetimePosition end);
 
   // Find a lifetime position in the interval [start, end] which
@@ -516,16 +446,13 @@ class LAllocator BASE_EMBEDDED {
   void SpillAfter(LiveRange* range, LifetimePosition pos);
 
   // Spill the given life range after position [start] and up to position [end].
-  void SpillBetween(LiveRange* range,
-                    LifetimePosition start,
+  void SpillBetween(LiveRange* range, LifetimePosition start,
                     LifetimePosition end);
 
   // Spill the given life range after position [start] and up to position [end].
   // Range is guaranteed to be spilled at least until position [until].
-  void SpillBetweenUntil(LiveRange* range,
-                         LifetimePosition start,
-                         LifetimePosition until,
-                         LifetimePosition end);
+  void SpillBetweenUntil(LiveRange* range, LifetimePosition start,
+                         LifetimePosition until, LifetimePosition end);
 
   void SplitAndSpillIntersecting(LiveRange* range);
 
@@ -538,18 +465,17 @@ class LAllocator BASE_EMBEDDED {
   bool IsBlockBoundary(LifetimePosition pos);
 
   // Helper methods for resolving control flow.
-  void ResolveControlFlow(LiveRange* range,
-                          HBasicBlock* block,
-                          HBasicBlock* pred);
+  void ResolveControlFlow(LiveRange* range, BasicBlock* block,
+                          BasicBlock* pred);
 
   inline void SetLiveRangeAssignedRegister(LiveRange* range, int reg);
 
   // Return parallel move that should be used to connect ranges split at the
   // given position.
-  LParallelMove* GetConnectingParallelMove(LifetimePosition pos);
+  ParallelMove* GetConnectingParallelMove(LifetimePosition pos);
 
   // Return the block which contains give lifetime position.
-  HBasicBlock* GetBlock(LifetimePosition pos);
+  BasicBlock* GetBlock(LifetimePosition pos);
 
   // Helper methods for the fixed registers.
   int RegisterCount() const;
@@ -558,20 +484,16 @@ class LAllocator BASE_EMBEDDED {
   LiveRange* FixedLiveRangeFor(int index);
   LiveRange* FixedDoubleLiveRangeFor(int index);
   LiveRange* LiveRangeFor(int index);
-  HPhi* LookupPhi(LOperand* operand) const;
-  LGap* GetLastGap(HBasicBlock* block);
+  GapInstruction* GetLastGap(BasicBlock* block);
 
   const char* RegisterName(int allocation_index);
 
-  inline bool IsGapAt(int index);
-
-  inline LInstruction* InstructionAt(int index);
-
-  inline LGap* GapAt(int index);
+  inline Instruction* InstructionAt(int index) {
+    return code()->InstructionAt(index);
+  }
 
   Zone zone_;
-
-  LPlatformChunk* chunk_;
+  InstructionSequence* code_;
 
   // During liveness analysis keep a mapping from block id to live_in sets
   // for blocks already analyzed.
@@ -590,21 +512,12 @@ class LAllocator BASE_EMBEDDED {
   ZoneList<LiveRange*> inactive_live_ranges_;
   ZoneList<LiveRange*> reusable_slots_;
 
-  // Next virtual register number to be assigned to temporaries.
-  int next_virtual_register_;
-  int first_artificial_register_;
-  GrowableBitVector double_artificial_registers_;
-
   RegisterKind mode_;
   int num_registers_;
 
   BitVector* assigned_registers_;
   BitVector* assigned_double_registers_;
 
-  HGraph* graph_;
-
-  bool has_osr_entry_;
-
   // Indicates success or failure during register allocation.
   bool allocation_ok_;
 
@@ -612,23 +525,23 @@ class LAllocator BASE_EMBEDDED {
   LifetimePosition allocation_finger_;
 #endif
 
-  DISALLOW_COPY_AND_ASSIGN(LAllocator);
+  DISALLOW_COPY_AND_ASSIGN(RegisterAllocator);
 };
 
 
-class LAllocatorPhase : public CompilationPhase {
+class RegisterAllocatorPhase : public CompilationPhase {
  public:
-  LAllocatorPhase(const char* name, LAllocator* allocator);
-  ~LAllocatorPhase();
+  RegisterAllocatorPhase(const char* name, RegisterAllocator* allocator);
+  ~RegisterAllocatorPhase();
 
  private:
-  LAllocator* allocator_;
+  RegisterAllocator* allocator_;
   unsigned allocator_zone_start_allocation_size_;
 
-  DISALLOW_COPY_AND_ASSIGN(LAllocatorPhase);
+  DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorPhase);
 };
+}
+}
+}  // namespace v8::internal::compiler
 
-
-} }  // namespace v8::internal
-
-#endif  // V8_LITHIUM_ALLOCATOR_H_
+#endif  // V8_REGISTER_ALLOCATOR_H_