1 /* Detection of Static Control Parts (SCoP) for Graphite.
2 Copyright (C) 2009-2015 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and
4 Tobias Grosser <grosser@fim.uni-passau.de>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
25 /* Workaround for GMP 5.1.3 bug, see PR56019. */
28 #include <isl/constraint.h>
31 #include <isl/union_map.h>
34 #include "coretypes.h"
42 #include "fold-const.h"
43 #include "gimple-iterator.h"
45 #include "tree-ssa-loop-manip.h"
46 #include "tree-ssa-loop-niter.h"
47 #include "tree-ssa-loop.h"
48 #include "tree-into-ssa.h"
51 #include "tree-data-ref.h"
52 #include "tree-scalar-evolution.h"
53 #include "tree-pass.h"
54 #include "graphite-poly.h"
55 #include "tree-ssa-propagate.h"
56 #include "graphite-scop-detection.h"
57 #include "gimple-pretty-print.h"
66 set_dump_file (FILE *f
)
72 friend debug_printer
&
73 operator<< (debug_printer
&output
, int i
)
75 fprintf (output
.dump_file
, "%d", i
);
78 friend debug_printer
&
79 operator<< (debug_printer
&output
, const char *s
)
81 fprintf (output
.dump_file
, "%s", s
);
86 #define DEBUG_PRINT(args) do \
88 if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \
91 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
92 different colors. If there are not enough colors, paint the
93 remaining SCoPs in gray.
96 - "*" after the node number denotes the entry of a SCoP,
97 - "#" after the node number denotes the exit of a SCoP,
98 - "()" around the node number denotes the entry or the
99 exit nodes of the SCOP. These are not part of SCoP. */
102 dot_all_scops_1 (FILE *file
, vec
<scop_p
> scops
)
111 /* Disable debugging while printing graph. */
112 int tmp_dump_flags
= dump_flags
;
115 fprintf (file
, "digraph all {\n");
117 FOR_ALL_BB_FN (bb
, cfun
)
119 int part_of_scop
= false;
121 /* Use HTML for every bb label. So we are able to print bbs
122 which are part of two different SCoPs, with two different
123 background colors. */
124 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
126 fprintf (file
, "CELLSPACING=\"0\">\n");
128 /* Select color for SCoP. */
129 FOR_EACH_VEC_ELT (scops
, i
, scop
)
131 sese_l region
= scop
->scop_info
->region
;
132 if (bb_in_sese_p (bb
, region
) || (region
.exit
->dest
== bb
)
133 || (region
.entry
->dest
== bb
))
192 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
195 if (!bb_in_sese_p (bb
, region
))
196 fprintf (file
, " (");
198 if (bb
== region
.entry
->dest
&& bb
== region
.exit
->dest
)
199 fprintf (file
, " %d*# ", bb
->index
);
200 else if (bb
== region
.entry
->dest
)
201 fprintf (file
, " %d* ", bb
->index
);
202 else if (bb
== region
.exit
->dest
)
203 fprintf (file
, " %d# ", bb
->index
);
205 fprintf (file
, " %d ", bb
->index
);
207 fprintf (file
, "{lp_%d}", bb
->loop_father
->num
);
209 if (!bb_in_sese_p (bb
, region
))
212 fprintf (file
, "</TD></TR>\n");
219 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
220 fprintf (file
, " %d {lp_%d} </TD></TR>\n", bb
->index
,
221 bb
->loop_father
->num
);
223 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
226 FOR_ALL_BB_FN (bb
, cfun
)
228 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
229 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
232 fputs ("}\n\n", file
);
234 /* Enable debugging again. */
235 dump_flags
= tmp_dump_flags
;
238 /* Display all SCoPs using dotty. */
241 dot_all_scops (vec
<scop_p
> scops
)
243 /* When debugging, enable the following code. This cannot be used
244 in production compilers because it calls "system". */
247 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
250 dot_all_scops_1 (stream
, scops
);
253 x
= system ("dotty /tmp/allscops.dot &");
255 dot_all_scops_1 (stderr
, scops
);
259 /* Display all SCoPs using dotty. */
262 dot_scop (scop_p scop
)
264 auto_vec
<scop_p
, 1> scops
;
267 scops
.safe_push (scop
);
269 /* When debugging, enable the following code. This cannot be used
270 in production compilers because it calls "system". */
274 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
277 dot_all_scops_1 (stream
, scops
);
279 x
= system ("dotty /tmp/allscops.dot &");
282 dot_all_scops_1 (stderr
, scops
);
286 /* Return true if BB is empty, contains only DEBUG_INSNs. */
289 trivially_empty_bb_p (basic_block bb
)
291 gimple_stmt_iterator gsi
;
293 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
294 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_DEBUG
)
300 /* Returns true when P1 and P2 are close phis with the same
304 same_close_phi_node (gphi
*p1
, gphi
*p2
)
306 return operand_equal_p (gimple_phi_arg_def (p1
, 0),
307 gimple_phi_arg_def (p2
, 0), 0);
310 static void make_close_phi_nodes_unique (basic_block bb
);
312 /* Remove the close phi node at GSI and replace its rhs with the rhs
316 remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
)
320 imm_use_iterator imm_iter
;
321 tree res
= gimple_phi_result (phi
);
322 tree def
= gimple_phi_result (gsi
->phi ());
324 gcc_assert (same_close_phi_node (phi
, gsi
->phi ()));
326 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
328 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
329 SET_USE (use_p
, res
);
331 update_stmt (use_stmt
);
333 /* It is possible that we just created a duplicate close-phi
334 for an already-processed containing loop. Check for this
335 case and clean it up. */
336 if (gimple_code (use_stmt
) == GIMPLE_PHI
337 && gimple_phi_num_args (use_stmt
) == 1)
338 make_close_phi_nodes_unique (gimple_bb (use_stmt
));
341 remove_phi_node (gsi
, true);
344 /* Removes all the close phi duplicates from BB. */
347 make_close_phi_nodes_unique (basic_block bb
)
351 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
353 gphi_iterator gsi
= psi
;
354 gphi
*phi
= psi
.phi ();
356 /* At this point, PHI should be a close phi in normal form. */
357 gcc_assert (gimple_phi_num_args (phi
) == 1);
359 /* Iterate over the next phis and remove duplicates. */
361 while (!gsi_end_p (gsi
))
362 if (same_close_phi_node (phi
, gsi
.phi ()))
363 remove_duplicate_close_phi (phi
, &gsi
);
369 /* Transforms LOOP to the canonical loop closed SSA form. */
372 canonicalize_loop_closed_ssa (loop_p loop
)
374 edge e
= single_exit (loop
);
377 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
382 if (single_pred_p (bb
))
384 e
= split_block_after_labels (bb
);
385 DEBUG_PRINT (dp
<< "\nSplitting bb_" << bb
->index
);
386 make_close_phi_nodes_unique (e
->src
);
391 basic_block close
= split_edge (e
);
393 e
= single_succ_edge (close
);
394 DEBUG_PRINT (dp
<< "\nSplitting edge (" << e
->src
->index
<< ","
395 << e
->dest
->index
<< ")\n");
397 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
399 gphi
*phi
= psi
.phi ();
402 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
403 if (gimple_phi_arg_edge (phi
, i
) == e
)
405 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
409 if (TREE_CODE (arg
) != SSA_NAME
)
412 close_phi
= create_phi_node (NULL_TREE
, close
);
413 res
= create_new_def_for (arg
, close_phi
,
414 gimple_phi_result_ptr (close_phi
));
415 add_phi_arg (close_phi
, arg
,
416 gimple_phi_arg_edge (close_phi
, 0),
418 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
419 replace_exp (use_p
, res
);
424 make_close_phi_nodes_unique (close
);
427 /* The code above does not properly handle changes in the post dominance
428 information (yet). */
429 recompute_all_dominators ();
432 /* Converts the current loop closed SSA form to a canonical form
433 expected by the Graphite code generation.
435 The loop closed SSA form has the following invariant: a variable
436 defined in a loop that is used outside the loop appears only in the
437 phi nodes in the destination of the loop exit. These phi nodes are
438 called close phi nodes.
440 The canonical loop closed SSA form contains the extra invariants:
442 - when the loop contains only one exit, the close phi nodes contain
443 only one argument. That implies that the basic block that contains
444 the close phi nodes has only one predecessor, that is a basic block
447 - the basic block containing the close phi nodes does not contain
450 - there exist only one phi node per definition in the loop.
454 canonicalize_loop_closed_ssa_form (void)
456 checking_verify_loop_closed_ssa (true);
459 FOR_EACH_LOOP (loop
, 0)
460 canonicalize_loop_closed_ssa (loop
);
462 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
463 update_ssa (TODO_update_ssa
);
465 checking_verify_loop_closed_ssa (true);
468 /* Can all ivs be represented by a signed integer?
469 As ISL might generate negative values in its expressions, signed loop ivs
470 are required in the backend. */
473 loop_ivs_can_be_represented (loop_p loop
)
475 unsigned type_long_long
= TYPE_PRECISION (long_long_integer_type_node
);
476 for (gphi_iterator psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
);
479 gphi
*phi
= psi
.phi ();
480 tree res
= PHI_RESULT (phi
);
481 tree type
= TREE_TYPE (res
);
483 if (TYPE_UNSIGNED (type
) && TYPE_PRECISION (type
) >= type_long_long
)
490 /* Returns a COND_EXPR statement when BB has a single predecessor, the
491 edge between BB and its predecessor is not a loop exit edge, and
492 the last statement of the single predecessor is a COND_EXPR. */
495 single_pred_cond_non_loop_exit (basic_block bb
)
497 if (single_pred_p (bb
))
499 edge e
= single_pred_edge (bb
);
500 basic_block pred
= e
->src
;
503 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
506 stmt
= last_stmt (pred
);
508 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
509 return as_a
<gcond
*> (stmt
);
518 /* Build the maximal scop containing LOOPs and add it to SCOPS. */
523 scop_detection () : scops (vNULL
) {}
525 /* A marker for invalid sese_l. */
526 static sese_l invalid_sese
;
528 /* Return the SCOPS in this SCOP_DETECTION. */
536 /* Return an sese_l around the LOOP. */
538 sese_l
get_sese (loop_p loop
);
540 /* Return the closest dominator with a single entry edge. In case of a
541 back-loop the back-edge is not counted. */
543 static edge
get_nearest_dom_with_single_entry (basic_block dom
);
545 /* Return the closest post-dominator with a single exit edge. In case of a
546 back-loop the back-edge is not counted. */
548 static edge
get_nearest_pdom_with_single_exit (basic_block dom
);
550 /* Print S to FILE. */
552 static void print_sese (FILE *file
, sese_l s
);
554 /* Merge scops at same loop depth and returns the new sese.
555 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
557 sese_l
merge_sese (sese_l first
, sese_l second
) const;
559 /* Build scop outer->inner if possible. */
561 sese_l
build_scop_depth (sese_l s
, loop_p loop
);
563 /* If loop and loop->next are valid scops, try to merge them. */
565 sese_l
build_scop_breadth (sese_l s1
, loop_p loop
);
567 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
568 region of code that can be represented in the polyhedral model. SCOP
569 defines the region we analyse. */
571 bool loop_is_valid_scop (loop_p loop
, sese_l scop
) const;
573 /* Return true when BEGIN is the preheader edge of a loop with a single exit
576 static bool region_has_one_loop (sese_l s
);
578 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
580 void add_scop (sese_l s
);
582 /* Returns true if S1 subsumes/surrounds S2. */
583 static bool subsumes (sese_l s1
, sese_l s2
);
585 /* Remove a SCoP which is subsumed by S1. */
586 void remove_subscops (sese_l s1
);
588 /* Returns true if S1 intersects with S2. Since we already know that S1 does
589 not subsume S2 or vice-versa, we only check for entry bbs. */
591 static bool intersects (sese_l s1
, sese_l s2
);
593 /* Remove one of the scops when it intersects with any other. */
595 void remove_intersecting_scops (sese_l s1
);
597 /* Return true when the body of LOOP has statements that can be represented
600 bool loop_body_is_valid_scop (loop_p loop
, sese_l scop
) const;
602 /* Return true when BB contains a harmful operation for a scop: that
603 can be a function call with side effects, the induction variables
604 are not linear with respect to SCOP, etc. The current open
605 scop should end before this statement. */
607 bool harmful_stmt_in_bb (sese_l scop
, basic_block bb
) const;
609 /* Return true when a statement in SCOP cannot be represented by Graphite.
610 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
611 Limit the number of bbs between adjacent loops to
612 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
614 bool harmful_stmt_in_region (sese_l scop
) const;
616 /* Return true only when STMT is simple enough for being handled by Graphite.
617 This depends on SCOP, as the parameters are initialized relatively to
618 this basic block, the linear functions are initialized based on the
619 outermost loop containing STMT inside the SCOP. BB is the place where we
620 try to evaluate the STMT. */
622 bool stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
623 basic_block bb
) const;
625 /* Something like "n * m" is not allowed. */
627 static bool graphite_can_represent_init (tree e
);
629 /* Return true when SCEV can be represented in the polyhedral model.
631 An expression can be represented, if it can be expressed as an
632 affine expression. For loops (i, j) and parameters (m, n) all
633 affine expressions are of the form:
635 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
637 1 i + 20 j + (-2) m + 25
639 Something like "i * n" or "n * m" is not allowed. */
641 static bool graphite_can_represent_scev (tree scev
);
643 /* Return true when EXPR can be represented in the polyhedral model.
645 This means an expression can be represented, if it is linear with respect
646 to the loops and the strides are non parametric. LOOP is the place where
647 the expr will be evaluated. SCOP defines the region we analyse. */
649 static bool graphite_can_represent_expr (sese_l scop
, loop_p loop
,
652 /* Return true if the data references of STMT can be represented by Graphite.
653 We try to analyze the data references in a loop contained in the SCOP. */
655 static bool stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
);
657 /* Remove the close phi node at GSI and replace its rhs with the rhs
660 static void remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
);
662 /* Returns true when Graphite can represent LOOP in SCOP.
663 FIXME: For the moment, graphite cannot be used on loops that iterate using
664 induction variables that wrap. */
666 static bool can_represent_loop_1 (loop_p loop
, sese_l scop
);
668 /* Return true when all the loops within LOOP can be represented by
671 static bool can_represent_loop (loop_p loop
, sese_l scop
);
673 /* Returns the number of pbbs that are in loops contained in SCOP. */
675 static int nb_pbbs_in_loops (scop_p scop
);
677 static bool graphite_can_represent_stmt (sese_l
, gimple
*, basic_block
);
683 sese_l
scop_detection::invalid_sese (NULL
, NULL
);
685 /* Return an sese_l around the LOOP. */
688 scop_detection::get_sese (loop_p loop
)
693 if (!loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
))
695 edge scop_end
= single_exit (loop
);
698 edge scop_begin
= loop_preheader_edge (loop
);
699 sese_l
s (scop_begin
, scop_end
);
703 /* Return the closest dominator with a single entry edge. */
706 scop_detection::get_nearest_dom_with_single_entry (basic_block dom
)
710 /* If e1->src dominates e2->src then e1->src will also dominate dom. */
711 if (dom
->preds
->length () == 2)
713 edge e1
= (*dom
->preds
)[0];
714 edge e2
= (*dom
->preds
)[1];
715 if (dominated_by_p (CDI_DOMINATORS
, e2
->src
, e1
->src
))
717 if (dominated_by_p (CDI_DOMINATORS
, e1
->src
, e2
->src
))
721 while (dom
->preds
->length () != 1)
723 if (dom
->preds
->length () < 1)
725 dom
= get_immediate_dominator (CDI_DOMINATORS
, dom
);
729 return (*dom
->preds
)[0];
732 /* Return the closest post-dominator with a single exit edge. In case of a
733 back-loop the back-edge is not counted. */
736 scop_detection::get_nearest_pdom_with_single_exit (basic_block dom
)
740 if (dom
->succs
->length () == 2)
742 edge e1
= (*dom
->succs
)[0];
743 edge e2
= (*dom
->succs
)[1];
744 if (dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, e1
->dest
))
746 if (dominated_by_p (CDI_POST_DOMINATORS
, e1
->dest
, e2
->dest
))
750 while (dom
->succs
->length () != 1)
752 if (dom
->succs
->length () < 1)
754 dom
= get_immediate_dominator (CDI_POST_DOMINATORS
, dom
);
758 return (*dom
->succs
)[0];
761 /* Print S to FILE. */
764 scop_detection::print_sese (FILE *file
, sese_l s
)
766 fprintf (file
, "(entry_edge (bb_%d, bb_%d), exit_edge (bb_%d, bb_%d))\n",
767 s
.entry
->src
->index
, s
.entry
->dest
->index
,
768 s
.exit
->src
->index
, s
.exit
->dest
->index
);
771 /* Merge scops at same loop depth and returns the new sese.
772 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
775 scop_detection::merge_sese (sese_l first
, sese_l second
) const
777 /* In the trivial case first/second may be NULL. */
783 DEBUG_PRINT (dp
<< "[try-merging-sese] s1: "; print_sese (dump_file
, first
);
784 dp
<< "[try-merging-sese] s2: ";
785 print_sese (dump_file
, second
));
787 /* Assumption: Both the sese's should be at the same loop depth or one scop
788 should subsume the other like in case of nested loops. */
790 /* Find the common dominators for entry,
791 and common post-dominators for the exit. */
792 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
,
793 get_entry_bb (first
),
794 get_entry_bb (second
));
796 edge entry
= get_nearest_dom_with_single_entry (dom
);
798 if (!entry
|| (entry
->flags
& EDGE_IRREDUCIBLE_LOOP
))
801 basic_block pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
,
803 get_exit_bb (second
));
804 pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
, dom
, pdom
);
806 edge exit
= get_nearest_pdom_with_single_exit (pdom
);
808 if (!exit
|| (exit
->flags
& EDGE_IRREDUCIBLE_LOOP
))
811 sese_l
combined (entry
, exit
);
813 /* FIXME: We could iterate to find the dom which dominates pdom, and pdom
814 which post-dominates dom, until it stabilizes. Also, ENTRY->SRC and
815 EXIT->DEST should be in the same loop nest. */
816 if (!dominated_by_p (CDI_DOMINATORS
, pdom
, dom
)
817 || loop_depth (entry
->src
->loop_father
)
818 != loop_depth (exit
->dest
->loop_father
))
821 /* For now we just want to bail out when exit does not post-dominate entry.
822 TODO: We might just add a basic_block at the exit to make exit
823 post-dominate entry (the entire region). */
824 if (!dominated_by_p (CDI_POST_DOMINATORS
, get_entry_bb (combined
),
825 get_exit_bb (combined
))
826 || !dominated_by_p (CDI_DOMINATORS
, get_exit_bb (combined
),
827 get_entry_bb (combined
)))
829 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
833 /* FIXME: We should remove this piece of code once
834 canonicalize_loop_closed_ssa has been removed, because that function
835 adds a BB with single exit. */
836 if (!trivially_empty_bb_p (get_exit_bb (combined
)))
838 /* Find the first empty succ (with single exit) of combined.exit. */
839 basic_block imm_succ
= combined
.exit
->dest
;
840 if (single_succ_p (imm_succ
) && trivially_empty_bb_p (imm_succ
))
841 combined
.exit
= single_succ_edge (imm_succ
);
844 DEBUG_PRINT (dp
<< "\n[scop-detection-fail] Discarding SCoP because "
845 << "no single exit (empty succ) for sese exit";
846 print_sese (dump_file
, combined
));
851 /* Analyze all the BBs in new sese. */
852 if (harmful_stmt_in_region (combined
))
855 DEBUG_PRINT (dp
<< "[merged-sese] s1: "; print_sese (dump_file
, combined
));
860 /* Build scop outer->inner if possible. */
863 scop_detection::build_scop_depth (sese_l s
, loop_p loop
)
868 DEBUG_PRINT (dp
<< "\n[Depth loop_" << loop
->num
<< "]");
869 s
= build_scop_depth (s
, loop
->inner
);
871 sese_l s2
= merge_sese (s
, get_sese (loop
));
874 /* s might be a valid scop, so return it and start analyzing from the
876 build_scop_depth (invalid_sese
, loop
->next
);
880 if (!loop_is_valid_scop (loop
, s2
))
881 return build_scop_depth (invalid_sese
, loop
->next
);
883 return build_scop_breadth (s2
, loop
);
886 /* If loop and loop->next are valid scops, try to merge them. */
889 scop_detection::build_scop_breadth (sese_l s1
, loop_p loop
)
893 DEBUG_PRINT (dp
<< "\n[Breadth loop_" << loop
->num
<< "]");
897 sese_l s2
= build_scop_depth (invalid_sese
, l
->next
);
905 sese_l combined
= merge_sese (s1
, s2
);
917 /* Returns true when Graphite can represent LOOP in SCOP.
918 FIXME: For the moment, graphite cannot be used on loops that iterate using
919 induction variables that wrap. */
922 scop_detection::can_represent_loop_1 (loop_p loop
, sese_l scop
)
925 struct tree_niter_desc niter_desc
;
927 return single_exit (loop
)
928 && !(loop_preheader_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
)
929 && number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
930 && niter_desc
.control
.no_overflow
931 && (niter
= number_of_latch_executions (loop
))
932 && !chrec_contains_undetermined (niter
)
933 && graphite_can_represent_expr (scop
, loop
, niter
);
936 /* Return true when all the loops within LOOP can be represented by
940 scop_detection::can_represent_loop (loop_p loop
, sese_l scop
)
942 if (!can_represent_loop_1 (loop
, scop
))
944 if (loop
->inner
&& !can_represent_loop (loop
->inner
, scop
))
946 if (loop
->next
&& !can_represent_loop (loop
->next
, scop
))
952 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
953 region of code that can be represented in the polyhedral model. SCOP
954 defines the region we analyse. */
957 scop_detection::loop_is_valid_scop (loop_p loop
, sese_l scop
) const
962 if (!optimize_loop_nest_for_speed_p (loop
))
964 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_"
965 << loop
->num
<< " is not on a hot path.\n");
969 if (!can_represent_loop (loop
, scop
))
971 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot represent loop_"
972 << loop
->num
<< "\n");
976 if (loop_body_is_valid_scop (loop
, scop
))
978 DEBUG_PRINT (dp
<< "[valid-scop] loop_" << loop
->num
979 << "is a valid scop.\n");
985 /* Return true when BEGIN is the preheader edge of a loop with a single exit
989 scop_detection::region_has_one_loop (sese_l s
)
991 edge begin
= s
.entry
;
993 /* Check for a single perfectly nested loop. */
994 if (begin
->dest
->loop_father
->inner
)
997 /* Otherwise, check whether we have adjacent loops. */
998 return begin
->dest
->loop_father
== end
->src
->loop_father
;
1001 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
1004 scop_detection::add_scop (sese_l s
)
1008 /* Do not add scops with only one loop. */
1009 if (region_has_one_loop (s
))
1011 DEBUG_PRINT (dp
<< "\n[scop-detection-fail] Discarding one loop SCoP";
1012 print_sese (dump_file
, s
));
1016 if (get_exit_bb (s
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1018 DEBUG_PRINT (dp
<< "\n[scop-detection-fail] "
1019 << "Discarding SCoP exiting to return";
1020 print_sese (dump_file
, s
));
1024 /* Remove all the scops which are subsumed by s. */
1025 remove_subscops (s
);
1027 /* Replace this with split-intersecting scops. */
1028 remove_intersecting_scops (s
);
1030 scops
.safe_push (s
);
1031 DEBUG_PRINT (dp
<< "\nAdding SCoP "; print_sese (dump_file
, s
));
1034 /* Return true when a statement in SCOP cannot be represented by Graphite.
1035 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
1036 Limit the number of bbs between adjacent loops to
1037 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
1040 scop_detection::harmful_stmt_in_region (sese_l scop
) const
1042 basic_block exit_bb
= get_exit_bb (scop
);
1043 basic_block entry_bb
= get_entry_bb (scop
);
1045 DEBUG_PRINT (dp
<< "\n[checking-harmful-bbs] ";
1046 print_sese (dump_file
, scop
));
1047 gcc_assert (dominated_by_p (CDI_DOMINATORS
, exit_bb
, entry_bb
));
1049 int depth
= bb_dom_dfs_in (CDI_DOMINATORS
, exit_bb
)
1050 - bb_dom_dfs_in (CDI_DOMINATORS
, entry_bb
);
1052 gcc_assert (depth
> 0);
1054 vec
<basic_block
> dom
1055 = get_dominated_to_depth (CDI_DOMINATORS
, entry_bb
, depth
);
1058 FOR_EACH_VEC_ELT (dom
, i
, bb
)
1060 DEBUG_PRINT (dp
<< "\nVisiting bb_" << bb
->index
);
1062 /* We don't want to analyze any bb outside sese. */
1063 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb
, exit_bb
))
1066 /* The basic block should not be part of an irreducible loop. */
1067 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1070 if (harmful_stmt_in_bb (scop
, bb
))
1077 /* Returns true if S1 subsumes/surrounds S2. */
1079 scop_detection::subsumes (sese_l s1
, sese_l s2
)
1081 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
1083 && dominated_by_p (CDI_POST_DOMINATORS
, s2
.exit
->dest
,
1089 /* Remove a SCoP which is subsumed by S1. */
1091 scop_detection::remove_subscops (sese_l s1
)
1095 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
1097 if (subsumes (s1
, *s2
))
1099 DEBUG_PRINT (dp
<< "\nRemoving sub-SCoP";
1100 print_sese (dump_file
, *s2
));
1101 scops
.unordered_remove (j
);
1106 /* Returns true if S1 intersects with S2. Since we already know that S1 does
1107 not subsume S2 or vice-versa, we only check for entry bbs. */
1110 scop_detection::intersects (sese_l s1
, sese_l s2
)
1112 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
1114 && !dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
1117 if ((s1
.exit
== s2
.entry
) || (s2
.exit
== s1
.entry
))
1123 /* Remove one of the scops when it intersects with any other. */
1126 scop_detection::remove_intersecting_scops (sese_l s1
)
1130 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
1132 if (intersects (s1
, *s2
))
1134 DEBUG_PRINT (dp
<< "\nRemoving intersecting SCoP";
1135 print_sese (dump_file
, *s2
); dp
<< "Intersects with:";
1136 print_sese (dump_file
, s1
));
1137 scops
.unordered_remove (j
);
1142 /* Something like "n * m" is not allowed. */
1145 scop_detection::graphite_can_represent_init (tree e
)
1147 switch (TREE_CODE (e
))
1149 case POLYNOMIAL_CHREC
:
1150 return graphite_can_represent_init (CHREC_LEFT (e
))
1151 && graphite_can_represent_init (CHREC_RIGHT (e
));
1154 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1155 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
1156 && tree_fits_shwi_p (TREE_OPERAND (e
, 1));
1158 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
1159 && tree_fits_shwi_p (TREE_OPERAND (e
, 0));
1162 case POINTER_PLUS_EXPR
:
1164 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
1165 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
1170 case NON_LVALUE_EXPR
:
1171 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
1180 /* Return true when SCEV can be represented in the polyhedral model.
1182 An expression can be represented, if it can be expressed as an
1183 affine expression. For loops (i, j) and parameters (m, n) all
1184 affine expressions are of the form:
1186 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
1188 1 i + 20 j + (-2) m + 25
1190 Something like "i * n" or "n * m" is not allowed. */
1193 scop_detection::graphite_can_represent_scev (tree scev
)
1195 if (chrec_contains_undetermined (scev
))
1198 /* We disable the handling of pointer types, because it’s currently not
1199 supported by Graphite with the ISL AST generator. SSA_NAME nodes are
1200 the only nodes, which are disabled in case they are pointers to object
1201 types, but this can be changed. */
1203 if (POINTER_TYPE_P (TREE_TYPE (scev
)) && TREE_CODE (scev
) == SSA_NAME
)
1206 switch (TREE_CODE (scev
))
1211 case NON_LVALUE_EXPR
:
1212 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0));
1215 case POINTER_PLUS_EXPR
:
1217 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1218 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1221 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
1222 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
1223 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
1224 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
1225 && graphite_can_represent_init (scev
)
1226 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1227 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1229 case POLYNOMIAL_CHREC
:
1230 /* Check for constant strides. With a non constant stride of
1231 'n' we would have a value of 'iv * n'. Also check that the
1232 initial value can represented: for example 'n * m' cannot be
1234 if (!evolution_function_right_is_integer_cst (scev
)
1235 || !graphite_can_represent_init (scev
))
1237 return graphite_can_represent_scev (CHREC_LEFT (scev
));
1243 /* Only affine functions can be represented. */
1244 if (tree_contains_chrecs (scev
, NULL
) || !scev_is_linear_expression (scev
))
1250 /* Return true when EXPR can be represented in the polyhedral model.
1252 This means an expression can be represented, if it is linear with respect to
1253 the loops and the strides are non parametric. LOOP is the place where the
1254 expr will be evaluated. SCOP defines the region we analyse. */
1257 scop_detection::graphite_can_represent_expr (sese_l scop
, loop_p loop
,
1260 tree scev
= scalar_evolution_in_region (scop
, loop
, expr
);
1261 return graphite_can_represent_scev (scev
);
1264 /* Return true if the data references of STMT can be represented by Graphite.
1265 We try to analyze the data references in a loop contained in the SCOP. */
1268 scop_detection::stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
)
1270 loop_p nest
= outermost_loop_in_sese (scop
, gimple_bb (stmt
));
1271 loop_p loop
= loop_containing_stmt (stmt
);
1272 vec
<data_reference_p
> drs
= vNULL
;
1274 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1277 data_reference_p dr
;
1278 FOR_EACH_VEC_ELT (drs
, j
, dr
)
1280 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1282 if (nb_subscripts
< 1)
1284 free_data_refs (drs
);
1288 tree ref
= DR_REF (dr
);
1290 for (int i
= nb_subscripts
- 1; i
>= 0; i
--)
1292 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
))
1293 || (TREE_CODE (ref
) != ARRAY_REF
&& TREE_CODE (ref
) != MEM_REF
1294 && TREE_CODE (ref
) != COMPONENT_REF
))
1296 free_data_refs (drs
);
1300 ref
= TREE_OPERAND (ref
, 0);
1304 free_data_refs (drs
);
1308 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1309 Calls have side-effects, except those to const or pure
1313 stmt_has_side_effects (gimple
*stmt
)
1315 if (gimple_has_volatile_ops (stmt
)
1316 || (gimple_code (stmt
) == GIMPLE_CALL
1317 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
1318 || (gimple_code (stmt
) == GIMPLE_ASM
))
1320 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1321 << "Statement has side-effects:\n";
1322 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1328 /* Returns true if STMT can be represented in polyhedral model. LABEL,
1329 simple COND stmts, pure calls, and assignments can be repesented. */
1332 scop_detection::graphite_can_represent_stmt (sese_l scop
, gimple
*stmt
,
1335 loop_p loop
= bb
->loop_father
;
1336 switch (gimple_code (stmt
))
1343 /* We can handle all binary comparisons. Inequalities are
1344 also supported as they can be represented with union of
1346 enum tree_code code
= gimple_cond_code (stmt
);
1347 if (!(code
== LT_EXPR
1352 || code
== NE_EXPR
))
1354 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1355 << "Graphite cannot handle cond stmt:\n";
1356 print_gimple_stmt (dump_file
, stmt
, 0,
1357 TDF_VOPS
| TDF_MEMSYMS
));
1361 for (unsigned i
= 0; i
< 2; ++i
)
1363 tree op
= gimple_op (stmt
, i
);
1364 if (!graphite_can_represent_expr (scop
, loop
, op
)
1365 /* We can only constrain on integer type. */
1366 || (TREE_CODE (TREE_TYPE (op
)) != INTEGER_TYPE
))
1368 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1369 << "Graphite cannot represent stmt:\n";
1370 print_gimple_stmt (dump_file
, stmt
, 0,
1371 TDF_VOPS
| TDF_MEMSYMS
));
1384 /* These nodes cut a new scope. */
1386 dp
<< "[scop-detection-fail] "
1387 << "Gimple stmt not handled in Graphite:\n";
1388 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1393 /* Return true only when STMT is simple enough for being handled by Graphite.
1394 This depends on SCOP, as the parameters are initialized relatively to
1395 this basic block, the linear functions are initialized based on the outermost
1396 loop containing STMT inside the SCOP. BB is the place where we try to
1397 evaluate the STMT. */
1400 scop_detection::stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
1401 basic_block bb
) const
1405 if (is_gimple_debug (stmt
))
1408 if (stmt_has_side_effects (stmt
))
1411 if (!stmt_has_simple_data_refs_p (scop
, stmt
))
1413 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1414 << "Graphite cannot handle data-refs in stmt:\n";
1415 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
););
1419 return graphite_can_represent_stmt (scop
, stmt
, bb
);
1422 /* Return true when BB contains a harmful operation for a scop: that
1423 can be a function call with side effects, the induction variables
1424 are not linear with respect to SCOP, etc. The current open
1425 scop should end before this statement. */
1428 scop_detection::harmful_stmt_in_bb (sese_l scop
, basic_block bb
) const
1430 gimple_stmt_iterator gsi
;
1432 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1433 if (!stmt_simple_for_scop_p (scop
, gsi_stmt (gsi
), bb
))
1439 /* Return true when the body of LOOP has statements that can be represented as a
1443 scop_detection::loop_body_is_valid_scop (loop_p loop
, sese_l scop
) const
1445 if (!loop_ivs_can_be_represented (loop
))
1447 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
1448 << "IV cannot be represented.\n");
1452 if (!loop_nest_has_data_refs (loop
))
1454 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
1455 << "does not have any data reference.\n");
1459 basic_block
*bbs
= get_loop_body (loop
);
1460 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
1462 basic_block bb
= bbs
[i
];
1464 if (harmful_stmt_in_bb (scop
, bb
))
1474 if (!loop_body_is_valid_scop (loop
, scop
))
1483 /* Returns the number of pbbs that are in loops contained in SCOP. */
1486 scop_detection::nb_pbbs_in_loops (scop_p scop
)
1492 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1493 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), scop
->scop_info
->region
))
1499 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
1500 Otherwise returns -1. */
1503 parameter_index_in_region_1 (tree name
, sese_info_p region
)
1508 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1510 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
1517 /* When the parameter NAME is in REGION, returns its index in
1518 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
1519 and returns the index of NAME. */
1522 parameter_index_in_region (tree name
, sese_info_p region
)
1526 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1528 /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
1529 if (TREE_CODE (TREE_TYPE (name
)) != INTEGER_TYPE
)
1532 if (!invariant_in_sese_p_rec (name
, region
->region
, NULL
))
1535 i
= parameter_index_in_region_1 (name
, region
);
1539 i
= region
->params
.length ();
1540 region
->params
.safe_push (name
);
1544 /* In the context of sese S, scan the expression E and translate it to
1545 a linear expression C. When parsing a symbolic multiplication, K
1546 represents the constant multiplier of an expression containing
1550 scan_tree_for_params (sese_info_p s
, tree e
)
1552 if (e
== chrec_dont_know
)
1555 switch (TREE_CODE (e
))
1557 case POLYNOMIAL_CHREC
:
1558 scan_tree_for_params (s
, CHREC_LEFT (e
));
1562 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1563 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1565 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1569 case POINTER_PLUS_EXPR
:
1571 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1572 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1578 case NON_LVALUE_EXPR
:
1579 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1583 parameter_index_in_region (e
, s
);
1599 /* Find parameters with respect to REGION in BB. We are looking in memory
1600 access functions, conditions and loop bounds. */
1603 find_params_in_bb (sese_info_p region
, gimple_poly_bb_p gbb
)
1605 /* Find parameters in the access functions of data references. */
1607 data_reference_p dr
;
1608 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
1609 for (unsigned j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
1610 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
1612 /* Find parameters in conditional statements. */
1614 loop_p loop
= GBB_BB (gbb
)->loop_father
;
1615 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1617 tree lhs
= scalar_evolution_in_region (region
->region
, loop
,
1618 gimple_cond_lhs (stmt
));
1619 tree rhs
= scalar_evolution_in_region (region
->region
, loop
,
1620 gimple_cond_rhs (stmt
));
1622 scan_tree_for_params (region
, lhs
);
1623 scan_tree_for_params (region
, rhs
);
1627 /* Record the parameters used in the SCOP. A variable is a parameter
1628 in a scop if it does not vary during the execution of that scop. */
1631 find_scop_parameters (scop_p scop
)
1634 sese_info_p region
= scop
->scop_info
;
1637 /* Find the parameters used in the loop bounds. */
1638 FOR_EACH_VEC_ELT (region
->loop_nest
, i
, loop
)
1640 tree nb_iters
= number_of_latch_executions (loop
);
1642 if (!chrec_contains_symbols (nb_iters
))
1645 nb_iters
= scalar_evolution_in_region (region
->region
, loop
, nb_iters
);
1646 scan_tree_for_params (region
, nb_iters
);
1649 /* Find the parameters used in data accesses. */
1651 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1652 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1654 int nbp
= sese_nb_params (region
);
1655 scop_set_nb_params (scop
, nbp
);
1658 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1661 build_cross_bb_scalars_def (scop_p scop
, tree def
, basic_block def_bb
,
1665 if (!is_gimple_reg (def
))
1668 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1669 generated out of the induction variables. */
1670 if (scev_analyzable_p (def
, scop
->scop_info
->region
))
1674 imm_use_iterator imm_iter
;
1675 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1676 if (def_bb
!= gimple_bb (use_stmt
) && !is_gimple_debug (use_stmt
))
1678 writes
->safe_push (def
);
1679 DEBUG_PRINT (dp
<< "Adding scalar write:\n";
1680 print_generic_expr (dump_file
, def
, 0);
1681 dp
<< "From stmt:\n";
1682 print_gimple_stmt (dump_file
,
1683 SSA_NAME_DEF_STMT (def
), 0, 0));
1684 /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
1685 before all the uses have been visited. */
1686 BREAK_FROM_IMM_USE_STMT (imm_iter
);
1690 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1693 build_cross_bb_scalars_use (scop_p scop
, tree use
, gimple
*use_stmt
,
1694 vec
<scalar_use
> *reads
)
1697 if (!is_gimple_reg (use
))
1700 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1701 generated out of the induction variables. */
1702 if (scev_analyzable_p (use
, scop
->scop_info
->region
))
1705 gimple
*def_stmt
= SSA_NAME_DEF_STMT (use
);
1706 if (gimple_bb (def_stmt
) != gimple_bb (use_stmt
))
1708 DEBUG_PRINT (dp
<< "Adding scalar read:\n";
1709 print_generic_expr (dump_file
, use
, 0);
1710 dp
<< "From stmt:\n";
1711 print_gimple_stmt (dump_file
, use_stmt
, 0, 0));
1712 reads
->safe_push (std::make_pair (use_stmt
, use
));
1716 /* Record all scalar variables that are defined and used in different BBs of the
1720 graphite_find_cross_bb_scalar_vars (scop_p scop
, gimple
*stmt
,
1721 vec
<scalar_use
> *reads
, vec
<tree
> *writes
)
1725 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
1726 def
= gimple_assign_lhs (stmt
);
1727 else if (gimple_code (stmt
) == GIMPLE_CALL
)
1728 def
= gimple_call_lhs (stmt
);
1729 else if (gimple_code (stmt
) == GIMPLE_PHI
)
1730 def
= gimple_phi_result (stmt
);
1735 build_cross_bb_scalars_def (scop
, def
, gimple_bb (stmt
), writes
);
1738 use_operand_p use_p
;
1739 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1741 tree use
= USE_FROM_PTR (use_p
);
1742 build_cross_bb_scalars_use (scop
, use
, stmt
, reads
);
1746 /* Generates a polyhedral black box only if the bb contains interesting
1749 static gimple_poly_bb_p
1750 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
1752 vec
<data_reference_p
> drs
;
1756 vec
<scalar_use
> reads
;
1759 sese_l region
= scop
->scop_info
->region
;
1760 loop_p nest
= outermost_loop_in_sese (region
, bb
);
1762 loop_p loop
= bb
->loop_father
;
1763 if (!loop_in_sese_p (loop
, region
))
1766 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1769 gimple
*stmt
= gsi_stmt (gsi
);
1770 if (is_gimple_debug (stmt
))
1773 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1774 graphite_find_cross_bb_scalar_vars (scop
, stmt
, &reads
, &writes
);
1777 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1779 if (!virtual_operand_p (gimple_phi_result (psi
.phi ())))
1780 graphite_find_cross_bb_scalar_vars (scop
, psi
.phi (), &reads
, &writes
);
1782 if (drs
.is_empty () && writes
.is_empty () && reads
.is_empty ())
1785 return new_gimple_poly_bb (bb
, drs
, reads
, writes
);
1788 /* Compute alias-sets for all data references in DRS. */
1791 build_alias_set (scop_p scop
)
1793 int num_vertices
= scop
->drs
.length ();
1794 struct graph
*g
= new_graph (num_vertices
);
1799 FOR_EACH_VEC_ELT (scop
->drs
, i
, dr1
)
1800 for (j
= i
+1; scop
->drs
.iterate (j
, &dr2
); j
++)
1801 if (dr_may_alias_p (dr1
->dr
, dr2
->dr
, true))
1807 all_vertices
= XNEWVEC (int, num_vertices
);
1808 for (i
= 0; i
< num_vertices
; i
++)
1809 all_vertices
[i
] = i
;
1811 graphds_dfs (g
, all_vertices
, num_vertices
, NULL
, true, NULL
);
1812 free (all_vertices
);
1814 for (i
= 0; i
< g
->n_vertices
; i
++)
1815 scop
->drs
[i
].alias_set
= g
->vertices
[i
].component
+ 1;
1820 /* Gather BBs and conditions for a SCOP. */
1821 class gather_bbs
: public dom_walker
1824 gather_bbs (cdi_direction
, scop_p
);
1826 virtual void before_dom_children (basic_block
);
1827 virtual void after_dom_children (basic_block
);
1830 auto_vec
<gimple
*, 3> conditions
, cases
;
1834 gather_bbs::gather_bbs (cdi_direction direction
, scop_p scop
)
1835 : dom_walker (direction
), scop (scop
)
1839 /* Call-back for dom_walk executed before visiting the dominated
1843 gather_bbs::before_dom_children (basic_block bb
)
1845 if (!bb_in_sese_p (bb
, scop
->scop_info
->region
))
1848 gcond
*stmt
= single_pred_cond_non_loop_exit (bb
);
1852 edge e
= single_pred_edge (bb
);
1854 conditions
.safe_push (stmt
);
1856 if (e
->flags
& EDGE_TRUE_VALUE
)
1857 cases
.safe_push (stmt
);
1859 cases
.safe_push (NULL
);
1862 scop
->scop_info
->bbs
.safe_push (bb
);
1864 gimple_poly_bb_p gbb
= try_generate_gimple_bb (scop
, bb
);
1868 GBB_CONDITIONS (gbb
) = conditions
.copy ();
1869 GBB_CONDITION_CASES (gbb
) = cases
.copy ();
1871 poly_bb_p pbb
= new_poly_bb (scop
, gbb
);
1872 scop
->pbbs
.safe_push (pbb
);
1875 data_reference_p dr
;
1876 FOR_EACH_VEC_ELT (gbb
->data_refs
, i
, dr
)
1877 scop
->drs
.safe_push (dr_info (dr
, pbb
));
1880 /* Call-back for dom_walk executed after visiting the dominated
1884 gather_bbs::after_dom_children (basic_block bb
)
1886 if (!bb_in_sese_p (bb
, scop
->scop_info
->region
))
1889 if (single_pred_cond_non_loop_exit (bb
))
1896 /* Find Static Control Parts (SCoP) in the current function and pushes
1900 build_scops (vec
<scop_p
> *scops
)
1903 dp
.set_dump_file (dump_file
);
1905 canonicalize_loop_closed_ssa_form ();
1908 sb
.build_scop_depth (scop_detection::invalid_sese
, current_loops
->tree_root
);
1910 /* Now create scops from the lightweight SESEs. */
1911 vec
<sese_l
> scops_l
= sb
.get_scops ();
1914 FOR_EACH_VEC_ELT (scops_l
, i
, s
)
1916 scop_p scop
= new_scop (s
->entry
, s
->exit
);
1918 /* Record all basic blocks and their conditions in REGION. */
1919 gather_bbs (CDI_DOMINATORS
, scop
).walk (cfun
->cfg
->x_entry_block_ptr
);
1921 build_alias_set (scop
);
1923 /* Do not optimize a scop containing only PBBs that do not belong
1925 if (sb
.nb_pbbs_in_loops (scop
) == 0)
1927 DEBUG_PRINT (dp
<< "[scop-detection-fail] no data references.\n");
1932 unsigned max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
1933 if (scop
->drs
.length () >= max_arrays
)
1935 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many data references: "
1936 << scop
->drs
.length ()
1937 << " is larger than --param graphite-max-arrays-per-scop="
1938 << max_arrays
<< ".\n");
1943 build_sese_loop_nests (scop
->scop_info
);
1945 find_scop_parameters (scop
);
1946 graphite_dim_t max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
1948 if (scop_nb_params (scop
) > max_dim
)
1950 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many parameters: "
1951 << scop_nb_params (scop
)
1952 << " larger than --param graphite-max-nb-scop-params="
1953 << max_dim
<< ".\n");
1958 scops
->safe_push (scop
);
1961 DEBUG_PRINT (dp
<< "number of SCoPs: " << (scops
? scops
->length () : 0););
1964 #endif /* HAVE_isl */