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 34179 : default_branch_(default_branch) {
38 34179 : 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 34179 : 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 33872 : std::vector<CaseInfo> CasesSortedByValue() const {
56 33872 : 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 33874 : 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 77868241 : : selector_(selector) {}
82 :
83 : InstructionOperand NoOutput() {
84 : return InstructionOperand(); // Generates an invalid operand.
85 : }
86 :
87 13130245 : InstructionOperand DefineAsRegister(Node* node) {
88 : return Define(node,
89 : UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
90 13130483 : GetVReg(node)));
91 : }
92 :
93 3034432 : InstructionOperand DefineSameAsFirst(Node* node) {
94 : return Define(node,
95 : UnallocatedOperand(UnallocatedOperand::SAME_AS_FIRST_INPUT,
96 3034500 : GetVReg(node)));
97 : }
98 :
99 97082 : InstructionOperand DefineAsFixed(Node* node, Register reg) {
100 : return Define(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
101 97082 : reg.code(), GetVReg(node)));
102 : }
103 :
104 : template <typename FPRegType>
105 3273 : InstructionOperand DefineAsFixed(Node* node, FPRegType reg) {
106 : return Define(node,
107 : UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
108 3273 : reg.code(), GetVReg(node)));
109 : }
110 :
111 14062565 : InstructionOperand DefineAsConstant(Node* node) {
112 14062565 : return DefineAsConstant(node, ToConstant(node));
113 : }
114 :
115 14063321 : InstructionOperand DefineAsConstant(Node* node, Constant constant) {
116 : selector()->MarkAsDefined(node);
117 : int virtual_register = GetVReg(node);
118 : sequence()->AddConstant(virtual_register, constant);
119 14063707 : return ConstantOperand(virtual_register);
120 : }
121 :
122 9518851 : InstructionOperand DefineAsLocation(Node* node, LinkageLocation location) {
123 19037870 : return Define(node, ToUnallocatedOperand(location, GetVReg(node)));
124 : }
125 :
126 441680 : InstructionOperand DefineAsDualLocation(Node* node,
127 : LinkageLocation primary_location,
128 : LinkageLocation secondary_location) {
129 : return Define(node,
130 : ToDualLocationUnallocatedOperand(
131 441682 : primary_location, secondary_location, GetVReg(node)));
132 : }
133 :
134 6441792 : InstructionOperand Use(Node* node) {
135 : return Use(node, UnallocatedOperand(UnallocatedOperand::NONE,
136 : UnallocatedOperand::USED_AT_START,
137 6441977 : GetVReg(node)));
138 : }
139 :
140 2333793 : InstructionOperand UseAnyAtEnd(Node* node) {
141 : return Use(node, UnallocatedOperand(UnallocatedOperand::REGISTER_OR_SLOT,
142 : UnallocatedOperand::USED_AT_END,
143 2333792 : GetVReg(node)));
144 : }
145 :
146 2748492 : InstructionOperand UseAny(Node* node) {
147 : return Use(node, UnallocatedOperand(UnallocatedOperand::REGISTER_OR_SLOT,
148 : UnallocatedOperand::USED_AT_START,
149 2748501 : 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 27605345 : InstructionOperand UseRegister(Node* node) {
165 : return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
166 : UnallocatedOperand::USED_AT_START,
167 27605736 : GetVReg(node)));
168 : }
169 :
170 14922485 : InstructionOperand UseUniqueSlot(Node* node) {
171 : return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_SLOT,
172 14922502 : 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 860100 : InstructionOperand UseUniqueRegister(Node* node) {
185 : return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
186 860191 : GetVReg(node)));
187 : }
188 :
189 168532 : InstructionOperand UseFixed(Node* node, Register reg) {
190 : return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
191 168534 : reg.code(), GetVReg(node)));
192 : }
193 :
194 : template <typename FPRegType>
195 3738 : InstructionOperand UseFixed(Node* node, FPRegType reg) {
196 : return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
197 3738 : 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 52933 : InstructionOperand UseImmediate(int immediate) {
212 105874 : return sequence()->AddImmediate(Constant(immediate));
213 : }
214 :
215 31789931 : InstructionOperand UseImmediate(Node* node) {
216 63580209 : return sequence()->AddImmediate(ToConstant(node));
217 : }
218 :
219 0 : InstructionOperand UseNegatedImmediate(Node* node) {
220 0 : return sequence()->AddImmediate(ToNegatedConstant(node));
221 : }
222 :
223 23827595 : InstructionOperand UseLocation(Node* node, LinkageLocation location) {
224 47654345 : 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 19272 : InstructionOperand UsePointerLocation(LinkageLocation to_location,
230 : LinkageLocation from_location) {
231 : UnallocatedOperand casted_from_operand =
232 38544 : UnallocatedOperand::cast(TempLocation(from_location));
233 19272 : selector_->Emit(kArchNop, casted_from_operand);
234 38544 : return ToUnallocatedOperand(to_location,
235 38544 : casted_from_operand.virtual_register());
236 : }
237 :
238 : InstructionOperand TempRegister() {
239 : return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
240 : UnallocatedOperand::USED_AT_START,
241 687663 : 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 11833056 : InstructionOperand TempImmediate(int32_t imm) {
283 23666128 : return sequence()->AddImmediate(Constant(imm));
284 : }
285 :
286 19272 : InstructionOperand TempLocation(LinkageLocation location) {
287 19272 : return ToUnallocatedOperand(location, sequence()->NextVirtualRegister());
288 : }
289 :
290 : InstructionOperand Label(BasicBlock* block) {
291 42390399 : return sequence()->AddImmediate(
292 42390528 : Constant(RpoNumber::FromInt(block->rpo_number())));
293 : }
294 :
295 : protected:
296 206544969 : InstructionSelector* selector() const { return selector_; }
297 : InstructionSequence* sequence() const { return selector()->sequence(); }
298 : Zone* zone() const { return selector()->instruction_zone(); }
299 :
300 : private:
301 119200756 : int GetVReg(Node* node) const { return selector_->GetVirtualRegister(node); }
302 :
303 45852484 : static Constant ToConstant(const Node* node) {
304 45852484 : switch (node->opcode()) {
305 : case IrOpcode::kInt32Constant:
306 10718032 : return Constant(OpParameter<int32_t>(node->op()));
307 : case IrOpcode::kInt64Constant:
308 14750580 : return Constant(OpParameter<int64_t>(node->op()));
309 : case IrOpcode::kFloat32Constant:
310 20758 : return Constant(OpParameter<float>(node->op()));
311 : case IrOpcode::kRelocatableInt32Constant:
312 : case IrOpcode::kRelocatableInt64Constant:
313 93151 : return Constant(OpParameter<RelocatablePtrConstantInfo>(node->op()));
314 : case IrOpcode::kFloat64Constant:
315 : case IrOpcode::kNumberConstant:
316 2041776 : return Constant(OpParameter<double>(node->op()));
317 : case IrOpcode::kExternalConstant:
318 2587806 : 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 15646641 : return Constant(HeapConstantOf(node->op()));
329 : case IrOpcode::kDelayedStringConstant:
330 4115 : 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 14898118 : 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 10373144 : 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 33384202 : UnallocatedOperand ToUnallocatedOperand(LinkageLocation location,
396 : int virtual_register) {
397 33384202 : if (location.IsAnyRegister()) {
398 : // any machine register.
399 : return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
400 0 : virtual_register);
401 : }
402 33384202 : if (location.IsCallerFrameSlot()) {
403 : // a location on the caller frame.
404 : return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
405 4810163 : location.AsCallerFrameSlot(), virtual_register);
406 : }
407 28574039 : if (location.IsCalleeFrameSlot()) {
408 : // a spill location on this (callee) frame.
409 : return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
410 103102 : location.AsCalleeFrameSlot(), virtual_register);
411 : }
412 : // a fixed register.
413 28470937 : if (IsFloatingPoint(location.GetType().representation())) {
414 : return UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
415 136798 : location.AsRegister(), virtual_register);
416 : }
417 : return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
418 28334139 : 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_
|
