1 // Copyright 2016 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_GRAPH_ASSEMBLER_H_
6 #define V8_COMPILER_GRAPH_ASSEMBLER_H_
7
8 #include "src/compiler/js-graph.h"
9 #include "src/compiler/node.h"
10 #include "src/compiler/simplified-operator.h"
11
12 namespace v8 {
13 namespace internal {
14
15 class JSGraph;
16 class Graph;
17
18 namespace compiler {
19
20 #define PURE_ASSEMBLER_MACH_UNOP_LIST(V) \
21 V(ChangeInt32ToInt64) \
22 V(ChangeInt32ToFloat64) \
23 V(ChangeUint32ToFloat64) \
24 V(ChangeUint32ToUint64) \
25 V(ChangeFloat64ToInt32) \
26 V(ChangeFloat64ToUint32) \
27 V(TruncateInt64ToInt32) \
28 V(RoundFloat64ToInt32) \
29 V(TruncateFloat64ToWord32) \
30 V(Float64ExtractHighWord32) \
31 V(Float64Abs) \
32 V(BitcastWordToTagged)
33
34 #define PURE_ASSEMBLER_MACH_BINOP_LIST(V) \
35 V(WordShl) \
36 V(WordSar) \
37 V(WordAnd) \
38 V(Word32Or) \
39 V(Word32And) \
40 V(Word32Shr) \
41 V(Word32Shl) \
42 V(IntAdd) \
43 V(IntSub) \
44 V(UintLessThan) \
45 V(Int32Add) \
46 V(Int32Sub) \
47 V(Int32Mul) \
48 V(Int32LessThanOrEqual) \
49 V(Uint32LessThanOrEqual) \
50 V(Uint32LessThan) \
51 V(Int32LessThan) \
52 V(Float64Add) \
53 V(Float64Sub) \
54 V(Float64Mod) \
55 V(Float64Equal) \
56 V(Float64LessThan) \
57 V(Float64LessThanOrEqual) \
58 V(Word32Equal) \
59 V(WordEqual)
60
61 #define CHECKED_ASSEMBLER_MACH_BINOP_LIST(V) \
62 V(Int32AddWithOverflow) \
63 V(Int32SubWithOverflow) \
64 V(Int32MulWithOverflow) \
65 V(Int32Mod) \
66 V(Int32Div) \
67 V(Uint32Mod) \
68 V(Uint32Div)
69
70 #define JSGRAPH_SINGLETON_CONSTANT_LIST(V) \
71 V(TrueConstant) \
72 V(FalseConstant) \
73 V(HeapNumberMapConstant) \
74 V(NoContextConstant) \
75 V(EmptyStringConstant) \
76 V(UndefinedConstant) \
77 V(TheHoleConstant) \
78 V(FixedArrayMapConstant) \
79 V(ToNumberBuiltinConstant) \
80 V(AllocateInNewSpaceStubConstant) \
81 V(AllocateInOldSpaceStubConstant)
82
83 class GraphAssembler;
84
85 enum class GraphAssemblerLabelType { kDeferred, kNonDeferred };
86
87 // Label with statically known count of incoming branches and phis.
88 template <size_t MergeCount, size_t VarCount = 0u>
89 class GraphAssemblerStaticLabel {
90 public:
91 Node* PhiAt(size_t index);
92
93 template <typename... Reps>
GraphAssemblerStaticLabel(GraphAssemblerLabelType is_deferred,Reps...reps)94 explicit GraphAssemblerStaticLabel(GraphAssemblerLabelType is_deferred,
95 Reps... reps)
96 : is_deferred_(is_deferred == GraphAssemblerLabelType::kDeferred) {
97 STATIC_ASSERT(VarCount == sizeof...(reps));
98 MachineRepresentation reps_array[] = {MachineRepresentation::kNone,
99 reps...};
100 for (size_t i = 0; i < VarCount; i++) {
101 representations_[i] = reps_array[i + 1];
102 }
103 }
104
~GraphAssemblerStaticLabel()105 ~GraphAssemblerStaticLabel() { DCHECK(IsBound() || MergedCount() == 0); }
106
107 private:
108 friend class GraphAssembler;
109
SetBound()110 void SetBound() {
111 DCHECK(!IsBound());
112 DCHECK_EQ(merged_count_, MergeCount);
113 is_bound_ = true;
114 }
IsBound()115 bool IsBound() const { return is_bound_; }
116
PhiCount()117 size_t PhiCount() const { return VarCount; }
MaxMergeCount()118 size_t MaxMergeCount() const { return MergeCount; }
MergedCount()119 size_t MergedCount() const { return merged_count_; }
IsDeferred()120 bool IsDeferred() const { return is_deferred_; }
121
122 // For each phi, the buffer must have at least MaxMergeCount() + 1
123 // node entries.
GetBindingsPtrFor(size_t phi_index)124 Node** GetBindingsPtrFor(size_t phi_index) {
125 DCHECK_LT(phi_index, PhiCount());
126 return &bindings_[phi_index * (MergeCount + 1)];
127 }
SetBinding(size_t phi_index,size_t merge_index,Node * binding)128 void SetBinding(size_t phi_index, size_t merge_index, Node* binding) {
129 DCHECK_LT(phi_index, PhiCount());
130 DCHECK_LT(merge_index, MergeCount);
131 bindings_[phi_index * (MergeCount + 1) + merge_index] = binding;
132 }
GetRepresentationFor(size_t phi_index)133 MachineRepresentation GetRepresentationFor(size_t phi_index) {
134 DCHECK_LT(phi_index, PhiCount());
135 return representations_[phi_index];
136 }
137 // The controls buffer must have at least MaxMergeCount() entries.
GetControlsPtr()138 Node** GetControlsPtr() { return controls_; }
139 // The effects buffer must have at least MaxMergeCount() + 1 entries.
GetEffectsPtr()140 Node** GetEffectsPtr() { return effects_; }
IncrementMergedCount()141 void IncrementMergedCount() { merged_count_++; }
142
143 bool is_bound_ = false;
144 bool is_deferred_;
145 size_t merged_count_ = 0;
146 Node* effects_[MergeCount + 1]; // Extra element for control edge,
147 // so that we can use the array to
148 // construct EffectPhi.
149 Node* controls_[MergeCount];
150 Node* bindings_[(MergeCount + 1) * VarCount + 1];
151 MachineRepresentation representations_[VarCount + 1];
152 };
153
154 // General label (with zone allocated buffers for incoming branches and phi
155 // inputs).
156 class GraphAssemblerLabel {
157 public:
158 Node* PhiAt(size_t index);
159
160 GraphAssemblerLabel(GraphAssemblerLabelType is_deferred, size_t merge_count,
161 size_t var_count, MachineRepresentation* representations,
162 Zone* zone);
163
164 ~GraphAssemblerLabel();
165
166 private:
167 friend class GraphAssembler;
168
SetBound()169 void SetBound() {
170 DCHECK(!is_bound_);
171 is_bound_ = true;
172 }
IsBound()173 bool IsBound() const { return is_bound_; }
PhiCount()174 size_t PhiCount() const { return var_count_; }
MaxMergeCount()175 size_t MaxMergeCount() const { return max_merge_count_; }
MergedCount()176 size_t MergedCount() const { return merged_count_; }
IsDeferred()177 bool IsDeferred() const { return is_deferred_; }
178
179 // For each phi, the buffer must have at least MaxMergeCount() + 1
180 // node entries.
181 Node** GetBindingsPtrFor(size_t phi_index);
182 void SetBinding(size_t phi_index, size_t merge_index, Node* binding);
183 MachineRepresentation GetRepresentationFor(size_t phi_index);
184 // The controls buffer must have at least MaxMergeCount() entries.
185 Node** GetControlsPtr();
186 // The effects buffer must have at least MaxMergeCount() + 1 entries.
187 Node** GetEffectsPtr();
IncrementMergedCount()188 void IncrementMergedCount() { merged_count_++; }
189
190 bool is_bound_ = false;
191 bool is_deferred_;
192 size_t merged_count_ = 0;
193 size_t max_merge_count_;
194 size_t var_count_;
195 Node** effects_ = nullptr;
196 Node** controls_ = nullptr;
197 Node** bindings_ = nullptr;
198 MachineRepresentation* representations_ = nullptr;
199 };
200
201 class GraphAssembler {
202 public:
203 GraphAssembler(JSGraph* jsgraph, Node* effect, Node* control, Zone* zone);
204
205 void Reset(Node* effect, Node* control);
206
207 // Create non-deferred label with statically known number of incoming
208 // gotos/branches.
209 template <size_t MergeCount, typename... Reps>
MakeLabel(Reps...reps)210 static GraphAssemblerStaticLabel<MergeCount, sizeof...(Reps)> MakeLabel(
211 Reps... reps) {
212 return GraphAssemblerStaticLabel<MergeCount, sizeof...(Reps)>(
213 GraphAssemblerLabelType::kNonDeferred, reps...);
214 }
215
216 // Create deferred label with statically known number of incoming
217 // gotos/branches.
218 template <size_t MergeCount, typename... Reps>
219 static GraphAssemblerStaticLabel<MergeCount, sizeof...(Reps)>
MakeDeferredLabel(Reps...reps)220 MakeDeferredLabel(Reps... reps) {
221 return GraphAssemblerStaticLabel<MergeCount, sizeof...(Reps)>(
222 GraphAssemblerLabelType::kDeferred, reps...);
223 }
224
225 // Create label with number of incoming branches supplied at runtime.
226 template <typename... Reps>
MakeLabelFor(GraphAssemblerLabelType is_deferred,size_t merge_count,Reps...reps)227 GraphAssemblerLabel MakeLabelFor(GraphAssemblerLabelType is_deferred,
228 size_t merge_count, Reps... reps) {
229 MachineRepresentation reps_array[] = {MachineRepresentation::kNone,
230 reps...};
231 return GraphAssemblerLabel(is_deferred, merge_count, sizeof...(reps),
232 &(reps_array[1]), temp_zone());
233 }
234
235 // Value creation.
236 Node* IntPtrConstant(intptr_t value);
237 Node* Uint32Constant(int32_t value);
238 Node* Int32Constant(int32_t value);
239 Node* UniqueInt32Constant(int32_t value);
240 Node* SmiConstant(int32_t value);
241 Node* Float64Constant(double value);
242 Node* Projection(int index, Node* value);
243 Node* HeapConstant(Handle<HeapObject> object);
244 Node* CEntryStubConstant(int result_size);
245 Node* ExternalConstant(ExternalReference ref);
246
247 #define SINGLETON_CONST_DECL(Name) Node* Name();
248 JSGRAPH_SINGLETON_CONSTANT_LIST(SINGLETON_CONST_DECL)
249 #undef SINGLETON_CONST_DECL
250
251 #define PURE_UNOP_DECL(Name) Node* Name(Node* input);
252 PURE_ASSEMBLER_MACH_UNOP_LIST(PURE_UNOP_DECL)
253 #undef PURE_UNOP_DECL
254
255 #define BINOP_DECL(Name) Node* Name(Node* left, Node* right);
256 PURE_ASSEMBLER_MACH_BINOP_LIST(BINOP_DECL)
257 CHECKED_ASSEMBLER_MACH_BINOP_LIST(BINOP_DECL)
258 #undef BINOP_DECL
259
260 Node* Float64RoundDown(Node* value);
261
262 Node* ToNumber(Node* value);
263 Node* Allocate(PretenureFlag pretenure, Node* size);
264 Node* LoadField(FieldAccess const&, Node* object);
265 Node* LoadElement(ElementAccess const&, Node* object, Node* index);
266 Node* StoreField(FieldAccess const&, Node* object, Node* value);
267 Node* StoreElement(ElementAccess const&, Node* object, Node* index,
268 Node* value);
269
270 Node* Store(StoreRepresentation rep, Node* object, Node* offset, Node* value);
271 Node* Load(MachineType rep, Node* object, Node* offset);
272
273 Node* Retain(Node* buffer);
274 Node* UnsafePointerAdd(Node* base, Node* external);
275
276 Node* DeoptimizeIf(DeoptimizeReason reason, Node* condition,
277 Node* frame_state);
278 Node* DeoptimizeUnless(DeoptimizeKind kind, DeoptimizeReason reason,
279 Node* condition, Node* frame_state);
280 Node* DeoptimizeUnless(DeoptimizeReason reason, Node* condition,
281 Node* frame_state);
282 template <typename... Args>
283 Node* Call(const CallDescriptor* desc, Args... args);
284 template <typename... Args>
285 Node* Call(const Operator* op, Args... args);
286
287 // Basic control operations.
288 template <class LabelType>
289 void Bind(LabelType* label);
290
291 template <class LabelType, typename... vars>
292 void Goto(LabelType* label, vars...);
293
294 void Branch(Node* condition, GraphAssemblerStaticLabel<1>* if_true,
295 GraphAssemblerStaticLabel<1>* if_false);
296
297 // Control helpers.
298 // {GotoIf(c, l)} is equivalent to {Branch(c, l, templ);Bind(templ)}.
299 template <class LabelType, typename... vars>
300 void GotoIf(Node* condition, LabelType* label, vars...);
301
302 // {GotoUnless(c, l)} is equivalent to {Branch(c, templ, l);Bind(templ)}.
303 template <class LabelType, typename... vars>
304 void GotoUnless(Node* condition, LabelType* label, vars...);
305
306 // Extractors (should be only used when destructing/resetting the assembler).
307 Node* ExtractCurrentControl();
308 Node* ExtractCurrentEffect();
309
310 private:
311 template <class LabelType, typename... Vars>
312 void MergeState(LabelType label, Vars... vars);
313
314 Operator const* ToNumberOperator();
315
jsgraph()316 JSGraph* jsgraph() const { return jsgraph_; }
graph()317 Graph* graph() const { return jsgraph_->graph(); }
temp_zone()318 Zone* temp_zone() const { return temp_zone_; }
common()319 CommonOperatorBuilder* common() const { return jsgraph()->common(); }
machine()320 MachineOperatorBuilder* machine() const { return jsgraph()->machine(); }
simplified()321 SimplifiedOperatorBuilder* simplified() const {
322 return jsgraph()->simplified();
323 }
324
325 SetOncePointer<Operator const> to_number_operator_;
326 Zone* temp_zone_;
327 JSGraph* jsgraph_;
328 Node* current_effect_;
329 Node* current_control_;
330 };
331
332 template <size_t MergeCount, size_t VarCount>
PhiAt(size_t index)333 Node* GraphAssemblerStaticLabel<MergeCount, VarCount>::PhiAt(size_t index) {
334 DCHECK(IsBound());
335 return GetBindingsPtrFor(index)[0];
336 }
337
338 template <class LabelType, typename... Vars>
MergeState(LabelType label,Vars...vars)339 void GraphAssembler::MergeState(LabelType label, Vars... vars) {
340 DCHECK(!label->IsBound());
341 size_t merged_count = label->MergedCount();
342 DCHECK_LT(merged_count, label->MaxMergeCount());
343 DCHECK_EQ(label->PhiCount(), sizeof...(vars));
344 label->GetEffectsPtr()[merged_count] = current_effect_;
345 label->GetControlsPtr()[merged_count] = current_control_;
346 // We need to start with nullptr to avoid 0-length arrays.
347 Node* var_array[] = {nullptr, vars...};
348 for (size_t i = 0; i < sizeof...(vars); i++) {
349 label->SetBinding(i, merged_count, var_array[i + 1]);
350 }
351 label->IncrementMergedCount();
352 }
353
354 template <class LabelType>
Bind(LabelType * label)355 void GraphAssembler::Bind(LabelType* label) {
356 DCHECK(current_control_ == nullptr);
357 DCHECK(current_effect_ == nullptr);
358 DCHECK(label->MaxMergeCount() > 0);
359 DCHECK_EQ(label->MaxMergeCount(), label->MergedCount());
360
361 int merge_count = static_cast<int>(label->MaxMergeCount());
362 if (merge_count == 1) {
363 current_control_ = label->GetControlsPtr()[0];
364 current_effect_ = label->GetEffectsPtr()[0];
365 label->SetBound();
366 return;
367 }
368
369 current_control_ = graph()->NewNode(common()->Merge(merge_count), merge_count,
370 label->GetControlsPtr());
371
372 Node** effects = label->GetEffectsPtr();
373 current_effect_ = effects[0];
374 for (size_t i = 1; i < label->MaxMergeCount(); i++) {
375 if (current_effect_ != effects[i]) {
376 effects[label->MaxMergeCount()] = current_control_;
377 current_effect_ = graph()->NewNode(common()->EffectPhi(merge_count),
378 merge_count + 1, effects);
379 break;
380 }
381 }
382
383 for (size_t var = 0; var < label->PhiCount(); var++) {
384 Node** bindings = label->GetBindingsPtrFor(var);
385 bindings[label->MaxMergeCount()] = current_control_;
386 bindings[0] = graph()->NewNode(
387 common()->Phi(label->GetRepresentationFor(var), merge_count),
388 merge_count + 1, bindings);
389 }
390
391 label->SetBound();
392 }
393
394 template <class LabelType, typename... Vars>
Goto(LabelType * label,Vars...vars)395 void GraphAssembler::Goto(LabelType* label, Vars... vars) {
396 DCHECK_NOT_NULL(current_control_);
397 DCHECK_NOT_NULL(current_effect_);
398 MergeState(label, vars...);
399 current_control_ = nullptr;
400 current_effect_ = nullptr;
401 }
402
403 template <class LabelType, typename... Vars>
GotoIf(Node * condition,LabelType * label,Vars...vars)404 void GraphAssembler::GotoIf(Node* condition, LabelType* label, Vars... vars) {
405 BranchHint hint =
406 label->IsDeferred() ? BranchHint::kFalse : BranchHint::kNone;
407 Node* branch =
408 graph()->NewNode(common()->Branch(hint), condition, current_control_);
409
410 current_control_ = graph()->NewNode(common()->IfTrue(), branch);
411 MergeState(label, vars...);
412
413 current_control_ = graph()->NewNode(common()->IfFalse(), branch);
414 }
415
416 template <class LabelType, typename... Vars>
GotoUnless(Node * condition,LabelType * label,Vars...vars)417 void GraphAssembler::GotoUnless(Node* condition, LabelType* label,
418 Vars... vars) {
419 BranchHint hint = label->IsDeferred() ? BranchHint::kTrue : BranchHint::kNone;
420 Node* branch =
421 graph()->NewNode(common()->Branch(hint), condition, current_control_);
422
423 current_control_ = graph()->NewNode(common()->IfFalse(), branch);
424 MergeState(label, vars...);
425
426 current_control_ = graph()->NewNode(common()->IfTrue(), branch);
427 }
428
429 template <typename... Args>
Call(const CallDescriptor * desc,Args...args)430 Node* GraphAssembler::Call(const CallDescriptor* desc, Args... args) {
431 const Operator* op = common()->Call(desc);
432 return Call(op, args...);
433 }
434
435 template <typename... Args>
Call(const Operator * op,Args...args)436 Node* GraphAssembler::Call(const Operator* op, Args... args) {
437 DCHECK_EQ(IrOpcode::kCall, op->opcode());
438 Node* args_array[] = {args..., current_effect_, current_control_};
439 int size = static_cast<int>(sizeof...(args)) + op->EffectInputCount() +
440 op->ControlInputCount();
441 Node* call = graph()->NewNode(op, size, args_array);
442 DCHECK_EQ(0, op->ControlOutputCount());
443 current_effect_ = call;
444 return call;
445 }
446
447 } // namespace compiler
448 } // namespace internal
449 } // namespace v8
450
451 #endif // V8_COMPILER_GRAPH_ASSEMBLER_H_
452