src/compiler/liveness-analyzer.cc

// 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, bool has_accumulator,
                                   Zone* zone)
    : zone_(zone),
      blocks_(zone),
      local_count_(local_count),
      has_accumulator_(has_accumulator),
      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_, has_accumulator_, 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 && !has_accumulator_) {
    // No 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_) + (has_accumulator_ ? 1 : 0), 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,
                                             bool has_accumulator, Zone* zone)
    : entries_(zone),
      predecessors_(zone),
      live_(static_cast<int>(local_count) + (has_accumulator ? 1 : 0), zone),
      queued_(false),
      has_accumulator_(has_accumulator),
      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(liveness->length(), permanently_live_.length());

  DCHECK_EQ(frame_state->opcode(), IrOpcode::kFrameState);
  Node* locals_state = frame_state->InputAt(1);
  DCHECK_EQ(locals_state->opcode(), IrOpcode::kStateValues);
  int count = liveness->length() - (has_accumulator_ ? 1 : 0);
  DCHECK_EQ(count, static_cast<int>(StateValuesAccess(locals_state).size()));
  for (int i = 0; i < count; i++) {
    if (!liveness->Contains(i) && !permanently_live_.Contains(i)) {
      Node* new_values = ClearNonLiveStateValues(locals_state, liveness);
      frame_state->ReplaceInput(1, new_values);
      break;
    }
  }

  if (has_accumulator_) {
    DCHECK_EQ(frame_state->InputAt(2)->opcode(), IrOpcode::kStateValues);
    DCHECK_EQ(
        static_cast<int>(StateValuesAccess(frame_state->InputAt(2)).size()), 1);
    int index = liveness->length() - 1;
    if (!liveness->Contains(index) && !permanently_live_.Contains(index)) {
      Node* new_value =
          state_values_cache()->GetNodeForValues(&replacement_node_, 1);
      frame_state->ReplaceInput(2, new_value);
    }
  }
}


Node* NonLiveFrameStateSlotReplacer::ClearNonLiveStateValues(
    Node* values, BitVector* liveness) {
  DCHECK(inputs_buffer_.empty());

  int var = 0;
  for (Node* value_node : values->inputs()) {
    // Make sure this isn't a state value tree
    DCHECK(value_node->opcode() != IrOpcode::kStateValues);

    // Index of the next variable is its furure index in the inputs buffer,
    // i.e., the buffer's size.
    bool live = liveness->Contains(var) || permanently_live_.Contains(var);
    inputs_buffer_.push_back(live ? value_node : replacement_node_);

    var++;
  }

  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:
        if (has_accumulator_ && entry.var() == live_.length() - 1) {
          os << "- Lookup accumulator" << std::endl;
        } else {
          os << "- Lookup " << entry.var() << std::endl;
        }
        break;
      case Entry::kBind:
        if (has_accumulator_ && entry.var() == live_.length() - 1) {
          os << "- Bind accumulator" << std::endl;
        } else {
          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