control.h File Reference

Go to the source code of this file.

Macros
#define	CONTROL_INCLUDED
	Warning! Do not modify this file that is automatically generated! More...
#define	USE_NEW_CONTROLIZER_ENV_VAR_NAME   "PIPS_USE_NEW_CONTROLIZER"
	Define the environment variables used to select which controlizer version to use independently of which one was activated at the pipsmake level: More...
#define	USE_OLD_CONTROLIZER_ENV_VAR_NAME   "PIPS_USE_OLD_CONTROLIZER"
	The name of the one to force the use of the old controlizer: More...

Functions
statement	unsugared_loop_header (statement)
	LOOP_HEADER, LOOP_TEST and LOOP_INC build the desugaring phases of a do-loop L for the loop header (i=1), the test (i<10) and the increment (i=i+1). More...
statement	unsugared_forloop_header (statement)
statement	unsugared_whileloop_header (statement)
statement	unsugared_loop_test (statement)
	Do a crude test of end of do-loop for do-loop unsugaring. More...
statement	unsugared_forloop_test (statement)
statement	unsugared_whileloop_test (statement)
statement	unsugared_loop_inc (statement)
	Do an index increment instruction for do-loop unsugaring. More...
statement	unsugared_forloop_inc (statement)
control	find_exit_control_node (list, control)
	Find the exit node of a sub-CFG defined by the list of nodes ctls and by the first node to execute when finished. More...
control	find_or_create_exit_control_node (list, control)
	FI: remake of function above, incomplete backward approach, now obsolete because the forward approach works. More...
bool	controlize_statement (control, control, hash_table)
	Controlize a statement that is in a control node, that is restructure it to have a HCFG recursively (a hierarchical control flow graph). More...
statement	hcfg (statement)
	Compute the hierarchical control flow graph (HCFG) of a statement. More...
statement	loop_header (statement)
	LOOP_HEADER, LOOP_TEST and LOOP_INC build the desugaring phases of a do-loop L for the loop header (i=1), the test (i<10) and the increment (i=i+1). More...
statement	loop_test (statement)
statement	loop_inc (statement)
statement	forloop_header (statement)
statement	forloop_test (statement)
statement	forloop_inc (statement)
unstructured	control_graph (statement)
	CONTROL_GRAPH returns the control graph of the statement ST. More...
bool	ctrl_graph_undefined_p (void)
	graph.c More...
void	reset_ctrl_graph (void)
void	error_reset_ctrl_graph (void)
void	set_ctrl_graph (controlmap)
controlmap	get_ctrl_graph (void)
void	init_ctrl_graph (void)
void	close_ctrl_graph (void)
void	store_ctrl_graph (statement, control)
void	update_ctrl_graph (statement, control)
control	load_ctrl_graph (statement)
control	delete_ctrl_graph (statement)
bool	bound_ctrl_graph_p (statement)
void	store_or_update_ctrl_graph (statement, control)
void	clean_ctrl_graph (void)
	global mapping from statements to their control in the full control graph More...
list	control_list_to_statement_list (list)
	of statement More...
void	build_full_ctrl_graph (statement)
void	full_control_graph (string)
	FULL CONTROL GRAPH for module NAME. More...
void	init_ctrl_graph_travel (statement, bool(*)(statement))
bool	next_ctrl_graph_travel (statement *)
void	close_ctrl_graph_travel (void)
void	control_graph_recursive_decomposition (unstructured)
	hierarchize.c More...
bool	new_controlizer (const char *)
	module.c More...
bool	controlizer (const char *)
	The old controlizer user interface. More...
void	fuse_sequences_in_unstructured (statement)
	Try to transform each control sequence in a single statement instead of a list of control nodes: More...
statement	take_out_the_exit_node_if_not_a_continue (statement)
	Extract the statement from an exit node of an unstructured statement if it is a useful statement. More...
void	unspaghettify_or_restructure_statement (statement)
	The entry point common to unspaghettify or restructure a module: More...
void	unspaghettify_statement (statement)
	The real entry point of unspaghettify: More...
void	simple_restructure_statement (statement)
	A simple cleaning of the control graph without major topological restructuring. More...
bool	unspaghettify (const string)
	Try to simplify the control graph of a module by removing useless CONTINUEs, unreachable code. More...
void	restructure_statement (statement)
	The real entry point of control graph restructuring: More...
bool	restructure_control (const string)
	Try to simplify the control graph of a module by removing useless CONTINUEs, unreachable code, etc. More...
bool	unstructured_consistency_p (unstructured, bool)
	cfg.c More...
bool	unstructured_while_p (unstructured)
	Test if an unstructured is found to be like a structured while-loop. More...
void	init_reachable (statement)
	unreachable.c More...
bool	statement_reachable_p (statement)
	Test if the given statement is reachable from some statements given at init_reachable(start) More...
bool	statement_continued_p (statement)
	Test if the execution goes on after the given statement. More...
void	close_reachable (void)
	Remove reachability information about previously checked statements. More...
bool	meaningless_control_p (control)
	bourdoncle.c More...
bool	control_test_p (control)
	Check that a node is used as a test in a CFG. More...
void	add_control_to_embedding_control_list (control)
control	control_to_ancestor (control, hash_table)
	If vertex is an ancestor control node from the input control graph, return vertex, else return its ancestor. More...
control	control_shallow_copy (control)
unstructured	unstructured_shallow_copy (unstructured, hash_table)
unstructured	partition_to_unstructured (control, list)
	Build a new unstructured (CFG) for partition. More...
void	intersect_successors_with_partition_or_complement (control, list, bool)
	If complement_p, preserve successors in the complement of partition. More...
void	intersect_successors_with_partition (control, list)
void	intersect_successors_with_partition_complement (control, list)
list	bourdoncle_partition (unstructured, unstructured *, hash_table *, hash_table *)
list	bourdoncle_component (control, hash_table, hash_table)
int	bourdoncle_visit (control, list *, hash_table, hash_table)
unstructured	ancestor_cycle_head_to_scc (control, hash_table)
	scc_map maps either the ancestor node to its scc if the transformers are computed without context, or the call site node to its scc if cycles are replicated to compute transformers within their context. More...
unstructured	proper_cycle_head_to_scc (control, hash_table)
	Retrieve a scc_u from its head. More...
bool	cycle_head_p (control, hash_table, hash_table)
	This node is a cycle call site. More...
bool	proper_cycle_head_p (control, hash_table)
	This node is really the head of a cycle (red on daVinci pictures). More...
bool	direct_cycle_head_p (control, hash_table)
	This node is directly associated to a specific cycle. More...
unstructured	cycle_head_to_scc (control, hash_table, hash_table)
	The ancestor of this node is associated to a specific cycle. More...
bool	one_successor_kind_only_p (control, bool)
	useful for non-deterministic control flow graph only More...
bool	true_successors_only_p (control)
bool	false_successors_only_p (control)
void	bourdoncle_free (unstructured, hash_table, hash_table)
bool	guess_late_read_effect_on_entity (expression, entity)
	for_to_do_or_while_loops.c More...
sequence	for_to_do_loop_conversion (forloop, statement)
	Try to convert a C-like for-loop into a Fortran-like do-loop. More...
void	try_to_transform_a_for_loop_into_a_do_loop (forloop)
	Try to to transform the C-like for-loops into Fortran-like do-loops. More...
bool	for_loop_to_do_loop (const string)
	For-loop to do-loop transformation phase. More...
sequence	for_to_while_loop_conversion (expression, expression, expression, statement, extensions)
	Build a sequence with a while-loop from for-loop parameters. More...
void	transform_a_for_loop_into_a_while_loop (forloop)
	Try to to transform the C-like for-loops into Fortran-like do-loops. More...
void	transform_a_for_loop_statement_into_a_while_loop (statement)
	Same as above, but with no calls to ancestors. More...
bool	for_loop_to_while_loop (const string)
	For-loop to while-loop transformation phase. More...
bool	dowhile_to_while (const char *)
	dowhile_to_while.c More...
void	do_loop_to_while_loop (statement)
	converts a doloop to a while loop, in place More...
void	do_loop_to_for_loop (statement)
	converts a doloop to a for loop, in place More...

Variables
char	vcid_control_controlizer []
	cproto-generated files More...
char	vcid_control_old_controlizer []
	old_controlizer.c More...
char	vcid_unspaghettify []
	unspaghettify.c More...

Macro Definition Documentation

CONTROL_INCLUDED

#define CONTROL_INCLUDED

Warning! Do not modify this file that is automatically generated!

Modify src/Libs/control/control-local.h instead, to add your own modifications. header file built by cproto control-local.h – control.h

Definition at line 35 of file control.h.

USE_NEW_CONTROLIZER_ENV_VAR_NAME

#define USE_NEW_CONTROLIZER_ENV_VAR_NAME   "PIPS_USE_NEW_CONTROLIZER"

Define the environment variables used to select which controlizer version to use independently of which one was activated at the pipsmake level:

The name of the one to force the use of the new controlizer:

Definition at line 41 of file control.h.

USE_OLD_CONTROLIZER_ENV_VAR_NAME

#define USE_OLD_CONTROLIZER_ENV_VAR_NAME   "PIPS_USE_OLD_CONTROLIZER"

The name of the one to force the use of the old controlizer:

Definition at line 43 of file control.h.

Function Documentation

add_control_to_embedding_control_list()

void add_control_to_embedding_control_list

(

control

c

)

Definition at line 535 of file bourdoncle.c.

{
  embedding_control_list = CONS(CONTROL, c, embedding_control_list);
}

References CONS, CONTROL, and embedding_control_list.

Referenced by node_to_linked_nodes(), and print_embedding_graph().

Here is the caller graph for this function:

ancestor_cycle_head_to_scc()

unstructured ancestor_cycle_head_to_scc	(	control	a,
		hash_table	scc_map
	)

scc_map maps either the ancestor node to its scc if the transformers are computed without context, or the call site node to its scc if cycles are replicated to compute transformers within their context.

In spite of the name, this function can be call with ANY control, ancestor or not. An ancestor or a call site are mapped to a defined value.

Parameters

scc_map

cc_map

Definition at line 2356 of file bourdoncle.c.

{
  unstructured scc_u = unstructured_undefined;
 
  if((scc_u = (unstructured) hash_get(scc_map, (void *) a))
     == (unstructured) (HASH_UNDEFINED_VALUE))
    scc_u = unstructured_undefined;
 
  return scc_u;
}

References hash_get(), HASH_UNDEFINED_VALUE, and unstructured_undefined.

Referenced by cycle_head_p(), cycle_head_to_scc(), cycle_to_flow_sensitive_preconditions(), dag_to_flow_sensitive_preconditions(), direct_cycle_head_p(), load_control_fix_point(), and replicate_cycles().

Here is the call graph for this function:

Here is the caller graph for this function:

bound_ctrl_graph_p()

bool bound_ctrl_graph_p

(

statement

)

Referenced by stmt_rewrite().

Here is the caller graph for this function:

bourdoncle_component()

list bourdoncle_component	(	control	vertex,
		hash_table	ancestor_map,
		hash_table	scc_map
	)

bourdoncle partition

Build sub-unstructured associated to vertex and partition

Re-use copying performed in scc_to_dag() instead u = partition_to_unstructured(vertex, partition); vertex_ancestor = control_to_ancestor(vertex, ancestor_map); hash_put(scc_map, vertex_ancestor, u);

The partition may have to be refreshed because of the previous recursive descent and its graph restructuring action. It is assumed that vertex is still good because heads are not: however vertex is not an ancestor because the input unstructured is copied right away by bourdoncle_partition().

It might be better to recompute the smallest scc including vertex...

Update parent unstructured containing vertex and partition, remove partition and return a new unstructured with the partition inside, except for the initial vertex node which is left in the embedding graph

Build sub-unstructured associated to vertex and partition

u = unlink_partition_and build_unstructured(vertex, partition);

Do not go down into nested unstructured

Parameters

vertex	ertex
ancestor_map	ncestor_map
scc_map	cc_map

Definition at line 2218 of file bourdoncle.c.

{
  list partition = NIL;
  list b_partition = list_undefined; /* bourdoncle partition */
  unstructured u = unstructured_undefined;
  control vertex_ancestor = control_undefined;
 
  ifdebug(2) {
    pips_debug(2, "Begin for node: \n");
    print_control_node_b(vertex);
  }
 
  MAP(CONTROL, c,
  {
    if(get_dfn(c)==0) {
      (void) bourdoncle_visit(c, &partition, ancestor_map, scc_map);
    }
  }
      , control_successors(vertex));
 
  partition = CONS(CONTROL, vertex, partition);
 
  /* Build sub-unstructured associated to vertex and partition */
  /* Re-use copying performed in scc_to_dag() instead
  u = partition_to_unstructured(vertex, partition);
  vertex_ancestor = control_to_ancestor(vertex, ancestor_map);
  hash_put(scc_map, vertex_ancestor, u);
  */
 
  /* The partition may have to be refreshed because of the previous
     recursive descent and its graph restructuring action. It is assumed
     that vertex is still good because heads are not: however vertex is
     not an ancestor because the input unstructured is copied right away
     by bourdoncle_partition().
 
     It might be better to recompute the smallest scc including
     vertex... */
  b_partition = gen_copy_seq(partition);
 
  update_partition(vertex, partition, ancestor_map);
 
  /* Update parent unstructured containing vertex and partition, remove
     partition and return a new unstructured with the partition inside,
     except for the initial vertex node which is left in the embedding
     graph */
  u = scc_to_dag(vertex, partition, ancestor_map);
 
  /* Build sub-unstructured associated to vertex and partition */
  /* u = unlink_partition_and build_unstructured(vertex, partition); */
  vertex_ancestor = control_to_ancestor(vertex, ancestor_map);
  hash_put(scc_map, vertex_ancestor, u);
 
  ifdebug(2) {
    pips_debug(2, "End with internal partition: ");
    print_control_nodes(partition);
    pips_debug(2, "End with Bourdoncle partition: ");
    print_control_nodes(b_partition);
    pips_debug(2, "End with new nodes:\n");
    /* Do not go down into nested unstructured */
    gen_multi_recurse(u, statement_domain, gen_false, gen_null,
                      control_domain, gen_true, print_control_node_b, NULL);
    pips_debug(2, "With entry nodes\n");
    print_control_node_b(unstructured_control(u));
    pips_debug(2, "And exit node\n");
    print_control_node_b(unstructured_exit(u));
    pips_debug(2, "End.\n");
  }
 
  gen_free_list(partition);
  return b_partition;
}

References bourdoncle_visit(), CONS, CONTROL, control_domain, control_successors, control_to_ancestor(), control_undefined, gen_copy_seq(), gen_false(), gen_free_list(), gen_multi_recurse(), gen_null(), gen_true(), get_dfn(), hash_put(), ifdebug, list_undefined, MAP, NIL, pips_debug, print_control_node_b(), print_control_nodes(), scc_to_dag(), statement_domain, unstructured_control, unstructured_exit, unstructured_undefined, and update_partition().

Referenced by bourdoncle_visit().

Here is the call graph for this function:

Here is the caller graph for this function:

bourdoncle_free()

void bourdoncle_free	(	unstructured	ndu,
		hash_table	ancestor_map,
		hash_table	scc_map
	)

Do not free the statements pointed by the nodes in ndu or in the scc

Parameters

ndu	du
ancestor_map	ncestor_map
scc_map	cc_map

Definition at line 2506 of file bourdoncle.c.

{
  /* Do not free the statements pointed by the nodes in ndu or in the scc */
  bourdoncle_unstructured_free(ndu);
  HASH_MAP(k, v, {
    bourdoncle_unstructured_free((unstructured) v);
  }, scc_map);
  hash_table_free(ancestor_map);
  hash_table_free(scc_map);
}

References bourdoncle_unstructured_free(), HASH_MAP, and hash_table_free().

Referenced by unstructured_to_flow_sensitive_postconditions_or_transformers().

Here is the call graph for this function:

Here is the caller graph for this function:

bourdoncle_partition()

list bourdoncle_partition	(	unstructured	u,
		unstructured *	p_ndu,
		hash_table *	p_ancestor_map,
		hash_table *	p_scc_map
	)

DAG derived from u by elimination all cycles

mapping from nodes in the new unstructured to the node in the input unstructured

mapping from nodes in u, used as cycle breakers, to the corresponding scc represented as an unstructured

Initialize dfn to 0

Start from the entry point

Should the partition be translated?

Should the cycles be replicated to refine the analyses? If yes, replicate them.

Control nodes associated to a fix point

The hierarchy of fix points is/seems to be lost by scc_map...

We also need the final embedding graph... which might be lost? Or hanging from the first node in partition, the entry point, and hence from new_u.

Parameters

p_ndu	_ndu
p_ancestor_map	_ancestor_map
p_scc_map	_scc_map

Definition at line 1902 of file bourdoncle.c.

