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>.
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify
9it under the terms of the GNU General Public License as published by
10the Free Software Foundation; either version 3, or (at your option)
11any later version.
12
13GCC is distributed in the hope that it will be useful,
14but WITHOUT ANY WARRANTY; without even the implied warranty of
15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16GNU General Public License for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING3. If not see
20<http://www.gnu.org/licenses/>. */
21
22#ifndef GCC_SESE_H
23#define GCC_SESE_H
24
25typedef struct ifsese_s *ifsese;
26
27/* A Single Entry, Single Exit region is a part of the CFG delimited
28 by two edges. */
29struct sese_l
30{
31 sese_l (edge e, edge x) : entry (e), exit (x) {}
32
33 operator bool () const { return entry && exit; }
34
35 edge entry;
36 edge exit;
37};
38
39void print_edge (FILE *file, const_edge e);
40void print_sese (FILE *file, const sese_l &s);
41void dump_edge (const_edge e);
42void dump_sese (const sese_l &);
43
44/* Get the entry of an sese S. */
45
46static inline basic_block
47get_entry_bb (sese_l &s)
48{
49 return s.entry->dest;
50}
51
52/* Get the exit of an sese S. */
53
54static inline basic_block
55get_exit_bb (sese_l &s)
56{
57 return s.exit->src;
58}
59
60/* Returns the index of V where ELEM can be found. -1 Otherwise. */
61template<typename T>
62int
63vec_find (const vec<T> &v, const T &elem)
64{
65 int i;
66 T t;
67 FOR_EACH_VEC_ELT (v, i, t)
68 if (elem == t)
69 return i;
70 return -1;
71}
72
73/* A helper structure for bookkeeping information about a scop in graphite. */
74typedef struct sese_info_t
75{
76 /* The SESE region. */
77 sese_l region;
78
79 /* Liveout vars. */
80 bitmap liveout;
81
82 /* Liveout in debug stmts. */
83 bitmap debug_liveout;
84
85 /* Parameters used within the SCOP. */
86 vec<tree> params;
87
88 /* Maps an old name to a new decl. */
89 hash_map<tree, tree> *rename_map;
90
91 /* Basic blocks contained in this SESE. */
92 vec<basic_block> bbs;
93
94 /* The condition region generated for this sese. */
95 ifsese if_region;
96
97} *sese_info_p;
98
99extern sese_info_p new_sese_info (edge, edge);
100extern void free_sese_info (sese_info_p);
101extern void sese_insert_phis_for_liveouts (sese_info_p, basic_block, edge, edge);
102extern struct loop *outermost_loop_in_sese (sese_l &, basic_block);
103extern tree scalar_evolution_in_region (const sese_l &, loop_p, tree);
104extern bool scev_analyzable_p (tree, sese_l &);
105extern bool invariant_in_sese_p_rec (tree, const sese_l &, bool *);
106extern void sese_build_liveouts (sese_info_p);
107extern bool sese_trivially_empty_bb_p (basic_block);
108
109/* The number of parameters in REGION. */
110
111static inline unsigned
112sese_nb_params (sese_info_p region)
113{
114 return region->params.length ();
115}
116
117/* Checks whether BB is contained in the region delimited by ENTRY and
118 EXIT blocks. */
119
120static inline bool
121bb_in_region (const_basic_block bb, const_basic_block entry, const_basic_block exit)
122{
123 /* FIXME: PR67842. */
124#if 0
125 if (flag_checking)
126 {
127 edge e;
128 edge_iterator ei;
129
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));
134 }
135#endif
136
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));
140}
141
142/* Checks whether BB is contained in the region delimited by ENTRY and
143 EXIT blocks. */
144
145static inline bool
146bb_in_sese_p (basic_block bb, const sese_l &r)
147{
148 return bb_in_region (bb, r.entry->dest, r.exit->dest);
149}
150
151/* Returns true when STMT is defined in REGION. */
152
153static inline bool
154stmt_in_sese_p (gimple *stmt, const sese_l &r)
155{
156 basic_block bb = gimple_bb (stmt);
157 return bb && bb_in_sese_p (bb, r);
158}
159
160/* Returns true when NAME is defined in REGION. */
161
162static inline bool
163defined_in_sese_p (tree name, const sese_l &r)
164{
165 return stmt_in_sese_p (SSA_NAME_DEF_STMT (name), r);
166}
167
168/* Returns true when LOOP is in REGION. */
169
170static inline bool
171loop_in_sese_p (struct loop *loop, const sese_l &region)
172{
173 return (bb_in_sese_p (loop->header, region)
174 && bb_in_sese_p (loop->latch, region));
175}
176
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.
179
180 Example:
181
182 loop_0
183 loop_1
184 {
185 S0
186 <- region start
187 S1
188
189 loop_2
190 S2
191
192 S3
193 <- region end
194 }
195
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 */
199
200static inline unsigned int
201sese_loop_depth (const sese_l &region, loop_p loop)
202{
203 unsigned int depth = 0;
204
205 while (loop_in_sese_p (loop, region))
206 {
207 depth++;
208 loop = loop_outer (loop);
209 }
210
211 return depth;
212}
213
214/* A single entry single exit specialized for conditions. */
215
216typedef struct ifsese_s {
217 sese_info_p region;
218 sese_info_p true_region;
219 sese_info_p false_region;
220} *ifsese;
221
222extern ifsese move_sese_in_condition (sese_info_p);
223extern void set_ifsese_condition (ifsese, tree);
224extern edge get_true_edge_from_guard_bb (basic_block);
225extern edge get_false_edge_from_guard_bb (basic_block);
226
227static inline edge
228if_region_entry (ifsese if_region)
229{
230 return if_region->region->region.entry;
231}
232
233static inline edge
234if_region_exit (ifsese if_region)
235{
236 return if_region->region->region.exit;
237}
238
239static inline basic_block
240if_region_get_condition_block (ifsese if_region)
241{
242 return if_region_entry (if_region)->dest;
243}
244
245/* Free and compute again all the dominators information. */
246
247static inline void
248recompute_all_dominators (void)
249{
250 mark_irreducible_loops ();
251 free_dominance_info (CDI_DOMINATORS);
252 calculate_dominance_info (CDI_DOMINATORS);
253
254 free_dominance_info (CDI_POST_DOMINATORS);
255 calculate_dominance_info (CDI_POST_DOMINATORS);
256}
257
258typedef std::pair <gimple *, tree> scalar_use;
259
260typedef struct gimple_poly_bb
261{
262 basic_block bb;
263 struct poly_bb *pbb;
264
265 /* Lists containing the restrictions of the conditional statements
266 dominating this bb. This bb can only be executed, if all conditions
267 are true.
268
269 Example:
270
271 for (i = 0; i <= 20; i++)
272 {
273 A
274
275 if (2i <= 8)
276 B
277 }
278
279 So for B there is an additional condition (2i <= 8).
280
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
284 CASE_LABEL_EXPR. */
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;
290} *gimple_poly_bb_p;
291
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
297
298/* Return the innermost loop that contains the basic block GBB. */
299
300static inline struct loop *
301gbb_loop (gimple_poly_bb_p gbb)
302{
303 return GBB_BB (gbb)->loop_father;
304}
305
306/* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
307 If there is no corresponding gimple loop, we return NULL. */
308
309static inline loop_p
310gbb_loop_at_index (gimple_poly_bb_p gbb, sese_l &region, int index)
311{
312 loop_p loop = gbb_loop (gbb);
313 int depth = sese_loop_depth (region, loop);
314
315 while (--depth > index)
316 loop = loop_outer (loop);
317
318 gcc_assert (loop_in_sese_p (loop, region));
319
320 return loop;
321}
322
323/* The number of common loops in REGION for GBB1 and GBB2. */
324
325static inline int
326nb_common_loops (sese_l &region, gimple_poly_bb_p gbb1, gimple_poly_bb_p gbb2)
327{
328 loop_p l1 = gbb_loop (gbb1);
329 loop_p l2 = gbb_loop (gbb2);
330 loop_p common = find_common_loop (l1, l2);
331
332 return sese_loop_depth (region, common);
333}
334
335#endif
336