#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "resources.h"
#include "misc.h"
#include "ri-util.h"
#include "effects-util.h"
#include "text-util.h"
#include "pipsdbm.h"
#include "effects-generic.h"
#include "control.h"
#include "transformations.h"
#include "effects-simple.h"
#include "sac.h"
#include "ricedg.h"

Include dependency graph for singleass.c:

Functions
static bool	successor_conflicts_on_entity_p (successor s, entity e)
	helper thats checks if entity `e` is involved in a conflict of successor `s` More...

static bool	vertex_in_cycle_aux_p (vertex v, entity e, vertex curr, set visited)
	helper that checks if there is a cycle from `curr` back to `v` following chains of `e` More...

static bool	vertex_in_cycle_p (vertex v, entity e)
	check if there is a cycle from @pv to `v` following chains from `e` More...

static set	graph_to_live_writes (graph g, entity e)

static void	do_scalar_renaming_in_successors (vertex v, entity e, entity new, set live_writes, hash_table visited, hash_table renamings)

static void	do_scalar_renaming_in_vertex (vertex v, entity e, set live_writes, hash_table visited, hash_table renamings)

static void	do_scalar_renaming_in_graph (graph g, entity e)

static void	do_scalar_renaming (entity module, statement module_statement, graph dg)
	do scalar renaming for graph `dg` of module `module` and statements `module_statement` More...

static set	vertex_to_chains (vertex v, entity e, set visited)
	recursievly computes the set of all chains involving e starting from v More...

static void	do_prune_arcs (list l, list l2)
	we know l is included in l2, let's remove redundant arcs More...

static void	do_simplify_dg (graph g, entity e)
	remove all conflicts that involve entity e and that can be regenerated from another conflict chain More...

static void	simplify_dg (entity module, graph dg)
	removes redundant arcs from dg. More...

bool	scalar_renaming (char *mod_name)
	rename scalars to remove some false dependencies More...

Function Documentation

◆ do_prune_arcs()

static void do_prune_arcs	(	list	l,
		list	l2
	)

static

we know l is included in l2, let's remove redundant arcs

arc between prev and v are not needed

Definition at line 222 of file singleass.c.

                                            {
     bool same_chain_p = false;
     vertex prev = vertex_undefined;
     for(;!ENDP(l)&&!ENDP(l2);POP(l2)) {
         vertex v = VERTEX(CAR(l)),
                v2=VERTEX(CAR(l2));
         if(v==v2) {
             same_chain_p=true;
             prev=v;
             POP(l);
         }
         else if(same_chain_p) {
             /* arc between prev and v are not needed */
             set remove = set_make(set_pointer);
             FOREACH(SUCCESSOR,s,vertex_successors(prev))
                 if(v==successor_vertex(s))
                     set_add_element(remove,remove,s);
             SET_FOREACH(successor,s,remove)
                 gen_remove_once(&vertex_successors(prev),s);
             set_free(remove);
         }
     }
 }

References CAR, ENDP, FOREACH, gen_remove_once(), POP, set_add_element(), SET_FOREACH, set_free(), set_make(), set_pointer, SUCCESSOR, successor_vertex, VERTEX, vertex_successors, and vertex_undefined.

Referenced by do_simplify_dg().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ do_scalar_renaming()

static void do_scalar_renaming	(	entity	module,
		statement	module_statement,
		graph	dg
	)

static

do scalar renaming for graph dg of module module and statements module_statement

only local non static scalar entities non static as a quick fix ...

Definition at line 180 of file singleass.c.

                                                                                     {
  
     FOREACH(ENTITY,e,entity_declarations(module)) {
         /* only local non static scalar entities
          * non static as a quick fix ...*/
         if(local_entity_of_module_p(e,module) && entity_scalar_p(e) && !entity_static_variable_p(e))
             do_scalar_renaming_in_graph(dg,e);
     }
     module_clean_declarations(module,module_statement);
     unnormalize_expression(module_statement); // overkill ? It's not a game of kick-the-orphe
 }

