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 35036 : default_branch_(default_branch) {
38 70072 : 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 35036 : 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 0 : std::stable_sort(result.begin(), result.end());
53 0 : return result;
54 : }
55 34722 : std::vector<CaseInfo> CasesSortedByValue() const {
56 34722 : std::vector<CaseInfo> result(cases_.begin(), cases_.end());
57 : std::stable_sort(result.begin(), result.end(),
58 34722 : [](CaseInfo a, CaseInfo b) { return a.value < b.value; });
59 34722 : 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 49230 : 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 86176396 : : selector_(selector) {}
82 :
83 : InstructionOperand NoOutput() {
84 : return InstructionOperand(); // Generates an invalid operand.
85 : }
86 :
87 10560145 : InstructionOperand DefineAsRegister(Node* node) {
88 : return Define(node,
89 : UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
90 10560264 : GetVReg(node)));
91 : }
92 :
93 2777677 : InstructionOperand DefineSameAsFirst(Node* node) {
94 : return Define(node,
95 : UnallocatedOperand(UnallocatedOperand::SAME_AS_FIRST_INPUT,
96 2777678 : GetVReg(node)));
97 : }
98 :
99 95854 : InstructionOperand DefineAsFixed(Node* node, Register reg) {
100 : return Define(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
101 95864 : reg.code(), GetVReg(node)));
102 : }
103 :
104 : template <typename FPRegType>
105 3267 : InstructionOperand DefineAsFixed(Node* node, FPRegType reg) {
106 : return Define(node,
107 : UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
108 3267 : reg.code(), GetVReg(node)));
109 : }
110 :
111 12527776 : InstructionOperand DefineAsConstant(Node* node) {
112 12527776 : return DefineAsConstant(node, ToConstant(node));
113 : }
114 :
115 12527768 : InstructionOperand DefineAsConstant(Node* node, Constant constant) {
116 : selector()->MarkAsDefined(node);
117 : int virtual_register = GetVReg(node);
118 : sequence()->AddConstant(virtual_register, constant);
119 12527871 : return ConstantOperand(virtual_register);
120 : }
121 :
122 9030007 : InstructionOperand DefineAsLocation(Node* node, LinkageLocation location) {
123 18060048 : return Define(node, ToUnallocatedOperand(location, GetVReg(node)));
124 : }
125 :
126 73098 : InstructionOperand DefineAsDualLocation(Node* node,
127 73100 : LinkageLocation primary_location,
128 73100 : LinkageLocation secondary_location) {
129 : return Define(node,
130 : ToDualLocationUnallocatedOperand(
131 73100 : primary_location, secondary_location, GetVReg(node)));
132 : }
133 :
134 5312131 : InstructionOperand Use(Node* node) {
135 : return Use(node, UnallocatedOperand(UnallocatedOperand::NONE,
136 : UnallocatedOperand::USED_AT_START,
137 5312191 : GetVReg(node)));
138 : }
139 :
140 2379407 : InstructionOperand UseAnyAtEnd(Node* node) {
141 : return Use(node, UnallocatedOperand(UnallocatedOperand::REGISTER_OR_SLOT,
142 : UnallocatedOperand::USED_AT_END,
143 2379411 : GetVReg(node)));
144 : }
145 :
146 2919823 : InstructionOperand UseAny(Node* node) {
147 : return Use(node, UnallocatedOperand(UnallocatedOperand::REGISTER_OR_SLOT,
148 : UnallocatedOperand::USED_AT_START,
149 2919824 : 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 25582976 : InstructionOperand UseRegister(Node* node) {
165 : return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
166 : UnallocatedOperand::USED_AT_START,
167 25583116 : GetVReg(node)));
168 : }
169 :
170 14781641 : InstructionOperand UseUniqueSlot(Node* node) {
171 : return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_SLOT,
172 14781665 : 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 854786 : InstructionOperand UseUniqueRegister(Node* node) {
185 : return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
186 854804 : GetVReg(node)));
187 : }
188 :
189 168345 : InstructionOperand UseFixed(Node* node, Register reg) {
190 : return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
191 168345 : reg.code(), GetVReg(node)));
192 : }
193 :
194 : template <typename FPRegType>
195 3732 : InstructionOperand UseFixed(Node* node, FPRegType reg) {
196 : return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
197 3732 : 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 61080 : InstructionOperand UseImmediate(int immediate) {
212 122161 : return sequence()->AddImmediate(Constant(immediate));
213 : }
214 :
215 29950612 : InstructionOperand UseImmediate(Node* node) {
216 59901128 : return sequence()->AddImmediate(ToConstant(node));
217 : }
218 :
219 0 : InstructionOperand UseNegatedImmediate(Node* node) {
220 0 : return sequence()->AddImmediate(ToNegatedConstant(node));
221 : }
222 :
223 21619060 : InstructionOperand UseLocation(Node* node, LinkageLocation location) {
224 43238112 : 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 18436 : InstructionOperand UsePointerLocation(LinkageLocation to_location,
230 : LinkageLocation from_location) {
231 : UnallocatedOperand casted_from_operand =
232 36872 : UnallocatedOperand::cast(TempLocation(from_location));
233 18436 : selector_->Emit(kArchNop, casted_from_operand);
234 : return ToUnallocatedOperand(to_location,
235 18436 : casted_from_operand.virtual_register());
236 : }
237 :
238 : InstructionOperand TempRegister() {
239 : return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
240 : UnallocatedOperand::USED_AT_START,
241 681266 : 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 12069119 : InstructionOperand TempImmediate(int32_t imm) {
283 24138251 : return sequence()->AddImmediate(Constant(imm));
284 : }
285 :
286 18436 : InstructionOperand TempLocation(LinkageLocation location) {
287 18436 : return ToUnallocatedOperand(location, sequence()->NextVirtualRegister());
288 : }
289 :
290 20705328 : InstructionOperand Label(BasicBlock* block) {
291 : return sequence()->AddImmediate(
292 20705328 : Constant(RpoNumber::FromInt(block->rpo_number())));
293 : }
294 :
295 : protected:
296 201857696 : InstructionSelector* selector() const { return selector_; }
297 76013615 : InstructionSequence* sequence() const { return selector()->sequence(); }
298 : Zone* zone() const { return selector()->instruction_zone(); }
299 :
300 : private:
301 108689717 : int GetVReg(Node* node) const { return selector_->GetVirtualRegister(node); }
302 :
303 42478582 : static Constant ToConstant(const Node* node) {
304 42478582 : switch (node->opcode()) {
305 : case IrOpcode::kInt32Constant:
306 9478048 : return Constant(OpParameter<int32_t>(node->op()));
307 : case IrOpcode::kInt64Constant:
308 14113396 : return Constant(OpParameter<int64_t>(node->op()));
309 : case IrOpcode::kFloat32Constant:
310 20688 : return Constant(OpParameter<float>(node->op()));
311 : case IrOpcode::kRelocatableInt32Constant:
312 : case IrOpcode::kRelocatableInt64Constant:
313 80800 : return Constant(OpParameter<RelocatablePtrConstantInfo>(node->op()));
314 : case IrOpcode::kFloat64Constant:
315 : case IrOpcode::kNumberConstant:
316 2564004 : return Constant(OpParameter<double>(node->op()));
317 : case IrOpcode::kExternalConstant:
318 1992817 : 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 15517024 : return Constant(HeapConstantOf(node->op()));
329 : case IrOpcode::kDelayedStringConstant:
330 8294 : 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 0 : return Constant(static_cast<int32_t>(0));
339 : case MachineRepresentation::kFloat64:
340 0 : return Constant(static_cast<double>(0));
341 : case MachineRepresentation::kFloat32:
342 0 : return Constant(static_cast<float>(0));
343 : default:
344 0 : UNREACHABLE();
345 : }
346 : break;
347 : }
348 : default:
349 : break;
350 : }
351 0 : UNREACHABLE();
352 : }
353 :
354 0 : static Constant ToNegatedConstant(const Node* node) {
355 0 : switch (node->opcode()) {
356 : case IrOpcode::kInt32Constant:
357 0 : return Constant(-OpParameter<int32_t>(node->op()));
358 : case IrOpcode::kInt64Constant:
359 0 : return Constant(-OpParameter<int64_t>(node->op()));
360 : default:
361 : break;
362 : }
363 0 : UNREACHABLE();
364 : }
365 :
366 : UnallocatedOperand Define(Node* node, UnallocatedOperand operand) {
367 : DCHECK_NOT_NULL(node);
368 : DCHECK_EQ(operand.virtual_register(), GetVReg(node));
369 12255840 : selector()->MarkAsDefined(node);
370 : return operand;
371 : }
372 :
373 : UnallocatedOperand Use(Node* node, UnallocatedOperand operand) {
374 : DCHECK_NOT_NULL(node);
375 : DCHECK_EQ(operand.virtual_register(), GetVReg(node));
376 8534955 : selector()->MarkAsUsed(node);
377 : return operand;
378 : }
379 :
380 : UnallocatedOperand ToDualLocationUnallocatedOperand(
381 : LinkageLocation primary_location, LinkageLocation secondary_location,
382 : int virtual_register) {
383 : // We only support the primary location being a register and the secondary
384 : // one a slot.
385 : DCHECK(primary_location.IsRegister() &&
386 : secondary_location.IsCalleeFrameSlot());
387 : int reg_id = primary_location.AsRegister();
388 : int slot_id = secondary_location.AsCalleeFrameSlot();
389 : return UnallocatedOperand(reg_id, slot_id, virtual_register);
390 : }
391 :
392 30685935 : UnallocatedOperand ToUnallocatedOperand(LinkageLocation location,
393 : int virtual_register) {
394 30685935 : if (location.IsAnyRegister()) {
395 : // any machine register.
396 : return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
397 0 : virtual_register);
398 : }
399 30685935 : if (location.IsCallerFrameSlot()) {
400 : // a location on the caller frame.
401 : return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
402 4207117 : location.AsCallerFrameSlot(), virtual_register);
403 : }
404 26478818 : if (location.IsCalleeFrameSlot()) {
405 : // a spill location on this (callee) frame.
406 : return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
407 98716 : location.AsCalleeFrameSlot(), virtual_register);
408 : }
409 : // a fixed register.
410 26380102 : if (IsFloatingPoint(location.GetType().representation())) {
411 : return UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
412 130936 : location.AsRegister(), virtual_register);
413 : }
414 : return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
415 26249166 : location.AsRegister(), virtual_register);
416 : }
417 :
418 : InstructionSelector* selector_;
419 : };
420 :
421 : } // namespace compiler
422 : } // namespace internal
423 : } // namespace v8
424 :
425 : #endif // V8_COMPILER_BACKEND_INSTRUCTION_SELECTOR_IMPL_H_
|
