#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "resources.h"
#include "misc.h"
#include "ri-util.h"
#include "prettyprint.h"
#include "effects-util.h"
#include "text-util.h"
#include "pipsdbm.h"
#include "effects-generic.h"
#include "effects-convex.h"
#include "effects-simple.h"
#include "accel-util.h"
#include "ray_dte.h"
#include "sommet.h"
#include "sg.h"
#include "polyedre.h"
#include "sac.h"
#include "ricedg.h"
#include "control.h"
#include "callgraph.h"

Include dependency graph for simdizer.c:

Data Structures
struct	simdizer_context

Macros
#define	SWAP_ARGUMENTS(c) do { call_arguments(c)=gen_nreverse(call_arguments(c)) ; return ;} while(0)

#define	NOSWAP_ARGUMENTS(c) return

Functions
static void	init_statement_matches_map (list l)

static void	free_statement_matches_map ()

static list	get_statement_matches (statement s)

match	get_statement_match_of_kind (statement s, opcodeClass kind)
	simdizer.c More...

static set	get_statement_matching_types (statement s)

static bool	conflict_is_a_real_conflict_p (conflict c, statement source, statement sink, size_t loop_level)
	this code is here because levels information seems inaccurate so it checks all the possible conflict between `source` and Â `sink` that could have generated `c` and then instead of using references_may_conflict, it assumes we are in ssa form which should be ok thanks to scalar renaming, and symbolically computes the distance between each reference More...

static bool	successor_only_has_rr_conflict_p (vertex v, successor su, size_t loop_level)

static void	free_statement_equivalence_table ()

static set	extract_non_conflicting_statements (statement s, list tail)

static set	extract_matching_statements (statement s, set stats, set *matches)

static bool	sac_statement_to_expressions_gather (expression e, list *l)

static list	sac_statement_to_expressions (statement s)

static bool	comparable_statements_on_distance_p (statement s0, statement s1)

static int	compare_statements_on_ordering (const void v0, const void v1)

static void	set_statement_origin (statement s)

static void	reset_statement_origin ()

static int	compare_statements_on_distance_to_origin (const void ps0, const void ps1)

static int	compare_list_from_length (const void v0, const void v1)

static list	order_isomorphic_statements_list (list ordered)

static list	order_isomorphic_statements (set s)

static void	init_statement_equivalence_table (list *l, graph dependence_graph, size_t loop_level)

static list	simdize_simple_statements_pass2 (list seq, float *simdCost)

static void	simdize_simple_statements (statement s, simdizer_context *sc)

static bool	simd_simple_sequence_filter (statement s, __attribute__((unused)) simdizer_context *sc)

string	sac_commenter (entity e)

static bool	incr_counter (loop l, simdizer_context *sc)

static void	decr_counter (loop l, simdizer_context *sc)

bool	simdizer (char *mod_name)

static void	do_simdizer_init (call c)

static void	do_split_block_statements (statement s)

static void	do_split_decl_block_statements (statement s)

bool	simdizer_init (const char *module_name)

Variables
static hash_table	matches = NULL

static hash_table	equivalence_table = hash_table_undefined

static statement	origin =NULL

statement	sac_current_block = statement_undefined

instruction	sac_real_current_instruction = instruction_undefined

Macro Definition Documentation

◆ NOSWAP_ARGUMENTS

#define NOSWAP_ARGUMENTS ( c ) return

◆ SWAP_ARGUMENTS

#define SWAP_ARGUMENTS ( c ) do { call_arguments(c)=gen_nreverse(call_arguments(c)) ; return ;} while(0)

Function Documentation

◆ comparable_statements_on_distance_p()

static bool comparable_statements_on_distance_p	(	statement	s0,
		statement	s1
	)

static

Definition at line 344 of file simdizer.c.

 {
     list exp0=sac_statement_to_expressions(s0),
         exp1=sac_statement_to_expressions(s1);
     list iter=exp1;
     FOREACH(EXPRESSION,e0,exp0)
     {
         expression e1 = EXPRESSION(CAR(iter));
         expression distance = distance_between_expression(e1,e0);
         intptr_t val=0;
         if(!expression_undefined_p(distance))
         {
             (void)expression_integer_value(distance,&val);
             free_expression(distance);
             if(val) return true;
         }
         POP(iter);
         if(ENDP(iter)) break;
     }
     return false;
 }

References CAR, distance_between_expression(), ENDP, EXPRESSION, expression_integer_value(), expression_undefined_p, FOREACH, free_expression(), intptr_t, POP, s1, and sac_statement_to_expressions().

Referenced by order_isomorphic_statements_list().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ compare_list_from_length()

static int compare_list_from_length	(	const void *	v0,
		const void *	v1
	)

static

Definition at line 469 of file simdizer.c.

 {
     const list l0=*(const list*)v0;
     const list l1=*(const list*)v1;
     size_t n0 = gen_length(l0);
     size_t n1 = gen_length(l1);
     return n0==n1 ? 0 : n0 > n1 ? 1 : -1;
 }

References gen_length().

Referenced by order_isomorphic_statements_list().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ compare_statements_on_distance_to_origin()

static int compare_statements_on_distance_to_origin	(	const void *	ps0,
		const void *	ps1
	)

static

