propagation.c File Reference

#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 "pipsdbm.h"
#include "reductions.h"
#include "expressions.h"
#include "dg.h"
#include "graph.h"
#include "ricedg.h"
#include "control.h"

Include dependency graph for propagation.c:

Go to the source code of this file.

Typedefs
typedef dg_arc_label	arc_label
typedef dg_vertex_label	vertex_label

Functions
static void	do_reduction_propagation (graph dg)
	sg: this function does a huge pattern matching :) and is not very smart More...
bool	reduction_propagation (const char *mod_name)
	now try to backward propagate the reduction, if it is meaningful. More...
static reference	guess_potential_reduction (successor su, conflict *relevant)
static bool	potential_reduction_substitution_valid_p (list sus, conflict legal_conflict, reference ref)
static bool	do_reduction_detection (graph dg)
	sg: this function does a huge pattern matching :) and is not very smart More...
bool	reduction_detection (const char *mod_name)

Typedef Documentation

arc_label

typedef dg_arc_label arc_label

Definition at line 44 of file propagation.c.

vertex_label

typedef dg_vertex_label vertex_label

Definition at line 45 of file propagation.c.

Function Documentation

do_reduction_detection()

static bool do_reduction_detection ( graph  dg )

static

sg: this function does a huge pattern matching :) and is not very smart

lazy ... s = f(sigma)

lazier , only scalar on lhs

lazier, only intrinsic call on rhs

look for a potential reduction

even lazier

verify validity of the substitution