{
  list partition = NIL;
  control root = control_undefined;
  /* DAG derived from u by elimination all cycles */
  unstructured new_u = unstructured_undefined;
  /* mapping from nodes in the new unstructured to the node in the input unstructured */
  hash_table ancestor_map = hash_table_make(hash_pointer, 0);
  /* mapping from nodes in u, used as cycle breakers, to the corresponding
     scc represented as an unstructured */
  hash_table scc_map = hash_table_make(hash_pointer, 0);
 
  set_davinci_count();
 
  ifdebug(2) {
    pips_debug(2, "Begin with unstructured:\n");
    print_unstructured(u);
    davinci_print_non_deterministic_unstructured(u, "Initial unstructured", scc_map, ancestor_map);
  }
 
  make_vertex_stack();
  num = 0;
  dfn = hash_table_make(hash_pointer, 0);
 
  new_u = unstructured_shallow_copy(u, ancestor_map);
 
  ifdebug(8) {
    pips_debug(3, "Copied unstructured new_u:\n");
    print_unstructured(new_u);
    davinci_print_non_deterministic_unstructured(u, "Copy of initial unstructured",
                                                 scc_map, ancestor_map);
  }
 
 
  /* Initialize dfn to 0 */
  gen_multi_recurse(new_u, statement_domain, gen_false, gen_null,
                    control_domain, gen_true, reset_dfn, NULL);
 
  /* Start from the entry point */
  root = unstructured_control(new_u);
  (void) bourdoncle_visit(root, &partition, ancestor_map, scc_map);
 
  /* Should the partition be translated? */
 
  free_vertex_stack();
  hash_table_free(dfn);
 
  /* Should the cycles be replicated to refine the analyses? If yes, replicate them. */
  if(get_bool_property("SEMANTICS_COMPUTE_TRANSFORMERS_IN_CONTEXT")) {
    replicate_cycles(new_u, scc_map, ancestor_map);
  }
 
  ifdebug(2) {
    int number_of_fix_points = 0;
 
    pips_debug(2, "End with partition:");
    print_control_nodes(partition);
 
    pips_debug(2, "End with scc_map:\n");
    HASH_MAP(h, uc, {
      number_of_fix_points++;
      fprintf(stderr, "head=%p with unstructured=%p\n", h, uc);
    } , scc_map);
    pips_debug(2, "End with %d fix points\n", number_of_fix_points);
 
    /* Control nodes associated to a fix point */
    pips_debug(2, "\nControl nodes associated to a fix point via a sub-unstructured:\n");
    HASH_MAP(c_n, c_o, {
      void * su;
      if((su=hash_get(scc_map, c_o))!=HASH_UNDEFINED_VALUE) {
        fprintf(stderr, "head=%p copy of %p with unstructured=%p\n", c_n, c_o, su);
      }
    }, ancestor_map);
 
    /* The hierarchy of fix points is/seems to be lost by scc_map... */
    pips_debug(2, "End with %d sets of cycles:\n", number_of_fix_points);
    number_of_fix_points = 0;
    HASH_MAP(h, uc, {
      char msg[256];
 
      number_of_fix_points++;
      fprintf(stderr, "Cycles associated to head=%p with unstructured=%p (fix point %d)\n",
              h, uc, number_of_fix_points);
      sprintf(msg, "Cycles associated to head=%p\\n with unstructured=%p (fix point %d)",
              h, uc, number_of_fix_points);
      print_unstructured((unstructured) uc);
      davinci_print_non_deterministic_unstructured((unstructured) uc, msg, scc_map, ancestor_map);
      fprintf(stderr, "\n");
    } , scc_map);
 
    /* We also need the final embedding graph... which might be lost? Or
       hanging from the first node in partition, the entry point, and hence from new_u. */
    pips_debug(2, "Final embedding graph %p:\n", new_u);
      print_unstructured(new_u);
    davinci_print_non_deterministic_unstructured(new_u, "Final embedding graph", scc_map, ancestor_map);
 
    pips_debug(2, "End. \n");
  }
 
  *p_ndu = new_u;
  *p_ancestor_map = ancestor_map;
  *p_scc_map = scc_map;
 
  return partition;
}

References bourdoncle_visit(), control_domain, control_undefined, davinci_print_non_deterministic_unstructured(), dfn, fprintf(), gen_false(), gen_multi_recurse(), gen_null(), gen_true(), get_bool_property(), hash_get(), HASH_MAP, hash_pointer, hash_table_free(), hash_table_make(), HASH_UNDEFINED_VALUE, ifdebug, NIL, num, pips_debug, print_control_nodes(), print_unstructured(), replicate_cycles(), reset_dfn(), set_davinci_count(), statement_domain, unstructured_control, unstructured_shallow_copy(), and unstructured_undefined.

Referenced by unstructured_to_flow_sensitive_postconditions_or_transformers().

Here is the call graph for this function:

Here is the caller graph for this function:

bourdoncle_visit()

int bourdoncle_visit	(	control	vertex,
		list *	ppartition,
		hash_table	ancestor_map,
		hash_table	scc_map
	)

Parameters

vertex	ertex
ppartition	partition
ancestor_map	ncestor_map
scc_map	cc_map

Definition at line 2293 of file bourdoncle.c.

{
  _int min = 0;
  _int head = 0;
  bool loop = false;
 
  vertex_push(vertex);
  num = num+1;
  head = num;
  update_dfn(vertex, num);
 
  MAP(CONTROL, succ,
  {
    if(get_dfn(succ)==0) {
      min = bourdoncle_visit(succ, ppartition, ancestor_map, scc_map);
    }
    else {
      min = get_dfn(succ);
    }
    if(min<=head) {
      head = min;
      loop = true;
    }
  }
      , control_successors(vertex));
 
  if (head==get_dfn(vertex)) {
    control e = vertex_pop();
 
    update_dfn(vertex, LONG_MAX);
 
    if(loop) {
      while(e!=vertex) {
        update_dfn(e, 0);
        e = vertex_pop();
      }
      *ppartition = gen_nconc(bourdoncle_component(vertex, ancestor_map, scc_map),
                              *ppartition);
    }
    else {
      *ppartition = CONS(CONTROL, vertex, *ppartition);
    }
 
  }
 
  return head;
}

References bourdoncle_component(), CONS, CONTROL, control_successors, gen_nconc(), get_dfn(), MAP, min, num, and update_dfn().

Referenced by bourdoncle_component(), and bourdoncle_partition().

Here is the call graph for this function:

Here is the caller graph for this function:

build_full_ctrl_graph()

void build_full_ctrl_graph

(

statement

s

)

first pass to initialize the ctrl_graph controls

STATEMENT

second pass to link the statements

Definition at line 238 of file graph.c.

{
    pips_debug(3, "statement (%td,%td:%td)\n",
               ORDERING_NUMBER(statement_ordering(s)),
               ORDERING_STATEMENT(statement_ordering(s)),
               statement_number(s));
 
    /*  first pass to initialize the ctrl_graph controls
     */
    init_ctrl_graph();
    gen_multi_recurse(s,
                      statement_domain, gen_true, stmt_rewrite, /* STATEMENT */
                      NULL);
 
    /*  second pass to link the statements
     */
    statement_arrows(s, NIL);
}

References gen_multi_recurse(), gen_true(), init_ctrl_graph(), NIL, ORDERING_NUMBER, ORDERING_STATEMENT, pips_debug, statement_arrows(), statement_domain, statement_number, statement_ordering, and stmt_rewrite().

Referenced by full_control_graph(), and handle_hpf_directives().

Here is the call graph for this function:

Here is the caller graph for this function:

clean_ctrl_graph()

void clean_ctrl_graph

(

void

)

global mapping from statements to their control in the full control graph

the crtl_graph is freed by hand, because the default behavior is not convenient for my purpose. I would have needed a persistant statement in the control, but it is not desired in pips.

now it can be freed safely

Definition at line 53 of file graph.c.

{
    CONTROLMAP_MAP(s, c,
      {
          pips_debug(7, "statement (%td,%td)\n",
                     ORDERING_NUMBER(statement_ordering(s)),
                     ORDERING_STATEMENT(statement_ordering(s)));
 
          control_statement(c) = statement_undefined;
          gen_free_list(control_successors(c));
          control_successors(c) = NIL;
          gen_free_list(control_predecessors(c));
          control_predecessors(c) = NIL;
      },
          get_ctrl_graph());
 
    close_ctrl_graph(); /* now it can be freed safely */
}

References close_ctrl_graph(), control_predecessors, control_statement, control_successors, CONTROLMAP_MAP, gen_free_list(), get_ctrl_graph(), NIL, ORDERING_NUMBER, ORDERING_STATEMENT, pips_debug, statement_ordering, and statement_undefined.

Referenced by handle_hpf_directives().

Here is the call graph for this function:

Here is the caller graph for this function:

close_ctrl_graph()

void close_ctrl_graph

(

void

)

Referenced by clean_ctrl_graph().

Here is the caller graph for this function:

close_ctrl_graph_travel()

void close_ctrl_graph_travel

(

void

)

Definition at line 340 of file graph.c.

{
    free_to_see_stack();
    free_stacked_map();
}

Referenced by handle_independent_directive(), handle_reduction_directive(), and propagate_synonym().

Here is the caller graph for this function:

close_reachable()

void close_reachable

(

void

)

Remove reachability information about previously checked statements.

Definition at line 252 of file unreachable.c.

{
    close_reached();
    close_continued();
}

Referenced by module_name_to_preconditions(), and module_name_to_total_preconditions().

Here is the caller graph for this function:

control_graph_recursive_decomposition()

void control_graph_recursive_decomposition

(

unstructured

u

)

hierarchize.c

hierarchize.c

Have a look to paper "A Control-Flow Normalization Algorithm and Its Complexity" (1994) from Zahira Ammarguellat for a bibliography of the domain.

An interval graph is represented by a graph with interval_vertex_label decorations embedding control nodes. The first interval of the graph is the entry interval of the interval graph and the first control node of an interval is the entry control node of the interval:

The seed interval graph is indeed the control graph itself:

Apply recursively interval graph decomposition:

For all intervals of the graph:

If this interval has at most one exit it should be put in its own unstructured:

Useless to restructure the exit node...

If a single node, only useful if there is a loop inside (in order to detect these loops, hierarchize_control_list() is called before interval_graph() but then we need to add more guards...):

If an interval has at most one exit, the underlaying control graph can be hierachized by an unstructured.

Put all the controls in their own unstructured to hierarchize the graph:

Skip the entry interval

Stop if the interval graph does no longer change : it is only one node or an irreductible graph:

Construct the interval graph from the previous one:

Do not forget to detach control nodes from interval before sweeping:

Definition at line 563 of file hierarchize.c.

{
    /* An interval graph is represented by a graph with
       interval_vertex_label decorations embedding control nodes. The
       first interval of the graph is the entry interval of the
       interval graph and the first control node of an interval is the
       entry control node of the interval: */
    bool modified;
    control entry_node, exit_node;
    graph intervals;
 
    debug_on("RECURSIVE_DECOMPOSITION_DEBUG_LEVEL");
 
    entry_node = unstructured_control(u);
    exit_node = unstructured_exit(u);
 
    /* The seed interval graph is indeed the control graph itself: */
    intervals = control_graph_to_interval_graph_format(entry_node);
 
    pips_debug(3, "Entering with unstructured %p (%p, %p)\n",
               u, entry_node, exit_node);
    ifdebug(5) {
        pips_debug(5, "Nodes from entry_node: ");
        display_linked_control_nodes(entry_node);
        pips_debug(5, "\nNodes from exit_node: ");
        display_linked_control_nodes(exit_node);
    }
    ifdebug(6)
        display_interval_graph(intervals);
 
    /* Apply recursively interval graph decomposition: */
    do {
        /* For all intervals of the graph: */
        MAP(VERTEX, interval, {
            list controls = interval_vertex_label_controls(vertex_vertex_label(interval));
            control interval_entry = CONTROL(CAR(controls));
            list interval_exits = interval_exit_nodes(interval, exit_node);
            if (/* If this interval has at most one exit it should be put
                   in its own unstructured: */
                gen_length(interval_exits) <= 1
                && /* Useless to restructure the exit node... */
                interval_entry != exit_node
                && /* If a single node, only useful if there is a loop
                      inside (in order to detect these loops,
                      hierarchize_control_list() is called before
                      interval_graph() but then we need to add more
                      guards...): */
                (gen_length(controls) > 1
                 || (gen_length(control_successors(interval_entry)) == 2
                     && (CONTROL(CAR(control_successors(interval_entry))) == interval_entry
                         || CONTROL(CAR(CDR(control_successors(interval_entry)))) == interval_entry)))
                ) {
                /* If an interval has at most one exit, the
                   underlaying control graph can be hierachized by an
                   unstructured. */
                /* Put all the controls in their own unstructured
                   to hierarchize the graph: */
                hierarchize_control_list(interval,
                                         controls,
                                         interval_exits == NIL ? control_undefined : CONTROL(CAR(interval_exits)));
 
                gen_free_list(interval_exits);
            }
        }, CDR(graph_vertices(intervals)) /* Skip the entry interval */);
        /* Stop if the interval graph does no longer change : it is
           only one node or an irreductible graph: */
        /* Construct the interval graph from the previous one: */
        modified = interval_graph(intervals);
        pips_debug(6, "Modified = %d\n", modified);
        ifdebug(6)
            display_interval_graph(intervals);
    } while (modified);
 
 
    /* Do not forget to detach control nodes from interval before
       sweeping: */
    MAP(VERTEX, v, {
        gen_free_list(interval_vertex_label_controls(vertex_vertex_label(v)));
        interval_vertex_label_controls(vertex_vertex_label(v)) = NIL;
    }, graph_vertices(intervals));
    free_graph(intervals);
 
    pips_debug(3, "Exiting.\n");
    ifdebug(5) {
        pips_debug(5, "Nodes from entry_node: ");
        display_linked_control_nodes(entry_node);
        pips_debug(5, "\nNodes from exit_node: ");
        display_linked_control_nodes(exit_node);
    }
    ifdebug(1)
        pips_assert("Unstructured should be consistent here...",
                    unstructured_consistent_p(u));
    debug_off();
}

References CAR, CDR, CONTROL, control_graph_to_interval_graph_format(), control_successors, control_undefined, debug_off, debug_on, display_interval_graph(), display_linked_control_nodes(), free_graph(), gen_free_list(), gen_length(), graph_vertices, hierarchize_control_list(), ifdebug, interval_exit_nodes(), interval_graph(), interval_vertex_label_controls, MAP, NIL, pips_assert, pips_debug, unstructured_consistent_p(), unstructured_control, unstructured_exit, VERTEX, and vertex_vertex_label.

Referenced by unspaghettify_or_restructure_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

control_list_to_statement_list()

list control_list_to_statement_list

(

list

lc

)

of statement

of statements

Parameters

lc

c

Definition at line 103 of file graph.c.

{
    list /* of statements */ ls = NIL;
    MAP(CONTROL, c, ls = CONS(STATEMENT, control_statement(c), ls), lc);
    return ls;
}

References CONS, CONTROL, control_statement, MAP, NIL, and STATEMENT.

Referenced by compute_cumulated_reductions(), and statement_arrows().

Here is the caller graph for this function:

control_shallow_copy()

control control_shallow_copy

(

control

c

)

Definition at line 970 of file bourdoncle.c.

{
  control new_c = control_undefined;
 
  new_c = make_control(control_statement(c),
                       gen_copy_seq(control_predecessors(c)),
                       gen_copy_seq(control_successors(c)));
  hash_put(replicate_map, (void *) c, (void *) new_c);
 
  return new_c;
}

References control_predecessors, control_statement, control_successors, control_undefined, gen_copy_seq(), hash_put(), make_control(), and replicate_map.

Referenced by partition_to_unstructured(), and unstructured_shallow_copy().

Here is the call graph for this function:

Here is the caller graph for this function:

control_test_p()

bool control_test_p

(

control

c

)

Check that a node is used as a test in a CFG.

The associated statement must be a test, the number of successors must be two and the true and false branches must be empty. Exported for user of ND CFG's.

Definition at line 175 of file bourdoncle.c.

{
  bool test_p = false;
  if(!meaningless_control_p(c)) {
    if(statement_test_p(control_statement(c))) {
      if(gen_length(control_successors(c))>=2) {
        test t = statement_test(control_statement(c));
        statement ts = test_true(t);
        statement fs = test_false(t);
        test_p = (empty_statement_or_labelless_continue_p(ts)
          && empty_statement_or_labelless_continue_p(fs));
      }
    }
  }
  return test_p;
}

References control_statement, control_successors, empty_statement_or_labelless_continue_p(), gen_length(), meaningless_control_p(), statement_test(), statement_test_p(), test_false, and test_true.

Referenced by add_test_successor(), clean_up_embedding_graph(), dag_to_flow_sensitive_preconditions(), davinci_print_control_node(), intersect_successors_with_partition_or_complement(), load_arc_precondition(), one_successor_kind_only_p(), process_ready_node(), update_successor_in_copy(), and update_successors_of_predecessor().

Here is the call graph for this function:

Here is the caller graph for this function:

control_to_ancestor()

control control_to_ancestor	(	control	vertex,
		hash_table	ancestor_map
	)

If vertex is an ancestor control node from the input control graph, return vertex, else return its ancestor.

