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"
34 #include "tree-flow.h"
36 #include "tree-chrec.h"
37 #include "tree-data-ref.h"
38 #include "tree-scalar-evolution.h"
39 #include "tree-pass.h"
43 #include "graphite-poly.h"
44 #include "graphite-scop-detection.h"
46 /* Forward declarations. */
47 static void make_close_phi_nodes_unique (basic_block
);
49 /* The type of the analyzed basic block. */
51 typedef enum gbb_type
{
53 GBB_LOOP_SING_EXIT_HEADER
,
54 GBB_LOOP_MULT_EXIT_HEADER
,
61 /* Detect the type of BB. Loop headers are only marked, if they are
62 new. This means their loop_father is different to LAST_LOOP.
63 Otherwise they are treated like any other bb and their type can be
67 get_bb_type (basic_block bb
, struct loop
*last_loop
)
71 struct loop
*loop
= bb
->loop_father
;
73 /* Check, if we entry into a new loop. */
74 if (loop
!= last_loop
)
76 if (single_exit (loop
) != NULL
)
77 return GBB_LOOP_SING_EXIT_HEADER
;
78 else if (loop
->num
!= 0)
79 return GBB_LOOP_MULT_EXIT_HEADER
;
81 return GBB_COND_HEADER
;
84 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
85 nb_dom
= dom
.length ();
91 if (nb_dom
== 1 && single_succ_p (bb
))
94 return GBB_COND_HEADER
;
97 /* A SCoP detection region, defined using bbs as borders.
99 All control flow touching this region, comes in passing basic_block
100 ENTRY and leaves passing basic_block EXIT. By using bbs instead of
101 edges for the borders we are able to represent also regions that do
102 not have a single entry or exit edge.
104 But as they have a single entry basic_block and a single exit
105 basic_block, we are able to generate for every sd_region a single
113 / \ This region contains: {3, 4, 5, 6, 7, 8}
121 typedef struct sd_region_p
123 /* The entry bb dominates all bbs in the sd_region. It is part of
127 /* The exit bb postdominates all bbs in the sd_region, but is not
128 part of the region. */
134 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
137 move_sd_regions (vec
<sd_region
> *source
, vec
<sd_region
> *target
)
142 FOR_EACH_VEC_ELT (*source
, i
, s
)
143 target
->safe_push (*s
);
148 /* Something like "n * m" is not allowed. */
151 graphite_can_represent_init (tree e
)
153 switch (TREE_CODE (e
))
155 case POLYNOMIAL_CHREC
:
156 return graphite_can_represent_init (CHREC_LEFT (e
))
157 && graphite_can_represent_init (CHREC_RIGHT (e
));
160 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
161 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
162 && host_integerp (TREE_OPERAND (e
, 1), 0);
164 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
165 && host_integerp (TREE_OPERAND (e
, 0), 0);
168 case POINTER_PLUS_EXPR
:
170 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
171 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
176 case NON_LVALUE_EXPR
:
177 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
186 /* Return true when SCEV can be represented in the polyhedral model.
188 An expression can be represented, if it can be expressed as an
189 affine expression. For loops (i, j) and parameters (m, n) all
190 affine expressions are of the form:
192 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
194 1 i + 20 j + (-2) m + 25
196 Something like "i * n" or "n * m" is not allowed. */
199 graphite_can_represent_scev (tree scev
)
201 if (chrec_contains_undetermined (scev
))
204 switch (TREE_CODE (scev
))
209 case NON_LVALUE_EXPR
:
210 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0));
213 case POINTER_PLUS_EXPR
:
215 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
216 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
219 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
220 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
221 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
222 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
223 && graphite_can_represent_init (scev
)
224 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
225 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
227 case POLYNOMIAL_CHREC
:
228 /* Check for constant strides. With a non constant stride of
229 'n' we would have a value of 'iv * n'. Also check that the
230 initial value can represented: for example 'n * m' cannot be
232 if (!evolution_function_right_is_integer_cst (scev
)
233 || !graphite_can_represent_init (scev
))
235 return graphite_can_represent_scev (CHREC_LEFT (scev
));
241 /* Only affine functions can be represented. */
242 if (tree_contains_chrecs (scev
, NULL
)
243 || !scev_is_linear_expression (scev
))
250 /* Return true when EXPR can be represented in the polyhedral model.
252 This means an expression can be represented, if it is linear with
253 respect to the loops and the strides are non parametric.
254 LOOP is the place where the expr will be evaluated. SCOP_ENTRY defines the
255 entry of the region we analyse. */
258 graphite_can_represent_expr (basic_block scop_entry
, loop_p loop
,
261 tree scev
= analyze_scalar_evolution (loop
, expr
);
263 scev
= instantiate_scev (scop_entry
, loop
, scev
);
265 return graphite_can_represent_scev (scev
);
268 /* Return true if the data references of STMT can be represented by
272 stmt_has_simple_data_refs_p (loop_p outermost_loop ATTRIBUTE_UNUSED
,
279 vec
<data_reference_p
> drs
= vNULL
;
282 for (outer
= loop_containing_stmt (stmt
); outer
; outer
= loop_outer (outer
))
284 graphite_find_data_references_in_stmt (outer
,
285 loop_containing_stmt (stmt
),
288 FOR_EACH_VEC_ELT (drs
, j
, dr
)
289 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
290 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
)))
296 free_data_refs (drs
);
301 free_data_refs (drs
);
305 /* Return true only when STMT is simple enough for being handled by
306 Graphite. This depends on SCOP_ENTRY, as the parameters are
307 initialized relatively to this basic block, the linear functions
308 are initialized to OUTERMOST_LOOP and BB is the place where we try
309 to evaluate the STMT. */
312 stmt_simple_for_scop_p (basic_block scop_entry
, loop_p outermost_loop
,
313 gimple stmt
, basic_block bb
)
315 loop_p loop
= bb
->loop_father
;
317 gcc_assert (scop_entry
);
319 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
320 Calls have side-effects, except those to const or pure
322 if (gimple_has_volatile_ops (stmt
)
323 || (gimple_code (stmt
) == GIMPLE_CALL
324 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
325 || (gimple_code (stmt
) == GIMPLE_ASM
))
328 if (is_gimple_debug (stmt
))
331 if (!stmt_has_simple_data_refs_p (outermost_loop
, stmt
))
334 switch (gimple_code (stmt
))
342 /* We can handle all binary comparisons. Inequalities are
343 also supported as they can be represented with union of
345 enum tree_code code
= gimple_cond_code (stmt
);
346 if (!(code
== LT_EXPR
354 for (unsigned i
= 0; i
< 2; ++i
)
356 tree op
= gimple_op (stmt
, i
);
357 if (!graphite_can_represent_expr (scop_entry
, loop
, op
)
358 /* We can not handle REAL_TYPE. Failed for pr39260. */
359 || TREE_CODE (TREE_TYPE (op
)) == REAL_TYPE
)
371 /* These nodes cut a new scope. */
378 /* Returns the statement of BB that contains a harmful operation: that
379 can be a function call with side effects, the induction variables
380 are not linear with respect to SCOP_ENTRY, etc. The current open
381 scop should end before this statement. The evaluation is limited using
382 OUTERMOST_LOOP as outermost loop that may change. */
385 harmful_stmt_in_bb (basic_block scop_entry
, loop_p outer_loop
, basic_block bb
)
387 gimple_stmt_iterator gsi
;
389 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
390 if (!stmt_simple_for_scop_p (scop_entry
, outer_loop
, gsi_stmt (gsi
), bb
))
391 return gsi_stmt (gsi
);
396 /* Return true if LOOP can be represented in the polyhedral
397 representation. This is evaluated taking SCOP_ENTRY and
398 OUTERMOST_LOOP in mind. */
401 graphite_can_represent_loop (basic_block scop_entry
, loop_p loop
)
404 struct tree_niter_desc niter_desc
;
406 /* FIXME: For the moment, graphite cannot be used on loops that
407 iterate using induction variables that wrap. */
409 return number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
410 && niter_desc
.control
.no_overflow
411 && (niter
= number_of_latch_executions (loop
))
412 && !chrec_contains_undetermined (niter
)
413 && graphite_can_represent_expr (scop_entry
, loop
, niter
);
416 /* Store information needed by scopdet_* functions. */
420 /* Exit of the open scop would stop if the current BB is harmful. */
423 /* Where the next scop would start if the current BB is harmful. */
426 /* The bb or one of its children contains open loop exits. That means
427 loop exit nodes that are not surrounded by a loop dominated by bb. */
430 /* The bb or one of its children contains only structures we can handle. */
434 static struct scopdet_info
build_scops_1 (basic_block
, loop_p
,
435 vec
<sd_region
> *, loop_p
);
437 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
438 to SCOPS. TYPE is the gbb_type of BB. */
440 static struct scopdet_info
441 scopdet_basic_block_info (basic_block bb
, loop_p outermost_loop
,
442 vec
<sd_region
> *scops
, gbb_type type
)
444 loop_p loop
= bb
->loop_father
;
445 struct scopdet_info result
;
448 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
449 basic_block entry_block
= ENTRY_BLOCK_PTR
;
450 stmt
= harmful_stmt_in_bb (entry_block
, outermost_loop
, bb
);
451 result
.difficult
= (stmt
!= NULL
);
458 result
.exits
= false;
460 /* Mark bbs terminating a SESE region difficult, if they start
462 if (!single_succ_p (bb
))
463 result
.difficult
= true;
465 result
.exit
= single_succ (bb
);
470 result
.next
= single_succ (bb
);
471 result
.exits
= false;
472 result
.exit
= single_succ (bb
);
475 case GBB_LOOP_SING_EXIT_HEADER
:
477 vec
<sd_region
> regions
;
479 struct scopdet_info sinfo
;
480 edge exit_e
= single_exit (loop
);
482 sinfo
= build_scops_1 (bb
, outermost_loop
, ®ions
, loop
);
484 if (!graphite_can_represent_loop (entry_block
, loop
))
485 result
.difficult
= true;
487 result
.difficult
|= sinfo
.difficult
;
489 /* Try again with another loop level. */
491 && loop_depth (outermost_loop
) + 1 == loop_depth (loop
))
493 outermost_loop
= loop
;
498 sinfo
= scopdet_basic_block_info (bb
, outermost_loop
, scops
, type
);
501 result
.difficult
= true;
504 move_sd_regions (®ions
, scops
);
508 open_scop
.entry
= bb
;
509 open_scop
.exit
= exit_e
->dest
;
510 scops
->safe_push (open_scop
);
516 result
.exit
= exit_e
->dest
;
517 result
.next
= exit_e
->dest
;
519 /* If we do not dominate result.next, remove it. It's either
520 the EXIT_BLOCK_PTR, or another bb dominates it and will
521 call the scop detection for this bb. */
522 if (!dominated_by_p (CDI_DOMINATORS
, result
.next
, bb
))
525 if (exit_e
->src
->loop_father
!= loop
)
528 result
.exits
= false;
530 if (result
.difficult
)
531 move_sd_regions (®ions
, scops
);
539 case GBB_LOOP_MULT_EXIT_HEADER
:
541 /* XXX: For now we just do not join loops with multiple exits. If the
542 exits lead to the same bb it may be possible to join the loop. */
543 vec
<sd_region
> regions
;
545 vec
<edge
> exits
= get_loop_exit_edges (loop
);
548 build_scops_1 (bb
, loop
, ®ions
, loop
);
550 /* Scan the code dominated by this loop. This means all bbs, that are
551 are dominated by a bb in this loop, but are not part of this loop.
554 - The loop exit destination is dominated by the exit sources.
556 TODO: We miss here the more complex cases:
557 - The exit destinations are dominated by another bb inside
559 - The loop dominates bbs, that are not exit destinations. */
560 FOR_EACH_VEC_ELT (exits
, i
, e
)
561 if (e
->src
->loop_father
== loop
562 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
))
564 if (loop_outer (outermost_loop
))
565 outermost_loop
= loop_outer (outermost_loop
);
567 /* Pass loop_outer to recognize e->dest as loop header in
569 if (e
->dest
->loop_father
->header
== e
->dest
)
570 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
571 loop_outer (e
->dest
->loop_father
));
573 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
574 e
->dest
->loop_father
);
579 result
.difficult
= true;
580 result
.exits
= false;
581 move_sd_regions (®ions
, scops
);
585 case GBB_COND_HEADER
:
587 vec
<sd_region
> regions
;
589 struct scopdet_info sinfo
;
590 vec
<basic_block
> dominated
;
593 basic_block last_exit
= NULL
;
595 result
.exits
= false;
597 /* First check the successors of BB, and check if it is
598 possible to join the different branches. */
599 FOR_EACH_VEC_SAFE_ELT (bb
->succs
, i
, e
)
601 /* Ignore loop exits. They will be handled after the loop
603 if (loop_exits_to_bb_p (loop
, e
->dest
))
609 /* Do not follow edges that lead to the end of the
610 conditions block. For example, in
620 the edge from 0 => 6. Only check if all paths lead to
623 if (!single_pred_p (e
->dest
))
625 /* Check, if edge leads directly to the end of this
630 if (e
->dest
!= last_exit
)
631 result
.difficult
= true;
636 if (!dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
638 result
.difficult
= true;
642 sinfo
= build_scops_1 (e
->dest
, outermost_loop
, ®ions
, loop
);
644 result
.exits
|= sinfo
.exits
;
645 result
.difficult
|= sinfo
.difficult
;
647 /* Checks, if all branches end at the same point.
648 If that is true, the condition stays joinable.
649 Have a look at the example above. */
653 last_exit
= sinfo
.exit
;
655 if (sinfo
.exit
!= last_exit
)
656 result
.difficult
= true;
659 result
.difficult
= true;
663 result
.difficult
= true;
665 /* Join the branches of the condition if possible. */
666 if (!result
.exits
&& !result
.difficult
)
668 /* Only return a next pointer if we dominate this pointer.
669 Otherwise it will be handled by the bb dominating it. */
670 if (dominated_by_p (CDI_DOMINATORS
, last_exit
, bb
)
672 result
.next
= last_exit
;
676 result
.exit
= last_exit
;
682 /* Scan remaining bbs dominated by BB. */
683 dominated
= get_dominated_by (CDI_DOMINATORS
, bb
);
685 FOR_EACH_VEC_ELT (dominated
, i
, dom_bb
)
687 /* Ignore loop exits: they will be handled after the loop body. */
688 if (loop_depth (find_common_loop (loop
, dom_bb
->loop_father
))
695 /* Ignore the bbs processed above. */
696 if (single_pred_p (dom_bb
) && single_pred (dom_bb
) == bb
)
699 if (loop_depth (loop
) > loop_depth (dom_bb
->loop_father
))
700 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
,
703 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
, loop
);
705 result
.exits
|= sinfo
.exits
;
706 result
.difficult
= true;
710 dominated
.release ();
713 move_sd_regions (®ions
, scops
);
725 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
726 SCOPS. The analyse if a sd_region can be handled is based on the value
727 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
728 is the loop in which CURRENT is handled.
730 TODO: These functions got a little bit big. They definitely should be cleaned
733 static struct scopdet_info
734 build_scops_1 (basic_block current
, loop_p outermost_loop
,
735 vec
<sd_region
> *scops
, loop_p loop
)
737 bool in_scop
= false;
739 struct scopdet_info sinfo
;
741 /* Initialize result. */
742 struct scopdet_info result
;
743 result
.exits
= false;
744 result
.difficult
= false;
747 open_scop
.entry
= NULL
;
748 open_scop
.exit
= NULL
;
751 /* Loop over the dominance tree. If we meet a difficult bb, close
752 the current SCoP. Loop and condition header start a new layer,
753 and can only be added if all bbs in deeper layers are simple. */
754 while (current
!= NULL
)
756 sinfo
= scopdet_basic_block_info (current
, outermost_loop
, scops
,
757 get_bb_type (current
, loop
));
759 if (!in_scop
&& !(sinfo
.exits
|| sinfo
.difficult
))
761 open_scop
.entry
= current
;
762 open_scop
.exit
= NULL
;
765 else if (in_scop
&& (sinfo
.exits
|| sinfo
.difficult
))
767 open_scop
.exit
= current
;
768 scops
->safe_push (open_scop
);
772 result
.difficult
|= sinfo
.difficult
;
773 result
.exits
|= sinfo
.exits
;
775 current
= sinfo
.next
;
778 /* Try to close open_scop, if we are still in an open SCoP. */
781 open_scop
.exit
= sinfo
.exit
;
782 gcc_assert (open_scop
.exit
);
783 scops
->safe_push (open_scop
);
786 result
.exit
= sinfo
.exit
;
790 /* Checks if a bb is contained in REGION. */
793 bb_in_sd_region (basic_block bb
, sd_region
*region
)
795 return bb_in_region (bb
, region
->entry
, region
->exit
);
798 /* Returns the single entry edge of REGION, if it does not exits NULL. */
801 find_single_entry_edge (sd_region
*region
)
807 FOR_EACH_EDGE (e
, ei
, region
->entry
->preds
)
808 if (!bb_in_sd_region (e
->src
, region
))
823 /* Returns the single exit edge of REGION, if it does not exits NULL. */
826 find_single_exit_edge (sd_region
*region
)
832 FOR_EACH_EDGE (e
, ei
, region
->exit
->preds
)
833 if (bb_in_sd_region (e
->src
, region
))
848 /* Create a single entry edge for REGION. */
851 create_single_entry_edge (sd_region
*region
)
853 if (find_single_entry_edge (region
))
856 /* There are multiple predecessors for bb_3
869 There are two edges (1->3, 2->3), that point from outside into the region,
870 and another one (5->3), a loop latch, lead to bb_3.
878 | |\ (3.0 -> 3.1) = single entry edge
887 If the loop is part of the SCoP, we have to redirect the loop latches.
893 | | (3.0 -> 3.1) = entry edge
902 if (region
->entry
->loop_father
->header
!= region
->entry
903 || dominated_by_p (CDI_DOMINATORS
,
904 loop_latch_edge (region
->entry
->loop_father
)->src
,
907 edge forwarder
= split_block_after_labels (region
->entry
);
908 region
->entry
= forwarder
->dest
;
911 /* This case is never executed, as the loop headers seem always to have a
912 single edge pointing from outside into the loop. */
915 gcc_checking_assert (find_single_entry_edge (region
));
918 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
921 sd_region_without_exit (edge e
)
923 sd_region
*r
= (sd_region
*) e
->aux
;
926 return r
->exit
== NULL
;
931 /* Create a single exit edge for REGION. */
934 create_single_exit_edge (sd_region
*region
)
938 edge forwarder
= NULL
;
941 /* We create a forwarder bb (5) for all edges leaving this region
942 (3->5, 4->5). All other edges leading to the same bb, are moved
943 to a new bb (6). If these edges where part of another region (2->5)
944 we update the region->exit pointer, of this region.
946 To identify which edge belongs to which region we depend on the e->aux
947 pointer in every edge. It points to the region of the edge or to NULL,
948 if the edge is not part of any region.
950 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
951 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
956 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
957 | | \/ 3->5 no region, 4->5 no region,
959 \| / 5->6 region->exit = 6
962 Now there is only a single exit edge (5->6). */
965 forwarder
= make_forwarder_block (exit
, &sd_region_without_exit
, NULL
);
967 /* Unmark the edges, that are no longer exit edges. */
968 FOR_EACH_EDGE (e
, ei
, forwarder
->src
->preds
)
972 /* Mark the new exit edge. */
973 single_succ_edge (forwarder
->src
)->aux
= region
;
975 /* Update the exit bb of all regions, where exit edges lead to
977 FOR_EACH_EDGE (e
, ei
, forwarder
->dest
->preds
)
979 ((sd_region
*) e
->aux
)->exit
= forwarder
->dest
;
981 gcc_checking_assert (find_single_exit_edge (region
));
984 /* Unmark the exit edges of all REGIONS.
985 See comment in "create_single_exit_edge". */
988 unmark_exit_edges (vec
<sd_region
> regions
)
995 FOR_EACH_VEC_ELT (regions
, i
, s
)
996 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1001 /* Mark the exit edges of all REGIONS.
1002 See comment in "create_single_exit_edge". */
1005 mark_exit_edges (vec
<sd_region
> regions
)
1012 FOR_EACH_VEC_ELT (regions
, i
, s
)
1013 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1014 if (bb_in_sd_region (e
->src
, s
))
1018 /* Create for all scop regions a single entry and a single exit edge. */
1021 create_sese_edges (vec
<sd_region
> regions
)
1026 FOR_EACH_VEC_ELT (regions
, i
, s
)
1027 create_single_entry_edge (s
);
1029 mark_exit_edges (regions
);
1031 FOR_EACH_VEC_ELT (regions
, i
, s
)
1032 /* Don't handle multiple edges exiting the function. */
1033 if (!find_single_exit_edge (s
)
1034 && s
->exit
!= EXIT_BLOCK_PTR
)
1035 create_single_exit_edge (s
);
1037 unmark_exit_edges (regions
);
1039 calculate_dominance_info (CDI_DOMINATORS
);
1040 fix_loop_structure (NULL
);
1042 #ifdef ENABLE_CHECKING
1043 verify_loop_structure ();
1048 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1051 build_graphite_scops (vec
<sd_region
> regions
,
1057 FOR_EACH_VEC_ELT (regions
, i
, s
)
1059 edge entry
= find_single_entry_edge (s
);
1060 edge exit
= find_single_exit_edge (s
);
1066 scop
= new_scop (new_sese (entry
, exit
));
1067 scops
->safe_push (scop
);
1069 /* Are there overlapping SCoPs? */
1070 #ifdef ENABLE_CHECKING
1075 FOR_EACH_VEC_ELT (regions
, j
, s2
)
1077 gcc_assert (!bb_in_sd_region (s
->entry
, s2
));
1083 /* Returns true when BB contains only close phi nodes. */
1086 contains_only_close_phi_nodes (basic_block bb
)
1088 gimple_stmt_iterator gsi
;
1090 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1091 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_LABEL
)
1097 /* Print statistics for SCOP to FILE. */
1100 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
1105 long n_conditions
= 0;
1109 long n_p_conditions
= 0;
1115 gimple_stmt_iterator psi
;
1116 loop_p loop
= bb
->loop_father
;
1118 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
1122 n_p_bbs
+= bb
->count
;
1124 if (EDGE_COUNT (bb
->succs
) > 1)
1127 n_p_conditions
+= bb
->count
;
1130 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1133 n_p_stmts
+= bb
->count
;
1136 if (loop
->header
== bb
&& loop_in_sese_p (loop
, SCOP_REGION (scop
)))
1139 n_p_loops
+= bb
->count
;
1144 fprintf (file
, "\nBefore limit_scops SCoP statistics (");
1145 fprintf (file
, "BBS:%ld, ", n_bbs
);
1146 fprintf (file
, "LOOPS:%ld, ", n_loops
);
1147 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
1148 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
1149 fprintf (file
, "\nBefore limit_scops SCoP profiling statistics (");
1150 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
1151 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
1152 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
1153 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
1156 /* Print statistics for SCOPS to FILE. */
1159 print_graphite_statistics (FILE* file
, vec
<scop_p
> scops
)
1164 FOR_EACH_VEC_ELT (scops
, i
, scop
)
1165 print_graphite_scop_statistics (file
, scop
);
1168 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1178 * SCoP frontier, as this line is not surrounded by any loop. *
1182 This is necessary as scalar evolution and parameter detection need a
1183 outermost loop to initialize parameters correctly.
1185 TODO: FIX scalar evolution and parameter detection to allow more flexible
1189 limit_scops (vec
<scop_p
> *scops
)
1191 vec
<sd_region
> regions
;
1197 FOR_EACH_VEC_ELT (*scops
, i
, scop
)
1201 sese region
= SCOP_REGION (scop
);
1202 build_sese_loop_nests (region
);
1204 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), j
, loop
)
1205 if (!loop_in_sese_p (loop_outer (loop
), region
)
1206 && single_exit (loop
))
1208 sd_region open_scop
;
1209 open_scop
.entry
= loop
->header
;
1210 open_scop
.exit
= single_exit (loop
)->dest
;
1212 /* This is a hack on top of the limit_scops hack. The
1213 limit_scops hack should disappear all together. */
1214 if (single_succ_p (open_scop
.exit
)
1215 && contains_only_close_phi_nodes (open_scop
.exit
))
1216 open_scop
.exit
= single_succ_edge (open_scop
.exit
)->dest
;
1218 regions
.safe_push (open_scop
);
1222 free_scops (*scops
);
1225 create_sese_edges (regions
);
1226 build_graphite_scops (regions
, scops
);
1230 /* Returns true when P1 and P2 are close phis with the same
1234 same_close_phi_node (gimple p1
, gimple p2
)
1236 return operand_equal_p (gimple_phi_arg_def (p1
, 0),
1237 gimple_phi_arg_def (p2
, 0), 0);
1240 /* Remove the close phi node at GSI and replace its rhs with the rhs
1244 remove_duplicate_close_phi (gimple phi
, gimple_stmt_iterator
*gsi
)
1247 use_operand_p use_p
;
1248 imm_use_iterator imm_iter
;
1249 tree res
= gimple_phi_result (phi
);
1250 tree def
= gimple_phi_result (gsi_stmt (*gsi
));
1252 gcc_assert (same_close_phi_node (phi
, gsi_stmt (*gsi
)));
1254 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1256 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1257 SET_USE (use_p
, res
);
1259 update_stmt (use_stmt
);
1261 /* It is possible that we just created a duplicate close-phi
1262 for an already-processed containing loop. Check for this
1263 case and clean it up. */
1264 if (gimple_code (use_stmt
) == GIMPLE_PHI
1265 && gimple_phi_num_args (use_stmt
) == 1)
1266 make_close_phi_nodes_unique (gimple_bb (use_stmt
));
1269 remove_phi_node (gsi
, true);
1272 /* Removes all the close phi duplicates from BB. */
1275 make_close_phi_nodes_unique (basic_block bb
)
1277 gimple_stmt_iterator psi
;
1279 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1281 gimple_stmt_iterator gsi
= psi
;
1282 gimple phi
= gsi_stmt (psi
);
1284 /* At this point, PHI should be a close phi in normal form. */
1285 gcc_assert (gimple_phi_num_args (phi
) == 1);
1287 /* Iterate over the next phis and remove duplicates. */
1289 while (!gsi_end_p (gsi
))
1290 if (same_close_phi_node (phi
, gsi_stmt (gsi
)))
1291 remove_duplicate_close_phi (phi
, &gsi
);
1297 /* Transforms LOOP to the canonical loop closed SSA form. */
1300 canonicalize_loop_closed_ssa (loop_p loop
)
1302 edge e
= single_exit (loop
);
1305 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
1310 if (single_pred_p (bb
))
1312 e
= split_block_after_labels (bb
);
1313 make_close_phi_nodes_unique (e
->src
);
1317 gimple_stmt_iterator psi
;
1318 basic_block close
= split_edge (e
);
1320 e
= single_succ_edge (close
);
1322 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1324 gimple phi
= gsi_stmt (psi
);
1327 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1328 if (gimple_phi_arg_edge (phi
, i
) == e
)
1330 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
1331 use_operand_p use_p
;
1334 if (TREE_CODE (arg
) != SSA_NAME
)
1337 close_phi
= create_phi_node (NULL_TREE
, close
);
1338 res
= create_new_def_for (arg
, close_phi
,
1339 gimple_phi_result_ptr (close_phi
));
1340 add_phi_arg (close_phi
, arg
,
1341 gimple_phi_arg_edge (close_phi
, 0),
1343 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
1344 replace_exp (use_p
, res
);
1349 make_close_phi_nodes_unique (close
);
1352 /* The code above does not properly handle changes in the post dominance
1353 information (yet). */
1354 free_dominance_info (CDI_POST_DOMINATORS
);
1357 /* Converts the current loop closed SSA form to a canonical form
1358 expected by the Graphite code generation.
1360 The loop closed SSA form has the following invariant: a variable
1361 defined in a loop that is used outside the loop appears only in the
1362 phi nodes in the destination of the loop exit. These phi nodes are
1363 called close phi nodes.
1365 The canonical loop closed SSA form contains the extra invariants:
1367 - when the loop contains only one exit, the close phi nodes contain
1368 only one argument. That implies that the basic block that contains
1369 the close phi nodes has only one predecessor, that is a basic block
1372 - the basic block containing the close phi nodes does not contain
1375 - there exist only one phi node per definition in the loop.
1379 canonicalize_loop_closed_ssa_form (void)
1384 #ifdef ENABLE_CHECKING
1385 verify_loop_closed_ssa (true);
1388 FOR_EACH_LOOP (li
, loop
, 0)
1389 canonicalize_loop_closed_ssa (loop
);
1391 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1392 update_ssa (TODO_update_ssa
);
1394 #ifdef ENABLE_CHECKING
1395 verify_loop_closed_ssa (true);
1399 /* Find Static Control Parts (SCoP) in the current function and pushes
1403 build_scops (vec
<scop_p
> *scops
)
1405 struct loop
*loop
= current_loops
->tree_root
;
1406 vec
<sd_region
> regions
;
1409 canonicalize_loop_closed_ssa_form ();
1410 build_scops_1 (single_succ (ENTRY_BLOCK_PTR
), ENTRY_BLOCK_PTR
->loop_father
,
1412 create_sese_edges (regions
);
1413 build_graphite_scops (regions
, scops
);
1415 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1416 print_graphite_statistics (dump_file
, *scops
);
1418 limit_scops (scops
);
1421 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1422 fprintf (dump_file
, "\nnumber of SCoPs: %d\n",
1423 scops
? scops
->length () : 0);
1426 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1427 different colors. If there are not enough colors, paint the
1428 remaining SCoPs in gray.
1431 - "*" after the node number denotes the entry of a SCoP,
1432 - "#" after the node number denotes the exit of a SCoP,
1433 - "()" around the node number denotes the entry or the
1434 exit nodes of the SCOP. These are not part of SCoP. */
1437 dot_all_scops_1 (FILE *file
, vec
<scop_p
> scops
)
1446 /* Disable debugging while printing graph. */
1447 int tmp_dump_flags
= dump_flags
;
1450 fprintf (file
, "digraph all {\n");
1454 int part_of_scop
= false;
1456 /* Use HTML for every bb label. So we are able to print bbs
1457 which are part of two different SCoPs, with two different
1458 background colors. */
1459 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1461 fprintf (file
, "CELLSPACING=\"0\">\n");
1463 /* Select color for SCoP. */
1464 FOR_EACH_VEC_ELT (scops
, i
, scop
)
1466 sese region
= SCOP_REGION (scop
);
1467 if (bb_in_sese_p (bb
, region
)
1468 || (SESE_EXIT_BB (region
) == bb
)
1469 || (SESE_ENTRY_BB (region
) == bb
))
1482 case 3: /* purple */
1485 case 4: /* orange */
1488 case 5: /* yellow */
1528 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color
);
1530 if (!bb_in_sese_p (bb
, region
))
1531 fprintf (file
, " (");
1533 if (bb
== SESE_ENTRY_BB (region
)
1534 && bb
== SESE_EXIT_BB (region
))
1535 fprintf (file
, " %d*# ", bb
->index
);
1536 else if (bb
== SESE_ENTRY_BB (region
))
1537 fprintf (file
, " %d* ", bb
->index
);
1538 else if (bb
== SESE_EXIT_BB (region
))
1539 fprintf (file
, " %d# ", bb
->index
);
1541 fprintf (file
, " %d ", bb
->index
);
1543 if (!bb_in_sese_p (bb
,region
))
1544 fprintf (file
, ")");
1546 fprintf (file
, "</TD></TR>\n");
1547 part_of_scop
= true;
1553 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1554 fprintf (file
, " %d </TD></TR>\n", bb
->index
);
1556 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1561 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1562 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
1565 fputs ("}\n\n", file
);
1567 /* Enable debugging again. */
1568 dump_flags
= tmp_dump_flags
;
1571 /* Display all SCoPs using dotty. */
1574 dot_all_scops (vec
<scop_p
> scops
)
1576 /* When debugging, enable the following code. This cannot be used
1577 in production compilers because it calls "system". */
1580 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1581 gcc_assert (stream
);
1583 dot_all_scops_1 (stream
, scops
);
1586 x
= system ("dotty /tmp/allscops.dot &");
1588 dot_all_scops_1 (stderr
, scops
);
1592 /* Display all SCoPs using dotty. */
1595 dot_scop (scop_p scop
)
1597 vec
<scop_p
> scops
= vNULL
;
1600 scops
.safe_push (scop
);
1602 /* When debugging, enable the following code. This cannot be used
1603 in production compilers because it calls "system". */
1607 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1608 gcc_assert (stream
);
1610 dot_all_scops_1 (stream
, scops
);
1612 x
= system ("dotty /tmp/allscops.dot &");
1615 dot_all_scops_1 (stderr
, scops
);