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