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"
42 #include "fold-const.h"
43 #include "gimple-iterator.h"
45 #include "tree-ssa-loop-manip.h"
46 #include "tree-ssa-loop-niter.h"
47 #include "tree-ssa-loop.h"
48 #include "tree-into-ssa.h"
51 #include "tree-data-ref.h"
52 #include "tree-scalar-evolution.h"
53 #include "tree-pass.h"
54 #include "graphite-poly.h"
55 #include "tree-ssa-propagate.h"
56 #include "graphite-scop-detection.h"
57 #include "gimple-pretty-print.h"
66 set_dump_file (FILE *f
)
72 friend debug_printer
&
73 operator<< (debug_printer
&output
, int i
)
75 fprintf (output
.dump_file
, "%d", i
);
78 friend debug_printer
&
79 operator<< (debug_printer
&output
, const char *s
)
81 fprintf (output
.dump_file
, "%s", s
);
86 #define DEBUG_PRINT(args) do \
88 if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \
92 /* Return true if BB is empty, contains only DEBUG_INSNs. */
95 trivially_empty_bb_p (basic_block bb
)
97 gimple_stmt_iterator gsi
;
99 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
100 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_DEBUG
)
106 /* Returns true when P1 and P2 are close phis with the same
110 same_close_phi_node (gphi
*p1
, gphi
*p2
)
112 return operand_equal_p (gimple_phi_arg_def (p1
, 0),
113 gimple_phi_arg_def (p2
, 0), 0);
116 /* Compare the depth of two basic_block's P1 and P2. */
119 compare_bb_depths (const void *p1
, const void *p2
)
121 const_basic_block
const bb1
= *(const_basic_block
const *)p1
;
122 const_basic_block
const bb2
= *(const_basic_block
const *)p2
;
123 int d1
= loop_depth (bb1
->loop_father
);
124 int d2
= loop_depth (bb2
->loop_father
);
135 /* Sort the basic blocks from DOM such that the first are the ones at
136 a deepest loop level. */
139 graphite_sort_dominated_info (vec
<basic_block
> dom
)
141 dom
.qsort (compare_bb_depths
);
144 static void make_close_phi_nodes_unique (basic_block bb
);
146 /* Remove the close phi node at GSI and replace its rhs with the rhs
150 remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
)
154 imm_use_iterator imm_iter
;
155 tree res
= gimple_phi_result (phi
);
156 tree def
= gimple_phi_result (gsi
->phi ());
158 gcc_assert (same_close_phi_node (phi
, gsi
->phi ()));
160 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
162 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
163 SET_USE (use_p
, res
);
165 update_stmt (use_stmt
);
167 /* It is possible that we just created a duplicate close-phi
168 for an already-processed containing loop. Check for this
169 case and clean it up. */
170 if (gimple_code (use_stmt
) == GIMPLE_PHI
171 && gimple_phi_num_args (use_stmt
) == 1)
172 make_close_phi_nodes_unique (gimple_bb (use_stmt
));
175 remove_phi_node (gsi
, true);
178 /* Removes all the close phi duplicates from BB. */
181 make_close_phi_nodes_unique (basic_block bb
)
185 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
187 gphi_iterator gsi
= psi
;
188 gphi
*phi
= psi
.phi ();
190 /* At this point, PHI should be a close phi in normal form. */
191 gcc_assert (gimple_phi_num_args (phi
) == 1);
193 /* Iterate over the next phis and remove duplicates. */
195 while (!gsi_end_p (gsi
))
196 if (same_close_phi_node (phi
, gsi
.phi ()))
197 remove_duplicate_close_phi (phi
, &gsi
);
203 /* Transforms LOOP to the canonical loop closed SSA form. */
206 canonicalize_loop_closed_ssa (loop_p loop
)
208 edge e
= single_exit (loop
);
211 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
216 if (single_pred_p (bb
))
218 e
= split_block_after_labels (bb
);
219 DEBUG_PRINT (dp
<< "\nSplitting bb_" << bb
->index
);
220 make_close_phi_nodes_unique (e
->src
);
225 basic_block close
= split_edge (e
);
227 e
= single_succ_edge (close
);
228 DEBUG_PRINT (dp
<< "\nSplitting edge (" << e
->src
->index
<< ","
229 << e
->dest
->index
<< ")\n");
231 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
233 gphi
*phi
= psi
.phi ();
236 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
237 if (gimple_phi_arg_edge (phi
, i
) == e
)
239 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
243 if (TREE_CODE (arg
) != SSA_NAME
)
246 close_phi
= create_phi_node (NULL_TREE
, close
);
247 res
= create_new_def_for (arg
, close_phi
,
248 gimple_phi_result_ptr (close_phi
));
249 add_phi_arg (close_phi
, arg
,
250 gimple_phi_arg_edge (close_phi
, 0),
252 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
253 replace_exp (use_p
, res
);
258 make_close_phi_nodes_unique (close
);
261 /* The code above does not properly handle changes in the post dominance
262 information (yet). */
263 recompute_all_dominators ();
266 /* Converts the current loop closed SSA form to a canonical form
267 expected by the Graphite code generation.
269 The loop closed SSA form has the following invariant: a variable
270 defined in a loop that is used outside the loop appears only in the
271 phi nodes in the destination of the loop exit. These phi nodes are
272 called close phi nodes.
274 The canonical loop closed SSA form contains the extra invariants:
276 - when the loop contains only one exit, the close phi nodes contain
277 only one argument. That implies that the basic block that contains
278 the close phi nodes has only one predecessor, that is a basic block
281 - the basic block containing the close phi nodes does not contain
284 - there exist only one phi node per definition in the loop.
288 canonicalize_loop_closed_ssa_form (void)
292 #ifdef ENABLE_CHECKING
293 verify_loop_closed_ssa (true);
296 FOR_EACH_LOOP (loop
, 0)
297 canonicalize_loop_closed_ssa (loop
);
299 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
300 update_ssa (TODO_update_ssa
);
302 #ifdef ENABLE_CHECKING
303 verify_loop_closed_ssa (true);
307 /* Can all ivs be represented by a signed integer?
308 As ISL might generate negative values in its expressions, signed loop ivs
309 are required in the backend. */
312 loop_ivs_can_be_represented (loop_p loop
)
314 unsigned type_long_long
= TYPE_PRECISION (long_long_integer_type_node
);
315 for (gphi_iterator psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
);
318 gphi
*phi
= psi
.phi ();
319 tree res
= PHI_RESULT (phi
);
320 tree type
= TREE_TYPE (res
);
322 if (TYPE_UNSIGNED (type
) && TYPE_PRECISION (type
) >= type_long_long
)
329 /* Returns a COND_EXPR statement when BB has a single predecessor, the
330 edge between BB and its predecessor is not a loop exit edge, and
331 the last statement of the single predecessor is a COND_EXPR. */
334 single_pred_cond_non_loop_exit (basic_block bb
)
336 if (single_pred_p (bb
))
338 edge e
= single_pred_edge (bb
);
339 basic_block pred
= e
->src
;
342 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
345 stmt
= last_stmt (pred
);
347 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
348 return as_a
<gcond
*> (stmt
);
357 /* Build the maximal scop containing LOOPs and add it to SCOPS. */
362 scop_detection () : scops (vNULL
) {}
364 /* A marker for invalid sese_l. */
365 static sese_l invalid_sese
;
367 /* Return the SCOPS in this SCOP_DETECTION. */
375 /* Return an sese_l around the LOOP. */
377 sese_l
get_sese (loop_p loop
);
379 /* Return the closest dominator with a single entry edge. In case of a
380 back-loop the back-edge is not counted. */
382 static edge
get_nearest_dom_with_single_entry (basic_block dom
);
384 /* Return the closest post-dominator with a single exit edge. In case of a
385 back-loop the back-edge is not counted. */
387 static edge
get_nearest_pdom_with_single_exit (basic_block dom
);
389 /* Print S to FILE. */
391 static void print_sese (FILE *file
, sese_l s
);
393 /* Merge scops at same loop depth and returns the new sese.
394 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
396 sese_l
merge_sese (sese_l first
, sese_l second
) const;
398 /* Build scop outer->inner if possible. */
400 sese_l
build_scop_depth (sese_l s
, loop_p loop
);
402 /* If loop and loop->next are valid scops, try to merge them. */
404 sese_l
build_scop_breadth (sese_l s1
, loop_p loop
);
406 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
407 region of code that can be represented in the polyhedral model. SCOP
408 defines the region we analyse. */
410 bool loop_is_valid_scop (loop_p loop
, sese_l scop
) const;
412 /* Return true when BEGIN is the preheader edge of a loop with a single exit
415 static bool region_has_one_loop (sese_l s
);
417 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
419 void add_scop (sese_l s
);
421 /* Returns true if S1 subsumes/surrounds S2. */
422 static bool subsumes (sese_l s1
, sese_l s2
);
424 /* Remove a SCoP which is subsumed by S1. */
425 void remove_subscops (sese_l s1
);
427 /* Returns true if S1 intersects with S2. Since we already know that S1 does
428 not subsume S2 or vice-versa, we only check for entry bbs. */
430 static bool intersects (sese_l s1
, sese_l s2
);
432 /* Remove one of the scops when it intersects with any other. */
434 void remove_intersecting_scops (sese_l s1
);
436 /* Return true when the body of LOOP has statements that can be represented
439 bool loop_body_is_valid_scop (loop_p loop
, sese_l scop
) const;
441 /* Return true when BB contains a harmful operation for a scop: that
442 can be a function call with side effects, the induction variables
443 are not linear with respect to SCOP, etc. The current open
444 scop should end before this statement. */
446 bool harmful_stmt_in_bb (sese_l scop
, basic_block bb
) const;
448 /* Return true when a statement in SCOP cannot be represented by Graphite.
449 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
450 Limit the number of bbs between adjacent loops to
451 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
453 bool harmful_stmt_in_region (sese_l scop
) const;
455 /* Return true only when STMT is simple enough for being handled by Graphite.
456 This depends on SCOP, as the parameters are initialized relatively to
457 this basic block, the linear functions are initialized based on the
458 outermost loop containing STMT inside the SCOP. BB is the place where we
459 try to evaluate the STMT. */
461 bool stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
462 basic_block bb
) const;
464 /* Something like "n * m" is not allowed. */
466 static bool graphite_can_represent_init (tree e
);
468 /* Return true when SCEV can be represented in the polyhedral model.
470 An expression can be represented, if it can be expressed as an
471 affine expression. For loops (i, j) and parameters (m, n) all
472 affine expressions are of the form:
474 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
476 1 i + 20 j + (-2) m + 25
478 Something like "i * n" or "n * m" is not allowed. */
480 static bool graphite_can_represent_scev (tree scev
);
482 /* Return true when EXPR can be represented in the polyhedral model.
484 This means an expression can be represented, if it is linear with respect
485 to the loops and the strides are non parametric. LOOP is the place where
486 the expr will be evaluated. SCOP defines the region we analyse. */
488 static bool graphite_can_represent_expr (sese_l scop
, loop_p loop
,
491 /* Return true if the data references of STMT can be represented by Graphite.
492 We try to analyze the data references in a loop contained in the SCOP. */
494 static bool stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
);
496 /* Remove the close phi node at GSI and replace its rhs with the rhs
499 static void remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
);
501 /* Returns true when Graphite can represent LOOP in SCOP.
502 FIXME: For the moment, graphite cannot be used on loops that iterate using
503 induction variables that wrap. */
505 static bool can_represent_loop_1 (loop_p loop
, sese_l scop
);
507 /* Return true when all the loops within LOOP can be represented by
510 static bool can_represent_loop (loop_p loop
, sese_l scop
);
512 /* Generates a polyhedral black box only if the bb contains interesting
515 static gimple_poly_bb_p
try_generate_gimple_bb (scop_p scop
, basic_block bb
);
517 /* Returns true if all predecessors of BB, that are not dominated by BB, are
518 marked in MAP. The predecessors dominated by BB are loop latches and will
519 be handled after BB. */
521 static bool all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
);
523 /* Recursive helper function for build_scops_bbs. */
525 static void build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
);
527 /* Gather the basic blocks belonging to the SCOP. */
529 static void build_scop_bbs (scop_p scop
);
531 /* Returns the number of pbbs that are in loops contained in SCOP. */
533 static int nb_pbbs_in_loops (scop_p scop
);
535 static bool graphite_can_represent_stmt (sese_l
, gimple
*, basic_block
);
541 sese_l
scop_detection::invalid_sese (0);
543 /* Return an sese_l around the LOOP. */
546 scop_detection::get_sese (loop_p loop
)
551 if (!loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
))
553 edge scop_end
= single_exit (loop
);
556 edge scop_begin
= loop_preheader_edge (loop
);
557 sese_l
s (scop_begin
, scop_end
);
561 /* Return the closest dominator with a single entry edge. */
564 scop_detection::get_nearest_dom_with_single_entry (basic_block dom
)
568 /* If e1->src dominates e2->src then e1->src will also dominate dom. */
569 if (dom
->preds
->length () == 2)
571 edge e1
= (*dom
->preds
)[0];
572 edge e2
= (*dom
->preds
)[1];
573 if (dominated_by_p (CDI_DOMINATORS
, e2
->src
, e1
->src
))
575 if (dominated_by_p (CDI_DOMINATORS
, e1
->src
, e2
->src
))
579 while (dom
->preds
->length () != 1)
581 if (dom
->preds
->length () < 1)
583 dom
= get_immediate_dominator (CDI_DOMINATORS
, dom
);
587 return (*dom
->preds
)[0];
590 /* Return the closest post-dominator with a single exit edge. In case of a
591 back-loop the back-edge is not counted. */
594 scop_detection::get_nearest_pdom_with_single_exit (basic_block dom
)
598 if (dom
->succs
->length () == 2)
600 edge e1
= (*dom
->succs
)[0];
601 edge e2
= (*dom
->succs
)[1];
602 if (dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, e1
->dest
))
604 if (dominated_by_p (CDI_POST_DOMINATORS
, e1
->dest
, e2
->dest
))
608 while (dom
->succs
->length () != 1)
610 if (dom
->succs
->length () < 1)
612 dom
= get_immediate_dominator (CDI_POST_DOMINATORS
, dom
);
616 return (*dom
->succs
)[0];
619 /* Print S to FILE. */
622 scop_detection::print_sese (FILE *file
, sese_l s
)
624 fprintf (file
, "(entry_edge (bb_%d, bb_%d), exit_edge (bb_%d, bb_%d))\n",
625 s
.entry
->src
->index
, s
.entry
->dest
->index
,
626 s
.exit
->src
->index
, s
.exit
->dest
->index
);
629 /* Merge scops at same loop depth and returns the new sese.
630 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
633 scop_detection::merge_sese (sese_l first
, sese_l second
) const
635 /* In the trivial case first/second may be NULL. */
641 DEBUG_PRINT (dp
<< "[try-merging-sese] s1: "; print_sese (dump_file
, first
);
642 dp
<< "[try-merging-sese] s2: ";
643 print_sese (dump_file
, second
));
645 /* Assumption: Both the sese's should be at the same loop depth or one scop
646 should subsume the other like in case of nested loops. */
648 /* Find the common dominators for entry,
649 and common post-dominators for the exit. */
650 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
,
651 get_entry_bb (first
),
652 get_entry_bb (second
));
654 edge entry
= get_nearest_dom_with_single_entry (dom
);
658 basic_block pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
,
660 get_exit_bb (second
));
661 pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
, dom
, pdom
);
663 edge exit
= get_nearest_pdom_with_single_exit (pdom
);
667 sese_l
combined (entry
, exit
);
669 /* FIXME: We could iterate to find the dom which dominates pdom, and pdom
670 which post-dominates dom, until it stabilizes. Also, ENTRY->SRC and
671 EXIT->DEST should be in the same loop nest. */
672 if (!dominated_by_p (CDI_DOMINATORS
, pdom
, dom
)
673 || loop_depth (entry
->src
->loop_father
)
674 != loop_depth (exit
->dest
->loop_father
))
677 /* For now we just want to bail out when exit does not post-dominate entry.
678 TODO: We might just add a basic_block at the exit to make exit
679 post-dominate entry (the entire region). */
680 if (!dominated_by_p (CDI_POST_DOMINATORS
, get_entry_bb (combined
),
681 get_exit_bb (combined
))
682 || !dominated_by_p (CDI_DOMINATORS
, get_exit_bb (combined
),
683 get_entry_bb (combined
)))
685 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
689 /* FIXME: We should remove this piece of code once
690 canonicalize_loop_closed_ssa has been removed, because that function
691 adds a BB with single exit. */
692 if (!trivially_empty_bb_p (get_exit_bb (combined
)))
694 /* Find the first empty succ (with single exit) of combined.exit. */
695 basic_block imm_succ
= combined
.exit
->dest
;
696 if (single_succ_p (imm_succ
) && trivially_empty_bb_p (imm_succ
))
697 combined
.exit
= single_succ_edge (imm_succ
);
700 DEBUG_PRINT (dp
<< "\n[scop-detection-fail] Discarding SCoP because "
701 << "no single exit (empty succ) for sese exit";
702 print_sese (dump_file
, combined
));
707 /* Analyze all the BBs in new sese. */
708 if (harmful_stmt_in_region (combined
))
711 DEBUG_PRINT (dp
<< "[merged-sese] s1: "; print_sese (dump_file
, combined
));
716 /* Build scop outer->inner if possible. */
719 scop_detection::build_scop_depth (sese_l s
, loop_p loop
)
724 DEBUG_PRINT (dp
<< "\n[Depth loop_" << loop
->num
<< "]");
725 s
= build_scop_depth (s
, loop
->inner
);
727 sese_l s2
= merge_sese (s
, get_sese (loop
));
730 /* s might be a valid scop, so return it and start analyzing from the
732 build_scop_depth (invalid_sese
, loop
->next
);
736 if (!loop_is_valid_scop (loop
, s2
))
737 return build_scop_depth (invalid_sese
, loop
->next
);
739 return build_scop_breadth (s2
, loop
);
742 /* If loop and loop->next are valid scops, try to merge them. */
745 scop_detection::build_scop_breadth (sese_l s1
, loop_p loop
)
749 DEBUG_PRINT (dp
<< "\n[Breadth loop_" << loop
->num
<< "]");
753 sese_l s2
= build_scop_depth (invalid_sese
, l
->next
);
761 sese_l combined
= merge_sese (s1
, s2
);
773 /* Returns true when Graphite can represent LOOP in SCOP.
774 FIXME: For the moment, graphite cannot be used on loops that iterate using
775 induction variables that wrap. */
778 scop_detection::can_represent_loop_1 (loop_p loop
, sese_l scop
)
781 struct tree_niter_desc niter_desc
;
783 return single_exit (loop
)
784 && number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
785 && niter_desc
.control
.no_overflow
786 && (niter
= number_of_latch_executions (loop
))
787 && !chrec_contains_undetermined (niter
)
788 && graphite_can_represent_expr (scop
, loop
, niter
);
791 /* Return true when all the loops within LOOP can be represented by
795 scop_detection::can_represent_loop (loop_p loop
, sese_l scop
)
797 if (!can_represent_loop_1 (loop
, scop
))
799 if (loop
->inner
&& !can_represent_loop (loop
->inner
, scop
))
801 if (loop
->next
&& !can_represent_loop (loop
->next
, scop
))
807 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
808 region of code that can be represented in the polyhedral model. SCOP
809 defines the region we analyse. */
812 scop_detection::loop_is_valid_scop (loop_p loop
, sese_l scop
) const
817 if (!can_represent_loop (loop
, scop
))
819 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot represent loop_"
820 << loop
->num
<< "\n");
824 if (loop_body_is_valid_scop (loop
, scop
))
826 DEBUG_PRINT (dp
<< "[valid-scop] loop_" << loop
->num
827 << "is a valid scop.\n");
833 /* Return true when BEGIN is the preheader edge of a loop with a single exit
837 scop_detection::region_has_one_loop (sese_l s
)
839 edge begin
= s
.entry
;
841 /* Check for a single perfectly nested loop. */
842 if (begin
->dest
->loop_father
->inner
)
845 /* Otherwise, check whether we have adjacent loops. */
846 return begin
->dest
->loop_father
== end
->src
->loop_father
;
849 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
852 scop_detection::add_scop (sese_l s
)
856 /* Do not add scops with only one loop. */
857 if (region_has_one_loop (s
))
859 DEBUG_PRINT (dp
<< "\n[scop-detection-fail] Discarding one loop SCoP";
860 print_sese (dump_file
, s
));
864 if (get_exit_bb (s
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
866 DEBUG_PRINT (dp
<< "\n[scop-detection-fail] "
867 << "Discarding SCoP exiting to return";
868 print_sese (dump_file
, s
));
872 /* Remove all the scops which are subsumed by s. */
875 /* Replace this with split-intersecting scops. */
876 remove_intersecting_scops (s
);
879 DEBUG_PRINT (dp
<< "\nAdding SCoP "; print_sese (dump_file
, s
));
882 /* Return true when a statement in SCOP cannot be represented by Graphite.
883 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
884 Limit the number of bbs between adjacent loops to
885 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
888 scop_detection::harmful_stmt_in_region (sese_l scop
) const
890 basic_block exit_bb
= get_exit_bb (scop
);
891 basic_block entry_bb
= get_entry_bb (scop
);
893 DEBUG_PRINT (dp
<< "\n[checking-harmful-bbs] ";
894 print_sese (dump_file
, scop
));
895 gcc_assert (dominated_by_p (CDI_DOMINATORS
, exit_bb
, entry_bb
));
897 int depth
= bb_dom_dfs_in (CDI_DOMINATORS
, exit_bb
)
898 - bb_dom_dfs_in (CDI_DOMINATORS
, entry_bb
);
900 gcc_assert (depth
> 0);
903 = get_dominated_to_depth (CDI_DOMINATORS
, entry_bb
, depth
);
906 FOR_EACH_VEC_ELT (dom
, i
, bb
)
908 DEBUG_PRINT (dp
<< "\nVisiting bb_" << bb
->index
);
910 /* We don't want to analyze any bb outside sese. */
911 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb
, exit_bb
))
914 if (harmful_stmt_in_bb (scop
, bb
))
921 /* Returns true if S1 subsumes/surrounds S2. */
923 scop_detection::subsumes (sese_l s1
, sese_l s2
)
925 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
927 && dominated_by_p (CDI_POST_DOMINATORS
, s2
.exit
->dest
,
933 /* Remove a SCoP which is subsumed by S1. */
935 scop_detection::remove_subscops (sese_l s1
)
939 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
941 if (subsumes (s1
, s2
))
943 DEBUG_PRINT (dp
<< "\nRemoving sub-SCoP";
944 print_sese (dump_file
, s2
));
945 scops
.unordered_remove (j
);
950 /* Returns true if S1 intersects with S2. Since we already know that S1 does
951 not subsume S2 or vice-versa, we only check for entry bbs. */
954 scop_detection::intersects (sese_l s1
, sese_l s2
)
956 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
958 && !dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
961 if ((s1
.exit
== s2
.entry
) || (s2
.exit
== s1
.entry
))
967 /* Remove one of the scops when it intersects with any other. */
970 scop_detection::remove_intersecting_scops (sese_l s1
)
974 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
976 if (intersects (s1
, s2
))
978 DEBUG_PRINT (dp
<< "\nRemoving intersecting SCoP";
979 print_sese (dump_file
, s2
); dp
<< "Intersects with:";
980 print_sese (dump_file
, s1
));
981 scops
.unordered_remove (j
);
986 /* Something like "n * m" is not allowed. */
989 scop_detection::graphite_can_represent_init (tree e
)
991 switch (TREE_CODE (e
))
993 case POLYNOMIAL_CHREC
:
994 return graphite_can_represent_init (CHREC_LEFT (e
))
995 && graphite_can_represent_init (CHREC_RIGHT (e
));
998 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
999 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
1000 && tree_fits_shwi_p (TREE_OPERAND (e
, 1));
1002 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
1003 && tree_fits_shwi_p (TREE_OPERAND (e
, 0));
1006 case POINTER_PLUS_EXPR
:
1008 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
1009 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
1014 case NON_LVALUE_EXPR
:
1015 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
1024 /* Return true when SCEV can be represented in the polyhedral model.
1026 An expression can be represented, if it can be expressed as an
1027 affine expression. For loops (i, j) and parameters (m, n) all
1028 affine expressions are of the form:
1030 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
1032 1 i + 20 j + (-2) m + 25
1034 Something like "i * n" or "n * m" is not allowed. */
1037 scop_detection::graphite_can_represent_scev (tree scev
)
1039 if (chrec_contains_undetermined (scev
))
1042 /* We disable the handling of pointer types, because it’s currently not
1043 supported by Graphite with the ISL AST generator. SSA_NAME nodes are
1044 the only nodes, which are disabled in case they are pointers to object
1045 types, but this can be changed. */
1047 if (POINTER_TYPE_P (TREE_TYPE (scev
)) && TREE_CODE (scev
) == SSA_NAME
)
1050 switch (TREE_CODE (scev
))
1055 case NON_LVALUE_EXPR
:
1056 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0));
1059 case POINTER_PLUS_EXPR
:
1061 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1062 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1065 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
1066 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
1067 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
1068 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
1069 && graphite_can_represent_init (scev
)
1070 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1071 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1073 case POLYNOMIAL_CHREC
:
1074 /* Check for constant strides. With a non constant stride of
1075 'n' we would have a value of 'iv * n'. Also check that the
1076 initial value can represented: for example 'n * m' cannot be
1078 if (!evolution_function_right_is_integer_cst (scev
)
1079 || !graphite_can_represent_init (scev
))
1081 return graphite_can_represent_scev (CHREC_LEFT (scev
));
1087 /* Only affine functions can be represented. */
1088 if (tree_contains_chrecs (scev
, NULL
) || !scev_is_linear_expression (scev
))
1094 /* Return true when EXPR can be represented in the polyhedral model.
1096 This means an expression can be represented, if it is linear with respect to
1097 the loops and the strides are non parametric. LOOP is the place where the
1098 expr will be evaluated. SCOP defines the region we analyse. */
1101 scop_detection::graphite_can_represent_expr (sese_l scop
, loop_p loop
,
1104 tree scev
= scalar_evolution_in_region (scop
, loop
, expr
);
1105 return graphite_can_represent_scev (scev
);
1108 /* Return true if the data references of STMT can be represented by Graphite.
1109 We try to analyze the data references in a loop contained in the SCOP. */
1112 scop_detection::stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
)
1114 loop_p nest
= outermost_loop_in_sese (scop
, gimple_bb (stmt
));
1115 loop_p loop
= loop_containing_stmt (stmt
);
1116 vec
<data_reference_p
> drs
= vNULL
;
1118 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1121 data_reference_p dr
;
1122 FOR_EACH_VEC_ELT (drs
, j
, dr
)
1124 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1126 if (nb_subscripts
< 1)
1128 free_data_refs (drs
);
1132 tree ref
= DR_REF (dr
);
1134 for (int i
= nb_subscripts
- 1; i
>= 0; i
--)
1136 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
))
1137 || (TREE_CODE (ref
) != ARRAY_REF
&& TREE_CODE (ref
) != MEM_REF
1138 && TREE_CODE (ref
) != COMPONENT_REF
))
1140 free_data_refs (drs
);
1144 ref
= TREE_OPERAND (ref
, 0);
1148 free_data_refs (drs
);
1152 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1153 Calls have side-effects, except those to const or pure
1157 stmt_has_side_effects (gimple
*stmt
)
1159 if (gimple_has_volatile_ops (stmt
)
1160 || (gimple_code (stmt
) == GIMPLE_CALL
1161 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
1162 || (gimple_code (stmt
) == GIMPLE_ASM
))
1164 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1165 << "Statement has side-effects:\n";
1166 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1172 /* Returns true if STMT can be represented in polyhedral model. LABEL,
1173 simple COND stmts, pure calls, and assignments can be repesented. */
1176 scop_detection::graphite_can_represent_stmt (sese_l scop
, gimple
*stmt
,
1179 loop_p loop
= bb
->loop_father
;
1180 switch (gimple_code (stmt
))
1187 /* We can handle all binary comparisons. Inequalities are
1188 also supported as they can be represented with union of
1190 enum tree_code code
= gimple_cond_code (stmt
);
1191 if (!(code
== LT_EXPR
1196 || code
== NE_EXPR
))
1198 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1199 << "Graphite cannot handle cond stmt:\n";
1200 print_gimple_stmt (dump_file
, stmt
, 0,
1201 TDF_VOPS
| TDF_MEMSYMS
));
1205 for (unsigned i
= 0; i
< 2; ++i
)
1207 tree op
= gimple_op (stmt
, i
);
1208 if (!graphite_can_represent_expr (scop
, loop
, op
)
1209 /* We can only constrain on integer type. */
1210 || (TREE_CODE (TREE_TYPE (op
)) != INTEGER_TYPE
))
1212 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1213 << "Graphite cannot represent stmt:\n";
1214 print_gimple_stmt (dump_file
, stmt
, 0,
1215 TDF_VOPS
| TDF_MEMSYMS
));
1228 /* These nodes cut a new scope. */
1230 dp
<< "[scop-detection-fail] "
1231 << "Gimple stmt not handled in Graphite:\n";
1232 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1237 /* Return true only when STMT is simple enough for being handled by Graphite.
1238 This depends on SCOP, as the parameters are initialized relatively to
1239 this basic block, the linear functions are initialized based on the outermost
1240 loop containing STMT inside the SCOP. BB is the place where we try to
1241 evaluate the STMT. */
1244 scop_detection::stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
1245 basic_block bb
) const
1249 if (is_gimple_debug (stmt
))
1252 if (stmt_has_side_effects (stmt
))
1255 if (!stmt_has_simple_data_refs_p (scop
, stmt
))
1257 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1258 << "Graphite cannot handle data-refs in stmt:\n";
1259 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
););
1263 return graphite_can_represent_stmt (scop
, stmt
, bb
);
1266 /* Return true when BB contains a harmful operation for a scop: that
1267 can be a function call with side effects, the induction variables
1268 are not linear with respect to SCOP, etc. The current open
1269 scop should end before this statement. */
1272 scop_detection::harmful_stmt_in_bb (sese_l scop
, basic_block bb
) const
1274 gimple_stmt_iterator gsi
;
1276 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1277 if (!stmt_simple_for_scop_p (scop
, gsi_stmt (gsi
), bb
))
1283 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1284 different colors. If there are not enough colors, paint the
1285 remaining SCoPs in gray.
1288 - "*" after the node number denotes the entry of a SCoP,
1289 - "#" after the node number denotes the exit of a SCoP,
1290 - "()" around the node number denotes the entry or the
1291 exit nodes of the SCOP. These are not part of SCoP. */
1294 dot_all_scops_1 (FILE *file
, vec
<scop_p
> scops
)
1303 /* Disable debugging while printing graph. */
1304 int tmp_dump_flags
= dump_flags
;
1307 fprintf (file
, "digraph all {\n");
1309 FOR_ALL_BB_FN (bb
, cfun
)
1311 int part_of_scop
= false;
1313 /* Use HTML for every bb label. So we are able to print bbs
1314 which are part of two different SCoPs, with two different
1315 background colors. */
1316 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1318 fprintf (file
, "CELLSPACING=\"0\">\n");
1320 /* Select color for SCoP. */
1321 FOR_EACH_VEC_ELT (scops
, i
, scop
)
1323 sese_l region
= scop
->region
->region
;
1324 if (bb_in_sese_p (bb
, region
) || (region
.exit
->dest
== bb
)
1325 || (region
.entry
->dest
== bb
))
1338 case 3: /* purple */
1341 case 4: /* orange */
1344 case 5: /* yellow */
1384 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
1387 if (!bb_in_sese_p (bb
, region
))
1388 fprintf (file
, " (");
1390 if (bb
== region
.entry
->dest
&& bb
== region
.exit
->dest
)
1391 fprintf (file
, " %d*# ", bb
->index
);
1392 else if (bb
== region
.entry
->dest
)
1393 fprintf (file
, " %d* ", bb
->index
);
1394 else if (bb
== region
.exit
->dest
)
1395 fprintf (file
, " %d# ", bb
->index
);
1397 fprintf (file
, " %d ", bb
->index
);
1399 fprintf (file
, "{lp_%d}", bb
->loop_father
->num
);
1401 if (!bb_in_sese_p (bb
, region
))
1402 fprintf (file
, ")");
1404 fprintf (file
, "</TD></TR>\n");
1405 part_of_scop
= true;
1411 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1412 fprintf (file
, " %d {lp_%d} </TD></TR>\n", bb
->index
,
1413 bb
->loop_father
->num
);
1415 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1418 FOR_ALL_BB_FN (bb
, cfun
)
1420 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1421 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
1424 fputs ("}\n\n", file
);
1426 /* Enable debugging again. */
1427 dump_flags
= tmp_dump_flags
;
1430 /* Display all SCoPs using dotty. */
1433 dot_all_scops (vec
<scop_p
> scops
)
1435 /* When debugging, enable the following code. This cannot be used
1436 in production compilers because it calls "system". */
1439 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1440 gcc_assert (stream
);
1442 dot_all_scops_1 (stream
, scops
);
1445 x
= system ("dotty /tmp/allscops.dot &");
1447 dot_all_scops_1 (stderr
, scops
);
1451 /* Display all SCoPs using dotty. */
1454 dot_scop (scop_p scop
)
1456 auto_vec
<scop_p
, 1> scops
;
1459 scops
.safe_push (scop
);
1461 /* When debugging, enable the following code. This cannot be used
1462 in production compilers because it calls "system". */
1466 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1467 gcc_assert (stream
);
1469 dot_all_scops_1 (stream
, scops
);
1471 x
= system ("dotty /tmp/allscops.dot &");
1474 dot_all_scops_1 (stderr
, scops
);
1478 /* Return true when the body of LOOP has statements that can be represented as a
1482 scop_detection::loop_body_is_valid_scop (loop_p loop
, sese_l scop
) const
1484 if (!loop_ivs_can_be_represented (loop
))
1486 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
1487 << "IV cannot be represented.\n");
1491 if (!loop_nest_has_data_refs (loop
))
1493 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
1494 << "does not have any data reference.\n");
1498 basic_block
*bbs
= get_loop_body (loop
);
1499 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
1501 basic_block bb
= bbs
[i
];
1503 if (harmful_stmt_in_bb (scop
, bb
))
1513 if (!loop_body_is_valid_scop (loop
, scop
))
1522 /* Generates a polyhedral black box only if the bb contains interesting
1526 scop_detection::try_generate_gimple_bb (scop_p scop
, basic_block bb
)
1528 vec
<data_reference_p
> drs
;
1530 sese_l region
= scop
->region
->region
;
1531 loop_p nest
= outermost_loop_in_sese (region
, bb
);
1533 loop_p loop
= bb
->loop_father
;
1534 if (!loop_in_sese_p (loop
, region
))
1537 gimple_stmt_iterator gsi
;
1538 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1540 gimple
*stmt
= gsi_stmt (gsi
);
1541 if (is_gimple_debug (stmt
))
1544 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1547 return new_gimple_poly_bb (bb
, drs
);
1550 /* Returns true if all predecessors of BB, that are not dominated by BB, are
1551 marked in MAP. The predecessors dominated by BB are loop latches and will
1552 be handled after BB. */
1555 scop_detection::all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
1560 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1561 if (!bitmap_bit_p (map
, e
->src
->index
)
1562 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
1568 /* Recursive helper function for build_scops_bbs. */
1571 scop_detection::build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
1573 if (bitmap_bit_p (visited
, bb
->index
)
1574 || !bb_in_sese_p (bb
, scop
->region
->region
))
1577 poly_bb_p pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
1578 SCOP_BBS (scop
).safe_push (pbb
);
1579 bitmap_set_bit (visited
, bb
->index
);
1581 vec
<basic_block
> dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
1586 graphite_sort_dominated_info (dom
);
1588 while (!dom
.is_empty ())
1593 FOR_EACH_VEC_ELT (dom
, i
, dom_bb
)
1594 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
1596 build_scop_bbs_1 (scop
, visited
, dom_bb
);
1597 dom
.unordered_remove (i
);
1605 /* Gather the basic blocks belonging to the SCOP. */
1608 scop_detection::build_scop_bbs (scop_p scop
)
1610 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1611 sese_l region
= scop
->region
->region
;
1613 bitmap_clear (visited
);
1614 build_scop_bbs_1 (scop
, visited
, region
.entry
->dest
);
1615 sbitmap_free (visited
);
1618 /* Returns the number of pbbs that are in loops contained in SCOP. */
1621 scop_detection::nb_pbbs_in_loops (scop_p scop
)
1627 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1628 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), scop
->region
->region
))
1634 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
1635 Otherwise returns -1. */
1638 parameter_index_in_region_1 (tree name
, sese_info_p region
)
1643 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1645 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
1652 /* When the parameter NAME is in REGION, returns its index in
1653 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
1654 and returns the index of NAME. */
1657 parameter_index_in_region (tree name
, sese_info_p region
)
1661 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1663 /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
1664 if (TREE_CODE (TREE_TYPE (name
)) != INTEGER_TYPE
)
1667 if (!invariant_in_sese_p_rec (name
, region
->region
))
1670 i
= parameter_index_in_region_1 (name
, region
);
1674 gcc_assert (SESE_ADD_PARAMS (region
));
1676 i
= SESE_PARAMS (region
).length ();
1677 SESE_PARAMS (region
).safe_push (name
);
1681 /* In the context of sese S, scan the expression E and translate it to
1682 a linear expression C. When parsing a symbolic multiplication, K
1683 represents the constant multiplier of an expression containing
1687 scan_tree_for_params (sese_info_p s
, tree e
)
1689 if (e
== chrec_dont_know
)
1692 switch (TREE_CODE (e
))
1694 case POLYNOMIAL_CHREC
:
1695 scan_tree_for_params (s
, CHREC_LEFT (e
));
1699 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1700 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1702 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1706 case POINTER_PLUS_EXPR
:
1708 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1709 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1715 case NON_LVALUE_EXPR
:
1716 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1720 parameter_index_in_region (e
, s
);
1736 /* Find parameters with respect to REGION in BB. We are looking in memory
1737 access functions, conditions and loop bounds. */
1740 find_params_in_bb (sese_info_p region
, gimple_poly_bb_p gbb
)
1742 /* Find parameters in the access functions of data references. */
1744 data_reference_p dr
;
1745 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
1746 for (unsigned j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
1747 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
1749 /* Find parameters in conditional statements. */
1751 loop_p loop
= GBB_BB (gbb
)->loop_father
;
1752 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1754 tree lhs
= scalar_evolution_in_region (region
->region
, loop
,
1755 gimple_cond_lhs (stmt
));
1756 tree rhs
= scalar_evolution_in_region (region
->region
, loop
,
1757 gimple_cond_rhs (stmt
));
1759 scan_tree_for_params (region
, lhs
);
1760 scan_tree_for_params (region
, rhs
);
1764 /* Record the parameters used in the SCOP. A variable is a parameter
1765 in a scop if it does not vary during the execution of that scop. */
1768 find_scop_parameters (scop_p scop
)
1771 sese_info_p region
= scop
->region
;
1774 /* Find the parameters used in the loop bounds. */
1775 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1777 tree nb_iters
= number_of_latch_executions (loop
);
1779 if (!chrec_contains_symbols (nb_iters
))
1782 nb_iters
= scalar_evolution_in_region (region
->region
, loop
, nb_iters
);
1783 scan_tree_for_params (region
, nb_iters
);
1786 /* Find the parameters used in data accesses. */
1788 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1789 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1791 int nbp
= sese_nb_params (region
);
1792 scop_set_nb_params (scop
, nbp
);
1793 SESE_ADD_PARAMS (region
) = false;
1796 class sese_dom_walker
: public dom_walker
1799 sese_dom_walker (cdi_direction
, sese_l
);
1801 virtual void before_dom_children (basic_block
);
1802 virtual void after_dom_children (basic_block
);
1805 auto_vec
<gimple
*, 3> m_conditions
, m_cases
;
1809 sese_dom_walker::sese_dom_walker (cdi_direction direction
, sese_l region
)
1810 : dom_walker (direction
), m_region (region
)
1814 /* Call-back for dom_walk executed before visiting the dominated
1818 sese_dom_walker::before_dom_children (basic_block bb
)
1820 gimple_poly_bb_p gbb
;
1823 if (!bb_in_sese_p (bb
, m_region
))
1826 stmt
= single_pred_cond_non_loop_exit (bb
);
1830 edge e
= single_pred_edge (bb
);
1832 m_conditions
.safe_push (stmt
);
1834 if (e
->flags
& EDGE_TRUE_VALUE
)
1835 m_cases
.safe_push (stmt
);
1837 m_cases
.safe_push (NULL
);
1840 gbb
= gbb_from_bb (bb
);
1844 GBB_CONDITIONS (gbb
) = m_conditions
.copy ();
1845 GBB_CONDITION_CASES (gbb
) = m_cases
.copy ();
1849 /* Call-back for dom_walk executed after visiting the dominated
1853 sese_dom_walker::after_dom_children (basic_block bb
)
1855 if (!bb_in_sese_p (bb
, m_region
))
1858 if (single_pred_cond_non_loop_exit (bb
))
1860 m_conditions
.pop ();
1865 /* Find Static Control Parts (SCoP) in the current function and pushes
1869 build_scops (vec
<scop_p
> *scops
)
1872 dp
.set_dump_file (dump_file
);
1874 canonicalize_loop_closed_ssa_form ();
1877 sb
.build_scop_depth (scop_detection::invalid_sese
, current_loops
->tree_root
);
1879 /* Now create scops from the lightweight SESEs. */
1880 vec
<sese_l
> scops_l
= sb
.get_scops ();
1883 FOR_EACH_VEC_ELT (scops_l
, i
, s
)
1885 scop_p scop
= new_scop (s
.entry
, s
.exit
);
1887 sb
.build_scop_bbs (scop
);
1888 /* Do not optimize a scop containing only PBBs that do not belong
1890 if (sb
.nb_pbbs_in_loops (scop
) == 0)
1892 DEBUG_PRINT (dp
<< "[scop-detection-fail] no data references.\n");
1897 build_sese_loop_nests (scop
->region
);
1898 /* Record all conditions in REGION. */
1899 sese_dom_walker (CDI_DOMINATORS
, scop
->region
->region
).walk
1900 (cfun
->cfg
->x_entry_block_ptr
);
1902 find_scop_parameters (scop
);
1903 graphite_dim_t max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
1905 if (scop_nb_params (scop
) > max_dim
)
1907 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many parameters: "
1908 << scop_nb_params (scop
)
1909 << " larger than --param graphite-max-nb-scop-params="
1910 << max_dim
<< ".\n");
1916 scops
->safe_push (scop
);
1919 DEBUG_PRINT (dp
<< "number of SCoPs: " << (scops
? scops
->length () : 0););
1922 #endif /* HAVE_isl */