Line data Source code
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 :
13 : namespace v8 {
14 : namespace internal {
15 : namespace compiler {
16 :
17 : class LivenessAnalyzerBlock;
18 : class Node;
19 : class StateValuesCache;
20 :
21 : class 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 876 : has_accumulator_(has_accumulator) {}
35 :
36 : // TODO(leszeks): Not used by bytecode, remove once AST graph builder is gone.
37 4 : 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 :
58 : class 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 :
88 : class LivenessAnalyzerBlock {
89 : public:
90 : friend class LivenessAnalyzer;
91 :
92 248 : void Lookup(int var) { entries_.push_back(Entry(Entry::kLookup, var)); }
93 308 : 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 3232 : void Checkpoint(Node* node) { entries_.push_back(Entry(node)); }
106 597 : void AddPredecessor(LivenessAnalyzerBlock* b) { predecessors_.push_back(b); }
107 0 : LivenessAnalyzerBlock* GetPredecessor() {
108 : DCHECK(predecessors_.size() == 1);
109 0 : 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 1616 : explicit Entry(Node* node) : kind_(kCheckpoint), var_(-1), node_(node) {}
128 278 : 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 480 : 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_
|