DDG Namespace Reference

Detailed Description

All the API symbols used in the DDG library.


Data Structures

class  ARCHITECTURE
class  DAG
 This class represents a directed acyclic graph (DAG). More...
class  IllegalAccessNode
class  InvalidISADesc
class  BadIODDG
class  BadRegType
class  BadInstructionType
class  NonUniqueRegisterType
class  IllegalDependance
class  NonUniqueNodeID
class  INFO_EDGE
 This class represents the attributes (information) attached to an edge in a DDG. More...
class  INFO_NODE
 This class represents the attributes (information) attached to each node in a DDG. More...
class  INSTRUCTIONS_TYPES
 This class describes a generic instruction, used by the class ARCHITECTURE to describe an ISA. A generic instruction object contains opcode, unique id per opcode, string opcode, list of writtent registers, list of written register types, etc. More...
class  LOOP
 This class represent cyclic data dependence graphs of simple loops (without branches). More...
class  REGISTER_TYPES
class  CBC
class  EN

Enumerations

enum  edge_type {
  flowdep_reg = 1, antidep_reg, outputdep_reg, inputdep_reg,
  flowdep_mem, antidep_mem, outputdep_mem, inputdep_mem,
  spilldep_mem, other_mem, serial, killerdep,
  reusedep
}
 Edges corresponds to data dependences. Data dependences are classified into multiple types : flowdep_reg, antidep_reg, outputdep_reg, inputdep_reg, flowdep_mem, etc. More...
enum  NodeFlag {
  NodeFlag_Nothing = 0x0, NodeFlag_PartialDef = 0x1, NodeFlag_SpillCode = 0x2, NodeFlag_Volatile = 0x4,
  NodeFlag_SPUpdate = 0x8, NodeFlag_Prefetch = 0x10, NodeFlag_Preload = 0x20, NodeFlag_Barrier = 0x40,
  NodeFlag_Clobber = 0x80, NodeFlag_Hoisted = 0x100, NodeFlag_DeadCode = 0x200, NodeFlag_SafeAccess = 0x800,
  NodeFlag_SafePerfs = 0x1000, NodeFlag_EntryCode = 0x4000, NodeFlag_ExitCode = 0x8000, NodeFlag_KillOp = 0x5000
}
 Nodes may have some flag representing, special nodes. If a node corresponds to a regular instruction, then its flag is NodeFlag_Nothing. More...

Functions

template<class T>
LEDA::list< T > set_to_list (const set< T > l)
template<class T>
set< T > list_to_set (const list< T > l)
bool lt (node u, node v)
bool le (node u, node v)
bool gt (node u, node v)
bool ge (node u, node v)
bool parallel (node u, node v)
bool comparable (node u, node v)
int MAXIMAL_ANTI_CHAIN (const graph &G, set< node > &MA)
int MINIMAL_CHAIN (const graph &G, node_array< int > &chain)
int MINIMAL_CHAIN (const DAG &G, array< list< node > > &C)
int REGISTER_SATURATION (const DAG &G, leda::list< node > &RS_values)
int REGISTER_SATURATION (const DAG &G, leda::list< node > &RS_values, node_array< node > &k)
int REGISTER_SATURATION (const DAG &G, int t, leda::list< node > &RS_values)
int REGISTER_SATURATION (const DAG &G, int t, leda::list< node > &RS_values, node_array< node > &k)
std::string edge_type_to_string (const edge_type)
 Convert an edge_type to string ("flow", "serial", "antidep", ...).
edge_type string_to_edge_type (const std::string)
 Convert a string to an edge_type.
void unroll (const LOOP &L, DAG &unrolled, int unroll_degree)
 Returns the body of the unrolled loop.
void unroll (const LOOP &L, LOOP &unrolled, int unroll_degree)
 Returns an unrolled loop.
void loop_merge (const LOOP &L1, const LOOP &L2, LOOP &L3)
 Merges two independent loop DDGs in order to produce a new DDG.
bool retime_ddg (LOOP &G, LEDA::node_array< int > &r)
 Computes and applies a valid loop retiming (called also loop shifing).
bool retime_ddg (LOOP &G)
 Computes and applies a valid loop retiming (called also loop shifing).
bool apply_retiming (LOOP &G, const LEDA::node_array< int > r)
 Applies the loop retiming given as input.
bool is_lexicographic_positive (LOOP &G, leda::list< edge > &le)
 Checks if all circuits of $ G $ are lexicographic positive. That is, $ \forall C $ a circuit in $ G $, $ \lambda(C)=\sum_{e\in C} \lambda(e) > 0 $.

