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