References dg, do_scalar_renaming_in_graph(), ENTITY, entity_declarations, entity_scalar_p(), entity_static_variable_p(), FOREACH, local_entity_of_module_p(), module, module_clean_declarations(), module_statement, and unnormalize_expression().

Referenced by scalar_renaming().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ do_scalar_renaming_in_graph()

static void do_scalar_renaming_in_graph	(	graph	g,
		entity	e
	)

static

Definition at line 160 of file singleass.c.

                                                            {
     set live_writes = graph_to_live_writes(g, e);
     hash_table visited = hash_table_make(hash_pointer,HASH_DEFAULT_SIZE);
     hash_table renamings = hash_table_make(hash_pointer,HASH_DEFAULT_SIZE);
     list l = set_to_sorted_list(live_writes,compare_vertex);
     FOREACH(VERTEX,v,l) {
         statement s = vertex_to_statement(v);
         if(!declaration_statement_p(s) ||
                     gen_chunk_undefined_p(gen_find_eq(e,statement_declarations(s)))) 
             do_scalar_renaming_in_vertex(v,e,live_writes,visited,renamings);
     }
     hash_table_free(visited);
     HASH_FOREACH(entity,k,set,v,renamings) set_free(v);
     hash_table_free(renamings);
     gen_free_list(l);
     set_free(live_writes);
 }

References compare_vertex(), declaration_statement_p(), do_scalar_renaming_in_vertex(), FOREACH, gen_chunk_undefined_p, gen_find_eq(), gen_free_list(), graph_to_live_writes(), HASH_DEFAULT_SIZE, HASH_FOREACH, hash_pointer, hash_table_free(), hash_table_make(), set_free(), set_to_sorted_list(), statement_declarations, VERTEX, and vertex_to_statement().

Referenced by do_scalar_renaming().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ do_scalar_renaming_in_successors()

static void do_scalar_renaming_in_successors	(	vertex	v,
		entity	e,
		entity	new,
		set	live_writes,
		hash_table	visited,
		hash_table	renamings
	)

static

check if sink is read

this successor belongs to the def-use chain

was it already renamed ?

no -> proceeed

yes, but no conflict

yes and a conbflict -> fix it by adding an assign

Definition at line 102 of file singleass.c.

 {
     FOREACH(SUCCESSOR,s,vertex_successors(v)) {
         if(successor_conflicts_on_entity_p(s,e)) {
             vertex v2 = successor_vertex(s);
             bool read_p = false;
             /* check if sink is read */
             FOREACH(CONFLICT,c,dg_arc_label_conflicts(successor_arc_label(s))) {
                 if(effect_read_p(conflict_sink(c))) {
                     read_p= true;
                     break;
                 }
             }
             /* this successor belongs to the def-use chain */
             if(read_p && !set_belong_p(live_writes,v2)) {
                 /* was it already renamed ? */
                 entity renamed = (entity)hash_get(visited,v2);
                 /* no -> proceeed */
                 if(renamed == HASH_UNDEFINED_VALUE) {
                     hash_put(visited,v2,new);
                     replace_entity(vertex_to_statement(v2),e,new);
                     do_scalar_renaming_in_successors(v2,e,new,live_writes,visited,renamings);
                 }
                 /* yes, but no conflict */
                 else if (same_entity_p(renamed,new) ) {
                     continue;
                 }
                 /* yes and a conbflict -> fix it by adding an assign */
                 else { 
                     set renaming = (set) hash_get(renamings,v);
                     if(renaming == HASH_UNDEFINED_VALUE || !set_belong_p(renaming,new)) {
                         insert_statement(vertex_to_statement(v),
                                 make_assign_statement(entity_to_expression(renamed),entity_to_expression(new)),
                                 false);
                         if(renaming == HASH_UNDEFINED_VALUE)
                             renaming=set_make(set_pointer);
                         set_add_element(renaming,renaming,new);
                         hash_put_or_update(renamings,v,renaming);
                     }
                     continue;
                 }
             }
         }
     }
 }