Is used in other libraries.

This assert may be too strong, but all control nodes are copied when just after entering bourdoncle_partition which should make it correct.

Theoretically only useful when HASH_UNDEFINED_VALUE has been returned, i.e. when ancestor==vertex

Parameters

vertex	ertex
ancestor_map	ncestor_map

Definition at line 854 of file bourdoncle.c.

{
  control ancestor = control_undefined;
 
  if((ancestor = hash_get(ancestor_map, vertex))==HASH_UNDEFINED_VALUE)
    ancestor = vertex;
  ifdebug(2) {
    /* This assert may be too strong, but all control nodes are copied
       when just after entering bourdoncle_partition which should make it
       correct. */
    /* Theoretically only useful when HASH_UNDEFINED_VALUE has been
       returned, i.e. when ancestor==vertex */
    if(!ancestor_control_p(ancestor_map, ancestor)) {
      statement vs = control_statement(vertex);
      statement as = control_statement(ancestor);
 
      pips_debug(2, "vertex=%p with statement %s\n",
                 vertex, statement_identification(vs));
      pips_debug(2, "ancestor=%p with statement %s\n",
                 ancestor, statement_identification(as));
      pips_assert("ancestor really is an ancestor",
                  ancestor_control_p(ancestor_map, ancestor));
    }
  }
 
  return ancestor;
}

References ancestor_control_p(), control_statement, control_undefined, hash_get(), HASH_UNDEFINED_VALUE, ifdebug, pips_assert, pips_debug, and statement_identification().

Referenced by bourdoncle_component(), cycle_head_p(), cycle_head_to_scc(), cycle_to_flow_sensitive_preconditions(), dag_or_cycle_to_flow_sensitive_postconditions_or_transformers(), dag_to_flow_sensitive_preconditions(), load_control_fix_point(), load_cycle_temporary_precondition(), replicate_cycles(), and update_partition().

Here is the call graph for this function:

Here is the caller graph for this function:

controlizer()

bool controlizer

(

const char *

module_name

)

The old controlizer user interface.

Transform a code with some goto and labels (typically generated by a parser) into a code that is a hierarchical control flow graph, the standard abstract syntax tree of PIPS (the RI).

Interface for pipsdbm and pipsmake

Should never arise

To have the debug in unspaghettify_statement() working:

The statement of a compilation unit is a long list of continue statements and it takes a long time to restructure although nothing is done in the end. So, let's skip this useless processing. SG:it may be ok to skip it, but we still need to call module_reorder ...

gen_copy_seq(statement_declarations(parsed_mod_stat))

By setting this property, we try to unspaghettify the control graph of the module:

With C code, some local declarations may have been lost by the (current) restructurer

Reorder the module, because we have a new statement structure.

Parameters

module_name

odule_name

Definition at line 224 of file module.c.

{
  if (getenv(USE_NEW_CONTROLIZER_ENV_VAR_NAME) != NULL) {
    pips_user_warning("Force the use of the new controlizer because a '%s' environment variable is defined\n", USE_NEW_CONTROLIZER_ENV_VAR_NAME);
    return new_controlizer(module_name);
  }
 
  entity m = module_name_to_entity(module_name);
  pips_assert("Module must be defined in symbol table",!entity_undefined_p(m));
 
  statement module_stat, parsed_mod_stat;
 
  // generate pragma string or expression using the correct language:
  value mv = entity_initial(module_name_to_entity(module_name));
  if(value_code_p(mv)) {
    code c = value_code(mv);
    set_prettyprint_language_from_property(language_tag(code_language(c)));
  } else {
    /* Should never arise */
    set_prettyprint_language_from_property(is_language_fortran);
  }
 
  set_current_module_entity(m);
 
  parsed_mod_stat = (statement) db_get_memory_resource(DBR_PARSED_CODE, module_name, true);
  module_stat =  copy_statement(parsed_mod_stat) ;
  /* To have the debug in unspaghettify_statement() working: */
  set_current_module_statement(module_stat);
 
  debug_on("CONTROL_DEBUG_LEVEL");
  ifdebug(1){
    statement_consistent_p(parsed_mod_stat);
    statement_consistent_p(module_stat);
  }
 
  /* The statement of a compilation unit is a long list of continue
     statements and it takes a long time to restructure although
     nothing is done in the end. So, let's skip this useless
     processing.
    SG:it may be ok to skip it, but we still need to call module_reorder ...
     */
  if(!compilation_unit_p(module_name)) {
    /* *module_stat can be re-used because control_graph reallocates
       statements; do not show that to any student!
       statement_instruction(module_stat) =
       make_instruction(is_instruction_unstructured,
       control_graph(module_stat));
       Maintenant que je nettoie le code aussi avant le controlizer,
       un programme sans instruction ne contient qu'un statement
       RETURN, c'est a` dire un statement de CALL vers RETURN avec le
       label 00000.  Comme la ligne ci-dessus recycle le label et le
       commentaire, on se retrouve avec un unstructured avec le label
       et le commentaire du RETURN qu'il contient... En plus il y avait
       une re'cursion de l'unstructured vers module_stat. :-(
 
       So now correct the label and the comment: */
 
    ifdebug(1) pips_assert("the module statement is consistent "
                "before the controlizer is called",
                statement_consistent_p(module_stat));
 
    module_stat = make_statement(entity_empty_label(),
        STATEMENT_NUMBER_UNDEFINED,
        MAKE_ORDERING(0,1),
        empty_comments,
        make_instruction(is_instruction_unstructured,
            control_graph(module_stat)),
            NIL /* gen_copy_seq(statement_declarations(parsed_mod_stat))*/,
            NULL,
            empty_extensions(),
            make_synchronization_none());
 
    ifdebug(1) pips_assert("the module statement is consistent "
                "after the controlizer call",
                statement_consistent_p(module_stat));
 
    /* By setting this property, we try to unspaghettify the control graph
       of the module: */
    if (get_bool_property("UNSPAGHETTIFY_IN_CONTROLIZER"))
      unspaghettify_statement(module_stat);
 
 
    /* With C code, some local declarations may have been lost by the
       (current) restructurer */
    if(c_module_p(m))
      module_stat = update_unstructured_declarations(module_stat);
 
  }
 
  /* Reorder the module, because we have a new statement structure. */
  module_reorder(module_stat);
 
  ifdebug(1) statement_consistent_p(module_stat);
 
  DB_PUT_MEMORY_RESOURCE(DBR_CODE, module_name, module_stat);
 
  reset_current_module_entity();
  reset_current_module_statement();
 
  debug_off();
 
  return true;
}

