/cp
[official-gcc.git] / gcc / sese.h
blobd0f03e8d1b5c1208f47fc2e316fdfc5782c0d53a
1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008-2018 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 typedef struct ifsese_s *ifsese;
27 /* A Single Entry, Single Exit region is a part of the CFG delimited
28 by two edges. */
29 struct sese_l
31 sese_l (edge e, edge x) : entry (e), exit (x) {}
33 operator bool () const { return entry && exit; }
35 edge entry;
36 edge exit;
39 void print_edge (FILE *file, const_edge e);
40 void print_sese (FILE *file, const sese_l &s);
41 void dump_edge (const_edge e);
42 void dump_sese (const sese_l &);
44 /* Get the entry of an sese S. */
46 static inline basic_block
47 get_entry_bb (sese_l &s)
49 return s.entry->dest;
52 /* Get the exit of an sese S. */
54 static inline basic_block
55 get_exit_bb (sese_l &s)
57 return s.exit->src;
60 /* Returns the index of V where ELEM can be found. -1 Otherwise. */
61 template<typename T>
62 int
63 vec_find (const vec<T> &v, const T &elem)
65 int i;
66 T t;
67 FOR_EACH_VEC_ELT (v, i, t)
68 if (elem == t)
69 return i;
70 return -1;
73 /* A helper structure for bookkeeping information about a scop in graphite. */
74 typedef struct sese_info_t
76 /* The SESE region. */
77 sese_l region;
79 /* Liveout vars. */
80 bitmap liveout;
82 /* Liveout in debug stmts. */
83 bitmap debug_liveout;
85 /* Parameters used within the SCOP. */
86 vec<tree> params;
88 /* Maps an old name to a new decl. */
89 hash_map<tree, tree> *rename_map;
91 /* Basic blocks contained in this SESE. */
92 vec<basic_block> bbs;
94 /* The condition region generated for this sese. */
95 ifsese if_region;
97 } *sese_info_p;
99 extern sese_info_p new_sese_info (edge, edge);
100 extern void free_sese_info (sese_info_p);
101 extern void sese_insert_phis_for_liveouts (sese_info_p, basic_block, edge, edge);
102 extern struct loop *outermost_loop_in_sese (sese_l &, basic_block);
103 extern tree scalar_evolution_in_region (const sese_l &, loop_p, tree);
104 extern bool scev_analyzable_p (tree, sese_l &);
105 extern bool invariant_in_sese_p_rec (tree, const sese_l &, bool *);
106 extern void sese_build_liveouts (sese_info_p);
107 extern bool sese_trivially_empty_bb_p (basic_block);
109 /* The number of parameters in REGION. */
111 static inline unsigned
112 sese_nb_params (sese_info_p region)
114 return region->params.length ();
117 /* Checks whether BB is contained in the region delimited by ENTRY and
118 EXIT blocks. */
120 static inline bool
121 bb_in_region (const_basic_block bb, const_basic_block entry, const_basic_block exit)
123 return dominated_by_p (CDI_DOMINATORS, bb, entry)
124 && !(dominated_by_p (CDI_DOMINATORS, bb, exit)
125 && !dominated_by_p (CDI_DOMINATORS, entry, exit));
128 /* Checks whether BB is contained in the region delimited by ENTRY and
129 EXIT blocks. */
131 static inline bool
132 bb_in_sese_p (basic_block bb, const sese_l &r)
134 return bb_in_region (bb, r.entry->dest, r.exit->dest);
137 /* Returns true when STMT is defined in REGION. */
139 static inline bool
140 stmt_in_sese_p (gimple *stmt, const sese_l &r)
142 basic_block bb = gimple_bb (stmt);
143 return bb && bb_in_sese_p (bb, r);
146 /* Returns true when NAME is defined in REGION. */
148 static inline bool
149 defined_in_sese_p (tree name, const sese_l &r)
151 return stmt_in_sese_p (SSA_NAME_DEF_STMT (name), r);
154 /* Returns true when LOOP is in REGION. */
156 static inline bool
157 loop_in_sese_p (struct loop *loop, const sese_l &region)
159 return (bb_in_sese_p (loop->header, region)
160 && bb_in_sese_p (loop->latch, region));
163 /* Returns the loop depth of LOOP in REGION. The loop depth
164 is the same as the normal loop depth, but limited by a region.
166 Example:
168 loop_0
169 loop_1
172 <- region start
175 loop_2
179 <- region end
182 loop_0 does not exist in the region -> invalid
183 loop_1 exists, but is not completely contained in the region -> depth 0
184 loop_2 is completely contained -> depth 1 */
186 static inline unsigned int
187 sese_loop_depth (const sese_l &region, loop_p loop)
189 unsigned int depth = 0;
191 while (loop_in_sese_p (loop, region))
193 depth++;
194 loop = loop_outer (loop);
197 return depth;
200 /* A single entry single exit specialized for conditions. */
202 typedef struct ifsese_s {
203 sese_info_p region;
204 sese_info_p true_region;
205 sese_info_p false_region;
206 } *ifsese;
208 extern ifsese move_sese_in_condition (sese_info_p);
209 extern void set_ifsese_condition (ifsese, tree);
210 extern edge get_true_edge_from_guard_bb (basic_block);
211 extern edge get_false_edge_from_guard_bb (basic_block);
213 static inline edge
214 if_region_entry (ifsese if_region)
216 return if_region->region->region.entry;
219 static inline edge
220 if_region_exit (ifsese if_region)
222 return if_region->region->region.exit;
225 static inline basic_block
226 if_region_get_condition_block (ifsese if_region)
228 return if_region_entry (if_region)->dest;
231 typedef std::pair <gimple *, tree> scalar_use;
233 typedef struct gimple_poly_bb
235 basic_block bb;
236 struct poly_bb *pbb;
238 /* Lists containing the restrictions of the conditional statements
239 dominating this bb. This bb can only be executed, if all conditions
240 are true.
242 Example:
244 for (i = 0; i <= 20; i++)
248 if (2i <= 8)
252 So for B there is an additional condition (2i <= 8).
254 List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the
255 corresponding element in CONDITION_CASES is not NULL_TREE. For a
256 SWITCH_EXPR the corresponding element in CONDITION_CASES is a
257 CASE_LABEL_EXPR. */
258 vec<gimple *> conditions;
259 vec<gimple *> condition_cases;
260 vec<data_reference_p> data_refs;
261 vec<scalar_use> read_scalar_refs;
262 vec<tree> write_scalar_refs;
263 } *gimple_poly_bb_p;
265 #define GBB_BB(GBB) (GBB)->bb
266 #define GBB_PBB(GBB) (GBB)->pbb
267 #define GBB_DATA_REFS(GBB) (GBB)->data_refs
268 #define GBB_CONDITIONS(GBB) (GBB)->conditions
269 #define GBB_CONDITION_CASES(GBB) (GBB)->condition_cases
271 /* Return the innermost loop that contains the basic block GBB. */
273 static inline struct loop *
274 gbb_loop (gimple_poly_bb_p gbb)
276 return GBB_BB (gbb)->loop_father;
279 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
280 If there is no corresponding gimple loop, we return NULL. */
282 static inline loop_p
283 gbb_loop_at_index (gimple_poly_bb_p gbb, sese_l &region, int index)
285 loop_p loop = gbb_loop (gbb);
286 int depth = sese_loop_depth (region, loop);
288 while (--depth > index)
289 loop = loop_outer (loop);
291 gcc_assert (loop_in_sese_p (loop, region));
293 return loop;
296 /* The number of common loops in REGION for GBB1 and GBB2. */
298 static inline int
299 nb_common_loops (sese_l &region, gimple_poly_bb_p gbb1, gimple_poly_bb_p gbb2)
301 loop_p l1 = gbb_loop (gbb1);
302 loop_p l2 = gbb_loop (gbb2);
303 loop_p common = find_common_loop (l1, l2);
305 return sese_loop_depth (region, common);
308 #endif