o-analysis.c File Reference

#include "defines-local.h"
#include "prettyprint.h"
#include "access_description.h"
#include "effects-generic.h"

Include dependency graph for o-analysis.c:

Go to the source code of this file.

Macros
#define	RETURN(x)
	must clear everything before returning in Overlap_Analysis... More...

Functions
bool	block_distributed_p (entity array)
	true if there is no cyclic distribution for the array More...
static bool	simple_indices_p (reference r)
	true if indices are constants or index More...
static bool	aligned_p (reference r1, reference r2, list lvref, list lkref)
	true if references are aligned or, for constants, on the same processor... More...
static bool	on_same_proc_p (int t1, int t2, entity template, int dim)
	true if the given template elements on the specified dimension are mapped on the same processor. More...
static bool	message_manageable_p (entity array, list lpref, list lkref)
	every thing should be manageable, i.e. More...
static statement	statement_compute_bounds (entity newlobnd, entity newupbnd, entity oldidxvl, expression lb, expression ub, int an, int dp)
	generate the call to the dynamic loop bounds computation More...
static void	hpfc_overlap_kill_unused_scalars_rewrite (statement stat)
static bool	hpfc_overlap_kill_unused_scalars (statement stat)
	true if one statement was killed More...
static int	which_array_dimension (reference r, entity e)
	returns the dimension of reference on which index entity e is used More...
static loop	make_loop_skeleton (entity newindex, expression lower_expression, expression upper_expression)
static void	update_indices_for_local_computation (entity_mapping new_indexes, list Ref, list lRef)
static statement	make_increment_statement (entity index)
static void	variable_used_rewrite (reference r)
static void	initialize_variable_used_map_for_current_loop_nest (statement inner_body)
static void	close_variable_used_map_for_statement ()
static bool	variable_used_in_statement_p (entity ent, statement stat)
static int	number_of_distributed_dimensions (entity a)
static syntax	choose_one_syntax_in_references_list (list *pls)
	one of the syntax is chosen from the list. More...
static statement	make_loop_nest_for_overlap (list lold, list lnew, list lbl, entity_mapping new_indexes, entity_mapping old_indexes, statement innerbody)
static bool	generate_optimized_code_for_loop_nest (statement innerbody, statement *pstat, syntax the_computer_syntax, list Wa, list Ra, list Ro, list lWa, list lRa, list lRo)
bool	Overlap_Analysis (statement stat, statement *pstat)
	check conditions and compile... More...

Variables
static list	lblocks = NIL
	Overlap Analysis Module for HPFC. More...
static list	lloop = NIL
static bool	hpfc_killed_scalar
	To Kill scalar definitions within the generated code recognize if only one reference. More...
static statement	current_variable_used_statement = statement_undefined
	bool variable_used_in_statement_p(ent, stat) More...

Macro Definition Documentation

RETURN

#define RETURN

(

x

)

Value:

{ pips_debug(9, "returning %d from line %d\n", x, __LINE__);\
  gen_free_list(Wa); gen_free_list(lWa); gen_free_list(Ra);\
  gen_free_list(lRa); gen_free_list(Ro); gen_free_list(lRo);\
  gen_free_list(Rrt); gen_free_list(lblocks); gen_free_list(lloop);\
  gen_free_list(W); gen_free_list(R); gen_free_list(lw); gen_free_list(lr);\
  reset_hpfc_current_statement(); reset_current_loops(); return x;}

must clear everything before returning in Overlap_Analysis...

Definition at line 860 of file o-analysis.c.

Function Documentation

aligned_p()

static bool aligned_p ( reference  r1, reference  r2, list  lvref, list  lkref  )

static

true if references are aligned or, for constants, on the same processor...

Definition at line 144 of file o-analysis.c.

{
    entity e2 = reference_variable(r2), template = array_to_template(e2);
    list lv = lvref, lk = lkref;
    bool result = true;
    int i = 1 ;
 
    pips_debug(7, "arrays %s and %s\n",
               entity_name(reference_variable(r1)), entity_name(e2));
 
    for ( ; (lk!=NIL) ; POP(lv), POP(lk))
    {
        tag t = access_tag(INT(CAR(lk)));
        Pvecteur v = (Pvecteur) PVECTOR(CAR(lv));
        Value vt = vect_coeff(TEMPLATEV, v),
              vd = vect_coeff(DELTAV, v),
              vs = vect_coeff(TSHIFTV, v);
        int p,
            tpldim = template_dimension_of_array_dimension(e2, i),
            tpl = VALUE_TO_INT(vt),
            dlt = VALUE_TO_INT(vd),
            tsh = VALUE_TO_INT(vs);
 
        if ((t==not_aligned) ||
            ((t==aligned_constant) && 
             (processor_number(template, tpldim, tpl, &p)!=
              processor_number(template, tpldim, tpl-dlt, &p))) ||
            ((t==aligned_shift) && (tsh!=0)))
            return false;
 
        i++;
    }
    
    return result;
}

References access_tag, aligned_constant, aligned_shift, array_to_template, CAR, DELTAV, entity_name, INT, NIL, not_aligned, pips_debug, POP, processor_number(), PVECTOR, reference_variable, template_dimension_of_array_dimension(), TEMPLATEV, TSHIFTV, VALUE_TO_INT, and vect_coeff().

Referenced by Overlap_Analysis().

Here is the call graph for this function:

Here is the caller graph for this function:

block_distributed_p()

bool block_distributed_p

(

entity

array

)

true if there is no cyclic distribution for the array

o-analysis.c

distributed && (nd==is_hpf_newdecl_none)) ? ??? the case is not handled later on

Parameters

array

rray

Definition at line 44 of file o-analysis.c.

{
    int dim = NumberOfDimension(array);
    tag n;
 
    for(; dim>0; dim--)
    {
        n = new_declaration_tag(array, dim);
        if ((n==is_hpf_newdecl_gamma) || (n==is_hpf_newdecl_delta))
            /* distributed && (nd==is_hpf_newdecl_none)) ?
             * ??? the case is not handled later on 
             */
            return(false);
    }
 
    return(true);
}

