DDG::DAG

DAG Class Reference

Inheritance diagram for DAG:

LOOP

Detailed Description

This class represents a directed acyclic graph (DAG).

Author:
Sid Touati
It inherits from the LEDA class GRAPH<INFO_NODE, INFO_EDGE>. The attributes of the nodes are of type INFO_NODE, and the attributes of edges are of type INFO_EDGE. The implemented DAG model is described in DAG Model.

For more information about LEDA, please consult http://www.algorithmic-solutions.info/leda_manual

Examples:

dag_example.cpp, and RS_example.cpp.

Definition at line 227 of file DAG.h.


Public Member Functions

Creation


 DAG ()
 Declares an empry DAG.
 DAG (const ARCHITECTURE)
 ~DAG ()
Access Operations


LEDA::set< edge > edges_from_to (node u, node v) const
 Returns the set of all edges from the source node $ u $ to the destination node $ v $.
LEDA::set< edge > edges_from_to (int id_u, int id_v) const
 Returns the set of all edges from the source node to the destination node.
int LongestPath () const
 Returns the value of the longest path of the DAG.
int LongestPath (LEDA::list< node > &nl) const
 Returns the value of the longest path of the DAG.
int LongestPath (list< edge > &el) const
 Returns the value of the longest path of the DAG.
int CriticalPath ()
 This is an alias of the method DAG::LongestPath(). It returns the value of the longest (critical) path.
int CriticalPath (LEDA::list< node > &nl)
 Returns the value of the longest (critical) path.
int CriticalPath (LEDA::list< edge > &el)
 Returns the value of the longest (critical) path.
int LongestPathTo (node) const
 Returns the value of the longest path from the top of the DAG (sources) up to a node given as argument.
int LongestPathFrom (node) const
 Returns the value of the longest path from a node given as argument to the bottom the DAG (sinks).
int ShortestPathTo (node) const
 Returns the value of the shortest path from the top of the DAG (sources) up to a node given as argument.
int ShortestPathFrom (node) const
 Returns the value of the shortest path from a node given as argument to the bottom the DAG (sinks).
int lp (node u, node v) const
 Returns the value of the longest path from a node $ u $ to a node $ v $ given as arguments*.
LEDA::set< node > get_down (node u) const
 Returns the set $ \downarrow u$ (the set of all descending nodes)., see Notation and Definitions on DAGs.
LEDA::set< node > get_up (node u) const
 Returns the set $ \uparrow u $.(the set of all ascenfing nodes), see Notation and Definitions on DAGs.
LEDA::set< node > get_parents (node u) const
 Returns the set $ \Gamma^+_G(u) $ (set of children), see Notation and Definitions on DAGs.
LEDA::set< node > get_children (const node u) const
 Returns the set $ \Gamma^-_G(u) $ (set of parents), see Notation and Definitions on DAGs.
node node_with_id (int i) const
 Returns the node with the integer identifier given as argument.
node node_with_name (std::string name) const
 Returns the node with the name given as argument.
bool is_value (node n) const
 Returns true if the node is an instruction writing into a register (i.e. if it belongs to the $ V_R $ set).
bool is_value (int i, int t) const
 Returns true if the node defined by its indentifier is an instruction writing into a register of type t (i.e. if it belongs to the $ {V_R,t} $ set).
bool is_value (node n, int t) const
 Returns true if the node is an instruction writing into a register of type t (i.e. if it belongs to the $ V_{R,t} $ set).
bool is_value (int i) const
 Returns true if the node defined by its indentifier is an instruction writing into a register (i.e. if it belongs to the $ V_R $ set).
bool is_flow (edge e) const
 Returns true if the edges is a flow dependence (not necessarily through registers).
bool is_flow_reg (edge e) const
 Returns true if the edges is a flow dependence through a register. This is the case of a flow edge having a source writing into a register.
int get_register_type_id (edge e) const
 Returns the register type of a flow edge.
bool is_flow_reg (edge e, int t) const
 Returns true if the edges is a flow dependence through a register of type t. This is the case of a flow edge having a source writing into a register.
DDG::edge_type etype (edge e) const
 Returns the type of the edge $ e $. (flow, serial, antidep, ...).
set< node > get_V_R () const
 Returns the set $ V_R \subseteq V $ of instructions (nodes) writing into registers.
set< node > get_V_R (int t) const
 Returns the set $ V_ {R,t}\subseteq V $ of instructions (nodes) writing into registers of type t (given by its id).
