Branch data Line data Source code
1 : : /* Single entry single exit control flow regions.
2 : : Copyright (C) 2008-2025 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 : 4529 : sese_build_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb,
52 : : tree use)
53 : : {
54 : 4529 : gcc_assert (!bb_in_sese_p (bb, region->region));
55 : 4529 : if (TREE_CODE (use) != SSA_NAME)
56 : : return;
57 : :
58 : 3959 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
59 : :
60 : 3959 : if (!def_bb || !bb_in_sese_p (def_bb, region->region))
61 : 3885 : return;
62 : :
63 : 74 : unsigned ver = SSA_NAME_VERSION (use);
64 : 74 : 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 : 2111 : sese_build_liveouts_bb (sese_info_p region, basic_block bb)
72 : : {
73 : 2111 : ssa_op_iter iter;
74 : 2111 : use_operand_p use_p;
75 : :
76 : 3171 : for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
77 : 1060 : gsi_next (&bsi))
78 : 2251 : FOR_EACH_PHI_ARG (use_p, bsi.phi (), iter, SSA_OP_USE)
79 : 1191 : sese_build_liveouts_use (region, region->liveout,
80 : : bb, USE_FROM_PTR (use_p));
81 : :
82 : 8439 : for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
83 : 4217 : gsi_next (&bsi))
84 : : {
85 : 4217 : gimple *stmt = gsi_stmt (bsi);
86 : :
87 : 4217 : bitmap liveouts = region->liveout;
88 : 4217 : if (is_gimple_debug (stmt))
89 : 30 : liveouts = region->debug_liveout;
90 : :
91 : 7555 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
92 : 3338 : sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
93 : : }
94 : 2111 : }
95 : :
96 : : /* Reset debug stmts that reference SSA_NAMES defined in REGION that
97 : : are not marked as liveouts. */
98 : :
99 : : static void
100 : 4 : sese_reset_debug_liveouts (sese_info_p region)
101 : : {
102 : 4 : bitmap_iterator bi;
103 : 4 : unsigned i;
104 : 4 : EXECUTE_IF_AND_COMPL_IN_BITMAP (region->debug_liveout, region->liveout,
105 : : 0, i, bi)
106 : : {
107 : 0 : tree name = ssa_name (i);
108 : 0 : auto_vec<gimple *, 4> stmts;
109 : 0 : gimple *use_stmt;
110 : 0 : imm_use_iterator use_iter;
111 : 0 : FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name)
112 : : {
113 : 0 : if (! is_gimple_debug (use_stmt)
114 : 0 : || bb_in_sese_p (gimple_bb (use_stmt), region->region))
115 : 0 : continue;
116 : 0 : stmts.safe_push (use_stmt);
117 : 0 : }
118 : 0 : while (!stmts.is_empty ())
119 : : {
120 : 0 : gimple *stmt = stmts.pop ();
121 : 0 : gimple_debug_bind_reset_value (stmt);
122 : 0 : update_stmt (stmt);
123 : : }
124 : 0 : }
125 : 4 : }
126 : :
127 : : /* Build the LIVEOUTS of REGION: the set of variables defined inside
128 : : and used outside the REGION. */
129 : :
130 : : void
131 : 202 : sese_build_liveouts (sese_info_p region)
132 : : {
133 : 202 : basic_block bb;
134 : :
135 : 202 : gcc_assert (region->liveout == NULL
136 : : && region->debug_liveout == NULL);
137 : :
138 : 202 : region->liveout = BITMAP_ALLOC (NULL);
139 : 202 : region->debug_liveout = BITMAP_ALLOC (NULL);
140 : :
141 : : /* FIXME: We could start iterating form the successor of sese. */
142 : 4369 : FOR_EACH_BB_FN (bb, cfun)
143 : 4167 : if (!bb_in_sese_p (bb, region->region))
144 : 2111 : sese_build_liveouts_bb (region, bb);
145 : 202 : }
146 : :
147 : : /* Builds a new SESE region from edges ENTRY and EXIT. */
148 : :
149 : : sese_info_p
150 : 202 : new_sese_info (edge entry, edge exit)
151 : : {
152 : 202 : sese_info_p region = XNEW (class sese_info_t);
153 : :
154 : 202 : region->region.entry = entry;
155 : 202 : region->region.exit = exit;
156 : 202 : region->liveout = NULL;
157 : 202 : region->debug_liveout = NULL;
158 : 202 : region->params.create (3);
159 : 202 : region->rename_map = new hash_map <tree, tree>;
160 : 202 : region->bbs.create (3);
161 : :
162 : 202 : return region;
163 : : }
164 : :
165 : : /* Deletes REGION. */
166 : :
167 : : void
168 : 202 : free_sese_info (sese_info_p region)
169 : : {
170 : 202 : region->params.release ();
171 : 202 : BITMAP_FREE (region->liveout);
172 : 202 : BITMAP_FREE (region->debug_liveout);
173 : :
174 : 404 : delete region->rename_map;
175 : 202 : region->rename_map = NULL;
176 : 202 : region->bbs.release ();
177 : :
178 : 202 : XDELETE (region);
179 : 202 : }
180 : :
181 : : /* Add exit phis for USE on EXIT. */
182 : :
183 : : static void
184 : 56 : sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
185 : : {
186 : 56 : gphi *phi = create_phi_node (NULL_TREE, exit);
187 : 56 : create_new_def_for (use, phi, gimple_phi_result_ptr (phi));
188 : 56 : add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
189 : 56 : add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
190 : 56 : update_stmt (phi);
191 : 56 : }
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 : 155 : sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb,
206 : : edge false_e, edge true_e)
207 : : {
208 : 155 : if (MAY_HAVE_DEBUG_BIND_STMTS)
209 : 4 : sese_reset_debug_liveouts (region);
210 : :
211 : 155 : unsigned i;
212 : 155 : bitmap_iterator bi;
213 : 211 : EXECUTE_IF_SET_IN_BITMAP (region->liveout, 0, i, bi)
214 : 112 : if (!virtual_operand_p (ssa_name (i)))
215 : 56 : sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
216 : 155 : }
217 : :
218 : : /* Returns the outermost loop in SCOP that contains BB. */
219 : :
220 : : class loop *
221 : 0 : outermost_loop_in_sese_1 (sese_l ®ion, basic_block bb)
222 : : {
223 : 0 : class loop *nest;
224 : :
225 : 0 : nest = bb->loop_father;
226 : 0 : while (loop_outer (nest)
227 : 0 : && loop_in_sese_p (loop_outer (nest), region))
228 : 0 : nest = loop_outer (nest);
229 : :
230 : 0 : 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 : 0 : outermost_loop_in_sese (sese_l ®ion, basic_block bb)
240 : : {
241 : 0 : loop_p nest = outermost_loop_in_sese_1 (region, bb);
242 : :
243 : 0 : if (loop_in_sese_p (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 : 0 : nest = nest->inner;
249 : 0 : while (nest)
250 : 0 : if (loop_in_sese_p (nest, region))
251 : : break;
252 : : else
253 : 0 : nest = nest->next;
254 : :
255 : 0 : 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 : 201 : get_true_edge_from_guard_bb (basic_block bb)
263 : : {
264 : 201 : edge e;
265 : 201 : edge_iterator ei;
266 : :
267 : 201 : FOR_EACH_EDGE (e, ei, bb->succs)
268 : 201 : if (e->flags & EDGE_TRUE_VALUE)
269 : 201 : return e;
270 : :
271 : 0 : 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 : 32 : get_false_edge_from_guard_bb (basic_block bb)
279 : : {
280 : 32 : edge e;
281 : 32 : edge_iterator ei;
282 : :
283 : 64 : FOR_EACH_EDGE (e, ei, bb->succs)
284 : 64 : if (!(e->flags & EDGE_TRUE_VALUE))
285 : 32 : return e;
286 : :
287 : 0 : 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 : 157 : move_sese_in_condition (sese_info_p region)
300 : : {
301 : 157 : basic_block region_entry_dest = region->region.entry->dest;
302 : 157 : basic_block pred_block = split_edge (region->region.entry);
303 : 157 : basic_block merge_block = split_edge (region->region.exit);
304 : :
305 : 157 : edge true_edge = make_edge (pred_block, merge_block, EDGE_TRUE_VALUE);
306 : 157 : edge false_edge = find_edge (pred_block, region_entry_dest);
307 : 157 : false_edge->flags &= ~EDGE_FALLTHRU;
308 : 157 : false_edge->flags |= EDGE_FALSE_VALUE;
309 : 157 : gimple_stmt_iterator gsi = gsi_last_bb (pred_block);
310 : 157 : gcond *cond = gimple_build_cond (NE_EXPR, integer_one_node, integer_zero_node,
311 : : NULL_TREE, NULL_TREE);
312 : 157 : gsi_insert_after (&gsi, cond, GSI_CONTINUE_LINKING);
313 : 157 : if (dom_info_available_p (CDI_DOMINATORS))
314 : 157 : set_immediate_dominator (CDI_DOMINATORS, merge_block, pred_block);
315 : :
316 : 157 : ifsese if_region = XNEW (ifsese_s);
317 : 157 : if_region->region = XCNEW (sese_info_t);
318 : 157 : if_region->true_region = XCNEW (sese_info_t);
319 : 157 : if_region->false_region = XCNEW (sese_info_t);
320 : 157 : if_region->region->region.entry = single_pred_edge (pred_block);
321 : 157 : if_region->region->region.exit = single_succ_edge (merge_block);
322 : 157 : if_region->false_region->region.entry = false_edge;
323 : 157 : if_region->false_region->region.exit = region->region.exit;
324 : 157 : if_region->true_region->region.entry = true_edge;
325 : 157 : if_region->true_region->region.exit
326 : 157 : = single_succ_edge (split_edge (true_edge));
327 : :
328 : 157 : region->region = if_region->false_region->region;
329 : :
330 : 157 : 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 : 0 : set_ifsese_condition (ifsese if_region, tree condition)
342 : : {
343 : 0 : sese_info_p region = if_region->region;
344 : 0 : edge entry = region->region.entry;
345 : 0 : basic_block bb = entry->dest;
346 : 0 : gcond *cond_stmt;
347 : :
348 : 0 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
349 : 0 : gcc_assert (gimple_code (*gsi) == GIMPLE_COND);
350 : :
351 : 0 : condition = force_gimple_operand_gsi_1 (&gsi, condition,
352 : : is_gimple_condexpr_for_cond,
353 : : NULL_TREE, true, GSI_SAME_STMT);
354 : 0 : cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
355 : 0 : gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
356 : 0 : gsi_remove (&gsi, true);
357 : 0 : }
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 : 0 : invariant_in_sese_p_rec (tree t, const sese_l ®ion, bool *has_vdefs)
365 : : {
366 : 0 : if (!defined_in_sese_p (t, region))
367 : : return true;
368 : :
369 : 0 : gimple *stmt = SSA_NAME_DEF_STMT (t);
370 : :
371 : 0 : if (gimple_code (stmt) == GIMPLE_PHI
372 : 0 : || gimple_code (stmt) == GIMPLE_CALL)
373 : : return false;
374 : :
375 : : /* VDEF is variant when it is in the region. */
376 : 0 : if (gimple_vdef (stmt))
377 : : {
378 : 0 : if (has_vdefs)
379 : 0 : *has_vdefs = true;
380 : 0 : return false;
381 : : }
382 : :
383 : : /* A VUSE may or may not be variant following the VDEFs. */
384 : 0 : if (tree vuse = gimple_vuse (stmt))
385 : : return invariant_in_sese_p_rec (vuse, region, has_vdefs);
386 : :
387 : 0 : ssa_op_iter iter;
388 : 0 : use_operand_p use_p;
389 : 0 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
390 : : {
391 : 0 : tree use = USE_FROM_PTR (use_p);
392 : :
393 : 0 : if (!defined_in_sese_p (use, region))
394 : 0 : continue;
395 : :
396 : 0 : if (!invariant_in_sese_p_rec (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 : 31226 : scev_analyzable_p (tree def, sese_l ®ion)
408 : : {
409 : 31226 : loop_p loop;
410 : 31226 : tree scev;
411 : 31226 : 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 : 31226 : if (!INTEGRAL_TYPE_P (type)
420 : 6241 : && !POINTER_TYPE_P (type))
421 : : return false;
422 : :
423 : 26626 : loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
424 : 26626 : scev = scalar_evolution_in_region (region, loop, def);
425 : :
426 : 26626 : return (!chrec_contains_undetermined (scev)
427 : 20870 : && (TREE_CODE (scev) != SSA_NAME
428 : 1238 : || !defined_in_sese_p (scev, region))
429 : 20870 : && scev_is_linear_expression (scev)
430 : 47321 : && (! loop
431 : 20092 : || ! loop_in_sese_p (loop, region)
432 : 19390 : || ! 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 : 33646 : scalar_evolution_in_region (const sese_l ®ion, loop_p loop, tree t)
440 : : {
441 : : /* SCOP parameters. */
442 : 33646 : if (TREE_CODE (t) == SSA_NAME
443 : 33646 : && !defined_in_sese_p (t, region))
444 : : return t;
445 : :
446 : 31386 : if (!loop_in_sese_p (loop, region))
447 : 403 : loop = NULL;
448 : :
449 : 31386 : return instantiate_scev (region.entry, loop,
450 : 31386 : analyze_scalar_evolution (loop, t));
451 : : }
452 : :
453 : : /* Return true if BB is empty, contains only DEBUG_INSNs. */
454 : :
455 : : bool
456 : 1767 : sese_trivially_empty_bb_p (basic_block bb)
457 : : {
458 : 1767 : gimple_stmt_iterator gsi;
459 : :
460 : 3534 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
461 : 0 : if (!is_gimple_debug (gsi_stmt (gsi))
462 : 0 : && gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
463 : : return false;
464 : :
465 : : return true;
466 : : }
467 : :
468 : : /* Pretty print edge E to FILE. */
469 : :
470 : : void
471 : 1394 : print_edge (FILE *file, const_edge e)
472 : : {
473 : 1394 : fprintf (file, "edge (bb_%d, bb_%d)", e->src->index, e->dest->index);
474 : 1394 : }
475 : :
476 : : /* Pretty print sese S to FILE. */
477 : :
478 : : void
479 : 697 : print_sese (FILE *file, const sese_l &s)
480 : : {
481 : 697 : fprintf (file, "(entry_"); print_edge (file, s.entry);
482 : 697 : fprintf (file, ", exit_"); print_edge (file, s.exit);
483 : 697 : fprintf (file, ")\n");
484 : 697 : }
485 : :
486 : : /* Pretty print edge E to STDERR. */
487 : :
488 : : DEBUG_FUNCTION void
489 : 0 : debug_edge (const_edge e)
490 : : {
491 : 0 : print_edge (stderr, e);
492 : 0 : fprintf (stderr, "\n");
493 : 0 : }
494 : :
495 : : /* Pretty print sese S to STDERR. */
496 : :
497 : : DEBUG_FUNCTION void
498 : 0 : debug_sese (const sese_l &s)
499 : : {
500 : 0 : print_sese (stderr, s);
501 : 0 : }
|