References CONFLICT, conflict_sink, dg_arc_label_conflicts, effect_read_p, entity_to_expression(), FOREACH, hash_get(), hash_put(), hash_put_or_update, HASH_UNDEFINED_VALUE, insert_statement(), make_assign_statement(), replace_entity(), same_entity_p(), set_add_element(), set_belong_p(), set_make(), set_pointer, SUCCESSOR, successor_arc_label, successor_conflicts_on_entity_p(), successor_vertex, vertex_successors, and vertex_to_statement().

Referenced by do_scalar_renaming_in_vertex().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ do_scalar_renaming_in_vertex()

static void do_scalar_renaming_in_vertex	(	vertex	v,
		entity	e,
		set	live_writes,
		hash_table	visited,
		hash_table	renamings
	)

static

create new assigned value

propagate it to each reading successor

Definition at line 148 of file singleass.c.

                                                                                                                         {
  
     /* create new assigned value */
     entity new = make_new_scalar_variable_with_prefix(entity_user_name(e),get_current_module_entity(),copy_basic(entity_basic(e)));
     entity_initial(new)=copy_value(entity_initial(e));
     AddEntityToCurrentModule(new);
     replace_entity(vertex_to_statement(v),e,new);
     /* propagate it to each reading successor */
     do_scalar_renaming_in_successors(v,e,new,live_writes,visited,renamings);
 }

References AddEntityToCurrentModule(), copy_basic(), copy_value(), do_scalar_renaming_in_successors(), entity_basic(), entity_initial, entity_user_name(), get_current_module_entity(), make_new_scalar_variable_with_prefix(), replace_entity(), and vertex_to_statement().

Referenced by do_scalar_renaming_in_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ do_simplify_dg()

static void do_simplify_dg	(	graph	g,
		entity	e
	)

static

remove all conflicts that involve entity e and that can be regenerated from another conflict chain

SG: I am not sure it is ok to prune the exploration space like this

arcs now holds all possible arcs of g that impact e let's remove the chains that are not needed, that is those that have an englobing chain

if s is included in s2, arcs in s not is s2 are not needed

prune some arcs

Definition at line 249 of file singleass.c.

                                               {
     set chains = set_make(set_pointer);
     /* SG: I am not sure it is ok to prune the exploration space like this */
     set visited = set_make(set_pointer);
     FOREACH(VERTEX,v,graph_vertices(g)) {
         set tmp = vertex_to_chains(v,e,visited);
         set_union(chains,chains,tmp);
         set_free(tmp);
     }
     set_free(visited);
     /* arcs now holds all possible arcs of g that impact e
      * let's remove the chains that are not needed, that is those that have an englobing chain */
     SET_FOREACH(list,l,chains) {
         SET_FOREACH(list,l2,chains) {
             /* if s is included in s2, arcs in s not is s2 are not needed */
             if(l!=l2) {
                 set s = set_make(set_pointer);
                 set_assign_list(s,l);
                 set s2 = set_make(set_pointer);
                 set_assign_list(s2,l2);
                 /* prune some arcs */
                 if(set_inclusion_p(s,s2))
                     do_prune_arcs(l,l2);
                 set_free(s);
                 set_free(s2);
             }
         }
     }
 #if 0 //that's some ugly debug !
     FILE * fd = fopen("/tmp/a.dot","w");
     prettyprint_dot_dependence_graph(fd,get_current_module_statement(),g);
     fclose(fd);
 #endif
  
 }

References chains(), do_prune_arcs(), FOREACH, get_current_module_statement(), graph_vertices, prettyprint_dot_dependence_graph(), set_assign_list(), SET_FOREACH, set_free(), set_inclusion_p(), set_make(), set_pointer, set_union(), VERTEX, and vertex_to_chains().

