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"
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"
53 #include "refined-regions.h"
55 /* The type of the analyzed basic block. */
57 typedef enum gbb_type
{
59 GBB_LOOP_SING_EXIT_HEADER
,
60 GBB_LOOP_MULT_EXIT_HEADER
,
67 /* Detect the type of BB. Loop headers are only marked, if they are
68 new. This means their loop_father is different to LAST_LOOP.
69 Otherwise they are treated like any other bb and their type can be
73 get_bb_type (basic_block bb
, struct loop
*last_loop
)
75 VEC (basic_block
, heap
) *dom
;
77 struct loop
*loop
= bb
->loop_father
;
79 /* Check, if we entry into a new loop. */
80 if (loop
!= last_loop
)
82 if (single_exit (loop
) != NULL
)
83 return GBB_LOOP_SING_EXIT_HEADER
;
84 else if (loop
->num
!= 0)
85 return GBB_LOOP_MULT_EXIT_HEADER
;
87 return GBB_COND_HEADER
;
90 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
91 nb_dom
= VEC_length (basic_block
, dom
);
92 VEC_free (basic_block
, heap
, dom
);
97 nb_suc
= VEC_length (edge
, bb
->succs
);
99 if (nb_dom
== 1 && nb_suc
== 1)
102 return GBB_COND_HEADER
;
105 /* A SCoP detection region, defined using bbs as borders.
107 All control flow touching this region, comes in passing basic_block
108 ENTRY and leaves passing basic_block EXIT. By using bbs instead of
109 edges for the borders we are able to represent also regions that do
110 not have a single entry or exit edge.
112 But as they have a single entry basic_block and a single exit
113 basic_block, we are able to generate for every sd_region a single
121 / \ This region contains: {3, 4, 5, 6, 7, 8}
129 typedef struct sd_region_p
131 /* The entry bb dominates all bbs in the sd_region. It is part of
135 /* The exit bb postdominates all bbs in the sd_region, but is not
136 part of the region. */
140 DEF_VEC_O(sd_region
);
141 DEF_VEC_ALLOC_O(sd_region
, heap
);
144 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
147 move_sd_regions (VEC (sd_region
, heap
) **source
,
148 VEC (sd_region
, heap
) **target
)
153 for (i
= 0; VEC_iterate (sd_region
, *source
, i
, s
); i
++)
154 VEC_safe_push (sd_region
, heap
, *target
, s
);
156 VEC_free (sd_region
, heap
, *source
);
159 /* Something like "n * m" is not allowed. */
162 graphite_can_represent_init (tree e
)
164 switch (TREE_CODE (e
))
166 case POLYNOMIAL_CHREC
:
167 return graphite_can_represent_init (CHREC_LEFT (e
))
168 && graphite_can_represent_init (CHREC_RIGHT (e
));
171 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
172 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
173 && host_integerp (TREE_OPERAND (e
, 1), 0);
175 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
176 && host_integerp (TREE_OPERAND (e
, 0), 0);
179 case POINTER_PLUS_EXPR
:
181 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
182 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
187 case NON_LVALUE_EXPR
:
188 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
197 /* Return true when SCEV can be represented in the polyhedral model.
199 An expression can be represented, if it can be expressed as an
200 affine expression. For loops (i, j) and parameters (m, n) all
201 affine expressions are of the form:
203 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
205 1 i + 20 j + (-2) m + 25
207 Something like "i * n" or "n * m" is not allowed.
209 OUTERMOST_LOOP defines the outermost loop that can variate. */
212 graphite_can_represent_scev (tree scev
, int outermost_loop
)
214 if (chrec_contains_undetermined (scev
))
217 switch (TREE_CODE (scev
))
221 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0), outermost_loop
)
222 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1), outermost_loop
);
225 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
226 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
227 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
228 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
229 && graphite_can_represent_init (scev
)
230 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0), outermost_loop
)
231 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1), outermost_loop
);
233 case POLYNOMIAL_CHREC
:
234 /* Check for constant strides. With a non constant stride of
235 'n' we would have a value of 'iv * n'. Also check that the
236 initial value can represented: for example 'n * m' cannot be
238 if (!evolution_function_right_is_integer_cst (scev
)
239 || !graphite_can_represent_init (scev
))
246 /* Only affine functions can be represented. */
247 if (!scev_is_linear_expression (scev
))
250 return evolution_function_is_invariant_p (scev
, outermost_loop
)
251 || evolution_function_is_affine_multivariate_p (scev
, outermost_loop
);
255 /* Return true when EXPR can be represented in the polyhedral model.
257 This means an expression can be represented, if it is linear with
258 respect to the loops and the strides are non parametric.
259 LOOP is the place where the expr will be evaluated and OUTERMOST_LOOP
260 defindes the outermost loop that can variate. SCOP_ENTRY defines the
261 entry of the region we analyse. */
264 graphite_can_represent_expr (basic_block scop_entry
, loop_p loop
,
265 loop_p outermost_loop
, tree expr
)
267 tree scev
= analyze_scalar_evolution (loop
, expr
);
269 scev
= instantiate_scev (scop_entry
, loop
, scev
);
271 return graphite_can_represent_scev (scev
, outermost_loop
->num
);
274 /* Return true if the data references of STMT can be represented by
278 stmt_has_simple_data_refs_p (loop_p outermost_loop
, gimple stmt
)
284 int loop
= outermost_loop
->num
;
285 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 5);
287 graphite_find_data_references_in_stmt (outermost_loop
, stmt
, &drs
);
289 for (j
= 0; VEC_iterate (data_reference_p
, drs
, j
, dr
); j
++)
290 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
291 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
), loop
))
298 free_data_refs (drs
);
302 /* Return true only when STMT is simple enough for being handled by
303 Graphite. This depends on SCOP_ENTRY, as the parameters are
304 initialized relatively to this basic block, the linear functions
305 are initialized to OUTERMOST_LOOP and BB is the place where we try
306 to evaluate the STMT. */
309 stmt_simple_for_scop_p (basic_block scop_entry
, loop_p outermost_loop
,
310 gimple stmt
, basic_block bb
)
312 loop_p loop
= bb
->loop_father
;
314 gcc_assert (scop_entry
);
316 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
317 Calls have side-effects, except those to const or pure
319 if (gimple_has_volatile_ops (stmt
)
320 || (gimple_code (stmt
) == GIMPLE_CALL
321 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
322 || (gimple_code (stmt
) == GIMPLE_ASM
))
325 if (is_gimple_debug (stmt
))
328 if (!stmt_has_simple_data_refs_p (outermost_loop
, stmt
))
331 switch (gimple_code (stmt
))
341 enum tree_code code
= gimple_cond_code (stmt
);
343 /* We can handle all binary comparisons. Inequalities are
344 also supported as they can be represented with union of
346 if (!(code
== LT_EXPR
354 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, op_iter
, SSA_OP_ALL_USES
)
355 if (!graphite_can_represent_expr (scop_entry
, loop
, outermost_loop
,
357 /* We can not handle REAL_TYPE. Failed for pr39260. */
358 || TREE_CODE (TREE_TYPE (op
)) == REAL_TYPE
)
369 /* These nodes cut a new scope. */
376 /* Returns the statement of BB that contains a harmful operation: that
377 can be a function call with side effects, the induction variables
378 are not linear with respect to SCOP_ENTRY, etc. The current open
379 scop should end before this statement. The evaluation is limited using
380 OUTERMOST_LOOP as outermost loop that may change. */
383 harmful_stmt_in_bb (basic_block scop_entry
, loop_p outer_loop
, basic_block bb
)
385 gimple_stmt_iterator gsi
;
387 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
388 if (!stmt_simple_for_scop_p (scop_entry
, outer_loop
, gsi_stmt (gsi
), bb
))
389 return gsi_stmt (gsi
);
394 /* Return true when it is not possible to represent LOOP in the
395 polyhedral representation. This is evaluated taking SCOP_ENTRY and
396 OUTERMOST_LOOP in mind. */
399 graphite_can_represent_loop (basic_block scop_entry
, loop_p outermost_loop
,
402 tree niter
= number_of_latch_executions (loop
);
404 /* Number of iterations unknown. */
405 if (chrec_contains_undetermined (niter
))
408 /* Number of iterations not affine. */
409 if (!graphite_can_represent_expr (scop_entry
, loop
, outermost_loop
, niter
))
415 /* Store information needed by scopdet_* functions. */
419 /* Exit of the open scop would stop if the current BB is harmful. */
422 /* Where the next scop would start if the current BB is harmful. */
425 /* The bb or one of its children contains open loop exits. That means
426 loop exit nodes that are not surrounded by a loop dominated by bb. */
429 /* The bb or one of its children contains only structures we can handle. */
433 static struct scopdet_info
build_scops_1 (basic_block
, loop_p
,
434 VEC (sd_region
, heap
) **, loop_p
);
436 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
437 to SCOPS. TYPE is the gbb_type of BB. */
439 static struct scopdet_info
440 scopdet_basic_block_info (basic_block bb
, loop_p outermost_loop
,
441 VEC (sd_region
, heap
) **scops
, gbb_type type
)
443 loop_p loop
= bb
->loop_father
;
444 struct scopdet_info result
;
447 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
448 basic_block entry_block
= ENTRY_BLOCK_PTR
;
449 stmt
= harmful_stmt_in_bb (entry_block
, outermost_loop
, bb
);
450 result
.difficult
= (stmt
!= NULL
);
457 result
.exits
= false;
459 /* Mark bbs terminating a SESE region difficult, if they start
461 if (!single_succ_p (bb
))
462 result
.difficult
= true;
464 result
.exit
= single_succ (bb
);
469 result
.next
= single_succ (bb
);
470 result
.exits
= false;
471 result
.exit
= single_succ (bb
);
474 case GBB_LOOP_SING_EXIT_HEADER
:
476 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
477 struct scopdet_info sinfo
;
478 edge exit_e
= single_exit (loop
);
480 sinfo
= build_scops_1 (bb
, outermost_loop
, ®ions
, loop
);
482 if (!graphite_can_represent_loop (entry_block
, outermost_loop
, loop
))
483 result
.difficult
= true;
485 result
.difficult
|= sinfo
.difficult
;
487 /* Try again with another loop level. */
489 && loop_depth (outermost_loop
) + 1 == loop_depth (loop
))
491 outermost_loop
= loop
;
493 VEC_free (sd_region
, heap
, regions
);
494 regions
= VEC_alloc (sd_region
, heap
, 3);
496 sinfo
= scopdet_basic_block_info (bb
, outermost_loop
, scops
, type
);
499 result
.difficult
= true;
502 move_sd_regions (®ions
, scops
);
506 open_scop
.entry
= bb
;
507 open_scop
.exit
= exit_e
->dest
;
508 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
509 VEC_free (sd_region
, heap
, regions
);
514 result
.exit
= exit_e
->dest
;
515 result
.next
= exit_e
->dest
;
517 /* If we do not dominate result.next, remove it. It's either
518 the EXIT_BLOCK_PTR, or another bb dominates it and will
519 call the scop detection for this bb. */
520 if (!dominated_by_p (CDI_DOMINATORS
, result
.next
, bb
))
523 if (exit_e
->src
->loop_father
!= loop
)
526 result
.exits
= false;
528 if (result
.difficult
)
529 move_sd_regions (®ions
, scops
);
531 VEC_free (sd_region
, heap
, regions
);
537 case GBB_LOOP_MULT_EXIT_HEADER
:
539 /* XXX: For now we just do not join loops with multiple exits. If the
540 exits lead to the same bb it may be possible to join the loop. */
541 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
542 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
545 build_scops_1 (bb
, loop
, ®ions
, loop
);
547 /* Scan the code dominated by this loop. This means all bbs, that are
548 are dominated by a bb in this loop, but are not part of this loop.
551 - The loop exit destination is dominated by the exit sources.
553 TODO: We miss here the more complex cases:
554 - The exit destinations are dominated by another bb inside
556 - The loop dominates bbs, that are not exit destinations. */
557 for (i
= 0; VEC_iterate (edge
, exits
, i
, e
); i
++)
558 if (e
->src
->loop_father
== loop
559 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
))
561 if (loop_outer (outermost_loop
))
562 outermost_loop
= loop_outer (outermost_loop
);
564 /* Pass loop_outer to recognize e->dest as loop header in
566 if (e
->dest
->loop_father
->header
== e
->dest
)
567 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
568 loop_outer (e
->dest
->loop_father
));
570 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
571 e
->dest
->loop_father
);
576 result
.difficult
= true;
577 result
.exits
= false;
578 move_sd_regions (®ions
, scops
);
579 VEC_free (edge
, heap
, exits
);
582 case GBB_COND_HEADER
:
584 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
585 struct scopdet_info sinfo
;
586 VEC (basic_block
, heap
) *dominated
;
589 basic_block last_exit
= NULL
;
591 result
.exits
= false;
593 /* First check the successors of BB, and check if it is
594 possible to join the different branches. */
595 for (i
= 0; VEC_iterate (edge
, bb
->succs
, i
, e
); i
++)
597 /* Ignore loop exits. They will be handled after the loop
599 if (is_loop_exit (loop
, e
->dest
))
605 /* Do not follow edges that lead to the end of the
606 conditions block. For example, in
616 the edge from 0 => 6. Only check if all paths lead to
619 if (!single_pred_p (e
->dest
))
621 /* Check, if edge leads directly to the end of this
626 if (e
->dest
!= last_exit
)
627 result
.difficult
= true;
632 if (!dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
634 result
.difficult
= true;
638 sinfo
= build_scops_1 (e
->dest
, outermost_loop
, ®ions
, loop
);
640 result
.exits
|= sinfo
.exits
;
641 result
.difficult
|= sinfo
.difficult
;
643 /* Checks, if all branches end at the same point.
644 If that is true, the condition stays joinable.
645 Have a look at the example above. */
649 last_exit
= sinfo
.exit
;
651 if (sinfo
.exit
!= last_exit
)
652 result
.difficult
= true;
655 result
.difficult
= true;
659 result
.difficult
= true;
661 /* Join the branches of the condition if possible. */
662 if (!result
.exits
&& !result
.difficult
)
664 /* Only return a next pointer if we dominate this pointer.
665 Otherwise it will be handled by the bb dominating it. */
666 if (dominated_by_p (CDI_DOMINATORS
, last_exit
, bb
)
668 result
.next
= last_exit
;
672 result
.exit
= last_exit
;
674 VEC_free (sd_region
, heap
, regions
);
678 /* Scan remaining bbs dominated by BB. */
679 dominated
= get_dominated_by (CDI_DOMINATORS
, bb
);
681 for (i
= 0; VEC_iterate (basic_block
, dominated
, i
, dom_bb
); i
++)
683 /* Ignore loop exits: they will be handled after the loop body. */
684 if (loop_depth (find_common_loop (loop
, dom_bb
->loop_father
))
691 /* Ignore the bbs processed above. */
692 if (single_pred_p (dom_bb
) && single_pred (dom_bb
) == bb
)
695 if (loop_depth (loop
) > loop_depth (dom_bb
->loop_father
))
696 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
,
699 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
, loop
);
701 result
.exits
|= sinfo
.exits
;
702 result
.difficult
= true;
706 VEC_free (basic_block
, heap
, dominated
);
709 move_sd_regions (®ions
, scops
);
721 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
722 SCOPS. The analyse if a sd_region can be handled is based on the value
723 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
724 is the loop in which CURRENT is handled.
726 TODO: These functions got a little bit big. They definitely should be cleaned
729 static struct scopdet_info
730 build_scops_1 (basic_block current
, loop_p outermost_loop
,
731 VEC (sd_region
, heap
) **scops
, loop_p loop
)
733 bool in_scop
= false;
735 struct scopdet_info sinfo
;
737 /* Initialize result. */
738 struct scopdet_info result
;
739 result
.exits
= false;
740 result
.difficult
= false;
743 open_scop
.entry
= NULL
;
744 open_scop
.exit
= NULL
;
747 /* Loop over the dominance tree. If we meet a difficult bb, close
748 the current SCoP. Loop and condition header start a new layer,
749 and can only be added if all bbs in deeper layers are simple. */
750 while (current
!= NULL
)
752 sinfo
= scopdet_basic_block_info (current
, outermost_loop
, scops
,
753 get_bb_type (current
, loop
));
755 if (!in_scop
&& !(sinfo
.exits
|| sinfo
.difficult
))
757 open_scop
.entry
= current
;
758 open_scop
.exit
= NULL
;
761 else if (in_scop
&& (sinfo
.exits
|| sinfo
.difficult
))
763 open_scop
.exit
= current
;
764 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
768 result
.difficult
|= sinfo
.difficult
;
769 result
.exits
|= sinfo
.exits
;
771 current
= sinfo
.next
;
774 /* Try to close open_scop, if we are still in an open SCoP. */
777 open_scop
.exit
= sinfo
.exit
;
778 gcc_assert (open_scop
.exit
);
779 VEC_safe_push (sd_region
, heap
, *scops
, &open_scop
);
782 result
.exit
= sinfo
.exit
;
786 /* Checks if a bb is contained in REGION. */
789 bb_in_sd_region (basic_block bb
, sd_region
*region
)
791 return bb_in_region (bb
, region
->entry
, region
->exit
);
794 /* Returns the single entry edge of REGION, if it does not exits NULL. */
797 find_single_entry_edge (sd_region
*region
)
803 FOR_EACH_EDGE (e
, ei
, region
->entry
->preds
)
804 if (!bb_in_sd_region (e
->src
, region
))
819 /* Returns the single exit edge of REGION, if it does not exits NULL. */
822 find_single_exit_edge (sd_region
*region
)
828 FOR_EACH_EDGE (e
, ei
, region
->exit
->preds
)
829 if (bb_in_sd_region (e
->src
, region
))
844 /* Create a single entry edge for REGION. */
847 create_single_entry_edge (sd_region
*region
)
849 if (find_single_entry_edge (region
))
852 /* There are multiple predecessors for bb_3
865 There are two edges (1->3, 2->3), that point from outside into the region,
866 and another one (5->3), a loop latch, lead to bb_3.
874 | |\ (3.0 -> 3.1) = single entry edge
883 If the loop is part of the SCoP, we have to redirect the loop latches.
889 | | (3.0 -> 3.1) = entry edge
898 if (region
->entry
->loop_father
->header
!= region
->entry
899 || dominated_by_p (CDI_DOMINATORS
,
900 loop_latch_edge (region
->entry
->loop_father
)->src
,
903 edge forwarder
= split_block_after_labels (region
->entry
);
904 region
->entry
= forwarder
->dest
;
907 /* This case is never executed, as the loop headers seem always to have a
908 single edge pointing from outside into the loop. */
911 #ifdef ENABLE_CHECKING
912 gcc_assert (find_single_entry_edge (region
));
916 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
919 sd_region_without_exit (edge e
)
921 sd_region
*r
= (sd_region
*) e
->aux
;
924 return r
->exit
== NULL
;
929 /* Create a single exit edge for REGION. */
932 create_single_exit_edge (sd_region
*region
)
936 edge forwarder
= NULL
;
939 /* We create a forwarder bb (5) for all edges leaving this region
940 (3->5, 4->5). All other edges leading to the same bb, are moved
941 to a new bb (6). If these edges where part of another region (2->5)
942 we update the region->exit pointer, of this region.
944 To identify which edge belongs to which region we depend on the e->aux
945 pointer in every edge. It points to the region of the edge or to NULL,
946 if the edge is not part of any region.
948 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
949 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
954 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
955 | | \/ 3->5 no region, 4->5 no region,
957 \| / 5->6 region->exit = 6
960 Now there is only a single exit edge (5->6). */
963 forwarder
= make_forwarder_block (exit
, &sd_region_without_exit
, NULL
);
965 /* Unmark the edges, that are no longer exit edges. */
966 FOR_EACH_EDGE (e
, ei
, forwarder
->src
->preds
)
970 /* Mark the new exit edge. */
971 single_succ_edge (forwarder
->src
)->aux
= region
;
973 /* Update the exit bb of all regions, where exit edges lead to
975 FOR_EACH_EDGE (e
, ei
, forwarder
->dest
->preds
)
977 ((sd_region
*) e
->aux
)->exit
= forwarder
->dest
;
979 #ifdef ENABLE_CHECKING
980 gcc_assert (find_single_exit_edge (region
));
984 /* Unmark the exit edges of all REGIONS.
985 See comment in "create_single_exit_edge". */
988 unmark_exit_edges (VEC (sd_region
, heap
) *regions
)
995 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
996 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1001 /* Mark the exit edges of all REGIONS.
1002 See comment in "create_single_exit_edge". */
1005 mark_exit_edges (VEC (sd_region
, heap
) *regions
)
1012 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1013 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1014 if (bb_in_sd_region (e
->src
, s
))
1018 /* Create for all scop regions a single entry and a single exit edge. */
1021 create_sese_edges (VEC (sd_region
, heap
) *regions
)
1026 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1027 create_single_entry_edge (s
);
1029 mark_exit_edges (regions
);
1031 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1032 /* Don't handle multiple edges exiting the function. */
1033 if (!find_single_exit_edge (s
)
1034 && s
->exit
!= EXIT_BLOCK_PTR
)
1035 create_single_exit_edge (s
);
1037 unmark_exit_edges (regions
);
1039 fix_loop_structure (NULL
);
1041 #ifdef ENABLE_CHECKING
1042 verify_loop_structure ();
1043 verify_dominators (CDI_DOMINATORS
);
1048 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1051 build_graphite_scops (VEC (sd_region
, heap
) *regions
,
1052 VEC (scop_p
, heap
) **scops
)
1057 for (i
= 0; VEC_iterate (sd_region
, regions
, i
, s
); i
++)
1059 edge entry
= find_single_entry_edge (s
);
1060 edge exit
= find_single_exit_edge (s
);
1066 scop
= new_scop (new_sese (entry
, exit
));
1067 VEC_safe_push (scop_p
, heap
, *scops
, scop
);
1069 /* Are there overlapping SCoPs? */
1070 #ifdef ENABLE_CHECKING
1075 for (j
= 0; VEC_iterate (sd_region
, regions
, j
, s2
); j
++)
1077 gcc_assert (!bb_in_sd_region (s
->entry
, s2
));
1083 /* Returns true when BB contains only close phi nodes. */
1086 contains_only_close_phi_nodes (basic_block bb
)
1088 gimple_stmt_iterator gsi
;
1090 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1091 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_LABEL
)
1097 /* Print statistics for SCOP to FILE. */
1100 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
1105 long n_conditions
= 0;
1109 long n_p_conditions
= 0;
1115 gimple_stmt_iterator psi
;
1116 loop_p loop
= bb
->loop_father
;
1118 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
1122 n_p_bbs
+= bb
->count
;
1124 if (VEC_length (edge
, bb
->succs
) > 1)
1127 n_p_conditions
+= bb
->count
;
1130 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1133 n_p_stmts
+= bb
->count
;
1136 if (loop
->header
== bb
&& loop_in_sese_p (loop
, SCOP_REGION (scop
)))
1139 n_p_loops
+= bb
->count
;
1144 fprintf (file
, "\nBefore limit_scops SCoP statistics (");
1145 fprintf (file
, "BBS:%ld, ", n_bbs
);
1146 fprintf (file
, "LOOPS:%ld, ", n_loops
);
1147 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
1148 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
1149 fprintf (file
, "\nBefore limit_scops SCoP profiling statistics (");
1150 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
1151 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
1152 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
1153 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
1156 /* Print statistics for SCOPS to FILE. */
1159 print_graphite_statistics (FILE* file
, VEC (scop_p
, heap
) *scops
)
1164 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
1165 print_graphite_scop_statistics (file
, scop
);
1168 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1178 * SCoP frontier, as this line is not surrounded by any loop. *
1182 This is necessary as scalar evolution and parameter detection need a
1183 outermost loop to initialize parameters correctly.
1185 TODO: FIX scalar evolution and parameter detection to allow more flexible
1189 limit_scops (VEC (scop_p
, heap
) **scops
)
1191 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
1196 for (i
= 0; VEC_iterate (scop_p
, *scops
, i
, scop
); i
++)
1200 sese region
= SCOP_REGION (scop
);
1201 build_sese_loop_nests (region
);
1203 for (j
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), j
, loop
); j
++)
1204 if (!loop_in_sese_p (loop_outer (loop
), region
)
1205 && single_exit (loop
))
1207 sd_region open_scop
;
1208 open_scop
.entry
= loop
->header
;
1209 open_scop
.exit
= single_exit (loop
)->dest
;
1211 /* This is a hack on top of the limit_scops hack. The
1212 limit_scops hack should disappear all together. */
1213 if (single_succ_p (open_scop
.exit
)
1214 && contains_only_close_phi_nodes (open_scop
.exit
))
1215 open_scop
.exit
= single_succ_edge (open_scop
.exit
)->dest
;
1217 VEC_safe_push (sd_region
, heap
, regions
, &open_scop
);
1221 free_scops (*scops
);
1222 *scops
= VEC_alloc (scop_p
, heap
, 3);
1224 create_sese_edges (regions
);
1225 build_graphite_scops (regions
, scops
);
1226 VEC_free (sd_region
, heap
, regions
);
1229 /* Transforms LOOP to the canonical loop closed SSA form. */
1232 canonicalize_loop_closed_ssa (loop_p loop
)
1234 edge e
= single_exit (loop
);
1237 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
1242 if (VEC_length (edge
, bb
->preds
) == 1)
1243 split_block_after_labels (bb
);
1246 gimple_stmt_iterator psi
;
1247 basic_block close
= split_edge (e
);
1249 e
= single_succ_edge (close
);
1251 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1253 gimple phi
= gsi_stmt (psi
);
1256 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1257 if (gimple_phi_arg_edge (phi
, i
) == e
)
1259 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
1260 use_operand_p use_p
;
1263 if (TREE_CODE (arg
) != SSA_NAME
)
1266 close_phi
= create_phi_node (arg
, close
);
1267 res
= create_new_def_for (gimple_phi_result (close_phi
),
1269 gimple_phi_result_ptr (close_phi
));
1270 add_phi_arg (close_phi
, arg
,
1271 gimple_phi_arg_edge (close_phi
, 0),
1273 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
1274 replace_exp (use_p
, res
);
1281 /* Converts the current loop closed SSA form to a canonical form
1282 expected by the Graphite code generation.
1284 The loop closed SSA form has the following invariant: a variable
1285 defined in a loop that is used outside the loop appears only in the
1286 phi nodes in the destination of the loop exit. These phi nodes are
1287 called close phi nodes.
1289 The canonical loop closed SSA form contains the extra invariants:
1291 - when the loop contains only one exit, the close phi nodes contain
1292 only one argument. That implies that the basic block that contains
1293 the close phi nodes has only one predecessor, that is a basic block
1296 - the basic block containing the close phi nodes does not contain
1301 canonicalize_loop_closed_ssa_form (void)
1306 #ifdef ENABLE_CHECKING
1307 verify_loop_closed_ssa (true);
1310 FOR_EACH_LOOP (li
, loop
, 0)
1311 canonicalize_loop_closed_ssa (loop
);
1313 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1314 update_ssa (TODO_update_ssa
);
1316 #ifdef ENABLE_CHECKING
1317 verify_loop_closed_ssa (true);
1321 /* Check if REGION is a valid SCoP. */
1324 is_scop_p (refined_region_p region ATTRIBUTE_UNUSED
)
1326 /* TODO: Are there any harmful bbs in the region? */
1327 /* TODO: Do all loops have a number of iterations that can be expressed
1328 by an affine linear function. */
1329 /* TODO: Is there only well structured control flow in the region?
1330 * All loops have just one exit?
1331 * All loops are detected by gcc's loop detection?
1332 * All conditions are well nested? */
1337 /* Find in a structured way Static Control Parts (SCoP) in the current
1341 build_scops_new (void)
1344 VEC (refined_region_p
, heap
) *scops
= VEC_alloc (refined_region_p
, heap
, 3);
1345 VEC (refined_region_p
, heap
) *check
= VEC_alloc (refined_region_p
, heap
, 3);
1347 /* TODO: Call canonicalize_loop_closed_ssa_form() at the right place. */
1349 /* Build new region tree. */
1350 refined_region_p new_region
= calculate_region_tree ();
1352 /* Find the maximal valid regions. */
1353 VEC_safe_push (refined_region_p
, heap
, check
, new_region
);
1355 while (VEC_length (refined_region_p
, check
) != 0)
1357 refined_region_p region
= VEC_last (refined_region_p
, check
);
1358 VEC_pop (refined_region_p
, check
);
1360 if (is_scop_p (region
))
1361 VEC_safe_push (refined_region_p
, heap
, scops
, region
);
1365 refined_region_p subregion
;
1368 VEC_iterate (refined_region_p
, region
->children
, ix
, subregion
);
1370 VEC_safe_push (refined_region_p
, heap
, check
, subregion
);
1374 /* TODO: Check if we can create even bigger regions by combining
1375 canonical regions, that are executed one after another. */
1376 /* TODO: Create sese edges. */
1377 /* TODO: Create graphite scops. */
1379 VEC_free (refined_region_p
, heap
, check
);
1380 VEC_free (refined_region_p
, heap
, scops
);
1381 free_region_tree (new_region
);
1385 /* Find Static Control Parts (SCoP) in the current function and pushes
1386 them to SCOPS. (Old version) */
1389 build_scops_old (VEC (scop_p
, heap
) **scops
)
1391 struct loop
*loop
= current_loops
->tree_root
;
1392 VEC (sd_region
, heap
) *regions
= VEC_alloc (sd_region
, heap
, 3);
1394 canonicalize_loop_closed_ssa_form ();
1395 build_scops_1 (single_succ (ENTRY_BLOCK_PTR
), ENTRY_BLOCK_PTR
->loop_father
,
1397 create_sese_edges (regions
);
1398 build_graphite_scops (regions
, scops
);
1400 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1401 print_graphite_statistics (dump_file
, *scops
);
1403 limit_scops (scops
);
1404 VEC_free (sd_region
, heap
, regions
);
1406 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1407 fprintf (dump_file
, "\nnumber of SCoPs: %d\n",
1408 VEC_length (scop_p
, *scops
));
1411 /* Find Static Control Parts (SCoP) in the current function and pushes
1415 build_scops (VEC (scop_p
, heap
) **scops
)
1417 /* Run the new version in parallel to check it. */
1419 build_scops_old (scops
);
1422 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1423 different colors. If there are not enough colors, paint the
1424 remaining SCoPs in gray.
1427 - "*" after the node number denotes the entry of a SCoP,
1428 - "#" after the node number denotes the exit of a SCoP,
1429 - "()" around the node number denotes the entry or the
1430 exit nodes of the SCOP. These are not part of SCoP. */
1433 dot_all_scops_1 (FILE *file
, VEC (scop_p
, heap
) *scops
)
1442 /* Disable debugging while printing graph. */
1443 int tmp_dump_flags
= dump_flags
;
1446 fprintf (file
, "digraph all {\n");
1450 int part_of_scop
= false;
1452 /* Use HTML for every bb label. So we are able to print bbs
1453 which are part of two different SCoPs, with two different
1454 background colors. */
1455 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1457 fprintf (file
, "CELLSPACING=\"0\">\n");
1459 /* Select color for SCoP. */
1460 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
1462 sese region
= SCOP_REGION (scop
);
1463 if (bb_in_sese_p (bb
, region
)
1464 || (SESE_EXIT_BB (region
) == bb
)
1465 || (SESE_ENTRY_BB (region
) == bb
))
1478 case 3: /* purple */
1481 case 4: /* orange */
1484 case 5: /* yellow */
1524 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color
);
1526 if (!bb_in_sese_p (bb
, region
))
1527 fprintf (file
, " (");
1529 if (bb
== SESE_ENTRY_BB (region
)
1530 && bb
== SESE_EXIT_BB (region
))
1531 fprintf (file
, " %d*# ", bb
->index
);
1532 else if (bb
== SESE_ENTRY_BB (region
))
1533 fprintf (file
, " %d* ", bb
->index
);
1534 else if (bb
== SESE_EXIT_BB (region
))
1535 fprintf (file
, " %d# ", bb
->index
);
1537 fprintf (file
, " %d ", bb
->index
);
1539 if (!bb_in_sese_p (bb
,region
))
1540 fprintf (file
, ")");
1542 fprintf (file
, "</TD></TR>\n");
1543 part_of_scop
= true;
1549 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1550 fprintf (file
, " %d </TD></TR>\n", bb
->index
);
1552 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1557 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1558 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
1561 fputs ("}\n\n", file
);
1563 /* Enable debugging again. */
1564 dump_flags
= tmp_dump_flags
;
1567 /* Display all SCoPs using dotty. */
1570 dot_all_scops (VEC (scop_p
, heap
) *scops
)
1572 /* When debugging, enable the following code. This cannot be used
1573 in production compilers because it calls "system". */
1575 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1576 gcc_assert (stream
);
1578 dot_all_scops_1 (stream
, scops
);
1581 system ("dotty /tmp/allscops.dot &");
1583 dot_all_scops_1 (stderr
, scops
);
1587 /* Display all SCoPs using dotty. */
1590 dot_scop (scop_p scop
)
1592 VEC (scop_p
, heap
) *scops
= NULL
;
1595 VEC_safe_push (scop_p
, heap
, scops
, scop
);
1597 /* When debugging, enable the following code. This cannot be used
1598 in production compilers because it calls "system". */
1601 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1602 gcc_assert (stream
);
1604 dot_all_scops_1 (stream
, scops
);
1606 system ("dotty /tmp/allscops.dot &");
1609 dot_all_scops_1 (stderr
, scops
);
1612 VEC_free (scop_p
, heap
, scops
);