Definition at line 415 of file simdizer.c.

                                                                                       {
     
     const statement s0 = *(const statement*)ps0;
     const statement s1 = *(const statement*)ps1;
     list expo=sac_statement_to_expressions(origin),
          exp0=sac_statement_to_expressions(s0),
          exp1=sac_statement_to_expressions(s1);
     size_t dist0=0,
            dist1=0;
     static const int dinf=1000;
  
     list iter0 = exp0,iter1=exp1;
     FOREACH(EXPRESSION,eo,expo)
     {
         expression e0 = ENDP(iter0)? expression_undefined:EXPRESSION(CAR(iter0)),
                    e1 = ENDP(iter1)? expression_undefined:EXPRESSION(CAR(iter1));
         expression distance0 = expression_undefined_p(e0) ? expression_undefined : distance_between_expression(eo,e0),
                    distance1 = expression_undefined_p(e1) ? expression_undefined : distance_between_expression(eo,e1);
         intptr_t val0=0, val1;
         if(!expression_undefined_p(distance0))
         {
             if(expression_integer_value(distance0,&val0)) {
                 dist0+=val0*val0;
             }
             else dist0+=dinf*dinf;
             free_expression(distance0);
  
         }
         else if(expression_scalar_p(e0) && expression_scalar_p(e1))
             dist0+=1;
         else
             dist0+=dinf*dinf;
         if(!expression_undefined_p(distance1))
         {
             if(expression_integer_value(distance1,&val1)) {
                 dist1+=val1*val1;
             }
             else dist1+=dinf*dinf;
             free_expression(distance1);
  
         }
         else if(expression_scalar_p(e0) && expression_scalar_p(e1))
             dist1+=1;
         else
             dist1+=dinf*dinf;
         POP(iter0);
         POP(iter1);
     }
     gen_free_list(expo);
     gen_free_list(exp0);
     gen_free_list(exp1);
     return dist0>dist1? 1 : dist0 == dist1 ? 0 : -1;
 }

References CAR, distance_between_expression(), ENDP, EXPRESSION, expression_integer_value(), expression_scalar_p, expression_undefined, expression_undefined_p, FOREACH, free_expression(), gen_free_list(), intptr_t, origin, POP, s1, and sac_statement_to_expressions().

Referenced by order_isomorphic_statements_list().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ compare_statements_on_ordering()

static int compare_statements_on_ordering	(	const void *	v0,
		const void *	v1
	)

static

Definition at line 365 of file simdizer.c.

 {
     const statement s0 = *(const statement*)v0;
     const statement s1 = *(const statement*)v1;
     if (statement_ordering(s0) > statement_ordering(s1)) return 1;
     if (statement_ordering(s0) < statement_ordering(s1)) return -1;
     return 0;
 }

References s1, and statement_ordering.

Referenced by init_statement_equivalence_table(), order_isomorphic_statements(), and order_isomorphic_statements_list().

Here is the caller graph for this function:

◆ conflict_is_a_real_conflict_p()

static bool conflict_is_a_real_conflict_p	(	conflict	c,
		statement	source,
		statement	sink,
		size_t	loop_level
	)

static

this code is here because levels information seems inaccurate so it checks all the possible conflict between source and Â sink that could have generated c and then instead of using references_may_conflict, it assumes we are in ssa form which should be ok thanks to scalar renaming, and symbolically computes the distance between each reference

hack no longer needed , simple is beautiful

Definition at line 138 of file simdizer.c.

                                                                                                            {
   pips_assert("true", source==source && sink==sink);
     cone co = conflict_cone(c);
     if(!cone_undefined_p(co)) {
         bool no_intra_loop_dep = true;
         FOREACH(INT,i,cone_levels(co))
           if(i == (int) loop_level +1 )
                 no_intra_loop_dep = false;
 #if 0 /* hack no longer needed , simple is beautiful */
         if(!no_intra_loop_dep) /* there seems to be an intra loop dep, verify this */ {
             reference sink_ref = effect_any_reference(conflict_sink(c)),
                       source_ref = effect_any_reference(conflict_source(c));
             if(same_entity_p(reference_variable(sink_ref),reference_variable(source_ref))) {
                 list sink_effects =  load_proper_rw_effects_list(sink),
                      source_effects = load_proper_rw_effects_list(source);
                 sink_effects = effect_read_p(conflict_sink(c))?
                     effects_read_effects(sink_effects):
                     effects_write_effects(sink_effects);
                 source_effects = effect_read_p(conflict_source(c))?
                     effects_read_effects(source_effects):
                     effects_write_effects(source_effects);
                 set sink_refs = set_make(set_pointer),
                     source_refs = set_make(set_pointer);
  
                 FOREACH(EFFECT,eff,sink_effects)
                     if(effects_may_conflict_p(eff,conflict_source(c)))
                         set_add_element(sink_refs,sink_refs,effect_any_reference(eff));
                 FOREACH(EFFECT,eff,source_effects)
                     if(effects_may_conflict_p(eff,conflict_sink(c)))
                         set_add_element(source_refs,source_refs,effect_any_reference(eff));
                 no_intra_loop_dep = true;
                 SET_FOREACH(reference,rsink,sink_refs) {
                     expression esink = reference_to_expression(rsink);
                     SET_FOREACH(reference,rsource,source_refs) {
                         expression esource = reference_to_expression(rsource);
                         expression d = distance_between_expression(esink,esource);
                         intptr_t val;
                         if(expression_undefined_p(d) ||
                                 !expression_integer_value(d,&val) ||
                                 val == 0) {
                             no_intra_loop_dep = false;
                         }
                     }
                 }
                 set_free(sink_refs);
                 set_free(source_refs);
                 gen_free_list(sink_effects);
                 gen_free_list(source_effects);
             }
         }
 #endif
         return !no_intra_loop_dep;
     }
     else
         return true;
 }

References cone_levels, cone_undefined_p, conflict_cone, conflict_sink, conflict_source, distance_between_expression(), EFFECT, effect_any_reference, effect_read_p, effects_may_conflict_p(), effects_read_effects(), effects_write_effects(), expression_integer_value(), expression_undefined_p, FOREACH, gen_free_list(), INT, intptr_t, load_proper_rw_effects_list(), pips_assert, reference_to_expression(), reference_variable, same_entity_p(), set_add_element(), SET_FOREACH, set_free(), set_make(), and set_pointer.

Referenced by successor_only_has_rr_conflict_p().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ decr_counter()

static void decr_counter	(	loop	l,
		simdizer_context *	sc
	)

static

Definition at line 843 of file simdizer.c.

                                                        {
   pips_assert("true", l==l);
     sc->nb_enclosing_loops--;
 }

References simdizer_context::nb_enclosing_loops, and pips_assert.

Referenced by simdizer().

Here is the caller graph for this function:

◆ do_simdizer_init()

