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