Control node visitors

Collaboration diagram for Control node visitors:

Macros
#define	CONTROL_MAP(ctl, code, c, list)
	Macro to walk through all the controls reachable from a given control node of an unstructured. More...
#define	UNSTRUCTURED_CONTROL_MAP(c, u, l, code)
	Walk through all the controls of un unstructured. More...
#define	FORWARD_CONTROL_MAP(ctl, code, c, list)
	Walk through all the controls forward-reachable from a given control node of an unstructured. More...
#define	BACKWARD_CONTROL_MAP(ctl, code, c, list)
	Walk through all the controls backward-reachable from a given control node of an unstructured. More...
#define	WIDE_FORWARD_CONTROL_MAP(ctl, code, c, list)
	Walk through all the controls backward-reachable from a given control node of an unstructured. More...
#define	GENERIC_CONTROL_MAP(get_controls, ctl, code, c, list)
	The control node visiting engine. More...
#define	CONTROL_MAP(ctl, code, c, list)
	Macro to walk through all the controls reachable from a given control node of an unstructured. More...
#define	UNSTRUCTURED_CONTROL_MAP(c, u, l, code)
	Walk through all the controls of un unstructured. More...
#define	FORWARD_CONTROL_MAP(ctl, code, c, list)
	Walk through all the controls forward-reachable from a given control node of an unstructured. More...
#define	BACKWARD_CONTROL_MAP(ctl, code, c, list)
	Walk through all the controls backward-reachable from a given control node of an unstructured. More...
#define	WIDE_FORWARD_CONTROL_MAP(ctl, code, c, list)
	Walk through all the controls backward-reachable from a given control node of an unstructured. More...
#define	GENERIC_CONTROL_MAP(get_controls, ctl, code, c, list)
	The control node visiting engine. More...

Functions
void	control_map_get_blocs (control c, list *l)
	Build recursively the list of all controls reachable from a control of an unstructured. More...
void	find_a_control_path (control b, control e, list *pp, list *vp, int dir)
	Build recursively a control path from b to e. More...
void	backward_control_map_get_blocs (c, l)
	Build recursively the list of all controls backward-reachable from a control of an unstructured. More...
void	backward_control_map_get_blocs_but (control c, control f, list *l)
	Transitive closure of c's predecessors, but for control f. More...
void	forward_control_map_get_blocs (c, l)
	Build recursively the list of all controls forward-reachable from a control of an unstructured. More...
void	forward_control_map_get_blocs_but (control c, control f, list *l)
	Transitive closure of c's successors, but for control f. More...
void	wide_forward_control_map_get_blocs (c, l)
	Same as above, but follows successors by minimal path lengths. More...

Detailed Description

Macro Definition Documentation

BACKWARD_CONTROL_MAP [1/2]

#define BACKWARD_CONTROL_MAP	(		ctl,
			code,
			c,
			list
	)

Value:

  do {                                                                  \
    GENERIC_CONTROL_MAP( backward_control_map_get_blocs, ctl, code, c, list ) \
    } while(0)

Walk through all the controls backward-reachable from a given control node of an unstructured.

Reachability is defined by predecessor-only relation (i.e. the control flow graph is seen as directed)

Parameters

ctl	is a name of a control node variable that is declared inside this macro and is used by the following code to access the visited control node
code	is the actions to execute on the visited control node
c	is a control node to start visiting with
list	is a list that will store the visited control nodes. It is used mainly for this macro to avoid visiting twice a node. The simple usage is to give a list variable initialized to NIL. A nice side effect is that it will contain the list of all the backward-reachable control nodes. Do not forget to free this list afterwards. Another classical usage is to give to the macro a list with a list of nodes to avoid visiting.

Definition at line 2167 of file ri-util-local.h.

BACKWARD_CONTROL_MAP [2/2]

#define BACKWARD_CONTROL_MAP	(		ctl,
			code,
			c,
			list
	)

Value:

  do {                                                                  \
    GENERIC_CONTROL_MAP( backward_control_map_get_blocs, ctl, code, c, list ) \
    } while(0)

Walk through all the controls backward-reachable from a given control node of an unstructured.

