]>
Commit | Line | Data |
---|---|---|
2abae5f1 | 1 | /* Single entry single exit control flow regions. |
5624e564 | 2 | Copyright (C) 2008-2015 Free Software Foundation, Inc. |
2abae5f1 SP |
3 | Contributed by Jan Sjodin <jan.sjodin@amd.com> and |
4 | Sebastian Pop <sebastian.pop@amd.com>. | |
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 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
c7131fb2 | 25 | #include "backend.h" |
cf2d1b38 | 26 | #include "tree.h" |
c7131fb2 | 27 | #include "gimple.h" |
957060b5 AM |
28 | #include "cfghooks.h" |
29 | #include "tree-pass.h" | |
c7131fb2 | 30 | #include "ssa.h" |
cf835838 | 31 | #include "tree-pretty-print.h" |
957060b5 | 32 | #include "fold-const.h" |
45b0be94 | 33 | #include "gimplify.h" |
5be5c238 | 34 | #include "gimple-iterator.h" |
65b016eb | 35 | #include "gimple-pretty-print.h" |
18f429e2 | 36 | #include "gimplify-me.h" |
442b4905 | 37 | #include "tree-cfg.h" |
442b4905 AM |
38 | #include "tree-ssa-loop.h" |
39 | #include "tree-into-ssa.h" | |
2abae5f1 | 40 | #include "cfgloop.h" |
2abae5f1 SP |
41 | #include "tree-data-ref.h" |
42 | #include "tree-scalar-evolution.h" | |
2abae5f1 | 43 | #include "sese.h" |
744730a4 | 44 | #include "tree-ssa-propagate.h" |
2abae5f1 | 45 | |
073a8998 | 46 | /* Record LOOP as occurring in REGION. */ |
2abae5f1 SP |
47 | |
48 | static void | |
bafcb153 | 49 | sese_record_loop (sese_info_p region, loop_p loop) |
2abae5f1 SP |
50 | { |
51 | if (sese_contains_loop (region, loop)) | |
52 | return; | |
53 | ||
65b016eb AK |
54 | bitmap_set_bit (region->loops, loop->num); |
55 | region->loop_nest.safe_push (loop); | |
2abae5f1 SP |
56 | } |
57 | ||
58 | /* Build the loop nests contained in REGION. Returns true when the | |
59 | operation was successful. */ | |
60 | ||
61 | void | |
bafcb153 | 62 | build_sese_loop_nests (sese_info_p region) |
2abae5f1 SP |
63 | { |
64 | unsigned i; | |
65 | basic_block bb; | |
66 | struct loop *loop0, *loop1; | |
67 | ||
11cd3bed | 68 | FOR_EACH_BB_FN (bb, cfun) |
bafcb153 | 69 | if (bb_in_sese_p (bb, region->region)) |
2abae5f1 SP |
70 | { |
71 | struct loop *loop = bb->loop_father; | |
72 | ||
73 | /* Only add loops if they are completely contained in the SCoP. */ | |
74 | if (loop->header == bb | |
bafcb153 | 75 | && bb_in_sese_p (loop->latch, region->region)) |
2abae5f1 SP |
76 | sese_record_loop (region, loop); |
77 | } | |
78 | ||
79 | /* Make sure that the loops in the SESE_LOOP_NEST are ordered. It | |
80 | can be the case that an inner loop is inserted before an outer | |
81 | loop. To avoid this, semi-sort once. */ | |
65b016eb | 82 | FOR_EACH_VEC_ELT (region->loop_nest, i, loop0) |
2abae5f1 | 83 | { |
65b016eb | 84 | if (region->loop_nest.length () == i + 1) |
2abae5f1 SP |
85 | break; |
86 | ||
65b016eb | 87 | loop1 = region->loop_nest[i + 1]; |
2abae5f1 SP |
88 | if (loop0->num > loop1->num) |
89 | { | |
65b016eb AK |
90 | region->loop_nest[i] = loop1; |
91 | region->loop_nest[i + 1] = loop0; | |
2abae5f1 SP |
92 | } |
93 | } | |
94 | } | |
95 | ||
96 | /* For a USE in BB, if BB is outside REGION, mark the USE in the | |
97 | LIVEOUTS set. */ | |
98 | ||
99 | static void | |
bafcb153 | 100 | sese_build_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb, |
2abae5f1 SP |
101 | tree use) |
102 | { | |
bafcb153 | 103 | gcc_assert (!bb_in_sese_p (bb, region->region)); |
2abae5f1 SP |
104 | if (TREE_CODE (use) != SSA_NAME) |
105 | return; | |
106 | ||
216cc294 | 107 | basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (use)); |
2abae5f1 | 108 | |
bafcb153 | 109 | if (!def_bb || !bb_in_sese_p (def_bb, region->region)) |
2abae5f1 SP |
110 | return; |
111 | ||
216cc294 | 112 | unsigned ver = SSA_NAME_VERSION (use); |
2abae5f1 SP |
113 | bitmap_set_bit (liveouts, ver); |
114 | } | |
115 | ||
116 | /* Marks for rewrite all the SSA_NAMES defined in REGION and that are | |
117 | used in BB that is outside of the REGION. */ | |
118 | ||
119 | static void | |
bafcb153 | 120 | sese_build_liveouts_bb (sese_info_p region, bitmap liveouts, basic_block bb) |
2abae5f1 | 121 | { |
2abae5f1 SP |
122 | edge e; |
123 | edge_iterator ei; | |
124 | ssa_op_iter iter; | |
125 | use_operand_p use_p; | |
126 | ||
127 | FOR_EACH_EDGE (e, ei, bb->succs) | |
538dd0b7 DM |
128 | for (gphi_iterator bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); |
129 | gsi_next (&bsi)) | |
2abae5f1 | 130 | sese_build_liveouts_use (region, liveouts, bb, |
538dd0b7 | 131 | PHI_ARG_DEF_FROM_EDGE (bsi.phi (), e)); |
2abae5f1 | 132 | |
538dd0b7 DM |
133 | for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); |
134 | gsi_next (&bsi)) | |
a3201927 | 135 | { |
355fe088 | 136 | gimple *stmt = gsi_stmt (bsi); |
a3201927 AO |
137 | |
138 | if (is_gimple_debug (stmt)) | |
139 | continue; | |
140 | ||
141 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) | |
142 | sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p)); | |
143 | } | |
144 | } | |
145 | ||
146 | /* For a USE in BB, return true if BB is outside REGION and it's not | |
147 | in the LIVEOUTS set. */ | |
148 | ||
149 | static bool | |
bafcb153 | 150 | sese_bad_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb, |
a3201927 AO |
151 | tree use) |
152 | { | |
bafcb153 | 153 | gcc_assert (!bb_in_sese_p (bb, region->region)); |
a3201927 AO |
154 | |
155 | if (TREE_CODE (use) != SSA_NAME) | |
156 | return false; | |
157 | ||
216cc294 | 158 | unsigned ver = SSA_NAME_VERSION (use); |
a3201927 AO |
159 | |
160 | /* If it's in liveouts, the variable will get a new PHI node, and | |
161 | the debug use will be properly adjusted. */ | |
162 | if (bitmap_bit_p (liveouts, ver)) | |
163 | return false; | |
164 | ||
216cc294 | 165 | basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (use)); |
a3201927 | 166 | |
bafcb153 | 167 | if (!def_bb || !bb_in_sese_p (def_bb, region->region)) |
a3201927 AO |
168 | return false; |
169 | ||
170 | return true; | |
171 | } | |
172 | ||
173 | /* Reset debug stmts that reference SSA_NAMES defined in REGION that | |
174 | are not marked as liveouts. */ | |
175 | ||
176 | static void | |
2ecf4eca AK |
177 | sese_reset_debug_liveouts_bb (sese_info_p region, bitmap liveouts, |
178 | basic_block bb) | |
a3201927 AO |
179 | { |
180 | gimple_stmt_iterator bsi; | |
181 | ssa_op_iter iter; | |
182 | use_operand_p use_p; | |
183 | ||
184 | for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) | |
185 | { | |
355fe088 | 186 | gimple *stmt = gsi_stmt (bsi); |
a3201927 AO |
187 | |
188 | if (!is_gimple_debug (stmt)) | |
189 | continue; | |
190 | ||
191 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) | |
192 | if (sese_bad_liveouts_use (region, liveouts, bb, | |
193 | USE_FROM_PTR (use_p))) | |
194 | { | |
195 | gimple_debug_bind_reset_value (stmt); | |
196 | update_stmt (stmt); | |
197 | break; | |
198 | } | |
199 | } | |
2abae5f1 SP |
200 | } |
201 | ||
202 | /* Build the LIVEOUTS of REGION: the set of variables defined inside | |
203 | and used outside the REGION. */ | |
204 | ||
205 | static void | |
bafcb153 | 206 | sese_build_liveouts (sese_info_p region, bitmap liveouts) |
2abae5f1 SP |
207 | { |
208 | basic_block bb; | |
209 | ||
216cc294 | 210 | /* FIXME: We could start iterating form the successor of sese. */ |
11cd3bed | 211 | FOR_EACH_BB_FN (bb, cfun) |
bafcb153 | 212 | if (!bb_in_sese_p (bb, region->region)) |
216cc294 AK |
213 | sese_build_liveouts_bb (region, liveouts, bb); |
214 | ||
215 | /* FIXME: We could start iterating form the successor of sese. */ | |
1c1ad7bb | 216 | if (MAY_HAVE_DEBUG_STMTS) |
11cd3bed | 217 | FOR_EACH_BB_FN (bb, cfun) |
bafcb153 | 218 | if (!bb_in_sese_p (bb, region->region)) |
216cc294 | 219 | sese_reset_debug_liveouts_bb (region, liveouts, bb); |
2abae5f1 SP |
220 | } |
221 | ||
222 | /* Builds a new SESE region from edges ENTRY and EXIT. */ | |
223 | ||
bafcb153 AK |
224 | sese_info_p |
225 | new_sese_info (edge entry, edge exit) | |
2abae5f1 | 226 | { |
bafcb153 | 227 | sese_info_p region = XNEW (struct sese_info_t); |
2abae5f1 | 228 | |
bafcb153 AK |
229 | region->region.entry = entry; |
230 | region->region.exit = exit; | |
65b016eb AK |
231 | region->loops = BITMAP_ALLOC (NULL); |
232 | region->loop_nest.create (3); | |
233 | region->params.create (3); | |
234 | region->rename_map = new rename_map_t; | |
235 | region->copied_bb_map = new bb_map_t; | |
b0b5710c | 236 | region->bbs.create (3); |
65b016eb | 237 | region->incomplete_phis.create (3); |
2abae5f1 SP |
238 | |
239 | return region; | |
240 | } | |
241 | ||
242 | /* Deletes REGION. */ | |
243 | ||
244 | void | |
bafcb153 | 245 | free_sese_info (sese_info_p region) |
2abae5f1 | 246 | { |
65b016eb AK |
247 | if (region->loops) |
248 | region->loops = BITMAP_ALLOC (NULL); | |
249 | ||
250 | region->params.release (); | |
251 | region->loop_nest.release (); | |
252 | ||
253 | for (rename_map_t::iterator it = region->rename_map->begin (); | |
254 | it != region->rename_map->begin (); ++it) | |
255 | (*it).second.release (); | |
256 | ||
257 | for (bb_map_t::iterator it = region->copied_bb_map->begin (); | |
258 | it != region->copied_bb_map->begin (); ++it) | |
259 | (*it).second.release (); | |
2abae5f1 | 260 | |
65b016eb AK |
261 | delete region->rename_map; |
262 | delete region->copied_bb_map; | |
263 | ||
264 | region->rename_map = NULL; | |
265 | region->copied_bb_map = NULL; | |
266 | ||
267 | region->bbs.release (); | |
268 | region->incomplete_phis.release (); | |
2abae5f1 | 269 | |
2abae5f1 SP |
270 | XDELETE (region); |
271 | } | |
272 | ||
273 | /* Add exit phis for USE on EXIT. */ | |
274 | ||
275 | static void | |
276 | sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e) | |
277 | { | |
538dd0b7 | 278 | gphi *phi = create_phi_node (NULL_TREE, exit); |
dcc748dd | 279 | create_new_def_for (use, phi, gimple_phi_result_ptr (phi)); |
9e227d60 DC |
280 | add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION); |
281 | add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION); | |
74032f47 | 282 | update_stmt (phi); |
2abae5f1 SP |
283 | } |
284 | ||
285 | /* Insert in the block BB phi nodes for variables defined in REGION | |
286 | and used outside the REGION. The code generation moves REGION in | |
287 | the else clause of an "if (1)" and generates code in the then | |
288 | clause that is at this point empty: | |
289 | ||
290 | | if (1) | |
291 | | empty; | |
292 | | else | |
293 | | REGION; | |
294 | */ | |
295 | ||
296 | void | |
bafcb153 | 297 | sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb, |
2abae5f1 SP |
298 | edge false_e, edge true_e) |
299 | { | |
300 | unsigned i; | |
301 | bitmap_iterator bi; | |
302 | bitmap liveouts = BITMAP_ALLOC (NULL); | |
303 | ||
2abae5f1 | 304 | sese_build_liveouts (region, liveouts); |
65b016eb | 305 | |
2abae5f1 | 306 | EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi) |
65b016eb AK |
307 | if (!virtual_operand_p (ssa_name (i))) |
308 | sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e); | |
309 | ||
2abae5f1 | 310 | BITMAP_FREE (liveouts); |
2abae5f1 SP |
311 | } |
312 | ||
65b016eb | 313 | /* Returns the outermost loop in SCOP that contains BB. */ |
2abae5f1 SP |
314 | |
315 | struct loop * | |
bafcb153 | 316 | outermost_loop_in_sese_1 (sese_l ®ion, basic_block bb) |
2abae5f1 SP |
317 | { |
318 | struct loop *nest; | |
319 | ||
320 | nest = bb->loop_father; | |
321 | while (loop_outer (nest) | |
322 | && loop_in_sese_p (loop_outer (nest), region)) | |
323 | nest = loop_outer (nest); | |
324 | ||
325 | return nest; | |
326 | } | |
327 | ||
95ad2417 SP |
328 | /* Same as outermost_loop_in_sese_1, returns the outermost loop |
329 | containing BB in REGION, but makes sure that the returned loop | |
330 | belongs to the REGION, and so this returns the first loop in the | |
331 | REGION when the loop containing BB does not belong to REGION. */ | |
332 | ||
333 | loop_p | |
bafcb153 | 334 | outermost_loop_in_sese (sese_l ®ion, basic_block bb) |
95ad2417 SP |
335 | { |
336 | loop_p nest = outermost_loop_in_sese_1 (region, bb); | |
337 | ||
338 | if (loop_in_sese_p (nest, region)) | |
339 | return nest; | |
340 | ||
341 | /* When the basic block BB does not belong to a loop in the region, | |
342 | return the first loop in the region. */ | |
343 | nest = nest->inner; | |
344 | while (nest) | |
345 | if (loop_in_sese_p (nest, region)) | |
346 | break; | |
347 | else | |
348 | nest = nest->next; | |
349 | ||
350 | gcc_assert (nest); | |
351 | return nest; | |
352 | } | |
353 | ||
09b574dd AK |
354 | /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */ |
355 | ||
356 | edge | |
357 | get_true_edge_from_guard_bb (basic_block bb) | |
358 | { | |
359 | edge e; | |
360 | edge_iterator ei; | |
361 | ||
362 | FOR_EACH_EDGE (e, ei, bb->succs) | |
363 | if (e->flags & EDGE_TRUE_VALUE) | |
364 | return e; | |
365 | ||
366 | gcc_unreachable (); | |
367 | return NULL; | |
368 | } | |
369 | ||
370 | /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */ | |
371 | ||
372 | edge | |
373 | get_false_edge_from_guard_bb (basic_block bb) | |
374 | { | |
375 | edge e; | |
376 | edge_iterator ei; | |
377 | ||
378 | FOR_EACH_EDGE (e, ei, bb->succs) | |
379 | if (!(e->flags & EDGE_TRUE_VALUE)) | |
380 | return e; | |
381 | ||
382 | gcc_unreachable (); | |
383 | return NULL; | |
384 | } | |
385 | ||
2abae5f1 SP |
386 | /* Sets the false region of an IF_REGION to REGION. */ |
387 | ||
388 | void | |
bafcb153 | 389 | if_region_set_false_region (ifsese if_region, sese_info_p region) |
2abae5f1 SP |
390 | { |
391 | basic_block condition = if_region_get_condition_block (if_region); | |
392 | edge false_edge = get_false_edge_from_guard_bb (condition); | |
393 | basic_block dummy = false_edge->dest; | |
bafcb153 AK |
394 | edge entry_region = region->region.entry; |
395 | edge exit_region = region->region.exit; | |
2abae5f1 SP |
396 | basic_block before_region = entry_region->src; |
397 | basic_block last_in_region = exit_region->src; | |
2a22f99c TS |
398 | hashval_t hash = htab_hash_pointer (exit_region); |
399 | loop_exit **slot | |
400 | = current_loops->exits->find_slot_with_hash (exit_region, hash, NO_INSERT); | |
2abae5f1 SP |
401 | |
402 | entry_region->flags = false_edge->flags; | |
403 | false_edge->flags = exit_region->flags; | |
404 | ||
405 | redirect_edge_pred (entry_region, condition); | |
406 | redirect_edge_pred (exit_region, before_region); | |
407 | redirect_edge_pred (false_edge, last_in_region); | |
408 | redirect_edge_succ (false_edge, single_succ (dummy)); | |
409 | delete_basic_block (dummy); | |
410 | ||
411 | exit_region->flags = EDGE_FALLTHRU; | |
412 | recompute_all_dominators (); | |
413 | ||
bafcb153 | 414 | region->region.exit = false_edge; |
8c54631d | 415 | |
04695783 | 416 | free (if_region->false_region); |
2abae5f1 SP |
417 | if_region->false_region = region; |
418 | ||
419 | if (slot) | |
420 | { | |
766090c2 | 421 | struct loop_exit *loop_exit = ggc_cleared_alloc<struct loop_exit> (); |
2abae5f1 | 422 | |
2ecf4eca AK |
423 | memcpy (loop_exit, *((struct loop_exit **) slot), |
424 | sizeof (struct loop_exit)); | |
2a22f99c | 425 | current_loops->exits->clear_slot (slot); |
2abae5f1 | 426 | |
65ef70d6 | 427 | hashval_t hash = htab_hash_pointer (false_edge); |
2a22f99c TS |
428 | slot = current_loops->exits->find_slot_with_hash (false_edge, hash, |
429 | INSERT); | |
2abae5f1 SP |
430 | loop_exit->e = false_edge; |
431 | *slot = loop_exit; | |
432 | false_edge->src->loop_father->exits->next = loop_exit; | |
433 | } | |
434 | } | |
435 | ||
436 | /* Creates an IFSESE with CONDITION on edge ENTRY. */ | |
437 | ||
086058c2 | 438 | static ifsese |
2abae5f1 SP |
439 | create_if_region_on_edge (edge entry, tree condition) |
440 | { | |
441 | edge e; | |
442 | edge_iterator ei; | |
bafcb153 AK |
443 | sese_info_p sese_region = XNEW (struct sese_info_t); |
444 | sese_info_p true_region = XNEW (struct sese_info_t); | |
445 | sese_info_p false_region = XNEW (struct sese_info_t); | |
8c54631d | 446 | ifsese if_region = XNEW (struct ifsese_s); |
2abae5f1 SP |
447 | edge exit = create_empty_if_region_on_edge (entry, condition); |
448 | ||
449 | if_region->region = sese_region; | |
bafcb153 AK |
450 | if_region->region->region.entry = entry; |
451 | if_region->region->region.exit = exit; | |
2abae5f1 SP |
452 | |
453 | FOR_EACH_EDGE (e, ei, entry->dest->succs) | |
454 | { | |
455 | if (e->flags & EDGE_TRUE_VALUE) | |
456 | { | |
bafcb153 AK |
457 | true_region->region.entry = e; |
458 | true_region->region.exit = single_succ_edge (e->dest); | |
2abae5f1 SP |
459 | if_region->true_region = true_region; |
460 | } | |
461 | else if (e->flags & EDGE_FALSE_VALUE) | |
462 | { | |
bafcb153 AK |
463 | false_region->region.entry = e; |
464 | false_region->region.exit = single_succ_edge (e->dest); | |
2abae5f1 SP |
465 | if_region->false_region = false_region; |
466 | } | |
467 | } | |
468 | ||
469 | return if_region; | |
470 | } | |
471 | ||
472 | /* Moves REGION in a condition expression: | |
473 | | if (1) | |
474 | | ; | |
475 | | else | |
476 | | REGION; | |
477 | */ | |
478 | ||
479 | ifsese | |
bafcb153 | 480 | move_sese_in_condition (sese_info_p region) |
2abae5f1 | 481 | { |
bafcb153 | 482 | basic_block pred_block = split_edge (region->region.entry); |
8c54631d | 483 | ifsese if_region; |
2abae5f1 | 484 | |
bafcb153 | 485 | region->region.entry = single_succ_edge (pred_block); |
65ef70d6 AK |
486 | if_region = create_if_region_on_edge (single_pred_edge (pred_block), |
487 | integer_one_node); | |
2abae5f1 SP |
488 | if_region_set_false_region (if_region, region); |
489 | ||
490 | return if_region; | |
491 | } | |
492 | ||
3c7c0158 SP |
493 | /* Replaces the condition of the IF_REGION with CONDITION: |
494 | | if (CONDITION) | |
495 | | true_region; | |
496 | | else | |
497 | | false_region; | |
498 | */ | |
499 | ||
500 | void | |
501 | set_ifsese_condition (ifsese if_region, tree condition) | |
502 | { | |
bafcb153 AK |
503 | sese_info_p region = if_region->region; |
504 | edge entry = region->region.entry; | |
3c7c0158 | 505 | basic_block bb = entry->dest; |
355fe088 | 506 | gimple *last = last_stmt (bb); |
3c7c0158 | 507 | gimple_stmt_iterator gsi = gsi_last_bb (bb); |
538dd0b7 | 508 | gcond *cond_stmt; |
3c7c0158 SP |
509 | |
510 | gcc_assert (gimple_code (last) == GIMPLE_COND); | |
511 | ||
512 | gsi_remove (&gsi, true); | |
513 | gsi = gsi_last_bb (bb); | |
514 | condition = force_gimple_operand_gsi (&gsi, condition, true, NULL, | |
515 | false, GSI_NEW_STMT); | |
516 | cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE); | |
517 | gsi = gsi_last_bb (bb); | |
518 | gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT); | |
519 | } | |
520 | ||
d5b5a232 | 521 | /* Return true when T is defined outside REGION or when no definitions are |
78fd2726 AK |
522 | variant in REGION. When HAS_VDEFS is a valid pointer, sets HAS_VDEFS to true |
523 | when T depends on memory that may change in REGION. */ | |
74032f47 | 524 | |
d5b5a232 | 525 | bool |
78fd2726 | 526 | invariant_in_sese_p_rec (tree t, sese_l ®ion, bool *has_vdefs) |
74032f47 | 527 | { |
74032f47 AK |
528 | if (!defined_in_sese_p (t, region)) |
529 | return true; | |
530 | ||
355fe088 | 531 | gimple *stmt = SSA_NAME_DEF_STMT (t); |
74032f47 AK |
532 | |
533 | if (gimple_code (stmt) == GIMPLE_PHI | |
534 | || gimple_code (stmt) == GIMPLE_CALL) | |
535 | return false; | |
536 | ||
d5b5a232 | 537 | /* VDEF is variant when it is in the region. */ |
d95fc584 | 538 | if (gimple_vdef (stmt)) |
78fd2726 AK |
539 | { |
540 | if (has_vdefs) | |
541 | *has_vdefs = true; | |
542 | return false; | |
543 | } | |
d5b5a232 AK |
544 | |
545 | /* A VUSE may or may not be variant following the VDEFs. */ | |
546 | if (tree vuse = gimple_vuse (stmt)) | |
78fd2726 | 547 | return invariant_in_sese_p_rec (vuse, region, has_vdefs); |
d5b5a232 | 548 | |
65b016eb AK |
549 | ssa_op_iter iter; |
550 | use_operand_p use_p; | |
74032f47 AK |
551 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) |
552 | { | |
553 | tree use = USE_FROM_PTR (use_p); | |
d5b5a232 | 554 | |
74032f47 AK |
555 | if (!defined_in_sese_p (use, region)) |
556 | continue; | |
557 | ||
78fd2726 | 558 | if (!invariant_in_sese_p_rec (use, region, has_vdefs)) |
74032f47 AK |
559 | return false; |
560 | } | |
561 | ||
562 | return true; | |
563 | } | |
564 | ||
2ecf4eca AK |
565 | /* Return true when DEF can be analyzed in REGION by the scalar |
566 | evolution analyzer. */ | |
567 | ||
568 | bool | |
569 | scev_analyzable_p (tree def, sese_l ®ion) | |
570 | { | |
571 | loop_p loop; | |
572 | tree scev; | |
573 | tree type = TREE_TYPE (def); | |
574 | ||
575 | /* When Graphite generates code for a scev, the code generator | |
576 | expresses the scev in function of a single induction variable. | |
577 | This is unsafe for floating point computations, as it may replace | |
578 | a floating point sum reduction with a multiplication. The | |
579 | following test returns false for non integer types to avoid such | |
580 | problems. */ | |
581 | if (!INTEGRAL_TYPE_P (type) | |
582 | && !POINTER_TYPE_P (type)) | |
583 | return false; | |
584 | ||
585 | loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def)); | |
586 | scev = scalar_evolution_in_region (region, loop, def); | |
587 | ||
588 | return !chrec_contains_undetermined (scev) | |
589 | && (TREE_CODE (scev) != SSA_NAME | |
590 | || !defined_in_sese_p (scev, region)) | |
591 | && (tree_does_not_contain_chrecs (scev) | |
592 | || evolution_function_is_affine_p (scev)); | |
593 | } | |
594 | ||
2abae5f1 SP |
595 | /* Returns the scalar evolution of T in REGION. Every variable that |
596 | is not defined in the REGION is considered a parameter. */ | |
597 | ||
598 | tree | |
bafcb153 | 599 | scalar_evolution_in_region (sese_l ®ion, loop_p loop, tree t) |
2abae5f1 | 600 | { |
355fe088 | 601 | gimple *def; |
2abae5f1 | 602 | struct loop *def_loop; |
bafcb153 | 603 | basic_block before = region.entry->src; |
2abae5f1 | 604 | |
05575a46 SP |
605 | /* SCOP parameters. */ |
606 | if (TREE_CODE (t) == SSA_NAME | |
607 | && !defined_in_sese_p (t, region)) | |
608 | return t; | |
609 | ||
2abae5f1 SP |
610 | if (TREE_CODE (t) != SSA_NAME |
611 | || loop_in_sese_p (loop, region)) | |
36f40be0 AK |
612 | /* FIXME: we would need instantiate SCEV to work on a region, and be more |
613 | flexible wrt. memory loads that may be invariant in the region. */ | |
2abae5f1 SP |
614 | return instantiate_scev (before, loop, |
615 | analyze_scalar_evolution (loop, t)); | |
616 | ||
2abae5f1 SP |
617 | def = SSA_NAME_DEF_STMT (t); |
618 | def_loop = loop_containing_stmt (def); | |
619 | ||
620 | if (loop_in_sese_p (def_loop, region)) | |
621 | { | |
622 | t = analyze_scalar_evolution (def_loop, t); | |
623 | def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1); | |
624 | t = compute_overall_effect_of_inner_loop (def_loop, t); | |
625 | return t; | |
626 | } | |
74032f47 | 627 | |
78fd2726 AK |
628 | bool has_vdefs = false; |
629 | if (invariant_in_sese_p_rec (t, region, &has_vdefs)) | |
74032f47 AK |
630 | return t; |
631 | ||
78fd2726 AK |
632 | /* T variates in REGION. */ |
633 | if (has_vdefs) | |
634 | return chrec_dont_know; | |
635 | ||
74032f47 | 636 | return instantiate_scev (before, loop, t); |
2abae5f1 | 637 | } |