1/* Detection of Static Control Parts (SCoP) for Graphite.
2 Copyright (C) 2009-2023 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and
4 Tobias Grosser <grosser@fim.uni-passau.de>.
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify
9it under the terms of the GNU General Public License as published by
10the Free Software Foundation; either version 3, or (at your option)
11any later version.
12
13GCC is distributed in the hope that it will be useful,
14but WITHOUT ANY WARRANTY; without even the implied warranty of
15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16GNU General Public License for more details.
17
18You should have received a copy of the GNU General Public License
19along 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
53class debug_printer
54{
55private:
56 FILE *dump_file;
57
58public:
59 void
60 set_dump_file (FILE *f)
61 {
62 gcc_assert (f);
63 dump_file = f;
64 }
65
66 friend debug_printer &
67 operator<< (debug_printer &output, int i)
68 {
69 fprintf (output.dump_file, "%d", i);
70 return output;
71 }
72
73 friend debug_printer &
74 operator<< (debug_printer &output, const char *s)
75 {
76 fprintf (output.dump_file, "%s", s);
77 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 operator<< (debug_printer &output, tree t)
89 {
90 print_generic_expr (output.dump_file, t, TDF_SLIM);
91 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
110DEBUG_FUNCTION void
111dot_all_sese (FILE *file, vec<sese_l>& scops)
112{
113 /* Disable debugging while printing graph. */
114 dump_flags_t tmp_dump_flags = dump_flags;
115 dump_flags = TDF_NONE;
116
117 fprintf (file, "digraph all {\n");
118
119 basic_block bb;
120 FOR_ALL_BB_FN (bb, cfun)
121 {
122 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 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
128 bb->index);
129 fprintf (file, "CELLSPACING=\"0\">\n");
130
131 /* Select color for SCoP. */
132 sese_l *region;
133 int i;
134 FOR_EACH_VEC_ELT (scops, i, region)
135 {
136 bool sese_in_region = bb_in_sese_p (bb, *region);
137 if (sese_in_region || (region->exit->dest == bb)
138 || (region->entry->dest == bb))
139 {
140 const char *color;
141 switch (i % 17)
142 {
143 case 0: /* red */
144 color = "#e41a1c";
145 break;
146 case 1: /* blue */
147 color = "#377eb8";
148 break;
149 case 2: /* green */
150 color = "#4daf4a";
151 break;
152 case 3: /* purple */
153 color = "#984ea3";
154 break;
155 case 4: /* orange */
156 color = "#ff7f00";
157 break;
158 case 5: /* yellow */
159 color = "#ffff33";
160 break;
161 case 6: /* brown */
162 color = "#a65628";
163 break;
164 case 7: /* rose */
165 color = "#f781bf";
166 break;
167 case 8:
168 color = "#8dd3c7";
169 break;
170 case 9:
171 color = "#ffffb3";
172 break;
173 case 10:
174 color = "#bebada";
175 break;
176 case 11:
177 color = "#fb8072";
178 break;
179 case 12:
180 color = "#80b1d3";
181 break;
182 case 13:
183 color = "#fdb462";
184 break;
185 case 14:
186 color = "#b3de69";
187 break;
188 case 15:
189 color = "#fccde5";
190 break;
191 case 16:
192 color = "#bc80bd";
193 break;
194 default: /* gray */
195 color = "#999999";
196 }
197
198 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
199 color);
200
201 if (!sese_in_region)
202 fprintf (file, " (");
203
204 if (bb == region->entry->dest && bb == region->exit->dest)
205 fprintf (file, " %d*# ", bb->index);
206 else if (bb == region->entry->dest)
207 fprintf (file, " %d* ", bb->index);
208 else if (bb == region->exit->dest)
209 fprintf (file, " %d# ", bb->index);
210 else
211 fprintf (file, " %d ", bb->index);
212
213 fprintf (file, "{lp_%d}", bb->loop_father->num);
214
215 if (!sese_in_region)
216 fprintf (file, ")");
217
218 fprintf (file, "</TD></TR>\n");
219 part_of_scop = true;
220 }
221 }
222
223 if (!part_of_scop)
224 {
225 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
226 fprintf (file, " %d {lp_%d} </TD></TR>\n", bb->index,
227 bb->loop_father->num);
228 }
229 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
230 }
231
232 FOR_ALL_BB_FN (bb, cfun)
233 {
234 edge e;
235 edge_iterator ei;
236 FOR_EACH_EDGE (e, ei, bb->succs)
237 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
238 }
239
240 fputs ("}\n\n", file);
241
242 /* Enable debugging again. */
243 dump_flags = tmp_dump_flags;
244}
245
246/* Display SCoP on stderr. */
247
248DEBUG_FUNCTION void
249dot_sese (sese_l& scop)
250{
251 vec<sese_l> scops;
252 scops.create (1);
253
254 if (scop)
255 scops.safe_push (scop);
256
257 dot_all_sese (stderr, scops);
258
259 scops.release ();
260}
261
262DEBUG_FUNCTION void
263dot_cfg ()
264{
265 vec<sese_l> scops;
266 scops.create (1);
267 dot_all_sese (stderr, scops);
268 scops.release ();
269}
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
275static gcond *
276single_pred_cond_non_loop_exit (basic_block bb)
277{
278 if (single_pred_p (bb))
279 {
280 basic_block pred = single_pred (bb);
281
282 if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
283 return NULL;
284
285 return safe_dyn_cast <gcond *> (*gsi_last_bb (pred));
286 }
287
288 return NULL;
289}
290
291namespace
292{
293
294/* Build the maximal scop containing LOOPs and add it to SCOPS. */
295
296class scop_detection
297{
298public:
299 scop_detection () : scops (vNULL) {}
300
301 ~scop_detection ()
302 {
303 scops.release ();
304 }
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 get_scops ()
313 {
314 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
414private:
415 vec<sese_l> scops;
416};
417
418sese_l scop_detection::invalid_sese (NULL, NULL);
419
420/* Return an sese_l around the LOOP. */
421
422sese_l
423scop_detection::get_sese (loop_p loop)
424{
425 if (!loop)
426 return invalid_sese;
427
428 edge scop_begin = loop_preheader_edge (loop);
429 edge scop_end = single_exit (loop);
430 if (!scop_end || (scop_end->flags & (EDGE_COMPLEX|EDGE_FAKE)))
431 return invalid_sese;
432
433 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
439sese_l
440scop_detection::merge_sese (sese_l first, sese_l second) const
441{
442 /* In the trivial case first/second may be NULL. */
443 if (!first)
444 return second;
445 if (!second)
446 return first;
447
448 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 auto_bitmap worklist, in_sese_region;
454 bitmap_set_bit (worklist, get_entry_bb (first)->index);
455 bitmap_set_bit (worklist, get_exit_bb (first)->index);
456 bitmap_set_bit (worklist, get_entry_bb (second)->index);
457 bitmap_set_bit (worklist, get_exit_bb (second)->index);
458 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 do
466 {
467 int index = bitmap_clear_first_set_bit (worklist);
468 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, index);
469 edge_iterator ei;
470 edge e;
471
472 /* With fake exit edges we can end up with no possible exit. */
473 if (index == EXIT_BLOCK)
474 {
475 DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
476 return invalid_sese;
477 }
478
479 bitmap_set_bit (in_sese_region, bb->index);
480
481 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
482 FOR_EACH_EDGE (e, ei, bb->preds)
483 if (e->src == dom
484 && (! entry
485 || dominated_by_p (CDI_DOMINATORS, entry->dest, bb)))
486 {
487 if (entry
488 && ! bitmap_bit_p (in_sese_region, entry->src->index))
489 bitmap_set_bit (worklist, entry->src->index);
490 entry = e;
491 }
492 else if (! bitmap_bit_p (in_sese_region, e->src->index))
493 bitmap_set_bit (worklist, e->src->index);
494
495 basic_block pdom = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
496 FOR_EACH_EDGE (e, ei, bb->succs)
497 if (e->dest == pdom
498 && (! exit
499 || dominated_by_p (CDI_POST_DOMINATORS, exit->src, bb)))
500 {
501 if (exit
502 && ! bitmap_bit_p (in_sese_region, exit->dest->index))
503 bitmap_set_bit (worklist, exit->dest->index);
504 exit = e;
505 }
506 else if (! bitmap_bit_p (in_sese_region, e->dest->index))
507 bitmap_set_bit (worklist, e->dest->index);
508 }
509 while (! bitmap_empty_p (worklist));
510
511 sese_l combined (entry, exit);
512
513 DEBUG_PRINT (dp << "[merged-sese] s1: "; print_sese (dump_file, combined));
514
515 return combined;
516}
517
518/* Print the loop numbers of the loops contained in SESE to FILE. */
519
520static void
521print_sese_loop_numbers (FILE *file, sese_l sese)
522{
523 bool first_loop = true;
524 for (loop_p nest = sese.entry->dest->loop_father; nest; nest = nest->next)
525 {
526 if (!loop_in_sese_p (nest, sese))
527 break;
528
529 for (auto loop : loops_list (cfun, LI_INCLUDE_ROOT, nest))
530 {
531 gcc_assert (loop_in_sese_p (loop, sese));
532
533 fprintf (file, "%s%d", first_loop ? "" : ", ", loop->num);
534 first_loop = false;
535 }
536 }
537}
538
539/* Build scop outer->inner if possible. */
540
541void
542scop_detection::build_scop_depth (loop_p loop)
543{
544 sese_l s = invalid_sese;
545 loop = loop->inner;
546 while (loop)
547 {
548 sese_l next = get_sese (loop);
549 if (! next
550 || harmful_loop_in_region (next))
551 {
552 if (next)
553 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 if (s)
557 add_scop (s);
558 build_scop_depth (loop);
559 s = invalid_sese;
560 }
561 else if (! s)
562 s = next;
563 else
564 {
565 sese_l combined = merge_sese (s, next);
566 if (! combined
567 || harmful_loop_in_region (combined))
568 {
569 add_scop (s);
570 s = next;
571 }
572 else
573 s = combined;
574 }
575 loop = loop->next;
576 }
577 if (s)
578 add_scop (s);
579}
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
585bool
586scop_detection::can_represent_loop (loop_p loop, sese_l scop)
587{
588 tree niter;
589 struct tree_niter_desc niter_desc;
590
591 /* We can only handle do {} while () style loops correctly. */
592 edge exit = single_exit (loop);
593 if (!exit
594 || !single_pred_p (loop->latch)
595 || exit->src != single_pred (loop->latch)
596 || !empty_block_p (loop->latch))
597 {
598 DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop shape unsupported.\n");
599 return false;
600 }
601
602 bool edge_irreducible = (loop_preheader_edge (loop)->flags
603 & EDGE_IRREDUCIBLE_LOOP);
604 if (edge_irreducible)
605 {
606 DEBUG_PRINT (dp << "[can_represent_loop-fail] "
607 "Loop is not a natural loop.\n");
608 return false;
609 }
610
611 bool niter_is_unconditional = number_of_iterations_exit (loop,
612 single_exit (loop),
613 &niter_desc, false);
614
615 if (!niter_is_unconditional)
616 {
617 DEBUG_PRINT (dp << "[can_represent_loop-fail] "
618 "Loop niter not unconditional.\n"
619 "Condition: " << niter_desc.assumptions << "\n");
620 return false;
621 }
622
623 niter = number_of_latch_executions (loop);
624 if (!niter)
625 {
626 DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop niter unknown.\n");
627 return false;
628 }
629 if (!niter_desc.control.no_overflow)
630 {
631 DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop niter can overflow.\n");
632 return false;
633 }
634
635 bool undetermined_coefficients = chrec_contains_undetermined (niter);
636 if (undetermined_coefficients)
637 {
638 DEBUG_PRINT (dp << "[can_represent_loop-fail] "
639 "Loop niter chrec contains undetermined "
640 "coefficients.\n");
641 return false;
642 }
643
644 bool can_represent_expr = graphite_can_represent_expr (scop, loop, niter);
645 if (!can_represent_expr)
646 {
647 DEBUG_PRINT (dp << "[can_represent_loop-fail] "
648 << "Loop niter expression cannot be represented: "
649 << niter << "\n");
650 return false;
651 }
652
653 return true;
654}
655
656/* Return true when BEGIN is the preheader edge of a loop with a single exit
657 END. */
658
659bool
660scop_detection::region_has_one_loop (sese_l s)
661{
662 edge begin = s.entry;
663 edge end = s.exit;
664 /* Check for a single perfectly nested loop. */
665 if (begin->dest->loop_father->inner)
666 return false;
667
668 /* Otherwise, check whether we have adjacent loops. */
669 return (single_pred_p (end->src)
670 && 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
675void
676scop_detection::add_scop (sese_l s)
677{
678 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 if (s.exit->flags & EDGE_FAKE)
683 {
684 DEBUG_PRINT (dp << "[scop-detection-fail] Discarding infinite loop SCoP: ";
685 print_sese (dump_file, s));
686 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 if (s.exit->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
693 && loop_exit_edge_p (s.exit->src->loop_father, s.exit))
694 {
695 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 s.exit = single_succ_edge (s.exit->dest);
699 }
700
701 /* Do not add scops with only one loop. */
702 if (region_has_one_loop (s))
703 {
704 DEBUG_PRINT (dp << "[scop-detection-fail] Discarding one loop SCoP: ";
705 print_sese (dump_file, s));
706 return;
707 }
708
709 if (get_exit_bb (s) == EXIT_BLOCK_PTR_FOR_FN (cfun))
710 {
711 DEBUG_PRINT (dp << "[scop-detection-fail] "
712 << "Discarding SCoP exiting to return: ";
713 print_sese (dump_file, s));
714 return;
715 }
716
717 /* Remove all the scops which are subsumed by s. */
718 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 remove_intersecting_scops (s);
723
724 scops.safe_push (s);
725 DEBUG_PRINT (dp << "[scop-detection] Adding SCoP: "; print_sese (dump_file, s));
726
727 if (dump_file && dump_flags & TDF_DETAILS)
728 {
729 fprintf (dump_file, "Loops in SCoP: ");
730 print_sese_loop_numbers (dump_file, s);
731 fprintf (dump_file, "\n");
732 }
733}
734
735/* Return true when a statement in SCOP cannot be represented by Graphite. */
736
737bool
738scop_detection::harmful_loop_in_region (sese_l scop) const
739{
740 basic_block exit_bb = get_exit_bb (scop);
741 basic_block entry_bb = get_entry_bb (scop);
742
743 DEBUG_PRINT (dp << "[checking-harmful-bbs] ";
744 print_sese (dump_file, scop));
745 gcc_assert (dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb));
746
747 auto_vec<basic_block> worklist;
748 auto_bitmap loops;
749
750 worklist.safe_push (entry_bb);
751 while (! worklist.is_empty ())
752 {
753 basic_block bb = worklist.pop ();
754 DEBUG_PRINT (dp << "Visiting bb_" << bb->index << "\n");
755
756 /* The basic block should not be part of an irreducible loop. */
757 if (bb->flags & BB_IRREDUCIBLE_LOOP)
758 {
759 DEBUG_PRINT (dp << "[scop-detection-fail] Found bb in irreducible "
760 "loop.\n");
761
762 return true;
763 }
764
765 /* Check for unstructured control flow: CFG not generated by structured
766 if-then-else. */
767 if (bb->succs->length () > 1)
768 {
769 edge e;
770 edge_iterator ei;
771 FOR_EACH_EDGE (e, ei, bb->succs)
772 if (!dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)
773 && !dominated_by_p (CDI_DOMINATORS, e->dest, bb))
774 {
775 DEBUG_PRINT (dp << "[scop-detection-fail] Found unstructured "
776 "control flow.\n");
777 return true;
778 }
779 }
780
781 /* Collect all loops in the current region. */
782 loop_p loop = bb->loop_father;
783 if (loop_in_sese_p (loop, scop))
784 bitmap_set_bit (loops, loop->num);
785
786 /* Check for harmful statements in basic blocks part of the region. */
787 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
788 !gsi_end_p (gsi); gsi_next (&gsi))
789 if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb))
790 {
791 DEBUG_PRINT (dp << "[scop-detection-fail] "
792 "Found harmful statement.\n");
793 return true;
794 }
795
796 for (basic_block dom = first_dom_son (CDI_DOMINATORS, bb);
797 dom;
798 dom = next_dom_son (CDI_DOMINATORS, dom))
799 if (dom != scop.exit->dest)
800 worklist.safe_push (dom);
801 }
802
803 /* Go through all loops and check that they are still valid in the combined
804 scop. */
805 unsigned j;
806 bitmap_iterator bi;
807 EXECUTE_IF_SET_IN_BITMAP (loops, 0, j, bi)
808 {
809 loop_p loop = (*current_loops->larray)[j];
810 gcc_assert (loop->num == (int) j);
811
812 /* Check if the loop nests are to be optimized for speed. */
813 if (! loop->inner
814 && ! optimize_loop_for_speed_p (loop))
815 {
816 DEBUG_PRINT (dp << "[scop-detection-fail] loop_"
817 << loop->num << " is not on a hot path.\n");
818 return true;
819 }
820
821 if (! can_represent_loop (loop, scop))
822 {
823 DEBUG_PRINT (dp << "[scop-detection-fail] cannot represent loop_"
824 << loop->num << "\n");
825 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 if (! loop->inner
834 && ! loop_nest_has_data_refs (loop))
835 {
836 DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
837 << " does not have any data reference.\n");
838 return true;
839 }
840 DEBUG_PRINT (dp << "[scop-detection] loop_" << loop->num << " is harmless.\n");
841 }
842
843 return false;
844}
845
846/* Returns true if S1 subsumes/surrounds S2. */
847bool
848scop_detection::subsumes (sese_l s1, sese_l s2)
849{
850 if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
851 get_entry_bb (s1))
852 && dominated_by_p (CDI_POST_DOMINATORS, s2.exit->dest,
853 s1.exit->dest))
854 return true;
855 return false;
856}
857
858/* Remove a SCoP which is subsumed by S1. */
859void
860scop_detection::remove_subscops (sese_l s1)
861{
862 int j;
863 sese_l *s2;
864 FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
865 {
866 if (subsumes (s1, *s2))
867 {
868 DEBUG_PRINT (dp << "Removing sub-SCoP";
869 print_sese (dump_file, *s2));
870 scops.unordered_remove (j);
871 }
872 }
873}
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
878bool
879scop_detection::intersects (sese_l s1, sese_l s2)
880{
881 if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
882 get_entry_bb (s1))
883 && !dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
884 get_exit_bb (s1)))
885 return true;
886 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
894void
895scop_detection::remove_intersecting_scops (sese_l s1)
896{
897 int j;
898 sese_l *s2;
899 FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
900 {
901 if (intersects (s1, *s2))
902 {
903 DEBUG_PRINT (dp << "Removing intersecting SCoP";
904 print_sese (dump_file, *s2);
905 dp << "Intersects with:";
906 print_sese (dump_file, s1));
907 scops.unordered_remove (j);
908 }
909 }
910}
911
912/* Something like "n * m" is not allowed. */
913
914bool
915scop_detection::graphite_can_represent_init (tree e)
916{
917 switch (TREE_CODE (e))
918 {
919 case POLYNOMIAL_CHREC:
920 return graphite_can_represent_init (CHREC_LEFT (e))
921 && graphite_can_represent_init (CHREC_RIGHT (e));
922
923 case MULT_EXPR:
924 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
925 return graphite_can_represent_init (TREE_OPERAND (e, 0))
926 && tree_fits_shwi_p (TREE_OPERAND (e, 1));
927 else
928 return graphite_can_represent_init (TREE_OPERAND (e, 1))
929 && tree_fits_shwi_p (TREE_OPERAND (e, 0));
930
931 case PLUS_EXPR:
932 case POINTER_PLUS_EXPR:
933 case MINUS_EXPR:
934 return graphite_can_represent_init (TREE_OPERAND (e, 0))
935 && graphite_can_represent_init (TREE_OPERAND (e, 1));
936
937 case NEGATE_EXPR:
938 case BIT_NOT_EXPR:
939 CASE_CONVERT:
940 case NON_LVALUE_EXPR:
941 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
962bool
963scop_detection::graphite_can_represent_scev (sese_l scop, tree scev)
964{
965 if (chrec_contains_undetermined (scev))
966 return false;
967
968 switch (TREE_CODE (scev))
969 {
970 case NEGATE_EXPR:
971 case BIT_NOT_EXPR:
972 CASE_CONVERT:
973 case NON_LVALUE_EXPR:
974 return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0));
975
976 case PLUS_EXPR:
977 case POINTER_PLUS_EXPR:
978 case MINUS_EXPR:
979 return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
980 && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
981
982 case MULT_EXPR:
983 return !CONVERT_EXPR_P (TREE_OPERAND (scev, 0))
984 && !CONVERT_EXPR_P (TREE_OPERAND (scev, 1))
985 && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
986 && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
987 && graphite_can_represent_init (scev)
988 && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
989 && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
990
991 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 gcc_assert (loop_in_sese_p (get_loop (cfun,
997 CHREC_VARIABLE (scev)), scop));
998 if (!evolution_function_right_is_integer_cst (scev)
999 || !graphite_can_represent_init (scev))
1000 return false;
1001 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 default:
1008 break;
1009 }
1010
1011 /* Only affine functions can be represented. */
1012 if (tree_contains_chrecs (scev, NULL) || !scev_is_linear_expression (scev))
1013 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
1024bool
1025scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop,
1026 tree expr)
1027{
1028 tree scev = cached_scalar_evolution_in_region (scop, loop, expr);
1029 bool can_represent = graphite_can_represent_scev (scop, scev);
1030
1031 if (!can_represent)
1032 {
1033 if (dump_file)
1034 {
1035 fprintf (dump_file,
1036 "[graphite_can_represent_expr] Cannot represent scev \"");
1037 print_generic_expr (dump_file, scev, TDF_SLIM);
1038 fprintf (dump_file, "\" of expression ");
1039 print_generic_expr (dump_file, expr, TDF_SLIM);
1040 fprintf (dump_file, " in loop %d\n", loop->num);
1041 }
1042 }
1043 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
1049bool
1050scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt)
1051{
1052 edge nest = scop.entry;
1053 loop_p loop = loop_containing_stmt (stmt);
1054 if (!loop_in_sese_p (loop, scop))
1055 loop = NULL;
1056
1057 auto_vec<data_reference_p> drs;
1058 if (! graphite_find_data_references_in_stmt (nest, loop, stmt, &drs))
1059 {
1060 DEBUG_PRINT (dp << "[stmt_has_simple_data_refs_p] "
1061 "Unanalyzable statement.\n");
1062 return false;
1063 }
1064
1065 int j;
1066 data_reference_p dr;
1067 FOR_EACH_VEC_ELT (drs, j, dr)
1068 {
1069 for (unsigned i = 0; i < DR_NUM_DIMENSIONS (dr); ++i)
1070 if (! graphite_can_represent_scev (scop, DR_ACCESS_FN (dr, i)))
1071 {
1072 DEBUG_PRINT (dp << "[stmt_has_simple_data_refs_p] "
1073 "Cannot represent access function SCEV: "
1074 << DR_ACCESS_FN (dr, i) << "\n");
1075 return false;
1076 }
1077 }
1078
1079 return true;
1080}
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
1086static bool
1087stmt_has_side_effects (gimple *stmt)
1088{
1089 if (gimple_has_volatile_ops (stmt)
1090 || (gimple_code (stmt) == GIMPLE_CALL
1091 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
1092 || (gimple_code (stmt) == GIMPLE_ASM))
1093 {
1094 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 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
1108bool
1109scop_detection::stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
1110 basic_block bb) const
1111{
1112 gcc_assert (scop);
1113
1114 if (is_gimple_debug (stmt))
1115 return true;
1116
1117 if (stmt_has_side_effects (stmt))
1118 return false;
1119
1120 if (!stmt_has_simple_data_refs_p (scop, stmt))
1121 {
1122 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 return false;
1126 }
1127
1128 switch (gimple_code (stmt))
1129 {
1130 case GIMPLE_LABEL:
1131 return true;
1132
1133 case GIMPLE_COND:
1134 {
1135 /* We can handle all binary comparisons. Inequalities are
1136 also supported as they can be represented with union of
1137 polyhedra. */
1138 enum tree_code code = gimple_cond_code (stmt);
1139 if (!(code == LT_EXPR
1140 || code == GT_EXPR
1141 || code == LE_EXPR
1142 || code == GE_EXPR
1143 || code == EQ_EXPR
1144 || code == NE_EXPR))
1145 {
1146 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 return false;
1151 }
1152
1153 loop_p loop = bb->loop_father;
1154 for (unsigned i = 0; i < 2; ++i)
1155 {
1156 tree op = gimple_op (stmt, i);
1157 if (!graphite_can_represent_expr (scop, loop, op))
1158 {
1159 DEBUG_PRINT (dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmt,
1160 "[scop-detection-fail] "
1161 "Graphite cannot represent cond "
1162 "stmt operator expression.\n"));
1163 DEBUG_PRINT (dp << op << "\n");
1164 return false;
1165 }
1166
1167 if (! INTEGRAL_TYPE_P (TREE_TYPE (op)))
1168 {
1169 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 return false;
1175 }
1176 }
1177
1178 return true;
1179 }
1180
1181 case GIMPLE_ASSIGN:
1182 case GIMPLE_CALL:
1183 {
1184 tree op, lhs = gimple_get_lhs (stmt);
1185 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 if (lhs
1189 && TREE_CODE (lhs) == SSA_NAME
1190 && 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 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
1195 if (scev_analyzable_p (op, scop)
1196 && chrec_contains_undetermined
1197 (cached_scalar_evolution_in_region (scop,
1198 bb->loop_father, op)))
1199 {
1200 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 return false;
1205 }
1206 return true;
1207 }
1208
1209 default:
1210 /* These nodes cut a new scope. */
1211 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
1221int
1222scop_detection::nb_pbbs_in_loops (scop_p scop)
1223{
1224 int i;
1225 poly_bb_p pbb;
1226 int res = 0;
1227
1228 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1229 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), scop->scop_info->region))
1230 res++;
1231
1232 return res;
1233}
1234
1235/* Assigns the parameter NAME an index in REGION. */
1236
1237static void
1238assign_parameter_index_in_region (tree name, sese_info_p region)
1239{
1240 gcc_assert (TREE_CODE (name) == SSA_NAME
1241 && ! defined_in_sese_p (name, region->region));
1242 int i;
1243 tree p;
1244 FOR_EACH_VEC_ELT (region->params, i, p)
1245 if (p == name)
1246 return;
1247
1248 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
1256static void
1257scan_tree_for_params (sese_info_p s, tree e)
1258{
1259 if (e == chrec_dont_know)
1260 return;
1261
1262 switch (TREE_CODE (e))
1263 {
1264 case POLYNOMIAL_CHREC:
1265 scan_tree_for_params (s, CHREC_LEFT (e));
1266 break;
1267
1268 case MULT_EXPR:
1269 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
1270 scan_tree_for_params (s, TREE_OPERAND (e, 0));
1271 else
1272 scan_tree_for_params (s, TREE_OPERAND (e, 1));
1273 break;
1274
1275 case PLUS_EXPR:
1276 case POINTER_PLUS_EXPR:
1277 case MINUS_EXPR:
1278 scan_tree_for_params (s, TREE_OPERAND (e, 0));
1279 scan_tree_for_params (s, TREE_OPERAND (e, 1));
1280 break;
1281
1282 case NEGATE_EXPR:
1283 case BIT_NOT_EXPR:
1284 CASE_CONVERT:
1285 case NON_LVALUE_EXPR:
1286 scan_tree_for_params (s, TREE_OPERAND (e, 0));
1287 break;
1288
1289 case SSA_NAME:
1290 assign_parameter_index_in_region (e, s);
1291 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 default:
1301 gcc_unreachable ();
1302 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
1309static void
1310find_params_in_bb (sese_info_p region, gimple_poly_bb_p gbb)
1311{
1312 /* Find parameters in the access functions of data references. */
1313 int i;
1314 data_reference_p dr;
1315 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb), i, dr)
1316 for (unsigned j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
1317 scan_tree_for_params (region, DR_ACCESS_FN (dr, j));
1318
1319 /* Find parameters in conditional statements. */
1320 gimple *stmt;
1321 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
1322 {
1323 loop_p loop = gimple_bb (stmt)->loop_father;
1324 tree lhs = cached_scalar_evolution_in_region (region->region, loop,
1325 gimple_cond_lhs (stmt));
1326 tree rhs = cached_scalar_evolution_in_region (region->region, loop,
1327 gimple_cond_rhs (stmt));
1328 gcc_assert (!chrec_contains_undetermined (lhs)
1329 && !chrec_contains_undetermined (rhs));
1330
1331 scan_tree_for_params (region, lhs);
1332 scan_tree_for_params (region, rhs);
1333 }
1334}
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
1339static void
1340find_scop_parameters (scop_p scop)
1341{
1342 unsigned i;
1343 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 poly_bb_p pbb;
1349 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1350 find_params_in_bb (region, PBB_BLACK_BOX (pbb));
1351
1352 int nbp = sese_nb_params (region);
1353 scop_set_nb_params (scop, nbp);
1354}
1355
1356static void
1357add_write (vec<tree> *writes, tree def)
1358{
1359 writes->safe_push (def);
1360 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}
1366
1367static void
1368add_read (vec<scalar_use> *reads, tree use, gimple *use_stmt)
1369{
1370 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 reads->safe_push (std::make_pair (use_stmt, use));
1375}
1376
1377
1378/* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1379
1380static void
1381build_cross_bb_scalars_def (scop_p scop, tree def, basic_block def_bb,
1382 vec<tree> *writes)
1383{
1384 if (!is_gimple_reg (def))
1385 return;
1386
1387 bool scev_analyzable = scev_analyzable_p (def, scop->scop_info->region);
1388
1389 gimple *use_stmt;
1390 imm_use_iterator imm_iter;
1391 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 if ((! scev_analyzable
1395 /* But gather SESE liveouts as we otherwise fail to rewrite their
1396 exit PHIs. */
1397 || ! bb_in_sese_p (gimple_bb (use_stmt), scop->scop_info->region))
1398 && (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt)))
1399 {
1400 add_write (writes, def);
1401 break;
1402 }
1403}
1404
1405/* Record USE if it is defined in other bbs different than USE_STMT
1406 in the SCOP. */
1407
1408static void
1409build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt,
1410 vec<scalar_use> *reads)
1411{
1412 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 if (scev_analyzable_p (use, scop->scop_info->region))
1418 return;
1419
1420 gimple *def_stmt = SSA_NAME_DEF_STMT (use);
1421 if (gimple_bb (def_stmt) != gimple_bb (use_stmt))
1422 add_read (reads, use, use_stmt);
1423}
1424
1425/* Generates a polyhedral black box only if the bb contains interesting
1426 information. */
1427
1428static gimple_poly_bb_p
1429try_generate_gimple_bb (scop_p scop, basic_block bb)
1430{
1431 vec<data_reference_p> drs = vNULL;
1432 vec<tree> writes = vNULL;
1433 vec<scalar_use> reads = vNULL;
1434
1435 sese_l region = scop->scop_info->region;
1436 edge nest = region.entry;
1437 loop_p loop = bb->loop_father;
1438 if (!loop_in_sese_p (loop, region))
1439 loop = NULL;
1440
1441 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1442 gsi_next (&gsi))
1443 {
1444 gimple *stmt = gsi_stmt (gsi);
1445 if (is_gimple_debug (stmt))
1446 continue;
1447
1448 graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
1449
1450 tree def = gimple_get_lhs (stmt);
1451 if (def)
1452 build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), &writes);
1453
1454 ssa_op_iter iter;
1455 tree use;
1456 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1457 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 for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
1464 gsi_next (&psi))
1465 {
1466 gphi *phi = psi.phi ();
1467 tree res = gimple_phi_result (phi);
1468 if (virtual_operand_p (res)
1469 || scev_analyzable_p (res, scop->scop_info->region))
1470 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 add_read (&reads, res, phi);
1476 add_write (&writes, res);
1477 }
1478 basic_block bb_for_succs = bb;
1479 if (bb_for_succs == bb_for_succs->loop_father->latch
1480 && bb_in_sese_p (bb_for_succs, scop->scop_info->region)
1481 && sese_trivially_empty_bb_p (bb_for_succs))
1482 bb_for_succs = NULL;
1483 while (bb_for_succs)
1484 {
1485 basic_block latch = NULL;
1486 edge_iterator ei;
1487 edge e;
1488 FOR_EACH_EDGE (e, ei, bb_for_succs->succs)
1489 {
1490 for (gphi_iterator psi = gsi_start_phis (e->dest); !gsi_end_p (psi);
1491 gsi_next (&psi))
1492 {
1493 gphi *phi = psi.phi ();
1494 tree res = gimple_phi_result (phi);
1495 if (virtual_operand_p (res))
1496 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 if (! scev_analyzable_p (res, scop->scop_info->region))
1500 add_write (&writes, res);
1501 tree use = PHI_ARG_DEF_FROM_EDGE (phi, e);
1502 if (TREE_CODE (use) == SSA_NAME
1503 && ! SSA_NAME_IS_DEFAULT_DEF (use)
1504 && gimple_bb (SSA_NAME_DEF_STMT (use)) != bb_for_succs
1505 && ! scev_analyzable_p (use, scop->scop_info->region))
1506 add_read (&reads, use, phi);
1507 }
1508 if (e->dest == bb_for_succs->loop_father->latch
1509 && bb_in_sese_p (e->dest, scop->scop_info->region)
1510 && sese_trivially_empty_bb_p (e->dest))
1511 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 bb_for_succs = latch;
1518 }
1519
1520 /* For the region exit block add reads for all live-out vars. */
1521 if (bb == scop->scop_info->region.exit->src)
1522 {
1523 sese_build_liveouts (scop->scop_info);
1524 unsigned i;
1525 bitmap_iterator bi;
1526 EXECUTE_IF_SET_IN_BITMAP (scop->scop_info->liveout, 0, i, bi)
1527 {
1528 tree use = ssa_name (i);
1529 add_read (&reads, use, NULL);
1530 }
1531 }
1532
1533 if (drs.is_empty () && writes.is_empty () && reads.is_empty ())
1534 return NULL;
1535
1536 return new_gimple_poly_bb (bb, drs, reads, writes);
1537}
1538
1539/* Compute alias-sets for all data references in DRS. */
1540
1541static bool
1542build_alias_set (scop_p scop)
1543{
1544 int num_vertices = scop->drs.length ();
1545 struct graph *g = new_graph (num_vertices);
1546 dr_info *dr1, *dr2;
1547 int i, j;
1548 int *all_vertices;
1549
1550 struct loop *nest
1551 = find_common_loop (scop->scop_info->region.entry->dest->loop_father,
1552 scop->scop_info->region.exit->src->loop_father);
1553
1554 FOR_EACH_VEC_ELT (scop->drs, i, dr1)
1555 for (j = i+1; scop->drs.iterate (j, &dr2); j++)
1556 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 if (DR_NUM_DIMENSIONS (dr1->dr) == 0
1561 || DR_NUM_DIMENSIONS (dr1->dr) != DR_NUM_DIMENSIONS (dr2->dr)
1562 || ! operand_equal_p (DR_BASE_OBJECT (dr1->dr),
1563 DR_BASE_OBJECT (dr2->dr),
1564 OEP_ADDRESS_OF)
1565 || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1->dr)),
1566 TREE_TYPE (DR_BASE_OBJECT (dr2->dr))))
1567 {
1568 free_graph (g);
1569 return false;
1570 }
1571 add_edge (g, i, j);
1572 add_edge (g, j, i);
1573 }
1574
1575 all_vertices = XNEWVEC (int, num_vertices);
1576 for (i = 0; i < num_vertices; i++)
1577 all_vertices[i] = i;
1578
1579 scop->max_alias_set
1580 = graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + 1;
1581 free (all_vertices);
1582
1583 for (i = 0; i < g->n_vertices; i++)
1584 scop->drs[i].alias_set = g->vertices[i].component + 1;
1585
1586 free_graph (g);
1587 return true;
1588}
1589
1590/* Gather BBs and conditions for a SCOP. */
1591class gather_bbs : public dom_walker
1592{
1593public:
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
1599private:
1600 auto_vec<gimple *, 3> conditions, cases;
1601 scop_p scop;
1602};
1603}
1604gather_bbs::gather_bbs (cdi_direction direction, scop_p scop, int *bb_to_rpo)
1605 : dom_walker (direction, ALL_BLOCKS, bb_to_rpo), scop (scop)
1606{
1607}
1608
1609/* Call-back for dom_walk executed before visiting the dominated
1610 blocks. */
1611
1612edge
1613gather_bbs::before_dom_children (basic_block bb)
1614{
1615 sese_info_p region = scop->scop_info;
1616 if (!bb_in_sese_p (bb, region->region))
1617 return dom_walker::STOP;
1618
1619 /* For loops fully contained in the region record parameters in the
1620 loop bounds. */
1621 loop_p loop = bb->loop_father;
1622 if (loop->header == bb
1623 && loop_in_sese_p (loop, region->region))
1624 {
1625 tree nb_iters = number_of_latch_executions (loop);
1626 if (chrec_contains_symbols (nb_iters))
1627 {
1628 nb_iters = cached_scalar_evolution_in_region (region->region,
1629 loop, nb_iters);
1630 scan_tree_for_params (region, nb_iters);
1631 }
1632 }
1633
1634 if (gcond *stmt = single_pred_cond_non_loop_exit (bb))
1635 {
1636 edge e = single_pred_edge (bb);
1637 /* Make sure the condition is in the region and thus was verified
1638 to be handled. */
1639 if (e != region->region.entry)
1640 {
1641 conditions.safe_push (stmt);
1642 if (e->flags & EDGE_TRUE_VALUE)
1643 cases.safe_push (stmt);
1644 else
1645 cases.safe_push (NULL);
1646 }
1647 }
1648
1649 scop->scop_info->bbs.safe_push (bb);
1650
1651 gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb);
1652 if (!gbb)
1653 return NULL;
1654
1655 GBB_CONDITIONS (gbb) = conditions.copy ();
1656 GBB_CONDITION_CASES (gbb) = cases.copy ();
1657
1658 poly_bb_p pbb = new_poly_bb (scop, gbb);
1659 scop->pbbs.safe_push (pbb);
1660
1661 int i;
1662 data_reference_p dr;
1663 FOR_EACH_VEC_ELT (gbb->data_refs, i, dr)
1664 {
1665 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 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
1683void
1684gather_bbs::after_dom_children (basic_block bb)
1685{
1686 if (!bb_in_sese_p (bb, scop->scop_info->region))
1687 return;
1688
1689 if (single_pred_cond_non_loop_exit (bb))
1690 {
1691 edge e = single_pred_edge (bb);
1692 if (e != scop->scop_info->region.entry)
1693 {
1694 conditions.pop ();
1695 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
1704static int *bb_to_rpo;
1705
1706/* Helper for qsort, sorting after order above. */
1707
1708static int
1709cmp_pbbs (const void *pa, const void *pb)
1710{
1711 poly_bb_p bb1 = *((const poly_bb_p *)pa);
1712 poly_bb_p bb2 = *((const poly_bb_p *)pb);
1713 if (bb_to_rpo[bb1->black_box->bb->index]
1714 < bb_to_rpo[bb2->black_box->bb->index])
1715 return -1;
1716 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 return 0;
1721}
1722
1723/* Find Static Control Parts (SCoP) in the current function and pushes
1724 them to SCOPS. */
1725
1726void
1727build_scops (vec<scop_p> *scops)
1728{
1729 if (dump_file)
1730 dp.set_dump_file (dump_file);
1731
1732 scop_detection sb;
1733 sb.build_scop_depth (current_loops->tree_root);
1734
1735 /* Now create scops from the lightweight SESEs. */
1736 vec<sese_l> scops_l = sb.get_scops ();
1737
1738 /* Domwalk needs a bb to RPO mapping. Compute it once here. */
1739 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
1740 int postorder_num = pre_and_rev_post_order_compute (NULL, postorder, true);
1741 bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
1742 for (int i = 0; i < postorder_num; ++i)
1743 bb_to_rpo[postorder[i]] = i;
1744 free (postorder);
1745
1746 int i;
1747 sese_l *s;
1748 FOR_EACH_VEC_ELT (scops_l, i, s)
1749 {
1750 scop_p scop = new_scop (s->entry, s->exit);
1751
1752 /* Record all basic blocks and their conditions in REGION. */
1753 gather_bbs (CDI_DOMINATORS, scop, bb_to_rpo).walk (s->entry->dest);
1754
1755 /* Sort pbbs after execution order for initial schedule generation. */
1756 scop->pbbs.qsort (cmp_pbbs);
1757
1758 if (! build_alias_set (scop))
1759 {
1760 DEBUG_PRINT (dp << "[scop-detection-fail] cannot handle dependences\n");
1761 free_scop (scop);
1762 continue;
1763 }
1764
1765 /* Do not optimize a scop containing only PBBs that do not belong
1766 to any loops. */
1767 if (sb.nb_pbbs_in_loops (scop) == 0)
1768 {
1769 DEBUG_PRINT (dp << "[scop-detection-fail] no data references.\n");
1770 free_scop (scop);
1771 continue;
1772 }
1773
1774 unsigned max_arrays = param_graphite_max_arrays_per_scop;
1775 if (max_arrays > 0
1776 && scop->drs.length () >= max_arrays)
1777 {
1778 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 free_scop (scop);
1783 continue;
1784 }
1785
1786 find_scop_parameters (scop);
1787 graphite_dim_t max_dim = param_graphite_max_nb_scop_params;
1788 if (max_dim > 0
1789 && scop_nb_params (scop) > max_dim)
1790 {
1791 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 free_scop (scop);
1796 continue;
1797 }
1798
1799 scops->safe_push (scop);
1800 }
1801
1802 free (bb_to_rpo);
1803 bb_to_rpo = NULL;
1804 DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0););
1805}
1806
1807#endif /* HAVE_isl */
1808

source code of gcc/graphite-scop-detection.cc