1 /* Single entry single exit control flow regions. 2 Copyright (C) 2008, 2009, 2010 3 Free Software Foundation, Inc. 4 Contributed by Jan Sjodin <jan.sjodin@amd.com> and 5 Sebastian Pop <sebastian.pop@amd.com>. 6 7 This file is part of GCC. 8 9 GCC is free software; you can redistribute it and/or modify 10 it under the terms of the GNU General Public License as published by 11 the Free Software Foundation; either version 3, or (at your option) 12 any later version. 13 14 GCC is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU General Public License for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with GCC; see the file COPYING3. If not see 21 <http://www.gnu.org/licenses/>. */ 22 23 #ifndef GCC_SESE_H 24 #define GCC_SESE_H 25 26 /* A Single Entry, Single Exit region is a part of the CFG delimited 27 by two edges. */ 28 typedef struct sese_s 29 { 30 /* Single ENTRY and single EXIT from the SESE region. */ 31 edge entry, exit; 32 33 /* Parameters used within the SCOP. */ 34 VEC (tree, heap) *params; 35 36 /* Loops completely contained in the SCOP. */ 37 bitmap loops; 38 VEC (loop_p, heap) *loop_nest; 39 40 /* Are we allowed to add more params? This is for debugging purpose. We 41 can only add new params before generating the bb domains, otherwise they 42 become invalid. */ 43 bool add_params; 44 } *sese; 45 46 #define SESE_ENTRY(S) (S->entry) 47 #define SESE_ENTRY_BB(S) (S->entry->dest) 48 #define SESE_EXIT(S) (S->exit) 49 #define SESE_EXIT_BB(S) (S->exit->dest) 50 #define SESE_PARAMS(S) (S->params) 51 #define SESE_LOOPS(S) (S->loops) 52 #define SESE_LOOP_NEST(S) (S->loop_nest) 53 #define SESE_ADD_PARAMS(S) (S->add_params) 54 55 extern sese new_sese (edge, edge); 56 extern void free_sese (sese); 57 extern void sese_insert_phis_for_liveouts (sese, basic_block, edge, edge); 58 extern void build_sese_loop_nests (sese); 59 extern edge copy_bb_and_scalar_dependences (basic_block, sese, edge, 60 VEC (tree, heap) *, bool *); 61 extern struct loop *outermost_loop_in_sese (sese, basic_block); 62 extern void insert_loop_close_phis (htab_t, loop_p); 63 extern void insert_guard_phis (basic_block, edge, edge, htab_t, htab_t); 64 extern tree scalar_evolution_in_region (sese, loop_p, tree); 65 66 /* Check that SESE contains LOOP. */ 67 68 static inline bool 69 sese_contains_loop (sese sese, struct loop *loop) 70 { 71 return bitmap_bit_p (SESE_LOOPS (sese), loop->num); 72 } 73 74 /* The number of parameters in REGION. */ 75 76 static inline unsigned 77 sese_nb_params (sese region) 78 { 79 return VEC_length (tree, SESE_PARAMS (region)); 80 } 81 82 /* Checks whether BB is contained in the region delimited by ENTRY and 83 EXIT blocks. */ 84 85 static inline bool 86 bb_in_region (basic_block bb, basic_block entry, basic_block exit) 87 { 88 #ifdef ENABLE_CHECKING 89 { 90 edge e; 91 edge_iterator ei; 92 93 /* Check that there are no edges coming in the region: all the 94 predecessors of EXIT are dominated by ENTRY. */ 95 FOR_EACH_EDGE (e, ei, exit->preds) 96 dominated_by_p (CDI_DOMINATORS, e->src, entry); 97 } 98 #endif 99 100 return dominated_by_p (CDI_DOMINATORS, bb, entry) 101 && !(dominated_by_p (CDI_DOMINATORS, bb, exit) 102 && !dominated_by_p (CDI_DOMINATORS, entry, exit)); 103 } 104 105 /* Checks whether BB is contained in the region delimited by ENTRY and 106 EXIT blocks. */ 107 108 static inline bool 109 bb_in_sese_p (basic_block bb, sese region) 110 { 111 basic_block entry = SESE_ENTRY_BB (region); 112 basic_block exit = SESE_EXIT_BB (region); 113 114 return bb_in_region (bb, entry, exit); 115 } 116 117 /* Returns true when STMT is defined in REGION. */ 118 119 static inline bool 120 stmt_in_sese_p (gimple stmt, sese region) 121 { 122 basic_block bb = gimple_bb (stmt); 123 return bb && bb_in_sese_p (bb, region); 124 } 125 126 /* Returns true when NAME is defined in REGION. */ 127 128 static inline bool 129 defined_in_sese_p (tree name, sese region) 130 { 131 gimple stmt = SSA_NAME_DEF_STMT (name); 132 return stmt_in_sese_p (stmt, region); 133 } 134 135 /* Returns true when LOOP is in REGION. */ 136 137 static inline bool 138 loop_in_sese_p (struct loop *loop, sese region) 139 { 140 return (bb_in_sese_p (loop->header, region) 141 && bb_in_sese_p (loop->latch, region)); 142 } 143 144 /* Returns the loop depth of LOOP in REGION. The loop depth 145 is the same as the normal loop depth, but limited by a region. 146 147 Example: 148 149 loop_0 150 loop_1 151 { 152 S0 153 <- region start 154 S1 155 156 loop_2 157 S2 158 159 S3 160 <- region end 161 } 162 163 loop_0 does not exist in the region -> invalid 164 loop_1 exists, but is not completely contained in the region -> depth 0 165 loop_2 is completely contained -> depth 1 */ 166 167 static inline unsigned int 168 sese_loop_depth (sese region, loop_p loop) 169 { 170 unsigned int depth = 0; 171 172 gcc_assert ((!loop_in_sese_p (loop, region) 173 && (SESE_ENTRY_BB (region)->loop_father == loop 174 || SESE_EXIT (region)->src->loop_father == loop)) 175 || loop_in_sese_p (loop, region)); 176 177 while (loop_in_sese_p (loop, region)) 178 { 179 depth++; 180 loop = loop_outer (loop); 181 } 182 183 return depth; 184 } 185 186 /* Splits BB to make a single entry single exit region. */ 187 188 static inline sese 189 split_region_for_bb (basic_block bb) 190 { 191 edge entry, exit; 192 193 if (single_pred_p (bb)) 194 entry = single_pred_edge (bb); 195 else 196 { 197 entry = split_block_after_labels (bb); 198 bb = single_succ (bb); 199 } 200 201 if (single_succ_p (bb)) 202 exit = single_succ_edge (bb); 203 else 204 { 205 gimple_stmt_iterator gsi = gsi_last_bb (bb); 206 gsi_prev (&gsi); 207 exit = split_block (bb, gsi_stmt (gsi)); 208 } 209 210 return new_sese (entry, exit); 211 } 212 213 /* Returns the block preceding the entry of a SESE. */ 214 215 static inline basic_block 216 block_before_sese (sese sese) 217 { 218 return SESE_ENTRY (sese)->src; 219 } 220 221 222 223 /* A single entry single exit specialized for conditions. */ 224 225 typedef struct ifsese_s { 226 sese region; 227 sese true_region; 228 sese false_region; 229 } *ifsese; 230 231 extern void if_region_set_false_region (ifsese, sese); 232 extern ifsese move_sese_in_condition (sese); 233 extern edge get_true_edge_from_guard_bb (basic_block); 234 extern edge get_false_edge_from_guard_bb (basic_block); 235 extern void set_ifsese_condition (ifsese, tree); 236 237 static inline edge 238 if_region_entry (ifsese if_region) 239 { 240 return SESE_ENTRY (if_region->region); 241 } 242 243 static inline edge 244 if_region_exit (ifsese if_region) 245 { 246 return SESE_EXIT (if_region->region); 247 } 248 249 static inline basic_block 250 if_region_get_condition_block (ifsese if_region) 251 { 252 return if_region_entry (if_region)->dest; 253 } 254 255 /* Structure containing the mapping between the old names and the new 256 names used after block copy in the new loop context. */ 257 typedef struct rename_map_elt_s 258 { 259 tree old_name, expr; 260 } *rename_map_elt; 261 262 DEF_VEC_P(rename_map_elt); 263 DEF_VEC_ALLOC_P (rename_map_elt, heap); 264 265 extern void debug_rename_map (htab_t); 266 extern hashval_t rename_map_elt_info (const void *); 267 extern int eq_rename_map_elts (const void *, const void *); 268 269 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */ 270 271 static inline rename_map_elt 272 new_rename_map_elt (tree old_name, tree expr) 273 { 274 rename_map_elt res; 275 276 res = XNEW (struct rename_map_elt_s); 277 res->old_name = old_name; 278 res->expr = expr; 279 280 return res; 281 } 282 283 /* Structure containing the mapping between the CLooG's induction 284 variable and the type of the old induction variable. */ 285 typedef struct ivtype_map_elt_s 286 { 287 tree type; 288 const char *cloog_iv; 289 } *ivtype_map_elt; 290 291 extern void debug_ivtype_map (htab_t); 292 extern hashval_t ivtype_map_elt_info (const void *); 293 extern int eq_ivtype_map_elts (const void *, const void *); 294 295 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */ 296 297 static inline ivtype_map_elt 298 new_ivtype_map_elt (const char *cloog_iv, tree type) 299 { 300 ivtype_map_elt res; 301 302 res = XNEW (struct ivtype_map_elt_s); 303 res->cloog_iv = cloog_iv; 304 res->type = type; 305 306 return res; 307 } 308 309 /* Free and compute again all the dominators information. */ 310 311 static inline void 312 recompute_all_dominators (void) 313 { 314 mark_irreducible_loops (); 315 free_dominance_info (CDI_DOMINATORS); 316 calculate_dominance_info (CDI_DOMINATORS); 317 } 318 319 typedef struct gimple_bb 320 { 321 basic_block bb; 322 struct poly_bb *pbb; 323 324 /* Lists containing the restrictions of the conditional statements 325 dominating this bb. This bb can only be executed, if all conditions 326 are true. 327 328 Example: 329 330 for (i = 0; i <= 20; i++) 331 { 332 A 333 334 if (2i <= 8) 335 B 336 } 337 338 So for B there is an additional condition (2i <= 8). 339 340 List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the 341 corresponding element in CONDITION_CASES is not NULL_TREE. For a 342 SWITCH_EXPR the corresponding element in CONDITION_CASES is a 343 CASE_LABEL_EXPR. */ 344 VEC (gimple, heap) *conditions; 345 VEC (gimple, heap) *condition_cases; 346 VEC (data_reference_p, heap) *data_refs; 347 } *gimple_bb_p; 348 349 #define GBB_BB(GBB) (GBB)->bb 350 #define GBB_PBB(GBB) (GBB)->pbb 351 #define GBB_DATA_REFS(GBB) (GBB)->data_refs 352 #define GBB_CONDITIONS(GBB) (GBB)->conditions 353 #define GBB_CONDITION_CASES(GBB) (GBB)->condition_cases 354 355 /* Return the innermost loop that contains the basic block GBB. */ 356 357 static inline struct loop * 358 gbb_loop (struct gimple_bb *gbb) 359 { 360 return GBB_BB (gbb)->loop_father; 361 } 362 363 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX. 364 If there is no corresponding gimple loop, we return NULL. */ 365 366 static inline loop_p 367 gbb_loop_at_index (gimple_bb_p gbb, sese region, int index) 368 { 369 loop_p loop = gbb_loop (gbb); 370 int depth = sese_loop_depth (region, loop); 371 372 while (--depth > index) 373 loop = loop_outer (loop); 374 375 gcc_assert (sese_contains_loop (region, loop)); 376 377 return loop; 378 } 379 380 /* The number of common loops in REGION for GBB1 and GBB2. */ 381 382 static inline int 383 nb_common_loops (sese region, gimple_bb_p gbb1, gimple_bb_p gbb2) 384 { 385 loop_p l1 = gbb_loop (gbb1); 386 loop_p l2 = gbb_loop (gbb2); 387 loop_p common = find_common_loop (l1, l2); 388 389 return sese_loop_depth (region, common); 390 } 391 392 /* Return true when DEF can be analyzed in REGION by the scalar 393 evolution analyzer. */ 394 395 static inline bool 396 scev_analyzable_p (tree def, sese region) 397 { 398 loop_p loop; 399 tree scev; 400 tree type = TREE_TYPE (def); 401 402 /* When Graphite generates code for a scev, the code generator 403 expresses the scev in function of a single induction variable. 404 This is unsafe for floating point computations, as it may replace 405 a floating point sum reduction with a multiplication. The 406 following test returns false for non integer types to avoid such 407 problems. */ 408 if (!INTEGRAL_TYPE_P (type) 409 && !POINTER_TYPE_P (type)) 410 return false; 411 412 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def)); 413 scev = scalar_evolution_in_region (region, loop, def); 414 415 return !chrec_contains_undetermined (scev) 416 && (TREE_CODE (scev) != SSA_NAME 417 || !defined_in_sese_p (scev, region)) 418 && (tree_does_not_contain_chrecs (scev) 419 || evolution_function_is_affine_p (scev)); 420 } 421 422 #endif 423