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 "gimple-ssa.h"
37 #include "tree-phinodes.h"
38 #include "ssa-iterators.h"
39 #include "tree-ssa-loop-manip.h"
40 #include "tree-ssa-loop-niter.h"
41 #include "tree-ssa-loop.h"
42 #include "tree-into-ssa.h"
45 #include "tree-chrec.h"
46 #include "tree-data-ref.h"
47 #include "tree-scalar-evolution.h"
48 #include "tree-pass.h"
50 #include "tree-ssa-propagate.h"
53 #include "graphite-poly.h"
54 #include "graphite-scop-detection.h"
56 /* Forward declarations. */
57 static void make_close_phi_nodes_unique (basic_block
);
59 /* The type of the analyzed basic block. */
61 typedef enum gbb_type
{
63 GBB_LOOP_SING_EXIT_HEADER
,
64 GBB_LOOP_MULT_EXIT_HEADER
,
71 /* Detect the type of BB. Loop headers are only marked, if they are
72 new. This means their loop_father is different to LAST_LOOP.
73 Otherwise they are treated like any other bb and their type can be
77 get_bb_type (basic_block bb
, struct loop
*last_loop
)
81 struct loop
*loop
= bb
->loop_father
;
83 /* Check, if we entry into a new loop. */
84 if (loop
!= last_loop
)
86 if (single_exit (loop
) != NULL
)
87 return GBB_LOOP_SING_EXIT_HEADER
;
88 else if (loop
->num
!= 0)
89 return GBB_LOOP_MULT_EXIT_HEADER
;
91 return GBB_COND_HEADER
;
94 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
95 nb_dom
= dom
.length ();
101 if (nb_dom
== 1 && single_succ_p (bb
))
104 return GBB_COND_HEADER
;
107 /* A SCoP detection region, defined using bbs as borders.
109 All control flow touching this region, comes in passing basic_block
110 ENTRY and leaves passing basic_block EXIT. By using bbs instead of
111 edges for the borders we are able to represent also regions that do
112 not have a single entry or exit edge.
114 But as they have a single entry basic_block and a single exit
115 basic_block, we are able to generate for every sd_region a single
123 / \ This region contains: {3, 4, 5, 6, 7, 8}
131 typedef struct sd_region_p
133 /* The entry bb dominates all bbs in the sd_region. It is part of
137 /* The exit bb postdominates all bbs in the sd_region, but is not
138 part of the region. */
144 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
147 move_sd_regions (vec
<sd_region
> *source
, vec
<sd_region
> *target
)
152 FOR_EACH_VEC_ELT (*source
, i
, s
)
153 target
->safe_push (*s
);
158 /* Something like "n * m" is not allowed. */
161 graphite_can_represent_init (tree e
)
163 switch (TREE_CODE (e
))
165 case POLYNOMIAL_CHREC
:
166 return graphite_can_represent_init (CHREC_LEFT (e
))
167 && graphite_can_represent_init (CHREC_RIGHT (e
));
170 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
171 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
172 && host_integerp (TREE_OPERAND (e
, 1), 0);
174 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
175 && host_integerp (TREE_OPERAND (e
, 0), 0);
178 case POINTER_PLUS_EXPR
:
180 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
181 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
186 case NON_LVALUE_EXPR
:
187 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
196 /* Return true when SCEV can be represented in the polyhedral model.
198 An expression can be represented, if it can be expressed as an
199 affine expression. For loops (i, j) and parameters (m, n) all
200 affine expressions are of the form:
202 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
204 1 i + 20 j + (-2) m + 25
206 Something like "i * n" or "n * m" is not allowed. */
209 graphite_can_represent_scev (tree scev
)
211 if (chrec_contains_undetermined (scev
))
214 switch (TREE_CODE (scev
))
218 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
219 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
222 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
223 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
224 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
225 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
226 && graphite_can_represent_init (scev
)
227 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
228 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
230 case POLYNOMIAL_CHREC
:
231 /* Check for constant strides. With a non constant stride of
232 'n' we would have a value of 'iv * n'. Also check that the
233 initial value can represented: for example 'n * m' cannot be
235 if (!evolution_function_right_is_integer_cst (scev
)
236 || !graphite_can_represent_init (scev
))
243 /* Only affine functions can be represented. */
244 if (!scev_is_linear_expression (scev
))
251 /* Return true when EXPR can be represented in the polyhedral model.
253 This means an expression can be represented, if it is linear with
254 respect to the loops and the strides are non parametric.
255 LOOP is the place where the expr will be evaluated. SCOP_ENTRY defines the
256 entry of the region we analyse. */
259 graphite_can_represent_expr (basic_block scop_entry
, loop_p loop
,
262 tree scev
= analyze_scalar_evolution (loop
, expr
);
264 scev
= instantiate_scev (scop_entry
, loop
, scev
);
266 return graphite_can_represent_scev (scev
);
269 /* Return true if the data references of STMT can be represented by
273 stmt_has_simple_data_refs_p (loop_p outermost_loop ATTRIBUTE_UNUSED
,
280 vec
<data_reference_p
> drs
= vNULL
;
283 for (outer
= loop_containing_stmt (stmt
); outer
; outer
= loop_outer (outer
))
285 graphite_find_data_references_in_stmt (outer
,
286 loop_containing_stmt (stmt
),
289 FOR_EACH_VEC_ELT (drs
, j
, dr
)
290 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
291 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
)))
297 free_data_refs (drs
);
302 free_data_refs (drs
);
306 /* Return true only when STMT is simple enough for being handled by
307 Graphite. This depends on SCOP_ENTRY, as the parameters are
308 initialized relatively to this basic block, the linear functions
309 are initialized to OUTERMOST_LOOP and BB is the place where we try
310 to evaluate the STMT. */
313 stmt_simple_for_scop_p (basic_block scop_entry
, loop_p outermost_loop
,
314 gimple stmt
, basic_block bb
)
316 loop_p loop
= bb
->loop_father
;
318 gcc_assert (scop_entry
);
320 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
321 Calls have side-effects, except those to const or pure
323 if (gimple_has_volatile_ops (stmt
)
324 || (gimple_code (stmt
) == GIMPLE_CALL
325 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
326 || (gimple_code (stmt
) == GIMPLE_ASM
))
329 if (is_gimple_debug (stmt
))
332 if (!stmt_has_simple_data_refs_p (outermost_loop
, stmt
))
335 switch (gimple_code (stmt
))
345 enum tree_code code
= gimple_cond_code (stmt
);
347 /* We can handle all binary comparisons. Inequalities are
348 also supported as they can be represented with union of
350 if (!(code
== LT_EXPR
358 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, op_iter
, SSA_OP_ALL_USES
)
359 if (!graphite_can_represent_expr (scop_entry
, loop
, op
)
360 /* We can not handle REAL_TYPE. Failed for pr39260. */
361 || TREE_CODE (TREE_TYPE (op
)) == REAL_TYPE
)
372 /* These nodes cut a new scope. */
379 /* Returns the statement of BB that contains a harmful operation: that
380 can be a function call with side effects, the induction variables
381 are not linear with respect to SCOP_ENTRY, etc. The current open
382 scop should end before this statement. The evaluation is limited using
383 OUTERMOST_LOOP as outermost loop that may change. */
386 harmful_stmt_in_bb (basic_block scop_entry
, loop_p outer_loop
, basic_block bb
)
388 gimple_stmt_iterator gsi
;
390 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
391 if (!stmt_simple_for_scop_p (scop_entry
, outer_loop
, gsi_stmt (gsi
), bb
))
392 return gsi_stmt (gsi
);
397 /* Return true if LOOP can be represented in the polyhedral
398 representation. This is evaluated taking SCOP_ENTRY and
399 OUTERMOST_LOOP in mind. */
402 graphite_can_represent_loop (basic_block scop_entry
, loop_p loop
)
405 struct tree_niter_desc niter_desc
;
407 /* FIXME: For the moment, graphite cannot be used on loops that
408 iterate using induction variables that wrap. */
410 return number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
411 && niter_desc
.control
.no_overflow
412 && (niter
= number_of_latch_executions (loop
))
413 && !chrec_contains_undetermined (niter
)
414 && graphite_can_represent_expr (scop_entry
, loop
, niter
);
417 /* Store information needed by scopdet_* functions. */
421 /* Exit of the open scop would stop if the current BB is harmful. */
424 /* Where the next scop would start if the current BB is harmful. */
427 /* The bb or one of its children contains open loop exits. That means
428 loop exit nodes that are not surrounded by a loop dominated by bb. */
431 /* The bb or one of its children contains only structures we can handle. */
435 static struct scopdet_info
build_scops_1 (basic_block
, loop_p
,
436 vec
<sd_region
> *, loop_p
);
438 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
439 to SCOPS. TYPE is the gbb_type of BB. */
441 static struct scopdet_info
442 scopdet_basic_block_info (basic_block bb
, loop_p outermost_loop
,
443 vec
<sd_region
> *scops
, gbb_type type
)
445 loop_p loop
= bb
->loop_father
;
446 struct scopdet_info result
;
449 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
450 basic_block entry_block
= ENTRY_BLOCK_PTR
;
451 stmt
= harmful_stmt_in_bb (entry_block
, outermost_loop
, bb
);
452 result
.difficult
= (stmt
!= NULL
);
459 result
.exits
= false;
461 /* Mark bbs terminating a SESE region difficult, if they start
463 if (!single_succ_p (bb
))
464 result
.difficult
= true;
466 result
.exit
= single_succ (bb
);
471 result
.next
= single_succ (bb
);
472 result
.exits
= false;
473 result
.exit
= single_succ (bb
);
476 case GBB_LOOP_SING_EXIT_HEADER
:
478 vec
<sd_region
> regions
;
480 struct scopdet_info sinfo
;
481 edge exit_e
= single_exit (loop
);
483 sinfo
= build_scops_1 (bb
, outermost_loop
, ®ions
, loop
);
485 if (!graphite_can_represent_loop (entry_block
, loop
))
486 result
.difficult
= true;
488 result
.difficult
|= sinfo
.difficult
;
490 /* Try again with another loop level. */
492 && loop_depth (outermost_loop
) + 1 == loop_depth (loop
))
494 outermost_loop
= loop
;
499 sinfo
= scopdet_basic_block_info (bb
, outermost_loop
, scops
, type
);
502 result
.difficult
= true;
505 move_sd_regions (®ions
, scops
);
509 open_scop
.entry
= bb
;
510 open_scop
.exit
= exit_e
->dest
;
511 scops
->safe_push (open_scop
);
517 result
.exit
= exit_e
->dest
;
518 result
.next
= exit_e
->dest
;
520 /* If we do not dominate result.next, remove it. It's either
521 the EXIT_BLOCK_PTR, or another bb dominates it and will
522 call the scop detection for this bb. */
523 if (!dominated_by_p (CDI_DOMINATORS
, result
.next
, bb
))
526 if (exit_e
->src
->loop_father
!= loop
)
529 result
.exits
= false;
531 if (result
.difficult
)
532 move_sd_regions (®ions
, scops
);
540 case GBB_LOOP_MULT_EXIT_HEADER
:
542 /* XXX: For now we just do not join loops with multiple exits. If the
543 exits lead to the same bb it may be possible to join the loop. */
544 vec
<sd_region
> regions
;
546 vec
<edge
> exits
= get_loop_exit_edges (loop
);
549 build_scops_1 (bb
, loop
, ®ions
, loop
);
551 /* Scan the code dominated by this loop. This means all bbs, that are
552 are dominated by a bb in this loop, but are not part of this loop.
555 - The loop exit destination is dominated by the exit sources.
557 TODO: We miss here the more complex cases:
558 - The exit destinations are dominated by another bb inside
560 - The loop dominates bbs, that are not exit destinations. */
561 FOR_EACH_VEC_ELT (exits
, i
, e
)
562 if (e
->src
->loop_father
== loop
563 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
))
565 if (loop_outer (outermost_loop
))
566 outermost_loop
= loop_outer (outermost_loop
);
568 /* Pass loop_outer to recognize e->dest as loop header in
570 if (e
->dest
->loop_father
->header
== e
->dest
)
571 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
572 loop_outer (e
->dest
->loop_father
));
574 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
575 e
->dest
->loop_father
);
580 result
.difficult
= true;
581 result
.exits
= false;
582 move_sd_regions (®ions
, scops
);
586 case GBB_COND_HEADER
:
588 vec
<sd_region
> regions
;
590 struct scopdet_info sinfo
;
591 vec
<basic_block
> dominated
;
594 basic_block last_exit
= NULL
;
596 result
.exits
= false;
598 /* First check the successors of BB, and check if it is
599 possible to join the different branches. */
600 FOR_EACH_VEC_SAFE_ELT (bb
->succs
, i
, e
)
602 /* Ignore loop exits. They will be handled after the loop
604 if (loop_exits_to_bb_p (loop
, e
->dest
))
610 /* Do not follow edges that lead to the end of the
611 conditions block. For example, in
621 the edge from 0 => 6. Only check if all paths lead to
624 if (!single_pred_p (e
->dest
))
626 /* Check, if edge leads directly to the end of this
631 if (e
->dest
!= last_exit
)
632 result
.difficult
= true;
637 if (!dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
639 result
.difficult
= true;
643 sinfo
= build_scops_1 (e
->dest
, outermost_loop
, ®ions
, loop
);
645 result
.exits
|= sinfo
.exits
;
646 result
.difficult
|= sinfo
.difficult
;
648 /* Checks, if all branches end at the same point.
649 If that is true, the condition stays joinable.
650 Have a look at the example above. */
654 last_exit
= sinfo
.exit
;
656 if (sinfo
.exit
!= last_exit
)
657 result
.difficult
= true;
660 result
.difficult
= true;
664 result
.difficult
= true;
666 /* Join the branches of the condition if possible. */
667 if (!result
.exits
&& !result
.difficult
)
669 /* Only return a next pointer if we dominate this pointer.
670 Otherwise it will be handled by the bb dominating it. */
671 if (dominated_by_p (CDI_DOMINATORS
, last_exit
, bb
)
673 result
.next
= last_exit
;
677 result
.exit
= last_exit
;
683 /* Scan remaining bbs dominated by BB. */
684 dominated
= get_dominated_by (CDI_DOMINATORS
, bb
);
686 FOR_EACH_VEC_ELT (dominated
, i
, dom_bb
)
688 /* Ignore loop exits: they will be handled after the loop body. */
689 if (loop_depth (find_common_loop (loop
, dom_bb
->loop_father
))
696 /* Ignore the bbs processed above. */
697 if (single_pred_p (dom_bb
) && single_pred (dom_bb
) == bb
)
700 if (loop_depth (loop
) > loop_depth (dom_bb
->loop_father
))
701 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
,
704 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
, loop
);
706 result
.exits
|= sinfo
.exits
;
707 result
.difficult
= true;
711 dominated
.release ();
714 move_sd_regions (®ions
, scops
);
726 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
727 SCOPS. The analyse if a sd_region can be handled is based on the value
728 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
729 is the loop in which CURRENT is handled.
731 TODO: These functions got a little bit big. They definitely should be cleaned
734 static struct scopdet_info
735 build_scops_1 (basic_block current
, loop_p outermost_loop
,
736 vec
<sd_region
> *scops
, loop_p loop
)
738 bool in_scop
= false;
740 struct scopdet_info sinfo
;
742 /* Initialize result. */
743 struct scopdet_info result
;
744 result
.exits
= false;
745 result
.difficult
= false;
748 open_scop
.entry
= NULL
;
749 open_scop
.exit
= NULL
;
752 /* Loop over the dominance tree. If we meet a difficult bb, close
753 the current SCoP. Loop and condition header start a new layer,
754 and can only be added if all bbs in deeper layers are simple. */
755 while (current
!= NULL
)
757 sinfo
= scopdet_basic_block_info (current
, outermost_loop
, scops
,
758 get_bb_type (current
, loop
));
760 if (!in_scop
&& !(sinfo
.exits
|| sinfo
.difficult
))
762 open_scop
.entry
= current
;
763 open_scop
.exit
= NULL
;
766 else if (in_scop
&& (sinfo
.exits
|| sinfo
.difficult
))
768 open_scop
.exit
= current
;
769 scops
->safe_push (open_scop
);
773 result
.difficult
|= sinfo
.difficult
;
774 result
.exits
|= sinfo
.exits
;
776 current
= sinfo
.next
;
779 /* Try to close open_scop, if we are still in an open SCoP. */
782 open_scop
.exit
= sinfo
.exit
;
783 gcc_assert (open_scop
.exit
);
784 scops
->safe_push (open_scop
);
787 result
.exit
= sinfo
.exit
;
791 /* Checks if a bb is contained in REGION. */
794 bb_in_sd_region (basic_block bb
, sd_region
*region
)
796 return bb_in_region (bb
, region
->entry
, region
->exit
);
799 /* Returns the single entry edge of REGION, if it does not exits NULL. */
802 find_single_entry_edge (sd_region
*region
)
808 FOR_EACH_EDGE (e
, ei
, region
->entry
->preds
)
809 if (!bb_in_sd_region (e
->src
, region
))
824 /* Returns the single exit edge of REGION, if it does not exits NULL. */
827 find_single_exit_edge (sd_region
*region
)
833 FOR_EACH_EDGE (e
, ei
, region
->exit
->preds
)
834 if (bb_in_sd_region (e
->src
, region
))
849 /* Create a single entry edge for REGION. */
852 create_single_entry_edge (sd_region
*region
)
854 if (find_single_entry_edge (region
))
857 /* There are multiple predecessors for bb_3
870 There are two edges (1->3, 2->3), that point from outside into the region,
871 and another one (5->3), a loop latch, lead to bb_3.
879 | |\ (3.0 -> 3.1) = single entry edge
888 If the loop is part of the SCoP, we have to redirect the loop latches.
894 | | (3.0 -> 3.1) = entry edge
903 if (region
->entry
->loop_father
->header
!= region
->entry
904 || dominated_by_p (CDI_DOMINATORS
,
905 loop_latch_edge (region
->entry
->loop_father
)->src
,
908 edge forwarder
= split_block_after_labels (region
->entry
);
909 region
->entry
= forwarder
->dest
;
912 /* This case is never executed, as the loop headers seem always to have a
913 single edge pointing from outside into the loop. */
916 gcc_checking_assert (find_single_entry_edge (region
));
919 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
922 sd_region_without_exit (edge e
)
924 sd_region
*r
= (sd_region
*) e
->aux
;
927 return r
->exit
== NULL
;
932 /* Create a single exit edge for REGION. */
935 create_single_exit_edge (sd_region
*region
)
939 edge forwarder
= NULL
;
942 /* We create a forwarder bb (5) for all edges leaving this region
943 (3->5, 4->5). All other edges leading to the same bb, are moved
944 to a new bb (6). If these edges where part of another region (2->5)
945 we update the region->exit pointer, of this region.
947 To identify which edge belongs to which region we depend on the e->aux
948 pointer in every edge. It points to the region of the edge or to NULL,
949 if the edge is not part of any region.
951 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
952 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
957 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
958 | | \/ 3->5 no region, 4->5 no region,
960 \| / 5->6 region->exit = 6
963 Now there is only a single exit edge (5->6). */
966 forwarder
= make_forwarder_block (exit
, &sd_region_without_exit
, NULL
);
968 /* Unmark the edges, that are no longer exit edges. */
969 FOR_EACH_EDGE (e
, ei
, forwarder
->src
->preds
)
973 /* Mark the new exit edge. */
974 single_succ_edge (forwarder
->src
)->aux
= region
;
976 /* Update the exit bb of all regions, where exit edges lead to
978 FOR_EACH_EDGE (e
, ei
, forwarder
->dest
->preds
)
980 ((sd_region
*) e
->aux
)->exit
= forwarder
->dest
;
982 gcc_checking_assert (find_single_exit_edge (region
));
985 /* Unmark the exit edges of all REGIONS.
986 See comment in "create_single_exit_edge". */
989 unmark_exit_edges (vec
<sd_region
> regions
)
996 FOR_EACH_VEC_ELT (regions
, i
, s
)
997 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1002 /* Mark the exit edges of all REGIONS.
1003 See comment in "create_single_exit_edge". */
1006 mark_exit_edges (vec
<sd_region
> regions
)
1013 FOR_EACH_VEC_ELT (regions
, i
, s
)
1014 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1015 if (bb_in_sd_region (e
->src
, s
))
1019 /* Create for all scop regions a single entry and a single exit edge. */
1022 create_sese_edges (vec
<sd_region
> regions
)
1027 FOR_EACH_VEC_ELT (regions
, i
, s
)
1028 create_single_entry_edge (s
);
1030 mark_exit_edges (regions
);
1032 FOR_EACH_VEC_ELT (regions
, i
, s
)
1033 /* Don't handle multiple edges exiting the function. */
1034 if (!find_single_exit_edge (s
)
1035 && s
->exit
!= EXIT_BLOCK_PTR
)
1036 create_single_exit_edge (s
);
1038 unmark_exit_edges (regions
);
1040 calculate_dominance_info (CDI_DOMINATORS
);
1041 fix_loop_structure (NULL
);
1043 #ifdef ENABLE_CHECKING
1044 verify_loop_structure ();
1049 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1052 build_graphite_scops (vec
<sd_region
> regions
,
1058 FOR_EACH_VEC_ELT (regions
, i
, s
)
1060 edge entry
= find_single_entry_edge (s
);
1061 edge exit
= find_single_exit_edge (s
);
1067 scop
= new_scop (new_sese (entry
, exit
));
1068 scops
->safe_push (scop
);
1070 /* Are there overlapping SCoPs? */
1071 #ifdef ENABLE_CHECKING
1076 FOR_EACH_VEC_ELT (regions
, j
, s2
)
1078 gcc_assert (!bb_in_sd_region (s
->entry
, s2
));
1084 /* Returns true when BB contains only close phi nodes. */
1087 contains_only_close_phi_nodes (basic_block bb
)
1089 gimple_stmt_iterator gsi
;
1091 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1092 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_LABEL
)
1098 /* Print statistics for SCOP to FILE. */
1101 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
1106 long n_conditions
= 0;
1110 long n_p_conditions
= 0;
1116 gimple_stmt_iterator psi
;
1117 loop_p loop
= bb
->loop_father
;
1119 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
1123 n_p_bbs
+= bb
->count
;
1125 if (EDGE_COUNT (bb
->succs
) > 1)
1128 n_p_conditions
+= bb
->count
;
1131 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1134 n_p_stmts
+= bb
->count
;
1137 if (loop
->header
== bb
&& loop_in_sese_p (loop
, SCOP_REGION (scop
)))
1140 n_p_loops
+= bb
->count
;
1145 fprintf (file
, "\nBefore limit_scops SCoP statistics (");
1146 fprintf (file
, "BBS:%ld, ", n_bbs
);
1147 fprintf (file
, "LOOPS:%ld, ", n_loops
);
1148 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
1149 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
1150 fprintf (file
, "\nBefore limit_scops SCoP profiling statistics (");
1151 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
1152 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
1153 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
1154 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
1157 /* Print statistics for SCOPS to FILE. */
1160 print_graphite_statistics (FILE* file
, vec
<scop_p
> scops
)
1165 FOR_EACH_VEC_ELT (scops
, i
, scop
)
1166 print_graphite_scop_statistics (file
, scop
);
1169 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1179 * SCoP frontier, as this line is not surrounded by any loop. *
1183 This is necessary as scalar evolution and parameter detection need a
1184 outermost loop to initialize parameters correctly.
1186 TODO: FIX scalar evolution and parameter detection to allow more flexible
1190 limit_scops (vec
<scop_p
> *scops
)
1192 vec
<sd_region
> regions
;
1198 FOR_EACH_VEC_ELT (*scops
, i
, scop
)
1202 sese region
= SCOP_REGION (scop
);
1203 build_sese_loop_nests (region
);
1205 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), j
, loop
)
1206 if (!loop_in_sese_p (loop_outer (loop
), region
)
1207 && single_exit (loop
))
1209 sd_region open_scop
;
1210 open_scop
.entry
= loop
->header
;
1211 open_scop
.exit
= single_exit (loop
)->dest
;
1213 /* This is a hack on top of the limit_scops hack. The
1214 limit_scops hack should disappear all together. */
1215 if (single_succ_p (open_scop
.exit
)
1216 && contains_only_close_phi_nodes (open_scop
.exit
))
1217 open_scop
.exit
= single_succ_edge (open_scop
.exit
)->dest
;
1219 regions
.safe_push (open_scop
);
1223 free_scops (*scops
);
1226 create_sese_edges (regions
);
1227 build_graphite_scops (regions
, scops
);
1231 /* Returns true when P1 and P2 are close phis with the same
1235 same_close_phi_node (gimple p1
, gimple p2
)
1237 return operand_equal_p (gimple_phi_arg_def (p1
, 0),
1238 gimple_phi_arg_def (p2
, 0), 0);
1241 /* Remove the close phi node at GSI and replace its rhs with the rhs
1245 remove_duplicate_close_phi (gimple phi
, gimple_stmt_iterator
*gsi
)
1248 use_operand_p use_p
;
1249 imm_use_iterator imm_iter
;
1250 tree res
= gimple_phi_result (phi
);
1251 tree def
= gimple_phi_result (gsi_stmt (*gsi
));
1253 gcc_assert (same_close_phi_node (phi
, gsi_stmt (*gsi
)));
1255 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1257 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1258 SET_USE (use_p
, res
);
1260 update_stmt (use_stmt
);
1262 /* It is possible that we just created a duplicate close-phi
1263 for an already-processed containing loop. Check for this
1264 case and clean it up. */
1265 if (gimple_code (use_stmt
) == GIMPLE_PHI
1266 && gimple_phi_num_args (use_stmt
) == 1)
1267 make_close_phi_nodes_unique (gimple_bb (use_stmt
));
1270 remove_phi_node (gsi
, true);
1273 /* Removes all the close phi duplicates from BB. */
1276 make_close_phi_nodes_unique (basic_block bb
)
1278 gimple_stmt_iterator psi
;
1280 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1282 gimple_stmt_iterator gsi
= psi
;
1283 gimple phi
= gsi_stmt (psi
);
1285 /* At this point, PHI should be a close phi in normal form. */
1286 gcc_assert (gimple_phi_num_args (phi
) == 1);
1288 /* Iterate over the next phis and remove duplicates. */
1290 while (!gsi_end_p (gsi
))
1291 if (same_close_phi_node (phi
, gsi_stmt (gsi
)))
1292 remove_duplicate_close_phi (phi
, &gsi
);
1298 /* Transforms LOOP to the canonical loop closed SSA form. */
1301 canonicalize_loop_closed_ssa (loop_p loop
)
1303 edge e
= single_exit (loop
);
1306 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
1311 if (single_pred_p (bb
))
1313 e
= split_block_after_labels (bb
);
1314 make_close_phi_nodes_unique (e
->src
);
1318 gimple_stmt_iterator psi
;
1319 basic_block close
= split_edge (e
);
1321 e
= single_succ_edge (close
);
1323 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1325 gimple phi
= gsi_stmt (psi
);
1328 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1329 if (gimple_phi_arg_edge (phi
, i
) == e
)
1331 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
1332 use_operand_p use_p
;
1335 if (TREE_CODE (arg
) != SSA_NAME
)
1338 close_phi
= create_phi_node (NULL_TREE
, close
);
1339 res
= create_new_def_for (arg
, close_phi
,
1340 gimple_phi_result_ptr (close_phi
));
1341 add_phi_arg (close_phi
, arg
,
1342 gimple_phi_arg_edge (close_phi
, 0),
1344 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
1345 replace_exp (use_p
, res
);
1350 make_close_phi_nodes_unique (close
);
1353 /* The code above does not properly handle changes in the post dominance
1354 information (yet). */
1355 free_dominance_info (CDI_POST_DOMINATORS
);
1358 /* Converts the current loop closed SSA form to a canonical form
1359 expected by the Graphite code generation.
1361 The loop closed SSA form has the following invariant: a variable
1362 defined in a loop that is used outside the loop appears only in the
1363 phi nodes in the destination of the loop exit. These phi nodes are
1364 called close phi nodes.
1366 The canonical loop closed SSA form contains the extra invariants:
1368 - when the loop contains only one exit, the close phi nodes contain
1369 only one argument. That implies that the basic block that contains
1370 the close phi nodes has only one predecessor, that is a basic block
1373 - the basic block containing the close phi nodes does not contain
1376 - there exist only one phi node per definition in the loop.
1380 canonicalize_loop_closed_ssa_form (void)
1385 #ifdef ENABLE_CHECKING
1386 verify_loop_closed_ssa (true);
1389 FOR_EACH_LOOP (li
, loop
, 0)
1390 canonicalize_loop_closed_ssa (loop
);
1392 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1393 update_ssa (TODO_update_ssa
);
1395 #ifdef ENABLE_CHECKING
1396 verify_loop_closed_ssa (true);
1400 /* Find Static Control Parts (SCoP) in the current function and pushes
1404 build_scops (vec
<scop_p
> *scops
)
1406 struct loop
*loop
= current_loops
->tree_root
;
1407 vec
<sd_region
> regions
;
1410 canonicalize_loop_closed_ssa_form ();
1411 build_scops_1 (single_succ (ENTRY_BLOCK_PTR
), ENTRY_BLOCK_PTR
->loop_father
,
1413 create_sese_edges (regions
);
1414 build_graphite_scops (regions
, scops
);
1416 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1417 print_graphite_statistics (dump_file
, *scops
);
1419 limit_scops (scops
);
1422 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1423 fprintf (dump_file
, "\nnumber of SCoPs: %d\n",
1424 scops
? scops
->length () : 0);
1427 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1428 different colors. If there are not enough colors, paint the
1429 remaining SCoPs in gray.
1432 - "*" after the node number denotes the entry of a SCoP,
1433 - "#" after the node number denotes the exit of a SCoP,
1434 - "()" around the node number denotes the entry or the
1435 exit nodes of the SCOP. These are not part of SCoP. */
1438 dot_all_scops_1 (FILE *file
, vec
<scop_p
> scops
)
1447 /* Disable debugging while printing graph. */
1448 int tmp_dump_flags
= dump_flags
;
1451 fprintf (file
, "digraph all {\n");
1455 int part_of_scop
= false;
1457 /* Use HTML for every bb label. So we are able to print bbs
1458 which are part of two different SCoPs, with two different
1459 background colors. */
1460 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1462 fprintf (file
, "CELLSPACING=\"0\">\n");
1464 /* Select color for SCoP. */
1465 FOR_EACH_VEC_ELT (scops
, i
, scop
)
1467 sese region
= SCOP_REGION (scop
);
1468 if (bb_in_sese_p (bb
, region
)
1469 || (SESE_EXIT_BB (region
) == bb
)
1470 || (SESE_ENTRY_BB (region
) == bb
))
1483 case 3: /* purple */
1486 case 4: /* orange */
1489 case 5: /* yellow */
1529 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color
);
1531 if (!bb_in_sese_p (bb
, region
))
1532 fprintf (file
, " (");
1534 if (bb
== SESE_ENTRY_BB (region
)
1535 && bb
== SESE_EXIT_BB (region
))
1536 fprintf (file
, " %d*# ", bb
->index
);
1537 else if (bb
== SESE_ENTRY_BB (region
))
1538 fprintf (file
, " %d* ", bb
->index
);
1539 else if (bb
== SESE_EXIT_BB (region
))
1540 fprintf (file
, " %d# ", bb
->index
);
1542 fprintf (file
, " %d ", bb
->index
);
1544 if (!bb_in_sese_p (bb
,region
))
1545 fprintf (file
, ")");
1547 fprintf (file
, "</TD></TR>\n");
1548 part_of_scop
= true;
1554 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1555 fprintf (file
, " %d </TD></TR>\n", bb
->index
);
1557 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1562 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1563 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
1566 fputs ("}\n\n", file
);
1568 /* Enable debugging again. */
1569 dump_flags
= tmp_dump_flags
;
1572 /* Display all SCoPs using dotty. */
1575 dot_all_scops (vec
<scop_p
> scops
)
1577 /* When debugging, enable the following code. This cannot be used
1578 in production compilers because it calls "system". */
1581 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1582 gcc_assert (stream
);
1584 dot_all_scops_1 (stream
, scops
);
1587 x
= system ("dotty /tmp/allscops.dot &");
1589 dot_all_scops_1 (stderr
, scops
);
1593 /* Display all SCoPs using dotty. */
1596 dot_scop (scop_p scop
)
1598 vec
<scop_p
> scops
= vNULL
;
1601 scops
.safe_push (scop
);
1603 /* When debugging, enable the following code. This cannot be used
1604 in production compilers because it calls "system". */
1608 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1609 gcc_assert (stream
);
1611 dot_all_scops_1 (stream
, scops
);
1613 x
= system ("dotty /tmp/allscops.dot &");
1616 dot_all_scops_1 (stderr
, scops
);