dart::VariableLivenessAnalysis Class Reference

Inheritance diagram for dart::VariableLivenessAnalysis:

Public Member Functions
	VariableLivenessAnalysis (FlowGraph *flow_graph)
const GrowableArray< BitVector * > &	ComputeAssignedVars ()
bool	IsStoreAlive (BlockEntryInstr *block, StoreLocalInstr *store)
bool	IsLastLoad (BlockEntryInstr *block, LoadLocalInstr *load)
Public Member Functions inherited from dart::LivenessAnalysis
	LivenessAnalysis (intptr_t variable_count, const GrowableArray< BlockEntryInstr * > &postorder)
void	Analyze ()
virtual	~LivenessAnalysis ()
BitVector *	GetLiveInSetAt (intptr_t postorder_number) const
BitVector *	GetLiveOutSetAt (intptr_t postorder_number) const
BitVector *	GetLiveInSet (BlockEntryInstr *block) const
BitVector *	GetKillSet (BlockEntryInstr *block) const
BitVector *	GetLiveOutSet (BlockEntryInstr *block) const
void	Dump ()
Public Member Functions inherited from dart::ValueObject
	ValueObject ()
	~ValueObject ()

Private Member Functions
virtual void	ComputeInitialSets ()

Additional Inherited Members
Protected Member Functions inherited from dart::LivenessAnalysis
virtual void	ComputeInitialSets ()=0
bool	UpdateLiveOut (const BlockEntryInstr &instr)
bool	UpdateLiveIn (const BlockEntryInstr &instr)
void	ComputeLiveInAndLiveOutSets ()
Zone *	zone () const
Protected Attributes inherited from dart::LivenessAnalysis
Zone *	zone_
const intptr_t	variable_count_
const GrowableArray< BlockEntryInstr * > &	postorder_
GrowableArray< BitVector * >	live_out_
GrowableArray< BitVector * >	kill_
GrowableArray< BitVector * >	live_in_

Detailed Description

Definition at line 771 of file flow_graph.cc.

Constructor & Destructor Documentation

VariableLivenessAnalysis()

dart::VariableLivenessAnalysis::VariableLivenessAnalysis ( FlowGraph *  flow_graph )

inlineexplicit

Definition at line 773 of file flow_graph.cc.

      : LivenessAnalysis(flow_graph->variable_count(), flow_graph->postorder()),
        flow_graph_(flow_graph),
        assigned_vars_() {}

Member Function Documentation

ComputeAssignedVars()

const GrowableArray< BitVector * > & dart::VariableLivenessAnalysis::ComputeAssignedVars ( )

inline

Definition at line 780 of file flow_graph.cc.

                                                         {
    // We can't directly return kill_ because it uses postorder numbering while
    // SSA construction uses preorder numbering internally.
    // We have to permute postorder into preorder.
    assigned_vars_.Clear();
 
    const intptr_t block_count = flow_graph_->preorder().length();
    for (intptr_t i = 0; i < block_count; i++) {
      BlockEntryInstr* block = flow_graph_->preorder()[i];
      // All locals are assigned inside a try{} block.
      // This is a safe approximation and workaround to force insertion of
      // phis for stores that appear non-live because of the way catch-blocks
      // are connected to the graph: They normally are dominated by the
      // try-entry, but are direct successors of the graph entry in our flow
      // graph.
      // TODO(fschneider): Improve this approximation by better modeling the
      // actual data flow to reduce the number of redundant phis.
      BitVector* kill = GetKillSet(block);
      if (block->InsideTryBlock()) {
        kill->SetAll();
      } else {
        kill->Intersect(GetLiveOutSet(block));
      }
      assigned_vars_.Add(kill);
    }
 
    return assigned_vars_;
  }

ComputeInitialSets()

void dart::VariableLivenessAnalysis::ComputeInitialSets ( )

privatevirtual

Implements dart::LivenessAnalysis.

