bdt_read_paf.c File Reference

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "boolean.h"
#include "arithmetique.h"
#include "vecteur.h"
#include "contrainte.h"
#include "ray_dte.h"
#include "sommet.h"
#include "sg.h"
#include "sc.h"
#include "polyedre.h"
#include "matrice.h"
#include "matrix.h"
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "ri-util.h"
#include "constants.h"
#include "misc.h"
#include "paf_ri.h"
#include "graph.h"
#include "paf-util.h"

Include dependency graph for bdt_read_paf.c:

Go to the source code of this file.

Macros
#define	POSITIVE   1
#define	NEGATIVE   0
#define	INS_NAME_LENGTH   4
#define	DOT   "."
#define	BDT_STRING   "bdt"

Typedefs
typedef dfg_arc_label	arc_label
	Name : bdt_read_paf.c Package : paf-util Author : Alexis Platonoff Date : april 1993 Historic : More...
typedef dfg_vertex_label	vertex_label

Functions
bdt	bdt_read_paf (char *s)
	=========================================================================== More...
bool	same_predicate_p (predicate p1, predicate p2)
	=========================================================================== More...
void	reorganize_bdt (bdt base)
	=========================================================================== More...
void	bdt_init_new_base ()
	=========================================================================== More...
void	bdt_init_new_ins (char *s_ins)
	=========================================================================== More...
void	bdt_new_shedule (string s_func __attribute__((unused)))
	=========================================================================== More...
void	bdt_save_pred (int option)
	=========================================================================== More...
void	bdt_elim_last_pred ()
	=========================================================================== More...
void	bdt_save_int (int i)
	=========================================================================== More...
void	bdt_save_id (string s)
	=========================================================================== More...
void	bdt_init_op_exp (string op_name)
	=========================================================================== More...
void	bdt_save_exp ()
	=========================================================================== More...

Variables
static int	crt_ins
	Static global variables. More...
static list	pred_l
	Current stmt (an integer) More...
static list	lin_exp_l
	Current list of predicates. More...
static expression	crt_exp
	Current list of linear expressions. More...
bdt	base
	Current expression. More...

Macro Definition Documentation

BDT_STRING

#define BDT_STRING   "bdt"

Definition at line 85 of file bdt_read_paf.c.

DOT

#define DOT   "."

Definition at line 84 of file bdt_read_paf.c.

INS_NAME_LENGTH

#define INS_NAME_LENGTH   4

Definition at line 83 of file bdt_read_paf.c.

NEGATIVE

#define NEGATIVE   0

Definition at line 82 of file bdt_read_paf.c.

POSITIVE

#define POSITIVE   1

Definition at line 81 of file bdt_read_paf.c.

Typedef Documentation

arc_label

typedef dfg_arc_label arc_label

Name : bdt_read_paf.c Package : paf-util Author : Alexis Platonoff Date : april 1993 Historic :

• 16 july 93, changes in paf_ri, AP
• 2 august 93, moved from (package) scheduling to paf-util, AP
• 10 nov 93: add of reorganize_bdt() and same_predicate_p(), AP

Documents: Comments : These functions are used to store a timing function (BDT) in a Newgen structure from the reading of a file generate by the PAF parallelizer: ".bdt" file, which contains the BDT functions.

Each BDT function is associated with an instruction and a predicate. The Newgen structure is called "bdt" which is a list of BDT function of type "schedule". These two Newgen structures are defined in the file paf_ri.f.tex (see comments on them in this file). We also use the library of PIPS and its RI Newgen structure.

The ".bdt" file is read with Yacc and Lex programs (parse.y and scan.l). The Newgen structure "bdt" is update during the parsing of the file.

Definition at line 76 of file bdt_read_paf.c.

vertex_label

typedef dfg_vertex_label vertex_label

Definition at line 77 of file bdt_read_paf.c.

Function Documentation

bdt_elim_last_pred()

void bdt_elim_last_pred

(

void

)

===========================================================================