static void do_simdizer_init ( call c )

static

constant first

then scalar

we finally end with two references

Definition at line 907 of file simdizer.c.

 {
 #define SWAP_ARGUMENTS(c) do { call_arguments(c)=gen_nreverse(call_arguments(c)) ; return ;} while(0)
 #define NOSWAP_ARGUMENTS(c)  return
     if(commutative_call_p(c))
     {
         pips_assert("commutative call are binary calls",gen_length(call_arguments(c))==2);
         expression e0 = binary_call_lhs(c),
                    e1 = binary_call_rhs(c);
         /* constant first */
         if(extended_expression_constant_p(e0)) NOSWAP_ARGUMENTS(c);
         if(extended_expression_constant_p(e1)) SWAP_ARGUMENTS(c);
         /* then scalar */
         if(expression_scalar_p(e0)) NOSWAP_ARGUMENTS(c);
         if(expression_scalar_p(e1)) SWAP_ARGUMENTS(c) ;
  
         /* we finally end with two references */
         if(expression_reference_or_field_p(e0) && expression_reference_or_field_p(e1))
         {
             expression distance = distance_between_expression(e0,e1);
             intptr_t val;
             if( !expression_undefined_p(distance) && expression_integer_value(distance,&val))
             {
                 free_expression(distance);
                 if(val <= 0) NOSWAP_ARGUMENTS(c);
                 else SWAP_ARGUMENTS(c) ;
             }
             else
             {
                 entity ent0 = expression_to_entity(e0);
                 entity ent1 = expression_to_entity(e1);
                 if(compare_entities(&ent0,&ent1)<=0) NOSWAP_ARGUMENTS(c);
                 else SWAP_ARGUMENTS(c) ;
             }
         }
         else
         {
             string msg = words_to_string(Words_Call(c,0,true,true));
             pips_user_warning("unable to decide how to commute %s\n",msg);
             free(msg);
         }
     }
 #undef SWAP_ARGUMENTS
 #undef NOSWAP_ARGUMENTS
 }

References binary_call_lhs, binary_call_rhs, call_arguments, commutative_call_p(), compare_entities(), distance_between_expression(), expression_integer_value(), expression_reference_or_field_p(), expression_scalar_p, expression_to_entity(), expression_undefined_p, extended_expression_constant_p(), free(), free_expression(), gen_length(), intptr_t, NOSWAP_ARGUMENTS, pips_assert, pips_user_warning, SWAP_ARGUMENTS, Words_Call(), and words_to_string().

Referenced by simdizer_init().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ do_split_block_statements()

static void do_split_block_statements ( statement s )

static

Definition at line 953 of file simdizer.c.

                                                    {
     if(statement_block_p(s)) {
         list blocks = NIL;
         list iter=statement_block(s);
         while(!ENDP(iter)) {
             list curr = NIL;
             bool block_created = false;
             do  {
                 statement st = STATEMENT(CAR(iter));
                 POP(iter);
                 if(entity_empty_label_p(statement_label(st)) ) {
                     if(!ENDP(curr)) 
                         blocks=CONS(STATEMENT,make_block_statement(curr),blocks);
                     blocks=CONS(STATEMENT,st,blocks);
                     block_created=true;
                 }
                 else
                     curr=CONS(STATEMENT,st,curr);
             } while(!ENDP(iter)&&!block_created);
             if(!block_created) {
               curr=gen_nreverse(curr);
               blocks=CONS(STATEMENT,make_block_statement(curr),blocks);
             }
         }
         gen_free_list(sequence_statements(statement_sequence(s)));
         sequence_statements(statement_sequence(s))=NIL;
         sequence_statements(statement_sequence(s))=gen_nreverse(blocks);
     }
 }

References blocks, CAR, CONS, ENDP, entity_empty_label_p(), gen_free_list(), gen_nreverse(), make_block_statement(), NIL, POP, sequence_statements, STATEMENT, statement_block(), statement_block_p, statement_label, and statement_sequence().

Referenced by simdizer_init().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ do_split_decl_block_statements()

static void do_split_decl_block_statements ( statement s )

static

is there a tail return ?

yes there is

is there a tail return ?

yes there is

not using insert_statement because it is too smart ! we want to keep a block

Definition at line 983 of file simdizer.c.

                                                         {
   if(statement_block_p(s)) {
     list iter,prev=NIL;
     for(iter=statement_block(s);!ENDP(iter) && declaration_statement_p(STATEMENT(CAR(iter))); POP(iter) ) {
       prev=iter;
     }
     if(!ENDP(iter) && !ENDP(prev) ) {
       CDR(prev)=NIL;
       statement tail = make_block_statement(iter);
       /* is there a tail return ? */
       list iter2,prev2=NIL;
       for(iter2=iter;!ENDP(iter2) && !return_statement_p(STATEMENT(CAR(iter2))); POP(iter2) ) {
         prev2=iter2;
       }
       if(!ENDP(iter2) && !ENDP(prev2) ) { /* yes there is */
         CDR(prev2)=NIL;
         statement rtail = make_block_statement(iter2);
         insert_statement_no_matter_what(STATEMENT(CAR(prev)),tail,false);
         insert_statement_no_matter_what(STATEMENT(CAR(prev)),rtail,false);
       }
       else {
         insert_statement_no_matter_what(STATEMENT(CAR(prev)),tail,false);
       }
     }
     else {
       /* is there a tail return ? */
       list iter2,prev2=NIL;
       for(iter2=iter=statement_block(s);!ENDP(iter2) && !return_statement_p(STATEMENT(CAR(iter2))); POP(iter2) ) {
         prev2=iter2;
       }
       if(!ENDP(iter2) && !ENDP(prev2) ) { /* yes there is */
         CDR(prev2)=NIL;
         statement rtail = make_block_statement(iter2);
         /* not using insert_statement because it is too smart ! we want to keep a block*/
         gen_append(statement_block(s),make_statement_list(rtail));
       }
     }
   }
 }

