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 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 GetLoopInfos()117 const ZoneMap<int, LoopInfo>& GetLoopInfos() const { return header_to_info_; } 118 119 // Get the top-level resume jump targets. 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. osr_entry_point()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). osr_bailout_id()136 BytecodeOffset osr_bailout_id() const { return osr_bailout_id_; } 137 138 // Return whether liveness analysis was performed (for verification purposes). liveness_analyzed()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). bytecode_count()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 zone()164 Zone* zone() const { return zone_; } bytecode_array()165 Handle<BytecodeArray> bytecode_array() const { return bytecode_array_; } liveness_map()166 BytecodeLivenessMap& liveness_map() { 167 DCHECK(analyze_liveness_); 168 return *liveness_map_; 169 } liveness_map()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