hyperplane.h File Reference

#include "matrice.h"

Include dependency graph for hyperplane.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros
#define	HYPERPLANE_OPTIONS   "X"
	Warning! Do not modify this file that is automatically generated! More...

Functions
statement	hyperplane (list, bool(*)(statement))
	cproto-generated files More...
bool	interactive_hyperplane_direction (Value *, int)
	hyperplane_direction.c More...
void	scanning_base_hyperplane (Value[], int, matrice)
	scanning_base.c More...
void	base_G_h1_unnull (Value[], int, matrice)
void	global_parallelization (const char *)
	global_parallelization.c More...
bool	loop_hyperplane (const char *)
statement	code_generation (list, Pvecteur[], Pbase, Pbase, Psysteme, bool)
	code_generation.c More...
bool	static_partitioning_matrix (matrice, int, const char *)
	tiling.c More...
bool	interactive_partitioning_matrix (matrice, int)
	Query the user for a partitioning matrix P. More...
Psysteme	tile_hyperplane_constraints (Pbase, Pbase, matrice, Pvecteur)
	Generate the tile membership constraints between a tile coordinates and an iteration coordinate. More...
Psysteme	local_tile_constraints (Pbase, Pbase, Psysteme, matrice, Pvecteur *, statement)
Pvecteur	loop_nest_to_offset (list)
statement	tiling_transformation (list, bool(*)(statement))
bool	loop_tiling (const char *)
bool	check_tiling_legality (statement, matrice, int)
Psysteme	sc_projection_concat_proj_on_variables (Psysteme, Pbase)
statement	parallel_tiling (list, bool(*)(statement))
bool	parallel_loop_tiling (const char *)
void	do_symbolic_tiling (statement, list)
	symbolic_tiling.c More...
bool	symbolic_tiling (const char *)
int	loop_unimodular (string)
	unimodular.c More...

Macro Definition Documentation

HYPERPLANE_OPTIONS

#define HYPERPLANE_OPTIONS   "X"

Warning! Do not modify this file that is automatically generated!

Modify src/Libs/hyperplane/hyperplane-local.h instead, to add your own modifications. header file built by cproto hyperplane-local.h package hyperplane

Definition at line 34 of file hyperplane.h.

Function Documentation

base_G_h1_unnull()

void base_G_h1_unnull	(	Value	[],
		int	,
		matrice
	)

check_tiling_legality()

bool check_tiling_legality	(	statement	loopnest_st,
		matrice	H,
		int	dim
	)

Parameters

loopnest_st	oopnest_st
dim	im

Definition at line 812 of file tiling.c.

{
  const char * module_name = get_current_module_name();
  graph dg = (graph) db_get_memory_resource(DBR_DG, module_name, true);
   int bl;
   matrice HC;
  // statement mod_stat = get_current_module_statement();
  bool legal=true;
  FOREACH(VERTEX,v,graph_vertices(dg)) {
    statement s = vertex_to_statement(v);
    // Verify s is a statement in the loop nest
    statement_in_loopnest_p= false;
    test_statement_of_reference = s;
    gen_recurse(loopnest_st, statement_domain, gen_true,statement_in_loopnest);
        
    if(statement_in_loopnest_p) {
      FOREACH(SUCCESSOR,su,vertex_successors(v)) {
              
        vertex v2 = successor_vertex(su);
        statement s2 = vertex_to_statement( v2 );
        // Verify s2 is a statement in the loop nest      
        statement_in_loopnest_p= false;
        test_statement_of_reference = s2;
        gen_recurse(loopnest_st, statement_domain, gen_true,statement_in_loopnest);
        
        if(statement_in_loopnest_p) { // s and s2 are in the loop nest
          FOREACH(CONFLICT,c,dg_arc_label_conflicts(successor_arc_label(su))) {
                       
            if ( conflict_cone(c) != cone_undefined ) {
              //test H.D >0 for sommets, rays, and lines            
              Ptsg gs = (Ptsg) cone_generating_system(conflict_cone(c));
              if( !SG_UNDEFINED_P(gs)) {
                Pbase b=gs->base;
                bl=vect_size(b);
                
                if (bl==dim)
                  check_positive_dependence(gs, H,dim, &legal);
                else {
                  if (bl > dim) {
                    HC=matrice_new(bl,bl);
                    int row,col;
                    ifdebug(8) {
                      fprintf(stdout," Different SIZES for base %d and matrice %d, Partial tiling case ?\n",bl,dim);
                    }
                    // Complete matrix Ht for the first non tiled dimension of the loop nest
                    // for 1<=i<=bl-dim, if di!=0  hji>=loop increment
                    // only loop with increment 1 are tiled ==> hji =1
                    matrice_identite(HC,bl,0);
                    DENOMINATOR(HC)=DENOMINATOR(H);
                    for (row=1; row<=bl; row++) {
                      if (row>=bl-dim+1) {
                        for(col=1;  col<bl-dim+1;col++) {
                          ACCESS(HC, bl, row, col)=DENOMINATOR(H) ;
                        }
                        for(col=bl-dim+1;  col<=bl;col++) {
                          ACCESS(HC, bl, row, col)= ACCESS(H, dim, row-bl+dim, col-bl+dim);
                        }
                      }
                      else {
                        ACCESS(HC, bl, row, row)=DENOMINATOR(H);
                      }
                    }
                    check_positive_dependence(gs, HC,bl, &legal);
                    matrice_free(HC);
                  }
                  else
                    pips_user_warning(" Different SIZES for dependence cone basis %d and partitioning matrice %d\n",bl,dim);
                }
              }
            }
          }
        }
      }
    }
  }
  return(legal);
}

