bytecode-analysis.h 5.49 KB
Newer Older
1 2 3 4 5 6 7
// Copyright 2016 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_COMPILER_BYTECODE_ANALYSIS_H_
#define V8_COMPILER_BYTECODE_ANALYSIS_H_

8 9 10
#include "src/base/hashmap.h"
#include "src/bit-vector.h"
#include "src/compiler/bytecode-liveness-map.h"
11
#include "src/handles.h"
12
#include "src/interpreter/bytecode-register.h"
13
#include "src/utils.h"
14 15 16 17 18 19 20 21 22
#include "src/zone/zone-containers.h"

namespace v8 {
namespace internal {

class BytecodeArray;

namespace compiler {

23 24 25 26 27
class V8_EXPORT_PRIVATE BytecodeLoopAssignments {
 public:
  BytecodeLoopAssignments(int parameter_count, int register_count, Zone* zone);

  void Add(interpreter::Register r);
28
  void AddList(interpreter::Register r, uint32_t count);
29 30 31 32 33 34 35 36 37
  void Union(const BytecodeLoopAssignments& other);

  bool ContainsParameter(int index) const;
  bool ContainsLocal(int index) const;

  int parameter_count() const { return parameter_count_; }
  int local_count() const { return bit_vector_->length() - parameter_count_; }

 private:
38 39
  int const parameter_count_;
  BitVector* const bit_vector_;
40 41
};

42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
// Jump targets for resuming a suspended generator.
class V8_EXPORT_PRIVATE ResumeJumpTarget {
 public:
  // Create a resume jump target representing an actual resume.
  static ResumeJumpTarget Leaf(int suspend_id, int target_offset);

  // Create a resume jump target at a loop header, which will have another
  // resume jump after the loop header is crossed.
  static ResumeJumpTarget AtLoopHeader(int loop_header_offset,
                                       const ResumeJumpTarget& next);

  int suspend_id() const { return suspend_id_; }
  int target_offset() const { return target_offset_; }
  bool is_leaf() const { return target_offset_ == final_target_offset_; }

 private:
  // The suspend id of the resume.
  int suspend_id_;
  // The target offset of this resume jump.
  int target_offset_;
  // The final offset of this resume, which may be across multiple jumps.
  int final_target_offset_;

  ResumeJumpTarget(int suspend_id, int target_offset, int final_target_offset);
};

68 69 70 71 72
struct V8_EXPORT_PRIVATE LoopInfo {
 public:
  LoopInfo(int parent_offset, int parameter_count, int register_count,
           Zone* zone)
      : parent_offset_(parent_offset),
73 74
        assignments_(parameter_count, register_count, zone),
        resume_jump_targets_(zone) {}
75 76 77

  int parent_offset() const { return parent_offset_; }

78 79 80 81 82 83 84
  const ZoneVector<ResumeJumpTarget>& resume_jump_targets() const {
    return resume_jump_targets_;
  }
  void AddResumeTarget(const ResumeJumpTarget& target) {
    resume_jump_targets_.push_back(target);
  }

85 86 87 88 89 90 91
  BytecodeLoopAssignments& assignments() { return assignments_; }
  const BytecodeLoopAssignments& assignments() const { return assignments_; }

 private:
  // The offset to the parent loop, or -1 if there is no parent.
  int parent_offset_;
  BytecodeLoopAssignments assignments_;
92
  ZoneVector<ResumeJumpTarget> resume_jump_targets_;
93 94
};

95
class V8_EXPORT_PRIVATE BytecodeAnalysis {
96
 public:
97 98
  BytecodeAnalysis(Handle<BytecodeArray> bytecode_array, Zone* zone,
                   bool do_liveness_analysis);
99

100 101 102 103 104 105 106
  // Analyze the bytecodes to find the loop ranges, loop nesting, loop
  // assignments and liveness, under the assumption that there is an OSR bailout
  // at {osr_bailout_id}.
  //
  // No other methods in this class return valid information until this has been
  // called.
  void Analyze(BailoutId osr_bailout_id);
107 108 109 110 111 112

  // Return true if the given offset is a loop header
  bool IsLoopHeader(int offset) const;
  // Get the loop header offset of the containing loop for arbitrary
  // {offset}, or -1 if the {offset} is not inside any loop.
  int GetLoopOffsetFor(int offset) const;
113 114
  // Get the loop info of the loop header at {header_offset}.
  const LoopInfo& GetLoopInfoFor(int header_offset) const;
115

116 117 118 119 120
  // Get the top-level resume jump targets.
  const ZoneVector<ResumeJumpTarget>& resume_jump_targets() const {
    return resume_jump_targets_;
  }

121
  // True if the current analysis has an OSR entry point.
122
  bool HasOsrEntryPoint() const { return osr_entry_point_ != -1; }
123

124
  int osr_entry_point() const { return osr_entry_point_; }
125

126 127 128 129 130
  // Gets the in-liveness for the bytecode at {offset}.
  const BytecodeLivenessState* GetInLivenessFor(int offset) const;

  // Gets the out-liveness for the bytecode at {offset}.
  const BytecodeLivenessState* GetOutLivenessFor(int offset) const;
131

132
 private:
133 134 135 136 137
  struct LoopStackEntry {
    int header_offset;
    LoopInfo* loop_info;
  };

138 139
  void PushLoop(int loop_header, int loop_end);

140
#if DEBUG
141 142 143 144 145 146
  bool ResumeJumpTargetsAreValid();
  bool ResumeJumpTargetLeavesResolveSuspendIds(
      int parent_offset,
      const ZoneVector<ResumeJumpTarget>& resume_jump_targets,
      std::map<int, int>* unresolved_suspend_ids);

147 148 149
  bool LivenessIsValid();
#endif

150 151 152
  Zone* zone() const { return zone_; }
  Handle<BytecodeArray> bytecode_array() const { return bytecode_array_; }

153 154 155 156 157
  std::ostream& PrintLivenessTo(std::ostream& os) const;

  Handle<BytecodeArray> const bytecode_array_;
  bool const do_liveness_analysis_;
  Zone* const zone_;
158

159
  ZoneStack<LoopStackEntry> loop_stack_;
160
  ZoneVector<int> loop_end_index_queue_;
161
  ZoneVector<ResumeJumpTarget> resume_jump_targets_;
162 163

  ZoneMap<int, int> end_to_header_;
164
  ZoneMap<int, LoopInfo> header_to_info_;
165
  int osr_entry_point_;
166

167 168
  BytecodeLivenessMap liveness_map_;

169 170 171 172 173 174 175 176
  DISALLOW_COPY_AND_ASSIGN(BytecodeAnalysis);
};

}  // namespace compiler
}  // namespace internal
}  // namespace v8

#endif  // V8_COMPILER_BYTECODE_ANALYSIS_H_