Line data Source code
1 : /* Single entry single exit control flow regions.
2 : Copyright (C) 2008-2026 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 1027 : sese_l (edge e, edge x) : entry (e), exit (x) {}
33 :
34 15023 : 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 2227 : get_entry_bb (const sese_l &s)
49 : {
50 2227 : return s.entry->dest;
51 : }
52 :
53 : /* Get the exit of an sese S. */
54 :
55 : inline basic_block
56 1516 : get_exit_bb (const sese_l &s)
57 : {
58 1516 : 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 565 : sese_nb_params (sese_info_p region)
115 : {
116 929 : 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 225805 : bb_in_region (const_basic_block bb, const_basic_block entry, const_basic_block exit)
124 : {
125 225805 : return dominated_by_p (CDI_DOMINATORS, bb, entry)
126 232374 : && !(dominated_by_p (CDI_DOMINATORS, bb, exit)
127 6569 : && !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 225805 : bb_in_sese_p (basic_block bb, const sese_l &r)
135 : {
136 225805 : return bb_in_region (bb, r.entry->dest, r.exit->dest);
137 : }
138 :
139 : /* Returns true when STMT is defined in REGION. */
140 :
141 : inline bool
142 34439 : stmt_in_sese_p (gimple *stmt, const sese_l &r)
143 : {
144 34439 : basic_block bb = gimple_bb (stmt);
145 34439 : return bb && bb_in_sese_p (bb, r);
146 : }
147 :
148 : /* Returns true when NAME is defined in REGION. */
149 :
150 : inline bool
151 34439 : defined_in_sese_p (tree name, const sese_l &r)
152 : {
153 34439 : 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 85457 : loop_in_sese_p (class loop *loop, const sese_l ®ion)
160 : {
161 85457 : return (bb_in_sese_p (loop->header, region)
162 85457 : && 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 : {
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 2041 : sese_loop_depth (const sese_l ®ion, loop_p loop)
190 : {
191 2041 : unsigned int depth = 0;
192 :
193 5591 : while (loop_in_sese_p (loop, region))
194 : {
195 3550 : depth++;
196 3550 : loop = loop_outer (loop);
197 : }
198 :
199 2041 : 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 7803 : gbb_loop (gimple_poly_bb_p gbb)
277 : {
278 5440 : 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 839 : gbb_loop_at_index (gimple_poly_bb_p gbb, sese_l ®ion, int index)
286 : {
287 839 : loop_p loop = gbb_loop (gbb);
288 839 : int depth = sese_loop_depth (region, loop);
289 :
290 1226 : while (--depth > index)
291 387 : loop = loop_outer (loop);
292 :
293 839 : gcc_assert (loop_in_sese_p (loop, region));
294 :
295 839 : 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 (gbb1);
304 : loop_p l2 = gbb_loop (gbb2);
305 : loop_p common = find_common_loop (l1, l2);
306 :
307 : return sese_loop_depth (region, common);
308 : }
309 :
310 : #endif
|
