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
12namespace v8 {
13namespace internal {
14
15class JSGraph;
16class Graph;
17
18namespace 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
83class GraphAssembler;
84
85enum class GraphAssemblerLabelType { kDeferred, kNonDeferred };
86
87// Label with statically known count of incoming branches and phis.
88template <size_t MergeCount, size_t VarCount = 0u>
89class GraphAssemblerStaticLabel {
90 public:
91  Node* PhiAt(size_t index);
92
93  template <typename... 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
105  ~GraphAssemblerStaticLabel() { DCHECK(IsBound() || MergedCount() == 0); }
106
107 private:
108  friend class GraphAssembler;
109
110  void SetBound() {
111    DCHECK(!IsBound());
112    DCHECK_EQ(merged_count_, MergeCount);
113    is_bound_ = true;
114  }
115  bool IsBound() const { return is_bound_; }
116
117  size_t PhiCount() const { return VarCount; }
118  size_t MaxMergeCount() const { return MergeCount; }
119  size_t MergedCount() const { return merged_count_; }
120  bool IsDeferred() const { return is_deferred_; }
121
122  // For each phi, the buffer must have at least MaxMergeCount() + 1
123  // node entries.
124  Node** GetBindingsPtrFor(size_t phi_index) {
125    DCHECK_LT(phi_index, PhiCount());
126    return &bindings_[phi_index * (MergeCount + 1)];
127  }
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  }
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.
138  Node** GetControlsPtr() { return controls_; }
139  // The effects buffer must have at least MaxMergeCount() + 1 entries.
140  Node** GetEffectsPtr() { return effects_; }
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).
156class 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
169  void SetBound() {
170    DCHECK(!is_bound_);
171    is_bound_ = true;
172  }
173  bool IsBound() const { return is_bound_; }
174  size_t PhiCount() const { return var_count_; }
175  size_t MaxMergeCount() const { return max_merge_count_; }
176  size_t MergedCount() const { return merged_count_; }
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();
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
201class 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>
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)>
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>
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
316  JSGraph* jsgraph() const { return jsgraph_; }
317  Graph* graph() const { return jsgraph_->graph(); }
318  Zone* temp_zone() const { return temp_zone_; }
319  CommonOperatorBuilder* common() const { return jsgraph()->common(); }
320  MachineOperatorBuilder* machine() const { return jsgraph()->machine(); }
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
332template <size_t MergeCount, size_t VarCount>
333Node* GraphAssemblerStaticLabel<MergeCount, VarCount>::PhiAt(size_t index) {
334  DCHECK(IsBound());
335  return GetBindingsPtrFor(index)[0];
336}
337
338template <class LabelType, typename... Vars>
339void 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
354template <class LabelType>
355void 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
394template <class LabelType, typename... Vars>
395void 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
403template <class LabelType, typename... Vars>
404void 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
416template <class LabelType, typename... Vars>
417void 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
429template <typename... Args>
430Node* GraphAssembler::Call(const CallDescriptor* desc, Args... args) {
431  const Operator* op = common()->Call(desc);
432  return Call(op, args...);
433}
434
435template <typename... Args>
436Node* 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