Reachability is defined by predecessor-only relation (i.e. the control flow graph is seen as directed)

Parameters

ctl	is a name of a control node variable that is declared inside this macro and is used by the following code to access the visited control node
code	is the actions to execute on the visited control node
c	is a control node to start visiting with
list	is a list that will store the visited control nodes. It is used mainly for this macro to avoid visiting twice a node. The simple usage is to give a list variable initialized to NIL. A nice side effect is that it will contain the list of all the backward-reachable control nodes. Do not forget to free this list afterwards. Another classical usage is to give to the macro a list with a list of nodes to avoid visiting.

Definition at line 2175 of file ri-util.h.

CONTROL_MAP [1/2]

#define CONTROL_MAP	(		ctl,
			code,
			c,
			list
	)

Value:

  do {                                                                  \
    GENERIC_CONTROL_MAP( control_map_get_blocs, ctl, code, c, list )    \
      } while(0)

Macro to walk through all the controls reachable from a given control node of an unstructured.

Reachability is defined by successors and predecessors (i.e. the control flow graph is seen as non-directed)

Parameters

ctl	is a name of a control node variable that is declared inside this macro and is used by the following code to access the visited control node
code	is the actions to execute on the visited control node
c	is a control node to start visiting with
list	is a list that will store the visited control nodes. It is used mainly for this macro to avoid visiting twice a node. The simple usage is to give a list variable initialized to NIL. A nice side effect is that it will contain the list of all the reachable control nodes. Do not forget to free this list afterwards. Another classical usage is to give to the macro a list with a list of nodes to avoid visiting.

Definition at line 2071 of file ri-util-local.h.

CONTROL_MAP [2/2]

#define CONTROL_MAP	(		ctl,
			code,
			c,
			list
	)

Value:

  do {                                                                  \
    GENERIC_CONTROL_MAP( control_map_get_blocs, ctl, code, c, list )    \
      } while(0)

Macro to walk through all the controls reachable from a given control node of an unstructured.

Reachability is defined by successors and predecessors (i.e. the control flow graph is seen as non-directed)

Parameters

ctl	is a name of a control node variable that is declared inside this macro and is used by the following code to access the visited control node
code	is the actions to execute on the visited control node
c	is a control node to start visiting with
list	is a list that will store the visited control nodes. It is used mainly for this macro to avoid visiting twice a node. The simple usage is to give a list variable initialized to NIL. A nice side effect is that it will contain the list of all the reachable control nodes. Do not forget to free this list afterwards. Another classical usage is to give to the macro a list with a list of nodes to avoid visiting.

Definition at line 2079 of file ri-util.h.

FORWARD_CONTROL_MAP [1/2]

#define FORWARD_CONTROL_MAP	(		ctl,
			code,
			c,
			list
	)

Value:

  do {                                                                  \
    GENERIC_CONTROL_MAP( forward_control_map_get_blocs, ctl, code, c, list ) \
      } while(0)

Walk through all the controls forward-reachable from a given control node of an unstructured.

Reachability is defined by successor-only relation (i.e. the control flow graph is seen as directed)

Parameters

ctl	is a name of a control node variable that is declared inside this macro and is used by the following code to access the visited control node
code	is the actions to execute on the visited control node
c	is a control node to start visiting with
list	is a list that will store the visited control nodes. It is used mainly for this macro to avoid visiting twice a node. The simple usage is to give a list variable initialized to NIL. A nice side effect is that it will contain the list of all the forward-reachable control nodes. Do not forget to free this list afterwards. Another classical usage is to give to the macro a list with a list of nodes to avoid visiting.

Definition at line 2139 of file ri-util-local.h.

FORWARD_CONTROL_MAP [2/2]

#define FORWARD_CONTROL_MAP	(		ctl,
			code,
			c,
			list
	)

Value:

  do {                                                                  \
    GENERIC_CONTROL_MAP( forward_control_map_get_blocs, ctl, code, c, list ) \
      } while(0)

Walk through all the controls forward-reachable from a given control node of an unstructured.

Reachability is defined by successor-only relation (i.e. the control flow graph is seen as directed)

Parameters

