binaires.c File Reference

#include <stdio.h>
#include "linear_assert.h"
#include <limits.h>
#include "boolean.h"
#include "arithmetique.h"
#include "vecteur.h"

Include dependency graph for binaires.c:

Go to the source code of this file.

Functions
Pvecteur	vect_add (Pvecteur v1, Pvecteur v2)
	package vecteur - operations binaires More...
Pvecteur	vect_substract (Pvecteur v1, Pvecteur v2)
	Pvecteur vect_substract(Pvecteur v1, Pvecteur v2): allocation d'un vecteur v dont la valeur est la difference des deux vecteurs v1 et v2. More...
Pvecteur	vect_substitute_dimension (Pvecteur v, Variable i, Pvecteur s)
	Pvecteur vect_substitute_dimension(Pvecteur v, Variable i, Pvecteur s) More...
Pvecteur	vect_cl_ofl_ctrl (Pvecteur v, Value lambda, Pvecteur u, int ofl_ctrl)
	Pvecteur vect_cl_ofl_ctrl(Pvecteur v, Value lambda, Pvecteur u, int ofl_ctrl): etape d'acculumulation dans une combinaison lineaire; aucun sharing entre v et u n'est cree (allocation implicite) Le controle de l'overflow est effectue et traite par le retour du contexte correspondant au dernier CATCH(overflow_error) effectue. More...
Pvecteur	vect_cl_ofl (Pvecteur v, Value lambda, Pvecteur u)
Pvecteur	vect_cl (Pvecteur v, Value lambda, Pvecteur u)
Pvecteur	vect_cl2_ofl_ctrl (Value x1, Pvecteur v1, Value x2, Pvecteur v2, int ofl_ctrl)
	Pvecteur vect_cl2_ofl(Value x1, Pvecteur v1, Value x2, Pvecteur v2): allocation d'un vecteur v dont la valeur est la combinaison lineaire des deux vecteurs v1 et v2 avec les coefficients respectifs x1 et x2 Le controle de l'overflow est effectue par vect_cl_ofl et traite par le retour du contexte correspondant au dernier CATCH(overflow_error) effectue. More...
Pvecteur	vect_cl2_ofl (Value x1, Pvecteur v1, Value x2, Pvecteur v2)
Pvecteur	vect_cl2 (Value x1, Pvecteur v1, Value x2, Pvecteur v2)
Pvecteur	vect_subst (Variable v, Pvecteur v1, Pvecteur v2)
	Pvecteur vect_subst(Variable v, Pvecteur v1, Pvecteur v2): calcul d'un vecteur v3 tel que l'intersection des hyperplans definis par v1 et v2 soit egale a l'intersection des hyperplans definis par v1 et v3, et que v appartiennent a l'hyperplan defini par v3. More...

Function Documentation

vect_add()

Pvecteur vect_add	(	Pvecteur	v1,
		Pvecteur	v2
	)

package vecteur - operations binaires

binaires.c

INTLIBRARY Pvecteur vect_add(Pvecteur v1, Pvecteur v2): allocation d'un vecteur v dont la valeur est la somme des deux vecteurs v1 et v2

     ->

allocate v; -> -> -> v := v1 + v2; -> return v;

RT: j'ai besoin d'un vect_add a effet de bord pour la normalisation d'expression lineaire. idem pour vect_substract, vect_mult, ...

Parameters

v1	1
v2	2

Definition at line 53 of file binaires.c.

{
    Pvecteur v = vect_dup (v1);
 
    for ( ; v2!= NULL; v2=v2->succ)
        vect_add_elem (&v,var_of(v2),val_of(v2));
 
    return (v);
}

References Svecteur::succ, val_of, var_of, vect_add_elem(), and vect_dup().