References CAR, CDR, declaration_statement_p(), ENDP, gen_append(), insert_statement_no_matter_what(), make_block_statement(), make_statement_list, NIL, POP, return_statement_p(), STATEMENT, statement_block(), and statement_block_p.

Referenced by simdizer_init().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ extract_matching_statements()

static set extract_matching_statements	(	statement	s,
		set	stats,
		set *	matches
	)

static

Definition at line 279 of file simdizer.c.

 {
   pips_assert("true", s==s);
     set out = set_make(set_pointer);
     SET_FOREACH(statement,st,stats)
     {
         set smt = get_statement_matching_types(st);
         set tmp = set_make(set_pointer);
         set_intersection(tmp,*matches,smt);
         if(set_empty_p(tmp))
         {
             set_free(tmp);
         }
         else {
             simd_fill_curArgType(st);
             if( simd_check_argType()){
                 *matches=tmp;
                 set_add_element(out,out,st);
             }
             else {
                 ifdebug(3){
                     pips_debug(3,"following statement does not have good arg type\n");
                     print_statement(st);
                 }
             }
         }
         set_free(smt);
     }
     return out;
 }

References get_statement_matching_types(), ifdebug, matches, out, pips_assert, pips_debug, print_statement(), set_add_element(), set_empty_p(), SET_FOREACH, set_free(), set_intersection(), set_make(), set_pointer, simd_check_argType(), and simd_fill_curArgType().

Referenced by simdize_simple_statements_pass2().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ extract_non_conflicting_statements()

static set extract_non_conflicting_statements	(	statement	s,
		list	tail
	)

static

Definition at line 257 of file simdizer.c.

 {
     list equivalences = (list)hash_get(equivalence_table,s);
     pips_assert("table is correct",equivalences!= HASH_UNDEFINED_VALUE);
  
     set eq = set_make(set_pointer);
     set_assign_list(eq,equivalences);
  
     set stail = set_make(set_pointer);
     set_assign_list(stail,tail);
  
     set_intersection(eq,eq,stail);
     set_free(stail);
     ifdebug(3) {
         pips_debug(3,"non conficting statement with\n");
         print_statement(s);
         SET_FOREACH(statement,st,eq)
             print_statement(st);
     }
  
     return eq;
 }

References eq, equivalence_table, hash_get(), HASH_UNDEFINED_VALUE, ifdebug, pips_assert, pips_debug, print_statement(), set_assign_list(), SET_FOREACH, set_free(), set_intersection(), set_make(), and set_pointer.

Referenced by simdize_simple_statements_pass2().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ free_statement_equivalence_table()

static void free_statement_equivalence_table ( )

static

leak spotted !

Definition at line 250 of file simdizer.c.

 {
     pips_assert("init called",!hash_table_undefined_p(equivalence_table));
     hash_table_free(equivalence_table);/* leak spotted !*/
     equivalence_table=hash_table_undefined;
 }

References equivalence_table, hash_table_free(), hash_table_undefined, hash_table_undefined_p, and pips_assert.

Referenced by simdize_simple_statements().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ free_statement_matches_map()

static void free_statement_matches_map ( )

static

Definition at line 81 of file simdizer.c.

 {
     hash_table_free(matches);
 }

References hash_table_free(), and matches.

Referenced by simdize_simple_statements().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_statement_match_of_kind()

match get_statement_match_of_kind	(	statement	s,
		opcodeClass	kind
	)

simdizer.c

Parameters

kind ind

Definition at line 101 of file simdizer.c.

 {
     list l = get_statement_matches(s);
  
     for( ; l!=NIL; l=CDR(l))
     {
         match m = MATCH(CAR(l));
         if (match_type(m) == kind)
             return m;
     }
  
     return match_undefined;
 }

References CAR, CDR, get_statement_matches(), MATCH, match_type, match_undefined, and NIL.

Referenced by make_simd_statements().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_statement_matches()

static list get_statement_matches ( statement s )

static

Definition at line 90 of file simdizer.c.

 {
     list m =(list)hash_get_default_empty_list(matches,s);
     return  m; 
 }

References hash_get_default_empty_list(), and matches.

Referenced by get_statement_match_of_kind(), and get_statement_matching_types().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_statement_matching_types()

static set get_statement_matching_types ( statement s )

static

Definition at line 119 of file simdizer.c.

 {
     set out = set_make(set_pointer);
  
     FOREACH(MATCH,m,get_statement_matches(s))
         set_add_element(out,out,match_type(m));
  
     return out;
 }

References FOREACH, get_statement_matches(), MATCH, match_type, out, set_add_element(), set_make(), and set_pointer.

Referenced by extract_matching_statements(), and simdize_simple_statements_pass2().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ incr_counter()

static bool incr_counter	(	loop	l,
		simdizer_context *	sc
	)

static

Definition at line 838 of file simdizer.c.

                                                        {
   pips_assert("true", l==l);
     sc->nb_enclosing_loops++;
     return true;
 }

References simdizer_context::nb_enclosing_loops, and pips_assert.

Referenced by simdizer().

Here is the caller graph for this function:

◆ init_statement_equivalence_table()

static void init_statement_equivalence_table	(	list *	l,
		graph	dependence_graph,
		size_t	loop_level
	)

static

for faster access

first extract corresponding vertices

then count the references between each other

do not take into account backward references, or R-R conflicts

now recursievly retreive the head of each vertex with no reference on them and reorder initial statement list

fill the head

found nothing, assume we are in the tail

remove those vertex from the head and decrease references elsewhere

do not take into account backward references and ignored statements

