Line data Source code
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/bit-vector.h"
10 : #include "src/compiler/bytecode-liveness-map.h"
11 : #include "src/handles.h"
12 : #include "src/interpreter/bytecode-register.h"
13 : #include "src/utils.h"
14 : #include "src/zone/zone-containers.h"
15 :
16 : namespace v8 {
17 : namespace internal {
18 :
19 : class BytecodeArray;
20 :
21 : namespace compiler {
22 :
23 : class 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 parameter_count_;
39 : BitVector* bit_vector_;
40 : };
41 :
42 : // Jump targets for resuming a suspended generator.
43 : class 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 :
68 285622 : struct 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 57125 : resume_jump_targets_(zone) {}
75 :
76 : int parent_offset() const { return parent_offset_; }
77 :
78 : const ZoneVector<ResumeJumpTarget>& resume_jump_targets() const {
79 473 : return resume_jump_targets_;
80 : }
81 : void AddResumeTarget(const ResumeJumpTarget& target) {
82 567 : resume_jump_targets_.push_back(target);
83 : }
84 :
85 1834891 : BytecodeLoopAssignments& assignments() { return assignments_; }
86 219811 : 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 1059513 : class V8_EXPORT_PRIVATE BytecodeAnalysis {
96 : public:
97 : BytecodeAnalysis(Handle<BytecodeArray> bytecode_array, Zone* zone,
98 : bool do_liveness_analysis);
99 :
100 : // Analyze the bytecodes to find the loop ranges, loop nesting, loop
101 : // assignments and liveness, under the assumption that there is an OSR bailout
102 : // at {osr_bailout_id}.
103 : //
104 : // No other methods in this class return valid information until this has been
105 : // called.
106 : void Analyze(BailoutId osr_bailout_id);
107 :
108 : // Return true if the given offset is a loop header
109 : bool IsLoopHeader(int offset) const;
110 : // Get the loop header offset of the containing loop for arbitrary
111 : // {offset}, or -1 if the {offset} is not inside any loop.
112 : int GetLoopOffsetFor(int offset) const;
113 : // Get the loop info of the loop header at {header_offset}.
114 : const LoopInfo& GetLoopInfoFor(int header_offset) const;
115 :
116 : // Get the top-level resume jump targets.
117 : const ZoneVector<ResumeJumpTarget>& resume_jump_targets() const {
118 2189 : return resume_jump_targets_;
119 : }
120 :
121 : // True if the current analysis has an OSR entry point.
122 : bool HasOsrEntryPoint() const { return osr_entry_point_ != -1; }
123 :
124 : int osr_entry_point() const { return osr_entry_point_; }
125 :
126 : // Gets the in-liveness for the bytecode at {offset}.
127 : const BytecodeLivenessState* GetInLivenessFor(int offset) const;
128 :
129 : // Gets the out-liveness for the bytecode at {offset}.
130 : const BytecodeLivenessState* GetOutLivenessFor(int offset) const;
131 :
132 : std::ostream& PrintLivenessTo(std::ostream& os) const;
133 :
134 : private:
135 : struct LoopStackEntry {
136 : int header_offset;
137 : LoopInfo* loop_info;
138 : };
139 :
140 : void PushLoop(int loop_header, int loop_end);
141 :
142 : #if DEBUG
143 : bool ResumeJumpTargetsAreValid();
144 : bool ResumeJumpTargetLeavesResolveSuspendIds(
145 : int parent_offset,
146 : const ZoneVector<ResumeJumpTarget>& resume_jump_targets,
147 : std::map<int, int>* unresolved_suspend_ids);
148 :
149 : bool LivenessIsValid();
150 : #endif
151 :
152 : Zone* zone() const { return zone_; }
153 : Handle<BytecodeArray> bytecode_array() const { return bytecode_array_; }
154 :
155 : private:
156 : Handle<BytecodeArray> bytecode_array_;
157 : bool do_liveness_analysis_;
158 : Zone* zone_;
159 :
160 : ZoneStack<LoopStackEntry> loop_stack_;
161 : ZoneVector<int> loop_end_index_queue_;
162 : ZoneVector<ResumeJumpTarget> resume_jump_targets_;
163 :
164 : ZoneMap<int, int> end_to_header_;
165 : ZoneMap<int, LoopInfo> header_to_info_;
166 : int osr_entry_point_;
167 :
168 : BytecodeLivenessMap liveness_map_;
169 :
170 : DISALLOW_COPY_AND_ASSIGN(BytecodeAnalysis);
171 : };
172 :
173 : } // namespace compiler
174 : } // namespace internal
175 : } // namespace v8
176 :
177 : #endif // V8_COMPILER_BYTECODE_ANALYSIS_H_
|