1 /* Detection of Static Control Parts (SCoP) for Graphite.
2 Copyright (C) 2009-2013 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/>. */
27 #include <isl/union_map.h>
28 #include <cloog/cloog.h>
29 #include <cloog/isl/domain.h>
33 #include "coretypes.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 "tree-ssa-propagate.h"
44 #include "graphite-poly.h"
45 #include "graphite-scop-detection.h"
47 /* Forward declarations. */
48 static void make_close_phi_nodes_unique (basic_block
);
50 /* The type of the analyzed basic block. */
52 typedef enum gbb_type
{
54 GBB_LOOP_SING_EXIT_HEADER
,
55 GBB_LOOP_MULT_EXIT_HEADER
,
62 /* Detect the type of BB. Loop headers are only marked, if they are
63 new. This means their loop_father is different to LAST_LOOP.
64 Otherwise they are treated like any other bb and their type can be
68 get_bb_type (basic_block bb
, struct loop
*last_loop
)
72 struct loop
*loop
= bb
->loop_father
;
74 /* Check, if we entry into a new loop. */
75 if (loop
!= last_loop
)
77 if (single_exit (loop
) != NULL
)
78 return GBB_LOOP_SING_EXIT_HEADER
;
79 else if (loop
->num
!= 0)
80 return GBB_LOOP_MULT_EXIT_HEADER
;
82 return GBB_COND_HEADER
;
85 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
86 nb_dom
= dom
.length ();
92 if (nb_dom
== 1 && single_succ_p (bb
))
95 return GBB_COND_HEADER
;
98 /* A SCoP detection region, defined using bbs as borders.
100 All control flow touching this region, comes in passing basic_block
101 ENTRY and leaves passing basic_block EXIT. By using bbs instead of
102 edges for the borders we are able to represent also regions that do
103 not have a single entry or exit edge.
105 But as they have a single entry basic_block and a single exit
106 basic_block, we are able to generate for every sd_region a single
114 / \ This region contains: {3, 4, 5, 6, 7, 8}
122 typedef struct sd_region_p
124 /* The entry bb dominates all bbs in the sd_region. It is part of
128 /* The exit bb postdominates all bbs in the sd_region, but is not
129 part of the region. */
135 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
138 move_sd_regions (vec
<sd_region
> *source
, vec
<sd_region
> *target
)
143 FOR_EACH_VEC_ELT (*source
, i
, s
)
144 target
->safe_push (*s
);
149 /* Something like "n * m" is not allowed. */
152 graphite_can_represent_init (tree e
)
154 switch (TREE_CODE (e
))
156 case POLYNOMIAL_CHREC
:
157 return graphite_can_represent_init (CHREC_LEFT (e
))
158 && graphite_can_represent_init (CHREC_RIGHT (e
));
161 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
162 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
163 && tree_fits_shwi_p (TREE_OPERAND (e
, 1));
165 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
166 && tree_fits_shwi_p (TREE_OPERAND (e
, 0));
169 case POINTER_PLUS_EXPR
:
171 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
172 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
177 case NON_LVALUE_EXPR
:
178 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
187 /* Return true when SCEV can be represented in the polyhedral model.
189 An expression can be represented, if it can be expressed as an
190 affine expression. For loops (i, j) and parameters (m, n) all
191 affine expressions are of the form:
193 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
195 1 i + 20 j + (-2) m + 25
197 Something like "i * n" or "n * m" is not allowed. */
200 graphite_can_represent_scev (tree scev
)
202 if (chrec_contains_undetermined (scev
))
205 switch (TREE_CODE (scev
))
209 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
210 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
213 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
214 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
215 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
216 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
217 && graphite_can_represent_init (scev
)
218 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
219 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
221 case POLYNOMIAL_CHREC
:
222 /* Check for constant strides. With a non constant stride of
223 'n' we would have a value of 'iv * n'. Also check that the
224 initial value can represented: for example 'n * m' cannot be
226 if (!evolution_function_right_is_integer_cst (scev
)
227 || !graphite_can_represent_init (scev
))
234 /* Only affine functions can be represented. */
235 if (!scev_is_linear_expression (scev
))
242 /* Return true when EXPR can be represented in the polyhedral model.
244 This means an expression can be represented, if it is linear with
245 respect to the loops and the strides are non parametric.
246 LOOP is the place where the expr will be evaluated. SCOP_ENTRY defines the
247 entry of the region we analyse. */
250 graphite_can_represent_expr (basic_block scop_entry
, loop_p loop
,
253 tree scev
= analyze_scalar_evolution (loop
, expr
);
255 scev
= instantiate_scev (scop_entry
, loop
, scev
);
257 return graphite_can_represent_scev (scev
);
260 /* Return true if the data references of STMT can be represented by
264 stmt_has_simple_data_refs_p (loop_p outermost_loop ATTRIBUTE_UNUSED
,
271 vec
<data_reference_p
> drs
= vNULL
;
274 for (outer
= loop_containing_stmt (stmt
); outer
; outer
= loop_outer (outer
))
276 graphite_find_data_references_in_stmt (outer
,
277 loop_containing_stmt (stmt
),
280 FOR_EACH_VEC_ELT (drs
, j
, dr
)
281 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
282 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
)))
288 free_data_refs (drs
);
293 free_data_refs (drs
);
297 /* Return true only when STMT is simple enough for being handled by
298 Graphite. This depends on SCOP_ENTRY, as the parameters are
299 initialized relatively to this basic block, the linear functions
300 are initialized to OUTERMOST_LOOP and BB is the place where we try
301 to evaluate the STMT. */
304 stmt_simple_for_scop_p (basic_block scop_entry
, loop_p outermost_loop
,
305 gimple stmt
, basic_block bb
)
307 loop_p loop
= bb
->loop_father
;
309 gcc_assert (scop_entry
);
311 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
312 Calls have side-effects, except those to const or pure
314 if (gimple_has_volatile_ops (stmt
)
315 || (gimple_code (stmt
) == GIMPLE_CALL
316 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
317 || (gimple_code (stmt
) == GIMPLE_ASM
))
320 if (is_gimple_debug (stmt
))
323 if (!stmt_has_simple_data_refs_p (outermost_loop
, stmt
))
326 switch (gimple_code (stmt
))
336 enum tree_code code
= gimple_cond_code (stmt
);
338 /* We can handle all binary comparisons. Inequalities are
339 also supported as they can be represented with union of
341 if (!(code
== LT_EXPR
349 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, op_iter
, SSA_OP_ALL_USES
)
350 if (!graphite_can_represent_expr (scop_entry
, loop
, op
)
351 /* We can not handle REAL_TYPE. Failed for pr39260. */
352 || TREE_CODE (TREE_TYPE (op
)) == REAL_TYPE
)
363 /* These nodes cut a new scope. */
370 /* Returns the statement of BB that contains a harmful operation: that
371 can be a function call with side effects, the induction variables
372 are not linear with respect to SCOP_ENTRY, etc. The current open
373 scop should end before this statement. The evaluation is limited using
374 OUTERMOST_LOOP as outermost loop that may change. */
377 harmful_stmt_in_bb (basic_block scop_entry
, loop_p outer_loop
, basic_block bb
)
379 gimple_stmt_iterator gsi
;
381 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
382 if (!stmt_simple_for_scop_p (scop_entry
, outer_loop
, gsi_stmt (gsi
), bb
))
383 return gsi_stmt (gsi
);
388 /* Return true if LOOP can be represented in the polyhedral
389 representation. This is evaluated taking SCOP_ENTRY and
390 OUTERMOST_LOOP in mind. */
393 graphite_can_represent_loop (basic_block scop_entry
, loop_p loop
)
396 struct tree_niter_desc niter_desc
;
398 /* FIXME: For the moment, graphite cannot be used on loops that
399 iterate using induction variables that wrap. */
401 return number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
402 && niter_desc
.control
.no_overflow
403 && (niter
= number_of_latch_executions (loop
))
404 && !chrec_contains_undetermined (niter
)
405 && graphite_can_represent_expr (scop_entry
, loop
, niter
);
408 /* Store information needed by scopdet_* functions. */
412 /* Exit of the open scop would stop if the current BB is harmful. */
415 /* Where the next scop would start if the current BB is harmful. */
418 /* The bb or one of its children contains open loop exits. That means
419 loop exit nodes that are not surrounded by a loop dominated by bb. */
422 /* The bb or one of its children contains only structures we can handle. */
426 static struct scopdet_info
build_scops_1 (basic_block
, loop_p
,
427 vec
<sd_region
> *, loop_p
);
429 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
430 to SCOPS. TYPE is the gbb_type of BB. */
432 static struct scopdet_info
433 scopdet_basic_block_info (basic_block bb
, loop_p outermost_loop
,
434 vec
<sd_region
> *scops
, gbb_type type
)
436 loop_p loop
= bb
->loop_father
;
437 struct scopdet_info result
;
440 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
441 basic_block entry_block
= ENTRY_BLOCK_PTR
;
442 stmt
= harmful_stmt_in_bb (entry_block
, outermost_loop
, bb
);
443 result
.difficult
= (stmt
!= NULL
);
450 result
.exits
= false;
452 /* Mark bbs terminating a SESE region difficult, if they start
454 if (!single_succ_p (bb
))
455 result
.difficult
= true;
457 result
.exit
= single_succ (bb
);
462 result
.next
= single_succ (bb
);
463 result
.exits
= false;
464 result
.exit
= single_succ (bb
);
467 case GBB_LOOP_SING_EXIT_HEADER
:
469 vec
<sd_region
> regions
;
471 struct scopdet_info sinfo
;
472 edge exit_e
= single_exit (loop
);
474 sinfo
= build_scops_1 (bb
, outermost_loop
, ®ions
, loop
);
476 if (!graphite_can_represent_loop (entry_block
, loop
))
477 result
.difficult
= true;
479 result
.difficult
|= sinfo
.difficult
;
481 /* Try again with another loop level. */
483 && loop_depth (outermost_loop
) + 1 == loop_depth (loop
))
485 outermost_loop
= loop
;
490 sinfo
= scopdet_basic_block_info (bb
, outermost_loop
, scops
, type
);
493 result
.difficult
= true;
496 move_sd_regions (®ions
, scops
);
500 open_scop
.entry
= bb
;
501 open_scop
.exit
= exit_e
->dest
;
502 scops
->safe_push (open_scop
);
508 result
.exit
= exit_e
->dest
;
509 result
.next
= exit_e
->dest
;
511 /* If we do not dominate result.next, remove it. It's either
512 the EXIT_BLOCK_PTR, or another bb dominates it and will
513 call the scop detection for this bb. */
514 if (!dominated_by_p (CDI_DOMINATORS
, result
.next
, bb
))
517 if (exit_e
->src
->loop_father
!= loop
)
520 result
.exits
= false;
522 if (result
.difficult
)
523 move_sd_regions (®ions
, scops
);
531 case GBB_LOOP_MULT_EXIT_HEADER
:
533 /* XXX: For now we just do not join loops with multiple exits. If the
534 exits lead to the same bb it may be possible to join the loop. */
535 vec
<sd_region
> regions
;
537 vec
<edge
> exits
= get_loop_exit_edges (loop
);
540 build_scops_1 (bb
, loop
, ®ions
, loop
);
542 /* Scan the code dominated by this loop. This means all bbs, that are
543 are dominated by a bb in this loop, but are not part of this loop.
546 - The loop exit destination is dominated by the exit sources.
548 TODO: We miss here the more complex cases:
549 - The exit destinations are dominated by another bb inside
551 - The loop dominates bbs, that are not exit destinations. */
552 FOR_EACH_VEC_ELT (exits
, i
, e
)
553 if (e
->src
->loop_father
== loop
554 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
))
556 if (loop_outer (outermost_loop
))
557 outermost_loop
= loop_outer (outermost_loop
);
559 /* Pass loop_outer to recognize e->dest as loop header in
561 if (e
->dest
->loop_father
->header
== e
->dest
)
562 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
563 loop_outer (e
->dest
->loop_father
));
565 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
566 e
->dest
->loop_father
);
571 result
.difficult
= true;
572 result
.exits
= false;
573 move_sd_regions (®ions
, scops
);
577 case GBB_COND_HEADER
:
579 vec
<sd_region
> regions
;
581 struct scopdet_info sinfo
;
582 vec
<basic_block
> dominated
;
585 basic_block last_exit
= NULL
;
587 result
.exits
= false;
589 /* First check the successors of BB, and check if it is
590 possible to join the different branches. */
591 FOR_EACH_VEC_SAFE_ELT (bb
->succs
, i
, e
)
593 /* Ignore loop exits. They will be handled after the loop
595 if (loop_exits_to_bb_p (loop
, e
->dest
))
601 /* Do not follow edges that lead to the end of the
602 conditions block. For example, in
612 the edge from 0 => 6. Only check if all paths lead to
615 if (!single_pred_p (e
->dest
))
617 /* Check, if edge leads directly to the end of this
622 if (e
->dest
!= last_exit
)
623 result
.difficult
= true;
628 if (!dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
630 result
.difficult
= true;
634 sinfo
= build_scops_1 (e
->dest
, outermost_loop
, ®ions
, loop
);
636 result
.exits
|= sinfo
.exits
;
637 result
.difficult
|= sinfo
.difficult
;
639 /* Checks, if all branches end at the same point.
640 If that is true, the condition stays joinable.
641 Have a look at the example above. */
645 last_exit
= sinfo
.exit
;
647 if (sinfo
.exit
!= last_exit
)
648 result
.difficult
= true;
651 result
.difficult
= true;
655 result
.difficult
= true;
657 /* Join the branches of the condition if possible. */
658 if (!result
.exits
&& !result
.difficult
)
660 /* Only return a next pointer if we dominate this pointer.
661 Otherwise it will be handled by the bb dominating it. */
662 if (dominated_by_p (CDI_DOMINATORS
, last_exit
, bb
)
664 result
.next
= last_exit
;
668 result
.exit
= last_exit
;
674 /* Scan remaining bbs dominated by BB. */
675 dominated
= get_dominated_by (CDI_DOMINATORS
, bb
);
677 FOR_EACH_VEC_ELT (dominated
, i
, dom_bb
)
679 /* Ignore loop exits: they will be handled after the loop body. */
680 if (loop_depth (find_common_loop (loop
, dom_bb
->loop_father
))
687 /* Ignore the bbs processed above. */
688 if (single_pred_p (dom_bb
) && single_pred (dom_bb
) == bb
)
691 if (loop_depth (loop
) > loop_depth (dom_bb
->loop_father
))
692 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
,
695 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
, loop
);
697 result
.exits
|= sinfo
.exits
;
698 result
.difficult
= true;
702 dominated
.release ();
705 move_sd_regions (®ions
, scops
);
717 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
718 SCOPS. The analyse if a sd_region can be handled is based on the value
719 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
720 is the loop in which CURRENT is handled.
722 TODO: These functions got a little bit big. They definitely should be cleaned
725 static struct scopdet_info
726 build_scops_1 (basic_block current
, loop_p outermost_loop
,
727 vec
<sd_region
> *scops
, loop_p loop
)
729 bool in_scop
= false;
731 struct scopdet_info sinfo
;
733 /* Initialize result. */
734 struct scopdet_info result
;
735 result
.exits
= false;
736 result
.difficult
= false;
739 open_scop
.entry
= NULL
;
740 open_scop
.exit
= NULL
;
743 /* Loop over the dominance tree. If we meet a difficult bb, close
744 the current SCoP. Loop and condition header start a new layer,
745 and can only be added if all bbs in deeper layers are simple. */
746 while (current
!= NULL
)
748 sinfo
= scopdet_basic_block_info (current
, outermost_loop
, scops
,
749 get_bb_type (current
, loop
));
751 if (!in_scop
&& !(sinfo
.exits
|| sinfo
.difficult
))
753 open_scop
.entry
= current
;
754 open_scop
.exit
= NULL
;
757 else if (in_scop
&& (sinfo
.exits
|| sinfo
.difficult
))
759 open_scop
.exit
= current
;
760 scops
->safe_push (open_scop
);
764 result
.difficult
|= sinfo
.difficult
;
765 result
.exits
|= sinfo
.exits
;
767 current
= sinfo
.next
;
770 /* Try to close open_scop, if we are still in an open SCoP. */
773 open_scop
.exit
= sinfo
.exit
;
774 gcc_assert (open_scop
.exit
);
775 scops
->safe_push (open_scop
);
778 result
.exit
= sinfo
.exit
;
782 /* Checks if a bb is contained in REGION. */
785 bb_in_sd_region (basic_block bb
, sd_region
*region
)
787 return bb_in_region (bb
, region
->entry
, region
->exit
);
790 /* Returns the single entry edge of REGION, if it does not exits NULL. */
793 find_single_entry_edge (sd_region
*region
)
799 FOR_EACH_EDGE (e
, ei
, region
->entry
->preds
)
800 if (!bb_in_sd_region (e
->src
, region
))
815 /* Returns the single exit edge of REGION, if it does not exits NULL. */
818 find_single_exit_edge (sd_region
*region
)
824 FOR_EACH_EDGE (e
, ei
, region
->exit
->preds
)
825 if (bb_in_sd_region (e
->src
, region
))
840 /* Create a single entry edge for REGION. */
843 create_single_entry_edge (sd_region
*region
)
845 if (find_single_entry_edge (region
))
848 /* There are multiple predecessors for bb_3
861 There are two edges (1->3, 2->3), that point from outside into the region,
862 and another one (5->3), a loop latch, lead to bb_3.
870 | |\ (3.0 -> 3.1) = single entry edge
879 If the loop is part of the SCoP, we have to redirect the loop latches.
885 | | (3.0 -> 3.1) = entry edge
894 if (region
->entry
->loop_father
->header
!= region
->entry
895 || dominated_by_p (CDI_DOMINATORS
,
896 loop_latch_edge (region
->entry
->loop_father
)->src
,
899 edge forwarder
= split_block_after_labels (region
->entry
);
900 region
->entry
= forwarder
->dest
;
903 /* This case is never executed, as the loop headers seem always to have a
904 single edge pointing from outside into the loop. */
907 gcc_checking_assert (find_single_entry_edge (region
));
910 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
913 sd_region_without_exit (edge e
)
915 sd_region
*r
= (sd_region
*) e
->aux
;
918 return r
->exit
== NULL
;
923 /* Create a single exit edge for REGION. */
926 create_single_exit_edge (sd_region
*region
)
930 edge forwarder
= NULL
;
933 /* We create a forwarder bb (5) for all edges leaving this region
934 (3->5, 4->5). All other edges leading to the same bb, are moved
935 to a new bb (6). If these edges where part of another region (2->5)
936 we update the region->exit pointer, of this region.
938 To identify which edge belongs to which region we depend on the e->aux
939 pointer in every edge. It points to the region of the edge or to NULL,
940 if the edge is not part of any region.
942 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
943 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
948 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
949 | | \/ 3->5 no region, 4->5 no region,
951 \| / 5->6 region->exit = 6
954 Now there is only a single exit edge (5->6). */
957 forwarder
= make_forwarder_block (exit
, &sd_region_without_exit
, NULL
);
959 /* Unmark the edges, that are no longer exit edges. */
960 FOR_EACH_EDGE (e
, ei
, forwarder
->src
->preds
)
964 /* Mark the new exit edge. */
965 single_succ_edge (forwarder
->src
)->aux
= region
;
967 /* Update the exit bb of all regions, where exit edges lead to
969 FOR_EACH_EDGE (e
, ei
, forwarder
->dest
->preds
)
971 ((sd_region
*) e
->aux
)->exit
= forwarder
->dest
;
973 gcc_checking_assert (find_single_exit_edge (region
));
976 /* Unmark the exit edges of all REGIONS.
977 See comment in "create_single_exit_edge". */
980 unmark_exit_edges (vec
<sd_region
> regions
)
987 FOR_EACH_VEC_ELT (regions
, i
, s
)
988 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
993 /* Mark the exit edges of all REGIONS.
994 See comment in "create_single_exit_edge". */
997 mark_exit_edges (vec
<sd_region
> regions
)
1004 FOR_EACH_VEC_ELT (regions
, i
, s
)
1005 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1006 if (bb_in_sd_region (e
->src
, s
))
1010 /* Create for all scop regions a single entry and a single exit edge. */
1013 create_sese_edges (vec
<sd_region
> regions
)
1018 FOR_EACH_VEC_ELT (regions
, i
, s
)
1019 create_single_entry_edge (s
);
1021 mark_exit_edges (regions
);
1023 FOR_EACH_VEC_ELT (regions
, i
, s
)
1024 /* Don't handle multiple edges exiting the function. */
1025 if (!find_single_exit_edge (s
)
1026 && s
->exit
!= EXIT_BLOCK_PTR
)
1027 create_single_exit_edge (s
);
1029 unmark_exit_edges (regions
);
1031 calculate_dominance_info (CDI_DOMINATORS
);
1032 fix_loop_structure (NULL
);
1034 #ifdef ENABLE_CHECKING
1035 verify_loop_structure ();
1040 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1043 build_graphite_scops (vec
<sd_region
> regions
,
1049 FOR_EACH_VEC_ELT (regions
, i
, s
)
1051 edge entry
= find_single_entry_edge (s
);
1052 edge exit
= find_single_exit_edge (s
);
1058 scop
= new_scop (new_sese (entry
, exit
));
1059 scops
->safe_push (scop
);
1061 /* Are there overlapping SCoPs? */
1062 #ifdef ENABLE_CHECKING
1067 FOR_EACH_VEC_ELT (regions
, j
, s2
)
1069 gcc_assert (!bb_in_sd_region (s
->entry
, s2
));
1075 /* Returns true when BB contains only close phi nodes. */
1078 contains_only_close_phi_nodes (basic_block bb
)
1080 gimple_stmt_iterator gsi
;
1082 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1083 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_LABEL
)
1089 /* Print statistics for SCOP to FILE. */
1092 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
1097 long n_conditions
= 0;
1101 long n_p_conditions
= 0;
1107 gimple_stmt_iterator psi
;
1108 loop_p loop
= bb
->loop_father
;
1110 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
1114 n_p_bbs
+= bb
->count
;
1116 if (EDGE_COUNT (bb
->succs
) > 1)
1119 n_p_conditions
+= bb
->count
;
1122 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1125 n_p_stmts
+= bb
->count
;
1128 if (loop
->header
== bb
&& loop_in_sese_p (loop
, SCOP_REGION (scop
)))
1131 n_p_loops
+= bb
->count
;
1136 fprintf (file
, "\nBefore limit_scops SCoP statistics (");
1137 fprintf (file
, "BBS:%ld, ", n_bbs
);
1138 fprintf (file
, "LOOPS:%ld, ", n_loops
);
1139 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
1140 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
1141 fprintf (file
, "\nBefore limit_scops SCoP profiling statistics (");
1142 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
1143 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
1144 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
1145 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
1148 /* Print statistics for SCOPS to FILE. */
1151 print_graphite_statistics (FILE* file
, vec
<scop_p
> scops
)
1156 FOR_EACH_VEC_ELT (scops
, i
, scop
)
1157 print_graphite_scop_statistics (file
, scop
);
1160 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1170 * SCoP frontier, as this line is not surrounded by any loop. *
1174 This is necessary as scalar evolution and parameter detection need a
1175 outermost loop to initialize parameters correctly.
1177 TODO: FIX scalar evolution and parameter detection to allow more flexible
1181 limit_scops (vec
<scop_p
> *scops
)
1183 vec
<sd_region
> regions
;
1189 FOR_EACH_VEC_ELT (*scops
, i
, scop
)
1193 sese region
= SCOP_REGION (scop
);
1194 build_sese_loop_nests (region
);
1196 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), j
, loop
)
1197 if (!loop_in_sese_p (loop_outer (loop
), region
)
1198 && single_exit (loop
))
1200 sd_region open_scop
;
1201 open_scop
.entry
= loop
->header
;
1202 open_scop
.exit
= single_exit (loop
)->dest
;
1204 /* This is a hack on top of the limit_scops hack. The
1205 limit_scops hack should disappear all together. */
1206 if (single_succ_p (open_scop
.exit
)
1207 && contains_only_close_phi_nodes (open_scop
.exit
))
1208 open_scop
.exit
= single_succ_edge (open_scop
.exit
)->dest
;
1210 regions
.safe_push (open_scop
);
1214 free_scops (*scops
);
1217 create_sese_edges (regions
);
1218 build_graphite_scops (regions
, scops
);
1222 /* Returns true when P1 and P2 are close phis with the same
1226 same_close_phi_node (gimple p1
, gimple p2
)
1228 return operand_equal_p (gimple_phi_arg_def (p1
, 0),
1229 gimple_phi_arg_def (p2
, 0), 0);
1232 /* Remove the close phi node at GSI and replace its rhs with the rhs
1236 remove_duplicate_close_phi (gimple phi
, gimple_stmt_iterator
*gsi
)
1239 use_operand_p use_p
;
1240 imm_use_iterator imm_iter
;
1241 tree res
= gimple_phi_result (phi
);
1242 tree def
= gimple_phi_result (gsi_stmt (*gsi
));
1244 gcc_assert (same_close_phi_node (phi
, gsi_stmt (*gsi
)));
1246 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1248 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1249 SET_USE (use_p
, res
);
1251 update_stmt (use_stmt
);
1253 /* It is possible that we just created a duplicate close-phi
1254 for an already-processed containing loop. Check for this
1255 case and clean it up. */
1256 if (gimple_code (use_stmt
) == GIMPLE_PHI
1257 && gimple_phi_num_args (use_stmt
) == 1)
1258 make_close_phi_nodes_unique (gimple_bb (use_stmt
));
1261 remove_phi_node (gsi
, true);
1264 /* Removes all the close phi duplicates from BB. */
1267 make_close_phi_nodes_unique (basic_block bb
)
1269 gimple_stmt_iterator psi
;
1271 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1273 gimple_stmt_iterator gsi
= psi
;
1274 gimple phi
= gsi_stmt (psi
);
1276 /* At this point, PHI should be a close phi in normal form. */
1277 gcc_assert (gimple_phi_num_args (phi
) == 1);
1279 /* Iterate over the next phis and remove duplicates. */
1281 while (!gsi_end_p (gsi
))
1282 if (same_close_phi_node (phi
, gsi_stmt (gsi
)))
1283 remove_duplicate_close_phi (phi
, &gsi
);
1289 /* Transforms LOOP to the canonical loop closed SSA form. */
1292 canonicalize_loop_closed_ssa (loop_p loop
)
1294 edge e
= single_exit (loop
);
1297 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
1302 if (single_pred_p (bb
))
1304 e
= split_block_after_labels (bb
);
1305 make_close_phi_nodes_unique (e
->src
);
1309 gimple_stmt_iterator psi
;
1310 basic_block close
= split_edge (e
);
1312 e
= single_succ_edge (close
);
1314 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1316 gimple phi
= gsi_stmt (psi
);
1319 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1320 if (gimple_phi_arg_edge (phi
, i
) == e
)
1322 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
1323 use_operand_p use_p
;
1326 if (TREE_CODE (arg
) != SSA_NAME
)
1329 close_phi
= create_phi_node (NULL_TREE
, close
);
1330 res
= create_new_def_for (arg
, close_phi
,
1331 gimple_phi_result_ptr (close_phi
));
1332 add_phi_arg (close_phi
, arg
,
1333 gimple_phi_arg_edge (close_phi
, 0),
1335 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
1336 replace_exp (use_p
, res
);
1341 make_close_phi_nodes_unique (close
);
1344 /* The code above does not properly handle changes in the post dominance
1345 information (yet). */
1346 free_dominance_info (CDI_POST_DOMINATORS
);
1349 /* Converts the current loop closed SSA form to a canonical form
1350 expected by the Graphite code generation.
1352 The loop closed SSA form has the following invariant: a variable
1353 defined in a loop that is used outside the loop appears only in the
1354 phi nodes in the destination of the loop exit. These phi nodes are
1355 called close phi nodes.
1357 The canonical loop closed SSA form contains the extra invariants:
1359 - when the loop contains only one exit, the close phi nodes contain
1360 only one argument. That implies that the basic block that contains
1361 the close phi nodes has only one predecessor, that is a basic block
1364 - the basic block containing the close phi nodes does not contain
1367 - there exist only one phi node per definition in the loop.
1371 canonicalize_loop_closed_ssa_form (void)
1376 #ifdef ENABLE_CHECKING
1377 verify_loop_closed_ssa (true);
1380 FOR_EACH_LOOP (li
, loop
, 0)
1381 canonicalize_loop_closed_ssa (loop
);
1383 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1384 update_ssa (TODO_update_ssa
);
1386 #ifdef ENABLE_CHECKING
1387 verify_loop_closed_ssa (true);
1391 /* Find Static Control Parts (SCoP) in the current function and pushes
1395 build_scops (vec
<scop_p
> *scops
)
1397 struct loop
*loop
= current_loops
->tree_root
;
1398 vec
<sd_region
> regions
;
1401 canonicalize_loop_closed_ssa_form ();
1402 build_scops_1 (single_succ (ENTRY_BLOCK_PTR
), ENTRY_BLOCK_PTR
->loop_father
,
1404 create_sese_edges (regions
);
1405 build_graphite_scops (regions
, scops
);
1407 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1408 print_graphite_statistics (dump_file
, *scops
);
1410 limit_scops (scops
);
1413 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1414 fprintf (dump_file
, "\nnumber of SCoPs: %d\n",
1415 scops
? scops
->length () : 0);
1418 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1419 different colors. If there are not enough colors, paint the
1420 remaining SCoPs in gray.
1423 - "*" after the node number denotes the entry of a SCoP,
1424 - "#" after the node number denotes the exit of a SCoP,
1425 - "()" around the node number denotes the entry or the
1426 exit nodes of the SCOP. These are not part of SCoP. */
1429 dot_all_scops_1 (FILE *file
, vec
<scop_p
> scops
)
1438 /* Disable debugging while printing graph. */
1439 int tmp_dump_flags
= dump_flags
;
1442 fprintf (file
, "digraph all {\n");
1446 int part_of_scop
= false;
1448 /* Use HTML for every bb label. So we are able to print bbs
1449 which are part of two different SCoPs, with two different
1450 background colors. */
1451 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1453 fprintf (file
, "CELLSPACING=\"0\">\n");
1455 /* Select color for SCoP. */
1456 FOR_EACH_VEC_ELT (scops
, i
, scop
)
1458 sese region
= SCOP_REGION (scop
);
1459 if (bb_in_sese_p (bb
, region
)
1460 || (SESE_EXIT_BB (region
) == bb
)
1461 || (SESE_ENTRY_BB (region
) == bb
))
1474 case 3: /* purple */
1477 case 4: /* orange */
1480 case 5: /* yellow */
1520 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color
);
1522 if (!bb_in_sese_p (bb
, region
))
1523 fprintf (file
, " (");
1525 if (bb
== SESE_ENTRY_BB (region
)
1526 && bb
== SESE_EXIT_BB (region
))
1527 fprintf (file
, " %d*# ", bb
->index
);
1528 else if (bb
== SESE_ENTRY_BB (region
))
1529 fprintf (file
, " %d* ", bb
->index
);
1530 else if (bb
== SESE_EXIT_BB (region
))
1531 fprintf (file
, " %d# ", bb
->index
);
1533 fprintf (file
, " %d ", bb
->index
);
1535 if (!bb_in_sese_p (bb
,region
))
1536 fprintf (file
, ")");
1538 fprintf (file
, "</TD></TR>\n");
1539 part_of_scop
= true;
1545 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1546 fprintf (file
, " %d </TD></TR>\n", bb
->index
);
1548 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1553 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1554 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
1557 fputs ("}\n\n", file
);
1559 /* Enable debugging again. */
1560 dump_flags
= tmp_dump_flags
;
1563 /* Display all SCoPs using dotty. */
1566 dot_all_scops (vec
<scop_p
> scops
)
1568 /* When debugging, enable the following code. This cannot be used
1569 in production compilers because it calls "system". */
1572 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1573 gcc_assert (stream
);
1575 dot_all_scops_1 (stream
, scops
);
1578 x
= system ("dotty /tmp/allscops.dot &");
1580 dot_all_scops_1 (stderr
, scops
);
1584 /* Display all SCoPs using dotty. */
1587 dot_scop (scop_p scop
)
1589 vec
<scop_p
> scops
= vNULL
;
1592 scops
.safe_push (scop
);
1594 /* When debugging, enable the following code. This cannot be used
1595 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
);
1604 x
= system ("dotty /tmp/allscops.dot &");
1607 dot_all_scops_1 (stderr
, scops
);