1/* Single entry single exit control flow regions. 2 Copyright (C) 2008-2020 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 25typedef struct ifsese_s *ifsese; 26 27/* A Single Entry, Single Exit region is a part of the CFG delimited 28 by two edges. */ 29class sese_l 30{ 31public: 32 sese_l (edge e, edge x) : entry (e), exit (x) {} 33 34 operator bool () const { return entry && exit; } 35 36 edge entry; 37 edge exit; 38}; 39 40void print_edge (FILE *file, const_edge e); 41void print_sese (FILE *file, const sese_l &s); 42void dump_edge (const_edge e); 43void dump_sese (const sese_l &); 44 45/* Get the entry of an sese S. */ 46 47static inline basic_block 48get_entry_bb (sese_l &s) 49{ 50 return s.entry->dest; 51} 52 53/* Get the exit of an sese S. */ 54 55static inline basic_block 56get_exit_bb (sese_l &s) 57{ 58 return s.exit->src; 59} 60 61/* Returns the index of V where ELEM can be found. -1 Otherwise. */ 62template<typename T> 63int 64vec_find (const vec<T> &v, const T &elem) 65{ 66 int i; 67 T t; 68 FOR_EACH_VEC_ELT (v, i, t) 69 if (elem == t) 70 return i; 71 return -1; 72} 73 74/* A helper structure for bookkeeping information about a scop in graphite. */ 75typedef class sese_info_t 76{ 77public: 78 /* The SESE region. */ 79 sese_l region; 80 81 /* Liveout vars. */ 82 bitmap liveout; 83 84 /* Liveout in debug stmts. */ 85 bitmap debug_liveout; 86 87 /* Parameters used within the SCOP. */ 88 vec<tree> params; 89 90 /* Maps an old name to a new decl. */ 91 hash_map<tree, tree> *rename_map; 92 93 /* Basic blocks contained in this SESE. */ 94 vec<basic_block> bbs; 95 96 /* The condition region generated for this sese. */ 97 ifsese if_region; 98 99} *sese_info_p; 100 101extern sese_info_p new_sese_info (edge, edge); 102extern void free_sese_info (sese_info_p); 103extern void sese_insert_phis_for_liveouts (sese_info_p, basic_block, edge, edge); 104extern class loop *outermost_loop_in_sese (sese_l &, basic_block); 105extern tree scalar_evolution_in_region (const sese_l &, loop_p, tree); 106extern bool scev_analyzable_p (tree, sese_l &); 107extern bool invariant_in_sese_p_rec (tree, const sese_l &, bool *); 108extern void sese_build_liveouts (sese_info_p); 109extern bool sese_trivially_empty_bb_p (basic_block); 110 111/* The number of parameters in REGION. */ 112 113static inline unsigned 114sese_nb_params (sese_info_p region) 115{ 116 return region->params.length (); 117} 118 119/* Checks whether BB is contained in the region delimited by ENTRY and 120 EXIT blocks. */ 121 122static inline bool 123bb_in_region (const_basic_block bb, const_basic_block entry, const_basic_block exit) 124{ 125 return dominated_by_p (CDI_DOMINATORS, bb, entry) 126 && !(dominated_by_p (CDI_DOMINATORS, bb, exit) 127 && !dominated_by_p (CDI_DOMINATORS, entry, exit)); 128} 129 130/* Checks whether BB is contained in the region delimited by ENTRY and 131 EXIT blocks. */ 132 133static inline bool 134bb_in_sese_p (basic_block bb, const sese_l &r) 135{ 136 return bb_in_region (bb, r.entry->dest, r.exit->dest); 137} 138 139/* Returns true when STMT is defined in REGION. */ 140 141static inline bool 142stmt_in_sese_p (gimple *stmt, const sese_l &r) 143{ 144 basic_block bb = gimple_bb (stmt); 145 return bb && bb_in_sese_p (bb, r); 146} 147 148/* Returns true when NAME is defined in REGION. */ 149 150static inline bool 151defined_in_sese_p (tree name, const sese_l &r) 152{ 153 return stmt_in_sese_p (SSA_NAME_DEF_STMT (name), r); 154} 155 156/* Returns true when LOOP is in REGION. */ 157 158static inline bool 159loop_in_sese_p (class loop *loop, const sese_l ®ion) 160{ 161 return (bb_in_sese_p (loop->header, region) 162 && bb_in_sese_p (loop->latch, region)); 163} 164 165/* Returns the loop depth of LOOP in REGION. The loop depth 166 is the same as the normal loop depth, but limited by a region. 167 168 Example: 169 170 loop_0 171 loop_1 172 { 173 S0 174 <- region start 175 S1 176 177 loop_2 178 S2 179 180 S3 181 <- region end 182 } 183 184 loop_0 does not exist in the region -> invalid 185 loop_1 exists, but is not completely contained in the region -> depth 0 186 loop_2 is completely contained -> depth 1 */ 187 188static inline unsigned int 189sese_loop_depth (const sese_l ®ion, loop_p loop) 190{ 191 unsigned int depth = 0; 192 193 while (loop_in_sese_p (loop, region)) 194 { 195 depth++; 196 loop = loop_outer (loop); 197 } 198 199 return depth; 200} 201 202/* A single entry single exit specialized for conditions. */ 203 204typedef struct ifsese_s { 205 sese_info_p region; 206 sese_info_p true_region; 207 sese_info_p false_region; 208} *ifsese; 209 210extern ifsese move_sese_in_condition (sese_info_p); 211extern void set_ifsese_condition (ifsese, tree); 212extern edge get_true_edge_from_guard_bb (basic_block); 213extern edge get_false_edge_from_guard_bb (basic_block); 214 215static inline edge 216if_region_entry (ifsese if_region) 217{ 218 return if_region->region->region.entry; 219} 220 221static inline edge 222if_region_exit (ifsese if_region) 223{ 224 return if_region->region->region.exit; 225} 226 227static inline basic_block 228if_region_get_condition_block (ifsese if_region) 229{ 230 return if_region_entry (if_region)->dest; 231} 232 233typedef std::pair <gimple *, tree> scalar_use; 234 235typedef struct gimple_poly_bb 236{ 237 basic_block bb; 238 struct poly_bb *pbb; 239 240 /* Lists containing the restrictions of the conditional statements 241 dominating this bb. This bb can only be executed, if all conditions 242 are true. 243 244 Example: 245 246 for (i = 0; i <= 20; i++) 247 { 248 A 249 250 if (2i <= 8) 251 B 252 } 253 254 So for B there is an additional condition (2i <= 8). 255 256 List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the 257 corresponding element in CONDITION_CASES is not NULL_TREE. For a 258 SWITCH_EXPR the corresponding element in CONDITION_CASES is a 259 CASE_LABEL_EXPR. */ 260 vec<gimple *> conditions; 261 vec<gimple *> condition_cases; 262 vec<data_reference_p> data_refs; 263 vec<scalar_use> read_scalar_refs; 264 vec<tree> write_scalar_refs; 265} *gimple_poly_bb_p; 266 267#define GBB_BB(GBB) (GBB)->bb 268#define GBB_PBB(GBB) (GBB)->pbb 269#define GBB_DATA_REFS(GBB) (GBB)->data_refs 270#define GBB_CONDITIONS(GBB) (GBB)->conditions 271#define GBB_CONDITION_CASES(GBB) (GBB)->condition_cases 272 273/* Return the innermost loop that contains the basic block GBB. */ 274 275static inline class loop * 276gbb_loop (gimple_poly_bb_p gbb) 277{ 278 return GBB_BB (gbb)->loop_father; 279} 280 281/* Returns the gimple loop, that corresponds to the loop_iterator_INDEX. 282 If there is no corresponding gimple loop, we return NULL. */ 283 284static inline loop_p 285gbb_loop_at_index (gimple_poly_bb_p gbb, sese_l ®ion, int index) 286{ 287 loop_p loop = gbb_loop (gbb); 288 int depth = sese_loop_depth (region, loop); 289 290 while (--depth > index) 291 loop = loop_outer (loop); 292 293 gcc_assert (loop_in_sese_p (loop, region)); 294 295 return loop; 296} 297 298/* The number of common loops in REGION for GBB1 and GBB2. */ 299 300static inline int 301nb_common_loops (sese_l ®ion, gimple_poly_bb_p gbb1, gimple_poly_bb_p gbb2) 302{ 303 loop_p l1 = gbb_loop (gbb1); 304 loop_p l2 = gbb_loop (gbb2); 305 loop_p common = find_common_loop (l1, l2); 306 307 return sese_loop_depth (region, common); 308} 309 310#endif 311