References ACCESS, type_sg::base, check_positive_dependence(), cone_generating_system, cone_undefined, CONFLICT, conflict_cone, db_get_memory_resource(), DENOMINATOR, dg, dg_arc_label_conflicts, FOREACH, fprintf(), gen_recurse, gen_true(), get_current_module_name(), graph_vertices, ifdebug, matrice_free, matrice_identite(), matrice_new, module_name(), pips_user_warning, SG_UNDEFINED_P, statement_domain, statement_in_loopnest(), statement_in_loopnest_p, SUCCESSOR, successor_arc_label, successor_vertex, test_statement_of_reference, vect_size(), VERTEX, vertex_successors, and vertex_to_statement().

Referenced by local_tile_constraints(), and parallel_tiling().

Here is the call graph for this function:

Here is the caller graph for this function:

code_generation()

statement code_generation	(	list	lls,
		Pvecteur	pvg[],
		Pbase	base_oldindex,
		Pbase	base_newindex,
		Psysteme	sc_newbase,
		bool	preserve_entry_label_p
	)

code_generation.c

code_generation.c

include <sys/stdtypes.h> for debug with dbmalloc include "stdlib.h" statement code_generation(cons *lls,Pvecteur pvg[], Pbase base_oldindex, Pbase base_newindex) generation of hyperplane code for the nested loops (cons *lls). the new nested loops will be ; DOSEQ Ip = ... DOALL Jp = ... DOALL Kp = ... ... ENDDO

modification : Keep the code in the sequential version. Let the parallelisation to generate the parallel code. suggested by BB, modified by Yi-Qing. 17/05/92

make the parallel loops from inner loop to outermost loop

handling of current loop

new bounds for new index related to the old index of the old loop

FI: I do not understand how you could keep a go to target (!) or a list of local variables

Parameters

lls	ls
pvg	vg
base_oldindex	ase_oldindex
base_newindex	ase_newindex
sc_newbase	c_newbase
preserve_entry_label_p	reserve_entry_label_p

Definition at line 58 of file code_generation.c.

{
    statement state_lhyp = statement_undefined;
    instruction instr_lhyp = instruction_undefined;
    loop l_hyp = loop_undefined;
    range rl = range_undefined;
    expression lower = expression_undefined;
    expression upper = expression_undefined;
    statement bl = statement_undefined; 
    statement s_loop = statement_undefined;
    Pbase pb = BASE_UNDEFINED;
 
    bl = loop_body(instruction_loop(statement_instruction(STATEMENT(CAR(lls)))));
    statement_newbase(bl,pvg,base_oldindex);
    /* make the parallel loops from inner loop to outermost loop*/
 
    for(pb=base_reversal(base_newindex);lls!=NIL; lls=CDR(lls), pb = pb->succ) {
        /* handling of current loop */
        s_loop = STATEMENT(CAR(lls));
 
        /* new bounds for new index related to the old index of the old loop*/
        make_bound_expression(pb->var, base_newindex,sc_newbase, &lower, &upper);
        rl = make_range(lower, upper, int_to_expression(1));
 
        /*
    loop l_old = loop_undefined;
        l_old = instruction_loop(statement_instruction(s_loop));
        l_hyp = make_loop((entity) pb->var,
                          rl,
                          bl,
                          loop_label(l_old),
                          make_execution(is_execution_sequential,UU),
                          loop_locals(l_old));
        */
 
        /* FI: I do not understand how you could keep a go to target (!)
         * or a list of local variables
         */
        l_hyp = make_loop((entity) pb->var,
                          rl,
                          bl,
                          entity_empty_label(),
                          make_execution(is_execution_sequential,UU),
                          NIL);
 
        bl = makeloopbody(l_hyp, s_loop, true);
    }
    
    instr_lhyp = make_instruction(is_instruction_loop,l_hyp);
    state_lhyp = copy_statement(s_loop);
    if(!preserve_entry_label_p)
      clear_label(state_lhyp);
    free_instruction(statement_instruction(state_lhyp));
    statement_instruction(state_lhyp) = instr_lhyp;
    return(state_lhyp);
}

References base_reversal(), BASE_UNDEFINED, CAR, CDR, clear_label(), copy_statement(), entity_empty_label(), expression_undefined, free_instruction(), instruction_loop, instruction_undefined, int_to_expression(), is_execution_sequential, is_instruction_loop, loop_body, loop_undefined, make_bound_expression(), make_execution(), make_instruction(), make_loop(), make_range(), makeloopbody(), NIL, range_undefined, sc_newbase, STATEMENT, statement_instruction, statement_newbase(), statement_undefined, Svecteur::succ, UU, and Svecteur::var.

Referenced by hyperplane(), parallel_tiling(), tiling_transformation(), and unimodular().

Here is the call graph for this function:

Here is the caller graph for this function:

do_symbolic_tiling()

void do_symbolic_tiling	(	statement	base,
		list	vector
	)

symbolic_tiling.c

check if tile_size is modified by sloop and generate a temporary variable if needed

we should also check tile_size has no write effect but currently, string_to_expression asserts this

outer loop new index

inner loop

outer loop

will help partial_eval

save

go on for the next one

once we are done, regenerate the whole thing

prepare chain all

set tail

chain all

update

he label have been duplicated by copy_statement

fix signed / unsigned types for further processing otherwise we could end with integer overflow

Parameters

base	ase
vector	ector