References c_module_p(), code_language, compilation_unit_p(), control_graph(), copy_statement(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, empty_comments, empty_extensions(), entity_empty_label(), entity_initial, entity_undefined_p, get_bool_property(), ifdebug, is_instruction_unstructured, is_language_fortran, language_tag, make_instruction(), MAKE_ORDERING, make_statement(), make_synchronization_none(), module_name(), module_name_to_entity(), module_reorder(), new_controlizer(), NIL, pips_assert, pips_user_warning, reset_current_module_entity(), reset_current_module_statement(), set_current_module_entity(), set_current_module_statement(), set_prettyprint_language_from_property(), statement_consistent_p(), STATEMENT_NUMBER_UNDEFINED, unspaghettify_statement(), update_unstructured_declarations(), USE_NEW_CONTROLIZER_ENV_VAR_NAME, value_code, and value_code_p.

Referenced by AddEntityToCompilationUnit(), new_controlizer(), outliner_independent(), and RemoveEntityFromCompilationUnit().

Here is the call graph for this function:

Here is the caller graph for this function:

ctrl_graph_undefined_p()

bool ctrl_graph_undefined_p

(

void

)

graph.c

cycle_head_p()

bool cycle_head_p	(	control	c,
		hash_table	ancestor_map,
		hash_table	scc_map
	)

This node is a cycle call site.

This is correct whether the actual scc associated to c is scc_u or not. If a copy of a control is associated to a scc, its ancestors and all the others copies also are associated to a scc.

we may be in the context sensitive transformer mode

Parameters

ancestor_map	ncestor_map
scc_map	cc_map

Definition at line 2385 of file bourdoncle.c.

{
  /* This is correct whether the actual scc associated to c is scc_u or
     not. If a copy of a control is associated to a scc, its ancestors and
     all the others copies also are associated to a scc. */
  bool is_cycle = false;
  control a = control_to_ancestor(c, ancestor_map);
  unstructured scc_u = ancestor_cycle_head_to_scc(a, scc_map);
 
  if(unstructured_undefined_p(scc_u)) {
    /* we may be in the context sensitive transformer mode */
    scc_u = ancestor_cycle_head_to_scc(c, scc_map);
  }
 
  is_cycle = !unstructured_undefined_p(scc_u);
 
  return is_cycle;
}

References ancestor_cycle_head_to_scc(), control_to_ancestor(), and unstructured_undefined_p.

Referenced by cycle_to_flow_sensitive_preconditions(), dag_to_flow_sensitive_preconditions(), davinci_print_non_deterministic_unstructured(), process_ready_node(), replicate_cycles(), and unstructured_to_effects().

Here is the call graph for this function:

Here is the caller graph for this function:

cycle_head_to_scc()

unstructured cycle_head_to_scc	(	control	c,
		hash_table	ancestor_map,
		hash_table	scc_map
	)

The ancestor of this node is associated to a specific cycle.

either we have a direct connection, or we need to go thru the ancestor node

Parameters

ancestor_map	ncestor_map
scc_map	cc_map

Definition at line 2433 of file bourdoncle.c.

{
  /* either we have a direct connection, or we need to go thru the
     ancestor node */
 
  unstructured scc_u = ancestor_cycle_head_to_scc(c, scc_map);
 
  if(unstructured_undefined_p(scc_u)) {
    control a = control_to_ancestor(c, ancestor_map);
    scc_u = ancestor_cycle_head_to_scc(a, scc_map);
  }
  return scc_u;
}

References ancestor_cycle_head_to_scc(), control_to_ancestor(), and unstructured_undefined_p.

Referenced by dag_to_flow_sensitive_preconditions(), process_ready_node(), and unstructured_to_effects().

Here is the call graph for this function:

Here is the caller graph for this function:

delete_ctrl_graph()

control delete_ctrl_graph

(

statement

)

direct_cycle_head_p()

bool direct_cycle_head_p	(	control	c,
		hash_table	scc_map
	)

This node is directly associated to a specific cycle.

Parameters

scc_map

cc_map

Definition at line 2422 of file bourdoncle.c.

{
  bool is_cycle = false;
  unstructured scc_u = ancestor_cycle_head_to_scc(c, scc_map);
 
  is_cycle = !unstructured_undefined_p(scc_u);
 
  return is_cycle;
}

References ancestor_cycle_head_to_scc(), and unstructured_undefined_p.

Referenced by replicate_cycles().

Here is the call graph for this function:

Here is the caller graph for this function:

do_loop_to_for_loop()

void do_loop_to_for_loop

(

statement

sl

)

converts a doloop to a for loop, in place

Parameters

sl

l

Definition at line 162 of file dowhile_to_while.c.

{
  pips_assert("statement is a loop",statement_loop_p(sl));
  loop l =statement_loop(sl);
  range r = loop_range(l);
 
  forloop fl = make_forloop(
    make_assign_expression(entity_to_expression(loop_index(l)),
                           copy_expression(range_lower(r))),
    MakeBinaryCall(entity_intrinsic(LESS_OR_EQUAL_OPERATOR_NAME),
                   entity_to_expression(loop_index(l)),
                   copy_expression(range_upper(r))),
    MakeBinaryCall(entity_intrinsic(PLUS_UPDATE_OPERATOR_NAME),
                   entity_to_expression(loop_index(l)),
                   copy_expression(range_increment(r))),
    copy_statement(loop_body(l)));
  update_statement_instruction(sl, make_instruction_forloop(fl));
}

References copy_expression(), copy_statement(), entity_intrinsic(), entity_to_expression(), LESS_OR_EQUAL_OPERATOR_NAME, loop_body, loop_index, loop_range, make_assign_expression(), make_forloop(), make_instruction_forloop(), MakeBinaryCall(), pips_assert, PLUS_UPDATE_OPERATOR_NAME, range_increment, range_lower, range_upper, statement_loop(), statement_loop_p(), and update_statement_instruction().

Referenced by rw_loop().

Here is the call graph for this function:

Here is the caller graph for this function:

do_loop_to_while_loop()

void do_loop_to_while_loop

(

statement

sl

)

converts a doloop to a while loop, in place

convert the loop to a while loop : fst the body

then the whileloop

and the prelude

Parameters

sl

l

Definition at line 115 of file dowhile_to_while.c.

{
  pips_assert("statement is a loop",statement_loop_p(sl));
  loop l =statement_loop(sl);
  range r = loop_range(l);
 
  /* convert the loop to a while loop :
   * fst the body
   */
  list statements = make_statement_list(
    copy_statement(loop_body(l)),
    make_assign_statement(
      entity_to_expression(loop_index(l)),
      MakeBinaryCall(
        entity_intrinsic(PLUS_OPERATOR_NAME),
        entity_to_expression(loop_index(l)),
        range_increment(r)
        )
      )
    );
  /* then the whileloop */
  whileloop wl = make_whileloop(
    MakeBinaryCall(
      entity_intrinsic(LESS_OR_EQUAL_OPERATOR_NAME),
      entity_to_expression(loop_index(l)),
      range_upper(r)
      ),
    make_block_statement(statements),
    entity_empty_label(),
    make_evaluation_before());
 
  /* and the prelude */
  sequence seq = make_sequence(
    make_statement_list(
      make_assign_statement(entity_to_expression(loop_index(l)),
                            range_lower(r)),
      instruction_to_statement(make_instruction_whileloop(wl))
      )
    );
  range_upper(r)=expression_undefined;
  range_lower(r)=expression_undefined;
  range_increment(r)=expression_undefined;
 
  update_statement_instruction(sl,make_instruction_sequence(seq));
}

References copy_statement(), entity_empty_label(), entity_intrinsic(), entity_to_expression(), expression_undefined, instruction_to_statement(), LESS_OR_EQUAL_OPERATOR_NAME, loop_body, loop_index, loop_range, make_assign_statement(), make_block_statement(), make_evaluation_before(), make_instruction_sequence(), make_instruction_whileloop(), make_sequence(), make_statement_list, make_whileloop(), MakeBinaryCall(), pips_assert, PLUS_OPERATOR_NAME, range_increment, range_lower, range_upper, statement_loop(), statement_loop_p(), and update_statement_instruction().

Referenced by terapix_loop_handler().

Here is the call graph for this function:

Here is the caller graph for this function:

dowhile_to_while()

bool dowhile_to_while

(

const char *

module_name

)

dowhile_to_while.c

Parameters

module_name

odule_name

Definition at line 82 of file dowhile_to_while.c.

{
        // prelude
  debug_on("CONTROL_DEBUG_LEVEL");
        set_current_module_entity( module_name_to_entity(module_name) );
        set_current_module_statement(
    (statement) db_get_memory_resource(DBR_CODE, module_name, true)
    );
 
  // whether anything was changed
  bool changed = false;
 
        // actual transformation
  gen_context_recurse(get_current_module_statement(), &changed,
                      statement_domain, gen_true2, dowhile_to_while_walker);
 
        // postlude
  if (changed)
  {
    module_reorder(get_current_module_statement());
    DB_PUT_MEMORY_RESOURCE(DBR_CODE, module_name,
                           get_current_module_statement());
  }
 
        reset_current_module_statement();
        reset_current_module_entity();
  debug_off();
        return true;
}

References db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, dowhile_to_while_walker(), gen_context_recurse, gen_true2(), get_current_module_statement(), module_name(), module_name_to_entity(), module_reorder(), reset_current_module_entity(), reset_current_module_statement(), set_current_module_entity(), set_current_module_statement(), and statement_domain.

Here is the call graph for this function:

error_reset_ctrl_graph()

void error_reset_ctrl_graph

(

void

)

false_successors_only_p()

bool false_successors_only_p

(

control

c

)

Definition at line 2481 of file bourdoncle.c.

{
  bool true_only_p = false;
  true_only_p = one_successor_kind_only_p(c, true);
  return true_only_p;
}

References one_successor_kind_only_p().

Referenced by dag_to_flow_sensitive_preconditions(), and process_ready_node().

Here is the call graph for this function:

Here is the caller graph for this function:

for_loop_to_do_loop()

bool for_loop_to_do_loop

(

const string

module_name

)

For-loop to do-loop transformation phase.

This transformation transform for example a \begin{lstlisting} for (i = lb; i < ub; i += stride) body; \end{lstlisting} into a \begin{lstlisting}[language=fortran] do i = lb, ub - 1, stride body end do \end{lstlisting}

Now use pure local analysis on the code but we could imagine further use of semantics analysis some day...

Get the true ressource, not a copy, since we modify it in place.

We need to access to the instruction containing the current for-loops, so ask NewGen gen_recurse to keep this informations for us:

Iterate on all the for-loops:

Reorder the module, because some statements have been replaced.

Should have worked:

Parameters

module_name

odule_name

Definition at line 779 of file for_to_do_or_while_loops.c.

                                                   {
  statement module_statement;
 
  /* Get the true ressource, not a copy, since we modify it in place. */
  module_statement =
    (statement) db_get_memory_resource(DBR_CODE, module_name, true);
 
  set_current_module_statement(module_statement);
  entity mod = module_name_to_entity(module_name);
  set_current_module_entity(mod);
 
  debug_on("FOR_LOOP_TO_DO_LOOP_DEBUG_LEVEL");
  pips_assert("Statement should be OK before...", statement_consistent_p(module_statement));
 
  /* We need to access to the instruction containing the current
     for-loops, so ask NewGen gen_recurse to keep this informations for
     us: */
  /* Iterate on all the for-loops: */
  gen_recurse(module_statement,
              // Since for-loop statements can be nested, only restructure in
              // a bottom-up way, : 
              forloop_domain, gen_true, try_to_transform_a_for_loop_into_a_do_loop);
 
  pips_assert("Statement should be OK after...", statement_consistent_p(module_statement));
 
  pips_debug(2, "done\n");
 
  debug_off();
 
  /* Reorder the module, because some statements have been replaced. */
  module_reorder(module_statement);
 
  DB_PUT_MEMORY_RESOURCE(DBR_CODE, module_name, module_statement);
 
  reset_current_module_statement();
  reset_current_module_entity();
 
  /* Should have worked: */
  return true;
}

References db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, forloop_domain, gen_recurse, gen_true(), module_name(), module_name_to_entity(), module_reorder(), module_statement, pips_assert, pips_debug, reset_current_module_entity(), reset_current_module_statement(), set_current_module_entity(), set_current_module_statement(), statement_consistent_p(), and try_to_transform_a_for_loop_into_a_do_loop().

Here is the call graph for this function:

for_loop_to_while_loop()

bool for_loop_to_while_loop

(

const string

module_name

)

For-loop to while-loop transformation phase.

This transformation transforms a \begin{lstlisting} for (init; cond; update) body; \end{lstlisting} into a \begin{lstlisting} { init; while(cond) { body; update; } } \end{lstlisting}

Get the true ressource, not a copy, since we modify it in place.

We need to access to the instruction containing the current for-loops, so ask NewGen gen_recurse to keep this informations for us:

Iterate on all the for-loops:

Reorder the module, because some statements have been replaced.

Should have worked:

Parameters

module_name

odule_name

Definition at line 1001 of file for_to_do_or_while_loops.c.

                                                      {
  statement module_statement;
 
  /* Get the true ressource, not a copy, since we modify it in place. */
  module_statement =
    (statement) db_get_memory_resource(DBR_CODE, module_name, true);
 
  set_current_module_statement(module_statement);
  entity mod = module_name_to_entity(module_name);
  set_current_module_entity(mod);
 
  debug_on("FOR_LOOP_TO_WHILE_LOOP_DEBUG_LEVEL");
  pips_assert("Statement should be OK before...", statement_consistent_p(module_statement));
 
  /* We need to access to the instruction containing the current
     for-loops, so ask NewGen gen_recurse to keep this informations for
     us: */
  /* Iterate on all the for-loops: */
  gen_recurse(module_statement,
              // Since for-loop statements can be nested, only restructure in
              // a bottom-up way, :
              //forloop_domain, gen_true, transform_a_for_loop_into_a_while_loop);
              statement_domain, gen_true, transform_a_for_loop_statement_into_a_while_loop);
 
  pips_assert("Statement should be OK after...", statement_consistent_p(module_statement));
 
  pips_debug(2, "done\n");
 
  debug_off();
 
  /* Reorder the module, because some statements have been replaced. */
  module_reorder(module_statement);
 
  DB_PUT_MEMORY_RESOURCE(DBR_CODE, module_name, module_statement);
 
  reset_current_module_statement();
  reset_current_module_entity();
 
  /* Should have worked: */
  return true;
}

References db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, gen_recurse, gen_true(), module_name(), module_name_to_entity(), module_reorder(), module_statement, pips_assert, pips_debug, reset_current_module_entity(), reset_current_module_statement(), set_current_module_entity(), set_current_module_statement(), statement_consistent_p(), statement_domain, and transform_a_for_loop_statement_into_a_while_loop().

Here is the call graph for this function:

for_to_do_loop_conversion()

sequence for_to_do_loop_conversion	(	forloop	theloop,
		statement	parent
	)

Try to convert a C-like for-loop into a Fortran-like do-loop.

Assume to match what is done in the prettyprinter C_loop_range().

Returns

a sequence containing the do-loop if the transformation worked or sequence_undefined if it failed.

This does not filter scalar integers...

Consider only scalar integer variables as loop indices

&& type_depth(lit)==1

We got a candidate loop index and final bound, let's check the increment

We have found a do-loop compatible for-loop:

guess lower bound

try hard to reproduce statement content

Parameters

theloop	heloop
parent	arent

Definition at line 614 of file for_to_do_or_while_loops.c.

{
 
    sequence output = sequence_undefined;
    expression init = forloop_initialization(theloop);
    expression cond = forloop_condition(theloop);
    expression incr = forloop_increment(theloop);
    statement body  = forloop_body(theloop);
 
    set cond_entities = get_referenced_entities(cond);
    /* This does not filter scalar integers... */
    set incr_entities = get_referenced_entities(incr);
    set cond_inter_incr_entities = set_make(set_pointer);
    cond_inter_incr_entities = set_intersection(cond_inter_incr_entities,incr_entities,cond_entities);
 
    SET_FOREACH(entity,loop_index,cond_inter_incr_entities)
    {
      /* Consider only scalar integer variables as loop indices */
      type lit = ultimate_type(entity_type(loop_index));
      if(scalar_integer_type_p(lit) /* && type_depth(lit)==1*/ ) {
        if(!guess_write_effect_on_entity(body,loop_index)
           &&!guess_late_read_effect_on_entity(init, loop_index))
        {
            bool is_upper_p,is_increasing_p;
            expression upper_bound;
            if(condition_expression_to_final_bound(cond,loop_index,&is_upper_p, &upper_bound))
            {
                set upper_bound_entities = get_referenced_entities(upper_bound);
                bool upper_bound_entity_written=false;
                SET_FOREACH(entity,e,upper_bound_entities)
                {
                    if(guess_write_effect_on_entity(body,e) || guess_write_effect_on_entity(incr,e))
                    {
                        upper_bound_entity_written=true;
                        break;
                    }
                }
                set_free(upper_bound_entities);
                if(!upper_bound_entity_written){
                    /* We got a candidate loop index and final bound,
                       let's check the increment */
                    expression increment_expression =
                      guess_loop_increment(incr,loop_index,body);
                    expression increment;
                    if( !expression_undefined_p(increment_expression) &&
                        incrementation_expression_to_increment(increment_expression,
                                                               loop_index,
                                                               &is_increasing_p,
                                                               &increment))
                    {
                        /* We have found a do-loop compatible for-loop: */
                        output=make_sequence(NIL);
                        if(increment_expression!=incr){
                            remove_expression_from_comma_list(incr,increment_expression);
                            insert_statement(body,instruction_to_statement(make_instruction_expression(incr)),false);
                            //statement_consistent_p(body);
                        }
 
                        /* guess lower bound */
                        expression lower_bound = guess_loop_lower_bound(init,loop_index);
                        if(expression_undefined_p(lower_bound))
                            lower_bound=entity_to_expression(loop_index);
                        else {
                            if( lower_bound!= init) {
                                remove_expression_from_comma_list(init,lower_bound);
                                sequence_statements(output)=gen_append(sequence_statements(output),
                                        CONS(STATEMENT,instruction_to_statement(make_instruction_call(expression_call(init))),NIL));
                            }
                            lower_bound=EXPRESSION(CAR(CDR(call_arguments(expression_call(lower_bound)))));
                        }
 
                        if (!is_upper_p && is_increasing_p)
                            pips_user_warning("Loop with lower bound and increasing index %s\n", entity_local_name(loop_index));
                        if (is_upper_p && !is_increasing_p)
                            pips_user_warning("Loop with upper bound and decreasing index %s\n", entity_local_name(loop_index));
 
                        range lr;
                        if(is_upper_p)
                          lr = make_range(lower_bound, upper_bound, increment);
                        else {
                          // FI: Unfortunately, the problem must be
                          // postponed to the prettyprinter
                          lr = make_range(lower_bound, upper_bound, increment);
                        }
                        loop l = make_loop(loop_index, lr, body, statement_label(parent),
                                           make_execution_sequential(),NIL);
 
                        /* try hard to reproduce statement content */
                        statement sl = make_statement(
                                statement_label(parent),
                                statement_number(parent),
                                STATEMENT_ORDERING_UNDEFINED,
                                statement_comments(parent),
                                make_instruction_loop(l),
                                statement_declarations(parent),
                                statement_decls_text(parent),
                                statement_extensions(parent), make_synchronization_none());
 
                        statement_label(parent)=entity_empty_label();
                        statement_ordering(parent)=STATEMENT_ORDERING_UNDEFINED;
                        statement_number(parent)=STATEMENT_NUMBER_UNDEFINED;
                        statement_comments(parent)=empty_comments;
                        statement_declarations(parent)=NIL;
                        statement_decls_text(parent)=NULL;
                        statement_extensions(parent)=empty_extensions();
 
                        sequence_statements(output)=gen_append(sequence_statements(output),CONS(STATEMENT,sl,NIL));
 
                    }
                }
            }
        }
      }
    }
    set_free(cond_entities);
    set_free(incr_entities );
    set_free( cond_inter_incr_entities);
    return output;
}

References call_arguments, CAR, CDR, condition_expression_to_final_bound(), CONS, empty_comments, empty_extensions(), entity_empty_label(), entity_local_name(), entity_to_expression(), entity_type, EXPRESSION, expression_call(), expression_undefined_p, forloop_body, forloop_condition, forloop_increment, forloop_initialization, gen_append(), get_referenced_entities(), guess_late_read_effect_on_entity(), guess_loop_increment(), guess_loop_lower_bound(), guess_write_effect_on_entity(), incrementation_expression_to_increment(), init, insert_statement(), instruction_to_statement(), loop_index, make_execution_sequential(), make_instruction_call(), make_instruction_expression(), make_instruction_loop(), make_loop(), make_range(), make_sequence(), make_statement(), make_synchronization_none(), NIL, pips_user_warning, remove_expression_from_comma_list(), scalar_integer_type_p(), sequence_statements, sequence_undefined, SET_FOREACH, set_free(), set_intersection(), set_make(), set_pointer, STATEMENT, statement_comments, statement_declarations, statement_decls_text, statement_extensions, statement_label, statement_number, STATEMENT_NUMBER_UNDEFINED, statement_ordering, STATEMENT_ORDERING_UNDEFINED, and ultimate_type().

Referenced by controlize_forloop(), and try_to_transform_a_for_loop_into_a_do_loop().

Here is the call graph for this function:

Here is the caller graph for this function:

for_to_while_loop_conversion()

sequence for_to_while_loop_conversion	(	expression	init,
		expression	cond,
		expression	incr,
		statement	body,
		extensions	exts
	)

Build a sequence with a while-loop from for-loop parameters.

The API is a little weird to comply with the controlizer implementation...

Build the loop body of the while with { body; incr_st; } :

Build the while(cond) { n_body } statement:

ifdebug(5) {

pips_debug(5, "Initialization statement:\n");

print_statement(init_st);

pips_debug(5, "Incrementation statement:\n");

print_statement(incr_st);

pips_debug(5, "New body statement with incrementation:\n");

print_statement(n_body);

pips_debug(5, "New whileloop statement:\n");

print_statement(wl_st);

}

Parameters

init	nit
cond	ond
incr	ncr
body	ody
exts	xts

Definition at line 826 of file for_to_do_or_while_loops.c.

                                                       {
  pips_debug(5, "Begin\n");
 
  statement init_st = make_expression_statement(init);
  statement incr_st = make_expression_statement(incr);
  sequence wlseq = sequence_undefined;
 
  /* Build the loop body of the while with { body; incr_st; } : */
  statement n_body = make_statement_from_statement_varargs_list(body,
                                                                incr_st,
                                                                NULL);
  /* Build the while(cond) { n_body } statement: */
  statement wl_st =  make_whileloop_statement(cond,
                                              n_body,
                                              STATEMENT_NUMBER_UNDEFINED,
                                              true);
  if(!empty_extensions_p(exts)) {
      free_extensions(statement_extensions(wl_st));
      statement_extensions(wl_st)=copy_extensions(exts);
  }
 
  /* ifdebug(5) { */
  /*   pips_debug(5, "Initialization statement:\n"); */
  /*   print_statement(init_st); */
  /*   pips_debug(5, "Incrementation statement:\n"); */
  /*   print_statement(incr_st); */
  /*   pips_debug(5, "New body statement with incrementation:\n"); */
  /*   print_statement(n_body); */
  /*   pips_debug(5, "New whileloop statement:\n"); */
  /*   print_statement(wl_st); */
  /* } */
 
  wlseq = make_sequence(CONS(STATEMENT, init_st,
                             CONS(STATEMENT, wl_st, NIL)));
  return wlseq;
}

References CONS, copy_extensions(), empty_extensions_p(), free_extensions(), init, make_expression_statement(), make_sequence(), make_statement_from_statement_varargs_list(), make_whileloop_statement(), NIL, pips_debug, sequence_undefined, STATEMENT, statement_extensions, and STATEMENT_NUMBER_UNDEFINED.

Referenced by controlize_forloop(), transform_a_for_loop_into_a_while_loop(), and transform_a_for_loop_statement_into_a_while_loop().

Here is the call graph for this function:

Here is the caller graph for this function:

full_control_graph()

void full_control_graph

(

string

name

)

FULL CONTROL GRAPH for module NAME.

should put something in the db if made as a pass

Parameters

name

ame

Definition at line 259 of file graph.c.

{
    statement s = (statement) db_get_memory_resource(DBR_CODE, name, true);
    build_full_ctrl_graph(s);
 
    /*  should put something in the db if made as a pass
     */
}

References build_full_ctrl_graph(), and db_get_memory_resource().

Here is the call graph for this function:

fuse_sequences_in_unstructured()

void fuse_sequences_in_unstructured

(

statement

s

)

Try to transform each control sequence in a single statement instead of a list of control nodes:

The entry point of the unstructured:

and its exit point:

To store the list of the controls to fuse we use a mapping since we need to keep track of eventual previous fuse on a control:

ifdebug(5)

print_statement(s);

Select a node with only one successor:

Since I use an O(n) algorithm instead of an O(n^2) all this condition must be checked again later since these topological and semantical properties may have changed during the fusion phase. I think it is true because the fused graph is included into the former graph but I am too lazy to write a proof... :-( Have a look to Validation/Control/create.f.

...Accept the exit node

Ok, we have found a node in a sequence. Note that we cannot fuse with the entry node since it must keep this role...

But if c is empty, we can fuse it with any successor without changing the semantincs, even if the successor is the entry node. Don't do this if there is a comment since it mess up the original source look-alike.

The fact we can have a cycle is considered a page below...

Put the control in the fuse list. Since no fusing occurs yet, the address of a control node is itself:

Use also a real list to remove the non-determinism of a later HASH_MAP. Note that since it follow a depth-first algorithm, the output program is more likely to be similar to the output, especially with cycles in the control graph:

Reverse the list to follow the order of appearance :

Now, since we have the list of the control nodes to fuse with their successors, do the fusion:

Find the address of a control node to fuse even if it has already been fused with predecessors through a transitive closure:

...The control node has not been moved

...or it has not been moved because it is not a control node to fuse anyway.

Ok, the node has been located:

Follow a former control movement:

ifdebug(5) {

fprintf(stderr,"Statement with label \"s" for control a_control_fo_fuse=p
",

entity_local_name(statement_label(control_statement(a_control_to_fuse))),

a_control_to_fuse);

print_statement(control_statement(a_control_to_fuse));

fprintf(stderr,"Let's print the statement a second time to see its label again:\n");

print_statement(control_statement(a_control_to_fuse));

}

ifdebug(6) {

pips_debug(5, "All the unstructured %p:\n", u);

print_statement(s);

}

Verify that the fusion is still valid:

...Accept the exit node

||entity_empty_label_p(statement_to_label(control_statement(the_successor)))

Well, it seems to be a real sequence, at most a loop with 2 control nodes...

make st with the statements of 2 following nodes:

Update the entry node if we fuse with it:

If the node "the_successor" is in the fuse list, we want to keep track of its new place, that is in fact fused in "a_control_to_fuse", so that an eventual fusion will use "a_control_to_fuse" instead of "the_successor":

Ok, "the_successor" is a node to fuse or that has been already fused (in this case the following is useless, but anyway...). Thus we keep track of its new location:

Update the potentially modified entry and exit nodes:

Definition at line 250 of file unspaghettify.c.

{
    list blocs = NIL;
    list control_nodes_to_fuse = NIL;
    unstructured u = instruction_unstructured(statement_instruction(s));
    list tl = statement_to_implicit_target_labels(s);
    /* The entry point of the unstructured: */
    control entry_node = unstructured_control(u);
    /* and its exit point: */
    control exit_node = unstructured_exit(u);
   /* To store the list of the controls to fuse we use a mapping since
       we need to keep track of eventual previous fuse on a control: */
    hash_table controls_to_fuse_with_their_successors =
        hash_table_make(hash_pointer, 0);
 
    bool aggressive_restructure_p = get_bool_property("FUSE_CONTROL_NODES_WITH_COMMENTS_OR_LABEL");
 
    ifdebug(4) {
      pips_debug(4, "Begin with implicit target labels:");
      print_arguments(tl);
      pips_debug(4, "\n");
    }
 
    ifdebug (1)
        pips_assert("unstructured is consistent",
                    unstructured_consistent_p(u));
    pips_debug(3, "Unstructured %p\n", u);
 
    CONTROL_MAP(c,
                {
                    statement s = control_statement(c);
                    ifdebug (1)
                        pips_assert("control is consistent",
                                    control_consistent_p(c));
                    pips_debug(3, "Looking for control %p...\n", c);
                    /* ifdebug(5) */
                    /*   print_statement(s); */
 
                    /* Select a node with only one successor: */
                    if (gen_length(control_successors(c)) == 1) {
                        control the_successor = CONTROL(CAR(control_successors(c)));
 
                        size_t number_of_successors_of_the_successor = gen_length(control_successors(the_successor));
                        size_t number_of_predecessors_of_the_successor = gen_length(control_predecessors(the_successor));
                        pips_debug(3, "Control %p: (gen_length(control_successors(c)) == 1), number_of_successors_of_the_successor = %zd, number_of_predecessors_of_the_successor = %zd, the successor is the entry node: %d, empty_statement_or_continue_p(control_statement(c)) = %d\n",
                                   c,
                                   number_of_successors_of_the_successor,
                                   number_of_predecessors_of_the_successor,
                                   the_successor == entry_node,
                                   aggressive_restructure_p ? empty_statement_or_continue_p(s) : empty_statement_or_continue_without_comment_p(s));
                        /* Since I use an O(n) algorithm instead of an
                           O(n^2) all this condition must be checked
                           again later since these topological and
                           semantical properties may have changed
                           during the fusion phase. I think it is true
                           because the fused graph is included into
                           the former graph but I am too lazy to write
                           a proof... :-( Have a look to
                           Validation/Control/create.f. */
                        if ((number_of_successors_of_the_successor <= 1
                             /* ...Accept the exit node */
                             && the_successor != entry_node
                             && number_of_predecessors_of_the_successor == 1)
                            || (aggressive_restructure_p ? empty_statement_or_continue_p(s) : empty_statement_or_continue_without_comment_p(s))) {
                            /* Ok, we have found a node in a
                               sequence. Note that we cannot fuse with the
                               entry node since it must keep this
                               role... */
                            /* But if c is empty, we can fuse it with any
                               successor without changing the semantincs,
                               even if the successor is the entry
                               node. Don't do this if there is a comment
                               since it mess up the original source
                               look-alike. */
                            /* The fact we can have a cycle is considered
                               a page below... */
                            /* Put the control in the fuse
                               list. Since no fusing occurs yet, the
                               address of a control node is itself: */
                            hash_put(controls_to_fuse_with_their_successors,
                                     (char *) c,
                                     (char *) c);
                            /* Use also a real list to remove the
                               non-determinism of a later
                               HASH_MAP. Note that since it follow a
                               depth-first algorithm, the output
                               program is more likely to be similar to
                               the output, especially with cycles in
                               the control graph: */
                            control_nodes_to_fuse = CONS(CONTROL,
                                                         c,
                                                         control_nodes_to_fuse);
                        }
                    }
                    else {
                        pips_debug(3, "(gen_length(control_successors(c)) == %zd)\n",
                                   gen_length(control_successors(c)));
                    }
                },
                entry_node,
                blocs);
    gen_free_list(blocs);
 
    /* Reverse the list to follow the order of appearance : */
    control_nodes_to_fuse = gen_nreverse(control_nodes_to_fuse);
 
    /* Now, since we have the list of the control nodes to fuse with
       their successors, do the fusion: */
    MAP(CONTROL, the_original_control, {
        control a_control_to_fuse;
        control the_successor;
        char * its_address_now;
        char * old_address;
 
        its_address_now = hash_get(controls_to_fuse_with_their_successors,
                                   (char *) the_original_control);
        /* Find the address of a control node to fuse even if
           it has already been fused with predecessors through
           a transitive closure: */
        for(old_address = (char *) the_original_control;;) {
            pips_debug(3, "Control %p (originally %p):\n",
                       its_address_now, the_original_control);
            if (old_address == its_address_now
                /* ...The control node has not been moved */
                || !hash_defined_p(controls_to_fuse_with_their_successors,
                                   (char *) its_address_now)
                /* ...or it has not been moved because it is
                   not a control node to fuse anyway. */
                )
                /* Ok, the node has been located: */
                break;
            else {
                /* Follow a former control movement: */
                old_address = its_address_now;
                its_address_now
                    = hash_get(controls_to_fuse_with_their_successors,
                               (char *) its_address_now);
            }
        }
        a_control_to_fuse = (control) its_address_now;
 
        /* ifdebug(5) { */
        /*   fprintf(stderr,"Statement with label \"%s\" for control a_control_fo_fuse=%p\n", */
        /*        entity_local_name(statement_label(control_statement(a_control_to_fuse))), */
        /*        a_control_to_fuse); */
        /*   print_statement(control_statement(a_control_to_fuse)); */
        /*   fprintf(stderr,"Let's print the statement a second time to see its label again:\n"); */
        /*   print_statement(control_statement(a_control_to_fuse)); */
        /* } */
        /* ifdebug(6) { */
        /*     pips_debug(5, "All the unstructured %p:\n", u); */
        /*     print_statement(s); */
        /* } */
        ifdebug (3)
            fprintf(stderr, "Want to fuse control %p\n", a_control_to_fuse);
        ifdebug (1)
            pips_assert("control a_control_to_fuse is consistent",
                        control_consistent_p(a_control_to_fuse));
 
        the_successor = CONTROL(CAR(control_successors(a_control_to_fuse)));
        ifdebug (3)
            fprintf(stderr, " with control %p\n", the_successor);
        ifdebug (1)
            pips_assert("control the_successor is consistent",
                        control_consistent_p(the_successor));
 
        if (a_control_to_fuse == the_successor) {
            pips_debug(3, "\tA loop of control has been found... Do not fuse the control %p\n", a_control_to_fuse);
        }
        else {
            int number_of_successors_of_the_successor =
                gen_length(control_successors(the_successor));
            int number_of_predecessors_of_the_successor =
                gen_length(control_predecessors(the_successor));
            /* Verify that the fusion is still valid: */
            if ((number_of_successors_of_the_successor <= 1
                 /* ...Accept the exit node */
                 && the_successor != entry_node
                 && number_of_predecessors_of_the_successor == 1)
                ||
                (empty_statement_or_continue_p(control_statement(a_control_to_fuse))
                 && (!gen_in_list_p(statement_to_label(control_statement(a_control_to_fuse)), tl)
                     /* ||entity_empty_label_p(statement_to_label(control_statement(the_successor)))*/)
                 /*
                   (entity_empty_label_p(statement_to_label(control_statement(a_control_to_fuse)))
                     || entity_empty_label_p(statement_to_label(control_statement(the_successor))))
                 */
                 )) {
                /* Well, it seems to be a real sequence, at most a
                   loop with 2 control nodes... */
                pips_debug(3, "\tOk fuse them.\n");
 
                fuse_2_control_nodes(a_control_to_fuse, the_successor);
                /* make st with the statements of 2 following nodes: */
 
                if (the_successor == entry_node)
                    /* Update the entry node if we fuse with it: */
                entry_node = a_control_to_fuse;
                if (the_successor == exit_node)
                    exit_node = a_control_to_fuse;
 
                /* If the node "the_successor" is in the fuse list, we
                   want to keep track of its new place, that is in
                   fact fused in "a_control_to_fuse", so that an
                   eventual fusion will use "a_control_to_fuse"
                   instead of "the_successor": */
                if (hash_defined_p(controls_to_fuse_with_their_successors,
                                   (char *) the_successor)) {
                    /* Ok, "the_successor" is a node to fuse or that
                       has been already fused (in this case the
                       following is useless, but anyway...). Thus we
                       keep track of its new location: */
                    hash_update(controls_to_fuse_with_their_successors,
                                (char *) the_successor,
                                (char *) a_control_to_fuse);
                }
            }
            else
                pips_debug(3, "\tDo not fuse them because the semantics have changed.\n");
        }
        ifdebug (1)
            pips_assert("control after fuse is consistent",
                        control_consistent_p(a_control_to_fuse));
 
    },
        control_nodes_to_fuse);
 
    /* Update the potentially modified entry and exit nodes: */
    unstructured_control(u)= entry_node;
    unstructured_exit(u)= exit_node;
 
    gen_free_list(tl);
    hash_table_free(controls_to_fuse_with_their_successors);
}

References CAR, CONS, CONTROL, control_consistent_p(), CONTROL_MAP, control_predecessors, control_statement, control_successors, empty_statement_or_continue_p(), empty_statement_or_continue_without_comment_p(), fprintf(), fuse_2_control_nodes(), gen_free_list(), gen_in_list_p(), gen_length(), gen_nreverse(), get_bool_property(), hash_defined_p(), hash_get(), hash_pointer, hash_put(), hash_table_free(), hash_table_make(), hash_update(), ifdebug, instruction_unstructured, MAP, NIL, pips_assert, pips_debug, print_arguments(), statement_instruction, statement_to_implicit_target_labels(), statement_to_label(), unstructured_consistent_p(), unstructured_control, and unstructured_exit.

Referenced by recursively_restructure_an_unstructured().

Here is the call graph for this function:

Here is the caller graph for this function:

get_ctrl_graph()

controlmap get_ctrl_graph

(

void

)

Referenced by clean_ctrl_graph().

Here is the caller graph for this function:

guess_late_read_effect_on_entity()

bool guess_late_read_effect_on_entity	(	expression	init,
		entity	loop_index
	)

for_to_do_or_while_loops.c

for_to_do_or_while_loops.c

Assuming loop_index is a potential do loop index, and init a comma expression, do we have subexpressions after the loop_index initialization that may use this index? If yes, the loop cannot be transformed into a DO loop, because this subexpression will be moved before the loop index initialization. Or the loop index initialization should be replicated before the loop.

Example (SPEC2006, milc):

for (i = parity==0x01?even_sites_on_node:0, s = &lattice[i]; i<(parity==0x02?even_sites_on_node:sites_on_node); i++, s++) {

s = &lattice[i] is going to be placed ahead of i's own initialization.

In other words, the loop can be changed in different ways:

• the loop is converted into a while loop with the initialization expression moved into a statement (easy, alreayd implemented, safe)
• the conversion into a DO loop is performed, but all initializations are moved into a statement and the new initialization expression is "loop_init = loop_init" to satisfy the do loop semantics (a new implementation is required).

Parameters

init	nit
loop_index	oop_index

Definition at line 412 of file for_to_do_or_while_loops.c.

{
  bool guess_p = false;
  if(expression_call_p(init)) {
    call c = expression_call(init);
    entity f = call_function(c);
    if(ENTITY_COMMA_P(f)) {
      bool write_found_p = false;
      list el = call_arguments(c);
      FOREACH(EXPRESSION, e, el) {
        if(!write_found_p && guess_write_effect_on_entity(e, loop_index))
          write_found_p = true;
        else if(write_found_p) {
          list rl = expression_to_reference_list(e, NIL);
          FOREACH(REFERENCE, r, rl) {
            guess_p = reference_variable(r)==loop_index;
            if(guess_p)
              break;
          }
          if(guess_p) {
            gen_free_list(rl); // Just the spine...
            break;
          }
        }
      }
    }
  }
  return guess_p;
}

References call_arguments, call_function, ENTITY_COMMA_P, EXPRESSION, expression_call(), expression_call_p(), expression_to_reference_list(), f(), FOREACH, gen_free_list(), guess_write_effect_on_entity(), init, loop_index, NIL, REFERENCE, and reference_variable.

Referenced by for_to_do_loop_conversion().

Here is the call graph for this function:

Here is the caller graph for this function:

init_ctrl_graph()

void init_ctrl_graph

(

void

)

Referenced by build_full_ctrl_graph().

Here is the caller graph for this function:

init_ctrl_graph_travel()

void init_ctrl_graph_travel	(	statement	s,
		bool(*)(statement)	decision
	)

initializations

no loop back

Definition at line 315 of file graph.c.

{
    make_to_see_stack();             /* initializations */
    make_stacked_map();
    travel_decision = decision;
 
    store_statement_stacked(s, true); /* no loop back */
    push_successors(s);
}

References push_successors(), and travel_decision.

Referenced by handle_independent_directive(), handle_reduction_directive(), and propagate_synonym().

Here is the call graph for this function:

Here is the caller graph for this function:

init_reachable()

void init_reachable

(

statement

start

)

unreachable.c

unreachable.c

Parameters

start

statement.

Parameters

start

tart

Definition at line 223 of file unreachable.c.

                                     {
  debug_on("REACHABLE_DEBUG_LEVEL");
  init_reached();
  init_continued();
  propagate(start);
  debug_off();
}

References debug_off, debug_on, propagate(), and start.

Referenced by module_name_to_preconditions(), and module_name_to_total_preconditions().

Here is the call graph for this function:

Here is the caller graph for this function:

intersect_successors_with_partition()

void intersect_successors_with_partition	(	control	c,
		list	partition
	)

Parameters

partition

artition

Definition at line 1224 of file bourdoncle.c.

{
  intersect_successors_with_partition_or_complement(c, partition, false);
}

References intersect_successors_with_partition_or_complement().

Referenced by scc_to_dag().

Here is the call graph for this function:

Here is the caller graph for this function:

intersect_successors_with_partition_complement()

void intersect_successors_with_partition_complement	(	control	c,
		list	partition
	)

Parameters

partition

artition

Definition at line 1230 of file bourdoncle.c.

{
  intersect_successors_with_partition_or_complement(c, partition, true);
}

References intersect_successors_with_partition_or_complement().

Referenced by scc_to_dag().

Here is the call graph for this function:

Here is the caller graph for this function:

intersect_successors_with_partition_or_complement()

void intersect_successors_with_partition_or_complement	(	control	c,
		list	partition,
		bool	complement_p
	)

If complement_p, preserve successors in the complement of partition.

Else preserve successors in partition. Take care of test nodes wich must keep two successors no matter what.

The CFG may not be connexe or the exit path may be hidden by a STOP statement

Let's boldy assume the parent control node is used as a CFG test statement and preserve the number of successors.

It is not a CFG test node: get rid of useless

Not true: you may have non-connexe CFG and loops with no exit.

pips_assert("We still have at least one successor", gen_length(*succs)>0);

Parameters

partition	artition
complement_p	omplement_p

Definition at line 1181 of file bourdoncle.c.

{
  list * succs = &control_successors(c);
 
  pips_assert("We have at least one successor", gen_length(*succs)>0);
 
  if(gen_length(*succs)==1) {
    control c = CONTROL(CAR(*succs));
    /* The CFG may not be connexe or the exit path may be hidden by a STOP statement */
    /*
      pips_assert("The unique successor must be in partition",
      gen_in_list_p(c, partition)==!complement_p);
    */
    if(gen_in_list_p(c, partition)==complement_p) {
      if(complement_p)
        gen_list_and_not(succs, partition);
      else
        gen_list_and(succs, partition);
    }
  }
  else if (control_test_p(c)) {
    /* Let's boldy assume the parent control node is used as a CFG test
       statement and preserve the number of successors. */
    MAPL(succ_c, {
      control succ = CONTROL(CAR(succ_c));
 
      if(gen_in_list_p(succ, partition)==complement_p)
        CONTROL_(CAR(succ_c)) = make_meaningless_control(CONS(CONTROL, c, NIL), NIL);
    } , *succs);
  }
  else {
    /* It is not a CFG test node: get rid of useless  */
    if(complement_p)
      gen_list_and_not(succs, partition);
    else
      gen_list_and(succs, partition);
  }
  /* Not true: you may have non-connexe CFG and loops with no exit. */
  /* pips_assert("We still have at least one successor", gen_length(*succs)>0); */
}

References CAR, CONS, CONTROL, CONTROL_, control_successors, control_test_p(), gen_in_list_p(), gen_length(), gen_list_and(), gen_list_and_not(), make_meaningless_control(), MAPL, NIL, and pips_assert.

Referenced by intersect_successors_with_partition(), and intersect_successors_with_partition_complement().

Here is the call graph for this function:

Here is the caller graph for this function:

load_ctrl_graph()

control load_ctrl_graph

(

statement

)

Referenced by add_arrow_in_ctrl_graph(), and push_successors().

Here is the caller graph for this function:

meaningless_control_p()

bool meaningless_control_p

(

control

c

)

bourdoncle.c

bourdoncle.c

Definition at line 154 of file bourdoncle.c.

{
  return statement_undefined_p(control_statement(c));
}

References control_statement, and statement_undefined_p.

Referenced by add_test_successor(), check_control_statement(), clean_up_control_test(), clean_up_embedding_graph(), control_cons_compare(), control_test_p(), cycle_to_flow_sensitive_preconditions(), dag_or_cycle_to_flow_sensitive_postconditions_or_transformers(), dag_to_flow_sensitive_preconditions(), davinci_print_control_node(), davinci_print_non_deterministic_unstructured(), entry_or_exit_control_p(), get_control_precondition(), node_to_path_transformer_or_postcondition(), one_successor_kind_only_p(), print_embedding_graph(), process_ready_node(), process_unreachable_node(), registered_controls_p(), replicate_cycles(), store_control_fix_point(), store_control_postcondition(), unstructured_to_effects(), update_control_postcondition(), and update_partition().

Here is the caller graph for this function:

new_controlizer()

bool new_controlizer

(

const char *

module_name

)

module.c

module.c

Interface for pipsdbm and pipsmake

Should never happen

To have the debug in unspaghettify_statement() working:

The statement of a compilation unit is a long list of continue statements and it takes a long time to restructure although nothing is done in the end. So, let's skip this useless processing. SG:it may be ok to skip it, but we still need to call module_reorder ...

By setting this property, we try to unspaghettify the control graph of the module:

With C code, some local declarations may have been lost by the (current) restructurer. FI: not investigated; should be useless by now..

Reorder the module, because we have a new statement structure.

Parameters

module_name

odule_name

Definition at line 102 of file module.c.

{
  if (getenv(USE_OLD_CONTROLIZER_ENV_VAR_NAME) != NULL) {
    pips_user_warning("Force the use of the old controlizer because a '%s' environment variable is defined\n", USE_OLD_CONTROLIZER_ENV_VAR_NAME);
    return controlizer(module_name);
  }
 
  entity m = module_name_to_entity(module_name);
  pips_assert("Module must be defined in symbol table",!entity_undefined_p(m));
 
  statement module_stat, parsed_mod_stat;
 
  // generate pragma string or expression using the correct language:
  value mv = entity_initial(module_name_to_entity(module_name));
  if(value_code_p(mv)) {
    code c = value_code(mv);
    set_prettyprint_language_from_property(language_tag(code_language(c)));
  } else {
    /* Should never happen */
    set_prettyprint_language_from_property(is_language_fortran);
  }
 
  set_current_module_entity(m);
 
  parsed_mod_stat = (statement) db_get_memory_resource(DBR_PARSED_CODE, module_name, true);
  module_stat =  copy_statement(parsed_mod_stat) ;
  /* To have the debug in unspaghettify_statement() working: */
  set_current_module_statement(module_stat);
 
  debug_on("CONTROL_DEBUG_LEVEL");
  ifdebug(1){
    statement_consistent_p(parsed_mod_stat);
    statement_consistent_p(module_stat);
  }
 
  /* The statement of a compilation unit is a long list of continue
     statements and it takes a long time to restructure although
     nothing is done in the end. So, let's skip this useless
     processing.
    SG:it may be ok to skip it, but we still need to call module_reorder ...
     */
  if(!compilation_unit_p(module_name)) {
    /* *module_stat can be re-used because control_graph reallocates
       statements; do not show that to any student!
       statement_instruction(module_stat) =
       make_instruction(is_instruction_unstructured,
       control_graph(module_stat));
       Maintenant que je nettoie le code aussi avant le controlizer,
       un programme sans instruction ne contient qu'un statement
       RETURN, c'est a` dire un statement de CALL vers RETURN avec le
       label 00000.  Comme la ligne ci-dessus recycle le label et le
       commentaire, on se retrouve avec un unstructured avec le label
       et le commentaire du RETURN qu'il contient... En plus il y avait
       une re'cursion de l'unstructured vers module_stat. :-(
 
       So now correct the label and the comment: */
 
    pips_assert("the module statement is consistent "
                "before the controlizer is called",
                statement_consistent_p(module_stat));
 
    module_stat = hcfg(module_stat);
 
    pips_assert("the module statement is consistent "
                "after the controlizer call",
                statement_consistent_p(module_stat));
 
    if (get_bool_property("FOR_TO_DO_LOOP_IN_CONTROLIZER")) {
      gen_recurse(module_stat,
                  // Since for-loop statements can be nested,
                  // only restructure in a bottom-up way, :
                  forloop_domain, gen_true,
                  try_to_transform_a_for_loop_into_a_do_loop);
 
    }
 
    if (get_bool_property("FOR_TO_WHILE_LOOP_IN_CONTROLIZER")) {
      gen_recurse(module_stat,
                  // Since for-loop statements can be nested,
                  // only restructure in a bottom-up way, :
                  //forloop_domain, gen_true,
                  //transform_a_for_loop_into_a_while_loop);
                  statement_domain, gen_true,
                  transform_a_for_loop_statement_into_a_while_loop);
    }
 
    /* By setting this property, we try to unspaghettify the control graph
       of the module: */
    if (get_bool_property("UNSPAGHETTIFY_IN_CONTROLIZER"))
      unspaghettify_statement(module_stat);
 
    /* With C code, some local declarations may have been lost by the
       (current) restructurer. FI: not investigated; should be
       useless by now.. */
    if(c_module_p(m))
      module_stat = update_unstructured_declarations(module_stat);
 
  }
 
  /* Reorder the module, because we have a new statement structure. */
  module_reorder(module_stat);
 
  statement_consistent_p(module_stat);
 
  DB_PUT_MEMORY_RESOURCE(DBR_CODE, module_name, module_stat);
 
  reset_current_module_entity();
  reset_current_module_statement();
 
  debug_off();
 
  return true;
}

References c_module_p(), code_language, compilation_unit_p(), controlizer(), copy_statement(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, entity_initial, entity_undefined_p, forloop_domain, gen_recurse, gen_true(), get_bool_property(), hcfg(), ifdebug, is_language_fortran, language_tag, module_name(), module_name_to_entity(), module_reorder(), pips_assert, pips_user_warning, reset_current_module_entity(), reset_current_module_statement(), set_current_module_entity(), set_current_module_statement(), set_prettyprint_language_from_property(), statement_consistent_p(), statement_domain, transform_a_for_loop_statement_into_a_while_loop(), try_to_transform_a_for_loop_into_a_do_loop(), unspaghettify_statement(), update_unstructured_declarations(), USE_OLD_CONTROLIZER_ENV_VAR_NAME, value_code, and value_code_p.

Referenced by controlizer().

Here is the call graph for this function:

Here is the caller graph for this function:

next_ctrl_graph_travel()

bool next_ctrl_graph_travel

(

statement *

ps

)

Parameters

ps

s

Definition at line 325 of file graph.c.

{
    while (!to_see_empty_p())
    {
        *ps = to_see_pop();
        if ((*travel_decision)(*ps))
        {
            push_successors(*ps);
            return true;
        }
    }
 
    return false;
}

References push_successors(), and travel_decision.

Referenced by handle_independent_directive(), handle_reduction_directive(), and propagate_synonym().

Here is the call graph for this function:

Here is the caller graph for this function:

one_successor_kind_only_p()

bool one_successor_kind_only_p	(	control	c,
		bool	true_p
	)

useful for non-deterministic control flow graph only

There exists at least one real successor of the requested kind and only meaningless successors of the other kind.

Parameters

true_p

rue_p

Definition at line 2451 of file bourdoncle.c.

{
  bool one_kind_only_p = false;
  bool is_true_successor_p = true;
  bool real_successor_found_p = false;
  list succs = control_successors(c);
 
  pips_assert("c is a test", control_test_p(c));
 
  MAP(CONTROL, s, {
    if(is_true_successor_p && true_p) {
      real_successor_found_p |= !meaningless_control_p(s);
    }
    else {
      one_kind_only_p &= meaningless_control_p(s);
    }
  }, succs);
 
  one_kind_only_p &= real_successor_found_p;
 
  return one_kind_only_p;
}

References CONTROL, control_successors, control_test_p(), MAP, meaningless_control_p(), and pips_assert.

Referenced by false_successors_only_p(), and true_successors_only_p().

Here is the call graph for this function:

Here is the caller graph for this function:

partition_to_unstructured()

unstructured partition_to_unstructured	(	control	vertex,
		list	partition
	)

Build a new unstructured (CFG) for partition.

vertex is the entry and exit point. New nodes must be allocated because the parent graph is untouched. vertex is supposed to be included into partition.

Create the translation table replicate_map

Generate new unstructured with relevant entry and exit node vertex

Update arcs

Update predecessors

The only predecessors that are useful are in partition

This predecessor is irrelevant

Handle successors

This successor is irrelevant but irrelevant true branches must be preserved

A second irrelevant successor is not needed. But are we ready to have IF nodes with only one successor?

useless = CONS(CONTROL, old_c, useless);

Parameters

vertex	ertex
partition	artition

Definition at line 1053 of file bourdoncle.c.

{
  unstructured new_u = unstructured_undefined;
  list useless = NIL;
 
  replicate_map = hash_table_make(hash_pointer, 0);
 
  /* Create the translation table replicate_map */
  MAP(CONTROL, c,
  {
    (void) control_shallow_copy(c);
  }
      , partition);
 
  /* Generate new unstructured with relevant entry and exit node vertex */
  new_u = make_unstructured(control_to_replicate(vertex),
                            control_to_replicate(vertex));
 
  /* Update arcs */
 
  /* Update predecessors */
  MAP(CONTROL, c,
  {
    control c_new = control_to_replicate(c);
 
    /* The only predecessors that are useful are in partition */
    MAPL(c_c,
    {
      control old_c = CONTROL(CAR(c_c));
      control new_c = control_undefined;
 
      if(gen_in_list_p(old_c, partition)) {
        new_c = hash_get(replicate_map, (void *) old_c);
        pips_assert("new_c is defined", new_c!=(control) HASH_UNDEFINED_VALUE);
        CONTROL_(CAR(c_c)) = new_c;
      }
      else {
        /* This predecessor is irrelevant */
        useless = CONS(CONTROL, old_c, useless);
      }
    }
         , control_predecessors(c_new));
 
    gen_list_and_not(&control_predecessors(c_new), useless);
    gen_free_list(useless);
    useless = NIL;
 
    /* Handle successors */
    MAPL(c_c,
    {
      control old_c = CONTROL(CAR(c_c));
      control new_c = control_undefined;
 
      if(gen_in_list_p(old_c, partition)) {
        new_c = hash_get(replicate_map, (void *) old_c);
        pips_assert("new_c is defined",
                    new_c!=(control) HASH_UNDEFINED_VALUE);
      }
      else {
        pips_assert("If a successor is not in partition,"
                    " then there must be two successors",
                    gen_length(control_successors(c_new))==2);
        /* This successor is irrelevant but irrelevant true branches must
           be preserved */
        if(c_c==control_successors(c_new)) {
          pips_assert("The second successor is in partition and has been copied",
                      gen_in_list_p(CONTROL(CAR(CDR(c_c))),partition) );
          new_c = make_meaningless_control(CONS(CONTROL, c_new, NIL), NIL);
        }
        else {
          /* A second irrelevant successor is not needed. But are we ready
             to have IF nodes with only one successor? */
          /* useless = CONS(CONTROL, old_c, useless); */
          new_c = make_meaningless_control(CONS(CONTROL, c_new, NIL), NIL);
        }
      }
        
      if(!control_undefined_p(new_c))
        CONTROL_(CAR(c_c)) = new_c;
    }
         , control_successors(c_new));
  }
      , partition);
 
  /*
    control_predecessors(c_new) = gen_list_and_not(control_predecessors(c_new), useless);
    gen_free_list(useless);
    useless = NIL;
  */
 
  hash_table_free(replicate_map);
  replicate_map = hash_table_undefined;
 
  return new_u;
}

References CAR, CDR, CONS, CONTROL, CONTROL_, control_predecessors, control_shallow_copy(), control_successors, control_to_replicate(), control_undefined, control_undefined_p, gen_free_list(), gen_in_list_p(), gen_length(), gen_list_and_not(), hash_get(), hash_pointer, hash_table_free(), hash_table_make(), hash_table_undefined, HASH_UNDEFINED_VALUE, make_meaningless_control(), make_unstructured(), MAP, MAPL, NIL, pips_assert, replicate_map, unstructured_undefined, and useless().

Here is the call graph for this function:

proper_cycle_head_p()

bool proper_cycle_head_p	(	control	c,
		hash_table	scc_map
	)

This node is really the head of a cycle (red on daVinci pictures).

Parameters

scc_map

cc_map

Definition at line 2405 of file bourdoncle.c.

{
  bool is_proper_cycle_head_p = false;
 
    HASH_MAP(n, u,
    {
      unstructured scc_u = (unstructured) u;
 
      if((control)c==unstructured_control(scc_u)) {
        is_proper_cycle_head_p = true;
        break;
      }
    }, scc_map);
  return is_proper_cycle_head_p;
}

References HASH_MAP, and unstructured_control.

Referenced by replicate_cycles().

Here is the caller graph for this function:

proper_cycle_head_to_scc()

unstructured proper_cycle_head_to_scc	(	control	h,
		hash_table	scc_map
	)

Retrieve a scc_u from its head.

Parameters

scc_map

cc_map

Definition at line 2368 of file bourdoncle.c.

{
  unstructured r_scc_u = unstructured_undefined;
 
  HASH_MAP(k_c, v_scc_u, {
    unstructured scc_u = (unstructured) v_scc_u;
 
    if(h==unstructured_control(scc_u)) {
      r_scc_u = scc_u;
      break;
    }
  }, scc_map);
 
  return r_scc_u;
}

References HASH_MAP, unstructured_control, and unstructured_undefined.

Referenced by dag_to_flow_sensitive_preconditions().

Here is the caller graph for this function:

reset_ctrl_graph()

void reset_ctrl_graph

(

void

)

restructure_control()

bool restructure_control

(

const string

mod_name

)

Try to simplify the control graph of a module by removing useless CONTINUEs, unreachable code, etc.

as in unspaghettify.

Do also test restructuring and control graph recursive graph decomposition.

Get the true resource, not a copy.

Reorder the module, because new statements may have been changed.

Parameters

mod_name

od_name

Definition at line 1492 of file unspaghettify.c.

{
   statement mod_stmt;
 
   /* Get the true resource, not a copy. */
   mod_stmt = (statement) db_get_memory_resource(DBR_CODE, mod_name, true);
   set_current_module_statement(mod_stmt);
 
   set_current_module_entity(local_name_to_top_level_entity(mod_name));
 
   restructure_statement(mod_stmt);
 
   /* Reorder the module, because new statements may have been
      changed. */
   module_reorder(mod_stmt);
 
   DB_PUT_MEMORY_RESOURCE(DBR_CODE, strdup(mod_name), mod_stmt);
 
   reset_current_module_statement();
   reset_current_module_entity();
 
   return true;
}

References db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, local_name_to_top_level_entity(), module_reorder(), reset_current_module_entity(), reset_current_module_statement(), restructure_statement(), set_current_module_entity(), set_current_module_statement(), and strdup().

Here is the call graph for this function:

restructure_statement()

void restructure_statement

(

statement

mod_stmt

)

The real entry point of control graph restructuring:

Parameters

mod_stmt

od_stmt

Definition at line 1477 of file unspaghettify.c.

{
   currently_apply_test_restructuring = true;
   currently_apply_recursive_decomposition = true;
 
   unspaghettify_or_restructure_statement(mod_stmt);
}

References currently_apply_recursive_decomposition, currently_apply_test_restructuring, and unspaghettify_or_restructure_statement().

Referenced by restructure_control().

Here is the call graph for this function:

Here is the caller graph for this function:

set_ctrl_graph()

void set_ctrl_graph

(

controlmap

)

simple_restructure_statement()

void simple_restructure_statement

(

statement

mod_stmt

)

A simple cleaning of the control graph without major topological restructuring.

Used by example by PHRASE.

Parameters

mod_stmt

od_stmt

Definition at line 1435 of file unspaghettify.c.

{
  currently_apply_test_restructuring = false;
  currently_apply_recursive_decomposition = false;
 
  unspaghettify_or_restructure_statement(mod_stmt);
}

References currently_apply_recursive_decomposition, currently_apply_test_restructuring, and unspaghettify_or_restructure_statement().

Referenced by full_spaghettify(), identify_statements_to_distribute(), and safescale_distributor().

Here is the call graph for this function:

Here is the caller graph for this function:

statement_continued_p()

bool statement_continued_p

(

statement

s

)

Test if the execution goes on after the given statement.

For example it is false after a "return" in C

Definition at line 242 of file unreachable.c.

{
    if (bound_continued_p(s))
        return continued_p(s);
    else
        return false;
}

References continued_p.

statement_reachable_p()

bool statement_reachable_p

(

statement

s

)

Test if the given statement is reachable from some statements given at init_reachable(start)

Definition at line 234 of file unreachable.c.

{
    return reached_p(s);
}

References reached_p.

Referenced by statement_to_postcondition(), and statement_to_total_precondition().

Here is the caller graph for this function:

store_ctrl_graph()

void store_ctrl_graph	(	statement	,
		control
	)

Referenced by stmt_rewrite().

Here is the caller graph for this function:

store_or_update_ctrl_graph()

void store_or_update_ctrl_graph	(	statement	,
		control
	)

take_out_the_exit_node_if_not_a_continue()

statement take_out_the_exit_node_if_not_a_continue

(

statement

s

)

Extract the statement from an exit node of an unstructured statement if it is a useful statement.

Parameters

s	is the statement that contains an unstructured

Returns

the new restructured statement

The exit node is the landing pad of the control graph. But if it is not a continue, that means that its statement is a useful instruction at the end of the unstructured and we can take it out of the unstructured. We just return the statement directly containing the unstructured.

Right now, it does not extract a RETURN since as explained in ￜ PIPS: Internal Representation of Fortran and C Code ￜ about RETURN_LABEL_NAME in the Entities section, since a RETURN with a label at the exit of un unstructured is always the representation of a RETURN in Fortran unstructured code... So even for C code, a return stay inside an unstructured. RK does not think it is important anyway...

To return and keep track of the unstructured:

ifdebug(5) {

pips_debug(5,

"Statement at entry:\n");

print_statement(s);

}

First, linearize the exit statement since fuse_sequences_in_unstructured() may have gathered many statements in a messy way:

Then normalize to have only one non-sequence statement as the exit node:

Well, this should be always true if the sequence survived to clean_up_sequences_rewrite()...

Then, append the last statements at the end of the unstructured:

...followed by the last statements:

Fix the variables for the following pass:

Here the_exit_statement is not a sequence.

Put an empty exit node and keep the statement for the label:

Replace the unstructured by an unstructured followed by the out-keeped instruction:

Keep track of the statement number:

Heavily rely on a later clean_up_sequences to normalize the above...

Definition at line 734 of file unspaghettify.c.

{
    instruction i = statement_instruction(s);
 
    pips_assert("take_out_the_exit_node_if_not_a_continue :"
                "The statement must be an unstructured",
                instruction_unstructured_p(i));
 
    /* To return and keep track of the unstructured: */
    statement the_unstructured = s;
    unstructured u = instruction_unstructured(i);
    control exit_node = unstructured_exit(u);
    statement the_exit_statement = control_statement(exit_node);
    instruction the_exit_instruction;
 
    /* ifdebug(5) { */
    /*   pips_debug(5, */
    /*           "Statement at entry:\n"); */
    /*   print_statement(s); */
    /* } */
 
    /* First, linearize the exit statement since
       fuse_sequences_in_unstructured() may have gathered many
       statements in a messy way: */
    clean_up_sequences_internal(the_exit_statement);
    the_exit_instruction =
        statement_instruction(the_exit_statement);
 
    /* Then normalize to have only one non-sequence statement as the
       exit node: */
    if (instruction_sequence_p(the_exit_instruction)
        && !nop_statement_p(the_exit_statement)) {
        list first_statement_list;
        statement first_statement, last_statements;
 
        list the_statements =
            sequence_statements(instruction_sequence(the_exit_instruction));
        pips_assert("the_statements must be a true sequence",
                    gen_length(the_statements) >= 2);
 
        /* Well, this should be always true if the sequence
           survived to clean_up_sequences_rewrite()... */
        first_statement_list = the_statements;
        first_statement = STATEMENT(CAR(first_statement_list));
        the_statements = CDR(the_statements);
        CDR(first_statement_list) = NIL;
        gen_free_list(first_statement_list);
 
        last_statements = the_exit_statement;
        sequence_statements(instruction_sequence(the_exit_instruction)) =
            the_statements;
 
        control_statement(exit_node) = first_statement;
        /* Then, append the last statements at the end of the
           unstructured: */
        the_unstructured = instruction_to_statement(i);
        statement_instruction(s) =
            make_instruction_block(CONS(STATEMENT,
                                        the_unstructured,
                                        /* ...followed by the last
                                           statements: */
                                        CONS(STATEMENT,
                                             last_statements,
                                             NIL)));
        /* Fix the variables for the following pass: */
        the_exit_statement = first_statement;
        the_exit_instruction = statement_instruction(the_exit_statement);
    }
    /* Here the_exit_statement is not a sequence. */
    if (! empty_statement_or_continue_p(the_exit_statement)
        && ! return_statement_p(the_exit_statement)) {
        statement new_statement;
        statement out_keeping;
        /* Put an empty exit node and keep the statement for the
           label: */
        statement_instruction(the_exit_statement) =
            make_continue_instruction();
        ifdebug (1)
            pips_assert("Statement is consistent", statement_consistent_p(the_exit_statement));
        /* Replace the unstructured by an unstructured followed by the
           out-keeped instruction: */
        new_statement = instruction_to_statement(i);
        out_keeping = instruction_to_statement(the_exit_instruction);
        /* Keep track of the statement number: */
        statement_number(out_keeping) = statement_number(the_exit_statement);
        statement_instruction(the_unstructured) =
            make_instruction_block(CONS(STATEMENT,
                                        new_statement,
                                        CONS(STATEMENT, out_keeping, NIL)));
        the_unstructured = new_statement;
    }
    /* Heavily rely on a later clean_up_sequences to normalize the
       above... */
 
    ifdebug (1)
        pips_assert("Statement is consistent", statement_consistent_p(s));
 
    return the_unstructured;
}

References CAR, CDR, clean_up_sequences_internal(), CONS, control_statement, empty_statement_or_continue_p(), gen_free_list(), gen_length(), ifdebug, instruction_sequence, instruction_sequence_p, instruction_to_statement(), instruction_unstructured, instruction_unstructured_p, make_continue_instruction(), make_instruction_block(), NIL, nop_statement_p(), pips_assert, return_statement_p(), sequence_statements, STATEMENT, statement_consistent_p(), statement_instruction, statement_number, and unstructured_exit.

Referenced by recursively_restructure_an_unstructured().

Here is the call graph for this function:

Here is the caller graph for this function:

transform_a_for_loop_into_a_while_loop()

void transform_a_for_loop_into_a_while_loop

(

forloop

f

)

Try to to transform the C-like for-loops into Fortran-like do-loops.

Assume we are in a gen_recurse since we use gen_get_recurse_ancestor(f).

The forloop is freed and replaced by a while loop in the statement owning the for-loop

Get the instruction owning the forloop:

Get the statement owning instruction owning the forloop:

Get a sequence with a while-loop instead:

These fields have been re-used, so protect them from memory recycling:

We need to replace the for-loop instruction by the sequence instruction. The cleaner way should be to delete the first one and make the other one, but since we are in a gen_recurse() and we iterate on the first one, it is dangerous. Well, I've tried and it works, but valgrind complains a bit. :-)

So change the type of the instruction on the fly instead:

And discard the old for:

Since we have replaced a statement that may have comments and labels by a sequence, do not forget to forward them where they can be:

FI: one issue: st is an ancestor of the current object and some of its pointers are going to be modified although they are being processed by gen_recurse()...

Removed useless instructions that may remain:

ifdebug(5) {

print_statement(st);

pips_debug(5, "Exiting with statement\n");

}

Definition at line 876 of file for_to_do_or_while_loops.c.

                                                  {
  pips_debug(5, "Begin\n");
 
  /* Get the instruction owning the forloop: */
  instruction i = (instruction) gen_get_recurse_ancestor(f);
  /* Get the statement owning instruction owning the forloop: */
  statement st = (statement) gen_get_recurse_ancestor(i);
 
  /* Get a sequence with a while-loop instead: */
  sequence wls = for_to_while_loop_conversion(forloop_initialization(f),
                                              forloop_condition(f),
                                              forloop_increment(f),
                                              forloop_body(f),
                                              statement_extensions(st));
 
  /* These fields have been re-used, so protect them from memory
     recycling: */
  forloop_initialization(f) = expression_undefined;
  forloop_condition(f) = expression_undefined;
  forloop_increment(f) = expression_undefined;
  forloop_body(f) = statement_undefined;
 
  /* We need to replace the for-loop instruction by the sequence
     instruction. The cleaner way should be to delete the first one and
     make the other one, but since we are in a gen_recurse() and we
     iterate on the first one, it is dangerous. Well, I've tried and it
     works, but valgrind complains a bit. :-)
 
     So change the type of the instruction on the fly instead: */
  instruction_tag(i) = is_instruction_sequence;
  instruction_sequence(i) = wls;
  /* And discard the old for: */
  free_forloop(f);
 
  /* Since we have replaced a statement that may have comments and labels
     by a sequence, do not forget to forward them where they can be: */
  /* FI: one issue: st is an ancestor of the current object and some
     of its pointers are going to be modified although they are being
     processed by gen_recurse()... */
  fix_sequence_statement_attributes(st);
 
  /* Removed useless instructions that may remain: */
  clean_up_sequences(st);
 
  /* ifdebug(5) { */
  /*   print_statement(st); */
  /*   pips_debug(5, "Exiting with statement\n"); */
  /* } */
}

References clean_up_sequences(), expression_undefined, f(), fix_sequence_statement_attributes(), for_to_while_loop_conversion(), forloop_body, forloop_condition, forloop_increment, forloop_initialization, free_forloop(), gen_get_recurse_ancestor(), instruction_sequence, instruction_tag, is_instruction_sequence, pips_debug, statement_extensions, and statement_undefined.

Here is the call graph for this function:

transform_a_for_loop_statement_into_a_while_loop()

void transform_a_for_loop_statement_into_a_while_loop

(

statement

st

)

Same as above, but with no calls to ancestors.

Get the instruction owning the forloop:

Get the statement owning instruction owning the forloop:

Get a sequence with a while-loop instead:

These fields have been re-used, so protect them from memory recycling:

We need to replace the for-loop instruction by the sequence instruction. The cleaner way should be to delete the first one and make the other one, but since we are in a gen_recurse() and we iterate on the first one, it is dangerous. Well, I've tried and it works, but valgrind complains a bit. :-)

So change the type of the instruction on the fly instead:

And discard the old for:

Since we have replaced a statement that may have comments and labels by a sequence, do not forget to forward them where they can be:

FI: one issue: st is an ancestor of the current object and some of its pointers are going to be modified although they are being processed by gen_recurse()...

Removed useless instructions that may remain:

ifdebug(5) {

print_statement(st);

pips_debug(5, "Exiting with statement\n");

}

Parameters

st

t

Definition at line 928 of file for_to_do_or_while_loops.c.

                                                               {
  if(forloop_statement_p(st)) {
    pips_debug(5, "Begin\n");
 
    /* Get the instruction owning the forloop: */
    //instruction i = (instruction) gen_get_recurse_ancestor(f);
    instruction i = statement_instruction(st);
    /* Get the statement owning instruction owning the forloop: */
    //statement st = (statement) gen_get_recurse_ancestor(i);
    forloop f = instruction_forloop(i);
 
    /* Get a sequence with a while-loop instead: */
    sequence wls = for_to_while_loop_conversion(forloop_initialization(f),
                                                forloop_condition(f),
                                                forloop_increment(f),
                                                forloop_body(f),
                                                statement_extensions(st));
 
    /* These fields have been re-used, so protect them from memory
       recycling: */
    forloop_initialization(f) = expression_undefined;
    forloop_condition(f) = expression_undefined;
    forloop_increment(f) = expression_undefined;
    forloop_body(f) = statement_undefined;
 
    /* We need to replace the for-loop instruction by the sequence
       instruction. The cleaner way should be to delete the first one and
       make the other one, but since we are in a gen_recurse() and we
       iterate on the first one, it is dangerous. Well, I've tried and it
       works, but valgrind complains a bit. :-)
 
       So change the type of the instruction on the fly instead: */
    instruction_tag(i) = is_instruction_sequence;
    instruction_sequence(i) = wls;
    /* And discard the old for: */
    free_forloop(f);
 
    /* Since we have replaced a statement that may have comments and labels
       by a sequence, do not forget to forward them where they can be: */
    /* FI: one issue: st is an ancestor of the current object and some
       of its pointers are going to be modified although they are being
       processed by gen_recurse()... */
    fix_sequence_statement_attributes(st);
 
    /* Removed useless instructions that may remain: */
    clean_up_sequences(st);
 
    /* ifdebug(5) { */
    /*   print_statement(st); */
    /*   pips_debug(5, "Exiting with statement\n"); */
    /* } */
  }
}

References clean_up_sequences(), expression_undefined, f(), fix_sequence_statement_attributes(), for_to_while_loop_conversion(), forloop_body, forloop_condition, forloop_increment, forloop_initialization, forloop_statement_p(), free_forloop(), instruction_forloop, instruction_sequence, instruction_tag, is_instruction_sequence, pips_debug, statement_extensions, statement_instruction, and statement_undefined.

Referenced by for_loop_to_while_loop(), and new_controlizer().

Here is the call graph for this function:

Here is the caller graph for this function:

true_successors_only_p()

bool true_successors_only_p

(

control

c

)

Definition at line 2474 of file bourdoncle.c.

{
  bool true_only_p = false;
  true_only_p = one_successor_kind_only_p(c, true);
  return true_only_p;
}

References one_successor_kind_only_p().

Referenced by dag_to_flow_sensitive_preconditions(), and process_ready_node().

Here is the call graph for this function:

Here is the caller graph for this function:

try_to_transform_a_for_loop_into_a_do_loop()

void try_to_transform_a_for_loop_into_a_do_loop

(

forloop

f

)

Try to to transform the C-like for-loops into Fortran-like do-loops.

Assume we are in a gen_recurse since we use gen_get_recurse_ancestor(f).

Get the englobing statement of the "for" assuming we are called from a gen_recurse()-like function:

Definition at line 740 of file for_to_do_or_while_loops.c.

                                                      {
 
    /* Get the englobing statement of the "for" assuming we are called
       from a gen_recurse()-like function: */
    statement parent=
        (statement)gen_get_recurse_ancestor(
                (instruction)gen_get_recurse_ancestor(f));
 
    sequence new_l = for_to_do_loop_conversion(f,parent);
 
    if (!sequence_undefined_p(new_l)) {
        pips_debug(3, "do-loop has been generated.\n");
        statement_instruction(parent)=make_instruction_sequence(new_l);
        forloop_body(f)=statement_undefined;
        forloop_condition(f)=expression_undefined;
        forloop_increment(f)=expression_undefined;
        forloop_initialization(f)=expression_undefined;
        free_forloop(f);
    }
}

References expression_undefined, f(), for_to_do_loop_conversion(), forloop_body, forloop_condition, forloop_increment, forloop_initialization, free_forloop(), gen_get_recurse_ancestor(), make_instruction_sequence(), pips_debug, sequence_undefined_p, statement_instruction, and statement_undefined.

Referenced by for_loop_to_do_loop(), and new_controlizer().

Here is the call graph for this function:

Here is the caller graph for this function:

unspaghettify()

bool unspaghettify

(

const string

mod_name

)

Try to simplify the control graph of a module by removing useless CONTINUEs, unreachable code.

Try to structure a little bit more and so on according to some properties.

Unspaguettify is now targetted to be included in the controlizer.

Get the true resource, not a copy.

Reorder the module, because new statements may have been changed.

Parameters

mod_name

od_name

Definition at line 1450 of file unspaghettify.c.

{
   statement mod_stmt;
 
   /* Get the true resource, not a copy. */
   mod_stmt = (statement) db_get_memory_resource(DBR_CODE, mod_name, true);
   set_current_module_statement(mod_stmt);
 
   set_current_module_entity(local_name_to_top_level_entity(mod_name));
 
   unspaghettify_statement(mod_stmt);
 
   /* Reorder the module, because new statements may have been
      changed. */
   module_reorder(mod_stmt);
 
   DB_PUT_MEMORY_RESOURCE(DBR_CODE, strdup(mod_name), mod_stmt);
 
   reset_current_module_statement();
   reset_current_module_entity();
 
   return true;
}

References db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, local_name_to_top_level_entity(), module_reorder(), reset_current_module_entity(), reset_current_module_statement(), set_current_module_entity(), set_current_module_statement(), strdup(), and unspaghettify_statement().

Here is the call graph for this function:

unspaghettify_or_restructure_statement()

void unspaghettify_or_restructure_statement

(

statement

mod_stmt

)

The entry point common to unspaghettify or restructure a module:

Track the number of restructurations done for a fix point:

To track the number of restructuring iterations:

ifdebug(5) {

pips_debug(5, "Statement before unspaghettify_or_restructure_statement:\n");

print_statement(mod_stmt);

}

Split the recursion in three parts to fit in my brain:

First, clean up easy things done by the controlizer:

Then try to hierarchize the control flow:

Now apply some local rule, such as if/then/else restructuring and so on:

End by removing parasitic sequences:

If something changed, retry further restructuring:

ifdebug(5) {

pips_debug(5, "Statement after unspaghettify_or_restructure_statement:\n");

print_statement(mod_stmt);

}

Parameters

mod_stmt

od_stmt

Definition at line 1330 of file unspaghettify.c.

{
  /* Track the number of restructurations done for a fix point: */
  int nr = 0;
  int old_nr;
  /* To track the number of restructuring iterations: */
  int iter = 0;
 
  // Note that this debug is not controlled by "UNSPAGHETTIFY_DEBUG_LEVEL":
  /* ifdebug(5) { */
  /*   pips_debug(5, "Statement before unspaghettify_or_restructure_statement:\n"); */
  /*   print_statement(mod_stmt); */
  /* } */
 
  debug_on("UNSPAGHETTIFY_DEBUG_LEVEL");
 
  ifdebug (1)
    pips_assert("Statement is consistent", statement_consistent_p(mod_stmt));
 
  if (get_bool_property("GATHER_FORMATS_AT_BEGINNING"))
    put_formats_at_module_beginning(mod_stmt);
  else if (get_bool_property("GATHER_FORMATS_AT_END"))
    put_formats_at_module_end(mod_stmt);
 
  ifdebug (1)
    pips_assert("Statement is consistent", statement_consistent_p(mod_stmt));
 
  initialize_unspaghettify_statistics();
 
  do {
    old_nr = nr;
    /* Split the recursion in three parts to fit in my brain: */
    /* First, clean up easy things done by the controlizer: */
    gen_recurse(mod_stmt, statement_domain,
                gen_true, clean_up_control);
 
    ifdebug (1)
      pips_assert("Statement is consistent", statement_consistent_p(mod_stmt));
 
    if (currently_apply_recursive_decomposition) {
      /* Then try to hierarchize the control flow: */
      gen_recurse(mod_stmt, unstructured_domain,
                  gen_true, control_graph_recursive_decomposition);
 
      ifdebug (1)
        pips_assert("Statement is consistent",
                    statement_consistent_p(mod_stmt));
    }
 
    /* Now apply some local rule, such as if/then/else restructuring
       and so on: */
    gen_recurse(mod_stmt, statement_domain,
                gen_true, recursively_restructure_an_unstructured);
 
    ifdebug (1)
      pips_assert("Statement is consistent", statement_consistent_p(mod_stmt));
 
    if (get_bool_property("UNSPAGHETTIFY_WHILE_RECOVER"))
      gen_recurse(mod_stmt, unstructured_domain,
                  gen_true, recover_structured_while);
 
    /* End by removing parasitic sequences: */
    clean_up_sequences(mod_stmt);
 
    ifdebug (1)
      pips_assert("Statement is consistent", statement_consistent_p(mod_stmt));
 
    /* If something changed, retry further restructuring: */
    nr = total_number_of_restructurations();
    ifdebug(2)
      display_unspaghettify_statistics();
  } while (nr != old_nr && ++iter < N_ITER_RESTRUCTURE_FIX_POINT);
 
  if (nr != old_nr)
    pips_user_warning("Possible infinite loop restructuring found.\n");
 
  pips_debug(2, "done\n");
 
  display_unspaghettify_statistics();
 
  debug_off();
  // Note that this debug is not controlled by "UNSPAGHETTIFY_DEBUG_LEVEL":
  /* ifdebug(5) { */
  /*   pips_debug(5, "Statement after unspaghettify_or_restructure_statement:\n"); */
  /*   print_statement(mod_stmt); */
  /* } */
}

References clean_up_control(), clean_up_sequences(), control_graph_recursive_decomposition(), currently_apply_recursive_decomposition, debug_off, debug_on, display_unspaghettify_statistics(), gen_recurse, gen_true(), get_bool_property(), ifdebug, initialize_unspaghettify_statistics(), N_ITER_RESTRUCTURE_FIX_POINT, pips_assert, pips_debug, pips_user_warning, put_formats_at_module_beginning(), put_formats_at_module_end(), recover_structured_while(), recursively_restructure_an_unstructured(), statement_consistent_p(), statement_domain, total_number_of_restructurations(), and unstructured_domain.

Referenced by restructure_statement(), simple_restructure_statement(), and unspaghettify_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

unspaghettify_statement()

void unspaghettify_statement

(

statement

mod_stmt

)

The real entry point of unspaghettify:

Parameters

mod_stmt

od_stmt

Definition at line 1421 of file unspaghettify.c.

{
   currently_apply_test_restructuring =
       get_bool_property("UNSPAGHETTIFY_TEST_RESTRUCTURING");
   currently_apply_recursive_decomposition =
       get_bool_property("UNSPAGHETTIFY_RECURSIVE_DECOMPOSITION");
 
   unspaghettify_or_restructure_statement(mod_stmt);
}

References currently_apply_recursive_decomposition, currently_apply_test_restructuring, get_bool_property(), STUB_ERROR, and unspaghettify_or_restructure_statement().

Referenced by controlizer(), copy_value_of_write(), copy_value_of_write_with_cumulated_regions(), mpi_conversion(), new_controlizer(), ProcessEntry(), and unspaghettify().

Here is the call graph for this function:

Here is the caller graph for this function:

unstructured_consistency_p()

bool unstructured_consistency_p	(	unstructured	u,
		bool	assert_p
	)

cfg.c

cfg.c

Francois Irigoin, 1997. Check some nice properties expected to be true after a powerful enough controlizer phase.

The calls to pips_assert could be replaced by calls to user_warning, the control graph could be printed out before core dumping,...

See also check_control_coherency().

the exit and entry nodes must be different or the unstructured would have been reduced to one structured statement

The entry node must have at least one predecessor: else it should have been moved out of the unstructured. Note that it has in fact TWO predecessors since it is the unstructured entry point.

The exit node should have no successors: its real successor is the statement following the unstructured

The exit node should not be a test: else one of its successors should be control_undefined since it would be outside of the unstructured, or the exit condition would be unknown.

The exit node may have no predecessor because an infinite loop appears in the code. Or it is a successor of the entry node.

RK: ??? If the exit node is unreachable, it should be a CONTINUE Since a CONTINUE has no effects, it does not perturb analyses even if they do not check reachability. RK: The NOP might be the empty sequence instead of a CONTINUE?

If the exit node has only one predecessor, it should be a test or the exit node would have been moved outside of the unstructured.

Since sequences are merged into a unique node, if a node c1 has only one successor c2, and if c2 has only one predecessor c3, c3 must be c1 and either c1 is the exit node which is impossible because there would be no exit condition and the exit node would have a successor, c2, or c2 is the entry node. So c2 must be the entry node.

Well, this is not true because only tests can have two successors. hence, a test node cannot be merged.

Parameters

assert_p

ssert_p

Definition at line 52 of file cfg.c.

{
    control entry_node = unstructured_control(u);
    control exit_node = unstructured_exit(u);
    bool consistency_p = true;
    list nodes = NIL;
 
    forward_control_map_get_blocs(entry_node, &nodes);
 
    /* the exit and entry nodes must be different or the
     * unstructured would have been reduced to one structured statement
     */
    if(exit_node==entry_node) {
        consistency_p = false;
        if(assert_p) pips_assert("Entry and exit nodes are different", false);
    }
 
    /* The entry node must have at least one predecessor:
     * else it should have been moved out of the unstructured.
     * Note that it has in fact TWO predecessors since it is the
     * unstructured entry point.
     */
    if(consistency_p && ENDP(control_predecessors(entry_node))) {
        consistency_p = false;
        if(assert_p) pips_assert("Entry node has at least one predecessor", false);
    }
 
    /* The exit node should have no successors: its real successor
     * is the statement following the unstructured
     */
    if(consistency_p && !ENDP(control_successors(exit_node))) {
        consistency_p = false;
        if(assert_p) pips_assert("Exit node has no successor", false);
    }
 
    /* The exit node should not be a test:
     * else one of its successors should be control_undefined
     * since it would be outside of the unstructured, or the
     * exit condition would be unknown.
     */
    if(consistency_p) {
        statement exit_s = control_statement(exit_node);
        if(statement_test_p(exit_s)) {
            consistency_p = false;
            if(assert_p) pips_assert("Exit node is not a test", false);
        }
    }
 
    /* The exit node may have no predecessor because an infinite loop
     * appears in the code. Or it is a successor of the entry node.
     */
    if(consistency_p && !ENDP(control_predecessors(exit_node))) {
        if(gen_find_eq(exit_node, nodes)!=exit_node) {
            consistency_p = false;
            if(assert_p) pips_assert("Exit node has predecessors but is unreachable", false);
        }
    }
 
    /* RK: ??? If the exit node is unreachable, it should be a CONTINUE
     * Since a CONTINUE has no effects, it does not perturb analyses even
     * if they do not check reachability.
     * RK: The NOP might be the empty sequence instead of a CONTINUE?
     */
    if(consistency_p && ENDP(control_predecessors(exit_node))) {
        statement exit_s = control_statement(exit_node);
 
        if(!continue_statement_p(exit_s)) {
            consistency_p = false;
            if(assert_p) pips_assert("Unreachable exit node is a CONTINUE statement", false);
        }
    }
 
    /* If the exit node has only one predecessor, it should
     * be a test or the exit node would have been moved outside of
     * the unstructured.
     */
    if(consistency_p && gen_length(control_predecessors(exit_node))==1) {
        control c = CONTROL(CAR(control_predecessors(exit_node)));
        statement s = control_statement(c);
 
        if(!statement_test_p(s)) {
            consistency_p = false;
            if(assert_p) pips_assert("Unique predecessor of exit node is a test", false);
        }
    }
 
    /* Since sequences are merged into a unique node, if a node c1 has only one
     * successor c2, and if c2 has only one predecessor c3, c3 must be c1
     * and either c1 is the exit node which is impossible because there
     * would be no exit condition and the exit node would have a
     * successor, c2, or c2 is the entry node. So c2 must be the entry node.
     *
     * Well, this is not true because only tests can have two successors.
     * hence, a test node cannot be merged.
     */
    MAP(CONTROL, c1, {
        if(gen_length(control_successors(c1))==1) {
            control c2 = CONTROL(CAR(control_successors(c1)));
            statement s2 = control_statement(c2);
 
            if(gen_length(control_predecessors(c2))==1) {
                control c3 = CONTROL(CAR(control_predecessors(c2)));
                if(c1!=c3) {
                    consistency_p = false;
                    if(assert_p) {
                        (void) fprintf(stderr,
                                       "\nEntry node: %p\nExit node: %p\n"
                                       "c1 node: %p\nc2 node: %p\nc3 node: %p\n",
                                       entry_node, exit_node, c1, c2, c3);
                        display_linked_control_nodes(entry_node);
                        pips_assert("c3, the unique predecessor of the unique successor of c1, is c1",
                                    false);
                    }
                }
                else if(c2!=entry_node && !statement_test_p(s2)) {
                    consistency_p = false;
                    if(assert_p) {
                        (void) fprintf(stderr,
                                       "\nEntry node: %p\nExit node: %p\nc1 node: %p\nc2 node: %p\n\n",
                                       entry_node, exit_node, c1, c2);
                        display_linked_control_nodes(entry_node);
                        pips_assert("c2 is the unique successor of c1. "
                                    "c2 has c1 as unique predecessor. c2 must be the entry node",
                                    false);
                    }
                }
            }
 
        }
        }, nodes)
 
    gen_free_list(nodes);
 
    return consistency_p;
}

References CAR, continue_statement_p(), CONTROL, control_predecessors, control_statement, control_successors, display_linked_control_nodes(), ENDP, forward_control_map_get_blocs(), fprintf(), gen_find_eq(), gen_free_list(), gen_length(), MAP, NIL, pips_assert, statement_test_p(), unstructured_control, and unstructured_exit.

Referenced by unstructured_while_p().

Here is the call graph for this function:

Here is the caller graph for this function:

unstructured_shallow_copy()

unstructured unstructured_shallow_copy	(	unstructured	u,
		hash_table	ancestor_map
	)

Do not go down into nested unstructured and replicate all control nodes

Update predecessor and successor arcs of the new control nodes to point to the new control nodes using the global conversion mapping replicate_map

Generate new unstructured with relevant entry and exit nodes

Generate ancestor_map as the inverse function of replicate_map

Parameters

ancestor_map

ncestor_map

Definition at line 1009 of file bourdoncle.c.

{
  unstructured new_u = unstructured_undefined;
 
  pips_assert("replicate_map is undefined",
              hash_table_undefined_p(replicate_map));
 
  replicate_map = hash_table_make(hash_pointer, 0);
 
  /* Do not go down into nested unstructured and replicate all control
     nodes */
  gen_multi_recurse(u, statement_domain, gen_false, gen_null,
                    control_domain, gen_true, control_shallow_copy, NULL);
 
  ifdebug(2) print_replicate_map();
 
  /* Update predecessor and successor arcs of the new control nodes to
     point to the new control nodes using the global conversion mapping
     replicate_map */
  HASH_MAP(old_c, new_c,
  {
    control_translate_arcs((control) new_c);
  }
           , replicate_map);
 
  /* Generate new unstructured with relevant entry and exit nodes */
  new_u = make_unstructured(control_to_replicate(unstructured_control(u)),
                            control_to_replicate(unstructured_exit(u)));
 
  /* Generate ancestor_map as the inverse function of replicate_map */
  HASH_MAP(old_n, new_n,{
    add_child_parent_pair(ancestor_map, (control) new_n, (control) old_n);
  }, replicate_map);
 
  hash_table_free(replicate_map);
  replicate_map = hash_table_undefined;
 
  return new_u;
}

References add_child_parent_pair(), control_domain, control_shallow_copy(), control_to_replicate(), control_translate_arcs(), gen_false(), gen_multi_recurse(), gen_null(), gen_true(), HASH_MAP, hash_pointer, hash_table_free(), hash_table_make(), hash_table_undefined, hash_table_undefined_p, ifdebug, make_unstructured(), pips_assert, print_replicate_map(), replicate_map, statement_domain, unstructured_control, unstructured_exit, and unstructured_undefined.

Referenced by bourdoncle_partition(), and replicate_cycles().

Here is the call graph for this function:

Here is the caller graph for this function:

unstructured_while_p()

bool unstructured_while_p

(

unstructured

u

)

Test if an unstructured is found to be like a structured while-loop.

Make sure that the unstructured has been "normalized"

while_p = unstructured_consistency_p(u, true);

An unstructured is a while loop if and only if the exit node has only one predecessor and if the entry node is a successor of the predecessor of the exit node.

A loop with two exit conditions is not recognized as a while loop.

A loop with an exit test on entry, a final exit test (do...while) or an exit test anywhere is recognized as a while loop.

Definition at line 191 of file cfg.c.

{
    control entry_node = unstructured_control(u);
    control exit_node = unstructured_exit(u);
    bool while_p = false;
 
    ifdebug(5) {
        debug(5, "unstructured_while_p", "Begin with graph\n");
        (void) fprintf(stderr,
                       "\nEntry node: %p\nExit node: %p\n\n",
                       entry_node, exit_node);
        display_linked_control_nodes(entry_node);
    }
 
    /* Make sure that the unstructured has been "normalized" */
    /* while_p = unstructured_consistency_p(u, true); */
    while_p = unstructured_consistency_p(u, false);
 
    /* An unstructured is a while loop if and only if the exit node
     * has only one predecessor and if the entry node is a successor
     * of the predecessor of the exit node.
     *
     * A loop with two exit conditions is not recognized as a while loop.
     *
     * A loop with an exit test on entry, a final exit test (do...while) or
     * an exit test anywhere is recognized as a while loop.
     */
 
    if(while_p && gen_length(control_predecessors(exit_node))==1) {
        control pred = CONTROL(CAR(control_predecessors(exit_node)));
        list succs = NIL;
 
        forward_control_map_get_blocs(pred, &succs);
 
        if(gen_find_eq(entry_node, succs)==entry_node) {
            while_p = true;
        }
        gen_free_list(succs);
    }
    else {
        while_p = false;
    }
 
    debug(5, "unstructured_while_p", "End with while_p=%s\n", bool_to_string(while_p));
 
    return while_p;
}

References bool_to_string(), CAR, CONTROL, control_predecessors, debug(), display_linked_control_nodes(), forward_control_map_get_blocs(), fprintf(), gen_find_eq(), gen_free_list(), gen_length(), ifdebug, NIL, unstructured_consistency_p(), unstructured_control, and unstructured_exit.

Referenced by instruction_flt(), and instruction_rwt().

Here is the call graph for this function:

Here is the caller graph for this function:

unsugared_whileloop_header()

statement unsugared_whileloop_header

(

statement

)

update_ctrl_graph()

void update_ctrl_graph	(	statement	,
		control
	)

Variable Documentation

vcid_control_controlizer

char vcid_control_controlizer[]

extern

cproto-generated files

controlizer.c

cproto-generated files

Definition at line 40 of file controlizer.c.

vcid_control_old_controlizer

char vcid_control_old_controlizer[]

extern

old_controlizer.c

Definition at line 29 of file old_controlizer.c.

vcid_unspaghettify

char vcid_unspaghettify[]

extern

unspaghettify.c

unspaghettify.c

Definition at line 30 of file unspaghettify.c.