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 #include "src/compiler/bytecode-loop-analysis.h" 6 7 #include "src/compiler/bytecode-branch-analysis.h" 8 #include "src/interpreter/bytecode-array-iterator.h" 9 #include "src/objects-inl.h" 10 11 namespace v8 { 12 namespace internal { 13 namespace compiler { 14 15 BytecodeLoopAnalysis::BytecodeLoopAnalysis( 16 Handle<BytecodeArray> bytecode_array, 17 const BytecodeBranchAnalysis* branch_analysis, Zone* zone) 18 : bytecode_array_(bytecode_array), 19 branch_analysis_(branch_analysis), 20 zone_(zone), 21 current_loop_offset_(-1), 22 found_current_backedge_(false), 23 backedge_to_header_(zone), 24 loop_header_to_parent_(zone) {} 25 26 void BytecodeLoopAnalysis::Analyze() { 27 current_loop_offset_ = -1; 28 found_current_backedge_ = false; 29 interpreter::BytecodeArrayIterator iterator(bytecode_array()); 30 while (!iterator.done()) { 31 interpreter::Bytecode bytecode = iterator.current_bytecode(); 32 int current_offset = iterator.current_offset(); 33 if (branch_analysis_->backward_branches_target(current_offset)) { 34 AddLoopEntry(current_offset); 35 } else if (interpreter::Bytecodes::IsJump(bytecode)) { 36 AddBranch(current_offset, iterator.GetJumpTargetOffset()); 37 } 38 iterator.Advance(); 39 } 40 } 41 42 void BytecodeLoopAnalysis::AddLoopEntry(int entry_offset) { 43 if (found_current_backedge_) { 44 // We assume that all backedges of a loop must occur together and before 45 // another loop entry or an outer loop backedge. 46 // This is guaranteed by the invariants from AddBranch, such that every 47 // backedge must either go to the current loop or be the first of the 48 // backedges to the parent loop. 49 // Thus here, the current loop actually ended before and we have a loop 50 // with the same parent. 51 current_loop_offset_ = loop_header_to_parent_[current_loop_offset_]; 52 found_current_backedge_ = false; 53 } 54 loop_header_to_parent_[entry_offset] = current_loop_offset_; 55 current_loop_offset_ = entry_offset; 56 } 57 58 void BytecodeLoopAnalysis::AddBranch(int origin_offset, int target_offset) { 59 // If this is a backedge, record it. 60 if (target_offset < origin_offset) { 61 backedge_to_header_[origin_offset] = target_offset; 62 // Check whether this is actually a backedge of the outer loop and we have 63 // already finished the current loop. 64 if (target_offset < current_loop_offset_) { 65 DCHECK(found_current_backedge_); 66 int parent_offset = loop_header_to_parent_[current_loop_offset_]; 67 DCHECK_EQ(target_offset, parent_offset); 68 current_loop_offset_ = parent_offset; 69 } else { 70 DCHECK_EQ(target_offset, current_loop_offset_); 71 found_current_backedge_ = true; 72 } 73 } 74 } 75 76 int BytecodeLoopAnalysis::GetLoopOffsetFor(int offset) const { 77 auto next_backedge = backedge_to_header_.lower_bound(offset); 78 // If there is no next backedge => offset is not in a loop. 79 if (next_backedge == backedge_to_header_.end()) { 80 return -1; 81 } 82 // If the header preceeds the offset, it is the backedge of the containing 83 // loop. 84 if (next_backedge->second <= offset) { 85 return next_backedge->second; 86 } 87 // Otherwise there is a nested loop after this offset. We just return the 88 // parent of the next nested loop. 89 return loop_header_to_parent_.upper_bound(offset)->second; 90 } 91 92 int BytecodeLoopAnalysis::GetParentLoopFor(int header_offset) const { 93 auto parent = loop_header_to_parent_.find(header_offset); 94 DCHECK(parent != loop_header_to_parent_.end()); 95 return parent->second; 96 } 97 98 } // namespace compiler 99 } // namespace internal 100 } // namespace v8 101
