1 /* Detection of Static Control Parts (SCoP) for Graphite.
2 Copyright (C) 2009-2015 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/>. */
25 /* Workaround for GMP 5.1.3 bug, see PR56019. */
28 #include <isl/constraint.h>
31 #include <isl/union_map.h>
34 #include "coretypes.h"
41 #include "fold-const.h"
42 #include "gimple-iterator.h"
43 #include "tree-ssa-loop-manip.h"
44 #include "tree-ssa-loop-niter.h"
45 #include "tree-ssa-loop.h"
46 #include "tree-into-ssa.h"
49 #include "tree-data-ref.h"
50 #include "tree-scalar-evolution.h"
51 #include "tree-pass.h"
52 #include "graphite-poly.h"
53 #include "tree-ssa-propagate.h"
54 #include "graphite-scop-detection.h"
55 #include "gimple-pretty-print.h"
57 /* Lightweight representation of sese for scop detection.
58 TODO: Make all this as a constant_edge. */
61 sese_l (edge e
, edge x
)
65 /* This is to push objects of sese_l in a vec. */
67 : entry (NULL
), exit (NULL
)
72 operator bool () const
78 operator= (const sese_l
&s
)
89 /* APIs for getting entry/exit of an sese. */
107 void set_dump_file (FILE *f
)
113 friend debug_printer
&operator<<(debug_printer
&output
, int i
)
115 fprintf (output
.dump_file
, "%d", i
);
118 friend debug_printer
&operator<<(debug_printer
&output
, const char *s
)
120 fprintf (output
.dump_file
, "%s", s
);
125 #define DEBUG_PRINT(args) do \
127 if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \
131 /* Return true if BB is empty, contains only DEBUG_INSNs. */
134 trivially_empty_bb_p (basic_block bb
)
136 gimple_stmt_iterator gsi
;
138 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
139 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_DEBUG
)
146 /* Forward declarations. */
147 static void make_close_phi_nodes_unique (basic_block
);
149 /* Something like "n * m" is not allowed. */
152 graphite_can_represent_init (tree e
)
154 switch (TREE_CODE (e
))
156 case POLYNOMIAL_CHREC
:
157 return graphite_can_represent_init (CHREC_LEFT (e
))
158 && graphite_can_represent_init (CHREC_RIGHT (e
));
161 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
162 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
163 && tree_fits_shwi_p (TREE_OPERAND (e
, 1));
165 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
166 && tree_fits_shwi_p (TREE_OPERAND (e
, 0));
169 case POINTER_PLUS_EXPR
:
171 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
172 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
177 case NON_LVALUE_EXPR
:
178 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
187 /* Return true when SCEV can be represented in the polyhedral model.
189 An expression can be represented, if it can be expressed as an
190 affine expression. For loops (i, j) and parameters (m, n) all
191 affine expressions are of the form:
193 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
195 1 i + 20 j + (-2) m + 25
197 Something like "i * n" or "n * m" is not allowed. */
200 graphite_can_represent_scev (tree scev
)
202 if (chrec_contains_undetermined (scev
))
205 /* We disable the handling of pointer types, because it’s currently not
206 supported by Graphite with the ISL AST generator. SSA_NAME nodes are
207 the only nodes, which are disabled in case they are pointers to object
208 types, but this can be changed. */
210 if (POINTER_TYPE_P (TREE_TYPE (scev
)) && TREE_CODE (scev
) == SSA_NAME
)
213 switch (TREE_CODE (scev
))
218 case NON_LVALUE_EXPR
:
219 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0));
222 case POINTER_PLUS_EXPR
:
224 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
225 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
228 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
229 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
230 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
231 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
232 && graphite_can_represent_init (scev
)
233 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
234 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
236 case POLYNOMIAL_CHREC
:
237 /* Check for constant strides. With a non constant stride of
238 'n' we would have a value of 'iv * n'. Also check that the
239 initial value can represented: for example 'n * m' cannot be
241 if (!evolution_function_right_is_integer_cst (scev
)
242 || !graphite_can_represent_init (scev
))
244 return graphite_can_represent_scev (CHREC_LEFT (scev
));
250 /* Only affine functions can be represented. */
251 if (tree_contains_chrecs (scev
, NULL
)
252 || !scev_is_linear_expression (scev
))
259 /* Return true when EXPR can be represented in the polyhedral model.
261 This means an expression can be represented, if it is linear with respect to
262 the loops and the strides are non parametric. LOOP is the place where the
263 expr will be evaluated. SCOP defines the region we analyse. */
266 graphite_can_represent_expr (sese_l scop
, loop_p loop
, tree expr
)
268 sese region
= new_sese (scop
.entry
, scop
.exit
);
269 tree scev
= scalar_evolution_in_region (region
, loop
, expr
);
271 return graphite_can_represent_scev (scev
);
274 /* Return true if the data references of STMT can be represented by Graphite.
275 We try to analyze the data references in a loop contained in the SCOP. */
278 stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
)
280 sese region
= new_sese (scop
.entry
, scop
.exit
);
281 loop_p nest
= outermost_loop_in_sese (region
, gimple_bb (stmt
));
282 loop_p loop
= loop_containing_stmt (stmt
);
283 vec
<data_reference_p
> drs
= vNULL
;
285 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
289 FOR_EACH_VEC_ELT (drs
, j
, dr
)
291 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
293 if (nb_subscripts
< 1)
295 free_data_refs (drs
);
299 tree ref
= DR_REF (dr
);
301 for (int i
= nb_subscripts
- 1; i
>= 0; i
--)
303 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
))
304 || (TREE_CODE (ref
) != ARRAY_REF
305 && TREE_CODE (ref
) != MEM_REF
306 && TREE_CODE (ref
) != COMPONENT_REF
))
308 free_data_refs (drs
);
312 ref
= TREE_OPERAND (ref
, 0);
316 free_data_refs (drs
);
320 /* Return true only when STMT is simple enough for being handled by Graphite.
321 This depends on SCOP, as the parameters are initialized relatively to
322 this basic block, the linear functions are initialized based on the outermost
323 loop containing STMT inside the SCOP. BB is the place where we try to
324 evaluate the STMT. */
327 stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
, basic_block bb
)
329 loop_p loop
= bb
->loop_father
;
333 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
334 Calls have side-effects, except those to const or pure
336 if (gimple_has_volatile_ops (stmt
)
337 || (gimple_code (stmt
) == GIMPLE_CALL
338 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
339 || (gimple_code (stmt
) == GIMPLE_ASM
))
341 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
342 << "Graphite cannot handle this stmt:\n";
343 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
));
347 if (is_gimple_debug (stmt
))
350 if (!stmt_has_simple_data_refs_p (scop
, stmt
))
352 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
353 << "Graphite cannot handle data-refs in stmt:\n";
354 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
););
358 switch (gimple_code (stmt
))
365 /* We can handle all binary comparisons. Inequalities are
366 also supported as they can be represented with union of
368 enum tree_code code
= gimple_cond_code (stmt
);
369 if (!(code
== LT_EXPR
376 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
377 << "Graphite cannot handle cond stmt:\n";
378 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
));
382 for (unsigned i
= 0; i
< 2; ++i
)
384 tree op
= gimple_op (stmt
, i
);
385 if (!graphite_can_represent_expr (scop
, loop
, op
)
386 /* We can only constrain on integer type. */
387 || (TREE_CODE (TREE_TYPE (op
)) != INTEGER_TYPE
))
389 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
390 << "Graphite cannot represent stmt:\n";
391 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
));
404 /* These nodes cut a new scope. */
405 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
406 << "Gimple stmt not handled in Graphite:\n";
407 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
));
414 /* Return true when BB contains a harmful operation for a scop: that
415 can be a function call with side effects, the induction variables
416 are not linear with respect to SCOP, etc. The current open
417 scop should end before this statement. */
420 harmful_stmt_in_bb (sese_l scop
, basic_block bb
)
422 gimple_stmt_iterator gsi
;
424 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
425 if (!stmt_simple_for_scop_p (scop
, gsi_stmt (gsi
), bb
))
431 /* Returns true when P1 and P2 are close phis with the same
435 same_close_phi_node (gphi
*p1
, gphi
*p2
)
437 return operand_equal_p (gimple_phi_arg_def (p1
, 0),
438 gimple_phi_arg_def (p2
, 0), 0);
441 /* Remove the close phi node at GSI and replace its rhs with the rhs
445 remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
)
449 imm_use_iterator imm_iter
;
450 tree res
= gimple_phi_result (phi
);
451 tree def
= gimple_phi_result (gsi
->phi ());
453 gcc_assert (same_close_phi_node (phi
, gsi
->phi ()));
455 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
457 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
458 SET_USE (use_p
, res
);
460 update_stmt (use_stmt
);
462 /* It is possible that we just created a duplicate close-phi
463 for an already-processed containing loop. Check for this
464 case and clean it up. */
465 if (gimple_code (use_stmt
) == GIMPLE_PHI
466 && gimple_phi_num_args (use_stmt
) == 1)
467 make_close_phi_nodes_unique (gimple_bb (use_stmt
));
470 remove_phi_node (gsi
, true);
473 /* Removes all the close phi duplicates from BB. */
476 make_close_phi_nodes_unique (basic_block bb
)
480 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
482 gphi_iterator gsi
= psi
;
483 gphi
*phi
= psi
.phi ();
485 /* At this point, PHI should be a close phi in normal form. */
486 gcc_assert (gimple_phi_num_args (phi
) == 1);
488 /* Iterate over the next phis and remove duplicates. */
490 while (!gsi_end_p (gsi
))
491 if (same_close_phi_node (phi
, gsi
.phi ()))
492 remove_duplicate_close_phi (phi
, &gsi
);
498 /* Transforms LOOP to the canonical loop closed SSA form. */
501 canonicalize_loop_closed_ssa (loop_p loop
)
503 edge e
= single_exit (loop
);
506 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
511 if (single_pred_p (bb
))
513 e
= split_block_after_labels (bb
);
514 DEBUG_PRINT (dp
<< "\nSplitting bb_" << bb
->index
);
515 make_close_phi_nodes_unique (e
->src
);
520 basic_block close
= split_edge (e
);
522 e
= single_succ_edge (close
);
523 DEBUG_PRINT (dp
<< "\nSplitting edge ("
524 << e
->src
->index
<< "," << e
->dest
->index
527 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
529 gphi
*phi
= psi
.phi ();
532 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
533 if (gimple_phi_arg_edge (phi
, i
) == e
)
535 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
539 if (TREE_CODE (arg
) != SSA_NAME
)
542 close_phi
= create_phi_node (NULL_TREE
, close
);
543 res
= create_new_def_for (arg
, close_phi
,
544 gimple_phi_result_ptr (close_phi
));
545 add_phi_arg (close_phi
, arg
,
546 gimple_phi_arg_edge (close_phi
, 0),
548 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
549 replace_exp (use_p
, res
);
554 make_close_phi_nodes_unique (close
);
557 /* The code above does not properly handle changes in the post dominance
558 information (yet). */
559 recompute_all_dominators ();
562 /* Converts the current loop closed SSA form to a canonical form
563 expected by the Graphite code generation.
565 The loop closed SSA form has the following invariant: a variable
566 defined in a loop that is used outside the loop appears only in the
567 phi nodes in the destination of the loop exit. These phi nodes are
568 called close phi nodes.
570 The canonical loop closed SSA form contains the extra invariants:
572 - when the loop contains only one exit, the close phi nodes contain
573 only one argument. That implies that the basic block that contains
574 the close phi nodes has only one predecessor, that is a basic block
577 - the basic block containing the close phi nodes does not contain
580 - there exist only one phi node per definition in the loop.
584 canonicalize_loop_closed_ssa_form (void)
588 #ifdef ENABLE_CHECKING
589 verify_loop_closed_ssa (true);
592 FOR_EACH_LOOP (loop
, 0)
593 canonicalize_loop_closed_ssa (loop
);
595 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
596 update_ssa (TODO_update_ssa
);
598 #ifdef ENABLE_CHECKING
599 verify_loop_closed_ssa (true);
603 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
604 different colors. If there are not enough colors, paint the
605 remaining SCoPs in gray.
608 - "*" after the node number denotes the entry of a SCoP,
609 - "#" after the node number denotes the exit of a SCoP,
610 - "()" around the node number denotes the entry or the
611 exit nodes of the SCOP. These are not part of SCoP. */
614 dot_all_scops_1 (FILE *file
, vec
<scop_p
> scops
)
623 /* Disable debugging while printing graph. */
624 int tmp_dump_flags
= dump_flags
;
627 fprintf (file
, "digraph all {\n");
629 FOR_ALL_BB_FN (bb
, cfun
)
631 int part_of_scop
= false;
633 /* Use HTML for every bb label. So we are able to print bbs
634 which are part of two different SCoPs, with two different
635 background colors. */
636 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
638 fprintf (file
, "CELLSPACING=\"0\">\n");
640 /* Select color for SCoP. */
641 FOR_EACH_VEC_ELT (scops
, i
, scop
)
643 sese region
= SCOP_REGION (scop
);
644 if (bb_in_sese_p (bb
, region
)
645 || (SESE_EXIT_BB (region
) == bb
)
646 || (SESE_ENTRY_BB (region
) == bb
))
705 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color
);
707 if (!bb_in_sese_p (bb
, region
))
708 fprintf (file
, " (");
710 if (bb
== SESE_ENTRY_BB (region
)
711 && bb
== SESE_EXIT_BB (region
))
712 fprintf (file
, " %d*# ", bb
->index
);
713 else if (bb
== SESE_ENTRY_BB (region
))
714 fprintf (file
, " %d* ", bb
->index
);
715 else if (bb
== SESE_EXIT_BB (region
))
716 fprintf (file
, " %d# ", bb
->index
);
718 fprintf (file
, " %d ", bb
->index
);
720 fprintf (file
, "{lp_%d}", bb
->loop_father
->num
);
722 if (!bb_in_sese_p (bb
,region
))
725 fprintf (file
, "</TD></TR>\n");
732 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
733 fprintf (file
, " %d {lp_%d} </TD></TR>\n",
734 bb
->index
, bb
->loop_father
->num
);
736 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
739 FOR_ALL_BB_FN (bb
, cfun
)
741 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
742 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
745 fputs ("}\n\n", file
);
747 /* Enable debugging again. */
748 dump_flags
= tmp_dump_flags
;
751 /* Display all SCoPs using dotty. */
754 dot_all_scops (vec
<scop_p
> scops
)
756 /* When debugging, enable the following code. This cannot be used
757 in production compilers because it calls "system". */
760 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
763 dot_all_scops_1 (stream
, scops
);
766 x
= system ("dotty /tmp/allscops.dot &");
768 dot_all_scops_1 (stderr
, scops
);
772 /* Display all SCoPs using dotty. */
775 dot_scop (scop_p scop
)
777 auto_vec
<scop_p
, 1> scops
;
780 scops
.safe_push (scop
);
782 /* When debugging, enable the following code. This cannot be used
783 in production compilers because it calls "system". */
787 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
790 dot_all_scops_1 (stream
, scops
);
792 x
= system ("dotty /tmp/allscops.dot &");
795 dot_all_scops_1 (stderr
, scops
);
799 /* Return true when the body of LOOP has statements that can be represented as a
803 loop_body_is_valid_scop (loop_p loop
, sese_l scop
)
805 if (!loop_nest_has_data_refs (loop
))
807 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_"
808 << loop
->num
<< "does not have any data reference.\n");
812 basic_block
*bbs
= get_loop_body (loop
);
813 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
815 basic_block bb
= bbs
[i
];
817 if (harmful_stmt_in_bb (scop
, bb
))
827 if (!loop_body_is_valid_scop (loop
, scop
))
836 /* Build the maximal scop containing LOOP(s) and add it to SCOPS. */
845 static sese_l invalid_sese
;
854 get_sese (loop_p loop
)
859 if (!loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
))
861 edge scop_end
= single_exit (loop
);
864 edge scop_begin
= loop_preheader_edge (loop
);
865 sese_l
s (scop_begin
, scop_end
);
870 get_nearest_dom_with_single_entry (basic_block dom
)
874 /* If e1->src dominates e2->src then e1->src will also dominate dom. */
875 if (dom
->preds
->length () == 2)
877 edge e1
= (*dom
->preds
)[0];
878 edge e2
= (*dom
->preds
)[1];
879 if (dominated_by_p (CDI_DOMINATORS
, e2
->src
, e1
->src
))
881 if (dominated_by_p (CDI_DOMINATORS
, e1
->src
, e2
->src
))
885 while (dom
->preds
->length () != 1)
887 if (dom
->preds
->length () < 1)
889 dom
= get_immediate_dominator (CDI_DOMINATORS
, dom
);
893 return (*dom
->preds
)[0];
897 get_nearest_pdom_with_single_exit (basic_block dom
)
901 if (dom
->succs
->length () == 2)
903 edge e1
= (*dom
->succs
)[0];
904 edge e2
= (*dom
->succs
)[1];
905 if (dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, e1
->dest
))
907 if (dominated_by_p (CDI_POST_DOMINATORS
, e1
->dest
, e2
->dest
))
911 while (dom
->succs
->length () != 1)
913 if (dom
->succs
->length () < 1)
915 dom
= get_immediate_dominator (CDI_POST_DOMINATORS
, dom
);
919 return (*dom
->succs
)[0];
922 /* Print S to FILE. */
925 print_sese (FILE *file
, sese_l s
)
927 fprintf (file
, "(entry_edge (bb_%d, bb_%d), exit_edge (bb_%d, bb_%d))\n",
928 s
.entry
->src
->index
, s
.entry
->dest
->index
,
929 s
.exit
->src
->index
, s
.exit
->dest
->index
);
932 /* Merge scops at same loop depth and returns the new sese.
933 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
936 merge_sese (sese_l first
, sese_l second
)
938 /* In the trivial case first/second may be NULL. */
944 DEBUG_PRINT (dp
<< "[try-merging-sese] s1: ";
945 print_sese (dump_file
, first
);
946 dp
<< "[try-merging-sese] s2: ";
947 print_sese (dump_file
, second
));
949 /* Assumption: Both the sese's should be at the same loop depth or one scop
950 should subsume the other like in case of nested loops. */
952 /* Find the common dominators for entry,
953 and common post-dominators for the exit. */
954 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
,
955 get_entry_bb (first
.entry
),
956 get_entry_bb (second
.entry
));
959 edge entry
= get_nearest_dom_with_single_entry (dom
);
963 basic_block pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
,
964 get_exit_bb (first
.exit
),
965 get_exit_bb (second
.exit
));
966 pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
, dom
, pdom
);
968 edge exit
= get_nearest_pdom_with_single_exit (pdom
);
972 sese_l
combined (entry
, exit
);
974 /* FIXME: We could iterate to find the dom which dominates pdom, and pdom
975 which post-dominates dom, until it stabilizes. Also, ENTRY->SRC and
976 EXIT->DEST should be in the same loop nest. */
977 if (!dominated_by_p (CDI_DOMINATORS
, pdom
, dom
)
978 || loop_depth (entry
->src
->loop_father
)
979 != loop_depth (exit
->dest
->loop_father
))
982 /* For now we just want to bail out when exit does not post-dominate entry.
983 TODO: We might just add a basic_block at the exit to make exit
984 post-dominate entry (the entire region). */
985 if (!dominated_by_p (CDI_POST_DOMINATORS
, get_entry_bb (entry
),
987 || !dominated_by_p (CDI_DOMINATORS
, get_exit_bb (exit
),
988 get_entry_bb (entry
)))
990 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
994 /* FIXME: We should remove this piece of code once
995 canonicalize_loop_closed_ssa has been removed, because that function
996 adds a BB with single exit. */
997 if (!trivially_empty_bb_p (get_exit_bb (combined
.exit
)))
999 /* Find the first empty succ (with single exit) of combined.exit. */
1000 basic_block imm_succ
= combined
.exit
->dest
;
1001 if (single_succ_p (imm_succ
) && trivially_empty_bb_p (imm_succ
))
1002 combined
.exit
= single_succ_edge (imm_succ
);
1005 DEBUG_PRINT (dp
<< "\n[scop-detection-fail] Discarding SCoP because "
1006 << "no single exit (empty succ) for sese exit";
1007 print_sese (dump_file
, combined
));
1008 return invalid_sese
;
1012 /* Analyze all the BBs in new sese. */
1013 if (harmful_stmt_in_region (combined
))
1014 return invalid_sese
;
1016 DEBUG_PRINT (dp
<< "[merged-sese] s1: ";
1017 print_sese (dump_file
, combined
));
1022 /* Build scop outer->inner if possible. */
1024 build_scop_depth (sese_l s
, loop_p loop
)
1029 DEBUG_PRINT (dp
<< "\n[Depth loop_" << loop
->num
<< "]");
1030 s
= build_scop_depth (s
, loop
->inner
);
1032 sese_l s2
= merge_sese (s
, get_sese (loop
));
1035 /* s might be a valid scop, so return it and start analyzing from the
1037 build_scop_depth (invalid_sese
, loop
->next
);
1041 if (!loop_is_valid_scop (loop
, s2
))
1042 return build_scop_depth (invalid_sese
, loop
->next
);
1044 return build_scop_breadth (s2
, loop
);
1047 /* If loop and loop->next are valid scops, try to merge them. */
1050 build_scop_breadth (sese_l s1
, loop_p loop
)
1054 DEBUG_PRINT (dp
<< "\n[Breadth loop_" << loop
->num
<< "]");
1058 sese_l s2
= build_scop_depth (invalid_sese
, l
->next
);
1066 sese_l combined
= merge_sese (s1
, s2
);
1078 /* Returns true when Graphite can represent LOOP in SCOP.
1079 FIXME: For the moment, graphite cannot be used on loops that iterate using
1080 induction variables that wrap. */
1082 can_represent_loop_1 (loop_p loop
, sese_l scop
)
1085 struct tree_niter_desc niter_desc
;
1087 return single_exit (loop
)
1088 && number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
1089 && niter_desc
.control
.no_overflow
1090 && (niter
= number_of_latch_executions (loop
))
1091 && !chrec_contains_undetermined (niter
)
1092 && graphite_can_represent_expr (scop
, loop
, niter
);
1095 /* Return true when all the loops within LOOP can be represented by
1099 can_represent_loop (loop_p loop
, sese_l scop
)
1101 if (!can_represent_loop_1 (loop
, scop
))
1103 if (loop
->inner
&& !can_represent_loop (loop
->inner
, scop
))
1105 if (loop
->next
&& !can_represent_loop (loop
->next
, scop
))
1111 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
1112 region of code that can be represented in the polyhedral model. SCOP
1113 defines the region we analyse. */
1116 loop_is_valid_scop (loop_p loop
, sese_l scop
)
1121 if (!can_represent_loop (loop
, scop
))
1123 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot represent loop_"
1124 << loop
->num
<< "\n");
1128 if (loop_body_is_valid_scop (loop
, scop
))
1130 DEBUG_PRINT (dp
<< "[valid-scop] loop_"
1131 << loop
->num
<< "is a valid scop.\n");
1137 /* Return true when BEGIN is the preheader edge of a loop with a single exit
1141 region_has_one_loop (sese_l s
)
1143 edge begin
= s
.entry
;
1145 /* Check for a single perfectly nested loop. */
1146 if (begin
->dest
->loop_father
->inner
)
1149 /* Otherwise, check whether we have adjacent loops. */
1150 return begin
->dest
->loop_father
== end
->src
->loop_father
;
1153 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
1160 /* Do not add scops with only one loop. */
1161 if (region_has_one_loop (s
))
1163 DEBUG_PRINT (dp
<< "\n[scop-detection-fail] Discarding one loop SCoP";
1164 print_sese (dump_file
, s
));
1168 if (get_exit_bb (s
.exit
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1170 DEBUG_PRINT (dp
<< "\n[scop-detection-fail] "
1171 << "Discarding SCoP exiting to return";
1172 print_sese (dump_file
, s
));
1176 /* Remove all the scops which are subsumed by s. */
1177 remove_subscops (s
);
1179 /* Replace this with split-intersecting scops. */
1180 remove_intersecting_scops (s
);
1182 scops
.safe_push (s
);
1183 DEBUG_PRINT (dp
<< "\nAdding SCoP "; print_sese (dump_file
, s
));
1186 /* Return true when a statement in SCOP cannot be represented by Graphite.
1187 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
1188 Limit the number of bbs between adjacent loops to
1189 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
1192 harmful_stmt_in_region (sese_l scop
)
1194 basic_block exit_bb
= get_exit_bb (scop
.exit
);
1195 basic_block entry_bb
= get_entry_bb (scop
.entry
);
1197 DEBUG_PRINT (dp
<< "\n[checking-harmful-bbs] ";
1198 print_sese (dump_file
, scop
));
1199 gcc_assert (dominated_by_p (CDI_DOMINATORS
, exit_bb
, entry_bb
));
1201 int depth
= bb_dom_dfs_in (CDI_DOMINATORS
, exit_bb
)
1202 - bb_dom_dfs_in (CDI_DOMINATORS
, entry_bb
);
1204 gcc_assert (depth
>0);
1206 vec
<basic_block
> dom
= get_dominated_to_depth (CDI_DOMINATORS
,
1210 FOR_EACH_VEC_ELT (dom
, i
, bb
)
1212 DEBUG_PRINT (dp
<< "\nVisiting bb_" << bb
->index
);
1214 /* We don't want to analyze any bb outside sese. */
1215 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb
, exit_bb
))
1218 if (harmful_stmt_in_bb (scop
, bb
))
1225 /* Returns true if S1 subsumes/surrounds S2. */
1227 subsumes (sese_l s1
, sese_l s2
)
1229 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
.entry
),
1230 get_entry_bb (s1
.entry
))
1231 && dominated_by_p (CDI_POST_DOMINATORS
, get_entry_bb (s2
.exit
),
1232 get_entry_bb (s1
.exit
)))
1237 /* Remove a SCoP which is subsumed by S1. */
1239 remove_subscops (sese_l s1
)
1243 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
1245 if (subsumes (s1
, s2
))
1247 DEBUG_PRINT (dp
<< "\nRemoving sub-SCoP";
1248 print_sese (dump_file
, s2
));
1249 scops
.unordered_remove (j
);
1254 /* Returns true if S1 intersects with S2. Since we already know that S1 does
1255 not subsume S2 or vice-versa, we only check for entry bbs. */
1258 intersects (sese_l s1
, sese_l s2
)
1260 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
.entry
),
1261 get_entry_bb (s1
.entry
))
1262 && !dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
.entry
),
1263 get_exit_bb (s1
.exit
)))
1265 if ((s1
.exit
== s2
.entry
)
1266 || (s2
.exit
== s1
.entry
))
1272 /* Remove one of the scops when it intersects with any other. */
1275 remove_intersecting_scops (sese_l s1
)
1279 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
1281 if (intersects (s1
, s2
))
1283 DEBUG_PRINT (dp
<< "\nRemoving intersecting SCoP";
1284 print_sese (dump_file
, s2
);
1285 dp
<< "Intersects with:";
1286 print_sese (dump_file
, s1
));
1287 scops
.unordered_remove (j
);
1296 sese_l
scop_builder::invalid_sese (0);
1298 /* Find Static Control Parts (SCoP) in the current function and pushes
1302 build_scops (vec
<scop_p
> *scops
)
1305 dp
.set_dump_file (dump_file
);
1307 canonicalize_loop_closed_ssa_form ();
1310 sb
.build_scop_depth (scop_builder::invalid_sese
, current_loops
->tree_root
);
1312 /* Now create scops from the lightweight SESEs. */
1313 vec
<sese_l
> scops_l
= sb
.get_scops ();
1316 FOR_EACH_VEC_ELT (scops_l
, i
, s
)
1318 sese sese_reg
= new_sese (s
.entry
, s
.exit
);
1319 scops
->safe_push (new_scop (sese_reg
));
1322 DEBUG_PRINT (dp
<< "number of SCoPs: " << (scops
? scops
->length () : 0););
1325 #endif /* HAVE_isl */