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 /* Returns a COND_EXPR statement when BB has a single predecessor, the
258 edge between BB and its predecessor is not a loop exit edge, and
259 the last statement of the single predecessor is a COND_EXPR. */
262 single_pred_cond_non_loop_exit (basic_block bb
)
264 if (single_pred_p (bb
))
266 edge e
= single_pred_edge (bb
);
267 basic_block pred
= e
->src
;
270 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
273 stmt
= last_stmt (pred
);
275 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
276 return as_a
<gcond
*> (stmt
);
285 /* Build the maximal scop containing LOOPs and add it to SCOPS. */
290 scop_detection () : scops (vNULL
) {}
297 /* A marker for invalid sese_l. */
298 static sese_l invalid_sese
;
300 /* Return the SCOPS in this SCOP_DETECTION. */
308 /* Return an sese_l around the LOOP. */
310 sese_l
get_sese (loop_p loop
);
312 /* Return the closest dominator with a single entry edge. In case of a
313 back-loop the back-edge is not counted. */
315 static edge
get_nearest_dom_with_single_entry (basic_block dom
);
317 /* Return the closest post-dominator with a single exit edge. In case of a
318 back-loop the back-edge is not counted. */
320 static edge
get_nearest_pdom_with_single_exit (basic_block dom
);
322 /* Merge scops at same loop depth and returns the new sese.
323 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
325 sese_l
merge_sese (sese_l first
, sese_l second
) const;
327 /* Build scop outer->inner if possible. */
329 void build_scop_depth (loop_p loop
);
331 /* Return true when BEGIN is the preheader edge of a loop with a single exit
334 static bool region_has_one_loop (sese_l s
);
336 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
338 void add_scop (sese_l s
);
340 /* Returns true if S1 subsumes/surrounds S2. */
341 static bool subsumes (sese_l s1
, sese_l s2
);
343 /* Remove a SCoP which is subsumed by S1. */
344 void remove_subscops (sese_l s1
);
346 /* Returns true if S1 intersects with S2. Since we already know that S1 does
347 not subsume S2 or vice-versa, we only check for entry bbs. */
349 static bool intersects (sese_l s1
, sese_l s2
);
351 /* Remove one of the scops when it intersects with any other. */
353 void remove_intersecting_scops (sese_l s1
);
355 /* Return true when a statement in SCOP cannot be represented by Graphite. */
357 bool harmful_loop_in_region (sese_l scop
) const;
359 /* Return true only when STMT is simple enough for being handled by Graphite.
360 This depends on SCOP, as the parameters are initialized relatively to
361 this basic block, the linear functions are initialized based on the
362 outermost loop containing STMT inside the SCOP. BB is the place where we
363 try to evaluate the STMT. */
365 bool stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
366 basic_block bb
) const;
368 /* Something like "n * m" is not allowed. */
370 static bool graphite_can_represent_init (tree e
);
372 /* Return true when SCEV can be represented in the polyhedral model.
374 An expression can be represented, if it can be expressed as an
375 affine expression. For loops (i, j) and parameters (m, n) all
376 affine expressions are of the form:
378 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
380 1 i + 20 j + (-2) m + 25
382 Something like "i * n" or "n * m" is not allowed. */
384 static bool graphite_can_represent_scev (tree scev
);
386 /* Return true when EXPR can be represented in the polyhedral model.
388 This means an expression can be represented, if it is linear with respect
389 to the loops and the strides are non parametric. LOOP is the place where
390 the expr will be evaluated. SCOP defines the region we analyse. */
392 static bool graphite_can_represent_expr (sese_l scop
, loop_p loop
,
395 /* Return true if the data references of STMT can be represented by Graphite.
396 We try to analyze the data references in a loop contained in the SCOP. */
398 static bool stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
);
400 /* Remove the close phi node at GSI and replace its rhs with the rhs
403 static void remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
);
405 /* Returns true when Graphite can represent LOOP in SCOP.
406 FIXME: For the moment, graphite cannot be used on loops that iterate using
407 induction variables that wrap. */
409 static bool can_represent_loop (loop_p loop
, sese_l scop
);
411 /* Returns the number of pbbs that are in loops contained in SCOP. */
413 static int nb_pbbs_in_loops (scop_p scop
);
419 sese_l
scop_detection::invalid_sese (NULL
, NULL
);
421 /* Return an sese_l around the LOOP. */
424 scop_detection::get_sese (loop_p loop
)
429 edge scop_begin
= loop_preheader_edge (loop
);
430 edge scop_end
= single_exit (loop
);
431 if (!scop_end
|| (scop_end
->flags
& EDGE_COMPLEX
))
433 /* Include the BB with the loop-closed SSA PHI nodes.
434 canonicalize_loop_closed_ssa makes sure that is in proper shape. */
435 if (! single_pred_p (scop_end
->dest
)
436 || ! single_succ_p (scop_end
->dest
)
437 || ! sese_trivially_empty_bb_p (scop_end
->dest
))
439 scop_end
= single_succ_edge (scop_end
->dest
);
441 return sese_l (scop_begin
, scop_end
);
444 /* Return the closest dominator with a single entry edge. */
447 scop_detection::get_nearest_dom_with_single_entry (basic_block dom
)
452 /* If any of the dominators has two predecessors but one of them is a back
453 edge, then that basic block also qualifies as a dominator with single
455 if (dom
->preds
->length () == 2)
457 /* If e1->src dominates e2->src then e1->src will also dominate dom. */
458 edge e1
= (*dom
->preds
)[0];
459 edge e2
= (*dom
->preds
)[1];
460 loop_p l
= dom
->loop_father
;
461 loop_p l1
= e1
->src
->loop_father
;
462 loop_p l2
= e2
->src
->loop_father
;
463 if (l
!= l1
&& l
== l2
464 && dominated_by_p (CDI_DOMINATORS
, e2
->src
, e1
->src
))
466 if (l
!= l2
&& l
== l1
467 && dominated_by_p (CDI_DOMINATORS
, e1
->src
, e2
->src
))
471 while (dom
->preds
->length () != 1)
473 if (dom
->preds
->length () < 1)
475 dom
= get_immediate_dominator (CDI_DOMINATORS
, dom
);
479 return (*dom
->preds
)[0];
482 /* Return the closest post-dominator with a single exit edge. In case of a
483 back-loop the back-edge is not counted. */
486 scop_detection::get_nearest_pdom_with_single_exit (basic_block pdom
)
491 /* If any of the post-dominators has two successors but one of them is a back
492 edge, then that basic block also qualifies as a post-dominator with single
494 if (pdom
->succs
->length () == 2)
496 /* If e1->dest post-dominates e2->dest then e1->dest will also
497 post-dominate pdom. */
498 edge e1
= (*pdom
->succs
)[0];
499 edge e2
= (*pdom
->succs
)[1];
500 loop_p l
= pdom
->loop_father
;
501 loop_p l1
= e1
->dest
->loop_father
;
502 loop_p l2
= e2
->dest
->loop_father
;
503 if (l
!= l1
&& l
== l2
504 && dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, e1
->dest
))
506 if (l
!= l2
&& l
== l1
507 && dominated_by_p (CDI_POST_DOMINATORS
, e1
->dest
, e2
->dest
))
511 while (pdom
->succs
->length () != 1)
513 if (pdom
->succs
->length () < 1)
515 pdom
= get_immediate_dominator (CDI_POST_DOMINATORS
, pdom
);
520 return (*pdom
->succs
)[0];
523 /* Merge scops at same loop depth and returns the new sese.
524 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
527 scop_detection::merge_sese (sese_l first
, sese_l second
) const
529 /* In the trivial case first/second may be NULL. */
535 DEBUG_PRINT (dp
<< "[scop-detection] try merging sese s1: ";
536 print_sese (dump_file
, first
);
537 dp
<< "[scop-detection] try merging sese s2: ";
538 print_sese (dump_file
, second
));
540 /* Assumption: Both the sese's should be at the same loop depth or one scop
541 should subsume the other like in case of nested loops. */
543 /* Find the common dominators for entry,
544 and common post-dominators for the exit. */
545 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
,
546 get_entry_bb (first
),
547 get_entry_bb (second
));
549 edge entry
= get_nearest_dom_with_single_entry (dom
);
551 if (!entry
|| (entry
->flags
& EDGE_IRREDUCIBLE_LOOP
))
554 basic_block pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
,
556 get_exit_bb (second
));
557 pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
, dom
, pdom
);
559 edge exit
= get_nearest_pdom_with_single_exit (pdom
);
561 if (!exit
|| (exit
->flags
& EDGE_IRREDUCIBLE_LOOP
))
564 sese_l
combined (entry
, exit
);
566 DEBUG_PRINT (dp
<< "[scop-detection] checking combined sese: ";
567 print_sese (dump_file
, combined
));
569 /* FIXME: We could iterate to find the dom which dominates pdom, and pdom
570 which post-dominates dom, until it stabilizes. Also, ENTRY->SRC and
571 EXIT->DEST should be in the same loop nest. */
572 if (!dominated_by_p (CDI_DOMINATORS
, pdom
, dom
)
573 || loop_depth (entry
->src
->loop_father
)
574 != loop_depth (exit
->dest
->loop_father
))
577 /* For now we just bail out when there is a loop exit in the region
578 that is not also the exit of the region. We could enlarge the
579 region to cover the loop that region exits to. See PR79977. */
580 if (loop_outer (entry
->src
->loop_father
))
582 vec
<edge
> exits
= get_loop_exit_edges (entry
->src
->loop_father
);
583 for (unsigned i
= 0; i
< exits
.length (); ++i
)
586 && bb_in_region (exits
[i
]->src
, entry
->dest
, exit
->src
))
588 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
596 /* For now we just want to bail out when exit does not post-dominate entry.
597 TODO: We might just add a basic_block at the exit to make exit
598 post-dominate entry (the entire region). */
599 if (!dominated_by_p (CDI_POST_DOMINATORS
, get_entry_bb (combined
),
600 get_exit_bb (combined
))
601 || !dominated_by_p (CDI_DOMINATORS
, get_exit_bb (combined
),
602 get_entry_bb (combined
)))
604 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
608 DEBUG_PRINT (dp
<< "[merged-sese] s1: "; print_sese (dump_file
, combined
));
613 /* Build scop outer->inner if possible. */
616 scop_detection::build_scop_depth (loop_p loop
)
618 sese_l s
= invalid_sese
;
622 sese_l next
= get_sese (loop
);
624 || harmful_loop_in_region (next
))
628 build_scop_depth (loop
);
635 sese_l combined
= merge_sese (s
, next
);
637 || harmful_loop_in_region (combined
))
651 /* Returns true when Graphite can represent LOOP in SCOP.
652 FIXME: For the moment, graphite cannot be used on loops that iterate using
653 induction variables that wrap. */
656 scop_detection::can_represent_loop (loop_p loop
, sese_l scop
)
659 struct tree_niter_desc niter_desc
;
661 return single_exit (loop
)
662 && !(loop_preheader_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
)
663 && number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
664 && niter_desc
.control
.no_overflow
665 && (niter
= number_of_latch_executions (loop
))
666 && !chrec_contains_undetermined (niter
)
667 && !chrec_contains_undetermined (scalar_evolution_in_region (scop
,
669 && graphite_can_represent_expr (scop
, loop
, niter
);
672 /* Return true when BEGIN is the preheader edge of a loop with a single exit
676 scop_detection::region_has_one_loop (sese_l s
)
678 edge begin
= s
.entry
;
680 /* Check for a single perfectly nested loop. */
681 if (begin
->dest
->loop_father
->inner
)
684 /* Otherwise, check whether we have adjacent loops. */
685 return (single_pred_p (end
->src
)
686 && begin
->dest
->loop_father
== single_pred (end
->src
)->loop_father
);
689 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
692 scop_detection::add_scop (sese_l s
)
696 /* Do not add scops with only one loop. */
697 if (region_has_one_loop (s
))
699 DEBUG_PRINT (dp
<< "[scop-detection-fail] Discarding one loop SCoP: ";
700 print_sese (dump_file
, s
));
704 if (get_exit_bb (s
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
706 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
707 << "Discarding SCoP exiting to return: ";
708 print_sese (dump_file
, s
));
712 /* Remove all the scops which are subsumed by s. */
715 /* Remove intersecting scops. FIXME: It will be a good idea to keep
716 the non-intersecting part of the scop already in the list. */
717 remove_intersecting_scops (s
);
720 DEBUG_PRINT (dp
<< "[scop-detection] Adding SCoP: "; print_sese (dump_file
, s
));
723 /* Return true when a statement in SCOP cannot be represented by Graphite. */
726 scop_detection::harmful_loop_in_region (sese_l scop
) const
728 basic_block exit_bb
= get_exit_bb (scop
);
729 basic_block entry_bb
= get_entry_bb (scop
);
731 DEBUG_PRINT (dp
<< "[checking-harmful-bbs] ";
732 print_sese (dump_file
, scop
));
733 gcc_assert (dominated_by_p (CDI_DOMINATORS
, exit_bb
, entry_bb
));
735 auto_vec
<basic_block
> worklist
;
738 worklist
.safe_push (entry_bb
);
739 while (! worklist
.is_empty ())
741 basic_block bb
= worklist
.pop ();
742 DEBUG_PRINT (dp
<< "Visiting bb_" << bb
->index
<< "\n");
744 /* The basic block should not be part of an irreducible loop. */
745 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
748 /* Check for unstructured control flow: CFG not generated by structured
750 if (bb
->succs
->length () > 1)
754 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
755 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb
, e
->dest
)
756 && !dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
760 /* Collect all loops in the current region. */
761 loop_p loop
= bb
->loop_father
;
762 if (loop_in_sese_p (loop
, scop
))
763 bitmap_set_bit (loops
, loop
->num
);
765 /* Check for harmful statements in basic blocks part of the region. */
766 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
767 !gsi_end_p (gsi
); gsi_next (&gsi
))
768 if (!stmt_simple_for_scop_p (scop
, gsi_stmt (gsi
), bb
))
772 for (basic_block dom
= first_dom_son (CDI_DOMINATORS
, bb
);
774 dom
= next_dom_son (CDI_DOMINATORS
, dom
))
775 worklist
.safe_push (dom
);
778 /* Go through all loops and check that they are still valid in the combined
782 EXECUTE_IF_SET_IN_BITMAP (loops
, 0, j
, bi
)
784 loop_p loop
= (*current_loops
->larray
)[j
];
785 gcc_assert (loop
->num
== (int) j
);
787 /* Check if the loop nests are to be optimized for speed. */
789 && ! optimize_loop_for_speed_p (loop
))
791 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_"
792 << loop
->num
<< " is not on a hot path.\n");
796 if (! can_represent_loop (loop
, scop
))
798 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot represent loop_"
799 << loop
->num
<< "\n");
803 /* Check if all loop nests have at least one data reference.
804 ??? This check is expensive and loops premature at this point.
805 If important to retain we can pre-compute this for all innermost
806 loops and reject those when we build a SESE region for a loop
807 during SESE discovery. */
809 && ! loop_nest_has_data_refs (loop
))
811 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
812 << "does not have any data reference.\n");
820 /* Returns true if S1 subsumes/surrounds S2. */
822 scop_detection::subsumes (sese_l s1
, sese_l s2
)
824 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
826 && dominated_by_p (CDI_POST_DOMINATORS
, s2
.exit
->dest
,
832 /* Remove a SCoP which is subsumed by S1. */
834 scop_detection::remove_subscops (sese_l s1
)
838 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
840 if (subsumes (s1
, *s2
))
842 DEBUG_PRINT (dp
<< "Removing sub-SCoP";
843 print_sese (dump_file
, *s2
));
844 scops
.unordered_remove (j
);
849 /* Returns true if S1 intersects with S2. Since we already know that S1 does
850 not subsume S2 or vice-versa, we only check for entry bbs. */
853 scop_detection::intersects (sese_l s1
, sese_l s2
)
855 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
857 && !dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
860 if ((s1
.exit
== s2
.entry
) || (s2
.exit
== s1
.entry
))
866 /* Remove one of the scops when it intersects with any other. */
869 scop_detection::remove_intersecting_scops (sese_l s1
)
873 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
875 if (intersects (s1
, *s2
))
877 DEBUG_PRINT (dp
<< "Removing intersecting SCoP";
878 print_sese (dump_file
, *s2
);
879 dp
<< "Intersects with:";
880 print_sese (dump_file
, s1
));
881 scops
.unordered_remove (j
);
886 /* Something like "n * m" is not allowed. */
889 scop_detection::graphite_can_represent_init (tree e
)
891 switch (TREE_CODE (e
))
893 case POLYNOMIAL_CHREC
:
894 return graphite_can_represent_init (CHREC_LEFT (e
))
895 && graphite_can_represent_init (CHREC_RIGHT (e
));
898 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
899 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
900 && tree_fits_shwi_p (TREE_OPERAND (e
, 1));
902 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
903 && tree_fits_shwi_p (TREE_OPERAND (e
, 0));
906 case POINTER_PLUS_EXPR
:
908 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
909 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
914 case NON_LVALUE_EXPR
:
915 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
924 /* Return true when SCEV can be represented in the polyhedral model.
926 An expression can be represented, if it can be expressed as an
927 affine expression. For loops (i, j) and parameters (m, n) all
928 affine expressions are of the form:
930 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
932 1 i + 20 j + (-2) m + 25
934 Something like "i * n" or "n * m" is not allowed. */
937 scop_detection::graphite_can_represent_scev (tree scev
)
939 if (chrec_contains_undetermined (scev
))
942 switch (TREE_CODE (scev
))
947 case NON_LVALUE_EXPR
:
948 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0));
951 case POINTER_PLUS_EXPR
:
953 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
954 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
957 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
958 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
959 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
960 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
961 && graphite_can_represent_init (scev
)
962 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
963 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
965 case POLYNOMIAL_CHREC
:
966 /* Check for constant strides. With a non constant stride of
967 'n' we would have a value of 'iv * n'. Also check that the
968 initial value can represented: for example 'n * m' cannot be
970 if (!evolution_function_right_is_integer_cst (scev
)
971 || !graphite_can_represent_init (scev
))
973 return graphite_can_represent_scev (CHREC_LEFT (scev
));
979 /* Only affine functions can be represented. */
980 if (tree_contains_chrecs (scev
, NULL
) || !scev_is_linear_expression (scev
))
986 /* Return true when EXPR can be represented in the polyhedral model.
988 This means an expression can be represented, if it is linear with respect to
989 the loops and the strides are non parametric. LOOP is the place where the
990 expr will be evaluated. SCOP defines the region we analyse. */
993 scop_detection::graphite_can_represent_expr (sese_l scop
, loop_p loop
,
996 tree scev
= scalar_evolution_in_region (scop
, loop
, expr
);
997 return graphite_can_represent_scev (scev
);
1000 /* Return true if the data references of STMT can be represented by Graphite.
1001 We try to analyze the data references in a loop contained in the SCOP. */
1004 scop_detection::stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
)
1007 loop_p loop
= loop_containing_stmt (stmt
);
1008 if (!loop_in_sese_p (loop
, scop
))
1011 nest
= outermost_loop_in_sese (scop
, gimple_bb (stmt
));
1013 auto_vec
<data_reference_p
> drs
;
1014 if (! graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
))
1018 data_reference_p dr
;
1019 FOR_EACH_VEC_ELT (drs
, j
, dr
)
1021 for (unsigned i
= 0; i
< DR_NUM_DIMENSIONS (dr
); ++i
)
1022 if (! graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
)))
1029 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1030 Calls have side-effects, except those to const or pure
1034 stmt_has_side_effects (gimple
*stmt
)
1036 if (gimple_has_volatile_ops (stmt
)
1037 || (gimple_code (stmt
) == GIMPLE_CALL
1038 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
1039 || (gimple_code (stmt
) == GIMPLE_ASM
))
1041 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1042 << "Statement has side-effects:\n";
1043 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1049 /* Return true only when STMT is simple enough for being handled by Graphite.
1050 This depends on SCOP, as the parameters are initialized relatively to
1051 this basic block, the linear functions are initialized based on the outermost
1052 loop containing STMT inside the SCOP. BB is the place where we try to
1053 evaluate the STMT. */
1056 scop_detection::stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
1057 basic_block bb
) const
1061 if (is_gimple_debug (stmt
))
1064 if (stmt_has_side_effects (stmt
))
1067 if (!stmt_has_simple_data_refs_p (scop
, stmt
))
1069 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1070 << "Graphite cannot handle data-refs in stmt:\n";
1071 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
););
1075 switch (gimple_code (stmt
))
1082 /* We can handle all binary comparisons. Inequalities are
1083 also supported as they can be represented with union of
1085 enum tree_code code
= gimple_cond_code (stmt
);
1086 if (!(code
== LT_EXPR
1091 || code
== NE_EXPR
))
1093 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1094 << "Graphite cannot handle cond stmt:\n";
1095 print_gimple_stmt (dump_file
, stmt
, 0,
1096 TDF_VOPS
| TDF_MEMSYMS
));
1100 loop_p loop
= bb
->loop_father
;
1101 for (unsigned i
= 0; i
< 2; ++i
)
1103 tree op
= gimple_op (stmt
, i
);
1104 if (!graphite_can_represent_expr (scop
, loop
, op
)
1105 /* We can only constrain on integer type. */
1106 || (TREE_CODE (TREE_TYPE (op
)) != INTEGER_TYPE
))
1108 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1109 << "Graphite cannot represent stmt:\n";
1110 print_gimple_stmt (dump_file
, stmt
, 0,
1111 TDF_VOPS
| TDF_MEMSYMS
));
1124 /* These nodes cut a new scope. */
1126 dp
<< "[scop-detection-fail] "
1127 << "Gimple stmt not handled in Graphite:\n";
1128 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1133 /* Returns the number of pbbs that are in loops contained in SCOP. */
1136 scop_detection::nb_pbbs_in_loops (scop_p scop
)
1142 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1143 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), scop
->scop_info
->region
))
1149 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
1150 Otherwise returns -1. */
1153 parameter_index_in_region_1 (tree name
, sese_info_p region
)
1158 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1160 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
1167 /* When the parameter NAME is in REGION, returns its index in
1168 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
1169 and returns the index of NAME. */
1172 parameter_index_in_region (tree name
, sese_info_p region
)
1176 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1178 /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
1179 if (TREE_CODE (TREE_TYPE (name
)) != INTEGER_TYPE
)
1182 if (!invariant_in_sese_p_rec (name
, region
->region
, NULL
))
1185 i
= parameter_index_in_region_1 (name
, region
);
1189 i
= region
->params
.length ();
1190 region
->params
.safe_push (name
);
1194 /* In the context of sese S, scan the expression E and translate it to
1195 a linear expression C. When parsing a symbolic multiplication, K
1196 represents the constant multiplier of an expression containing
1200 scan_tree_for_params (sese_info_p s
, tree e
)
1202 if (e
== chrec_dont_know
)
1205 switch (TREE_CODE (e
))
1207 case POLYNOMIAL_CHREC
:
1208 scan_tree_for_params (s
, CHREC_LEFT (e
));
1212 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1213 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1215 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1219 case POINTER_PLUS_EXPR
:
1221 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1222 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1228 case NON_LVALUE_EXPR
:
1229 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1233 parameter_index_in_region (e
, s
);
1249 /* Find parameters with respect to REGION in BB. We are looking in memory
1250 access functions, conditions and loop bounds. */
1253 find_params_in_bb (sese_info_p region
, gimple_poly_bb_p gbb
)
1255 /* Find parameters in the access functions of data references. */
1257 data_reference_p dr
;
1258 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
1259 for (unsigned j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
1260 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
1262 /* Find parameters in conditional statements. */
1264 loop_p loop
= GBB_BB (gbb
)->loop_father
;
1265 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1267 tree lhs
= scalar_evolution_in_region (region
->region
, loop
,
1268 gimple_cond_lhs (stmt
));
1269 tree rhs
= scalar_evolution_in_region (region
->region
, loop
,
1270 gimple_cond_rhs (stmt
));
1272 scan_tree_for_params (region
, lhs
);
1273 scan_tree_for_params (region
, rhs
);
1277 /* Record the parameters used in the SCOP BBs. A variable is a parameter
1278 in a scop if it does not vary during the execution of that scop. */
1281 find_scop_parameters (scop_p scop
)
1284 sese_info_p region
= scop
->scop_info
;
1286 /* Parameters used in loop bounds are processed during gather_bbs. */
1288 /* Find the parameters used in data accesses. */
1290 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1291 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1293 int nbp
= sese_nb_params (region
);
1294 scop_set_nb_params (scop
, nbp
);
1298 add_write (vec
<tree
> *writes
, tree def
)
1300 writes
->safe_push (def
);
1301 DEBUG_PRINT (dp
<< "Adding scalar write: ";
1302 print_generic_expr (dump_file
, def
);
1303 dp
<< "\nFrom stmt: ";
1304 print_gimple_stmt (dump_file
,
1305 SSA_NAME_DEF_STMT (def
), 0));
1309 add_read (vec
<scalar_use
> *reads
, tree use
, gimple
*use_stmt
)
1311 DEBUG_PRINT (dp
<< "Adding scalar read: ";
1312 print_generic_expr (dump_file
, use
);
1313 dp
<< "\nFrom stmt: ";
1314 print_gimple_stmt (dump_file
, use_stmt
, 0));
1315 reads
->safe_push (std::make_pair (use_stmt
, use
));
1319 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1322 build_cross_bb_scalars_def (scop_p scop
, tree def
, basic_block def_bb
,
1325 if (!is_gimple_reg (def
))
1328 bool scev_analyzable
= scev_analyzable_p (def
, scop
->scop_info
->region
);
1331 imm_use_iterator imm_iter
;
1332 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1333 /* Do not gather scalar variables that can be analyzed by SCEV as they can
1334 be generated out of the induction variables. */
1335 if ((! scev_analyzable
1336 /* But gather SESE liveouts as we otherwise fail to rewrite their
1338 || ! bb_in_sese_p (gimple_bb (use_stmt
), scop
->scop_info
->region
))
1339 && (def_bb
!= gimple_bb (use_stmt
) && !is_gimple_debug (use_stmt
)))
1341 add_write (writes
, def
);
1342 /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
1343 before all the uses have been visited. */
1344 BREAK_FROM_IMM_USE_STMT (imm_iter
);
1348 /* Record USE if it is defined in other bbs different than USE_STMT
1352 build_cross_bb_scalars_use (scop_p scop
, tree use
, gimple
*use_stmt
,
1353 vec
<scalar_use
> *reads
)
1355 if (!is_gimple_reg (use
))
1358 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1359 generated out of the induction variables. */
1360 if (scev_analyzable_p (use
, scop
->scop_info
->region
))
1363 gimple
*def_stmt
= SSA_NAME_DEF_STMT (use
);
1364 if (gimple_bb (def_stmt
) != gimple_bb (use_stmt
))
1365 add_read (reads
, use
, use_stmt
);
1368 /* Generates a polyhedral black box only if the bb contains interesting
1371 static gimple_poly_bb_p
1372 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
1374 vec
<data_reference_p
> drs
= vNULL
;
1375 vec
<tree
> writes
= vNULL
;
1376 vec
<scalar_use
> reads
= vNULL
;
1378 sese_l region
= scop
->scop_info
->region
;
1380 loop_p loop
= bb
->loop_father
;
1381 if (!loop_in_sese_p (loop
, region
))
1384 nest
= outermost_loop_in_sese (region
, bb
);
1386 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1389 gimple
*stmt
= gsi_stmt (gsi
);
1390 if (is_gimple_debug (stmt
))
1393 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1395 tree def
= gimple_get_lhs (stmt
);
1397 build_cross_bb_scalars_def (scop
, def
, gimple_bb (stmt
), &writes
);
1401 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
1402 build_cross_bb_scalars_use (scop
, use
, stmt
, &reads
);
1405 /* Handle defs and uses in PHIs. Those need special treatment given
1406 that we have to present ISL with sth that looks like we've rewritten
1407 the IL out-of-SSA. */
1408 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1411 gphi
*phi
= psi
.phi ();
1412 tree res
= gimple_phi_result (phi
);
1413 if (virtual_operand_p (res
)
1414 || scev_analyzable_p (res
, scop
->scop_info
->region
))
1416 /* To simulate out-of-SSA the block containing the PHI node has
1417 reads of the PHI destination. And to preserve SSA dependences
1418 we also write to it (the out-of-SSA decl and the SSA result
1419 are coalesced for dependence purposes which is good enough). */
1420 add_read (&reads
, res
, phi
);
1421 add_write (&writes
, res
);
1423 basic_block bb_for_succs
= bb
;
1424 if (bb_for_succs
== bb_for_succs
->loop_father
->latch
1425 && bb_in_sese_p (bb_for_succs
, scop
->scop_info
->region
)
1426 && sese_trivially_empty_bb_p (bb_for_succs
))
1427 bb_for_succs
= NULL
;
1428 while (bb_for_succs
)
1430 basic_block latch
= NULL
;
1433 FOR_EACH_EDGE (e
, ei
, bb_for_succs
->succs
)
1435 for (gphi_iterator psi
= gsi_start_phis (e
->dest
); !gsi_end_p (psi
);
1438 gphi
*phi
= psi
.phi ();
1439 tree res
= gimple_phi_result (phi
);
1440 if (virtual_operand_p (res
))
1442 /* To simulate out-of-SSA the predecessor of edges into PHI nodes
1443 has a copy from the PHI argument to the PHI destination. */
1444 if (! scev_analyzable_p (res
, scop
->scop_info
->region
))
1445 add_write (&writes
, res
);
1446 tree use
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
1447 if (TREE_CODE (use
) == SSA_NAME
1448 && ! SSA_NAME_IS_DEFAULT_DEF (use
)
1449 && gimple_bb (SSA_NAME_DEF_STMT (use
)) != bb_for_succs
1450 && ! scev_analyzable_p (use
, scop
->scop_info
->region
))
1451 add_read (&reads
, use
, phi
);
1453 if (e
->dest
== bb_for_succs
->loop_father
->latch
1454 && bb_in_sese_p (e
->dest
, scop
->scop_info
->region
)
1455 && sese_trivially_empty_bb_p (e
->dest
))
1458 /* Handle empty latch block PHIs here, otherwise we confuse ISL
1459 with extra conditional code where it then peels off the last
1460 iteration just because of that. It would be simplest if we
1461 just didn't force simple latches (thus remove the forwarder). */
1462 bb_for_succs
= latch
;
1465 /* For the region exit block add reads for all live-out vars. */
1466 if (bb
== scop
->scop_info
->region
.exit
->src
)
1468 sese_build_liveouts (scop
->scop_info
);
1471 EXECUTE_IF_SET_IN_BITMAP (scop
->scop_info
->liveout
, 0, i
, bi
)
1473 tree use
= ssa_name (i
);
1474 add_read (&reads
, use
, NULL
);
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 /* For our out-of-SSA we need a block on s->entry, similar to how
1704 we include the LCSSA block in the region. */
1705 s
->entry
= single_pred_edge (split_edge (s
->entry
));
1707 scop_p scop
= new_scop (s
->entry
, s
->exit
);
1709 /* Record all basic blocks and their conditions in REGION. */
1710 gather_bbs (CDI_DOMINATORS
, scop
, bb_to_rpo
).walk (s
->entry
->dest
);
1712 /* domwalk does not fulfil our code-generations constraints on the
1713 order of pbb which is to produce sth like execution order, delaying
1714 exection of loop exit edges. So compute such order and sort after
1716 order
.create (last_basic_block_for_fn (cfun
));
1717 order
.quick_grow (last_basic_block_for_fn (cfun
));
1718 unsigned dfs_num
= 0;
1719 get_order (scop
, s
->entry
->dest
, &order
, &dfs_num
);
1720 scop
->pbbs
.qsort (cmp_pbbs
);
1723 if (! build_alias_set (scop
))
1725 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot handle dependences\n");
1730 /* Do not optimize a scop containing only PBBs that do not belong
1732 if (sb
.nb_pbbs_in_loops (scop
) == 0)
1734 DEBUG_PRINT (dp
<< "[scop-detection-fail] no data references.\n");
1739 unsigned max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
1741 && scop
->drs
.length () >= max_arrays
)
1743 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many data references: "
1744 << scop
->drs
.length ()
1745 << " is larger than --param graphite-max-arrays-per-scop="
1746 << max_arrays
<< ".\n");
1751 find_scop_parameters (scop
);
1752 graphite_dim_t max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
1754 && scop_nb_params (scop
) > max_dim
)
1756 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many parameters: "
1757 << scop_nb_params (scop
)
1758 << " larger than --param graphite-max-nb-scop-params="
1759 << max_dim
<< ".\n");
1764 scops
->safe_push (scop
);
1768 DEBUG_PRINT (dp
<< "number of SCoPs: " << (scops
? scops
->length () : 0););
1771 #endif /* HAVE_isl */