1 /* Detection of Static Control Parts (SCoP) for Graphite.
2 Copyright (C) 2009-2015 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/>. */
25 #include <isl/constraint.h>
28 #include <isl/union_map.h>
32 #include "coretypes.h"
36 #include "double-int.h"
44 #include "fold-const.h"
47 #include "hard-reg-set.h"
50 #include "dominance.h"
52 #include "basic-block.h"
53 #include "tree-ssa-alias.h"
54 #include "internal-fn.h"
55 #include "gimple-expr.h"
58 #include "gimple-iterator.h"
59 #include "gimple-ssa.h"
60 #include "tree-phinodes.h"
61 #include "ssa-iterators.h"
62 #include "tree-ssa-loop-manip.h"
63 #include "tree-ssa-loop-niter.h"
64 #include "tree-ssa-loop.h"
65 #include "tree-into-ssa.h"
68 #include "tree-chrec.h"
69 #include "tree-data-ref.h"
70 #include "tree-scalar-evolution.h"
71 #include "tree-pass.h"
73 #include "tree-ssa-propagate.h"
74 #include "cp/cp-tree.h"
77 #include "graphite-poly.h"
78 #include "graphite-scop-detection.h"
80 /* Forward declarations. */
81 static void make_close_phi_nodes_unique (basic_block);
83 /* The type of the analyzed basic block. */
85 typedef enum gbb_type {
87 GBB_LOOP_SING_EXIT_HEADER,
88 GBB_LOOP_MULT_EXIT_HEADER,
95 /* Detect the type of BB. Loop headers are only marked, if they are
96 new. This means their loop_father is different to LAST_LOOP.
97 Otherwise they are treated like any other bb and their type can be
101 get_bb_type (basic_block bb, struct loop *last_loop)
103 vec<basic_block> dom;
105 struct loop *loop = bb->loop_father;
107 /* Check, if we entry into a new loop. */
108 if (loop != last_loop)
110 if (single_exit (loop) != NULL)
111 return GBB_LOOP_SING_EXIT_HEADER;
112 else if (loop->num != 0)
113 return GBB_LOOP_MULT_EXIT_HEADER;
115 return GBB_COND_HEADER;
118 dom = get_dominated_by (CDI_DOMINATORS, bb);
119 nb_dom = dom.length ();
125 if (nb_dom == 1 && single_succ_p (bb))
128 return GBB_COND_HEADER;
131 /* A SCoP detection region, defined using bbs as borders.
133 All control flow touching this region, comes in passing basic_block
134 ENTRY and leaves passing basic_block EXIT. By using bbs instead of
135 edges for the borders we are able to represent also regions that do
136 not have a single entry or exit edge.
138 But as they have a single entry basic_block and a single exit
139 basic_block, we are able to generate for every sd_region a single
147 / \ This region contains: {3, 4, 5, 6, 7, 8}
155 typedef struct sd_region_p
157 /* The entry bb dominates all bbs in the sd_region. It is part of
161 /* The exit bb postdominates all bbs in the sd_region, but is not
162 part of the region. */
168 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
171 move_sd_regions (vec<sd_region> *source, vec<sd_region> *target)
176 FOR_EACH_VEC_ELT (*source, i, s)
177 target->safe_push (*s);
182 /* Something like "n * m" is not allowed. */
185 graphite_can_represent_init (tree e)
187 switch (TREE_CODE (e))
189 case POLYNOMIAL_CHREC:
190 return graphite_can_represent_init (CHREC_LEFT (e))
191 && graphite_can_represent_init (CHREC_RIGHT (e));
194 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
195 return graphite_can_represent_init (TREE_OPERAND (e, 0))
196 && tree_fits_shwi_p (TREE_OPERAND (e, 1));
198 return graphite_can_represent_init (TREE_OPERAND (e, 1))
199 && tree_fits_shwi_p (TREE_OPERAND (e, 0));
202 case POINTER_PLUS_EXPR:
204 return graphite_can_represent_init (TREE_OPERAND (e, 0))
205 && graphite_can_represent_init (TREE_OPERAND (e, 1));
210 case NON_LVALUE_EXPR:
211 return graphite_can_represent_init (TREE_OPERAND (e, 0));
220 /* Return true when SCEV can be represented in the polyhedral model.
222 An expression can be represented, if it can be expressed as an
223 affine expression. For loops (i, j) and parameters (m, n) all
224 affine expressions are of the form:
226 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
228 1 i + 20 j + (-2) m + 25
230 Something like "i * n" or "n * m" is not allowed. */
233 graphite_can_represent_scev (tree scev)
235 if (chrec_contains_undetermined (scev))
238 /* We disable the handling of pointer types, because it’s currently not
239 supported by Graphite with the ISL AST generator. SSA_NAME nodes are
240 the only nodes, which are disabled in case they are pointers to object
241 types, but this can be changed. */
243 if (TYPE_PTROB_P (TREE_TYPE (scev)) && TREE_CODE (scev) == SSA_NAME)
246 switch (TREE_CODE (scev))
251 case NON_LVALUE_EXPR:
252 return graphite_can_represent_scev (TREE_OPERAND (scev, 0));
255 case POINTER_PLUS_EXPR:
257 return graphite_can_represent_scev (TREE_OPERAND (scev, 0))
258 && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
261 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
262 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
263 && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
264 && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
265 && graphite_can_represent_init (scev)
266 && graphite_can_represent_scev (TREE_OPERAND (scev, 0))
267 && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
269 case POLYNOMIAL_CHREC:
270 /* Check for constant strides. With a non constant stride of
271 'n' we would have a value of 'iv * n'. Also check that the
272 initial value can represented: for example 'n * m' cannot be
274 if (!evolution_function_right_is_integer_cst (scev)
275 || !graphite_can_represent_init (scev))
277 return graphite_can_represent_scev (CHREC_LEFT (scev));
283 /* Only affine functions can be represented. */
284 if (tree_contains_chrecs (scev, NULL)
285 || !scev_is_linear_expression (scev))
292 /* Return true when EXPR can be represented in the polyhedral model.
294 This means an expression can be represented, if it is linear with
295 respect to the loops and the strides are non parametric.
296 LOOP is the place where the expr will be evaluated. SCOP_ENTRY defines the
297 entry of the region we analyse. */
300 graphite_can_represent_expr (basic_block scop_entry, loop_p loop,
303 tree scev = analyze_scalar_evolution (loop, expr);
305 scev = instantiate_scev (scop_entry, loop, scev);
307 return graphite_can_represent_scev (scev);
310 /* Return true if the data references of STMT can be represented by
314 stmt_has_simple_data_refs_p (loop_p outermost_loop ATTRIBUTE_UNUSED,
321 vec<data_reference_p> drs = vNULL;
324 for (outer = loop_containing_stmt (stmt); outer; outer = loop_outer (outer))
326 graphite_find_data_references_in_stmt (outer,
327 loop_containing_stmt (stmt),
330 FOR_EACH_VEC_ELT (drs, j, dr)
331 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
332 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr, i)))
338 free_data_refs (drs);
343 free_data_refs (drs);
347 /* Return true only when STMT is simple enough for being handled by
348 Graphite. This depends on SCOP_ENTRY, as the parameters are
349 initialized relatively to this basic block, the linear functions
350 are initialized to OUTERMOST_LOOP and BB is the place where we try
351 to evaluate the STMT. */
354 stmt_simple_for_scop_p (basic_block scop_entry, loop_p outermost_loop,
355 gimple stmt, basic_block bb)
357 loop_p loop = bb->loop_father;
359 gcc_assert (scop_entry);
361 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
362 Calls have side-effects, except those to const or pure
364 if (gimple_has_volatile_ops (stmt)
365 || (gimple_code (stmt) == GIMPLE_CALL
366 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
367 || (gimple_code (stmt) == GIMPLE_ASM))
370 if (is_gimple_debug (stmt))
373 if (!stmt_has_simple_data_refs_p (outermost_loop, stmt))
376 switch (gimple_code (stmt))
384 /* We can handle all binary comparisons. Inequalities are
385 also supported as they can be represented with union of
387 enum tree_code code = gimple_cond_code (stmt);
388 if (!(code == LT_EXPR
396 for (unsigned i = 0; i < 2; ++i)
398 tree op = gimple_op (stmt, i);
399 if (!graphite_can_represent_expr (scop_entry, loop, op)
400 /* We can not handle REAL_TYPE. Failed for pr39260. */
401 || TREE_CODE (TREE_TYPE (op)) == REAL_TYPE)
413 /* These nodes cut a new scope. */
420 /* Returns the statement of BB that contains a harmful operation: that
421 can be a function call with side effects, the induction variables
422 are not linear with respect to SCOP_ENTRY, etc. The current open
423 scop should end before this statement. The evaluation is limited using
424 OUTERMOST_LOOP as outermost loop that may change. */
427 harmful_stmt_in_bb (basic_block scop_entry, loop_p outer_loop, basic_block bb)
429 gimple_stmt_iterator gsi;
431 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
432 if (!stmt_simple_for_scop_p (scop_entry, outer_loop, gsi_stmt (gsi), bb))
433 return gsi_stmt (gsi);
438 /* Return true if LOOP can be represented in the polyhedral
439 representation. This is evaluated taking SCOP_ENTRY and
440 OUTERMOST_LOOP in mind. */
443 graphite_can_represent_loop (basic_block scop_entry, loop_p loop)
446 struct tree_niter_desc niter_desc;
448 /* FIXME: For the moment, graphite cannot be used on loops that
449 iterate using induction variables that wrap. */
451 return number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false)
452 && niter_desc.control.no_overflow
453 && (niter = number_of_latch_executions (loop))
454 && !chrec_contains_undetermined (niter)
455 && graphite_can_represent_expr (scop_entry, loop, niter);
458 /* Store information needed by scopdet_* functions. */
462 /* Exit of the open scop would stop if the current BB is harmful. */
465 /* Where the next scop would start if the current BB is harmful. */
468 /* The bb or one of its children contains open loop exits. That means
469 loop exit nodes that are not surrounded by a loop dominated by bb. */
472 /* The bb or one of its children contains only structures we can handle. */
476 static struct scopdet_info build_scops_1 (basic_block, loop_p,
477 vec<sd_region> *, loop_p);
479 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
480 to SCOPS. TYPE is the gbb_type of BB. */
482 static struct scopdet_info
483 scopdet_basic_block_info (basic_block bb, loop_p outermost_loop,
484 vec<sd_region> *scops, gbb_type type)
486 loop_p loop = bb->loop_father;
487 struct scopdet_info result;
490 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
491 basic_block entry_block = ENTRY_BLOCK_PTR_FOR_FN (cfun);
492 stmt = harmful_stmt_in_bb (entry_block, outermost_loop, bb);
493 result.difficult = (stmt != NULL);
500 result.exits = false;
502 /* Mark bbs terminating a SESE region difficult, if they start
503 a condition or if the block it exits to cannot be split
504 with make_forwarder_block. */
505 if (!single_succ_p (bb)
506 || bb_has_abnormal_pred (single_succ (bb)))
507 result.difficult = true;
509 result.exit = single_succ (bb);
514 result.next = single_succ (bb);
515 result.exits = false;
516 result.exit = single_succ (bb);
519 case GBB_LOOP_SING_EXIT_HEADER:
521 auto_vec<sd_region, 3> regions;
522 struct scopdet_info sinfo;
523 edge exit_e = single_exit (loop);
525 sinfo = build_scops_1 (bb, outermost_loop, ®ions, loop);
527 if (!graphite_can_represent_loop (entry_block, loop))
528 result.difficult = true;
530 result.difficult |= sinfo.difficult;
532 /* Try again with another loop level. */
534 && loop_depth (outermost_loop) + 1 == loop_depth (loop))
536 outermost_loop = loop;
541 sinfo = scopdet_basic_block_info (bb, outermost_loop, scops, type);
544 result.difficult = true;
547 move_sd_regions (®ions, scops);
551 open_scop.entry = bb;
552 open_scop.exit = exit_e->dest;
553 scops->safe_push (open_scop);
559 result.exit = exit_e->dest;
560 result.next = exit_e->dest;
562 /* If we do not dominate result.next, remove it. It's either
563 the exit block, or another bb dominates it and will
564 call the scop detection for this bb. */
565 if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
568 if (exit_e->src->loop_father != loop)
571 result.exits = false;
573 if (result.difficult)
574 move_sd_regions (®ions, scops);
582 case GBB_LOOP_MULT_EXIT_HEADER:
584 /* XXX: For now we just do not join loops with multiple exits. If the
585 exits lead to the same bb it may be possible to join the loop. */
586 auto_vec<sd_region, 3> regions;
587 vec<edge> exits = get_loop_exit_edges (loop);
590 build_scops_1 (bb, loop, ®ions, loop);
592 /* Scan the code dominated by this loop. This means all bbs, that are
593 are dominated by a bb in this loop, but are not part of this loop.
596 - The loop exit destination is dominated by the exit sources.
598 TODO: We miss here the more complex cases:
599 - The exit destinations are dominated by another bb inside
601 - The loop dominates bbs, that are not exit destinations. */
602 FOR_EACH_VEC_ELT (exits, i, e)
603 if (e->src->loop_father == loop
604 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
606 if (loop_outer (outermost_loop))
607 outermost_loop = loop_outer (outermost_loop);
609 /* Pass loop_outer to recognize e->dest as loop header in
611 if (e->dest->loop_father->header == e->dest)
612 build_scops_1 (e->dest, outermost_loop, ®ions,
613 loop_outer (e->dest->loop_father));
615 build_scops_1 (e->dest, outermost_loop, ®ions,
616 e->dest->loop_father);
621 result.difficult = true;
622 result.exits = false;
623 move_sd_regions (®ions, scops);
627 case GBB_COND_HEADER:
629 auto_vec<sd_region, 3> regions;
630 struct scopdet_info sinfo;
631 vec<basic_block> dominated;
634 basic_block last_exit = NULL;
636 result.exits = false;
638 /* First check the successors of BB, and check if it is
639 possible to join the different branches. */
640 FOR_EACH_VEC_SAFE_ELT (bb->succs, i, e)
642 /* Ignore loop exits. They will be handled after the loop
644 if (loop_exits_to_bb_p (loop, e->dest))
650 /* Do not follow edges that lead to the end of the
651 conditions block. For example, in
661 the edge from 0 => 6. Only check if all paths lead to
664 if (!single_pred_p (e->dest))
666 /* Check, if edge leads directly to the end of this
671 if (e->dest != last_exit)
672 result.difficult = true;
677 if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
679 result.difficult = true;
683 sinfo = build_scops_1 (e->dest, outermost_loop, ®ions, loop);
685 result.exits |= sinfo.exits;
686 result.difficult |= sinfo.difficult;
688 /* Checks, if all branches end at the same point.
689 If that is true, the condition stays joinable.
690 Have a look at the example above. */
694 last_exit = sinfo.exit;
696 if (sinfo.exit != last_exit)
697 result.difficult = true;
700 result.difficult = true;
704 result.difficult = true;
706 /* Join the branches of the condition if possible. */
707 if (!result.exits && !result.difficult)
709 /* Only return a next pointer if we dominate this pointer.
710 Otherwise it will be handled by the bb dominating it. */
711 if (dominated_by_p (CDI_DOMINATORS, last_exit, bb)
713 result.next = last_exit;
717 result.exit = last_exit;
723 /* Scan remaining bbs dominated by BB. */
724 dominated = get_dominated_by (CDI_DOMINATORS, bb);
726 FOR_EACH_VEC_ELT (dominated, i, dom_bb)
728 /* Ignore loop exits: they will be handled after the loop body. */
729 if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
736 /* Ignore the bbs processed above. */
737 if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
740 if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
741 sinfo = build_scops_1 (dom_bb, outermost_loop, ®ions,
744 sinfo = build_scops_1 (dom_bb, outermost_loop, ®ions, loop);
746 result.exits |= sinfo.exits;
747 result.difficult = true;
751 dominated.release ();
754 move_sd_regions (®ions, scops);
766 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
767 SCOPS. The analyse if a sd_region can be handled is based on the value
768 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
769 is the loop in which CURRENT is handled.
771 TODO: These functions got a little bit big. They definitely should be cleaned
774 static struct scopdet_info
775 build_scops_1 (basic_block current, loop_p outermost_loop,
776 vec<sd_region> *scops, loop_p loop)
778 bool in_scop = false;
780 struct scopdet_info sinfo;
782 /* Initialize result. */
783 struct scopdet_info result;
784 result.exits = false;
785 result.difficult = false;
788 open_scop.entry = NULL;
789 open_scop.exit = NULL;
792 /* Loop over the dominance tree. If we meet a difficult bb, close
793 the current SCoP. Loop and condition header start a new layer,
794 and can only be added if all bbs in deeper layers are simple. */
795 while (current != NULL)
797 sinfo = scopdet_basic_block_info (current, outermost_loop, scops,
798 get_bb_type (current, loop));
800 if (!in_scop && !(sinfo.exits || sinfo.difficult))
802 open_scop.entry = current;
803 open_scop.exit = NULL;
806 else if (in_scop && (sinfo.exits || sinfo.difficult))
808 open_scop.exit = current;
809 scops->safe_push (open_scop);
813 result.difficult |= sinfo.difficult;
814 result.exits |= sinfo.exits;
816 current = sinfo.next;
819 /* Try to close open_scop, if we are still in an open SCoP. */
822 open_scop.exit = sinfo.exit;
823 gcc_assert (open_scop.exit);
824 scops->safe_push (open_scop);
827 result.exit = sinfo.exit;
831 /* Checks if a bb is contained in REGION. */
834 bb_in_sd_region (basic_block bb, sd_region *region)
836 return bb_in_region (bb, region->entry, region->exit);
839 /* Returns the single entry edge of REGION, if it does not exits NULL. */
842 find_single_entry_edge (sd_region *region)
848 FOR_EACH_EDGE (e, ei, region->entry->preds)
849 if (!bb_in_sd_region (e->src, region))
864 /* Returns the single exit edge of REGION, if it does not exits NULL. */
867 find_single_exit_edge (sd_region *region)
873 FOR_EACH_EDGE (e, ei, region->exit->preds)
874 if (bb_in_sd_region (e->src, region))
889 /* Create a single entry edge for REGION. */
892 create_single_entry_edge (sd_region *region)
894 if (find_single_entry_edge (region))
897 /* There are multiple predecessors for bb_3
910 There are two edges (1->3, 2->3), that point from outside into the region,
911 and another one (5->3), a loop latch, lead to bb_3.
919 | |\ (3.0 -> 3.1) = single entry edge
928 If the loop is part of the SCoP, we have to redirect the loop latches.
934 | | (3.0 -> 3.1) = entry edge
943 if (region->entry->loop_father->header != region->entry
944 || dominated_by_p (CDI_DOMINATORS,
945 loop_latch_edge (region->entry->loop_father)->src,
948 edge forwarder = split_block_after_labels (region->entry);
949 region->entry = forwarder->dest;
952 /* This case is never executed, as the loop headers seem always to have a
953 single edge pointing from outside into the loop. */
956 gcc_checking_assert (find_single_entry_edge (region));
959 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
962 sd_region_without_exit (edge e)
964 sd_region *r = (sd_region *) e->aux;
967 return r->exit == NULL;
972 /* Create a single exit edge for REGION. */
975 create_single_exit_edge (sd_region *region)
979 edge forwarder = NULL;
982 /* We create a forwarder bb (5) for all edges leaving this region
983 (3->5, 4->5). All other edges leading to the same bb, are moved
984 to a new bb (6). If these edges where part of another region (2->5)
985 we update the region->exit pointer, of this region.
987 To identify which edge belongs to which region we depend on the e->aux
988 pointer in every edge. It points to the region of the edge or to NULL,
989 if the edge is not part of any region.
991 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
992 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
997 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
998 | | \/ 3->5 no region, 4->5 no region,
1000 \| / 5->6 region->exit = 6
1003 Now there is only a single exit edge (5->6). */
1004 exit = region->exit;
1005 region->exit = NULL;
1006 forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
1008 /* Unmark the edges, that are no longer exit edges. */
1009 FOR_EACH_EDGE (e, ei, forwarder->src->preds)
1013 /* Mark the new exit edge. */
1014 single_succ_edge (forwarder->src)->aux = region;
1016 /* Update the exit bb of all regions, where exit edges lead to
1018 FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
1020 ((sd_region *) e->aux)->exit = forwarder->dest;
1022 gcc_checking_assert (find_single_exit_edge (region));
1025 /* Unmark the exit edges of all REGIONS.
1026 See comment in "create_single_exit_edge". */
1029 unmark_exit_edges (vec<sd_region> regions)
1036 FOR_EACH_VEC_ELT (regions, i, s)
1037 FOR_EACH_EDGE (e, ei, s->exit->preds)
1042 /* Mark the exit edges of all REGIONS.
1043 See comment in "create_single_exit_edge". */
1046 mark_exit_edges (vec<sd_region> regions)
1053 FOR_EACH_VEC_ELT (regions, i, s)
1054 FOR_EACH_EDGE (e, ei, s->exit->preds)
1055 if (bb_in_sd_region (e->src, s))
1059 /* Create for all scop regions a single entry and a single exit edge. */
1062 create_sese_edges (vec<sd_region> regions)
1067 FOR_EACH_VEC_ELT (regions, i, s)
1068 create_single_entry_edge (s);
1070 mark_exit_edges (regions);
1072 FOR_EACH_VEC_ELT (regions, i, s)
1073 /* Don't handle multiple edges exiting the function. */
1074 if (!find_single_exit_edge (s)
1075 && s->exit != EXIT_BLOCK_PTR_FOR_FN (cfun))
1076 create_single_exit_edge (s);
1078 unmark_exit_edges (regions);
1080 calculate_dominance_info (CDI_DOMINATORS);
1081 fix_loop_structure (NULL);
1083 #ifdef ENABLE_CHECKING
1084 verify_loop_structure ();
1085 verify_ssa (false, true);
1089 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1092 build_graphite_scops (vec<sd_region> regions,
1098 FOR_EACH_VEC_ELT (regions, i, s)
1100 edge entry = find_single_entry_edge (s);
1101 edge exit = find_single_exit_edge (s);
1107 scop = new_scop (new_sese (entry, exit));
1108 scops->safe_push (scop);
1110 /* Are there overlapping SCoPs? */
1111 #ifdef ENABLE_CHECKING
1116 FOR_EACH_VEC_ELT (regions, j, s2)
1118 gcc_assert (!bb_in_sd_region (s->entry, s2));
1124 /* Returns true when BB contains only close phi nodes. */
1127 contains_only_close_phi_nodes (basic_block bb)
1129 gimple_stmt_iterator gsi;
1131 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1132 if (gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
1138 /* Print statistics for SCOP to FILE. */
1141 print_graphite_scop_statistics (FILE* file, scop_p scop)
1146 long n_conditions = 0;
1150 long n_p_conditions = 0;
1154 FOR_ALL_BB_FN (bb, cfun)
1156 gimple_stmt_iterator psi;
1157 loop_p loop = bb->loop_father;
1159 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
1163 n_p_bbs += bb->count;
1165 if (EDGE_COUNT (bb->succs) > 1)
1168 n_p_conditions += bb->count;
1171 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
1174 n_p_stmts += bb->count;
1177 if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
1180 n_p_loops += bb->count;
1185 fprintf (file, "\nBefore limit_scops SCoP statistics (");
1186 fprintf (file, "BBS:%ld, ", n_bbs);
1187 fprintf (file, "LOOPS:%ld, ", n_loops);
1188 fprintf (file, "CONDITIONS:%ld, ", n_conditions);
1189 fprintf (file, "STMTS:%ld)\n", n_stmts);
1190 fprintf (file, "\nBefore limit_scops SCoP profiling statistics (");
1191 fprintf (file, "BBS:%ld, ", n_p_bbs);
1192 fprintf (file, "LOOPS:%ld, ", n_p_loops);
1193 fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
1194 fprintf (file, "STMTS:%ld)\n", n_p_stmts);
1197 /* Print statistics for SCOPS to FILE. */
1200 print_graphite_statistics (FILE* file, vec<scop_p> scops)
1205 FOR_EACH_VEC_ELT (scops, i, scop)
1206 print_graphite_scop_statistics (file, scop);
1209 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1219 * SCoP frontier, as this line is not surrounded by any loop. *
1223 This is necessary as scalar evolution and parameter detection need a
1224 outermost loop to initialize parameters correctly.
1226 TODO: FIX scalar evolution and parameter detection to allow more flexible
1230 limit_scops (vec<scop_p> *scops)
1232 auto_vec<sd_region, 3> regions;
1237 FOR_EACH_VEC_ELT (*scops, i, scop)
1241 sese region = SCOP_REGION (scop);
1242 build_sese_loop_nests (region);
1244 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), j, loop)
1245 if (!loop_in_sese_p (loop_outer (loop), region)
1246 && single_exit (loop))
1248 sd_region open_scop;
1249 open_scop.entry = loop->header;
1250 open_scop.exit = single_exit (loop)->dest;
1252 /* This is a hack on top of the limit_scops hack. The
1253 limit_scops hack should disappear all together. */
1254 if (single_succ_p (open_scop.exit)
1255 && contains_only_close_phi_nodes (open_scop.exit))
1256 open_scop.exit = single_succ_edge (open_scop.exit)->dest;
1258 regions.safe_push (open_scop);
1262 free_scops (*scops);
1265 create_sese_edges (regions);
1266 build_graphite_scops (regions, scops);
1269 /* Returns true when P1 and P2 are close phis with the same
1273 same_close_phi_node (gphi *p1, gphi *p2)
1275 return operand_equal_p (gimple_phi_arg_def (p1, 0),
1276 gimple_phi_arg_def (p2, 0), 0);
1279 /* Remove the close phi node at GSI and replace its rhs with the rhs
1283 remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi)
1286 use_operand_p use_p;
1287 imm_use_iterator imm_iter;
1288 tree res = gimple_phi_result (phi);
1289 tree def = gimple_phi_result (gsi->phi ());
1291 gcc_assert (same_close_phi_node (phi, gsi->phi ()));
1293 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
1295 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
1296 SET_USE (use_p, res);
1298 update_stmt (use_stmt);
1300 /* It is possible that we just created a duplicate close-phi
1301 for an already-processed containing loop. Check for this
1302 case and clean it up. */
1303 if (gimple_code (use_stmt) == GIMPLE_PHI
1304 && gimple_phi_num_args (use_stmt) == 1)
1305 make_close_phi_nodes_unique (gimple_bb (use_stmt));
1308 remove_phi_node (gsi, true);
1311 /* Removes all the close phi duplicates from BB. */
1314 make_close_phi_nodes_unique (basic_block bb)
1318 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1320 gphi_iterator gsi = psi;
1321 gphi *phi = psi.phi ();
1323 /* At this point, PHI should be a close phi in normal form. */
1324 gcc_assert (gimple_phi_num_args (phi) == 1);
1326 /* Iterate over the next phis and remove duplicates. */
1328 while (!gsi_end_p (gsi))
1329 if (same_close_phi_node (phi, gsi.phi ()))
1330 remove_duplicate_close_phi (phi, &gsi);
1336 /* Transforms LOOP to the canonical loop closed SSA form. */
1339 canonicalize_loop_closed_ssa (loop_p loop)
1341 edge e = single_exit (loop);
1344 if (!e || e->flags & EDGE_ABNORMAL)
1349 if (single_pred_p (bb))
1351 e = split_block_after_labels (bb);
1352 make_close_phi_nodes_unique (e->src);
1357 basic_block close = split_edge (e);
1359 e = single_succ_edge (close);
1361 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1363 gphi *phi = psi.phi ();
1366 for (i = 0; i < gimple_phi_num_args (phi); i++)
1367 if (gimple_phi_arg_edge (phi, i) == e)
1369 tree res, arg = gimple_phi_arg_def (phi, i);
1370 use_operand_p use_p;
1373 if (TREE_CODE (arg) != SSA_NAME)
1376 close_phi = create_phi_node (NULL_TREE, close);
1377 res = create_new_def_for (arg, close_phi,
1378 gimple_phi_result_ptr (close_phi));
1379 add_phi_arg (close_phi, arg,
1380 gimple_phi_arg_edge (close_phi, 0),
1382 use_p = gimple_phi_arg_imm_use_ptr (phi, i);
1383 replace_exp (use_p, res);
1388 make_close_phi_nodes_unique (close);
1391 /* The code above does not properly handle changes in the post dominance
1392 information (yet). */
1393 free_dominance_info (CDI_POST_DOMINATORS);
1396 /* Converts the current loop closed SSA form to a canonical form
1397 expected by the Graphite code generation.
1399 The loop closed SSA form has the following invariant: a variable
1400 defined in a loop that is used outside the loop appears only in the
1401 phi nodes in the destination of the loop exit. These phi nodes are
1402 called close phi nodes.
1404 The canonical loop closed SSA form contains the extra invariants:
1406 - when the loop contains only one exit, the close phi nodes contain
1407 only one argument. That implies that the basic block that contains
1408 the close phi nodes has only one predecessor, that is a basic block
1411 - the basic block containing the close phi nodes does not contain
1414 - there exist only one phi node per definition in the loop.
1418 canonicalize_loop_closed_ssa_form (void)
1422 #ifdef ENABLE_CHECKING
1423 verify_loop_closed_ssa (true);
1426 FOR_EACH_LOOP (loop, 0)
1427 canonicalize_loop_closed_ssa (loop);
1429 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1430 update_ssa (TODO_update_ssa);
1432 #ifdef ENABLE_CHECKING
1433 verify_loop_closed_ssa (true);
1437 /* Find Static Control Parts (SCoP) in the current function and pushes
1441 build_scops (vec<scop_p> *scops)
1443 struct loop *loop = current_loops->tree_root;
1444 auto_vec<sd_region, 3> regions;
1446 canonicalize_loop_closed_ssa_form ();
1447 build_scops_1 (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
1448 ENTRY_BLOCK_PTR_FOR_FN (cfun)->loop_father,
1450 create_sese_edges (regions);
1451 build_graphite_scops (regions, scops);
1453 if (dump_file && (dump_flags & TDF_DETAILS))
1454 print_graphite_statistics (dump_file, *scops);
1456 limit_scops (scops);
1459 if (dump_file && (dump_flags & TDF_DETAILS))
1460 fprintf (dump_file, "\nnumber of SCoPs: %d\n",
1461 scops ? scops->length () : 0);
1464 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1465 different colors. If there are not enough colors, paint the
1466 remaining SCoPs in gray.
1469 - "*" after the node number denotes the entry of a SCoP,
1470 - "#" after the node number denotes the exit of a SCoP,
1471 - "()" around the node number denotes the entry or the
1472 exit nodes of the SCOP. These are not part of SCoP. */
1475 dot_all_scops_1 (FILE *file, vec<scop_p> scops)
1484 /* Disable debugging while printing graph. */
1485 int tmp_dump_flags = dump_flags;
1488 fprintf (file, "digraph all {\n");
1490 FOR_ALL_BB_FN (bb, cfun)
1492 int part_of_scop = false;
1494 /* Use HTML for every bb label. So we are able to print bbs
1495 which are part of two different SCoPs, with two different
1496 background colors. */
1497 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1499 fprintf (file, "CELLSPACING=\"0\">\n");
1501 /* Select color for SCoP. */
1502 FOR_EACH_VEC_ELT (scops, i, scop)
1504 sese region = SCOP_REGION (scop);
1505 if (bb_in_sese_p (bb, region)
1506 || (SESE_EXIT_BB (region) == bb)
1507 || (SESE_ENTRY_BB (region) == bb))
1520 case 3: /* purple */
1523 case 4: /* orange */
1526 case 5: /* yellow */
1566 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
1568 if (!bb_in_sese_p (bb, region))
1569 fprintf (file, " (");
1571 if (bb == SESE_ENTRY_BB (region)
1572 && bb == SESE_EXIT_BB (region))
1573 fprintf (file, " %d*# ", bb->index);
1574 else if (bb == SESE_ENTRY_BB (region))
1575 fprintf (file, " %d* ", bb->index);
1576 else if (bb == SESE_EXIT_BB (region))
1577 fprintf (file, " %d# ", bb->index);
1579 fprintf (file, " %d ", bb->index);
1581 if (!bb_in_sese_p (bb,region))
1582 fprintf (file, ")");
1584 fprintf (file, "</TD></TR>\n");
1585 part_of_scop = true;
1591 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1592 fprintf (file, " %d </TD></TR>\n", bb->index);
1594 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1597 FOR_ALL_BB_FN (bb, cfun)
1599 FOR_EACH_EDGE (e, ei, bb->succs)
1600 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
1603 fputs ("}\n\n", file);
1605 /* Enable debugging again. */
1606 dump_flags = tmp_dump_flags;
1609 /* Display all SCoPs using dotty. */
1612 dot_all_scops (vec<scop_p> scops)
1614 /* When debugging, enable the following code. This cannot be used
1615 in production compilers because it calls "system". */
1618 FILE *stream = fopen ("/tmp/allscops.dot", "w");
1619 gcc_assert (stream);
1621 dot_all_scops_1 (stream, scops);
1624 x = system ("dotty /tmp/allscops.dot &");
1626 dot_all_scops_1 (stderr, scops);
1630 /* Display all SCoPs using dotty. */
1633 dot_scop (scop_p scop)
1635 auto_vec<scop_p, 1> scops;
1638 scops.safe_push (scop);
1640 /* When debugging, enable the following code. This cannot be used
1641 in production compilers because it calls "system". */
1645 FILE *stream = fopen ("/tmp/allscops.dot", "w");
1646 gcc_assert (stream);
1648 dot_all_scops_1 (stream, scops);
1650 x = system ("dotty /tmp/allscops.dot &");
1653 dot_all_scops_1 (stderr, scops);