1 | /* Single entry single exit control flow regions. |
2 | Copyright (C) 2008-2023 Free Software Foundation, Inc. |
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 | |
25 | typedef struct ifsese_s *ifsese; |
26 | |
27 | /* A Single Entry, Single Exit region is a part of the CFG delimited |
28 | by two edges. */ |
29 | class sese_l |
30 | { |
31 | public: |
32 | sese_l (edge e, edge x) : entry (e), exit (x) {} |
33 | |
34 | operator bool () const { return entry && exit; } |
35 | |
36 | edge entry; |
37 | edge exit; |
38 | }; |
39 | |
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 | |
45 | /* Get the entry of an sese S. */ |
46 | |
47 | inline basic_block |
48 | get_entry_bb (const sese_l &s) |
49 | { |
50 | return s.entry->dest; |
51 | } |
52 | |
53 | /* Get the exit of an sese S. */ |
54 | |
55 | inline basic_block |
56 | get_exit_bb (const sese_l &s) |
57 | { |
58 | return s.exit->src; |
59 | } |
60 | |
61 | /* Returns the index of V where ELEM can be found. -1 Otherwise. */ |
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 | |
74 | /* A helper structure for bookkeeping information about a scop in graphite. */ |
75 | typedef class sese_info_t |
76 | { |
77 | public: |
78 | /* The SESE region. */ |
79 | sese_l region; |
80 | |
81 | /* Liveout vars. */ |
82 | bitmap liveout; |
83 | |
84 | /* Liveout in debug stmts. */ |
85 | bitmap debug_liveout; |
86 | |
87 | /* Parameters used within the SCOP. */ |
88 | vec<tree> params; |
89 | |
90 | /* Maps an old name to a new decl. */ |
91 | hash_map<tree, tree> *rename_map; |
92 | |
93 | /* Basic blocks contained in this SESE. */ |
94 | vec<basic_block> bbs; |
95 | |
96 | /* The condition region generated for this sese. */ |
97 | ifsese if_region; |
98 | |
99 | } *sese_info_p; |
100 | |
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); |
104 | extern class loop *outermost_loop_in_sese (sese_l &, basic_block); |
105 | extern tree scalar_evolution_in_region (const sese_l &, loop_p, tree); |
106 | extern bool scev_analyzable_p (tree, sese_l &); |
107 | extern bool invariant_in_sese_p_rec (tree, const sese_l &, bool *); |
108 | extern void sese_build_liveouts (sese_info_p); |
109 | extern bool sese_trivially_empty_bb_p (basic_block); |
110 | |
111 | /* The number of parameters in REGION. */ |
112 | |
113 | inline unsigned |
114 | sese_nb_params (sese_info_p region) |
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 | |
122 | inline bool |
123 | bb_in_region (const_basic_block bb, const_basic_block entry, const_basic_block exit) |
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 | |
133 | inline bool |
134 | bb_in_sese_p (basic_block bb, const sese_l &r) |
135 | { |
136 | return bb_in_region (bb, entry: r.entry->dest, exit: r.exit->dest); |
137 | } |
138 | |
139 | /* Returns true when STMT is defined in REGION. */ |
140 | |
141 | inline bool |
142 | stmt_in_sese_p (gimple *stmt, const sese_l &r) |
143 | { |
144 | basic_block bb = gimple_bb (g: stmt); |
145 | return bb && bb_in_sese_p (bb, r); |
146 | } |
147 | |
148 | /* Returns true when NAME is defined in REGION. */ |
149 | |
150 | inline bool |
151 | defined_in_sese_p (tree name, const sese_l &r) |
152 | { |
153 | return stmt_in_sese_p (SSA_NAME_DEF_STMT (name), r); |
154 | } |
155 | |
156 | /* Returns true when LOOP is in REGION. */ |
157 | |
158 | inline bool |
159 | loop_in_sese_p (class loop *loop, const sese_l ®ion) |
160 | { |
161 | return (bb_in_sese_p (bb: loop->header, r: region) |
162 | && bb_in_sese_p (bb: loop->latch, r: 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 | |
188 | inline unsigned int |
189 | sese_loop_depth (const sese_l ®ion, loop_p loop) |
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 | |
204 | typedef struct ifsese_s { |
205 | sese_info_p region; |
206 | sese_info_p true_region; |
207 | sese_info_p false_region; |
208 | } *ifsese; |
209 | |
210 | extern ifsese move_sese_in_condition (sese_info_p); |
211 | extern void set_ifsese_condition (ifsese, tree); |
212 | extern edge get_true_edge_from_guard_bb (basic_block); |
213 | extern edge get_false_edge_from_guard_bb (basic_block); |
214 | |
215 | inline edge |
216 | if_region_entry (ifsese if_region) |
217 | { |
218 | return if_region->region->region.entry; |
219 | } |
220 | |
221 | inline edge |
222 | if_region_exit (ifsese if_region) |
223 | { |
224 | return if_region->region->region.exit; |
225 | } |
226 | |
227 | inline basic_block |
228 | if_region_get_condition_block (ifsese if_region) |
229 | { |
230 | return if_region_entry (if_region)->dest; |
231 | } |
232 | |
233 | typedef std::pair <gimple *, tree> scalar_use; |
234 | |
235 | typedef struct gimple_poly_bb |
236 | { |
237 | basic_block bb; |
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. */ |
260 | vec<gimple *> conditions; |
261 | vec<gimple *> condition_cases; |
262 | vec<data_reference_p> data_refs; |
263 | vec<scalar_use> read_scalar_refs; |
264 | vec<tree> write_scalar_refs; |
265 | } *gimple_poly_bb_p; |
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 | |
275 | inline class loop * |
276 | gbb_loop (gimple_poly_bb_p gbb) |
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 | |
284 | inline loop_p |
285 | gbb_loop_at_index (gimple_poly_bb_p gbb, sese_l ®ion, int index) |
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 | |
300 | inline int |
301 | nb_common_loops (sese_l ®ion, gimple_poly_bb_p gbb1, gimple_poly_bb_p gbb2) |
302 | { |
303 | loop_p l1 = gbb_loop (gbb: gbb1); |
304 | loop_p l2 = gbb_loop (gbb: gbb2); |
305 | loop_p common = find_common_loop (l1, l2); |
306 | |
307 | return sese_loop_depth (region, loop: common); |
308 | } |
309 | |
310 | #endif |
311 | |