Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1476)

Unified Diff: src/compiler/liveness-analyzer.cc

Issue 949743002: [turbofan] Variable liveness analysis for deopt (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Address review comments Created 5 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/compiler/liveness-analyzer.h ('k') | src/compiler/state-values-utils.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/compiler/liveness-analyzer.cc
diff --git a/src/compiler/liveness-analyzer.cc b/src/compiler/liveness-analyzer.cc
new file mode 100644
index 0000000000000000000000000000000000000000..8aeb8d5cb7923b38a590400cd31354fa4d0667df
--- /dev/null
+++ b/src/compiler/liveness-analyzer.cc
@@ -0,0 +1,200 @@
+// 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/compiler/liveness-analyzer.h"
+#include "src/compiler/js-graph.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 i = entries_.rbegin(); i != entries_.rend(); i++) {
+ auto entry = *i;
+ 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 (Node* 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 : 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
« no previous file with comments | « src/compiler/liveness-analyzer.h ('k') | src/compiler/state-values-utils.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698