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 (sese_l scop
, 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 (sese_l scop
, tree scev
)
939 if (chrec_contains_undetermined (scev
))
942 switch (TREE_CODE (scev
))
947 case NON_LVALUE_EXPR
:
948 return graphite_can_represent_scev (scop
, TREE_OPERAND (scev
, 0));
951 case POINTER_PLUS_EXPR
:
953 return graphite_can_represent_scev (scop
, TREE_OPERAND (scev
, 0))
954 && graphite_can_represent_scev (scop
, 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 (scop
, TREE_OPERAND (scev
, 0))
963 && graphite_can_represent_scev (scop
, 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 gcc_assert (loop_in_sese_p (get_loop (cfun
,
971 CHREC_VARIABLE (scev
)), scop
));
972 if (!evolution_function_right_is_integer_cst (scev
)
973 || !graphite_can_represent_init (scev
))
975 return graphite_can_represent_scev (scop
, CHREC_LEFT (scev
));
981 /* Only affine functions can be represented. */
982 if (tree_contains_chrecs (scev
, NULL
) || !scev_is_linear_expression (scev
))
988 /* Return true when EXPR can be represented in the polyhedral model.
990 This means an expression can be represented, if it is linear with respect to
991 the loops and the strides are non parametric. LOOP is the place where the
992 expr will be evaluated. SCOP defines the region we analyse. */
995 scop_detection::graphite_can_represent_expr (sese_l scop
, loop_p loop
,
998 tree scev
= scalar_evolution_in_region (scop
, loop
, expr
);
999 return graphite_can_represent_scev (scop
, scev
);
1002 /* Return true if the data references of STMT can be represented by Graphite.
1003 We try to analyze the data references in a loop contained in the SCOP. */
1006 scop_detection::stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
)
1008 edge nest
= scop
.entry
;;
1009 loop_p loop
= loop_containing_stmt (stmt
);
1010 if (!loop_in_sese_p (loop
, scop
))
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 (scop
, 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 || ! INTEGRAL_TYPE_P (TREE_TYPE (op
)))
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 /* Assigns the parameter NAME an index in REGION. */
1152 assign_parameter_index_in_region (tree name
, sese_info_p region
)
1154 gcc_assert (TREE_CODE (name
) == SSA_NAME
1155 && INTEGRAL_TYPE_P (TREE_TYPE (name
))
1156 && ! defined_in_sese_p (name
, region
->region
));
1160 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
1164 i
= region
->params
.length ();
1165 region
->params
.safe_push (name
);
1168 /* In the context of sese S, scan the expression E and translate it to
1169 a linear expression C. When parsing a symbolic multiplication, K
1170 represents the constant multiplier of an expression containing
1174 scan_tree_for_params (sese_info_p s
, tree e
)
1176 if (e
== chrec_dont_know
)
1179 switch (TREE_CODE (e
))
1181 case POLYNOMIAL_CHREC
:
1182 scan_tree_for_params (s
, CHREC_LEFT (e
));
1186 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1187 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1189 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1193 case POINTER_PLUS_EXPR
:
1195 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1196 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1202 case NON_LVALUE_EXPR
:
1203 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1207 assign_parameter_index_in_region (e
, s
);
1223 /* Find parameters with respect to REGION in BB. We are looking in memory
1224 access functions, conditions and loop bounds. */
1227 find_params_in_bb (sese_info_p region
, gimple_poly_bb_p gbb
)
1229 /* Find parameters in the access functions of data references. */
1231 data_reference_p dr
;
1232 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
1233 for (unsigned j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
1234 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
1236 /* Find parameters in conditional statements. */
1238 loop_p loop
= GBB_BB (gbb
)->loop_father
;
1239 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1241 tree lhs
= scalar_evolution_in_region (region
->region
, loop
,
1242 gimple_cond_lhs (stmt
));
1243 tree rhs
= scalar_evolution_in_region (region
->region
, loop
,
1244 gimple_cond_rhs (stmt
));
1246 scan_tree_for_params (region
, lhs
);
1247 scan_tree_for_params (region
, rhs
);
1251 /* Record the parameters used in the SCOP BBs. A variable is a parameter
1252 in a scop if it does not vary during the execution of that scop. */
1255 find_scop_parameters (scop_p scop
)
1258 sese_info_p region
= scop
->scop_info
;
1260 /* Parameters used in loop bounds are processed during gather_bbs. */
1262 /* Find the parameters used in data accesses. */
1264 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1265 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1267 int nbp
= sese_nb_params (region
);
1268 scop_set_nb_params (scop
, nbp
);
1272 add_write (vec
<tree
> *writes
, tree def
)
1274 writes
->safe_push (def
);
1275 DEBUG_PRINT (dp
<< "Adding scalar write: ";
1276 print_generic_expr (dump_file
, def
);
1277 dp
<< "\nFrom stmt: ";
1278 print_gimple_stmt (dump_file
,
1279 SSA_NAME_DEF_STMT (def
), 0));
1283 add_read (vec
<scalar_use
> *reads
, tree use
, gimple
*use_stmt
)
1285 DEBUG_PRINT (dp
<< "Adding scalar read: ";
1286 print_generic_expr (dump_file
, use
);
1287 dp
<< "\nFrom stmt: ";
1288 print_gimple_stmt (dump_file
, use_stmt
, 0));
1289 reads
->safe_push (std::make_pair (use_stmt
, use
));
1293 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1296 build_cross_bb_scalars_def (scop_p scop
, tree def
, basic_block def_bb
,
1299 if (!is_gimple_reg (def
))
1302 bool scev_analyzable
= scev_analyzable_p (def
, scop
->scop_info
->region
);
1305 imm_use_iterator imm_iter
;
1306 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1307 /* Do not gather scalar variables that can be analyzed by SCEV as they can
1308 be generated out of the induction variables. */
1309 if ((! scev_analyzable
1310 /* But gather SESE liveouts as we otherwise fail to rewrite their
1312 || ! bb_in_sese_p (gimple_bb (use_stmt
), scop
->scop_info
->region
))
1313 && (def_bb
!= gimple_bb (use_stmt
) && !is_gimple_debug (use_stmt
)))
1315 add_write (writes
, def
);
1316 /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
1317 before all the uses have been visited. */
1318 BREAK_FROM_IMM_USE_STMT (imm_iter
);
1322 /* Record USE if it is defined in other bbs different than USE_STMT
1326 build_cross_bb_scalars_use (scop_p scop
, tree use
, gimple
*use_stmt
,
1327 vec
<scalar_use
> *reads
)
1329 if (!is_gimple_reg (use
))
1332 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1333 generated out of the induction variables. */
1334 if (scev_analyzable_p (use
, scop
->scop_info
->region
))
1337 gimple
*def_stmt
= SSA_NAME_DEF_STMT (use
);
1338 if (gimple_bb (def_stmt
) != gimple_bb (use_stmt
))
1339 add_read (reads
, use
, use_stmt
);
1342 /* Generates a polyhedral black box only if the bb contains interesting
1345 static gimple_poly_bb_p
1346 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
1348 vec
<data_reference_p
> drs
= vNULL
;
1349 vec
<tree
> writes
= vNULL
;
1350 vec
<scalar_use
> reads
= vNULL
;
1352 sese_l region
= scop
->scop_info
->region
;
1353 edge nest
= region
.entry
;
1354 loop_p loop
= bb
->loop_father
;
1355 if (!loop_in_sese_p (loop
, region
))
1358 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1361 gimple
*stmt
= gsi_stmt (gsi
);
1362 if (is_gimple_debug (stmt
))
1365 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1367 tree def
= gimple_get_lhs (stmt
);
1369 build_cross_bb_scalars_def (scop
, def
, gimple_bb (stmt
), &writes
);
1373 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
1374 build_cross_bb_scalars_use (scop
, use
, stmt
, &reads
);
1377 /* Handle defs and uses in PHIs. Those need special treatment given
1378 that we have to present ISL with sth that looks like we've rewritten
1379 the IL out-of-SSA. */
1380 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1383 gphi
*phi
= psi
.phi ();
1384 tree res
= gimple_phi_result (phi
);
1385 if (virtual_operand_p (res
)
1386 || scev_analyzable_p (res
, scop
->scop_info
->region
))
1388 /* To simulate out-of-SSA the block containing the PHI node has
1389 reads of the PHI destination. And to preserve SSA dependences
1390 we also write to it (the out-of-SSA decl and the SSA result
1391 are coalesced for dependence purposes which is good enough). */
1392 add_read (&reads
, res
, phi
);
1393 add_write (&writes
, res
);
1395 basic_block bb_for_succs
= bb
;
1396 if (bb_for_succs
== bb_for_succs
->loop_father
->latch
1397 && bb_in_sese_p (bb_for_succs
, scop
->scop_info
->region
)
1398 && sese_trivially_empty_bb_p (bb_for_succs
))
1399 bb_for_succs
= NULL
;
1400 while (bb_for_succs
)
1402 basic_block latch
= NULL
;
1405 FOR_EACH_EDGE (e
, ei
, bb_for_succs
->succs
)
1407 for (gphi_iterator psi
= gsi_start_phis (e
->dest
); !gsi_end_p (psi
);
1410 gphi
*phi
= psi
.phi ();
1411 tree res
= gimple_phi_result (phi
);
1412 if (virtual_operand_p (res
))
1414 /* To simulate out-of-SSA the predecessor of edges into PHI nodes
1415 has a copy from the PHI argument to the PHI destination. */
1416 if (! scev_analyzable_p (res
, scop
->scop_info
->region
))
1417 add_write (&writes
, res
);
1418 tree use
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
1419 if (TREE_CODE (use
) == SSA_NAME
1420 && ! SSA_NAME_IS_DEFAULT_DEF (use
)
1421 && gimple_bb (SSA_NAME_DEF_STMT (use
)) != bb_for_succs
1422 && ! scev_analyzable_p (use
, scop
->scop_info
->region
))
1423 add_read (&reads
, use
, phi
);
1425 if (e
->dest
== bb_for_succs
->loop_father
->latch
1426 && bb_in_sese_p (e
->dest
, scop
->scop_info
->region
)
1427 && sese_trivially_empty_bb_p (e
->dest
))
1430 /* Handle empty latch block PHIs here, otherwise we confuse ISL
1431 with extra conditional code where it then peels off the last
1432 iteration just because of that. It would be simplest if we
1433 just didn't force simple latches (thus remove the forwarder). */
1434 bb_for_succs
= latch
;
1437 /* For the region exit block add reads for all live-out vars. */
1438 if (bb
== scop
->scop_info
->region
.exit
->src
)
1440 sese_build_liveouts (scop
->scop_info
);
1443 EXECUTE_IF_SET_IN_BITMAP (scop
->scop_info
->liveout
, 0, i
, bi
)
1445 tree use
= ssa_name (i
);
1446 add_read (&reads
, use
, NULL
);
1450 if (drs
.is_empty () && writes
.is_empty () && reads
.is_empty ())
1453 return new_gimple_poly_bb (bb
, drs
, reads
, writes
);
1456 /* Compute alias-sets for all data references in DRS. */
1459 build_alias_set (scop_p scop
)
1461 int num_vertices
= scop
->drs
.length ();
1462 struct graph
*g
= new_graph (num_vertices
);
1467 FOR_EACH_VEC_ELT (scop
->drs
, i
, dr1
)
1468 for (j
= i
+1; scop
->drs
.iterate (j
, &dr2
); j
++)
1469 if (dr_may_alias_p (dr1
->dr
, dr2
->dr
, true))
1471 /* Dependences in the same alias set need to be handled
1472 by just looking at DR_ACCESS_FNs. */
1473 if (DR_NUM_DIMENSIONS (dr1
->dr
) == 0
1474 || DR_NUM_DIMENSIONS (dr1
->dr
) != DR_NUM_DIMENSIONS (dr2
->dr
)
1475 || ! operand_equal_p (DR_BASE_OBJECT (dr1
->dr
),
1476 DR_BASE_OBJECT (dr2
->dr
),
1478 || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1
->dr
)),
1479 TREE_TYPE (DR_BASE_OBJECT (dr2
->dr
))))
1488 all_vertices
= XNEWVEC (int, num_vertices
);
1489 for (i
= 0; i
< num_vertices
; i
++)
1490 all_vertices
[i
] = i
;
1493 = graphds_dfs (g
, all_vertices
, num_vertices
, NULL
, true, NULL
) + 1;
1494 free (all_vertices
);
1496 for (i
= 0; i
< g
->n_vertices
; i
++)
1497 scop
->drs
[i
].alias_set
= g
->vertices
[i
].component
+ 1;
1503 /* Gather BBs and conditions for a SCOP. */
1504 class gather_bbs
: public dom_walker
1507 gather_bbs (cdi_direction
, scop_p
, int *);
1509 virtual edge
before_dom_children (basic_block
);
1510 virtual void after_dom_children (basic_block
);
1513 auto_vec
<gimple
*, 3> conditions
, cases
;
1517 gather_bbs::gather_bbs (cdi_direction direction
, scop_p scop
, int *bb_to_rpo
)
1518 : dom_walker (direction
, false, bb_to_rpo
), scop (scop
)
1522 /* Call-back for dom_walk executed before visiting the dominated
1526 gather_bbs::before_dom_children (basic_block bb
)
1528 sese_info_p region
= scop
->scop_info
;
1529 if (!bb_in_sese_p (bb
, region
->region
))
1530 return dom_walker::STOP
;
1532 /* For loops fully contained in the region record parameters in the
1534 loop_p loop
= bb
->loop_father
;
1535 if (loop
->header
== bb
1536 && loop_in_sese_p (loop
, region
->region
))
1538 tree nb_iters
= number_of_latch_executions (loop
);
1539 if (chrec_contains_symbols (nb_iters
))
1541 nb_iters
= scalar_evolution_in_region (region
->region
,
1543 scan_tree_for_params (region
, nb_iters
);
1547 gcond
*stmt
= single_pred_cond_non_loop_exit (bb
);
1551 edge e
= single_pred_edge (bb
);
1553 conditions
.safe_push (stmt
);
1555 if (e
->flags
& EDGE_TRUE_VALUE
)
1556 cases
.safe_push (stmt
);
1558 cases
.safe_push (NULL
);
1561 scop
->scop_info
->bbs
.safe_push (bb
);
1563 gimple_poly_bb_p gbb
= try_generate_gimple_bb (scop
, bb
);
1567 GBB_CONDITIONS (gbb
) = conditions
.copy ();
1568 GBB_CONDITION_CASES (gbb
) = cases
.copy ();
1570 poly_bb_p pbb
= new_poly_bb (scop
, gbb
);
1571 scop
->pbbs
.safe_push (pbb
);
1574 data_reference_p dr
;
1575 FOR_EACH_VEC_ELT (gbb
->data_refs
, i
, dr
)
1577 DEBUG_PRINT (dp
<< "Adding memory ";
1582 print_generic_expr (dump_file
, dr
->ref
);
1583 dp
<< "\nFrom stmt: ";
1584 print_gimple_stmt (dump_file
, dr
->stmt
, 0));
1586 scop
->drs
.safe_push (dr_info (dr
, pbb
));
1592 /* Call-back for dom_walk executed after visiting the dominated
1596 gather_bbs::after_dom_children (basic_block bb
)
1598 if (!bb_in_sese_p (bb
, scop
->scop_info
->region
))
1601 if (single_pred_cond_non_loop_exit (bb
))
1609 /* Compute sth like an execution order, dominator order with first executing
1610 edges that stay inside the current loop, delaying processing exit edges. */
1612 static vec
<unsigned> order
;
1615 get_order (scop_p scop
, basic_block bb
, vec
<unsigned> *order
, unsigned *dfs_num
)
1617 if (! bb_in_sese_p (bb
, scop
->scop_info
->region
))
1620 (*order
)[bb
->index
] = (*dfs_num
)++;
1621 for (basic_block son
= first_dom_son (CDI_DOMINATORS
, bb
);
1623 son
= next_dom_son (CDI_DOMINATORS
, son
))
1624 if (flow_bb_inside_loop_p (bb
->loop_father
, son
))
1625 get_order (scop
, son
, order
, dfs_num
);
1626 for (basic_block son
= first_dom_son (CDI_DOMINATORS
, bb
);
1628 son
= next_dom_son (CDI_DOMINATORS
, son
))
1629 if (! flow_bb_inside_loop_p (bb
->loop_father
, son
))
1630 get_order (scop
, son
, order
, dfs_num
);
1633 /* Helper for qsort, sorting after order above. */
1636 cmp_pbbs (const void *pa
, const void *pb
)
1638 poly_bb_p bb1
= *((const poly_bb_p
*)pa
);
1639 poly_bb_p bb2
= *((const poly_bb_p
*)pb
);
1640 if (order
[bb1
->black_box
->bb
->index
] < order
[bb2
->black_box
->bb
->index
])
1642 else if (order
[bb1
->black_box
->bb
->index
] > order
[bb2
->black_box
->bb
->index
])
1648 /* Find Static Control Parts (SCoP) in the current function and pushes
1652 build_scops (vec
<scop_p
> *scops
)
1655 dp
.set_dump_file (dump_file
);
1658 sb
.build_scop_depth (current_loops
->tree_root
);
1660 /* Now create scops from the lightweight SESEs. */
1661 vec
<sese_l
> scops_l
= sb
.get_scops ();
1663 /* Domwalk needs a bb to RPO mapping. Compute it once here. */
1664 int *postorder
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
1665 int postorder_num
= pre_and_rev_post_order_compute (NULL
, postorder
, true);
1666 int *bb_to_rpo
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1667 for (int i
= 0; i
< postorder_num
; ++i
)
1668 bb_to_rpo
[postorder
[i
]] = i
;
1673 FOR_EACH_VEC_ELT (scops_l
, i
, s
)
1675 scop_p scop
= new_scop (s
->entry
, s
->exit
);
1677 /* Record all basic blocks and their conditions in REGION. */
1678 gather_bbs (CDI_DOMINATORS
, scop
, bb_to_rpo
).walk (s
->entry
->dest
);
1680 /* domwalk does not fulfil our code-generations constraints on the
1681 order of pbb which is to produce sth like execution order, delaying
1682 exection of loop exit edges. So compute such order and sort after
1684 order
.create (last_basic_block_for_fn (cfun
));
1685 order
.quick_grow (last_basic_block_for_fn (cfun
));
1686 unsigned dfs_num
= 0;
1687 get_order (scop
, s
->entry
->dest
, &order
, &dfs_num
);
1688 scop
->pbbs
.qsort (cmp_pbbs
);
1691 if (! build_alias_set (scop
))
1693 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot handle dependences\n");
1698 /* Do not optimize a scop containing only PBBs that do not belong
1700 if (sb
.nb_pbbs_in_loops (scop
) == 0)
1702 DEBUG_PRINT (dp
<< "[scop-detection-fail] no data references.\n");
1707 unsigned max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
1709 && scop
->drs
.length () >= max_arrays
)
1711 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many data references: "
1712 << scop
->drs
.length ()
1713 << " is larger than --param graphite-max-arrays-per-scop="
1714 << max_arrays
<< ".\n");
1719 find_scop_parameters (scop
);
1720 graphite_dim_t max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
1722 && scop_nb_params (scop
) > max_dim
)
1724 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many parameters: "
1725 << scop_nb_params (scop
)
1726 << " larger than --param graphite-max-nb-scop-params="
1727 << max_dim
<< ".\n");
1732 scops
->safe_push (scop
);
1736 DEBUG_PRINT (dp
<< "number of SCoPs: " << (scops
? scops
->length () : 0););
1739 #endif /* HAVE_isl */