Dead Node Elimination context class. More...

Collaboration diagram for jlm::llvm::DeadNodeElimination::Context:

Public Member Functions
bool	markAlive (const rvsdg::Output &output)

bool	markAlive (const rvsdg::SimpleNode &simpleNode)

bool	isAlive (const rvsdg::Output &output) const noexcept

bool	isAlive (const rvsdg::SimpleNode &simpleNode) const noexcept

Static Public Member Functions
static std::unique_ptr< Context >	create ()

Private Attributes
util::HashSet< const rvsdg::SimpleNode * >	SimpleNodes_ {}

util::HashSet< const rvsdg::Output * >	Outputs_ {}

Detailed Description

Dead Node Elimination context class.

This class keeps track of all the nodes and outputs that are alive. In contrast to all other nodes, a simple node is considered alive if already a single of its outputs is alive. For this reason, this class keeps separately track of simple nodes and therefore avoids to store all its outputs (and instead stores the node itself). By marking the entire node as alive, we also avoid that we reiterate through all inputs of this node again in the future. The following example illustrates the issue:

o1 ... oN = Node2 i1 ... iN p1 ... pN = Node1 o1 ... oN

When we mark o1 as alive, we actually mark the entire Node2 as alive. This means that when we try to mark o2 alive in the future, we can immediately stop marking instead of reiterating through i1 ... iN again. Thus, by marking the entire simple node instead of just its outputs, we reduce the runtime for marking Node2 from O(oN x iN) to O(oN + iN).

Definition at line 39 of file DeadNodeElimination.cpp.

Member Function Documentation

◆ create()

static std::unique_ptr<Context> jlm::llvm::DeadNodeElimination::Context::create ( )

inlinestatic

Definition at line 75 of file DeadNodeElimination.cpp.

◆ isAlive() [1/2]

bool jlm::llvm::DeadNodeElimination::Context::isAlive ( const rvsdg::Output & output ) const

inlinenoexcept

Definition at line 63 of file DeadNodeElimination.cpp.

◆ isAlive() [2/2]

bool jlm::llvm::DeadNodeElimination::Context::isAlive ( const rvsdg::SimpleNode & simpleNode ) const

inlinenoexcept

Definition at line 69 of file DeadNodeElimination.cpp.

◆ markAlive() [1/2]

bool jlm::llvm::DeadNodeElimination::Context::markAlive ( const rvsdg::Output & output )

inline

Marks the given output as alive.

Returns: true if the output was previously not marked, false otherwise.

Definition at line 47 of file DeadNodeElimination.cpp.

◆ markAlive() [2/2]

bool jlm::llvm::DeadNodeElimination::Context::markAlive ( const rvsdg::SimpleNode & simpleNode )

inline

Marks the given simpleNode as alive.

Returns: true if the node was previously not marked, false otherwise.

Definition at line 57 of file DeadNodeElimination.cpp.

Member Data Documentation

◆ Outputs_

util::HashSet<const rvsdg::Output *> jlm::llvm::DeadNodeElimination::Context::Outputs_ {}

private

Definition at line 82 of file DeadNodeElimination.cpp.

◆ SimpleNodes_

util::HashSet<const rvsdg::SimpleNode *> jlm::llvm::DeadNodeElimination::Context::SimpleNodes_ {}

private

Definition at line 81 of file DeadNodeElimination.cpp.

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

jlm/llvm/opt/DeadNodeElimination.cpp

Public Member Functions

Static Public Member Functions

Private Attributes