1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008-2013 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 /* A Single Entry, Single Exit region is a part of the CFG delimited
26 by two edges. */
27 typedef struct sese_s
28 {
29 /* Single ENTRY and single EXIT from the SESE region. */
30 edge entry, exit;
31
32 /* Parameters used within the SCOP. */
33 vec<tree> params;
34
35 /* Loops completely contained in the SCOP. */
36 bitmap loops;
37 vec<loop_p> loop_nest;
38
39 /* Are we allowed to add more params? This is for debugging purpose. We
40 can only add new params before generating the bb domains, otherwise they
41 become invalid. */
42 bool add_params;
43 } *sese;
44
45 #define SESE_ENTRY(S) (S->entry)
46 #define SESE_ENTRY_BB(S) (S->entry->dest)
47 #define SESE_EXIT(S) (S->exit)
48 #define SESE_EXIT_BB(S) (S->exit->dest)
49 #define SESE_PARAMS(S) (S->params)
50 #define SESE_LOOPS(S) (S->loops)
51 #define SESE_LOOP_NEST(S) (S->loop_nest)
52 #define SESE_ADD_PARAMS(S) (S->add_params)
53
54 extern sese new_sese (edge, edge);
55 extern void free_sese (sese);
56 extern void sese_insert_phis_for_liveouts (sese, basic_block, edge, edge);
57 extern void build_sese_loop_nests (sese);
58 extern edge copy_bb_and_scalar_dependences (basic_block, sese, edge,
59 vec<tree> , bool *);
60 extern struct loop *outermost_loop_in_sese (sese, basic_block);
61 extern void insert_loop_close_phis (htab_t, loop_p);
62 extern void insert_guard_phis (basic_block, edge, edge, htab_t, htab_t);
63 extern tree scalar_evolution_in_region (sese, loop_p, tree);
64
65 /* Check that SESE contains LOOP. */
66
67 static inline bool
sese_contains_loop(sese sese,struct loop * loop)68 sese_contains_loop (sese sese, struct loop *loop)
69 {
70 return bitmap_bit_p (SESE_LOOPS (sese), loop->num);
71 }
72
73 /* The number of parameters in REGION. */
74
75 static inline unsigned
sese_nb_params(sese region)76 sese_nb_params (sese region)
77 {
78 return SESE_PARAMS (region).length ();
79 }
80
81 /* Checks whether BB is contained in the region delimited by ENTRY and
82 EXIT blocks. */
83
84 static inline bool
bb_in_region(basic_block bb,basic_block entry,basic_block exit)85 bb_in_region (basic_block bb, basic_block entry, basic_block exit)
86 {
87 #ifdef ENABLE_CHECKING
88 {
89 edge e;
90 edge_iterator ei;
91
92 /* Check that there are no edges coming in the region: all the
93 predecessors of EXIT are dominated by ENTRY. */
94 FOR_EACH_EDGE (e, ei, exit->preds)
95 dominated_by_p (CDI_DOMINATORS, e->src, entry);
96 }
97 #endif
98
99 return dominated_by_p (CDI_DOMINATORS, bb, entry)
100 && !(dominated_by_p (CDI_DOMINATORS, bb, exit)
101 && !dominated_by_p (CDI_DOMINATORS, entry, exit));
102 }
103
104 /* Checks whether BB is contained in the region delimited by ENTRY and
105 EXIT blocks. */
106
107 static inline bool
bb_in_sese_p(basic_block bb,sese region)108 bb_in_sese_p (basic_block bb, sese region)
109 {
110 basic_block entry = SESE_ENTRY_BB (region);
111 basic_block exit = SESE_EXIT_BB (region);
112
113 return bb_in_region (bb, entry, exit);
114 }
115
116 /* Returns true when STMT is defined in REGION. */
117
118 static inline bool
stmt_in_sese_p(gimple stmt,sese region)119 stmt_in_sese_p (gimple stmt, sese region)
120 {
121 basic_block bb = gimple_bb (stmt);
122 return bb && bb_in_sese_p (bb, region);
123 }
124
125 /* Returns true when NAME is defined in REGION. */
126
127 static inline bool
defined_in_sese_p(tree name,sese region)128 defined_in_sese_p (tree name, sese region)
129 {
130 gimple stmt = SSA_NAME_DEF_STMT (name);
131 return stmt_in_sese_p (stmt, region);
132 }
133
134 /* Returns true when LOOP is in REGION. */
135
136 static inline bool
loop_in_sese_p(struct loop * loop,sese region)137 loop_in_sese_p (struct loop *loop, sese region)
138 {
139 return (bb_in_sese_p (loop->header, region)
140 && bb_in_sese_p (loop->latch, region));
141 }
142
143 /* Returns the loop depth of LOOP in REGION. The loop depth
144 is the same as the normal loop depth, but limited by a region.
145
146 Example:
147
148 loop_0
149 loop_1
150 {
151 S0
152 <- region start
153 S1
154
155 loop_2
156 S2
157
158 S3
159 <- region end
160 }
161
162 loop_0 does not exist in the region -> invalid
163 loop_1 exists, but is not completely contained in the region -> depth 0
164 loop_2 is completely contained -> depth 1 */
165
166 static inline unsigned int
sese_loop_depth(sese region,loop_p loop)167 sese_loop_depth (sese region, loop_p loop)
168 {
169 unsigned int depth = 0;
170
171 gcc_assert ((!loop_in_sese_p (loop, region)
172 && (SESE_ENTRY_BB (region)->loop_father == loop
173 || SESE_EXIT (region)->src->loop_father == loop))
174 || loop_in_sese_p (loop, region));
175
176 while (loop_in_sese_p (loop, region))
177 {
178 depth++;
179 loop = loop_outer (loop);
180 }
181
182 return depth;
183 }
184
185 /* Splits BB to make a single entry single exit region. */
186
187 static inline sese
split_region_for_bb(basic_block bb)188 split_region_for_bb (basic_block bb)
189 {
190 edge entry, exit;
191
192 if (single_pred_p (bb))
193 entry = single_pred_edge (bb);
194 else
195 {
196 entry = split_block_after_labels (bb);
197 bb = single_succ (bb);
198 }
199
200 if (single_succ_p (bb))
201 exit = single_succ_edge (bb);
202 else
203 {
204 gimple_stmt_iterator gsi = gsi_last_bb (bb);
205 gsi_prev (&gsi);
206 exit = split_block (bb, gsi_stmt (gsi));
207 }
208
209 return new_sese (entry, exit);
210 }
211
212 /* Returns the block preceding the entry of a SESE. */
213
214 static inline basic_block
block_before_sese(sese sese)215 block_before_sese (sese sese)
216 {
217 return SESE_ENTRY (sese)->src;
218 }
219
220
221
222 /* A single entry single exit specialized for conditions. */
223
224 typedef struct ifsese_s {
225 sese region;
226 sese true_region;
227 sese false_region;
228 } *ifsese;
229
230 extern void if_region_set_false_region (ifsese, sese);
231 extern ifsese move_sese_in_condition (sese);
232 extern edge get_true_edge_from_guard_bb (basic_block);
233 extern edge get_false_edge_from_guard_bb (basic_block);
234 extern void set_ifsese_condition (ifsese, tree);
235
236 static inline edge
if_region_entry(ifsese if_region)237 if_region_entry (ifsese if_region)
238 {
239 return SESE_ENTRY (if_region->region);
240 }
241
242 static inline edge
if_region_exit(ifsese if_region)243 if_region_exit (ifsese if_region)
244 {
245 return SESE_EXIT (if_region->region);
246 }
247
248 static inline basic_block
if_region_get_condition_block(ifsese if_region)249 if_region_get_condition_block (ifsese if_region)
250 {
251 return if_region_entry (if_region)->dest;
252 }
253
254 /* Structure containing the mapping between the old names and the new
255 names used after block copy in the new loop context. */
256 typedef struct rename_map_elt_s
257 {
258 tree old_name, expr;
259 } *rename_map_elt;
260
261
262 extern void debug_rename_map (htab_t);
263 extern hashval_t rename_map_elt_info (const void *);
264 extern int eq_rename_map_elts (const void *, const void *);
265
266 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
267
268 static inline rename_map_elt
new_rename_map_elt(tree old_name,tree expr)269 new_rename_map_elt (tree old_name, tree expr)
270 {
271 rename_map_elt res;
272
273 res = XNEW (struct rename_map_elt_s);
274 res->old_name = old_name;
275 res->expr = expr;
276
277 return res;
278 }
279
280 /* Structure containing the mapping between the CLooG's induction
281 variable and the type of the old induction variable. */
282 typedef struct ivtype_map_elt_s
283 {
284 tree type;
285 const char *cloog_iv;
286 } *ivtype_map_elt;
287
288 extern void debug_ivtype_map (htab_t);
289 extern hashval_t ivtype_map_elt_info (const void *);
290 extern int eq_ivtype_map_elts (const void *, const void *);
291
292 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
293
294 static inline ivtype_map_elt
new_ivtype_map_elt(const char * cloog_iv,tree type)295 new_ivtype_map_elt (const char *cloog_iv, tree type)
296 {
297 ivtype_map_elt res;
298
299 res = XNEW (struct ivtype_map_elt_s);
300 res->cloog_iv = cloog_iv;
301 res->type = type;
302
303 return res;
304 }
305
306 /* Free and compute again all the dominators information. */
307
308 static inline void
recompute_all_dominators(void)309 recompute_all_dominators (void)
310 {
311 mark_irreducible_loops ();
312 free_dominance_info (CDI_DOMINATORS);
313 calculate_dominance_info (CDI_DOMINATORS);
314 }
315
316 typedef struct gimple_bb
317 {
318 basic_block bb;
319 struct poly_bb *pbb;
320
321 /* Lists containing the restrictions of the conditional statements
322 dominating this bb. This bb can only be executed, if all conditions
323 are true.
324
325 Example:
326
327 for (i = 0; i <= 20; i++)
328 {
329 A
330
331 if (2i <= 8)
332 B
333 }
334
335 So for B there is an additional condition (2i <= 8).
336
337 List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the
338 corresponding element in CONDITION_CASES is not NULL_TREE. For a
339 SWITCH_EXPR the corresponding element in CONDITION_CASES is a
340 CASE_LABEL_EXPR. */
341 vec<gimple> conditions;
342 vec<gimple> condition_cases;
343 vec<data_reference_p> data_refs;
344 } *gimple_bb_p;
345
346 #define GBB_BB(GBB) (GBB)->bb
347 #define GBB_PBB(GBB) (GBB)->pbb
348 #define GBB_DATA_REFS(GBB) (GBB)->data_refs
349 #define GBB_CONDITIONS(GBB) (GBB)->conditions
350 #define GBB_CONDITION_CASES(GBB) (GBB)->condition_cases
351
352 /* Return the innermost loop that contains the basic block GBB. */
353
354 static inline struct loop *
gbb_loop(struct gimple_bb * gbb)355 gbb_loop (struct gimple_bb *gbb)
356 {
357 return GBB_BB (gbb)->loop_father;
358 }
359
360 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
361 If there is no corresponding gimple loop, we return NULL. */
362
363 static inline loop_p
gbb_loop_at_index(gimple_bb_p gbb,sese region,int index)364 gbb_loop_at_index (gimple_bb_p gbb, sese region, int index)
365 {
366 loop_p loop = gbb_loop (gbb);
367 int depth = sese_loop_depth (region, loop);
368
369 while (--depth > index)
370 loop = loop_outer (loop);
371
372 gcc_assert (sese_contains_loop (region, loop));
373
374 return loop;
375 }
376
377 /* The number of common loops in REGION for GBB1 and GBB2. */
378
379 static inline int
nb_common_loops(sese region,gimple_bb_p gbb1,gimple_bb_p gbb2)380 nb_common_loops (sese region, gimple_bb_p gbb1, gimple_bb_p gbb2)
381 {
382 loop_p l1 = gbb_loop (gbb1);
383 loop_p l2 = gbb_loop (gbb2);
384 loop_p common = find_common_loop (l1, l2);
385
386 return sese_loop_depth (region, common);
387 }
388
389 /* Return true when DEF can be analyzed in REGION by the scalar
390 evolution analyzer. */
391
392 static inline bool
scev_analyzable_p(tree def,sese region)393 scev_analyzable_p (tree def, sese region)
394 {
395 loop_p loop;
396 tree scev;
397 tree type = TREE_TYPE (def);
398
399 /* When Graphite generates code for a scev, the code generator
400 expresses the scev in function of a single induction variable.
401 This is unsafe for floating point computations, as it may replace
402 a floating point sum reduction with a multiplication. The
403 following test returns false for non integer types to avoid such
404 problems. */
405 if (!INTEGRAL_TYPE_P (type)
406 && !POINTER_TYPE_P (type))
407 return false;
408
409 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
410 scev = scalar_evolution_in_region (region, loop, def);
411
412 return !chrec_contains_undetermined (scev)
413 && (TREE_CODE (scev) != SSA_NAME
414 || !defined_in_sese_p (scev, region))
415 && (tree_does_not_contain_chrecs (scev)
416 || evolution_function_is_affine_p (scev));
417 }
418
419 #endif
420