1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009, 2010, 2011 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tree-flow.h"
25 #include "tree-dump.h"
26 #include "cfgloop.h"
27 #include "tree-chrec.h"
28 #include "tree-data-ref.h"
29 #include "tree-scalar-evolution.h"
30 #include "domwalk.h"
31 #include "sese.h"
32
33 #ifdef HAVE_cloog
34 #include "ppl_c.h"
35 #include "graphite-ppl.h"
36 #include "graphite-poly.h"
37 #include "graphite-sese-to-poly.h"
38
39 /* Returns the index of the PHI argument defined in the outermost
40 loop. */
41
42 static size_t
phi_arg_in_outermost_loop(gimple phi)43 phi_arg_in_outermost_loop (gimple phi)
44 {
45 loop_p loop = gimple_bb (phi)->loop_father;
46 size_t i, res = 0;
47
48 for (i = 0; i < gimple_phi_num_args (phi); i++)
49 if (!flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, i)->src))
50 {
51 loop = gimple_phi_arg_edge (phi, i)->src->loop_father;
52 res = i;
53 }
54
55 return res;
56 }
57
58 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
59 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
60
61 static void
remove_simple_copy_phi(gimple_stmt_iterator * psi)62 remove_simple_copy_phi (gimple_stmt_iterator *psi)
63 {
64 gimple phi = gsi_stmt (*psi);
65 tree res = gimple_phi_result (phi);
66 size_t entry = phi_arg_in_outermost_loop (phi);
67 tree init = gimple_phi_arg_def (phi, entry);
68 gimple stmt = gimple_build_assign (res, init);
69 edge e = gimple_phi_arg_edge (phi, entry);
70
71 remove_phi_node (psi, false);
72 gsi_insert_on_edge_immediate (e, stmt);
73 SSA_NAME_DEF_STMT (res) = stmt;
74 }
75
76 /* Removes an invariant phi node at position PSI by inserting on the
77 loop ENTRY edge the assignment RES = INIT. */
78
79 static void
remove_invariant_phi(sese region,gimple_stmt_iterator * psi)80 remove_invariant_phi (sese region, gimple_stmt_iterator *psi)
81 {
82 gimple phi = gsi_stmt (*psi);
83 loop_p loop = loop_containing_stmt (phi);
84 tree res = gimple_phi_result (phi);
85 tree scev = scalar_evolution_in_region (region, loop, res);
86 size_t entry = phi_arg_in_outermost_loop (phi);
87 edge e = gimple_phi_arg_edge (phi, entry);
88 tree var;
89 gimple stmt;
90 gimple_seq stmts;
91 gimple_stmt_iterator gsi;
92
93 if (tree_contains_chrecs (scev, NULL))
94 scev = gimple_phi_arg_def (phi, entry);
95
96 var = force_gimple_operand (scev, &stmts, true, NULL_TREE);
97 stmt = gimple_build_assign (res, var);
98 remove_phi_node (psi, false);
99
100 if (!stmts)
101 stmts = gimple_seq_alloc ();
102
103 gsi = gsi_last (stmts);
104 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
105 gsi_insert_seq_on_edge (e, stmts);
106 gsi_commit_edge_inserts ();
107 SSA_NAME_DEF_STMT (res) = stmt;
108 }
109
110 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
111
112 static inline bool
simple_copy_phi_p(gimple phi)113 simple_copy_phi_p (gimple phi)
114 {
115 tree res;
116
117 if (gimple_phi_num_args (phi) != 2)
118 return false;
119
120 res = gimple_phi_result (phi);
121 return (res == gimple_phi_arg_def (phi, 0)
122 || res == gimple_phi_arg_def (phi, 1));
123 }
124
125 /* Returns true when the phi node at position PSI is a reduction phi
126 node in REGION. Otherwise moves the pointer PSI to the next phi to
127 be considered. */
128
129 static bool
reduction_phi_p(sese region,gimple_stmt_iterator * psi)130 reduction_phi_p (sese region, gimple_stmt_iterator *psi)
131 {
132 loop_p loop;
133 gimple phi = gsi_stmt (*psi);
134 tree res = gimple_phi_result (phi);
135
136 loop = loop_containing_stmt (phi);
137
138 if (simple_copy_phi_p (phi))
139 {
140 /* PRE introduces phi nodes like these, for an example,
141 see id-5.f in the fortran graphite testsuite:
142
143 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
144 */
145 remove_simple_copy_phi (psi);
146 return false;
147 }
148
149 if (scev_analyzable_p (res, region))
150 {
151 tree scev = scalar_evolution_in_region (region, loop, res);
152
153 if (evolution_function_is_invariant_p (scev, loop->num))
154 remove_invariant_phi (region, psi);
155 else
156 gsi_next (psi);
157
158 return false;
159 }
160
161 /* All the other cases are considered reductions. */
162 return true;
163 }
164
165 /* Store the GRAPHITE representation of BB. */
166
167 static gimple_bb_p
new_gimple_bb(basic_block bb,VEC (data_reference_p,heap)* drs)168 new_gimple_bb (basic_block bb, VEC (data_reference_p, heap) *drs)
169 {
170 struct gimple_bb *gbb;
171
172 gbb = XNEW (struct gimple_bb);
173 bb->aux = gbb;
174 GBB_BB (gbb) = bb;
175 GBB_DATA_REFS (gbb) = drs;
176 GBB_CONDITIONS (gbb) = NULL;
177 GBB_CONDITION_CASES (gbb) = NULL;
178
179 return gbb;
180 }
181
182 static void
free_data_refs_aux(VEC (data_reference_p,heap)* datarefs)183 free_data_refs_aux (VEC (data_reference_p, heap) *datarefs)
184 {
185 unsigned int i;
186 struct data_reference *dr;
187
188 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
189 if (dr->aux)
190 {
191 base_alias_pair *bap = (base_alias_pair *)(dr->aux);
192
193 free (bap->alias_set);
194
195 free (bap);
196 dr->aux = NULL;
197 }
198 }
199 /* Frees GBB. */
200
201 static void
free_gimple_bb(struct gimple_bb * gbb)202 free_gimple_bb (struct gimple_bb *gbb)
203 {
204 free_data_refs_aux (GBB_DATA_REFS (gbb));
205 free_data_refs (GBB_DATA_REFS (gbb));
206
207 VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
208 VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
209 GBB_BB (gbb)->aux = 0;
210 XDELETE (gbb);
211 }
212
213 /* Deletes all gimple bbs in SCOP. */
214
215 static void
remove_gbbs_in_scop(scop_p scop)216 remove_gbbs_in_scop (scop_p scop)
217 {
218 int i;
219 poly_bb_p pbb;
220
221 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
222 free_gimple_bb (PBB_BLACK_BOX (pbb));
223 }
224
225 /* Deletes all scops in SCOPS. */
226
227 void
free_scops(VEC (scop_p,heap)* scops)228 free_scops (VEC (scop_p, heap) *scops)
229 {
230 int i;
231 scop_p scop;
232
233 FOR_EACH_VEC_ELT (scop_p, scops, i, scop)
234 {
235 remove_gbbs_in_scop (scop);
236 free_sese (SCOP_REGION (scop));
237 free_scop (scop);
238 }
239
240 VEC_free (scop_p, heap, scops);
241 }
242
243 /* Same as outermost_loop_in_sese, returns the outermost loop
244 containing BB in REGION, but makes sure that the returned loop
245 belongs to the REGION, and so this returns the first loop in the
246 REGION when the loop containing BB does not belong to REGION. */
247
248 static loop_p
outermost_loop_in_sese_1(sese region,basic_block bb)249 outermost_loop_in_sese_1 (sese region, basic_block bb)
250 {
251 loop_p nest = outermost_loop_in_sese (region, bb);
252
253 if (loop_in_sese_p (nest, region))
254 return nest;
255
256 /* When the basic block BB does not belong to a loop in the region,
257 return the first loop in the region. */
258 nest = nest->inner;
259 while (nest)
260 if (loop_in_sese_p (nest, region))
261 break;
262 else
263 nest = nest->next;
264
265 gcc_assert (nest);
266 return nest;
267 }
268
269 /* Generates a polyhedral black box only if the bb contains interesting
270 information. */
271
272 static gimple_bb_p
try_generate_gimple_bb(scop_p scop,basic_block bb)273 try_generate_gimple_bb (scop_p scop, basic_block bb)
274 {
275 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
276 sese region = SCOP_REGION (scop);
277 loop_p nest = outermost_loop_in_sese_1 (region, bb);
278 gimple_stmt_iterator gsi;
279
280 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
281 {
282 gimple stmt = gsi_stmt (gsi);
283 loop_p loop;
284
285 if (is_gimple_debug (stmt))
286 continue;
287
288 loop = loop_containing_stmt (stmt);
289 if (!loop_in_sese_p (loop, region))
290 loop = nest;
291
292 graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
293 }
294
295 return new_gimple_bb (bb, drs);
296 }
297
298 /* Returns true if all predecessors of BB, that are not dominated by BB, are
299 marked in MAP. The predecessors dominated by BB are loop latches and will
300 be handled after BB. */
301
302 static bool
all_non_dominated_preds_marked_p(basic_block bb,sbitmap map)303 all_non_dominated_preds_marked_p (basic_block bb, sbitmap map)
304 {
305 edge e;
306 edge_iterator ei;
307
308 FOR_EACH_EDGE (e, ei, bb->preds)
309 if (!TEST_BIT (map, e->src->index)
310 && !dominated_by_p (CDI_DOMINATORS, e->src, bb))
311 return false;
312
313 return true;
314 }
315
316 /* Compare the depth of two basic_block's P1 and P2. */
317
318 static int
compare_bb_depths(const void * p1,const void * p2)319 compare_bb_depths (const void *p1, const void *p2)
320 {
321 const_basic_block const bb1 = *(const_basic_block const*)p1;
322 const_basic_block const bb2 = *(const_basic_block const*)p2;
323 int d1 = loop_depth (bb1->loop_father);
324 int d2 = loop_depth (bb2->loop_father);
325
326 if (d1 < d2)
327 return 1;
328
329 if (d1 > d2)
330 return -1;
331
332 return 0;
333 }
334
335 /* Sort the basic blocks from DOM such that the first are the ones at
336 a deepest loop level. */
337
338 static void
graphite_sort_dominated_info(VEC (basic_block,heap)* dom)339 graphite_sort_dominated_info (VEC (basic_block, heap) *dom)
340 {
341 VEC_qsort (basic_block, dom, compare_bb_depths);
342 }
343
344 /* Recursive helper function for build_scops_bbs. */
345
346 static void
build_scop_bbs_1(scop_p scop,sbitmap visited,basic_block bb)347 build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb)
348 {
349 sese region = SCOP_REGION (scop);
350 VEC (basic_block, heap) *dom;
351 poly_bb_p pbb;
352
353 if (TEST_BIT (visited, bb->index)
354 || !bb_in_sese_p (bb, region))
355 return;
356
357 pbb = new_poly_bb (scop, try_generate_gimple_bb (scop, bb));
358 VEC_safe_push (poly_bb_p, heap, SCOP_BBS (scop), pbb);
359 SET_BIT (visited, bb->index);
360
361 dom = get_dominated_by (CDI_DOMINATORS, bb);
362
363 if (dom == NULL)
364 return;
365
366 graphite_sort_dominated_info (dom);
367
368 while (!VEC_empty (basic_block, dom))
369 {
370 int i;
371 basic_block dom_bb;
372
373 FOR_EACH_VEC_ELT (basic_block, dom, i, dom_bb)
374 if (all_non_dominated_preds_marked_p (dom_bb, visited))
375 {
376 build_scop_bbs_1 (scop, visited, dom_bb);
377 VEC_unordered_remove (basic_block, dom, i);
378 break;
379 }
380 }
381
382 VEC_free (basic_block, heap, dom);
383 }
384
385 /* Gather the basic blocks belonging to the SCOP. */
386
387 static void
build_scop_bbs(scop_p scop)388 build_scop_bbs (scop_p scop)
389 {
390 sbitmap visited = sbitmap_alloc (last_basic_block);
391 sese region = SCOP_REGION (scop);
392
393 sbitmap_zero (visited);
394 build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region));
395 sbitmap_free (visited);
396 }
397
398 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
399 We generate SCATTERING_DIMENSIONS scattering dimensions.
400
401 CLooG 0.15.0 and previous versions require, that all
402 scattering functions of one CloogProgram have the same number of
403 scattering dimensions, therefore we allow to specify it. This
404 should be removed in future versions of CLooG.
405
406 The scattering polyhedron consists of these dimensions: scattering,
407 loop_iterators, parameters.
408
409 Example:
410
411 | scattering_dimensions = 5
412 | used_scattering_dimensions = 3
413 | nb_iterators = 1
414 | scop_nb_params = 2
415 |
416 | Schedule:
417 | i
418 | 4 5
419 |
420 | Scattering polyhedron:
421 |
422 | scattering: {s1, s2, s3, s4, s5}
423 | loop_iterators: {i}
424 | parameters: {p1, p2}
425 |
426 | s1 s2 s3 s4 s5 i p1 p2 1
427 | 1 0 0 0 0 0 0 0 -4 = 0
428 | 0 1 0 0 0 -1 0 0 0 = 0
429 | 0 0 1 0 0 0 0 0 -5 = 0 */
430
431 static void
build_pbb_scattering_polyhedrons(ppl_Linear_Expression_t static_schedule,poly_bb_p pbb,int scattering_dimensions)432 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule,
433 poly_bb_p pbb, int scattering_dimensions)
434 {
435 int i;
436 scop_p scop = PBB_SCOP (pbb);
437 int nb_iterators = pbb_dim_iter_domain (pbb);
438 int used_scattering_dimensions = nb_iterators * 2 + 1;
439 int nb_params = scop_nb_params (scop);
440 ppl_Coefficient_t c;
441 ppl_dimension_type dim = scattering_dimensions + nb_iterators + nb_params;
442 mpz_t v;
443
444 gcc_assert (scattering_dimensions >= used_scattering_dimensions);
445
446 mpz_init (v);
447 ppl_new_Coefficient (&c);
448 PBB_TRANSFORMED (pbb) = poly_scattering_new ();
449 ppl_new_C_Polyhedron_from_space_dimension
450 (&PBB_TRANSFORMED_SCATTERING (pbb), dim, 0);
451
452 PBB_NB_SCATTERING_TRANSFORM (pbb) = scattering_dimensions;
453
454 for (i = 0; i < scattering_dimensions; i++)
455 {
456 ppl_Constraint_t cstr;
457 ppl_Linear_Expression_t expr;
458
459 ppl_new_Linear_Expression_with_dimension (&expr, dim);
460 mpz_set_si (v, 1);
461 ppl_assign_Coefficient_from_mpz_t (c, v);
462 ppl_Linear_Expression_add_to_coefficient (expr, i, c);
463
464 /* Textual order inside this loop. */
465 if ((i % 2) == 0)
466 {
467 ppl_Linear_Expression_coefficient (static_schedule, i / 2, c);
468 ppl_Coefficient_to_mpz_t (c, v);
469 mpz_neg (v, v);
470 ppl_assign_Coefficient_from_mpz_t (c, v);
471 ppl_Linear_Expression_add_to_inhomogeneous (expr, c);
472 }
473
474 /* Iterations of this loop. */
475 else /* if ((i % 2) == 1) */
476 {
477 int loop = (i - 1) / 2;
478
479 mpz_set_si (v, -1);
480 ppl_assign_Coefficient_from_mpz_t (c, v);
481 ppl_Linear_Expression_add_to_coefficient
482 (expr, scattering_dimensions + loop, c);
483 }
484
485 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
486 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
487 ppl_delete_Linear_Expression (expr);
488 ppl_delete_Constraint (cstr);
489 }
490
491 mpz_clear (v);
492 ppl_delete_Coefficient (c);
493
494 PBB_ORIGINAL (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb));
495 }
496
497 /* Build for BB the static schedule.
498
499 The static schedule is a Dewey numbering of the abstract syntax
500 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
501
502 The following example informally defines the static schedule:
503
504 A
505 for (i: ...)
506 {
507 for (j: ...)
508 {
509 B
510 C
511 }
512
513 for (k: ...)
514 {
515 D
516 E
517 }
518 }
519 F
520
521 Static schedules for A to F:
522
523 DEPTH
524 0 1 2
525 A 0
526 B 1 0 0
527 C 1 0 1
528 D 1 1 0
529 E 1 1 1
530 F 2
531 */
532
533 static void
build_scop_scattering(scop_p scop)534 build_scop_scattering (scop_p scop)
535 {
536 int i;
537 poly_bb_p pbb;
538 gimple_bb_p previous_gbb = NULL;
539 ppl_Linear_Expression_t static_schedule;
540 ppl_Coefficient_t c;
541 mpz_t v;
542
543 mpz_init (v);
544 ppl_new_Coefficient (&c);
545 ppl_new_Linear_Expression (&static_schedule);
546
547 /* We have to start schedules at 0 on the first component and
548 because we cannot compare_prefix_loops against a previous loop,
549 prefix will be equal to zero, and that index will be
550 incremented before copying. */
551 mpz_set_si (v, -1);
552 ppl_assign_Coefficient_from_mpz_t (c, v);
553 ppl_Linear_Expression_add_to_coefficient (static_schedule, 0, c);
554
555 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
556 {
557 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
558 ppl_Linear_Expression_t common;
559 int prefix;
560 int nb_scat_dims = pbb_dim_iter_domain (pbb) * 2 + 1;
561
562 if (previous_gbb)
563 prefix = nb_common_loops (SCOP_REGION (scop), previous_gbb, gbb);
564 else
565 prefix = 0;
566
567 previous_gbb = gbb;
568 ppl_new_Linear_Expression_with_dimension (&common, prefix + 1);
569 ppl_assign_Linear_Expression_from_Linear_Expression (common,
570 static_schedule);
571
572 mpz_set_si (v, 1);
573 ppl_assign_Coefficient_from_mpz_t (c, v);
574 ppl_Linear_Expression_add_to_coefficient (common, prefix, c);
575 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule,
576 common);
577
578 build_pbb_scattering_polyhedrons (common, pbb, nb_scat_dims);
579
580 ppl_delete_Linear_Expression (common);
581 }
582
583 mpz_clear (v);
584 ppl_delete_Coefficient (c);
585 ppl_delete_Linear_Expression (static_schedule);
586 }
587
588 /* Add the value K to the dimension D of the linear expression EXPR. */
589
590 static void
add_value_to_dim(ppl_dimension_type d,ppl_Linear_Expression_t expr,mpz_t k)591 add_value_to_dim (ppl_dimension_type d, ppl_Linear_Expression_t expr,
592 mpz_t k)
593 {
594 mpz_t val;
595 ppl_Coefficient_t coef;
596
597 ppl_new_Coefficient (&coef);
598 ppl_Linear_Expression_coefficient (expr, d, coef);
599 mpz_init (val);
600 ppl_Coefficient_to_mpz_t (coef, val);
601
602 mpz_add (val, val, k);
603
604 ppl_assign_Coefficient_from_mpz_t (coef, val);
605 ppl_Linear_Expression_add_to_coefficient (expr, d, coef);
606 mpz_clear (val);
607 ppl_delete_Coefficient (coef);
608 }
609
610 /* In the context of scop S, scan E, the right hand side of a scalar
611 evolution function in loop VAR, and translate it to a linear
612 expression EXPR. */
613
614 static void
scan_tree_for_params_right_scev(sese s,tree e,int var,ppl_Linear_Expression_t expr)615 scan_tree_for_params_right_scev (sese s, tree e, int var,
616 ppl_Linear_Expression_t expr)
617 {
618 if (expr)
619 {
620 loop_p loop = get_loop (var);
621 ppl_dimension_type l = sese_loop_depth (s, loop) - 1;
622 mpz_t val;
623
624 /* Scalar evolutions should happen in the sese region. */
625 gcc_assert (sese_loop_depth (s, loop) > 0);
626
627 /* We can not deal with parametric strides like:
628
629 | p = parameter;
630 |
631 | for i:
632 | a [i * p] = ... */
633 gcc_assert (TREE_CODE (e) == INTEGER_CST);
634
635 mpz_init (val);
636 tree_int_to_gmp (e, val);
637 add_value_to_dim (l, expr, val);
638 mpz_clear (val);
639 }
640 }
641
642 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
643 linear expression EXPR. K is the multiplier of the constant. */
644
645 static void
scan_tree_for_params_int(tree cst,ppl_Linear_Expression_t expr,mpz_t k)646 scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, mpz_t k)
647 {
648 mpz_t val;
649 ppl_Coefficient_t coef;
650 tree type = TREE_TYPE (cst);
651
652 mpz_init (val);
653
654 /* Necessary to not get "-1 = 2^n - 1". */
655 mpz_set_double_int (val, double_int_sext (tree_to_double_int (cst),
656 TYPE_PRECISION (type)), false);
657
658 mpz_mul (val, val, k);
659 ppl_new_Coefficient (&coef);
660 ppl_assign_Coefficient_from_mpz_t (coef, val);
661 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
662 mpz_clear (val);
663 ppl_delete_Coefficient (coef);
664 }
665
666 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
667 Otherwise returns -1. */
668
669 static inline int
parameter_index_in_region_1(tree name,sese region)670 parameter_index_in_region_1 (tree name, sese region)
671 {
672 int i;
673 tree p;
674
675 gcc_assert (TREE_CODE (name) == SSA_NAME);
676
677 FOR_EACH_VEC_ELT (tree, SESE_PARAMS (region), i, p)
678 if (p == name)
679 return i;
680
681 return -1;
682 }
683
684 /* When the parameter NAME is in REGION, returns its index in
685 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
686 and returns the index of NAME. */
687
688 static int
parameter_index_in_region(tree name,sese region)689 parameter_index_in_region (tree name, sese region)
690 {
691 int i;
692
693 gcc_assert (TREE_CODE (name) == SSA_NAME);
694
695 i = parameter_index_in_region_1 (name, region);
696 if (i != -1)
697 return i;
698
699 gcc_assert (SESE_ADD_PARAMS (region));
700
701 i = VEC_length (tree, SESE_PARAMS (region));
702 VEC_safe_push (tree, heap, SESE_PARAMS (region), name);
703 return i;
704 }
705
706 /* In the context of sese S, scan the expression E and translate it to
707 a linear expression C. When parsing a symbolic multiplication, K
708 represents the constant multiplier of an expression containing
709 parameters. */
710
711 static void
scan_tree_for_params(sese s,tree e,ppl_Linear_Expression_t c,mpz_t k)712 scan_tree_for_params (sese s, tree e, ppl_Linear_Expression_t c,
713 mpz_t k)
714 {
715 if (e == chrec_dont_know)
716 return;
717
718 switch (TREE_CODE (e))
719 {
720 case POLYNOMIAL_CHREC:
721 scan_tree_for_params_right_scev (s, CHREC_RIGHT (e),
722 CHREC_VARIABLE (e), c);
723 scan_tree_for_params (s, CHREC_LEFT (e), c, k);
724 break;
725
726 case MULT_EXPR:
727 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
728 {
729 if (c)
730 {
731 mpz_t val;
732 gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
733 mpz_init (val);
734 tree_int_to_gmp (TREE_OPERAND (e, 1), val);
735 mpz_mul (val, val, k);
736 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, val);
737 mpz_clear (val);
738 }
739 else
740 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
741 }
742 else
743 {
744 if (c)
745 {
746 mpz_t val;
747 gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
748 mpz_init (val);
749 tree_int_to_gmp (TREE_OPERAND (e, 0), val);
750 mpz_mul (val, val, k);
751 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, val);
752 mpz_clear (val);
753 }
754 else
755 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
756 }
757 break;
758
759 case PLUS_EXPR:
760 case POINTER_PLUS_EXPR:
761 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
762 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
763 break;
764
765 case MINUS_EXPR:
766 {
767 ppl_Linear_Expression_t tmp_expr = NULL;
768
769 if (c)
770 {
771 ppl_dimension_type dim;
772 ppl_Linear_Expression_space_dimension (c, &dim);
773 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
774 }
775
776 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
777 scan_tree_for_params (s, TREE_OPERAND (e, 1), tmp_expr, k);
778
779 if (c)
780 {
781 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
782 tmp_expr);
783 ppl_delete_Linear_Expression (tmp_expr);
784 }
785
786 break;
787 }
788
789 case NEGATE_EXPR:
790 {
791 ppl_Linear_Expression_t tmp_expr = NULL;
792
793 if (c)
794 {
795 ppl_dimension_type dim;
796 ppl_Linear_Expression_space_dimension (c, &dim);
797 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
798 }
799
800 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
801
802 if (c)
803 {
804 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
805 tmp_expr);
806 ppl_delete_Linear_Expression (tmp_expr);
807 }
808
809 break;
810 }
811
812 case BIT_NOT_EXPR:
813 {
814 ppl_Linear_Expression_t tmp_expr = NULL;
815
816 if (c)
817 {
818 ppl_dimension_type dim;
819 ppl_Linear_Expression_space_dimension (c, &dim);
820 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
821 }
822
823 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
824
825 if (c)
826 {
827 ppl_Coefficient_t coef;
828 mpz_t minus_one;
829
830 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
831 tmp_expr);
832 ppl_delete_Linear_Expression (tmp_expr);
833 mpz_init (minus_one);
834 mpz_set_si (minus_one, -1);
835 ppl_new_Coefficient_from_mpz_t (&coef, minus_one);
836 ppl_Linear_Expression_add_to_inhomogeneous (c, coef);
837 mpz_clear (minus_one);
838 ppl_delete_Coefficient (coef);
839 }
840
841 break;
842 }
843
844 case SSA_NAME:
845 {
846 ppl_dimension_type p = parameter_index_in_region (e, s);
847
848 if (c)
849 {
850 ppl_dimension_type dim;
851 ppl_Linear_Expression_space_dimension (c, &dim);
852 p += dim - sese_nb_params (s);
853 add_value_to_dim (p, c, k);
854 }
855 break;
856 }
857
858 case INTEGER_CST:
859 if (c)
860 scan_tree_for_params_int (e, c, k);
861 break;
862
863 CASE_CONVERT:
864 case NON_LVALUE_EXPR:
865 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
866 break;
867
868 case ADDR_EXPR:
869 break;
870
871 default:
872 gcc_unreachable ();
873 break;
874 }
875 }
876
877 /* Find parameters with respect to REGION in BB. We are looking in memory
878 access functions, conditions and loop bounds. */
879
880 static void
find_params_in_bb(sese region,gimple_bb_p gbb)881 find_params_in_bb (sese region, gimple_bb_p gbb)
882 {
883 int i;
884 unsigned j;
885 data_reference_p dr;
886 gimple stmt;
887 loop_p loop = GBB_BB (gbb)->loop_father;
888 mpz_t one;
889
890 mpz_init (one);
891 mpz_set_si (one, 1);
892
893 /* Find parameters in the access functions of data references. */
894 FOR_EACH_VEC_ELT (data_reference_p, GBB_DATA_REFS (gbb), i, dr)
895 for (j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
896 scan_tree_for_params (region, DR_ACCESS_FN (dr, j), NULL, one);
897
898 /* Find parameters in conditional statements. */
899 FOR_EACH_VEC_ELT (gimple, GBB_CONDITIONS (gbb), i, stmt)
900 {
901 tree lhs = scalar_evolution_in_region (region, loop,
902 gimple_cond_lhs (stmt));
903 tree rhs = scalar_evolution_in_region (region, loop,
904 gimple_cond_rhs (stmt));
905
906 scan_tree_for_params (region, lhs, NULL, one);
907 scan_tree_for_params (region, rhs, NULL, one);
908 }
909
910 mpz_clear (one);
911 }
912
913 /* Record the parameters used in the SCOP. A variable is a parameter
914 in a scop if it does not vary during the execution of that scop. */
915
916 static void
find_scop_parameters(scop_p scop)917 find_scop_parameters (scop_p scop)
918 {
919 poly_bb_p pbb;
920 unsigned i;
921 sese region = SCOP_REGION (scop);
922 struct loop *loop;
923 mpz_t one;
924
925 mpz_init (one);
926 mpz_set_si (one, 1);
927
928 /* Find the parameters used in the loop bounds. */
929 FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop)
930 {
931 tree nb_iters = number_of_latch_executions (loop);
932
933 if (!chrec_contains_symbols (nb_iters))
934 continue;
935
936 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
937 scan_tree_for_params (region, nb_iters, NULL, one);
938 }
939
940 mpz_clear (one);
941
942 /* Find the parameters used in data accesses. */
943 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
944 find_params_in_bb (region, PBB_BLACK_BOX (pbb));
945
946 scop_set_nb_params (scop, sese_nb_params (region));
947 SESE_ADD_PARAMS (region) = false;
948
949 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
950 (&SCOP_CONTEXT (scop), scop_nb_params (scop), 0);
951 }
952
953 /* Insert in the SCOP context constraints from the estimation of the
954 number of iterations. UB_EXPR is a linear expression describing
955 the number of iterations in a loop. This expression is bounded by
956 the estimation NIT. */
957
958 static void
add_upper_bounds_from_estimated_nit(scop_p scop,double_int nit,ppl_dimension_type dim,ppl_Linear_Expression_t ub_expr)959 add_upper_bounds_from_estimated_nit (scop_p scop, double_int nit,
960 ppl_dimension_type dim,
961 ppl_Linear_Expression_t ub_expr)
962 {
963 mpz_t val;
964 ppl_Linear_Expression_t nb_iters_le;
965 ppl_Polyhedron_t pol;
966 ppl_Coefficient_t coef;
967 ppl_Constraint_t ub;
968
969 ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0);
970 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le,
971 ub_expr);
972
973 /* Construct the negated number of last iteration in VAL. */
974 mpz_init (val);
975 mpz_set_double_int (val, nit, false);
976 mpz_sub_ui (val, val, 1);
977 mpz_neg (val, val);
978
979 /* NB_ITERS_LE holds the number of last iteration in
980 parametrical form. Subtract estimated number of last
981 iteration and assert that result is not positive. */
982 ppl_new_Coefficient_from_mpz_t (&coef, val);
983 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le, coef);
984 ppl_delete_Coefficient (coef);
985 ppl_new_Constraint (&ub, nb_iters_le,
986 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
987 ppl_Polyhedron_add_constraint (pol, ub);
988
989 /* Remove all but last GDIM dimensions from POL to obtain
990 only the constraints on the parameters. */
991 {
992 graphite_dim_t gdim = scop_nb_params (scop);
993 ppl_dimension_type *dims = XNEWVEC (ppl_dimension_type, dim - gdim);
994 graphite_dim_t i;
995
996 for (i = 0; i < dim - gdim; i++)
997 dims[i] = i;
998
999 ppl_Polyhedron_remove_space_dimensions (pol, dims, dim - gdim);
1000 XDELETEVEC (dims);
1001 }
1002
1003 /* Add the constraints on the parameters to the SCoP context. */
1004 {
1005 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps;
1006
1007 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1008 (&constraints_ps, pol);
1009 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1010 (SCOP_CONTEXT (scop), constraints_ps);
1011 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps);
1012 }
1013
1014 ppl_delete_Polyhedron (pol);
1015 ppl_delete_Linear_Expression (nb_iters_le);
1016 ppl_delete_Constraint (ub);
1017 mpz_clear (val);
1018 }
1019
1020 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1021 the constraints for the surrounding loops. */
1022
1023 static void
build_loop_iteration_domains(scop_p scop,struct loop * loop,ppl_Polyhedron_t outer_ph,int nb,ppl_Pointset_Powerset_C_Polyhedron_t * domains)1024 build_loop_iteration_domains (scop_p scop, struct loop *loop,
1025 ppl_Polyhedron_t outer_ph, int nb,
1026 ppl_Pointset_Powerset_C_Polyhedron_t *domains)
1027 {
1028 int i;
1029 ppl_Polyhedron_t ph;
1030 tree nb_iters = number_of_latch_executions (loop);
1031 ppl_dimension_type dim = nb + 1 + scop_nb_params (scop);
1032 sese region = SCOP_REGION (scop);
1033
1034 {
1035 ppl_const_Constraint_System_t pcs;
1036 ppl_dimension_type *map
1037 = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
1038
1039 ppl_new_C_Polyhedron_from_space_dimension (&ph, dim, 0);
1040 ppl_Polyhedron_get_constraints (outer_ph, &pcs);
1041 ppl_Polyhedron_add_constraints (ph, pcs);
1042
1043 for (i = 0; i < (int) nb; i++)
1044 map[i] = i;
1045 for (i = (int) nb; i < (int) dim - 1; i++)
1046 map[i] = i + 1;
1047 map[dim - 1] = nb;
1048
1049 ppl_Polyhedron_map_space_dimensions (ph, map, dim);
1050 free (map);
1051 }
1052
1053 /* 0 <= loop_i */
1054 {
1055 ppl_Constraint_t lb;
1056 ppl_Linear_Expression_t lb_expr;
1057
1058 ppl_new_Linear_Expression_with_dimension (&lb_expr, dim);
1059 ppl_set_coef (lb_expr, nb, 1);
1060 ppl_new_Constraint (&lb, lb_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1061 ppl_delete_Linear_Expression (lb_expr);
1062 ppl_Polyhedron_add_constraint (ph, lb);
1063 ppl_delete_Constraint (lb);
1064 }
1065
1066 if (TREE_CODE (nb_iters) == INTEGER_CST)
1067 {
1068 ppl_Constraint_t ub;
1069 ppl_Linear_Expression_t ub_expr;
1070
1071 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1072
1073 /* loop_i <= cst_nb_iters */
1074 ppl_set_coef (ub_expr, nb, -1);
1075 ppl_set_inhomogeneous_tree (ub_expr, nb_iters);
1076 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1077 ppl_Polyhedron_add_constraint (ph, ub);
1078 ppl_delete_Linear_Expression (ub_expr);
1079 ppl_delete_Constraint (ub);
1080 }
1081 else if (!chrec_contains_undetermined (nb_iters))
1082 {
1083 mpz_t one;
1084 ppl_Constraint_t ub;
1085 ppl_Linear_Expression_t ub_expr;
1086 double_int nit;
1087
1088 mpz_init (one);
1089 mpz_set_si (one, 1);
1090 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1091 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1092 scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one);
1093 mpz_clear (one);
1094
1095 if (max_stmt_executions (loop, true, &nit))
1096 add_upper_bounds_from_estimated_nit (scop, nit, dim, ub_expr);
1097
1098 /* loop_i <= expr_nb_iters */
1099 ppl_set_coef (ub_expr, nb, -1);
1100 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1101 ppl_Polyhedron_add_constraint (ph, ub);
1102 ppl_delete_Linear_Expression (ub_expr);
1103 ppl_delete_Constraint (ub);
1104 }
1105 else
1106 gcc_unreachable ();
1107
1108 if (loop->inner && loop_in_sese_p (loop->inner, region))
1109 build_loop_iteration_domains (scop, loop->inner, ph, nb + 1, domains);
1110
1111 if (nb != 0
1112 && loop->next
1113 && loop_in_sese_p (loop->next, region))
1114 build_loop_iteration_domains (scop, loop->next, outer_ph, nb, domains);
1115
1116 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1117 (&domains[loop->num], ph);
1118
1119 ppl_delete_Polyhedron (ph);
1120 }
1121
1122 /* Returns a linear expression for tree T evaluated in PBB. */
1123
1124 static ppl_Linear_Expression_t
create_linear_expr_from_tree(poly_bb_p pbb,tree t)1125 create_linear_expr_from_tree (poly_bb_p pbb, tree t)
1126 {
1127 mpz_t one;
1128 ppl_Linear_Expression_t res;
1129 ppl_dimension_type dim;
1130 sese region = SCOP_REGION (PBB_SCOP (pbb));
1131 loop_p loop = pbb_loop (pbb);
1132
1133 dim = pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
1134 ppl_new_Linear_Expression_with_dimension (&res, dim);
1135
1136 t = scalar_evolution_in_region (region, loop, t);
1137 gcc_assert (!automatically_generated_chrec_p (t));
1138
1139 mpz_init (one);
1140 mpz_set_si (one, 1);
1141 scan_tree_for_params (region, t, res, one);
1142 mpz_clear (one);
1143
1144 return res;
1145 }
1146
1147 /* Returns the ppl constraint type from the gimple tree code CODE. */
1148
1149 static enum ppl_enum_Constraint_Type
ppl_constraint_type_from_tree_code(enum tree_code code)1150 ppl_constraint_type_from_tree_code (enum tree_code code)
1151 {
1152 switch (code)
1153 {
1154 /* We do not support LT and GT to be able to work with C_Polyhedron.
1155 As we work on integer polyhedron "a < b" can be expressed by
1156 "a + 1 <= b". */
1157 case LT_EXPR:
1158 case GT_EXPR:
1159 gcc_unreachable ();
1160
1161 case LE_EXPR:
1162 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL;
1163
1164 case GE_EXPR:
1165 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL;
1166
1167 case EQ_EXPR:
1168 return PPL_CONSTRAINT_TYPE_EQUAL;
1169
1170 default:
1171 gcc_unreachable ();
1172 }
1173 }
1174
1175 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1176 CODE is used as the comparison operator. This allows us to invert the
1177 condition or to handle inequalities. */
1178
1179 static void
add_condition_to_domain(ppl_Pointset_Powerset_C_Polyhedron_t ps,gimple stmt,poly_bb_p pbb,enum tree_code code)1180 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps, gimple stmt,
1181 poly_bb_p pbb, enum tree_code code)
1182 {
1183 mpz_t v;
1184 ppl_Coefficient_t c;
1185 ppl_Linear_Expression_t left, right;
1186 ppl_Constraint_t cstr;
1187 enum ppl_enum_Constraint_Type type;
1188
1189 left = create_linear_expr_from_tree (pbb, gimple_cond_lhs (stmt));
1190 right = create_linear_expr_from_tree (pbb, gimple_cond_rhs (stmt));
1191
1192 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1193 the left or the right side of the expression. */
1194 if (code == LT_EXPR)
1195 {
1196 mpz_init (v);
1197 mpz_set_si (v, 1);
1198 ppl_new_Coefficient (&c);
1199 ppl_assign_Coefficient_from_mpz_t (c, v);
1200 ppl_Linear_Expression_add_to_inhomogeneous (left, c);
1201 ppl_delete_Coefficient (c);
1202 mpz_clear (v);
1203
1204 code = LE_EXPR;
1205 }
1206 else if (code == GT_EXPR)
1207 {
1208 mpz_init (v);
1209 mpz_set_si (v, 1);
1210 ppl_new_Coefficient (&c);
1211 ppl_assign_Coefficient_from_mpz_t (c, v);
1212 ppl_Linear_Expression_add_to_inhomogeneous (right, c);
1213 ppl_delete_Coefficient (c);
1214 mpz_clear (v);
1215
1216 code = GE_EXPR;
1217 }
1218
1219 type = ppl_constraint_type_from_tree_code (code);
1220
1221 ppl_subtract_Linear_Expression_from_Linear_Expression (left, right);
1222
1223 ppl_new_Constraint (&cstr, left, type);
1224 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps, cstr);
1225
1226 ppl_delete_Constraint (cstr);
1227 ppl_delete_Linear_Expression (left);
1228 ppl_delete_Linear_Expression (right);
1229 }
1230
1231 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1232 operator. This allows us to invert the condition or to handle
1233 inequalities. */
1234
1235 static void
add_condition_to_pbb(poly_bb_p pbb,gimple stmt,enum tree_code code)1236 add_condition_to_pbb (poly_bb_p pbb, gimple stmt, enum tree_code code)
1237 {
1238 if (code == NE_EXPR)
1239 {
1240 ppl_Pointset_Powerset_C_Polyhedron_t left = PBB_DOMAIN (pbb);
1241 ppl_Pointset_Powerset_C_Polyhedron_t right;
1242 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1243 (&right, left);
1244 add_condition_to_domain (left, stmt, pbb, LT_EXPR);
1245 add_condition_to_domain (right, stmt, pbb, GT_EXPR);
1246 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left, right);
1247 ppl_delete_Pointset_Powerset_C_Polyhedron (right);
1248 }
1249 else
1250 add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code);
1251 }
1252
1253 /* Add conditions to the domain of PBB. */
1254
1255 static void
add_conditions_to_domain(poly_bb_p pbb)1256 add_conditions_to_domain (poly_bb_p pbb)
1257 {
1258 unsigned int i;
1259 gimple stmt;
1260 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1261
1262 if (VEC_empty (gimple, GBB_CONDITIONS (gbb)))
1263 return;
1264
1265 FOR_EACH_VEC_ELT (gimple, GBB_CONDITIONS (gbb), i, stmt)
1266 switch (gimple_code (stmt))
1267 {
1268 case GIMPLE_COND:
1269 {
1270 enum tree_code code = gimple_cond_code (stmt);
1271
1272 /* The conditions for ELSE-branches are inverted. */
1273 if (!VEC_index (gimple, GBB_CONDITION_CASES (gbb), i))
1274 code = invert_tree_comparison (code, false);
1275
1276 add_condition_to_pbb (pbb, stmt, code);
1277 break;
1278 }
1279
1280 case GIMPLE_SWITCH:
1281 /* Switch statements are not supported right now - fall throught. */
1282
1283 default:
1284 gcc_unreachable ();
1285 break;
1286 }
1287 }
1288
1289 /* Traverses all the GBBs of the SCOP and add their constraints to the
1290 iteration domains. */
1291
1292 static void
add_conditions_to_constraints(scop_p scop)1293 add_conditions_to_constraints (scop_p scop)
1294 {
1295 int i;
1296 poly_bb_p pbb;
1297
1298 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1299 add_conditions_to_domain (pbb);
1300 }
1301
1302 /* Structure used to pass data to dom_walk. */
1303
1304 struct bsc
1305 {
1306 VEC (gimple, heap) **conditions, **cases;
1307 sese region;
1308 };
1309
1310 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1311 edge between BB and its predecessor is not a loop exit edge, and
1312 the last statement of the single predecessor is a COND_EXPR. */
1313
1314 static gimple
single_pred_cond_non_loop_exit(basic_block bb)1315 single_pred_cond_non_loop_exit (basic_block bb)
1316 {
1317 if (single_pred_p (bb))
1318 {
1319 edge e = single_pred_edge (bb);
1320 basic_block pred = e->src;
1321 gimple stmt;
1322
1323 if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
1324 return NULL;
1325
1326 stmt = last_stmt (pred);
1327
1328 if (stmt && gimple_code (stmt) == GIMPLE_COND)
1329 return stmt;
1330 }
1331
1332 return NULL;
1333 }
1334
1335 /* Call-back for dom_walk executed before visiting the dominated
1336 blocks. */
1337
1338 static void
build_sese_conditions_before(struct dom_walk_data * dw_data,basic_block bb)1339 build_sese_conditions_before (struct dom_walk_data *dw_data,
1340 basic_block bb)
1341 {
1342 struct bsc *data = (struct bsc *) dw_data->global_data;
1343 VEC (gimple, heap) **conditions = data->conditions;
1344 VEC (gimple, heap) **cases = data->cases;
1345 gimple_bb_p gbb;
1346 gimple stmt;
1347
1348 if (!bb_in_sese_p (bb, data->region))
1349 return;
1350
1351 stmt = single_pred_cond_non_loop_exit (bb);
1352
1353 if (stmt)
1354 {
1355 edge e = single_pred_edge (bb);
1356
1357 VEC_safe_push (gimple, heap, *conditions, stmt);
1358
1359 if (e->flags & EDGE_TRUE_VALUE)
1360 VEC_safe_push (gimple, heap, *cases, stmt);
1361 else
1362 VEC_safe_push (gimple, heap, *cases, NULL);
1363 }
1364
1365 gbb = gbb_from_bb (bb);
1366
1367 if (gbb)
1368 {
1369 GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
1370 GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
1371 }
1372 }
1373
1374 /* Call-back for dom_walk executed after visiting the dominated
1375 blocks. */
1376
1377 static void
build_sese_conditions_after(struct dom_walk_data * dw_data,basic_block bb)1378 build_sese_conditions_after (struct dom_walk_data *dw_data,
1379 basic_block bb)
1380 {
1381 struct bsc *data = (struct bsc *) dw_data->global_data;
1382 VEC (gimple, heap) **conditions = data->conditions;
1383 VEC (gimple, heap) **cases = data->cases;
1384
1385 if (!bb_in_sese_p (bb, data->region))
1386 return;
1387
1388 if (single_pred_cond_non_loop_exit (bb))
1389 {
1390 VEC_pop (gimple, *conditions);
1391 VEC_pop (gimple, *cases);
1392 }
1393 }
1394
1395 /* Record all conditions in REGION. */
1396
1397 static void
build_sese_conditions(sese region)1398 build_sese_conditions (sese region)
1399 {
1400 struct dom_walk_data walk_data;
1401 VEC (gimple, heap) *conditions = VEC_alloc (gimple, heap, 3);
1402 VEC (gimple, heap) *cases = VEC_alloc (gimple, heap, 3);
1403 struct bsc data;
1404
1405 data.conditions = &conditions;
1406 data.cases = &cases;
1407 data.region = region;
1408
1409 walk_data.dom_direction = CDI_DOMINATORS;
1410 walk_data.initialize_block_local_data = NULL;
1411 walk_data.before_dom_children = build_sese_conditions_before;
1412 walk_data.after_dom_children = build_sese_conditions_after;
1413 walk_data.global_data = &data;
1414 walk_data.block_local_data_size = 0;
1415
1416 init_walk_dominator_tree (&walk_data);
1417 walk_dominator_tree (&walk_data, SESE_ENTRY_BB (region));
1418 fini_walk_dominator_tree (&walk_data);
1419
1420 VEC_free (gimple, heap, conditions);
1421 VEC_free (gimple, heap, cases);
1422 }
1423
1424 /* Add constraints on the possible values of parameter P from the type
1425 of P. */
1426
1427 static void
add_param_constraints(scop_p scop,ppl_Polyhedron_t context,graphite_dim_t p)1428 add_param_constraints (scop_p scop, ppl_Polyhedron_t context, graphite_dim_t p)
1429 {
1430 ppl_Constraint_t cstr;
1431 ppl_Linear_Expression_t le;
1432 tree parameter = VEC_index (tree, SESE_PARAMS (SCOP_REGION (scop)), p);
1433 tree type = TREE_TYPE (parameter);
1434 tree lb = NULL_TREE;
1435 tree ub = NULL_TREE;
1436
1437 if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
1438 lb = lower_bound_in_type (type, type);
1439 else
1440 lb = TYPE_MIN_VALUE (type);
1441
1442 if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
1443 ub = upper_bound_in_type (type, type);
1444 else
1445 ub = TYPE_MAX_VALUE (type);
1446
1447 if (lb)
1448 {
1449 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1450 ppl_set_coef (le, p, -1);
1451 ppl_set_inhomogeneous_tree (le, lb);
1452 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1453 ppl_Polyhedron_add_constraint (context, cstr);
1454 ppl_delete_Linear_Expression (le);
1455 ppl_delete_Constraint (cstr);
1456 }
1457
1458 if (ub)
1459 {
1460 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1461 ppl_set_coef (le, p, -1);
1462 ppl_set_inhomogeneous_tree (le, ub);
1463 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1464 ppl_Polyhedron_add_constraint (context, cstr);
1465 ppl_delete_Linear_Expression (le);
1466 ppl_delete_Constraint (cstr);
1467 }
1468 }
1469
1470 /* Build the context of the SCOP. The context usually contains extra
1471 constraints that are added to the iteration domains that constrain
1472 some parameters. */
1473
1474 static void
build_scop_context(scop_p scop)1475 build_scop_context (scop_p scop)
1476 {
1477 ppl_Polyhedron_t context;
1478 ppl_Pointset_Powerset_C_Polyhedron_t ps;
1479 graphite_dim_t p, n = scop_nb_params (scop);
1480
1481 ppl_new_C_Polyhedron_from_space_dimension (&context, n, 0);
1482
1483 for (p = 0; p < n; p++)
1484 add_param_constraints (scop, context, p);
1485
1486 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1487 (&ps, context);
1488 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1489 (SCOP_CONTEXT (scop), ps);
1490
1491 ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
1492 ppl_delete_Polyhedron (context);
1493 }
1494
1495 /* Build the iteration domains: the loops belonging to the current
1496 SCOP, and that vary for the execution of the current basic block.
1497 Returns false if there is no loop in SCOP. */
1498
1499 static void
build_scop_iteration_domain(scop_p scop)1500 build_scop_iteration_domain (scop_p scop)
1501 {
1502 struct loop *loop;
1503 sese region = SCOP_REGION (scop);
1504 int i;
1505 ppl_Polyhedron_t ph;
1506 poly_bb_p pbb;
1507 int nb_loops = number_of_loops ();
1508 ppl_Pointset_Powerset_C_Polyhedron_t *domains
1509 = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t, nb_loops);
1510
1511 for (i = 0; i < nb_loops; i++)
1512 domains[i] = NULL;
1513
1514 ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0);
1515
1516 FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop)
1517 if (!loop_in_sese_p (loop_outer (loop), region))
1518 build_loop_iteration_domains (scop, loop, ph, 0, domains);
1519
1520 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1521 if (domains[gbb_loop (PBB_BLACK_BOX (pbb))->num])
1522 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1523 (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t)
1524 domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]);
1525 else
1526 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1527 (&PBB_DOMAIN (pbb), ph);
1528
1529 for (i = 0; i < nb_loops; i++)
1530 if (domains[i])
1531 ppl_delete_Pointset_Powerset_C_Polyhedron (domains[i]);
1532
1533 ppl_delete_Polyhedron (ph);
1534 free (domains);
1535 }
1536
1537 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1538 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1539 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1540 domain. */
1541
1542 static void
pdr_add_alias_set(ppl_Polyhedron_t accesses,data_reference_p dr,ppl_dimension_type accessp_nb_dims,ppl_dimension_type dom_nb_dims)1543 pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr,
1544 ppl_dimension_type accessp_nb_dims,
1545 ppl_dimension_type dom_nb_dims)
1546 {
1547 ppl_Linear_Expression_t alias;
1548 ppl_Constraint_t cstr;
1549 int alias_set_num = 0;
1550 base_alias_pair *bap = (base_alias_pair *)(dr->aux);
1551
1552 if (bap && bap->alias_set)
1553 alias_set_num = *(bap->alias_set);
1554
1555 ppl_new_Linear_Expression_with_dimension (&alias, accessp_nb_dims);
1556
1557 ppl_set_coef (alias, dom_nb_dims, 1);
1558 ppl_set_inhomogeneous (alias, -alias_set_num);
1559 ppl_new_Constraint (&cstr, alias, PPL_CONSTRAINT_TYPE_EQUAL);
1560 ppl_Polyhedron_add_constraint (accesses, cstr);
1561
1562 ppl_delete_Linear_Expression (alias);
1563 ppl_delete_Constraint (cstr);
1564 }
1565
1566 /* Add to ACCESSES polyhedron equalities defining the access functions
1567 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1568 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1569 PBB is the poly_bb_p that contains the data reference DR. */
1570
1571 static void
pdr_add_memory_accesses(ppl_Polyhedron_t accesses,data_reference_p dr,ppl_dimension_type accessp_nb_dims,ppl_dimension_type dom_nb_dims,poly_bb_p pbb)1572 pdr_add_memory_accesses (ppl_Polyhedron_t accesses, data_reference_p dr,
1573 ppl_dimension_type accessp_nb_dims,
1574 ppl_dimension_type dom_nb_dims,
1575 poly_bb_p pbb)
1576 {
1577 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1578 mpz_t v;
1579 scop_p scop = PBB_SCOP (pbb);
1580 sese region = SCOP_REGION (scop);
1581
1582 mpz_init (v);
1583
1584 for (i = 0; i < nb_subscripts; i++)
1585 {
1586 ppl_Linear_Expression_t fn, access;
1587 ppl_Constraint_t cstr;
1588 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1589 tree afn = DR_ACCESS_FN (dr, nb_subscripts - 1 - i);
1590
1591 ppl_new_Linear_Expression_with_dimension (&fn, dom_nb_dims);
1592 ppl_new_Linear_Expression_with_dimension (&access, accessp_nb_dims);
1593
1594 mpz_set_si (v, 1);
1595 scan_tree_for_params (region, afn, fn, v);
1596 ppl_assign_Linear_Expression_from_Linear_Expression (access, fn);
1597
1598 ppl_set_coef (access, subscript, -1);
1599 ppl_new_Constraint (&cstr, access, PPL_CONSTRAINT_TYPE_EQUAL);
1600 ppl_Polyhedron_add_constraint (accesses, cstr);
1601
1602 ppl_delete_Linear_Expression (fn);
1603 ppl_delete_Linear_Expression (access);
1604 ppl_delete_Constraint (cstr);
1605 }
1606
1607 mpz_clear (v);
1608 }
1609
1610 /* Add constrains representing the size of the accessed data to the
1611 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1612 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1613 domain. */
1614
1615 static void
pdr_add_data_dimensions(ppl_Polyhedron_t accesses,data_reference_p dr,ppl_dimension_type accessp_nb_dims,ppl_dimension_type dom_nb_dims)1616 pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr,
1617 ppl_dimension_type accessp_nb_dims,
1618 ppl_dimension_type dom_nb_dims)
1619 {
1620 tree ref = DR_REF (dr);
1621 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1622
1623 for (i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
1624 {
1625 ppl_Linear_Expression_t expr;
1626 ppl_Constraint_t cstr;
1627 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1628 tree low, high;
1629
1630 if (TREE_CODE (ref) != ARRAY_REF)
1631 break;
1632
1633 low = array_ref_low_bound (ref);
1634
1635 /* subscript - low >= 0 */
1636 if (host_integerp (low, 0))
1637 {
1638 tree minus_low;
1639
1640 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1641 ppl_set_coef (expr, subscript, 1);
1642
1643 minus_low = fold_build1 (NEGATE_EXPR, TREE_TYPE (low), low);
1644 ppl_set_inhomogeneous_tree (expr, minus_low);
1645
1646 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1647 ppl_Polyhedron_add_constraint (accesses, cstr);
1648 ppl_delete_Linear_Expression (expr);
1649 ppl_delete_Constraint (cstr);
1650 }
1651
1652 high = array_ref_up_bound (ref);
1653
1654 /* high - subscript >= 0 */
1655 if (high && host_integerp (high, 0)
1656 /* 1-element arrays at end of structures may extend over
1657 their declared size. */
1658 && !(array_at_struct_end_p (ref)
1659 && operand_equal_p (low, high, 0)))
1660 {
1661 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1662 ppl_set_coef (expr, subscript, -1);
1663
1664 ppl_set_inhomogeneous_tree (expr, high);
1665
1666 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1667 ppl_Polyhedron_add_constraint (accesses, cstr);
1668 ppl_delete_Linear_Expression (expr);
1669 ppl_delete_Constraint (cstr);
1670 }
1671 }
1672 }
1673
1674 /* Build data accesses for DR in PBB. */
1675
1676 static void
build_poly_dr(data_reference_p dr,poly_bb_p pbb)1677 build_poly_dr (data_reference_p dr, poly_bb_p pbb)
1678 {
1679 ppl_Polyhedron_t accesses;
1680 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps;
1681 ppl_dimension_type dom_nb_dims;
1682 ppl_dimension_type accessp_nb_dims;
1683 int dr_base_object_set;
1684
1685 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb),
1686 &dom_nb_dims);
1687 accessp_nb_dims = dom_nb_dims + 1 + DR_NUM_DIMENSIONS (dr);
1688
1689 ppl_new_C_Polyhedron_from_space_dimension (&accesses, accessp_nb_dims, 0);
1690
1691 pdr_add_alias_set (accesses, dr, accessp_nb_dims, dom_nb_dims);
1692 pdr_add_memory_accesses (accesses, dr, accessp_nb_dims, dom_nb_dims, pbb);
1693 pdr_add_data_dimensions (accesses, dr, accessp_nb_dims, dom_nb_dims);
1694
1695 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps,
1696 accesses);
1697 ppl_delete_Polyhedron (accesses);
1698
1699 gcc_assert (dr->aux);
1700 dr_base_object_set = ((base_alias_pair *)(dr->aux))->base_obj_set;
1701
1702 new_poly_dr (pbb, dr_base_object_set, accesses_ps,
1703 DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
1704 dr, DR_NUM_DIMENSIONS (dr));
1705 }
1706
1707 /* Write to FILE the alias graph of data references in DIMACS format. */
1708
1709 static inline bool
write_alias_graph_to_ascii_dimacs(FILE * file,char * comment,VEC (data_reference_p,heap)* drs)1710 write_alias_graph_to_ascii_dimacs (FILE *file, char *comment,
1711 VEC (data_reference_p, heap) *drs)
1712 {
1713 int num_vertex = VEC_length (data_reference_p, drs);
1714 int edge_num = 0;
1715 data_reference_p dr1, dr2;
1716 int i, j;
1717
1718 if (num_vertex == 0)
1719 return true;
1720
1721 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1722 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1723 if (dr_may_alias_p (dr1, dr2, true))
1724 edge_num++;
1725
1726 fprintf (file, "$\n");
1727
1728 if (comment)
1729 fprintf (file, "c %s\n", comment);
1730
1731 fprintf (file, "p edge %d %d\n", num_vertex, edge_num);
1732
1733 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1734 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1735 if (dr_may_alias_p (dr1, dr2, true))
1736 fprintf (file, "e %d %d\n", i + 1, j + 1);
1737
1738 return true;
1739 }
1740
1741 /* Write to FILE the alias graph of data references in DOT format. */
1742
1743 static inline bool
write_alias_graph_to_ascii_dot(FILE * file,char * comment,VEC (data_reference_p,heap)* drs)1744 write_alias_graph_to_ascii_dot (FILE *file, char *comment,
1745 VEC (data_reference_p, heap) *drs)
1746 {
1747 int num_vertex = VEC_length (data_reference_p, drs);
1748 data_reference_p dr1, dr2;
1749 int i, j;
1750
1751 if (num_vertex == 0)
1752 return true;
1753
1754 fprintf (file, "$\n");
1755
1756 if (comment)
1757 fprintf (file, "c %s\n", comment);
1758
1759 /* First print all the vertices. */
1760 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1761 fprintf (file, "n%d;\n", i);
1762
1763 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1764 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1765 if (dr_may_alias_p (dr1, dr2, true))
1766 fprintf (file, "n%d n%d\n", i, j);
1767
1768 return true;
1769 }
1770
1771 /* Write to FILE the alias graph of data references in ECC format. */
1772
1773 static inline bool
write_alias_graph_to_ascii_ecc(FILE * file,char * comment,VEC (data_reference_p,heap)* drs)1774 write_alias_graph_to_ascii_ecc (FILE *file, char *comment,
1775 VEC (data_reference_p, heap) *drs)
1776 {
1777 int num_vertex = VEC_length (data_reference_p, drs);
1778 data_reference_p dr1, dr2;
1779 int i, j;
1780
1781 if (num_vertex == 0)
1782 return true;
1783
1784 fprintf (file, "$\n");
1785
1786 if (comment)
1787 fprintf (file, "c %s\n", comment);
1788
1789 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1790 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1791 if (dr_may_alias_p (dr1, dr2, true))
1792 fprintf (file, "%d %d\n", i, j);
1793
1794 return true;
1795 }
1796
1797 /* Check if DR1 and DR2 are in the same object set. */
1798
1799 static bool
dr_same_base_object_p(const struct data_reference * dr1,const struct data_reference * dr2)1800 dr_same_base_object_p (const struct data_reference *dr1,
1801 const struct data_reference *dr2)
1802 {
1803 return operand_equal_p (DR_BASE_OBJECT (dr1), DR_BASE_OBJECT (dr2), 0);
1804 }
1805
1806 /* Uses DFS component number as representative of alias-sets. Also tests for
1807 optimality by verifying if every connected component is a clique. Returns
1808 true (1) if the above test is true, and false (0) otherwise. */
1809
1810 static int
build_alias_set_optimal_p(VEC (data_reference_p,heap)* drs)1811 build_alias_set_optimal_p (VEC (data_reference_p, heap) *drs)
1812 {
1813 int num_vertices = VEC_length (data_reference_p, drs);
1814 struct graph *g = new_graph (num_vertices);
1815 data_reference_p dr1, dr2;
1816 int i, j;
1817 int num_connected_components;
1818 int v_indx1, v_indx2, num_vertices_in_component;
1819 int *all_vertices;
1820 int *vertices;
1821 struct graph_edge *e;
1822 int this_component_is_clique;
1823 int all_components_are_cliques = 1;
1824
1825 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1826 for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1827 if (dr_may_alias_p (dr1, dr2, true))
1828 {
1829 add_edge (g, i, j);
1830 add_edge (g, j, i);
1831 }
1832
1833 all_vertices = XNEWVEC (int, num_vertices);
1834 vertices = XNEWVEC (int, num_vertices);
1835 for (i = 0; i < num_vertices; i++)
1836 all_vertices[i] = i;
1837
1838 num_connected_components = graphds_dfs (g, all_vertices, num_vertices,
1839 NULL, true, NULL);
1840 for (i = 0; i < g->n_vertices; i++)
1841 {
1842 data_reference_p dr = VEC_index (data_reference_p, drs, i);
1843 base_alias_pair *bap;
1844
1845 gcc_assert (dr->aux);
1846 bap = (base_alias_pair *)(dr->aux);
1847
1848 bap->alias_set = XNEW (int);
1849 *(bap->alias_set) = g->vertices[i].component + 1;
1850 }
1851
1852 /* Verify if the DFS numbering results in optimal solution. */
1853 for (i = 0; i < num_connected_components; i++)
1854 {
1855 num_vertices_in_component = 0;
1856 /* Get all vertices whose DFS component number is the same as i. */
1857 for (j = 0; j < num_vertices; j++)
1858 if (g->vertices[j].component == i)
1859 vertices[num_vertices_in_component++] = j;
1860
1861 /* Now test if the vertices in 'vertices' form a clique, by testing
1862 for edges among each pair. */
1863 this_component_is_clique = 1;
1864 for (v_indx1 = 0; v_indx1 < num_vertices_in_component; v_indx1++)
1865 {
1866 for (v_indx2 = v_indx1+1; v_indx2 < num_vertices_in_component; v_indx2++)
1867 {
1868 /* Check if the two vertices are connected by iterating
1869 through all the edges which have one of these are source. */
1870 e = g->vertices[vertices[v_indx2]].pred;
1871 while (e)
1872 {
1873 if (e->src == vertices[v_indx1])
1874 break;
1875 e = e->pred_next;
1876 }
1877 if (!e)
1878 {
1879 this_component_is_clique = 0;
1880 break;
1881 }
1882 }
1883 if (!this_component_is_clique)
1884 all_components_are_cliques = 0;
1885 }
1886 }
1887
1888 free (all_vertices);
1889 free (vertices);
1890 free_graph (g);
1891 return all_components_are_cliques;
1892 }
1893
1894 /* Group each data reference in DRS with its base object set num. */
1895
1896 static void
build_base_obj_set_for_drs(VEC (data_reference_p,heap)* drs)1897 build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs)
1898 {
1899 int num_vertex = VEC_length (data_reference_p, drs);
1900 struct graph *g = new_graph (num_vertex);
1901 data_reference_p dr1, dr2;
1902 int i, j;
1903 int *queue;
1904
1905 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1906 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1907 if (dr_same_base_object_p (dr1, dr2))
1908 {
1909 add_edge (g, i, j);
1910 add_edge (g, j, i);
1911 }
1912
1913 queue = XNEWVEC (int, num_vertex);
1914 for (i = 0; i < num_vertex; i++)
1915 queue[i] = i;
1916
1917 graphds_dfs (g, queue, num_vertex, NULL, true, NULL);
1918
1919 for (i = 0; i < g->n_vertices; i++)
1920 {
1921 data_reference_p dr = VEC_index (data_reference_p, drs, i);
1922 base_alias_pair *bap;
1923
1924 gcc_assert (dr->aux);
1925 bap = (base_alias_pair *)(dr->aux);
1926
1927 bap->base_obj_set = g->vertices[i].component + 1;
1928 }
1929
1930 free (queue);
1931 free_graph (g);
1932 }
1933
1934 /* Build the data references for PBB. */
1935
1936 static void
build_pbb_drs(poly_bb_p pbb)1937 build_pbb_drs (poly_bb_p pbb)
1938 {
1939 int j;
1940 data_reference_p dr;
1941 VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb));
1942
1943 FOR_EACH_VEC_ELT (data_reference_p, gbb_drs, j, dr)
1944 build_poly_dr (dr, pbb);
1945 }
1946
1947 /* Dump to file the alias graphs for the data references in DRS. */
1948
1949 static void
dump_alias_graphs(VEC (data_reference_p,heap)* drs)1950 dump_alias_graphs (VEC (data_reference_p, heap) *drs)
1951 {
1952 char comment[100];
1953 FILE *file_dimacs, *file_ecc, *file_dot;
1954
1955 file_dimacs = fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1956 if (file_dimacs)
1957 {
1958 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
1959 current_function_name ());
1960 write_alias_graph_to_ascii_dimacs (file_dimacs, comment, drs);
1961 fclose (file_dimacs);
1962 }
1963
1964 file_ecc = fopen ("/tmp/dr_alias_graph_ecc", "ab");
1965 if (file_ecc)
1966 {
1967 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
1968 current_function_name ());
1969 write_alias_graph_to_ascii_ecc (file_ecc, comment, drs);
1970 fclose (file_ecc);
1971 }
1972
1973 file_dot = fopen ("/tmp/dr_alias_graph_dot", "ab");
1974 if (file_dot)
1975 {
1976 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
1977 current_function_name ());
1978 write_alias_graph_to_ascii_dot (file_dot, comment, drs);
1979 fclose (file_dot);
1980 }
1981 }
1982
1983 /* Build data references in SCOP. */
1984
1985 static void
build_scop_drs(scop_p scop)1986 build_scop_drs (scop_p scop)
1987 {
1988 int i, j;
1989 poly_bb_p pbb;
1990 data_reference_p dr;
1991 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
1992
1993 /* Remove all the PBBs that do not have data references: these basic
1994 blocks are not handled in the polyhedral representation. */
1995 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1996 if (VEC_empty (data_reference_p, GBB_DATA_REFS (PBB_BLACK_BOX (pbb))))
1997 {
1998 free_gimple_bb (PBB_BLACK_BOX (pbb));
1999 VEC_ordered_remove (poly_bb_p, SCOP_BBS (scop), i);
2000 i--;
2001 }
2002
2003 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
2004 for (j = 0; VEC_iterate (data_reference_p,
2005 GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++)
2006 VEC_safe_push (data_reference_p, heap, drs, dr);
2007
2008 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr)
2009 dr->aux = XNEW (base_alias_pair);
2010
2011 if (!build_alias_set_optimal_p (drs))
2012 {
2013 /* TODO: Add support when building alias set is not optimal. */
2014 ;
2015 }
2016
2017 build_base_obj_set_for_drs (drs);
2018
2019 /* When debugging, enable the following code. This cannot be used
2020 in production compilers. */
2021 if (0)
2022 dump_alias_graphs (drs);
2023
2024 VEC_free (data_reference_p, heap, drs);
2025
2026 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
2027 build_pbb_drs (pbb);
2028 }
2029
2030 /* Return a gsi at the position of the phi node STMT. */
2031
2032 static gimple_stmt_iterator
gsi_for_phi_node(gimple stmt)2033 gsi_for_phi_node (gimple stmt)
2034 {
2035 gimple_stmt_iterator psi;
2036 basic_block bb = gimple_bb (stmt);
2037
2038 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
2039 if (stmt == gsi_stmt (psi))
2040 return psi;
2041
2042 gcc_unreachable ();
2043 return psi;
2044 }
2045
2046 /* Analyze all the data references of STMTS and add them to the
2047 GBB_DATA_REFS vector of BB. */
2048
2049 static void
analyze_drs_in_stmts(scop_p scop,basic_block bb,VEC (gimple,heap)* stmts)2050 analyze_drs_in_stmts (scop_p scop, basic_block bb, VEC (gimple, heap) *stmts)
2051 {
2052 loop_p nest;
2053 gimple_bb_p gbb;
2054 gimple stmt;
2055 int i;
2056 sese region = SCOP_REGION (scop);
2057
2058 if (!bb_in_sese_p (bb, region))
2059 return;
2060
2061 nest = outermost_loop_in_sese_1 (region, bb);
2062 gbb = gbb_from_bb (bb);
2063
2064 FOR_EACH_VEC_ELT (gimple, stmts, i, stmt)
2065 {
2066 loop_p loop;
2067
2068 if (is_gimple_debug (stmt))
2069 continue;
2070
2071 loop = loop_containing_stmt (stmt);
2072 if (!loop_in_sese_p (loop, region))
2073 loop = nest;
2074
2075 graphite_find_data_references_in_stmt (nest, loop, stmt,
2076 &GBB_DATA_REFS (gbb));
2077 }
2078 }
2079
2080 /* Insert STMT at the end of the STMTS sequence and then insert the
2081 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
2082 on STMTS. */
2083
2084 static void
insert_stmts(scop_p scop,gimple stmt,gimple_seq stmts,gimple_stmt_iterator insert_gsi)2085 insert_stmts (scop_p scop, gimple stmt, gimple_seq stmts,
2086 gimple_stmt_iterator insert_gsi)
2087 {
2088 gimple_stmt_iterator gsi;
2089 VEC (gimple, heap) *x = VEC_alloc (gimple, heap, 3);
2090
2091 if (!stmts)
2092 stmts = gimple_seq_alloc ();
2093
2094 gsi = gsi_last (stmts);
2095 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2096 for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
2097 VEC_safe_push (gimple, heap, x, gsi_stmt (gsi));
2098
2099 gsi_insert_seq_before (&insert_gsi, stmts, GSI_SAME_STMT);
2100 analyze_drs_in_stmts (scop, gsi_bb (insert_gsi), x);
2101 VEC_free (gimple, heap, x);
2102 }
2103
2104 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
2105
2106 static void
insert_out_of_ssa_copy(scop_p scop,tree res,tree expr,gimple after_stmt)2107 insert_out_of_ssa_copy (scop_p scop, tree res, tree expr, gimple after_stmt)
2108 {
2109 gimple_seq stmts;
2110 gimple_stmt_iterator si;
2111 gimple_stmt_iterator gsi;
2112 tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
2113 gimple stmt = gimple_build_assign (res, var);
2114 VEC (gimple, heap) *x = VEC_alloc (gimple, heap, 3);
2115
2116 if (!stmts)
2117 stmts = gimple_seq_alloc ();
2118 si = gsi_last (stmts);
2119 gsi_insert_after (&si, stmt, GSI_NEW_STMT);
2120 for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
2121 VEC_safe_push (gimple, heap, x, gsi_stmt (gsi));
2122
2123 if (gimple_code (after_stmt) == GIMPLE_PHI)
2124 {
2125 gsi = gsi_after_labels (gimple_bb (after_stmt));
2126 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2127 }
2128 else
2129 {
2130 gsi = gsi_for_stmt (after_stmt);
2131 gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
2132 }
2133
2134 analyze_drs_in_stmts (scop, gimple_bb (after_stmt), x);
2135 VEC_free (gimple, heap, x);
2136 }
2137
2138 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2139
2140 static void
new_pbb_from_pbb(scop_p scop,poly_bb_p pbb,basic_block bb)2141 new_pbb_from_pbb (scop_p scop, poly_bb_p pbb, basic_block bb)
2142 {
2143 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
2144 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
2145 gimple_bb_p gbb1 = new_gimple_bb (bb, drs);
2146 poly_bb_p pbb1 = new_poly_bb (scop, gbb1);
2147 int index, n = VEC_length (poly_bb_p, SCOP_BBS (scop));
2148
2149 /* The INDEX of PBB in SCOP_BBS. */
2150 for (index = 0; index < n; index++)
2151 if (VEC_index (poly_bb_p, SCOP_BBS (scop), index) == pbb)
2152 break;
2153
2154 if (PBB_DOMAIN (pbb))
2155 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
2156 (&PBB_DOMAIN (pbb1), PBB_DOMAIN (pbb));
2157
2158 GBB_PBB (gbb1) = pbb1;
2159 GBB_CONDITIONS (gbb1) = VEC_copy (gimple, heap, GBB_CONDITIONS (gbb));
2160 GBB_CONDITION_CASES (gbb1) = VEC_copy (gimple, heap, GBB_CONDITION_CASES (gbb));
2161 VEC_safe_insert (poly_bb_p, heap, SCOP_BBS (scop), index + 1, pbb1);
2162 }
2163
2164 /* Insert on edge E the assignment "RES := EXPR". */
2165
2166 static void
insert_out_of_ssa_copy_on_edge(scop_p scop,edge e,tree res,tree expr)2167 insert_out_of_ssa_copy_on_edge (scop_p scop, edge e, tree res, tree expr)
2168 {
2169 gimple_stmt_iterator gsi;
2170 gimple_seq stmts;
2171 tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
2172 gimple stmt = gimple_build_assign (res, var);
2173 basic_block bb;
2174 VEC (gimple, heap) *x = VEC_alloc (gimple, heap, 3);
2175
2176 if (!stmts)
2177 stmts = gimple_seq_alloc ();
2178
2179 gsi = gsi_last (stmts);
2180 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2181 for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
2182 VEC_safe_push (gimple, heap, x, gsi_stmt (gsi));
2183
2184 gsi_insert_seq_on_edge (e, stmts);
2185 gsi_commit_edge_inserts ();
2186 bb = gimple_bb (stmt);
2187
2188 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
2189 return;
2190
2191 if (!gbb_from_bb (bb))
2192 new_pbb_from_pbb (scop, pbb_from_bb (e->src), bb);
2193
2194 analyze_drs_in_stmts (scop, bb, x);
2195 VEC_free (gimple, heap, x);
2196 }
2197
2198 /* Creates a zero dimension array of the same type as VAR. */
2199
2200 static tree
create_zero_dim_array(tree var,const char * base_name)2201 create_zero_dim_array (tree var, const char *base_name)
2202 {
2203 tree index_type = build_index_type (integer_zero_node);
2204 tree elt_type = TREE_TYPE (var);
2205 tree array_type = build_array_type (elt_type, index_type);
2206 tree base = create_tmp_var (array_type, base_name);
2207
2208 add_referenced_var (base);
2209
2210 return build4 (ARRAY_REF, elt_type, base, integer_zero_node, NULL_TREE,
2211 NULL_TREE);
2212 }
2213
2214 /* Returns true when PHI is a loop close phi node. */
2215
2216 static bool
scalar_close_phi_node_p(gimple phi)2217 scalar_close_phi_node_p (gimple phi)
2218 {
2219 if (gimple_code (phi) != GIMPLE_PHI
2220 || !is_gimple_reg (gimple_phi_result (phi)))
2221 return false;
2222
2223 /* Note that loop close phi nodes should have a single argument
2224 because we translated the representation into a canonical form
2225 before Graphite: see canonicalize_loop_closed_ssa_form. */
2226 return (gimple_phi_num_args (phi) == 1);
2227 }
2228
2229 /* For a definition DEF in REGION, propagates the expression EXPR in
2230 all the uses of DEF outside REGION. */
2231
2232 static void
propagate_expr_outside_region(tree def,tree expr,sese region)2233 propagate_expr_outside_region (tree def, tree expr, sese region)
2234 {
2235 imm_use_iterator imm_iter;
2236 gimple use_stmt;
2237 gimple_seq stmts;
2238 bool replaced_once = false;
2239
2240 gcc_assert (TREE_CODE (def) == SSA_NAME);
2241
2242 expr = force_gimple_operand (unshare_expr (expr), &stmts, true,
2243 NULL_TREE);
2244
2245 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2246 if (!is_gimple_debug (use_stmt)
2247 && !bb_in_sese_p (gimple_bb (use_stmt), region))
2248 {
2249 ssa_op_iter iter;
2250 use_operand_p use_p;
2251
2252 FOR_EACH_PHI_OR_STMT_USE (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2253 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0)
2254 && (replaced_once = true))
2255 replace_exp (use_p, expr);
2256
2257 update_stmt (use_stmt);
2258 }
2259
2260 if (replaced_once)
2261 {
2262 gsi_insert_seq_on_edge (SESE_ENTRY (region), stmts);
2263 gsi_commit_edge_inserts ();
2264 }
2265 }
2266
2267 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2268 dimension array for it. */
2269
2270 static void
rewrite_close_phi_out_of_ssa(scop_p scop,gimple_stmt_iterator * psi)2271 rewrite_close_phi_out_of_ssa (scop_p scop, gimple_stmt_iterator *psi)
2272 {
2273 sese region = SCOP_REGION (scop);
2274 gimple phi = gsi_stmt (*psi);
2275 tree res = gimple_phi_result (phi);
2276 tree var = SSA_NAME_VAR (res);
2277 basic_block bb = gimple_bb (phi);
2278 gimple_stmt_iterator gsi = gsi_after_labels (bb);
2279 tree arg = gimple_phi_arg_def (phi, 0);
2280 gimple stmt;
2281
2282 /* Note that loop close phi nodes should have a single argument
2283 because we translated the representation into a canonical form
2284 before Graphite: see canonicalize_loop_closed_ssa_form. */
2285 gcc_assert (gimple_phi_num_args (phi) == 1);
2286
2287 /* The phi node can be a non close phi node, when its argument is
2288 invariant, or a default definition. */
2289 if (is_gimple_min_invariant (arg)
2290 || SSA_NAME_IS_DEFAULT_DEF (arg))
2291 {
2292 propagate_expr_outside_region (res, arg, region);
2293 gsi_next (psi);
2294 return;
2295 }
2296
2297 else if (gimple_bb (SSA_NAME_DEF_STMT (arg))->loop_father == bb->loop_father)
2298 {
2299 propagate_expr_outside_region (res, arg, region);
2300 stmt = gimple_build_assign (res, arg);
2301 remove_phi_node (psi, false);
2302 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2303 SSA_NAME_DEF_STMT (res) = stmt;
2304 return;
2305 }
2306
2307 /* If res is scev analyzable and is not a scalar value, it is safe
2308 to ignore the close phi node: it will be code generated in the
2309 out of Graphite pass. */
2310 else if (scev_analyzable_p (res, region))
2311 {
2312 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (res));
2313 tree scev;
2314
2315 if (!loop_in_sese_p (loop, region))
2316 {
2317 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (arg));
2318 scev = scalar_evolution_in_region (region, loop, arg);
2319 scev = compute_overall_effect_of_inner_loop (loop, scev);
2320 }
2321 else
2322 scev = scalar_evolution_in_region (region, loop, res);
2323
2324 if (tree_does_not_contain_chrecs (scev))
2325 propagate_expr_outside_region (res, scev, region);
2326
2327 gsi_next (psi);
2328 return;
2329 }
2330 else
2331 {
2332 tree zero_dim_array = create_zero_dim_array (var, "Close_Phi");
2333
2334 stmt = gimple_build_assign (res, zero_dim_array);
2335
2336 if (TREE_CODE (arg) == SSA_NAME)
2337 insert_out_of_ssa_copy (scop, zero_dim_array, arg,
2338 SSA_NAME_DEF_STMT (arg));
2339 else
2340 insert_out_of_ssa_copy_on_edge (scop, single_pred_edge (bb),
2341 zero_dim_array, arg);
2342 }
2343
2344 remove_phi_node (psi, false);
2345 SSA_NAME_DEF_STMT (res) = stmt;
2346
2347 insert_stmts (scop, stmt, NULL, gsi_after_labels (bb));
2348 }
2349
2350 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2351 dimension array for it. */
2352
2353 static void
rewrite_phi_out_of_ssa(scop_p scop,gimple_stmt_iterator * psi)2354 rewrite_phi_out_of_ssa (scop_p scop, gimple_stmt_iterator *psi)
2355 {
2356 size_t i;
2357 gimple phi = gsi_stmt (*psi);
2358 basic_block bb = gimple_bb (phi);
2359 tree res = gimple_phi_result (phi);
2360 tree var = SSA_NAME_VAR (res);
2361 tree zero_dim_array = create_zero_dim_array (var, "phi_out_of_ssa");
2362 gimple stmt;
2363 gimple_seq stmts;
2364
2365 for (i = 0; i < gimple_phi_num_args (phi); i++)
2366 {
2367 tree arg = gimple_phi_arg_def (phi, i);
2368 edge e = gimple_phi_arg_edge (phi, i);
2369
2370 /* Avoid the insertion of code in the loop latch to please the
2371 pattern matching of the vectorizer. */
2372 if (TREE_CODE (arg) == SSA_NAME
2373 && e->src == bb->loop_father->latch)
2374 insert_out_of_ssa_copy (scop, zero_dim_array, arg,
2375 SSA_NAME_DEF_STMT (arg));
2376 else
2377 insert_out_of_ssa_copy_on_edge (scop, e, zero_dim_array, arg);
2378 }
2379
2380 var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE);
2381
2382 stmt = gimple_build_assign (res, var);
2383 remove_phi_node (psi, false);
2384 SSA_NAME_DEF_STMT (res) = stmt;
2385
2386 insert_stmts (scop, stmt, stmts, gsi_after_labels (bb));
2387 }
2388
2389 /* Rewrite the degenerate phi node at position PSI from the degenerate
2390 form "x = phi (y, y, ..., y)" to "x = y". */
2391
2392 static void
rewrite_degenerate_phi(gimple_stmt_iterator * psi)2393 rewrite_degenerate_phi (gimple_stmt_iterator *psi)
2394 {
2395 tree rhs;
2396 gimple stmt;
2397 gimple_stmt_iterator gsi;
2398 gimple phi = gsi_stmt (*psi);
2399 tree res = gimple_phi_result (phi);
2400 basic_block bb;
2401
2402 bb = gimple_bb (phi);
2403 rhs = degenerate_phi_result (phi);
2404 gcc_assert (rhs);
2405
2406 stmt = gimple_build_assign (res, rhs);
2407 remove_phi_node (psi, false);
2408 SSA_NAME_DEF_STMT (res) = stmt;
2409
2410 gsi = gsi_after_labels (bb);
2411 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2412 }
2413
2414 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2415
2416 static void
rewrite_reductions_out_of_ssa(scop_p scop)2417 rewrite_reductions_out_of_ssa (scop_p scop)
2418 {
2419 basic_block bb;
2420 gimple_stmt_iterator psi;
2421 sese region = SCOP_REGION (scop);
2422
2423 FOR_EACH_BB (bb)
2424 if (bb_in_sese_p (bb, region))
2425 for (psi = gsi_start_phis (bb); !gsi_end_p (psi);)
2426 {
2427 gimple phi = gsi_stmt (psi);
2428
2429 if (!is_gimple_reg (gimple_phi_result (phi)))
2430 {
2431 gsi_next (&psi);
2432 continue;
2433 }
2434
2435 if (gimple_phi_num_args (phi) > 1
2436 && degenerate_phi_result (phi))
2437 rewrite_degenerate_phi (&psi);
2438
2439 else if (scalar_close_phi_node_p (phi))
2440 rewrite_close_phi_out_of_ssa (scop, &psi);
2441
2442 else if (reduction_phi_p (region, &psi))
2443 rewrite_phi_out_of_ssa (scop, &psi);
2444 }
2445
2446 update_ssa (TODO_update_ssa);
2447 #ifdef ENABLE_CHECKING
2448 verify_loop_closed_ssa (true);
2449 #endif
2450 }
2451
2452 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2453 read from ZERO_DIM_ARRAY. */
2454
2455 static void
rewrite_cross_bb_scalar_dependence(scop_p scop,tree zero_dim_array,tree def,gimple use_stmt)2456 rewrite_cross_bb_scalar_dependence (scop_p scop, tree zero_dim_array,
2457 tree def, gimple use_stmt)
2458 {
2459 tree var = SSA_NAME_VAR (def);
2460 gimple name_stmt = gimple_build_assign (var, zero_dim_array);
2461 tree name = make_ssa_name (var, name_stmt);
2462 ssa_op_iter iter;
2463 use_operand_p use_p;
2464
2465 gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
2466
2467 gimple_assign_set_lhs (name_stmt, name);
2468 insert_stmts (scop, name_stmt, NULL, gsi_for_stmt (use_stmt));
2469
2470 FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2471 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0))
2472 replace_exp (use_p, name);
2473
2474 update_stmt (use_stmt);
2475 }
2476
2477 /* For every definition DEF in the SCOP that is used outside the scop,
2478 insert a closing-scop definition in the basic block just after this
2479 SCOP. */
2480
2481 static void
handle_scalar_deps_crossing_scop_limits(scop_p scop,tree def,gimple stmt)2482 handle_scalar_deps_crossing_scop_limits (scop_p scop, tree def, gimple stmt)
2483 {
2484 tree var = create_tmp_reg (TREE_TYPE (def), NULL);
2485 tree new_name = make_ssa_name (var, stmt);
2486 bool needs_copy = false;
2487 use_operand_p use_p;
2488 imm_use_iterator imm_iter;
2489 gimple use_stmt;
2490 sese region = SCOP_REGION (scop);
2491
2492 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2493 {
2494 if (!bb_in_sese_p (gimple_bb (use_stmt), region))
2495 {
2496 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
2497 {
2498 SET_USE (use_p, new_name);
2499 }
2500 update_stmt (use_stmt);
2501 needs_copy = true;
2502 }
2503 }
2504
2505 /* Insert in the empty BB just after the scop a use of DEF such
2506 that the rewrite of cross_bb_scalar_dependences won't insert
2507 arrays everywhere else. */
2508 if (needs_copy)
2509 {
2510 gimple assign = gimple_build_assign (new_name, def);
2511 gimple_stmt_iterator psi = gsi_after_labels (SESE_EXIT (region)->dest);
2512
2513 add_referenced_var (var);
2514 SSA_NAME_DEF_STMT (new_name) = assign;
2515 update_stmt (assign);
2516 gsi_insert_before (&psi, assign, GSI_SAME_STMT);
2517 }
2518 }
2519
2520 /* Rewrite the scalar dependences crossing the boundary of the BB
2521 containing STMT with an array. Return true when something has been
2522 changed. */
2523
2524 static bool
rewrite_cross_bb_scalar_deps(scop_p scop,gimple_stmt_iterator * gsi)2525 rewrite_cross_bb_scalar_deps (scop_p scop, gimple_stmt_iterator *gsi)
2526 {
2527 sese region = SCOP_REGION (scop);
2528 gimple stmt = gsi_stmt (*gsi);
2529 imm_use_iterator imm_iter;
2530 tree def;
2531 basic_block def_bb;
2532 tree zero_dim_array = NULL_TREE;
2533 gimple use_stmt;
2534 bool res = false;
2535
2536 switch (gimple_code (stmt))
2537 {
2538 case GIMPLE_ASSIGN:
2539 def = gimple_assign_lhs (stmt);
2540 break;
2541
2542 case GIMPLE_CALL:
2543 def = gimple_call_lhs (stmt);
2544 break;
2545
2546 default:
2547 return false;
2548 }
2549
2550 if (!def
2551 || !is_gimple_reg (def))
2552 return false;
2553
2554 if (scev_analyzable_p (def, region))
2555 {
2556 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
2557 tree scev = scalar_evolution_in_region (region, loop, def);
2558
2559 if (tree_contains_chrecs (scev, NULL))
2560 return false;
2561
2562 propagate_expr_outside_region (def, scev, region);
2563 return true;
2564 }
2565
2566 def_bb = gimple_bb (stmt);
2567
2568 handle_scalar_deps_crossing_scop_limits (scop, def, stmt);
2569
2570 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2571 if (gimple_code (use_stmt) == GIMPLE_PHI
2572 && (res = true))
2573 {
2574 gimple_stmt_iterator psi = gsi_for_stmt (use_stmt);
2575
2576 if (scalar_close_phi_node_p (gsi_stmt (psi)))
2577 rewrite_close_phi_out_of_ssa (scop, &psi);
2578 else
2579 rewrite_phi_out_of_ssa (scop, &psi);
2580 }
2581
2582 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2583 if (gimple_code (use_stmt) != GIMPLE_PHI
2584 && def_bb != gimple_bb (use_stmt)
2585 && !is_gimple_debug (use_stmt)
2586 && (res = true))
2587 {
2588 if (!zero_dim_array)
2589 {
2590 zero_dim_array = create_zero_dim_array
2591 (SSA_NAME_VAR (def), "Cross_BB_scalar_dependence");
2592 insert_out_of_ssa_copy (scop, zero_dim_array, def,
2593 SSA_NAME_DEF_STMT (def));
2594 gsi_next (gsi);
2595 }
2596
2597 rewrite_cross_bb_scalar_dependence (scop, zero_dim_array,
2598 def, use_stmt);
2599 }
2600
2601 return res;
2602 }
2603
2604 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2605
2606 static void
rewrite_cross_bb_scalar_deps_out_of_ssa(scop_p scop)2607 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop)
2608 {
2609 basic_block bb;
2610 gimple_stmt_iterator psi;
2611 sese region = SCOP_REGION (scop);
2612 bool changed = false;
2613
2614 /* Create an extra empty BB after the scop. */
2615 split_edge (SESE_EXIT (region));
2616
2617 FOR_EACH_BB (bb)
2618 if (bb_in_sese_p (bb, region))
2619 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
2620 changed |= rewrite_cross_bb_scalar_deps (scop, &psi);
2621
2622 if (changed)
2623 {
2624 scev_reset_htab ();
2625 update_ssa (TODO_update_ssa);
2626 #ifdef ENABLE_CHECKING
2627 verify_loop_closed_ssa (true);
2628 #endif
2629 }
2630 }
2631
2632 /* Returns the number of pbbs that are in loops contained in SCOP. */
2633
2634 static int
nb_pbbs_in_loops(scop_p scop)2635 nb_pbbs_in_loops (scop_p scop)
2636 {
2637 int i;
2638 poly_bb_p pbb;
2639 int res = 0;
2640
2641 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
2642 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop)))
2643 res++;
2644
2645 return res;
2646 }
2647
2648 /* Return the number of data references in BB that write in
2649 memory. */
2650
2651 static int
nb_data_writes_in_bb(basic_block bb)2652 nb_data_writes_in_bb (basic_block bb)
2653 {
2654 int res = 0;
2655 gimple_stmt_iterator gsi;
2656
2657 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2658 if (gimple_vdef (gsi_stmt (gsi)))
2659 res++;
2660
2661 return res;
2662 }
2663
2664 /* Splits at STMT the basic block BB represented as PBB in the
2665 polyhedral form. */
2666
2667 static edge
split_pbb(scop_p scop,poly_bb_p pbb,basic_block bb,gimple stmt)2668 split_pbb (scop_p scop, poly_bb_p pbb, basic_block bb, gimple stmt)
2669 {
2670 edge e1 = split_block (bb, stmt);
2671 new_pbb_from_pbb (scop, pbb, e1->dest);
2672 return e1;
2673 }
2674
2675 /* Splits STMT out of its current BB. This is done for reduction
2676 statements for which we want to ignore data dependences. */
2677
2678 static basic_block
split_reduction_stmt(scop_p scop,gimple stmt)2679 split_reduction_stmt (scop_p scop, gimple stmt)
2680 {
2681 basic_block bb = gimple_bb (stmt);
2682 poly_bb_p pbb = pbb_from_bb (bb);
2683 gimple_bb_p gbb = gbb_from_bb (bb);
2684 edge e1;
2685 int i;
2686 data_reference_p dr;
2687
2688 /* Do not split basic blocks with no writes to memory: the reduction
2689 will be the only write to memory. */
2690 if (nb_data_writes_in_bb (bb) == 0
2691 /* Or if we have already marked BB as a reduction. */
2692 || PBB_IS_REDUCTION (pbb_from_bb (bb)))
2693 return bb;
2694
2695 e1 = split_pbb (scop, pbb, bb, stmt);
2696
2697 /* Split once more only when the reduction stmt is not the only one
2698 left in the original BB. */
2699 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb)))
2700 {
2701 gimple_stmt_iterator gsi = gsi_last_bb (bb);
2702 gsi_prev (&gsi);
2703 e1 = split_pbb (scop, pbb, bb, gsi_stmt (gsi));
2704 }
2705
2706 /* A part of the data references will end in a different basic block
2707 after the split: move the DRs from the original GBB to the newly
2708 created GBB1. */
2709 FOR_EACH_VEC_ELT (data_reference_p, GBB_DATA_REFS (gbb), i, dr)
2710 {
2711 basic_block bb1 = gimple_bb (DR_STMT (dr));
2712
2713 if (bb1 != bb)
2714 {
2715 gimple_bb_p gbb1 = gbb_from_bb (bb1);
2716 VEC_safe_push (data_reference_p, heap, GBB_DATA_REFS (gbb1), dr);
2717 VEC_ordered_remove (data_reference_p, GBB_DATA_REFS (gbb), i);
2718 i--;
2719 }
2720 }
2721
2722 return e1->dest;
2723 }
2724
2725 /* Return true when stmt is a reduction operation. */
2726
2727 static inline bool
is_reduction_operation_p(gimple stmt)2728 is_reduction_operation_p (gimple stmt)
2729 {
2730 enum tree_code code;
2731
2732 gcc_assert (is_gimple_assign (stmt));
2733 code = gimple_assign_rhs_code (stmt);
2734
2735 return flag_associative_math
2736 && commutative_tree_code (code)
2737 && associative_tree_code (code);
2738 }
2739
2740 /* Returns true when PHI contains an argument ARG. */
2741
2742 static bool
phi_contains_arg(gimple phi,tree arg)2743 phi_contains_arg (gimple phi, tree arg)
2744 {
2745 size_t i;
2746
2747 for (i = 0; i < gimple_phi_num_args (phi); i++)
2748 if (operand_equal_p (arg, gimple_phi_arg_def (phi, i), 0))
2749 return true;
2750
2751 return false;
2752 }
2753
2754 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2755
2756 static gimple
follow_ssa_with_commutative_ops(tree arg,tree lhs)2757 follow_ssa_with_commutative_ops (tree arg, tree lhs)
2758 {
2759 gimple stmt;
2760
2761 if (TREE_CODE (arg) != SSA_NAME)
2762 return NULL;
2763
2764 stmt = SSA_NAME_DEF_STMT (arg);
2765
2766 if (gimple_code (stmt) == GIMPLE_NOP
2767 || gimple_code (stmt) == GIMPLE_CALL)
2768 return NULL;
2769
2770 if (gimple_code (stmt) == GIMPLE_PHI)
2771 {
2772 if (phi_contains_arg (stmt, lhs))
2773 return stmt;
2774 return NULL;
2775 }
2776
2777 if (!is_gimple_assign (stmt))
2778 return NULL;
2779
2780 if (gimple_num_ops (stmt) == 2)
2781 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2782
2783 if (is_reduction_operation_p (stmt))
2784 {
2785 gimple res = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2786
2787 return res ? res :
2788 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt), lhs);
2789 }
2790
2791 return NULL;
2792 }
2793
2794 /* Detect commutative and associative scalar reductions starting at
2795 the STMT. Return the phi node of the reduction cycle, or NULL. */
2796
2797 static gimple
detect_commutative_reduction_arg(tree lhs,gimple stmt,tree arg,VEC (gimple,heap)** in,VEC (gimple,heap)** out)2798 detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg,
2799 VEC (gimple, heap) **in,
2800 VEC (gimple, heap) **out)
2801 {
2802 gimple phi = follow_ssa_with_commutative_ops (arg, lhs);
2803
2804 if (!phi)
2805 return NULL;
2806
2807 VEC_safe_push (gimple, heap, *in, stmt);
2808 VEC_safe_push (gimple, heap, *out, stmt);
2809 return phi;
2810 }
2811
2812 /* Detect commutative and associative scalar reductions starting at
2813 STMT. Return the phi node of the reduction cycle, or NULL. */
2814
2815 static gimple
detect_commutative_reduction_assign(gimple stmt,VEC (gimple,heap)** in,VEC (gimple,heap)** out)2816 detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in,
2817 VEC (gimple, heap) **out)
2818 {
2819 tree lhs = gimple_assign_lhs (stmt);
2820
2821 if (gimple_num_ops (stmt) == 2)
2822 return detect_commutative_reduction_arg (lhs, stmt,
2823 gimple_assign_rhs1 (stmt),
2824 in, out);
2825
2826 if (is_reduction_operation_p (stmt))
2827 {
2828 gimple res = detect_commutative_reduction_arg (lhs, stmt,
2829 gimple_assign_rhs1 (stmt),
2830 in, out);
2831 return res ? res
2832 : detect_commutative_reduction_arg (lhs, stmt,
2833 gimple_assign_rhs2 (stmt),
2834 in, out);
2835 }
2836
2837 return NULL;
2838 }
2839
2840 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2841
2842 static gimple
follow_inital_value_to_phi(tree arg,tree lhs)2843 follow_inital_value_to_phi (tree arg, tree lhs)
2844 {
2845 gimple stmt;
2846
2847 if (!arg || TREE_CODE (arg) != SSA_NAME)
2848 return NULL;
2849
2850 stmt = SSA_NAME_DEF_STMT (arg);
2851
2852 if (gimple_code (stmt) == GIMPLE_PHI
2853 && phi_contains_arg (stmt, lhs))
2854 return stmt;
2855
2856 return NULL;
2857 }
2858
2859
2860 /* Return the argument of the loop PHI that is the inital value coming
2861 from outside the loop. */
2862
2863 static edge
edge_initial_value_for_loop_phi(gimple phi)2864 edge_initial_value_for_loop_phi (gimple phi)
2865 {
2866 size_t i;
2867
2868 for (i = 0; i < gimple_phi_num_args (phi); i++)
2869 {
2870 edge e = gimple_phi_arg_edge (phi, i);
2871
2872 if (loop_depth (e->src->loop_father)
2873 < loop_depth (e->dest->loop_father))
2874 return e;
2875 }
2876
2877 return NULL;
2878 }
2879
2880 /* Return the argument of the loop PHI that is the inital value coming
2881 from outside the loop. */
2882
2883 static tree
initial_value_for_loop_phi(gimple phi)2884 initial_value_for_loop_phi (gimple phi)
2885 {
2886 size_t i;
2887
2888 for (i = 0; i < gimple_phi_num_args (phi); i++)
2889 {
2890 edge e = gimple_phi_arg_edge (phi, i);
2891
2892 if (loop_depth (e->src->loop_father)
2893 < loop_depth (e->dest->loop_father))
2894 return gimple_phi_arg_def (phi, i);
2895 }
2896
2897 return NULL_TREE;
2898 }
2899
2900 /* Returns true when DEF is used outside the reduction cycle of
2901 LOOP_PHI. */
2902
2903 static bool
used_outside_reduction(tree def,gimple loop_phi)2904 used_outside_reduction (tree def, gimple loop_phi)
2905 {
2906 use_operand_p use_p;
2907 imm_use_iterator imm_iter;
2908 loop_p loop = loop_containing_stmt (loop_phi);
2909
2910 /* In LOOP, DEF should be used only in LOOP_PHI. */
2911 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
2912 {
2913 gimple stmt = USE_STMT (use_p);
2914
2915 if (stmt != loop_phi
2916 && !is_gimple_debug (stmt)
2917 && flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
2918 return true;
2919 }
2920
2921 return false;
2922 }
2923
2924 /* Detect commutative and associative scalar reductions belonging to
2925 the SCOP starting at the loop closed phi node STMT. Return the phi
2926 node of the reduction cycle, or NULL. */
2927
2928 static gimple
detect_commutative_reduction(scop_p scop,gimple stmt,VEC (gimple,heap)** in,VEC (gimple,heap)** out)2929 detect_commutative_reduction (scop_p scop, gimple stmt, VEC (gimple, heap) **in,
2930 VEC (gimple, heap) **out)
2931 {
2932 if (scalar_close_phi_node_p (stmt))
2933 {
2934 gimple def, loop_phi, phi, close_phi = stmt;
2935 tree init, lhs, arg = gimple_phi_arg_def (close_phi, 0);
2936
2937 if (TREE_CODE (arg) != SSA_NAME)
2938 return NULL;
2939
2940 /* Note that loop close phi nodes should have a single argument
2941 because we translated the representation into a canonical form
2942 before Graphite: see canonicalize_loop_closed_ssa_form. */
2943 gcc_assert (gimple_phi_num_args (close_phi) == 1);
2944
2945 def = SSA_NAME_DEF_STMT (arg);
2946 if (!stmt_in_sese_p (def, SCOP_REGION (scop))
2947 || !(loop_phi = detect_commutative_reduction (scop, def, in, out)))
2948 return NULL;
2949
2950 lhs = gimple_phi_result (close_phi);
2951 init = initial_value_for_loop_phi (loop_phi);
2952 phi = follow_inital_value_to_phi (init, lhs);
2953
2954 if (phi && (used_outside_reduction (lhs, phi)
2955 || !has_single_use (gimple_phi_result (phi))))
2956 return NULL;
2957
2958 VEC_safe_push (gimple, heap, *in, loop_phi);
2959 VEC_safe_push (gimple, heap, *out, close_phi);
2960 return phi;
2961 }
2962
2963 if (gimple_code (stmt) == GIMPLE_ASSIGN)
2964 return detect_commutative_reduction_assign (stmt, in, out);
2965
2966 return NULL;
2967 }
2968
2969 /* Translate the scalar reduction statement STMT to an array RED
2970 knowing that its recursive phi node is LOOP_PHI. */
2971
2972 static void
translate_scalar_reduction_to_array_for_stmt(scop_p scop,tree red,gimple stmt,gimple loop_phi)2973 translate_scalar_reduction_to_array_for_stmt (scop_p scop, tree red,
2974 gimple stmt, gimple loop_phi)
2975 {
2976 tree res = gimple_phi_result (loop_phi);
2977 gimple assign = gimple_build_assign (res, unshare_expr (red));
2978 gimple_stmt_iterator gsi;
2979
2980 insert_stmts (scop, assign, NULL, gsi_after_labels (gimple_bb (loop_phi)));
2981
2982 assign = gimple_build_assign (unshare_expr (red), gimple_assign_lhs (stmt));
2983 gsi = gsi_for_stmt (stmt);
2984 gsi_next (&gsi);
2985 insert_stmts (scop, assign, NULL, gsi);
2986 }
2987
2988 /* Removes the PHI node and resets all the debug stmts that are using
2989 the PHI_RESULT. */
2990
2991 static void
remove_phi(gimple phi)2992 remove_phi (gimple phi)
2993 {
2994 imm_use_iterator imm_iter;
2995 tree def;
2996 use_operand_p use_p;
2997 gimple_stmt_iterator gsi;
2998 VEC (gimple, heap) *update = VEC_alloc (gimple, heap, 3);
2999 unsigned int i;
3000 gimple stmt;
3001
3002 def = PHI_RESULT (phi);
3003 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
3004 {
3005 stmt = USE_STMT (use_p);
3006
3007 if (is_gimple_debug (stmt))
3008 {
3009 gimple_debug_bind_reset_value (stmt);
3010 VEC_safe_push (gimple, heap, update, stmt);
3011 }
3012 }
3013
3014 FOR_EACH_VEC_ELT (gimple, update, i, stmt)
3015 update_stmt (stmt);
3016
3017 VEC_free (gimple, heap, update);
3018
3019 gsi = gsi_for_phi_node (phi);
3020 remove_phi_node (&gsi, false);
3021 }
3022
3023 /* Helper function for for_each_index. For each INDEX of the data
3024 reference REF, returns true when its indices are valid in the loop
3025 nest LOOP passed in as DATA. */
3026
3027 static bool
dr_indices_valid_in_loop(tree ref ATTRIBUTE_UNUSED,tree * index,void * data)3028 dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED, tree *index, void *data)
3029 {
3030 loop_p loop;
3031 basic_block header, def_bb;
3032 gimple stmt;
3033
3034 if (TREE_CODE (*index) != SSA_NAME)
3035 return true;
3036
3037 loop = *((loop_p *) data);
3038 header = loop->header;
3039 stmt = SSA_NAME_DEF_STMT (*index);
3040
3041 if (!stmt)
3042 return true;
3043
3044 def_bb = gimple_bb (stmt);
3045
3046 if (!def_bb)
3047 return true;
3048
3049 return dominated_by_p (CDI_DOMINATORS, header, def_bb);
3050 }
3051
3052 /* When the result of a CLOSE_PHI is written to a memory location,
3053 return a pointer to that memory reference, otherwise return
3054 NULL_TREE. */
3055
3056 static tree
close_phi_written_to_memory(gimple close_phi)3057 close_phi_written_to_memory (gimple close_phi)
3058 {
3059 imm_use_iterator imm_iter;
3060 use_operand_p use_p;
3061 gimple stmt;
3062 tree res, def = gimple_phi_result (close_phi);
3063
3064 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
3065 if ((stmt = USE_STMT (use_p))
3066 && gimple_code (stmt) == GIMPLE_ASSIGN
3067 && (res = gimple_assign_lhs (stmt)))
3068 {
3069 switch (TREE_CODE (res))
3070 {
3071 case VAR_DECL:
3072 case PARM_DECL:
3073 case RESULT_DECL:
3074 return res;
3075
3076 case ARRAY_REF:
3077 case MEM_REF:
3078 {
3079 tree arg = gimple_phi_arg_def (close_phi, 0);
3080 loop_p nest = loop_containing_stmt (SSA_NAME_DEF_STMT (arg));
3081
3082 /* FIXME: this restriction is for id-{24,25}.f and
3083 could be handled by duplicating the computation of
3084 array indices before the loop of the close_phi. */
3085 if (for_each_index (&res, dr_indices_valid_in_loop, &nest))
3086 return res;
3087 }
3088 /* Fallthru. */
3089
3090 default:
3091 continue;
3092 }
3093 }
3094 return NULL_TREE;
3095 }
3096
3097 /* Rewrite out of SSA the reduction described by the loop phi nodes
3098 IN, and the close phi nodes OUT. IN and OUT are structured by loop
3099 levels like this:
3100
3101 IN: stmt, loop_n, ..., loop_0
3102 OUT: stmt, close_n, ..., close_0
3103
3104 the first element is the reduction statement, and the next elements
3105 are the loop and close phi nodes of each of the outer loops. */
3106
3107 static void
translate_scalar_reduction_to_array(scop_p scop,VEC (gimple,heap)* in,VEC (gimple,heap)* out)3108 translate_scalar_reduction_to_array (scop_p scop,
3109 VEC (gimple, heap) *in,
3110 VEC (gimple, heap) *out)
3111 {
3112 gimple loop_phi;
3113 unsigned int i = VEC_length (gimple, out) - 1;
3114 tree red = close_phi_written_to_memory (VEC_index (gimple, out, i));
3115
3116 FOR_EACH_VEC_ELT (gimple, in, i, loop_phi)
3117 {
3118 gimple close_phi = VEC_index (gimple, out, i);
3119
3120 if (i == 0)
3121 {
3122 gimple stmt = loop_phi;
3123 basic_block bb = split_reduction_stmt (scop, stmt);
3124 poly_bb_p pbb = pbb_from_bb (bb);
3125 PBB_IS_REDUCTION (pbb) = true;
3126 gcc_assert (close_phi == loop_phi);
3127
3128 if (!red)
3129 red = create_zero_dim_array
3130 (gimple_assign_lhs (stmt), "Commutative_Associative_Reduction");
3131
3132 translate_scalar_reduction_to_array_for_stmt
3133 (scop, red, stmt, VEC_index (gimple, in, 1));
3134 continue;
3135 }
3136
3137 if (i == VEC_length (gimple, in) - 1)
3138 {
3139 insert_out_of_ssa_copy (scop, gimple_phi_result (close_phi),
3140 unshare_expr (red), close_phi);
3141 insert_out_of_ssa_copy_on_edge
3142 (scop, edge_initial_value_for_loop_phi (loop_phi),
3143 unshare_expr (red), initial_value_for_loop_phi (loop_phi));
3144 }
3145
3146 remove_phi (loop_phi);
3147 remove_phi (close_phi);
3148 }
3149 }
3150
3151 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3152 true when something has been changed. */
3153
3154 static bool
rewrite_commutative_reductions_out_of_ssa_close_phi(scop_p scop,gimple close_phi)3155 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop,
3156 gimple close_phi)
3157 {
3158 bool res;
3159 VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10);
3160 VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10);
3161
3162 detect_commutative_reduction (scop, close_phi, &in, &out);
3163 res = VEC_length (gimple, in) > 1;
3164 if (res)
3165 translate_scalar_reduction_to_array (scop, in, out);
3166
3167 VEC_free (gimple, heap, in);
3168 VEC_free (gimple, heap, out);
3169 return res;
3170 }
3171
3172 /* Rewrites all the commutative reductions from LOOP out of SSA.
3173 Returns true when something has been changed. */
3174
3175 static bool
rewrite_commutative_reductions_out_of_ssa_loop(scop_p scop,loop_p loop)3176 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop,
3177 loop_p loop)
3178 {
3179 gimple_stmt_iterator gsi;
3180 edge exit = single_exit (loop);
3181 tree res;
3182 bool changed = false;
3183
3184 if (!exit)
3185 return false;
3186
3187 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
3188 if ((res = gimple_phi_result (gsi_stmt (gsi)))
3189 && is_gimple_reg (res)
3190 && !scev_analyzable_p (res, SCOP_REGION (scop)))
3191 changed |= rewrite_commutative_reductions_out_of_ssa_close_phi
3192 (scop, gsi_stmt (gsi));
3193
3194 return changed;
3195 }
3196
3197 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3198
3199 static void
rewrite_commutative_reductions_out_of_ssa(scop_p scop)3200 rewrite_commutative_reductions_out_of_ssa (scop_p scop)
3201 {
3202 loop_iterator li;
3203 loop_p loop;
3204 bool changed = false;
3205 sese region = SCOP_REGION (scop);
3206
3207 FOR_EACH_LOOP (li, loop, 0)
3208 if (loop_in_sese_p (loop, region))
3209 changed |= rewrite_commutative_reductions_out_of_ssa_loop (scop, loop);
3210
3211 if (changed)
3212 {
3213 scev_reset_htab ();
3214 gsi_commit_edge_inserts ();
3215 update_ssa (TODO_update_ssa);
3216 #ifdef ENABLE_CHECKING
3217 verify_loop_closed_ssa (true);
3218 #endif
3219 }
3220 }
3221
3222 /* Can all ivs be represented by a signed integer?
3223 As CLooG might generate negative values in its expressions, signed loop ivs
3224 are required in the backend. */
3225
3226 static bool
scop_ivs_can_be_represented(scop_p scop)3227 scop_ivs_can_be_represented (scop_p scop)
3228 {
3229 loop_iterator li;
3230 loop_p loop;
3231 gimple_stmt_iterator psi;
3232 bool result = true;
3233
3234 FOR_EACH_LOOP (li, loop, 0)
3235 {
3236 if (!loop_in_sese_p (loop, SCOP_REGION (scop)))
3237 continue;
3238
3239 for (psi = gsi_start_phis (loop->header);
3240 !gsi_end_p (psi); gsi_next (&psi))
3241 {
3242 gimple phi = gsi_stmt (psi);
3243 tree res = PHI_RESULT (phi);
3244 tree type = TREE_TYPE (res);
3245
3246 if (TYPE_UNSIGNED (type)
3247 && TYPE_PRECISION (type) >= TYPE_PRECISION (long_long_integer_type_node))
3248 {
3249 result = false;
3250 break;
3251 }
3252 }
3253 if (!result)
3254 FOR_EACH_LOOP_BREAK (li);
3255 }
3256
3257 return result;
3258 }
3259
3260 /* Builds the polyhedral representation for a SESE region. */
3261
3262 void
build_poly_scop(scop_p scop)3263 build_poly_scop (scop_p scop)
3264 {
3265 sese region = SCOP_REGION (scop);
3266 graphite_dim_t max_dim;
3267
3268 build_scop_bbs (scop);
3269
3270 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3271 Once CLooG is fixed, remove this guard. Anyways, it makes no
3272 sense to optimize a scop containing only PBBs that do not belong
3273 to any loops. */
3274 if (nb_pbbs_in_loops (scop) == 0)
3275 return;
3276
3277 if (!scop_ivs_can_be_represented (scop))
3278 return;
3279
3280 if (flag_associative_math)
3281 rewrite_commutative_reductions_out_of_ssa (scop);
3282
3283 build_sese_loop_nests (region);
3284 build_sese_conditions (region);
3285 find_scop_parameters (scop);
3286
3287 max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
3288 if (scop_nb_params (scop) > max_dim)
3289 return;
3290
3291 build_scop_iteration_domain (scop);
3292 build_scop_context (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);
3303 scop_to_lst (scop);
3304 build_scop_scattering (scop);
3305
3306 /* This SCoP has been translated to the polyhedral
3307 representation. */
3308 POLY_SCOP_P (scop) = true;
3309 }
3310 #endif
3311