Enumeration Type Documentation

enum typedef enum edge_type

Edges corresponds to data dependences. Data dependences are classified into multiple types : flowdep_reg, antidep_reg, outputdep_reg, inputdep_reg, flowdep_mem, etc.

Remarks:
The user can modify this set of edge types in order to take into account user-defined data dependences.
Enumerator:
flowdep_reg 
antidep_reg 
outputdep_reg 
inputdep_reg 
flowdep_mem 
antidep_mem 
outputdep_mem 
inputdep_mem 
spilldep_mem 
other_mem 
serial 
killerdep 
reusedep 

Definition at line 50 of file info_edge.h.

enum typedef enum NodeFlag

Nodes may have some flag representing, special nodes. If a node corresponds to a regular instruction, then its flag is NodeFlag_Nothing.

Enumerator:
NodeFlag_Nothing 
NodeFlag_PartialDef 
NodeFlag_SpillCode 
NodeFlag_Volatile 
NodeFlag_SPUpdate 
NodeFlag_Prefetch 
NodeFlag_Preload 
NodeFlag_Barrier 
NodeFlag_Clobber 
NodeFlag_Hoisted 
NodeFlag_DeadCode 
NodeFlag_SafeAccess 
NodeFlag_SafePerfs 
NodeFlag_EntryCode 
NodeFlag_ExitCode 
NodeFlag_KillOp 

Definition at line 51 of file info_node.h.

Function Documentation

bool apply_retiming ( LOOP &  G,
const LEDA::node_array< int >  r 
)

Applies the loop retiming given as input.

Parameters:
[in,out] G The loop to retime (modified by the loop retiming)
[in] r the input retiming given by the user.
Returns:
true if the input retiming is valid (all retimed edge distances are nonnegative).

false if the input retiming is not valid (in case of the presence of a nonpositive retimed edge distance).

Warning:
If the retiming is not valid, the loop would been modified anywhere.
Loop retiming consists of the following graph transformation: for each loop statement $ u $, we associate an integer shift $ r(u) $ which means that we delay the operation $ u $ by $ r(u) $ iterations. Then, each statement $ u $ that was representing the operation $ u $ of loop iteration $ i $ represents now the operation $ u $ of loop iteration $ i-r(u) $. The new distance of each arc $ e=(u,v) $ becomes equal to $ \lambda_r(e)=\lambda(e)+r(v)-r(u) $. Such new distance is always nonnegative $ \lambda_r(u)\ge 0, \forall u \in V $.

For more details about loop retiming, please study the excellent research article of Leiserson and Saxe published in Algorithmica 1991 (Retiming asynchronous circuits).

bool comparable ( node  u,
node  v 
)

Parameters:
[in] u A first node
[in] v A second node
Returns:
True if $ u \sim v $, i.e., $ u\le v \vee v \le u $.
Precondition:
$ u $ and $ v $ belongs to the same DAG. This is a notation from the lattices and order theory
Remarks:
$ \forall u \in V, u \sim u $
Examples:
dag_example.cpp.

std::string DDG::edge_type_to_string ( const   edge_type  ) 

Convert an edge_type to string ("flow", "serial", "antidep", ...).

Warning:
Returns empty string in case of unknownn edge_type

bool ge ( node  u,
node  v 
)

Parameters:
[in] u A first node
[in] v A second node
Returns:
Returns True if $ u \ge v $, i.e., $ u=v \vee \exists \textrm{ a path } (v,\ldots,u) $.
Precondition:
$ u $ and $ v $ belongs to the same DAG. This is a notation from the lattices and order theory
Remarks:
this relationship is reflexive: $ \forall u \in V, u \ge u $
Examples:
dag_example.cpp.

bool gt ( node  u,
node  v 
)

Parameters:
[in] u A first node
[in] v A second node
Returns:
Returns True if $ u > v $, i.e., $ u \neq \wedge \exists \textrm{ a path } (v,\ldots,u) $.
Precondition:
$ u $ and $ v $ belongs to the same DAG. This is a notation from the lattices and order theory
Examples:
dag_example.cpp.

is_lexicographic_positive ( LOOP &  G,
leda::list< edge > &  le 
)

Checks if all circuits of $ G $ are lexicographic positive. That is, $ \forall C $ a circuit in $ G $, $ \lambda(C)=\sum_{e\in C} \lambda(e) > 0 $.

