forward_substitution.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "dg.h"
#include "graph.h"
#include "ri-util.h"
#include "prettyprint.h"
#include "effects-util.h"
#include "text-util.h"
#include "database.h"
#include "misc.h"
#include "pipsdbm.h"
#include "resources.h"
#include "effects-generic.h"
#include "effects-simple.h"
#include "properties.h"
#include "expressions-local.h"
#include "expressions.h"
#include "ricedg.h"

Include dependency graph for forward_substitution.c:

Go to the source code of this file.

Data Structures
struct	t_substitution
	structure to hold a substitution to be performed forward. More...
struct	s_p_s

Typedefs
typedef dg_arc_label	arc_label
typedef dg_vertex_label	vertex_label
typedef struct t_substitution *	p_substitution

Functions
static p_substitution	make_substitution (statement source, reference ref, expression val)
	newgen-looking make/free More...
static void	free_substitution (p_substitution subs)
static bool	no_write_effects_on_var (entity var, list le)
static bool	functionnal_on_effects (reference ref, list le)
static bool	functionnal_on (reference ref, statement s)
	returns whether there is other write proper effect than on var or if some variable conflicting with var is read... More...
static p_substitution	substitution_candidate (statement s, bool only_scalar)
	Whether it is a candidate of a substitution operation. More...
static bool	cool_enough_for_a_last_substitution (statement s)
	x = a(i) ; a(j) = x ; More...
static bool	other_cool_enough_for_a_last_substitution (statement s, reference ref)
	s = r ; s = s + w ; // read THEN write... More...
static void	perform_substitution_in_expression (expression e, p_substitution subs)
	do perform the substitution var -> val everywhere in s More...
static bool	call_flt (call c, p_substitution subs)
static void	perform_substitution (p_substitution subs, void *s)
static void	perform_substitution_in_assign (p_substitution subs, statement s)
static bool	some_conflicts_between (hash_table successors, statement s1, statement s2, p_substitution sub)
	whether there are some conflicts between s1 and s2 according to successor table successors More...
static bool	do_substitute (statement anext, struct s_p_s *param)
static bool	fs_filter (statement stat, graph dg)
	top-down forward substitution of reference in SEQUENCE only. More...
bool	forward_substitute (const char *module_name)
	interface to pipsmake. More...

Typedef Documentation

arc_label

typedef dg_arc_label arc_label

Definition at line 60 of file forward_substitution.c.

p_substitution

typedef struct t_substitution * p_substitution

vertex_label

typedef dg_vertex_label vertex_label

Definition at line 61 of file forward_substitution.c.

Function Documentation

call_flt()

static bool call_flt ( call  c, p_substitution  subs  )

static

Definition at line 302 of file forward_substitution.c.

{
    entity op = call_function(c);
    if(same_entity_p(op, entity_intrinsic(ASSIGN_OPERATOR_NAME))||
            !entity_undefined_p(update_operator_to_regular_operator(op)))
    {
        expression lhs = binary_call_lhs(c);
        if(expression_reference_p(lhs) && reference_equal_p(expression_reference(lhs),subs->ref))
            gen_recurse_stop(lhs);
    }
    return true;
}

References ASSIGN_OPERATOR_NAME, binary_call_lhs, call_function, entity_intrinsic(), entity_undefined_p, expression_reference(), expression_reference_p(), gen_recurse_stop(), t_substitution::ref, reference_equal_p(), same_entity_p(), and update_operator_to_regular_operator().

Referenced by perform_substitution().

Here is the call graph for this function:

Here is the caller graph for this function:

cool_enough_for_a_last_substitution()

static bool cool_enough_for_a_last_substitution ( statement  s )

static

x = a(i) ; a(j) = x ;

we can substitute x but it cannot be continued. just a hack for this very case at the time. maybe englobing parallel loops or dependence information could be use for a better decision? I'll think about it on request only.

Definition at line 220 of file forward_substitution.c.

{
    p_substitution x = substitution_candidate(s, false);
    bool ok = (x!=NULL);
    free_substitution(x);
    return ok;
}

References free_substitution(), ok, substitution_candidate(), and x.

Referenced by do_substitute().

Here is the call graph for this function:

Here is the caller graph for this function:

do_substitute()

static bool do_substitute ( statement  anext, struct s_p_s *  param  )

static

for some special case the substitution is performed. in some cases effects should be updated?

now STOP propagation!

Definition at line 389 of file forward_substitution.c.

