1 /* Detection of Static Control Parts (SCoP) for Graphite.
2 Copyright (C) 2009-2014 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"
35 #include "basic-block.h"
36 #include "tree-ssa-alias.h"
37 #include "internal-fn.h"
38 #include "gimple-expr.h"
41 #include "gimple-iterator.h"
42 #include "gimple-ssa.h"
43 #include "tree-phinodes.h"
44 #include "ssa-iterators.h"
45 #include "tree-ssa-loop-manip.h"
46 #include "tree-ssa-loop-niter.h"
47 #include "tree-ssa-loop.h"
48 #include "tree-into-ssa.h"
51 #include "tree-chrec.h"
52 #include "tree-data-ref.h"
53 #include "tree-scalar-evolution.h"
54 #include "tree-pass.h"
56 #include "tree-ssa-propagate.h"
59 #include "graphite-poly.h"
60 #include "graphite-scop-detection.h"
62 /* Forward declarations. */
63 static void make_close_phi_nodes_unique (basic_block
);
65 /* The type of the analyzed basic block. */
67 typedef enum gbb_type
{
69 GBB_LOOP_SING_EXIT_HEADER
,
70 GBB_LOOP_MULT_EXIT_HEADER
,
77 /* Detect the type of BB. Loop headers are only marked, if they are
78 new. This means their loop_father is different to LAST_LOOP.
79 Otherwise they are treated like any other bb and their type can be
83 get_bb_type (basic_block bb
, struct loop
*last_loop
)
87 struct loop
*loop
= bb
->loop_father
;
89 /* Check, if we entry into a new loop. */
90 if (loop
!= last_loop
)
92 if (single_exit (loop
) != NULL
)
93 return GBB_LOOP_SING_EXIT_HEADER
;
94 else if (loop
->num
!= 0)
95 return GBB_LOOP_MULT_EXIT_HEADER
;
97 return GBB_COND_HEADER
;
100 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
101 nb_dom
= dom
.length ();
107 if (nb_dom
== 1 && single_succ_p (bb
))
110 return GBB_COND_HEADER
;
113 /* A SCoP detection region, defined using bbs as borders.
115 All control flow touching this region, comes in passing basic_block
116 ENTRY and leaves passing basic_block EXIT. By using bbs instead of
117 edges for the borders we are able to represent also regions that do
118 not have a single entry or exit edge.
120 But as they have a single entry basic_block and a single exit
121 basic_block, we are able to generate for every sd_region a single
129 / \ This region contains: {3, 4, 5, 6, 7, 8}
137 typedef struct sd_region_p
139 /* The entry bb dominates all bbs in the sd_region. It is part of
143 /* The exit bb postdominates all bbs in the sd_region, but is not
144 part of the region. */
150 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
153 move_sd_regions (vec
<sd_region
> *source
, vec
<sd_region
> *target
)
158 FOR_EACH_VEC_ELT (*source
, i
, s
)
159 target
->safe_push (*s
);
164 /* Something like "n * m" is not allowed. */
167 graphite_can_represent_init (tree e
)
169 switch (TREE_CODE (e
))
171 case POLYNOMIAL_CHREC
:
172 return graphite_can_represent_init (CHREC_LEFT (e
))
173 && graphite_can_represent_init (CHREC_RIGHT (e
));
176 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
177 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
178 && tree_fits_shwi_p (TREE_OPERAND (e
, 1));
180 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
181 && tree_fits_shwi_p (TREE_OPERAND (e
, 0));
184 case POINTER_PLUS_EXPR
:
186 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
187 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
192 case NON_LVALUE_EXPR
:
193 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
202 /* Return true when SCEV can be represented in the polyhedral model.
204 An expression can be represented, if it can be expressed as an
205 affine expression. For loops (i, j) and parameters (m, n) all
206 affine expressions are of the form:
208 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
210 1 i + 20 j + (-2) m + 25
212 Something like "i * n" or "n * m" is not allowed. */
215 graphite_can_represent_scev (tree scev
)
217 if (chrec_contains_undetermined (scev
))
220 switch (TREE_CODE (scev
))
225 case NON_LVALUE_EXPR
:
226 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0));
229 case POINTER_PLUS_EXPR
:
231 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
232 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
235 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
236 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
237 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
238 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
239 && graphite_can_represent_init (scev
)
240 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
241 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
243 case POLYNOMIAL_CHREC
:
244 /* Check for constant strides. With a non constant stride of
245 'n' we would have a value of 'iv * n'. Also check that the
246 initial value can represented: for example 'n * m' cannot be
248 if (!evolution_function_right_is_integer_cst (scev
)
249 || !graphite_can_represent_init (scev
))
251 return graphite_can_represent_scev (CHREC_LEFT (scev
));
257 /* Only affine functions can be represented. */
258 if (tree_contains_chrecs (scev
, NULL
)
259 || !scev_is_linear_expression (scev
))
266 /* Return true when EXPR can be represented in the polyhedral model.
268 This means an expression can be represented, if it is linear with
269 respect to the loops and the strides are non parametric.
270 LOOP is the place where the expr will be evaluated. SCOP_ENTRY defines the
271 entry of the region we analyse. */
274 graphite_can_represent_expr (basic_block scop_entry
, loop_p loop
,
277 tree scev
= analyze_scalar_evolution (loop
, expr
);
279 scev
= instantiate_scev (scop_entry
, loop
, scev
);
281 return graphite_can_represent_scev (scev
);
284 /* Return true if the data references of STMT can be represented by
288 stmt_has_simple_data_refs_p (loop_p outermost_loop ATTRIBUTE_UNUSED
,
295 vec
<data_reference_p
> drs
= vNULL
;
298 for (outer
= loop_containing_stmt (stmt
); outer
; outer
= loop_outer (outer
))
300 graphite_find_data_references_in_stmt (outer
,
301 loop_containing_stmt (stmt
),
304 FOR_EACH_VEC_ELT (drs
, j
, dr
)
305 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
306 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
)))
312 free_data_refs (drs
);
317 free_data_refs (drs
);
321 /* Return true only when STMT is simple enough for being handled by
322 Graphite. This depends on SCOP_ENTRY, as the parameters are
323 initialized relatively to this basic block, the linear functions
324 are initialized to OUTERMOST_LOOP and BB is the place where we try
325 to evaluate the STMT. */
328 stmt_simple_for_scop_p (basic_block scop_entry
, loop_p outermost_loop
,
329 gimple stmt
, basic_block bb
)
331 loop_p loop
= bb
->loop_father
;
333 gcc_assert (scop_entry
);
335 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
336 Calls have side-effects, except those to const or pure
338 if (gimple_has_volatile_ops (stmt
)
339 || (gimple_code (stmt
) == GIMPLE_CALL
340 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
341 || (gimple_code (stmt
) == GIMPLE_ASM
))
344 if (is_gimple_debug (stmt
))
347 if (!stmt_has_simple_data_refs_p (outermost_loop
, stmt
))
350 switch (gimple_code (stmt
))
358 /* We can handle all binary comparisons. Inequalities are
359 also supported as they can be represented with union of
361 enum tree_code code
= gimple_cond_code (stmt
);
362 if (!(code
== LT_EXPR
370 for (unsigned i
= 0; i
< 2; ++i
)
372 tree op
= gimple_op (stmt
, i
);
373 if (!graphite_can_represent_expr (scop_entry
, loop
, op
)
374 /* We can not handle REAL_TYPE. Failed for pr39260. */
375 || TREE_CODE (TREE_TYPE (op
)) == REAL_TYPE
)
387 /* These nodes cut a new scope. */
394 /* Returns the statement of BB that contains a harmful operation: that
395 can be a function call with side effects, the induction variables
396 are not linear with respect to SCOP_ENTRY, etc. The current open
397 scop should end before this statement. The evaluation is limited using
398 OUTERMOST_LOOP as outermost loop that may change. */
401 harmful_stmt_in_bb (basic_block scop_entry
, loop_p outer_loop
, basic_block bb
)
403 gimple_stmt_iterator gsi
;
405 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
406 if (!stmt_simple_for_scop_p (scop_entry
, outer_loop
, gsi_stmt (gsi
), bb
))
407 return gsi_stmt (gsi
);
412 /* Return true if LOOP can be represented in the polyhedral
413 representation. This is evaluated taking SCOP_ENTRY and
414 OUTERMOST_LOOP in mind. */
417 graphite_can_represent_loop (basic_block scop_entry
, loop_p loop
)
420 struct tree_niter_desc niter_desc
;
422 /* FIXME: For the moment, graphite cannot be used on loops that
423 iterate using induction variables that wrap. */
425 return number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
426 && niter_desc
.control
.no_overflow
427 && (niter
= number_of_latch_executions (loop
))
428 && !chrec_contains_undetermined (niter
)
429 && graphite_can_represent_expr (scop_entry
, loop
, niter
);
432 /* Store information needed by scopdet_* functions. */
436 /* Exit of the open scop would stop if the current BB is harmful. */
439 /* Where the next scop would start if the current BB is harmful. */
442 /* The bb or one of its children contains open loop exits. That means
443 loop exit nodes that are not surrounded by a loop dominated by bb. */
446 /* The bb or one of its children contains only structures we can handle. */
450 static struct scopdet_info
build_scops_1 (basic_block
, loop_p
,
451 vec
<sd_region
> *, loop_p
);
453 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
454 to SCOPS. TYPE is the gbb_type of BB. */
456 static struct scopdet_info
457 scopdet_basic_block_info (basic_block bb
, loop_p outermost_loop
,
458 vec
<sd_region
> *scops
, gbb_type type
)
460 loop_p loop
= bb
->loop_father
;
461 struct scopdet_info result
;
464 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
465 basic_block entry_block
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
466 stmt
= harmful_stmt_in_bb (entry_block
, outermost_loop
, bb
);
467 result
.difficult
= (stmt
!= NULL
);
474 result
.exits
= false;
476 /* Mark bbs terminating a SESE region difficult, if they start
477 a condition or if the block it exits to cannot be split
478 with make_forwarder_block. */
479 if (!single_succ_p (bb
)
480 || bb_has_abnormal_pred (single_succ (bb
)))
481 result
.difficult
= true;
483 result
.exit
= single_succ (bb
);
488 result
.next
= single_succ (bb
);
489 result
.exits
= false;
490 result
.exit
= single_succ (bb
);
493 case GBB_LOOP_SING_EXIT_HEADER
:
495 auto_vec
<sd_region
, 3> regions
;
496 struct scopdet_info sinfo
;
497 edge exit_e
= single_exit (loop
);
499 sinfo
= build_scops_1 (bb
, outermost_loop
, ®ions
, loop
);
501 if (!graphite_can_represent_loop (entry_block
, loop
))
502 result
.difficult
= true;
504 result
.difficult
|= sinfo
.difficult
;
506 /* Try again with another loop level. */
508 && loop_depth (outermost_loop
) + 1 == loop_depth (loop
))
510 outermost_loop
= loop
;
515 sinfo
= scopdet_basic_block_info (bb
, outermost_loop
, scops
, type
);
518 result
.difficult
= true;
521 move_sd_regions (®ions
, scops
);
525 open_scop
.entry
= bb
;
526 open_scop
.exit
= exit_e
->dest
;
527 scops
->safe_push (open_scop
);
533 result
.exit
= exit_e
->dest
;
534 result
.next
= exit_e
->dest
;
536 /* If we do not dominate result.next, remove it. It's either
537 the exit block, or another bb dominates it and will
538 call the scop detection for this bb. */
539 if (!dominated_by_p (CDI_DOMINATORS
, result
.next
, bb
))
542 if (exit_e
->src
->loop_father
!= loop
)
545 result
.exits
= false;
547 if (result
.difficult
)
548 move_sd_regions (®ions
, scops
);
556 case GBB_LOOP_MULT_EXIT_HEADER
:
558 /* XXX: For now we just do not join loops with multiple exits. If the
559 exits lead to the same bb it may be possible to join the loop. */
560 auto_vec
<sd_region
, 3> regions
;
561 vec
<edge
> exits
= get_loop_exit_edges (loop
);
564 build_scops_1 (bb
, loop
, ®ions
, loop
);
566 /* Scan the code dominated by this loop. This means all bbs, that are
567 are dominated by a bb in this loop, but are not part of this loop.
570 - The loop exit destination is dominated by the exit sources.
572 TODO: We miss here the more complex cases:
573 - The exit destinations are dominated by another bb inside
575 - The loop dominates bbs, that are not exit destinations. */
576 FOR_EACH_VEC_ELT (exits
, i
, e
)
577 if (e
->src
->loop_father
== loop
578 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
))
580 if (loop_outer (outermost_loop
))
581 outermost_loop
= loop_outer (outermost_loop
);
583 /* Pass loop_outer to recognize e->dest as loop header in
585 if (e
->dest
->loop_father
->header
== e
->dest
)
586 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
587 loop_outer (e
->dest
->loop_father
));
589 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
590 e
->dest
->loop_father
);
595 result
.difficult
= true;
596 result
.exits
= false;
597 move_sd_regions (®ions
, scops
);
601 case GBB_COND_HEADER
:
603 auto_vec
<sd_region
, 3> regions
;
604 struct scopdet_info sinfo
;
605 vec
<basic_block
> dominated
;
608 basic_block last_exit
= NULL
;
610 result
.exits
= false;
612 /* First check the successors of BB, and check if it is
613 possible to join the different branches. */
614 FOR_EACH_VEC_SAFE_ELT (bb
->succs
, i
, e
)
616 /* Ignore loop exits. They will be handled after the loop
618 if (loop_exits_to_bb_p (loop
, e
->dest
))
624 /* Do not follow edges that lead to the end of the
625 conditions block. For example, in
635 the edge from 0 => 6. Only check if all paths lead to
638 if (!single_pred_p (e
->dest
))
640 /* Check, if edge leads directly to the end of this
645 if (e
->dest
!= last_exit
)
646 result
.difficult
= true;
651 if (!dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
653 result
.difficult
= true;
657 sinfo
= build_scops_1 (e
->dest
, outermost_loop
, ®ions
, loop
);
659 result
.exits
|= sinfo
.exits
;
660 result
.difficult
|= sinfo
.difficult
;
662 /* Checks, if all branches end at the same point.
663 If that is true, the condition stays joinable.
664 Have a look at the example above. */
668 last_exit
= sinfo
.exit
;
670 if (sinfo
.exit
!= last_exit
)
671 result
.difficult
= true;
674 result
.difficult
= true;
678 result
.difficult
= true;
680 /* Join the branches of the condition if possible. */
681 if (!result
.exits
&& !result
.difficult
)
683 /* Only return a next pointer if we dominate this pointer.
684 Otherwise it will be handled by the bb dominating it. */
685 if (dominated_by_p (CDI_DOMINATORS
, last_exit
, bb
)
687 result
.next
= last_exit
;
691 result
.exit
= last_exit
;
697 /* Scan remaining bbs dominated by BB. */
698 dominated
= get_dominated_by (CDI_DOMINATORS
, bb
);
700 FOR_EACH_VEC_ELT (dominated
, i
, dom_bb
)
702 /* Ignore loop exits: they will be handled after the loop body. */
703 if (loop_depth (find_common_loop (loop
, dom_bb
->loop_father
))
710 /* Ignore the bbs processed above. */
711 if (single_pred_p (dom_bb
) && single_pred (dom_bb
) == bb
)
714 if (loop_depth (loop
) > loop_depth (dom_bb
->loop_father
))
715 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
,
718 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
, loop
);
720 result
.exits
|= sinfo
.exits
;
721 result
.difficult
= true;
725 dominated
.release ();
728 move_sd_regions (®ions
, scops
);
740 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
741 SCOPS. The analyse if a sd_region can be handled is based on the value
742 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
743 is the loop in which CURRENT is handled.
745 TODO: These functions got a little bit big. They definitely should be cleaned
748 static struct scopdet_info
749 build_scops_1 (basic_block current
, loop_p outermost_loop
,
750 vec
<sd_region
> *scops
, loop_p loop
)
752 bool in_scop
= false;
754 struct scopdet_info sinfo
;
756 /* Initialize result. */
757 struct scopdet_info result
;
758 result
.exits
= false;
759 result
.difficult
= false;
762 open_scop
.entry
= NULL
;
763 open_scop
.exit
= NULL
;
766 /* Loop over the dominance tree. If we meet a difficult bb, close
767 the current SCoP. Loop and condition header start a new layer,
768 and can only be added if all bbs in deeper layers are simple. */
769 while (current
!= NULL
)
771 sinfo
= scopdet_basic_block_info (current
, outermost_loop
, scops
,
772 get_bb_type (current
, loop
));
774 if (!in_scop
&& !(sinfo
.exits
|| sinfo
.difficult
))
776 open_scop
.entry
= current
;
777 open_scop
.exit
= NULL
;
780 else if (in_scop
&& (sinfo
.exits
|| sinfo
.difficult
))
782 open_scop
.exit
= current
;
783 scops
->safe_push (open_scop
);
787 result
.difficult
|= sinfo
.difficult
;
788 result
.exits
|= sinfo
.exits
;
790 current
= sinfo
.next
;
793 /* Try to close open_scop, if we are still in an open SCoP. */
796 open_scop
.exit
= sinfo
.exit
;
797 gcc_assert (open_scop
.exit
);
798 scops
->safe_push (open_scop
);
801 result
.exit
= sinfo
.exit
;
805 /* Checks if a bb is contained in REGION. */
808 bb_in_sd_region (basic_block bb
, sd_region
*region
)
810 return bb_in_region (bb
, region
->entry
, region
->exit
);
813 /* Returns the single entry edge of REGION, if it does not exits NULL. */
816 find_single_entry_edge (sd_region
*region
)
822 FOR_EACH_EDGE (e
, ei
, region
->entry
->preds
)
823 if (!bb_in_sd_region (e
->src
, region
))
838 /* Returns the single exit edge of REGION, if it does not exits NULL. */
841 find_single_exit_edge (sd_region
*region
)
847 FOR_EACH_EDGE (e
, ei
, region
->exit
->preds
)
848 if (bb_in_sd_region (e
->src
, region
))
863 /* Create a single entry edge for REGION. */
866 create_single_entry_edge (sd_region
*region
)
868 if (find_single_entry_edge (region
))
871 /* There are multiple predecessors for bb_3
884 There are two edges (1->3, 2->3), that point from outside into the region,
885 and another one (5->3), a loop latch, lead to bb_3.
893 | |\ (3.0 -> 3.1) = single entry edge
902 If the loop is part of the SCoP, we have to redirect the loop latches.
908 | | (3.0 -> 3.1) = entry edge
917 if (region
->entry
->loop_father
->header
!= region
->entry
918 || dominated_by_p (CDI_DOMINATORS
,
919 loop_latch_edge (region
->entry
->loop_father
)->src
,
922 edge forwarder
= split_block_after_labels (region
->entry
);
923 region
->entry
= forwarder
->dest
;
926 /* This case is never executed, as the loop headers seem always to have a
927 single edge pointing from outside into the loop. */
930 gcc_checking_assert (find_single_entry_edge (region
));
933 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
936 sd_region_without_exit (edge e
)
938 sd_region
*r
= (sd_region
*) e
->aux
;
941 return r
->exit
== NULL
;
946 /* Create a single exit edge for REGION. */
949 create_single_exit_edge (sd_region
*region
)
953 edge forwarder
= NULL
;
956 /* We create a forwarder bb (5) for all edges leaving this region
957 (3->5, 4->5). All other edges leading to the same bb, are moved
958 to a new bb (6). If these edges where part of another region (2->5)
959 we update the region->exit pointer, of this region.
961 To identify which edge belongs to which region we depend on the e->aux
962 pointer in every edge. It points to the region of the edge or to NULL,
963 if the edge is not part of any region.
965 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
966 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
971 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
972 | | \/ 3->5 no region, 4->5 no region,
974 \| / 5->6 region->exit = 6
977 Now there is only a single exit edge (5->6). */
980 forwarder
= make_forwarder_block (exit
, &sd_region_without_exit
, NULL
);
982 /* Unmark the edges, that are no longer exit edges. */
983 FOR_EACH_EDGE (e
, ei
, forwarder
->src
->preds
)
987 /* Mark the new exit edge. */
988 single_succ_edge (forwarder
->src
)->aux
= region
;
990 /* Update the exit bb of all regions, where exit edges lead to
992 FOR_EACH_EDGE (e
, ei
, forwarder
->dest
->preds
)
994 ((sd_region
*) e
->aux
)->exit
= forwarder
->dest
;
996 gcc_checking_assert (find_single_exit_edge (region
));
999 /* Unmark the exit edges of all REGIONS.
1000 See comment in "create_single_exit_edge". */
1003 unmark_exit_edges (vec
<sd_region
> regions
)
1010 FOR_EACH_VEC_ELT (regions
, i
, s
)
1011 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1016 /* Mark the exit edges of all REGIONS.
1017 See comment in "create_single_exit_edge". */
1020 mark_exit_edges (vec
<sd_region
> regions
)
1027 FOR_EACH_VEC_ELT (regions
, i
, s
)
1028 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1029 if (bb_in_sd_region (e
->src
, s
))
1033 /* Create for all scop regions a single entry and a single exit edge. */
1036 create_sese_edges (vec
<sd_region
> regions
)
1041 FOR_EACH_VEC_ELT (regions
, i
, s
)
1042 create_single_entry_edge (s
);
1044 mark_exit_edges (regions
);
1046 FOR_EACH_VEC_ELT (regions
, i
, s
)
1047 /* Don't handle multiple edges exiting the function. */
1048 if (!find_single_exit_edge (s
)
1049 && s
->exit
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1050 create_single_exit_edge (s
);
1052 unmark_exit_edges (regions
);
1054 calculate_dominance_info (CDI_DOMINATORS
);
1055 fix_loop_structure (NULL
);
1057 #ifdef ENABLE_CHECKING
1058 verify_loop_structure ();
1059 verify_ssa (false, true);
1063 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1066 build_graphite_scops (vec
<sd_region
> regions
,
1072 FOR_EACH_VEC_ELT (regions
, i
, s
)
1074 edge entry
= find_single_entry_edge (s
);
1075 edge exit
= find_single_exit_edge (s
);
1081 scop
= new_scop (new_sese (entry
, exit
));
1082 scops
->safe_push (scop
);
1084 /* Are there overlapping SCoPs? */
1085 #ifdef ENABLE_CHECKING
1090 FOR_EACH_VEC_ELT (regions
, j
, s2
)
1092 gcc_assert (!bb_in_sd_region (s
->entry
, s2
));
1098 /* Returns true when BB contains only close phi nodes. */
1101 contains_only_close_phi_nodes (basic_block bb
)
1103 gimple_stmt_iterator gsi
;
1105 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1106 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_LABEL
)
1112 /* Print statistics for SCOP to FILE. */
1115 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
1120 long n_conditions
= 0;
1124 long n_p_conditions
= 0;
1128 FOR_ALL_BB_FN (bb
, cfun
)
1130 gimple_stmt_iterator psi
;
1131 loop_p loop
= bb
->loop_father
;
1133 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
1137 n_p_bbs
+= bb
->count
;
1139 if (EDGE_COUNT (bb
->succs
) > 1)
1142 n_p_conditions
+= bb
->count
;
1145 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1148 n_p_stmts
+= bb
->count
;
1151 if (loop
->header
== bb
&& loop_in_sese_p (loop
, SCOP_REGION (scop
)))
1154 n_p_loops
+= bb
->count
;
1159 fprintf (file
, "\nBefore limit_scops SCoP statistics (");
1160 fprintf (file
, "BBS:%ld, ", n_bbs
);
1161 fprintf (file
, "LOOPS:%ld, ", n_loops
);
1162 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
1163 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
1164 fprintf (file
, "\nBefore limit_scops SCoP profiling statistics (");
1165 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
1166 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
1167 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
1168 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
1171 /* Print statistics for SCOPS to FILE. */
1174 print_graphite_statistics (FILE* file
, vec
<scop_p
> scops
)
1179 FOR_EACH_VEC_ELT (scops
, i
, scop
)
1180 print_graphite_scop_statistics (file
, scop
);
1183 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1193 * SCoP frontier, as this line is not surrounded by any loop. *
1197 This is necessary as scalar evolution and parameter detection need a
1198 outermost loop to initialize parameters correctly.
1200 TODO: FIX scalar evolution and parameter detection to allow more flexible
1204 limit_scops (vec
<scop_p
> *scops
)
1206 auto_vec
<sd_region
, 3> regions
;
1211 FOR_EACH_VEC_ELT (*scops
, i
, scop
)
1215 sese region
= SCOP_REGION (scop
);
1216 build_sese_loop_nests (region
);
1218 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), j
, loop
)
1219 if (!loop_in_sese_p (loop_outer (loop
), region
)
1220 && single_exit (loop
))
1222 sd_region open_scop
;
1223 open_scop
.entry
= loop
->header
;
1224 open_scop
.exit
= single_exit (loop
)->dest
;
1226 /* This is a hack on top of the limit_scops hack. The
1227 limit_scops hack should disappear all together. */
1228 if (single_succ_p (open_scop
.exit
)
1229 && contains_only_close_phi_nodes (open_scop
.exit
))
1230 open_scop
.exit
= single_succ_edge (open_scop
.exit
)->dest
;
1232 regions
.safe_push (open_scop
);
1236 free_scops (*scops
);
1239 create_sese_edges (regions
);
1240 build_graphite_scops (regions
, scops
);
1243 /* Returns true when P1 and P2 are close phis with the same
1247 same_close_phi_node (gimple p1
, gimple p2
)
1249 return operand_equal_p (gimple_phi_arg_def (p1
, 0),
1250 gimple_phi_arg_def (p2
, 0), 0);
1253 /* Remove the close phi node at GSI and replace its rhs with the rhs
1257 remove_duplicate_close_phi (gimple phi
, gimple_stmt_iterator
*gsi
)
1260 use_operand_p use_p
;
1261 imm_use_iterator imm_iter
;
1262 tree res
= gimple_phi_result (phi
);
1263 tree def
= gimple_phi_result (gsi_stmt (*gsi
));
1265 gcc_assert (same_close_phi_node (phi
, gsi_stmt (*gsi
)));
1267 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1269 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1270 SET_USE (use_p
, res
);
1272 update_stmt (use_stmt
);
1274 /* It is possible that we just created a duplicate close-phi
1275 for an already-processed containing loop. Check for this
1276 case and clean it up. */
1277 if (gimple_code (use_stmt
) == GIMPLE_PHI
1278 && gimple_phi_num_args (use_stmt
) == 1)
1279 make_close_phi_nodes_unique (gimple_bb (use_stmt
));
1282 remove_phi_node (gsi
, true);
1285 /* Removes all the close phi duplicates from BB. */
1288 make_close_phi_nodes_unique (basic_block bb
)
1290 gimple_stmt_iterator psi
;
1292 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1294 gimple_stmt_iterator gsi
= psi
;
1295 gimple phi
= gsi_stmt (psi
);
1297 /* At this point, PHI should be a close phi in normal form. */
1298 gcc_assert (gimple_phi_num_args (phi
) == 1);
1300 /* Iterate over the next phis and remove duplicates. */
1302 while (!gsi_end_p (gsi
))
1303 if (same_close_phi_node (phi
, gsi_stmt (gsi
)))
1304 remove_duplicate_close_phi (phi
, &gsi
);
1310 /* Transforms LOOP to the canonical loop closed SSA form. */
1313 canonicalize_loop_closed_ssa (loop_p loop
)
1315 edge e
= single_exit (loop
);
1318 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
1323 if (single_pred_p (bb
))
1325 e
= split_block_after_labels (bb
);
1326 make_close_phi_nodes_unique (e
->src
);
1330 gimple_stmt_iterator psi
;
1331 basic_block close
= split_edge (e
);
1333 e
= single_succ_edge (close
);
1335 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1337 gimple phi
= gsi_stmt (psi
);
1340 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1341 if (gimple_phi_arg_edge (phi
, i
) == e
)
1343 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
1344 use_operand_p use_p
;
1347 if (TREE_CODE (arg
) != SSA_NAME
)
1350 close_phi
= create_phi_node (NULL_TREE
, close
);
1351 res
= create_new_def_for (arg
, close_phi
,
1352 gimple_phi_result_ptr (close_phi
));
1353 add_phi_arg (close_phi
, arg
,
1354 gimple_phi_arg_edge (close_phi
, 0),
1356 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
1357 replace_exp (use_p
, res
);
1362 make_close_phi_nodes_unique (close
);
1365 /* The code above does not properly handle changes in the post dominance
1366 information (yet). */
1367 free_dominance_info (CDI_POST_DOMINATORS
);
1370 /* Converts the current loop closed SSA form to a canonical form
1371 expected by the Graphite code generation.
1373 The loop closed SSA form has the following invariant: a variable
1374 defined in a loop that is used outside the loop appears only in the
1375 phi nodes in the destination of the loop exit. These phi nodes are
1376 called close phi nodes.
1378 The canonical loop closed SSA form contains the extra invariants:
1380 - when the loop contains only one exit, the close phi nodes contain
1381 only one argument. That implies that the basic block that contains
1382 the close phi nodes has only one predecessor, that is a basic block
1385 - the basic block containing the close phi nodes does not contain
1388 - there exist only one phi node per definition in the loop.
1392 canonicalize_loop_closed_ssa_form (void)
1396 #ifdef ENABLE_CHECKING
1397 verify_loop_closed_ssa (true);
1400 FOR_EACH_LOOP (loop
, 0)
1401 canonicalize_loop_closed_ssa (loop
);
1403 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1404 update_ssa (TODO_update_ssa
);
1406 #ifdef ENABLE_CHECKING
1407 verify_loop_closed_ssa (true);
1411 /* Find Static Control Parts (SCoP) in the current function and pushes
1415 build_scops (vec
<scop_p
> *scops
)
1417 struct loop
*loop
= current_loops
->tree_root
;
1418 auto_vec
<sd_region
, 3> regions
;
1420 canonicalize_loop_closed_ssa_form ();
1421 build_scops_1 (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)),
1422 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->loop_father
,
1424 create_sese_edges (regions
);
1425 build_graphite_scops (regions
, scops
);
1427 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1428 print_graphite_statistics (dump_file
, *scops
);
1430 limit_scops (scops
);
1433 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1434 fprintf (dump_file
, "\nnumber of SCoPs: %d\n",
1435 scops
? scops
->length () : 0);
1438 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1439 different colors. If there are not enough colors, paint the
1440 remaining SCoPs in gray.
1443 - "*" after the node number denotes the entry of a SCoP,
1444 - "#" after the node number denotes the exit of a SCoP,
1445 - "()" around the node number denotes the entry or the
1446 exit nodes of the SCOP. These are not part of SCoP. */
1449 dot_all_scops_1 (FILE *file
, vec
<scop_p
> scops
)
1458 /* Disable debugging while printing graph. */
1459 int tmp_dump_flags
= dump_flags
;
1462 fprintf (file
, "digraph all {\n");
1464 FOR_ALL_BB_FN (bb
, cfun
)
1466 int part_of_scop
= false;
1468 /* Use HTML for every bb label. So we are able to print bbs
1469 which are part of two different SCoPs, with two different
1470 background colors. */
1471 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1473 fprintf (file
, "CELLSPACING=\"0\">\n");
1475 /* Select color for SCoP. */
1476 FOR_EACH_VEC_ELT (scops
, i
, scop
)
1478 sese region
= SCOP_REGION (scop
);
1479 if (bb_in_sese_p (bb
, region
)
1480 || (SESE_EXIT_BB (region
) == bb
)
1481 || (SESE_ENTRY_BB (region
) == bb
))
1494 case 3: /* purple */
1497 case 4: /* orange */
1500 case 5: /* yellow */
1540 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color
);
1542 if (!bb_in_sese_p (bb
, region
))
1543 fprintf (file
, " (");
1545 if (bb
== SESE_ENTRY_BB (region
)
1546 && bb
== SESE_EXIT_BB (region
))
1547 fprintf (file
, " %d*# ", bb
->index
);
1548 else if (bb
== SESE_ENTRY_BB (region
))
1549 fprintf (file
, " %d* ", bb
->index
);
1550 else if (bb
== SESE_EXIT_BB (region
))
1551 fprintf (file
, " %d# ", bb
->index
);
1553 fprintf (file
, " %d ", bb
->index
);
1555 if (!bb_in_sese_p (bb
,region
))
1556 fprintf (file
, ")");
1558 fprintf (file
, "</TD></TR>\n");
1559 part_of_scop
= true;
1565 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1566 fprintf (file
, " %d </TD></TR>\n", bb
->index
);
1568 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1571 FOR_ALL_BB_FN (bb
, cfun
)
1573 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1574 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
1577 fputs ("}\n\n", file
);
1579 /* Enable debugging again. */
1580 dump_flags
= tmp_dump_flags
;
1583 /* Display all SCoPs using dotty. */
1586 dot_all_scops (vec
<scop_p
> scops
)
1588 /* When debugging, enable the following code. This cannot be used
1589 in production compilers because it calls "system". */
1592 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1593 gcc_assert (stream
);
1595 dot_all_scops_1 (stream
, scops
);
1598 x
= system ("dotty /tmp/allscops.dot &");
1600 dot_all_scops_1 (stderr
, scops
);
1604 /* Display all SCoPs using dotty. */
1607 dot_scop (scop_p scop
)
1609 auto_vec
<scop_p
, 1> scops
;
1612 scops
.safe_push (scop
);
1614 /* When debugging, enable the following code. This cannot be used
1615 in production compilers because it calls "system". */
1619 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1620 gcc_assert (stream
);
1622 dot_all_scops_1 (stream
, scops
);
1624 x
= system ("dotty /tmp/allscops.dot &");
1627 dot_all_scops_1 (stderr
, scops
);