src/compiler/register-allocator.h - Issue 426233002: Land the Fan (disabled)

Unified Diff: src/compiler/register-allocator.h

Issue 426233002: Land the Fan (disabled) (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge

Patch Set: Created 6 years, 5 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

View side-by-side diff with in-line comments

Index: src/compiler/register-allocator.h

diff --git a/src/lithium-allocator.h b/src/compiler/register-allocator.h

similarity index 74%

copy from src/lithium-allocator.h

copy to src/compiler/register-allocator.h

index 1d313a5a54825e890981cd0ddab90317fb2d37a4..82b5558fcfde83ecce27f8d05122d537334e93a8 100644

--- a/src/lithium-allocator.h

+++ b/src/compiler/register-allocator.h

@@ -1,41 +1,40 @@

// 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

@@ -118,64 +117,6 @@ class LifetimePosition {

};

-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 {

public:

@@ -204,26 +145,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 {

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,17 +170,14 @@ 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)

@@ -261,11 +197,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 +243,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 +265,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_);

@@ -342,10 +284,8 @@ class LiveRange: public ZoneObject {

void AddUseInterval(LifetimePosition start,

LifetimePosition end,

Zone* zone);

- void AddUsePosition(LifetimePosition pos,

- LOperand* operand,

- LOperand* hint,

- 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 +304,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 +317,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,29 +348,27 @@ 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

@@ -447,31 +388,34 @@ 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 +429,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);

@@ -539,17 +483,17 @@ class LAllocator BASE_EMBEDDED {

// Helper methods for resolving control flow.

void ResolveControlFlow(LiveRange* range,

- HBasicBlock* block,

- HBasicBlock* pred);

+ 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 +502,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 +530,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 +543,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

+} } } // namespace v8::internal::compiler

-#endif // V8_LITHIUM_ALLOCATOR_H_

+#endif // V8_REGISTER_ALLOCATOR_H_

« no previous file with comments | « src/compiler/raw-machine-assembler.cc ('k') | src/compiler/register-allocator.cc » ('j') | src/lithium-inl.h » ('J')