1// Copyright 2020 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef V8_COMPILER_BACKEND_MID_TIER_REGISTER_ALLOCATOR_H_
6#define V8_COMPILER_BACKEND_MID_TIER_REGISTER_ALLOCATOR_H_
7
8#include "src/base/compiler-specific.h"
9#include "src/common/globals.h"
10#include "src/compiler/backend/instruction.h"
11#include "src/compiler/backend/register-allocation.h"
12#include "src/flags/flags.h"
13#include "src/utils/bit-vector.h"
14#include "src/zone/zone-containers.h"
15#include "src/zone/zone.h"
16
17namespace v8 {
18namespace internal {
19
20class TickCounter;
21
22namespace compiler {
23
24class BlockState;
25class VirtualRegisterData;
26
27// The MidTierRegisterAllocator is a register allocator specifically designed to
28// perform register allocation as fast as possible while minimizing spill moves.
29
30class MidTierRegisterAllocationData final : public RegisterAllocationData {
31 public:
32  MidTierRegisterAllocationData(const RegisterConfiguration* config,
33                                Zone* allocation_zone, Frame* frame,
34                                InstructionSequence* code,
35                                TickCounter* tick_counter,
36                                const char* debug_name = nullptr);
37  MidTierRegisterAllocationData(const MidTierRegisterAllocationData&) = delete;
38  MidTierRegisterAllocationData& operator=(
39      const MidTierRegisterAllocationData&) = delete;
40
41  static MidTierRegisterAllocationData* cast(RegisterAllocationData* data) {
42    DCHECK_EQ(data->type(), Type::kMidTier);
43    return static_cast<MidTierRegisterAllocationData*>(data);
44  }
45
46  VirtualRegisterData& VirtualRegisterDataFor(int virtual_register);
47
48  // Add a gap move between the given operands |from| and |to|.
49  MoveOperands* AddGapMove(int instr_index, Instruction::GapPosition position,
50                           const InstructionOperand& from,
51                           const InstructionOperand& to);
52
53  // Adds a gap move where both sides are PendingOperand operands.
54  MoveOperands* AddPendingOperandGapMove(int instr_index,
55                                         Instruction::GapPosition position);
56
57  // Helpers to get a block from an |rpo_number| or |instr_index|.
58  const InstructionBlock* GetBlock(const RpoNumber rpo_number);
59  const InstructionBlock* GetBlock(int instr_index);
60
61  // Returns a bitvector representing all the blocks that are dominated by the
62  // output of the instruction in |block|.
63  const BitVector* GetBlocksDominatedBy(const InstructionBlock* block);
64
65  // List of all instruction indexs that require a reference map.
66  ZoneVector<int>& reference_map_instructions() {
67    return reference_map_instructions_;
68  }
69
70  // Returns a bitvector representing the virtual registers that were spilled.
71  BitVector& spilled_virtual_registers() { return spilled_virtual_registers_; }
72
73  // This zone is for data structures only needed during register allocation
74  // phases.
75  Zone* allocation_zone() const { return allocation_zone_; }
76
77  // This zone is for InstructionOperands and moves that live beyond register
78  // allocation.
79  Zone* code_zone() const { return code()->zone(); }
80
81  BlockState& block_state(RpoNumber rpo_number);
82
83  InstructionSequence* code() const { return code_; }
84  Frame* frame() const { return frame_; }
85  const char* debug_name() const { return debug_name_; }
86  const RegisterConfiguration* config() const { return config_; }
87  TickCounter* tick_counter() { return tick_counter_; }
88
89 private:
90  Zone* const allocation_zone_;
91  Frame* const frame_;
92  InstructionSequence* const code_;
93  const char* const debug_name_;
94  const RegisterConfiguration* const config_;
95
96  ZoneVector<VirtualRegisterData> virtual_register_data_;
97  ZoneVector<BlockState> block_states_;
98  ZoneVector<int> reference_map_instructions_;
99  BitVector spilled_virtual_registers_;
100
101  TickCounter* const tick_counter_;
102};
103
104// Phase 1: Process instruction outputs to determine how each virtual register
105// is defined.
106void DefineOutputs(MidTierRegisterAllocationData* data);
107
108// Phase 2: Allocate registers to instructions.
109void AllocateRegisters(MidTierRegisterAllocationData* data);
110
111// Phase 3: assign spilled operands to specific spill slots.
112void AllocateSpillSlots(MidTierRegisterAllocationData* data);
113
114// Phase 4: Populate reference maps for spilled references.
115void PopulateReferenceMaps(MidTierRegisterAllocationData* data);
116
117}  // namespace compiler
118}  // namespace internal
119}  // namespace v8
120
121#endif  // V8_COMPILER_BACKEND_MID_TIER_REGISTER_ALLOCATOR_H_
122