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 /* Workaround for GMP 5.1.3 bug, see PR56019. */
30 #include <isl/union_map.h>
33 #include "coretypes.h"
39 #include "fold-const.h"
40 #include "gimple-iterator.h"
41 #include "tree-ssa-loop-manip.h"
42 #include "tree-ssa-loop-niter.h"
43 #include "tree-ssa-loop.h"
44 #include "tree-into-ssa.h"
47 #include "tree-data-ref.h"
48 #include "tree-scalar-evolution.h"
49 #include "tree-pass.h"
50 #include "graphite-poly.h"
51 #include "tree-ssa-propagate.h"
52 #include "graphite-scop-detection.h"
54 /* Forward declarations. */
55 static void make_close_phi_nodes_unique (basic_block);
57 /* The type of the analyzed basic block. */
59 typedef enum gbb_type {
61 GBB_LOOP_SING_EXIT_HEADER,
62 GBB_LOOP_MULT_EXIT_HEADER,
69 /* Detect the type of BB. Loop headers are only marked, if they are
70 new. This means their loop_father is different to LAST_LOOP.
71 Otherwise they are treated like any other bb and their type can be
75 get_bb_type (basic_block bb, struct loop *last_loop)
79 struct loop *loop = bb->loop_father;
81 /* Check, if we entry into a new loop. */
82 if (loop != last_loop)
84 if (single_exit (loop) != NULL)
85 return GBB_LOOP_SING_EXIT_HEADER;
86 else if (loop->num != 0)
87 return GBB_LOOP_MULT_EXIT_HEADER;
89 return GBB_COND_HEADER;
92 dom = get_dominated_by (CDI_DOMINATORS, bb);
93 nb_dom = dom.length ();
99 if (nb_dom == 1 && single_succ_p (bb))
102 return GBB_COND_HEADER;
105 /* A SCoP detection region, defined using bbs as borders.
107 All control flow touching this region, comes in passing basic_block
108 ENTRY and leaves passing basic_block EXIT. By using bbs instead of
109 edges for the borders we are able to represent also regions that do
110 not have a single entry or exit edge.
112 But as they have a single entry basic_block and a single exit
113 basic_block, we are able to generate for every sd_region a single
121 / \ This region contains: {3, 4, 5, 6, 7, 8}
129 typedef struct sd_region_p
131 /* The entry bb dominates all bbs in the sd_region. It is part of
135 /* The exit bb postdominates all bbs in the sd_region, but is not
136 part of the region. */
142 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
145 move_sd_regions (vec<sd_region> *source, vec<sd_region> *target)
150 FOR_EACH_VEC_ELT (*source, i, s)
151 target->safe_push (*s);
156 /* Something like "n * m" is not allowed. */
159 graphite_can_represent_init (tree e)
161 switch (TREE_CODE (e))
163 case POLYNOMIAL_CHREC:
164 return graphite_can_represent_init (CHREC_LEFT (e))
165 && graphite_can_represent_init (CHREC_RIGHT (e));
168 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
169 return graphite_can_represent_init (TREE_OPERAND (e, 0))
170 && tree_fits_shwi_p (TREE_OPERAND (e, 1));
172 return graphite_can_represent_init (TREE_OPERAND (e, 1))
173 && tree_fits_shwi_p (TREE_OPERAND (e, 0));
176 case POINTER_PLUS_EXPR:
178 return graphite_can_represent_init (TREE_OPERAND (e, 0))
179 && graphite_can_represent_init (TREE_OPERAND (e, 1));
184 case NON_LVALUE_EXPR:
185 return graphite_can_represent_init (TREE_OPERAND (e, 0));
194 /* Return true when SCEV can be represented in the polyhedral model.
196 An expression can be represented, if it can be expressed as an
197 affine expression. For loops (i, j) and parameters (m, n) all
198 affine expressions are of the form:
200 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
202 1 i + 20 j + (-2) m + 25
204 Something like "i * n" or "n * m" is not allowed. */
207 graphite_can_represent_scev (tree scev)
209 if (chrec_contains_undetermined (scev))
212 /* We disable the handling of pointer types, because it’s currently not
213 supported by Graphite with the ISL AST generator. SSA_NAME nodes are
214 the only nodes, which are disabled in case they are pointers to object
215 types, but this can be changed. */
217 if (POINTER_TYPE_P (TREE_TYPE (scev)) && TREE_CODE (scev) == SSA_NAME)
220 switch (TREE_CODE (scev))
225 case NON_LVALUE_EXPR:
226 return graphite_can_represent_scev (TREE_OPERAND (scev, 0));
229 case POINTER_PLUS_EXPR:
231 return graphite_can_represent_scev (TREE_OPERAND (scev, 0))
232 && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
235 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
236 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
237 && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
238 && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
239 && graphite_can_represent_init (scev)
240 && graphite_can_represent_scev (TREE_OPERAND (scev, 0))
241 && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
243 case POLYNOMIAL_CHREC:
244 /* Check for constant strides. With a non constant stride of
245 'n' we would have a value of 'iv * n'. Also check that the
246 initial value can represented: for example 'n * m' cannot be
248 if (!evolution_function_right_is_integer_cst (scev)
249 || !graphite_can_represent_init (scev))
251 return graphite_can_represent_scev (CHREC_LEFT (scev));
257 /* Only affine functions can be represented. */
258 if (tree_contains_chrecs (scev, NULL)
259 || !scev_is_linear_expression (scev))
266 /* Return true when EXPR can be represented in the polyhedral model.
268 This means an expression can be represented, if it is linear with
269 respect to the loops and the strides are non parametric.
270 LOOP is the place where the expr will be evaluated. SCOP_ENTRY defines the
271 entry of the region we analyse. */
274 graphite_can_represent_expr (basic_block scop_entry, loop_p loop,
277 tree scev = analyze_scalar_evolution (loop, expr);
279 scev = instantiate_scev (scop_entry, loop, scev);
281 return graphite_can_represent_scev (scev);
284 /* Return true if the data references of STMT can be represented by
288 stmt_has_simple_data_refs_p (loop_p outermost_loop ATTRIBUTE_UNUSED,
295 vec<data_reference_p> drs = vNULL;
298 for (outer = loop_containing_stmt (stmt); outer; outer = loop_outer (outer))
300 graphite_find_data_references_in_stmt (outer,
301 loop_containing_stmt (stmt),
304 FOR_EACH_VEC_ELT (drs, j, dr)
305 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
306 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr, i)))
312 free_data_refs (drs);
317 free_data_refs (drs);
321 /* Return true only when STMT is simple enough for being handled by
322 Graphite. This depends on SCOP_ENTRY, as the parameters are
323 initialized relatively to this basic block, the linear functions
324 are initialized to OUTERMOST_LOOP and BB is the place where we try
325 to evaluate the STMT. */
328 stmt_simple_for_scop_p (basic_block scop_entry, loop_p outermost_loop,
329 gimple stmt, basic_block bb)
331 loop_p loop = bb->loop_father;
333 gcc_assert (scop_entry);
335 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
336 Calls have side-effects, except those to const or pure
338 if (gimple_has_volatile_ops (stmt)
339 || (gimple_code (stmt) == GIMPLE_CALL
340 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
341 || (gimple_code (stmt) == GIMPLE_ASM))
344 if (is_gimple_debug (stmt))
347 if (!stmt_has_simple_data_refs_p (outermost_loop, stmt))
350 switch (gimple_code (stmt))
357 /* We can handle all binary comparisons. Inequalities are
358 also supported as they can be represented with union of
360 enum tree_code code = gimple_cond_code (stmt);
361 if (!(code == LT_EXPR
369 for (unsigned i = 0; i < 2; ++i)
371 tree op = gimple_op (stmt, i);
372 if (!graphite_can_represent_expr (scop_entry, loop, op)
373 /* We can not handle REAL_TYPE. Failed for pr39260. */
374 || TREE_CODE (TREE_TYPE (op)) == REAL_TYPE)
386 /* These nodes cut a new scope. */
393 /* Returns the statement of BB that contains a harmful operation: that
394 can be a function call with side effects, the induction variables
395 are not linear with respect to SCOP_ENTRY, etc. The current open
396 scop should end before this statement. The evaluation is limited using
397 OUTERMOST_LOOP as outermost loop that may change. */
400 harmful_stmt_in_bb (basic_block scop_entry, loop_p outer_loop, basic_block bb)
402 gimple_stmt_iterator gsi;
404 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
405 if (!stmt_simple_for_scop_p (scop_entry, outer_loop, gsi_stmt (gsi), bb))
406 return gsi_stmt (gsi);
411 /* Return true if LOOP can be represented in the polyhedral
412 representation. This is evaluated taking SCOP_ENTRY and
413 OUTERMOST_LOOP in mind. */
416 graphite_can_represent_loop (basic_block scop_entry, loop_p loop)
419 struct tree_niter_desc niter_desc;
421 /* FIXME: For the moment, graphite cannot be used on loops that
422 iterate using induction variables that wrap. */
424 return number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false)
425 && niter_desc.control.no_overflow
426 && (niter = number_of_latch_executions (loop))
427 && !chrec_contains_undetermined (niter)
428 && graphite_can_represent_expr (scop_entry, loop, niter);
431 /* Store information needed by scopdet_* functions. */
435 /* Exit of the open scop would stop if the current BB is harmful. */
438 /* Where the next scop would start if the current BB is harmful. */
441 /* The bb or one of its children contains open loop exits. That means
442 loop exit nodes that are not surrounded by a loop dominated by bb. */
445 /* The bb or one of its children contains only structures we can handle. */
449 static struct scopdet_info build_scops_1 (basic_block, loop_p,
450 vec<sd_region> *, loop_p);
452 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
453 to SCOPS. TYPE is the gbb_type of BB. */
455 static struct scopdet_info
456 scopdet_basic_block_info (basic_block bb, loop_p outermost_loop,
457 vec<sd_region> *scops, gbb_type type)
459 loop_p loop = bb->loop_father;
460 struct scopdet_info result;
463 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
464 basic_block entry_block = ENTRY_BLOCK_PTR_FOR_FN (cfun);
465 stmt = harmful_stmt_in_bb (entry_block, outermost_loop, bb);
466 result.difficult = (stmt != NULL);
473 result.exits = false;
475 /* Mark bbs terminating a SESE region difficult, if they start
476 a condition or if the block it exits to cannot be split
477 with make_forwarder_block. */
478 if (!single_succ_p (bb)
479 || bb_has_abnormal_pred (single_succ (bb)))
480 result.difficult = true;
482 result.exit = single_succ (bb);
487 result.next = single_succ (bb);
488 result.exits = false;
489 result.exit = single_succ (bb);
492 case GBB_LOOP_SING_EXIT_HEADER:
494 auto_vec<sd_region, 3> regions;
495 struct scopdet_info sinfo;
496 edge exit_e = single_exit (loop);
498 sinfo = build_scops_1 (bb, outermost_loop, ®ions, loop);
500 if (!graphite_can_represent_loop (entry_block, loop))
501 result.difficult = true;
503 result.difficult |= sinfo.difficult;
505 /* Try again with another loop level. */
507 && loop_depth (outermost_loop) + 1 == loop_depth (loop))
509 outermost_loop = loop;
514 sinfo = scopdet_basic_block_info (bb, outermost_loop, scops, type);
517 result.difficult = true;
520 move_sd_regions (®ions, scops);
524 open_scop.entry = bb;
525 open_scop.exit = exit_e->dest;
526 scops->safe_push (open_scop);
532 result.exit = exit_e->dest;
533 result.next = exit_e->dest;
535 /* If we do not dominate result.next, remove it. It's either
536 the exit block, or another bb dominates it and will
537 call the scop detection for this bb. */
538 if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
541 if (exit_e->src->loop_father != loop)
544 result.exits = false;
546 if (result.difficult)
547 move_sd_regions (®ions, scops);
555 case GBB_LOOP_MULT_EXIT_HEADER:
557 /* XXX: For now we just do not join loops with multiple exits. If the
558 exits lead to the same bb it may be possible to join the loop. */
559 auto_vec<sd_region, 3> regions;
560 vec<edge> exits = get_loop_exit_edges (loop);
563 build_scops_1 (bb, loop, ®ions, loop);
565 /* Scan the code dominated by this loop. This means all bbs, that are
566 are dominated by a bb in this loop, but are not part of this loop.
569 - The loop exit destination is dominated by the exit sources.
571 TODO: We miss here the more complex cases:
572 - The exit destinations are dominated by another bb inside
574 - The loop dominates bbs, that are not exit destinations. */
575 FOR_EACH_VEC_ELT (exits, i, e)
576 if (e->src->loop_father == loop
577 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
579 if (loop_outer (outermost_loop))
580 outermost_loop = loop_outer (outermost_loop);
582 /* Pass loop_outer to recognize e->dest as loop header in
584 if (e->dest->loop_father->header == e->dest)
585 build_scops_1 (e->dest, outermost_loop, ®ions,
586 loop_outer (e->dest->loop_father));
588 build_scops_1 (e->dest, outermost_loop, ®ions,
589 e->dest->loop_father);
594 result.difficult = true;
595 result.exits = false;
596 move_sd_regions (®ions, scops);
600 case GBB_COND_HEADER:
602 auto_vec<sd_region, 3> regions;
603 struct scopdet_info sinfo;
604 vec<basic_block> dominated;
607 basic_block last_exit = NULL;
609 result.exits = false;
611 /* First check the successors of BB, and check if it is
612 possible to join the different branches. */
613 FOR_EACH_VEC_SAFE_ELT (bb->succs, i, e)
615 /* Ignore loop exits. They will be handled after the loop
617 if (loop_exits_to_bb_p (loop, e->dest))
623 /* Do not follow edges that lead to the end of the
624 conditions block. For example, in
634 the edge from 0 => 6. Only check if all paths lead to
637 if (!single_pred_p (e->dest))
639 /* Check, if edge leads directly to the end of this
644 if (e->dest != last_exit)
645 result.difficult = true;
650 if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
652 result.difficult = true;
656 sinfo = build_scops_1 (e->dest, outermost_loop, ®ions, loop);
658 result.exits |= sinfo.exits;
659 result.difficult |= sinfo.difficult;
661 /* Checks, if all branches end at the same point.
662 If that is true, the condition stays joinable.
663 Have a look at the example above. */
667 last_exit = sinfo.exit;
669 if (sinfo.exit != last_exit)
670 result.difficult = true;
673 result.difficult = true;
677 result.difficult = true;
679 /* Join the branches of the condition if possible. */
680 if (!result.exits && !result.difficult)
682 /* Only return a next pointer if we dominate this pointer.
683 Otherwise it will be handled by the bb dominating it. */
684 if (dominated_by_p (CDI_DOMINATORS, last_exit, bb)
686 result.next = last_exit;
690 result.exit = last_exit;
696 /* Scan remaining bbs dominated by BB. */
697 dominated = get_dominated_by (CDI_DOMINATORS, bb);
699 FOR_EACH_VEC_ELT (dominated, i, dom_bb)
701 /* Ignore loop exits: they will be handled after the loop body. */
702 if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
709 /* Ignore the bbs processed above. */
710 if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
713 if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
714 sinfo = build_scops_1 (dom_bb, outermost_loop, ®ions,
717 sinfo = build_scops_1 (dom_bb, outermost_loop, ®ions, loop);
719 result.exits |= sinfo.exits;
720 result.difficult = true;
724 dominated.release ();
727 move_sd_regions (®ions, scops);
739 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
740 SCOPS. The analyse if a sd_region can be handled is based on the value
741 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
742 is the loop in which CURRENT is handled.
744 TODO: These functions got a little bit big. They definitely should be cleaned
747 static struct scopdet_info
748 build_scops_1 (basic_block current, loop_p outermost_loop,
749 vec<sd_region> *scops, loop_p loop)
751 bool in_scop = false;
753 struct scopdet_info sinfo;
755 /* Initialize result. */
756 struct scopdet_info result;
757 result.exits = false;
758 result.difficult = false;
761 open_scop.entry = NULL;
762 open_scop.exit = NULL;
765 /* Loop over the dominance tree. If we meet a difficult bb, close
766 the current SCoP. Loop and condition header start a new layer,
767 and can only be added if all bbs in deeper layers are simple. */
768 while (current != NULL)
770 sinfo = scopdet_basic_block_info (current, outermost_loop, scops,
771 get_bb_type (current, loop));
773 if (!in_scop && !(sinfo.exits || sinfo.difficult))
775 open_scop.entry = current;
776 open_scop.exit = NULL;
779 else if (in_scop && (sinfo.exits || sinfo.difficult))
781 open_scop.exit = current;
782 scops->safe_push (open_scop);
786 result.difficult |= sinfo.difficult;
787 result.exits |= sinfo.exits;
789 current = sinfo.next;
792 /* Try to close open_scop, if we are still in an open SCoP. */
795 open_scop.exit = sinfo.exit;
796 gcc_assert (open_scop.exit);
797 scops->safe_push (open_scop);
800 result.exit = sinfo.exit;
804 /* Checks if a bb is contained in REGION. */
807 bb_in_sd_region (basic_block bb, sd_region *region)
809 return bb_in_region (bb, region->entry, region->exit);
812 /* Returns the single entry edge of REGION, if it does not exits NULL. */
815 find_single_entry_edge (sd_region *region)
821 FOR_EACH_EDGE (e, ei, region->entry->preds)
822 if (!bb_in_sd_region (e->src, region))
837 /* Returns the single exit edge of REGION, if it does not exits NULL. */
840 find_single_exit_edge (sd_region *region)
846 FOR_EACH_EDGE (e, ei, region->exit->preds)
847 if (bb_in_sd_region (e->src, region))
862 /* Create a single entry edge for REGION. */
865 create_single_entry_edge (sd_region *region)
867 if (find_single_entry_edge (region))
870 /* There are multiple predecessors for bb_3
883 There are two edges (1->3, 2->3), that point from outside into the region,
884 and another one (5->3), a loop latch, lead to bb_3.
892 | |\ (3.0 -> 3.1) = single entry edge
901 If the loop is part of the SCoP, we have to redirect the loop latches.
907 | | (3.0 -> 3.1) = entry edge
916 if (region->entry->loop_father->header != region->entry
917 || dominated_by_p (CDI_DOMINATORS,
918 loop_latch_edge (region->entry->loop_father)->src,
921 edge forwarder = split_block_after_labels (region->entry);
922 region->entry = forwarder->dest;
925 /* This case is never executed, as the loop headers seem always to have a
926 single edge pointing from outside into the loop. */
929 gcc_checking_assert (find_single_entry_edge (region));
932 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
935 sd_region_without_exit (edge e)
937 sd_region *r = (sd_region *) e->aux;
940 return r->exit == NULL;
945 /* Create a single exit edge for REGION. */
948 create_single_exit_edge (sd_region *region)
952 edge forwarder = NULL;
955 /* We create a forwarder bb (5) for all edges leaving this region
956 (3->5, 4->5). All other edges leading to the same bb, are moved
957 to a new bb (6). If these edges where part of another region (2->5)
958 we update the region->exit pointer, of this region.
960 To identify which edge belongs to which region we depend on the e->aux
961 pointer in every edge. It points to the region of the edge or to NULL,
962 if the edge is not part of any region.
964 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
965 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
970 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
971 | | \/ 3->5 no region, 4->5 no region,
973 \| / 5->6 region->exit = 6
976 Now there is only a single exit edge (5->6). */
979 forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
981 /* Unmark the edges, that are no longer exit edges. */
982 FOR_EACH_EDGE (e, ei, forwarder->src->preds)
986 /* Mark the new exit edge. */
987 single_succ_edge (forwarder->src)->aux = region;
989 /* Update the exit bb of all regions, where exit edges lead to
991 FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
993 ((sd_region *) e->aux)->exit = forwarder->dest;
995 gcc_checking_assert (find_single_exit_edge (region));
998 /* Unmark the exit edges of all REGIONS.
999 See comment in "create_single_exit_edge". */
1002 unmark_exit_edges (vec<sd_region> regions)
1009 FOR_EACH_VEC_ELT (regions, i, s)
1010 FOR_EACH_EDGE (e, ei, s->exit->preds)
1015 /* Mark the exit edges of all REGIONS.
1016 See comment in "create_single_exit_edge". */
1019 mark_exit_edges (vec<sd_region> regions)
1026 FOR_EACH_VEC_ELT (regions, i, s)
1027 FOR_EACH_EDGE (e, ei, s->exit->preds)
1028 if (bb_in_sd_region (e->src, s))
1032 /* Create for all scop regions a single entry and a single exit edge. */
1035 create_sese_edges (vec<sd_region> regions)
1040 FOR_EACH_VEC_ELT (regions, i, s)
1041 create_single_entry_edge (s);
1043 mark_exit_edges (regions);
1045 FOR_EACH_VEC_ELT (regions, i, s)
1046 /* Don't handle multiple edges exiting the function. */
1047 if (!find_single_exit_edge (s)
1048 && s->exit != EXIT_BLOCK_PTR_FOR_FN (cfun))
1049 create_single_exit_edge (s);
1051 unmark_exit_edges (regions);
1053 calculate_dominance_info (CDI_DOMINATORS);
1054 fix_loop_structure (NULL);
1056 #ifdef ENABLE_CHECKING
1057 verify_loop_structure ();
1058 verify_ssa (false, true);
1062 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1065 build_graphite_scops (vec<sd_region> regions,
1071 FOR_EACH_VEC_ELT (regions, i, s)
1073 edge entry = find_single_entry_edge (s);
1074 edge exit = find_single_exit_edge (s);
1080 scop = new_scop (new_sese (entry, exit));
1081 scops->safe_push (scop);
1083 /* Are there overlapping SCoPs? */
1084 #ifdef ENABLE_CHECKING
1089 FOR_EACH_VEC_ELT (regions, j, s2)
1091 gcc_assert (!bb_in_sd_region (s->entry, s2));
1097 /* Returns true when BB contains only close phi nodes. */
1100 contains_only_close_phi_nodes (basic_block bb)
1102 gimple_stmt_iterator gsi;
1104 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1105 if (gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
1111 /* Print statistics for SCOP to FILE. */
1114 print_graphite_scop_statistics (FILE* file, scop_p scop)
1119 long n_conditions = 0;
1123 long n_p_conditions = 0;
1127 FOR_ALL_BB_FN (bb, cfun)
1129 gimple_stmt_iterator psi;
1130 loop_p loop = bb->loop_father;
1132 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
1136 n_p_bbs += bb->count;
1138 if (EDGE_COUNT (bb->succs) > 1)
1141 n_p_conditions += bb->count;
1144 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
1147 n_p_stmts += bb->count;
1150 if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
1153 n_p_loops += bb->count;
1158 fprintf (file, "\nBefore limit_scops SCoP statistics (");
1159 fprintf (file, "BBS:%ld, ", n_bbs);
1160 fprintf (file, "LOOPS:%ld, ", n_loops);
1161 fprintf (file, "CONDITIONS:%ld, ", n_conditions);
1162 fprintf (file, "STMTS:%ld)\n", n_stmts);
1163 fprintf (file, "\nBefore limit_scops SCoP profiling statistics (");
1164 fprintf (file, "BBS:%ld, ", n_p_bbs);
1165 fprintf (file, "LOOPS:%ld, ", n_p_loops);
1166 fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
1167 fprintf (file, "STMTS:%ld)\n", n_p_stmts);
1170 /* Print statistics for SCOPS to FILE. */
1173 print_graphite_statistics (FILE* file, vec<scop_p> scops)
1178 FOR_EACH_VEC_ELT (scops, i, scop)
1179 print_graphite_scop_statistics (file, scop);
1182 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1192 * SCoP frontier, as this line is not surrounded by any loop. *
1196 This is necessary as scalar evolution and parameter detection need a
1197 outermost loop to initialize parameters correctly.
1199 TODO: FIX scalar evolution and parameter detection to allow more flexible
1203 limit_scops (vec<scop_p> *scops)
1205 auto_vec<sd_region, 3> regions;
1210 FOR_EACH_VEC_ELT (*scops, i, scop)
1214 sese region = SCOP_REGION (scop);
1215 build_sese_loop_nests (region);
1217 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), j, loop)
1218 if (!loop_in_sese_p (loop_outer (loop), region)
1219 && single_exit (loop))
1221 sd_region open_scop;
1222 open_scop.entry = loop->header;
1223 open_scop.exit = single_exit (loop)->dest;
1225 /* This is a hack on top of the limit_scops hack. The
1226 limit_scops hack should disappear all together. */
1227 if (single_succ_p (open_scop.exit)
1228 && contains_only_close_phi_nodes (open_scop.exit))
1229 open_scop.exit = single_succ_edge (open_scop.exit)->dest;
1231 regions.safe_push (open_scop);
1235 free_scops (*scops);
1238 create_sese_edges (regions);
1239 build_graphite_scops (regions, scops);
1242 /* Returns true when P1 and P2 are close phis with the same
1246 same_close_phi_node (gphi *p1, gphi *p2)
1248 return operand_equal_p (gimple_phi_arg_def (p1, 0),
1249 gimple_phi_arg_def (p2, 0), 0);
1252 /* Remove the close phi node at GSI and replace its rhs with the rhs
1256 remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi)
1259 use_operand_p use_p;
1260 imm_use_iterator imm_iter;
1261 tree res = gimple_phi_result (phi);
1262 tree def = gimple_phi_result (gsi->phi ());
1264 gcc_assert (same_close_phi_node (phi, gsi->phi ()));
1266 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
1268 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
1269 SET_USE (use_p, res);
1271 update_stmt (use_stmt);
1273 /* It is possible that we just created a duplicate close-phi
1274 for an already-processed containing loop. Check for this
1275 case and clean it up. */
1276 if (gimple_code (use_stmt) == GIMPLE_PHI
1277 && gimple_phi_num_args (use_stmt) == 1)
1278 make_close_phi_nodes_unique (gimple_bb (use_stmt));
1281 remove_phi_node (gsi, true);
1284 /* Removes all the close phi duplicates from BB. */
1287 make_close_phi_nodes_unique (basic_block bb)
1291 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1293 gphi_iterator gsi = psi;
1294 gphi *phi = psi.phi ();
1296 /* At this point, PHI should be a close phi in normal form. */
1297 gcc_assert (gimple_phi_num_args (phi) == 1);
1299 /* Iterate over the next phis and remove duplicates. */
1301 while (!gsi_end_p (gsi))
1302 if (same_close_phi_node (phi, gsi.phi ()))
1303 remove_duplicate_close_phi (phi, &gsi);
1309 /* Transforms LOOP to the canonical loop closed SSA form. */
1312 canonicalize_loop_closed_ssa (loop_p loop)
1314 edge e = single_exit (loop);
1317 if (!e || e->flags & EDGE_ABNORMAL)
1322 if (single_pred_p (bb))
1324 e = split_block_after_labels (bb);
1325 make_close_phi_nodes_unique (e->src);
1330 basic_block close = split_edge (e);
1332 e = single_succ_edge (close);
1334 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1336 gphi *phi = psi.phi ();
1339 for (i = 0; i < gimple_phi_num_args (phi); i++)
1340 if (gimple_phi_arg_edge (phi, i) == e)
1342 tree res, arg = gimple_phi_arg_def (phi, i);
1343 use_operand_p use_p;
1346 if (TREE_CODE (arg) != SSA_NAME)
1349 close_phi = create_phi_node (NULL_TREE, close);
1350 res = create_new_def_for (arg, close_phi,
1351 gimple_phi_result_ptr (close_phi));
1352 add_phi_arg (close_phi, arg,
1353 gimple_phi_arg_edge (close_phi, 0),
1355 use_p = gimple_phi_arg_imm_use_ptr (phi, i);
1356 replace_exp (use_p, res);
1361 make_close_phi_nodes_unique (close);
1364 /* The code above does not properly handle changes in the post dominance
1365 information (yet). */
1366 free_dominance_info (CDI_POST_DOMINATORS);
1369 /* Converts the current loop closed SSA form to a canonical form
1370 expected by the Graphite code generation.
1372 The loop closed SSA form has the following invariant: a variable
1373 defined in a loop that is used outside the loop appears only in the
1374 phi nodes in the destination of the loop exit. These phi nodes are
1375 called close phi nodes.
1377 The canonical loop closed SSA form contains the extra invariants:
1379 - when the loop contains only one exit, the close phi nodes contain
1380 only one argument. That implies that the basic block that contains
1381 the close phi nodes has only one predecessor, that is a basic block
1384 - the basic block containing the close phi nodes does not contain
1387 - there exist only one phi node per definition in the loop.
1391 canonicalize_loop_closed_ssa_form (void)
1395 #ifdef ENABLE_CHECKING
1396 verify_loop_closed_ssa (true);
1399 FOR_EACH_LOOP (loop, 0)
1400 canonicalize_loop_closed_ssa (loop);
1402 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1403 update_ssa (TODO_update_ssa);
1405 #ifdef ENABLE_CHECKING
1406 verify_loop_closed_ssa (true);
1410 /* Find Static Control Parts (SCoP) in the current function and pushes
1414 build_scops (vec<scop_p> *scops)
1416 struct loop *loop = current_loops->tree_root;
1417 auto_vec<sd_region, 3> regions;
1419 canonicalize_loop_closed_ssa_form ();
1420 build_scops_1 (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
1421 ENTRY_BLOCK_PTR_FOR_FN (cfun)->loop_father,
1423 create_sese_edges (regions);
1424 build_graphite_scops (regions, scops);
1426 if (dump_file && (dump_flags & TDF_DETAILS))
1427 print_graphite_statistics (dump_file, *scops);
1429 limit_scops (scops);
1432 if (dump_file && (dump_flags & TDF_DETAILS))
1433 fprintf (dump_file, "\nnumber of SCoPs: %d\n",
1434 scops ? scops->length () : 0);
1437 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1438 different colors. If there are not enough colors, paint the
1439 remaining SCoPs in gray.
1442 - "*" after the node number denotes the entry of a SCoP,
1443 - "#" after the node number denotes the exit of a SCoP,
1444 - "()" around the node number denotes the entry or the
1445 exit nodes of the SCOP. These are not part of SCoP. */
1448 dot_all_scops_1 (FILE *file, vec<scop_p> scops)
1457 /* Disable debugging while printing graph. */
1458 int tmp_dump_flags = dump_flags;
1461 fprintf (file, "digraph all {\n");
1463 FOR_ALL_BB_FN (bb, cfun)
1465 int part_of_scop = false;
1467 /* Use HTML for every bb label. So we are able to print bbs
1468 which are part of two different SCoPs, with two different
1469 background colors. */
1470 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1472 fprintf (file, "CELLSPACING=\"0\">\n");
1474 /* Select color for SCoP. */
1475 FOR_EACH_VEC_ELT (scops, i, scop)
1477 sese region = SCOP_REGION (scop);
1478 if (bb_in_sese_p (bb, region)
1479 || (SESE_EXIT_BB (region) == bb)
1480 || (SESE_ENTRY_BB (region) == bb))
1493 case 3: /* purple */
1496 case 4: /* orange */
1499 case 5: /* yellow */
1539 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
1541 if (!bb_in_sese_p (bb, region))
1542 fprintf (file, " (");
1544 if (bb == SESE_ENTRY_BB (region)
1545 && bb == SESE_EXIT_BB (region))
1546 fprintf (file, " %d*# ", bb->index);
1547 else if (bb == SESE_ENTRY_BB (region))
1548 fprintf (file, " %d* ", bb->index);
1549 else if (bb == SESE_EXIT_BB (region))
1550 fprintf (file, " %d# ", bb->index);
1552 fprintf (file, " %d ", bb->index);
1554 if (!bb_in_sese_p (bb,region))
1555 fprintf (file, ")");
1557 fprintf (file, "</TD></TR>\n");
1558 part_of_scop = true;
1564 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1565 fprintf (file, " %d </TD></TR>\n", bb->index);
1567 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1570 FOR_ALL_BB_FN (bb, cfun)
1572 FOR_EACH_EDGE (e, ei, bb->succs)
1573 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
1576 fputs ("}\n\n", file);
1578 /* Enable debugging again. */
1579 dump_flags = tmp_dump_flags;
1582 /* Display all SCoPs using dotty. */
1585 dot_all_scops (vec<scop_p> scops)
1587 /* When debugging, enable the following code. This cannot be used
1588 in production compilers because it calls "system". */
1591 FILE *stream = fopen ("/tmp/allscops.dot", "w");
1592 gcc_assert (stream);
1594 dot_all_scops_1 (stream, scops);
1597 x = system ("dotty /tmp/allscops.dot &");
1599 dot_all_scops_1 (stderr, scops);
1603 /* Display all SCoPs using dotty. */
1606 dot_scop (scop_p scop)
1608 auto_vec<scop_p, 1> scops;
1611 scops.safe_push (scop);
1613 /* When debugging, enable the following code. This cannot be used
1614 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);
1623 x = system ("dotty /tmp/allscops.dot &");
1626 dot_all_scops_1 (stderr, scops);
1630 #endif /* HAVE_isl */