dart::LivenessAnalysis Class Reference

#include <flow_graph.h>

Inheritance diagram for dart::LivenessAnalysis:

Public Member Functions
	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 ()

Protected Member Functions
virtual void	ComputeInitialSets ()=0
bool	UpdateLiveOut (const BlockEntryInstr &instr)
bool	UpdateLiveIn (const BlockEntryInstr &instr)
void	ComputeLiveInAndLiveOutSets ()
Zone *	zone () const

Protected Attributes
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 748 of file flow_graph.h.

Constructor & Destructor Documentation

LivenessAnalysis()

dart::LivenessAnalysis::LivenessAnalysis	(	intptr_t	variable_count,
		const GrowableArray< BlockEntryInstr * > &	postorder
	)

Definition at line 679 of file flow_graph.cc.

    : zone_(Thread::Current()->zone()),
      variable_count_(variable_count),
      postorder_(postorder),
      live_out_(postorder.length()),
      kill_(postorder.length()),
      live_in_(postorder.length()) {}

~LivenessAnalysis()

virtual dart::LivenessAnalysis::~LivenessAnalysis ( )

inlinevirtual

Definition at line 755 of file flow_graph.h.

{}

Member Function Documentation

Analyze()

void dart::LivenessAnalysis::Analyze

(

)

Definition at line 731 of file flow_graph.cc.

                               {
  const intptr_t block_count = postorder_.length();
  for (intptr_t i = 0; i < block_count; i++) {
    live_out_.Add(new (zone()) BitVector(zone(), variable_count_));
    kill_.Add(new (zone()) BitVector(zone(), variable_count_));
    live_in_.Add(new (zone()) BitVector(zone(), variable_count_));
  }
 
  ComputeInitialSets();
  ComputeLiveInAndLiveOutSets();
}

ComputeInitialSets()

virtual void dart::LivenessAnalysis::ComputeInitialSets ( )

protectedpure virtual

Implemented in dart::VariableLivenessAnalysis, dart::SSALivenessAnalysis, and dart::StoreOptimizer.

ComputeLiveInAndLiveOutSets()

void dart::LivenessAnalysis::ComputeLiveInAndLiveOutSets ( )

protected

Definition at line 711 of file flow_graph.cc.

                                                   {
  const intptr_t block_count = postorder_.length();
  bool changed;
  do {
    changed = false;
 
    for (intptr_t i = 0; i < block_count; i++) {
      const BlockEntryInstr& block = *postorder_[i];
 
      // Live-in set depends only on kill set which does not
      // change in this loop and live-out set.  If live-out
      // set does not change there is no need to recompute
      // live-in set.
      if (UpdateLiveOut(block) && UpdateLiveIn(block)) {
        changed = true;
      }
    }
  } while (changed);
}

Dump()

void dart::LivenessAnalysis::Dump

(

)

Definition at line 751 of file flow_graph.cc.

                            {
  const intptr_t block_count = postorder_.length();
  for (intptr_t i = 0; i < block_count; i++) {
    BlockEntryInstr* block = postorder_[i];
    THR_Print("block @%" Pd " -> ", block->block_id());
 
    Instruction* last = block->last_instruction();
    for (intptr_t j = 0; j < last->SuccessorCount(); j++) {
      BlockEntryInstr* succ = last->SuccessorAt(j);
      THR_Print(" @%" Pd "", succ->block_id());
    }
    THR_Print("\n");
 
    PrintBitVector("  live out", live_out_[i]);
    PrintBitVector("  kill", kill_[i]);
    PrintBitVector("  live in", live_in_[i]);
  }
}

GetKillSet()

BitVector * dart::LivenessAnalysis::GetKillSet ( BlockEntryInstr *  block ) const

inline

Definition at line 769 of file flow_graph.h.

                                                      {
    return kill_[block->postorder_number()];
  }

GetLiveInSet()

BitVector * dart::LivenessAnalysis::GetLiveInSet ( BlockEntryInstr *  block ) const

inline

Definition at line 765 of file flow_graph.h.

                                                        {
    return GetLiveInSetAt(block->postorder_number());
  }

GetLiveInSetAt()

BitVector * dart::LivenessAnalysis::GetLiveInSetAt ( intptr_t  postorder_number ) const

inline

Definition at line 757 of file flow_graph.h.

                                                             {
    return live_in_[postorder_number];
  }

GetLiveOutSet()

BitVector * dart::LivenessAnalysis::GetLiveOutSet ( BlockEntryInstr *  block ) const

inline

Definition at line 773 of file flow_graph.h.

                                                         {
    return GetLiveOutSetAt(block->postorder_number());
  }

GetLiveOutSetAt()

BitVector * dart::LivenessAnalysis::GetLiveOutSetAt ( intptr_t  postorder_number ) const

inline

Definition at line 761 of file flow_graph.h.

                                                              {
    return live_out_[postorder_number];
  }

UpdateLiveIn()

bool dart::LivenessAnalysis::UpdateLiveIn ( const BlockEntryInstr &  instr )

protected

Definition at line 704 of file flow_graph.cc.

                                                                {
  BitVector* live_out = live_out_[block.postorder_number()];
  BitVector* kill = kill_[block.postorder_number()];
  BitVector* live_in = live_in_[block.postorder_number()];
  return live_in->KillAndAdd(kill, live_out);
}

UpdateLiveOut()

bool dart::LivenessAnalysis::UpdateLiveOut ( const BlockEntryInstr &  instr )

protected

Definition at line 689 of file flow_graph.cc.

                                                                 {
  BitVector* live_out = live_out_[block.postorder_number()];
  bool changed = false;
  Instruction* last = block.last_instruction();
  ASSERT(last != nullptr);
  for (intptr_t i = 0; i < last->SuccessorCount(); i++) {
    BlockEntryInstr* succ = last->SuccessorAt(i);
    ASSERT(succ != nullptr);
    if (live_out->AddAll(live_in_[succ->postorder_number()])) {
      changed = true;
    }
  }
  return changed;
}

zone()

Zone * dart::LivenessAnalysis::zone ( ) const

inlineprotected

Definition at line 799 of file flow_graph.h.

{ return zone_; }

Member Data Documentation

kill_

GrowableArray<BitVector*> dart::LivenessAnalysis::kill_

protected

Definition at line 815 of file flow_graph.h.

live_in_

GrowableArray<BitVector*> dart::LivenessAnalysis::live_in_

protected

Definition at line 819 of file flow_graph.h.

live_out_

GrowableArray<BitVector*> dart::LivenessAnalysis::live_out_

protected

Definition at line 811 of file flow_graph.h.

postorder_

const GrowableArray<BlockEntryInstr*>& dart::LivenessAnalysis::postorder_

protected

Definition at line 805 of file flow_graph.h.

variable_count_

const intptr_t dart::LivenessAnalysis::variable_count_

protected

Definition at line 803 of file flow_graph.h.

zone_

Zone* dart::LivenessAnalysis::zone_

protected

Definition at line 801 of file flow_graph.h.

---

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

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