1 /* Detection of Static Control Parts (SCoP) for Graphite.
2 Copyright (C) 2009-2016 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_in_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_loop_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
)
697 /* If any of the dominators has two predecessors but one of them is a back
698 edge, then that basic block also qualifies as a dominator with single
700 if (dom
->preds
->length () == 2)
702 /* If e1->src dominates e2->src then e1->src will also dominate dom. */
703 edge e1
= (*dom
->preds
)[0];
704 edge e2
= (*dom
->preds
)[1];
705 loop_p l
= dom
->loop_father
;
706 loop_p l1
= e1
->src
->loop_father
;
707 loop_p l2
= e2
->src
->loop_father
;
708 if (l
!= l1
&& l
== l2
709 && dominated_by_p (CDI_DOMINATORS
, e2
->src
, e1
->src
))
711 if (l
!= l2
&& l
== l1
712 && dominated_by_p (CDI_DOMINATORS
, e1
->src
, e2
->src
))
716 while (dom
->preds
->length () != 1)
718 if (dom
->preds
->length () < 1)
720 dom
= get_immediate_dominator (CDI_DOMINATORS
, dom
);
724 return (*dom
->preds
)[0];
727 /* Return the closest post-dominator with a single exit edge. In case of a
728 back-loop the back-edge is not counted. */
731 scop_detection::get_nearest_pdom_with_single_exit (basic_block pdom
)
736 /* If any of the post-dominators has two successors but one of them is a back
737 edge, then that basic block also qualifies as a post-dominator with single
739 if (pdom
->succs
->length () == 2)
741 /* If e1->dest post-dominates e2->dest then e1->dest will also
742 post-dominate pdom. */
743 edge e1
= (*pdom
->succs
)[0];
744 edge e2
= (*pdom
->succs
)[1];
745 loop_p l
= pdom
->loop_father
;
746 loop_p l1
= e1
->dest
->loop_father
;
747 loop_p l2
= e2
->dest
->loop_father
;
748 if (l
!= l1
&& l
== l2
749 && dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, e1
->dest
))
751 if (l
!= l2
&& l
== l1
752 && dominated_by_p (CDI_POST_DOMINATORS
, e1
->dest
, e2
->dest
))
756 while (pdom
->succs
->length () != 1)
758 if (pdom
->succs
->length () < 1)
760 pdom
= get_immediate_dominator (CDI_POST_DOMINATORS
, pdom
);
765 return (*pdom
->succs
)[0];
768 /* Merge scops at same loop depth and returns the new sese.
769 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
772 scop_detection::merge_sese (sese_l first
, sese_l second
) const
774 /* In the trivial case first/second may be NULL. */
780 DEBUG_PRINT (dp
<< "[scop-detection] try merging sese s1: ";
781 print_sese (dump_file
, first
);
782 dp
<< "[scop-detection] try merging sese s2: ";
783 print_sese (dump_file
, second
));
785 /* Assumption: Both the sese's should be at the same loop depth or one scop
786 should subsume the other like in case of nested loops. */
788 /* Find the common dominators for entry,
789 and common post-dominators for the exit. */
790 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
,
791 get_entry_bb (first
),
792 get_entry_bb (second
));
794 edge entry
= get_nearest_dom_with_single_entry (dom
);
796 if (!entry
|| (entry
->flags
& EDGE_IRREDUCIBLE_LOOP
))
799 basic_block pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
,
801 get_exit_bb (second
));
802 pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
, dom
, pdom
);
804 edge exit
= get_nearest_pdom_with_single_exit (pdom
);
806 if (!exit
|| (exit
->flags
& EDGE_IRREDUCIBLE_LOOP
))
809 sese_l
combined (entry
, exit
);
811 DEBUG_PRINT (dp
<< "[scop-detection] checking combined sese: ";
812 print_sese (dump_file
, combined
));
814 /* FIXME: We could iterate to find the dom which dominates pdom, and pdom
815 which post-dominates dom, until it stabilizes. Also, ENTRY->SRC and
816 EXIT->DEST should be in the same loop nest. */
817 if (!dominated_by_p (CDI_DOMINATORS
, pdom
, dom
)
818 || loop_depth (entry
->src
->loop_father
)
819 != loop_depth (exit
->dest
->loop_father
))
822 /* For now we just want to bail out when exit does not post-dominate entry.
823 TODO: We might just add a basic_block at the exit to make exit
824 post-dominate entry (the entire region). */
825 if (!dominated_by_p (CDI_POST_DOMINATORS
, get_entry_bb (combined
),
826 get_exit_bb (combined
))
827 || !dominated_by_p (CDI_DOMINATORS
, get_exit_bb (combined
),
828 get_entry_bb (combined
)))
830 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
834 /* FIXME: We should remove this piece of code once
835 canonicalize_loop_closed_ssa has been removed, because that function
836 adds a BB with single exit. */
837 if (!trivially_empty_bb_p (get_exit_bb (combined
)))
839 /* Find the first empty succ (with single exit) of combined.exit. */
840 basic_block imm_succ
= combined
.exit
->dest
;
841 if (single_succ_p (imm_succ
) && trivially_empty_bb_p (imm_succ
))
842 combined
.exit
= single_succ_edge (imm_succ
);
845 DEBUG_PRINT (dp
<< "[scop-detection-fail] Discarding SCoP because "
846 << "no single exit (empty succ) for sese exit";
847 print_sese (dump_file
, combined
));
852 /* Analyze all the BBs in new sese. */
853 if (harmful_loop_in_region (combined
))
856 DEBUG_PRINT (dp
<< "[merged-sese] s1: "; print_sese (dump_file
, combined
));
861 /* Build scop outer->inner if possible. */
864 scop_detection::build_scop_depth (sese_l s
, loop_p loop
)
869 DEBUG_PRINT (dp
<< "[Depth loop_" << loop
->num
<< "]\n");
870 s
= build_scop_depth (s
, loop
->inner
);
872 sese_l s2
= merge_sese (s
, get_sese (loop
));
875 /* s might be a valid scop, so return it and start analyzing from the
877 build_scop_depth (invalid_sese
, loop
->next
);
881 if (!loop_is_valid_in_scop (loop
, s2
))
882 return build_scop_depth (invalid_sese
, loop
->next
);
884 return build_scop_breadth (s2
, loop
);
887 /* If loop and loop->next are valid scops, try to merge them. */
890 scop_detection::build_scop_breadth (sese_l s1
, loop_p loop
)
894 DEBUG_PRINT (dp
<< "[Breadth loop_" << loop
->num
<< "]\n");
898 sese_l s2
= build_scop_depth (invalid_sese
, l
->next
);
906 sese_l combined
= merge_sese (s1
, s2
);
918 /* Returns true when Graphite can represent LOOP in SCOP.
919 FIXME: For the moment, graphite cannot be used on loops that iterate using
920 induction variables that wrap. */
923 scop_detection::can_represent_loop_1 (loop_p loop
, sese_l scop
)
926 struct tree_niter_desc niter_desc
;
928 return single_exit (loop
)
929 && !(loop_preheader_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
)
930 && number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
931 && niter_desc
.control
.no_overflow
932 && (niter
= number_of_latch_executions (loop
))
933 && !chrec_contains_undetermined (niter
)
934 && graphite_can_represent_expr (scop
, loop
, niter
);
937 /* Return true when all the loops within LOOP can be represented by
941 scop_detection::can_represent_loop (loop_p loop
, sese_l scop
)
943 if (!can_represent_loop_1 (loop
, scop
))
945 if (loop
->inner
&& !can_represent_loop (loop
->inner
, scop
))
947 if (loop
->next
&& !can_represent_loop (loop
->next
, scop
))
953 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
954 region of code that can be represented in the polyhedral model. SCOP
955 defines the region we analyse. */
958 scop_detection::loop_is_valid_in_scop (loop_p loop
, sese_l scop
) const
963 if (!optimize_loop_nest_for_speed_p (loop
))
965 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_"
966 << loop
->num
<< " is not on a hot path.\n");
970 if (!can_represent_loop (loop
, scop
))
972 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot represent loop_"
973 << loop
->num
<< "\n");
977 if (loop_body_is_valid_scop (loop
, scop
))
979 DEBUG_PRINT (dp
<< "[valid-scop] loop_" << loop
->num
980 << " is a valid scop.\n");
986 /* Return true when BEGIN is the preheader edge of a loop with a single exit
990 scop_detection::region_has_one_loop (sese_l s
)
992 edge begin
= s
.entry
;
994 /* Check for a single perfectly nested loop. */
995 if (begin
->dest
->loop_father
->inner
)
998 /* Otherwise, check whether we have adjacent loops. */
999 return begin
->dest
->loop_father
== end
->src
->loop_father
;
1002 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
1005 scop_detection::add_scop (sese_l s
)
1009 /* Do not add scops with only one loop. */
1010 if (region_has_one_loop (s
))
1012 DEBUG_PRINT (dp
<< "[scop-detection-fail] Discarding one loop SCoP: ";
1013 print_sese (dump_file
, s
));
1017 if (get_exit_bb (s
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1019 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1020 << "Discarding SCoP exiting to return: ";
1021 print_sese (dump_file
, s
));
1025 /* Remove all the scops which are subsumed by s. */
1026 remove_subscops (s
);
1028 /* Remove intersecting scops. FIXME: It will be a good idea to keep
1029 the non-intersecting part of the scop already in the list. */
1030 remove_intersecting_scops (s
);
1032 scops
.safe_push (s
);
1033 DEBUG_PRINT (dp
<< "[scop-detection] Adding SCoP: "; print_sese (dump_file
, s
));
1036 /* Return true when a statement in SCOP cannot be represented by Graphite.
1037 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
1038 Limit the number of bbs between adjacent loops to
1039 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
1042 scop_detection::harmful_loop_in_region (sese_l scop
) const
1044 basic_block exit_bb
= get_exit_bb (scop
);
1045 basic_block entry_bb
= get_entry_bb (scop
);
1047 DEBUG_PRINT (dp
<< "[checking-harmful-bbs] ";
1048 print_sese (dump_file
, scop
));
1049 gcc_assert (dominated_by_p (CDI_DOMINATORS
, exit_bb
, entry_bb
));
1051 int depth
= bb_dom_dfs_in (CDI_DOMINATORS
, exit_bb
)
1052 - bb_dom_dfs_in (CDI_DOMINATORS
, entry_bb
);
1054 gcc_assert (depth
> 0);
1056 vec
<basic_block
> dom
1057 = get_dominated_to_depth (CDI_DOMINATORS
, entry_bb
, depth
);
1060 bitmap loops
= BITMAP_ALLOC (NULL
);
1061 FOR_EACH_VEC_ELT (dom
, i
, bb
)
1063 DEBUG_PRINT (dp
<< "Visiting bb_" << bb
->index
<< "\n");
1065 /* We don't want to analyze any bb outside sese. */
1066 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb
, exit_bb
))
1069 /* Basic blocks dominated by the scop->exit are not in the scop. */
1070 if (bb
!= exit_bb
&& dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
1073 /* The basic block should not be part of an irreducible loop. */
1074 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1077 BITMAP_FREE (loops
);
1081 /* Check for unstructured control flow: CFG not generated by structured
1083 if (bb
->succs
->length () > 1)
1087 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1088 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb
, e
->dest
)
1089 && !dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
1093 /* Collect all loops in the current region. */
1094 loop_p loop
= bb
->loop_father
;
1095 if (loop_in_sese_p (loop
, scop
))
1096 bitmap_set_bit (loops
, loop
->num
);
1099 /* We only check for harmful statements in basic blocks not part of
1100 any loop fully contained in the scop: other bbs are checked below
1101 in loop_is_valid_in_scop. */
1102 if (harmful_stmt_in_bb (scop
, bb
))
1105 BITMAP_FREE (loops
);
1112 /* Go through all loops and check that they are still valid in the combined
1116 EXECUTE_IF_SET_IN_BITMAP (loops
, 0, j
, bi
)
1118 loop_p loop
= (*current_loops
->larray
)[j
];
1119 gcc_assert (loop
->num
== (int) j
);
1121 if (!loop_is_valid_in_scop (loop
, scop
))
1124 BITMAP_FREE (loops
);
1130 BITMAP_FREE (loops
);
1134 /* Returns true if S1 subsumes/surrounds S2. */
1136 scop_detection::subsumes (sese_l s1
, sese_l s2
)
1138 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
1140 && dominated_by_p (CDI_POST_DOMINATORS
, s2
.exit
->dest
,
1146 /* Remove a SCoP which is subsumed by S1. */
1148 scop_detection::remove_subscops (sese_l s1
)
1152 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
1154 if (subsumes (s1
, *s2
))
1156 DEBUG_PRINT (dp
<< "Removing sub-SCoP";
1157 print_sese (dump_file
, *s2
));
1158 scops
.unordered_remove (j
);
1163 /* Returns true if S1 intersects with S2. Since we already know that S1 does
1164 not subsume S2 or vice-versa, we only check for entry bbs. */
1167 scop_detection::intersects (sese_l s1
, sese_l s2
)
1169 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
1171 && !dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
1174 if ((s1
.exit
== s2
.entry
) || (s2
.exit
== s1
.entry
))
1180 /* Remove one of the scops when it intersects with any other. */
1183 scop_detection::remove_intersecting_scops (sese_l s1
)
1187 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
1189 if (intersects (s1
, *s2
))
1191 DEBUG_PRINT (dp
<< "Removing intersecting SCoP";
1192 print_sese (dump_file
, *s2
);
1193 dp
<< "Intersects with:";
1194 print_sese (dump_file
, s1
));
1195 scops
.unordered_remove (j
);
1200 /* Something like "n * m" is not allowed. */
1203 scop_detection::graphite_can_represent_init (tree e
)
1205 switch (TREE_CODE (e
))
1207 case POLYNOMIAL_CHREC
:
1208 return graphite_can_represent_init (CHREC_LEFT (e
))
1209 && graphite_can_represent_init (CHREC_RIGHT (e
));
1212 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1213 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
1214 && tree_fits_shwi_p (TREE_OPERAND (e
, 1));
1216 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
1217 && tree_fits_shwi_p (TREE_OPERAND (e
, 0));
1220 case POINTER_PLUS_EXPR
:
1222 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
1223 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
1228 case NON_LVALUE_EXPR
:
1229 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
1238 /* Return true when SCEV can be represented in the polyhedral model.
1240 An expression can be represented, if it can be expressed as an
1241 affine expression. For loops (i, j) and parameters (m, n) all
1242 affine expressions are of the form:
1244 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
1246 1 i + 20 j + (-2) m + 25
1248 Something like "i * n" or "n * m" is not allowed. */
1251 scop_detection::graphite_can_represent_scev (tree scev
)
1253 if (chrec_contains_undetermined (scev
))
1256 /* We disable the handling of pointer types, because it’s currently not
1257 supported by Graphite with the isl AST generator. SSA_NAME nodes are
1258 the only nodes, which are disabled in case they are pointers to object
1259 types, but this can be changed. */
1261 if (POINTER_TYPE_P (TREE_TYPE (scev
)) && TREE_CODE (scev
) == SSA_NAME
)
1264 switch (TREE_CODE (scev
))
1269 case NON_LVALUE_EXPR
:
1270 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0));
1273 case POINTER_PLUS_EXPR
:
1275 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1276 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1279 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
1280 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
1281 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
1282 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
1283 && graphite_can_represent_init (scev
)
1284 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1285 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1287 case POLYNOMIAL_CHREC
:
1288 /* Check for constant strides. With a non constant stride of
1289 'n' we would have a value of 'iv * n'. Also check that the
1290 initial value can represented: for example 'n * m' cannot be
1292 if (!evolution_function_right_is_integer_cst (scev
)
1293 || !graphite_can_represent_init (scev
))
1295 return graphite_can_represent_scev (CHREC_LEFT (scev
));
1301 /* Only affine functions can be represented. */
1302 if (tree_contains_chrecs (scev
, NULL
) || !scev_is_linear_expression (scev
))
1308 /* Return true when EXPR can be represented in the polyhedral model.
1310 This means an expression can be represented, if it is linear with respect to
1311 the loops and the strides are non parametric. LOOP is the place where the
1312 expr will be evaluated. SCOP defines the region we analyse. */
1315 scop_detection::graphite_can_represent_expr (sese_l scop
, loop_p loop
,
1318 tree scev
= scalar_evolution_in_region (scop
, loop
, expr
);
1319 return graphite_can_represent_scev (scev
);
1322 /* Return true if the data references of STMT can be represented by Graphite.
1323 We try to analyze the data references in a loop contained in the SCOP. */
1326 scop_detection::stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
)
1328 loop_p nest
= outermost_loop_in_sese (scop
, gimple_bb (stmt
));
1329 loop_p loop
= loop_containing_stmt (stmt
);
1330 vec
<data_reference_p
> drs
= vNULL
;
1332 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1335 data_reference_p dr
;
1336 FOR_EACH_VEC_ELT (drs
, j
, dr
)
1338 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1340 if (nb_subscripts
< 1)
1342 free_data_refs (drs
);
1346 tree ref
= DR_REF (dr
);
1348 for (int i
= nb_subscripts
- 1; i
>= 0; i
--)
1350 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
))
1351 || (TREE_CODE (ref
) != ARRAY_REF
&& TREE_CODE (ref
) != MEM_REF
1352 && TREE_CODE (ref
) != COMPONENT_REF
))
1354 free_data_refs (drs
);
1358 ref
= TREE_OPERAND (ref
, 0);
1362 free_data_refs (drs
);
1366 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1367 Calls have side-effects, except those to const or pure
1371 stmt_has_side_effects (gimple
*stmt
)
1373 if (gimple_has_volatile_ops (stmt
)
1374 || (gimple_code (stmt
) == GIMPLE_CALL
1375 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
1376 || (gimple_code (stmt
) == GIMPLE_ASM
))
1378 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1379 << "Statement has side-effects:\n";
1380 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1386 /* Returns true if STMT can be represented in polyhedral model. LABEL,
1387 simple COND stmts, pure calls, and assignments can be repesented. */
1390 scop_detection::graphite_can_represent_stmt (sese_l scop
, gimple
*stmt
,
1393 loop_p loop
= bb
->loop_father
;
1394 switch (gimple_code (stmt
))
1401 /* We can handle all binary comparisons. Inequalities are
1402 also supported as they can be represented with union of
1404 enum tree_code code
= gimple_cond_code (stmt
);
1405 if (!(code
== LT_EXPR
1410 || code
== NE_EXPR
))
1412 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1413 << "Graphite cannot handle cond stmt:\n";
1414 print_gimple_stmt (dump_file
, stmt
, 0,
1415 TDF_VOPS
| TDF_MEMSYMS
));
1419 for (unsigned i
= 0; i
< 2; ++i
)
1421 tree op
= gimple_op (stmt
, i
);
1422 if (!graphite_can_represent_expr (scop
, loop
, op
)
1423 /* We can only constrain on integer type. */
1424 || (TREE_CODE (TREE_TYPE (op
)) != INTEGER_TYPE
))
1426 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1427 << "Graphite cannot represent stmt:\n";
1428 print_gimple_stmt (dump_file
, stmt
, 0,
1429 TDF_VOPS
| TDF_MEMSYMS
));
1442 /* These nodes cut a new scope. */
1444 dp
<< "[scop-detection-fail] "
1445 << "Gimple stmt not handled in Graphite:\n";
1446 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1451 /* Return true only when STMT is simple enough for being handled by Graphite.
1452 This depends on SCOP, as the parameters are initialized relatively to
1453 this basic block, the linear functions are initialized based on the outermost
1454 loop containing STMT inside the SCOP. BB is the place where we try to
1455 evaluate the STMT. */
1458 scop_detection::stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
1459 basic_block bb
) const
1463 if (is_gimple_debug (stmt
))
1466 if (stmt_has_side_effects (stmt
))
1469 if (!stmt_has_simple_data_refs_p (scop
, stmt
))
1471 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1472 << "Graphite cannot handle data-refs in stmt:\n";
1473 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
););
1477 return graphite_can_represent_stmt (scop
, stmt
, bb
);
1480 /* Return true when BB contains a harmful operation for a scop: that
1481 can be a function call with side effects, the induction variables
1482 are not linear with respect to SCOP, etc. The current open
1483 scop should end before this statement. */
1486 scop_detection::harmful_stmt_in_bb (sese_l scop
, basic_block bb
) const
1488 gimple_stmt_iterator gsi
;
1490 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1491 if (!stmt_simple_for_scop_p (scop
, gsi_stmt (gsi
), bb
))
1497 /* Return true when the body of LOOP has statements that can be represented as a
1501 scop_detection::loop_body_is_valid_scop (loop_p loop
, sese_l scop
) const
1503 if (!loop_ivs_can_be_represented (loop
))
1505 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
1506 << "IV cannot be represented.\n");
1510 if (!loop_nest_has_data_refs (loop
))
1512 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
1513 << "does not have any data reference.\n");
1517 basic_block
*bbs
= get_loop_body (loop
);
1518 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
1520 basic_block bb
= bbs
[i
];
1522 if (harmful_stmt_in_bb (scop
, bb
))
1535 if (!loop_body_is_valid_scop (loop
, scop
))
1544 /* Returns the number of pbbs that are in loops contained in SCOP. */
1547 scop_detection::nb_pbbs_in_loops (scop_p scop
)
1553 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1554 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), scop
->scop_info
->region
))
1560 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
1561 Otherwise returns -1. */
1564 parameter_index_in_region_1 (tree name
, sese_info_p region
)
1569 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1571 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
1578 /* When the parameter NAME is in REGION, returns its index in
1579 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
1580 and returns the index of NAME. */
1583 parameter_index_in_region (tree name
, sese_info_p region
)
1587 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1589 /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
1590 if (TREE_CODE (TREE_TYPE (name
)) != INTEGER_TYPE
)
1593 if (!invariant_in_sese_p_rec (name
, region
->region
, NULL
))
1596 i
= parameter_index_in_region_1 (name
, region
);
1600 i
= region
->params
.length ();
1601 region
->params
.safe_push (name
);
1605 /* In the context of sese S, scan the expression E and translate it to
1606 a linear expression C. When parsing a symbolic multiplication, K
1607 represents the constant multiplier of an expression containing
1611 scan_tree_for_params (sese_info_p s
, tree e
)
1613 if (e
== chrec_dont_know
)
1616 switch (TREE_CODE (e
))
1618 case POLYNOMIAL_CHREC
:
1619 scan_tree_for_params (s
, CHREC_LEFT (e
));
1623 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1624 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1626 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1630 case POINTER_PLUS_EXPR
:
1632 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1633 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1639 case NON_LVALUE_EXPR
:
1640 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1644 parameter_index_in_region (e
, s
);
1660 /* Find parameters with respect to REGION in BB. We are looking in memory
1661 access functions, conditions and loop bounds. */
1664 find_params_in_bb (sese_info_p region
, gimple_poly_bb_p gbb
)
1666 /* Find parameters in the access functions of data references. */
1668 data_reference_p dr
;
1669 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
1670 for (unsigned j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
1671 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
1673 /* Find parameters in conditional statements. */
1675 loop_p loop
= GBB_BB (gbb
)->loop_father
;
1676 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1678 tree lhs
= scalar_evolution_in_region (region
->region
, loop
,
1679 gimple_cond_lhs (stmt
));
1680 tree rhs
= scalar_evolution_in_region (region
->region
, loop
,
1681 gimple_cond_rhs (stmt
));
1683 scan_tree_for_params (region
, lhs
);
1684 scan_tree_for_params (region
, rhs
);
1688 /* Record the parameters used in the SCOP. A variable is a parameter
1689 in a scop if it does not vary during the execution of that scop. */
1692 find_scop_parameters (scop_p scop
)
1695 sese_info_p region
= scop
->scop_info
;
1698 /* Find the parameters used in the loop bounds. */
1699 FOR_EACH_VEC_ELT (region
->loop_nest
, i
, loop
)
1701 tree nb_iters
= number_of_latch_executions (loop
);
1703 if (!chrec_contains_symbols (nb_iters
))
1706 nb_iters
= scalar_evolution_in_region (region
->region
, loop
, nb_iters
);
1707 scan_tree_for_params (region
, nb_iters
);
1710 /* Find the parameters used in data accesses. */
1712 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1713 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1715 int nbp
= sese_nb_params (region
);
1716 scop_set_nb_params (scop
, nbp
);
1719 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1722 build_cross_bb_scalars_def (scop_p scop
, tree def
, basic_block def_bb
,
1726 if (!is_gimple_reg (def
))
1729 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1730 generated out of the induction variables. */
1731 if (scev_analyzable_p (def
, scop
->scop_info
->region
))
1735 imm_use_iterator imm_iter
;
1736 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1737 if (def_bb
!= gimple_bb (use_stmt
) && !is_gimple_debug (use_stmt
))
1739 writes
->safe_push (def
);
1740 DEBUG_PRINT (dp
<< "Adding scalar write: ";
1741 print_generic_expr (dump_file
, def
, 0);
1742 dp
<< "\nFrom stmt: ";
1743 print_gimple_stmt (dump_file
,
1744 SSA_NAME_DEF_STMT (def
), 0, 0));
1745 /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
1746 before all the uses have been visited. */
1747 BREAK_FROM_IMM_USE_STMT (imm_iter
);
1751 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1754 build_cross_bb_scalars_use (scop_p scop
, tree use
, gimple
*use_stmt
,
1755 vec
<scalar_use
> *reads
)
1758 if (!is_gimple_reg (use
))
1761 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1762 generated out of the induction variables. */
1763 if (scev_analyzable_p (use
, scop
->scop_info
->region
))
1766 gimple
*def_stmt
= SSA_NAME_DEF_STMT (use
);
1767 if (gimple_bb (def_stmt
) != gimple_bb (use_stmt
))
1769 DEBUG_PRINT (dp
<< "Adding scalar read: ";
1770 print_generic_expr (dump_file
, use
, 0);
1771 dp
<< "\nFrom stmt: ";
1772 print_gimple_stmt (dump_file
, use_stmt
, 0, 0));
1773 reads
->safe_push (std::make_pair (use_stmt
, use
));
1777 /* Record all scalar variables that are defined and used in different BBs of the
1781 graphite_find_cross_bb_scalar_vars (scop_p scop
, gimple
*stmt
,
1782 vec
<scalar_use
> *reads
, vec
<tree
> *writes
)
1786 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
1787 def
= gimple_assign_lhs (stmt
);
1788 else if (gimple_code (stmt
) == GIMPLE_CALL
)
1789 def
= gimple_call_lhs (stmt
);
1790 else if (gimple_code (stmt
) == GIMPLE_PHI
)
1791 def
= gimple_phi_result (stmt
);
1796 build_cross_bb_scalars_def (scop
, def
, gimple_bb (stmt
), writes
);
1799 use_operand_p use_p
;
1800 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1802 tree use
= USE_FROM_PTR (use_p
);
1803 build_cross_bb_scalars_use (scop
, use
, stmt
, reads
);
1807 /* Generates a polyhedral black box only if the bb contains interesting
1810 static gimple_poly_bb_p
1811 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
1813 vec
<data_reference_p
> drs
= vNULL
;
1814 vec
<tree
> writes
= vNULL
;
1815 vec
<scalar_use
> reads
= vNULL
;
1817 sese_l region
= scop
->scop_info
->region
;
1818 loop_p nest
= outermost_loop_in_sese (region
, bb
);
1820 loop_p loop
= bb
->loop_father
;
1821 if (!loop_in_sese_p (loop
, region
))
1824 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1827 gimple
*stmt
= gsi_stmt (gsi
);
1828 if (is_gimple_debug (stmt
))
1831 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1832 graphite_find_cross_bb_scalar_vars (scop
, stmt
, &reads
, &writes
);
1835 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1837 if (!virtual_operand_p (gimple_phi_result (psi
.phi ())))
1838 graphite_find_cross_bb_scalar_vars (scop
, psi
.phi (), &reads
, &writes
);
1840 if (drs
.is_empty () && writes
.is_empty () && reads
.is_empty ())
1843 return new_gimple_poly_bb (bb
, drs
, reads
, writes
);
1846 /* Compute alias-sets for all data references in DRS. */
1849 build_alias_set (scop_p scop
)
1851 int num_vertices
= scop
->drs
.length ();
1852 struct graph
*g
= new_graph (num_vertices
);
1857 FOR_EACH_VEC_ELT (scop
->drs
, i
, dr1
)
1858 for (j
= i
+1; scop
->drs
.iterate (j
, &dr2
); j
++)
1859 if (dr_may_alias_p (dr1
->dr
, dr2
->dr
, true))
1865 all_vertices
= XNEWVEC (int, num_vertices
);
1866 for (i
= 0; i
< num_vertices
; i
++)
1867 all_vertices
[i
] = i
;
1869 graphds_dfs (g
, all_vertices
, num_vertices
, NULL
, true, NULL
);
1870 free (all_vertices
);
1872 for (i
= 0; i
< g
->n_vertices
; i
++)
1873 scop
->drs
[i
].alias_set
= g
->vertices
[i
].component
+ 1;
1878 /* Gather BBs and conditions for a SCOP. */
1879 class gather_bbs
: public dom_walker
1882 gather_bbs (cdi_direction
, scop_p
);
1884 virtual edge
before_dom_children (basic_block
);
1885 virtual void after_dom_children (basic_block
);
1888 auto_vec
<gimple
*, 3> conditions
, cases
;
1892 gather_bbs::gather_bbs (cdi_direction direction
, scop_p scop
)
1893 : dom_walker (direction
), scop (scop
)
1897 /* Record in execution order the loops fully contained in the region. */
1900 record_loop_in_sese (basic_block bb
, sese_info_p region
)
1902 loop_p father
= bb
->loop_father
;
1903 if (loop_in_sese_p (father
, region
->region
))
1908 FOR_EACH_VEC_ELT (region
->loop_nest
, j
, loop0
)
1909 if (father
== loop0
)
1915 region
->loop_nest
.safe_push (father
);
1919 /* Call-back for dom_walk executed before visiting the dominated
1923 gather_bbs::before_dom_children (basic_block bb
)
1925 sese_info_p region
= scop
->scop_info
;
1926 if (!bb_in_sese_p (bb
, region
->region
))
1929 record_loop_in_sese (bb
, region
);
1931 gcond
*stmt
= single_pred_cond_non_loop_exit (bb
);
1935 edge e
= single_pred_edge (bb
);
1937 conditions
.safe_push (stmt
);
1939 if (e
->flags
& EDGE_TRUE_VALUE
)
1940 cases
.safe_push (stmt
);
1942 cases
.safe_push (NULL
);
1945 scop
->scop_info
->bbs
.safe_push (bb
);
1947 gimple_poly_bb_p gbb
= try_generate_gimple_bb (scop
, bb
);
1951 GBB_CONDITIONS (gbb
) = conditions
.copy ();
1952 GBB_CONDITION_CASES (gbb
) = cases
.copy ();
1954 poly_bb_p pbb
= new_poly_bb (scop
, gbb
);
1955 scop
->pbbs
.safe_push (pbb
);
1958 data_reference_p dr
;
1959 FOR_EACH_VEC_ELT (gbb
->data_refs
, i
, dr
)
1961 DEBUG_PRINT (dp
<< "Adding memory ";
1966 print_generic_expr (dump_file
, dr
->ref
, 0);
1967 dp
<< "\nFrom stmt: ";
1968 print_gimple_stmt (dump_file
, dr
->stmt
, 0, 0));
1970 scop
->drs
.safe_push (dr_info (dr
, pbb
));
1976 /* Call-back for dom_walk executed after visiting the dominated
1980 gather_bbs::after_dom_children (basic_block bb
)
1982 if (!bb_in_sese_p (bb
, scop
->scop_info
->region
))
1985 if (single_pred_cond_non_loop_exit (bb
))
1992 /* Find Static Control Parts (SCoP) in the current function and pushes
1996 build_scops (vec
<scop_p
> *scops
)
1999 dp
.set_dump_file (dump_file
);
2001 canonicalize_loop_closed_ssa_form ();
2004 sb
.build_scop_depth (scop_detection::invalid_sese
, current_loops
->tree_root
);
2006 /* Now create scops from the lightweight SESEs. */
2007 vec
<sese_l
> scops_l
= sb
.get_scops ();
2010 FOR_EACH_VEC_ELT (scops_l
, i
, s
)
2012 scop_p scop
= new_scop (s
->entry
, s
->exit
);
2014 /* Record all basic blocks and their conditions in REGION. */
2015 gather_bbs (CDI_DOMINATORS
, scop
).walk (cfun
->cfg
->x_entry_block_ptr
);
2017 build_alias_set (scop
);
2019 /* Do not optimize a scop containing only PBBs that do not belong
2021 if (sb
.nb_pbbs_in_loops (scop
) == 0)
2023 DEBUG_PRINT (dp
<< "[scop-detection-fail] no data references.\n");
2028 unsigned max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
2029 if (scop
->drs
.length () >= max_arrays
)
2031 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many data references: "
2032 << scop
->drs
.length ()
2033 << " is larger than --param graphite-max-arrays-per-scop="
2034 << max_arrays
<< ".\n");
2039 find_scop_parameters (scop
);
2040 graphite_dim_t max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
2042 if (scop_nb_params (scop
) > max_dim
)
2044 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many parameters: "
2045 << scop_nb_params (scop
)
2046 << " larger than --param graphite-max-nb-scop-params="
2047 << max_dim
<< ".\n");
2052 scops
->safe_push (scop
);
2055 DEBUG_PRINT (dp
<< "number of SCoPs: " << (scops
? scops
->length () : 0););
2058 #endif /* HAVE_isl */