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