Definition at line 64 of file symbolic_tiling.c.

{
    list effects = load_cumulated_rw_effects_list(base);
    list tiled_loops_outer = NIL;
    list tiled_loops_inner = NIL;
    list prelude = NIL;
    statement sloop=copy_statement(base);
    set_conflict_testing_properties();
    FOREACH(EXPRESSION,tile_size,vector)
    {
        loop l = statement_loop(sloop);
        list tile_expression_effects = proper_effects_of_expression(tile_size);
        /* check if tile_size is modified by sloop and generate a temporary variable if needed */
        /* we should also check tile_size has no write effect
         * but currently, string_to_expression asserts this */
        FOREACH(EFFECT,teff,tile_expression_effects) {
            FOREACH(EFFECT,eff,effects) {
                if(effect_write_p(eff) && 
                        references_may_conflict_p(effect_any_reference(teff),effect_any_reference(eff)))
                {
                    entity etemp = make_new_scalar_variable(get_current_module_entity(),make_basic_int(DEFAULT_INTEGER_TYPE_SIZE));
                    AddEntityToCurrentModule(etemp);
                    statement ass = make_assign_statement(entity_to_expression(etemp),copy_expression(tile_size));
                    update_expression_syntax(tile_size,make_syntax_reference(make_reference(etemp,NIL)));
                    prelude=CONS(STATEMENT,ass,prelude);
                    goto generate_tile;
                }
            }
        }
generate_tile:;
        /* outer loop new index */
        entity index = make_new_scalar_variable(get_current_module_entity(),make_basic_int(DEFAULT_INTEGER_TYPE_SIZE));
        AddEntityToCurrentModule(index);
        expression lower_bound = 
            make_op_exp(MULTIPLY_OPERATOR_NAME,
                    entity_to_expression(index),
                    copy_expression(tile_size)
                    );
        expression upperbound_lhs = copy_expression(range_upper(loop_range(l)));
        expression upperbound_rhs = 
            make_op_exp(PLUS_OPERATOR_NAME,
                    copy_expression(lower_bound),
                    make_op_exp(MINUS_OPERATOR_NAME,
                        copy_expression(tile_size),
                        int_to_expression(1)
                        )
                    );
 
        expression upper_bound = 
            binary_intrinsic_expression(MIN_OPERATOR_NAME,
                    upperbound_lhs,
                    upperbound_rhs
                    );
 
        /* inner loop */
        statement inner = instruction_to_statement(
                make_instruction_loop(
                    make_loop(
                        loop_index(l),
                        make_range(
                            lower_bound,
                            upper_bound,
                            int_to_expression(1)
                            ),
                        statement_undefined,
                        entity_empty_label(),
                        make_execution_parallel(),
                        NIL
                        )
                    )
                );
        /* outer loop */
        statement outer = sloop;
        loop_index(l)=index;
        //range_increment(loop_range(l))=copy_expression(tile_size);
        /* will help partial_eval */
        range_upper(loop_range(l))=
            make_op_exp(DIVIDE_OPERATOR_NAME,
                    range_upper(loop_range(l)),
                    copy_expression(tile_size)
                    );
        /* save */
        tiled_loops_outer=CONS(STATEMENT,outer,tiled_loops_outer);
        tiled_loops_inner=CONS(STATEMENT,inner,tiled_loops_inner);
 
        /* go on for the next one */
        sloop=loop_body(l);
    }
    /* once we are done, regenerate the whole thing */
 
    /* prepare chain all */
    tiled_loops_inner=gen_append(tiled_loops_inner,tiled_loops_outer);
    statement last = STATEMENT(CAR(tiled_loops_inner));
    statement prev = last;
    POP(tiled_loops_inner);
    /* set tail */
    loop_body(statement_loop(last))=sloop;
    /* chain all */
    FOREACH(STATEMENT,curr,tiled_loops_inner) {
        loop_body(statement_loop(curr))=prev;
        prev=curr;
    }
 
    /* update */
    statement_label(base)=entity_empty_label();/*the label have been duplicated by copy_statement */
    statement_instruction(base)=instruction_undefined;
    update_statement_instruction(base,make_instruction_block(gen_nreverse(CONS(STATEMENT,prev,prelude))));
    clean_up_sequences(base);
 
    /* fix signed / unsigned types for further processing otherwise we could end with integer overflow */
    gen_recurse(base, loop_domain, gen_true, fix_loop_index_sign);
}

References AddEntityToCurrentModule(), base, binary_intrinsic_expression, CAR, clean_up_sequences(), CONS, copy_expression(), copy_statement(), DEFAULT_INTEGER_TYPE_SIZE, DIVIDE_OPERATOR_NAME, EFFECT, effect_any_reference, effect_write_p, entity_empty_label(), entity_to_expression(), EXPRESSION, fix_loop_index_sign(), FOREACH, gen_append(), gen_nreverse(), gen_recurse, gen_true(), get_current_module_entity(), instruction_to_statement(), instruction_undefined, int_to_expression(), load_cumulated_rw_effects_list(), loop_body, loop_domain, loop_index, loop_range, make_assign_statement(), make_basic_int(), make_execution_parallel(), make_instruction_block(), make_instruction_loop(), make_loop(), make_new_scalar_variable(), make_op_exp(), make_range(), make_reference(), make_syntax_reference(), MIN_OPERATOR_NAME, MINUS_OPERATOR_NAME, MULTIPLY_OPERATOR_NAME, NIL, PLUS_OPERATOR_NAME, POP, proper_effects_of_expression(), range_upper, references_may_conflict_p(), set_conflict_testing_properties(), STATEMENT, statement_instruction, statement_label, statement_loop(), statement_undefined, update_expression_syntax(), and update_statement_instruction().

