text: // Copyright 2013 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 "hydrogen-environment-liveness.h"
  
  
  namespace v8 {
  namespace internal {
  
  
  HEnvironmentLivenessAnalysisPhase::HEnvironmentLivenessAnalysisPhase(
      HGraph* graph)
      : HPhase("H_Environment liveness analysis", graph),
        block_count_(graph->blocks()->length()),
        maximum_environment_size_(graph->maximum_environment_size()),
        live_at_block_start_(block_count_, zone()),
        first_simulate_(block_count_, zone()),
        first_simulate_invalid_for_index_(block_count_, zone()),
        markers_(maximum_environment_size_, zone()),
        collect_markers_(true),
        last_simulate_(NULL),
        went_live_since_last_simulate_(maximum_environment_size_, zone()) {
    ASSERT(maximum_environment_size_ > 0);
    for (int i = 0; i < block_count_; ++i) {
      live_at_block_start_.Add(
          new(zone()) BitVector(maximum_environment_size_, zone()), zone());
      first_simulate_.Add(NULL, zone());
      first_simulate_invalid_for_index_.Add(
          new(zone()) BitVector(maximum_environment_size_, zone()), zone());
    }
  }
  
  
  void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlot(
      int index, HSimulate* simulate) {
    int operand_index = simulate->ToOperandIndex(index);
    if (operand_index == -1) {
      simulate->AddAssignedValue(index, graph()->GetConstantUndefined());
    } else {
      simulate->SetOperandAt(operand_index, graph()->GetConstantUndefined());
    }
  }
  
  
  void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsInSuccessors(
      HBasicBlock* block, BitVector* live) {
    // When a value is live in successor A but dead in B, we must
    // explicitly zap it in B.
    for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
      HBasicBlock* successor = it.Current();
      int successor_id = successor->block_id();
      BitVector* live_in_successor = live_at_block_start_[successor_id];
      if (live_in_successor->Equals(*live)) continue;
      for (int i = 0; i < live->length(); ++i) {
        if (!live->Contains(i)) continue;
        if (live_in_successor->Contains(i)) continue;
        if (first_simulate_invalid_for_index_.at(successor_id)->Contains(i)) {
          continue;
        }
        HSimulate* simulate = first_simulate_.at(successor_id);
        if (simulate == NULL) continue;
        ASSERT(VerifyClosures(simulate->closure(),
            block->last_environment()->closure()));
        ZapEnvironmentSlot(i, simulate);
      }
    }
  }
  
  
  void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsForInstruction(
      HEnvironmentMarker* marker) {
    if (!marker->CheckFlag(HValue::kEndsLiveRange)) return;
    HSimulate* simulate = marker->next_simulate();
    if (simulate != NULL) {
      ASSERT(VerifyClosures(simulate->closure(), marker->closure()));
      ZapEnvironmentSlot(marker->index(), simulate);
    }
  }
  
  
  void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtBlockEnd(
      HBasicBlock* block,
      BitVector* live) {
    // Liveness at the end of each block: union of liveness in successors.
    live->Clear();
    for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
      live->Union(*live_at_block_start_[it.Current()->block_id()]);
    }
  }
  
  
  void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtInstruction(
      HInstruction* instr,
      BitVector* live) {
    switch (instr->opcode()) {
      case HValue::kEnvironmentMarker: {
        HEnvironmentMarker* marker = HEnvironmentMarker::cast(instr);
        int index = marker->index();
        if (!live->Contains(index)) {
          marker->SetFlag(HValue::kEndsLiveRange);
        } else {
          marker->ClearFlag(HValue::kEndsLiveRange);
        }
        if (!went_live_since_last_simulate_.Contains(index)) {
          marker->set_next_simulate(last_simulate_);
        }
        if (marker->kind() == HEnvironmentMarker::LOOKUP) {
          live->Add(index);
        } else {
          ASSERT(marker->kind() == HEnvironmentMarker::BIND);
          live->Remove(index);
          went_live_since_last_simulate_.Add(index);
        }
        if (collect_markers_) {
          // Populate |markers_| list during the first pass.
          markers_.Add(marker, zone());
        }
        break;
      }
      case HValue::kLeaveInlined:
        // No environment values are live at the end of an inlined section.
        live->Clear();
        last_simulate_ = NULL;
  
        // The following ASSERTs guard the assumption used in case
        // kEnterInlined below:
        ASSERT(instr->next()->IsSimulate());
        ASSERT(instr->next()->next()->IsGoto());
  
        break;
      case HValue::kEnterInlined: {
        // Those environment values are live that are live at any return
        // target block. Here we make use of the fact that the end of an
        // inline sequence always looks like this: HLeaveInlined, HSimulate,
        // HGoto (to return_target block), with no environment lookups in
        // between (see ASSERTs above).
        HEnterInlined* enter = HEnterInlined::cast(instr);
        live->Clear();
        for (int i = 0; i < enter->return_targets()->length(); ++i) {
          int return_id = enter->return_targets()->at(i)->block_id();
          live->Union(*live_at_block_start_[return_id]);
        }
        last_simulate_ = NULL;
        break;
      }
      case HValue::kSimulate:
        last_simulate_ = HSimulate::cast(instr);
        went_live_since_last_simulate_.Clear();
        break;
      default:
        break;
    }
  }
  
  
  void HEnvironmentLivenessAnalysisPhase::Run() {
    ASSERT(maximum_environment_size_ > 0);
  
    // Main iteration. Compute liveness of environment slots, and store it
    // for each block until it doesn't change any more. For efficiency, visit
    // blocks in reverse order and walk backwards through each block. We
    // need several iterations to propagate liveness through nested loops.
    BitVector live(maximum_environment_size_, zone());
    BitVector worklist(block_count_, zone());
    for (int i = 0; i < block_count_; ++i) {
      worklist.Add(i);
    }
    while (!worklist.IsEmpty()) {
      for (int block_id = block_count_ - 1; block_id >= 0; --block_id) {
        if (!worklist.Contains(block_id)) {
          continue;
        }
        worklist.Remove(block_id);
        last_simulate_ = NULL;
  
        HBasicBlock* block = graph()->blocks()->at(block_id);
        UpdateLivenessAtBlockEnd(block, &live);
  
        for (HInstruction* instr = block->end(); instr != NULL;
             instr = instr->previous()) {
          UpdateLivenessAtInstruction(instr, &live);
        }
  
        // Reached the start of the block, do necessary bookkeeping:
        // store computed information for this block and add predecessors
        // to the work list as necessary.
        first_simulate_.Set(block_id, last_simulate_);
        first_simulate_invalid_for_index_[block_id]->CopyFrom(
            went_live_since_last_simulate_);
        if (live_at_block_start_[block_id]->UnionIsChanged(live)) {
          for (int i = 0; i < block->predecessors()->length(); ++i) {
            worklist.Add(block->predecessors()->at(i)->block_id());
          }
          if (block->IsInlineReturnTarget()) {
            worklist.Add(block->inlined_entry_block()->block_id());
          }
        }
      }
      // Only collect bind/lookup instructions during the first pass.
      collect_markers_ = false;
    }
  
    // Analysis finished. Zap dead environment slots.
    for (int i = 0; i < markers_.length(); ++i) {
      ZapEnvironmentSlotsForInstruction(markers_[i]);
    }
    for (int block_id = block_count_ - 1; block_id >= 0; --block_id) {
      HBasicBlock* block = graph()->blocks()->at(block_id);
      UpdateLivenessAtBlockEnd(block, &live);
      ZapEnvironmentSlotsInSuccessors(block, &live);
    }
  
    // Finally, remove the HEnvironment{Bind,Lookup} markers.
    for (int i = 0; i < markers_.length(); ++i) {
      markers_[i]->DeleteAndReplaceWith(NULL);
    }
  }
  
  
  #ifdef DEBUG
  bool HEnvironmentLivenessAnalysisPhase::VerifyClosures(
      Handle<JSFunction> a, Handle<JSFunction> b) {
    Heap::RelocationLock for_heap_access(isolate()->heap());
    AllowHandleDereference for_verification;
    return a.is_identical_to(b);
  }
  #endif
  
  } }  // namespace v8::internal
  