1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008-2016 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)
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/>. */
25 typedef hash_map<tree, tree> parameter_rename_map_t;
26 typedef hash_map<basic_block, vec<basic_block> > bb_map_t;
27 typedef hash_map<tree, vec<tree> > rename_map_t;
28 typedef struct ifsese_s *ifsese;
29 /* First phi is the new codegenerated phi second one is original phi. */
30 typedef std::pair <gphi *, gphi *> phi_rename;
31 /* First edge is the init edge and second is the back edge w.r.t. a loop. */
32 typedef std::pair<edge, edge> init_back_edge_pair_t;
34 /* A Single Entry, Single Exit region is a part of the CFG delimited
38 sese_l (edge e, edge x) : entry (e), exit (x) {}
40 operator bool () const { return entry && exit; }
46 void print_edge (FILE *file, const_edge e);
47 void print_sese (FILE *file, const sese_l &s);
48 void dump_edge (const_edge e);
49 void dump_sese (const sese_l &);
51 /* Get the entry of an sese S. */
53 static inline basic_block
54 get_entry_bb (sese_l &s)
59 /* Get the exit of an sese S. */
61 static inline basic_block
62 get_exit_bb (sese_l &s)
67 /* Returns the index of V where ELEM can be found. -1 Otherwise. */
70 vec_find (const vec<T> &v, const T &elem)
74 FOR_EACH_VEC_ELT (v, i, t)
80 /* A helper structure for bookkeeping information about a scop in graphite. */
81 typedef struct sese_info_t
83 /* The SESE region. */
86 /* Parameters used within the SCOP. */
89 /* Maps an old name to one or more new names. When there are several new
90 names, one has to select the definition corresponding to the immediate
92 rename_map_t *rename_map;
94 /* Parameters to be renamed. */
95 parameter_rename_map_t *parameter_rename_map;
97 /* Loops completely contained in this SESE. */
98 vec<loop_p> loop_nest;
100 /* Basic blocks contained in this SESE. */
101 vec<basic_block> bbs;
103 /* Copied basic blocks indexed by the original bb. */
104 bb_map_t *copied_bb_map;
106 /* A vector of phi nodes to be updated when all arguments are available. The
107 pair contains first the old_phi and second the new_phi. */
108 vec<phi_rename> incomplete_phis;
110 /* The condition region generated for this sese. */
115 extern sese_info_p new_sese_info (edge, edge);
116 extern void free_sese_info (sese_info_p);
117 extern void sese_insert_phis_for_liveouts (sese_info_p, basic_block, edge, edge);
118 extern struct loop *outermost_loop_in_sese (sese_l &, basic_block);
119 extern tree scalar_evolution_in_region (const sese_l &, loop_p, tree);
120 extern bool scev_analyzable_p (tree, sese_l &);
121 extern bool invariant_in_sese_p_rec (tree, const sese_l &, bool *);
123 /* The number of parameters in REGION. */
125 static inline unsigned
126 sese_nb_params (sese_info_p region)
128 return region->params.length ();
131 /* Checks whether BB is contained in the region delimited by ENTRY and
135 bb_in_region (const_basic_block bb, const_basic_block entry, const_basic_block exit)
137 /* FIXME: PR67842. */
144 /* Check that there are no edges coming in the region: all the
145 predecessors of EXIT are dominated by ENTRY. */
146 FOR_EACH_EDGE (e, ei, exit->preds)
147 gcc_assert (dominated_by_p (CDI_DOMINATORS, e->src, entry));
151 return dominated_by_p (CDI_DOMINATORS, bb, entry)
152 && !(dominated_by_p (CDI_DOMINATORS, bb, exit)
153 && !dominated_by_p (CDI_DOMINATORS, entry, exit));
156 /* Checks whether BB is contained in the region delimited by ENTRY and
160 bb_in_sese_p (basic_block bb, const sese_l &r)
162 return bb_in_region (bb, r.entry->dest, r.exit->dest);
165 /* Returns true when STMT is defined in REGION. */
168 stmt_in_sese_p (gimple *stmt, const sese_l &r)
170 basic_block bb = gimple_bb (stmt);
171 return bb && bb_in_sese_p (bb, r);
174 /* Returns true when NAME is defined in REGION. */
177 defined_in_sese_p (tree name, const sese_l &r)
179 return stmt_in_sese_p (SSA_NAME_DEF_STMT (name), r);
182 /* Returns true when LOOP is in REGION. */
185 loop_in_sese_p (struct loop *loop, const sese_l ®ion)
187 return (bb_in_sese_p (loop->header, region)
188 && bb_in_sese_p (loop->latch, region));
191 /* Returns the loop depth of LOOP in REGION. The loop depth
192 is the same as the normal loop depth, but limited by a region.
210 loop_0 does not exist in the region -> invalid
211 loop_1 exists, but is not completely contained in the region -> depth 0
212 loop_2 is completely contained -> depth 1 */
214 static inline unsigned int
215 sese_loop_depth (const sese_l ®ion, loop_p loop)
217 unsigned int depth = 0;
219 while (loop_in_sese_p (loop, region))
222 loop = loop_outer (loop);
228 /* A single entry single exit specialized for conditions. */
230 typedef struct ifsese_s {
232 sese_info_p true_region;
233 sese_info_p false_region;
236 extern void if_region_set_false_region (ifsese, sese_info_p);
237 extern ifsese move_sese_in_condition (sese_info_p);
238 extern void set_ifsese_condition (ifsese, tree);
239 extern edge get_true_edge_from_guard_bb (basic_block);
240 extern edge get_false_edge_from_guard_bb (basic_block);
243 if_region_entry (ifsese if_region)
245 return if_region->region->region.entry;
249 if_region_exit (ifsese if_region)
251 return if_region->region->region.exit;
254 static inline basic_block
255 if_region_get_condition_block (ifsese if_region)
257 return if_region_entry (if_region)->dest;
260 /* Free and compute again all the dominators information. */
263 recompute_all_dominators (void)
265 mark_irreducible_loops ();
266 free_dominance_info (CDI_DOMINATORS);
267 calculate_dominance_info (CDI_DOMINATORS);
269 free_dominance_info (CDI_POST_DOMINATORS);
270 calculate_dominance_info (CDI_POST_DOMINATORS);
273 typedef std::pair <gimple *, tree> scalar_use;
275 typedef struct gimple_poly_bb
280 /* Lists containing the restrictions of the conditional statements
281 dominating this bb. This bb can only be executed, if all conditions
286 for (i = 0; i <= 20; i++)
294 So for B there is an additional condition (2i <= 8).
296 List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the
297 corresponding element in CONDITION_CASES is not NULL_TREE. For a
298 SWITCH_EXPR the corresponding element in CONDITION_CASES is a
300 vec<gimple *> conditions;
301 vec<gimple *> condition_cases;
302 vec<data_reference_p> data_refs;
303 vec<scalar_use> read_scalar_refs;
304 vec<tree> write_scalar_refs;
307 #define GBB_BB(GBB) (GBB)->bb
308 #define GBB_PBB(GBB) (GBB)->pbb
309 #define GBB_DATA_REFS(GBB) (GBB)->data_refs
310 #define GBB_CONDITIONS(GBB) (GBB)->conditions
311 #define GBB_CONDITION_CASES(GBB) (GBB)->condition_cases
313 /* Return the innermost loop that contains the basic block GBB. */
315 static inline struct loop *
316 gbb_loop (gimple_poly_bb_p gbb)
318 return GBB_BB (gbb)->loop_father;
321 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
322 If there is no corresponding gimple loop, we return NULL. */
325 gbb_loop_at_index (gimple_poly_bb_p gbb, sese_l ®ion, int index)
327 loop_p loop = gbb_loop (gbb);
328 int depth = sese_loop_depth (region, loop);
330 while (--depth > index)
331 loop = loop_outer (loop);
333 gcc_assert (loop_in_sese_p (loop, region));
338 /* The number of common loops in REGION for GBB1 and GBB2. */
341 nb_common_loops (sese_l ®ion, gimple_poly_bb_p gbb1, gimple_poly_bb_p gbb2)
343 loop_p l1 = gbb_loop (gbb1);
344 loop_p l2 = gbb_loop (gbb2);
345 loop_p common = find_common_loop (l1, l2);
347 return sese_loop_depth (region, common);