align-checker.c File Reference

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

Include dependency graph for align-checker.c:

Go to the source code of this file.

Macros
#define	REGION_TYPE   EFFECT_TYPE
	Align Checker. More...

Functions
static bool	write_on_entity_p (entity e)
bool	local_integer_constant_expression (expression e)
	true is the expression is locally constant, that is in the whole loop nest, the reference is not written. More...
static bool	shift_expression_of_loop_index_p (expression e, entity *pe, int *pi)
	true if the expression is shift function of a loop nest index. More...
static bool	affine_expression_of_loop_index_p (expression e, entity *pe, int *pi1, int *pi2)
	true if the expression is an affine function of a loop nest index. More...
bool	align_check (reference r1, reference r2, list *plvect, list *plkind)
	computes the shift vector that links the two references, true if every thing is ok, i.e. More...
bool	hpfc_integer_constant_expression_p (expression e, int *pi)

Macro Definition Documentation

REGION_TYPE

#define REGION_TYPE   EFFECT_TYPE

Align Checker.

try to decide whether two references are aligned or not. if not, gives back the alignement shift vector of the second reference to the first one.

this should use use-def chains, vectors and so on

Fabien Coelho August 93

Definition at line 47 of file align-checker.c.

Function Documentation

affine_expression_of_loop_index_p()

static bool affine_expression_of_loop_index_p ( expression  e, entity *  pe, int *  pi1, int *  pi2  )

static

true if the expression is an affine function of a loop nest index.

just to avoid a gcc warning

Definition at line 130 of file align-checker.c.

{
    normalized n = expression_normalized(e);
 
    ifdebug(6)
    {
        fprintf(stderr, "[affine_expression_of_loop_index_p]\nexpression:\n");
        print_expression(e);
    }
            
    pips_assert("normalized", !normalized_undefined_p(n));
 
    switch (normalized_tag(n))
    {
    case is_normalized_complex:
        return(false);
        break;
    case is_normalized_linear:
    {
        Pvecteur v = (Pvecteur) normalized_linear(n),
            vp = vect_del_var(v, TCST);
        int s = vect_size(vp);
        bool result;
 
        if (s!=1) return(false);
 
        result = (entity_loop_index_p((entity)var_of(vp)) && 
                  value_notone_p(val_of(vp)));
 
        if (result) 
        {
            Value v1 = vect_coeff(TCST, v);
            *pe = (entity) var_of(vp);
            *pi1 = VALUE_TO_INT(v1);
            *pi2 = VALUE_TO_INT(val_of(vp));
        }
 
        vect_rm(vp);
 
        return result;
        break;
    }
    default:
        pips_internal_error("unexpected normalized tag");
        break;
    }
    
    return(false); /* just to avoid a gcc warning */
}

References entity_loop_index_p(), expression_normalized, fprintf(), ifdebug, is_normalized_complex, is_normalized_linear, normalized_linear, normalized_tag, normalized_undefined_p, pips_assert, pips_internal_error, print_expression(), TCST, val_of, value_notone_p, VALUE_TO_INT, var_of, vect_coeff(), vect_del_var(), vect_rm(), and vect_size().

Referenced by align_check().

Here is the call graph for this function:

Here is the caller graph for this function:

align_check()

bool align_check	(	reference	r1,
		reference	r2,
		list *	plvect,
		list *	plkind
	)

computes the shift vector that links the two references, true if every thing is ok, i.e.

the vector is ok for the distributed dimensions... The vector considered here is just a list of integers. conditions: same template

default value, used in the shift case !

default value, used in the const case !

replication, say it is not aligned

replicated reference...

a(i) -> t(i,1), b(i,j)->t(i,j), should detect do i a(i) = b(i,1) as aligned...

??? this could be managed later in this function...

should be ok, even if a delta is induced, if it stays on the same processor along this dimension. The case should also be managed downward, when playing with local updates. ??? maybe there is also a consequence on the send/receive symetry, in order to put the message where it should be...

it is checked later whether the data are on the same processor or not.

now we have everything to check whether it is aligned... and to compute the shift necessary to the overlap analysis.

something is true!

just check whether aligned or not

even in the constant case ! not aligned

aligned... ??? bug if not 1: later on, because decl shift

4 cases study with bconst and bshift, plus the rates

what should be the relevent information(s) ??? not only d, but shift2 and t2 may be usefull either ??? what about rates!=1 ? decl shift problem added.

say not aligned...

??? decl shift problem may occur here as well

??? I should do something with blcnst2?

