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
BytecodeLoopAnalysis(Handle<BytecodeArray> bytecode_array,const BytecodeBranchAnalysis * branch_analysis,Zone * zone)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
Analyze()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
AddLoopEntry(int entry_offset)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
AddBranch(int origin_offset,int target_offset)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
GetLoopOffsetFor(int offset) const76 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
GetParentLoopFor(int header_offset) const92 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