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"
59 /* Lightweight representation of sese for scop detection.
60 TODO: Make all this as a constant_edge. */
63 sese_l (edge e
, edge x
) : entry (e
), exit (x
) {}
65 /* This is to push objects of sese_l in a vec. */
66 sese_l (int i
) : entry (NULL
), exit (NULL
) { gcc_assert (i
== 0); }
68 operator bool () const { return entry
&& exit
; }
71 operator= (const sese_l
&s
)
82 /* APIs for getting entry/exit of an sese. */
102 set_dump_file (FILE *f
)
108 friend debug_printer
&
109 operator<< (debug_printer
&output
, int i
)
111 fprintf (output
.dump_file
, "%d", i
);
114 friend debug_printer
&
115 operator<< (debug_printer
&output
, const char *s
)
117 fprintf (output
.dump_file
, "%s", s
);
122 #define DEBUG_PRINT(args) do \
124 if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \
128 /* Return true if BB is empty, contains only DEBUG_INSNs. */
131 trivially_empty_bb_p (basic_block bb
)
133 gimple_stmt_iterator gsi
;
135 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
136 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_DEBUG
)
142 /* Returns true when P1 and P2 are close phis with the same
146 same_close_phi_node (gphi
*p1
, gphi
*p2
)
148 return operand_equal_p (gimple_phi_arg_def (p1
, 0),
149 gimple_phi_arg_def (p2
, 0), 0);
152 /* Compare the depth of two basic_block's P1 and P2. */
155 compare_bb_depths (const void *p1
, const void *p2
)
157 const_basic_block
const bb1
= *(const_basic_block
const *)p1
;
158 const_basic_block
const bb2
= *(const_basic_block
const *)p2
;
159 int d1
= loop_depth (bb1
->loop_father
);
160 int d2
= loop_depth (bb2
->loop_father
);
171 /* Sort the basic blocks from DOM such that the first are the ones at
172 a deepest loop level. */
175 graphite_sort_dominated_info (vec
<basic_block
> dom
)
177 dom
.qsort (compare_bb_depths
);
180 static void make_close_phi_nodes_unique (basic_block bb
);
182 /* Remove the close phi node at GSI and replace its rhs with the rhs
186 remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
)
190 imm_use_iterator imm_iter
;
191 tree res
= gimple_phi_result (phi
);
192 tree def
= gimple_phi_result (gsi
->phi ());
194 gcc_assert (same_close_phi_node (phi
, gsi
->phi ()));
196 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
198 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
199 SET_USE (use_p
, res
);
201 update_stmt (use_stmt
);
203 /* It is possible that we just created a duplicate close-phi
204 for an already-processed containing loop. Check for this
205 case and clean it up. */
206 if (gimple_code (use_stmt
) == GIMPLE_PHI
207 && gimple_phi_num_args (use_stmt
) == 1)
208 make_close_phi_nodes_unique (gimple_bb (use_stmt
));
211 remove_phi_node (gsi
, true);
214 /* Removes all the close phi duplicates from BB. */
217 make_close_phi_nodes_unique (basic_block bb
)
221 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
223 gphi_iterator gsi
= psi
;
224 gphi
*phi
= psi
.phi ();
226 /* At this point, PHI should be a close phi in normal form. */
227 gcc_assert (gimple_phi_num_args (phi
) == 1);
229 /* Iterate over the next phis and remove duplicates. */
231 while (!gsi_end_p (gsi
))
232 if (same_close_phi_node (phi
, gsi
.phi ()))
233 remove_duplicate_close_phi (phi
, &gsi
);
239 /* Transforms LOOP to the canonical loop closed SSA form. */
242 canonicalize_loop_closed_ssa (loop_p loop
)
244 edge e
= single_exit (loop
);
247 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
252 if (single_pred_p (bb
))
254 e
= split_block_after_labels (bb
);
255 DEBUG_PRINT (dp
<< "\nSplitting bb_" << bb
->index
);
256 make_close_phi_nodes_unique (e
->src
);
261 basic_block close
= split_edge (e
);
263 e
= single_succ_edge (close
);
264 DEBUG_PRINT (dp
<< "\nSplitting edge (" << e
->src
->index
<< ","
265 << e
->dest
->index
<< ")\n");
267 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
269 gphi
*phi
= psi
.phi ();
272 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
273 if (gimple_phi_arg_edge (phi
, i
) == e
)
275 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
279 if (TREE_CODE (arg
) != SSA_NAME
)
282 close_phi
= create_phi_node (NULL_TREE
, close
);
283 res
= create_new_def_for (arg
, close_phi
,
284 gimple_phi_result_ptr (close_phi
));
285 add_phi_arg (close_phi
, arg
,
286 gimple_phi_arg_edge (close_phi
, 0),
288 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
289 replace_exp (use_p
, res
);
294 make_close_phi_nodes_unique (close
);
297 /* The code above does not properly handle changes in the post dominance
298 information (yet). */
299 recompute_all_dominators ();
302 /* Converts the current loop closed SSA form to a canonical form
303 expected by the Graphite code generation.
305 The loop closed SSA form has the following invariant: a variable
306 defined in a loop that is used outside the loop appears only in the
307 phi nodes in the destination of the loop exit. These phi nodes are
308 called close phi nodes.
310 The canonical loop closed SSA form contains the extra invariants:
312 - when the loop contains only one exit, the close phi nodes contain
313 only one argument. That implies that the basic block that contains
314 the close phi nodes has only one predecessor, that is a basic block
317 - the basic block containing the close phi nodes does not contain
320 - there exist only one phi node per definition in the loop.
324 canonicalize_loop_closed_ssa_form (void)
328 #ifdef ENABLE_CHECKING
329 verify_loop_closed_ssa (true);
332 FOR_EACH_LOOP (loop
, 0)
333 canonicalize_loop_closed_ssa (loop
);
335 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
336 update_ssa (TODO_update_ssa
);
338 #ifdef ENABLE_CHECKING
339 verify_loop_closed_ssa (true);
343 /* Can all ivs be represented by a signed integer?
344 As ISL might generate negative values in its expressions, signed loop ivs
345 are required in the backend. */
348 loop_ivs_can_be_represented (loop_p loop
)
350 unsigned type_long_long
= TYPE_PRECISION (long_long_integer_type_node
);
351 for (gphi_iterator psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
);
354 gphi
*phi
= psi
.phi ();
355 tree res
= PHI_RESULT (phi
);
356 tree type
= TREE_TYPE (res
);
358 if (TYPE_UNSIGNED (type
) && TYPE_PRECISION (type
) >= type_long_long
)
365 /* Returns a COND_EXPR statement when BB has a single predecessor, the
366 edge between BB and its predecessor is not a loop exit edge, and
367 the last statement of the single predecessor is a COND_EXPR. */
370 single_pred_cond_non_loop_exit (basic_block bb
)
372 if (single_pred_p (bb
))
374 edge e
= single_pred_edge (bb
);
375 basic_block pred
= e
->src
;
378 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
381 stmt
= last_stmt (pred
);
383 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
384 return as_a
<gcond
*> (stmt
);
393 /* Build the maximal scop containing LOOPs and add it to SCOPS. */
398 scop_detection () : scops (vNULL
) {}
400 /* A marker for invalid sese_l. */
401 static sese_l invalid_sese
;
403 /* Return the SCOPS in this SCOP_DETECTION. */
411 /* Return an sese_l around the LOOP. */
413 sese_l
get_sese (loop_p loop
);
415 /* Return the closest dominator with a single entry edge. In case of a
416 back-loop the back-edge is not counted. */
418 static edge
get_nearest_dom_with_single_entry (basic_block dom
);
420 /* Return the closest post-dominator with a single exit edge. In case of a
421 back-loop the back-edge is not counted. */
423 static edge
get_nearest_pdom_with_single_exit (basic_block dom
);
425 /* Print S to FILE. */
427 static void print_sese (FILE *file
, sese_l s
);
429 /* Merge scops at same loop depth and returns the new sese.
430 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
432 sese_l
merge_sese (sese_l first
, sese_l second
) const;
434 /* Build scop outer->inner if possible. */
436 sese_l
build_scop_depth (sese_l s
, loop_p loop
);
438 /* If loop and loop->next are valid scops, try to merge them. */
440 sese_l
build_scop_breadth (sese_l s1
, loop_p loop
);
442 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
443 region of code that can be represented in the polyhedral model. SCOP
444 defines the region we analyse. */
446 bool loop_is_valid_scop (loop_p loop
, sese_l scop
) const;
448 /* Return true when BEGIN is the preheader edge of a loop with a single exit
451 static bool region_has_one_loop (sese_l s
);
453 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
455 void add_scop (sese_l s
);
457 /* Returns true if S1 subsumes/surrounds S2. */
458 static bool subsumes (sese_l s1
, sese_l s2
);
460 /* Remove a SCoP which is subsumed by S1. */
461 void remove_subscops (sese_l s1
);
463 /* Returns true if S1 intersects with S2. Since we already know that S1 does
464 not subsume S2 or vice-versa, we only check for entry bbs. */
466 static bool intersects (sese_l s1
, sese_l s2
);
468 /* Remove one of the scops when it intersects with any other. */
470 void remove_intersecting_scops (sese_l s1
);
472 /* Return true when the body of LOOP has statements that can be represented
475 bool loop_body_is_valid_scop (loop_p loop
, sese_l scop
) const;
477 /* Return true when BB contains a harmful operation for a scop: that
478 can be a function call with side effects, the induction variables
479 are not linear with respect to SCOP, etc. The current open
480 scop should end before this statement. */
482 bool harmful_stmt_in_bb (sese_l scop
, basic_block bb
) const;
484 /* Return true when a statement in SCOP cannot be represented by Graphite.
485 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
486 Limit the number of bbs between adjacent loops to
487 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
489 bool harmful_stmt_in_region (sese_l scop
) const;
491 /* Return true only when STMT is simple enough for being handled by Graphite.
492 This depends on SCOP, as the parameters are initialized relatively to
493 this basic block, the linear functions are initialized based on the
494 outermost loop containing STMT inside the SCOP. BB is the place where we
495 try to evaluate the STMT. */
497 bool stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
498 basic_block bb
) const;
500 /* Something like "n * m" is not allowed. */
502 static bool graphite_can_represent_init (tree e
);
504 /* Return true when SCEV can be represented in the polyhedral model.
506 An expression can be represented, if it can be expressed as an
507 affine expression. For loops (i, j) and parameters (m, n) all
508 affine expressions are of the form:
510 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
512 1 i + 20 j + (-2) m + 25
514 Something like "i * n" or "n * m" is not allowed. */
516 static bool graphite_can_represent_scev (tree scev
);
518 /* Return true when EXPR can be represented in the polyhedral model.
520 This means an expression can be represented, if it is linear with respect
521 to the loops and the strides are non parametric. LOOP is the place where
522 the expr will be evaluated. SCOP defines the region we analyse. */
524 static bool graphite_can_represent_expr (sese_l scop
, loop_p loop
,
527 /* Return true if the data references of STMT can be represented by Graphite.
528 We try to analyze the data references in a loop contained in the SCOP. */
530 static bool stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
);
532 /* Remove the close phi node at GSI and replace its rhs with the rhs
535 static void remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
);
537 /* Returns true when Graphite can represent LOOP in SCOP.
538 FIXME: For the moment, graphite cannot be used on loops that iterate using
539 induction variables that wrap. */
541 static bool can_represent_loop_1 (loop_p loop
, sese_l scop
);
543 /* Return true when all the loops within LOOP can be represented by
546 static bool can_represent_loop (loop_p loop
, sese_l scop
);
548 /* Generates a polyhedral black box only if the bb contains interesting
551 static gimple_poly_bb_p
try_generate_gimple_bb (scop_p scop
, basic_block bb
);
553 /* Returns true if all predecessors of BB, that are not dominated by BB, are
554 marked in MAP. The predecessors dominated by BB are loop latches and will
555 be handled after BB. */
557 static bool all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
);
559 /* Recursive helper function for build_scops_bbs. */
561 static void build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
);
563 /* Gather the basic blocks belonging to the SCOP. */
565 static void build_scop_bbs (scop_p scop
);
567 /* Returns the number of pbbs that are in loops contained in SCOP. */
569 static int nb_pbbs_in_loops (scop_p scop
);
571 static bool graphite_can_represent_stmt (sese_l
, gimple
*, basic_block
);
577 sese_l
scop_detection::invalid_sese (0);
579 /* Return an sese_l around the LOOP. */
582 scop_detection::get_sese (loop_p loop
)
587 if (!loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
))
589 edge scop_end
= single_exit (loop
);
592 edge scop_begin
= loop_preheader_edge (loop
);
593 sese_l
s (scop_begin
, scop_end
);
597 /* Return the closest dominator with a single entry edge. */
600 scop_detection::get_nearest_dom_with_single_entry (basic_block dom
)
604 /* If e1->src dominates e2->src then e1->src will also dominate dom. */
605 if (dom
->preds
->length () == 2)
607 edge e1
= (*dom
->preds
)[0];
608 edge e2
= (*dom
->preds
)[1];
609 if (dominated_by_p (CDI_DOMINATORS
, e2
->src
, e1
->src
))
611 if (dominated_by_p (CDI_DOMINATORS
, e1
->src
, e2
->src
))
615 while (dom
->preds
->length () != 1)
617 if (dom
->preds
->length () < 1)
619 dom
= get_immediate_dominator (CDI_DOMINATORS
, dom
);
623 return (*dom
->preds
)[0];
626 /* Return the closest post-dominator with a single exit edge. In case of a
627 back-loop the back-edge is not counted. */
630 scop_detection::get_nearest_pdom_with_single_exit (basic_block dom
)
634 if (dom
->succs
->length () == 2)
636 edge e1
= (*dom
->succs
)[0];
637 edge e2
= (*dom
->succs
)[1];
638 if (dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, e1
->dest
))
640 if (dominated_by_p (CDI_POST_DOMINATORS
, e1
->dest
, e2
->dest
))
644 while (dom
->succs
->length () != 1)
646 if (dom
->succs
->length () < 1)
648 dom
= get_immediate_dominator (CDI_POST_DOMINATORS
, dom
);
652 return (*dom
->succs
)[0];
655 /* Print S to FILE. */
658 scop_detection::print_sese (FILE *file
, sese_l s
)
660 fprintf (file
, "(entry_edge (bb_%d, bb_%d), exit_edge (bb_%d, bb_%d))\n",
661 s
.entry
->src
->index
, s
.entry
->dest
->index
,
662 s
.exit
->src
->index
, s
.exit
->dest
->index
);
665 /* Merge scops at same loop depth and returns the new sese.
666 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
669 scop_detection::merge_sese (sese_l first
, sese_l second
) const
671 /* In the trivial case first/second may be NULL. */
677 DEBUG_PRINT (dp
<< "[try-merging-sese] s1: "; print_sese (dump_file
, first
);
678 dp
<< "[try-merging-sese] s2: ";
679 print_sese (dump_file
, second
));
681 /* Assumption: Both the sese's should be at the same loop depth or one scop
682 should subsume the other like in case of nested loops. */
684 /* Find the common dominators for entry,
685 and common post-dominators for the exit. */
686 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
,
687 get_entry_bb (first
.entry
),
688 get_entry_bb (second
.entry
));
690 edge entry
= get_nearest_dom_with_single_entry (dom
);
694 basic_block pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
,
695 get_exit_bb (first
.exit
),
696 get_exit_bb (second
.exit
));
697 pdom
= nearest_common_dominator (CDI_POST_DOMINATORS
, dom
, pdom
);
699 edge exit
= get_nearest_pdom_with_single_exit (pdom
);
703 sese_l
combined (entry
, exit
);
705 /* FIXME: We could iterate to find the dom which dominates pdom, and pdom
706 which post-dominates dom, until it stabilizes. Also, ENTRY->SRC and
707 EXIT->DEST should be in the same loop nest. */
708 if (!dominated_by_p (CDI_DOMINATORS
, pdom
, dom
)
709 || loop_depth (entry
->src
->loop_father
)
710 != loop_depth (exit
->dest
->loop_father
))
713 /* For now we just want to bail out when exit does not post-dominate entry.
714 TODO: We might just add a basic_block at the exit to make exit
715 post-dominate entry (the entire region). */
716 if (!dominated_by_p (CDI_POST_DOMINATORS
, get_entry_bb (entry
),
718 || !dominated_by_p (CDI_DOMINATORS
, get_exit_bb (exit
),
719 get_entry_bb (entry
)))
721 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
725 /* FIXME: We should remove this piece of code once
726 canonicalize_loop_closed_ssa has been removed, because that function
727 adds a BB with single exit. */
728 if (!trivially_empty_bb_p (get_exit_bb (combined
.exit
)))
730 /* Find the first empty succ (with single exit) of combined.exit. */
731 basic_block imm_succ
= combined
.exit
->dest
;
732 if (single_succ_p (imm_succ
) && trivially_empty_bb_p (imm_succ
))
733 combined
.exit
= single_succ_edge (imm_succ
);
736 DEBUG_PRINT (dp
<< "\n[scop-detection-fail] Discarding SCoP because "
737 << "no single exit (empty succ) for sese exit";
738 print_sese (dump_file
, combined
));
743 /* Analyze all the BBs in new sese. */
744 if (harmful_stmt_in_region (combined
))
747 DEBUG_PRINT (dp
<< "[merged-sese] s1: "; print_sese (dump_file
, combined
));
752 /* Build scop outer->inner if possible. */
755 scop_detection::build_scop_depth (sese_l s
, loop_p loop
)
760 DEBUG_PRINT (dp
<< "\n[Depth loop_" << loop
->num
<< "]");
761 s
= build_scop_depth (s
, loop
->inner
);
763 sese_l s2
= merge_sese (s
, get_sese (loop
));
766 /* s might be a valid scop, so return it and start analyzing from the
768 build_scop_depth (invalid_sese
, loop
->next
);
772 if (!loop_is_valid_scop (loop
, s2
))
773 return build_scop_depth (invalid_sese
, loop
->next
);
775 return build_scop_breadth (s2
, loop
);
778 /* If loop and loop->next are valid scops, try to merge them. */
781 scop_detection::build_scop_breadth (sese_l s1
, loop_p loop
)
785 DEBUG_PRINT (dp
<< "\n[Breadth loop_" << loop
->num
<< "]");
789 sese_l s2
= build_scop_depth (invalid_sese
, l
->next
);
797 sese_l combined
= merge_sese (s1
, s2
);
809 /* Returns true when Graphite can represent LOOP in SCOP.
810 FIXME: For the moment, graphite cannot be used on loops that iterate using
811 induction variables that wrap. */
814 scop_detection::can_represent_loop_1 (loop_p loop
, sese_l scop
)
817 struct tree_niter_desc niter_desc
;
819 return single_exit (loop
)
820 && number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
821 && niter_desc
.control
.no_overflow
822 && (niter
= number_of_latch_executions (loop
))
823 && !chrec_contains_undetermined (niter
)
824 && graphite_can_represent_expr (scop
, loop
, niter
);
827 /* Return true when all the loops within LOOP can be represented by
831 scop_detection::can_represent_loop (loop_p loop
, sese_l scop
)
833 if (!can_represent_loop_1 (loop
, scop
))
835 if (loop
->inner
&& !can_represent_loop (loop
->inner
, scop
))
837 if (loop
->next
&& !can_represent_loop (loop
->next
, scop
))
843 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
844 region of code that can be represented in the polyhedral model. SCOP
845 defines the region we analyse. */
848 scop_detection::loop_is_valid_scop (loop_p loop
, sese_l scop
) const
853 if (!can_represent_loop (loop
, scop
))
855 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot represent loop_"
856 << loop
->num
<< "\n");
860 if (loop_body_is_valid_scop (loop
, scop
))
862 DEBUG_PRINT (dp
<< "[valid-scop] loop_" << loop
->num
863 << "is a valid scop.\n");
869 /* Return true when BEGIN is the preheader edge of a loop with a single exit
873 scop_detection::region_has_one_loop (sese_l s
)
875 edge begin
= s
.entry
;
877 /* Check for a single perfectly nested loop. */
878 if (begin
->dest
->loop_father
->inner
)
881 /* Otherwise, check whether we have adjacent loops. */
882 return begin
->dest
->loop_father
== end
->src
->loop_father
;
885 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
888 scop_detection::add_scop (sese_l s
)
892 /* Do not add scops with only one loop. */
893 if (region_has_one_loop (s
))
895 DEBUG_PRINT (dp
<< "\n[scop-detection-fail] Discarding one loop SCoP";
896 print_sese (dump_file
, s
));
900 if (get_exit_bb (s
.exit
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
902 DEBUG_PRINT (dp
<< "\n[scop-detection-fail] "
903 << "Discarding SCoP exiting to return";
904 print_sese (dump_file
, s
));
908 /* Remove all the scops which are subsumed by s. */
911 /* Replace this with split-intersecting scops. */
912 remove_intersecting_scops (s
);
915 DEBUG_PRINT (dp
<< "\nAdding SCoP "; print_sese (dump_file
, s
));
918 /* Return true when a statement in SCOP cannot be represented by Graphite.
919 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
920 Limit the number of bbs between adjacent loops to
921 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
924 scop_detection::harmful_stmt_in_region (sese_l scop
) const
926 basic_block exit_bb
= get_exit_bb (scop
.exit
);
927 basic_block entry_bb
= get_entry_bb (scop
.entry
);
929 DEBUG_PRINT (dp
<< "\n[checking-harmful-bbs] ";
930 print_sese (dump_file
, scop
));
931 gcc_assert (dominated_by_p (CDI_DOMINATORS
, exit_bb
, entry_bb
));
933 int depth
= bb_dom_dfs_in (CDI_DOMINATORS
, exit_bb
)
934 - bb_dom_dfs_in (CDI_DOMINATORS
, entry_bb
);
936 gcc_assert (depth
> 0);
939 = get_dominated_to_depth (CDI_DOMINATORS
, entry_bb
, depth
);
942 FOR_EACH_VEC_ELT (dom
, i
, bb
)
944 DEBUG_PRINT (dp
<< "\nVisiting bb_" << bb
->index
);
946 /* We don't want to analyze any bb outside sese. */
947 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb
, exit_bb
))
950 if (harmful_stmt_in_bb (scop
, bb
))
957 /* Returns true if S1 subsumes/surrounds S2. */
959 scop_detection::subsumes (sese_l s1
, sese_l s2
)
961 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
.entry
),
962 get_entry_bb (s1
.entry
))
963 && dominated_by_p (CDI_POST_DOMINATORS
, get_entry_bb (s2
.exit
),
964 get_entry_bb (s1
.exit
)))
969 /* Remove a SCoP which is subsumed by S1. */
971 scop_detection::remove_subscops (sese_l s1
)
975 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
977 if (subsumes (s1
, s2
))
979 DEBUG_PRINT (dp
<< "\nRemoving sub-SCoP";
980 print_sese (dump_file
, s2
));
981 scops
.unordered_remove (j
);
986 /* Returns true if S1 intersects with S2. Since we already know that S1 does
987 not subsume S2 or vice-versa, we only check for entry bbs. */
990 scop_detection::intersects (sese_l s1
, sese_l s2
)
992 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
.entry
),
993 get_entry_bb (s1
.entry
))
994 && !dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
.entry
),
995 get_exit_bb (s1
.exit
)))
997 if ((s1
.exit
== s2
.entry
) || (s2
.exit
== s1
.entry
))
1003 /* Remove one of the scops when it intersects with any other. */
1006 scop_detection::remove_intersecting_scops (sese_l s1
)
1010 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
1012 if (intersects (s1
, s2
))
1014 DEBUG_PRINT (dp
<< "\nRemoving intersecting SCoP";
1015 print_sese (dump_file
, s2
); dp
<< "Intersects with:";
1016 print_sese (dump_file
, s1
));
1017 scops
.unordered_remove (j
);
1022 /* Something like "n * m" is not allowed. */
1025 scop_detection::graphite_can_represent_init (tree e
)
1027 switch (TREE_CODE (e
))
1029 case POLYNOMIAL_CHREC
:
1030 return graphite_can_represent_init (CHREC_LEFT (e
))
1031 && graphite_can_represent_init (CHREC_RIGHT (e
));
1034 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1035 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
1036 && tree_fits_shwi_p (TREE_OPERAND (e
, 1));
1038 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
1039 && tree_fits_shwi_p (TREE_OPERAND (e
, 0));
1042 case POINTER_PLUS_EXPR
:
1044 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
1045 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
1050 case NON_LVALUE_EXPR
:
1051 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
1060 /* Return true when SCEV can be represented in the polyhedral model.
1062 An expression can be represented, if it can be expressed as an
1063 affine expression. For loops (i, j) and parameters (m, n) all
1064 affine expressions are of the form:
1066 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
1068 1 i + 20 j + (-2) m + 25
1070 Something like "i * n" or "n * m" is not allowed. */
1073 scop_detection::graphite_can_represent_scev (tree scev
)
1075 if (chrec_contains_undetermined (scev
))
1078 /* We disable the handling of pointer types, because it’s currently not
1079 supported by Graphite with the ISL AST generator. SSA_NAME nodes are
1080 the only nodes, which are disabled in case they are pointers to object
1081 types, but this can be changed. */
1083 if (POINTER_TYPE_P (TREE_TYPE (scev
)) && TREE_CODE (scev
) == SSA_NAME
)
1086 switch (TREE_CODE (scev
))
1091 case NON_LVALUE_EXPR
:
1092 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0));
1095 case POINTER_PLUS_EXPR
:
1097 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1098 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1101 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
1102 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
1103 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
1104 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
1105 && graphite_can_represent_init (scev
)
1106 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
1107 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
1109 case POLYNOMIAL_CHREC
:
1110 /* Check for constant strides. With a non constant stride of
1111 'n' we would have a value of 'iv * n'. Also check that the
1112 initial value can represented: for example 'n * m' cannot be
1114 if (!evolution_function_right_is_integer_cst (scev
)
1115 || !graphite_can_represent_init (scev
))
1117 return graphite_can_represent_scev (CHREC_LEFT (scev
));
1123 /* Only affine functions can be represented. */
1124 if (tree_contains_chrecs (scev
, NULL
) || !scev_is_linear_expression (scev
))
1130 /* Return true when EXPR can be represented in the polyhedral model.
1132 This means an expression can be represented, if it is linear with respect to
1133 the loops and the strides are non parametric. LOOP is the place where the
1134 expr will be evaluated. SCOP defines the region we analyse. */
1137 scop_detection::graphite_can_represent_expr (sese_l scop
, loop_p loop
,
1140 sese region
= new_sese (scop
.entry
, scop
.exit
);
1141 tree scev
= scalar_evolution_in_region (region
, loop
, expr
);
1143 return graphite_can_represent_scev (scev
);
1146 /* Return true if the data references of STMT can be represented by Graphite.
1147 We try to analyze the data references in a loop contained in the SCOP. */
1150 scop_detection::stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
)
1152 sese region
= new_sese (scop
.entry
, scop
.exit
);
1153 loop_p nest
= outermost_loop_in_sese (region
, gimple_bb (stmt
));
1154 loop_p loop
= loop_containing_stmt (stmt
);
1155 vec
<data_reference_p
> drs
= vNULL
;
1157 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1160 data_reference_p dr
;
1161 FOR_EACH_VEC_ELT (drs
, j
, dr
)
1163 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1165 if (nb_subscripts
< 1)
1167 free_data_refs (drs
);
1171 tree ref
= DR_REF (dr
);
1173 for (int i
= nb_subscripts
- 1; i
>= 0; i
--)
1175 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
))
1176 || (TREE_CODE (ref
) != ARRAY_REF
&& TREE_CODE (ref
) != MEM_REF
1177 && TREE_CODE (ref
) != COMPONENT_REF
))
1179 free_data_refs (drs
);
1183 ref
= TREE_OPERAND (ref
, 0);
1187 free_data_refs (drs
);
1191 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1192 Calls have side-effects, except those to const or pure
1196 stmt_has_side_effects (gimple
*stmt
)
1198 if (gimple_has_volatile_ops (stmt
)
1199 || (gimple_code (stmt
) == GIMPLE_CALL
1200 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
1201 || (gimple_code (stmt
) == GIMPLE_ASM
))
1203 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1204 << "Statement has side-effects:\n";
1205 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1211 /* Returns true if STMT can be represented in polyhedral model. LABEL,
1212 simple COND stmts, pure calls, and assignments can be repesented. */
1215 scop_detection::graphite_can_represent_stmt (sese_l scop
, gimple
*stmt
,
1218 loop_p loop
= bb
->loop_father
;
1219 switch (gimple_code (stmt
))
1226 /* We can handle all binary comparisons. Inequalities are
1227 also supported as they can be represented with union of
1229 enum tree_code code
= gimple_cond_code (stmt
);
1230 if (!(code
== LT_EXPR
1235 || code
== NE_EXPR
))
1237 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1238 << "Graphite cannot handle cond stmt:\n";
1239 print_gimple_stmt (dump_file
, stmt
, 0,
1240 TDF_VOPS
| TDF_MEMSYMS
));
1244 for (unsigned i
= 0; i
< 2; ++i
)
1246 tree op
= gimple_op (stmt
, i
);
1247 if (!graphite_can_represent_expr (scop
, loop
, op
)
1248 /* We can only constrain on integer type. */
1249 || (TREE_CODE (TREE_TYPE (op
)) != INTEGER_TYPE
))
1251 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1252 << "Graphite cannot represent stmt:\n";
1253 print_gimple_stmt (dump_file
, stmt
, 0,
1254 TDF_VOPS
| TDF_MEMSYMS
));
1267 /* These nodes cut a new scope. */
1269 dp
<< "[scop-detection-fail] "
1270 << "Gimple stmt not handled in Graphite:\n";
1271 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1276 /* Return true only when STMT is simple enough for being handled by Graphite.
1277 This depends on SCOP, as the parameters are initialized relatively to
1278 this basic block, the linear functions are initialized based on the outermost
1279 loop containing STMT inside the SCOP. BB is the place where we try to
1280 evaluate the STMT. */
1283 scop_detection::stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
1284 basic_block bb
) const
1288 if (is_gimple_debug (stmt
))
1291 if (stmt_has_side_effects (stmt
))
1294 if (!stmt_has_simple_data_refs_p (scop
, stmt
))
1296 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1297 << "Graphite cannot handle data-refs in stmt:\n";
1298 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
););
1302 return graphite_can_represent_stmt (scop
, stmt
, bb
);
1305 /* Return true when BB contains a harmful operation for a scop: that
1306 can be a function call with side effects, the induction variables
1307 are not linear with respect to SCOP, etc. The current open
1308 scop should end before this statement. */
1311 scop_detection::harmful_stmt_in_bb (sese_l scop
, basic_block bb
) const
1313 gimple_stmt_iterator gsi
;
1315 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1316 if (!stmt_simple_for_scop_p (scop
, gsi_stmt (gsi
), bb
))
1322 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1323 different colors. If there are not enough colors, paint the
1324 remaining SCoPs in gray.
1327 - "*" after the node number denotes the entry of a SCoP,
1328 - "#" after the node number denotes the exit of a SCoP,
1329 - "()" around the node number denotes the entry or the
1330 exit nodes of the SCOP. These are not part of SCoP. */
1333 dot_all_scops_1 (FILE *file
, vec
<scop_p
> scops
)
1342 /* Disable debugging while printing graph. */
1343 int tmp_dump_flags
= dump_flags
;
1346 fprintf (file
, "digraph all {\n");
1348 FOR_ALL_BB_FN (bb
, cfun
)
1350 int part_of_scop
= false;
1352 /* Use HTML for every bb label. So we are able to print bbs
1353 which are part of two different SCoPs, with two different
1354 background colors. */
1355 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1357 fprintf (file
, "CELLSPACING=\"0\">\n");
1359 /* Select color for SCoP. */
1360 FOR_EACH_VEC_ELT (scops
, i
, scop
)
1362 sese region
= SCOP_REGION (scop
);
1363 if (bb_in_sese_p (bb
, region
) || (SESE_EXIT_BB (region
) == bb
)
1364 || (SESE_ENTRY_BB (region
) == bb
))
1377 case 3: /* purple */
1380 case 4: /* orange */
1383 case 5: /* yellow */
1423 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
1426 if (!bb_in_sese_p (bb
, region
))
1427 fprintf (file
, " (");
1429 if (bb
== SESE_ENTRY_BB (region
) && bb
== SESE_EXIT_BB (region
))
1430 fprintf (file
, " %d*# ", bb
->index
);
1431 else if (bb
== SESE_ENTRY_BB (region
))
1432 fprintf (file
, " %d* ", bb
->index
);
1433 else if (bb
== SESE_EXIT_BB (region
))
1434 fprintf (file
, " %d# ", bb
->index
);
1436 fprintf (file
, " %d ", bb
->index
);
1438 fprintf (file
, "{lp_%d}", bb
->loop_father
->num
);
1440 if (!bb_in_sese_p (bb
, region
))
1441 fprintf (file
, ")");
1443 fprintf (file
, "</TD></TR>\n");
1444 part_of_scop
= true;
1450 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1451 fprintf (file
, " %d {lp_%d} </TD></TR>\n", bb
->index
,
1452 bb
->loop_father
->num
);
1454 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1457 FOR_ALL_BB_FN (bb
, cfun
)
1459 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1460 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
1463 fputs ("}\n\n", file
);
1465 /* Enable debugging again. */
1466 dump_flags
= tmp_dump_flags
;
1469 /* Display all SCoPs using dotty. */
1472 dot_all_scops (vec
<scop_p
> scops
)
1474 /* When debugging, enable the following code. This cannot be used
1475 in production compilers because it calls "system". */
1478 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1479 gcc_assert (stream
);
1481 dot_all_scops_1 (stream
, scops
);
1484 x
= system ("dotty /tmp/allscops.dot &");
1486 dot_all_scops_1 (stderr
, scops
);
1490 /* Display all SCoPs using dotty. */
1493 dot_scop (scop_p scop
)
1495 auto_vec
<scop_p
, 1> scops
;
1498 scops
.safe_push (scop
);
1500 /* When debugging, enable the following code. This cannot be used
1501 in production compilers because it calls "system". */
1505 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1506 gcc_assert (stream
);
1508 dot_all_scops_1 (stream
, scops
);
1510 x
= system ("dotty /tmp/allscops.dot &");
1513 dot_all_scops_1 (stderr
, scops
);
1517 /* Return true when the body of LOOP has statements that can be represented as a
1521 scop_detection::loop_body_is_valid_scop (loop_p loop
, sese_l scop
) const
1523 if (!loop_ivs_can_be_represented (loop
))
1525 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
1526 << "IV cannot be represented.\n");
1530 if (!loop_nest_has_data_refs (loop
))
1532 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
1533 << "does not have any data reference.\n");
1537 basic_block
*bbs
= get_loop_body (loop
);
1538 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
1540 basic_block bb
= bbs
[i
];
1542 if (harmful_stmt_in_bb (scop
, bb
))
1552 if (!loop_body_is_valid_scop (loop
, scop
))
1561 /* Generates a polyhedral black box only if the bb contains interesting
1565 scop_detection::try_generate_gimple_bb (scop_p scop
, basic_block bb
)
1567 vec
<data_reference_p
> drs
;
1569 sese region
= SCOP_REGION (scop
);
1570 loop_p nest
= outermost_loop_in_sese (region
, bb
);
1572 loop_p loop
= bb
->loop_father
;
1573 if (!loop_in_sese_p (loop
, region
))
1576 gimple_stmt_iterator gsi
;
1577 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1579 gimple
*stmt
= gsi_stmt (gsi
);
1580 if (is_gimple_debug (stmt
))
1583 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1586 return new_gimple_poly_bb (bb
, drs
);
1589 /* Returns true if all predecessors of BB, that are not dominated by BB, are
1590 marked in MAP. The predecessors dominated by BB are loop latches and will
1591 be handled after BB. */
1594 scop_detection::all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
1599 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1600 if (!bitmap_bit_p (map
, e
->src
->index
)
1601 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
1607 /* Recursive helper function for build_scops_bbs. */
1610 scop_detection::build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
1612 sese region
= SCOP_REGION (scop
);
1613 vec
<basic_block
> dom
;
1616 if (bitmap_bit_p (visited
, bb
->index
) || !bb_in_sese_p (bb
, region
))
1619 pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
1620 SCOP_BBS (scop
).safe_push (pbb
);
1621 bitmap_set_bit (visited
, bb
->index
);
1623 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
1628 graphite_sort_dominated_info (dom
);
1630 while (!dom
.is_empty ())
1635 FOR_EACH_VEC_ELT (dom
, i
, dom_bb
)
1636 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
1638 build_scop_bbs_1 (scop
, visited
, dom_bb
);
1639 dom
.unordered_remove (i
);
1647 /* Gather the basic blocks belonging to the SCOP. */
1650 scop_detection::build_scop_bbs (scop_p scop
)
1652 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1653 sese region
= SCOP_REGION (scop
);
1655 bitmap_clear (visited
);
1656 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
1657 sbitmap_free (visited
);
1660 /* Returns the number of pbbs that are in loops contained in SCOP. */
1663 scop_detection::nb_pbbs_in_loops (scop_p scop
)
1669 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1670 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
1676 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
1677 Otherwise returns -1. */
1680 parameter_index_in_region_1 (tree name
, sese region
)
1685 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1687 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
1694 /* When the parameter NAME is in REGION, returns its index in
1695 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
1696 and returns the index of NAME. */
1699 parameter_index_in_region (tree name
, sese region
)
1703 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1705 /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
1706 if (TREE_CODE (TREE_TYPE (name
)) != INTEGER_TYPE
)
1709 if (!invariant_in_sese_p_rec (name
, region
))
1712 i
= parameter_index_in_region_1 (name
, region
);
1716 gcc_assert (SESE_ADD_PARAMS (region
));
1718 i
= SESE_PARAMS (region
).length ();
1719 SESE_PARAMS (region
).safe_push (name
);
1723 /* In the context of sese S, scan the expression E and translate it to
1724 a linear expression C. When parsing a symbolic multiplication, K
1725 represents the constant multiplier of an expression containing
1729 scan_tree_for_params (sese s
, tree e
)
1731 if (e
== chrec_dont_know
)
1734 switch (TREE_CODE (e
))
1736 case POLYNOMIAL_CHREC
:
1737 scan_tree_for_params (s
, CHREC_LEFT (e
));
1741 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1742 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1744 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1748 case POINTER_PLUS_EXPR
:
1750 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1751 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1757 case NON_LVALUE_EXPR
:
1758 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1762 parameter_index_in_region (e
, s
);
1778 /* Find parameters with respect to REGION in BB. We are looking in memory
1779 access functions, conditions and loop bounds. */
1782 find_params_in_bb (sese region
, gimple_poly_bb_p gbb
)
1786 data_reference_p dr
;
1788 loop_p loop
= GBB_BB (gbb
)->loop_father
;
1790 /* Find parameters in the access functions of data references. */
1791 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
1792 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
1793 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
1795 /* Find parameters in conditional statements. */
1796 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1798 tree lhs
= scalar_evolution_in_region (region
, loop
,
1799 gimple_cond_lhs (stmt
));
1800 tree rhs
= scalar_evolution_in_region (region
, loop
,
1801 gimple_cond_rhs (stmt
));
1803 scan_tree_for_params (region
, lhs
);
1804 scan_tree_for_params (region
, rhs
);
1808 /* Record the parameters used in the SCOP. A variable is a parameter
1809 in a scop if it does not vary during the execution of that scop. */
1812 find_scop_parameters (scop_p scop
)
1816 sese region
= SCOP_REGION (scop
);
1820 /* Find the parameters used in the loop bounds. */
1821 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1823 tree nb_iters
= number_of_latch_executions (loop
);
1825 if (!chrec_contains_symbols (nb_iters
))
1828 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1829 scan_tree_for_params (region
, nb_iters
);
1832 /* Find the parameters used in data accesses. */
1833 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1834 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1836 nbp
= sese_nb_params (region
);
1837 scop_set_nb_params (scop
, nbp
);
1838 SESE_ADD_PARAMS (region
) = false;
1841 class sese_dom_walker
: public dom_walker
1844 sese_dom_walker (cdi_direction
, sese
);
1846 virtual void before_dom_children (basic_block
);
1847 virtual void after_dom_children (basic_block
);
1850 auto_vec
<gimple
*, 3> m_conditions
, m_cases
;
1854 sese_dom_walker::sese_dom_walker (cdi_direction direction
, sese region
)
1855 : dom_walker (direction
), m_region (region
)
1859 /* Call-back for dom_walk executed before visiting the dominated
1863 sese_dom_walker::before_dom_children (basic_block bb
)
1865 gimple_poly_bb_p gbb
;
1868 if (!bb_in_sese_p (bb
, m_region
))
1871 stmt
= single_pred_cond_non_loop_exit (bb
);
1875 edge e
= single_pred_edge (bb
);
1877 m_conditions
.safe_push (stmt
);
1879 if (e
->flags
& EDGE_TRUE_VALUE
)
1880 m_cases
.safe_push (stmt
);
1882 m_cases
.safe_push (NULL
);
1885 gbb
= gbb_from_bb (bb
);
1889 GBB_CONDITIONS (gbb
) = m_conditions
.copy ();
1890 GBB_CONDITION_CASES (gbb
) = m_cases
.copy ();
1894 /* Call-back for dom_walk executed after visiting the dominated
1898 sese_dom_walker::after_dom_children (basic_block bb
)
1900 if (!bb_in_sese_p (bb
, m_region
))
1903 if (single_pred_cond_non_loop_exit (bb
))
1905 m_conditions
.pop ();
1910 /* Find Static Control Parts (SCoP) in the current function and pushes
1914 build_scops (vec
<scop_p
> *scops
)
1917 dp
.set_dump_file (dump_file
);
1919 canonicalize_loop_closed_ssa_form ();
1922 sb
.build_scop_depth (scop_detection::invalid_sese
, current_loops
->tree_root
);
1924 /* Now create scops from the lightweight SESEs. */
1925 vec
<sese_l
> scops_l
= sb
.get_scops ();
1928 FOR_EACH_VEC_ELT (scops_l
, i
, s
)
1930 scop_p scop
= new_scop (s
.entry
, s
.exit
);
1932 sb
.build_scop_bbs (scop
);
1933 /* Do not optimize a scop containing only PBBs that do not belong
1935 if (sb
.nb_pbbs_in_loops (scop
) == 0)
1937 DEBUG_PRINT (dp
<< "[scop-detection-fail] no data references.\n");
1942 build_sese_loop_nests (scop
->region
);
1943 /* Record all conditions in REGION. */
1944 sese_dom_walker (CDI_DOMINATORS
, scop
->region
).walk
1945 (cfun
->cfg
->x_entry_block_ptr
);
1947 find_scop_parameters (scop
);
1948 graphite_dim_t max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
1950 if (scop_nb_params (scop
) > max_dim
)
1952 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many parameters: "
1953 << scop_nb_params (scop
)
1954 << " larger than --param graphite-max-nb-scop-params="
1955 << max_dim
<< ".\n");
1961 scops
->safe_push (scop
);
1964 DEBUG_PRINT (dp
<< "number of SCoPs: " << (scops
? scops
->length () : 0););
1967 #endif /* HAVE_isl */