1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008-2017 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
;
26 typedef hash_map
<basic_block
, vec
<basic_block
> > bb_map_t
;
27 typedef hash_map
<tree
, vec
<tree
> > rename_map_t
;
28 typedef struct ifsese_s
*ifsese
;
29 /* First phi is the new codegenerated phi second one is original phi. */
30 typedef std::pair
<gphi
*, gphi
*> phi_rename
;
31 /* First edge is the init edge and second is the back edge w.r.t. a loop. */
32 typedef std::pair
<edge
, edge
> init_back_edge_pair_t
;
34 /* A Single Entry, Single Exit region is a part of the CFG delimited
38 sese_l (edge e
, edge x
) : entry (e
), exit (x
) {}
40 operator bool () const { return entry
&& exit
; }
46 void print_edge (FILE *file
, const_edge e
);
47 void print_sese (FILE *file
, const sese_l
&s
);
48 void dump_edge (const_edge e
);
49 void dump_sese (const sese_l
&);
51 /* Get the entry of an sese S. */
53 static inline basic_block
54 get_entry_bb (sese_l
&s
)
59 /* Get the exit of an sese S. */
61 static inline basic_block
62 get_exit_bb (sese_l
&s
)
67 /* Returns the index of V where ELEM can be found. -1 Otherwise. */
70 vec_find (const vec
<T
> &v
, const T
&elem
)
74 FOR_EACH_VEC_ELT (v
, i
, t
)
80 /* A helper structure for bookkeeping information about a scop in graphite. */
81 typedef struct sese_info_t
83 /* The SESE region. */
89 /* Liveout in debug stmts. */
92 /* Parameters used within the SCOP. */
95 /* Maps an old name to one or more new names. When there are several new
96 names, one has to select the definition corresponding to the immediate
98 rename_map_t
*rename_map
;
100 /* Parameters to be renamed. */
101 parameter_rename_map_t
*parameter_rename_map
;
103 /* Basic blocks contained in this SESE. */
104 vec
<basic_block
> bbs
;
106 /* Copied basic blocks indexed by the original bb. */
107 bb_map_t
*copied_bb_map
;
109 /* A vector of phi nodes to be updated when all arguments are available. The
110 pair contains first the old_phi and second the new_phi. */
111 vec
<phi_rename
> incomplete_phis
;
113 /* The condition region generated for this sese. */
118 extern sese_info_p
new_sese_info (edge
, edge
);
119 extern void free_sese_info (sese_info_p
);
120 extern void sese_insert_phis_for_liveouts (sese_info_p
, basic_block
, edge
, edge
);
121 extern struct loop
*outermost_loop_in_sese (sese_l
&, basic_block
);
122 extern tree
scalar_evolution_in_region (const sese_l
&, loop_p
, tree
);
123 extern bool scev_analyzable_p (tree
, sese_l
&);
124 extern bool invariant_in_sese_p_rec (tree
, const sese_l
&, bool *);
125 extern void sese_build_liveouts (sese_info_p
);
126 extern bool sese_trivially_empty_bb_p (basic_block
);
128 /* The number of parameters in REGION. */
130 static inline unsigned
131 sese_nb_params (sese_info_p region
)
133 return region
->params
.length ();
136 /* Checks whether BB is contained in the region delimited by ENTRY and
140 bb_in_region (const_basic_block bb
, const_basic_block entry
, const_basic_block exit
)
142 /* FIXME: PR67842. */
149 /* Check that there are no edges coming in the region: all the
150 predecessors of EXIT are dominated by ENTRY. */
151 FOR_EACH_EDGE (e
, ei
, exit
->preds
)
152 gcc_assert (dominated_by_p (CDI_DOMINATORS
, e
->src
, entry
));
156 return dominated_by_p (CDI_DOMINATORS
, bb
, entry
)
157 && !(dominated_by_p (CDI_DOMINATORS
, bb
, exit
)
158 && !dominated_by_p (CDI_DOMINATORS
, entry
, exit
));
161 /* Checks whether BB is contained in the region delimited by ENTRY and
165 bb_in_sese_p (basic_block bb
, const sese_l
&r
)
167 return bb_in_region (bb
, r
.entry
->dest
, r
.exit
->dest
);
170 /* Returns true when STMT is defined in REGION. */
173 stmt_in_sese_p (gimple
*stmt
, const sese_l
&r
)
175 basic_block bb
= gimple_bb (stmt
);
176 return bb
&& bb_in_sese_p (bb
, r
);
179 /* Returns true when NAME is defined in REGION. */
182 defined_in_sese_p (tree name
, const sese_l
&r
)
184 return stmt_in_sese_p (SSA_NAME_DEF_STMT (name
), r
);
187 /* Returns true when LOOP is in REGION. */
190 loop_in_sese_p (struct loop
*loop
, const sese_l
®ion
)
192 return (bb_in_sese_p (loop
->header
, region
)
193 && bb_in_sese_p (loop
->latch
, region
));
196 /* Returns the loop depth of LOOP in REGION. The loop depth
197 is the same as the normal loop depth, but limited by a region.
215 loop_0 does not exist in the region -> invalid
216 loop_1 exists, but is not completely contained in the region -> depth 0
217 loop_2 is completely contained -> depth 1 */
219 static inline unsigned int
220 sese_loop_depth (const sese_l
®ion
, loop_p loop
)
222 unsigned int depth
= 0;
224 while (loop_in_sese_p (loop
, region
))
227 loop
= loop_outer (loop
);
233 /* A single entry single exit specialized for conditions. */
235 typedef struct ifsese_s
{
237 sese_info_p true_region
;
238 sese_info_p false_region
;
241 extern ifsese
move_sese_in_condition (sese_info_p
);
242 extern void set_ifsese_condition (ifsese
, tree
);
243 extern edge
get_true_edge_from_guard_bb (basic_block
);
244 extern edge
get_false_edge_from_guard_bb (basic_block
);
247 if_region_entry (ifsese if_region
)
249 return if_region
->region
->region
.entry
;
253 if_region_exit (ifsese if_region
)
255 return if_region
->region
->region
.exit
;
258 static inline basic_block
259 if_region_get_condition_block (ifsese if_region
)
261 return if_region_entry (if_region
)->dest
;
264 /* Free and compute again all the dominators information. */
267 recompute_all_dominators (void)
269 mark_irreducible_loops ();
270 free_dominance_info (CDI_DOMINATORS
);
271 calculate_dominance_info (CDI_DOMINATORS
);
273 free_dominance_info (CDI_POST_DOMINATORS
);
274 calculate_dominance_info (CDI_POST_DOMINATORS
);
277 typedef std::pair
<gimple
*, tree
> scalar_use
;
279 typedef struct gimple_poly_bb
284 /* Lists containing the restrictions of the conditional statements
285 dominating this bb. This bb can only be executed, if all conditions
290 for (i = 0; i <= 20; i++)
298 So for B there is an additional condition (2i <= 8).
300 List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the
301 corresponding element in CONDITION_CASES is not NULL_TREE. For a
302 SWITCH_EXPR the corresponding element in CONDITION_CASES is a
304 vec
<gimple
*> conditions
;
305 vec
<gimple
*> condition_cases
;
306 vec
<data_reference_p
> data_refs
;
307 vec
<scalar_use
> read_scalar_refs
;
308 vec
<tree
> write_scalar_refs
;
311 #define GBB_BB(GBB) (GBB)->bb
312 #define GBB_PBB(GBB) (GBB)->pbb
313 #define GBB_DATA_REFS(GBB) (GBB)->data_refs
314 #define GBB_CONDITIONS(GBB) (GBB)->conditions
315 #define GBB_CONDITION_CASES(GBB) (GBB)->condition_cases
317 /* Return the innermost loop that contains the basic block GBB. */
319 static inline struct loop
*
320 gbb_loop (gimple_poly_bb_p gbb
)
322 return GBB_BB (gbb
)->loop_father
;
325 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
326 If there is no corresponding gimple loop, we return NULL. */
329 gbb_loop_at_index (gimple_poly_bb_p gbb
, sese_l
®ion
, int index
)
331 loop_p loop
= gbb_loop (gbb
);
332 int depth
= sese_loop_depth (region
, loop
);
334 while (--depth
> index
)
335 loop
= loop_outer (loop
);
340 /* The number of common loops in REGION for GBB1 and GBB2. */
343 nb_common_loops (sese_l
®ion
, gimple_poly_bb_p gbb1
, gimple_poly_bb_p gbb2
)
345 loop_p l1
= gbb_loop (gbb1
);
346 loop_p l2
= gbb_loop (gbb2
);
347 loop_p common
= find_common_loop (l1
, l2
);
349 return sese_loop_depth (region
, common
);