Definition at line 844 of file flow_graph.cc.

                                                  {
  const intptr_t block_count = postorder_.length();
 
  BitVector* last_loads = new (zone()) BitVector(zone(), variable_count_);
  for (intptr_t i = 0; i < block_count; i++) {
    BlockEntryInstr* block = postorder_[i];
 
    BitVector* kill = kill_[i];
    BitVector* live_in = live_in_[i];
    last_loads->Clear();
 
    // There is an implicit use (load-local) of every local variable at each
    // call inside a try{} block and every call has an implicit control-flow
    // to the catch entry. As an approximation we mark all locals as live
    // inside try{}.
    // TODO(fschneider): Improve this approximation, since not all local
    // variable stores actually reach a call.
    if (block->InsideTryBlock()) {
      live_in->SetAll();
      continue;
    }
 
    // Iterate backwards starting at the last instruction.
    for (BackwardInstructionIterator it(block); !it.Done(); it.Advance()) {
      Instruction* current = it.Current();
 
      LoadLocalInstr* load = current->AsLoadLocal();
      if (load != nullptr) {
        const intptr_t index = flow_graph_->EnvIndex(&load->local());
        if (index >= live_in->length()) continue;  // Skip tmp_locals.
        live_in->Add(index);
        if (!last_loads->Contains(index)) {
          last_loads->Add(index);
          load->mark_last();
        }
        continue;
      }
 
      StoreLocalInstr* store = current->AsStoreLocal();
      if (store != nullptr) {
        const intptr_t index = flow_graph_->EnvIndex(&store->local());
        if (index >= live_in->length()) continue;  // Skip tmp_locals.
        if (kill->Contains(index)) {
          if (!live_in->Contains(index)) {
            store->mark_dead();
          }
        } else {
          if (!live_in->Contains(index)) {
            store->mark_last();
          }
          kill->Add(index);
        }
        live_in->Remove(index);
        continue;
      }
    }
 
    // For blocks with parameter or special parameter instructions we add them
    // to the kill set.
    const bool is_function_entry = block->IsFunctionEntry();
    const bool is_osr_entry = block->IsOsrEntry();
    const bool is_catch_block_entry = block->IsCatchBlockEntry();
    if (is_function_entry || is_osr_entry || is_catch_block_entry) {
      const intptr_t parameter_count =
          (is_osr_entry || is_catch_block_entry)
              ? flow_graph_->variable_count()
              : flow_graph_->num_direct_parameters();
      for (intptr_t i = 0; i < parameter_count; ++i) {
        live_in->Remove(i);
        kill->Add(i);
      }
    }
    if (is_function_entry) {
      if (flow_graph_->parsed_function().has_arg_desc_var()) {
        const auto index = flow_graph_->ArgumentDescriptorEnvIndex();
        live_in->Remove(index);
        kill->Add(index);
      }
    }
  }
}

IsLastLoad()

bool dart::VariableLivenessAnalysis::IsLastLoad ( BlockEntryInstr *  block, LoadLocalInstr *  load  )

inline

Definition at line 829 of file flow_graph.cc.

                                                                {
    if (load->local().Equals(*flow_graph_->CurrentContextVar())) {
      return false;
    }
    const intptr_t index = flow_graph_->EnvIndex(&load->local());
    return load->is_last() && !GetLiveOutSet(block)->Contains(index);
  }

IsStoreAlive()

bool dart::VariableLivenessAnalysis::IsStoreAlive ( BlockEntryInstr *  block, StoreLocalInstr *  store  )

inline

Definition at line 811 of file flow_graph.cc.

                                                                    {
    if (store->local().Equals(*flow_graph_->CurrentContextVar())) {
      return true;
    }
 
    if (store->is_dead()) {
      return false;
    }
    if (store->is_last()) {
      const intptr_t index = flow_graph_->EnvIndex(&store->local());
      return GetLiveOutSet(block)->Contains(index);
    }
 
    return true;
  }

---

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

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