void bdt_elim_last_pred(): When POSITIVE and NEGATIVE cases of one predicate have been completed, we eliminate the corresponding expression which is the first one of the list "pred_l".

Definition at line 312 of file bdt_read_paf.c.

{
 extern list pred_l;
 
 pred_l = CDR(pred_l);
}

References CDR, and pred_l.

bdt_init_new_base()

void bdt_init_new_base

(

void

)

===========================================================================

void bdt_init_new_base() : initializes the computation of the BDT, i.e. the creation of the BDT in the "base" variable.

Definition at line 207 of file bdt_read_paf.c.

{
 extern bdt base;
 
 base = make_bdt(NIL);
}

References base, make_bdt(), and NIL.

Here is the call graph for this function:

bdt_init_new_ins()

void bdt_init_new_ins

(

char *

s_ins

)

===========================================================================

void bdt_init_new_ins(char *s_ins): initializes the computation of the current statement for which we are now parsing its BDT. This statement is represented by its ordering contained in its name "s_ins". Also, we initialize "lin_exp_l" used for the parsing of the lisp expressions and "pred_l" used for the parsing of the predicates.

In PAF, a statement name is a string "ins_#", where "#" is the number associated with the statement. We get this number.

Parameters

s_ins

_ins

Definition at line 221 of file bdt_read_paf.c.

{
 extern int crt_ins;
 extern list pred_l, lin_exp_l;
 
 /* In PAF, a statement name is a string "ins_#", where "#" is the number
  * associated with the statement. We get this number.
  */
 crt_ins = atoi(strdup(s_ins + INS_NAME_LENGTH));
 
 pred_l = NIL;
 lin_exp_l = NIL;
}

References crt_ins, INS_NAME_LENGTH, lin_exp_l, NIL, pred_l, and strdup().

Here is the call graph for this function:

bdt_init_op_exp()

void bdt_init_op_exp

(

string

op_name

)

===========================================================================

void bdt_init_op_exp(string op_name): initializes a new lisp expression with the operation "op_name". This expression is put at the beginning of "lin_exp_l", it is the expression the parser is currently reading.

If "op_name" is the string "0" then the operator used is "crt_op_name", else the operator name is contained in "op_name".

Parameters

op_name

p_name

Definition at line 379 of file bdt_read_paf.c.

{
 extern list lin_exp_l;
 
 lin_exp_l = CONS(LISP_EXPRESSION, make_lisp_expression(op_name, NIL), lin_exp_l);
}

References CONS, lin_exp_l, LISP_EXPRESSION, make_lisp_expression(), and NIL.

Here is the call graph for this function:

bdt_new_shedule()

void bdt_new_shedule

(

string s_func

__attribute__(unused)

)

===========================================================================

