logo::RemoveDeadNodePass Struct Reference

#include <RemoveDeadNodePass.h>

Collaboration diagram for logo::RemoveDeadNodePass:

Public Member Functions
const char *	name (void) const final
bool	run (loco::Graph *g)
	Run the pass.
Public Member Functions inherited from logo::Pass
virtual	~Pass ()=default

Detailed Description

Definition at line 25 of file RemoveDeadNodePass.h.

Member Function Documentation

name()

const char * logo::RemoveDeadNodePass::name ( void  ) const

inlinefinalvirtual

Reimplemented from logo::Pass.

Definition at line 27 of file RemoveDeadNodePass.h.

{ return "RemoveDeadNodePass"; }

run()

bool logo::RemoveDeadNodePass::run ( loco::Graph *  graph )

virtual

Run the pass.

Returns

false if there was nothing changed

Implements logo::Pass.

Definition at line 28 of file RemoveDeadNodePass.cpp.

{
  // Let's enumerate nodes required to compute output nodes
  auto active_nodes = loco::active_nodes(loco::output_nodes(g));
 
  // Find dead(= non-active) nodes
  std::set<loco::Node *> candidates;
 
  for (auto node : loco::all_nodes(g))
  {
    if (active_nodes.find(node) == active_nodes.end())
    {
      candidates.insert(node);
    }
  }
 
  // Let's drop the references from each dead node first and then remove these dead nodes
  //
  // Why?
  //
  // Let us consider the following example:
  //    %0 = Pull(...)
  //    %1 = ConstGen(...)
  //    %2 = Forward(input: %1)
  //    %3 = Push(from: %0) <- OUTPUT
  //
  // Forward (%2) is dead as it does not contribute to the final result (%3). However, it
  // refers to another dead node (%1).
  //
  // This example indicates that naive implementation results in dangling references.
  //
  // There are two possible solutions:
  //  1. Destroy nodes in topological order
  //  2. Drop the reference first and then destroy them
  //
  // The current implementation takes the latter approach for the simplicity of implementation.
  for (auto node : candidates)
  {
    node->drop();
  }
 
  for (auto node : candidates)
  {
    g->nodes()->destroy(node);
  }
 
  return candidates.size() > 0;
}

References loco::active_nodes(), loco::all_nodes(), and loco::output_nodes().

---

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

• compiler/logo/include/logo/RemoveDeadNodePass.h
• compiler/logo/src/Passes/RemoveDeadNodePass.cpp