References array, is_hpf_newdecl_delta, is_hpf_newdecl_gamma, new_declaration_tag(), and NumberOfDimension().

Referenced by message_manageable_p(), Overlap_Analysis(), and subarray_shift_assignment_p().

Here is the call graph for this function:

Here is the caller graph for this function:

choose_one_syntax_in_references_list()

static syntax choose_one_syntax_in_references_list ( list *  pls )

static

one of the syntax is chosen from the list.

The "larger one". and the list is given back, the chosen syntax as first element.

Definition at line 601 of file o-analysis.c.

{
    list cls = *pls, nls = NIL;
    syntax chosen = SYNTAX(CAR(cls));
    int chosen_distribution = 
            number_of_distributed_dimensions
                (reference_variable(syntax_reference(chosen)));
 
    MAP(SYNTAX, current,
    {
        int current_distribution = 
                number_of_distributed_dimensions
                    (reference_variable(syntax_reference(current)));
 
         if (current_distribution > chosen_distribution)
         {
             nls = CONS(SYNTAX, chosen, nls);
             chosen = current;
             chosen_distribution = current_distribution;
         }
         else
             nls = CONS(SYNTAX, current, nls);
     },
         CDR(cls));
         
    gen_free_list(cls);
    *pls = CONS(SYNTAX, chosen, nls);
 
    debug(7, "choose_one_syntax_in_references_list",
          "reference to %s chosen, %d dimensions\n",
          entity_name(reference_variable(syntax_reference(chosen))),
          chosen_distribution);
 
    return(chosen);
}

References CAR, CDR, CONS, current, debug(), entity_name, gen_free_list(), MAP, NIL, number_of_distributed_dimensions(), reference_variable, SYNTAX, and syntax_reference.

Referenced by Overlap_Analysis().

Here is the call graph for this function:

Here is the caller graph for this function:

close_variable_used_map_for_statement()

static void close_variable_used_map_for_statement ( )

static

Definition at line 573 of file o-analysis.c.

{
    close_entity_variable_used();
    current_variable_used_statement = statement_undefined;
}

References current_variable_used_statement, and statement_undefined.

Referenced by generate_optimized_code_for_loop_nest().

Here is the caller graph for this function:

generate_optimized_code_for_loop_nest()

static bool generate_optimized_code_for_loop_nest ( statement  innerbody, statement *  pstat, syntax  the_computer_syntax, list  Wa, list  Ra, list  Ro, list  lWa, list  lRa, list  lRo  )

static

new bounds to compute, and so on

constant new loop bounds are computed on entry in the subroutine.

??? there is a core dump on the second free, when executed, in test 37~; free_execution(loop_execution(l)); free_loop(l);

and now generates the code...

Definition at line 739 of file o-analysis.c.

{
    reference the_computer_reference = syntax_reference(the_computer_syntax);
    entity array = reference_variable(the_computer_reference);
    int an = load_hpf_number(array);
    entity_mapping
        new_indexes = MAKE_ENTITY_MAPPING(),
        old_indexes = MAKE_ENTITY_MAPPING();
    list boundcomp = NIL, newloops = NIL;
    statement newnest = NULL;
    range rg;
    expression lb, ub;
    entity index, newindex, newlobnd, newupbnd, oldidxvl;
    loop nl;
    int p, dim;
 
    MAP(LOOP, l,
     {
         index = loop_index(l);
         dim = which_array_dimension(the_computer_reference, index);
 
         if (ith_dim_distributed_p(array, dim, &p))
         {
             statement bc;
 
             /* new bounds to compute, and so on */
             rg = loop_range(l);
             lb = copy_expression(range_lower(rg));
             ub = copy_expression(range_upper(rg));
             
             newindex = make_new_scalar_variable(node_module, 
                                             MakeBasic(is_basic_int));
             newlobnd = make_new_scalar_variable(node_module, 
                                             MakeBasic(is_basic_int));
             newupbnd = make_new_scalar_variable(node_module, 
                                             MakeBasic(is_basic_int));
             oldidxvl = make_new_scalar_variable(node_module, 
                                             MakeBasic(is_basic_int));
         AddEntityToCurrentModule(newindex);
         AddEntityToCurrentModule(newlobnd);
         AddEntityToCurrentModule(newupbnd);
         AddEntityToCurrentModule(oldidxvl);
 
             bc = statement_compute_bounds
                 (newlobnd, newupbnd, oldidxvl, lb, ub, an, p);
 
             /* constant new loop bounds are computed on entry
              * in the subroutine.
              */
             if (expression_integer_constant_p(lb) && 
                 expression_integer_constant_p(ub))
                 hpfc_add_ahead_of_node_code(bc);
             else
                 boundcomp = gen_nconc(boundcomp, CONS(STATEMENT, bc, NIL));
 
             newloops = 
                 gen_nconc(newloops,
                   CONS(LOOP,
                        make_loop_skeleton(newindex, 
                                           entity_to_expression(newlobnd),
                                           entity_to_expression(newupbnd)),
                        NIL));
 
             SET_ENTITY_MAPPING(new_indexes, index, newindex);
             SET_ENTITY_MAPPING(old_indexes, index, oldidxvl);
         }
         else
         {
             nl = make_loop(loop_index(l),
                            loop_range(l),
                            statement_undefined,
                            loop_label(l),
                            make_execution(is_execution_sequential, UU),
                            NIL);
/* ??? there is a core dump on the second free, when executed, in test 37~;
             free_execution(loop_execution(l));
             free_loop(l);
*/
             newloops = gen_nconc(newloops, CONS(LOOP, nl, NIL));
         }
     },
         lloop);
 
    update_indices_for_local_computation(new_indexes, Wa, lWa);
    update_indices_for_local_computation(new_indexes, Ra, lRa);
    update_indices_for_local_computation(new_indexes, Ro, lRo);
    
    /* and now generates the code...
     */
    initialize_variable_used_map_for_current_loop_nest(innerbody);
 
    if (hpfc_overlap_kill_unused_scalars(innerbody))
    {
        close_variable_used_map_for_statement();
        initialize_variable_used_map_for_current_loop_nest(innerbody);
    }
 
    newnest = make_loop_nest_for_overlap(lloop, newloops, lblocks,
                                         new_indexes, old_indexes, 
                                         innerbody);
    close_variable_used_map_for_statement();
 
    
    (*pstat) = make_block_statement(gen_nconc(boundcomp,
                                              CONS(STATEMENT, newnest,
                                                   NIL)));
 
    return(true);
}