ctl	is a name of a control node variable that is declared inside this macro and is used by the following code to access the visited control node
code	is the actions to execute on the visited control node
c	is a control node to start visiting with
list	is a list that will store the visited control nodes. It is used mainly for this macro to avoid visiting twice a node. The simple usage is to give a list variable initialized to NIL. A nice side effect is that it will contain the list of all the forward-reachable control nodes. Do not forget to free this list afterwards. Another classical usage is to give to the macro a list with a list of nodes to avoid visiting.

Definition at line 2147 of file ri-util.h.

GENERIC_CONTROL_MAP [1/2]

#define GENERIC_CONTROL_MAP	(		get_controls,
			ctl,
			code,
			c,
			list
	)

Value:

{ \
    cons *_cm_list_init = (list) ; \
    cons *_cm_list = _cm_list_init ; \
    if( _cm_list == NIL ) {\
         get_controls( c, &_cm_list ) ; \
         _cm_list = gen_nreverse( _cm_list ) ; \
    }\
    MAPL( _cm_ctls, {control ctl = CONTROL( CAR( _cm_ctls )) ; \
 \
                 code ;}, \
          _cm_list ) ; \
   if( _cm_list_init == NIL ) \
        list = _cm_list ; \
}

The control node visiting engine.

Definition at line 2202 of file ri-util-local.h.

GENERIC_CONTROL_MAP [2/2]

#define GENERIC_CONTROL_MAP	(		get_controls,
			ctl,
			code,
			c,
			list
	)

Value:

{ \
    cons *_cm_list_init = (list) ; \
    cons *_cm_list = _cm_list_init ; \
    if( _cm_list == NIL ) {\
         get_controls( c, &_cm_list ) ; \
         _cm_list = gen_nreverse( _cm_list ) ; \
    }\
    MAPL( _cm_ctls, {control ctl = CONTROL( CAR( _cm_ctls )) ; \
 \
                 code ;}, \
          _cm_list ) ; \
   if( _cm_list_init == NIL ) \
        list = _cm_list ; \
}

The control node visiting engine.

Definition at line 2210 of file ri-util.h.

UNSTRUCTURED_CONTROL_MAP [1/2]

#define UNSTRUCTURED_CONTROL_MAP	(		c,
			u,
			l,
			code
	)

Value:

  /**The implementation is sub-optimal because it duplicates the        \
     code... */                                                         \
  do {                                                                  \
    /**First get the control nodes reachable from the entry node: */    \
    control_map_get_blocs(unstructured_entry(u), &l);                   \
    /**Add then the control nodes reachable from the exit nodes if not  \
       already in: */                                                   \
    control_map_get_blocs(unstructured_exit(u), &l);                    \
    /**Reverse the list because previous construction was done in the   \
       reverse way: */                                                  \
    l = gen_nreverse(l);                                                \
    /**Iterate on all the selected control nodes: */                    \
    FOREACH(CONTROL, c, l)                                              \
      code                                                              \
  } while(0)

Walk through all the controls of un unstructured.

This macro do not work indeed because often the...

The nodes are those reachable from the entry node and also from the exit node (that may be unreachable from the entry node of th unstructured).

Reachability is defined by successors and predecessors (i.e. the control flow graph is seen as non-directed)

Parameters

c	is a name of a control node variable that is declared inside this macro and is used by the following code to access the visited control node
code	is the actions to execute on the visited control node
u	is the unstructured to visit
l	is a list that will store the visited control nodes. It is used mainly for this macro to avoid visiting twice a node. The simple usage is to give a list variable initialized to NIL. A nice side effect is that it will contain the list of all the reachable control nodes. Do not forget to free this list afterwards. Another classical usage is to give to the macro a list with a list of nodes to avoid visiting.

Definition at line 2102 of file ri-util-local.h.

UNSTRUCTURED_CONTROL_MAP [2/2]

#define UNSTRUCTURED_CONTROL_MAP	(		c,
			u,
			l,
			code
	)

