dart::DeadCodeElimination Class Reference

#include <redundancy_elimination.h>

Inheritance diagram for dart::DeadCodeElimination:

Static Public Member Functions
static void	EliminateDeadPhis (FlowGraph *graph)
static void	RemoveDeadAndRedundantPhisFromTheGraph (FlowGraph *graph)
static void	EliminateDeadCode (FlowGraph *graph)

Detailed Description

Definition at line 110 of file redundancy_elimination.h.

Member Function Documentation

EliminateDeadCode()

void dart::DeadCodeElimination::EliminateDeadCode ( FlowGraph *  graph )

static

Definition at line 4461 of file redundancy_elimination.cc.

                                                                 {
  GrowableArray<Instruction*> worklist;
  BitVector live(flow_graph->zone(), flow_graph->current_ssa_temp_index());
 
  // Mark all instructions with side-effects as live.
  for (BlockIterator block_it = flow_graph->reverse_postorder_iterator();
       !block_it.Done(); block_it.Advance()) {
    BlockEntryInstr* block = block_it.Current();
    for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
      Instruction* current = it.Current();
      ASSERT(!current->IsMoveArgument());
      // TODO(alexmarkov): take control dependencies into account and
      // eliminate dead branches/conditions.
      if (!current->CanEliminate(block)) {
        worklist.Add(current);
        if (Definition* def = current->AsDefinition()) {
          if (def->HasSSATemp()) {
            live.Add(def->ssa_temp_index());
          }
        }
      }
    }
  }
 
  // Iteratively follow inputs of instructions in the work list.
  while (!worklist.is_empty()) {
    Instruction* current = worklist.RemoveLast();
    for (intptr_t i = 0, n = current->InputCount(); i < n; ++i) {
      Definition* input = current->InputAt(i)->definition();
      ASSERT(input->HasSSATemp());
      if (!live.Contains(input->ssa_temp_index())) {
        worklist.Add(input);
        live.Add(input->ssa_temp_index());
      }
    }
    for (intptr_t i = 0, n = current->ArgumentCount(); i < n; ++i) {
      Definition* input = current->ArgumentAt(i);
      ASSERT(input->HasSSATemp());
      if (!live.Contains(input->ssa_temp_index())) {
        worklist.Add(input);
        live.Add(input->ssa_temp_index());
      }
    }
    if (current->env() != nullptr) {
      for (Environment::DeepIterator it(current->env()); !it.Done();
           it.Advance()) {
        Definition* input = it.CurrentValue()->definition();
        ASSERT(!input->IsMoveArgument());
        if (input->HasSSATemp() && !live.Contains(input->ssa_temp_index())) {
          worklist.Add(input);
          live.Add(input->ssa_temp_index());
        }
      }
    }
  }
 
  // Remove all instructions which are not marked as live.
  for (BlockIterator block_it = flow_graph->reverse_postorder_iterator();
       !block_it.Done(); block_it.Advance()) {
    BlockEntryInstr* block = block_it.Current();
    if (JoinEntryInstr* join = block->AsJoinEntry()) {
      for (PhiIterator it(join); !it.Done(); it.Advance()) {
        PhiInstr* current = it.Current();
        if (!live.Contains(current->ssa_temp_index())) {
          it.RemoveCurrentFromGraph();
        }
      }
    }
    for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
      Instruction* current = it.Current();
      if (!current->CanEliminate(block)) {
        continue;
      }
      ASSERT(!current->IsMoveArgument());
      ASSERT((current->ArgumentCount() == 0) || !current->HasMoveArguments());
      if (Definition* def = current->AsDefinition()) {
        if (def->HasSSATemp() && live.Contains(def->ssa_temp_index())) {
          continue;
        }
      }
      it.RemoveCurrentFromGraph();
    }
  }
}

EliminateDeadPhis()

void dart::DeadCodeElimination::EliminateDeadPhis ( FlowGraph *  graph )

static

Definition at line 4394 of file redundancy_elimination.cc.

                                                                 {
  GrowableArray<PhiInstr*> live_phis;
  for (BlockIterator b = flow_graph->postorder_iterator(); !b.Done();
       b.Advance()) {
    JoinEntryInstr* join = b.Current()->AsJoinEntry();
    if (join != nullptr) {
      for (PhiIterator it(join); !it.Done(); it.Advance()) {
        PhiInstr* phi = it.Current();
        // Phis that have uses and phis inside try blocks are
        // marked as live.
        if (HasRealUse(phi)) {
          live_phis.Add(phi);
          phi->mark_alive();
        } else {
          phi->mark_dead();
        }
      }
    }
  }
 
  while (!live_phis.is_empty()) {
    PhiInstr* phi = live_phis.RemoveLast();
    for (intptr_t i = 0; i < phi->InputCount(); i++) {
      Value* val = phi->InputAt(i);
      PhiInstr* used_phi = val->definition()->AsPhi();
      if ((used_phi != nullptr) && !used_phi->is_alive()) {
        used_phi->mark_alive();
        live_phis.Add(used_phi);
      }
    }
  }
 
  RemoveDeadAndRedundantPhisFromTheGraph(flow_graph);
}

RemoveDeadAndRedundantPhisFromTheGraph()

void dart::DeadCodeElimination::RemoveDeadAndRedundantPhisFromTheGraph ( FlowGraph *  graph )

static

Definition at line 4429 of file redundancy_elimination.cc.

                           {
  for (auto block : flow_graph->postorder()) {
    if (JoinEntryInstr* join = block->AsJoinEntry()) {
      if (join->phis_ == nullptr) continue;
 
      // Eliminate dead phis and compact the phis_ array of the block.
      intptr_t to_index = 0;
      for (intptr_t i = 0; i < join->phis_->length(); ++i) {
        PhiInstr* phi = (*join->phis_)[i];
        if (phi != nullptr) {
          if (!phi->is_alive()) {
            phi->ReplaceUsesWith(flow_graph->constant_null());
            phi->UnuseAllInputs();
            (*join->phis_)[i] = nullptr;
            if (FLAG_trace_optimization && flow_graph->should_print()) {
              THR_Print("Removing dead phi v%" Pd "\n", phi->ssa_temp_index());
            }
          } else {
            (*join->phis_)[to_index++] = phi;
          }
        }
      }
      if (to_index == 0) {
        join->phis_ = nullptr;
      } else {
        join->phis_->TruncateTo(to_index);
      }
    }
  }
}

---

The documentation for this class was generated from the following files:

• third_party/dart-lang/sdk/runtime/vm/compiler/backend/redundancy_elimination.h
• third_party/dart-lang/sdk/runtime/vm/compiler/backend/redundancy_elimination.cc