Referenced by do_simdizer_auto_tile_generate_all_tests(), and symbolic_tiling().

Here is the call graph for this function:

Here is the caller graph for this function:

global_parallelization()

void global_parallelization

(

const char *

module_name

)

global_parallelization.c

Parameters

module_name

odule_name

Definition at line 51 of file global_parallelization.c.

{
    entity module = local_name_to_top_level_entity(module_name);
    statement s;
 
    pips_assert("global_parallelization", entity_module_p(module));
    s = (statement) db_get_memory_resource(DBR_CODE, module_name, false);
        
    debug_on("HYPERPLANE_DEBUG_LEVEL");
 
    look_for_nested_loop_statements(s, hyperplane, always_select);
 
    debug_off();
 
    module_reorder(s);
 
    DB_PUT_MEMORY_RESOURCE(DBR_CODE, 
                           strdup(module_name), 
                           (char*) s);
}

References always_select(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, entity_module_p(), hyperplane(), local_name_to_top_level_entity(), look_for_nested_loop_statements(), module, module_name(), module_reorder(), pips_assert, and strdup().

Here is the call graph for this function:

hyperplane()

statement hyperplane	(	list	,
		bool(*)(statement)
	)

cproto-generated files

hyperplane.c

interactive_hyperplane_direction()

bool interactive_hyperplane_direction	(	Value *	h,
		int	n
	)

hyperplane_direction.c

hyperplane_direction.c

In a first phase, trust the user blindly!

Query the user for h's coordinates

Definition at line 40 of file hyperplane_direction.c.

{
    int i;
    int n_read;
    string resp = string_undefined;
    string cn = string_undefined;
    bool return_status = false;
 
    /* Query the user for h's coordinates */
    pips_assert("hyperplane_direction", n>=1);
    debug(8, "interactive_hyperplane_direction", "Reading h\n");
    resp = user_request("Hyperplane direction vector?\n"
                        "(give all its integer coordinates on one line): ");
    if (resp[0] == '\0') {
        user_log("Hyperplane loop transformation has been cancelled.\n");
        return_status = false;
    }
    else {    
        cn = strtok(resp, " \t");
 
        return_status = true;
        for( i = 0; i<n; i++) {
            if(cn==NULL) {
                user_log("Not enough coordinates. "
                         "Hyperplane loop transformation has been cancelled.\n");
                return_status = false;
                break;
            }
            n_read = sscanf(cn," " VALUE_FMT, h+i);
            if(n_read!=1) {
                user_log("Not enough coordinates. "
                         "Hyperplane loop transformation has been cancelled.\n");
                return_status = false;
                break;
            }
            cn = strtok(NULL, " \t");
        }
    }
 
    if(cn!=NULL) {
        user_log("Too many coordinates. "
                 "Hyperplane loop transformation has been cancelled.\n");
        return_status = false;
    }
 
    ifdebug(8) {
        if(return_status) {
            pips_debug(8, "Hyperplane direction vector:\n");
            for( i = 0; i<n; i++) {
                (void) fprintf(stderr," " VALUE_FMT, *(h+i));
            }
            (void) fprintf(stderr,"\n");
            pips_debug(8, "End\n");
        }
        else {
            pips_debug(8, "Ends with failure\n");
        }
    }
 
    return return_status;
}

References debug(), fprintf(), ifdebug, pips_assert, pips_debug, string_undefined, user_log(), user_request(), and VALUE_FMT.

Referenced by hyperplane().

Here is the call graph for this function:

Here is the caller graph for this function:

interactive_partitioning_matrix()

bool interactive_partitioning_matrix	(	matrice	P,
		int	n
	)

Query the user for a partitioning matrix P.

Query the user for P's components

Definition at line 137 of file tiling.c.

{
    int n_read;
    string resp = string_undefined;
    string cn = string_undefined;
    bool return_status = false;
    int row;
    int col;
 
    DENOMINATOR(P) = VALUE_ONE;
    /* Query the user for P's components */
    pips_assert("interactive_partitioning_matrix", n>=1);
    debug(8, "interactive_partitioning_matrix", "Reading P\n");
 
    for(row=1; row<=n; row++) {
        resp = user_request("Partitioning matrix (%dx%d)?\n"
                            "(give all its integer coordinates on one line of %d per row): ",
                            n, n, n);
        if (resp[0] == '\0') {
            user_log("Tiling loop transformation has been cancelled.\n");
            return_status = false;
        }
        else {    
            cn = strtok(resp, " \t");
 
            return_status = true;
            for( col = 1; col<=n; col++) {
                if(cn==NULL) {
                    user_log("Too few coordinates. "
                             "Tiling loop transformation has been cancelled.\n");
                    return_status = false;
                    break;
                }
                n_read = sscanf(cn," " VALUE_FMT, &ACCESS(P, n, row, col));
                if(n_read!=1) {
                    user_log("Too few coordinates. "
                             "Hyperplane loop transformation has been cancelled.\n");
                    return_status = false;
                    break;
                }
                cn = strtok(NULL, " \t");
            }
        }
 
        if(cn!=NULL) {
            user_log("Too many coordinates. "
                     "Tiling loop transformation has been cancelled.\n");
            return_status = false;
        }
    }
 
    ifdebug(8) {
        if(return_status) {
            pips_debug(8, "Partitioning matrix:\n");
            matrice_fprint(stderr, P, n, n);
            (void) fprintf(stderr,"\n");
            pips_debug(8, "End\n");
        }
        else {
            pips_debug(8, "Ends with failure\n");
        }
    }
 
    return return_status;
}

References ACCESS, debug(), DENOMINATOR, fprintf(), ifdebug, matrice_fprint(), pips_assert, pips_debug, string_undefined, user_log(), user_request(), VALUE_FMT, and VALUE_ONE.

Referenced by parallel_tiling(), and tiling_transformation().

Here is the call graph for this function:

Here is the caller graph for this function:

local_tile_constraints()

Psysteme local_tile_constraints	(	Pbase	initial_basis,
		Pbase	local_tile_basis,
		Psysteme	sc,
		matrice	P,
		Pvecteur *	pvch,
		statement	st
	)

computation of the hyperplane tile direction in the tile basis: = sum(hi)= 1H

The local tile direction is legal and colinear to the partitioning vecteur (pdim)

Build the constraints 0 <= det(HT).[HT. (i -i0)]<det(HT).1 with i0=P.G_tile.i_tile <==> 0 <= det(HT).[HT. (i -P.G_tile.i_tile)]<det(HT).1 <==> 0 <= det(HT).[HT.i -G_tile.i_tile]<= det(HT)-1

Parameters

initial_basis	nitial_basis
local_tile_basis	ocal_tile_basis
sc	c
pvch	vch
st	t

Definition at line 407 of file tiling.c.

{
  Psysteme mc = sc_dup(sc),mc2;
  int dim = base_dimension(initial_basis);
  int row;
  int col;
  Pbase civ = BASE_UNDEFINED;
  Pbase ctv = BASE_UNDEFINED;
  Value *h_tile; // hyperplane direction
  int n = dim; 
  matrice V = matrice_new(n,n);
  matrice G_tile = matrice_new(n,n);
  bool legal=false;
  
  pips_assert("The two bases have the same dimension", dim == base_dimension(local_tile_basis));
 
  string local_tile_direction = (string) get_string_property("LOCAL_TILE_DIRECTION");
  if (!empty_string_p(local_tile_direction) && strcmp(local_tile_direction,"LI") != 0) {
    h_tile = (Value*)(malloc(n*sizeof(Value)));
    if(strcmp(local_tile_direction,"LP") == 0) {
      /* computation of the hyperplane tile direction in the tile basis: = sum(hi)= 1H */
      compute_local_change_of_basis(h_tile, P, G_tile, 1 , n, 1);
      matrice_general_inversion(G_tile,V,n);
      legal = check_tiling_legality(st,V,n);
      if (!legal)
        matrice_identite(G_tile,n,0); 
    }
    else // search a valid direction colinear to one of the partitioning vectors
      if(strcmp(local_tile_direction,"LS") == 0) {
        int pdim;
        legal=false;
        for (pdim=1; !legal && pdim<=n; pdim++) {
          /* The local tile direction is legal and colinear to the partitioning vecteur (pdim) */
          compute_local_change_of_basis(h_tile, P, G_tile, 2, n, pdim);
          ifdebug(8) {
            fprintf(stderr,"Check the legality of the chosen LOCAL basis");
            (void) fprintf(stderr,"Temporary local tile scanning base G_tile obtained with %d-th Pvecteur :",pdim);
            matrice_fprint(stderr, G_tile, n, n);
          }
          matrice_general_inversion(G_tile,V,n);
          legal = check_tiling_legality(st,V,n);
        }
        if (pdim>n && !legal)
          matrice_identite(G_tile,n,0);  
      }
  }
  else // the local tile direction is the original basis
    matrice_identite(G_tile,n,0);
  
  ifdebug(8) {
    (void) fprintf(stderr,"The local tile scanning base G_tile - i = G_tile.i_prime is :");
    matrice_fprint(stderr, G_tile, n, n);
  }
  /* Build the constraints
     0 <= det(HT).[HT. (i -i0)]<det(HT).1 with 
     i0=P.G_tile.i_tile
     <==> 0 <= det(HT).[HT. (i -P.G_tile.i_tile)]<det(HT).1
     <==> 0 <= det(HT).[HT.i -G_tile.i_tile]<= det(HT)-1
  */
  for(ctv = local_tile_basis; !VECTEUR_NUL_P(ctv) ; ctv = vecteur_succ(ctv)) {
    base_add_variable(mc->base,vecteur_var(ctv));
    sc_dimension(mc)++;
  }
  for(row = 1, civ = initial_basis;  row <= dim; row++, civ = vecteur_succ(civ)) {
    Pvecteur veq = vect_new(vecteur_var(civ),VALUE_ONE);
    Pcontrainte ceq = CONTRAINTE_UNDEFINED;
 
    for(col = 1, ctv = local_tile_basis; col <= dim ; col++, ctv = vecteur_succ(ctv)) {
      if(ACCESS(G_tile, dim, row, col)!=VALUE_ZERO) {
        Value coeff = ACCESS(G_tile, dim, row, col);
        vect_add_elem(&veq, vecteur_var(ctv), -1*coeff);
      }
    }  
    ceq = contrainte_make(veq);
    sc_add_egalite(mc, ceq);
  }
 
  ifdebug(8) {
    pips_debug(8, "End with constraint system mc:\n");
    sc_fprint(stderr, mc, (get_variable_name_t)entity_local_name);
    fprintf(stderr, "sc dimension = %d \n",mc->dimension);
  }
  mc2=sc_dup(mc);
  sc_projection_along_variables_ofl_ctrl(&mc2,initial_basis , OFL_CTRL);
  ifdebug(8) {
    pips_debug(8, "End with constraint system mc after change of basis:\n");
    sc_fprint(stderr, mc, (get_variable_name_t)entity_local_name);
  }
  scanning_base_to_vect(G_tile, n, local_tile_basis, pvch);
  return mc2;
}

References ACCESS, Ssysteme::base, base_add_variable(), base_dimension, BASE_UNDEFINED, check_tiling_legality(), compute_local_change_of_basis(), contrainte_make(), CONTRAINTE_UNDEFINED, Ssysteme::dimension, empty_string_p(), entity_local_name(), fprintf(), get_string_property(), ifdebug, malloc(), matrice_fprint(), matrice_general_inversion(), matrice_identite(), matrice_new, OFL_CTRL, pips_assert, pips_debug, sc_add_egalite(), sc_dup(), sc_fprint(), scanning_base_to_vect(), VALUE_ONE, VALUE_ZERO, vect_add_elem(), vect_new(), VECTEUR_NUL_P, vecteur_succ, and vecteur_var.

Referenced by parallel_tiling().

Here is the call graph for this function:

Here is the caller graph for this function:

loop_hyperplane()

bool loop_hyperplane

(

const char *

module_name

)

Parameters

module_name

odule_name

Definition at line 72 of file global_parallelization.c.

{
    bool return_status = false;
 
    return_status = interactive_loop_transformation(module_name, hyperplane);
    
    return return_status;
}

References hyperplane(), interactive_loop_transformation(), and module_name().

Here is the call graph for this function:

loop_nest_to_offset()

Pvecteur loop_nest_to_offset

(

list

lls

)

Parameters

lls

ls

Definition at line 501 of file tiling.c.

{
    Pvecteur origin = VECTEUR_NUL;
    list cs = list_undefined;
 
    for (cs = lls; cs != NIL; cs = CDR(cs)){
        loop l = instruction_loop(statement_instruction(STATEMENT(CAR(cs))));
        entity ind = loop_index(l);
        range r = loop_range(l);
        expression lower = range_lower(r);
        intptr_t val;
 
        if(expression_integer_value(lower, &val)) {
            vect_chg_coeff(&origin, (Variable) ind, (Value) val);
        }
    }
 
    return origin;
}

References CAR, CDR, expression_integer_value(), instruction_loop, intptr_t, list_undefined, loop_index, loop_range, NIL, origin, range_lower, STATEMENT, statement_instruction, vect_chg_coeff(), and VECTEUR_NUL.

Referenced by parallel_tiling(), and tiling_transformation().

Here is the call graph for this function:

Here is the caller graph for this function:

loop_tiling()

bool loop_tiling

(

const char *

module_name

)

Parameters

module_name

odule_name

Definition at line 725 of file tiling.c.

{
    bool return_status = false;
 
    return_status = interactive_loop_transformation(module_name,  (statement (*)(list, bool (*)(statement)))tiling_transformation);
    
    return return_status;
}

References interactive_loop_transformation(), module_name(), and tiling_transformation().

Here is the call graph for this function:

loop_unimodular()

int loop_unimodular

(

string

)

unimodular.c

parallel_loop_tiling()

bool parallel_loop_tiling

(

const char *

module_name

)

Parameters

module_name

odule_name

Definition at line 1143 of file tiling.c.

{
  bool return_status = false;
    return_status = interactive_loop_transformation(module_name, parallel_tiling);
    return return_status;
}

References interactive_loop_transformation(), module_name(), and parallel_tiling().

Here is the call graph for this function:

parallel_tiling()

statement parallel_tiling	(	list	,
		bool(*)(statement)
	)

sc_projection_concat_proj_on_variables()

Psysteme sc_projection_concat_proj_on_variables	(	Psysteme	sc,
		Pbase	index_base
	)

Parameters

sc	c
index_base	ndex_base

Definition at line 890 of file tiling.c.

{
  Pvecteur lvar_proj;
  Psysteme sc1 = sc_dup(sc);
  int nb=vect_size(index_base);
  // Automatic variables read in a CATCH block need to be declared volatile as
  // specified by the documentation
  volatile Psysteme sc2,sc3;
   sc3=sc_init_with_sc(sc);
   
  if (!VECTEUR_NUL_P(index_base))
  {
    volatile Pvecteur pv1;
    lvar_proj = vect_copy(base_reversal(index_base));
    sc2 = sc_copy(sc);
    for (pv1 = lvar_proj;!VECTEUR_NUL_P(pv1) && nb>1; pv1=pv1->succ, nb--) {
            
      CATCH(overflow_error) {
        sc_elim_var(sc2, vecteur_var(pv1));
      }
      TRY {// force the overflow forwarding in order to apply sc_elim_var in case of overflow
        sc_projection_along_variable_ofl_ctrl
          (&sc2,vecteur_var(pv1), FWD_OFL_CTRL);
        UNCATCH(overflow_error);
      }
      sc2 = sc_normalize(sc2);
      if (SC_EMPTY_P(sc2)) {
        sc2 = sc_empty(base_copy(sc->base));
        break;
      }
      else {
        build_sc_nredund_1pass(&sc2);
      }
      // Concatenation of the intermediate system sc2 resulting
      // from the projection of pv1 and the previous concatenated system sc3
      sc3 = sc_append(sc3,sc2);
      if (SC_EMPTY_P(sc3)) {
        sc3 = sc_empty(base_copy(sc->base));
        break;
      }
    }
  }
  sc1 = sc_append(sc1,sc3);
  sc1 = sc_normalize(sc1);
  if (SC_EMPTY_P(sc1))
    sc1 = sc_empty(base_copy(sc->base));     
  return sc1;
}

References Ssysteme::base, base_copy(), base_reversal(), build_sc_nredund_1pass(), CATCH, FWD_OFL_CTRL, overflow_error, sc_append(), sc_copy(), sc_dup(), sc_elim_var(), sc_empty(), sc_init_with_sc(), sc_normalize(), Svecteur::succ, TRY, UNCATCH, vect_copy(), vect_size(), VECTEUR_NUL_P, and vecteur_var.

Referenced by parallel_tiling().

Here is the call graph for this function:

Here is the caller graph for this function:

scanning_base_hyperplane()

void scanning_base_hyperplane	(	Value	[],
		int	,
		matrice
	)

scanning_base.c

Referenced by compute_local_change_of_basis(), hyperplane(), tile_hyperplane_constraints(), and tiling_transformation().

Here is the caller graph for this function:

static_partitioning_matrix()

bool static_partitioning_matrix	(	matrice	P,
		int	n,
		const char *	serialized_matrix
	)

tiling.c

Parameters

serialized_matrix

erialized_matrix

Definition at line 104 of file tiling.c.

{
    pips_assert("interactive_partitioning_matrix", n>=1);
    bool status = false;
    if( serialized_matrix && !string_undefined_p(serialized_matrix) && !empty_string_p(serialized_matrix))
    {
        int row,col;
        string ctxt0 = string_undefined, ctxt1 = string_undefined;
        string saved_ptr,buffer,elem = NULL;
        saved_ptr= buffer = strdup(serialized_matrix);
        string line = strtok_r(buffer,",",&ctxt0);
        DENOMINATOR(P) = VALUE_ONE;
        for(row=1;row<=n;row++){
            elem = strtok_r(line," ",&ctxt1);
 
            for(col=1;col<=n;col++)
            {
                if(!elem) elem = col==row ? "1" : "0";
                ACCESS(P, n, row, col)=atoi(elem);
                elem = strtok_r(NULL," ",&ctxt1);
            }
            line = strtok_r(NULL,",",&ctxt0);
        }
        status= ( line == NULL ) && (elem == NULL );
        free(saved_ptr);
    }
    return status;
}

References ACCESS, buffer, DENOMINATOR, empty_string_p(), free(), line, pips_assert, strdup(), string_undefined, string_undefined_p, and VALUE_ONE.

Referenced by parallel_tiling(), and tiling_transformation().

Here is the call graph for this function:

Here is the caller graph for this function:

symbolic_tiling()

bool symbolic_tiling

(

const char *

module_name

)

prelude

postlude

Parameters

module_name

odule_name

Definition at line 199 of file symbolic_tiling.c.

{
    /* prelude */
    bool result = false;
    set_current_module_entity(module_name_to_entity( module_name ));
    set_current_module_statement((statement) db_get_memory_resource(DBR_CODE, module_name, true) );
    set_cumulated_rw_effects((statement_effects)db_get_memory_resource(DBR_CUMULATED_EFFECTS, module_name, true));
 
    // sometimes empty continues are put here and there and disturb me
    clean_up_sequences(get_current_module_statement());
 
    entity elabel = find_label_entity(
            get_current_module_name(),
            get_string_property("LOOP_LABEL")
            );
    statement sloop = find_loop_from_label(get_current_module_statement(),elabel);
    if( !statement_undefined_p(sloop) )
    {
        list vector = string_to_expressions(
                get_string_property("SYMBOLIC_TILING_VECTOR"),",",
                get_current_module_entity());
        if(ENDP(vector))
            pips_user_warning("must provide a non empty array with expressions valid in current context\n");
        else if((result=symbolic_tiling_valid_p(sloop,gen_length(vector)))) {
            do_symbolic_tiling(sloop,vector);
        }
        gen_full_free_list(vector);
    }
    else pips_user_warning("must provide a valid loop label\n");
 
    /* postlude */
    module_reorder(get_current_module_statement());
    DB_PUT_MEMORY_RESOURCE(DBR_CODE, module_name,get_current_module_statement());
 
    reset_current_module_entity();
    reset_current_module_statement();
    reset_cumulated_rw_effects();
 
    return result;
}

References clean_up_sequences(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, do_symbolic_tiling(), ENDP, find_label_entity(), find_loop_from_label(), gen_full_free_list(), gen_length(), get_current_module_entity(), get_current_module_name(), get_current_module_statement(), get_string_property(), module_name(), module_name_to_entity(), module_reorder(), pips_user_warning, reset_cumulated_rw_effects(), reset_current_module_entity(), reset_current_module_statement(), set_cumulated_rw_effects(), set_current_module_entity(), set_current_module_statement(), statement_undefined_p, string_to_expressions(), and symbolic_tiling_valid_p().

Here is the call graph for this function:

tile_hyperplane_constraints()

Psysteme tile_hyperplane_constraints	(	Pbase	initial_basis,
		Pbase	tile_basis,
		matrice	HT,
		Pvecteur	tiling_offset
	)

Generate the tile membership constraints between a tile coordinates and an iteration coordinate.

computation of the hyperplane tile direction in the tile basis: = sum(hi)= 1H

computation of the tile scanning base G.

Build the constraints 0 <= det(HT).[HT. (i -i0)]<det(HT).1 with i0=P.G_tile.i_tile <==> 0 <= det(HT).[HT. (i -P.G_tile.i_tile)]<det(HT).1 <==> 0 <= det(HT).[HT.i -G_tile.i_tile]<= det(HT)-1

Find the origin of the iteration domain. Use 0 as default coordinate

Parameters

initial_basis	nitial_basis
tile_basis	ile_basis
HT	T
tiling_offset	iling_offset

Definition at line 274 of file tiling.c.

{
  Psysteme mc = sc_new();
  int dim = base_dimension(initial_basis);
  int row;
  int col,col2;
  Value k = DENOMINATOR(HT);
  Value up = k - VALUE_ONE;
  Pbase civ = BASE_UNDEFINED;
  Pbase ctv = BASE_UNDEFINED;
  matrice  G_tile;
  Value *h_tile; // hyperplane direction
  ifdebug(8) {
    debug(8, "tile_membership_constraints", "Begin with Matrix HT:\n");
    matrice_fprint(stderr,HT, dim, dim);
  }
  int n = dim; 
  pips_assert("The two bases have the same dimension", dim == base_dimension(tile_basis));
 
  ifdebug(8) {
    pips_debug(8,"hyperplane matrix HT:");
    matrice_fprint(stderr, HT, n, n);
    (void) fprintf(stderr,"\n");
  }
 
  /* computation of the hyperplane tile direction in the tile basis: = sum(hi)= 1H */
  h_tile = (Value*)(malloc(n*sizeof(Value)));
  G_tile = matrice_new(n,n);
 
  string tile_direction = (string) get_string_property("TILE_DIRECTION");
  if(!empty_string_p(tile_direction) && strcmp(tile_direction,"TP") == 0) {
    for(col=0; col<n; col++) {
      h_tile[col]=VALUE_ONE;
    }
    
    ifdebug(8) {
      (void) fprintf(stdout,"The hyperplane direction h_tile is :");
      for(col=0; col<n; col++) 
        (void) printf("%d ;",(int)h_tile[col]);
      (void) printf("\n");
    }
    /* computation of the tile scanning base G.  
     */
   scanning_base_hyperplane(h_tile, n, G_tile);
    ifdebug(8) {
      (void) fprintf(stderr,"The tile scanning base G_tile is :");
      matrice_fprint(stderr, G_tile, n, n);
    }
  }
  else matrice_identite(G_tile,n,0);
  
    /* Build the constraints
       0 <= det(HT).[HT. (i -i0)]<det(HT).1 with 
       i0=P.G_tile.i_tile
     <==> 0 <= det(HT).[HT. (i -P.G_tile.i_tile)]<det(HT).1
     <==> 0 <= det(HT).[HT.i -G_tile.i_tile]<= det(HT)-1
  */
  for(row = 1; row <= dim; row++) {
    Pvecteur upper = VECTEUR_NUL;
    Pvecteur lower = VECTEUR_NUL;
    Pcontrainte cupper = CONTRAINTE_UNDEFINED;
    Pcontrainte clower = CONTRAINTE_UNDEFINED;
 
    for(col = 1, civ = initial_basis; col <= dim; col++, civ = vecteur_succ(civ)) {
      if(ACCESS(HT, dim, row, col)!=VALUE_ZERO) {
        Value coeff = ACCESS(HT, dim, row, col);
        Value offset = vect_coeff(vecteur_var(civ), tiling_offset);
 
        vect_add_elem(&upper, vecteur_var(civ), coeff);
        vect_add_elem(&upper, TCST, value_uminus(offset*coeff));
     }
    }
    for(col2 = 1, ctv = tile_basis; col2 <= dim; col2++,ctv = vecteur_succ(ctv)) {
 
      /* Find the origin of the iteration domain. Use 0 as default coordinate */
      if(ACCESS(G_tile, dim, row, col2)!=VALUE_ZERO) {
        Value coeff2 = ACCESS(G_tile, dim,row, col2);
        vect_add_elem(&upper, vecteur_var(ctv), value_uminus(k) *coeff2);       
      }
    }
  
    lower = vect_dup(upper);
    vect_chg_sgn(lower);
    vect_add_elem(&upper, TCST, value_uminus(up));
    cupper = contrainte_make(upper);
    clower = contrainte_make(lower);
    sc_add_inegalite(mc, cupper);
    sc_add_inegalite(mc, clower);
  }
  sc_creer_base(mc);
 
  ifdebug(8) {
    pips_debug(8, "End with constraint system mc:\n");
    sc_fprint(stderr, mc, (get_variable_name_t)entity_local_name);
  }
 
  return mc;
}

References ACCESS, base_dimension, BASE_UNDEFINED, contrainte_make(), CONTRAINTE_UNDEFINED, debug(), DENOMINATOR, empty_string_p(), entity_local_name(), fprintf(), get_string_property(), ifdebug, malloc(), matrice_fprint(), matrice_identite(), matrice_new, offset, pips_assert, pips_debug, printf(), sc_add_inegalite(), sc_creer_base(), sc_fprint(), sc_new(), scanning_base_hyperplane(), TCST, VALUE_ONE, value_uminus, VALUE_ZERO, vect_add_elem(), vect_chg_sgn(), vect_coeff(), vect_dup(), VECTEUR_NUL, vecteur_succ, and vecteur_var.

Referenced by parallel_tiling().

Here is the call graph for this function:

Here is the caller graph for this function:

tiling_transformation()

statement tiling_transformation	(	list	,
		bool(*)(statement)
	)