Value:

  /**The implementation is sub-optimal because it duplicates the        \
     code... */                                                         \
  do {                                                                  \
    /**First get the control nodes reachable from the entry node: */    \
    control_map_get_blocs(unstructured_entry(u), &l);                   \
    /**Add then the control nodes reachable from the exit nodes if not  \
       already in: */                                                   \
    control_map_get_blocs(unstructured_exit(u), &l);                    \
    /**Reverse the list because previous construction was done in the   \
       reverse way: */                                                  \
    l = gen_nreverse(l);                                                \
    /**Iterate on all the selected control nodes: */                    \
    FOREACH(CONTROL, c, l)                                              \
      code                                                              \
  } while(0)

Walk through all the controls of un unstructured.

This macro do not work indeed because often the...

The nodes are those reachable from the entry node and also from the exit node (that may be unreachable from the entry node of th unstructured).

Reachability is defined by successors and predecessors (i.e. the control flow graph is seen as non-directed)

Parameters

c	is a name of a control node variable that is declared inside this macro and is used by the following code to access the visited control node
code	is the actions to execute on the visited control node
u	is the unstructured to visit
l	is a list that will store the visited control nodes. It is used mainly for this macro to avoid visiting twice a node. The simple usage is to give a list variable initialized to NIL. A nice side effect is that it will contain the list of all the reachable control nodes. Do not forget to free this list afterwards. Another classical usage is to give to the macro a list with a list of nodes to avoid visiting.

Definition at line 2110 of file ri-util.h.

WIDE_FORWARD_CONTROL_MAP [1/2]

#define WIDE_FORWARD_CONTROL_MAP	(		ctl,
			code,
			c,
			list
	)

Value:

   do {                                                         \
     GENERIC_CONTROL_MAP(wide_forward_control_map_get_blocs,    \
                         ctl, code, c, list )                   \
     } while(0)

Walk through all the controls backward-reachable from a given control node of an unstructured.

Reachability is defined by successor-only relation (i.e. the control flow graph is seen as directed)

Parameters

ctl	is a name of a control node variable that is declared inside this macro and is used by the following code to access the visited control node
code	is the actions to execute on the visited control node
c	is a control node to start visiting with
list	is a list that will store the visited control nodes. It is used mainly for this macro to avoid visiting twice a node. The simple usage is to give a list variable initialized to NIL. A nice side effect is that it will contain the list of all the reachable control nodes. Do not forget to free this list afterwards. Another classical usage is to give to the macro a list with a list of nodes to avoid visiting.

Definition at line 2194 of file ri-util-local.h.

WIDE_FORWARD_CONTROL_MAP [2/2]

#define WIDE_FORWARD_CONTROL_MAP	(		ctl,
			code,
			c,
			list
	)

Value:

   do {                                                         \
     GENERIC_CONTROL_MAP(wide_forward_control_map_get_blocs,    \
                         ctl, code, c, list )                   \
     } while(0)

Walk through all the controls backward-reachable from a given control node of an unstructured.

Reachability is defined by successor-only relation (i.e. the control flow graph is seen as directed)

Parameters

ctl	is a name of a control node variable that is declared inside this macro and is used by the following code to access the visited control node
code	is the actions to execute on the visited control node
c	is a control node to start visiting with
list	is a list that will store the visited control nodes. It is used mainly for this macro to avoid visiting twice a node. The simple usage is to give a list variable initialized to NIL. A nice side effect is that it will contain the list of all the reachable control nodes. Do not forget to free this list afterwards. Another classical usage is to give to the macro a list with a list of nodes to avoid visiting.

Definition at line 2202 of file ri-util.h.

Function Documentation

backward_control_map_get_blocs()

void backward_control_map_get_blocs	(	c	,
		l
	)

Build recursively the list of all controls backward-reachable from a control of an unstructured.

It is usually called from the BACKWARD_CONTROL_MAP macro, with the entry node of an unstructured as initial argument. It uses predecessors to define reachability.

Parameters

c	is a control node to start with
l	is a list used to stored the visited nodes. It must be initialized to the list of nodes to skip. To visit all the nodes from c, just give a list variable initialized to NIL

Definition at line 157 of file control.c.