References AddEntityToCurrentModule(), array, close_variable_used_map_for_statement(), CONS, copy_expression(), entity_to_expression(), expression_integer_constant_p(), gen_nconc(), hpfc_add_ahead_of_node_code(), hpfc_overlap_kill_unused_scalars(), initialize_variable_used_map_for_current_loop_nest(), is_basic_int, is_execution_sequential, ith_dim_distributed_p(), lblocks, lloop, load_hpf_number(), LOOP, loop_index, loop_label, loop_range, make_block_statement(), MAKE_ENTITY_MAPPING, make_execution(), make_loop(), make_loop_nest_for_overlap(), make_loop_skeleton(), make_new_scalar_variable(), MakeBasic(), MAP, NIL, node_module, range_lower, range_upper, reference_variable, SET_ENTITY_MAPPING, STATEMENT, statement_compute_bounds(), statement_undefined, syntax_reference, update_indices_for_local_computation(), UU, and which_array_dimension().

Referenced by Overlap_Analysis().

Here is the call graph for this function:

Here is the caller graph for this function:

hpfc_overlap_kill_unused_scalars()

static bool hpfc_overlap_kill_unused_scalars ( statement  stat )

static

true if one statement was killed

Definition at line 350 of file o-analysis.c.

{
    message_assert("defined", !entity_variable_used_undefined_p());
 
    hpfc_killed_scalar = false;
 
    gen_recurse(stat, statement_domain, gen_true,
                hpfc_overlap_kill_unused_scalars_rewrite);
 
    return(hpfc_killed_scalar);
}

References gen_recurse, gen_true(), hpfc_killed_scalar, hpfc_overlap_kill_unused_scalars_rewrite(), message_assert, and statement_domain.

Referenced by generate_optimized_code_for_loop_nest().

Here is the call graph for this function:

Here is the caller graph for this function:

hpfc_overlap_kill_unused_scalars_rewrite()

static void hpfc_overlap_kill_unused_scalars_rewrite ( statement  stat )

static

??? memory leak

Definition at line 313 of file o-analysis.c.

{
    instruction
        i = statement_instruction(stat);
    expression
        e = expression_undefined;
    entity
        var = entity_undefined;
 
    if (!instruction_assign_p(i)) return;
 
    e = EXPRESSION(CAR(call_arguments(instruction_call(i))));
 
    assert(expression_reference_p(e));
 
    var = reference_variable(syntax_reference(expression_syntax(e)));
 
    debug(5, "hpfc_overlap_kill_unused_scalars_rewrite",
          "considering definition of %s (statement 0x%x)\n",
          entity_name(var), stat);
 
    if (entity_integer_scalar_p(var) &&
        load_entity_variable_used(var)==1)
    {
        debug(3, "hpfc_overlap_kill_unused_scalars_rewrite",
              "killing definition of %s (statement 0x%x)\n",
              entity_name(var), stat);
 
        hpfc_killed_scalar = true;
        statement_instruction(stat) =  /* ??? memory leak */
            make_continue_instruction();
    }
}

References assert, call_arguments, CAR, debug(), entity_integer_scalar_p(), entity_name, entity_undefined, EXPRESSION, expression_reference_p(), expression_syntax, expression_undefined, hpfc_killed_scalar, instruction_assign_p(), instruction_call, make_continue_instruction(), reference_variable, statement_instruction, and syntax_reference.

Referenced by hpfc_overlap_kill_unused_scalars().

Here is the call graph for this function:

Here is the caller graph for this function:

initialize_variable_used_map_for_current_loop_nest()

static void initialize_variable_used_map_for_current_loop_nest ( statement  inner_body )

static

Definition at line 542 of file o-analysis.c.

{
    list ll=lloop, lb=lblocks;
    instruction i;
    loop l;
 
    init_entity_variable_used();     
    current_variable_used_statement = inner_body;
 
    gen_recurse(inner_body, reference_domain, gen_true, variable_used_rewrite);
 
    for (; !ENDP(ll); ll=CDR(ll), lb=CDR(lb))
    {
        l = LOOP(CAR(ll));
 
        MAP(STATEMENT, s,
        {
            i = statement_instruction(s);
            
            if (!(instruction_loop_p(i) && l==instruction_loop(i)))
                gen_recurse(s,
                            reference_domain,
                            gen_true,
                            variable_used_rewrite);
            
        },
            CONSP(CAR(lb)));
    }
}

References CAR, CDR, CONSP, current_variable_used_statement, ENDP, gen_recurse, gen_true(), inner_body, instruction_loop, instruction_loop_p, lblocks, lloop, LOOP, MAP, reference_domain, STATEMENT, statement_instruction, and variable_used_rewrite().

Referenced by generate_optimized_code_for_loop_nest().

Here is the call graph for this function:

Here is the caller graph for this function:

make_increment_statement()

static statement make_increment_statement ( entity  index )

static

Definition at line 507 of file o-analysis.c.

{
    return(make_assign_statement
           (entity_to_expression(index),
            MakeBinaryCall(entity_intrinsic(PLUS_OPERATOR_NAME),
                           entity_to_expression(index),
                           int_to_expression(1))));
}

References entity_intrinsic(), entity_to_expression(), int_to_expression(), make_assign_statement(), MakeBinaryCall(), and PLUS_OPERATOR_NAME.

