1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008-2024 Free Software Foundation, Inc.
3 Contributed by Jan Sjodin <jan.sjodin@amd.com> and
4 Sebastian Pop <sebastian.pop@amd.com>.
6 This file is part of GCC.
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)
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.
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/>. */
23 #define INCLUDE_MEMORY
25 #include "coretypes.h"
30 #include "tree-pass.h"
32 #include "tree-pretty-print.h"
33 #include "fold-const.h"
35 #include "gimple-iterator.h"
36 #include "gimple-pretty-print.h"
37 #include "gimplify-me.h"
39 #include "tree-ssa-loop.h"
40 #include "tree-into-ssa.h"
42 #include "tree-data-ref.h"
43 #include "tree-scalar-evolution.h"
44 #include "tree-ssa-propagate.h"
48 /* For a USE in BB, if BB is outside REGION, mark the USE in the
52 sese_build_liveouts_use (sese_info_p region
, bitmap liveouts
, basic_block bb
,
55 gcc_assert (!bb_in_sese_p (bb
, region
->region
));
56 if (TREE_CODE (use
) != SSA_NAME
)
59 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (use
));
61 if (!def_bb
|| !bb_in_sese_p (def_bb
, region
->region
))
64 unsigned ver
= SSA_NAME_VERSION (use
);
65 bitmap_set_bit (liveouts
, ver
);
68 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
69 used in BB that is outside of the REGION. */
72 sese_build_liveouts_bb (sese_info_p region
, basic_block bb
)
77 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
79 FOR_EACH_PHI_ARG (use_p
, bsi
.phi (), iter
, SSA_OP_USE
)
80 sese_build_liveouts_use (region
, region
->liveout
,
81 bb
, USE_FROM_PTR (use_p
));
83 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
86 gimple
*stmt
= gsi_stmt (bsi
);
88 bitmap liveouts
= region
->liveout
;
89 if (is_gimple_debug (stmt
))
90 liveouts
= region
->debug_liveout
;
92 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
93 sese_build_liveouts_use (region
, liveouts
, bb
, USE_FROM_PTR (use_p
));
97 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
98 are not marked as liveouts. */
101 sese_reset_debug_liveouts (sese_info_p region
)
105 EXECUTE_IF_AND_COMPL_IN_BITMAP (region
->debug_liveout
, region
->liveout
,
108 tree name
= ssa_name (i
);
109 auto_vec
<gimple
*, 4> stmts
;
111 imm_use_iterator use_iter
;
112 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, name
)
114 if (! is_gimple_debug (use_stmt
)
115 || bb_in_sese_p (gimple_bb (use_stmt
), region
->region
))
117 stmts
.safe_push (use_stmt
);
119 while (!stmts
.is_empty ())
121 gimple
*stmt
= stmts
.pop ();
122 gimple_debug_bind_reset_value (stmt
);
128 /* Build the LIVEOUTS of REGION: the set of variables defined inside
129 and used outside the REGION. */
132 sese_build_liveouts (sese_info_p region
)
136 gcc_assert (region
->liveout
== NULL
137 && region
->debug_liveout
== NULL
);
139 region
->liveout
= BITMAP_ALLOC (NULL
);
140 region
->debug_liveout
= BITMAP_ALLOC (NULL
);
142 /* FIXME: We could start iterating form the successor of sese. */
143 FOR_EACH_BB_FN (bb
, cfun
)
144 if (!bb_in_sese_p (bb
, region
->region
))
145 sese_build_liveouts_bb (region
, bb
);
148 /* Builds a new SESE region from edges ENTRY and EXIT. */
151 new_sese_info (edge entry
, edge exit
)
153 sese_info_p region
= XNEW (class sese_info_t
);
155 region
->region
.entry
= entry
;
156 region
->region
.exit
= exit
;
157 region
->liveout
= NULL
;
158 region
->debug_liveout
= NULL
;
159 region
->params
.create (3);
160 region
->rename_map
= new hash_map
<tree
, tree
>;
161 region
->bbs
.create (3);
166 /* Deletes REGION. */
169 free_sese_info (sese_info_p region
)
171 region
->params
.release ();
172 BITMAP_FREE (region
->liveout
);
173 BITMAP_FREE (region
->debug_liveout
);
175 delete region
->rename_map
;
176 region
->rename_map
= NULL
;
177 region
->bbs
.release ();
182 /* Add exit phis for USE on EXIT. */
185 sese_add_exit_phis_edge (basic_block exit
, tree use
, edge false_e
, edge true_e
)
187 gphi
*phi
= create_phi_node (NULL_TREE
, exit
);
188 create_new_def_for (use
, phi
, gimple_phi_result_ptr (phi
));
189 add_phi_arg (phi
, use
, false_e
, UNKNOWN_LOCATION
);
190 add_phi_arg (phi
, use
, true_e
, UNKNOWN_LOCATION
);
194 /* Insert in the block BB phi nodes for variables defined in REGION
195 and used outside the REGION. The code generation moves REGION in
196 the else clause of an "if (1)" and generates code in the then
197 clause that is at this point empty:
206 sese_insert_phis_for_liveouts (sese_info_p region
, basic_block bb
,
207 edge false_e
, edge true_e
)
209 if (MAY_HAVE_DEBUG_BIND_STMTS
)
210 sese_reset_debug_liveouts (region
);
214 EXECUTE_IF_SET_IN_BITMAP (region
->liveout
, 0, i
, bi
)
215 if (!virtual_operand_p (ssa_name (i
)))
216 sese_add_exit_phis_edge (bb
, ssa_name (i
), false_e
, true_e
);
219 /* Returns the outermost loop in SCOP that contains BB. */
222 outermost_loop_in_sese_1 (sese_l
®ion
, basic_block bb
)
226 nest
= bb
->loop_father
;
227 while (loop_outer (nest
)
228 && loop_in_sese_p (loop_outer (nest
), region
))
229 nest
= loop_outer (nest
);
234 /* Same as outermost_loop_in_sese_1, returns the outermost loop
235 containing BB in REGION, but makes sure that the returned loop
236 belongs to the REGION, and so this returns the first loop in the
237 REGION when the loop containing BB does not belong to REGION. */
240 outermost_loop_in_sese (sese_l
®ion
, basic_block bb
)
242 loop_p nest
= outermost_loop_in_sese_1 (region
, bb
);
244 if (loop_in_sese_p (nest
, region
))
247 /* When the basic block BB does not belong to a loop in the region,
248 return the first loop in the region. */
251 if (loop_in_sese_p (nest
, region
))
260 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
263 get_true_edge_from_guard_bb (basic_block bb
)
268 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
269 if (e
->flags
& EDGE_TRUE_VALUE
)
276 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
279 get_false_edge_from_guard_bb (basic_block bb
)
284 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
285 if (!(e
->flags
& EDGE_TRUE_VALUE
))
292 /* Moves REGION in a condition expression:
300 move_sese_in_condition (sese_info_p region
)
302 basic_block region_entry_dest
= region
->region
.entry
->dest
;
303 basic_block pred_block
= split_edge (region
->region
.entry
);
304 basic_block merge_block
= split_edge (region
->region
.exit
);
306 edge true_edge
= make_edge (pred_block
, merge_block
, EDGE_TRUE_VALUE
);
307 edge false_edge
= find_edge (pred_block
, region_entry_dest
);
308 false_edge
->flags
&= ~EDGE_FALLTHRU
;
309 false_edge
->flags
|= EDGE_FALSE_VALUE
;
310 gimple_stmt_iterator gsi
= gsi_last_bb (pred_block
);
311 gcond
*cond
= gimple_build_cond (NE_EXPR
, integer_one_node
, integer_zero_node
,
312 NULL_TREE
, NULL_TREE
);
313 gsi_insert_after (&gsi
, cond
, GSI_CONTINUE_LINKING
);
314 if (dom_info_available_p (CDI_DOMINATORS
))
315 set_immediate_dominator (CDI_DOMINATORS
, merge_block
, pred_block
);
317 ifsese if_region
= XNEW (ifsese_s
);
318 if_region
->region
= XCNEW (sese_info_t
);
319 if_region
->true_region
= XCNEW (sese_info_t
);
320 if_region
->false_region
= XCNEW (sese_info_t
);
321 if_region
->region
->region
.entry
= single_pred_edge (pred_block
);
322 if_region
->region
->region
.exit
= single_succ_edge (merge_block
);
323 if_region
->false_region
->region
.entry
= false_edge
;
324 if_region
->false_region
->region
.exit
= region
->region
.exit
;
325 if_region
->true_region
->region
.entry
= true_edge
;
326 if_region
->true_region
->region
.exit
327 = single_succ_edge (split_edge (true_edge
));
329 region
->region
= if_region
->false_region
->region
;
334 /* Replaces the condition of the IF_REGION with CONDITION:
342 set_ifsese_condition (ifsese if_region
, tree condition
)
344 sese_info_p region
= if_region
->region
;
345 edge entry
= region
->region
.entry
;
346 basic_block bb
= entry
->dest
;
349 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
350 gcc_assert (gimple_code (*gsi
) == GIMPLE_COND
);
352 condition
= force_gimple_operand_gsi_1 (&gsi
, condition
,
353 is_gimple_condexpr_for_cond
,
354 NULL_TREE
, true, GSI_SAME_STMT
);
355 cond_stmt
= gimple_build_cond_from_tree (condition
, NULL_TREE
, NULL_TREE
);
356 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
357 gsi_remove (&gsi
, true);
360 /* Return true when T is defined outside REGION or when no definitions are
361 variant in REGION. When HAS_VDEFS is a valid pointer, sets HAS_VDEFS to true
362 when T depends on memory that may change in REGION. */
365 invariant_in_sese_p_rec (tree t
, const sese_l
®ion
, bool *has_vdefs
)
367 if (!defined_in_sese_p (t
, region
))
370 gimple
*stmt
= SSA_NAME_DEF_STMT (t
);
372 if (gimple_code (stmt
) == GIMPLE_PHI
373 || gimple_code (stmt
) == GIMPLE_CALL
)
376 /* VDEF is variant when it is in the region. */
377 if (gimple_vdef (stmt
))
384 /* A VUSE may or may not be variant following the VDEFs. */
385 if (tree vuse
= gimple_vuse (stmt
))
386 return invariant_in_sese_p_rec (vuse
, region
, has_vdefs
);
390 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
392 tree use
= USE_FROM_PTR (use_p
);
394 if (!defined_in_sese_p (use
, region
))
397 if (!invariant_in_sese_p_rec (use
, region
, has_vdefs
))
404 /* Return true when DEF can be analyzed in REGION by the scalar
405 evolution analyzer. */
408 scev_analyzable_p (tree def
, sese_l
®ion
)
412 tree type
= TREE_TYPE (def
);
414 /* When Graphite generates code for a scev, the code generator
415 expresses the scev in function of a single induction variable.
416 This is unsafe for floating point computations, as it may replace
417 a floating point sum reduction with a multiplication. The
418 following test returns false for non integer types to avoid such
420 if (!INTEGRAL_TYPE_P (type
)
421 && !POINTER_TYPE_P (type
))
424 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
425 scev
= scalar_evolution_in_region (region
, loop
, def
);
427 return (!chrec_contains_undetermined (scev
)
428 && (TREE_CODE (scev
) != SSA_NAME
429 || !defined_in_sese_p (scev
, region
))
430 && scev_is_linear_expression (scev
)
432 || ! loop_in_sese_p (loop
, region
)
433 || ! chrec_contains_symbols_defined_in_loop (scev
, loop
->num
)));
436 /* Returns the scalar evolution of T in REGION. Every variable that
437 is not defined in the REGION is considered a parameter. */
440 scalar_evolution_in_region (const sese_l
®ion
, loop_p loop
, tree t
)
442 /* SCOP parameters. */
443 if (TREE_CODE (t
) == SSA_NAME
444 && !defined_in_sese_p (t
, region
))
447 if (!loop_in_sese_p (loop
, region
))
450 return instantiate_scev (region
.entry
, loop
,
451 analyze_scalar_evolution (loop
, t
));
454 /* Return true if BB is empty, contains only DEBUG_INSNs. */
457 sese_trivially_empty_bb_p (basic_block bb
)
459 gimple_stmt_iterator gsi
;
461 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
462 if (!is_gimple_debug (gsi_stmt (gsi
))
463 && gimple_code (gsi_stmt (gsi
)) != GIMPLE_LABEL
)
469 /* Pretty print edge E to FILE. */
472 print_edge (FILE *file
, const_edge e
)
474 fprintf (file
, "edge (bb_%d, bb_%d)", e
->src
->index
, e
->dest
->index
);
477 /* Pretty print sese S to FILE. */
480 print_sese (FILE *file
, const sese_l
&s
)
482 fprintf (file
, "(entry_"); print_edge (file
, s
.entry
);
483 fprintf (file
, ", exit_"); print_edge (file
, s
.exit
);
484 fprintf (file
, ")\n");
487 /* Pretty print edge E to STDERR. */
490 debug_edge (const_edge e
)
492 print_edge (stderr
, e
);
495 /* Pretty print sese S to STDERR. */
498 debug_sese (const sese_l
&s
)
500 print_sese (stderr
, s
);