LEDA::list
< REGISTER_TYPES > 		T () const
LEDA::set< edge > get_E_R () const
 Returns the set $ E_R \subseteq E $ of flow dependence edges through registers.
LEDA::set< edge > get_E_R (int t) const
 Returns the set $ E_{R,t} \subseteq E $ of flow dependence edges through registers of type t (given by its id).
LEDA::set< node > get_Sources () const
 Returns the set of nodes which are the sources of the DAG.
LEDA::set< node > get_Targets () const
 Returns the set of nodes which are the targetsof (sinks) of the DAG.
LEDA::set< node > get_Cons (node u) const
 Returns the set of consumers of a node.
LEDA::set< node > get_Cons (node u, int id_regtype) const
 Returns the set of consumers of a node writing inside a register of a given type.
LEDA::set< int > get_Sources_id () const
 Returns the set of nodes identifiers which are the sources of the DAG.
LEDA::set< int > get_Targets_id () const
 Returns the set of nodes identifiers which are the targetsof (sinks) the DAG.
LEDA::set< int > all_nodes_id ()
 Returns the set of nodes identifiers.
int source_id (edge e) const
 Returns the integer identifier of the edge source.
int target_id (edge e) const
 Returns the integer identifier of the edge target.
ARCHITECTURE get_ISA () const
 Returns the ARCHITECTURE of the DAG.
int delta (edge e) const
 Returns the latency $ \delta(e) $ of the edge $ e $.
int latency (node n) const
 Returns the latency $ latency(n) $ of the generic instruction of the node $ n $.
int delta_r (node n) const
 Returns the reading latency $ \delta_r(n) $ of the node $ n $.
int delta_r (int idn) const
 Returns the reading latency $ \delta_r(idn) $ of the node given by its id.
int delta_w (node n) const
 Returns the writing latency $ \delta_w(n) $ of the node $ n $.
int delta_w (int idn) const
 Returns the writing latency $ \delta_w(idn) $ of the node given by its id.
int delta_w (node n, int regtype_id) const
 Returns the writing latency $ \delta_{w,t}(n) $ of the node $ n $.
int delta_w (int idn, int regtype_id) const
 Returns the writing latency $ \delta_{w,t}(idn) $ of the node given by its id.
int id (node n) const
 Returns the integer identifier of the node $ n $.
INSTRUCTIONS_TYPES instruction_type (node n) const
 Returns an INSTRUCTIONS_TYPES object attached to the node $ n $.
INSTRUCTIONS_TYPES instruction_type (int id) const
 Returns an INSTRUCTIONS_TYPES object attached to the node given by its $ id $.
std::string get_string_attribute (node n) const
 Returns the textual attribute of the node $ n $.
const INFO_NODE & inf (node v) const
 Returns the information of node $ v $.
const INFO_NODE & operator[] (node v) const
 Returns a reference to the information of $ v $.
INFO_NODE & operator[] (node v)
const INFO_EDGE & inf (edge e) const
 Returns the information of node $ e $.
const INFO_EDGE & operator[] (edge e) const
 Returns a reference to the information of $ e $.
INFO_EDGE & operator[] (edge e)
int outdeg (node v) const
 Returns the number of edges leaving to node $ v $.
int indeg (node v) const
 Returns the number of edges entering $ v $.
int degree (node v) const
 Returns $ outdeg(v) + indeg(v) $.
node source (edge e) const
 Returns the source node of edge $ e $.
node target (edge e) const
 Returns the target node of edge $ e $.
node opposite (node v, edge e) const
 Returns $ target(e) $ if $ v = source(e) $ and $ source(e) $ otherwise.
node opposite (edge e, node v) const
 Returns $ target(e) $ if $ v = source(e) $ and $ source(e) $ otherwise.
int number_of_nodes () const
 Returns the number of nodes in the DAG.
int number_of_edges () const
 Returns the number of edges in the DAG.
const LEDA::list
< node > & 		all_nodes () const
 Returns the list of all nodes in the DAG.
const LEDA::list
< edge > & 		all_edges () const
 Returns the list of all edges in the DAG.
LEDA::list< edge > out_edges (node v) const
 Returns the list of edges leaving the node $ v $.
LEDA::list< edge > in_edges (node v) const
 Returns the list of edges entering the node $ v $.
node first_node () const
 Returns the first node in the DAG.
node last_node () const
 Returns the last node in the DAG.
node choose_node () const
 Returns a random node of the DAG (nil if empty).
node succ_node (node v) const
 Returns the successor of node $ v $ (nil if it does not exist).