Referenced by make_loop_nest_for_overlap().

Here is the call graph for this function:

Here is the caller graph for this function:

make_loop_nest_for_overlap()

static statement make_loop_nest_for_overlap ( list  lold, list  lnew, list  lbl, entity_mapping  new_indexes, entity_mapping  old_indexes, statement  innerbody  )

static

??? should also look in lbl

if the index value is needed, the increment is added

i = initial_old_value DO i' = ... i = i + 1 body ENDDO

copy the non perfectly nested parts if needed

switch from pre to post.

the swith must have been encountered

Definition at line 639 of file o-analysis.c.

{
    entity index, oldindexvalue;
    loop oldloop, newloop;
    list l, lnew_loop = NIL, lnew_body = NIL;
    bool compute_index = false;
 
    if (ENDP(lold)) 
        return(innerbody);
    
    oldloop = LOOP(CAR(lold));
    newloop = LOOP(CAR(lnew));
 
    index = loop_index(oldloop);
    oldindexvalue = (entity) GET_ENTITY_MAPPING(old_indexes, index);
    lnew_body = CONS(STATEMENT,
                    make_loop_nest_for_overlap(CDR(lold), CDR(lnew), CDR(lbl),
                                               new_indexes, old_indexes, 
                                               innerbody),
                    NIL);
 
    /* ??? should also look in lbl */
    compute_index = (oldindexvalue!=(entity)HASH_UNDEFINED_VALUE) &&
        variable_used_in_statement_p(index, innerbody);
    
    /* if the index value is needed, the increment is added
     */
    if (compute_index)
        lnew_body = CONS(STATEMENT, make_increment_statement(index), 
                        lnew_body);
 
    loop_body(newloop) = make_block_statement(lnew_body);
    lnew_loop = CONS(STATEMENT,
                     instruction_to_statement(make_instruction(is_instruction_loop,
                                                         newloop)),
                     NIL);
 
    /* i = initial_old_value 
     * DO i' = ...
     *   i = i + 1
     *   body
     * ENDDO
     */
 
    if (compute_index)
        lnew_loop = 
            CONS(STATEMENT,
                 make_assign_statement(entity_to_expression(index),
                                       entity_to_expression(oldindexvalue)),
                 lnew_loop);
 
    /* copy the non perfectly nested parts if needed
     */
    l = CONSP(CAR(lbl));
    if (!ENDP(l))
    {
        statement
            s;
        instruction
            i;
        list
            lpre = NIL,
            lpost = NIL;
        bool 
            pre = true;
 
        for(; !ENDP(l); l=CDR(l))
        {
            s = STATEMENT(CAR(l));
            i = statement_instruction(s);
            
            /*  switch from pre to post.
             */
            if (instruction_loop_p(i) && instruction_loop(i)==oldloop)
                pre = false;
            else
                if (pre)
                    lpre = CONS(STATEMENT, copy_statement(s), lpre);
                else
                    lpost = CONS(STATEMENT, copy_statement(s), lpost);
        }
 
        /* the swith must have been encountered */
        assert(!pre);
            
        lnew_loop = gen_nconc(gen_nreverse(lpre),
                    gen_nconc(lnew_loop,
                              gen_nreverse(lpost)));
    }
 
    return(make_block_statement(lnew_loop));
}

References assert, CAR, CDR, CONS, CONSP, copy_statement(), ENDP, entity_to_expression(), gen_nconc(), gen_nreverse(), GET_ENTITY_MAPPING, HASH_UNDEFINED_VALUE, instruction_loop, instruction_loop_p, instruction_to_statement(), is_instruction_loop, LOOP, loop_body, loop_index, make_assign_statement(), make_block_statement(), make_increment_statement(), make_instruction(), NIL, STATEMENT, statement_instruction, and variable_used_in_statement_p().

Referenced by generate_optimized_code_for_loop_nest().

Here is the call graph for this function:

Here is the caller graph for this function:

make_loop_skeleton()

static loop make_loop_skeleton ( entity  newindex, expression  lower_expression, expression  upper_expression  )

static

statement is not yet defined

Definition at line 388 of file o-analysis.c.

{
    return(make_loop(newindex, 
                     make_range(lower_expression, 
                                upper_expression,
                                int_to_expression(1)),
                     statement_undefined, /* statement is not yet defined */
                     entity_empty_label(),
                     make_execution(is_execution_sequential, UU),
                     NIL));
}

References entity_empty_label(), int_to_expression(), is_execution_sequential, make_execution(), make_loop(), make_range(), NIL, statement_undefined, and UU.

Referenced by generate_optimized_code_for_loop_nest().

Here is the call graph for this function:

Here is the caller graph for this function:

message_manageable_p()

static bool message_manageable_p ( entity  array, list  lpref, list  lkref  )

static

every thing should be manageable, i.e.

??? removed: no star in the dimensions , and the width has to be accepted...

ta==local_star) ||

accepted!

Definition at line 202 of file o-analysis.c.