Definition at line 187 of file propagation.c.

                                             {
    set seen = set_make(set_pointer);
    FOREACH(VERTEX, v,graph_vertices(dg))
    {
        statement s = vertex_to_statement(v);
        if(!set_belong_p(seen,s) ) {
            set_add_element(seen,seen,s);
            /* lazy ... s = f(sigma) */
            if(assignment_statement_p(s)) {
                expression assigned_exp = binary_call_lhs(statement_call(s));
                /* lazier , only scalar on lhs */
                if(expression_scalar_p(assigned_exp)) {
                    expression rhs = binary_call_rhs(statement_call(s));
                    /* lazier, only intrinsic call on rhs */
                    if(expression_call_p(rhs)) {
                        reference assigned_ref = expression_reference(assigned_exp);
                        conflict cculprit = conflict_undefined;
                        call rhs_call = expression_call(rhs);
                        entity rhs_op = call_function(rhs_call);
                        if(intrinsic_entity_p(rhs_op)) {
                            reference potential_reduction = reference_undefined;
                            /* look for a potential reduction */
                            FOREACH(SUCCESSOR,su,vertex_successors(v)) {
                                vertex sv = successor_vertex(su);
                                statement ssv = vertex_to_statement(sv);
                                /* even lazier */
                                if(assignment_statement_p(ssv)) {
                                    expression assigned_exp_sv = binary_call_lhs(statement_call(ssv));
                                    if(expression_scalar_p(assigned_exp_sv)) {
                                        reference assigned_ref_sv = expression_reference(assigned_exp_sv);
                                        potential_reduction = guess_potential_reduction(su,&cculprit);
                                        if(!reference_undefined_p(potential_reduction) &&
                                                reference_equal_p(potential_reduction,assigned_ref_sv)) {
                                            break;
                                        }
                                    }
                                }
                            }
                            /* verify validity of the substitution */
                            if(!reference_undefined_p(potential_reduction)) {
                                if(potential_reduction_substitution_valid_p(vertex_successors(v),cculprit,potential_reduction)) {
                                    pips_debug(1,"replacing %s by %s\n",entity_user_name(reference_variable(assigned_ref)),entity_user_name(reference_variable(potential_reduction)));
                                    RemoveLocalEntityFromDeclarations(reference_variable(assigned_ref),get_current_module_entity(),get_current_module_statement());
                                    replace_reference(get_current_module_statement(),assigned_ref,reference_variable(potential_reduction));
                                    set_free(seen);
                                    return true;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    set_free(seen);
    return false;
}

References assignment_statement_p(), binary_call_lhs, binary_call_rhs, call_function, conflict_undefined, dg, entity_user_name(), expression_call(), expression_call_p(), expression_reference(), expression_scalar_p, FOREACH, get_current_module_entity(), get_current_module_statement(), graph_vertices, guess_potential_reduction(), intrinsic_entity_p(), pips_debug, potential_reduction_substitution_valid_p(), reference_equal_p(), reference_undefined, reference_undefined_p, reference_variable, RemoveLocalEntityFromDeclarations(), replace_reference(), seen, set_add_element(), set_belong_p(), set_free(), set_make(), set_pointer, statement_call(), SUCCESSOR, successor_vertex, VERTEX, vertex_successors, and vertex_to_statement().

Referenced by reduction_detection().

Here is the call graph for this function:

Here is the caller graph for this function:

do_reduction_propagation()

static void do_reduction_propagation ( graph  dg )

static

sg: this function does a huge pattern matching :) and is not very smart

lazy ... s = f(sigma)

lazier

even lazier

we got some simple reductions here, try to propagate them backward

Definition at line 57 of file propagation.c.

                                               {
    set seen = set_make(set_pointer);
    FOREACH(VERTEX, v,graph_vertices(dg))
    {
        statement s = vertex_to_statement(v);
        if(!set_belong_p(seen,s)) {
            set_add_element(seen,seen,s);
            /* lazy ... s = f(sigma) */
            if(assignment_statement_p(s)) {
                expression assigned_exp = binary_call_lhs(statement_call(s));
                /* lazier */
                if(expression_reference_p(assigned_exp)) {
                    expression rhs = binary_call_rhs(statement_call(s));
                    if(expression_call_p(rhs)) {
                        reference assigned_ref = expression_reference(assigned_exp);
                        if(reference_scalar_p(assigned_ref)) {
                            call rhs_call = expression_call(rhs);
                            entity rhs_op = call_function(rhs_call);
 
                            FOREACH(SUCCESSOR,su,vertex_successors(v)) {
                                vertex sv = successor_vertex(su);
                                statement ssv = vertex_to_statement(sv);
                                /* even lazier */
                                if(assignment_statement_p(ssv)) {
                                    list reductions = reductions_list(load_proper_reductions(ssv));
                                    /* we got some simple reductions here, try to propagate them backward */
                                    if(gen_length(reductions) == 1 ) {
                                        reduction red = REDUCTION(CAR(reductions));
                                        if(same_entity_p(reduction_operator_entity(reduction_op(red)),rhs_op)) {
                                            FOREACH(CONFLICT,con,dg_arc_label_conflicts(successor_arc_label(su))) {
                                                if(effect_read_p(conflict_sink(con)) &&
                                                        effect_write_p(conflict_source(con)) &&
                                                        reference_equal_p(effect_any_reference(conflict_source(con)),assigned_ref)) {
                                                    expression rhs_fst_arg =EXPRESSION(CAR(call_arguments(rhs_call)));
                                                    if(expression_scalar_p(rhs_fst_arg)) {
                                                        reference rhs_fst_ref = copy_reference(expression_reference(rhs_fst_arg));
                                                        expression red_exp = reference_to_expression(reduction_reference(red));
                                                        replace_entity_by_expression(s,reference_variable(rhs_fst_ref),red_exp);
                                                        replace_reference(ssv,assigned_ref,reference_variable(rhs_fst_ref));
                                                        replace_entity_by_expression(s,reference_variable(assigned_ref),red_exp);
                                                        free_reference(rhs_fst_ref);
                                                        syntax_reference(expression_syntax(red_exp))=reference_undefined;
                                                        free_expression(red_exp);
                                                    }
                                                    else pips_user_warning("replacement of non reference expression not implemented yet \n");
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    set_free(seen);
}

References assignment_statement_p(), binary_call_lhs, binary_call_rhs, call_arguments, call_function, CAR, CONFLICT, conflict_sink, conflict_source, copy_reference(), dg, dg_arc_label_conflicts, effect_any_reference, effect_read_p, effect_write_p, EXPRESSION, expression_call(), expression_call_p(), expression_reference(), expression_reference_p(), expression_scalar_p, expression_syntax, FOREACH, free_expression(), free_reference(), gen_length(), graph_vertices, load_proper_reductions(), pips_user_warning, REDUCTION, reduction_op, reduction_operator_entity(), reduction_reference, reductions_list, reference_equal_p(), reference_scalar_p(), reference_to_expression(), reference_undefined, reference_variable, replace_entity_by_expression(), replace_reference(), same_entity_p(), seen, set_add_element(), set_belong_p(), set_free(), set_make(), set_pointer, statement_call(), SUCCESSOR, successor_arc_label, successor_vertex, syntax_reference, VERTEX, vertex_successors, and vertex_to_statement().

Referenced by reduction_propagation().

Here is the call graph for this function:

Here is the caller graph for this function:

guess_potential_reduction()

static reference guess_potential_reduction ( successor  su, conflict *  relevant  )

static

this looks like a potential reduction to me

Definition at line 154 of file propagation.c.

                                                                             {
  reference out = reference_undefined;
  FOREACH(CONFLICT,c,dg_arc_label_conflicts(successor_arc_label(su))) {
    /* this looks like a potential reduction to me */
    if( !anywhere_effect_p(conflict_source(c)) && !anywhere_effect_p(conflict_sink(c)) &&
        effect_read_p(conflict_source(c))&&effect_write_p(conflict_sink(c))) {
      out = effect_any_reference(conflict_source(c));
      if ( reference_scalar_p(out) ) {
          pips_debug(1,"potential reduction: %s\n",entity_user_name(reference_variable(out)));
          *relevant=c;
          break;
      }
      else out = reference_undefined;
    }
  }
  return out;
}

References anywhere_effect_p(), CONFLICT, conflict_sink, conflict_source, dg_arc_label_conflicts, effect_any_reference, effect_read_p, effect_write_p, entity_user_name(), FOREACH, out, pips_debug, reference_scalar_p(), reference_undefined, reference_variable, and successor_arc_label.

Referenced by do_reduction_detection().

Here is the call graph for this function:

Here is the caller graph for this function:

potential_reduction_substitution_valid_p()

static bool potential_reduction_substitution_valid_p ( list  sus, conflict  legal_conflict, reference  ref  )

static

Parameters

sus	f successors

Definition at line 172 of file propagation.c.

                                                                                                       {
    FOREACH(SUCCESSOR,su,sus) {
        FOREACH(CONFLICT,c,dg_arc_label_conflicts(successor_arc_label(su))) {
            if( c!=legal_conflict && (reference_equal_p(ref,effect_any_reference(conflict_sink(c))) || reference_equal_p(ref,effect_any_reference(conflict_source(c))))
              ) {
                return false;
            }
        }
    }
    return true;
}

References CONFLICT, conflict_sink, conflict_source, dg_arc_label_conflicts, effect_any_reference, FOREACH, ref, reference_equal_p(), SUCCESSOR, and successor_arc_label.

Referenced by do_reduction_detection().

Here is the call graph for this function:

Here is the caller graph for this function:

reduction_detection()

bool reduction_detection

(

const char *

mod_name

)

get the resources

do the job

validate computation

update/release resources

Parameters

mod_name

od_name

Definition at line 245 of file propagation.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);
    graph dependence_graph = 
        (graph) db_get_memory_resource(DBR_DG, mod_name, true);
 
    /* do the job */
    debug_on("REDUCTION_DETECTION_DEBUG_LEVEL");
    bool res = do_reduction_detection(dependence_graph);
    debug_off();
    if(res) {
        /* validate computation */
        module_reorder(mod_stmt);
        DB_PUT_MEMORY_RESOURCE(DBR_CODE, mod_name, mod_stmt);
    }
 
    /* update/release resources */
        reset_ordering_to_statement();
    reset_current_module_statement();
    reset_current_module_entity();
    return res;
}

References db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, dependence_graph, do_reduction_detection(), module_name_to_entity(), module_reorder(), reset_current_module_entity(), reset_current_module_statement(), reset_ordering_to_statement(), set_current_module_entity(), set_current_module_statement(), and set_ordering_to_statement().

Here is the call graph for this function:

reduction_propagation()

bool reduction_propagation

(

const char *

mod_name

)

now try to backward propagate the reduction, if it is meaningful.

propagation.c

the pattern checked is a = b + c; r = r + a; which should become r = r +b ; r = r +c ;

get the resources

do the job

validate computation

update/release resources

Parameters

mod_name

od_name

Definition at line 125 of file propagation.c.

                                                  {
    /* get the resources */
    statement mod_stmt = (statement)
        db_get_memory_resource(DBR_CODE, mod_name, true);
 
    set_current_module_statement(mod_stmt); 
    set_proper_reductions((pstatement_reductions) db_get_memory_resource(DBR_PROPER_REDUCTIONS, mod_name, true));
    set_current_module_entity(module_name_to_entity(mod_name));
        set_ordering_to_statement(mod_stmt);
    graph dependence_graph = 
        (graph) db_get_memory_resource(DBR_DG, mod_name, true);
 
    simplify_c_operator(get_current_module_statement());
 
    /* do the job */
    do_reduction_propagation(dependence_graph);
 
    /* validate computation */
    module_reorder(mod_stmt);
    DB_PUT_MEMORY_RESOURCE(DBR_CODE, mod_name, mod_stmt);
 
    /* update/release resources */
    reset_proper_reductions();
        reset_ordering_to_statement();
    reset_current_module_statement();
    reset_current_module_entity();
    return true;
}

References db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, dependence_graph, do_reduction_propagation(), get_current_module_statement(), module_name_to_entity(), module_reorder(), reset_current_module_entity(), reset_current_module_statement(), reset_ordering_to_statement(), reset_proper_reductions(), set_current_module_entity(), set_current_module_statement(), set_ordering_to_statement(), set_proper_reductions(), and simplify_c_operator().

Here is the call graph for this function: