1 // Copyright 2015 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-branch-analysis.h"
6
7 #include "src/interpreter/bytecode-array-iterator.h"
8 #include "src/objects-inl.h"
9
10 namespace v8 {
11 namespace internal {
12 namespace compiler {
13
14 // The class contains all of the sites that contain
15 // branches to a particular target (bytecode offset).
16 class BytecodeBranchInfo final : public ZoneObject {
17 public:
BytecodeBranchInfo(Zone * zone)18 explicit BytecodeBranchInfo(Zone* zone)
19 : back_edge_offsets_(zone), fore_edge_offsets_(zone) {}
20
21 void AddBranch(int source_offset, int target_offset);
22
23 // The offsets of bytecodes that refer to this bytecode as
24 // a back-edge predecessor.
back_edge_offsets()25 const ZoneVector<int>* back_edge_offsets() { return &back_edge_offsets_; }
26
27 // The offsets of bytecodes that refer to this bytecode as
28 // a forwards-edge predecessor.
fore_edge_offsets()29 const ZoneVector<int>* fore_edge_offsets() { return &fore_edge_offsets_; }
30
31 private:
32 ZoneVector<int> back_edge_offsets_;
33 ZoneVector<int> fore_edge_offsets_;
34
35 DISALLOW_COPY_AND_ASSIGN(BytecodeBranchInfo);
36 };
37
38
AddBranch(int source_offset,int target_offset)39 void BytecodeBranchInfo::AddBranch(int source_offset, int target_offset) {
40 if (source_offset < target_offset) {
41 fore_edge_offsets_.push_back(source_offset);
42 } else {
43 back_edge_offsets_.push_back(source_offset);
44 }
45 }
46
47
BytecodeBranchAnalysis(Handle<BytecodeArray> bytecode_array,Zone * zone)48 BytecodeBranchAnalysis::BytecodeBranchAnalysis(
49 Handle<BytecodeArray> bytecode_array, Zone* zone)
50 : branch_infos_(zone),
51 bytecode_array_(bytecode_array),
52 reachable_(bytecode_array->length(), zone),
53 zone_(zone) {}
54
55
Analyze()56 void BytecodeBranchAnalysis::Analyze() {
57 interpreter::BytecodeArrayIterator iterator(bytecode_array());
58 bool reachable = true;
59 while (!iterator.done()) {
60 interpreter::Bytecode bytecode = iterator.current_bytecode();
61 int current_offset = iterator.current_offset();
62 // All bytecode basic blocks are generated to be forward reachable
63 // and may also be backward reachable. Hence if there's a forward
64 // branch targetting here the code becomes reachable.
65 reachable = reachable || forward_branches_target(current_offset);
66 if (reachable) {
67 reachable_.Add(current_offset);
68 if (interpreter::Bytecodes::IsConditionalJump(bytecode)) {
69 // Only the branch is recorded, the forward path falls through
70 // and is handled as normal bytecode data flow.
71 AddBranch(current_offset, iterator.GetJumpTargetOffset());
72 } else if (interpreter::Bytecodes::IsJump(bytecode)) {
73 // Unless the branch targets the next bytecode it's not
74 // reachable. If it targets the next bytecode the check at the
75 // start of the loop will set the reachable flag.
76 AddBranch(current_offset, iterator.GetJumpTargetOffset());
77 reachable = false;
78 } else if (interpreter::Bytecodes::IsJumpOrReturn(bytecode)) {
79 DCHECK_EQ(bytecode, interpreter::Bytecode::kReturn);
80 reachable = false;
81 }
82 }
83 iterator.Advance();
84 }
85 }
86
87
BackwardBranchesTargetting(int offset) const88 const ZoneVector<int>* BytecodeBranchAnalysis::BackwardBranchesTargetting(
89 int offset) const {
90 auto iterator = branch_infos_.find(offset);
91 if (branch_infos_.end() != iterator) {
92 return iterator->second->back_edge_offsets();
93 } else {
94 return nullptr;
95 }
96 }
97
98
ForwardBranchesTargetting(int offset) const99 const ZoneVector<int>* BytecodeBranchAnalysis::ForwardBranchesTargetting(
100 int offset) const {
101 auto iterator = branch_infos_.find(offset);
102 if (branch_infos_.end() != iterator) {
103 return iterator->second->fore_edge_offsets();
104 } else {
105 return nullptr;
106 }
107 }
108
109
AddBranch(int source_offset,int target_offset)110 void BytecodeBranchAnalysis::AddBranch(int source_offset, int target_offset) {
111 BytecodeBranchInfo* branch_info = nullptr;
112 auto iterator = branch_infos_.find(target_offset);
113 if (branch_infos_.end() == iterator) {
114 branch_info = new (zone()) BytecodeBranchInfo(zone());
115 branch_infos_.insert(std::make_pair(target_offset, branch_info));
116 } else {
117 branch_info = iterator->second;
118 }
119 branch_info->AddBranch(source_offset, target_offset);
120 }
121
122
123 } // namespace compiler
124 } // namespace internal
125 } // namespace v8
126