| // Copyright 2014 the V8 project authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "src/base/adapters.h" |
| #include "src/compiler/js-graph.h" |
| #include "src/compiler/liveness-analyzer.h" |
| #include "src/compiler/node.h" |
| #include "src/compiler/node-matchers.h" |
| #include "src/compiler/state-values-utils.h" |
| |
| namespace v8 { |
| namespace internal { |
| namespace compiler { |
| |
| |
| LivenessAnalyzer::LivenessAnalyzer(size_t local_count, Zone* zone) |
| : zone_(zone), blocks_(zone), local_count_(local_count), queue_(zone) {} |
| |
| |
| void LivenessAnalyzer::Print(std::ostream& os) { |
| for (auto block : blocks_) { |
| block->Print(os); |
| os << std::endl; |
| } |
| } |
| |
| |
| LivenessAnalyzerBlock* LivenessAnalyzer::NewBlock() { |
| LivenessAnalyzerBlock* result = |
| new (zone()->New(sizeof(LivenessAnalyzerBlock))) |
| LivenessAnalyzerBlock(blocks_.size(), local_count_, zone()); |
| blocks_.push_back(result); |
| return result; |
| } |
| |
| |
| LivenessAnalyzerBlock* LivenessAnalyzer::NewBlock( |
| LivenessAnalyzerBlock* predecessor) { |
| LivenessAnalyzerBlock* result = NewBlock(); |
| result->AddPredecessor(predecessor); |
| return result; |
| } |
| |
| |
| void LivenessAnalyzer::Queue(LivenessAnalyzerBlock* block) { |
| if (!block->IsQueued()) { |
| block->SetQueued(); |
| queue_.push(block); |
| } |
| } |
| |
| |
| void LivenessAnalyzer::Run(NonLiveFrameStateSlotReplacer* replacer) { |
| if (local_count_ == 0) { |
| // No local variables => nothing to do. |
| return; |
| } |
| |
| // Put all blocks into the queue. |
| DCHECK(queue_.empty()); |
| for (auto block : blocks_) { |
| Queue(block); |
| } |
| |
| // Compute the fix-point. |
| BitVector working_area(static_cast<int>(local_count_), zone_); |
| while (!queue_.empty()) { |
| LivenessAnalyzerBlock* block = queue_.front(); |
| queue_.pop(); |
| block->Process(&working_area, nullptr); |
| |
| for (auto i = block->pred_begin(); i != block->pred_end(); i++) { |
| if ((*i)->UpdateLive(&working_area)) { |
| Queue(*i); |
| } |
| } |
| } |
| |
| // Update the frame states according to the liveness. |
| for (auto block : blocks_) { |
| block->Process(&working_area, replacer); |
| } |
| } |
| |
| LivenessAnalyzerBlock::LivenessAnalyzerBlock(size_t id, size_t local_count, |
| Zone* zone) |
| : entries_(zone), |
| predecessors_(zone), |
| live_(local_count == 0 ? 1 : static_cast<int>(local_count), zone), |
| queued_(false), |
| id_(id) {} |
| |
| void LivenessAnalyzerBlock::Process(BitVector* result, |
| NonLiveFrameStateSlotReplacer* replacer) { |
| queued_ = false; |
| |
| // Copy the bitvector to the target bit vector. |
| result->CopyFrom(live_); |
| |
| for (auto entry : base::Reversed(entries_)) { |
| switch (entry.kind()) { |
| case Entry::kLookup: |
| result->Add(entry.var()); |
| break; |
| case Entry::kBind: |
| result->Remove(entry.var()); |
| break; |
| case Entry::kCheckpoint: |
| if (replacer != nullptr) { |
| replacer->ClearNonLiveFrameStateSlots(entry.node(), result); |
| } |
| break; |
| } |
| } |
| } |
| |
| |
| bool LivenessAnalyzerBlock::UpdateLive(BitVector* working_area) { |
| return live_.UnionIsChanged(*working_area); |
| } |
| |
| |
| void NonLiveFrameStateSlotReplacer::ClearNonLiveFrameStateSlots( |
| Node* frame_state, BitVector* liveness) { |
| DCHECK_EQ(frame_state->opcode(), IrOpcode::kFrameState); |
| Node* locals_state = frame_state->InputAt(1); |
| DCHECK_EQ(locals_state->opcode(), IrOpcode::kStateValues); |
| int count = static_cast<int>(StateValuesAccess(locals_state).size()); |
| DCHECK_EQ(count == 0 ? 1 : count, liveness->length()); |
| for (int i = 0; i < count; i++) { |
| bool live = liveness->Contains(i) || permanently_live_.Contains(i); |
| if (!live || locals_state->InputAt(i) != replacement_node_) { |
| Node* new_values = ClearNonLiveStateValues(locals_state, liveness); |
| frame_state->ReplaceInput(1, new_values); |
| break; |
| } |
| } |
| } |
| |
| |
| Node* NonLiveFrameStateSlotReplacer::ClearNonLiveStateValues( |
| Node* values, BitVector* liveness) { |
| DCHECK(inputs_buffer_.empty()); |
| for (StateValuesAccess::TypedNode node : StateValuesAccess(values)) { |
| // Index of the next variable is its furure index in the inputs buffer, |
| // i.e., the buffer's size. |
| int var = static_cast<int>(inputs_buffer_.size()); |
| bool live = liveness->Contains(var) || permanently_live_.Contains(var); |
| inputs_buffer_.push_back(live ? node.node : replacement_node_); |
| } |
| Node* result = state_values_cache()->GetNodeForValues( |
| inputs_buffer_.empty() ? nullptr : &(inputs_buffer_.front()), |
| inputs_buffer_.size()); |
| inputs_buffer_.clear(); |
| return result; |
| } |
| |
| |
| void LivenessAnalyzerBlock::Print(std::ostream& os) { |
| os << "Block " << id(); |
| bool first = true; |
| for (LivenessAnalyzerBlock* pred : predecessors_) { |
| if (!first) { |
| os << ", "; |
| } else { |
| os << "; predecessors: "; |
| first = false; |
| } |
| os << pred->id(); |
| } |
| os << std::endl; |
| |
| for (auto entry : entries_) { |
| os << " "; |
| switch (entry.kind()) { |
| case Entry::kLookup: |
| os << "- Lookup " << entry.var() << std::endl; |
| break; |
| case Entry::kBind: |
| os << "- Bind " << entry.var() << std::endl; |
| break; |
| case Entry::kCheckpoint: |
| os << "- Checkpoint " << entry.node()->id() << std::endl; |
| break; |
| } |
| } |
| |
| if (live_.length() > 0) { |
| os << " Live set: "; |
| for (int i = 0; i < live_.length(); i++) { |
| os << (live_.Contains(i) ? "L" : "."); |
| } |
| os << std::endl; |
| } |
| } |
| |
| } // namespace compiler |
| } // namespace internal |
| } // namespace v8 |