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