]>
Commit | Line | Data |
---|---|---|
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 | ||
6 | This file is part of GCC. | |
7 | ||
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) | |
11 | any later version. | |
12 | ||
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. | |
17 | ||
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/>. */ | |
21 | ||
22 | #ifndef GCC_SESE_H | |
23 | #define GCC_SESE_H | |
24 | ||
30162daa | 25 | typedef 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. */ | |
f032380c | 29 | struct sese_l |
c6bb733d | 30 | { |
f032380c | 31 | sese_l (edge e, edge x) : entry (e), exit (x) {} |
32 | ||
f032380c | 33 | operator bool () const { return entry && exit; } |
34 | ||
f032380c | 35 | edge entry; |
36 | edge exit; | |
37 | }; | |
38 | ||
c1616982 | 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 &); | |
43 | ||
f032380c | 44 | /* Get the entry of an sese S. */ |
45 | ||
46 | static inline basic_block | |
47 | get_entry_bb (sese_l &s) | |
48 | { | |
49 | return s.entry->dest; | |
50 | } | |
51 | ||
52 | /* Get the exit of an sese S. */ | |
53 | ||
54 | static inline basic_block | |
55 | get_exit_bb (sese_l &s) | |
56 | { | |
57 | return s.exit->src; | |
58 | } | |
59 | ||
30162daa | 60 | /* Returns the index of V where ELEM can be found. -1 Otherwise. */ |
30162daa | 61 | template<typename T> |
62 | int | |
63 | vec_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 | ||
f032380c | 73 | /* A helper structure for bookkeeping information about a scop in graphite. */ |
74 | typedef struct sese_info_t | |
75 | { | |
76 | /* The SESE region. */ | |
77 | sese_l region; | |
c6bb733d | 78 | |
74936b22 | 79 | /* Liveout vars. */ |
80 | bitmap liveout; | |
81 | ||
82 | /* Liveout in debug stmts. */ | |
83 | bitmap debug_liveout; | |
84 | ||
c6bb733d | 85 | /* Parameters used within the SCOP. */ |
f1f41a6c | 86 | vec<tree> params; |
c6bb733d | 87 | |
cbd0be31 | 88 | /* Maps an old name to a new decl. */ |
89 | hash_map<tree, tree> *rename_map; | |
30162daa | 90 | |
0e526381 | 91 | /* Basic blocks contained in this SESE. */ |
92 | vec<basic_block> bbs; | |
c6bb733d | 93 | |
30162daa | 94 | /* The condition region generated for this sese. */ |
95 | ifsese if_region; | |
96 | ||
97 | } *sese_info_p; | |
c6bb733d | 98 | |
f032380c | 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); | |
f032380c | 102 | extern struct loop *outermost_loop_in_sese (sese_l &, basic_block); |
d523d0c4 | 103 | extern tree scalar_evolution_in_region (const sese_l &, loop_p, tree); |
c604a230 | 104 | extern bool scev_analyzable_p (tree, sese_l &); |
d523d0c4 | 105 | extern bool invariant_in_sese_p_rec (tree, const sese_l &, bool *); |
74936b22 | 106 | extern void sese_build_liveouts (sese_info_p); |
107 | extern bool sese_trivially_empty_bb_p (basic_block); | |
c6bb733d | 108 | |
c6bb733d | 109 | /* The number of parameters in REGION. */ |
110 | ||
111 | static inline unsigned | |
f032380c | 112 | sese_nb_params (sese_info_p region) |
c6bb733d | 113 | { |
30162daa | 114 | return region->params.length (); |
c6bb733d | 115 | } |
116 | ||
117 | /* Checks whether BB is contained in the region delimited by ENTRY and | |
118 | EXIT blocks. */ | |
119 | ||
120 | static inline bool | |
d523d0c4 | 121 | bb_in_region (const_basic_block bb, const_basic_block entry, const_basic_block exit) |
c6bb733d | 122 | { |
c6bb733d | 123 | return dominated_by_p (CDI_DOMINATORS, bb, entry) |
124 | && !(dominated_by_p (CDI_DOMINATORS, bb, exit) | |
125 | && !dominated_by_p (CDI_DOMINATORS, entry, exit)); | |
126 | } | |
127 | ||
128 | /* Checks whether BB is contained in the region delimited by ENTRY and | |
129 | EXIT blocks. */ | |
130 | ||
131 | static inline bool | |
d523d0c4 | 132 | bb_in_sese_p (basic_block bb, const sese_l &r) |
c6bb733d | 133 | { |
f032380c | 134 | return bb_in_region (bb, r.entry->dest, r.exit->dest); |
c6bb733d | 135 | } |
136 | ||
93514494 | 137 | /* Returns true when STMT is defined in REGION. */ |
138 | ||
139 | static inline bool | |
d523d0c4 | 140 | stmt_in_sese_p (gimple *stmt, const sese_l &r) |
93514494 | 141 | { |
142 | basic_block bb = gimple_bb (stmt); | |
f032380c | 143 | return bb && bb_in_sese_p (bb, r); |
93514494 | 144 | } |
145 | ||
c6bb733d | 146 | /* Returns true when NAME is defined in REGION. */ |
147 | ||
148 | static inline bool | |
d523d0c4 | 149 | defined_in_sese_p (tree name, const sese_l &r) |
c6bb733d | 150 | { |
f032380c | 151 | return stmt_in_sese_p (SSA_NAME_DEF_STMT (name), r); |
c6bb733d | 152 | } |
153 | ||
154 | /* Returns true when LOOP is in REGION. */ | |
155 | ||
48e1416a | 156 | static inline bool |
d523d0c4 | 157 | loop_in_sese_p (struct loop *loop, const sese_l ®ion) |
c6bb733d | 158 | { |
159 | return (bb_in_sese_p (loop->header, region) | |
160 | && bb_in_sese_p (loop->latch, region)); | |
161 | } | |
162 | ||
163 | /* Returns the loop depth of LOOP in REGION. The loop depth | |
164 | is the same as the normal loop depth, but limited by a region. | |
165 | ||
166 | Example: | |
167 | ||
168 | loop_0 | |
169 | loop_1 | |
170 | { | |
48e1416a | 171 | S0 |
c6bb733d | 172 | <- region start |
173 | S1 | |
174 | ||
175 | loop_2 | |
176 | S2 | |
177 | ||
178 | S3 | |
179 | <- region end | |
48e1416a | 180 | } |
c6bb733d | 181 | |
182 | loop_0 does not exist in the region -> invalid | |
183 | loop_1 exists, but is not completely contained in the region -> depth 0 | |
184 | loop_2 is completely contained -> depth 1 */ | |
185 | ||
186 | static inline unsigned int | |
c1616982 | 187 | sese_loop_depth (const sese_l ®ion, loop_p loop) |
c6bb733d | 188 | { |
189 | unsigned int depth = 0; | |
190 | ||
c6bb733d | 191 | while (loop_in_sese_p (loop, region)) |
192 | { | |
193 | depth++; | |
194 | loop = loop_outer (loop); | |
195 | } | |
196 | ||
197 | return depth; | |
198 | } | |
199 | ||
c6bb733d | 200 | /* A single entry single exit specialized for conditions. */ |
201 | ||
202 | typedef struct ifsese_s { | |
f032380c | 203 | sese_info_p region; |
204 | sese_info_p true_region; | |
205 | sese_info_p false_region; | |
c6bb733d | 206 | } *ifsese; |
207 | ||
f032380c | 208 | extern ifsese move_sese_in_condition (sese_info_p); |
2bca9286 | 209 | extern void set_ifsese_condition (ifsese, tree); |
c6bb733d | 210 | extern edge get_true_edge_from_guard_bb (basic_block); |
211 | extern edge get_false_edge_from_guard_bb (basic_block); | |
212 | ||
213 | static inline edge | |
214 | if_region_entry (ifsese if_region) | |
215 | { | |
f032380c | 216 | return if_region->region->region.entry; |
c6bb733d | 217 | } |
218 | ||
219 | static inline edge | |
220 | if_region_exit (ifsese if_region) | |
221 | { | |
f032380c | 222 | return if_region->region->region.exit; |
c6bb733d | 223 | } |
224 | ||
225 | static inline basic_block | |
226 | if_region_get_condition_block (ifsese if_region) | |
227 | { | |
228 | return if_region_entry (if_region)->dest; | |
c6bb733d | 229 | } |
230 | ||
30162daa | 231 | typedef std::pair <gimple *, tree> scalar_use; |
232 | ||
e0c0be18 | 233 | typedef struct gimple_poly_bb |
c6bb733d | 234 | { |
235 | basic_block bb; | |
8c6b3774 | 236 | struct poly_bb *pbb; |
c6bb733d | 237 | |
238 | /* Lists containing the restrictions of the conditional statements | |
239 | dominating this bb. This bb can only be executed, if all conditions | |
240 | are true. | |
48e1416a | 241 | |
c6bb733d | 242 | Example: |
48e1416a | 243 | |
c6bb733d | 244 | for (i = 0; i <= 20; i++) |
245 | { | |
246 | A | |
48e1416a | 247 | |
c6bb733d | 248 | if (2i <= 8) |
249 | B | |
250 | } | |
48e1416a | 251 | |
c6bb733d | 252 | So for B there is an additional condition (2i <= 8). |
48e1416a | 253 | |
c6bb733d | 254 | List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the |
255 | corresponding element in CONDITION_CASES is not NULL_TREE. For a | |
256 | SWITCH_EXPR the corresponding element in CONDITION_CASES is a | |
257 | CASE_LABEL_EXPR. */ | |
42acab1c | 258 | vec<gimple *> conditions; |
259 | vec<gimple *> condition_cases; | |
f1f41a6c | 260 | vec<data_reference_p> data_refs; |
30162daa | 261 | vec<scalar_use> read_scalar_refs; |
262 | vec<tree> write_scalar_refs; | |
e0c0be18 | 263 | } *gimple_poly_bb_p; |
c6bb733d | 264 | |
8c6b3774 | 265 | #define GBB_BB(GBB) (GBB)->bb |
266 | #define GBB_PBB(GBB) (GBB)->pbb | |
267 | #define GBB_DATA_REFS(GBB) (GBB)->data_refs | |
268 | #define GBB_CONDITIONS(GBB) (GBB)->conditions | |
269 | #define GBB_CONDITION_CASES(GBB) (GBB)->condition_cases | |
c6bb733d | 270 | |
271 | /* Return the innermost loop that contains the basic block GBB. */ | |
272 | ||
273 | static inline struct loop * | |
e0c0be18 | 274 | gbb_loop (gimple_poly_bb_p gbb) |
c6bb733d | 275 | { |
276 | return GBB_BB (gbb)->loop_father; | |
277 | } | |
278 | ||
48e1416a | 279 | /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX. |
c6bb733d | 280 | If there is no corresponding gimple loop, we return NULL. */ |
281 | ||
282 | static inline loop_p | |
f032380c | 283 | gbb_loop_at_index (gimple_poly_bb_p gbb, sese_l ®ion, int index) |
c6bb733d | 284 | { |
285 | loop_p loop = gbb_loop (gbb); | |
286 | int depth = sese_loop_depth (region, loop); | |
287 | ||
288 | while (--depth > index) | |
289 | loop = loop_outer (loop); | |
290 | ||
453841f9 | 291 | gcc_assert (loop_in_sese_p (loop, region)); |
292 | ||
c6bb733d | 293 | return loop; |
294 | } | |
295 | ||
296 | /* The number of common loops in REGION for GBB1 and GBB2. */ | |
297 | ||
298 | static inline int | |
f032380c | 299 | nb_common_loops (sese_l ®ion, gimple_poly_bb_p gbb1, gimple_poly_bb_p gbb2) |
c6bb733d | 300 | { |
301 | loop_p l1 = gbb_loop (gbb1); | |
302 | loop_p l2 = gbb_loop (gbb2); | |
303 | loop_p common = find_common_loop (l1, l2); | |
48e1416a | 304 | |
c6bb733d | 305 | return sese_loop_depth (region, common); |
306 | } | |
307 | ||
c6bb733d | 308 | #endif |