Referenced by simplify_dg().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ graph_to_live_writes()

static set graph_to_live_writes	(	graph	g,
		entity	e
	)

static

Returns: the list of vertices for which a write on e leads to a new declaration that is writes without reductions or cycles

Definition at line 90 of file singleass.c.

                                                    {
     set live_writes = set_make(set_pointer);
     FOREACH(VERTEX,v,graph_vertices(g)){
         list effects = load_proper_rw_effects_list(vertex_to_statement(v));
         bool read_p = effects_read_variable_p(effects,e),
              write_p = effects_write_variable_p(effects,e);
         if( write_p && !read_p && !vertex_in_cycle_p(v,e) )
             set_add_element(live_writes,live_writes,v);
     }
     return live_writes;
 }

References effects_read_variable_p(), effects_write_variable_p(), FOREACH, graph_vertices, load_proper_rw_effects_list(), set_add_element(), set_make(), set_pointer, VERTEX, vertex_in_cycle_p(), and vertex_to_statement().

Referenced by do_scalar_renaming_in_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ scalar_renaming()

bool scalar_renaming ( char * mod_name )

rename scalars to remove some false dependencies

singleass.c

Get the resources

needed for vertex_to_statement

prune graph

Now do the job

Reorder the module, because new statements have been added

update/release resources

Parameters

mod_name od_name

Definition at line 300 of file singleass.c.

 {
     /* Get the resources */
     statement mod_stmt = (statement)
         db_get_memory_resource(DBR_CODE, mod_name, true);
     graph dg = (graph) db_get_memory_resource(DBR_DG, mod_name, true);
  
     set_current_module_statement(mod_stmt);
     set_current_module_entity(module_name_to_entity(mod_name));
     set_ordering_to_statement(mod_stmt); /* needed for vertex_to_statement */
  
     set_proper_rw_effects((statement_effects)
                     db_get_memory_resource(DBR_PROPER_EFFECTS, mod_name, true));
  
     debug_on("SCALAR_RENAMING_DEBUG_LEVEL");
  
     /* prune graph */
     simplify_dg(get_current_module_entity(),dg);
  
     /* Now do the job */
     do_scalar_renaming(get_current_module_entity(),get_current_module_statement(),dg);
  
     pips_assert("Statement is consistent after SCALAR_RENAMING",
             statement_consistent_p(mod_stmt));
  
     /* Reorder the module, because new statements have been added */
     module_reorder(mod_stmt);
  
     DB_PUT_MEMORY_RESOURCE(DBR_CODE, mod_name, mod_stmt);
  
     /* update/release resources */
     reset_current_module_statement();
     reset_current_module_entity();
     reset_proper_rw_effects();
         reset_ordering_to_statement();
  
     debug_off();
  
     return true;
 }

References db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, dg, do_scalar_renaming(), get_current_module_entity(), get_current_module_statement(), module_name_to_entity(), module_reorder(), pips_assert, reset_current_module_entity(), reset_current_module_statement(), reset_ordering_to_statement(), reset_proper_rw_effects(), set_current_module_entity(), set_current_module_statement(), set_ordering_to_statement(), set_proper_rw_effects(), simplify_dg(), and statement_consistent_p().

Here is the call graph for this function:

◆ simplify_dg()

static void simplify_dg	(	entity	module,
		graph	dg
	)

static

removes redundant arcs from dg.

An arc from v to v' is redundant if there exist a chain in dg that goes from v to v'

only local entity

Definition at line 288 of file singleass.c.

                                                  {
     FOREACH(ENTITY,e,entity_declarations(get_current_module_entity())) {
         /* only local entity */
         if(local_entity_of_module_p(e,module) && entity_scalar_p(e) ) {
             do_simplify_dg(dg,e);
         }
     }
 }

References dg, do_simplify_dg(), ENTITY, entity_declarations, entity_scalar_p(), FOREACH, get_current_module_entity(), local_entity_of_module_p(), and module.