Parameters:
[in] G The loop check
[out] le A list of a delinquent circuit $ C $, that is $ \lambda(C) \le 0 $.
Returns:
true if the input DDG is lexicographic positive. False otherwise.
In order to check if a DDG is lexicographic positive, we use the lemma number 10.3 in page 193 of the PhD thesis of M. Sid Touati. That lemma uses loop retiming (studied by Leiserson and Saxe), but the current implementation converts loop retiming to a potential computation algorithms. As proved by Leiserson and Saxe, every retiming is equivalent to a potential in a graph.

bool le ( node  u,
node  v 
)

Parameters:
[in] u A first node
[in] v A second node
Returns:
Returns True if $ u \le v $, i.e., $ u=v \vee \exists \textrm{ a path } (u,\ldots,v) $.
Precondition:
$ u $ and $ v $ belongs to the same DAG. This is a notation from the lattices and order theory
Remarks:
this relationship is reflexive: $ \forall u \in V, u \le u $
Examples:
dag_example.cpp, and RS_example.cpp.

void loop_merge ( const LOOP &  L1,
const LOOP &  L2,
LOOP &  L3 
)

Merges two independent loop DDGs in order to produce a new DDG.

Parameters:
[in] L1 The first DDG to consider.
[in] L2 The second DDG to consider.
[out] L3 A new loop consisting of merging distinct copies of L1 and L2.
Precondition:
Unrolling degree and all dependence distances should be nonnegative. $ \forall u\in V, \lambda(u)\ge 0 $.

bool lt ( node  u,
node  v 
)

Parameters:
[in] u A first node
[in] v A second node
Returns:
Returns True if $ u < v $, i.e., $ u \neq \wedge \exists \textrm{ a path } (u,\ldots,v) $.
Precondition:
$ u $ and $ v $ belongs to the same DAG. This is a notation from the lattices and order theory
Examples:
dag_example.cpp.

int MAXIMAL_ANTI_CHAIN ( const graph &  G,
set< node > &  MA 
)

Parameters:
[in] G An acyclic graph (DAG, order)
[out] MA The set of nodes belonging to a maximal antichain
Returns:
The size of a maximal antichain in the graph (-1 if the graph is not acyclic). Returns 0 if the input acyclic graph is empty. Returns -1 if error.
This function implements Dilworth decomposition to compute maximal antichain inside an order (DAG).
Remarks:
A maximal antichain may not be unique. This function returns an arbitrary one.
Precondition:
The input graph G should be acyclic.
Examples:
dag_example.cpp.

int DDG::MINIMAL_CHAIN ( const DAG &  G,
array< list< node > > &  C 
)

int MINIMAL_CHAIN(const DAG &G, array< list<node> > &C) This function computes a minimal chain decomposition of a DAG (an order).

Parameters:
[in] G An input DAG
[out] C $ C[i] $ is a node list reprensenting the chain number $ i $, with $ 0 \le i < p(G) $. The lists are sorted in increasing order: $ \forall i, \forall u,v \in C[i], u \le v \Longleftrightarrow \exists \textrm{ a path } (u,\ldots,v) \textrm{ in }G $.
Returns:
$ p(G) $ the minimal number of chains of the DAG. Dilworth proved that $ p(G)=w(G)$ , that is, it is equal to the size of a maximal antichain. Returns 0 if the input acyclic graph is empty. Returns -1 if error.
Remarks:
A minimal chain decomposition may not be unique. This function returns an arbitrary one.
Precondition:
G is acyclic.
Examples:
dag_example.cpp.

int MINIMAL_CHAIN ( const graph &  G,
node_array< int > &  chain 
)

Parameters:
[in] G An acyclic graph (DAG, order)
[out] chain Contains the chain number for each node of the DAG. $ \forall u \in V, chain[u] $ is the number of the chain to which $ u $ belongs.
Returns:
The size of a minimal chain decomposition of the graph. Returns 0 if the input acyclic graph is empty. Returns -1 if error.
This function implements Dilworth decomposition to compute minimal chain decomposition of an order (DAG).
Precondition:
The input graph G should be acyclic.
Remarks:
A minimal chain decomposition may not be unique. This function returns an arbitrary one.

bool parallel ( node  u,
node  v 
)

Parameters:
[in] u A first node
[in] v A second node
Returns:
True if $ u || v $, i.e., $ \neg(u \le v) \wedge \neg (v \le u) $.
Precondition:
$ u $ and $ v $ belongs to the same DAG. This is a notation from the lattices and order theory
Examples:
dag_example.cpp.