Definition at line 519 of file simdizer.c.

 {
     pips_assert("free was called",hash_table_undefined_p(equivalence_table));
     equivalence_table=hash_table_make(hash_pointer,HASH_DEFAULT_SIZE);
  
     /* for faster access */
     set statements = set_make(set_pointer);
     set_assign_list(statements,*l);
     hash_table counters = hash_table_make(hash_pointer,HASH_DEFAULT_SIZE);
  
     /* first extract corresponding vertices */
     FOREACH(VERTEX, a_vertex,graph_vertices(dependence_graph))
     {
         statement s = vertex_to_statement(a_vertex);
         if(set_belong_p(statements,s))
             hash_put(counters,a_vertex,(void*)0);
     }
     /* then count the references between each other */
     for(void *k,*v,*iter=NULL; (iter=hash_table_scan(counters,iter,&k,&v));)
     {
         FOREACH(SUCCESSOR,su,vertex_successors((vertex)k))
         {
             /* do not take into account backward references, or R-R conflicts */
             if(vertex_ordering(successor_vertex(su)) > vertex_ordering((vertex)k)  &&
                     !successor_only_has_rr_conflict_p((vertex)k,su,loop_level) )
             {
                 void* counter = hash_get(counters,successor_vertex(su));
                 if(counter != HASH_UNDEFINED_VALUE)
                 {
                     intptr_t value = (intptr_t)counter;
                     ++value;
                     pips_debug(4,"counter now is %td for\n",value);
                     ifdebug(4) print_statement(vertex_to_statement(successor_vertex(su)));
                     pips_debug(4,"referenced by\n");
                     ifdebug(4) print_statement(vertex_to_statement((vertex)k));
                     hash_update(counters,successor_vertex(su),(void*)value);
                 }
             }
         }
     }
  
     /* now  recursievly retreive the head of each vertex with no reference on them
      *  and reorder initial statement list */
     list new_l = NIL;
     while(!hash_table_empty_p(counters))
     {
         set head = set_make(set_pointer);
         /* fill the head */
         HASH_MAP(k,v,if((intptr_t)v == 0) set_add_element(head,head,k), counters);
         /* found nothing, assume we are in the tail */
         if(set_empty_p(head))
         {
             list equivalence_list = NIL;
             HASH_MAP(k,v,equivalence_list=CONS(STATEMENT,vertex_to_statement((vertex)k),equivalence_list),counters);
             HASH_MAP(k,v, hash_put(equivalence_table,vertex_to_statement((vertex)k),equivalence_list), counters);
             hash_table_clear(counters);
             new_l = gen_nconc(new_l, equivalence_list);
         }
         /* remove those vertex from the head and decrease references elsewhere */
         else
         {
             list equivalence_list = NIL;
             { SET_FOREACH(vertex,v,head) equivalence_list=CONS(STATEMENT,vertex_to_statement(v),equivalence_list); }
             gen_sort_list(equivalence_list, compare_statements_on_ordering);
  
             SET_FOREACH(vertex,v,head) {
                 FOREACH(SUCCESSOR,su,vertex_successors(v)) {
                     void* counter = hash_get(counters,successor_vertex(su));
                     /* do not take into account backward references and ignored statements */
                     if(counter != HASH_UNDEFINED_VALUE && vertex_ordering(successor_vertex(su)) > vertex_ordering(v) && !successor_only_has_rr_conflict_p(v,su,loop_level))
                     {
                         intptr_t value = (intptr_t)counter;
                         --value;
                         pips_assert("not missed something",value>=0);
                         hash_update(counters,successor_vertex(su),(void*)value);
                     }
                 }
                 if(hash_get(equivalence_table,vertex_to_statement(v))!=HASH_UNDEFINED_VALUE)
                         pips_internal_error("failed");
                 hash_put(equivalence_table,vertex_to_statement(v),gen_copy_seq(equivalence_list));
                 hash_del(counters,v);
             }
             new_l = gen_nconc(new_l, equivalence_list);
  
         }
         set_free(head);
     }
     hash_table_free(counters);
     gen_free_list(*l);
     *l = new_l;
 }

References compare_statements_on_ordering(), CONS, dependence_graph, equivalence_table, FOREACH, gen_copy_seq(), gen_free_list(), gen_nconc(), gen_sort_list(), graph_vertices, HASH_DEFAULT_SIZE, hash_del(), hash_get(), HASH_MAP, hash_pointer, hash_put(), hash_table_clear(), hash_table_empty_p, hash_table_free(), hash_table_make(), hash_table_scan(), hash_table_undefined_p, HASH_UNDEFINED_VALUE, hash_update(), ifdebug, intptr_t, NIL, pips_assert, pips_debug, pips_internal_error, print_statement(), set_add_element(), set_assign_list(), set_belong_p(), set_empty_p(), SET_FOREACH, set_free(), set_make(), set_pointer, STATEMENT, SUCCESSOR, successor_only_has_rr_conflict_p(), successor_vertex, VERTEX, vertex_ordering(), vertex_successors, and vertex_to_statement().

Referenced by simdize_simple_statements().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ init_statement_matches_map()

static void init_statement_matches_map ( list l )

static

Definition at line 66 of file simdizer.c.

 {
     matches = hash_table_make(hash_pointer, 0);
     FOREACH(STATEMENT, s,l)
     {
         list match = match_statement(s);
  
         if (match != NIL)
             hash_put(matches, (void *)s, (void *)match);
     }
 }

References FOREACH, hash_pointer, hash_put(), hash_table_make(), match_statement(), matches, NIL, and STATEMENT.

Referenced by simdize_simple_statements().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ order_isomorphic_statements()

static list order_isomorphic_statements ( set s )

static

Definition at line 508 of file simdizer.c.

                                                {
     list ordered = set_to_sorted_list(s,compare_statements_on_ordering);
     return order_isomorphic_statements_list(ordered);
 }

References compare_statements_on_ordering(), order_isomorphic_statements_list(), and set_to_sorted_list().

Referenced by simdize_simple_statements_pass2().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ order_isomorphic_statements_list()

static list order_isomorphic_statements_list ( list ordered )

static

