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::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 24 void LivenessAnalyzer::Print(std::ostream& os) { 25 for (auto block : blocks_) { 26 block->Print(os); 27 os << std::endl; 28 } 29 } 30 31 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 41 LivenessAnalyzerBlock* LivenessAnalyzer::NewBlock( 42 LivenessAnalyzerBlock* predecessor) { 43 LivenessAnalyzerBlock* result = NewBlock(); 44 result->AddPredecessor(predecessor); 45 return result; 46 } 47 48 49 void LivenessAnalyzer::Queue(LivenessAnalyzerBlock* block) { 50 if (!block->IsQueued()) { 51 block->SetQueued(); 52 queue_.push(block); 53 } 54 } 55 56 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 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 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 124 bool LivenessAnalyzerBlock::UpdateLive(BitVector* working_area) { 125 return live_.UnionIsChanged(*working_area); 126 } 127 128 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 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 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