Line data Source code
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 :
16 2512 : 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 5024 : queue_(zone) {}
23 :
24 0 : void LivenessAnalyzer::Print(std::ostream& os) {
25 0 : for (auto block : blocks_) {
26 0 : block->Print(os);
27 : os << std::endl;
28 : }
29 0 : }
30 :
31 :
32 1920 : LivenessAnalyzerBlock* LivenessAnalyzer::NewBlock() {
33 : LivenessAnalyzerBlock* result =
34 : new (zone()->New(sizeof(LivenessAnalyzerBlock))) LivenessAnalyzerBlock(
35 960 : blocks_.size(), local_count_, has_accumulator_, zone());
36 960 : blocks_.push_back(result);
37 960 : return result;
38 : }
39 :
40 :
41 517 : LivenessAnalyzerBlock* LivenessAnalyzer::NewBlock(
42 : LivenessAnalyzerBlock* predecessor) {
43 517 : LivenessAnalyzerBlock* result = NewBlock();
44 : result->AddPredecessor(predecessor);
45 517 : return result;
46 : }
47 :
48 :
49 0 : void LivenessAnalyzer::Queue(LivenessAnalyzerBlock* block) {
50 484 : if (!block->IsQueued()) {
51 : block->SetQueued();
52 : queue_.push(block);
53 : }
54 0 : }
55 :
56 :
57 443 : void LivenessAnalyzer::Run(NonLiveFrameStateSlotReplacer* replacer) {
58 443 : if (local_count_ == 0 && !has_accumulator_) {
59 : // No variables => nothing to do.
60 342 : return;
61 : }
62 :
63 : // Put all blocks into the queue.
64 : DCHECK(queue_.empty());
65 865 : for (auto block : blocks_) {
66 : Queue(block);
67 : }
68 :
69 : // Compute the fix-point.
70 : BitVector working_area(
71 101 : static_cast<int>(local_count_) + (has_accumulator_ ? 1 : 0), zone_);
72 682 : while (!queue_.empty()) {
73 480 : LivenessAnalyzerBlock* block = queue_.front();
74 : queue_.pop();
75 480 : block->Process(&working_area, nullptr);
76 :
77 883 : for (auto i = block->pred_begin(); i != block->pred_end(); i++) {
78 806 : if ((*i)->UpdateLive(&working_area)) {
79 : Queue(*i);
80 : }
81 : }
82 : }
83 :
84 : // Update the frame states according to the liveness.
85 865 : for (auto block : blocks_) {
86 382 : block->Process(&working_area, replacer);
87 : }
88 : }
89 :
90 960 : 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 960 : id_(id) {}
98 :
99 2424 : void LivenessAnalyzerBlock::Process(BitVector* result,
100 : NonLiveFrameStateSlotReplacer* replacer) {
101 862 : queued_ = false;
102 :
103 : // Copy the bitvector to the target bit vector.
104 862 : result->CopyFrom(live_);
105 :
106 5632 : for (auto entry : base::Reversed(entries_)) {
107 1954 : 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 1254 : if (replacer != nullptr) {
116 544 : replacer->ClearNonLiveFrameStateSlots(entry.node(), result);
117 : }
118 : break;
119 : }
120 : }
121 862 : }
122 :
123 :
124 0 : bool LivenessAnalyzerBlock::UpdateLive(BitVector* working_area) {
125 403 : return live_.UnionIsChanged(*working_area);
126 : }
127 :
128 :
129 544 : void NonLiveFrameStateSlotReplacer::ClearNonLiveFrameStateSlots(
130 1178 : 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 544 : int count = liveness->length() - (has_accumulator_ ? 1 : 0);
137 : DCHECK_EQ(count, static_cast<int>(StateValuesAccess(locals_state).size()));
138 754 : for (int i = 0; i < count; i++) {
139 1064 : if (!liveness->Contains(i) && !permanently_live_.Contains(i)) {
140 424 : Node* new_values = ClearNonLiveStateValues(locals_state, liveness);
141 424 : frame_state->ReplaceInput(1, new_values);
142 424 : break;
143 : }
144 : }
145 :
146 544 : 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 0 : int index = liveness->length() - 1;
151 0 : if (!liveness->Contains(index) && !permanently_live_.Contains(index)) {
152 : Node* new_value =
153 0 : state_values_cache()->GetNodeForValues(&replacement_node_, 1);
154 0 : frame_state->ReplaceInput(2, new_value);
155 : }
156 : }
157 544 : }
158 :
159 :
160 424 : Node* NonLiveFrameStateSlotReplacer::ClearNonLiveStateValues(
161 1094 : Node* values, BitVector* liveness) {
162 : DCHECK(inputs_buffer_.empty());
163 :
164 : int var = 0;
165 1764 : 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 1224 : bool live = liveness->Contains(var) || permanently_live_.Contains(var);
172 1094 : inputs_buffer_.push_back(live ? value_node : replacement_node_);
173 :
174 670 : var++;
175 : }
176 :
177 : Node* result = state_values_cache()->GetNodeForValues(
178 : inputs_buffer_.empty() ? nullptr : &(inputs_buffer_.front()),
179 848 : inputs_buffer_.size());
180 : inputs_buffer_.clear();
181 424 : return result;
182 : }
183 :
184 :
185 0 : void LivenessAnalyzerBlock::Print(std::ostream& os) {
186 0 : os << "Block " << id();
187 : bool first = true;
188 0 : for (LivenessAnalyzerBlock* pred : predecessors_) {
189 0 : if (!first) {
190 0 : os << ", ";
191 : } else {
192 0 : os << "; predecessors: ";
193 : first = false;
194 : }
195 : os << pred->id();
196 : }
197 : os << std::endl;
198 :
199 0 : for (auto entry : entries_) {
200 0 : os << " ";
201 0 : switch (entry.kind()) {
202 : case Entry::kLookup:
203 0 : if (has_accumulator_ && entry.var() == live_.length() - 1) {
204 0 : os << "- Lookup accumulator" << std::endl;
205 : } else {
206 0 : os << "- Lookup " << entry.var() << std::endl;
207 : }
208 : break;
209 : case Entry::kBind:
210 0 : if (has_accumulator_ && entry.var() == live_.length() - 1) {
211 0 : os << "- Bind accumulator" << std::endl;
212 : } else {
213 0 : os << "- Bind " << entry.var() << std::endl;
214 : }
215 : break;
216 : case Entry::kCheckpoint:
217 0 : os << "- Checkpoint " << entry.node()->id() << std::endl;
218 : break;
219 : }
220 : }
221 :
222 0 : if (live_.length() > 0) {
223 0 : os << " Live set: ";
224 0 : for (int i = 0; i < live_.length(); i++) {
225 0 : os << (live_.Contains(i) ? "L" : ".");
226 : }
227 : os << std::endl;
228 : }
229 0 : }
230 :
231 : } // namespace compiler
232 : } // namespace internal
233 : } // namespace v8
|
