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"
25 #include "tree-flow.h"
27 #include "tree-chrec.h"
28 #include "tree-data-ref.h"
29 #include "tree-scalar-evolution.h"
30 #include "tree-pass.h"
35 #include "graphite-ppl.h"
36 #include "graphite-poly.h"
37 #include "graphite-scop-detection.h"
39 /* The type of the analyzed basic block. */
41 typedef enum gbb_type {
43 GBB_LOOP_SING_EXIT_HEADER,
44 GBB_LOOP_MULT_EXIT_HEADER,
51 /* Detect the type of BB. Loop headers are only marked, if they are
52 new. This means their loop_father is different to LAST_LOOP.
53 Otherwise they are treated like any other bb and their type can be
57 get_bb_type (basic_block bb, struct loop *last_loop)
59 VEC (basic_block, heap) *dom;
61 struct loop *loop = bb->loop_father;
63 /* Check, if we entry into a new loop. */
64 if (loop != last_loop)
66 if (single_exit (loop) != NULL)
67 return GBB_LOOP_SING_EXIT_HEADER;
68 else if (loop->num != 0)
69 return GBB_LOOP_MULT_EXIT_HEADER;
71 return GBB_COND_HEADER;
74 dom = get_dominated_by (CDI_DOMINATORS, bb);
75 nb_dom = VEC_length (basic_block, dom);
76 VEC_free (basic_block, heap, dom);
81 nb_suc = VEC_length (edge, bb->succs);
83 if (nb_dom == 1 && nb_suc == 1)
86 return GBB_COND_HEADER;
89 /* A SCoP detection region, defined using bbs as borders.
91 All control flow touching this region, comes in passing basic_block
92 ENTRY and leaves passing basic_block EXIT. By using bbs instead of
93 edges for the borders we are able to represent also regions that do
94 not have a single entry or exit edge.
96 But as they have a single entry basic_block and a single exit
97 basic_block, we are able to generate for every sd_region a single
105 / \ This region contains: {3, 4, 5, 6, 7, 8}
113 typedef struct sd_region_p
115 /* The entry bb dominates all bbs in the sd_region. It is part of
119 /* The exit bb postdominates all bbs in the sd_region, but is not
120 part of the region. */
124 DEF_VEC_O(sd_region);
125 DEF_VEC_ALLOC_O(sd_region, heap);
128 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
131 move_sd_regions (VEC (sd_region, heap) **source,
132 VEC (sd_region, heap) **target)
137 FOR_EACH_VEC_ELT (sd_region, *source, i, s)
138 VEC_safe_push (sd_region, heap, *target, s);
140 VEC_free (sd_region, heap, *source);
143 /* Something like "n * m" is not allowed. */
146 graphite_can_represent_init (tree e)
148 switch (TREE_CODE (e))
150 case POLYNOMIAL_CHREC:
151 return graphite_can_represent_init (CHREC_LEFT (e))
152 && graphite_can_represent_init (CHREC_RIGHT (e));
155 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
156 return graphite_can_represent_init (TREE_OPERAND (e, 0))
157 && host_integerp (TREE_OPERAND (e, 1), 0);
159 return graphite_can_represent_init (TREE_OPERAND (e, 1))
160 && host_integerp (TREE_OPERAND (e, 0), 0);
163 case POINTER_PLUS_EXPR:
165 return graphite_can_represent_init (TREE_OPERAND (e, 0))
166 && graphite_can_represent_init (TREE_OPERAND (e, 1));
171 case NON_LVALUE_EXPR:
172 return graphite_can_represent_init (TREE_OPERAND (e, 0));
181 /* Return true when SCEV can be represented in the polyhedral model.
183 An expression can be represented, if it can be expressed as an
184 affine expression. For loops (i, j) and parameters (m, n) all
185 affine expressions are of the form:
187 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
189 1 i + 20 j + (-2) m + 25
191 Something like "i * n" or "n * m" is not allowed. */
194 graphite_can_represent_scev (tree scev)
196 if (chrec_contains_undetermined (scev))
199 switch (TREE_CODE (scev))
203 return graphite_can_represent_scev (TREE_OPERAND (scev, 0))
204 && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
207 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
208 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
209 && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
210 && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
211 && graphite_can_represent_init (scev)
212 && graphite_can_represent_scev (TREE_OPERAND (scev, 0))
213 && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
215 case POLYNOMIAL_CHREC:
216 /* Check for constant strides. With a non constant stride of
217 'n' we would have a value of 'iv * n'. Also check that the
218 initial value can represented: for example 'n * m' cannot be
220 if (!evolution_function_right_is_integer_cst (scev)
221 || !graphite_can_represent_init (scev))
228 /* Only affine functions can be represented. */
229 if (!scev_is_linear_expression (scev))
236 /* Return true when EXPR can be represented in the polyhedral model.
238 This means an expression can be represented, if it is linear with
239 respect to the loops and the strides are non parametric.
240 LOOP is the place where the expr will be evaluated. SCOP_ENTRY defines the
241 entry of the region we analyse. */
244 graphite_can_represent_expr (basic_block scop_entry, loop_p loop,
247 tree scev = analyze_scalar_evolution (loop, expr);
249 scev = instantiate_scev (scop_entry, loop, scev);
251 return graphite_can_represent_scev (scev);
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 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
266 graphite_find_data_references_in_stmt (outermost_loop, stmt, &drs);
268 FOR_EACH_VEC_ELT (data_reference_p, drs, j, dr)
269 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
270 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr, i)))
277 free_data_refs (drs);
281 /* Return true only when STMT is simple enough for being handled by
282 Graphite. This depends on SCOP_ENTRY, as the parameters are
283 initialized relatively to this basic block, the linear functions
284 are initialized to OUTERMOST_LOOP and BB is the place where we try
285 to evaluate the STMT. */
288 stmt_simple_for_scop_p (basic_block scop_entry, loop_p outermost_loop,
289 gimple stmt, basic_block bb)
291 loop_p loop = bb->loop_father;
293 gcc_assert (scop_entry);
295 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
296 Calls have side-effects, except those to const or pure
298 if (gimple_has_volatile_ops (stmt)
299 || (gimple_code (stmt) == GIMPLE_CALL
300 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
301 || (gimple_code (stmt) == GIMPLE_ASM))
304 if (is_gimple_debug (stmt))
307 if (!stmt_has_simple_data_refs_p (outermost_loop, stmt))
310 switch (gimple_code (stmt))
320 enum tree_code code = gimple_cond_code (stmt);
322 /* We can handle all binary comparisons. Inequalities are
323 also supported as they can be represented with union of
325 if (!(code == LT_EXPR
333 FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES)
334 if (!graphite_can_represent_expr (scop_entry, loop, op)
335 /* We can not handle REAL_TYPE. Failed for pr39260. */
336 || TREE_CODE (TREE_TYPE (op)) == REAL_TYPE)
347 /* These nodes cut a new scope. */
354 /* Returns the statement of BB that contains a harmful operation: that
355 can be a function call with side effects, the induction variables
356 are not linear with respect to SCOP_ENTRY, etc. The current open
357 scop should end before this statement. The evaluation is limited using
358 OUTERMOST_LOOP as outermost loop that may change. */
361 harmful_stmt_in_bb (basic_block scop_entry, loop_p outer_loop, basic_block bb)
363 gimple_stmt_iterator gsi;
365 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
366 if (!stmt_simple_for_scop_p (scop_entry, outer_loop, gsi_stmt (gsi), bb))
367 return gsi_stmt (gsi);
372 /* Return true if LOOP can be represented in the polyhedral
373 representation. This is evaluated taking SCOP_ENTRY and
374 OUTERMOST_LOOP in mind. */
377 graphite_can_represent_loop (basic_block scop_entry, loop_p loop)
379 tree niter = number_of_latch_executions (loop);
381 /* Number of iterations unknown. */
382 if (chrec_contains_undetermined (niter))
385 /* Number of iterations not affine. */
386 if (!graphite_can_represent_expr (scop_entry, loop, niter))
392 /* Store information needed by scopdet_* functions. */
396 /* Exit of the open scop would stop if the current BB is harmful. */
399 /* Where the next scop would start if the current BB is harmful. */
402 /* The bb or one of its children contains open loop exits. That means
403 loop exit nodes that are not surrounded by a loop dominated by bb. */
406 /* The bb or one of its children contains only structures we can handle. */
410 static struct scopdet_info build_scops_1 (basic_block, loop_p,
411 VEC (sd_region, heap) **, loop_p);
413 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
414 to SCOPS. TYPE is the gbb_type of BB. */
416 static struct scopdet_info
417 scopdet_basic_block_info (basic_block bb, loop_p outermost_loop,
418 VEC (sd_region, heap) **scops, gbb_type type)
420 loop_p loop = bb->loop_father;
421 struct scopdet_info result;
424 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
425 basic_block entry_block = ENTRY_BLOCK_PTR;
426 stmt = harmful_stmt_in_bb (entry_block, outermost_loop, bb);
427 result.difficult = (stmt != NULL);
434 result.exits = false;
436 /* Mark bbs terminating a SESE region difficult, if they start
438 if (!single_succ_p (bb))
439 result.difficult = true;
441 result.exit = single_succ (bb);
446 result.next = single_succ (bb);
447 result.exits = false;
448 result.exit = single_succ (bb);
451 case GBB_LOOP_SING_EXIT_HEADER:
453 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
454 struct scopdet_info sinfo;
455 edge exit_e = single_exit (loop);
457 sinfo = build_scops_1 (bb, outermost_loop, ®ions, loop);
459 if (!graphite_can_represent_loop (entry_block, loop))
460 result.difficult = true;
462 result.difficult |= sinfo.difficult;
464 /* Try again with another loop level. */
466 && loop_depth (outermost_loop) + 1 == loop_depth (loop))
468 outermost_loop = loop;
470 VEC_free (sd_region, heap, regions);
471 regions = VEC_alloc (sd_region, heap, 3);
473 sinfo = scopdet_basic_block_info (bb, outermost_loop, scops, type);
476 result.difficult = true;
479 move_sd_regions (®ions, scops);
483 open_scop.entry = bb;
484 open_scop.exit = exit_e->dest;
485 VEC_safe_push (sd_region, heap, *scops, &open_scop);
486 VEC_free (sd_region, heap, regions);
491 result.exit = exit_e->dest;
492 result.next = exit_e->dest;
494 /* If we do not dominate result.next, remove it. It's either
495 the EXIT_BLOCK_PTR, or another bb dominates it and will
496 call the scop detection for this bb. */
497 if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
500 if (exit_e->src->loop_father != loop)
503 result.exits = false;
505 if (result.difficult)
506 move_sd_regions (®ions, scops);
508 VEC_free (sd_region, heap, regions);
514 case GBB_LOOP_MULT_EXIT_HEADER:
516 /* XXX: For now we just do not join loops with multiple exits. If the
517 exits lead to the same bb it may be possible to join the loop. */
518 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
519 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
522 build_scops_1 (bb, loop, ®ions, loop);
524 /* Scan the code dominated by this loop. This means all bbs, that are
525 are dominated by a bb in this loop, but are not part of this loop.
528 - The loop exit destination is dominated by the exit sources.
530 TODO: We miss here the more complex cases:
531 - The exit destinations are dominated by another bb inside
533 - The loop dominates bbs, that are not exit destinations. */
534 FOR_EACH_VEC_ELT (edge, exits, i, e)
535 if (e->src->loop_father == loop
536 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
538 if (loop_outer (outermost_loop))
539 outermost_loop = loop_outer (outermost_loop);
541 /* Pass loop_outer to recognize e->dest as loop header in
543 if (e->dest->loop_father->header == e->dest)
544 build_scops_1 (e->dest, outermost_loop, ®ions,
545 loop_outer (e->dest->loop_father));
547 build_scops_1 (e->dest, outermost_loop, ®ions,
548 e->dest->loop_father);
553 result.difficult = true;
554 result.exits = false;
555 move_sd_regions (®ions, scops);
556 VEC_free (edge, heap, exits);
559 case GBB_COND_HEADER:
561 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
562 struct scopdet_info sinfo;
563 VEC (basic_block, heap) *dominated;
566 basic_block last_exit = NULL;
568 result.exits = false;
570 /* First check the successors of BB, and check if it is
571 possible to join the different branches. */
572 FOR_EACH_VEC_ELT (edge, bb->succs, i, e)
574 /* Ignore loop exits. They will be handled after the loop
576 if (loop_exits_to_bb_p (loop, e->dest))
582 /* Do not follow edges that lead to the end of the
583 conditions block. For example, in
593 the edge from 0 => 6. Only check if all paths lead to
596 if (!single_pred_p (e->dest))
598 /* Check, if edge leads directly to the end of this
603 if (e->dest != last_exit)
604 result.difficult = true;
609 if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
611 result.difficult = true;
615 sinfo = build_scops_1 (e->dest, outermost_loop, ®ions, loop);
617 result.exits |= sinfo.exits;
618 result.difficult |= sinfo.difficult;
620 /* Checks, if all branches end at the same point.
621 If that is true, the condition stays joinable.
622 Have a look at the example above. */
626 last_exit = sinfo.exit;
628 if (sinfo.exit != last_exit)
629 result.difficult = true;
632 result.difficult = true;
636 result.difficult = true;
638 /* Join the branches of the condition if possible. */
639 if (!result.exits && !result.difficult)
641 /* Only return a next pointer if we dominate this pointer.
642 Otherwise it will be handled by the bb dominating it. */
643 if (dominated_by_p (CDI_DOMINATORS, last_exit, bb)
645 result.next = last_exit;
649 result.exit = last_exit;
651 VEC_free (sd_region, heap, regions);
655 /* Scan remaining bbs dominated by BB. */
656 dominated = get_dominated_by (CDI_DOMINATORS, bb);
658 FOR_EACH_VEC_ELT (basic_block, dominated, i, dom_bb)
660 /* Ignore loop exits: they will be handled after the loop body. */
661 if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
668 /* Ignore the bbs processed above. */
669 if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
672 if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
673 sinfo = build_scops_1 (dom_bb, outermost_loop, ®ions,
676 sinfo = build_scops_1 (dom_bb, outermost_loop, ®ions, loop);
678 result.exits |= sinfo.exits;
679 result.difficult = true;
683 VEC_free (basic_block, heap, dominated);
686 move_sd_regions (®ions, scops);
698 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
699 SCOPS. The analyse if a sd_region can be handled is based on the value
700 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
701 is the loop in which CURRENT is handled.
703 TODO: These functions got a little bit big. They definitely should be cleaned
706 static struct scopdet_info
707 build_scops_1 (basic_block current, loop_p outermost_loop,
708 VEC (sd_region, heap) **scops, loop_p loop)
710 bool in_scop = false;
712 struct scopdet_info sinfo;
714 /* Initialize result. */
715 struct scopdet_info result;
716 result.exits = false;
717 result.difficult = false;
720 open_scop.entry = NULL;
721 open_scop.exit = NULL;
724 /* Loop over the dominance tree. If we meet a difficult bb, close
725 the current SCoP. Loop and condition header start a new layer,
726 and can only be added if all bbs in deeper layers are simple. */
727 while (current != NULL)
729 sinfo = scopdet_basic_block_info (current, outermost_loop, scops,
730 get_bb_type (current, loop));
732 if (!in_scop && !(sinfo.exits || sinfo.difficult))
734 open_scop.entry = current;
735 open_scop.exit = NULL;
738 else if (in_scop && (sinfo.exits || sinfo.difficult))
740 open_scop.exit = current;
741 VEC_safe_push (sd_region, heap, *scops, &open_scop);
745 result.difficult |= sinfo.difficult;
746 result.exits |= sinfo.exits;
748 current = sinfo.next;
751 /* Try to close open_scop, if we are still in an open SCoP. */
754 open_scop.exit = sinfo.exit;
755 gcc_assert (open_scop.exit);
756 VEC_safe_push (sd_region, heap, *scops, &open_scop);
759 result.exit = sinfo.exit;
763 /* Checks if a bb is contained in REGION. */
766 bb_in_sd_region (basic_block bb, sd_region *region)
768 return bb_in_region (bb, region->entry, region->exit);
771 /* Returns the single entry edge of REGION, if it does not exits NULL. */
774 find_single_entry_edge (sd_region *region)
780 FOR_EACH_EDGE (e, ei, region->entry->preds)
781 if (!bb_in_sd_region (e->src, region))
796 /* Returns the single exit edge of REGION, if it does not exits NULL. */
799 find_single_exit_edge (sd_region *region)
805 FOR_EACH_EDGE (e, ei, region->exit->preds)
806 if (bb_in_sd_region (e->src, region))
821 /* Create a single entry edge for REGION. */
824 create_single_entry_edge (sd_region *region)
826 if (find_single_entry_edge (region))
829 /* There are multiple predecessors for bb_3
842 There are two edges (1->3, 2->3), that point from outside into the region,
843 and another one (5->3), a loop latch, lead to bb_3.
851 | |\ (3.0 -> 3.1) = single entry edge
860 If the loop is part of the SCoP, we have to redirect the loop latches.
866 | | (3.0 -> 3.1) = entry edge
875 if (region->entry->loop_father->header != region->entry
876 || dominated_by_p (CDI_DOMINATORS,
877 loop_latch_edge (region->entry->loop_father)->src,
880 edge forwarder = split_block_after_labels (region->entry);
881 region->entry = forwarder->dest;
884 /* This case is never executed, as the loop headers seem always to have a
885 single edge pointing from outside into the loop. */
888 gcc_checking_assert (find_single_entry_edge (region));
891 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
894 sd_region_without_exit (edge e)
896 sd_region *r = (sd_region *) e->aux;
899 return r->exit == NULL;
904 /* Create a single exit edge for REGION. */
907 create_single_exit_edge (sd_region *region)
911 edge forwarder = NULL;
914 /* We create a forwarder bb (5) for all edges leaving this region
915 (3->5, 4->5). All other edges leading to the same bb, are moved
916 to a new bb (6). If these edges where part of another region (2->5)
917 we update the region->exit pointer, of this region.
919 To identify which edge belongs to which region we depend on the e->aux
920 pointer in every edge. It points to the region of the edge or to NULL,
921 if the edge is not part of any region.
923 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
924 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
929 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
930 | | \/ 3->5 no region, 4->5 no region,
932 \| / 5->6 region->exit = 6
935 Now there is only a single exit edge (5->6). */
938 forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
940 /* Unmark the edges, that are no longer exit edges. */
941 FOR_EACH_EDGE (e, ei, forwarder->src->preds)
945 /* Mark the new exit edge. */
946 single_succ_edge (forwarder->src)->aux = region;
948 /* Update the exit bb of all regions, where exit edges lead to
950 FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
952 ((sd_region *) e->aux)->exit = forwarder->dest;
954 gcc_checking_assert (find_single_exit_edge (region));
957 /* Unmark the exit edges of all REGIONS.
958 See comment in "create_single_exit_edge". */
961 unmark_exit_edges (VEC (sd_region, heap) *regions)
968 FOR_EACH_VEC_ELT (sd_region, regions, i, s)
969 FOR_EACH_EDGE (e, ei, s->exit->preds)
974 /* Mark the exit edges of all REGIONS.
975 See comment in "create_single_exit_edge". */
978 mark_exit_edges (VEC (sd_region, heap) *regions)
985 FOR_EACH_VEC_ELT (sd_region, regions, i, s)
986 FOR_EACH_EDGE (e, ei, s->exit->preds)
987 if (bb_in_sd_region (e->src, s))
991 /* Create for all scop regions a single entry and a single exit edge. */
994 create_sese_edges (VEC (sd_region, heap) *regions)
999 FOR_EACH_VEC_ELT (sd_region, regions, i, s)
1000 create_single_entry_edge (s);
1002 mark_exit_edges (regions);
1004 FOR_EACH_VEC_ELT (sd_region, regions, i, s)
1005 /* Don't handle multiple edges exiting the function. */
1006 if (!find_single_exit_edge (s)
1007 && s->exit != EXIT_BLOCK_PTR)
1008 create_single_exit_edge (s);
1010 unmark_exit_edges (regions);
1012 fix_loop_structure (NULL);
1014 #ifdef ENABLE_CHECKING
1015 verify_loop_structure ();
1016 verify_dominators (CDI_DOMINATORS);
1021 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1024 build_graphite_scops (VEC (sd_region, heap) *regions,
1025 VEC (scop_p, heap) **scops)
1030 FOR_EACH_VEC_ELT (sd_region, regions, i, s)
1032 edge entry = find_single_entry_edge (s);
1033 edge exit = find_single_exit_edge (s);
1039 scop = new_scop (new_sese (entry, exit));
1040 VEC_safe_push (scop_p, heap, *scops, scop);
1042 /* Are there overlapping SCoPs? */
1043 #ifdef ENABLE_CHECKING
1048 FOR_EACH_VEC_ELT (sd_region, regions, j, s2)
1050 gcc_assert (!bb_in_sd_region (s->entry, s2));
1056 /* Returns true when BB contains only close phi nodes. */
1059 contains_only_close_phi_nodes (basic_block bb)
1061 gimple_stmt_iterator gsi;
1063 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1064 if (gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
1070 /* Print statistics for SCOP to FILE. */
1073 print_graphite_scop_statistics (FILE* file, scop_p scop)
1078 long n_conditions = 0;
1082 long n_p_conditions = 0;
1088 gimple_stmt_iterator psi;
1089 loop_p loop = bb->loop_father;
1091 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
1095 n_p_bbs += bb->count;
1097 if (VEC_length (edge, bb->succs) > 1)
1100 n_p_conditions += bb->count;
1103 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
1106 n_p_stmts += bb->count;
1109 if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
1112 n_p_loops += bb->count;
1117 fprintf (file, "\nBefore limit_scops SCoP statistics (");
1118 fprintf (file, "BBS:%ld, ", n_bbs);
1119 fprintf (file, "LOOPS:%ld, ", n_loops);
1120 fprintf (file, "CONDITIONS:%ld, ", n_conditions);
1121 fprintf (file, "STMTS:%ld)\n", n_stmts);
1122 fprintf (file, "\nBefore limit_scops SCoP profiling statistics (");
1123 fprintf (file, "BBS:%ld, ", n_p_bbs);
1124 fprintf (file, "LOOPS:%ld, ", n_p_loops);
1125 fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
1126 fprintf (file, "STMTS:%ld)\n", n_p_stmts);
1129 /* Print statistics for SCOPS to FILE. */
1132 print_graphite_statistics (FILE* file, VEC (scop_p, heap) *scops)
1137 FOR_EACH_VEC_ELT (scop_p, scops, i, scop)
1138 print_graphite_scop_statistics (file, scop);
1141 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1151 * SCoP frontier, as this line is not surrounded by any loop. *
1155 This is necessary as scalar evolution and parameter detection need a
1156 outermost loop to initialize parameters correctly.
1158 TODO: FIX scalar evolution and parameter detection to allow more flexible
1162 limit_scops (VEC (scop_p, heap) **scops)
1164 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
1169 FOR_EACH_VEC_ELT (scop_p, *scops, i, scop)
1173 sese region = SCOP_REGION (scop);
1174 build_sese_loop_nests (region);
1176 FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), j, loop)
1177 if (!loop_in_sese_p (loop_outer (loop), region)
1178 && single_exit (loop))
1180 sd_region open_scop;
1181 open_scop.entry = loop->header;
1182 open_scop.exit = single_exit (loop)->dest;
1184 /* This is a hack on top of the limit_scops hack. The
1185 limit_scops hack should disappear all together. */
1186 if (single_succ_p (open_scop.exit)
1187 && contains_only_close_phi_nodes (open_scop.exit))
1188 open_scop.exit = single_succ_edge (open_scop.exit)->dest;
1190 VEC_safe_push (sd_region, heap, regions, &open_scop);
1194 free_scops (*scops);
1195 *scops = VEC_alloc (scop_p, heap, 3);
1197 create_sese_edges (regions);
1198 build_graphite_scops (regions, scops);
1199 VEC_free (sd_region, heap, regions);
1202 /* Transforms LOOP to the canonical loop closed SSA form. */
1205 canonicalize_loop_closed_ssa (loop_p loop)
1207 edge e = single_exit (loop);
1210 if (!e || e->flags & EDGE_ABNORMAL)
1215 if (VEC_length (edge, bb->preds) == 1)
1216 split_block_after_labels (bb);
1219 gimple_stmt_iterator psi;
1220 basic_block close = split_edge (e);
1222 e = single_succ_edge (close);
1224 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1226 gimple phi = gsi_stmt (psi);
1229 for (i = 0; i < gimple_phi_num_args (phi); i++)
1230 if (gimple_phi_arg_edge (phi, i) == e)
1232 tree res, arg = gimple_phi_arg_def (phi, i);
1233 use_operand_p use_p;
1236 if (TREE_CODE (arg) != SSA_NAME)
1239 close_phi = create_phi_node (arg, close);
1240 res = create_new_def_for (gimple_phi_result (close_phi),
1242 gimple_phi_result_ptr (close_phi));
1243 add_phi_arg (close_phi, arg,
1244 gimple_phi_arg_edge (close_phi, 0),
1246 use_p = gimple_phi_arg_imm_use_ptr (phi, i);
1247 replace_exp (use_p, res);
1254 /* Converts the current loop closed SSA form to a canonical form
1255 expected by the Graphite code generation.
1257 The loop closed SSA form has the following invariant: a variable
1258 defined in a loop that is used outside the loop appears only in the
1259 phi nodes in the destination of the loop exit. These phi nodes are
1260 called close phi nodes.
1262 The canonical loop closed SSA form contains the extra invariants:
1264 - when the loop contains only one exit, the close phi nodes contain
1265 only one argument. That implies that the basic block that contains
1266 the close phi nodes has only one predecessor, that is a basic block
1269 - the basic block containing the close phi nodes does not contain
1274 canonicalize_loop_closed_ssa_form (void)
1279 #ifdef ENABLE_CHECKING
1280 verify_loop_closed_ssa (true);
1283 FOR_EACH_LOOP (li, loop, 0)
1284 canonicalize_loop_closed_ssa (loop);
1286 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1287 update_ssa (TODO_update_ssa);
1289 #ifdef ENABLE_CHECKING
1290 verify_loop_closed_ssa (true);
1294 /* Find Static Control Parts (SCoP) in the current function and pushes
1298 build_scops (VEC (scop_p, heap) **scops)
1300 struct loop *loop = current_loops->tree_root;
1301 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
1303 canonicalize_loop_closed_ssa_form ();
1304 build_scops_1 (single_succ (ENTRY_BLOCK_PTR), ENTRY_BLOCK_PTR->loop_father,
1306 create_sese_edges (regions);
1307 build_graphite_scops (regions, scops);
1309 if (dump_file && (dump_flags & TDF_DETAILS))
1310 print_graphite_statistics (dump_file, *scops);
1312 limit_scops (scops);
1313 VEC_free (sd_region, heap, regions);
1315 if (dump_file && (dump_flags & TDF_DETAILS))
1316 fprintf (dump_file, "\nnumber of SCoPs: %d\n",
1317 VEC_length (scop_p, *scops));
1320 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1321 different colors. If there are not enough colors, paint the
1322 remaining SCoPs in gray.
1325 - "*" after the node number denotes the entry of a SCoP,
1326 - "#" after the node number denotes the exit of a SCoP,
1327 - "()" around the node number denotes the entry or the
1328 exit nodes of the SCOP. These are not part of SCoP. */
1331 dot_all_scops_1 (FILE *file, VEC (scop_p, heap) *scops)
1340 /* Disable debugging while printing graph. */
1341 int tmp_dump_flags = dump_flags;
1344 fprintf (file, "digraph all {\n");
1348 int part_of_scop = false;
1350 /* Use HTML for every bb label. So we are able to print bbs
1351 which are part of two different SCoPs, with two different
1352 background colors. */
1353 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1355 fprintf (file, "CELLSPACING=\"0\">\n");
1357 /* Select color for SCoP. */
1358 FOR_EACH_VEC_ELT (scop_p, scops, i, scop)
1360 sese region = SCOP_REGION (scop);
1361 if (bb_in_sese_p (bb, region)
1362 || (SESE_EXIT_BB (region) == bb)
1363 || (SESE_ENTRY_BB (region) == bb))
1376 case 3: /* purple */
1379 case 4: /* orange */
1382 case 5: /* yellow */
1422 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
1424 if (!bb_in_sese_p (bb, region))
1425 fprintf (file, " (");
1427 if (bb == SESE_ENTRY_BB (region)
1428 && bb == SESE_EXIT_BB (region))
1429 fprintf (file, " %d*# ", bb->index);
1430 else if (bb == SESE_ENTRY_BB (region))
1431 fprintf (file, " %d* ", bb->index);
1432 else if (bb == SESE_EXIT_BB (region))
1433 fprintf (file, " %d# ", bb->index);
1435 fprintf (file, " %d ", bb->index);
1437 if (!bb_in_sese_p (bb,region))
1438 fprintf (file, ")");
1440 fprintf (file, "</TD></TR>\n");
1441 part_of_scop = true;
1447 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1448 fprintf (file, " %d </TD></TR>\n", bb->index);
1450 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1455 FOR_EACH_EDGE (e, ei, bb->succs)
1456 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
1459 fputs ("}\n\n", file);
1461 /* Enable debugging again. */
1462 dump_flags = tmp_dump_flags;
1465 /* Display all SCoPs using dotty. */
1468 dot_all_scops (VEC (scop_p, heap) *scops)
1470 /* When debugging, enable the following code. This cannot be used
1471 in production compilers because it calls "system". */
1474 FILE *stream = fopen ("/tmp/allscops.dot", "w");
1475 gcc_assert (stream);
1477 dot_all_scops_1 (stream, scops);
1480 x = system ("dotty /tmp/allscops.dot &");
1482 dot_all_scops_1 (stderr, scops);
1486 /* Display all SCoPs using dotty. */
1489 dot_scop (scop_p scop)
1491 VEC (scop_p, heap) *scops = NULL;
1494 VEC_safe_push (scop_p, heap, scops, scop);
1496 /* When debugging, enable the following code. This cannot be used
1497 in production compilers because it calls "system". */
1501 FILE *stream = fopen ("/tmp/allscops.dot", "w");
1502 gcc_assert (stream);
1504 dot_all_scops_1 (stream, scops);
1506 x = system ("dotty /tmp/allscops.dot &");
1509 dot_all_scops_1 (stderr, scops);
1512 VEC_free (scop_p, heap, scops);