Referenced by adg_dataflowgraph(), adg_max_of_leaves(), align_check(), analyze_expression(), array_indices_communication(), bounds_equal_p(), broadcast_of_dataflow(), build_list_of_min(), build_sc_machine(), build_third_comb(), c_convex_effects_on_actual_parameter_forward_translation(), contrainte_parallele(), count_eq_occ(), dj_system_complement(), do_gather_all_expressions_perms(), eq_in_ineq(), expression_equal_in_context_p(), expression_less_than_in_context(), find_implicit_equation(), find_pattern(), generate_one_message(), include_trans_on_LC_in_ref(), invariant_vector_p(), loop_index_domaine_to_contrainte(), loop_nest_to_wp65_code(), make_datum_movement(), make_dual(), make_lin_op_exp(), make_load_blocks(), make_movements_loop_body_wp65(), make_store_blocks(), matrices_to_loop_sc(), matrix_to_system(), MergeLinExprs(), monome_monome_mult(), my_vect_var_subst(), normalize_intrinsic(), NormalizeIntrinsic(), one_message_guards_and_neighbour(), pa_path_to_few_disjunct_ofl_ctrl(), parallel_tiling(), sc_elim_double_constraints(), sc_transform_ineg_in_eg(), simplify_constraint_with_bounding_box(), simplify_dimension(), simplify_float_constraint(), simplify_predicate(), system_new_var_subst(), tiling_transformation(), update_basis(), vect_change_base(), and vect_var_subst().

Here is the call graph for this function:

vect_cl()

Pvecteur vect_cl	(	Pvecteur	v,
		Value	lambda,
		Pvecteur	u
	)

Parameters

lambda

ambda

Definition at line 181 of file binaires.c.

{
    return vect_cl_ofl_ctrl(v, lambda, u, NO_OFL_CTRL);
}

References NO_OFL_CTRL, and vect_cl_ofl_ctrl().

Referenced by add_loop_index_exit_value(), constraints_eliminate_constant_terms(), and vect_substitute_dimension().

Here is the call graph for this function:

Here is the caller graph for this function:

vect_cl2()

Pvecteur vect_cl2	(	Value	x1,
		Pvecteur	v1,
		Value	x2,
		Pvecteur	v2
	)

Parameters

x1	1
v1	1
x2	2
v2	2

Definition at line 247 of file binaires.c.

{
    return(vect_cl2_ofl_ctrl(x1,v1,x2,v2, NO_OFL_CTRL));
}

References NO_OFL_CTRL, and vect_cl2_ofl_ctrl().

Referenced by find_pattern(), lower_bound_generation(), upper_bound_generation(), and vect_subst().

Here is the call graph for this function:

Here is the caller graph for this function:

vect_cl2_ofl()

Pvecteur vect_cl2_ofl	(	Value	x1,
		Pvecteur	v1,
		Value	x2,
		Pvecteur	v2
	)

Parameters

x1	1
v1	1
x2	2
v2	2

Definition at line 238 of file binaires.c.

{
    return(vect_cl2_ofl_ctrl(x1,v1,x2,v2, FWD_OFL_CTRL));
}

References FWD_OFL_CTRL, and vect_cl2_ofl_ctrl().

Here is the call graph for this function:

vect_cl2_ofl_ctrl()

Pvecteur vect_cl2_ofl_ctrl	(	Value	x1,
		Pvecteur	v1,
		Value	x2,
		Pvecteur	v2,
		int	ofl_ctrl
	)

Pvecteur vect_cl2_ofl(Value x1, Pvecteur v1, Value x2, Pvecteur v2): allocation d'un vecteur v dont la valeur est la combinaison lineaire des deux vecteurs v1 et v2 avec les coefficients respectifs x1 et x2 Le controle de l'overflow est effectue par vect_cl_ofl et traite par le retour du contexte correspondant au dernier CATCH(overflow_error) effectue.

-> allocate v; -> -> -> v := x1 v1 + x2 v2; -> return v;

le bout de l'horreur sur ces vecteurs creux dont les composantes ne sont pas triees; Malik a essaye d'eviter les allocations inutiles en "marquant" les coefficients de v2 qui ont ete vus lors du parcours des coefficients non-nuls de v1; puis il ajoute a ce premier resultat la partie de x2 v2 qui n'a pas encore ete prise en compte parce que le coefficient correspondant dans v1 etait nul;