{
    if(!statement_block_p(anext))
    {
        ifdebug(1) {
            pips_debug(1, "with statement:\n");
            print_statement(anext);
        }
        if (some_conflicts_between(param->successors,param->subs->source, anext, param->subs))
        {
            /* for some special case the substitution is performed.
             * in some cases effects should be updated?
             */
          if (cool_enough_for_a_last_substitution(anext))// &&
            // !some_conflicts_between(param->successors,param->subs->source, anext, param->subs))
                perform_substitution(param->subs, anext);
            else
                if (other_cool_enough_for_a_last_substitution(anext, param->subs->ref))
                    perform_substitution_in_assign(param->subs, anext);
            param->stop=true;
 
            /* now STOP propagation!
            */
            gen_recurse_stop(NULL);
        }
        else
            perform_substitution(param->subs, anext);
    }   
    return true;
}

References cool_enough_for_a_last_substitution(), gen_recurse_stop(), ifdebug, other_cool_enough_for_a_last_substitution(), perform_substitution(), perform_substitution_in_assign(), pips_debug, print_statement(), some_conflicts_between(), and statement_block_p.

Referenced by fs_filter().

Here is the call graph for this function:

Here is the caller graph for this function:

forward_substitute()

bool forward_substitute

(

const char *

module_name

)

interface to pipsmake.

forward_substitution.c

should have proper and cumulated effects...

set require resources.

do the job here:

return result and clean.

Parameters

module_name

odule_name

Definition at line 470 of file forward_substitution.c.

{
    debug_on("FORWARD_SUBSTITUTE_DEBUG_LEVEL");
 
    /* set require resources.
     */
    set_current_module_entity(local_name_to_top_level_entity(module_name));
    set_current_module_statement((statement)db_get_memory_resource(DBR_CODE, module_name, true));
    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));
        set_ordering_to_statement(get_current_module_statement());
    graph dg = (graph) db_get_memory_resource(DBR_DG, module_name, true);
 
    /* do the job here:
     */
    gen_context_recurse(get_current_module_statement(), dg,statement_domain, fs_filter, gen_null2);
 
    /* return result and clean.
     */
    DB_PUT_MEMORY_RESOURCE(DBR_CODE, module_name, get_current_module_statement());
 
    reset_cumulated_rw_effects();
    reset_proper_rw_effects();
    reset_current_module_entity();
    reset_current_module_statement();
    reset_ordering_to_statement();
 
    debug_off();
 
    return true;
}

References db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, dg, fs_filter(), gen_context_recurse, gen_null2(), get_current_module_statement(), local_name_to_top_level_entity(), module_name(), reset_cumulated_rw_effects(), reset_current_module_entity(), reset_current_module_statement(), reset_ordering_to_statement(), reset_proper_rw_effects(), set_cumulated_rw_effects(), set_current_module_entity(), set_current_module_statement(), set_ordering_to_statement(), set_proper_rw_effects(), and statement_domain.

Here is the call graph for this function:

free_substitution()

static void free_substitution ( p_substitution  subs )

static

Definition at line 126 of file forward_substitution.c.

{
  if (subs) {
    free_expression(subs->val);
    free(subs);
  }
}

References free(), free_expression(), and t_substitution::val.

Referenced by cool_enough_for_a_last_substitution(), and fs_filter().

Here is the call graph for this function:

Here is the caller graph for this function:

fs_filter()

static bool fs_filter ( statement  stat, graph  dg  )

static

top-down forward substitution of reference in SEQUENCE only.

scan following statements and substitute while no conflicts.

Definition at line 423 of file forward_substitution.c.

{
    if(statement_block_p(stat))
    {
        ifdebug(1) {
            pips_debug(1, "considering block statement:\n");
            print_statement(stat);
        }
        hash_table successors = statements_to_successors(statement_block(stat),dg);
        for(list ls = statement_block(stat);!ENDP(ls);POP(ls)) 
        {
            statement first = STATEMENT(CAR(ls));
            if(assignment_statement_p(first))
            {
                ifdebug(1) {
                    pips_debug(1, "considering assignment statement:\n");
                    print_statement(first);
                }
                p_substitution subs = substitution_candidate(first, true);
                if (subs)
                {
                    /* scan following statements and substitute while no conflicts.
                    */
                    struct s_p_s param = { subs, successors,false};
                    bool once = false;
                    FOREACH(STATEMENT,next,CDR(ls))
                    {
                        param.stop=false;
                        gen_context_recurse(next, &param, statement_domain, do_substitute, gen_null2);
                        if(param.stop) break;
                        else once=true;
                    }
 
                    free_substitution(subs);
                    if(once && get_bool_property("FORWARD_SUBSTITUTE_OPTIMISTIC_CLEAN"))
                        update_statement_instruction(first,make_instruction_block(NIL));
                }
            }
        }
        hash_table_free(successors);
    }
    return true;
}