{
    list lp = NIL, lk = NIL;
    int i;
 
    for(i=1, lk=lkref, lp=lpref ; lk!=NIL ; lk=CDR(lk), lp=CDR(lp))
    {
        tag ta = access_tag(INT(CAR(lk)));
        Pvecteur v = (Pvecteur) PVECTOR(CAR(lp));
        Value vs = vect_coeff(TSHIFTV, v),
              vd = vect_coeff(DELTAV, v),
              vt = vect_coeff(TEMPLATEV, v);
        int p = 0,
            shift = VALUE_TO_INT(vs),
            dlt = VALUE_TO_INT(vd),
            t2 = VALUE_TO_INT(vt);
 
        if ((ta==not_aligned) ||
            /*(ta==local_star) ||*/
            (ta==aligned_star) ||
            ((ta==aligned_constant) &&
             (!on_same_proc_p(t2-dlt, t2,
                  array_to_template(array), 
                  template_dimension_of_array_dimension(array, i)))) ||
            ((ta==aligned_shift) &&
             (shift>DistributionParameterOfArrayDim(array, i, &p))))
        {
            debug(5, "message_manageable_p",
                  "returning false for %s, dim %d, access %d\n",
                  entity_name(array), i, ta);
 
            return(false);
        }
 
        i++;
    }
 
    if (!block_distributed_p(array)) return(false);
 
    /*
     * here the overlap is accepted, and stored
     *
     * ??? this should be done elsewhere, because too much overlap
     * may be too much memory, allocated... in generate_one_message()?
     */
 
 
    for(i=1, lk=lkref, lp=lpref ; lk!=NIL ; lk=CDR(lk), lp=CDR(lp))
    {
        tag ta = access_tag(INT(CAR(lk)));
        Value vs = vect_coeff(TSHIFTV, (Pvecteur) PVECTOR(CAR(lp)));
        int shift = VALUE_TO_INT(vs);
 
        if ((ta==aligned_shift) && (shift!=0))
            set_overlap(array, i, (shift<0)?(0):(1), abs(shift));
 
        i++;
    }
 
    return(true); /* accepted! */
}

References abs, access_tag, aligned_constant, aligned_shift, aligned_star, array, array_to_template, block_distributed_p(), CAR, CDR, debug(), DELTAV, DistributionParameterOfArrayDim(), entity_name, INT, NIL, not_aligned, on_same_proc_p(), PVECTOR, set_overlap(), template_dimension_of_array_dimension(), TEMPLATEV, TSHIFTV, VALUE_TO_INT, and vect_coeff().

Referenced by Overlap_Analysis().

Here is the call graph for this function:

Here is the caller graph for this function:

number_of_distributed_dimensions()

static int number_of_distributed_dimensions ( entity  a )

static

Definition at line 587 of file o-analysis.c.

{
    int p = -1, ndim = NumberOfDimension(a), i = 1, n = 0;
 
    for (i=1 ; i<=ndim ; i++)
        if (ith_dim_distributed_p(a, i, &p)) n++;
   
    return(n);
}

References ith_dim_distributed_p(), and NumberOfDimension().

Referenced by choose_one_syntax_in_references_list().

Here is the call graph for this function:

Here is the caller graph for this function:

on_same_proc_p()

static bool on_same_proc_p ( int  t1, int  t2, entity  template, int  dim  )

static

true if the given template elements on the specified dimension are mapped on the same processor.

Definition at line 187 of file o-analysis.c.

{
    int p;
    return(processor_number(template, dim, t1, &p) ==
           processor_number(template, dim, t2, &p));
}

References processor_number().

Referenced by message_manageable_p().

Here is the call graph for this function:

Here is the caller graph for this function:

Overlap_Analysis()

bool Overlap_Analysis	(	statement	stat,
		statement *	pstat
	)

check conditions and compile...

keeps only written references of which dimensions are block distributed, and indices simple enough (=> normalization of loops may be usefull). ??? bug: should also search for A(i,i) things that are forbidden...

ok distributed variable written !

must chose the computer among read references!

??? what about loop splitting

??? memory leak

??? memory leak

