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 
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 
parameter_count()34   int parameter_count() const { return parameter_count_; }
local_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.
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 
suspend_id()53   int suspend_id() const { return suspend_id_; }
target_offset()54   int target_offset() const { return target_offset_; }
is_leaf()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 struct V8_EXPORT_PRIVATE LoopInfo {
69  public:
LoopInfoLoopInfo70   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 
parent_offsetLoopInfo76   int parent_offset() const { return parent_offset_; }
77 
resume_jump_targetsLoopInfo78   const ZoneVector<ResumeJumpTarget>& resume_jump_targets() const {
79     return resume_jump_targets_;
80   }
AddResumeTargetLoopInfo81   void AddResumeTarget(const ResumeJumpTarget& target) {
82     resume_jump_targets_.push_back(target);
83   }
84 
assignmentsLoopInfo85   BytecodeLoopAssignments& assignments() { return assignments_; }
assignmentsLoopInfo86   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).
99 class V8_EXPORT_PRIVATE BytecodeAnalysis : public ZoneObject {
100  public:
101   BytecodeAnalysis(Handle<BytecodeArray> bytecode_array, Zone* zone,
102                    BailoutId osr_bailout_id, bool analyze_liveness);
103 
104   // Return true if the given offset is a loop header
105   bool IsLoopHeader(int offset) const;
106   // Get the loop header offset of the containing loop for arbitrary
107   // {offset}, or -1 if the {offset} is not inside any loop.
108   int GetLoopOffsetFor(int offset) const;
109   // Get the loop info of the loop header at {header_offset}.
110   const LoopInfo& GetLoopInfoFor(int header_offset) const;
111 
112   // Get the top-level resume jump targets.
resume_jump_targets()113   const ZoneVector<ResumeJumpTarget>& resume_jump_targets() const {
114     return resume_jump_targets_;
115   }
116 
117   // Gets the in-/out-liveness for the bytecode at {offset}.
118   const BytecodeLivenessState* GetInLivenessFor(int offset) const;
119   const BytecodeLivenessState* GetOutLivenessFor(int offset) const;
120 
121   // In the case of OSR, the analysis also computes the (bytecode offset of the)
122   // OSR entry point from the {osr_bailout_id} that was given to the
123   // constructor.
osr_entry_point()124   int osr_entry_point() const {
125     CHECK_LE(0, osr_entry_point_);
126     return osr_entry_point_;
127   }
128   // Return the osr_bailout_id (for verification purposes).
osr_bailout_id()129   BailoutId osr_bailout_id() const { return osr_bailout_id_; }
130 
131   // Return whether liveness analysis was performed (for verification purposes).
liveness_analyzed()132   bool liveness_analyzed() const { return analyze_liveness_; }
133 
134  private:
135   struct LoopStackEntry {
136     int header_offset;
137     LoopInfo* loop_info;
138   };
139 
140   void Analyze();
141   void PushLoop(int loop_header, int loop_end);
142 
143 #if DEBUG
144   bool ResumeJumpTargetsAreValid();
145   bool ResumeJumpTargetLeavesResolveSuspendIds(
146       int parent_offset,
147       const ZoneVector<ResumeJumpTarget>& resume_jump_targets,
148       std::map<int, int>* unresolved_suspend_ids);
149 
150   bool LivenessIsValid();
151 #endif
152 
zone()153   Zone* zone() const { return zone_; }
bytecode_array()154   Handle<BytecodeArray> bytecode_array() const { return bytecode_array_; }
155 
156   std::ostream& PrintLivenessTo(std::ostream& os) const;
157 
158   Handle<BytecodeArray> const bytecode_array_;
159   Zone* const zone_;
160   BailoutId const osr_bailout_id_;
161   bool const analyze_liveness_;
162   ZoneStack<LoopStackEntry> loop_stack_;
163   ZoneVector<int> loop_end_index_queue_;
164   ZoneVector<ResumeJumpTarget> resume_jump_targets_;
165   ZoneMap<int, int> end_to_header_;
166   ZoneMap<int, LoopInfo> header_to_info_;
167   int osr_entry_point_;
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_
178