int REGISTER_SATURATION ( const DAG &  G,
int  t,
leda::list< node > &  RS_values,
node_array< node > &  k 
)

Parameters:
[in] G An input DAG
[in] t A register type identifier.
[out] RS_values The list of saturating values. It is proved that there exists an instruction schedule for any underlying processor constraints that make all the saturating values simultaneously alive.
[out] k A valid saturating killing function. If the computed register saturation is equal to RS, then it is proved that there exists a schedule for the input DAG (for any hardware property) that requires RS registers if the killer of each value $ u \in V_{R,t} $ is set to $ k(u^t) $.
Returns:
An approximate register saturation for the DAG.
Precondition:
The set $ V_{R,t} \subseteq V $ of values and the set $ E_{R,t} \subseteq E $ of flow edges should be set. This function implements a heuristics for computing the register saturation of the DAG (computing the optimal register saturation is an NP-complete problem). It consists of computing the maximal register need of a DAG independently of instruction schedules. Our experiments on a large set of DAGs show that our heuristics is optimal in 95% of the cases, and far from the optimal by only one register in 5% of the cases. This concept has been mathematically and experimentally validated in the follwing research article :
Sid Touati. Register Saturation in Instruction Level Parallelism. International Journal of Parallel Programming, Springer-Verlag, Volume 33, Issue 4, August 2005.
Examples:
dag_example.cpp, and RS_example.cpp.

int REGISTER_SATURATION ( const DAG &  G,
int  t,
leda::list< node > &  RS_values 
)

Parameters:
[in] G A DAG
[in] t A register type identifier.
[out] RS_values The list of saturating values of type t. It is proved that there exists an instruction schedule for any underlying processor constraints that make all the saturating values simultaneously alive.
Returns:
An approximate register saturation for the DAG.
Precondition:
The set $ V_{R,t} \subseteq V $ of values and the set $ E_{R,t} \subseteq E $ of flow edges should be set. This function implements a heuristics for computing the register saturation of the DAG (computing the optimal register saturation is an NP-complete problem). It consists of computing the maximal register need of a DAG independently of instruction schedules. Our experiments on a large set of DAGs show that our heuristics is optimal in 95% of the cases, and far from the optimal by only one register in 5% of the cases. This concept has been mathematically and experimentally validated in the follwing research article :
Sid Touati. Register Saturation in Instruction Level Parallelism. International Journal of Parallel Programming, Springer-Verlag, Volume 33, Issue 4, August 2005.

int REGISTER_SATURATION ( const DAG &  G,
leda::list< node > &  RS_values,
node_array< node > &  k 
)

Parameters:
[in] G An input DAG
[out] RS_values The list of saturating values. It is proved that there exists an instruction schedule for any underlying processor constraints that make all the saturating values simultaneously alive.
[out] k A valid saturating killing function. If the computed register saturation is equal to RS, then it is proved that there exists a schedule for the input DAG (for any hardware property) that requires RS registers if the killer of each value $ u \in V_R $ is set to $ k(u) $.
Returns:
An approximate register saturation for the DAG.
Precondition:
The set $ V_R \subseteq V $ of values and the set $ E_R \subseteq E $ of flow edges should be set.

a unique register type exists in the ISA.

Exceptions:
NonUniqueRegisterType This function implements a heuristics for computing the register saturation of the DAG (computing the optimal register saturation is an NP-complete problem). It consists of computing the maximal register need of a DAG independently of instruction schedules. Our experiments on a large set of DAGs show that our heuristics is optimal in 95% of the cases, and far from the optimal by only one register in 5% of the cases. This concept has been mathematically and experimentally validated in the follwing research article :
Sid Touati. Register Saturation in Instruction Level Parallelism. International Journal of Parallel Programming, Springer-Verlag, Volume 33, Issue 4, August 2005.

int REGISTER_SATURATION ( const DAG &  G,
leda::list< node > &  RS_values 
)

Parameters:
[in] G A DAG
[out] RS_values The list of saturating values. It is proved that there exists an instruction schedule for any underlying processor constraints that make all the saturating values simultaneously alive.
Returns:
An approximate register saturation for the DAG.
Precondition:
The set $ V_R \subseteq V $ of values and the set $ E_R \subseteq E $ of flow edges should be set.

a unique register type exists in the ISA.

