Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(287)

Issues Search
    My Issues | Starred     Open | Closed | All

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

Issue 1061923005: Reland: Introducing the LLVM greedy register allocator. (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 5 years, 8 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
Download patch
« no previous file with comments | « src/compiler/pipeline.cc ('k') | src/compiler/register-allocator.cc » ('j') | src/compiler/register-allocator.cc » ('J')
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/compiler/register-allocator.h
diff --git a/src/compiler/register-allocator.h b/src/compiler/register-allocator.h
index 8ab37d19884034c88ff933342bbd2932d36d6e00..2ad13179e6cdf3db9e8f2c02c72ee74fe8d25f0b 100644
--- a/src/compiler/register-allocator.h
+++ b/src/compiler/register-allocator.h
@@ -412,7 +412,7 @@ class SpillRange FINAL : public ZoneObject {
};
-class RegisterAllocator FINAL : public ZoneObject {
+class RegisterAllocator : public ZoneObject {
public:
explicit RegisterAllocator(const RegisterConfiguration* config,
Zone* local_zone, Frame* frame,
@@ -442,8 +442,8 @@ class RegisterAllocator FINAL : public ZoneObject {
bool ExistsUseWithoutDefinition();
// Phase 4: compute register assignments.
- void AllocateGeneralRegisters();
- void AllocateDoubleRegisters();
+ virtual void AllocateGeneralRegisters() = 0;
+ virtual void AllocateDoubleRegisters() = 0;
// Phase 5: assign spill splots.
void AssignSpillSlots();
@@ -460,58 +460,163 @@ class RegisterAllocator FINAL : public ZoneObject {
// Phase 9: insert moves to connect ranges across basic blocks.
void ResolveControlFlow();
- private:
- int GetVirtualRegister() { return code()->NextVirtualRegister(); }
+ protected:
+ virtual ~RegisterAllocator() {}
+ 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());
+ }
+ PhiInstruction* const phi;
+ const InstructionBlock* const block;
+ ZoneVector<MoveOperands*> incoming_moves;
+ };
+ typedef ZoneMap<int, PhiMapValue*> PhiMap;
+ PhiMap& phi_map() { return phi_map_; }
- // Checks whether the value of a given virtual register is a reference.
- // TODO(titzer): rename this to IsReference.
- bool HasTaggedValue(int virtual_register) const;
+ ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; }
+ ZoneVector<LiveRange*>& fixed_live_ranges() { return fixed_live_ranges_; }
+ ZoneVector<LiveRange*>& fixed_double_live_ranges() {
+ return fixed_double_live_ranges_;
+ }
- // Returns the register kind required by the given virtual register.
- RegisterKind RequiredRegisterKind(int virtual_register) const;
+ BitVector* assigned_registers() const { return assigned_registers_; }
+ BitVector* assigned_double_registers() const {
+ return assigned_double_registers_;
+ }
- // Creates a new live range.
- LiveRange* NewLiveRange(int index);
+ Frame* frame() const { return frame_; }
+ const char* debug_name() const { return debug_name_; }
+ const RegisterConfiguration* config() const { return config_; }
+ ZoneVector<SpillRange*>& spill_ranges() { return spill_ranges_; }
// This zone is for InstructionOperands and moves that live beyond register
// allocation.
Zone* code_zone() const { return code()->zone(); }
+ Instruction* InstructionAt(int index) { return code()->InstructionAt(index); }
+ // Creates a new live range.
+ LiveRange* NewLiveRange(int index);
- BitVector* assigned_registers() { return assigned_registers_; }
- BitVector* assigned_double_registers() { return assigned_double_registers_; }
+ LiveRange* LiveRangeFor(int index);
+ LiveRange* LiveRangeFor(InstructionOperand* operand);
+ LiveRange* FixedLiveRangeFor(int index);
+ LiveRange* FixedDoubleLiveRangeFor(int index);
+ static int FixedLiveRangeID(int index) { return -index - 1; }
+ int FixedDoubleLiveRangeID(int index);
+ void SetLiveRangeAssignedRegister(LiveRange* range, int reg);
-#ifdef DEBUG
- void Verify() const;
-#endif
+ // Helper methods for building intervals.
+ InstructionOperand* AllocateFixed(UnallocatedOperand* operand, int pos,
+ bool is_tagged);
- void AllocateRegisters();
+ MoveOperands* AddGapMove(int index, Instruction::GapPosition position,
+ const InstructionOperand& from,
+ const InstructionOperand& to);
+ // Checks whether the value of a given virtual register is a reference.
+ // TODO(titzer): rename this to IsReference.
+ bool HasTaggedValue(int virtual_register) const;
+
+ bool IsBlockBoundary(LifetimePosition pos);
bool CanEagerlyResolveControlFlow(const InstructionBlock* block) const;
- bool SafePointsAreInOrder() const;
- // Liveness analysis support.
- BitVector* ComputeLiveOut(const InstructionBlock* block);
+ // Return the block which contains give lifetime position.
+ const InstructionBlock* GetInstructionBlock(LifetimePosition pos);
+ SpillRange* AssignSpillRangeToLiveRange(LiveRange* range);
+ void Spill(LiveRange* range);
+
+ // Live range splitting helpers.
+ // Split the given range at the given position.
+ // If range starts at or after the given position then the
+ // original range is returned.
+ // Otherwise returns the live range that starts at pos and contains
+ // all uses from the original range that follow pos. Uses at pos will
+ // still be owned by the original range after splitting.
+ LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos);
+
+ // Split the given range in a position from the interval [start, end].
+ LiveRange* SplitBetween(LiveRange* range, LifetimePosition start,
+ LifetimePosition end);
+
+ // Find a lifetime position in the interval [start, end] which
+ // is optimal for splitting: it is either header of the outermost
+ // loop covered by this interval or the latest possible position.
+ LifetimePosition FindOptimalSplitPos(LifetimePosition start,
+ LifetimePosition end);
+
+
+ private:
void AddInitialIntervals(const InstructionBlock* block, BitVector* live_out);
+ void AssignPhiInput(LiveRange* range, const InstructionOperand& assignment);
+ void ProcessInstructions(const InstructionBlock* block, BitVector* live);
+ Instruction* GetLastInstruction(const InstructionBlock* block);
+ void Define(LifetimePosition position, InstructionOperand* operand,
+ InstructionOperand* hint);
+ int GetVirtualRegister() { return code()->NextVirtualRegister(); }
+ void Use(LifetimePosition block_start, LifetimePosition position,
+ InstructionOperand* operand, InstructionOperand* hint);
+ // Returns the register kind required by the given virtual register.
+ RegisterKind RequiredRegisterKind(int virtual_register) const;
+
bool IsOutputRegisterOf(Instruction* instr, int index);
bool IsOutputDoubleRegisterOf(Instruction* instr, int index);
- void ProcessInstructions(const InstructionBlock* block, BitVector* live);
+
+ void ResolvePhis(const InstructionBlock* block);
void MeetRegisterConstraints(const InstructionBlock* block);
void MeetConstraintsBefore(int index);
void MeetConstraintsAfter(int index);
void MeetRegisterConstraintsForLastInstructionInBlock(
const InstructionBlock* block);
- void ResolvePhis(const InstructionBlock* block);
- // Helper methods for building intervals.
- 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);
- MoveOperands* AddGapMove(int index, Instruction::GapPosition position,
- const InstructionOperand& from,
- const InstructionOperand& to);
+ // Helper methods for resolving control flow.
+ void ResolveControlFlow(const InstructionBlock* block,
+ const InstructionOperand& cur_op,
+ const InstructionBlock* pred,
+ const InstructionOperand& pred_op);
+ bool SafePointsAreInOrder() const;
+
+ // Liveness analysis support.
+ BitVector* ComputeLiveOut(const InstructionBlock* block);
+
+ Zone* const local_zone_;
+ Frame* const frame_;
+ InstructionSequence* const code_;
+ const char* const debug_name_;
+ const RegisterConfiguration* config_;
+ PhiMap phi_map_;
+
+ // Liveness analysis results.
+ ZoneVector<LiveRange*> live_ranges_;
+
+ // Lists of live ranges.
+ ZoneVector<LiveRange*> fixed_live_ranges_;
+ ZoneVector<LiveRange*> fixed_double_live_ranges_;
+ ZoneVector<SpillRange*> spill_ranges_;
+
+ // During liveness analysis keep a mapping from block id to live_in sets
+ // for blocks already analyzed.
+ ZoneVector<BitVector*> live_in_sets_;
+
+ BitVector* assigned_registers_;
+ BitVector* assigned_double_registers_;
+};
+
+
+class RegisterAllocatorLinear FINAL : public RegisterAllocator {
+ public:
+ explicit RegisterAllocatorLinear(const RegisterConfiguration* config,
+ Zone* local_zone, Frame* frame,
+ InstructionSequence* code,
+ const char* debug_name = nullptr);
+ void AllocateGeneralRegisters() override;
+ void AllocateDoubleRegisters() override;
+
+ private:
+#ifdef DEBUG
+ void Verify() const;
+#endif
+
+ void AllocateRegisters();
// Helper methods for updating the life range lists.
void AddToActive(LiveRange* range);
@@ -529,27 +634,6 @@ class RegisterAllocator FINAL : public ZoneObject {
bool TryReuseSpillForPhi(LiveRange* range);
bool TryAllocateFreeReg(LiveRange* range);
void AllocateBlockedReg(LiveRange* range);
- SpillRange* AssignSpillRangeToLiveRange(LiveRange* range);
-
- // Live range splitting helpers.
-
- // Split the given range at the given position.
- // If range starts at or after the given position then the
- // original range is returned.
- // Otherwise returns the live range that starts at pos and contains
- // all uses from the original range that follow pos. Uses at pos will
- // still be owned by the original range after splitting.
- LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos);
-
- // Split the given range in a position from the interval [start, end].
- LiveRange* SplitBetween(LiveRange* range, LifetimePosition start,
- LifetimePosition end);
-
- // Find a lifetime position in the interval [start, end] which
- // is optimal for splitting: it is either header of the outermost
- // loop covered by this interval or the latest possible position.
- LifetimePosition FindOptimalSplitPos(LifetimePosition start,
- LifetimePosition end);
// Spill the given life range after position pos.
void SpillAfter(LiveRange* range, LifetimePosition pos);
@@ -570,42 +654,10 @@ class RegisterAllocator FINAL : public ZoneObject {
LifetimePosition FindOptimalSpillingPos(LiveRange* range,
LifetimePosition pos);
- void Spill(LiveRange* range);
- bool IsBlockBoundary(LifetimePosition pos);
-
- // Helper methods for resolving control flow.
- void ResolveControlFlow(const InstructionBlock* block,
- const InstructionOperand& cur_op,
- const InstructionBlock* pred,
- const InstructionOperand& pred_op);
-
- void SetLiveRangeAssignedRegister(LiveRange* range, int reg);
-
- // Return the block which contains give lifetime position.
- const InstructionBlock* GetInstructionBlock(LifetimePosition pos);
-
// Helper methods for the fixed registers.
int RegisterCount() const;
- static int FixedLiveRangeID(int index) { return -index - 1; }
- int FixedDoubleLiveRangeID(int index);
- LiveRange* FixedLiveRangeFor(int index);
- LiveRange* FixedDoubleLiveRangeFor(int index);
- LiveRange* LiveRangeFor(int index);
- Instruction* GetLastInstruction(const InstructionBlock* block);
const char* RegisterName(int allocation_index);
-
- Instruction* InstructionAt(int index) { return code()->InstructionAt(index); }
- void AssignPhiInput(LiveRange* range, const InstructionOperand& assignment);
-
- Frame* frame() const { return frame_; }
- const char* debug_name() const { return debug_name_; }
- const RegisterConfiguration* config() const { return config_; }
- ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; }
- ZoneVector<LiveRange*>& fixed_live_ranges() { return fixed_live_ranges_; }
- ZoneVector<LiveRange*>& fixed_double_live_ranges() {
- return fixed_double_live_ranges_;
- }
ZoneVector<LiveRange*>& unhandled_live_ranges() {
return unhandled_live_ranges_;
}
@@ -613,54 +665,61 @@ class RegisterAllocator FINAL : public ZoneObject {
ZoneVector<LiveRange*>& inactive_live_ranges() {
return inactive_live_ranges_;
}
- ZoneVector<SpillRange*>& spill_ranges() { return spill_ranges_; }
- 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());
- }
- PhiInstruction* const phi;
- const InstructionBlock* const block;
- ZoneVector<MoveOperands*> incoming_moves;
- };
- typedef ZoneMap<int, PhiMapValue*> PhiMap;
-
- Zone* const local_zone_;
- Frame* const frame_;
- InstructionSequence* const code_;
- const char* const debug_name_;
- const RegisterConfiguration* config_;
- PhiMap phi_map_;
-
- // During liveness analysis keep a mapping from block id to live_in sets
- // for blocks already analyzed.
- ZoneVector<BitVector*> live_in_sets_;
-
- // Liveness analysis results.
- ZoneVector<LiveRange*> live_ranges_;
-
- // Lists of live ranges
- ZoneVector<LiveRange*> fixed_live_ranges_;
- ZoneVector<LiveRange*> fixed_double_live_ranges_;
ZoneVector<LiveRange*> unhandled_live_ranges_;
ZoneVector<LiveRange*> active_live_ranges_;
ZoneVector<LiveRange*> inactive_live_ranges_;
- ZoneVector<SpillRange*> spill_ranges_;
RegisterKind mode_;
int num_registers_;
- BitVector* assigned_registers_;
- BitVector* assigned_double_registers_;
-
#ifdef DEBUG
LifetimePosition allocation_finger_;
#endif
- DISALLOW_COPY_AND_ASSIGN(RegisterAllocator);
+ DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorLinear);
+};
+
+
+class RegisterAllocationInfo;
+
+
+class RegisterAllocatorGreedy FINAL : public RegisterAllocator {
+ public:
+ explicit RegisterAllocatorGreedy(const RegisterConfiguration* config,
+ Zone* local_zone, Frame* frame,
+ InstructionSequence* code,
+ const char* debug_name = nullptr);
+
+ void AllocateGeneralRegisters() override;
+ void AllocateDoubleRegisters() override;
+
+ private:
+ void AllocateRegisters(RegisterKind mode);
+ typedef ZonePriorityQueue<std::pair<unsigned, LiveRange*>> PQueue;
+
+ unsigned GetLiveRangeSize(LiveRange* range);
+ void Enqueue(LiveRange* range);
+
+ void Evict(LiveRange* range);
+ float CalculateSpillWeight(LiveRange* range);
+ float CalculateMaxSpillWeight(const ZoneSet<LiveRange*>& ranges);
+
+
+ bool TryAllocate(LiveRange* current, ZoneSet<LiveRange*>* conflicting);
+ bool TryAllocatePhysicalRegister(unsigned reg_id, LiveRange* range,
+ ZoneSet<LiveRange*>* conflicting);
+ bool HandleSpillOperands(LiveRange* range);
+ bool AllocateBlockedRange(LiveRange*, const ZoneSet<LiveRange*>&);
+
+ LiveRange* SpillBetweenUntil(LiveRange* range, LifetimePosition start,
+ LifetimePosition until, LifetimePosition end);
+ void AssignRangeToRegister(unsigned regId, LiveRange* range);
+
+ ZoneVector<RegisterAllocationInfo*> allocations_;
+ PQueue queue_;
+ DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorGreedy);
};
} // namespace compiler
« no previous file with comments | « src/compiler/pipeline.cc ('k') | src/compiler/register-allocator.cc » ('j') | src/compiler/register-allocator.cc » ('J')

Powered by Google App Engine
This is Rietveld 408576698