1 /* Detection of Static Control Parts (SCoP) for Graphite.
2 Copyright (C) 2009, 2010 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/>. */
24 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "tree-dump.h"
35 #include "tree-chrec.h"
36 #include "tree-data-ref.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-pass.h"
40 #include "value-prof.h"
41 #include "pointer-set.h"
47 #include "graphite-ppl.h"
49 #include "graphite-poly.h"
50 #include "graphite-scop-detection.h"
52 /* The type of the analyzed basic block. */
54 typedef enum gbb_type
{
56 GBB_LOOP_SING_EXIT_HEADER
,
57 GBB_LOOP_MULT_EXIT_HEADER
,
64 /* Detect the type of BB. Loop headers are only marked, if they are
65 new. This means their loop_father is different to LAST_LOOP.
66 Otherwise they are treated like any other bb and their type can be
70 get_bb_type (basic_block bb
, struct loop
*last_loop
)
72 VEC (basic_block
, heap
) *dom
;
74 struct loop
*loop
= bb
->loop_father
;
76 /* Check, if we entry into a new loop. */
77 if (loop
!= last_loop
)
79 if (single_exit (loop
) != NULL
)
80 return GBB_LOOP_SING_EXIT_HEADER
;
81 else if (loop
->num
!= 0)
82 return GBB_LOOP_MULT_EXIT_HEADER
;
84 return GBB_COND_HEADER
;
87 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
88 nb_dom
= VEC_length (basic_block
, dom
);
89 VEC_free (basic_block
, heap
, dom
);
94 nb_suc
= VEC_length (edge
, bb
->succs
);
96 if (nb_dom
== 1 && nb_suc
== 1)
99 return GBB_COND_HEADER
;
102 /* A SCoP detection region, defined using bbs as borders.
104 All control flow touching this region, comes in passing basic_block
105 ENTRY and leaves passing basic_block EXIT. By using bbs instead of
106 edges for the borders we are able to represent also regions that do
107 not have a single entry or exit edge.
109 But as they have a single entry basic_block and a single exit
110 basic_block, we are able to generate for every sd_region a single
118 / \ This region contains: {3, 4, 5, 6, 7, 8}
126 typedef struct sd_region_p
128 /* The entry bb dominates all bbs in the sd_region. It is part of
132 /* The exit bb postdominates all bbs in the sd_region, but is not
133 part of the region. */
137 DEF_VEC_O(sd_region
);
138 DEF_VEC_ALLOC_O(sd_region
, heap
);
141 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
144 move_sd_regions (VEC (sd_region
, heap
) **source
,
145 VEC (sd_region
, heap
) **target
)
150 FOR_EACH_VEC_ELT (sd_region
, *source
, i
, s
)
151 VEC_safe_push (sd_region
, heap
, *target
, s
);
153 VEC_free (sd_region
, heap
, *source
);
156 /* Something like "n * m" is not allowed. */
159 graphite_can_represent_init (tree e
)
161 switch (TREE_CODE (e
))
163 case POLYNOMIAL_CHREC
:
164 return graphite_can_represent_init (CHREC_LEFT (e
))
165 && graphite_can_represent_init (CHREC_RIGHT (e
));
168 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
169 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
170 && host_integerp (TREE_OPERAND (e
, 1), 0);
172 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
173 && host_integerp (TREE_OPERAND (e
, 0), 0);
176 case POINTER_PLUS_EXPR
:
178 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
179 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
184 case NON_LVALUE_EXPR
:
185 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
194 /* Return true when SCEV can be represented in the polyhedral model.
196 An expression can be represented, if it can be expressed as an
197 affine expression. For loops (i, j) and parameters (m, n) all
198 affine expressions are of the form:
200 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
202 1 i + 20 j + (-2) m + 25
204 Something like "i * n" or "n * m" is not allowed. */
207 graphite_can_represent_scev (tree scev
)
209 if (chrec_contains_undetermined (scev
))
212 switch (TREE_CODE (scev
))
216 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
217 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
220 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
221 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
222 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
223 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
224 && graphite_can_represent_init (scev
)
225 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
226 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
228 case POLYNOMIAL_CHREC
:
229 /* Check for constant strides. With a non constant stride of
230 'n' we would have a value of 'iv * n'. Also check that the
231 initial value can represented: for example 'n * m' cannot be
233 if (!evolution_function_right_is_integer_cst (scev
)
234 || !graphite_can_represent_init (scev
))
241 /* Only affine functions can be represented. */
242 if (!scev_is_linear_expression (scev
))
249 /* Return true when EXPR can be represented in the polyhedral model.
251 This means an expression can be represented, if it is linear with
252 respect to the loops and the strides are non parametric.
253 LOOP is the place where the expr will be evaluated. SCOP_ENTRY defines the
254 entry of the region we analyse. */
257 graphite_can_represent_expr (basic_block scop_entry
, loop_p loop
,
260 tree scev
= analyze_scalar_evolution (loop
, expr
);
262 scev
= instantiate_scev (scop_entry
, loop
, scev
);
264 return graphite_can_represent_scev (scev
);
267 /* Return true if the data references of STMT can be represented by
271 stmt_has_simple_data_refs_p (loop_p outermost_loop
, gimple stmt
)
277 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 5);
279 graphite_find_data_references_in_stmt (outermost_loop
, stmt
, &drs
);
281 FOR_EACH_VEC_ELT (data_reference_p
, drs
, j
, dr
)
282 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
283 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
)))
290 free_data_refs (drs
);
294 /* Return true only when STMT is simple enough for being handled by
295 Graphite. This depends on SCOP_ENTRY, as the parameters are
296 initialized relatively to this basic block, the linear functions
297 are initialized to OUTERMOST_LOOP and BB is the place where we try
298 to evaluate the STMT. */
301 stmt_simple_for_scop_p (basic_block scop_entry
, loop_p outermost_loop
,
302 gimple stmt
, basic_block bb
)
304 loop_p loop
= bb
->loop_father
;
306 gcc_assert (scop_entry
);
308 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
309 Calls have side-effects, except those to const or pure
311 if (gimple_has_volatile_ops (stmt
)
312 || (gimple_code (stmt
) == GIMPLE_CALL
313 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
314 || (gimple_code (stmt
) == GIMPLE_ASM
))
317 if (is_gimple_debug (stmt
))
320 if (!stmt_has_simple_data_refs_p (outermost_loop
, stmt
))
323 switch (gimple_code (stmt
))
333 enum tree_code code
= gimple_cond_code (stmt
);
335 /* We can handle all binary comparisons. Inequalities are
336 also supported as they can be represented with union of
338 if (!(code
== LT_EXPR
346 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, op_iter
, SSA_OP_ALL_USES
)
347 if (!graphite_can_represent_expr (scop_entry
, loop
, op
)
348 /* We can not handle REAL_TYPE. Failed for pr39260. */
349 || TREE_CODE (TREE_TYPE (op
)) == REAL_TYPE
)
360 /* These nodes cut a new scope. */
367 /* Returns the statement of BB that contains a harmful operation: that
368 can be a function call with side effects, the induction variables
369 are not linear with respect to SCOP_ENTRY, etc. The current open
370 scop should end before this statement. The evaluation is limited using
371 OUTERMOST_LOOP as outermost loop that may change. */
374 harmful_stmt_in_bb (basic_block scop_entry
, loop_p outer_loop
, basic_block bb
)
376 gimple_stmt_iterator gsi
;
378 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
379 if (!stmt_simple_for_scop_p (scop_entry
, outer_loop
, gsi_stmt (gsi
), bb
))
380 return gsi_stmt (gsi
);
385 /* Return true if LOOP can be represented in the polyhedral
386 representation. This is evaluated taking SCOP_ENTRY and
387 OUTERMOST_LOOP in mind. */
390 graphite_can_represent_loop (basic_block scop_entry
, loop_p loop
)
392 tree niter
= number_of_latch_executions (loop
);
394 /* Number of iterations unknown. */
395 if (chrec_contains_undetermined (niter
))
398 /* Number of iterations not affine. */
399 if (!graphite_can_represent_expr (scop_entry
, loop
, niter
))
405 /* Store information needed by scopdet_* functions. */
409 /* Exit of the open scop would stop if the current BB is harmful. */
412 /* Where the next scop would start if the current BB is harmful. */
415 /* The bb or one of its children contains open loop exits. That means
416 loop exit nodes that are not surrounded by a loop dominated by bb. */
419 /* The bb or one of its children contains only structures we can handle. */
423 static struct scopdet_info
build_scops_1 (basic_block
, loop_p
,
424 VEC (sd_region
, heap
) **, loop_p
);
426 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
427 to SCOPS. TYPE is the gbb_type of BB. */
429 static struct scopdet_info
430 scopdet_basic_block_info (basic_block bb
, loop_p outermost_loop
,
431 VEC (sd_region
, heap
) **scops
, gbb_type type
)
433 loop_p loop
= bb
->loop_father
;
434 struct scopdet_info result
;
437 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
438 basic_block entry_block
= ENTRY_BLOCK_PTR
;
439 stmt
= harmful_stmt_in_bb (entry_block
, outermost_loop
, bb
);
440 result
.difficult
= (stmt
!= NULL
);
447 result
.exits
= false;
449 /* Mark bbs terminating a SESE region difficult, if they start
451 if (!single_succ_p (bb
))
452 result
.difficult
= true;
454 result
.exit
= single_succ (bb
);
459 result
.next
= single_succ (bb
);
460 result
.exits
= false;
461 result
.exit
= single_succ (bb
);
464 case GBB_LOOP_SING_EXIT_HEADER
:
466 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
467 struct scopdet_info sinfo
;
468 edge exit_e
= single_exit (loop
);
470 sinfo
= build_scops_1 (bb
, outermost_loop
, ®ions
, loop
);
472 if (!graphite_can_represent_loop (entry_block
, loop
))
473 result
.difficult
= true;
475 result
.difficult
|= sinfo
.difficult
;
477 /* Try again with another loop level. */
479 && loop_depth (outermost_loop
) + 1 == loop_depth (loop
))
481 outermost_loop
= loop
;
483 VEC_free (sd_region
, heap
, regions
);
484 regions
= VEC_alloc (sd_region
, heap
, 3);
486 sinfo
= scopdet_basic_block_info (bb
, outermost_loop
, scops
, type
);
489 result
.difficult
= true;
492 move_sd_regions (®ions
, scops
);
496 open_scop
.entry
= bb
;
497 open_scop
.exit
= exit_e
->dest
;
498 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
499 VEC_free (sd_region
, heap
, regions
);
504 result
.exit
= exit_e
->dest
;
505 result
.next
= exit_e
->dest
;
507 /* If we do not dominate result.next, remove it. It's either
508 the EXIT_BLOCK_PTR, or another bb dominates it and will
509 call the scop detection for this bb. */
510 if (!dominated_by_p (CDI_DOMINATORS
, result
.next
, bb
))
513 if (exit_e
->src
->loop_father
!= loop
)
516 result
.exits
= false;
518 if (result
.difficult
)
519 move_sd_regions (®ions
, scops
);
521 VEC_free (sd_region
, heap
, regions
);
527 case GBB_LOOP_MULT_EXIT_HEADER
:
529 /* XXX: For now we just do not join loops with multiple exits. If the
530 exits lead to the same bb it may be possible to join the loop. */
531 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
532 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
535 build_scops_1 (bb
, loop
, ®ions
, loop
);
537 /* Scan the code dominated by this loop. This means all bbs, that are
538 are dominated by a bb in this loop, but are not part of this loop.
541 - The loop exit destination is dominated by the exit sources.
543 TODO: We miss here the more complex cases:
544 - The exit destinations are dominated by another bb inside
546 - The loop dominates bbs, that are not exit destinations. */
547 FOR_EACH_VEC_ELT (edge
, exits
, i
, e
)
548 if (e
->src
->loop_father
== loop
549 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
))
551 if (loop_outer (outermost_loop
))
552 outermost_loop
= loop_outer (outermost_loop
);
554 /* Pass loop_outer to recognize e->dest as loop header in
556 if (e
->dest
->loop_father
->header
== e
->dest
)
557 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
558 loop_outer (e
->dest
->loop_father
));
560 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
561 e
->dest
->loop_father
);
566 result
.difficult
= true;
567 result
.exits
= false;
568 move_sd_regions (®ions
, scops
);
569 VEC_free (edge
, heap
, exits
);
572 case GBB_COND_HEADER
:
574 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
575 struct scopdet_info sinfo
;
576 VEC (basic_block
, heap
) *dominated
;
579 basic_block last_exit
= NULL
;
581 result
.exits
= false;
583 /* First check the successors of BB, and check if it is
584 possible to join the different branches. */
585 FOR_EACH_VEC_ELT (edge
, bb
->succs
, i
, e
)
587 /* Ignore loop exits. They will be handled after the loop
589 if (loop_exits_to_bb_p (loop
, e
->dest
))
595 /* Do not follow edges that lead to the end of the
596 conditions block. For example, in
606 the edge from 0 => 6. Only check if all paths lead to
609 if (!single_pred_p (e
->dest
))
611 /* Check, if edge leads directly to the end of this
616 if (e
->dest
!= last_exit
)
617 result
.difficult
= true;
622 if (!dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
624 result
.difficult
= true;
628 sinfo
= build_scops_1 (e
->dest
, outermost_loop
, ®ions
, loop
);
630 result
.exits
|= sinfo
.exits
;
631 result
.difficult
|= sinfo
.difficult
;
633 /* Checks, if all branches end at the same point.
634 If that is true, the condition stays joinable.
635 Have a look at the example above. */
639 last_exit
= sinfo
.exit
;
641 if (sinfo
.exit
!= last_exit
)
642 result
.difficult
= true;
645 result
.difficult
= true;
649 result
.difficult
= true;
651 /* Join the branches of the condition if possible. */
652 if (!result
.exits
&& !result
.difficult
)
654 /* Only return a next pointer if we dominate this pointer.
655 Otherwise it will be handled by the bb dominating it. */
656 if (dominated_by_p (CDI_DOMINATORS
, last_exit
, bb
)
658 result
.next
= last_exit
;
662 result
.exit
= last_exit
;
664 VEC_free (sd_region
, heap
, regions
);
668 /* Scan remaining bbs dominated by BB. */
669 dominated
= get_dominated_by (CDI_DOMINATORS
, bb
);
671 FOR_EACH_VEC_ELT (basic_block
, dominated
, i
, dom_bb
)
673 /* Ignore loop exits: they will be handled after the loop body. */
674 if (loop_depth (find_common_loop (loop
, dom_bb
->loop_father
))
681 /* Ignore the bbs processed above. */
682 if (single_pred_p (dom_bb
) && single_pred (dom_bb
) == bb
)
685 if (loop_depth (loop
) > loop_depth (dom_bb
->loop_father
))
686 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
,
689 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
, loop
);
691 result
.exits
|= sinfo
.exits
;
692 result
.difficult
= true;
696 VEC_free (basic_block
, heap
, dominated
);
699 move_sd_regions (®ions
, scops
);
711 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
712 SCOPS. The analyse if a sd_region can be handled is based on the value
713 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
714 is the loop in which CURRENT is handled.
716 TODO: These functions got a little bit big. They definitely should be cleaned
719 static struct scopdet_info
720 build_scops_1 (basic_block current
, loop_p outermost_loop
,
721 VEC (sd_region
, heap
) **scops
, loop_p loop
)
723 bool in_scop
= false;
725 struct scopdet_info sinfo
;
727 /* Initialize result. */
728 struct scopdet_info result
;
729 result
.exits
= false;
730 result
.difficult
= false;
733 open_scop
.entry
= NULL
;
734 open_scop
.exit
= NULL
;
737 /* Loop over the dominance tree. If we meet a difficult bb, close
738 the current SCoP. Loop and condition header start a new layer,
739 and can only be added if all bbs in deeper layers are simple. */
740 while (current
!= NULL
)
742 sinfo
= scopdet_basic_block_info (current
, outermost_loop
, scops
,
743 get_bb_type (current
, loop
));
745 if (!in_scop
&& !(sinfo
.exits
|| sinfo
.difficult
))
747 open_scop
.entry
= current
;
748 open_scop
.exit
= NULL
;
751 else if (in_scop
&& (sinfo
.exits
|| sinfo
.difficult
))
753 open_scop
.exit
= current
;
754 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
758 result
.difficult
|= sinfo
.difficult
;
759 result
.exits
|= sinfo
.exits
;
761 current
= sinfo
.next
;
764 /* Try to close open_scop, if we are still in an open SCoP. */
767 open_scop
.exit
= sinfo
.exit
;
768 gcc_assert (open_scop
.exit
);
769 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
772 result
.exit
= sinfo
.exit
;
776 /* Checks if a bb is contained in REGION. */
779 bb_in_sd_region (basic_block bb
, sd_region
*region
)
781 return bb_in_region (bb
, region
->entry
, region
->exit
);
784 /* Returns the single entry edge of REGION, if it does not exits NULL. */
787 find_single_entry_edge (sd_region
*region
)
793 FOR_EACH_EDGE (e
, ei
, region
->entry
->preds
)
794 if (!bb_in_sd_region (e
->src
, region
))
809 /* Returns the single exit edge of REGION, if it does not exits NULL. */
812 find_single_exit_edge (sd_region
*region
)
818 FOR_EACH_EDGE (e
, ei
, region
->exit
->preds
)
819 if (bb_in_sd_region (e
->src
, region
))
834 /* Create a single entry edge for REGION. */
837 create_single_entry_edge (sd_region
*region
)
839 if (find_single_entry_edge (region
))
842 /* There are multiple predecessors for bb_3
855 There are two edges (1->3, 2->3), that point from outside into the region,
856 and another one (5->3), a loop latch, lead to bb_3.
864 | |\ (3.0 -> 3.1) = single entry edge
873 If the loop is part of the SCoP, we have to redirect the loop latches.
879 | | (3.0 -> 3.1) = entry edge
888 if (region
->entry
->loop_father
->header
!= region
->entry
889 || dominated_by_p (CDI_DOMINATORS
,
890 loop_latch_edge (region
->entry
->loop_father
)->src
,
893 edge forwarder
= split_block_after_labels (region
->entry
);
894 region
->entry
= forwarder
->dest
;
897 /* This case is never executed, as the loop headers seem always to have a
898 single edge pointing from outside into the loop. */
901 gcc_checking_assert (find_single_entry_edge (region
));
904 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
907 sd_region_without_exit (edge e
)
909 sd_region
*r
= (sd_region
*) e
->aux
;
912 return r
->exit
== NULL
;
917 /* Create a single exit edge for REGION. */
920 create_single_exit_edge (sd_region
*region
)
924 edge forwarder
= NULL
;
927 /* We create a forwarder bb (5) for all edges leaving this region
928 (3->5, 4->5). All other edges leading to the same bb, are moved
929 to a new bb (6). If these edges where part of another region (2->5)
930 we update the region->exit pointer, of this region.
932 To identify which edge belongs to which region we depend on the e->aux
933 pointer in every edge. It points to the region of the edge or to NULL,
934 if the edge is not part of any region.
936 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
937 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
942 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
943 | | \/ 3->5 no region, 4->5 no region,
945 \| / 5->6 region->exit = 6
948 Now there is only a single exit edge (5->6). */
951 forwarder
= make_forwarder_block (exit
, &sd_region_without_exit
, NULL
);
953 /* Unmark the edges, that are no longer exit edges. */
954 FOR_EACH_EDGE (e
, ei
, forwarder
->src
->preds
)
958 /* Mark the new exit edge. */
959 single_succ_edge (forwarder
->src
)->aux
= region
;
961 /* Update the exit bb of all regions, where exit edges lead to
963 FOR_EACH_EDGE (e
, ei
, forwarder
->dest
->preds
)
965 ((sd_region
*) e
->aux
)->exit
= forwarder
->dest
;
967 gcc_checking_assert (find_single_exit_edge (region
));
970 /* Unmark the exit edges of all REGIONS.
971 See comment in "create_single_exit_edge". */
974 unmark_exit_edges (VEC (sd_region
, heap
) *regions
)
981 FOR_EACH_VEC_ELT (sd_region
, regions
, i
, s
)
982 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
987 /* Mark the exit edges of all REGIONS.
988 See comment in "create_single_exit_edge". */
991 mark_exit_edges (VEC (sd_region
, heap
) *regions
)
998 FOR_EACH_VEC_ELT (sd_region
, regions
, i
, s
)
999 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1000 if (bb_in_sd_region (e
->src
, s
))
1004 /* Create for all scop regions a single entry and a single exit edge. */
1007 create_sese_edges (VEC (sd_region
, heap
) *regions
)
1012 FOR_EACH_VEC_ELT (sd_region
, regions
, i
, s
)
1013 create_single_entry_edge (s
);
1015 mark_exit_edges (regions
);
1017 FOR_EACH_VEC_ELT (sd_region
, regions
, i
, s
)
1018 /* Don't handle multiple edges exiting the function. */
1019 if (!find_single_exit_edge (s
)
1020 && s
->exit
!= EXIT_BLOCK_PTR
)
1021 create_single_exit_edge (s
);
1023 unmark_exit_edges (regions
);
1025 fix_loop_structure (NULL
);
1027 #ifdef ENABLE_CHECKING
1028 verify_loop_structure ();
1029 verify_dominators (CDI_DOMINATORS
);
1034 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1037 build_graphite_scops (VEC (sd_region
, heap
) *regions
,
1038 VEC (scop_p
, heap
) **scops
)
1043 FOR_EACH_VEC_ELT (sd_region
, regions
, i
, s
)
1045 edge entry
= find_single_entry_edge (s
);
1046 edge exit
= find_single_exit_edge (s
);
1052 scop
= new_scop (new_sese (entry
, exit
));
1053 VEC_safe_push (scop_p
, heap
, *scops
, scop
);
1055 /* Are there overlapping SCoPs? */
1056 #ifdef ENABLE_CHECKING
1061 FOR_EACH_VEC_ELT (sd_region
, regions
, j
, s2
)
1063 gcc_assert (!bb_in_sd_region (s
->entry
, s2
));
1069 /* Returns true when BB contains only close phi nodes. */
1072 contains_only_close_phi_nodes (basic_block bb
)
1074 gimple_stmt_iterator gsi
;
1076 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1077 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_LABEL
)
1083 /* Print statistics for SCOP to FILE. */
1086 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
1091 long n_conditions
= 0;
1095 long n_p_conditions
= 0;
1101 gimple_stmt_iterator psi
;
1102 loop_p loop
= bb
->loop_father
;
1104 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
1108 n_p_bbs
+= bb
->count
;
1110 if (VEC_length (edge
, bb
->succs
) > 1)
1113 n_p_conditions
+= bb
->count
;
1116 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1119 n_p_stmts
+= bb
->count
;
1122 if (loop
->header
== bb
&& loop_in_sese_p (loop
, SCOP_REGION (scop
)))
1125 n_p_loops
+= bb
->count
;
1130 fprintf (file
, "\nBefore limit_scops SCoP statistics (");
1131 fprintf (file
, "BBS:%ld, ", n_bbs
);
1132 fprintf (file
, "LOOPS:%ld, ", n_loops
);
1133 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
1134 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
1135 fprintf (file
, "\nBefore limit_scops SCoP profiling statistics (");
1136 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
1137 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
1138 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
1139 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
1142 /* Print statistics for SCOPS to FILE. */
1145 print_graphite_statistics (FILE* file
, VEC (scop_p
, heap
) *scops
)
1150 FOR_EACH_VEC_ELT (scop_p
, scops
, i
, scop
)
1151 print_graphite_scop_statistics (file
, scop
);
1154 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1164 * SCoP frontier, as this line is not surrounded by any loop. *
1168 This is necessary as scalar evolution and parameter detection need a
1169 outermost loop to initialize parameters correctly.
1171 TODO: FIX scalar evolution and parameter detection to allow more flexible
1175 limit_scops (VEC (scop_p
, heap
) **scops
)
1177 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
1182 FOR_EACH_VEC_ELT (scop_p
, *scops
, i
, scop
)
1186 sese region
= SCOP_REGION (scop
);
1187 build_sese_loop_nests (region
);
1189 FOR_EACH_VEC_ELT (loop_p
, SESE_LOOP_NEST (region
), j
, loop
)
1190 if (!loop_in_sese_p (loop_outer (loop
), region
)
1191 && single_exit (loop
))
1193 sd_region open_scop
;
1194 open_scop
.entry
= loop
->header
;
1195 open_scop
.exit
= single_exit (loop
)->dest
;
1197 /* This is a hack on top of the limit_scops hack. The
1198 limit_scops hack should disappear all together. */
1199 if (single_succ_p (open_scop
.exit
)
1200 && contains_only_close_phi_nodes (open_scop
.exit
))
1201 open_scop
.exit
= single_succ_edge (open_scop
.exit
)->dest
;
1203 VEC_safe_push (sd_region
, heap
, regions
, &open_scop
);
1207 free_scops (*scops
);
1208 *scops
= VEC_alloc (scop_p
, heap
, 3);
1210 create_sese_edges (regions
);
1211 build_graphite_scops (regions
, scops
);
1212 VEC_free (sd_region
, heap
, regions
);
1215 /* Transforms LOOP to the canonical loop closed SSA form. */
1218 canonicalize_loop_closed_ssa (loop_p loop
)
1220 edge e
= single_exit (loop
);
1223 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
1228 if (VEC_length (edge
, bb
->preds
) == 1)
1229 split_block_after_labels (bb
);
1232 gimple_stmt_iterator psi
;
1233 basic_block close
= split_edge (e
);
1235 e
= single_succ_edge (close
);
1237 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1239 gimple phi
= gsi_stmt (psi
);
1242 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1243 if (gimple_phi_arg_edge (phi
, i
) == e
)
1245 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
1246 use_operand_p use_p
;
1249 if (TREE_CODE (arg
) != SSA_NAME
)
1252 close_phi
= create_phi_node (arg
, close
);
1253 res
= create_new_def_for (gimple_phi_result (close_phi
),
1255 gimple_phi_result_ptr (close_phi
));
1256 add_phi_arg (close_phi
, arg
,
1257 gimple_phi_arg_edge (close_phi
, 0),
1259 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
1260 replace_exp (use_p
, res
);
1267 /* Converts the current loop closed SSA form to a canonical form
1268 expected by the Graphite code generation.
1270 The loop closed SSA form has the following invariant: a variable
1271 defined in a loop that is used outside the loop appears only in the
1272 phi nodes in the destination of the loop exit. These phi nodes are
1273 called close phi nodes.
1275 The canonical loop closed SSA form contains the extra invariants:
1277 - when the loop contains only one exit, the close phi nodes contain
1278 only one argument. That implies that the basic block that contains
1279 the close phi nodes has only one predecessor, that is a basic block
1282 - the basic block containing the close phi nodes does not contain
1287 canonicalize_loop_closed_ssa_form (void)
1292 #ifdef ENABLE_CHECKING
1293 verify_loop_closed_ssa (true);
1296 FOR_EACH_LOOP (li
, loop
, 0)
1297 canonicalize_loop_closed_ssa (loop
);
1299 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1300 update_ssa (TODO_update_ssa
);
1302 #ifdef ENABLE_CHECKING
1303 verify_loop_closed_ssa (true);
1307 /* Find Static Control Parts (SCoP) in the current function and pushes
1311 build_scops (VEC (scop_p
, heap
) **scops
)
1313 struct loop
*loop
= current_loops
->tree_root
;
1314 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
1316 canonicalize_loop_closed_ssa_form ();
1317 build_scops_1 (single_succ (ENTRY_BLOCK_PTR
), ENTRY_BLOCK_PTR
->loop_father
,
1319 create_sese_edges (regions
);
1320 build_graphite_scops (regions
, scops
);
1322 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1323 print_graphite_statistics (dump_file
, *scops
);
1325 limit_scops (scops
);
1326 VEC_free (sd_region
, heap
, regions
);
1328 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1329 fprintf (dump_file
, "\nnumber of SCoPs: %d\n",
1330 VEC_length (scop_p
, *scops
));
1333 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1334 different colors. If there are not enough colors, paint the
1335 remaining SCoPs in gray.
1338 - "*" after the node number denotes the entry of a SCoP,
1339 - "#" after the node number denotes the exit of a SCoP,
1340 - "()" around the node number denotes the entry or the
1341 exit nodes of the SCOP. These are not part of SCoP. */
1344 dot_all_scops_1 (FILE *file
, VEC (scop_p
, heap
) *scops
)
1353 /* Disable debugging while printing graph. */
1354 int tmp_dump_flags
= dump_flags
;
1357 fprintf (file
, "digraph all {\n");
1361 int part_of_scop
= false;
1363 /* Use HTML for every bb label. So we are able to print bbs
1364 which are part of two different SCoPs, with two different
1365 background colors. */
1366 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1368 fprintf (file
, "CELLSPACING=\"0\">\n");
1370 /* Select color for SCoP. */
1371 FOR_EACH_VEC_ELT (scop_p
, scops
, i
, scop
)
1373 sese region
= SCOP_REGION (scop
);
1374 if (bb_in_sese_p (bb
, region
)
1375 || (SESE_EXIT_BB (region
) == bb
)
1376 || (SESE_ENTRY_BB (region
) == bb
))
1389 case 3: /* purple */
1392 case 4: /* orange */
1395 case 5: /* yellow */
1435 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color
);
1437 if (!bb_in_sese_p (bb
, region
))
1438 fprintf (file
, " (");
1440 if (bb
== SESE_ENTRY_BB (region
)
1441 && bb
== SESE_EXIT_BB (region
))
1442 fprintf (file
, " %d*# ", bb
->index
);
1443 else if (bb
== SESE_ENTRY_BB (region
))
1444 fprintf (file
, " %d* ", bb
->index
);
1445 else if (bb
== SESE_EXIT_BB (region
))
1446 fprintf (file
, " %d# ", bb
->index
);
1448 fprintf (file
, " %d ", bb
->index
);
1450 if (!bb_in_sese_p (bb
,region
))
1451 fprintf (file
, ")");
1453 fprintf (file
, "</TD></TR>\n");
1454 part_of_scop
= true;
1460 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1461 fprintf (file
, " %d </TD></TR>\n", bb
->index
);
1463 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1468 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1469 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
1472 fputs ("}\n\n", file
);
1474 /* Enable debugging again. */
1475 dump_flags
= tmp_dump_flags
;
1478 /* Display all SCoPs using dotty. */
1481 dot_all_scops (VEC (scop_p
, heap
) *scops
)
1483 /* When debugging, enable the following code. This cannot be used
1484 in production compilers because it calls "system". */
1487 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1488 gcc_assert (stream
);
1490 dot_all_scops_1 (stream
, scops
);
1493 x
= system ("dotty /tmp/allscops.dot &");
1495 dot_all_scops_1 (stderr
, scops
);
1499 /* Display all SCoPs using dotty. */
1502 dot_scop (scop_p scop
)
1504 VEC (scop_p
, heap
) *scops
= NULL
;
1507 VEC_safe_push (scop_p
, heap
, scops
, scop
);
1509 /* When debugging, enable the following code. This cannot be used
1510 in production compilers because it calls "system". */
1514 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1515 gcc_assert (stream
);
1517 dot_all_scops_1 (stream
, scops
);
1519 x
= system ("dotty /tmp/allscops.dot &");
1522 dot_all_scops_1 (stderr
, scops
);
1525 VEC_free (scop_p
, heap
, scops
);