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 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 false if the tree_code of the operand OP or any of its operands
256 exclude_component_ref (tree op
)
264 if (TREE_CODE (op
) == COMPONENT_REF
)
267 len
= TREE_OPERAND_LENGTH (op
);
268 for (i
= 0; i
< len
; ++i
)
269 if (!exclude_component_ref (TREE_OPERAND (op
, i
)))
275 /* Return true if the data references of STMT can be represented by
279 stmt_has_simple_data_refs_p (loop_p outermost_loop
, gimple stmt
)
285 int loop
= outermost_loop
->num
;
286 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 5);
288 graphite_find_data_references_in_stmt (outermost_loop
, stmt
, &drs
);
290 for (j
= 0; VEC_iterate (data_reference_p
, drs
, j
, dr
); j
++)
291 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
292 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
), loop
))
299 free_data_refs (drs
);
303 /* Return true if we can create an affine data-ref for OP in STMT
304 in regards to OUTERMOST_LOOP. */
307 stmt_simple_memref_p (loop_p outermost_loop
, gimple stmt
, tree op
)
315 dr
= create_data_ref (outermost_loop
, op
, stmt
, true);
316 fns
= DR_ACCESS_FNS (dr
);
318 for (i
= 0; VEC_iterate (tree
, fns
, i
, t
); i
++)
319 if (!graphite_can_represent_scev (t
, outermost_loop
->num
))
329 /* Return true if the operand OP used in STMT is simple in regards to
333 is_simple_operand (loop_p outermost_loop
, gimple stmt
, tree op
)
335 /* It is not a simple operand when it is a declaration, */
339 /* or a structure, */
340 if (AGGREGATE_TYPE_P (TREE_TYPE (op
)))
343 /* or a memory access that cannot be analyzed by the data reference
345 if (handled_component_p (op
) || INDIRECT_REF_P (op
))
346 if (!stmt_simple_memref_p (outermost_loop
, stmt
, op
))
349 return exclude_component_ref (op
);
352 /* Return true only when STMT is simple enough for being handled by
353 Graphite. This depends on SCOP_ENTRY, as the parameters are
354 initialized relatively to this basic block, the linear functions
355 are initialized to OUTERMOST_LOOP and BB is the place where we try
356 to evaluate the STMT. */
359 stmt_simple_for_scop_p (basic_block scop_entry
, loop_p outermost_loop
,
360 gimple stmt
, basic_block bb
)
362 loop_p loop
= bb
->loop_father
;
364 gcc_assert (scop_entry
);
366 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
367 Calls have side-effects, except those to const or pure
369 if (gimple_has_volatile_ops (stmt
)
370 || (gimple_code (stmt
) == GIMPLE_CALL
371 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
372 || (gimple_code (stmt
) == GIMPLE_ASM
))
375 if (!stmt_has_simple_data_refs_p (outermost_loop
, stmt
))
378 switch (gimple_code (stmt
))
388 enum tree_code code
= gimple_cond_code (stmt
);
390 /* We can handle all binary comparisons. Inequalities are
391 also supported as they can be represented with union of
393 if (!(code
== LT_EXPR
401 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, op_iter
, SSA_OP_ALL_USES
)
402 if (!graphite_can_represent_expr (scop_entry
, loop
, outermost_loop
,
404 /* We can not handle REAL_TYPE. Failed for pr39260. */
405 || TREE_CODE (TREE_TYPE (op
)) == REAL_TYPE
)
413 enum tree_code code
= gimple_assign_rhs_code (stmt
);
415 switch (get_gimple_rhs_class (code
))
417 case GIMPLE_UNARY_RHS
:
418 case GIMPLE_SINGLE_RHS
:
419 return (is_simple_operand (outermost_loop
, stmt
,
420 gimple_assign_lhs (stmt
))
421 && is_simple_operand (outermost_loop
, stmt
,
422 gimple_assign_rhs1 (stmt
)));
424 case GIMPLE_BINARY_RHS
:
425 return (is_simple_operand (outermost_loop
, stmt
,
426 gimple_assign_lhs (stmt
))
427 && is_simple_operand (outermost_loop
, stmt
,
428 gimple_assign_rhs1 (stmt
))
429 && is_simple_operand (outermost_loop
, stmt
,
430 gimple_assign_rhs2 (stmt
)));
432 case GIMPLE_INVALID_RHS
:
441 size_t n
= gimple_call_num_args (stmt
);
442 tree lhs
= gimple_call_lhs (stmt
);
444 if (lhs
&& !is_simple_operand (outermost_loop
, stmt
, lhs
))
447 for (i
= 0; i
< n
; i
++)
448 if (!is_simple_operand (outermost_loop
, stmt
,
449 gimple_call_arg (stmt
, i
)))
456 /* These nodes cut a new scope. */
463 /* Returns the statement of BB that contains a harmful operation: that
464 can be a function call with side effects, the induction variables
465 are not linear with respect to SCOP_ENTRY, etc. The current open
466 scop should end before this statement. The evaluation is limited using
467 OUTERMOST_LOOP as outermost loop that may change. */
470 harmful_stmt_in_bb (basic_block scop_entry
, loop_p outer_loop
, basic_block bb
)
472 gimple_stmt_iterator gsi
;
474 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
475 if (!stmt_simple_for_scop_p (scop_entry
, outer_loop
, gsi_stmt (gsi
), bb
))
476 return gsi_stmt (gsi
);
481 /* Return true when it is not possible to represent LOOP in the
482 polyhedral representation. This is evaluated taking SCOP_ENTRY and
483 OUTERMOST_LOOP in mind. */
486 graphite_can_represent_loop (basic_block scop_entry
, loop_p outermost_loop
,
489 tree niter
= number_of_latch_executions (loop
);
491 /* Number of iterations unknown. */
492 if (chrec_contains_undetermined (niter
))
495 /* Number of iterations not affine. */
496 if (!graphite_can_represent_expr (scop_entry
, loop
, outermost_loop
, niter
))
502 /* Store information needed by scopdet_* functions. */
506 /* Exit of the open scop would stop if the current BB is harmful. */
509 /* Where the next scop would start if the current BB is harmful. */
512 /* The bb or one of its children contains open loop exits. That means
513 loop exit nodes that are not surrounded by a loop dominated by bb. */
516 /* The bb or one of its children contains only structures we can handle. */
520 static struct scopdet_info
build_scops_1 (basic_block
, loop_p
,
521 VEC (sd_region
, heap
) **, loop_p
);
523 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
524 to SCOPS. TYPE is the gbb_type of BB. */
526 static struct scopdet_info
527 scopdet_basic_block_info (basic_block bb
, loop_p outermost_loop
,
528 VEC (sd_region
, heap
) **scops
, gbb_type type
)
530 loop_p loop
= bb
->loop_father
;
531 struct scopdet_info result
;
534 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
535 basic_block entry_block
= ENTRY_BLOCK_PTR
;
536 stmt
= harmful_stmt_in_bb (entry_block
, outermost_loop
, bb
);
537 result
.difficult
= (stmt
!= NULL
);
544 result
.exits
= false;
546 /* Mark bbs terminating a SESE region difficult, if they start
548 if (!single_succ_p (bb
))
549 result
.difficult
= true;
551 result
.exit
= single_succ (bb
);
556 result
.next
= single_succ (bb
);
557 result
.exits
= false;
558 result
.exit
= single_succ (bb
);
561 case GBB_LOOP_SING_EXIT_HEADER
:
563 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
564 struct scopdet_info sinfo
;
565 edge exit_e
= single_exit (loop
);
567 sinfo
= build_scops_1 (bb
, outermost_loop
, ®ions
, loop
);
569 if (!graphite_can_represent_loop (entry_block
, outermost_loop
, loop
))
570 result
.difficult
= true;
572 result
.difficult
|= sinfo
.difficult
;
574 /* Try again with another loop level. */
576 && loop_depth (outermost_loop
) + 1 == loop_depth (loop
))
578 outermost_loop
= loop
;
580 VEC_free (sd_region
, heap
, regions
);
581 regions
= VEC_alloc (sd_region
, heap
, 3);
583 sinfo
= scopdet_basic_block_info (bb
, outermost_loop
, scops
, type
);
586 result
.difficult
= true;
589 move_sd_regions (®ions
, scops
);
593 open_scop
.entry
= bb
;
594 open_scop
.exit
= exit_e
->dest
;
595 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
596 VEC_free (sd_region
, heap
, regions
);
601 result
.exit
= exit_e
->dest
;
602 result
.next
= exit_e
->dest
;
604 /* If we do not dominate result.next, remove it. It's either
605 the EXIT_BLOCK_PTR, or another bb dominates it and will
606 call the scop detection for this bb. */
607 if (!dominated_by_p (CDI_DOMINATORS
, result
.next
, bb
))
610 if (exit_e
->src
->loop_father
!= loop
)
613 result
.exits
= false;
615 if (result
.difficult
)
616 move_sd_regions (®ions
, scops
);
618 VEC_free (sd_region
, heap
, regions
);
624 case GBB_LOOP_MULT_EXIT_HEADER
:
626 /* XXX: For now we just do not join loops with multiple exits. If the
627 exits lead to the same bb it may be possible to join the loop. */
628 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
629 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
632 build_scops_1 (bb
, loop
, ®ions
, loop
);
634 /* Scan the code dominated by this loop. This means all bbs, that are
635 are dominated by a bb in this loop, but are not part of this loop.
638 - The loop exit destination is dominated by the exit sources.
640 TODO: We miss here the more complex cases:
641 - The exit destinations are dominated by another bb inside
643 - The loop dominates bbs, that are not exit destinations. */
644 for (i
= 0; VEC_iterate (edge
, exits
, i
, e
); i
++)
645 if (e
->src
->loop_father
== loop
646 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
))
648 if (loop_outer (outermost_loop
))
649 outermost_loop
= loop_outer (outermost_loop
);
651 /* Pass loop_outer to recognize e->dest as loop header in
653 if (e
->dest
->loop_father
->header
== e
->dest
)
654 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
655 loop_outer (e
->dest
->loop_father
));
657 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
658 e
->dest
->loop_father
);
663 result
.difficult
= true;
664 result
.exits
= false;
665 move_sd_regions (®ions
, scops
);
666 VEC_free (edge
, heap
, exits
);
669 case GBB_COND_HEADER
:
671 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
672 struct scopdet_info sinfo
;
673 VEC (basic_block
, heap
) *dominated
;
676 basic_block last_exit
= NULL
;
678 result
.exits
= false;
680 /* First check the successors of BB, and check if it is
681 possible to join the different branches. */
682 for (i
= 0; VEC_iterate (edge
, bb
->succs
, i
, e
); i
++)
684 /* Ignore loop exits. They will be handled after the loop
686 if (is_loop_exit (loop
, e
->dest
))
692 /* Do not follow edges that lead to the end of the
693 conditions block. For example, in
703 the edge from 0 => 6. Only check if all paths lead to
706 if (!single_pred_p (e
->dest
))
708 /* Check, if edge leads directly to the end of this
713 if (e
->dest
!= last_exit
)
714 result
.difficult
= true;
719 if (!dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
721 result
.difficult
= true;
725 sinfo
= build_scops_1 (e
->dest
, outermost_loop
, ®ions
, loop
);
727 result
.exits
|= sinfo
.exits
;
728 result
.difficult
|= sinfo
.difficult
;
730 /* Checks, if all branches end at the same point.
731 If that is true, the condition stays joinable.
732 Have a look at the example above. */
736 last_exit
= sinfo
.exit
;
738 if (sinfo
.exit
!= last_exit
)
739 result
.difficult
= true;
742 result
.difficult
= true;
746 result
.difficult
= true;
748 /* Join the branches of the condition if possible. */
749 if (!result
.exits
&& !result
.difficult
)
751 /* Only return a next pointer if we dominate this pointer.
752 Otherwise it will be handled by the bb dominating it. */
753 if (dominated_by_p (CDI_DOMINATORS
, last_exit
, bb
)
755 result
.next
= last_exit
;
759 result
.exit
= last_exit
;
761 VEC_free (sd_region
, heap
, regions
);
765 /* Scan remaining bbs dominated by BB. */
766 dominated
= get_dominated_by (CDI_DOMINATORS
, bb
);
768 for (i
= 0; VEC_iterate (basic_block
, dominated
, i
, dom_bb
); i
++)
770 /* Ignore loop exits: they will be handled after the loop body. */
771 if (loop_depth (find_common_loop (loop
, dom_bb
->loop_father
))
778 /* Ignore the bbs processed above. */
779 if (single_pred_p (dom_bb
) && single_pred (dom_bb
) == bb
)
782 if (loop_depth (loop
) > loop_depth (dom_bb
->loop_father
))
783 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
,
786 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
, loop
);
788 result
.exits
|= sinfo
.exits
;
789 result
.difficult
= true;
793 VEC_free (basic_block
, heap
, dominated
);
796 move_sd_regions (®ions
, scops
);
808 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
809 SCOPS. The analyse if a sd_region can be handled is based on the value
810 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
811 is the loop in which CURRENT is handled.
813 TODO: These functions got a little bit big. They definitely should be cleaned
816 static struct scopdet_info
817 build_scops_1 (basic_block current
, loop_p outermost_loop
,
818 VEC (sd_region
, heap
) **scops
, loop_p loop
)
820 bool in_scop
= false;
822 struct scopdet_info sinfo
;
824 /* Initialize result. */
825 struct scopdet_info result
;
826 result
.exits
= false;
827 result
.difficult
= false;
830 open_scop
.entry
= NULL
;
831 open_scop
.exit
= NULL
;
834 /* Loop over the dominance tree. If we meet a difficult bb, close
835 the current SCoP. Loop and condition header start a new layer,
836 and can only be added if all bbs in deeper layers are simple. */
837 while (current
!= NULL
)
839 sinfo
= scopdet_basic_block_info (current
, outermost_loop
, scops
,
840 get_bb_type (current
, loop
));
842 if (!in_scop
&& !(sinfo
.exits
|| sinfo
.difficult
))
844 open_scop
.entry
= current
;
845 open_scop
.exit
= NULL
;
848 else if (in_scop
&& (sinfo
.exits
|| sinfo
.difficult
))
850 open_scop
.exit
= current
;
851 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
855 result
.difficult
|= sinfo
.difficult
;
856 result
.exits
|= sinfo
.exits
;
858 current
= sinfo
.next
;
861 /* Try to close open_scop, if we are still in an open SCoP. */
864 open_scop
.exit
= sinfo
.exit
;
865 gcc_assert (open_scop
.exit
);
866 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
869 result
.exit
= sinfo
.exit
;
873 /* Checks if a bb is contained in REGION. */
876 bb_in_sd_region (basic_block bb
, sd_region
*region
)
878 return bb_in_region (bb
, region
->entry
, region
->exit
);
881 /* Returns the single entry edge of REGION, if it does not exits NULL. */
884 find_single_entry_edge (sd_region
*region
)
890 FOR_EACH_EDGE (e
, ei
, region
->entry
->preds
)
891 if (!bb_in_sd_region (e
->src
, region
))
906 /* Returns the single exit edge of REGION, if it does not exits NULL. */
909 find_single_exit_edge (sd_region
*region
)
915 FOR_EACH_EDGE (e
, ei
, region
->exit
->preds
)
916 if (bb_in_sd_region (e
->src
, region
))
931 /* Create a single entry edge for REGION. */
934 create_single_entry_edge (sd_region
*region
)
936 if (find_single_entry_edge (region
))
939 /* There are multiple predecessors for bb_3
952 There are two edges (1->3, 2->3), that point from outside into the region,
953 and another one (5->3), a loop latch, lead to bb_3.
961 | |\ (3.0 -> 3.1) = single entry edge
970 If the loop is part of the SCoP, we have to redirect the loop latches.
976 | | (3.0 -> 3.1) = entry edge
985 if (region
->entry
->loop_father
->header
!= region
->entry
986 || dominated_by_p (CDI_DOMINATORS
,
987 loop_latch_edge (region
->entry
->loop_father
)->src
,
990 edge forwarder
= split_block_after_labels (region
->entry
);
991 region
->entry
= forwarder
->dest
;
994 /* This case is never executed, as the loop headers seem always to have a
995 single edge pointing from outside into the loop. */
998 #ifdef ENABLE_CHECKING
999 gcc_assert (find_single_entry_edge (region
));
1003 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
1006 sd_region_without_exit (edge e
)
1008 sd_region
*r
= (sd_region
*) e
->aux
;
1011 return r
->exit
== NULL
;
1016 /* Create a single exit edge for REGION. */
1019 create_single_exit_edge (sd_region
*region
)
1023 edge forwarder
= NULL
;
1026 if (find_single_exit_edge (region
))
1029 /* We create a forwarder bb (5) for all edges leaving this region
1030 (3->5, 4->5). All other edges leading to the same bb, are moved
1031 to a new bb (6). If these edges where part of another region (2->5)
1032 we update the region->exit pointer, of this region.
1034 To identify which edge belongs to which region we depend on the e->aux
1035 pointer in every edge. It points to the region of the edge or to NULL,
1036 if the edge is not part of any region.
1038 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
1039 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
1044 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
1045 | | \/ 3->5 no region, 4->5 no region,
1047 \| / 5->6 region->exit = 6
1050 Now there is only a single exit edge (5->6). */
1051 exit
= region
->exit
;
1052 region
->exit
= NULL
;
1053 forwarder
= make_forwarder_block (exit
, &sd_region_without_exit
, NULL
);
1055 /* Unmark the edges, that are no longer exit edges. */
1056 FOR_EACH_EDGE (e
, ei
, forwarder
->src
->preds
)
1060 /* Mark the new exit edge. */
1061 single_succ_edge (forwarder
->src
)->aux
= region
;
1063 /* Update the exit bb of all regions, where exit edges lead to
1065 FOR_EACH_EDGE (e
, ei
, forwarder
->dest
->preds
)
1067 ((sd_region
*) e
->aux
)->exit
= forwarder
->dest
;
1069 #ifdef ENABLE_CHECKING
1070 gcc_assert (find_single_exit_edge (region
));
1074 /* Unmark the exit edges of all REGIONS.
1075 See comment in "create_single_exit_edge". */
1078 unmark_exit_edges (VEC (sd_region
, heap
) *regions
)
1085 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1086 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1091 /* Mark the exit edges of all REGIONS.
1092 See comment in "create_single_exit_edge". */
1095 mark_exit_edges (VEC (sd_region
, heap
) *regions
)
1102 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1103 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1104 if (bb_in_sd_region (e
->src
, s
))
1108 /* Create for all scop regions a single entry and a single exit edge. */
1111 create_sese_edges (VEC (sd_region
, heap
) *regions
)
1116 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1117 create_single_entry_edge (s
);
1119 mark_exit_edges (regions
);
1121 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1122 create_single_exit_edge (s
);
1124 unmark_exit_edges (regions
);
1126 fix_loop_structure (NULL
);
1128 #ifdef ENABLE_CHECKING
1129 verify_loop_structure ();
1130 verify_dominators (CDI_DOMINATORS
);
1135 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1138 build_graphite_scops (VEC (sd_region
, heap
) *regions
,
1139 VEC (scop_p
, heap
) **scops
)
1144 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1146 edge entry
= find_single_entry_edge (s
);
1147 edge exit
= find_single_exit_edge (s
);
1148 scop_p scop
= new_scop (new_sese (entry
, exit
));
1149 VEC_safe_push (scop_p
, heap
, *scops
, scop
);
1151 /* Are there overlapping SCoPs? */
1152 #ifdef ENABLE_CHECKING
1157 for (j
= 0; VEC_iterate (sd_region
, regions
, j
, s2
); j
++)
1159 gcc_assert (!bb_in_sd_region (s
->entry
, s2
));
1165 /* Returns true when BB contains only close phi nodes. */
1168 contains_only_close_phi_nodes (basic_block bb
)
1170 gimple_stmt_iterator gsi
;
1172 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1173 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_LABEL
)
1179 /* Print statistics for SCOP to FILE. */
1182 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
1187 long n_conditions
= 0;
1191 long n_p_conditions
= 0;
1197 gimple_stmt_iterator psi
;
1198 loop_p loop
= bb
->loop_father
;
1200 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
1204 n_p_bbs
+= bb
->count
;
1206 if (VEC_length (edge
, bb
->succs
) > 1)
1209 n_p_conditions
+= bb
->count
;
1212 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1215 n_p_stmts
+= bb
->count
;
1218 if (loop
->header
== bb
&& loop_in_sese_p (loop
, SCOP_REGION (scop
)))
1221 n_p_loops
+= bb
->count
;
1226 fprintf (file
, "\nBefore limit_scops SCoP statistics (");
1227 fprintf (file
, "BBS:%ld, ", n_bbs
);
1228 fprintf (file
, "LOOPS:%ld, ", n_loops
);
1229 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
1230 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
1231 fprintf (file
, "\nBefore limit_scops SCoP profiling statistics (");
1232 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
1233 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
1234 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
1235 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
1238 /* Print statistics for SCOPS to FILE. */
1241 print_graphite_statistics (FILE* file
, VEC (scop_p
, heap
) *scops
)
1246 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
1247 print_graphite_scop_statistics (file
, scop
);
1250 /* Version of free_scops special cased for limit_scops. */
1253 free_scops_1 (VEC (scop_p
, heap
) **scops
)
1258 for (i
= 0; VEC_iterate (scop_p
, *scops
, i
, scop
); i
++)
1260 sese region
= SCOP_REGION (scop
);
1261 free (SESE_PARAMS_NAMES (region
));
1262 SESE_PARAMS_NAMES (region
) = 0;
1265 free_scops (*scops
);
1268 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1278 * SCoP frontier, as this line is not surrounded by any loop. *
1282 This is necessary as scalar evolution and parameter detection need a
1283 outermost loop to initialize parameters correctly.
1285 TODO: FIX scalar evolution and parameter detection to allow more flexible
1289 limit_scops (VEC (scop_p
, heap
) **scops
)
1291 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
1296 for (i
= 0; VEC_iterate (scop_p
, *scops
, i
, scop
); i
++)
1300 sese region
= SCOP_REGION (scop
);
1301 build_scop_bbs (scop
);
1302 build_sese_loop_nests (region
);
1304 for (j
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), j
, loop
); j
++)
1305 if (!loop_in_sese_p (loop_outer (loop
), region
)
1306 && single_exit (loop
))
1308 sd_region open_scop
;
1309 open_scop
.entry
= loop
->header
;
1310 open_scop
.exit
= single_exit (loop
)->dest
;
1312 /* This is a hack on top of the limit_scops hack. The
1313 limit_scops hack should disappear all together. */
1314 if (single_succ_p (open_scop
.exit
)
1315 && contains_only_close_phi_nodes (open_scop
.exit
))
1316 open_scop
.exit
= single_succ_edge (open_scop
.exit
)->dest
;
1318 VEC_safe_push (sd_region
, heap
, regions
, &open_scop
);
1322 free_scops_1 (scops
);
1323 *scops
= VEC_alloc (scop_p
, heap
, 3);
1325 create_sese_edges (regions
);
1326 build_graphite_scops (regions
, scops
);
1327 VEC_free (sd_region
, heap
, regions
);
1330 /* Transforms LOOP to the canonical loop closed SSA form. */
1333 canonicalize_loop_closed_ssa (loop_p loop
)
1335 edge e
= single_exit (loop
);
1338 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
1343 if (VEC_length (edge
, bb
->preds
) == 1)
1344 split_block_after_labels (bb
);
1347 gimple_stmt_iterator psi
;
1348 basic_block close
= split_edge (e
);
1350 e
= single_succ_edge (close
);
1352 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1354 gimple phi
= gsi_stmt (psi
);
1357 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1358 if (gimple_phi_arg_edge (phi
, i
) == e
)
1360 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
1361 use_operand_p use_p
;
1364 if (TREE_CODE (arg
) != SSA_NAME
)
1367 close_phi
= create_phi_node (arg
, close
);
1368 res
= create_new_def_for (gimple_phi_result (close_phi
),
1370 gimple_phi_result_ptr (close_phi
));
1371 add_phi_arg (close_phi
, arg
,
1372 gimple_phi_arg_edge (close_phi
, 0),
1374 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
1375 replace_exp (use_p
, res
);
1382 /* Converts the current loop closed SSA form to a canonical form
1383 expected by the Graphite code generation.
1385 The loop closed SSA form has the following invariant: a variable
1386 defined in a loop that is used outside the loop appears only in the
1387 phi nodes in the destination of the loop exit. These phi nodes are
1388 called close phi nodes.
1390 The canonical loop closed SSA form contains the extra invariants:
1392 - when the loop contains only one exit, the close phi nodes contain
1393 only one argument. That implies that the basic block that contains
1394 the close phi nodes has only one predecessor, that is a basic block
1397 - the basic block containing the close phi nodes does not contain
1402 canonicalize_loop_closed_ssa_form (void)
1407 #ifdef ENABLE_CHECKING
1408 verify_loop_closed_ssa ();
1411 FOR_EACH_LOOP (li
, loop
, 0)
1412 canonicalize_loop_closed_ssa (loop
);
1414 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1415 update_ssa (TODO_update_ssa
);
1417 #ifdef ENABLE_CHECKING
1418 verify_loop_closed_ssa ();
1422 /* Find Static Control Parts (SCoP) in the current function and pushes
1426 build_scops (VEC (scop_p
, heap
) **scops
)
1428 struct loop
*loop
= current_loops
->tree_root
;
1429 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
1431 canonicalize_loop_closed_ssa_form ();
1432 build_scops_1 (single_succ (ENTRY_BLOCK_PTR
), ENTRY_BLOCK_PTR
->loop_father
,
1434 create_sese_edges (regions
);
1435 build_graphite_scops (regions
, scops
);
1437 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1438 print_graphite_statistics (dump_file
, *scops
);
1440 limit_scops (scops
);
1441 VEC_free (sd_region
, heap
, regions
);
1443 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1444 fprintf (dump_file
, "\nnumber of SCoPs: %d\n",
1445 VEC_length (scop_p
, *scops
));
1448 /* Pretty print all SCoPs in DOT format and mark them with different colors.
1449 If there are not enough colors, paint later SCoPs gray.
1451 - "*" after the node number: entry of a SCoP,
1452 - "#" after the node number: exit of a SCoP,
1453 - "()" entry or exit not part of SCoP. */
1456 dot_all_scops_1 (FILE *file
, VEC (scop_p
, heap
) *scops
)
1465 /* Disable debugging while printing graph. */
1466 int tmp_dump_flags
= dump_flags
;
1469 fprintf (file
, "digraph all {\n");
1473 int part_of_scop
= false;
1475 /* Use HTML for every bb label. So we are able to print bbs
1476 which are part of two different SCoPs, with two different
1477 background colors. */
1478 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1480 fprintf (file
, "CELLSPACING=\"0\">\n");
1482 /* Select color for SCoP. */
1483 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
1485 sese region
= SCOP_REGION (scop
);
1486 if (bb_in_sese_p (bb
, region
)
1487 || (SESE_EXIT_BB (region
) == bb
)
1488 || (SESE_ENTRY_BB (region
) == bb
))
1501 case 3: /* purple */
1504 case 4: /* orange */
1507 case 5: /* yellow */
1547 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color
);
1549 if (!bb_in_sese_p (bb
, region
))
1550 fprintf (file
, " (");
1552 if (bb
== SESE_ENTRY_BB (region
)
1553 && bb
== SESE_EXIT_BB (region
))
1554 fprintf (file
, " %d*# ", bb
->index
);
1555 else if (bb
== SESE_ENTRY_BB (region
))
1556 fprintf (file
, " %d* ", bb
->index
);
1557 else if (bb
== SESE_EXIT_BB (region
))
1558 fprintf (file
, " %d# ", bb
->index
);
1560 fprintf (file
, " %d ", bb
->index
);
1562 if (!bb_in_sese_p (bb
,region
))
1563 fprintf (file
, ")");
1565 fprintf (file
, "</TD></TR>\n");
1566 part_of_scop
= true;
1572 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1573 fprintf (file
, " %d </TD></TR>\n", bb
->index
);
1575 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1580 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1581 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
1584 fputs ("}\n\n", file
);
1586 /* Enable debugging again. */
1587 dump_flags
= tmp_dump_flags
;
1590 /* Display all SCoPs using dotty. */
1593 dot_all_scops (VEC (scop_p
, heap
) *scops
)
1595 /* When debugging, enable the following code. This cannot be used
1596 in production compilers because it calls "system". */
1599 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1600 gcc_assert (stream
);
1602 dot_all_scops_1 (stream
, scops
);
1605 x
= system ("dotty /tmp/allscops.dot");
1607 dot_all_scops_1 (stderr
, scops
);
1611 /* Display all SCoPs using dotty. */
1614 dot_scop (scop_p scop
)
1616 VEC (scop_p
, heap
) *scops
= NULL
;
1619 VEC_safe_push (scop_p
, heap
, scops
, scop
);
1621 /* When debugging, enable the following code. This cannot be used
1622 in production compilers because it calls "system". */
1626 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1627 gcc_assert (stream
);
1629 dot_all_scops_1 (stream
, scops
);
1631 x
= system ("dotty /tmp/allscops.dot");
1634 dot_all_scops_1 (stderr
, scops
);
1637 VEC_free (scop_p
, heap
, scops
);