1// Copyright 2015 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_INTERPRETER_CONTROL_FLOW_BUILDERS_H_
6#define V8_INTERPRETER_CONTROL_FLOW_BUILDERS_H_
7
8#include <map>
9
10#include "src/ast/ast-source-ranges.h"
11#include "src/interpreter/block-coverage-builder.h"
12#include "src/interpreter/bytecode-array-builder.h"
13#include "src/interpreter/bytecode-generator.h"
14#include "src/interpreter/bytecode-jump-table.h"
15#include "src/interpreter/bytecode-label.h"
16#include "src/zone/zone-containers.h"
17
18namespace v8 {
19namespace internal {
20namespace interpreter {
21
22class V8_EXPORT_PRIVATE ControlFlowBuilder {
23 public:
24  explicit ControlFlowBuilder(BytecodeArrayBuilder* builder)
25      : builder_(builder) {}
26  ControlFlowBuilder(const ControlFlowBuilder&) = delete;
27  ControlFlowBuilder& operator=(const ControlFlowBuilder&) = delete;
28  virtual ~ControlFlowBuilder() = default;
29
30 protected:
31  BytecodeArrayBuilder* builder() const { return builder_; }
32
33 private:
34  BytecodeArrayBuilder* builder_;
35};
36
37class V8_EXPORT_PRIVATE BreakableControlFlowBuilder
38    : public ControlFlowBuilder {
39 public:
40  BreakableControlFlowBuilder(BytecodeArrayBuilder* builder,
41                              BlockCoverageBuilder* block_coverage_builder,
42                              AstNode* node)
43      : ControlFlowBuilder(builder),
44        break_labels_(builder->zone()),
45        node_(node),
46        block_coverage_builder_(block_coverage_builder) {}
47  ~BreakableControlFlowBuilder() override;
48
49  // This method is called when visiting break statements in the AST.
50  // Inserts a jump to an unbound label that is patched when the corresponding
51  // BindBreakTarget is called.
52  void Break() { EmitJump(&break_labels_); }
53  void BreakIfTrue(BytecodeArrayBuilder::ToBooleanMode mode) {
54    EmitJumpIfTrue(mode, &break_labels_);
55  }
56  void BreakIfFalse(BytecodeArrayBuilder::ToBooleanMode mode) {
57    EmitJumpIfFalse(mode, &break_labels_);
58  }
59  void BreakIfUndefined() { EmitJumpIfUndefined(&break_labels_); }
60  void BreakIfNull() { EmitJumpIfNull(&break_labels_); }
61
62  BytecodeLabels* break_labels() { return &break_labels_; }
63
64 protected:
65  void EmitJump(BytecodeLabels* labels);
66  void EmitJumpIfTrue(BytecodeArrayBuilder::ToBooleanMode mode,
67                      BytecodeLabels* labels);
68  void EmitJumpIfFalse(BytecodeArrayBuilder::ToBooleanMode mode,
69                       BytecodeLabels* labels);
70  void EmitJumpIfUndefined(BytecodeLabels* labels);
71  void EmitJumpIfNull(BytecodeLabels* labels);
72
73  // Called from the destructor to update sites that emit jumps for break.
74  void BindBreakTarget();
75
76  // Unbound labels that identify jumps for break statements in the code.
77  BytecodeLabels break_labels_;
78
79  // A continuation counter (for block coverage) is needed e.g. when
80  // encountering a break statement.
81  AstNode* node_;
82  BlockCoverageBuilder* block_coverage_builder_;
83};
84
85// Class to track control flow for block statements (which can break in JS).
86class V8_EXPORT_PRIVATE BlockBuilder final
87    : public BreakableControlFlowBuilder {
88 public:
89  BlockBuilder(BytecodeArrayBuilder* builder,
90               BlockCoverageBuilder* block_coverage_builder,
91               BreakableStatement* statement)
92      : BreakableControlFlowBuilder(builder, block_coverage_builder,
93                                    statement) {}
94};
95
96// A class to help with co-ordinating break and continue statements with
97// their loop.
98class V8_EXPORT_PRIVATE LoopBuilder final : public BreakableControlFlowBuilder {
99 public:
100  LoopBuilder(BytecodeArrayBuilder* builder,
101              BlockCoverageBuilder* block_coverage_builder, AstNode* node)
102      : BreakableControlFlowBuilder(builder, block_coverage_builder, node),
103        continue_labels_(builder->zone()),
104        end_labels_(builder->zone()) {
105    if (block_coverage_builder_ != nullptr) {
106      block_coverage_body_slot_ =
107          block_coverage_builder_->AllocateBlockCoverageSlot(
108              node, SourceRangeKind::kBody);
109    }
110    source_position_ = node ? node->position() : kNoSourcePosition;
111  }
112  ~LoopBuilder() override;
113
114  void LoopHeader();
115  void LoopBody();
116  void JumpToHeader(int loop_depth, LoopBuilder* const parent_loop);
117  void BindContinueTarget();
118
119  // This method is called when visiting continue statements in the AST.
120  // Inserts a jump to an unbound label that is patched when BindContinueTarget
121  // is called.
122  void Continue() { EmitJump(&continue_labels_); }
123  void ContinueIfUndefined() { EmitJumpIfUndefined(&continue_labels_); }
124  void ContinueIfNull() { EmitJumpIfNull(&continue_labels_); }
125
126 private:
127  // Emit a Jump to our parent_loop_'s end label which could be a JumpLoop or,
128  // iff they are a nested inner loop with the same loop header bytecode offset
129  // as their parent's, a Jump to its parent's end label.
130  void JumpToLoopEnd() { EmitJump(&end_labels_); }
131  void BindLoopEnd();
132
133  BytecodeLoopHeader loop_header_;
134
135  // Unbound labels that identify jumps for continue statements in the code and
136  // jumps from checking the loop condition to the header for do-while loops.
137  BytecodeLabels continue_labels_;
138
139  // Unbound labels that identify jumps for nested inner loops which share the
140  // same header offset as this loop. Said inner loops will Jump to our end
141  // label, which could be a JumpLoop or, iff we are a nested inner loop too, a
142  // Jump to our parent's end label.
143  BytecodeLabels end_labels_;
144
145  int block_coverage_body_slot_;
146
147  int source_position_;
148};
149
150// A class to help with co-ordinating break statements with their switch.
151class V8_EXPORT_PRIVATE SwitchBuilder final
152    : public BreakableControlFlowBuilder {
153 public:
154  SwitchBuilder(BytecodeArrayBuilder* builder,
155                BlockCoverageBuilder* block_coverage_builder,
156                SwitchStatement* statement, int number_of_cases,
157                BytecodeJumpTable* jump_table)
158      : BreakableControlFlowBuilder(builder, block_coverage_builder, statement),
159        case_sites_(builder->zone()),
160        default_(builder->zone()),
161        fall_through_(builder->zone()),
162        jump_table_(jump_table) {
163    case_sites_.resize(number_of_cases);
164  }
165
166  ~SwitchBuilder() override;
167
168  void BindCaseTargetForJumpTable(int case_value, CaseClause* clause);
169
170  void BindCaseTargetForCompareJump(int index, CaseClause* clause);
171
172  // This method is called when visiting case comparison operation for |index|.
173  // Inserts a JumpIfTrue with ToBooleanMode |mode| to a unbound label that is
174  // patched when the corresponding SetCaseTarget is called.
175  void JumpToCaseIfTrue(BytecodeArrayBuilder::ToBooleanMode mode, int index);
176
177  void EmitJumpTableIfExists(int min_case, int max_case,
178                             std::map<int, CaseClause*>& covered_cases);
179
180  void BindDefault(CaseClause* clause);
181
182  void JumpToDefault();
183
184  void JumpToFallThroughIfFalse();
185
186 private:
187  // Unbound labels that identify jumps for case statements in the code.
188  ZoneVector<BytecodeLabel> case_sites_;
189  BytecodeLabels default_;
190  BytecodeLabels fall_through_;
191  BytecodeJumpTable* jump_table_;
192
193  void BuildBlockCoverage(CaseClause* clause) {
194    if (block_coverage_builder_ && clause != nullptr) {
195      block_coverage_builder_->IncrementBlockCounter(clause,
196                                                     SourceRangeKind::kBody);
197    }
198  }
199};
200
201// A class to help with co-ordinating control flow in try-catch statements.
202class V8_EXPORT_PRIVATE TryCatchBuilder final : public ControlFlowBuilder {
203 public:
204  TryCatchBuilder(BytecodeArrayBuilder* builder,
205                  BlockCoverageBuilder* block_coverage_builder,
206                  TryCatchStatement* statement,
207                  HandlerTable::CatchPrediction catch_prediction)
208      : ControlFlowBuilder(builder),
209        handler_id_(builder->NewHandlerEntry()),
210        catch_prediction_(catch_prediction),
211        block_coverage_builder_(block_coverage_builder),
212        statement_(statement) {}
213
214  ~TryCatchBuilder() override;
215
216  void BeginTry(Register context);
217  void EndTry();
218  void EndCatch();
219
220 private:
221  int handler_id_;
222  HandlerTable::CatchPrediction catch_prediction_;
223  BytecodeLabel exit_;
224
225  BlockCoverageBuilder* block_coverage_builder_;
226  TryCatchStatement* statement_;
227};
228
229// A class to help with co-ordinating control flow in try-finally statements.
230class V8_EXPORT_PRIVATE TryFinallyBuilder final : public ControlFlowBuilder {
231 public:
232  TryFinallyBuilder(BytecodeArrayBuilder* builder,
233                    BlockCoverageBuilder* block_coverage_builder,
234                    TryFinallyStatement* statement,
235                    HandlerTable::CatchPrediction catch_prediction)
236      : ControlFlowBuilder(builder),
237        handler_id_(builder->NewHandlerEntry()),
238        catch_prediction_(catch_prediction),
239        finalization_sites_(builder->zone()),
240        block_coverage_builder_(block_coverage_builder),
241        statement_(statement) {}
242
243  ~TryFinallyBuilder() override;
244
245  void BeginTry(Register context);
246  void LeaveTry();
247  void EndTry();
248  void BeginHandler();
249  void BeginFinally();
250  void EndFinally();
251
252 private:
253  int handler_id_;
254  HandlerTable::CatchPrediction catch_prediction_;
255  BytecodeLabel handler_;
256
257  // Unbound labels that identify jumps to the finally block in the code.
258  BytecodeLabels finalization_sites_;
259
260  BlockCoverageBuilder* block_coverage_builder_;
261  TryFinallyStatement* statement_;
262};
263
264class V8_EXPORT_PRIVATE ConditionalControlFlowBuilder final
265    : public ControlFlowBuilder {
266 public:
267  ConditionalControlFlowBuilder(BytecodeArrayBuilder* builder,
268                                BlockCoverageBuilder* block_coverage_builder,
269                                AstNode* node)
270      : ControlFlowBuilder(builder),
271        end_labels_(builder->zone()),
272        then_labels_(builder->zone()),
273        else_labels_(builder->zone()),
274        node_(node),
275        block_coverage_builder_(block_coverage_builder) {
276    DCHECK(node->IsIfStatement() || node->IsConditional());
277    if (block_coverage_builder != nullptr) {
278      block_coverage_then_slot_ =
279          block_coverage_builder->AllocateBlockCoverageSlot(
280              node, SourceRangeKind::kThen);
281      block_coverage_else_slot_ =
282          block_coverage_builder->AllocateBlockCoverageSlot(
283              node, SourceRangeKind::kElse);
284    }
285  }
286  ~ConditionalControlFlowBuilder() override;
287
288  BytecodeLabels* then_labels() { return &then_labels_; }
289  BytecodeLabels* else_labels() { return &else_labels_; }
290
291  void Then();
292  void Else();
293
294  void JumpToEnd();
295
296 private:
297  BytecodeLabels end_labels_;
298  BytecodeLabels then_labels_;
299  BytecodeLabels else_labels_;
300
301  AstNode* node_;
302  int block_coverage_then_slot_;
303  int block_coverage_else_slot_;
304  BlockCoverageBuilder* block_coverage_builder_;
305};
306
307}  // namespace interpreter
308}  // namespace internal
309}  // namespace v8
310
311#endif  // V8_INTERPRETER_CONTROL_FLOW_BUILDERS_H_
312