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 if (TREE_CODE (scev) == POLYNOMIAL_CHREC
218 /* Check for constant strides. With a non constant stride of
219 'n' we would have a value of 'iv * n'. */
220 && (!evolution_function_right_is_integer_cst (scev)
222 /* Check the initial value: 'n * m' cannot be represented. */
223 || !graphite_can_represent_init (scev)))
226 /* Only affine functions can be represented. */
227 if (!scev_is_linear_expression (scev))
230 return evolution_function_is_invariant_p (scev, outermost_loop)
231 || evolution_function_is_affine_multivariate_p (scev, outermost_loop);
235 /* Return true when EXPR can be represented in the polyhedral model.
237 This means an expression can be represented, if it is linear with
238 respect to the loops and the strides are non parametric.
239 LOOP is the place where the expr will be evaluated and OUTERMOST_LOOP
240 defindes the outermost loop that can variate. SCOP_ENTRY defines the
241 entry of the region we analyse. */
244 graphite_can_represent_expr (basic_block scop_entry, loop_p loop,
245 loop_p outermost_loop, tree expr)
247 tree scev = analyze_scalar_evolution (loop, expr);
249 scev = instantiate_scev (scop_entry, loop, scev);
251 return graphite_can_represent_scev (scev, outermost_loop->num);
254 /* Return true if the data references of STMT can be represented by
258 stmt_has_simple_data_refs_p (loop_p outermost_loop, gimple stmt)
264 int loop = outermost_loop->num;
265 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
267 graphite_find_data_references_in_stmt (outermost_loop, stmt, &drs);
269 for (j = 0; VEC_iterate (data_reference_p, drs, j, dr); j++)
270 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
271 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr, i), loop))
278 free_data_refs (drs);
282 /* Return false if the TREE_CODE of the operand OP or any of its operands
283 is a COMPONENT_REF. */
286 exclude_component_ref (tree op)
294 if (TREE_CODE (op) == COMPONENT_REF)
297 len = TREE_OPERAND_LENGTH (op);
298 for (i = 0; i < len; ++i)
299 if (!exclude_component_ref (TREE_OPERAND (op, i)))
305 /* Return true if the operand OP used in STMT is simple in regards to
309 is_simple_operand (tree op)
311 /* It is not a simple operand when it is a declaration or a
313 return !DECL_P (op) && !AGGREGATE_TYPE_P (TREE_TYPE (op))
314 && exclude_component_ref (op);
317 /* Return true only when STMT is simple enough for being handled by
318 Graphite. This depends on SCOP_ENTRY, as the parameters are
319 initialized relatively to this basic block, the linear functions
320 are initialized to OUTERMOST_LOOP and BB is the place where we try
321 to evaluate the STMT. */
324 stmt_simple_for_scop_p (basic_block scop_entry, loop_p outermost_loop,
325 gimple stmt, basic_block bb)
327 loop_p loop = bb->loop_father;
329 gcc_assert (scop_entry);
331 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
332 Calls have side-effects, except those to const or pure
334 if (gimple_has_volatile_ops (stmt)
335 || (gimple_code (stmt) == GIMPLE_CALL
336 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
337 || (gimple_code (stmt) == GIMPLE_ASM))
340 if (is_gimple_debug (stmt))
343 if (!stmt_has_simple_data_refs_p (outermost_loop, stmt))
346 switch (gimple_code (stmt))
356 enum tree_code code = gimple_cond_code (stmt);
358 /* We can handle all binary comparisons. Inequalities are
359 also supported as they can be represented with union of
361 if (!(code == LT_EXPR
369 FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES)
370 if (!graphite_can_represent_expr (scop_entry, loop, outermost_loop,
372 /* We can not handle REAL_TYPE. Failed for pr39260. */
373 || TREE_CODE (TREE_TYPE (op)) == REAL_TYPE)
381 enum tree_code code = gimple_assign_rhs_code (stmt);
383 switch (get_gimple_rhs_class (code))
385 case GIMPLE_UNARY_RHS:
386 case GIMPLE_SINGLE_RHS:
387 return (is_simple_operand (gimple_assign_lhs (stmt))
388 && is_simple_operand (gimple_assign_rhs1 (stmt)));
390 case GIMPLE_BINARY_RHS:
391 return (is_simple_operand (gimple_assign_lhs (stmt))
392 && is_simple_operand (gimple_assign_rhs1 (stmt))
393 && is_simple_operand (gimple_assign_rhs2 (stmt)));
395 case GIMPLE_INVALID_RHS:
404 size_t n = gimple_call_num_args (stmt);
405 tree lhs = gimple_call_lhs (stmt);
407 if (lhs && !is_simple_operand (lhs))
410 for (i = 0; i < n; i++)
411 if (!is_simple_operand (gimple_call_arg (stmt, i)))
418 /* These nodes cut a new scope. */
425 /* Returns the statement of BB that contains a harmful operation: that
426 can be a function call with side effects, the induction variables
427 are not linear with respect to SCOP_ENTRY, etc. The current open
428 scop should end before this statement. The evaluation is limited using
429 OUTERMOST_LOOP as outermost loop that may change. */
432 harmful_stmt_in_bb (basic_block scop_entry, loop_p outer_loop, basic_block bb)
434 gimple_stmt_iterator gsi;
436 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
437 if (!stmt_simple_for_scop_p (scop_entry, outer_loop, gsi_stmt (gsi), bb))
438 return gsi_stmt (gsi);
443 /* Return true when it is not possible to represent LOOP in the
444 polyhedral representation. This is evaluated taking SCOP_ENTRY and
445 OUTERMOST_LOOP in mind. */
448 graphite_can_represent_loop (basic_block scop_entry, loop_p outermost_loop,
451 tree niter = number_of_latch_executions (loop);
453 /* Number of iterations unknown. */
454 if (chrec_contains_undetermined (niter))
457 /* Number of iterations not affine. */
458 if (!graphite_can_represent_expr (scop_entry, loop, outermost_loop, niter))
464 /* Store information needed by scopdet_* functions. */
468 /* Exit of the open scop would stop if the current BB is harmful. */
471 /* Where the next scop would start if the current BB is harmful. */
474 /* The bb or one of its children contains open loop exits. That means
475 loop exit nodes that are not surrounded by a loop dominated by bb. */
478 /* The bb or one of its children contains only structures we can handle. */
482 static struct scopdet_info build_scops_1 (basic_block, loop_p,
483 VEC (sd_region, heap) **, loop_p);
485 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
486 to SCOPS. TYPE is the gbb_type of BB. */
488 static struct scopdet_info
489 scopdet_basic_block_info (basic_block bb, loop_p outermost_loop,
490 VEC (sd_region, heap) **scops, gbb_type type)
492 loop_p loop = bb->loop_father;
493 struct scopdet_info result;
496 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
497 basic_block entry_block = ENTRY_BLOCK_PTR;
498 stmt = harmful_stmt_in_bb (entry_block, outermost_loop, bb);
499 result.difficult = (stmt != NULL);
506 result.exits = false;
508 /* Mark bbs terminating a SESE region difficult, if they start
510 if (!single_succ_p (bb))
511 result.difficult = true;
513 result.exit = single_succ (bb);
518 result.next = single_succ (bb);
519 result.exits = false;
520 result.exit = single_succ (bb);
523 case GBB_LOOP_SING_EXIT_HEADER:
525 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
526 struct scopdet_info sinfo;
527 edge exit_e = single_exit (loop);
529 sinfo = build_scops_1 (bb, outermost_loop, ®ions, loop);
531 if (!graphite_can_represent_loop (entry_block, outermost_loop, loop))
532 result.difficult = true;
534 result.difficult |= sinfo.difficult;
536 /* Try again with another loop level. */
538 && loop_depth (outermost_loop) + 1 == loop_depth (loop))
540 outermost_loop = loop;
542 VEC_free (sd_region, heap, regions);
543 regions = VEC_alloc (sd_region, heap, 3);
545 sinfo = scopdet_basic_block_info (bb, outermost_loop, scops, type);
548 result.difficult = true;
551 move_sd_regions (®ions, scops);
555 open_scop.entry = bb;
556 open_scop.exit = exit_e->dest;
557 VEC_safe_push (sd_region, heap, *scops, &open_scop);
558 VEC_free (sd_region, heap, regions);
563 result.exit = exit_e->dest;
564 result.next = exit_e->dest;
566 /* If we do not dominate result.next, remove it. It's either
567 the EXIT_BLOCK_PTR, or another bb dominates it and will
568 call the scop detection for this bb. */
569 if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
572 if (exit_e->src->loop_father != loop)
575 result.exits = false;
577 if (result.difficult)
578 move_sd_regions (®ions, scops);
580 VEC_free (sd_region, heap, regions);
586 case GBB_LOOP_MULT_EXIT_HEADER:
588 /* XXX: For now we just do not join loops with multiple exits. If the
589 exits lead to the same bb it may be possible to join the loop. */
590 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
591 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
594 build_scops_1 (bb, loop, ®ions, loop);
596 /* Scan the code dominated by this loop. This means all bbs, that are
597 are dominated by a bb in this loop, but are not part of this loop.
600 - The loop exit destination is dominated by the exit sources.
602 TODO: We miss here the more complex cases:
603 - The exit destinations are dominated by another bb inside
605 - The loop dominates bbs, that are not exit destinations. */
606 for (i = 0; VEC_iterate (edge, exits, i, e); i++)
607 if (e->src->loop_father == loop
608 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
610 if (loop_outer (outermost_loop))
611 outermost_loop = loop_outer (outermost_loop);
613 /* Pass loop_outer to recognize e->dest as loop header in
615 if (e->dest->loop_father->header == e->dest)
616 build_scops_1 (e->dest, outermost_loop, ®ions,
617 loop_outer (e->dest->loop_father));
619 build_scops_1 (e->dest, outermost_loop, ®ions,
620 e->dest->loop_father);
625 result.difficult = true;
626 result.exits = false;
627 move_sd_regions (®ions, scops);
628 VEC_free (edge, heap, exits);
631 case GBB_COND_HEADER:
633 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
634 struct scopdet_info sinfo;
635 VEC (basic_block, heap) *dominated;
638 basic_block last_exit = NULL;
640 result.exits = false;
642 /* First check the successors of BB, and check if it is
643 possible to join the different branches. */
644 for (i = 0; VEC_iterate (edge, bb->succs, i, e); i++)
646 /* Ignore loop exits. They will be handled after the loop
648 if (is_loop_exit (loop, e->dest))
654 /* Do not follow edges that lead to the end of the
655 conditions block. For example, in
665 the edge from 0 => 6. Only check if all paths lead to
668 if (!single_pred_p (e->dest))
670 /* Check, if edge leads directly to the end of this
675 if (e->dest != last_exit)
676 result.difficult = true;
681 if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
683 result.difficult = true;
687 sinfo = build_scops_1 (e->dest, outermost_loop, ®ions, loop);
689 result.exits |= sinfo.exits;
690 result.difficult |= sinfo.difficult;
692 /* Checks, if all branches end at the same point.
693 If that is true, the condition stays joinable.
694 Have a look at the example above. */
698 last_exit = sinfo.exit;
700 if (sinfo.exit != last_exit)
701 result.difficult = true;
704 result.difficult = true;
708 result.difficult = true;
710 /* Join the branches of the condition if possible. */
711 if (!result.exits && !result.difficult)
713 /* Only return a next pointer if we dominate this pointer.
714 Otherwise it will be handled by the bb dominating it. */
715 if (dominated_by_p (CDI_DOMINATORS, last_exit, bb)
717 result.next = last_exit;
721 result.exit = last_exit;
723 VEC_free (sd_region, heap, regions);
727 /* Scan remaining bbs dominated by BB. */
728 dominated = get_dominated_by (CDI_DOMINATORS, bb);
730 for (i = 0; VEC_iterate (basic_block, dominated, i, dom_bb); i++)
732 /* Ignore loop exits: they will be handled after the loop body. */
733 if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
740 /* Ignore the bbs processed above. */
741 if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
744 if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
745 sinfo = build_scops_1 (dom_bb, outermost_loop, ®ions,
748 sinfo = build_scops_1 (dom_bb, outermost_loop, ®ions, loop);
750 result.exits |= sinfo.exits;
751 result.difficult = true;
755 VEC_free (basic_block, heap, dominated);
758 move_sd_regions (®ions, scops);
770 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
771 SCOPS. The analyse if a sd_region can be handled is based on the value
772 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
773 is the loop in which CURRENT is handled.
775 TODO: These functions got a little bit big. They definitely should be cleaned
778 static struct scopdet_info
779 build_scops_1 (basic_block current, loop_p outermost_loop,
780 VEC (sd_region, heap) **scops, loop_p loop)
782 bool in_scop = false;
784 struct scopdet_info sinfo;
786 /* Initialize result. */
787 struct scopdet_info result;
788 result.exits = false;
789 result.difficult = false;
792 open_scop.entry = NULL;
793 open_scop.exit = NULL;
796 /* Loop over the dominance tree. If we meet a difficult bb, close
797 the current SCoP. Loop and condition header start a new layer,
798 and can only be added if all bbs in deeper layers are simple. */
799 while (current != NULL)
801 sinfo = scopdet_basic_block_info (current, outermost_loop, scops,
802 get_bb_type (current, loop));
804 if (!in_scop && !(sinfo.exits || sinfo.difficult))
806 open_scop.entry = current;
807 open_scop.exit = NULL;
810 else if (in_scop && (sinfo.exits || sinfo.difficult))
812 open_scop.exit = current;
813 VEC_safe_push (sd_region, heap, *scops, &open_scop);
817 result.difficult |= sinfo.difficult;
818 result.exits |= sinfo.exits;
820 current = sinfo.next;
823 /* Try to close open_scop, if we are still in an open SCoP. */
826 open_scop.exit = sinfo.exit;
827 gcc_assert (open_scop.exit);
828 VEC_safe_push (sd_region, heap, *scops, &open_scop);
831 result.exit = sinfo.exit;
835 /* Checks if a bb is contained in REGION. */
838 bb_in_sd_region (basic_block bb, sd_region *region)
840 return bb_in_region (bb, region->entry, region->exit);
843 /* Returns the single entry edge of REGION, if it does not exits NULL. */
846 find_single_entry_edge (sd_region *region)
852 FOR_EACH_EDGE (e, ei, region->entry->preds)
853 if (!bb_in_sd_region (e->src, region))
868 /* Returns the single exit edge of REGION, if it does not exits NULL. */
871 find_single_exit_edge (sd_region *region)
877 FOR_EACH_EDGE (e, ei, region->exit->preds)
878 if (bb_in_sd_region (e->src, region))
893 /* Create a single entry edge for REGION. */
896 create_single_entry_edge (sd_region *region)
898 if (find_single_entry_edge (region))
901 /* There are multiple predecessors for bb_3
914 There are two edges (1->3, 2->3), that point from outside into the region,
915 and another one (5->3), a loop latch, lead to bb_3.
923 | |\ (3.0 -> 3.1) = single entry edge
932 If the loop is part of the SCoP, we have to redirect the loop latches.
938 | | (3.0 -> 3.1) = entry edge
947 if (region->entry->loop_father->header != region->entry
948 || dominated_by_p (CDI_DOMINATORS,
949 loop_latch_edge (region->entry->loop_father)->src,
952 edge forwarder = split_block_after_labels (region->entry);
953 region->entry = forwarder->dest;
956 /* This case is never executed, as the loop headers seem always to have a
957 single edge pointing from outside into the loop. */
960 #ifdef ENABLE_CHECKING
961 gcc_assert (find_single_entry_edge (region));
965 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
968 sd_region_without_exit (edge e)
970 sd_region *r = (sd_region *) e->aux;
973 return r->exit == NULL;
978 /* Create a single exit edge for REGION. */
981 create_single_exit_edge (sd_region *region)
985 edge forwarder = NULL;
988 if (find_single_exit_edge (region))
991 /* We create a forwarder bb (5) for all edges leaving this region
992 (3->5, 4->5). All other edges leading to the same bb, are moved
993 to a new bb (6). If these edges where part of another region (2->5)
994 we update the region->exit pointer, of this region.
996 To identify which edge belongs to which region we depend on the e->aux
997 pointer in every edge. It points to the region of the edge or to NULL,
998 if the edge is not part of any region.
1000 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
1001 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
1006 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
1007 | | \/ 3->5 no region, 4->5 no region,
1009 \| / 5->6 region->exit = 6
1012 Now there is only a single exit edge (5->6). */
1013 exit = region->exit;
1014 region->exit = NULL;
1015 forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
1017 /* Unmark the edges, that are no longer exit edges. */
1018 FOR_EACH_EDGE (e, ei, forwarder->src->preds)
1022 /* Mark the new exit edge. */
1023 single_succ_edge (forwarder->src)->aux = region;
1025 /* Update the exit bb of all regions, where exit edges lead to
1027 FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
1029 ((sd_region *) e->aux)->exit = forwarder->dest;
1031 #ifdef ENABLE_CHECKING
1032 gcc_assert (find_single_exit_edge (region));
1036 /* Unmark the exit edges of all REGIONS.
1037 See comment in "create_single_exit_edge". */
1040 unmark_exit_edges (VEC (sd_region, heap) *regions)
1047 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
1048 FOR_EACH_EDGE (e, ei, s->exit->preds)
1053 /* Mark the exit edges of all REGIONS.
1054 See comment in "create_single_exit_edge". */
1057 mark_exit_edges (VEC (sd_region, heap) *regions)
1064 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
1065 FOR_EACH_EDGE (e, ei, s->exit->preds)
1066 if (bb_in_sd_region (e->src, s))
1070 /* Create for all scop regions a single entry and a single exit edge. */
1073 create_sese_edges (VEC (sd_region, heap) *regions)
1078 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
1079 create_single_entry_edge (s);
1081 mark_exit_edges (regions);
1083 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
1084 create_single_exit_edge (s);
1086 unmark_exit_edges (regions);
1088 fix_loop_structure (NULL);
1090 #ifdef ENABLE_CHECKING
1091 verify_loop_structure ();
1092 verify_dominators (CDI_DOMINATORS);
1097 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1100 build_graphite_scops (VEC (sd_region, heap) *regions,
1101 VEC (scop_p, heap) **scops)
1106 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
1108 edge entry = find_single_entry_edge (s);
1109 edge exit = find_single_exit_edge (s);
1110 scop_p scop = new_scop (new_sese (entry, exit));
1111 VEC_safe_push (scop_p, heap, *scops, scop);
1113 /* Are there overlapping SCoPs? */
1114 #ifdef ENABLE_CHECKING
1119 for (j = 0; VEC_iterate (sd_region, regions, j, s2); j++)
1121 gcc_assert (!bb_in_sd_region (s->entry, s2));
1127 /* Returns true when BB contains only close phi nodes. */
1130 contains_only_close_phi_nodes (basic_block bb)
1132 gimple_stmt_iterator gsi;
1134 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1135 if (gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
1141 /* Print statistics for SCOP to FILE. */
1144 print_graphite_scop_statistics (FILE* file, scop_p scop)
1149 long n_conditions = 0;
1153 long n_p_conditions = 0;
1159 gimple_stmt_iterator psi;
1160 loop_p loop = bb->loop_father;
1162 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
1166 n_p_bbs += bb->count;
1168 if (VEC_length (edge, bb->succs) > 1)
1171 n_p_conditions += bb->count;
1174 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
1177 n_p_stmts += bb->count;
1180 if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
1183 n_p_loops += bb->count;
1188 fprintf (file, "\nBefore limit_scops SCoP statistics (");
1189 fprintf (file, "BBS:%ld, ", n_bbs);
1190 fprintf (file, "LOOPS:%ld, ", n_loops);
1191 fprintf (file, "CONDITIONS:%ld, ", n_conditions);
1192 fprintf (file, "STMTS:%ld)\n", n_stmts);
1193 fprintf (file, "\nBefore limit_scops SCoP profiling statistics (");
1194 fprintf (file, "BBS:%ld, ", n_p_bbs);
1195 fprintf (file, "LOOPS:%ld, ", n_p_loops);
1196 fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
1197 fprintf (file, "STMTS:%ld)\n", n_p_stmts);
1200 /* Print statistics for SCOPS to FILE. */
1203 print_graphite_statistics (FILE* file, VEC (scop_p, heap) *scops)
1208 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
1209 print_graphite_scop_statistics (file, scop);
1212 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1222 * SCoP frontier, as this line is not surrounded by any loop. *
1226 This is necessary as scalar evolution and parameter detection need a
1227 outermost loop to initialize parameters correctly.
1229 TODO: FIX scalar evolution and parameter detection to allow more flexible
1233 limit_scops (VEC (scop_p, heap) **scops)
1235 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
1240 for (i = 0; VEC_iterate (scop_p, *scops, i, scop); i++)
1244 sese region = SCOP_REGION (scop);
1245 build_sese_loop_nests (region);
1247 for (j = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), j, loop); j++)
1248 if (!loop_in_sese_p (loop_outer (loop), region)
1249 && single_exit (loop))
1251 sd_region open_scop;
1252 open_scop.entry = loop->header;
1253 open_scop.exit = single_exit (loop)->dest;
1255 /* This is a hack on top of the limit_scops hack. The
1256 limit_scops hack should disappear all together. */
1257 if (single_succ_p (open_scop.exit)
1258 && contains_only_close_phi_nodes (open_scop.exit))
1259 open_scop.exit = single_succ_edge (open_scop.exit)->dest;
1261 VEC_safe_push (sd_region, heap, regions, &open_scop);
1265 free_scops (*scops);
1266 *scops = VEC_alloc (scop_p, heap, 3);
1268 create_sese_edges (regions);
1269 build_graphite_scops (regions, scops);
1270 VEC_free (sd_region, heap, regions);
1273 /* Transforms LOOP to the canonical loop closed SSA form. */
1276 canonicalize_loop_closed_ssa (loop_p loop)
1278 edge e = single_exit (loop);
1281 if (!e || e->flags & EDGE_ABNORMAL)
1286 if (VEC_length (edge, bb->preds) == 1)
1287 split_block_after_labels (bb);
1290 gimple_stmt_iterator psi;
1291 basic_block close = split_edge (e);
1293 e = single_succ_edge (close);
1295 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1297 gimple phi = gsi_stmt (psi);
1300 for (i = 0; i < gimple_phi_num_args (phi); i++)
1301 if (gimple_phi_arg_edge (phi, i) == e)
1303 tree res, arg = gimple_phi_arg_def (phi, i);
1304 use_operand_p use_p;
1307 if (TREE_CODE (arg) != SSA_NAME)
1310 close_phi = create_phi_node (arg, close);
1311 res = create_new_def_for (gimple_phi_result (close_phi),
1313 gimple_phi_result_ptr (close_phi));
1314 add_phi_arg (close_phi, arg,
1315 gimple_phi_arg_edge (close_phi, 0),
1317 use_p = gimple_phi_arg_imm_use_ptr (phi, i);
1318 replace_exp (use_p, res);
1325 /* Converts the current loop closed SSA form to a canonical form
1326 expected by the Graphite code generation.
1328 The loop closed SSA form has the following invariant: a variable
1329 defined in a loop that is used outside the loop appears only in the
1330 phi nodes in the destination of the loop exit. These phi nodes are
1331 called close phi nodes.
1333 The canonical loop closed SSA form contains the extra invariants:
1335 - when the loop contains only one exit, the close phi nodes contain
1336 only one argument. That implies that the basic block that contains
1337 the close phi nodes has only one predecessor, that is a basic block
1340 - the basic block containing the close phi nodes does not contain
1345 canonicalize_loop_closed_ssa_form (void)
1350 #ifdef ENABLE_CHECKING
1351 verify_loop_closed_ssa ();
1354 FOR_EACH_LOOP (li, loop, 0)
1355 canonicalize_loop_closed_ssa (loop);
1357 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1358 update_ssa (TODO_update_ssa);
1360 #ifdef ENABLE_CHECKING
1361 verify_loop_closed_ssa ();
1365 /* Find Static Control Parts (SCoP) in the current function and pushes
1369 build_scops (VEC (scop_p, heap) **scops)
1371 struct loop *loop = current_loops->tree_root;
1372 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
1374 canonicalize_loop_closed_ssa_form ();
1375 build_scops_1 (single_succ (ENTRY_BLOCK_PTR), ENTRY_BLOCK_PTR->loop_father,
1377 create_sese_edges (regions);
1378 build_graphite_scops (regions, scops);
1380 if (dump_file && (dump_flags & TDF_DETAILS))
1381 print_graphite_statistics (dump_file, *scops);
1383 limit_scops (scops);
1384 VEC_free (sd_region, heap, regions);
1386 if (dump_file && (dump_flags & TDF_DETAILS))
1387 fprintf (dump_file, "\nnumber of SCoPs: %d\n",
1388 VEC_length (scop_p, *scops));
1391 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1392 different colors. If there are not enough colors, paint the
1393 remaining SCoPs in gray.
1396 - "*" after the node number denotes the entry of a SCoP,
1397 - "#" after the node number denotes the exit of a SCoP,
1398 - "()" around the node number denotes the entry or the
1399 exit nodes of the SCOP. These are not part of SCoP. */
1402 dot_all_scops_1 (FILE *file, VEC (scop_p, heap) *scops)
1411 /* Disable debugging while printing graph. */
1412 int tmp_dump_flags = dump_flags;
1415 fprintf (file, "digraph all {\n");
1419 int part_of_scop = false;
1421 /* Use HTML for every bb label. So we are able to print bbs
1422 which are part of two different SCoPs, with two different
1423 background colors. */
1424 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1426 fprintf (file, "CELLSPACING=\"0\">\n");
1428 /* Select color for SCoP. */
1429 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
1431 sese region = SCOP_REGION (scop);
1432 if (bb_in_sese_p (bb, region)
1433 || (SESE_EXIT_BB (region) == bb)
1434 || (SESE_ENTRY_BB (region) == bb))
1447 case 3: /* purple */
1450 case 4: /* orange */
1453 case 5: /* yellow */
1493 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
1495 if (!bb_in_sese_p (bb, region))
1496 fprintf (file, " (");
1498 if (bb == SESE_ENTRY_BB (region)
1499 && bb == SESE_EXIT_BB (region))
1500 fprintf (file, " %d*# ", bb->index);
1501 else if (bb == SESE_ENTRY_BB (region))
1502 fprintf (file, " %d* ", bb->index);
1503 else if (bb == SESE_EXIT_BB (region))
1504 fprintf (file, " %d# ", bb->index);
1506 fprintf (file, " %d ", bb->index);
1508 if (!bb_in_sese_p (bb,region))
1509 fprintf (file, ")");
1511 fprintf (file, "</TD></TR>\n");
1512 part_of_scop = true;
1518 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1519 fprintf (file, " %d </TD></TR>\n", bb->index);
1521 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1526 FOR_EACH_EDGE (e, ei, bb->succs)
1527 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
1530 fputs ("}\n\n", file);
1532 /* Enable debugging again. */
1533 dump_flags = tmp_dump_flags;
1536 /* Display all SCoPs using dotty. */
1539 dot_all_scops (VEC (scop_p, heap) *scops)
1541 /* When debugging, enable the following code. This cannot be used
1542 in production compilers because it calls "system". */
1545 FILE *stream = fopen ("/tmp/allscops.dot", "w");
1546 gcc_assert (stream);
1548 dot_all_scops_1 (stream, scops);
1551 x = system ("dotty /tmp/allscops.dot");
1553 dot_all_scops_1 (stderr, scops);
1557 /* Display all SCoPs using dotty. */
1560 dot_scop (scop_p scop)
1562 VEC (scop_p, heap) *scops = NULL;
1565 VEC_safe_push (scop_p, heap, scops, scop);
1567 /* When debugging, enable the following code. This cannot be used
1568 in production compilers because it calls "system". */
1572 FILE *stream = fopen ("/tmp/allscops.dot", "w");
1573 gcc_assert (stream);
1575 dot_all_scops_1 (stream, scops);
1577 x = system ("dotty /tmp/allscops.dot");
1580 dot_all_scops_1 (stderr, scops);
1583 VEC_free (scop_p, heap, scops);