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/bit-vector.h"
10#include "src/compiler/bytecode-liveness-map.h"
11#include "src/handles.h"
12#include "src/interpreter/bytecode-register.h"
13#include "src/zone/zone-containers.h"
14
15namespace v8 {
16namespace internal {
17
18class BytecodeArray;
19
20namespace compiler {
21
22class V8_EXPORT_PRIVATE BytecodeLoopAssignments {
23 public:
24  BytecodeLoopAssignments(int parameter_count, int register_count, Zone* zone);
25
26  void Add(interpreter::Register r);
27  void AddPair(interpreter::Register r);
28  void AddTriple(interpreter::Register r);
29  void AddAll();
30  void Union(const BytecodeLoopAssignments& other);
31
32  bool ContainsParameter(int index) const;
33  bool ContainsLocal(int index) const;
34  bool ContainsAccumulator() const;
35
36  int parameter_count() const { return parameter_count_; }
37  int local_count() const { return bit_vector_->length() - parameter_count_; }
38
39 private:
40  int parameter_count_;
41  BitVector* bit_vector_;
42};
43
44struct V8_EXPORT_PRIVATE LoopInfo {
45 public:
46  LoopInfo(int parent_offset, int parameter_count, int register_count,
47           Zone* zone)
48      : parent_offset_(parent_offset),
49        assignments_(parameter_count, register_count, zone) {}
50
51  int parent_offset() const { return parent_offset_; }
52
53  BytecodeLoopAssignments& assignments() { return assignments_; }
54  const BytecodeLoopAssignments& assignments() const { return assignments_; }
55
56 private:
57  // The offset to the parent loop, or -1 if there is no parent.
58  int parent_offset_;
59  BytecodeLoopAssignments assignments_;
60};
61
62class V8_EXPORT_PRIVATE BytecodeAnalysis BASE_EMBEDDED {
63 public:
64  BytecodeAnalysis(Handle<BytecodeArray> bytecode_array, Zone* zone,
65                   bool do_liveness_analysis);
66
67  // Analyze the bytecodes to find the loop ranges, loop nesting, loop
68  // assignments and liveness, under the assumption that there is an OSR bailout
69  // at {osr_bailout_id}.
70  //
71  // No other methods in this class return valid information until this has been
72  // called.
73  void Analyze(BailoutId osr_bailout_id);
74
75  // Return true if the given offset is a loop header
76  bool IsLoopHeader(int offset) const;
77  // Get the loop header offset of the containing loop for arbitrary
78  // {offset}, or -1 if the {offset} is not inside any loop.
79  int GetLoopOffsetFor(int offset) const;
80  // Get the loop info of the loop header at {header_offset}.
81  const LoopInfo& GetLoopInfoFor(int header_offset) const;
82
83  // Gets the in-liveness for the bytecode at {offset}.
84  const BytecodeLivenessState* GetInLivenessFor(int offset) const;
85
86  // Gets the out-liveness for the bytecode at {offset}.
87  const BytecodeLivenessState* GetOutLivenessFor(int offset) const;
88
89  std::ostream& PrintLivenessTo(std::ostream& os) const;
90
91 private:
92  struct LoopStackEntry {
93    int header_offset;
94    LoopInfo* loop_info;
95  };
96
97  void PushLoop(int loop_header, int loop_end);
98
99#if DEBUG
100  bool LivenessIsValid();
101#endif
102
103  Zone* zone() const { return zone_; }
104  Handle<BytecodeArray> bytecode_array() const { return bytecode_array_; }
105
106 private:
107  Handle<BytecodeArray> bytecode_array_;
108  bool do_liveness_analysis_;
109  Zone* zone_;
110
111  ZoneStack<LoopStackEntry> loop_stack_;
112  ZoneVector<int> loop_end_index_queue_;
113
114  ZoneMap<int, int> end_to_header_;
115  ZoneMap<int, LoopInfo> header_to_info_;
116
117  BytecodeLivenessMap liveness_map_;
118
119  DISALLOW_COPY_AND_ASSIGN(BytecodeAnalysis);
120};
121
122}  // namespace compiler
123}  // namespace internal
124}  // namespace v8
125
126#endif  // V8_COMPILER_BYTECODE_ANALYSIS_H_
127