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"
52 #include <isl/constraint.h>
55 #include <isl/union_map.h>
66 set_dump_file (FILE *f
)
72 friend debug_printer
&
73 operator<< (debug_printer
&output
, int i
)
75 fprintf (output
.dump_file
, "%d", i
);
78 friend debug_printer
&
79 operator<< (debug_printer
&output
, const char *s
)
81 fprintf (output
.dump_file
, "%s", s
);
86 #define DEBUG_PRINT(args) do \
88 if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \
91 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
92 different colors. If there are not enough colors, paint the
93 remaining SCoPs in gray.
96 - "*" after the node number denotes the entry of a SCoP,
97 - "#" after the node number denotes the exit of a SCoP,
98 - "()" around the node number denotes the entry or the
99 exit nodes of the SCOP. These are not part of SCoP. */
102 dot_all_sese (FILE *file
, vec
<sese_l
>& scops
)
104 /* Disable debugging while printing graph. */
105 int tmp_dump_flags
= dump_flags
;
108 fprintf (file
, "digraph all {\n");
111 FOR_ALL_BB_FN (bb
, cfun
)
113 int part_of_scop
= false;
115 /* Use HTML for every bb label. So we are able to print bbs
116 which are part of two different SCoPs, with two different
117 background colors. */
118 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
120 fprintf (file
, "CELLSPACING=\"0\">\n");
122 /* Select color for SCoP. */
125 FOR_EACH_VEC_ELT (scops
, i
, region
)
127 bool sese_in_region
= bb_in_sese_p (bb
, *region
);
128 if (sese_in_region
|| (region
->exit
->dest
== bb
)
129 || (region
->entry
->dest
== bb
))
189 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
193 fprintf (file
, " (");
195 if (bb
== region
->entry
->dest
&& bb
== region
->exit
->dest
)
196 fprintf (file
, " %d*# ", bb
->index
);
197 else if (bb
== region
->entry
->dest
)
198 fprintf (file
, " %d* ", bb
->index
);
199 else if (bb
== region
->exit
->dest
)
200 fprintf (file
, " %d# ", bb
->index
);
202 fprintf (file
, " %d ", bb
->index
);
204 fprintf (file
, "{lp_%d}", bb
->loop_father
->num
);
209 fprintf (file
, "</TD></TR>\n");
216 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
217 fprintf (file
, " %d {lp_%d} </TD></TR>\n", bb
->index
,
218 bb
->loop_father
->num
);
220 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
223 FOR_ALL_BB_FN (bb
, cfun
)
227 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
228 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
231 fputs ("}\n\n", file
);
233 /* Enable debugging again. */
234 dump_flags
= tmp_dump_flags
;
237 /* Display SCoP on stderr. */
240 dot_sese (sese_l
& scop
)
246 scops
.safe_push (scop
);
248 dot_all_sese (stderr
, scops
);
258 dot_all_sese (stderr
, scops
);
262 /* Return true if BB is empty, contains only DEBUG_INSNs. */
265 trivially_empty_bb_p (basic_block bb
)
267 gimple_stmt_iterator gsi
;
269 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
270 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_DEBUG
)
276 /* Returns true when P1 and P2 are close phis with the same
280 same_close_phi_node (gphi
*p1
, gphi
*p2
)
282 return operand_equal_p (gimple_phi_arg_def (p1
, 0),
283 gimple_phi_arg_def (p2
, 0), 0);
286 static void make_close_phi_nodes_unique (basic_block bb
);
288 /* Remove the close phi node at GSI and replace its rhs with the rhs
292 remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
)
296 imm_use_iterator imm_iter
;
297 tree res
= gimple_phi_result (phi
);
298 tree def
= gimple_phi_result (gsi
->phi ());
300 gcc_assert (same_close_phi_node (phi
, gsi
->phi ()));
302 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
304 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
305 SET_USE (use_p
, res
);
307 update_stmt (use_stmt
);
309 /* It is possible that we just created a duplicate close-phi
310 for an already-processed containing loop. Check for this
311 case and clean it up. */
312 if (gimple_code (use_stmt
) == GIMPLE_PHI
313 && gimple_phi_num_args (use_stmt
) == 1)
314 make_close_phi_nodes_unique (gimple_bb (use_stmt
));
317 remove_phi_node (gsi
, true);
320 /* Removes all the close phi duplicates from BB. */
323 make_close_phi_nodes_unique (basic_block bb
)
327 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
329 gphi_iterator gsi
= psi
;
330 gphi
*phi
= psi
.phi ();
332 /* At this point, PHI should be a close phi in normal form. */
333 gcc_assert (gimple_phi_num_args (phi
) == 1);
335 /* Iterate over the next phis and remove duplicates. */
337 while (!gsi_end_p (gsi
))
338 if (same_close_phi_node (phi
, gsi
.phi ()))
339 remove_duplicate_close_phi (phi
, &gsi
);
345 /* Transforms LOOP to the canonical loop closed SSA form. */
348 canonicalize_loop_closed_ssa (loop_p loop
)
350 edge e
= single_exit (loop
);
353 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
358 if (single_pred_p (bb
))
360 e
= split_block_after_labels (bb
);
361 DEBUG_PRINT (dp
<< "Splitting bb_" << bb
->index
<< ".\n");
362 make_close_phi_nodes_unique (e
->src
);
367 basic_block close
= split_edge (e
);
369 e
= single_succ_edge (close
);
370 DEBUG_PRINT (dp
<< "Splitting edge (" << e
->src
->index
<< ","
371 << e
->dest
->index
<< ")\n");
373 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
375 gphi
*phi
= psi
.phi ();
378 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
379 if (gimple_phi_arg_edge (phi
, i
) == e
)
381 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
385 if (TREE_CODE (arg
) != SSA_NAME
)
388 close_phi
= create_phi_node (NULL_TREE
, close
);
389 res
= create_new_def_for (arg
, close_phi
,
390 gimple_phi_result_ptr (close_phi
));
391 add_phi_arg (close_phi
, arg
,
392 gimple_phi_arg_edge (close_phi
, 0),
394 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
395 replace_exp (use_p
, res
);
400 make_close_phi_nodes_unique (close
);
403 /* The code above does not properly handle changes in the post dominance
404 information (yet). */
405 recompute_all_dominators ();
408 /* Converts the current loop closed SSA form to a canonical form
409 expected by the Graphite code generation.
411 The loop closed SSA form has the following invariant: a variable
412 defined in a loop that is used outside the loop appears only in the
413 phi nodes in the destination of the loop exit. These phi nodes are
414 called close phi nodes.
416 The canonical loop closed SSA form contains the extra invariants:
418 - when the loop contains only one exit, the close phi nodes contain
419 only one argument. That implies that the basic block that contains
420 the close phi nodes has only one predecessor, that is a basic block
423 - the basic block containing the close phi nodes does not contain
426 - there exist only one phi node per definition in the loop.
430 canonicalize_loop_closed_ssa_form (void)
432 checking_verify_loop_closed_ssa (true);
435 FOR_EACH_LOOP (loop
, 0)
436 canonicalize_loop_closed_ssa (loop
);
438 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
439 update_ssa (TODO_update_ssa
);
441 checking_verify_loop_closed_ssa (true);
444 /* Can all ivs be represented by a signed integer?
445 As ISL might generate negative values in its expressions, signed loop ivs
446 are required in the backend. */
449 loop_ivs_can_be_represented (loop_p loop
)
451 unsigned type_long_long
= TYPE_PRECISION (long_long_integer_type_node
);
452 for (gphi_iterator psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
);
455 gphi
*phi
= psi
.phi ();
456 tree res
= PHI_RESULT (phi
);
457 tree type
= TREE_TYPE (res
);
459 if (TYPE_UNSIGNED (type
) && TYPE_PRECISION (type
) >= type_long_long
)
466 /* Returns a COND_EXPR statement when BB has a single predecessor, the
467 edge between BB and its predecessor is not a loop exit edge, and
468 the last statement of the single predecessor is a COND_EXPR. */
471 single_pred_cond_non_loop_exit (basic_block bb
)
473 if (single_pred_p (bb
))
475 edge e
= single_pred_edge (bb
);
476 basic_block pred
= e
->src
;
479 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
482 stmt
= last_stmt (pred
);
484 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
485 return as_a
<gcond
*> (stmt
);
494 /* Build the maximal scop containing LOOPs and add it to SCOPS. */
499 scop_detection () : scops (vNULL
) {}
506 /* A marker for invalid sese_l. */
507 static sese_l invalid_sese
;
509 /* Return the SCOPS in this SCOP_DETECTION. */
517 /* Return an sese_l around the LOOP. */
519 sese_l
get_sese (loop_p loop
);
521 /* Return the closest dominator with a single entry edge. In case of a
522 back-loop the back-edge is not counted. */
524 static edge
get_nearest_dom_with_single_entry (basic_block dom
);
526 /* Return the closest post-dominator with a single exit edge. In case of a
527 back-loop the back-edge is not counted. */
529 static edge
get_nearest_pdom_with_single_exit (basic_block dom
);
532 /* Pretty printers. */
534 static void print_edge (FILE *file
, const_edge e
)
536 fprintf (file
, "edge (bb_%d, bb_%d)", e
->src
->index
, e
->dest
->index
);
539 static void print_sese (FILE *file
, sese_l s
)
541 fprintf (file
, "(entry_"); print_edge (file
, s
.entry
);
542 fprintf (file
, ", exit_"); print_edge (file
, s
.exit
);
543 fprintf (file
, ")\n");
546 /* Merge scops at same loop depth and returns the new sese.
547 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
549 sese_l
merge_sese (sese_l first
, sese_l second
) const;
551 /* Build scop outer->inner if possible. */
553 sese_l
build_scop_depth (sese_l s
, loop_p loop
);
555 /* If loop and loop->next are valid scops, try to merge them. */
557 sese_l
build_scop_breadth (sese_l s1
, loop_p loop
);
559 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
560 region of code that can be represented in the polyhedral model. SCOP
561 defines the region we analyse. */
563 bool loop_is_valid_scop (loop_p loop
, sese_l scop
) const;
565 /* Return true when BEGIN is the preheader edge of a loop with a single exit
568 static bool region_has_one_loop (sese_l s
);
570 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
572 void add_scop (sese_l s
);
574 /* Returns true if S1 subsumes/surrounds S2. */
575 static bool subsumes (sese_l s1
, sese_l s2
);
577 /* Remove a SCoP which is subsumed by S1. */
578 void remove_subscops (sese_l s1
);
580 /* Returns true if S1 intersects with S2. Since we already know that S1 does
581 not subsume S2 or vice-versa, we only check for entry bbs. */
583 static bool intersects (sese_l s1
, sese_l s2
);
585 /* Remove one of the scops when it intersects with any other. */
587 void remove_intersecting_scops (sese_l s1
);
589 /* Return true when the body of LOOP has statements that can be represented
592 bool loop_body_is_valid_scop (loop_p loop
, sese_l scop
) const;
594 /* Return true when BB contains a harmful operation for a scop: that
595 can be a function call with side effects, the induction variables
596 are not linear with respect to SCOP, etc. The current open
597 scop should end before this statement. */
599 bool harmful_stmt_in_bb (sese_l scop
, basic_block bb
) const;
601 /* Return true when a statement in SCOP cannot be represented by Graphite.
602 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
603 Limit the number of bbs between adjacent loops to
604 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
606 bool harmful_stmt_in_region (sese_l scop
) const;
608 /* Return true only when STMT is simple enough for being handled by Graphite.
609 This depends on SCOP, as the parameters are initialized relatively to
610 this basic block, the linear functions are initialized based on the
611 outermost loop containing STMT inside the SCOP. BB is the place where we
612 try to evaluate the STMT. */
614 bool stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
615 basic_block bb
) const;
617 /* Something like "n * m" is not allowed. */
619 static bool graphite_can_represent_init (tree e
);
621 /* Return true when SCEV can be represented in the polyhedral model.
623 An expression can be represented, if it can be expressed as an
624 affine expression. For loops (i, j) and parameters (m, n) all
625 affine expressions are of the form:
627 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
629 1 i + 20 j + (-2) m + 25
631 Something like "i * n" or "n * m" is not allowed. */
633 static bool graphite_can_represent_scev (tree scev
);
635 /* Return true when EXPR can be represented in the polyhedral model.
637 This means an expression can be represented, if it is linear with respect
638 to the loops and the strides are non parametric. LOOP is the place where
639 the expr will be evaluated. SCOP defines the region we analyse. */
641 static bool graphite_can_represent_expr (sese_l scop
, loop_p loop
,
644 /* Return true if the data references of STMT can be represented by Graphite.
645 We try to analyze the data references in a loop contained in the SCOP. */
647 static bool stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
);
649 /* Remove the close phi node at GSI and replace its rhs with the rhs
652 static void remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
);
654 /* Returns true when Graphite can represent LOOP in SCOP.
655 FIXME: For the moment, graphite cannot be used on loops that iterate using
656 induction variables that wrap. */
658 static bool can_represent_loop_1 (loop_p loop
, sese_l scop
);
660 /* Return true when all the loops within LOOP can be represented by
663 static bool can_represent_loop (loop_p loop
, sese_l scop
);
665 /* Returns the number of pbbs that are in loops contained in SCOP. */
667 static int nb_pbbs_in_loops (scop_p scop
);
669 static bool graphite_can_represent_stmt (sese_l
, gimple
*, basic_block
);
675 sese_l
scop_detection::invalid_sese (NULL
, NULL
);
677 /* Return an sese_l around the LOOP. */
680 scop_detection::get_sese (loop_p loop
)
685 if (!loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
))
687 edge scop_end
= single_exit (loop
);
690 edge scop_begin
= loop_preheader_edge (loop
);
691 sese_l
s (scop_begin
, scop_end
);
695 /* Return the closest dominator with a single entry edge. */
698 scop_detection::get_nearest_dom_with_single_entry (basic_block dom
)
702 /* If e1->src dominates e2->src then e1->src will also dominate dom. */
703 if (dom
->preds
->length () == 2)
705 edge e1
= (*dom
->preds
)[0];
706 edge e2
= (*dom
->preds
)[1];
707 loop_p l
= dom
->loop_father
;
708 loop_p l1
= e1
->src
->loop_father
;
709 loop_p l2
= e2
->src
->loop_father
;
711 && dominated_by_p (CDI_DOMINATORS
, e2
->src
, e1
->src
))
714 && dominated_by_p (CDI_DOMINATORS
, e1
->src
, e2
->src
))
718 while (dom
->preds
->length () != 1)
720 if (dom
->preds
->length () < 1)
722 dom
= get_immediate_dominator (CDI_DOMINATORS
, dom
);
726 return (*dom
->preds
)[0];
729 /* Return the closest post-dominator with a single exit edge. In case of a
730 back-loop the back-edge is not counted. */
733 scop_detection::get_nearest_pdom_with_single_exit (basic_block pdom
)
737 if (pdom
->succs
->length () == 2)
739 edge e1
= (*pdom
->succs
)[0];
740 edge e2
= (*pdom
->succs
)[1];
741 loop_p l
= pdom
->loop_father
;
742 loop_p l1
= e1
->dest
->loop_father
;
743 loop_p l2
= e2
->dest
->loop_father
;
745 && dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, e1
->dest
))
748 && dominated_by_p (CDI_POST_DOMINATORS
, e1
->dest
, e2
->dest
))
752 while (pdom
->succs
->length () != 1)
754 if (pdom
->succs
->length () < 1)
756 pdom
= get_immediate_dominator (CDI_POST_DOMINATORS
, pdom
);
761 return (*pdom
->succs
)[0];
764 /* Merge scops at same loop depth and returns the new sese.
765 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
768 scop_detection::merge_sese (sese_l first
, sese_l second
) const
770 /* In the trivial case first/second may be NULL. */
776 DEBUG_PRINT (dp
<< "[try-merging-sese] s1: "; print_sese (dump_file
, first
);
777 dp
<< "[try-merging-sese] s2: ";
778 print_sese (dump_file
, second
));
780 /* Assumption: Both the sese's should be at the same loop depth or one scop
781 should subsume the other like in case of nested loops. */
783 /* Find the common dominators for entry,
784 and common post-dominators for the exit. */
785 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
,
786 get_entry_bb (first
),
787 get_entry_bb (second
));
789 edge entry
= get_nearest_dom_with_single_entry (dom
);
791 if (!entry
|| (entry
->flags
& EDGE_IRREDUCIBLE_LOOP
))
794 basic_block pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
,
796 get_exit_bb (second
));
797 pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
, dom
, pdom
);
799 edge exit
= get_nearest_pdom_with_single_exit (pdom
);
801 if (!exit
|| (exit
->flags
& EDGE_IRREDUCIBLE_LOOP
))
804 sese_l
combined (entry
, exit
);
806 DEBUG_PRINT (dp
<< "checking combined sese: ";
807 print_sese (dump_file
, combined
));
809 /* FIXME: We could iterate to find the dom which dominates pdom, and pdom
810 which post-dominates dom, until it stabilizes. Also, ENTRY->SRC and
811 EXIT->DEST should be in the same loop nest. */
812 if (!dominated_by_p (CDI_DOMINATORS
, pdom
, dom
)
813 || loop_depth (entry
->src
->loop_father
)
814 != loop_depth (exit
->dest
->loop_father
))
817 /* For now we just want to bail out when exit does not post-dominate entry.
818 TODO: We might just add a basic_block at the exit to make exit
819 post-dominate entry (the entire region). */
820 if (!dominated_by_p (CDI_POST_DOMINATORS
, get_entry_bb (combined
),
821 get_exit_bb (combined
))
822 || !dominated_by_p (CDI_DOMINATORS
, get_exit_bb (combined
),
823 get_entry_bb (combined
)))
825 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
829 /* FIXME: We should remove this piece of code once
830 canonicalize_loop_closed_ssa has been removed, because that function
831 adds a BB with single exit. */
832 if (!trivially_empty_bb_p (get_exit_bb (combined
)))
834 /* Find the first empty succ (with single exit) of combined.exit. */
835 basic_block imm_succ
= combined
.exit
->dest
;
836 if (single_succ_p (imm_succ
) && trivially_empty_bb_p (imm_succ
))
837 combined
.exit
= single_succ_edge (imm_succ
);
840 DEBUG_PRINT (dp
<< "[scop-detection-fail] Discarding SCoP because "
841 << "no single exit (empty succ) for sese exit";
842 print_sese (dump_file
, combined
));
847 /* Analyze all the BBs in new sese. */
848 if (harmful_stmt_in_region (combined
))
851 DEBUG_PRINT (dp
<< "[merged-sese] s1: "; print_sese (dump_file
, combined
));
856 /* Build scop outer->inner if possible. */
859 scop_detection::build_scop_depth (sese_l s
, loop_p loop
)
864 DEBUG_PRINT (dp
<< "[Depth loop_" << loop
->num
<< "]\n");
865 s
= build_scop_depth (s
, loop
->inner
);
867 sese_l s2
= merge_sese (s
, get_sese (loop
));
870 /* s might be a valid scop, so return it and start analyzing from the
872 build_scop_depth (invalid_sese
, loop
->next
);
876 if (!loop_is_valid_scop (loop
, s2
))
877 return build_scop_depth (invalid_sese
, loop
->next
);
879 return build_scop_breadth (s2
, loop
);
882 /* If loop and loop->next are valid scops, try to merge them. */
885 scop_detection::build_scop_breadth (sese_l s1
, loop_p loop
)
889 DEBUG_PRINT (dp
<< "[Breadth loop_" << loop
->num
<< "]\n");
893 sese_l s2
= build_scop_depth (invalid_sese
, l
->next
);
901 sese_l combined
= merge_sese (s1
, s2
);
913 /* Returns true when Graphite can represent LOOP in SCOP.
914 FIXME: For the moment, graphite cannot be used on loops that iterate using
915 induction variables that wrap. */
918 scop_detection::can_represent_loop_1 (loop_p loop
, sese_l scop
)
921 struct tree_niter_desc niter_desc
;
923 return single_exit (loop
)
924 && !(loop_preheader_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
)
925 && number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
926 && niter_desc
.control
.no_overflow
927 && (niter
= number_of_latch_executions (loop
))
928 && !chrec_contains_undetermined (niter
)
929 && graphite_can_represent_expr (scop
, loop
, niter
);
932 /* Return true when all the loops within LOOP can be represented by
936 scop_detection::can_represent_loop (loop_p loop
, sese_l scop
)
938 if (!can_represent_loop_1 (loop
, scop
))
940 if (loop
->inner
&& !can_represent_loop (loop
->inner
, scop
))
942 if (loop
->next
&& !can_represent_loop (loop
->next
, scop
))
948 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
949 region of code that can be represented in the polyhedral model. SCOP
950 defines the region we analyse. */
953 scop_detection::loop_is_valid_scop (loop_p loop
, sese_l scop
) const
958 if (!optimize_loop_nest_for_speed_p (loop
))
960 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_"
961 << loop
->num
<< " is not on a hot path.\n");
965 if (!can_represent_loop (loop
, scop
))
967 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot represent loop_"
968 << loop
->num
<< "\n");
972 if (loop_body_is_valid_scop (loop
, scop
))
974 DEBUG_PRINT (dp
<< "[valid-scop] loop_" << loop
->num
975 << " is a valid scop.\n");
981 /* Return true when BEGIN is the preheader edge of a loop with a single exit
985 scop_detection::region_has_one_loop (sese_l s
)
987 edge begin
= s
.entry
;
989 /* Check for a single perfectly nested loop. */
990 if (begin
->dest
->loop_father
->inner
)
993 /* Otherwise, check whether we have adjacent loops. */
994 return begin
->dest
->loop_father
== end
->src
->loop_father
;
997 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
1000 scop_detection::add_scop (sese_l s
)
1004 /* Do not add scops with only one loop. */
1005 if (region_has_one_loop (s
))
1007 DEBUG_PRINT (dp
<< "[scop-detection-fail] Discarding one loop SCoP.\n";
1008 print_sese (dump_file
, s
));
1012 if (get_exit_bb (s
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1014 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1015 << "Discarding SCoP exiting to return.";
1016 print_sese (dump_file
, s
));
1020 /* Remove all the scops which are subsumed by s. */
1021 remove_subscops (s
);
1023 /* Replace this with split-intersecting scops. */
1024 remove_intersecting_scops (s
);
1026 scops
.safe_push (s
);
1027 DEBUG_PRINT (dp
<< "Adding SCoP "; print_sese (dump_file
, s
));
1030 /* Return true when a statement in SCOP cannot be represented by Graphite.
1031 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
1032 Limit the number of bbs between adjacent loops to
1033 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
1036 scop_detection::harmful_stmt_in_region (sese_l scop
) const
1038 basic_block exit_bb
= get_exit_bb (scop
);
1039 basic_block entry_bb
= get_entry_bb (scop
);
1041 DEBUG_PRINT (dp
<< "[checking-harmful-bbs] ";
1042 print_sese (dump_file
, scop
));
1043 gcc_assert (dominated_by_p (CDI_DOMINATORS
, exit_bb
, entry_bb
));
1045 int depth
= bb_dom_dfs_in (CDI_DOMINATORS
, exit_bb
)
1046 - bb_dom_dfs_in (CDI_DOMINATORS
, entry_bb
);
1048 gcc_assert (depth
> 0);
1050 vec
<basic_block
> dom
1051 = get_dominated_to_depth (CDI_DOMINATORS
, entry_bb
, depth
);
1054 FOR_EACH_VEC_ELT (dom
, i
, bb
)
1056 DEBUG_PRINT (dp
<< "Visiting bb_" << bb
->index
<< "\n");
1058 /* We don't want to analyze any bb outside sese. */
1059 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb
, exit_bb
))
1062 /* Basic blocks dominated by the scop->exit are not in the scop. */
1063 if (bb
!= exit_bb
&& dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
1066 /* The basic block should not be part of an irreducible loop. */
1067 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1073 if (harmful_stmt_in_bb (scop
, bb
))
1084 /* Returns true if S1 subsumes/surrounds S2. */
1086 scop_detection::subsumes (sese_l s1
, sese_l s2
)
1088 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
1090 && dominated_by_p (CDI_POST_DOMINATORS
, s2
.exit
->dest
,
1096 /* Remove a SCoP which is subsumed by S1. */
1098 scop_detection::remove_subscops (sese_l s1
)
1102 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
1104 if (subsumes (s1
, *s2
))
1106 DEBUG_PRINT (dp
<< "Removing sub-SCoP";
1107 print_sese (dump_file
, *s2
));
1108 scops
.unordered_remove (j
);
1113 /* Returns true if S1 intersects with S2. Since we already know that S1 does
1114 not subsume S2 or vice-versa, we only check for entry bbs. */
1117 scop_detection::intersects (sese_l s1
, sese_l s2
)
1119 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
1121 && !dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
1124 if ((s1
.exit
== s2
.entry
) || (s2
.exit
== s1
.entry
))
1130 /* Remove one of the scops when it intersects with any other. */
1133 scop_detection::remove_intersecting_scops (sese_l s1
)
1137 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
1139 if (intersects (s1
, *s2
))
1141 DEBUG_PRINT (dp
<< "Removing intersecting SCoP";
1142 print_sese (dump_file
, *s2
);
1143 dp
<< "Intersects with:";
1144 print_sese (dump_file
, s1
));
1145 scops
.unordered_remove (j
);
1150 /* Something like "n * m" is not allowed. */
1153 scop_detection::graphite_can_represent_init (tree e
)
1155 switch (TREE_CODE (e
))
1157 case POLYNOMIAL_CHREC
:
1158 return graphite_can_represent_init (CHREC_LEFT (e
))
1159 && graphite_can_represent_init (CHREC_RIGHT (e
));
1162 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1163 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
1164 && tree_fits_shwi_p (TREE_OPERAND (e
, 1));
1166 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
1167 && tree_fits_shwi_p (TREE_OPERAND (e
, 0));
1170 case POINTER_PLUS_EXPR
:
1172 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
1173 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
1178 case NON_LVALUE_EXPR
:
1179 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
1188 /* Return true when SCEV can be represented in the polyhedral model.
1190 An expression can be represented, if it can be expressed as an
1191 affine expression. For loops (i, j) and parameters (m, n) all
1192 affine expressions are of the form:
1194 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
1196 1 i + 20 j + (-2) m + 25
1198 Something like "i * n" or "n * m" is not allowed. */
1201 scop_detection::graphite_can_represent_scev (tree scev
)
1203 if (chrec_contains_undetermined (scev
))
1206 /* We disable the handling of pointer types, because it’s currently not
1207 supported by Graphite with the ISL AST generator. SSA_NAME nodes are
1208 the only nodes, which are disabled in case they are pointers to object
1209 types, but this can be changed. */
1211 if (POINTER_TYPE_P (TREE_TYPE (scev
)) && TREE_CODE (scev
) == SSA_NAME
)
1214 switch (TREE_CODE (scev
))
1219 case NON_LVALUE_EXPR
:
1220 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0));
1223 case POINTER_PLUS_EXPR
:
1225 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1226 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1229 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
1230 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
1231 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
1232 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
1233 && graphite_can_represent_init (scev
)
1234 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1235 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1237 case POLYNOMIAL_CHREC
:
1238 /* Check for constant strides. With a non constant stride of
1239 'n' we would have a value of 'iv * n'. Also check that the
1240 initial value can represented: for example 'n * m' cannot be
1242 if (!evolution_function_right_is_integer_cst (scev
)
1243 || !graphite_can_represent_init (scev
))
1245 return graphite_can_represent_scev (CHREC_LEFT (scev
));
1251 /* Only affine functions can be represented. */
1252 if (tree_contains_chrecs (scev
, NULL
) || !scev_is_linear_expression (scev
))
1258 /* Return true when EXPR can be represented in the polyhedral model.
1260 This means an expression can be represented, if it is linear with respect to
1261 the loops and the strides are non parametric. LOOP is the place where the
1262 expr will be evaluated. SCOP defines the region we analyse. */
1265 scop_detection::graphite_can_represent_expr (sese_l scop
, loop_p loop
,
1268 tree scev
= scalar_evolution_in_region (scop
, loop
, expr
);
1269 return graphite_can_represent_scev (scev
);
1272 /* Return true if the data references of STMT can be represented by Graphite.
1273 We try to analyze the data references in a loop contained in the SCOP. */
1276 scop_detection::stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
)
1278 loop_p nest
= outermost_loop_in_sese (scop
, gimple_bb (stmt
));
1279 loop_p loop
= loop_containing_stmt (stmt
);
1280 vec
<data_reference_p
> drs
= vNULL
;
1282 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1285 data_reference_p dr
;
1286 FOR_EACH_VEC_ELT (drs
, j
, dr
)
1288 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1290 if (nb_subscripts
< 1)
1292 free_data_refs (drs
);
1296 tree ref
= DR_REF (dr
);
1298 for (int i
= nb_subscripts
- 1; i
>= 0; i
--)
1300 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
))
1301 || (TREE_CODE (ref
) != ARRAY_REF
&& TREE_CODE (ref
) != MEM_REF
1302 && TREE_CODE (ref
) != COMPONENT_REF
))
1304 free_data_refs (drs
);
1308 ref
= TREE_OPERAND (ref
, 0);
1312 free_data_refs (drs
);
1316 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1317 Calls have side-effects, except those to const or pure
1321 stmt_has_side_effects (gimple
*stmt
)
1323 if (gimple_has_volatile_ops (stmt
)
1324 || (gimple_code (stmt
) == GIMPLE_CALL
1325 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
1326 || (gimple_code (stmt
) == GIMPLE_ASM
))
1328 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1329 << "Statement has side-effects:\n";
1330 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1336 /* Returns true if STMT can be represented in polyhedral model. LABEL,
1337 simple COND stmts, pure calls, and assignments can be repesented. */
1340 scop_detection::graphite_can_represent_stmt (sese_l scop
, gimple
*stmt
,
1343 loop_p loop
= bb
->loop_father
;
1344 switch (gimple_code (stmt
))
1351 /* We can handle all binary comparisons. Inequalities are
1352 also supported as they can be represented with union of
1354 enum tree_code code
= gimple_cond_code (stmt
);
1355 if (!(code
== LT_EXPR
1360 || code
== NE_EXPR
))
1362 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1363 << "Graphite cannot handle cond stmt:\n";
1364 print_gimple_stmt (dump_file
, stmt
, 0,
1365 TDF_VOPS
| TDF_MEMSYMS
));
1369 for (unsigned i
= 0; i
< 2; ++i
)
1371 tree op
= gimple_op (stmt
, i
);
1372 if (!graphite_can_represent_expr (scop
, loop
, op
)
1373 /* We can only constrain on integer type. */
1374 || (TREE_CODE (TREE_TYPE (op
)) != INTEGER_TYPE
))
1376 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1377 << "Graphite cannot represent stmt:\n";
1378 print_gimple_stmt (dump_file
, stmt
, 0,
1379 TDF_VOPS
| TDF_MEMSYMS
));
1392 /* These nodes cut a new scope. */
1394 dp
<< "[scop-detection-fail] "
1395 << "Gimple stmt not handled in Graphite:\n";
1396 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1401 /* Return true only when STMT is simple enough for being handled by Graphite.
1402 This depends on SCOP, as the parameters are initialized relatively to
1403 this basic block, the linear functions are initialized based on the outermost
1404 loop containing STMT inside the SCOP. BB is the place where we try to
1405 evaluate the STMT. */
1408 scop_detection::stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
1409 basic_block bb
) const
1413 if (is_gimple_debug (stmt
))
1416 if (stmt_has_side_effects (stmt
))
1419 if (!stmt_has_simple_data_refs_p (scop
, stmt
))
1421 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1422 << "Graphite cannot handle data-refs in stmt:\n";
1423 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
););
1427 return graphite_can_represent_stmt (scop
, stmt
, bb
);
1430 /* Return true when BB contains a harmful operation for a scop: that
1431 can be a function call with side effects, the induction variables
1432 are not linear with respect to SCOP, etc. The current open
1433 scop should end before this statement. */
1436 scop_detection::harmful_stmt_in_bb (sese_l scop
, basic_block bb
) const
1438 gimple_stmt_iterator gsi
;
1440 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1441 if (!stmt_simple_for_scop_p (scop
, gsi_stmt (gsi
), bb
))
1447 /* Return true when the body of LOOP has statements that can be represented as a
1451 scop_detection::loop_body_is_valid_scop (loop_p loop
, sese_l scop
) const
1453 if (!loop_ivs_can_be_represented (loop
))
1455 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
1456 << "IV cannot be represented.\n");
1460 if (!loop_nest_has_data_refs (loop
))
1462 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
1463 << "does not have any data reference.\n");
1467 basic_block
*bbs
= get_loop_body (loop
);
1468 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
1470 basic_block bb
= bbs
[i
];
1472 if (harmful_stmt_in_bb (scop
, bb
))
1482 if (!loop_body_is_valid_scop (loop
, scop
))
1491 /* Returns the number of pbbs that are in loops contained in SCOP. */
1494 scop_detection::nb_pbbs_in_loops (scop_p scop
)
1500 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1501 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), scop
->scop_info
->region
))
1507 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
1508 Otherwise returns -1. */
1511 parameter_index_in_region_1 (tree name
, sese_info_p region
)
1516 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1518 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
1525 /* When the parameter NAME is in REGION, returns its index in
1526 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
1527 and returns the index of NAME. */
1530 parameter_index_in_region (tree name
, sese_info_p region
)
1534 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1536 /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
1537 if (TREE_CODE (TREE_TYPE (name
)) != INTEGER_TYPE
)
1540 if (!invariant_in_sese_p_rec (name
, region
->region
, NULL
))
1543 i
= parameter_index_in_region_1 (name
, region
);
1547 i
= region
->params
.length ();
1548 region
->params
.safe_push (name
);
1552 /* In the context of sese S, scan the expression E and translate it to
1553 a linear expression C. When parsing a symbolic multiplication, K
1554 represents the constant multiplier of an expression containing
1558 scan_tree_for_params (sese_info_p s
, tree e
)
1560 if (e
== chrec_dont_know
)
1563 switch (TREE_CODE (e
))
1565 case POLYNOMIAL_CHREC
:
1566 scan_tree_for_params (s
, CHREC_LEFT (e
));
1570 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1571 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1573 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1577 case POINTER_PLUS_EXPR
:
1579 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1580 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1586 case NON_LVALUE_EXPR
:
1587 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1591 parameter_index_in_region (e
, s
);
1607 /* Find parameters with respect to REGION in BB. We are looking in memory
1608 access functions, conditions and loop bounds. */
1611 find_params_in_bb (sese_info_p region
, gimple_poly_bb_p gbb
)
1613 /* Find parameters in the access functions of data references. */
1615 data_reference_p dr
;
1616 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
1617 for (unsigned j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
1618 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
1620 /* Find parameters in conditional statements. */
1622 loop_p loop
= GBB_BB (gbb
)->loop_father
;
1623 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1625 tree lhs
= scalar_evolution_in_region (region
->region
, loop
,
1626 gimple_cond_lhs (stmt
));
1627 tree rhs
= scalar_evolution_in_region (region
->region
, loop
,
1628 gimple_cond_rhs (stmt
));
1630 scan_tree_for_params (region
, lhs
);
1631 scan_tree_for_params (region
, rhs
);
1635 /* Record the parameters used in the SCOP. A variable is a parameter
1636 in a scop if it does not vary during the execution of that scop. */
1639 find_scop_parameters (scop_p scop
)
1642 sese_info_p region
= scop
->scop_info
;
1645 /* Find the parameters used in the loop bounds. */
1646 FOR_EACH_VEC_ELT (region
->loop_nest
, i
, loop
)
1648 tree nb_iters
= number_of_latch_executions (loop
);
1650 if (!chrec_contains_symbols (nb_iters
))
1653 nb_iters
= scalar_evolution_in_region (region
->region
, loop
, nb_iters
);
1654 scan_tree_for_params (region
, nb_iters
);
1657 /* Find the parameters used in data accesses. */
1659 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1660 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1662 int nbp
= sese_nb_params (region
);
1663 scop_set_nb_params (scop
, nbp
);
1666 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1669 build_cross_bb_scalars_def (scop_p scop
, tree def
, basic_block def_bb
,
1673 if (!is_gimple_reg (def
))
1676 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1677 generated out of the induction variables. */
1678 if (scev_analyzable_p (def
, scop
->scop_info
->region
))
1682 imm_use_iterator imm_iter
;
1683 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1684 if (def_bb
!= gimple_bb (use_stmt
) && !is_gimple_debug (use_stmt
))
1686 writes
->safe_push (def
);
1687 DEBUG_PRINT (dp
<< "Adding scalar write: ";
1688 print_generic_expr (dump_file
, def
, 0);
1689 dp
<< "\nFrom stmt: ";
1690 print_gimple_stmt (dump_file
,
1691 SSA_NAME_DEF_STMT (def
), 0, 0));
1692 /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
1693 before all the uses have been visited. */
1694 BREAK_FROM_IMM_USE_STMT (imm_iter
);
1698 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1701 build_cross_bb_scalars_use (scop_p scop
, tree use
, gimple
*use_stmt
,
1702 vec
<scalar_use
> *reads
)
1705 if (!is_gimple_reg (use
))
1708 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1709 generated out of the induction variables. */
1710 if (scev_analyzable_p (use
, scop
->scop_info
->region
))
1713 gimple
*def_stmt
= SSA_NAME_DEF_STMT (use
);
1714 if (gimple_bb (def_stmt
) != gimple_bb (use_stmt
))
1716 DEBUG_PRINT (dp
<< "Adding scalar read: ";
1717 print_generic_expr (dump_file
, use
, 0);
1718 dp
<< "\nFrom stmt: ";
1719 print_gimple_stmt (dump_file
, use_stmt
, 0, 0));
1720 reads
->safe_push (std::make_pair (use_stmt
, use
));
1724 /* Record all scalar variables that are defined and used in different BBs of the
1728 graphite_find_cross_bb_scalar_vars (scop_p scop
, gimple
*stmt
,
1729 vec
<scalar_use
> *reads
, vec
<tree
> *writes
)
1733 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
1734 def
= gimple_assign_lhs (stmt
);
1735 else if (gimple_code (stmt
) == GIMPLE_CALL
)
1736 def
= gimple_call_lhs (stmt
);
1737 else if (gimple_code (stmt
) == GIMPLE_PHI
)
1738 def
= gimple_phi_result (stmt
);
1743 build_cross_bb_scalars_def (scop
, def
, gimple_bb (stmt
), writes
);
1746 use_operand_p use_p
;
1747 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1749 tree use
= USE_FROM_PTR (use_p
);
1750 build_cross_bb_scalars_use (scop
, use
, stmt
, reads
);
1754 /* Generates a polyhedral black box only if the bb contains interesting
1757 static gimple_poly_bb_p
1758 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
1760 vec
<data_reference_p
> drs
= vNULL
;
1761 vec
<tree
> writes
= vNULL
;
1762 vec
<scalar_use
> reads
= vNULL
;
1764 sese_l region
= scop
->scop_info
->region
;
1765 loop_p nest
= outermost_loop_in_sese (region
, bb
);
1767 loop_p loop
= bb
->loop_father
;
1768 if (!loop_in_sese_p (loop
, region
))
1771 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1774 gimple
*stmt
= gsi_stmt (gsi
);
1775 if (is_gimple_debug (stmt
))
1778 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1779 graphite_find_cross_bb_scalar_vars (scop
, stmt
, &reads
, &writes
);
1782 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1784 if (!virtual_operand_p (gimple_phi_result (psi
.phi ())))
1785 graphite_find_cross_bb_scalar_vars (scop
, psi
.phi (), &reads
, &writes
);
1787 if (drs
.is_empty () && writes
.is_empty () && reads
.is_empty ())
1790 return new_gimple_poly_bb (bb
, drs
, reads
, writes
);
1793 /* Compute alias-sets for all data references in DRS. */
1796 build_alias_set (scop_p scop
)
1798 int num_vertices
= scop
->drs
.length ();
1799 struct graph
*g
= new_graph (num_vertices
);
1804 FOR_EACH_VEC_ELT (scop
->drs
, i
, dr1
)
1805 for (j
= i
+1; scop
->drs
.iterate (j
, &dr2
); j
++)
1806 if (dr_may_alias_p (dr1
->dr
, dr2
->dr
, true))
1812 all_vertices
= XNEWVEC (int, num_vertices
);
1813 for (i
= 0; i
< num_vertices
; i
++)
1814 all_vertices
[i
] = i
;
1816 graphds_dfs (g
, all_vertices
, num_vertices
, NULL
, true, NULL
);
1817 free (all_vertices
);
1819 for (i
= 0; i
< g
->n_vertices
; i
++)
1820 scop
->drs
[i
].alias_set
= g
->vertices
[i
].component
+ 1;
1825 /* Gather BBs and conditions for a SCOP. */
1826 class gather_bbs
: public dom_walker
1829 gather_bbs (cdi_direction
, scop_p
);
1831 virtual edge
before_dom_children (basic_block
);
1832 virtual void after_dom_children (basic_block
);
1835 auto_vec
<gimple
*, 3> conditions
, cases
;
1839 gather_bbs::gather_bbs (cdi_direction direction
, scop_p scop
)
1840 : dom_walker (direction
), scop (scop
)
1844 /* Call-back for dom_walk executed before visiting the dominated
1848 gather_bbs::before_dom_children (basic_block bb
)
1850 if (!bb_in_sese_p (bb
, scop
->scop_info
->region
))
1853 gcond
*stmt
= single_pred_cond_non_loop_exit (bb
);
1857 edge e
= single_pred_edge (bb
);
1859 conditions
.safe_push (stmt
);
1861 if (e
->flags
& EDGE_TRUE_VALUE
)
1862 cases
.safe_push (stmt
);
1864 cases
.safe_push (NULL
);
1867 scop
->scop_info
->bbs
.safe_push (bb
);
1869 gimple_poly_bb_p gbb
= try_generate_gimple_bb (scop
, bb
);
1873 GBB_CONDITIONS (gbb
) = conditions
.copy ();
1874 GBB_CONDITION_CASES (gbb
) = cases
.copy ();
1876 poly_bb_p pbb
= new_poly_bb (scop
, gbb
);
1877 scop
->pbbs
.safe_push (pbb
);
1880 data_reference_p dr
;
1881 FOR_EACH_VEC_ELT (gbb
->data_refs
, i
, dr
)
1883 DEBUG_PRINT (dp
<< "Adding memory ";
1888 print_generic_expr (dump_file
, dr
->ref
, 0);
1889 dp
<< "\nFrom stmt: ";
1890 print_gimple_stmt (dump_file
, dr
->stmt
, 0, 0));
1892 scop
->drs
.safe_push (dr_info (dr
, pbb
));
1898 /* Call-back for dom_walk executed after visiting the dominated
1902 gather_bbs::after_dom_children (basic_block bb
)
1904 if (!bb_in_sese_p (bb
, scop
->scop_info
->region
))
1907 if (single_pred_cond_non_loop_exit (bb
))
1914 /* Find Static Control Parts (SCoP) in the current function and pushes
1918 build_scops (vec
<scop_p
> *scops
)
1921 dp
.set_dump_file (dump_file
);
1923 canonicalize_loop_closed_ssa_form ();
1926 sb
.build_scop_depth (scop_detection::invalid_sese
, current_loops
->tree_root
);
1928 /* Now create scops from the lightweight SESEs. */
1929 vec
<sese_l
> scops_l
= sb
.get_scops ();
1932 FOR_EACH_VEC_ELT (scops_l
, i
, s
)
1934 scop_p scop
= new_scop (s
->entry
, s
->exit
);
1936 /* Record all basic blocks and their conditions in REGION. */
1937 gather_bbs (CDI_DOMINATORS
, scop
).walk (cfun
->cfg
->x_entry_block_ptr
);
1939 build_alias_set (scop
);
1941 /* Do not optimize a scop containing only PBBs that do not belong
1943 if (sb
.nb_pbbs_in_loops (scop
) == 0)
1945 DEBUG_PRINT (dp
<< "[scop-detection-fail] no data references.\n");
1950 unsigned max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
1951 if (scop
->drs
.length () >= max_arrays
)
1953 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many data references: "
1954 << scop
->drs
.length ()
1955 << " is larger than --param graphite-max-arrays-per-scop="
1956 << max_arrays
<< ".\n");
1961 build_sese_loop_nests (scop
->scop_info
);
1963 find_scop_parameters (scop
);
1964 graphite_dim_t max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
1966 if (scop_nb_params (scop
) > max_dim
)
1968 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many parameters: "
1969 << scop_nb_params (scop
)
1970 << " larger than --param graphite-max-nb-scop-params="
1971 << max_dim
<< ".\n");
1976 scops
->safe_push (scop
);
1979 DEBUG_PRINT (dp
<< "number of SCoPs: " << (scops
? scops
->length () : 0););
1982 #endif /* HAVE_isl */