la variable de nom 0 est traitee a part car la procedure de marquage (multiplication par -1) ne la marque pas

Une autre solution, presque aussi efficace, consisterait a allouer et calculer x1 v1 puis a y ajouter x2 v2 a coups de vect_add_elem; on n'a pas de procedure faisant simultanement l'allocation et la multiplication par un scalaire; on n'a pas de procedure faisant l'addition sans allocation (accumulation);

Francois Irigoin, 2 juin 1989

Parameters

x1	1
v1	1
x2	2
v2	2
ofl_ctrl	fl_ctrl

Definition at line 204 of file binaires.c.

{
    /* le bout de l'horreur sur ces vecteurs creux dont les composantes ne
       sont pas triees; Malik a essaye d'eviter les allocations inutiles
       en "marquant" les coefficients de v2 qui ont ete vus lors du parcours
       des coefficients non-nuls de v1; puis il ajoute a ce premier resultat
       la partie de x2 v2 qui n'a pas encore ete prise en compte parce
       que le coefficient correspondant dans v1 etait nul;
 
       la variable de nom 0 est traitee a part car la procedure de
       marquage (multiplication par -1) ne la marque pas
 
       Une autre solution, presque aussi efficace, consisterait a
       allouer et calculer x1 v1 puis a y ajouter x2 v2 a coups
       de vect_add_elem; on n'a pas de procedure faisant simultanement
       l'allocation et la multiplication par un scalaire; on n'a pas
       de procedure faisant l'addition sans allocation (accumulation);
 
       Francois Irigoin, 2 juin 1989 */
 
    Pvecteur v = NULL;
    
    v = vect_cl_ofl_ctrl(v,x1,v1, ofl_ctrl);
    v = vect_cl_ofl_ctrl(v,x2,v2, ofl_ctrl);
 
    return(v);
}

References vect_cl_ofl_ctrl().

Referenced by compose_vvs(), contrainte_subst_ofl_ctrl(), elim_var_with_eg(), inegalite_comb_ofl_ctrl(), my_substitute_var_with_vec(), plc_elim_var_with_eg(), plc_make_vvs_with_vector(), sc_to_vvs(), substitute_var_with_vec(), valuer(), vect_cl2(), vect_cl2_ofl(), and vvs_on_vvs().

Here is the call graph for this function:

Here is the caller graph for this function:

vect_cl_ofl()

Pvecteur vect_cl_ofl	(	Pvecteur	v,
		Value	lambda,
		Pvecteur	u
	)

Parameters

lambda

ambda

Definition at line 173 of file binaires.c.

{
    return vect_cl_ofl_ctrl(v, lambda, u, FWD_OFL_CTRL);
}

References FWD_OFL_CTRL, and vect_cl_ofl_ctrl().

Here is the call graph for this function:

vect_cl_ofl_ctrl()

Pvecteur vect_cl_ofl_ctrl	(	Pvecteur	v,
		Value	lambda,
		Pvecteur	u,
		int	ofl_ctrl
	)

Pvecteur vect_cl_ofl_ctrl(Pvecteur v, Value lambda, Pvecteur u, int ofl_ctrl): etape d'acculumulation dans une combinaison lineaire; aucun sharing entre v et u n'est cree (allocation implicite) Le controle de l'overflow est effectue et traite par le retour du contexte correspondant au dernier CATCH(overflow_error) effectue.

-> -> -> v := v + lambda u; -> return v;

Modifications:

• exploitation des lambdas 1 et -1; ca rallonge mechamment le code; non teste; u est casse mais en principe ce n'est pas grave car il n'est utilise qu'une seule fois (Francois Irigoin, 26/03/90)
• add the cu variable to avoid side effects on parameter u; (Francois Irigoin, 17 December 1991)
• add assert() to try to avoid most integer overflow; this is likely to (uselessly) slow down dependence tests since overflows occur only (?) in code generation phases; (Francois Irigoin, 17 December 1991)

