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"
42 #include "fold-const.h"
43 #include "gimple-iterator.h"
45 #include "tree-ssa-loop-manip.h"
46 #include "tree-ssa-loop-niter.h"
47 #include "tree-ssa-loop.h"
48 #include "tree-into-ssa.h"
51 #include "tree-data-ref.h"
52 #include "tree-scalar-evolution.h"
53 #include "tree-pass.h"
54 #include "graphite-poly.h"
55 #include "tree-ssa-propagate.h"
56 #include "graphite-scop-detection.h"
57 #include "gimple-pretty-print.h"
66 set_dump_file (FILE *f
)
72 friend debug_printer
&
73 operator<< (debug_printer
&output
, int i
)
75 fprintf (output
.dump_file
, "%d", i
);
78 friend debug_printer
&
79 operator<< (debug_printer
&output
, const char *s
)
81 fprintf (output
.dump_file
, "%s", s
);
86 #define DEBUG_PRINT(args) do \
88 if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \
91 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
92 different colors. If there are not enough colors, paint the
93 remaining SCoPs in gray.
96 - "*" after the node number denotes the entry of a SCoP,
97 - "#" after the node number denotes the exit of a SCoP,
98 - "()" around the node number denotes the entry or the
99 exit nodes of the SCOP. These are not part of SCoP. */
102 dot_all_scops_1 (FILE *file
, vec
<scop_p
> scops
)
111 /* Disable debugging while printing graph. */
112 int tmp_dump_flags
= dump_flags
;
115 fprintf (file
, "digraph all {\n");
117 FOR_ALL_BB_FN (bb
, cfun
)
119 int part_of_scop
= false;
121 /* Use HTML for every bb label. So we are able to print bbs
122 which are part of two different SCoPs, with two different
123 background colors. */
124 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
126 fprintf (file
, "CELLSPACING=\"0\">\n");
128 /* Select color for SCoP. */
129 FOR_EACH_VEC_ELT (scops
, i
, scop
)
131 sese_l region
= scop
->scop_info
->region
;
132 if (bb_in_sese_p (bb
, region
) || (region
.exit
->dest
== bb
)
133 || (region
.entry
->dest
== bb
))
192 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
195 if (!bb_in_sese_p (bb
, region
))
196 fprintf (file
, " (");
198 if (bb
== region
.entry
->dest
&& bb
== region
.exit
->dest
)
199 fprintf (file
, " %d*# ", bb
->index
);
200 else if (bb
== region
.entry
->dest
)
201 fprintf (file
, " %d* ", bb
->index
);
202 else if (bb
== region
.exit
->dest
)
203 fprintf (file
, " %d# ", bb
->index
);
205 fprintf (file
, " %d ", bb
->index
);
207 fprintf (file
, "{lp_%d}", bb
->loop_father
->num
);
209 if (!bb_in_sese_p (bb
, region
))
212 fprintf (file
, "</TD></TR>\n");
219 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
220 fprintf (file
, " %d {lp_%d} </TD></TR>\n", bb
->index
,
221 bb
->loop_father
->num
);
223 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
226 FOR_ALL_BB_FN (bb
, cfun
)
228 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
229 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
232 fputs ("}\n\n", file
);
234 /* Enable debugging again. */
235 dump_flags
= tmp_dump_flags
;
238 /* Display all SCoPs using dotty. */
241 dot_all_scops (vec
<scop_p
> scops
)
243 /* When debugging, enable the following code. This cannot be used
244 in production compilers because it calls "system". */
247 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
250 dot_all_scops_1 (stream
, scops
);
253 x
= system ("dotty /tmp/allscops.dot &");
255 dot_all_scops_1 (stderr
, scops
);
259 /* Display all SCoPs using dotty. */
262 dot_scop (scop_p scop
)
264 auto_vec
<scop_p
, 1> scops
;
267 scops
.safe_push (scop
);
269 /* When debugging, enable the following code. This cannot be used
270 in production compilers because it calls "system". */
274 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
277 dot_all_scops_1 (stream
, scops
);
279 x
= system ("dotty /tmp/allscops.dot &");
282 dot_all_scops_1 (stderr
, scops
);
286 /* Return true if BB is empty, contains only DEBUG_INSNs. */
289 trivially_empty_bb_p (basic_block bb
)
291 gimple_stmt_iterator gsi
;
293 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
294 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_DEBUG
)
300 /* Returns true when P1 and P2 are close phis with the same
304 same_close_phi_node (gphi
*p1
, gphi
*p2
)
306 return operand_equal_p (gimple_phi_arg_def (p1
, 0),
307 gimple_phi_arg_def (p2
, 0), 0);
310 static void make_close_phi_nodes_unique (basic_block bb
);
312 /* Remove the close phi node at GSI and replace its rhs with the rhs
316 remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
)
320 imm_use_iterator imm_iter
;
321 tree res
= gimple_phi_result (phi
);
322 tree def
= gimple_phi_result (gsi
->phi ());
324 gcc_assert (same_close_phi_node (phi
, gsi
->phi ()));
326 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
328 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
329 SET_USE (use_p
, res
);
331 update_stmt (use_stmt
);
333 /* It is possible that we just created a duplicate close-phi
334 for an already-processed containing loop. Check for this
335 case and clean it up. */
336 if (gimple_code (use_stmt
) == GIMPLE_PHI
337 && gimple_phi_num_args (use_stmt
) == 1)
338 make_close_phi_nodes_unique (gimple_bb (use_stmt
));
341 remove_phi_node (gsi
, true);
344 /* Removes all the close phi duplicates from BB. */
347 make_close_phi_nodes_unique (basic_block bb
)
351 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
353 gphi_iterator gsi
= psi
;
354 gphi
*phi
= psi
.phi ();
356 /* At this point, PHI should be a close phi in normal form. */
357 gcc_assert (gimple_phi_num_args (phi
) == 1);
359 /* Iterate over the next phis and remove duplicates. */
361 while (!gsi_end_p (gsi
))
362 if (same_close_phi_node (phi
, gsi
.phi ()))
363 remove_duplicate_close_phi (phi
, &gsi
);
369 /* Transforms LOOP to the canonical loop closed SSA form. */
372 canonicalize_loop_closed_ssa (loop_p loop
)
374 edge e
= single_exit (loop
);
377 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
382 if (single_pred_p (bb
))
384 e
= split_block_after_labels (bb
);
385 DEBUG_PRINT (dp
<< "\nSplitting bb_" << bb
->index
);
386 make_close_phi_nodes_unique (e
->src
);
391 basic_block close
= split_edge (e
);
393 e
= single_succ_edge (close
);
394 DEBUG_PRINT (dp
<< "\nSplitting edge (" << e
->src
->index
<< ","
395 << e
->dest
->index
<< ")\n");
397 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
399 gphi
*phi
= psi
.phi ();
402 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
403 if (gimple_phi_arg_edge (phi
, i
) == e
)
405 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
409 if (TREE_CODE (arg
) != SSA_NAME
)
412 close_phi
= create_phi_node (NULL_TREE
, close
);
413 res
= create_new_def_for (arg
, close_phi
,
414 gimple_phi_result_ptr (close_phi
));
415 add_phi_arg (close_phi
, arg
,
416 gimple_phi_arg_edge (close_phi
, 0),
418 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
419 replace_exp (use_p
, res
);
424 make_close_phi_nodes_unique (close
);
427 /* The code above does not properly handle changes in the post dominance
428 information (yet). */
429 recompute_all_dominators ();
432 /* Converts the current loop closed SSA form to a canonical form
433 expected by the Graphite code generation.
435 The loop closed SSA form has the following invariant: a variable
436 defined in a loop that is used outside the loop appears only in the
437 phi nodes in the destination of the loop exit. These phi nodes are
438 called close phi nodes.
440 The canonical loop closed SSA form contains the extra invariants:
442 - when the loop contains only one exit, the close phi nodes contain
443 only one argument. That implies that the basic block that contains
444 the close phi nodes has only one predecessor, that is a basic block
447 - the basic block containing the close phi nodes does not contain
450 - there exist only one phi node per definition in the loop.
454 canonicalize_loop_closed_ssa_form (void)
456 checking_verify_loop_closed_ssa (true);
459 FOR_EACH_LOOP (loop
, 0)
460 canonicalize_loop_closed_ssa (loop
);
462 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
463 update_ssa (TODO_update_ssa
);
465 checking_verify_loop_closed_ssa (true);
468 /* Can all ivs be represented by a signed integer?
469 As ISL might generate negative values in its expressions, signed loop ivs
470 are required in the backend. */
473 loop_ivs_can_be_represented (loop_p loop
)
475 unsigned type_long_long
= TYPE_PRECISION (long_long_integer_type_node
);
476 for (gphi_iterator psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
);
479 gphi
*phi
= psi
.phi ();
480 tree res
= PHI_RESULT (phi
);
481 tree type
= TREE_TYPE (res
);
483 if (TYPE_UNSIGNED (type
) && TYPE_PRECISION (type
) >= type_long_long
)
490 /* Returns a COND_EXPR statement when BB has a single predecessor, the
491 edge between BB and its predecessor is not a loop exit edge, and
492 the last statement of the single predecessor is a COND_EXPR. */
495 single_pred_cond_non_loop_exit (basic_block bb
)
497 if (single_pred_p (bb
))
499 edge e
= single_pred_edge (bb
);
500 basic_block pred
= e
->src
;
503 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
506 stmt
= last_stmt (pred
);
508 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
509 return as_a
<gcond
*> (stmt
);
518 /* Build the maximal scop containing LOOPs and add it to SCOPS. */
523 scop_detection () : scops (vNULL
) {}
530 /* A marker for invalid sese_l. */
531 static sese_l invalid_sese
;
533 /* Return the SCOPS in this SCOP_DETECTION. */
541 /* Return an sese_l around the LOOP. */
543 sese_l
get_sese (loop_p loop
);
545 /* Return the closest dominator with a single entry edge. In case of a
546 back-loop the back-edge is not counted. */
548 static edge
get_nearest_dom_with_single_entry (basic_block dom
);
550 /* Return the closest post-dominator with a single exit edge. In case of a
551 back-loop the back-edge is not counted. */
553 static edge
get_nearest_pdom_with_single_exit (basic_block dom
);
555 /* Print S to FILE. */
557 static void print_sese (FILE *file
, sese_l s
);
559 /* Merge scops at same loop depth and returns the new sese.
560 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
562 sese_l
merge_sese (sese_l first
, sese_l second
) const;
564 /* Build scop outer->inner if possible. */
566 sese_l
build_scop_depth (sese_l s
, loop_p loop
);
568 /* If loop and loop->next are valid scops, try to merge them. */
570 sese_l
build_scop_breadth (sese_l s1
, loop_p loop
);
572 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
573 region of code that can be represented in the polyhedral model. SCOP
574 defines the region we analyse. */
576 bool loop_is_valid_scop (loop_p loop
, sese_l scop
) const;
578 /* Return true when BEGIN is the preheader edge of a loop with a single exit
581 static bool region_has_one_loop (sese_l s
);
583 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
585 void add_scop (sese_l s
);
587 /* Returns true if S1 subsumes/surrounds S2. */
588 static bool subsumes (sese_l s1
, sese_l s2
);
590 /* Remove a SCoP which is subsumed by S1. */
591 void remove_subscops (sese_l s1
);
593 /* Returns true if S1 intersects with S2. Since we already know that S1 does
594 not subsume S2 or vice-versa, we only check for entry bbs. */
596 static bool intersects (sese_l s1
, sese_l s2
);
598 /* Remove one of the scops when it intersects with any other. */
600 void remove_intersecting_scops (sese_l s1
);
602 /* Return true when the body of LOOP has statements that can be represented
605 bool loop_body_is_valid_scop (loop_p loop
, sese_l scop
) const;
607 /* Return true when BB contains a harmful operation for a scop: that
608 can be a function call with side effects, the induction variables
609 are not linear with respect to SCOP, etc. The current open
610 scop should end before this statement. */
612 bool harmful_stmt_in_bb (sese_l scop
, basic_block bb
) const;
614 /* Return true when a statement in SCOP cannot be represented by Graphite.
615 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
616 Limit the number of bbs between adjacent loops to
617 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
619 bool harmful_stmt_in_region (sese_l scop
) const;
621 /* Return true only when STMT is simple enough for being handled by Graphite.
622 This depends on SCOP, as the parameters are initialized relatively to
623 this basic block, the linear functions are initialized based on the
624 outermost loop containing STMT inside the SCOP. BB is the place where we
625 try to evaluate the STMT. */
627 bool stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
628 basic_block bb
) const;
630 /* Something like "n * m" is not allowed. */
632 static bool graphite_can_represent_init (tree e
);
634 /* Return true when SCEV can be represented in the polyhedral model.
636 An expression can be represented, if it can be expressed as an
637 affine expression. For loops (i, j) and parameters (m, n) all
638 affine expressions are of the form:
640 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
642 1 i + 20 j + (-2) m + 25
644 Something like "i * n" or "n * m" is not allowed. */
646 static bool graphite_can_represent_scev (tree scev
);
648 /* Return true when EXPR can be represented in the polyhedral model.
650 This means an expression can be represented, if it is linear with respect
651 to the loops and the strides are non parametric. LOOP is the place where
652 the expr will be evaluated. SCOP defines the region we analyse. */
654 static bool graphite_can_represent_expr (sese_l scop
, loop_p loop
,
657 /* Return true if the data references of STMT can be represented by Graphite.
658 We try to analyze the data references in a loop contained in the SCOP. */
660 static bool stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
);
662 /* Remove the close phi node at GSI and replace its rhs with the rhs
665 static void remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
);
667 /* Returns true when Graphite can represent LOOP in SCOP.
668 FIXME: For the moment, graphite cannot be used on loops that iterate using
669 induction variables that wrap. */
671 static bool can_represent_loop_1 (loop_p loop
, sese_l scop
);
673 /* Return true when all the loops within LOOP can be represented by
676 static bool can_represent_loop (loop_p loop
, sese_l scop
);
678 /* Returns the number of pbbs that are in loops contained in SCOP. */
680 static int nb_pbbs_in_loops (scop_p scop
);
682 static bool graphite_can_represent_stmt (sese_l
, gimple
*, basic_block
);
688 sese_l
scop_detection::invalid_sese (NULL
, NULL
);
690 /* Return an sese_l around the LOOP. */
693 scop_detection::get_sese (loop_p loop
)
698 if (!loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
))
700 edge scop_end
= single_exit (loop
);
703 edge scop_begin
= loop_preheader_edge (loop
);
704 sese_l
s (scop_begin
, scop_end
);
708 /* Return the closest dominator with a single entry edge. */
711 scop_detection::get_nearest_dom_with_single_entry (basic_block dom
)
715 /* If e1->src dominates e2->src then e1->src will also dominate dom. */
716 if (dom
->preds
->length () == 2)
718 edge e1
= (*dom
->preds
)[0];
719 edge e2
= (*dom
->preds
)[1];
720 if (dominated_by_p (CDI_DOMINATORS
, e2
->src
, e1
->src
))
722 if (dominated_by_p (CDI_DOMINATORS
, e1
->src
, e2
->src
))
726 while (dom
->preds
->length () != 1)
728 if (dom
->preds
->length () < 1)
730 dom
= get_immediate_dominator (CDI_DOMINATORS
, dom
);
734 return (*dom
->preds
)[0];
737 /* Return the closest post-dominator with a single exit edge. In case of a
738 back-loop the back-edge is not counted. */
741 scop_detection::get_nearest_pdom_with_single_exit (basic_block dom
)
745 if (dom
->succs
->length () == 2)
747 edge e1
= (*dom
->succs
)[0];
748 edge e2
= (*dom
->succs
)[1];
749 if (dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, e1
->dest
))
751 if (dominated_by_p (CDI_POST_DOMINATORS
, e1
->dest
, e2
->dest
))
755 while (dom
->succs
->length () != 1)
757 if (dom
->succs
->length () < 1)
759 dom
= get_immediate_dominator (CDI_POST_DOMINATORS
, dom
);
763 return (*dom
->succs
)[0];
766 /* Print S to FILE. */
769 scop_detection::print_sese (FILE *file
, sese_l s
)
771 fprintf (file
, "(entry_edge (bb_%d, bb_%d), exit_edge (bb_%d, bb_%d))\n",
772 s
.entry
->src
->index
, s
.entry
->dest
->index
,
773 s
.exit
->src
->index
, s
.exit
->dest
->index
);
776 /* Merge scops at same loop depth and returns the new sese.
777 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
780 scop_detection::merge_sese (sese_l first
, sese_l second
) const
782 /* In the trivial case first/second may be NULL. */
788 DEBUG_PRINT (dp
<< "[try-merging-sese] s1: "; print_sese (dump_file
, first
);
789 dp
<< "[try-merging-sese] s2: ";
790 print_sese (dump_file
, second
));
792 /* Assumption: Both the sese's should be at the same loop depth or one scop
793 should subsume the other like in case of nested loops. */
795 /* Find the common dominators for entry,
796 and common post-dominators for the exit. */
797 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
,
798 get_entry_bb (first
),
799 get_entry_bb (second
));
801 edge entry
= get_nearest_dom_with_single_entry (dom
);
803 if (!entry
|| (entry
->flags
& EDGE_IRREDUCIBLE_LOOP
))
806 basic_block pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
,
808 get_exit_bb (second
));
809 pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
, dom
, pdom
);
811 edge exit
= get_nearest_pdom_with_single_exit (pdom
);
813 if (!exit
|| (exit
->flags
& EDGE_IRREDUCIBLE_LOOP
))
816 sese_l
combined (entry
, exit
);
818 /* FIXME: We could iterate to find the dom which dominates pdom, and pdom
819 which post-dominates dom, until it stabilizes. Also, ENTRY->SRC and
820 EXIT->DEST should be in the same loop nest. */
821 if (!dominated_by_p (CDI_DOMINATORS
, pdom
, dom
)
822 || loop_depth (entry
->src
->loop_father
)
823 != loop_depth (exit
->dest
->loop_father
))
826 /* For now we just want to bail out when exit does not post-dominate entry.
827 TODO: We might just add a basic_block at the exit to make exit
828 post-dominate entry (the entire region). */
829 if (!dominated_by_p (CDI_POST_DOMINATORS
, get_entry_bb (combined
),
830 get_exit_bb (combined
))
831 || !dominated_by_p (CDI_DOMINATORS
, get_exit_bb (combined
),
832 get_entry_bb (combined
)))
834 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
838 /* FIXME: We should remove this piece of code once
839 canonicalize_loop_closed_ssa has been removed, because that function
840 adds a BB with single exit. */
841 if (!trivially_empty_bb_p (get_exit_bb (combined
)))
843 /* Find the first empty succ (with single exit) of combined.exit. */
844 basic_block imm_succ
= combined
.exit
->dest
;
845 if (single_succ_p (imm_succ
) && trivially_empty_bb_p (imm_succ
))
846 combined
.exit
= single_succ_edge (imm_succ
);
849 DEBUG_PRINT (dp
<< "\n[scop-detection-fail] Discarding SCoP because "
850 << "no single exit (empty succ) for sese exit";
851 print_sese (dump_file
, combined
));
856 /* Analyze all the BBs in new sese. */
857 if (harmful_stmt_in_region (combined
))
860 DEBUG_PRINT (dp
<< "[merged-sese] s1: "; print_sese (dump_file
, combined
));
865 /* Build scop outer->inner if possible. */
868 scop_detection::build_scop_depth (sese_l s
, loop_p loop
)
873 DEBUG_PRINT (dp
<< "\n[Depth loop_" << loop
->num
<< "]");
874 s
= build_scop_depth (s
, loop
->inner
);
876 sese_l s2
= merge_sese (s
, get_sese (loop
));
879 /* s might be a valid scop, so return it and start analyzing from the
881 build_scop_depth (invalid_sese
, loop
->next
);
885 if (!loop_is_valid_scop (loop
, s2
))
886 return build_scop_depth (invalid_sese
, loop
->next
);
888 return build_scop_breadth (s2
, loop
);
891 /* If loop and loop->next are valid scops, try to merge them. */
894 scop_detection::build_scop_breadth (sese_l s1
, loop_p loop
)
898 DEBUG_PRINT (dp
<< "\n[Breadth loop_" << loop
->num
<< "]");
902 sese_l s2
= build_scop_depth (invalid_sese
, l
->next
);
910 sese_l combined
= merge_sese (s1
, s2
);
922 /* Returns true when Graphite can represent LOOP in SCOP.
923 FIXME: For the moment, graphite cannot be used on loops that iterate using
924 induction variables that wrap. */
927 scop_detection::can_represent_loop_1 (loop_p loop
, sese_l scop
)
930 struct tree_niter_desc niter_desc
;
932 return single_exit (loop
)
933 && !(loop_preheader_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
)
934 && number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
935 && niter_desc
.control
.no_overflow
936 && (niter
= number_of_latch_executions (loop
))
937 && !chrec_contains_undetermined (niter
)
938 && graphite_can_represent_expr (scop
, loop
, niter
);
941 /* Return true when all the loops within LOOP can be represented by
945 scop_detection::can_represent_loop (loop_p loop
, sese_l scop
)
947 if (!can_represent_loop_1 (loop
, scop
))
949 if (loop
->inner
&& !can_represent_loop (loop
->inner
, scop
))
951 if (loop
->next
&& !can_represent_loop (loop
->next
, scop
))
957 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
958 region of code that can be represented in the polyhedral model. SCOP
959 defines the region we analyse. */
962 scop_detection::loop_is_valid_scop (loop_p loop
, sese_l scop
) const
967 if (!optimize_loop_nest_for_speed_p (loop
))
969 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_"
970 << loop
->num
<< " is not on a hot path.\n");
974 if (!can_represent_loop (loop
, scop
))
976 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot represent loop_"
977 << loop
->num
<< "\n");
981 if (loop_body_is_valid_scop (loop
, scop
))
983 DEBUG_PRINT (dp
<< "[valid-scop] loop_" << loop
->num
984 << "is a valid scop.\n");
990 /* Return true when BEGIN is the preheader edge of a loop with a single exit
994 scop_detection::region_has_one_loop (sese_l s
)
996 edge begin
= s
.entry
;
998 /* Check for a single perfectly nested loop. */
999 if (begin
->dest
->loop_father
->inner
)
1002 /* Otherwise, check whether we have adjacent loops. */
1003 return begin
->dest
->loop_father
== end
->src
->loop_father
;
1006 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
1009 scop_detection::add_scop (sese_l s
)
1013 /* Do not add scops with only one loop. */
1014 if (region_has_one_loop (s
))
1016 DEBUG_PRINT (dp
<< "\n[scop-detection-fail] Discarding one loop SCoP";
1017 print_sese (dump_file
, s
));
1021 if (get_exit_bb (s
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1023 DEBUG_PRINT (dp
<< "\n[scop-detection-fail] "
1024 << "Discarding SCoP exiting to return";
1025 print_sese (dump_file
, s
));
1029 /* Remove all the scops which are subsumed by s. */
1030 remove_subscops (s
);
1032 /* Replace this with split-intersecting scops. */
1033 remove_intersecting_scops (s
);
1035 scops
.safe_push (s
);
1036 DEBUG_PRINT (dp
<< "\nAdding SCoP "; print_sese (dump_file
, s
));
1039 /* Return true when a statement in SCOP cannot be represented by Graphite.
1040 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
1041 Limit the number of bbs between adjacent loops to
1042 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
1045 scop_detection::harmful_stmt_in_region (sese_l scop
) const
1047 basic_block exit_bb
= get_exit_bb (scop
);
1048 basic_block entry_bb
= get_entry_bb (scop
);
1050 DEBUG_PRINT (dp
<< "\n[checking-harmful-bbs] ";
1051 print_sese (dump_file
, scop
));
1052 gcc_assert (dominated_by_p (CDI_DOMINATORS
, exit_bb
, entry_bb
));
1054 int depth
= bb_dom_dfs_in (CDI_DOMINATORS
, exit_bb
)
1055 - bb_dom_dfs_in (CDI_DOMINATORS
, entry_bb
);
1057 gcc_assert (depth
> 0);
1059 vec
<basic_block
> dom
1060 = get_dominated_to_depth (CDI_DOMINATORS
, entry_bb
, depth
);
1063 FOR_EACH_VEC_ELT (dom
, i
, bb
)
1065 DEBUG_PRINT (dp
<< "Visiting bb_" << bb
->index
<< "\n");
1067 /* We don't want to analyze any bb outside sese. */
1068 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb
, exit_bb
))
1071 /* Basic blocks dominated by the scop->exit are not in the scop. */
1072 if (bb
!= exit_bb
&& dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
1075 /* The basic block should not be part of an irreducible loop. */
1076 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1082 if (harmful_stmt_in_bb (scop
, bb
))
1093 /* Returns true if S1 subsumes/surrounds S2. */
1095 scop_detection::subsumes (sese_l s1
, sese_l s2
)
1097 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
1099 && dominated_by_p (CDI_POST_DOMINATORS
, s2
.exit
->dest
,
1105 /* Remove a SCoP which is subsumed by S1. */
1107 scop_detection::remove_subscops (sese_l s1
)
1111 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
1113 if (subsumes (s1
, *s2
))
1115 DEBUG_PRINT (dp
<< "\nRemoving sub-SCoP";
1116 print_sese (dump_file
, *s2
));
1117 scops
.unordered_remove (j
);
1122 /* Returns true if S1 intersects with S2. Since we already know that S1 does
1123 not subsume S2 or vice-versa, we only check for entry bbs. */
1126 scop_detection::intersects (sese_l s1
, sese_l s2
)
1128 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
1130 && !dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
1133 if ((s1
.exit
== s2
.entry
) || (s2
.exit
== s1
.entry
))
1139 /* Remove one of the scops when it intersects with any other. */
1142 scop_detection::remove_intersecting_scops (sese_l s1
)
1146 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
1148 if (intersects (s1
, *s2
))
1150 DEBUG_PRINT (dp
<< "\nRemoving intersecting SCoP";
1151 print_sese (dump_file
, *s2
); dp
<< "Intersects with:";
1152 print_sese (dump_file
, s1
));
1153 scops
.unordered_remove (j
);
1158 /* Something like "n * m" is not allowed. */
1161 scop_detection::graphite_can_represent_init (tree e
)
1163 switch (TREE_CODE (e
))
1165 case POLYNOMIAL_CHREC
:
1166 return graphite_can_represent_init (CHREC_LEFT (e
))
1167 && graphite_can_represent_init (CHREC_RIGHT (e
));
1170 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1171 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
1172 && tree_fits_shwi_p (TREE_OPERAND (e
, 1));
1174 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
1175 && tree_fits_shwi_p (TREE_OPERAND (e
, 0));
1178 case POINTER_PLUS_EXPR
:
1180 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
1181 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
1186 case NON_LVALUE_EXPR
:
1187 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
1196 /* Return true when SCEV can be represented in the polyhedral model.
1198 An expression can be represented, if it can be expressed as an
1199 affine expression. For loops (i, j) and parameters (m, n) all
1200 affine expressions are of the form:
1202 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
1204 1 i + 20 j + (-2) m + 25
1206 Something like "i * n" or "n * m" is not allowed. */
1209 scop_detection::graphite_can_represent_scev (tree scev
)
1211 if (chrec_contains_undetermined (scev
))
1214 /* We disable the handling of pointer types, because it’s currently not
1215 supported by Graphite with the ISL AST generator. SSA_NAME nodes are
1216 the only nodes, which are disabled in case they are pointers to object
1217 types, but this can be changed. */
1219 if (POINTER_TYPE_P (TREE_TYPE (scev
)) && TREE_CODE (scev
) == SSA_NAME
)
1222 switch (TREE_CODE (scev
))
1227 case NON_LVALUE_EXPR
:
1228 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0));
1231 case POINTER_PLUS_EXPR
:
1233 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1234 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1237 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
1238 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
1239 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
1240 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
1241 && graphite_can_represent_init (scev
)
1242 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1243 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1245 case POLYNOMIAL_CHREC
:
1246 /* Check for constant strides. With a non constant stride of
1247 'n' we would have a value of 'iv * n'. Also check that the
1248 initial value can represented: for example 'n * m' cannot be
1250 if (!evolution_function_right_is_integer_cst (scev
)
1251 || !graphite_can_represent_init (scev
))
1253 return graphite_can_represent_scev (CHREC_LEFT (scev
));
1259 /* Only affine functions can be represented. */
1260 if (tree_contains_chrecs (scev
, NULL
) || !scev_is_linear_expression (scev
))
1266 /* Return true when EXPR can be represented in the polyhedral model.
1268 This means an expression can be represented, if it is linear with respect to
1269 the loops and the strides are non parametric. LOOP is the place where the
1270 expr will be evaluated. SCOP defines the region we analyse. */
1273 scop_detection::graphite_can_represent_expr (sese_l scop
, loop_p loop
,
1276 tree scev
= scalar_evolution_in_region (scop
, loop
, expr
);
1277 return graphite_can_represent_scev (scev
);
1280 /* Return true if the data references of STMT can be represented by Graphite.
1281 We try to analyze the data references in a loop contained in the SCOP. */
1284 scop_detection::stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
)
1286 loop_p nest
= outermost_loop_in_sese (scop
, gimple_bb (stmt
));
1287 loop_p loop
= loop_containing_stmt (stmt
);
1288 vec
<data_reference_p
> drs
= vNULL
;
1290 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1293 data_reference_p dr
;
1294 FOR_EACH_VEC_ELT (drs
, j
, dr
)
1296 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1298 if (nb_subscripts
< 1)
1300 free_data_refs (drs
);
1304 tree ref
= DR_REF (dr
);
1306 for (int i
= nb_subscripts
- 1; i
>= 0; i
--)
1308 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
))
1309 || (TREE_CODE (ref
) != ARRAY_REF
&& TREE_CODE (ref
) != MEM_REF
1310 && TREE_CODE (ref
) != COMPONENT_REF
))
1312 free_data_refs (drs
);
1316 ref
= TREE_OPERAND (ref
, 0);
1320 free_data_refs (drs
);
1324 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1325 Calls have side-effects, except those to const or pure
1329 stmt_has_side_effects (gimple
*stmt
)
1331 if (gimple_has_volatile_ops (stmt
)
1332 || (gimple_code (stmt
) == GIMPLE_CALL
1333 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
1334 || (gimple_code (stmt
) == GIMPLE_ASM
))
1336 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1337 << "Statement has side-effects:\n";
1338 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1344 /* Returns true if STMT can be represented in polyhedral model. LABEL,
1345 simple COND stmts, pure calls, and assignments can be repesented. */
1348 scop_detection::graphite_can_represent_stmt (sese_l scop
, gimple
*stmt
,
1351 loop_p loop
= bb
->loop_father
;
1352 switch (gimple_code (stmt
))
1359 /* We can handle all binary comparisons. Inequalities are
1360 also supported as they can be represented with union of
1362 enum tree_code code
= gimple_cond_code (stmt
);
1363 if (!(code
== LT_EXPR
1368 || code
== NE_EXPR
))
1370 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1371 << "Graphite cannot handle cond stmt:\n";
1372 print_gimple_stmt (dump_file
, stmt
, 0,
1373 TDF_VOPS
| TDF_MEMSYMS
));
1377 for (unsigned i
= 0; i
< 2; ++i
)
1379 tree op
= gimple_op (stmt
, i
);
1380 if (!graphite_can_represent_expr (scop
, loop
, op
)
1381 /* We can only constrain on integer type. */
1382 || (TREE_CODE (TREE_TYPE (op
)) != INTEGER_TYPE
))
1384 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1385 << "Graphite cannot represent stmt:\n";
1386 print_gimple_stmt (dump_file
, stmt
, 0,
1387 TDF_VOPS
| TDF_MEMSYMS
));
1400 /* These nodes cut a new scope. */
1402 dp
<< "[scop-detection-fail] "
1403 << "Gimple stmt not handled in Graphite:\n";
1404 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1409 /* Return true only when STMT is simple enough for being handled by Graphite.
1410 This depends on SCOP, as the parameters are initialized relatively to
1411 this basic block, the linear functions are initialized based on the outermost
1412 loop containing STMT inside the SCOP. BB is the place where we try to
1413 evaluate the STMT. */
1416 scop_detection::stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
1417 basic_block bb
) const
1421 if (is_gimple_debug (stmt
))
1424 if (stmt_has_side_effects (stmt
))
1427 if (!stmt_has_simple_data_refs_p (scop
, stmt
))
1429 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1430 << "Graphite cannot handle data-refs in stmt:\n";
1431 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
););
1435 return graphite_can_represent_stmt (scop
, stmt
, bb
);
1438 /* Return true when BB contains a harmful operation for a scop: that
1439 can be a function call with side effects, the induction variables
1440 are not linear with respect to SCOP, etc. The current open
1441 scop should end before this statement. */
1444 scop_detection::harmful_stmt_in_bb (sese_l scop
, basic_block bb
) const
1446 gimple_stmt_iterator gsi
;
1448 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1449 if (!stmt_simple_for_scop_p (scop
, gsi_stmt (gsi
), bb
))
1455 /* Return true when the body of LOOP has statements that can be represented as a
1459 scop_detection::loop_body_is_valid_scop (loop_p loop
, sese_l scop
) const
1461 if (!loop_ivs_can_be_represented (loop
))
1463 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
1464 << "IV cannot be represented.\n");
1468 if (!loop_nest_has_data_refs (loop
))
1470 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
1471 << "does not have any data reference.\n");
1475 basic_block
*bbs
= get_loop_body (loop
);
1476 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
1478 basic_block bb
= bbs
[i
];
1480 if (harmful_stmt_in_bb (scop
, bb
))
1490 if (!loop_body_is_valid_scop (loop
, scop
))
1499 /* Returns the number of pbbs that are in loops contained in SCOP. */
1502 scop_detection::nb_pbbs_in_loops (scop_p scop
)
1508 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1509 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), scop
->scop_info
->region
))
1515 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
1516 Otherwise returns -1. */
1519 parameter_index_in_region_1 (tree name
, sese_info_p region
)
1524 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1526 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
1533 /* When the parameter NAME is in REGION, returns its index in
1534 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
1535 and returns the index of NAME. */
1538 parameter_index_in_region (tree name
, sese_info_p region
)
1542 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1544 /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
1545 if (TREE_CODE (TREE_TYPE (name
)) != INTEGER_TYPE
)
1548 if (!invariant_in_sese_p_rec (name
, region
->region
, NULL
))
1551 i
= parameter_index_in_region_1 (name
, region
);
1555 i
= region
->params
.length ();
1556 region
->params
.safe_push (name
);
1560 /* In the context of sese S, scan the expression E and translate it to
1561 a linear expression C. When parsing a symbolic multiplication, K
1562 represents the constant multiplier of an expression containing
1566 scan_tree_for_params (sese_info_p s
, tree e
)
1568 if (e
== chrec_dont_know
)
1571 switch (TREE_CODE (e
))
1573 case POLYNOMIAL_CHREC
:
1574 scan_tree_for_params (s
, CHREC_LEFT (e
));
1578 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1579 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1581 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1585 case POINTER_PLUS_EXPR
:
1587 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1588 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1594 case NON_LVALUE_EXPR
:
1595 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1599 parameter_index_in_region (e
, s
);
1615 /* Find parameters with respect to REGION in BB. We are looking in memory
1616 access functions, conditions and loop bounds. */
1619 find_params_in_bb (sese_info_p region
, gimple_poly_bb_p gbb
)
1621 /* Find parameters in the access functions of data references. */
1623 data_reference_p dr
;
1624 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
1625 for (unsigned j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
1626 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
1628 /* Find parameters in conditional statements. */
1630 loop_p loop
= GBB_BB (gbb
)->loop_father
;
1631 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1633 tree lhs
= scalar_evolution_in_region (region
->region
, loop
,
1634 gimple_cond_lhs (stmt
));
1635 tree rhs
= scalar_evolution_in_region (region
->region
, loop
,
1636 gimple_cond_rhs (stmt
));
1638 scan_tree_for_params (region
, lhs
);
1639 scan_tree_for_params (region
, rhs
);
1643 /* Record the parameters used in the SCOP. A variable is a parameter
1644 in a scop if it does not vary during the execution of that scop. */
1647 find_scop_parameters (scop_p scop
)
1650 sese_info_p region
= scop
->scop_info
;
1653 /* Find the parameters used in the loop bounds. */
1654 FOR_EACH_VEC_ELT (region
->loop_nest
, i
, loop
)
1656 tree nb_iters
= number_of_latch_executions (loop
);
1658 if (!chrec_contains_symbols (nb_iters
))
1661 nb_iters
= scalar_evolution_in_region (region
->region
, loop
, nb_iters
);
1662 scan_tree_for_params (region
, nb_iters
);
1665 /* Find the parameters used in data accesses. */
1667 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1668 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1670 int nbp
= sese_nb_params (region
);
1671 scop_set_nb_params (scop
, nbp
);
1674 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1677 build_cross_bb_scalars_def (scop_p scop
, tree def
, basic_block def_bb
,
1681 if (!is_gimple_reg (def
))
1684 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1685 generated out of the induction variables. */
1686 if (scev_analyzable_p (def
, scop
->scop_info
->region
))
1690 imm_use_iterator imm_iter
;
1691 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1692 if (def_bb
!= gimple_bb (use_stmt
) && !is_gimple_debug (use_stmt
))
1694 writes
->safe_push (def
);
1695 DEBUG_PRINT (dp
<< "Adding scalar write:\n";
1696 print_generic_expr (dump_file
, def
, 0);
1697 dp
<< "From stmt:\n";
1698 print_gimple_stmt (dump_file
,
1699 SSA_NAME_DEF_STMT (def
), 0, 0));
1700 /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
1701 before all the uses have been visited. */
1702 BREAK_FROM_IMM_USE_STMT (imm_iter
);
1706 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1709 build_cross_bb_scalars_use (scop_p scop
, tree use
, gimple
*use_stmt
,
1710 vec
<scalar_use
> *reads
)
1713 if (!is_gimple_reg (use
))
1716 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1717 generated out of the induction variables. */
1718 if (scev_analyzable_p (use
, scop
->scop_info
->region
))
1721 gimple
*def_stmt
= SSA_NAME_DEF_STMT (use
);
1722 if (gimple_bb (def_stmt
) != gimple_bb (use_stmt
))
1724 DEBUG_PRINT (dp
<< "\nAdding scalar read:";
1725 print_generic_expr (dump_file
, use
, 0);
1726 dp
<< "\nFrom stmt:";
1727 print_gimple_stmt (dump_file
, use_stmt
, 0, 0));
1728 reads
->safe_push (std::make_pair (use_stmt
, use
));
1732 /* Record all scalar variables that are defined and used in different BBs of the
1736 graphite_find_cross_bb_scalar_vars (scop_p scop
, gimple
*stmt
,
1737 vec
<scalar_use
> *reads
, vec
<tree
> *writes
)
1741 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
1742 def
= gimple_assign_lhs (stmt
);
1743 else if (gimple_code (stmt
) == GIMPLE_CALL
)
1744 def
= gimple_call_lhs (stmt
);
1745 else if (gimple_code (stmt
) == GIMPLE_PHI
)
1746 def
= gimple_phi_result (stmt
);
1751 build_cross_bb_scalars_def (scop
, def
, gimple_bb (stmt
), writes
);
1754 use_operand_p use_p
;
1755 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1757 tree use
= USE_FROM_PTR (use_p
);
1758 build_cross_bb_scalars_use (scop
, use
, stmt
, reads
);
1762 /* Generates a polyhedral black box only if the bb contains interesting
1765 static gimple_poly_bb_p
1766 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
1768 vec
<data_reference_p
> drs
= vNULL
;
1769 vec
<tree
> writes
= vNULL
;
1770 vec
<scalar_use
> reads
= vNULL
;
1772 sese_l region
= scop
->scop_info
->region
;
1773 loop_p nest
= outermost_loop_in_sese (region
, bb
);
1775 loop_p loop
= bb
->loop_father
;
1776 if (!loop_in_sese_p (loop
, region
))
1779 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1782 gimple
*stmt
= gsi_stmt (gsi
);
1783 if (is_gimple_debug (stmt
))
1786 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1787 graphite_find_cross_bb_scalar_vars (scop
, stmt
, &reads
, &writes
);
1790 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1792 if (!virtual_operand_p (gimple_phi_result (psi
.phi ())))
1793 graphite_find_cross_bb_scalar_vars (scop
, psi
.phi (), &reads
, &writes
);
1795 if (drs
.is_empty () && writes
.is_empty () && reads
.is_empty ())
1798 return new_gimple_poly_bb (bb
, drs
, reads
, writes
);
1801 /* Compute alias-sets for all data references in DRS. */
1804 build_alias_set (scop_p scop
)
1806 int num_vertices
= scop
->drs
.length ();
1807 struct graph
*g
= new_graph (num_vertices
);
1812 FOR_EACH_VEC_ELT (scop
->drs
, i
, dr1
)
1813 for (j
= i
+1; scop
->drs
.iterate (j
, &dr2
); j
++)
1814 if (dr_may_alias_p (dr1
->dr
, dr2
->dr
, true))
1820 all_vertices
= XNEWVEC (int, num_vertices
);
1821 for (i
= 0; i
< num_vertices
; i
++)
1822 all_vertices
[i
] = i
;
1824 graphds_dfs (g
, all_vertices
, num_vertices
, NULL
, true, NULL
);
1825 free (all_vertices
);
1827 for (i
= 0; i
< g
->n_vertices
; i
++)
1828 scop
->drs
[i
].alias_set
= g
->vertices
[i
].component
+ 1;
1833 /* Gather BBs and conditions for a SCOP. */
1834 class gather_bbs
: public dom_walker
1837 gather_bbs (cdi_direction
, scop_p
);
1839 virtual void before_dom_children (basic_block
);
1840 virtual void after_dom_children (basic_block
);
1843 auto_vec
<gimple
*, 3> conditions
, cases
;
1847 gather_bbs::gather_bbs (cdi_direction direction
, scop_p scop
)
1848 : dom_walker (direction
), scop (scop
)
1852 /* Call-back for dom_walk executed before visiting the dominated
1856 gather_bbs::before_dom_children (basic_block bb
)
1858 if (!bb_in_sese_p (bb
, scop
->scop_info
->region
))
1861 gcond
*stmt
= single_pred_cond_non_loop_exit (bb
);
1865 edge e
= single_pred_edge (bb
);
1867 conditions
.safe_push (stmt
);
1869 if (e
->flags
& EDGE_TRUE_VALUE
)
1870 cases
.safe_push (stmt
);
1872 cases
.safe_push (NULL
);
1875 scop
->scop_info
->bbs
.safe_push (bb
);
1877 gimple_poly_bb_p gbb
= try_generate_gimple_bb (scop
, bb
);
1881 GBB_CONDITIONS (gbb
) = conditions
.copy ();
1882 GBB_CONDITION_CASES (gbb
) = cases
.copy ();
1884 poly_bb_p pbb
= new_poly_bb (scop
, gbb
);
1885 scop
->pbbs
.safe_push (pbb
);
1888 data_reference_p dr
;
1889 FOR_EACH_VEC_ELT (gbb
->data_refs
, i
, dr
)
1890 scop
->drs
.safe_push (dr_info (dr
, pbb
));
1893 /* Call-back for dom_walk executed after visiting the dominated
1897 gather_bbs::after_dom_children (basic_block bb
)
1899 if (!bb_in_sese_p (bb
, scop
->scop_info
->region
))
1902 if (single_pred_cond_non_loop_exit (bb
))
1909 /* Find Static Control Parts (SCoP) in the current function and pushes
1913 build_scops (vec
<scop_p
> *scops
)
1916 dp
.set_dump_file (dump_file
);
1918 canonicalize_loop_closed_ssa_form ();
1921 sb
.build_scop_depth (scop_detection::invalid_sese
, current_loops
->tree_root
);
1923 /* Now create scops from the lightweight SESEs. */
1924 vec
<sese_l
> scops_l
= sb
.get_scops ();
1927 FOR_EACH_VEC_ELT (scops_l
, i
, s
)
1929 scop_p scop
= new_scop (s
->entry
, s
->exit
);
1931 /* Record all basic blocks and their conditions in REGION. */
1932 gather_bbs (CDI_DOMINATORS
, scop
).walk (cfun
->cfg
->x_entry_block_ptr
);
1934 build_alias_set (scop
);
1936 /* Do not optimize a scop containing only PBBs that do not belong
1938 if (sb
.nb_pbbs_in_loops (scop
) == 0)
1940 DEBUG_PRINT (dp
<< "[scop-detection-fail] no data references.\n");
1945 unsigned max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
1946 if (scop
->drs
.length () >= max_arrays
)
1948 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many data references: "
1949 << scop
->drs
.length ()
1950 << " is larger than --param graphite-max-arrays-per-scop="
1951 << max_arrays
<< ".\n");
1956 build_sese_loop_nests (scop
->scop_info
);
1958 find_scop_parameters (scop
);
1959 graphite_dim_t max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
1961 if (scop_nb_params (scop
) > max_dim
)
1963 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many parameters: "
1964 << scop_nb_params (scop
)
1965 << " larger than --param graphite-max-nb-scop-params="
1966 << max_dim
<< ".\n");
1971 scops
->safe_push (scop
);
1974 DEBUG_PRINT (dp
<< "number of SCoPs: " << (scops
? scops
->length () : 0););
1977 #endif /* HAVE_isl */