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_BYTECODE_ANALYSIS_H_
6#define V8_COMPILER_BYTECODE_ANALYSIS_H_
7
8#include "src/base/hashmap.h"
9#include "src/compiler/bytecode-liveness-map.h"
10#include "src/handles/handles.h"
11#include "src/interpreter/bytecode-register.h"
12#include "src/utils/bit-vector.h"
13#include "src/utils/utils.h"
14#include "src/zone/zone-containers.h"
15
16namespace v8 {
17namespace internal {
18
19class BytecodeArray;
20
21namespace compiler {
22
23class V8_EXPORT_PRIVATE BytecodeLoopAssignments {
24 public:
25  BytecodeLoopAssignments(int parameter_count, int register_count, Zone* zone);
26
27  void Add(interpreter::Register r);
28  void AddList(interpreter::Register r, uint32_t count);
29  void Union(const BytecodeLoopAssignments& other);
30
31  bool ContainsParameter(int index) const;
32  bool ContainsLocal(int index) const;
33
34  int parameter_count() const { return parameter_count_; }
35  int local_count() const { return bit_vector_->length() - parameter_count_; }
36
37 private:
38  int const parameter_count_;
39  BitVector* const bit_vector_;
40};
41
42// Jump targets for resuming a suspended generator.
43class V8_EXPORT_PRIVATE ResumeJumpTarget {
44 public:
45  // Create a resume jump target representing an actual resume.
46  static ResumeJumpTarget Leaf(int suspend_id, int target_offset);
47
48  // Create a resume jump target at a loop header, which will have another
49  // resume jump after the loop header is crossed.
50  static ResumeJumpTarget AtLoopHeader(int loop_header_offset,
51                                       const ResumeJumpTarget& next);
52
53  int suspend_id() const { return suspend_id_; }
54  int target_offset() const { return target_offset_; }
55  bool is_leaf() const { return target_offset_ == final_target_offset_; }
56
57 private:
58  // The suspend id of the resume.
59  int suspend_id_;
60  // The target offset of this resume jump.
61  int target_offset_;
62  // The final offset of this resume, which may be across multiple jumps.
63  int final_target_offset_;
64
65  ResumeJumpTarget(int suspend_id, int target_offset, int final_target_offset);
66};
67
68struct V8_EXPORT_PRIVATE LoopInfo {
69 public:
70  LoopInfo(int parent_offset, int parameter_count, int register_count,
71           Zone* zone)
72      : parent_offset_(parent_offset),
73        assignments_(parameter_count, register_count, zone),
74        resume_jump_targets_(zone) {}
75
76  int parent_offset() const { return parent_offset_; }
77
78  const ZoneVector<ResumeJumpTarget>& resume_jump_targets() const {
79    return resume_jump_targets_;
80  }
81  void AddResumeTarget(const ResumeJumpTarget& target) {
82    resume_jump_targets_.push_back(target);
83  }
84
85  BytecodeLoopAssignments& assignments() { return assignments_; }
86  const BytecodeLoopAssignments& assignments() const { return assignments_; }
87
88 private:
89  // The offset to the parent loop, or -1 if there is no parent.
90  int parent_offset_;
91  BytecodeLoopAssignments assignments_;
92  ZoneVector<ResumeJumpTarget> resume_jump_targets_;
93};
94
95// Analyze the bytecodes to find the loop ranges, loop nesting, loop assignments
96// and liveness.  NOTE: The broker/serializer relies on the fact that an
97// analysis for OSR (osr_bailout_id is not None) subsumes an analysis for
98// non-OSR (osr_bailout_id is None).
99class V8_EXPORT_PRIVATE BytecodeAnalysis : public ZoneObject {
100 public:
101  BytecodeAnalysis(Handle<BytecodeArray> bytecode_array, Zone* zone,
102                   BytecodeOffset osr_bailout_id, bool analyze_liveness);
103  BytecodeAnalysis(const BytecodeAnalysis&) = delete;
104  BytecodeAnalysis& operator=(const BytecodeAnalysis&) = delete;
105
106  // Return true if the given offset is a loop header
107  bool IsLoopHeader(int offset) const;
108  // Get the loop header offset of the containing loop for arbitrary
109  // {offset}, or -1 if the {offset} is not inside any loop.
110  int GetLoopOffsetFor(int offset) const;
111  // Get the loop info of the loop header at {header_offset}.
112  const LoopInfo& GetLoopInfoFor(int header_offset) const;
113  // Try to get the loop info of the loop header at {header_offset}, returning
114  // null if there isn't any.
115  const LoopInfo* TryGetLoopInfoFor(int header_offset) const;
116
117  const ZoneMap<int, LoopInfo>& GetLoopInfos() const { return header_to_info_; }
118
119  // Get the top-level resume jump targets.
120  const ZoneVector<ResumeJumpTarget>& resume_jump_targets() const {
121    return resume_jump_targets_;
122  }
123
124  // Gets the in-/out-liveness for the bytecode at {offset}.
125  const BytecodeLivenessState* GetInLivenessFor(int offset) const;
126  const BytecodeLivenessState* GetOutLivenessFor(int offset) const;
127
128  // In the case of OSR, the analysis also computes the (bytecode offset of the)
129  // OSR entry point from the {osr_bailout_id} that was given to the
130  // constructor.
131  int osr_entry_point() const {
132    CHECK_LE(0, osr_entry_point_);
133    return osr_entry_point_;
134  }
135  // Return the osr_bailout_id (for verification purposes).
136  BytecodeOffset osr_bailout_id() const { return osr_bailout_id_; }
137
138  // Return whether liveness analysis was performed (for verification purposes).
139  bool liveness_analyzed() const { return analyze_liveness_; }
140
141  // Return the number of bytecodes (i.e. the number of bytecode operations, as
142  // opposed to the number of bytes in the bytecode).
143  int bytecode_count() const { return bytecode_count_; }
144
145 private:
146  struct LoopStackEntry {
147    int header_offset;
148    LoopInfo* loop_info;
149  };
150
151  void Analyze();
152  void PushLoop(int loop_header, int loop_end);
153
154#if DEBUG
155  bool ResumeJumpTargetsAreValid();
156  bool ResumeJumpTargetLeavesResolveSuspendIds(
157      int parent_offset,
158      const ZoneVector<ResumeJumpTarget>& resume_jump_targets,
159      std::map<int, int>* unresolved_suspend_ids);
160
161  bool LivenessIsValid();
162#endif
163
164  Zone* zone() const { return zone_; }
165  Handle<BytecodeArray> bytecode_array() const { return bytecode_array_; }
166  BytecodeLivenessMap& liveness_map() {
167    DCHECK(analyze_liveness_);
168    return *liveness_map_;
169  }
170  const BytecodeLivenessMap& liveness_map() const {
171    DCHECK(analyze_liveness_);
172    return *liveness_map_;
173  }
174
175  std::ostream& PrintLivenessTo(std::ostream& os) const;
176
177  Handle<BytecodeArray> const bytecode_array_;
178  Zone* const zone_;
179  BytecodeOffset const osr_bailout_id_;
180  bool const analyze_liveness_;
181  ZoneStack<LoopStackEntry> loop_stack_;
182  ZoneVector<int> loop_end_index_queue_;
183  ZoneVector<ResumeJumpTarget> resume_jump_targets_;
184  ZoneMap<int, int> end_to_header_;
185  ZoneMap<int, LoopInfo> header_to_info_;
186  int osr_entry_point_;
187  base::Optional<BytecodeLivenessMap> liveness_map_;
188  int bytecode_count_;
189};
190
191}  // namespace compiler
192}  // namespace internal
193}  // namespace v8
194
195#endif  // V8_COMPILER_BYTECODE_ANALYSIS_H_
196