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