Line data Source code
1 : // Copyright 2014 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_INSTRUCTION_SELECTOR_IMPL_H_
6 : #define V8_COMPILER_BACKEND_INSTRUCTION_SELECTOR_IMPL_H_
7 :
8 : #include "src/compiler/backend/instruction-selector.h"
9 : #include "src/compiler/backend/instruction.h"
10 : #include "src/compiler/common-operator.h"
11 : #include "src/compiler/linkage.h"
12 : #include "src/compiler/schedule.h"
13 : #include "src/macro-assembler.h"
14 :
15 : namespace v8 {
16 : namespace internal {
17 : namespace compiler {
18 :
19 : struct CaseInfo {
20 : int32_t value; // The case value.
21 : int32_t order; // The order for lowering to comparisons (less means earlier).
22 : BasicBlock* branch; // The basic blocks corresponding to the case value.
23 : };
24 :
25 : inline bool operator<(const CaseInfo& l, const CaseInfo& r) {
26 : return l.order < r.order;
27 : }
28 :
29 : // Helper struct containing data about a table or lookup switch.
30 : class SwitchInfo {
31 : public:
32 : SwitchInfo(ZoneVector<CaseInfo>& cases, int32_t min_value, int32_t max_value,
33 : BasicBlock* default_branch)
34 : : cases_(cases),
35 : min_value_(min_value),
36 : max_value_(min_value),
37 35237 : default_branch_(default_branch) {
38 35237 : if (cases.size() != 0) {
39 : DCHECK_LE(min_value, max_value);
40 : // Note that {value_range} can be 0 if {min_value} is -2^31 and
41 : // {max_value} is 2^31-1, so don't assume that it's non-zero below.
42 : value_range_ =
43 35237 : 1u + bit_cast<uint32_t>(max_value) - bit_cast<uint32_t>(min_value);
44 : } else {
45 0 : value_range_ = 0;
46 : }
47 : }
48 :
49 : // Ensure that comparison order of if-cascades is preserved.
50 0 : std::vector<CaseInfo> CasesSortedByOriginalOrder() const {
51 0 : std::vector<CaseInfo> result(cases_.begin(), cases_.end());
52 : std::stable_sort(result.begin(), result.end());
53 0 : return result;
54 : }
55 34907 : std::vector<CaseInfo> CasesSortedByValue() const {
56 34907 : std::vector<CaseInfo> result(cases_.begin(), cases_.end());
57 : std::stable_sort(result.begin(), result.end(),
58 : [](CaseInfo a, CaseInfo b) { return a.value < b.value; });
59 34908 : return result;
60 : }
61 : const ZoneVector<CaseInfo>& CasesUnsorted() const { return cases_; }
62 : int32_t min_value() const { return min_value_; }
63 : int32_t max_value() const { return max_value_; }
64 : size_t value_range() const { return value_range_; }
65 : size_t case_count() const { return cases_.size(); }
66 : BasicBlock* default_branch() const { return default_branch_; }
67 :
68 : private:
69 : const ZoneVector<CaseInfo>& cases_;
70 : int32_t min_value_; // minimum value of {cases_}
71 : int32_t max_value_; // maximum value of {cases_}
72 : size_t value_range_; // |max_value - min_value| + 1
73 : BasicBlock* default_branch_;
74 : };
75 :
76 : // A helper class for the instruction selector that simplifies construction of
77 : // Operands. This class implements a base for architecture-specific helpers.
78 : class OperandGenerator {
79 : public:
80 : explicit OperandGenerator(InstructionSelector* selector)
81 76898832 : : selector_(selector) {}
82 :
83 : InstructionOperand NoOutput() {
84 : return InstructionOperand(); // Generates an invalid operand.
85 : }
86 :
87 12081279 : InstructionOperand DefineAsRegister(Node* node) {
88 : return Define(node,
89 : UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
90 12081292 : GetVReg(node)));
91 : }
92 :
93 2730417 : InstructionOperand DefineSameAsFirst(Node* node) {
94 : return Define(node,
95 : UnallocatedOperand(UnallocatedOperand::SAME_AS_FIRST_INPUT,
96 2730424 : GetVReg(node)));
97 : }
98 :
99 97356 : InstructionOperand DefineAsFixed(Node* node, Register reg) {
100 : return Define(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
101 97378 : reg.code(), GetVReg(node)));
102 : }
103 :
104 : template <typename FPRegType>
105 3240 : InstructionOperand DefineAsFixed(Node* node, FPRegType reg) {
106 : return Define(node,
107 : UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
108 3240 : reg.code(), GetVReg(node)));
109 : }
110 :
111 14348565 : InstructionOperand DefineAsConstant(Node* node) {
112 14348565 : return DefineAsConstant(node, ToConstant(node));
113 : }
114 :
115 14349634 : InstructionOperand DefineAsConstant(Node* node, Constant constant) {
116 : selector()->MarkAsDefined(node);
117 : int virtual_register = GetVReg(node);
118 : sequence()->AddConstant(virtual_register, constant);
119 14350123 : return ConstantOperand(virtual_register);
120 : }
121 :
122 9474514 : InstructionOperand DefineAsLocation(Node* node, LinkageLocation location) {
123 18949365 : return Define(node, ToUnallocatedOperand(location, GetVReg(node)));
124 : }
125 :
126 554480 : InstructionOperand DefineAsDualLocation(Node* node,
127 : LinkageLocation primary_location,
128 : LinkageLocation secondary_location) {
129 : return Define(node,
130 : ToDualLocationUnallocatedOperand(
131 554497 : primary_location, secondary_location, GetVReg(node)));
132 : }
133 :
134 5454176 : InstructionOperand Use(Node* node) {
135 : return Use(node, UnallocatedOperand(UnallocatedOperand::NONE,
136 : UnallocatedOperand::USED_AT_START,
137 5454329 : GetVReg(node)));
138 : }
139 :
140 2310914 : InstructionOperand UseAnyAtEnd(Node* node) {
141 : return Use(node, UnallocatedOperand(UnallocatedOperand::REGISTER_OR_SLOT,
142 : UnallocatedOperand::USED_AT_END,
143 2310914 : GetVReg(node)));
144 : }
145 :
146 3013611 : InstructionOperand UseAny(Node* node) {
147 : return Use(node, UnallocatedOperand(UnallocatedOperand::REGISTER_OR_SLOT,
148 : UnallocatedOperand::USED_AT_START,
149 3013615 : GetVReg(node)));
150 : }
151 :
152 0 : InstructionOperand UseRegisterOrSlotOrConstant(Node* node) {
153 : return Use(node, UnallocatedOperand(
154 : UnallocatedOperand::REGISTER_OR_SLOT_OR_CONSTANT,
155 0 : UnallocatedOperand::USED_AT_START, GetVReg(node)));
156 : }
157 :
158 : InstructionOperand UseUniqueRegisterOrSlotOrConstant(Node* node) {
159 : return Use(node, UnallocatedOperand(
160 : UnallocatedOperand::REGISTER_OR_SLOT_OR_CONSTANT,
161 : GetVReg(node)));
162 : }
163 :
164 26968785 : InstructionOperand UseRegister(Node* node) {
165 : return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
166 : UnallocatedOperand::USED_AT_START,
167 26968604 : GetVReg(node)));
168 : }
169 :
170 13937131 : InstructionOperand UseUniqueSlot(Node* node) {
171 : return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_SLOT,
172 13937137 : GetVReg(node)));
173 : }
174 :
175 : // Use register or operand for the node. If a register is chosen, it won't
176 : // alias any temporary or output registers.
177 : InstructionOperand UseUnique(Node* node) {
178 : return Use(node,
179 : UnallocatedOperand(UnallocatedOperand::NONE, GetVReg(node)));
180 : }
181 :
182 : // Use a unique register for the node that does not alias any temporary or
183 : // output registers.
184 844442 : InstructionOperand UseUniqueRegister(Node* node) {
185 : return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
186 844644 : GetVReg(node)));
187 : }
188 :
189 168788 : InstructionOperand UseFixed(Node* node, Register reg) {
190 : return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
191 168790 : reg.code(), GetVReg(node)));
192 : }
193 :
194 : template <typename FPRegType>
195 3702 : InstructionOperand UseFixed(Node* node, FPRegType reg) {
196 : return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
197 3702 : reg.code(), GetVReg(node)));
198 : }
199 :
200 : InstructionOperand UseExplicit(LinkageLocation location) {
201 : MachineRepresentation rep = InstructionSequence::DefaultRepresentation();
202 : if (location.IsRegister()) {
203 : return ExplicitOperand(LocationOperand::REGISTER, rep,
204 : location.AsRegister());
205 : } else {
206 : return ExplicitOperand(LocationOperand::STACK_SLOT, rep,
207 : location.GetLocation());
208 : }
209 : }
210 :
211 160678 : InstructionOperand UseImmediate(int immediate) {
212 321381 : return sequence()->AddImmediate(Constant(immediate));
213 : }
214 :
215 30944170 : InstructionOperand UseImmediate(Node* node) {
216 61888022 : return sequence()->AddImmediate(ToConstant(node));
217 : }
218 :
219 0 : InstructionOperand UseNegatedImmediate(Node* node) {
220 0 : return sequence()->AddImmediate(ToNegatedConstant(node));
221 : }
222 :
223 23227951 : InstructionOperand UseLocation(Node* node, LinkageLocation location) {
224 46456299 : return Use(node, ToUnallocatedOperand(location, GetVReg(node)));
225 : }
226 :
227 : // Used to force gap moves from the from_location to the to_location
228 : // immediately before an instruction.
229 19444 : InstructionOperand UsePointerLocation(LinkageLocation to_location,
230 : LinkageLocation from_location) {
231 : UnallocatedOperand casted_from_operand =
232 38888 : UnallocatedOperand::cast(TempLocation(from_location));
233 19444 : selector_->Emit(kArchNop, casted_from_operand);
234 38888 : return ToUnallocatedOperand(to_location,
235 38888 : casted_from_operand.virtual_register());
236 : }
237 :
238 : InstructionOperand TempRegister() {
239 : return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
240 : UnallocatedOperand::USED_AT_START,
241 673793 : sequence()->NextVirtualRegister());
242 : }
243 :
244 : int AllocateVirtualRegister() { return sequence()->NextVirtualRegister(); }
245 :
246 : InstructionOperand DefineSameAsFirstForVreg(int vreg) {
247 : return UnallocatedOperand(UnallocatedOperand::SAME_AS_FIRST_INPUT, vreg);
248 : }
249 :
250 : InstructionOperand DefineAsRegistertForVreg(int vreg) {
251 : return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, vreg);
252 : }
253 :
254 : InstructionOperand UseRegisterForVreg(int vreg) {
255 : return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
256 : UnallocatedOperand::USED_AT_START, vreg);
257 : }
258 :
259 : InstructionOperand TempDoubleRegister() {
260 : UnallocatedOperand op = UnallocatedOperand(
261 : UnallocatedOperand::MUST_HAVE_REGISTER,
262 : UnallocatedOperand::USED_AT_START, sequence()->NextVirtualRegister());
263 : sequence()->MarkAsRepresentation(MachineRepresentation::kFloat64,
264 : op.virtual_register());
265 : return op;
266 : }
267 :
268 8 : InstructionOperand TempSimd128Register() {
269 : UnallocatedOperand op = UnallocatedOperand(
270 : UnallocatedOperand::MUST_HAVE_REGISTER,
271 8 : UnallocatedOperand::USED_AT_START, sequence()->NextVirtualRegister());
272 : sequence()->MarkAsRepresentation(MachineRepresentation::kSimd128,
273 8 : op.virtual_register());
274 8 : return op;
275 : }
276 :
277 : InstructionOperand TempRegister(Register reg) {
278 : return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER, reg.code(),
279 : InstructionOperand::kInvalidVirtualRegister);
280 : }
281 :
282 12334677 : InstructionOperand TempImmediate(int32_t imm) {
283 24669412 : return sequence()->AddImmediate(Constant(imm));
284 : }
285 :
286 19444 : InstructionOperand TempLocation(LinkageLocation location) {
287 19444 : return ToUnallocatedOperand(location, sequence()->NextVirtualRegister());
288 : }
289 :
290 : InstructionOperand Label(BasicBlock* block) {
291 41388897 : return sequence()->AddImmediate(
292 41389092 : Constant(RpoNumber::FromInt(block->rpo_number())));
293 : }
294 :
295 : protected:
296 203014158 : InstructionSelector* selector() const { return selector_; }
297 : InstructionSequence* sequence() const { return selector()->sequence(); }
298 : Zone* zone() const { return selector()->instruction_zone(); }
299 :
300 : private:
301 115220420 : int GetVReg(Node* node) const { return selector_->GetVirtualRegister(node); }
302 :
303 45293472 : static Constant ToConstant(const Node* node) {
304 45293472 : switch (node->opcode()) {
305 : case IrOpcode::kInt32Constant:
306 11393000 : return Constant(OpParameter<int32_t>(node->op()));
307 : case IrOpcode::kInt64Constant:
308 14056471 : return Constant(OpParameter<int64_t>(node->op()));
309 : case IrOpcode::kFloat32Constant:
310 225164 : return Constant(OpParameter<float>(node->op()));
311 : case IrOpcode::kRelocatableInt32Constant:
312 : case IrOpcode::kRelocatableInt64Constant:
313 192580 : return Constant(OpParameter<RelocatablePtrConstantInfo>(node->op()));
314 : case IrOpcode::kFloat64Constant:
315 : case IrOpcode::kNumberConstant:
316 2142851 : return Constant(OpParameter<double>(node->op()));
317 : case IrOpcode::kExternalConstant:
318 2358479 : return Constant(OpParameter<ExternalReference>(node->op()));
319 : case IrOpcode::kComment: {
320 : // We cannot use {intptr_t} here, since the Constant constructor would
321 : // be ambiguous on some architectures.
322 : using ptrsize_int_t =
323 : std::conditional<kSystemPointerSize == 8, int64_t, int32_t>::type;
324 : return Constant(reinterpret_cast<ptrsize_int_t>(
325 4 : OpParameter<const char*>(node->op())));
326 : }
327 : case IrOpcode::kHeapConstant:
328 15033361 : return Constant(HeapConstantOf(node->op()));
329 : case IrOpcode::kDelayedStringConstant:
330 4144 : return Constant(StringConstantBaseOf(node->op()));
331 : case IrOpcode::kDeadValue: {
332 0 : switch (DeadValueRepresentationOf(node->op())) {
333 : case MachineRepresentation::kBit:
334 : case MachineRepresentation::kWord32:
335 : case MachineRepresentation::kTagged:
336 : case MachineRepresentation::kTaggedSigned:
337 : case MachineRepresentation::kTaggedPointer:
338 : case MachineRepresentation::kCompressed:
339 : case MachineRepresentation::kCompressedSigned:
340 : case MachineRepresentation::kCompressedPointer:
341 0 : return Constant(static_cast<int32_t>(0));
342 : case MachineRepresentation::kFloat64:
343 0 : return Constant(static_cast<double>(0));
344 : case MachineRepresentation::kFloat32:
345 0 : return Constant(static_cast<float>(0));
346 : default:
347 0 : UNREACHABLE();
348 : }
349 : break;
350 : }
351 : default:
352 : break;
353 : }
354 0 : UNREACHABLE();
355 : }
356 :
357 0 : static Constant ToNegatedConstant(const Node* node) {
358 0 : switch (node->opcode()) {
359 : case IrOpcode::kInt32Constant:
360 0 : return Constant(-OpParameter<int32_t>(node->op()));
361 : case IrOpcode::kInt64Constant:
362 0 : return Constant(-OpParameter<int64_t>(node->op()));
363 : default:
364 : break;
365 : }
366 0 : UNREACHABLE();
367 : }
368 :
369 : UnallocatedOperand Define(Node* node, UnallocatedOperand operand) {
370 : DCHECK_NOT_NULL(node);
371 : DCHECK_EQ(operand.virtual_register(), GetVReg(node));
372 13718760 : selector()->MarkAsDefined(node);
373 : return operand;
374 : }
375 :
376 : UnallocatedOperand Use(Node* node, UnallocatedOperand operand) {
377 : DCHECK_NOT_NULL(node);
378 : DCHECK_EQ(operand.virtual_register(), GetVReg(node));
379 35588174 : selector()->MarkAsUsed(node);
380 : return operand;
381 : }
382 :
383 : UnallocatedOperand ToDualLocationUnallocatedOperand(
384 : LinkageLocation primary_location, LinkageLocation secondary_location,
385 : int virtual_register) {
386 : // We only support the primary location being a register and the secondary
387 : // one a slot.
388 : DCHECK(primary_location.IsRegister() &&
389 : secondary_location.IsCalleeFrameSlot());
390 : int reg_id = primary_location.AsRegister();
391 : int slot_id = secondary_location.AsCalleeFrameSlot();
392 : return UnallocatedOperand(reg_id, slot_id, virtual_register);
393 : }
394 :
395 32741303 : UnallocatedOperand ToUnallocatedOperand(LinkageLocation location,
396 : int virtual_register) {
397 32741303 : if (location.IsAnyRegister()) {
398 : // any machine register.
399 : return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
400 0 : virtual_register);
401 : }
402 32741303 : if (location.IsCallerFrameSlot()) {
403 : // a location on the caller frame.
404 : return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
405 4699794 : location.AsCallerFrameSlot(), virtual_register);
406 : }
407 28041509 : if (location.IsCalleeFrameSlot()) {
408 : // a spill location on this (callee) frame.
409 : return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
410 103269 : location.AsCalleeFrameSlot(), virtual_register);
411 : }
412 : // a fixed register.
413 27938240 : if (IsFloatingPoint(location.GetType().representation())) {
414 : return UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
415 397824 : location.AsRegister(), virtual_register);
416 : }
417 : return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
418 27540416 : location.AsRegister(), virtual_register);
419 : }
420 :
421 : InstructionSelector* selector_;
422 : };
423 :
424 : } // namespace compiler
425 : } // namespace internal
426 : } // namespace v8
427 :
428 : #endif // V8_COMPILER_BACKEND_INSTRUCTION_SELECTOR_IMPL_H_
|