Referenced by scalar_renaming().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ successor_conflicts_on_entity_p()

static bool successor_conflicts_on_entity_p	(	successor	s,
		entity	e
	)

static

helper thats checks if entity e is involved in a conflict of successor s

Definition at line 51 of file singleass.c.

                                                                    {
     FOREACH(CONFLICT,c,dg_arc_label_conflicts(successor_arc_label(s))) {
         if(same_entity_p(e,effect_any_entity(conflict_source(c))) ||
                 same_entity_p(e,effect_any_entity(conflict_sink(c)))
           )
             return true;
     }
     return false;
 }

References CONFLICT, conflict_sink, conflict_source, dg_arc_label_conflicts, effect_any_entity, FOREACH, same_entity_p(), and successor_arc_label.

Referenced by do_scalar_renaming_in_successors(), vertex_in_cycle_aux_p(), vertex_in_cycle_p(), and vertex_to_chains().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ vertex_in_cycle_aux_p()

static bool vertex_in_cycle_aux_p	(	vertex	v,
		entity	e,
		vertex	curr,
		set	visited
	)

static

helper that checks if there is a cycle from curr back to v following chains of e

Definition at line 61 of file singleass.c.

                                                                                {
     if(v==curr) return true;
     if(set_belong_p(visited,curr)) return false;
     set_add_element(visited,visited,curr);
     FOREACH(SUCCESSOR,s,vertex_successors(v)){
         if(successor_conflicts_on_entity_p(s,e) &&
                 vertex_in_cycle_aux_p(v,e,successor_vertex(s),visited))
             return true;
     }
     return false;
 }

References FOREACH, set_add_element(), set_belong_p(), SUCCESSOR, successor_conflicts_on_entity_p(), successor_vertex, and vertex_successors.

Referenced by vertex_in_cycle_p().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ vertex_in_cycle_p()

static bool vertex_in_cycle_p	(	vertex	v,
		entity	e
	)

static

check if there is a cycle from @pv to v following chains from e

Definition at line 74 of file singleass.c.

                                                    {
     set visited = set_make(set_pointer);
     FOREACH(SUCCESSOR,s,vertex_successors(v)){
         if(successor_conflicts_on_entity_p(s,e) &&
                 vertex_in_cycle_aux_p(v,e,successor_vertex(s),visited)) {
                 set_free(visited);
                 return true;
             }
     }
     set_free(visited);
     return false;
 }

References FOREACH, set_free(), set_make(), set_pointer, SUCCESSOR, successor_conflicts_on_entity_p(), successor_vertex, vertex_in_cycle_aux_p(), and vertex_successors.

Referenced by graph_to_live_writes().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ vertex_to_chains()

static set vertex_to_chains	(	vertex	v,
		entity	e,
		set	visited
	)

static

recursievly computes the set of all chains involving e starting from v

Definition at line 193 of file singleass.c.

                                                              {
     set all = set_make(set_pointer);
     if(!set_belong_p(visited,v)) {
         set_add_element(visited,visited,v);
         list effects = load_proper_rw_effects_list(vertex_to_statement(v));
         bool read_p = effects_read_variable_p(effects,e),
              write_p = effects_write_variable_p(effects,e);
         if(read_p||write_p) {
             list this = CONS(VERTEX,v,NIL);
             set_add_element(all,all,this);
             FOREACH(SUCCESSOR,s,vertex_successors(v)) {
                 if(successor_conflicts_on_entity_p(s,e)) {
                     vertex v2 = successor_vertex(s);
                     if(statement_ordering(vertex_to_statement(v2)) >
                             statement_ordering(vertex_to_statement(v)))
                     {
                         set tmp2=vertex_to_chains(v2,e,visited);
                         SET_FOREACH(list,ltmp,tmp2)
                             set_add_element(all,all,CONS(VERTEX,v,ltmp));
                         set_free(tmp2);
                     }
                 }
             }
         }
     }
     return all;
 }