{
    MAPL( cs, {if( CONTROL( CAR( cs )) == c ) return ;}, *l ) ;
    *l = CONS( CONTROL, c, *l ) ;
    MAPL( cs,
          {backward_control_map_get_blocs( CONTROL( CAR( cs )), l );},
          control_predecessors( c )) ;
}

References CAR, CONS, CONTROL, control_predecessors, and MAPL.

backward_control_map_get_blocs_but()

void backward_control_map_get_blocs_but	(	control	c,
		control	f,
		list *	l
	)

Transitive closure of c's predecessors, but for control f.

It is like backward_control_map_get_blocs() but avoid visiting a control node. It is used to visit subgraphs begining at c and ending at f (excluded).

Parameters

c	is a control node to start with
f	is a control node not to visit
l	is a list used to stored the visited nodes. It must be initialized to the list of nodes to skip. To visit all the nodes from c, just give a list variable initialized to NIL

Definition at line 184 of file control.c.

{
  if(gen_in_list_p(c, *l) || c == f) return;
  *l = CONS( CONTROL, c, *l ) ;
  MAPL( cs, {
    backward_control_map_get_blocs_but( CONTROL( CAR( cs )), f, l );
  }, control_predecessors( c )) ;
}

References CAR, CONS, CONTROL, control_predecessors, f(), gen_in_list_p(), and MAPL.

Here is the call graph for this function:

control_map_get_blocs()

void control_map_get_blocs	(	control	c,
		list *	l
	)

Build recursively the list of all controls reachable from a control of an unstructured.

It is usually called from the CONTROL_MAP macro, with the entry node of an unstructured as initial argument. It uses both successors and predecessors to define reachability, i.e. the graph arcs are considered edges.

Parameters

c	is a control node to start with
l	is a list used to stored the visited nodes. It must be initialized to the list of nodes to skip. To visit all the nodes from c, just give a list variable initialized to NIL

Definition at line 75 of file control.c.

{
    MAPL( cs,
    {if( CONTROL( CAR( cs )) == c ) return ;},
    *l ) ;
    *l = CONS( CONTROL, c, *l ) ;
    MAPL( cs,
    {control_map_get_blocs( CONTROL( CAR( cs )), l );},
    control_successors( c )) ;
    MAPL( ps, {control_map_get_blocs( CONTROL( CAR( ps )), l );},
    control_predecessors( c )) ;
}

References CAR, CONS, CONTROL, control_predecessors, control_successors, and MAPL.

Referenced by controlize_sequence(), dag_or_cycle_to_flow_sensitive_postconditions_or_transformers(), dag_to_flow_sensitive_preconditions(), loop_normalize_of_unstructured(), static_controlize_unstructured(), and stco_renumber_code().

Here is the caller graph for this function:

find_a_control_path()

void find_a_control_path	(	control	b,
		control	e,
		list *	pp,
		list *	vp,
		int	dir
	)

Build recursively a control path from b to e.

It is used for debugging purposes

Parameters

b	is a control node to begin with
e	is a control node to end with
pp	is a pointer to the list used to stored the path from b to e. It includes both b and e.
vp	is a pointer to the list used to stored the visited nodes. It must be initialized to the list of nodes to skip if any. To visit all the nodes from c, just give a list variable initialized to NIL. It usually must be by the caller.
dir	request a forward path is strictly positive, a backward path is stricly negative and an undirected path if zero.

Parameters

pp	p
vp	p
dir	ir

Definition at line 107 of file control.c.

{
  if(b==e) {
    *pp = CONS(CONTROL, b, NIL);
    return;
  }
 
  if(ENDP(*pp) && !gen_in_list_p(b, *vp)) {
    *vp = CONS(CONTROL, b, *vp);
    if(dir>=0) {
      FOREACH(CONTROL, s, control_successors(b)) {
        find_a_control_path(s, e, pp, vp, dir);
        if(!ENDP(*pp)) {
          pips_assert("e is the last element of *pp",
                      e==CONTROL(CAR(gen_last(*pp))));
          *pp = CONS(CONTROL, s, *pp);
          return;
        }
      }
    }
    if(dir<=0) {
      FOREACH(CONTROL, p, control_predecessors(b)) {
        find_a_control_path(p, e, pp, vp, dir);
        if(!ENDP(*pp)) {
          pips_assert("e is the last element of *pp",
                      e==CONTROL(CAR(gen_last(*pp))));
          *pp = CONS(CONTROL, p, *pp);
          return;
        }
      }
    }
  }
  pips_assert("*pp is empty", ENDP(*pp));
  return;
}

