1// Copyright 2016 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_INTERPRETER_BYTECODE_REGISTER_OPTIMIZER_H_
6#define V8_INTERPRETER_BYTECODE_REGISTER_OPTIMIZER_H_
7
8#include "src/base/compiler-specific.h"
9#include "src/common/globals.h"
10#include "src/interpreter/bytecode-register-allocator.h"
11
12namespace v8 {
13namespace internal {
14namespace interpreter {
15
16// An optimization stage for eliminating unnecessary transfers between
17// registers. The bytecode generator uses temporary registers
18// liberally for correctness and convenience and this stage removes
19// transfers that are not required and preserves correctness.
20class V8_EXPORT_PRIVATE BytecodeRegisterOptimizer final
21    : public NON_EXPORTED_BASE(BytecodeRegisterAllocator::Observer),
22      public NON_EXPORTED_BASE(ZoneObject) {
23 public:
24  class BytecodeWriter {
25   public:
26    BytecodeWriter() = default;
27    virtual ~BytecodeWriter() = default;
28    BytecodeWriter(const BytecodeWriter&) = delete;
29    BytecodeWriter& operator=(const BytecodeWriter&) = delete;
30
31    // Called to emit a register transfer bytecode.
32    virtual void EmitLdar(Register input) = 0;
33    virtual void EmitStar(Register output) = 0;
34    virtual void EmitMov(Register input, Register output) = 0;
35  };
36
37  BytecodeRegisterOptimizer(Zone* zone,
38                            BytecodeRegisterAllocator* register_allocator,
39                            int fixed_registers_count, int parameter_count,
40                            BytecodeWriter* bytecode_writer);
41  ~BytecodeRegisterOptimizer() override = default;
42  BytecodeRegisterOptimizer(const BytecodeRegisterOptimizer&) = delete;
43  BytecodeRegisterOptimizer& operator=(const BytecodeRegisterOptimizer&) =
44      delete;
45
46  // Perform explicit register transfer operations.
47  void DoLdar(Register input) {
48    // TODO(rmcilroy): Avoid treating accumulator loads as clobbering the
49    // accumulator until the value is actually materialized in the accumulator.
50    RegisterInfo* input_info = GetRegisterInfo(input);
51    RegisterTransfer(input_info, accumulator_info_);
52  }
53  void DoStar(Register output) {
54    RegisterInfo* output_info = GetRegisterInfo(output);
55    RegisterTransfer(accumulator_info_, output_info);
56  }
57  void DoMov(Register input, Register output) {
58    RegisterInfo* input_info = GetRegisterInfo(input);
59    RegisterInfo* output_info = GetRegisterInfo(output);
60    RegisterTransfer(input_info, output_info);
61  }
62
63  // Materialize all live registers and flush equivalence sets.
64  void Flush();
65  bool EnsureAllRegistersAreFlushed() const;
66
67  // Prepares for |bytecode|.
68  template <Bytecode bytecode, ImplicitRegisterUse implicit_register_use>
69  V8_INLINE void PrepareForBytecode() {
70    if (Bytecodes::IsJump(bytecode) || Bytecodes::IsSwitch(bytecode) ||
71        bytecode == Bytecode::kDebugger ||
72        bytecode == Bytecode::kSuspendGenerator ||
73        bytecode == Bytecode::kResumeGenerator) {
74      // All state must be flushed before emitting
75      // - a jump bytecode (as the register equivalents at the jump target
76      //   aren't known)
77      // - a switch bytecode (as the register equivalents at the switch targets
78      //   aren't known)
79      // - a call to the debugger (as it can manipulate locals and parameters),
80      // - a generator suspend (as this involves saving all registers).
81      // - a generator register restore.
82      Flush();
83    }
84
85    // Materialize the accumulator if it is read by the bytecode. The
86    // accumulator is special and no other register can be materialized
87    // in it's place.
88    if (BytecodeOperands::ReadsAccumulator(implicit_register_use)) {
89      Materialize(accumulator_info_);
90    }
91
92    // Materialize an equivalent to the accumulator if it will be
93    // clobbered when the bytecode is dispatched.
94    if (BytecodeOperands::WritesAccumulator(implicit_register_use)) {
95      PrepareOutputRegister(accumulator_);
96    }
97  }
98
99  // Prepares |reg| for being used as an output operand.
100  void PrepareOutputRegister(Register reg);
101
102  // Prepares registers in |reg_list| for being used as an output operand.
103  void PrepareOutputRegisterList(RegisterList reg_list);
104
105  // Returns an equivalent register to |reg| to be used as an input operand.
106  Register GetInputRegister(Register reg);
107
108  // Returns an equivalent register list to |reg_list| to be used as an input
109  // operand.
110  RegisterList GetInputRegisterList(RegisterList reg_list);
111
112  int maxiumum_register_index() const { return max_register_index_; }
113
114 private:
115  static const uint32_t kInvalidEquivalenceId;
116
117  class RegisterInfo;
118
119  // BytecodeRegisterAllocator::Observer interface.
120  void RegisterAllocateEvent(Register reg) override;
121  void RegisterListAllocateEvent(RegisterList reg_list) override;
122  void RegisterListFreeEvent(RegisterList reg) override;
123
124  // Update internal state for register transfer from |input| to |output|
125  void RegisterTransfer(RegisterInfo* input, RegisterInfo* output);
126
127  // Emit a register transfer bytecode from |input| to |output|.
128  void OutputRegisterTransfer(RegisterInfo* input, RegisterInfo* output);
129
130  void CreateMaterializedEquivalent(RegisterInfo* info);
131  RegisterInfo* GetMaterializedEquivalent(RegisterInfo* info);
132  RegisterInfo* GetMaterializedEquivalentNotAccumulator(RegisterInfo* info);
133  void Materialize(RegisterInfo* info);
134  void AddToEquivalenceSet(RegisterInfo* set_member,
135                           RegisterInfo* non_set_member);
136
137  void PushToRegistersNeedingFlush(RegisterInfo* reg);
138  // Methods for finding and creating metadata for each register.
139  RegisterInfo* GetRegisterInfo(Register reg) {
140    size_t index = GetRegisterInfoTableIndex(reg);
141    DCHECK_LT(index, register_info_table_.size());
142    return register_info_table_[index];
143  }
144  RegisterInfo* GetOrCreateRegisterInfo(Register reg) {
145    size_t index = GetRegisterInfoTableIndex(reg);
146    return index < register_info_table_.size() ? register_info_table_[index]
147                                               : NewRegisterInfo(reg);
148  }
149  RegisterInfo* NewRegisterInfo(Register reg) {
150    size_t index = GetRegisterInfoTableIndex(reg);
151    DCHECK_GE(index, register_info_table_.size());
152    GrowRegisterMap(reg);
153    return register_info_table_[index];
154  }
155
156  void GrowRegisterMap(Register reg);
157
158  bool RegisterIsTemporary(Register reg) const {
159    return reg >= temporary_base_;
160  }
161
162  bool RegisterIsObservable(Register reg) const {
163    return reg != accumulator_ && !RegisterIsTemporary(reg);
164  }
165
166  static Register OperandToRegister(uint32_t operand) {
167    return Register::FromOperand(static_cast<int32_t>(operand));
168  }
169
170  size_t GetRegisterInfoTableIndex(Register reg) const {
171    return static_cast<size_t>(reg.index() + register_info_table_offset_);
172  }
173
174  Register RegisterFromRegisterInfoTableIndex(size_t index) const {
175    return Register(static_cast<int>(index) - register_info_table_offset_);
176  }
177
178  uint32_t NextEquivalenceId() {
179    equivalence_id_++;
180    // TODO(rmcilroy): use the same type for these and remove static_cast.
181    CHECK_NE(static_cast<size_t>(equivalence_id_), kInvalidEquivalenceId);
182    return equivalence_id_;
183  }
184
185  void AllocateRegister(RegisterInfo* info);
186
187  Zone* zone() { return zone_; }
188
189  const Register accumulator_;
190  RegisterInfo* accumulator_info_;
191  const Register temporary_base_;
192  int max_register_index_;
193
194  // Direct mapping to register info.
195  ZoneVector<RegisterInfo*> register_info_table_;
196  int register_info_table_offset_;
197
198  ZoneDeque<RegisterInfo*> registers_needing_flushed_;
199
200  // Counter for equivalence sets identifiers.
201  int equivalence_id_;
202
203  BytecodeWriter* bytecode_writer_;
204  bool flush_required_;
205  Zone* zone_;
206};
207
208}  // namespace interpreter
209}  // namespace internal
210}  // namespace v8
211
212#endif  // V8_INTERPRETER_BYTECODE_REGISTER_OPTIMIZER_H_
213