1 /* Detection of Static Control Parts (SCoP) for Graphite.
2 Copyright (C) 2009-2018 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"
61 set_dump_file (FILE *f
)
67 friend debug_printer
&
68 operator<< (debug_printer
&output
, int i
)
70 fprintf (output
.dump_file
, "%d", i
);
73 friend debug_printer
&
74 operator<< (debug_printer
&output
, const char *s
)
76 fprintf (output
.dump_file
, "%s", s
);
81 #define DEBUG_PRINT(args) do \
83 if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \
86 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
87 different colors. If there are not enough colors, paint the
88 remaining SCoPs in gray.
91 - "*" after the node number denotes the entry of a SCoP,
92 - "#" after the node number denotes the exit of a SCoP,
93 - "()" around the node number denotes the entry or the
94 exit nodes of the SCOP. These are not part of SCoP. */
97 dot_all_sese (FILE *file
, vec
<sese_l
>& scops
)
99 /* Disable debugging while printing graph. */
100 dump_flags_t tmp_dump_flags
= dump_flags
;
101 dump_flags
= TDF_NONE
;
103 fprintf (file
, "digraph all {\n");
106 FOR_ALL_BB_FN (bb
, cfun
)
108 int part_of_scop
= false;
110 /* Use HTML for every bb label. So we are able to print bbs
111 which are part of two different SCoPs, with two different
112 background colors. */
113 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
115 fprintf (file
, "CELLSPACING=\"0\">\n");
117 /* Select color for SCoP. */
120 FOR_EACH_VEC_ELT (scops
, i
, region
)
122 bool sese_in_region
= bb_in_sese_p (bb
, *region
);
123 if (sese_in_region
|| (region
->exit
->dest
== bb
)
124 || (region
->entry
->dest
== bb
))
184 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
188 fprintf (file
, " (");
190 if (bb
== region
->entry
->dest
&& bb
== region
->exit
->dest
)
191 fprintf (file
, " %d*# ", bb
->index
);
192 else if (bb
== region
->entry
->dest
)
193 fprintf (file
, " %d* ", bb
->index
);
194 else if (bb
== region
->exit
->dest
)
195 fprintf (file
, " %d# ", bb
->index
);
197 fprintf (file
, " %d ", bb
->index
);
199 fprintf (file
, "{lp_%d}", bb
->loop_father
->num
);
204 fprintf (file
, "</TD></TR>\n");
211 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
212 fprintf (file
, " %d {lp_%d} </TD></TR>\n", bb
->index
,
213 bb
->loop_father
->num
);
215 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
218 FOR_ALL_BB_FN (bb
, cfun
)
222 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
223 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
226 fputs ("}\n\n", file
);
228 /* Enable debugging again. */
229 dump_flags
= tmp_dump_flags
;
232 /* Display SCoP on stderr. */
235 dot_sese (sese_l
& scop
)
241 scops
.safe_push (scop
);
243 dot_all_sese (stderr
, scops
);
253 dot_all_sese (stderr
, scops
);
257 /* Returns a COND_EXPR statement when BB has a single predecessor, the
258 edge between BB and its predecessor is not a loop exit edge, and
259 the last statement of the single predecessor is a COND_EXPR. */
262 single_pred_cond_non_loop_exit (basic_block bb
)
264 if (single_pred_p (bb
))
266 edge e
= single_pred_edge (bb
);
267 basic_block pred
= e
->src
;
270 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
273 stmt
= last_stmt (pred
);
275 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
276 return as_a
<gcond
*> (stmt
);
285 /* Build the maximal scop containing LOOPs and add it to SCOPS. */
290 scop_detection () : scops (vNULL
) {}
297 /* A marker for invalid sese_l. */
298 static sese_l invalid_sese
;
300 /* Return the SCOPS in this SCOP_DETECTION. */
308 /* Return an sese_l around the LOOP. */
310 sese_l
get_sese (loop_p loop
);
312 /* Merge scops at same loop depth and returns the new sese.
313 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
315 sese_l
merge_sese (sese_l first
, sese_l second
) const;
317 /* Build scop outer->inner if possible. */
319 void build_scop_depth (loop_p loop
);
321 /* Return true when BEGIN is the preheader edge of a loop with a single exit
324 static bool region_has_one_loop (sese_l s
);
326 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
328 void add_scop (sese_l s
);
330 /* Returns true if S1 subsumes/surrounds S2. */
331 static bool subsumes (sese_l s1
, sese_l s2
);
333 /* Remove a SCoP which is subsumed by S1. */
334 void remove_subscops (sese_l s1
);
336 /* Returns true if S1 intersects with S2. Since we already know that S1 does
337 not subsume S2 or vice-versa, we only check for entry bbs. */
339 static bool intersects (sese_l s1
, sese_l s2
);
341 /* Remove one of the scops when it intersects with any other. */
343 void remove_intersecting_scops (sese_l s1
);
345 /* Return true when a statement in SCOP cannot be represented by Graphite. */
347 bool harmful_loop_in_region (sese_l scop
) const;
349 /* Return true only when STMT is simple enough for being handled by Graphite.
350 This depends on SCOP, as the parameters are initialized relatively to
351 this basic block, the linear functions are initialized based on the
352 outermost loop containing STMT inside the SCOP. BB is the place where we
353 try to evaluate the STMT. */
355 bool stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
356 basic_block bb
) const;
358 /* Something like "n * m" is not allowed. */
360 static bool graphite_can_represent_init (tree e
);
362 /* Return true when SCEV can be represented in the polyhedral model.
364 An expression can be represented, if it can be expressed as an
365 affine expression. For loops (i, j) and parameters (m, n) all
366 affine expressions are of the form:
368 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
370 1 i + 20 j + (-2) m + 25
372 Something like "i * n" or "n * m" is not allowed. */
374 static bool graphite_can_represent_scev (sese_l scop
, tree scev
);
376 /* Return true when EXPR can be represented in the polyhedral model.
378 This means an expression can be represented, if it is linear with respect
379 to the loops and the strides are non parametric. LOOP is the place where
380 the expr will be evaluated. SCOP defines the region we analyse. */
382 static bool graphite_can_represent_expr (sese_l scop
, loop_p loop
,
385 /* Return true if the data references of STMT can be represented by Graphite.
386 We try to analyze the data references in a loop contained in the SCOP. */
388 static bool stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
);
390 /* Remove the close phi node at GSI and replace its rhs with the rhs
393 static void remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
);
395 /* Returns true when Graphite can represent LOOP in SCOP.
396 FIXME: For the moment, graphite cannot be used on loops that iterate using
397 induction variables that wrap. */
399 static bool can_represent_loop (loop_p loop
, sese_l scop
);
401 /* Returns the number of pbbs that are in loops contained in SCOP. */
403 static int nb_pbbs_in_loops (scop_p scop
);
409 sese_l
scop_detection::invalid_sese (NULL
, NULL
);
411 /* Return an sese_l around the LOOP. */
414 scop_detection::get_sese (loop_p loop
)
419 edge scop_begin
= loop_preheader_edge (loop
);
420 edge scop_end
= single_exit (loop
);
421 if (!scop_end
|| (scop_end
->flags
& (EDGE_COMPLEX
|EDGE_FAKE
)))
424 return sese_l (scop_begin
, scop_end
);
427 /* Merge scops at same loop depth and returns the new sese.
428 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
431 scop_detection::merge_sese (sese_l first
, sese_l second
) const
433 /* In the trivial case first/second may be NULL. */
439 DEBUG_PRINT (dp
<< "[scop-detection] try merging sese s1: ";
440 print_sese (dump_file
, first
);
441 dp
<< "[scop-detection] try merging sese s2: ";
442 print_sese (dump_file
, second
));
444 auto_bitmap worklist
, in_sese_region
;
445 bitmap_set_bit (worklist
, get_entry_bb (first
)->index
);
446 bitmap_set_bit (worklist
, get_exit_bb (first
)->index
);
447 bitmap_set_bit (worklist
, get_entry_bb (second
)->index
);
448 bitmap_set_bit (worklist
, get_exit_bb (second
)->index
);
449 edge entry
= NULL
, exit
= NULL
;
451 /* We can optimize the case of adding a loop entry dest or exit
452 src to the worklist (for single-exit loops) by skipping
453 directly to the exit dest / entry src. in_sese_region
454 doesn't have to cover all blocks in the region but merely
455 its border it acts more like a visited bitmap. */
458 int index
= bitmap_first_set_bit (worklist
);
459 bitmap_clear_bit (worklist
, index
);
460 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, index
);
464 /* With fake exit edges we can end up with no possible exit. */
465 if (index
== EXIT_BLOCK
)
467 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
471 bitmap_set_bit (in_sese_region
, bb
->index
);
473 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
474 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
477 || dominated_by_p (CDI_DOMINATORS
, entry
->dest
, bb
)))
480 && ! bitmap_bit_p (in_sese_region
, entry
->src
->index
))
481 bitmap_set_bit (worklist
, entry
->src
->index
);
484 else if (! bitmap_bit_p (in_sese_region
, e
->src
->index
))
485 bitmap_set_bit (worklist
, e
->src
->index
);
487 basic_block pdom
= get_immediate_dominator (CDI_POST_DOMINATORS
, bb
);
488 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
491 || dominated_by_p (CDI_POST_DOMINATORS
, exit
->src
, bb
)))
494 && ! bitmap_bit_p (in_sese_region
, exit
->dest
->index
))
495 bitmap_set_bit (worklist
, exit
->dest
->index
);
498 else if (! bitmap_bit_p (in_sese_region
, e
->dest
->index
))
499 bitmap_set_bit (worklist
, e
->dest
->index
);
501 while (! bitmap_empty_p (worklist
));
503 sese_l
combined (entry
, exit
);
505 DEBUG_PRINT (dp
<< "[merged-sese] s1: "; print_sese (dump_file
, combined
));
510 /* Build scop outer->inner if possible. */
513 scop_detection::build_scop_depth (loop_p loop
)
515 sese_l s
= invalid_sese
;
519 sese_l next
= get_sese (loop
);
521 || harmful_loop_in_region (next
))
525 build_scop_depth (loop
);
532 sese_l combined
= merge_sese (s
, next
);
534 || harmful_loop_in_region (combined
))
548 /* Returns true when Graphite can represent LOOP in SCOP.
549 FIXME: For the moment, graphite cannot be used on loops that iterate using
550 induction variables that wrap. */
553 scop_detection::can_represent_loop (loop_p loop
, sese_l scop
)
556 struct tree_niter_desc niter_desc
;
558 return single_exit (loop
)
559 && !(loop_preheader_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
)
560 && number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
561 && niter_desc
.control
.no_overflow
562 && (niter
= number_of_latch_executions (loop
))
563 && !chrec_contains_undetermined (niter
)
564 && !chrec_contains_undetermined (scalar_evolution_in_region (scop
,
566 && graphite_can_represent_expr (scop
, loop
, niter
);
569 /* Return true when BEGIN is the preheader edge of a loop with a single exit
573 scop_detection::region_has_one_loop (sese_l s
)
575 edge begin
= s
.entry
;
577 /* Check for a single perfectly nested loop. */
578 if (begin
->dest
->loop_father
->inner
)
581 /* Otherwise, check whether we have adjacent loops. */
582 return (single_pred_p (end
->src
)
583 && begin
->dest
->loop_father
== single_pred (end
->src
)->loop_father
);
586 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
589 scop_detection::add_scop (sese_l s
)
593 /* Include the BB with the loop-closed SSA PHI nodes, we need this
594 block in the region for code-generating out-of-SSA copies.
595 canonicalize_loop_closed_ssa makes sure that is in proper shape. */
596 if (s
.exit
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
597 && loop_exit_edge_p (s
.exit
->src
->loop_father
, s
.exit
))
599 gcc_assert (single_pred_p (s
.exit
->dest
)
600 && single_succ_p (s
.exit
->dest
)
601 && sese_trivially_empty_bb_p (s
.exit
->dest
));
602 s
.exit
= single_succ_edge (s
.exit
->dest
);
605 /* Do not add scops with only one loop. */
606 if (region_has_one_loop (s
))
608 DEBUG_PRINT (dp
<< "[scop-detection-fail] Discarding one loop SCoP: ";
609 print_sese (dump_file
, s
));
613 if (get_exit_bb (s
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
615 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
616 << "Discarding SCoP exiting to return: ";
617 print_sese (dump_file
, s
));
621 /* Remove all the scops which are subsumed by s. */
624 /* Remove intersecting scops. FIXME: It will be a good idea to keep
625 the non-intersecting part of the scop already in the list. */
626 remove_intersecting_scops (s
);
629 DEBUG_PRINT (dp
<< "[scop-detection] Adding SCoP: "; print_sese (dump_file
, s
));
632 /* Return true when a statement in SCOP cannot be represented by Graphite. */
635 scop_detection::harmful_loop_in_region (sese_l scop
) const
637 basic_block exit_bb
= get_exit_bb (scop
);
638 basic_block entry_bb
= get_entry_bb (scop
);
640 DEBUG_PRINT (dp
<< "[checking-harmful-bbs] ";
641 print_sese (dump_file
, scop
));
642 gcc_assert (dominated_by_p (CDI_DOMINATORS
, exit_bb
, entry_bb
));
644 auto_vec
<basic_block
> worklist
;
647 worklist
.safe_push (entry_bb
);
648 while (! worklist
.is_empty ())
650 basic_block bb
= worklist
.pop ();
651 DEBUG_PRINT (dp
<< "Visiting bb_" << bb
->index
<< "\n");
653 /* The basic block should not be part of an irreducible loop. */
654 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
657 /* Check for unstructured control flow: CFG not generated by structured
659 if (bb
->succs
->length () > 1)
663 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
664 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb
, e
->dest
)
665 && !dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
669 /* Collect all loops in the current region. */
670 loop_p loop
= bb
->loop_father
;
671 if (loop_in_sese_p (loop
, scop
))
672 bitmap_set_bit (loops
, loop
->num
);
674 /* Check for harmful statements in basic blocks part of the region. */
675 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
676 !gsi_end_p (gsi
); gsi_next (&gsi
))
677 if (!stmt_simple_for_scop_p (scop
, gsi_stmt (gsi
), bb
))
680 for (basic_block dom
= first_dom_son (CDI_DOMINATORS
, bb
);
682 dom
= next_dom_son (CDI_DOMINATORS
, dom
))
683 if (dom
!= scop
.exit
->dest
)
684 worklist
.safe_push (dom
);
687 /* Go through all loops and check that they are still valid in the combined
691 EXECUTE_IF_SET_IN_BITMAP (loops
, 0, j
, bi
)
693 loop_p loop
= (*current_loops
->larray
)[j
];
694 gcc_assert (loop
->num
== (int) j
);
696 /* Check if the loop nests are to be optimized for speed. */
698 && ! optimize_loop_for_speed_p (loop
))
700 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_"
701 << loop
->num
<< " is not on a hot path.\n");
705 if (! can_represent_loop (loop
, scop
))
707 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot represent loop_"
708 << loop
->num
<< "\n");
712 /* Check if all loop nests have at least one data reference.
713 ??? This check is expensive and loops premature at this point.
714 If important to retain we can pre-compute this for all innermost
715 loops and reject those when we build a SESE region for a loop
716 during SESE discovery. */
718 && ! loop_nest_has_data_refs (loop
))
720 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
721 << "does not have any data reference.\n");
729 /* Returns true if S1 subsumes/surrounds S2. */
731 scop_detection::subsumes (sese_l s1
, sese_l s2
)
733 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
735 && dominated_by_p (CDI_POST_DOMINATORS
, s2
.exit
->dest
,
741 /* Remove a SCoP which is subsumed by S1. */
743 scop_detection::remove_subscops (sese_l s1
)
747 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
749 if (subsumes (s1
, *s2
))
751 DEBUG_PRINT (dp
<< "Removing sub-SCoP";
752 print_sese (dump_file
, *s2
));
753 scops
.unordered_remove (j
);
758 /* Returns true if S1 intersects with S2. Since we already know that S1 does
759 not subsume S2 or vice-versa, we only check for entry bbs. */
762 scop_detection::intersects (sese_l s1
, sese_l s2
)
764 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
766 && !dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
769 if ((s1
.exit
== s2
.entry
) || (s2
.exit
== s1
.entry
))
775 /* Remove one of the scops when it intersects with any other. */
778 scop_detection::remove_intersecting_scops (sese_l s1
)
782 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
784 if (intersects (s1
, *s2
))
786 DEBUG_PRINT (dp
<< "Removing intersecting SCoP";
787 print_sese (dump_file
, *s2
);
788 dp
<< "Intersects with:";
789 print_sese (dump_file
, s1
));
790 scops
.unordered_remove (j
);
795 /* Something like "n * m" is not allowed. */
798 scop_detection::graphite_can_represent_init (tree e
)
800 switch (TREE_CODE (e
))
802 case POLYNOMIAL_CHREC
:
803 return graphite_can_represent_init (CHREC_LEFT (e
))
804 && graphite_can_represent_init (CHREC_RIGHT (e
));
807 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
808 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
809 && tree_fits_shwi_p (TREE_OPERAND (e
, 1));
811 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
812 && tree_fits_shwi_p (TREE_OPERAND (e
, 0));
815 case POINTER_PLUS_EXPR
:
817 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
818 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
823 case NON_LVALUE_EXPR
:
824 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
833 /* Return true when SCEV can be represented in the polyhedral model.
835 An expression can be represented, if it can be expressed as an
836 affine expression. For loops (i, j) and parameters (m, n) all
837 affine expressions are of the form:
839 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
841 1 i + 20 j + (-2) m + 25
843 Something like "i * n" or "n * m" is not allowed. */
846 scop_detection::graphite_can_represent_scev (sese_l scop
, tree scev
)
848 if (chrec_contains_undetermined (scev
))
851 switch (TREE_CODE (scev
))
856 case NON_LVALUE_EXPR
:
857 return graphite_can_represent_scev (scop
, TREE_OPERAND (scev
, 0));
860 case POINTER_PLUS_EXPR
:
862 return graphite_can_represent_scev (scop
, TREE_OPERAND (scev
, 0))
863 && graphite_can_represent_scev (scop
, TREE_OPERAND (scev
, 1));
866 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
867 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
868 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
869 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
870 && graphite_can_represent_init (scev
)
871 && graphite_can_represent_scev (scop
, TREE_OPERAND (scev
, 0))
872 && graphite_can_represent_scev (scop
, TREE_OPERAND (scev
, 1));
874 case POLYNOMIAL_CHREC
:
875 /* Check for constant strides. With a non constant stride of
876 'n' we would have a value of 'iv * n'. Also check that the
877 initial value can represented: for example 'n * m' cannot be
879 gcc_assert (loop_in_sese_p (get_loop (cfun
,
880 CHREC_VARIABLE (scev
)), scop
));
881 if (!evolution_function_right_is_integer_cst (scev
)
882 || !graphite_can_represent_init (scev
))
884 return graphite_can_represent_scev (scop
, CHREC_LEFT (scev
));
890 /* Only affine functions can be represented. */
891 if (tree_contains_chrecs (scev
, NULL
) || !scev_is_linear_expression (scev
))
897 /* Return true when EXPR can be represented in the polyhedral model.
899 This means an expression can be represented, if it is linear with respect to
900 the loops and the strides are non parametric. LOOP is the place where the
901 expr will be evaluated. SCOP defines the region we analyse. */
904 scop_detection::graphite_can_represent_expr (sese_l scop
, loop_p loop
,
907 tree scev
= scalar_evolution_in_region (scop
, loop
, expr
);
908 return graphite_can_represent_scev (scop
, scev
);
911 /* Return true if the data references of STMT can be represented by Graphite.
912 We try to analyze the data references in a loop contained in the SCOP. */
915 scop_detection::stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
)
917 edge nest
= scop
.entry
;
918 loop_p loop
= loop_containing_stmt (stmt
);
919 if (!loop_in_sese_p (loop
, scop
))
922 auto_vec
<data_reference_p
> drs
;
923 if (! graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
))
928 FOR_EACH_VEC_ELT (drs
, j
, dr
)
930 for (unsigned i
= 0; i
< DR_NUM_DIMENSIONS (dr
); ++i
)
931 if (! graphite_can_represent_scev (scop
, DR_ACCESS_FN (dr
, i
)))
938 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
939 Calls have side-effects, except those to const or pure
943 stmt_has_side_effects (gimple
*stmt
)
945 if (gimple_has_volatile_ops (stmt
)
946 || (gimple_code (stmt
) == GIMPLE_CALL
947 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
948 || (gimple_code (stmt
) == GIMPLE_ASM
))
950 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
951 << "Statement has side-effects:\n";
952 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
958 /* Return true only when STMT is simple enough for being handled by Graphite.
959 This depends on SCOP, as the parameters are initialized relatively to
960 this basic block, the linear functions are initialized based on the outermost
961 loop containing STMT inside the SCOP. BB is the place where we try to
962 evaluate the STMT. */
965 scop_detection::stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
966 basic_block bb
) const
970 if (is_gimple_debug (stmt
))
973 if (stmt_has_side_effects (stmt
))
976 if (!stmt_has_simple_data_refs_p (scop
, stmt
))
978 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
979 << "Graphite cannot handle data-refs in stmt:\n";
980 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
););
984 switch (gimple_code (stmt
))
991 /* We can handle all binary comparisons. Inequalities are
992 also supported as they can be represented with union of
994 enum tree_code code
= gimple_cond_code (stmt
);
995 if (!(code
== LT_EXPR
1000 || code
== NE_EXPR
))
1002 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1003 << "Graphite cannot handle cond stmt:\n";
1004 print_gimple_stmt (dump_file
, stmt
, 0,
1005 TDF_VOPS
| TDF_MEMSYMS
));
1009 loop_p loop
= bb
->loop_father
;
1010 for (unsigned i
= 0; i
< 2; ++i
)
1012 tree op
= gimple_op (stmt
, i
);
1013 if (!graphite_can_represent_expr (scop
, loop
, op
)
1014 /* We can only constrain on integer type. */
1015 || ! INTEGRAL_TYPE_P (TREE_TYPE (op
)))
1017 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1018 << "Graphite cannot represent stmt:\n";
1019 print_gimple_stmt (dump_file
, stmt
, 0,
1020 TDF_VOPS
| TDF_MEMSYMS
));
1031 tree op
, lhs
= gimple_get_lhs (stmt
);
1033 /* If we are not going to instantiate the stmt do not require
1034 its operands to be instantiatable at this point. */
1036 && TREE_CODE (lhs
) == SSA_NAME
1037 && scev_analyzable_p (lhs
, scop
))
1039 /* Verify that if we can analyze operands at their def site we
1040 also can represent them when analyzed at their uses. */
1041 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_USE
)
1042 if (scev_analyzable_p (op
, scop
)
1043 && chrec_contains_undetermined
1044 (scalar_evolution_in_region (scop
, bb
->loop_father
, op
)))
1046 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1047 << "Graphite cannot code-gen stmt:\n";
1048 print_gimple_stmt (dump_file
, stmt
, 0,
1049 TDF_VOPS
| TDF_MEMSYMS
));
1056 /* These nodes cut a new scope. */
1058 dp
<< "[scop-detection-fail] "
1059 << "Gimple stmt not handled in Graphite:\n";
1060 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1065 /* Returns the number of pbbs that are in loops contained in SCOP. */
1068 scop_detection::nb_pbbs_in_loops (scop_p scop
)
1074 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1075 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), scop
->scop_info
->region
))
1081 /* Assigns the parameter NAME an index in REGION. */
1084 assign_parameter_index_in_region (tree name
, sese_info_p region
)
1086 gcc_assert (TREE_CODE (name
) == SSA_NAME
1087 && INTEGRAL_TYPE_P (TREE_TYPE (name
))
1088 && ! defined_in_sese_p (name
, region
->region
));
1092 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
1096 i
= region
->params
.length ();
1097 region
->params
.safe_push (name
);
1100 /* In the context of sese S, scan the expression E and translate it to
1101 a linear expression C. When parsing a symbolic multiplication, K
1102 represents the constant multiplier of an expression containing
1106 scan_tree_for_params (sese_info_p s
, tree e
)
1108 if (e
== chrec_dont_know
)
1111 switch (TREE_CODE (e
))
1113 case POLYNOMIAL_CHREC
:
1114 scan_tree_for_params (s
, CHREC_LEFT (e
));
1118 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1119 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1121 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1125 case POINTER_PLUS_EXPR
:
1127 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1128 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1134 case NON_LVALUE_EXPR
:
1135 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1139 assign_parameter_index_in_region (e
, s
);
1155 /* Find parameters with respect to REGION in BB. We are looking in memory
1156 access functions, conditions and loop bounds. */
1159 find_params_in_bb (sese_info_p region
, gimple_poly_bb_p gbb
)
1161 /* Find parameters in the access functions of data references. */
1163 data_reference_p dr
;
1164 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
1165 for (unsigned j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
1166 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
1168 /* Find parameters in conditional statements. */
1170 loop_p loop
= GBB_BB (gbb
)->loop_father
;
1171 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1173 tree lhs
= scalar_evolution_in_region (region
->region
, loop
,
1174 gimple_cond_lhs (stmt
));
1175 tree rhs
= scalar_evolution_in_region (region
->region
, loop
,
1176 gimple_cond_rhs (stmt
));
1178 scan_tree_for_params (region
, lhs
);
1179 scan_tree_for_params (region
, rhs
);
1183 /* Record the parameters used in the SCOP BBs. A variable is a parameter
1184 in a scop if it does not vary during the execution of that scop. */
1187 find_scop_parameters (scop_p scop
)
1190 sese_info_p region
= scop
->scop_info
;
1192 /* Parameters used in loop bounds are processed during gather_bbs. */
1194 /* Find the parameters used in data accesses. */
1196 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1197 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1199 int nbp
= sese_nb_params (region
);
1200 scop_set_nb_params (scop
, nbp
);
1204 add_write (vec
<tree
> *writes
, tree def
)
1206 writes
->safe_push (def
);
1207 DEBUG_PRINT (dp
<< "Adding scalar write: ";
1208 print_generic_expr (dump_file
, def
);
1209 dp
<< "\nFrom stmt: ";
1210 print_gimple_stmt (dump_file
,
1211 SSA_NAME_DEF_STMT (def
), 0));
1215 add_read (vec
<scalar_use
> *reads
, tree use
, gimple
*use_stmt
)
1217 DEBUG_PRINT (dp
<< "Adding scalar read: ";
1218 print_generic_expr (dump_file
, use
);
1219 dp
<< "\nFrom stmt: ";
1220 print_gimple_stmt (dump_file
, use_stmt
, 0));
1221 reads
->safe_push (std::make_pair (use_stmt
, use
));
1225 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1228 build_cross_bb_scalars_def (scop_p scop
, tree def
, basic_block def_bb
,
1231 if (!is_gimple_reg (def
))
1234 bool scev_analyzable
= scev_analyzable_p (def
, scop
->scop_info
->region
);
1237 imm_use_iterator imm_iter
;
1238 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1239 /* Do not gather scalar variables that can be analyzed by SCEV as they can
1240 be generated out of the induction variables. */
1241 if ((! scev_analyzable
1242 /* But gather SESE liveouts as we otherwise fail to rewrite their
1244 || ! bb_in_sese_p (gimple_bb (use_stmt
), scop
->scop_info
->region
))
1245 && (def_bb
!= gimple_bb (use_stmt
) && !is_gimple_debug (use_stmt
)))
1247 add_write (writes
, def
);
1248 /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
1249 before all the uses have been visited. */
1250 BREAK_FROM_IMM_USE_STMT (imm_iter
);
1254 /* Record USE if it is defined in other bbs different than USE_STMT
1258 build_cross_bb_scalars_use (scop_p scop
, tree use
, gimple
*use_stmt
,
1259 vec
<scalar_use
> *reads
)
1261 if (!is_gimple_reg (use
))
1264 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1265 generated out of the induction variables. */
1266 if (scev_analyzable_p (use
, scop
->scop_info
->region
))
1269 gimple
*def_stmt
= SSA_NAME_DEF_STMT (use
);
1270 if (gimple_bb (def_stmt
) != gimple_bb (use_stmt
))
1271 add_read (reads
, use
, use_stmt
);
1274 /* Generates a polyhedral black box only if the bb contains interesting
1277 static gimple_poly_bb_p
1278 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
1280 vec
<data_reference_p
> drs
= vNULL
;
1281 vec
<tree
> writes
= vNULL
;
1282 vec
<scalar_use
> reads
= vNULL
;
1284 sese_l region
= scop
->scop_info
->region
;
1285 edge nest
= region
.entry
;
1286 loop_p loop
= bb
->loop_father
;
1287 if (!loop_in_sese_p (loop
, region
))
1290 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1293 gimple
*stmt
= gsi_stmt (gsi
);
1294 if (is_gimple_debug (stmt
))
1297 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1299 tree def
= gimple_get_lhs (stmt
);
1301 build_cross_bb_scalars_def (scop
, def
, gimple_bb (stmt
), &writes
);
1305 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
1306 build_cross_bb_scalars_use (scop
, use
, stmt
, &reads
);
1309 /* Handle defs and uses in PHIs. Those need special treatment given
1310 that we have to present ISL with sth that looks like we've rewritten
1311 the IL out-of-SSA. */
1312 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1315 gphi
*phi
= psi
.phi ();
1316 tree res
= gimple_phi_result (phi
);
1317 if (virtual_operand_p (res
)
1318 || scev_analyzable_p (res
, scop
->scop_info
->region
))
1320 /* To simulate out-of-SSA the block containing the PHI node has
1321 reads of the PHI destination. And to preserve SSA dependences
1322 we also write to it (the out-of-SSA decl and the SSA result
1323 are coalesced for dependence purposes which is good enough). */
1324 add_read (&reads
, res
, phi
);
1325 add_write (&writes
, res
);
1327 basic_block bb_for_succs
= bb
;
1328 if (bb_for_succs
== bb_for_succs
->loop_father
->latch
1329 && bb_in_sese_p (bb_for_succs
, scop
->scop_info
->region
)
1330 && sese_trivially_empty_bb_p (bb_for_succs
))
1331 bb_for_succs
= NULL
;
1332 while (bb_for_succs
)
1334 basic_block latch
= NULL
;
1337 FOR_EACH_EDGE (e
, ei
, bb_for_succs
->succs
)
1339 for (gphi_iterator psi
= gsi_start_phis (e
->dest
); !gsi_end_p (psi
);
1342 gphi
*phi
= psi
.phi ();
1343 tree res
= gimple_phi_result (phi
);
1344 if (virtual_operand_p (res
))
1346 /* To simulate out-of-SSA the predecessor of edges into PHI nodes
1347 has a copy from the PHI argument to the PHI destination. */
1348 if (! scev_analyzable_p (res
, scop
->scop_info
->region
))
1349 add_write (&writes
, res
);
1350 tree use
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
1351 if (TREE_CODE (use
) == SSA_NAME
1352 && ! SSA_NAME_IS_DEFAULT_DEF (use
)
1353 && gimple_bb (SSA_NAME_DEF_STMT (use
)) != bb_for_succs
1354 && ! scev_analyzable_p (use
, scop
->scop_info
->region
))
1355 add_read (&reads
, use
, phi
);
1357 if (e
->dest
== bb_for_succs
->loop_father
->latch
1358 && bb_in_sese_p (e
->dest
, scop
->scop_info
->region
)
1359 && sese_trivially_empty_bb_p (e
->dest
))
1362 /* Handle empty latch block PHIs here, otherwise we confuse ISL
1363 with extra conditional code where it then peels off the last
1364 iteration just because of that. It would be simplest if we
1365 just didn't force simple latches (thus remove the forwarder). */
1366 bb_for_succs
= latch
;
1369 /* For the region exit block add reads for all live-out vars. */
1370 if (bb
== scop
->scop_info
->region
.exit
->src
)
1372 sese_build_liveouts (scop
->scop_info
);
1375 EXECUTE_IF_SET_IN_BITMAP (scop
->scop_info
->liveout
, 0, i
, bi
)
1377 tree use
= ssa_name (i
);
1378 add_read (&reads
, use
, NULL
);
1382 if (drs
.is_empty () && writes
.is_empty () && reads
.is_empty ())
1385 return new_gimple_poly_bb (bb
, drs
, reads
, writes
);
1388 /* Compute alias-sets for all data references in DRS. */
1391 build_alias_set (scop_p scop
)
1393 int num_vertices
= scop
->drs
.length ();
1394 struct graph
*g
= new_graph (num_vertices
);
1399 FOR_EACH_VEC_ELT (scop
->drs
, i
, dr1
)
1400 for (j
= i
+1; scop
->drs
.iterate (j
, &dr2
); j
++)
1401 if (dr_may_alias_p (dr1
->dr
, dr2
->dr
, true))
1403 /* Dependences in the same alias set need to be handled
1404 by just looking at DR_ACCESS_FNs. */
1405 if (DR_NUM_DIMENSIONS (dr1
->dr
) == 0
1406 || DR_NUM_DIMENSIONS (dr1
->dr
) != DR_NUM_DIMENSIONS (dr2
->dr
)
1407 || ! operand_equal_p (DR_BASE_OBJECT (dr1
->dr
),
1408 DR_BASE_OBJECT (dr2
->dr
),
1410 || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1
->dr
)),
1411 TREE_TYPE (DR_BASE_OBJECT (dr2
->dr
))))
1420 all_vertices
= XNEWVEC (int, num_vertices
);
1421 for (i
= 0; i
< num_vertices
; i
++)
1422 all_vertices
[i
] = i
;
1425 = graphds_dfs (g
, all_vertices
, num_vertices
, NULL
, true, NULL
) + 1;
1426 free (all_vertices
);
1428 for (i
= 0; i
< g
->n_vertices
; i
++)
1429 scop
->drs
[i
].alias_set
= g
->vertices
[i
].component
+ 1;
1435 /* Gather BBs and conditions for a SCOP. */
1436 class gather_bbs
: public dom_walker
1439 gather_bbs (cdi_direction
, scop_p
, int *);
1441 virtual edge
before_dom_children (basic_block
);
1442 virtual void after_dom_children (basic_block
);
1445 auto_vec
<gimple
*, 3> conditions
, cases
;
1449 gather_bbs::gather_bbs (cdi_direction direction
, scop_p scop
, int *bb_to_rpo
)
1450 : dom_walker (direction
, ALL_BLOCKS
, bb_to_rpo
), scop (scop
)
1454 /* Call-back for dom_walk executed before visiting the dominated
1458 gather_bbs::before_dom_children (basic_block bb
)
1460 sese_info_p region
= scop
->scop_info
;
1461 if (!bb_in_sese_p (bb
, region
->region
))
1462 return dom_walker::STOP
;
1464 /* For loops fully contained in the region record parameters in the
1466 loop_p loop
= bb
->loop_father
;
1467 if (loop
->header
== bb
1468 && loop_in_sese_p (loop
, region
->region
))
1470 tree nb_iters
= number_of_latch_executions (loop
);
1471 if (chrec_contains_symbols (nb_iters
))
1473 nb_iters
= scalar_evolution_in_region (region
->region
,
1475 scan_tree_for_params (region
, nb_iters
);
1479 if (gcond
*stmt
= single_pred_cond_non_loop_exit (bb
))
1481 edge e
= single_pred_edge (bb
);
1482 /* Make sure the condition is in the region and thus was verified
1484 if (e
!= region
->region
.entry
)
1486 conditions
.safe_push (stmt
);
1487 if (e
->flags
& EDGE_TRUE_VALUE
)
1488 cases
.safe_push (stmt
);
1490 cases
.safe_push (NULL
);
1494 scop
->scop_info
->bbs
.safe_push (bb
);
1496 gimple_poly_bb_p gbb
= try_generate_gimple_bb (scop
, bb
);
1500 GBB_CONDITIONS (gbb
) = conditions
.copy ();
1501 GBB_CONDITION_CASES (gbb
) = cases
.copy ();
1503 poly_bb_p pbb
= new_poly_bb (scop
, gbb
);
1504 scop
->pbbs
.safe_push (pbb
);
1507 data_reference_p dr
;
1508 FOR_EACH_VEC_ELT (gbb
->data_refs
, i
, dr
)
1510 DEBUG_PRINT (dp
<< "Adding memory ";
1515 print_generic_expr (dump_file
, dr
->ref
);
1516 dp
<< "\nFrom stmt: ";
1517 print_gimple_stmt (dump_file
, dr
->stmt
, 0));
1519 scop
->drs
.safe_push (dr_info (dr
, pbb
));
1525 /* Call-back for dom_walk executed after visiting the dominated
1529 gather_bbs::after_dom_children (basic_block bb
)
1531 if (!bb_in_sese_p (bb
, scop
->scop_info
->region
))
1534 if (single_pred_cond_non_loop_exit (bb
))
1536 edge e
= single_pred_edge (bb
);
1537 if (e
!= scop
->scop_info
->region
.entry
)
1546 /* Compute sth like an execution order, dominator order with first executing
1547 edges that stay inside the current loop, delaying processing exit edges. */
1549 static int *bb_to_rpo
;
1551 /* Helper for qsort, sorting after order above. */
1554 cmp_pbbs (const void *pa
, const void *pb
)
1556 poly_bb_p bb1
= *((const poly_bb_p
*)pa
);
1557 poly_bb_p bb2
= *((const poly_bb_p
*)pb
);
1558 if (bb_to_rpo
[bb1
->black_box
->bb
->index
]
1559 < bb_to_rpo
[bb2
->black_box
->bb
->index
])
1561 else if (bb_to_rpo
[bb1
->black_box
->bb
->index
]
1562 > bb_to_rpo
[bb2
->black_box
->bb
->index
])
1568 /* Find Static Control Parts (SCoP) in the current function and pushes
1572 build_scops (vec
<scop_p
> *scops
)
1575 dp
.set_dump_file (dump_file
);
1578 sb
.build_scop_depth (current_loops
->tree_root
);
1580 /* Now create scops from the lightweight SESEs. */
1581 vec
<sese_l
> scops_l
= sb
.get_scops ();
1583 /* Domwalk needs a bb to RPO mapping. Compute it once here. */
1584 int *postorder
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
1585 int postorder_num
= pre_and_rev_post_order_compute (NULL
, postorder
, true);
1586 bb_to_rpo
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1587 for (int i
= 0; i
< postorder_num
; ++i
)
1588 bb_to_rpo
[postorder
[i
]] = i
;
1593 FOR_EACH_VEC_ELT (scops_l
, i
, s
)
1595 scop_p scop
= new_scop (s
->entry
, s
->exit
);
1597 /* Record all basic blocks and their conditions in REGION. */
1598 gather_bbs (CDI_DOMINATORS
, scop
, bb_to_rpo
).walk (s
->entry
->dest
);
1600 /* Sort pbbs after execution order for initial schedule generation. */
1601 scop
->pbbs
.qsort (cmp_pbbs
);
1603 if (! build_alias_set (scop
))
1605 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot handle dependences\n");
1610 /* Do not optimize a scop containing only PBBs that do not belong
1612 if (sb
.nb_pbbs_in_loops (scop
) == 0)
1614 DEBUG_PRINT (dp
<< "[scop-detection-fail] no data references.\n");
1619 unsigned max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
1621 && scop
->drs
.length () >= max_arrays
)
1623 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many data references: "
1624 << scop
->drs
.length ()
1625 << " is larger than --param graphite-max-arrays-per-scop="
1626 << max_arrays
<< ".\n");
1631 find_scop_parameters (scop
);
1632 graphite_dim_t max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
1634 && scop_nb_params (scop
) > max_dim
)
1636 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many parameters: "
1637 << scop_nb_params (scop
)
1638 << " larger than --param graphite-max-nb-scop-params="
1639 << max_dim
<< ".\n");
1644 scops
->safe_push (scop
);
1649 DEBUG_PRINT (dp
<< "number of SCoPs: " << (scops
? scops
->length () : 0););
1652 #endif /* HAVE_isl */