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_H_
6 : #define V8_COMPILER_INSTRUCTION_SELECTOR_H_
7 :
8 : #include <map>
9 :
10 : #include "src/compiler/common-operator.h"
11 : #include "src/compiler/instruction-scheduler.h"
12 : #include "src/compiler/instruction.h"
13 : #include "src/compiler/machine-operator.h"
14 : #include "src/compiler/node.h"
15 : #include "src/globals.h"
16 : #include "src/zone/zone-containers.h"
17 :
18 : namespace v8 {
19 : namespace internal {
20 : namespace compiler {
21 :
22 : // Forward declarations.
23 : class BasicBlock;
24 : struct CallBuffer; // TODO(bmeurer): Remove this.
25 : class FlagsContinuation;
26 : class Linkage;
27 : class OperandGenerator;
28 : struct SwitchInfo;
29 : class StateObjectDeduplicator;
30 :
31 : // This struct connects nodes of parameters which are going to be pushed on the
32 : // call stack with their parameter index in the call descriptor of the callee.
33 : class PushParameter {
34 : public:
35 3699938 : PushParameter() : node_(nullptr), type_(MachineType::None()) {}
36 : PushParameter(Node* node, MachineType type) : node_(node), type_(type) {}
37 :
38 : Node* node() const { return node_; }
39 : MachineType type() const { return type_; }
40 :
41 : private:
42 : Node* node_;
43 : MachineType type_;
44 : };
45 :
46 : enum class FrameStateInputKind { kAny, kStackSlot };
47 :
48 : // Instruction selection generates an InstructionSequence for a given Schedule.
49 : class V8_EXPORT_PRIVATE InstructionSelector final {
50 : public:
51 : // Forward declarations.
52 : class Features;
53 :
54 : enum SourcePositionMode { kCallSourcePositions, kAllSourcePositions };
55 : enum EnableScheduling { kDisableScheduling, kEnableScheduling };
56 : enum EnableSerialization { kDisableSerialization, kEnableSerialization };
57 :
58 : InstructionSelector(
59 : Zone* zone, size_t node_count, Linkage* linkage,
60 : InstructionSequence* sequence, Schedule* schedule,
61 : SourcePositionTable* source_positions, Frame* frame,
62 : SourcePositionMode source_position_mode = kCallSourcePositions,
63 : Features features = SupportedFeatures(),
64 : EnableScheduling enable_scheduling = FLAG_turbo_instruction_scheduling
65 : ? kEnableScheduling
66 : : kDisableScheduling,
67 : EnableSerialization enable_serialization = kDisableSerialization);
68 :
69 : // Visit code for the entire graph with the included schedule.
70 : bool SelectInstructions();
71 :
72 : void StartBlock(RpoNumber rpo);
73 : void EndBlock(RpoNumber rpo);
74 : void AddInstruction(Instruction* instr);
75 :
76 : // ===========================================================================
77 : // ============= Architecture-independent code emission methods. =============
78 : // ===========================================================================
79 :
80 : Instruction* Emit(InstructionCode opcode, InstructionOperand output,
81 : size_t temp_count = 0, InstructionOperand* temps = nullptr);
82 : Instruction* Emit(InstructionCode opcode, InstructionOperand output,
83 : InstructionOperand a, size_t temp_count = 0,
84 : InstructionOperand* temps = nullptr);
85 : Instruction* Emit(InstructionCode opcode, InstructionOperand output,
86 : InstructionOperand a, InstructionOperand b,
87 : size_t temp_count = 0, InstructionOperand* temps = nullptr);
88 : Instruction* Emit(InstructionCode opcode, InstructionOperand output,
89 : InstructionOperand a, InstructionOperand b,
90 : InstructionOperand c, size_t temp_count = 0,
91 : InstructionOperand* temps = nullptr);
92 : Instruction* Emit(InstructionCode opcode, InstructionOperand output,
93 : InstructionOperand a, InstructionOperand b,
94 : InstructionOperand c, InstructionOperand d,
95 : size_t temp_count = 0, InstructionOperand* temps = nullptr);
96 : Instruction* Emit(InstructionCode opcode, InstructionOperand output,
97 : InstructionOperand a, InstructionOperand b,
98 : InstructionOperand c, InstructionOperand d,
99 : InstructionOperand e, size_t temp_count = 0,
100 : InstructionOperand* temps = nullptr);
101 : Instruction* Emit(InstructionCode opcode, InstructionOperand output,
102 : InstructionOperand a, InstructionOperand b,
103 : InstructionOperand c, InstructionOperand d,
104 : InstructionOperand e, InstructionOperand f,
105 : size_t temp_count = 0, InstructionOperand* temps = nullptr);
106 : Instruction* Emit(InstructionCode opcode, size_t output_count,
107 : InstructionOperand* outputs, size_t input_count,
108 : InstructionOperand* inputs, size_t temp_count = 0,
109 : InstructionOperand* temps = nullptr);
110 : Instruction* Emit(Instruction* instr);
111 :
112 : // ===========================================================================
113 : // ===== Architecture-independent deoptimization exit emission methods. ======
114 : // ===========================================================================
115 :
116 : Instruction* EmitDeoptimize(InstructionCode opcode, InstructionOperand output,
117 : InstructionOperand a, DeoptimizeKind kind,
118 : DeoptimizeReason reason, Node* frame_state);
119 : Instruction* EmitDeoptimize(InstructionCode opcode, InstructionOperand output,
120 : InstructionOperand a, InstructionOperand b,
121 : DeoptimizeKind kind, DeoptimizeReason reason,
122 : Node* frame_state);
123 : Instruction* EmitDeoptimize(InstructionCode opcode, size_t output_count,
124 : InstructionOperand* outputs, size_t input_count,
125 : InstructionOperand* inputs, DeoptimizeKind kind,
126 : DeoptimizeReason reason, Node* frame_state);
127 :
128 : // ===========================================================================
129 : // ============== Architecture-independent CPU feature methods. ==============
130 : // ===========================================================================
131 :
132 : class Features final {
133 : public:
134 239 : Features() : bits_(0) {}
135 : explicit Features(unsigned bits) : bits_(bits) {}
136 3 : explicit Features(CpuFeature f) : bits_(1u << f) {}
137 : Features(CpuFeature f1, CpuFeature f2) : bits_((1u << f1) | (1u << f2)) {}
138 :
139 3840929 : bool Contains(CpuFeature f) const { return (bits_ & (1u << f)); }
140 :
141 : private:
142 : unsigned bits_;
143 : };
144 :
145 : bool IsSupported(CpuFeature feature) const {
146 : return features_.Contains(feature);
147 : }
148 :
149 : // Returns the features supported on the target platform.
150 1301544 : static Features SupportedFeatures() {
151 1301544 : return Features(CpuFeatures::SupportedFeatures());
152 : }
153 :
154 : // TODO(sigurds) This should take a CpuFeatures argument.
155 : static MachineOperatorBuilder::Flags SupportedMachineOperatorFlags();
156 :
157 : static MachineOperatorBuilder::AlignmentRequirements AlignmentRequirements();
158 :
159 : // ===========================================================================
160 : // ============ Architecture-independent graph covering methods. =============
161 : // ===========================================================================
162 :
163 : // Used in pattern matching during code generation.
164 : // Check if {node} can be covered while generating code for the current
165 : // instruction. A node can be covered if the {user} of the node has the only
166 : // edge and the two are in the same basic block.
167 : bool CanCover(Node* user, Node* node) const;
168 :
169 : // Used in pattern matching during code generation.
170 : // This function checks that {node} and {user} are in the same basic block,
171 : // and that {user} is the only user of {node} in this basic block. This
172 : // check guarantees that there are no users of {node} scheduled between
173 : // {node} and {user}, and thus we can select a single instruction for both
174 : // nodes, if such an instruction exists. This check can be used for example
175 : // when selecting instructions for:
176 : // n = Int32Add(a, b)
177 : // c = Word32Compare(n, 0, cond)
178 : // Branch(c, true_label, false_label)
179 : // Here we can generate a flag-setting add instruction, even if the add has
180 : // uses in other basic blocks, since the flag-setting add instruction will
181 : // still generate the result of the addition and not just set the flags.
182 : // However, if we had uses of the add in the same basic block, we could have:
183 : // n = Int32Add(a, b)
184 : // o = OtherOp(n, ...)
185 : // c = Word32Compare(n, 0, cond)
186 : // Branch(c, true_label, false_label)
187 : // where we cannot select the add and the compare together. If we were to
188 : // select a flag-setting add instruction for Word32Compare and Int32Add while
189 : // visiting Word32Compare, we would then have to select an instruction for
190 : // OtherOp *afterwards*, which means we would attempt to use the result of
191 : // the add before we have defined it.
192 : bool IsOnlyUserOfNodeInSameBlock(Node* user, Node* node) const;
193 :
194 : // Checks if {node} was already defined, and therefore code was already
195 : // generated for it.
196 : bool IsDefined(Node* node) const;
197 :
198 : // Checks if {node} has any uses, and therefore code has to be generated for
199 : // it.
200 : bool IsUsed(Node* node) const;
201 :
202 : // Checks if {node} is currently live.
203 580796 : bool IsLive(Node* node) const { return !IsDefined(node) && IsUsed(node); }
204 :
205 : // Gets the effect level of {node}.
206 : int GetEffectLevel(Node* node) const;
207 :
208 : int GetVirtualRegister(const Node* node);
209 : const std::map<NodeId, int> GetVirtualRegistersForTesting() const;
210 :
211 : // Check if we can generate loads and stores of ExternalConstants relative
212 : // to the roots register, i.e. if both a root register is available for this
213 : // compilation unit and the serializer is disabled.
214 : bool CanAddressRelativeToRootsRegister() const;
215 : // Check if we can use the roots register to access GC roots.
216 : bool CanUseRootsRegister() const;
217 :
218 24346069 : Isolate* isolate() const { return sequence()->isolate(); }
219 :
220 : private:
221 : friend class OperandGenerator;
222 :
223 : bool UseInstructionScheduling() const {
224 70809237 : return (enable_scheduling_ == kEnableScheduling) &&
225 0 : InstructionScheduler::SchedulerSupported();
226 : }
227 :
228 : void EmitTableSwitch(const SwitchInfo& sw, InstructionOperand& index_operand);
229 : void EmitLookupSwitch(const SwitchInfo& sw,
230 : InstructionOperand& value_operand);
231 :
232 : void TryRename(InstructionOperand* op);
233 : int GetRename(int virtual_register);
234 : void SetRename(const Node* node, const Node* rename);
235 : void UpdateRenames(Instruction* instruction);
236 : void UpdateRenamesInPhi(PhiInstruction* phi);
237 :
238 : // Inform the instruction selection that {node} was just defined.
239 : void MarkAsDefined(Node* node);
240 :
241 : // Inform the instruction selection that {node} has at least one use and we
242 : // will need to generate code for it.
243 : void MarkAsUsed(Node* node);
244 :
245 : // Sets the effect level of {node}.
246 : void SetEffectLevel(Node* node, int effect_level);
247 :
248 : // Inform the register allocation of the representation of the value produced
249 : // by {node}.
250 : void MarkAsRepresentation(MachineRepresentation rep, Node* node);
251 : void MarkAsWord32(Node* node) {
252 1131910 : MarkAsRepresentation(MachineRepresentation::kWord32, node);
253 : }
254 : void MarkAsWord64(Node* node) {
255 2192275 : MarkAsRepresentation(MachineRepresentation::kWord64, node);
256 : }
257 : void MarkAsFloat32(Node* node) {
258 161934 : MarkAsRepresentation(MachineRepresentation::kFloat32, node);
259 : }
260 : void MarkAsFloat64(Node* node) {
261 797262 : MarkAsRepresentation(MachineRepresentation::kFloat64, node);
262 : }
263 : void MarkAsSimd128(Node* node) {
264 1740 : MarkAsRepresentation(MachineRepresentation::kSimd128, node);
265 : }
266 : void MarkAsReference(Node* node) {
267 3755952 : MarkAsRepresentation(MachineRepresentation::kTagged, node);
268 : }
269 :
270 : // Inform the register allocation of the representation of the unallocated
271 : // operand {op}.
272 : void MarkAsRepresentation(MachineRepresentation rep,
273 : const InstructionOperand& op);
274 :
275 : enum CallBufferFlag {
276 : kCallCodeImmediate = 1u << 0,
277 : kCallAddressImmediate = 1u << 1,
278 : kCallTail = 1u << 2
279 : };
280 : typedef base::Flags<CallBufferFlag> CallBufferFlags;
281 :
282 : // Initialize the call buffer with the InstructionOperands, nodes, etc,
283 : // corresponding
284 : // to the inputs and outputs of the call.
285 : // {call_code_immediate} to generate immediate operands to calls of code.
286 : // {call_address_immediate} to generate immediate operands to address calls.
287 : void InitializeCallBuffer(Node* call, CallBuffer* buffer,
288 : CallBufferFlags flags, int stack_slot_delta = 0);
289 : bool IsTailCallAddressImmediate();
290 : int GetTempsCountForTailCallFromJSFunction();
291 :
292 : FrameStateDescriptor* GetFrameStateDescriptor(Node* node);
293 : size_t AddInputsToFrameStateDescriptor(FrameStateDescriptor* descriptor,
294 : Node* state, OperandGenerator* g,
295 : StateObjectDeduplicator* deduplicator,
296 : InstructionOperandVector* inputs,
297 : FrameStateInputKind kind, Zone* zone);
298 : size_t AddOperandToStateValueDescriptor(StateValueList* values,
299 : InstructionOperandVector* inputs,
300 : OperandGenerator* g,
301 : StateObjectDeduplicator* deduplicator,
302 : Node* input, MachineType type,
303 : FrameStateInputKind kind, Zone* zone);
304 :
305 : // ===========================================================================
306 : // ============= Architecture-specific graph covering methods. ===============
307 : // ===========================================================================
308 :
309 : // Visit nodes in the given block and generate code.
310 : void VisitBlock(BasicBlock* block);
311 :
312 : // Visit the node for the control flow at the end of the block, generating
313 : // code if necessary.
314 : void VisitControl(BasicBlock* block);
315 :
316 : // Visit the node and generate code, if any.
317 : void VisitNode(Node* node);
318 :
319 : // Visit the node and generate code for IEEE 754 functions.
320 : void VisitFloat64Ieee754Binop(Node*, InstructionCode code);
321 : void VisitFloat64Ieee754Unop(Node*, InstructionCode code);
322 :
323 : #define DECLARE_GENERATOR(x) void Visit##x(Node* node);
324 : MACHINE_OP_LIST(DECLARE_GENERATOR)
325 : MACHINE_SIMD_OP_LIST(DECLARE_GENERATOR)
326 : #undef DECLARE_GENERATOR
327 :
328 : void VisitFinishRegion(Node* node);
329 : void VisitParameter(Node* node);
330 : void VisitIfException(Node* node);
331 : void VisitOsrValue(Node* node);
332 : void VisitPhi(Node* node);
333 : void VisitProjection(Node* node);
334 : void VisitConstant(Node* node);
335 : void VisitCall(Node* call, BasicBlock* handler = nullptr);
336 : void VisitCallWithCallerSavedRegisters(Node* call,
337 : BasicBlock* handler = nullptr);
338 : void VisitDeoptimizeIf(Node* node);
339 : void VisitDeoptimizeUnless(Node* node);
340 : void VisitTrapIf(Node* node, Runtime::FunctionId func_id);
341 : void VisitTrapUnless(Node* node, Runtime::FunctionId func_id);
342 : void VisitTailCall(Node* call);
343 : void VisitGoto(BasicBlock* target);
344 : void VisitBranch(Node* input, BasicBlock* tbranch, BasicBlock* fbranch);
345 : void VisitSwitch(Node* node, const SwitchInfo& sw);
346 : void VisitDeoptimize(DeoptimizeKind kind, DeoptimizeReason reason,
347 : Node* value);
348 : void VisitReturn(Node* ret);
349 : void VisitThrow(Node* node);
350 : void VisitRetain(Node* node);
351 :
352 : void EmitPrepareArguments(ZoneVector<compiler::PushParameter>* arguments,
353 : const CallDescriptor* descriptor, Node* node);
354 :
355 : void EmitIdentity(Node* node);
356 : bool CanProduceSignalingNaN(Node* node);
357 :
358 : // ===========================================================================
359 : // ============= Vector instruction (SIMD) helper fns. =======================
360 : // ===========================================================================
361 :
362 : // Tries to match a byte shuffle to a scalar splat operation. Returns the
363 : // index of the lane if successful.
364 : template <int LANES>
365 : static bool TryMatchDup(const uint8_t* shuffle, int* index) {
366 : const int kBytesPerLane = kSimd128Size / LANES;
367 : // Get the first lane's worth of bytes and check that indices start at a
368 : // lane boundary and are consecutive.
369 : uint8_t lane0[kBytesPerLane];
370 : lane0[0] = shuffle[0];
371 : if (lane0[0] % kBytesPerLane != 0) return false;
372 : for (int i = 1; i < kBytesPerLane; ++i) {
373 : lane0[i] = shuffle[i];
374 : if (lane0[i] != lane0[0] + i) return false;
375 : }
376 : // Now check that the other lanes are identical to lane0.
377 : for (int i = 1; i < LANES; ++i) {
378 : for (int j = 0; j < kBytesPerLane; ++j) {
379 : if (lane0[j] != shuffle[i * kBytesPerLane + j]) return false;
380 : }
381 : }
382 : *index = lane0[0] / kBytesPerLane;
383 : return true;
384 : }
385 :
386 : // Tries to match 8x16 byte shuffle to an equivalent 32x4 word shuffle. If
387 : // successful, it writes the 32x4 shuffle word indices.
388 : static bool TryMatch32x4Shuffle(const uint8_t* shuffle, uint8_t* shuffle32x4);
389 :
390 : // Tries to match a byte shuffle to a concatenate operation. If successful,
391 : // it writes the byte offset.
392 : static bool TryMatchConcat(const uint8_t* shuffle, uint8_t mask,
393 : uint8_t* offset);
394 :
395 : // Packs 4 bytes of shuffle into a 32 bit immediate, using a mask from
396 : // CanonicalizeShuffle to convert unary shuffles.
397 : static int32_t Pack4Lanes(const uint8_t* shuffle, uint8_t mask);
398 :
399 : // Canonicalize shuffles to make pattern matching simpler. Returns a mask that
400 : // will ignore the high bit of indices if shuffle is unary.
401 : uint8_t CanonicalizeShuffle(Node* node);
402 :
403 : // ===========================================================================
404 :
405 : Schedule* schedule() const { return schedule_; }
406 : Linkage* linkage() const { return linkage_; }
407 : InstructionSequence* sequence() const { return sequence_; }
408 56160571 : Zone* instruction_zone() const { return sequence()->zone(); }
409 : Zone* zone() const { return zone_; }
410 :
411 : void set_instruction_selection_failed() {
412 10 : instruction_selection_failed_ = true;
413 : }
414 : bool instruction_selection_failed() { return instruction_selection_failed_; }
415 :
416 : void MarkPairProjectionsAsWord32(Node* node);
417 : bool IsSourcePositionUsed(Node* node);
418 : void VisitAtomicBinaryOperation(Node* node, ArchOpcode int8_op,
419 : ArchOpcode uint8_op, ArchOpcode int16_op,
420 : ArchOpcode uint16_op, ArchOpcode word32_op);
421 :
422 : // ===========================================================================
423 :
424 : Zone* const zone_;
425 : Linkage* const linkage_;
426 : InstructionSequence* const sequence_;
427 : SourcePositionTable* const source_positions_;
428 : SourcePositionMode const source_position_mode_;
429 : Features features_;
430 : Schedule* const schedule_;
431 : BasicBlock* current_block_;
432 : ZoneVector<Instruction*> instructions_;
433 : BoolVector defined_;
434 : BoolVector used_;
435 : IntVector effect_level_;
436 : IntVector virtual_registers_;
437 : IntVector virtual_register_rename_;
438 : InstructionScheduler* scheduler_;
439 : EnableScheduling enable_scheduling_;
440 : EnableSerialization enable_serialization_;
441 : Frame* frame_;
442 : bool instruction_selection_failed_;
443 : };
444 :
445 : } // namespace compiler
446 : } // namespace internal
447 : } // namespace v8
448 :
449 : #endif // V8_COMPILER_INSTRUCTION_SELECTOR_H_
|
