unstructured.c File Reference

#include <stdlib.h>
#include <stdio.h>
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "ri-util.h"
#include "effects-util.h"
#include "misc.h"
#include "properties.h"
#include "prettyprint.h"
#include "points-to.h"

Include dependency graph for unstructured.c:

Go to the source code of this file.

Functions
static bool	statement_equal_p (statement s1, statement s2)
bool	control_in_set_p (control c, set s)
	test if a control belong to a set More...
bool	control_equal_p (const void *vc1, const void *vc2)
_uint	control_rank (const void *vc, size_t size)
	create a key which is the statement number More...
bool	Ready_p (control c, set Processed, set Reachable)
	A node is ready to be processed if its predecessors are not reachable or processed. More...
set	ready_to_be_processed_set (control n, set Processed, set Reachable)
	A set containing all the successors of n that are ready to be processed. More...
static pt_map	control_to_points_to (control c, pt_map in, __attribute__((__unused__)) bool store)
static pt_map	cyclic_graph_to_points_to (set ctrls, pt_map in, bool store __attribute__((unused)))
pt_map	new_points_to_unstructured (unstructured uns, pt_map pt_in_g, bool __attribute__((__unused__)) store)

Function Documentation

control_equal_p()

bool control_equal_p	(	const void *	vc1,
		const void *	vc2
	)

Parameters

vc1	c1
vc2	c2

Definition at line 71 of file unstructured.c.

{
  control c1 = (control)vc1;
  control c2 = (control)vc2;
  statement s1 = control_statement(c1);
  statement s2 = control_statement(c2);
  
  return statement_ordering(s1) == statement_ordering(s2);
 
}

References control_statement, s1, and statement_ordering.

Referenced by new_points_to_unstructured().

Here is the caller graph for this function:

control_in_set_p()

bool control_in_set_p	(	control	c,
		set	s
	)

test if a control belong to a set

unstructured.c

Definition at line 61 of file unstructured.c.

{
  bool  in_p = false;
  SET_FOREACH(control, n, s) {
    if(statement_equal_p(control_statement(c), control_statement(n)))
      in_p = true;
  }
  return in_p;
}

References control_statement, SET_FOREACH, and statement_equal_p().

Referenced by new_points_to_unstructured().

Here is the call graph for this function:

Here is the caller graph for this function:

control_rank()

_uint control_rank	(	const void *	vc,
		size_t	size
	)

create a key which is the statement number

Parameters

vc	c
size	ize

Definition at line 83 of file unstructured.c.

{
  control c = (control)vc;
  statement s = control_statement(c);
  // FI: use asprintf?
  extern char * int2a(int);
  string key = strdup(int2a(statement_ordering(s)));
  return hash_string_rank(key,size);
}

References control_statement, hash_string_rank(), int2a(), statement_ordering, and strdup().

Referenced by new_points_to_unstructured().

Here is the call graph for this function:

Here is the caller graph for this function:

control_to_points_to()

static pt_map control_to_points_to ( control  c, pt_map  in, __attribute__((__unused__)) bool  store  )

static

Definition at line 131 of file unstructured.c.

{
  pt_map out = new_pt_map();
 
  out = points_to_graph_assign(out, in);
  statement s = control_statement(c);
  out =  statement_to_points_to(s, in); // FI: seems to anihilate
  // previous assignment to out
 
  list Succ_l = gen_full_copy_list(control_successors(c));
  FOREACH(control, ctr, Succ_l) {
    out =  statement_to_points_to(control_statement(ctr), out);
    }
  out = merge_points_to_graphs(in, out);
 
  return out;
}

References control_statement, control_successors, FOREACH, gen_full_copy_list(), merge_points_to_graphs(), new_pt_map, out, points_to_graph_assign(), and statement_to_points_to().

Referenced by new_points_to_unstructured().

Here is the call graph for this function:

Here is the caller graph for this function:

cyclic_graph_to_points_to()

static pt_map cyclic_graph_to_points_to ( set  ctrls, pt_map  in, bool store   __attribute__(unused)  )

static

sequence seq = sequence_undefined;

seq_l = NIL,

Pred = set_assign_list(Pred, gen_full_copy_list(pred));

Definition at line 160 of file unstructured.c.

{
  pt_map out = new_pt_map();
  set Pred = set_make(set_pointer);
  set Succ = set_make(set_pointer);
  /* sequence seq = sequence_undefined; */
  list /* seq_l = NIL, */ succ = NIL, pred = NIL;
  out = points_to_graph_assign(out, in);
  SET_FOREACH(control, c, ctrls) {
    out = statement_to_points_to(control_statement(c), out);
    pred = control_predecessors(c);
    /* Pred = set_assign_list(Pred, gen_full_copy_list(pred)); */
  }
  FOREACH(control, ctr, pred) {
    Pred = set_add_element(Pred, Pred, (void*)ctr);
  }
  SET_FOREACH(control, p, Pred) {
    out = statement_to_points_to(control_statement(p), out);
    succ = gen_copy_seq(control_successors(p));
  }
  
  
  Succ = set_assign_list(Succ, succ);
  SET_FOREACH(control, s, Succ) {
    out = statement_to_points_to(control_statement(s), out);
  }
  return out;
}

