1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008-2013 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 /* A Single Entry, Single Exit region is a part of the CFG delimited
29 /* Single ENTRY and single EXIT from the SESE region. */
32 /* Parameters used within the SCOP. */
35 /* Loops completely contained in the SCOP. */
37 vec
<loop_p
> loop_nest
;
39 /* Are we allowed to add more params? This is for debugging purpose. We
40 can only add new params before generating the bb domains, otherwise they
45 #define SESE_ENTRY(S) (S->entry)
46 #define SESE_ENTRY_BB(S) (S->entry->dest)
47 #define SESE_EXIT(S) (S->exit)
48 #define SESE_EXIT_BB(S) (S->exit->dest)
49 #define SESE_PARAMS(S) (S->params)
50 #define SESE_LOOPS(S) (S->loops)
51 #define SESE_LOOP_NEST(S) (S->loop_nest)
52 #define SESE_ADD_PARAMS(S) (S->add_params)
54 extern sese
new_sese (edge
, edge
);
55 extern void free_sese (sese
);
56 extern void sese_insert_phis_for_liveouts (sese
, basic_block
, edge
, edge
);
57 extern void build_sese_loop_nests (sese
);
58 extern edge
copy_bb_and_scalar_dependences (basic_block
, sese
, edge
,
60 extern struct loop
*outermost_loop_in_sese (sese
, basic_block
);
61 extern void insert_loop_close_phis (htab_t
, loop_p
);
62 extern void insert_guard_phis (basic_block
, edge
, edge
, htab_t
, htab_t
);
63 extern tree
scalar_evolution_in_region (sese
, loop_p
, tree
);
65 /* Check that SESE contains LOOP. */
68 sese_contains_loop (sese sese
, struct loop
*loop
)
70 return bitmap_bit_p (SESE_LOOPS (sese
), loop
->num
);
73 /* The number of parameters in REGION. */
75 static inline unsigned
76 sese_nb_params (sese region
)
78 return SESE_PARAMS (region
).length ();
81 /* Checks whether BB is contained in the region delimited by ENTRY and
85 bb_in_region (basic_block bb
, basic_block entry
, basic_block exit
)
87 #ifdef ENABLE_CHECKING
92 /* Check that there are no edges coming in the region: all the
93 predecessors of EXIT are dominated by ENTRY. */
94 FOR_EACH_EDGE (e
, ei
, exit
->preds
)
95 dominated_by_p (CDI_DOMINATORS
, e
->src
, entry
);
99 return dominated_by_p (CDI_DOMINATORS
, bb
, entry
)
100 && !(dominated_by_p (CDI_DOMINATORS
, bb
, exit
)
101 && !dominated_by_p (CDI_DOMINATORS
, entry
, exit
));
104 /* Checks whether BB is contained in the region delimited by ENTRY and
108 bb_in_sese_p (basic_block bb
, sese region
)
110 basic_block entry
= SESE_ENTRY_BB (region
);
111 basic_block exit
= SESE_EXIT_BB (region
);
113 return bb_in_region (bb
, entry
, exit
);
116 /* Returns true when STMT is defined in REGION. */
119 stmt_in_sese_p (gimple stmt
, sese region
)
121 basic_block bb
= gimple_bb (stmt
);
122 return bb
&& bb_in_sese_p (bb
, region
);
125 /* Returns true when NAME is defined in REGION. */
128 defined_in_sese_p (tree name
, sese region
)
130 gimple stmt
= SSA_NAME_DEF_STMT (name
);
131 return stmt_in_sese_p (stmt
, region
);
134 /* Returns true when LOOP is in REGION. */
137 loop_in_sese_p (struct loop
*loop
, sese region
)
139 return (bb_in_sese_p (loop
->header
, region
)
140 && bb_in_sese_p (loop
->latch
, region
));
143 /* Returns the loop depth of LOOP in REGION. The loop depth
144 is the same as the normal loop depth, but limited by a region.
162 loop_0 does not exist in the region -> invalid
163 loop_1 exists, but is not completely contained in the region -> depth 0
164 loop_2 is completely contained -> depth 1 */
166 static inline unsigned int
167 sese_loop_depth (sese region
, loop_p loop
)
169 unsigned int depth
= 0;
171 gcc_assert ((!loop_in_sese_p (loop
, region
)
172 && (SESE_ENTRY_BB (region
)->loop_father
== loop
173 || SESE_EXIT (region
)->src
->loop_father
== loop
))
174 || loop_in_sese_p (loop
, region
));
176 while (loop_in_sese_p (loop
, region
))
179 loop
= loop_outer (loop
);
185 /* Splits BB to make a single entry single exit region. */
188 split_region_for_bb (basic_block bb
)
192 if (single_pred_p (bb
))
193 entry
= single_pred_edge (bb
);
196 entry
= split_block_after_labels (bb
);
197 bb
= single_succ (bb
);
200 if (single_succ_p (bb
))
201 exit
= single_succ_edge (bb
);
204 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
206 exit
= split_block (bb
, gsi_stmt (gsi
));
209 return new_sese (entry
, exit
);
212 /* Returns the block preceding the entry of a SESE. */
214 static inline basic_block
215 block_before_sese (sese sese
)
217 return SESE_ENTRY (sese
)->src
;
222 /* A single entry single exit specialized for conditions. */
224 typedef struct ifsese_s
{
230 extern void if_region_set_false_region (ifsese
, sese
);
231 extern ifsese
move_sese_in_condition (sese
);
232 extern edge
get_true_edge_from_guard_bb (basic_block
);
233 extern edge
get_false_edge_from_guard_bb (basic_block
);
234 extern void set_ifsese_condition (ifsese
, tree
);
237 if_region_entry (ifsese if_region
)
239 return SESE_ENTRY (if_region
->region
);
243 if_region_exit (ifsese if_region
)
245 return SESE_EXIT (if_region
->region
);
248 static inline basic_block
249 if_region_get_condition_block (ifsese if_region
)
251 return if_region_entry (if_region
)->dest
;
254 /* Structure containing the mapping between the old names and the new
255 names used after block copy in the new loop context. */
256 typedef struct rename_map_elt_s
262 extern void debug_rename_map (htab_t
);
263 extern hashval_t
rename_map_elt_info (const void *);
264 extern int eq_rename_map_elts (const void *, const void *);
266 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
268 static inline rename_map_elt
269 new_rename_map_elt (tree old_name
, tree expr
)
273 res
= XNEW (struct rename_map_elt_s
);
274 res
->old_name
= old_name
;
280 /* Structure containing the mapping between the CLooG's induction
281 variable and the type of the old induction variable. */
282 typedef struct ivtype_map_elt_s
285 const char *cloog_iv
;
288 extern void debug_ivtype_map (htab_t
);
289 extern hashval_t
ivtype_map_elt_info (const void *);
290 extern int eq_ivtype_map_elts (const void *, const void *);
292 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
294 static inline ivtype_map_elt
295 new_ivtype_map_elt (const char *cloog_iv
, tree type
)
299 res
= XNEW (struct ivtype_map_elt_s
);
300 res
->cloog_iv
= cloog_iv
;
306 /* Free and compute again all the dominators information. */
309 recompute_all_dominators (void)
311 mark_irreducible_loops ();
312 free_dominance_info (CDI_DOMINATORS
);
313 calculate_dominance_info (CDI_DOMINATORS
);
316 typedef struct gimple_bb
321 /* Lists containing the restrictions of the conditional statements
322 dominating this bb. This bb can only be executed, if all conditions
327 for (i = 0; i <= 20; i++)
335 So for B there is an additional condition (2i <= 8).
337 List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the
338 corresponding element in CONDITION_CASES is not NULL_TREE. For a
339 SWITCH_EXPR the corresponding element in CONDITION_CASES is a
341 vec
<gimple
> conditions
;
342 vec
<gimple
> condition_cases
;
343 vec
<data_reference_p
> data_refs
;
346 #define GBB_BB(GBB) (GBB)->bb
347 #define GBB_PBB(GBB) (GBB)->pbb
348 #define GBB_DATA_REFS(GBB) (GBB)->data_refs
349 #define GBB_CONDITIONS(GBB) (GBB)->conditions
350 #define GBB_CONDITION_CASES(GBB) (GBB)->condition_cases
352 /* Return the innermost loop that contains the basic block GBB. */
354 static inline struct loop
*
355 gbb_loop (struct gimple_bb
*gbb
)
357 return GBB_BB (gbb
)->loop_father
;
360 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
361 If there is no corresponding gimple loop, we return NULL. */
364 gbb_loop_at_index (gimple_bb_p gbb
, sese region
, int index
)
366 loop_p loop
= gbb_loop (gbb
);
367 int depth
= sese_loop_depth (region
, loop
);
369 while (--depth
> index
)
370 loop
= loop_outer (loop
);
372 gcc_assert (sese_contains_loop (region
, loop
));
377 /* The number of common loops in REGION for GBB1 and GBB2. */
380 nb_common_loops (sese region
, gimple_bb_p gbb1
, gimple_bb_p gbb2
)
382 loop_p l1
= gbb_loop (gbb1
);
383 loop_p l2
= gbb_loop (gbb2
);
384 loop_p common
= find_common_loop (l1
, l2
);
386 return sese_loop_depth (region
, common
);
389 /* Return true when DEF can be analyzed in REGION by the scalar
390 evolution analyzer. */
393 scev_analyzable_p (tree def
, sese region
)
397 tree type
= TREE_TYPE (def
);
399 /* When Graphite generates code for a scev, the code generator
400 expresses the scev in function of a single induction variable.
401 This is unsafe for floating point computations, as it may replace
402 a floating point sum reduction with a multiplication. The
403 following test returns false for non integer types to avoid such
405 if (!INTEGRAL_TYPE_P (type
)
406 && !POINTER_TYPE_P (type
))
409 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
410 scev
= scalar_evolution_in_region (region
, loop
, def
);
412 return !chrec_contains_undetermined (scev
)
413 && (TREE_CODE (scev
) != SSA_NAME
414 || !defined_in_sese_p (scev
, region
))
415 && (tree_does_not_contain_chrecs (scev
)
416 || evolution_function_is_affine_p (scev
));