well, say not aligned, but one to many or many to one communications may be used...

ith dimension of e2 is not distributed

may be used to generate RSDs

else the local constant should be detected, for onde24...

Parameters

r1	1
r2	2
plvect	lvect
plkind	lkind

Definition at line 190 of file align-checker.c.

{
    int procdim, i, ne2dim;
    entity e1, e2;
    align a1, a2;
    bool ok = true;
    list li1, li2;
 
    e1 = reference_variable(r1),
    e2 = reference_variable(r2);
    a1 = load_hpf_alignment(e1),
    a2 = load_hpf_alignment(e2);
    li1 = reference_indices(r1),
    li2 = reference_indices(r2);
    *plvect = NIL;
    *plkind = NIL;
 
    pips_debug(7, "with references to %s[DIM=%zd] and %s[DIM=%zd]\n",
          entity_name(e1), gen_length(li1), entity_name(e2), gen_length(li2));
 
    ne2dim = NumberOfDimension(e2);
    
    if (!conformant_templates_p(align_template(a1),align_template(a2)))
    {
        pips_debug(5, "different templates\n");
 
        for (i=1 ; i<=ne2dim ; i++)
            if (ith_dim_distributed_p(e2, i, &procdim))
            {
                *plkind = gen_nconc(*plkind, CONS(INT, not_aligned, NIL));
                *plvect = gen_nconc(*plvect, CONS(PVECTOR,
                                                  (VECTOR) VECTEUR_NUL, NIL));
            }
            else
            {
                *plkind = gen_nconc(*plkind, CONS(INT, local_star, NIL));
                *plvect = gen_nconc(*plvect, CONS(PVECTOR,
                                                  (VECTOR) VECTEUR_NUL, NIL));
            }
        
        return ok;
    }
 
    ifdebug(8)
         {
             fprintf(stderr, "[align_check] references are: ");
             print_reference(r1);
             fprintf(stderr, " and ");
             print_reference(r2);
             fprintf(stderr, "\n");
         }
 
    for (i=1 ; i<=ne2dim ; i++)
    {
        expression indice1, indice2; 
        int 
            affr1 = 1, /* default value, used in the shift case ! */
            affr2 = 1,
            shft1, shft2;
        entity
            index1 = NULL, /* default value, used in the const case ! */
            index2 = NULL;
        bool
            baffin1, baffin2,
            bshift1, bshift2,
            bconst1, bconst2,
            blcnst2=0;
 
        pips_debug(8, "considering dimension %d of %s\n", i, entity_name(e2));
 
        indice2 = EXPRESSION(gen_nth(i-1, li2));
 
        baffin2 = affine_expression_of_loop_index_p(indice2, 
                                                    &index2, &shft2, &affr2);
        bshift2 = shift_expression_of_loop_index_p(indice2, &index2, &shft2);
        bconst2 = hpfc_integer_constant_expression_p(indice2, &shft2);
        if (!(baffin2 || bshift2 || bconst2))
            blcnst2 = local_integer_constant_expression(indice2);
        
        if (ith_dim_distributed_p(e2, i, &procdim))
        {
            alignment
                a2 = FindArrayDimAlignmentOfArray(e2, i),
                a1 = FindTemplateDimAlignmentOfArray(e1,
                                 alignment_templatedim(a2));
            int
                dim1=((a1!=alignment_undefined)?(alignment_arraydim(a1)):(-1)),
                rate1, rate2, 
                cnst1, cnst2;
 
            rate2   = HpfcExpressionToInt(alignment_rate(a2));
            cnst2   = HpfcExpressionToInt(alignment_constant(a2));
 
            if ((dim1<0) || /* replication, say it is not aligned */
                ((dim1==0) && (!bconst2))) /* replicated reference...*/
            {
                pips_debug(8, "%s[DIM=%d] not aligned aff %d shi %d cst %d\n",
                           entity_name(e2), i, baffin2, bshift2, bconst2);
 
                *plkind = gen_nconc(*plkind, CONS(INT, not_aligned, NIL));
                *plvect = gen_nconc(*plvect, CONS(PVECTOR, 
                                                  (VECTOR) VECTEUR_NUL, NIL));
            }
            else
            if ((dim1==0) && (bconst2))
            {
                /* a(i) -> t(i,1), b(i,j)->t(i,j), should detect 
                 * do i a(i) = b(i,1) as aligned...
                 *
                 * ??? this could be managed later in this function...
                 */
 
                int t1 = HpfcExpressionToInt(alignment_constant(a1)),
                    t2 = rate2*shft2+cnst2;
                
                /* should be ok, even if a delta is induced, if it stays
                 * on the same processor along this dimension. The case
                 * should also be managed downward, when playing with 
                 * local updates. 
                 * ??? maybe there is also a consequence on the 
                 * send/receive symetry, in order to put the message where it
                 * should be...
                 */
 
                /* it is checked later whether the data are on the same 
                 * processor or not.
                 */
 
                *plkind = gen_nconc(*plkind, CONS(INT, aligned_constant, NIL));
                *plvect = gen_nconc(*plvect,
                                    CONS(PVECTOR, (VECTOR)
                   vect_add(vect_new(TEMPLATEV, int_to_value(t2)),
                            vect_new(DELTAV, int_to_value(t2-t1))),
                                         NIL));
            }
            else
            {
                indice1 = EXPRESSION(gen_nth(dim1-1, li1));
 
                rate1   = HpfcExpressionToInt(alignment_rate(a1));
                cnst1   = HpfcExpressionToInt(alignment_constant(a1));
 
                baffin1 = affine_expression_of_loop_index_p
                    (indice1, &index1, &shft1, &affr1);
                bshift1 = shift_expression_of_loop_index_p
                    (indice1, &index1, &shft1);
                bconst1 = hpfc_integer_constant_expression_p
                    (indice1, &shft1);          
 
                /* now we have everything to check whether it is aligned...
                 * and to compute the shift necessary to the overlap analysis.
                 */
 
                if (!((baffin1 || bshift1 || bconst1) &&
                      (baffin2 || bshift2 || bconst2)))
                {
                    *plkind = gen_nconc(*plkind, CONS(INT, not_aligned, NIL));
                    *plvect = gen_nconc(*plvect, CONS(PVECTOR,(VECTOR) 
                                                      VECTEUR_NUL, NIL));
                }
                else /* something is true! */
                if (baffin1 || baffin2) /* just check whether aligned or not */
                {
                    int
                        r1 = ((bconst1)?(0):(rate1*affr1)),
                        r2 = ((bconst2)?(0):(rate2*affr2)),
                        c1 = rate1*shft1+cnst1,
                        c2 = rate2*shft2+cnst2;
 
                    /* even in the constant case ! not aligned */
                    if ((index1!=index2) ||
                        (r1!=r2) || (c1!=c2))
                    {
                        *plkind = 
                            gen_nconc(*plkind, CONS(INT, not_aligned, NIL));
                        *plvect = 
                            gen_nconc(*plvect, CONS(PVECTOR, 
                                          (VECTOR) VECTEUR_NUL, NIL));
                    }    
                    else /* aligned... ??? 
                          * bug if not 1: later on, because decl shift
                          */
                    {
                        *plkind = 
                            gen_nconc(*plkind, CONS(INT, aligned_star, NIL));
                        *plvect = 
                            gen_nconc(*plvect, CONS(PVECTOR,
                                         (VECTOR) VECTEUR_NUL, NIL));
                    }
                }
                else /* 4 cases study with bconst and bshift, plus the rates */
                if (bconst1 && bconst2)
                {
                    int
                        t1 = (rate1*shft1+cnst1),
                        t2 = (rate2*shft2+cnst2),
                        d  = (t2-t1);
 
                    /* what should be the relevent information(s) ??? 
                     * not only d, but shift2 and t2 may be usefull either
                     * ??? what about rates!=1 ? decl shift problem added.
                     */
 
                    *plkind = 
                        gen_nconc(*plkind, CONS(INT, aligned_constant, NIL));
                    *plvect = 
                        gen_nconc(*plvect, 
                                  CONS(PVECTOR, (VECTOR)
                                       vect_make(VECTEUR_NUL,
                                                 DELTAV, int_to_value(d),
                                                 TEMPLATEV, int_to_value(t2),
                                                 TCST, int_to_value(shft2)),
                                       NIL));
                }
                else /* say not aligned... */
                if ((rate1!=1) || (rate2!=1) || (index1!=index2)) 
                {
                    *plkind = gen_nconc(*plkind, 
                                        CONS(INT, not_aligned, NIL));
                    *plvect = gen_nconc(*plvect,
                                CONS(PVECTOR, (VECTOR) VECTEUR_NUL, NIL));
                }
                else
                if (bshift1 && bshift2)
                {
                    /* ??? decl shift problem may occur here as well */
                    int
                        tc1   = (shft1+cnst1),
                        tc2   = (shft2+cnst2),
                        shift = (tc2-tc1);
 
                    *plkind = gen_nconc(*plkind, CONS(INT, aligned_shift, NIL));
                    *plvect = gen_nconc
                        (*plvect, 
                         CONS(PVECTOR, (VECTOR)
                              vect_make(VECTEUR_NUL,
                                        TSHIFTV, int_to_value(shift),
                                        (Variable) index1, VALUE_ONE,
                                        TCST, int_to_value(shft2)),
                              NIL));
                }
                else /* ??? I should do something with blcnst2? */
                {
                    /* well, say not aligned, but one to many or many to one
                     * communications may be used...
                     */
                    *plkind = 
                        gen_nconc(*plkind, CONS(INT, not_aligned, NIL));
                    *plvect = 
                        gen_nconc(*plvect,
                                  CONS(PVECTOR, (VECTOR)  VECTEUR_NUL, NIL));
                }                                
            }
        }
        else /* ith dimension of e2 is not distributed */
        {
            if (!(baffin2 || bshift2 || bconst2 || blcnst2))
            {
                *plkind = gen_nconc(*plkind, CONS(INT, local_star, NIL));
                *plvect = gen_nconc(*plvect,
                                    CONS(PVECTOR, (VECTOR) VECTEUR_NUL, NIL));
            }
            else
            if (baffin2) /* may be used to generate RSDs */
            {
                *plkind = gen_nconc(*plkind, CONS(INT, local_affine, NIL));
                *plvect = 
                    gen_nconc(*plvect, 
                       CONS(PVECTOR, (VECTOR)
                            vect_make(VECTEUR_NUL,
                                      (Variable) index2, int_to_value(affr2),
                                      TCST, int_to_value(shft2)),
                            NIL));
            }
            else
            if (bshift2)
            {
                *plkind = gen_nconc(*plkind, CONS(INT, local_shift, NIL));
                *plvect = 
                    gen_nconc(*plvect, 
                              CONS(PVECTOR, (VECTOR)
                                   vect_make(VECTEUR_NUL,
                                             (Variable) index2, VALUE_ONE,
                                             TCST, int_to_value(shft2)),
                                   NIL));
            }
            else
            if (bconst2)
            {
                *plkind = gen_nconc(*plkind, CONS(INT, local_constant, NIL));
                *plvect = gen_nconc(*plvect, CONS(PVECTOR, (VECTOR)
                             vect_new(TCST, int_to_value(shft2)),
                                                  NIL));
            }
            /* else the local constant should be detected, for onde24... */
            else
            if (blcnst2)
            {
                *plkind = gen_nconc(*plkind, CONS(INT, local_form_cst, NIL));
                *plvect = 
                    gen_nconc(*plvect, 
                              CONS(PVECTOR,  (VECTOR)
                           normalized_linear(expression_normalized(indice2)),
                                   NIL));
            }
        }
    }
 
    ifdebug(8)
    {
        list l;
        fprintf(stderr, "[align_check] returning: ");
        for (l=*plkind; l; POP(l))
            fprintf(stderr, "%"PRIdPTR", ", INT(CAR(l)));
        fprintf(stderr, "\n");
    }
 
    return ok;
}

