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"
60 set_dump_file (FILE *f
)
66 friend debug_printer
&
67 operator<< (debug_printer
&output
, int i
)
69 fprintf (output
.dump_file
, "%d", i
);
72 friend debug_printer
&
73 operator<< (debug_printer
&output
, const char *s
)
75 fprintf (output
.dump_file
, "%s", s
);
80 #define DEBUG_PRINT(args) do \
82 if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \
85 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
86 different colors. If there are not enough colors, paint the
87 remaining SCoPs in gray.
90 - "*" after the node number denotes the entry of a SCoP,
91 - "#" after the node number denotes the exit of a SCoP,
92 - "()" around the node number denotes the entry or the
93 exit nodes of the SCOP. These are not part of SCoP. */
96 dot_all_sese (FILE *file
, vec
<sese_l
>& scops
)
98 /* Disable debugging while printing graph. */
99 dump_flags_t tmp_dump_flags
= dump_flags
;
100 dump_flags
= TDF_NONE
;
102 fprintf (file
, "digraph all {\n");
105 FOR_ALL_BB_FN (bb
, cfun
)
107 int part_of_scop
= false;
109 /* Use HTML for every bb label. So we are able to print bbs
110 which are part of two different SCoPs, with two different
111 background colors. */
112 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
114 fprintf (file
, "CELLSPACING=\"0\">\n");
116 /* Select color for SCoP. */
119 FOR_EACH_VEC_ELT (scops
, i
, region
)
121 bool sese_in_region
= bb_in_sese_p (bb
, *region
);
122 if (sese_in_region
|| (region
->exit
->dest
== bb
)
123 || (region
->entry
->dest
== bb
))
183 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
187 fprintf (file
, " (");
189 if (bb
== region
->entry
->dest
&& bb
== region
->exit
->dest
)
190 fprintf (file
, " %d*# ", bb
->index
);
191 else if (bb
== region
->entry
->dest
)
192 fprintf (file
, " %d* ", bb
->index
);
193 else if (bb
== region
->exit
->dest
)
194 fprintf (file
, " %d# ", bb
->index
);
196 fprintf (file
, " %d ", bb
->index
);
198 fprintf (file
, "{lp_%d}", bb
->loop_father
->num
);
203 fprintf (file
, "</TD></TR>\n");
210 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
211 fprintf (file
, " %d {lp_%d} </TD></TR>\n", bb
->index
,
212 bb
->loop_father
->num
);
214 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
217 FOR_ALL_BB_FN (bb
, cfun
)
221 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
222 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
225 fputs ("}\n\n", file
);
227 /* Enable debugging again. */
228 dump_flags
= tmp_dump_flags
;
231 /* Display SCoP on stderr. */
234 dot_sese (sese_l
& scop
)
240 scops
.safe_push (scop
);
242 dot_all_sese (stderr
, scops
);
252 dot_all_sese (stderr
, scops
);
256 /* Return true if BB is empty, contains only DEBUG_INSNs. */
259 trivially_empty_bb_p (basic_block bb
)
261 gimple_stmt_iterator gsi
;
263 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
264 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_DEBUG
265 && gimple_code (gsi_stmt (gsi
)) != GIMPLE_LABEL
)
271 /* Can all ivs be represented by a signed integer?
272 As isl might generate negative values in its expressions, signed loop ivs
273 are required in the backend. */
276 loop_ivs_can_be_represented (loop_p loop
)
278 unsigned type_long_long
= TYPE_PRECISION (long_long_integer_type_node
);
279 for (gphi_iterator psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
);
282 gphi
*phi
= psi
.phi ();
283 tree res
= PHI_RESULT (phi
);
284 tree type
= TREE_TYPE (res
);
286 if (TYPE_UNSIGNED (type
) && TYPE_PRECISION (type
) >= type_long_long
)
293 /* Returns a COND_EXPR statement when BB has a single predecessor, the
294 edge between BB and its predecessor is not a loop exit edge, and
295 the last statement of the single predecessor is a COND_EXPR. */
298 single_pred_cond_non_loop_exit (basic_block bb
)
300 if (single_pred_p (bb
))
302 edge e
= single_pred_edge (bb
);
303 basic_block pred
= e
->src
;
306 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
309 stmt
= last_stmt (pred
);
311 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
312 return as_a
<gcond
*> (stmt
);
321 /* Build the maximal scop containing LOOPs and add it to SCOPS. */
326 scop_detection () : scops (vNULL
) {}
333 /* A marker for invalid sese_l. */
334 static sese_l invalid_sese
;
336 /* Return the SCOPS in this SCOP_DETECTION. */
344 /* Return an sese_l around the LOOP. */
346 sese_l
get_sese (loop_p loop
);
348 /* Return the closest dominator with a single entry edge. In case of a
349 back-loop the back-edge is not counted. */
351 static edge
get_nearest_dom_with_single_entry (basic_block dom
);
353 /* Return the closest post-dominator with a single exit edge. In case of a
354 back-loop the back-edge is not counted. */
356 static edge
get_nearest_pdom_with_single_exit (basic_block dom
);
358 /* Merge scops at same loop depth and returns the new sese.
359 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
361 sese_l
merge_sese (sese_l first
, sese_l second
) const;
363 /* Build scop outer->inner if possible. */
365 void build_scop_depth (loop_p loop
);
367 /* Return true when BEGIN is the preheader edge of a loop with a single exit
370 static bool region_has_one_loop (sese_l s
);
372 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
374 void add_scop (sese_l s
);
376 /* Returns true if S1 subsumes/surrounds S2. */
377 static bool subsumes (sese_l s1
, sese_l s2
);
379 /* Remove a SCoP which is subsumed by S1. */
380 void remove_subscops (sese_l s1
);
382 /* Returns true if S1 intersects with S2. Since we already know that S1 does
383 not subsume S2 or vice-versa, we only check for entry bbs. */
385 static bool intersects (sese_l s1
, sese_l s2
);
387 /* Remove one of the scops when it intersects with any other. */
389 void remove_intersecting_scops (sese_l s1
);
391 /* Return true when a statement in SCOP cannot be represented by Graphite.
392 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
393 Limit the number of bbs between adjacent loops to
394 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
396 bool harmful_loop_in_region (sese_l scop
) const;
398 /* Return true only when STMT is simple enough for being handled by Graphite.
399 This depends on SCOP, as the parameters are initialized relatively to
400 this basic block, the linear functions are initialized based on the
401 outermost loop containing STMT inside the SCOP. BB is the place where we
402 try to evaluate the STMT. */
404 bool stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
405 basic_block bb
) const;
407 /* Something like "n * m" is not allowed. */
409 static bool graphite_can_represent_init (tree e
);
411 /* Return true when SCEV can be represented in the polyhedral model.
413 An expression can be represented, if it can be expressed as an
414 affine expression. For loops (i, j) and parameters (m, n) all
415 affine expressions are of the form:
417 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
419 1 i + 20 j + (-2) m + 25
421 Something like "i * n" or "n * m" is not allowed. */
423 static bool graphite_can_represent_scev (tree scev
);
425 /* Return true when EXPR can be represented in the polyhedral model.
427 This means an expression can be represented, if it is linear with respect
428 to the loops and the strides are non parametric. LOOP is the place where
429 the expr will be evaluated. SCOP defines the region we analyse. */
431 static bool graphite_can_represent_expr (sese_l scop
, loop_p loop
,
434 /* Return true if the data references of STMT can be represented by Graphite.
435 We try to analyze the data references in a loop contained in the SCOP. */
437 static bool stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
);
439 /* Remove the close phi node at GSI and replace its rhs with the rhs
442 static void remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
);
444 /* Returns true when Graphite can represent LOOP in SCOP.
445 FIXME: For the moment, graphite cannot be used on loops that iterate using
446 induction variables that wrap. */
448 static bool can_represent_loop (loop_p loop
, sese_l scop
);
450 /* Returns the number of pbbs that are in loops contained in SCOP. */
452 static int nb_pbbs_in_loops (scop_p scop
);
458 sese_l
scop_detection::invalid_sese (NULL
, NULL
);
460 /* Return an sese_l around the LOOP. */
463 scop_detection::get_sese (loop_p loop
)
468 edge scop_begin
= loop_preheader_edge (loop
);
469 edge scop_end
= single_exit (loop
);
470 if (!scop_end
|| (scop_end
->flags
& EDGE_COMPLEX
))
472 /* Include the BB with the loop-closed SSA PHI nodes.
473 canonicalize_loop_closed_ssa makes sure that is in proper shape. */
474 if (! single_pred_p (scop_end
->dest
)
475 || ! single_succ_p (scop_end
->dest
)
476 || ! trivially_empty_bb_p (scop_end
->dest
))
478 scop_end
= single_succ_edge (scop_end
->dest
);
480 return sese_l (scop_begin
, scop_end
);
483 /* Return the closest dominator with a single entry edge. */
486 scop_detection::get_nearest_dom_with_single_entry (basic_block dom
)
491 /* If any of the dominators has two predecessors but one of them is a back
492 edge, then that basic block also qualifies as a dominator with single
494 if (dom
->preds
->length () == 2)
496 /* If e1->src dominates e2->src then e1->src will also dominate dom. */
497 edge e1
= (*dom
->preds
)[0];
498 edge e2
= (*dom
->preds
)[1];
499 loop_p l
= dom
->loop_father
;
500 loop_p l1
= e1
->src
->loop_father
;
501 loop_p l2
= e2
->src
->loop_father
;
502 if (l
!= l1
&& l
== l2
503 && dominated_by_p (CDI_DOMINATORS
, e2
->src
, e1
->src
))
505 if (l
!= l2
&& l
== l1
506 && dominated_by_p (CDI_DOMINATORS
, e1
->src
, e2
->src
))
510 while (dom
->preds
->length () != 1)
512 if (dom
->preds
->length () < 1)
514 dom
= get_immediate_dominator (CDI_DOMINATORS
, dom
);
518 return (*dom
->preds
)[0];
521 /* Return the closest post-dominator with a single exit edge. In case of a
522 back-loop the back-edge is not counted. */
525 scop_detection::get_nearest_pdom_with_single_exit (basic_block pdom
)
530 /* If any of the post-dominators has two successors but one of them is a back
531 edge, then that basic block also qualifies as a post-dominator with single
533 if (pdom
->succs
->length () == 2)
535 /* If e1->dest post-dominates e2->dest then e1->dest will also
536 post-dominate pdom. */
537 edge e1
= (*pdom
->succs
)[0];
538 edge e2
= (*pdom
->succs
)[1];
539 loop_p l
= pdom
->loop_father
;
540 loop_p l1
= e1
->dest
->loop_father
;
541 loop_p l2
= e2
->dest
->loop_father
;
542 if (l
!= l1
&& l
== l2
543 && dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, e1
->dest
))
545 if (l
!= l2
&& l
== l1
546 && dominated_by_p (CDI_POST_DOMINATORS
, e1
->dest
, e2
->dest
))
550 while (pdom
->succs
->length () != 1)
552 if (pdom
->succs
->length () < 1)
554 pdom
= get_immediate_dominator (CDI_POST_DOMINATORS
, pdom
);
559 return (*pdom
->succs
)[0];
562 /* Merge scops at same loop depth and returns the new sese.
563 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
566 scop_detection::merge_sese (sese_l first
, sese_l second
) const
568 /* In the trivial case first/second may be NULL. */
574 DEBUG_PRINT (dp
<< "[scop-detection] try merging sese s1: ";
575 print_sese (dump_file
, first
);
576 dp
<< "[scop-detection] try merging sese s2: ";
577 print_sese (dump_file
, second
));
579 /* Assumption: Both the sese's should be at the same loop depth or one scop
580 should subsume the other like in case of nested loops. */
582 /* Find the common dominators for entry,
583 and common post-dominators for the exit. */
584 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
,
585 get_entry_bb (first
),
586 get_entry_bb (second
));
588 edge entry
= get_nearest_dom_with_single_entry (dom
);
590 if (!entry
|| (entry
->flags
& EDGE_IRREDUCIBLE_LOOP
))
593 basic_block pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
,
595 get_exit_bb (second
));
596 pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
, dom
, pdom
);
598 edge exit
= get_nearest_pdom_with_single_exit (pdom
);
600 if (!exit
|| (exit
->flags
& EDGE_IRREDUCIBLE_LOOP
))
603 sese_l
combined (entry
, exit
);
605 DEBUG_PRINT (dp
<< "[scop-detection] checking combined sese: ";
606 print_sese (dump_file
, combined
));
608 /* FIXME: We could iterate to find the dom which dominates pdom, and pdom
609 which post-dominates dom, until it stabilizes. Also, ENTRY->SRC and
610 EXIT->DEST should be in the same loop nest. */
611 if (!dominated_by_p (CDI_DOMINATORS
, pdom
, dom
)
612 || loop_depth (entry
->src
->loop_father
)
613 != loop_depth (exit
->dest
->loop_father
))
616 /* For now we just bail out when there is a loop exit in the region
617 that is not also the exit of the region. We could enlarge the
618 region to cover the loop that region exits to. See PR79977. */
619 if (loop_outer (entry
->src
->loop_father
))
621 vec
<edge
> exits
= get_loop_exit_edges (entry
->src
->loop_father
);
622 for (unsigned i
= 0; i
< exits
.length (); ++i
)
625 && bb_in_region (exits
[i
]->src
, entry
->dest
, exit
->src
))
627 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
635 /* For now we just want to bail out when exit does not post-dominate entry.
636 TODO: We might just add a basic_block at the exit to make exit
637 post-dominate entry (the entire region). */
638 if (!dominated_by_p (CDI_POST_DOMINATORS
, get_entry_bb (combined
),
639 get_exit_bb (combined
))
640 || !dominated_by_p (CDI_DOMINATORS
, get_exit_bb (combined
),
641 get_entry_bb (combined
)))
643 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
647 DEBUG_PRINT (dp
<< "[merged-sese] s1: "; print_sese (dump_file
, combined
));
652 /* Build scop outer->inner if possible. */
655 scop_detection::build_scop_depth (loop_p loop
)
657 sese_l s
= invalid_sese
;
661 sese_l next
= get_sese (loop
);
663 || harmful_loop_in_region (next
))
667 build_scop_depth (loop
);
674 sese_l combined
= merge_sese (s
, next
);
676 || harmful_loop_in_region (combined
))
690 /* Returns true when Graphite can represent LOOP in SCOP.
691 FIXME: For the moment, graphite cannot be used on loops that iterate using
692 induction variables that wrap. */
695 scop_detection::can_represent_loop (loop_p loop
, sese_l scop
)
698 struct tree_niter_desc niter_desc
;
700 return single_exit (loop
)
701 && !(loop_preheader_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
)
702 && number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
703 && niter_desc
.control
.no_overflow
704 && (niter
= number_of_latch_executions (loop
))
705 && !chrec_contains_undetermined (niter
)
706 && !chrec_contains_undetermined (scalar_evolution_in_region (scop
,
708 && graphite_can_represent_expr (scop
, loop
, niter
);
711 /* Return true when BEGIN is the preheader edge of a loop with a single exit
715 scop_detection::region_has_one_loop (sese_l s
)
717 edge begin
= s
.entry
;
719 /* Check for a single perfectly nested loop. */
720 if (begin
->dest
->loop_father
->inner
)
723 /* Otherwise, check whether we have adjacent loops. */
724 return (single_pred_p (end
->src
)
725 && begin
->dest
->loop_father
== single_pred (end
->src
)->loop_father
);
728 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
731 scop_detection::add_scop (sese_l s
)
735 /* Do not add scops with only one loop. */
736 if (region_has_one_loop (s
))
738 DEBUG_PRINT (dp
<< "[scop-detection-fail] Discarding one loop SCoP: ";
739 print_sese (dump_file
, s
));
743 if (get_exit_bb (s
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
745 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
746 << "Discarding SCoP exiting to return: ";
747 print_sese (dump_file
, s
));
751 /* Remove all the scops which are subsumed by s. */
754 /* Remove intersecting scops. FIXME: It will be a good idea to keep
755 the non-intersecting part of the scop already in the list. */
756 remove_intersecting_scops (s
);
759 DEBUG_PRINT (dp
<< "[scop-detection] Adding SCoP: "; print_sese (dump_file
, s
));
762 /* Return true when a statement in SCOP cannot be represented by Graphite.
763 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
764 Limit the number of bbs between adjacent loops to
765 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
768 scop_detection::harmful_loop_in_region (sese_l scop
) const
770 basic_block exit_bb
= get_exit_bb (scop
);
771 basic_block entry_bb
= get_entry_bb (scop
);
773 DEBUG_PRINT (dp
<< "[checking-harmful-bbs] ";
774 print_sese (dump_file
, scop
));
775 gcc_assert (dominated_by_p (CDI_DOMINATORS
, exit_bb
, entry_bb
));
777 auto_vec
<basic_block
> worklist
;
780 worklist
.safe_push (entry_bb
);
781 while (! worklist
.is_empty ())
783 basic_block bb
= worklist
.pop ();
784 DEBUG_PRINT (dp
<< "Visiting bb_" << bb
->index
<< "\n");
786 /* The basic block should not be part of an irreducible loop. */
787 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
790 /* Check for unstructured control flow: CFG not generated by structured
792 if (bb
->succs
->length () > 1)
796 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
797 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb
, e
->dest
)
798 && !dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
802 /* Collect all loops in the current region. */
803 loop_p loop
= bb
->loop_father
;
804 if (loop_in_sese_p (loop
, scop
))
805 bitmap_set_bit (loops
, loop
->num
);
807 /* Check for harmful statements in basic blocks part of the region. */
808 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
809 !gsi_end_p (gsi
); gsi_next (&gsi
))
810 if (!stmt_simple_for_scop_p (scop
, gsi_stmt (gsi
), bb
))
814 for (basic_block dom
= first_dom_son (CDI_DOMINATORS
, bb
);
816 dom
= next_dom_son (CDI_DOMINATORS
, dom
))
817 worklist
.safe_push (dom
);
820 /* Go through all loops and check that they are still valid in the combined
824 EXECUTE_IF_SET_IN_BITMAP (loops
, 0, j
, bi
)
826 loop_p loop
= (*current_loops
->larray
)[j
];
827 gcc_assert (loop
->num
== (int) j
);
829 /* Check if the loop nests are to be optimized for speed. */
831 && ! optimize_loop_for_speed_p (loop
))
833 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_"
834 << loop
->num
<< " is not on a hot path.\n");
838 if (! can_represent_loop (loop
, scop
))
840 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot represent loop_"
841 << loop
->num
<< "\n");
845 if (! loop_ivs_can_be_represented (loop
))
847 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
848 << "IV cannot be represented.\n");
852 /* Check if all loop nests have at least one data reference.
853 ??? This check is expensive and loops premature at this point.
854 If important to retain we can pre-compute this for all innermost
855 loops and reject those when we build a SESE region for a loop
856 during SESE discovery. */
858 && ! loop_nest_has_data_refs (loop
))
860 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
861 << "does not have any data reference.\n");
869 /* Returns true if S1 subsumes/surrounds S2. */
871 scop_detection::subsumes (sese_l s1
, sese_l s2
)
873 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
875 && dominated_by_p (CDI_POST_DOMINATORS
, s2
.exit
->dest
,
881 /* Remove a SCoP which is subsumed by S1. */
883 scop_detection::remove_subscops (sese_l s1
)
887 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
889 if (subsumes (s1
, *s2
))
891 DEBUG_PRINT (dp
<< "Removing sub-SCoP";
892 print_sese (dump_file
, *s2
));
893 scops
.unordered_remove (j
);
898 /* Returns true if S1 intersects with S2. Since we already know that S1 does
899 not subsume S2 or vice-versa, we only check for entry bbs. */
902 scop_detection::intersects (sese_l s1
, sese_l s2
)
904 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
906 && !dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
909 if ((s1
.exit
== s2
.entry
) || (s2
.exit
== s1
.entry
))
915 /* Remove one of the scops when it intersects with any other. */
918 scop_detection::remove_intersecting_scops (sese_l s1
)
922 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
924 if (intersects (s1
, *s2
))
926 DEBUG_PRINT (dp
<< "Removing intersecting SCoP";
927 print_sese (dump_file
, *s2
);
928 dp
<< "Intersects with:";
929 print_sese (dump_file
, s1
));
930 scops
.unordered_remove (j
);
935 /* Something like "n * m" is not allowed. */
938 scop_detection::graphite_can_represent_init (tree e
)
940 switch (TREE_CODE (e
))
942 case POLYNOMIAL_CHREC
:
943 return graphite_can_represent_init (CHREC_LEFT (e
))
944 && graphite_can_represent_init (CHREC_RIGHT (e
));
947 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
948 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
949 && tree_fits_shwi_p (TREE_OPERAND (e
, 1));
951 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
952 && tree_fits_shwi_p (TREE_OPERAND (e
, 0));
955 case POINTER_PLUS_EXPR
:
957 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
958 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
963 case NON_LVALUE_EXPR
:
964 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
973 /* Return true when SCEV can be represented in the polyhedral model.
975 An expression can be represented, if it can be expressed as an
976 affine expression. For loops (i, j) and parameters (m, n) all
977 affine expressions are of the form:
979 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
981 1 i + 20 j + (-2) m + 25
983 Something like "i * n" or "n * m" is not allowed. */
986 scop_detection::graphite_can_represent_scev (tree scev
)
988 if (chrec_contains_undetermined (scev
))
991 /* We disable the handling of pointer types, because it’s currently not
992 supported by Graphite with the isl AST generator. SSA_NAME nodes are
993 the only nodes, which are disabled in case they are pointers to object
994 types, but this can be changed. */
996 if (POINTER_TYPE_P (TREE_TYPE (scev
)) && TREE_CODE (scev
) == SSA_NAME
)
999 switch (TREE_CODE (scev
))
1004 case NON_LVALUE_EXPR
:
1005 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0));
1008 case POINTER_PLUS_EXPR
:
1010 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1011 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1014 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
1015 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
1016 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
1017 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
1018 && graphite_can_represent_init (scev
)
1019 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1020 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1022 case POLYNOMIAL_CHREC
:
1023 /* Check for constant strides. With a non constant stride of
1024 'n' we would have a value of 'iv * n'. Also check that the
1025 initial value can represented: for example 'n * m' cannot be
1027 if (!evolution_function_right_is_integer_cst (scev
)
1028 || !graphite_can_represent_init (scev
))
1030 return graphite_can_represent_scev (CHREC_LEFT (scev
));
1036 /* Only affine functions can be represented. */
1037 if (tree_contains_chrecs (scev
, NULL
) || !scev_is_linear_expression (scev
))
1043 /* Return true when EXPR can be represented in the polyhedral model.
1045 This means an expression can be represented, if it is linear with respect to
1046 the loops and the strides are non parametric. LOOP is the place where the
1047 expr will be evaluated. SCOP defines the region we analyse. */
1050 scop_detection::graphite_can_represent_expr (sese_l scop
, loop_p loop
,
1053 tree scev
= scalar_evolution_in_region (scop
, loop
, expr
);
1054 return graphite_can_represent_scev (scev
);
1057 /* Return true if the data references of STMT can be represented by Graphite.
1058 We try to analyze the data references in a loop contained in the SCOP. */
1061 scop_detection::stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
)
1063 loop_p nest
= outermost_loop_in_sese (scop
, gimple_bb (stmt
));
1064 loop_p loop
= loop_containing_stmt (stmt
);
1065 if (!loop_in_sese_p (loop
, scop
))
1068 auto_vec
<data_reference_p
> drs
;
1069 if (! graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
))
1073 data_reference_p dr
;
1074 FOR_EACH_VEC_ELT (drs
, j
, dr
)
1076 for (unsigned i
= 0; i
< DR_NUM_DIMENSIONS (dr
); ++i
)
1077 if (! graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
)))
1084 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1085 Calls have side-effects, except those to const or pure
1089 stmt_has_side_effects (gimple
*stmt
)
1091 if (gimple_has_volatile_ops (stmt
)
1092 || (gimple_code (stmt
) == GIMPLE_CALL
1093 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
1094 || (gimple_code (stmt
) == GIMPLE_ASM
))
1096 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1097 << "Statement has side-effects:\n";
1098 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1104 /* Return true only when STMT is simple enough for being handled by Graphite.
1105 This depends on SCOP, as the parameters are initialized relatively to
1106 this basic block, the linear functions are initialized based on the outermost
1107 loop containing STMT inside the SCOP. BB is the place where we try to
1108 evaluate the STMT. */
1111 scop_detection::stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
1112 basic_block bb
) const
1116 if (is_gimple_debug (stmt
))
1119 if (stmt_has_side_effects (stmt
))
1122 if (!stmt_has_simple_data_refs_p (scop
, stmt
))
1124 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1125 << "Graphite cannot handle data-refs in stmt:\n";
1126 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
););
1130 switch (gimple_code (stmt
))
1137 /* We can handle all binary comparisons. Inequalities are
1138 also supported as they can be represented with union of
1140 enum tree_code code
= gimple_cond_code (stmt
);
1141 if (!(code
== LT_EXPR
1146 || code
== NE_EXPR
))
1148 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1149 << "Graphite cannot handle cond stmt:\n";
1150 print_gimple_stmt (dump_file
, stmt
, 0,
1151 TDF_VOPS
| TDF_MEMSYMS
));
1155 loop_p loop
= bb
->loop_father
;
1156 for (unsigned i
= 0; i
< 2; ++i
)
1158 tree op
= gimple_op (stmt
, i
);
1159 if (!graphite_can_represent_expr (scop
, loop
, op
)
1160 /* We can only constrain on integer type. */
1161 || (TREE_CODE (TREE_TYPE (op
)) != INTEGER_TYPE
))
1163 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1164 << "Graphite cannot represent stmt:\n";
1165 print_gimple_stmt (dump_file
, stmt
, 0,
1166 TDF_VOPS
| TDF_MEMSYMS
));
1179 /* These nodes cut a new scope. */
1181 dp
<< "[scop-detection-fail] "
1182 << "Gimple stmt not handled in Graphite:\n";
1183 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1188 /* Returns the number of pbbs that are in loops contained in SCOP. */
1191 scop_detection::nb_pbbs_in_loops (scop_p scop
)
1197 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1198 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), scop
->scop_info
->region
))
1204 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
1205 Otherwise returns -1. */
1208 parameter_index_in_region_1 (tree name
, sese_info_p region
)
1213 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1215 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
1222 /* When the parameter NAME is in REGION, returns its index in
1223 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
1224 and returns the index of NAME. */
1227 parameter_index_in_region (tree name
, sese_info_p region
)
1231 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1233 /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
1234 if (TREE_CODE (TREE_TYPE (name
)) != INTEGER_TYPE
)
1237 if (!invariant_in_sese_p_rec (name
, region
->region
, NULL
))
1240 i
= parameter_index_in_region_1 (name
, region
);
1244 i
= region
->params
.length ();
1245 region
->params
.safe_push (name
);
1249 /* In the context of sese S, scan the expression E and translate it to
1250 a linear expression C. When parsing a symbolic multiplication, K
1251 represents the constant multiplier of an expression containing
1255 scan_tree_for_params (sese_info_p s
, tree e
)
1257 if (e
== chrec_dont_know
)
1260 switch (TREE_CODE (e
))
1262 case POLYNOMIAL_CHREC
:
1263 scan_tree_for_params (s
, CHREC_LEFT (e
));
1267 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1268 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1270 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1274 case POINTER_PLUS_EXPR
:
1276 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1277 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1283 case NON_LVALUE_EXPR
:
1284 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1288 parameter_index_in_region (e
, s
);
1304 /* Find parameters with respect to REGION in BB. We are looking in memory
1305 access functions, conditions and loop bounds. */
1308 find_params_in_bb (sese_info_p region
, gimple_poly_bb_p gbb
)
1310 /* Find parameters in the access functions of data references. */
1312 data_reference_p dr
;
1313 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
1314 for (unsigned j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
1315 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
1317 /* Find parameters in conditional statements. */
1319 loop_p loop
= GBB_BB (gbb
)->loop_father
;
1320 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1322 tree lhs
= scalar_evolution_in_region (region
->region
, loop
,
1323 gimple_cond_lhs (stmt
));
1324 tree rhs
= scalar_evolution_in_region (region
->region
, loop
,
1325 gimple_cond_rhs (stmt
));
1327 scan_tree_for_params (region
, lhs
);
1328 scan_tree_for_params (region
, rhs
);
1332 /* Record the parameters used in the SCOP. A variable is a parameter
1333 in a scop if it does not vary during the execution of that scop. */
1336 find_scop_parameters (scop_p scop
)
1339 sese_info_p region
= scop
->scop_info
;
1342 /* Find the parameters used in the loop bounds. */
1343 FOR_EACH_VEC_ELT (region
->loop_nest
, i
, loop
)
1345 tree nb_iters
= number_of_latch_executions (loop
);
1347 if (!chrec_contains_symbols (nb_iters
))
1350 nb_iters
= scalar_evolution_in_region (region
->region
, loop
, nb_iters
);
1351 scan_tree_for_params (region
, nb_iters
);
1354 /* Find the parameters used in data accesses. */
1356 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1357 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1359 int nbp
= sese_nb_params (region
);
1360 scop_set_nb_params (scop
, nbp
);
1363 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1366 build_cross_bb_scalars_def (scop_p scop
, tree def
, basic_block def_bb
,
1369 if (!def
|| !is_gimple_reg (def
))
1372 bool scev_analyzable
= scev_analyzable_p (def
, scop
->scop_info
->region
);
1375 imm_use_iterator imm_iter
;
1376 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1377 /* Do not gather scalar variables that can be analyzed by SCEV as they can
1378 be generated out of the induction variables. */
1379 if ((! scev_analyzable
1380 /* But gather SESE liveouts as we otherwise fail to rewrite their
1382 || ! bb_in_sese_p (gimple_bb (use_stmt
), scop
->scop_info
->region
))
1383 && ((def_bb
!= gimple_bb (use_stmt
) && !is_gimple_debug (use_stmt
))
1384 /* PHIs have their effect at "BBs" on the edges. See PR79622. */
1385 || gimple_code (SSA_NAME_DEF_STMT (def
)) == GIMPLE_PHI
))
1387 writes
->safe_push (def
);
1388 DEBUG_PRINT (dp
<< "Adding scalar write: ";
1389 print_generic_expr (dump_file
, def
);
1390 dp
<< "\nFrom stmt: ";
1391 print_gimple_stmt (dump_file
,
1392 SSA_NAME_DEF_STMT (def
), 0));
1393 /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
1394 before all the uses have been visited. */
1395 BREAK_FROM_IMM_USE_STMT (imm_iter
);
1399 /* Record USE if it is defined in other bbs different than USE_STMT
1403 build_cross_bb_scalars_use (scop_p scop
, tree use
, gimple
*use_stmt
,
1404 vec
<scalar_use
> *reads
)
1407 if (!is_gimple_reg (use
))
1410 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1411 generated out of the induction variables. */
1412 if (scev_analyzable_p (use
, scop
->scop_info
->region
))
1415 gimple
*def_stmt
= SSA_NAME_DEF_STMT (use
);
1416 if (gimple_bb (def_stmt
) != gimple_bb (use_stmt
)
1417 /* PHIs have their effect at "BBs" on the edges. See PR79622. */
1418 || gimple_code (def_stmt
) == GIMPLE_PHI
)
1420 DEBUG_PRINT (dp
<< "Adding scalar read: ";
1421 print_generic_expr (dump_file
, use
);
1422 dp
<< "\nFrom stmt: ";
1423 print_gimple_stmt (dump_file
, use_stmt
, 0));
1424 reads
->safe_push (std::make_pair (use_stmt
, use
));
1428 /* Record all scalar variables that are defined and used in different BBs of the
1432 graphite_find_cross_bb_scalar_vars (scop_p scop
, gimple
*stmt
,
1433 vec
<scalar_use
> *reads
, vec
<tree
> *writes
)
1437 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
1438 def
= gimple_assign_lhs (stmt
);
1439 else if (gimple_code (stmt
) == GIMPLE_CALL
)
1440 def
= gimple_call_lhs (stmt
);
1441 else if (gimple_code (stmt
) == GIMPLE_PHI
)
1442 def
= gimple_phi_result (stmt
);
1447 build_cross_bb_scalars_def (scop
, def
, gimple_bb (stmt
), writes
);
1450 use_operand_p use_p
;
1451 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1453 tree use
= USE_FROM_PTR (use_p
);
1454 build_cross_bb_scalars_use (scop
, use
, stmt
, reads
);
1458 /* Generates a polyhedral black box only if the bb contains interesting
1461 static gimple_poly_bb_p
1462 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
1464 vec
<data_reference_p
> drs
= vNULL
;
1465 vec
<tree
> writes
= vNULL
;
1466 vec
<scalar_use
> reads
= vNULL
;
1468 sese_l region
= scop
->scop_info
->region
;
1469 loop_p nest
= outermost_loop_in_sese (region
, bb
);
1471 loop_p loop
= bb
->loop_father
;
1472 if (!loop_in_sese_p (loop
, region
))
1475 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1478 gimple
*stmt
= gsi_stmt (gsi
);
1479 if (is_gimple_debug (stmt
))
1482 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1483 graphite_find_cross_bb_scalar_vars (scop
, stmt
, &reads
, &writes
);
1486 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1488 if (!virtual_operand_p (gimple_phi_result (psi
.phi ())))
1489 graphite_find_cross_bb_scalar_vars (scop
, psi
.phi (), &reads
, &writes
);
1491 if (drs
.is_empty () && writes
.is_empty () && reads
.is_empty ())
1494 return new_gimple_poly_bb (bb
, drs
, reads
, writes
);
1497 /* Compute alias-sets for all data references in DRS. */
1500 build_alias_set (scop_p scop
)
1502 int num_vertices
= scop
->drs
.length ();
1503 struct graph
*g
= new_graph (num_vertices
);
1508 FOR_EACH_VEC_ELT (scop
->drs
, i
, dr1
)
1509 for (j
= i
+1; scop
->drs
.iterate (j
, &dr2
); j
++)
1510 if (dr_may_alias_p (dr1
->dr
, dr2
->dr
, true))
1512 /* Dependences in the same alias set need to be handled
1513 by just looking at DR_ACCESS_FNs. */
1514 if (DR_NUM_DIMENSIONS (dr1
->dr
) == 0
1515 || DR_NUM_DIMENSIONS (dr1
->dr
) != DR_NUM_DIMENSIONS (dr2
->dr
)
1516 || ! operand_equal_p (DR_BASE_OBJECT (dr1
->dr
),
1517 DR_BASE_OBJECT (dr2
->dr
),
1519 || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1
->dr
)),
1520 TREE_TYPE (DR_BASE_OBJECT (dr2
->dr
))))
1529 all_vertices
= XNEWVEC (int, num_vertices
);
1530 for (i
= 0; i
< num_vertices
; i
++)
1531 all_vertices
[i
] = i
;
1533 graphds_dfs (g
, all_vertices
, num_vertices
, NULL
, true, NULL
);
1534 free (all_vertices
);
1536 for (i
= 0; i
< g
->n_vertices
; i
++)
1537 scop
->drs
[i
].alias_set
= g
->vertices
[i
].component
+ 1;
1543 /* Gather BBs and conditions for a SCOP. */
1544 class gather_bbs
: public dom_walker
1547 gather_bbs (cdi_direction
, scop_p
);
1549 virtual edge
before_dom_children (basic_block
);
1550 virtual void after_dom_children (basic_block
);
1553 auto_vec
<gimple
*, 3> conditions
, cases
;
1557 gather_bbs::gather_bbs (cdi_direction direction
, scop_p scop
)
1558 : dom_walker (direction
), scop (scop
)
1562 /* Record in execution order the loops fully contained in the region. */
1565 record_loop_in_sese (basic_block bb
, sese_info_p region
)
1567 loop_p father
= bb
->loop_father
;
1568 if (loop_in_sese_p (father
, region
->region
))
1573 FOR_EACH_VEC_ELT (region
->loop_nest
, j
, loop0
)
1574 if (father
== loop0
)
1580 region
->loop_nest
.safe_push (father
);
1584 /* Call-back for dom_walk executed before visiting the dominated
1588 gather_bbs::before_dom_children (basic_block bb
)
1590 sese_info_p region
= scop
->scop_info
;
1591 if (!bb_in_sese_p (bb
, region
->region
))
1594 record_loop_in_sese (bb
, region
);
1596 gcond
*stmt
= single_pred_cond_non_loop_exit (bb
);
1600 edge e
= single_pred_edge (bb
);
1602 conditions
.safe_push (stmt
);
1604 if (e
->flags
& EDGE_TRUE_VALUE
)
1605 cases
.safe_push (stmt
);
1607 cases
.safe_push (NULL
);
1610 scop
->scop_info
->bbs
.safe_push (bb
);
1612 gimple_poly_bb_p gbb
= try_generate_gimple_bb (scop
, bb
);
1616 GBB_CONDITIONS (gbb
) = conditions
.copy ();
1617 GBB_CONDITION_CASES (gbb
) = cases
.copy ();
1619 poly_bb_p pbb
= new_poly_bb (scop
, gbb
);
1620 scop
->pbbs
.safe_push (pbb
);
1623 data_reference_p dr
;
1624 FOR_EACH_VEC_ELT (gbb
->data_refs
, i
, dr
)
1626 DEBUG_PRINT (dp
<< "Adding memory ";
1631 print_generic_expr (dump_file
, dr
->ref
);
1632 dp
<< "\nFrom stmt: ";
1633 print_gimple_stmt (dump_file
, dr
->stmt
, 0));
1635 scop
->drs
.safe_push (dr_info (dr
, pbb
));
1641 /* Call-back for dom_walk executed after visiting the dominated
1645 gather_bbs::after_dom_children (basic_block bb
)
1647 if (!bb_in_sese_p (bb
, scop
->scop_info
->region
))
1650 if (single_pred_cond_non_loop_exit (bb
))
1658 /* Compute sth like an execution order, dominator order with first executing
1659 edges that stay inside the current loop, delaying processing exit edges. */
1661 static vec
<unsigned> order
;
1664 get_order (scop_p scop
, basic_block bb
, vec
<unsigned> *order
, unsigned *dfs_num
)
1666 if (! bb_in_sese_p (bb
, scop
->scop_info
->region
))
1669 (*order
)[bb
->index
] = (*dfs_num
)++;
1670 for (basic_block son
= first_dom_son (CDI_DOMINATORS
, bb
);
1672 son
= next_dom_son (CDI_DOMINATORS
, son
))
1673 if (flow_bb_inside_loop_p (bb
->loop_father
, son
))
1674 get_order (scop
, son
, order
, dfs_num
);
1675 for (basic_block son
= first_dom_son (CDI_DOMINATORS
, bb
);
1677 son
= next_dom_son (CDI_DOMINATORS
, son
))
1678 if (! flow_bb_inside_loop_p (bb
->loop_father
, son
))
1679 get_order (scop
, son
, order
, dfs_num
);
1682 /* Helper for qsort, sorting after order above. */
1685 cmp_pbbs (const void *pa
, const void *pb
)
1687 poly_bb_p bb1
= *((const poly_bb_p
*)pa
);
1688 poly_bb_p bb2
= *((const poly_bb_p
*)pb
);
1689 if (order
[bb1
->black_box
->bb
->index
] < order
[bb2
->black_box
->bb
->index
])
1691 else if (order
[bb1
->black_box
->bb
->index
] > order
[bb2
->black_box
->bb
->index
])
1697 /* Find Static Control Parts (SCoP) in the current function and pushes
1701 build_scops (vec
<scop_p
> *scops
)
1704 dp
.set_dump_file (dump_file
);
1707 sb
.build_scop_depth (current_loops
->tree_root
);
1709 /* Now create scops from the lightweight SESEs. */
1710 vec
<sese_l
> scops_l
= sb
.get_scops ();
1713 FOR_EACH_VEC_ELT (scops_l
, i
, s
)
1715 scop_p scop
= new_scop (s
->entry
, s
->exit
);
1717 /* Record all basic blocks and their conditions in REGION. */
1718 gather_bbs (CDI_DOMINATORS
, scop
).walk (s
->entry
->dest
);
1720 /* domwalk does not fulfil our code-generations constraints on the
1721 order of pbb which is to produce sth like execution order, delaying
1722 exection of loop exit edges. So compute such order and sort after
1724 order
.create (last_basic_block_for_fn (cfun
));
1725 order
.quick_grow (last_basic_block_for_fn (cfun
));
1726 unsigned dfs_num
= 0;
1727 get_order (scop
, s
->entry
->dest
, &order
, &dfs_num
);
1728 scop
->pbbs
.qsort (cmp_pbbs
);
1731 if (! build_alias_set (scop
))
1733 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot handle dependences\n");
1738 /* Do not optimize a scop containing only PBBs that do not belong
1740 if (sb
.nb_pbbs_in_loops (scop
) == 0)
1742 DEBUG_PRINT (dp
<< "[scop-detection-fail] no data references.\n");
1747 unsigned max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
1748 if (scop
->drs
.length () >= max_arrays
)
1750 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many data references: "
1751 << scop
->drs
.length ()
1752 << " is larger than --param graphite-max-arrays-per-scop="
1753 << max_arrays
<< ".\n");
1758 find_scop_parameters (scop
);
1759 graphite_dim_t max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
1761 if (scop_nb_params (scop
) > max_dim
)
1763 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many parameters: "
1764 << scop_nb_params (scop
)
1765 << " larger than --param graphite-max-nb-scop-params="
1766 << max_dim
<< ".\n");
1771 scops
->safe_push (scop
);
1774 DEBUG_PRINT (dp
<< "number of SCoPs: " << (scops
? scops
->length () : 0););
1777 #endif /* HAVE_isl */