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_INSTRUCTION_SELECTOR_IMPL_H_
6 : #define V8_COMPILER_INSTRUCTION_SELECTOR_IMPL_H_
7 :
8 : #include "src/compiler/instruction-selector.h"
9 : #include "src/compiler/instruction.h"
10 : #include "src/compiler/linkage.h"
11 : #include "src/compiler/schedule.h"
12 : #include "src/macro-assembler.h"
13 :
14 : namespace v8 {
15 : namespace internal {
16 : namespace compiler {
17 :
18 : // Helper struct containing data about a table or lookup switch.
19 : struct SwitchInfo {
20 : int32_t min_value; // minimum value of {case_values}
21 : int32_t max_value; // maximum value of {case_values}
22 : size_t value_range; // |max_value - min_value| + 1
23 : size_t case_count; // number of cases
24 : int32_t* case_values; // actual case values, unsorted
25 : BasicBlock** case_branches; // basic blocks corresponding to case values
26 : BasicBlock* default_branch; // default branch target
27 : };
28 :
29 : // A helper class for the instruction selector that simplifies construction of
30 : // Operands. This class implements a base for architecture-specific helpers.
31 : class OperandGenerator {
32 : public:
33 : explicit OperandGenerator(InstructionSelector* selector)
34 54523807 : : selector_(selector) {}
35 :
36 : InstructionOperand NoOutput() {
37 : return InstructionOperand(); // Generates an invalid operand.
38 : }
39 :
40 6147313 : InstructionOperand DefineAsRegister(Node* node) {
41 : return Define(node,
42 : UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
43 6147385 : GetVReg(node)));
44 : }
45 :
46 1709688 : InstructionOperand DefineSameAsFirst(Node* node) {
47 : return Define(node,
48 : UnallocatedOperand(UnallocatedOperand::SAME_AS_FIRST_INPUT,
49 1709696 : GetVReg(node)));
50 : }
51 :
52 16560 : InstructionOperand DefineAsFixed(Node* node, Register reg) {
53 : return Define(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
54 16560 : reg.code(), GetVReg(node)));
55 : }
56 :
57 : template <typename FPRegType>
58 2115 : InstructionOperand DefineAsFixed(Node* node, FPRegType reg) {
59 : return Define(node,
60 : UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
61 2115 : reg.code(), GetVReg(node)));
62 : }
63 :
64 10069103 : InstructionOperand DefineAsConstant(Node* node) {
65 10069103 : return DefineAsConstant(node, ToConstant(node));
66 : }
67 :
68 10069124 : InstructionOperand DefineAsConstant(Node* node, Constant constant) {
69 : selector()->MarkAsDefined(node);
70 : int virtual_register = GetVReg(node);
71 : sequence()->AddConstant(virtual_register, constant);
72 10069119 : return ConstantOperand(virtual_register);
73 : }
74 :
75 6658845 : InstructionOperand DefineAsLocation(Node* node, LinkageLocation location) {
76 13317770 : return Define(node, ToUnallocatedOperand(location, GetVReg(node)));
77 : }
78 :
79 493943 : InstructionOperand DefineAsDualLocation(Node* node,
80 493943 : LinkageLocation primary_location,
81 493943 : LinkageLocation secondary_location) {
82 : return Define(node,
83 : ToDualLocationUnallocatedOperand(
84 493943 : primary_location, secondary_location, GetVReg(node)));
85 : }
86 :
87 7050030 : InstructionOperand Use(Node* node) {
88 : return Use(node, UnallocatedOperand(UnallocatedOperand::NONE,
89 : UnallocatedOperand::USED_AT_START,
90 7050077 : GetVReg(node)));
91 : }
92 :
93 2443030 : InstructionOperand UseAnyAtEnd(Node* node) {
94 : return Use(node, UnallocatedOperand(UnallocatedOperand::ANY,
95 : UnallocatedOperand::USED_AT_END,
96 2443038 : GetVReg(node)));
97 : }
98 :
99 12192 : InstructionOperand UseAny(Node* node) {
100 : return Use(node, UnallocatedOperand(UnallocatedOperand::ANY,
101 : UnallocatedOperand::USED_AT_START,
102 12192 : GetVReg(node)));
103 : }
104 :
105 13053208 : InstructionOperand UseRegister(Node* node) {
106 : return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
107 : UnallocatedOperand::USED_AT_START,
108 13053301 : GetVReg(node)));
109 : }
110 :
111 13401913 : InstructionOperand UseUniqueSlot(Node* node) {
112 : return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_SLOT,
113 13401919 : GetVReg(node)));
114 : }
115 :
116 : // Use register or operand for the node. If a register is chosen, it won't
117 : // alias any temporary or output registers.
118 : InstructionOperand UseUnique(Node* node) {
119 : return Use(node,
120 : UnallocatedOperand(UnallocatedOperand::NONE, GetVReg(node)));
121 : }
122 :
123 : // Use a unique register for the node that does not alias any temporary or
124 : // output registers.
125 686140 : InstructionOperand UseUniqueRegister(Node* node) {
126 : return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
127 686142 : GetVReg(node)));
128 : }
129 :
130 23346 : InstructionOperand UseFixed(Node* node, Register reg) {
131 : return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
132 23346 : reg.code(), GetVReg(node)));
133 : }
134 :
135 : template <typename FPRegType>
136 2346 : InstructionOperand UseFixed(Node* node, FPRegType reg) {
137 : return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
138 2346 : reg.code(), GetVReg(node)));
139 : }
140 :
141 : InstructionOperand UseExplicit(LinkageLocation location) {
142 : MachineRepresentation rep = InstructionSequence::DefaultRepresentation();
143 : if (location.IsRegister()) {
144 : return ExplicitOperand(LocationOperand::REGISTER, rep,
145 : location.AsRegister());
146 : } else {
147 : return ExplicitOperand(LocationOperand::STACK_SLOT, rep,
148 : location.GetLocation());
149 : }
150 : }
151 :
152 204139 : InstructionOperand UseImmediate(int immediate) {
153 408294 : return sequence()->AddImmediate(Constant(immediate));
154 : }
155 :
156 20278649 : InstructionOperand UseImmediate(Node* node) {
157 40557283 : return sequence()->AddImmediate(ToConstant(node));
158 : }
159 :
160 16118 : InstructionOperand UseNegatedImmediate(Node* node) {
161 32236 : return sequence()->AddImmediate(ToNegatedConstant(node));
162 : }
163 :
164 20335933 : InstructionOperand UseLocation(Node* node, LinkageLocation location) {
165 40671998 : return Use(node, ToUnallocatedOperand(location, GetVReg(node)));
166 : }
167 :
168 : // Used to force gap moves from the from_location to the to_location
169 : // immediately before an instruction.
170 13799 : InstructionOperand UsePointerLocation(LinkageLocation to_location,
171 : LinkageLocation from_location) {
172 : UnallocatedOperand casted_from_operand =
173 27598 : UnallocatedOperand::cast(TempLocation(from_location));
174 13799 : selector_->Emit(kArchNop, casted_from_operand);
175 : return ToUnallocatedOperand(to_location,
176 13799 : casted_from_operand.virtual_register());
177 : }
178 :
179 : InstructionOperand TempRegister() {
180 : return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
181 : UnallocatedOperand::USED_AT_START,
182 654683 : sequence()->NextVirtualRegister());
183 : }
184 :
185 : int AllocateVirtualRegister() { return sequence()->NextVirtualRegister(); }
186 :
187 : InstructionOperand DefineSameAsFirstForVreg(int vreg) {
188 : return UnallocatedOperand(UnallocatedOperand::SAME_AS_FIRST_INPUT, vreg);
189 : }
190 :
191 : InstructionOperand DefineAsRegistertForVreg(int vreg) {
192 : return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, vreg);
193 : }
194 :
195 : InstructionOperand UseRegisterForVreg(int vreg) {
196 : return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
197 : UnallocatedOperand::USED_AT_START, vreg);
198 : }
199 :
200 : InstructionOperand TempDoubleRegister() {
201 : UnallocatedOperand op = UnallocatedOperand(
202 : UnallocatedOperand::MUST_HAVE_REGISTER,
203 : UnallocatedOperand::USED_AT_START, sequence()->NextVirtualRegister());
204 : sequence()->MarkAsRepresentation(MachineRepresentation::kFloat64,
205 : op.virtual_register());
206 : return op;
207 : }
208 :
209 : InstructionOperand TempRegister(Register reg) {
210 : return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER, reg.code(),
211 : InstructionOperand::kInvalidVirtualRegister);
212 : }
213 :
214 5589144 : InstructionOperand TempImmediate(int32_t imm) {
215 11178332 : return sequence()->AddImmediate(Constant(imm));
216 : }
217 :
218 13799 : InstructionOperand TempLocation(LinkageLocation location) {
219 13799 : return ToUnallocatedOperand(location, sequence()->NextVirtualRegister());
220 : }
221 :
222 14046303 : InstructionOperand Label(BasicBlock* block) {
223 : return sequence()->AddImmediate(
224 14046303 : Constant(RpoNumber::FromInt(block->rpo_number())));
225 : }
226 :
227 : protected:
228 142072771 : InstructionSelector* selector() const { return selector_; }
229 50872005 : InstructionSequence* sequence() const { return selector()->sequence(); }
230 : Zone* zone() const { return selector()->instruction_zone(); }
231 :
232 : private:
233 82105726 : int GetVReg(Node* node) const { return selector_->GetVirtualRegister(node); }
234 :
235 30347859 : static Constant ToConstant(const Node* node) {
236 30347859 : switch (node->opcode()) {
237 : case IrOpcode::kInt32Constant:
238 4868906 : return Constant(OpParameter<int32_t>(node));
239 : case IrOpcode::kInt64Constant:
240 7822873 : return Constant(OpParameter<int64_t>(node));
241 : case IrOpcode::kFloat32Constant:
242 271838 : return Constant(OpParameter<float>(node));
243 : case IrOpcode::kRelocatableInt32Constant:
244 : case IrOpcode::kRelocatableInt64Constant:
245 184623 : return Constant(OpParameter<RelocatablePtrConstantInfo>(node));
246 : case IrOpcode::kFloat64Constant:
247 : case IrOpcode::kNumberConstant:
248 7276362 : return Constant(OpParameter<double>(node));
249 : case IrOpcode::kExternalConstant:
250 : case IrOpcode::kComment:
251 1063451 : return Constant(OpParameter<ExternalReference>(node));
252 : case IrOpcode::kHeapConstant:
253 12633906 : return Constant(OpParameter<Handle<HeapObject>>(node));
254 : default:
255 : break;
256 : }
257 0 : UNREACHABLE();
258 : }
259 :
260 16118 : static Constant ToNegatedConstant(const Node* node) {
261 16118 : switch (node->opcode()) {
262 : case IrOpcode::kInt32Constant:
263 3720 : return Constant(-OpParameter<int32_t>(node));
264 : case IrOpcode::kInt64Constant:
265 12398 : return Constant(-OpParameter<int64_t>(node));
266 : default:
267 : break;
268 : }
269 0 : UNREACHABLE();
270 : }
271 :
272 : UnallocatedOperand Define(Node* node, UnallocatedOperand operand) {
273 : DCHECK_NOT_NULL(node);
274 : DCHECK_EQ(operand.virtual_register(), GetVReg(node));
275 7416261 : selector()->MarkAsDefined(node);
276 : return operand;
277 : }
278 :
279 : UnallocatedOperand Use(Node* node, UnallocatedOperand operand) {
280 : DCHECK_NOT_NULL(node);
281 : DCHECK_EQ(operand.virtual_register(), GetVReg(node));
282 20351384 : selector()->MarkAsUsed(node);
283 : return operand;
284 : }
285 :
286 : UnallocatedOperand ToDualLocationUnallocatedOperand(
287 : LinkageLocation primary_location, LinkageLocation secondary_location,
288 : int virtual_register) {
289 : // We only support the primary location being a register and the secondary
290 : // one a slot.
291 : DCHECK(primary_location.IsRegister() &&
292 : secondary_location.IsCalleeFrameSlot());
293 : int reg_id = primary_location.AsRegister();
294 : int slot_id = secondary_location.AsCalleeFrameSlot();
295 : return UnallocatedOperand(reg_id, slot_id, virtual_register);
296 : }
297 :
298 27022453 : UnallocatedOperand ToUnallocatedOperand(LinkageLocation location,
299 : int virtual_register) {
300 27022453 : if (location.IsAnyRegister()) {
301 : // any machine register.
302 : return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
303 0 : virtual_register);
304 : }
305 27022453 : if (location.IsCallerFrameSlot()) {
306 : // a location on the caller frame.
307 : return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
308 4807485 : location.AsCallerFrameSlot(), virtual_register);
309 : }
310 22214968 : if (location.IsCalleeFrameSlot()) {
311 : // a spill location on this (callee) frame.
312 : return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
313 87528 : location.AsCalleeFrameSlot(), virtual_register);
314 : }
315 : // a fixed register.
316 22127440 : if (IsFloatingPoint(location.GetType().representation())) {
317 : return UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
318 1011871 : location.AsRegister(), virtual_register);
319 : }
320 : return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
321 21115569 : location.AsRegister(), virtual_register);
322 : }
323 :
324 : InstructionSelector* selector_;
325 : };
326 :
327 :
328 : // The flags continuation is a way to combine a branch or a materialization
329 : // of a boolean value with an instruction that sets the flags register.
330 : // The whole instruction is treated as a unit by the register allocator, and
331 : // thus no spills or moves can be introduced between the flags-setting
332 : // instruction and the branch or set it should be combined with.
333 : class FlagsContinuation final {
334 : public:
335 403855 : FlagsContinuation() : mode_(kFlags_none) {}
336 :
337 : // Creates a new flags continuation from the given condition and true/false
338 : // blocks.
339 : FlagsContinuation(FlagsCondition condition, BasicBlock* true_block,
340 : BasicBlock* false_block)
341 : : mode_(kFlags_branch),
342 : condition_(condition),
343 : true_block_(true_block),
344 3610801 : false_block_(false_block) {
345 : DCHECK_NOT_NULL(true_block);
346 : DCHECK_NOT_NULL(false_block);
347 : }
348 :
349 : // Creates a new flags continuation for an eager deoptimization exit.
350 : static FlagsContinuation ForDeoptimize(FlagsCondition condition,
351 : DeoptimizeKind kind,
352 : DeoptimizeReason reason,
353 : Node* frame_state) {
354 : return FlagsContinuation(condition, kind, reason, frame_state);
355 : }
356 :
357 : // Creates a new flags continuation for a boolean value.
358 : static FlagsContinuation ForSet(FlagsCondition condition, Node* result) {
359 : return FlagsContinuation(condition, result);
360 : }
361 :
362 : // Creates a new flags continuation for a wasm trap.
363 : static FlagsContinuation ForTrap(FlagsCondition condition,
364 : Runtime::FunctionId trap_id, Node* result) {
365 : return FlagsContinuation(condition, trap_id, result);
366 : }
367 :
368 : bool IsNone() const { return mode_ == kFlags_none; }
369 : bool IsBranch() const { return mode_ == kFlags_branch; }
370 : bool IsDeoptimize() const { return mode_ == kFlags_deoptimize; }
371 : bool IsSet() const { return mode_ == kFlags_set; }
372 : bool IsTrap() const { return mode_ == kFlags_trap; }
373 : FlagsCondition condition() const {
374 : DCHECK(!IsNone());
375 : return condition_;
376 : }
377 : DeoptimizeKind kind() const {
378 : DCHECK(IsDeoptimize());
379 : return kind_;
380 : }
381 : DeoptimizeReason reason() const {
382 : DCHECK(IsDeoptimize());
383 : return reason_;
384 : }
385 : Node* frame_state() const {
386 : DCHECK(IsDeoptimize());
387 : return frame_state_or_result_;
388 : }
389 : Node* result() const {
390 : DCHECK(IsSet());
391 : return frame_state_or_result_;
392 : }
393 : Runtime::FunctionId trap_id() const {
394 : DCHECK(IsTrap());
395 : return trap_id_;
396 : }
397 : BasicBlock* true_block() const {
398 : DCHECK(IsBranch());
399 : return true_block_;
400 : }
401 : BasicBlock* false_block() const {
402 : DCHECK(IsBranch());
403 : return false_block_;
404 : }
405 :
406 : void Negate() {
407 : DCHECK(!IsNone());
408 1870972 : condition_ = NegateFlagsCondition(condition_);
409 : }
410 :
411 : void Commute() {
412 : DCHECK(!IsNone());
413 917647 : condition_ = CommuteFlagsCondition(condition_);
414 : }
415 :
416 : void Overwrite(FlagsCondition condition) { condition_ = condition; }
417 :
418 : void OverwriteAndNegateIfEqual(FlagsCondition condition) {
419 : DCHECK(condition_ == kEqual || condition_ == kNotEqual);
420 3532088 : bool negate = condition_ == kEqual;
421 3532088 : condition_ = condition;
422 3532088 : if (negate) Negate();
423 : }
424 :
425 : void OverwriteUnsignedIfSigned() {
426 192476 : switch (condition_) {
427 : case kSignedLessThan:
428 24762 : condition_ = kUnsignedLessThan;
429 : break;
430 : case kSignedLessThanOrEqual:
431 15090 : condition_ = kUnsignedLessThanOrEqual;
432 : break;
433 : case kSignedGreaterThan:
434 0 : condition_ = kUnsignedGreaterThan;
435 : break;
436 : case kSignedGreaterThanOrEqual:
437 0 : condition_ = kUnsignedGreaterThanOrEqual;
438 : break;
439 : default:
440 : break;
441 : }
442 : }
443 :
444 : // Encodes this flags continuation into the given opcode.
445 : InstructionCode Encode(InstructionCode opcode) {
446 4714540 : opcode |= FlagsModeField::encode(mode_);
447 4714540 : if (mode_ != kFlags_none) {
448 8621394 : opcode |= FlagsConditionField::encode(condition_);
449 : }
450 : return opcode;
451 : }
452 :
453 : private:
454 : FlagsContinuation(FlagsCondition condition, DeoptimizeKind kind,
455 : DeoptimizeReason reason, Node* frame_state)
456 : : mode_(kFlags_deoptimize),
457 : condition_(condition),
458 : kind_(kind),
459 : reason_(reason),
460 302320 : frame_state_or_result_(frame_state) {
461 : DCHECK_NOT_NULL(frame_state);
462 : }
463 : FlagsContinuation(FlagsCondition condition, Node* result)
464 : : mode_(kFlags_set),
465 : condition_(condition),
466 199928 : frame_state_or_result_(result) {
467 : DCHECK_NOT_NULL(result);
468 : }
469 :
470 : FlagsContinuation(FlagsCondition condition, Runtime::FunctionId trap_id,
471 : Node* result)
472 : : mode_(kFlags_trap),
473 : condition_(condition),
474 : frame_state_or_result_(result),
475 197667 : trap_id_(trap_id) {
476 : DCHECK_NOT_NULL(result);
477 : }
478 :
479 : FlagsMode const mode_;
480 : FlagsCondition condition_;
481 : DeoptimizeKind kind_; // Only valid if mode_ == kFlags_deoptimize
482 : DeoptimizeReason reason_; // Only valid if mode_ == kFlags_deoptimize
483 : Node* frame_state_or_result_; // Only valid if mode_ == kFlags_deoptimize
484 : // or mode_ == kFlags_set.
485 : BasicBlock* true_block_; // Only valid if mode_ == kFlags_branch.
486 : BasicBlock* false_block_; // Only valid if mode_ == kFlags_branch.
487 : Runtime::FunctionId trap_id_; // Only valid if mode_ == kFlags_trap.
488 : };
489 :
490 : } // namespace compiler
491 : } // namespace internal
492 : } // namespace v8
493 :
494 : #endif // V8_COMPILER_INSTRUCTION_SELECTOR_IMPL_H_
|
