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/>. */
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"
60 set_dump_file (FILE *f
)
66 friend debug_printer
&
67 operator<< (debug_printer
&output
, int i
)
69 fprintf (output
.dump_file
, "%d", i
);
72 friend debug_printer
&
73 operator<< (debug_printer
&output
, const char *s
)
75 fprintf (output
.dump_file
, "%s", s
);
80 #define DEBUG_PRINT(args) do \
82 if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \
85 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
86 different colors. If there are not enough colors, paint the
87 remaining SCoPs in gray.
90 - "*" after the node number denotes the entry of a SCoP,
91 - "#" after the node number denotes the exit of a SCoP,
92 - "()" around the node number denotes the entry or the
93 exit nodes of the SCOP. These are not part of SCoP. */
96 dot_all_sese (FILE *file
, vec
<sese_l
>& scops
)
98 /* Disable debugging while printing graph. */
99 int tmp_dump_flags
= dump_flags
;
102 fprintf (file
, "digraph all {\n");
105 FOR_ALL_BB_FN (bb
, cfun
)
107 int part_of_scop
= false;
109 /* Use HTML for every bb label. So we are able to print bbs
110 which are part of two different SCoPs, with two different
111 background colors. */
112 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
114 fprintf (file
, "CELLSPACING=\"0\">\n");
116 /* Select color for SCoP. */
119 FOR_EACH_VEC_ELT (scops
, i
, region
)
121 bool sese_in_region
= bb_in_sese_p (bb
, *region
);
122 if (sese_in_region
|| (region
->exit
->dest
== bb
)
123 || (region
->entry
->dest
== bb
))
183 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
187 fprintf (file
, " (");
189 if (bb
== region
->entry
->dest
&& bb
== region
->exit
->dest
)
190 fprintf (file
, " %d*# ", bb
->index
);
191 else if (bb
== region
->entry
->dest
)
192 fprintf (file
, " %d* ", bb
->index
);
193 else if (bb
== region
->exit
->dest
)
194 fprintf (file
, " %d# ", bb
->index
);
196 fprintf (file
, " %d ", bb
->index
);
198 fprintf (file
, "{lp_%d}", bb
->loop_father
->num
);
203 fprintf (file
, "</TD></TR>\n");
210 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
211 fprintf (file
, " %d {lp_%d} </TD></TR>\n", bb
->index
,
212 bb
->loop_father
->num
);
214 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
217 FOR_ALL_BB_FN (bb
, cfun
)
221 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
222 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
225 fputs ("}\n\n", file
);
227 /* Enable debugging again. */
228 dump_flags
= tmp_dump_flags
;
231 /* Display SCoP on stderr. */
234 dot_sese (sese_l
& scop
)
240 scops
.safe_push (scop
);
242 dot_all_sese (stderr
, scops
);
252 dot_all_sese (stderr
, scops
);
256 /* Return true if BB is empty, contains only DEBUG_INSNs. */
259 trivially_empty_bb_p (basic_block bb
)
261 gimple_stmt_iterator gsi
;
263 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
264 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_DEBUG
)
270 /* Returns true when P1 and P2 are close phis with the same
274 same_close_phi_node (gphi
*p1
, gphi
*p2
)
276 return operand_equal_p (gimple_phi_arg_def (p1
, 0),
277 gimple_phi_arg_def (p2
, 0), 0);
280 static void make_close_phi_nodes_unique (basic_block bb
);
282 /* Remove the close phi node at GSI and replace its rhs with the rhs
286 remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
)
290 imm_use_iterator imm_iter
;
291 tree res
= gimple_phi_result (phi
);
292 tree def
= gimple_phi_result (gsi
->phi ());
294 gcc_assert (same_close_phi_node (phi
, gsi
->phi ()));
296 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
298 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
299 SET_USE (use_p
, res
);
301 update_stmt (use_stmt
);
303 /* It is possible that we just created a duplicate close-phi
304 for an already-processed containing loop. Check for this
305 case and clean it up. */
306 if (gimple_code (use_stmt
) == GIMPLE_PHI
307 && gimple_phi_num_args (use_stmt
) == 1)
308 make_close_phi_nodes_unique (gimple_bb (use_stmt
));
311 remove_phi_node (gsi
, true);
314 /* Removes all the close phi duplicates from BB. */
317 make_close_phi_nodes_unique (basic_block bb
)
321 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
323 gphi_iterator gsi
= psi
;
324 gphi
*phi
= psi
.phi ();
326 /* At this point, PHI should be a close phi in normal form. */
327 gcc_assert (gimple_phi_num_args (phi
) == 1);
329 /* Iterate over the next phis and remove duplicates. */
331 while (!gsi_end_p (gsi
))
332 if (same_close_phi_node (phi
, gsi
.phi ()))
333 remove_duplicate_close_phi (phi
, &gsi
);
339 /* Transforms LOOP to the canonical loop closed SSA form. */
342 canonicalize_loop_closed_ssa (loop_p loop
)
344 edge e
= single_exit (loop
);
347 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
352 if (single_pred_p (bb
))
354 e
= split_block_after_labels (bb
);
355 DEBUG_PRINT (dp
<< "Splitting bb_" << bb
->index
<< ".\n");
356 make_close_phi_nodes_unique (e
->src
);
361 basic_block close
= split_edge (e
);
363 e
= single_succ_edge (close
);
364 DEBUG_PRINT (dp
<< "Splitting edge (" << e
->src
->index
<< ","
365 << e
->dest
->index
<< ")\n");
367 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
369 gphi
*phi
= psi
.phi ();
372 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
373 if (gimple_phi_arg_edge (phi
, i
) == e
)
375 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
379 if (TREE_CODE (arg
) != SSA_NAME
)
382 close_phi
= create_phi_node (NULL_TREE
, close
);
383 res
= create_new_def_for (arg
, close_phi
,
384 gimple_phi_result_ptr (close_phi
));
385 add_phi_arg (close_phi
, arg
,
386 gimple_phi_arg_edge (close_phi
, 0),
388 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
389 replace_exp (use_p
, res
);
394 make_close_phi_nodes_unique (close
);
397 /* The code above does not properly handle changes in the post dominance
398 information (yet). */
399 recompute_all_dominators ();
402 /* Converts the current loop closed SSA form to a canonical form
403 expected by the Graphite code generation.
405 The loop closed SSA form has the following invariant: a variable
406 defined in a loop that is used outside the loop appears only in the
407 phi nodes in the destination of the loop exit. These phi nodes are
408 called close phi nodes.
410 The canonical loop closed SSA form contains the extra invariants:
412 - when the loop contains only one exit, the close phi nodes contain
413 only one argument. That implies that the basic block that contains
414 the close phi nodes has only one predecessor, that is a basic block
417 - the basic block containing the close phi nodes does not contain
420 - there exist only one phi node per definition in the loop.
424 canonicalize_loop_closed_ssa_form (void)
426 checking_verify_loop_closed_ssa (true);
429 FOR_EACH_LOOP (loop
, 0)
430 canonicalize_loop_closed_ssa (loop
);
432 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
433 update_ssa (TODO_update_ssa
);
435 checking_verify_loop_closed_ssa (true);
438 /* Can all ivs be represented by a signed integer?
439 As ISL might generate negative values in its expressions, signed loop ivs
440 are required in the backend. */
443 loop_ivs_can_be_represented (loop_p loop
)
445 unsigned type_long_long
= TYPE_PRECISION (long_long_integer_type_node
);
446 for (gphi_iterator psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
);
449 gphi
*phi
= psi
.phi ();
450 tree res
= PHI_RESULT (phi
);
451 tree type
= TREE_TYPE (res
);
453 if (TYPE_UNSIGNED (type
) && TYPE_PRECISION (type
) >= type_long_long
)
460 /* Returns a COND_EXPR statement when BB has a single predecessor, the
461 edge between BB and its predecessor is not a loop exit edge, and
462 the last statement of the single predecessor is a COND_EXPR. */
465 single_pred_cond_non_loop_exit (basic_block bb
)
467 if (single_pred_p (bb
))
469 edge e
= single_pred_edge (bb
);
470 basic_block pred
= e
->src
;
473 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
476 stmt
= last_stmt (pred
);
478 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
479 return as_a
<gcond
*> (stmt
);
488 /* Build the maximal scop containing LOOPs and add it to SCOPS. */
493 scop_detection () : scops (vNULL
) {}
500 /* A marker for invalid sese_l. */
501 static sese_l invalid_sese
;
503 /* Return the SCOPS in this SCOP_DETECTION. */
511 /* Return an sese_l around the LOOP. */
513 sese_l
get_sese (loop_p loop
);
515 /* Return the closest dominator with a single entry edge. In case of a
516 back-loop the back-edge is not counted. */
518 static edge
get_nearest_dom_with_single_entry (basic_block dom
);
520 /* Return the closest post-dominator with a single exit edge. In case of a
521 back-loop the back-edge is not counted. */
523 static edge
get_nearest_pdom_with_single_exit (basic_block dom
);
526 /* Pretty printers. */
528 static void print_edge (FILE *file
, const_edge e
)
530 fprintf (file
, "edge (bb_%d, bb_%d)", e
->src
->index
, e
->dest
->index
);
533 static void print_sese (FILE *file
, sese_l s
)
535 fprintf (file
, "(entry_"); print_edge (file
, s
.entry
);
536 fprintf (file
, ", exit_"); print_edge (file
, s
.exit
);
537 fprintf (file
, ")\n");
540 /* Merge scops at same loop depth and returns the new sese.
541 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
543 sese_l
merge_sese (sese_l first
, sese_l second
) const;
545 /* Build scop outer->inner if possible. */
547 sese_l
build_scop_depth (sese_l s
, loop_p loop
);
549 /* If loop and loop->next are valid scops, try to merge them. */
551 sese_l
build_scop_breadth (sese_l s1
, loop_p loop
);
553 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
554 region of code that can be represented in the polyhedral model. SCOP
555 defines the region we analyse. */
557 bool loop_is_valid_scop (loop_p loop
, sese_l scop
) const;
559 /* Return true when BEGIN is the preheader edge of a loop with a single exit
562 static bool region_has_one_loop (sese_l s
);
564 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
566 void add_scop (sese_l s
);
568 /* Returns true if S1 subsumes/surrounds S2. */
569 static bool subsumes (sese_l s1
, sese_l s2
);
571 /* Remove a SCoP which is subsumed by S1. */
572 void remove_subscops (sese_l s1
);
574 /* Returns true if S1 intersects with S2. Since we already know that S1 does
575 not subsume S2 or vice-versa, we only check for entry bbs. */
577 static bool intersects (sese_l s1
, sese_l s2
);
579 /* Remove one of the scops when it intersects with any other. */
581 void remove_intersecting_scops (sese_l s1
);
583 /* Return true when the body of LOOP has statements that can be represented
586 bool loop_body_is_valid_scop (loop_p loop
, sese_l scop
) const;
588 /* Return true when BB contains a harmful operation for a scop: that
589 can be a function call with side effects, the induction variables
590 are not linear with respect to SCOP, etc. The current open
591 scop should end before this statement. */
593 bool harmful_stmt_in_bb (sese_l scop
, basic_block bb
) const;
595 /* Return true when a statement in SCOP cannot be represented by Graphite.
596 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
597 Limit the number of bbs between adjacent loops to
598 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
600 bool harmful_stmt_in_region (sese_l scop
) const;
602 /* Return true only when STMT is simple enough for being handled by Graphite.
603 This depends on SCOP, as the parameters are initialized relatively to
604 this basic block, the linear functions are initialized based on the
605 outermost loop containing STMT inside the SCOP. BB is the place where we
606 try to evaluate the STMT. */
608 bool stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
609 basic_block bb
) const;
611 /* Something like "n * m" is not allowed. */
613 static bool graphite_can_represent_init (tree e
);
615 /* Return true when SCEV can be represented in the polyhedral model.
617 An expression can be represented, if it can be expressed as an
618 affine expression. For loops (i, j) and parameters (m, n) all
619 affine expressions are of the form:
621 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
623 1 i + 20 j + (-2) m + 25
625 Something like "i * n" or "n * m" is not allowed. */
627 static bool graphite_can_represent_scev (tree scev
);
629 /* Return true when EXPR can be represented in the polyhedral model.
631 This means an expression can be represented, if it is linear with respect
632 to the loops and the strides are non parametric. LOOP is the place where
633 the expr will be evaluated. SCOP defines the region we analyse. */
635 static bool graphite_can_represent_expr (sese_l scop
, loop_p loop
,
638 /* Return true if the data references of STMT can be represented by Graphite.
639 We try to analyze the data references in a loop contained in the SCOP. */
641 static bool stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
);
643 /* Remove the close phi node at GSI and replace its rhs with the rhs
646 static void remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
);
648 /* Returns true when Graphite can represent LOOP in SCOP.
649 FIXME: For the moment, graphite cannot be used on loops that iterate using
650 induction variables that wrap. */
652 static bool can_represent_loop_1 (loop_p loop
, sese_l scop
);
654 /* Return true when all the loops within LOOP can be represented by
657 static bool can_represent_loop (loop_p loop
, sese_l scop
);
659 /* Returns the number of pbbs that are in loops contained in SCOP. */
661 static int nb_pbbs_in_loops (scop_p scop
);
663 static bool graphite_can_represent_stmt (sese_l
, gimple
*, basic_block
);
669 sese_l
scop_detection::invalid_sese (NULL
, NULL
);
671 /* Return an sese_l around the LOOP. */
674 scop_detection::get_sese (loop_p loop
)
679 if (!loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
))
681 edge scop_end
= single_exit (loop
);
684 edge scop_begin
= loop_preheader_edge (loop
);
685 sese_l
s (scop_begin
, scop_end
);
689 /* Return the closest dominator with a single entry edge. */
692 scop_detection::get_nearest_dom_with_single_entry (basic_block dom
)
696 /* If e1->src dominates e2->src then e1->src will also dominate dom. */
697 if (dom
->preds
->length () == 2)
699 edge e1
= (*dom
->preds
)[0];
700 edge e2
= (*dom
->preds
)[1];
701 loop_p l
= dom
->loop_father
;
702 loop_p l1
= e1
->src
->loop_father
;
703 loop_p l2
= e2
->src
->loop_father
;
705 && dominated_by_p (CDI_DOMINATORS
, e2
->src
, e1
->src
))
708 && dominated_by_p (CDI_DOMINATORS
, e1
->src
, e2
->src
))
712 while (dom
->preds
->length () != 1)
714 if (dom
->preds
->length () < 1)
716 dom
= get_immediate_dominator (CDI_DOMINATORS
, dom
);
720 return (*dom
->preds
)[0];
723 /* Return the closest post-dominator with a single exit edge. In case of a
724 back-loop the back-edge is not counted. */
727 scop_detection::get_nearest_pdom_with_single_exit (basic_block pdom
)
731 if (pdom
->succs
->length () == 2)
733 edge e1
= (*pdom
->succs
)[0];
734 edge e2
= (*pdom
->succs
)[1];
735 loop_p l
= pdom
->loop_father
;
736 loop_p l1
= e1
->dest
->loop_father
;
737 loop_p l2
= e2
->dest
->loop_father
;
739 && dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, e1
->dest
))
742 && dominated_by_p (CDI_POST_DOMINATORS
, e1
->dest
, e2
->dest
))
746 while (pdom
->succs
->length () != 1)
748 if (pdom
->succs
->length () < 1)
750 pdom
= get_immediate_dominator (CDI_POST_DOMINATORS
, pdom
);
755 return (*pdom
->succs
)[0];
758 /* Merge scops at same loop depth and returns the new sese.
759 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
762 scop_detection::merge_sese (sese_l first
, sese_l second
) const
764 /* In the trivial case first/second may be NULL. */
770 DEBUG_PRINT (dp
<< "[try-merging-sese] s1: "; print_sese (dump_file
, first
);
771 dp
<< "[try-merging-sese] s2: ";
772 print_sese (dump_file
, second
));
774 /* Assumption: Both the sese's should be at the same loop depth or one scop
775 should subsume the other like in case of nested loops. */
777 /* Find the common dominators for entry,
778 and common post-dominators for the exit. */
779 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
,
780 get_entry_bb (first
),
781 get_entry_bb (second
));
783 edge entry
= get_nearest_dom_with_single_entry (dom
);
785 if (!entry
|| (entry
->flags
& EDGE_IRREDUCIBLE_LOOP
))
788 basic_block pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
,
790 get_exit_bb (second
));
791 pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
, dom
, pdom
);
793 edge exit
= get_nearest_pdom_with_single_exit (pdom
);
795 if (!exit
|| (exit
->flags
& EDGE_IRREDUCIBLE_LOOP
))
798 sese_l
combined (entry
, exit
);
800 DEBUG_PRINT (dp
<< "checking combined sese: ";
801 print_sese (dump_file
, combined
));
803 /* FIXME: We could iterate to find the dom which dominates pdom, and pdom
804 which post-dominates dom, until it stabilizes. Also, ENTRY->SRC and
805 EXIT->DEST should be in the same loop nest. */
806 if (!dominated_by_p (CDI_DOMINATORS
, pdom
, dom
)
807 || loop_depth (entry
->src
->loop_father
)
808 != loop_depth (exit
->dest
->loop_father
))
811 /* For now we just want to bail out when exit does not post-dominate entry.
812 TODO: We might just add a basic_block at the exit to make exit
813 post-dominate entry (the entire region). */
814 if (!dominated_by_p (CDI_POST_DOMINATORS
, get_entry_bb (combined
),
815 get_exit_bb (combined
))
816 || !dominated_by_p (CDI_DOMINATORS
, get_exit_bb (combined
),
817 get_entry_bb (combined
)))
819 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
823 /* FIXME: We should remove this piece of code once
824 canonicalize_loop_closed_ssa has been removed, because that function
825 adds a BB with single exit. */
826 if (!trivially_empty_bb_p (get_exit_bb (combined
)))
828 /* Find the first empty succ (with single exit) of combined.exit. */
829 basic_block imm_succ
= combined
.exit
->dest
;
830 if (single_succ_p (imm_succ
) && trivially_empty_bb_p (imm_succ
))
831 combined
.exit
= single_succ_edge (imm_succ
);
834 DEBUG_PRINT (dp
<< "[scop-detection-fail] Discarding SCoP because "
835 << "no single exit (empty succ) for sese exit";
836 print_sese (dump_file
, combined
));
841 /* Analyze all the BBs in new sese. */
842 if (harmful_stmt_in_region (combined
))
845 DEBUG_PRINT (dp
<< "[merged-sese] s1: "; print_sese (dump_file
, combined
));
850 /* Build scop outer->inner if possible. */
853 scop_detection::build_scop_depth (sese_l s
, loop_p loop
)
858 DEBUG_PRINT (dp
<< "[Depth loop_" << loop
->num
<< "]\n");
859 s
= build_scop_depth (s
, loop
->inner
);
861 sese_l s2
= merge_sese (s
, get_sese (loop
));
864 /* s might be a valid scop, so return it and start analyzing from the
866 build_scop_depth (invalid_sese
, loop
->next
);
870 if (!loop_is_valid_scop (loop
, s2
))
871 return build_scop_depth (invalid_sese
, loop
->next
);
873 return build_scop_breadth (s2
, loop
);
876 /* If loop and loop->next are valid scops, try to merge them. */
879 scop_detection::build_scop_breadth (sese_l s1
, loop_p loop
)
883 DEBUG_PRINT (dp
<< "[Breadth loop_" << loop
->num
<< "]\n");
887 sese_l s2
= build_scop_depth (invalid_sese
, l
->next
);
895 sese_l combined
= merge_sese (s1
, s2
);
907 /* Returns true when Graphite can represent LOOP in SCOP.
908 FIXME: For the moment, graphite cannot be used on loops that iterate using
909 induction variables that wrap. */
912 scop_detection::can_represent_loop_1 (loop_p loop
, sese_l scop
)
915 struct tree_niter_desc niter_desc
;
917 return single_exit (loop
)
918 && !(loop_preheader_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
)
919 && number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
920 && niter_desc
.control
.no_overflow
921 && (niter
= number_of_latch_executions (loop
))
922 && !chrec_contains_undetermined (niter
)
923 && graphite_can_represent_expr (scop
, loop
, niter
);
926 /* Return true when all the loops within LOOP can be represented by
930 scop_detection::can_represent_loop (loop_p loop
, sese_l scop
)
932 if (!can_represent_loop_1 (loop
, scop
))
934 if (loop
->inner
&& !can_represent_loop (loop
->inner
, scop
))
936 if (loop
->next
&& !can_represent_loop (loop
->next
, scop
))
942 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
943 region of code that can be represented in the polyhedral model. SCOP
944 defines the region we analyse. */
947 scop_detection::loop_is_valid_scop (loop_p loop
, sese_l scop
) const
952 if (!optimize_loop_nest_for_speed_p (loop
))
954 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_"
955 << loop
->num
<< " is not on a hot path.\n");
959 if (!can_represent_loop (loop
, scop
))
961 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot represent loop_"
962 << loop
->num
<< "\n");
966 if (loop_body_is_valid_scop (loop
, scop
))
968 DEBUG_PRINT (dp
<< "[valid-scop] loop_" << loop
->num
969 << " is a valid scop.\n");
975 /* Return true when BEGIN is the preheader edge of a loop with a single exit
979 scop_detection::region_has_one_loop (sese_l s
)
981 edge begin
= s
.entry
;
983 /* Check for a single perfectly nested loop. */
984 if (begin
->dest
->loop_father
->inner
)
987 /* Otherwise, check whether we have adjacent loops. */
988 return begin
->dest
->loop_father
== end
->src
->loop_father
;
991 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
994 scop_detection::add_scop (sese_l s
)
998 /* Do not add scops with only one loop. */
999 if (region_has_one_loop (s
))
1001 DEBUG_PRINT (dp
<< "[scop-detection-fail] Discarding one loop SCoP.\n";
1002 print_sese (dump_file
, s
));
1006 if (get_exit_bb (s
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1008 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1009 << "Discarding SCoP exiting to return.";
1010 print_sese (dump_file
, s
));
1014 /* Remove all the scops which are subsumed by s. */
1015 remove_subscops (s
);
1017 /* Replace this with split-intersecting scops. */
1018 remove_intersecting_scops (s
);
1020 scops
.safe_push (s
);
1021 DEBUG_PRINT (dp
<< "Adding SCoP "; print_sese (dump_file
, s
));
1024 /* Return true when a statement in SCOP cannot be represented by Graphite.
1025 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
1026 Limit the number of bbs between adjacent loops to
1027 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
1030 scop_detection::harmful_stmt_in_region (sese_l scop
) const
1032 basic_block exit_bb
= get_exit_bb (scop
);
1033 basic_block entry_bb
= get_entry_bb (scop
);
1035 DEBUG_PRINT (dp
<< "[checking-harmful-bbs] ";
1036 print_sese (dump_file
, scop
));
1037 gcc_assert (dominated_by_p (CDI_DOMINATORS
, exit_bb
, entry_bb
));
1039 int depth
= bb_dom_dfs_in (CDI_DOMINATORS
, exit_bb
)
1040 - bb_dom_dfs_in (CDI_DOMINATORS
, entry_bb
);
1042 gcc_assert (depth
> 0);
1044 vec
<basic_block
> dom
1045 = get_dominated_to_depth (CDI_DOMINATORS
, entry_bb
, depth
);
1048 FOR_EACH_VEC_ELT (dom
, i
, bb
)
1050 DEBUG_PRINT (dp
<< "Visiting bb_" << bb
->index
<< "\n");
1052 /* We don't want to analyze any bb outside sese. */
1053 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb
, exit_bb
))
1056 /* Basic blocks dominated by the scop->exit are not in the scop. */
1057 if (bb
!= exit_bb
&& dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
1060 /* The basic block should not be part of an irreducible loop. */
1061 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1067 if (harmful_stmt_in_bb (scop
, bb
))
1078 /* Returns true if S1 subsumes/surrounds S2. */
1080 scop_detection::subsumes (sese_l s1
, sese_l s2
)
1082 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
1084 && dominated_by_p (CDI_POST_DOMINATORS
, s2
.exit
->dest
,
1090 /* Remove a SCoP which is subsumed by S1. */
1092 scop_detection::remove_subscops (sese_l s1
)
1096 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
1098 if (subsumes (s1
, *s2
))
1100 DEBUG_PRINT (dp
<< "Removing sub-SCoP";
1101 print_sese (dump_file
, *s2
));
1102 scops
.unordered_remove (j
);
1107 /* Returns true if S1 intersects with S2. Since we already know that S1 does
1108 not subsume S2 or vice-versa, we only check for entry bbs. */
1111 scop_detection::intersects (sese_l s1
, sese_l s2
)
1113 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
1115 && !dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
1118 if ((s1
.exit
== s2
.entry
) || (s2
.exit
== s1
.entry
))
1124 /* Remove one of the scops when it intersects with any other. */
1127 scop_detection::remove_intersecting_scops (sese_l s1
)
1131 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
1133 if (intersects (s1
, *s2
))
1135 DEBUG_PRINT (dp
<< "Removing intersecting SCoP";
1136 print_sese (dump_file
, *s2
);
1137 dp
<< "Intersects with:";
1138 print_sese (dump_file
, s1
));
1139 scops
.unordered_remove (j
);
1144 /* Something like "n * m" is not allowed. */
1147 scop_detection::graphite_can_represent_init (tree e
)
1149 switch (TREE_CODE (e
))
1151 case POLYNOMIAL_CHREC
:
1152 return graphite_can_represent_init (CHREC_LEFT (e
))
1153 && graphite_can_represent_init (CHREC_RIGHT (e
));
1156 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1157 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
1158 && tree_fits_shwi_p (TREE_OPERAND (e
, 1));
1160 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
1161 && tree_fits_shwi_p (TREE_OPERAND (e
, 0));
1164 case POINTER_PLUS_EXPR
:
1166 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
1167 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
1172 case NON_LVALUE_EXPR
:
1173 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
1182 /* Return true when SCEV can be represented in the polyhedral model.
1184 An expression can be represented, if it can be expressed as an
1185 affine expression. For loops (i, j) and parameters (m, n) all
1186 affine expressions are of the form:
1188 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
1190 1 i + 20 j + (-2) m + 25
1192 Something like "i * n" or "n * m" is not allowed. */
1195 scop_detection::graphite_can_represent_scev (tree scev
)
1197 if (chrec_contains_undetermined (scev
))
1200 /* We disable the handling of pointer types, because it’s currently not
1201 supported by Graphite with the ISL AST generator. SSA_NAME nodes are
1202 the only nodes, which are disabled in case they are pointers to object
1203 types, but this can be changed. */
1205 if (POINTER_TYPE_P (TREE_TYPE (scev
)) && TREE_CODE (scev
) == SSA_NAME
)
1208 switch (TREE_CODE (scev
))
1213 case NON_LVALUE_EXPR
:
1214 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0));
1217 case POINTER_PLUS_EXPR
:
1219 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1220 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1223 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
1224 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
1225 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
1226 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
1227 && graphite_can_represent_init (scev
)
1228 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1229 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1231 case POLYNOMIAL_CHREC
:
1232 /* Check for constant strides. With a non constant stride of
1233 'n' we would have a value of 'iv * n'. Also check that the
1234 initial value can represented: for example 'n * m' cannot be
1236 if (!evolution_function_right_is_integer_cst (scev
)
1237 || !graphite_can_represent_init (scev
))
1239 return graphite_can_represent_scev (CHREC_LEFT (scev
));
1245 /* Only affine functions can be represented. */
1246 if (tree_contains_chrecs (scev
, NULL
) || !scev_is_linear_expression (scev
))
1252 /* Return true when EXPR can be represented in the polyhedral model.
1254 This means an expression can be represented, if it is linear with respect to
1255 the loops and the strides are non parametric. LOOP is the place where the
1256 expr will be evaluated. SCOP defines the region we analyse. */
1259 scop_detection::graphite_can_represent_expr (sese_l scop
, loop_p loop
,
1262 tree scev
= scalar_evolution_in_region (scop
, loop
, expr
);
1263 return graphite_can_represent_scev (scev
);
1266 /* Return true if the data references of STMT can be represented by Graphite.
1267 We try to analyze the data references in a loop contained in the SCOP. */
1270 scop_detection::stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
)
1272 loop_p nest
= outermost_loop_in_sese (scop
, gimple_bb (stmt
));
1273 loop_p loop
= loop_containing_stmt (stmt
);
1274 vec
<data_reference_p
> drs
= vNULL
;
1276 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1279 data_reference_p dr
;
1280 FOR_EACH_VEC_ELT (drs
, j
, dr
)
1282 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1284 if (nb_subscripts
< 1)
1286 free_data_refs (drs
);
1290 tree ref
= DR_REF (dr
);
1292 for (int i
= nb_subscripts
- 1; i
>= 0; i
--)
1294 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
))
1295 || (TREE_CODE (ref
) != ARRAY_REF
&& TREE_CODE (ref
) != MEM_REF
1296 && TREE_CODE (ref
) != COMPONENT_REF
))
1298 free_data_refs (drs
);
1302 ref
= TREE_OPERAND (ref
, 0);
1306 free_data_refs (drs
);
1310 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1311 Calls have side-effects, except those to const or pure
1315 stmt_has_side_effects (gimple
*stmt
)
1317 if (gimple_has_volatile_ops (stmt
)
1318 || (gimple_code (stmt
) == GIMPLE_CALL
1319 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
1320 || (gimple_code (stmt
) == GIMPLE_ASM
))
1322 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1323 << "Statement has side-effects:\n";
1324 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1330 /* Returns true if STMT can be represented in polyhedral model. LABEL,
1331 simple COND stmts, pure calls, and assignments can be repesented. */
1334 scop_detection::graphite_can_represent_stmt (sese_l scop
, gimple
*stmt
,
1337 loop_p loop
= bb
->loop_father
;
1338 switch (gimple_code (stmt
))
1345 /* We can handle all binary comparisons. Inequalities are
1346 also supported as they can be represented with union of
1348 enum tree_code code
= gimple_cond_code (stmt
);
1349 if (!(code
== LT_EXPR
1354 || code
== NE_EXPR
))
1356 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1357 << "Graphite cannot handle cond stmt:\n";
1358 print_gimple_stmt (dump_file
, stmt
, 0,
1359 TDF_VOPS
| TDF_MEMSYMS
));
1363 for (unsigned i
= 0; i
< 2; ++i
)
1365 tree op
= gimple_op (stmt
, i
);
1366 if (!graphite_can_represent_expr (scop
, loop
, op
)
1367 /* We can only constrain on integer type. */
1368 || (TREE_CODE (TREE_TYPE (op
)) != INTEGER_TYPE
))
1370 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1371 << "Graphite cannot represent stmt:\n";
1372 print_gimple_stmt (dump_file
, stmt
, 0,
1373 TDF_VOPS
| TDF_MEMSYMS
));
1386 /* These nodes cut a new scope. */
1388 dp
<< "[scop-detection-fail] "
1389 << "Gimple stmt not handled in Graphite:\n";
1390 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1395 /* Return true only when STMT is simple enough for being handled by Graphite.
1396 This depends on SCOP, as the parameters are initialized relatively to
1397 this basic block, the linear functions are initialized based on the outermost
1398 loop containing STMT inside the SCOP. BB is the place where we try to
1399 evaluate the STMT. */
1402 scop_detection::stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
1403 basic_block bb
) const
1407 if (is_gimple_debug (stmt
))
1410 if (stmt_has_side_effects (stmt
))
1413 if (!stmt_has_simple_data_refs_p (scop
, stmt
))
1415 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1416 << "Graphite cannot handle data-refs in stmt:\n";
1417 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
););
1421 return graphite_can_represent_stmt (scop
, stmt
, bb
);
1424 /* Return true when BB contains a harmful operation for a scop: that
1425 can be a function call with side effects, the induction variables
1426 are not linear with respect to SCOP, etc. The current open
1427 scop should end before this statement. */
1430 scop_detection::harmful_stmt_in_bb (sese_l scop
, basic_block bb
) const
1432 gimple_stmt_iterator gsi
;
1434 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1435 if (!stmt_simple_for_scop_p (scop
, gsi_stmt (gsi
), bb
))
1441 /* Return true when the body of LOOP has statements that can be represented as a
1445 scop_detection::loop_body_is_valid_scop (loop_p loop
, sese_l scop
) const
1447 if (!loop_ivs_can_be_represented (loop
))
1449 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
1450 << "IV cannot be represented.\n");
1454 if (!loop_nest_has_data_refs (loop
))
1456 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
1457 << "does not have any data reference.\n");
1461 basic_block
*bbs
= get_loop_body (loop
);
1462 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
1464 basic_block bb
= bbs
[i
];
1466 if (harmful_stmt_in_bb (scop
, bb
))
1476 if (!loop_body_is_valid_scop (loop
, scop
))
1485 /* Returns the number of pbbs that are in loops contained in SCOP. */
1488 scop_detection::nb_pbbs_in_loops (scop_p scop
)
1494 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1495 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), scop
->scop_info
->region
))
1501 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
1502 Otherwise returns -1. */
1505 parameter_index_in_region_1 (tree name
, sese_info_p region
)
1510 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1512 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
1519 /* When the parameter NAME is in REGION, returns its index in
1520 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
1521 and returns the index of NAME. */
1524 parameter_index_in_region (tree name
, sese_info_p region
)
1528 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1530 /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
1531 if (TREE_CODE (TREE_TYPE (name
)) != INTEGER_TYPE
)
1534 if (!invariant_in_sese_p_rec (name
, region
->region
, NULL
))
1537 i
= parameter_index_in_region_1 (name
, region
);
1541 i
= region
->params
.length ();
1542 region
->params
.safe_push (name
);
1546 /* In the context of sese S, scan the expression E and translate it to
1547 a linear expression C. When parsing a symbolic multiplication, K
1548 represents the constant multiplier of an expression containing
1552 scan_tree_for_params (sese_info_p s
, tree e
)
1554 if (e
== chrec_dont_know
)
1557 switch (TREE_CODE (e
))
1559 case POLYNOMIAL_CHREC
:
1560 scan_tree_for_params (s
, CHREC_LEFT (e
));
1564 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1565 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1567 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1571 case POINTER_PLUS_EXPR
:
1573 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1574 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1580 case NON_LVALUE_EXPR
:
1581 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1585 parameter_index_in_region (e
, s
);
1601 /* Find parameters with respect to REGION in BB. We are looking in memory
1602 access functions, conditions and loop bounds. */
1605 find_params_in_bb (sese_info_p region
, gimple_poly_bb_p gbb
)
1607 /* Find parameters in the access functions of data references. */
1609 data_reference_p dr
;
1610 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
1611 for (unsigned j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
1612 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
1614 /* Find parameters in conditional statements. */
1616 loop_p loop
= GBB_BB (gbb
)->loop_father
;
1617 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1619 tree lhs
= scalar_evolution_in_region (region
->region
, loop
,
1620 gimple_cond_lhs (stmt
));
1621 tree rhs
= scalar_evolution_in_region (region
->region
, loop
,
1622 gimple_cond_rhs (stmt
));
1624 scan_tree_for_params (region
, lhs
);
1625 scan_tree_for_params (region
, rhs
);
1629 /* Record the parameters used in the SCOP. A variable is a parameter
1630 in a scop if it does not vary during the execution of that scop. */
1633 find_scop_parameters (scop_p scop
)
1636 sese_info_p region
= scop
->scop_info
;
1639 /* Find the parameters used in the loop bounds. */
1640 FOR_EACH_VEC_ELT (region
->loop_nest
, i
, loop
)
1642 tree nb_iters
= number_of_latch_executions (loop
);
1644 if (!chrec_contains_symbols (nb_iters
))
1647 nb_iters
= scalar_evolution_in_region (region
->region
, loop
, nb_iters
);
1648 scan_tree_for_params (region
, nb_iters
);
1651 /* Find the parameters used in data accesses. */
1653 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1654 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1656 int nbp
= sese_nb_params (region
);
1657 scop_set_nb_params (scop
, nbp
);
1660 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1663 build_cross_bb_scalars_def (scop_p scop
, tree def
, basic_block def_bb
,
1667 if (!is_gimple_reg (def
))
1670 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1671 generated out of the induction variables. */
1672 if (scev_analyzable_p (def
, scop
->scop_info
->region
))
1676 imm_use_iterator imm_iter
;
1677 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1678 if (def_bb
!= gimple_bb (use_stmt
) && !is_gimple_debug (use_stmt
))
1680 writes
->safe_push (def
);
1681 DEBUG_PRINT (dp
<< "Adding scalar write: ";
1682 print_generic_expr (dump_file
, def
, 0);
1683 dp
<< "\nFrom stmt: ";
1684 print_gimple_stmt (dump_file
,
1685 SSA_NAME_DEF_STMT (def
), 0, 0));
1686 /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
1687 before all the uses have been visited. */
1688 BREAK_FROM_IMM_USE_STMT (imm_iter
);
1692 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1695 build_cross_bb_scalars_use (scop_p scop
, tree use
, gimple
*use_stmt
,
1696 vec
<scalar_use
> *reads
)
1699 if (!is_gimple_reg (use
))
1702 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1703 generated out of the induction variables. */
1704 if (scev_analyzable_p (use
, scop
->scop_info
->region
))
1707 gimple
*def_stmt
= SSA_NAME_DEF_STMT (use
);
1708 if (gimple_bb (def_stmt
) != gimple_bb (use_stmt
))
1710 DEBUG_PRINT (dp
<< "Adding scalar read: ";
1711 print_generic_expr (dump_file
, use
, 0);
1712 dp
<< "\nFrom stmt: ";
1713 print_gimple_stmt (dump_file
, use_stmt
, 0, 0));
1714 reads
->safe_push (std::make_pair (use_stmt
, use
));
1718 /* Record all scalar variables that are defined and used in different BBs of the
1722 graphite_find_cross_bb_scalar_vars (scop_p scop
, gimple
*stmt
,
1723 vec
<scalar_use
> *reads
, vec
<tree
> *writes
)
1727 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
1728 def
= gimple_assign_lhs (stmt
);
1729 else if (gimple_code (stmt
) == GIMPLE_CALL
)
1730 def
= gimple_call_lhs (stmt
);
1731 else if (gimple_code (stmt
) == GIMPLE_PHI
)
1732 def
= gimple_phi_result (stmt
);
1737 build_cross_bb_scalars_def (scop
, def
, gimple_bb (stmt
), writes
);
1740 use_operand_p use_p
;
1741 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1743 tree use
= USE_FROM_PTR (use_p
);
1744 build_cross_bb_scalars_use (scop
, use
, stmt
, reads
);
1748 /* Generates a polyhedral black box only if the bb contains interesting
1751 static gimple_poly_bb_p
1752 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
1754 vec
<data_reference_p
> drs
= vNULL
;
1755 vec
<tree
> writes
= vNULL
;
1756 vec
<scalar_use
> reads
= vNULL
;
1758 sese_l region
= scop
->scop_info
->region
;
1759 loop_p nest
= outermost_loop_in_sese (region
, bb
);
1761 loop_p loop
= bb
->loop_father
;
1762 if (!loop_in_sese_p (loop
, region
))
1765 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1768 gimple
*stmt
= gsi_stmt (gsi
);
1769 if (is_gimple_debug (stmt
))
1772 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1773 graphite_find_cross_bb_scalar_vars (scop
, stmt
, &reads
, &writes
);
1776 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1778 if (!virtual_operand_p (gimple_phi_result (psi
.phi ())))
1779 graphite_find_cross_bb_scalar_vars (scop
, psi
.phi (), &reads
, &writes
);
1781 if (drs
.is_empty () && writes
.is_empty () && reads
.is_empty ())
1784 return new_gimple_poly_bb (bb
, drs
, reads
, writes
);
1787 /* Compute alias-sets for all data references in DRS. */
1790 build_alias_set (scop_p scop
)
1792 int num_vertices
= scop
->drs
.length ();
1793 struct graph
*g
= new_graph (num_vertices
);
1798 FOR_EACH_VEC_ELT (scop
->drs
, i
, dr1
)
1799 for (j
= i
+1; scop
->drs
.iterate (j
, &dr2
); j
++)
1800 if (dr_may_alias_p (dr1
->dr
, dr2
->dr
, true))
1806 all_vertices
= XNEWVEC (int, num_vertices
);
1807 for (i
= 0; i
< num_vertices
; i
++)
1808 all_vertices
[i
] = i
;
1810 graphds_dfs (g
, all_vertices
, num_vertices
, NULL
, true, NULL
);
1811 free (all_vertices
);
1813 for (i
= 0; i
< g
->n_vertices
; i
++)
1814 scop
->drs
[i
].alias_set
= g
->vertices
[i
].component
+ 1;
1819 /* Gather BBs and conditions for a SCOP. */
1820 class gather_bbs
: public dom_walker
1823 gather_bbs (cdi_direction
, scop_p
);
1825 virtual edge
before_dom_children (basic_block
);
1826 virtual void after_dom_children (basic_block
);
1829 auto_vec
<gimple
*, 3> conditions
, cases
;
1833 gather_bbs::gather_bbs (cdi_direction direction
, scop_p scop
)
1834 : dom_walker (direction
), scop (scop
)
1838 /* Call-back for dom_walk executed before visiting the dominated
1842 gather_bbs::before_dom_children (basic_block bb
)
1844 if (!bb_in_sese_p (bb
, scop
->scop_info
->region
))
1847 gcond
*stmt
= single_pred_cond_non_loop_exit (bb
);
1851 edge e
= single_pred_edge (bb
);
1853 conditions
.safe_push (stmt
);
1855 if (e
->flags
& EDGE_TRUE_VALUE
)
1856 cases
.safe_push (stmt
);
1858 cases
.safe_push (NULL
);
1861 scop
->scop_info
->bbs
.safe_push (bb
);
1863 gimple_poly_bb_p gbb
= try_generate_gimple_bb (scop
, bb
);
1867 GBB_CONDITIONS (gbb
) = conditions
.copy ();
1868 GBB_CONDITION_CASES (gbb
) = cases
.copy ();
1870 poly_bb_p pbb
= new_poly_bb (scop
, gbb
);
1871 scop
->pbbs
.safe_push (pbb
);
1874 data_reference_p dr
;
1875 FOR_EACH_VEC_ELT (gbb
->data_refs
, i
, dr
)
1877 DEBUG_PRINT (dp
<< "Adding memory ";
1882 print_generic_expr (dump_file
, dr
->ref
, 0);
1883 dp
<< "\nFrom stmt: ";
1884 print_gimple_stmt (dump_file
, dr
->stmt
, 0, 0));
1886 scop
->drs
.safe_push (dr_info (dr
, pbb
));
1892 /* Call-back for dom_walk executed after visiting the dominated
1896 gather_bbs::after_dom_children (basic_block bb
)
1898 if (!bb_in_sese_p (bb
, scop
->scop_info
->region
))
1901 if (single_pred_cond_non_loop_exit (bb
))
1908 /* Find Static Control Parts (SCoP) in the current function and pushes
1912 build_scops (vec
<scop_p
> *scops
)
1915 dp
.set_dump_file (dump_file
);
1917 canonicalize_loop_closed_ssa_form ();
1920 sb
.build_scop_depth (scop_detection::invalid_sese
, current_loops
->tree_root
);
1922 /* Now create scops from the lightweight SESEs. */
1923 vec
<sese_l
> scops_l
= sb
.get_scops ();
1926 FOR_EACH_VEC_ELT (scops_l
, i
, s
)
1928 scop_p scop
= new_scop (s
->entry
, s
->exit
);
1930 /* Record all basic blocks and their conditions in REGION. */
1931 gather_bbs (CDI_DOMINATORS
, scop
).walk (cfun
->cfg
->x_entry_block_ptr
);
1933 build_alias_set (scop
);
1935 /* Do not optimize a scop containing only PBBs that do not belong
1937 if (sb
.nb_pbbs_in_loops (scop
) == 0)
1939 DEBUG_PRINT (dp
<< "[scop-detection-fail] no data references.\n");
1944 unsigned max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
1945 if (scop
->drs
.length () >= max_arrays
)
1947 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many data references: "
1948 << scop
->drs
.length ()
1949 << " is larger than --param graphite-max-arrays-per-scop="
1950 << max_arrays
<< ".\n");
1955 build_sese_loop_nests (scop
->scop_info
);
1957 find_scop_parameters (scop
);
1958 graphite_dim_t max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
1960 if (scop_nb_params (scop
) > max_dim
)
1962 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many parameters: "
1963 << scop_nb_params (scop
)
1964 << " larger than --param graphite-max-nb-scop-params="
1965 << max_dim
<< ".\n");
1970 scops
->safe_push (scop
);
1973 DEBUG_PRINT (dp
<< "number of SCoPs: " << (scops
? scops
->length () : 0););
1976 #endif /* HAVE_isl */