ancienne version for( ;u!=NULL;u=u->succ) v = vect_chain(v,var_of(u),lambda*val_of(u));

== 1

== -1

bof, FC

Parameters

lambda	ambda
ofl_ctrl	fl_ctrl

Definition at line 128 of file binaires.c.

{
    Pvecteur cu;
 
    if(lambda==VALUE_ZERO)
        return v;
    else if(v==NULL) {
        /* ancienne version
         * for( ;u!=NULL;u=u->succ) 
         *   v = vect_chain(v,var_of(u),lambda*val_of(u));
         */
        v = vect_dup(u);
        if (value_notone_p(lambda)) {
            if (value_mone_p(lambda))
                vect_chg_sgn(v);
            else 
                v = vect_multiply(v, lambda);
        }
    }
    else
        if (value_one_p(lambda)) /* == 1 */
            for(cu=u ;cu!=NULL;cu=cu->succ) 
                vect_add_elem(&v, var_of(cu), val_of(cu));
        else if (value_mone_p(lambda)) /* == -1 */
            for(cu=u ;cu!=NULL;cu=cu->succ) 
                vect_add_elem(&v, var_of(cu), value_uminus(val_of(cu)));
        else
            for(cu=u ;cu!=NULL;cu=cu->succ) {
                /* bof, FC */
                Value x = ofl_ctrl!=NO_OFL_CTRL?
                    value_protected_mult(lambda,val_of(cu)):
                    value_mult(lambda,val_of(cu));
 
                vect_add_elem(&v, var_of(cu), x);
            }
    
    return v;
}

References NO_OFL_CTRL, Svecteur::succ, val_of, value_mone_p, value_mult, value_notone_p, value_one_p, value_protected_mult, value_uminus, VALUE_ZERO, var_of, vect_add_elem(), vect_chg_sgn(), vect_dup(), vect_multiply(), and x.

Referenced by calculate_delay(), converti_psysmin_psysmax(), loop_regions_normalize(), put_source_ind(), vect_cl(), vect_cl2_ofl_ctrl(), vect_cl_ofl(), and vvs_on_vecteur().

Here is the call graph for this function:

Here is the caller graph for this function:

vect_subst()

Pvecteur vect_subst	(	Variable	v,
		Pvecteur	v1,
		Pvecteur	v2
	)

Pvecteur vect_subst(Variable v, Pvecteur v1, Pvecteur v2): calcul d'un vecteur v3 tel que l'intersection des hyperplans definis par v1 et v2 soit egale a l'intersection des hyperplans definis par v1 et v3, et que v appartiennent a l'hyperplan defini par v3.

v3 est defini a une constante multiplicative pret et ses coefficients ne sont donc pas necessairement normalises, mais on s'arrange pour multiplier v2 par une constante positive ce qui est utile si v2 represente une inegalite (cf. package contrainte).

-> -> -> -> -> -> -> -> -> -> -> { U / V1 . u = 0 & v2 . u = 0 } = { u / v1 . u = 0 & v3 . u = 0 }

-> -> v3 . v = 0

Si v2 remplit la condition v2 . v = 0, on prend v3 = v2.

Il faut comme precondition a l'appel que v1 . v != 0

Le vecteur v1 est preserve. Le vecteur v2 est detruit. v3 est alloue.

Cette routine peut servir a eliminer une variable entre deux egalites ou inegalites. C'est pourquoi v2 est detruit. Il est destine a etre remplace par v3. Voir contrainte_subst().

ATTENTION: je ne comprends pas a quoi sert le vect_chg_coeff(). F.I. Les commentaires precedent sont donc partiellement (?) faux!!!

cv_v1 = coeff de v dans v1

cv_v2 = coeff de v dans v2

v2 est solution; i.e., substitution non faite: var absente

Parameters

v1	1
v2	2

Definition at line 286 of file binaires.c.

