1 /* Detection of Static Control Parts (SCoP) for Graphite.
2 Copyright (C) 2009 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/>. */
24 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
33 #include "tree-dump.h"
36 #include "tree-chrec.h"
37 #include "tree-data-ref.h"
38 #include "tree-scalar-evolution.h"
39 #include "tree-pass.h"
41 #include "value-prof.h"
42 #include "pointer-set.h"
47 #include "cloog/cloog.h"
49 #include "graphite-ppl.h"
51 #include "graphite-poly.h"
52 #include "graphite-scop-detection.h"
54 /* The type of the analyzed basic block. */
56 typedef enum gbb_type
{
58 GBB_LOOP_SING_EXIT_HEADER
,
59 GBB_LOOP_MULT_EXIT_HEADER
,
66 /* Detect the type of BB. Loop headers are only marked, if they are
67 new. This means their loop_father is different to LAST_LOOP.
68 Otherwise they are treated like any other bb and their type can be
72 get_bb_type (basic_block bb
, struct loop
*last_loop
)
74 VEC (basic_block
, heap
) *dom
;
76 struct loop
*loop
= bb
->loop_father
;
78 /* Check, if we entry into a new loop. */
79 if (loop
!= last_loop
)
81 if (single_exit (loop
) != NULL
)
82 return GBB_LOOP_SING_EXIT_HEADER
;
83 else if (loop
->num
!= 0)
84 return GBB_LOOP_MULT_EXIT_HEADER
;
86 return GBB_COND_HEADER
;
89 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
90 nb_dom
= VEC_length (basic_block
, dom
);
91 VEC_free (basic_block
, heap
, dom
);
96 nb_suc
= VEC_length (edge
, bb
->succs
);
98 if (nb_dom
== 1 && nb_suc
== 1)
101 return GBB_COND_HEADER
;
104 /* A SCoP detection region, defined using bbs as borders.
106 All control flow touching this region, comes in passing basic_block
107 ENTRY and leaves passing basic_block EXIT. By using bbs instead of
108 edges for the borders we are able to represent also regions that do
109 not have a single entry or exit edge.
111 But as they have a single entry basic_block and a single exit
112 basic_block, we are able to generate for every sd_region a single
120 / \ This region contains: {3, 4, 5, 6, 7, 8}
128 typedef struct sd_region_p
130 /* The entry bb dominates all bbs in the sd_region. It is part of
134 /* The exit bb postdominates all bbs in the sd_region, but is not
135 part of the region. */
139 DEF_VEC_O(sd_region
);
140 DEF_VEC_ALLOC_O(sd_region
, heap
);
143 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
146 move_sd_regions (VEC (sd_region
, heap
) **source
,
147 VEC (sd_region
, heap
) **target
)
152 for (i
= 0; VEC_iterate (sd_region
, *source
, i
, s
); i
++)
153 VEC_safe_push (sd_region
, heap
, *target
, s
);
155 VEC_free (sd_region
, heap
, *source
);
158 /* Something like "n * m" is not allowed. */
161 graphite_can_represent_init (tree e
)
163 switch (TREE_CODE (e
))
165 case POLYNOMIAL_CHREC
:
166 return graphite_can_represent_init (CHREC_LEFT (e
))
167 && graphite_can_represent_init (CHREC_RIGHT (e
));
170 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
171 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
172 && host_integerp (TREE_OPERAND (e
, 1), 0);
174 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
175 && host_integerp (TREE_OPERAND (e
, 0), 0);
178 case POINTER_PLUS_EXPR
:
180 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
181 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
186 case NON_LVALUE_EXPR
:
187 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
196 /* Return true when SCEV can be represented in the polyhedral model.
198 An expression can be represented, if it can be expressed as an
199 affine expression. For loops (i, j) and parameters (m, n) all
200 affine expressions are of the form:
202 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
204 1 i + 20 j + (-2) m + 25
206 Something like "i * n" or "n * m" is not allowed.
208 OUTERMOST_LOOP defines the outermost loop that can variate. */
211 graphite_can_represent_scev (tree scev
, int outermost_loop
)
213 if (chrec_contains_undetermined (scev
))
216 switch (TREE_CODE (scev
))
220 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0), outermost_loop
)
221 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1), outermost_loop
);
224 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
225 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
226 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
227 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
228 && graphite_can_represent_init (scev
)
229 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0), outermost_loop
)
230 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1), outermost_loop
);
232 case POLYNOMIAL_CHREC
:
233 /* Check for constant strides. With a non constant stride of
234 'n' we would have a value of 'iv * n'. Also check that the
235 initial value can represented: for example 'n * m' cannot be
237 if (!evolution_function_right_is_integer_cst (scev
)
238 || !graphite_can_represent_init (scev
))
245 /* Only affine functions can be represented. */
246 if (!scev_is_linear_expression (scev
))
249 return evolution_function_is_invariant_p (scev
, outermost_loop
)
250 || evolution_function_is_affine_multivariate_p (scev
, outermost_loop
);
254 /* Return true when EXPR can be represented in the polyhedral model.
256 This means an expression can be represented, if it is linear with
257 respect to the loops and the strides are non parametric.
258 LOOP is the place where the expr will be evaluated and OUTERMOST_LOOP
259 defindes the outermost loop that can variate. SCOP_ENTRY defines the
260 entry of the region we analyse. */
263 graphite_can_represent_expr (basic_block scop_entry
, loop_p loop
,
264 loop_p outermost_loop
, tree expr
)
266 tree scev
= analyze_scalar_evolution (loop
, expr
);
268 scev
= instantiate_scev (scop_entry
, loop
, scev
);
270 return graphite_can_represent_scev (scev
, outermost_loop
->num
);
273 /* Return true if the data references of STMT can be represented by
277 stmt_has_simple_data_refs_p (loop_p outermost_loop
, gimple stmt
)
283 int loop
= outermost_loop
->num
;
284 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 5);
286 graphite_find_data_references_in_stmt (outermost_loop
, stmt
, &drs
);
288 for (j
= 0; VEC_iterate (data_reference_p
, drs
, j
, dr
); j
++)
289 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
290 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
), loop
))
297 free_data_refs (drs
);
301 /* Return true only when STMT is simple enough for being handled by
302 Graphite. This depends on SCOP_ENTRY, as the parameters are
303 initialized relatively to this basic block, the linear functions
304 are initialized to OUTERMOST_LOOP and BB is the place where we try
305 to evaluate the STMT. */
308 stmt_simple_for_scop_p (basic_block scop_entry
, loop_p outermost_loop
,
309 gimple stmt
, basic_block bb
)
311 loop_p loop
= bb
->loop_father
;
313 gcc_assert (scop_entry
);
315 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
316 Calls have side-effects, except those to const or pure
318 if (gimple_has_volatile_ops (stmt
)
319 || (gimple_code (stmt
) == GIMPLE_CALL
320 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
321 || (gimple_code (stmt
) == GIMPLE_ASM
))
324 if (is_gimple_debug (stmt
))
327 if (!stmt_has_simple_data_refs_p (outermost_loop
, stmt
))
330 switch (gimple_code (stmt
))
340 enum tree_code code
= gimple_cond_code (stmt
);
342 /* We can handle all binary comparisons. Inequalities are
343 also supported as they can be represented with union of
345 if (!(code
== LT_EXPR
353 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, op_iter
, SSA_OP_ALL_USES
)
354 if (!graphite_can_represent_expr (scop_entry
, loop
, outermost_loop
,
356 /* We can not handle REAL_TYPE. Failed for pr39260. */
357 || TREE_CODE (TREE_TYPE (op
)) == REAL_TYPE
)
368 /* These nodes cut a new scope. */
375 /* Returns the statement of BB that contains a harmful operation: that
376 can be a function call with side effects, the induction variables
377 are not linear with respect to SCOP_ENTRY, etc. The current open
378 scop should end before this statement. The evaluation is limited using
379 OUTERMOST_LOOP as outermost loop that may change. */
382 harmful_stmt_in_bb (basic_block scop_entry
, loop_p outer_loop
, basic_block bb
)
384 gimple_stmt_iterator gsi
;
386 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
387 if (!stmt_simple_for_scop_p (scop_entry
, outer_loop
, gsi_stmt (gsi
), bb
))
388 return gsi_stmt (gsi
);
393 /* Return true when it is not possible to represent LOOP in the
394 polyhedral representation. This is evaluated taking SCOP_ENTRY and
395 OUTERMOST_LOOP in mind. */
398 graphite_can_represent_loop (basic_block scop_entry
, loop_p outermost_loop
,
401 tree niter
= number_of_latch_executions (loop
);
403 /* Number of iterations unknown. */
404 if (chrec_contains_undetermined (niter
))
407 /* Number of iterations not affine. */
408 if (!graphite_can_represent_expr (scop_entry
, loop
, outermost_loop
, niter
))
414 /* Store information needed by scopdet_* functions. */
418 /* Exit of the open scop would stop if the current BB is harmful. */
421 /* Where the next scop would start if the current BB is harmful. */
424 /* The bb or one of its children contains open loop exits. That means
425 loop exit nodes that are not surrounded by a loop dominated by bb. */
428 /* The bb or one of its children contains only structures we can handle. */
432 static struct scopdet_info
build_scops_1 (basic_block
, loop_p
,
433 VEC (sd_region
, heap
) **, loop_p
);
435 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
436 to SCOPS. TYPE is the gbb_type of BB. */
438 static struct scopdet_info
439 scopdet_basic_block_info (basic_block bb
, loop_p outermost_loop
,
440 VEC (sd_region
, heap
) **scops
, gbb_type type
)
442 loop_p loop
= bb
->loop_father
;
443 struct scopdet_info result
;
446 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
447 basic_block entry_block
= ENTRY_BLOCK_PTR
;
448 stmt
= harmful_stmt_in_bb (entry_block
, outermost_loop
, bb
);
449 result
.difficult
= (stmt
!= NULL
);
456 result
.exits
= false;
458 /* Mark bbs terminating a SESE region difficult, if they start
460 if (!single_succ_p (bb
))
461 result
.difficult
= true;
463 result
.exit
= single_succ (bb
);
468 result
.next
= single_succ (bb
);
469 result
.exits
= false;
470 result
.exit
= single_succ (bb
);
473 case GBB_LOOP_SING_EXIT_HEADER
:
475 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
476 struct scopdet_info sinfo
;
477 edge exit_e
= single_exit (loop
);
479 sinfo
= build_scops_1 (bb
, outermost_loop
, ®ions
, loop
);
481 if (!graphite_can_represent_loop (entry_block
, outermost_loop
, loop
))
482 result
.difficult
= true;
484 result
.difficult
|= sinfo
.difficult
;
486 /* Try again with another loop level. */
488 && loop_depth (outermost_loop
) + 1 == loop_depth (loop
))
490 outermost_loop
= loop
;
492 VEC_free (sd_region
, heap
, regions
);
493 regions
= VEC_alloc (sd_region
, heap
, 3);
495 sinfo
= scopdet_basic_block_info (bb
, outermost_loop
, scops
, type
);
498 result
.difficult
= true;
501 move_sd_regions (®ions
, scops
);
505 open_scop
.entry
= bb
;
506 open_scop
.exit
= exit_e
->dest
;
507 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
508 VEC_free (sd_region
, heap
, regions
);
513 result
.exit
= exit_e
->dest
;
514 result
.next
= exit_e
->dest
;
516 /* If we do not dominate result.next, remove it. It's either
517 the EXIT_BLOCK_PTR, or another bb dominates it and will
518 call the scop detection for this bb. */
519 if (!dominated_by_p (CDI_DOMINATORS
, result
.next
, bb
))
522 if (exit_e
->src
->loop_father
!= loop
)
525 result
.exits
= false;
527 if (result
.difficult
)
528 move_sd_regions (®ions
, scops
);
530 VEC_free (sd_region
, heap
, regions
);
536 case GBB_LOOP_MULT_EXIT_HEADER
:
538 /* XXX: For now we just do not join loops with multiple exits. If the
539 exits lead to the same bb it may be possible to join the loop. */
540 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
541 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
544 build_scops_1 (bb
, loop
, ®ions
, loop
);
546 /* Scan the code dominated by this loop. This means all bbs, that are
547 are dominated by a bb in this loop, but are not part of this loop.
550 - The loop exit destination is dominated by the exit sources.
552 TODO: We miss here the more complex cases:
553 - The exit destinations are dominated by another bb inside
555 - The loop dominates bbs, that are not exit destinations. */
556 for (i
= 0; VEC_iterate (edge
, exits
, i
, e
); i
++)
557 if (e
->src
->loop_father
== loop
558 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
))
560 if (loop_outer (outermost_loop
))
561 outermost_loop
= loop_outer (outermost_loop
);
563 /* Pass loop_outer to recognize e->dest as loop header in
565 if (e
->dest
->loop_father
->header
== e
->dest
)
566 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
567 loop_outer (e
->dest
->loop_father
));
569 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
570 e
->dest
->loop_father
);
575 result
.difficult
= true;
576 result
.exits
= false;
577 move_sd_regions (®ions
, scops
);
578 VEC_free (edge
, heap
, exits
);
581 case GBB_COND_HEADER
:
583 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
584 struct scopdet_info sinfo
;
585 VEC (basic_block
, heap
) *dominated
;
588 basic_block last_exit
= NULL
;
590 result
.exits
= false;
592 /* First check the successors of BB, and check if it is
593 possible to join the different branches. */
594 for (i
= 0; VEC_iterate (edge
, bb
->succs
, i
, e
); i
++)
596 /* Ignore loop exits. They will be handled after the loop
598 if (is_loop_exit (loop
, e
->dest
))
604 /* Do not follow edges that lead to the end of the
605 conditions block. For example, in
615 the edge from 0 => 6. Only check if all paths lead to
618 if (!single_pred_p (e
->dest
))
620 /* Check, if edge leads directly to the end of this
625 if (e
->dest
!= last_exit
)
626 result
.difficult
= true;
631 if (!dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
633 result
.difficult
= true;
637 sinfo
= build_scops_1 (e
->dest
, outermost_loop
, ®ions
, loop
);
639 result
.exits
|= sinfo
.exits
;
640 result
.difficult
|= sinfo
.difficult
;
642 /* Checks, if all branches end at the same point.
643 If that is true, the condition stays joinable.
644 Have a look at the example above. */
648 last_exit
= sinfo
.exit
;
650 if (sinfo
.exit
!= last_exit
)
651 result
.difficult
= true;
654 result
.difficult
= true;
658 result
.difficult
= true;
660 /* Join the branches of the condition if possible. */
661 if (!result
.exits
&& !result
.difficult
)
663 /* Only return a next pointer if we dominate this pointer.
664 Otherwise it will be handled by the bb dominating it. */
665 if (dominated_by_p (CDI_DOMINATORS
, last_exit
, bb
)
667 result
.next
= last_exit
;
671 result
.exit
= last_exit
;
673 VEC_free (sd_region
, heap
, regions
);
677 /* Scan remaining bbs dominated by BB. */
678 dominated
= get_dominated_by (CDI_DOMINATORS
, bb
);
680 for (i
= 0; VEC_iterate (basic_block
, dominated
, i
, dom_bb
); i
++)
682 /* Ignore loop exits: they will be handled after the loop body. */
683 if (loop_depth (find_common_loop (loop
, dom_bb
->loop_father
))
690 /* Ignore the bbs processed above. */
691 if (single_pred_p (dom_bb
) && single_pred (dom_bb
) == bb
)
694 if (loop_depth (loop
) > loop_depth (dom_bb
->loop_father
))
695 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
,
698 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
, loop
);
700 result
.exits
|= sinfo
.exits
;
701 result
.difficult
= true;
705 VEC_free (basic_block
, heap
, dominated
);
708 move_sd_regions (®ions
, scops
);
720 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
721 SCOPS. The analyse if a sd_region can be handled is based on the value
722 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
723 is the loop in which CURRENT is handled.
725 TODO: These functions got a little bit big. They definitely should be cleaned
728 static struct scopdet_info
729 build_scops_1 (basic_block current
, loop_p outermost_loop
,
730 VEC (sd_region
, heap
) **scops
, loop_p loop
)
732 bool in_scop
= false;
734 struct scopdet_info sinfo
;
736 /* Initialize result. */
737 struct scopdet_info result
;
738 result
.exits
= false;
739 result
.difficult
= false;
742 open_scop
.entry
= NULL
;
743 open_scop
.exit
= NULL
;
746 /* Loop over the dominance tree. If we meet a difficult bb, close
747 the current SCoP. Loop and condition header start a new layer,
748 and can only be added if all bbs in deeper layers are simple. */
749 while (current
!= NULL
)
751 sinfo
= scopdet_basic_block_info (current
, outermost_loop
, scops
,
752 get_bb_type (current
, loop
));
754 if (!in_scop
&& !(sinfo
.exits
|| sinfo
.difficult
))
756 open_scop
.entry
= current
;
757 open_scop
.exit
= NULL
;
760 else if (in_scop
&& (sinfo
.exits
|| sinfo
.difficult
))
762 open_scop
.exit
= current
;
763 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
767 result
.difficult
|= sinfo
.difficult
;
768 result
.exits
|= sinfo
.exits
;
770 current
= sinfo
.next
;
773 /* Try to close open_scop, if we are still in an open SCoP. */
776 open_scop
.exit
= sinfo
.exit
;
777 gcc_assert (open_scop
.exit
);
778 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
781 result
.exit
= sinfo
.exit
;
785 /* Checks if a bb is contained in REGION. */
788 bb_in_sd_region (basic_block bb
, sd_region
*region
)
790 return bb_in_region (bb
, region
->entry
, region
->exit
);
793 /* Returns the single entry edge of REGION, if it does not exits NULL. */
796 find_single_entry_edge (sd_region
*region
)
802 FOR_EACH_EDGE (e
, ei
, region
->entry
->preds
)
803 if (!bb_in_sd_region (e
->src
, region
))
818 /* Returns the single exit edge of REGION, if it does not exits NULL. */
821 find_single_exit_edge (sd_region
*region
)
827 FOR_EACH_EDGE (e
, ei
, region
->exit
->preds
)
828 if (bb_in_sd_region (e
->src
, region
))
843 /* Create a single entry edge for REGION. */
846 create_single_entry_edge (sd_region
*region
)
848 if (find_single_entry_edge (region
))
851 /* There are multiple predecessors for bb_3
864 There are two edges (1->3, 2->3), that point from outside into the region,
865 and another one (5->3), a loop latch, lead to bb_3.
873 | |\ (3.0 -> 3.1) = single entry edge
882 If the loop is part of the SCoP, we have to redirect the loop latches.
888 | | (3.0 -> 3.1) = entry edge
897 if (region
->entry
->loop_father
->header
!= region
->entry
898 || dominated_by_p (CDI_DOMINATORS
,
899 loop_latch_edge (region
->entry
->loop_father
)->src
,
902 edge forwarder
= split_block_after_labels (region
->entry
);
903 region
->entry
= forwarder
->dest
;
906 /* This case is never executed, as the loop headers seem always to have a
907 single edge pointing from outside into the loop. */
910 #ifdef ENABLE_CHECKING
911 gcc_assert (find_single_entry_edge (region
));
915 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
918 sd_region_without_exit (edge e
)
920 sd_region
*r
= (sd_region
*) e
->aux
;
923 return r
->exit
== NULL
;
928 /* Create a single exit edge for REGION. */
931 create_single_exit_edge (sd_region
*region
)
935 edge forwarder
= NULL
;
938 if (find_single_exit_edge (region
))
941 /* We create a forwarder bb (5) for all edges leaving this region
942 (3->5, 4->5). All other edges leading to the same bb, are moved
943 to a new bb (6). If these edges where part of another region (2->5)
944 we update the region->exit pointer, of this region.
946 To identify which edge belongs to which region we depend on the e->aux
947 pointer in every edge. It points to the region of the edge or to NULL,
948 if the edge is not part of any region.
950 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
951 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
956 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
957 | | \/ 3->5 no region, 4->5 no region,
959 \| / 5->6 region->exit = 6
962 Now there is only a single exit edge (5->6). */
965 forwarder
= make_forwarder_block (exit
, &sd_region_without_exit
, NULL
);
967 /* Unmark the edges, that are no longer exit edges. */
968 FOR_EACH_EDGE (e
, ei
, forwarder
->src
->preds
)
972 /* Mark the new exit edge. */
973 single_succ_edge (forwarder
->src
)->aux
= region
;
975 /* Update the exit bb of all regions, where exit edges lead to
977 FOR_EACH_EDGE (e
, ei
, forwarder
->dest
->preds
)
979 ((sd_region
*) e
->aux
)->exit
= forwarder
->dest
;
981 #ifdef ENABLE_CHECKING
982 gcc_assert (find_single_exit_edge (region
));
986 /* Unmark the exit edges of all REGIONS.
987 See comment in "create_single_exit_edge". */
990 unmark_exit_edges (VEC (sd_region
, heap
) *regions
)
997 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
998 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1003 /* Mark the exit edges of all REGIONS.
1004 See comment in "create_single_exit_edge". */
1007 mark_exit_edges (VEC (sd_region
, heap
) *regions
)
1014 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1015 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1016 if (bb_in_sd_region (e
->src
, s
))
1020 /* Create for all scop regions a single entry and a single exit edge. */
1023 create_sese_edges (VEC (sd_region
, heap
) *regions
)
1028 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1029 create_single_entry_edge (s
);
1031 mark_exit_edges (regions
);
1033 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1034 create_single_exit_edge (s
);
1036 unmark_exit_edges (regions
);
1038 fix_loop_structure (NULL
);
1040 #ifdef ENABLE_CHECKING
1041 verify_loop_structure ();
1042 verify_dominators (CDI_DOMINATORS
);
1047 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1050 build_graphite_scops (VEC (sd_region
, heap
) *regions
,
1051 VEC (scop_p
, heap
) **scops
)
1056 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1058 edge entry
= find_single_entry_edge (s
);
1059 edge exit
= find_single_exit_edge (s
);
1060 scop_p scop
= new_scop (new_sese (entry
, exit
));
1061 VEC_safe_push (scop_p
, heap
, *scops
, scop
);
1063 /* Are there overlapping SCoPs? */
1064 #ifdef ENABLE_CHECKING
1069 for (j
= 0; VEC_iterate (sd_region
, regions
, j
, s2
); j
++)
1071 gcc_assert (!bb_in_sd_region (s
->entry
, s2
));
1077 /* Returns true when BB contains only close phi nodes. */
1080 contains_only_close_phi_nodes (basic_block bb
)
1082 gimple_stmt_iterator gsi
;
1084 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1085 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_LABEL
)
1091 /* Print statistics for SCOP to FILE. */
1094 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
1099 long n_conditions
= 0;
1103 long n_p_conditions
= 0;
1109 gimple_stmt_iterator psi
;
1110 loop_p loop
= bb
->loop_father
;
1112 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
1116 n_p_bbs
+= bb
->count
;
1118 if (VEC_length (edge
, bb
->succs
) > 1)
1121 n_p_conditions
+= bb
->count
;
1124 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1127 n_p_stmts
+= bb
->count
;
1130 if (loop
->header
== bb
&& loop_in_sese_p (loop
, SCOP_REGION (scop
)))
1133 n_p_loops
+= bb
->count
;
1138 fprintf (file
, "\nBefore limit_scops SCoP statistics (");
1139 fprintf (file
, "BBS:%ld, ", n_bbs
);
1140 fprintf (file
, "LOOPS:%ld, ", n_loops
);
1141 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
1142 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
1143 fprintf (file
, "\nBefore limit_scops SCoP profiling statistics (");
1144 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
1145 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
1146 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
1147 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
1150 /* Print statistics for SCOPS to FILE. */
1153 print_graphite_statistics (FILE* file
, VEC (scop_p
, heap
) *scops
)
1158 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
1159 print_graphite_scop_statistics (file
, scop
);
1162 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1172 * SCoP frontier, as this line is not surrounded by any loop. *
1176 This is necessary as scalar evolution and parameter detection need a
1177 outermost loop to initialize parameters correctly.
1179 TODO: FIX scalar evolution and parameter detection to allow more flexible
1183 limit_scops (VEC (scop_p
, heap
) **scops
)
1185 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
1190 for (i
= 0; VEC_iterate (scop_p
, *scops
, i
, scop
); i
++)
1194 sese region
= SCOP_REGION (scop
);
1195 build_sese_loop_nests (region
);
1197 for (j
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), j
, loop
); j
++)
1198 if (!loop_in_sese_p (loop_outer (loop
), region
)
1199 && single_exit (loop
))
1201 sd_region open_scop
;
1202 open_scop
.entry
= loop
->header
;
1203 open_scop
.exit
= single_exit (loop
)->dest
;
1205 /* This is a hack on top of the limit_scops hack. The
1206 limit_scops hack should disappear all together. */
1207 if (single_succ_p (open_scop
.exit
)
1208 && contains_only_close_phi_nodes (open_scop
.exit
))
1209 open_scop
.exit
= single_succ_edge (open_scop
.exit
)->dest
;
1211 VEC_safe_push (sd_region
, heap
, regions
, &open_scop
);
1215 free_scops (*scops
);
1216 *scops
= VEC_alloc (scop_p
, heap
, 3);
1218 create_sese_edges (regions
);
1219 build_graphite_scops (regions
, scops
);
1220 VEC_free (sd_region
, heap
, regions
);
1223 /* Transforms LOOP to the canonical loop closed SSA form. */
1226 canonicalize_loop_closed_ssa (loop_p loop
)
1228 edge e
= single_exit (loop
);
1231 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
1236 if (VEC_length (edge
, bb
->preds
) == 1)
1237 split_block_after_labels (bb
);
1240 gimple_stmt_iterator psi
;
1241 basic_block close
= split_edge (e
);
1243 e
= single_succ_edge (close
);
1245 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1247 gimple phi
= gsi_stmt (psi
);
1250 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1251 if (gimple_phi_arg_edge (phi
, i
) == e
)
1253 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
1254 use_operand_p use_p
;
1257 if (TREE_CODE (arg
) != SSA_NAME
)
1260 close_phi
= create_phi_node (arg
, close
);
1261 res
= create_new_def_for (gimple_phi_result (close_phi
),
1263 gimple_phi_result_ptr (close_phi
));
1264 add_phi_arg (close_phi
, arg
,
1265 gimple_phi_arg_edge (close_phi
, 0),
1267 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
1268 replace_exp (use_p
, res
);
1275 /* Converts the current loop closed SSA form to a canonical form
1276 expected by the Graphite code generation.
1278 The loop closed SSA form has the following invariant: a variable
1279 defined in a loop that is used outside the loop appears only in the
1280 phi nodes in the destination of the loop exit. These phi nodes are
1281 called close phi nodes.
1283 The canonical loop closed SSA form contains the extra invariants:
1285 - when the loop contains only one exit, the close phi nodes contain
1286 only one argument. That implies that the basic block that contains
1287 the close phi nodes has only one predecessor, that is a basic block
1290 - the basic block containing the close phi nodes does not contain
1295 canonicalize_loop_closed_ssa_form (void)
1300 #ifdef ENABLE_CHECKING
1301 verify_loop_closed_ssa ();
1304 FOR_EACH_LOOP (li
, loop
, 0)
1305 canonicalize_loop_closed_ssa (loop
);
1307 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1308 update_ssa (TODO_update_ssa
);
1310 #ifdef ENABLE_CHECKING
1311 verify_loop_closed_ssa ();
1315 /* Find Static Control Parts (SCoP) in the current function and pushes
1319 build_scops (VEC (scop_p
, heap
) **scops
)
1321 struct loop
*loop
= current_loops
->tree_root
;
1322 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
1324 canonicalize_loop_closed_ssa_form ();
1325 build_scops_1 (single_succ (ENTRY_BLOCK_PTR
), ENTRY_BLOCK_PTR
->loop_father
,
1327 create_sese_edges (regions
);
1328 build_graphite_scops (regions
, scops
);
1330 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1331 print_graphite_statistics (dump_file
, *scops
);
1333 limit_scops (scops
);
1334 VEC_free (sd_region
, heap
, regions
);
1336 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1337 fprintf (dump_file
, "\nnumber of SCoPs: %d\n",
1338 VEC_length (scop_p
, *scops
));
1341 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1342 different colors. If there are not enough colors, paint the
1343 remaining SCoPs in gray.
1346 - "*" after the node number denotes the entry of a SCoP,
1347 - "#" after the node number denotes the exit of a SCoP,
1348 - "()" around the node number denotes the entry or the
1349 exit nodes of the SCOP. These are not part of SCoP. */
1352 dot_all_scops_1 (FILE *file
, VEC (scop_p
, heap
) *scops
)
1361 /* Disable debugging while printing graph. */
1362 int tmp_dump_flags
= dump_flags
;
1365 fprintf (file
, "digraph all {\n");
1369 int part_of_scop
= false;
1371 /* Use HTML for every bb label. So we are able to print bbs
1372 which are part of two different SCoPs, with two different
1373 background colors. */
1374 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1376 fprintf (file
, "CELLSPACING=\"0\">\n");
1378 /* Select color for SCoP. */
1379 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
1381 sese region
= SCOP_REGION (scop
);
1382 if (bb_in_sese_p (bb
, region
)
1383 || (SESE_EXIT_BB (region
) == bb
)
1384 || (SESE_ENTRY_BB (region
) == bb
))
1397 case 3: /* purple */
1400 case 4: /* orange */
1403 case 5: /* yellow */
1443 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color
);
1445 if (!bb_in_sese_p (bb
, region
))
1446 fprintf (file
, " (");
1448 if (bb
== SESE_ENTRY_BB (region
)
1449 && bb
== SESE_EXIT_BB (region
))
1450 fprintf (file
, " %d*# ", bb
->index
);
1451 else if (bb
== SESE_ENTRY_BB (region
))
1452 fprintf (file
, " %d* ", bb
->index
);
1453 else if (bb
== SESE_EXIT_BB (region
))
1454 fprintf (file
, " %d# ", bb
->index
);
1456 fprintf (file
, " %d ", bb
->index
);
1458 if (!bb_in_sese_p (bb
,region
))
1459 fprintf (file
, ")");
1461 fprintf (file
, "</TD></TR>\n");
1462 part_of_scop
= true;
1468 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1469 fprintf (file
, " %d </TD></TR>\n", bb
->index
);
1471 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1476 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1477 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
1480 fputs ("}\n\n", file
);
1482 /* Enable debugging again. */
1483 dump_flags
= tmp_dump_flags
;
1486 /* Display all SCoPs using dotty. */
1489 dot_all_scops (VEC (scop_p
, heap
) *scops
)
1491 /* When debugging, enable the following code. This cannot be used
1492 in production compilers because it calls "system". */
1495 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1496 gcc_assert (stream
);
1498 dot_all_scops_1 (stream
, scops
);
1501 x
= system ("dotty /tmp/allscops.dot &");
1503 dot_all_scops_1 (stderr
, scops
);
1507 /* Display all SCoPs using dotty. */
1510 dot_scop (scop_p scop
)
1512 VEC (scop_p
, heap
) *scops
= NULL
;
1515 VEC_safe_push (scop_p
, heap
, scops
, scop
);
1517 /* When debugging, enable the following code. This cannot be used
1518 in production compilers because it calls "system". */
1522 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1523 gcc_assert (stream
);
1525 dot_all_scops_1 (stream
, scops
);
1527 x
= system ("dotty /tmp/allscops.dot &");
1530 dot_all_scops_1 (stderr
, scops
);
1533 VEC_free (scop_p
, heap
, scops
);