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 #ifndef V8_COMPILER_BYTECODE_BRANCH_ANALYSIS_H_
6 #define V8_COMPILER_BYTECODE_BRANCH_ANALYSIS_H_
7 
8 #include "src/bit-vector.h"
9 #include "src/handles.h"
10 #include "src/zone-containers.h"
11 
12 namespace v8 {
13 namespace internal {
14 
15 class BytecodeArray;
16 
17 namespace compiler {
18 
19 class BytecodeBranchInfo;
20 
21 // A class for identifying the branch targets and their branch sites
22 // within a bytecode array and also identifying which bytecodes are
23 // reachable. This information can be used to construct the local
24 // control flow logic for high-level IR graphs built from bytecode.
25 //
26 // NB This class relies on the only backwards branches in bytecode
27 // being jumps back to loop headers.
28 class BytecodeBranchAnalysis BASE_EMBEDDED {
29  public:
30   BytecodeBranchAnalysis(Handle<BytecodeArray> bytecode_array, Zone* zone);
31 
32   // Analyze the bytecodes to find the branch sites and their
33   // targets. No other methods in this class return valid information
34   // until this has been called.
35   void Analyze();
36 
37   // Offsets of bytecodes having a backward branch to the bytecode at |offset|.
38   const ZoneVector<int>* BackwardBranchesTargetting(int offset) const;
39 
40   // Offsets of bytecodes having a forward branch to the bytecode at |offset|.
41   const ZoneVector<int>* ForwardBranchesTargetting(int offset) const;
42 
43   // Returns true if the bytecode at |offset| is reachable.
is_reachable(int offset)44   bool is_reachable(int offset) const { return reachable_.Contains(offset); }
45 
46   // Returns true if there are any forward branches to the bytecode at
47   // |offset|.
forward_branches_target(int offset)48   bool forward_branches_target(int offset) const {
49     const ZoneVector<int>* sites = ForwardBranchesTargetting(offset);
50     return sites != nullptr && sites->size() > 0;
51   }
52 
53   // Returns true if there are any backward branches to the bytecode
54   // at |offset|.
backward_branches_target(int offset)55   bool backward_branches_target(int offset) const {
56     const ZoneVector<int>* sites = BackwardBranchesTargetting(offset);
57     return sites != nullptr && sites->size() > 0;
58   }
59 
60  private:
61   void AddBranch(int origin_offset, int target_offset);
62 
zone()63   Zone* zone() const { return zone_; }
bytecode_array()64   Handle<BytecodeArray> bytecode_array() const { return bytecode_array_; }
65 
66   ZoneMap<int, BytecodeBranchInfo*> branch_infos_;
67   Handle<BytecodeArray> bytecode_array_;
68   BitVector reachable_;
69   Zone* zone_;
70 
71   DISALLOW_COPY_AND_ASSIGN(BytecodeBranchAnalysis);
72 };
73 
74 
75 }  // namespace compiler
76 }  // namespace internal
77 }  // namespace v8
78 
79 #endif  // V8_COMPILER_BYTECODE_BRANCH_ANALYSIS_H_
80