Now, we have the following situation: Wa: set of aligned written refs, the first of which is `‘the’' ref.

here is the situation now:

Wa set of aligned references written, Ra set of aligned references read, Ro set of nearly aligned references that suits the overlap analysis

messages handling

generate the local loop for every processor, given the global loop bounds. The former indexes have to be computed, and the loops are based upon new indexes, of which names have to be propagated in the body of the loop. This generation is to be based on the normalized form computed for every references of Ro, but it is direct for Ra and Wa, since new declarations implied that the alignment is performed for distributed indices. Not distributed dimensions indices have not to be touched, (at least if no new declarations are the common case)

Parameters

stat	tat
pstat	stat

Definition at line 870 of file o-analysis.c.

{
    list lw = NIL, lr = NIL, Ra = NIL, Ro = NIL, Rrt = NIL,
        lWa = NIL, lRa = NIL, lRo = NIL, W  = NIL, Wa = NIL, 
        Wrt = NIL, lvect = NIL, lkind = NIL, R=NIL;
    syntax the_computer_syntax = syntax_undefined;
    reference the_computer_reference = reference_undefined;
    statement innerbody, messages_stat, newloopnest;
    bool computer_is_written = true;
 
    DEBUG_STAT(9, "considering statement", stat);
 
    set_hpfc_current_statement(stat);
    set_current_loops(stat);
 
    lblocks = NIL,
    lloop = NIL;
    innerbody = parallel_loop_nest_to_body(stat, &lblocks, &lloop);
 
    FindRefToDistArrayInStatement(stat, &lw, &lr);
 
    /* keeps only written references of which dimensions are block distributed,
     * and indices simple enough (=> normalization of loops may be usefull).
     * ??? bug: should also search for A(i,i) things that are forbidden...
     */
    MAP(SYNTAX, s,
    {
        reference r = syntax_reference(s);
        entity array = reference_variable(r);
        
        if ((block_distributed_p(array)) && 
            (simple_indices_p(r)) && (!replicated_p(array)))
            W = CONS(SYNTAX, s, W);
        else
            Wrt = CONS(SYNTAX, s, Wrt);
    },
        lw);
 
    pips_debug(9, "choosing computer\n");
 
    if (W) /* ok distributed variable written ! */
    {
        the_computer_syntax = choose_one_syntax_in_references_list(&W);
        the_computer_reference = syntax_reference(the_computer_syntax);
        Wa = CONS(SYNTAX, the_computer_syntax, NIL);
    }
    else  /* must chose the computer among read references! */
    {
        computer_is_written = false;
 
        MAP(SYNTAX, s,
        {
            reference r = syntax_reference(s);
            entity array = reference_variable(r);
        
            if ((block_distributed_p(array)) && 
                (simple_indices_p(r)) && (!replicated_p(array)))
                R = CONS(SYNTAX, s, R);
        },
            lr);
 
        if (R) 
        {
            the_computer_syntax = choose_one_syntax_in_references_list(&R);
            the_computer_reference = syntax_reference(the_computer_syntax);
            Ra = CONS(SYNTAX, the_computer_syntax, NIL);
        }
        else
            RETURN(false); 
    }
 
    if (!align_check(the_computer_reference,
                     the_computer_reference, &lvect, &lkind))
        pips_internal_error("no self alignment!");
 
    if (computer_is_written)
      lWa = CONS(LIST, CONS(LIST, lkind, CONS(LIST, lvect, NIL)), NIL);
    else
      lRa = CONS(LIST, CONS(LIST, lkind, CONS(LIST, lvect, NIL)), NIL);
 
    pips_debug(9, "checking alignments\n");
 
    MAP(SYNTAX, s,
    {
        reference r = syntax_reference(s);
        if (the_computer_reference==r) 
          continue;
        if (align_check(the_computer_reference, r, &lvect, &lkind))
        {
            if (aligned_p(the_computer_reference, r, lvect, lkind))
            {
                Wa = gen_nconc(Wa, CONS(SYNTAX, s, NIL));
                lWa = gen_nconc(lWa, CONS(LIST,
                                          CONS(LIST, lkind, 
                                               CONS(LIST, lvect, NIL)),
                                          NIL));
            }
            else /* ??? what about loop splitting */
            {
                Wrt = gen_nconc(Wrt, CONS(SYNTAX, s, NIL));
                gen_free_list(lvect);
                gen_free_list(lkind); /* ??? memory leak */
            }
            }
        else
        {
            Wrt = gen_nconc(Wrt, CONS(SYNTAX, s, NIL));
            gen_free_list(lvect);
            gen_free_list(lkind); /* ??? memory leak */
        }
    },
        W);
 
    pips_debug(5, "Wa length is %zd (%zd), Wrt lenght is %zd\n",
               gen_length(Wa), gen_length(lWa), gen_length(Wrt));
 
    if (gen_length(Wrt)!=0) 
        RETURN(false);
 
    /* Now, we have the following situation:
     * Wa: set of aligned written refs, the first of which is ``the'' ref.
     */
    MAP(SYNTAX, s,
     {
         reference r = syntax_reference(s);
         entity array = reference_variable(r);
         list lvect = NIL;
         list lkind = NIL;
 
         if (the_computer_reference==r) continue;
 
         pips_debug(6, "dealing with reference of array %s\n",
                    entity_name(array));
 
         ifdebug(6)
         {
             fprintf(stderr, "[Overlap_Analysis]\nreference is:\n");
             print_reference(r);
             fprintf(stderr, "\n");
         }
 
         if (align_check(the_computer_reference, r, &lvect, &lkind))
         {
             if (aligned_p(the_computer_reference, r, lvect, lkind))
             {
                 Ra = gen_nconc(Ra, CONS(SYNTAX, s, NIL));
                 lRa = gen_nconc(lRa, CONS(LIST,
                                           CONS(LIST, lkind,
                                                CONS(LIST, lvect, NIL)),
                                           NIL));
             }
             else
             if (message_manageable_p(array, lvect, lkind))
             {
                 Ro = gen_nconc(Ro, CONS(SYNTAX, s, NIL));
                 lRo = gen_nconc(lRo, CONS(LIST,
                                           CONS(LIST, lkind, 
                                                CONS(LIST, lvect, NIL)),
                                           NIL));
             }
             else
             {
                 Rrt = gen_nconc(Rrt, CONS(SYNTAX, s, NIL));
                 gen_free_list(lvect);
                 gen_free_list(lkind);
             }
         }
         else
         {
             Rrt = gen_nconc(Rrt, CONS(SYNTAX, s, NIL));
             gen_free_list(lvect);
             gen_free_list(lkind);
         }
     },
         lr);
 
    debug(5, "Overlap_Analysis",
          "Ra length is %d, Ro length is %d, Rrt lenght is %d\n",
          gen_length(Ra), gen_length(Ro), gen_length(Rrt));
 
    if (gen_length(Rrt)!=0) 
        RETURN(false);
 
    /* here is the situation now:
     *
     * Wa set of aligned references written,
     * Ra set of aligned references read,
     * Ro set of nearly aligned references that suits the overlap analysis
     */
 
    /* messages handling
     */
    messages_stat = ((gen_length(Ro)>0)?
                     (messages_handling(Ro, lRo)):
                     (make_continue_statement(entity_empty_label())));
 
    /* generate the local loop for every processor, given the global loop
     * bounds. The former indexes have to be computed, and the loops are
     * based upon new indexes, of which names have to be propagated in the
     * body of the loop. This generation is to be based on the normalized
     * form computed for every references of Ro, but it is direct for
     * Ra and Wa, since new declarations implied that the alignment is
     * performed for distributed indices. Not distributed dimensions
     * indices have not to be touched, (at least if no new declarations are
     * the common case)
     */
    if (!generate_optimized_code_for_loop_nest
        (innerbody, &newloopnest, the_computer_syntax, 
         Wa, Ra, Ro, lWa, lRa, lRo))
        RETURN(false);
 
    DEBUG_STAT(9, entity_name(node_module), newloopnest);
 
    (*pstat) =
        make_block_statement
            (CONS(STATEMENT, messages_stat,
             CONS(STATEMENT,
                  loop_nest_guard(newloopnest,
                                  the_computer_reference,
                  CONSP(CAR(CONSP(CAR(computer_is_written? lWa: lRa)))),
                  CONSP(CAR(CDR(CONSP(CAR(computer_is_written? lWa: lRa)))))),
                  NIL)));
 
    DEBUG_STAT(8, entity_name(node_module), *pstat);
 
    RETURN(true);
}

References align_check(), aligned_p(), array, block_distributed_p(), CAR, CDR, choose_one_syntax_in_references_list(), CONS, CONSP, debug(), DEBUG_STAT, entity_empty_label(), entity_name, FindRefToDistArrayInStatement(), fprintf(), gen_free_list(), gen_length(), gen_nconc(), generate_optimized_code_for_loop_nest(), ifdebug, lblocks, LIST, lloop, loop_nest_guard(), lvect, make_block_statement(), make_continue_statement(), MAP, message_manageable_p(), messages_handling(), NIL, node_module, parallel_loop_nest_to_body(), pips_debug, pips_internal_error, print_reference(), reference_undefined, reference_variable, replicated_p(), RETURN, set_current_loops(), set_hpfc_current_statement(), simple_indices_p(), STATEMENT, SYNTAX, syntax_reference, and syntax_undefined.

Referenced by hpf_compile_loop().

Here is the call graph for this function:

Here is the caller graph for this function:

simple_indices_p()

static bool simple_indices_p ( reference  r )

static

true if indices are constants or index

cannot decide, so it is supposed to be false

??? checks that there is a shift alignment, what shouldn't be necessary...

Definition at line 64 of file o-analysis.c.

{
    entity array = reference_variable(r);
    int dim = 1;
 
    ifdebug(6) {
        pips_debug(6, "considering reference: ");
        print_reference(r);
        fprintf(stderr,"\n");
    }
 
    MAP(EXPRESSION, e,
     {
         normalized  n = expression_normalized(e); 
         int p;
         bool b1 = ith_dim_distributed_p(array, dim, &p);
         bool b2 = ((!b1) ? local_integer_constant_expression(e) : false);
 
         pips_debug(7, "%s(DIM=%d), distributed %d, locally constant %d\n",
                    entity_name(array), dim, b1, b2);
 
         if (!b2)
         {
         if (normalized_complex_p(n)) 
             /* cannot decide, so it is supposed to be false */
         {
             pips_debug(7, "returning false (complex)\n");
             return false; 
         }
         else
         {
             Pvecteur v = (Pvecteur) normalized_linear(n);
             int s = vect_size(v);
             
             if (s>1) 
             {
                 ifdebug(7) {
                     pips_debug(7, "returning false, vect size %d>1\n", s);
                     vect_debug(v);
                 }
                 return false;
             }
             
             if ((s==1) && 
                 (!entity_loop_index_p((entity)v->var)) &&
                 (value_zero_p(vect_coeff(TCST, v))))
             {
                 pips_debug(7, "returning false (not simple)\n");
                 return false;
             }
             else
             if (entity_loop_index_p((entity)v->var))
             {
                 /* ??? checks that there is a shift alignment, 
                  * what shouldn't be necessary...
                  */
                 alignment al = FindArrayDimAlignmentOfArray(array, dim);
                 int rate = al==alignment_undefined?
                     0: HpfcExpressionToInt(alignment_rate(al)) ;
 
                 if (rate!=0 && rate!=1)
                 {
                     pips_debug(7, "returning false (stride)\n");
                     return(false);
                 }
             }
         }
         }
         
         dim++;
     },
         reference_indices(r));
    
    pips_debug(7, "returning TRUE!\n");
    return true;
}

References alignment_rate, alignment_undefined, array, b1, b2, entity_loop_index_p(), entity_name, EXPRESSION, expression_normalized, FindArrayDimAlignmentOfArray, fprintf(), HpfcExpressionToInt(), ifdebug, ith_dim_distributed_p(), local_integer_constant_expression(), MAP, normalized_complex_p, normalized_linear, pips_debug, print_reference(), reference_indices, reference_variable, TCST, value_zero_p, Svecteur::var, vect_coeff(), vect_debug(), and vect_size().

Referenced by Overlap_Analysis().

Here is the call graph for this function:

Here is the caller graph for this function:

statement_compute_bounds()

static statement statement_compute_bounds ( entity  newlobnd, entity  newupbnd, entity  oldidxvl, expression  lb, expression  ub, int  an, int  dp  )

static

generate the call to the dynamic loop bounds computation

Definition at line 286 of file o-analysis.c.

{
    list
        l = CONS(EXPRESSION, entity_to_expression(newlobnd),
            CONS(EXPRESSION, entity_to_expression(newupbnd),
            CONS(EXPRESSION, entity_to_expression(oldidxvl),
            CONS(EXPRESSION, lb,
            CONS(EXPRESSION, ub,
            CONS(EXPRESSION, int_to_expression(an),
            CONS(EXPRESSION, int_to_expression(dp),
                 NIL)))))));
 
    return(hpfc_make_call_statement(hpfc_name_to_entity(LOOP_BOUNDS), l));
}

References CONS, entity_to_expression(), EXPRESSION, hpfc_make_call_statement(), hpfc_name_to_entity(), int_to_expression(), LOOP_BOUNDS, and NIL.

Referenced by generate_optimized_code_for_loop_nest().

Here is the call graph for this function:

Here is the caller graph for this function:

update_indices_for_local_computation()

static void update_indices_for_local_computation ( entity_mapping  new_indexes, list  Ref, list  lRef  )

static

caution: only distributed dimensions indexes are modified other have to remain untouched... ??? aligned star is missing

find the new index of the loop

compute the local indice

??? nothing is changed

Definition at line 404 of file o-analysis.c.

{
    list lr = Ref, lkv = lRef;
 
    for ( ; (lr!=NIL) ; lr=CDR(lr), lkv=CDR(lkv))
    {
        int dim = 1;
        syntax s = SYNTAX(CAR(lr));
        reference r = syntax_reference(s);
        entity array = reference_variable(r);
        list
            l1 = CONSP(CAR(lkv)),
            lk = CONSP(CAR(l1)),
            li = reference_indices(r),
            lv = CONSP(CAR(CDR(l1))),
            li2 = NIL;
 
        for ( ; (lk!=NIL) ; POP(lk), POP(li), POP(lv))
        {
            expression indice = EXPRESSION(CAR(li));
            Pvecteur v = (Pvecteur) PVECTOR(CAR(lv));
            access ac = INT(CAR(lk));
 
            /* caution: only distributed dimensions indexes are modified
             * other have to remain untouched...
             * ??? aligned star is missing
             */
            switch (access_tag(ac))
            {
            case aligned_shift: /* find the new index of the loop */
            {
                Pvecteur vindex = the_index_of_vect(v);
                entity
                    oldindex = (entity) var_of(vindex),
                    newindex = (entity) GET_ENTITY_MAPPING(new_indexes, 
                                                           oldindex);
                Value shift = vect_coeff(TSHIFTV, v);
 
                if (value_zero_p(shift))
                {
                    li2 = gen_nconc(li2,
                                    CONS(EXPRESSION,
                                         entity_to_expression(newindex),
                                         NIL));
                }
                else
                {
                    li2 = 
                        gen_nconc(li2,
                                  CONS(EXPRESSION,
                                       MakeBinaryCall
                                       (entity_intrinsic(value_pos_p(shift)?
                                                        (PLUS_OPERATOR_NAME):
                                                        (MINUS_OPERATOR_NAME)),
                                        entity_to_expression(newindex),
                                        Value_to_expression(value_abs(shift))),
                                       NIL));
                }
 
                break;
            }
            case aligned_constant: /* compute the local indice */
            {
                Value vval = vect_coeff(TEMPLATEV, v);
                int tval = VALUE_TO_INT(vval);
                
                li2 = gen_nconc(li2,
                                CONS(EXPRESSION,
                                     int_to_expression
                                     (template_cell_local_mapping(array, 
                                                                  dim, 
                                                                  tval)),
                                     NIL));
                break;
            }
            case aligned_affine:
            case aligned_star:
                pips_internal_error("part of that function not implemented yet");
                break;
            default: /* ??? nothing is changed */
                li2 = gen_nconc(li2, CONS(EXPRESSION, indice, NIL));
                break;
            }
            dim++;
        }
 
        reference_indices(r) = li2;
 
        ifdebug(8)
         {
             fprintf(stderr,
              "[update_indices_for_local_computation]\nnew reference is:\n");
             print_reference(r);
             fprintf(stderr, "\n");
         }
 
    }
    
}

References access, access_tag, aligned_affine, aligned_constant, aligned_shift, aligned_star, array, CAR, CDR, CONS, CONSP, entity_intrinsic(), entity_to_expression(), EXPRESSION, fprintf(), gen_nconc(), GET_ENTITY_MAPPING, ifdebug, INT, int_to_expression(), MakeBinaryCall(), MINUS_OPERATOR_NAME, NIL, pips_internal_error, PLUS_OPERATOR_NAME, POP, print_reference(), PVECTOR, Ref, reference_indices, reference_variable, SYNTAX, syntax_reference, template_cell_local_mapping(), TEMPLATEV, the_index_of_vect(), TSHIFTV, value_abs, value_pos_p, Value_to_expression(), VALUE_TO_INT, value_zero_p, var_of, and vect_coeff().

Referenced by generate_optimized_code_for_loop_nest().

Here is the call graph for this function:

Here is the caller graph for this function:

variable_used_in_statement_p()

static bool variable_used_in_statement_p ( entity  ent, statement  stat  )

static

Definition at line 579 of file o-analysis.c.

{
    message_assert("current statement", stat==current_variable_used_statement);
    return bound_entity_variable_used_p(ent);
}

References current_variable_used_statement, and message_assert.

Referenced by make_loop_nest_for_overlap().

Here is the caller graph for this function:

variable_used_rewrite()

static void variable_used_rewrite ( reference  r )

static

Definition at line 530 of file o-analysis.c.

{
    entity v = reference_variable(r);    
 
    if (bound_entity_variable_used_p(v))
        update_entity_variable_used(v, load_entity_variable_used(v)+1);
    else
        store_entity_variable_used(v, 1);
}

References reference_variable.

Referenced by initialize_variable_used_map_for_current_loop_nest().

Here is the caller graph for this function:

which_array_dimension()

static int which_array_dimension ( reference  r, entity  e  )

static

returns the dimension of reference on which index entity e is used

Definition at line 364 of file o-analysis.c.

{
    int dim = 1;
    list li = reference_indices(r);
    Variable v = (Variable) e;
 
    MAP(EXPRESSION, e,
    {
        normalized n = expression_normalized(e);
        
        if (normalized_linear_p(n) &&
            (vect_coeff(v, (Pvecteur)normalized_linear(n)) != 0))
            return(dim);
        
        dim++;
    },
        li);
 
    return(-1);
}

References EXPRESSION, expression_normalized, MAP, normalized_linear, normalized_linear_p, reference_indices, and vect_coeff().

Referenced by generate_optimized_code_for_loop_nest().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

current_variable_used_statement

statement current_variable_used_statement = statement_undefined

static

bool variable_used_in_statement_p(ent, stat)

not 0 if ent is referenced in statement stat. yes, I know, proper effects may be called several times for the same statement...

??? I should have used cumulated/proper effects to be computed on the statement being generated, but It would not have been as easy to compute and to use.

Definition at line 528 of file o-analysis.c.

Referenced by close_variable_used_map_for_statement(), initialize_variable_used_map_for_current_loop_nest(), and variable_used_in_statement_p().

hpfc_killed_scalar

bool hpfc_killed_scalar

static

To Kill scalar definitions within the generated code recognize if only one reference.

Definition at line 311 of file o-analysis.c.

Referenced by hpfc_overlap_kill_unused_scalars(), and hpfc_overlap_kill_unused_scalars_rewrite().

lblocks

list lblocks = NIL

static

Overlap Analysis Module for HPFC.

Fabien Coelho, August 1993

Definition at line 38 of file o-analysis.c.

Referenced by generate_optimized_code_for_loop_nest(), initialize_variable_used_map_for_current_loop_nest(), and Overlap_Analysis().

lloop

list lloop = NIL

static

Definition at line 38 of file o-analysis.c.

Referenced by generate_optimized_code_for_loop_nest(), initialize_variable_used_map_for_current_loop_nest(), and Overlap_Analysis().