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 /* Can all ivs be represented by a signed integer?
258 As isl might generate negative values in its expressions, signed loop ivs
259 are required in the backend. */
262 loop_ivs_can_be_represented (loop_p loop
)
264 unsigned type_long_long
= TYPE_PRECISION (long_long_integer_type_node
);
265 for (gphi_iterator psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
);
268 gphi
*phi
= psi
.phi ();
269 tree res
= PHI_RESULT (phi
);
270 tree type
= TREE_TYPE (res
);
272 if (TYPE_UNSIGNED (type
) && TYPE_PRECISION (type
) >= type_long_long
)
279 /* Returns a COND_EXPR statement when BB has a single predecessor, the
280 edge between BB and its predecessor is not a loop exit edge, and
281 the last statement of the single predecessor is a COND_EXPR. */
284 single_pred_cond_non_loop_exit (basic_block bb
)
286 if (single_pred_p (bb
))
288 edge e
= single_pred_edge (bb
);
289 basic_block pred
= e
->src
;
292 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
295 stmt
= last_stmt (pred
);
297 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
298 return as_a
<gcond
*> (stmt
);
307 /* Build the maximal scop containing LOOPs and add it to SCOPS. */
312 scop_detection () : scops (vNULL
) {}
319 /* A marker for invalid sese_l. */
320 static sese_l invalid_sese
;
322 /* Return the SCOPS in this SCOP_DETECTION. */
330 /* Return an sese_l around the LOOP. */
332 sese_l
get_sese (loop_p loop
);
334 /* Return the closest dominator with a single entry edge. In case of a
335 back-loop the back-edge is not counted. */
337 static edge
get_nearest_dom_with_single_entry (basic_block dom
);
339 /* Return the closest post-dominator with a single exit edge. In case of a
340 back-loop the back-edge is not counted. */
342 static edge
get_nearest_pdom_with_single_exit (basic_block dom
);
344 /* Merge scops at same loop depth and returns the new sese.
345 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
347 sese_l
merge_sese (sese_l first
, sese_l second
) const;
349 /* Build scop outer->inner if possible. */
351 void build_scop_depth (loop_p loop
);
353 /* Return true when BEGIN is the preheader edge of a loop with a single exit
356 static bool region_has_one_loop (sese_l s
);
358 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
360 void add_scop (sese_l s
);
362 /* Returns true if S1 subsumes/surrounds S2. */
363 static bool subsumes (sese_l s1
, sese_l s2
);
365 /* Remove a SCoP which is subsumed by S1. */
366 void remove_subscops (sese_l s1
);
368 /* Returns true if S1 intersects with S2. Since we already know that S1 does
369 not subsume S2 or vice-versa, we only check for entry bbs. */
371 static bool intersects (sese_l s1
, sese_l s2
);
373 /* Remove one of the scops when it intersects with any other. */
375 void remove_intersecting_scops (sese_l s1
);
377 /* Return true when a statement in SCOP cannot be represented by Graphite. */
379 bool harmful_loop_in_region (sese_l scop
) const;
381 /* Return true only when STMT is simple enough for being handled by Graphite.
382 This depends on SCOP, as the parameters are initialized relatively to
383 this basic block, the linear functions are initialized based on the
384 outermost loop containing STMT inside the SCOP. BB is the place where we
385 try to evaluate the STMT. */
387 bool stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
388 basic_block bb
) const;
390 /* Something like "n * m" is not allowed. */
392 static bool graphite_can_represent_init (tree e
);
394 /* Return true when SCEV can be represented in the polyhedral model.
396 An expression can be represented, if it can be expressed as an
397 affine expression. For loops (i, j) and parameters (m, n) all
398 affine expressions are of the form:
400 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
402 1 i + 20 j + (-2) m + 25
404 Something like "i * n" or "n * m" is not allowed. */
406 static bool graphite_can_represent_scev (tree scev
);
408 /* Return true when EXPR can be represented in the polyhedral model.
410 This means an expression can be represented, if it is linear with respect
411 to the loops and the strides are non parametric. LOOP is the place where
412 the expr will be evaluated. SCOP defines the region we analyse. */
414 static bool graphite_can_represent_expr (sese_l scop
, loop_p loop
,
417 /* Return true if the data references of STMT can be represented by Graphite.
418 We try to analyze the data references in a loop contained in the SCOP. */
420 static bool stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
);
422 /* Remove the close phi node at GSI and replace its rhs with the rhs
425 static void remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
);
427 /* Returns true when Graphite can represent LOOP in SCOP.
428 FIXME: For the moment, graphite cannot be used on loops that iterate using
429 induction variables that wrap. */
431 static bool can_represent_loop (loop_p loop
, sese_l scop
);
433 /* Returns the number of pbbs that are in loops contained in SCOP. */
435 static int nb_pbbs_in_loops (scop_p scop
);
441 sese_l
scop_detection::invalid_sese (NULL
, NULL
);
443 /* Return an sese_l around the LOOP. */
446 scop_detection::get_sese (loop_p loop
)
451 edge scop_begin
= loop_preheader_edge (loop
);
452 edge scop_end
= single_exit (loop
);
453 if (!scop_end
|| (scop_end
->flags
& EDGE_COMPLEX
))
455 /* Include the BB with the loop-closed SSA PHI nodes.
456 canonicalize_loop_closed_ssa makes sure that is in proper shape. */
457 if (! single_pred_p (scop_end
->dest
)
458 || ! single_succ_p (scop_end
->dest
)
459 || ! sese_trivially_empty_bb_p (scop_end
->dest
))
461 scop_end
= single_succ_edge (scop_end
->dest
);
463 return sese_l (scop_begin
, scop_end
);
466 /* Return the closest dominator with a single entry edge. */
469 scop_detection::get_nearest_dom_with_single_entry (basic_block dom
)
474 /* If any of the dominators has two predecessors but one of them is a back
475 edge, then that basic block also qualifies as a dominator with single
477 if (dom
->preds
->length () == 2)
479 /* If e1->src dominates e2->src then e1->src will also dominate dom. */
480 edge e1
= (*dom
->preds
)[0];
481 edge e2
= (*dom
->preds
)[1];
482 loop_p l
= dom
->loop_father
;
483 loop_p l1
= e1
->src
->loop_father
;
484 loop_p l2
= e2
->src
->loop_father
;
485 if (l
!= l1
&& l
== l2
486 && dominated_by_p (CDI_DOMINATORS
, e2
->src
, e1
->src
))
488 if (l
!= l2
&& l
== l1
489 && dominated_by_p (CDI_DOMINATORS
, e1
->src
, e2
->src
))
493 while (dom
->preds
->length () != 1)
495 if (dom
->preds
->length () < 1)
497 dom
= get_immediate_dominator (CDI_DOMINATORS
, dom
);
501 return (*dom
->preds
)[0];
504 /* Return the closest post-dominator with a single exit edge. In case of a
505 back-loop the back-edge is not counted. */
508 scop_detection::get_nearest_pdom_with_single_exit (basic_block pdom
)
513 /* If any of the post-dominators has two successors but one of them is a back
514 edge, then that basic block also qualifies as a post-dominator with single
516 if (pdom
->succs
->length () == 2)
518 /* If e1->dest post-dominates e2->dest then e1->dest will also
519 post-dominate pdom. */
520 edge e1
= (*pdom
->succs
)[0];
521 edge e2
= (*pdom
->succs
)[1];
522 loop_p l
= pdom
->loop_father
;
523 loop_p l1
= e1
->dest
->loop_father
;
524 loop_p l2
= e2
->dest
->loop_father
;
525 if (l
!= l1
&& l
== l2
526 && dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, e1
->dest
))
528 if (l
!= l2
&& l
== l1
529 && dominated_by_p (CDI_POST_DOMINATORS
, e1
->dest
, e2
->dest
))
533 while (pdom
->succs
->length () != 1)
535 if (pdom
->succs
->length () < 1)
537 pdom
= get_immediate_dominator (CDI_POST_DOMINATORS
, pdom
);
542 return (*pdom
->succs
)[0];
545 /* Merge scops at same loop depth and returns the new sese.
546 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
549 scop_detection::merge_sese (sese_l first
, sese_l second
) const
551 /* In the trivial case first/second may be NULL. */
557 DEBUG_PRINT (dp
<< "[scop-detection] try merging sese s1: ";
558 print_sese (dump_file
, first
);
559 dp
<< "[scop-detection] try merging sese s2: ";
560 print_sese (dump_file
, second
));
562 /* Assumption: Both the sese's should be at the same loop depth or one scop
563 should subsume the other like in case of nested loops. */
565 /* Find the common dominators for entry,
566 and common post-dominators for the exit. */
567 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
,
568 get_entry_bb (first
),
569 get_entry_bb (second
));
571 edge entry
= get_nearest_dom_with_single_entry (dom
);
573 if (!entry
|| (entry
->flags
& EDGE_IRREDUCIBLE_LOOP
))
576 basic_block pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
,
578 get_exit_bb (second
));
579 pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
, dom
, pdom
);
581 edge exit
= get_nearest_pdom_with_single_exit (pdom
);
583 if (!exit
|| (exit
->flags
& EDGE_IRREDUCIBLE_LOOP
))
586 sese_l
combined (entry
, exit
);
588 DEBUG_PRINT (dp
<< "[scop-detection] checking combined sese: ";
589 print_sese (dump_file
, combined
));
591 /* FIXME: We could iterate to find the dom which dominates pdom, and pdom
592 which post-dominates dom, until it stabilizes. Also, ENTRY->SRC and
593 EXIT->DEST should be in the same loop nest. */
594 if (!dominated_by_p (CDI_DOMINATORS
, pdom
, dom
)
595 || loop_depth (entry
->src
->loop_father
)
596 != loop_depth (exit
->dest
->loop_father
))
599 /* For now we just bail out when there is a loop exit in the region
600 that is not also the exit of the region. We could enlarge the
601 region to cover the loop that region exits to. See PR79977. */
602 if (loop_outer (entry
->src
->loop_father
))
604 vec
<edge
> exits
= get_loop_exit_edges (entry
->src
->loop_father
);
605 for (unsigned i
= 0; i
< exits
.length (); ++i
)
608 && bb_in_region (exits
[i
]->src
, entry
->dest
, exit
->src
))
610 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
618 /* For now we just want to bail out when exit does not post-dominate entry.
619 TODO: We might just add a basic_block at the exit to make exit
620 post-dominate entry (the entire region). */
621 if (!dominated_by_p (CDI_POST_DOMINATORS
, get_entry_bb (combined
),
622 get_exit_bb (combined
))
623 || !dominated_by_p (CDI_DOMINATORS
, get_exit_bb (combined
),
624 get_entry_bb (combined
)))
626 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
630 DEBUG_PRINT (dp
<< "[merged-sese] s1: "; print_sese (dump_file
, combined
));
635 /* Build scop outer->inner if possible. */
638 scop_detection::build_scop_depth (loop_p loop
)
640 sese_l s
= invalid_sese
;
644 sese_l next
= get_sese (loop
);
646 || harmful_loop_in_region (next
))
650 build_scop_depth (loop
);
657 sese_l combined
= merge_sese (s
, next
);
659 || harmful_loop_in_region (combined
))
673 /* Returns true when Graphite can represent LOOP in SCOP.
674 FIXME: For the moment, graphite cannot be used on loops that iterate using
675 induction variables that wrap. */
678 scop_detection::can_represent_loop (loop_p loop
, sese_l scop
)
681 struct tree_niter_desc niter_desc
;
683 return single_exit (loop
)
684 && !(loop_preheader_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
)
685 && number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
686 && niter_desc
.control
.no_overflow
687 && (niter
= number_of_latch_executions (loop
))
688 && !chrec_contains_undetermined (niter
)
689 && !chrec_contains_undetermined (scalar_evolution_in_region (scop
,
691 && graphite_can_represent_expr (scop
, loop
, niter
);
694 /* Return true when BEGIN is the preheader edge of a loop with a single exit
698 scop_detection::region_has_one_loop (sese_l s
)
700 edge begin
= s
.entry
;
702 /* Check for a single perfectly nested loop. */
703 if (begin
->dest
->loop_father
->inner
)
706 /* Otherwise, check whether we have adjacent loops. */
707 return (single_pred_p (end
->src
)
708 && begin
->dest
->loop_father
== single_pred (end
->src
)->loop_father
);
711 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
714 scop_detection::add_scop (sese_l s
)
718 /* Do not add scops with only one loop. */
719 if (region_has_one_loop (s
))
721 DEBUG_PRINT (dp
<< "[scop-detection-fail] Discarding one loop SCoP: ";
722 print_sese (dump_file
, s
));
726 if (get_exit_bb (s
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
728 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
729 << "Discarding SCoP exiting to return: ";
730 print_sese (dump_file
, s
));
734 /* Remove all the scops which are subsumed by s. */
737 /* Remove intersecting scops. FIXME: It will be a good idea to keep
738 the non-intersecting part of the scop already in the list. */
739 remove_intersecting_scops (s
);
742 DEBUG_PRINT (dp
<< "[scop-detection] Adding SCoP: "; print_sese (dump_file
, s
));
745 /* Return true when a statement in SCOP cannot be represented by Graphite. */
748 scop_detection::harmful_loop_in_region (sese_l scop
) const
750 basic_block exit_bb
= get_exit_bb (scop
);
751 basic_block entry_bb
= get_entry_bb (scop
);
753 DEBUG_PRINT (dp
<< "[checking-harmful-bbs] ";
754 print_sese (dump_file
, scop
));
755 gcc_assert (dominated_by_p (CDI_DOMINATORS
, exit_bb
, entry_bb
));
757 auto_vec
<basic_block
> worklist
;
760 worklist
.safe_push (entry_bb
);
761 while (! worklist
.is_empty ())
763 basic_block bb
= worklist
.pop ();
764 DEBUG_PRINT (dp
<< "Visiting bb_" << bb
->index
<< "\n");
766 /* The basic block should not be part of an irreducible loop. */
767 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
770 /* Check for unstructured control flow: CFG not generated by structured
772 if (bb
->succs
->length () > 1)
776 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
777 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb
, e
->dest
)
778 && !dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
782 /* Collect all loops in the current region. */
783 loop_p loop
= bb
->loop_father
;
784 if (loop_in_sese_p (loop
, scop
))
785 bitmap_set_bit (loops
, loop
->num
);
787 /* Check for harmful statements in basic blocks part of the region. */
788 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
789 !gsi_end_p (gsi
); gsi_next (&gsi
))
790 if (!stmt_simple_for_scop_p (scop
, gsi_stmt (gsi
), bb
))
794 for (basic_block dom
= first_dom_son (CDI_DOMINATORS
, bb
);
796 dom
= next_dom_son (CDI_DOMINATORS
, dom
))
797 worklist
.safe_push (dom
);
800 /* Go through all loops and check that they are still valid in the combined
804 EXECUTE_IF_SET_IN_BITMAP (loops
, 0, j
, bi
)
806 loop_p loop
= (*current_loops
->larray
)[j
];
807 gcc_assert (loop
->num
== (int) j
);
809 /* Check if the loop nests are to be optimized for speed. */
811 && ! optimize_loop_for_speed_p (loop
))
813 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_"
814 << loop
->num
<< " is not on a hot path.\n");
818 if (! can_represent_loop (loop
, scop
))
820 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot represent loop_"
821 << loop
->num
<< "\n");
825 if (! loop_ivs_can_be_represented (loop
))
827 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
828 << "IV cannot be represented.\n");
832 /* Check if all loop nests have at least one data reference.
833 ??? This check is expensive and loops premature at this point.
834 If important to retain we can pre-compute this for all innermost
835 loops and reject those when we build a SESE region for a loop
836 during SESE discovery. */
838 && ! loop_nest_has_data_refs (loop
))
840 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
841 << "does not have any data reference.\n");
849 /* Returns true if S1 subsumes/surrounds S2. */
851 scop_detection::subsumes (sese_l s1
, sese_l s2
)
853 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
855 && dominated_by_p (CDI_POST_DOMINATORS
, s2
.exit
->dest
,
861 /* Remove a SCoP which is subsumed by S1. */
863 scop_detection::remove_subscops (sese_l s1
)
867 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
869 if (subsumes (s1
, *s2
))
871 DEBUG_PRINT (dp
<< "Removing sub-SCoP";
872 print_sese (dump_file
, *s2
));
873 scops
.unordered_remove (j
);
878 /* Returns true if S1 intersects with S2. Since we already know that S1 does
879 not subsume S2 or vice-versa, we only check for entry bbs. */
882 scop_detection::intersects (sese_l s1
, sese_l s2
)
884 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
886 && !dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
889 if ((s1
.exit
== s2
.entry
) || (s2
.exit
== s1
.entry
))
895 /* Remove one of the scops when it intersects with any other. */
898 scop_detection::remove_intersecting_scops (sese_l s1
)
902 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
904 if (intersects (s1
, *s2
))
906 DEBUG_PRINT (dp
<< "Removing intersecting SCoP";
907 print_sese (dump_file
, *s2
);
908 dp
<< "Intersects with:";
909 print_sese (dump_file
, s1
));
910 scops
.unordered_remove (j
);
915 /* Something like "n * m" is not allowed. */
918 scop_detection::graphite_can_represent_init (tree e
)
920 switch (TREE_CODE (e
))
922 case POLYNOMIAL_CHREC
:
923 return graphite_can_represent_init (CHREC_LEFT (e
))
924 && graphite_can_represent_init (CHREC_RIGHT (e
));
927 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
928 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
929 && tree_fits_shwi_p (TREE_OPERAND (e
, 1));
931 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
932 && tree_fits_shwi_p (TREE_OPERAND (e
, 0));
935 case POINTER_PLUS_EXPR
:
937 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
938 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
943 case NON_LVALUE_EXPR
:
944 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
953 /* Return true when SCEV can be represented in the polyhedral model.
955 An expression can be represented, if it can be expressed as an
956 affine expression. For loops (i, j) and parameters (m, n) all
957 affine expressions are of the form:
959 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
961 1 i + 20 j + (-2) m + 25
963 Something like "i * n" or "n * m" is not allowed. */
966 scop_detection::graphite_can_represent_scev (tree scev
)
968 if (chrec_contains_undetermined (scev
))
971 /* We disable the handling of pointer types, because it’s currently not
972 supported by Graphite with the isl AST generator. SSA_NAME nodes are
973 the only nodes, which are disabled in case they are pointers to object
974 types, but this can be changed. */
976 if (POINTER_TYPE_P (TREE_TYPE (scev
)) && TREE_CODE (scev
) == SSA_NAME
)
979 switch (TREE_CODE (scev
))
984 case NON_LVALUE_EXPR
:
985 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0));
988 case POINTER_PLUS_EXPR
:
990 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
991 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
994 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
995 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
996 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
997 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
998 && graphite_can_represent_init (scev
)
999 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1000 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1002 case POLYNOMIAL_CHREC
:
1003 /* Check for constant strides. With a non constant stride of
1004 'n' we would have a value of 'iv * n'. Also check that the
1005 initial value can represented: for example 'n * m' cannot be
1007 if (!evolution_function_right_is_integer_cst (scev
)
1008 || !graphite_can_represent_init (scev
))
1010 return graphite_can_represent_scev (CHREC_LEFT (scev
));
1016 /* Only affine functions can be represented. */
1017 if (tree_contains_chrecs (scev
, NULL
) || !scev_is_linear_expression (scev
))
1023 /* Return true when EXPR can be represented in the polyhedral model.
1025 This means an expression can be represented, if it is linear with respect to
1026 the loops and the strides are non parametric. LOOP is the place where the
1027 expr will be evaluated. SCOP defines the region we analyse. */
1030 scop_detection::graphite_can_represent_expr (sese_l scop
, loop_p loop
,
1033 tree scev
= scalar_evolution_in_region (scop
, loop
, expr
);
1034 return graphite_can_represent_scev (scev
);
1037 /* Return true if the data references of STMT can be represented by Graphite.
1038 We try to analyze the data references in a loop contained in the SCOP. */
1041 scop_detection::stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
)
1044 loop_p loop
= loop_containing_stmt (stmt
);
1045 if (!loop_in_sese_p (loop
, scop
))
1048 nest
= outermost_loop_in_sese (scop
, gimple_bb (stmt
));
1050 auto_vec
<data_reference_p
> drs
;
1051 if (! graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
))
1055 data_reference_p dr
;
1056 FOR_EACH_VEC_ELT (drs
, j
, dr
)
1058 for (unsigned i
= 0; i
< DR_NUM_DIMENSIONS (dr
); ++i
)
1059 if (! graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
)))
1066 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1067 Calls have side-effects, except those to const or pure
1071 stmt_has_side_effects (gimple
*stmt
)
1073 if (gimple_has_volatile_ops (stmt
)
1074 || (gimple_code (stmt
) == GIMPLE_CALL
1075 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
1076 || (gimple_code (stmt
) == GIMPLE_ASM
))
1078 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1079 << "Statement has side-effects:\n";
1080 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1086 /* Return true only when STMT is simple enough for being handled by Graphite.
1087 This depends on SCOP, as the parameters are initialized relatively to
1088 this basic block, the linear functions are initialized based on the outermost
1089 loop containing STMT inside the SCOP. BB is the place where we try to
1090 evaluate the STMT. */
1093 scop_detection::stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
1094 basic_block bb
) const
1098 if (is_gimple_debug (stmt
))
1101 if (stmt_has_side_effects (stmt
))
1104 if (!stmt_has_simple_data_refs_p (scop
, stmt
))
1106 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1107 << "Graphite cannot handle data-refs in stmt:\n";
1108 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
););
1112 switch (gimple_code (stmt
))
1119 /* We can handle all binary comparisons. Inequalities are
1120 also supported as they can be represented with union of
1122 enum tree_code code
= gimple_cond_code (stmt
);
1123 if (!(code
== LT_EXPR
1128 || code
== NE_EXPR
))
1130 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1131 << "Graphite cannot handle cond stmt:\n";
1132 print_gimple_stmt (dump_file
, stmt
, 0,
1133 TDF_VOPS
| TDF_MEMSYMS
));
1137 loop_p loop
= bb
->loop_father
;
1138 for (unsigned i
= 0; i
< 2; ++i
)
1140 tree op
= gimple_op (stmt
, i
);
1141 if (!graphite_can_represent_expr (scop
, loop
, op
)
1142 /* We can only constrain on integer type. */
1143 || (TREE_CODE (TREE_TYPE (op
)) != INTEGER_TYPE
))
1145 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1146 << "Graphite cannot represent stmt:\n";
1147 print_gimple_stmt (dump_file
, stmt
, 0,
1148 TDF_VOPS
| TDF_MEMSYMS
));
1161 /* These nodes cut a new scope. */
1163 dp
<< "[scop-detection-fail] "
1164 << "Gimple stmt not handled in Graphite:\n";
1165 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1170 /* Returns the number of pbbs that are in loops contained in SCOP. */
1173 scop_detection::nb_pbbs_in_loops (scop_p scop
)
1179 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1180 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), scop
->scop_info
->region
))
1186 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
1187 Otherwise returns -1. */
1190 parameter_index_in_region_1 (tree name
, sese_info_p region
)
1195 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1197 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
1204 /* When the parameter NAME is in REGION, returns its index in
1205 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
1206 and returns the index of NAME. */
1209 parameter_index_in_region (tree name
, sese_info_p region
)
1213 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1215 /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
1216 if (TREE_CODE (TREE_TYPE (name
)) != INTEGER_TYPE
)
1219 if (!invariant_in_sese_p_rec (name
, region
->region
, NULL
))
1222 i
= parameter_index_in_region_1 (name
, region
);
1226 i
= region
->params
.length ();
1227 region
->params
.safe_push (name
);
1231 /* In the context of sese S, scan the expression E and translate it to
1232 a linear expression C. When parsing a symbolic multiplication, K
1233 represents the constant multiplier of an expression containing
1237 scan_tree_for_params (sese_info_p s
, tree e
)
1239 if (e
== chrec_dont_know
)
1242 switch (TREE_CODE (e
))
1244 case POLYNOMIAL_CHREC
:
1245 scan_tree_for_params (s
, CHREC_LEFT (e
));
1249 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1250 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1252 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1256 case POINTER_PLUS_EXPR
:
1258 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1259 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1265 case NON_LVALUE_EXPR
:
1266 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1270 parameter_index_in_region (e
, s
);
1286 /* Find parameters with respect to REGION in BB. We are looking in memory
1287 access functions, conditions and loop bounds. */
1290 find_params_in_bb (sese_info_p region
, gimple_poly_bb_p gbb
)
1292 /* Find parameters in the access functions of data references. */
1294 data_reference_p dr
;
1295 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
1296 for (unsigned j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
1297 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
1299 /* Find parameters in conditional statements. */
1301 loop_p loop
= GBB_BB (gbb
)->loop_father
;
1302 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1304 tree lhs
= scalar_evolution_in_region (region
->region
, loop
,
1305 gimple_cond_lhs (stmt
));
1306 tree rhs
= scalar_evolution_in_region (region
->region
, loop
,
1307 gimple_cond_rhs (stmt
));
1309 scan_tree_for_params (region
, lhs
);
1310 scan_tree_for_params (region
, rhs
);
1314 /* Record the parameters used in the SCOP BBs. A variable is a parameter
1315 in a scop if it does not vary during the execution of that scop. */
1318 find_scop_parameters (scop_p scop
)
1321 sese_info_p region
= scop
->scop_info
;
1323 /* Parameters used in loop bounds are processed during gather_bbs. */
1325 /* Find the parameters used in data accesses. */
1327 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1328 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1330 int nbp
= sese_nb_params (region
);
1331 scop_set_nb_params (scop
, nbp
);
1335 add_write (vec
<tree
> *writes
, tree def
)
1337 writes
->safe_push (def
);
1338 DEBUG_PRINT (dp
<< "Adding scalar write: ";
1339 print_generic_expr (dump_file
, def
);
1340 dp
<< "\nFrom stmt: ";
1341 print_gimple_stmt (dump_file
,
1342 SSA_NAME_DEF_STMT (def
), 0));
1346 add_read (vec
<scalar_use
> *reads
, tree use
, gimple
*use_stmt
)
1348 DEBUG_PRINT (dp
<< "Adding scalar read: ";
1349 print_generic_expr (dump_file
, use
);
1350 dp
<< "\nFrom stmt: ";
1351 print_gimple_stmt (dump_file
, use_stmt
, 0));
1352 reads
->safe_push (std::make_pair (use_stmt
, use
));
1356 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1359 build_cross_bb_scalars_def (scop_p scop
, tree def
, basic_block def_bb
,
1362 if (!is_gimple_reg (def
))
1365 bool scev_analyzable
= scev_analyzable_p (def
, scop
->scop_info
->region
);
1368 imm_use_iterator imm_iter
;
1369 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1370 /* Do not gather scalar variables that can be analyzed by SCEV as they can
1371 be generated out of the induction variables. */
1372 if ((! scev_analyzable
1373 /* But gather SESE liveouts as we otherwise fail to rewrite their
1375 || ! bb_in_sese_p (gimple_bb (use_stmt
), scop
->scop_info
->region
))
1376 && (def_bb
!= gimple_bb (use_stmt
) && !is_gimple_debug (use_stmt
)))
1378 add_write (writes
, def
);
1379 /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
1380 before all the uses have been visited. */
1381 BREAK_FROM_IMM_USE_STMT (imm_iter
);
1385 /* Record USE if it is defined in other bbs different than USE_STMT
1389 build_cross_bb_scalars_use (scop_p scop
, tree use
, gimple
*use_stmt
,
1390 vec
<scalar_use
> *reads
)
1392 if (!is_gimple_reg (use
))
1395 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1396 generated out of the induction variables. */
1397 if (scev_analyzable_p (use
, scop
->scop_info
->region
))
1400 gimple
*def_stmt
= SSA_NAME_DEF_STMT (use
);
1401 if (gimple_bb (def_stmt
) != gimple_bb (use_stmt
))
1402 add_read (reads
, use
, use_stmt
);
1405 /* Generates a polyhedral black box only if the bb contains interesting
1408 static gimple_poly_bb_p
1409 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
1411 vec
<data_reference_p
> drs
= vNULL
;
1412 vec
<tree
> writes
= vNULL
;
1413 vec
<scalar_use
> reads
= vNULL
;
1415 sese_l region
= scop
->scop_info
->region
;
1417 loop_p loop
= bb
->loop_father
;
1418 if (!loop_in_sese_p (loop
, region
))
1421 nest
= outermost_loop_in_sese (region
, bb
);
1423 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1426 gimple
*stmt
= gsi_stmt (gsi
);
1427 if (is_gimple_debug (stmt
))
1430 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1432 tree def
= gimple_get_lhs (stmt
);
1434 build_cross_bb_scalars_def (scop
, def
, gimple_bb (stmt
), &writes
);
1438 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
1439 build_cross_bb_scalars_use (scop
, use
, stmt
, &reads
);
1442 /* Handle defs and uses in PHIs. Those need special treatment given
1443 that we have to present ISL with sth that looks like we've rewritten
1444 the IL out-of-SSA. */
1445 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1448 gphi
*phi
= psi
.phi ();
1449 tree res
= gimple_phi_result (phi
);
1450 if (virtual_operand_p (res
)
1451 || scev_analyzable_p (res
, scop
->scop_info
->region
))
1453 /* To simulate out-of-SSA the block containing the PHI node has
1454 reads of the PHI destination. And to preserve SSA dependences
1455 we also write to it (the out-of-SSA decl and the SSA result
1456 are coalesced for dependence purposes which is good enough). */
1457 add_read (&reads
, res
, phi
);
1458 add_write (&writes
, res
);
1460 basic_block bb_for_succs
= bb
;
1461 if (bb_for_succs
== bb_for_succs
->loop_father
->latch
1462 && bb_in_sese_p (bb_for_succs
, scop
->scop_info
->region
)
1463 && sese_trivially_empty_bb_p (bb_for_succs
))
1464 bb_for_succs
= NULL
;
1465 while (bb_for_succs
)
1467 basic_block latch
= NULL
;
1470 FOR_EACH_EDGE (e
, ei
, bb_for_succs
->succs
)
1472 for (gphi_iterator psi
= gsi_start_phis (e
->dest
); !gsi_end_p (psi
);
1475 gphi
*phi
= psi
.phi ();
1476 tree res
= gimple_phi_result (phi
);
1477 if (virtual_operand_p (res
))
1479 /* To simulate out-of-SSA the predecessor of edges into PHI nodes
1480 has a copy from the PHI argument to the PHI destination. */
1481 if (! scev_analyzable_p (res
, scop
->scop_info
->region
))
1482 add_write (&writes
, res
);
1483 tree use
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
1484 if (TREE_CODE (use
) == SSA_NAME
1485 && ! SSA_NAME_IS_DEFAULT_DEF (use
)
1486 && gimple_bb (SSA_NAME_DEF_STMT (use
)) != bb_for_succs
1487 && ! scev_analyzable_p (use
, scop
->scop_info
->region
))
1488 add_read (&reads
, use
, phi
);
1490 if (e
->dest
== bb_for_succs
->loop_father
->latch
1491 && bb_in_sese_p (e
->dest
, scop
->scop_info
->region
)
1492 && sese_trivially_empty_bb_p (e
->dest
))
1495 /* Handle empty latch block PHIs here, otherwise we confuse ISL
1496 with extra conditional code where it then peels off the last
1497 iteration just because of that. It would be simplest if we
1498 just didn't force simple latches (thus remove the forwarder). */
1499 bb_for_succs
= latch
;
1502 /* For the region exit block add reads for all live-out vars. */
1503 if (bb
== scop
->scop_info
->region
.exit
->src
)
1505 sese_build_liveouts (scop
->scop_info
);
1508 EXECUTE_IF_SET_IN_BITMAP (scop
->scop_info
->liveout
, 0, i
, bi
)
1510 tree use
= ssa_name (i
);
1511 add_read (&reads
, use
, NULL
);
1515 if (drs
.is_empty () && writes
.is_empty () && reads
.is_empty ())
1518 return new_gimple_poly_bb (bb
, drs
, reads
, writes
);
1521 /* Compute alias-sets for all data references in DRS. */
1524 build_alias_set (scop_p scop
)
1526 int num_vertices
= scop
->drs
.length ();
1527 struct graph
*g
= new_graph (num_vertices
);
1532 FOR_EACH_VEC_ELT (scop
->drs
, i
, dr1
)
1533 for (j
= i
+1; scop
->drs
.iterate (j
, &dr2
); j
++)
1534 if (dr_may_alias_p (dr1
->dr
, dr2
->dr
, true))
1536 /* Dependences in the same alias set need to be handled
1537 by just looking at DR_ACCESS_FNs. */
1538 if (DR_NUM_DIMENSIONS (dr1
->dr
) == 0
1539 || DR_NUM_DIMENSIONS (dr1
->dr
) != DR_NUM_DIMENSIONS (dr2
->dr
)
1540 || ! operand_equal_p (DR_BASE_OBJECT (dr1
->dr
),
1541 DR_BASE_OBJECT (dr2
->dr
),
1543 || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1
->dr
)),
1544 TREE_TYPE (DR_BASE_OBJECT (dr2
->dr
))))
1553 all_vertices
= XNEWVEC (int, num_vertices
);
1554 for (i
= 0; i
< num_vertices
; i
++)
1555 all_vertices
[i
] = i
;
1558 = graphds_dfs (g
, all_vertices
, num_vertices
, NULL
, true, NULL
) + 1;
1559 free (all_vertices
);
1561 for (i
= 0; i
< g
->n_vertices
; i
++)
1562 scop
->drs
[i
].alias_set
= g
->vertices
[i
].component
+ 1;
1568 /* Gather BBs and conditions for a SCOP. */
1569 class gather_bbs
: public dom_walker
1572 gather_bbs (cdi_direction
, scop_p
, int *);
1574 virtual edge
before_dom_children (basic_block
);
1575 virtual void after_dom_children (basic_block
);
1578 auto_vec
<gimple
*, 3> conditions
, cases
;
1582 gather_bbs::gather_bbs (cdi_direction direction
, scop_p scop
, int *bb_to_rpo
)
1583 : dom_walker (direction
, false, bb_to_rpo
), scop (scop
)
1587 /* Call-back for dom_walk executed before visiting the dominated
1591 gather_bbs::before_dom_children (basic_block bb
)
1593 sese_info_p region
= scop
->scop_info
;
1594 if (!bb_in_sese_p (bb
, region
->region
))
1595 return dom_walker::STOP
;
1597 /* For loops fully contained in the region record parameters in the
1599 loop_p loop
= bb
->loop_father
;
1600 if (loop
->header
== bb
1601 && loop_in_sese_p (loop
, region
->region
))
1603 tree nb_iters
= number_of_latch_executions (loop
);
1604 if (chrec_contains_symbols (nb_iters
))
1606 nb_iters
= scalar_evolution_in_region (region
->region
,
1608 scan_tree_for_params (region
, nb_iters
);
1612 gcond
*stmt
= single_pred_cond_non_loop_exit (bb
);
1616 edge e
= single_pred_edge (bb
);
1618 conditions
.safe_push (stmt
);
1620 if (e
->flags
& EDGE_TRUE_VALUE
)
1621 cases
.safe_push (stmt
);
1623 cases
.safe_push (NULL
);
1626 scop
->scop_info
->bbs
.safe_push (bb
);
1628 gimple_poly_bb_p gbb
= try_generate_gimple_bb (scop
, bb
);
1632 GBB_CONDITIONS (gbb
) = conditions
.copy ();
1633 GBB_CONDITION_CASES (gbb
) = cases
.copy ();
1635 poly_bb_p pbb
= new_poly_bb (scop
, gbb
);
1636 scop
->pbbs
.safe_push (pbb
);
1639 data_reference_p dr
;
1640 FOR_EACH_VEC_ELT (gbb
->data_refs
, i
, dr
)
1642 DEBUG_PRINT (dp
<< "Adding memory ";
1647 print_generic_expr (dump_file
, dr
->ref
);
1648 dp
<< "\nFrom stmt: ";
1649 print_gimple_stmt (dump_file
, dr
->stmt
, 0));
1651 scop
->drs
.safe_push (dr_info (dr
, pbb
));
1657 /* Call-back for dom_walk executed after visiting the dominated
1661 gather_bbs::after_dom_children (basic_block bb
)
1663 if (!bb_in_sese_p (bb
, scop
->scop_info
->region
))
1666 if (single_pred_cond_non_loop_exit (bb
))
1674 /* Compute sth like an execution order, dominator order with first executing
1675 edges that stay inside the current loop, delaying processing exit edges. */
1677 static vec
<unsigned> order
;
1680 get_order (scop_p scop
, basic_block bb
, vec
<unsigned> *order
, unsigned *dfs_num
)
1682 if (! bb_in_sese_p (bb
, scop
->scop_info
->region
))
1685 (*order
)[bb
->index
] = (*dfs_num
)++;
1686 for (basic_block son
= first_dom_son (CDI_DOMINATORS
, bb
);
1688 son
= next_dom_son (CDI_DOMINATORS
, son
))
1689 if (flow_bb_inside_loop_p (bb
->loop_father
, son
))
1690 get_order (scop
, son
, order
, dfs_num
);
1691 for (basic_block son
= first_dom_son (CDI_DOMINATORS
, bb
);
1693 son
= next_dom_son (CDI_DOMINATORS
, son
))
1694 if (! flow_bb_inside_loop_p (bb
->loop_father
, son
))
1695 get_order (scop
, son
, order
, dfs_num
);
1698 /* Helper for qsort, sorting after order above. */
1701 cmp_pbbs (const void *pa
, const void *pb
)
1703 poly_bb_p bb1
= *((const poly_bb_p
*)pa
);
1704 poly_bb_p bb2
= *((const poly_bb_p
*)pb
);
1705 if (order
[bb1
->black_box
->bb
->index
] < order
[bb2
->black_box
->bb
->index
])
1707 else if (order
[bb1
->black_box
->bb
->index
] > order
[bb2
->black_box
->bb
->index
])
1713 /* Find Static Control Parts (SCoP) in the current function and pushes
1717 build_scops (vec
<scop_p
> *scops
)
1720 dp
.set_dump_file (dump_file
);
1723 sb
.build_scop_depth (current_loops
->tree_root
);
1725 /* Now create scops from the lightweight SESEs. */
1726 vec
<sese_l
> scops_l
= sb
.get_scops ();
1728 /* Domwalk needs a bb to RPO mapping. Compute it once here. */
1729 int *postorder
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
1730 int postorder_num
= pre_and_rev_post_order_compute (NULL
, postorder
, true);
1731 int *bb_to_rpo
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1732 for (int i
= 0; i
< postorder_num
; ++i
)
1733 bb_to_rpo
[postorder
[i
]] = i
;
1738 FOR_EACH_VEC_ELT (scops_l
, i
, s
)
1740 /* For our out-of-SSA we need a block on s->entry, similar to how
1741 we include the LCSSA block in the region. */
1742 s
->entry
= single_pred_edge (split_edge (s
->entry
));
1744 scop_p scop
= new_scop (s
->entry
, s
->exit
);
1746 /* Record all basic blocks and their conditions in REGION. */
1747 gather_bbs (CDI_DOMINATORS
, scop
, bb_to_rpo
).walk (s
->entry
->dest
);
1749 /* domwalk does not fulfil our code-generations constraints on the
1750 order of pbb which is to produce sth like execution order, delaying
1751 exection of loop exit edges. So compute such order and sort after
1753 order
.create (last_basic_block_for_fn (cfun
));
1754 order
.quick_grow (last_basic_block_for_fn (cfun
));
1755 unsigned dfs_num
= 0;
1756 get_order (scop
, s
->entry
->dest
, &order
, &dfs_num
);
1757 scop
->pbbs
.qsort (cmp_pbbs
);
1760 if (! build_alias_set (scop
))
1762 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot handle dependences\n");
1767 /* Do not optimize a scop containing only PBBs that do not belong
1769 if (sb
.nb_pbbs_in_loops (scop
) == 0)
1771 DEBUG_PRINT (dp
<< "[scop-detection-fail] no data references.\n");
1776 unsigned max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
1778 && scop
->drs
.length () >= max_arrays
)
1780 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many data references: "
1781 << scop
->drs
.length ()
1782 << " is larger than --param graphite-max-arrays-per-scop="
1783 << max_arrays
<< ".\n");
1788 find_scop_parameters (scop
);
1789 graphite_dim_t max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
1791 && scop_nb_params (scop
) > max_dim
)
1793 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many parameters: "
1794 << scop_nb_params (scop
)
1795 << " larger than --param graphite-max-nb-scop-params="
1796 << max_dim
<< ".\n");
1801 scops
->safe_push (scop
);
1805 DEBUG_PRINT (dp
<< "number of SCoPs: " << (scops
? scops
->length () : 0););
1808 #endif /* HAVE_isl */