PIPS
loop_expansion.c
Go to the documentation of this file.
1 #ifdef HAVE_CONFIG_H
2  #include "pips_config.h"
3 #endif
4 #include "genC.h"
5 #include "constants.h"
6 #include "misc.h"
7 #include "linear.h"
8 #include "ri.h"
9 #include "effects.h"
10 #include "ri-util.h"
11 #include "effects-util.h"
12 #include "database.h"
13 #include "pipsdbm.h"
14 #include "workspace-util.h"
15 #include "properties.h"
16 #include "control.h"
17 #include "resources.h"
18 #include "effects-generic.h"
19 #include "transformations.h"
20 #include "accel-util.h"
21 
22 #if 0
23 static void remove_guard(test t)
24 {
27 
28  list read_regions = regions_read_regions(regions);
29  list write_regions = regions_write_regions(regions);
31  /* skip read regions ... should be in a property */
32  FOREACH(REGION,reg,write_regions)
33  {
36  /* so e is written by s, does the write exactly match
37  * the dimension of e or not ?
38  */
39  list
41  }
42 }
43 
44 bool remove_guards(const char *module_name)
45 {
46  /* prelude */
53 
54  /* main */
56  test_domain,gen_true,remove_guard);
57 
58  /* validate */
61 
62  /* postlude */
69 
70  return true;
71 
72 }
73 #endif
74 
75 /**
76  * create a guard @a guard around statement @a s
77  *
78  * @param s statement to guard
79  * @param guard guard to apply
80  */
82 {
83  if(statement_test_p(s))
84  {
85  test t =statement_test(s);
88  copy_expression(guard),
90  );
91  }
92  else
93  {
94  statement false_branch = make_empty_statement();
96  make_test(
97  copy_expression(guard),
98  copy_statement(s),/* update_instruction force us to copy */
99  false_branch
100  )
101  );
103  }
104 }
105 
106 /**
107  * create a guard @a guard around statement @a s if needed
108  * it is needed when a not-private variable (that is not in @a parent_loop locals)
109  * is written by the statement
110  * @param s statement to guard
111  * @param guard guard to apply
112  * @param parent_loop set of enclosing loop locals
113  */
114 static
116 {
117  /* map guard on each block */
118  if(statement_block_p(s))
119  {
121  guard_expanded_statement_if_needed(st,guard,parent_loop);
122  }
123  /* map on loop body if range independant from loop_index(parent_loop) */
124  else if(statement_loop_p(s))
125  {
126  loop l =statement_loop(s);
128  if(set_belong_p(s0,loop_index(parent_loop)))
129  guard_expanded_statement(s,guard);
130  else
131  guard_expanded_statement_if_needed(loop_body(l),guard,parent_loop);
132  set_free(s0);
133  }
134  else {
136  list decls = statement_to_declarations(s);
137  set sdecls = set_make(set_pointer);set_assign_list(sdecls,decls); gen_free_list(decls);
138  list privates = loop_locals(parent_loop);
139  set sprivates = set_make(set_pointer); set_assign_list(sprivates,privates);
140 
141  bool must_guard= false;
142  FOREACH(EFFECT,eff,effects)
143  {
144  if((must_guard=(effect_write_p(eff) &&
145  !set_belong_p(sprivates,effect_entity(eff)) &&
146  !set_belong_p(sdecls,effect_entity(eff)) )))
147  break;
148  /* an io effect implies a guard too */
149  if((must_guard=io_effect_p(eff)))
150  break;
151  }
152  set_free(sdecls);set_free(sprivates);
153  if(must_guard) guard_expanded_statement(s,guard);
154  }
155 }
156 
157 static
158 void do_loop_expansion(statement st, expression size,bool center,bool apply_guard)
159 {
160  loop l =statement_loop(st);
161  range r = loop_range(l);
163  {
164  /* this gets (e-b)/i , that is the number of iterations in the loop */
166  /* the expanded nb_iter will be refered as efactor = factor* size */
167  expression factor =
170  copy_expression(nb_iter),
172  copy_expression(size),
174  )
175  ),
176  copy_expression(size)
177  );
180  basic_of_expression(factor)
181  );
182  AddEntityToCurrentModule(efactor);
183  /* get_current_module_statement is inaccurate here, but if factor is store independant ... icm should work better ! st would be better */
185 
186  expression expanded_nb_iter =
188  copy_expression(size),
189  entity_to_expression(efactor)
190  );
191  expression new_range_lower_value=expression_undefined;
192  if(center)
193  new_range_lower_value=make_op_exp(PLUS_OPERATOR_NAME,
195  make_op_exp(
197  make_op_exp(
199  copy_expression(expanded_nb_iter),
200  copy_expression(nb_iter)
201  ),
203  )
204  );
205  else
206  new_range_lower_value=copy_expression(range_lower(r));
207  /* we must check for loop_index() in range_lower*/
208  set ents = get_referenced_entities(new_range_lower_value);
209  entity new_range_lower_value_entity = entity_undefined;
210  statement assign_statement = statement_undefined;;
211  if(set_belong_p(ents,loop_index(l)))
212  {
213  new_range_lower_value_entity=make_new_scalar_variable(get_current_module_entity(),basic_of_expression(new_range_lower_value));
214  AddEntityToCurrentModule(new_range_lower_value_entity);
215  assign_statement=make_assign_statement(entity_to_expression(new_range_lower_value_entity),copy_expression(new_range_lower_value));
216  }
217  set_free(ents);
218  expression new_range_upper_value=
221  entity_undefined_p(new_range_lower_value_entity)?copy_expression(new_range_lower_value):entity_to_expression(new_range_lower_value_entity),
223  ),
225  );
226 
227  /* set the guard on all statement that need it */
228  if(apply_guard) {
229  expression guard = MakeBinaryCall(
234  entity_undefined_p(new_range_lower_value_entity)?range_lower(r):entity_to_expression(new_range_lower_value_entity)
235  )
236  ,
240  range_upper(r)
241  )
242  );
243 
245  free_expression(guard);
246  }
247 
248  /* update loop fields either by a constant, or by a new entity with appropriate init*/
249  range_upper(r)=new_range_upper_value;
250  range_lower(r)=new_range_lower_value;
251  /* insert statement in the end, otherwise pips gets disturbed */
252  if(!statement_undefined_p(assign_statement)) insert_statement(st,assign_statement,true);
253 
254  }
255  else
256  pips_user_warning("cannot expand a loop with non constant increment\n");
257 
258 }
259 
260 
261 bool loop_expansion(const char* module_name)
262 {
266 
267  debug_on("LOOP_EXPANSION_DEBUG_LEVEL");
268  /* first case: statement inserted by loop_expansion_init were illegal */
269  list statements_to_clean = find_statements_with_pragma(get_current_module_statement(),get_string_property("STATEMENT_INSERTION_FAILURE_PRAGMA"));
270  list statements_to_merge = find_statements_with_pragma(get_current_module_statement(),get_string_property("STATEMENT_INSERTION_SUCCESS_PRAGMA"));
271  /* generate guard if no statement to merge or no statement to clean */
272  bool apply_guard = ENDP(statements_to_merge) && ENDP(statements_to_clean);
273 
274  /* remove the test statement */
275  FOREACH(STATEMENT,statement_to_clean,statements_to_clean)
276  {
278  free_extensions(statement_extensions(statement_to_clean));
279  statement_extensions(statement_to_clean)=empty_extensions();
280  }
281 
282  /* second case: statement inserted by loop_expansion_init were legal */
283  /* remove the test statement and merge */
284  FOREACH(STATEMENT,statement_to_clean,statements_to_merge)
285  {
287  free_extensions(statement_extensions(statement_to_clean));
288  statement_extensions(statement_to_clean)=empty_extensions();
289 
290  }
291 
292  gen_free_list(statements_to_clean);
293  gen_free_list(statements_to_merge);
294 
295  const char* lp_label=get_string_property_or_ask(
296  "LOOP_LABEL",
297  "Which loop do you want to expand?\n(give its label):"
298  );
299  if( !empty_string_p(lp_label) )
300  {
301  entity lb_entity = find_label_entity(module_name,lp_label);
302  if( !entity_undefined_p(lb_entity) )
303  {
304  statement loop_statement = find_loop_from_label(get_current_module_statement(),lb_entity);
305  if(!statement_undefined_p(loop_statement))
306  {
307  const char* srate = get_string_property("LOOP_EXPANSION_SIZE");
309  /* ok for the ui part, let's do something !*/
310  do_loop_expansion(loop_statement,rate,get_bool_property("LOOP_EXPANSION_CENTER"),apply_guard);
311  /* commit changes */
312  module_reorder(get_current_module_statement()); ///< we may have add statements
314 
315  }
316  else pips_user_error("label '%s' is not put on a loop\n",lp_label);
317 
318 
319  }
320  else pips_user_error("loop label `%s' does not exist\n", lp_label);
321  }
322  else pips_user_error("transformation cancelled \n", lp_label);
323 
324  debug_off();
328  return true;;
329 
330 }
331 
332 /* creates a new statement that perfom the expansion of the loop
333  * this statement is flagged for further processing */
334 static
336 {
337  loop l =statement_loop(st);
338  range r = loop_range(l);
340  {
341  /* compute the range of new loop
342  * range lower will be next step of loop
343  */
344 
345  /* this gets (e-b)/i , that is the number of iterations in the loop */
347  /* this gets the expanded nb_iter */
348 
349  expression expanded_nb_iter =
351  copy_expression(size),
354  copy_expression(nb_iter),
356  copy_expression(size),
358  )
359  ),
360  copy_expression(size)
361  )
362  );
363 
366  );
367  expression new_range_upper = make_op_exp(MINUS_OPERATOR_NAME,
371  ),
373 
374  );
375 
377  statement inserted_statement =
380  make_loop(
381  loop_index(l),
382  make_range(new_range_lower,new_range_upper,copy_expression(range_increment(r))),
383  clone_statement(loop_body(l),cc),
386  NIL
387  )
388  )
389  );
390  free_clone_context(cc);
391  add_pragma_str_to_statement(inserted_statement,(char*)get_string_property("STATEMENT_INSERTION_PRAGMA"),true);
392  insert_statement(st,inserted_statement,false);
393  }
394  else
395  pips_user_warning("cannot expand a loop with non constant increment\n");
396 
397 }
398 /* first step of the loop expansion process:
399  * create a statement to insert and flag it with a pragma
400  */
402 {
405 
406  debug_on("LOOP_EXPANSION_INIT_DEBUG_LEVEL");
407 
408 
409  const char* lp_label=get_string_property_or_ask(
410  "LOOP_LABEL",
411  "Which loop do you want to expand?\n(give its label):"
412  );
413 
414  if( !empty_string_p(lp_label) )
415  {
416  entity lb_entity = find_label_entity(module_name,lp_label);
417  if( !entity_undefined_p(lb_entity) )
418  {
419  statement loop_statement = find_loop_from_label(get_current_module_statement(),lb_entity);
420  if(!statement_undefined_p(loop_statement))
421  {
422  const char* srate = get_string_property("LOOP_EXPANSION_SIZE");
424  /* ok for the ui part, let's do something !*/
425  do_loop_expansion_init(loop_statement,rate);
426  /* commit changes */
427  module_reorder(get_current_module_statement()); ///< we may have add statements
429 
430  }
431  else pips_user_error("label '%s' is not put on a loop\n",lp_label);
432 
433 
434  }
435  else pips_user_error("loop label `%s' does not exist\n", lp_label);
436  }
437  else pips_user_error("transformation cancelled \n", lp_label);
438 
439  debug_off();
442  return true;;
443 
444 }
445 
clone_context make_clone_context(entity a1, entity a2, list a3, statement a4)
Definition: cloning.c:52
void free_clone_context(clone_context p)
Definition: cloning.c:19
instruction make_instruction_loop(loop _field_)
Definition: ri.c:1175
loop make_loop(entity a1, range a2, statement a3, entity a4, execution a5, list a6)
Definition: ri.c:1301
expression copy_expression(expression p)
EXPRESSION.
Definition: ri.c:850
statement copy_statement(statement p)
STATEMENT.
Definition: ri.c:2186
void free_extensions(extensions p)
Definition: ri.c:950
test make_test(expression a1, statement a2, statement a3)
Definition: ri.c:2607
execution make_execution_sequential(void)
Definition: ri.c:841
instruction make_instruction_test(test _field_)
Definition: ri.c:1172
void free_expression(expression p)
Definition: ri.c:853
range make_range(expression a1, expression a2, expression a3)
Definition: ri.c:2041
bool region_to_minimal_dimensions(effect, transformer, list *, list *, bool, expression *)
statement clone_statement(statement s, clone_context cc)
clone_statement.c
struct _newgen_struct_statement_ * statement
Definition: cloning.h:21
#define region_any_reference(reg)
To be avoided.
#define REGION
list regions_write_regions(list)
list regions_read_regions(list)
void reset_proper_rw_effects(void)
void set_proper_rw_effects(statement_effects)
void set_cumulated_rw_effects(statement_effects)
list load_cumulated_rw_effects_list(statement)
void reset_cumulated_rw_effects(void)
#define effect_write_p(eff)
entity effect_entity(effect)
cproto-generated files
Definition: effects.c:52
bool io_effect_p(effect)
Definition: effects.c:501
#define EFFECT(x)
EFFECT.
Definition: effects.h:608
bool empty_string_p(const char *s)
Definition: entity_names.c:239
const char * module_name(const char *s)
Return the module part of an entity name.
Definition: entity_names.c:296
expression string_to_expression(const char *s, entity module)
Functions using simultaneously pipsdbm, which is based on strings, and ri-util, which contains basic ...
Definition: expressions.c:50
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
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
gen_chunk * gen_get_ancestor(int, const void *)
return the first ancestor object found of the given type.
Definition: genClib.c:3560
bool gen_true(__attribute__((unused)) gen_chunk *unused)
Return true and ignore the argument.
Definition: genClib.c:2780
instruction make_continue_instruction()
Creates a CONTINUE instruction, that is the FORTRAN nop, the ";" in C or the "pass" in Python for exa...
Definition: instruction.c:79
#define ENDP(l)
Test if a list is empty.
Definition: newgen_list.h:66
#define NIL
The empty list (nil in Lisp)
Definition: newgen_list.h:47
void gen_free_list(list l)
free the spine of the list
Definition: list.c:327
#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
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
list statement_block(statement)
Get the list of block statements of a statement sequence.
Definition: statement.c:1338
loop statement_loop(statement)
Get the loop of a statement.
Definition: statement.c:1374
test statement_test(statement)
Get the test of a statement.
Definition: statement.c:1348
bool statement_test_p(statement)
Definition: statement.c:343
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
list statement_to_declarations(void *)
Get a list of all variables declared recursively within a statement.
Definition: statement.c:3253
list find_statements_with_pragma(statement, const char *)
Get a list of statements with pragma begining with a prefix.
Definition: statement.c:3912
void insert_statement(statement, statement, bool)
This is the normal entry point.
Definition: statement.c:2570
bool expression_constant_p(expression)
HPFC module by Fabien COELHO.
Definition: expression.c:2453
static void do_loop_expansion(statement st, expression size, bool center, bool apply_guard)
bool loop_expansion(const char *module_name)
loop_expansion.c
bool loop_expansion_init(const char *module_name)
first step of the loop expansion process: create a statement to insert and flag it with a pragma
static void do_loop_expansion_init(statement st, expression size)
creates a new statement that perfom the expansion of the loop this statement is flagged for further p...
static void guard_expanded_statement(statement s, expression guard)
create a guard guard around statement s
static void guard_expanded_statement_if_needed(statement s, expression guard, loop parent_loop)
create a guard guard around statement s if needed it is needed when a not-private variable (that is n...
#define debug_on(env)
Definition: misc-local.h:157
#define pips_user_warning
Definition: misc-local.h:146
#define debug_off()
Definition: misc-local.h:160
#define pips_user_error
Definition: misc-local.h:147
set set_assign_list(set, const list)
assigns a list contents to a set all duplicated elements are lost
Definition: set.c:474
void set_free(set)
Definition: set.c:332
bool set_belong_p(const set, const void *)
Definition: set.c:194
@ set_pointer
Definition: newgen_set.h:44
set set_make(set_type)
Create an empty set of any type but hash_private.
Definition: set.c:102
const char * get_string_property_or_ask(const char *, const char[])
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 statement_block_p(stat)
#define AND_OPERATOR_NAME
FI: intrinsics are defined at a third place after bootstrap and effects! I guess the name should be d...
#define DIVIDE_OPERATOR_NAME
@ range_to_nbiter
#define GREATER_OR_EQUAL_OPERATOR_NAME
#define MULTIPLY_OPERATOR_NAME
#define LESS_OR_EQUAL_OPERATOR_NAME
#define make_empty_statement
An alias for make_empty_block_statement.
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
entity entity_intrinsic(const char *name)
FI: I do not understand this function name (see next one!).
Definition: entity.c:1292
expression range_to_expression(range r, enum range_to_expression_mode mode)
computes the distance between the lower bound and the upper bound of the range
Definition: eval.c:963
expression entity_to_expression(entity e)
if v is a constant, returns a constant call.
Definition: expression.c:165
expression MakeBinaryCall(entity f, expression eg, expression ed)
Creates a call expression to a function with 2 arguments.
Definition: expression.c:354
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
extensions empty_extensions(void)
extension.c
Definition: extension.c:43
void add_pragma_str_to_statement(statement st, const char *s, bool copy_flag)
Add a string as a pragma to a statement.
Definition: pragma.c:425
basic basic_of_expression(expression)
basic basic_of_expression(expression exp): Makes a basic of the same basic as the expression "exp".
Definition: type.c:1383
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
entity find_label_entity(const char *, const char *)
util.c
Definition: util.c:43
#define loop_body(x)
Definition: ri.h:1644
#define test_domain
newgen_entity_domain_defined
Definition: ri.h:418
#define reference_variable(x)
Definition: ri.h:2326
#define range_upper(x)
Definition: ri.h:2290
#define statement_domain
newgen_sizeofexpression_domain_defined
Definition: ri.h:362
#define range_increment(x)
Definition: ri.h:2292
#define entity_undefined_p(x)
Definition: ri.h:2762
#define entity_undefined
Definition: ri.h:2761
#define expression_undefined
Definition: ri.h:1223
#define statement_extensions(x)
Definition: ri.h:2464
#define loop_locals(x)
Definition: ri.h:1650
#define test_condition(x)
Definition: ri.h:2833
#define range_lower(x)
Definition: ri.h:2288
#define loop_range(x)
Definition: ri.h:1642
#define statement_undefined_p(x)
Definition: ri.h:2420
#define loop_index(x)
Definition: ri.h:1640
#define statement_undefined
Definition: ri.h:2419
#define STATEMENT(x)
STATEMENT.
Definition: ri.h:2413
void module_to_value_mappings(entity m)
void module_to_value_mappings(entity m): build hash tables between variables and values (old,...
Definition: mappings.c:624
transformer load_statement_precondition(statement)
void reset_precondition_map(void)
void set_precondition_map(statement_mapping)
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
statement find_loop_from_label(statement, entity)
Definition: util.c:218
transformer transformer_range(transformer tf)
Return the range of relation tf in a newly allocated transformer.
Definition: transformer.c:714
void free_value_mappings(void)
Normal call to free the mappings.
Definition: value.c:1212