node pred_node (node v) const
 Returns the predecessor of node $ v $ (nil if it does not exist).
edge first_edge () const
 Returns the first edge in the DAG.
edge last_edge () const
 Returns the last edge in the DAG.
edge choose_edge () const
 Returns a random edge of the DAG (nil if empty).
edge succ_edge (edge e) const
 Returns the successor of edge $ e $ (nil if it does not exist).
edge pred_edge (edge e) const
 Returns the predecessor of edge $ e $ (nil if it does not exist).
bool empty () const
 Returns true if the DAG is empty.
bool member (node v) const
 Returns true if the node $ v $ belongs to the DAG.
bool member (edge e) const
 Returns true if the edge $ e $ belongs to the DAG.
bool is_hidden (edge e) const
 Returns true if $ e $ is hidden, false otherwise. See DAG::hide_edge(edge e).
bool is_hidden (node v) const
 Returns true if $ v $ is hidden, false otherwise. See DAG::hide_node(node v).
LEDA::list< edge > hidden_edges () const
 Returns the list of all hidden edges.
LEDA::list< node > hidden_nodes () const
 Returns the list of all hidden nodes.
int max_delta (node u, node v) const
 Returns the maximal edge latency between to nodes, i.e., $ \max_{e=(u,v)} \delta(e) $.
int max_delta (int u, int v) const
 Returns the maximal edge latency between to nodes (given by their ids), i.e., $ \max_{e=(u,v)} \delta(e) $.
int min_delta (node u, node v) const
 Returns the minimal edge latency between to nodes, i.e., $ \min_{e=(u,v)} \delta(e) $.
int min_delta (int u, int v) const
 Returns the minimal edge latency between to nodes (given by their ids), i.e., $ \min_{e=(u,v)} \delta(e) $.
INSTRUCTIONS_TYPES search_instruction_type (const std::string opcode) const
 Looks for the instruction type (inside the DAG ISA) that has the opcode given as argument. If not found, it returns an INSTRUCTIONS_TYPES object with opcode_id equal to -1.
INSTRUCTIONS_TYPES search_instruction_type (int opcode_id) const
 Looks for the instruction type (inside the DAG ISA) that has the opcode id given as argument. Returns NULL if not found. If not found, it returns an INSTRUCTIONS_TYPES object with opcode_id equal to -1.
bool check ()
 A simple check method that returns true if the DAG object seems ok. False otherwise.
bool check (int regtype_id)
 A simple check method that returns true if the DAG object seems ok for the specified register type. False otherwise.
NodeFlag node_flag (node n) const
 Returns the node flag of n.
Update Operations
Returns the list of register types of the ISA of the DAG. The ISA object should be attached to the DAG before calling this function. See the DAG construtor method, or the DDG:DAG:set_ISA method. LEDA::list<REGISTER_TYPES> T() const ;

