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