References assignment_statement_p(), CAR, CDR, dg, do_substitute(), ENDP, FOREACH, free_substitution(), gen_context_recurse, gen_null2(), get_bool_property(), hash_table_free(), ifdebug, make_instruction_block(), NIL, pips_debug, POP, print_statement(), STATEMENT, statement_block(), statement_block_p, statement_domain, statements_to_successors(), s_p_s::subs, substitution_candidate(), successors(), and update_statement_instruction().

Referenced by forward_substitute().

Here is the call graph for this function:

Here is the caller graph for this function:

functionnal_on()

static bool functionnal_on ( reference  ref, statement  s  )

static

returns whether there is other write proper effect than on var or if some variable conflicting with var is read...

(?) proper_effects must be available.

Definition at line 158 of file forward_substitution.c.

{
  effects efs = load_proper_rw_effects(s);
 
  ifdebug(1) {
    pips_assert("efs is consistent", effects_consistent_p(efs));
  }
 
  return functionnal_on_effects(ref, effects_effects(efs));
}

References effects_consistent_p(), effects_effects, functionnal_on_effects(), ifdebug, load_proper_rw_effects(), pips_assert, and ref.

Referenced by substitution_candidate().

Here is the call graph for this function:

Here is the caller graph for this function:

functionnal_on_effects()

static bool functionnal_on_effects ( reference  ref, list  le  )

static

Parameters

le

of effect

Definition at line 143 of file forward_substitution.c.

{
    FOREACH(EFFECT, e, le) {
      if(action_kind_store_p(effect_action_kind(e)))
        if ((effect_write_p(e) && effect_variable(e)!=reference_variable(ref)) ||
                (effect_read_p(e) && entities_may_conflict_p(effect_variable(e), reference_variable(ref))))
            return false;
    }
  return true;  
}

References action_kind_store_p, EFFECT, effect_action_kind(), effect_read_p, effect_variable, effect_write_p, entities_may_conflict_p(), FOREACH, ref, and reference_variable.

Referenced by functionnal_on().

Here is the call graph for this function:

Here is the caller graph for this function:

make_substitution()

static p_substitution make_substitution ( statement  source, reference  ref, expression  val  )

static

newgen-looking make/free

Definition at line 96 of file forward_substitution.c.

{
    p_substitution subs;
    basic bval = basic_of_expression(val),
          bref = basic_of_reference(ref);
 
    pips_assert("defined basics", !(basic_undefined_p(bval) || basic_undefined_p(bref)));
 
    subs = (p_substitution) malloc(sizeof(t_substitution));
    pips_assert("malloc ok", subs);
    subs->source = source;
    subs->ref = ref;
    if (basic_equal_p(bval, bref))
        subs->val = copy_expression(val);
    else
    {
        entity conv = basic_to_generic_conversion(bref);
        if (entity_undefined_p(conv))
        {
            pips_user_warning("no conversion function...");
            free(subs); 
            return NULL;
        }
        subs->val = MakeUnaryCall(conv,copy_expression(val));
    }
    free_basic(bval);
    return subs;
}

References basic_equal_p(), basic_of_expression(), basic_of_reference(), basic_to_generic_conversion(), basic_undefined_p, copy_expression(), entity_undefined_p, free(), free_basic(), MakeUnaryCall(), malloc(), pips_assert, pips_user_warning, t_substitution::ref, ref, t_substitution::source, and t_substitution::val.

Referenced by substitution_candidate().

Here is the call graph for this function:

Here is the caller graph for this function:

no_write_effects_on_var()

static bool no_write_effects_on_var ( entity  var, list  le  )

static

Definition at line 134 of file forward_substitution.c.

{
    FOREACH(EFFECT, e, le)
      if (effect_write_p(e) && entities_may_conflict_p(effect_variable(e), var) 
          && action_kind_store_p(effect_action_kind(e)))
            return false;
    return true;  
}

References action_kind_store_p, EFFECT, effect_action_kind(), effect_variable, effect_write_p, entities_may_conflict_p(), and FOREACH.

Referenced by other_cool_enough_for_a_last_substitution().

Here is the call graph for this function:

Here is the caller graph for this function:

other_cool_enough_for_a_last_substitution()

static bool other_cool_enough_for_a_last_substitution ( statement  s, reference  ref  )

static

s = r ; s = s + w ; // read THEN write...

it is an assignment

Definition at line 231 of file forward_substitution.c.

