1 // Copyright 2014 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 #include "src/base/adapters.h"
6 #include "src/compiler/js-graph.h"
7 #include "src/compiler/liveness-analyzer.h"
8 #include "src/compiler/node.h"
9 #include "src/compiler/node-matchers.h"
10 #include "src/compiler/state-values-utils.h"
11
12 namespace v8 {
13 namespace internal {
14 namespace compiler {
15
LivenessAnalyzer(size_t local_count,bool has_accumulator,Zone * zone)16 LivenessAnalyzer::LivenessAnalyzer(size_t local_count, bool has_accumulator,
17 Zone* zone)
18 : zone_(zone),
19 blocks_(zone),
20 local_count_(local_count),
21 has_accumulator_(has_accumulator),
22 queue_(zone) {}
23
Print(std::ostream & os)24 void LivenessAnalyzer::Print(std::ostream& os) {
25 for (auto block : blocks_) {
26 block->Print(os);
27 os << std::endl;
28 }
29 }
30
31
NewBlock()32 LivenessAnalyzerBlock* LivenessAnalyzer::NewBlock() {
33 LivenessAnalyzerBlock* result =
34 new (zone()->New(sizeof(LivenessAnalyzerBlock))) LivenessAnalyzerBlock(
35 blocks_.size(), local_count_, has_accumulator_, zone());
36 blocks_.push_back(result);
37 return result;
38 }
39
40
NewBlock(LivenessAnalyzerBlock * predecessor)41 LivenessAnalyzerBlock* LivenessAnalyzer::NewBlock(
42 LivenessAnalyzerBlock* predecessor) {
43 LivenessAnalyzerBlock* result = NewBlock();
44 result->AddPredecessor(predecessor);
45 return result;
46 }
47
48
Queue(LivenessAnalyzerBlock * block)49 void LivenessAnalyzer::Queue(LivenessAnalyzerBlock* block) {
50 if (!block->IsQueued()) {
51 block->SetQueued();
52 queue_.push(block);
53 }
54 }
55
56
Run(NonLiveFrameStateSlotReplacer * replacer)57 void LivenessAnalyzer::Run(NonLiveFrameStateSlotReplacer* replacer) {
58 if (local_count_ == 0 && !has_accumulator_) {
59 // No variables => nothing to do.
60 return;
61 }
62
63 // Put all blocks into the queue.
64 DCHECK(queue_.empty());
65 for (auto block : blocks_) {
66 Queue(block);
67 }
68
69 // Compute the fix-point.
70 BitVector working_area(
71 static_cast<int>(local_count_) + (has_accumulator_ ? 1 : 0), zone_);
72 while (!queue_.empty()) {
73 LivenessAnalyzerBlock* block = queue_.front();
74 queue_.pop();
75 block->Process(&working_area, nullptr);
76
77 for (auto i = block->pred_begin(); i != block->pred_end(); i++) {
78 if ((*i)->UpdateLive(&working_area)) {
79 Queue(*i);
80 }
81 }
82 }
83
84 // Update the frame states according to the liveness.
85 for (auto block : blocks_) {
86 block->Process(&working_area, replacer);
87 }
88 }
89
LivenessAnalyzerBlock(size_t id,size_t local_count,bool has_accumulator,Zone * zone)90 LivenessAnalyzerBlock::LivenessAnalyzerBlock(size_t id, size_t local_count,
91 bool has_accumulator, Zone* zone)
92 : entries_(zone),
93 predecessors_(zone),
94 live_(static_cast<int>(local_count) + (has_accumulator ? 1 : 0), zone),
95 queued_(false),
96 has_accumulator_(has_accumulator),
97 id_(id) {}
98
Process(BitVector * result,NonLiveFrameStateSlotReplacer * replacer)99 void LivenessAnalyzerBlock::Process(BitVector* result,
100 NonLiveFrameStateSlotReplacer* replacer) {
101 queued_ = false;
102
103 // Copy the bitvector to the target bit vector.
104 result->CopyFrom(live_);
105
106 for (auto entry : base::Reversed(entries_)) {
107 switch (entry.kind()) {
108 case Entry::kLookup:
109 result->Add(entry.var());
110 break;
111 case Entry::kBind:
112 result->Remove(entry.var());
113 break;
114 case Entry::kCheckpoint:
115 if (replacer != nullptr) {
116 replacer->ClearNonLiveFrameStateSlots(entry.node(), result);
117 }
118 break;
119 }
120 }
121 }
122
123
UpdateLive(BitVector * working_area)124 bool LivenessAnalyzerBlock::UpdateLive(BitVector* working_area) {
125 return live_.UnionIsChanged(*working_area);
126 }
127
128
ClearNonLiveFrameStateSlots(Node * frame_state,BitVector * liveness)129 void NonLiveFrameStateSlotReplacer::ClearNonLiveFrameStateSlots(
130 Node* frame_state, BitVector* liveness) {
131 DCHECK_EQ(liveness->length(), permanently_live_.length());
132
133 DCHECK_EQ(frame_state->opcode(), IrOpcode::kFrameState);
134 Node* locals_state = frame_state->InputAt(1);
135 DCHECK_EQ(locals_state->opcode(), IrOpcode::kStateValues);
136 int count = liveness->length() - (has_accumulator_ ? 1 : 0);
137 DCHECK_EQ(count, static_cast<int>(StateValuesAccess(locals_state).size()));
138 for (int i = 0; i < count; i++) {
139 if (!liveness->Contains(i) && !permanently_live_.Contains(i)) {
140 Node* new_values = ClearNonLiveStateValues(locals_state, liveness);
141 frame_state->ReplaceInput(1, new_values);
142 break;
143 }
144 }
145
146 if (has_accumulator_) {
147 DCHECK_EQ(frame_state->InputAt(2)->opcode(), IrOpcode::kStateValues);
148 DCHECK_EQ(
149 static_cast<int>(StateValuesAccess(frame_state->InputAt(2)).size()), 1);
150 int index = liveness->length() - 1;
151 if (!liveness->Contains(index) && !permanently_live_.Contains(index)) {
152 Node* new_value =
153 state_values_cache()->GetNodeForValues(&replacement_node_, 1);
154 frame_state->ReplaceInput(2, new_value);
155 }
156 }
157 }
158
159
ClearNonLiveStateValues(Node * values,BitVector * liveness)160 Node* NonLiveFrameStateSlotReplacer::ClearNonLiveStateValues(
161 Node* values, BitVector* liveness) {
162 DCHECK(inputs_buffer_.empty());
163
164 int var = 0;
165 for (Node* value_node : values->inputs()) {
166 // Make sure this isn't a state value tree
167 DCHECK(value_node->opcode() != IrOpcode::kStateValues);
168
169 // Index of the next variable is its furure index in the inputs buffer,
170 // i.e., the buffer's size.
171 bool live = liveness->Contains(var) || permanently_live_.Contains(var);
172 inputs_buffer_.push_back(live ? value_node : replacement_node_);
173
174 var++;
175 }
176
177 Node* result = state_values_cache()->GetNodeForValues(
178 inputs_buffer_.empty() ? nullptr : &(inputs_buffer_.front()),
179 inputs_buffer_.size());
180 inputs_buffer_.clear();
181 return result;
182 }
183
184
Print(std::ostream & os)185 void LivenessAnalyzerBlock::Print(std::ostream& os) {
186 os << "Block " << id();
187 bool first = true;
188 for (LivenessAnalyzerBlock* pred : predecessors_) {
189 if (!first) {
190 os << ", ";
191 } else {
192 os << "; predecessors: ";
193 first = false;
194 }
195 os << pred->id();
196 }
197 os << std::endl;
198
199 for (auto entry : entries_) {
200 os << " ";
201 switch (entry.kind()) {
202 case Entry::kLookup:
203 if (has_accumulator_ && entry.var() == live_.length() - 1) {
204 os << "- Lookup accumulator" << std::endl;
205 } else {
206 os << "- Lookup " << entry.var() << std::endl;
207 }
208 break;
209 case Entry::kBind:
210 if (has_accumulator_ && entry.var() == live_.length() - 1) {
211 os << "- Bind accumulator" << std::endl;
212 } else {
213 os << "- Bind " << entry.var() << std::endl;
214 }
215 break;
216 case Entry::kCheckpoint:
217 os << "- Checkpoint " << entry.node()->id() << std::endl;
218 break;
219 }
220 }
221
222 if (live_.length() > 0) {
223 os << " Live set: ";
224 for (int i = 0; i < live_.length(); i++) {
225 os << (live_.Contains(i) ? "L" : ".");
226 }
227 os << std::endl;
228 }
229 }
230
231 } // namespace compiler
232 } // namespace internal
233 } // namespace v8
234