1 /* Detection of Static Control Parts (SCoP) for Graphite.
2 Copyright (C) 2009-2016 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and
4 Tobias Grosser <grosser@fim.uni-passau.de>.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
12
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.
17
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/>. */
21
22 #define USES_ISL
23
24 #include "config.h"
25
26 #ifdef HAVE_isl
27
28 #include "system.h"
29 #include "coretypes.h"
30 #include "backend.h"
31 #include "cfghooks.h"
32 #include "domwalk.h"
33 #include "params.h"
34 #include "tree.h"
35 #include "gimple.h"
36 #include "ssa.h"
37 #include "fold-const.h"
38 #include "gimple-iterator.h"
39 #include "tree-cfg.h"
40 #include "tree-ssa-loop-manip.h"
41 #include "tree-ssa-loop-niter.h"
42 #include "tree-ssa-loop.h"
43 #include "tree-into-ssa.h"
44 #include "tree-ssa.h"
45 #include "cfgloop.h"
46 #include "tree-data-ref.h"
47 #include "tree-scalar-evolution.h"
48 #include "tree-pass.h"
49 #include "tree-ssa-propagate.h"
50 #include "gimple-pretty-print.h"
51 #include "graphite.h"
52
53 class debug_printer
54 {
55 private:
56 FILE *dump_file;
57
58 public:
59 void
set_dump_file(FILE * f)60 set_dump_file (FILE *f)
61 {
62 gcc_assert (f);
63 dump_file = f;
64 }
65
66 friend debug_printer &
67 operator<< (debug_printer &output, int i)
68 {
69 fprintf (output.dump_file, "%d", i);
70 return output;
71 }
72 friend debug_printer &
73 operator<< (debug_printer &output, const char *s)
74 {
75 fprintf (output.dump_file, "%s", s);
76 return output;
77 }
78 } dp;
79
80 #define DEBUG_PRINT(args) do \
81 { \
82 if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \
83 } while (0);
84
85 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
86 different colors. If there are not enough colors, paint the
87 remaining SCoPs in gray.
88
89 Special nodes:
90 - "*" after the node number denotes the entry of a SCoP,
91 - "#" after the node number denotes the exit of a SCoP,
92 - "()" around the node number denotes the entry or the
93 exit nodes of the SCOP. These are not part of SCoP. */
94
95 DEBUG_FUNCTION void
dot_all_sese(FILE * file,vec<sese_l> & scops)96 dot_all_sese (FILE *file, vec<sese_l>& scops)
97 {
98 /* Disable debugging while printing graph. */
99 int tmp_dump_flags = dump_flags;
100 dump_flags = 0;
101
102 fprintf (file, "digraph all {\n");
103
104 basic_block bb;
105 FOR_ALL_BB_FN (bb, cfun)
106 {
107 int part_of_scop = false;
108
109 /* Use HTML for every bb label. So we are able to print bbs
110 which are part of two different SCoPs, with two different
111 background colors. */
112 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
113 bb->index);
114 fprintf (file, "CELLSPACING=\"0\">\n");
115
116 /* Select color for SCoP. */
117 sese_l *region;
118 int i;
119 FOR_EACH_VEC_ELT (scops, i, region)
120 {
121 bool sese_in_region = bb_in_sese_p (bb, *region);
122 if (sese_in_region || (region->exit->dest == bb)
123 || (region->entry->dest == bb))
124 {
125 const char *color;
126 switch (i % 17)
127 {
128 case 0: /* red */
129 color = "#e41a1c";
130 break;
131 case 1: /* blue */
132 color = "#377eb8";
133 break;
134 case 2: /* green */
135 color = "#4daf4a";
136 break;
137 case 3: /* purple */
138 color = "#984ea3";
139 break;
140 case 4: /* orange */
141 color = "#ff7f00";
142 break;
143 case 5: /* yellow */
144 color = "#ffff33";
145 break;
146 case 6: /* brown */
147 color = "#a65628";
148 break;
149 case 7: /* rose */
150 color = "#f781bf";
151 break;
152 case 8:
153 color = "#8dd3c7";
154 break;
155 case 9:
156 color = "#ffffb3";
157 break;
158 case 10:
159 color = "#bebada";
160 break;
161 case 11:
162 color = "#fb8072";
163 break;
164 case 12:
165 color = "#80b1d3";
166 break;
167 case 13:
168 color = "#fdb462";
169 break;
170 case 14:
171 color = "#b3de69";
172 break;
173 case 15:
174 color = "#fccde5";
175 break;
176 case 16:
177 color = "#bc80bd";
178 break;
179 default: /* gray */
180 color = "#999999";
181 }
182
183 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
184 color);
185
186 if (!sese_in_region)
187 fprintf (file, " (");
188
189 if (bb == region->entry->dest && bb == region->exit->dest)
190 fprintf (file, " %d*# ", bb->index);
191 else if (bb == region->entry->dest)
192 fprintf (file, " %d* ", bb->index);
193 else if (bb == region->exit->dest)
194 fprintf (file, " %d# ", bb->index);
195 else
196 fprintf (file, " %d ", bb->index);
197
198 fprintf (file, "{lp_%d}", bb->loop_father->num);
199
200 if (!sese_in_region)
201 fprintf (file, ")");
202
203 fprintf (file, "</TD></TR>\n");
204 part_of_scop = true;
205 }
206 }
207
208 if (!part_of_scop)
209 {
210 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
211 fprintf (file, " %d {lp_%d} </TD></TR>\n", bb->index,
212 bb->loop_father->num);
213 }
214 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
215 }
216
217 FOR_ALL_BB_FN (bb, cfun)
218 {
219 edge e;
220 edge_iterator ei;
221 FOR_EACH_EDGE (e, ei, bb->succs)
222 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
223 }
224
225 fputs ("}\n\n", file);
226
227 /* Enable debugging again. */
228 dump_flags = tmp_dump_flags;
229 }
230
231 /* Display SCoP on stderr. */
232
233 DEBUG_FUNCTION void
dot_sese(sese_l & scop)234 dot_sese (sese_l& scop)
235 {
236 vec<sese_l> scops;
237 scops.create (1);
238
239 if (scop)
240 scops.safe_push (scop);
241
242 dot_all_sese (stderr, scops);
243
244 scops.release ();
245 }
246
247 DEBUG_FUNCTION void
dot_cfg()248 dot_cfg ()
249 {
250 vec<sese_l> scops;
251 scops.create (1);
252 dot_all_sese (stderr, scops);
253 scops.release ();
254 }
255
256 /* Return true if BB is empty, contains only DEBUG_INSNs. */
257
258 static bool
trivially_empty_bb_p(basic_block bb)259 trivially_empty_bb_p (basic_block bb)
260 {
261 gimple_stmt_iterator gsi;
262
263 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
264 if (gimple_code (gsi_stmt (gsi)) != GIMPLE_DEBUG)
265 return false;
266
267 return true;
268 }
269
270 /* Returns true when P1 and P2 are close phis with the same
271 argument. */
272
273 static inline bool
same_close_phi_node(gphi * p1,gphi * p2)274 same_close_phi_node (gphi *p1, gphi *p2)
275 {
276 return (types_compatible_p (TREE_TYPE (gimple_phi_result (p1)),
277 TREE_TYPE (gimple_phi_result (p2)))
278 && operand_equal_p (gimple_phi_arg_def (p1, 0),
279 gimple_phi_arg_def (p2, 0), 0));
280 }
281
282 static void make_close_phi_nodes_unique (basic_block bb);
283
284 /* Remove the close phi node at GSI and replace its rhs with the rhs
285 of PHI. */
286
287 static void
remove_duplicate_close_phi(gphi * phi,gphi_iterator * gsi)288 remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi)
289 {
290 gimple *use_stmt;
291 use_operand_p use_p;
292 imm_use_iterator imm_iter;
293 tree res = gimple_phi_result (phi);
294 tree def = gimple_phi_result (gsi->phi ());
295
296 gcc_assert (same_close_phi_node (phi, gsi->phi ()));
297
298 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
299 {
300 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
301 SET_USE (use_p, res);
302
303 update_stmt (use_stmt);
304
305 /* It is possible that we just created a duplicate close-phi
306 for an already-processed containing loop. Check for this
307 case and clean it up. */
308 if (gimple_code (use_stmt) == GIMPLE_PHI
309 && gimple_phi_num_args (use_stmt) == 1)
310 make_close_phi_nodes_unique (gimple_bb (use_stmt));
311 }
312
313 remove_phi_node (gsi, true);
314 }
315
316 /* Removes all the close phi duplicates from BB. */
317
318 static void
make_close_phi_nodes_unique(basic_block bb)319 make_close_phi_nodes_unique (basic_block bb)
320 {
321 gphi_iterator psi;
322
323 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
324 {
325 gphi_iterator gsi = psi;
326 gphi *phi = psi.phi ();
327
328 /* At this point, PHI should be a close phi in normal form. */
329 gcc_assert (gimple_phi_num_args (phi) == 1);
330
331 /* Iterate over the next phis and remove duplicates. */
332 gsi_next (&gsi);
333 while (!gsi_end_p (gsi))
334 if (same_close_phi_node (phi, gsi.phi ()))
335 remove_duplicate_close_phi (phi, &gsi);
336 else
337 gsi_next (&gsi);
338 }
339 }
340
341 /* Return true when NAME is defined in LOOP. */
342
343 static bool
defined_in_loop_p(tree name,loop_p loop)344 defined_in_loop_p (tree name, loop_p loop)
345 {
346 gcc_assert (TREE_CODE (name) == SSA_NAME);
347 return loop == loop_containing_stmt (SSA_NAME_DEF_STMT (name));
348 }
349
350 /* Transforms LOOP to the canonical loop closed SSA form. */
351
352 static void
canonicalize_loop_closed_ssa(loop_p loop)353 canonicalize_loop_closed_ssa (loop_p loop)
354 {
355 edge e = single_exit (loop);
356 basic_block bb;
357
358 if (!e || e->flags & EDGE_ABNORMAL)
359 return;
360
361 bb = e->dest;
362
363 if (single_pred_p (bb))
364 {
365 e = split_block_after_labels (bb);
366 DEBUG_PRINT (dp << "Splitting bb_" << bb->index << ".\n");
367 make_close_phi_nodes_unique (e->src);
368 }
369 else
370 {
371 gphi_iterator psi;
372 basic_block close = split_edge (e);
373
374 e = single_succ_edge (close);
375 DEBUG_PRINT (dp << "Splitting edge (" << e->src->index << ","
376 << e->dest->index << ")\n");
377
378 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
379 {
380 gphi *phi = psi.phi ();
381 unsigned i;
382
383 for (i = 0; i < gimple_phi_num_args (phi); i++)
384 if (gimple_phi_arg_edge (phi, i) == e)
385 {
386 tree res, arg = gimple_phi_arg_def (phi, i);
387 use_operand_p use_p;
388 gphi *close_phi;
389
390 /* Only add close phi nodes for SSA_NAMEs defined in LOOP. */
391 if (TREE_CODE (arg) != SSA_NAME
392 || !defined_in_loop_p (arg, loop))
393 continue;
394
395 close_phi = create_phi_node (NULL_TREE, close);
396 res = create_new_def_for (arg, close_phi,
397 gimple_phi_result_ptr (close_phi));
398 add_phi_arg (close_phi, arg,
399 gimple_phi_arg_edge (close_phi, 0),
400 UNKNOWN_LOCATION);
401 use_p = gimple_phi_arg_imm_use_ptr (phi, i);
402 replace_exp (use_p, res);
403 update_stmt (phi);
404 }
405 }
406
407 make_close_phi_nodes_unique (close);
408 }
409
410 /* The code above does not properly handle changes in the post dominance
411 information (yet). */
412 recompute_all_dominators ();
413 }
414
415 /* Converts the current loop closed SSA form to a canonical form
416 expected by the Graphite code generation.
417
418 The loop closed SSA form has the following invariant: a variable
419 defined in a loop that is used outside the loop appears only in the
420 phi nodes in the destination of the loop exit. These phi nodes are
421 called close phi nodes.
422
423 The canonical loop closed SSA form contains the extra invariants:
424
425 - when the loop contains only one exit, the close phi nodes contain
426 only one argument. That implies that the basic block that contains
427 the close phi nodes has only one predecessor, that is a basic block
428 in the loop.
429
430 - the basic block containing the close phi nodes does not contain
431 other statements.
432
433 - there exist only one phi node per definition in the loop.
434 */
435
436 static void
canonicalize_loop_closed_ssa_form(void)437 canonicalize_loop_closed_ssa_form (void)
438 {
439 checking_verify_loop_closed_ssa (true);
440
441 loop_p loop;
442 FOR_EACH_LOOP (loop, 0)
443 canonicalize_loop_closed_ssa (loop);
444
445 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
446 update_ssa (TODO_update_ssa);
447
448 checking_verify_loop_closed_ssa (true);
449 }
450
451 /* Can all ivs be represented by a signed integer?
452 As isl might generate negative values in its expressions, signed loop ivs
453 are required in the backend. */
454
455 static bool
loop_ivs_can_be_represented(loop_p loop)456 loop_ivs_can_be_represented (loop_p loop)
457 {
458 unsigned type_long_long = TYPE_PRECISION (long_long_integer_type_node);
459 for (gphi_iterator psi = gsi_start_phis (loop->header); !gsi_end_p (psi);
460 gsi_next (&psi))
461 {
462 gphi *phi = psi.phi ();
463 tree res = PHI_RESULT (phi);
464 tree type = TREE_TYPE (res);
465
466 if (TYPE_UNSIGNED (type) && TYPE_PRECISION (type) >= type_long_long)
467 return false;
468 }
469
470 return true;
471 }
472
473 /* Returns a COND_EXPR statement when BB has a single predecessor, the
474 edge between BB and its predecessor is not a loop exit edge, and
475 the last statement of the single predecessor is a COND_EXPR. */
476
477 static gcond *
single_pred_cond_non_loop_exit(basic_block bb)478 single_pred_cond_non_loop_exit (basic_block bb)
479 {
480 if (single_pred_p (bb))
481 {
482 edge e = single_pred_edge (bb);
483 basic_block pred = e->src;
484 gimple *stmt;
485
486 if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
487 return NULL;
488
489 stmt = last_stmt (pred);
490
491 if (stmt && gimple_code (stmt) == GIMPLE_COND)
492 return as_a<gcond *> (stmt);
493 }
494
495 return NULL;
496 }
497
498 namespace
499 {
500
501 /* Build the maximal scop containing LOOPs and add it to SCOPS. */
502
503 class scop_detection
504 {
505 public:
scop_detection()506 scop_detection () : scops (vNULL) {}
507
~scop_detection()508 ~scop_detection ()
509 {
510 scops.release ();
511 }
512
513 /* A marker for invalid sese_l. */
514 static sese_l invalid_sese;
515
516 /* Return the SCOPS in this SCOP_DETECTION. */
517
518 vec<sese_l>
get_scops()519 get_scops ()
520 {
521 return scops;
522 }
523
524 /* Return an sese_l around the LOOP. */
525
526 sese_l get_sese (loop_p loop);
527
528 /* Return the closest dominator with a single entry edge. In case of a
529 back-loop the back-edge is not counted. */
530
531 static edge get_nearest_dom_with_single_entry (basic_block dom);
532
533 /* Return the closest post-dominator with a single exit edge. In case of a
534 back-loop the back-edge is not counted. */
535
536 static edge get_nearest_pdom_with_single_exit (basic_block dom);
537
538 /* Merge scops at same loop depth and returns the new sese.
539 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
540
541 sese_l merge_sese (sese_l first, sese_l second) const;
542
543 /* Build scop outer->inner if possible. */
544
545 sese_l build_scop_depth (sese_l s, loop_p loop);
546
547 /* If loop and loop->next are valid scops, try to merge them. */
548
549 sese_l build_scop_breadth (sese_l s1, loop_p loop);
550
551 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
552 region of code that can be represented in the polyhedral model. SCOP
553 defines the region we analyse. */
554
555 bool loop_is_valid_in_scop (loop_p loop, sese_l scop) const;
556
557 /* Return true when BEGIN is the preheader edge of a loop with a single exit
558 END. */
559
560 static bool region_has_one_loop (sese_l s);
561
562 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
563
564 void add_scop (sese_l s);
565
566 /* Returns true if S1 subsumes/surrounds S2. */
567 static bool subsumes (sese_l s1, sese_l s2);
568
569 /* Remove a SCoP which is subsumed by S1. */
570 void remove_subscops (sese_l s1);
571
572 /* Returns true if S1 intersects with S2. Since we already know that S1 does
573 not subsume S2 or vice-versa, we only check for entry bbs. */
574
575 static bool intersects (sese_l s1, sese_l s2);
576
577 /* Remove one of the scops when it intersects with any other. */
578
579 void remove_intersecting_scops (sese_l s1);
580
581 /* Return true when the body of LOOP has statements that can be represented
582 as a valid scop. */
583
584 bool loop_body_is_valid_scop (loop_p loop, sese_l scop) const;
585
586 /* Return true when BB contains a harmful operation for a scop: that
587 can be a function call with side effects, the induction variables
588 are not linear with respect to SCOP, etc. The current open
589 scop should end before this statement. */
590
591 bool harmful_stmt_in_bb (sese_l scop, basic_block bb) const;
592
593 /* Return true when a statement in SCOP cannot be represented by Graphite.
594 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
595 Limit the number of bbs between adjacent loops to
596 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
597
598 bool harmful_loop_in_region (sese_l scop) const;
599
600 /* Return true only when STMT is simple enough for being handled by Graphite.
601 This depends on SCOP, as the parameters are initialized relatively to
602 this basic block, the linear functions are initialized based on the
603 outermost loop containing STMT inside the SCOP. BB is the place where we
604 try to evaluate the STMT. */
605
606 bool stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
607 basic_block bb) const;
608
609 /* Something like "n * m" is not allowed. */
610
611 static bool graphite_can_represent_init (tree e);
612
613 /* Return true when SCEV can be represented in the polyhedral model.
614
615 An expression can be represented, if it can be expressed as an
616 affine expression. For loops (i, j) and parameters (m, n) all
617 affine expressions are of the form:
618
619 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
620
621 1 i + 20 j + (-2) m + 25
622
623 Something like "i * n" or "n * m" is not allowed. */
624
625 static bool graphite_can_represent_scev (tree scev);
626
627 /* Return true when EXPR can be represented in the polyhedral model.
628
629 This means an expression can be represented, if it is linear with respect
630 to the loops and the strides are non parametric. LOOP is the place where
631 the expr will be evaluated. SCOP defines the region we analyse. */
632
633 static bool graphite_can_represent_expr (sese_l scop, loop_p loop,
634 tree expr);
635
636 /* Return true if the data references of STMT can be represented by Graphite.
637 We try to analyze the data references in a loop contained in the SCOP. */
638
639 static bool stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt);
640
641 /* Remove the close phi node at GSI and replace its rhs with the rhs
642 of PHI. */
643
644 static void remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi);
645
646 /* Returns true when Graphite can represent LOOP in SCOP.
647 FIXME: For the moment, graphite cannot be used on loops that iterate using
648 induction variables that wrap. */
649
650 static bool can_represent_loop_1 (loop_p loop, sese_l scop);
651
652 /* Return true when all the loops within LOOP can be represented by
653 Graphite. */
654
655 static bool can_represent_loop (loop_p loop, sese_l scop);
656
657 /* Returns the number of pbbs that are in loops contained in SCOP. */
658
659 static int nb_pbbs_in_loops (scop_p scop);
660
661 static bool graphite_can_represent_stmt (sese_l, gimple *, basic_block);
662
663 private:
664 vec<sese_l> scops;
665 };
666
667 sese_l scop_detection::invalid_sese (NULL, NULL);
668
669 /* Return an sese_l around the LOOP. */
670
671 sese_l
get_sese(loop_p loop)672 scop_detection::get_sese (loop_p loop)
673 {
674 if (!loop)
675 return invalid_sese;
676
677 if (!loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS))
678 return invalid_sese;
679 edge scop_end = single_exit (loop);
680 if (!scop_end)
681 return invalid_sese;
682 edge scop_begin = loop_preheader_edge (loop);
683 sese_l s (scop_begin, scop_end);
684 return s;
685 }
686
687 /* Return the closest dominator with a single entry edge. */
688
689 edge
get_nearest_dom_with_single_entry(basic_block dom)690 scop_detection::get_nearest_dom_with_single_entry (basic_block dom)
691 {
692 if (!dom->preds)
693 return NULL;
694
695 /* If any of the dominators has two predecessors but one of them is a back
696 edge, then that basic block also qualifies as a dominator with single
697 entry. */
698 if (dom->preds->length () == 2)
699 {
700 /* If e1->src dominates e2->src then e1->src will also dominate dom. */
701 edge e1 = (*dom->preds)[0];
702 edge e2 = (*dom->preds)[1];
703 loop_p l = dom->loop_father;
704 loop_p l1 = e1->src->loop_father;
705 loop_p l2 = e2->src->loop_father;
706 if (l != l1 && l == l2
707 && dominated_by_p (CDI_DOMINATORS, e2->src, e1->src))
708 return e1;
709 if (l != l2 && l == l1
710 && dominated_by_p (CDI_DOMINATORS, e1->src, e2->src))
711 return e2;
712 }
713
714 while (dom->preds->length () != 1)
715 {
716 if (dom->preds->length () < 1)
717 return NULL;
718 dom = get_immediate_dominator (CDI_DOMINATORS, dom);
719 if (!dom->preds)
720 return NULL;
721 }
722 return (*dom->preds)[0];
723 }
724
725 /* Return the closest post-dominator with a single exit edge. In case of a
726 back-loop the back-edge is not counted. */
727
728 edge
get_nearest_pdom_with_single_exit(basic_block pdom)729 scop_detection::get_nearest_pdom_with_single_exit (basic_block pdom)
730 {
731 if (!pdom->succs)
732 return NULL;
733
734 /* If any of the post-dominators has two successors but one of them is a back
735 edge, then that basic block also qualifies as a post-dominator with single
736 exit. */
737 if (pdom->succs->length () == 2)
738 {
739 /* If e1->dest post-dominates e2->dest then e1->dest will also
740 post-dominate pdom. */
741 edge e1 = (*pdom->succs)[0];
742 edge e2 = (*pdom->succs)[1];
743 loop_p l = pdom->loop_father;
744 loop_p l1 = e1->dest->loop_father;
745 loop_p l2 = e2->dest->loop_father;
746 if (l != l1 && l == l2
747 && dominated_by_p (CDI_POST_DOMINATORS, e2->dest, e1->dest))
748 return e1;
749 if (l != l2 && l == l1
750 && dominated_by_p (CDI_POST_DOMINATORS, e1->dest, e2->dest))
751 return e2;
752 }
753
754 while (pdom->succs->length () != 1)
755 {
756 if (pdom->succs->length () < 1)
757 return NULL;
758 pdom = get_immediate_dominator (CDI_POST_DOMINATORS, pdom);
759 if (!pdom->succs)
760 return NULL;
761 }
762
763 return (*pdom->succs)[0];
764 }
765
766 /* Merge scops at same loop depth and returns the new sese.
767 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
768
769 sese_l
merge_sese(sese_l first,sese_l second)770 scop_detection::merge_sese (sese_l first, sese_l second) const
771 {
772 /* In the trivial case first/second may be NULL. */
773 if (!first)
774 return second;
775 if (!second)
776 return first;
777
778 DEBUG_PRINT (dp << "[scop-detection] try merging sese s1: ";
779 print_sese (dump_file, first);
780 dp << "[scop-detection] try merging sese s2: ";
781 print_sese (dump_file, second));
782
783 /* Assumption: Both the sese's should be at the same loop depth or one scop
784 should subsume the other like in case of nested loops. */
785
786 /* Find the common dominators for entry,
787 and common post-dominators for the exit. */
788 basic_block dom = nearest_common_dominator (CDI_DOMINATORS,
789 get_entry_bb (first),
790 get_entry_bb (second));
791
792 edge entry = get_nearest_dom_with_single_entry (dom);
793
794 if (!entry || (entry->flags & EDGE_IRREDUCIBLE_LOOP))
795 return invalid_sese;
796
797 basic_block pdom = nearest_common_dominator (CDI_POST_DOMINATORS,
798 get_exit_bb (first),
799 get_exit_bb (second));
800 pdom = nearest_common_dominator (CDI_POST_DOMINATORS, dom, pdom);
801
802 edge exit = get_nearest_pdom_with_single_exit (pdom);
803
804 if (!exit || (exit->flags & EDGE_IRREDUCIBLE_LOOP))
805 return invalid_sese;
806
807 sese_l combined (entry, exit);
808
809 DEBUG_PRINT (dp << "[scop-detection] checking combined sese: ";
810 print_sese (dump_file, combined));
811
812 /* FIXME: We could iterate to find the dom which dominates pdom, and pdom
813 which post-dominates dom, until it stabilizes. Also, ENTRY->SRC and
814 EXIT->DEST should be in the same loop nest. */
815 if (!dominated_by_p (CDI_DOMINATORS, pdom, dom)
816 || loop_depth (entry->src->loop_father)
817 != loop_depth (exit->dest->loop_father))
818 return invalid_sese;
819
820 /* For now we just bail out when there is a loop exit in the region
821 that is not also the exit of the region. We could enlarge the
822 region to cover the loop that region exits to. See PR79977. */
823 if (loop_outer (entry->src->loop_father))
824 {
825 vec<edge> exits = get_loop_exit_edges (entry->src->loop_father);
826 for (unsigned i = 0; i < exits.length (); ++i)
827 {
828 if (exits[i] != exit
829 && bb_in_region (exits[i]->src, entry->dest, exit->src))
830 {
831 DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
832 exits.release ();
833 return invalid_sese;
834 }
835 }
836 exits.release ();
837 }
838
839 /* For now we just want to bail out when exit does not post-dominate entry.
840 TODO: We might just add a basic_block at the exit to make exit
841 post-dominate entry (the entire region). */
842 if (!dominated_by_p (CDI_POST_DOMINATORS, get_entry_bb (combined),
843 get_exit_bb (combined))
844 || !dominated_by_p (CDI_DOMINATORS, get_exit_bb (combined),
845 get_entry_bb (combined)))
846 {
847 DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
848 return invalid_sese;
849 }
850
851 /* FIXME: We should remove this piece of code once
852 canonicalize_loop_closed_ssa has been removed, because that function
853 adds a BB with single exit. */
854 if (!trivially_empty_bb_p (get_exit_bb (combined)))
855 {
856 /* Find the first empty succ (with single exit) of combined.exit. */
857 basic_block imm_succ = combined.exit->dest;
858 if (single_succ_p (imm_succ)
859 && single_pred_p (imm_succ)
860 && trivially_empty_bb_p (imm_succ))
861 combined.exit = single_succ_edge (imm_succ);
862 else
863 {
864 DEBUG_PRINT (dp << "[scop-detection-fail] Discarding SCoP because "
865 << "no single exit (empty succ) for sese exit";
866 print_sese (dump_file, combined));
867 return invalid_sese;
868 }
869 }
870
871 /* Analyze all the BBs in new sese. */
872 if (harmful_loop_in_region (combined))
873 return invalid_sese;
874
875 DEBUG_PRINT (dp << "[merged-sese] s1: "; print_sese (dump_file, combined));
876
877 return combined;
878 }
879
880 /* Build scop outer->inner if possible. */
881
882 sese_l
build_scop_depth(sese_l s,loop_p loop)883 scop_detection::build_scop_depth (sese_l s, loop_p loop)
884 {
885 if (!loop)
886 return s;
887
888 DEBUG_PRINT (dp << "[Depth loop_" << loop->num << "]\n");
889 s = build_scop_depth (s, loop->inner);
890
891 sese_l s2 = merge_sese (s, get_sese (loop));
892 if (!s2)
893 {
894 /* s might be a valid scop, so return it and start analyzing from the
895 adjacent loop. */
896 build_scop_depth (invalid_sese, loop->next);
897 return s;
898 }
899
900 if (!loop_is_valid_in_scop (loop, s2))
901 return build_scop_depth (invalid_sese, loop->next);
902
903 return build_scop_breadth (s2, loop);
904 }
905
906 /* If loop and loop->next are valid scops, try to merge them. */
907
908 sese_l
build_scop_breadth(sese_l s1,loop_p loop)909 scop_detection::build_scop_breadth (sese_l s1, loop_p loop)
910 {
911 if (!loop)
912 return s1;
913 DEBUG_PRINT (dp << "[Breadth loop_" << loop->num << "]\n");
914 gcc_assert (s1);
915
916 loop_p l = loop;
917 sese_l s2 = build_scop_depth (invalid_sese, l->next);
918 if (!s2)
919 {
920 if (s1)
921 add_scop (s1);
922 return s1;
923 }
924
925 sese_l combined = merge_sese (s1, s2);
926
927 /* Combining adjacent loops may add unrelated loops into the
928 region so we have to check all sub-loops of the outer loop
929 that are in the combined region. */
930 if (combined)
931 for (l = loop_outer (loop)->inner; l; l = l->next)
932 if (bb_in_sese_p (l->header, combined)
933 && ! loop_is_valid_in_scop (l, combined))
934 {
935 combined = invalid_sese;
936 break;
937 }
938
939 if (combined)
940 s1 = combined;
941 else
942 add_scop (s2);
943
944 if (s1)
945 add_scop (s1);
946 return s1;
947 }
948
949 /* Returns true when Graphite can represent LOOP in SCOP.
950 FIXME: For the moment, graphite cannot be used on loops that iterate using
951 induction variables that wrap. */
952
953 bool
can_represent_loop_1(loop_p loop,sese_l scop)954 scop_detection::can_represent_loop_1 (loop_p loop, sese_l scop)
955 {
956 tree niter;
957 struct tree_niter_desc niter_desc;
958
959 return single_exit (loop)
960 && !(loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
961 && number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false)
962 && niter_desc.control.no_overflow
963 && (niter = number_of_latch_executions (loop))
964 && !chrec_contains_undetermined (niter)
965 && !chrec_contains_undetermined (scalar_evolution_in_region (scop,
966 loop, niter))
967 && graphite_can_represent_expr (scop, loop, niter);
968 }
969
970 /* Return true when all the loops within LOOP can be represented by
971 Graphite. */
972
973 bool
can_represent_loop(loop_p loop,sese_l scop)974 scop_detection::can_represent_loop (loop_p loop, sese_l scop)
975 {
976 if (!can_represent_loop_1 (loop, scop))
977 return false;
978 if (loop->inner && !can_represent_loop (loop->inner, scop))
979 return false;
980 if (loop->next && !can_represent_loop (loop->next, scop))
981 return false;
982
983 return true;
984 }
985
986 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
987 region of code that can be represented in the polyhedral model. SCOP
988 defines the region we analyse. */
989
990 bool
loop_is_valid_in_scop(loop_p loop,sese_l scop)991 scop_detection::loop_is_valid_in_scop (loop_p loop, sese_l scop) const
992 {
993 if (!scop)
994 return false;
995
996 if (!optimize_loop_nest_for_speed_p (loop))
997 {
998 DEBUG_PRINT (dp << "[scop-detection-fail] loop_"
999 << loop->num << " is not on a hot path.\n");
1000 return false;
1001 }
1002
1003 if (!can_represent_loop (loop, scop))
1004 {
1005 DEBUG_PRINT (dp << "[scop-detection-fail] cannot represent loop_"
1006 << loop->num << "\n");
1007 return false;
1008 }
1009
1010 if (loop_body_is_valid_scop (loop, scop))
1011 {
1012 DEBUG_PRINT (dp << "[valid-scop] loop_" << loop->num
1013 << " is a valid scop.\n");
1014 return true;
1015 }
1016 return false;
1017 }
1018
1019 /* Return true when BEGIN is the preheader edge of a loop with a single exit
1020 END. */
1021
1022 bool
region_has_one_loop(sese_l s)1023 scop_detection::region_has_one_loop (sese_l s)
1024 {
1025 edge begin = s.entry;
1026 edge end = s.exit;
1027 /* Check for a single perfectly nested loop. */
1028 if (begin->dest->loop_father->inner)
1029 return false;
1030
1031 /* Otherwise, check whether we have adjacent loops. */
1032 return begin->dest->loop_father == end->src->loop_father;
1033 }
1034
1035 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
1036
1037 void
add_scop(sese_l s)1038 scop_detection::add_scop (sese_l s)
1039 {
1040 gcc_assert (s);
1041
1042 /* Do not add scops with only one loop. */
1043 if (region_has_one_loop (s))
1044 {
1045 DEBUG_PRINT (dp << "[scop-detection-fail] Discarding one loop SCoP: ";
1046 print_sese (dump_file, s));
1047 return;
1048 }
1049
1050 if (get_exit_bb (s) == EXIT_BLOCK_PTR_FOR_FN (cfun))
1051 {
1052 DEBUG_PRINT (dp << "[scop-detection-fail] "
1053 << "Discarding SCoP exiting to return: ";
1054 print_sese (dump_file, s));
1055 return;
1056 }
1057
1058 /* Remove all the scops which are subsumed by s. */
1059 remove_subscops (s);
1060
1061 /* Remove intersecting scops. FIXME: It will be a good idea to keep
1062 the non-intersecting part of the scop already in the list. */
1063 remove_intersecting_scops (s);
1064
1065 scops.safe_push (s);
1066 DEBUG_PRINT (dp << "[scop-detection] Adding SCoP: "; print_sese (dump_file, s));
1067 }
1068
1069 /* Return true when a statement in SCOP cannot be represented by Graphite.
1070 The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
1071 Limit the number of bbs between adjacent loops to
1072 PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
1073
1074 bool
harmful_loop_in_region(sese_l scop)1075 scop_detection::harmful_loop_in_region (sese_l scop) const
1076 {
1077 basic_block exit_bb = get_exit_bb (scop);
1078 basic_block entry_bb = get_entry_bb (scop);
1079
1080 DEBUG_PRINT (dp << "[checking-harmful-bbs] ";
1081 print_sese (dump_file, scop));
1082 gcc_assert (dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb));
1083
1084 auto_vec<basic_block> worklist;
1085 bitmap loops = BITMAP_ALLOC (NULL);
1086
1087 worklist.safe_push (entry_bb);
1088 while (! worklist.is_empty ())
1089 {
1090 basic_block bb = worklist.pop ();
1091 DEBUG_PRINT (dp << "Visiting bb_" << bb->index << "\n");
1092
1093 /* The basic block should not be part of an irreducible loop. */
1094 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1095 {
1096 BITMAP_FREE (loops);
1097 return true;
1098 }
1099
1100 /* Check for unstructured control flow: CFG not generated by structured
1101 if-then-else. */
1102 if (bb->succs->length () > 1)
1103 {
1104 edge e;
1105 edge_iterator ei;
1106 FOR_EACH_EDGE (e, ei, bb->succs)
1107 if (!dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)
1108 && !dominated_by_p (CDI_DOMINATORS, e->dest, bb))
1109 {
1110 BITMAP_FREE (loops);
1111 return true;
1112 }
1113 }
1114
1115 /* Collect all loops in the current region. */
1116 loop_p loop = bb->loop_father;
1117 if (loop_in_sese_p (loop, scop))
1118 bitmap_set_bit (loops, loop->num);
1119 else
1120 {
1121 /* We only check for harmful statements in basic blocks not part of
1122 any loop fully contained in the scop: other bbs are checked below
1123 in loop_is_valid_in_scop. */
1124 if (harmful_stmt_in_bb (scop, bb))
1125 {
1126 BITMAP_FREE (loops);
1127 return true;
1128 }
1129 }
1130
1131 if (bb != exit_bb)
1132 for (basic_block dom = first_dom_son (CDI_DOMINATORS, bb);
1133 dom;
1134 dom = next_dom_son (CDI_DOMINATORS, dom))
1135 worklist.safe_push (dom);
1136 }
1137
1138 /* Go through all loops and check that they are still valid in the combined
1139 scop. */
1140 unsigned j;
1141 bitmap_iterator bi;
1142 EXECUTE_IF_SET_IN_BITMAP (loops, 0, j, bi)
1143 {
1144 loop_p loop = (*current_loops->larray)[j];
1145 gcc_assert (loop->num == (int) j);
1146
1147 if (!loop_is_valid_in_scop (loop, scop))
1148 {
1149 BITMAP_FREE (loops);
1150 return true;
1151 }
1152 }
1153 BITMAP_FREE (loops);
1154
1155 return false;
1156 }
1157
1158 /* Returns true if S1 subsumes/surrounds S2. */
1159 bool
subsumes(sese_l s1,sese_l s2)1160 scop_detection::subsumes (sese_l s1, sese_l s2)
1161 {
1162 if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
1163 get_entry_bb (s1))
1164 && dominated_by_p (CDI_POST_DOMINATORS, s2.exit->dest,
1165 s1.exit->dest))
1166 return true;
1167 return false;
1168 }
1169
1170 /* Remove a SCoP which is subsumed by S1. */
1171 void
remove_subscops(sese_l s1)1172 scop_detection::remove_subscops (sese_l s1)
1173 {
1174 int j;
1175 sese_l *s2;
1176 FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
1177 {
1178 if (subsumes (s1, *s2))
1179 {
1180 DEBUG_PRINT (dp << "Removing sub-SCoP";
1181 print_sese (dump_file, *s2));
1182 scops.unordered_remove (j);
1183 }
1184 }
1185 }
1186
1187 /* Returns true if S1 intersects with S2. Since we already know that S1 does
1188 not subsume S2 or vice-versa, we only check for entry bbs. */
1189
1190 bool
intersects(sese_l s1,sese_l s2)1191 scop_detection::intersects (sese_l s1, sese_l s2)
1192 {
1193 if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
1194 get_entry_bb (s1))
1195 && !dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
1196 get_exit_bb (s1)))
1197 return true;
1198 if ((s1.exit == s2.entry) || (s2.exit == s1.entry))
1199 return true;
1200
1201 return false;
1202 }
1203
1204 /* Remove one of the scops when it intersects with any other. */
1205
1206 void
remove_intersecting_scops(sese_l s1)1207 scop_detection::remove_intersecting_scops (sese_l s1)
1208 {
1209 int j;
1210 sese_l *s2;
1211 FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
1212 {
1213 if (intersects (s1, *s2))
1214 {
1215 DEBUG_PRINT (dp << "Removing intersecting SCoP";
1216 print_sese (dump_file, *s2);
1217 dp << "Intersects with:";
1218 print_sese (dump_file, s1));
1219 scops.unordered_remove (j);
1220 }
1221 }
1222 }
1223
1224 /* Something like "n * m" is not allowed. */
1225
1226 bool
graphite_can_represent_init(tree e)1227 scop_detection::graphite_can_represent_init (tree e)
1228 {
1229 switch (TREE_CODE (e))
1230 {
1231 case POLYNOMIAL_CHREC:
1232 return graphite_can_represent_init (CHREC_LEFT (e))
1233 && graphite_can_represent_init (CHREC_RIGHT (e));
1234
1235 case MULT_EXPR:
1236 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
1237 return graphite_can_represent_init (TREE_OPERAND (e, 0))
1238 && tree_fits_shwi_p (TREE_OPERAND (e, 1));
1239 else
1240 return graphite_can_represent_init (TREE_OPERAND (e, 1))
1241 && tree_fits_shwi_p (TREE_OPERAND (e, 0));
1242
1243 case PLUS_EXPR:
1244 case POINTER_PLUS_EXPR:
1245 case MINUS_EXPR:
1246 return graphite_can_represent_init (TREE_OPERAND (e, 0))
1247 && graphite_can_represent_init (TREE_OPERAND (e, 1));
1248
1249 case NEGATE_EXPR:
1250 case BIT_NOT_EXPR:
1251 CASE_CONVERT:
1252 case NON_LVALUE_EXPR:
1253 return graphite_can_represent_init (TREE_OPERAND (e, 0));
1254
1255 default:
1256 break;
1257 }
1258
1259 return true;
1260 }
1261
1262 /* Return true when SCEV can be represented in the polyhedral model.
1263
1264 An expression can be represented, if it can be expressed as an
1265 affine expression. For loops (i, j) and parameters (m, n) all
1266 affine expressions are of the form:
1267
1268 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
1269
1270 1 i + 20 j + (-2) m + 25
1271
1272 Something like "i * n" or "n * m" is not allowed. */
1273
1274 bool
graphite_can_represent_scev(tree scev)1275 scop_detection::graphite_can_represent_scev (tree scev)
1276 {
1277 if (chrec_contains_undetermined (scev))
1278 return false;
1279
1280 /* We disable the handling of pointer types, because it’s currently not
1281 supported by Graphite with the isl AST generator. SSA_NAME nodes are
1282 the only nodes, which are disabled in case they are pointers to object
1283 types, but this can be changed. */
1284
1285 if (POINTER_TYPE_P (TREE_TYPE (scev)) && TREE_CODE (scev) == SSA_NAME)
1286 return false;
1287
1288 switch (TREE_CODE (scev))
1289 {
1290 case NEGATE_EXPR:
1291 case BIT_NOT_EXPR:
1292 CASE_CONVERT:
1293 case NON_LVALUE_EXPR:
1294 return graphite_can_represent_scev (TREE_OPERAND (scev, 0));
1295
1296 case PLUS_EXPR:
1297 case POINTER_PLUS_EXPR:
1298 case MINUS_EXPR:
1299 return graphite_can_represent_scev (TREE_OPERAND (scev, 0))
1300 && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
1301
1302 case MULT_EXPR:
1303 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
1304 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
1305 && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
1306 && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
1307 && graphite_can_represent_init (scev)
1308 && graphite_can_represent_scev (TREE_OPERAND (scev, 0))
1309 && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
1310
1311 case POLYNOMIAL_CHREC:
1312 /* Check for constant strides. With a non constant stride of
1313 'n' we would have a value of 'iv * n'. Also check that the
1314 initial value can represented: for example 'n * m' cannot be
1315 represented. */
1316 if (!evolution_function_right_is_integer_cst (scev)
1317 || !graphite_can_represent_init (scev))
1318 return false;
1319 return graphite_can_represent_scev (CHREC_LEFT (scev));
1320
1321 default:
1322 break;
1323 }
1324
1325 /* Only affine functions can be represented. */
1326 if (tree_contains_chrecs (scev, NULL) || !scev_is_linear_expression (scev))
1327 return false;
1328
1329 return true;
1330 }
1331
1332 /* Return true when EXPR can be represented in the polyhedral model.
1333
1334 This means an expression can be represented, if it is linear with respect to
1335 the loops and the strides are non parametric. LOOP is the place where the
1336 expr will be evaluated. SCOP defines the region we analyse. */
1337
1338 bool
graphite_can_represent_expr(sese_l scop,loop_p loop,tree expr)1339 scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop,
1340 tree expr)
1341 {
1342 tree scev = scalar_evolution_in_region (scop, loop, expr);
1343 return graphite_can_represent_scev (scev);
1344 }
1345
1346 /* Return true if the data references of STMT can be represented by Graphite.
1347 We try to analyze the data references in a loop contained in the SCOP. */
1348
1349 bool
stmt_has_simple_data_refs_p(sese_l scop,gimple * stmt)1350 scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt)
1351 {
1352 loop_p nest = outermost_loop_in_sese (scop, gimple_bb (stmt));
1353 loop_p loop = loop_containing_stmt (stmt);
1354 vec<data_reference_p> drs = vNULL;
1355
1356 graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
1357
1358 int j;
1359 data_reference_p dr;
1360 FOR_EACH_VEC_ELT (drs, j, dr)
1361 {
1362 int nb_subscripts = DR_NUM_DIMENSIONS (dr);
1363
1364 if (nb_subscripts < 1)
1365 {
1366 free_data_refs (drs);
1367 return false;
1368 }
1369
1370 tree ref = DR_REF (dr);
1371
1372 for (int i = nb_subscripts - 1; i >= 0; i--)
1373 {
1374 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr, i))
1375 || (TREE_CODE (ref) != ARRAY_REF && TREE_CODE (ref) != MEM_REF
1376 && TREE_CODE (ref) != COMPONENT_REF))
1377 {
1378 free_data_refs (drs);
1379 return false;
1380 }
1381
1382 ref = TREE_OPERAND (ref, 0);
1383 }
1384 }
1385
1386 free_data_refs (drs);
1387 return true;
1388 }
1389
1390 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1391 Calls have side-effects, except those to const or pure
1392 functions. */
1393
1394 static bool
stmt_has_side_effects(gimple * stmt)1395 stmt_has_side_effects (gimple *stmt)
1396 {
1397 if (gimple_has_volatile_ops (stmt)
1398 || (gimple_code (stmt) == GIMPLE_CALL
1399 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
1400 || (gimple_code (stmt) == GIMPLE_ASM))
1401 {
1402 DEBUG_PRINT (dp << "[scop-detection-fail] "
1403 << "Statement has side-effects:\n";
1404 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
1405 return true;
1406 }
1407 return false;
1408 }
1409
1410 /* Returns true if STMT can be represented in polyhedral model. LABEL,
1411 simple COND stmts, pure calls, and assignments can be repesented. */
1412
1413 bool
graphite_can_represent_stmt(sese_l scop,gimple * stmt,basic_block bb)1414 scop_detection::graphite_can_represent_stmt (sese_l scop, gimple *stmt,
1415 basic_block bb)
1416 {
1417 loop_p loop = bb->loop_father;
1418 switch (gimple_code (stmt))
1419 {
1420 case GIMPLE_LABEL:
1421 return true;
1422
1423 case GIMPLE_COND:
1424 {
1425 /* We can handle all binary comparisons. Inequalities are
1426 also supported as they can be represented with union of
1427 polyhedra. */
1428 enum tree_code code = gimple_cond_code (stmt);
1429 if (!(code == LT_EXPR
1430 || code == GT_EXPR
1431 || code == LE_EXPR
1432 || code == GE_EXPR
1433 || code == EQ_EXPR
1434 || code == NE_EXPR))
1435 {
1436 DEBUG_PRINT (dp << "[scop-detection-fail] "
1437 << "Graphite cannot handle cond stmt:\n";
1438 print_gimple_stmt (dump_file, stmt, 0,
1439 TDF_VOPS | TDF_MEMSYMS));
1440 return false;
1441 }
1442
1443 for (unsigned i = 0; i < 2; ++i)
1444 {
1445 tree op = gimple_op (stmt, i);
1446 if (!graphite_can_represent_expr (scop, loop, op)
1447 /* We can only constrain on integer type. */
1448 || (TREE_CODE (TREE_TYPE (op)) != INTEGER_TYPE))
1449 {
1450 DEBUG_PRINT (dp << "[scop-detection-fail] "
1451 << "Graphite cannot represent stmt:\n";
1452 print_gimple_stmt (dump_file, stmt, 0,
1453 TDF_VOPS | TDF_MEMSYMS));
1454 return false;
1455 }
1456 }
1457
1458 return true;
1459 }
1460
1461 case GIMPLE_ASSIGN:
1462 case GIMPLE_CALL:
1463 return true;
1464
1465 default:
1466 /* These nodes cut a new scope. */
1467 DEBUG_PRINT (
1468 dp << "[scop-detection-fail] "
1469 << "Gimple stmt not handled in Graphite:\n";
1470 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
1471 return false;
1472 }
1473 }
1474
1475 /* Return true only when STMT is simple enough for being handled by Graphite.
1476 This depends on SCOP, as the parameters are initialized relatively to
1477 this basic block, the linear functions are initialized based on the outermost
1478 loop containing STMT inside the SCOP. BB is the place where we try to
1479 evaluate the STMT. */
1480
1481 bool
stmt_simple_for_scop_p(sese_l scop,gimple * stmt,basic_block bb)1482 scop_detection::stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
1483 basic_block bb) const
1484 {
1485 gcc_assert (scop);
1486
1487 if (is_gimple_debug (stmt))
1488 return true;
1489
1490 if (stmt_has_side_effects (stmt))
1491 return false;
1492
1493 if (!stmt_has_simple_data_refs_p (scop, stmt))
1494 {
1495 DEBUG_PRINT (dp << "[scop-detection-fail] "
1496 << "Graphite cannot handle data-refs in stmt:\n";
1497 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS););
1498 return false;
1499 }
1500
1501 return graphite_can_represent_stmt (scop, stmt, bb);
1502 }
1503
1504 /* Return true when BB contains a harmful operation for a scop: that
1505 can be a function call with side effects, the induction variables
1506 are not linear with respect to SCOP, etc. The current open
1507 scop should end before this statement. */
1508
1509 bool
harmful_stmt_in_bb(sese_l scop,basic_block bb)1510 scop_detection::harmful_stmt_in_bb (sese_l scop, basic_block bb) const
1511 {
1512 gimple_stmt_iterator gsi;
1513
1514 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1515 if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb))
1516 return true;
1517
1518 return false;
1519 }
1520
1521 /* Return true when the body of LOOP has statements that can be represented as a
1522 valid scop. */
1523
1524 bool
loop_body_is_valid_scop(loop_p loop,sese_l scop)1525 scop_detection::loop_body_is_valid_scop (loop_p loop, sese_l scop) const
1526 {
1527 if (!loop_ivs_can_be_represented (loop))
1528 {
1529 DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
1530 << "IV cannot be represented.\n");
1531 return false;
1532 }
1533
1534 if (!loop_nest_has_data_refs (loop))
1535 {
1536 DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
1537 << "does not have any data reference.\n");
1538 return false;
1539 }
1540
1541 basic_block *bbs = get_loop_body (loop);
1542 for (unsigned i = 0; i < loop->num_nodes; i++)
1543 {
1544 basic_block bb = bbs[i];
1545
1546 if (harmful_stmt_in_bb (scop, bb))
1547 {
1548 free (bbs);
1549 return false;
1550 }
1551 }
1552 free (bbs);
1553
1554 if (loop->inner)
1555 {
1556 loop = loop->inner;
1557 while (loop)
1558 {
1559 if (!loop_body_is_valid_scop (loop, scop))
1560 return false;
1561 loop = loop->next;
1562 }
1563 }
1564
1565 return true;
1566 }
1567
1568 /* Returns the number of pbbs that are in loops contained in SCOP. */
1569
1570 int
nb_pbbs_in_loops(scop_p scop)1571 scop_detection::nb_pbbs_in_loops (scop_p scop)
1572 {
1573 int i;
1574 poly_bb_p pbb;
1575 int res = 0;
1576
1577 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1578 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), scop->scop_info->region))
1579 res++;
1580
1581 return res;
1582 }
1583
1584 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
1585 Otherwise returns -1. */
1586
1587 static inline int
parameter_index_in_region_1(tree name,sese_info_p region)1588 parameter_index_in_region_1 (tree name, sese_info_p region)
1589 {
1590 int i;
1591 tree p;
1592
1593 gcc_assert (TREE_CODE (name) == SSA_NAME);
1594
1595 FOR_EACH_VEC_ELT (region->params, i, p)
1596 if (p == name)
1597 return i;
1598
1599 return -1;
1600 }
1601
1602 /* When the parameter NAME is in REGION, returns its index in
1603 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
1604 and returns the index of NAME. */
1605
1606 static int
parameter_index_in_region(tree name,sese_info_p region)1607 parameter_index_in_region (tree name, sese_info_p region)
1608 {
1609 int i;
1610
1611 gcc_assert (TREE_CODE (name) == SSA_NAME);
1612
1613 /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
1614 if (TREE_CODE (TREE_TYPE (name)) != INTEGER_TYPE)
1615 return -1;
1616
1617 if (!invariant_in_sese_p_rec (name, region->region, NULL))
1618 return -1;
1619
1620 i = parameter_index_in_region_1 (name, region);
1621 if (i != -1)
1622 return i;
1623
1624 i = region->params.length ();
1625 region->params.safe_push (name);
1626 return i;
1627 }
1628
1629 /* In the context of sese S, scan the expression E and translate it to
1630 a linear expression C. When parsing a symbolic multiplication, K
1631 represents the constant multiplier of an expression containing
1632 parameters. */
1633
1634 static void
scan_tree_for_params(sese_info_p s,tree e)1635 scan_tree_for_params (sese_info_p s, tree e)
1636 {
1637 if (e == chrec_dont_know)
1638 return;
1639
1640 switch (TREE_CODE (e))
1641 {
1642 case POLYNOMIAL_CHREC:
1643 scan_tree_for_params (s, CHREC_LEFT (e));
1644 break;
1645
1646 case MULT_EXPR:
1647 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
1648 scan_tree_for_params (s, TREE_OPERAND (e, 0));
1649 else
1650 scan_tree_for_params (s, TREE_OPERAND (e, 1));
1651 break;
1652
1653 case PLUS_EXPR:
1654 case POINTER_PLUS_EXPR:
1655 case MINUS_EXPR:
1656 scan_tree_for_params (s, TREE_OPERAND (e, 0));
1657 scan_tree_for_params (s, TREE_OPERAND (e, 1));
1658 break;
1659
1660 case NEGATE_EXPR:
1661 case BIT_NOT_EXPR:
1662 CASE_CONVERT:
1663 case NON_LVALUE_EXPR:
1664 scan_tree_for_params (s, TREE_OPERAND (e, 0));
1665 break;
1666
1667 case SSA_NAME:
1668 parameter_index_in_region (e, s);
1669 break;
1670
1671 case INTEGER_CST:
1672 case ADDR_EXPR:
1673 case REAL_CST:
1674 case COMPLEX_CST:
1675 case VECTOR_CST:
1676 break;
1677
1678 default:
1679 gcc_unreachable ();
1680 break;
1681 }
1682 }
1683
1684 /* Find parameters with respect to REGION in BB. We are looking in memory
1685 access functions, conditions and loop bounds. */
1686
1687 static void
find_params_in_bb(sese_info_p region,gimple_poly_bb_p gbb)1688 find_params_in_bb (sese_info_p region, gimple_poly_bb_p gbb)
1689 {
1690 /* Find parameters in the access functions of data references. */
1691 int i;
1692 data_reference_p dr;
1693 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb), i, dr)
1694 for (unsigned j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
1695 scan_tree_for_params (region, DR_ACCESS_FN (dr, j));
1696
1697 /* Find parameters in conditional statements. */
1698 gimple *stmt;
1699 loop_p loop = GBB_BB (gbb)->loop_father;
1700 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
1701 {
1702 tree lhs = scalar_evolution_in_region (region->region, loop,
1703 gimple_cond_lhs (stmt));
1704 tree rhs = scalar_evolution_in_region (region->region, loop,
1705 gimple_cond_rhs (stmt));
1706
1707 scan_tree_for_params (region, lhs);
1708 scan_tree_for_params (region, rhs);
1709 }
1710 }
1711
1712 /* Record the parameters used in the SCOP. A variable is a parameter
1713 in a scop if it does not vary during the execution of that scop. */
1714
1715 static void
find_scop_parameters(scop_p scop)1716 find_scop_parameters (scop_p scop)
1717 {
1718 unsigned i;
1719 sese_info_p region = scop->scop_info;
1720 struct loop *loop;
1721
1722 /* Find the parameters used in the loop bounds. */
1723 FOR_EACH_VEC_ELT (region->loop_nest, i, loop)
1724 {
1725 tree nb_iters = number_of_latch_executions (loop);
1726
1727 if (!chrec_contains_symbols (nb_iters))
1728 continue;
1729
1730 nb_iters = scalar_evolution_in_region (region->region, loop, nb_iters);
1731 scan_tree_for_params (region, nb_iters);
1732 }
1733
1734 /* Find the parameters used in data accesses. */
1735 poly_bb_p pbb;
1736 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1737 find_params_in_bb (region, PBB_BLACK_BOX (pbb));
1738
1739 int nbp = sese_nb_params (region);
1740 scop_set_nb_params (scop, nbp);
1741 }
1742
1743 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1744
1745 static void
build_cross_bb_scalars_def(scop_p scop,tree def,basic_block def_bb,vec<tree> * writes)1746 build_cross_bb_scalars_def (scop_p scop, tree def, basic_block def_bb,
1747 vec<tree> *writes)
1748 {
1749 if (!def || !is_gimple_reg (def))
1750 return;
1751
1752 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1753 generated out of the induction variables. */
1754 if (scev_analyzable_p (def, scop->scop_info->region))
1755 return;
1756
1757 gimple *use_stmt;
1758 imm_use_iterator imm_iter;
1759 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
1760 if (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt))
1761 {
1762 writes->safe_push (def);
1763 DEBUG_PRINT (dp << "Adding scalar write: ";
1764 print_generic_expr (dump_file, def, 0);
1765 dp << "\nFrom stmt: ";
1766 print_gimple_stmt (dump_file,
1767 SSA_NAME_DEF_STMT (def), 0, 0));
1768 /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
1769 before all the uses have been visited. */
1770 BREAK_FROM_IMM_USE_STMT (imm_iter);
1771 }
1772 }
1773
1774 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1775
1776 static void
build_cross_bb_scalars_use(scop_p scop,tree use,gimple * use_stmt,vec<scalar_use> * reads)1777 build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt,
1778 vec<scalar_use> *reads)
1779 {
1780 gcc_assert (use);
1781 if (!is_gimple_reg (use))
1782 return;
1783
1784 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1785 generated out of the induction variables. */
1786 if (scev_analyzable_p (use, scop->scop_info->region))
1787 return;
1788
1789 gimple *def_stmt = SSA_NAME_DEF_STMT (use);
1790 if (gimple_bb (def_stmt) != gimple_bb (use_stmt))
1791 {
1792 DEBUG_PRINT (dp << "Adding scalar read: ";
1793 print_generic_expr (dump_file, use, 0);
1794 dp << "\nFrom stmt: ";
1795 print_gimple_stmt (dump_file, use_stmt, 0, 0));
1796 reads->safe_push (std::make_pair (use_stmt, use));
1797 }
1798 }
1799
1800 /* Record all scalar variables that are defined and used in different BBs of the
1801 SCOP. */
1802
1803 static void
graphite_find_cross_bb_scalar_vars(scop_p scop,gimple * stmt,vec<scalar_use> * reads,vec<tree> * writes)1804 graphite_find_cross_bb_scalar_vars (scop_p scop, gimple *stmt,
1805 vec<scalar_use> *reads, vec<tree> *writes)
1806 {
1807 tree def;
1808
1809 if (gimple_code (stmt) == GIMPLE_ASSIGN)
1810 def = gimple_assign_lhs (stmt);
1811 else if (gimple_code (stmt) == GIMPLE_CALL)
1812 def = gimple_call_lhs (stmt);
1813 else if (gimple_code (stmt) == GIMPLE_PHI)
1814 def = gimple_phi_result (stmt);
1815 else
1816 return;
1817
1818
1819 build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), writes);
1820
1821 ssa_op_iter iter;
1822 use_operand_p use_p;
1823 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
1824 {
1825 tree use = USE_FROM_PTR (use_p);
1826 build_cross_bb_scalars_use (scop, use, stmt, reads);
1827 }
1828 }
1829
1830 /* Generates a polyhedral black box only if the bb contains interesting
1831 information. */
1832
1833 static gimple_poly_bb_p
try_generate_gimple_bb(scop_p scop,basic_block bb)1834 try_generate_gimple_bb (scop_p scop, basic_block bb)
1835 {
1836 vec<data_reference_p> drs = vNULL;
1837 vec<tree> writes = vNULL;
1838 vec<scalar_use> reads = vNULL;
1839
1840 sese_l region = scop->scop_info->region;
1841 loop_p nest = outermost_loop_in_sese (region, bb);
1842
1843 loop_p loop = bb->loop_father;
1844 if (!loop_in_sese_p (loop, region))
1845 loop = nest;
1846
1847 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1848 gsi_next (&gsi))
1849 {
1850 gimple *stmt = gsi_stmt (gsi);
1851 if (is_gimple_debug (stmt))
1852 continue;
1853
1854 graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
1855 graphite_find_cross_bb_scalar_vars (scop, stmt, &reads, &writes);
1856 }
1857
1858 for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
1859 gsi_next (&psi))
1860 if (!virtual_operand_p (gimple_phi_result (psi.phi ())))
1861 graphite_find_cross_bb_scalar_vars (scop, psi.phi (), &reads, &writes);
1862
1863 if (drs.is_empty () && writes.is_empty () && reads.is_empty ())
1864 return NULL;
1865
1866 return new_gimple_poly_bb (bb, drs, reads, writes);
1867 }
1868
1869 /* Compute alias-sets for all data references in DRS. */
1870
1871 static void
build_alias_set(scop_p scop)1872 build_alias_set (scop_p scop)
1873 {
1874 int num_vertices = scop->drs.length ();
1875 struct graph *g = new_graph (num_vertices);
1876 dr_info *dr1, *dr2;
1877 int i, j;
1878 int *all_vertices;
1879
1880 FOR_EACH_VEC_ELT (scop->drs, i, dr1)
1881 for (j = i+1; scop->drs.iterate (j, &dr2); j++)
1882 if (dr_may_alias_p (dr1->dr, dr2->dr, true))
1883 {
1884 add_edge (g, i, j);
1885 add_edge (g, j, i);
1886 }
1887
1888 all_vertices = XNEWVEC (int, num_vertices);
1889 for (i = 0; i < num_vertices; i++)
1890 all_vertices[i] = i;
1891
1892 graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL);
1893 free (all_vertices);
1894
1895 for (i = 0; i < g->n_vertices; i++)
1896 scop->drs[i].alias_set = g->vertices[i].component + 1;
1897
1898 free_graph (g);
1899 }
1900
1901 /* Gather BBs and conditions for a SCOP. */
1902 class gather_bbs : public dom_walker
1903 {
1904 public:
1905 gather_bbs (cdi_direction, scop_p);
1906
1907 virtual edge before_dom_children (basic_block);
1908 virtual void after_dom_children (basic_block);
1909
1910 private:
1911 auto_vec<gimple *, 3> conditions, cases;
1912 scop_p scop;
1913 };
1914 }
gather_bbs(cdi_direction direction,scop_p scop)1915 gather_bbs::gather_bbs (cdi_direction direction, scop_p scop)
1916 : dom_walker (direction), scop (scop)
1917 {
1918 }
1919
1920 /* Record in execution order the loops fully contained in the region. */
1921
1922 static void
record_loop_in_sese(basic_block bb,sese_info_p region)1923 record_loop_in_sese (basic_block bb, sese_info_p region)
1924 {
1925 loop_p father = bb->loop_father;
1926 if (loop_in_sese_p (father, region->region))
1927 {
1928 bool found = false;
1929 loop_p loop0;
1930 int j;
1931 FOR_EACH_VEC_ELT (region->loop_nest, j, loop0)
1932 if (father == loop0)
1933 {
1934 found = true;
1935 break;
1936 }
1937 if (!found)
1938 region->loop_nest.safe_push (father);
1939 }
1940 }
1941
1942 /* Call-back for dom_walk executed before visiting the dominated
1943 blocks. */
1944
1945 edge
before_dom_children(basic_block bb)1946 gather_bbs::before_dom_children (basic_block bb)
1947 {
1948 sese_info_p region = scop->scop_info;
1949 if (!bb_in_sese_p (bb, region->region))
1950 return NULL;
1951
1952 record_loop_in_sese (bb, region);
1953
1954 gcond *stmt = single_pred_cond_non_loop_exit (bb);
1955
1956 if (stmt)
1957 {
1958 edge e = single_pred_edge (bb);
1959
1960 conditions.safe_push (stmt);
1961
1962 if (e->flags & EDGE_TRUE_VALUE)
1963 cases.safe_push (stmt);
1964 else
1965 cases.safe_push (NULL);
1966 }
1967
1968 scop->scop_info->bbs.safe_push (bb);
1969
1970 gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb);
1971 if (!gbb)
1972 return NULL;
1973
1974 GBB_CONDITIONS (gbb) = conditions.copy ();
1975 GBB_CONDITION_CASES (gbb) = cases.copy ();
1976
1977 poly_bb_p pbb = new_poly_bb (scop, gbb);
1978 scop->pbbs.safe_push (pbb);
1979
1980 int i;
1981 data_reference_p dr;
1982 FOR_EACH_VEC_ELT (gbb->data_refs, i, dr)
1983 {
1984 DEBUG_PRINT (dp << "Adding memory ";
1985 if (dr->is_read)
1986 dp << "read: ";
1987 else
1988 dp << "write: ";
1989 print_generic_expr (dump_file, dr->ref, 0);
1990 dp << "\nFrom stmt: ";
1991 print_gimple_stmt (dump_file, dr->stmt, 0, 0));
1992
1993 scop->drs.safe_push (dr_info (dr, pbb));
1994 }
1995
1996 return NULL;
1997 }
1998
1999 /* Call-back for dom_walk executed after visiting the dominated
2000 blocks. */
2001
2002 void
after_dom_children(basic_block bb)2003 gather_bbs::after_dom_children (basic_block bb)
2004 {
2005 if (!bb_in_sese_p (bb, scop->scop_info->region))
2006 return;
2007
2008 if (single_pred_cond_non_loop_exit (bb))
2009 {
2010 conditions.pop ();
2011 cases.pop ();
2012 }
2013 }
2014
2015 /* Find Static Control Parts (SCoP) in the current function and pushes
2016 them to SCOPS. */
2017
2018 void
build_scops(vec<scop_p> * scops)2019 build_scops (vec<scop_p> *scops)
2020 {
2021 if (dump_file)
2022 dp.set_dump_file (dump_file);
2023
2024 canonicalize_loop_closed_ssa_form ();
2025
2026 scop_detection sb;
2027 sb.build_scop_depth (scop_detection::invalid_sese, current_loops->tree_root);
2028
2029 /* Now create scops from the lightweight SESEs. */
2030 vec<sese_l> scops_l = sb.get_scops ();
2031 int i;
2032 sese_l *s;
2033 FOR_EACH_VEC_ELT (scops_l, i, s)
2034 {
2035 scop_p scop = new_scop (s->entry, s->exit);
2036
2037 /* Record all basic blocks and their conditions in REGION. */
2038 gather_bbs (CDI_DOMINATORS, scop).walk (cfun->cfg->x_entry_block_ptr);
2039
2040 build_alias_set (scop);
2041
2042 /* Do not optimize a scop containing only PBBs that do not belong
2043 to any loops. */
2044 if (sb.nb_pbbs_in_loops (scop) == 0)
2045 {
2046 DEBUG_PRINT (dp << "[scop-detection-fail] no data references.\n");
2047 free_scop (scop);
2048 continue;
2049 }
2050
2051 unsigned max_arrays = PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP);
2052 if (scop->drs.length () >= max_arrays)
2053 {
2054 DEBUG_PRINT (dp << "[scop-detection-fail] too many data references: "
2055 << scop->drs.length ()
2056 << " is larger than --param graphite-max-arrays-per-scop="
2057 << max_arrays << ".\n");
2058 free_scop (scop);
2059 continue;
2060 }
2061
2062 find_scop_parameters (scop);
2063 graphite_dim_t max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
2064
2065 if (scop_nb_params (scop) > max_dim)
2066 {
2067 DEBUG_PRINT (dp << "[scop-detection-fail] too many parameters: "
2068 << scop_nb_params (scop)
2069 << " larger than --param graphite-max-nb-scop-params="
2070 << max_dim << ".\n");
2071 free_scop (scop);
2072 continue;
2073 }
2074
2075 scops->safe_push (scop);
2076 }
2077
2078 DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0););
2079 }
2080
2081 #endif /* HAVE_isl */
2082