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