SDG.c File Reference

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include "boolean.h"
#include <stdbool.h>
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "database.h"
#include "misc.h"
#include "text.h"
#include "text-util.h"
#include "ri-util.h"
#include "prettyprint.h"
#include "effects-util.h"
#include "accel-util.h"
#include "effects-generic.h"
#include "effects-simple.h"
#include "pipsdbm.h"
#include "resources.h"
#include "control.h"
#include "conversion.h"
#include "properties.h"
#include "semantics.h"
#include "transformations.h"
#include "effects-convex.h"
#include "complexity_ri.h"
#include "dg.h"
#include "graph.h"
#include "ricedg.h"
#include "chains.h"
#include "task_parallelization.h"

Include dependency graph for SDG.c:

Go to the source code of this file.

Data Structures
struct	cpv

Macros
#define	dot_print_label_string(ftg, str)
	print the string str in file descriptor fd, removing all More...

Typedefs
typedef dg_arc_label	arc_label
	Instantiation of the dependence graph: More...
typedef dg_vertex_label	vertex_label

Functions
static void	get_private_entities_walker (loop l, set s)
static set	get_private_entities (void *s)
static void	check_private_variables_call_walker (call c, struct cpv *p)
static bool	check_private_variables_loop_walker (loop l, struct cpv *p)
static list	private_variables (statement stat)
bool	statement_equal_p (statement s1, statement s2)
vertex	statement_to_vertex (statement s, graph g)
static list	enclosed_statements_ast (statement stmt, list children_s)
static bool	same_level_p (statement s1, statement s2, bool found_p)
static statement	in_same_sequence (statement child, sequence seq)
static bool	test_dependence_using_regions (statement s1, statement s2)
	for precision in dependences in arrays, we use array regions in this function More...
static bool	sequence_dg (statement stmt)
static bool	statement_in_sequence_p (statement s, statement stmt, bool found_p)
static graph	clean_sdg (statement module_stmt, graph tg)
	Second step to form a clustered DG (SDG), delete dependences between statement s1 and another statement S2 if s1 is not in a sequence and redondont dependences. More...
graph	partitioning_sdg (statement module_stmt)
static string	prettyprint_dot_label (statement s, string label1)
static void	print_sdg_task (FILE *ftg, gen_array_t annotations, statement stmt)
	return a dot graph for SDG, print only nodes that have at least one successor More...
void	print_SDGs (statement stmt, graph tg, FILE *ftg, gen_array_t annotations)
bool	sequence_dependence_graph (char *module_name)

Variables
static transformer	p_transformer
static graph	sdg
int	NBCLUSTERS
	parameters of BDSC, to be recovered using pips properties More...
int	MEMORY_SIZE
string	INSTRUMENTED_FILE
gen_array_t	annotations
	Global variables. More...
gen_array_t	clusters
static int	count = 0

Macro Definition Documentation

dot_print_label_string

#define dot_print_label_string	(		ftg,
			str
	)

Value:

  fprintf(ftg," [fontsize=24,fontcolor=black, label=\"");          \
  while ( *str ) {                         \
    char c = *str++;                                \
    if ( c == '"' ) { /**some char must be escaped */   \
      (void) putc( '\\', ftg);                          \
    }                                                   \
    (void) putc( c, ftg);                               \
  }\
  fprintf(ftg," \"]; \n");

print the string str in file descriptor fd, removing all

Definition at line 469 of file SDG.c.

Typedef Documentation

arc_label

typedef dg_arc_label arc_label

Instantiation of the dependence graph:

Definition at line 45 of file SDG.c.

vertex_label

typedef dg_vertex_label vertex_label

Definition at line 46 of file SDG.c.

Function Documentation

check_private_variables_call_walker()

static void check_private_variables_call_walker ( call  c, struct cpv *  p  )

static

Definition at line 88 of file SDG.c.

{
    set s = get_referenced_entities(c);
    if(set_belong_p(s,p->e)){
        p->rm=true;
        gen_recurse_stop(0);
    }
    set_free(s);
}

References cpv::e, gen_recurse_stop(), get_referenced_entities(), cpv::rm, set_belong_p(), and set_free().

Referenced by private_variables().

Here is the call graph for this function:

Here is the caller graph for this function:

check_private_variables_loop_walker()

static bool check_private_variables_loop_walker ( loop  l, struct cpv *  p  )

static

Definition at line 98 of file SDG.c.

{
    return !has_entity_with_same_name(p->e,loop_locals(l));
}

References cpv::e, has_entity_with_same_name(), and loop_locals.

Referenced by private_variables().

Here is the call graph for this function:

Here is the caller graph for this function:

clean_sdg()

static graph clean_sdg ( statement  module_stmt, graph  tg  )

static

Second step to form a clustered DG (SDG), delete dependences between statement s1 and another statement S2 if s1 is not in a sequence and redondont dependences.

Definition at line 421 of file SDG.c.

{
  list vertices = graph_vertices(tg);
  statement s;
  FOREACH(VERTEX, pre, vertices)
    {
      s = vertex_to_statement(pre);
      bool found_p =  statement_in_sequence_p(s, module_stmt, false);
      if(!found_p)
        {
          gen_free_list(vertex_successors(pre));
          vertex_successors(pre) = NIL;
        }
      else{
        int count;
        list ls = NIL, lv = NIL;
        FOREACH(SUCCESSOR, su, (vertex_successors(pre))) {
          vertex ssu = successor_vertex(su);
          statement child = vertex_to_statement(ssu);
          count = gen_occurences(child, ls);
          if(count == 0 && statement_ordering(s)<statement_ordering(child))
            {
              ls = CONS(STATEMENT, child,ls);
              if(gen_occurences(su, lv) == 0)
                lv = CONS(SUCCESSOR,su,lv);
            }
        }
        vertex_successors(pre) = lv; 
      }
    }
  return tg;
}

References CONS, count, FOREACH, gen_free_list(), gen_occurences(), graph_vertices, NIL, STATEMENT, statement_in_sequence_p(), statement_ordering, SUCCESSOR, successor_vertex, VERTEX, vertex_successors, and vertex_to_statement().

Referenced by partitioning_sdg().

Here is the call graph for this function:

Here is the caller graph for this function:

enclosed_statements_ast()

static list enclosed_statements_ast ( statement  stmt, list  children_s  )

static

Definition at line 141 of file SDG.c.

{
  instruction inst = statement_instruction(stmt);
  switch(instruction_tag(inst))
    {
    case is_instruction_block :
      {
        MAPL( stmt_ptr,
              {
                statement local_stmt = STATEMENT(CAR( stmt_ptr ));
                children_s = CONS( STATEMENT, local_stmt, children_s);
                children_s = enclosed_statements_ast(local_stmt,children_s);
              },
              instruction_block( inst ) );
        break;
      }
    case is_instruction_test :
      {
        test t = instruction_test(inst);
        children_s = CONS( STATEMENT, test_true(t), children_s);
        children_s = CONS( STATEMENT, test_false(t), children_s);
        children_s = enclosed_statements_ast(test_true(t),children_s);
        children_s = enclosed_statements_ast(test_false(t),children_s);
        break;
      }
    case is_instruction_loop :
      {
        loop l = statement_loop(stmt);
        statement body = loop_body(l);
        children_s = CONS( STATEMENT, body, children_s);
        children_s = enclosed_statements_ast(body,children_s);
        break;
      }
    case is_instruction_forloop :
      {
        forloop l = statement_forloop(stmt);
        statement body = forloop_body(l);
        children_s = CONS( STATEMENT, body, children_s);
        children_s = enclosed_statements_ast(body,children_s);
        break;
      }
    case is_instruction_whileloop :
      {
        whileloop l = statement_whileloop(stmt);
        statement body = whileloop_body(l);
        children_s = CONS( STATEMENT, body, children_s);
        children_s = enclosed_statements_ast(body,children_s);
        break;
      }
    case is_instruction_call:
      //children_s = CONS( STATEMENT, stmt, children_s);
      break;
    default:
      break;
    }
  return children_s;
}

References CAR, CONS, forloop_body, instruction_block, instruction_tag, instruction_test, is_instruction_block, is_instruction_call, is_instruction_forloop, is_instruction_loop, is_instruction_test, is_instruction_whileloop, loop_body, MAPL, STATEMENT, statement_forloop(), statement_instruction, statement_loop(), statement_whileloop(), test_false, test_true, and whileloop_body.

Referenced by sequence_dg().

Here is the call graph for this function:

Here is the caller graph for this function:

get_private_entities()

static set get_private_entities ( void *  s )

static

Definition at line 73 of file SDG.c.

{
    set tmp = set_make(set_pointer);
    gen_context_recurse(s, tmp, loop_domain, gen_true2, get_private_entities_walker);
    return tmp;
}

References gen_context_recurse, gen_true2(), get_private_entities_walker(), loop_domain, set_make(), and set_pointer.

Referenced by private_variables().

Here is the call graph for this function:

Here is the caller graph for this function:

get_private_entities_walker()

static void get_private_entities_walker ( loop  l, set  s  )

static

Definition at line 67 of file SDG.c.

{
  set_append_list(s,loop_locals(l));
}