Exceptions:
NonUniqueRegisterType This function implements a heuristics for computing the register saturation of the DAG (computing the optimal register saturation is an NP-complete problem). It consists of computing the maximal register need of a DAG independently of instruction schedules. Our experiments on a large set of DAGs show that our heuristics is optimal in 95% of the cases, and far from the optimal by only one register in 5% of the cases. This concept has been mathematically and experimentally validated in the follwing research article :
Sid Touati. Register Saturation in Instruction Level Parallelism. International Journal of Parallel Programming, Springer-Verlag, Volume 33, Issue 4, August 2005.

bool retime_ddg ( LOOP &  G  ) 

Computes and applies a valid loop retiming (called also loop shifing).

Parameters:
[in,out] G The loop to retime (modified by the loop retiming)
Returns:
true if a valid retiming has been found.

false if no valid retiming has been found (in case of the presence of nonpositive distance cycle).

Loop retiming consists of the following graph transformation: for each loop statement $ u $, we associate an integer shift $ r(u) $ which means that we delay the operation $ u $ by $ r(u) $ iterations. Then, each statement $ u $ that was representing the operation $ u $ of loop iteration $ i $ represents now the operation $ u $ of loop iteration $ i-r(u) $. The new distance of each arc $ e=(u,v) $ becomes equal to $ \lambda_r(e)=\lambda(e)+r(v)-r(u) $. Such new distance is always nonnegative $ \lambda_r(u)\ge 0, \forall u \in V $.

For more details about loop retiming, please study the excellent research article of Leiserson and Saxe published in Algorithmica 1991 (Retiming asynchronous circuits).

Warning:
If the retiming is not valid, the loop would been modified anywhere.

bool retime_ddg ( LOOP &  G,
LEDA::node_array< int > &  r 
)

Computes and applies a valid loop retiming (called also loop shifing).

Parameters:
[in,out] G The loop to retime (modified by the loop retiming)
[out] r the computed retiming.
Returns:
true if a valid retiming has been found.

false if no valid retiming has been found (in case of the presence of nonpositive distance cycle).

Loop retiming consists of the following graph transformation: for each loop statement $ u $, we associate an integer shift $ r(u) $ which means that we delay the operation $ u $ by $ r(u) $ iterations. Then, each statement $ u $ that was representing the operation $ u $ of loop iteration $ i $ represents now the operation $ u $ of loop iteration $ i-r(u) $. The new distance of each arc $ e=(u,v) $ becomes equal to $ \lambda_r(e)=\lambda(e)+r(v)-r(u) $. Such new distance is always nonnegative $ \lambda_r(u)\ge 0, \forall u \in V $.

For more details about loop retiming, please study the excellent research article of Leiserson and Saxe published in Algorithmica 1991 (Retiming asynchronous circuits).

Warning:
If the retiming is not valid, the loop would been modified anywhere.

edge_type DDG::string_to_edge_type ( const std::string   ) 

Convert a string to an edge_type.

Precondition:
The input string should be one of ("flow", "serial", "antidep", "outputdep, "inputdep")

void unroll ( const LOOP &  L,
LOOP &  unrolled,
int  unroll_degree 
)

Returns an unrolled loop.

Parameters:
[in] L The loop to be considered. Not altered by this function.
[out] unrolled The resulting unrolled loop.
[in] unroll_degree The degree of loop unrolling. If equal to zero, no loop unrolling is performed and the resulting loop is empty.
Remarks:
  • The degree unrolling tells how much loops bodies are duplicated. If the degree of unrolling is equal to 1, the resulting loop contains only one copy of the initial loop.
  • This unrolling function preserves and handles recurrent edges.
Precondition:
Unrolling degree and all dependence distances should be nonnegative. $ \forall u\in V, \lambda(u)\ge 0 $.
Examples:
dag_example.cpp, and loop_example.cpp.

void unroll ( const LOOP &  L,
DAG &  unrolled,
int  unroll_degree 
)

Returns the body of the unrolled loop.

Parameters:
[in] L The loop to be considered. Not altered by this function.
[out] unrolled The resulting DAG (the loop body of the unrolled loop).
[in] unroll_degree The degree of loop unrolling. If equal to zero, no loop unrolling is performed and the resulting DAG is empty.
Remarks:
  • The degree unrolling tells how much loop bodies are duplicated. If the degree of unrolling is equal to 1, the resulting DAG contains only one loop body.
  • This unrolling function preserves and handles recurrent edges.

January 2009, by Sid Touati (Copyright INRIA and University of Versailles)