d: Merge upstream dmd, druntime c8ae4adb2e, phobos 792c8b7c1.
[official-gcc.git] / gcc / graphite-scop-detection.cc
blob9792d87ee0ae2d750b8e16fac4b07ace0b29ad8a
1 /* Detection of Static Control Parts (SCoP) for Graphite.
2 Copyright (C) 2009-2022 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and
4 Tobias Grosser <grosser@fim.uni-passau.de>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 #define INCLUDE_ISL
24 #include "config.h"
26 #ifdef HAVE_isl
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"
53 class debug_printer
55 private:
56 FILE *dump_file;
58 public:
59 void
60 set_dump_file (FILE *f)
62 gcc_assert (f);
63 dump_file = f;
66 friend debug_printer &
67 operator<< (debug_printer &output, int i)
69 fprintf (output.dump_file, "%d", i);
70 return output;
73 friend debug_printer &
74 operator<< (debug_printer &output, const char *s)
76 fprintf (output.dump_file, "%s", s);
77 return output;
80 friend debug_printer &
81 operator<< (debug_printer &output, gimple* stmt)
83 print_gimple_stmt (output.dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS);
84 return output;
87 friend debug_printer &
88 operator<< (debug_printer &output, tree t)
90 print_generic_expr (output.dump_file, t, TDF_SLIM);
91 return output;
93 } dp;
95 #define DEBUG_PRINT(args) do \
96 { \
97 if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \
98 } while (0)
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.
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. */
110 DEBUG_FUNCTION void
111 dot_all_sese (FILE *file, vec<sese_l>& scops)
113 /* Disable debugging while printing graph. */
114 dump_flags_t tmp_dump_flags = dump_flags;
115 dump_flags = TDF_NONE;
117 fprintf (file, "digraph all {\n");
119 basic_block bb;
120 FOR_ALL_BB_FN (bb, cfun)
122 int part_of_scop = false;
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");
131 /* Select color for SCoP. */
132 sese_l *region;
133 int i;
134 FOR_EACH_VEC_ELT (scops, i, region)
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))
140 const char *color;
141 switch (i % 17)
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";
198 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
199 color);
201 if (!sese_in_region)
202 fprintf (file, " (");
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);
213 fprintf (file, "{lp_%d}", bb->loop_father->num);
215 if (!sese_in_region)
216 fprintf (file, ")");
218 fprintf (file, "</TD></TR>\n");
219 part_of_scop = true;
223 if (!part_of_scop)
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);
229 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
232 FOR_ALL_BB_FN (bb, cfun)
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);
240 fputs ("}\n\n", file);
242 /* Enable debugging again. */
243 dump_flags = tmp_dump_flags;
246 /* Display SCoP on stderr. */
248 DEBUG_FUNCTION void
249 dot_sese (sese_l& scop)
251 vec<sese_l> scops;
252 scops.create (1);
254 if (scop)
255 scops.safe_push (scop);
257 dot_all_sese (stderr, scops);
259 scops.release ();
262 DEBUG_FUNCTION void
263 dot_cfg ()
265 vec<sese_l> scops;
266 scops.create (1);
267 dot_all_sese (stderr, scops);
268 scops.release ();
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. */
275 static gcond *
276 single_pred_cond_non_loop_exit (basic_block bb)
278 if (single_pred_p (bb))
280 edge e = single_pred_edge (bb);
281 basic_block pred = e->src;
282 gimple *stmt;
284 if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
285 return NULL;
287 stmt = last_stmt (pred);
289 if (stmt && gimple_code (stmt) == GIMPLE_COND)
290 return as_a<gcond *> (stmt);
293 return NULL;
296 namespace
299 /* Build the maximal scop containing LOOPs and add it to SCOPS. */
301 class scop_detection
303 public:
304 scop_detection () : scops (vNULL) {}
306 ~scop_detection ()
308 scops.release ();
311 /* A marker for invalid sese_l. */
312 static sese_l invalid_sese;
314 /* Return the SCOPS in this SCOP_DETECTION. */
316 vec<sese_l>
317 get_scops ()
319 return scops;
322 /* Return an sese_l around the LOOP. */
324 sese_l get_sese (loop_p loop);
326 /* Merge scops at same loop depth and returns the new sese.
327 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
329 sese_l merge_sese (sese_l first, sese_l second) const;
331 /* Build scop outer->inner if possible. */
333 void build_scop_depth (loop_p loop);
335 /* Return true when BEGIN is the preheader edge of a loop with a single exit
336 END. */
338 static bool region_has_one_loop (sese_l s);
340 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
342 void add_scop (sese_l s);
344 /* Returns true if S1 subsumes/surrounds S2. */
345 static bool subsumes (sese_l s1, sese_l s2);
347 /* Remove a SCoP which is subsumed by S1. */
348 void remove_subscops (sese_l s1);
350 /* Returns true if S1 intersects with S2. Since we already know that S1 does
351 not subsume S2 or vice-versa, we only check for entry bbs. */
353 static bool intersects (sese_l s1, sese_l s2);
355 /* Remove one of the scops when it intersects with any other. */
357 void remove_intersecting_scops (sese_l s1);
359 /* Return true when a statement in SCOP cannot be represented by Graphite. */
361 bool harmful_loop_in_region (sese_l scop) const;
363 /* Return true only when STMT is simple enough for being handled by Graphite.
364 This depends on SCOP, as the parameters are initialized relatively to
365 this basic block, the linear functions are initialized based on the
366 outermost loop containing STMT inside the SCOP. BB is the place where we
367 try to evaluate the STMT. */
369 bool stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
370 basic_block bb) const;
372 /* Something like "n * m" is not allowed. */
374 static bool graphite_can_represent_init (tree e);
376 /* Return true when SCEV can be represented in the polyhedral model.
378 An expression can be represented, if it can be expressed as an
379 affine expression. For loops (i, j) and parameters (m, n) all
380 affine expressions are of the form:
382 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
384 1 i + 20 j + (-2) m + 25
386 Something like "i * n" or "n * m" is not allowed. */
388 static bool graphite_can_represent_scev (sese_l scop, tree scev);
390 /* Return true when EXPR can be represented in the polyhedral model.
392 This means an expression can be represented, if it is linear with respect
393 to the loops and the strides are non parametric. LOOP is the place where
394 the expr will be evaluated. SCOP defines the region we analyse. */
396 static bool graphite_can_represent_expr (sese_l scop, loop_p loop,
397 tree expr);
399 /* Return true if the data references of STMT can be represented by Graphite.
400 We try to analyze the data references in a loop contained in the SCOP. */
402 static bool stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt);
404 /* Remove the close phi node at GSI and replace its rhs with the rhs
405 of PHI. */
407 static void remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi);
409 /* Returns true when Graphite can represent LOOP in SCOP.
410 FIXME: For the moment, graphite cannot be used on loops that iterate using
411 induction variables that wrap. */
413 static bool can_represent_loop (loop_p loop, sese_l scop);
415 /* Returns the number of pbbs that are in loops contained in SCOP. */
417 static int nb_pbbs_in_loops (scop_p scop);
419 private:
420 vec<sese_l> scops;
423 sese_l scop_detection::invalid_sese (NULL, NULL);
425 /* Return an sese_l around the LOOP. */
427 sese_l
428 scop_detection::get_sese (loop_p loop)
430 if (!loop)
431 return invalid_sese;
433 edge scop_begin = loop_preheader_edge (loop);
434 edge scop_end = single_exit (loop);
435 if (!scop_end || (scop_end->flags & (EDGE_COMPLEX|EDGE_FAKE)))
436 return invalid_sese;
438 return sese_l (scop_begin, scop_end);
441 /* Merge scops at same loop depth and returns the new sese.
442 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
444 sese_l
445 scop_detection::merge_sese (sese_l first, sese_l second) const
447 /* In the trivial case first/second may be NULL. */
448 if (!first)
449 return second;
450 if (!second)
451 return first;
453 DEBUG_PRINT (dp << "[scop-detection] try merging sese s1: ";
454 print_sese (dump_file, first);
455 dp << "[scop-detection] try merging sese s2: ";
456 print_sese (dump_file, second));
458 auto_bitmap worklist, in_sese_region;
459 bitmap_set_bit (worklist, get_entry_bb (first)->index);
460 bitmap_set_bit (worklist, get_exit_bb (first)->index);
461 bitmap_set_bit (worklist, get_entry_bb (second)->index);
462 bitmap_set_bit (worklist, get_exit_bb (second)->index);
463 edge entry = NULL, exit = NULL;
465 /* We can optimize the case of adding a loop entry dest or exit
466 src to the worklist (for single-exit loops) by skipping
467 directly to the exit dest / entry src. in_sese_region
468 doesn't have to cover all blocks in the region but merely
469 its border it acts more like a visited bitmap. */
472 int index = bitmap_first_set_bit (worklist);
473 bitmap_clear_bit (worklist, index);
474 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, index);
475 edge_iterator ei;
476 edge e;
478 /* With fake exit edges we can end up with no possible exit. */
479 if (index == EXIT_BLOCK)
481 DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
482 return invalid_sese;
485 bitmap_set_bit (in_sese_region, bb->index);
487 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
488 FOR_EACH_EDGE (e, ei, bb->preds)
489 if (e->src == dom
490 && (! entry
491 || dominated_by_p (CDI_DOMINATORS, entry->dest, bb)))
493 if (entry
494 && ! bitmap_bit_p (in_sese_region, entry->src->index))
495 bitmap_set_bit (worklist, entry->src->index);
496 entry = e;
498 else if (! bitmap_bit_p (in_sese_region, e->src->index))
499 bitmap_set_bit (worklist, e->src->index);
501 basic_block pdom = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
502 FOR_EACH_EDGE (e, ei, bb->succs)
503 if (e->dest == pdom
504 && (! exit
505 || dominated_by_p (CDI_POST_DOMINATORS, exit->src, bb)))
507 if (exit
508 && ! bitmap_bit_p (in_sese_region, exit->dest->index))
509 bitmap_set_bit (worklist, exit->dest->index);
510 exit = e;
512 else if (! bitmap_bit_p (in_sese_region, e->dest->index))
513 bitmap_set_bit (worklist, e->dest->index);
515 while (! bitmap_empty_p (worklist));
517 sese_l combined (entry, exit);
519 DEBUG_PRINT (dp << "[merged-sese] s1: "; print_sese (dump_file, combined));
521 return combined;
524 /* Print the loop numbers of the loops contained in SESE to FILE. */
526 static void
527 print_sese_loop_numbers (FILE *file, sese_l sese)
529 bool first_loop = true;
530 for (loop_p nest = sese.entry->dest->loop_father; nest; nest = nest->next)
532 if (!loop_in_sese_p (nest, sese))
533 break;
535 for (auto loop : loops_list (cfun, LI_INCLUDE_ROOT, nest))
537 gcc_assert (loop_in_sese_p (loop, sese));
539 fprintf (file, "%s%d", first_loop ? "" : ", ", loop->num);
540 first_loop = false;
545 /* Build scop outer->inner if possible. */
547 void
548 scop_detection::build_scop_depth (loop_p loop)
550 sese_l s = invalid_sese;
551 loop = loop->inner;
552 while (loop)
554 sese_l next = get_sese (loop);
555 if (! next
556 || harmful_loop_in_region (next))
558 if (next)
559 DEBUG_PRINT (dp << "[scop-detection] Discarding SCoP on loops ";
560 print_sese_loop_numbers (dump_file, next);
561 dp << " because of harmful loops\n");
562 if (s)
563 add_scop (s);
564 build_scop_depth (loop);
565 s = invalid_sese;
567 else if (! s)
568 s = next;
569 else
571 sese_l combined = merge_sese (s, next);
572 if (! combined
573 || harmful_loop_in_region (combined))
575 add_scop (s);
576 s = next;
578 else
579 s = combined;
581 loop = loop->next;
583 if (s)
584 add_scop (s);
587 /* Returns true when Graphite can represent LOOP in SCOP.
588 FIXME: For the moment, graphite cannot be used on loops that iterate using
589 induction variables that wrap. */
591 bool
592 scop_detection::can_represent_loop (loop_p loop, sese_l scop)
594 tree niter;
595 struct tree_niter_desc niter_desc;
597 /* We can only handle do {} while () style loops correctly. */
598 edge exit = single_exit (loop);
599 if (!exit
600 || !single_pred_p (loop->latch)
601 || exit->src != single_pred (loop->latch)
602 || !empty_block_p (loop->latch))
604 DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop shape unsupported.\n");
605 return false;
608 bool edge_irreducible = (loop_preheader_edge (loop)->flags
609 & EDGE_IRREDUCIBLE_LOOP);
610 if (edge_irreducible)
612 DEBUG_PRINT (dp << "[can_represent_loop-fail] "
613 "Loop is not a natural loop.\n");
614 return false;
617 bool niter_is_unconditional = number_of_iterations_exit (loop,
618 single_exit (loop),
619 &niter_desc, false);
621 if (!niter_is_unconditional)
623 DEBUG_PRINT (dp << "[can_represent_loop-fail] "
624 "Loop niter not unconditional.\n"
625 "Condition: " << niter_desc.assumptions << "\n");
626 return false;
629 niter = number_of_latch_executions (loop);
630 if (!niter)
632 DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop niter unknown.\n");
633 return false;
635 if (!niter_desc.control.no_overflow)
637 DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop niter can overflow.\n");
638 return false;
641 bool undetermined_coefficients = chrec_contains_undetermined (niter);
642 if (undetermined_coefficients)
644 DEBUG_PRINT (dp << "[can_represent_loop-fail] "
645 "Loop niter chrec contains undetermined "
646 "coefficients.\n");
647 return false;
650 bool can_represent_expr = graphite_can_represent_expr (scop, loop, niter);
651 if (!can_represent_expr)
653 DEBUG_PRINT (dp << "[can_represent_loop-fail] "
654 << "Loop niter expression cannot be represented: "
655 << niter << "\n");
656 return false;
659 return true;
662 /* Return true when BEGIN is the preheader edge of a loop with a single exit
663 END. */
665 bool
666 scop_detection::region_has_one_loop (sese_l s)
668 edge begin = s.entry;
669 edge end = s.exit;
670 /* Check for a single perfectly nested loop. */
671 if (begin->dest->loop_father->inner)
672 return false;
674 /* Otherwise, check whether we have adjacent loops. */
675 return (single_pred_p (end->src)
676 && begin->dest->loop_father == single_pred (end->src)->loop_father);
679 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
681 void
682 scop_detection::add_scop (sese_l s)
684 gcc_assert (s);
686 /* If the exit edge is fake discard the SCoP for now as we're removing the
687 fake edges again after analysis. */
688 if (s.exit->flags & EDGE_FAKE)
690 DEBUG_PRINT (dp << "[scop-detection-fail] Discarding infinite loop SCoP: ";
691 print_sese (dump_file, s));
692 return;
695 /* Include the BB with the loop-closed SSA PHI nodes, we need this
696 block in the region for code-generating out-of-SSA copies.
697 canonicalize_loop_closed_ssa makes sure that is in proper shape. */
698 if (s.exit->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
699 && loop_exit_edge_p (s.exit->src->loop_father, s.exit))
701 gcc_assert (single_pred_p (s.exit->dest)
702 && single_succ_p (s.exit->dest)
703 && sese_trivially_empty_bb_p (s.exit->dest));
704 s.exit = single_succ_edge (s.exit->dest);
707 /* Do not add scops with only one loop. */
708 if (region_has_one_loop (s))
710 DEBUG_PRINT (dp << "[scop-detection-fail] Discarding one loop SCoP: ";
711 print_sese (dump_file, s));
712 return;
715 if (get_exit_bb (s) == EXIT_BLOCK_PTR_FOR_FN (cfun))
717 DEBUG_PRINT (dp << "[scop-detection-fail] "
718 << "Discarding SCoP exiting to return: ";
719 print_sese (dump_file, s));
720 return;
723 /* Remove all the scops which are subsumed by s. */
724 remove_subscops (s);
726 /* Remove intersecting scops. FIXME: It will be a good idea to keep
727 the non-intersecting part of the scop already in the list. */
728 remove_intersecting_scops (s);
730 scops.safe_push (s);
731 DEBUG_PRINT (dp << "[scop-detection] Adding SCoP: "; print_sese (dump_file, s));
733 if (dump_file && dump_flags & TDF_DETAILS)
735 fprintf (dump_file, "Loops in SCoP: ");
736 print_sese_loop_numbers (dump_file, s);
737 fprintf (dump_file, "\n");
741 /* Return true when a statement in SCOP cannot be represented by Graphite. */
743 bool
744 scop_detection::harmful_loop_in_region (sese_l scop) const
746 basic_block exit_bb = get_exit_bb (scop);
747 basic_block entry_bb = get_entry_bb (scop);
749 DEBUG_PRINT (dp << "[checking-harmful-bbs] ";
750 print_sese (dump_file, scop));
751 gcc_assert (dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb));
753 auto_vec<basic_block> worklist;
754 auto_bitmap loops;
756 worklist.safe_push (entry_bb);
757 while (! worklist.is_empty ())
759 basic_block bb = worklist.pop ();
760 DEBUG_PRINT (dp << "Visiting bb_" << bb->index << "\n");
762 /* The basic block should not be part of an irreducible loop. */
763 if (bb->flags & BB_IRREDUCIBLE_LOOP)
765 DEBUG_PRINT (dp << "[scop-detection-fail] Found bb in irreducible "
766 "loop.\n");
768 return true;
771 /* Check for unstructured control flow: CFG not generated by structured
772 if-then-else. */
773 if (bb->succs->length () > 1)
775 edge e;
776 edge_iterator ei;
777 FOR_EACH_EDGE (e, ei, bb->succs)
778 if (!dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)
779 && !dominated_by_p (CDI_DOMINATORS, e->dest, bb))
781 DEBUG_PRINT (dp << "[scop-detection-fail] Found unstructured "
782 "control flow.\n");
783 return true;
787 /* Collect all loops in the current region. */
788 loop_p loop = bb->loop_father;
789 if (loop_in_sese_p (loop, scop))
790 bitmap_set_bit (loops, loop->num);
792 /* Check for harmful statements in basic blocks part of the region. */
793 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
794 !gsi_end_p (gsi); gsi_next (&gsi))
795 if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb))
797 DEBUG_PRINT (dp << "[scop-detection-fail] "
798 "Found harmful statement.\n");
799 return true;
802 for (basic_block dom = first_dom_son (CDI_DOMINATORS, bb);
803 dom;
804 dom = next_dom_son (CDI_DOMINATORS, dom))
805 if (dom != scop.exit->dest)
806 worklist.safe_push (dom);
809 /* Go through all loops and check that they are still valid in the combined
810 scop. */
811 unsigned j;
812 bitmap_iterator bi;
813 EXECUTE_IF_SET_IN_BITMAP (loops, 0, j, bi)
815 loop_p loop = (*current_loops->larray)[j];
816 gcc_assert (loop->num == (int) j);
818 /* Check if the loop nests are to be optimized for speed. */
819 if (! loop->inner
820 && ! optimize_loop_for_speed_p (loop))
822 DEBUG_PRINT (dp << "[scop-detection-fail] loop_"
823 << loop->num << " is not on a hot path.\n");
824 return true;
827 if (! can_represent_loop (loop, scop))
829 DEBUG_PRINT (dp << "[scop-detection-fail] cannot represent loop_"
830 << loop->num << "\n");
831 return true;
834 /* Check if all loop nests have at least one data reference.
835 ??? This check is expensive and loops premature at this point.
836 If important to retain we can pre-compute this for all innermost
837 loops and reject those when we build a SESE region for a loop
838 during SESE discovery. */
839 if (! loop->inner
840 && ! loop_nest_has_data_refs (loop))
842 DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
843 << " does not have any data reference.\n");
844 return true;
846 DEBUG_PRINT (dp << "[scop-detection] loop_" << loop->num << " is harmless.\n");
849 return false;
852 /* Returns true if S1 subsumes/surrounds S2. */
853 bool
854 scop_detection::subsumes (sese_l s1, sese_l s2)
856 if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
857 get_entry_bb (s1))
858 && dominated_by_p (CDI_POST_DOMINATORS, s2.exit->dest,
859 s1.exit->dest))
860 return true;
861 return false;
864 /* Remove a SCoP which is subsumed by S1. */
865 void
866 scop_detection::remove_subscops (sese_l s1)
868 int j;
869 sese_l *s2;
870 FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
872 if (subsumes (s1, *s2))
874 DEBUG_PRINT (dp << "Removing sub-SCoP";
875 print_sese (dump_file, *s2));
876 scops.unordered_remove (j);
881 /* Returns true if S1 intersects with S2. Since we already know that S1 does
882 not subsume S2 or vice-versa, we only check for entry bbs. */
884 bool
885 scop_detection::intersects (sese_l s1, sese_l s2)
887 if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
888 get_entry_bb (s1))
889 && !dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
890 get_exit_bb (s1)))
891 return true;
892 if ((s1.exit == s2.entry) || (s2.exit == s1.entry))
893 return true;
895 return false;
898 /* Remove one of the scops when it intersects with any other. */
900 void
901 scop_detection::remove_intersecting_scops (sese_l s1)
903 int j;
904 sese_l *s2;
905 FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
907 if (intersects (s1, *s2))
909 DEBUG_PRINT (dp << "Removing intersecting SCoP";
910 print_sese (dump_file, *s2);
911 dp << "Intersects with:";
912 print_sese (dump_file, s1));
913 scops.unordered_remove (j);
918 /* Something like "n * m" is not allowed. */
920 bool
921 scop_detection::graphite_can_represent_init (tree e)
923 switch (TREE_CODE (e))
925 case POLYNOMIAL_CHREC:
926 return graphite_can_represent_init (CHREC_LEFT (e))
927 && graphite_can_represent_init (CHREC_RIGHT (e));
929 case MULT_EXPR:
930 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
931 return graphite_can_represent_init (TREE_OPERAND (e, 0))
932 && tree_fits_shwi_p (TREE_OPERAND (e, 1));
933 else
934 return graphite_can_represent_init (TREE_OPERAND (e, 1))
935 && tree_fits_shwi_p (TREE_OPERAND (e, 0));
937 case PLUS_EXPR:
938 case POINTER_PLUS_EXPR:
939 case MINUS_EXPR:
940 return graphite_can_represent_init (TREE_OPERAND (e, 0))
941 && graphite_can_represent_init (TREE_OPERAND (e, 1));
943 case NEGATE_EXPR:
944 case BIT_NOT_EXPR:
945 CASE_CONVERT:
946 case NON_LVALUE_EXPR:
947 return graphite_can_represent_init (TREE_OPERAND (e, 0));
949 default:
950 break;
953 return true;
956 /* Return true when SCEV can be represented in the polyhedral model.
958 An expression can be represented, if it can be expressed as an
959 affine expression. For loops (i, j) and parameters (m, n) all
960 affine expressions are of the form:
962 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
964 1 i + 20 j + (-2) m + 25
966 Something like "i * n" or "n * m" is not allowed. */
968 bool
969 scop_detection::graphite_can_represent_scev (sese_l scop, tree scev)
971 if (chrec_contains_undetermined (scev))
972 return false;
974 switch (TREE_CODE (scev))
976 case NEGATE_EXPR:
977 case BIT_NOT_EXPR:
978 CASE_CONVERT:
979 case NON_LVALUE_EXPR:
980 return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0));
982 case PLUS_EXPR:
983 case POINTER_PLUS_EXPR:
984 case MINUS_EXPR:
985 return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
986 && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
988 case MULT_EXPR:
989 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
990 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
991 && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
992 && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
993 && graphite_can_represent_init (scev)
994 && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
995 && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
997 case POLYNOMIAL_CHREC:
998 /* Check for constant strides. With a non constant stride of
999 'n' we would have a value of 'iv * n'. Also check that the
1000 initial value can represented: for example 'n * m' cannot be
1001 represented. */
1002 gcc_assert (loop_in_sese_p (get_loop (cfun,
1003 CHREC_VARIABLE (scev)), scop));
1004 if (!evolution_function_right_is_integer_cst (scev)
1005 || !graphite_can_represent_init (scev))
1006 return false;
1007 return graphite_can_represent_scev (scop, CHREC_LEFT (scev));
1009 case ADDR_EXPR:
1010 /* We cannot encode addresses for ISL. */
1011 return false;
1013 default:
1014 break;
1017 /* Only affine functions can be represented. */
1018 if (tree_contains_chrecs (scev, NULL) || !scev_is_linear_expression (scev))
1019 return false;
1021 return true;
1024 /* Return true when EXPR can be represented in the polyhedral model.
1026 This means an expression can be represented, if it is linear with respect to
1027 the loops and the strides are non parametric. LOOP is the place where the
1028 expr will be evaluated. SCOP defines the region we analyse. */
1030 bool
1031 scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop,
1032 tree expr)
1034 tree scev = cached_scalar_evolution_in_region (scop, loop, expr);
1035 bool can_represent = graphite_can_represent_scev (scop, scev);
1037 if (!can_represent)
1039 if (dump_file)
1041 fprintf (dump_file,
1042 "[graphite_can_represent_expr] Cannot represent scev \"");
1043 print_generic_expr (dump_file, scev, TDF_SLIM);
1044 fprintf (dump_file, "\" of expression ");
1045 print_generic_expr (dump_file, expr, TDF_SLIM);
1046 fprintf (dump_file, " in loop %d\n", loop->num);
1049 return can_represent;
1052 /* Return true if the data references of STMT can be represented by Graphite.
1053 We try to analyze the data references in a loop contained in the SCOP. */
1055 bool
1056 scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt)
1058 edge nest = scop.entry;
1059 loop_p loop = loop_containing_stmt (stmt);
1060 if (!loop_in_sese_p (loop, scop))
1061 loop = NULL;
1063 auto_vec<data_reference_p> drs;
1064 if (! graphite_find_data_references_in_stmt (nest, loop, stmt, &drs))
1066 DEBUG_PRINT (dp << "[stmt_has_simple_data_refs_p] "
1067 "Unanalyzable statement.\n");
1068 return false;
1071 int j;
1072 data_reference_p dr;
1073 FOR_EACH_VEC_ELT (drs, j, dr)
1075 for (unsigned i = 0; i < DR_NUM_DIMENSIONS (dr); ++i)
1076 if (! graphite_can_represent_scev (scop, DR_ACCESS_FN (dr, i)))
1078 DEBUG_PRINT (dp << "[stmt_has_simple_data_refs_p] "
1079 "Cannot represent access function SCEV: "
1080 << DR_ACCESS_FN (dr, i) << "\n");
1081 return false;
1085 return true;
1088 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1089 Calls have side-effects, except those to const or pure
1090 functions. */
1092 static bool
1093 stmt_has_side_effects (gimple *stmt)
1095 if (gimple_has_volatile_ops (stmt)
1096 || (gimple_code (stmt) == GIMPLE_CALL
1097 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
1098 || (gimple_code (stmt) == GIMPLE_ASM))
1100 DEBUG_PRINT (dp << "[scop-detection-fail] "
1101 << "Statement has side-effects:\n";
1102 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
1103 return true;
1105 return false;
1108 /* Return true only when STMT is simple enough for being handled by Graphite.
1109 This depends on SCOP, as the parameters are initialized relatively to
1110 this basic block, the linear functions are initialized based on the outermost
1111 loop containing STMT inside the SCOP. BB is the place where we try to
1112 evaluate the STMT. */
1114 bool
1115 scop_detection::stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
1116 basic_block bb) const
1118 gcc_assert (scop);
1120 if (is_gimple_debug (stmt))
1121 return true;
1123 if (stmt_has_side_effects (stmt))
1124 return false;
1126 if (!stmt_has_simple_data_refs_p (scop, stmt))
1128 DEBUG_PRINT (dp << "[scop-detection-fail] "
1129 << "Graphite cannot handle data-refs in stmt:\n";
1130 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS););
1131 return false;
1134 switch (gimple_code (stmt))
1136 case GIMPLE_LABEL:
1137 return true;
1139 case GIMPLE_COND:
1141 /* We can handle all binary comparisons. Inequalities are
1142 also supported as they can be represented with union of
1143 polyhedra. */
1144 enum tree_code code = gimple_cond_code (stmt);
1145 if (!(code == LT_EXPR
1146 || code == GT_EXPR
1147 || code == LE_EXPR
1148 || code == GE_EXPR
1149 || code == EQ_EXPR
1150 || code == NE_EXPR))
1152 DEBUG_PRINT (dp << "[scop-detection-fail] "
1153 << "Graphite cannot handle cond stmt:\n";
1154 print_gimple_stmt (dump_file, stmt, 0,
1155 TDF_VOPS | TDF_MEMSYMS));
1156 return false;
1159 loop_p loop = bb->loop_father;
1160 for (unsigned i = 0; i < 2; ++i)
1162 tree op = gimple_op (stmt, i);
1163 if (!graphite_can_represent_expr (scop, loop, op))
1165 DEBUG_PRINT (dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmt,
1166 "[scop-detection-fail] "
1167 "Graphite cannot represent cond "
1168 "stmt operator expression.\n"));
1169 DEBUG_PRINT (dp << op << "\n");
1170 return false;
1173 if (! INTEGRAL_TYPE_P (TREE_TYPE (op)))
1175 DEBUG_PRINT (dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmt,
1176 "[scop-detection-fail] "
1177 "Graphite cannot represent cond "
1178 "statement operator. "
1179 "Type must be integral.\n"));
1180 return false;
1184 return true;
1187 case GIMPLE_ASSIGN:
1188 case GIMPLE_CALL:
1190 tree op, lhs = gimple_get_lhs (stmt);
1191 ssa_op_iter i;
1192 /* If we are not going to instantiate the stmt do not require
1193 its operands to be instantiatable at this point. */
1194 if (lhs
1195 && TREE_CODE (lhs) == SSA_NAME
1196 && scev_analyzable_p (lhs, scop))
1197 return true;
1198 /* Verify that if we can analyze operands at their def site we
1199 also can represent them when analyzed at their uses. */
1200 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
1201 if (scev_analyzable_p (op, scop)
1202 && chrec_contains_undetermined
1203 (cached_scalar_evolution_in_region (scop,
1204 bb->loop_father, op)))
1206 DEBUG_PRINT (dp << "[scop-detection-fail] "
1207 << "Graphite cannot code-gen stmt:\n";
1208 print_gimple_stmt (dump_file, stmt, 0,
1209 TDF_VOPS | TDF_MEMSYMS));
1210 return false;
1212 return true;
1215 default:
1216 /* These nodes cut a new scope. */
1217 DEBUG_PRINT (
1218 dp << "[scop-detection-fail] "
1219 << "Gimple stmt not handled in Graphite:\n";
1220 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
1221 return false;
1225 /* Returns the number of pbbs that are in loops contained in SCOP. */
1228 scop_detection::nb_pbbs_in_loops (scop_p scop)
1230 int i;
1231 poly_bb_p pbb;
1232 int res = 0;
1234 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1235 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), scop->scop_info->region))
1236 res++;
1238 return res;
1241 /* Assigns the parameter NAME an index in REGION. */
1243 static void
1244 assign_parameter_index_in_region (tree name, sese_info_p region)
1246 gcc_assert (TREE_CODE (name) == SSA_NAME
1247 && ! defined_in_sese_p (name, region->region));
1248 int i;
1249 tree p;
1250 FOR_EACH_VEC_ELT (region->params, i, p)
1251 if (p == name)
1252 return;
1254 region->params.safe_push (name);
1257 /* In the context of sese S, scan the expression E and translate it to
1258 a linear expression C. When parsing a symbolic multiplication, K
1259 represents the constant multiplier of an expression containing
1260 parameters. */
1262 static void
1263 scan_tree_for_params (sese_info_p s, tree e)
1265 if (e == chrec_dont_know)
1266 return;
1268 switch (TREE_CODE (e))
1270 case POLYNOMIAL_CHREC:
1271 scan_tree_for_params (s, CHREC_LEFT (e));
1272 break;
1274 case MULT_EXPR:
1275 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
1276 scan_tree_for_params (s, TREE_OPERAND (e, 0));
1277 else
1278 scan_tree_for_params (s, TREE_OPERAND (e, 1));
1279 break;
1281 case PLUS_EXPR:
1282 case POINTER_PLUS_EXPR:
1283 case MINUS_EXPR:
1284 scan_tree_for_params (s, TREE_OPERAND (e, 0));
1285 scan_tree_for_params (s, TREE_OPERAND (e, 1));
1286 break;
1288 case NEGATE_EXPR:
1289 case BIT_NOT_EXPR:
1290 CASE_CONVERT:
1291 case NON_LVALUE_EXPR:
1292 scan_tree_for_params (s, TREE_OPERAND (e, 0));
1293 break;
1295 case SSA_NAME:
1296 assign_parameter_index_in_region (e, s);
1297 break;
1299 case INTEGER_CST:
1300 case ADDR_EXPR:
1301 case REAL_CST:
1302 case COMPLEX_CST:
1303 case VECTOR_CST:
1304 break;
1306 default:
1307 gcc_unreachable ();
1308 break;
1312 /* Find parameters with respect to REGION in BB. We are looking in memory
1313 access functions, conditions and loop bounds. */
1315 static void
1316 find_params_in_bb (sese_info_p region, gimple_poly_bb_p gbb)
1318 /* Find parameters in the access functions of data references. */
1319 int i;
1320 data_reference_p dr;
1321 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb), i, dr)
1322 for (unsigned j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
1323 scan_tree_for_params (region, DR_ACCESS_FN (dr, j));
1325 /* Find parameters in conditional statements. */
1326 gimple *stmt;
1327 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
1329 loop_p loop = gimple_bb (stmt)->loop_father;
1330 tree lhs = cached_scalar_evolution_in_region (region->region, loop,
1331 gimple_cond_lhs (stmt));
1332 tree rhs = cached_scalar_evolution_in_region (region->region, loop,
1333 gimple_cond_rhs (stmt));
1334 gcc_assert (!chrec_contains_undetermined (lhs)
1335 && !chrec_contains_undetermined (rhs));
1337 scan_tree_for_params (region, lhs);
1338 scan_tree_for_params (region, rhs);
1342 /* Record the parameters used in the SCOP BBs. A variable is a parameter
1343 in a scop if it does not vary during the execution of that scop. */
1345 static void
1346 find_scop_parameters (scop_p scop)
1348 unsigned i;
1349 sese_info_p region = scop->scop_info;
1351 /* Parameters used in loop bounds are processed during gather_bbs. */
1353 /* Find the parameters used in data accesses. */
1354 poly_bb_p pbb;
1355 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1356 find_params_in_bb (region, PBB_BLACK_BOX (pbb));
1358 int nbp = sese_nb_params (region);
1359 scop_set_nb_params (scop, nbp);
1362 static void
1363 add_write (vec<tree> *writes, tree def)
1365 writes->safe_push (def);
1366 DEBUG_PRINT (dp << "Adding scalar write: ";
1367 print_generic_expr (dump_file, def);
1368 dp << "\nFrom stmt: ";
1369 print_gimple_stmt (dump_file,
1370 SSA_NAME_DEF_STMT (def), 0));
1373 static void
1374 add_read (vec<scalar_use> *reads, tree use, gimple *use_stmt)
1376 DEBUG_PRINT (dp << "Adding scalar read: ";
1377 print_generic_expr (dump_file, use);
1378 dp << "\nFrom stmt: ";
1379 print_gimple_stmt (dump_file, use_stmt, 0));
1380 reads->safe_push (std::make_pair (use_stmt, use));
1384 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1386 static void
1387 build_cross_bb_scalars_def (scop_p scop, tree def, basic_block def_bb,
1388 vec<tree> *writes)
1390 if (!is_gimple_reg (def))
1391 return;
1393 bool scev_analyzable = scev_analyzable_p (def, scop->scop_info->region);
1395 gimple *use_stmt;
1396 imm_use_iterator imm_iter;
1397 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
1398 /* Do not gather scalar variables that can be analyzed by SCEV as they can
1399 be generated out of the induction variables. */
1400 if ((! scev_analyzable
1401 /* But gather SESE liveouts as we otherwise fail to rewrite their
1402 exit PHIs. */
1403 || ! bb_in_sese_p (gimple_bb (use_stmt), scop->scop_info->region))
1404 && (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt)))
1406 add_write (writes, def);
1407 break;
1411 /* Record USE if it is defined in other bbs different than USE_STMT
1412 in the SCOP. */
1414 static void
1415 build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt,
1416 vec<scalar_use> *reads)
1418 if (!is_gimple_reg (use))
1419 return;
1421 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1422 generated out of the induction variables. */
1423 if (scev_analyzable_p (use, scop->scop_info->region))
1424 return;
1426 gimple *def_stmt = SSA_NAME_DEF_STMT (use);
1427 if (gimple_bb (def_stmt) != gimple_bb (use_stmt))
1428 add_read (reads, use, use_stmt);
1431 /* Generates a polyhedral black box only if the bb contains interesting
1432 information. */
1434 static gimple_poly_bb_p
1435 try_generate_gimple_bb (scop_p scop, basic_block bb)
1437 vec<data_reference_p> drs = vNULL;
1438 vec<tree> writes = vNULL;
1439 vec<scalar_use> reads = vNULL;
1441 sese_l region = scop->scop_info->region;
1442 edge nest = region.entry;
1443 loop_p loop = bb->loop_father;
1444 if (!loop_in_sese_p (loop, region))
1445 loop = NULL;
1447 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1448 gsi_next (&gsi))
1450 gimple *stmt = gsi_stmt (gsi);
1451 if (is_gimple_debug (stmt))
1452 continue;
1454 graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
1456 tree def = gimple_get_lhs (stmt);
1457 if (def)
1458 build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), &writes);
1460 ssa_op_iter iter;
1461 tree use;
1462 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1463 build_cross_bb_scalars_use (scop, use, stmt, &reads);
1466 /* Handle defs and uses in PHIs. Those need special treatment given
1467 that we have to present ISL with sth that looks like we've rewritten
1468 the IL out-of-SSA. */
1469 for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
1470 gsi_next (&psi))
1472 gphi *phi = psi.phi ();
1473 tree res = gimple_phi_result (phi);
1474 if (virtual_operand_p (res)
1475 || scev_analyzable_p (res, scop->scop_info->region))
1476 continue;
1477 /* To simulate out-of-SSA the block containing the PHI node has
1478 reads of the PHI destination. And to preserve SSA dependences
1479 we also write to it (the out-of-SSA decl and the SSA result
1480 are coalesced for dependence purposes which is good enough). */
1481 add_read (&reads, res, phi);
1482 add_write (&writes, res);
1484 basic_block bb_for_succs = bb;
1485 if (bb_for_succs == bb_for_succs->loop_father->latch
1486 && bb_in_sese_p (bb_for_succs, scop->scop_info->region)
1487 && sese_trivially_empty_bb_p (bb_for_succs))
1488 bb_for_succs = NULL;
1489 while (bb_for_succs)
1491 basic_block latch = NULL;
1492 edge_iterator ei;
1493 edge e;
1494 FOR_EACH_EDGE (e, ei, bb_for_succs->succs)
1496 for (gphi_iterator psi = gsi_start_phis (e->dest); !gsi_end_p (psi);
1497 gsi_next (&psi))
1499 gphi *phi = psi.phi ();
1500 tree res = gimple_phi_result (phi);
1501 if (virtual_operand_p (res))
1502 continue;
1503 /* To simulate out-of-SSA the predecessor of edges into PHI nodes
1504 has a copy from the PHI argument to the PHI destination. */
1505 if (! scev_analyzable_p (res, scop->scop_info->region))
1506 add_write (&writes, res);
1507 tree use = PHI_ARG_DEF_FROM_EDGE (phi, e);
1508 if (TREE_CODE (use) == SSA_NAME
1509 && ! SSA_NAME_IS_DEFAULT_DEF (use)
1510 && gimple_bb (SSA_NAME_DEF_STMT (use)) != bb_for_succs
1511 && ! scev_analyzable_p (use, scop->scop_info->region))
1512 add_read (&reads, use, phi);
1514 if (e->dest == bb_for_succs->loop_father->latch
1515 && bb_in_sese_p (e->dest, scop->scop_info->region)
1516 && sese_trivially_empty_bb_p (e->dest))
1517 latch = e->dest;
1519 /* Handle empty latch block PHIs here, otherwise we confuse ISL
1520 with extra conditional code where it then peels off the last
1521 iteration just because of that. It would be simplest if we
1522 just didn't force simple latches (thus remove the forwarder). */
1523 bb_for_succs = latch;
1526 /* For the region exit block add reads for all live-out vars. */
1527 if (bb == scop->scop_info->region.exit->src)
1529 sese_build_liveouts (scop->scop_info);
1530 unsigned i;
1531 bitmap_iterator bi;
1532 EXECUTE_IF_SET_IN_BITMAP (scop->scop_info->liveout, 0, i, bi)
1534 tree use = ssa_name (i);
1535 add_read (&reads, use, NULL);
1539 if (drs.is_empty () && writes.is_empty () && reads.is_empty ())
1540 return NULL;
1542 return new_gimple_poly_bb (bb, drs, reads, writes);
1545 /* Compute alias-sets for all data references in DRS. */
1547 static bool
1548 build_alias_set (scop_p scop)
1550 int num_vertices = scop->drs.length ();
1551 struct graph *g = new_graph (num_vertices);
1552 dr_info *dr1, *dr2;
1553 int i, j;
1554 int *all_vertices;
1556 struct loop *nest
1557 = find_common_loop (scop->scop_info->region.entry->dest->loop_father,
1558 scop->scop_info->region.exit->src->loop_father);
1560 FOR_EACH_VEC_ELT (scop->drs, i, dr1)
1561 for (j = i+1; scop->drs.iterate (j, &dr2); j++)
1562 if (dr_may_alias_p (dr1->dr, dr2->dr, nest))
1564 /* Dependences in the same alias set need to be handled
1565 by just looking at DR_ACCESS_FNs. */
1566 if (DR_NUM_DIMENSIONS (dr1->dr) == 0
1567 || DR_NUM_DIMENSIONS (dr1->dr) != DR_NUM_DIMENSIONS (dr2->dr)
1568 || ! operand_equal_p (DR_BASE_OBJECT (dr1->dr),
1569 DR_BASE_OBJECT (dr2->dr),
1570 OEP_ADDRESS_OF)
1571 || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1->dr)),
1572 TREE_TYPE (DR_BASE_OBJECT (dr2->dr))))
1574 free_graph (g);
1575 return false;
1577 add_edge (g, i, j);
1578 add_edge (g, j, i);
1581 all_vertices = XNEWVEC (int, num_vertices);
1582 for (i = 0; i < num_vertices; i++)
1583 all_vertices[i] = i;
1585 scop->max_alias_set
1586 = graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + 1;
1587 free (all_vertices);
1589 for (i = 0; i < g->n_vertices; i++)
1590 scop->drs[i].alias_set = g->vertices[i].component + 1;
1592 free_graph (g);
1593 return true;
1596 /* Gather BBs and conditions for a SCOP. */
1597 class gather_bbs : public dom_walker
1599 public:
1600 gather_bbs (cdi_direction, scop_p, int *);
1602 virtual edge before_dom_children (basic_block);
1603 virtual void after_dom_children (basic_block);
1605 private:
1606 auto_vec<gimple *, 3> conditions, cases;
1607 scop_p scop;
1610 gather_bbs::gather_bbs (cdi_direction direction, scop_p scop, int *bb_to_rpo)
1611 : dom_walker (direction, ALL_BLOCKS, bb_to_rpo), scop (scop)
1615 /* Call-back for dom_walk executed before visiting the dominated
1616 blocks. */
1618 edge
1619 gather_bbs::before_dom_children (basic_block bb)
1621 sese_info_p region = scop->scop_info;
1622 if (!bb_in_sese_p (bb, region->region))
1623 return dom_walker::STOP;
1625 /* For loops fully contained in the region record parameters in the
1626 loop bounds. */
1627 loop_p loop = bb->loop_father;
1628 if (loop->header == bb
1629 && loop_in_sese_p (loop, region->region))
1631 tree nb_iters = number_of_latch_executions (loop);
1632 if (chrec_contains_symbols (nb_iters))
1634 nb_iters = cached_scalar_evolution_in_region (region->region,
1635 loop, nb_iters);
1636 scan_tree_for_params (region, nb_iters);
1640 if (gcond *stmt = single_pred_cond_non_loop_exit (bb))
1642 edge e = single_pred_edge (bb);
1643 /* Make sure the condition is in the region and thus was verified
1644 to be handled. */
1645 if (e != region->region.entry)
1647 conditions.safe_push (stmt);
1648 if (e->flags & EDGE_TRUE_VALUE)
1649 cases.safe_push (stmt);
1650 else
1651 cases.safe_push (NULL);
1655 scop->scop_info->bbs.safe_push (bb);
1657 gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb);
1658 if (!gbb)
1659 return NULL;
1661 GBB_CONDITIONS (gbb) = conditions.copy ();
1662 GBB_CONDITION_CASES (gbb) = cases.copy ();
1664 poly_bb_p pbb = new_poly_bb (scop, gbb);
1665 scop->pbbs.safe_push (pbb);
1667 int i;
1668 data_reference_p dr;
1669 FOR_EACH_VEC_ELT (gbb->data_refs, i, dr)
1671 DEBUG_PRINT (dp << "Adding memory ";
1672 if (dr->is_read)
1673 dp << "read: ";
1674 else
1675 dp << "write: ";
1676 print_generic_expr (dump_file, dr->ref);
1677 dp << "\nFrom stmt: ";
1678 print_gimple_stmt (dump_file, dr->stmt, 0));
1680 scop->drs.safe_push (dr_info (dr, pbb));
1683 return NULL;
1686 /* Call-back for dom_walk executed after visiting the dominated
1687 blocks. */
1689 void
1690 gather_bbs::after_dom_children (basic_block bb)
1692 if (!bb_in_sese_p (bb, scop->scop_info->region))
1693 return;
1695 if (single_pred_cond_non_loop_exit (bb))
1697 edge e = single_pred_edge (bb);
1698 if (e != scop->scop_info->region.entry)
1700 conditions.pop ();
1701 cases.pop ();
1707 /* Compute sth like an execution order, dominator order with first executing
1708 edges that stay inside the current loop, delaying processing exit edges. */
1710 static int *bb_to_rpo;
1712 /* Helper for qsort, sorting after order above. */
1714 static int
1715 cmp_pbbs (const void *pa, const void *pb)
1717 poly_bb_p bb1 = *((const poly_bb_p *)pa);
1718 poly_bb_p bb2 = *((const poly_bb_p *)pb);
1719 if (bb_to_rpo[bb1->black_box->bb->index]
1720 < bb_to_rpo[bb2->black_box->bb->index])
1721 return -1;
1722 else if (bb_to_rpo[bb1->black_box->bb->index]
1723 > bb_to_rpo[bb2->black_box->bb->index])
1724 return 1;
1725 else
1726 return 0;
1729 /* Find Static Control Parts (SCoP) in the current function and pushes
1730 them to SCOPS. */
1732 void
1733 build_scops (vec<scop_p> *scops)
1735 if (dump_file)
1736 dp.set_dump_file (dump_file);
1738 scop_detection sb;
1739 sb.build_scop_depth (current_loops->tree_root);
1741 /* Now create scops from the lightweight SESEs. */
1742 vec<sese_l> scops_l = sb.get_scops ();
1744 /* Domwalk needs a bb to RPO mapping. Compute it once here. */
1745 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
1746 int postorder_num = pre_and_rev_post_order_compute (NULL, postorder, true);
1747 bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
1748 for (int i = 0; i < postorder_num; ++i)
1749 bb_to_rpo[postorder[i]] = i;
1750 free (postorder);
1752 int i;
1753 sese_l *s;
1754 FOR_EACH_VEC_ELT (scops_l, i, s)
1756 scop_p scop = new_scop (s->entry, s->exit);
1758 /* Record all basic blocks and their conditions in REGION. */
1759 gather_bbs (CDI_DOMINATORS, scop, bb_to_rpo).walk (s->entry->dest);
1761 /* Sort pbbs after execution order for initial schedule generation. */
1762 scop->pbbs.qsort (cmp_pbbs);
1764 if (! build_alias_set (scop))
1766 DEBUG_PRINT (dp << "[scop-detection-fail] cannot handle dependences\n");
1767 free_scop (scop);
1768 continue;
1771 /* Do not optimize a scop containing only PBBs that do not belong
1772 to any loops. */
1773 if (sb.nb_pbbs_in_loops (scop) == 0)
1775 DEBUG_PRINT (dp << "[scop-detection-fail] no data references.\n");
1776 free_scop (scop);
1777 continue;
1780 unsigned max_arrays = param_graphite_max_arrays_per_scop;
1781 if (max_arrays > 0
1782 && scop->drs.length () >= max_arrays)
1784 DEBUG_PRINT (dp << "[scop-detection-fail] too many data references: "
1785 << scop->drs.length ()
1786 << " is larger than --param graphite-max-arrays-per-scop="
1787 << max_arrays << ".\n");
1788 free_scop (scop);
1789 continue;
1792 find_scop_parameters (scop);
1793 graphite_dim_t max_dim = param_graphite_max_nb_scop_params;
1794 if (max_dim > 0
1795 && scop_nb_params (scop) > max_dim)
1797 DEBUG_PRINT (dp << "[scop-detection-fail] too many parameters: "
1798 << scop_nb_params (scop)
1799 << " larger than --param graphite-max-nb-scop-params="
1800 << max_dim << ".\n");
1801 free_scop (scop);
1802 continue;
1805 scops->safe_push (scop);
1808 free (bb_to_rpo);
1809 bb_to_rpo = NULL;
1810 DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0););
1813 #endif /* HAVE_isl */