References affine_expression_of_loop_index_p(), align_template, aligned_constant, aligned_shift, aligned_star, alignment_arraydim, alignment_constant, alignment_rate, alignment_templatedim, alignment_undefined, CAR, conformant_templates_p(), CONS, DELTAV, entity_name, EXPRESSION, expression_normalized, FindArrayDimAlignmentOfArray, FindTemplateDimAlignmentOfArray, fprintf(), gen_length(), gen_nconc(), gen_nth(), hpfc_integer_constant_expression_p(), HpfcExpressionToInt(), ifdebug, INT, int_to_value, ith_dim_distributed_p(), load_hpf_alignment(), local_affine, local_constant, local_form_cst, local_integer_constant_expression(), local_shift, local_star, NIL, normalized_linear, not_aligned, NumberOfDimension(), ok, pips_debug, POP, print_reference(), PVECTOR, reference_indices, reference_variable, shift_expression_of_loop_index_p(), TCST, TEMPLATEV, TSHIFTV, VALUE_ONE, vect_add(), vect_make(), vect_new(), VECTEUR_NUL, and VECTOR.

Referenced by Overlap_Analysis().

Here is the call graph for this function:

Here is the caller graph for this function:

hpfc_integer_constant_expression_p()

bool hpfc_integer_constant_expression_p	(	expression	e,
		int *	pi
	)