{
    Pvecteur v3;
    /* cv_v1 = coeff de v dans v1 */
    Value cv_v1 = vect_coeff(v,v1);
    /* cv_v2 = coeff de v dans v2 */
    Value cv_v2 = vect_coeff(v,v2);
 
    if (cv_v2==VALUE_ZERO) {
        /* v2 est solution; i.e., substitution non faite: var absente */
        v3 = v2;
    }
    else {
        if (cv_v1<VALUE_ZERO) {
            v3 = vect_cl2(value_uminus(cv_v1),v2,cv_v2,v1);
            vect_chg_coeff(&v3,v,value_uminus(cv_v2));
        }
        else {
            v3 = vect_cl2(cv_v1,v2,value_uminus(cv_v2),v1);
            vect_chg_coeff(&v3,v,cv_v2);
        }
        vect_rm(v2);
    }
    return(v3);
}

References value_uminus, VALUE_ZERO, vect_chg_coeff(), vect_cl2(), vect_coeff(), and vect_rm().

Here is the call graph for this function:

vect_substitute_dimension()

Pvecteur vect_substitute_dimension	(	Pvecteur	v,
		Variable	i,
		Pvecteur	s
	)

Pvecteur vect_substitute_dimension(Pvecteur v, Variable i, Pvecteur s)

Vector v is updated to be equal to M v, where M is the identity matrix except for its ith column that is replaced by s. In other words, the resulting v is v + v_i s - v_i e_i = v + v_i (s - e_i), where e_i is the ith base vector.

Because the transformation is applied to a constraint system, it is better to update s once, and not a this low-level. So this compute v + v_i s.

Vector s is preserved.

Definition at line 99 of file binaires.c.

{
  Value v_i = vect_coeff(i, v);
  //vect_add_elem(s, i, VALUE_MONE);
  v = vect_cl(v, v_i, s);
  return v;
}

References vect_cl(), and vect_coeff().

Referenced by contrainte_substitute_dimension().

Here is the call graph for this function:

Here is the caller graph for this function:

vect_substract()

Pvecteur vect_substract	(	Pvecteur	v1,
		Pvecteur	v2
	)

Pvecteur vect_substract(Pvecteur v1, Pvecteur v2): allocation d'un vecteur v dont la valeur est la difference des deux vecteurs v1 et v2.

     ->

allocate v; -> -> -> v := v1 - v2; -> return v;

Parameters

v1	1
v2	2

Definition at line 75 of file binaires.c.

{
    Pvecteur v = vect_dup (v1);
 
    for (; v2 != NULL; v2 = v2->succ)
         vect_add_elem (&v,var_of(v2),value_uminus(val_of(v2)));
 
    return (v);
}

References Svecteur::succ, val_of, value_uminus, var_of, vect_add_elem(), and vect_dup().

Referenced by add_declaration_list_information(), add_loop_index_exit_value(), add_loop_skip_condition(), add_reference_information(), adg_dataflowgraph(), adg_dataflowgraph_with_extremities(), adg_get_predicate_of_loops(), adg_max_of_leaves(), affine_to_transformer(), analyze_expression(), build_contraction_matrices(), build_sc_with_several_uniform_ref(), c_convex_effects_on_actual_parameter_forward_translation(), calculate_delay(), check_range_wrt_precondition(), comp_exec_domain(), count_eq_occ(), expression_equal_in_context_p(), expression_flt(), expression_less_than_in_context(), free_guards(), gcd_and_constant_dependence_test(), include_trans_on_LC_in_ref(), loop_executed_approximation(), make_array_bounds(), make_lin_op_exp(), monome_monome_div(), my_matrices_to_constraints_with_sym_cst(), normalize_intrinsic(), NormalizeIntrinsic(), pip_solve(), pip_solve_min_with_big(), sc_elim_double_constraints(), simple_affine_to_transformer(), simplify_dimension(), simplify_predicate(), simplify_relational_expression(), subarray_shift_assignment_p(), top_down_abc_dimension(), transformer_add_integer_relation_information(), trivial_expression_p(), try_reorder_expression_call(), and uniform_dependence_p().

Here is the call graph for this function:

Here is the caller graph for this function: