GCC Middle and Back End API Reference
sese.h
Go to the documentation of this file.
1/* Single entry single exit control flow regions.
2 Copyright (C) 2008-2024 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. */
29class sese_l
30{
31public:
32 sese_l (edge e, edge x) : entry (e), exit (x) {}
33
34 operator bool () const { return entry && exit; }
35
38};
39
40void print_edge (FILE *file, const_edge e);
41void print_sese (FILE *file, const sese_l &s);
43void dump_sese (const sese_l &);
44
45/* Get the entry of an sese S. */
46
47inline basic_block
49{
50 return s.entry->dest;
51}
52
53/* Get the exit of an sese S. */
54
55inline basic_block
57{
58 return s.exit->src;
59}
60
61/* Returns the index of V where ELEM can be found. -1 Otherwise. */
62template<typename T>
63int
64vec_find (const vec<T> &v, const T &elem)
65{
66 int i;
67 T t;
68 FOR_EACH_VEC_ELT (v, i, t)
69 if (elem == t)
70 return i;
71 return -1;
72}
73
74/* A helper structure for bookkeeping information about a scop in graphite. */
75typedef class sese_info_t
76{
77public:
78 /* The SESE region. */
80
81 /* Liveout vars. */
83
84 /* Liveout in debug stmts. */
86
87 /* Parameters used within the SCOP. */
89
90 /* Maps an old name to a new decl. */
92
93 /* Basic blocks contained in this SESE. */
95
96 /* The condition region generated for this sese. */
98
100
102extern void free_sese_info (sese_info_p);
106extern bool scev_analyzable_p (tree, sese_l &);
107extern bool invariant_in_sese_p_rec (tree, const sese_l &, bool *);
108extern void sese_build_liveouts (sese_info_p);
110
111/* The number of parameters in REGION. */
112
113inline unsigned
115{
116 return region->params.length ();
117}
118
119/* Checks whether BB is contained in the region delimited by ENTRY and
120 EXIT blocks. */
121
122inline bool
124{
125 return dominated_by_p (CDI_DOMINATORS, bb, entry)
126 && !(dominated_by_p (CDI_DOMINATORS, bb, exit)
127 && !dominated_by_p (CDI_DOMINATORS, entry, exit));
128}
129
130/* Checks whether BB is contained in the region delimited by ENTRY and
131 EXIT blocks. */
132
133inline bool
135{
136 return bb_in_region (bb, r.entry->dest, r.exit->dest);
137}
138
139/* Returns true when STMT is defined in REGION. */
140
141inline bool
143{
144 basic_block bb = gimple_bb (stmt);
145 return bb && bb_in_sese_p (bb, r);
146}
147
148/* Returns true when NAME is defined in REGION. */
149
150inline bool
152{
153 return stmt_in_sese_p (SSA_NAME_DEF_STMT (name), r);
154}
155
156/* Returns true when LOOP is in REGION. */
157
158inline bool
159loop_in_sese_p (class loop *loop, const sese_l &region)
160{
161 return (bb_in_sese_p (loop->header, region)
162 && bb_in_sese_p (loop->latch, region));
163}
164
165/* Returns the loop depth of LOOP in REGION. The loop depth
166 is the same as the normal loop depth, but limited by a region.
167
168 Example:
169
170 loop_0
171 loop_1
172 {
173 S0
174 <- region start
175 S1
176
177 loop_2
178 S2
179
180 S3
181 <- region end
182 }
183
184 loop_0 does not exist in the region -> invalid
185 loop_1 exists, but is not completely contained in the region -> depth 0
186 loop_2 is completely contained -> depth 1 */
187
188inline unsigned int
190{
191 unsigned int depth = 0;
192
193 while (loop_in_sese_p (loop, region))
194 {
195 depth++;
196 loop = loop_outer (loop);
197 }
198
199 return depth;
200}
201
202/* A single entry single exit specialized for conditions. */
203
209
211extern void set_ifsese_condition (ifsese, tree);
214
215inline edge
217{
218 return if_region->region->region.entry;
219}
220
221inline edge
223{
224 return if_region->region->region.exit;
225}
226
227inline basic_block
229{
230 return if_region_entry (if_region)->dest;
231}
232
233typedef std::pair <gimple *, tree> scalar_use;
234
235typedef struct gimple_poly_bb
236{
238 struct poly_bb *pbb;
239
240 /* Lists containing the restrictions of the conditional statements
241 dominating this bb. This bb can only be executed, if all conditions
242 are true.
243
244 Example:
245
246 for (i = 0; i <= 20; i++)
247 {
248 A
249
250 if (2i <= 8)
251 B
252 }
253
254 So for B there is an additional condition (2i <= 8).
255
256 List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the
257 corresponding element in CONDITION_CASES is not NULL_TREE. For a
258 SWITCH_EXPR the corresponding element in CONDITION_CASES is a
259 CASE_LABEL_EXPR. */
266
267#define GBB_BB(GBB) (GBB)->bb
268#define GBB_PBB(GBB) (GBB)->pbb
269#define GBB_DATA_REFS(GBB) (GBB)->data_refs
270#define GBB_CONDITIONS(GBB) (GBB)->conditions
271#define GBB_CONDITION_CASES(GBB) (GBB)->condition_cases
272
273/* Return the innermost loop that contains the basic block GBB. */
274
275inline class loop *
277{
278 return GBB_BB (gbb)->loop_father;
279}
280
281/* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
282 If there is no corresponding gimple loop, we return NULL. */
283
284inline loop_p
286{
287 loop_p loop = gbb_loop (gbb);
288 int depth = sese_loop_depth (region, loop);
289
290 while (--depth > index)
291 loop = loop_outer (loop);
292
293 gcc_assert (loop_in_sese_p (loop, region));
294
295 return loop;
296}
297
298/* The number of common loops in REGION for GBB1 and GBB2. */
299
300inline int
302{
303 loop_p l1 = gbb_loop (gbb1);
304 loop_p l2 = gbb_loop (gbb2);
305 loop_p common = find_common_loop (l1, l2);
306
307 return sese_loop_depth (region, common);
308}
309
310#endif
class loop * find_common_loop(class loop *loop_s, class loop *loop_d)
Definition cfgloop.cc:1307
class loop * loop_outer(const class loop *loop)
Definition cfgloop.h:547
class loop * loop_p
Definition cfgloop.h:98
Definition hash-map.h:40
Definition cfgloop.h:120
basic_block latch
Definition cfgloop.h:133
basic_block header
Definition cfgloop.h:130
Definition sese.h:76
bitmap debug_liveout
Definition sese.h:85
ifsese if_region
Definition sese.h:97
hash_map< tree, tree > * rename_map
Definition sese.h:91
sese_l region
Definition sese.h:79
vec< tree > params
Definition sese.h:88
bitmap liveout
Definition sese.h:82
vec< basic_block > bbs
Definition sese.h:94
Definition sese.h:30
edge entry
Definition sese.h:36
edge exit
Definition sese.h:37
sese_l(edge e, edge x)
Definition sese.h:32
class edge_def * edge
Definition coretypes.h:343
const class edge_def * const_edge
Definition coretypes.h:344
class bitmap_head * bitmap
Definition coretypes.h:51
union tree_node * tree
Definition coretypes.h:97
bool dominated_by_p(enum cdi_direction dir, const_basic_block bb1, const_basic_block bb2)
Definition dominance.cc:1125
@ CDI_DOMINATORS
Definition dominance.h:25
basic_block gimple_bb(const gimple *g)
Definition gimple.h:1860
poly_int< N, C > r
Definition poly-int.h:770
i
Definition poly-int.h:772
std::pair< gimple *, tree > scalar_use
Definition sese.h:233
int nb_common_loops(sese_l &region, gimple_poly_bb_p gbb1, gimple_poly_bb_p gbb2)
Definition sese.h:301
edge get_false_edge_from_guard_bb(basic_block)
Definition sese.cc:278
class sese_info_t * sese_info_p
bool sese_trivially_empty_bb_p(basic_block)
Definition sese.cc:456
sese_info_p new_sese_info(edge, edge)
Definition sese.cc:150
void set_ifsese_condition(ifsese, tree)
Definition sese.cc:341
void dump_edge(const_edge e)
basic_block if_region_get_condition_block(ifsese if_region)
Definition sese.h:228
bool invariant_in_sese_p_rec(tree, const sese_l &, bool *)
Definition sese.cc:364
basic_block get_exit_bb(const sese_l &s)
Definition sese.h:56
basic_block get_entry_bb(const sese_l &s)
Definition sese.h:48
void dump_sese(const sese_l &)
int vec_find(const vec< T > &v, const T &elem)
Definition sese.h:64
class loop * outermost_loop_in_sese(sese_l &, basic_block)
Definition sese.cc:239
struct ifsese_s * ifsese
Definition sese.h:25
loop_p gbb_loop_at_index(gimple_poly_bb_p gbb, sese_l &region, int index)
Definition sese.h:285
void print_sese(FILE *file, const sese_l &s)
Definition sese.cc:479
void sese_build_liveouts(sese_info_p)
Definition sese.cc:131
bool stmt_in_sese_p(gimple *stmt, const sese_l &r)
Definition sese.h:142
void free_sese_info(sese_info_p)
Definition sese.cc:168
unsigned sese_nb_params(sese_info_p region)
Definition sese.h:114
edge get_true_edge_from_guard_bb(basic_block)
Definition sese.cc:262
edge if_region_exit(ifsese if_region)
Definition sese.h:222
tree scalar_evolution_in_region(const sese_l &, loop_p, tree)
Definition sese.cc:439
ifsese move_sese_in_condition(sese_info_p)
Definition sese.cc:299
void sese_insert_phis_for_liveouts(sese_info_p, basic_block, edge, edge)
Definition sese.cc:205
edge if_region_entry(ifsese if_region)
Definition sese.h:216
unsigned int sese_loop_depth(const sese_l &region, loop_p loop)
Definition sese.h:189
#define GBB_BB(GBB)
Definition sese.h:267
void print_edge(FILE *file, const_edge e)
Definition sese.cc:471
class loop * gbb_loop(gimple_poly_bb_p gbb)
Definition sese.h:276
bool scev_analyzable_p(tree, sese_l &)
Definition sese.cc:407
bool loop_in_sese_p(class loop *loop, const sese_l &region)
Definition sese.h:159
struct gimple_poly_bb * gimple_poly_bb_p
bool defined_in_sese_p(tree name, const sese_l &r)
Definition sese.h:151
bool bb_in_region(const_basic_block bb, const_basic_block entry, const_basic_block exit)
Definition sese.h:123
bool bb_in_sese_p(basic_block bb, const sese_l &r)
Definition sese.h:134
Definition basic-block.h:117
Definition sese.h:236
vec< data_reference_p > data_refs
Definition sese.h:262
vec< gimple * > conditions
Definition sese.h:260
vec< gimple * > condition_cases
Definition sese.h:261
struct poly_bb * pbb
Definition sese.h:238
vec< tree > write_scalar_refs
Definition sese.h:264
basic_block bb
Definition sese.h:237
vec< scalar_use > read_scalar_refs
Definition sese.h:263
Definition gimple.h:225
Definition sese.h:204
sese_info_p true_region
Definition sese.h:206
sese_info_p region
Definition sese.h:205
sese_info_p false_region
Definition sese.h:207
Definition graphite.h:217
Definition vec.h:450
#define gcc_assert(EXPR)
Definition system.h:821
#define bool
Definition system.h:893
#define SSA_NAME_DEF_STMT(NODE)
Definition tree.h:2105
#define FOR_EACH_VEC_ELT(V, I, P)
Definition vec.h:1884