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_LIVENESS_ANAYZER_H_
6#define V8_COMPILER_LIVENESS_ANAYZER_H_
7
8#include "src/bit-vector.h"
9#include "src/compiler/node.h"
10#include "src/globals.h"
11#include "src/zone/zone-containers.h"
12
13namespace v8 {
14namespace internal {
15namespace compiler {
16
17class LivenessAnalyzerBlock;
18class Node;
19class StateValuesCache;
20
21class NonLiveFrameStateSlotReplacer {
22 public:
23  void ClearNonLiveFrameStateSlots(Node* frame_state, BitVector* liveness);
24  NonLiveFrameStateSlotReplacer(StateValuesCache* state_values_cache,
25                                Node* replacement, size_t local_count,
26                                bool has_accumulator, Zone* local_zone)
27      : replacement_node_(replacement),
28        state_values_cache_(state_values_cache),
29        local_zone_(local_zone),
30        permanently_live_(
31            static_cast<int>(local_count) + (has_accumulator ? 1 : 0),
32            local_zone),
33        inputs_buffer_(local_zone),
34        has_accumulator_(has_accumulator) {}
35
36  // TODO(leszeks): Not used by bytecode, remove once AST graph builder is gone.
37  void MarkPermanentlyLive(int var) { permanently_live_.Add(var); }
38
39 private:
40  Node* ClearNonLiveStateValues(Node* frame_state, BitVector* liveness);
41
42  StateValuesCache* state_values_cache() { return state_values_cache_; }
43  Zone* local_zone() { return local_zone_; }
44
45  // Node that replaces dead values.
46  Node* replacement_node_;
47  // Reference to state values cache so that we can create state values
48  // nodes.
49  StateValuesCache* state_values_cache_;
50
51  Zone* local_zone_;
52  BitVector permanently_live_;
53  NodeVector inputs_buffer_;
54
55  bool has_accumulator_;
56};
57
58class V8_EXPORT_PRIVATE LivenessAnalyzer {
59 public:
60  LivenessAnalyzer(size_t local_count, bool has_accumulator, Zone* zone);
61
62  LivenessAnalyzerBlock* NewBlock();
63  LivenessAnalyzerBlock* NewBlock(LivenessAnalyzerBlock* predecessor);
64
65  void Run(NonLiveFrameStateSlotReplacer* relaxer);
66
67  Zone* zone() { return zone_; }
68
69  void Print(std::ostream& os);
70
71  size_t local_count() { return local_count_; }
72
73 private:
74  void Queue(LivenessAnalyzerBlock* block);
75
76  Zone* zone_;
77  ZoneDeque<LivenessAnalyzerBlock*> blocks_;
78  size_t local_count_;
79
80  // TODO(leszeks): Always true for bytecode, remove once AST graph builder is
81  // gone.
82  bool has_accumulator_;
83
84  ZoneQueue<LivenessAnalyzerBlock*> queue_;
85};
86
87
88class LivenessAnalyzerBlock {
89 public:
90  friend class LivenessAnalyzer;
91
92  void Lookup(int var) { entries_.push_back(Entry(Entry::kLookup, var)); }
93  void Bind(int var) { entries_.push_back(Entry(Entry::kBind, var)); }
94  void LookupAccumulator() {
95    DCHECK(has_accumulator_);
96    // The last entry is the accumulator entry.
97    entries_.push_back(Entry(Entry::kLookup, live_.length() - 1));
98  }
99  void BindAccumulator() {
100    DCHECK(has_accumulator_);
101    // The last entry is the accumulator entry.
102    entries_.push_back(Entry(Entry::kBind, live_.length() - 1));
103  }
104
105  void Checkpoint(Node* node) { entries_.push_back(Entry(node)); }
106  void AddPredecessor(LivenessAnalyzerBlock* b) { predecessors_.push_back(b); }
107  LivenessAnalyzerBlock* GetPredecessor() {
108    DCHECK(predecessors_.size() == 1);
109    return predecessors_[0];
110  }
111
112 private:
113  class Entry {
114   public:
115    enum Kind { kBind, kLookup, kCheckpoint };
116
117    Kind kind() const { return kind_; }
118    Node* node() const {
119      DCHECK(kind() == kCheckpoint);
120      return node_;
121    }
122    int var() const {
123      DCHECK(kind() != kCheckpoint);
124      return var_;
125    }
126
127    explicit Entry(Node* node) : kind_(kCheckpoint), var_(-1), node_(node) {}
128    Entry(Kind kind, int var) : kind_(kind), var_(var), node_(nullptr) {
129      DCHECK(kind != kCheckpoint);
130    }
131
132   private:
133    Kind kind_;
134    int var_;
135    Node* node_;
136  };
137
138  LivenessAnalyzerBlock(size_t id, size_t local_count, bool has_accumulator,
139                        Zone* zone);
140  void Process(BitVector* result, NonLiveFrameStateSlotReplacer* relaxer);
141  bool UpdateLive(BitVector* working_area);
142
143  void SetQueued() { queued_ = true; }
144  bool IsQueued() { return queued_; }
145
146  ZoneDeque<LivenessAnalyzerBlock*>::const_iterator pred_begin() {
147    return predecessors_.begin();
148  }
149  ZoneDeque<LivenessAnalyzerBlock*>::const_iterator pred_end() {
150    return predecessors_.end();
151  }
152
153  size_t id() { return id_; }
154  void Print(std::ostream& os);
155
156  ZoneDeque<Entry> entries_;
157  ZoneDeque<LivenessAnalyzerBlock*> predecessors_;
158
159  BitVector live_;
160  bool queued_;
161  bool has_accumulator_;
162
163  size_t id_;
164};
165
166
167}  // namespace compiler
168}  // namespace internal
169}  // namespace v8
170
171#endif  // V8_COMPILER_AST_GRAPH_BUILDER_H_
172