References CAR, CONS, CONTROL, control_predecessors, control_successors, ENDP, FOREACH, gen_in_list_p(), gen_last(), NIL, and pips_assert.

Referenced by controlize_sequence().

Here is the call graph for this function:

Here is the caller graph for this function:

forward_control_map_get_blocs()

void forward_control_map_get_blocs	(	c	,
		l
	)

Build recursively the list of all controls forward-reachable from a control of an unstructured.

It is usually called from the FORWARD_CONTROL_MAP macro, with the entry node of an unstructured as initial argument. It uses successors to define reachability.

Parameters

c	is a control node to start with
l	is a list used to stored the visited nodes. It must be initialized to the list of nodes to skip. To visit all the nodes from c, just give a list variable initialized to NIL

Definition at line 208 of file control.c.

{
    MAPL( cs, {if( CONTROL( CAR( cs )) == c ) return ;}, *l ) ;
    *l = CONS( CONTROL, c, *l ) ;
    MAPL( cs,
          {forward_control_map_get_blocs( CONTROL( CAR( cs )), l );},
          control_successors( c )) ;
}

References CAR, CONS, CONTROL, control_successors, and MAPL.

Referenced by cycle_to_flow_sensitive_preconditions(), dag_or_cycle_to_flow_sensitive_postconditions_or_transformers(), davinci_print_non_deterministic_unstructured(), unstructured_consistency_p(), unstructured_to_flow_sensitive_postconditions(), unstructured_to_transformer(), and unstructured_while_p().

Here is the caller graph for this function:

forward_control_map_get_blocs_but()

void forward_control_map_get_blocs_but	(	control	c,
		control	f,
		list *	l
	)

Transitive closure of c's successors, but for control f.

It is like forward_control_map_get_blocs() but avoid visiting a control node. It is used to visit subgraphs begining at c and ending at f (excluded).

Parameters

c	is a control node to start with
f	is a control node not to visit
l	is a list used to stored the visited nodes. It must be initialized to the list of nodes to skip. To visit all the nodes from c, just give a list variable initialized to NIL

Definition at line 234 of file control.c.

{
  if(gen_in_list_p(c, *l) || c == f) return;
  *l = CONS( CONTROL, c, *l ) ;
  MAPL( cs, {
    forward_control_map_get_blocs_but( CONTROL( CAR( cs )), f, l );
  }, control_successors( c )) ;
}

References CAR, CONS, CONTROL, control_successors, f(), gen_in_list_p(), and MAPL.

Here is the call graph for this function:

wide_forward_control_map_get_blocs()

void wide_forward_control_map_get_blocs	(	c	,
		l
	)

Same as above, but follows successors by minimal path lengths.

It is OK if there is only one path length when computing transformers and/or preconditions. However, if a node is reached by several paths, the node with the minimal maximal path length should come first.

This last condition assumes infinite path length for nodes in cycles (?). It is not implemented.

Definition at line 252 of file control.c.

{
  list nodes = NIL;
  list frontier = CONS( CONTROL, c, NIL );
  list new_frontier = NIL;
 
  while(!ENDP(frontier)) {
    MAP(CONTROL,c ,{
      MAP(CONTROL, cp, {
        if(!is_control_in_list_p(cp, nodes)
           && !is_control_in_list_p(cp, frontier)
           && !is_control_in_list_p(cp, new_frontier))
          new_frontier = CONS(CONTROL, cp, new_frontier);
      }, control_successors(c));
    }, frontier);
    nodes = gen_append(nodes, frontier);
    frontier = new_frontier;
    new_frontier = NIL;
  }
 
  *l = nodes;
}

References CONS, CONTROL, control_successors, cp, ENDP, gen_append(), is_control_in_list_p(), MAP, and NIL.

Here is the call graph for this function: