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 struct ifsese_s
*ifsese
;
27 /* A Single Entry, Single Exit region is a part of the CFG delimited
31 sese_l (edge e
, edge x
) : entry (e
), exit (x
) {}
33 operator bool () const { return entry
&& exit
; }
39 void print_edge (FILE *file
, const_edge e
);
40 void print_sese (FILE *file
, const sese_l
&s
);
41 void dump_edge (const_edge e
);
42 void dump_sese (const sese_l
&);
44 /* Get the entry of an sese S. */
46 static inline basic_block
47 get_entry_bb (sese_l
&s
)
52 /* Get the exit of an sese S. */
54 static inline basic_block
55 get_exit_bb (sese_l
&s
)
60 /* Returns the index of V where ELEM can be found. -1 Otherwise. */
63 vec_find (const vec
<T
> &v
, const T
&elem
)
67 FOR_EACH_VEC_ELT (v
, i
, t
)
73 /* A helper structure for bookkeeping information about a scop in graphite. */
74 typedef struct sese_info_t
76 /* The SESE region. */
82 /* Liveout in debug stmts. */
85 /* Parameters used within the SCOP. */
88 /* Maps an old name to a new decl. */
89 hash_map
<tree
, tree
> *rename_map
;
91 /* Basic blocks contained in this SESE. */
94 /* The condition region generated for this sese. */
99 extern sese_info_p
new_sese_info (edge
, edge
);
100 extern void free_sese_info (sese_info_p
);
101 extern void sese_insert_phis_for_liveouts (sese_info_p
, basic_block
, edge
, edge
);
102 extern struct loop
*outermost_loop_in_sese (sese_l
&, basic_block
);
103 extern tree
scalar_evolution_in_region (const sese_l
&, loop_p
, tree
);
104 extern bool scev_analyzable_p (tree
, sese_l
&);
105 extern bool invariant_in_sese_p_rec (tree
, const sese_l
&, bool *);
106 extern void sese_build_liveouts (sese_info_p
);
107 extern bool sese_trivially_empty_bb_p (basic_block
);
109 /* The number of parameters in REGION. */
111 static inline unsigned
112 sese_nb_params (sese_info_p region
)
114 return region
->params
.length ();
117 /* Checks whether BB is contained in the region delimited by ENTRY and
121 bb_in_region (const_basic_block bb
, const_basic_block entry
, const_basic_block exit
)
123 /* FIXME: PR67842. */
130 /* Check that there are no edges coming in the region: all the
131 predecessors of EXIT are dominated by ENTRY. */
132 FOR_EACH_EDGE (e
, ei
, exit
->preds
)
133 gcc_assert (dominated_by_p (CDI_DOMINATORS
, e
->src
, entry
));
137 return dominated_by_p (CDI_DOMINATORS
, bb
, entry
)
138 && !(dominated_by_p (CDI_DOMINATORS
, bb
, exit
)
139 && !dominated_by_p (CDI_DOMINATORS
, entry
, exit
));
142 /* Checks whether BB is contained in the region delimited by ENTRY and
146 bb_in_sese_p (basic_block bb
, const sese_l
&r
)
148 return bb_in_region (bb
, r
.entry
->dest
, r
.exit
->dest
);
151 /* Returns true when STMT is defined in REGION. */
154 stmt_in_sese_p (gimple
*stmt
, const sese_l
&r
)
156 basic_block bb
= gimple_bb (stmt
);
157 return bb
&& bb_in_sese_p (bb
, r
);
160 /* Returns true when NAME is defined in REGION. */
163 defined_in_sese_p (tree name
, const sese_l
&r
)
165 return stmt_in_sese_p (SSA_NAME_DEF_STMT (name
), r
);
168 /* Returns true when LOOP is in REGION. */
171 loop_in_sese_p (struct loop
*loop
, const sese_l
®ion
)
173 return (bb_in_sese_p (loop
->header
, region
)
174 && bb_in_sese_p (loop
->latch
, region
));
177 /* Returns the loop depth of LOOP in REGION. The loop depth
178 is the same as the normal loop depth, but limited by a region.
196 loop_0 does not exist in the region -> invalid
197 loop_1 exists, but is not completely contained in the region -> depth 0
198 loop_2 is completely contained -> depth 1 */
200 static inline unsigned int
201 sese_loop_depth (const sese_l
®ion
, loop_p loop
)
203 unsigned int depth
= 0;
205 while (loop_in_sese_p (loop
, region
))
208 loop
= loop_outer (loop
);
214 /* A single entry single exit specialized for conditions. */
216 typedef struct ifsese_s
{
218 sese_info_p true_region
;
219 sese_info_p false_region
;
222 extern ifsese
move_sese_in_condition (sese_info_p
);
223 extern void set_ifsese_condition (ifsese
, tree
);
224 extern edge
get_true_edge_from_guard_bb (basic_block
);
225 extern edge
get_false_edge_from_guard_bb (basic_block
);
228 if_region_entry (ifsese if_region
)
230 return if_region
->region
->region
.entry
;
234 if_region_exit (ifsese if_region
)
236 return if_region
->region
->region
.exit
;
239 static inline basic_block
240 if_region_get_condition_block (ifsese if_region
)
242 return if_region_entry (if_region
)->dest
;
245 /* Free and compute again all the dominators information. */
248 recompute_all_dominators (void)
250 mark_irreducible_loops ();
251 free_dominance_info (CDI_DOMINATORS
);
252 calculate_dominance_info (CDI_DOMINATORS
);
254 free_dominance_info (CDI_POST_DOMINATORS
);
255 calculate_dominance_info (CDI_POST_DOMINATORS
);
258 typedef std::pair
<gimple
*, tree
> scalar_use
;
260 typedef struct gimple_poly_bb
265 /* Lists containing the restrictions of the conditional statements
266 dominating this bb. This bb can only be executed, if all conditions
271 for (i = 0; i <= 20; i++)
279 So for B there is an additional condition (2i <= 8).
281 List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the
282 corresponding element in CONDITION_CASES is not NULL_TREE. For a
283 SWITCH_EXPR the corresponding element in CONDITION_CASES is a
285 vec
<gimple
*> conditions
;
286 vec
<gimple
*> condition_cases
;
287 vec
<data_reference_p
> data_refs
;
288 vec
<scalar_use
> read_scalar_refs
;
289 vec
<tree
> write_scalar_refs
;
292 #define GBB_BB(GBB) (GBB)->bb
293 #define GBB_PBB(GBB) (GBB)->pbb
294 #define GBB_DATA_REFS(GBB) (GBB)->data_refs
295 #define GBB_CONDITIONS(GBB) (GBB)->conditions
296 #define GBB_CONDITION_CASES(GBB) (GBB)->condition_cases
298 /* Return the innermost loop that contains the basic block GBB. */
300 static inline struct loop
*
301 gbb_loop (gimple_poly_bb_p gbb
)
303 return GBB_BB (gbb
)->loop_father
;
306 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
307 If there is no corresponding gimple loop, we return NULL. */
310 gbb_loop_at_index (gimple_poly_bb_p gbb
, sese_l
®ion
, int index
)
312 loop_p loop
= gbb_loop (gbb
);
313 int depth
= sese_loop_depth (region
, loop
);
315 while (--depth
> index
)
316 loop
= loop_outer (loop
);
318 gcc_assert (loop_in_sese_p (loop
, region
));
323 /* The number of common loops in REGION for GBB1 and GBB2. */
326 nb_common_loops (sese_l
®ion
, gimple_poly_bb_p gbb1
, gimple_poly_bb_p gbb2
)
328 loop_p l1
= gbb_loop (gbb1
);
329 loop_p l2
= gbb_loop (gbb2
);
330 loop_p common
= find_common_loop (l1
, l2
);
332 return sese_loop_depth (region
, common
);