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>.
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)
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/>. */
29 #include "coretypes.h"
37 #include "fold-const.h"
38 #include "gimple-iterator.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"
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"
61 set_dump_file (FILE *f
)
67 friend debug_printer
&
68 operator<< (debug_printer
&output
, int i
)
70 fprintf (output
.dump_file
, "%d", i
);
73 friend debug_printer
&
74 operator<< (debug_printer
&output
, const char *s
)
76 fprintf (output
.dump_file
, "%s", s
);
81 #define DEBUG_PRINT(args) do \
83 if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \
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.
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. */
97 dot_all_sese (FILE *file
, vec
<sese_l
>& scops
)
99 /* Disable debugging while printing graph. */
100 dump_flags_t tmp_dump_flags
= dump_flags
;
101 dump_flags
= TDF_NONE
;
103 fprintf (file
, "digraph all {\n");
106 FOR_ALL_BB_FN (bb
, cfun
)
108 int part_of_scop
= false;
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\" ",
115 fprintf (file
, "CELLSPACING=\"0\">\n");
117 /* Select color for SCoP. */
120 FOR_EACH_VEC_ELT (scops
, i
, region
)
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
))
184 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
188 fprintf (file
, " (");
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
);
197 fprintf (file
, " %d ", bb
->index
);
199 fprintf (file
, "{lp_%d}", bb
->loop_father
->num
);
204 fprintf (file
, "</TD></TR>\n");
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
);
215 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
218 FOR_ALL_BB_FN (bb
, cfun
)
222 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
223 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
226 fputs ("}\n\n", file
);
228 /* Enable debugging again. */
229 dump_flags
= tmp_dump_flags
;
232 /* Display SCoP on stderr. */
235 dot_sese (sese_l
& scop
)
241 scops
.safe_push (scop
);
243 dot_all_sese (stderr
, scops
);
253 dot_all_sese (stderr
, scops
);
257 /* Return true if BB is empty, contains only DEBUG_INSNs. */
260 trivially_empty_bb_p (basic_block bb
)
262 gimple_stmt_iterator gsi
;
264 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
265 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_DEBUG
266 && gimple_code (gsi_stmt (gsi
)) != GIMPLE_LABEL
)
272 /* Can all ivs be represented by a signed integer?
273 As isl might generate negative values in its expressions, signed loop ivs
274 are required in the backend. */
277 loop_ivs_can_be_represented (loop_p loop
)
279 unsigned type_long_long
= TYPE_PRECISION (long_long_integer_type_node
);
280 for (gphi_iterator psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
);
283 gphi
*phi
= psi
.phi ();
284 tree res
= PHI_RESULT (phi
);
285 tree type
= TREE_TYPE (res
);
287 if (TYPE_UNSIGNED (type
) && TYPE_PRECISION (type
) >= type_long_long
)
294 /* Returns a COND_EXPR statement when BB has a single predecessor, the
295 edge between BB and its predecessor is not a loop exit edge, and
296 the last statement of the single predecessor is a COND_EXPR. */
299 single_pred_cond_non_loop_exit (basic_block bb
)
301 if (single_pred_p (bb
))
303 edge e
= single_pred_edge (bb
);
304 basic_block pred
= e
->src
;
307 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
310 stmt
= last_stmt (pred
);
312 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
313 return as_a
<gcond
*> (stmt
);
322 /* Build the maximal scop containing LOOPs and add it to SCOPS. */
327 scop_detection () : scops (vNULL
) {}
334 /* A marker for invalid sese_l. */
335 static sese_l invalid_sese
;
337 /* Return the SCOPS in this SCOP_DETECTION. */
345 /* Return an sese_l around the LOOP. */
347 sese_l
get_sese (loop_p loop
);
349 /* Return the closest dominator with a single entry edge. In case of a
350 back-loop the back-edge is not counted. */
352 static edge
get_nearest_dom_with_single_entry (basic_block dom
);
354 /* Return the closest post-dominator with a single exit edge. In case of a
355 back-loop the back-edge is not counted. */
357 static edge
get_nearest_pdom_with_single_exit (basic_block dom
);
359 /* Merge scops at same loop depth and returns the new sese.
360 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
362 sese_l
merge_sese (sese_l first
, sese_l second
) const;
364 /* Build scop outer->inner if possible. */
366 void build_scop_depth (loop_p loop
);
368 /* Return true when BEGIN is the preheader edge of a loop with a single exit
371 static bool region_has_one_loop (sese_l s
);
373 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
375 void add_scop (sese_l s
);
377 /* Returns true if S1 subsumes/surrounds S2. */
378 static bool subsumes (sese_l s1
, sese_l s2
);
380 /* Remove a SCoP which is subsumed by S1. */
381 void remove_subscops (sese_l s1
);
383 /* Returns true if S1 intersects with S2. Since we already know that S1 does
384 not subsume S2 or vice-versa, we only check for entry bbs. */
386 static bool intersects (sese_l s1
, sese_l s2
);
388 /* Remove one of the scops when it intersects with any other. */
390 void remove_intersecting_scops (sese_l s1
);
392 /* Return true when a statement in SCOP cannot be represented by Graphite. */
394 bool harmful_loop_in_region (sese_l scop
) const;
396 /* Return true only when STMT is simple enough for being handled by Graphite.
397 This depends on SCOP, as the parameters are initialized relatively to
398 this basic block, the linear functions are initialized based on the
399 outermost loop containing STMT inside the SCOP. BB is the place where we
400 try to evaluate the STMT. */
402 bool stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
403 basic_block bb
) const;
405 /* Something like "n * m" is not allowed. */
407 static bool graphite_can_represent_init (tree e
);
409 /* Return true when SCEV can be represented in the polyhedral model.
411 An expression can be represented, if it can be expressed as an
412 affine expression. For loops (i, j) and parameters (m, n) all
413 affine expressions are of the form:
415 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
417 1 i + 20 j + (-2) m + 25
419 Something like "i * n" or "n * m" is not allowed. */
421 static bool graphite_can_represent_scev (tree scev
);
423 /* Return true when EXPR can be represented in the polyhedral model.
425 This means an expression can be represented, if it is linear with respect
426 to the loops and the strides are non parametric. LOOP is the place where
427 the expr will be evaluated. SCOP defines the region we analyse. */
429 static bool graphite_can_represent_expr (sese_l scop
, loop_p loop
,
432 /* Return true if the data references of STMT can be represented by Graphite.
433 We try to analyze the data references in a loop contained in the SCOP. */
435 static bool stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
);
437 /* Remove the close phi node at GSI and replace its rhs with the rhs
440 static void remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
);
442 /* Returns true when Graphite can represent LOOP in SCOP.
443 FIXME: For the moment, graphite cannot be used on loops that iterate using
444 induction variables that wrap. */
446 static bool can_represent_loop (loop_p loop
, sese_l scop
);
448 /* Returns the number of pbbs that are in loops contained in SCOP. */
450 static int nb_pbbs_in_loops (scop_p scop
);
456 sese_l
scop_detection::invalid_sese (NULL
, NULL
);
458 /* Return an sese_l around the LOOP. */
461 scop_detection::get_sese (loop_p loop
)
466 edge scop_begin
= loop_preheader_edge (loop
);
467 edge scop_end
= single_exit (loop
);
468 if (!scop_end
|| (scop_end
->flags
& EDGE_COMPLEX
))
470 /* Include the BB with the loop-closed SSA PHI nodes.
471 canonicalize_loop_closed_ssa makes sure that is in proper shape. */
472 if (! single_pred_p (scop_end
->dest
)
473 || ! single_succ_p (scop_end
->dest
)
474 || ! trivially_empty_bb_p (scop_end
->dest
))
476 scop_end
= single_succ_edge (scop_end
->dest
);
478 return sese_l (scop_begin
, scop_end
);
481 /* Return the closest dominator with a single entry edge. */
484 scop_detection::get_nearest_dom_with_single_entry (basic_block dom
)
489 /* If any of the dominators has two predecessors but one of them is a back
490 edge, then that basic block also qualifies as a dominator with single
492 if (dom
->preds
->length () == 2)
494 /* If e1->src dominates e2->src then e1->src will also dominate dom. */
495 edge e1
= (*dom
->preds
)[0];
496 edge e2
= (*dom
->preds
)[1];
497 loop_p l
= dom
->loop_father
;
498 loop_p l1
= e1
->src
->loop_father
;
499 loop_p l2
= e2
->src
->loop_father
;
500 if (l
!= l1
&& l
== l2
501 && dominated_by_p (CDI_DOMINATORS
, e2
->src
, e1
->src
))
503 if (l
!= l2
&& l
== l1
504 && dominated_by_p (CDI_DOMINATORS
, e1
->src
, e2
->src
))
508 while (dom
->preds
->length () != 1)
510 if (dom
->preds
->length () < 1)
512 dom
= get_immediate_dominator (CDI_DOMINATORS
, dom
);
516 return (*dom
->preds
)[0];
519 /* Return the closest post-dominator with a single exit edge. In case of a
520 back-loop the back-edge is not counted. */
523 scop_detection::get_nearest_pdom_with_single_exit (basic_block pdom
)
528 /* If any of the post-dominators has two successors but one of them is a back
529 edge, then that basic block also qualifies as a post-dominator with single
531 if (pdom
->succs
->length () == 2)
533 /* If e1->dest post-dominates e2->dest then e1->dest will also
534 post-dominate pdom. */
535 edge e1
= (*pdom
->succs
)[0];
536 edge e2
= (*pdom
->succs
)[1];
537 loop_p l
= pdom
->loop_father
;
538 loop_p l1
= e1
->dest
->loop_father
;
539 loop_p l2
= e2
->dest
->loop_father
;
540 if (l
!= l1
&& l
== l2
541 && dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, e1
->dest
))
543 if (l
!= l2
&& l
== l1
544 && dominated_by_p (CDI_POST_DOMINATORS
, e1
->dest
, e2
->dest
))
548 while (pdom
->succs
->length () != 1)
550 if (pdom
->succs
->length () < 1)
552 pdom
= get_immediate_dominator (CDI_POST_DOMINATORS
, pdom
);
557 return (*pdom
->succs
)[0];
560 /* Merge scops at same loop depth and returns the new sese.
561 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
564 scop_detection::merge_sese (sese_l first
, sese_l second
) const
566 /* In the trivial case first/second may be NULL. */
572 DEBUG_PRINT (dp
<< "[scop-detection] try merging sese s1: ";
573 print_sese (dump_file
, first
);
574 dp
<< "[scop-detection] try merging sese s2: ";
575 print_sese (dump_file
, second
));
577 /* Assumption: Both the sese's should be at the same loop depth or one scop
578 should subsume the other like in case of nested loops. */
580 /* Find the common dominators for entry,
581 and common post-dominators for the exit. */
582 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
,
583 get_entry_bb (first
),
584 get_entry_bb (second
));
586 edge entry
= get_nearest_dom_with_single_entry (dom
);
588 if (!entry
|| (entry
->flags
& EDGE_IRREDUCIBLE_LOOP
))
591 basic_block pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
,
593 get_exit_bb (second
));
594 pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
, dom
, pdom
);
596 edge exit
= get_nearest_pdom_with_single_exit (pdom
);
598 if (!exit
|| (exit
->flags
& EDGE_IRREDUCIBLE_LOOP
))
601 sese_l
combined (entry
, exit
);
603 DEBUG_PRINT (dp
<< "[scop-detection] checking combined sese: ";
604 print_sese (dump_file
, combined
));
606 /* FIXME: We could iterate to find the dom which dominates pdom, and pdom
607 which post-dominates dom, until it stabilizes. Also, ENTRY->SRC and
608 EXIT->DEST should be in the same loop nest. */
609 if (!dominated_by_p (CDI_DOMINATORS
, pdom
, dom
)
610 || loop_depth (entry
->src
->loop_father
)
611 != loop_depth (exit
->dest
->loop_father
))
614 /* For now we just bail out when there is a loop exit in the region
615 that is not also the exit of the region. We could enlarge the
616 region to cover the loop that region exits to. See PR79977. */
617 if (loop_outer (entry
->src
->loop_father
))
619 vec
<edge
> exits
= get_loop_exit_edges (entry
->src
->loop_father
);
620 for (unsigned i
= 0; i
< exits
.length (); ++i
)
623 && bb_in_region (exits
[i
]->src
, entry
->dest
, exit
->src
))
625 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
633 /* For now we just want to bail out when exit does not post-dominate entry.
634 TODO: We might just add a basic_block at the exit to make exit
635 post-dominate entry (the entire region). */
636 if (!dominated_by_p (CDI_POST_DOMINATORS
, get_entry_bb (combined
),
637 get_exit_bb (combined
))
638 || !dominated_by_p (CDI_DOMINATORS
, get_exit_bb (combined
),
639 get_entry_bb (combined
)))
641 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
645 DEBUG_PRINT (dp
<< "[merged-sese] s1: "; print_sese (dump_file
, combined
));
650 /* Build scop outer->inner if possible. */
653 scop_detection::build_scop_depth (loop_p loop
)
655 sese_l s
= invalid_sese
;
659 sese_l next
= get_sese (loop
);
661 || harmful_loop_in_region (next
))
665 build_scop_depth (loop
);
672 sese_l combined
= merge_sese (s
, next
);
674 || harmful_loop_in_region (combined
))
688 /* Returns true when Graphite can represent LOOP in SCOP.
689 FIXME: For the moment, graphite cannot be used on loops that iterate using
690 induction variables that wrap. */
693 scop_detection::can_represent_loop (loop_p loop
, sese_l scop
)
696 struct tree_niter_desc niter_desc
;
698 return single_exit (loop
)
699 && !(loop_preheader_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
)
700 && number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
701 && niter_desc
.control
.no_overflow
702 && (niter
= number_of_latch_executions (loop
))
703 && !chrec_contains_undetermined (niter
)
704 && !chrec_contains_undetermined (scalar_evolution_in_region (scop
,
706 && graphite_can_represent_expr (scop
, loop
, niter
);
709 /* Return true when BEGIN is the preheader edge of a loop with a single exit
713 scop_detection::region_has_one_loop (sese_l s
)
715 edge begin
= s
.entry
;
717 /* Check for a single perfectly nested loop. */
718 if (begin
->dest
->loop_father
->inner
)
721 /* Otherwise, check whether we have adjacent loops. */
722 return (single_pred_p (end
->src
)
723 && begin
->dest
->loop_father
== single_pred (end
->src
)->loop_father
);
726 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
729 scop_detection::add_scop (sese_l s
)
733 /* Do not add scops with only one loop. */
734 if (region_has_one_loop (s
))
736 DEBUG_PRINT (dp
<< "[scop-detection-fail] Discarding one loop SCoP: ";
737 print_sese (dump_file
, s
));
741 if (get_exit_bb (s
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
743 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
744 << "Discarding SCoP exiting to return: ";
745 print_sese (dump_file
, s
));
749 /* Remove all the scops which are subsumed by s. */
752 /* Remove intersecting scops. FIXME: It will be a good idea to keep
753 the non-intersecting part of the scop already in the list. */
754 remove_intersecting_scops (s
);
757 DEBUG_PRINT (dp
<< "[scop-detection] Adding SCoP: "; print_sese (dump_file
, s
));
760 /* Return true when a statement in SCOP cannot be represented by Graphite. */
763 scop_detection::harmful_loop_in_region (sese_l scop
) const
765 basic_block exit_bb
= get_exit_bb (scop
);
766 basic_block entry_bb
= get_entry_bb (scop
);
768 DEBUG_PRINT (dp
<< "[checking-harmful-bbs] ";
769 print_sese (dump_file
, scop
));
770 gcc_assert (dominated_by_p (CDI_DOMINATORS
, exit_bb
, entry_bb
));
772 auto_vec
<basic_block
> worklist
;
775 worklist
.safe_push (entry_bb
);
776 while (! worklist
.is_empty ())
778 basic_block bb
= worklist
.pop ();
779 DEBUG_PRINT (dp
<< "Visiting bb_" << bb
->index
<< "\n");
781 /* The basic block should not be part of an irreducible loop. */
782 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
785 /* Check for unstructured control flow: CFG not generated by structured
787 if (bb
->succs
->length () > 1)
791 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
792 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb
, e
->dest
)
793 && !dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
797 /* Collect all loops in the current region. */
798 loop_p loop
= bb
->loop_father
;
799 if (loop_in_sese_p (loop
, scop
))
800 bitmap_set_bit (loops
, loop
->num
);
802 /* Check for harmful statements in basic blocks part of the region. */
803 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
804 !gsi_end_p (gsi
); gsi_next (&gsi
))
805 if (!stmt_simple_for_scop_p (scop
, gsi_stmt (gsi
), bb
))
809 for (basic_block dom
= first_dom_son (CDI_DOMINATORS
, bb
);
811 dom
= next_dom_son (CDI_DOMINATORS
, dom
))
812 worklist
.safe_push (dom
);
815 /* Go through all loops and check that they are still valid in the combined
819 EXECUTE_IF_SET_IN_BITMAP (loops
, 0, j
, bi
)
821 loop_p loop
= (*current_loops
->larray
)[j
];
822 gcc_assert (loop
->num
== (int) j
);
824 /* Check if the loop nests are to be optimized for speed. */
826 && ! optimize_loop_for_speed_p (loop
))
828 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_"
829 << loop
->num
<< " is not on a hot path.\n");
833 if (! can_represent_loop (loop
, scop
))
835 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot represent loop_"
836 << loop
->num
<< "\n");
840 if (! loop_ivs_can_be_represented (loop
))
842 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
843 << "IV cannot be represented.\n");
847 /* Check if all loop nests have at least one data reference.
848 ??? This check is expensive and loops premature at this point.
849 If important to retain we can pre-compute this for all innermost
850 loops and reject those when we build a SESE region for a loop
851 during SESE discovery. */
853 && ! loop_nest_has_data_refs (loop
))
855 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
856 << "does not have any data reference.\n");
864 /* Returns true if S1 subsumes/surrounds S2. */
866 scop_detection::subsumes (sese_l s1
, sese_l s2
)
868 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
870 && dominated_by_p (CDI_POST_DOMINATORS
, s2
.exit
->dest
,
876 /* Remove a SCoP which is subsumed by S1. */
878 scop_detection::remove_subscops (sese_l s1
)
882 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
884 if (subsumes (s1
, *s2
))
886 DEBUG_PRINT (dp
<< "Removing sub-SCoP";
887 print_sese (dump_file
, *s2
));
888 scops
.unordered_remove (j
);
893 /* Returns true if S1 intersects with S2. Since we already know that S1 does
894 not subsume S2 or vice-versa, we only check for entry bbs. */
897 scop_detection::intersects (sese_l s1
, sese_l s2
)
899 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
901 && !dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
904 if ((s1
.exit
== s2
.entry
) || (s2
.exit
== s1
.entry
))
910 /* Remove one of the scops when it intersects with any other. */
913 scop_detection::remove_intersecting_scops (sese_l s1
)
917 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
919 if (intersects (s1
, *s2
))
921 DEBUG_PRINT (dp
<< "Removing intersecting SCoP";
922 print_sese (dump_file
, *s2
);
923 dp
<< "Intersects with:";
924 print_sese (dump_file
, s1
));
925 scops
.unordered_remove (j
);
930 /* Something like "n * m" is not allowed. */
933 scop_detection::graphite_can_represent_init (tree e
)
935 switch (TREE_CODE (e
))
937 case POLYNOMIAL_CHREC
:
938 return graphite_can_represent_init (CHREC_LEFT (e
))
939 && graphite_can_represent_init (CHREC_RIGHT (e
));
942 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
943 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
944 && tree_fits_shwi_p (TREE_OPERAND (e
, 1));
946 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
947 && tree_fits_shwi_p (TREE_OPERAND (e
, 0));
950 case POINTER_PLUS_EXPR
:
952 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
953 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
958 case NON_LVALUE_EXPR
:
959 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
968 /* Return true when SCEV can be represented in the polyhedral model.
970 An expression can be represented, if it can be expressed as an
971 affine expression. For loops (i, j) and parameters (m, n) all
972 affine expressions are of the form:
974 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
976 1 i + 20 j + (-2) m + 25
978 Something like "i * n" or "n * m" is not allowed. */
981 scop_detection::graphite_can_represent_scev (tree scev
)
983 if (chrec_contains_undetermined (scev
))
986 /* We disable the handling of pointer types, because it’s currently not
987 supported by Graphite with the isl AST generator. SSA_NAME nodes are
988 the only nodes, which are disabled in case they are pointers to object
989 types, but this can be changed. */
991 if (POINTER_TYPE_P (TREE_TYPE (scev
)) && TREE_CODE (scev
) == SSA_NAME
)
994 switch (TREE_CODE (scev
))
999 case NON_LVALUE_EXPR
:
1000 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0));
1003 case POINTER_PLUS_EXPR
:
1005 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1006 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1009 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
1010 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
1011 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
1012 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
1013 && graphite_can_represent_init (scev
)
1014 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1015 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1017 case POLYNOMIAL_CHREC
:
1018 /* Check for constant strides. With a non constant stride of
1019 'n' we would have a value of 'iv * n'. Also check that the
1020 initial value can represented: for example 'n * m' cannot be
1022 if (!evolution_function_right_is_integer_cst (scev
)
1023 || !graphite_can_represent_init (scev
))
1025 return graphite_can_represent_scev (CHREC_LEFT (scev
));
1031 /* Only affine functions can be represented. */
1032 if (tree_contains_chrecs (scev
, NULL
) || !scev_is_linear_expression (scev
))
1038 /* Return true when EXPR can be represented in the polyhedral model.
1040 This means an expression can be represented, if it is linear with respect to
1041 the loops and the strides are non parametric. LOOP is the place where the
1042 expr will be evaluated. SCOP defines the region we analyse. */
1045 scop_detection::graphite_can_represent_expr (sese_l scop
, loop_p loop
,
1048 tree scev
= scalar_evolution_in_region (scop
, loop
, expr
);
1049 return graphite_can_represent_scev (scev
);
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. */
1056 scop_detection::stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
)
1059 loop_p loop
= loop_containing_stmt (stmt
);
1060 if (!loop_in_sese_p (loop
, scop
))
1063 nest
= outermost_loop_in_sese (scop
, gimple_bb (stmt
));
1065 auto_vec
<data_reference_p
> drs
;
1066 if (! graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
))
1070 data_reference_p dr
;
1071 FOR_EACH_VEC_ELT (drs
, j
, dr
)
1073 for (unsigned i
= 0; i
< DR_NUM_DIMENSIONS (dr
); ++i
)
1074 if (! graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
)))
1081 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1082 Calls have side-effects, except those to const or pure
1086 stmt_has_side_effects (gimple
*stmt
)
1088 if (gimple_has_volatile_ops (stmt
)
1089 || (gimple_code (stmt
) == GIMPLE_CALL
1090 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
1091 || (gimple_code (stmt
) == GIMPLE_ASM
))
1093 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1094 << "Statement has side-effects:\n";
1095 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1101 /* Return true only when STMT is simple enough for being handled by Graphite.
1102 This depends on SCOP, as the parameters are initialized relatively to
1103 this basic block, the linear functions are initialized based on the outermost
1104 loop containing STMT inside the SCOP. BB is the place where we try to
1105 evaluate the STMT. */
1108 scop_detection::stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
1109 basic_block bb
) const
1113 if (is_gimple_debug (stmt
))
1116 if (stmt_has_side_effects (stmt
))
1119 if (!stmt_has_simple_data_refs_p (scop
, stmt
))
1121 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1122 << "Graphite cannot handle data-refs in stmt:\n";
1123 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
););
1127 switch (gimple_code (stmt
))
1134 /* We can handle all binary comparisons. Inequalities are
1135 also supported as they can be represented with union of
1137 enum tree_code code
= gimple_cond_code (stmt
);
1138 if (!(code
== LT_EXPR
1143 || code
== NE_EXPR
))
1145 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1146 << "Graphite cannot handle cond stmt:\n";
1147 print_gimple_stmt (dump_file
, stmt
, 0,
1148 TDF_VOPS
| TDF_MEMSYMS
));
1152 loop_p loop
= bb
->loop_father
;
1153 for (unsigned i
= 0; i
< 2; ++i
)
1155 tree op
= gimple_op (stmt
, i
);
1156 if (!graphite_can_represent_expr (scop
, loop
, op
)
1157 /* We can only constrain on integer type. */
1158 || (TREE_CODE (TREE_TYPE (op
)) != INTEGER_TYPE
))
1160 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1161 << "Graphite cannot represent stmt:\n";
1162 print_gimple_stmt (dump_file
, stmt
, 0,
1163 TDF_VOPS
| TDF_MEMSYMS
));
1176 /* These nodes cut a new scope. */
1178 dp
<< "[scop-detection-fail] "
1179 << "Gimple stmt not handled in Graphite:\n";
1180 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1185 /* Returns the number of pbbs that are in loops contained in SCOP. */
1188 scop_detection::nb_pbbs_in_loops (scop_p scop
)
1194 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1195 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), scop
->scop_info
->region
))
1201 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
1202 Otherwise returns -1. */
1205 parameter_index_in_region_1 (tree name
, sese_info_p region
)
1210 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1212 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
1219 /* When the parameter NAME is in REGION, returns its index in
1220 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
1221 and returns the index of NAME. */
1224 parameter_index_in_region (tree name
, sese_info_p region
)
1228 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1230 /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
1231 if (TREE_CODE (TREE_TYPE (name
)) != INTEGER_TYPE
)
1234 if (!invariant_in_sese_p_rec (name
, region
->region
, NULL
))
1237 i
= parameter_index_in_region_1 (name
, region
);
1241 i
= region
->params
.length ();
1242 region
->params
.safe_push (name
);
1246 /* In the context of sese S, scan the expression E and translate it to
1247 a linear expression C. When parsing a symbolic multiplication, K
1248 represents the constant multiplier of an expression containing
1252 scan_tree_for_params (sese_info_p s
, tree e
)
1254 if (e
== chrec_dont_know
)
1257 switch (TREE_CODE (e
))
1259 case POLYNOMIAL_CHREC
:
1260 scan_tree_for_params (s
, CHREC_LEFT (e
));
1264 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1265 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1267 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1271 case POINTER_PLUS_EXPR
:
1273 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1274 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1280 case NON_LVALUE_EXPR
:
1281 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1285 parameter_index_in_region (e
, s
);
1301 /* Find parameters with respect to REGION in BB. We are looking in memory
1302 access functions, conditions and loop bounds. */
1305 find_params_in_bb (sese_info_p region
, gimple_poly_bb_p gbb
)
1307 /* Find parameters in the access functions of data references. */
1309 data_reference_p dr
;
1310 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
1311 for (unsigned j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
1312 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
1314 /* Find parameters in conditional statements. */
1316 loop_p loop
= GBB_BB (gbb
)->loop_father
;
1317 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1319 tree lhs
= scalar_evolution_in_region (region
->region
, loop
,
1320 gimple_cond_lhs (stmt
));
1321 tree rhs
= scalar_evolution_in_region (region
->region
, loop
,
1322 gimple_cond_rhs (stmt
));
1324 scan_tree_for_params (region
, lhs
);
1325 scan_tree_for_params (region
, rhs
);
1329 /* Record the parameters used in the SCOP BBs. A variable is a parameter
1330 in a scop if it does not vary during the execution of that scop. */
1333 find_scop_parameters (scop_p scop
)
1336 sese_info_p region
= scop
->scop_info
;
1338 /* Parameters used in loop bounds are processed during gather_bbs. */
1340 /* Find the parameters used in data accesses. */
1342 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1343 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1345 int nbp
= sese_nb_params (region
);
1346 scop_set_nb_params (scop
, nbp
);
1349 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1352 build_cross_bb_scalars_def (scop_p scop
, tree def
, basic_block def_bb
,
1355 if (!def
|| !is_gimple_reg (def
))
1358 bool scev_analyzable
= scev_analyzable_p (def
, scop
->scop_info
->region
);
1361 imm_use_iterator imm_iter
;
1362 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1363 /* Do not gather scalar variables that can be analyzed by SCEV as they can
1364 be generated out of the induction variables. */
1365 if ((! scev_analyzable
1366 /* But gather SESE liveouts as we otherwise fail to rewrite their
1368 || ! bb_in_sese_p (gimple_bb (use_stmt
), scop
->scop_info
->region
))
1369 && ((def_bb
!= gimple_bb (use_stmt
) && !is_gimple_debug (use_stmt
))
1370 /* PHIs have their effect at "BBs" on the edges. See PR79622. */
1371 || gimple_code (SSA_NAME_DEF_STMT (def
)) == GIMPLE_PHI
))
1373 writes
->safe_push (def
);
1374 DEBUG_PRINT (dp
<< "Adding scalar write: ";
1375 print_generic_expr (dump_file
, def
);
1376 dp
<< "\nFrom stmt: ";
1377 print_gimple_stmt (dump_file
,
1378 SSA_NAME_DEF_STMT (def
), 0));
1379 /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
1380 before all the uses have been visited. */
1381 BREAK_FROM_IMM_USE_STMT (imm_iter
);
1385 /* Record USE if it is defined in other bbs different than USE_STMT
1389 build_cross_bb_scalars_use (scop_p scop
, tree use
, gimple
*use_stmt
,
1390 vec
<scalar_use
> *reads
)
1393 if (!is_gimple_reg (use
))
1396 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1397 generated out of the induction variables. */
1398 if (scev_analyzable_p (use
, scop
->scop_info
->region
))
1401 gimple
*def_stmt
= SSA_NAME_DEF_STMT (use
);
1402 if (gimple_bb (def_stmt
) != gimple_bb (use_stmt
)
1403 /* PHIs have their effect at "BBs" on the edges. See PR79622. */
1404 || gimple_code (def_stmt
) == GIMPLE_PHI
)
1406 DEBUG_PRINT (dp
<< "Adding scalar read: ";
1407 print_generic_expr (dump_file
, use
);
1408 dp
<< "\nFrom stmt: ";
1409 print_gimple_stmt (dump_file
, use_stmt
, 0));
1410 reads
->safe_push (std::make_pair (use_stmt
, use
));
1414 /* Record all scalar variables that are defined and used in different BBs of the
1418 graphite_find_cross_bb_scalar_vars (scop_p scop
, gimple
*stmt
,
1419 vec
<scalar_use
> *reads
, vec
<tree
> *writes
)
1423 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
1424 def
= gimple_assign_lhs (stmt
);
1425 else if (gimple_code (stmt
) == GIMPLE_CALL
)
1426 def
= gimple_call_lhs (stmt
);
1427 else if (gimple_code (stmt
) == GIMPLE_PHI
)
1428 def
= gimple_phi_result (stmt
);
1433 build_cross_bb_scalars_def (scop
, def
, gimple_bb (stmt
), writes
);
1436 use_operand_p use_p
;
1437 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1439 tree use
= USE_FROM_PTR (use_p
);
1440 build_cross_bb_scalars_use (scop
, use
, stmt
, reads
);
1444 /* Generates a polyhedral black box only if the bb contains interesting
1447 static gimple_poly_bb_p
1448 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
1450 vec
<data_reference_p
> drs
= vNULL
;
1451 vec
<tree
> writes
= vNULL
;
1452 vec
<scalar_use
> reads
= vNULL
;
1454 sese_l region
= scop
->scop_info
->region
;
1456 loop_p loop
= bb
->loop_father
;
1457 if (!loop_in_sese_p (loop
, region
))
1460 nest
= outermost_loop_in_sese (region
, bb
);
1462 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1465 gimple
*stmt
= gsi_stmt (gsi
);
1466 if (is_gimple_debug (stmt
))
1469 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1470 graphite_find_cross_bb_scalar_vars (scop
, stmt
, &reads
, &writes
);
1473 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1475 if (!virtual_operand_p (gimple_phi_result (psi
.phi ())))
1476 graphite_find_cross_bb_scalar_vars (scop
, psi
.phi (), &reads
, &writes
);
1478 if (drs
.is_empty () && writes
.is_empty () && reads
.is_empty ())
1481 return new_gimple_poly_bb (bb
, drs
, reads
, writes
);
1484 /* Compute alias-sets for all data references in DRS. */
1487 build_alias_set (scop_p scop
)
1489 int num_vertices
= scop
->drs
.length ();
1490 struct graph
*g
= new_graph (num_vertices
);
1495 FOR_EACH_VEC_ELT (scop
->drs
, i
, dr1
)
1496 for (j
= i
+1; scop
->drs
.iterate (j
, &dr2
); j
++)
1497 if (dr_may_alias_p (dr1
->dr
, dr2
->dr
, true))
1499 /* Dependences in the same alias set need to be handled
1500 by just looking at DR_ACCESS_FNs. */
1501 if (DR_NUM_DIMENSIONS (dr1
->dr
) == 0
1502 || DR_NUM_DIMENSIONS (dr1
->dr
) != DR_NUM_DIMENSIONS (dr2
->dr
)
1503 || ! operand_equal_p (DR_BASE_OBJECT (dr1
->dr
),
1504 DR_BASE_OBJECT (dr2
->dr
),
1506 || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1
->dr
)),
1507 TREE_TYPE (DR_BASE_OBJECT (dr2
->dr
))))
1516 all_vertices
= XNEWVEC (int, num_vertices
);
1517 for (i
= 0; i
< num_vertices
; i
++)
1518 all_vertices
[i
] = i
;
1521 = graphds_dfs (g
, all_vertices
, num_vertices
, NULL
, true, NULL
) + 1;
1522 free (all_vertices
);
1524 for (i
= 0; i
< g
->n_vertices
; i
++)
1525 scop
->drs
[i
].alias_set
= g
->vertices
[i
].component
+ 1;
1531 /* Gather BBs and conditions for a SCOP. */
1532 class gather_bbs
: public dom_walker
1535 gather_bbs (cdi_direction
, scop_p
, int *);
1537 virtual edge
before_dom_children (basic_block
);
1538 virtual void after_dom_children (basic_block
);
1541 auto_vec
<gimple
*, 3> conditions
, cases
;
1545 gather_bbs::gather_bbs (cdi_direction direction
, scop_p scop
, int *bb_to_rpo
)
1546 : dom_walker (direction
, false, bb_to_rpo
), scop (scop
)
1550 /* Call-back for dom_walk executed before visiting the dominated
1554 gather_bbs::before_dom_children (basic_block bb
)
1556 sese_info_p region
= scop
->scop_info
;
1557 if (!bb_in_sese_p (bb
, region
->region
))
1558 return dom_walker::STOP
;
1560 /* For loops fully contained in the region record parameters in the
1562 loop_p loop
= bb
->loop_father
;
1563 if (loop
->header
== bb
1564 && loop_in_sese_p (loop
, region
->region
))
1566 tree nb_iters
= number_of_latch_executions (loop
);
1567 if (chrec_contains_symbols (nb_iters
))
1569 nb_iters
= scalar_evolution_in_region (region
->region
,
1571 scan_tree_for_params (region
, nb_iters
);
1575 gcond
*stmt
= single_pred_cond_non_loop_exit (bb
);
1579 edge e
= single_pred_edge (bb
);
1581 conditions
.safe_push (stmt
);
1583 if (e
->flags
& EDGE_TRUE_VALUE
)
1584 cases
.safe_push (stmt
);
1586 cases
.safe_push (NULL
);
1589 scop
->scop_info
->bbs
.safe_push (bb
);
1591 gimple_poly_bb_p gbb
= try_generate_gimple_bb (scop
, bb
);
1595 GBB_CONDITIONS (gbb
) = conditions
.copy ();
1596 GBB_CONDITION_CASES (gbb
) = cases
.copy ();
1598 poly_bb_p pbb
= new_poly_bb (scop
, gbb
);
1599 scop
->pbbs
.safe_push (pbb
);
1602 data_reference_p dr
;
1603 FOR_EACH_VEC_ELT (gbb
->data_refs
, i
, dr
)
1605 DEBUG_PRINT (dp
<< "Adding memory ";
1610 print_generic_expr (dump_file
, dr
->ref
);
1611 dp
<< "\nFrom stmt: ";
1612 print_gimple_stmt (dump_file
, dr
->stmt
, 0));
1614 scop
->drs
.safe_push (dr_info (dr
, pbb
));
1620 /* Call-back for dom_walk executed after visiting the dominated
1624 gather_bbs::after_dom_children (basic_block bb
)
1626 if (!bb_in_sese_p (bb
, scop
->scop_info
->region
))
1629 if (single_pred_cond_non_loop_exit (bb
))
1637 /* Compute sth like an execution order, dominator order with first executing
1638 edges that stay inside the current loop, delaying processing exit edges. */
1640 static vec
<unsigned> order
;
1643 get_order (scop_p scop
, basic_block bb
, vec
<unsigned> *order
, unsigned *dfs_num
)
1645 if (! bb_in_sese_p (bb
, scop
->scop_info
->region
))
1648 (*order
)[bb
->index
] = (*dfs_num
)++;
1649 for (basic_block son
= first_dom_son (CDI_DOMINATORS
, bb
);
1651 son
= next_dom_son (CDI_DOMINATORS
, son
))
1652 if (flow_bb_inside_loop_p (bb
->loop_father
, son
))
1653 get_order (scop
, son
, order
, dfs_num
);
1654 for (basic_block son
= first_dom_son (CDI_DOMINATORS
, bb
);
1656 son
= next_dom_son (CDI_DOMINATORS
, son
))
1657 if (! flow_bb_inside_loop_p (bb
->loop_father
, son
))
1658 get_order (scop
, son
, order
, dfs_num
);
1661 /* Helper for qsort, sorting after order above. */
1664 cmp_pbbs (const void *pa
, const void *pb
)
1666 poly_bb_p bb1
= *((const poly_bb_p
*)pa
);
1667 poly_bb_p bb2
= *((const poly_bb_p
*)pb
);
1668 if (order
[bb1
->black_box
->bb
->index
] < order
[bb2
->black_box
->bb
->index
])
1670 else if (order
[bb1
->black_box
->bb
->index
] > order
[bb2
->black_box
->bb
->index
])
1676 /* Find Static Control Parts (SCoP) in the current function and pushes
1680 build_scops (vec
<scop_p
> *scops
)
1683 dp
.set_dump_file (dump_file
);
1686 sb
.build_scop_depth (current_loops
->tree_root
);
1688 /* Now create scops from the lightweight SESEs. */
1689 vec
<sese_l
> scops_l
= sb
.get_scops ();
1691 /* Domwalk needs a bb to RPO mapping. Compute it once here. */
1692 int *postorder
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
1693 int postorder_num
= pre_and_rev_post_order_compute (NULL
, postorder
, true);
1694 int *bb_to_rpo
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1695 for (int i
= 0; i
< postorder_num
; ++i
)
1696 bb_to_rpo
[postorder
[i
]] = i
;
1701 FOR_EACH_VEC_ELT (scops_l
, i
, s
)
1703 scop_p scop
= new_scop (s
->entry
, s
->exit
);
1705 /* Record all basic blocks and their conditions in REGION. */
1706 gather_bbs (CDI_DOMINATORS
, scop
, bb_to_rpo
).walk (s
->entry
->dest
);
1708 /* domwalk does not fulfil our code-generations constraints on the
1709 order of pbb which is to produce sth like execution order, delaying
1710 exection of loop exit edges. So compute such order and sort after
1712 order
.create (last_basic_block_for_fn (cfun
));
1713 order
.quick_grow (last_basic_block_for_fn (cfun
));
1714 unsigned dfs_num
= 0;
1715 get_order (scop
, s
->entry
->dest
, &order
, &dfs_num
);
1716 scop
->pbbs
.qsort (cmp_pbbs
);
1719 if (! build_alias_set (scop
))
1721 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot handle dependences\n");
1726 /* Do not optimize a scop containing only PBBs that do not belong
1728 if (sb
.nb_pbbs_in_loops (scop
) == 0)
1730 DEBUG_PRINT (dp
<< "[scop-detection-fail] no data references.\n");
1735 unsigned max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
1737 && scop
->drs
.length () >= max_arrays
)
1739 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many data references: "
1740 << scop
->drs
.length ()
1741 << " is larger than --param graphite-max-arrays-per-scop="
1742 << max_arrays
<< ".\n");
1747 find_scop_parameters (scop
);
1748 graphite_dim_t max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
1750 && scop_nb_params (scop
) > max_dim
)
1752 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many parameters: "
1753 << scop_nb_params (scop
)
1754 << " larger than --param graphite-max-nb-scop-params="
1755 << max_dim
<< ".\n");
1760 scops
->safe_push (scop
);
1764 DEBUG_PRINT (dp
<< "number of SCoPs: " << (scops
? scops
->length () : 0););
1767 #endif /* HAVE_isl */