References loop_locals, and set_append_list().

Referenced by get_private_entities().

Here is the call graph for this function:

Here is the caller graph for this function:

in_same_sequence()

static statement in_same_sequence ( statement  child, sequence  seq  )

static

Definition at line 246 of file SDG.c.

{
  statement enclosing_st = statement_undefined;
  bool found_p;
  list stmts = sequence_statements(seq);
  FOREACH(STATEMENT, st, stmts){
    found_p = same_level_p(child, st, false);
    if(found_p){
      enclosing_st = st;
      return st;
    }
  }
  return enclosing_st;
}

References FOREACH, same_level_p(), sequence_statements, STATEMENT, and statement_undefined.

Referenced by sequence_dg().

Here is the call graph for this function:

Here is the caller graph for this function:

partitioning_sdg()

graph partitioning_sdg

(

statement

module_stmt

)

Parameters

module_stmt

odule_stmt

Definition at line 455 of file SDG.c.

{
  gen_recurse(module_stmt, statement_domain, sequence_dg, gen_null);
  return clean_sdg(module_stmt, sdg);
}

References clean_sdg(), gen_null(), gen_recurse, sdg, sequence_dg(), and statement_domain.

Referenced by sequence_dependence_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

prettyprint_dot_label()

static string prettyprint_dot_label ( statement  s, string  label1  )

static

Definition at line 481 of file SDG.c.

                                                                 {
  string label2="";
  // saving comments
  string i_comments = statement_comments(s);
  // remove them
  statement_comments(s) = string_undefined;
  // Get the text without comments
  text txt = Text_Statement(entity_undefined, 0, s);
  // Restoring comments
  statement_comments(s) = i_comments;
  label2 = strdup (concatenate (label1, text_to_string(txt),"\\n", NULL));
  free_text(txt);
  return label2;
 }

References concatenate(), entity_undefined, free_text(), statement_comments, strdup(), string_undefined, Text_Statement(), and text_to_string().

Referenced by print_sdg_task().

Here is the call graph for this function:

Here is the caller graph for this function:

print_sdg_task()

static void print_sdg_task ( FILE *  ftg, gen_array_t  annotations, statement  stmt  )

static

return a dot graph for SDG, print only nodes that have at least one successor

Definition at line 500 of file SDG.c.

                                                                               {
  string ver = "";
  ver = prettyprint_dot_label(stmt,ver);
  fprintf( ftg,"%d",(int)statement_ordering(stmt) );
  if(strlen(ver)>1000)
    ver = "too large statement label with ordering \\n";
  if(gen_array_nitems(annotations)>0){
    annotation *an=gen_array_item(annotations, (int)statement_ordering(stmt));
    if(an->cluster != -1)
      {
        ver = strdup (concatenate (ver, "cluster = ", NULL));ver = strdup (concatenate (ver, i2a(an->cluster),"\\n", NULL));
        ver = strdup (concatenate (ver, "order = ", NULL)); ver = strdup (concatenate (ver, i2a(an->order_sched),"\\n", NULL));
        ver = strdup (concatenate (ver, "time = ", NULL)); ver = strdup (concatenate (ver, i2a(an->task_time),"\\n", NULL));
      }
  }
  dot_print_label_string( ftg, ver);    
  return;
}

References annotations, annotation::cluster, concatenate(), dot_print_label_string, fprintf(), gen_array_item(), gen_array_nitems(), i2a(), annotation::order_sched, prettyprint_dot_label(), statement_ordering, strdup(), and annotation::task_time.

Referenced by print_SDGs().

Here is the call graph for this function:

Here is the caller graph for this function:

print_SDGs()

void print_SDGs	(	statement	stmt,
		graph	tg,
		FILE *	ftg,
		gen_array_t	annotations
	)

Parameters

stmt	tmt
tg	g
ftg	tg
annotations	nnotations

