]>
Commit | Line | Data |
---|---|---|
2abae5f1 | 1 | /* Single entry single exit control flow regions. |
5624e564 | 2 | Copyright (C) 2008-2015 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 | ||
25 | /* A Single Entry, Single Exit region is a part of the CFG delimited | |
26 | by two edges. */ | |
bafcb153 | 27 | struct sese_l |
2abae5f1 | 28 | { |
bafcb153 AK |
29 | sese_l (edge e, edge x) : entry (e), exit (x) {} |
30 | ||
bafcb153 AK |
31 | operator bool () const { return entry && exit; } |
32 | ||
bafcb153 AK |
33 | edge entry; |
34 | edge exit; | |
35 | }; | |
36 | ||
37 | /* Get the entry of an sese S. */ | |
38 | ||
39 | static inline basic_block | |
40 | get_entry_bb (sese_l &s) | |
41 | { | |
42 | return s.entry->dest; | |
43 | } | |
44 | ||
45 | /* Get the exit of an sese S. */ | |
46 | ||
47 | static inline basic_block | |
48 | get_exit_bb (sese_l &s) | |
49 | { | |
50 | return s.exit->src; | |
51 | } | |
52 | ||
53 | /* A helper structure for bookkeeping information about a scop in graphite. */ | |
54 | typedef struct sese_info_t | |
55 | { | |
56 | /* The SESE region. */ | |
57 | sese_l region; | |
2abae5f1 SP |
58 | |
59 | /* Parameters used within the SCOP. */ | |
9771b263 | 60 | vec<tree> params; |
2abae5f1 | 61 | |
91bf00a9 | 62 | /* Loops completely contained in this SESE. */ |
2abae5f1 | 63 | bitmap loops; |
9771b263 | 64 | vec<loop_p> loop_nest; |
b0b5710c AK |
65 | |
66 | /* Basic blocks contained in this SESE. */ | |
67 | vec<basic_block> bbs; | |
bafcb153 | 68 | } *sese_info_p; |
2abae5f1 | 69 | |
2abae5f1 | 70 | #define SESE_PARAMS(S) (S->params) |
2abae5f1 SP |
71 | #define SESE_LOOPS(S) (S->loops) |
72 | #define SESE_LOOP_NEST(S) (S->loop_nest) | |
2abae5f1 | 73 | |
bafcb153 AK |
74 | extern sese_info_p new_sese_info (edge, edge); |
75 | extern void free_sese_info (sese_info_p); | |
76 | extern void sese_insert_phis_for_liveouts (sese_info_p, basic_block, edge, edge); | |
77 | extern void build_sese_loop_nests (sese_info_p); | |
78 | extern edge copy_bb_and_scalar_dependences (basic_block, sese_info_p, edge, | |
9771b263 | 79 | vec<tree> , bool *); |
bafcb153 AK |
80 | extern struct loop *outermost_loop_in_sese (sese_l &, basic_block); |
81 | extern tree scalar_evolution_in_region (sese_l &, loop_p, tree); | |
78fd2726 | 82 | extern bool invariant_in_sese_p_rec (tree, sese_l &, bool *); |
2abae5f1 SP |
83 | |
84 | /* Check that SESE contains LOOP. */ | |
85 | ||
86 | static inline bool | |
bafcb153 | 87 | sese_contains_loop (sese_info_p sese, struct loop *loop) |
2abae5f1 SP |
88 | { |
89 | return bitmap_bit_p (SESE_LOOPS (sese), loop->num); | |
90 | } | |
91 | ||
92 | /* The number of parameters in REGION. */ | |
93 | ||
94 | static inline unsigned | |
bafcb153 | 95 | sese_nb_params (sese_info_p region) |
2abae5f1 | 96 | { |
9771b263 | 97 | return SESE_PARAMS (region).length (); |
2abae5f1 SP |
98 | } |
99 | ||
100 | /* Checks whether BB is contained in the region delimited by ENTRY and | |
101 | EXIT blocks. */ | |
102 | ||
103 | static inline bool | |
104 | bb_in_region (basic_block bb, basic_block entry, basic_block exit) | |
105 | { | |
a6c764d0 MM |
106 | /* FIXME: PR67842. */ |
107 | #if 0 | |
108 | if (flag_checking) | |
109 | { | |
110 | edge e; | |
111 | edge_iterator ei; | |
112 | ||
113 | /* Check that there are no edges coming in the region: all the | |
114 | predecessors of EXIT are dominated by ENTRY. */ | |
115 | FOR_EACH_EDGE (e, ei, exit->preds) | |
116 | gcc_assert (dominated_by_p (CDI_DOMINATORS, e->src, entry)); | |
117 | } | |
2abae5f1 SP |
118 | #endif |
119 | ||
120 | return dominated_by_p (CDI_DOMINATORS, bb, entry) | |
121 | && !(dominated_by_p (CDI_DOMINATORS, bb, exit) | |
122 | && !dominated_by_p (CDI_DOMINATORS, entry, exit)); | |
123 | } | |
124 | ||
125 | /* Checks whether BB is contained in the region delimited by ENTRY and | |
126 | EXIT blocks. */ | |
127 | ||
128 | static inline bool | |
bafcb153 | 129 | bb_in_sese_p (basic_block bb, sese_l &r) |
2abae5f1 | 130 | { |
bafcb153 | 131 | return bb_in_region (bb, r.entry->dest, r.exit->dest); |
2abae5f1 SP |
132 | } |
133 | ||
a30e5345 SP |
134 | /* Returns true when STMT is defined in REGION. */ |
135 | ||
136 | static inline bool | |
bafcb153 | 137 | stmt_in_sese_p (gimple *stmt, sese_l &r) |
a30e5345 SP |
138 | { |
139 | basic_block bb = gimple_bb (stmt); | |
bafcb153 | 140 | return bb && bb_in_sese_p (bb, r); |
a30e5345 SP |
141 | } |
142 | ||
2abae5f1 SP |
143 | /* Returns true when NAME is defined in REGION. */ |
144 | ||
145 | static inline bool | |
bafcb153 | 146 | defined_in_sese_p (tree name, sese_l &r) |
2abae5f1 | 147 | { |
bafcb153 | 148 | return stmt_in_sese_p (SSA_NAME_DEF_STMT (name), r); |
2abae5f1 SP |
149 | } |
150 | ||
151 | /* Returns true when LOOP is in REGION. */ | |
152 | ||
b8698a0f | 153 | static inline bool |
bafcb153 | 154 | loop_in_sese_p (struct loop *loop, sese_l ®ion) |
2abae5f1 SP |
155 | { |
156 | return (bb_in_sese_p (loop->header, region) | |
157 | && bb_in_sese_p (loop->latch, region)); | |
158 | } | |
159 | ||
160 | /* Returns the loop depth of LOOP in REGION. The loop depth | |
161 | is the same as the normal loop depth, but limited by a region. | |
162 | ||
163 | Example: | |
164 | ||
165 | loop_0 | |
166 | loop_1 | |
167 | { | |
b8698a0f | 168 | S0 |
2abae5f1 SP |
169 | <- region start |
170 | S1 | |
171 | ||
172 | loop_2 | |
173 | S2 | |
174 | ||
175 | S3 | |
176 | <- region end | |
b8698a0f | 177 | } |
2abae5f1 SP |
178 | |
179 | loop_0 does not exist in the region -> invalid | |
180 | loop_1 exists, but is not completely contained in the region -> depth 0 | |
181 | loop_2 is completely contained -> depth 1 */ | |
182 | ||
183 | static inline unsigned int | |
bafcb153 | 184 | sese_loop_depth (sese_l ®ion, loop_p loop) |
2abae5f1 SP |
185 | { |
186 | unsigned int depth = 0; | |
187 | ||
2abae5f1 SP |
188 | while (loop_in_sese_p (loop, region)) |
189 | { | |
190 | depth++; | |
191 | loop = loop_outer (loop); | |
192 | } | |
193 | ||
194 | return depth; | |
195 | } | |
196 | ||
2abae5f1 SP |
197 | /* A single entry single exit specialized for conditions. */ |
198 | ||
199 | typedef struct ifsese_s { | |
bafcb153 AK |
200 | sese_info_p region; |
201 | sese_info_p true_region; | |
202 | sese_info_p false_region; | |
2abae5f1 SP |
203 | } *ifsese; |
204 | ||
bafcb153 AK |
205 | extern void if_region_set_false_region (ifsese, sese_info_p); |
206 | extern ifsese move_sese_in_condition (sese_info_p); | |
2abae5f1 SP |
207 | extern edge get_true_edge_from_guard_bb (basic_block); |
208 | extern edge get_false_edge_from_guard_bb (basic_block); | |
3c7c0158 | 209 | extern void set_ifsese_condition (ifsese, tree); |
2abae5f1 SP |
210 | |
211 | static inline edge | |
212 | if_region_entry (ifsese if_region) | |
213 | { | |
bafcb153 | 214 | return if_region->region->region.entry; |
2abae5f1 SP |
215 | } |
216 | ||
217 | static inline edge | |
218 | if_region_exit (ifsese if_region) | |
219 | { | |
bafcb153 | 220 | return if_region->region->region.exit; |
2abae5f1 SP |
221 | } |
222 | ||
223 | static inline basic_block | |
224 | if_region_get_condition_block (ifsese if_region) | |
225 | { | |
226 | return if_region_entry (if_region)->dest; | |
2abae5f1 SP |
227 | } |
228 | ||
2abae5f1 SP |
229 | /* Free and compute again all the dominators information. */ |
230 | ||
231 | static inline void | |
232 | recompute_all_dominators (void) | |
233 | { | |
234 | mark_irreducible_loops (); | |
235 | free_dominance_info (CDI_DOMINATORS); | |
2abae5f1 | 236 | calculate_dominance_info (CDI_DOMINATORS); |
7009b073 SP |
237 | |
238 | free_dominance_info (CDI_POST_DOMINATORS); | |
239 | calculate_dominance_info (CDI_POST_DOMINATORS); | |
2abae5f1 SP |
240 | } |
241 | ||
65ef70d6 | 242 | typedef struct gimple_poly_bb |
2abae5f1 SP |
243 | { |
244 | basic_block bb; | |
efa21390 | 245 | struct poly_bb *pbb; |
2abae5f1 SP |
246 | |
247 | /* Lists containing the restrictions of the conditional statements | |
248 | dominating this bb. This bb can only be executed, if all conditions | |
249 | are true. | |
b8698a0f | 250 | |
2abae5f1 | 251 | Example: |
b8698a0f | 252 | |
2abae5f1 SP |
253 | for (i = 0; i <= 20; i++) |
254 | { | |
255 | A | |
b8698a0f | 256 | |
2abae5f1 SP |
257 | if (2i <= 8) |
258 | B | |
259 | } | |
b8698a0f | 260 | |
2abae5f1 | 261 | So for B there is an additional condition (2i <= 8). |
b8698a0f | 262 | |
2abae5f1 SP |
263 | List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the |
264 | corresponding element in CONDITION_CASES is not NULL_TREE. For a | |
265 | SWITCH_EXPR the corresponding element in CONDITION_CASES is a | |
266 | CASE_LABEL_EXPR. */ | |
355fe088 TS |
267 | vec<gimple *> conditions; |
268 | vec<gimple *> condition_cases; | |
9771b263 | 269 | vec<data_reference_p> data_refs; |
65ef70d6 | 270 | } *gimple_poly_bb_p; |
2abae5f1 | 271 | |
efa21390 SP |
272 | #define GBB_BB(GBB) (GBB)->bb |
273 | #define GBB_PBB(GBB) (GBB)->pbb | |
274 | #define GBB_DATA_REFS(GBB) (GBB)->data_refs | |
275 | #define GBB_CONDITIONS(GBB) (GBB)->conditions | |
276 | #define GBB_CONDITION_CASES(GBB) (GBB)->condition_cases | |
2abae5f1 SP |
277 | |
278 | /* Return the innermost loop that contains the basic block GBB. */ | |
279 | ||
280 | static inline struct loop * | |
65ef70d6 | 281 | gbb_loop (gimple_poly_bb_p gbb) |
2abae5f1 SP |
282 | { |
283 | return GBB_BB (gbb)->loop_father; | |
284 | } | |
285 | ||
b8698a0f | 286 | /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX. |
2abae5f1 SP |
287 | If there is no corresponding gimple loop, we return NULL. */ |
288 | ||
289 | static inline loop_p | |
bafcb153 | 290 | gbb_loop_at_index (gimple_poly_bb_p gbb, sese_l ®ion, int index) |
2abae5f1 SP |
291 | { |
292 | loop_p loop = gbb_loop (gbb); | |
293 | int depth = sese_loop_depth (region, loop); | |
294 | ||
295 | while (--depth > index) | |
296 | loop = loop_outer (loop); | |
297 | ||
bafcb153 | 298 | gcc_assert (loop_in_sese_p (loop, region)); |
2abae5f1 SP |
299 | |
300 | return loop; | |
301 | } | |
302 | ||
303 | /* The number of common loops in REGION for GBB1 and GBB2. */ | |
304 | ||
305 | static inline int | |
bafcb153 | 306 | nb_common_loops (sese_l ®ion, gimple_poly_bb_p gbb1, gimple_poly_bb_p gbb2) |
2abae5f1 SP |
307 | { |
308 | loop_p l1 = gbb_loop (gbb1); | |
309 | loop_p l2 = gbb_loop (gbb2); | |
310 | loop_p common = find_common_loop (l1, l2); | |
b8698a0f | 311 | |
2abae5f1 SP |
312 | return sese_loop_depth (region, common); |
313 | } | |
314 | ||
2e286fd2 SP |
315 | /* Return true when DEF can be analyzed in REGION by the scalar |
316 | evolution analyzer. */ | |
317 | ||
318 | static inline bool | |
bafcb153 | 319 | scev_analyzable_p (tree def, sese_l ®ion) |
2e286fd2 | 320 | { |
8ba78f92 SP |
321 | loop_p loop; |
322 | tree scev; | |
323 | tree type = TREE_TYPE (def); | |
324 | ||
325 | /* When Graphite generates code for a scev, the code generator | |
326 | expresses the scev in function of a single induction variable. | |
327 | This is unsafe for floating point computations, as it may replace | |
328 | a floating point sum reduction with a multiplication. The | |
329 | following test returns false for non integer types to avoid such | |
330 | problems. */ | |
331 | if (!INTEGRAL_TYPE_P (type) | |
332 | && !POINTER_TYPE_P (type)) | |
333 | return false; | |
334 | ||
335 | loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def)); | |
336 | scev = scalar_evolution_in_region (region, loop, def); | |
2e286fd2 SP |
337 | |
338 | return !chrec_contains_undetermined (scev) | |
9be8ba7e SP |
339 | && (TREE_CODE (scev) != SSA_NAME |
340 | || !defined_in_sese_p (scev, region)) | |
f36fc876 SP |
341 | && (tree_does_not_contain_chrecs (scev) |
342 | || evolution_function_is_affine_p (scev)); | |
2e286fd2 SP |
343 | } |
344 | ||
2abae5f1 | 345 | #endif |