]>
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. */ | |
251317e4 | 29 | class sese_l |
c6bb733d | 30 | { |
251317e4 | 31 | public: |
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 | 40 | void print_edge (FILE *file, const_edge e); |
41 | void print_sese (FILE *file, const sese_l &s); | |
42 | void dump_edge (const_edge e); | |
43 | void dump_sese (const sese_l &); | |
44 | ||
f032380c | 45 | /* Get the entry of an sese S. */ |
46 | ||
47 | static inline basic_block | |
48 | get_entry_bb (sese_l &s) | |
49 | { | |
50 | return s.entry->dest; | |
51 | } | |
52 | ||
53 | /* Get the exit of an sese S. */ | |
54 | ||
55 | static inline basic_block | |
56 | get_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 | 62 | template<typename T> |
63 | int | |
64 | vec_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 | 75 | typedef class sese_info_t |
f032380c | 76 | { |
251317e4 | 77 | public: |
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 | 101 | extern sese_info_p new_sese_info (edge, edge); |
102 | extern void free_sese_info (sese_info_p); | |
103 | extern void sese_insert_phis_for_liveouts (sese_info_p, basic_block, edge, edge); | |
2e966e2a | 104 | extern class loop *outermost_loop_in_sese (sese_l &, basic_block); |
d523d0c4 | 105 | extern tree scalar_evolution_in_region (const sese_l &, loop_p, tree); |
c604a230 | 106 | extern bool scev_analyzable_p (tree, sese_l &); |
d523d0c4 | 107 | extern bool invariant_in_sese_p_rec (tree, const sese_l &, bool *); |
74936b22 | 108 | extern void sese_build_liveouts (sese_info_p); |
109 | extern bool sese_trivially_empty_bb_p (basic_block); | |
c6bb733d | 110 | |
c6bb733d | 111 | /* The number of parameters in REGION. */ |
112 | ||
113 | static inline unsigned | |
f032380c | 114 | sese_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 | ||
122 | static inline bool | |
d523d0c4 | 123 | bb_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 | ||
133 | static inline bool | |
d523d0c4 | 134 | bb_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 | ||
141 | static inline bool | |
d523d0c4 | 142 | stmt_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 | ||
150 | static inline bool | |
d523d0c4 | 151 | defined_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 | 158 | static inline bool |
2e966e2a | 159 | loop_in_sese_p (class loop *loop, const sese_l ®ion) |
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 | ||
188 | static inline unsigned int | |
c1616982 | 189 | sese_loop_depth (const sese_l ®ion, 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 | ||
204 | typedef 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 | 210 | extern ifsese move_sese_in_condition (sese_info_p); |
2bca9286 | 211 | extern void set_ifsese_condition (ifsese, tree); |
c6bb733d | 212 | extern edge get_true_edge_from_guard_bb (basic_block); |
213 | extern edge get_false_edge_from_guard_bb (basic_block); | |
214 | ||
215 | static inline edge | |
216 | if_region_entry (ifsese if_region) | |
217 | { | |
f032380c | 218 | return if_region->region->region.entry; |
c6bb733d | 219 | } |
220 | ||
221 | static inline edge | |
222 | if_region_exit (ifsese if_region) | |
223 | { | |
f032380c | 224 | return if_region->region->region.exit; |
c6bb733d | 225 | } |
226 | ||
227 | static inline basic_block | |
228 | if_region_get_condition_block (ifsese if_region) | |
229 | { | |
230 | return if_region_entry (if_region)->dest; | |
c6bb733d | 231 | } |
232 | ||
30162daa | 233 | typedef std::pair <gimple *, tree> scalar_use; |
234 | ||
e0c0be18 | 235 | typedef 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 | 275 | static inline class loop * |
e0c0be18 | 276 | gbb_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 | ||
284 | static inline loop_p | |
f032380c | 285 | gbb_loop_at_index (gimple_poly_bb_p gbb, sese_l ®ion, 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 | ||
300 | static inline int | |
f032380c | 301 | nb_common_loops (sese_l ®ion, 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 |