Definition at line 520 of file SDG.c.

                                                                              {
  instruction inst = statement_instruction(stmt);
  switch(instruction_tag(inst))
    {
    case is_instruction_block :
      {
      sequence seq = statement_sequence(stmt);
      list stmts = sequence_statements(seq);
      fprintf( ftg, "subgraph cluster%d { color = blue; \n ",count );
      FOREACH(STATEMENT, s, stmts) {
        list vertices = graph_vertices(tg);
        annotation *anp = NULL;
        FOREACH(VERTEX, pre, vertices) {
          statement parent = vertex_to_statement(pre);
          if(statement_equal_p(parent, s)){
            if(gen_array_nitems(annotations)>0)
              anp = gen_array_item(annotations, (int)statement_ordering(parent));
            print_sdg_task(ftg, annotations, parent);
            FOREACH(SUCCESSOR, su, (vertex_successors(pre))) {
              vertex s = successor_vertex(su);
              statement child = vertex_to_statement(s);
              print_sdg_task(ftg, annotations, child);
              if(gen_array_nitems(annotations)>0){
                annotation *an=gen_array_item(annotations, (int)statement_ordering(child));
                if(an->cluster!=-1)
                  {//FFT
                    double edge_c = (intptr_t)(gen_array_item(anp->edge_cost,statement_ordering(child)));
                    fprintf( ftg,"%d -> %d [style=filled,color=blue,fontsize=16,label=\"%ld\",color=black];\n", (int)statement_ordering(parent),(int)statement_ordering(child),(long)(edge_c));
                  }
              }
              else
                fprintf( ftg,"%d -> %d [style=filled,color=blue,fontsize=16,color=black];\n", (int)statement_ordering(parent),(int)statement_ordering(child));
            }
          }
        }
      }
      fprintf( ftg, "} \n " );
      count ++;
      stmts = sequence_statements(seq);
      FOREACH(STATEMENT, s, stmts) 
        print_SDGs(s,tg, ftg, annotations);
      break;
      }
    case is_instruction_test:
      {
        test t = instruction_test(inst);
        print_SDGs(test_true(t),tg, ftg, annotations); 
        print_SDGs(test_false(t),tg, ftg, annotations); 
        break;
      }
    case is_instruction_loop :
      {
        loop l = statement_loop(stmt);
        print_SDGs(loop_body(l),tg, ftg, annotations);
        break;
      }
    case is_instruction_forloop :
      {
        forloop l = statement_forloop(stmt);
        print_SDGs(forloop_body(l),tg, ftg, annotations);
        break;
      }
    case is_instruction_whileloop :
      {
        whileloop l = statement_whileloop(stmt);
        print_SDGs(whileloop_body(l),tg, ftg, annotations);
        break;
      }
    default:
      break;
    }
  return; 
}

References annotations, annotation::cluster, count, annotation::edge_cost, FOREACH, forloop_body, fprintf(), gen_array_item(), gen_array_nitems(), graph_vertices, instruction_tag, instruction_test, intptr_t, is_instruction_block, is_instruction_forloop, is_instruction_loop, is_instruction_test, is_instruction_whileloop, loop_body, print_sdg_task(), sequence_statements, STATEMENT, statement_equal_p(), statement_forloop(), statement_instruction, statement_loop(), statement_ordering, statement_sequence(), statement_whileloop(), SUCCESSOR, successor_vertex, test_false, test_true, VERTEX, vertex_successors, vertex_to_statement(), and whileloop_body.

Referenced by hbdsc_parallelization(), and sequence_dependence_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

private_variables()

static list private_variables ( statement  stat )

static

Definition at line 104 of file SDG.c.

{
    set s = get_private_entities(stat);
    list l =NIL;
    SET_FOREACH(entity,e,s) {
        struct cpv p = { .e=e, .rm=false };
        gen_context_multi_recurse(stat,&p,
                call_domain,gen_true,check_private_variables_call_walker,
                loop_domain,check_private_variables_loop_walker,gen_null,
                0);
        if(!p.rm)
            l=CONS(ENTITY,e,l);
    }
    set_free(s);
 
    return l;
}

References call_domain, check_private_variables_call_walker(), check_private_variables_loop_walker(), CONS, cpv::e, ENTITY, gen_context_multi_recurse(), gen_null(), gen_true(), get_private_entities(), loop_domain, NIL, cpv::rm, SET_FOREACH, and set_free().

Referenced by test_dependence_using_regions().

Here is the call graph for this function:

Here is the caller graph for this function:

same_level_p()

static bool same_level_p ( statement  s1, statement  s2, bool  found_p  )

static

Definition at line 199 of file SDG.c.

{
    
  if(statement_equal_p(s1, s2))
    return true;
  else {
    instruction inst = statement_instruction(s2);
    switch(instruction_tag(inst)){
    case is_instruction_block :{
      MAPL( stmt_ptr,
            {
              statement local_stmt = STATEMENT(CAR( stmt_ptr ));
              found_p = found_p || same_level_p(s1, local_stmt, found_p);
            },
            instruction_block(inst));
      break;
    }
    case is_instruction_test :{
      test t = instruction_test(inst);
      found_p = found_p || same_level_p(s1, test_true(t), found_p);
      return found_p || same_level_p(s1, test_false(t), found_p);
      break;
    }
    case is_instruction_loop :{
      loop l = statement_loop(s2);
      statement body = loop_body(l);
      return found_p || same_level_p(s1, body, found_p);
      break;
    }
    case is_instruction_forloop :{
      forloop l = statement_forloop(s2);
      statement body = forloop_body(l);
      return found_p || same_level_p(s1, body, found_p);
      break;
    }
    case is_instruction_whileloop :{
      whileloop l = statement_whileloop(s2);
      statement body = whileloop_body(l);
      return found_p || same_level_p(s1, body, found_p);
      break;
    }
    default:
      break;
    }
  }
  return found_p;
}

