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 46301132 : : selector_(selector) {}
35 :
36 : InstructionOperand NoOutput() {
37 : return InstructionOperand(); // Generates an invalid operand.
38 : }
39 :
40 5177667 : InstructionOperand DefineAsRegister(Node* node) {
41 : return Define(node,
42 : UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
43 5177675 : GetVReg(node)));
44 : }
45 :
46 1652798 : InstructionOperand DefineSameAsFirst(Node* node) {
47 : return Define(node,
48 : UnallocatedOperand(UnallocatedOperand::SAME_AS_FIRST_INPUT,
49 1652805 : GetVReg(node)));
50 : }
51 :
52 13397 : InstructionOperand DefineAsFixed(Node* node, Register reg) {
53 : return Define(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
54 13397 : reg.code(), GetVReg(node)));
55 : }
56 :
57 : template <typename FPRegType>
58 1796 : InstructionOperand DefineAsFixed(Node* node, FPRegType reg) {
59 : return Define(node,
60 : UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
61 1796 : reg.code(), GetVReg(node)));
62 : }
63 :
64 9047113 : InstructionOperand DefineAsConstant(Node* node) {
65 9047113 : return DefineAsConstant(node, ToConstant(node));
66 : }
67 :
68 9047093 : InstructionOperand DefineAsConstant(Node* node, Constant constant) {
69 : selector()->MarkAsDefined(node);
70 : int virtual_register = GetVReg(node);
71 9047145 : sequence()->AddConstant(virtual_register, constant);
72 9047172 : return ConstantOperand(virtual_register);
73 : }
74 :
75 5090755 : InstructionOperand DefineAsLocation(Node* node, LinkageLocation location) {
76 10181614 : return Define(node, ToUnallocatedOperand(location, GetVReg(node)));
77 : }
78 :
79 438462 : InstructionOperand DefineAsDualLocation(Node* node,
80 438463 : LinkageLocation primary_location,
81 438463 : LinkageLocation secondary_location) {
82 : return Define(node,
83 : ToDualLocationUnallocatedOperand(
84 438463 : primary_location, secondary_location, GetVReg(node)));
85 : }
86 :
87 6118703 : InstructionOperand Use(Node* node) {
88 : return Use(node, UnallocatedOperand(UnallocatedOperand::NONE,
89 : UnallocatedOperand::USED_AT_START,
90 6118703 : GetVReg(node)));
91 : }
92 :
93 1460775 : InstructionOperand UseAnyAtEnd(Node* node) {
94 : return Use(node, UnallocatedOperand(UnallocatedOperand::ANY,
95 : UnallocatedOperand::USED_AT_END,
96 1460779 : GetVReg(node)));
97 : }
98 :
99 6514 : InstructionOperand UseAny(Node* node) {
100 : return Use(node, UnallocatedOperand(UnallocatedOperand::ANY,
101 : UnallocatedOperand::USED_AT_START,
102 6514 : GetVReg(node)));
103 : }
104 :
105 12164252 : InstructionOperand UseRegister(Node* node) {
106 : return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
107 : UnallocatedOperand::USED_AT_START,
108 12164288 : GetVReg(node)));
109 : }
110 :
111 12140968 : InstructionOperand UseUniqueSlot(Node* node) {
112 : return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_SLOT,
113 12140957 : 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 791228 : InstructionOperand UseUniqueRegister(Node* node) {
126 : return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
127 791225 : GetVReg(node)));
128 : }
129 :
130 19783 : InstructionOperand UseFixed(Node* node, Register reg) {
131 : return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
132 19784 : reg.code(), GetVReg(node)));
133 : }
134 :
135 : template <typename FPRegType>
136 1974 : InstructionOperand UseFixed(Node* node, FPRegType reg) {
137 : return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
138 1974 : 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 21730 : InstructionOperand UseImmediate(int immediate) {
153 43462 : return sequence()->AddImmediate(Constant(immediate));
154 : }
155 :
156 18188804 : InstructionOperand UseImmediate(Node* node) {
157 36377614 : return sequence()->AddImmediate(ToConstant(node));
158 : }
159 :
160 11545 : InstructionOperand UseNegatedImmediate(Node* node) {
161 23090 : return sequence()->AddImmediate(ToNegatedConstant(node));
162 : }
163 :
164 16993045 : InstructionOperand UseLocation(Node* node, LinkageLocation location) {
165 33986180 : 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 12164 : InstructionOperand UsePointerLocation(LinkageLocation to_location,
171 : LinkageLocation from_location) {
172 : UnallocatedOperand casted_from_operand =
173 24328 : UnallocatedOperand::cast(TempLocation(from_location));
174 12164 : selector_->Emit(kArchNop, casted_from_operand);
175 : return ToUnallocatedOperand(to_location,
176 12164 : casted_from_operand.virtual_register());
177 : }
178 :
179 : InstructionOperand TempRegister() {
180 : return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
181 : UnallocatedOperand::USED_AT_START,
182 708888 : 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 5063945 : InstructionOperand TempImmediate(int32_t imm) {
215 10127901 : return sequence()->AddImmediate(Constant(imm));
216 : }
217 :
218 12164 : InstructionOperand TempLocation(LinkageLocation location) {
219 12164 : return ToUnallocatedOperand(location, sequence()->NextVirtualRegister());
220 : }
221 :
222 12933288 : InstructionOperand Label(BasicBlock* block) {
223 : return sequence()->AddImmediate(
224 12933288 : Constant(RpoNumber::FromInt(block->rpo_number())));
225 : }
226 :
227 : protected:
228 126290611 : InstructionSelector* selector() const { return selector_; }
229 45987528 : InstructionSequence* sequence() const { return selector()->sequence(); }
230 : Zone* zone() const { return selector()->instruction_zone(); }
231 :
232 : private:
233 71119210 : int GetVReg(Node* node) const { return selector_->GetVirtualRegister(node); }
234 :
235 27236057 : static Constant ToConstant(const Node* node) {
236 27236057 : switch (node->opcode()) {
237 : case IrOpcode::kInt32Constant:
238 4407542 : return Constant(OpParameter<int32_t>(node));
239 : case IrOpcode::kInt64Constant:
240 7374079 : return Constant(OpParameter<int64_t>(node));
241 : case IrOpcode::kFloat32Constant:
242 8457 : return Constant(OpParameter<float>(node));
243 : case IrOpcode::kRelocatableInt32Constant:
244 : case IrOpcode::kRelocatableInt64Constant:
245 145059 : return Constant(OpParameter<RelocatablePtrConstantInfo>(node));
246 : case IrOpcode::kFloat64Constant:
247 : case IrOpcode::kNumberConstant:
248 3528447 : return Constant(OpParameter<double>(node));
249 : case IrOpcode::kExternalConstant:
250 : case IrOpcode::kComment:
251 : return Constant(OpParameter<ExternalReference>(node));
252 : case IrOpcode::kHeapConstant:
253 : return Constant(OpParameter<Handle<HeapObject>>(node));
254 : default:
255 : break;
256 : }
257 0 : UNREACHABLE();
258 : return Constant(static_cast<int32_t>(0));
259 : }
260 :
261 11545 : static Constant ToNegatedConstant(const Node* node) {
262 11545 : switch (node->opcode()) {
263 : case IrOpcode::kInt32Constant:
264 2838 : return Constant(-OpParameter<int32_t>(node));
265 : case IrOpcode::kInt64Constant:
266 8707 : return Constant(-OpParameter<int64_t>(node));
267 : default:
268 : break;
269 : }
270 0 : UNREACHABLE();
271 : return Constant(static_cast<int32_t>(0));
272 : }
273 :
274 : UnallocatedOperand Define(Node* node, UnallocatedOperand operand) {
275 : DCHECK_NOT_NULL(node);
276 : DCHECK_EQ(operand.virtual_register(), GetVReg(node));
277 6350638 : selector()->MarkAsDefined(node);
278 : return operand;
279 : }
280 :
281 : UnallocatedOperand Use(Node* node, UnallocatedOperand operand) {
282 : DCHECK_NOT_NULL(node);
283 : DCHECK_EQ(operand.virtual_register(), GetVReg(node));
284 18631460 : selector()->MarkAsUsed(node);
285 : return operand;
286 : }
287 :
288 : UnallocatedOperand ToDualLocationUnallocatedOperand(
289 : LinkageLocation primary_location, LinkageLocation secondary_location,
290 : int virtual_register) {
291 : // We only support the primary location being a register and the secondary
292 : // one a slot.
293 : DCHECK(primary_location.IsRegister() &&
294 : secondary_location.IsCalleeFrameSlot());
295 : int reg_id = primary_location.AsRegister();
296 : int slot_id = secondary_location.AsCalleeFrameSlot();
297 : return UnallocatedOperand(reg_id, slot_id, virtual_register);
298 : }
299 :
300 22108164 : UnallocatedOperand ToUnallocatedOperand(LinkageLocation location,
301 : int virtual_register) {
302 22108164 : if (location.IsAnyRegister()) {
303 : // any machine register.
304 : return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
305 0 : virtual_register);
306 : }
307 22108164 : if (location.IsCallerFrameSlot()) {
308 : // a location on the caller frame.
309 : return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
310 4388853 : location.AsCallerFrameSlot(), virtual_register);
311 : }
312 17719311 : if (location.IsCalleeFrameSlot()) {
313 : // a spill location on this (callee) frame.
314 : return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
315 87555 : location.AsCalleeFrameSlot(), virtual_register);
316 : }
317 : // a fixed register.
318 17631756 : if (IsFloatingPoint(location.GetType().representation())) {
319 : return UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
320 100492 : location.AsRegister(), virtual_register);
321 : }
322 : return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
323 17531264 : location.AsRegister(), virtual_register);
324 : }
325 :
326 : InstructionSelector* selector_;
327 : };
328 :
329 :
330 : // The flags continuation is a way to combine a branch or a materialization
331 : // of a boolean value with an instruction that sets the flags register.
332 : // The whole instruction is treated as a unit by the register allocator, and
333 : // thus no spills or moves can be introduced between the flags-setting
334 : // instruction and the branch or set it should be combined with.
335 : class FlagsContinuation final {
336 : public:
337 320175 : FlagsContinuation() : mode_(kFlags_none) {}
338 :
339 : // Creates a new flags continuation from the given condition and true/false
340 : // blocks.
341 : FlagsContinuation(FlagsCondition condition, BasicBlock* true_block,
342 : BasicBlock* false_block)
343 : : mode_(kFlags_branch),
344 : condition_(condition),
345 : true_block_(true_block),
346 3308740 : false_block_(false_block) {
347 : DCHECK_NOT_NULL(true_block);
348 : DCHECK_NOT_NULL(false_block);
349 : }
350 :
351 : // Creates a new flags continuation for an eager deoptimization exit.
352 : static FlagsContinuation ForDeoptimize(FlagsCondition condition,
353 : DeoptimizeKind kind,
354 : DeoptimizeReason reason,
355 : Node* frame_state) {
356 : return FlagsContinuation(condition, kind, reason, frame_state);
357 : }
358 :
359 : // Creates a new flags continuation for a boolean value.
360 : static FlagsContinuation ForSet(FlagsCondition condition, Node* result) {
361 : return FlagsContinuation(condition, result);
362 : }
363 :
364 : // Creates a new flags continuation for a wasm trap.
365 : static FlagsContinuation ForTrap(FlagsCondition condition,
366 : Runtime::FunctionId trap_id, Node* result) {
367 : return FlagsContinuation(condition, trap_id, result);
368 : }
369 :
370 : bool IsNone() const { return mode_ == kFlags_none; }
371 : bool IsBranch() const { return mode_ == kFlags_branch; }
372 : bool IsDeoptimize() const { return mode_ == kFlags_deoptimize; }
373 : bool IsSet() const { return mode_ == kFlags_set; }
374 : bool IsTrap() const { return mode_ == kFlags_trap; }
375 : FlagsCondition condition() const {
376 : DCHECK(!IsNone());
377 : return condition_;
378 : }
379 : DeoptimizeKind kind() const {
380 : DCHECK(IsDeoptimize());
381 : return kind_;
382 : }
383 : DeoptimizeReason reason() const {
384 : DCHECK(IsDeoptimize());
385 : return reason_;
386 : }
387 : Node* frame_state() const {
388 : DCHECK(IsDeoptimize());
389 : return frame_state_or_result_;
390 : }
391 : Node* result() const {
392 : DCHECK(IsSet());
393 : return frame_state_or_result_;
394 : }
395 : Runtime::FunctionId trap_id() const {
396 : DCHECK(IsTrap());
397 : return trap_id_;
398 : }
399 : BasicBlock* true_block() const {
400 : DCHECK(IsBranch());
401 : return true_block_;
402 : }
403 : BasicBlock* false_block() const {
404 : DCHECK(IsBranch());
405 : return false_block_;
406 : }
407 :
408 : void Negate() {
409 : DCHECK(!IsNone());
410 1224005 : condition_ = NegateFlagsCondition(condition_);
411 : }
412 :
413 : void Commute() {
414 : DCHECK(!IsNone());
415 752067 : condition_ = CommuteFlagsCondition(condition_);
416 : }
417 :
418 : void Overwrite(FlagsCondition condition) { condition_ = condition; }
419 :
420 : void OverwriteAndNegateIfEqual(FlagsCondition condition) {
421 : DCHECK(condition_ == kEqual || condition_ == kNotEqual);
422 3215197 : bool negate = condition_ == kEqual;
423 3215197 : condition_ = condition;
424 3215197 : if (negate) Negate();
425 : }
426 :
427 : void OverwriteUnsignedIfSigned() {
428 135055 : switch (condition_) {
429 : case kSignedLessThan:
430 9696 : condition_ = kUnsignedLessThan;
431 : break;
432 : case kSignedLessThanOrEqual:
433 8744 : condition_ = kUnsignedLessThanOrEqual;
434 : break;
435 : case kSignedGreaterThan:
436 0 : condition_ = kUnsignedGreaterThan;
437 : break;
438 : case kSignedGreaterThanOrEqual:
439 0 : condition_ = kUnsignedGreaterThanOrEqual;
440 : break;
441 : default:
442 : break;
443 : }
444 : }
445 :
446 : // Encodes this flags continuation into the given opcode.
447 : InstructionCode Encode(InstructionCode opcode) {
448 4129200 : opcode |= FlagsModeField::encode(mode_);
449 4129200 : if (mode_ != kFlags_none) {
450 7617992 : opcode |= FlagsConditionField::encode(condition_);
451 : }
452 : return opcode;
453 : }
454 :
455 : private:
456 : FlagsContinuation(FlagsCondition condition, DeoptimizeKind kind,
457 : DeoptimizeReason reason, Node* frame_state)
458 : : mode_(kFlags_deoptimize),
459 : condition_(condition),
460 : kind_(kind),
461 : reason_(reason),
462 266679 : frame_state_or_result_(frame_state) {
463 : DCHECK_NOT_NULL(frame_state);
464 : }
465 : FlagsContinuation(FlagsCondition condition, Node* result)
466 : : mode_(kFlags_set),
467 : condition_(condition),
468 217331 : frame_state_or_result_(result) {
469 : DCHECK_NOT_NULL(result);
470 : }
471 :
472 : FlagsContinuation(FlagsCondition condition, Runtime::FunctionId trap_id,
473 : Node* result)
474 : : mode_(kFlags_trap),
475 : condition_(condition),
476 : frame_state_or_result_(result),
477 16299 : trap_id_(trap_id) {
478 : DCHECK_NOT_NULL(result);
479 : }
480 :
481 : FlagsMode const mode_;
482 : FlagsCondition condition_;
483 : DeoptimizeKind kind_; // Only valid if mode_ == kFlags_deoptimize
484 : DeoptimizeReason reason_; // Only valid if mode_ == kFlags_deoptimize
485 : Node* frame_state_or_result_; // Only valid if mode_ == kFlags_deoptimize
486 : // or mode_ == kFlags_set.
487 : BasicBlock* true_block_; // Only valid if mode_ == kFlags_branch.
488 : BasicBlock* false_block_; // Only valid if mode_ == kFlags_branch.
489 : Runtime::FunctionId trap_id_; // Only valid if mode_ == kFlags_trap.
490 : };
491 :
492 : } // namespace compiler
493 : } // namespace internal
494 : } // namespace v8
495 :
496 : #endif // V8_COMPILER_INSTRUCTION_SELECTOR_IMPL_H_
|
