This file contains code to determine the Tarjan intervals (nested strongly connected regions) of a flow graph. Tarjan's original algorithm is described in the following article: Tarjan, R.E. "Testing flow graph reducibility" J. of Computer & System Sciences 9, 355-365, 1974. More...

#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <cstring>
#include <cstdio>
#include <climits>
#include <unistd.h>
#include <OpenAnalysis/Utils/NestedSCR.hpp>

Include dependency graph for NestedSCR.cpp:

Go to the source code of this file.

Classes
class	OA::TarjWork
class	OA::TarjTreeNode
Namespaces
namespace	OA
	Namespace for the whole OpenAnalysis Toolkit.
Defines
#define	TARJ_nodeid(name) (tarj[name].nodeid)
#define	TARJ_outer(name) (tarj[name].outer)
#define	TARJ_inners(name) (tarj[name].inners)
#define	TARJ_next(name) (tarj[name].next)
#define	TARJ_level(name) (tarj[name].level)
#define	TARJ_type(name) (tarj[name].type)
#define	TARJ_last(name) (tarj[name].last)
#define	TARJ_last_id(name) (tarj[name].last_id)
#define	TARJ_loopIndex(name) (tarj[name].loopIndex)
#define	TARJ_contains(a, b)
#define	vertex(x) (wk[x].wk_vertex)
#define	TLast(x) (wk[x].wk_last)
#define	header(x) (wk[x].wk_header)
#define	nextP(x) (wk[x].wk_nextP)
#define	nextQ(x) (wk[x].wk_nextQ)
#define	inP(x) (wk[x].wk_inP)
#define	isCyclic(x) (wk[x].wk_isCyclic)
#define	reducible(x) (wk[x].wk_reducible)
#define	backPreds(x) (wk[x].backPreds)
#define	nonBackPreds(x) (wk[x].nonBackPreds)
#define	is_backedge(a, b) ((b <= a) & (a <= TLast(b)))
#define	dfnum(v) (nodeid_to_dfnum_map[v])
Variables
const OA::NestedSCR::DFNUM_t	DFNUM_ROOT = 0
const OA::NestedSCR::DFNUM_t	DFNUM_NIL = UINT_MAX
static int	OA::n
static int	OA::last_id
static int	OA::loopIndex

Detailed Description

This file contains code to determine the Tarjan intervals (nested strongly connected regions) of a flow graph. Tarjan's original algorithm is described in the following article: Tarjan, R.E. "Testing flow graph reducibility" J. of Computer & System Sciences 9, 355-365, 1974.

Extensions to Tarjan's algorithm were made here to handle reducible SCRs surrounded by or containing irreducible ones. The extensions are described in the following article: Havlak, P. "Nesting of reducible and irreducible loops" ACM TOPLAS, July, 1997.

The result is returned as a tree of SCRs, where a parent SCR contains its children. A leaf SCR is a single node, which is not really a loop unless the isCyclic flag is set.

Preconditions: 1. The underlying directed graph has a unique start node, dominating all others in the graph and a unique exit node, postdominating all others.

Authors:: Original DSystem code by phh (Paul Havlak?) Port to 'Classic OpenAnalysis' by John Mellor-Crummey, Jason Eckhardt Port to OpenAnalysis by Nathan Tallent (renamed NestedSCR from TarjanIntervals)

Version:

Id:: NestedSCR.cpp,v 1.2 2005/03/14 23:49:26 ntallent Exp

Copyright (c) 2002-2005, Rice University
Copyright (c) 2004-2005, University of Chicago
Copyright (c) 2006, Contributors
All rights reserved.
See ../../../Copyright.txt for details.

Definition in file NestedSCR.cpp.

Define Documentation

#define backPreds ( x ) (wk[x].backPreds)

Definition at line 191 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::FillPredLists(), and OA::NestedSCR::GetTarjans().

#define header ( x ) (wk[x].wk_header)

Definition at line 185 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::Build(), OA::CFG::ManagerCFGStandard::build_CFG_loop(), and OA::NestedSCR::GetTarjans().

#define inP ( x ) (wk[x].wk_inP)

Definition at line 188 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::GetTarjans().

#define is_backedge	(	a,
		b
	)		((b <= a) & (a <= TLast(b)))

Definition at line 205 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::FillPredLists(), OA::NestedSCR::GetTarjans(), and OA::NestedSCR::isBackEdge().