References control_predecessors, control_statement, control_successors, FOREACH, gen_copy_seq(), new_pt_map, NIL, out, points_to_graph_assign(), set_add_element(), set_assign_list(), SET_FOREACH, set_make(), set_pointer, and statement_to_points_to().

Referenced by new_points_to_unstructured().

Here is the call graph for this function:

Here is the caller graph for this function:

new_points_to_unstructured()

pt_map new_points_to_unstructured	(	unstructured	uns,
		pt_map	pt_in_g,
		bool __attribute__((__unused__))	store
	)

Get all the nodes of the unstructured

Gel all the reachable nodes of the unstructured

if 0

#endif

The entry node is part of a cycle, rtbp is empty and the while loop below is soing to be skipped. Relation "out_g" must be properly initialized.

Pred = set_assign_list(Pred, gen_full_copy_list(Pred_l));

Definition at line 204 of file unstructured.c.

{
  set pt_in = points_to_graph_set(pt_in_g);
  set pt_in_n = set_generic_make(set_private, points_to_equal_p,
                                 points_to_rank);
  set out = set_generic_make(set_private, points_to_equal_p,
                             points_to_rank);
  pt_map out_g = new_pt_map();
  list Pred_l = NIL, nodes_l = NIL,  nodes_l_exit = NIL ;
  list blocs = NIL ;
  set Pred =  set_generic_make(set_private, control_equal_p,
                                 control_rank);
  set Nodes =  set_generic_make(set_private, control_equal_p,
                                 control_rank);
  set Reachable =  set_generic_make(set_private, control_equal_p,
                                 control_rank);
  set Processed =  set_generic_make(set_private, control_equal_p,
                                 control_rank);
  set UnProcessed = set_generic_make(set_private, control_equal_p,
                                 control_rank);
  set rtbp =  set_generic_make(set_private, control_equal_p,
                                 control_rank);
  set rtbp_tmp = set_generic_make(set_private, control_equal_p,
                                 control_rank);
  set inter =  set_generic_make(set_private, control_equal_p,
                                 control_rank);
  set tmp =  set_generic_make(set_private, control_equal_p,
                                 control_rank);
  control entry = unstructured_control(uns) ;
  control exit = unstructured_exit(uns) ;
  Pred_l = control_predecessors(entry);
  Pred = set_assign_list(Pred, gen_full_copy_list(Pred_l));
  list trail = unstructured_to_trail(uns);
 
  /* Get all the nodes of the unstructured*/
#if 0
  CONTROL_MAP(c, {
      ;
    }, entry, nodes_l) ;
#endif
  FOREACH(control, ctrl, trail) {
    Nodes = set_add_element(Nodes, Nodes, (void*)ctrl);
  }
#if 0
  CONTROL_MAP(c, {
      ;
    }, exit, nodes_l_exit) ;
#endif
  nodes_l = gen_nconc(nodes_l, nodes_l_exit);
 
  /* Gel all the reachable nodes of the unstructured */
/* #if 0 */
  FORWARD_CONTROL_MAP(c, {
      Reachable = set_add_element(Reachable, Reachable, (void*)c);
    }, entry, blocs) ;
/* #endif */
 
  bool inter_p = set_intersection_p(Reachable, Pred);
  if(!inter_p)
    set_add_element(rtbp, rtbp, (void*)entry);
  else {
    /* The entry node is part of a cycle, rtbp is empty and the while
       loop below is soing to be skipped. Relation "out_g" must be
       properly initialized. */
    out_g = full_copy_pt_map(pt_in_g);
  }
 
  while(!set_empty_p(rtbp)) {
    rtbp_tmp = set_assign(rtbp_tmp,rtbp);
    SET_FOREACH(control, n , rtbp) {
      // to test the control's equality, I test if their statements are equals
      if ( statement_ordering(control_statement(n)) == statement_ordering(control_statement(entry)) ) {
        pt_in_n = set_assign(pt_in_n, pt_in);
        out = set_assign(out, pt_in_n);
      }
      Pred_l = NIL;
      Pred_l = control_predecessors(n);
      FOREACH(control, ctr, Pred_l) {
        Pred = set_add_element(Pred, Pred, (void*)ctr);
      }
      set_clear(Pred);
      /* Pred = set_assign_list(Pred, gen_full_copy_list(Pred_l)); */
      inter = set_intersection(inter,Reachable, Pred);
      out_g = make_points_to_graph(false, out);
      SET_FOREACH(control, p , inter) {
        out_g = control_to_points_to(p, out_g, true);
      }
      out_g = control_to_points_to(n, out_g, true);
      if(!control_in_set_p(n, Processed))
        Processed = set_add_element(Processed,Processed, (void*)n );
      rtbp_tmp = set_del_element(rtbp_tmp,rtbp_tmp,(void*)n);
      rtbp_tmp = set_union(rtbp_tmp,rtbp_tmp,
                           ready_to_be_processed_set(n, Processed, Reachable));
      set_clear(rtbp);
      rtbp = set_assign(rtbp,rtbp_tmp);
    }
  }
 
  UnProcessed = set_difference(UnProcessed, Reachable, Processed);
  out_g = cyclic_graph_to_points_to(UnProcessed, out_g, store);
  tmp = set_difference(tmp, Nodes, Reachable);
  SET_FOREACH(control, cc, tmp) {
    pt_in_n = set_clear(pt_in_n);
    out_g = statement_to_points_to(control_statement(cc), out_g);
  }
 
  free(blocs);
  free(nodes_l);
  statement exit_s = control_statement(exit);
  out_g = merge_points_to_graphs(out_g, pt_in_g);
  out_g = statement_to_points_to(exit_s, out_g); 
  return out_g;
}

