Line data Source code
1 : /* Detection of Static Control Parts (SCoP) for Graphite.
2 : Copyright (C) 2009-2026 Free Software Foundation, Inc.
3 : Contributed by Sebastian Pop <sebastian.pop@amd.com> and
4 : Tobias Grosser <grosser@fim.uni-passau.de>.
5 :
6 : This file is part of GCC.
7 :
8 : GCC is free software; you can redistribute it and/or modify
9 : it under the terms of the GNU General Public License as published by
10 : the Free Software Foundation; either version 3, or (at your option)
11 : any later version.
12 :
13 : GCC is distributed in the hope that it will be useful,
14 : but WITHOUT ANY WARRANTY; without even the implied warranty of
15 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 : GNU General Public License for more details.
17 :
18 : You should have received a copy of the GNU General Public License
19 : along with GCC; see the file COPYING3. If not see
20 : <http://www.gnu.org/licenses/>. */
21 :
22 : #define INCLUDE_ISL
23 :
24 : #include "config.h"
25 :
26 : #ifdef HAVE_isl
27 :
28 : #include "system.h"
29 : #include "coretypes.h"
30 : #include "backend.h"
31 : #include "cfghooks.h"
32 : #include "domwalk.h"
33 : #include "tree.h"
34 : #include "gimple.h"
35 : #include "ssa.h"
36 : #include "fold-const.h"
37 : #include "gimple-iterator.h"
38 : #include "tree-cfg.h"
39 : #include "tree-ssa-loop-manip.h"
40 : #include "tree-ssa-loop-niter.h"
41 : #include "tree-ssa-loop.h"
42 : #include "tree-into-ssa.h"
43 : #include "tree-ssa.h"
44 : #include "cfgloop.h"
45 : #include "tree-data-ref.h"
46 : #include "tree-scalar-evolution.h"
47 : #include "tree-pass.h"
48 : #include "tree-ssa-propagate.h"
49 : #include "gimple-pretty-print.h"
50 : #include "cfganal.h"
51 : #include "graphite.h"
52 :
53 : class debug_printer
54 : {
55 : private:
56 : FILE *dump_file;
57 :
58 : public:
59 : void
60 190 : set_dump_file (FILE *f)
61 : {
62 190 : gcc_assert (f);
63 190 : dump_file = f;
64 190 : }
65 :
66 : friend debug_printer &
67 2559 : operator<< (debug_printer &output, int i)
68 : {
69 0 : fprintf (output.dump_file, "%d", i);
70 189 : return output;
71 : }
72 :
73 : friend debug_printer &
74 8699 : operator<< (debug_printer &output, const char *s)
75 : {
76 8699 : fprintf (output.dump_file, "%s", s);
77 2971 : return output;
78 : }
79 :
80 : friend debug_printer &
81 : operator<< (debug_printer &output, gimple* stmt)
82 : {
83 : print_gimple_stmt (output.dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS);
84 : return output;
85 : }
86 :
87 : friend debug_printer &
88 49 : operator<< (debug_printer &output, tree t)
89 : {
90 49 : print_generic_expr (output.dump_file, t, TDF_SLIM);
91 49 : return output;
92 : }
93 : } dp;
94 :
95 : #define DEBUG_PRINT(args) do \
96 : { \
97 : if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \
98 : } while (0)
99 :
100 : /* Pretty print to FILE all the SCoPs in DOT format and mark them with
101 : different colors. If there are not enough colors, paint the
102 : remaining SCoPs in gray.
103 :
104 : Special nodes:
105 : - "*" after the node number denotes the entry of a SCoP,
106 : - "#" after the node number denotes the exit of a SCoP,
107 : - "()" around the node number denotes the entry or the
108 : exit nodes of the SCOP. These are not part of SCoP. */
109 :
110 : DEBUG_FUNCTION void
111 0 : dot_all_sese (FILE *file, vec<sese_l>& scops)
112 : {
113 : /* Disable debugging while printing graph. */
114 0 : dump_flags_t tmp_dump_flags = dump_flags;
115 0 : dump_flags = TDF_NONE;
116 :
117 0 : fprintf (file, "digraph all {\n");
118 :
119 0 : basic_block bb;
120 0 : FOR_ALL_BB_FN (bb, cfun)
121 : {
122 0 : int part_of_scop = false;
123 :
124 : /* Use HTML for every bb label. So we are able to print bbs
125 : which are part of two different SCoPs, with two different
126 : background colors. */
127 0 : fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
128 : bb->index);
129 0 : fprintf (file, "CELLSPACING=\"0\">\n");
130 :
131 : /* Select color for SCoP. */
132 0 : sese_l *region;
133 0 : int i;
134 0 : FOR_EACH_VEC_ELT (scops, i, region)
135 : {
136 0 : bool sese_in_region = bb_in_sese_p (bb, *region);
137 0 : if (sese_in_region || (region->exit->dest == bb)
138 0 : || (region->entry->dest == bb))
139 : {
140 0 : const char *color;
141 0 : switch (i % 17)
142 : {
143 : case 0: /* red */
144 : color = "#e41a1c";
145 : break;
146 0 : case 1: /* blue */
147 0 : color = "#377eb8";
148 0 : break;
149 0 : case 2: /* green */
150 0 : color = "#4daf4a";
151 0 : break;
152 0 : case 3: /* purple */
153 0 : color = "#984ea3";
154 0 : break;
155 0 : case 4: /* orange */
156 0 : color = "#ff7f00";
157 0 : break;
158 0 : case 5: /* yellow */
159 0 : color = "#ffff33";
160 0 : break;
161 0 : case 6: /* brown */
162 0 : color = "#a65628";
163 0 : break;
164 0 : case 7: /* rose */
165 0 : color = "#f781bf";
166 0 : break;
167 0 : case 8:
168 0 : color = "#8dd3c7";
169 0 : break;
170 0 : case 9:
171 0 : color = "#ffffb3";
172 0 : break;
173 0 : case 10:
174 0 : color = "#bebada";
175 0 : break;
176 0 : case 11:
177 0 : color = "#fb8072";
178 0 : break;
179 0 : case 12:
180 0 : color = "#80b1d3";
181 0 : break;
182 0 : case 13:
183 0 : color = "#fdb462";
184 0 : break;
185 0 : case 14:
186 0 : color = "#b3de69";
187 0 : break;
188 0 : case 15:
189 0 : color = "#fccde5";
190 0 : break;
191 0 : case 16:
192 0 : color = "#bc80bd";
193 0 : break;
194 : default: /* gray */
195 : color = "#999999";
196 : }
197 :
198 0 : fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
199 : color);
200 :
201 0 : if (!sese_in_region)
202 0 : fprintf (file, " (");
203 :
204 0 : if (bb == region->entry->dest && bb == region->exit->dest)
205 0 : fprintf (file, " %d*# ", bb->index);
206 0 : else if (bb == region->entry->dest)
207 0 : fprintf (file, " %d* ", bb->index);
208 0 : else if (bb == region->exit->dest)
209 0 : fprintf (file, " %d# ", bb->index);
210 : else
211 0 : fprintf (file, " %d ", bb->index);
212 :
213 0 : fprintf (file, "{lp_%d}", bb->loop_father->num);
214 :
215 0 : if (!sese_in_region)
216 0 : fprintf (file, ")");
217 :
218 0 : fprintf (file, "</TD></TR>\n");
219 0 : part_of_scop = true;
220 : }
221 : }
222 :
223 0 : if (!part_of_scop)
224 : {
225 0 : fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
226 0 : fprintf (file, " %d {lp_%d} </TD></TR>\n", bb->index,
227 0 : bb->loop_father->num);
228 : }
229 0 : fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
230 : }
231 :
232 0 : FOR_ALL_BB_FN (bb, cfun)
233 : {
234 0 : edge e;
235 0 : edge_iterator ei;
236 0 : FOR_EACH_EDGE (e, ei, bb->succs)
237 0 : fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
238 : }
239 :
240 0 : fputs ("}\n\n", file);
241 :
242 : /* Enable debugging again. */
243 0 : dump_flags = tmp_dump_flags;
244 0 : }
245 :
246 : /* Display SCoP on stderr. */
247 :
248 : DEBUG_FUNCTION void
249 0 : dot_sese (sese_l& scop)
250 : {
251 0 : vec<sese_l> scops;
252 0 : scops.create (1);
253 :
254 0 : if (scop)
255 0 : scops.safe_push (scop);
256 :
257 0 : dot_all_sese (stderr, scops);
258 :
259 0 : scops.release ();
260 0 : }
261 :
262 : DEBUG_FUNCTION void
263 0 : dot_cfg ()
264 : {
265 0 : vec<sese_l> scops;
266 0 : scops.create (1);
267 0 : dot_all_sese (stderr, scops);
268 0 : scops.release ();
269 0 : }
270 :
271 : /* Returns a COND_EXPR statement when BB has a single predecessor, the
272 : edge between BB and its predecessor is not a loop exit edge, and
273 : the last statement of the single predecessor is a COND_EXPR. */
274 :
275 : static gcond *
276 4342 : single_pred_cond_non_loop_exit (basic_block bb)
277 : {
278 4342 : if (single_pred_p (bb))
279 : {
280 3112 : basic_block pred = single_pred (bb);
281 :
282 8508 : if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
283 : return NULL;
284 :
285 5976 : return safe_dyn_cast <gcond *> (*gsi_last_bb (pred));
286 : }
287 :
288 : return NULL;
289 : }
290 :
291 : namespace
292 : {
293 :
294 : /* Build the maximal scop containing LOOPs and add it to SCOPS. */
295 :
296 : class scop_detection
297 : {
298 : public:
299 556 : scop_detection () : scops (vNULL) {}
300 :
301 556 : ~scop_detection ()
302 : {
303 556 : scops.release ();
304 556 : }
305 :
306 : /* A marker for invalid sese_l. */
307 : static sese_l invalid_sese;
308 :
309 : /* Return the SCOPS in this SCOP_DETECTION. */
310 :
311 : vec<sese_l>
312 556 : get_scops ()
313 : {
314 556 : return scops;
315 : }
316 :
317 : /* Return an sese_l around the LOOP. */
318 :
319 : sese_l get_sese (loop_p loop);
320 :
321 : /* Merge scops at same loop depth and returns the new sese.
322 : Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
323 :
324 : sese_l merge_sese (sese_l first, sese_l second) const;
325 :
326 : /* Build scop outer->inner if possible. */
327 :
328 : void build_scop_depth (loop_p loop);
329 :
330 : /* Return true when BEGIN is the preheader edge of a loop with a single exit
331 : END. */
332 :
333 : static bool region_has_one_loop (sese_l s);
334 :
335 : /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
336 :
337 : void add_scop (sese_l s);
338 :
339 : /* Returns true if S1 subsumes/surrounds S2. */
340 : static bool subsumes (sese_l s1, sese_l s2);
341 :
342 : /* Remove a SCoP which is subsumed by S1. */
343 : void remove_subscops (sese_l s1);
344 :
345 : /* Returns true if S1 intersects with S2. Since we already know that S1 does
346 : not subsume S2 or vice-versa, we only check for entry bbs. */
347 :
348 : static bool intersects (sese_l s1, sese_l s2);
349 :
350 : /* Remove one of the scops when it intersects with any other. */
351 :
352 : void remove_intersecting_scops (sese_l s1);
353 :
354 : /* Return true when a statement in SCOP cannot be represented by Graphite. */
355 :
356 : bool harmful_loop_in_region (sese_l scop) const;
357 :
358 : /* Return true only when STMT is simple enough for being handled by Graphite.
359 : This depends on SCOP, as the parameters are initialized relatively to
360 : this basic block, the linear functions are initialized based on the
361 : outermost loop containing STMT inside the SCOP. BB is the place where we
362 : try to evaluate the STMT. */
363 :
364 : bool stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
365 : basic_block bb) const;
366 :
367 : /* Something like "n * m" is not allowed. */
368 :
369 : static bool graphite_can_represent_init (tree e);
370 :
371 : /* Return true when SCEV can be represented in the polyhedral model.
372 :
373 : An expression can be represented, if it can be expressed as an
374 : affine expression. For loops (i, j) and parameters (m, n) all
375 : affine expressions are of the form:
376 :
377 : x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
378 :
379 : 1 i + 20 j + (-2) m + 25
380 :
381 : Something like "i * n" or "n * m" is not allowed. */
382 :
383 : static bool graphite_can_represent_scev (sese_l scop, tree scev);
384 :
385 : /* Return true when EXPR can be represented in the polyhedral model.
386 :
387 : This means an expression can be represented, if it is linear with respect
388 : to the loops and the strides are non parametric. LOOP is the place where
389 : the expr will be evaluated. SCOP defines the region we analyse. */
390 :
391 : static bool graphite_can_represent_expr (sese_l scop, loop_p loop,
392 : tree expr);
393 :
394 : /* Return true if the data references of STMT can be represented by Graphite.
395 : We try to analyze the data references in a loop contained in the SCOP. */
396 :
397 : static bool stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt);
398 :
399 : /* Remove the close phi node at GSI and replace its rhs with the rhs
400 : of PHI. */
401 :
402 : static void remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi);
403 :
404 : /* Returns true when Graphite can represent LOOP in SCOP.
405 : FIXME: For the moment, graphite cannot be used on loops that iterate using
406 : induction variables that wrap. */
407 :
408 : static bool can_represent_loop (loop_p loop, sese_l scop);
409 :
410 : /* Returns the number of pbbs that are in loops contained in SCOP. */
411 :
412 : static int nb_pbbs_in_loops (scop_p scop);
413 :
414 : private:
415 : vec<sese_l> scops;
416 : };
417 :
418 : sese_l scop_detection::invalid_sese (NULL, NULL);
419 :
420 : /* Return an sese_l around the LOOP. */
421 :
422 : sese_l
423 1104 : scop_detection::get_sese (loop_p loop)
424 : {
425 1104 : if (!loop)
426 0 : return invalid_sese;
427 :
428 1104 : edge scop_begin = loop_preheader_edge (loop);
429 1104 : edge scop_end = single_exit (loop);
430 1104 : if (!scop_end || (scop_end->flags & (EDGE_COMPLEX|EDGE_FAKE)))
431 214 : return invalid_sese;
432 :
433 890 : return sese_l (scop_begin, scop_end);
434 : }
435 :
436 : /* Merge scops at same loop depth and returns the new sese.
437 : Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
438 :
439 : sese_l
440 139 : scop_detection::merge_sese (sese_l first, sese_l second) const
441 : {
442 : /* In the trivial case first/second may be NULL. */
443 139 : if (!first)
444 0 : return second;
445 139 : if (!second)
446 0 : return first;
447 :
448 139 : DEBUG_PRINT (dp << "[scop-detection] try merging sese s1: ";
449 : print_sese (dump_file, first);
450 : dp << "[scop-detection] try merging sese s2: ";
451 : print_sese (dump_file, second));
452 :
453 139 : auto_bitmap worklist, in_sese_region;
454 139 : bitmap_set_bit (worklist, get_entry_bb (first)->index);
455 139 : bitmap_set_bit (worklist, get_exit_bb (first)->index);
456 139 : bitmap_set_bit (worklist, get_entry_bb (second)->index);
457 139 : bitmap_set_bit (worklist, get_exit_bb (second)->index);
458 139 : edge entry = NULL, exit = NULL;
459 :
460 : /* We can optimize the case of adding a loop entry dest or exit
461 : src to the worklist (for single-exit loops) by skipping
462 : directly to the exit dest / entry src. in_sese_region
463 : doesn't have to cover all blocks in the region but merely
464 : its border it acts more like a visited bitmap. */
465 1733 : do
466 : {
467 1733 : int index = bitmap_clear_first_set_bit (worklist);
468 1733 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, index);
469 1733 : edge_iterator ei;
470 1733 : edge e;
471 :
472 : /* With fake exit edges we can end up with no possible exit. */
473 1733 : if (index == EXIT_BLOCK)
474 : {
475 2 : DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
476 2 : return invalid_sese;
477 : }
478 :
479 1731 : bitmap_set_bit (in_sese_region, bb->index);
480 :
481 1731 : basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
482 4004 : FOR_EACH_EDGE (e, ei, bb->preds)
483 2273 : if (e->src == dom
484 2273 : && (! entry
485 1544 : || dominated_by_p (CDI_DOMINATORS, entry->dest, bb)))
486 : {
487 177 : if (entry
488 177 : && ! bitmap_bit_p (in_sese_region, entry->src->index))
489 29 : bitmap_set_bit (worklist, entry->src->index);
490 : entry = e;
491 : }
492 2096 : else if (! bitmap_bit_p (in_sese_region, e->src->index))
493 897 : bitmap_set_bit (worklist, e->src->index);
494 :
495 1731 : basic_block pdom = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
496 4004 : FOR_EACH_EDGE (e, ei, bb->succs)
497 2273 : if (e->dest == pdom
498 2273 : && (! exit
499 1531 : || dominated_by_p (CDI_POST_DOMINATORS, exit->src, bb)))
500 : {
501 332 : if (exit
502 332 : && ! bitmap_bit_p (in_sese_region, exit->dest->index))
503 171 : bitmap_set_bit (worklist, exit->dest->index);
504 : exit = e;
505 : }
506 1941 : else if (! bitmap_bit_p (in_sese_region, e->dest->index))
507 1019 : bitmap_set_bit (worklist, e->dest->index);
508 : }
509 1731 : while (! bitmap_empty_p (worklist));
510 :
511 137 : sese_l combined (entry, exit);
512 :
513 137 : DEBUG_PRINT (dp << "[merged-sese] s1: "; print_sese (dump_file, combined));
514 :
515 137 : return combined;
516 139 : }
517 :
518 : /* Print the loop numbers of the loops contained in SESE to FILE. */
519 :
520 : static void
521 178 : print_sese_loop_numbers (FILE *file, sese_l sese)
522 : {
523 178 : bool first_loop = true;
524 397 : for (loop_p nest = sese.entry->dest->loop_father; nest; nest = nest->next)
525 : {
526 248 : if (!loop_in_sese_p (nest, sese))
527 : break;
528 :
529 1084 : for (auto loop : loops_list (cfun, LI_INCLUDE_ROOT, nest))
530 : {
531 427 : gcc_assert (loop_in_sese_p (loop, sese));
532 :
533 677 : fprintf (file, "%s%d", first_loop ? "" : ", ", loop->num);
534 427 : first_loop = false;
535 219 : }
536 : }
537 178 : }
538 :
539 : /* Build scop outer->inner if possible. */
540 :
541 : void
542 1183 : scop_detection::build_scop_depth (loop_p loop)
543 : {
544 1183 : sese_l s = invalid_sese;
545 1183 : loop = loop->inner;
546 2287 : while (loop)
547 : {
548 1104 : sese_l next = get_sese (loop);
549 1104 : if (! next
550 890 : || harmful_loop_in_region (next))
551 : {
552 627 : if (next)
553 413 : DEBUG_PRINT (dp << "[scop-detection] Discarding SCoP on loops ";
554 : print_sese_loop_numbers (dump_file, next);
555 : dp << " because of harmful loops\n");
556 627 : if (s)
557 56 : add_scop (s);
558 627 : build_scop_depth (loop);
559 627 : s = invalid_sese;
560 : }
561 477 : else if (! s)
562 : s = next;
563 : else
564 : {
565 139 : sese_l combined = merge_sese (s, next);
566 139 : if (! combined
567 137 : || harmful_loop_in_region (combined))
568 : {
569 59 : add_scop (s);
570 59 : s = next;
571 : }
572 : else
573 : s = combined;
574 : }
575 1104 : loop = loop->next;
576 : }
577 1183 : if (s)
578 282 : add_scop (s);
579 1183 : }
580 :
581 : /* Returns true when Graphite can represent LOOP in SCOP.
582 : FIXME: For the moment, graphite cannot be used on loops that iterate using
583 : induction variables that wrap. */
584 :
585 : bool
586 1119 : scop_detection::can_represent_loop (loop_p loop, sese_l scop)
587 : {
588 1119 : tree niter;
589 1119 : struct tree_niter_desc niter_desc;
590 :
591 : /* We can only handle do {} while () style loops correctly. */
592 1119 : edge exit = single_exit (loop);
593 1119 : if (!exit
594 1118 : || !single_pred_p (loop->latch)
595 1118 : || exit->src != single_pred (loop->latch)
596 2232 : || !empty_block_p (loop->latch))
597 : {
598 23 : DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop shape unsupported.\n");
599 23 : return false;
600 : }
601 :
602 1096 : bool edge_irreducible = (loop_preheader_edge (loop)->flags
603 1096 : & EDGE_IRREDUCIBLE_LOOP);
604 1096 : if (edge_irreducible)
605 : {
606 1 : DEBUG_PRINT (dp << "[can_represent_loop-fail] "
607 : "Loop is not a natural loop.\n");
608 1 : return false;
609 : }
610 :
611 1095 : bool niter_is_unconditional = number_of_iterations_exit (loop,
612 : single_exit (loop),
613 : &niter_desc, false);
614 :
615 1095 : if (!niter_is_unconditional)
616 : {
617 5 : DEBUG_PRINT (dp << "[can_represent_loop-fail] "
618 : "Loop niter not unconditional.\n"
619 : "Condition: " << niter_desc.assumptions << "\n");
620 5 : return false;
621 : }
622 :
623 1090 : niter = number_of_latch_executions (loop);
624 1090 : if (!niter)
625 : {
626 0 : DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop niter unknown.\n");
627 0 : return false;
628 : }
629 1090 : if (!niter_desc.control.no_overflow)
630 : {
631 1 : DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop niter can overflow.\n");
632 1 : return false;
633 : }
634 :
635 1089 : bool undetermined_coefficients = chrec_contains_undetermined (niter);
636 1089 : if (undetermined_coefficients)
637 : {
638 0 : DEBUG_PRINT (dp << "[can_represent_loop-fail] "
639 : "Loop niter chrec contains undetermined "
640 : "coefficients.\n");
641 0 : return false;
642 : }
643 :
644 1089 : bool can_represent_expr = graphite_can_represent_expr (scop, loop, niter);
645 1089 : if (!can_represent_expr)
646 : {
647 9 : DEBUG_PRINT (dp << "[can_represent_loop-fail] "
648 : << "Loop niter expression cannot be represented: "
649 : << niter << "\n");
650 9 : return false;
651 : }
652 :
653 : return true;
654 1119 : }
655 :
656 : /* Return true when BEGIN is the preheader edge of a loop with a single exit
657 : END. */
658 :
659 : bool
660 397 : scop_detection::region_has_one_loop (sese_l s)
661 : {
662 397 : edge begin = s.entry;
663 397 : edge end = s.exit;
664 : /* Check for a single perfectly nested loop. */
665 397 : if (begin->dest->loop_father->inner)
666 : return false;
667 :
668 : /* Otherwise, check whether we have adjacent loops. */
669 228 : return (single_pred_p (end->src)
670 228 : && begin->dest->loop_father == single_pred (end->src)->loop_father);
671 : }
672 :
673 : /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
674 :
675 : void
676 397 : scop_detection::add_scop (sese_l s)
677 : {
678 397 : gcc_assert (s);
679 :
680 : /* If the exit edge is fake discard the SCoP for now as we're removing the
681 : fake edges again after analysis. */
682 397 : if (s.exit->flags & EDGE_FAKE)
683 : {
684 0 : DEBUG_PRINT (dp << "[scop-detection-fail] Discarding infinite loop SCoP: ";
685 : print_sese (dump_file, s));
686 0 : return;
687 : }
688 :
689 : /* Include the BB with the loop-closed SSA PHI nodes, we need this
690 : block in the region for code-generating out-of-SSA copies.
691 : canonicalize_loop_closed_ssa makes sure that is in proper shape. */
692 397 : if (s.exit->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
693 397 : && loop_exit_edge_p (s.exit->src->loop_father, s.exit))
694 : {
695 396 : gcc_assert (single_pred_p (s.exit->dest)
696 : && single_succ_p (s.exit->dest)
697 : && sese_trivially_empty_bb_p (s.exit->dest));
698 396 : s.exit = single_succ_edge (s.exit->dest);
699 : }
700 :
701 : /* Do not add scops with only one loop. */
702 397 : if (region_has_one_loop (s))
703 : {
704 186 : DEBUG_PRINT (dp << "[scop-detection-fail] Discarding one loop SCoP: ";
705 : print_sese (dump_file, s));
706 186 : return;
707 : }
708 :
709 211 : if (get_exit_bb (s) == EXIT_BLOCK_PTR_FOR_FN (cfun))
710 : {
711 0 : DEBUG_PRINT (dp << "[scop-detection-fail] "
712 : << "Discarding SCoP exiting to return: ";
713 : print_sese (dump_file, s));
714 0 : return;
715 : }
716 :
717 : /* Remove all the scops which are subsumed by s. */
718 211 : remove_subscops (s);
719 :
720 : /* Remove intersecting scops. FIXME: It will be a good idea to keep
721 : the non-intersecting part of the scop already in the list. */
722 211 : remove_intersecting_scops (s);
723 :
724 211 : scops.safe_push (s);
725 211 : DEBUG_PRINT (dp << "[scop-detection] Adding SCoP: "; print_sese (dump_file, s));
726 :
727 211 : if (dump_file && dump_flags & TDF_DETAILS)
728 : {
729 102 : fprintf (dump_file, "Loops in SCoP: ");
730 102 : print_sese_loop_numbers (dump_file, s);
731 102 : fprintf (dump_file, "\n");
732 : }
733 : }
734 :
735 : /* Return true when a statement in SCOP cannot be represented by Graphite. */
736 :
737 : bool
738 1027 : scop_detection::harmful_loop_in_region (sese_l scop) const
739 : {
740 1027 : basic_block exit_bb = get_exit_bb (scop);
741 1027 : basic_block entry_bb = get_entry_bb (scop);
742 :
743 1027 : DEBUG_PRINT (dp << "[checking-harmful-bbs] ";
744 : print_sese (dump_file, scop));
745 1027 : gcc_assert (dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb));
746 :
747 1027 : auto_vec<basic_block> worklist;
748 1027 : auto_bitmap loops;
749 :
750 1027 : worklist.safe_push (entry_bb);
751 6059 : while (! worklist.is_empty ())
752 : {
753 4353 : basic_block bb = worklist.pop ();
754 4353 : DEBUG_PRINT (dp << "Visiting bb_" << bb->index << "\n");
755 :
756 : /* The basic block should not be part of an irreducible loop. */
757 4353 : if (bb->flags & BB_IRREDUCIBLE_LOOP)
758 : {
759 2 : DEBUG_PRINT (dp << "[scop-detection-fail] Found bb in irreducible "
760 : "loop.\n");
761 :
762 2 : return true;
763 : }
764 :
765 : /* Check for unstructured control flow: CFG not generated by structured
766 : if-then-else. */
767 4351 : if (bb->succs->length () > 1)
768 : {
769 1745 : edge e;
770 1745 : edge_iterator ei;
771 5252 : FOR_EACH_EDGE (e, ei, bb->succs)
772 3510 : if (!dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)
773 3510 : && !dominated_by_p (CDI_DOMINATORS, e->dest, bb))
774 : {
775 3 : DEBUG_PRINT (dp << "[scop-detection-fail] Found unstructured "
776 : "control flow.\n");
777 3 : return true;
778 : }
779 : }
780 :
781 : /* Collect all loops in the current region. */
782 4348 : loop_p loop = bb->loop_father;
783 4348 : if (loop_in_sese_p (loop, scop))
784 3983 : bitmap_set_bit (loops, loop->num);
785 :
786 : /* Check for harmful statements in basic blocks part of the region. */
787 8696 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
788 14763 : !gsi_end_p (gsi); gsi_next (&gsi))
789 10758 : if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb))
790 : {
791 343 : DEBUG_PRINT (dp << "[scop-detection-fail] "
792 : "Found harmful statement.\n");
793 343 : return true;
794 : }
795 :
796 4005 : for (basic_block dom = first_dom_son (CDI_DOMINATORS, bb);
797 8201 : dom;
798 4196 : dom = next_dom_son (CDI_DOMINATORS, dom))
799 4196 : if (dom != scop.exit->dest)
800 3493 : worklist.safe_push (dom);
801 : }
802 :
803 : /* Go through all loops and check that they are still valid in the combined
804 : scop. */
805 679 : unsigned j;
806 679 : bitmap_iterator bi;
807 1689 : EXECUTE_IF_SET_IN_BITMAP (loops, 0, j, bi)
808 : {
809 1132 : loop_p loop = (*current_loops->larray)[j];
810 1132 : gcc_assert (loop->num == (int) j);
811 :
812 : /* Check if the loop nests are to be optimized for speed. */
813 1132 : if (! loop->inner
814 1132 : && ! optimize_loop_for_speed_p (loop))
815 : {
816 13 : DEBUG_PRINT (dp << "[scop-detection-fail] loop_"
817 : << loop->num << " is not on a hot path.\n");
818 13 : return true;
819 : }
820 :
821 1119 : if (! can_represent_loop (loop, scop))
822 : {
823 39 : DEBUG_PRINT (dp << "[scop-detection-fail] cannot represent loop_"
824 : << loop->num << "\n");
825 39 : return true;
826 : }
827 :
828 : /* Check if all loop nests have at least one data reference.
829 : ??? This check is expensive and loops premature at this point.
830 : If important to retain we can pre-compute this for all innermost
831 : loops and reject those when we build a SESE region for a loop
832 : during SESE discovery. */
833 1080 : if (! loop->inner
834 1080 : && ! loop_nest_has_data_refs (loop))
835 : {
836 70 : DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
837 : << " does not have any data reference.\n");
838 70 : return true;
839 : }
840 1491 : DEBUG_PRINT (dp << "[scop-detection] loop_" << loop->num << " is harmless.\n");
841 : }
842 :
843 : return false;
844 1027 : }
845 :
846 : /* Returns true if S1 subsumes/surrounds S2. */
847 : bool
848 18 : scop_detection::subsumes (sese_l s1, sese_l s2)
849 : {
850 18 : if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
851 18 : get_entry_bb (s1))
852 18 : && dominated_by_p (CDI_POST_DOMINATORS, s2.exit->dest,
853 0 : s1.exit->dest))
854 : return true;
855 : return false;
856 : }
857 :
858 : /* Remove a SCoP which is subsumed by S1. */
859 : void
860 211 : scop_detection::remove_subscops (sese_l s1)
861 : {
862 211 : int j;
863 211 : sese_l *s2;
864 244 : FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
865 : {
866 18 : if (subsumes (s1, *s2))
867 : {
868 0 : DEBUG_PRINT (dp << "Removing sub-SCoP";
869 : print_sese (dump_file, *s2));
870 0 : scops.unordered_remove (j);
871 : }
872 : }
873 211 : }
874 :
875 : /* Returns true if S1 intersects with S2. Since we already know that S1 does
876 : not subsume S2 or vice-versa, we only check for entry bbs. */
877 :
878 : bool
879 18 : scop_detection::intersects (sese_l s1, sese_l s2)
880 : {
881 18 : if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
882 18 : get_entry_bb (s1))
883 18 : && !dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
884 0 : get_exit_bb (s1)))
885 : return true;
886 18 : if ((s1.exit == s2.entry) || (s2.exit == s1.entry))
887 : return true;
888 :
889 : return false;
890 : }
891 :
892 : /* Remove one of the scops when it intersects with any other. */
893 :
894 : void
895 211 : scop_detection::remove_intersecting_scops (sese_l s1)
896 : {
897 211 : int j;
898 211 : sese_l *s2;
899 244 : FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
900 : {
901 18 : if (intersects (s1, *s2))
902 : {
903 0 : DEBUG_PRINT (dp << "Removing intersecting SCoP";
904 : print_sese (dump_file, *s2);
905 : dp << "Intersects with:";
906 : print_sese (dump_file, s1));
907 0 : scops.unordered_remove (j);
908 : }
909 : }
910 211 : }
911 :
912 : /* Something like "n * m" is not allowed. */
913 :
914 : bool
915 13124 : scop_detection::graphite_can_represent_init (tree e)
916 : {
917 13326 : switch (TREE_CODE (e))
918 : {
919 4261 : case POLYNOMIAL_CHREC:
920 4261 : return graphite_can_represent_init (CHREC_LEFT (e))
921 8505 : && graphite_can_represent_init (CHREC_RIGHT (e));
922 :
923 43 : case MULT_EXPR:
924 43 : if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
925 43 : return graphite_can_represent_init (TREE_OPERAND (e, 0))
926 43 : && tree_fits_shwi_p (TREE_OPERAND (e, 1));
927 : else
928 0 : return graphite_can_represent_init (TREE_OPERAND (e, 1))
929 0 : && tree_fits_shwi_p (TREE_OPERAND (e, 0));
930 :
931 402 : case PLUS_EXPR:
932 402 : case POINTER_PLUS_EXPR:
933 402 : case MINUS_EXPR:
934 402 : return graphite_can_represent_init (TREE_OPERAND (e, 0))
935 402 : && graphite_can_represent_init (TREE_OPERAND (e, 1));
936 :
937 202 : case NEGATE_EXPR:
938 202 : case BIT_NOT_EXPR:
939 202 : CASE_CONVERT:
940 202 : case NON_LVALUE_EXPR:
941 202 : return graphite_can_represent_init (TREE_OPERAND (e, 0));
942 :
943 : default:
944 : break;
945 : }
946 :
947 : return true;
948 : }
949 :
950 : /* Return true when SCEV can be represented in the polyhedral model.
951 :
952 : An expression can be represented, if it can be expressed as an
953 : affine expression. For loops (i, j) and parameters (m, n) all
954 : affine expressions are of the form:
955 :
956 : x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
957 :
958 : 1 i + 20 j + (-2) m + 25
959 :
960 : Something like "i * n" or "n * m" is not allowed. */
961 :
962 : bool
963 8007 : scop_detection::graphite_can_represent_scev (sese_l scop, tree scev)
964 : {
965 12256 : if (chrec_contains_undetermined (scev))
966 : return false;
967 :
968 12103 : switch (TREE_CODE (scev))
969 : {
970 483 : case NEGATE_EXPR:
971 483 : case BIT_NOT_EXPR:
972 483 : CASE_CONVERT:
973 483 : case NON_LVALUE_EXPR:
974 483 : return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0));
975 :
976 592 : case PLUS_EXPR:
977 592 : case POINTER_PLUS_EXPR:
978 592 : case MINUS_EXPR:
979 592 : return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
980 592 : && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
981 :
982 27 : case MULT_EXPR:
983 43 : return !CONVERT_EXPR_P (TREE_OPERAND (scev, 0))
984 16 : && !CONVERT_EXPR_P (TREE_OPERAND (scev, 1))
985 32 : && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
986 16 : && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
987 16 : && graphite_can_represent_init (scev)
988 16 : && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
989 43 : && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
990 :
991 3846 : case POLYNOMIAL_CHREC:
992 : /* Check for constant strides. With a non constant stride of
993 : 'n' we would have a value of 'iv * n'. Also check that the
994 : initial value can represented: for example 'n * m' cannot be
995 : represented. */
996 3846 : gcc_assert (loop_in_sese_p (get_loop (cfun,
997 : CHREC_VARIABLE (scev)), scop));
998 3846 : if (!evolution_function_right_is_integer_cst (scev)
999 3846 : || !graphite_can_represent_init (scev))
1000 80 : return false;
1001 3766 : return graphite_can_represent_scev (scop, CHREC_LEFT (scev));
1002 :
1003 : case ADDR_EXPR:
1004 : /* We cannot encode addresses for ISL. */
1005 : return false;
1006 :
1007 7155 : default:
1008 7155 : break;
1009 : }
1010 :
1011 : /* Only affine functions can be represented. */
1012 7155 : if (tree_contains_chrecs (scev, NULL) || !scev_is_linear_expression (scev))
1013 3 : return false;
1014 :
1015 : return true;
1016 : }
1017 :
1018 : /* Return true when EXPR can be represented in the polyhedral model.
1019 :
1020 : This means an expression can be represented, if it is linear with respect to
1021 : the loops and the strides are non parametric. LOOP is the place where the
1022 : expr will be evaluated. SCOP defines the region we analyse. */
1023 :
1024 : bool
1025 4129 : scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop,
1026 : tree expr)
1027 : {
1028 4129 : tree scev = cached_scalar_evolution_in_region (scop, loop, expr);
1029 4129 : bool can_represent = graphite_can_represent_scev (scop, scev);
1030 :
1031 4129 : if (!can_represent)
1032 : {
1033 134 : if (dump_file)
1034 : {
1035 19 : fprintf (dump_file,
1036 : "[graphite_can_represent_expr] Cannot represent scev \"");
1037 19 : print_generic_expr (dump_file, scev, TDF_SLIM);
1038 19 : fprintf (dump_file, "\" of expression ");
1039 19 : print_generic_expr (dump_file, expr, TDF_SLIM);
1040 19 : fprintf (dump_file, " in loop %d\n", loop->num);
1041 : }
1042 : }
1043 4129 : return can_represent;
1044 : }
1045 :
1046 : /* Return true if the data references of STMT can be represented by Graphite.
1047 : We try to analyze the data references in a loop contained in the SCOP. */
1048 :
1049 : bool
1050 10536 : scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt)
1051 : {
1052 10536 : edge nest = scop.entry;
1053 10536 : loop_p loop = loop_containing_stmt (stmt);
1054 10536 : if (!loop_in_sese_p (loop, scop))
1055 173 : loop = NULL;
1056 :
1057 10536 : auto_vec<data_reference_p> drs;
1058 10536 : if (! graphite_find_data_references_in_stmt (nest, loop, stmt, &drs))
1059 : {
1060 4 : DEBUG_PRINT (dp << "[stmt_has_simple_data_refs_p] "
1061 : "Unanalyzable statement.\n");
1062 4 : return false;
1063 : }
1064 :
1065 : int j;
1066 : data_reference_p dr;
1067 16779 : FOR_EACH_VEC_ELT (drs, j, dr)
1068 : {
1069 4683 : for (unsigned i = 0; i < DR_NUM_DIMENSIONS (dr); ++i)
1070 2676 : if (! graphite_can_represent_scev (scop, DR_ACCESS_FN (dr, i)))
1071 : {
1072 113 : DEBUG_PRINT (dp << "[stmt_has_simple_data_refs_p] "
1073 : "Cannot represent access function SCEV: "
1074 : << DR_ACCESS_FN (dr, i) << "\n");
1075 113 : return false;
1076 : }
1077 : }
1078 :
1079 : return true;
1080 10536 : }
1081 :
1082 : /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1083 : Calls have side-effects, except those to const or pure
1084 : functions. */
1085 :
1086 : static bool
1087 10622 : stmt_has_side_effects (gimple *stmt)
1088 : {
1089 10622 : if (gimple_has_volatile_ops (stmt)
1090 10607 : || (gimple_code (stmt) == GIMPLE_CALL
1091 107 : && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
1092 19561 : || (gimple_code (stmt) == GIMPLE_ASM))
1093 : {
1094 86 : DEBUG_PRINT (dp << "[scop-detection-fail] "
1095 : << "Statement has side-effects:\n";
1096 : print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
1097 86 : return true;
1098 : }
1099 : return false;
1100 : }
1101 :
1102 : /* Return true only when STMT is simple enough for being handled by Graphite.
1103 : This depends on SCOP, as the parameters are initialized relatively to
1104 : this basic block, the linear functions are initialized based on the outermost
1105 : loop containing STMT inside the SCOP. BB is the place where we try to
1106 : evaluate the STMT. */
1107 :
1108 : bool
1109 10758 : scop_detection::stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
1110 : basic_block bb) const
1111 : {
1112 10758 : gcc_assert (scop);
1113 :
1114 10758 : if (is_gimple_debug (stmt))
1115 : return true;
1116 :
1117 10622 : if (stmt_has_side_effects (stmt))
1118 : return false;
1119 :
1120 10536 : if (!stmt_has_simple_data_refs_p (scop, stmt))
1121 : {
1122 117 : DEBUG_PRINT (dp << "[scop-detection-fail] "
1123 : << "Graphite cannot handle data-refs in stmt:\n";
1124 : print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS););
1125 117 : return false;
1126 : }
1127 :
1128 10419 : switch (gimple_code (stmt))
1129 : {
1130 : case GIMPLE_LABEL:
1131 : return true;
1132 :
1133 1582 : case GIMPLE_COND:
1134 1582 : {
1135 : /* We can handle all binary comparisons. Inequalities are
1136 : also supported as they can be represented with union of
1137 : polyhedra. */
1138 1582 : enum tree_code code = gimple_cond_code (stmt);
1139 1046 : if (!(code == LT_EXPR
1140 1582 : || code == GT_EXPR
1141 1177 : || code == LE_EXPR
1142 1177 : || code == GE_EXPR
1143 : || code == EQ_EXPR
1144 : || code == NE_EXPR))
1145 : {
1146 0 : DEBUG_PRINT (dp << "[scop-detection-fail] "
1147 : << "Graphite cannot handle cond stmt:\n";
1148 : print_gimple_stmt (dump_file, stmt, 0,
1149 : TDF_VOPS | TDF_MEMSYMS));
1150 0 : return false;
1151 : }
1152 :
1153 1582 : loop_p loop = bb->loop_father;
1154 4491 : for (unsigned i = 0; i < 2; ++i)
1155 : {
1156 3040 : tree op = gimple_op (stmt, i);
1157 3040 : if (!graphite_can_represent_expr (scop, loop, op))
1158 : {
1159 125 : DEBUG_PRINT (dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmt,
1160 : "[scop-detection-fail] "
1161 : "Graphite cannot represent cond "
1162 : "stmt operator expression.\n"));
1163 125 : DEBUG_PRINT (dp << op << "\n");
1164 125 : return false;
1165 : }
1166 :
1167 2915 : if (! INTEGRAL_TYPE_P (TREE_TYPE (op)))
1168 : {
1169 6 : DEBUG_PRINT (dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmt,
1170 : "[scop-detection-fail] "
1171 : "Graphite cannot represent cond "
1172 : "statement operator. "
1173 : "Type must be integral.\n"));
1174 6 : return false;
1175 : }
1176 : }
1177 :
1178 : return true;
1179 : }
1180 :
1181 8820 : case GIMPLE_ASSIGN:
1182 8820 : case GIMPLE_CALL:
1183 8820 : {
1184 8820 : tree op, lhs = gimple_get_lhs (stmt);
1185 8820 : ssa_op_iter i;
1186 : /* If we are not going to instantiate the stmt do not require
1187 : its operands to be instantiatable at this point. */
1188 8820 : if (lhs
1189 8820 : && TREE_CODE (lhs) == SSA_NAME
1190 16741 : && scev_analyzable_p (lhs, scop))
1191 : return true;
1192 : /* Verify that if we can analyze operands at their def site we
1193 : also can represent them when analyzed at their uses. */
1194 9925 : FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
1195 6214 : if (scev_analyzable_p (op, scop)
1196 9438 : && chrec_contains_undetermined
1197 3224 : (cached_scalar_evolution_in_region (scop,
1198 3224 : bb->loop_father, op)))
1199 : {
1200 2 : DEBUG_PRINT (dp << "[scop-detection-fail] "
1201 : << "Graphite cannot code-gen stmt:\n";
1202 : print_gimple_stmt (dump_file, stmt, 0,
1203 : TDF_VOPS | TDF_MEMSYMS));
1204 2 : return false;
1205 : }
1206 : return true;
1207 : }
1208 :
1209 7 : default:
1210 : /* These nodes cut a new scope. */
1211 7 : DEBUG_PRINT (
1212 : dp << "[scop-detection-fail] "
1213 : << "Gimple stmt not handled in Graphite:\n";
1214 : print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
1215 : return false;
1216 : }
1217 : }
1218 :
1219 : /* Returns the number of pbbs that are in loops contained in SCOP. */
1220 :
1221 : int
1222 201 : scop_detection::nb_pbbs_in_loops (scop_p scop)
1223 : {
1224 201 : int i;
1225 201 : poly_bb_p pbb;
1226 201 : int res = 0;
1227 :
1228 869 : FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1229 668 : if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), scop->scop_info->region))
1230 568 : res++;
1231 :
1232 201 : return res;
1233 : }
1234 :
1235 : /* Assigns the parameter NAME an index in REGION. */
1236 :
1237 : static void
1238 318 : assign_parameter_index_in_region (tree name, sese_info_p region)
1239 : {
1240 318 : gcc_assert (TREE_CODE (name) == SSA_NAME
1241 : && ! defined_in_sese_p (name, region->region));
1242 : int i;
1243 : tree p;
1244 512 : FOR_EACH_VEC_ELT (region->params, i, p)
1245 373 : if (p == name)
1246 318 : return;
1247 :
1248 139 : region->params.safe_push (name);
1249 : }
1250 :
1251 : /* In the context of sese S, scan the expression E and translate it to
1252 : a linear expression C. When parsing a symbolic multiplication, K
1253 : represents the constant multiplier of an expression containing
1254 : parameters. */
1255 :
1256 : static void
1257 1502 : scan_tree_for_params (sese_info_p s, tree e)
1258 : {
1259 3035 : if (e == chrec_dont_know)
1260 : return;
1261 :
1262 3035 : switch (TREE_CODE (e))
1263 : {
1264 1202 : case POLYNOMIAL_CHREC:
1265 1202 : scan_tree_for_params (s, CHREC_LEFT (e));
1266 1202 : break;
1267 :
1268 3 : case MULT_EXPR:
1269 3 : if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
1270 3 : scan_tree_for_params (s, TREE_OPERAND (e, 0));
1271 : else
1272 0 : scan_tree_for_params (s, TREE_OPERAND (e, 1));
1273 : break;
1274 :
1275 170 : case PLUS_EXPR:
1276 170 : case POINTER_PLUS_EXPR:
1277 170 : case MINUS_EXPR:
1278 170 : scan_tree_for_params (s, TREE_OPERAND (e, 0));
1279 170 : scan_tree_for_params (s, TREE_OPERAND (e, 1));
1280 170 : break;
1281 :
1282 158 : case NEGATE_EXPR:
1283 158 : case BIT_NOT_EXPR:
1284 158 : CASE_CONVERT:
1285 158 : case NON_LVALUE_EXPR:
1286 158 : scan_tree_for_params (s, TREE_OPERAND (e, 0));
1287 158 : break;
1288 :
1289 318 : case SSA_NAME:
1290 318 : assign_parameter_index_in_region (e, s);
1291 318 : break;
1292 :
1293 : case INTEGER_CST:
1294 : case ADDR_EXPR:
1295 : case REAL_CST:
1296 : case COMPLEX_CST:
1297 : case VECTOR_CST:
1298 : break;
1299 :
1300 0 : default:
1301 0 : gcc_unreachable ();
1302 1502 : break;
1303 : }
1304 : }
1305 :
1306 : /* Find parameters with respect to REGION in BB. We are looking in memory
1307 : access functions, conditions and loop bounds. */
1308 :
1309 : static void
1310 668 : find_params_in_bb (sese_info_p region, gimple_poly_bb_p gbb)
1311 : {
1312 : /* Find parameters in the access functions of data references. */
1313 668 : int i;
1314 668 : data_reference_p dr;
1315 2535 : FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb), i, dr)
1316 1731 : for (unsigned j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
1317 999 : scan_tree_for_params (region, DR_ACCESS_FN (dr, j));
1318 :
1319 : /* Find parameters in conditional statements. */
1320 : gimple *stmt;
1321 763 : FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
1322 : {
1323 95 : loop_p loop = gimple_bb (stmt)->loop_father;
1324 95 : tree lhs = cached_scalar_evolution_in_region (region->region, loop,
1325 : gimple_cond_lhs (stmt));
1326 95 : tree rhs = cached_scalar_evolution_in_region (region->region, loop,
1327 : gimple_cond_rhs (stmt));
1328 95 : gcc_assert (!chrec_contains_undetermined (lhs)
1329 : && !chrec_contains_undetermined (rhs));
1330 :
1331 95 : scan_tree_for_params (region, lhs);
1332 95 : scan_tree_for_params (region, rhs);
1333 : }
1334 668 : }
1335 :
1336 : /* Record the parameters used in the SCOP BBs. A variable is a parameter
1337 : in a scop if it does not vary during the execution of that scop. */
1338 :
1339 : static void
1340 201 : find_scop_parameters (scop_p scop)
1341 : {
1342 201 : unsigned i;
1343 201 : sese_info_p region = scop->scop_info;
1344 :
1345 : /* Parameters used in loop bounds are processed during gather_bbs. */
1346 :
1347 : /* Find the parameters used in data accesses. */
1348 201 : poly_bb_p pbb;
1349 869 : FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1350 668 : find_params_in_bb (region, PBB_BLACK_BOX (pbb));
1351 :
1352 201 : int nbp = sese_nb_params (region);
1353 201 : scop_set_nb_params (scop, nbp);
1354 201 : }
1355 :
1356 : static void
1357 858 : add_write (vec<tree> *writes, tree def)
1358 : {
1359 858 : writes->safe_push (def);
1360 858 : DEBUG_PRINT (dp << "Adding scalar write: ";
1361 : print_generic_expr (dump_file, def);
1362 : dp << "\nFrom stmt: ";
1363 : print_gimple_stmt (dump_file,
1364 : SSA_NAME_DEF_STMT (def), 0));
1365 858 : }
1366 :
1367 : static void
1368 681 : add_read (vec<scalar_use> *reads, tree use, gimple *use_stmt)
1369 : {
1370 681 : DEBUG_PRINT (dp << "Adding scalar read: ";
1371 : print_generic_expr (dump_file, use);
1372 : dp << "\nFrom stmt: ";
1373 : print_gimple_stmt (dump_file, use_stmt, 0));
1374 681 : reads->safe_push (std::make_pair (use_stmt, use));
1375 681 : }
1376 :
1377 :
1378 : /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1379 :
1380 : static void
1381 3181 : build_cross_bb_scalars_def (scop_p scop, tree def, basic_block def_bb,
1382 : vec<tree> *writes)
1383 : {
1384 3181 : if (!is_gimple_reg (def))
1385 388 : return;
1386 :
1387 2793 : bool scev_analyzable = scev_analyzable_p (def, scop->scop_info->region);
1388 :
1389 2793 : gimple *use_stmt;
1390 2793 : imm_use_iterator imm_iter;
1391 9143 : FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
1392 : /* Do not gather scalar variables that can be analyzed by SCEV as they can
1393 : be generated out of the induction variables. */
1394 3717 : if ((! scev_analyzable
1395 : /* But gather SESE liveouts as we otherwise fail to rewrite their
1396 : exit PHIs. */
1397 2793 : || ! bb_in_sese_p (gimple_bb (use_stmt), scop->scop_info->region))
1398 3718 : && (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt)))
1399 : {
1400 160 : add_write (writes, def);
1401 160 : break;
1402 2793 : }
1403 : }
1404 :
1405 : /* Record USE if it is defined in other bbs different than USE_STMT
1406 : in the SCOP. */
1407 :
1408 : static void
1409 5173 : build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt,
1410 : vec<scalar_use> *reads)
1411 : {
1412 5173 : if (!is_gimple_reg (use))
1413 : return;
1414 :
1415 : /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1416 : generated out of the induction variables. */
1417 5173 : if (scev_analyzable_p (use, scop->scop_info->region))
1418 : return;
1419 :
1420 988 : gimple *def_stmt = SSA_NAME_DEF_STMT (use);
1421 988 : if (gimple_bb (def_stmt) != gimple_bb (use_stmt))
1422 120 : add_read (reads, use, use_stmt);
1423 : }
1424 :
1425 : /* Generates a polyhedral black box only if the bb contains interesting
1426 : information. */
1427 :
1428 : static gimple_poly_bb_p
1429 2171 : try_generate_gimple_bb (scop_p scop, basic_block bb)
1430 : {
1431 2171 : vec<data_reference_p> drs = vNULL;
1432 2171 : vec<tree> writes = vNULL;
1433 2171 : vec<scalar_use> reads = vNULL;
1434 :
1435 2171 : sese_l region = scop->scop_info->region;
1436 2171 : edge nest = region.entry;
1437 2171 : loop_p loop = bb->loop_father;
1438 2171 : if (!loop_in_sese_p (loop, region))
1439 392 : loop = NULL;
1440 :
1441 8187 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1442 3845 : gsi_next (&gsi))
1443 : {
1444 3845 : gimple *stmt = gsi_stmt (gsi);
1445 3845 : if (is_gimple_debug (stmt))
1446 48 : continue;
1447 :
1448 3797 : graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
1449 :
1450 3797 : tree def = gimple_get_lhs (stmt);
1451 3797 : if (def)
1452 3181 : build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), &writes);
1453 :
1454 3797 : ssa_op_iter iter;
1455 3797 : tree use;
1456 8970 : FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1457 5173 : build_cross_bb_scalars_use (scop, use, stmt, &reads);
1458 : }
1459 :
1460 : /* Handle defs and uses in PHIs. Those need special treatment given
1461 : that we have to present ISL with sth that looks like we've rewritten
1462 : the IL out-of-SSA. */
1463 4516 : for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
1464 2345 : gsi_next (&psi))
1465 : {
1466 2345 : gphi *phi = psi.phi ();
1467 2345 : tree res = gimple_phi_result (phi);
1468 2345 : if (virtual_operand_p (res)
1469 2345 : || scev_analyzable_p (res, scop->scop_info->region))
1470 2048 : continue;
1471 : /* To simulate out-of-SSA the block containing the PHI node has
1472 : reads of the PHI destination. And to preserve SSA dependences
1473 : we also write to it (the out-of-SSA decl and the SSA result
1474 : are coalesced for dependence purposes which is good enough). */
1475 297 : add_read (&reads, res, phi);
1476 297 : add_write (&writes, res);
1477 : }
1478 2171 : basic_block bb_for_succs = bb;
1479 2171 : if (bb_for_succs == bb_for_succs->loop_father->latch
1480 560 : && bb_in_sese_p (bb_for_succs, scop->scop_info->region)
1481 2731 : && sese_trivially_empty_bb_p (bb_for_succs))
1482 : bb_for_succs = NULL;
1483 4342 : while (bb_for_succs)
1484 : {
1485 2171 : basic_block latch = NULL;
1486 2171 : edge_iterator ei;
1487 2171 : edge e;
1488 4958 : FOR_EACH_EDGE (e, ei, bb_for_succs->succs)
1489 : {
1490 6230 : for (gphi_iterator psi = gsi_start_phis (e->dest); !gsi_end_p (psi);
1491 3443 : gsi_next (&psi))
1492 : {
1493 3443 : gphi *phi = psi.phi ();
1494 3443 : tree res = gimple_phi_result (phi);
1495 6886 : if (virtual_operand_p (res))
1496 1405 : continue;
1497 : /* To simulate out-of-SSA the predecessor of edges into PHI nodes
1498 : has a copy from the PHI argument to the PHI destination. */
1499 2038 : if (! scev_analyzable_p (res, scop->scop_info->region))
1500 401 : add_write (&writes, res);
1501 2038 : tree use = PHI_ARG_DEF_FROM_EDGE (phi, e);
1502 2038 : if (TREE_CODE (use) == SSA_NAME
1503 1402 : && ! SSA_NAME_IS_DEFAULT_DEF (use)
1504 1401 : && gimple_bb (SSA_NAME_DEF_STMT (use)) != bb_for_succs
1505 3262 : && ! scev_analyzable_p (use, scop->scop_info->region))
1506 199 : add_read (&reads, use, phi);
1507 : }
1508 2787 : if (e->dest == bb_for_succs->loop_father->latch
1509 560 : && bb_in_sese_p (e->dest, scop->scop_info->region)
1510 3347 : && sese_trivially_empty_bb_p (e->dest))
1511 560 : latch = e->dest;
1512 : }
1513 : /* Handle empty latch block PHIs here, otherwise we confuse ISL
1514 : with extra conditional code where it then peels off the last
1515 : iteration just because of that. It would be simplest if we
1516 : just didn't force simple latches (thus remove the forwarder). */
1517 2171 : bb_for_succs = latch;
1518 : }
1519 :
1520 : /* For the region exit block add reads for all live-out vars. */
1521 2171 : if (bb == scop->scop_info->region.exit->src)
1522 : {
1523 211 : sese_build_liveouts (scop->scop_info);
1524 211 : unsigned i;
1525 211 : bitmap_iterator bi;
1526 276 : EXECUTE_IF_SET_IN_BITMAP (scop->scop_info->liveout, 0, i, bi)
1527 : {
1528 65 : tree use = ssa_name (i);
1529 65 : add_read (&reads, use, NULL);
1530 : }
1531 : }
1532 :
1533 2171 : if (drs.is_empty () && writes.is_empty () && reads.is_empty ())
1534 : return NULL;
1535 :
1536 704 : return new_gimple_poly_bb (bb, drs, reads, writes);
1537 : }
1538 :
1539 : /* Compute alias-sets for all data references in DRS. */
1540 :
1541 : static bool
1542 211 : build_alias_set (scop_p scop)
1543 : {
1544 211 : int num_vertices = scop->drs.length ();
1545 211 : struct graph *g = new_graph (num_vertices);
1546 211 : dr_info *dr1, *dr2;
1547 211 : int i, j;
1548 211 : int *all_vertices;
1549 :
1550 211 : struct loop *nest
1551 211 : = find_common_loop (scop->scop_info->region.entry->dest->loop_father,
1552 211 : scop->scop_info->region.exit->src->loop_father);
1553 :
1554 211 : FOR_EACH_VEC_ELT (scop->drs, i, dr1)
1555 4195 : for (j = i+1; scop->drs.iterate (j, &dr2); j++)
1556 2518 : if (dr_may_alias_p (dr1->dr, dr2->dr, nest))
1557 : {
1558 : /* Dependences in the same alias set need to be handled
1559 : by just looking at DR_ACCESS_FNs. */
1560 1615 : if (DR_NUM_DIMENSIONS (dr1->dr) == 0
1561 3228 : || DR_NUM_DIMENSIONS (dr1->dr) != DR_NUM_DIMENSIONS (dr2->dr)
1562 1612 : || ! operand_equal_p (DR_BASE_OBJECT (dr1->dr),
1563 1612 : DR_BASE_OBJECT (dr2->dr),
1564 : OEP_ADDRESS_OF)
1565 3219 : || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1->dr)),
1566 1605 : TREE_TYPE (DR_BASE_OBJECT (dr2->dr))))
1567 : {
1568 10 : free_graph (g);
1569 10 : return false;
1570 : }
1571 1605 : add_edge (g, i, j);
1572 1605 : add_edge (g, j, i);
1573 : }
1574 :
1575 201 : all_vertices = XNEWVEC (int, num_vertices);
1576 1134 : for (i = 0; i < num_vertices; i++)
1577 732 : all_vertices[i] = i;
1578 :
1579 201 : scop->max_alias_set
1580 201 : = graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + 1;
1581 201 : free (all_vertices);
1582 :
1583 933 : for (i = 0; i < g->n_vertices; i++)
1584 732 : scop->drs[i].alias_set = g->vertices[i].component + 1;
1585 :
1586 201 : free_graph (g);
1587 201 : return true;
1588 : }
1589 :
1590 : /* Gather BBs and conditions for a SCOP. */
1591 : class gather_bbs : public dom_walker
1592 : {
1593 : public:
1594 : gather_bbs (cdi_direction, scop_p, int *);
1595 :
1596 : virtual edge before_dom_children (basic_block);
1597 : virtual void after_dom_children (basic_block);
1598 :
1599 : private:
1600 : auto_vec<gimple *, 3> conditions, cases;
1601 : scop_p scop;
1602 : };
1603 : }
1604 211 : gather_bbs::gather_bbs (cdi_direction direction, scop_p scop, int *bb_to_rpo)
1605 211 : : dom_walker (direction, ALL_BLOCKS, bb_to_rpo), scop (scop)
1606 : {
1607 211 : }
1608 :
1609 : /* Call-back for dom_walk executed before visiting the dominated
1610 : blocks. */
1611 :
1612 : edge
1613 2377 : gather_bbs::before_dom_children (basic_block bb)
1614 : {
1615 2377 : sese_info_p region = scop->scop_info;
1616 2377 : if (!bb_in_sese_p (bb, region->region))
1617 206 : return dom_walker::STOP;
1618 :
1619 : /* For loops fully contained in the region record parameters in the
1620 : loop bounds. */
1621 2171 : loop_p loop = bb->loop_father;
1622 2171 : if (loop->header == bb
1623 2171 : && loop_in_sese_p (loop, region->region))
1624 : {
1625 560 : tree nb_iters = number_of_latch_executions (loop);
1626 560 : if (chrec_contains_symbols (nb_iters))
1627 : {
1628 143 : nb_iters = cached_scalar_evolution_in_region (region->region,
1629 : loop, nb_iters);
1630 143 : scan_tree_for_params (region, nb_iters);
1631 : }
1632 : }
1633 :
1634 2171 : if (gcond *stmt = single_pred_cond_non_loop_exit (bb))
1635 : {
1636 647 : edge e = single_pred_edge (bb);
1637 : /* Make sure the condition is in the region and thus was verified
1638 : to be handled. */
1639 647 : if (e != region->region.entry)
1640 : {
1641 647 : conditions.safe_push (stmt);
1642 647 : if (e->flags & EDGE_TRUE_VALUE)
1643 465 : cases.safe_push (stmt);
1644 : else
1645 182 : cases.safe_push (NULL);
1646 : }
1647 : }
1648 :
1649 2171 : scop->scop_info->bbs.safe_push (bb);
1650 :
1651 2171 : gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb);
1652 2171 : if (!gbb)
1653 : return NULL;
1654 :
1655 704 : GBB_CONDITIONS (gbb) = conditions.copy ();
1656 704 : GBB_CONDITION_CASES (gbb) = cases.copy ();
1657 :
1658 704 : poly_bb_p pbb = new_poly_bb (scop, gbb);
1659 704 : scop->pbbs.safe_push (pbb);
1660 :
1661 704 : int i;
1662 704 : data_reference_p dr;
1663 2206 : FOR_EACH_VEC_ELT (gbb->data_refs, i, dr)
1664 : {
1665 1183 : DEBUG_PRINT (dp << "Adding memory ";
1666 : if (dr->is_read)
1667 : dp << "read: ";
1668 : else
1669 : dp << "write: ";
1670 : print_generic_expr (dump_file, dr->ref);
1671 : dp << "\nFrom stmt: ";
1672 : print_gimple_stmt (dump_file, dr->stmt, 0));
1673 :
1674 798 : scop->drs.safe_push (dr_info (dr, pbb));
1675 : }
1676 :
1677 : return NULL;
1678 : }
1679 :
1680 : /* Call-back for dom_walk executed after visiting the dominated
1681 : blocks. */
1682 :
1683 : void
1684 2377 : gather_bbs::after_dom_children (basic_block bb)
1685 : {
1686 2377 : if (!bb_in_sese_p (bb, scop->scop_info->region))
1687 : return;
1688 :
1689 2171 : if (single_pred_cond_non_loop_exit (bb))
1690 : {
1691 647 : edge e = single_pred_edge (bb);
1692 647 : if (e != scop->scop_info->region.entry)
1693 : {
1694 647 : conditions.pop ();
1695 647 : cases.pop ();
1696 : }
1697 : }
1698 : }
1699 :
1700 :
1701 : /* Compute sth like an execution order, dominator order with first executing
1702 : edges that stay inside the current loop, delaying processing exit edges. */
1703 :
1704 : static int *bb_to_rpo;
1705 :
1706 : /* Helper for qsort, sorting after order above. */
1707 :
1708 : static int
1709 4250 : cmp_pbbs (const void *pa, const void *pb)
1710 : {
1711 4250 : poly_bb_p bb1 = *((const poly_bb_p *)pa);
1712 4250 : poly_bb_p bb2 = *((const poly_bb_p *)pb);
1713 4250 : if (bb_to_rpo[bb1->black_box->bb->index]
1714 4250 : < bb_to_rpo[bb2->black_box->bb->index])
1715 : return -1;
1716 2293 : else if (bb_to_rpo[bb1->black_box->bb->index]
1717 : > bb_to_rpo[bb2->black_box->bb->index])
1718 : return 1;
1719 : else
1720 0 : return 0;
1721 : }
1722 :
1723 : /* Find Static Control Parts (SCoP) in the current function and pushes
1724 : them to SCOPS. */
1725 :
1726 : void
1727 556 : build_scops (vec<scop_p> *scops)
1728 : {
1729 556 : if (dump_file)
1730 190 : dp.set_dump_file (dump_file);
1731 :
1732 556 : scop_detection sb;
1733 556 : sb.build_scop_depth (current_loops->tree_root);
1734 :
1735 : /* Now create scops from the lightweight SESEs. */
1736 556 : vec<sese_l> scops_l = sb.get_scops ();
1737 :
1738 : /* Domwalk needs a bb to RPO mapping. Compute it once here. */
1739 556 : int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
1740 556 : int postorder_num = pre_and_rev_post_order_compute (NULL, postorder, true);
1741 556 : bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
1742 9841 : for (int i = 0; i < postorder_num; ++i)
1743 9285 : bb_to_rpo[postorder[i]] = i;
1744 556 : free (postorder);
1745 :
1746 556 : int i;
1747 556 : sese_l *s;
1748 767 : FOR_EACH_VEC_ELT (scops_l, i, s)
1749 : {
1750 211 : scop_p scop = new_scop (s->entry, s->exit);
1751 :
1752 : /* Record all basic blocks and their conditions in REGION. */
1753 211 : gather_bbs (CDI_DOMINATORS, scop, bb_to_rpo).walk (s->entry->dest);
1754 :
1755 : /* Sort pbbs after execution order for initial schedule generation. */
1756 211 : scop->pbbs.qsort (cmp_pbbs);
1757 :
1758 211 : if (! build_alias_set (scop))
1759 : {
1760 10 : DEBUG_PRINT (dp << "[scop-detection-fail] cannot handle dependences\n");
1761 10 : free_scop (scop);
1762 10 : continue;
1763 : }
1764 :
1765 : /* Do not optimize a scop containing only PBBs that do not belong
1766 : to any loops. */
1767 201 : if (sb.nb_pbbs_in_loops (scop) == 0)
1768 : {
1769 0 : DEBUG_PRINT (dp << "[scop-detection-fail] no data references.\n");
1770 0 : free_scop (scop);
1771 0 : continue;
1772 : }
1773 :
1774 201 : unsigned max_arrays = param_graphite_max_arrays_per_scop;
1775 201 : if (max_arrays > 0
1776 402 : && scop->drs.length () >= max_arrays)
1777 : {
1778 0 : DEBUG_PRINT (dp << "[scop-detection-fail] too many data references: "
1779 : << scop->drs.length ()
1780 : << " is larger than --param graphite-max-arrays-per-scop="
1781 : << max_arrays << ".\n");
1782 0 : free_scop (scop);
1783 0 : continue;
1784 : }
1785 :
1786 201 : find_scop_parameters (scop);
1787 201 : graphite_dim_t max_dim = param_graphite_max_nb_scop_params;
1788 201 : if (max_dim > 0
1789 201 : && scop_nb_params (scop) > max_dim)
1790 : {
1791 0 : DEBUG_PRINT (dp << "[scop-detection-fail] too many parameters: "
1792 : << scop_nb_params (scop)
1793 : << " larger than --param graphite-max-nb-scop-params="
1794 : << max_dim << ".\n");
1795 0 : free_scop (scop);
1796 0 : continue;
1797 : }
1798 :
1799 201 : scops->safe_push (scop);
1800 : }
1801 :
1802 556 : free (bb_to_rpo);
1803 556 : bb_to_rpo = NULL;
1804 934 : DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0););
1805 556 : }
1806 :
1807 : #endif /* HAVE_isl */
|