{
  instruction i = statement_instruction(s);
  call c;
  list args;
  syntax svar;
  entity var;
  list le;
 
  if (!instruction_call_p(i)) 
    return false;
 
  c = instruction_call(i);
  if (!ENTITY_ASSIGN_P(call_function(c)))
    return false;
 
  /* it is an assignment */
  args = call_arguments(c);
  pips_assert("2 args to =", gen_length(args)==2);
  svar = expression_syntax(EXPRESSION(CAR(args)));
  pips_assert("assign to a reference", syntax_reference_p(svar));
  var = reference_variable(syntax_reference(svar));
  
  if (!entity_scalar_p(var)) return false;
  
  le = proper_effects_of_expression(EXPRESSION(CAR(CDR(args))));
  bool cool = no_write_effects_on_var(reference_variable(ref), le);
  gen_full_free_list(le);
 
  return cool;
}

References call_arguments, call_function, CAR, CDR, ENTITY_ASSIGN_P, entity_scalar_p(), EXPRESSION, expression_syntax, gen_full_free_list(), gen_length(), instruction_call, instruction_call_p, no_write_effects_on_var(), pips_assert, proper_effects_of_expression(), ref, reference_variable, statement_instruction, syntax_reference, and syntax_reference_p.

Referenced by do_substitute().

Here is the call graph for this function:

Here is the caller graph for this function:

perform_substitution()

static void perform_substitution ( p_substitution  subs, void *  s  )

static

Parameters

s	substitution to perform where to do this

Definition at line 316 of file forward_substitution.c.

{
    gen_context_multi_recurse(s, subs,
            expression_domain, gen_true, perform_substitution_in_expression,
            call_domain,call_flt,gen_null,
            NULL);
    unnormalize_expression(s);
}

References call_domain, call_flt(), expression_domain, gen_context_multi_recurse(), gen_null(), gen_true(), perform_substitution_in_expression(), and unnormalize_expression().

Referenced by do_substitute(), and perform_substitution_in_assign().

Here is the call graph for this function:

Here is the caller graph for this function:

perform_substitution_in_assign()

static void perform_substitution_in_assign ( p_substitution  subs, statement  s  )

static

special case

Definition at line 328 of file forward_substitution.c.

{
    /* special case */
    pips_assert("assign call", statement_call_p(s));
 
    call c = statement_call(s);
    perform_substitution(subs,binary_call_rhs(c));
    FOREACH(EXPRESSION, e, reference_indices(expression_reference(binary_call_lhs(c))))
        perform_substitution(subs, e);
}

References binary_call_lhs, binary_call_rhs, EXPRESSION, expression_reference(), FOREACH, perform_substitution(), pips_assert, reference_indices, statement_call(), and statement_call_p().

Referenced by do_substitute().

Here is the call graph for this function:

Here is the caller graph for this function:

perform_substitution_in_expression()

static void perform_substitution_in_expression ( expression  e, p_substitution  subs  )

static

do perform the substitution var -> val everywhere in s

FI->FC: the syntax may be freed but not always the reference it contains because it can also be used in effects. The bug showed on transformations/Validation/fs01.f, fs02.f, fs04.f. I do not know why the effects are still used after the statement has been updated (?). The bug can be avoided by closing and opening the workspace which generates independent references in statements and in effects. Is there a link with the notion of cell = reference+preference?

Definition at line 265 of file forward_substitution.c.

{
    syntax s = expression_syntax(e);
    if (syntax_reference_p(s)) {
 
        reference r = syntax_reference(s);
        if (reference_equal_p(r,subs->ref)) 
        {
            ifdebug(2) {
                pips_debug(2,"substituing %s to %s\n",
                           expression_to_string(subs->val),
                           reference_to_string(r));
            }
            /* FI->FC: the syntax may be freed but not always the reference it
               contains because it can also be used in effects. The bug showed on
               transformations/Validation/fs01.f, fs02.f, fs04.f. I do not know why the
               effects are still used after the statement has been updated (?). The bug
               can be avoided by closing and opening the workspace which generates
               independent references in statements and in effects. Is there a link with
               the notion of cell = reference+preference? */
            expression_syntax(e)=syntax_undefined;
            update_expression_syntax(e,copy_syntax(expression_syntax(subs->val)));
        }
        else
        {
            ifdebug(2) {
                pips_debug(2,"not substituting ");
                print_reference(subs->ref);
                fputs(" to ",stderr);
                print_reference(r);
                fputs("\n",stderr);
            }
        }
    }
}

