PIPS
index_set_splitting.c
Go to the documentation of this file.
1 /*
2 
3  $Id: index_set_splitting.c 23495 2018-10-24 09:19:47Z coelho $
4 
5  Copyright 1989-2016 MINES ParisTech
6 
7  This file is part of PIPS.
8 
9  PIPS is free software: you can redistribute it and/or modify it
10  under the terms of the GNU General Public License as published by
11  the Free Software Foundation, either version 3 of the License, or
12  any later version.
13 
14  PIPS is distributed in the hope that it will be useful, but WITHOUT ANY
15  WARRANTY; without even the implied warranty of MERCHANTABILITY or
16  FITNESS FOR A PARTICULAR PURPOSE.
17 
18  See the GNU General Public License for more details.
19 
20  You should have received a copy of the GNU General Public License
21  along with PIPS. If not, see <http://www.gnu.org/licenses/>.
22 
23 */
24 
25 // do not compile unless required
26 #include "phases.h"
27 #if defined(BUILDER_INDEX_SET_SPLITTING) || \
28  defined(BUILDER_FORCE_LOOP_FUSION)
29 
30 #ifdef HAVE_CONFIG_H
31  #include "pips_config.h"
32 #endif
33 #include <stdio.h>
34 #include <string.h>
35 #include <stdlib.h>
36 #include <errno.h>
37 
38 #include "genC.h"
39 #include "linear.h"
40 
41 #include "misc.h"
42 #include "pipsdbm.h"
43 #include "properties.h"
44 
45 #include "ri.h"
46 #include "ri-util.h"
47 
48 #include "control.h" // module_reorder
49 #include "transformations.h" // find_loop_from_label
50 
51 static void
52 index_set_split_loop(statement original_loop, entity new_loop_bound)
53 {
54  pips_assert("index_set_split_loop called on a loop", statement_loop_p(original_loop));
56  {
57  pips_user_error("please set INDEX_SET_SPLITTING_BOUND property to an entity that is not the loop bound\n");
58  }
59 
60  loop l = statement_loop(original_loop);
61  /* split the loop */
62  statement first_loop_statement = copy_statement(original_loop);
63 
64 
68  NIL,
70 
71  statement second_loop_statement = clone_statement(original_loop,cc);
72 
74 
75  /* clone statement may have had declarations to the statement
76  * has a consequence the return statement may not be a for loop, but a sequence
77  */
78  statement the_second_loop_statement = second_loop_statement;
79  if( ! statement_loop_p(the_second_loop_statement) )
80  {
83  the_second_loop_statement=s;
84  pips_assert("last statement of cloned sequence is a loop",statement_loop_p(the_second_loop_statement));
85  }
86 
87  /* fix the bound */
88  bool index_set_split_before_bound = get_bool_property("INDEX_SET_SPLITTING_SPLIT_BEFORE_BOUND");
89  expression increment = range_increment(loop_range(statement_loop(the_second_loop_statement)));
90 
91  intptr_t vincrement;
92  if (!expression_integer_value(increment, &vincrement)) {
93  pips_user_warning("unable to guess loop increment sign, assuming positive\n");
94  vincrement = 1;
95  }
96 
97 
98  expression new_loop_bound_expression =
102  );
103  expression new_loop_bound_expression_with_xcrement =
104 
106  copy_expression(new_loop_bound_expression),
107  copy_expression(increment));
108 
109  expression fst_loop_upper = index_set_split_before_bound ?
110  new_loop_bound_expression_with_xcrement:
111  new_loop_bound_expression;
112 
113  expression snd_loop_lower = index_set_split_before_bound ?
114  new_loop_bound_expression:
115  new_loop_bound_expression_with_xcrement;
116 
117 
118  range_upper(loop_range(statement_loop(first_loop_statement)))=
119  fst_loop_upper;
120  range_lower(loop_range(statement_loop(the_second_loop_statement)))=
121  snd_loop_lower;
122 
123  /* put loops together */
124  instruction new_instruction = make_instruction_sequence(
125  make_sequence(make_statement_list(first_loop_statement,second_loop_statement))
126  );
127  statement_label(original_loop)=entity_empty_label();
130  statement_comments(original_loop)=empty_comments;
131  statement_instruction(original_loop)= new_instruction;
132  statement_declarations(original_loop)=NIL;
133  statement_decls_text(original_loop)=NULL;
134 
135 }
136 
137 bool index_set_splitting(const string module_name)
138 {
139  /* prelude */
142 
143  /* get the loop */
144  const char* loop_label = get_string_property("LOOP_LABEL");
145  entity loop_label_entity = entity_undefined;
146  if( string_undefined_p( loop_label ) ||
148  pips_user_error("please set LOOP_LABEL property to a valid label\n");
149 
150  statement loop_statement=find_loop_from_label(get_current_module_statement(),loop_label_entity);
151  if(statement_undefined_p(loop_statement))
152  pips_user_error("no statement with label %s found\n",loop_label);
153 
154  /* get the bound */
155  const char* loop_bound = get_string_property("INDEX_SET_SPLITTING_BOUND");
156  entity loop_bound_entity = entity_undefined;
157  if( string_undefined_p( loop_bound ) )
158  pips_user_error("please set INDEX_SET_SPLITTING_BOUND property to a known entity\n");
159  else {
160  loop_bound_entity = FindEntityFromUserName(module_name,loop_bound);
161  if(entity_undefined_p(loop_bound_entity)) // maybe its a constant
162  {
163  int integer ;
164  if( sscanf(loop_bound,"%d",&integer)==1 )
165  {
166  loop_bound_entity =
168  loop_bound,
169  is_basic_int,
172  NULL
173  );
174  }
175  else
176  {
177  pips_user_error("please set INDEX_SET_SPLITTING_BOUND property to a known entity\n");
178  }
179  }
180  }
181 
182 
183  /* perform substitution */
184  if(statement_loop_p(loop_statement))
185  index_set_split_loop(loop_statement,loop_bound_entity);
186 
187  /* validate */
190 
191  /*postlude*/
194  return true;
195 }
196 
197 static bool try_loop_fusion(statement s0, statement s1) {
198  loop l0 = statement_loop(s0),
199  l1 = statement_loop(s1);
200  statement base=s1;
201 
202  if(range_equal_p(loop_range(l0),loop_range(l1))) {
204  do {
205  if(!same_entity_p(loop_index(l0), loop_index(l1)))
207  s0=loop_body(l0);
208  s1=loop_body(l1);
209  } while(statement_loop_p(s0)&&statement_loop_p(s1) &&
213  insert_statement(s0,s1,false);
215  return true;
216  }
217  return false;
218 }
219 
220 static void do_loop_fusion_walker(sequence seq, entity lbl) {
221  for(list iter = sequence_statements(seq);!ENDP(iter);POP(iter)) {
222  statement st = STATEMENT(CAR(iter));
223  if(same_entity_p(statement_label(st),lbl)) {
224  /* look for loop to merge */
226  if(!ENDP(CDR(iter))) {
227  next = STATEMENT(CAR(CDR(iter)));
228  /* verify it is a good candidate */
229  if(statement_loop_p(next)) {
230  if(try_loop_fusion(st,next))
232  else pips_user_error("loop fusion failed\n");
233  }
234  else pips_user_error("loop fusion failed\n");
235  }
236  else pips_user_error("loop fusion failed\n");
237  gen_recurse_stop(0);
238  }
239  }
240 }
241 
242 static void do_loop_fusion(entity lbl) {
244  sequence_domain, gen_true2, do_loop_fusion_walker);
245 }
246 
247 /* loop_fusion */
248 bool force_loop_fusion(const string module_name)
249 {
250  /* prelude */
253 
254  /* get the loop */
255  const char* loop_label = get_string_property("LOOP_LABEL");
256  entity loop_label_entity = entity_undefined;
257  if( string_undefined_p( loop_label ) ||
259  pips_user_error("please set LOOP_LABEL property to a valid label, not '%s'\n",loop_label);
260  }
261  /* do the job */
262  do_loop_fusion(loop_label_entity);
263 
264  /* validate */
267 
268  /*postlude*/
271  return true;
272 }
273 
274 #endif // BUILDER_*
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
expression copy_expression(expression p)
EXPRESSION.
Definition: ri.c:850
statement copy_statement(statement p)
STATEMENT.
Definition: ri.c:2186
instruction make_instruction_sequence(sequence _field_)
Definition: ri.c:1169
sequence make_sequence(list a)
Definition: ri.c:2125
bdt base
Current expression.
Definition: bdt_read_paf.c:100
statement clone_statement(statement s, clone_context cc)
clone_statement.c
entity make_C_or_Fortran_constant_entity(const char *name, tag bt, size_t size, bool is_fortran, bool(*error_manager)(const char *, const char *))
This function creates a constant.
Definition: constant.c:148
const char * module_name(const char *s)
Return the module part of an entity name.
Definition: entity_names.c:296
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_context_recurse(start, ctxt, domain_number, flt, rwt)
Definition: genC.h:285
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
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_entities(void *s, hash_table ht)
Recursively substitute a set of entities in a statement.
Definition: replace.c:91
void gen_recurse_stop(void *obj)
Tells the recursion not to go in this object.
Definition: genClib.c:3251
bool gen_true2(__attribute__((unused)) gen_chunk *u1, __attribute__((unused)) void *u2)
Definition: genClib.c:2785
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 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
#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
#define CDR(pcons)
Get the list less its first element.
Definition: newgen_list.h:111
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 update_statement_instruction(statement, instruction)
Replace the instruction in statement s by instruction i.
Definition: statement.c:3039
void insert_statement(statement, statement, bool)
This is the normal entry point.
Definition: statement.c:2570
hash_table hash_table_make(hash_key_type key_type, size_t size)
Definition: hash.c:294
void hash_put(hash_table htp, const void *key, const void *val)
This functions stores a couple (key,val) in the hash table pointed to by htp.
Definition: hash.c:364
void hash_table_free(hash_table htp)
this function deletes a hash table that is no longer useful.
Definition: hash.c:327
#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 STATEMENT_ORDERING_UNDEFINED
mapping.h inclusion
Definition: newgen-local.h:35
@ hash_pointer
Definition: newgen_hash.h:32
#define HASH_DEFAULT_SIZE
Definition: newgen_hash.h:26
#define string_undefined_p(s)
Definition: newgen_types.h:41
bool module_reorder(statement body)
Reorder a module and recompute order to statement if any.
Definition: reorder.c:244
#define MAX_OPERATOR_NAME
#define MINUS_OPERATOR_NAME
#define PLUS_OPERATOR_NAME
#define DEFAULT_INTEGER_TYPE_SIZE
#define STATEMENT_NUMBER_UNDEFINED
default values
#define binary_intrinsic_expression(name, e1, e2)
#define make_statement_list(stats...)
easy list constructor
#define empty_comments
Empty comments (i.e.
#define MIN_OPERATOR_NAME
bool same_entity_p(entity e1, entity e2)
predicates on entities
Definition: entity.c:1321
entity module_name_to_entity(const char *mn)
This is an alias for local_name_to_top_level_entity.
Definition: entity.c:1479
entity FindEntityFromUserName(const char *package, const char *name)
Definition: entity.c:1520
entity entity_empty_label(void)
Definition: entity.c:1105
bool fortran_module_p(entity m)
Test if a module is in Fortran.
Definition: entity.c:2799
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
bool range_equal_p(range r1, range r2)
Definition: expression.c:1522
entity find_label_entity(const char *, const char *)
util.c
Definition: util.c:43
#define loop_body(x)
Definition: ri.h:1644
@ is_basic_int
Definition: ri.h:571
#define range_upper(x)
Definition: ri.h:2290
#define statement_ordering(x)
Definition: ri.h:2454
#define range_increment(x)
Definition: ri.h:2292
#define statement_label(x)
Definition: ri.h:2450
#define entity_undefined_p(x)
Definition: ri.h:2762
#define entity_undefined
Definition: ri.h:2761
#define sequence_statements(x)
Definition: ri.h:2360
#define instruction_sequence(x)
Definition: ri.h:1514
#define loop_label(x)
Definition: ri.h:1646
#define range_lower(x)
Definition: ri.h:2288
#define statement_declarations(x)
Definition: ri.h:2460
#define statement_instruction(x)
Definition: ri.h:2458
#define statement_comments(x)
Definition: ri.h:2456
#define statement_decls_text(x)
Definition: ri.h:2462
#define loop_range(x)
Definition: ri.h:1642
#define statement_undefined_p(x)
Definition: ri.h:2420
#define statement_number(x)
Definition: ri.h:2452
#define sequence_domain
newgen_reference_domain_defined
Definition: ri.h:346
#define loop_index(x)
Definition: ri.h:1640
#define statement_undefined
Definition: ri.h:2419
#define STATEMENT(x)
STATEMENT.
Definition: ri.h:2413
Psysteme new_loop_bound(Psysteme scn, Pbase base_index)
Psysteme new_loop_bound(Psysteme scn, Pbase base_index) computation of the new iteration space (given...
s1
Definition: set.c:247
#define intptr_t
Definition: stdint.in.h:294
The structure used to build lists in NewGen.
Definition: newgen_list.h:41
bool index_set_splitting(const string)
index_set_splitting.c
statement find_loop_from_label(statement, entity)
Definition: util.c:218
bool force_loop_fusion(const string)