#define isCyclic ( x ) (wk[x].wk_isCyclic)

Definition at line 189 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::Build(), and OA::NestedSCR::GetTarjans().

#define nextP ( x ) (wk[x].wk_nextP)

Definition at line 186 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::GetTarjans().

#define nextQ ( x ) (wk[x].wk_nextQ)

Definition at line 187 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::GetTarjans().

#define nonBackPreds ( x ) (wk[x].nonBackPreds)

Definition at line 192 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::FillPredLists(), and OA::NestedSCR::GetTarjans().

#define reducible ( x ) (wk[x].wk_reducible)

Definition at line 190 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::Build(), and OA::NestedSCR::GetTarjans().

#define TARJ_contains	(	a,
		b
	)

Value:

( ( tarj[a].prenum <= tarj[b].prenum ) && \
      ( tarj[b].prenum <= tarj[tarj[a].last].prenum ) \
    )

Definition at line 177 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::Contains().

#define TARJ_inners ( name ) (tarj[name].inners)

Definition at line 170 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::Build(), OA::NestedSCR::ComputeIntervalIndexSubTree(), OA::NestedSCR::DumpSubTree(), OA::NestedSCR::getInners(), OA::NestedSCR::Prenumber(), and OA::NestedSCR::Sort().

#define TARJ_last ( name ) (tarj[name].last)

Definition at line 174 of file NestedSCR.cpp.

#define TARJ_last_id ( name ) (tarj[name].last_id)

Definition at line 175 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::getInnersLast().

#define TARJ_level ( name ) (tarj[name].level)

Definition at line 172 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::Build(), OA::NestedSCR::DumpSubTree(), OA::NestedSCR::getExits(), and OA::NestedSCR::getLevel().

#define TARJ_loopIndex ( name ) (tarj[name].loopIndex)

Definition at line 176 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::ComputeIntervalIndexSubTree(), OA::NestedSCR::DumpSubTree(), and OA::NestedSCR::getLoopIndex().

#define TARJ_next ( name ) (tarj[name].next)

Definition at line 171 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::Build(), OA::NestedSCR::ComputeIntervalIndexSubTree(), OA::NestedSCR::DumpSubTree(), OA::NestedSCR::getNext(), OA::NestedSCR::Prenumber(), and OA::NestedSCR::Sort().

#define TARJ_nodeid ( name ) (tarj[name].nodeid)

Definition at line 168 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::Build(), OA::NestedSCR::DumpSubTree(), OA::NestedSCR::getInners(), OA::NestedSCR::getInnersLast(), OA::NestedSCR::getLoopExited(), OA::NestedSCR::getNext(), OA::NestedSCR::getOuter(), OA::NestedSCR::LCA(), and OA::NestedSCR::Prenumber().

#define TARJ_outer ( name ) (tarj[name].outer)

Definition at line 169 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::Build(), OA::NestedSCR::getEdgeType(), OA::NestedSCR::getLoopExited(), OA::NestedSCR::getOuter(), OA::NestedSCR::LCA(), and OA::NestedSCR::Sort().

#define TARJ_type ( name ) (tarj[name].type)

Definition at line 173 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::Build(), OA::NestedSCR::DumpSubTree(), OA::NestedSCR::getEdgeType(), OA::NestedSCR::getLoopExited(), and OA::NestedSCR::getNodeType().

#define TLast ( x ) (wk[x].wk_last)

Definition at line 184 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::DFS().

#define vertex ( x ) (wk[x].wk_vertex)

Definition at line 183 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::Build(), OA::NestedSCR::DFS(), OA::NestedSCR::FillPredLists(), and OA::NestedSCR::GetTarjans().

Variable Documentation

const OA::NestedSCR::DFNUM_t DFNUM_ROOT = 0

Definition at line 66 of file NestedSCR.cpp.

Referenced by OA::NestedSCR::Build(), OA::NestedSCR::ComputeIntervalIndex(), OA::NestedSCR::dump(), OA::NestedSCR::FillPredLists(), OA::NestedSCR::GetTarjans(), OA::NestedSCR::Init(), OA::NestedSCR::Renumber(), and OA::TarjWork::TarjWork().

NestedSCR.cpp File Reference

Classes

Namespaces

Defines

Variables

Detailed Description

Define Documentation

Variable Documentation