Definition at line 478 of file simdizer.c.

 {
     gen_sort_list(ordered,compare_statements_on_ordering);
     list heads = NIL;
     while(!ENDP(ordered)) {
         statement head = STATEMENT(CAR(ordered));
         list firsts = CONS(STATEMENT,head,NIL);
         list lasts = NIL;
         FOREACH(STATEMENT,st,CDR(ordered))
         {
             if(comparable_statements_on_distance_p(head,st))
                 firsts=CONS(STATEMENT,st,firsts);
             else
                 lasts=CONS(STATEMENT,st,lasts);
         }
         gen_free_list(ordered);
         set_statement_origin(head);
         gen_sort_list(firsts,compare_statements_on_distance_to_origin);
         reset_statement_origin();
         gen_sort_list(lasts,compare_statements_on_ordering);
         heads=CONS(LIST,firsts,heads);
         ordered=lasts;
     }
     gen_sort_list(heads,compare_list_from_length);
     list out = NIL;
     FOREACH(LIST,l,heads)
         out=gen_nconc(l,out);
     gen_free_list(heads);
     return out;
 }

References CAR, CDR, comparable_statements_on_distance_p(), compare_list_from_length(), compare_statements_on_distance_to_origin(), compare_statements_on_ordering(), CONS, ENDP, FOREACH, gen_free_list(), gen_nconc(), gen_sort_list(), LIST, NIL, out, reset_statement_origin(), set_statement_origin(), and STATEMENT.

Referenced by order_isomorphic_statements(), and simdize_simple_statements_pass2().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ reset_statement_origin()

static void reset_statement_origin ( )

static

Definition at line 413 of file simdizer.c.

413 {origin=NULL;}

References origin.

Referenced by order_isomorphic_statements_list().

Here is the caller graph for this function:

◆ sac_commenter()

string sac_commenter ( entity e )

Definition at line 821 of file simdizer.c.

 {
     if(sac_aligned_entity_p(e))
     {
         return strdup("SAC generated temporary array");
     }
     else if(simd_vector_entity_p(e))
     {
         string s,g = basic_to_string(entity_basic(e));
         asprintf(&s,"PIPS:SAC generated %s vector(s)", g);
         free(g);
         return s;
     }
     else
         return strdup("PIPS:SAC generated variable");
 }

References asprintf, basic_to_string(), entity_basic(), free(), sac_aligned_entity_p(), simd_vector_entity_p(), and strdup().

Referenced by simdizer().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sac_statement_to_expressions()

static list sac_statement_to_expressions ( statement s )

static

Definition at line 320 of file simdizer.c.

 {
     list out = NIL;
     gen_context_recurse(s, &out, expression_domain, sac_statement_to_expressions_gather, gen_null2);
     return out;
 }

References expression_domain, gen_context_recurse, gen_null2(), NIL, out, and sac_statement_to_expressions_gather().

Referenced by comparable_statements_on_distance_p(), and compare_statements_on_distance_to_origin().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sac_statement_to_expressions_gather()

static bool sac_statement_to_expressions_gather	(	expression	e,
		list *	l
	)

static

Definition at line 310 of file simdizer.c.

 {
     if(expression_reference_or_field_p(e))
     {
         *l=CONS(EXPRESSION,e,*l);
         return false;
     }
     return true;
 }

References CONS, EXPRESSION, and expression_reference_or_field_p().

Referenced by sac_statement_to_expressions().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ set_statement_origin()

static void set_statement_origin ( statement s )

static

Definition at line 412 of file simdizer.c.

412 {origin=s;}

References origin.

Referenced by order_isomorphic_statements_list().

Here is the caller graph for this function:

◆ simd_simple_sequence_filter()

static bool simd_simple_sequence_filter	(	statement	s,
		__attribute__((unused)) simdizer_context *	sc
	)

static

Definition at line 816 of file simdizer.c.

 {
     return ! ( instruction_call_p( statement_instruction(s) ) ) ;
 }

References instruction_call_p, and statement_instruction.

Referenced by simdizer().

Here is the caller graph for this function:

◆ simdize_simple_statements()

static void simdize_simple_statements	(	statement	s,
		simdizer_context *	sc
	)

static

not much we can do with a single statement, or with "complex" statements (ie, with tests/loops/...)

we cannot handle anything but sequence of calls

process already existing statements

Definition at line 740 of file simdizer.c.

 {
     /* not much we can do with a single statement, or with
      * "complex" statements (ie, with tests/loops/...)
      */
     if (statement_block_p(s))
     {
         graph dependence_graph = sc->dg;
         sac_current_block=s;
         /* we cannot handle anything but sequence of calls */
         list iter = statement_block(s);
         sac_real_current_instruction = statement_instruction(s);
         statement_instruction(s)=make_instruction_block(NIL);
  
         list new_seq = NIL;
         while(!ENDP(iter))
         {
             list seq = NIL;
             for(;!ENDP(iter);POP(iter))
             {
                 statement st = STATEMENT(CAR(iter));
                 if(declaration_statement_p(st))
                     insert_statement_no_matter_what(s,st,false);
                 else {
                     if(statement_call_p(st))
                         seq=CONS(STATEMENT,st,seq);
  
                     if(!statement_call_p(st)||ENDP(CDR(iter)))
                     {
                         /* process already existing statements */
                         if(!ENDP(seq))
                         {
                             seq=gen_nreverse(seq);
  
                             init_statement_matches_map(seq);
                             init_statement_equivalence_table(&seq,dependence_graph,sc->nb_enclosing_loops);
  
                             float saveSimdCost = 0;
                             list simdseq = simdize_simple_statements_pass2(seq, &saveSimdCost);
  
                             pips_debug(2,"opcode cost1 %f\n", saveSimdCost);
  
                             if((saveSimdCost >= 0.0))
                             {
                                 new_seq=gen_append(new_seq,seq);
                                 gen_free_list(simdseq);
                             }
                             else
                             {
                                 new_seq=gen_append(new_seq,simdseq);
                                 gen_free_list(seq);
                                 sc->result |= true;
                             }
  
                             free_statement_matches_map();
                             free_statement_equivalence_table();
                             seq=NIL;
  
                         }
                         if(!statement_call_p(st))
                             new_seq=gen_append(new_seq,CONS(STATEMENT,st,NIL));
                     }
                 }
  
             }
         }
         sequence_statements(instruction_sequence(statement_instruction(s)))=
             gen_append(statement_block(s),new_seq);
     }
 }

