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. */
28 #include <isl/constraint.h>
31 #include <isl/union_map.h>
34 #include "coretypes.h"
40 #include "fold-const.h"
41 #include "gimple-iterator.h"
42 #include "tree-ssa-loop-manip.h"
43 #include "tree-ssa-loop-niter.h"
44 #include "tree-ssa-loop.h"
45 #include "tree-into-ssa.h"
48 #include "tree-data-ref.h"
49 #include "tree-scalar-evolution.h"
50 #include "tree-pass.h"
51 #include "graphite-poly.h"
52 #include "tree-ssa-propagate.h"
53 #include "graphite-scop-detection.h"
54 #include "gimple-pretty-print.h"
56 /* Forward declarations. */
57 static void make_close_phi_nodes_unique (basic_block
);
59 /* The type of the analyzed basic block. */
63 GBB_LOOP_SING_EXIT_HEADER
,
64 GBB_LOOP_MULT_EXIT_HEADER
,
71 /* Detect the type of BB. Loop headers are only marked, if they are
72 new. This means their loop_father is different to LAST_LOOP.
73 Otherwise they are treated like any other bb and their type can be
77 get_bb_type (basic_block bb
, struct loop
*last_loop
)
81 struct loop
*loop
= bb
->loop_father
;
83 /* Check, if we entry into a new loop. */
84 if (loop
!= last_loop
)
86 if (single_exit (loop
) != NULL
)
87 return GBB_LOOP_SING_EXIT_HEADER
;
88 else if (loop
->num
!= 0)
89 return GBB_LOOP_MULT_EXIT_HEADER
;
91 return GBB_COND_HEADER
;
94 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
95 nb_dom
= dom
.length ();
101 if (nb_dom
== 1 && single_succ_p (bb
))
104 return GBB_COND_HEADER
;
107 /* A SCoP detection region, defined using bbs as borders.
109 All control flow touching this region, comes in passing basic_block
110 ENTRY and leaves passing basic_block EXIT. By using bbs instead of
111 edges for the borders we are able to represent also regions that do
112 not have a single entry or exit edge.
114 But as they have a single entry basic_block and a single exit
115 basic_block, we are able to generate for every sd_region a single
123 / \ This region contains: {3, 4, 5, 6, 7, 8}
133 /* The entry bb dominates all bbs in the sd_region. It is part of
137 /* The exit bb postdominates all bbs in the sd_region, but is not
138 part of the region. */
144 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
147 move_sd_regions (vec
<sd_region
> *source
, vec
<sd_region
> *target
)
152 FOR_EACH_VEC_ELT (*source
, i
, s
)
153 target
->safe_push (*s
);
158 /* Something like "n * m" is not allowed. */
161 graphite_can_represent_init (tree e
)
163 switch (TREE_CODE (e
))
165 case POLYNOMIAL_CHREC
:
166 return graphite_can_represent_init (CHREC_LEFT (e
))
167 && graphite_can_represent_init (CHREC_RIGHT (e
));
170 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
171 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
172 && tree_fits_shwi_p (TREE_OPERAND (e
, 1));
174 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
175 && tree_fits_shwi_p (TREE_OPERAND (e
, 0));
178 case POINTER_PLUS_EXPR
:
180 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
181 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
186 case NON_LVALUE_EXPR
:
187 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
196 /* Return true when SCEV can be represented in the polyhedral model.
198 An expression can be represented, if it can be expressed as an
199 affine expression. For loops (i, j) and parameters (m, n) all
200 affine expressions are of the form:
202 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
204 1 i + 20 j + (-2) m + 25
206 Something like "i * n" or "n * m" is not allowed. */
209 graphite_can_represent_scev (tree scev
)
211 if (chrec_contains_undetermined (scev
))
214 /* We disable the handling of pointer types, because it’s currently not
215 supported by Graphite with the ISL AST generator. SSA_NAME nodes are
216 the only nodes, which are disabled in case they are pointers to object
217 types, but this can be changed. */
219 if (POINTER_TYPE_P (TREE_TYPE (scev
)) && TREE_CODE (scev
) == SSA_NAME
)
222 switch (TREE_CODE (scev
))
227 case NON_LVALUE_EXPR
:
228 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0));
231 case POINTER_PLUS_EXPR
:
233 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
234 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
237 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
238 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
239 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
240 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
241 && graphite_can_represent_init (scev
)
242 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
243 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
245 case POLYNOMIAL_CHREC
:
246 /* Check for constant strides. With a non constant stride of
247 'n' we would have a value of 'iv * n'. Also check that the
248 initial value can represented: for example 'n * m' cannot be
250 if (!evolution_function_right_is_integer_cst (scev
)
251 || !graphite_can_represent_init (scev
))
253 return graphite_can_represent_scev (CHREC_LEFT (scev
));
259 /* Only affine functions can be represented. */
260 if (tree_contains_chrecs (scev
, NULL
)
261 || !scev_is_linear_expression (scev
))
268 /* Return true when EXPR can be represented in the polyhedral model.
270 This means an expression can be represented, if it is linear with
271 respect to the loops and the strides are non parametric.
272 LOOP is the place where the expr will be evaluated. SCOP_ENTRY defines the
273 entry of the region we analyse. */
276 graphite_can_represent_expr (basic_block scop_entry
, loop_p loop
,
279 tree scev
= analyze_scalar_evolution (loop
, expr
);
281 scev
= instantiate_scev (scop_entry
, loop
, scev
);
283 return graphite_can_represent_scev (scev
);
286 /* Return true if the data references of STMT can be represented by
290 stmt_has_simple_data_refs_p (loop_p outermost_loop ATTRIBUTE_UNUSED
,
296 vec
<data_reference_p
> drs
= vNULL
;
299 for (outer
= loop_containing_stmt (stmt
); outer
; outer
= loop_outer (outer
))
301 graphite_find_data_references_in_stmt (outer
,
302 loop_containing_stmt (stmt
),
305 FOR_EACH_VEC_ELT (drs
, j
, dr
)
307 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
308 tree ref
= DR_REF (dr
);
310 for (int i
= nb_subscripts
- 1; i
>= 0; i
--)
312 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
))
313 || (TREE_CODE (ref
) != ARRAY_REF
314 && TREE_CODE (ref
) != MEM_REF
315 && TREE_CODE (ref
) != COMPONENT_REF
))
317 free_data_refs (drs
);
321 ref
= TREE_OPERAND (ref
, 0);
325 free_data_refs (drs
);
329 free_data_refs (drs
);
333 /* Return true only when STMT is simple enough for being handled by
334 Graphite. This depends on SCOP_ENTRY, as the parameters are
335 initialized relatively to this basic block, the linear functions
336 are initialized to OUTERMOST_LOOP and BB is the place where we try
337 to evaluate the STMT. */
340 stmt_simple_for_scop_p (basic_block scop_entry
, loop_p outermost_loop
,
341 gimple
*stmt
, basic_block bb
)
343 loop_p loop
= bb
->loop_father
;
345 gcc_assert (scop_entry
);
347 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
348 Calls have side-effects, except those to const or pure
350 if (gimple_has_volatile_ops (stmt
)
351 || (gimple_code (stmt
) == GIMPLE_CALL
352 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
353 || (gimple_code (stmt
) == GIMPLE_ASM
))
355 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
357 fprintf (dump_file
, "[scop-detection-fail] ");
358 fprintf (dump_file
, "Graphite cannot handle this stmt:\n");
359 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
);
365 if (is_gimple_debug (stmt
))
368 if (!stmt_has_simple_data_refs_p (outermost_loop
, stmt
))
370 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
372 fprintf (dump_file
, "[scop-detection-fail] ");
373 fprintf (dump_file
, "Graphite cannot handle data-refs in stmt:\n");
374 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
);
380 switch (gimple_code (stmt
))
387 /* We can handle all binary comparisons. Inequalities are
388 also supported as they can be represented with union of
390 enum tree_code code
= gimple_cond_code (stmt
);
391 if (!(code
== LT_EXPR
398 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
400 fprintf (dump_file
, "[scop-detection-fail] ");
401 fprintf (dump_file
, "Graphite cannot handle cond stmt:\n");
402 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
);
408 for (unsigned i
= 0; i
< 2; ++i
)
410 tree op
= gimple_op (stmt
, i
);
411 if (!graphite_can_represent_expr (scop_entry
, loop
, op
)
412 /* We can only constrain on integer type. */
413 || (TREE_CODE (TREE_TYPE (op
)) != INTEGER_TYPE
))
415 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
417 fprintf (dump_file
, "[scop-detection-fail] ");
418 fprintf (dump_file
, "Graphite cannot represent stmt:\n");
419 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
);
434 /* These nodes cut a new scope. */
435 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
437 fprintf (dump_file
, "[scop-detection-fail] ");
438 fprintf (dump_file
, "Gimple stmt not handled in Graphite:\n");
439 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
);
447 /* Returns the statement of BB that contains a harmful operation: that
448 can be a function call with side effects, the induction variables
449 are not linear with respect to SCOP_ENTRY, etc. The current open
450 scop should end before this statement. The evaluation is limited using
451 OUTERMOST_LOOP as outermost loop that may change. */
454 harmful_stmt_in_bb (basic_block scop_entry
, loop_p outer_loop
, basic_block bb
)
456 gimple_stmt_iterator gsi
;
458 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
459 if (!stmt_simple_for_scop_p (scop_entry
, outer_loop
, gsi_stmt (gsi
), bb
))
460 return gsi_stmt (gsi
);
465 /* Return true if LOOP can be represented in the polyhedral
466 representation. This is evaluated taking SCOP_ENTRY and
467 OUTERMOST_LOOP in mind. */
470 graphite_can_represent_loop (basic_block scop_entry
, loop_p loop
)
473 struct tree_niter_desc niter_desc
;
475 if (!loop_nest_has_data_refs (loop
))
477 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
479 fprintf (dump_file
, "[scop-detection-fail] ");
480 fprintf (dump_file
, "Loop %d does not have any data reference.\n",
486 /* FIXME: For the moment, graphite cannot be used on loops that
487 iterate using induction variables that wrap. */
489 return number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
490 && niter_desc
.control
.no_overflow
491 && (niter
= number_of_latch_executions (loop
))
492 && !chrec_contains_undetermined (niter
)
493 && graphite_can_represent_expr (scop_entry
, loop
, niter
);
496 /* Store information needed by scopdet_* functions. */
500 /* Exit of the open scop would stop if the current BB is harmful. */
503 /* Where the next scop would start if the current BB is harmful. */
506 /* The bb or one of its children contains open loop exits. That means
507 loop exit nodes that are not surrounded by a loop dominated by bb. */
510 /* The bb or one of its children contains only structures we can handle. */
514 static struct scopdet_info
build_scops_1 (basic_block
, loop_p
,
515 vec
<sd_region
> *, loop_p
);
517 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
518 to SCOPS. TYPE is the gbb_type of BB. */
520 static struct scopdet_info
521 scopdet_basic_block_info (basic_block bb
, loop_p outermost_loop
,
522 vec
<sd_region
> *scops
, gbb_type type
)
524 loop_p loop
= bb
->loop_father
;
525 struct scopdet_info result
;
528 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
529 basic_block entry_block
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
530 stmt
= harmful_stmt_in_bb (entry_block
, outermost_loop
, bb
);
531 result
.difficult
= (stmt
!= NULL
);
538 result
.exits
= false;
540 /* Mark bbs terminating a SESE region difficult, if they start
541 a condition or if the block it exits to cannot be split
542 with make_forwarder_block. */
543 if (!single_succ_p (bb
)
544 || bb_has_abnormal_pred (single_succ (bb
)))
546 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
548 fprintf (dump_file
, "[scop-detection-fail] ");
549 fprintf (dump_file
, "BB %d cannot be part of a scop.\n",
553 result
.difficult
= true;
556 result
.exit
= single_succ (bb
);
561 result
.next
= single_succ (bb
);
562 result
.exits
= false;
563 result
.exit
= single_succ (bb
);
566 case GBB_LOOP_SING_EXIT_HEADER
:
568 auto_vec
<sd_region
, 3> regions
;
569 struct scopdet_info sinfo
;
570 edge exit_e
= single_exit (loop
);
572 sinfo
= build_scops_1 (bb
, outermost_loop
, ®ions
, loop
);
574 if (!graphite_can_represent_loop (entry_block
, loop
))
576 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
578 fprintf (dump_file
, "[scop-detection-fail] ");
579 fprintf (dump_file
, "Graphite cannot represent loop %d.\n",
582 result
.difficult
= true;
585 result
.difficult
|= sinfo
.difficult
;
587 /* Try again with another loop level. */
589 && loop_depth (outermost_loop
) + 1 == loop_depth (loop
))
591 outermost_loop
= loop
;
596 sinfo
= scopdet_basic_block_info (bb
, outermost_loop
, scops
, type
);
599 result
.difficult
= true;
602 move_sd_regions (®ions
, scops
);
606 open_scop
.entry
= bb
;
607 open_scop
.exit
= exit_e
->dest
;
608 scops
->safe_push (open_scop
);
614 result
.exit
= exit_e
->dest
;
615 result
.next
= exit_e
->dest
;
617 /* If we do not dominate result.next, remove it. It's either
618 the exit block, or another bb dominates it and will
619 call the scop detection for this bb. */
620 if (!dominated_by_p (CDI_DOMINATORS
, result
.next
, bb
))
623 if (exit_e
->src
->loop_father
!= loop
)
626 result
.exits
= false;
628 if (result
.difficult
)
629 move_sd_regions (®ions
, scops
);
637 case GBB_LOOP_MULT_EXIT_HEADER
:
639 /* XXX: For now we just do not join loops with multiple exits. If the
640 exits lead to the same bb it may be possible to join the loop. */
641 auto_vec
<sd_region
, 3> regions
;
642 vec
<edge
> exits
= get_loop_exit_edges (loop
);
645 build_scops_1 (bb
, loop
, ®ions
, loop
);
647 /* Scan the code dominated by this loop. This means all bbs, that are
648 are dominated by a bb in this loop, but are not part of this loop.
651 - The loop exit destination is dominated by the exit sources.
653 TODO: We miss here the more complex cases:
654 - The exit destinations are dominated by another bb inside
656 - The loop dominates bbs, that are not exit destinations. */
657 FOR_EACH_VEC_ELT (exits
, i
, e
)
658 if (e
->src
->loop_father
== loop
659 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
))
661 if (loop_outer (outermost_loop
))
662 outermost_loop
= loop_outer (outermost_loop
);
664 /* Pass loop_outer to recognize e->dest as loop header in
666 if (e
->dest
->loop_father
->header
== e
->dest
)
667 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
668 loop_outer (e
->dest
->loop_father
));
670 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
671 e
->dest
->loop_father
);
676 result
.difficult
= true;
677 result
.exits
= false;
678 move_sd_regions (®ions
, scops
);
682 case GBB_COND_HEADER
:
684 auto_vec
<sd_region
, 3> regions
;
685 struct scopdet_info sinfo
;
686 vec
<basic_block
> dominated
;
689 basic_block last_exit
= NULL
;
691 result
.exits
= false;
693 /* First check the successors of BB, and check if it is
694 possible to join the different branches. */
695 FOR_EACH_VEC_SAFE_ELT (bb
->succs
, i
, e
)
697 /* Ignore loop exits. They will be handled after the loop
699 if (loop_exits_to_bb_p (loop
, e
->dest
))
705 /* Do not follow edges that lead to the end of the
706 conditions block. For example, in
716 the edge from 0 => 6. Only check if all paths lead to
719 if (!single_pred_p (e
->dest
))
721 /* Check, if edge leads directly to the end of this
726 if (e
->dest
!= last_exit
)
727 result
.difficult
= true;
732 if (!dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
734 result
.difficult
= true;
738 sinfo
= build_scops_1 (e
->dest
, outermost_loop
, ®ions
, loop
);
740 result
.exits
|= sinfo
.exits
;
741 result
.difficult
|= sinfo
.difficult
;
743 /* Checks, if all branches end at the same point.
744 If that is true, the condition stays joinable.
745 Have a look at the example above. */
749 last_exit
= sinfo
.exit
;
751 if (sinfo
.exit
!= last_exit
)
752 result
.difficult
= true;
755 result
.difficult
= true;
759 result
.difficult
= true;
761 /* Join the branches of the condition if possible. */
762 if (!result
.exits
&& !result
.difficult
)
764 /* Only return a next pointer if we dominate this pointer.
765 Otherwise it will be handled by the bb dominating it. */
766 if (dominated_by_p (CDI_DOMINATORS
, last_exit
, bb
)
768 result
.next
= last_exit
;
772 result
.exit
= last_exit
;
778 /* Scan remaining bbs dominated by BB. */
779 dominated
= get_dominated_by (CDI_DOMINATORS
, bb
);
781 FOR_EACH_VEC_ELT (dominated
, i
, dom_bb
)
783 /* Ignore loop exits: they will be handled after the loop body. */
784 if (loop_depth (find_common_loop (loop
, dom_bb
->loop_father
))
791 /* Ignore the bbs processed above. */
792 if (single_pred_p (dom_bb
) && single_pred (dom_bb
) == bb
)
795 if (loop_depth (loop
) > loop_depth (dom_bb
->loop_father
))
796 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
,
799 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
, loop
);
801 result
.exits
|= sinfo
.exits
;
802 result
.difficult
= true;
806 dominated
.release ();
809 move_sd_regions (®ions
, scops
);
821 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
822 SCOPS. The analyse if a sd_region can be handled is based on the value
823 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
824 is the loop in which CURRENT is handled.
826 TODO: These functions got a little bit big. They definitely should be cleaned
829 static struct scopdet_info
830 build_scops_1 (basic_block current
, loop_p outermost_loop
,
831 vec
<sd_region
> *scops
, loop_p loop
)
833 bool in_scop
= false;
835 struct scopdet_info sinfo
;
837 /* Initialize result. */
838 struct scopdet_info result
;
839 result
.exits
= false;
840 result
.difficult
= false;
843 open_scop
.entry
= NULL
;
844 open_scop
.exit
= NULL
;
847 /* Loop over the dominance tree. If we meet a difficult bb, close
848 the current SCoP. Loop and condition header start a new layer,
849 and can only be added if all bbs in deeper layers are simple. */
850 while (current
!= NULL
)
852 sinfo
= scopdet_basic_block_info (current
, outermost_loop
, scops
,
853 get_bb_type (current
, loop
));
855 if (!in_scop
&& !(sinfo
.exits
|| sinfo
.difficult
))
857 open_scop
.entry
= current
;
858 open_scop
.exit
= NULL
;
861 else if (in_scop
&& (sinfo
.exits
|| sinfo
.difficult
))
863 open_scop
.exit
= current
;
864 scops
->safe_push (open_scop
);
868 result
.difficult
|= sinfo
.difficult
;
869 result
.exits
|= sinfo
.exits
;
871 current
= sinfo
.next
;
874 /* Try to close open_scop, if we are still in an open SCoP. */
877 open_scop
.exit
= sinfo
.exit
;
878 gcc_assert (open_scop
.exit
);
879 if (open_scop
.entry
!= open_scop
.exit
)
880 scops
->safe_push (open_scop
);
883 sinfo
.difficult
= true;
889 result
.exit
= sinfo
.exit
;
893 /* Checks if a bb is contained in REGION. */
896 bb_in_sd_region (basic_block bb
, sd_region
*region
)
898 return bb_in_region (bb
, region
->entry
, region
->exit
);
901 /* Returns the single entry edge of REGION, if it does not exits NULL. */
904 find_single_entry_edge (sd_region
*region
)
910 FOR_EACH_EDGE (e
, ei
, region
->entry
->preds
)
911 if (!bb_in_sd_region (e
->src
, region
))
926 /* Returns the single exit edge of REGION, if it does not exits NULL. */
929 find_single_exit_edge (sd_region
*region
)
935 FOR_EACH_EDGE (e
, ei
, region
->exit
->preds
)
936 if (bb_in_sd_region (e
->src
, region
))
951 /* Create a single entry edge for REGION. */
954 create_single_entry_edge (sd_region
*region
)
956 if (find_single_entry_edge (region
))
959 /* There are multiple predecessors for bb_3
972 There are two edges (1->3, 2->3), that point from outside into the region,
973 and another one (5->3), a loop latch, lead to bb_3.
981 | |\ (3.0 -> 3.1) = single entry edge
990 If the loop is part of the SCoP, we have to redirect the loop latches.
996 | | (3.0 -> 3.1) = entry edge
1005 if (region
->entry
->loop_father
->header
!= region
->entry
1006 || dominated_by_p (CDI_DOMINATORS
,
1007 loop_latch_edge (region
->entry
->loop_father
)->src
,
1010 edge forwarder
= split_block_after_labels (region
->entry
);
1011 region
->entry
= forwarder
->dest
;
1014 /* This case is never executed, as the loop headers seem always to have a
1015 single edge pointing from outside into the loop. */
1018 gcc_checking_assert (find_single_entry_edge (region
));
1021 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
1024 sd_region_without_exit (edge e
)
1026 sd_region
*r
= (sd_region
*) e
->aux
;
1029 return r
->exit
== NULL
;
1034 /* Create a single exit edge for REGION. */
1037 create_single_exit_edge (sd_region
*region
)
1041 edge forwarder
= NULL
;
1044 /* We create a forwarder bb (5) for all edges leaving this region
1045 (3->5, 4->5). All other edges leading to the same bb, are moved
1046 to a new bb (6). If these edges where part of another region (2->5)
1047 we update the region->exit pointer, of this region.
1049 To identify which edge belongs to which region we depend on the e->aux
1050 pointer in every edge. It points to the region of the edge or to NULL,
1051 if the edge is not part of any region.
1053 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
1054 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
1059 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
1060 | | \/ 3->5 no region, 4->5 no region,
1062 \| / 5->6 region->exit = 6
1065 Now there is only a single exit edge (5->6). */
1066 exit
= region
->exit
;
1067 region
->exit
= NULL
;
1068 forwarder
= make_forwarder_block (exit
, &sd_region_without_exit
, NULL
);
1070 /* Unmark the edges, that are no longer exit edges. */
1071 FOR_EACH_EDGE (e
, ei
, forwarder
->src
->preds
)
1075 /* Mark the new exit edge. */
1076 single_succ_edge (forwarder
->src
)->aux
= region
;
1078 /* Update the exit bb of all regions, where exit edges lead to
1080 FOR_EACH_EDGE (e
, ei
, forwarder
->dest
->preds
)
1082 ((sd_region
*) e
->aux
)->exit
= forwarder
->dest
;
1084 gcc_checking_assert (find_single_exit_edge (region
));
1087 /* Unmark the exit edges of all REGIONS.
1088 See comment in "create_single_exit_edge". */
1091 unmark_exit_edges (vec
<sd_region
> regions
)
1098 FOR_EACH_VEC_ELT (regions
, i
, s
)
1099 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1104 /* Mark the exit edges of all REGIONS.
1105 See comment in "create_single_exit_edge". */
1108 mark_exit_edges (vec
<sd_region
> regions
)
1115 FOR_EACH_VEC_ELT (regions
, i
, s
)
1116 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1117 if (bb_in_sd_region (e
->src
, s
))
1121 /* Create for all scop regions a single entry and a single exit edge. */
1124 create_sese_edges (vec
<sd_region
> regions
)
1129 FOR_EACH_VEC_ELT (regions
, i
, s
)
1130 create_single_entry_edge (s
);
1132 mark_exit_edges (regions
);
1134 FOR_EACH_VEC_ELT (regions
, i
, s
)
1135 /* Don't handle multiple edges exiting the function. */
1136 if (!find_single_exit_edge (s
)
1137 && s
->exit
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1138 create_single_exit_edge (s
);
1140 unmark_exit_edges (regions
);
1142 calculate_dominance_info (CDI_DOMINATORS
);
1143 fix_loop_structure (NULL
);
1145 #ifdef ENABLE_CHECKING
1146 verify_loop_structure ();
1147 verify_ssa (false, true);
1151 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1154 build_graphite_scops (vec
<sd_region
> regions
,
1160 FOR_EACH_VEC_ELT (regions
, i
, s
)
1162 edge entry
= find_single_entry_edge (s
);
1163 edge exit
= find_single_exit_edge (s
);
1169 sese sese_reg
= new_sese (entry
, exit
);
1170 scop
= new_scop (sese_reg
);
1172 build_sese_loop_nests (sese_reg
);
1174 /* Scops with one or no loops are not interesting. */
1175 if (SESE_LOOP_NEST (sese_reg
).length () > 1)
1176 scops
->safe_push (scop
);
1177 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1178 fprintf (dump_file
, "Discarded scop: %d loops\n",
1179 SESE_LOOP_NEST (sese_reg
).length ());
1181 /* Are there overlapping SCoPs? */
1182 #ifdef ENABLE_CHECKING
1187 FOR_EACH_VEC_ELT (regions
, j
, s2
)
1189 gcc_assert (!bb_in_sd_region (s
->entry
, s2
));
1195 /* Returns true when P1 and P2 are close phis with the same
1199 same_close_phi_node (gphi
*p1
, gphi
*p2
)
1201 return operand_equal_p (gimple_phi_arg_def (p1
, 0),
1202 gimple_phi_arg_def (p2
, 0), 0);
1205 /* Remove the close phi node at GSI and replace its rhs with the rhs
1209 remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
)
1212 use_operand_p use_p
;
1213 imm_use_iterator imm_iter
;
1214 tree res
= gimple_phi_result (phi
);
1215 tree def
= gimple_phi_result (gsi
->phi ());
1217 gcc_assert (same_close_phi_node (phi
, gsi
->phi ()));
1219 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1221 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1222 SET_USE (use_p
, res
);
1224 update_stmt (use_stmt
);
1226 /* It is possible that we just created a duplicate close-phi
1227 for an already-processed containing loop. Check for this
1228 case and clean it up. */
1229 if (gimple_code (use_stmt
) == GIMPLE_PHI
1230 && gimple_phi_num_args (use_stmt
) == 1)
1231 make_close_phi_nodes_unique (gimple_bb (use_stmt
));
1234 remove_phi_node (gsi
, true);
1237 /* Removes all the close phi duplicates from BB. */
1240 make_close_phi_nodes_unique (basic_block bb
)
1244 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1246 gphi_iterator gsi
= psi
;
1247 gphi
*phi
= psi
.phi ();
1249 /* At this point, PHI should be a close phi in normal form. */
1250 gcc_assert (gimple_phi_num_args (phi
) == 1);
1252 /* Iterate over the next phis and remove duplicates. */
1254 while (!gsi_end_p (gsi
))
1255 if (same_close_phi_node (phi
, gsi
.phi ()))
1256 remove_duplicate_close_phi (phi
, &gsi
);
1262 /* Transforms LOOP to the canonical loop closed SSA form. */
1265 canonicalize_loop_closed_ssa (loop_p loop
)
1267 edge e
= single_exit (loop
);
1270 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
1275 if (single_pred_p (bb
))
1277 e
= split_block_after_labels (bb
);
1278 make_close_phi_nodes_unique (e
->src
);
1283 basic_block close
= split_edge (e
);
1285 e
= single_succ_edge (close
);
1287 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1289 gphi
*phi
= psi
.phi ();
1292 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1293 if (gimple_phi_arg_edge (phi
, i
) == e
)
1295 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
1296 use_operand_p use_p
;
1299 if (TREE_CODE (arg
) != SSA_NAME
)
1302 close_phi
= create_phi_node (NULL_TREE
, close
);
1303 res
= create_new_def_for (arg
, close_phi
,
1304 gimple_phi_result_ptr (close_phi
));
1305 add_phi_arg (close_phi
, arg
,
1306 gimple_phi_arg_edge (close_phi
, 0),
1308 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
1309 replace_exp (use_p
, res
);
1314 make_close_phi_nodes_unique (close
);
1317 /* The code above does not properly handle changes in the post dominance
1318 information (yet). */
1319 free_dominance_info (CDI_POST_DOMINATORS
);
1322 /* Converts the current loop closed SSA form to a canonical form
1323 expected by the Graphite code generation.
1325 The loop closed SSA form has the following invariant: a variable
1326 defined in a loop that is used outside the loop appears only in the
1327 phi nodes in the destination of the loop exit. These phi nodes are
1328 called close phi nodes.
1330 The canonical loop closed SSA form contains the extra invariants:
1332 - when the loop contains only one exit, the close phi nodes contain
1333 only one argument. That implies that the basic block that contains
1334 the close phi nodes has only one predecessor, that is a basic block
1337 - the basic block containing the close phi nodes does not contain
1340 - there exist only one phi node per definition in the loop.
1344 canonicalize_loop_closed_ssa_form (void)
1348 #ifdef ENABLE_CHECKING
1349 verify_loop_closed_ssa (true);
1352 FOR_EACH_LOOP (loop
, 0)
1353 canonicalize_loop_closed_ssa (loop
);
1355 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1356 update_ssa (TODO_update_ssa
);
1358 #ifdef ENABLE_CHECKING
1359 verify_loop_closed_ssa (true);
1363 /* Find Static Control Parts (SCoP) in the current function and pushes
1367 build_scops (vec
<scop_p
> *scops
)
1369 struct loop
*loop
= current_loops
->tree_root
;
1370 auto_vec
<sd_region
, 3> regions
;
1372 canonicalize_loop_closed_ssa_form ();
1373 build_scops_1 (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)),
1374 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->loop_father
,
1376 create_sese_edges (regions
);
1377 build_graphite_scops (regions
, scops
);
1381 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1382 fprintf (dump_file
, "\nnumber of SCoPs: %d\n",
1383 scops
? scops
->length () : 0);
1386 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1387 different colors. If there are not enough colors, paint the
1388 remaining SCoPs in gray.
1391 - "*" after the node number denotes the entry of a SCoP,
1392 - "#" after the node number denotes the exit of a SCoP,
1393 - "()" around the node number denotes the entry or the
1394 exit nodes of the SCOP. These are not part of SCoP. */
1397 dot_all_scops_1 (FILE *file
, vec
<scop_p
> scops
)
1406 /* Disable debugging while printing graph. */
1407 int tmp_dump_flags
= dump_flags
;
1410 fprintf (file
, "digraph all {\n");
1412 FOR_ALL_BB_FN (bb
, cfun
)
1414 int part_of_scop
= false;
1416 /* Use HTML for every bb label. So we are able to print bbs
1417 which are part of two different SCoPs, with two different
1418 background colors. */
1419 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1421 fprintf (file
, "CELLSPACING=\"0\">\n");
1423 /* Select color for SCoP. */
1424 FOR_EACH_VEC_ELT (scops
, i
, scop
)
1426 sese region
= SCOP_REGION (scop
);
1427 if (bb_in_sese_p (bb
, region
)
1428 || (SESE_EXIT_BB (region
) == bb
)
1429 || (SESE_ENTRY_BB (region
) == bb
))
1442 case 3: /* purple */
1445 case 4: /* orange */
1448 case 5: /* yellow */
1488 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color
);
1490 if (!bb_in_sese_p (bb
, region
))
1491 fprintf (file
, " (");
1493 if (bb
== SESE_ENTRY_BB (region
)
1494 && bb
== SESE_EXIT_BB (region
))
1495 fprintf (file
, " %d*# ", bb
->index
);
1496 else if (bb
== SESE_ENTRY_BB (region
))
1497 fprintf (file
, " %d* ", bb
->index
);
1498 else if (bb
== SESE_EXIT_BB (region
))
1499 fprintf (file
, " %d# ", bb
->index
);
1501 fprintf (file
, " %d ", bb
->index
);
1503 if (!bb_in_sese_p (bb
,region
))
1504 fprintf (file
, ")");
1506 fprintf (file
, "</TD></TR>\n");
1507 part_of_scop
= true;
1513 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1514 fprintf (file
, " %d </TD></TR>\n", bb
->index
);
1516 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1519 FOR_ALL_BB_FN (bb
, cfun
)
1521 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1522 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
1525 fputs ("}\n\n", file
);
1527 /* Enable debugging again. */
1528 dump_flags
= tmp_dump_flags
;
1531 /* Display all SCoPs using dotty. */
1534 dot_all_scops (vec
<scop_p
> scops
)
1536 /* When debugging, enable the following code. This cannot be used
1537 in production compilers because it calls "system". */
1540 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1541 gcc_assert (stream
);
1543 dot_all_scops_1 (stream
, scops
);
1546 x
= system ("dotty /tmp/allscops.dot &");
1548 dot_all_scops_1 (stderr
, scops
);
1552 /* Display all SCoPs using dotty. */
1555 dot_scop (scop_p scop
)
1557 auto_vec
<scop_p
, 1> scops
;
1560 scops
.safe_push (scop
);
1562 /* When debugging, enable the following code. This cannot be used
1563 in production compilers because it calls "system". */
1567 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1568 gcc_assert (stream
);
1570 dot_all_scops_1 (stream
, scops
);
1572 x
= system ("dotty /tmp/allscops.dot &");
1575 dot_all_scops_1 (stderr
, scops
);
1579 #endif /* HAVE_isl */