1 /* Detection of Static Control Parts (SCoP) for Graphite.
2 Copyright (C) 2009, 2010 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"
25 #include "tree-flow.h"
27 #include "tree-chrec.h"
28 #include "tree-data-ref.h"
29 #include "tree-scalar-evolution.h"
30 #include "tree-pass.h"
35 #include "graphite-ppl.h"
36 #include "graphite-poly.h"
37 #include "graphite-scop-detection.h"
39 /* The type of the analyzed basic block. */
41 typedef enum gbb_type
{
43 GBB_LOOP_SING_EXIT_HEADER
,
44 GBB_LOOP_MULT_EXIT_HEADER
,
51 /* Detect the type of BB. Loop headers are only marked, if they are
52 new. This means their loop_father is different to LAST_LOOP.
53 Otherwise they are treated like any other bb and their type can be
57 get_bb_type (basic_block bb
, struct loop
*last_loop
)
59 VEC (basic_block
, heap
) *dom
;
61 struct loop
*loop
= bb
->loop_father
;
63 /* Check, if we entry into a new loop. */
64 if (loop
!= last_loop
)
66 if (single_exit (loop
) != NULL
)
67 return GBB_LOOP_SING_EXIT_HEADER
;
68 else if (loop
->num
!= 0)
69 return GBB_LOOP_MULT_EXIT_HEADER
;
71 return GBB_COND_HEADER
;
74 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
75 nb_dom
= VEC_length (basic_block
, dom
);
76 VEC_free (basic_block
, heap
, dom
);
81 nb_suc
= VEC_length (edge
, bb
->succs
);
83 if (nb_dom
== 1 && nb_suc
== 1)
86 return GBB_COND_HEADER
;
89 /* A SCoP detection region, defined using bbs as borders.
91 All control flow touching this region, comes in passing basic_block
92 ENTRY and leaves passing basic_block EXIT. By using bbs instead of
93 edges for the borders we are able to represent also regions that do
94 not have a single entry or exit edge.
96 But as they have a single entry basic_block and a single exit
97 basic_block, we are able to generate for every sd_region a single
105 / \ This region contains: {3, 4, 5, 6, 7, 8}
113 typedef struct sd_region_p
115 /* The entry bb dominates all bbs in the sd_region. It is part of
119 /* The exit bb postdominates all bbs in the sd_region, but is not
120 part of the region. */
124 DEF_VEC_O(sd_region
);
125 DEF_VEC_ALLOC_O(sd_region
, heap
);
128 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
131 move_sd_regions (VEC (sd_region
, heap
) **source
,
132 VEC (sd_region
, heap
) **target
)
137 FOR_EACH_VEC_ELT (sd_region
, *source
, i
, s
)
138 VEC_safe_push (sd_region
, heap
, *target
, s
);
140 VEC_free (sd_region
, heap
, *source
);
143 /* Something like "n * m" is not allowed. */
146 graphite_can_represent_init (tree e
)
148 switch (TREE_CODE (e
))
150 case POLYNOMIAL_CHREC
:
151 return graphite_can_represent_init (CHREC_LEFT (e
))
152 && graphite_can_represent_init (CHREC_RIGHT (e
));
155 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
156 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
157 && host_integerp (TREE_OPERAND (e
, 1), 0);
159 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
160 && host_integerp (TREE_OPERAND (e
, 0), 0);
163 case POINTER_PLUS_EXPR
:
165 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
166 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
171 case NON_LVALUE_EXPR
:
172 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
181 /* Return true when SCEV can be represented in the polyhedral model.
183 An expression can be represented, if it can be expressed as an
184 affine expression. For loops (i, j) and parameters (m, n) all
185 affine expressions are of the form:
187 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
189 1 i + 20 j + (-2) m + 25
191 Something like "i * n" or "n * m" is not allowed. */
194 graphite_can_represent_scev (tree scev
)
196 if (chrec_contains_undetermined (scev
))
199 switch (TREE_CODE (scev
))
203 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
204 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
207 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
208 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
209 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
210 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
211 && graphite_can_represent_init (scev
)
212 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
213 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
215 case POLYNOMIAL_CHREC
:
216 /* Check for constant strides. With a non constant stride of
217 'n' we would have a value of 'iv * n'. Also check that the
218 initial value can represented: for example 'n * m' cannot be
220 if (!evolution_function_right_is_integer_cst (scev
)
221 || !graphite_can_represent_init (scev
))
228 /* Only affine functions can be represented. */
229 if (!scev_is_linear_expression (scev
))
236 /* Return true when EXPR can be represented in the polyhedral model.
238 This means an expression can be represented, if it is linear with
239 respect to the loops and the strides are non parametric.
240 LOOP is the place where the expr will be evaluated. SCOP_ENTRY defines the
241 entry of the region we analyse. */
244 graphite_can_represent_expr (basic_block scop_entry
, loop_p loop
,
247 tree scev
= analyze_scalar_evolution (loop
, expr
);
249 scev
= instantiate_scev (scop_entry
, loop
, scev
);
251 return graphite_can_represent_scev (scev
);
254 /* Return true if the data references of STMT can be represented by
258 stmt_has_simple_data_refs_p (loop_p outermost_loop
, gimple stmt
)
264 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 5);
266 graphite_find_data_references_in_stmt (outermost_loop
,
267 loop_containing_stmt (stmt
),
270 FOR_EACH_VEC_ELT (data_reference_p
, drs
, j
, dr
)
271 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
272 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
)))
279 free_data_refs (drs
);
283 /* Return true only when STMT is simple enough for being handled by
284 Graphite. This depends on SCOP_ENTRY, as the parameters are
285 initialized relatively to this basic block, the linear functions
286 are initialized to OUTERMOST_LOOP and BB is the place where we try
287 to evaluate the STMT. */
290 stmt_simple_for_scop_p (basic_block scop_entry
, loop_p outermost_loop
,
291 gimple stmt
, basic_block bb
)
293 loop_p loop
= bb
->loop_father
;
295 gcc_assert (scop_entry
);
297 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
298 Calls have side-effects, except those to const or pure
300 if (gimple_has_volatile_ops (stmt
)
301 || (gimple_code (stmt
) == GIMPLE_CALL
302 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
303 || (gimple_code (stmt
) == GIMPLE_ASM
))
306 if (is_gimple_debug (stmt
))
309 if (!stmt_has_simple_data_refs_p (outermost_loop
, stmt
))
312 switch (gimple_code (stmt
))
322 enum tree_code code
= gimple_cond_code (stmt
);
324 /* We can handle all binary comparisons. Inequalities are
325 also supported as they can be represented with union of
327 if (!(code
== LT_EXPR
335 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, op_iter
, SSA_OP_ALL_USES
)
336 if (!graphite_can_represent_expr (scop_entry
, loop
, op
)
337 /* We can not handle REAL_TYPE. Failed for pr39260. */
338 || TREE_CODE (TREE_TYPE (op
)) == REAL_TYPE
)
349 /* These nodes cut a new scope. */
356 /* Returns the statement of BB that contains a harmful operation: that
357 can be a function call with side effects, the induction variables
358 are not linear with respect to SCOP_ENTRY, etc. The current open
359 scop should end before this statement. The evaluation is limited using
360 OUTERMOST_LOOP as outermost loop that may change. */
363 harmful_stmt_in_bb (basic_block scop_entry
, loop_p outer_loop
, basic_block bb
)
365 gimple_stmt_iterator gsi
;
367 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
368 if (!stmt_simple_for_scop_p (scop_entry
, outer_loop
, gsi_stmt (gsi
), bb
))
369 return gsi_stmt (gsi
);
374 /* Return true if LOOP can be represented in the polyhedral
375 representation. This is evaluated taking SCOP_ENTRY and
376 OUTERMOST_LOOP in mind. */
379 graphite_can_represent_loop (basic_block scop_entry
, loop_p loop
)
381 tree niter
= number_of_latch_executions (loop
);
383 /* Number of iterations unknown. */
384 if (chrec_contains_undetermined (niter
))
387 /* Number of iterations not affine. */
388 if (!graphite_can_represent_expr (scop_entry
, loop
, niter
))
394 /* Store information needed by scopdet_* functions. */
398 /* Exit of the open scop would stop if the current BB is harmful. */
401 /* Where the next scop would start if the current BB is harmful. */
404 /* The bb or one of its children contains open loop exits. That means
405 loop exit nodes that are not surrounded by a loop dominated by bb. */
408 /* The bb or one of its children contains only structures we can handle. */
412 static struct scopdet_info
build_scops_1 (basic_block
, loop_p
,
413 VEC (sd_region
, heap
) **, loop_p
);
415 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
416 to SCOPS. TYPE is the gbb_type of BB. */
418 static struct scopdet_info
419 scopdet_basic_block_info (basic_block bb
, loop_p outermost_loop
,
420 VEC (sd_region
, heap
) **scops
, gbb_type type
)
422 loop_p loop
= bb
->loop_father
;
423 struct scopdet_info result
;
426 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
427 basic_block entry_block
= ENTRY_BLOCK_PTR
;
428 stmt
= harmful_stmt_in_bb (entry_block
, outermost_loop
, bb
);
429 result
.difficult
= (stmt
!= NULL
);
436 result
.exits
= false;
438 /* Mark bbs terminating a SESE region difficult, if they start
440 if (!single_succ_p (bb
))
441 result
.difficult
= true;
443 result
.exit
= single_succ (bb
);
448 result
.next
= single_succ (bb
);
449 result
.exits
= false;
450 result
.exit
= single_succ (bb
);
453 case GBB_LOOP_SING_EXIT_HEADER
:
455 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
456 struct scopdet_info sinfo
;
457 edge exit_e
= single_exit (loop
);
459 sinfo
= build_scops_1 (bb
, outermost_loop
, ®ions
, loop
);
461 if (!graphite_can_represent_loop (entry_block
, loop
))
462 result
.difficult
= true;
464 result
.difficult
|= sinfo
.difficult
;
466 /* Try again with another loop level. */
468 && loop_depth (outermost_loop
) + 1 == loop_depth (loop
))
470 outermost_loop
= loop
;
472 VEC_free (sd_region
, heap
, regions
);
473 regions
= VEC_alloc (sd_region
, heap
, 3);
475 sinfo
= scopdet_basic_block_info (bb
, outermost_loop
, scops
, type
);
478 result
.difficult
= true;
481 move_sd_regions (®ions
, scops
);
485 open_scop
.entry
= bb
;
486 open_scop
.exit
= exit_e
->dest
;
487 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
488 VEC_free (sd_region
, heap
, regions
);
493 result
.exit
= exit_e
->dest
;
494 result
.next
= exit_e
->dest
;
496 /* If we do not dominate result.next, remove it. It's either
497 the EXIT_BLOCK_PTR, or another bb dominates it and will
498 call the scop detection for this bb. */
499 if (!dominated_by_p (CDI_DOMINATORS
, result
.next
, bb
))
502 if (exit_e
->src
->loop_father
!= loop
)
505 result
.exits
= false;
507 if (result
.difficult
)
508 move_sd_regions (®ions
, scops
);
510 VEC_free (sd_region
, heap
, regions
);
516 case GBB_LOOP_MULT_EXIT_HEADER
:
518 /* XXX: For now we just do not join loops with multiple exits. If the
519 exits lead to the same bb it may be possible to join the loop. */
520 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
521 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
524 build_scops_1 (bb
, loop
, ®ions
, loop
);
526 /* Scan the code dominated by this loop. This means all bbs, that are
527 are dominated by a bb in this loop, but are not part of this loop.
530 - The loop exit destination is dominated by the exit sources.
532 TODO: We miss here the more complex cases:
533 - The exit destinations are dominated by another bb inside
535 - The loop dominates bbs, that are not exit destinations. */
536 FOR_EACH_VEC_ELT (edge
, exits
, i
, e
)
537 if (e
->src
->loop_father
== loop
538 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
))
540 if (loop_outer (outermost_loop
))
541 outermost_loop
= loop_outer (outermost_loop
);
543 /* Pass loop_outer to recognize e->dest as loop header in
545 if (e
->dest
->loop_father
->header
== e
->dest
)
546 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
547 loop_outer (e
->dest
->loop_father
));
549 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
550 e
->dest
->loop_father
);
555 result
.difficult
= true;
556 result
.exits
= false;
557 move_sd_regions (®ions
, scops
);
558 VEC_free (edge
, heap
, exits
);
561 case GBB_COND_HEADER
:
563 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
564 struct scopdet_info sinfo
;
565 VEC (basic_block
, heap
) *dominated
;
568 basic_block last_exit
= NULL
;
570 result
.exits
= false;
572 /* First check the successors of BB, and check if it is
573 possible to join the different branches. */
574 FOR_EACH_VEC_ELT (edge
, bb
->succs
, i
, e
)
576 /* Ignore loop exits. They will be handled after the loop
578 if (loop_exits_to_bb_p (loop
, e
->dest
))
584 /* Do not follow edges that lead to the end of the
585 conditions block. For example, in
595 the edge from 0 => 6. Only check if all paths lead to
598 if (!single_pred_p (e
->dest
))
600 /* Check, if edge leads directly to the end of this
605 if (e
->dest
!= last_exit
)
606 result
.difficult
= true;
611 if (!dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
613 result
.difficult
= true;
617 sinfo
= build_scops_1 (e
->dest
, outermost_loop
, ®ions
, loop
);
619 result
.exits
|= sinfo
.exits
;
620 result
.difficult
|= sinfo
.difficult
;
622 /* Checks, if all branches end at the same point.
623 If that is true, the condition stays joinable.
624 Have a look at the example above. */
628 last_exit
= sinfo
.exit
;
630 if (sinfo
.exit
!= last_exit
)
631 result
.difficult
= true;
634 result
.difficult
= true;
638 result
.difficult
= true;
640 /* Join the branches of the condition if possible. */
641 if (!result
.exits
&& !result
.difficult
)
643 /* Only return a next pointer if we dominate this pointer.
644 Otherwise it will be handled by the bb dominating it. */
645 if (dominated_by_p (CDI_DOMINATORS
, last_exit
, bb
)
647 result
.next
= last_exit
;
651 result
.exit
= last_exit
;
653 VEC_free (sd_region
, heap
, regions
);
657 /* Scan remaining bbs dominated by BB. */
658 dominated
= get_dominated_by (CDI_DOMINATORS
, bb
);
660 FOR_EACH_VEC_ELT (basic_block
, dominated
, i
, dom_bb
)
662 /* Ignore loop exits: they will be handled after the loop body. */
663 if (loop_depth (find_common_loop (loop
, dom_bb
->loop_father
))
670 /* Ignore the bbs processed above. */
671 if (single_pred_p (dom_bb
) && single_pred (dom_bb
) == bb
)
674 if (loop_depth (loop
) > loop_depth (dom_bb
->loop_father
))
675 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
,
678 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
, loop
);
680 result
.exits
|= sinfo
.exits
;
681 result
.difficult
= true;
685 VEC_free (basic_block
, heap
, dominated
);
688 move_sd_regions (®ions
, scops
);
700 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
701 SCOPS. The analyse if a sd_region can be handled is based on the value
702 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
703 is the loop in which CURRENT is handled.
705 TODO: These functions got a little bit big. They definitely should be cleaned
708 static struct scopdet_info
709 build_scops_1 (basic_block current
, loop_p outermost_loop
,
710 VEC (sd_region
, heap
) **scops
, loop_p loop
)
712 bool in_scop
= false;
714 struct scopdet_info sinfo
;
716 /* Initialize result. */
717 struct scopdet_info result
;
718 result
.exits
= false;
719 result
.difficult
= false;
722 open_scop
.entry
= NULL
;
723 open_scop
.exit
= NULL
;
726 /* Loop over the dominance tree. If we meet a difficult bb, close
727 the current SCoP. Loop and condition header start a new layer,
728 and can only be added if all bbs in deeper layers are simple. */
729 while (current
!= NULL
)
731 sinfo
= scopdet_basic_block_info (current
, outermost_loop
, scops
,
732 get_bb_type (current
, loop
));
734 if (!in_scop
&& !(sinfo
.exits
|| sinfo
.difficult
))
736 open_scop
.entry
= current
;
737 open_scop
.exit
= NULL
;
740 else if (in_scop
&& (sinfo
.exits
|| sinfo
.difficult
))
742 open_scop
.exit
= current
;
743 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
747 result
.difficult
|= sinfo
.difficult
;
748 result
.exits
|= sinfo
.exits
;
750 current
= sinfo
.next
;
753 /* Try to close open_scop, if we are still in an open SCoP. */
756 open_scop
.exit
= sinfo
.exit
;
757 gcc_assert (open_scop
.exit
);
758 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
761 result
.exit
= sinfo
.exit
;
765 /* Checks if a bb is contained in REGION. */
768 bb_in_sd_region (basic_block bb
, sd_region
*region
)
770 return bb_in_region (bb
, region
->entry
, region
->exit
);
773 /* Returns the single entry edge of REGION, if it does not exits NULL. */
776 find_single_entry_edge (sd_region
*region
)
782 FOR_EACH_EDGE (e
, ei
, region
->entry
->preds
)
783 if (!bb_in_sd_region (e
->src
, region
))
798 /* Returns the single exit edge of REGION, if it does not exits NULL. */
801 find_single_exit_edge (sd_region
*region
)
807 FOR_EACH_EDGE (e
, ei
, region
->exit
->preds
)
808 if (bb_in_sd_region (e
->src
, region
))
823 /* Create a single entry edge for REGION. */
826 create_single_entry_edge (sd_region
*region
)
828 if (find_single_entry_edge (region
))
831 /* There are multiple predecessors for bb_3
844 There are two edges (1->3, 2->3), that point from outside into the region,
845 and another one (5->3), a loop latch, lead to bb_3.
853 | |\ (3.0 -> 3.1) = single entry edge
862 If the loop is part of the SCoP, we have to redirect the loop latches.
868 | | (3.0 -> 3.1) = entry edge
877 if (region
->entry
->loop_father
->header
!= region
->entry
878 || dominated_by_p (CDI_DOMINATORS
,
879 loop_latch_edge (region
->entry
->loop_father
)->src
,
882 edge forwarder
= split_block_after_labels (region
->entry
);
883 region
->entry
= forwarder
->dest
;
886 /* This case is never executed, as the loop headers seem always to have a
887 single edge pointing from outside into the loop. */
890 gcc_checking_assert (find_single_entry_edge (region
));
893 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
896 sd_region_without_exit (edge e
)
898 sd_region
*r
= (sd_region
*) e
->aux
;
901 return r
->exit
== NULL
;
906 /* Create a single exit edge for REGION. */
909 create_single_exit_edge (sd_region
*region
)
913 edge forwarder
= NULL
;
916 /* We create a forwarder bb (5) for all edges leaving this region
917 (3->5, 4->5). All other edges leading to the same bb, are moved
918 to a new bb (6). If these edges where part of another region (2->5)
919 we update the region->exit pointer, of this region.
921 To identify which edge belongs to which region we depend on the e->aux
922 pointer in every edge. It points to the region of the edge or to NULL,
923 if the edge is not part of any region.
925 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
926 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
931 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
932 | | \/ 3->5 no region, 4->5 no region,
934 \| / 5->6 region->exit = 6
937 Now there is only a single exit edge (5->6). */
940 forwarder
= make_forwarder_block (exit
, &sd_region_without_exit
, NULL
);
942 /* Unmark the edges, that are no longer exit edges. */
943 FOR_EACH_EDGE (e
, ei
, forwarder
->src
->preds
)
947 /* Mark the new exit edge. */
948 single_succ_edge (forwarder
->src
)->aux
= region
;
950 /* Update the exit bb of all regions, where exit edges lead to
952 FOR_EACH_EDGE (e
, ei
, forwarder
->dest
->preds
)
954 ((sd_region
*) e
->aux
)->exit
= forwarder
->dest
;
956 gcc_checking_assert (find_single_exit_edge (region
));
959 /* Unmark the exit edges of all REGIONS.
960 See comment in "create_single_exit_edge". */
963 unmark_exit_edges (VEC (sd_region
, heap
) *regions
)
970 FOR_EACH_VEC_ELT (sd_region
, regions
, i
, s
)
971 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
976 /* Mark the exit edges of all REGIONS.
977 See comment in "create_single_exit_edge". */
980 mark_exit_edges (VEC (sd_region
, heap
) *regions
)
987 FOR_EACH_VEC_ELT (sd_region
, regions
, i
, s
)
988 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
989 if (bb_in_sd_region (e
->src
, s
))
993 /* Create for all scop regions a single entry and a single exit edge. */
996 create_sese_edges (VEC (sd_region
, heap
) *regions
)
1001 FOR_EACH_VEC_ELT (sd_region
, regions
, i
, s
)
1002 create_single_entry_edge (s
);
1004 mark_exit_edges (regions
);
1006 FOR_EACH_VEC_ELT (sd_region
, regions
, i
, s
)
1007 /* Don't handle multiple edges exiting the function. */
1008 if (!find_single_exit_edge (s
)
1009 && s
->exit
!= EXIT_BLOCK_PTR
)
1010 create_single_exit_edge (s
);
1012 unmark_exit_edges (regions
);
1014 fix_loop_structure (NULL
);
1016 #ifdef ENABLE_CHECKING
1017 verify_loop_structure ();
1018 verify_dominators (CDI_DOMINATORS
);
1023 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1026 build_graphite_scops (VEC (sd_region
, heap
) *regions
,
1027 VEC (scop_p
, heap
) **scops
)
1032 FOR_EACH_VEC_ELT (sd_region
, regions
, i
, s
)
1034 edge entry
= find_single_entry_edge (s
);
1035 edge exit
= find_single_exit_edge (s
);
1041 scop
= new_scop (new_sese (entry
, exit
));
1042 VEC_safe_push (scop_p
, heap
, *scops
, scop
);
1044 /* Are there overlapping SCoPs? */
1045 #ifdef ENABLE_CHECKING
1050 FOR_EACH_VEC_ELT (sd_region
, regions
, j
, s2
)
1052 gcc_assert (!bb_in_sd_region (s
->entry
, s2
));
1058 /* Returns true when BB contains only close phi nodes. */
1061 contains_only_close_phi_nodes (basic_block bb
)
1063 gimple_stmt_iterator gsi
;
1065 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1066 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_LABEL
)
1072 /* Print statistics for SCOP to FILE. */
1075 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
1080 long n_conditions
= 0;
1084 long n_p_conditions
= 0;
1090 gimple_stmt_iterator psi
;
1091 loop_p loop
= bb
->loop_father
;
1093 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
1097 n_p_bbs
+= bb
->count
;
1099 if (VEC_length (edge
, bb
->succs
) > 1)
1102 n_p_conditions
+= bb
->count
;
1105 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1108 n_p_stmts
+= bb
->count
;
1111 if (loop
->header
== bb
&& loop_in_sese_p (loop
, SCOP_REGION (scop
)))
1114 n_p_loops
+= bb
->count
;
1119 fprintf (file
, "\nBefore limit_scops SCoP statistics (");
1120 fprintf (file
, "BBS:%ld, ", n_bbs
);
1121 fprintf (file
, "LOOPS:%ld, ", n_loops
);
1122 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
1123 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
1124 fprintf (file
, "\nBefore limit_scops SCoP profiling statistics (");
1125 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
1126 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
1127 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
1128 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
1131 /* Print statistics for SCOPS to FILE. */
1134 print_graphite_statistics (FILE* file
, VEC (scop_p
, heap
) *scops
)
1139 FOR_EACH_VEC_ELT (scop_p
, scops
, i
, scop
)
1140 print_graphite_scop_statistics (file
, scop
);
1143 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1153 * SCoP frontier, as this line is not surrounded by any loop. *
1157 This is necessary as scalar evolution and parameter detection need a
1158 outermost loop to initialize parameters correctly.
1160 TODO: FIX scalar evolution and parameter detection to allow more flexible
1164 limit_scops (VEC (scop_p
, heap
) **scops
)
1166 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
1171 FOR_EACH_VEC_ELT (scop_p
, *scops
, i
, scop
)
1175 sese region
= SCOP_REGION (scop
);
1176 build_sese_loop_nests (region
);
1178 FOR_EACH_VEC_ELT (loop_p
, SESE_LOOP_NEST (region
), j
, loop
)
1179 if (!loop_in_sese_p (loop_outer (loop
), region
)
1180 && single_exit (loop
))
1182 sd_region open_scop
;
1183 open_scop
.entry
= loop
->header
;
1184 open_scop
.exit
= single_exit (loop
)->dest
;
1186 /* This is a hack on top of the limit_scops hack. The
1187 limit_scops hack should disappear all together. */
1188 if (single_succ_p (open_scop
.exit
)
1189 && contains_only_close_phi_nodes (open_scop
.exit
))
1190 open_scop
.exit
= single_succ_edge (open_scop
.exit
)->dest
;
1192 VEC_safe_push (sd_region
, heap
, regions
, &open_scop
);
1196 free_scops (*scops
);
1197 *scops
= VEC_alloc (scop_p
, heap
, 3);
1199 create_sese_edges (regions
);
1200 build_graphite_scops (regions
, scops
);
1201 VEC_free (sd_region
, heap
, regions
);
1204 /* Returns true when P1 and P2 are close phis with the same
1208 same_close_phi_node (gimple p1
, gimple p2
)
1210 return operand_equal_p (gimple_phi_arg_def (p1
, 0),
1211 gimple_phi_arg_def (p2
, 0), 0);
1214 /* Remove the close phi node at GSI and replace its rhs with the rhs
1218 remove_duplicate_close_phi (gimple phi
, gimple_stmt_iterator
*gsi
)
1221 use_operand_p use_p
;
1222 imm_use_iterator imm_iter
;
1223 tree res
= gimple_phi_result (phi
);
1224 tree def
= gimple_phi_result (gsi_stmt (*gsi
));
1226 gcc_assert (same_close_phi_node (phi
, gsi_stmt (*gsi
)));
1228 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1230 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1231 SET_USE (use_p
, res
);
1233 update_stmt (use_stmt
);
1236 remove_phi_node (gsi
, true);
1239 /* Removes all the close phi duplicates from BB. */
1242 make_close_phi_nodes_unique (basic_block bb
)
1244 gimple_stmt_iterator psi
;
1246 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1248 gimple_stmt_iterator gsi
= psi
;
1249 gimple phi
= gsi_stmt (psi
);
1251 /* At this point, PHI should be a close phi in normal form. */
1252 gcc_assert (gimple_phi_num_args (phi
) == 1);
1254 /* Iterate over the next phis and remove duplicates. */
1256 while (!gsi_end_p (gsi
))
1257 if (same_close_phi_node (phi
, gsi_stmt (gsi
)))
1258 remove_duplicate_close_phi (phi
, &gsi
);
1264 /* Transforms LOOP to the canonical loop closed SSA form. */
1267 canonicalize_loop_closed_ssa (loop_p loop
)
1269 edge e
= single_exit (loop
);
1272 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
1277 if (VEC_length (edge
, bb
->preds
) == 1)
1279 e
= split_block_after_labels (bb
);
1280 make_close_phi_nodes_unique (e
->src
);
1284 gimple_stmt_iterator psi
;
1285 basic_block close
= split_edge (e
);
1287 e
= single_succ_edge (close
);
1289 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1291 gimple phi
= gsi_stmt (psi
);
1294 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1295 if (gimple_phi_arg_edge (phi
, i
) == e
)
1297 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
1298 use_operand_p use_p
;
1301 if (TREE_CODE (arg
) != SSA_NAME
)
1304 close_phi
= create_phi_node (arg
, close
);
1305 res
= create_new_def_for (gimple_phi_result (close_phi
),
1307 gimple_phi_result_ptr (close_phi
));
1308 add_phi_arg (close_phi
, arg
,
1309 gimple_phi_arg_edge (close_phi
, 0),
1311 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
1312 replace_exp (use_p
, res
);
1317 make_close_phi_nodes_unique (close
);
1320 /* The code above does not properly handle changes in the post dominance
1321 information (yet). */
1322 free_dominance_info (CDI_POST_DOMINATORS
);
1325 /* Converts the current loop closed SSA form to a canonical form
1326 expected by the Graphite code generation.
1328 The loop closed SSA form has the following invariant: a variable
1329 defined in a loop that is used outside the loop appears only in the
1330 phi nodes in the destination of the loop exit. These phi nodes are
1331 called close phi nodes.
1333 The canonical loop closed SSA form contains the extra invariants:
1335 - when the loop contains only one exit, the close phi nodes contain
1336 only one argument. That implies that the basic block that contains
1337 the close phi nodes has only one predecessor, that is a basic block
1340 - the basic block containing the close phi nodes does not contain
1343 - there exist only one phi node per definition in the loop.
1347 canonicalize_loop_closed_ssa_form (void)
1352 #ifdef ENABLE_CHECKING
1353 verify_loop_closed_ssa (true);
1356 FOR_EACH_LOOP (li
, loop
, 0)
1357 canonicalize_loop_closed_ssa (loop
);
1359 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1360 update_ssa (TODO_update_ssa
);
1362 #ifdef ENABLE_CHECKING
1363 verify_loop_closed_ssa (true);
1367 /* Find Static Control Parts (SCoP) in the current function and pushes
1371 build_scops (VEC (scop_p
, heap
) **scops
)
1373 struct loop
*loop
= current_loops
->tree_root
;
1374 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
1376 canonicalize_loop_closed_ssa_form ();
1377 build_scops_1 (single_succ (ENTRY_BLOCK_PTR
), ENTRY_BLOCK_PTR
->loop_father
,
1379 create_sese_edges (regions
);
1380 build_graphite_scops (regions
, scops
);
1382 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1383 print_graphite_statistics (dump_file
, *scops
);
1385 limit_scops (scops
);
1386 VEC_free (sd_region
, heap
, regions
);
1388 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1389 fprintf (dump_file
, "\nnumber of SCoPs: %d\n",
1390 VEC_length (scop_p
, *scops
));
1393 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1394 different colors. If there are not enough colors, paint the
1395 remaining SCoPs in gray.
1398 - "*" after the node number denotes the entry of a SCoP,
1399 - "#" after the node number denotes the exit of a SCoP,
1400 - "()" around the node number denotes the entry or the
1401 exit nodes of the SCOP. These are not part of SCoP. */
1404 dot_all_scops_1 (FILE *file
, VEC (scop_p
, heap
) *scops
)
1413 /* Disable debugging while printing graph. */
1414 int tmp_dump_flags
= dump_flags
;
1417 fprintf (file
, "digraph all {\n");
1421 int part_of_scop
= false;
1423 /* Use HTML for every bb label. So we are able to print bbs
1424 which are part of two different SCoPs, with two different
1425 background colors. */
1426 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1428 fprintf (file
, "CELLSPACING=\"0\">\n");
1430 /* Select color for SCoP. */
1431 FOR_EACH_VEC_ELT (scop_p
, scops
, i
, scop
)
1433 sese region
= SCOP_REGION (scop
);
1434 if (bb_in_sese_p (bb
, region
)
1435 || (SESE_EXIT_BB (region
) == bb
)
1436 || (SESE_ENTRY_BB (region
) == bb
))
1449 case 3: /* purple */
1452 case 4: /* orange */
1455 case 5: /* yellow */
1495 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color
);
1497 if (!bb_in_sese_p (bb
, region
))
1498 fprintf (file
, " (");
1500 if (bb
== SESE_ENTRY_BB (region
)
1501 && bb
== SESE_EXIT_BB (region
))
1502 fprintf (file
, " %d*# ", bb
->index
);
1503 else if (bb
== SESE_ENTRY_BB (region
))
1504 fprintf (file
, " %d* ", bb
->index
);
1505 else if (bb
== SESE_EXIT_BB (region
))
1506 fprintf (file
, " %d# ", bb
->index
);
1508 fprintf (file
, " %d ", bb
->index
);
1510 if (!bb_in_sese_p (bb
,region
))
1511 fprintf (file
, ")");
1513 fprintf (file
, "</TD></TR>\n");
1514 part_of_scop
= true;
1520 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1521 fprintf (file
, " %d </TD></TR>\n", bb
->index
);
1523 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1528 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1529 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
1532 fputs ("}\n\n", file
);
1534 /* Enable debugging again. */
1535 dump_flags
= tmp_dump_flags
;
1538 /* Display all SCoPs using dotty. */
1541 dot_all_scops (VEC (scop_p
, heap
) *scops
)
1543 /* When debugging, enable the following code. This cannot be used
1544 in production compilers because it calls "system". */
1547 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1548 gcc_assert (stream
);
1550 dot_all_scops_1 (stream
, scops
);
1553 x
= system ("dotty /tmp/allscops.dot &");
1555 dot_all_scops_1 (stderr
, scops
);
1559 /* Display all SCoPs using dotty. */
1562 dot_scop (scop_p scop
)
1564 VEC (scop_p
, heap
) *scops
= NULL
;
1567 VEC_safe_push (scop_p
, heap
, scops
, scop
);
1569 /* When debugging, enable the following code. This cannot be used
1570 in production compilers because it calls "system". */
1574 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1575 gcc_assert (stream
);
1577 dot_all_scops_1 (stream
, scops
);
1579 x
= system ("dotty /tmp/allscops.dot &");
1582 dot_all_scops_1 (stderr
, scops
);
1585 VEC_free (scop_p
, heap
, scops
);