References CAR, CDR, CONS, declaration_statement_p(), dependence_graph, simdizer_context::dg, ENDP, free_statement_equivalence_table(), free_statement_matches_map(), gen_append(), gen_free_list(), gen_nreverse(), init_statement_equivalence_table(), init_statement_matches_map(), insert_statement_no_matter_what(), instruction_sequence, make_instruction_block(), simdizer_context::nb_enclosing_loops, NIL, pips_debug, POP, simdizer_context::result, sac_current_block, sac_real_current_instruction, sequence_statements, simdize_simple_statements_pass2(), STATEMENT, statement_block(), statement_block_p, statement_call_p(), and statement_instruction.

Referenced by simdizer().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ simdize_simple_statements_pass2()

static list simdize_simple_statements_pass2	(	list	seq,
		float *	simdCost
	)

static

Traverse to list to group isomorphic statements

if this is not a recognized statement (ie, no match), skip it

try to find all the compatible isomorphic statements after the current statement

if the matches for statement sj and for the group have a non-empty intersection, and the move is legal (ie, does not break dependency chain) then we can add the statement sj to the group.

filter out already visited statements

Free the list of statements info

Set the new list as the statements' instructions

Definition at line 611 of file simdizer.c.

 {
     list newseq=NIL;
  
     //argument info dependencies are local to each sequence -> RESET
     init_vector_to_expressions();
  
     set visited = set_make(set_pointer);
  
     /* Traverse to list to group isomorphic statements */
     for(list  i = seq;!ENDP(i);POP(i))
     {
         statement si = STATEMENT(CAR(i));
         if(!set_belong_p(visited,si))
         {
             set_add_element(visited,visited,si);
             ifdebug(3){
                 pips_debug(3,"trying to match statement\n");
                 print_statement(si);
             }
  
             /* if this is not a recognized statement (ie, no match), skip it */
             set group_matches = get_statement_matching_types(si);
             if (set_empty_p(group_matches) )
             {
                 pips_debug(3,"no match found\n");
                 invalidate_expressions_in_statement(si);
                 newseq = CONS(STATEMENT,si,newseq);
                 continue;
             }
             else 
             {
                 ifdebug(3) {
                     pips_debug(3,"matching opcode found:\n");
                     SET_FOREACH(opcodeClass,oc,group_matches)
                         pips_debug(3,"%s\n",opcodeClass_name(oc));
                 }
             }
  
             simd_fill_finalArgType(si);
             ifdebug(3) {
                 pips_debug(3,"examining following statments:\n");
                 print_statements(CDR(i));
             }
  
             /* try to find all the compatible isomorphic statements after the
              * current statement
              */
             /* if the matches for statement sj and for the group have a non-empty
              * intersection, and the move is legal (ie, does not break dependency
              * chain) then we can add the statement sj to the group.
              */
             set non_conflicting = extract_non_conflicting_statements(si,CDR(i));
             /* filter out already visited statements */
             set_difference(non_conflicting,non_conflicting,visited);
             set isomorphics = extract_matching_statements(si,non_conflicting,&group_matches);
             if(set_empty_p(isomorphics))
             {
                 ifdebug(3){
                     pips_debug(3,"following statement cannot be moved\n");
                     print_statement(si);
                 }
                 invalidate_expressions_in_statement(si);
                 newseq = CONS(STATEMENT,si,newseq);
             }
             else
             {
                 set_add_element(isomorphics,isomorphics,si);
                 ifdebug(3){
                     pips_debug(3,"following statements matches!\n");
                     SET_FOREACH(statement,sj,isomorphics)
                         print_statement(sj);
                 }
                 list iso_stats = order_isomorphic_statements(isomorphics);
                 set_free(isomorphics);
                 for(list iso_iter=iso_stats;!ENDP(iso_iter);)
                 {
                     simdstatement ss = make_simd_statements(group_matches, iso_iter);
                     if(simdstatement_undefined_p(ss))
                     {
                         invalidate_expressions_in_statement(si);
                         newseq = CONS(STATEMENT,si,newseq);
                         POP(iso_iter);
                         break;
                     }
                     else
                     {
                         newseq=gen_append(generate_simd_code(ss,simdCost),newseq);
                         for(intptr_t i= opcode_vectorSize(simdstatement_opcode(ss));i!=0;i--)
                         {
                             set_add_element(visited,visited,STATEMENT(CAR(iso_iter)));
                             POP(iso_iter);
                         }
                         iso_iter=order_isomorphic_statements_list(iso_iter);
                     }
                 }
                 set_free(group_matches);
                 //gen_free_list(iso_stats);
             }
             simd_reset_finalArgType();
         }
     }
     reset_vector_to_expressions();
     newseq=gen_nreverse(newseq);
  
     /* Free the list of statements info */
  
     /* Set the new list as the statements' instructions */
     return newseq;
 }

References CAR, CDR, CONS, ENDP, extract_matching_statements(), extract_non_conflicting_statements(), gen_append(), gen_nreverse(), generate_simd_code(), get_statement_matching_types(), ifdebug, init_vector_to_expressions(), intptr_t, invalidate_expressions_in_statement(), make_simd_statements(), NIL, opcode_vectorSize, opcodeClass_name, order_isomorphic_statements(), order_isomorphic_statements_list(), pips_debug, POP, print_statement(), print_statements(), reset_vector_to_expressions(), set_add_element(), set_belong_p(), set_difference(), set_empty_p(), SET_FOREACH, set_free(), set_make(), set_pointer, simd_fill_finalArgType(), simd_reset_finalArgType(), simdstatement_opcode, simdstatement_undefined_p, and STATEMENT.

Referenced by simdize_simple_statements().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ simdizer()

bool simdizer ( char * mod_name )

get the resources

Now do the job

Reorder the module, because new statements have been added

update/release resources

Parameters

mod_name od_name

