Branch data Line data Source code
1 : : /* Single entry single exit control flow regions.
2 : : Copyright (C) 2008-2024 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 : 1013 : sese_l (edge e, edge x) : entry (e), exit (x) {}
33 : :
34 : 14736 : 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 : 2157 : get_entry_bb (const sese_l &s)
49 : : {
50 : 2157 : return s.entry->dest;
51 : : }
52 : :
53 : : /* Get the exit of an sese S. */
54 : :
55 : : inline basic_block
56 : 1485 : get_exit_bb (const sese_l &s)
57 : : {
58 : 1485 : 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 : 544 : sese_nb_params (sese_info_p region)
115 : : {
116 : 895 : 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 : 217372 : bb_in_region (const_basic_block bb, const_basic_block entry, const_basic_block exit)
124 : : {
125 : 217372 : return dominated_by_p (CDI_DOMINATORS, bb, entry)
126 : 223560 : && !(dominated_by_p (CDI_DOMINATORS, bb, exit)
127 : 6188 : && !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 : 217372 : bb_in_sese_p (basic_block bb, const sese_l &r)
135 : : {
136 : 217372 : 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 : 33509 : stmt_in_sese_p (gimple *stmt, const sese_l &r)
143 : : {
144 : 33509 : basic_block bb = gimple_bb (stmt);
145 : 33509 : return bb && bb_in_sese_p (bb, r);
146 : : }
147 : :
148 : : /* Returns true when NAME is defined in REGION. */
149 : :
150 : : inline bool
151 : 33509 : defined_in_sese_p (tree name, const sese_l &r)
152 : : {
153 : 33509 : 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 : 82526 : loop_in_sese_p (class loop *loop, const sese_l ®ion)
160 : : {
161 : 82526 : return (bb_in_sese_p (loop->header, region)
162 : 82526 : && 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 : 1934 : sese_loop_depth (const sese_l ®ion, loop_p loop)
190 : : {
191 : 1934 : unsigned int depth = 0;
192 : :
193 : 5252 : while (loop_in_sese_p (loop, region))
194 : : {
195 : 3318 : depth++;
196 : 3318 : loop = loop_outer (loop);
197 : : }
198 : :
199 : 1934 : 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 : 7285 : gbb_loop (gimple_poly_bb_p gbb)
277 : : {
278 : 5072 : 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 : 789 : gbb_loop_at_index (gimple_poly_bb_p gbb, sese_l ®ion, int index)
286 : : {
287 : 789 : loop_p loop = gbb_loop (gbb);
288 : 789 : int depth = sese_loop_depth (region, loop);
289 : :
290 : 1137 : while (--depth > index)
291 : 348 : loop = loop_outer (loop);
292 : :
293 : 789 : gcc_assert (loop_in_sese_p (loop, region));
294 : :
295 : 789 : 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
|
