1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008, 2009 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. */
33 VEC (tree
, heap
) *params
;
35 /* Used to quickly retrieve the index of a parameter in PARAMS. */
38 /* Store the names of the parameters that are passed to CLooG. */
41 /* Loops completely contained in the SCOP. */
43 VEC (loop_p
, heap
) *loop_nest
;
45 /* Are we allowed to add more params? This is for debugging purpose. We
46 can only add new params before generating the bb domains, otherwise they
51 #define SESE_ENTRY(S) (S->entry)
52 #define SESE_ENTRY_BB(S) (S->entry->dest)
53 #define SESE_EXIT(S) (S->exit)
54 #define SESE_EXIT_BB(S) (S->exit->dest)
55 #define SESE_PARAMS(S) (S->params)
56 #define SESE_PARAMS_INDEX(S) (S->params_index)
57 #define SESE_PARAMS_NAMES(S) (S->params_names)
58 #define SESE_LOOPS(S) (S->loops)
59 #define SESE_LOOP_NEST(S) (S->loop_nest)
60 #define SESE_ADD_PARAMS(S) (S->add_params)
62 extern sese
new_sese (edge
, edge
);
63 extern void free_sese (sese
);
64 extern void sese_insert_phis_for_liveouts (sese
, basic_block
, edge
, edge
);
65 extern void sese_adjust_liveout_phis (sese
, htab_t
, basic_block
, edge
, edge
);
66 extern void build_sese_loop_nests (sese
);
67 extern edge
copy_bb_and_scalar_dependences (basic_block
, sese
, edge
, htab_t
);
68 extern struct loop
*outermost_loop_in_sese (sese
, basic_block
);
69 extern void insert_loop_close_phis (htab_t
, loop_p
);
70 extern void insert_guard_phis (basic_block
, edge
, edge
, htab_t
, htab_t
);
71 extern void sese_reset_aux_in_loops (sese
);
72 extern tree
scalar_evolution_in_region (sese
, loop_p
, tree
);
74 /* Check that SESE contains LOOP. */
77 sese_contains_loop (sese sese
, struct loop
*loop
)
79 return bitmap_bit_p (SESE_LOOPS (sese
), loop
->num
);
82 /* The number of parameters in REGION. */
84 static inline unsigned
85 sese_nb_params (sese region
)
87 return VEC_length (tree
, SESE_PARAMS (region
));
90 /* Checks whether BB is contained in the region delimited by ENTRY and
94 bb_in_region (basic_block bb
, basic_block entry
, basic_block exit
)
96 #ifdef ENABLE_CHECKING
101 /* Check that there are no edges coming in the region: all the
102 predecessors of EXIT are dominated by ENTRY. */
103 FOR_EACH_EDGE (e
, ei
, exit
->preds
)
104 dominated_by_p (CDI_DOMINATORS
, e
->src
, entry
);
106 /* Check that there are no edges going out of the region: the
107 entry is post-dominated by the exit. FIXME: This cannot be
108 checked right now as the CDI_POST_DOMINATORS are needed. */
112 return dominated_by_p (CDI_DOMINATORS
, bb
, entry
)
113 && !(dominated_by_p (CDI_DOMINATORS
, bb
, exit
)
114 && !dominated_by_p (CDI_DOMINATORS
, entry
, exit
));
117 /* Checks whether BB is contained in the region delimited by ENTRY and
121 bb_in_sese_p (basic_block bb
, sese region
)
123 basic_block entry
= SESE_ENTRY_BB (region
);
124 basic_block exit
= SESE_EXIT_BB (region
);
126 return bb_in_region (bb
, entry
, exit
);
129 /* Returns true when NAME is defined in REGION. */
132 defined_in_sese_p (tree name
, sese region
)
134 gimple stmt
= SSA_NAME_DEF_STMT (name
);
135 basic_block bb
= gimple_bb (stmt
);
137 return bb
&& bb_in_sese_p (bb
, region
);
140 /* Returns true when LOOP is in REGION. */
143 loop_in_sese_p (struct loop
*loop
, sese region
)
145 return (bb_in_sese_p (loop
->header
, region
)
146 && bb_in_sese_p (loop
->latch
, region
));
149 /* Returns the loop depth of LOOP in REGION. The loop depth
150 is the same as the normal loop depth, but limited by a region.
168 loop_0 does not exist in the region -> invalid
169 loop_1 exists, but is not completely contained in the region -> depth 0
170 loop_2 is completely contained -> depth 1 */
172 static inline unsigned int
173 sese_loop_depth (sese region
, loop_p loop
)
175 unsigned int depth
= 0;
177 gcc_assert ((!loop_in_sese_p (loop
, region
)
178 && (SESE_ENTRY_BB (region
)->loop_father
== loop
179 || SESE_EXIT (region
)->src
->loop_father
== loop
))
180 || loop_in_sese_p (loop
, region
));
182 while (loop_in_sese_p (loop
, region
))
185 loop
= loop_outer (loop
);
191 /* Splits BB to make a single entry single exit region. */
194 split_region_for_bb (basic_block bb
)
198 if (single_pred_p (bb
))
199 entry
= single_pred_edge (bb
);
202 entry
= split_block_after_labels (bb
);
203 bb
= single_succ (bb
);
206 if (single_succ_p (bb
))
207 exit
= single_succ_edge (bb
);
210 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
212 exit
= split_block (bb
, gsi_stmt (gsi
));
215 return new_sese (entry
, exit
);
218 /* Returns the block preceding the entry of a SESE. */
220 static inline basic_block
221 block_before_sese (sese sese
)
223 return SESE_ENTRY (sese
)->src
;
226 /* Stores the INDEX in a vector for a given clast NAME. */
228 typedef struct clast_name_index
{
231 } *clast_name_index_p
;
233 /* Returns a pointer to a new element of type clast_name_index_p built
234 from NAME and INDEX. */
236 static inline clast_name_index_p
237 new_clast_name_index (const char *name
, int index
)
239 clast_name_index_p res
= XNEW (struct clast_name_index
);
246 /* For a given clast NAME, returns -1 if it does not correspond to any
247 parameter, or otherwise, returns the index in the PARAMS or
248 SCATTERING_DIMENSIONS vector. */
251 clast_name_to_index (const char *name
, htab_t index_table
)
253 struct clast_name_index tmp
;
257 slot
= htab_find_slot (index_table
, &tmp
, NO_INSERT
);
260 return ((struct clast_name_index
*) *slot
)->index
;
265 /* Records in INDEX_TABLE the INDEX for NAME. */
268 save_clast_name_index (htab_t index_table
, const char *name
, int index
)
270 struct clast_name_index tmp
;
274 slot
= htab_find_slot (index_table
, &tmp
, INSERT
);
277 *slot
= new_clast_name_index (name
, index
);
280 /* Print to stderr the element ELT. */
283 debug_clast_name_index (clast_name_index_p elt
)
285 fprintf (stderr
, "(index = %d, name = %s)\n", elt
->index
, elt
->name
);
288 /* Helper function for debug_rename_map. */
291 debug_clast_name_indexes_1 (void **slot
, void *s ATTRIBUTE_UNUSED
)
293 struct clast_name_index
*entry
= (struct clast_name_index
*) *slot
;
294 debug_clast_name_index (entry
);
298 /* Print to stderr all the elements of MAP. */
301 debug_clast_name_indexes (htab_t map
)
303 htab_traverse (map
, debug_clast_name_indexes_1
, NULL
);
306 /* Computes a hash function for database element ELT. */
308 static inline hashval_t
309 clast_name_index_elt_info (const void *elt
)
311 return htab_hash_pointer (((const struct clast_name_index
*) elt
)->name
);
314 /* Compares database elements E1 and E2. */
317 eq_clast_name_indexes (const void *e1
, const void *e2
)
319 const struct clast_name_index
*elt1
= (const struct clast_name_index
*) e1
;
320 const struct clast_name_index
*elt2
= (const struct clast_name_index
*) e2
;
322 return (elt1
->name
== elt2
->name
);
327 /* A single entry single exit specialized for conditions. */
329 typedef struct ifsese_s
{
335 extern void if_region_set_false_region (ifsese
, sese
);
336 extern ifsese
create_if_region_on_edge (edge
, tree
);
337 extern ifsese
move_sese_in_condition (sese
);
338 extern edge
get_true_edge_from_guard_bb (basic_block
);
339 extern edge
get_false_edge_from_guard_bb (basic_block
);
342 if_region_entry (ifsese if_region
)
344 return SESE_ENTRY (if_region
->region
);
348 if_region_exit (ifsese if_region
)
350 return SESE_EXIT (if_region
->region
);
353 static inline basic_block
354 if_region_get_condition_block (ifsese if_region
)
356 return if_region_entry (if_region
)->dest
;
359 /* Structure containing the mapping between the old names and the new
360 names used after block copy in the new loop context. */
361 typedef struct rename_map_elt_s
366 DEF_VEC_P(rename_map_elt
);
367 DEF_VEC_ALLOC_P (rename_map_elt
, heap
);
369 extern void debug_rename_map (htab_t
);
370 extern hashval_t
rename_map_elt_info (const void *);
371 extern int eq_rename_map_elts (const void *, const void *);
372 extern void set_rename (htab_t
, tree
, tree
);
374 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
376 static inline rename_map_elt
377 new_rename_map_elt (tree old_name
, tree expr
)
381 res
= XNEW (struct rename_map_elt_s
);
382 res
->old_name
= old_name
;
388 /* Structure containing the mapping between the CLooG's induction
389 variable and the type of the old induction variable. */
390 typedef struct ivtype_map_elt_s
393 const char *cloog_iv
;
396 extern void debug_ivtype_map (htab_t
);
397 extern hashval_t
ivtype_map_elt_info (const void *);
398 extern int eq_ivtype_map_elts (const void *, const void *);
400 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
402 static inline ivtype_map_elt
403 new_ivtype_map_elt (const char *cloog_iv
, tree type
)
407 res
= XNEW (struct ivtype_map_elt_s
);
408 res
->cloog_iv
= cloog_iv
;
414 /* Free and compute again all the dominators information. */
417 recompute_all_dominators (void)
419 mark_irreducible_loops ();
420 free_dominance_info (CDI_DOMINATORS
);
421 free_dominance_info (CDI_POST_DOMINATORS
);
422 calculate_dominance_info (CDI_DOMINATORS
);
423 calculate_dominance_info (CDI_POST_DOMINATORS
);
426 typedef struct gimple_bb
430 /* Lists containing the restrictions of the conditional statements
431 dominating this bb. This bb can only be executed, if all conditions
436 for (i = 0; i <= 20; i++)
444 So for B there is an additional condition (2i <= 8).
446 List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the
447 corresponding element in CONDITION_CASES is not NULL_TREE. For a
448 SWITCH_EXPR the corresponding element in CONDITION_CASES is a
450 VEC (gimple
, heap
) *conditions
;
451 VEC (gimple
, heap
) *condition_cases
;
452 VEC (data_reference_p
, heap
) *data_refs
;
453 htab_t cloog_iv_types
;
456 #define GBB_BB(GBB) GBB->bb
457 #define GBB_DATA_REFS(GBB) GBB->data_refs
458 #define GBB_CONDITIONS(GBB) GBB->conditions
459 #define GBB_CONDITION_CASES(GBB) GBB->condition_cases
460 #define GBB_CLOOG_IV_TYPES(GBB) GBB->cloog_iv_types
462 /* Return the innermost loop that contains the basic block GBB. */
464 static inline struct loop
*
465 gbb_loop (struct gimple_bb
*gbb
)
467 return GBB_BB (gbb
)->loop_father
;
470 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
471 If there is no corresponding gimple loop, we return NULL. */
474 gbb_loop_at_index (gimple_bb_p gbb
, sese region
, int index
)
476 loop_p loop
= gbb_loop (gbb
);
477 int depth
= sese_loop_depth (region
, loop
);
479 while (--depth
> index
)
480 loop
= loop_outer (loop
);
482 gcc_assert (sese_contains_loop (region
, loop
));
487 /* The number of common loops in REGION for GBB1 and GBB2. */
490 nb_common_loops (sese region
, gimple_bb_p gbb1
, gimple_bb_p gbb2
)
492 loop_p l1
= gbb_loop (gbb1
);
493 loop_p l2
= gbb_loop (gbb2
);
494 loop_p common
= find_common_loop (l1
, l2
);
496 return sese_loop_depth (region
, common
);
499 extern void print_gimple_bb (FILE *, gimple_bb_p
, int, int);
500 extern void debug_gbb (gimple_bb_p
, int);