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"
37 #include "tree-chrec.h"
38 #include "tree-data-ref.h"
39 #include "tree-scalar-evolution.h"
40 #include "tree-pass.h"
42 #include "tree-ssa-propagate.h"
45 #include "graphite-poly.h"
46 #include "graphite-scop-detection.h"
48 /* Forward declarations. */
49 static void make_close_phi_nodes_unique (basic_block
);
51 /* The type of the analyzed basic block. */
53 typedef enum gbb_type
{
55 GBB_LOOP_SING_EXIT_HEADER
,
56 GBB_LOOP_MULT_EXIT_HEADER
,
63 /* Detect the type of BB. Loop headers are only marked, if they are
64 new. This means their loop_father is different to LAST_LOOP.
65 Otherwise they are treated like any other bb and their type can be
69 get_bb_type (basic_block bb
, struct loop
*last_loop
)
73 struct loop
*loop
= bb
->loop_father
;
75 /* Check, if we entry into a new loop. */
76 if (loop
!= last_loop
)
78 if (single_exit (loop
) != NULL
)
79 return GBB_LOOP_SING_EXIT_HEADER
;
80 else if (loop
->num
!= 0)
81 return GBB_LOOP_MULT_EXIT_HEADER
;
83 return GBB_COND_HEADER
;
86 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
87 nb_dom
= dom
.length ();
93 if (nb_dom
== 1 && single_succ_p (bb
))
96 return GBB_COND_HEADER
;
99 /* A SCoP detection region, defined using bbs as borders.
101 All control flow touching this region, comes in passing basic_block
102 ENTRY and leaves passing basic_block EXIT. By using bbs instead of
103 edges for the borders we are able to represent also regions that do
104 not have a single entry or exit edge.
106 But as they have a single entry basic_block and a single exit
107 basic_block, we are able to generate for every sd_region a single
115 / \ This region contains: {3, 4, 5, 6, 7, 8}
123 typedef struct sd_region_p
125 /* The entry bb dominates all bbs in the sd_region. It is part of
129 /* The exit bb postdominates all bbs in the sd_region, but is not
130 part of the region. */
136 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
139 move_sd_regions (vec
<sd_region
> *source
, vec
<sd_region
> *target
)
144 FOR_EACH_VEC_ELT (*source
, i
, s
)
145 target
->safe_push (*s
);
150 /* Something like "n * m" is not allowed. */
153 graphite_can_represent_init (tree e
)
155 switch (TREE_CODE (e
))
157 case POLYNOMIAL_CHREC
:
158 return graphite_can_represent_init (CHREC_LEFT (e
))
159 && graphite_can_represent_init (CHREC_RIGHT (e
));
162 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
163 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
164 && host_integerp (TREE_OPERAND (e
, 1), 0);
166 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
167 && host_integerp (TREE_OPERAND (e
, 0), 0);
170 case POINTER_PLUS_EXPR
:
172 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
173 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
178 case NON_LVALUE_EXPR
:
179 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
188 /* Return true when SCEV can be represented in the polyhedral model.
190 An expression can be represented, if it can be expressed as an
191 affine expression. For loops (i, j) and parameters (m, n) all
192 affine expressions are of the form:
194 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
196 1 i + 20 j + (-2) m + 25
198 Something like "i * n" or "n * m" is not allowed. */
201 graphite_can_represent_scev (tree scev
)
203 if (chrec_contains_undetermined (scev
))
206 switch (TREE_CODE (scev
))
210 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
211 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
214 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
215 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
216 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
217 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
218 && graphite_can_represent_init (scev
)
219 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
220 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
222 case POLYNOMIAL_CHREC
:
223 /* Check for constant strides. With a non constant stride of
224 'n' we would have a value of 'iv * n'. Also check that the
225 initial value can represented: for example 'n * m' cannot be
227 if (!evolution_function_right_is_integer_cst (scev
)
228 || !graphite_can_represent_init (scev
))
235 /* Only affine functions can be represented. */
236 if (!scev_is_linear_expression (scev
))
243 /* Return true when EXPR can be represented in the polyhedral model.
245 This means an expression can be represented, if it is linear with
246 respect to the loops and the strides are non parametric.
247 LOOP is the place where the expr will be evaluated. SCOP_ENTRY defines the
248 entry of the region we analyse. */
251 graphite_can_represent_expr (basic_block scop_entry
, loop_p loop
,
254 tree scev
= analyze_scalar_evolution (loop
, expr
);
256 scev
= instantiate_scev (scop_entry
, loop
, scev
);
258 return graphite_can_represent_scev (scev
);
261 /* Return true if the data references of STMT can be represented by
265 stmt_has_simple_data_refs_p (loop_p outermost_loop ATTRIBUTE_UNUSED
,
272 vec
<data_reference_p
> drs
= vNULL
;
275 for (outer
= loop_containing_stmt (stmt
); outer
; outer
= loop_outer (outer
))
277 graphite_find_data_references_in_stmt (outer
,
278 loop_containing_stmt (stmt
),
281 FOR_EACH_VEC_ELT (drs
, j
, dr
)
282 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
283 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
)))
289 free_data_refs (drs
);
294 free_data_refs (drs
);
298 /* Return true only when STMT is simple enough for being handled by
299 Graphite. This depends on SCOP_ENTRY, as the parameters are
300 initialized relatively to this basic block, the linear functions
301 are initialized to OUTERMOST_LOOP and BB is the place where we try
302 to evaluate the STMT. */
305 stmt_simple_for_scop_p (basic_block scop_entry
, loop_p outermost_loop
,
306 gimple stmt
, basic_block bb
)
308 loop_p loop
= bb
->loop_father
;
310 gcc_assert (scop_entry
);
312 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
313 Calls have side-effects, except those to const or pure
315 if (gimple_has_volatile_ops (stmt
)
316 || (gimple_code (stmt
) == GIMPLE_CALL
317 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
318 || (gimple_code (stmt
) == GIMPLE_ASM
))
321 if (is_gimple_debug (stmt
))
324 if (!stmt_has_simple_data_refs_p (outermost_loop
, stmt
))
327 switch (gimple_code (stmt
))
337 enum tree_code code
= gimple_cond_code (stmt
);
339 /* We can handle all binary comparisons. Inequalities are
340 also supported as they can be represented with union of
342 if (!(code
== LT_EXPR
350 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, op_iter
, SSA_OP_ALL_USES
)
351 if (!graphite_can_represent_expr (scop_entry
, loop
, op
)
352 /* We can not handle REAL_TYPE. Failed for pr39260. */
353 || TREE_CODE (TREE_TYPE (op
)) == REAL_TYPE
)
364 /* These nodes cut a new scope. */
371 /* Returns the statement of BB that contains a harmful operation: that
372 can be a function call with side effects, the induction variables
373 are not linear with respect to SCOP_ENTRY, etc. The current open
374 scop should end before this statement. The evaluation is limited using
375 OUTERMOST_LOOP as outermost loop that may change. */
378 harmful_stmt_in_bb (basic_block scop_entry
, loop_p outer_loop
, basic_block bb
)
380 gimple_stmt_iterator gsi
;
382 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
383 if (!stmt_simple_for_scop_p (scop_entry
, outer_loop
, gsi_stmt (gsi
), bb
))
384 return gsi_stmt (gsi
);
389 /* Return true if LOOP can be represented in the polyhedral
390 representation. This is evaluated taking SCOP_ENTRY and
391 OUTERMOST_LOOP in mind. */
394 graphite_can_represent_loop (basic_block scop_entry
, loop_p loop
)
397 struct tree_niter_desc niter_desc
;
399 /* FIXME: For the moment, graphite cannot be used on loops that
400 iterate using induction variables that wrap. */
402 return number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
403 && niter_desc
.control
.no_overflow
404 && (niter
= number_of_latch_executions (loop
))
405 && !chrec_contains_undetermined (niter
)
406 && graphite_can_represent_expr (scop_entry
, loop
, niter
);
409 /* Store information needed by scopdet_* functions. */
413 /* Exit of the open scop would stop if the current BB is harmful. */
416 /* Where the next scop would start if the current BB is harmful. */
419 /* The bb or one of its children contains open loop exits. That means
420 loop exit nodes that are not surrounded by a loop dominated by bb. */
423 /* The bb or one of its children contains only structures we can handle. */
427 static struct scopdet_info
build_scops_1 (basic_block
, loop_p
,
428 vec
<sd_region
> *, loop_p
);
430 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
431 to SCOPS. TYPE is the gbb_type of BB. */
433 static struct scopdet_info
434 scopdet_basic_block_info (basic_block bb
, loop_p outermost_loop
,
435 vec
<sd_region
> *scops
, gbb_type type
)
437 loop_p loop
= bb
->loop_father
;
438 struct scopdet_info result
;
441 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
442 basic_block entry_block
= ENTRY_BLOCK_PTR
;
443 stmt
= harmful_stmt_in_bb (entry_block
, outermost_loop
, bb
);
444 result
.difficult
= (stmt
!= NULL
);
451 result
.exits
= false;
453 /* Mark bbs terminating a SESE region difficult, if they start
455 if (!single_succ_p (bb
))
456 result
.difficult
= true;
458 result
.exit
= single_succ (bb
);
463 result
.next
= single_succ (bb
);
464 result
.exits
= false;
465 result
.exit
= single_succ (bb
);
468 case GBB_LOOP_SING_EXIT_HEADER
:
470 vec
<sd_region
> regions
;
472 struct scopdet_info sinfo
;
473 edge exit_e
= single_exit (loop
);
475 sinfo
= build_scops_1 (bb
, outermost_loop
, ®ions
, loop
);
477 if (!graphite_can_represent_loop (entry_block
, loop
))
478 result
.difficult
= true;
480 result
.difficult
|= sinfo
.difficult
;
482 /* Try again with another loop level. */
484 && loop_depth (outermost_loop
) + 1 == loop_depth (loop
))
486 outermost_loop
= loop
;
491 sinfo
= scopdet_basic_block_info (bb
, outermost_loop
, scops
, type
);
494 result
.difficult
= true;
497 move_sd_regions (®ions
, scops
);
501 open_scop
.entry
= bb
;
502 open_scop
.exit
= exit_e
->dest
;
503 scops
->safe_push (open_scop
);
509 result
.exit
= exit_e
->dest
;
510 result
.next
= exit_e
->dest
;
512 /* If we do not dominate result.next, remove it. It's either
513 the EXIT_BLOCK_PTR, or another bb dominates it and will
514 call the scop detection for this bb. */
515 if (!dominated_by_p (CDI_DOMINATORS
, result
.next
, bb
))
518 if (exit_e
->src
->loop_father
!= loop
)
521 result
.exits
= false;
523 if (result
.difficult
)
524 move_sd_regions (®ions
, scops
);
532 case GBB_LOOP_MULT_EXIT_HEADER
:
534 /* XXX: For now we just do not join loops with multiple exits. If the
535 exits lead to the same bb it may be possible to join the loop. */
536 vec
<sd_region
> regions
;
538 vec
<edge
> exits
= get_loop_exit_edges (loop
);
541 build_scops_1 (bb
, loop
, ®ions
, loop
);
543 /* Scan the code dominated by this loop. This means all bbs, that are
544 are dominated by a bb in this loop, but are not part of this loop.
547 - The loop exit destination is dominated by the exit sources.
549 TODO: We miss here the more complex cases:
550 - The exit destinations are dominated by another bb inside
552 - The loop dominates bbs, that are not exit destinations. */
553 FOR_EACH_VEC_ELT (exits
, i
, e
)
554 if (e
->src
->loop_father
== loop
555 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
))
557 if (loop_outer (outermost_loop
))
558 outermost_loop
= loop_outer (outermost_loop
);
560 /* Pass loop_outer to recognize e->dest as loop header in
562 if (e
->dest
->loop_father
->header
== e
->dest
)
563 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
564 loop_outer (e
->dest
->loop_father
));
566 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
567 e
->dest
->loop_father
);
572 result
.difficult
= true;
573 result
.exits
= false;
574 move_sd_regions (®ions
, scops
);
578 case GBB_COND_HEADER
:
580 vec
<sd_region
> regions
;
582 struct scopdet_info sinfo
;
583 vec
<basic_block
> dominated
;
586 basic_block last_exit
= NULL
;
588 result
.exits
= false;
590 /* First check the successors of BB, and check if it is
591 possible to join the different branches. */
592 FOR_EACH_VEC_SAFE_ELT (bb
->succs
, i
, e
)
594 /* Ignore loop exits. They will be handled after the loop
596 if (loop_exits_to_bb_p (loop
, e
->dest
))
602 /* Do not follow edges that lead to the end of the
603 conditions block. For example, in
613 the edge from 0 => 6. Only check if all paths lead to
616 if (!single_pred_p (e
->dest
))
618 /* Check, if edge leads directly to the end of this
623 if (e
->dest
!= last_exit
)
624 result
.difficult
= true;
629 if (!dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
631 result
.difficult
= true;
635 sinfo
= build_scops_1 (e
->dest
, outermost_loop
, ®ions
, loop
);
637 result
.exits
|= sinfo
.exits
;
638 result
.difficult
|= sinfo
.difficult
;
640 /* Checks, if all branches end at the same point.
641 If that is true, the condition stays joinable.
642 Have a look at the example above. */
646 last_exit
= sinfo
.exit
;
648 if (sinfo
.exit
!= last_exit
)
649 result
.difficult
= true;
652 result
.difficult
= true;
656 result
.difficult
= true;
658 /* Join the branches of the condition if possible. */
659 if (!result
.exits
&& !result
.difficult
)
661 /* Only return a next pointer if we dominate this pointer.
662 Otherwise it will be handled by the bb dominating it. */
663 if (dominated_by_p (CDI_DOMINATORS
, last_exit
, bb
)
665 result
.next
= last_exit
;
669 result
.exit
= last_exit
;
675 /* Scan remaining bbs dominated by BB. */
676 dominated
= get_dominated_by (CDI_DOMINATORS
, bb
);
678 FOR_EACH_VEC_ELT (dominated
, i
, dom_bb
)
680 /* Ignore loop exits: they will be handled after the loop body. */
681 if (loop_depth (find_common_loop (loop
, dom_bb
->loop_father
))
688 /* Ignore the bbs processed above. */
689 if (single_pred_p (dom_bb
) && single_pred (dom_bb
) == bb
)
692 if (loop_depth (loop
) > loop_depth (dom_bb
->loop_father
))
693 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
,
696 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
, loop
);
698 result
.exits
|= sinfo
.exits
;
699 result
.difficult
= true;
703 dominated
.release ();
706 move_sd_regions (®ions
, scops
);
718 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
719 SCOPS. The analyse if a sd_region can be handled is based on the value
720 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
721 is the loop in which CURRENT is handled.
723 TODO: These functions got a little bit big. They definitely should be cleaned
726 static struct scopdet_info
727 build_scops_1 (basic_block current
, loop_p outermost_loop
,
728 vec
<sd_region
> *scops
, loop_p loop
)
730 bool in_scop
= false;
732 struct scopdet_info sinfo
;
734 /* Initialize result. */
735 struct scopdet_info result
;
736 result
.exits
= false;
737 result
.difficult
= false;
740 open_scop
.entry
= NULL
;
741 open_scop
.exit
= NULL
;
744 /* Loop over the dominance tree. If we meet a difficult bb, close
745 the current SCoP. Loop and condition header start a new layer,
746 and can only be added if all bbs in deeper layers are simple. */
747 while (current
!= NULL
)
749 sinfo
= scopdet_basic_block_info (current
, outermost_loop
, scops
,
750 get_bb_type (current
, loop
));
752 if (!in_scop
&& !(sinfo
.exits
|| sinfo
.difficult
))
754 open_scop
.entry
= current
;
755 open_scop
.exit
= NULL
;
758 else if (in_scop
&& (sinfo
.exits
|| sinfo
.difficult
))
760 open_scop
.exit
= current
;
761 scops
->safe_push (open_scop
);
765 result
.difficult
|= sinfo
.difficult
;
766 result
.exits
|= sinfo
.exits
;
768 current
= sinfo
.next
;
771 /* Try to close open_scop, if we are still in an open SCoP. */
774 open_scop
.exit
= sinfo
.exit
;
775 gcc_assert (open_scop
.exit
);
776 scops
->safe_push (open_scop
);
779 result
.exit
= sinfo
.exit
;
783 /* Checks if a bb is contained in REGION. */
786 bb_in_sd_region (basic_block bb
, sd_region
*region
)
788 return bb_in_region (bb
, region
->entry
, region
->exit
);
791 /* Returns the single entry edge of REGION, if it does not exits NULL. */
794 find_single_entry_edge (sd_region
*region
)
800 FOR_EACH_EDGE (e
, ei
, region
->entry
->preds
)
801 if (!bb_in_sd_region (e
->src
, region
))
816 /* Returns the single exit edge of REGION, if it does not exits NULL. */
819 find_single_exit_edge (sd_region
*region
)
825 FOR_EACH_EDGE (e
, ei
, region
->exit
->preds
)
826 if (bb_in_sd_region (e
->src
, region
))
841 /* Create a single entry edge for REGION. */
844 create_single_entry_edge (sd_region
*region
)
846 if (find_single_entry_edge (region
))
849 /* There are multiple predecessors for bb_3
862 There are two edges (1->3, 2->3), that point from outside into the region,
863 and another one (5->3), a loop latch, lead to bb_3.
871 | |\ (3.0 -> 3.1) = single entry edge
880 If the loop is part of the SCoP, we have to redirect the loop latches.
886 | | (3.0 -> 3.1) = entry edge
895 if (region
->entry
->loop_father
->header
!= region
->entry
896 || dominated_by_p (CDI_DOMINATORS
,
897 loop_latch_edge (region
->entry
->loop_father
)->src
,
900 edge forwarder
= split_block_after_labels (region
->entry
);
901 region
->entry
= forwarder
->dest
;
904 /* This case is never executed, as the loop headers seem always to have a
905 single edge pointing from outside into the loop. */
908 gcc_checking_assert (find_single_entry_edge (region
));
911 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
914 sd_region_without_exit (edge e
)
916 sd_region
*r
= (sd_region
*) e
->aux
;
919 return r
->exit
== NULL
;
924 /* Create a single exit edge for REGION. */
927 create_single_exit_edge (sd_region
*region
)
931 edge forwarder
= NULL
;
934 /* We create a forwarder bb (5) for all edges leaving this region
935 (3->5, 4->5). All other edges leading to the same bb, are moved
936 to a new bb (6). If these edges where part of another region (2->5)
937 we update the region->exit pointer, of this region.
939 To identify which edge belongs to which region we depend on the e->aux
940 pointer in every edge. It points to the region of the edge or to NULL,
941 if the edge is not part of any region.
943 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
944 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
949 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
950 | | \/ 3->5 no region, 4->5 no region,
952 \| / 5->6 region->exit = 6
955 Now there is only a single exit edge (5->6). */
958 forwarder
= make_forwarder_block (exit
, &sd_region_without_exit
, NULL
);
960 /* Unmark the edges, that are no longer exit edges. */
961 FOR_EACH_EDGE (e
, ei
, forwarder
->src
->preds
)
965 /* Mark the new exit edge. */
966 single_succ_edge (forwarder
->src
)->aux
= region
;
968 /* Update the exit bb of all regions, where exit edges lead to
970 FOR_EACH_EDGE (e
, ei
, forwarder
->dest
->preds
)
972 ((sd_region
*) e
->aux
)->exit
= forwarder
->dest
;
974 gcc_checking_assert (find_single_exit_edge (region
));
977 /* Unmark the exit edges of all REGIONS.
978 See comment in "create_single_exit_edge". */
981 unmark_exit_edges (vec
<sd_region
> regions
)
988 FOR_EACH_VEC_ELT (regions
, i
, s
)
989 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
994 /* Mark the exit edges of all REGIONS.
995 See comment in "create_single_exit_edge". */
998 mark_exit_edges (vec
<sd_region
> regions
)
1005 FOR_EACH_VEC_ELT (regions
, i
, s
)
1006 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1007 if (bb_in_sd_region (e
->src
, s
))
1011 /* Create for all scop regions a single entry and a single exit edge. */
1014 create_sese_edges (vec
<sd_region
> regions
)
1019 FOR_EACH_VEC_ELT (regions
, i
, s
)
1020 create_single_entry_edge (s
);
1022 mark_exit_edges (regions
);
1024 FOR_EACH_VEC_ELT (regions
, i
, s
)
1025 /* Don't handle multiple edges exiting the function. */
1026 if (!find_single_exit_edge (s
)
1027 && s
->exit
!= EXIT_BLOCK_PTR
)
1028 create_single_exit_edge (s
);
1030 unmark_exit_edges (regions
);
1032 calculate_dominance_info (CDI_DOMINATORS
);
1033 fix_loop_structure (NULL
);
1035 #ifdef ENABLE_CHECKING
1036 verify_loop_structure ();
1041 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1044 build_graphite_scops (vec
<sd_region
> regions
,
1050 FOR_EACH_VEC_ELT (regions
, i
, s
)
1052 edge entry
= find_single_entry_edge (s
);
1053 edge exit
= find_single_exit_edge (s
);
1059 scop
= new_scop (new_sese (entry
, exit
));
1060 scops
->safe_push (scop
);
1062 /* Are there overlapping SCoPs? */
1063 #ifdef ENABLE_CHECKING
1068 FOR_EACH_VEC_ELT (regions
, j
, s2
)
1070 gcc_assert (!bb_in_sd_region (s
->entry
, s2
));
1076 /* Returns true when BB contains only close phi nodes. */
1079 contains_only_close_phi_nodes (basic_block bb
)
1081 gimple_stmt_iterator gsi
;
1083 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1084 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_LABEL
)
1090 /* Print statistics for SCOP to FILE. */
1093 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
1098 long n_conditions
= 0;
1102 long n_p_conditions
= 0;
1108 gimple_stmt_iterator psi
;
1109 loop_p loop
= bb
->loop_father
;
1111 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
1115 n_p_bbs
+= bb
->count
;
1117 if (EDGE_COUNT (bb
->succs
) > 1)
1120 n_p_conditions
+= bb
->count
;
1123 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1126 n_p_stmts
+= bb
->count
;
1129 if (loop
->header
== bb
&& loop_in_sese_p (loop
, SCOP_REGION (scop
)))
1132 n_p_loops
+= bb
->count
;
1137 fprintf (file
, "\nBefore limit_scops SCoP statistics (");
1138 fprintf (file
, "BBS:%ld, ", n_bbs
);
1139 fprintf (file
, "LOOPS:%ld, ", n_loops
);
1140 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
1141 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
1142 fprintf (file
, "\nBefore limit_scops SCoP profiling statistics (");
1143 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
1144 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
1145 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
1146 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
1149 /* Print statistics for SCOPS to FILE. */
1152 print_graphite_statistics (FILE* file
, vec
<scop_p
> scops
)
1157 FOR_EACH_VEC_ELT (scops
, i
, scop
)
1158 print_graphite_scop_statistics (file
, scop
);
1161 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1171 * SCoP frontier, as this line is not surrounded by any loop. *
1175 This is necessary as scalar evolution and parameter detection need a
1176 outermost loop to initialize parameters correctly.
1178 TODO: FIX scalar evolution and parameter detection to allow more flexible
1182 limit_scops (vec
<scop_p
> *scops
)
1184 vec
<sd_region
> regions
;
1190 FOR_EACH_VEC_ELT (*scops
, i
, scop
)
1194 sese region
= SCOP_REGION (scop
);
1195 build_sese_loop_nests (region
);
1197 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), j
, loop
)
1198 if (!loop_in_sese_p (loop_outer (loop
), region
)
1199 && single_exit (loop
))
1201 sd_region open_scop
;
1202 open_scop
.entry
= loop
->header
;
1203 open_scop
.exit
= single_exit (loop
)->dest
;
1205 /* This is a hack on top of the limit_scops hack. The
1206 limit_scops hack should disappear all together. */
1207 if (single_succ_p (open_scop
.exit
)
1208 && contains_only_close_phi_nodes (open_scop
.exit
))
1209 open_scop
.exit
= single_succ_edge (open_scop
.exit
)->dest
;
1211 regions
.safe_push (open_scop
);
1215 free_scops (*scops
);
1218 create_sese_edges (regions
);
1219 build_graphite_scops (regions
, scops
);
1223 /* Returns true when P1 and P2 are close phis with the same
1227 same_close_phi_node (gimple p1
, gimple p2
)
1229 return operand_equal_p (gimple_phi_arg_def (p1
, 0),
1230 gimple_phi_arg_def (p2
, 0), 0);
1233 /* Remove the close phi node at GSI and replace its rhs with the rhs
1237 remove_duplicate_close_phi (gimple phi
, gimple_stmt_iterator
*gsi
)
1240 use_operand_p use_p
;
1241 imm_use_iterator imm_iter
;
1242 tree res
= gimple_phi_result (phi
);
1243 tree def
= gimple_phi_result (gsi_stmt (*gsi
));
1245 gcc_assert (same_close_phi_node (phi
, gsi_stmt (*gsi
)));
1247 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1249 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1250 SET_USE (use_p
, res
);
1252 update_stmt (use_stmt
);
1254 /* It is possible that we just created a duplicate close-phi
1255 for an already-processed containing loop. Check for this
1256 case and clean it up. */
1257 if (gimple_code (use_stmt
) == GIMPLE_PHI
1258 && gimple_phi_num_args (use_stmt
) == 1)
1259 make_close_phi_nodes_unique (gimple_bb (use_stmt
));
1262 remove_phi_node (gsi
, true);
1265 /* Removes all the close phi duplicates from BB. */
1268 make_close_phi_nodes_unique (basic_block bb
)
1270 gimple_stmt_iterator psi
;
1272 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1274 gimple_stmt_iterator gsi
= psi
;
1275 gimple phi
= gsi_stmt (psi
);
1277 /* At this point, PHI should be a close phi in normal form. */
1278 gcc_assert (gimple_phi_num_args (phi
) == 1);
1280 /* Iterate over the next phis and remove duplicates. */
1282 while (!gsi_end_p (gsi
))
1283 if (same_close_phi_node (phi
, gsi_stmt (gsi
)))
1284 remove_duplicate_close_phi (phi
, &gsi
);
1290 /* Transforms LOOP to the canonical loop closed SSA form. */
1293 canonicalize_loop_closed_ssa (loop_p loop
)
1295 edge e
= single_exit (loop
);
1298 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
1303 if (single_pred_p (bb
))
1305 e
= split_block_after_labels (bb
);
1306 make_close_phi_nodes_unique (e
->src
);
1310 gimple_stmt_iterator psi
;
1311 basic_block close
= split_edge (e
);
1313 e
= single_succ_edge (close
);
1315 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1317 gimple phi
= gsi_stmt (psi
);
1320 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1321 if (gimple_phi_arg_edge (phi
, i
) == e
)
1323 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
1324 use_operand_p use_p
;
1327 if (TREE_CODE (arg
) != SSA_NAME
)
1330 close_phi
= create_phi_node (NULL_TREE
, close
);
1331 res
= create_new_def_for (arg
, close_phi
,
1332 gimple_phi_result_ptr (close_phi
));
1333 add_phi_arg (close_phi
, arg
,
1334 gimple_phi_arg_edge (close_phi
, 0),
1336 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
1337 replace_exp (use_p
, res
);
1342 make_close_phi_nodes_unique (close
);
1345 /* The code above does not properly handle changes in the post dominance
1346 information (yet). */
1347 free_dominance_info (CDI_POST_DOMINATORS
);
1350 /* Converts the current loop closed SSA form to a canonical form
1351 expected by the Graphite code generation.
1353 The loop closed SSA form has the following invariant: a variable
1354 defined in a loop that is used outside the loop appears only in the
1355 phi nodes in the destination of the loop exit. These phi nodes are
1356 called close phi nodes.
1358 The canonical loop closed SSA form contains the extra invariants:
1360 - when the loop contains only one exit, the close phi nodes contain
1361 only one argument. That implies that the basic block that contains
1362 the close phi nodes has only one predecessor, that is a basic block
1365 - the basic block containing the close phi nodes does not contain
1368 - there exist only one phi node per definition in the loop.
1372 canonicalize_loop_closed_ssa_form (void)
1377 #ifdef ENABLE_CHECKING
1378 verify_loop_closed_ssa (true);
1381 FOR_EACH_LOOP (li
, loop
, 0)
1382 canonicalize_loop_closed_ssa (loop
);
1384 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1385 update_ssa (TODO_update_ssa
);
1387 #ifdef ENABLE_CHECKING
1388 verify_loop_closed_ssa (true);
1392 /* Find Static Control Parts (SCoP) in the current function and pushes
1396 build_scops (vec
<scop_p
> *scops
)
1398 struct loop
*loop
= current_loops
->tree_root
;
1399 vec
<sd_region
> regions
;
1402 canonicalize_loop_closed_ssa_form ();
1403 build_scops_1 (single_succ (ENTRY_BLOCK_PTR
), ENTRY_BLOCK_PTR
->loop_father
,
1405 create_sese_edges (regions
);
1406 build_graphite_scops (regions
, scops
);
1408 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1409 print_graphite_statistics (dump_file
, *scops
);
1411 limit_scops (scops
);
1414 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1415 fprintf (dump_file
, "\nnumber of SCoPs: %d\n",
1416 scops
? scops
->length () : 0);
1419 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1420 different colors. If there are not enough colors, paint the
1421 remaining SCoPs in gray.
1424 - "*" after the node number denotes the entry of a SCoP,
1425 - "#" after the node number denotes the exit of a SCoP,
1426 - "()" around the node number denotes the entry or the
1427 exit nodes of the SCOP. These are not part of SCoP. */
1430 dot_all_scops_1 (FILE *file
, vec
<scop_p
> scops
)
1439 /* Disable debugging while printing graph. */
1440 int tmp_dump_flags
= dump_flags
;
1443 fprintf (file
, "digraph all {\n");
1447 int part_of_scop
= false;
1449 /* Use HTML for every bb label. So we are able to print bbs
1450 which are part of two different SCoPs, with two different
1451 background colors. */
1452 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1454 fprintf (file
, "CELLSPACING=\"0\">\n");
1456 /* Select color for SCoP. */
1457 FOR_EACH_VEC_ELT (scops
, i
, scop
)
1459 sese region
= SCOP_REGION (scop
);
1460 if (bb_in_sese_p (bb
, region
)
1461 || (SESE_EXIT_BB (region
) == bb
)
1462 || (SESE_ENTRY_BB (region
) == bb
))
1475 case 3: /* purple */
1478 case 4: /* orange */
1481 case 5: /* yellow */
1521 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color
);
1523 if (!bb_in_sese_p (bb
, region
))
1524 fprintf (file
, " (");
1526 if (bb
== SESE_ENTRY_BB (region
)
1527 && bb
== SESE_EXIT_BB (region
))
1528 fprintf (file
, " %d*# ", bb
->index
);
1529 else if (bb
== SESE_ENTRY_BB (region
))
1530 fprintf (file
, " %d* ", bb
->index
);
1531 else if (bb
== SESE_EXIT_BB (region
))
1532 fprintf (file
, " %d# ", bb
->index
);
1534 fprintf (file
, " %d ", bb
->index
);
1536 if (!bb_in_sese_p (bb
,region
))
1537 fprintf (file
, ")");
1539 fprintf (file
, "</TD></TR>\n");
1540 part_of_scop
= true;
1546 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1547 fprintf (file
, " %d </TD></TR>\n", bb
->index
);
1549 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1554 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1555 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
1558 fputs ("}\n\n", file
);
1560 /* Enable debugging again. */
1561 dump_flags
= tmp_dump_flags
;
1564 /* Display all SCoPs using dotty. */
1567 dot_all_scops (vec
<scop_p
> scops
)
1569 /* When debugging, enable the following code. This cannot be used
1570 in production compilers because it calls "system". */
1573 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1574 gcc_assert (stream
);
1576 dot_all_scops_1 (stream
, scops
);
1579 x
= system ("dotty /tmp/allscops.dot &");
1581 dot_all_scops_1 (stderr
, scops
);
1585 /* Display all SCoPs using dotty. */
1588 dot_scop (scop_p scop
)
1590 vec
<scop_p
> scops
= vNULL
;
1593 scops
.safe_push (scop
);
1595 /* When debugging, enable the following code. This cannot be used
1596 in production compilers because it calls "system". */
1600 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1601 gcc_assert (stream
);
1603 dot_all_scops_1 (stream
, scops
);
1605 x
= system ("dotty /tmp/allscops.dot &");
1608 dot_all_scops_1 (stderr
, scops
);