Mercurial > hg > CbC > CbC_gcc
comparison gcc/graphite-sese-to-poly.c @ 67:f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
author | nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 22 Mar 2011 17:18:12 +0900 |
parents | b7f97abdc517 |
children | 04ced10e8804 |
comparison
equal
deleted
inserted
replaced
65:65488c3d617d | 67:f6334be47118 |
---|---|
1 /* Conversion of SESE regions to Polyhedra. | 1 /* Conversion of SESE regions to Polyhedra. |
2 Copyright (C) 2009, 2010 Free Software Foundation, Inc. | 2 Copyright (C) 2009, 2010, 2011 Free Software Foundation, Inc. |
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>. | 3 Contributed by Sebastian Pop <sebastian.pop@amd.com>. |
4 | 4 |
5 This file is part of GCC. | 5 This file is part of GCC. |
6 | 6 |
7 GCC is free software; you can redistribute it and/or modify | 7 GCC is free software; you can redistribute it and/or modify |
19 <http://www.gnu.org/licenses/>. */ | 19 <http://www.gnu.org/licenses/>. */ |
20 | 20 |
21 #include "config.h" | 21 #include "config.h" |
22 #include "system.h" | 22 #include "system.h" |
23 #include "coretypes.h" | 23 #include "coretypes.h" |
24 #include "tm.h" | |
25 #include "ggc.h" | |
26 #include "tree.h" | |
27 #include "rtl.h" | |
28 #include "basic-block.h" | |
29 #include "diagnostic.h" | |
30 #include "tree-flow.h" | 24 #include "tree-flow.h" |
31 #include "toplev.h" | |
32 #include "tree-dump.h" | 25 #include "tree-dump.h" |
33 #include "timevar.h" | |
34 #include "cfgloop.h" | 26 #include "cfgloop.h" |
35 #include "tree-chrec.h" | 27 #include "tree-chrec.h" |
36 #include "tree-data-ref.h" | 28 #include "tree-data-ref.h" |
37 #include "tree-scalar-evolution.h" | 29 #include "tree-scalar-evolution.h" |
38 #include "tree-pass.h" | |
39 #include "domwalk.h" | 30 #include "domwalk.h" |
40 #include "value-prof.h" | |
41 #include "pointer-set.h" | |
42 #include "gimple.h" | |
43 #include "sese.h" | 31 #include "sese.h" |
44 | 32 |
45 #ifdef HAVE_cloog | 33 #ifdef HAVE_cloog |
46 #include "cloog/cloog.h" | |
47 #include "ppl_c.h" | 34 #include "ppl_c.h" |
48 #include "graphite-ppl.h" | 35 #include "graphite-ppl.h" |
49 #include "graphite.h" | |
50 #include "graphite-poly.h" | 36 #include "graphite-poly.h" |
51 #include "graphite-scop-detection.h" | |
52 #include "graphite-clast-to-gimple.h" | |
53 #include "graphite-sese-to-poly.h" | 37 #include "graphite-sese-to-poly.h" |
54 | 38 |
55 /* Check if VAR is used in a phi node, that is no loop header. */ | 39 /* Returns the index of the PHI argument defined in the outermost |
56 | 40 loop. */ |
57 static bool | |
58 var_used_in_not_loop_header_phi_node (tree var) | |
59 { | |
60 imm_use_iterator imm_iter; | |
61 gimple stmt; | |
62 bool result = false; | |
63 | |
64 FOR_EACH_IMM_USE_STMT (stmt, imm_iter, var) | |
65 { | |
66 basic_block bb = gimple_bb (stmt); | |
67 | |
68 if (gimple_code (stmt) == GIMPLE_PHI | |
69 && bb->loop_father->header != bb) | |
70 result = true; | |
71 } | |
72 | |
73 return result; | |
74 } | |
75 | |
76 /* Returns the index of the phi argument corresponding to the initial | |
77 value in the loop. */ | |
78 | 41 |
79 static size_t | 42 static size_t |
80 loop_entry_phi_arg (gimple phi) | 43 phi_arg_in_outermost_loop (gimple phi) |
81 { | 44 { |
82 loop_p loop = gimple_bb (phi)->loop_father; | 45 loop_p loop = gimple_bb (phi)->loop_father; |
83 size_t i; | 46 size_t i, res = 0; |
84 | 47 |
85 for (i = 0; i < gimple_phi_num_args (phi); i++) | 48 for (i = 0; i < gimple_phi_num_args (phi); i++) |
86 if (!flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, i)->src)) | 49 if (!flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, i)->src)) |
87 return i; | 50 { |
88 | 51 loop = gimple_phi_arg_edge (phi, i)->src->loop_father; |
89 gcc_unreachable (); | 52 res = i; |
90 return 0; | 53 } |
54 | |
55 return res; | |
91 } | 56 } |
92 | 57 |
93 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position | 58 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position |
94 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */ | 59 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */ |
95 | 60 |
96 static void | 61 static void |
97 remove_simple_copy_phi (gimple_stmt_iterator *psi) | 62 remove_simple_copy_phi (gimple_stmt_iterator *psi) |
98 { | 63 { |
99 gimple phi = gsi_stmt (*psi); | 64 gimple phi = gsi_stmt (*psi); |
100 tree res = gimple_phi_result (phi); | 65 tree res = gimple_phi_result (phi); |
101 size_t entry = loop_entry_phi_arg (phi); | 66 size_t entry = phi_arg_in_outermost_loop (phi); |
102 tree init = gimple_phi_arg_def (phi, entry); | 67 tree init = gimple_phi_arg_def (phi, entry); |
103 gimple stmt = gimple_build_assign (res, init); | 68 gimple stmt = gimple_build_assign (res, init); |
104 edge e = gimple_phi_arg_edge (phi, entry); | 69 edge e = gimple_phi_arg_edge (phi, entry); |
105 | 70 |
106 remove_phi_node (psi, false); | 71 remove_phi_node (psi, false); |
116 { | 81 { |
117 gimple phi = gsi_stmt (*psi); | 82 gimple phi = gsi_stmt (*psi); |
118 loop_p loop = loop_containing_stmt (phi); | 83 loop_p loop = loop_containing_stmt (phi); |
119 tree res = gimple_phi_result (phi); | 84 tree res = gimple_phi_result (phi); |
120 tree scev = scalar_evolution_in_region (region, loop, res); | 85 tree scev = scalar_evolution_in_region (region, loop, res); |
121 size_t entry = loop_entry_phi_arg (phi); | 86 size_t entry = phi_arg_in_outermost_loop (phi); |
122 edge e = gimple_phi_arg_edge (phi, entry); | 87 edge e = gimple_phi_arg_edge (phi, entry); |
123 tree var; | 88 tree var; |
124 gimple stmt; | 89 gimple stmt; |
125 gimple_seq stmts; | 90 gimple_seq stmts; |
126 gimple_stmt_iterator gsi; | 91 gimple_stmt_iterator gsi; |
163 | 128 |
164 static bool | 129 static bool |
165 reduction_phi_p (sese region, gimple_stmt_iterator *psi) | 130 reduction_phi_p (sese region, gimple_stmt_iterator *psi) |
166 { | 131 { |
167 loop_p loop; | 132 loop_p loop; |
168 tree scev; | |
169 affine_iv iv; | |
170 gimple phi = gsi_stmt (*psi); | 133 gimple phi = gsi_stmt (*psi); |
171 tree res = gimple_phi_result (phi); | 134 tree res = gimple_phi_result (phi); |
172 | |
173 if (!is_gimple_reg (res)) | |
174 { | |
175 gsi_next (psi); | |
176 return false; | |
177 } | |
178 | 135 |
179 loop = loop_containing_stmt (phi); | 136 loop = loop_containing_stmt (phi); |
180 | 137 |
181 if (simple_copy_phi_p (phi)) | 138 if (simple_copy_phi_p (phi)) |
182 { | 139 { |
187 */ | 144 */ |
188 remove_simple_copy_phi (psi); | 145 remove_simple_copy_phi (psi); |
189 return false; | 146 return false; |
190 } | 147 } |
191 | 148 |
192 /* Main induction variables with constant strides in LOOP are not | 149 if (scev_analyzable_p (res, region)) |
193 reductions. */ | 150 { |
194 if (simple_iv (loop, loop, res, &iv, true)) | 151 tree scev = scalar_evolution_in_region (region, loop, res); |
195 { | 152 |
196 if (integer_zerop (iv.step)) | 153 if (evolution_function_is_invariant_p (scev, loop->num)) |
197 remove_invariant_phi (region, psi); | 154 remove_invariant_phi (region, psi); |
198 else | 155 else |
199 gsi_next (psi); | 156 gsi_next (psi); |
200 | 157 |
201 return false; | 158 return false; |
202 } | 159 } |
203 | 160 |
204 scev = scalar_evolution_in_region (region, loop, res); | |
205 if (chrec_contains_undetermined (scev)) | |
206 return true; | |
207 | |
208 if (evolution_function_is_invariant_p (scev, loop->num)) | |
209 { | |
210 remove_invariant_phi (region, psi); | |
211 return false; | |
212 } | |
213 | |
214 /* All the other cases are considered reductions. */ | 161 /* All the other cases are considered reductions. */ |
215 return true; | 162 return true; |
216 } | |
217 | |
218 /* Returns true when BB will be represented in graphite. Return false | |
219 for the basic blocks that contain code eliminated in the code | |
220 generation pass: i.e. induction variables and exit conditions. */ | |
221 | |
222 static bool | |
223 graphite_stmt_p (sese region, basic_block bb, | |
224 VEC (data_reference_p, heap) *drs) | |
225 { | |
226 gimple_stmt_iterator gsi; | |
227 loop_p loop = bb->loop_father; | |
228 | |
229 if (VEC_length (data_reference_p, drs) > 0) | |
230 return true; | |
231 | |
232 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
233 { | |
234 gimple stmt = gsi_stmt (gsi); | |
235 | |
236 switch (gimple_code (stmt)) | |
237 { | |
238 case GIMPLE_DEBUG: | |
239 /* Control flow expressions can be ignored, as they are | |
240 represented in the iteration domains and will be | |
241 regenerated by graphite. */ | |
242 case GIMPLE_COND: | |
243 case GIMPLE_GOTO: | |
244 case GIMPLE_SWITCH: | |
245 break; | |
246 | |
247 case GIMPLE_ASSIGN: | |
248 { | |
249 tree var = gimple_assign_lhs (stmt); | |
250 | |
251 /* We need these bbs to be able to construct the phi nodes. */ | |
252 if (var_used_in_not_loop_header_phi_node (var)) | |
253 return true; | |
254 | |
255 var = scalar_evolution_in_region (region, loop, var); | |
256 if (chrec_contains_undetermined (var)) | |
257 return true; | |
258 | |
259 break; | |
260 } | |
261 | |
262 default: | |
263 return true; | |
264 } | |
265 } | |
266 | |
267 return false; | |
268 } | 163 } |
269 | 164 |
270 /* Store the GRAPHITE representation of BB. */ | 165 /* Store the GRAPHITE representation of BB. */ |
271 | 166 |
272 static gimple_bb_p | 167 static gimple_bb_p |
288 free_data_refs_aux (VEC (data_reference_p, heap) *datarefs) | 183 free_data_refs_aux (VEC (data_reference_p, heap) *datarefs) |
289 { | 184 { |
290 unsigned int i; | 185 unsigned int i; |
291 struct data_reference *dr; | 186 struct data_reference *dr; |
292 | 187 |
293 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) | 188 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr) |
294 if (dr->aux) | 189 if (dr->aux) |
295 { | 190 { |
296 base_alias_pair *bap = (base_alias_pair *)(dr->aux); | 191 base_alias_pair *bap = (base_alias_pair *)(dr->aux); |
297 | 192 |
298 if (bap->alias_set) | 193 if (bap->alias_set) |
322 remove_gbbs_in_scop (scop_p scop) | 217 remove_gbbs_in_scop (scop_p scop) |
323 { | 218 { |
324 int i; | 219 int i; |
325 poly_bb_p pbb; | 220 poly_bb_p pbb; |
326 | 221 |
327 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) | 222 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) |
328 free_gimple_bb (PBB_BLACK_BOX (pbb)); | 223 free_gimple_bb (PBB_BLACK_BOX (pbb)); |
329 } | 224 } |
330 | 225 |
331 /* Deletes all scops in SCOPS. */ | 226 /* Deletes all scops in SCOPS. */ |
332 | 227 |
334 free_scops (VEC (scop_p, heap) *scops) | 229 free_scops (VEC (scop_p, heap) *scops) |
335 { | 230 { |
336 int i; | 231 int i; |
337 scop_p scop; | 232 scop_p scop; |
338 | 233 |
339 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++) | 234 FOR_EACH_VEC_ELT (scop_p, scops, i, scop) |
340 { | 235 { |
341 remove_gbbs_in_scop (scop); | 236 remove_gbbs_in_scop (scop); |
342 free_sese (SCOP_REGION (scop)); | 237 free_sese (SCOP_REGION (scop)); |
343 free_scop (scop); | 238 free_scop (scop); |
344 } | 239 } |
345 | 240 |
346 VEC_free (scop_p, heap, scops); | 241 VEC_free (scop_p, heap, scops); |
347 } | 242 } |
348 | 243 |
244 /* Same as outermost_loop_in_sese, returns the outermost loop | |
245 containing BB in REGION, but makes sure that the returned loop | |
246 belongs to the REGION, and so this returns the first loop in the | |
247 REGION when the loop containing BB does not belong to REGION. */ | |
248 | |
249 static loop_p | |
250 outermost_loop_in_sese_1 (sese region, basic_block bb) | |
251 { | |
252 loop_p nest = outermost_loop_in_sese (region, bb); | |
253 | |
254 if (loop_in_sese_p (nest, region)) | |
255 return nest; | |
256 | |
257 /* When the basic block BB does not belong to a loop in the region, | |
258 return the first loop in the region. */ | |
259 nest = nest->inner; | |
260 while (nest) | |
261 if (loop_in_sese_p (nest, region)) | |
262 break; | |
263 else | |
264 nest = nest->next; | |
265 | |
266 gcc_assert (nest); | |
267 return nest; | |
268 } | |
269 | |
349 /* Generates a polyhedral black box only if the bb contains interesting | 270 /* Generates a polyhedral black box only if the bb contains interesting |
350 information. */ | 271 information. */ |
351 | 272 |
352 static void | 273 static gimple_bb_p |
353 try_generate_gimple_bb (scop_p scop, basic_block bb, sbitmap reductions) | 274 try_generate_gimple_bb (scop_p scop, basic_block bb) |
354 { | 275 { |
355 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5); | 276 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5); |
356 loop_p nest = outermost_loop_in_sese (SCOP_REGION (scop), bb); | 277 sese region = SCOP_REGION (scop); |
278 loop_p nest = outermost_loop_in_sese_1 (region, bb); | |
357 gimple_stmt_iterator gsi; | 279 gimple_stmt_iterator gsi; |
358 | 280 |
359 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | 281 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
360 { | 282 { |
361 gimple stmt = gsi_stmt (gsi); | 283 gimple stmt = gsi_stmt (gsi); |
362 if (!is_gimple_debug (stmt)) | 284 loop_p loop; |
363 graphite_find_data_references_in_stmt (nest, stmt, &drs); | 285 |
364 } | 286 if (is_gimple_debug (stmt)) |
365 | 287 continue; |
366 if (!graphite_stmt_p (SCOP_REGION (scop), bb, drs)) | 288 |
367 free_data_refs (drs); | 289 loop = loop_containing_stmt (stmt); |
368 else | 290 if (!loop_in_sese_p (loop, region)) |
369 new_poly_bb (scop, new_gimple_bb (bb, drs), TEST_BIT (reductions, | 291 loop = nest; |
370 bb->index)); | 292 |
293 graphite_find_data_references_in_stmt (nest, loop, stmt, &drs); | |
294 } | |
295 | |
296 return new_gimple_bb (bb, drs); | |
371 } | 297 } |
372 | 298 |
373 /* Returns true if all predecessors of BB, that are not dominated by BB, are | 299 /* Returns true if all predecessors of BB, that are not dominated by BB, are |
374 marked in MAP. The predecessors dominated by BB are loop latches and will | 300 marked in MAP. The predecessors dominated by BB are loop latches and will |
375 be handled after BB. */ | 301 be handled after BB. */ |
411 a deepest loop level. */ | 337 a deepest loop level. */ |
412 | 338 |
413 static void | 339 static void |
414 graphite_sort_dominated_info (VEC (basic_block, heap) *dom) | 340 graphite_sort_dominated_info (VEC (basic_block, heap) *dom) |
415 { | 341 { |
416 size_t len = VEC_length (basic_block, dom); | 342 VEC_qsort (basic_block, dom, compare_bb_depths); |
417 | |
418 qsort (VEC_address (basic_block, dom), len, sizeof (basic_block), | |
419 compare_bb_depths); | |
420 } | 343 } |
421 | 344 |
422 /* Recursive helper function for build_scops_bbs. */ | 345 /* Recursive helper function for build_scops_bbs. */ |
423 | 346 |
424 static void | 347 static void |
425 build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb, sbitmap reductions) | 348 build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb) |
426 { | 349 { |
427 sese region = SCOP_REGION (scop); | 350 sese region = SCOP_REGION (scop); |
428 VEC (basic_block, heap) *dom; | 351 VEC (basic_block, heap) *dom; |
352 poly_bb_p pbb; | |
429 | 353 |
430 if (TEST_BIT (visited, bb->index) | 354 if (TEST_BIT (visited, bb->index) |
431 || !bb_in_sese_p (bb, region)) | 355 || !bb_in_sese_p (bb, region)) |
432 return; | 356 return; |
433 | 357 |
434 try_generate_gimple_bb (scop, bb, reductions); | 358 pbb = new_poly_bb (scop, try_generate_gimple_bb (scop, bb)); |
359 VEC_safe_push (poly_bb_p, heap, SCOP_BBS (scop), pbb); | |
435 SET_BIT (visited, bb->index); | 360 SET_BIT (visited, bb->index); |
436 | 361 |
437 dom = get_dominated_by (CDI_DOMINATORS, bb); | 362 dom = get_dominated_by (CDI_DOMINATORS, bb); |
438 | 363 |
439 if (dom == NULL) | 364 if (dom == NULL) |
444 while (!VEC_empty (basic_block, dom)) | 369 while (!VEC_empty (basic_block, dom)) |
445 { | 370 { |
446 int i; | 371 int i; |
447 basic_block dom_bb; | 372 basic_block dom_bb; |
448 | 373 |
449 for (i = 0; VEC_iterate (basic_block, dom, i, dom_bb); i++) | 374 FOR_EACH_VEC_ELT (basic_block, dom, i, dom_bb) |
450 if (all_non_dominated_preds_marked_p (dom_bb, visited)) | 375 if (all_non_dominated_preds_marked_p (dom_bb, visited)) |
451 { | 376 { |
452 build_scop_bbs_1 (scop, visited, dom_bb, reductions); | 377 build_scop_bbs_1 (scop, visited, dom_bb); |
453 VEC_unordered_remove (basic_block, dom, i); | 378 VEC_unordered_remove (basic_block, dom, i); |
454 break; | 379 break; |
455 } | 380 } |
456 } | 381 } |
457 | 382 |
459 } | 384 } |
460 | 385 |
461 /* Gather the basic blocks belonging to the SCOP. */ | 386 /* Gather the basic blocks belonging to the SCOP. */ |
462 | 387 |
463 static void | 388 static void |
464 build_scop_bbs (scop_p scop, sbitmap reductions) | 389 build_scop_bbs (scop_p scop) |
465 { | 390 { |
466 sbitmap visited = sbitmap_alloc (last_basic_block); | 391 sbitmap visited = sbitmap_alloc (last_basic_block); |
467 sese region = SCOP_REGION (scop); | 392 sese region = SCOP_REGION (scop); |
468 | 393 |
469 sbitmap_zero (visited); | 394 sbitmap_zero (visited); |
470 build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region), reductions); | 395 build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region)); |
471 sbitmap_free (visited); | 396 sbitmap_free (visited); |
472 } | 397 } |
473 | 398 |
474 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron. | 399 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron. |
475 We generate SCATTERING_DIMENSIONS scattering dimensions. | 400 We generate SCATTERING_DIMENSIONS scattering dimensions. |
626 incremented before copying. */ | 551 incremented before copying. */ |
627 mpz_set_si (v, -1); | 552 mpz_set_si (v, -1); |
628 ppl_assign_Coefficient_from_mpz_t (c, v); | 553 ppl_assign_Coefficient_from_mpz_t (c, v); |
629 ppl_Linear_Expression_add_to_coefficient (static_schedule, 0, c); | 554 ppl_Linear_Expression_add_to_coefficient (static_schedule, 0, c); |
630 | 555 |
631 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) | 556 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) |
632 { | 557 { |
633 gimple_bb_p gbb = PBB_BLACK_BOX (pbb); | 558 gimple_bb_p gbb = PBB_BLACK_BOX (pbb); |
634 ppl_Linear_Expression_t common; | 559 ppl_Linear_Expression_t common; |
635 int prefix; | 560 int prefix; |
636 int nb_scat_dims = pbb_dim_iter_domain (pbb) * 2 + 1; | 561 int nb_scat_dims = pbb_dim_iter_domain (pbb) * 2 + 1; |
707 | for i: | 632 | for i: |
708 | a [i * p] = ... */ | 633 | a [i * p] = ... */ |
709 gcc_assert (TREE_CODE (e) == INTEGER_CST); | 634 gcc_assert (TREE_CODE (e) == INTEGER_CST); |
710 | 635 |
711 mpz_init (val); | 636 mpz_init (val); |
712 mpz_set_si (val, int_cst_value (e)); | 637 tree_int_to_gmp (e, val); |
713 add_value_to_dim (l, expr, val); | 638 add_value_to_dim (l, expr, val); |
714 mpz_clear (val); | 639 mpz_clear (val); |
715 } | 640 } |
716 } | 641 } |
717 | 642 |
721 static void | 646 static void |
722 scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, mpz_t k) | 647 scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, mpz_t k) |
723 { | 648 { |
724 mpz_t val; | 649 mpz_t val; |
725 ppl_Coefficient_t coef; | 650 ppl_Coefficient_t coef; |
726 int v = int_cst_value (cst); | 651 tree type = TREE_TYPE (cst); |
727 | 652 |
728 mpz_init (val); | 653 mpz_init (val); |
729 mpz_set_si (val, 0); | |
730 | 654 |
731 /* Necessary to not get "-1 = 2^n - 1". */ | 655 /* Necessary to not get "-1 = 2^n - 1". */ |
732 if (v < 0) | 656 mpz_set_double_int (val, double_int_sext (tree_to_double_int (cst), |
733 mpz_sub_ui (val, val, -v); | 657 TYPE_PRECISION (type)), false); |
734 else | |
735 mpz_add_ui (val, val, v); | |
736 | 658 |
737 mpz_mul (val, val, k); | 659 mpz_mul (val, val, k); |
738 ppl_new_Coefficient (&coef); | 660 ppl_new_Coefficient (&coef); |
739 ppl_assign_Coefficient_from_mpz_t (coef, val); | 661 ppl_assign_Coefficient_from_mpz_t (coef, val); |
740 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef); | 662 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef); |
751 int i; | 673 int i; |
752 tree p; | 674 tree p; |
753 | 675 |
754 gcc_assert (TREE_CODE (name) == SSA_NAME); | 676 gcc_assert (TREE_CODE (name) == SSA_NAME); |
755 | 677 |
756 for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++) | 678 FOR_EACH_VEC_ELT (tree, SESE_PARAMS (region), i, p) |
757 if (p == name) | 679 if (p == name) |
758 return i; | 680 return i; |
759 | 681 |
760 return -1; | 682 return -1; |
761 } | 683 } |
808 if (c) | 730 if (c) |
809 { | 731 { |
810 mpz_t val; | 732 mpz_t val; |
811 gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0)); | 733 gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0)); |
812 mpz_init (val); | 734 mpz_init (val); |
813 mpz_set_si (val, int_cst_value (TREE_OPERAND (e, 1))); | 735 tree_int_to_gmp (TREE_OPERAND (e, 1), val); |
814 mpz_mul (val, val, k); | 736 mpz_mul (val, val, k); |
815 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, val); | 737 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, val); |
816 mpz_clear (val); | 738 mpz_clear (val); |
817 } | 739 } |
818 else | 740 else |
823 if (c) | 745 if (c) |
824 { | 746 { |
825 mpz_t val; | 747 mpz_t val; |
826 gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0)); | 748 gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0)); |
827 mpz_init (val); | 749 mpz_init (val); |
828 mpz_set_si (val, int_cst_value (TREE_OPERAND (e, 0))); | 750 tree_int_to_gmp (TREE_OPERAND (e, 0), val); |
829 mpz_mul (val, val, k); | 751 mpz_mul (val, val, k); |
830 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, val); | 752 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, val); |
831 mpz_clear (val); | 753 mpz_clear (val); |
832 } | 754 } |
833 else | 755 else |
942 CASE_CONVERT: | 864 CASE_CONVERT: |
943 case NON_LVALUE_EXPR: | 865 case NON_LVALUE_EXPR: |
944 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k); | 866 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k); |
945 break; | 867 break; |
946 | 868 |
869 case ADDR_EXPR: | |
870 break; | |
871 | |
947 default: | 872 default: |
948 gcc_unreachable (); | 873 gcc_unreachable (); |
949 break; | 874 break; |
950 } | 875 } |
951 } | 876 } |
965 | 890 |
966 mpz_init (one); | 891 mpz_init (one); |
967 mpz_set_si (one, 1); | 892 mpz_set_si (one, 1); |
968 | 893 |
969 /* Find parameters in the access functions of data references. */ | 894 /* Find parameters in the access functions of data references. */ |
970 for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gbb), i, dr); i++) | 895 FOR_EACH_VEC_ELT (data_reference_p, GBB_DATA_REFS (gbb), i, dr) |
971 for (j = 0; j < DR_NUM_DIMENSIONS (dr); j++) | 896 for (j = 0; j < DR_NUM_DIMENSIONS (dr); j++) |
972 scan_tree_for_params (region, DR_ACCESS_FN (dr, j), NULL, one); | 897 scan_tree_for_params (region, DR_ACCESS_FN (dr, j), NULL, one); |
973 | 898 |
974 /* Find parameters in conditional statements. */ | 899 /* Find parameters in conditional statements. */ |
975 for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gbb), i, stmt); i++) | 900 FOR_EACH_VEC_ELT (gimple, GBB_CONDITIONS (gbb), i, stmt) |
976 { | 901 { |
977 tree lhs = scalar_evolution_in_region (region, loop, | 902 tree lhs = scalar_evolution_in_region (region, loop, |
978 gimple_cond_lhs (stmt)); | 903 gimple_cond_lhs (stmt)); |
979 tree rhs = scalar_evolution_in_region (region, loop, | 904 tree rhs = scalar_evolution_in_region (region, loop, |
980 gimple_cond_rhs (stmt)); | 905 gimple_cond_rhs (stmt)); |
1000 | 925 |
1001 mpz_init (one); | 926 mpz_init (one); |
1002 mpz_set_si (one, 1); | 927 mpz_set_si (one, 1); |
1003 | 928 |
1004 /* Find the parameters used in the loop bounds. */ | 929 /* Find the parameters used in the loop bounds. */ |
1005 for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++) | 930 FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop) |
1006 { | 931 { |
1007 tree nb_iters = number_of_latch_executions (loop); | 932 tree nb_iters = number_of_latch_executions (loop); |
1008 | 933 |
1009 if (!chrec_contains_symbols (nb_iters)) | 934 if (!chrec_contains_symbols (nb_iters)) |
1010 continue; | 935 continue; |
1014 } | 939 } |
1015 | 940 |
1016 mpz_clear (one); | 941 mpz_clear (one); |
1017 | 942 |
1018 /* Find the parameters used in data accesses. */ | 943 /* Find the parameters used in data accesses. */ |
1019 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) | 944 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) |
1020 find_params_in_bb (region, PBB_BLACK_BOX (pbb)); | 945 find_params_in_bb (region, PBB_BLACK_BOX (pbb)); |
1021 | 946 |
1022 scop_set_nb_params (scop, sese_nb_params (region)); | 947 scop_set_nb_params (scop, sese_nb_params (region)); |
1023 SESE_ADD_PARAMS (region) = false; | 948 SESE_ADD_PARAMS (region) = false; |
1024 | 949 |
1025 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension | 950 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension |
1026 (&SCOP_CONTEXT (scop), scop_nb_params (scop), 0); | 951 (&SCOP_CONTEXT (scop), scop_nb_params (scop), 0); |
1027 } | |
1028 | |
1029 /* Returns a gimple_bb from BB. */ | |
1030 | |
1031 static inline gimple_bb_p | |
1032 gbb_from_bb (basic_block bb) | |
1033 { | |
1034 return (gimple_bb_p) bb->aux; | |
1035 } | 952 } |
1036 | 953 |
1037 /* Insert in the SCOP context constraints from the estimation of the | 954 /* Insert in the SCOP context constraints from the estimation of the |
1038 number of iterations. UB_EXPR is a linear expression describing | 955 number of iterations. UB_EXPR is a linear expression describing |
1039 the number of iterations in a loop. This expression is bounded by | 956 the number of iterations in a loop. This expression is bounded by |
1048 ppl_Linear_Expression_t nb_iters_le; | 965 ppl_Linear_Expression_t nb_iters_le; |
1049 ppl_Polyhedron_t pol; | 966 ppl_Polyhedron_t pol; |
1050 ppl_Coefficient_t coef; | 967 ppl_Coefficient_t coef; |
1051 ppl_Constraint_t ub; | 968 ppl_Constraint_t ub; |
1052 | 969 |
1053 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim); | |
1054 ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0); | 970 ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0); |
1055 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le, | 971 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le, |
1056 ub_expr); | 972 ub_expr); |
1057 | 973 |
1058 /* Construct the negated number of last iteration in VAL. */ | 974 /* Construct the negated number of last iteration in VAL. */ |
1326 ppl_Pointset_Powerset_C_Polyhedron_t right; | 1242 ppl_Pointset_Powerset_C_Polyhedron_t right; |
1327 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron | 1243 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron |
1328 (&right, left); | 1244 (&right, left); |
1329 add_condition_to_domain (left, stmt, pbb, LT_EXPR); | 1245 add_condition_to_domain (left, stmt, pbb, LT_EXPR); |
1330 add_condition_to_domain (right, stmt, pbb, GT_EXPR); | 1246 add_condition_to_domain (right, stmt, pbb, GT_EXPR); |
1331 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left, | 1247 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left, right); |
1332 right); | |
1333 ppl_delete_Pointset_Powerset_C_Polyhedron (right); | 1248 ppl_delete_Pointset_Powerset_C_Polyhedron (right); |
1334 } | 1249 } |
1335 else | 1250 else |
1336 add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code); | 1251 add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code); |
1337 } | 1252 } |
1342 add_conditions_to_domain (poly_bb_p pbb) | 1257 add_conditions_to_domain (poly_bb_p pbb) |
1343 { | 1258 { |
1344 unsigned int i; | 1259 unsigned int i; |
1345 gimple stmt; | 1260 gimple stmt; |
1346 gimple_bb_p gbb = PBB_BLACK_BOX (pbb); | 1261 gimple_bb_p gbb = PBB_BLACK_BOX (pbb); |
1347 VEC (gimple, heap) *conditions = GBB_CONDITIONS (gbb); | 1262 |
1348 | 1263 if (VEC_empty (gimple, GBB_CONDITIONS (gbb))) |
1349 if (VEC_empty (gimple, conditions)) | |
1350 return; | 1264 return; |
1351 | 1265 |
1352 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++) | 1266 FOR_EACH_VEC_ELT (gimple, GBB_CONDITIONS (gbb), i, stmt) |
1353 switch (gimple_code (stmt)) | 1267 switch (gimple_code (stmt)) |
1354 { | 1268 { |
1355 case GIMPLE_COND: | 1269 case GIMPLE_COND: |
1356 { | 1270 { |
1357 enum tree_code code = gimple_cond_code (stmt); | 1271 enum tree_code code = gimple_cond_code (stmt); |
1358 | 1272 |
1359 /* The conditions for ELSE-branches are inverted. */ | 1273 /* The conditions for ELSE-branches are inverted. */ |
1360 if (VEC_index (gimple, gbb->condition_cases, i) == NULL) | 1274 if (!VEC_index (gimple, GBB_CONDITION_CASES (gbb), i)) |
1361 code = invert_tree_comparison (code, false); | 1275 code = invert_tree_comparison (code, false); |
1362 | 1276 |
1363 add_condition_to_pbb (pbb, stmt, code); | 1277 add_condition_to_pbb (pbb, stmt, code); |
1364 break; | 1278 break; |
1365 } | 1279 } |
1371 gcc_unreachable (); | 1285 gcc_unreachable (); |
1372 break; | 1286 break; |
1373 } | 1287 } |
1374 } | 1288 } |
1375 | 1289 |
1290 /* Traverses all the GBBs of the SCOP and add their constraints to the | |
1291 iteration domains. */ | |
1292 | |
1293 static void | |
1294 add_conditions_to_constraints (scop_p scop) | |
1295 { | |
1296 int i; | |
1297 poly_bb_p pbb; | |
1298 | |
1299 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) | |
1300 add_conditions_to_domain (pbb); | |
1301 } | |
1302 | |
1376 /* Structure used to pass data to dom_walk. */ | 1303 /* Structure used to pass data to dom_walk. */ |
1377 | 1304 |
1378 struct bsc | 1305 struct bsc |
1379 { | 1306 { |
1380 VEC (gimple, heap) **conditions, **cases; | 1307 VEC (gimple, heap) **conditions, **cases; |
1381 sese region; | 1308 sese region; |
1382 }; | 1309 }; |
1383 | 1310 |
1384 /* Returns non NULL when BB has a single predecessor and the last | 1311 /* Returns a COND_EXPR statement when BB has a single predecessor, the |
1385 statement of that predecessor is a COND_EXPR. */ | 1312 edge between BB and its predecessor is not a loop exit edge, and |
1313 the last statement of the single predecessor is a COND_EXPR. */ | |
1386 | 1314 |
1387 static gimple | 1315 static gimple |
1388 single_pred_cond (basic_block bb) | 1316 single_pred_cond_non_loop_exit (basic_block bb) |
1389 { | 1317 { |
1390 if (single_pred_p (bb)) | 1318 if (single_pred_p (bb)) |
1391 { | 1319 { |
1392 edge e = single_pred_edge (bb); | 1320 edge e = single_pred_edge (bb); |
1393 basic_block pred = e->src; | 1321 basic_block pred = e->src; |
1394 gimple stmt = last_stmt (pred); | 1322 gimple stmt; |
1323 | |
1324 if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father)) | |
1325 return NULL; | |
1326 | |
1327 stmt = last_stmt (pred); | |
1395 | 1328 |
1396 if (stmt && gimple_code (stmt) == GIMPLE_COND) | 1329 if (stmt && gimple_code (stmt) == GIMPLE_COND) |
1397 return stmt; | 1330 return stmt; |
1398 } | 1331 } |
1332 | |
1399 return NULL; | 1333 return NULL; |
1400 } | 1334 } |
1401 | 1335 |
1402 /* Call-back for dom_walk executed before visiting the dominated | 1336 /* Call-back for dom_walk executed before visiting the dominated |
1403 blocks. */ | 1337 blocks. */ |
1407 basic_block bb) | 1341 basic_block bb) |
1408 { | 1342 { |
1409 struct bsc *data = (struct bsc *) dw_data->global_data; | 1343 struct bsc *data = (struct bsc *) dw_data->global_data; |
1410 VEC (gimple, heap) **conditions = data->conditions; | 1344 VEC (gimple, heap) **conditions = data->conditions; |
1411 VEC (gimple, heap) **cases = data->cases; | 1345 VEC (gimple, heap) **cases = data->cases; |
1412 gimple_bb_p gbb = gbb_from_bb (bb); | 1346 gimple_bb_p gbb; |
1413 gimple stmt = single_pred_cond (bb); | 1347 gimple stmt; |
1414 | 1348 |
1415 if (!bb_in_sese_p (bb, data->region)) | 1349 if (!bb_in_sese_p (bb, data->region)) |
1416 return; | 1350 return; |
1351 | |
1352 stmt = single_pred_cond_non_loop_exit (bb); | |
1417 | 1353 |
1418 if (stmt) | 1354 if (stmt) |
1419 { | 1355 { |
1420 edge e = single_pred_edge (bb); | 1356 edge e = single_pred_edge (bb); |
1421 | 1357 |
1425 VEC_safe_push (gimple, heap, *cases, stmt); | 1361 VEC_safe_push (gimple, heap, *cases, stmt); |
1426 else | 1362 else |
1427 VEC_safe_push (gimple, heap, *cases, NULL); | 1363 VEC_safe_push (gimple, heap, *cases, NULL); |
1428 } | 1364 } |
1429 | 1365 |
1366 gbb = gbb_from_bb (bb); | |
1367 | |
1430 if (gbb) | 1368 if (gbb) |
1431 { | 1369 { |
1432 GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions); | 1370 GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions); |
1433 GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases); | 1371 GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases); |
1434 } | 1372 } |
1446 VEC (gimple, heap) **cases = data->cases; | 1384 VEC (gimple, heap) **cases = data->cases; |
1447 | 1385 |
1448 if (!bb_in_sese_p (bb, data->region)) | 1386 if (!bb_in_sese_p (bb, data->region)) |
1449 return; | 1387 return; |
1450 | 1388 |
1451 if (single_pred_cond (bb)) | 1389 if (single_pred_cond_non_loop_exit (bb)) |
1452 { | 1390 { |
1453 VEC_pop (gimple, *conditions); | 1391 VEC_pop (gimple, *conditions); |
1454 VEC_pop (gimple, *cases); | 1392 VEC_pop (gimple, *cases); |
1455 } | 1393 } |
1456 } | 1394 } |
1480 walk_dominator_tree (&walk_data, SESE_ENTRY_BB (region)); | 1418 walk_dominator_tree (&walk_data, SESE_ENTRY_BB (region)); |
1481 fini_walk_dominator_tree (&walk_data); | 1419 fini_walk_dominator_tree (&walk_data); |
1482 | 1420 |
1483 VEC_free (gimple, heap, conditions); | 1421 VEC_free (gimple, heap, conditions); |
1484 VEC_free (gimple, heap, cases); | 1422 VEC_free (gimple, heap, cases); |
1485 } | |
1486 | |
1487 /* Traverses all the GBBs of the SCOP and add their constraints to the | |
1488 iteration domains. */ | |
1489 | |
1490 static void | |
1491 add_conditions_to_constraints (scop_p scop) | |
1492 { | |
1493 int i; | |
1494 poly_bb_p pbb; | |
1495 | |
1496 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) | |
1497 add_conditions_to_domain (pbb); | |
1498 } | 1423 } |
1499 | 1424 |
1500 /* Add constraints on the possible values of parameter P from the type | 1425 /* Add constraints on the possible values of parameter P from the type |
1501 of P. */ | 1426 of P. */ |
1502 | 1427 |
1587 for (i = 0; i < nb_loops; i++) | 1512 for (i = 0; i < nb_loops; i++) |
1588 domains[i] = NULL; | 1513 domains[i] = NULL; |
1589 | 1514 |
1590 ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0); | 1515 ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0); |
1591 | 1516 |
1592 for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++) | 1517 FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop) |
1593 if (!loop_in_sese_p (loop_outer (loop), region)) | 1518 if (!loop_in_sese_p (loop_outer (loop), region)) |
1594 build_loop_iteration_domains (scop, loop, ph, 0, domains); | 1519 build_loop_iteration_domains (scop, loop, ph, 0, domains); |
1595 | 1520 |
1596 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) | 1521 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) |
1597 if (domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]) | 1522 if (domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]) |
1598 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron | 1523 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron |
1599 (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t) | 1524 (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t) |
1600 domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]); | 1525 domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]); |
1601 else | 1526 else |
1709 low = array_ref_low_bound (ref); | 1634 low = array_ref_low_bound (ref); |
1710 | 1635 |
1711 /* subscript - low >= 0 */ | 1636 /* subscript - low >= 0 */ |
1712 if (host_integerp (low, 0)) | 1637 if (host_integerp (low, 0)) |
1713 { | 1638 { |
1639 tree minus_low; | |
1640 | |
1714 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims); | 1641 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims); |
1715 ppl_set_coef (expr, subscript, 1); | 1642 ppl_set_coef (expr, subscript, 1); |
1716 | 1643 |
1717 ppl_set_inhomogeneous (expr, -int_cst_value (low)); | 1644 minus_low = fold_build1 (NEGATE_EXPR, TREE_TYPE (low), low); |
1645 ppl_set_inhomogeneous_tree (expr, minus_low); | |
1718 | 1646 |
1719 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); | 1647 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); |
1720 ppl_Polyhedron_add_constraint (accesses, cstr); | 1648 ppl_Polyhedron_add_constraint (accesses, cstr); |
1721 ppl_delete_Linear_Expression (expr); | 1649 ppl_delete_Linear_Expression (expr); |
1722 ppl_delete_Constraint (cstr); | 1650 ppl_delete_Constraint (cstr); |
1732 && operand_equal_p (low, high, 0))) | 1660 && operand_equal_p (low, high, 0))) |
1733 { | 1661 { |
1734 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims); | 1662 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims); |
1735 ppl_set_coef (expr, subscript, -1); | 1663 ppl_set_coef (expr, subscript, -1); |
1736 | 1664 |
1737 ppl_set_inhomogeneous (expr, int_cst_value (high)); | 1665 ppl_set_inhomogeneous_tree (expr, high); |
1738 | 1666 |
1739 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); | 1667 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); |
1740 ppl_Polyhedron_add_constraint (accesses, cstr); | 1668 ppl_Polyhedron_add_constraint (accesses, cstr); |
1741 ppl_delete_Linear_Expression (expr); | 1669 ppl_delete_Linear_Expression (expr); |
1742 ppl_delete_Constraint (cstr); | 1670 ppl_delete_Constraint (cstr); |
1767 | 1695 |
1768 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps, | 1696 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps, |
1769 accesses); | 1697 accesses); |
1770 ppl_delete_Polyhedron (accesses); | 1698 ppl_delete_Polyhedron (accesses); |
1771 | 1699 |
1772 if (dr->aux) | 1700 gcc_assert (dr->aux); |
1773 dr_base_object_set = ((base_alias_pair *)(dr->aux))->base_obj_set; | 1701 dr_base_object_set = ((base_alias_pair *)(dr->aux))->base_obj_set; |
1774 | 1702 |
1775 new_poly_dr (pbb, dr_base_object_set, accesses_ps, DR_IS_READ (dr) ? PDR_READ : PDR_WRITE, | 1703 new_poly_dr (pbb, dr_base_object_set, accesses_ps, |
1704 DR_IS_READ (dr) ? PDR_READ : PDR_WRITE, | |
1776 dr, DR_NUM_DIMENSIONS (dr)); | 1705 dr, DR_NUM_DIMENSIONS (dr)); |
1777 } | 1706 } |
1778 | 1707 |
1779 /* Write to FILE the alias graph of data references in DIMACS format. */ | 1708 /* Write to FILE the alias graph of data references in DIMACS format. */ |
1780 | 1709 |
1788 int i, j; | 1717 int i, j; |
1789 | 1718 |
1790 if (num_vertex == 0) | 1719 if (num_vertex == 0) |
1791 return true; | 1720 return true; |
1792 | 1721 |
1793 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) | 1722 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1) |
1794 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) | 1723 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) |
1795 if (dr_may_alias_p (dr1, dr2)) | 1724 if (dr_may_alias_p (dr1, dr2)) |
1796 edge_num++; | 1725 edge_num++; |
1797 | 1726 |
1798 fprintf (file, "$\n"); | 1727 fprintf (file, "$\n"); |
1800 if (comment) | 1729 if (comment) |
1801 fprintf (file, "c %s\n", comment); | 1730 fprintf (file, "c %s\n", comment); |
1802 | 1731 |
1803 fprintf (file, "p edge %d %d\n", num_vertex, edge_num); | 1732 fprintf (file, "p edge %d %d\n", num_vertex, edge_num); |
1804 | 1733 |
1805 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) | 1734 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1) |
1806 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) | 1735 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) |
1807 if (dr_may_alias_p (dr1, dr2)) | 1736 if (dr_may_alias_p (dr1, dr2)) |
1808 fprintf (file, "e %d %d\n", i + 1, j + 1); | 1737 fprintf (file, "e %d %d\n", i + 1, j + 1); |
1809 | 1738 |
1810 return true; | 1739 return true; |
1827 | 1756 |
1828 if (comment) | 1757 if (comment) |
1829 fprintf (file, "c %s\n", comment); | 1758 fprintf (file, "c %s\n", comment); |
1830 | 1759 |
1831 /* First print all the vertices. */ | 1760 /* First print all the vertices. */ |
1832 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) | 1761 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1) |
1833 fprintf (file, "n%d;\n", i); | 1762 fprintf (file, "n%d;\n", i); |
1834 | 1763 |
1835 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) | 1764 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1) |
1836 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) | 1765 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) |
1837 if (dr_may_alias_p (dr1, dr2)) | 1766 if (dr_may_alias_p (dr1, dr2)) |
1838 fprintf (file, "n%d n%d\n", i, j); | 1767 fprintf (file, "n%d n%d\n", i, j); |
1839 | 1768 |
1840 return true; | 1769 return true; |
1856 fprintf (file, "$\n"); | 1785 fprintf (file, "$\n"); |
1857 | 1786 |
1858 if (comment) | 1787 if (comment) |
1859 fprintf (file, "c %s\n", comment); | 1788 fprintf (file, "c %s\n", comment); |
1860 | 1789 |
1861 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) | 1790 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1) |
1862 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) | 1791 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) |
1863 if (dr_may_alias_p (dr1, dr2)) | 1792 if (dr_may_alias_p (dr1, dr2)) |
1864 fprintf (file, "%d %d\n", i, j); | 1793 fprintf (file, "%d %d\n", i, j); |
1865 | 1794 |
1866 return true; | 1795 return true; |
1892 int *vertices; | 1821 int *vertices; |
1893 struct graph_edge *e; | 1822 struct graph_edge *e; |
1894 int this_component_is_clique; | 1823 int this_component_is_clique; |
1895 int all_components_are_cliques = 1; | 1824 int all_components_are_cliques = 1; |
1896 | 1825 |
1897 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) | 1826 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1) |
1898 for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++) | 1827 for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++) |
1899 if (dr_may_alias_p (dr1, dr2)) | 1828 if (dr_may_alias_p (dr1, dr2)) |
1900 { | 1829 { |
1901 add_edge (g, i, j); | 1830 add_edge (g, i, j); |
1902 add_edge (g, j, i); | 1831 add_edge (g, j, i); |
1912 for (i = 0; i < g->n_vertices; i++) | 1841 for (i = 0; i < g->n_vertices; i++) |
1913 { | 1842 { |
1914 data_reference_p dr = VEC_index (data_reference_p, drs, i); | 1843 data_reference_p dr = VEC_index (data_reference_p, drs, i); |
1915 base_alias_pair *bap; | 1844 base_alias_pair *bap; |
1916 | 1845 |
1917 if (dr->aux) | 1846 gcc_assert (dr->aux); |
1918 bap = (base_alias_pair *)(dr->aux); | 1847 bap = (base_alias_pair *)(dr->aux); |
1919 | 1848 |
1920 bap->alias_set = XNEW (int); | 1849 bap->alias_set = XNEW (int); |
1921 *(bap->alias_set) = g->vertices[i].component + 1; | 1850 *(bap->alias_set) = g->vertices[i].component + 1; |
1922 } | 1851 } |
1923 | 1852 |
1961 free (vertices); | 1890 free (vertices); |
1962 free_graph (g); | 1891 free_graph (g); |
1963 return all_components_are_cliques; | 1892 return all_components_are_cliques; |
1964 } | 1893 } |
1965 | 1894 |
1966 /* Group each data reference in DRS with it's base object set num. */ | 1895 /* Group each data reference in DRS with its base object set num. */ |
1967 | 1896 |
1968 static void | 1897 static void |
1969 build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs) | 1898 build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs) |
1970 { | 1899 { |
1971 int num_vertex = VEC_length (data_reference_p, drs); | 1900 int num_vertex = VEC_length (data_reference_p, drs); |
1972 struct graph *g = new_graph (num_vertex); | 1901 struct graph *g = new_graph (num_vertex); |
1973 data_reference_p dr1, dr2; | 1902 data_reference_p dr1, dr2; |
1974 int i, j; | 1903 int i, j; |
1975 int *queue; | 1904 int *queue; |
1976 | 1905 |
1977 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) | 1906 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1) |
1978 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) | 1907 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) |
1979 if (dr_same_base_object_p (dr1, dr2)) | 1908 if (dr_same_base_object_p (dr1, dr2)) |
1980 { | 1909 { |
1981 add_edge (g, i, j); | 1910 add_edge (g, i, j); |
1982 add_edge (g, j, i); | 1911 add_edge (g, j, i); |
1991 for (i = 0; i < g->n_vertices; i++) | 1920 for (i = 0; i < g->n_vertices; i++) |
1992 { | 1921 { |
1993 data_reference_p dr = VEC_index (data_reference_p, drs, i); | 1922 data_reference_p dr = VEC_index (data_reference_p, drs, i); |
1994 base_alias_pair *bap; | 1923 base_alias_pair *bap; |
1995 | 1924 |
1996 if (dr->aux) | 1925 gcc_assert (dr->aux); |
1997 bap = (base_alias_pair *)(dr->aux); | 1926 bap = (base_alias_pair *)(dr->aux); |
1998 | 1927 |
1999 bap->base_obj_set = g->vertices[i].component + 1; | 1928 bap->base_obj_set = g->vertices[i].component + 1; |
2000 } | 1929 } |
2001 | 1930 |
2002 free (queue); | 1931 free (queue); |
2010 { | 1939 { |
2011 int j; | 1940 int j; |
2012 data_reference_p dr; | 1941 data_reference_p dr; |
2013 VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb)); | 1942 VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb)); |
2014 | 1943 |
2015 for (j = 0; VEC_iterate (data_reference_p, gbb_drs, j, dr); j++) | 1944 FOR_EACH_VEC_ELT (data_reference_p, gbb_drs, j, dr) |
2016 build_poly_dr (dr, pbb); | 1945 build_poly_dr (dr, pbb); |
2017 } | 1946 } |
2018 | 1947 |
2019 /* Dump to file the alias graphs for the data references in DRS. */ | 1948 /* Dump to file the alias graphs for the data references in DRS. */ |
2020 | 1949 |
2060 int i, j; | 1989 int i, j; |
2061 poly_bb_p pbb; | 1990 poly_bb_p pbb; |
2062 data_reference_p dr; | 1991 data_reference_p dr; |
2063 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3); | 1992 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3); |
2064 | 1993 |
1994 /* Remove all the PBBs that do not have data references: these basic | |
1995 blocks are not handled in the polyhedral representation. */ | |
2065 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) | 1996 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) |
1997 if (VEC_empty (data_reference_p, GBB_DATA_REFS (PBB_BLACK_BOX (pbb)))) | |
1998 { | |
1999 free_gimple_bb (PBB_BLACK_BOX (pbb)); | |
2000 VEC_ordered_remove (poly_bb_p, SCOP_BBS (scop), i); | |
2001 i--; | |
2002 } | |
2003 | |
2004 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) | |
2066 for (j = 0; VEC_iterate (data_reference_p, | 2005 for (j = 0; VEC_iterate (data_reference_p, |
2067 GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++) | 2006 GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++) |
2068 VEC_safe_push (data_reference_p, heap, drs, dr); | 2007 VEC_safe_push (data_reference_p, heap, drs, dr); |
2069 | 2008 |
2070 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr); i++) | 2009 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr) |
2071 dr->aux = XNEW (base_alias_pair); | 2010 dr->aux = XNEW (base_alias_pair); |
2072 | 2011 |
2073 if (!build_alias_set_optimal_p (drs)) | 2012 if (!build_alias_set_optimal_p (drs)) |
2074 { | 2013 { |
2075 /* TODO: Add support when building alias set is not optimal. */ | 2014 /* TODO: Add support when building alias set is not optimal. */ |
2083 if (0) | 2022 if (0) |
2084 dump_alias_graphs (drs); | 2023 dump_alias_graphs (drs); |
2085 | 2024 |
2086 VEC_free (data_reference_p, heap, drs); | 2025 VEC_free (data_reference_p, heap, drs); |
2087 | 2026 |
2088 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) | 2027 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) |
2089 build_pbb_drs (pbb); | 2028 build_pbb_drs (pbb); |
2090 } | 2029 } |
2091 | 2030 |
2092 /* Return a gsi at the position of the phi node STMT. */ | 2031 /* Return a gsi at the position of the phi node STMT. */ |
2093 | 2032 |
2103 | 2042 |
2104 gcc_unreachable (); | 2043 gcc_unreachable (); |
2105 return psi; | 2044 return psi; |
2106 } | 2045 } |
2107 | 2046 |
2108 /* Insert the assignment "RES := VAR" just after the definition of VAR. */ | 2047 /* Analyze all the data references of STMTS and add them to the |
2109 | 2048 GBB_DATA_REFS vector of BB. */ |
2110 static void | 2049 |
2111 insert_out_of_ssa_copy (tree res, tree var) | 2050 static void |
2112 { | 2051 analyze_drs_in_stmts (scop_p scop, basic_block bb, VEC (gimple, heap) *stmts) |
2052 { | |
2053 loop_p nest; | |
2054 gimple_bb_p gbb; | |
2113 gimple stmt; | 2055 gimple stmt; |
2056 int i; | |
2057 sese region = SCOP_REGION (scop); | |
2058 | |
2059 if (!bb_in_sese_p (bb, region)) | |
2060 return; | |
2061 | |
2062 nest = outermost_loop_in_sese_1 (region, bb); | |
2063 gbb = gbb_from_bb (bb); | |
2064 | |
2065 FOR_EACH_VEC_ELT (gimple, stmts, i, stmt) | |
2066 { | |
2067 loop_p loop; | |
2068 | |
2069 if (is_gimple_debug (stmt)) | |
2070 continue; | |
2071 | |
2072 loop = loop_containing_stmt (stmt); | |
2073 if (!loop_in_sese_p (loop, region)) | |
2074 loop = nest; | |
2075 | |
2076 graphite_find_data_references_in_stmt (nest, loop, stmt, | |
2077 &GBB_DATA_REFS (gbb)); | |
2078 } | |
2079 } | |
2080 | |
2081 /* Insert STMT at the end of the STMTS sequence and then insert the | |
2082 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts | |
2083 on STMTS. */ | |
2084 | |
2085 static void | |
2086 insert_stmts (scop_p scop, gimple stmt, gimple_seq stmts, | |
2087 gimple_stmt_iterator insert_gsi) | |
2088 { | |
2089 gimple_stmt_iterator gsi; | |
2090 VEC (gimple, heap) *x = VEC_alloc (gimple, heap, 3); | |
2091 | |
2092 if (!stmts) | |
2093 stmts = gimple_seq_alloc (); | |
2094 | |
2095 gsi = gsi_last (stmts); | |
2096 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT); | |
2097 for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi)) | |
2098 VEC_safe_push (gimple, heap, x, gsi_stmt (gsi)); | |
2099 | |
2100 gsi_insert_seq_before (&insert_gsi, stmts, GSI_SAME_STMT); | |
2101 analyze_drs_in_stmts (scop, gsi_bb (insert_gsi), x); | |
2102 VEC_free (gimple, heap, x); | |
2103 } | |
2104 | |
2105 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */ | |
2106 | |
2107 static void | |
2108 insert_out_of_ssa_copy (scop_p scop, tree res, tree expr, gimple after_stmt) | |
2109 { | |
2114 gimple_seq stmts; | 2110 gimple_seq stmts; |
2115 gimple_stmt_iterator si; | 2111 gimple_stmt_iterator si; |
2116 gimple_stmt_iterator gsi; | 2112 gimple_stmt_iterator gsi; |
2117 | 2113 tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE); |
2118 var = force_gimple_operand (var, &stmts, true, NULL_TREE); | 2114 gimple stmt = gimple_build_assign (res, var); |
2119 stmt = gimple_build_assign (res, var); | 2115 VEC (gimple, heap) *x = VEC_alloc (gimple, heap, 3); |
2116 | |
2120 if (!stmts) | 2117 if (!stmts) |
2121 stmts = gimple_seq_alloc (); | 2118 stmts = gimple_seq_alloc (); |
2122 si = gsi_last (stmts); | 2119 si = gsi_last (stmts); |
2123 gsi_insert_after (&si, stmt, GSI_NEW_STMT); | 2120 gsi_insert_after (&si, stmt, GSI_NEW_STMT); |
2124 | 2121 for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi)) |
2125 stmt = SSA_NAME_DEF_STMT (var); | 2122 VEC_safe_push (gimple, heap, x, gsi_stmt (gsi)); |
2126 if (gimple_code (stmt) == GIMPLE_PHI) | 2123 |
2127 { | 2124 if (gimple_code (after_stmt) == GIMPLE_PHI) |
2128 gsi = gsi_after_labels (gimple_bb (stmt)); | 2125 { |
2126 gsi = gsi_after_labels (gimple_bb (after_stmt)); | |
2129 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT); | 2127 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT); |
2130 } | 2128 } |
2131 else | 2129 else |
2132 { | 2130 { |
2133 gsi = gsi_for_stmt (stmt); | 2131 gsi = gsi_for_stmt (after_stmt); |
2134 gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT); | 2132 gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT); |
2135 } | 2133 } |
2134 | |
2135 analyze_drs_in_stmts (scop, gimple_bb (after_stmt), x); | |
2136 VEC_free (gimple, heap, x); | |
2137 } | |
2138 | |
2139 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */ | |
2140 | |
2141 static void | |
2142 new_pbb_from_pbb (scop_p scop, poly_bb_p pbb, basic_block bb) | |
2143 { | |
2144 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3); | |
2145 gimple_bb_p gbb = PBB_BLACK_BOX (pbb); | |
2146 gimple_bb_p gbb1 = new_gimple_bb (bb, drs); | |
2147 poly_bb_p pbb1 = new_poly_bb (scop, gbb1); | |
2148 int index, n = VEC_length (poly_bb_p, SCOP_BBS (scop)); | |
2149 | |
2150 /* The INDEX of PBB in SCOP_BBS. */ | |
2151 for (index = 0; index < n; index++) | |
2152 if (VEC_index (poly_bb_p, SCOP_BBS (scop), index) == pbb) | |
2153 break; | |
2154 | |
2155 if (PBB_DOMAIN (pbb)) | |
2156 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron | |
2157 (&PBB_DOMAIN (pbb1), PBB_DOMAIN (pbb)); | |
2158 | |
2159 GBB_PBB (gbb1) = pbb1; | |
2160 GBB_CONDITIONS (gbb1) = VEC_copy (gimple, heap, GBB_CONDITIONS (gbb)); | |
2161 GBB_CONDITION_CASES (gbb1) = VEC_copy (gimple, heap, GBB_CONDITION_CASES (gbb)); | |
2162 VEC_safe_insert (poly_bb_p, heap, SCOP_BBS (scop), index + 1, pbb1); | |
2136 } | 2163 } |
2137 | 2164 |
2138 /* Insert on edge E the assignment "RES := EXPR". */ | 2165 /* Insert on edge E the assignment "RES := EXPR". */ |
2139 | 2166 |
2140 static void | 2167 static void |
2141 insert_out_of_ssa_copy_on_edge (edge e, tree res, tree expr) | 2168 insert_out_of_ssa_copy_on_edge (scop_p scop, edge e, tree res, tree expr) |
2142 { | 2169 { |
2143 gimple_stmt_iterator gsi; | 2170 gimple_stmt_iterator gsi; |
2144 gimple_seq stmts; | 2171 gimple_seq stmts; |
2145 tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE); | 2172 tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE); |
2146 gimple stmt = gimple_build_assign (res, var); | 2173 gimple stmt = gimple_build_assign (res, var); |
2174 basic_block bb; | |
2175 VEC (gimple, heap) *x = VEC_alloc (gimple, heap, 3); | |
2147 | 2176 |
2148 if (!stmts) | 2177 if (!stmts) |
2149 stmts = gimple_seq_alloc (); | 2178 stmts = gimple_seq_alloc (); |
2150 | 2179 |
2151 gsi = gsi_last (stmts); | 2180 gsi = gsi_last (stmts); |
2152 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT); | 2181 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT); |
2182 for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi)) | |
2183 VEC_safe_push (gimple, heap, x, gsi_stmt (gsi)); | |
2184 | |
2153 gsi_insert_seq_on_edge (e, stmts); | 2185 gsi_insert_seq_on_edge (e, stmts); |
2154 gsi_commit_edge_inserts (); | 2186 gsi_commit_edge_inserts (); |
2187 bb = gimple_bb (stmt); | |
2188 | |
2189 if (!bb_in_sese_p (bb, SCOP_REGION (scop))) | |
2190 return; | |
2191 | |
2192 if (!gbb_from_bb (bb)) | |
2193 new_pbb_from_pbb (scop, pbb_from_bb (e->src), bb); | |
2194 | |
2195 analyze_drs_in_stmts (scop, bb, x); | |
2196 VEC_free (gimple, heap, x); | |
2155 } | 2197 } |
2156 | 2198 |
2157 /* Creates a zero dimension array of the same type as VAR. */ | 2199 /* Creates a zero dimension array of the same type as VAR. */ |
2158 | 2200 |
2159 static tree | 2201 static tree |
2183 because we translated the representation into a canonical form | 2225 because we translated the representation into a canonical form |
2184 before Graphite: see canonicalize_loop_closed_ssa_form. */ | 2226 before Graphite: see canonicalize_loop_closed_ssa_form. */ |
2185 return (gimple_phi_num_args (phi) == 1); | 2227 return (gimple_phi_num_args (phi) == 1); |
2186 } | 2228 } |
2187 | 2229 |
2230 /* For a definition DEF in REGION, propagates the expression EXPR in | |
2231 all the uses of DEF outside REGION. */ | |
2232 | |
2233 static void | |
2234 propagate_expr_outside_region (tree def, tree expr, sese region) | |
2235 { | |
2236 imm_use_iterator imm_iter; | |
2237 gimple use_stmt; | |
2238 gimple_seq stmts; | |
2239 bool replaced_once = false; | |
2240 | |
2241 gcc_assert (TREE_CODE (def) == SSA_NAME); | |
2242 | |
2243 expr = force_gimple_operand (unshare_expr (expr), &stmts, true, | |
2244 NULL_TREE); | |
2245 | |
2246 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) | |
2247 if (!is_gimple_debug (use_stmt) | |
2248 && !bb_in_sese_p (gimple_bb (use_stmt), region)) | |
2249 { | |
2250 ssa_op_iter iter; | |
2251 use_operand_p use_p; | |
2252 | |
2253 FOR_EACH_PHI_OR_STMT_USE (use_p, use_stmt, iter, SSA_OP_ALL_USES) | |
2254 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0) | |
2255 && (replaced_once = true)) | |
2256 replace_exp (use_p, expr); | |
2257 | |
2258 update_stmt (use_stmt); | |
2259 } | |
2260 | |
2261 if (replaced_once) | |
2262 { | |
2263 gsi_insert_seq_on_edge (SESE_ENTRY (region), stmts); | |
2264 gsi_commit_edge_inserts (); | |
2265 } | |
2266 } | |
2267 | |
2188 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero | 2268 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero |
2189 dimension array for it. */ | 2269 dimension array for it. */ |
2190 | 2270 |
2191 static void | 2271 static void |
2192 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi) | 2272 rewrite_close_phi_out_of_ssa (scop_p scop, gimple_stmt_iterator *psi) |
2193 { | 2273 { |
2274 sese region = SCOP_REGION (scop); | |
2194 gimple phi = gsi_stmt (*psi); | 2275 gimple phi = gsi_stmt (*psi); |
2195 tree res = gimple_phi_result (phi); | 2276 tree res = gimple_phi_result (phi); |
2196 tree var = SSA_NAME_VAR (res); | 2277 tree var = SSA_NAME_VAR (res); |
2197 tree zero_dim_array = create_zero_dim_array (var, "Close_Phi"); | 2278 basic_block bb = gimple_bb (phi); |
2198 gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi)); | 2279 gimple_stmt_iterator gsi = gsi_after_labels (bb); |
2199 gimple stmt = gimple_build_assign (res, zero_dim_array); | |
2200 tree arg = gimple_phi_arg_def (phi, 0); | 2280 tree arg = gimple_phi_arg_def (phi, 0); |
2281 gimple stmt; | |
2201 | 2282 |
2202 /* Note that loop close phi nodes should have a single argument | 2283 /* Note that loop close phi nodes should have a single argument |
2203 because we translated the representation into a canonical form | 2284 because we translated the representation into a canonical form |
2204 before Graphite: see canonicalize_loop_closed_ssa_form. */ | 2285 before Graphite: see canonicalize_loop_closed_ssa_form. */ |
2205 gcc_assert (gimple_phi_num_args (phi) == 1); | 2286 gcc_assert (gimple_phi_num_args (phi) == 1); |
2206 | 2287 |
2207 if (TREE_CODE (arg) == SSA_NAME | 2288 /* The phi node can be a non close phi node, when its argument is |
2208 && !SSA_NAME_IS_DEFAULT_DEF (arg)) | 2289 invariant, or a default definition. */ |
2209 insert_out_of_ssa_copy (zero_dim_array, arg); | 2290 if (is_gimple_min_invariant (arg) |
2291 || SSA_NAME_IS_DEFAULT_DEF (arg)) | |
2292 { | |
2293 propagate_expr_outside_region (res, arg, region); | |
2294 gsi_next (psi); | |
2295 return; | |
2296 } | |
2297 | |
2298 else if (gimple_bb (SSA_NAME_DEF_STMT (arg))->loop_father == bb->loop_father) | |
2299 { | |
2300 propagate_expr_outside_region (res, arg, region); | |
2301 stmt = gimple_build_assign (res, arg); | |
2302 remove_phi_node (psi, false); | |
2303 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT); | |
2304 SSA_NAME_DEF_STMT (res) = stmt; | |
2305 return; | |
2306 } | |
2307 | |
2308 /* If res is scev analyzable and is not a scalar value, it is safe | |
2309 to ignore the close phi node: it will be code generated in the | |
2310 out of Graphite pass. */ | |
2311 else if (scev_analyzable_p (res, region)) | |
2312 { | |
2313 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (res)); | |
2314 tree scev; | |
2315 | |
2316 if (!loop_in_sese_p (loop, region)) | |
2317 { | |
2318 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (arg)); | |
2319 scev = scalar_evolution_in_region (region, loop, arg); | |
2320 scev = compute_overall_effect_of_inner_loop (loop, scev); | |
2321 } | |
2322 else | |
2323 scev = scalar_evolution_in_region (region, loop, res); | |
2324 | |
2325 if (tree_does_not_contain_chrecs (scev)) | |
2326 propagate_expr_outside_region (res, scev, region); | |
2327 | |
2328 gsi_next (psi); | |
2329 return; | |
2330 } | |
2210 else | 2331 else |
2211 insert_out_of_ssa_copy_on_edge (single_pred_edge (gimple_bb (phi)), | 2332 { |
2212 zero_dim_array, arg); | 2333 tree zero_dim_array = create_zero_dim_array (var, "Close_Phi"); |
2334 | |
2335 stmt = gimple_build_assign (res, zero_dim_array); | |
2336 | |
2337 if (TREE_CODE (arg) == SSA_NAME) | |
2338 insert_out_of_ssa_copy (scop, zero_dim_array, arg, | |
2339 SSA_NAME_DEF_STMT (arg)); | |
2340 else | |
2341 insert_out_of_ssa_copy_on_edge (scop, single_pred_edge (bb), | |
2342 zero_dim_array, arg); | |
2343 } | |
2213 | 2344 |
2214 remove_phi_node (psi, false); | 2345 remove_phi_node (psi, false); |
2215 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT); | |
2216 SSA_NAME_DEF_STMT (res) = stmt; | 2346 SSA_NAME_DEF_STMT (res) = stmt; |
2347 | |
2348 insert_stmts (scop, stmt, NULL, gsi_after_labels (bb)); | |
2217 } | 2349 } |
2218 | 2350 |
2219 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero | 2351 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero |
2220 dimension array for it. */ | 2352 dimension array for it. */ |
2221 | 2353 |
2222 static void | 2354 static void |
2223 rewrite_phi_out_of_ssa (gimple_stmt_iterator *psi) | 2355 rewrite_phi_out_of_ssa (scop_p scop, gimple_stmt_iterator *psi) |
2224 { | 2356 { |
2225 size_t i; | 2357 size_t i; |
2226 gimple phi = gsi_stmt (*psi); | 2358 gimple phi = gsi_stmt (*psi); |
2227 basic_block bb = gimple_bb (phi); | 2359 basic_block bb = gimple_bb (phi); |
2228 tree res = gimple_phi_result (phi); | 2360 tree res = gimple_phi_result (phi); |
2229 tree var = SSA_NAME_VAR (res); | 2361 tree var = SSA_NAME_VAR (res); |
2230 tree zero_dim_array = create_zero_dim_array (var, "General_Reduction"); | 2362 tree zero_dim_array = create_zero_dim_array (var, "phi_out_of_ssa"); |
2231 gimple_stmt_iterator gsi; | |
2232 gimple stmt; | 2363 gimple stmt; |
2233 gimple_seq stmts; | 2364 gimple_seq stmts; |
2234 | 2365 |
2235 for (i = 0; i < gimple_phi_num_args (phi); i++) | 2366 for (i = 0; i < gimple_phi_num_args (phi); i++) |
2236 { | 2367 { |
2237 tree arg = gimple_phi_arg_def (phi, i); | 2368 tree arg = gimple_phi_arg_def (phi, i); |
2238 | 2369 edge e = gimple_phi_arg_edge (phi, i); |
2239 /* Try to avoid the insertion on edges as much as possible: this | 2370 |
2240 would avoid the insertion of code on loop latch edges, making | 2371 /* Avoid the insertion of code in the loop latch to please the |
2241 the pattern matching of the vectorizer happy, or it would | 2372 pattern matching of the vectorizer. */ |
2242 avoid the insertion of useless basic blocks. Note that it is | |
2243 incorrect to insert out of SSA copies close by their | |
2244 definition when they are more than two loop levels apart: | |
2245 for example, starting from a double nested loop | |
2246 | |
2247 | a = ... | |
2248 | loop_1 | |
2249 | loop_2 | |
2250 | b = phi (a, c) | |
2251 | c = ... | |
2252 | end_2 | |
2253 | end_1 | |
2254 | |
2255 the following transform is incorrect | |
2256 | |
2257 | a = ... | |
2258 | Red[0] = a | |
2259 | loop_1 | |
2260 | loop_2 | |
2261 | b = Red[0] | |
2262 | c = ... | |
2263 | Red[0] = c | |
2264 | end_2 | |
2265 | end_1 | |
2266 | |
2267 whereas inserting the copy on the incoming edge is correct | |
2268 | |
2269 | a = ... | |
2270 | loop_1 | |
2271 | Red[0] = a | |
2272 | loop_2 | |
2273 | b = Red[0] | |
2274 | c = ... | |
2275 | Red[0] = c | |
2276 | end_2 | |
2277 | end_1 | |
2278 */ | |
2279 if (TREE_CODE (arg) == SSA_NAME | 2373 if (TREE_CODE (arg) == SSA_NAME |
2280 && is_gimple_reg (arg) | 2374 && e->src == bb->loop_father->latch) |
2281 && gimple_bb (SSA_NAME_DEF_STMT (arg)) | 2375 insert_out_of_ssa_copy (scop, zero_dim_array, arg, |
2282 && (flow_bb_inside_loop_p (bb->loop_father, | 2376 SSA_NAME_DEF_STMT (arg)); |
2283 gimple_bb (SSA_NAME_DEF_STMT (arg))) | |
2284 || flow_bb_inside_loop_p (loop_outer (bb->loop_father), | |
2285 gimple_bb (SSA_NAME_DEF_STMT (arg))))) | |
2286 insert_out_of_ssa_copy (zero_dim_array, arg); | |
2287 else | 2377 else |
2288 insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi, i), | 2378 insert_out_of_ssa_copy_on_edge (scop, e, zero_dim_array, arg); |
2289 zero_dim_array, arg); | |
2290 } | 2379 } |
2291 | 2380 |
2292 var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE); | 2381 var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE); |
2293 | |
2294 if (!stmts) | |
2295 stmts = gimple_seq_alloc (); | |
2296 | 2382 |
2297 stmt = gimple_build_assign (res, var); | 2383 stmt = gimple_build_assign (res, var); |
2298 remove_phi_node (psi, false); | 2384 remove_phi_node (psi, false); |
2299 SSA_NAME_DEF_STMT (res) = stmt; | 2385 SSA_NAME_DEF_STMT (res) = stmt; |
2300 | 2386 |
2301 gsi = gsi_last (stmts); | 2387 insert_stmts (scop, stmt, stmts, gsi_after_labels (bb)); |
2302 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT); | 2388 } |
2389 | |
2390 /* Rewrite the degenerate phi node at position PSI from the degenerate | |
2391 form "x = phi (y, y, ..., y)" to "x = y". */ | |
2392 | |
2393 static void | |
2394 rewrite_degenerate_phi (gimple_stmt_iterator *psi) | |
2395 { | |
2396 tree rhs; | |
2397 gimple stmt; | |
2398 gimple_stmt_iterator gsi; | |
2399 gimple phi = gsi_stmt (*psi); | |
2400 tree res = gimple_phi_result (phi); | |
2401 basic_block bb; | |
2402 | |
2403 bb = gimple_bb (phi); | |
2404 rhs = degenerate_phi_result (phi); | |
2405 gcc_assert (rhs); | |
2406 | |
2407 stmt = gimple_build_assign (res, rhs); | |
2408 remove_phi_node (psi, false); | |
2409 SSA_NAME_DEF_STMT (res) = stmt; | |
2303 | 2410 |
2304 gsi = gsi_after_labels (bb); | 2411 gsi = gsi_after_labels (bb); |
2305 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT); | 2412 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT); |
2306 } | 2413 } |
2307 | 2414 |
2308 /* Return true when DEF can be analyzed in REGION by the scalar | 2415 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */ |
2309 evolution analyzer. */ | 2416 |
2310 | 2417 static void |
2311 static bool | 2418 rewrite_reductions_out_of_ssa (scop_p scop) |
2312 scev_analyzable_p (tree def, sese region) | 2419 { |
2313 { | 2420 basic_block bb; |
2314 gimple stmt = SSA_NAME_DEF_STMT (def); | 2421 gimple_stmt_iterator psi; |
2315 loop_p loop = loop_containing_stmt (stmt); | 2422 sese region = SCOP_REGION (scop); |
2316 tree scev = scalar_evolution_in_region (region, loop, def); | 2423 |
2317 | 2424 FOR_EACH_BB (bb) |
2318 return !chrec_contains_undetermined (scev); | 2425 if (bb_in_sese_p (bb, region)) |
2426 for (psi = gsi_start_phis (bb); !gsi_end_p (psi);) | |
2427 { | |
2428 gimple phi = gsi_stmt (psi); | |
2429 | |
2430 if (!is_gimple_reg (gimple_phi_result (phi))) | |
2431 { | |
2432 gsi_next (&psi); | |
2433 continue; | |
2434 } | |
2435 | |
2436 if (gimple_phi_num_args (phi) > 1 | |
2437 && degenerate_phi_result (phi)) | |
2438 rewrite_degenerate_phi (&psi); | |
2439 | |
2440 else if (scalar_close_phi_node_p (phi)) | |
2441 rewrite_close_phi_out_of_ssa (scop, &psi); | |
2442 | |
2443 else if (reduction_phi_p (region, &psi)) | |
2444 rewrite_phi_out_of_ssa (scop, &psi); | |
2445 } | |
2446 | |
2447 update_ssa (TODO_update_ssa); | |
2448 #ifdef ENABLE_CHECKING | |
2449 verify_loop_closed_ssa (true); | |
2450 #endif | |
2319 } | 2451 } |
2320 | 2452 |
2321 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory | 2453 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory |
2322 read from ZERO_DIM_ARRAY. */ | 2454 read from ZERO_DIM_ARRAY. */ |
2323 | 2455 |
2324 static void | 2456 static void |
2325 rewrite_cross_bb_scalar_dependence (tree zero_dim_array, tree def, gimple use_stmt) | 2457 rewrite_cross_bb_scalar_dependence (scop_p scop, tree zero_dim_array, |
2458 tree def, gimple use_stmt) | |
2326 { | 2459 { |
2327 tree var = SSA_NAME_VAR (def); | 2460 tree var = SSA_NAME_VAR (def); |
2328 gimple name_stmt = gimple_build_assign (var, zero_dim_array); | 2461 gimple name_stmt = gimple_build_assign (var, zero_dim_array); |
2329 tree name = make_ssa_name (var, name_stmt); | 2462 tree name = make_ssa_name (var, name_stmt); |
2330 ssa_op_iter iter; | 2463 ssa_op_iter iter; |
2331 use_operand_p use_p; | 2464 use_operand_p use_p; |
2332 gimple_stmt_iterator gsi; | |
2333 | 2465 |
2334 gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI); | 2466 gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI); |
2335 | 2467 |
2336 gimple_assign_set_lhs (name_stmt, name); | 2468 gimple_assign_set_lhs (name_stmt, name); |
2337 | 2469 insert_stmts (scop, name_stmt, NULL, gsi_for_stmt (use_stmt)); |
2338 gsi = gsi_for_stmt (use_stmt); | |
2339 gsi_insert_before (&gsi, name_stmt, GSI_NEW_STMT); | |
2340 | 2470 |
2341 FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES) | 2471 FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES) |
2342 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0)) | 2472 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0)) |
2343 replace_exp (use_p, name); | 2473 replace_exp (use_p, name); |
2344 | 2474 |
2345 update_stmt (use_stmt); | 2475 update_stmt (use_stmt); |
2346 } | 2476 } |
2347 | 2477 |
2478 /* For every definition DEF in the SCOP that is used outside the scop, | |
2479 insert a closing-scop definition in the basic block just after this | |
2480 SCOP. */ | |
2481 | |
2482 static void | |
2483 handle_scalar_deps_crossing_scop_limits (scop_p scop, tree def, gimple stmt) | |
2484 { | |
2485 tree var = create_tmp_reg (TREE_TYPE (def), NULL); | |
2486 tree new_name = make_ssa_name (var, stmt); | |
2487 bool needs_copy = false; | |
2488 use_operand_p use_p; | |
2489 imm_use_iterator imm_iter; | |
2490 gimple use_stmt; | |
2491 sese region = SCOP_REGION (scop); | |
2492 | |
2493 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) | |
2494 { | |
2495 if (!bb_in_sese_p (gimple_bb (use_stmt), region)) | |
2496 { | |
2497 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter) | |
2498 { | |
2499 SET_USE (use_p, new_name); | |
2500 } | |
2501 update_stmt (use_stmt); | |
2502 needs_copy = true; | |
2503 } | |
2504 } | |
2505 | |
2506 /* Insert in the empty BB just after the scop a use of DEF such | |
2507 that the rewrite of cross_bb_scalar_dependences won't insert | |
2508 arrays everywhere else. */ | |
2509 if (needs_copy) | |
2510 { | |
2511 gimple assign = gimple_build_assign (new_name, def); | |
2512 gimple_stmt_iterator psi = gsi_after_labels (SESE_EXIT (region)->dest); | |
2513 | |
2514 add_referenced_var (var); | |
2515 SSA_NAME_DEF_STMT (new_name) = assign; | |
2516 update_stmt (assign); | |
2517 gsi_insert_before (&psi, assign, GSI_SAME_STMT); | |
2518 } | |
2519 } | |
2520 | |
2348 /* Rewrite the scalar dependences crossing the boundary of the BB | 2521 /* Rewrite the scalar dependences crossing the boundary of the BB |
2349 containing STMT with an array. */ | 2522 containing STMT with an array. Return true when something has been |
2350 | 2523 changed. */ |
2351 static void | 2524 |
2352 rewrite_cross_bb_scalar_deps (sese region, gimple_stmt_iterator *gsi) | 2525 static bool |
2353 { | 2526 rewrite_cross_bb_scalar_deps (scop_p scop, gimple_stmt_iterator *gsi) |
2527 { | |
2528 sese region = SCOP_REGION (scop); | |
2354 gimple stmt = gsi_stmt (*gsi); | 2529 gimple stmt = gsi_stmt (*gsi); |
2355 imm_use_iterator imm_iter; | 2530 imm_use_iterator imm_iter; |
2356 tree def; | 2531 tree def; |
2357 basic_block def_bb; | 2532 basic_block def_bb; |
2358 tree zero_dim_array = NULL_TREE; | 2533 tree zero_dim_array = NULL_TREE; |
2359 gimple use_stmt; | 2534 gimple use_stmt; |
2360 | 2535 bool res = false; |
2361 if (gimple_code (stmt) != GIMPLE_ASSIGN) | 2536 |
2362 return; | 2537 switch (gimple_code (stmt)) |
2363 | 2538 { |
2364 def = gimple_assign_lhs (stmt); | 2539 case GIMPLE_ASSIGN: |
2365 if (!is_gimple_reg (def) | 2540 def = gimple_assign_lhs (stmt); |
2366 || scev_analyzable_p (def, region)) | 2541 break; |
2367 return; | 2542 |
2543 case GIMPLE_CALL: | |
2544 def = gimple_call_lhs (stmt); | |
2545 break; | |
2546 | |
2547 default: | |
2548 return false; | |
2549 } | |
2550 | |
2551 if (!def | |
2552 || !is_gimple_reg (def)) | |
2553 return false; | |
2554 | |
2555 if (scev_analyzable_p (def, region)) | |
2556 { | |
2557 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def)); | |
2558 tree scev = scalar_evolution_in_region (region, loop, def); | |
2559 | |
2560 if (tree_contains_chrecs (scev, NULL)) | |
2561 return false; | |
2562 | |
2563 propagate_expr_outside_region (def, scev, region); | |
2564 return true; | |
2565 } | |
2368 | 2566 |
2369 def_bb = gimple_bb (stmt); | 2567 def_bb = gimple_bb (stmt); |
2370 | 2568 |
2569 handle_scalar_deps_crossing_scop_limits (scop, def, stmt); | |
2570 | |
2371 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) | 2571 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) |
2372 if (def_bb != gimple_bb (use_stmt) | 2572 if (gimple_code (use_stmt) == GIMPLE_PHI |
2373 && gimple_code (use_stmt) != GIMPLE_PHI | 2573 && (res = true)) |
2374 && !is_gimple_debug (use_stmt)) | 2574 { |
2575 gimple_stmt_iterator psi = gsi_for_stmt (use_stmt); | |
2576 | |
2577 if (scalar_close_phi_node_p (gsi_stmt (psi))) | |
2578 rewrite_close_phi_out_of_ssa (scop, &psi); | |
2579 else | |
2580 rewrite_phi_out_of_ssa (scop, &psi); | |
2581 } | |
2582 | |
2583 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) | |
2584 if (gimple_code (use_stmt) != GIMPLE_PHI | |
2585 && def_bb != gimple_bb (use_stmt) | |
2586 && !is_gimple_debug (use_stmt) | |
2587 && (res = true)) | |
2375 { | 2588 { |
2376 if (!zero_dim_array) | 2589 if (!zero_dim_array) |
2377 { | 2590 { |
2378 zero_dim_array = create_zero_dim_array | 2591 zero_dim_array = create_zero_dim_array |
2379 (SSA_NAME_VAR (def), "Cross_BB_scalar_dependence"); | 2592 (SSA_NAME_VAR (def), "Cross_BB_scalar_dependence"); |
2380 insert_out_of_ssa_copy (zero_dim_array, def); | 2593 insert_out_of_ssa_copy (scop, zero_dim_array, def, |
2594 SSA_NAME_DEF_STMT (def)); | |
2381 gsi_next (gsi); | 2595 gsi_next (gsi); |
2382 } | 2596 } |
2383 | 2597 |
2384 rewrite_cross_bb_scalar_dependence (zero_dim_array, def, use_stmt); | 2598 rewrite_cross_bb_scalar_dependence (scop, zero_dim_array, |
2599 def, use_stmt); | |
2385 } | 2600 } |
2601 | |
2602 return res; | |
2386 } | 2603 } |
2387 | 2604 |
2388 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */ | 2605 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */ |
2389 | 2606 |
2390 static void | 2607 static void |
2391 rewrite_reductions_out_of_ssa (scop_p scop) | 2608 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop) |
2392 { | 2609 { |
2393 basic_block bb; | 2610 basic_block bb; |
2394 gimple_stmt_iterator psi; | 2611 gimple_stmt_iterator psi; |
2395 sese region = SCOP_REGION (scop); | 2612 sese region = SCOP_REGION (scop); |
2396 | 2613 bool changed = false; |
2397 FOR_EACH_BB (bb) | 2614 |
2398 if (bb_in_sese_p (bb, region)) | 2615 /* Create an extra empty BB after the scop. */ |
2399 for (psi = gsi_start_phis (bb); !gsi_end_p (psi);) | 2616 split_edge (SESE_EXIT (region)); |
2400 { | |
2401 if (scalar_close_phi_node_p (gsi_stmt (psi))) | |
2402 rewrite_close_phi_out_of_ssa (&psi); | |
2403 else if (reduction_phi_p (region, &psi)) | |
2404 rewrite_phi_out_of_ssa (&psi); | |
2405 } | |
2406 | |
2407 update_ssa (TODO_update_ssa); | |
2408 #ifdef ENABLE_CHECKING | |
2409 verify_loop_closed_ssa (true); | |
2410 #endif | |
2411 | 2617 |
2412 FOR_EACH_BB (bb) | 2618 FOR_EACH_BB (bb) |
2413 if (bb_in_sese_p (bb, region)) | 2619 if (bb_in_sese_p (bb, region)) |
2414 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) | 2620 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) |
2415 rewrite_cross_bb_scalar_deps (region, &psi); | 2621 changed |= rewrite_cross_bb_scalar_deps (scop, &psi); |
2416 | 2622 |
2417 update_ssa (TODO_update_ssa); | 2623 if (changed) |
2624 { | |
2625 scev_reset_htab (); | |
2626 update_ssa (TODO_update_ssa); | |
2418 #ifdef ENABLE_CHECKING | 2627 #ifdef ENABLE_CHECKING |
2419 verify_loop_closed_ssa (true); | 2628 verify_loop_closed_ssa (true); |
2420 #endif | 2629 #endif |
2630 } | |
2421 } | 2631 } |
2422 | 2632 |
2423 /* Returns the number of pbbs that are in loops contained in SCOP. */ | 2633 /* Returns the number of pbbs that are in loops contained in SCOP. */ |
2424 | 2634 |
2425 static int | 2635 static int |
2427 { | 2637 { |
2428 int i; | 2638 int i; |
2429 poly_bb_p pbb; | 2639 poly_bb_p pbb; |
2430 int res = 0; | 2640 int res = 0; |
2431 | 2641 |
2432 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) | 2642 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) |
2433 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop))) | 2643 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop))) |
2434 res++; | 2644 res++; |
2435 | 2645 |
2436 return res; | 2646 return res; |
2437 } | 2647 } |
2450 res++; | 2660 res++; |
2451 | 2661 |
2452 return res; | 2662 return res; |
2453 } | 2663 } |
2454 | 2664 |
2455 /* Splits STMT out of its current BB. */ | 2665 /* Splits at STMT the basic block BB represented as PBB in the |
2666 polyhedral form. */ | |
2667 | |
2668 static edge | |
2669 split_pbb (scop_p scop, poly_bb_p pbb, basic_block bb, gimple stmt) | |
2670 { | |
2671 edge e1 = split_block (bb, stmt); | |
2672 new_pbb_from_pbb (scop, pbb, e1->dest); | |
2673 return e1; | |
2674 } | |
2675 | |
2676 /* Splits STMT out of its current BB. This is done for reduction | |
2677 statements for which we want to ignore data dependences. */ | |
2456 | 2678 |
2457 static basic_block | 2679 static basic_block |
2458 split_reduction_stmt (gimple stmt) | 2680 split_reduction_stmt (scop_p scop, gimple stmt) |
2459 { | 2681 { |
2460 gimple_stmt_iterator gsi; | |
2461 basic_block bb = gimple_bb (stmt); | 2682 basic_block bb = gimple_bb (stmt); |
2462 edge e; | 2683 poly_bb_p pbb = pbb_from_bb (bb); |
2684 gimple_bb_p gbb = gbb_from_bb (bb); | |
2685 edge e1; | |
2686 int i; | |
2687 data_reference_p dr; | |
2463 | 2688 |
2464 /* Do not split basic blocks with no writes to memory: the reduction | 2689 /* Do not split basic blocks with no writes to memory: the reduction |
2465 will be the only write to memory. */ | 2690 will be the only write to memory. */ |
2466 if (nb_data_writes_in_bb (bb) == 0) | 2691 if (nb_data_writes_in_bb (bb) == 0 |
2692 /* Or if we have already marked BB as a reduction. */ | |
2693 || PBB_IS_REDUCTION (pbb_from_bb (bb))) | |
2467 return bb; | 2694 return bb; |
2468 | 2695 |
2469 split_block (bb, stmt); | 2696 e1 = split_pbb (scop, pbb, bb, stmt); |
2470 | 2697 |
2471 if (gsi_one_before_end_p (gsi_start_nondebug_bb (bb))) | 2698 /* Split once more only when the reduction stmt is not the only one |
2472 return bb; | 2699 left in the original BB. */ |
2473 | 2700 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb))) |
2474 gsi = gsi_last_bb (bb); | 2701 { |
2475 gsi_prev (&gsi); | 2702 gimple_stmt_iterator gsi = gsi_last_bb (bb); |
2476 e = split_block (bb, gsi_stmt (gsi)); | 2703 gsi_prev (&gsi); |
2477 | 2704 e1 = split_pbb (scop, pbb, bb, gsi_stmt (gsi)); |
2478 return e->dest; | 2705 } |
2706 | |
2707 /* A part of the data references will end in a different basic block | |
2708 after the split: move the DRs from the original GBB to the newly | |
2709 created GBB1. */ | |
2710 FOR_EACH_VEC_ELT (data_reference_p, GBB_DATA_REFS (gbb), i, dr) | |
2711 { | |
2712 basic_block bb1 = gimple_bb (DR_STMT (dr)); | |
2713 | |
2714 if (bb1 != bb) | |
2715 { | |
2716 gimple_bb_p gbb1 = gbb_from_bb (bb1); | |
2717 VEC_safe_push (data_reference_p, heap, GBB_DATA_REFS (gbb1), dr); | |
2718 VEC_ordered_remove (data_reference_p, GBB_DATA_REFS (gbb), i); | |
2719 i--; | |
2720 } | |
2721 } | |
2722 | |
2723 return e1->dest; | |
2479 } | 2724 } |
2480 | 2725 |
2481 /* Return true when stmt is a reduction operation. */ | 2726 /* Return true when stmt is a reduction operation. */ |
2482 | 2727 |
2483 static inline bool | 2728 static inline bool |
2564 VEC_safe_push (gimple, heap, *out, stmt); | 2809 VEC_safe_push (gimple, heap, *out, stmt); |
2565 return phi; | 2810 return phi; |
2566 } | 2811 } |
2567 | 2812 |
2568 /* Detect commutative and associative scalar reductions starting at | 2813 /* Detect commutative and associative scalar reductions starting at |
2569 the STMT. Return the phi node of the reduction cycle, or NULL. */ | 2814 STMT. Return the phi node of the reduction cycle, or NULL. */ |
2570 | 2815 |
2571 static gimple | 2816 static gimple |
2572 detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in, | 2817 detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in, |
2573 VEC (gimple, heap) **out) | 2818 VEC (gimple, heap) **out) |
2574 { | 2819 { |
2651 } | 2896 } |
2652 | 2897 |
2653 return NULL_TREE; | 2898 return NULL_TREE; |
2654 } | 2899 } |
2655 | 2900 |
2656 /* Detect commutative and associative scalar reductions starting at | 2901 /* Returns true when DEF is used outside the reduction cycle of |
2657 the loop closed phi node CLOSE_PHI. Return the phi node of the | 2902 LOOP_PHI. */ |
2658 reduction cycle, or NULL. */ | 2903 |
2904 static bool | |
2905 used_outside_reduction (tree def, gimple loop_phi) | |
2906 { | |
2907 use_operand_p use_p; | |
2908 imm_use_iterator imm_iter; | |
2909 loop_p loop = loop_containing_stmt (loop_phi); | |
2910 | |
2911 /* In LOOP, DEF should be used only in LOOP_PHI. */ | |
2912 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def) | |
2913 { | |
2914 gimple stmt = USE_STMT (use_p); | |
2915 | |
2916 if (stmt != loop_phi | |
2917 && !is_gimple_debug (stmt) | |
2918 && flow_bb_inside_loop_p (loop, gimple_bb (stmt))) | |
2919 return true; | |
2920 } | |
2921 | |
2922 return false; | |
2923 } | |
2924 | |
2925 /* Detect commutative and associative scalar reductions belonging to | |
2926 the SCOP starting at the loop closed phi node STMT. Return the phi | |
2927 node of the reduction cycle, or NULL. */ | |
2659 | 2928 |
2660 static gimple | 2929 static gimple |
2661 detect_commutative_reduction (gimple stmt, VEC (gimple, heap) **in, | 2930 detect_commutative_reduction (scop_p scop, gimple stmt, VEC (gimple, heap) **in, |
2662 VEC (gimple, heap) **out) | 2931 VEC (gimple, heap) **out) |
2663 { | 2932 { |
2664 if (scalar_close_phi_node_p (stmt)) | 2933 if (scalar_close_phi_node_p (stmt)) |
2665 { | 2934 { |
2666 tree arg = gimple_phi_arg_def (stmt, 0); | 2935 gimple def, loop_phi, phi, close_phi = stmt; |
2667 gimple def, loop_phi; | 2936 tree init, lhs, arg = gimple_phi_arg_def (close_phi, 0); |
2668 | 2937 |
2669 if (TREE_CODE (arg) != SSA_NAME) | 2938 if (TREE_CODE (arg) != SSA_NAME) |
2670 return NULL; | 2939 return NULL; |
2671 | 2940 |
2672 /* Note that loop close phi nodes should have a single argument | 2941 /* Note that loop close phi nodes should have a single argument |
2673 because we translated the representation into a canonical form | 2942 because we translated the representation into a canonical form |
2674 before Graphite: see canonicalize_loop_closed_ssa_form. */ | 2943 before Graphite: see canonicalize_loop_closed_ssa_form. */ |
2675 gcc_assert (gimple_phi_num_args (stmt) == 1); | 2944 gcc_assert (gimple_phi_num_args (close_phi) == 1); |
2676 | 2945 |
2677 def = SSA_NAME_DEF_STMT (arg); | 2946 def = SSA_NAME_DEF_STMT (arg); |
2678 loop_phi = detect_commutative_reduction (def, in, out); | 2947 if (!stmt_in_sese_p (def, SCOP_REGION (scop)) |
2679 | 2948 || !(loop_phi = detect_commutative_reduction (scop, def, in, out))) |
2680 if (loop_phi) | |
2681 { | |
2682 tree lhs = gimple_phi_result (stmt); | |
2683 tree init = initial_value_for_loop_phi (loop_phi); | |
2684 gimple phi = follow_inital_value_to_phi (init, lhs); | |
2685 | |
2686 VEC_safe_push (gimple, heap, *in, loop_phi); | |
2687 VEC_safe_push (gimple, heap, *out, stmt); | |
2688 return phi; | |
2689 } | |
2690 else | |
2691 return NULL; | 2949 return NULL; |
2950 | |
2951 lhs = gimple_phi_result (close_phi); | |
2952 init = initial_value_for_loop_phi (loop_phi); | |
2953 phi = follow_inital_value_to_phi (init, lhs); | |
2954 | |
2955 if (phi && (used_outside_reduction (lhs, phi) | |
2956 || !has_single_use (gimple_phi_result (phi)))) | |
2957 return NULL; | |
2958 | |
2959 VEC_safe_push (gimple, heap, *in, loop_phi); | |
2960 VEC_safe_push (gimple, heap, *out, close_phi); | |
2961 return phi; | |
2692 } | 2962 } |
2693 | 2963 |
2694 if (gimple_code (stmt) == GIMPLE_ASSIGN) | 2964 if (gimple_code (stmt) == GIMPLE_ASSIGN) |
2695 return detect_commutative_reduction_assign (stmt, in, out); | 2965 return detect_commutative_reduction_assign (stmt, in, out); |
2696 | 2966 |
2699 | 2969 |
2700 /* Translate the scalar reduction statement STMT to an array RED | 2970 /* Translate the scalar reduction statement STMT to an array RED |
2701 knowing that its recursive phi node is LOOP_PHI. */ | 2971 knowing that its recursive phi node is LOOP_PHI. */ |
2702 | 2972 |
2703 static void | 2973 static void |
2704 translate_scalar_reduction_to_array_for_stmt (tree red, gimple stmt, | 2974 translate_scalar_reduction_to_array_for_stmt (scop_p scop, tree red, |
2705 gimple loop_phi) | 2975 gimple stmt, gimple loop_phi) |
2706 { | 2976 { |
2707 gimple_stmt_iterator insert_gsi = gsi_after_labels (gimple_bb (loop_phi)); | |
2708 tree res = gimple_phi_result (loop_phi); | 2977 tree res = gimple_phi_result (loop_phi); |
2709 gimple assign = gimple_build_assign (res, red); | 2978 gimple assign = gimple_build_assign (res, unshare_expr (red)); |
2710 | 2979 gimple_stmt_iterator gsi; |
2711 gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT); | 2980 |
2712 | 2981 insert_stmts (scop, assign, NULL, gsi_after_labels (gimple_bb (loop_phi))); |
2713 insert_gsi = gsi_after_labels (gimple_bb (stmt)); | 2982 |
2714 assign = gimple_build_assign (red, gimple_assign_lhs (stmt)); | 2983 assign = gimple_build_assign (unshare_expr (red), gimple_assign_lhs (stmt)); |
2715 insert_gsi = gsi_for_stmt (stmt); | 2984 gsi = gsi_for_stmt (stmt); |
2716 gsi_insert_after (&insert_gsi, assign, GSI_SAME_STMT); | 2985 gsi_next (&gsi); |
2717 } | 2986 insert_stmts (scop, assign, NULL, gsi); |
2718 | |
2719 /* Insert the assignment "result (CLOSE_PHI) = RED". */ | |
2720 | |
2721 static void | |
2722 insert_copyout (tree red, gimple close_phi) | |
2723 { | |
2724 tree res = gimple_phi_result (close_phi); | |
2725 basic_block bb = gimple_bb (close_phi); | |
2726 gimple_stmt_iterator insert_gsi = gsi_after_labels (bb); | |
2727 gimple assign = gimple_build_assign (res, red); | |
2728 | |
2729 gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT); | |
2730 } | |
2731 | |
2732 /* Insert the assignment "RED = initial_value (LOOP_PHI)". */ | |
2733 | |
2734 static void | |
2735 insert_copyin (tree red, gimple loop_phi) | |
2736 { | |
2737 gimple_seq stmts; | |
2738 tree init = initial_value_for_loop_phi (loop_phi); | |
2739 tree expr = build2 (MODIFY_EXPR, TREE_TYPE (init), red, init); | |
2740 | |
2741 force_gimple_operand (expr, &stmts, true, NULL); | |
2742 gsi_insert_seq_on_edge (edge_initial_value_for_loop_phi (loop_phi), stmts); | |
2743 } | 2987 } |
2744 | 2988 |
2745 /* Removes the PHI node and resets all the debug stmts that are using | 2989 /* Removes the PHI node and resets all the debug stmts that are using |
2746 the PHI_RESULT. */ | 2990 the PHI_RESULT. */ |
2747 | 2991 |
2766 gimple_debug_bind_reset_value (stmt); | 3010 gimple_debug_bind_reset_value (stmt); |
2767 VEC_safe_push (gimple, heap, update, stmt); | 3011 VEC_safe_push (gimple, heap, update, stmt); |
2768 } | 3012 } |
2769 } | 3013 } |
2770 | 3014 |
2771 for (i = 0; VEC_iterate (gimple, update, i, stmt); i++) | 3015 FOR_EACH_VEC_ELT (gimple, update, i, stmt) |
2772 update_stmt (stmt); | 3016 update_stmt (stmt); |
2773 | 3017 |
2774 VEC_free (gimple, heap, update); | 3018 VEC_free (gimple, heap, update); |
2775 | 3019 |
2776 gsi = gsi_for_phi_node (phi); | 3020 gsi = gsi_for_phi_node (phi); |
2777 remove_phi_node (&gsi, false); | 3021 remove_phi_node (&gsi, false); |
3022 } | |
3023 | |
3024 /* Helper function for for_each_index. For each INDEX of the data | |
3025 reference REF, returns true when its indices are valid in the loop | |
3026 nest LOOP passed in as DATA. */ | |
3027 | |
3028 static bool | |
3029 dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED, tree *index, void *data) | |
3030 { | |
3031 loop_p loop; | |
3032 basic_block header, def_bb; | |
3033 gimple stmt; | |
3034 | |
3035 if (TREE_CODE (*index) != SSA_NAME) | |
3036 return true; | |
3037 | |
3038 loop = *((loop_p *) data); | |
3039 header = loop->header; | |
3040 stmt = SSA_NAME_DEF_STMT (*index); | |
3041 | |
3042 if (!stmt) | |
3043 return true; | |
3044 | |
3045 def_bb = gimple_bb (stmt); | |
3046 | |
3047 if (!def_bb) | |
3048 return true; | |
3049 | |
3050 return dominated_by_p (CDI_DOMINATORS, header, def_bb); | |
3051 } | |
3052 | |
3053 /* When the result of a CLOSE_PHI is written to a memory location, | |
3054 return a pointer to that memory reference, otherwise return | |
3055 NULL_TREE. */ | |
3056 | |
3057 static tree | |
3058 close_phi_written_to_memory (gimple close_phi) | |
3059 { | |
3060 imm_use_iterator imm_iter; | |
3061 use_operand_p use_p; | |
3062 gimple stmt; | |
3063 tree res, def = gimple_phi_result (close_phi); | |
3064 | |
3065 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def) | |
3066 if ((stmt = USE_STMT (use_p)) | |
3067 && gimple_code (stmt) == GIMPLE_ASSIGN | |
3068 && (res = gimple_assign_lhs (stmt))) | |
3069 { | |
3070 switch (TREE_CODE (res)) | |
3071 { | |
3072 case VAR_DECL: | |
3073 case PARM_DECL: | |
3074 case RESULT_DECL: | |
3075 return res; | |
3076 | |
3077 case ARRAY_REF: | |
3078 case MEM_REF: | |
3079 { | |
3080 tree arg = gimple_phi_arg_def (close_phi, 0); | |
3081 loop_p nest = loop_containing_stmt (SSA_NAME_DEF_STMT (arg)); | |
3082 | |
3083 /* FIXME: this restriction is for id-{24,25}.f and | |
3084 could be handled by duplicating the computation of | |
3085 array indices before the loop of the close_phi. */ | |
3086 if (for_each_index (&res, dr_indices_valid_in_loop, &nest)) | |
3087 return res; | |
3088 } | |
3089 /* Fallthru. */ | |
3090 | |
3091 default: | |
3092 continue; | |
3093 } | |
3094 } | |
3095 return NULL_TREE; | |
2778 } | 3096 } |
2779 | 3097 |
2780 /* Rewrite out of SSA the reduction described by the loop phi nodes | 3098 /* Rewrite out of SSA the reduction described by the loop phi nodes |
2781 IN, and the close phi nodes OUT. IN and OUT are structured by loop | 3099 IN, and the close phi nodes OUT. IN and OUT are structured by loop |
2782 levels like this: | 3100 levels like this: |
2786 | 3104 |
2787 the first element is the reduction statement, and the next elements | 3105 the first element is the reduction statement, and the next elements |
2788 are the loop and close phi nodes of each of the outer loops. */ | 3106 are the loop and close phi nodes of each of the outer loops. */ |
2789 | 3107 |
2790 static void | 3108 static void |
2791 translate_scalar_reduction_to_array (VEC (gimple, heap) *in, | 3109 translate_scalar_reduction_to_array (scop_p scop, |
2792 VEC (gimple, heap) *out, | 3110 VEC (gimple, heap) *in, |
2793 sbitmap reductions) | 3111 VEC (gimple, heap) *out) |
2794 { | 3112 { |
2795 unsigned int i; | |
2796 gimple loop_phi; | 3113 gimple loop_phi; |
2797 tree red = NULL_TREE; | 3114 unsigned int i = VEC_length (gimple, out) - 1; |
2798 | 3115 tree red = close_phi_written_to_memory (VEC_index (gimple, out, i)); |
2799 for (i = 0; VEC_iterate (gimple, in, i, loop_phi); i++) | 3116 |
3117 FOR_EACH_VEC_ELT (gimple, in, i, loop_phi) | |
2800 { | 3118 { |
2801 gimple close_phi = VEC_index (gimple, out, i); | 3119 gimple close_phi = VEC_index (gimple, out, i); |
2802 | 3120 |
2803 if (i == 0) | 3121 if (i == 0) |
2804 { | 3122 { |
2805 gimple stmt = loop_phi; | 3123 gimple stmt = loop_phi; |
2806 basic_block bb = split_reduction_stmt (stmt); | 3124 basic_block bb = split_reduction_stmt (scop, stmt); |
2807 | 3125 poly_bb_p pbb = pbb_from_bb (bb); |
2808 SET_BIT (reductions, bb->index); | 3126 PBB_IS_REDUCTION (pbb) = true; |
2809 gcc_assert (close_phi == loop_phi); | 3127 gcc_assert (close_phi == loop_phi); |
2810 | 3128 |
2811 red = create_zero_dim_array | 3129 if (!red) |
2812 (gimple_assign_lhs (stmt), "Commutative_Associative_Reduction"); | 3130 red = create_zero_dim_array |
3131 (gimple_assign_lhs (stmt), "Commutative_Associative_Reduction"); | |
3132 | |
2813 translate_scalar_reduction_to_array_for_stmt | 3133 translate_scalar_reduction_to_array_for_stmt |
2814 (red, stmt, VEC_index (gimple, in, 1)); | 3134 (scop, red, stmt, VEC_index (gimple, in, 1)); |
2815 continue; | 3135 continue; |
2816 } | 3136 } |
2817 | 3137 |
2818 if (i == VEC_length (gimple, in) - 1) | 3138 if (i == VEC_length (gimple, in) - 1) |
2819 { | 3139 { |
2820 insert_copyout (red, close_phi); | 3140 insert_out_of_ssa_copy (scop, gimple_phi_result (close_phi), |
2821 insert_copyin (red, loop_phi); | 3141 unshare_expr (red), close_phi); |
3142 insert_out_of_ssa_copy_on_edge | |
3143 (scop, edge_initial_value_for_loop_phi (loop_phi), | |
3144 unshare_expr (red), initial_value_for_loop_phi (loop_phi)); | |
2822 } | 3145 } |
2823 | 3146 |
2824 remove_phi (loop_phi); | 3147 remove_phi (loop_phi); |
2825 remove_phi (close_phi); | 3148 remove_phi (close_phi); |
2826 } | 3149 } |
2827 } | 3150 } |
2828 | 3151 |
2829 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. */ | 3152 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns |
2830 | 3153 true when something has been changed. */ |
2831 static void | 3154 |
2832 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi, | 3155 static bool |
2833 sbitmap reductions) | 3156 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop, |
2834 { | 3157 gimple close_phi) |
3158 { | |
3159 bool res; | |
2835 VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10); | 3160 VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10); |
2836 VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10); | 3161 VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10); |
2837 | 3162 |
2838 detect_commutative_reduction (close_phi, &in, &out); | 3163 detect_commutative_reduction (scop, close_phi, &in, &out); |
2839 if (VEC_length (gimple, in) > 0) | 3164 res = VEC_length (gimple, in) > 1; |
2840 translate_scalar_reduction_to_array (in, out, reductions); | 3165 if (res) |
3166 translate_scalar_reduction_to_array (scop, in, out); | |
2841 | 3167 |
2842 VEC_free (gimple, heap, in); | 3168 VEC_free (gimple, heap, in); |
2843 VEC_free (gimple, heap, out); | 3169 VEC_free (gimple, heap, out); |
2844 } | 3170 return res; |
2845 | 3171 } |
2846 /* Rewrites all the commutative reductions from LOOP out of SSA. */ | 3172 |
2847 | 3173 /* Rewrites all the commutative reductions from LOOP out of SSA. |
2848 static void | 3174 Returns true when something has been changed. */ |
2849 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop, | 3175 |
2850 sbitmap reductions) | 3176 static bool |
3177 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop, | |
3178 loop_p loop) | |
2851 { | 3179 { |
2852 gimple_stmt_iterator gsi; | 3180 gimple_stmt_iterator gsi; |
2853 edge exit = single_exit (loop); | 3181 edge exit = single_exit (loop); |
3182 tree res; | |
3183 bool changed = false; | |
2854 | 3184 |
2855 if (!exit) | 3185 if (!exit) |
2856 return; | 3186 return false; |
2857 | 3187 |
2858 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi)) | 3188 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi)) |
2859 rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi), | 3189 if ((res = gimple_phi_result (gsi_stmt (gsi))) |
2860 reductions); | 3190 && is_gimple_reg (res) |
3191 && !scev_analyzable_p (res, SCOP_REGION (scop))) | |
3192 changed |= rewrite_commutative_reductions_out_of_ssa_close_phi | |
3193 (scop, gsi_stmt (gsi)); | |
3194 | |
3195 return changed; | |
2861 } | 3196 } |
2862 | 3197 |
2863 /* Rewrites all the commutative reductions from SCOP out of SSA. */ | 3198 /* Rewrites all the commutative reductions from SCOP out of SSA. */ |
2864 | 3199 |
2865 static void | 3200 static void |
2866 rewrite_commutative_reductions_out_of_ssa (sese region, sbitmap reductions) | 3201 rewrite_commutative_reductions_out_of_ssa (scop_p scop) |
2867 { | 3202 { |
2868 loop_iterator li; | 3203 loop_iterator li; |
2869 loop_p loop; | 3204 loop_p loop; |
3205 bool changed = false; | |
3206 sese region = SCOP_REGION (scop); | |
2870 | 3207 |
2871 FOR_EACH_LOOP (li, loop, 0) | 3208 FOR_EACH_LOOP (li, loop, 0) |
2872 if (loop_in_sese_p (loop, region)) | 3209 if (loop_in_sese_p (loop, region)) |
2873 rewrite_commutative_reductions_out_of_ssa_loop (loop, reductions); | 3210 changed |= rewrite_commutative_reductions_out_of_ssa_loop (scop, loop); |
2874 | 3211 |
2875 gsi_commit_edge_inserts (); | 3212 if (changed) |
2876 update_ssa (TODO_update_ssa); | 3213 { |
3214 scev_reset_htab (); | |
3215 gsi_commit_edge_inserts (); | |
3216 update_ssa (TODO_update_ssa); | |
2877 #ifdef ENABLE_CHECKING | 3217 #ifdef ENABLE_CHECKING |
2878 verify_loop_closed_ssa (true); | 3218 verify_loop_closed_ssa (true); |
2879 #endif | 3219 #endif |
2880 } | 3220 } |
2881 | |
2882 /* A LOOP is in normal form for Graphite when it contains only one | |
2883 scalar phi node that defines the main induction variable of the | |
2884 loop, only one increment of the IV, and only one exit condition. */ | |
2885 | |
2886 static void | |
2887 graphite_loop_normal_form (loop_p loop) | |
2888 { | |
2889 struct tree_niter_desc niter; | |
2890 tree nit; | |
2891 gimple_seq stmts; | |
2892 edge exit = single_dom_exit (loop); | |
2893 | |
2894 bool known_niter = number_of_iterations_exit (loop, exit, &niter, false); | |
2895 | |
2896 /* At this point we should know the number of iterations. */ | |
2897 gcc_assert (known_niter); | |
2898 | |
2899 nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true, | |
2900 NULL_TREE); | |
2901 if (stmts) | |
2902 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts); | |
2903 | |
2904 loop->single_iv = canonicalize_loop_ivs (loop, &nit, false); | |
2905 } | |
2906 | |
2907 /* Rewrite all the loops of SCOP in normal form: one induction | |
2908 variable per loop. */ | |
2909 | |
2910 static void | |
2911 scop_canonicalize_loops (scop_p scop) | |
2912 { | |
2913 loop_iterator li; | |
2914 loop_p loop; | |
2915 | |
2916 FOR_EACH_LOOP (li, loop, 0) | |
2917 if (loop_in_sese_p (loop, SCOP_REGION (scop))) | |
2918 graphite_loop_normal_form (loop); | |
2919 } | 3221 } |
2920 | 3222 |
2921 /* Java does not initialize long_long_integer_type_node. */ | 3223 /* Java does not initialize long_long_integer_type_node. */ |
2922 #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype) | 3224 #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype) |
2923 | 3225 |
2924 /* Can all ivs be represented by a signed integer? | 3226 /* Can all ivs be represented by a signed integer? |
2925 As CLooG might generate negative values in its expressions, signed loop ivs | 3227 As CLooG might generate negative values in its expressions, signed loop ivs |
2926 are required in the backend. */ | 3228 are required in the backend. */ |
3229 | |
2927 static bool | 3230 static bool |
2928 scop_ivs_can_be_represented (scop_p scop) | 3231 scop_ivs_can_be_represented (scop_p scop) |
2929 { | 3232 { |
2930 loop_iterator li; | 3233 loop_iterator li; |
2931 loop_p loop; | 3234 loop_p loop; |
3235 gimple_stmt_iterator psi; | |
2932 | 3236 |
2933 FOR_EACH_LOOP (li, loop, 0) | 3237 FOR_EACH_LOOP (li, loop, 0) |
2934 { | 3238 { |
2935 tree type; | |
2936 int precision; | |
2937 | |
2938 if (!loop_in_sese_p (loop, SCOP_REGION (scop))) | 3239 if (!loop_in_sese_p (loop, SCOP_REGION (scop))) |
2939 continue; | 3240 continue; |
2940 | 3241 |
2941 if (!loop->single_iv) | 3242 for (psi = gsi_start_phis (loop->header); |
2942 continue; | 3243 !gsi_end_p (psi); gsi_next (&psi)) |
2943 | 3244 { |
2944 type = TREE_TYPE(loop->single_iv); | 3245 gimple phi = gsi_stmt (psi); |
2945 precision = TYPE_PRECISION (type); | 3246 tree res = PHI_RESULT (phi); |
2946 | 3247 tree type = TREE_TYPE (res); |
2947 if (TYPE_UNSIGNED (type) | 3248 |
2948 && precision >= TYPE_PRECISION (my_long_long)) | 3249 if (TYPE_UNSIGNED (type) |
2949 return false; | 3250 && TYPE_PRECISION (type) >= TYPE_PRECISION (my_long_long)) |
3251 return false; | |
3252 } | |
2950 } | 3253 } |
2951 | 3254 |
2952 return true; | 3255 return true; |
2953 } | 3256 } |
2954 | 3257 |
2958 | 3261 |
2959 void | 3262 void |
2960 build_poly_scop (scop_p scop) | 3263 build_poly_scop (scop_p scop) |
2961 { | 3264 { |
2962 sese region = SCOP_REGION (scop); | 3265 sese region = SCOP_REGION (scop); |
2963 sbitmap reductions = sbitmap_alloc (last_basic_block * 2); | |
2964 graphite_dim_t max_dim; | 3266 graphite_dim_t max_dim; |
2965 | 3267 |
2966 sbitmap_zero (reductions); | 3268 build_scop_bbs (scop); |
2967 rewrite_commutative_reductions_out_of_ssa (region, reductions); | |
2968 rewrite_reductions_out_of_ssa (scop); | |
2969 build_scop_bbs (scop, reductions); | |
2970 sbitmap_free (reductions); | |
2971 | 3269 |
2972 /* FIXME: This restriction is needed to avoid a problem in CLooG. | 3270 /* FIXME: This restriction is needed to avoid a problem in CLooG. |
2973 Once CLooG is fixed, remove this guard. Anyways, it makes no | 3271 Once CLooG is fixed, remove this guard. Anyways, it makes no |
2974 sense to optimize a scop containing only PBBs that do not belong | 3272 sense to optimize a scop containing only PBBs that do not belong |
2975 to any loops. */ | 3273 to any loops. */ |
2976 if (nb_pbbs_in_loops (scop) == 0) | 3274 if (nb_pbbs_in_loops (scop) == 0) |
2977 return; | 3275 return; |
2978 | 3276 |
2979 scop_canonicalize_loops (scop); | |
2980 if (!scop_ivs_can_be_represented (scop)) | 3277 if (!scop_ivs_can_be_represented (scop)) |
2981 return; | 3278 return; |
3279 | |
3280 if (flag_associative_math) | |
3281 rewrite_commutative_reductions_out_of_ssa (scop); | |
2982 | 3282 |
2983 build_sese_loop_nests (region); | 3283 build_sese_loop_nests (region); |
2984 build_sese_conditions (region); | 3284 build_sese_conditions (region); |
2985 find_scop_parameters (scop); | 3285 find_scop_parameters (scop); |
2986 | 3286 |
2988 if (scop_nb_params (scop) > max_dim) | 3288 if (scop_nb_params (scop) > max_dim) |
2989 return; | 3289 return; |
2990 | 3290 |
2991 build_scop_iteration_domain (scop); | 3291 build_scop_iteration_domain (scop); |
2992 build_scop_context (scop); | 3292 build_scop_context (scop); |
2993 | |
2994 add_conditions_to_constraints (scop); | 3293 add_conditions_to_constraints (scop); |
3294 | |
3295 /* Rewrite out of SSA only after having translated the | |
3296 representation to the polyhedral representation to avoid scev | |
3297 analysis failures. That means that these functions will insert | |
3298 new data references that they create in the right place. */ | |
3299 rewrite_reductions_out_of_ssa (scop); | |
3300 rewrite_cross_bb_scalar_deps_out_of_ssa (scop); | |
3301 | |
3302 build_scop_drs (scop); | |
2995 scop_to_lst (scop); | 3303 scop_to_lst (scop); |
2996 build_scop_scattering (scop); | 3304 build_scop_scattering (scop); |
2997 build_scop_drs (scop); | |
2998 | 3305 |
2999 /* This SCoP has been translated to the polyhedral | 3306 /* This SCoP has been translated to the polyhedral |
3000 representation. */ | 3307 representation. */ |
3001 POLY_SCOP_P (scop) = true; | 3308 POLY_SCOP_P (scop) = true; |
3002 } | 3309 } |
3003 | |
3004 /* Always return false. Exercise the scop_to_clast function. */ | |
3005 | |
3006 void | |
3007 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED) | |
3008 { | |
3009 #ifdef ENABLE_CHECKING | |
3010 cloog_prog_clast pc = scop_to_clast (scop); | |
3011 cloog_clast_free (pc.stmt); | |
3012 cloog_program_free (pc.prog); | |
3013 #endif | 3310 #endif |
3014 } | |
3015 #endif |