References CAR, forloop_body, instruction_block, instruction_tag, instruction_test, is_instruction_block, is_instruction_forloop, is_instruction_loop, is_instruction_test, is_instruction_whileloop, loop_body, MAPL, s1, STATEMENT, statement_equal_p(), statement_forloop(), statement_instruction, statement_loop(), statement_whileloop(), test_false, test_true, and whileloop_body.

Referenced by in_same_sequence().

Here is the call graph for this function:

Here is the caller graph for this function:

sequence_dependence_graph()

bool sequence_dependence_graph

(

char *

module_name

)

The proper effect to detect the I/O operations:

dg contains the original dependences before clustering and scheduling, it is saved to not make a side effect on the original dg when constructing the SDG

Parameters

module_name

odule_name

Definition at line 593 of file SDG.c.

{ 
  //entity      module;
  statement     module_stat;
  string tg_name = NULL;
  FILE *ftg;
  //module = local_name_to_top_level_entity(module_name);
  module_stat = (statement)db_get_memory_resource(DBR_CODE, module_name, true);
  set_ordering_to_statement(module_stat);
  set_current_module_entity(module_name_to_entity(module_name));
  set_current_module_statement(module_stat);
  set_precondition_map((statement_mapping)db_get_memory_resource(DBR_PRECONDITIONS, module_name, true));
  set_transformer_map((statement_mapping)
                      db_get_memory_resource(DBR_TRANSFORMERS, module_name, true));
  /* The proper effect to detect the I/O operations: */
  set_proper_rw_effects((statement_effects)db_get_memory_resource(DBR_PROPER_EFFECTS, module_name, true));
  set_cumulated_rw_effects((statement_effects)db_get_memory_resource(DBR_CUMULATED_EFFECTS, module_name, true));
  module_to_value_mappings(get_current_module_entity());
  set_rw_effects((statement_effects) 
                 db_get_memory_resource(DBR_REGIONS, module_name, true));
  set_in_effects((statement_effects) db_get_memory_resource(DBR_IN_REGIONS, module_name, true));
  set_out_effects((statement_effects) db_get_memory_resource(DBR_OUT_REGIONS, module_name, true));
  set_methods_for_convex_effects();
  init_convex_rw_prettyprint(module_name);
 
  ddg = (graph) db_get_memory_resource (DBR_DG, module_name, true );
  /*ddg contains the original dependences before clustering and  scheduling, it
    is saved to not make a side effect on the original dg when
    constructing the SDG*/
  sdg = copy_graph(ddg);
  sdg = partitioning_sdg(module_stat);
  tg_name = strdup(concatenate(db_get_current_workspace_directory(),
                               "/",module_name,"/",module_name, "_sdg.dot", NULL));
  ftg = safe_fopen(tg_name, "w");
  fprintf( ftg, "digraph {\n compound=true;ratio=fill; node[fontsize=24,fontname=\"Courier\",labelloc=\"t\"];nodesep=.05;\n" );
  print_SDGs(module_stat, sdg, ftg, gen_array_make(0));
  fprintf( ftg, "\n}\n" );
  safe_fclose(ftg, tg_name);
  free(tg_name);
  
  reset_ordering_to_statement();
  DB_PUT_MEMORY_RESOURCE(DBR_SDG, module_name, (char*) sdg);
  
  reset_proper_rw_effects();
  reset_cumulated_rw_effects();
  reset_rw_effects();
  reset_in_effects();
  reset_out_effects();
  reset_precondition_map();
  reset_transformer_map();
  reset_current_module_statement();
  reset_current_module_entity();
  generic_effects_reset_all_methods();
  free_value_mappings();
  return true;
}