just to avoid a gcc warning

Parameters

pi

i

Definition at line 514 of file align-checker.c.

{
    normalized n = expression_normalized(e);
 
    if (normalized_undefined_p(n)) 
    {
        n = NORMALIZE_EXPRESSION(e);
    }
 
    switch (normalized_tag(n))
    {
    case is_normalized_complex:
        return(false);
        break;
    case is_normalized_linear:
    {
        Pvecteur  v = (Pvecteur) normalized_linear(n),
            vp = vect_del_var(v, TCST);
        int s = vect_size(vp);
        bool result = (s==0);
 
        vect_rm(vp);
 
        if (result)
        {
            Value vi = vect_coeff(TCST, v);
            *pi = VALUE_TO_INT(vi);
        }
        
        return(result);
        break;
    }
    default:
        pips_internal_error("unexpected normalized tag");
        break;
    }
    
    return(false); /* just to avoid a gcc warning */
}

References expression_normalized, is_normalized_complex, is_normalized_linear, NORMALIZE_EXPRESSION, normalized_linear, normalized_tag, normalized_undefined_p, pips_internal_error, TCST, VALUE_TO_INT, vect_coeff(), vect_del_var(), vect_rm(), and vect_size().

Referenced by align_check(), compute_entity_to_declaration_constraints(), empty_range_p(), fprint_range(), lrange_larger_p(), safe_static_domain_bound(), and sprint_range().

