gcc/
[official-gcc.git] / gcc / sese.h
blob52aa8688cbffaef17ad7a085d43c47e050264caf
1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008-2015 Free Software Foundation, Inc.
3 Contributed by Jan Sjodin <jan.sjodin@amd.com> and
4 Sebastian Pop <sebastian.pop@amd.com>.
6 This file is part of GCC.
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.
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.
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/>. */
22 #ifndef GCC_SESE_H
23 #define GCC_SESE_H
25 /* A Single Entry, Single Exit region is a part of the CFG delimited
26 by two edges. */
27 typedef struct sese_s
29 /* Single ENTRY and single EXIT from the SESE region. */
30 edge entry, exit;
32 /* Parameters used within the SCOP. */
33 vec<tree> params;
35 /* Loops completely contained in the SCOP. */
36 bitmap loops;
37 vec<loop_p> loop_nest;
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;
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)
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 tree scalar_evolution_in_region (sese, loop_p, tree);
63 /* Check that SESE contains LOOP. */
65 static inline bool
66 sese_contains_loop (sese sese, struct loop *loop)
68 return bitmap_bit_p (SESE_LOOPS (sese), loop->num);
71 /* The number of parameters in REGION. */
73 static inline unsigned
74 sese_nb_params (sese region)
76 return SESE_PARAMS (region).length ();
79 /* Checks whether BB is contained in the region delimited by ENTRY and
80 EXIT blocks. */
82 static inline bool
83 bb_in_region (basic_block bb, basic_block entry, basic_block exit)
85 #ifdef ENABLE_CHECKING
87 edge e;
88 edge_iterator ei;
90 /* Check that there are no edges coming in the region: all the
91 predecessors of EXIT are dominated by ENTRY. */
92 FOR_EACH_EDGE (e, ei, exit->preds)
93 dominated_by_p (CDI_DOMINATORS, e->src, entry);
95 #endif
97 return dominated_by_p (CDI_DOMINATORS, bb, entry)
98 && !(dominated_by_p (CDI_DOMINATORS, bb, exit)
99 && !dominated_by_p (CDI_DOMINATORS, entry, exit));
102 /* Checks whether BB is contained in the region delimited by ENTRY and
103 EXIT blocks. */
105 static inline bool
106 bb_in_sese_p (basic_block bb, sese region)
108 basic_block entry = SESE_ENTRY_BB (region);
109 basic_block exit = SESE_EXIT_BB (region);
111 return bb_in_region (bb, entry, exit);
114 /* Returns true when STMT is defined in REGION. */
116 static inline bool
117 stmt_in_sese_p (gimple stmt, sese region)
119 basic_block bb = gimple_bb (stmt);
120 return bb && bb_in_sese_p (bb, region);
123 /* Returns true when NAME is defined in REGION. */
125 static inline bool
126 defined_in_sese_p (tree name, sese region)
128 gimple stmt = SSA_NAME_DEF_STMT (name);
129 return stmt_in_sese_p (stmt, region);
132 /* Returns true when LOOP is in REGION. */
134 static inline bool
135 loop_in_sese_p (struct loop *loop, sese region)
137 return (bb_in_sese_p (loop->header, region)
138 && bb_in_sese_p (loop->latch, region));
141 /* Returns the loop depth of LOOP in REGION. The loop depth
142 is the same as the normal loop depth, but limited by a region.
144 Example:
146 loop_0
147 loop_1
150 <- region start
153 loop_2
157 <- region end
160 loop_0 does not exist in the region -> invalid
161 loop_1 exists, but is not completely contained in the region -> depth 0
162 loop_2 is completely contained -> depth 1 */
164 static inline unsigned int
165 sese_loop_depth (sese region, loop_p loop)
167 unsigned int depth = 0;
169 gcc_assert ((!loop_in_sese_p (loop, region)
170 && (SESE_ENTRY_BB (region)->loop_father == loop
171 || SESE_EXIT (region)->src->loop_father == loop))
172 || loop_in_sese_p (loop, region));
174 while (loop_in_sese_p (loop, region))
176 depth++;
177 loop = loop_outer (loop);
180 return depth;
183 /* Splits BB to make a single entry single exit region. */
185 static inline sese
186 split_region_for_bb (basic_block bb)
188 edge entry, exit;
190 if (single_pred_p (bb))
191 entry = single_pred_edge (bb);
192 else
194 entry = split_block_after_labels (bb);
195 bb = single_succ (bb);
198 if (single_succ_p (bb))
199 exit = single_succ_edge (bb);
200 else
202 gimple_stmt_iterator gsi = gsi_last_bb (bb);
203 gsi_prev (&gsi);
204 exit = split_block (bb, gsi_stmt (gsi));
207 return new_sese (entry, exit);
210 /* Returns the block preceding the entry of a SESE. */
212 static inline basic_block
213 block_before_sese (sese sese)
215 return SESE_ENTRY (sese)->src;
220 /* A single entry single exit specialized for conditions. */
222 typedef struct ifsese_s {
223 sese region;
224 sese true_region;
225 sese false_region;
226 } *ifsese;
228 extern void if_region_set_false_region (ifsese, sese);
229 extern ifsese move_sese_in_condition (sese);
230 extern edge get_true_edge_from_guard_bb (basic_block);
231 extern edge get_false_edge_from_guard_bb (basic_block);
232 extern void set_ifsese_condition (ifsese, tree);
234 static inline edge
235 if_region_entry (ifsese if_region)
237 return SESE_ENTRY (if_region->region);
240 static inline edge
241 if_region_exit (ifsese if_region)
243 return SESE_EXIT (if_region->region);
246 static inline basic_block
247 if_region_get_condition_block (ifsese if_region)
249 return if_region_entry (if_region)->dest;
252 /* Free and compute again all the dominators information. */
254 static inline void
255 recompute_all_dominators (void)
257 mark_irreducible_loops ();
258 free_dominance_info (CDI_DOMINATORS);
259 calculate_dominance_info (CDI_DOMINATORS);
262 typedef struct gimple_bb
264 basic_block bb;
265 struct poly_bb *pbb;
267 /* Lists containing the restrictions of the conditional statements
268 dominating this bb. This bb can only be executed, if all conditions
269 are true.
271 Example:
273 for (i = 0; i <= 20; i++)
277 if (2i <= 8)
281 So for B there is an additional condition (2i <= 8).
283 List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the
284 corresponding element in CONDITION_CASES is not NULL_TREE. For a
285 SWITCH_EXPR the corresponding element in CONDITION_CASES is a
286 CASE_LABEL_EXPR. */
287 vec<gimple> conditions;
288 vec<gimple> condition_cases;
289 vec<data_reference_p> data_refs;
290 } *gimple_bb_p;
292 #define GBB_BB(GBB) (GBB)->bb
293 #define GBB_PBB(GBB) (GBB)->pbb
294 #define GBB_DATA_REFS(GBB) (GBB)->data_refs
295 #define GBB_CONDITIONS(GBB) (GBB)->conditions
296 #define GBB_CONDITION_CASES(GBB) (GBB)->condition_cases
298 /* Return the innermost loop that contains the basic block GBB. */
300 static inline struct loop *
301 gbb_loop (struct gimple_bb *gbb)
303 return GBB_BB (gbb)->loop_father;
306 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
307 If there is no corresponding gimple loop, we return NULL. */
309 static inline loop_p
310 gbb_loop_at_index (gimple_bb_p gbb, sese region, int index)
312 loop_p loop = gbb_loop (gbb);
313 int depth = sese_loop_depth (region, loop);
315 while (--depth > index)
316 loop = loop_outer (loop);
318 gcc_assert (sese_contains_loop (region, loop));
320 return loop;
323 /* The number of common loops in REGION for GBB1 and GBB2. */
325 static inline int
326 nb_common_loops (sese region, gimple_bb_p gbb1, gimple_bb_p gbb2)
328 loop_p l1 = gbb_loop (gbb1);
329 loop_p l2 = gbb_loop (gbb2);
330 loop_p common = find_common_loop (l1, l2);
332 return sese_loop_depth (region, common);
335 /* Return true when DEF can be analyzed in REGION by the scalar
336 evolution analyzer. */
338 static inline bool
339 scev_analyzable_p (tree def, sese region)
341 loop_p loop;
342 tree scev;
343 tree type = TREE_TYPE (def);
345 /* When Graphite generates code for a scev, the code generator
346 expresses the scev in function of a single induction variable.
347 This is unsafe for floating point computations, as it may replace
348 a floating point sum reduction with a multiplication. The
349 following test returns false for non integer types to avoid such
350 problems. */
351 if (!INTEGRAL_TYPE_P (type)
352 && !POINTER_TYPE_P (type))
353 return false;
355 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
356 scev = scalar_evolution_in_region (region, loop, def);
358 return !chrec_contains_undetermined (scev)
359 && (TREE_CODE (scev) != SSA_NAME
360 || !defined_in_sese_p (scev, region))
361 && (tree_does_not_contain_chrecs (scev)
362 || evolution_function_is_affine_p (scev));
365 #endif