2013-11-21 Edward Smith-Rowland <3dw4rd@verizon.net>
[official-gcc.git] / gcc / graphite-scop-detection.c
blob15c4c0f99ea78dd00fc4b79b519a91b3137ad629
1 /* Detection of Static Control Parts (SCoP) for Graphite.
2 Copyright (C) 2009-2013 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)
11 any later version.
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/>. */
22 #include "config.h"
24 #ifdef HAVE_cloog
25 #include <isl/set.h>
26 #include <isl/map.h>
27 #include <isl/union_map.h>
28 #include <cloog/cloog.h>
29 #include <cloog/isl/domain.h>
30 #endif
32 #include "system.h"
33 #include "coretypes.h"
34 #include "tree.h"
35 #include "gimple.h"
36 #include "gimple-iterator.h"
37 #include "gimple-ssa.h"
38 #include "tree-phinodes.h"
39 #include "ssa-iterators.h"
40 #include "tree-ssa-loop-manip.h"
41 #include "tree-ssa-loop-niter.h"
42 #include "tree-ssa-loop.h"
43 #include "tree-into-ssa.h"
44 #include "tree-ssa.h"
45 #include "cfgloop.h"
46 #include "tree-chrec.h"
47 #include "tree-data-ref.h"
48 #include "tree-scalar-evolution.h"
49 #include "tree-pass.h"
50 #include "sese.h"
51 #include "tree-ssa-propagate.h"
53 #ifdef HAVE_cloog
54 #include "graphite-poly.h"
55 #include "graphite-scop-detection.h"
57 /* Forward declarations. */
58 static void make_close_phi_nodes_unique (basic_block);
60 /* The type of the analyzed basic block. */
62 typedef enum gbb_type {
63 GBB_UNKNOWN,
64 GBB_LOOP_SING_EXIT_HEADER,
65 GBB_LOOP_MULT_EXIT_HEADER,
66 GBB_LOOP_EXIT,
67 GBB_COND_HEADER,
68 GBB_SIMPLE,
69 GBB_LAST
70 } gbb_type;
72 /* Detect the type of BB. Loop headers are only marked, if they are
73 new. This means their loop_father is different to LAST_LOOP.
74 Otherwise they are treated like any other bb and their type can be
75 any other type. */
77 static gbb_type
78 get_bb_type (basic_block bb, struct loop *last_loop)
80 vec<basic_block> dom;
81 int nb_dom;
82 struct loop *loop = bb->loop_father;
84 /* Check, if we entry into a new loop. */
85 if (loop != last_loop)
87 if (single_exit (loop) != NULL)
88 return GBB_LOOP_SING_EXIT_HEADER;
89 else if (loop->num != 0)
90 return GBB_LOOP_MULT_EXIT_HEADER;
91 else
92 return GBB_COND_HEADER;
95 dom = get_dominated_by (CDI_DOMINATORS, bb);
96 nb_dom = dom.length ();
97 dom.release ();
99 if (nb_dom == 0)
100 return GBB_LAST;
102 if (nb_dom == 1 && single_succ_p (bb))
103 return GBB_SIMPLE;
105 return GBB_COND_HEADER;
108 /* A SCoP detection region, defined using bbs as borders.
110 All control flow touching this region, comes in passing basic_block
111 ENTRY and leaves passing basic_block EXIT. By using bbs instead of
112 edges for the borders we are able to represent also regions that do
113 not have a single entry or exit edge.
115 But as they have a single entry basic_block and a single exit
116 basic_block, we are able to generate for every sd_region a single
117 entry and exit edge.
121 3 <- entry
124 / \ This region contains: {3, 4, 5, 6, 7, 8}
129 9 <- exit */
132 typedef struct sd_region_p
134 /* The entry bb dominates all bbs in the sd_region. It is part of
135 the region. */
136 basic_block entry;
138 /* The exit bb postdominates all bbs in the sd_region, but is not
139 part of the region. */
140 basic_block exit;
141 } sd_region;
145 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
147 static void
148 move_sd_regions (vec<sd_region> *source, vec<sd_region> *target)
150 sd_region *s;
151 int i;
153 FOR_EACH_VEC_ELT (*source, i, s)
154 target->safe_push (*s);
156 source->release ();
159 /* Something like "n * m" is not allowed. */
161 static bool
162 graphite_can_represent_init (tree e)
164 switch (TREE_CODE (e))
166 case POLYNOMIAL_CHREC:
167 return graphite_can_represent_init (CHREC_LEFT (e))
168 && graphite_can_represent_init (CHREC_RIGHT (e));
170 case MULT_EXPR:
171 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
172 return graphite_can_represent_init (TREE_OPERAND (e, 0))
173 && tree_fits_shwi_p (TREE_OPERAND (e, 1));
174 else
175 return graphite_can_represent_init (TREE_OPERAND (e, 1))
176 && tree_fits_shwi_p (TREE_OPERAND (e, 0));
178 case PLUS_EXPR:
179 case POINTER_PLUS_EXPR:
180 case MINUS_EXPR:
181 return graphite_can_represent_init (TREE_OPERAND (e, 0))
182 && graphite_can_represent_init (TREE_OPERAND (e, 1));
184 case NEGATE_EXPR:
185 case BIT_NOT_EXPR:
186 CASE_CONVERT:
187 case NON_LVALUE_EXPR:
188 return graphite_can_represent_init (TREE_OPERAND (e, 0));
190 default:
191 break;
194 return true;
197 /* Return true when SCEV can be represented in the polyhedral model.
199 An expression can be represented, if it can be expressed as an
200 affine expression. For loops (i, j) and parameters (m, n) all
201 affine expressions are of the form:
203 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
205 1 i + 20 j + (-2) m + 25
207 Something like "i * n" or "n * m" is not allowed. */
209 static bool
210 graphite_can_represent_scev (tree scev)
212 if (chrec_contains_undetermined (scev))
213 return false;
215 switch (TREE_CODE (scev))
217 case PLUS_EXPR:
218 case MINUS_EXPR:
219 return graphite_can_represent_scev (TREE_OPERAND (scev, 0))
220 && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
222 case MULT_EXPR:
223 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
224 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
225 && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
226 && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
227 && graphite_can_represent_init (scev)
228 && graphite_can_represent_scev (TREE_OPERAND (scev, 0))
229 && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
231 case POLYNOMIAL_CHREC:
232 /* Check for constant strides. With a non constant stride of
233 'n' we would have a value of 'iv * n'. Also check that the
234 initial value can represented: for example 'n * m' cannot be
235 represented. */
236 if (!evolution_function_right_is_integer_cst (scev)
237 || !graphite_can_represent_init (scev))
238 return false;
240 default:
241 break;
244 /* Only affine functions can be represented. */
245 if (!scev_is_linear_expression (scev))
246 return false;
248 return true;
252 /* Return true when EXPR can be represented in the polyhedral model.
254 This means an expression can be represented, if it is linear with
255 respect to the loops and the strides are non parametric.
256 LOOP is the place where the expr will be evaluated. SCOP_ENTRY defines the
257 entry of the region we analyse. */
259 static bool
260 graphite_can_represent_expr (basic_block scop_entry, loop_p loop,
261 tree expr)
263 tree scev = analyze_scalar_evolution (loop, expr);
265 scev = instantiate_scev (scop_entry, loop, scev);
267 return graphite_can_represent_scev (scev);
270 /* Return true if the data references of STMT can be represented by
271 Graphite. */
273 static bool
274 stmt_has_simple_data_refs_p (loop_p outermost_loop ATTRIBUTE_UNUSED,
275 gimple stmt)
277 data_reference_p dr;
278 unsigned i;
279 int j;
280 bool res = true;
281 vec<data_reference_p> drs = vNULL;
282 loop_p outer;
284 for (outer = loop_containing_stmt (stmt); outer; outer = loop_outer (outer))
286 graphite_find_data_references_in_stmt (outer,
287 loop_containing_stmt (stmt),
288 stmt, &drs);
290 FOR_EACH_VEC_ELT (drs, j, dr)
291 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
292 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr, i)))
294 res = false;
295 goto done;
298 free_data_refs (drs);
299 drs.create (0);
302 done:
303 free_data_refs (drs);
304 return res;
307 /* Return true only when STMT is simple enough for being handled by
308 Graphite. This depends on SCOP_ENTRY, as the parameters are
309 initialized relatively to this basic block, the linear functions
310 are initialized to OUTERMOST_LOOP and BB is the place where we try
311 to evaluate the STMT. */
313 static bool
314 stmt_simple_for_scop_p (basic_block scop_entry, loop_p outermost_loop,
315 gimple stmt, basic_block bb)
317 loop_p loop = bb->loop_father;
319 gcc_assert (scop_entry);
321 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
322 Calls have side-effects, except those to const or pure
323 functions. */
324 if (gimple_has_volatile_ops (stmt)
325 || (gimple_code (stmt) == GIMPLE_CALL
326 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
327 || (gimple_code (stmt) == GIMPLE_ASM))
328 return false;
330 if (is_gimple_debug (stmt))
331 return true;
333 if (!stmt_has_simple_data_refs_p (outermost_loop, stmt))
334 return false;
336 switch (gimple_code (stmt))
338 case GIMPLE_RETURN:
339 case GIMPLE_LABEL:
340 return true;
342 case GIMPLE_COND:
344 tree op;
345 ssa_op_iter op_iter;
346 enum tree_code code = gimple_cond_code (stmt);
348 /* We can handle all binary comparisons. Inequalities are
349 also supported as they can be represented with union of
350 polyhedra. */
351 if (!(code == LT_EXPR
352 || code == GT_EXPR
353 || code == LE_EXPR
354 || code == GE_EXPR
355 || code == EQ_EXPR
356 || code == NE_EXPR))
357 return false;
359 FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES)
360 if (!graphite_can_represent_expr (scop_entry, loop, op)
361 /* We can not handle REAL_TYPE. Failed for pr39260. */
362 || TREE_CODE (TREE_TYPE (op)) == REAL_TYPE)
363 return false;
365 return true;
368 case GIMPLE_ASSIGN:
369 case GIMPLE_CALL:
370 return true;
372 default:
373 /* These nodes cut a new scope. */
374 return false;
377 return false;
380 /* Returns the statement of BB that contains a harmful operation: that
381 can be a function call with side effects, the induction variables
382 are not linear with respect to SCOP_ENTRY, etc. The current open
383 scop should end before this statement. The evaluation is limited using
384 OUTERMOST_LOOP as outermost loop that may change. */
386 static gimple
387 harmful_stmt_in_bb (basic_block scop_entry, loop_p outer_loop, basic_block bb)
389 gimple_stmt_iterator gsi;
391 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
392 if (!stmt_simple_for_scop_p (scop_entry, outer_loop, gsi_stmt (gsi), bb))
393 return gsi_stmt (gsi);
395 return NULL;
398 /* Return true if LOOP can be represented in the polyhedral
399 representation. This is evaluated taking SCOP_ENTRY and
400 OUTERMOST_LOOP in mind. */
402 static bool
403 graphite_can_represent_loop (basic_block scop_entry, loop_p loop)
405 tree niter;
406 struct tree_niter_desc niter_desc;
408 /* FIXME: For the moment, graphite cannot be used on loops that
409 iterate using induction variables that wrap. */
411 return number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false)
412 && niter_desc.control.no_overflow
413 && (niter = number_of_latch_executions (loop))
414 && !chrec_contains_undetermined (niter)
415 && graphite_can_represent_expr (scop_entry, loop, niter);
418 /* Store information needed by scopdet_* functions. */
420 struct scopdet_info
422 /* Exit of the open scop would stop if the current BB is harmful. */
423 basic_block exit;
425 /* Where the next scop would start if the current BB is harmful. */
426 basic_block next;
428 /* The bb or one of its children contains open loop exits. That means
429 loop exit nodes that are not surrounded by a loop dominated by bb. */
430 bool exits;
432 /* The bb or one of its children contains only structures we can handle. */
433 bool difficult;
436 static struct scopdet_info build_scops_1 (basic_block, loop_p,
437 vec<sd_region> *, loop_p);
439 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
440 to SCOPS. TYPE is the gbb_type of BB. */
442 static struct scopdet_info
443 scopdet_basic_block_info (basic_block bb, loop_p outermost_loop,
444 vec<sd_region> *scops, gbb_type type)
446 loop_p loop = bb->loop_father;
447 struct scopdet_info result;
448 gimple stmt;
450 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
451 basic_block entry_block = ENTRY_BLOCK_PTR_FOR_FN (cfun);
452 stmt = harmful_stmt_in_bb (entry_block, outermost_loop, bb);
453 result.difficult = (stmt != NULL);
454 result.exit = NULL;
456 switch (type)
458 case GBB_LAST:
459 result.next = NULL;
460 result.exits = false;
462 /* Mark bbs terminating a SESE region difficult, if they start
463 a condition. */
464 if (!single_succ_p (bb))
465 result.difficult = true;
466 else
467 result.exit = single_succ (bb);
469 break;
471 case GBB_SIMPLE:
472 result.next = single_succ (bb);
473 result.exits = false;
474 result.exit = single_succ (bb);
475 break;
477 case GBB_LOOP_SING_EXIT_HEADER:
479 stack_vec<sd_region, 3> regions;
480 struct scopdet_info sinfo;
481 edge exit_e = single_exit (loop);
483 sinfo = build_scops_1 (bb, outermost_loop, &regions, loop);
485 if (!graphite_can_represent_loop (entry_block, loop))
486 result.difficult = true;
488 result.difficult |= sinfo.difficult;
490 /* Try again with another loop level. */
491 if (result.difficult
492 && loop_depth (outermost_loop) + 1 == loop_depth (loop))
494 outermost_loop = loop;
496 regions.release ();
497 regions.create (3);
499 sinfo = scopdet_basic_block_info (bb, outermost_loop, scops, type);
501 result = sinfo;
502 result.difficult = true;
504 if (sinfo.difficult)
505 move_sd_regions (&regions, scops);
506 else
508 sd_region open_scop;
509 open_scop.entry = bb;
510 open_scop.exit = exit_e->dest;
511 scops->safe_push (open_scop);
512 regions.release ();
515 else
517 result.exit = exit_e->dest;
518 result.next = exit_e->dest;
520 /* If we do not dominate result.next, remove it. It's either
521 the exit block, or another bb dominates it and will
522 call the scop detection for this bb. */
523 if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
524 result.next = NULL;
526 if (exit_e->src->loop_father != loop)
527 result.next = NULL;
529 result.exits = false;
531 if (result.difficult)
532 move_sd_regions (&regions, scops);
533 else
534 regions.release ();
537 break;
540 case GBB_LOOP_MULT_EXIT_HEADER:
542 /* XXX: For now we just do not join loops with multiple exits. If the
543 exits lead to the same bb it may be possible to join the loop. */
544 stack_vec<sd_region, 3> regions;
545 vec<edge> exits = get_loop_exit_edges (loop);
546 edge e;
547 int i;
548 build_scops_1 (bb, loop, &regions, loop);
550 /* Scan the code dominated by this loop. This means all bbs, that are
551 are dominated by a bb in this loop, but are not part of this loop.
553 The easiest case:
554 - The loop exit destination is dominated by the exit sources.
556 TODO: We miss here the more complex cases:
557 - The exit destinations are dominated by another bb inside
558 the loop.
559 - The loop dominates bbs, that are not exit destinations. */
560 FOR_EACH_VEC_ELT (exits, i, e)
561 if (e->src->loop_father == loop
562 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
564 if (loop_outer (outermost_loop))
565 outermost_loop = loop_outer (outermost_loop);
567 /* Pass loop_outer to recognize e->dest as loop header in
568 build_scops_1. */
569 if (e->dest->loop_father->header == e->dest)
570 build_scops_1 (e->dest, outermost_loop, &regions,
571 loop_outer (e->dest->loop_father));
572 else
573 build_scops_1 (e->dest, outermost_loop, &regions,
574 e->dest->loop_father);
577 result.next = NULL;
578 result.exit = NULL;
579 result.difficult = true;
580 result.exits = false;
581 move_sd_regions (&regions, scops);
582 exits.release ();
583 break;
585 case GBB_COND_HEADER:
587 stack_vec<sd_region, 3> regions;
588 struct scopdet_info sinfo;
589 vec<basic_block> dominated;
590 int i;
591 basic_block dom_bb;
592 basic_block last_exit = NULL;
593 edge e;
594 result.exits = false;
596 /* First check the successors of BB, and check if it is
597 possible to join the different branches. */
598 FOR_EACH_VEC_SAFE_ELT (bb->succs, i, e)
600 /* Ignore loop exits. They will be handled after the loop
601 body. */
602 if (loop_exits_to_bb_p (loop, e->dest))
604 result.exits = true;
605 continue;
608 /* Do not follow edges that lead to the end of the
609 conditions block. For example, in
612 | /|\
613 | 1 2 |
614 | | | |
615 | 3 4 |
616 | \|/
619 the edge from 0 => 6. Only check if all paths lead to
620 the same node 6. */
622 if (!single_pred_p (e->dest))
624 /* Check, if edge leads directly to the end of this
625 condition. */
626 if (!last_exit)
627 last_exit = e->dest;
629 if (e->dest != last_exit)
630 result.difficult = true;
632 continue;
635 if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
637 result.difficult = true;
638 continue;
641 sinfo = build_scops_1 (e->dest, outermost_loop, &regions, loop);
643 result.exits |= sinfo.exits;
644 result.difficult |= sinfo.difficult;
646 /* Checks, if all branches end at the same point.
647 If that is true, the condition stays joinable.
648 Have a look at the example above. */
649 if (sinfo.exit)
651 if (!last_exit)
652 last_exit = sinfo.exit;
654 if (sinfo.exit != last_exit)
655 result.difficult = true;
657 else
658 result.difficult = true;
661 if (!last_exit)
662 result.difficult = true;
664 /* Join the branches of the condition if possible. */
665 if (!result.exits && !result.difficult)
667 /* Only return a next pointer if we dominate this pointer.
668 Otherwise it will be handled by the bb dominating it. */
669 if (dominated_by_p (CDI_DOMINATORS, last_exit, bb)
670 && last_exit != bb)
671 result.next = last_exit;
672 else
673 result.next = NULL;
675 result.exit = last_exit;
677 regions.release ();
678 break;
681 /* Scan remaining bbs dominated by BB. */
682 dominated = get_dominated_by (CDI_DOMINATORS, bb);
684 FOR_EACH_VEC_ELT (dominated, i, dom_bb)
686 /* Ignore loop exits: they will be handled after the loop body. */
687 if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
688 < loop_depth (loop))
690 result.exits = true;
691 continue;
694 /* Ignore the bbs processed above. */
695 if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
696 continue;
698 if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
699 sinfo = build_scops_1 (dom_bb, outermost_loop, &regions,
700 loop_outer (loop));
701 else
702 sinfo = build_scops_1 (dom_bb, outermost_loop, &regions, loop);
704 result.exits |= sinfo.exits;
705 result.difficult = true;
706 result.exit = NULL;
709 dominated.release ();
711 result.next = NULL;
712 move_sd_regions (&regions, scops);
714 break;
717 default:
718 gcc_unreachable ();
721 return result;
724 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
725 SCOPS. The analyse if a sd_region can be handled is based on the value
726 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
727 is the loop in which CURRENT is handled.
729 TODO: These functions got a little bit big. They definitely should be cleaned
730 up. */
732 static struct scopdet_info
733 build_scops_1 (basic_block current, loop_p outermost_loop,
734 vec<sd_region> *scops, loop_p loop)
736 bool in_scop = false;
737 sd_region open_scop;
738 struct scopdet_info sinfo;
740 /* Initialize result. */
741 struct scopdet_info result;
742 result.exits = false;
743 result.difficult = false;
744 result.next = NULL;
745 result.exit = NULL;
746 open_scop.entry = NULL;
747 open_scop.exit = NULL;
748 sinfo.exit = NULL;
750 /* Loop over the dominance tree. If we meet a difficult bb, close
751 the current SCoP. Loop and condition header start a new layer,
752 and can only be added if all bbs in deeper layers are simple. */
753 while (current != NULL)
755 sinfo = scopdet_basic_block_info (current, outermost_loop, scops,
756 get_bb_type (current, loop));
758 if (!in_scop && !(sinfo.exits || sinfo.difficult))
760 open_scop.entry = current;
761 open_scop.exit = NULL;
762 in_scop = true;
764 else if (in_scop && (sinfo.exits || sinfo.difficult))
766 open_scop.exit = current;
767 scops->safe_push (open_scop);
768 in_scop = false;
771 result.difficult |= sinfo.difficult;
772 result.exits |= sinfo.exits;
774 current = sinfo.next;
777 /* Try to close open_scop, if we are still in an open SCoP. */
778 if (in_scop)
780 open_scop.exit = sinfo.exit;
781 gcc_assert (open_scop.exit);
782 scops->safe_push (open_scop);
785 result.exit = sinfo.exit;
786 return result;
789 /* Checks if a bb is contained in REGION. */
791 static bool
792 bb_in_sd_region (basic_block bb, sd_region *region)
794 return bb_in_region (bb, region->entry, region->exit);
797 /* Returns the single entry edge of REGION, if it does not exits NULL. */
799 static edge
800 find_single_entry_edge (sd_region *region)
802 edge e;
803 edge_iterator ei;
804 edge entry = NULL;
806 FOR_EACH_EDGE (e, ei, region->entry->preds)
807 if (!bb_in_sd_region (e->src, region))
809 if (entry)
811 entry = NULL;
812 break;
815 else
816 entry = e;
819 return entry;
822 /* Returns the single exit edge of REGION, if it does not exits NULL. */
824 static edge
825 find_single_exit_edge (sd_region *region)
827 edge e;
828 edge_iterator ei;
829 edge exit = NULL;
831 FOR_EACH_EDGE (e, ei, region->exit->preds)
832 if (bb_in_sd_region (e->src, region))
834 if (exit)
836 exit = NULL;
837 break;
840 else
841 exit = e;
844 return exit;
847 /* Create a single entry edge for REGION. */
849 static void
850 create_single_entry_edge (sd_region *region)
852 if (find_single_entry_edge (region))
853 return;
855 /* There are multiple predecessors for bb_3
857 | 1 2
858 | | /
859 | |/
860 | 3 <- entry
861 | |\
862 | | |
863 | 4 ^
864 | | |
865 | |/
868 There are two edges (1->3, 2->3), that point from outside into the region,
869 and another one (5->3), a loop latch, lead to bb_3.
871 We split bb_3.
873 | 1 2
874 | | /
875 | |/
876 |3.0
877 | |\ (3.0 -> 3.1) = single entry edge
878 |3.1 | <- entry
879 | | |
880 | | |
881 | 4 ^
882 | | |
883 | |/
886 If the loop is part of the SCoP, we have to redirect the loop latches.
888 | 1 2
889 | | /
890 | |/
891 |3.0
892 | | (3.0 -> 3.1) = entry edge
893 |3.1 <- entry
894 | |\
895 | | |
896 | 4 ^
897 | | |
898 | |/
899 | 5 */
901 if (region->entry->loop_father->header != region->entry
902 || dominated_by_p (CDI_DOMINATORS,
903 loop_latch_edge (region->entry->loop_father)->src,
904 region->exit))
906 edge forwarder = split_block_after_labels (region->entry);
907 region->entry = forwarder->dest;
909 else
910 /* This case is never executed, as the loop headers seem always to have a
911 single edge pointing from outside into the loop. */
912 gcc_unreachable ();
914 gcc_checking_assert (find_single_entry_edge (region));
917 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
919 static bool
920 sd_region_without_exit (edge e)
922 sd_region *r = (sd_region *) e->aux;
924 if (r)
925 return r->exit == NULL;
926 else
927 return false;
930 /* Create a single exit edge for REGION. */
932 static void
933 create_single_exit_edge (sd_region *region)
935 edge e;
936 edge_iterator ei;
937 edge forwarder = NULL;
938 basic_block exit;
940 /* We create a forwarder bb (5) for all edges leaving this region
941 (3->5, 4->5). All other edges leading to the same bb, are moved
942 to a new bb (6). If these edges where part of another region (2->5)
943 we update the region->exit pointer, of this region.
945 To identify which edge belongs to which region we depend on the e->aux
946 pointer in every edge. It points to the region of the edge or to NULL,
947 if the edge is not part of any region.
949 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
950 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
951 5 <- exit
953 changes to
955 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
956 | | \/ 3->5 no region, 4->5 no region,
957 | | 5
958 \| / 5->6 region->exit = 6
961 Now there is only a single exit edge (5->6). */
962 exit = region->exit;
963 region->exit = NULL;
964 forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
966 /* Unmark the edges, that are no longer exit edges. */
967 FOR_EACH_EDGE (e, ei, forwarder->src->preds)
968 if (e->aux)
969 e->aux = NULL;
971 /* Mark the new exit edge. */
972 single_succ_edge (forwarder->src)->aux = region;
974 /* Update the exit bb of all regions, where exit edges lead to
975 forwarder->dest. */
976 FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
977 if (e->aux)
978 ((sd_region *) e->aux)->exit = forwarder->dest;
980 gcc_checking_assert (find_single_exit_edge (region));
983 /* Unmark the exit edges of all REGIONS.
984 See comment in "create_single_exit_edge". */
986 static void
987 unmark_exit_edges (vec<sd_region> regions)
989 int i;
990 sd_region *s;
991 edge e;
992 edge_iterator ei;
994 FOR_EACH_VEC_ELT (regions, i, s)
995 FOR_EACH_EDGE (e, ei, s->exit->preds)
996 e->aux = NULL;
1000 /* Mark the exit edges of all REGIONS.
1001 See comment in "create_single_exit_edge". */
1003 static void
1004 mark_exit_edges (vec<sd_region> regions)
1006 int i;
1007 sd_region *s;
1008 edge e;
1009 edge_iterator ei;
1011 FOR_EACH_VEC_ELT (regions, i, s)
1012 FOR_EACH_EDGE (e, ei, s->exit->preds)
1013 if (bb_in_sd_region (e->src, s))
1014 e->aux = s;
1017 /* Create for all scop regions a single entry and a single exit edge. */
1019 static void
1020 create_sese_edges (vec<sd_region> regions)
1022 int i;
1023 sd_region *s;
1025 FOR_EACH_VEC_ELT (regions, i, s)
1026 create_single_entry_edge (s);
1028 mark_exit_edges (regions);
1030 FOR_EACH_VEC_ELT (regions, i, s)
1031 /* Don't handle multiple edges exiting the function. */
1032 if (!find_single_exit_edge (s)
1033 && s->exit != EXIT_BLOCK_PTR_FOR_FN (cfun))
1034 create_single_exit_edge (s);
1036 unmark_exit_edges (regions);
1038 calculate_dominance_info (CDI_DOMINATORS);
1039 fix_loop_structure (NULL);
1041 #ifdef ENABLE_CHECKING
1042 verify_loop_structure ();
1043 verify_ssa (false);
1044 #endif
1047 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1049 static void
1050 build_graphite_scops (vec<sd_region> regions,
1051 vec<scop_p> *scops)
1053 int i;
1054 sd_region *s;
1056 FOR_EACH_VEC_ELT (regions, i, s)
1058 edge entry = find_single_entry_edge (s);
1059 edge exit = find_single_exit_edge (s);
1060 scop_p scop;
1062 if (!exit)
1063 continue;
1065 scop = new_scop (new_sese (entry, exit));
1066 scops->safe_push (scop);
1068 /* Are there overlapping SCoPs? */
1069 #ifdef ENABLE_CHECKING
1071 int j;
1072 sd_region *s2;
1074 FOR_EACH_VEC_ELT (regions, j, s2)
1075 if (s != s2)
1076 gcc_assert (!bb_in_sd_region (s->entry, s2));
1078 #endif
1082 /* Returns true when BB contains only close phi nodes. */
1084 static bool
1085 contains_only_close_phi_nodes (basic_block bb)
1087 gimple_stmt_iterator gsi;
1089 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1090 if (gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
1091 return false;
1093 return true;
1096 /* Print statistics for SCOP to FILE. */
1098 static void
1099 print_graphite_scop_statistics (FILE* file, scop_p scop)
1101 long n_bbs = 0;
1102 long n_loops = 0;
1103 long n_stmts = 0;
1104 long n_conditions = 0;
1105 long n_p_bbs = 0;
1106 long n_p_loops = 0;
1107 long n_p_stmts = 0;
1108 long n_p_conditions = 0;
1110 basic_block bb;
1112 FOR_ALL_BB (bb)
1114 gimple_stmt_iterator psi;
1115 loop_p loop = bb->loop_father;
1117 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
1118 continue;
1120 n_bbs++;
1121 n_p_bbs += bb->count;
1123 if (EDGE_COUNT (bb->succs) > 1)
1125 n_conditions++;
1126 n_p_conditions += bb->count;
1129 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
1131 n_stmts++;
1132 n_p_stmts += bb->count;
1135 if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
1137 n_loops++;
1138 n_p_loops += bb->count;
1143 fprintf (file, "\nBefore limit_scops SCoP statistics (");
1144 fprintf (file, "BBS:%ld, ", n_bbs);
1145 fprintf (file, "LOOPS:%ld, ", n_loops);
1146 fprintf (file, "CONDITIONS:%ld, ", n_conditions);
1147 fprintf (file, "STMTS:%ld)\n", n_stmts);
1148 fprintf (file, "\nBefore limit_scops SCoP profiling statistics (");
1149 fprintf (file, "BBS:%ld, ", n_p_bbs);
1150 fprintf (file, "LOOPS:%ld, ", n_p_loops);
1151 fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
1152 fprintf (file, "STMTS:%ld)\n", n_p_stmts);
1155 /* Print statistics for SCOPS to FILE. */
1157 static void
1158 print_graphite_statistics (FILE* file, vec<scop_p> scops)
1160 int i;
1161 scop_p scop;
1163 FOR_EACH_VEC_ELT (scops, i, scop)
1164 print_graphite_scop_statistics (file, scop);
1167 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1169 Example:
1171 for (i |
1173 for (j | SCoP 1
1174 for (k |
1177 * SCoP frontier, as this line is not surrounded by any loop. *
1179 for (l | SCoP 2
1181 This is necessary as scalar evolution and parameter detection need a
1182 outermost loop to initialize parameters correctly.
1184 TODO: FIX scalar evolution and parameter detection to allow more flexible
1185 SCoP frontiers. */
1187 static void
1188 limit_scops (vec<scop_p> *scops)
1190 stack_vec<sd_region, 3> regions;
1192 int i;
1193 scop_p scop;
1195 FOR_EACH_VEC_ELT (*scops, i, scop)
1197 int j;
1198 loop_p loop;
1199 sese region = SCOP_REGION (scop);
1200 build_sese_loop_nests (region);
1202 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), j, loop)
1203 if (!loop_in_sese_p (loop_outer (loop), region)
1204 && single_exit (loop))
1206 sd_region open_scop;
1207 open_scop.entry = loop->header;
1208 open_scop.exit = single_exit (loop)->dest;
1210 /* This is a hack on top of the limit_scops hack. The
1211 limit_scops hack should disappear all together. */
1212 if (single_succ_p (open_scop.exit)
1213 && contains_only_close_phi_nodes (open_scop.exit))
1214 open_scop.exit = single_succ_edge (open_scop.exit)->dest;
1216 regions.safe_push (open_scop);
1220 free_scops (*scops);
1221 scops->create (3);
1223 create_sese_edges (regions);
1224 build_graphite_scops (regions, scops);
1227 /* Returns true when P1 and P2 are close phis with the same
1228 argument. */
1230 static inline bool
1231 same_close_phi_node (gimple p1, gimple p2)
1233 return operand_equal_p (gimple_phi_arg_def (p1, 0),
1234 gimple_phi_arg_def (p2, 0), 0);
1237 /* Remove the close phi node at GSI and replace its rhs with the rhs
1238 of PHI. */
1240 static void
1241 remove_duplicate_close_phi (gimple phi, gimple_stmt_iterator *gsi)
1243 gimple use_stmt;
1244 use_operand_p use_p;
1245 imm_use_iterator imm_iter;
1246 tree res = gimple_phi_result (phi);
1247 tree def = gimple_phi_result (gsi_stmt (*gsi));
1249 gcc_assert (same_close_phi_node (phi, gsi_stmt (*gsi)));
1251 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
1253 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
1254 SET_USE (use_p, res);
1256 update_stmt (use_stmt);
1258 /* It is possible that we just created a duplicate close-phi
1259 for an already-processed containing loop. Check for this
1260 case and clean it up. */
1261 if (gimple_code (use_stmt) == GIMPLE_PHI
1262 && gimple_phi_num_args (use_stmt) == 1)
1263 make_close_phi_nodes_unique (gimple_bb (use_stmt));
1266 remove_phi_node (gsi, true);
1269 /* Removes all the close phi duplicates from BB. */
1271 static void
1272 make_close_phi_nodes_unique (basic_block bb)
1274 gimple_stmt_iterator psi;
1276 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1278 gimple_stmt_iterator gsi = psi;
1279 gimple phi = gsi_stmt (psi);
1281 /* At this point, PHI should be a close phi in normal form. */
1282 gcc_assert (gimple_phi_num_args (phi) == 1);
1284 /* Iterate over the next phis and remove duplicates. */
1285 gsi_next (&gsi);
1286 while (!gsi_end_p (gsi))
1287 if (same_close_phi_node (phi, gsi_stmt (gsi)))
1288 remove_duplicate_close_phi (phi, &gsi);
1289 else
1290 gsi_next (&gsi);
1294 /* Transforms LOOP to the canonical loop closed SSA form. */
1296 static void
1297 canonicalize_loop_closed_ssa (loop_p loop)
1299 edge e = single_exit (loop);
1300 basic_block bb;
1302 if (!e || e->flags & EDGE_ABNORMAL)
1303 return;
1305 bb = e->dest;
1307 if (single_pred_p (bb))
1309 e = split_block_after_labels (bb);
1310 make_close_phi_nodes_unique (e->src);
1312 else
1314 gimple_stmt_iterator psi;
1315 basic_block close = split_edge (e);
1317 e = single_succ_edge (close);
1319 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1321 gimple phi = gsi_stmt (psi);
1322 unsigned i;
1324 for (i = 0; i < gimple_phi_num_args (phi); i++)
1325 if (gimple_phi_arg_edge (phi, i) == e)
1327 tree res, arg = gimple_phi_arg_def (phi, i);
1328 use_operand_p use_p;
1329 gimple close_phi;
1331 if (TREE_CODE (arg) != SSA_NAME)
1332 continue;
1334 close_phi = create_phi_node (NULL_TREE, close);
1335 res = create_new_def_for (arg, close_phi,
1336 gimple_phi_result_ptr (close_phi));
1337 add_phi_arg (close_phi, arg,
1338 gimple_phi_arg_edge (close_phi, 0),
1339 UNKNOWN_LOCATION);
1340 use_p = gimple_phi_arg_imm_use_ptr (phi, i);
1341 replace_exp (use_p, res);
1342 update_stmt (phi);
1346 make_close_phi_nodes_unique (close);
1349 /* The code above does not properly handle changes in the post dominance
1350 information (yet). */
1351 free_dominance_info (CDI_POST_DOMINATORS);
1354 /* Converts the current loop closed SSA form to a canonical form
1355 expected by the Graphite code generation.
1357 The loop closed SSA form has the following invariant: a variable
1358 defined in a loop that is used outside the loop appears only in the
1359 phi nodes in the destination of the loop exit. These phi nodes are
1360 called close phi nodes.
1362 The canonical loop closed SSA form contains the extra invariants:
1364 - when the loop contains only one exit, the close phi nodes contain
1365 only one argument. That implies that the basic block that contains
1366 the close phi nodes has only one predecessor, that is a basic block
1367 in the loop.
1369 - the basic block containing the close phi nodes does not contain
1370 other statements.
1372 - there exist only one phi node per definition in the loop.
1375 static void
1376 canonicalize_loop_closed_ssa_form (void)
1378 loop_p loop;
1380 #ifdef ENABLE_CHECKING
1381 verify_loop_closed_ssa (true);
1382 #endif
1384 FOR_EACH_LOOP (loop, 0)
1385 canonicalize_loop_closed_ssa (loop);
1387 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1388 update_ssa (TODO_update_ssa);
1390 #ifdef ENABLE_CHECKING
1391 verify_loop_closed_ssa (true);
1392 #endif
1395 /* Find Static Control Parts (SCoP) in the current function and pushes
1396 them to SCOPS. */
1398 void
1399 build_scops (vec<scop_p> *scops)
1401 struct loop *loop = current_loops->tree_root;
1402 stack_vec<sd_region, 3> regions;
1404 canonicalize_loop_closed_ssa_form ();
1405 build_scops_1 (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
1406 ENTRY_BLOCK_PTR_FOR_FN (cfun)->loop_father,
1407 &regions, loop);
1408 create_sese_edges (regions);
1409 build_graphite_scops (regions, scops);
1411 if (dump_file && (dump_flags & TDF_DETAILS))
1412 print_graphite_statistics (dump_file, *scops);
1414 limit_scops (scops);
1415 regions.release ();
1417 if (dump_file && (dump_flags & TDF_DETAILS))
1418 fprintf (dump_file, "\nnumber of SCoPs: %d\n",
1419 scops ? scops->length () : 0);
1422 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1423 different colors. If there are not enough colors, paint the
1424 remaining SCoPs in gray.
1426 Special nodes:
1427 - "*" after the node number denotes the entry of a SCoP,
1428 - "#" after the node number denotes the exit of a SCoP,
1429 - "()" around the node number denotes the entry or the
1430 exit nodes of the SCOP. These are not part of SCoP. */
1432 static void
1433 dot_all_scops_1 (FILE *file, vec<scop_p> scops)
1435 basic_block bb;
1436 edge e;
1437 edge_iterator ei;
1438 scop_p scop;
1439 const char* color;
1440 int i;
1442 /* Disable debugging while printing graph. */
1443 int tmp_dump_flags = dump_flags;
1444 dump_flags = 0;
1446 fprintf (file, "digraph all {\n");
1448 FOR_ALL_BB (bb)
1450 int part_of_scop = false;
1452 /* Use HTML for every bb label. So we are able to print bbs
1453 which are part of two different SCoPs, with two different
1454 background colors. */
1455 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1456 bb->index);
1457 fprintf (file, "CELLSPACING=\"0\">\n");
1459 /* Select color for SCoP. */
1460 FOR_EACH_VEC_ELT (scops, i, scop)
1462 sese region = SCOP_REGION (scop);
1463 if (bb_in_sese_p (bb, region)
1464 || (SESE_EXIT_BB (region) == bb)
1465 || (SESE_ENTRY_BB (region) == bb))
1467 switch (i % 17)
1469 case 0: /* red */
1470 color = "#e41a1c";
1471 break;
1472 case 1: /* blue */
1473 color = "#377eb8";
1474 break;
1475 case 2: /* green */
1476 color = "#4daf4a";
1477 break;
1478 case 3: /* purple */
1479 color = "#984ea3";
1480 break;
1481 case 4: /* orange */
1482 color = "#ff7f00";
1483 break;
1484 case 5: /* yellow */
1485 color = "#ffff33";
1486 break;
1487 case 6: /* brown */
1488 color = "#a65628";
1489 break;
1490 case 7: /* rose */
1491 color = "#f781bf";
1492 break;
1493 case 8:
1494 color = "#8dd3c7";
1495 break;
1496 case 9:
1497 color = "#ffffb3";
1498 break;
1499 case 10:
1500 color = "#bebada";
1501 break;
1502 case 11:
1503 color = "#fb8072";
1504 break;
1505 case 12:
1506 color = "#80b1d3";
1507 break;
1508 case 13:
1509 color = "#fdb462";
1510 break;
1511 case 14:
1512 color = "#b3de69";
1513 break;
1514 case 15:
1515 color = "#fccde5";
1516 break;
1517 case 16:
1518 color = "#bc80bd";
1519 break;
1520 default: /* gray */
1521 color = "#999999";
1524 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
1526 if (!bb_in_sese_p (bb, region))
1527 fprintf (file, " (");
1529 if (bb == SESE_ENTRY_BB (region)
1530 && bb == SESE_EXIT_BB (region))
1531 fprintf (file, " %d*# ", bb->index);
1532 else if (bb == SESE_ENTRY_BB (region))
1533 fprintf (file, " %d* ", bb->index);
1534 else if (bb == SESE_EXIT_BB (region))
1535 fprintf (file, " %d# ", bb->index);
1536 else
1537 fprintf (file, " %d ", bb->index);
1539 if (!bb_in_sese_p (bb,region))
1540 fprintf (file, ")");
1542 fprintf (file, "</TD></TR>\n");
1543 part_of_scop = true;
1547 if (!part_of_scop)
1549 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1550 fprintf (file, " %d </TD></TR>\n", bb->index);
1552 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1555 FOR_ALL_BB (bb)
1557 FOR_EACH_EDGE (e, ei, bb->succs)
1558 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
1561 fputs ("}\n\n", file);
1563 /* Enable debugging again. */
1564 dump_flags = tmp_dump_flags;
1567 /* Display all SCoPs using dotty. */
1569 DEBUG_FUNCTION void
1570 dot_all_scops (vec<scop_p> scops)
1572 /* When debugging, enable the following code. This cannot be used
1573 in production compilers because it calls "system". */
1574 #if 0
1575 int x;
1576 FILE *stream = fopen ("/tmp/allscops.dot", "w");
1577 gcc_assert (stream);
1579 dot_all_scops_1 (stream, scops);
1580 fclose (stream);
1582 x = system ("dotty /tmp/allscops.dot &");
1583 #else
1584 dot_all_scops_1 (stderr, scops);
1585 #endif
1588 /* Display all SCoPs using dotty. */
1590 DEBUG_FUNCTION void
1591 dot_scop (scop_p scop)
1593 stack_vec<scop_p, 1> scops;
1595 if (scop)
1596 scops.safe_push (scop);
1598 /* When debugging, enable the following code. This cannot be used
1599 in production compilers because it calls "system". */
1600 #if 0
1602 int x;
1603 FILE *stream = fopen ("/tmp/allscops.dot", "w");
1604 gcc_assert (stream);
1606 dot_all_scops_1 (stream, scops);
1607 fclose (stream);
1608 x = system ("dotty /tmp/allscops.dot &");
1610 #else
1611 dot_all_scops_1 (stderr, scops);
1612 #endif
1615 #endif