]> git.ipfire.org Git - thirdparty/gcc.git/blame - gcc/sese.h
* doc/install.texi (Specific, alpha): Remove note to use
[thirdparty/gcc.git] / gcc / sese.h
CommitLineData
c6bb733d 1/* Single entry single exit control flow regions.
fbd26352 2 Copyright (C) 2008-2019 Free Software Foundation, Inc.
c6bb733d 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
30162daa 25typedef struct ifsese_s *ifsese;
30162daa 26
c6bb733d 27/* A Single Entry, Single Exit region is a part of the CFG delimited
28 by two edges. */
251317e4 29class sese_l
c6bb733d 30{
251317e4 31public:
f032380c 32 sese_l (edge e, edge x) : entry (e), exit (x) {}
33
f032380c 34 operator bool () const { return entry && exit; }
35
f032380c 36 edge entry;
37 edge exit;
38};
39
c1616982 40void print_edge (FILE *file, const_edge e);
41void print_sese (FILE *file, const sese_l &s);
42void dump_edge (const_edge e);
43void dump_sese (const sese_l &);
44
f032380c 45/* Get the entry of an sese S. */
46
47static inline basic_block
48get_entry_bb (sese_l &s)
49{
50 return s.entry->dest;
51}
52
53/* Get the exit of an sese S. */
54
55static inline basic_block
56get_exit_bb (sese_l &s)
57{
58 return s.exit->src;
59}
60
30162daa 61/* Returns the index of V where ELEM can be found. -1 Otherwise. */
30162daa 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
f032380c 74/* A helper structure for bookkeeping information about a scop in graphite. */
251317e4 75typedef class sese_info_t
f032380c 76{
251317e4 77public:
f032380c 78 /* The SESE region. */
79 sese_l region;
c6bb733d 80
74936b22 81 /* Liveout vars. */
82 bitmap liveout;
83
84 /* Liveout in debug stmts. */
85 bitmap debug_liveout;
86
c6bb733d 87 /* Parameters used within the SCOP. */
f1f41a6c 88 vec<tree> params;
c6bb733d 89
cbd0be31 90 /* Maps an old name to a new decl. */
91 hash_map<tree, tree> *rename_map;
30162daa 92
0e526381 93 /* Basic blocks contained in this SESE. */
94 vec<basic_block> bbs;
c6bb733d 95
30162daa 96 /* The condition region generated for this sese. */
97 ifsese if_region;
98
99} *sese_info_p;
c6bb733d 100
f032380c 101extern sese_info_p new_sese_info (edge, edge);
102extern void free_sese_info (sese_info_p);
103extern void sese_insert_phis_for_liveouts (sese_info_p, basic_block, edge, edge);
2e966e2a 104extern class loop *outermost_loop_in_sese (sese_l &, basic_block);
d523d0c4 105extern tree scalar_evolution_in_region (const sese_l &, loop_p, tree);
c604a230 106extern bool scev_analyzable_p (tree, sese_l &);
d523d0c4 107extern bool invariant_in_sese_p_rec (tree, const sese_l &, bool *);
74936b22 108extern void sese_build_liveouts (sese_info_p);
109extern bool sese_trivially_empty_bb_p (basic_block);
c6bb733d 110
c6bb733d 111/* The number of parameters in REGION. */
112
113static inline unsigned
f032380c 114sese_nb_params (sese_info_p region)
c6bb733d 115{
30162daa 116 return region->params.length ();
c6bb733d 117}
118
119/* Checks whether BB is contained in the region delimited by ENTRY and
120 EXIT blocks. */
121
122static inline bool
d523d0c4 123bb_in_region (const_basic_block bb, const_basic_block entry, const_basic_block exit)
c6bb733d 124{
c6bb733d 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
133static inline bool
d523d0c4 134bb_in_sese_p (basic_block bb, const sese_l &r)
c6bb733d 135{
f032380c 136 return bb_in_region (bb, r.entry->dest, r.exit->dest);
c6bb733d 137}
138
93514494 139/* Returns true when STMT is defined in REGION. */
140
141static inline bool
d523d0c4 142stmt_in_sese_p (gimple *stmt, const sese_l &r)
93514494 143{
144 basic_block bb = gimple_bb (stmt);
f032380c 145 return bb && bb_in_sese_p (bb, r);
93514494 146}
147
c6bb733d 148/* Returns true when NAME is defined in REGION. */
149
150static inline bool
d523d0c4 151defined_in_sese_p (tree name, const sese_l &r)
c6bb733d 152{
f032380c 153 return stmt_in_sese_p (SSA_NAME_DEF_STMT (name), r);
c6bb733d 154}
155
156/* Returns true when LOOP is in REGION. */
157
48e1416a 158static inline bool
2e966e2a 159loop_in_sese_p (class loop *loop, const sese_l &region)
c6bb733d 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 {
48e1416a 173 S0
c6bb733d 174 <- region start
175 S1
176
177 loop_2
178 S2
179
180 S3
181 <- region end
48e1416a 182 }
c6bb733d 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
188static inline unsigned int
c1616982 189sese_loop_depth (const sese_l &region, loop_p loop)
c6bb733d 190{
191 unsigned int depth = 0;
192
c6bb733d 193 while (loop_in_sese_p (loop, region))
194 {
195 depth++;
196 loop = loop_outer (loop);
197 }
198
199 return depth;
200}
201
c6bb733d 202/* A single entry single exit specialized for conditions. */
203
204typedef struct ifsese_s {
f032380c 205 sese_info_p region;
206 sese_info_p true_region;
207 sese_info_p false_region;
c6bb733d 208} *ifsese;
209
f032380c 210extern ifsese move_sese_in_condition (sese_info_p);
2bca9286 211extern void set_ifsese_condition (ifsese, tree);
c6bb733d 212extern edge get_true_edge_from_guard_bb (basic_block);
213extern edge get_false_edge_from_guard_bb (basic_block);
214
215static inline edge
216if_region_entry (ifsese if_region)
217{
f032380c 218 return if_region->region->region.entry;
c6bb733d 219}
220
221static inline edge
222if_region_exit (ifsese if_region)
223{
f032380c 224 return if_region->region->region.exit;
c6bb733d 225}
226
227static inline basic_block
228if_region_get_condition_block (ifsese if_region)
229{
230 return if_region_entry (if_region)->dest;
c6bb733d 231}
232
30162daa 233typedef std::pair <gimple *, tree> scalar_use;
234
e0c0be18 235typedef struct gimple_poly_bb
c6bb733d 236{
237 basic_block bb;
8c6b3774 238 struct poly_bb *pbb;
c6bb733d 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.
48e1416a 243
c6bb733d 244 Example:
48e1416a 245
c6bb733d 246 for (i = 0; i <= 20; i++)
247 {
248 A
48e1416a 249
c6bb733d 250 if (2i <= 8)
251 B
252 }
48e1416a 253
c6bb733d 254 So for B there is an additional condition (2i <= 8).
48e1416a 255
c6bb733d 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. */
42acab1c 260 vec<gimple *> conditions;
261 vec<gimple *> condition_cases;
f1f41a6c 262 vec<data_reference_p> data_refs;
30162daa 263 vec<scalar_use> read_scalar_refs;
264 vec<tree> write_scalar_refs;
e0c0be18 265} *gimple_poly_bb_p;
c6bb733d 266
8c6b3774 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
c6bb733d 272
273/* Return the innermost loop that contains the basic block GBB. */
274
2e966e2a 275static inline class loop *
e0c0be18 276gbb_loop (gimple_poly_bb_p gbb)
c6bb733d 277{
278 return GBB_BB (gbb)->loop_father;
279}
280
48e1416a 281/* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
c6bb733d 282 If there is no corresponding gimple loop, we return NULL. */
283
284static inline loop_p
f032380c 285gbb_loop_at_index (gimple_poly_bb_p gbb, sese_l &region, int index)
c6bb733d 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
453841f9 293 gcc_assert (loop_in_sese_p (loop, region));
294
c6bb733d 295 return loop;
296}
297
298/* The number of common loops in REGION for GBB1 and GBB2. */
299
300static inline int
f032380c 301nb_common_loops (sese_l &region, gimple_poly_bb_p gbb1, gimple_poly_bb_p gbb2)
c6bb733d 302{
303 loop_p l1 = gbb_loop (gbb1);
304 loop_p l2 = gbb_loop (gbb2);
305 loop_p common = find_common_loop (l1, l2);
48e1416a 306
c6bb733d 307 return sese_loop_depth (region, common);
308}
309
c6bb733d 310#endif