/**

void clear ()
 Empty the DAG.
int new_node (int it_id)
 Creates a new node.
int new_node (int it_id, std::string text_inst)
 Creates a new node.
int new_node (int it_id, int n_id)
 Creates a new node.
int new_node (int it_id, int n_id, std::string text_inst)
 Creates a new node.
void del_node (node)
 Deletes the node given as argument.
void del_node (int node_id)
 Deletes the node whose id is given as argument.
edge new_edge (int s, int t, INFO_EDGE ie)
 Creates a new edge.
edge new_edge (node s, node t, INFO_EDGE ie)
 Creates a new edge.
void del_edge (edge e)
 Deletes the edge given as argument.
void copy (const DAG &G2)
 Duplicates a DAG.
void copy (const DAG &G2, node_map< node > &mn, edge_map< edge > &me)
 Duplicates a DAG.
void get_loop_body (const LOOP &G2, node_map< node > &mn, edge_map< edge > &me)
 Retrieves a loop body.
void get_loop_body (const LOOP &G2)
 Retrieves a loop body.
void build_internal_structures ()
 Build internal data structures for the DAG.
void set_ISA (ARCHITECTURE isa)
 Sets the set of generic instruction types (ISA) encapsulated inside the DAG.
void set_delta (edge e, int l)
 Sets a latency $ \delta(e) $ to the edge $ e $.
void set_instruction_type (node n, int it_id)
 Sets an INSTRUCTIONS_TYPES object (given by its opcode id) attached to the node $ n $.
void set_string_attribute (node u, std::string inst_text)
 Sets a textual attribute to the node $ n $. For instance, this textual attribute can be used to associate the textual code of the instruction.
void set_etype (edge e, DDG::edge_type et)
 Sets an edge type (flow, serial, antidep, etc.).
void hide_edge (edge e)
 Removes temporarily the edge $ e $. The edge can be restored by DAG::restore_edge(edge e).
void hide_edges (const LEDA::list< edge > &el)
 Hides all edges in the list el.
void restore_edge (edge e)
 Restores the hidden edge $ e $ .
void restore_edges (const LEDA::list< edge > &el)
 Restores all edges in the list el.
void restore_all_edges ()
 Restores all hidden edges.
void hide_node (node v)
 Removes temporarily the node $ v $. Leaving and entering edges are also hidden. The node can be restored by DAG::restore_node(node v).
void hide_nodes (const LEDA::list< node > &nl)
 Hides all nodes in the list nl.
void hide_node (node v, LEDA::list< edge > &h_edges)
 Removes temporarily the node $ v $. Leaving and entering edges are also hidden. The node can be restored by DAG::restore_node(node n).
void restore_node (node v)
 Restores the hidden node $ v $. Note that no edge adjacent to v that was hidden by G.hide_node(v) is restored by this operation.
void restore_all_nodes ()
 Restores all hidden nodes. Note that no adjacent edges to the hidden nodes are restored by this operation.
void del_all_edges ()
 Deletes all edges from the DAG.
void move_edge (edge e, node v, node w)
 Moves the edge $ e $ to source $ v $ and target $ w $.
void set_node_flag (node n, const NodeFlag theValue)
 Set the flag of the node n.
Import and Export Methods


void write_to_gl (const char *filename) const
 Exports the DAG to a gl file.
void write_to_gl (const char *filename, int regtype_id) const
 Exports the DAG to a gl file.
bool read_from_gl (const char *filename)
 Imports the DAG from a gl file when a unique register type exists in the architecture.
bool read_from_gl (const char *filename, int regtype_id)
 Imports the DAG from a gl file when multiple registers types exist in the architecture. This function asks to fix which register type to consider.
void write_to_vcg (const char *filename) const
 Exports the DAG to a vcg file to in order to be visualized with the xvcg tool. The user can navigate using vcg on all DDG attributes (types of edges, opcodes, etc.).
void write_to_vcg (const char *filename, int t) const
 Exports the DAG to a vcg file to in order to be visualized with the xvcg tool while considering one register type. The user can navigate using vcg on all DDG attributes (types of edges, opcodes, etc.) For more information about xvcg, see http://rw4.cs.uni-sb.de/users/sander/html/gsvcg1.html.
void write_to_xml (const char *filename)
 Exports the DAG to an XML description.
bool read_from_xml (const char *filename)
 Imports the DAG from its xml description.

Protected Attributes

unsigned int cpt_nodes
LEDA::d_array< int,
LEDA::set< node > > 		V_R
LEDA::d_array< int,
LEDA::set< edge > > 		E_R
ARCHITECTURE ISA
node_array< set< node > > down
node_array< set< node > > up
node_array< int > longuest_path_from
node_array< int > longuest_path_to
node_matrix< int > lp_array
node_array< int > shortest_path_from
node_array< int > shortest_path_to
set< node > Sources
set< node > Targets
map2< node, int, set
< node > > 		Cons
LEDA::map< int, node > node_index_table

Constructor & Destructor Documentation

DAG (  ) 

Declares an empry DAG.

Default constructor.

It creates an empty DAG. A default architecture (ISA) is assumed, but the user may attach another ISA to the DAG. See DDG::DAG::set_ISA

DAG ( const   ARCHITECTURE  ) 

Constructs a DAG after reading the generic description of the architecture (ISA).

Parameters:
[in] ARCHITECTURE The ARCHITECTURE (ISA) object containing the ISA description.

Member Function Documentation

LEDA::set<edge> edges_from_to ( int  id_u,
int  id_v 
) const

Returns the set of all edges from the source node to the destination node.

Parameters:
[in] id_u The integer identifier of the source node.
[in] id_v The integer identifier of the destination node.

int LongestPath ( LEDA::list< node > &  nl  )  const

Returns the value of the longest path of the DAG.

Parameters:
[out] nl Contains the list of nodes belonging to the computed longest path.
Warning:
Despite the unicity of its value, the longest path in a DAG may not be unique.

int LongestPath ( list< edge > &  el  )  const

Returns the value of the longest path of the DAG.

Parameters:
[out] el Contains the list of edges belonging to the computed longest path.
Warning:
Despite the unicity of its value, the longest path in a DAG may not be unique.

int CriticalPath ( LEDA::list< node > &  nl  ) 

Returns the value of the longest (critical) path.

Parameters:
[out] nl Contains the list of nodes belonging to the computed longest path.
Warning:
The longest path in a DAG may not be unique

int CriticalPath ( LEDA::list< edge > &  el  ) 

Returns the value of the longest (critical) path.

Parameters:
[out] el Contains the list of edges belonging to the computed longest path.
Warning:
The longest path in a DAG may not be unique

int lp ( node  u,
node  v 
) const

Returns the value of the longest path from a node $ u $ to a node $ v $ given as arguments*.

Precondition:
Such path exists

node node_with_id ( int  i  )  const

Returns the node with the integer identifier given as argument.

Exceptions:
IllegalAccessNode If the node id does not exist, or if the node is hidden, then an exception of type DDG:IllegalAccessNode is thrown.

Referenced by DAG::max_delta(), and DAG::min_delta().

node node_with_name ( std::string  name  )  const

Returns the node with the name given as argument.

Exceptions:
IllegalAccessNode If the node id does not exist, or if the node is hidden.

bool is_value ( node  n  )  const

Returns true if the node is an instruction writing into a register (i.e. if it belongs to the $ V_R $ set).

Precondition:
There is a unique register type in the architecture
Exceptions:
NonUniqueRegisterType 

bool is_value ( int  i  )  const

Returns true if the node defined by its indentifier is an instruction writing into a register (i.e. if it belongs to the $ V_R $ set).

Precondition:
There is a unique register type in the architecture
Exceptions:
NonUniqueRegisterType 

bool is_flow_reg ( edge  e  )  const [inline]

Returns true if the edges is a flow dependence through a register. This is the case of a flow edge having a source writing into a register.

Precondition:
There is a unique register type in the architecture
Exceptions:
NonUniqueRegisterType 

Definition at line 383 of file DAG.h.

References ARCHITECTURE::get_the_unique_register_type_id(), DAG::inf(), INFO_EDGE::is_flow_reg(), and DAG::ISA.

int get_register_type_id ( edge  e  )  const

Returns the register type of a flow edge.

Precondition:
The edge should be a flow through register (flowdep_reg)

set<node> get_V_R (  )  const [inline]

Returns the set $ V_R \subseteq V $ of instructions (nodes) writing into registers.

Precondition:
a unique register type should exist in the architecture
Exceptions:
NonUniqueRegisterType 
Examples:
dag_example.cpp, loop_example.cpp, and RS_example.cpp.

Definition at line 408 of file DAG.h.

References ARCHITECTURE::get_the_unique_register_type_id(), DAG::ISA, and DAG::V_R.

set<node> get_V_R ( int  t  )  const [inline]

Returns the set $ V_ {R,t}\subseteq V $ of instructions (nodes) writing into registers of type t (given by its id).

Exceptions:
BadRegType 

Definition at line 414 of file DAG.h.

References ARCHITECTURE::exist_register_type_id(), DAG::ISA, and DAG::V_R.

LEDA::set<edge> get_E_R (  )  const [inline]

Returns the set $ E_R \subseteq E $ of flow dependence edges through registers.

Precondition:
A unique register type must exist.
Exceptions:
NonUniqueRegisterType 
Examples:
loop_example.cpp.

Definition at line 426 of file DAG.h.

References DAG::E_R, ARCHITECTURE::get_the_unique_register_type_id(), and DAG::ISA.

LEDA::set<edge> get_E_R ( int  t  )  const [inline]

Returns the set $ E_{R,t} \subseteq E $ of flow dependence edges through registers of type t (given by its id).

Exceptions:
BadRegType 

Definition at line 432 of file DAG.h.

References DAG::E_R, ARCHITECTURE::exist_register_type_id(), and DAG::ISA.

LEDA::set<node> get_Cons ( node  u  )  const [inline]

Returns the set of consumers of a node.

Precondition:
A unique register type should exist in the architecture.
Exceptions:
NonUniqueRegisterType 

Definition at line 450 of file DAG.h.

References DAG::Cons, ARCHITECTURE::get_the_unique_register_type_id(), and DAG::ISA.

LEDA::set<node> get_Cons ( node  u,
int  id_regtype 
) const [inline]

Returns the set of consumers of a node writing inside a register of a given type.

Precondition:
id_regtype is an id of register type in the architetcure
Exceptions:
BadRegType 

Definition at line 458 of file DAG.h.

References DAG::Cons, ARCHITECTURE::exist_register_type_id(), and DAG::ISA.

int delta_w ( node  n  )  const

Returns the writing latency $ \delta_w(n) $ of the node $ n $.

Precondition:
a unique register type should exist in the architecture
Examples:
dag_example.cpp, and loop_example.cpp.

int delta_w ( int  idn  )  const

Returns the writing latency $ \delta_w(idn) $ of the node given by its id.

Precondition:
a unique register type should exist in the architecture

int new_node ( int  it_id  ) 

Creates a new node.

Parameters:
[in] it_id The id of the INSTRUCTIONS_TYPES object describing the generic instruction of the node
Returns:
The integer node identifier.
Remarks:
This method assigns a unique inter identifier for the created node.
See also DAG::build_internal_structures().
Examples:
dag_example.cpp.

int new_node ( int  it_id,
std::string  text_inst 
)

Creates a new node.

Parameters:
[in] it_id The id of the INSTRUCTIONS_TYPES object describing the generic instruction of the node
[in] text_inst A textual attribute of the instruction
Returns:
The integer node identifier.
Remarks:
This method assigns a unique inter identifier for the created node.
See also DAG::build_internal_structures().

int new_node ( int  it_id,
int  n_id 
)

Creates a new node.

Parameters:
[in] it_id The id of the INSTRUCTIONS_TYPES object describing the generic instruction of the node
[in] n_id A unique id for the node to create
Returns:
The integer node identifier. Returns -1 if the there exists an node with the input id.
Exceptions:
NonUniqueNodeID if the input node id already exists
Remarks:
This method creates a node with an identifier given as input.
Precondition:
n_id is positive
See also DAG::build_internal_structures().

int new_node ( int  it_id,
int  n_id,
std::string  text_inst 
)

Creates a new node.

Parameters:
[in] it_id The id of the INSTRUCTIONS_TYPES object describing the generic instruction of the node
[in] n_id A unique id for the node to create
[in] text_inst A textual attribute of the instruction
Returns:
The integer node identifier.
Exceptions:
NonUniqueNodeID if the input node id already exists
Remarks:
This method creates a node with an identifier given as input.
Precondition:
n_id is positive
See also DAG::build_internal_structures().

void del_node ( node   ) 

Deletes the node given as argument.

All the edges incident to the deleted node are removed from the DAG too.

void del_node ( int  node_id  ) 

Deletes the node whose id is given as argument.

All the edges incident to the deleted node are removed from the DAG too.

See also DAG::build_internal_structures().

edge new_edge ( int  s,
int  t,
INFO_EDGE  ie 
)

Creates a new edge.

It takes three arguments. If flow dependence, the inserted edge is added to the set $ E_R $.

Parameters:
[in] s The integer identifier of the source node.
[in] t The integer identifier of the destination node.
[in] ie The INFO_EDGE object describing the edge attribute. See also DAG::build_internal_structures().
Examples:
dag_example.cpp.

edge new_edge ( node  s,
node  t,
INFO_EDGE  ie 
)

Creates a new edge.

It takes three arguments. If flow dependence, the inserted edge is added to the set $ E_R $.

Parameters:
[in] s The source node.
[in] t The destination node.
[in] ie The INFO_EDGE object describing the edge attribute. See also DAG::build_internal_structures().

void copy ( const DAG &  G2  ) 

Duplicates a DAG.

Parameters:
[in] G2 The current DAG object will contain a duplicated copy of G2. This method will keep the same node ids, same edge and node information, etc. The internal consistency of the duplicated DAG is guaranteed.
Remarks:
DAG::build_internal_structures() is called inside this method.
Examples:
dag_example.cpp.

void copy ( const DAG &  G2,
node_map< node > &  mn,
edge_map< edge > &  me 
)

Duplicates a DAG.

Parameters:
[in] G2 The current DAG object will contain a duplicated copy of G2. This method will keep the same node ids, same edge and node information, etc. The internal consistency of the duplicated DAG is guaranteed.
[out] mn mn is a mapping from the set of nodes of G2 to the set of nodes of the current DAG. $ \forall u\in G_2, mn[u] $ contains the node belonging to the current DAG corresponding to its original copy $ u \in G_2 $.
[out] me me is a mapping from the set of edges of G2 to the set of edges of the current DAG. $ \forall e \in G_2, me[e] $ contains the edge belonging to the current DAG corresponding to its original copy $ e \in G_2 $.
Remarks:
DAG::build_internal_structures() is called inside this method.

void get_loop_body ( const LOOP &  G2,
node_map< node > &  mn,
edge_map< edge > &  me 
)

Retrieves a loop body.

Parameters:
[in] G2 The current DAG object will contain the loop body of G2. This method will keep the same node ids, same edge and node information, etc. The internal consistency of the DAG is guaranteed.
[out] mn mn is a mapping from the set of nodes of G2 to the set of nodes of the current DAG. $ \forall u\in G_2, mn[u] $ contains the node belonging to the current DAG corresponding to its original copy $ u \in G_2 $.
[out] me me is a mapping from the set of edges of G2 to the set of edges of the current DAG. $ \forall e \in G_2, me[e] $ contains the edge belonging to the current DAG corresponding to its original copy $ e \in G_2 $.
Remarks:
DAG::build_internal_structures() is called inside this method. The loop body contains the set of all nodes, but the set of edges contains only the edges with null distance: $ \forall e \textrm{ in the loop body}, \lambda(e)=0 $.

void get_loop_body ( const LOOP &  G2  ) 

Retrieves a loop body.

Parameters:
[in] G2 The current DAG object will contain the loop body of G2. This method will keep the same node ids, same edge and node information, etc. The internal consistency of the duplicated DAG is guaranteed.
Remarks:
DAG::build_internal_structures() is called inside this method. The loop body contains the set of all nodes, but the set of edges contains only the edges with null distance: $ \forall e \textrm{ in the loop body}, \lambda(e)=0 $.

void build_internal_structures (  ) 

Build internal data structures for the DAG.

For internal information consistency, this function member should be called after update operations such as DAG::new_node(INSTRUCTIONS_TYPES it), DAG::new_edge(INFO_EDGE), etc. This method compute some internal information returned by other methods (the set $ V_R $, the set of consumers per value, all pair shortest paths, transitive closure, set of descendant and ascendant nodes, set of values, etc.). If the DAG is not modified after calling build_internal_structures(), all its internal information remain consistent.

Remarks:
For efficiency, the user can group series of update operations before ultimately calling build_internal_structures()
Precondition:
The graph should not contain a circuit.

Reimplemented in LOOP.

Examples:
dag_example.cpp.

void set_ISA ( ARCHITECTURE  isa  )  [inline]

Sets the set of generic instruction types (ISA) encapsulated inside the DAG.

Parameters:
[in] isa An ARCHITECTURE object describing a user-defined ISA.
Warning:
It is better to clear the DAG before changing its ISA. If the ISA of a non empty DAG is modified on-the-fly, the successive behavior of the DAG object would be indefined.

Definition at line 886 of file DAG.h.

void set_string_attribute ( node  u,
std::string  inst_text 
)

Sets a textual attribute to the node $ n $. For instance, this textual attribute can be used to associate the textual code of the instruction.

Remarks:
  • Currently, a textual attribute is a single textual line. Hence, it should not contain the newline character \n. If they exist, the current implementation replaces them by white spaces.
  • Double quotes characters " should be specialized. They should be written as \" inside the string attribute.

void hide_edge ( edge  e  ) 

Removes temporarily the edge $ e $. The edge can be restored by DAG::restore_edge(edge e).

Remarks:
A hidden edge does no longer belong to the list of graph edges

void hide_edges ( const LEDA::list< edge > &  el  ) 

Hides all edges in the list el.

Remarks:
A hidden edge does no longer belong to the list of graph edges

void restore_edge ( edge  e  ) 

Restores the hidden edge $ e $ .

Warning:
If an endpoint of $ e $ is hidden, an exception occurs.

void restore_edges ( const LEDA::list< edge > &  el  ) 

Restores all edges in the list el.

Warning:
If an endpoint of an edge is hidden, an exception occurs.

void restore_all_edges (  ) 

Restores all hidden edges.

Warning:
If an endpoint of an edge is hidden, an exception occurs.
Examples:
dag_example.cpp, and loop_example.cpp.

void hide_node ( node  v  ) 

Removes temporarily the node $ v $. Leaving and entering edges are also hidden. The node can be restored by DAG::restore_node(node v).

Remarks:
A hidden node does no longer belong to the list of graph nodes
Examples:
dag_example.cpp, and loop_example.cpp.

void hide_nodes ( const LEDA::list< node > &  nl  ) 

Hides all nodes in the list nl.

Remarks:
A hidden node does no longer belong to the list of graph nodes

void hide_node ( node  v,
LEDA::list< edge > &  h_edges 
)

Removes temporarily the node $ v $. Leaving and entering edges are also hidden. The node can be restored by DAG::restore_node(node n).

Parameters:
[in] v the node to hide.
[out] h_edges the list of leaving and entering edges hidden in consequence of hiding the node $ v $.
Remarks:
A hidden node does no longer belong to the list of graph nodes

void del_all_edges (  ) 

Deletes all edges from the DAG.

See also DAG::empty();

void write_to_gl ( const char *  filename  )  const

Exports the DAG to a gl file.

Deprecated:
Parameters:
[in] filename the file name of the DDG in gl format
Remarks:
if multiple registers types exist in the architecture, then the output gl file will consider them as the same register type, because the current gl format does not support multiple register files.

Reimplemented in LOOP.

void write_to_gl ( const char *  filename,
int  regtype_id 
) const

Exports the DAG to a gl file.

Deprecated:
Parameters:
[in] filename the file name of the DDG in gl format
[in] regtype_id An id of a register type to consider for the flow_reg dependances in the gl file. Only flow edges through registers of type regtype_id will be output as flow_reg. Other flow of other register types are considered as serial.

Reimplemented in LOOP.

bool read_from_gl ( const char *  filename  ) 

Imports the DAG from a gl file when a unique register type exists in the architecture.

Deprecated:
Parameters:
[in] filename the file name of the DDG in gl format
Returns:
true if OK.
Remarks:
  • To get the DAG from a cyclic data dependence graph, all edges with non null distances are ignored. That is, only the loop body is considered when importing a cyclic data dependence graph from a gl file.

Exceptions:
BadIODDG If an IO error occurs (corrupted or non present input files for instance), an exception object of type DDG::BadIODDG is thrown
Precondition:
Before reading a DAG from a gl file, it is assumed that the ISA of the DAG defines all the opcodes ids of the nodes as present in the gl file. Also, it is assumed that the ISA has a unique register type (this is a restriction of the gl format). The constructor DDG::DAG(ARCHITECTURE) defines a DAG with a user defined ISA, otherwise a default ISA is assumed, see ISA_xml.

Reimplemented in LOOP.

bool read_from_gl ( const char *  filename,
int  regtype_id 
)

Imports the DAG from a gl file when multiple registers types exist in the architecture. This function asks to fix which register type to consider.

Deprecated:
Parameters:
[in] filename the file name of the DDG in gl format
[in] regtype_id The id of the register type to consider for flow_reg dependances.
Returns:
true if OK.
Remarks:
  • To get the DAG from a cyclic data dependence graph, all edges with non null distances are ignored. That is, only the loop body is considered when importing a cyclic data dependence graph from a gl file.

Exceptions:
BadIODDG If an IO error occurs (corrupted or non present input files for instance), an exception object of type DDG::BadIODDG is thrown
Precondition:
Before reading a DAG from a gl file, it is assumed that the ISA of the DAG defines all the opcodes ids of the nodes as present in the gl file. The constructor DDG::DAG(ARCHITECTURE) defines a DAG with a user defined ISA, otherwise a default ISA is assumed, see User Defined Instruction Set Architectures (XML format).

Reimplemented in LOOP.

void write_to_vcg ( const char *  filename  )  const

Exports the DAG to a vcg file to in order to be visualized with the xvcg tool. The user can navigate using vcg on all DDG attributes (types of edges, opcodes, etc.).

Parameters:
[in] filename the file name of the DDG in vcg format For more information about xvcg, see http://rw4.cs.uni-sb.de/users/sander/html/gsvcg1.html

Reimplemented in LOOP.

Examples:
dag_example.cpp.

void write_to_vcg ( const char *  filename,
int  t 
) const

Exports the DAG to a vcg file to in order to be visualized with the xvcg tool while considering one register type. The user can navigate using vcg on all DDG attributes (types of edges, opcodes, etc.) For more information about xvcg, see http://rw4.cs.uni-sb.de/users/sander/html/gsvcg1.html.

Parameters:
[in] filename the file name of the DDG in vcg format
[in] t the id of the considered register type

Reimplemented in LOOP.

void write_to_xml ( const char *  filename  ) 

Exports the DAG to an XML description.

All DDG attributes are included into this XML graph format.

bool read_from_xml ( const char *  filename  ) 

Imports the DAG from its xml description.

Returns:
True if OK. False if problem.

Reimplemented in LOOP.

Examples:
dag_example.cpp, and RS_example.cpp.

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