1 /* Detection of Static Control Parts (SCoP) for Graphite.
2 Copyright (C) 2009 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"
33 #include "tree-dump.h"
36 #include "tree-chrec.h"
37 #include "tree-data-ref.h"
38 #include "tree-scalar-evolution.h"
39 #include "tree-pass.h"
41 #include "value-prof.h"
42 #include "pointer-set.h"
47 #include "cloog/cloog.h"
49 #include "graphite-ppl.h"
51 #include "graphite-poly.h"
52 #include "graphite-scop-detection.h"
54 /* The type of the analyzed basic block. */
56 typedef enum gbb_type
{
58 GBB_LOOP_SING_EXIT_HEADER
,
59 GBB_LOOP_MULT_EXIT_HEADER
,
66 /* Detect the type of BB. Loop headers are only marked, if they are
67 new. This means their loop_father is different to LAST_LOOP.
68 Otherwise they are treated like any other bb and their type can be
72 get_bb_type (basic_block bb
, struct loop
*last_loop
)
74 VEC (basic_block
, heap
) *dom
;
76 struct loop
*loop
= bb
->loop_father
;
78 /* Check, if we entry into a new loop. */
79 if (loop
!= last_loop
)
81 if (single_exit (loop
) != NULL
)
82 return GBB_LOOP_SING_EXIT_HEADER
;
83 else if (loop
->num
!= 0)
84 return GBB_LOOP_MULT_EXIT_HEADER
;
86 return GBB_COND_HEADER
;
89 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
90 nb_dom
= VEC_length (basic_block
, dom
);
91 VEC_free (basic_block
, heap
, dom
);
96 nb_suc
= VEC_length (edge
, bb
->succs
);
98 if (nb_dom
== 1 && nb_suc
== 1)
101 return GBB_COND_HEADER
;
104 /* A SCoP detection region, defined using bbs as borders.
106 All control flow touching this region, comes in passing basic_block
107 ENTRY and leaves passing basic_block EXIT. By using bbs instead of
108 edges for the borders we are able to represent also regions that do
109 not have a single entry or exit edge.
111 But as they have a single entry basic_block and a single exit
112 basic_block, we are able to generate for every sd_region a single
120 / \ This region contains: {3, 4, 5, 6, 7, 8}
128 typedef struct sd_region_p
130 /* The entry bb dominates all bbs in the sd_region. It is part of
134 /* The exit bb postdominates all bbs in the sd_region, but is not
135 part of the region. */
139 DEF_VEC_O(sd_region
);
140 DEF_VEC_ALLOC_O(sd_region
, heap
);
143 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
146 move_sd_regions (VEC (sd_region
, heap
) **source
,
147 VEC (sd_region
, heap
) **target
)
152 for (i
= 0; VEC_iterate (sd_region
, *source
, i
, s
); i
++)
153 VEC_safe_push (sd_region
, heap
, *target
, s
);
155 VEC_free (sd_region
, heap
, *source
);
158 /* Something like "n * m" is not allowed. */
161 graphite_can_represent_init (tree e
)
163 switch (TREE_CODE (e
))
165 case POLYNOMIAL_CHREC
:
166 return graphite_can_represent_init (CHREC_LEFT (e
))
167 && graphite_can_represent_init (CHREC_RIGHT (e
));
170 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
171 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
172 && host_integerp (TREE_OPERAND (e
, 1), 0);
174 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
175 && host_integerp (TREE_OPERAND (e
, 0), 0);
178 case POINTER_PLUS_EXPR
:
180 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
181 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
186 case NON_LVALUE_EXPR
:
187 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
196 /* Return true when SCEV can be represented in the polyhedral model.
198 An expression can be represented, if it can be expressed as an
199 affine expression. For loops (i, j) and parameters (m, n) all
200 affine expressions are of the form:
202 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
204 1 i + 20 j + (-2) m + 25
206 Something like "i * n" or "n * m" is not allowed.
208 OUTERMOST_LOOP defines the outermost loop that can variate. */
211 graphite_can_represent_scev (tree scev
, int outermost_loop
)
213 if (chrec_contains_undetermined (scev
))
216 switch (TREE_CODE (scev
))
220 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0), outermost_loop
)
221 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1), outermost_loop
);
224 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
225 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
226 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
227 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
228 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0), outermost_loop
)
229 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1), outermost_loop
);
231 case POLYNOMIAL_CHREC
:
232 /* Check for constant strides. With a non constant stride of
233 'n' we would have a value of 'iv * n'. Also check that the
234 initial value can represented: for example 'n * m' cannot be
236 if (!evolution_function_right_is_integer_cst (scev
)
237 || !graphite_can_represent_init (scev
))
244 /* Only affine functions can be represented. */
245 if (!scev_is_linear_expression (scev
))
248 return evolution_function_is_invariant_p (scev
, outermost_loop
)
249 || evolution_function_is_affine_multivariate_p (scev
, outermost_loop
);
253 /* Return true when EXPR can be represented in the polyhedral model.
255 This means an expression can be represented, if it is linear with
256 respect to the loops and the strides are non parametric.
257 LOOP is the place where the expr will be evaluated and OUTERMOST_LOOP
258 defindes the outermost loop that can variate. SCOP_ENTRY defines the
259 entry of the region we analyse. */
262 graphite_can_represent_expr (basic_block scop_entry
, loop_p loop
,
263 loop_p outermost_loop
, tree expr
)
265 tree scev
= analyze_scalar_evolution (loop
, expr
);
267 scev
= instantiate_scev (scop_entry
, loop
, scev
);
269 return graphite_can_represent_scev (scev
, outermost_loop
->num
);
272 /* Return true if the data references of STMT can be represented by
276 stmt_has_simple_data_refs_p (loop_p outermost_loop
, gimple stmt
)
282 int loop
= outermost_loop
->num
;
283 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 5);
285 graphite_find_data_references_in_stmt (outermost_loop
, stmt
, &drs
);
287 for (j
= 0; VEC_iterate (data_reference_p
, drs
, j
, dr
); j
++)
288 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
289 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
), loop
))
296 free_data_refs (drs
);
300 /* Return true only when STMT is simple enough for being handled by
301 Graphite. This depends on SCOP_ENTRY, as the parameters are
302 initialized relatively to this basic block, the linear functions
303 are initialized to OUTERMOST_LOOP and BB is the place where we try
304 to evaluate the STMT. */
307 stmt_simple_for_scop_p (basic_block scop_entry
, loop_p outermost_loop
,
308 gimple stmt
, basic_block bb
)
310 loop_p loop
= bb
->loop_father
;
312 gcc_assert (scop_entry
);
314 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
315 Calls have side-effects, except those to const or pure
317 if (gimple_has_volatile_ops (stmt
)
318 || (gimple_code (stmt
) == GIMPLE_CALL
319 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
320 || (gimple_code (stmt
) == GIMPLE_ASM
))
323 if (is_gimple_debug (stmt
))
326 if (!stmt_has_simple_data_refs_p (outermost_loop
, stmt
))
329 switch (gimple_code (stmt
))
339 enum tree_code code
= gimple_cond_code (stmt
);
341 /* We can handle all binary comparisons. Inequalities are
342 also supported as they can be represented with union of
344 if (!(code
== LT_EXPR
352 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, op_iter
, SSA_OP_ALL_USES
)
353 if (!graphite_can_represent_expr (scop_entry
, loop
, outermost_loop
,
355 /* We can not handle REAL_TYPE. Failed for pr39260. */
356 || TREE_CODE (TREE_TYPE (op
)) == REAL_TYPE
)
367 /* These nodes cut a new scope. */
374 /* Returns the statement of BB that contains a harmful operation: that
375 can be a function call with side effects, the induction variables
376 are not linear with respect to SCOP_ENTRY, etc. The current open
377 scop should end before this statement. The evaluation is limited using
378 OUTERMOST_LOOP as outermost loop that may change. */
381 harmful_stmt_in_bb (basic_block scop_entry
, loop_p outer_loop
, basic_block bb
)
383 gimple_stmt_iterator gsi
;
385 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
386 if (!stmt_simple_for_scop_p (scop_entry
, outer_loop
, gsi_stmt (gsi
), bb
))
387 return gsi_stmt (gsi
);
392 /* Return true when it is not possible to represent LOOP in the
393 polyhedral representation. This is evaluated taking SCOP_ENTRY and
394 OUTERMOST_LOOP in mind. */
397 graphite_can_represent_loop (basic_block scop_entry
, loop_p outermost_loop
,
400 tree niter
= number_of_latch_executions (loop
);
402 /* Number of iterations unknown. */
403 if (chrec_contains_undetermined (niter
))
406 /* Number of iterations not affine. */
407 if (!graphite_can_represent_expr (scop_entry
, loop
, outermost_loop
, niter
))
413 /* Store information needed by scopdet_* functions. */
417 /* Exit of the open scop would stop if the current BB is harmful. */
420 /* Where the next scop would start if the current BB is harmful. */
423 /* The bb or one of its children contains open loop exits. That means
424 loop exit nodes that are not surrounded by a loop dominated by bb. */
427 /* The bb or one of its children contains only structures we can handle. */
431 static struct scopdet_info
build_scops_1 (basic_block
, loop_p
,
432 VEC (sd_region
, heap
) **, loop_p
);
434 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
435 to SCOPS. TYPE is the gbb_type of BB. */
437 static struct scopdet_info
438 scopdet_basic_block_info (basic_block bb
, loop_p outermost_loop
,
439 VEC (sd_region
, heap
) **scops
, gbb_type type
)
441 loop_p loop
= bb
->loop_father
;
442 struct scopdet_info result
;
445 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
446 basic_block entry_block
= ENTRY_BLOCK_PTR
;
447 stmt
= harmful_stmt_in_bb (entry_block
, outermost_loop
, bb
);
448 result
.difficult
= (stmt
!= NULL
);
455 result
.exits
= false;
457 /* Mark bbs terminating a SESE region difficult, if they start
459 if (!single_succ_p (bb
))
460 result
.difficult
= true;
462 result
.exit
= single_succ (bb
);
467 result
.next
= single_succ (bb
);
468 result
.exits
= false;
469 result
.exit
= single_succ (bb
);
472 case GBB_LOOP_SING_EXIT_HEADER
:
474 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
475 struct scopdet_info sinfo
;
476 edge exit_e
= single_exit (loop
);
478 sinfo
= build_scops_1 (bb
, outermost_loop
, ®ions
, loop
);
480 if (!graphite_can_represent_loop (entry_block
, outermost_loop
, loop
))
481 result
.difficult
= true;
483 result
.difficult
|= sinfo
.difficult
;
485 /* Try again with another loop level. */
487 && loop_depth (outermost_loop
) + 1 == loop_depth (loop
))
489 outermost_loop
= loop
;
491 VEC_free (sd_region
, heap
, regions
);
492 regions
= VEC_alloc (sd_region
, heap
, 3);
494 sinfo
= scopdet_basic_block_info (bb
, outermost_loop
, scops
, type
);
497 result
.difficult
= true;
500 move_sd_regions (®ions
, scops
);
504 open_scop
.entry
= bb
;
505 open_scop
.exit
= exit_e
->dest
;
506 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
507 VEC_free (sd_region
, heap
, regions
);
512 result
.exit
= exit_e
->dest
;
513 result
.next
= exit_e
->dest
;
515 /* If we do not dominate result.next, remove it. It's either
516 the EXIT_BLOCK_PTR, or another bb dominates it and will
517 call the scop detection for this bb. */
518 if (!dominated_by_p (CDI_DOMINATORS
, result
.next
, bb
))
521 if (exit_e
->src
->loop_father
!= loop
)
524 result
.exits
= false;
526 if (result
.difficult
)
527 move_sd_regions (®ions
, scops
);
529 VEC_free (sd_region
, heap
, regions
);
535 case GBB_LOOP_MULT_EXIT_HEADER
:
537 /* XXX: For now we just do not join loops with multiple exits. If the
538 exits lead to the same bb it may be possible to join the loop. */
539 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
540 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
543 build_scops_1 (bb
, loop
, ®ions
, loop
);
545 /* Scan the code dominated by this loop. This means all bbs, that are
546 are dominated by a bb in this loop, but are not part of this loop.
549 - The loop exit destination is dominated by the exit sources.
551 TODO: We miss here the more complex cases:
552 - The exit destinations are dominated by another bb inside
554 - The loop dominates bbs, that are not exit destinations. */
555 for (i
= 0; VEC_iterate (edge
, exits
, i
, e
); i
++)
556 if (e
->src
->loop_father
== loop
557 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
))
559 if (loop_outer (outermost_loop
))
560 outermost_loop
= loop_outer (outermost_loop
);
562 /* Pass loop_outer to recognize e->dest as loop header in
564 if (e
->dest
->loop_father
->header
== e
->dest
)
565 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
566 loop_outer (e
->dest
->loop_father
));
568 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
569 e
->dest
->loop_father
);
574 result
.difficult
= true;
575 result
.exits
= false;
576 move_sd_regions (®ions
, scops
);
577 VEC_free (edge
, heap
, exits
);
580 case GBB_COND_HEADER
:
582 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
583 struct scopdet_info sinfo
;
584 VEC (basic_block
, heap
) *dominated
;
587 basic_block last_exit
= NULL
;
589 result
.exits
= false;
591 /* First check the successors of BB, and check if it is
592 possible to join the different branches. */
593 for (i
= 0; VEC_iterate (edge
, bb
->succs
, i
, e
); i
++)
595 /* Ignore loop exits. They will be handled after the loop
597 if (is_loop_exit (loop
, e
->dest
))
603 /* Do not follow edges that lead to the end of the
604 conditions block. For example, in
614 the edge from 0 => 6. Only check if all paths lead to
617 if (!single_pred_p (e
->dest
))
619 /* Check, if edge leads directly to the end of this
624 if (e
->dest
!= last_exit
)
625 result
.difficult
= true;
630 if (!dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
632 result
.difficult
= true;
636 sinfo
= build_scops_1 (e
->dest
, outermost_loop
, ®ions
, loop
);
638 result
.exits
|= sinfo
.exits
;
639 result
.difficult
|= sinfo
.difficult
;
641 /* Checks, if all branches end at the same point.
642 If that is true, the condition stays joinable.
643 Have a look at the example above. */
647 last_exit
= sinfo
.exit
;
649 if (sinfo
.exit
!= last_exit
)
650 result
.difficult
= true;
653 result
.difficult
= true;
657 result
.difficult
= true;
659 /* Join the branches of the condition if possible. */
660 if (!result
.exits
&& !result
.difficult
)
662 /* Only return a next pointer if we dominate this pointer.
663 Otherwise it will be handled by the bb dominating it. */
664 if (dominated_by_p (CDI_DOMINATORS
, last_exit
, bb
)
666 result
.next
= last_exit
;
670 result
.exit
= last_exit
;
672 VEC_free (sd_region
, heap
, regions
);
676 /* Scan remaining bbs dominated by BB. */
677 dominated
= get_dominated_by (CDI_DOMINATORS
, bb
);
679 for (i
= 0; VEC_iterate (basic_block
, dominated
, i
, dom_bb
); i
++)
681 /* Ignore loop exits: they will be handled after the loop body. */
682 if (loop_depth (find_common_loop (loop
, dom_bb
->loop_father
))
689 /* Ignore the bbs processed above. */
690 if (single_pred_p (dom_bb
) && single_pred (dom_bb
) == bb
)
693 if (loop_depth (loop
) > loop_depth (dom_bb
->loop_father
))
694 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
,
697 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
, loop
);
699 result
.exits
|= sinfo
.exits
;
700 result
.difficult
= true;
704 VEC_free (basic_block
, heap
, dominated
);
707 move_sd_regions (®ions
, scops
);
719 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
720 SCOPS. The analyse if a sd_region can be handled is based on the value
721 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
722 is the loop in which CURRENT is handled.
724 TODO: These functions got a little bit big. They definitely should be cleaned
727 static struct scopdet_info
728 build_scops_1 (basic_block current
, loop_p outermost_loop
,
729 VEC (sd_region
, heap
) **scops
, loop_p loop
)
731 bool in_scop
= false;
733 struct scopdet_info sinfo
;
735 /* Initialize result. */
736 struct scopdet_info result
;
737 result
.exits
= false;
738 result
.difficult
= false;
741 open_scop
.entry
= NULL
;
742 open_scop
.exit
= NULL
;
745 /* Loop over the dominance tree. If we meet a difficult bb, close
746 the current SCoP. Loop and condition header start a new layer,
747 and can only be added if all bbs in deeper layers are simple. */
748 while (current
!= NULL
)
750 sinfo
= scopdet_basic_block_info (current
, outermost_loop
, scops
,
751 get_bb_type (current
, loop
));
753 if (!in_scop
&& !(sinfo
.exits
|| sinfo
.difficult
))
755 open_scop
.entry
= current
;
756 open_scop
.exit
= NULL
;
759 else if (in_scop
&& (sinfo
.exits
|| sinfo
.difficult
))
761 open_scop
.exit
= current
;
762 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
766 result
.difficult
|= sinfo
.difficult
;
767 result
.exits
|= sinfo
.exits
;
769 current
= sinfo
.next
;
772 /* Try to close open_scop, if we are still in an open SCoP. */
775 open_scop
.exit
= sinfo
.exit
;
776 gcc_assert (open_scop
.exit
);
777 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
780 result
.exit
= sinfo
.exit
;
784 /* Checks if a bb is contained in REGION. */
787 bb_in_sd_region (basic_block bb
, sd_region
*region
)
789 return bb_in_region (bb
, region
->entry
, region
->exit
);
792 /* Returns the single entry edge of REGION, if it does not exits NULL. */
795 find_single_entry_edge (sd_region
*region
)
801 FOR_EACH_EDGE (e
, ei
, region
->entry
->preds
)
802 if (!bb_in_sd_region (e
->src
, region
))
817 /* Returns the single exit edge of REGION, if it does not exits NULL. */
820 find_single_exit_edge (sd_region
*region
)
826 FOR_EACH_EDGE (e
, ei
, region
->exit
->preds
)
827 if (bb_in_sd_region (e
->src
, region
))
842 /* Create a single entry edge for REGION. */
845 create_single_entry_edge (sd_region
*region
)
847 if (find_single_entry_edge (region
))
850 /* There are multiple predecessors for bb_3
863 There are two edges (1->3, 2->3), that point from outside into the region,
864 and another one (5->3), a loop latch, lead to bb_3.
872 | |\ (3.0 -> 3.1) = single entry edge
881 If the loop is part of the SCoP, we have to redirect the loop latches.
887 | | (3.0 -> 3.1) = entry edge
896 if (region
->entry
->loop_father
->header
!= region
->entry
897 || dominated_by_p (CDI_DOMINATORS
,
898 loop_latch_edge (region
->entry
->loop_father
)->src
,
901 edge forwarder
= split_block_after_labels (region
->entry
);
902 region
->entry
= forwarder
->dest
;
905 /* This case is never executed, as the loop headers seem always to have a
906 single edge pointing from outside into the loop. */
909 #ifdef ENABLE_CHECKING
910 gcc_assert (find_single_entry_edge (region
));
914 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
917 sd_region_without_exit (edge e
)
919 sd_region
*r
= (sd_region
*) e
->aux
;
922 return r
->exit
== NULL
;
927 /* Create a single exit edge for REGION. */
930 create_single_exit_edge (sd_region
*region
)
934 edge forwarder
= NULL
;
937 if (find_single_exit_edge (region
))
940 /* We create a forwarder bb (5) for all edges leaving this region
941 (3->5, 4->5). All other edges leading to the same bb, are moved
942 to a new bb (6). If these edges where part of another region (2->5)
943 we update the region->exit pointer, of this region.
945 To identify which edge belongs to which region we depend on the e->aux
946 pointer in every edge. It points to the region of the edge or to NULL,
947 if the edge is not part of any region.
949 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
950 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
955 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
956 | | \/ 3->5 no region, 4->5 no region,
958 \| / 5->6 region->exit = 6
961 Now there is only a single exit edge (5->6). */
964 forwarder
= make_forwarder_block (exit
, &sd_region_without_exit
, NULL
);
966 /* Unmark the edges, that are no longer exit edges. */
967 FOR_EACH_EDGE (e
, ei
, forwarder
->src
->preds
)
971 /* Mark the new exit edge. */
972 single_succ_edge (forwarder
->src
)->aux
= region
;
974 /* Update the exit bb of all regions, where exit edges lead to
976 FOR_EACH_EDGE (e
, ei
, forwarder
->dest
->preds
)
978 ((sd_region
*) e
->aux
)->exit
= forwarder
->dest
;
980 #ifdef ENABLE_CHECKING
981 gcc_assert (find_single_exit_edge (region
));
985 /* Unmark the exit edges of all REGIONS.
986 See comment in "create_single_exit_edge". */
989 unmark_exit_edges (VEC (sd_region
, heap
) *regions
)
996 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
997 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1002 /* Mark the exit edges of all REGIONS.
1003 See comment in "create_single_exit_edge". */
1006 mark_exit_edges (VEC (sd_region
, heap
) *regions
)
1013 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1014 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1015 if (bb_in_sd_region (e
->src
, s
))
1019 /* Create for all scop regions a single entry and a single exit edge. */
1022 create_sese_edges (VEC (sd_region
, heap
) *regions
)
1027 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1028 create_single_entry_edge (s
);
1030 mark_exit_edges (regions
);
1032 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1033 create_single_exit_edge (s
);
1035 unmark_exit_edges (regions
);
1037 fix_loop_structure (NULL
);
1039 #ifdef ENABLE_CHECKING
1040 verify_loop_structure ();
1041 verify_dominators (CDI_DOMINATORS
);
1046 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1049 build_graphite_scops (VEC (sd_region
, heap
) *regions
,
1050 VEC (scop_p
, heap
) **scops
)
1055 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1057 edge entry
= find_single_entry_edge (s
);
1058 edge exit
= find_single_exit_edge (s
);
1059 scop_p scop
= new_scop (new_sese (entry
, exit
));
1060 VEC_safe_push (scop_p
, heap
, *scops
, scop
);
1062 /* Are there overlapping SCoPs? */
1063 #ifdef ENABLE_CHECKING
1068 for (j
= 0; VEC_iterate (sd_region
, regions
, j
, s2
); j
++)
1070 gcc_assert (!bb_in_sd_region (s
->entry
, s2
));
1076 /* Returns true when BB contains only close phi nodes. */
1079 contains_only_close_phi_nodes (basic_block bb
)
1081 gimple_stmt_iterator gsi
;
1083 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1084 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_LABEL
)
1090 /* Print statistics for SCOP to FILE. */
1093 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
1098 long n_conditions
= 0;
1102 long n_p_conditions
= 0;
1108 gimple_stmt_iterator psi
;
1109 loop_p loop
= bb
->loop_father
;
1111 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
1115 n_p_bbs
+= bb
->count
;
1117 if (VEC_length (edge
, bb
->succs
) > 1)
1120 n_p_conditions
+= bb
->count
;
1123 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1126 n_p_stmts
+= bb
->count
;
1129 if (loop
->header
== bb
&& loop_in_sese_p (loop
, SCOP_REGION (scop
)))
1132 n_p_loops
+= bb
->count
;
1137 fprintf (file
, "\nBefore limit_scops SCoP statistics (");
1138 fprintf (file
, "BBS:%ld, ", n_bbs
);
1139 fprintf (file
, "LOOPS:%ld, ", n_loops
);
1140 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
1141 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
1142 fprintf (file
, "\nBefore limit_scops SCoP profiling statistics (");
1143 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
1144 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
1145 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
1146 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
1149 /* Print statistics for SCOPS to FILE. */
1152 print_graphite_statistics (FILE* file
, VEC (scop_p
, heap
) *scops
)
1157 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
1158 print_graphite_scop_statistics (file
, scop
);
1161 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1171 * SCoP frontier, as this line is not surrounded by any loop. *
1175 This is necessary as scalar evolution and parameter detection need a
1176 outermost loop to initialize parameters correctly.
1178 TODO: FIX scalar evolution and parameter detection to allow more flexible
1182 limit_scops (VEC (scop_p
, heap
) **scops
)
1184 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
1189 for (i
= 0; VEC_iterate (scop_p
, *scops
, i
, scop
); i
++)
1193 sese region
= SCOP_REGION (scop
);
1194 build_sese_loop_nests (region
);
1196 for (j
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), j
, loop
); j
++)
1197 if (!loop_in_sese_p (loop_outer (loop
), region
)
1198 && single_exit (loop
))
1200 sd_region open_scop
;
1201 open_scop
.entry
= loop
->header
;
1202 open_scop
.exit
= single_exit (loop
)->dest
;
1204 /* This is a hack on top of the limit_scops hack. The
1205 limit_scops hack should disappear all together. */
1206 if (single_succ_p (open_scop
.exit
)
1207 && contains_only_close_phi_nodes (open_scop
.exit
))
1208 open_scop
.exit
= single_succ_edge (open_scop
.exit
)->dest
;
1210 VEC_safe_push (sd_region
, heap
, regions
, &open_scop
);
1214 free_scops (*scops
);
1215 *scops
= VEC_alloc (scop_p
, heap
, 3);
1217 create_sese_edges (regions
);
1218 build_graphite_scops (regions
, scops
);
1219 VEC_free (sd_region
, heap
, regions
);
1222 /* Transforms LOOP to the canonical loop closed SSA form. */
1225 canonicalize_loop_closed_ssa (loop_p loop
)
1227 edge e
= single_exit (loop
);
1230 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
1235 if (VEC_length (edge
, bb
->preds
) == 1)
1236 split_block_after_labels (bb
);
1239 gimple_stmt_iterator psi
;
1240 basic_block close
= split_edge (e
);
1242 e
= single_succ_edge (close
);
1244 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1246 gimple phi
= gsi_stmt (psi
);
1249 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1250 if (gimple_phi_arg_edge (phi
, i
) == e
)
1252 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
1253 use_operand_p use_p
;
1256 if (TREE_CODE (arg
) != SSA_NAME
)
1259 close_phi
= create_phi_node (arg
, close
);
1260 res
= create_new_def_for (gimple_phi_result (close_phi
),
1262 gimple_phi_result_ptr (close_phi
));
1263 add_phi_arg (close_phi
, arg
,
1264 gimple_phi_arg_edge (close_phi
, 0),
1266 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
1267 replace_exp (use_p
, res
);
1274 /* Converts the current loop closed SSA form to a canonical form
1275 expected by the Graphite code generation.
1277 The loop closed SSA form has the following invariant: a variable
1278 defined in a loop that is used outside the loop appears only in the
1279 phi nodes in the destination of the loop exit. These phi nodes are
1280 called close phi nodes.
1282 The canonical loop closed SSA form contains the extra invariants:
1284 - when the loop contains only one exit, the close phi nodes contain
1285 only one argument. That implies that the basic block that contains
1286 the close phi nodes has only one predecessor, that is a basic block
1289 - the basic block containing the close phi nodes does not contain
1294 canonicalize_loop_closed_ssa_form (void)
1299 #ifdef ENABLE_CHECKING
1300 verify_loop_closed_ssa ();
1303 FOR_EACH_LOOP (li
, loop
, 0)
1304 canonicalize_loop_closed_ssa (loop
);
1306 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1307 update_ssa (TODO_update_ssa
);
1309 #ifdef ENABLE_CHECKING
1310 verify_loop_closed_ssa ();
1314 /* Find Static Control Parts (SCoP) in the current function and pushes
1318 build_scops (VEC (scop_p
, heap
) **scops
)
1320 struct loop
*loop
= current_loops
->tree_root
;
1321 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
1323 canonicalize_loop_closed_ssa_form ();
1324 build_scops_1 (single_succ (ENTRY_BLOCK_PTR
), ENTRY_BLOCK_PTR
->loop_father
,
1326 create_sese_edges (regions
);
1327 build_graphite_scops (regions
, scops
);
1329 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1330 print_graphite_statistics (dump_file
, *scops
);
1332 limit_scops (scops
);
1333 VEC_free (sd_region
, heap
, regions
);
1335 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1336 fprintf (dump_file
, "\nnumber of SCoPs: %d\n",
1337 VEC_length (scop_p
, *scops
));
1340 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1341 different colors. If there are not enough colors, paint the
1342 remaining SCoPs in gray.
1345 - "*" after the node number denotes the entry of a SCoP,
1346 - "#" after the node number denotes the exit of a SCoP,
1347 - "()" around the node number denotes the entry or the
1348 exit nodes of the SCOP. These are not part of SCoP. */
1351 dot_all_scops_1 (FILE *file
, VEC (scop_p
, heap
) *scops
)
1360 /* Disable debugging while printing graph. */
1361 int tmp_dump_flags
= dump_flags
;
1364 fprintf (file
, "digraph all {\n");
1368 int part_of_scop
= false;
1370 /* Use HTML for every bb label. So we are able to print bbs
1371 which are part of two different SCoPs, with two different
1372 background colors. */
1373 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1375 fprintf (file
, "CELLSPACING=\"0\">\n");
1377 /* Select color for SCoP. */
1378 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
1380 sese region
= SCOP_REGION (scop
);
1381 if (bb_in_sese_p (bb
, region
)
1382 || (SESE_EXIT_BB (region
) == bb
)
1383 || (SESE_ENTRY_BB (region
) == bb
))
1396 case 3: /* purple */
1399 case 4: /* orange */
1402 case 5: /* yellow */
1442 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color
);
1444 if (!bb_in_sese_p (bb
, region
))
1445 fprintf (file
, " (");
1447 if (bb
== SESE_ENTRY_BB (region
)
1448 && bb
== SESE_EXIT_BB (region
))
1449 fprintf (file
, " %d*# ", bb
->index
);
1450 else if (bb
== SESE_ENTRY_BB (region
))
1451 fprintf (file
, " %d* ", bb
->index
);
1452 else if (bb
== SESE_EXIT_BB (region
))
1453 fprintf (file
, " %d# ", bb
->index
);
1455 fprintf (file
, " %d ", bb
->index
);
1457 if (!bb_in_sese_p (bb
,region
))
1458 fprintf (file
, ")");
1460 fprintf (file
, "</TD></TR>\n");
1461 part_of_scop
= true;
1467 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1468 fprintf (file
, " %d </TD></TR>\n", bb
->index
);
1470 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1475 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1476 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
1479 fputs ("}\n\n", file
);
1481 /* Enable debugging again. */
1482 dump_flags
= tmp_dump_flags
;
1485 /* Display all SCoPs using dotty. */
1488 dot_all_scops (VEC (scop_p
, heap
) *scops
)
1490 /* When debugging, enable the following code. This cannot be used
1491 in production compilers because it calls "system". */
1494 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1495 gcc_assert (stream
);
1497 dot_all_scops_1 (stream
, scops
);
1500 x
= system ("dotty /tmp/allscops.dot");
1502 dot_all_scops_1 (stderr
, scops
);
1506 /* Display all SCoPs using dotty. */
1509 dot_scop (scop_p scop
)
1511 VEC (scop_p
, heap
) *scops
= NULL
;
1514 VEC_safe_push (scop_p
, heap
, scops
, scop
);
1516 /* When debugging, enable the following code. This cannot be used
1517 in production compilers because it calls "system". */
1521 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1522 gcc_assert (stream
);
1524 dot_all_scops_1 (stream
, scops
);
1526 x
= system ("dotty /tmp/allscops.dot");
1529 dot_all_scops_1 (stderr
, scops
);
1532 VEC_free (scop_p
, heap
, scops
);