References concatenate(), copy_graph(), db_get_current_workspace_directory(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, ddg, fprintf(), free(), free_value_mappings(), gen_array_make(), generic_effects_reset_all_methods(), get_current_module_entity(), init_convex_rw_prettyprint(), module_name(), module_name_to_entity(), module_to_value_mappings(), partitioning_sdg(), print_SDGs(), reset_cumulated_rw_effects(), reset_current_module_entity(), reset_current_module_statement(), reset_in_effects(), reset_ordering_to_statement(), reset_out_effects(), reset_precondition_map(), reset_proper_rw_effects(), reset_rw_effects(), reset_transformer_map(), safe_fclose(), safe_fopen(), sdg, set_cumulated_rw_effects(), set_current_module_entity(), set_current_module_statement(), set_in_effects(), set_methods_for_convex_effects(), set_ordering_to_statement(), set_out_effects(), set_precondition_map(), set_proper_rw_effects(), set_rw_effects(), set_transformer_map(), and strdup().

Here is the call graph for this function:

sequence_dg()

static bool sequence_dg ( statement  stmt )

static

pdate the sdg for st(parent) using enclosing_stmt instead of the enclosed one child

Definition at line 321 of file SDG.c.

{
  if(statement_sequence_p(stmt)){
    sequence seq = statement_sequence(stmt);
    list stmts = sequence_statements(seq);
    path pbegin;
    path pend;
    FOREACH(STATEMENT, st_g, stmts) {
      {
        list children_s = CONS(STATEMENT, st_g, NIL);
        list ls = NIL;
        children_s = enclosed_statements_ast(st_g,children_s);
        vertex pre_g = statement_to_vertex(st_g, sdg);
        FOREACH(STATEMENT, st, children_s){
          vertex pre = statement_to_vertex(st, sdg);
          FOREACH(SUCCESSOR, su, (vertex_successors(pre))) {
            vertex s = successor_vertex(su);
            statement child = vertex_to_statement(s);
            statement enclosing_stmt = statement_undefined;
            enclosing_stmt = in_same_sequence(child, seq);
            if(statement_undefined_p(enclosing_stmt))
              enclosing_stmt = in_same_sequence(st, seq);
 
            p_transformer =  transformer_identity();
            path_initialize(stmt, st,child, &pbegin, &pend);
            //p_transformer = compute_path_transformer(stmt, pbegin, pend);
            /*update the sdg for st(parent) using enclosing_stmt instead of
             *the enclosed one child*/
            if(!statement_equal_p(st_g, enclosing_stmt) && test_dependence_using_regions(st_g,enclosing_stmt)){
              if(statement_ordering(st_g)<statement_ordering(enclosing_stmt)){
                vertex new_v = statement_to_vertex(enclosing_stmt, sdg);
                successor_vertex(su) = new_v;
                if(gen_occurences(su, ls) == 0)
                  ls = CONS(SUCCESSOR, su, ls);
              }
            }
          }
        }
        vertex_successors(pre_g) = ls; 
      }
    }
  }
  return true;
}

References CONS, enclosed_statements_ast(), FOREACH, gen_occurences(), in_same_sequence(), NIL, p_transformer, path_initialize(), sdg, sequence_statements, STATEMENT, statement_equal_p(), statement_ordering, statement_sequence(), statement_sequence_p(), statement_to_vertex(), statement_undefined, statement_undefined_p, SUCCESSOR, successor_vertex, test_dependence_using_regions(), transformer_identity(), vertex_successors, and vertex_to_statement().

Referenced by partitioning_sdg().

Here is the call graph for this function:

Here is the caller graph for this function:

statement_equal_p()

bool statement_equal_p	(	statement	s1,
		statement	s2
	)

Parameters

s1	1
s2	2

Definition at line 123 of file SDG.c.

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

References s1, statement_number, and statement_ordering.

Referenced by print_SDGs(), same_level_p(), sequence_dg(), statement_in_sequence_p(), and statement_to_vertex().

Here is the caller graph for this function:

statement_in_sequence_p()

static bool statement_in_sequence_p ( statement  s, statement  stmt, bool  found_p  )

static

Definition at line 366 of file SDG.c.

{
  instruction inst = statement_instruction(stmt);
  switch(instruction_tag(inst))
    {
    case is_instruction_block :
      {
        MAPL( stmt_ptr,
              {
                statement local_stmt = STATEMENT(CAR( stmt_ptr ));
                if(statement_equal_p(s, local_stmt))
                  return true;
                else
                  found_p = found_p ||  statement_in_sequence_p(s, local_stmt, found_p);
              },
              instruction_block( inst ) );
        break;
      }
    case is_instruction_test :
      {
        test t = instruction_test(inst);
        found_p = found_p ||  statement_in_sequence_p(s, test_true(t), found_p);
        return found_p ||  statement_in_sequence_p(s, test_false(t), found_p);
        break;
      }
    case is_instruction_loop :
      {
        loop l = statement_loop(stmt);
        statement body = loop_body(l);
        return found_p ||  statement_in_sequence_p(s, body, found_p);
        break;
      }
    case is_instruction_forloop :
      {
        forloop l = statement_forloop(stmt);
        statement body = forloop_body(l);
        return found_p ||  statement_in_sequence_p(s, body, found_p);
        break;
      }
    case is_instruction_whileloop :
      {
        whileloop l = statement_whileloop(stmt);
        statement body = whileloop_body(l);
        return found_p ||  statement_in_sequence_p(s, body, found_p);
        break;
      }
    default:
      break;
    }
  return found_p;
}

References CAR, forloop_body, instruction_block, instruction_tag, instruction_test, is_instruction_block, is_instruction_forloop, is_instruction_loop, is_instruction_test, is_instruction_whileloop, loop_body, MAPL, STATEMENT, statement_equal_p(), statement_forloop(), statement_instruction, statement_loop(), statement_whileloop(), test_false, test_true, and whileloop_body.

Referenced by clean_sdg().

Here is the call graph for this function:

Here is the caller graph for this function:

statement_to_vertex()

vertex statement_to_vertex	(	statement	s,
		graph	g
	)

Definition at line 131 of file SDG.c.

{
    MAP(VERTEX, v, {
        statement sv = vertex_to_statement(v);
        if (statement_equal_p(s, sv))
          return v;
    }, graph_vertices(g));
    return vertex_undefined;
}

References graph_vertices, MAP, statement_equal_p(), VERTEX, vertex_to_statement(), and vertex_undefined.

Referenced by sequence_dg().

Here is the call graph for this function:

Here is the caller graph for this function:

test_dependence_using_regions()

static bool test_dependence_using_regions ( statement  s1, statement  s2  )

static

for precision in dependences in arrays, we use array regions in this function

Definition at line 263 of file SDG.c.

{
  bool dependence_b = false;
  list l_write_1 = regions_dup(regions_write_regions(load_statement_local_regions(s1)));
  list private_ents1 = NIL, private_ents2 = NIL;
  if(statement_loop_p(s1))
    private_ents1 =  loop_locals(statement_loop(s1));
  private_ents1= gen_nconc(private_ents1,private_variables(s1));
  if(statement_loop_p(s2))
     private_ents2 = loop_locals(statement_loop(s2));
  private_ents2= gen_nconc(private_ents2, private_variables(s2));
  FOREACH(ENTITY,e,private_ents1){
    FOREACH(REGION,reg,l_write_1){
      if (same_entity_p(region_entity(reg),e))
        gen_remove(&l_write_1, reg);
    }
  }
  list l_write_2 = regions_dup(regions_write_regions(load_statement_local_regions(s2)));
  FOREACH(ENTITY,e,private_ents2){
    FOREACH(REGION,reg,l_write_2){
      if (same_entity_p(region_entity(reg),e))
        gen_remove(&l_write_2, reg);
    }
  }
  l_write_2 = convex_regions_transformer_compose(l_write_2, p_transformer);
  list l_read_2 = regions_dup(regions_read_regions(load_statement_local_regions(s2)));  
  FOREACH(ENTITY,e,private_ents2){
    FOREACH(REGION,reg,l_read_2) {
      if (same_entity_p(region_entity(reg),e))
        gen_remove(&l_read_2, reg);
    }
  }
  l_read_2 = convex_regions_transformer_compose(l_read_2, p_transformer);
  list l_read_1 = regions_dup(regions_read_regions(load_statement_local_regions(s1)));  
  FOREACH(ENTITY,e,private_ents1){
    FOREACH(REGION,reg,l_read_1){
      if (same_entity_p(region_entity(reg),e))
        gen_remove(&l_read_1, reg);
    }
  }
  list dependence_rw = RegionsIntersection(regions_dup(l_read_1), regions_dup(l_write_2), r_w_combinable_p);
  list dependence_wr = RegionsIntersection(regions_dup(l_write_1), regions_dup(l_read_2), w_r_combinable_p);
  list dependence_ww = RegionsIntersection(regions_dup(l_write_1), regions_dup(l_write_2), w_w_combinable_p);
  if(gen_length(dependence_rw)==0)
    {
      if(gen_length(dependence_wr)==0)
        {
          if(gen_length(dependence_ww)>0)
            dependence_b=true;
        }
      else
        dependence_b=true;
    }
  else
    dependence_b = true;
  return dependence_b;
}

References convex_regions_transformer_compose(), cpv::e, ENTITY, FOREACH, gen_length(), gen_nconc(), gen_remove(), load_statement_local_regions(), loop_locals, NIL, p_transformer, private_variables(), r_w_combinable_p(), REGION, region_entity, regions_dup(), regions_read_regions(), regions_write_regions(), RegionsIntersection(), s1, same_entity_p(), statement_loop(), statement_loop_p(), w_r_combinable_p(), and w_w_combinable_p().

Referenced by sequence_dg().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

annotations

gen_array_t annotations

Global variables.

Definition at line 62 of file SDG.c.

Referenced by allocate_task_to_cluster(), BDSC(), bottom_level(), cancel_schedule(), DSC(), dsc_code_parallelization(), DSRW(), end_idle_clusters(), hbdsc_parallelization(), hierarchical_schedule(), hierarchical_schedule_step(), initialization(), MCW(), move_task_to_cluster(), parse_instrumented_file(), print_sdg_task(), print_SDGs(), priorities(), ready_node(), schedule_failsafe(), select_task_with_highest_priority(), t_level(), tlevel_decrease(), top_level(), update_parallel_task(), update_priority_values(), and zeroing_multiple_edges().

clusters

gen_array_t clusters

Definition at line 63 of file SDG.c.

Referenced by allocate_task_to_cluster(), critical_path_length(), DSC(), dsc_code_parallelization(), end_idle_clusters(), hbdsc_parallelization(), initialization_clusters(), max_start_time_cluster(), MCW(), min_start_time_cluster(), move_task_to_cluster(), tlevel_decrease(), and zeroing_multiple_edges().

count

int count = 0

static

Definition at line 519 of file SDG.c.

Referenced by adg_enrichir(), adg_number_of_same_loops(), adg_vertex_to_ordering(), build_convex_constraints_from_vertices(), build_second_comb(), character_occurences_in_string(), clean_sdg(), clear_C_comment(), concatenate(), count_dataflows_on_ref(), create_farkas_poly(), create_var_name(), cycle_to_flow_sensitive_preconditions(), dag_computation_count(), dag_or_cycle_to_flow_sensitive_postconditions_or_transformers(), dag_to_flow_sensitive_preconditions(), dagvtx_dot(), db_unput_resources(), delete_named_resources(), do_loop_unroll_with_epilogue(), entity_all_module_xxx_locations_typed(), entity_all_xxx_locations_typed(), find_kth_points_to_node_in_points_to_path(), FixCInternalLabels(), fprint_functional(), fprint_pla_pp_dims(), general_build_signature(), generate_mmcd_stat_from_ref(), generate_mmcd_stats_from_ref(), get_optimal_opcode(), get_time_ent(), include_trans_in_poly(), lf_count(), make_lInitStats(), make_proto(), mapping_to_domain_list(), mapping_to_value_number(), my_clean_ps(), new_array_elements_backward_substitution_in_transformer(), new_array_elements_forward_substitution_in_transformer(), points_to_subscripts_to_number_of_unbounded_dimensions(), print_make_cache(), print_SDGs(), PRINTF_FETCHARGS(), put_source_ind(), raw_flint_message(), ref_count_rwt(), reference_ith_index(), replace_ref_by_ent(), reset_C_comment(), safe_fread(), safe_fwrite(), sc_fprint(), search_scc_bdt(), simplify_minmax_contrainte(), SimplifyGraph(), stco_renumber_code(), SupressDependances(), switch_cast_to_copy(), tpips_help(), transformer_with_temporary_values_p(), typing_assign_substring(), typing_buffer_inout(), typing_implied_do(), typing_substring(), VASNPRINTF(), and words_any_reference().

INSTRUMENTED_FILE

string INSTRUMENTED_FILE

Definition at line 59 of file SDG.c.

Referenced by dsc_code_parallelization(), and hbdsc_parallelization().

MEMORY_SIZE

int MEMORY_SIZE

Definition at line 58 of file SDG.c.

Referenced by dsc_code_parallelization(), find_cluster(), hbdsc_parallelization(), spire_distributed_unstructured_to_structured(), spire_shared_unstructured_to_structured(), tlevel_decrease(), and zeroing_multiple_edges().

NBCLUSTERS

int NBCLUSTERS

parameters of BDSC, to be recovered using pips properties

cproto-generated files

Definition at line 57 of file SDG.c.

Referenced by cluster_stage_spire(), dsc_code_parallelization(), gen_recv_communications(), gen_send_communications(), hbdsc_parallelization(), hierarchical_schedule(), initialization_clusters(), rebuild_topological_sort(), spire_distributed_unstructured_to_structured(), and spire_shared_unstructured_to_structured().

p_transformer

transformer p_transformer

static

Definition at line 53 of file SDG.c.

Referenced by sequence_dg(), and test_dependence_using_regions().

sdg

graph sdg

static

Definition at line 54 of file SDG.c.

Referenced by partitioning_sdg(), sequence_dependence_graph(), and sequence_dg().