References control_equal_p(), control_in_set_p(), CONTROL_MAP, control_predecessors, control_rank(), control_statement, control_to_points_to(), cyclic_graph_to_points_to(), exit, FOREACH, FORWARD_CONTROL_MAP, free(), full_copy_pt_map(), gen_full_copy_list(), gen_nconc(), make_points_to_graph(), merge_points_to_graphs(), new_pt_map, NIL, out, points_to_equal_p(), points_to_graph_set, points_to_rank(), ready_to_be_processed_set(), set_add_element(), set_assign(), set_assign_list(), set_clear(), set_del_element(), set_difference(), set_empty_p(), SET_FOREACH, set_generic_make(), set_intersection(), set_intersection_p(), set_private, set_union(), statement_ordering, statement_to_points_to(), unstructured_control, unstructured_exit, and unstructured_to_trail().

Here is the call graph for this function:

Ready_p()

bool Ready_p	(	control	c,
		set	Processed,
		set	Reachable
	)

A node is ready to be processed if its predecessors are not reachable or processed.

Pred = set_assign_list(Pred,gen_full_copy_list( Pred_l));

Parameters

Processed	rocessed
Reachable	eachable

Definition at line 97 of file unstructured.c.

{ 
  set Pred =  set_make(set_pointer);
  list Pred_l = control_predecessors(c);
  FOREACH(control, ctr, Pred_l) {
    Pred = set_add_element(Pred, Pred, (void*)ctr);
  }
  /* Pred = set_assign_list(Pred,gen_full_copy_list( Pred_l)); */
  bool ready_p = false;
  SET_FOREACH(control, p , Pred) {
    ready_p = set_belong_p(Processed,(void*) p) || !set_belong_p(Reachable,(void*) p); 
  }
  return ready_p;
}

References control_predecessors, FOREACH, set_add_element(), set_belong_p(), SET_FOREACH, set_make(), and set_pointer.

Referenced by ready_to_be_processed_set().

Here is the call graph for this function:

Here is the caller graph for this function:

ready_to_be_processed_set()

set ready_to_be_processed_set	(	control	n,
		set	Processed,
		set	Reachable
	)

A set containing all the successors of n that are ready to be processed.

Succ = set_assign_list(Succ, gen_full_copy_list(Succ_l));

Parameters

Processed	rocessed
Reachable	eachable

Definition at line 114 of file unstructured.c.

{
   set Succ =  set_make(set_pointer);
   set rtbp =  set_make(set_pointer);
   list Succ_l = control_successors(n);
   FOREACH(control, ctr, Succ_l) {
    Succ = set_add_element(Succ, Succ, (void*)ctr);
  }
   /* Succ = set_assign_list(Succ, gen_full_copy_list(Succ_l)); */
   SET_FOREACH(control, p , Succ){
     if(Ready_p(p, Processed, Reachable))
       set_add_element(rtbp, rtbp, (void*)p);
   }
   return rtbp;
}

References control_successors, FOREACH, Ready_p(), set_add_element(), SET_FOREACH, set_make(), and set_pointer.

Referenced by new_points_to_unstructured().

Here is the call graph for this function:

Here is the caller graph for this function:

statement_equal_p()

static bool statement_equal_p ( statement  s1, statement  s2  )

static

Definition at line 55 of file unstructured.c.

{
    return (statement_ordering(s1) == statement_ordering(s2));
}

References s1, and statement_ordering.

Referenced by allocate_task_to_cluster(), bottom_level(), communications_construction(), control_in_set_p(), end_idle_clusters(), predecessors(), ready_node(), t_level(), task_time_polynome(), tlevel_decrease(), topological_sort(), and zeroing_multiple_edges().

Here is the caller graph for this function: