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.h"
12 #include "src/compiler/instruction-scheduler.h"
13 #include "src/compiler/machine-operator.h"
14 #include "src/compiler/node.h"
15 #include "src/zone-containers.h"
16 
17 namespace v8 {
18 namespace internal {
19 namespace compiler {
20 
21 // Forward declarations.
22 class BasicBlock;
23 struct CallBuffer;  // TODO(bmeurer): Remove this.
24 class FlagsContinuation;
25 class Linkage;
26 class OperandGenerator;
27 struct SwitchInfo;
28 
29 // This struct connects nodes of parameters which are going to be pushed on the
30 // call stack with their parameter index in the call descriptor of the callee.
31 class PushParameter {
32  public:
PushParameter()33   PushParameter() : node_(nullptr), type_(MachineType::None()) {}
PushParameter(Node * node,MachineType type)34   PushParameter(Node* node, MachineType type) : node_(node), type_(type) {}
35 
node()36   Node* node() const { return node_; }
type()37   MachineType type() const { return type_; }
38 
39  private:
40   Node* node_;
41   MachineType type_;
42 };
43 
44 // Instruction selection generates an InstructionSequence for a given Schedule.
45 class InstructionSelector final {
46  public:
47   // Forward declarations.
48   class Features;
49 
50   enum SourcePositionMode { kCallSourcePositions, kAllSourcePositions };
51 
52   InstructionSelector(
53       Zone* zone, size_t node_count, Linkage* linkage,
54       InstructionSequence* sequence, Schedule* schedule,
55       SourcePositionTable* source_positions,
56       SourcePositionMode source_position_mode = kCallSourcePositions,
57       Features features = SupportedFeatures());
58 
59   // Visit code for the entire graph with the included schedule.
60   void SelectInstructions();
61 
62   void StartBlock(RpoNumber rpo);
63   void EndBlock(RpoNumber rpo);
64   void AddInstruction(Instruction* instr);
65 
66   // ===========================================================================
67   // ============= Architecture-independent code emission methods. =============
68   // ===========================================================================
69 
70   Instruction* Emit(InstructionCode opcode, InstructionOperand output,
71                     size_t temp_count = 0, InstructionOperand* temps = nullptr);
72   Instruction* Emit(InstructionCode opcode, InstructionOperand output,
73                     InstructionOperand a, size_t temp_count = 0,
74                     InstructionOperand* temps = nullptr);
75   Instruction* Emit(InstructionCode opcode, InstructionOperand output,
76                     InstructionOperand a, InstructionOperand b,
77                     size_t temp_count = 0, InstructionOperand* temps = nullptr);
78   Instruction* Emit(InstructionCode opcode, InstructionOperand output,
79                     InstructionOperand a, InstructionOperand b,
80                     InstructionOperand c, size_t temp_count = 0,
81                     InstructionOperand* temps = nullptr);
82   Instruction* Emit(InstructionCode opcode, InstructionOperand output,
83                     InstructionOperand a, InstructionOperand b,
84                     InstructionOperand c, InstructionOperand d,
85                     size_t temp_count = 0, InstructionOperand* temps = nullptr);
86   Instruction* Emit(InstructionCode opcode, InstructionOperand output,
87                     InstructionOperand a, InstructionOperand b,
88                     InstructionOperand c, InstructionOperand d,
89                     InstructionOperand e, size_t temp_count = 0,
90                     InstructionOperand* temps = nullptr);
91   Instruction* Emit(InstructionCode opcode, InstructionOperand output,
92                     InstructionOperand a, InstructionOperand b,
93                     InstructionOperand c, InstructionOperand d,
94                     InstructionOperand e, InstructionOperand f,
95                     size_t temp_count = 0, InstructionOperand* temps = nullptr);
96   Instruction* Emit(InstructionCode opcode, size_t output_count,
97                     InstructionOperand* outputs, size_t input_count,
98                     InstructionOperand* inputs, size_t temp_count = 0,
99                     InstructionOperand* temps = nullptr);
100   Instruction* Emit(Instruction* instr);
101 
102   // ===========================================================================
103   // ============== Architecture-independent CPU feature methods. ==============
104   // ===========================================================================
105 
106   class Features final {
107    public:
Features()108     Features() : bits_(0) {}
Features(unsigned bits)109     explicit Features(unsigned bits) : bits_(bits) {}
Features(CpuFeature f)110     explicit Features(CpuFeature f) : bits_(1u << f) {}
Features(CpuFeature f1,CpuFeature f2)111     Features(CpuFeature f1, CpuFeature f2) : bits_((1u << f1) | (1u << f2)) {}
112 
Contains(CpuFeature f)113     bool Contains(CpuFeature f) const { return (bits_ & (1u << f)); }
114 
115    private:
116     unsigned bits_;
117   };
118 
IsSupported(CpuFeature feature)119   bool IsSupported(CpuFeature feature) const {
120     return features_.Contains(feature);
121   }
122 
123   // Returns the features supported on the target platform.
SupportedFeatures()124   static Features SupportedFeatures() {
125     return Features(CpuFeatures::SupportedFeatures());
126   }
127 
128   // TODO(sigurds) This should take a CpuFeatures argument.
129   static MachineOperatorBuilder::Flags SupportedMachineOperatorFlags();
130 
131   // ===========================================================================
132   // ============ Architecture-independent graph covering methods. =============
133   // ===========================================================================
134 
135   // Used in pattern matching during code generation.
136   // Check if {node} can be covered while generating code for the current
137   // instruction. A node can be covered if the {user} of the node has the only
138   // edge and the two are in the same basic block.
139   bool CanCover(Node* user, Node* node) const;
140 
141   // Checks if {node} was already defined, and therefore code was already
142   // generated for it.
143   bool IsDefined(Node* node) const;
144 
145   // Checks if {node} has any uses, and therefore code has to be generated for
146   // it.
147   bool IsUsed(Node* node) const;
148 
149   // Checks if {node} is currently live.
IsLive(Node * node)150   bool IsLive(Node* node) const { return !IsDefined(node) && IsUsed(node); }
151 
152   int GetVirtualRegister(const Node* node);
153   const std::map<NodeId, int> GetVirtualRegistersForTesting() const;
154 
isolate()155   Isolate* isolate() const { return sequence()->isolate(); }
156 
157  private:
158   friend class OperandGenerator;
159 
160   void EmitTableSwitch(const SwitchInfo& sw, InstructionOperand& index_operand);
161   void EmitLookupSwitch(const SwitchInfo& sw,
162                         InstructionOperand& value_operand);
163 
164   // Inform the instruction selection that {node} was just defined.
165   void MarkAsDefined(Node* node);
166 
167   // Inform the instruction selection that {node} has at least one use and we
168   // will need to generate code for it.
169   void MarkAsUsed(Node* node);
170 
171   // Inform the register allocation of the representation of the value produced
172   // by {node}.
173   void MarkAsRepresentation(MachineRepresentation rep, Node* node);
MarkAsWord32(Node * node)174   void MarkAsWord32(Node* node) {
175     MarkAsRepresentation(MachineRepresentation::kWord32, node);
176   }
MarkAsWord64(Node * node)177   void MarkAsWord64(Node* node) {
178     MarkAsRepresentation(MachineRepresentation::kWord64, node);
179   }
MarkAsFloat32(Node * node)180   void MarkAsFloat32(Node* node) {
181     MarkAsRepresentation(MachineRepresentation::kFloat32, node);
182   }
MarkAsFloat64(Node * node)183   void MarkAsFloat64(Node* node) {
184     MarkAsRepresentation(MachineRepresentation::kFloat64, node);
185   }
MarkAsReference(Node * node)186   void MarkAsReference(Node* node) {
187     MarkAsRepresentation(MachineRepresentation::kTagged, node);
188   }
189 
190   // Inform the register allocation of the representation of the unallocated
191   // operand {op}.
192   void MarkAsRepresentation(MachineRepresentation rep,
193                             const InstructionOperand& op);
194 
195   enum CallBufferFlag {
196     kCallCodeImmediate = 1u << 0,
197     kCallAddressImmediate = 1u << 1,
198     kCallTail = 1u << 2
199   };
200   typedef base::Flags<CallBufferFlag> CallBufferFlags;
201 
202   // Initialize the call buffer with the InstructionOperands, nodes, etc,
203   // corresponding
204   // to the inputs and outputs of the call.
205   // {call_code_immediate} to generate immediate operands to calls of code.
206   // {call_address_immediate} to generate immediate operands to address calls.
207   void InitializeCallBuffer(Node* call, CallBuffer* buffer,
208                             CallBufferFlags flags, int stack_param_delta = 0);
209   bool IsTailCallAddressImmediate();
210 
211   FrameStateDescriptor* GetFrameStateDescriptor(Node* node);
212 
213   // ===========================================================================
214   // ============= Architecture-specific graph covering methods. ===============
215   // ===========================================================================
216 
217   // Visit nodes in the given block and generate code.
218   void VisitBlock(BasicBlock* block);
219 
220   // Visit the node for the control flow at the end of the block, generating
221   // code if necessary.
222   void VisitControl(BasicBlock* block);
223 
224   // Visit the node and generate code, if any.
225   void VisitNode(Node* node);
226 
227 #define DECLARE_GENERATOR(x) void Visit##x(Node* node);
228   MACHINE_OP_LIST(DECLARE_GENERATOR)
229 #undef DECLARE_GENERATOR
230 
231   void VisitFinishRegion(Node* node);
232   void VisitGuard(Node* node);
233   void VisitParameter(Node* node);
234   void VisitIfException(Node* node);
235   void VisitOsrValue(Node* node);
236   void VisitPhi(Node* node);
237   void VisitProjection(Node* node);
238   void VisitConstant(Node* node);
239   void VisitCall(Node* call, BasicBlock* handler = nullptr);
240   void VisitTailCall(Node* call);
241   void VisitGoto(BasicBlock* target);
242   void VisitBranch(Node* input, BasicBlock* tbranch, BasicBlock* fbranch);
243   void VisitSwitch(Node* node, const SwitchInfo& sw);
244   void VisitDeoptimize(DeoptimizeKind kind, Node* value);
245   void VisitReturn(Node* ret);
246   void VisitThrow(Node* value);
247 
248   void EmitPrepareArguments(ZoneVector<compiler::PushParameter>* arguments,
249                             const CallDescriptor* descriptor, Node* node);
250 
251   // ===========================================================================
252 
schedule()253   Schedule* schedule() const { return schedule_; }
linkage()254   Linkage* linkage() const { return linkage_; }
sequence()255   InstructionSequence* sequence() const { return sequence_; }
instruction_zone()256   Zone* instruction_zone() const { return sequence()->zone(); }
zone()257   Zone* zone() const { return zone_; }
258 
259   // ===========================================================================
260 
261   Zone* const zone_;
262   Linkage* const linkage_;
263   InstructionSequence* const sequence_;
264   SourcePositionTable* const source_positions_;
265   SourcePositionMode const source_position_mode_;
266   Features features_;
267   Schedule* const schedule_;
268   BasicBlock* current_block_;
269   ZoneVector<Instruction*> instructions_;
270   BoolVector defined_;
271   BoolVector used_;
272   IntVector virtual_registers_;
273   InstructionScheduler* scheduler_;
274 };
275 
276 }  // namespace compiler
277 }  // namespace internal
278 }  // namespace v8
279 
280 #endif  // V8_COMPILER_INSTRUCTION_SELECTOR_H_
281