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-scalar-evolution.h"
38 #include "tree-data-ref.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 host_integerp (TREE_OPERAND (e
, 1), 0);
173 return host_integerp (TREE_OPERAND (e
, 0), 0);
176 case POINTER_PLUS_EXPR
:
178 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
179 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
184 case NON_LVALUE_EXPR
:
185 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
194 /* Return true when SCEV can be represented in the polyhedral model.
196 An expression can be represented, if it can be expressed as an
197 affine expression. For loops (i, j) and parameters (m, n) all
198 affine expressions are of the form:
200 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
202 1 i + 20 j + (-2) m + 25
204 Something like "i * n" or "n * m" is not allowed.
206 OUTERMOST_LOOP defines the outermost loop that can variate. */
209 graphite_can_represent_scev (tree scev
, int outermost_loop
)
211 if (chrec_contains_undetermined (scev
))
214 if (TREE_CODE (scev
) == POLYNOMIAL_CHREC
216 /* Check for constant strides. With a non constant stride of
217 'n' we would have a value of 'iv * n'. */
218 && (!evolution_function_right_is_integer_cst (scev
)
220 /* Check the initial value: 'n * m' cannot be represented. */
221 || !graphite_can_represent_init (scev
)))
224 /* Only affine functions can be represented. */
225 if (!scev_is_linear_expression (scev
))
228 return evolution_function_is_invariant_p (scev
, outermost_loop
)
229 || evolution_function_is_affine_multivariate_p (scev
, outermost_loop
);
233 /* Return true when EXPR can be represented in the polyhedral model.
235 This means an expression can be represented, if it is linear with
236 respect to the loops and the strides are non parametric.
237 LOOP is the place where the expr will be evaluated and OUTERMOST_LOOP
238 defindes the outermost loop that can variate. SCOP_ENTRY defines the
239 entry of the region we analyse. */
242 graphite_can_represent_expr (basic_block scop_entry
, loop_p loop
,
243 loop_p outermost_loop
, tree expr
)
245 tree scev
= analyze_scalar_evolution (loop
, expr
);
247 scev
= instantiate_scev (scop_entry
, loop
, scev
);
249 return graphite_can_represent_scev (scev
, outermost_loop
->num
);
252 /* Return true if the data references of STMT can be represented by
256 stmt_has_simple_data_refs_p (loop_p outermost_loop
, gimple stmt
)
262 int loop
= outermost_loop
->num
;
263 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 5);
265 graphite_find_data_references_in_stmt (outermost_loop
, stmt
, &drs
);
267 for (j
= 0; VEC_iterate (data_reference_p
, drs
, j
, dr
); j
++)
268 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
269 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
), loop
))
276 free_data_refs (drs
);
280 /* Return false if the TREE_CODE of the operand OP or any of its operands
281 is a COMPONENT_REF. */
284 exclude_component_ref (tree op
)
292 if (TREE_CODE (op
) == COMPONENT_REF
)
295 len
= TREE_OPERAND_LENGTH (op
);
296 for (i
= 0; i
< len
; ++i
)
297 if (!exclude_component_ref (TREE_OPERAND (op
, i
)))
303 /* Return true if the operand OP used in STMT is simple in regards to
307 is_simple_operand (tree op
)
309 /* It is not a simple operand when it is a declaration or a
311 return !DECL_P (op
) && !AGGREGATE_TYPE_P (TREE_TYPE (op
))
312 && exclude_component_ref (op
);
315 /* Return true only when STMT is simple enough for being handled by
316 Graphite. This depends on SCOP_ENTRY, as the parameters are
317 initialized relatively to this basic block, the linear functions
318 are initialized to OUTERMOST_LOOP and BB is the place where we try
319 to evaluate the STMT. */
322 stmt_simple_for_scop_p (basic_block scop_entry
, loop_p outermost_loop
,
323 gimple stmt
, basic_block bb
)
325 loop_p loop
= bb
->loop_father
;
327 gcc_assert (scop_entry
);
329 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
330 Calls have side-effects, except those to const or pure
332 if (gimple_has_volatile_ops (stmt
)
333 || (gimple_code (stmt
) == GIMPLE_CALL
334 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
335 || (gimple_code (stmt
) == GIMPLE_ASM
))
338 if (!stmt_has_simple_data_refs_p (outermost_loop
, stmt
))
341 switch (gimple_code (stmt
))
351 enum tree_code code
= gimple_cond_code (stmt
);
353 /* We can handle all binary comparisons. Inequalities are
354 also supported as they can be represented with union of
356 if (!(code
== LT_EXPR
364 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, op_iter
, SSA_OP_ALL_USES
)
365 if (!graphite_can_represent_expr (scop_entry
, loop
, outermost_loop
,
367 /* We can not handle REAL_TYPE. Failed for pr39260. */
368 || TREE_CODE (TREE_TYPE (op
)) == REAL_TYPE
)
376 enum tree_code code
= gimple_assign_rhs_code (stmt
);
378 switch (get_gimple_rhs_class (code
))
380 case GIMPLE_UNARY_RHS
:
381 case GIMPLE_SINGLE_RHS
:
382 return (is_simple_operand (gimple_assign_lhs (stmt
))
383 && is_simple_operand (gimple_assign_rhs1 (stmt
)));
385 case GIMPLE_BINARY_RHS
:
386 return (is_simple_operand (gimple_assign_lhs (stmt
))
387 && is_simple_operand (gimple_assign_rhs1 (stmt
))
388 && is_simple_operand (gimple_assign_rhs2 (stmt
)));
390 case GIMPLE_INVALID_RHS
:
399 size_t n
= gimple_call_num_args (stmt
);
400 tree lhs
= gimple_call_lhs (stmt
);
402 if (lhs
&& !is_simple_operand (lhs
))
405 for (i
= 0; i
< n
; i
++)
406 if (!is_simple_operand (gimple_call_arg (stmt
, i
)))
413 /* These nodes cut a new scope. */
420 /* Returns the statement of BB that contains a harmful operation: that
421 can be a function call with side effects, the induction variables
422 are not linear with respect to SCOP_ENTRY, etc. The current open
423 scop should end before this statement. The evaluation is limited using
424 OUTERMOST_LOOP as outermost loop that may change. */
427 harmful_stmt_in_bb (basic_block scop_entry
, loop_p outer_loop
, basic_block bb
)
429 gimple_stmt_iterator gsi
;
431 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
432 if (!stmt_simple_for_scop_p (scop_entry
, outer_loop
, gsi_stmt (gsi
), bb
))
433 return gsi_stmt (gsi
);
438 /* Return true when it is not possible to represent LOOP in the
439 polyhedral representation. This is evaluated taking SCOP_ENTRY and
440 OUTERMOST_LOOP in mind. */
443 graphite_can_represent_loop (basic_block scop_entry
, loop_p outermost_loop
,
446 tree niter
= number_of_latch_executions (loop
);
448 /* Number of iterations unknown. */
449 if (chrec_contains_undetermined (niter
))
452 /* Number of iterations not affine. */
453 if (!graphite_can_represent_expr (scop_entry
, loop
, outermost_loop
, niter
))
459 /* Store information needed by scopdet_* functions. */
463 /* Exit of the open scop would stop if the current BB is harmful. */
466 /* Where the next scop would start if the current BB is harmful. */
469 /* The bb or one of its children contains open loop exits. That means
470 loop exit nodes that are not surrounded by a loop dominated by bb. */
473 /* The bb or one of its children contains only structures we can handle. */
477 static struct scopdet_info
build_scops_1 (basic_block
, loop_p
,
478 VEC (sd_region
, heap
) **, loop_p
);
480 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
481 to SCOPS. TYPE is the gbb_type of BB. */
483 static struct scopdet_info
484 scopdet_basic_block_info (basic_block bb
, loop_p outermost_loop
,
485 VEC (sd_region
, heap
) **scops
, gbb_type type
)
487 loop_p loop
= bb
->loop_father
;
488 struct scopdet_info result
;
491 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
492 basic_block entry_block
= ENTRY_BLOCK_PTR
;
493 stmt
= harmful_stmt_in_bb (entry_block
, outermost_loop
, bb
);
494 result
.difficult
= (stmt
!= NULL
);
501 result
.exits
= false;
503 /* Mark bbs terminating a SESE region difficult, if they start
505 if (!single_succ_p (bb
))
506 result
.difficult
= true;
508 result
.exit
= single_succ (bb
);
513 result
.next
= single_succ (bb
);
514 result
.exits
= false;
515 result
.exit
= single_succ (bb
);
518 case GBB_LOOP_SING_EXIT_HEADER
:
520 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
521 struct scopdet_info sinfo
;
522 edge exit_e
= single_exit (loop
);
524 sinfo
= build_scops_1 (bb
, outermost_loop
, ®ions
, loop
);
526 if (!graphite_can_represent_loop (entry_block
, outermost_loop
, loop
))
527 result
.difficult
= true;
529 result
.difficult
|= sinfo
.difficult
;
531 /* Try again with another loop level. */
533 && loop_depth (outermost_loop
) + 1 == loop_depth (loop
))
535 outermost_loop
= loop
;
537 VEC_free (sd_region
, heap
, regions
);
538 regions
= VEC_alloc (sd_region
, heap
, 3);
540 sinfo
= scopdet_basic_block_info (bb
, outermost_loop
, scops
, type
);
543 result
.difficult
= true;
546 move_sd_regions (®ions
, scops
);
550 open_scop
.entry
= bb
;
551 open_scop
.exit
= exit_e
->dest
;
552 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
553 VEC_free (sd_region
, heap
, regions
);
558 result
.exit
= exit_e
->dest
;
559 result
.next
= exit_e
->dest
;
561 /* If we do not dominate result.next, remove it. It's either
562 the EXIT_BLOCK_PTR, or another bb dominates it and will
563 call the scop detection for this bb. */
564 if (!dominated_by_p (CDI_DOMINATORS
, result
.next
, bb
))
567 if (exit_e
->src
->loop_father
!= loop
)
570 result
.exits
= false;
572 if (result
.difficult
)
573 move_sd_regions (®ions
, scops
);
575 VEC_free (sd_region
, heap
, regions
);
581 case GBB_LOOP_MULT_EXIT_HEADER
:
583 /* XXX: For now we just do not join loops with multiple exits. If the
584 exits lead to the same bb it may be possible to join the loop. */
585 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
586 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
589 build_scops_1 (bb
, loop
, ®ions
, loop
);
591 /* Scan the code dominated by this loop. This means all bbs, that are
592 are dominated by a bb in this loop, but are not part of this loop.
595 - The loop exit destination is dominated by the exit sources.
597 TODO: We miss here the more complex cases:
598 - The exit destinations are dominated by another bb inside
600 - The loop dominates bbs, that are not exit destinations. */
601 for (i
= 0; VEC_iterate (edge
, exits
, i
, e
); i
++)
602 if (e
->src
->loop_father
== loop
603 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
))
605 if (loop_outer (outermost_loop
))
606 outermost_loop
= loop_outer (outermost_loop
);
608 /* Pass loop_outer to recognize e->dest as loop header in
610 if (e
->dest
->loop_father
->header
== e
->dest
)
611 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
612 loop_outer (e
->dest
->loop_father
));
614 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
615 e
->dest
->loop_father
);
620 result
.difficult
= true;
621 result
.exits
= false;
622 move_sd_regions (®ions
, scops
);
623 VEC_free (edge
, heap
, exits
);
626 case GBB_COND_HEADER
:
628 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
629 struct scopdet_info sinfo
;
630 VEC (basic_block
, heap
) *dominated
;
633 basic_block last_exit
= NULL
;
635 result
.exits
= false;
637 /* First check the successors of BB, and check if it is
638 possible to join the different branches. */
639 for (i
= 0; VEC_iterate (edge
, bb
->succs
, i
, e
); i
++)
641 /* Ignore loop exits. They will be handled after the loop
643 if (is_loop_exit (loop
, e
->dest
))
649 /* Do not follow edges that lead to the end of the
650 conditions block. For example, in
660 the edge from 0 => 6. Only check if all paths lead to
663 if (!single_pred_p (e
->dest
))
665 /* Check, if edge leads directly to the end of this
670 if (e
->dest
!= last_exit
)
671 result
.difficult
= true;
676 if (!dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
678 result
.difficult
= true;
682 sinfo
= build_scops_1 (e
->dest
, outermost_loop
, ®ions
, loop
);
684 result
.exits
|= sinfo
.exits
;
685 result
.difficult
|= sinfo
.difficult
;
687 /* Checks, if all branches end at the same point.
688 If that is true, the condition stays joinable.
689 Have a look at the example above. */
693 last_exit
= sinfo
.exit
;
695 if (sinfo
.exit
!= last_exit
)
696 result
.difficult
= true;
699 result
.difficult
= true;
703 result
.difficult
= true;
705 /* Join the branches of the condition if possible. */
706 if (!result
.exits
&& !result
.difficult
)
708 /* Only return a next pointer if we dominate this pointer.
709 Otherwise it will be handled by the bb dominating it. */
710 if (dominated_by_p (CDI_DOMINATORS
, last_exit
, bb
)
712 result
.next
= last_exit
;
716 result
.exit
= last_exit
;
718 VEC_free (sd_region
, heap
, regions
);
722 /* Scan remaining bbs dominated by BB. */
723 dominated
= get_dominated_by (CDI_DOMINATORS
, bb
);
725 for (i
= 0; VEC_iterate (basic_block
, dominated
, i
, dom_bb
); i
++)
727 /* Ignore loop exits: they will be handled after the loop body. */
728 if (loop_depth (find_common_loop (loop
, dom_bb
->loop_father
))
735 /* Ignore the bbs processed above. */
736 if (single_pred_p (dom_bb
) && single_pred (dom_bb
) == bb
)
739 if (loop_depth (loop
) > loop_depth (dom_bb
->loop_father
))
740 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
,
743 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
, loop
);
745 result
.exits
|= sinfo
.exits
;
746 result
.difficult
= true;
750 VEC_free (basic_block
, heap
, dominated
);
753 move_sd_regions (®ions
, scops
);
765 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
766 SCOPS. The analyse if a sd_region can be handled is based on the value
767 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
768 is the loop in which CURRENT is handled.
770 TODO: These functions got a little bit big. They definitely should be cleaned
773 static struct scopdet_info
774 build_scops_1 (basic_block current
, loop_p outermost_loop
,
775 VEC (sd_region
, heap
) **scops
, loop_p loop
)
777 bool in_scop
= false;
779 struct scopdet_info sinfo
;
781 /* Initialize result. */
782 struct scopdet_info result
;
783 result
.exits
= false;
784 result
.difficult
= false;
787 open_scop
.entry
= NULL
;
788 open_scop
.exit
= NULL
;
791 /* Loop over the dominance tree. If we meet a difficult bb, close
792 the current SCoP. Loop and condition header start a new layer,
793 and can only be added if all bbs in deeper layers are simple. */
794 while (current
!= NULL
)
796 sinfo
= scopdet_basic_block_info (current
, outermost_loop
, scops
,
797 get_bb_type (current
, loop
));
799 if (!in_scop
&& !(sinfo
.exits
|| sinfo
.difficult
))
801 open_scop
.entry
= current
;
802 open_scop
.exit
= NULL
;
805 else if (in_scop
&& (sinfo
.exits
|| sinfo
.difficult
))
807 open_scop
.exit
= current
;
808 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
812 result
.difficult
|= sinfo
.difficult
;
813 result
.exits
|= sinfo
.exits
;
815 current
= sinfo
.next
;
818 /* Try to close open_scop, if we are still in an open SCoP. */
821 open_scop
.exit
= sinfo
.exit
;
822 gcc_assert (open_scop
.exit
);
823 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
826 result
.exit
= sinfo
.exit
;
830 /* Checks if a bb is contained in REGION. */
833 bb_in_sd_region (basic_block bb
, sd_region
*region
)
835 return bb_in_region (bb
, region
->entry
, region
->exit
);
838 /* Returns the single entry edge of REGION, if it does not exits NULL. */
841 find_single_entry_edge (sd_region
*region
)
847 FOR_EACH_EDGE (e
, ei
, region
->entry
->preds
)
848 if (!bb_in_sd_region (e
->src
, region
))
863 /* Returns the single exit edge of REGION, if it does not exits NULL. */
866 find_single_exit_edge (sd_region
*region
)
872 FOR_EACH_EDGE (e
, ei
, region
->exit
->preds
)
873 if (bb_in_sd_region (e
->src
, region
))
888 /* Create a single entry edge for REGION. */
891 create_single_entry_edge (sd_region
*region
)
893 if (find_single_entry_edge (region
))
896 /* There are multiple predecessors for bb_3
909 There are two edges (1->3, 2->3), that point from outside into the region,
910 and another one (5->3), a loop latch, lead to bb_3.
918 | |\ (3.0 -> 3.1) = single entry edge
927 If the loop is part of the SCoP, we have to redirect the loop latches.
933 | | (3.0 -> 3.1) = entry edge
942 if (region
->entry
->loop_father
->header
!= region
->entry
943 || dominated_by_p (CDI_DOMINATORS
,
944 loop_latch_edge (region
->entry
->loop_father
)->src
,
947 edge forwarder
= split_block_after_labels (region
->entry
);
948 region
->entry
= forwarder
->dest
;
951 /* This case is never executed, as the loop headers seem always to have a
952 single edge pointing from outside into the loop. */
955 #ifdef ENABLE_CHECKING
956 gcc_assert (find_single_entry_edge (region
));
960 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
963 sd_region_without_exit (edge e
)
965 sd_region
*r
= (sd_region
*) e
->aux
;
968 return r
->exit
== NULL
;
973 /* Create a single exit edge for REGION. */
976 create_single_exit_edge (sd_region
*region
)
980 edge forwarder
= NULL
;
983 if (find_single_exit_edge (region
))
986 /* We create a forwarder bb (5) for all edges leaving this region
987 (3->5, 4->5). All other edges leading to the same bb, are moved
988 to a new bb (6). If these edges where part of another region (2->5)
989 we update the region->exit pointer, of this region.
991 To identify which edge belongs to which region we depend on the e->aux
992 pointer in every edge. It points to the region of the edge or to NULL,
993 if the edge is not part of any region.
995 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
996 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
1001 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
1002 | | \/ 3->5 no region, 4->5 no region,
1004 \| / 5->6 region->exit = 6
1007 Now there is only a single exit edge (5->6). */
1008 exit
= region
->exit
;
1009 region
->exit
= NULL
;
1010 forwarder
= make_forwarder_block (exit
, &sd_region_without_exit
, NULL
);
1012 /* Unmark the edges, that are no longer exit edges. */
1013 FOR_EACH_EDGE (e
, ei
, forwarder
->src
->preds
)
1017 /* Mark the new exit edge. */
1018 single_succ_edge (forwarder
->src
)->aux
= region
;
1020 /* Update the exit bb of all regions, where exit edges lead to
1022 FOR_EACH_EDGE (e
, ei
, forwarder
->dest
->preds
)
1024 ((sd_region
*) e
->aux
)->exit
= forwarder
->dest
;
1026 #ifdef ENABLE_CHECKING
1027 gcc_assert (find_single_exit_edge (region
));
1031 /* Unmark the exit edges of all REGIONS.
1032 See comment in "create_single_exit_edge". */
1035 unmark_exit_edges (VEC (sd_region
, heap
) *regions
)
1042 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1043 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1048 /* Mark the exit edges of all REGIONS.
1049 See comment in "create_single_exit_edge". */
1052 mark_exit_edges (VEC (sd_region
, heap
) *regions
)
1059 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1060 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1061 if (bb_in_sd_region (e
->src
, s
))
1065 /* Create for all scop regions a single entry and a single exit edge. */
1068 create_sese_edges (VEC (sd_region
, heap
) *regions
)
1073 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1074 create_single_entry_edge (s
);
1076 mark_exit_edges (regions
);
1078 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1079 create_single_exit_edge (s
);
1081 unmark_exit_edges (regions
);
1083 fix_loop_structure (NULL
);
1085 #ifdef ENABLE_CHECKING
1086 verify_loop_structure ();
1087 verify_dominators (CDI_DOMINATORS
);
1092 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1095 build_graphite_scops (VEC (sd_region
, heap
) *regions
,
1096 VEC (scop_p
, heap
) **scops
)
1101 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1103 edge entry
= find_single_entry_edge (s
);
1104 edge exit
= find_single_exit_edge (s
);
1105 scop_p scop
= new_scop (new_sese (entry
, exit
));
1106 VEC_safe_push (scop_p
, heap
, *scops
, scop
);
1108 /* Are there overlapping SCoPs? */
1109 #ifdef ENABLE_CHECKING
1114 for (j
= 0; VEC_iterate (sd_region
, regions
, j
, s2
); j
++)
1116 gcc_assert (!bb_in_sd_region (s
->entry
, s2
));
1122 /* Returns true when BB contains only close phi nodes. */
1125 contains_only_close_phi_nodes (basic_block bb
)
1127 gimple_stmt_iterator gsi
;
1129 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1130 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_LABEL
)
1136 /* Print statistics for SCOP to FILE. */
1139 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
1144 long n_conditions
= 0;
1148 long n_p_conditions
= 0;
1154 gimple_stmt_iterator psi
;
1155 loop_p loop
= bb
->loop_father
;
1157 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
1161 n_p_bbs
+= bb
->count
;
1163 if (VEC_length (edge
, bb
->succs
) > 1)
1166 n_p_conditions
+= bb
->count
;
1169 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1172 n_p_stmts
+= bb
->count
;
1175 if (loop
->header
== bb
&& loop_in_sese_p (loop
, SCOP_REGION (scop
)))
1178 n_p_loops
+= bb
->count
;
1183 fprintf (file
, "\nBefore limit_scops SCoP statistics (");
1184 fprintf (file
, "BBS:%ld, ", n_bbs
);
1185 fprintf (file
, "LOOPS:%ld, ", n_loops
);
1186 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
1187 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
1188 fprintf (file
, "\nBefore limit_scops SCoP profiling statistics (");
1189 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
1190 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
1191 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
1192 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
1195 /* Print statistics for SCOPS to FILE. */
1198 print_graphite_statistics (FILE* file
, VEC (scop_p
, heap
) *scops
)
1203 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
1204 print_graphite_scop_statistics (file
, scop
);
1207 /* Version of free_scops special cased for limit_scops. */
1210 free_scops_1 (VEC (scop_p
, heap
) **scops
)
1215 for (i
= 0; VEC_iterate (scop_p
, *scops
, i
, scop
); i
++)
1217 sese region
= SCOP_REGION (scop
);
1218 free (SESE_PARAMS_NAMES (region
));
1219 SESE_PARAMS_NAMES (region
) = 0;
1222 free_scops (*scops
);
1225 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1235 * SCoP frontier, as this line is not surrounded by any loop. *
1239 This is necessary as scalar evolution and parameter detection need a
1240 outermost loop to initialize parameters correctly.
1242 TODO: FIX scalar evolution and parameter detection to allow more flexible
1246 limit_scops (VEC (scop_p
, heap
) **scops
)
1248 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
1253 for (i
= 0; VEC_iterate (scop_p
, *scops
, i
, scop
); i
++)
1257 sese region
= SCOP_REGION (scop
);
1258 build_sese_loop_nests (region
);
1260 for (j
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), j
, loop
); j
++)
1261 if (!loop_in_sese_p (loop_outer (loop
), region
)
1262 && single_exit (loop
))
1264 sd_region open_scop
;
1265 open_scop
.entry
= loop
->header
;
1266 open_scop
.exit
= single_exit (loop
)->dest
;
1268 /* This is a hack on top of the limit_scops hack. The
1269 limit_scops hack should disappear all together. */
1270 if (single_succ_p (open_scop
.exit
)
1271 && contains_only_close_phi_nodes (open_scop
.exit
))
1272 open_scop
.exit
= single_succ_edge (open_scop
.exit
)->dest
;
1274 VEC_safe_push (sd_region
, heap
, regions
, &open_scop
);
1278 free_scops_1 (scops
);
1279 *scops
= VEC_alloc (scop_p
, heap
, 3);
1281 create_sese_edges (regions
);
1282 build_graphite_scops (regions
, scops
);
1283 VEC_free (sd_region
, heap
, regions
);
1286 /* Transforms LOOP to the canonical loop closed SSA form. */
1289 canonicalize_loop_closed_ssa (loop_p loop
)
1291 edge e
= single_exit (loop
);
1294 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
1299 if (VEC_length (edge
, bb
->preds
) == 1)
1300 split_block_after_labels (bb
);
1303 gimple_stmt_iterator psi
;
1304 basic_block close
= split_edge (e
);
1306 e
= single_succ_edge (close
);
1308 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1310 gimple phi
= gsi_stmt (psi
);
1313 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1314 if (gimple_phi_arg_edge (phi
, i
) == e
)
1316 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
1317 use_operand_p use_p
;
1320 if (TREE_CODE (arg
) != SSA_NAME
)
1323 close_phi
= create_phi_node (arg
, close
);
1324 res
= create_new_def_for (gimple_phi_result (close_phi
),
1326 gimple_phi_result_ptr (close_phi
));
1327 add_phi_arg (close_phi
, arg
,
1328 gimple_phi_arg_edge (close_phi
, 0),
1330 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
1331 replace_exp (use_p
, res
);
1338 /* Converts the current loop closed SSA form to a canonical form
1339 expected by the Graphite code generation.
1341 The loop closed SSA form has the following invariant: a variable
1342 defined in a loop that is used outside the loop appears only in the
1343 phi nodes in the destination of the loop exit. These phi nodes are
1344 called close phi nodes.
1346 The canonical loop closed SSA form contains the extra invariants:
1348 - when the loop contains only one exit, the close phi nodes contain
1349 only one argument. That implies that the basic block that contains
1350 the close phi nodes has only one predecessor, that is a basic block
1353 - the basic block containing the close phi nodes does not contain
1358 canonicalize_loop_closed_ssa_form (void)
1363 #ifdef ENABLE_CHECKING
1364 verify_loop_closed_ssa ();
1367 FOR_EACH_LOOP (li
, loop
, 0)
1368 canonicalize_loop_closed_ssa (loop
);
1370 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1371 update_ssa (TODO_update_ssa
);
1373 #ifdef ENABLE_CHECKING
1374 verify_loop_closed_ssa ();
1378 /* Find Static Control Parts (SCoP) in the current function and pushes
1382 build_scops (VEC (scop_p
, heap
) **scops
)
1384 struct loop
*loop
= current_loops
->tree_root
;
1385 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
1387 canonicalize_loop_closed_ssa_form ();
1388 build_scops_1 (single_succ (ENTRY_BLOCK_PTR
), ENTRY_BLOCK_PTR
->loop_father
,
1390 create_sese_edges (regions
);
1391 build_graphite_scops (regions
, scops
);
1393 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1394 print_graphite_statistics (dump_file
, *scops
);
1396 limit_scops (scops
);
1397 VEC_free (sd_region
, heap
, regions
);
1399 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1400 fprintf (dump_file
, "\nnumber of SCoPs: %d\n",
1401 VEC_length (scop_p
, *scops
));
1404 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1405 different colors. If there are not enough colors, paint the
1406 remaining SCoPs in gray.
1409 - "*" after the node number denotes the entry of a SCoP,
1410 - "#" after the node number denotes the exit of a SCoP,
1411 - "()" around the node number denotes the entry or the
1412 exit nodes of the SCOP. These are not part of SCoP. */
1415 dot_all_scops_1 (FILE *file
, VEC (scop_p
, heap
) *scops
)
1424 /* Disable debugging while printing graph. */
1425 int tmp_dump_flags
= dump_flags
;
1428 fprintf (file
, "digraph all {\n");
1432 int part_of_scop
= false;
1434 /* Use HTML for every bb label. So we are able to print bbs
1435 which are part of two different SCoPs, with two different
1436 background colors. */
1437 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1439 fprintf (file
, "CELLSPACING=\"0\">\n");
1441 /* Select color for SCoP. */
1442 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
1444 sese region
= SCOP_REGION (scop
);
1445 if (bb_in_sese_p (bb
, region
)
1446 || (SESE_EXIT_BB (region
) == bb
)
1447 || (SESE_ENTRY_BB (region
) == bb
))
1460 case 3: /* purple */
1463 case 4: /* orange */
1466 case 5: /* yellow */
1506 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color
);
1508 if (!bb_in_sese_p (bb
, region
))
1509 fprintf (file
, " (");
1511 if (bb
== SESE_ENTRY_BB (region
)
1512 && bb
== SESE_EXIT_BB (region
))
1513 fprintf (file
, " %d*# ", bb
->index
);
1514 else if (bb
== SESE_ENTRY_BB (region
))
1515 fprintf (file
, " %d* ", bb
->index
);
1516 else if (bb
== SESE_EXIT_BB (region
))
1517 fprintf (file
, " %d# ", bb
->index
);
1519 fprintf (file
, " %d ", bb
->index
);
1521 if (!bb_in_sese_p (bb
,region
))
1522 fprintf (file
, ")");
1524 fprintf (file
, "</TD></TR>\n");
1525 part_of_scop
= true;
1531 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1532 fprintf (file
, " %d </TD></TR>\n", bb
->index
);
1534 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1539 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1540 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
1543 fputs ("}\n\n", file
);
1545 /* Enable debugging again. */
1546 dump_flags
= tmp_dump_flags
;
1549 /* Display all SCoPs using dotty. */
1552 dot_all_scops (VEC (scop_p
, heap
) *scops
)
1554 /* When debugging, enable the following code. This cannot be used
1555 in production compilers because it calls "system". */
1558 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1559 gcc_assert (stream
);
1561 dot_all_scops_1 (stream
, scops
);
1564 x
= system ("dotty /tmp/allscops.dot");
1566 dot_all_scops_1 (stderr
, scops
);
1570 /* Display all SCoPs using dotty. */
1573 dot_scop (scop_p scop
)
1575 VEC (scop_p
, heap
) *scops
= NULL
;
1578 VEC_safe_push (scop_p
, heap
, scops
, scop
);
1580 /* When debugging, enable the following code. This cannot be used
1581 in production compilers because it calls "system". */
1585 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1586 gcc_assert (stream
);
1588 dot_all_scops_1 (stream
, scops
);
1590 x
= system ("dotty /tmp/allscops.dot");
1593 dot_all_scops_1 (stderr
, scops
);
1596 VEC_free (scop_p
, heap
, scops
);