1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008-2015 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/>. */
25 typedef hash_map
<tree
, tree
> parameter_rename_map_t
;
27 /* A Single Entry, Single Exit region is a part of the CFG delimited
31 /* Single ENTRY and single EXIT from the SESE region. */
34 /* Parameters used within the SCOP. */
37 /* Parameters to be renamed. */
38 parameter_rename_map_t
*parameter_rename_map
;
40 /* Loops completely contained in the SCOP. */
42 vec
<loop_p
> loop_nest
;
44 /* Are we allowed to add more params? This is for debugging purpose. We
45 can only add new params before generating the bb domains, otherwise they
50 #define SESE_ENTRY(S) (S->entry)
51 #define SESE_ENTRY_BB(S) (S->entry->dest)
52 #define SESE_EXIT(S) (S->exit)
53 #define SESE_EXIT_BB(S) (S->exit->dest)
54 #define SESE_PARAMS(S) (S->params)
55 #define SESE_LOOPS(S) (S->loops)
56 #define SESE_LOOP_NEST(S) (S->loop_nest)
57 #define SESE_ADD_PARAMS(S) (S->add_params)
59 extern sese
new_sese (edge
, edge
);
60 extern void free_sese (sese
);
61 extern void sese_insert_phis_for_liveouts (sese
, basic_block
, edge
, edge
);
62 extern void build_sese_loop_nests (sese
);
63 extern edge
copy_bb_and_scalar_dependences (basic_block
, sese
, edge
,
65 extern struct loop
*outermost_loop_in_sese (sese
, basic_block
);
66 extern tree
scalar_evolution_in_region (sese
, loop_p
, tree
);
68 /* Check that SESE contains LOOP. */
71 sese_contains_loop (sese sese
, struct loop
*loop
)
73 return bitmap_bit_p (SESE_LOOPS (sese
), loop
->num
);
76 /* The number of parameters in REGION. */
78 static inline unsigned
79 sese_nb_params (sese region
)
81 return SESE_PARAMS (region
).length ();
84 /* Checks whether BB is contained in the region delimited by ENTRY and
88 bb_in_region (basic_block bb
, basic_block entry
, basic_block exit
)
90 #ifdef ENABLE_CHECKING
95 /* Check that there are no edges coming in the region: all the
96 predecessors of EXIT are dominated by ENTRY. */
97 FOR_EACH_EDGE (e
, ei
, exit
->preds
)
98 dominated_by_p (CDI_DOMINATORS
, e
->src
, entry
);
102 return dominated_by_p (CDI_DOMINATORS
, bb
, entry
)
103 && !(dominated_by_p (CDI_DOMINATORS
, bb
, exit
)
104 && !dominated_by_p (CDI_DOMINATORS
, entry
, exit
));
107 /* Checks whether BB is contained in the region delimited by ENTRY and
111 bb_in_sese_p (basic_block bb
, sese region
)
113 basic_block entry
= SESE_ENTRY_BB (region
);
114 basic_block exit
= SESE_EXIT_BB (region
);
116 return bb_in_region (bb
, entry
, exit
);
119 /* Returns true when STMT is defined in REGION. */
122 stmt_in_sese_p (gimple
*stmt
, sese region
)
124 basic_block bb
= gimple_bb (stmt
);
125 return bb
&& bb_in_sese_p (bb
, region
);
128 /* Returns true when NAME is defined in REGION. */
131 defined_in_sese_p (tree name
, sese region
)
133 gimple
*stmt
= SSA_NAME_DEF_STMT (name
);
134 return stmt_in_sese_p (stmt
, region
);
137 /* Returns true when LOOP is in REGION. */
140 loop_in_sese_p (struct loop
*loop
, sese region
)
142 return (bb_in_sese_p (loop
->header
, region
)
143 && bb_in_sese_p (loop
->latch
, region
));
146 /* Returns the loop depth of LOOP in REGION. The loop depth
147 is the same as the normal loop depth, but limited by a region.
165 loop_0 does not exist in the region -> invalid
166 loop_1 exists, but is not completely contained in the region -> depth 0
167 loop_2 is completely contained -> depth 1 */
169 static inline unsigned int
170 sese_loop_depth (sese region
, loop_p loop
)
172 unsigned int depth
= 0;
174 gcc_assert ((!loop_in_sese_p (loop
, region
)
175 && (SESE_ENTRY_BB (region
)->loop_father
== loop
176 || SESE_EXIT (region
)->src
->loop_father
== loop
))
177 || loop_in_sese_p (loop
, region
));
179 while (loop_in_sese_p (loop
, region
))
182 loop
= loop_outer (loop
);
188 /* Splits BB to make a single entry single exit region. */
191 split_region_for_bb (basic_block bb
)
195 if (single_pred_p (bb
))
196 entry
= single_pred_edge (bb
);
199 entry
= split_block_after_labels (bb
);
200 bb
= single_succ (bb
);
203 if (single_succ_p (bb
))
204 exit
= single_succ_edge (bb
);
207 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
209 exit
= split_block (bb
, gsi_stmt (gsi
));
212 return new_sese (entry
, exit
);
215 /* Returns the block preceding the entry of a SESE. */
217 static inline basic_block
218 block_before_sese (sese sese
)
220 return SESE_ENTRY (sese
)->src
;
225 /* A single entry single exit specialized for conditions. */
227 typedef struct ifsese_s
{
233 extern void if_region_set_false_region (ifsese
, sese
);
234 extern ifsese
move_sese_in_condition (sese
);
235 extern edge
get_true_edge_from_guard_bb (basic_block
);
236 extern edge
get_false_edge_from_guard_bb (basic_block
);
237 extern void set_ifsese_condition (ifsese
, tree
);
240 if_region_entry (ifsese if_region
)
242 return SESE_ENTRY (if_region
->region
);
246 if_region_exit (ifsese if_region
)
248 return SESE_EXIT (if_region
->region
);
251 static inline basic_block
252 if_region_get_condition_block (ifsese if_region
)
254 return if_region_entry (if_region
)->dest
;
257 /* Free and compute again all the dominators information. */
260 recompute_all_dominators (void)
262 mark_irreducible_loops ();
263 free_dominance_info (CDI_DOMINATORS
);
264 calculate_dominance_info (CDI_DOMINATORS
);
267 typedef struct gimple_bb
272 /* Lists containing the restrictions of the conditional statements
273 dominating this bb. This bb can only be executed, if all conditions
278 for (i = 0; i <= 20; i++)
286 So for B there is an additional condition (2i <= 8).
288 List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the
289 corresponding element in CONDITION_CASES is not NULL_TREE. For a
290 SWITCH_EXPR the corresponding element in CONDITION_CASES is a
292 vec
<gimple
*> conditions
;
293 vec
<gimple
*> condition_cases
;
294 vec
<data_reference_p
> data_refs
;
297 #define GBB_BB(GBB) (GBB)->bb
298 #define GBB_PBB(GBB) (GBB)->pbb
299 #define GBB_DATA_REFS(GBB) (GBB)->data_refs
300 #define GBB_CONDITIONS(GBB) (GBB)->conditions
301 #define GBB_CONDITION_CASES(GBB) (GBB)->condition_cases
303 /* Return the innermost loop that contains the basic block GBB. */
305 static inline struct loop
*
306 gbb_loop (struct gimple_bb
*gbb
)
308 return GBB_BB (gbb
)->loop_father
;
311 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
312 If there is no corresponding gimple loop, we return NULL. */
315 gbb_loop_at_index (gimple_bb_p gbb
, sese region
, int index
)
317 loop_p loop
= gbb_loop (gbb
);
318 int depth
= sese_loop_depth (region
, loop
);
320 while (--depth
> index
)
321 loop
= loop_outer (loop
);
323 gcc_assert (sese_contains_loop (region
, loop
));
328 /* The number of common loops in REGION for GBB1 and GBB2. */
331 nb_common_loops (sese region
, gimple_bb_p gbb1
, gimple_bb_p gbb2
)
333 loop_p l1
= gbb_loop (gbb1
);
334 loop_p l2
= gbb_loop (gbb2
);
335 loop_p common
= find_common_loop (l1
, l2
);
337 return sese_loop_depth (region
, common
);
340 /* Return true when DEF can be analyzed in REGION by the scalar
341 evolution analyzer. */
344 scev_analyzable_p (tree def
, sese region
)
348 tree type
= TREE_TYPE (def
);
350 /* When Graphite generates code for a scev, the code generator
351 expresses the scev in function of a single induction variable.
352 This is unsafe for floating point computations, as it may replace
353 a floating point sum reduction with a multiplication. The
354 following test returns false for non integer types to avoid such
356 if (!INTEGRAL_TYPE_P (type
)
357 && !POINTER_TYPE_P (type
))
360 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
361 scev
= scalar_evolution_in_region (region
, loop
, def
);
363 return !chrec_contains_undetermined (scev
)
364 && (TREE_CODE (scev
) != SSA_NAME
365 || !defined_in_sese_p (scev
, region
))
366 && (tree_does_not_contain_chrecs (scev
)
367 || evolution_function_is_affine_p (scev
));