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>. 5 6 This file is part of GCC. 7 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. 12 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. 17 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/>. */ 21 22 #ifndef GCC_SESE_H 23 #define GCC_SESE_H 24 25 typedef struct ifsese_s *ifsese; 26 27 /* A Single Entry, Single Exit region is a part of the CFG delimited 28 by two edges. */ 29 struct sese_l 30 { 31 sese_l (edge e, edge x) : entry (e), exit (x) {} 32 33 operator bool () const { return entry && exit; } 34 35 edge entry; 36 edge exit; 37 }; 38 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 &); 43 44 /* Get the entry of an sese S. */ 45 46 static inline basic_block 47 get_entry_bb (sese_l &s) 48 { 49 return s.entry->dest; 50 } 51 52 /* Get the exit of an sese S. */ 53 54 static inline basic_block 55 get_exit_bb (sese_l &s) 56 { 57 return s.exit->src; 58 } 59 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) 64 { 65 int i; 66 T t; 67 FOR_EACH_VEC_ELT (v, i, t) 68 if (elem == t) 69 return i; 70 return -1; 71 } 72 73 /* A helper structure for bookkeeping information about a scop in graphite. */ 74 typedef struct sese_info_t 75 { 76 /* The SESE region. */ 77 sese_l region; 78 79 /* Liveout vars. */ 80 bitmap liveout; 81 82 /* Liveout in debug stmts. */ 83 bitmap debug_liveout; 84 85 /* Parameters used within the SCOP. */ 86 vec<tree> params; 87 88 /* Maps an old name to a new decl. */ 89 hash_map<tree, tree> *rename_map; 90 91 /* Basic blocks contained in this SESE. */ 92 vec<basic_block> bbs; 93 94 /* The condition region generated for this sese. */ 95 ifsese if_region; 96 97 } *sese_info_p; 98 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); 108 109 /* The number of parameters in REGION. */ 110 111 static inline unsigned 112 sese_nb_params (sese_info_p region) 113 { 114 return region->params.length (); 115 } 116 117 /* Checks whether BB is contained in the region delimited by ENTRY and 118 EXIT blocks. */ 119 120 static inline bool 121 bb_in_region (const_basic_block bb, const_basic_block entry, const_basic_block exit) 122 { 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)); 126 } 127 128 /* Checks whether BB is contained in the region delimited by ENTRY and 129 EXIT blocks. */ 130 131 static inline bool 132 bb_in_sese_p (basic_block bb, const sese_l &r) 133 { 134 return bb_in_region (bb, r.entry->dest, r.exit->dest); 135 } 136 137 /* Returns true when STMT is defined in REGION. */ 138 139 static inline bool 140 stmt_in_sese_p (gimple *stmt, const sese_l &r) 141 { 142 basic_block bb = gimple_bb (stmt); 143 return bb && bb_in_sese_p (bb, r); 144 } 145 146 /* Returns true when NAME is defined in REGION. */ 147 148 static inline bool 149 defined_in_sese_p (tree name, const sese_l &r) 150 { 151 return stmt_in_sese_p (SSA_NAME_DEF_STMT (name), r); 152 } 153 154 /* Returns true when LOOP is in REGION. */ 155 156 static inline bool 157 loop_in_sese_p (struct loop *loop, const sese_l ®ion) 158 { 159 return (bb_in_sese_p (loop->header, region) 160 && bb_in_sese_p (loop->latch, region)); 161 } 162 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. 165 166 Example: 167 168 loop_0 169 loop_1 170 { 171 S0 172 <- region start 173 S1 174 175 loop_2 176 S2 177 178 S3 179 <- region end 180 } 181 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 */ 185 186 static inline unsigned int 187 sese_loop_depth (const sese_l ®ion, loop_p loop) 188 { 189 unsigned int depth = 0; 190 191 while (loop_in_sese_p (loop, region)) 192 { 193 depth++; 194 loop = loop_outer (loop); 195 } 196 197 return depth; 198 } 199 200 /* A single entry single exit specialized for conditions. */ 201 202 typedef struct ifsese_s { 203 sese_info_p region; 204 sese_info_p true_region; 205 sese_info_p false_region; 206 } *ifsese; 207 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); 212 213 static inline edge 214 if_region_entry (ifsese if_region) 215 { 216 return if_region->region->region.entry; 217 } 218 219 static inline edge 220 if_region_exit (ifsese if_region) 221 { 222 return if_region->region->region.exit; 223 } 224 225 static inline basic_block 226 if_region_get_condition_block (ifsese if_region) 227 { 228 return if_region_entry (if_region)->dest; 229 } 230 231 typedef std::pair <gimple *, tree> scalar_use; 232 233 typedef struct gimple_poly_bb 234 { 235 basic_block bb; 236 struct poly_bb *pbb; 237 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. 241 242 Example: 243 244 for (i = 0; i <= 20; i++) 245 { 246 A 247 248 if (2i <= 8) 249 B 250 } 251 252 So for B there is an additional condition (2i <= 8). 253 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; 264 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 270 271 /* Return the innermost loop that contains the basic block GBB. */ 272 273 static inline struct loop * 274 gbb_loop (gimple_poly_bb_p gbb) 275 { 276 return GBB_BB (gbb)->loop_father; 277 } 278 279 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX. 280 If there is no corresponding gimple loop, we return NULL. */ 281 282 static inline loop_p 283 gbb_loop_at_index (gimple_poly_bb_p gbb, sese_l ®ion, int index) 284 { 285 loop_p loop = gbb_loop (gbb); 286 int depth = sese_loop_depth (region, loop); 287 288 while (--depth > index) 289 loop = loop_outer (loop); 290 291 gcc_assert (loop_in_sese_p (loop, region)); 292 293 return loop; 294 } 295 296 /* The number of common loops in REGION for GBB1 and GBB2. */ 297 298 static inline int 299 nb_common_loops (sese_l ®ion, gimple_poly_bb_p gbb1, gimple_poly_bb_p gbb2) 300 { 301 loop_p l1 = gbb_loop (gbb1); 302 loop_p l2 = gbb_loop (gbb2); 303 loop_p common = find_common_loop (l1, l2); 304 305 return sese_loop_depth (region, common); 306 } 307 308 #endif 309