Definition at line 854 of file simdizer.c.

 {
     /* get the resources */
     statement mod_stmt = (statement)
         db_get_memory_resource(DBR_CODE, 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);
     simdizer_context sc = { .dg = (graph) db_get_memory_resource(DBR_DG, mod_name, true),
         .nb_enclosing_loops = 0,
                             .result = false };
     set_simd_treematch((matchTree)db_get_memory_resource(DBR_SIMD_TREEMATCH,"",true));
     set_simd_operator_mappings(db_get_memory_resource(DBR_SIMD_OPERATOR_MAPPINGS,"",true));
     statement_effects se = (statement_effects)db_get_memory_resource(DBR_PROPER_EFFECTS,mod_name,true);
     remove_preferences(se);
     set_proper_rw_effects(se);
     push_generated_variable_commenter(sac_commenter);
     set_conflict_testing_properties();
  
     debug_on("SIMDIZER_DEBUG_LEVEL");
  
     /* Now do the job */
     gen_context_multi_recurse(mod_stmt, &sc, statement_domain,
             simd_simple_sequence_filter, simdize_simple_statements,
             loop_domain, incr_counter,decr_counter,
             NULL);
  
     pips_assert("Statement is consistent after SIMDIZER", 
             statement_consistent_p(mod_stmt));
  
     /* Reorder the module, because new statements have been added */  
     clean_up_sequences(mod_stmt);
     module_reorder(mod_stmt);
     DB_PUT_MEMORY_RESOURCE(DBR_CODE, mod_name, mod_stmt);
     DB_PUT_MEMORY_RESOURCE(DBR_CALLEES, mod_name, compute_callees(mod_stmt));
     //DB_PUT_MEMORY_RESOURCE(DBR_DG, mod_name, dependence_graph);
  
     /* update/release resources */
     reset_proper_rw_effects();
     reset_simd_operator_mappings();
     reset_simd_treematch();
         reset_ordering_to_statement();
     reset_current_module_statement();
     reset_current_module_entity();
     pop_generated_variable_commenter();
  
     debug_off();
  
     return sc.result;
 }

References clean_up_sequences(), compute_callees(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, decr_counter(), simdizer_context::dg, gen_context_multi_recurse(), incr_counter(), loop_domain, module_name_to_entity(), module_reorder(), pips_assert, pop_generated_variable_commenter(), push_generated_variable_commenter(), remove_preferences(), reset_current_module_entity(), reset_current_module_statement(), reset_ordering_to_statement(), reset_proper_rw_effects(), reset_simd_operator_mappings(), reset_simd_treematch(), simdizer_context::result, sac_commenter(), set_conflict_testing_properties(), set_current_module_entity(), set_current_module_statement(), set_ordering_to_statement(), set_proper_rw_effects(), set_simd_operator_mappings(), set_simd_treematch(), simd_simple_sequence_filter(), simdize_simple_statements(), statement_consistent_p(), and statement_domain.

Here is the call graph for this function:

◆ simdizer_init()

bool simdizer_init ( const char * module_name )

get the resources

normalize blocks

then split blocks containing declarations statement

then split blocks containing labeled statement

sort commutative operators

reset

Parameters

module_name odule_name

Definition at line 1023 of file simdizer.c.

 {
     /* get the resources */
     set_current_module_statement((statement)db_get_memory_resource(DBR_CODE, module_name, true));
     set_current_module_entity(module_name_to_entity(module_name));
  
     /* normalize blocks */
     clean_up_sequences(get_current_module_statement());
  
     /* then split blocks containing declarations statement */
     gen_recurse(get_current_module_statement(), statement_domain, gen_true, do_split_decl_block_statements);
  
     /* then split blocks containing labeled statement */
     gen_recurse(get_current_module_statement(), statement_domain, gen_true, do_split_block_statements);
  
     /* sort commutative operators */
     gen_recurse(get_current_module_statement(),call_domain,gen_true,do_simdizer_init);
  
     module_reorder(get_current_module_statement());
     DB_PUT_MEMORY_RESOURCE(DBR_CODE, module_name, get_current_module_statement());
  
     /* reset */
     reset_current_module_statement();
     reset_current_module_entity();
  
     return true;
  
 }

References call_domain, clean_up_sequences(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, do_simdizer_init(), do_split_block_statements(), do_split_decl_block_statements(), gen_recurse, gen_true(), 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:

◆ successor_only_has_rr_conflict_p()

static bool successor_only_has_rr_conflict_p	(	vertex	v,
		successor	su,
		size_t	loop_level
	)

static

regions tell us there is a conflict. check if the dependence is loop carried or not

Definition at line 195 of file simdizer.c.

 {
     bool all_rr = true;
     FOREACH(CONFLICT,c,dg_arc_label_conflicts(successor_arc_label(su)))
     {
         if(effect_read_p(conflict_sink(c))&&
                 effect_read_p(conflict_source(c))
           )
         {
             pips_debug(3,
                        "conflict skipped between %s and %s\n",
                        reference_to_string(effect_any_reference(conflict_sink(c))),
                        reference_to_string(effect_any_reference(conflict_source(c))));
         }
         else {
 #if 0
             list inter = region_intersection(conflict_sink(c),conflict_source(c));
             if(ENDP(inter)) // why is this conflict generated ?!?
             {
                 pips_debug(3,
                            "conflict skipped between %s and %s\n",
                            reference_to_string(effect_any_reference(conflict_sink(c))),
                            reference_to_string(effect_any_reference(conflict_source(c))));
                 continue;
             }
             gen_full_free_list(inter);
 #endif
             /* regions tell us there is a conflict.
              * check if the dependence is loop carried or not
              * */
             all_rr=!conflict_is_a_real_conflict_p(c,vertex_to_statement(v),vertex_to_statement(successor_vertex(su)),loop_level);
  
             if(!all_rr) {
                 pips_debug(3,"conflict found :\n");
                 ifdebug(3) {
                     print_region(conflict_sink(c));
                     print_region(conflict_source(c));
                 }
             }
             else {
                 pips_debug(3,
                         "conflict not relevant between:\n");
                 ifdebug(3) {
                     print_region(conflict_sink(c));
                     print_region(conflict_source(c));
                 }
             }
         }
     }
     return all_rr;
 }