Branch data Line data Source code
1 : : /* Detection of Static Control Parts (SCoP) for Graphite.
2 : : Copyright (C) 2009-2024 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 INCLUDE_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 "tree.h"
34 : : #include "gimple.h"
35 : : #include "ssa.h"
36 : : #include "fold-const.h"
37 : : #include "gimple-iterator.h"
38 : : #include "tree-cfg.h"
39 : : #include "tree-ssa-loop-manip.h"
40 : : #include "tree-ssa-loop-niter.h"
41 : : #include "tree-ssa-loop.h"
42 : : #include "tree-into-ssa.h"
43 : : #include "tree-ssa.h"
44 : : #include "cfgloop.h"
45 : : #include "tree-data-ref.h"
46 : : #include "tree-scalar-evolution.h"
47 : : #include "tree-pass.h"
48 : : #include "tree-ssa-propagate.h"
49 : : #include "gimple-pretty-print.h"
50 : : #include "cfganal.h"
51 : : #include "graphite.h"
52 : :
53 : : class debug_printer
54 : : {
55 : : private:
56 : : FILE *dump_file;
57 : :
58 : : public:
59 : : void
60 : 189 : set_dump_file (FILE *f)
61 : : {
62 : 189 : gcc_assert (f);
63 : 189 : dump_file = f;
64 : 189 : }
65 : :
66 : : friend debug_printer &
67 : 2518 : operator<< (debug_printer &output, int i)
68 : : {
69 : 0 : fprintf (output.dump_file, "%d", i);
70 : 188 : return output;
71 : : }
72 : :
73 : : friend debug_printer &
74 : 8481 : operator<< (debug_printer &output, const char *s)
75 : : {
76 : 8481 : fprintf (output.dump_file, "%s", s);
77 : 2918 : return output;
78 : : }
79 : :
80 : : friend debug_printer &
81 : : operator<< (debug_printer &output, gimple* stmt)
82 : : {
83 : : print_gimple_stmt (output.dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS);
84 : : return output;
85 : : }
86 : :
87 : : friend debug_printer &
88 : 47 : operator<< (debug_printer &output, tree t)
89 : : {
90 : 47 : print_generic_expr (output.dump_file, t, TDF_SLIM);
91 : 47 : return output;
92 : : }
93 : : } dp;
94 : :
95 : : #define DEBUG_PRINT(args) do \
96 : : { \
97 : : if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \
98 : : } while (0)
99 : :
100 : : /* Pretty print to FILE all the SCoPs in DOT format and mark them with
101 : : different colors. If there are not enough colors, paint the
102 : : remaining SCoPs in gray.
103 : :
104 : : Special nodes:
105 : : - "*" after the node number denotes the entry of a SCoP,
106 : : - "#" after the node number denotes the exit of a SCoP,
107 : : - "()" around the node number denotes the entry or the
108 : : exit nodes of the SCOP. These are not part of SCoP. */
109 : :
110 : : DEBUG_FUNCTION void
111 : 0 : dot_all_sese (FILE *file, vec<sese_l>& scops)
112 : : {
113 : : /* Disable debugging while printing graph. */
114 : 0 : dump_flags_t tmp_dump_flags = dump_flags;
115 : 0 : dump_flags = TDF_NONE;
116 : :
117 : 0 : fprintf (file, "digraph all {\n");
118 : :
119 : 0 : basic_block bb;
120 : 0 : FOR_ALL_BB_FN (bb, cfun)
121 : : {
122 : 0 : int part_of_scop = false;
123 : :
124 : : /* Use HTML for every bb label. So we are able to print bbs
125 : : which are part of two different SCoPs, with two different
126 : : background colors. */
127 : 0 : fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
128 : : bb->index);
129 : 0 : fprintf (file, "CELLSPACING=\"0\">\n");
130 : :
131 : : /* Select color for SCoP. */
132 : 0 : sese_l *region;
133 : 0 : int i;
134 : 0 : FOR_EACH_VEC_ELT (scops, i, region)
135 : : {
136 : 0 : bool sese_in_region = bb_in_sese_p (bb, *region);
137 : 0 : if (sese_in_region || (region->exit->dest == bb)
138 : 0 : || (region->entry->dest == bb))
139 : : {
140 : 0 : const char *color;
141 : 0 : switch (i % 17)
142 : : {
143 : : case 0: /* red */
144 : : color = "#e41a1c";
145 : : break;
146 : 0 : case 1: /* blue */
147 : 0 : color = "#377eb8";
148 : 0 : break;
149 : 0 : case 2: /* green */
150 : 0 : color = "#4daf4a";
151 : 0 : break;
152 : 0 : case 3: /* purple */
153 : 0 : color = "#984ea3";
154 : 0 : break;
155 : 0 : case 4: /* orange */
156 : 0 : color = "#ff7f00";
157 : 0 : break;
158 : 0 : case 5: /* yellow */
159 : 0 : color = "#ffff33";
160 : 0 : break;
161 : 0 : case 6: /* brown */
162 : 0 : color = "#a65628";
163 : 0 : break;
164 : 0 : case 7: /* rose */
165 : 0 : color = "#f781bf";
166 : 0 : break;
167 : 0 : case 8:
168 : 0 : color = "#8dd3c7";
169 : 0 : break;
170 : 0 : case 9:
171 : 0 : color = "#ffffb3";
172 : 0 : break;
173 : 0 : case 10:
174 : 0 : color = "#bebada";
175 : 0 : break;
176 : 0 : case 11:
177 : 0 : color = "#fb8072";
178 : 0 : break;
179 : 0 : case 12:
180 : 0 : color = "#80b1d3";
181 : 0 : break;
182 : 0 : case 13:
183 : 0 : color = "#fdb462";
184 : 0 : break;
185 : 0 : case 14:
186 : 0 : color = "#b3de69";
187 : 0 : break;
188 : 0 : case 15:
189 : 0 : color = "#fccde5";
190 : 0 : break;
191 : 0 : case 16:
192 : 0 : color = "#bc80bd";
193 : 0 : break;
194 : : default: /* gray */
195 : : color = "#999999";
196 : : }
197 : :
198 : 0 : fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
199 : : color);
200 : :
201 : 0 : if (!sese_in_region)
202 : 0 : fprintf (file, " (");
203 : :
204 : 0 : if (bb == region->entry->dest && bb == region->exit->dest)
205 : 0 : fprintf (file, " %d*# ", bb->index);
206 : 0 : else if (bb == region->entry->dest)
207 : 0 : fprintf (file, " %d* ", bb->index);
208 : 0 : else if (bb == region->exit->dest)
209 : 0 : fprintf (file, " %d# ", bb->index);
210 : : else
211 : 0 : fprintf (file, " %d ", bb->index);
212 : :
213 : 0 : fprintf (file, "{lp_%d}", bb->loop_father->num);
214 : :
215 : 0 : if (!sese_in_region)
216 : 0 : fprintf (file, ")");
217 : :
218 : 0 : fprintf (file, "</TD></TR>\n");
219 : 0 : part_of_scop = true;
220 : : }
221 : : }
222 : :
223 : 0 : if (!part_of_scop)
224 : : {
225 : 0 : fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
226 : 0 : fprintf (file, " %d {lp_%d} </TD></TR>\n", bb->index,
227 : 0 : bb->loop_father->num);
228 : : }
229 : 0 : fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
230 : : }
231 : :
232 : 0 : FOR_ALL_BB_FN (bb, cfun)
233 : : {
234 : 0 : edge e;
235 : 0 : edge_iterator ei;
236 : 0 : FOR_EACH_EDGE (e, ei, bb->succs)
237 : 0 : fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
238 : : }
239 : :
240 : 0 : fputs ("}\n\n", file);
241 : :
242 : : /* Enable debugging again. */
243 : 0 : dump_flags = tmp_dump_flags;
244 : 0 : }
245 : :
246 : : /* Display SCoP on stderr. */
247 : :
248 : : DEBUG_FUNCTION void
249 : 0 : dot_sese (sese_l& scop)
250 : : {
251 : 0 : vec<sese_l> scops;
252 : 0 : scops.create (1);
253 : :
254 : 0 : if (scop)
255 : 0 : scops.safe_push (scop);
256 : :
257 : 0 : dot_all_sese (stderr, scops);
258 : :
259 : 0 : scops.release ();
260 : 0 : }
261 : :
262 : : DEBUG_FUNCTION void
263 : 0 : dot_cfg ()
264 : : {
265 : 0 : vec<sese_l> scops;
266 : 0 : scops.create (1);
267 : 0 : dot_all_sese (stderr, scops);
268 : 0 : scops.release ();
269 : 0 : }
270 : :
271 : : /* Returns a COND_EXPR statement when BB has a single predecessor, the
272 : : edge between BB and its predecessor is not a loop exit edge, and
273 : : the last statement of the single predecessor is a COND_EXPR. */
274 : :
275 : : static gcond *
276 : 4146 : single_pred_cond_non_loop_exit (basic_block bb)
277 : : {
278 : 4146 : if (single_pred_p (bb))
279 : : {
280 : 2970 : basic_block pred = single_pred (bb);
281 : :
282 : 8124 : if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
283 : : return NULL;
284 : :
285 : 5706 : return safe_dyn_cast <gcond *> (*gsi_last_bb (pred));
286 : : }
287 : :
288 : : return NULL;
289 : : }
290 : :
291 : : namespace
292 : : {
293 : :
294 : : /* Build the maximal scop containing LOOPs and add it to SCOPS. */
295 : :
296 : : class scop_detection
297 : : {
298 : : public:
299 : 556 : scop_detection () : scops (vNULL) {}
300 : :
301 : 556 : ~scop_detection ()
302 : : {
303 : 556 : scops.release ();
304 : 556 : }
305 : :
306 : : /* A marker for invalid sese_l. */
307 : : static sese_l invalid_sese;
308 : :
309 : : /* Return the SCOPS in this SCOP_DETECTION. */
310 : :
311 : : vec<sese_l>
312 : 556 : get_scops ()
313 : : {
314 : 556 : return scops;
315 : : }
316 : :
317 : : /* Return an sese_l around the LOOP. */
318 : :
319 : : sese_l get_sese (loop_p loop);
320 : :
321 : : /* Merge scops at same loop depth and returns the new sese.
322 : : Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
323 : :
324 : : sese_l merge_sese (sese_l first, sese_l second) const;
325 : :
326 : : /* Build scop outer->inner if possible. */
327 : :
328 : : void build_scop_depth (loop_p loop);
329 : :
330 : : /* Return true when BEGIN is the preheader edge of a loop with a single exit
331 : : END. */
332 : :
333 : : static bool region_has_one_loop (sese_l s);
334 : :
335 : : /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
336 : :
337 : : void add_scop (sese_l s);
338 : :
339 : : /* Returns true if S1 subsumes/surrounds S2. */
340 : : static bool subsumes (sese_l s1, sese_l s2);
341 : :
342 : : /* Remove a SCoP which is subsumed by S1. */
343 : : void remove_subscops (sese_l s1);
344 : :
345 : : /* Returns true if S1 intersects with S2. Since we already know that S1 does
346 : : not subsume S2 or vice-versa, we only check for entry bbs. */
347 : :
348 : : static bool intersects (sese_l s1, sese_l s2);
349 : :
350 : : /* Remove one of the scops when it intersects with any other. */
351 : :
352 : : void remove_intersecting_scops (sese_l s1);
353 : :
354 : : /* Return true when a statement in SCOP cannot be represented by Graphite. */
355 : :
356 : : bool harmful_loop_in_region (sese_l scop) const;
357 : :
358 : : /* Return true only when STMT is simple enough for being handled by Graphite.
359 : : This depends on SCOP, as the parameters are initialized relatively to
360 : : this basic block, the linear functions are initialized based on the
361 : : outermost loop containing STMT inside the SCOP. BB is the place where we
362 : : try to evaluate the STMT. */
363 : :
364 : : bool stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
365 : : basic_block bb) const;
366 : :
367 : : /* Something like "n * m" is not allowed. */
368 : :
369 : : static bool graphite_can_represent_init (tree e);
370 : :
371 : : /* Return true when SCEV can be represented in the polyhedral model.
372 : :
373 : : An expression can be represented, if it can be expressed as an
374 : : affine expression. For loops (i, j) and parameters (m, n) all
375 : : affine expressions are of the form:
376 : :
377 : : x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
378 : :
379 : : 1 i + 20 j + (-2) m + 25
380 : :
381 : : Something like "i * n" or "n * m" is not allowed. */
382 : :
383 : : static bool graphite_can_represent_scev (sese_l scop, tree scev);
384 : :
385 : : /* Return true when EXPR can be represented in the polyhedral model.
386 : :
387 : : This means an expression can be represented, if it is linear with respect
388 : : to the loops and the strides are non parametric. LOOP is the place where
389 : : the expr will be evaluated. SCOP defines the region we analyse. */
390 : :
391 : : static bool graphite_can_represent_expr (sese_l scop, loop_p loop,
392 : : tree expr);
393 : :
394 : : /* Return true if the data references of STMT can be represented by Graphite.
395 : : We try to analyze the data references in a loop contained in the SCOP. */
396 : :
397 : : static bool stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt);
398 : :
399 : : /* Remove the close phi node at GSI and replace its rhs with the rhs
400 : : of PHI. */
401 : :
402 : : static void remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi);
403 : :
404 : : /* Returns true when Graphite can represent LOOP in SCOP.
405 : : FIXME: For the moment, graphite cannot be used on loops that iterate using
406 : : induction variables that wrap. */
407 : :
408 : : static bool can_represent_loop (loop_p loop, sese_l scop);
409 : :
410 : : /* Returns the number of pbbs that are in loops contained in SCOP. */
411 : :
412 : : static int nb_pbbs_in_loops (scop_p scop);
413 : :
414 : : private:
415 : : vec<sese_l> scops;
416 : : };
417 : :
418 : : sese_l scop_detection::invalid_sese (NULL, NULL);
419 : :
420 : : /* Return an sese_l around the LOOP. */
421 : :
422 : : sese_l
423 : 1091 : scop_detection::get_sese (loop_p loop)
424 : : {
425 : 1091 : if (!loop)
426 : 0 : return invalid_sese;
427 : :
428 : 1091 : edge scop_begin = loop_preheader_edge (loop);
429 : 1091 : edge scop_end = single_exit (loop);
430 : 1091 : if (!scop_end || (scop_end->flags & (EDGE_COMPLEX|EDGE_FAKE)))
431 : 210 : return invalid_sese;
432 : :
433 : 881 : return sese_l (scop_begin, scop_end);
434 : : }
435 : :
436 : : /* Merge scops at same loop depth and returns the new sese.
437 : : Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
438 : :
439 : : sese_l
440 : 134 : scop_detection::merge_sese (sese_l first, sese_l second) const
441 : : {
442 : : /* In the trivial case first/second may be NULL. */
443 : 134 : if (!first)
444 : 0 : return second;
445 : 134 : if (!second)
446 : 0 : return first;
447 : :
448 : 134 : DEBUG_PRINT (dp << "[scop-detection] try merging sese s1: ";
449 : : print_sese (dump_file, first);
450 : : dp << "[scop-detection] try merging sese s2: ";
451 : : print_sese (dump_file, second));
452 : :
453 : 134 : auto_bitmap worklist, in_sese_region;
454 : 134 : bitmap_set_bit (worklist, get_entry_bb (first)->index);
455 : 134 : bitmap_set_bit (worklist, get_exit_bb (first)->index);
456 : 134 : bitmap_set_bit (worklist, get_entry_bb (second)->index);
457 : 134 : bitmap_set_bit (worklist, get_exit_bb (second)->index);
458 : 134 : edge entry = NULL, exit = NULL;
459 : :
460 : : /* We can optimize the case of adding a loop entry dest or exit
461 : : src to the worklist (for single-exit loops) by skipping
462 : : directly to the exit dest / entry src. in_sese_region
463 : : doesn't have to cover all blocks in the region but merely
464 : : its border it acts more like a visited bitmap. */
465 : 1633 : do
466 : : {
467 : 1633 : int index = bitmap_clear_first_set_bit (worklist);
468 : 1633 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, index);
469 : 1633 : edge_iterator ei;
470 : 1633 : edge e;
471 : :
472 : : /* With fake exit edges we can end up with no possible exit. */
473 : 1633 : if (index == EXIT_BLOCK)
474 : : {
475 : 2 : DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
476 : 2 : return invalid_sese;
477 : : }
478 : :
479 : 1631 : bitmap_set_bit (in_sese_region, bb->index);
480 : :
481 : 1631 : basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
482 : 3773 : FOR_EACH_EDGE (e, ei, bb->preds)
483 : 2142 : if (e->src == dom
484 : 2142 : && (! entry
485 : 1442 : || dominated_by_p (CDI_DOMINATORS, entry->dest, bb)))
486 : : {
487 : 172 : if (entry
488 : 172 : && ! bitmap_bit_p (in_sese_region, entry->src->index))
489 : 31 : bitmap_set_bit (worklist, entry->src->index);
490 : : entry = e;
491 : : }
492 : 1970 : else if (! bitmap_bit_p (in_sese_region, e->src->index))
493 : 851 : bitmap_set_bit (worklist, e->src->index);
494 : :
495 : 1631 : basic_block pdom = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
496 : 3774 : FOR_EACH_EDGE (e, ei, bb->succs)
497 : 2143 : if (e->dest == pdom
498 : 2143 : && (! exit
499 : 1434 : || dominated_by_p (CDI_POST_DOMINATORS, exit->src, bb)))
500 : : {
501 : 318 : if (exit
502 : 318 : && ! bitmap_bit_p (in_sese_region, exit->dest->index))
503 : 165 : bitmap_set_bit (worklist, exit->dest->index);
504 : : exit = e;
505 : : }
506 : 1825 : else if (! bitmap_bit_p (in_sese_region, e->dest->index))
507 : 949 : bitmap_set_bit (worklist, e->dest->index);
508 : : }
509 : 1631 : while (! bitmap_empty_p (worklist));
510 : :
511 : 132 : sese_l combined (entry, exit);
512 : :
513 : 132 : DEBUG_PRINT (dp << "[merged-sese] s1: "; print_sese (dump_file, combined));
514 : :
515 : 132 : return combined;
516 : 134 : }
517 : :
518 : : /* Print the loop numbers of the loops contained in SESE to FILE. */
519 : :
520 : : static void
521 : 175 : print_sese_loop_numbers (FILE *file, sese_l sese)
522 : : {
523 : 175 : bool first_loop = true;
524 : 393 : for (loop_p nest = sese.entry->dest->loop_father; nest; nest = nest->next)
525 : : {
526 : 246 : if (!loop_in_sese_p (nest, sese))
527 : : break;
528 : :
529 : 1071 : for (auto loop : loops_list (cfun, LI_INCLUDE_ROOT, nest))
530 : : {
531 : 417 : gcc_assert (loop_in_sese_p (loop, sese));
532 : :
533 : 659 : fprintf (file, "%s%d", first_loop ? "" : ", ", loop->num);
534 : 417 : first_loop = false;
535 : 218 : }
536 : : }
537 : 175 : }
538 : :
539 : : /* Build scop outer->inner if possible. */
540 : :
541 : : void
542 : 1183 : scop_detection::build_scop_depth (loop_p loop)
543 : : {
544 : 1183 : sese_l s = invalid_sese;
545 : 1183 : loop = loop->inner;
546 : 2274 : while (loop)
547 : : {
548 : 1091 : sese_l next = get_sese (loop);
549 : 1091 : if (! next
550 : 881 : || harmful_loop_in_region (next))
551 : : {
552 : 627 : if (next)
553 : 417 : DEBUG_PRINT (dp << "[scop-detection] Discarding SCoP on loops ";
554 : : print_sese_loop_numbers (dump_file, next);
555 : : dp << " because of harmful loops\n");
556 : 627 : if (s)
557 : 53 : add_scop (s);
558 : 627 : build_scop_depth (loop);
559 : 627 : s = invalid_sese;
560 : : }
561 : 464 : else if (! s)
562 : : s = next;
563 : : else
564 : : {
565 : 134 : sese_l combined = merge_sese (s, next);
566 : 134 : if (! combined
567 : 132 : || harmful_loop_in_region (combined))
568 : : {
569 : 59 : add_scop (s);
570 : 59 : s = next;
571 : : }
572 : : else
573 : : s = combined;
574 : : }
575 : 1091 : loop = loop->next;
576 : : }
577 : 1183 : if (s)
578 : 277 : add_scop (s);
579 : 1183 : }
580 : :
581 : : /* Returns true when Graphite can represent LOOP in SCOP.
582 : : FIXME: For the moment, graphite cannot be used on loops that iterate using
583 : : induction variables that wrap. */
584 : :
585 : : bool
586 : 1070 : scop_detection::can_represent_loop (loop_p loop, sese_l scop)
587 : : {
588 : 1070 : tree niter;
589 : 1070 : struct tree_niter_desc niter_desc;
590 : :
591 : : /* We can only handle do {} while () style loops correctly. */
592 : 1070 : edge exit = single_exit (loop);
593 : 1070 : if (!exit
594 : 2138 : || !single_pred_p (loop->latch)
595 : 1069 : || exit->src != single_pred (loop->latch)
596 : 2134 : || !empty_block_p (loop->latch))
597 : : {
598 : 19 : DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop shape unsupported.\n");
599 : 19 : return false;
600 : : }
601 : :
602 : 1051 : bool edge_irreducible = (loop_preheader_edge (loop)->flags
603 : 1051 : & EDGE_IRREDUCIBLE_LOOP);
604 : 1051 : if (edge_irreducible)
605 : : {
606 : 1 : DEBUG_PRINT (dp << "[can_represent_loop-fail] "
607 : : "Loop is not a natural loop.\n");
608 : 1 : return false;
609 : : }
610 : :
611 : 1050 : bool niter_is_unconditional = number_of_iterations_exit (loop,
612 : : single_exit (loop),
613 : : &niter_desc, false);
614 : :
615 : 1050 : if (!niter_is_unconditional)
616 : : {
617 : 5 : DEBUG_PRINT (dp << "[can_represent_loop-fail] "
618 : : "Loop niter not unconditional.\n"
619 : : "Condition: " << niter_desc.assumptions << "\n");
620 : 5 : return false;
621 : : }
622 : :
623 : 1045 : niter = number_of_latch_executions (loop);
624 : 1045 : if (!niter)
625 : : {
626 : 0 : DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop niter unknown.\n");
627 : 0 : return false;
628 : : }
629 : 1045 : if (!niter_desc.control.no_overflow)
630 : : {
631 : 1 : DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop niter can overflow.\n");
632 : 1 : return false;
633 : : }
634 : :
635 : 1044 : bool undetermined_coefficients = chrec_contains_undetermined (niter);
636 : 1044 : if (undetermined_coefficients)
637 : : {
638 : 0 : DEBUG_PRINT (dp << "[can_represent_loop-fail] "
639 : : "Loop niter chrec contains undetermined "
640 : : "coefficients.\n");
641 : 0 : return false;
642 : : }
643 : :
644 : 1044 : bool can_represent_expr = graphite_can_represent_expr (scop, loop, niter);
645 : 1044 : if (!can_represent_expr)
646 : : {
647 : 14 : DEBUG_PRINT (dp << "[can_represent_loop-fail] "
648 : : << "Loop niter expression cannot be represented: "
649 : : << niter << "\n");
650 : 14 : return false;
651 : : }
652 : :
653 : : return true;
654 : 1070 : }
655 : :
656 : : /* Return true when BEGIN is the preheader edge of a loop with a single exit
657 : : END. */
658 : :
659 : : bool
660 : 389 : scop_detection::region_has_one_loop (sese_l s)
661 : : {
662 : 389 : edge begin = s.entry;
663 : 389 : edge end = s.exit;
664 : : /* Check for a single perfectly nested loop. */
665 : 389 : if (begin->dest->loop_father->inner)
666 : : return false;
667 : :
668 : : /* Otherwise, check whether we have adjacent loops. */
669 : 227 : return (single_pred_p (end->src)
670 : 227 : && begin->dest->loop_father == single_pred (end->src)->loop_father);
671 : : }
672 : :
673 : : /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
674 : :
675 : : void
676 : 389 : scop_detection::add_scop (sese_l s)
677 : : {
678 : 389 : gcc_assert (s);
679 : :
680 : : /* If the exit edge is fake discard the SCoP for now as we're removing the
681 : : fake edges again after analysis. */
682 : 389 : if (s.exit->flags & EDGE_FAKE)
683 : : {
684 : 0 : DEBUG_PRINT (dp << "[scop-detection-fail] Discarding infinite loop SCoP: ";
685 : : print_sese (dump_file, s));
686 : 0 : return;
687 : : }
688 : :
689 : : /* Include the BB with the loop-closed SSA PHI nodes, we need this
690 : : block in the region for code-generating out-of-SSA copies.
691 : : canonicalize_loop_closed_ssa makes sure that is in proper shape. */
692 : 389 : if (s.exit->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
693 : 389 : && loop_exit_edge_p (s.exit->src->loop_father, s.exit))
694 : : {
695 : 1161 : gcc_assert (single_pred_p (s.exit->dest)
696 : : && single_succ_p (s.exit->dest)
697 : : && sese_trivially_empty_bb_p (s.exit->dest));
698 : 387 : s.exit = single_succ_edge (s.exit->dest);
699 : : }
700 : :
701 : : /* Do not add scops with only one loop. */
702 : 389 : if (region_has_one_loop (s))
703 : : {
704 : 185 : DEBUG_PRINT (dp << "[scop-detection-fail] Discarding one loop SCoP: ";
705 : : print_sese (dump_file, s));
706 : 185 : return;
707 : : }
708 : :
709 : 204 : if (get_exit_bb (s) == EXIT_BLOCK_PTR_FOR_FN (cfun))
710 : : {
711 : 0 : DEBUG_PRINT (dp << "[scop-detection-fail] "
712 : : << "Discarding SCoP exiting to return: ";
713 : : print_sese (dump_file, s));
714 : 0 : return;
715 : : }
716 : :
717 : : /* Remove all the scops which are subsumed by s. */
718 : 204 : remove_subscops (s);
719 : :
720 : : /* Remove intersecting scops. FIXME: It will be a good idea to keep
721 : : the non-intersecting part of the scop already in the list. */
722 : 204 : remove_intersecting_scops (s);
723 : :
724 : 204 : scops.safe_push (s);
725 : 204 : DEBUG_PRINT (dp << "[scop-detection] Adding SCoP: "; print_sese (dump_file, s));
726 : :
727 : 204 : if (dump_file && dump_flags & TDF_DETAILS)
728 : : {
729 : 100 : fprintf (dump_file, "Loops in SCoP: ");
730 : 100 : print_sese_loop_numbers (dump_file, s);
731 : 100 : fprintf (dump_file, "\n");
732 : : }
733 : : }
734 : :
735 : : /* Return true when a statement in SCOP cannot be represented by Graphite. */
736 : :
737 : : bool
738 : 1013 : scop_detection::harmful_loop_in_region (sese_l scop) const
739 : : {
740 : 1013 : basic_block exit_bb = get_exit_bb (scop);
741 : 1013 : basic_block entry_bb = get_entry_bb (scop);
742 : :
743 : 1013 : DEBUG_PRINT (dp << "[checking-harmful-bbs] ";
744 : : print_sese (dump_file, scop));
745 : 1013 : gcc_assert (dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb));
746 : :
747 : 1013 : auto_vec<basic_block> worklist;
748 : 1013 : auto_bitmap loops;
749 : :
750 : 1013 : worklist.safe_push (entry_bb);
751 : 5955 : while (! worklist.is_empty ())
752 : : {
753 : 4281 : basic_block bb = worklist.pop ();
754 : 4281 : DEBUG_PRINT (dp << "Visiting bb_" << bb->index << "\n");
755 : :
756 : : /* The basic block should not be part of an irreducible loop. */
757 : 4281 : if (bb->flags & BB_IRREDUCIBLE_LOOP)
758 : : {
759 : 2 : DEBUG_PRINT (dp << "[scop-detection-fail] Found bb in irreducible "
760 : : "loop.\n");
761 : :
762 : 2 : return true;
763 : : }
764 : :
765 : : /* Check for unstructured control flow: CFG not generated by structured
766 : : if-then-else. */
767 : 4279 : if (bb->succs->length () > 1)
768 : : {
769 : 1729 : edge e;
770 : 1729 : edge_iterator ei;
771 : 5197 : FOR_EACH_EDGE (e, ei, bb->succs)
772 : 3476 : if (!dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)
773 : 3476 : && !dominated_by_p (CDI_DOMINATORS, e->dest, bb))
774 : : {
775 : 8 : DEBUG_PRINT (dp << "[scop-detection-fail] Found unstructured "
776 : : "control flow.\n");
777 : 8 : return true;
778 : : }
779 : : }
780 : :
781 : : /* Collect all loops in the current region. */
782 : 4271 : loop_p loop = bb->loop_father;
783 : 4271 : if (loop_in_sese_p (loop, scop))
784 : 3936 : bitmap_set_bit (loops, loop->num);
785 : :
786 : : /* Check for harmful statements in basic blocks part of the region. */
787 : 8542 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
788 : 14436 : !gsi_end_p (gsi); gsi_next (&gsi))
789 : 10507 : if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb))
790 : : {
791 : 342 : DEBUG_PRINT (dp << "[scop-detection-fail] "
792 : : "Found harmful statement.\n");
793 : 342 : return true;
794 : : }
795 : :
796 : 3929 : for (basic_block dom = first_dom_son (CDI_DOMINATORS, bb);
797 : 8046 : dom;
798 : 4117 : dom = next_dom_son (CDI_DOMINATORS, dom))
799 : 4117 : if (dom != scop.exit->dest)
800 : 3411 : worklist.safe_push (dom);
801 : : }
802 : :
803 : : /* Go through all loops and check that they are still valid in the combined
804 : : scop. */
805 : 661 : unsigned j;
806 : 661 : bitmap_iterator bi;
807 : 1621 : EXECUTE_IF_SET_IN_BITMAP (loops, 0, j, bi)
808 : : {
809 : 1082 : loop_p loop = (*current_loops->larray)[j];
810 : 1082 : gcc_assert (loop->num == (int) j);
811 : :
812 : : /* Check if the loop nests are to be optimized for speed. */
813 : 1082 : if (! loop->inner
814 : 1082 : && ! optimize_loop_for_speed_p (loop))
815 : : {
816 : 12 : DEBUG_PRINT (dp << "[scop-detection-fail] loop_"
817 : : << loop->num << " is not on a hot path.\n");
818 : 12 : return true;
819 : : }
820 : :
821 : 1070 : if (! can_represent_loop (loop, scop))
822 : : {
823 : 40 : DEBUG_PRINT (dp << "[scop-detection-fail] cannot represent loop_"
824 : : << loop->num << "\n");
825 : 40 : return true;
826 : : }
827 : :
828 : : /* Check if all loop nests have at least one data reference.
829 : : ??? This check is expensive and loops premature at this point.
830 : : If important to retain we can pre-compute this for all innermost
831 : : loops and reject those when we build a SESE region for a loop
832 : : during SESE discovery. */
833 : 1030 : if (! loop->inner
834 : 1030 : && ! loop_nest_has_data_refs (loop))
835 : : {
836 : 70 : DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
837 : : << " does not have any data reference.\n");
838 : 70 : return true;
839 : : }
840 : 1426 : DEBUG_PRINT (dp << "[scop-detection] loop_" << loop->num << " is harmless.\n");
841 : : }
842 : :
843 : : return false;
844 : 1013 : }
845 : :
846 : : /* Returns true if S1 subsumes/surrounds S2. */
847 : : bool
848 : 15 : scop_detection::subsumes (sese_l s1, sese_l s2)
849 : : {
850 : 15 : if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
851 : 15 : get_entry_bb (s1))
852 : 15 : && dominated_by_p (CDI_POST_DOMINATORS, s2.exit->dest,
853 : 0 : s1.exit->dest))
854 : : return true;
855 : : return false;
856 : : }
857 : :
858 : : /* Remove a SCoP which is subsumed by S1. */
859 : : void
860 : 204 : scop_detection::remove_subscops (sese_l s1)
861 : : {
862 : 204 : int j;
863 : 204 : sese_l *s2;
864 : 231 : FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
865 : : {
866 : 15 : if (subsumes (s1, *s2))
867 : : {
868 : 0 : DEBUG_PRINT (dp << "Removing sub-SCoP";
869 : : print_sese (dump_file, *s2));
870 : 0 : scops.unordered_remove (j);
871 : : }
872 : : }
873 : 204 : }
874 : :
875 : : /* Returns true if S1 intersects with S2. Since we already know that S1 does
876 : : not subsume S2 or vice-versa, we only check for entry bbs. */
877 : :
878 : : bool
879 : 15 : scop_detection::intersects (sese_l s1, sese_l s2)
880 : : {
881 : 15 : if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
882 : 15 : get_entry_bb (s1))
883 : 15 : && !dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
884 : 0 : get_exit_bb (s1)))
885 : : return true;
886 : 15 : if ((s1.exit == s2.entry) || (s2.exit == s1.entry))
887 : : return true;
888 : :
889 : : return false;
890 : : }
891 : :
892 : : /* Remove one of the scops when it intersects with any other. */
893 : :
894 : : void
895 : 204 : scop_detection::remove_intersecting_scops (sese_l s1)
896 : : {
897 : 204 : int j;
898 : 204 : sese_l *s2;
899 : 231 : FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
900 : : {
901 : 15 : if (intersects (s1, *s2))
902 : : {
903 : 0 : DEBUG_PRINT (dp << "Removing intersecting SCoP";
904 : : print_sese (dump_file, *s2);
905 : : dp << "Intersects with:";
906 : : print_sese (dump_file, s1));
907 : 0 : scops.unordered_remove (j);
908 : : }
909 : : }
910 : 204 : }
911 : :
912 : : /* Something like "n * m" is not allowed. */
913 : :
914 : : bool
915 : 12523 : scop_detection::graphite_can_represent_init (tree e)
916 : : {
917 : 12659 : switch (TREE_CODE (e))
918 : : {
919 : 4071 : case POLYNOMIAL_CHREC:
920 : 4071 : return graphite_can_represent_init (CHREC_LEFT (e))
921 : 8135 : && graphite_can_represent_init (CHREC_RIGHT (e));
922 : :
923 : 38 : case MULT_EXPR:
924 : 38 : if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
925 : 38 : return graphite_can_represent_init (TREE_OPERAND (e, 0))
926 : 38 : && tree_fits_shwi_p (TREE_OPERAND (e, 1));
927 : : else
928 : 0 : return graphite_can_represent_init (TREE_OPERAND (e, 1))
929 : 0 : && tree_fits_shwi_p (TREE_OPERAND (e, 0));
930 : :
931 : 355 : case PLUS_EXPR:
932 : 355 : case POINTER_PLUS_EXPR:
933 : 355 : case MINUS_EXPR:
934 : 355 : return graphite_can_represent_init (TREE_OPERAND (e, 0))
935 : 355 : && graphite_can_represent_init (TREE_OPERAND (e, 1));
936 : :
937 : 136 : case NEGATE_EXPR:
938 : 136 : case BIT_NOT_EXPR:
939 : 136 : CASE_CONVERT:
940 : 136 : case NON_LVALUE_EXPR:
941 : 136 : return graphite_can_represent_init (TREE_OPERAND (e, 0));
942 : :
943 : : default:
944 : : break;
945 : : }
946 : :
947 : : return true;
948 : : }
949 : :
950 : : /* Return true when SCEV can be represented in the polyhedral model.
951 : :
952 : : An expression can be represented, if it can be expressed as an
953 : : affine expression. For loops (i, j) and parameters (m, n) all
954 : : affine expressions are of the form:
955 : :
956 : : x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
957 : :
958 : : 1 i + 20 j + (-2) m + 25
959 : :
960 : : Something like "i * n" or "n * m" is not allowed. */
961 : :
962 : : bool
963 : 7787 : scop_detection::graphite_can_represent_scev (sese_l scop, tree scev)
964 : : {
965 : 11878 : if (chrec_contains_undetermined (scev))
966 : : return false;
967 : :
968 : 11724 : switch (TREE_CODE (scev))
969 : : {
970 : 462 : case NEGATE_EXPR:
971 : 462 : case BIT_NOT_EXPR:
972 : 462 : CASE_CONVERT:
973 : 462 : case NON_LVALUE_EXPR:
974 : 462 : return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0));
975 : :
976 : 579 : case PLUS_EXPR:
977 : 579 : case POINTER_PLUS_EXPR:
978 : 579 : case MINUS_EXPR:
979 : 579 : return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
980 : 579 : && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
981 : :
982 : 27 : case MULT_EXPR:
983 : 43 : return !CONVERT_EXPR_P (TREE_OPERAND (scev, 0))
984 : 16 : && !CONVERT_EXPR_P (TREE_OPERAND (scev, 1))
985 : 32 : && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
986 : 16 : && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
987 : 16 : && graphite_can_represent_init (scev)
988 : 16 : && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
989 : 43 : && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
990 : :
991 : 3706 : case POLYNOMIAL_CHREC:
992 : : /* Check for constant strides. With a non constant stride of
993 : : 'n' we would have a value of 'iv * n'. Also check that the
994 : : initial value can represented: for example 'n * m' cannot be
995 : : represented. */
996 : 3706 : gcc_assert (loop_in_sese_p (get_loop (cfun,
997 : : CHREC_VARIABLE (scev)), scop));
998 : 3706 : if (!evolution_function_right_is_integer_cst (scev)
999 : 3706 : || !graphite_can_represent_init (scev))
1000 : 77 : return false;
1001 : 3629 : return graphite_can_represent_scev (scop, CHREC_LEFT (scev));
1002 : :
1003 : : case ADDR_EXPR:
1004 : : /* We cannot encode addresses for ISL. */
1005 : : return false;
1006 : :
1007 : 6950 : default:
1008 : 6950 : break;
1009 : : }
1010 : :
1011 : : /* Only affine functions can be represented. */
1012 : 6950 : if (tree_contains_chrecs (scev, NULL) || !scev_is_linear_expression (scev))
1013 : 3 : return false;
1014 : :
1015 : : return true;
1016 : : }
1017 : :
1018 : : /* Return true when EXPR can be represented in the polyhedral model.
1019 : :
1020 : : This means an expression can be represented, if it is linear with respect to
1021 : : the loops and the strides are non parametric. LOOP is the place where the
1022 : : expr will be evaluated. SCOP defines the region we analyse. */
1023 : :
1024 : : bool
1025 : 4049 : scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop,
1026 : : tree expr)
1027 : : {
1028 : 4049 : tree scev = cached_scalar_evolution_in_region (scop, loop, expr);
1029 : 4049 : bool can_represent = graphite_can_represent_scev (scop, scev);
1030 : :
1031 : 4049 : if (!can_represent)
1032 : : {
1033 : 135 : if (dump_file)
1034 : : {
1035 : 17 : fprintf (dump_file,
1036 : : "[graphite_can_represent_expr] Cannot represent scev \"");
1037 : 17 : print_generic_expr (dump_file, scev, TDF_SLIM);
1038 : 17 : fprintf (dump_file, "\" of expression ");
1039 : 17 : print_generic_expr (dump_file, expr, TDF_SLIM);
1040 : 17 : fprintf (dump_file, " in loop %d\n", loop->num);
1041 : : }
1042 : : }
1043 : 4049 : return can_represent;
1044 : : }
1045 : :
1046 : : /* Return true if the data references of STMT can be represented by Graphite.
1047 : : We try to analyze the data references in a loop contained in the SCOP. */
1048 : :
1049 : : bool
1050 : 10300 : scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt)
1051 : : {
1052 : 10300 : edge nest = scop.entry;
1053 : 10300 : loop_p loop = loop_containing_stmt (stmt);
1054 : 10300 : if (!loop_in_sese_p (loop, scop))
1055 : 143 : loop = NULL;
1056 : :
1057 : 10300 : auto_vec<data_reference_p> drs;
1058 : 10300 : if (! graphite_find_data_references_in_stmt (nest, loop, stmt, &drs))
1059 : : {
1060 : 5 : DEBUG_PRINT (dp << "[stmt_has_simple_data_refs_p] "
1061 : : "Unanalyzable statement.\n");
1062 : 5 : return false;
1063 : : }
1064 : :
1065 : : int j;
1066 : : data_reference_p dr;
1067 : 16304 : FOR_EACH_VEC_ELT (drs, j, dr)
1068 : : {
1069 : 8858 : for (unsigned i = 0; i < DR_NUM_DIMENSIONS (dr); ++i)
1070 : 2562 : if (! graphite_can_represent_scev (scop, DR_ACCESS_FN (dr, i)))
1071 : : {
1072 : 110 : DEBUG_PRINT (dp << "[stmt_has_simple_data_refs_p] "
1073 : : "Cannot represent access function SCEV: "
1074 : : << DR_ACCESS_FN (dr, i) << "\n");
1075 : 110 : return false;
1076 : : }
1077 : : }
1078 : :
1079 : : return true;
1080 : 10300 : }
1081 : :
1082 : : /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1083 : : Calls have side-effects, except those to const or pure
1084 : : functions. */
1085 : :
1086 : : static bool
1087 : 10382 : stmt_has_side_effects (gimple *stmt)
1088 : : {
1089 : 10382 : if (gimple_has_volatile_ops (stmt)
1090 : 10362 : || (gimple_code (stmt) == GIMPLE_CALL
1091 : 92 : && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
1092 : 19100 : || (gimple_code (stmt) == GIMPLE_ASM))
1093 : : {
1094 : 82 : DEBUG_PRINT (dp << "[scop-detection-fail] "
1095 : : << "Statement has side-effects:\n";
1096 : : print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
1097 : 82 : return true;
1098 : : }
1099 : : return false;
1100 : : }
1101 : :
1102 : : /* Return true only when STMT is simple enough for being handled by Graphite.
1103 : : This depends on SCOP, as the parameters are initialized relatively to
1104 : : this basic block, the linear functions are initialized based on the outermost
1105 : : loop containing STMT inside the SCOP. BB is the place where we try to
1106 : : evaluate the STMT. */
1107 : :
1108 : : bool
1109 : 10507 : scop_detection::stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
1110 : : basic_block bb) const
1111 : : {
1112 : 10507 : gcc_assert (scop);
1113 : :
1114 : 10507 : if (is_gimple_debug (stmt))
1115 : : return true;
1116 : :
1117 : 10382 : if (stmt_has_side_effects (stmt))
1118 : : return false;
1119 : :
1120 : 10300 : if (!stmt_has_simple_data_refs_p (scop, stmt))
1121 : : {
1122 : 115 : DEBUG_PRINT (dp << "[scop-detection-fail] "
1123 : : << "Graphite cannot handle data-refs in stmt:\n";
1124 : : print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS););
1125 : 115 : return false;
1126 : : }
1127 : :
1128 : 10185 : switch (gimple_code (stmt))
1129 : : {
1130 : : case GIMPLE_LABEL:
1131 : : return true;
1132 : :
1133 : 1567 : case GIMPLE_COND:
1134 : 1567 : {
1135 : : /* We can handle all binary comparisons. Inequalities are
1136 : : also supported as they can be represented with union of
1137 : : polyhedra. */
1138 : 1567 : enum tree_code code = gimple_cond_code (stmt);
1139 : 1018 : if (!(code == LT_EXPR
1140 : 1567 : || code == GT_EXPR
1141 : 1155 : || code == LE_EXPR
1142 : 1155 : || code == GE_EXPR
1143 : : || code == EQ_EXPR
1144 : : || code == NE_EXPR))
1145 : : {
1146 : 0 : DEBUG_PRINT (dp << "[scop-detection-fail] "
1147 : : << "Graphite cannot handle cond stmt:\n";
1148 : : print_gimple_stmt (dump_file, stmt, 0,
1149 : : TDF_VOPS | TDF_MEMSYMS));
1150 : 0 : return false;
1151 : : }
1152 : :
1153 : 1567 : loop_p loop = bb->loop_father;
1154 : 4436 : for (unsigned i = 0; i < 2; ++i)
1155 : : {
1156 : 3005 : tree op = gimple_op (stmt, i);
1157 : 3005 : if (!graphite_can_represent_expr (scop, loop, op))
1158 : : {
1159 : 121 : DEBUG_PRINT (dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmt,
1160 : : "[scop-detection-fail] "
1161 : : "Graphite cannot represent cond "
1162 : : "stmt operator expression.\n"));
1163 : 121 : DEBUG_PRINT (dp << op << "\n");
1164 : 121 : return false;
1165 : : }
1166 : :
1167 : 2884 : if (! INTEGRAL_TYPE_P (TREE_TYPE (op)))
1168 : : {
1169 : 15 : DEBUG_PRINT (dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmt,
1170 : : "[scop-detection-fail] "
1171 : : "Graphite cannot represent cond "
1172 : : "statement operator. "
1173 : : "Type must be integral.\n"));
1174 : 15 : return false;
1175 : : }
1176 : : }
1177 : :
1178 : : return true;
1179 : : }
1180 : :
1181 : 8601 : case GIMPLE_ASSIGN:
1182 : 8601 : case GIMPLE_CALL:
1183 : 8601 : {
1184 : 8601 : tree op, lhs = gimple_get_lhs (stmt);
1185 : 8601 : ssa_op_iter i;
1186 : : /* If we are not going to instantiate the stmt do not require
1187 : : its operands to be instantiatable at this point. */
1188 : 8601 : if (lhs
1189 : 8601 : && TREE_CODE (lhs) == SSA_NAME
1190 : 16336 : && scev_analyzable_p (lhs, scop))
1191 : : return true;
1192 : : /* Verify that if we can analyze operands at their def site we
1193 : : also can represent them when analyzed at their uses. */
1194 : 9714 : FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
1195 : 6080 : if (scev_analyzable_p (op, scop)
1196 : 9212 : && chrec_contains_undetermined
1197 : 3132 : (cached_scalar_evolution_in_region (scop,
1198 : : bb->loop_father, op)))
1199 : : {
1200 : 2 : DEBUG_PRINT (dp << "[scop-detection-fail] "
1201 : : << "Graphite cannot code-gen stmt:\n";
1202 : : print_gimple_stmt (dump_file, stmt, 0,
1203 : : TDF_VOPS | TDF_MEMSYMS));
1204 : 2 : return false;
1205 : : }
1206 : : return true;
1207 : : }
1208 : :
1209 : 7 : default:
1210 : : /* These nodes cut a new scope. */
1211 : 7 : DEBUG_PRINT (
1212 : : dp << "[scop-detection-fail] "
1213 : : << "Gimple stmt not handled in Graphite:\n";
1214 : : print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
1215 : : return false;
1216 : : }
1217 : : }
1218 : :
1219 : : /* Returns the number of pbbs that are in loops contained in SCOP. */
1220 : :
1221 : : int
1222 : 193 : scop_detection::nb_pbbs_in_loops (scop_p scop)
1223 : : {
1224 : 193 : int i;
1225 : 193 : poly_bb_p pbb;
1226 : 193 : int res = 0;
1227 : :
1228 : 822 : FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1229 : 629 : if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), scop->scop_info->region))
1230 : 534 : res++;
1231 : :
1232 : 193 : return res;
1233 : : }
1234 : :
1235 : : /* Assigns the parameter NAME an index in REGION. */
1236 : :
1237 : : static void
1238 : 301 : assign_parameter_index_in_region (tree name, sese_info_p region)
1239 : : {
1240 : 301 : gcc_assert (TREE_CODE (name) == SSA_NAME
1241 : : && ! defined_in_sese_p (name, region->region));
1242 : : int i;
1243 : : tree p;
1244 : 483 : FOR_EACH_VEC_ELT (region->params, i, p)
1245 : 346 : if (p == name)
1246 : 301 : return;
1247 : :
1248 : 137 : region->params.safe_push (name);
1249 : : }
1250 : :
1251 : : /* In the context of sese S, scan the expression E and translate it to
1252 : : a linear expression C. When parsing a symbolic multiplication, K
1253 : : represents the constant multiplier of an expression containing
1254 : : parameters. */
1255 : :
1256 : : static void
1257 : 1432 : scan_tree_for_params (sese_info_p s, tree e)
1258 : : {
1259 : 2897 : if (e == chrec_dont_know)
1260 : : return;
1261 : :
1262 : 2897 : switch (TREE_CODE (e))
1263 : : {
1264 : 1145 : case POLYNOMIAL_CHREC:
1265 : 1145 : scan_tree_for_params (s, CHREC_LEFT (e));
1266 : 1145 : break;
1267 : :
1268 : 3 : case MULT_EXPR:
1269 : 3 : if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
1270 : 3 : scan_tree_for_params (s, TREE_OPERAND (e, 0));
1271 : : else
1272 : 0 : scan_tree_for_params (s, TREE_OPERAND (e, 1));
1273 : : break;
1274 : :
1275 : 162 : case PLUS_EXPR:
1276 : 162 : case POINTER_PLUS_EXPR:
1277 : 162 : case MINUS_EXPR:
1278 : 162 : scan_tree_for_params (s, TREE_OPERAND (e, 0));
1279 : 162 : scan_tree_for_params (s, TREE_OPERAND (e, 1));
1280 : 162 : break;
1281 : :
1282 : 155 : case NEGATE_EXPR:
1283 : 155 : case BIT_NOT_EXPR:
1284 : 155 : CASE_CONVERT:
1285 : 155 : case NON_LVALUE_EXPR:
1286 : 155 : scan_tree_for_params (s, TREE_OPERAND (e, 0));
1287 : 155 : break;
1288 : :
1289 : 301 : case SSA_NAME:
1290 : 301 : assign_parameter_index_in_region (e, s);
1291 : 301 : break;
1292 : :
1293 : : case INTEGER_CST:
1294 : : case ADDR_EXPR:
1295 : : case REAL_CST:
1296 : : case COMPLEX_CST:
1297 : : case VECTOR_CST:
1298 : : break;
1299 : :
1300 : 0 : default:
1301 : 0 : gcc_unreachable ();
1302 : 1432 : break;
1303 : : }
1304 : : }
1305 : :
1306 : : /* Find parameters with respect to REGION in BB. We are looking in memory
1307 : : access functions, conditions and loop bounds. */
1308 : :
1309 : : static void
1310 : 629 : find_params_in_bb (sese_info_p region, gimple_poly_bb_p gbb)
1311 : : {
1312 : : /* Find parameters in the access functions of data references. */
1313 : 629 : int i;
1314 : 629 : data_reference_p dr;
1315 : 2389 : FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb), i, dr)
1316 : 3273 : for (unsigned j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
1317 : 949 : scan_tree_for_params (region, DR_ACCESS_FN (dr, j));
1318 : :
1319 : : /* Find parameters in conditional statements. */
1320 : : gimple *stmt;
1321 : 720 : FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
1322 : : {
1323 : 91 : loop_p loop = gimple_bb (stmt)->loop_father;
1324 : 91 : tree lhs = cached_scalar_evolution_in_region (region->region, loop,
1325 : : gimple_cond_lhs (stmt));
1326 : 91 : tree rhs = cached_scalar_evolution_in_region (region->region, loop,
1327 : : gimple_cond_rhs (stmt));
1328 : 91 : gcc_assert (!chrec_contains_undetermined (lhs)
1329 : : && !chrec_contains_undetermined (rhs));
1330 : :
1331 : 91 : scan_tree_for_params (region, lhs);
1332 : 91 : scan_tree_for_params (region, rhs);
1333 : : }
1334 : 629 : }
1335 : :
1336 : : /* Record the parameters used in the SCOP BBs. A variable is a parameter
1337 : : in a scop if it does not vary during the execution of that scop. */
1338 : :
1339 : : static void
1340 : 193 : find_scop_parameters (scop_p scop)
1341 : : {
1342 : 193 : unsigned i;
1343 : 193 : sese_info_p region = scop->scop_info;
1344 : :
1345 : : /* Parameters used in loop bounds are processed during gather_bbs. */
1346 : :
1347 : : /* Find the parameters used in data accesses. */
1348 : 193 : poly_bb_p pbb;
1349 : 822 : FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1350 : 629 : find_params_in_bb (region, PBB_BLACK_BOX (pbb));
1351 : :
1352 : 193 : int nbp = sese_nb_params (region);
1353 : 193 : scop_set_nb_params (scop, nbp);
1354 : 193 : }
1355 : :
1356 : : static void
1357 : 829 : add_write (vec<tree> *writes, tree def)
1358 : : {
1359 : 829 : writes->safe_push (def);
1360 : 829 : DEBUG_PRINT (dp << "Adding scalar write: ";
1361 : : print_generic_expr (dump_file, def);
1362 : : dp << "\nFrom stmt: ";
1363 : : print_gimple_stmt (dump_file,
1364 : : SSA_NAME_DEF_STMT (def), 0));
1365 : 829 : }
1366 : :
1367 : : static void
1368 : 659 : add_read (vec<scalar_use> *reads, tree use, gimple *use_stmt)
1369 : : {
1370 : 659 : DEBUG_PRINT (dp << "Adding scalar read: ";
1371 : : print_generic_expr (dump_file, use);
1372 : : dp << "\nFrom stmt: ";
1373 : : print_gimple_stmt (dump_file, use_stmt, 0));
1374 : 659 : reads->safe_push (std::make_pair (use_stmt, use));
1375 : 659 : }
1376 : :
1377 : :
1378 : : /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1379 : :
1380 : : static void
1381 : 3054 : build_cross_bb_scalars_def (scop_p scop, tree def, basic_block def_bb,
1382 : : vec<tree> *writes)
1383 : : {
1384 : 3054 : if (!is_gimple_reg (def))
1385 : 364 : return;
1386 : :
1387 : 2690 : bool scev_analyzable = scev_analyzable_p (def, scop->scop_info->region);
1388 : :
1389 : 2690 : gimple *use_stmt;
1390 : 2690 : imm_use_iterator imm_iter;
1391 : 6113 : FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
1392 : : /* Do not gather scalar variables that can be analyzed by SCEV as they can
1393 : : be generated out of the induction variables. */
1394 : 3575 : if ((! scev_analyzable
1395 : : /* But gather SESE liveouts as we otherwise fail to rewrite their
1396 : : exit PHIs. */
1397 : 2668 : || ! bb_in_sese_p (gimple_bb (use_stmt), scop->scop_info->region))
1398 : 3576 : && (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt)))
1399 : : {
1400 : 152 : add_write (writes, def);
1401 : 152 : break;
1402 : 2690 : }
1403 : : }
1404 : :
1405 : : /* Record USE if it is defined in other bbs different than USE_STMT
1406 : : in the SCOP. */
1407 : :
1408 : : static void
1409 : 4969 : build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt,
1410 : : vec<scalar_use> *reads)
1411 : : {
1412 : 4969 : if (!is_gimple_reg (use))
1413 : : return;
1414 : :
1415 : : /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1416 : : generated out of the induction variables. */
1417 : 4969 : if (scev_analyzable_p (use, scop->scop_info->region))
1418 : : return;
1419 : :
1420 : 966 : gimple *def_stmt = SSA_NAME_DEF_STMT (use);
1421 : 966 : if (gimple_bb (def_stmt) != gimple_bb (use_stmt))
1422 : 110 : add_read (reads, use, use_stmt);
1423 : : }
1424 : :
1425 : : /* Generates a polyhedral black box only if the bb contains interesting
1426 : : information. */
1427 : :
1428 : : static gimple_poly_bb_p
1429 : 2073 : try_generate_gimple_bb (scop_p scop, basic_block bb)
1430 : : {
1431 : 2073 : vec<data_reference_p> drs = vNULL;
1432 : 2073 : vec<tree> writes = vNULL;
1433 : 2073 : vec<scalar_use> reads = vNULL;
1434 : :
1435 : 2073 : sese_l region = scop->scop_info->region;
1436 : 2073 : edge nest = region.entry;
1437 : 2073 : loop_p loop = bb->loop_father;
1438 : 2073 : if (!loop_in_sese_p (loop, region))
1439 : 371 : loop = NULL;
1440 : :
1441 : 7839 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1442 : 3693 : gsi_next (&gsi))
1443 : : {
1444 : 3693 : gimple *stmt = gsi_stmt (gsi);
1445 : 3693 : if (is_gimple_debug (stmt))
1446 : 51 : continue;
1447 : :
1448 : 3642 : graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
1449 : :
1450 : 3642 : tree def = gimple_get_lhs (stmt);
1451 : 3642 : if (def)
1452 : 3054 : build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), &writes);
1453 : :
1454 : 3642 : ssa_op_iter iter;
1455 : 3642 : tree use;
1456 : 8611 : FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1457 : 4969 : build_cross_bb_scalars_use (scop, use, stmt, &reads);
1458 : : }
1459 : :
1460 : : /* Handle defs and uses in PHIs. Those need special treatment given
1461 : : that we have to present ISL with sth that looks like we've rewritten
1462 : : the IL out-of-SSA. */
1463 : 4308 : for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
1464 : 2235 : gsi_next (&psi))
1465 : : {
1466 : 2235 : gphi *phi = psi.phi ();
1467 : 2235 : tree res = gimple_phi_result (phi);
1468 : 2235 : if (virtual_operand_p (res)
1469 : 2235 : || scev_analyzable_p (res, scop->scop_info->region))
1470 : 1946 : continue;
1471 : : /* To simulate out-of-SSA the block containing the PHI node has
1472 : : reads of the PHI destination. And to preserve SSA dependences
1473 : : we also write to it (the out-of-SSA decl and the SSA result
1474 : : are coalesced for dependence purposes which is good enough). */
1475 : 289 : add_read (&reads, res, phi);
1476 : 289 : add_write (&writes, res);
1477 : : }
1478 : 2073 : basic_block bb_for_succs = bb;
1479 : 2073 : if (bb_for_succs == bb_for_succs->loop_father->latch
1480 : 534 : && bb_in_sese_p (bb_for_succs, scop->scop_info->region)
1481 : 2607 : && sese_trivially_empty_bb_p (bb_for_succs))
1482 : : bb_for_succs = NULL;
1483 : 4146 : while (bb_for_succs)
1484 : : {
1485 : 2073 : basic_block latch = NULL;
1486 : 2073 : edge_iterator ei;
1487 : 2073 : edge e;
1488 : 4734 : FOR_EACH_EDGE (e, ei, bb_for_succs->succs)
1489 : : {
1490 : 5925 : for (gphi_iterator psi = gsi_start_phis (e->dest); !gsi_end_p (psi);
1491 : 3264 : gsi_next (&psi))
1492 : : {
1493 : 3264 : gphi *phi = psi.phi ();
1494 : 3264 : tree res = gimple_phi_result (phi);
1495 : 6528 : if (virtual_operand_p (res))
1496 : 1325 : continue;
1497 : : /* To simulate out-of-SSA the predecessor of edges into PHI nodes
1498 : : has a copy from the PHI argument to the PHI destination. */
1499 : 1939 : if (! scev_analyzable_p (res, scop->scop_info->region))
1500 : 388 : add_write (&writes, res);
1501 : 1939 : tree use = PHI_ARG_DEF_FROM_EDGE (phi, e);
1502 : 1939 : if (TREE_CODE (use) == SSA_NAME
1503 : 1345 : && ! SSA_NAME_IS_DEFAULT_DEF (use)
1504 : 1341 : && gimple_bb (SSA_NAME_DEF_STMT (use)) != bb_for_succs
1505 : 3105 : && ! scev_analyzable_p (use, scop->scop_info->region))
1506 : 193 : add_read (&reads, use, phi);
1507 : : }
1508 : 2661 : if (e->dest == bb_for_succs->loop_father->latch
1509 : 535 : && bb_in_sese_p (e->dest, scop->scop_info->region)
1510 : 3195 : && sese_trivially_empty_bb_p (e->dest))
1511 : 534 : latch = e->dest;
1512 : : }
1513 : : /* Handle empty latch block PHIs here, otherwise we confuse ISL
1514 : : with extra conditional code where it then peels off the last
1515 : : iteration just because of that. It would be simplest if we
1516 : : just didn't force simple latches (thus remove the forwarder). */
1517 : 2073 : bb_for_succs = latch;
1518 : : }
1519 : :
1520 : : /* For the region exit block add reads for all live-out vars. */
1521 : 2073 : if (bb == scop->scop_info->region.exit->src)
1522 : : {
1523 : 204 : sese_build_liveouts (scop->scop_info);
1524 : 204 : unsigned i;
1525 : 204 : bitmap_iterator bi;
1526 : 271 : EXECUTE_IF_SET_IN_BITMAP (scop->scop_info->liveout, 0, i, bi)
1527 : : {
1528 : 67 : tree use = ssa_name (i);
1529 : 67 : add_read (&reads, use, NULL);
1530 : : }
1531 : : }
1532 : :
1533 : 2073 : if (drs.is_empty () && writes.is_empty () && reads.is_empty ())
1534 : : return NULL;
1535 : :
1536 : 669 : return new_gimple_poly_bb (bb, drs, reads, writes);
1537 : : }
1538 : :
1539 : : /* Compute alias-sets for all data references in DRS. */
1540 : :
1541 : : static bool
1542 : 204 : build_alias_set (scop_p scop)
1543 : : {
1544 : 204 : int num_vertices = scop->drs.length ();
1545 : 204 : struct graph *g = new_graph (num_vertices);
1546 : 204 : dr_info *dr1, *dr2;
1547 : 204 : int i, j;
1548 : 204 : int *all_vertices;
1549 : :
1550 : 204 : struct loop *nest
1551 : 204 : = find_common_loop (scop->scop_info->region.entry->dest->loop_father,
1552 : 204 : scop->scop_info->region.exit->src->loop_father);
1553 : :
1554 : 204 : FOR_EACH_VEC_ELT (scop->drs, i, dr1)
1555 : 3951 : for (j = i+1; scop->drs.iterate (j, &dr2); j++)
1556 : 2361 : if (dr_may_alias_p (dr1->dr, dr2->dr, nest))
1557 : : {
1558 : : /* Dependences in the same alias set need to be handled
1559 : : by just looking at DR_ACCESS_FNs. */
1560 : 1558 : if (DR_NUM_DIMENSIONS (dr1->dr) == 0
1561 : 3112 : || DR_NUM_DIMENSIONS (dr1->dr) != DR_NUM_DIMENSIONS (dr2->dr)
1562 : 1554 : || ! operand_equal_p (DR_BASE_OBJECT (dr1->dr),
1563 : 1554 : DR_BASE_OBJECT (dr2->dr),
1564 : : OEP_ADDRESS_OF)
1565 : 3103 : || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1->dr)),
1566 : 1547 : TREE_TYPE (DR_BASE_OBJECT (dr2->dr))))
1567 : : {
1568 : 11 : free_graph (g);
1569 : 11 : return false;
1570 : : }
1571 : 1547 : add_edge (g, i, j);
1572 : 1547 : add_edge (g, j, i);
1573 : : }
1574 : :
1575 : 193 : all_vertices = XNEWVEC (int, num_vertices);
1576 : 1078 : for (i = 0; i < num_vertices; i++)
1577 : 692 : all_vertices[i] = i;
1578 : :
1579 : 193 : scop->max_alias_set
1580 : 193 : = graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + 1;
1581 : 193 : free (all_vertices);
1582 : :
1583 : 885 : for (i = 0; i < g->n_vertices; i++)
1584 : 692 : scop->drs[i].alias_set = g->vertices[i].component + 1;
1585 : :
1586 : 193 : free_graph (g);
1587 : 193 : return true;
1588 : : }
1589 : :
1590 : : /* Gather BBs and conditions for a SCOP. */
1591 : : class gather_bbs : public dom_walker
1592 : : {
1593 : : public:
1594 : : gather_bbs (cdi_direction, scop_p, int *);
1595 : :
1596 : : virtual edge before_dom_children (basic_block);
1597 : : virtual void after_dom_children (basic_block);
1598 : :
1599 : : private:
1600 : : auto_vec<gimple *, 3> conditions, cases;
1601 : : scop_p scop;
1602 : : };
1603 : : }
1604 : 204 : gather_bbs::gather_bbs (cdi_direction direction, scop_p scop, int *bb_to_rpo)
1605 : 204 : : dom_walker (direction, ALL_BLOCKS, bb_to_rpo), scop (scop)
1606 : : {
1607 : 204 : }
1608 : :
1609 : : /* Call-back for dom_walk executed before visiting the dominated
1610 : : blocks. */
1611 : :
1612 : : edge
1613 : 2276 : gather_bbs::before_dom_children (basic_block bb)
1614 : : {
1615 : 2276 : sese_info_p region = scop->scop_info;
1616 : 2276 : if (!bb_in_sese_p (bb, region->region))
1617 : 203 : return dom_walker::STOP;
1618 : :
1619 : : /* For loops fully contained in the region record parameters in the
1620 : : loop bounds. */
1621 : 2073 : loop_p loop = bb->loop_father;
1622 : 2073 : if (loop->header == bb
1623 : 2073 : && loop_in_sese_p (loop, region->region))
1624 : : {
1625 : 534 : tree nb_iters = number_of_latch_executions (loop);
1626 : 534 : if (chrec_contains_symbols (nb_iters))
1627 : : {
1628 : 139 : nb_iters = cached_scalar_evolution_in_region (region->region,
1629 : : loop, nb_iters);
1630 : 139 : scan_tree_for_params (region, nb_iters);
1631 : : }
1632 : : }
1633 : :
1634 : 2073 : if (gcond *stmt = single_pred_cond_non_loop_exit (bb))
1635 : : {
1636 : 619 : edge e = single_pred_edge (bb);
1637 : : /* Make sure the condition is in the region and thus was verified
1638 : : to be handled. */
1639 : 619 : if (e != region->region.entry)
1640 : : {
1641 : 618 : conditions.safe_push (stmt);
1642 : 618 : if (e->flags & EDGE_TRUE_VALUE)
1643 : 448 : cases.safe_push (stmt);
1644 : : else
1645 : 170 : cases.safe_push (NULL);
1646 : : }
1647 : : }
1648 : :
1649 : 2073 : scop->scop_info->bbs.safe_push (bb);
1650 : :
1651 : 2073 : gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb);
1652 : 2073 : if (!gbb)
1653 : : return NULL;
1654 : :
1655 : 669 : GBB_CONDITIONS (gbb) = conditions.copy ();
1656 : 669 : GBB_CONDITION_CASES (gbb) = cases.copy ();
1657 : :
1658 : 669 : poly_bb_p pbb = new_poly_bb (scop, gbb);
1659 : 669 : scop->pbbs.safe_push (pbb);
1660 : :
1661 : 669 : int i;
1662 : 669 : data_reference_p dr;
1663 : 2101 : FOR_EACH_VEC_ELT (gbb->data_refs, i, dr)
1664 : : {
1665 : 1137 : DEBUG_PRINT (dp << "Adding memory ";
1666 : : if (dr->is_read)
1667 : : dp << "read: ";
1668 : : else
1669 : : dp << "write: ";
1670 : : print_generic_expr (dump_file, dr->ref);
1671 : : dp << "\nFrom stmt: ";
1672 : : print_gimple_stmt (dump_file, dr->stmt, 0));
1673 : :
1674 : 763 : scop->drs.safe_push (dr_info (dr, pbb));
1675 : : }
1676 : :
1677 : : return NULL;
1678 : : }
1679 : :
1680 : : /* Call-back for dom_walk executed after visiting the dominated
1681 : : blocks. */
1682 : :
1683 : : void
1684 : 2276 : gather_bbs::after_dom_children (basic_block bb)
1685 : : {
1686 : 2276 : if (!bb_in_sese_p (bb, scop->scop_info->region))
1687 : : return;
1688 : :
1689 : 2073 : if (single_pred_cond_non_loop_exit (bb))
1690 : : {
1691 : 619 : edge e = single_pred_edge (bb);
1692 : 619 : if (e != scop->scop_info->region.entry)
1693 : : {
1694 : 618 : conditions.pop ();
1695 : 618 : cases.pop ();
1696 : : }
1697 : : }
1698 : : }
1699 : :
1700 : :
1701 : : /* Compute sth like an execution order, dominator order with first executing
1702 : : edges that stay inside the current loop, delaying processing exit edges. */
1703 : :
1704 : : static int *bb_to_rpo;
1705 : :
1706 : : /* Helper for qsort, sorting after order above. */
1707 : :
1708 : : static int
1709 : 3891 : cmp_pbbs (const void *pa, const void *pb)
1710 : : {
1711 : 3891 : poly_bb_p bb1 = *((const poly_bb_p *)pa);
1712 : 3891 : poly_bb_p bb2 = *((const poly_bb_p *)pb);
1713 : 3891 : if (bb_to_rpo[bb1->black_box->bb->index]
1714 : 3891 : < bb_to_rpo[bb2->black_box->bb->index])
1715 : : return -1;
1716 : 2109 : else if (bb_to_rpo[bb1->black_box->bb->index]
1717 : : > bb_to_rpo[bb2->black_box->bb->index])
1718 : : return 1;
1719 : : else
1720 : 0 : return 0;
1721 : : }
1722 : :
1723 : : /* Find Static Control Parts (SCoP) in the current function and pushes
1724 : : them to SCOPS. */
1725 : :
1726 : : void
1727 : 556 : build_scops (vec<scop_p> *scops)
1728 : : {
1729 : 556 : if (dump_file)
1730 : 189 : dp.set_dump_file (dump_file);
1731 : :
1732 : 556 : scop_detection sb;
1733 : 556 : sb.build_scop_depth (current_loops->tree_root);
1734 : :
1735 : : /* Now create scops from the lightweight SESEs. */
1736 : 556 : vec<sese_l> scops_l = sb.get_scops ();
1737 : :
1738 : : /* Domwalk needs a bb to RPO mapping. Compute it once here. */
1739 : 556 : int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
1740 : 556 : int postorder_num = pre_and_rev_post_order_compute (NULL, postorder, true);
1741 : 556 : bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
1742 : 9963 : for (int i = 0; i < postorder_num; ++i)
1743 : 9407 : bb_to_rpo[postorder[i]] = i;
1744 : 556 : free (postorder);
1745 : :
1746 : 556 : int i;
1747 : 556 : sese_l *s;
1748 : 760 : FOR_EACH_VEC_ELT (scops_l, i, s)
1749 : : {
1750 : 204 : scop_p scop = new_scop (s->entry, s->exit);
1751 : :
1752 : : /* Record all basic blocks and their conditions in REGION. */
1753 : 204 : gather_bbs (CDI_DOMINATORS, scop, bb_to_rpo).walk (s->entry->dest);
1754 : :
1755 : : /* Sort pbbs after execution order for initial schedule generation. */
1756 : 204 : scop->pbbs.qsort (cmp_pbbs);
1757 : :
1758 : 204 : if (! build_alias_set (scop))
1759 : : {
1760 : 11 : DEBUG_PRINT (dp << "[scop-detection-fail] cannot handle dependences\n");
1761 : 11 : free_scop (scop);
1762 : 11 : continue;
1763 : : }
1764 : :
1765 : : /* Do not optimize a scop containing only PBBs that do not belong
1766 : : to any loops. */
1767 : 193 : if (sb.nb_pbbs_in_loops (scop) == 0)
1768 : : {
1769 : 0 : DEBUG_PRINT (dp << "[scop-detection-fail] no data references.\n");
1770 : 0 : free_scop (scop);
1771 : 0 : continue;
1772 : : }
1773 : :
1774 : 193 : unsigned max_arrays = param_graphite_max_arrays_per_scop;
1775 : 193 : if (max_arrays > 0
1776 : 386 : && scop->drs.length () >= max_arrays)
1777 : : {
1778 : 0 : DEBUG_PRINT (dp << "[scop-detection-fail] too many data references: "
1779 : : << scop->drs.length ()
1780 : : << " is larger than --param graphite-max-arrays-per-scop="
1781 : : << max_arrays << ".\n");
1782 : 0 : free_scop (scop);
1783 : 0 : continue;
1784 : : }
1785 : :
1786 : 193 : find_scop_parameters (scop);
1787 : 193 : graphite_dim_t max_dim = param_graphite_max_nb_scop_params;
1788 : 193 : if (max_dim > 0
1789 : 193 : && scop_nb_params (scop) > max_dim)
1790 : : {
1791 : 0 : DEBUG_PRINT (dp << "[scop-detection-fail] too many parameters: "
1792 : : << scop_nb_params (scop)
1793 : : << " larger than --param graphite-max-nb-scop-params="
1794 : : << max_dim << ".\n");
1795 : 0 : free_scop (scop);
1796 : 0 : continue;
1797 : : }
1798 : :
1799 : 193 : scops->safe_push (scop);
1800 : : }
1801 : :
1802 : 556 : free (bb_to_rpo);
1803 : 556 : bb_to_rpo = NULL;
1804 : 932 : DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0););
1805 : 556 : }
1806 : :
1807 : : #endif /* HAVE_isl */
|