Here is the call graph for this function:

Here is the caller graph for this function:

local_integer_constant_expression()

bool local_integer_constant_expression

(

expression

e

)

true is the expression is locally constant, that is in the whole loop nest, the reference is not written.

??? not very portable thru pips...

Definition at line 64 of file align-checker.c.

{
    syntax s = expression_syntax(e);
 
    if ((syntax_reference_p(s)) &&
        (normalized_linear_p(expression_normalized(e))))
    {
        entity ent = reference_variable(syntax_reference(s));
        if (write_on_entity_p(ent)) return false;
    }
    
    return true;
}

References expression_normalized, expression_syntax, normalized_linear_p, reference_variable, syntax_reference, syntax_reference_p, and write_on_entity_p().

Referenced by align_check(), and simple_indices_p().

Here is the call graph for this function:

Here is the caller graph for this function:

shift_expression_of_loop_index_p()

static bool shift_expression_of_loop_index_p ( expression  e, entity *  pe, int *  pi  )

static

true if the expression is shift function of a loop nest index.

just to avoid a gcc warning

Definition at line 82 of file align-checker.c.

{
    normalized n = expression_normalized(e);
 
    pips_assert("normalized", !normalized_undefined_p(n));
 
    switch (normalized_tag(n))
    {
    case is_normalized_complex:
        return(false);
        break;
    case is_normalized_linear:
    {
        Pvecteur v = normalized_linear(n), vp = vect_del_var(v, TCST);
        int s = vect_size(vp);
        bool result;
 
        if (s!=1) return false;
 
        result = entity_loop_index_p((entity)var_of(vp)) && 
            value_one_p(val_of(vp));
 
        if (result) 
        {
            Value vi = vect_coeff(TCST, v);
            *pe = (entity) var_of(vp);
            *pi = VALUE_TO_INT(vi);
        }
 
        vect_rm(vp);
 
        return result;
        break;
    }
    default:
        pips_internal_error("unexpected normalized tag");
        break;
    }
    
    return false; /* just to avoid a gcc warning */
}

References entity_loop_index_p(), expression_normalized, is_normalized_complex, is_normalized_linear, normalized_linear, normalized_tag, normalized_undefined_p, pips_assert, pips_internal_error, TCST, val_of, value_one_p, VALUE_TO_INT, var_of, vect_coeff(), vect_del_var(), vect_rm(), and vect_size().

Referenced by align_check().

Here is the call graph for this function:

Here is the caller graph for this function:

write_on_entity_p()

static bool write_on_entity_p ( entity  e )

static

Definition at line 50 of file align-checker.c.

{
    MAP(REGION, r,
        if (region_entity(r)==e && region_write_p(r)) return true,
        load_statement_local_regions(get_hpfc_current_statement()));
 
    return false;
}

References get_hpfc_current_statement(), load_statement_local_regions(), MAP, REGION, region_entity, and region_write_p.

Referenced by local_integer_constant_expression().

Here is the call graph for this function:

Here is the caller graph for this function: