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 false if the TREE_CODE of the operand OP or any of its operands
301 is a COMPONENT_REF. */
304 exclude_component_ref (tree op)
312 if (TREE_CODE (op) == COMPONENT_REF)
315 len = TREE_OPERAND_LENGTH (op);
316 for (i = 0; i < len; ++i)
317 if (!exclude_component_ref (TREE_OPERAND (op, i)))
323 /* Return true if the operand OP used in STMT is simple in regards to
327 is_simple_operand (tree op)
329 /* It is not a simple operand when it is a declaration or a
331 return !DECL_P (op) && !AGGREGATE_TYPE_P (TREE_TYPE (op))
332 && exclude_component_ref (op);
335 /* Return true only when STMT is simple enough for being handled by
336 Graphite. This depends on SCOP_ENTRY, as the parameters are
337 initialized relatively to this basic block, the linear functions
338 are initialized to OUTERMOST_LOOP and BB is the place where we try
339 to evaluate the STMT. */
342 stmt_simple_for_scop_p (basic_block scop_entry, loop_p outermost_loop,
343 gimple stmt, basic_block bb)
345 loop_p loop = bb->loop_father;
347 gcc_assert (scop_entry);
349 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
350 Calls have side-effects, except those to const or pure
352 if (gimple_has_volatile_ops (stmt)
353 || (gimple_code (stmt) == GIMPLE_CALL
354 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
355 || (gimple_code (stmt) == GIMPLE_ASM))
358 if (is_gimple_debug (stmt))
361 if (!stmt_has_simple_data_refs_p (outermost_loop, stmt))
364 switch (gimple_code (stmt))
374 enum tree_code code = gimple_cond_code (stmt);
376 /* We can handle all binary comparisons. Inequalities are
377 also supported as they can be represented with union of
379 if (!(code == LT_EXPR
387 FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES)
388 if (!graphite_can_represent_expr (scop_entry, loop, outermost_loop,
390 /* We can not handle REAL_TYPE. Failed for pr39260. */
391 || TREE_CODE (TREE_TYPE (op)) == REAL_TYPE)
399 enum tree_code code = gimple_assign_rhs_code (stmt);
401 switch (get_gimple_rhs_class (code))
403 case GIMPLE_UNARY_RHS:
404 case GIMPLE_SINGLE_RHS:
405 return (is_simple_operand (gimple_assign_lhs (stmt))
406 && is_simple_operand (gimple_assign_rhs1 (stmt)));
408 case GIMPLE_BINARY_RHS:
409 return (is_simple_operand (gimple_assign_lhs (stmt))
410 && is_simple_operand (gimple_assign_rhs1 (stmt))
411 && is_simple_operand (gimple_assign_rhs2 (stmt)));
413 case GIMPLE_INVALID_RHS:
422 size_t n = gimple_call_num_args (stmt);
423 tree lhs = gimple_call_lhs (stmt);
425 if (lhs && !is_simple_operand (lhs))
428 for (i = 0; i < n; i++)
429 if (!is_simple_operand (gimple_call_arg (stmt, i)))
436 /* These nodes cut a new scope. */
443 /* Returns the statement of BB that contains a harmful operation: that
444 can be a function call with side effects, the induction variables
445 are not linear with respect to SCOP_ENTRY, etc. The current open
446 scop should end before this statement. The evaluation is limited using
447 OUTERMOST_LOOP as outermost loop that may change. */
450 harmful_stmt_in_bb (basic_block scop_entry, loop_p outer_loop, basic_block bb)
452 gimple_stmt_iterator gsi;
454 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
455 if (!stmt_simple_for_scop_p (scop_entry, outer_loop, gsi_stmt (gsi), bb))
456 return gsi_stmt (gsi);
461 /* Return true when it is not possible to represent LOOP in the
462 polyhedral representation. This is evaluated taking SCOP_ENTRY and
463 OUTERMOST_LOOP in mind. */
466 graphite_can_represent_loop (basic_block scop_entry, loop_p outermost_loop,
469 tree niter = number_of_latch_executions (loop);
471 /* Number of iterations unknown. */
472 if (chrec_contains_undetermined (niter))
475 /* Number of iterations not affine. */
476 if (!graphite_can_represent_expr (scop_entry, loop, outermost_loop, niter))
482 /* Store information needed by scopdet_* functions. */
486 /* Exit of the open scop would stop if the current BB is harmful. */
489 /* Where the next scop would start if the current BB is harmful. */
492 /* The bb or one of its children contains open loop exits. That means
493 loop exit nodes that are not surrounded by a loop dominated by bb. */
496 /* The bb or one of its children contains only structures we can handle. */
500 static struct scopdet_info build_scops_1 (basic_block, loop_p,
501 VEC (sd_region, heap) **, loop_p);
503 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
504 to SCOPS. TYPE is the gbb_type of BB. */
506 static struct scopdet_info
507 scopdet_basic_block_info (basic_block bb, loop_p outermost_loop,
508 VEC (sd_region, heap) **scops, gbb_type type)
510 loop_p loop = bb->loop_father;
511 struct scopdet_info result;
514 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
515 basic_block entry_block = ENTRY_BLOCK_PTR;
516 stmt = harmful_stmt_in_bb (entry_block, outermost_loop, bb);
517 result.difficult = (stmt != NULL);
524 result.exits = false;
526 /* Mark bbs terminating a SESE region difficult, if they start
528 if (!single_succ_p (bb))
529 result.difficult = true;
531 result.exit = single_succ (bb);
536 result.next = single_succ (bb);
537 result.exits = false;
538 result.exit = single_succ (bb);
541 case GBB_LOOP_SING_EXIT_HEADER:
543 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
544 struct scopdet_info sinfo;
545 edge exit_e = single_exit (loop);
547 sinfo = build_scops_1 (bb, outermost_loop, ®ions, loop);
549 if (!graphite_can_represent_loop (entry_block, outermost_loop, loop))
550 result.difficult = true;
552 result.difficult |= sinfo.difficult;
554 /* Try again with another loop level. */
556 && loop_depth (outermost_loop) + 1 == loop_depth (loop))
558 outermost_loop = loop;
560 VEC_free (sd_region, heap, regions);
561 regions = VEC_alloc (sd_region, heap, 3);
563 sinfo = scopdet_basic_block_info (bb, outermost_loop, scops, type);
566 result.difficult = true;
569 move_sd_regions (®ions, scops);
573 open_scop.entry = bb;
574 open_scop.exit = exit_e->dest;
575 VEC_safe_push (sd_region, heap, *scops, &open_scop);
576 VEC_free (sd_region, heap, regions);
581 result.exit = exit_e->dest;
582 result.next = exit_e->dest;
584 /* If we do not dominate result.next, remove it. It's either
585 the EXIT_BLOCK_PTR, or another bb dominates it and will
586 call the scop detection for this bb. */
587 if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
590 if (exit_e->src->loop_father != loop)
593 result.exits = false;
595 if (result.difficult)
596 move_sd_regions (®ions, scops);
598 VEC_free (sd_region, heap, regions);
604 case GBB_LOOP_MULT_EXIT_HEADER:
606 /* XXX: For now we just do not join loops with multiple exits. If the
607 exits lead to the same bb it may be possible to join the loop. */
608 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
609 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
612 build_scops_1 (bb, loop, ®ions, loop);
614 /* Scan the code dominated by this loop. This means all bbs, that are
615 are dominated by a bb in this loop, but are not part of this loop.
618 - The loop exit destination is dominated by the exit sources.
620 TODO: We miss here the more complex cases:
621 - The exit destinations are dominated by another bb inside
623 - The loop dominates bbs, that are not exit destinations. */
624 for (i = 0; VEC_iterate (edge, exits, i, e); i++)
625 if (e->src->loop_father == loop
626 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
628 if (loop_outer (outermost_loop))
629 outermost_loop = loop_outer (outermost_loop);
631 /* Pass loop_outer to recognize e->dest as loop header in
633 if (e->dest->loop_father->header == e->dest)
634 build_scops_1 (e->dest, outermost_loop, ®ions,
635 loop_outer (e->dest->loop_father));
637 build_scops_1 (e->dest, outermost_loop, ®ions,
638 e->dest->loop_father);
643 result.difficult = true;
644 result.exits = false;
645 move_sd_regions (®ions, scops);
646 VEC_free (edge, heap, exits);
649 case GBB_COND_HEADER:
651 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
652 struct scopdet_info sinfo;
653 VEC (basic_block, heap) *dominated;
656 basic_block last_exit = NULL;
658 result.exits = false;
660 /* First check the successors of BB, and check if it is
661 possible to join the different branches. */
662 for (i = 0; VEC_iterate (edge, bb->succs, i, e); i++)
664 /* Ignore loop exits. They will be handled after the loop
666 if (is_loop_exit (loop, e->dest))
672 /* Do not follow edges that lead to the end of the
673 conditions block. For example, in
683 the edge from 0 => 6. Only check if all paths lead to
686 if (!single_pred_p (e->dest))
688 /* Check, if edge leads directly to the end of this
693 if (e->dest != last_exit)
694 result.difficult = true;
699 if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
701 result.difficult = true;
705 sinfo = build_scops_1 (e->dest, outermost_loop, ®ions, loop);
707 result.exits |= sinfo.exits;
708 result.difficult |= sinfo.difficult;
710 /* Checks, if all branches end at the same point.
711 If that is true, the condition stays joinable.
712 Have a look at the example above. */
716 last_exit = sinfo.exit;
718 if (sinfo.exit != last_exit)
719 result.difficult = true;
722 result.difficult = true;
726 result.difficult = true;
728 /* Join the branches of the condition if possible. */
729 if (!result.exits && !result.difficult)
731 /* Only return a next pointer if we dominate this pointer.
732 Otherwise it will be handled by the bb dominating it. */
733 if (dominated_by_p (CDI_DOMINATORS, last_exit, bb)
735 result.next = last_exit;
739 result.exit = last_exit;
741 VEC_free (sd_region, heap, regions);
745 /* Scan remaining bbs dominated by BB. */
746 dominated = get_dominated_by (CDI_DOMINATORS, bb);
748 for (i = 0; VEC_iterate (basic_block, dominated, i, dom_bb); i++)
750 /* Ignore loop exits: they will be handled after the loop body. */
751 if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
758 /* Ignore the bbs processed above. */
759 if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
762 if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
763 sinfo = build_scops_1 (dom_bb, outermost_loop, ®ions,
766 sinfo = build_scops_1 (dom_bb, outermost_loop, ®ions, loop);
768 result.exits |= sinfo.exits;
769 result.difficult = true;
773 VEC_free (basic_block, heap, dominated);
776 move_sd_regions (®ions, scops);
788 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
789 SCOPS. The analyse if a sd_region can be handled is based on the value
790 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
791 is the loop in which CURRENT is handled.
793 TODO: These functions got a little bit big. They definitely should be cleaned
796 static struct scopdet_info
797 build_scops_1 (basic_block current, loop_p outermost_loop,
798 VEC (sd_region, heap) **scops, loop_p loop)
800 bool in_scop = false;
802 struct scopdet_info sinfo;
804 /* Initialize result. */
805 struct scopdet_info result;
806 result.exits = false;
807 result.difficult = false;
810 open_scop.entry = NULL;
811 open_scop.exit = NULL;
814 /* Loop over the dominance tree. If we meet a difficult bb, close
815 the current SCoP. Loop and condition header start a new layer,
816 and can only be added if all bbs in deeper layers are simple. */
817 while (current != NULL)
819 sinfo = scopdet_basic_block_info (current, outermost_loop, scops,
820 get_bb_type (current, loop));
822 if (!in_scop && !(sinfo.exits || sinfo.difficult))
824 open_scop.entry = current;
825 open_scop.exit = NULL;
828 else if (in_scop && (sinfo.exits || sinfo.difficult))
830 open_scop.exit = current;
831 VEC_safe_push (sd_region, heap, *scops, &open_scop);
835 result.difficult |= sinfo.difficult;
836 result.exits |= sinfo.exits;
838 current = sinfo.next;
841 /* Try to close open_scop, if we are still in an open SCoP. */
844 open_scop.exit = sinfo.exit;
845 gcc_assert (open_scop.exit);
846 VEC_safe_push (sd_region, heap, *scops, &open_scop);
849 result.exit = sinfo.exit;
853 /* Checks if a bb is contained in REGION. */
856 bb_in_sd_region (basic_block bb, sd_region *region)
858 return bb_in_region (bb, region->entry, region->exit);
861 /* Returns the single entry edge of REGION, if it does not exits NULL. */
864 find_single_entry_edge (sd_region *region)
870 FOR_EACH_EDGE (e, ei, region->entry->preds)
871 if (!bb_in_sd_region (e->src, region))
886 /* Returns the single exit edge of REGION, if it does not exits NULL. */
889 find_single_exit_edge (sd_region *region)
895 FOR_EACH_EDGE (e, ei, region->exit->preds)
896 if (bb_in_sd_region (e->src, region))
911 /* Create a single entry edge for REGION. */
914 create_single_entry_edge (sd_region *region)
916 if (find_single_entry_edge (region))
919 /* There are multiple predecessors for bb_3
932 There are two edges (1->3, 2->3), that point from outside into the region,
933 and another one (5->3), a loop latch, lead to bb_3.
941 | |\ (3.0 -> 3.1) = single entry edge
950 If the loop is part of the SCoP, we have to redirect the loop latches.
956 | | (3.0 -> 3.1) = entry edge
965 if (region->entry->loop_father->header != region->entry
966 || dominated_by_p (CDI_DOMINATORS,
967 loop_latch_edge (region->entry->loop_father)->src,
970 edge forwarder = split_block_after_labels (region->entry);
971 region->entry = forwarder->dest;
974 /* This case is never executed, as the loop headers seem always to have a
975 single edge pointing from outside into the loop. */
978 #ifdef ENABLE_CHECKING
979 gcc_assert (find_single_entry_edge (region));
983 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
986 sd_region_without_exit (edge e)
988 sd_region *r = (sd_region *) e->aux;
991 return r->exit == NULL;
996 /* Create a single exit edge for REGION. */
999 create_single_exit_edge (sd_region *region)
1003 edge forwarder = NULL;
1006 if (find_single_exit_edge (region))
1009 /* We create a forwarder bb (5) for all edges leaving this region
1010 (3->5, 4->5). All other edges leading to the same bb, are moved
1011 to a new bb (6). If these edges where part of another region (2->5)
1012 we update the region->exit pointer, of this region.
1014 To identify which edge belongs to which region we depend on the e->aux
1015 pointer in every edge. It points to the region of the edge or to NULL,
1016 if the edge is not part of any region.
1018 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
1019 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
1024 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
1025 | | \/ 3->5 no region, 4->5 no region,
1027 \| / 5->6 region->exit = 6
1030 Now there is only a single exit edge (5->6). */
1031 exit = region->exit;
1032 region->exit = NULL;
1033 forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
1035 /* Unmark the edges, that are no longer exit edges. */
1036 FOR_EACH_EDGE (e, ei, forwarder->src->preds)
1040 /* Mark the new exit edge. */
1041 single_succ_edge (forwarder->src)->aux = region;
1043 /* Update the exit bb of all regions, where exit edges lead to
1045 FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
1047 ((sd_region *) e->aux)->exit = forwarder->dest;
1049 #ifdef ENABLE_CHECKING
1050 gcc_assert (find_single_exit_edge (region));
1054 /* Unmark the exit edges of all REGIONS.
1055 See comment in "create_single_exit_edge". */
1058 unmark_exit_edges (VEC (sd_region, heap) *regions)
1065 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
1066 FOR_EACH_EDGE (e, ei, s->exit->preds)
1071 /* Mark the exit edges of all REGIONS.
1072 See comment in "create_single_exit_edge". */
1075 mark_exit_edges (VEC (sd_region, heap) *regions)
1082 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
1083 FOR_EACH_EDGE (e, ei, s->exit->preds)
1084 if (bb_in_sd_region (e->src, s))
1088 /* Create for all scop regions a single entry and a single exit edge. */
1091 create_sese_edges (VEC (sd_region, heap) *regions)
1096 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
1097 create_single_entry_edge (s);
1099 mark_exit_edges (regions);
1101 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
1102 create_single_exit_edge (s);
1104 unmark_exit_edges (regions);
1106 fix_loop_structure (NULL);
1108 #ifdef ENABLE_CHECKING
1109 verify_loop_structure ();
1110 verify_dominators (CDI_DOMINATORS);
1115 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1118 build_graphite_scops (VEC (sd_region, heap) *regions,
1119 VEC (scop_p, heap) **scops)
1124 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
1126 edge entry = find_single_entry_edge (s);
1127 edge exit = find_single_exit_edge (s);
1128 scop_p scop = new_scop (new_sese (entry, exit));
1129 VEC_safe_push (scop_p, heap, *scops, scop);
1131 /* Are there overlapping SCoPs? */
1132 #ifdef ENABLE_CHECKING
1137 for (j = 0; VEC_iterate (sd_region, regions, j, s2); j++)
1139 gcc_assert (!bb_in_sd_region (s->entry, s2));
1145 /* Returns true when BB contains only close phi nodes. */
1148 contains_only_close_phi_nodes (basic_block bb)
1150 gimple_stmt_iterator gsi;
1152 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1153 if (gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
1159 /* Print statistics for SCOP to FILE. */
1162 print_graphite_scop_statistics (FILE* file, scop_p scop)
1167 long n_conditions = 0;
1171 long n_p_conditions = 0;
1177 gimple_stmt_iterator psi;
1178 loop_p loop = bb->loop_father;
1180 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
1184 n_p_bbs += bb->count;
1186 if (VEC_length (edge, bb->succs) > 1)
1189 n_p_conditions += bb->count;
1192 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
1195 n_p_stmts += bb->count;
1198 if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
1201 n_p_loops += bb->count;
1206 fprintf (file, "\nBefore limit_scops SCoP statistics (");
1207 fprintf (file, "BBS:%ld, ", n_bbs);
1208 fprintf (file, "LOOPS:%ld, ", n_loops);
1209 fprintf (file, "CONDITIONS:%ld, ", n_conditions);
1210 fprintf (file, "STMTS:%ld)\n", n_stmts);
1211 fprintf (file, "\nBefore limit_scops SCoP profiling statistics (");
1212 fprintf (file, "BBS:%ld, ", n_p_bbs);
1213 fprintf (file, "LOOPS:%ld, ", n_p_loops);
1214 fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
1215 fprintf (file, "STMTS:%ld)\n", n_p_stmts);
1218 /* Print statistics for SCOPS to FILE. */
1221 print_graphite_statistics (FILE* file, VEC (scop_p, heap) *scops)
1226 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
1227 print_graphite_scop_statistics (file, scop);
1230 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1240 * SCoP frontier, as this line is not surrounded by any loop. *
1244 This is necessary as scalar evolution and parameter detection need a
1245 outermost loop to initialize parameters correctly.
1247 TODO: FIX scalar evolution and parameter detection to allow more flexible
1251 limit_scops (VEC (scop_p, heap) **scops)
1253 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
1258 for (i = 0; VEC_iterate (scop_p, *scops, i, scop); i++)
1262 sese region = SCOP_REGION (scop);
1263 build_sese_loop_nests (region);
1265 for (j = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), j, loop); j++)
1266 if (!loop_in_sese_p (loop_outer (loop), region)
1267 && single_exit (loop))
1269 sd_region open_scop;
1270 open_scop.entry = loop->header;
1271 open_scop.exit = single_exit (loop)->dest;
1273 /* This is a hack on top of the limit_scops hack. The
1274 limit_scops hack should disappear all together. */
1275 if (single_succ_p (open_scop.exit)
1276 && contains_only_close_phi_nodes (open_scop.exit))
1277 open_scop.exit = single_succ_edge (open_scop.exit)->dest;
1279 VEC_safe_push (sd_region, heap, regions, &open_scop);
1283 free_scops (*scops);
1284 *scops = VEC_alloc (scop_p, heap, 3);
1286 create_sese_edges (regions);
1287 build_graphite_scops (regions, scops);
1288 VEC_free (sd_region, heap, regions);
1291 /* Transforms LOOP to the canonical loop closed SSA form. */
1294 canonicalize_loop_closed_ssa (loop_p loop)
1296 edge e = single_exit (loop);
1299 if (!e || e->flags & EDGE_ABNORMAL)
1304 if (VEC_length (edge, bb->preds) == 1)
1305 split_block_after_labels (bb);
1308 gimple_stmt_iterator psi;
1309 basic_block close = split_edge (e);
1311 e = single_succ_edge (close);
1313 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1315 gimple phi = gsi_stmt (psi);
1318 for (i = 0; i < gimple_phi_num_args (phi); i++)
1319 if (gimple_phi_arg_edge (phi, i) == e)
1321 tree res, arg = gimple_phi_arg_def (phi, i);
1322 use_operand_p use_p;
1325 if (TREE_CODE (arg) != SSA_NAME)
1328 close_phi = create_phi_node (arg, close);
1329 res = create_new_def_for (gimple_phi_result (close_phi),
1331 gimple_phi_result_ptr (close_phi));
1332 add_phi_arg (close_phi, arg,
1333 gimple_phi_arg_edge (close_phi, 0),
1335 use_p = gimple_phi_arg_imm_use_ptr (phi, i);
1336 replace_exp (use_p, res);
1343 /* Converts the current loop closed SSA form to a canonical form
1344 expected by the Graphite code generation.
1346 The loop closed SSA form has the following invariant: a variable
1347 defined in a loop that is used outside the loop appears only in the
1348 phi nodes in the destination of the loop exit. These phi nodes are
1349 called close phi nodes.
1351 The canonical loop closed SSA form contains the extra invariants:
1353 - when the loop contains only one exit, the close phi nodes contain
1354 only one argument. That implies that the basic block that contains
1355 the close phi nodes has only one predecessor, that is a basic block
1358 - the basic block containing the close phi nodes does not contain
1363 canonicalize_loop_closed_ssa_form (void)
1368 #ifdef ENABLE_CHECKING
1369 verify_loop_closed_ssa ();
1372 FOR_EACH_LOOP (li, loop, 0)
1373 canonicalize_loop_closed_ssa (loop);
1375 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1376 update_ssa (TODO_update_ssa);
1378 #ifdef ENABLE_CHECKING
1379 verify_loop_closed_ssa ();
1383 /* Find Static Control Parts (SCoP) in the current function and pushes
1387 build_scops (VEC (scop_p, heap) **scops)
1389 struct loop *loop = current_loops->tree_root;
1390 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
1392 canonicalize_loop_closed_ssa_form ();
1393 build_scops_1 (single_succ (ENTRY_BLOCK_PTR), ENTRY_BLOCK_PTR->loop_father,
1395 create_sese_edges (regions);
1396 build_graphite_scops (regions, scops);
1398 if (dump_file && (dump_flags & TDF_DETAILS))
1399 print_graphite_statistics (dump_file, *scops);
1401 limit_scops (scops);
1402 VEC_free (sd_region, heap, regions);
1404 if (dump_file && (dump_flags & TDF_DETAILS))
1405 fprintf (dump_file, "\nnumber of SCoPs: %d\n",
1406 VEC_length (scop_p, *scops));
1409 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1410 different colors. If there are not enough colors, paint the
1411 remaining SCoPs in gray.
1414 - "*" after the node number denotes the entry of a SCoP,
1415 - "#" after the node number denotes the exit of a SCoP,
1416 - "()" around the node number denotes the entry or the
1417 exit nodes of the SCOP. These are not part of SCoP. */
1420 dot_all_scops_1 (FILE *file, VEC (scop_p, heap) *scops)
1429 /* Disable debugging while printing graph. */
1430 int tmp_dump_flags = dump_flags;
1433 fprintf (file, "digraph all {\n");
1437 int part_of_scop = false;
1439 /* Use HTML for every bb label. So we are able to print bbs
1440 which are part of two different SCoPs, with two different
1441 background colors. */
1442 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1444 fprintf (file, "CELLSPACING=\"0\">\n");
1446 /* Select color for SCoP. */
1447 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
1449 sese region = SCOP_REGION (scop);
1450 if (bb_in_sese_p (bb, region)
1451 || (SESE_EXIT_BB (region) == bb)
1452 || (SESE_ENTRY_BB (region) == bb))
1465 case 3: /* purple */
1468 case 4: /* orange */
1471 case 5: /* yellow */
1511 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
1513 if (!bb_in_sese_p (bb, region))
1514 fprintf (file, " (");
1516 if (bb == SESE_ENTRY_BB (region)
1517 && bb == SESE_EXIT_BB (region))
1518 fprintf (file, " %d*# ", bb->index);
1519 else if (bb == SESE_ENTRY_BB (region))
1520 fprintf (file, " %d* ", bb->index);
1521 else if (bb == SESE_EXIT_BB (region))
1522 fprintf (file, " %d# ", bb->index);
1524 fprintf (file, " %d ", bb->index);
1526 if (!bb_in_sese_p (bb,region))
1527 fprintf (file, ")");
1529 fprintf (file, "</TD></TR>\n");
1530 part_of_scop = true;
1536 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1537 fprintf (file, " %d </TD></TR>\n", bb->index);
1539 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1544 FOR_EACH_EDGE (e, ei, bb->succs)
1545 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
1548 fputs ("}\n\n", file);
1550 /* Enable debugging again. */
1551 dump_flags = tmp_dump_flags;
1554 /* Display all SCoPs using dotty. */
1557 dot_all_scops (VEC (scop_p, heap) *scops)
1559 /* When debugging, enable the following code. This cannot be used
1560 in production compilers because it calls "system". */
1563 FILE *stream = fopen ("/tmp/allscops.dot", "w");
1564 gcc_assert (stream);
1566 dot_all_scops_1 (stream, scops);
1569 x = system ("dotty /tmp/allscops.dot");
1571 dot_all_scops_1 (stderr, scops);
1575 /* Display all SCoPs using dotty. */
1578 dot_scop (scop_p scop)
1580 VEC (scop_p, heap) *scops = NULL;
1583 VEC_safe_push (scop_p, heap, scops, scop);
1585 /* When debugging, enable the following code. This cannot be used
1586 in production compilers because it calls "system". */
1590 FILE *stream = fopen ("/tmp/allscops.dot", "w");
1591 gcc_assert (stream);
1593 dot_all_scops_1 (stream, scops);
1595 x = system ("dotty /tmp/allscops.dot");
1598 dot_all_scops_1 (stderr, scops);
1601 VEC_free (scop_p, heap, scops);