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>.
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify
9it under the terms of the GNU General Public License as published by
10the Free Software Foundation; either version 3, or (at your option)
11any later version.
12
13GCC is distributed in the hope that it will be useful,
14but WITHOUT ANY WARRANTY; without even the implied warranty of
15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16GNU General Public License for more details.
17
18You should have received a copy of the GNU General Public License
19along 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.  */
27typedef 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
54extern sese new_sese (edge, edge);
55extern void free_sese (sese);
56extern void sese_insert_phis_for_liveouts (sese, basic_block, edge, edge);
57extern void build_sese_loop_nests (sese);
58extern edge copy_bb_and_scalar_dependences (basic_block, sese, edge,
59					    vec<tree> , bool *);
60extern struct loop *outermost_loop_in_sese (sese, basic_block);
61extern tree scalar_evolution_in_region (sese, loop_p, tree);
62
63/* Check that SESE contains LOOP.  */
64
65static inline bool
66sese_contains_loop (sese sese, struct loop *loop)
67{
68  return bitmap_bit_p (SESE_LOOPS (sese), loop->num);
69}
70
71/* The number of parameters in REGION. */
72
73static inline unsigned
74sese_nb_params (sese region)
75{
76  return SESE_PARAMS (region).length ();
77}
78
79/* Checks whether BB is contained in the region delimited by ENTRY and
80   EXIT blocks.  */
81
82static inline bool
83bb_in_region (basic_block bb, basic_block entry, basic_block exit)
84{
85#ifdef ENABLE_CHECKING
86  {
87    edge e;
88    edge_iterator ei;
89
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);
94  }
95#endif
96
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));
100}
101
102/* Checks whether BB is contained in the region delimited by ENTRY and
103   EXIT blocks.  */
104
105static inline bool
106bb_in_sese_p (basic_block bb, sese region)
107{
108  basic_block entry = SESE_ENTRY_BB (region);
109  basic_block exit = SESE_EXIT_BB (region);
110
111  return bb_in_region (bb, entry, exit);
112}
113
114/* Returns true when STMT is defined in REGION.  */
115
116static inline bool
117stmt_in_sese_p (gimple stmt, sese region)
118{
119  basic_block bb = gimple_bb (stmt);
120  return bb && bb_in_sese_p (bb, region);
121}
122
123/* Returns true when NAME is defined in REGION.  */
124
125static inline bool
126defined_in_sese_p (tree name, sese region)
127{
128  gimple stmt = SSA_NAME_DEF_STMT (name);
129  return stmt_in_sese_p (stmt, region);
130}
131
132/* Returns true when LOOP is in REGION.  */
133
134static inline bool
135loop_in_sese_p (struct loop *loop, sese region)
136{
137  return (bb_in_sese_p (loop->header, region)
138	  && bb_in_sese_p (loop->latch, region));
139}
140
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.
143
144   Example:
145
146   loop_0
147     loop_1
148       {
149         S0
150            <- region start
151         S1
152
153         loop_2
154           S2
155
156         S3
157            <- region end
158       }
159
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  */
163
164static inline unsigned int
165sese_loop_depth (sese region, loop_p loop)
166{
167  unsigned int depth = 0;
168
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));
173
174  while (loop_in_sese_p (loop, region))
175    {
176      depth++;
177      loop = loop_outer (loop);
178    }
179
180  return depth;
181}
182
183/* Splits BB to make a single entry single exit region.  */
184
185static inline sese
186split_region_for_bb (basic_block bb)
187{
188  edge entry, exit;
189
190  if (single_pred_p (bb))
191    entry = single_pred_edge (bb);
192  else
193    {
194      entry = split_block_after_labels (bb);
195      bb = single_succ (bb);
196    }
197
198  if (single_succ_p (bb))
199    exit = single_succ_edge (bb);
200  else
201    {
202      gimple_stmt_iterator gsi = gsi_last_bb (bb);
203      gsi_prev (&gsi);
204      exit = split_block (bb, gsi_stmt (gsi));
205    }
206
207  return new_sese (entry, exit);
208}
209
210/* Returns the block preceding the entry of a SESE.  */
211
212static inline basic_block
213block_before_sese (sese sese)
214{
215  return SESE_ENTRY (sese)->src;
216}
217
218
219
220/* A single entry single exit specialized for conditions.  */
221
222typedef struct ifsese_s {
223  sese region;
224  sese true_region;
225  sese false_region;
226} *ifsese;
227
228extern void if_region_set_false_region (ifsese, sese);
229extern ifsese move_sese_in_condition (sese);
230extern edge get_true_edge_from_guard_bb (basic_block);
231extern edge get_false_edge_from_guard_bb (basic_block);
232extern void set_ifsese_condition (ifsese, tree);
233
234static inline edge
235if_region_entry (ifsese if_region)
236{
237  return SESE_ENTRY (if_region->region);
238}
239
240static inline edge
241if_region_exit (ifsese if_region)
242{
243  return SESE_EXIT (if_region->region);
244}
245
246static inline basic_block
247if_region_get_condition_block (ifsese if_region)
248{
249  return if_region_entry (if_region)->dest;
250}
251
252/* Free and compute again all the dominators information.  */
253
254static inline void
255recompute_all_dominators (void)
256{
257  mark_irreducible_loops ();
258  free_dominance_info (CDI_DOMINATORS);
259  calculate_dominance_info (CDI_DOMINATORS);
260}
261
262typedef struct gimple_bb
263{
264  basic_block bb;
265  struct poly_bb *pbb;
266
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.
270
271     Example:
272
273     for (i = 0; i <= 20; i++)
274     {
275       A
276
277       if (2i <= 8)
278         B
279     }
280
281     So for B there is an additional condition (2i <= 8).
282
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;
291
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
297
298/* Return the innermost loop that contains the basic block GBB.  */
299
300static inline struct loop *
301gbb_loop (struct gimple_bb *gbb)
302{
303  return GBB_BB (gbb)->loop_father;
304}
305
306/* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
307   If there is no corresponding gimple loop, we return NULL.  */
308
309static inline loop_p
310gbb_loop_at_index (gimple_bb_p gbb, sese region, int index)
311{
312  loop_p loop = gbb_loop (gbb);
313  int depth = sese_loop_depth (region, loop);
314
315  while (--depth > index)
316    loop = loop_outer (loop);
317
318  gcc_assert (sese_contains_loop (region, loop));
319
320  return loop;
321}
322
323/* The number of common loops in REGION for GBB1 and GBB2.  */
324
325static inline int
326nb_common_loops (sese region, gimple_bb_p gbb1, gimple_bb_p gbb2)
327{
328  loop_p l1 = gbb_loop (gbb1);
329  loop_p l2 = gbb_loop (gbb2);
330  loop_p common = find_common_loop (l1, l2);
331
332  return sese_loop_depth (region, common);
333}
334
335/* Return true when DEF can be analyzed in REGION by the scalar
336   evolution analyzer.  */
337
338static inline bool
339scev_analyzable_p (tree def, sese region)
340{
341  loop_p loop;
342  tree scev;
343  tree type = TREE_TYPE (def);
344
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;
354
355  loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
356  scev = scalar_evolution_in_region (region, loop, def);
357
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));
363}
364
365#endif
366