]>
Commit | Line | Data |
---|---|---|
2abae5f1 | 1 | /* Single entry single exit control flow regions. |
cbe34bb5 | 2 | Copyright (C) 2008-2017 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" | |
744730a4 | 43 | #include "tree-ssa-propagate.h" |
2c818750 RB |
44 | #include "cfganal.h" |
45 | #include "sese.h" | |
2abae5f1 | 46 | |
2abae5f1 SP |
47 | /* For a USE in BB, if BB is outside REGION, mark the USE in the |
48 | LIVEOUTS set. */ | |
49 | ||
50 | static void | |
bafcb153 | 51 | sese_build_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb, |
2abae5f1 SP |
52 | tree use) |
53 | { | |
bafcb153 | 54 | gcc_assert (!bb_in_sese_p (bb, region->region)); |
2abae5f1 SP |
55 | if (TREE_CODE (use) != SSA_NAME) |
56 | return; | |
57 | ||
216cc294 | 58 | basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (use)); |
2abae5f1 | 59 | |
bafcb153 | 60 | if (!def_bb || !bb_in_sese_p (def_bb, region->region)) |
2abae5f1 SP |
61 | return; |
62 | ||
216cc294 | 63 | unsigned ver = SSA_NAME_VERSION (use); |
2abae5f1 SP |
64 | bitmap_set_bit (liveouts, ver); |
65 | } | |
66 | ||
67 | /* Marks for rewrite all the SSA_NAMES defined in REGION and that are | |
68 | used in BB that is outside of the REGION. */ | |
69 | ||
70 | static void | |
bd8d431f | 71 | sese_build_liveouts_bb (sese_info_p region, basic_block bb) |
2abae5f1 | 72 | { |
2abae5f1 SP |
73 | ssa_op_iter iter; |
74 | use_operand_p use_p; | |
75 | ||
bd8d431f RB |
76 | for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi); |
77 | gsi_next (&bsi)) | |
78 | FOR_EACH_PHI_ARG (use_p, bsi.phi (), iter, SSA_OP_USE) | |
79 | sese_build_liveouts_use (region, region->liveout, | |
80 | bb, USE_FROM_PTR (use_p)); | |
2abae5f1 | 81 | |
538dd0b7 DM |
82 | for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); |
83 | gsi_next (&bsi)) | |
a3201927 | 84 | { |
355fe088 | 85 | gimple *stmt = gsi_stmt (bsi); |
a3201927 | 86 | |
bd8d431f | 87 | bitmap liveouts = region->liveout; |
a3201927 | 88 | if (is_gimple_debug (stmt)) |
bd8d431f | 89 | liveouts = region->debug_liveout; |
a3201927 | 90 | |
bd8d431f | 91 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) |
a3201927 AO |
92 | sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p)); |
93 | } | |
94 | } | |
95 | ||
a3201927 AO |
96 | /* Reset debug stmts that reference SSA_NAMES defined in REGION that |
97 | are not marked as liveouts. */ | |
98 | ||
99 | static void | |
bd8d431f | 100 | sese_reset_debug_liveouts (sese_info_p region) |
a3201927 | 101 | { |
bd8d431f RB |
102 | bitmap_iterator bi; |
103 | unsigned i; | |
104 | EXECUTE_IF_AND_COMPL_IN_BITMAP (region->debug_liveout, region->liveout, | |
105 | 0, i, bi) | |
a3201927 | 106 | { |
bd8d431f RB |
107 | tree name = ssa_name (i); |
108 | auto_vec<gimple *, 4> stmts; | |
109 | gimple *use_stmt; | |
110 | imm_use_iterator use_iter; | |
111 | FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name) | |
112 | { | |
113 | if (! is_gimple_debug (use_stmt) | |
114 | || bb_in_sese_p (gimple_bb (use_stmt), region->region)) | |
115 | continue; | |
116 | stmts.safe_push (use_stmt); | |
117 | } | |
118 | while (!stmts.is_empty ()) | |
119 | { | |
120 | gimple *stmt = stmts.pop (); | |
121 | gimple_debug_bind_reset_value (stmt); | |
122 | update_stmt (stmt); | |
123 | } | |
a3201927 | 124 | } |
2abae5f1 SP |
125 | } |
126 | ||
127 | /* Build the LIVEOUTS of REGION: the set of variables defined inside | |
128 | and used outside the REGION. */ | |
129 | ||
bd8d431f RB |
130 | void |
131 | sese_build_liveouts (sese_info_p region) | |
2abae5f1 SP |
132 | { |
133 | basic_block bb; | |
134 | ||
bd8d431f RB |
135 | gcc_assert (region->liveout == NULL |
136 | && region->debug_liveout == NULL); | |
137 | ||
138 | region->liveout = BITMAP_ALLOC (NULL); | |
139 | region->debug_liveout = BITMAP_ALLOC (NULL); | |
140 | ||
216cc294 | 141 | /* FIXME: We could start iterating form the successor of sese. */ |
11cd3bed | 142 | FOR_EACH_BB_FN (bb, cfun) |
bafcb153 | 143 | if (!bb_in_sese_p (bb, region->region)) |
bd8d431f | 144 | sese_build_liveouts_bb (region, bb); |
2abae5f1 SP |
145 | } |
146 | ||
147 | /* Builds a new SESE region from edges ENTRY and EXIT. */ | |
148 | ||
bafcb153 AK |
149 | sese_info_p |
150 | new_sese_info (edge entry, edge exit) | |
2abae5f1 | 151 | { |
bafcb153 | 152 | sese_info_p region = XNEW (struct sese_info_t); |
2abae5f1 | 153 | |
bafcb153 AK |
154 | region->region.entry = entry; |
155 | region->region.exit = exit; | |
bd8d431f RB |
156 | region->liveout = NULL; |
157 | region->debug_liveout = NULL; | |
65b016eb AK |
158 | region->params.create (3); |
159 | region->rename_map = new rename_map_t; | |
b0b5710c | 160 | region->bbs.create (3); |
65b016eb | 161 | region->incomplete_phis.create (3); |
2abae5f1 | 162 | |
1d198f09 | 163 | |
2abae5f1 SP |
164 | return region; |
165 | } | |
166 | ||
167 | /* Deletes REGION. */ | |
168 | ||
169 | void | |
bafcb153 | 170 | free_sese_info (sese_info_p region) |
2abae5f1 | 171 | { |
65b016eb | 172 | region->params.release (); |
bd8d431f RB |
173 | BITMAP_FREE (region->liveout); |
174 | BITMAP_FREE (region->debug_liveout); | |
65b016eb AK |
175 | |
176 | for (rename_map_t::iterator it = region->rename_map->begin (); | |
61c81999 | 177 | it != region->rename_map->end (); ++it) |
65b016eb AK |
178 | (*it).second.release (); |
179 | ||
65b016eb | 180 | delete region->rename_map; |
65b016eb | 181 | region->rename_map = NULL; |
65b016eb AK |
182 | region->bbs.release (); |
183 | region->incomplete_phis.release (); | |
2abae5f1 | 184 | |
2abae5f1 SP |
185 | XDELETE (region); |
186 | } | |
187 | ||
188 | /* Add exit phis for USE on EXIT. */ | |
189 | ||
190 | static void | |
191 | sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e) | |
192 | { | |
538dd0b7 | 193 | gphi *phi = create_phi_node (NULL_TREE, exit); |
dcc748dd | 194 | create_new_def_for (use, phi, gimple_phi_result_ptr (phi)); |
9e227d60 DC |
195 | add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION); |
196 | add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION); | |
74032f47 | 197 | update_stmt (phi); |
2abae5f1 SP |
198 | } |
199 | ||
200 | /* Insert in the block BB phi nodes for variables defined in REGION | |
201 | and used outside the REGION. The code generation moves REGION in | |
202 | the else clause of an "if (1)" and generates code in the then | |
203 | clause that is at this point empty: | |
204 | ||
205 | | if (1) | |
206 | | empty; | |
207 | | else | |
208 | | REGION; | |
209 | */ | |
210 | ||
211 | void | |
bafcb153 | 212 | sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb, |
2abae5f1 SP |
213 | edge false_e, edge true_e) |
214 | { | |
bd8d431f RB |
215 | if (MAY_HAVE_DEBUG_STMTS) |
216 | sese_reset_debug_liveouts (region); | |
217 | ||
2abae5f1 SP |
218 | unsigned i; |
219 | bitmap_iterator bi; | |
bd8d431f | 220 | EXECUTE_IF_SET_IN_BITMAP (region->liveout, 0, i, bi) |
65b016eb AK |
221 | if (!virtual_operand_p (ssa_name (i))) |
222 | sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e); | |
2abae5f1 SP |
223 | } |
224 | ||
65b016eb | 225 | /* Returns the outermost loop in SCOP that contains BB. */ |
2abae5f1 SP |
226 | |
227 | struct loop * | |
bafcb153 | 228 | outermost_loop_in_sese_1 (sese_l ®ion, basic_block bb) |
2abae5f1 SP |
229 | { |
230 | struct loop *nest; | |
231 | ||
232 | nest = bb->loop_father; | |
233 | while (loop_outer (nest) | |
234 | && loop_in_sese_p (loop_outer (nest), region)) | |
235 | nest = loop_outer (nest); | |
236 | ||
237 | return nest; | |
238 | } | |
239 | ||
95ad2417 SP |
240 | /* Same as outermost_loop_in_sese_1, returns the outermost loop |
241 | containing BB in REGION, but makes sure that the returned loop | |
242 | belongs to the REGION, and so this returns the first loop in the | |
243 | REGION when the loop containing BB does not belong to REGION. */ | |
244 | ||
245 | loop_p | |
bafcb153 | 246 | outermost_loop_in_sese (sese_l ®ion, basic_block bb) |
95ad2417 SP |
247 | { |
248 | loop_p nest = outermost_loop_in_sese_1 (region, bb); | |
249 | ||
250 | if (loop_in_sese_p (nest, region)) | |
251 | return nest; | |
252 | ||
253 | /* When the basic block BB does not belong to a loop in the region, | |
254 | return the first loop in the region. */ | |
255 | nest = nest->inner; | |
256 | while (nest) | |
257 | if (loop_in_sese_p (nest, region)) | |
258 | break; | |
259 | else | |
260 | nest = nest->next; | |
261 | ||
262 | gcc_assert (nest); | |
263 | return nest; | |
264 | } | |
265 | ||
09b574dd AK |
266 | /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */ |
267 | ||
268 | edge | |
269 | get_true_edge_from_guard_bb (basic_block bb) | |
270 | { | |
271 | edge e; | |
272 | edge_iterator ei; | |
273 | ||
274 | FOR_EACH_EDGE (e, ei, bb->succs) | |
275 | if (e->flags & EDGE_TRUE_VALUE) | |
276 | return e; | |
277 | ||
278 | gcc_unreachable (); | |
279 | return NULL; | |
280 | } | |
281 | ||
282 | /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */ | |
283 | ||
284 | edge | |
285 | get_false_edge_from_guard_bb (basic_block bb) | |
286 | { | |
287 | edge e; | |
288 | edge_iterator ei; | |
289 | ||
290 | FOR_EACH_EDGE (e, ei, bb->succs) | |
291 | if (!(e->flags & EDGE_TRUE_VALUE)) | |
292 | return e; | |
293 | ||
294 | gcc_unreachable (); | |
295 | return NULL; | |
296 | } | |
297 | ||
2abae5f1 SP |
298 | /* Moves REGION in a condition expression: |
299 | | if (1) | |
300 | | ; | |
301 | | else | |
302 | | REGION; | |
303 | */ | |
304 | ||
305 | ifsese | |
bafcb153 | 306 | move_sese_in_condition (sese_info_p region) |
2abae5f1 | 307 | { |
2c818750 | 308 | basic_block region_entry_dest = region->region.entry->dest; |
bafcb153 | 309 | basic_block pred_block = split_edge (region->region.entry); |
2c818750 RB |
310 | basic_block merge_block = split_edge (region->region.exit); |
311 | ||
312 | edge true_edge = make_edge (pred_block, merge_block, EDGE_TRUE_VALUE); | |
313 | edge false_edge = find_edge (pred_block, region_entry_dest); | |
314 | false_edge->flags &= ~EDGE_FALLTHRU; | |
315 | false_edge->flags |= EDGE_FALSE_VALUE; | |
316 | gimple_stmt_iterator gsi = gsi_last_bb (pred_block); | |
317 | gcond *cond = gimple_build_cond (NE_EXPR, integer_one_node, integer_zero_node, | |
318 | NULL_TREE, NULL_TREE); | |
319 | gsi_insert_after (&gsi, cond, GSI_CONTINUE_LINKING); | |
320 | if (dom_info_available_p (CDI_DOMINATORS)) | |
321 | set_immediate_dominator (CDI_DOMINATORS, merge_block, pred_block); | |
322 | ||
323 | ifsese if_region = XNEW (ifsese_s); | |
324 | if_region->region = XCNEW (sese_info_t); | |
325 | if_region->true_region = XCNEW (sese_info_t); | |
326 | if_region->false_region = XCNEW (sese_info_t); | |
327 | if_region->region->region.entry = single_pred_edge (pred_block); | |
328 | if_region->region->region.exit = single_succ_edge (merge_block); | |
329 | if_region->false_region->region.entry = false_edge; | |
330 | if_region->false_region->region.exit = region->region.exit; | |
331 | if_region->true_region->region.entry = true_edge; | |
332 | if_region->true_region->region.exit | |
333 | = single_succ_edge (split_edge (true_edge)); | |
2abae5f1 | 334 | |
bd8d431f RB |
335 | region->region = if_region->false_region->region; |
336 | ||
2abae5f1 SP |
337 | return if_region; |
338 | } | |
339 | ||
3c7c0158 SP |
340 | /* Replaces the condition of the IF_REGION with CONDITION: |
341 | | if (CONDITION) | |
342 | | true_region; | |
343 | | else | |
344 | | false_region; | |
345 | */ | |
346 | ||
347 | void | |
348 | set_ifsese_condition (ifsese if_region, tree condition) | |
349 | { | |
bafcb153 AK |
350 | sese_info_p region = if_region->region; |
351 | edge entry = region->region.entry; | |
3c7c0158 | 352 | basic_block bb = entry->dest; |
355fe088 | 353 | gimple *last = last_stmt (bb); |
3c7c0158 | 354 | gimple_stmt_iterator gsi = gsi_last_bb (bb); |
538dd0b7 | 355 | gcond *cond_stmt; |
3c7c0158 SP |
356 | |
357 | gcc_assert (gimple_code (last) == GIMPLE_COND); | |
358 | ||
359 | gsi_remove (&gsi, true); | |
360 | gsi = gsi_last_bb (bb); | |
361 | condition = force_gimple_operand_gsi (&gsi, condition, true, NULL, | |
362 | false, GSI_NEW_STMT); | |
363 | cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE); | |
364 | gsi = gsi_last_bb (bb); | |
365 | gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT); | |
366 | } | |
367 | ||
d5b5a232 | 368 | /* Return true when T is defined outside REGION or when no definitions are |
78fd2726 AK |
369 | variant in REGION. When HAS_VDEFS is a valid pointer, sets HAS_VDEFS to true |
370 | when T depends on memory that may change in REGION. */ | |
74032f47 | 371 | |
d5b5a232 | 372 | bool |
1cb28772 | 373 | invariant_in_sese_p_rec (tree t, const sese_l ®ion, bool *has_vdefs) |
74032f47 | 374 | { |
74032f47 AK |
375 | if (!defined_in_sese_p (t, region)) |
376 | return true; | |
377 | ||
355fe088 | 378 | gimple *stmt = SSA_NAME_DEF_STMT (t); |
74032f47 AK |
379 | |
380 | if (gimple_code (stmt) == GIMPLE_PHI | |
381 | || gimple_code (stmt) == GIMPLE_CALL) | |
382 | return false; | |
383 | ||
d5b5a232 | 384 | /* VDEF is variant when it is in the region. */ |
d95fc584 | 385 | if (gimple_vdef (stmt)) |
78fd2726 AK |
386 | { |
387 | if (has_vdefs) | |
388 | *has_vdefs = true; | |
389 | return false; | |
390 | } | |
d5b5a232 AK |
391 | |
392 | /* A VUSE may or may not be variant following the VDEFs. */ | |
393 | if (tree vuse = gimple_vuse (stmt)) | |
78fd2726 | 394 | return invariant_in_sese_p_rec (vuse, region, has_vdefs); |
d5b5a232 | 395 | |
65b016eb AK |
396 | ssa_op_iter iter; |
397 | use_operand_p use_p; | |
74032f47 AK |
398 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) |
399 | { | |
400 | tree use = USE_FROM_PTR (use_p); | |
d5b5a232 | 401 | |
74032f47 AK |
402 | if (!defined_in_sese_p (use, region)) |
403 | continue; | |
404 | ||
78fd2726 | 405 | if (!invariant_in_sese_p_rec (use, region, has_vdefs)) |
74032f47 AK |
406 | return false; |
407 | } | |
408 | ||
409 | return true; | |
410 | } | |
411 | ||
2ecf4eca AK |
412 | /* Return true when DEF can be analyzed in REGION by the scalar |
413 | evolution analyzer. */ | |
414 | ||
415 | bool | |
416 | scev_analyzable_p (tree def, sese_l ®ion) | |
417 | { | |
418 | loop_p loop; | |
419 | tree scev; | |
420 | tree type = TREE_TYPE (def); | |
421 | ||
422 | /* When Graphite generates code for a scev, the code generator | |
423 | expresses the scev in function of a single induction variable. | |
424 | This is unsafe for floating point computations, as it may replace | |
425 | a floating point sum reduction with a multiplication. The | |
426 | following test returns false for non integer types to avoid such | |
427 | problems. */ | |
428 | if (!INTEGRAL_TYPE_P (type) | |
429 | && !POINTER_TYPE_P (type)) | |
430 | return false; | |
431 | ||
432 | loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def)); | |
433 | scev = scalar_evolution_in_region (region, loop, def); | |
434 | ||
7668b0a6 RB |
435 | return (!chrec_contains_undetermined (scev) |
436 | && (TREE_CODE (scev) != SSA_NAME | |
437 | || !defined_in_sese_p (scev, region)) | |
438 | && scev_is_linear_expression (scev) | |
439 | && (! loop | |
440 | || ! loop_in_sese_p (loop, region) | |
441 | || ! chrec_contains_symbols_defined_in_loop (scev, loop->num))); | |
2ecf4eca AK |
442 | } |
443 | ||
2abae5f1 SP |
444 | /* Returns the scalar evolution of T in REGION. Every variable that |
445 | is not defined in the REGION is considered a parameter. */ | |
446 | ||
447 | tree | |
1cb28772 | 448 | scalar_evolution_in_region (const sese_l ®ion, loop_p loop, tree t) |
2abae5f1 | 449 | { |
05575a46 SP |
450 | /* SCOP parameters. */ |
451 | if (TREE_CODE (t) == SSA_NAME | |
452 | && !defined_in_sese_p (t, region)) | |
453 | return t; | |
454 | ||
92900aec RB |
455 | if (!loop_in_sese_p (loop, region)) |
456 | loop = NULL; | |
78fd2726 | 457 | |
92900aec RB |
458 | return instantiate_scev (region.entry, loop, |
459 | analyze_scalar_evolution (loop, t)); | |
2abae5f1 | 460 | } |
adba512d | 461 | |
bd8d431f RB |
462 | /* Return true if BB is empty, contains only DEBUG_INSNs. */ |
463 | ||
464 | bool | |
465 | sese_trivially_empty_bb_p (basic_block bb) | |
466 | { | |
467 | gimple_stmt_iterator gsi; | |
468 | ||
469 | for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
470 | if (gimple_code (gsi_stmt (gsi)) != GIMPLE_DEBUG | |
471 | && gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL) | |
472 | return false; | |
473 | ||
474 | return true; | |
475 | } | |
476 | ||
adba512d AK |
477 | /* Pretty print edge E to FILE. */ |
478 | ||
479 | void | |
480 | print_edge (FILE *file, const_edge e) | |
481 | { | |
482 | fprintf (file, "edge (bb_%d, bb_%d)", e->src->index, e->dest->index); | |
483 | } | |
484 | ||
485 | /* Pretty print sese S to FILE. */ | |
486 | ||
487 | void | |
488 | print_sese (FILE *file, const sese_l &s) | |
489 | { | |
490 | fprintf (file, "(entry_"); print_edge (file, s.entry); | |
491 | fprintf (file, ", exit_"); print_edge (file, s.exit); | |
492 | fprintf (file, ")\n"); | |
493 | } | |
494 | ||
495 | /* Pretty print edge E to STDERR. */ | |
496 | ||
497 | DEBUG_FUNCTION void | |
498 | debug_edge (const_edge e) | |
499 | { | |
500 | print_edge (stderr, e); | |
501 | } | |
502 | ||
503 | /* Pretty print sese S to STDERR. */ | |
504 | ||
505 | DEBUG_FUNCTION void | |
506 | debug_sese (const sese_l &s) | |
507 | { | |
508 | print_sese (stderr, s); | |
509 | } |