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 3687031 : 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 : Features() : bits_(0) {}
135 : explicit Features(unsigned bits) : bits_(bits) {}
136 : explicit Features(CpuFeature f) : bits_(1u << f) {}
137 : Features(CpuFeature f1, CpuFeature f2) : bits_((1u << f1) | (1u << f2)) {}
138 :
139 3771397 : 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 915847 : static Features SupportedFeatures() {
151 915847 : 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 413534 : 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 22003374 : Isolate* isolate() const { return sequence()->isolate(); }
219 :
220 : private:
221 : friend class OperandGenerator;
222 :
223 : bool UseInstructionScheduling() const {
224 62053114 : 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 956486 : MarkAsRepresentation(MachineRepresentation::kWord32, node);
253 : }
254 : void MarkAsWord64(Node* node) {
255 1857830 : MarkAsRepresentation(MachineRepresentation::kWord64, node);
256 : }
257 : void MarkAsFloat32(Node* node) {
258 18947 : MarkAsRepresentation(MachineRepresentation::kFloat32, node);
259 : }
260 : void MarkAsFloat64(Node* node) {
261 645110 : MarkAsRepresentation(MachineRepresentation::kFloat64, node);
262 : }
263 : void MarkAsSimd128(Node* node) {
264 1309 : MarkAsRepresentation(MachineRepresentation::kSimd128, node);
265 : }
266 : void MarkAsSimd1x4(Node* node) {
267 : if (kSimdMaskRegisters) {
268 : MarkAsRepresentation(MachineRepresentation::kSimd1x4, node);
269 : } else {
270 : MarkAsSimd128(node);
271 : }
272 : }
273 : void MarkAsSimd1x8(Node* node) {
274 : if (kSimdMaskRegisters) {
275 : MarkAsRepresentation(MachineRepresentation::kSimd1x8, node);
276 : } else {
277 : MarkAsSimd128(node);
278 : }
279 : }
280 : void MarkAsSimd1x16(Node* node) {
281 : if (kSimdMaskRegisters) {
282 : MarkAsRepresentation(MachineRepresentation::kSimd1x16, node);
283 : } else {
284 : MarkAsSimd128(node);
285 : }
286 : }
287 : void MarkAsReference(Node* node) {
288 3418273 : MarkAsRepresentation(MachineRepresentation::kTagged, node);
289 : }
290 :
291 : // Inform the register allocation of the representation of the unallocated
292 : // operand {op}.
293 : void MarkAsRepresentation(MachineRepresentation rep,
294 : const InstructionOperand& op);
295 :
296 : enum CallBufferFlag {
297 : kCallCodeImmediate = 1u << 0,
298 : kCallAddressImmediate = 1u << 1,
299 : kCallTail = 1u << 2
300 : };
301 : typedef base::Flags<CallBufferFlag> CallBufferFlags;
302 :
303 : // Initialize the call buffer with the InstructionOperands, nodes, etc,
304 : // corresponding
305 : // to the inputs and outputs of the call.
306 : // {call_code_immediate} to generate immediate operands to calls of code.
307 : // {call_address_immediate} to generate immediate operands to address calls.
308 : void InitializeCallBuffer(Node* call, CallBuffer* buffer,
309 : CallBufferFlags flags, int stack_slot_delta = 0);
310 : bool IsTailCallAddressImmediate();
311 : int GetTempsCountForTailCallFromJSFunction();
312 :
313 : FrameStateDescriptor* GetFrameStateDescriptor(Node* node);
314 : size_t AddInputsToFrameStateDescriptor(FrameStateDescriptor* descriptor,
315 : Node* state, OperandGenerator* g,
316 : StateObjectDeduplicator* deduplicator,
317 : InstructionOperandVector* inputs,
318 : FrameStateInputKind kind, Zone* zone);
319 : size_t AddOperandToStateValueDescriptor(StateValueList* values,
320 : InstructionOperandVector* inputs,
321 : OperandGenerator* g,
322 : StateObjectDeduplicator* deduplicator,
323 : Node* input, MachineType type,
324 : FrameStateInputKind kind, Zone* zone);
325 :
326 : // ===========================================================================
327 : // ============= Architecture-specific graph covering methods. ===============
328 : // ===========================================================================
329 :
330 : // Visit nodes in the given block and generate code.
331 : void VisitBlock(BasicBlock* block);
332 :
333 : // Visit the node for the control flow at the end of the block, generating
334 : // code if necessary.
335 : void VisitControl(BasicBlock* block);
336 :
337 : // Visit the node and generate code, if any.
338 : void VisitNode(Node* node);
339 :
340 : // Visit the node and generate code for IEEE 754 functions.
341 : void VisitFloat64Ieee754Binop(Node*, InstructionCode code);
342 : void VisitFloat64Ieee754Unop(Node*, InstructionCode code);
343 :
344 : #define DECLARE_GENERATOR(x) void Visit##x(Node* node);
345 : MACHINE_OP_LIST(DECLARE_GENERATOR)
346 : MACHINE_SIMD_OP_LIST(DECLARE_GENERATOR)
347 : #undef DECLARE_GENERATOR
348 :
349 : void VisitFinishRegion(Node* node);
350 : void VisitParameter(Node* node);
351 : void VisitIfException(Node* node);
352 : void VisitOsrValue(Node* node);
353 : void VisitPhi(Node* node);
354 : void VisitProjection(Node* node);
355 : void VisitConstant(Node* node);
356 : void VisitCall(Node* call, BasicBlock* handler = nullptr);
357 : void VisitDeoptimizeIf(Node* node);
358 : void VisitDeoptimizeUnless(Node* node);
359 : void VisitTrapIf(Node* node, Runtime::FunctionId func_id);
360 : void VisitTrapUnless(Node* node, Runtime::FunctionId func_id);
361 : void VisitTailCall(Node* call);
362 : void VisitGoto(BasicBlock* target);
363 : void VisitBranch(Node* input, BasicBlock* tbranch, BasicBlock* fbranch);
364 : void VisitSwitch(Node* node, const SwitchInfo& sw);
365 : void VisitDeoptimize(DeoptimizeKind kind, DeoptimizeReason reason,
366 : Node* value);
367 : void VisitReturn(Node* ret);
368 : void VisitThrow(Node* node);
369 : void VisitRetain(Node* node);
370 :
371 : void EmitPrepareArguments(ZoneVector<compiler::PushParameter>* arguments,
372 : const CallDescriptor* descriptor, Node* node);
373 :
374 : void EmitIdentity(Node* node);
375 : bool CanProduceSignalingNaN(Node* node);
376 :
377 : // ===========================================================================
378 :
379 : Schedule* schedule() const { return schedule_; }
380 : Linkage* linkage() const { return linkage_; }
381 : InstructionSequence* sequence() const { return sequence_; }
382 46776001 : Zone* instruction_zone() const { return sequence()->zone(); }
383 : Zone* zone() const { return zone_; }
384 :
385 : void set_instruction_selection_failed() {
386 0 : instruction_selection_failed_ = true;
387 : }
388 : bool instruction_selection_failed() { return instruction_selection_failed_; }
389 :
390 : void MarkPairProjectionsAsWord32(Node* node);
391 : bool IsSourcePositionUsed(Node* node);
392 : void VisitAtomicBinaryOperation(Node* node, ArchOpcode int8_op,
393 : ArchOpcode uint8_op, ArchOpcode int16_op,
394 : ArchOpcode uint16_op, ArchOpcode word32_op);
395 :
396 : // ===========================================================================
397 :
398 : Zone* const zone_;
399 : Linkage* const linkage_;
400 : InstructionSequence* const sequence_;
401 : SourcePositionTable* const source_positions_;
402 : SourcePositionMode const source_position_mode_;
403 : Features features_;
404 : Schedule* const schedule_;
405 : BasicBlock* current_block_;
406 : ZoneVector<Instruction*> instructions_;
407 : BoolVector defined_;
408 : BoolVector used_;
409 : IntVector effect_level_;
410 : IntVector virtual_registers_;
411 : IntVector virtual_register_rename_;
412 : InstructionScheduler* scheduler_;
413 : EnableScheduling enable_scheduling_;
414 : EnableSerialization enable_serialization_;
415 : Frame* frame_;
416 : bool instruction_selection_failed_;
417 : };
418 :
419 : } // namespace compiler
420 : } // namespace internal
421 : } // namespace v8
422 :
423 : #endif // V8_COMPILER_INSTRUCTION_SELECTOR_H_
|
