PIPS
symbolic_tiling.c
Go to the documentation of this file.
1 /* symbolic tiling
2  * less general, but works for symbolics bounds
3  */
4 #ifdef HAVE_CONFIG_H
5  #include "pips_config.h"
6 #endif
7 
8 #include "genC.h"
9 #include "linear.h"
10 #include "ri.h"
11 
12 #include "ri-util.h"
13 #include "misc.h"
14 #include "pipsdbm.h"
15 #include "workspace-util.h"
16 #include "properties.h"
17 #include "control.h"
18 
19 #include "effects-generic.h"
20 #include "effects-simple.h"
21 #include "effects-util.h"
22 
23 #include "transformations.h"
24 
25 static void fix_loop_index_sign(loop l)
26 {
28  set_add_element(ent,ent,loop_index(l));
29  SET_FOREACH(entity,e,ent) {
31  if(entity_formal_p(e)) {
33  if(unsigned_type_p(t)) {
39  replace_entity(l,e,newe);
40  pips_assert("type consistent",type_consistent_p(entity_type(e)));
41  }
42  }
43  else {
45  if(unsigned_type_p(t)) {
47  entity_type(e)=
51  NIL,
52  NIL
53  )
54  );
55  pips_assert("type consistent",type_consistent_p(entity_type(e)));
56  }
57  }
58  }
59  pips_assert("entity is fine",entity_consistent_p(e));
60  }
61  set_free(ent);
62 }
63 
65 {
67  list tiled_loops_outer = NIL;
68  list tiled_loops_inner = NIL;
69  list prelude = NIL;
72  FOREACH(EXPRESSION,tile_size,vector)
73  {
74  loop l = statement_loop(sloop);
75  list tile_expression_effects = proper_effects_of_expression(tile_size);
76  /* check if tile_size is modified by sloop and generate a temporary variable if needed */
77  /* we should also check tile_size has no write effect
78  * but currently, string_to_expression asserts this */
79  FOREACH(EFFECT,teff,tile_expression_effects) {
80  FOREACH(EFFECT,eff,effects) {
81  if(effect_write_p(eff) &&
83  {
88  prelude=CONS(STATEMENT,ass,prelude);
89  goto generate_tile;
90  }
91  }
92  }
93 generate_tile:;
94  /* outer loop new index */
97  expression lower_bound =
99  entity_to_expression(index),
100  copy_expression(tile_size)
101  );
102  expression upperbound_lhs = copy_expression(range_upper(loop_range(l)));
103  expression upperbound_rhs =
105  copy_expression(lower_bound),
107  copy_expression(tile_size),
109  )
110  );
111 
112  expression upper_bound =
114  upperbound_lhs,
115  upperbound_rhs
116  );
117 
118  /* inner loop */
121  make_loop(
122  loop_index(l),
123  make_range(
124  lower_bound,
125  upper_bound,
127  ),
131  NIL
132  )
133  )
134  );
135  /* outer loop */
136  statement outer = sloop;
137  loop_index(l)=index;
138  //range_increment(loop_range(l))=copy_expression(tile_size);
139  /* will help partial_eval */
143  copy_expression(tile_size)
144  );
145  /* save */
146  tiled_loops_outer=CONS(STATEMENT,outer,tiled_loops_outer);
147  tiled_loops_inner=CONS(STATEMENT,inner,tiled_loops_inner);
148 
149  /* go on for the next one */
150  sloop=loop_body(l);
151  }
152  /* once we are done, regenerate the whole thing */
153 
154  /* prepare chain all */
155  tiled_loops_inner=gen_append(tiled_loops_inner,tiled_loops_outer);
156  statement last = STATEMENT(CAR(tiled_loops_inner));
157  statement prev = last;
158  POP(tiled_loops_inner);
159  /* set tail */
160  loop_body(statement_loop(last))=sloop;
161  /* chain all */
162  FOREACH(STATEMENT,curr,tiled_loops_inner) {
163  loop_body(statement_loop(curr))=prev;
164  prev=curr;
165  }
166 
167  /* update */
168  statement_label(base)=entity_empty_label();/*the label have been duplicated by copy_statement */
172 
173  /* fix signed / unsigned types for further processing otherwise we could end with integer overflow */
175 }
176 
177 
178 /* checks if sloop is a perfectly nested loop of depth @depth */
179 static bool symbolic_tiling_valid_p(statement sloop, size_t depth)
180 {
181  intptr_t l;
182  if(depth == 0 ) return true;
183  else {
184  if(statement_loop_p(sloop) &&
185  ( execution_parallel_p(loop_execution(statement_loop(sloop))) || get_bool_property("SYMBOLIC_TILING_FORCE") ) &&
187  ){
188  statement body = loop_body(statement_loop(sloop));
189  return symbolic_tiling_valid_p(body,depth-1);
190  }
191  else {
192  pips_user_error("given loop is either not normalized or not parallel or not nested\n");
193  return false;
194  }
195  }
196 }
197 
198 
199 bool symbolic_tiling(const char *module_name)
200 {
201  /* prelude */
202  bool result = false;
206 
207  // sometimes empty continues are put here and there and disturb me
209 
210  entity elabel = find_label_entity(
212  get_string_property("LOOP_LABEL")
213  );
215  if( !statement_undefined_p(sloop) )
216  {
218  get_string_property("SYMBOLIC_TILING_VECTOR"),",",
220  if(ENDP(vector))
221  pips_user_warning("must provide a non empty array with expressions valid in current context\n");
222  else if((result=symbolic_tiling_valid_p(sloop,gen_length(vector)))) {
223  do_symbolic_tiling(sloop,vector);
224  }
226  }
227  else pips_user_warning("must provide a valid loop label\n");
228 
229  /* postlude */
232 
236 
237  return result;
238 }
239 
instruction make_instruction_loop(loop _field_)
Definition: ri.c:1175
value make_value_expression(expression _field_)
Definition: ri.c:2850
loop make_loop(entity a1, range a2, statement a3, entity a4, execution a5, list a6)
Definition: ri.c:1301
type make_type_variable(variable _field_)
Definition: ri.c:2715
basic make_basic_int(intptr_t _field_)
Definition: ri.c:158
expression copy_expression(expression p)
EXPRESSION.
Definition: ri.c:850
statement copy_statement(statement p)
STATEMENT.
Definition: ri.c:2186
reference make_reference(entity a1, list a2)
Definition: ri.c:2083
variable make_variable(basic a1, list a2, list a3)
Definition: ri.c:2895
void free_type(type p)
Definition: ri.c:2658
execution make_execution_parallel(void)
Definition: ri.c:844
bool type_consistent_p(type p)
Definition: ri.c:2664
bool entity_consistent_p(entity p)
Definition: ri.c:2530
range make_range(expression a1, expression a2, expression a3)
Definition: ri.c:2041
void free_value(value p)
Definition: ri.c:2787
syntax make_syntax_reference(reference _field_)
Definition: ri.c:2494
bdt base
Current expression.
Definition: bdt_read_paf.c:100
bool clean_up_sequences(statement s)
Recursively clean up the statement sequences by fusing them if possible and by removing useless one.
void set_cumulated_rw_effects(statement_effects)
list load_cumulated_rw_effects_list(statement)
void reset_cumulated_rw_effects(void)
list proper_effects_of_expression(expression)
#define effect_any_reference(e)
FI: cannot be used as a left hand side.
#define effect_write_p(eff)
#define EFFECT(x)
EFFECT.
Definition: effects.h:608
const char * module_name(const char *s)
Return the module part of an entity name.
Definition: entity_names.c:296
list string_to_expressions(const char *str, const char *seed, entity module)
split a string using seed as separator and call string_to_expression on each chunk
Definition: expressions.c:98
char * get_string_property(const char *)
bool get_bool_property(const string)
FC 2015-07-20: yuk, moved out to prevent an include cycle dependency include "properties....
#define gen_recurse(start, domain_number, flt, rwt)
Definition: genC.h:283
void gen_full_free_list(list l)
Definition: genClib.c:1023
bool references_may_conflict_p(reference r1, reference r2)
Check if two references may conflict.
Definition: conflicts.c:426
void set_conflict_testing_properties()
conflicts.c
Definition: conflicts.c:68
statement instruction_to_statement(instruction)
Build a statement from a give instruction.
Definition: statement.c:597
void reset_current_module_entity(void)
Reset the current module entity.
Definition: static.c:97
void reset_current_module_statement(void)
Reset the current module statement.
Definition: static.c:221
const char * get_current_module_name(void)
Get the name of the current module.
Definition: static.c:121
statement set_current_module_statement(statement)
Set the current module statement.
Definition: static.c:165
statement get_current_module_statement(void)
Get the current module statement.
Definition: static.c:208
entity set_current_module_entity(entity)
static.c
Definition: static.c:66
entity get_current_module_entity(void)
Get the entity of the current module.
Definition: static.c:85
void replace_entity(void *s, entity old, entity new)
per variable version of replace_entities.
Definition: replace.c:113
bool gen_true(__attribute__((unused)) gen_chunk *unused)
Return true and ignore the argument.
Definition: genClib.c:2780
instruction make_instruction_block(list statements)
Build an instruction block from a list of statements.
Definition: instruction.c:106
#define ENDP(l)
Test if a list is empty.
Definition: newgen_list.h:66
list gen_nreverse(list cp)
reverse a list in place
Definition: list.c:304
#define POP(l)
Modify a list pointer to point on the next element of the list.
Definition: newgen_list.h:59
#define NIL
The empty list (nil in Lisp)
Definition: newgen_list.h:47
size_t gen_length(const list l)
Definition: list.c:150
#define CONS(_t_, _i_, _l_)
List element cell constructor (insert an element at the beginning of a list)
Definition: newgen_list.h:150
#define CAR(pcons)
Get the value of the first element of a list.
Definition: newgen_list.h:92
#define FOREACH(_fe_CASTER, _fe_item, _fe_list)
Apply/map an instruction block on all the elements of a list.
Definition: newgen_list.h:179
list gen_append(list l1, const list l2)
Definition: list.c:471
string db_get_memory_resource(const char *rname, const char *oname, bool pure)
Return the pointer to the resource, whatever it is.
Definition: database.c:755
#define DB_PUT_MEMORY_RESOURCE(res_name, own_name, res_val)
conform to old interface.
Definition: pipsdbm-local.h:66
loop statement_loop(statement)
Get the loop of a statement.
Definition: statement.c:1374
bool statement_loop_p(statement)
Definition: statement.c:349
statement make_assign_statement(expression, expression)
Definition: statement.c:583
statement update_statement_instruction(statement, instruction)
Replace the instruction in statement s by instruction i.
Definition: statement.c:3039
#define pips_user_warning
Definition: misc-local.h:146
#define pips_assert(what, predicate)
common macros, two flavors depending on NDEBUG
Definition: misc-local.h:172
#define pips_user_error
Definition: misc-local.h:147
#define SET_FOREACH(type_name, the_item, the_set)
enumerate set elements in their internal order.
Definition: newgen_set.h:78
void set_free(set)
Definition: set.c:332
set set_add_element(set, const set, const void *)
Definition: set.c:152
bool module_reorder(statement body)
Reorder a module and recompute order to statement if any.
Definition: reorder.c:244
#define MINUS_OPERATOR_NAME
#define PLUS_OPERATOR_NAME
#define DEFAULT_INTEGER_TYPE_SIZE
#define binary_intrinsic_expression(name, e1, e2)
#define DIVIDE_OPERATOR_NAME
#define MULTIPLY_OPERATOR_NAME
#define MIN_OPERATOR_NAME
const char * entity_user_name(entity e)
Since entity_local_name may contain PIPS special characters such as prefixes (label,...
Definition: entity.c:487
bool entity_formal_p(entity p)
is p a formal parameter?
Definition: entity.c:1935
bool local_entity_of_module_p(entity e, entity module)
This test shows that "e" has been declared in "module".
Definition: entity.c:1069
entity module_name_to_entity(const char *mn)
This is an alias for local_name_to_top_level_entity.
Definition: entity.c:1479
entity entity_empty_label(void)
Definition: entity.c:1105
set get_referenced_entities(void *elem)
retrieves the set of entities used in elem beware that this entities may be formal parameters,...
Definition: entity.c:3063
bool expression_integer_value(expression e, intptr_t *pval)
Definition: eval.c:792
expression entity_to_expression(entity e)
if v is a constant, returns a constant call.
Definition: expression.c:165
void update_expression_syntax(expression e, syntax s)
frees expression syntax of e and replace it by the new syntax s
Definition: expression.c:3564
expression int_to_expression(_int i)
transform an int into an expression and generate the corresponding entity if necessary; it is not cle...
Definition: expression.c:1188
expression make_op_exp(char *op_name, expression exp1, expression exp2)
================================================================
Definition: expression.c:2012
type ultimate_type(type)
Definition: type.c:3466
entity make_new_scalar_variable(entity, basic)
Definition: variable.c:741
void AddEntityToCurrentModule(entity)
Add a variable entity to the current module declarations.
Definition: variable.c:260
bool unsigned_type_p(type)
Predicates on types.
Definition: type.c:2821
entity make_new_scalar_variable_with_prefix(const char *, entity, basic)
Create a new scalar variable of type b in the given module.
Definition: variable.c:592
entity find_label_entity(const char *, const char *)
util.c
Definition: util.c:43
#define loop_body(x)
Definition: ri.h:1644
#define loop_execution(x)
Definition: ri.h:1648
#define loop_domain
newgen_language_domain_defined
Definition: ri.h:218
#define range_upper(x)
Definition: ri.h:2290
#define range_increment(x)
Definition: ri.h:2292
#define EXPRESSION(x)
EXPRESSION.
Definition: ri.h:1217
#define instruction_undefined
Definition: ri.h:1454
#define statement_label(x)
Definition: ri.h:2450
#define statement_instruction(x)
Definition: ri.h:2458
#define loop_range(x)
Definition: ri.h:1642
#define statement_undefined_p(x)
Definition: ri.h:2420
#define entity_type(x)
Definition: ri.h:2792
#define execution_parallel_p(x)
Definition: ri.h:1211
#define loop_index(x)
Definition: ri.h:1640
#define statement_undefined
Definition: ri.h:2419
#define STATEMENT(x)
STATEMENT.
Definition: ri.h:2413
#define entity_initial(x)
Definition: ri.h:2796
#define intptr_t
Definition: stdint.in.h:294
FI: I do not understand why the type is duplicated at the set level.
Definition: set.c:59
The structure used to build lists in NewGen.
Definition: newgen_list.h:41
test de chernikovaa
void do_symbolic_tiling(statement base, list vector)
symbolic_tiling.c
static void fix_loop_index_sign(loop l)
symbolic tiling less general, but works for symbolics bounds
static bool symbolic_tiling_valid_p(statement sloop, size_t depth)
checks if sloop is a perfectly nested loop of depth @depth
bool symbolic_tiling(const char *module_name)
static int depth
la sequence de nids
statement find_loop_from_label(statement, entity)
Definition: util.c:218