void bdt_new_shedule(char *s_func): the parser has found all the predicates of a schedule. We create this new schedule and put it in "base". This predicate is formed with the list of expressions of "pred_l". The function expressions_to_predicate() translates this list of expressions into a predicate. The schedule statement number is the current one (crt_ins"). The schedule has one dimension, the corresponding expression is found in "crt_exp".

Definition at line 245 of file bdt_read_paf.c.

{
    extern int crt_ins;
    extern expression crt_exp;
    extern list pred_l, lin_exp_l;
 
    bdt_schedules(base) = CONS(SCHEDULE,
                               make_schedule(crt_ins,
                                             expressions_to_predicate(pred_l),
                                             CONS(EXPRESSION, crt_exp, NIL)),
                               bdt_schedules(base));
    
    lin_exp_l = NIL;
    crt_exp = expression_undefined;
}

References base, bdt_schedules, CONS, crt_exp, crt_ins, EXPRESSION, expression_undefined, expressions_to_predicate(), lin_exp_l, make_schedule(), NIL, pred_l, and SCHEDULE.

Here is the call graph for this function:

bdt_read_paf()

bdt bdt_read_paf

(

char *

s

)

===========================================================================

bdt bdt_read_paf(char *s) : computes the BDT of the PAF program name given in argument and returns it.

bdtyyparse() do the parsing over the ".bdt" file and put the timing function into the global variable "base" which is returned.

Definition at line 110 of file bdt_read_paf.c.

{
 extern bdt base;
 
 FILE *bdt_file;
 char *bdt_file_name;
 
 bdt_file_name = strdup(concatenate(s, DOT, BDT_STRING, (char *) NULL));
 
 if( (bdt_file = fopen(bdt_file_name, "r")) == NULL)
   {
     fprintf(stderr, "Cannot open file %s\n", bdt_file_name);
     exit(1);
   }
 
#if defined(HAS_BDTYY)
 
 bdtyyin = bdt_file;
 (void) bdtyyparse();
 
#else
 
 pips_internal_error("not bdtyy{in,parse} compiled in (HAS_BDTYY undef)");
 
#endif
 
 fclose(bdt_file);
 
 reorganize_bdt(base);
 
 return(base);
}

References base, BDT_STRING, concatenate(), DOT, exit, fprintf(), pips_internal_error, reorganize_bdt(), and strdup().

Here is the call graph for this function:

bdt_save_exp()

void bdt_save_exp

(

void

)

===========================================================================

void bdt_save_exp(): the parser has completed the reading of one lisp expression, this is the first lisp expression of "lin_exp_l". We extract it from this list and translate it into a Pips expression. If there is no other lisp expression in "lin_exp_l", then this expression becomes the current expression, else it becomes an argument of the next lisp expression which is now the first object of "lin_exp_l".

Definition at line 395 of file bdt_read_paf.c.

{
 extern expression crt_exp;
 
 expression aux_exp;
 lisp_expression aux_le;
 
 aux_le = LISP_EXPRESSION(CAR(lin_exp_l));
 aux_exp = lisp_exp_to_ri_exp(aux_le);
 
 lin_exp_l = CDR(lin_exp_l);
 
 if(lin_exp_l == NIL)
   crt_exp = aux_exp;
 else
   {
    lisp_expression crt_le = LISP_EXPRESSION(CAR(lin_exp_l));
    lisp_expression_args(crt_le) = gen_nconc(lisp_expression_args(crt_le),
                                             CONS(EXPRESSION, aux_exp, NIL));
   }
}

References CAR, CDR, CONS, crt_exp, EXPRESSION, gen_nconc(), lin_exp_l, lisp_exp_to_ri_exp(), LISP_EXPRESSION, lisp_expression_args, and NIL.

Here is the call graph for this function:

bdt_save_id()

void bdt_save_id

(

string

s

)

===========================================================================

void bdt_save_id(string s): The parser has found a variable as a part of a lisp expression. We save it in our global variable "lin_exp_l".

If "lin_exp_l" is empty, then this variable becomes the current expression. If not, it becomes an argument of the first lisp expression of "lin_exp_l".

Definition at line 352 of file bdt_read_paf.c.

{
 extern list lin_exp_l;
 extern expression crt_exp;
 expression aux_exp;
 
 aux_exp = make_id_expression(s);
 
 if(lin_exp_l == NIL)
    crt_exp = aux_exp;
 else
   {
    lisp_expression crt_le = LISP_EXPRESSION(CAR(lin_exp_l));
    lisp_expression_args(crt_le) = gen_nconc(lisp_expression_args(crt_le),
                                             CONS(EXPRESSION, aux_exp, NIL));
   }
}

References CAR, CONS, crt_exp, EXPRESSION, gen_nconc(), lin_exp_l, LISP_EXPRESSION, lisp_expression_args, make_id_expression(), and NIL.

Here is the call graph for this function:

bdt_save_int()

void bdt_save_int

(

int

i

)

===========================================================================

void bdt_save_int(int i): The parser has found an integer as a part of a lisp expression. We save it in our global variable "lin_exp_l".

If "lin_exp_l" is empty, then this integer becomes the current expression. If not, it becomes an argument of the first lisp expression of "lin_exp_l".

Definition at line 326 of file bdt_read_paf.c.

{
 extern list lin_exp_l;
 extern expression crt_exp;
 expression aux_exp;
 
 aux_exp = int_to_expression(i);
 
 if(lin_exp_l == NIL)
    crt_exp = aux_exp;
 else
   {
    lisp_expression crt_le = LISP_EXPRESSION(CAR(lin_exp_l));
    lisp_expression_args(crt_le) = gen_nconc(lisp_expression_args(crt_le),
                                             CONS(EXPRESSION, aux_exp, NIL));
   }
}

References CAR, CONS, crt_exp, EXPRESSION, gen_nconc(), int_to_expression(), lin_exp_l, LISP_EXPRESSION, lisp_expression_args, and NIL.

Here is the call graph for this function:

bdt_save_pred()

void bdt_save_pred

(

int

option

)

===========================================================================

void bdt_save_pred(int option): computes one expression of the predicate. Each expression is used twice ; indeed, an expression may be greater or equal than zero (>=) and smaller than zero (<). "option" says in which case we are: POSITIVE indicates that the predicate is >=, with NEGATIVE it is <. However, the C3 library always represents its inequalities with <=. So, the inequality "A >= 0" becomes "-A <= 0" and "A < 0" becomes "A + 1 <= 0".

This function updates the global list "pred_l" that contains the current list of predicates. When a new predicate expression is parsed, the POSITIVE is always considered first (that is why only in that case we use "crt_exp"). When the NEGATICE case is considered, the corresponding expression (used in the POSITIVE case) is the first expression of the list "pred_l". So, we only have to replace this expression by it equivalent for the NEGATIVE case (that is why the expression is multiplied by -1).

option == NEGATIVE

Initialization of global variables

Parameters

option

ption

Definition at line 277 of file bdt_read_paf.c.

{
 extern list pred_l, lin_exp_l;
 extern expression crt_exp;
 
 expression aux_pred;
 
 if(option == POSITIVE)
   {
    if(crt_exp == expression_undefined)
       pips_internal_error("current expression is undefined");
 
    pred_l = CONS(EXPRESSION, negate_expression(crt_exp), pred_l);
    crt_exp = expression_undefined;
   }
 else
 /* option == NEGATIVE */
   {
    aux_pred = make_op_exp(PLUS_OPERATOR_NAME,
                           negate_expression(EXPRESSION(CAR(pred_l))),
                           int_to_expression(1));
 
    pred_l = CONS(EXPRESSION, aux_pred, CDR(pred_l));
   }
 
/* Initialization of global variables */
 lin_exp_l = NIL;
}

References CAR, CDR, CONS, crt_exp, EXPRESSION, expression_undefined, int_to_expression(), lin_exp_l, make_op_exp(), negate_expression(), NIL, pips_internal_error, PLUS_OPERATOR_NAME, POSITIVE, and pred_l.

Here is the call graph for this function:

reorganize_bdt()

void reorganize_bdt

(

bdt

base

)

===========================================================================

void reorganize_bdt(bdt base):

Parameters

base

ase

Definition at line 171 of file bdt_read_paf.c.

{
  list sch_l, new_sch_l = NIL, l;
 
  for(sch_l = bdt_schedules(base); !ENDP(sch_l); POP(sch_l)) {
    schedule sch = SCHEDULE(CAR(sch_l));
    int stmt = schedule_statement(sch);
    predicate pred = schedule_predicate(sch);
    bool to_add = true;
 
    for(l = new_sch_l; (!ENDP(l)) && to_add; POP(l)) {
      schedule nsch =  SCHEDULE(CAR(l));
      int nstmt = schedule_statement(nsch);
      predicate npred = schedule_predicate(nsch);
 
      if(stmt == nstmt) {
        if(same_predicate_p(pred, npred)) {
          expression nexp = EXPRESSION(CAR(schedule_dims(sch)));
          schedule_dims(nsch) = gen_nconc(schedule_dims(nsch),
                                          CONS(EXPRESSION, nexp, NIL));
          to_add = false;
        }
      }
    }
    if(to_add)
      new_sch_l = gen_nconc(new_sch_l, CONS(SCHEDULE, sch, NIL));
  }
  bdt_schedules(base) = new_sch_l;
}

References base, bdt_schedules, CAR, CONS, ENDP, EXPRESSION, gen_nconc(), NIL, POP, same_predicate_p(), SCHEDULE, schedule_dims, schedule_predicate, and schedule_statement.

Referenced by bdt_read_paf().

Here is the call graph for this function:

Here is the caller graph for this function:

same_predicate_p()

bool same_predicate_p	(	predicate	p1,
		predicate	p2
	)

===========================================================================

If the predicate are defined, we consider them as always different

Parameters

p1	1
p2	2

Definition at line 145 of file bdt_read_paf.c.

{
 
  if( (p1 == predicate_undefined) && (p2 == predicate_undefined) )
    return(true);
  else if(p1 == predicate_undefined)
    return(false);
  else if(p2 == predicate_undefined)
    return(false);
 
  if( (p1 == NULL) && (p2 == NULL) )
    return(true);
  else if(p1 == NULL)
    return(false);
  else if(p2 == NULL)
    return(false);
 
  /* If the predicate are defined, we consider them as always different */
  return(false);
}

References predicate_undefined.

Referenced by reorganize_bdt().

Here is the caller graph for this function:

Variable Documentation

base

bdt base

Current expression.

bdt_read_paf.c

Global variables This global variable is the current BDT being computed. Its type is defined in paf_ri.h

Definition at line 100 of file bdt_read_paf.c.

Referenced by bdt_init_new_base(), bdt_new_shedule(), bdt_read_paf(), check_the_reference(), clean_list_of_unk(), contrainte_extract(), contrainte_sort(), contrainte_to_matrix_ligne(), create_pointer_to_array_stub_points_to(), create_private_integer_variable_for_new_module(), create_private_variable_for_new_module(), do_symbolic_tiling(), expression_to_transformer(), expression_try_find_size(), find_bd_call(), find_bd_expression(), find_bd_parameter(), find_bd_reference(), find_bd_type_variable(), find_or_create_scalar_entity(), find_or_create_typed_entity(), hpfc_algorithm_row_echelon(), hpfc_fclose(), hpfc_fopen(), make_array_entity(), make_bound_expression(), make_list_of_unk(), make_new_reduction_function(), make_packing_function(), make_primal(), make_reduction_function(), make_reduction_vector_entity(), make_scalar_entity(), MakeFileName(), new_ecrit_ligne(), pip_solve(), position_in_the_area(), rank_of_variable(), region_to_com_nest(), region_to_loop_nest(), reorganize_bdt(), sc_of_constrs(), sc_of_rays(), scanning_base_to_vect(), search_higher_rank(), search_var_of_higher_rank(), set_sort_context(), sg_of_constrs(), sg_of_rays(), sort_entities_with_dep(), terapix_init_row(), variable_of_rank(), vecteur_of_zvec(), and zmat_set_row().

crt_exp

expression crt_exp

static

Current list of linear expressions.

Definition at line 92 of file bdt_read_paf.c.

Referenced by bdt_new_shedule(), bdt_save_exp(), bdt_save_id(), bdt_save_int(), and bdt_save_pred().

crt_ins

int crt_ins

static

Static global variables.

Definition at line 89 of file bdt_read_paf.c.

Referenced by bdt_init_new_ins(), and bdt_new_shedule().

lin_exp_l

list lin_exp_l

static

Current list of predicates.

Definition at line 91 of file bdt_read_paf.c.

Referenced by bdt_init_new_ins(), bdt_init_op_exp(), bdt_new_shedule(), bdt_save_exp(), bdt_save_id(), bdt_save_int(), and bdt_save_pred().

pred_l

list pred_l

static

Current stmt (an integer)

Definition at line 90 of file bdt_read_paf.c.

Referenced by bdt_elim_last_pred(), bdt_init_new_ins(), bdt_new_shedule(), and bdt_save_pred().