Line data Source code
1 : /* Single entry single exit control flow regions.
2 : Copyright (C) 2008-2026 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 5147 : sese_build_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb,
52 : tree use)
53 : {
54 5147 : gcc_assert (!bb_in_sese_p (bb, region->region));
55 5147 : if (TREE_CODE (use) != SSA_NAME)
56 : return;
57 :
58 4483 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
59 :
60 4483 : if (!def_bb || !bb_in_sese_p (def_bb, region->region))
61 4406 : return;
62 :
63 77 : unsigned ver = SSA_NAME_VERSION (use);
64 77 : 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 2343 : sese_build_liveouts_bb (sese_info_p region, basic_block bb)
72 : {
73 2343 : ssa_op_iter iter;
74 2343 : use_operand_p use_p;
75 :
76 3554 : for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
77 1211 : gsi_next (&bsi))
78 2644 : FOR_EACH_PHI_ARG (use_p, bsi.phi (), iter, SSA_OP_USE)
79 1433 : sese_build_liveouts_use (region, region->liveout,
80 : bb, USE_FROM_PTR (use_p));
81 :
82 9366 : for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
83 4680 : gsi_next (&bsi))
84 : {
85 4680 : gimple *stmt = gsi_stmt (bsi);
86 :
87 4680 : bitmap liveouts = region->liveout;
88 4680 : if (is_gimple_debug (stmt))
89 37 : liveouts = region->debug_liveout;
90 :
91 8394 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
92 3714 : sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
93 : }
94 2343 : }
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 211 : sese_build_liveouts (sese_info_p region)
132 : {
133 211 : basic_block bb;
134 :
135 211 : gcc_assert (region->liveout == NULL
136 : && region->debug_liveout == NULL);
137 :
138 211 : region->liveout = BITMAP_ALLOC (NULL);
139 211 : region->debug_liveout = BITMAP_ALLOC (NULL);
140 :
141 : /* FIXME: We could start iterating form the successor of sese. */
142 4725 : FOR_EACH_BB_FN (bb, cfun)
143 4514 : if (!bb_in_sese_p (bb, region->region))
144 2343 : sese_build_liveouts_bb (region, bb);
145 211 : }
146 :
147 : /* Builds a new SESE region from edges ENTRY and EXIT. */
148 :
149 : sese_info_p
150 211 : new_sese_info (edge entry, edge exit)
151 : {
152 211 : sese_info_p region = XNEW (class sese_info_t);
153 :
154 211 : region->region.entry = entry;
155 211 : region->region.exit = exit;
156 211 : region->liveout = NULL;
157 211 : region->debug_liveout = NULL;
158 211 : region->params.create (3);
159 211 : region->rename_map = new hash_map <tree, tree>;
160 211 : region->bbs.create (3);
161 :
162 211 : return region;
163 : }
164 :
165 : /* Deletes REGION. */
166 :
167 : void
168 211 : free_sese_info (sese_info_p region)
169 : {
170 211 : region->params.release ();
171 211 : BITMAP_FREE (region->liveout);
172 211 : BITMAP_FREE (region->debug_liveout);
173 :
174 422 : delete region->rename_map;
175 211 : region->rename_map = NULL;
176 211 : region->bbs.release ();
177 :
178 211 : XDELETE (region);
179 211 : }
180 :
181 : /* Add exit phis for USE on EXIT. */
182 :
183 : static void
184 55 : sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
185 : {
186 55 : gphi *phi = create_phi_node (NULL_TREE, exit);
187 55 : create_new_def_for (use, phi, gimple_phi_result_ptr (phi));
188 55 : add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
189 55 : add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
190 55 : update_stmt (phi);
191 55 : }
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 161 : sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb,
206 : edge false_e, edge true_e)
207 : {
208 161 : if (MAY_HAVE_DEBUG_BIND_STMTS)
209 4 : sese_reset_debug_liveouts (region);
210 :
211 161 : unsigned i;
212 161 : bitmap_iterator bi;
213 216 : EXECUTE_IF_SET_IN_BITMAP (region->liveout, 0, i, bi)
214 110 : if (!virtual_operand_p (ssa_name (i)))
215 55 : sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
216 161 : }
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 203 : get_true_edge_from_guard_bb (basic_block bb)
263 : {
264 203 : edge e;
265 203 : edge_iterator ei;
266 :
267 203 : FOR_EACH_EDGE (e, ei, bb->succs)
268 203 : if (e->flags & EDGE_TRUE_VALUE)
269 203 : 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 163 : move_sese_in_condition (sese_info_p region)
300 : {
301 163 : basic_block region_entry_dest = region->region.entry->dest;
302 163 : basic_block pred_block = split_edge (region->region.entry);
303 163 : basic_block merge_block = split_edge (region->region.exit);
304 :
305 163 : edge true_edge = make_edge (pred_block, merge_block, EDGE_TRUE_VALUE);
306 163 : edge false_edge = find_edge (pred_block, region_entry_dest);
307 163 : false_edge->flags &= ~EDGE_FALLTHRU;
308 163 : false_edge->flags |= EDGE_FALSE_VALUE;
309 163 : gimple_stmt_iterator gsi = gsi_last_bb (pred_block);
310 163 : gcond *cond = gimple_build_cond (NE_EXPR, integer_one_node, integer_zero_node,
311 : NULL_TREE, NULL_TREE);
312 163 : gsi_insert_after (&gsi, cond, GSI_CONTINUE_LINKING);
313 163 : if (dom_info_available_p (CDI_DOMINATORS))
314 163 : set_immediate_dominator (CDI_DOMINATORS, merge_block, pred_block);
315 :
316 163 : ifsese if_region = XNEW (ifsese_s);
317 163 : if_region->region = XCNEW (sese_info_t);
318 163 : if_region->true_region = XCNEW (sese_info_t);
319 163 : if_region->false_region = XCNEW (sese_info_t);
320 163 : if_region->region->region.entry = single_pred_edge (pred_block);
321 163 : if_region->region->region.exit = single_succ_edge (merge_block);
322 163 : if_region->false_region->region.entry = false_edge;
323 163 : if_region->false_region->region.exit = region->region.exit;
324 163 : if_region->true_region->region.entry = true_edge;
325 163 : if_region->true_region->region.exit
326 163 : = single_succ_edge (split_edge (true_edge));
327 :
328 163 : region->region = if_region->false_region->region;
329 :
330 163 : 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 32399 : scev_analyzable_p (tree def, sese_l ®ion)
408 : {
409 32399 : loop_p loop;
410 32399 : tree scev;
411 32399 : 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 32399 : if (!INTEGRAL_TYPE_P (type)
420 6537 : && !POINTER_TYPE_P (type))
421 : return false;
422 :
423 27565 : loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
424 27565 : scev = scalar_evolution_in_region (region, loop, def);
425 :
426 27565 : return (!chrec_contains_undetermined (scev)
427 21805 : && (TREE_CODE (scev) != SSA_NAME
428 1293 : || !defined_in_sese_p (scev, region))
429 21805 : && scev_is_linear_expression (scev)
430 49163 : && (! loop
431 20991 : || ! loop_in_sese_p (loop, region)
432 20216 : || ! 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 34787 : scalar_evolution_in_region (const sese_l ®ion, loop_p loop, tree t)
440 : {
441 : /* SCOP parameters. */
442 34787 : if (TREE_CODE (t) == SSA_NAME
443 34787 : && !defined_in_sese_p (t, region))
444 : return t;
445 :
446 32446 : if (!loop_in_sese_p (loop, region))
447 449 : loop = NULL;
448 :
449 32446 : return instantiate_scev (region.entry, loop,
450 32446 : analyze_scalar_evolution (loop, t));
451 : }
452 :
453 : /* Return true if BB is empty, contains only DEBUG_INSNs. */
454 :
455 : bool
456 1854 : sese_trivially_empty_bb_p (basic_block bb)
457 : {
458 1854 : gimple_stmt_iterator gsi;
459 :
460 3708 : 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 1406 : print_edge (FILE *file, const_edge e)
472 : {
473 1406 : fprintf (file, "edge (bb_%d, bb_%d)", e->src->index, e->dest->index);
474 1406 : }
475 :
476 : /* Pretty print sese S to FILE. */
477 :
478 : void
479 703 : print_sese (FILE *file, const sese_l &s)
480 : {
481 703 : fprintf (file, "(entry_"); print_edge (file, s.entry);
482 703 : fprintf (file, ", exit_"); print_edge (file, s.exit);
483 703 : fprintf (file, ")\n");
484 703 : }
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 : }
|