References copy_syntax(), expression_syntax, expression_to_string(), ifdebug, pips_debug, print_reference(), t_substitution::ref, reference_equal_p(), reference_to_string(), syntax_reference, syntax_reference_p, syntax_undefined, update_expression_syntax(), and t_substitution::val.

Referenced by perform_substitution().

Here is the call graph for this function:

Here is the caller graph for this function:

some_conflicts_between()

static bool some_conflicts_between ( hash_table  successors, statement  s1, statement  s2, p_substitution  sub  )

static

whether there are some conflicts between s1 and s2 according to successor table successors

if there is a write-* conflict, we cannot do much

this case is safe

Definition at line 343 of file forward_substitution.c.

{
  pips_assert("true", sub==sub);
    pips_debug(2, "looking for conflict with statement\n");
    ifdebug(2) { print_statement(s2); }
    list s1_successors = hash_get(successors,s1);
    FOREACH(SUCCESSOR,s,s1_successors)
    {
        statement ss = vertex_to_statement(successor_vertex(s));
        pips_debug(2, "checking:\n");
        ifdebug(2) { print_statement(ss); }
        if(statement_in_statement_p(ss,s2))
        {
            FOREACH(CONFLICT,c,dg_arc_label_conflicts(successor_arc_label(s)))
            {
                /* if there is a write-* conflict, we cannot do much */
              if ( effect_write_p(conflict_sink(c)) &&
                   action_kind_store_p(effect_action_kind(conflict_sink(c))) )
                {
                    /* this case is safe */
                    if( ENDP(reference_indices(effect_any_reference(conflict_source(c)))) && 
                            !ENDP(reference_indices(effect_any_reference(conflict_sink(c)))))
                        continue;
                    ifdebug(2) {
                        pips_debug(2, "conflict found on reference, with") ;
                        print_reference(effect_any_reference(conflict_sink(c)));
                        print_reference(effect_any_reference(conflict_source(c)));
                        fputs("\n",stderr) ;
                    }
                    return true;
                }
            }
        }
    }
 
    pips_debug(2, "no conflict\n");
    return false;
}

References action_kind_store_p, CONFLICT, conflict_sink, conflict_source, dg_arc_label_conflicts, effect_action_kind(), effect_any_reference, effect_write_p, ENDP, FOREACH, hash_get(), ifdebug, pips_assert, pips_debug, print_reference(), print_statement(), reference_indices, s1, statement_in_statement_p(), SUCCESSOR, successor_arc_label, successor_vertex, successors(), and vertex_to_statement().

Referenced by do_substitute().

Here is the call graph for this function:

Here is the caller graph for this function:

substitution_candidate()

static p_substitution substitution_candidate ( statement  s, bool  only_scalar  )

static

Whether it is a candidate of a substitution operation.

that is: (1) it is a call (2) it is an assignment call (3) the assigned variable is a scalar (sg: no longer true !) (4) there are no side effects in the expression

Note: a substitution candidate might be one after substitutions... but not before? So effects should be recomputed? or updated? eg: x = 1; x = x + 1;

of expression

CALL

ASSIGN

NO SIDE EFFECTS

Definition at line 179 of file forward_substitution.c.

{
  pips_assert("true", only_scalar==only_scalar);
  list /* of expression */ args;
  call c;
  entity fun;
  syntax svar;
  instruction i = statement_instruction(s);
  
  if (!instruction_call_p(i)) return NULL; /* CALL */
  
  c = instruction_call(i);
  fun = call_function(c);
  
  if (!ENTITY_ASSIGN_P(fun)) return NULL; /* ASSIGN */
  
  
  args = call_arguments(c);
  pips_assert("2 args to =", gen_length(args)==2);
  svar = expression_syntax(EXPRESSION(CAR(args)));
 
  if(!syntax_reference_p(svar)) // What about subscripts ?
    return NULL;
 
  reference ref = syntax_reference(svar);
  
  //if (only_scalar && ENDP(reference_indices(ref))) return NULL; /* SCALAR */
  
  if (!functionnal_on(ref, s)) return NULL; /* NO SIDE EFFECTS */
  
  return make_substitution(s, ref, EXPRESSION(CAR(CDR(args))));
}

References call_arguments, call_function, CAR, CDR, ENTITY_ASSIGN_P, EXPRESSION, expression_syntax, functionnal_on(), gen_length(), instruction_call, instruction_call_p, make_substitution(), pips_assert, ref, statement_instruction, syntax_reference, and syntax_reference_p.

Referenced by cool_enough_for_a_last_substitution(), and fs_filter().

Here is the call graph for this function:

Here is the caller graph for this function: