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
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify
9it under the terms of the GNU General Public License as published by
10the Free Software Foundation; either version 3, or (at your option)
11any later version.
12
13GCC is distributed in the hope that it will be useful,
14but WITHOUT ANY WARRANTY; without even the implied warranty of
15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16GNU General Public License for more details.
17
18You should have received a copy of the GNU General Public License
19along 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
50static void
51sese_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
70static void
71sese_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
99static void
100sese_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
130void
131sese_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
149sese_info_p
150new_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
167void
168free_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
183static void
184sese_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
204void
205sese_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
220class loop *
221outermost_loop_in_sese_1 (sese_l &region, 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
238loop_p
239outermost_loop_in_sese (sese_l &region, 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
261edge
262get_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
277edge
278get_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
298ifsese
299move_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
340void
341set_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
363bool
364invariant_in_sese_p_rec (tree t, const sese_l &region, 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
406bool
407scev_analyzable_p (tree def, sese_l &region)
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
438tree
439scalar_evolution_in_region (const sese_l &region, 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
455bool
456sese_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
470void
471print_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
478void
479print_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
488DEBUG_FUNCTION void
489debug_edge (const_edge e)
490{
491 print_edge (stderr, e);
492}
493
494/* Pretty print sese S to STDERR. */
495
496DEBUG_FUNCTION void
497debug_sese (const sese_l &s)
498{
499 print_sese (stderr, s);
500}
501

source code of gcc/sese.cc