1 /* Detection of Static Control Parts (SCoP) for Graphite.
2 Copyright (C) 2009-2017 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 dump_flags_t tmp_dump_flags
= dump_flags
;
100 dump_flags
= TDF_NONE
;
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
265 && gimple_code (gsi_stmt (gsi
)) != GIMPLE_LABEL
)
271 /* Returns true when P1 and P2 are close phis with the same
275 same_close_phi_node (gphi
*p1
, gphi
*p2
)
277 return (types_compatible_p (TREE_TYPE (gimple_phi_result (p1
)),
278 TREE_TYPE (gimple_phi_result (p2
)))
279 && operand_equal_p (gimple_phi_arg_def (p1
, 0),
280 gimple_phi_arg_def (p2
, 0), 0));
283 static void make_close_phi_nodes_unique (basic_block bb
);
285 /* Remove the close phi node at GSI and replace its rhs with the rhs
289 remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
)
293 imm_use_iterator imm_iter
;
294 tree res
= gimple_phi_result (phi
);
295 tree def
= gimple_phi_result (gsi
->phi ());
297 gcc_assert (same_close_phi_node (phi
, gsi
->phi ()));
299 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
301 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
302 SET_USE (use_p
, res
);
304 update_stmt (use_stmt
);
306 /* It is possible that we just created a duplicate close-phi
307 for an already-processed containing loop. Check for this
308 case and clean it up. */
309 if (gimple_code (use_stmt
) == GIMPLE_PHI
310 && gimple_phi_num_args (use_stmt
) == 1)
311 make_close_phi_nodes_unique (gimple_bb (use_stmt
));
314 remove_phi_node (gsi
, true);
317 /* Removes all the close phi duplicates from BB. */
320 make_close_phi_nodes_unique (basic_block bb
)
324 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
326 gphi_iterator gsi
= psi
;
327 gphi
*phi
= psi
.phi ();
329 /* At this point, PHI should be a close phi in normal form. */
330 gcc_assert (gimple_phi_num_args (phi
) == 1);
332 /* Iterate over the next phis and remove duplicates. */
334 while (!gsi_end_p (gsi
))
335 if (same_close_phi_node (phi
, gsi
.phi ()))
336 remove_duplicate_close_phi (phi
, &gsi
);
342 /* Return true when NAME is defined in LOOP. */
345 defined_in_loop_p (tree name
, loop_p loop
)
347 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
348 return loop
== loop_containing_stmt (SSA_NAME_DEF_STMT (name
));
351 /* Transforms LOOP to the canonical loop closed SSA form. */
354 canonicalize_loop_closed_ssa (loop_p loop
)
356 edge e
= single_exit (loop
);
359 if (!e
|| (e
->flags
& EDGE_COMPLEX
))
364 if (single_pred_p (bb
))
366 e
= split_block_after_labels (bb
);
367 DEBUG_PRINT (dp
<< "Splitting bb_" << bb
->index
<< ".\n");
368 make_close_phi_nodes_unique (e
->src
);
373 basic_block close
= split_edge (e
);
375 e
= single_succ_edge (close
);
376 DEBUG_PRINT (dp
<< "Splitting edge (" << e
->src
->index
<< ","
377 << e
->dest
->index
<< ")\n");
379 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
381 gphi
*phi
= psi
.phi ();
384 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
385 if (gimple_phi_arg_edge (phi
, i
) == e
)
387 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
391 /* Only add close phi nodes for SSA_NAMEs defined in LOOP. */
392 if (TREE_CODE (arg
) != SSA_NAME
393 || !defined_in_loop_p (arg
, loop
))
396 close_phi
= create_phi_node (NULL_TREE
, close
);
397 res
= create_new_def_for (arg
, close_phi
,
398 gimple_phi_result_ptr (close_phi
));
399 add_phi_arg (close_phi
, arg
,
400 gimple_phi_arg_edge (close_phi
, 0),
402 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
403 replace_exp (use_p
, res
);
408 make_close_phi_nodes_unique (close
);
411 /* The code above does not properly handle changes in the post dominance
412 information (yet). */
413 recompute_all_dominators ();
416 /* Converts the current loop closed SSA form to a canonical form
417 expected by the Graphite code generation.
419 The loop closed SSA form has the following invariant: a variable
420 defined in a loop that is used outside the loop appears only in the
421 phi nodes in the destination of the loop exit. These phi nodes are
422 called close phi nodes.
424 The canonical loop closed SSA form contains the extra invariants:
426 - when the loop contains only one exit, the close phi nodes contain
427 only one argument. That implies that the basic block that contains
428 the close phi nodes has only one predecessor, that is a basic block
431 - the basic block containing the close phi nodes does not contain
434 - there exist only one phi node per definition in the loop.
438 canonicalize_loop_closed_ssa_form (void)
440 checking_verify_loop_closed_ssa (true);
443 FOR_EACH_LOOP (loop
, 0)
444 canonicalize_loop_closed_ssa (loop
);
446 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
447 update_ssa (TODO_update_ssa
);
449 checking_verify_loop_closed_ssa (true);
452 /* Can all ivs be represented by a signed integer?
453 As isl might generate negative values in its expressions, signed loop ivs
454 are required in the backend. */
457 loop_ivs_can_be_represented (loop_p loop
)
459 unsigned type_long_long
= TYPE_PRECISION (long_long_integer_type_node
);
460 for (gphi_iterator psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
);
463 gphi
*phi
= psi
.phi ();
464 tree res
= PHI_RESULT (phi
);
465 tree type
= TREE_TYPE (res
);
467 if (TYPE_UNSIGNED (type
) && TYPE_PRECISION (type
) >= type_long_long
)
474 /* Returns a COND_EXPR statement when BB has a single predecessor, the
475 edge between BB and its predecessor is not a loop exit edge, and
476 the last statement of the single predecessor is a COND_EXPR. */
479 single_pred_cond_non_loop_exit (basic_block bb
)
481 if (single_pred_p (bb
))
483 edge e
= single_pred_edge (bb
);
484 basic_block pred
= e
->src
;
487 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
490 stmt
= last_stmt (pred
);
492 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
493 return as_a
<gcond
*> (stmt
);
502 /* Build the maximal scop containing LOOPs and add it to SCOPS. */
507 scop_detection () : scops (vNULL
) {}
514 /* A marker for invalid sese_l. */
515 static sese_l invalid_sese
;
517 /* Return the SCOPS in this SCOP_DETECTION. */
525 /* Return an sese_l around the LOOP. */
527 sese_l
get_sese (loop_p loop
);
529 /* Return the closest dominator with a single entry edge. In case of a
530 back-loop the back-edge is not counted. */
532 static edge
get_nearest_dom_with_single_entry (basic_block dom
);
534 /* Return the closest post-dominator with a single exit edge. In case of a
535 back-loop the back-edge is not counted. */
537 static edge
get_nearest_pdom_with_single_exit (basic_block dom
);
539 /* Merge scops at same loop depth and returns the new sese.
540 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
542 sese_l
merge_sese (sese_l first
, sese_l second
) const;
544 /* Build scop outer->inner if possible. */
546 sese_l
build_scop_depth (sese_l s
, loop_p loop
);
548 /* If loop and loop->next are valid scops, try to merge them. */
550 sese_l
build_scop_breadth (sese_l s1
, loop_p loop
);
552 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
553 region of code that can be represented in the polyhedral model. SCOP
554 defines the region we analyse. */
556 bool loop_is_valid_in_scop (loop_p loop
, sese_l scop
) const;
558 /* Return true when BEGIN is the preheader edge of a loop with a single exit
561 static bool region_has_one_loop (sese_l s
);
563 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
565 void add_scop (sese_l s
);
567 /* Returns true if S1 subsumes/surrounds S2. */
568 static bool subsumes (sese_l s1
, sese_l s2
);
570 /* Remove a SCoP which is subsumed by S1. */
571 void remove_subscops (sese_l s1
);
573 /* Returns true if S1 intersects with S2. Since we already know that S1 does
574 not subsume S2 or vice-versa, we only check for entry bbs. */
576 static bool intersects (sese_l s1
, sese_l s2
);
578 /* Remove one of the scops when it intersects with any other. */
580 void remove_intersecting_scops (sese_l s1
);
582 /* Return true when the body of LOOP has statements that can be represented
585 bool loop_body_is_valid_scop (loop_p loop
, sese_l scop
) const;
587 /* Return true when BB contains a harmful operation for a scop: that
588 can be a function call with side effects, the induction variables
589 are not linear with respect to SCOP, etc. The current open
590 scop should end before this statement. */
592 bool harmful_stmt_in_bb (sese_l scop
, basic_block bb
) const;
594 /* Return true when a statement in SCOP cannot be represented by Graphite.
595 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
596 Limit the number of bbs between adjacent loops to
597 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
599 bool harmful_loop_in_region (sese_l scop
) const;
601 /* Return true only when STMT is simple enough for being handled by Graphite.
602 This depends on SCOP, as the parameters are initialized relatively to
603 this basic block, the linear functions are initialized based on the
604 outermost loop containing STMT inside the SCOP. BB is the place where we
605 try to evaluate the STMT. */
607 bool stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
608 basic_block bb
) const;
610 /* Something like "n * m" is not allowed. */
612 static bool graphite_can_represent_init (tree e
);
614 /* Return true when SCEV can be represented in the polyhedral model.
616 An expression can be represented, if it can be expressed as an
617 affine expression. For loops (i, j) and parameters (m, n) all
618 affine expressions are of the form:
620 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
622 1 i + 20 j + (-2) m + 25
624 Something like "i * n" or "n * m" is not allowed. */
626 static bool graphite_can_represent_scev (tree scev
);
628 /* Return true when EXPR can be represented in the polyhedral model.
630 This means an expression can be represented, if it is linear with respect
631 to the loops and the strides are non parametric. LOOP is the place where
632 the expr will be evaluated. SCOP defines the region we analyse. */
634 static bool graphite_can_represent_expr (sese_l scop
, loop_p loop
,
637 /* Return true if the data references of STMT can be represented by Graphite.
638 We try to analyze the data references in a loop contained in the SCOP. */
640 static bool stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
);
642 /* Remove the close phi node at GSI and replace its rhs with the rhs
645 static void remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
);
647 /* Returns true when Graphite can represent LOOP in SCOP.
648 FIXME: For the moment, graphite cannot be used on loops that iterate using
649 induction variables that wrap. */
651 static bool can_represent_loop_1 (loop_p loop
, sese_l scop
);
653 /* Return true when all the loops within LOOP can be represented by
656 static bool can_represent_loop (loop_p loop
, sese_l scop
);
658 /* Returns the number of pbbs that are in loops contained in SCOP. */
660 static int nb_pbbs_in_loops (scop_p scop
);
662 static bool graphite_can_represent_stmt (sese_l
, gimple
*, basic_block
);
668 sese_l
scop_detection::invalid_sese (NULL
, NULL
);
670 /* Return an sese_l around the LOOP. */
673 scop_detection::get_sese (loop_p loop
)
678 edge scop_begin
= loop_preheader_edge (loop
);
679 edge scop_end
= single_exit (loop
);
680 if (!scop_end
|| (scop_end
->flags
& EDGE_COMPLEX
))
682 /* Include the BB with the loop-closed SSA PHI nodes.
683 canonicalize_loop_closed_ssa makes sure that is in proper shape. */
684 if (! single_pred_p (scop_end
->dest
)
685 || ! single_succ_p (scop_end
->dest
)
686 || ! trivially_empty_bb_p (scop_end
->dest
))
688 scop_end
= single_succ_edge (scop_end
->dest
);
690 return sese_l (scop_begin
, scop_end
);
693 /* Return the closest dominator with a single entry edge. */
696 scop_detection::get_nearest_dom_with_single_entry (basic_block dom
)
701 /* If any of the dominators has two predecessors but one of them is a back
702 edge, then that basic block also qualifies as a dominator with single
704 if (dom
->preds
->length () == 2)
706 /* If e1->src dominates e2->src then e1->src will also dominate dom. */
707 edge e1
= (*dom
->preds
)[0];
708 edge e2
= (*dom
->preds
)[1];
709 loop_p l
= dom
->loop_father
;
710 loop_p l1
= e1
->src
->loop_father
;
711 loop_p l2
= e2
->src
->loop_father
;
712 if (l
!= l1
&& l
== l2
713 && dominated_by_p (CDI_DOMINATORS
, e2
->src
, e1
->src
))
715 if (l
!= l2
&& l
== l1
716 && dominated_by_p (CDI_DOMINATORS
, e1
->src
, e2
->src
))
720 while (dom
->preds
->length () != 1)
722 if (dom
->preds
->length () < 1)
724 dom
= get_immediate_dominator (CDI_DOMINATORS
, dom
);
728 return (*dom
->preds
)[0];
731 /* Return the closest post-dominator with a single exit edge. In case of a
732 back-loop the back-edge is not counted. */
735 scop_detection::get_nearest_pdom_with_single_exit (basic_block pdom
)
740 /* If any of the post-dominators has two successors but one of them is a back
741 edge, then that basic block also qualifies as a post-dominator with single
743 if (pdom
->succs
->length () == 2)
745 /* If e1->dest post-dominates e2->dest then e1->dest will also
746 post-dominate pdom. */
747 edge e1
= (*pdom
->succs
)[0];
748 edge e2
= (*pdom
->succs
)[1];
749 loop_p l
= pdom
->loop_father
;
750 loop_p l1
= e1
->dest
->loop_father
;
751 loop_p l2
= e2
->dest
->loop_father
;
752 if (l
!= l1
&& l
== l2
753 && dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, e1
->dest
))
755 if (l
!= l2
&& l
== l1
756 && dominated_by_p (CDI_POST_DOMINATORS
, e1
->dest
, e2
->dest
))
760 while (pdom
->succs
->length () != 1)
762 if (pdom
->succs
->length () < 1)
764 pdom
= get_immediate_dominator (CDI_POST_DOMINATORS
, pdom
);
769 return (*pdom
->succs
)[0];
772 /* Merge scops at same loop depth and returns the new sese.
773 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
776 scop_detection::merge_sese (sese_l first
, sese_l second
) const
778 /* In the trivial case first/second may be NULL. */
784 DEBUG_PRINT (dp
<< "[scop-detection] try merging sese s1: ";
785 print_sese (dump_file
, first
);
786 dp
<< "[scop-detection] try merging sese s2: ";
787 print_sese (dump_file
, second
));
789 /* Assumption: Both the sese's should be at the same loop depth or one scop
790 should subsume the other like in case of nested loops. */
792 /* Find the common dominators for entry,
793 and common post-dominators for the exit. */
794 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
,
795 get_entry_bb (first
),
796 get_entry_bb (second
));
798 edge entry
= get_nearest_dom_with_single_entry (dom
);
800 if (!entry
|| (entry
->flags
& EDGE_IRREDUCIBLE_LOOP
))
803 basic_block pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
,
805 get_exit_bb (second
));
806 pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
, dom
, pdom
);
808 edge exit
= get_nearest_pdom_with_single_exit (pdom
);
810 if (!exit
|| (exit
->flags
& EDGE_IRREDUCIBLE_LOOP
))
813 sese_l
combined (entry
, exit
);
815 DEBUG_PRINT (dp
<< "[scop-detection] checking combined sese: ";
816 print_sese (dump_file
, combined
));
818 /* FIXME: We could iterate to find the dom which dominates pdom, and pdom
819 which post-dominates dom, until it stabilizes. Also, ENTRY->SRC and
820 EXIT->DEST should be in the same loop nest. */
821 if (!dominated_by_p (CDI_DOMINATORS
, pdom
, dom
)
822 || loop_depth (entry
->src
->loop_father
)
823 != loop_depth (exit
->dest
->loop_father
))
826 /* For now we just bail out when there is a loop exit in the region
827 that is not also the exit of the region. We could enlarge the
828 region to cover the loop that region exits to. See PR79977. */
829 if (loop_outer (entry
->src
->loop_father
))
831 vec
<edge
> exits
= get_loop_exit_edges (entry
->src
->loop_father
);
832 for (unsigned i
= 0; i
< exits
.length (); ++i
)
835 && bb_in_region (exits
[i
]->src
, entry
->dest
, exit
->src
))
837 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
845 /* For now we just want to bail out when exit does not post-dominate entry.
846 TODO: We might just add a basic_block at the exit to make exit
847 post-dominate entry (the entire region). */
848 if (!dominated_by_p (CDI_POST_DOMINATORS
, get_entry_bb (combined
),
849 get_exit_bb (combined
))
850 || !dominated_by_p (CDI_DOMINATORS
, get_exit_bb (combined
),
851 get_entry_bb (combined
)))
853 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
857 /* Analyze all the BBs in new sese. */
858 if (harmful_loop_in_region (combined
))
861 DEBUG_PRINT (dp
<< "[merged-sese] s1: "; print_sese (dump_file
, combined
));
866 /* Build scop outer->inner if possible. */
869 scop_detection::build_scop_depth (sese_l s
, loop_p loop
)
874 DEBUG_PRINT (dp
<< "[Depth loop_" << loop
->num
<< "]\n");
875 s
= build_scop_depth (s
, loop
->inner
);
877 sese_l s2
= merge_sese (s
, get_sese (loop
));
880 /* s might be a valid scop, so return it and start analyzing from the
882 build_scop_depth (invalid_sese
, loop
->next
);
886 if (!loop_is_valid_in_scop (loop
, s2
))
887 return build_scop_depth (invalid_sese
, loop
->next
);
889 return build_scop_breadth (s2
, loop
);
892 /* If loop and loop->next are valid scops, try to merge them. */
895 scop_detection::build_scop_breadth (sese_l s1
, loop_p loop
)
899 DEBUG_PRINT (dp
<< "[Breadth loop_" << loop
->num
<< "]\n");
903 sese_l s2
= build_scop_depth (invalid_sese
, l
->next
);
911 sese_l combined
= merge_sese (s1
, s2
);
913 /* Combining adjacent loops may add unrelated loops into the
914 region so we have to check all sub-loops of the outer loop
915 that are in the combined region. */
917 for (l
= loop_outer (loop
)->inner
; l
; l
= l
->next
)
918 if (bb_in_sese_p (l
->header
, combined
)
919 && ! loop_is_valid_in_scop (l
, combined
))
921 combined
= invalid_sese
;
935 /* Returns true when Graphite can represent LOOP in SCOP.
936 FIXME: For the moment, graphite cannot be used on loops that iterate using
937 induction variables that wrap. */
940 scop_detection::can_represent_loop_1 (loop_p loop
, sese_l scop
)
943 struct tree_niter_desc niter_desc
;
945 return single_exit (loop
)
946 && !(loop_preheader_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
)
947 && number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
948 && niter_desc
.control
.no_overflow
949 && (niter
= number_of_latch_executions (loop
))
950 && !chrec_contains_undetermined (niter
)
951 && !chrec_contains_undetermined (scalar_evolution_in_region (scop
,
953 && graphite_can_represent_expr (scop
, loop
, niter
);
956 /* Return true when all the loops within LOOP can be represented by
960 scop_detection::can_represent_loop (loop_p loop
, sese_l scop
)
962 if (!can_represent_loop_1 (loop
, scop
))
964 for (loop_p inner
= loop
->inner
; inner
; inner
= inner
->next
)
965 if (!can_represent_loop (inner
, scop
))
970 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
971 region of code that can be represented in the polyhedral model. SCOP
972 defines the region we analyse. */
975 scop_detection::loop_is_valid_in_scop (loop_p loop
, sese_l scop
) const
980 if (!optimize_loop_nest_for_speed_p (loop
))
982 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_"
983 << loop
->num
<< " is not on a hot path.\n");
987 if (!can_represent_loop (loop
, scop
))
989 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot represent loop_"
990 << loop
->num
<< "\n");
994 if (loop_body_is_valid_scop (loop
, scop
))
996 DEBUG_PRINT (dp
<< "[valid-scop] loop_" << loop
->num
997 << " is a valid scop.\n");
1003 /* Return true when BEGIN is the preheader edge of a loop with a single exit
1007 scop_detection::region_has_one_loop (sese_l s
)
1009 edge begin
= s
.entry
;
1011 /* Check for a single perfectly nested loop. */
1012 if (begin
->dest
->loop_father
->inner
)
1015 /* Otherwise, check whether we have adjacent loops. */
1016 return (single_pred_p (end
->src
)
1017 && begin
->dest
->loop_father
== single_pred (end
->src
)->loop_father
);
1020 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
1023 scop_detection::add_scop (sese_l s
)
1027 /* Do not add scops with only one loop. */
1028 if (region_has_one_loop (s
))
1030 DEBUG_PRINT (dp
<< "[scop-detection-fail] Discarding one loop SCoP: ";
1031 print_sese (dump_file
, s
));
1035 if (get_exit_bb (s
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1037 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1038 << "Discarding SCoP exiting to return: ";
1039 print_sese (dump_file
, s
));
1043 /* Remove all the scops which are subsumed by s. */
1044 remove_subscops (s
);
1046 /* Remove intersecting scops. FIXME: It will be a good idea to keep
1047 the non-intersecting part of the scop already in the list. */
1048 remove_intersecting_scops (s
);
1050 scops
.safe_push (s
);
1051 DEBUG_PRINT (dp
<< "[scop-detection] Adding SCoP: "; print_sese (dump_file
, s
));
1054 /* Return true when a statement in SCOP cannot be represented by Graphite.
1055 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
1056 Limit the number of bbs between adjacent loops to
1057 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
1060 scop_detection::harmful_loop_in_region (sese_l scop
) const
1062 basic_block exit_bb
= get_exit_bb (scop
);
1063 basic_block entry_bb
= get_entry_bb (scop
);
1065 DEBUG_PRINT (dp
<< "[checking-harmful-bbs] ";
1066 print_sese (dump_file
, scop
));
1067 gcc_assert (dominated_by_p (CDI_DOMINATORS
, exit_bb
, entry_bb
));
1069 auto_vec
<basic_block
> worklist
;
1072 worklist
.safe_push (entry_bb
);
1073 while (! worklist
.is_empty ())
1075 basic_block bb
= worklist
.pop ();
1076 DEBUG_PRINT (dp
<< "Visiting bb_" << bb
->index
<< "\n");
1078 /* The basic block should not be part of an irreducible loop. */
1079 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1082 /* Check for unstructured control flow: CFG not generated by structured
1084 if (bb
->succs
->length () > 1)
1088 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1089 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb
, e
->dest
)
1090 && !dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
1094 /* Collect all loops in the current region. */
1095 loop_p loop
= bb
->loop_father
;
1096 if (loop_in_sese_p (loop
, scop
))
1097 bitmap_set_bit (loops
, loop
->num
);
1100 /* We only check for harmful statements in basic blocks not part of
1101 any loop fully contained in the scop: other bbs are checked below
1102 in loop_is_valid_in_scop. */
1103 if (harmful_stmt_in_bb (scop
, bb
))
1108 for (basic_block dom
= first_dom_son (CDI_DOMINATORS
, bb
);
1110 dom
= next_dom_son (CDI_DOMINATORS
, dom
))
1111 worklist
.safe_push (dom
);
1114 /* Go through all loops and check that they are still valid in the combined
1118 EXECUTE_IF_SET_IN_BITMAP (loops
, 0, j
, bi
)
1120 loop_p loop
= (*current_loops
->larray
)[j
];
1121 gcc_assert (loop
->num
== (int) j
);
1123 if (!loop_is_valid_in_scop (loop
, scop
))
1130 /* Returns true if S1 subsumes/surrounds S2. */
1132 scop_detection::subsumes (sese_l s1
, sese_l s2
)
1134 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
1136 && dominated_by_p (CDI_POST_DOMINATORS
, s2
.exit
->dest
,
1142 /* Remove a SCoP which is subsumed by S1. */
1144 scop_detection::remove_subscops (sese_l s1
)
1148 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
1150 if (subsumes (s1
, *s2
))
1152 DEBUG_PRINT (dp
<< "Removing sub-SCoP";
1153 print_sese (dump_file
, *s2
));
1154 scops
.unordered_remove (j
);
1159 /* Returns true if S1 intersects with S2. Since we already know that S1 does
1160 not subsume S2 or vice-versa, we only check for entry bbs. */
1163 scop_detection::intersects (sese_l s1
, sese_l s2
)
1165 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
1167 && !dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
1170 if ((s1
.exit
== s2
.entry
) || (s2
.exit
== s1
.entry
))
1176 /* Remove one of the scops when it intersects with any other. */
1179 scop_detection::remove_intersecting_scops (sese_l s1
)
1183 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
1185 if (intersects (s1
, *s2
))
1187 DEBUG_PRINT (dp
<< "Removing intersecting SCoP";
1188 print_sese (dump_file
, *s2
);
1189 dp
<< "Intersects with:";
1190 print_sese (dump_file
, s1
));
1191 scops
.unordered_remove (j
);
1196 /* Something like "n * m" is not allowed. */
1199 scop_detection::graphite_can_represent_init (tree e
)
1201 switch (TREE_CODE (e
))
1203 case POLYNOMIAL_CHREC
:
1204 return graphite_can_represent_init (CHREC_LEFT (e
))
1205 && graphite_can_represent_init (CHREC_RIGHT (e
));
1208 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1209 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
1210 && tree_fits_shwi_p (TREE_OPERAND (e
, 1));
1212 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
1213 && tree_fits_shwi_p (TREE_OPERAND (e
, 0));
1216 case POINTER_PLUS_EXPR
:
1218 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
1219 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
1224 case NON_LVALUE_EXPR
:
1225 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
1234 /* Return true when SCEV can be represented in the polyhedral model.
1236 An expression can be represented, if it can be expressed as an
1237 affine expression. For loops (i, j) and parameters (m, n) all
1238 affine expressions are of the form:
1240 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
1242 1 i + 20 j + (-2) m + 25
1244 Something like "i * n" or "n * m" is not allowed. */
1247 scop_detection::graphite_can_represent_scev (tree scev
)
1249 if (chrec_contains_undetermined (scev
))
1252 /* We disable the handling of pointer types, because it’s currently not
1253 supported by Graphite with the isl AST generator. SSA_NAME nodes are
1254 the only nodes, which are disabled in case they are pointers to object
1255 types, but this can be changed. */
1257 if (POINTER_TYPE_P (TREE_TYPE (scev
)) && TREE_CODE (scev
) == SSA_NAME
)
1260 switch (TREE_CODE (scev
))
1265 case NON_LVALUE_EXPR
:
1266 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0));
1269 case POINTER_PLUS_EXPR
:
1271 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1272 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1275 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
1276 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
1277 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
1278 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
1279 && graphite_can_represent_init (scev
)
1280 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1281 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1283 case POLYNOMIAL_CHREC
:
1284 /* Check for constant strides. With a non constant stride of
1285 'n' we would have a value of 'iv * n'. Also check that the
1286 initial value can represented: for example 'n * m' cannot be
1288 if (!evolution_function_right_is_integer_cst (scev
)
1289 || !graphite_can_represent_init (scev
))
1291 return graphite_can_represent_scev (CHREC_LEFT (scev
));
1297 /* Only affine functions can be represented. */
1298 if (tree_contains_chrecs (scev
, NULL
) || !scev_is_linear_expression (scev
))
1304 /* Return true when EXPR can be represented in the polyhedral model.
1306 This means an expression can be represented, if it is linear with respect to
1307 the loops and the strides are non parametric. LOOP is the place where the
1308 expr will be evaluated. SCOP defines the region we analyse. */
1311 scop_detection::graphite_can_represent_expr (sese_l scop
, loop_p loop
,
1314 tree scev
= scalar_evolution_in_region (scop
, loop
, expr
);
1315 return graphite_can_represent_scev (scev
);
1318 /* Return true if the data references of STMT can be represented by Graphite.
1319 We try to analyze the data references in a loop contained in the SCOP. */
1322 scop_detection::stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
)
1324 loop_p nest
= outermost_loop_in_sese (scop
, gimple_bb (stmt
));
1325 loop_p loop
= loop_containing_stmt (stmt
);
1326 if (!loop_in_sese_p (loop
, scop
))
1329 auto_vec
<data_reference_p
> drs
;
1330 if (! graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
))
1334 data_reference_p dr
;
1335 FOR_EACH_VEC_ELT (drs
, j
, dr
)
1337 for (unsigned i
= 0; i
< DR_NUM_DIMENSIONS (dr
); ++i
)
1338 if (! graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
)))
1345 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1346 Calls have side-effects, except those to const or pure
1350 stmt_has_side_effects (gimple
*stmt
)
1352 if (gimple_has_volatile_ops (stmt
)
1353 || (gimple_code (stmt
) == GIMPLE_CALL
1354 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
1355 || (gimple_code (stmt
) == GIMPLE_ASM
))
1357 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1358 << "Statement has side-effects:\n";
1359 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1365 /* Returns true if STMT can be represented in polyhedral model. LABEL,
1366 simple COND stmts, pure calls, and assignments can be repesented. */
1369 scop_detection::graphite_can_represent_stmt (sese_l scop
, gimple
*stmt
,
1372 loop_p loop
= bb
->loop_father
;
1373 switch (gimple_code (stmt
))
1380 /* We can handle all binary comparisons. Inequalities are
1381 also supported as they can be represented with union of
1383 enum tree_code code
= gimple_cond_code (stmt
);
1384 if (!(code
== LT_EXPR
1389 || code
== NE_EXPR
))
1391 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1392 << "Graphite cannot handle cond stmt:\n";
1393 print_gimple_stmt (dump_file
, stmt
, 0,
1394 TDF_VOPS
| TDF_MEMSYMS
));
1398 for (unsigned i
= 0; i
< 2; ++i
)
1400 tree op
= gimple_op (stmt
, i
);
1401 if (!graphite_can_represent_expr (scop
, loop
, op
)
1402 /* We can only constrain on integer type. */
1403 || (TREE_CODE (TREE_TYPE (op
)) != INTEGER_TYPE
))
1405 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1406 << "Graphite cannot represent stmt:\n";
1407 print_gimple_stmt (dump_file
, stmt
, 0,
1408 TDF_VOPS
| TDF_MEMSYMS
));
1421 /* These nodes cut a new scope. */
1423 dp
<< "[scop-detection-fail] "
1424 << "Gimple stmt not handled in Graphite:\n";
1425 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1430 /* Return true only when STMT is simple enough for being handled by Graphite.
1431 This depends on SCOP, as the parameters are initialized relatively to
1432 this basic block, the linear functions are initialized based on the outermost
1433 loop containing STMT inside the SCOP. BB is the place where we try to
1434 evaluate the STMT. */
1437 scop_detection::stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
1438 basic_block bb
) const
1442 if (is_gimple_debug (stmt
))
1445 if (stmt_has_side_effects (stmt
))
1448 if (!stmt_has_simple_data_refs_p (scop
, stmt
))
1450 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1451 << "Graphite cannot handle data-refs in stmt:\n";
1452 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
););
1456 return graphite_can_represent_stmt (scop
, stmt
, bb
);
1459 /* Return true when BB contains a harmful operation for a scop: that
1460 can be a function call with side effects, the induction variables
1461 are not linear with respect to SCOP, etc. The current open
1462 scop should end before this statement. */
1465 scop_detection::harmful_stmt_in_bb (sese_l scop
, basic_block bb
) const
1467 gimple_stmt_iterator gsi
;
1469 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1470 if (!stmt_simple_for_scop_p (scop
, gsi_stmt (gsi
), bb
))
1476 /* Return true when the body of LOOP has statements that can be represented as a
1480 scop_detection::loop_body_is_valid_scop (loop_p loop
, sese_l scop
) const
1482 if (!loop_ivs_can_be_represented (loop
))
1484 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
1485 << "IV cannot be represented.\n");
1489 if (!loop_nest_has_data_refs (loop
))
1491 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
1492 << "does not have any data reference.\n");
1496 basic_block
*bbs
= get_loop_body (loop
);
1497 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
1499 basic_block bb
= bbs
[i
];
1501 if (harmful_stmt_in_bb (scop
, bb
))
1514 if (!loop_body_is_valid_scop (loop
, scop
))
1523 /* Returns the number of pbbs that are in loops contained in SCOP. */
1526 scop_detection::nb_pbbs_in_loops (scop_p scop
)
1532 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1533 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), scop
->scop_info
->region
))
1539 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
1540 Otherwise returns -1. */
1543 parameter_index_in_region_1 (tree name
, sese_info_p region
)
1548 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1550 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
1557 /* When the parameter NAME is in REGION, returns its index in
1558 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
1559 and returns the index of NAME. */
1562 parameter_index_in_region (tree name
, sese_info_p region
)
1566 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1568 /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
1569 if (TREE_CODE (TREE_TYPE (name
)) != INTEGER_TYPE
)
1572 if (!invariant_in_sese_p_rec (name
, region
->region
, NULL
))
1575 i
= parameter_index_in_region_1 (name
, region
);
1579 i
= region
->params
.length ();
1580 region
->params
.safe_push (name
);
1584 /* In the context of sese S, scan the expression E and translate it to
1585 a linear expression C. When parsing a symbolic multiplication, K
1586 represents the constant multiplier of an expression containing
1590 scan_tree_for_params (sese_info_p s
, tree e
)
1592 if (e
== chrec_dont_know
)
1595 switch (TREE_CODE (e
))
1597 case POLYNOMIAL_CHREC
:
1598 scan_tree_for_params (s
, CHREC_LEFT (e
));
1602 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1603 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1605 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1609 case POINTER_PLUS_EXPR
:
1611 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1612 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1618 case NON_LVALUE_EXPR
:
1619 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1623 parameter_index_in_region (e
, s
);
1639 /* Find parameters with respect to REGION in BB. We are looking in memory
1640 access functions, conditions and loop bounds. */
1643 find_params_in_bb (sese_info_p region
, gimple_poly_bb_p gbb
)
1645 /* Find parameters in the access functions of data references. */
1647 data_reference_p dr
;
1648 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
1649 for (unsigned j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
1650 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
1652 /* Find parameters in conditional statements. */
1654 loop_p loop
= GBB_BB (gbb
)->loop_father
;
1655 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1657 tree lhs
= scalar_evolution_in_region (region
->region
, loop
,
1658 gimple_cond_lhs (stmt
));
1659 tree rhs
= scalar_evolution_in_region (region
->region
, loop
,
1660 gimple_cond_rhs (stmt
));
1662 scan_tree_for_params (region
, lhs
);
1663 scan_tree_for_params (region
, rhs
);
1667 /* Record the parameters used in the SCOP. A variable is a parameter
1668 in a scop if it does not vary during the execution of that scop. */
1671 find_scop_parameters (scop_p scop
)
1674 sese_info_p region
= scop
->scop_info
;
1677 /* Find the parameters used in the loop bounds. */
1678 FOR_EACH_VEC_ELT (region
->loop_nest
, i
, loop
)
1680 tree nb_iters
= number_of_latch_executions (loop
);
1682 if (!chrec_contains_symbols (nb_iters
))
1685 nb_iters
= scalar_evolution_in_region (region
->region
, loop
, nb_iters
);
1686 scan_tree_for_params (region
, nb_iters
);
1689 /* Find the parameters used in data accesses. */
1691 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1692 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1694 int nbp
= sese_nb_params (region
);
1695 scop_set_nb_params (scop
, nbp
);
1698 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1701 build_cross_bb_scalars_def (scop_p scop
, tree def
, basic_block def_bb
,
1704 if (!def
|| !is_gimple_reg (def
))
1707 bool scev_analyzable
= scev_analyzable_p (def
, scop
->scop_info
->region
);
1710 imm_use_iterator imm_iter
;
1711 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1712 /* Do not gather scalar variables that can be analyzed by SCEV as they can
1713 be generated out of the induction variables. */
1714 if ((! scev_analyzable
1715 /* But gather SESE liveouts as we otherwise fail to rewrite their
1717 || ! bb_in_sese_p (gimple_bb (use_stmt
), scop
->scop_info
->region
))
1718 && ((def_bb
!= gimple_bb (use_stmt
) && !is_gimple_debug (use_stmt
))
1719 /* PHIs have their effect at "BBs" on the edges. See PR79622. */
1720 || gimple_code (SSA_NAME_DEF_STMT (def
)) == GIMPLE_PHI
))
1722 writes
->safe_push (def
);
1723 DEBUG_PRINT (dp
<< "Adding scalar write: ";
1724 print_generic_expr (dump_file
, def
);
1725 dp
<< "\nFrom stmt: ";
1726 print_gimple_stmt (dump_file
,
1727 SSA_NAME_DEF_STMT (def
), 0));
1728 /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
1729 before all the uses have been visited. */
1730 BREAK_FROM_IMM_USE_STMT (imm_iter
);
1734 /* Record USE if it is defined in other bbs different than USE_STMT
1738 build_cross_bb_scalars_use (scop_p scop
, tree use
, gimple
*use_stmt
,
1739 vec
<scalar_use
> *reads
)
1742 if (!is_gimple_reg (use
))
1745 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1746 generated out of the induction variables. */
1747 if (scev_analyzable_p (use
, scop
->scop_info
->region
))
1750 gimple
*def_stmt
= SSA_NAME_DEF_STMT (use
);
1751 if (gimple_bb (def_stmt
) != gimple_bb (use_stmt
)
1752 /* PHIs have their effect at "BBs" on the edges. See PR79622. */
1753 || gimple_code (def_stmt
) == GIMPLE_PHI
)
1755 DEBUG_PRINT (dp
<< "Adding scalar read: ";
1756 print_generic_expr (dump_file
, use
);
1757 dp
<< "\nFrom stmt: ";
1758 print_gimple_stmt (dump_file
, use_stmt
, 0));
1759 reads
->safe_push (std::make_pair (use_stmt
, use
));
1763 /* Record all scalar variables that are defined and used in different BBs of the
1767 graphite_find_cross_bb_scalar_vars (scop_p scop
, gimple
*stmt
,
1768 vec
<scalar_use
> *reads
, vec
<tree
> *writes
)
1772 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
1773 def
= gimple_assign_lhs (stmt
);
1774 else if (gimple_code (stmt
) == GIMPLE_CALL
)
1775 def
= gimple_call_lhs (stmt
);
1776 else if (gimple_code (stmt
) == GIMPLE_PHI
)
1777 def
= gimple_phi_result (stmt
);
1782 build_cross_bb_scalars_def (scop
, def
, gimple_bb (stmt
), writes
);
1785 use_operand_p use_p
;
1786 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1788 tree use
= USE_FROM_PTR (use_p
);
1789 build_cross_bb_scalars_use (scop
, use
, stmt
, reads
);
1793 /* Generates a polyhedral black box only if the bb contains interesting
1796 static gimple_poly_bb_p
1797 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
1799 vec
<data_reference_p
> drs
= vNULL
;
1800 vec
<tree
> writes
= vNULL
;
1801 vec
<scalar_use
> reads
= vNULL
;
1803 sese_l region
= scop
->scop_info
->region
;
1804 loop_p nest
= outermost_loop_in_sese (region
, bb
);
1806 loop_p loop
= bb
->loop_father
;
1807 if (!loop_in_sese_p (loop
, region
))
1810 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1813 gimple
*stmt
= gsi_stmt (gsi
);
1814 if (is_gimple_debug (stmt
))
1817 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1818 graphite_find_cross_bb_scalar_vars (scop
, stmt
, &reads
, &writes
);
1821 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1823 if (!virtual_operand_p (gimple_phi_result (psi
.phi ())))
1824 graphite_find_cross_bb_scalar_vars (scop
, psi
.phi (), &reads
, &writes
);
1826 if (drs
.is_empty () && writes
.is_empty () && reads
.is_empty ())
1829 return new_gimple_poly_bb (bb
, drs
, reads
, writes
);
1832 /* Compute alias-sets for all data references in DRS. */
1835 build_alias_set (scop_p scop
)
1837 int num_vertices
= scop
->drs
.length ();
1838 struct graph
*g
= new_graph (num_vertices
);
1843 FOR_EACH_VEC_ELT (scop
->drs
, i
, dr1
)
1844 for (j
= i
+1; scop
->drs
.iterate (j
, &dr2
); j
++)
1845 if (dr_may_alias_p (dr1
->dr
, dr2
->dr
, true))
1847 /* Dependences in the same alias set need to be handled
1848 by just looking at DR_ACCESS_FNs. */
1849 if (DR_NUM_DIMENSIONS (dr1
->dr
) == 0
1850 || DR_NUM_DIMENSIONS (dr1
->dr
) != DR_NUM_DIMENSIONS (dr2
->dr
)
1851 || ! operand_equal_p (DR_BASE_OBJECT (dr1
->dr
),
1852 DR_BASE_OBJECT (dr2
->dr
),
1854 || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1
->dr
)),
1855 TREE_TYPE (DR_BASE_OBJECT (dr2
->dr
))))
1864 all_vertices
= XNEWVEC (int, num_vertices
);
1865 for (i
= 0; i
< num_vertices
; i
++)
1866 all_vertices
[i
] = i
;
1868 graphds_dfs (g
, all_vertices
, num_vertices
, NULL
, true, NULL
);
1869 free (all_vertices
);
1871 for (i
= 0; i
< g
->n_vertices
; i
++)
1872 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
);
1967 dp
<< "\nFrom stmt: ";
1968 print_gimple_stmt (dump_file
, dr
->stmt
, 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
))
1993 /* Compute sth like an execution order, dominator order with first executing
1994 edges that stay inside the current loop, delaying processing exit edges. */
1996 static vec
<unsigned> order
;
1999 get_order (scop_p scop
, basic_block bb
, vec
<unsigned> *order
, unsigned *dfs_num
)
2001 if (! bb_in_sese_p (bb
, scop
->scop_info
->region
))
2004 (*order
)[bb
->index
] = (*dfs_num
)++;
2005 for (basic_block son
= first_dom_son (CDI_DOMINATORS
, bb
);
2007 son
= next_dom_son (CDI_DOMINATORS
, son
))
2008 if (flow_bb_inside_loop_p (bb
->loop_father
, son
))
2009 get_order (scop
, son
, order
, dfs_num
);
2010 for (basic_block son
= first_dom_son (CDI_DOMINATORS
, bb
);
2012 son
= next_dom_son (CDI_DOMINATORS
, son
))
2013 if (! flow_bb_inside_loop_p (bb
->loop_father
, son
))
2014 get_order (scop
, son
, order
, dfs_num
);
2017 /* Helper for qsort, sorting after order above. */
2020 cmp_pbbs (const void *pa
, const void *pb
)
2022 poly_bb_p bb1
= *((const poly_bb_p
*)pa
);
2023 poly_bb_p bb2
= *((const poly_bb_p
*)pb
);
2024 if (order
[bb1
->black_box
->bb
->index
] < order
[bb2
->black_box
->bb
->index
])
2026 else if (order
[bb1
->black_box
->bb
->index
] > order
[bb2
->black_box
->bb
->index
])
2032 /* Find Static Control Parts (SCoP) in the current function and pushes
2036 build_scops (vec
<scop_p
> *scops
)
2039 dp
.set_dump_file (dump_file
);
2041 canonicalize_loop_closed_ssa_form ();
2043 /* ??? We walk the loop tree assuming loop->next is ordered.
2044 This is not so but we'd be free to order it here. */
2046 sese_l tem
= sb
.build_scop_depth (scop_detection::invalid_sese
,
2047 current_loops
->tree_root
);
2050 /* Now create scops from the lightweight SESEs. */
2051 vec
<sese_l
> scops_l
= sb
.get_scops ();
2054 FOR_EACH_VEC_ELT (scops_l
, i
, s
)
2056 scop_p scop
= new_scop (s
->entry
, s
->exit
);
2058 /* Record all basic blocks and their conditions in REGION. */
2059 gather_bbs (CDI_DOMINATORS
, scop
).walk (s
->entry
->dest
);
2061 /* domwalk does not fulfil our code-generations constraints on the
2062 order of pbb which is to produce sth like execution order, delaying
2063 exection of loop exit edges. So compute such order and sort after
2065 order
.create (last_basic_block_for_fn (cfun
));
2066 order
.quick_grow (last_basic_block_for_fn (cfun
));
2067 unsigned dfs_num
= 0;
2068 get_order (scop
, s
->entry
->dest
, &order
, &dfs_num
);
2069 scop
->pbbs
.qsort (cmp_pbbs
);
2072 if (! build_alias_set (scop
))
2074 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot handle dependences\n");
2079 /* Do not optimize a scop containing only PBBs that do not belong
2081 if (sb
.nb_pbbs_in_loops (scop
) == 0)
2083 DEBUG_PRINT (dp
<< "[scop-detection-fail] no data references.\n");
2088 unsigned max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
2089 if (scop
->drs
.length () >= max_arrays
)
2091 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many data references: "
2092 << scop
->drs
.length ()
2093 << " is larger than --param graphite-max-arrays-per-scop="
2094 << max_arrays
<< ".\n");
2099 find_scop_parameters (scop
);
2100 graphite_dim_t max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
2102 if (scop_nb_params (scop
) > max_dim
)
2104 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many parameters: "
2105 << scop_nb_params (scop
)
2106 << " larger than --param graphite-max-nb-scop-params="
2107 << max_dim
<< ".\n");
2112 scops
->safe_push (scop
);
2115 DEBUG_PRINT (dp
<< "number of SCoPs: " << (scops
? scops
->length () : 0););
2118 #endif /* HAVE_isl */