gcc/sese.h

   1 /* Single entry single exit control flow regions.
   2    Copyright (C) 2008, 2009  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 /* A Single Entry, Single Exit region is a part of the CFG delimited
  26    by two edges.  */
  27 typedef struct sese_s
  28 {
  29   /* Single ENTRY and single EXIT from the SESE region.  */
  30   edge entry, exit;
  31
  32   /* Parameters used within the SCOP.  */
  33   VEC (tree, heap) *params;
  34
  35   /* Used to quickly retrieve the index of a parameter in PARAMS.  */
  36   htab_t params_index;
  37
  38   /* Store the names of the parameters that are passed to CLooG.  */
  39   char **params_names;
  40
  41   /* Loops completely contained in the SCOP.  */
  42   bitmap loops;
  43   VEC (loop_p, heap) *loop_nest;
  44
  45   /* Are we allowed to add more params?  This is for debugging purpose.  We
  46      can only add new params before generating the bb domains, otherwise they
  47      become invalid.  */
  48   bool add_params;
  49 } *sese;
  50
  51 #define SESE_ENTRY(S) (S->entry)
  52 #define SESE_ENTRY_BB(S) (S->entry->dest)
  53 #define SESE_EXIT(S) (S->exit)
  54 #define SESE_EXIT_BB(S) (S->exit->dest)
  55 #define SESE_PARAMS(S) (S->params)
  56 #define SESE_PARAMS_INDEX(S) (S->params_index)
  57 #define SESE_PARAMS_NAMES(S) (S->params_names)
  58 #define SESE_LOOPS(S) (S->loops)
  59 #define SESE_LOOP_NEST(S) (S->loop_nest)
  60 #define SESE_ADD_PARAMS(S) (S->add_params)
  61
  62 extern sese new_sese (edge, edge);
  63 extern void free_sese (sese);
  64 extern void sese_insert_phis_for_liveouts (sese, basic_block, edge, edge);
  65 extern void sese_adjust_liveout_phis (sese, htab_t, basic_block, edge, edge);
  66 extern void build_sese_loop_nests (sese);
  67 extern edge copy_bb_and_scalar_dependences (basic_block, sese, edge, htab_t);
  68 extern struct loop *outermost_loop_in_sese (sese, basic_block);
  69 extern void insert_loop_close_phis (htab_t, loop_p);
  70 extern void insert_guard_phis (basic_block, edge, edge, htab_t, htab_t);
  71 extern void sese_reset_aux_in_loops (sese);
  72 extern tree scalar_evolution_in_region (sese, loop_p, tree);
  73
  74 /* Check that SESE contains LOOP.  */
  75
  76 static inline bool
  77 sese_contains_loop (sese sese, struct loop *loop)
  78 {
  79   return bitmap_bit_p (SESE_LOOPS (sese), loop->num);
  80 }
  81
  82 /* The number of parameters in REGION. */
  83
  84 static inline unsigned
  85 sese_nb_params (sese region)
  86 {
  87   return VEC_length (tree, SESE_PARAMS (region));
  88 }
  89
  90 /* Checks whether BB is contained in the region delimited by ENTRY and
  91    EXIT blocks.  */
  92
  93 static inline bool
  94 bb_in_region (basic_block bb, basic_block entry, basic_block exit)
  95 {
  96 #ifdef ENABLE_CHECKING
  97   {
  98     edge e;
  99     edge_iterator ei;
 100
 101     /* Check that there are no edges coming in the region: all the
 102        predecessors of EXIT are dominated by ENTRY.  */
 103     FOR_EACH_EDGE (e, ei, exit->preds)
 104       dominated_by_p (CDI_DOMINATORS, e->src, entry);
 105
 106     /* Check that there are no edges going out of the region: the
 107        entry is post-dominated by the exit.  FIXME: This cannot be
 108        checked right now as the CDI_POST_DOMINATORS are needed.  */
 109   }
 110 #endif
 111
 112   return dominated_by_p (CDI_DOMINATORS, bb, entry)
 113          && !(dominated_by_p (CDI_DOMINATORS, bb, exit)
 114               && !dominated_by_p (CDI_DOMINATORS, entry, exit));
 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_sese_p (basic_block bb, sese region)
 122 {
 123   basic_block entry = SESE_ENTRY_BB (region);
 124   basic_block exit = SESE_EXIT_BB (region);
 125
 126   return bb_in_region (bb, entry, exit);
 127 }
 128
 129 /* Returns true when NAME is defined in REGION.  */
 130
 131 static inline bool
 132 defined_in_sese_p (tree name, sese region)
 133 {
 134   gimple stmt = SSA_NAME_DEF_STMT (name);
 135   basic_block bb = gimple_bb (stmt);
 136
 137   return bb && bb_in_sese_p (bb, region);
 138 }
 139
 140 /* Returns true when LOOP is in REGION.  */
 141
 142 static inline bool
 143 loop_in_sese_p (struct loop *loop, sese region)
 144 {
 145   return (bb_in_sese_p (loop->header, region)
 146           && bb_in_sese_p (loop->latch, region));
 147 }
 148
 149 /* Returns the loop depth of LOOP in REGION.  The loop depth
 150    is the same as the normal loop depth, but limited by a region.
 151
 152    Example:
 153
 154    loop_0
 155      loop_1
 156        {
 157          S0
 158             <- region start
 159          S1
 160
 161          loop_2
 162            S2
 163
 164          S3
 165             <- region end
 166        }
 167
 168     loop_0 does not exist in the region -> invalid
 169     loop_1 exists, but is not completely contained in the region -> depth 0
 170     loop_2 is completely contained -> depth 1  */
 171
 172 static inline unsigned int
 173 sese_loop_depth (sese region, loop_p loop)
 174 {
 175   unsigned int depth = 0;
 176
 177   gcc_assert ((!loop_in_sese_p (loop, region)
 178                && (SESE_ENTRY_BB (region)->loop_father == loop
 179                    || SESE_EXIT (region)->src->loop_father == loop))
 180               || loop_in_sese_p (loop, region));
 181
 182   while (loop_in_sese_p (loop, region))
 183     {
 184       depth++;
 185       loop = loop_outer (loop);
 186     }
 187
 188   return depth;
 189 }
 190
 191 /* Splits BB to make a single entry single exit region.  */
 192
 193 static inline sese
 194 split_region_for_bb (basic_block bb)
 195 {
 196   edge entry, exit;
 197
 198   if (single_pred_p (bb))
 199     entry = single_pred_edge (bb);
 200   else
 201     {
 202       entry = split_block_after_labels (bb);
 203       bb = single_succ (bb);
 204     }
 205
 206   if (single_succ_p (bb))
 207     exit = single_succ_edge (bb);
 208   else
 209     {
 210       gimple_stmt_iterator gsi = gsi_last_bb (bb);
 211       gsi_prev (&gsi);
 212       exit = split_block (bb, gsi_stmt (gsi));
 213     }
 214
 215   return new_sese (entry, exit);
 216 }
 217
 218 /* Returns the block preceding the entry of a SESE.  */
 219
 220 static inline basic_block
 221 block_before_sese (sese sese)
 222 {
 223   return SESE_ENTRY (sese)->src;
 224 }
 225
 226 /* Stores the INDEX in a vector for a given clast NAME.  */
 227
 228 typedef struct clast_name_index {
 229   int index;
 230   const char *name;
 231 } *clast_name_index_p;
 232
 233 /* Returns a pointer to a new element of type clast_name_index_p built
 234    from NAME and INDEX.  */
 235
 236 static inline clast_name_index_p
 237 new_clast_name_index (const char *name, int index)
 238 {
 239   clast_name_index_p res = XNEW (struct clast_name_index);
 240
 241   res->name = name;
 242   res->index = index;
 243   return res;
 244 }
 245
 246 /* For a given clast NAME, returns -1 if it does not correspond to any
 247    parameter, or otherwise, returns the index in the PARAMS or
 248    SCATTERING_DIMENSIONS vector.  */
 249
 250 static inline int
 251 clast_name_to_index (const char *name, htab_t index_table)
 252 {
 253   struct clast_name_index tmp;
 254   PTR *slot;
 255
 256   tmp.name = name;
 257   slot = htab_find_slot (index_table, &tmp, NO_INSERT);
 258
 259   if (slot && *slot)
 260     return ((struct clast_name_index *) *slot)->index;
 261
 262   return -1;
 263 }
 264
 265 /* Records in INDEX_TABLE the INDEX for NAME.  */
 266
 267 static inline void
 268 save_clast_name_index (htab_t index_table, const char *name, int index)
 269 {
 270   struct clast_name_index tmp;
 271   PTR *slot;
 272
 273   tmp.name = name;
 274   slot = htab_find_slot (index_table, &tmp, INSERT);
 275
 276   if (slot)
 277     *slot = new_clast_name_index (name, index);
 278 }
 279
 280 /* Print to stderr the element ELT.  */
 281
 282 static inline void
 283 debug_clast_name_index (clast_name_index_p elt)
 284 {
 285   fprintf (stderr, "(index = %d, name = %s)\n", elt->index, elt->name);
 286 }
 287
 288 /* Helper function for debug_rename_map.  */
 289
 290 static inline int
 291 debug_clast_name_indexes_1 (void **slot, void *s ATTRIBUTE_UNUSED)
 292 {
 293   struct clast_name_index *entry = (struct clast_name_index *) *slot;
 294   debug_clast_name_index (entry);
 295   return 1;
 296 }
 297
 298 /* Print to stderr all the elements of MAP.  */
 299
 300 static inline void
 301 debug_clast_name_indexes (htab_t map)
 302 {
 303   htab_traverse (map, debug_clast_name_indexes_1, NULL);
 304 }
 305
 306 /* Computes a hash function for database element ELT.  */
 307
 308 static inline hashval_t
 309 clast_name_index_elt_info (const void *elt)
 310 {
 311   return htab_hash_pointer (((const struct clast_name_index *) elt)->name);
 312 }
 313
 314 /* Compares database elements E1 and E2.  */
 315
 316 static inline int
 317 eq_clast_name_indexes (const void *e1, const void *e2)
 318 {
 319   const struct clast_name_index *elt1 = (const struct clast_name_index *) e1;
 320   const struct clast_name_index *elt2 = (const struct clast_name_index *) e2;
 321
 322   return (elt1->name == elt2->name);
 323 }
 324
 325 \f
 326
 327 /* A single entry single exit specialized for conditions.  */
 328
 329 typedef struct ifsese_s {
 330   sese region;
 331   sese true_region;
 332   sese false_region;
 333 } *ifsese;
 334
 335 extern void if_region_set_false_region (ifsese, sese);
 336 extern ifsese create_if_region_on_edge (edge, tree);
 337 extern ifsese move_sese_in_condition (sese);
 338 extern edge get_true_edge_from_guard_bb (basic_block);
 339 extern edge get_false_edge_from_guard_bb (basic_block);
 340
 341 static inline edge
 342 if_region_entry (ifsese if_region)
 343 {
 344   return SESE_ENTRY (if_region->region);
 345 }
 346
 347 static inline edge
 348 if_region_exit (ifsese if_region)
 349 {
 350   return SESE_EXIT (if_region->region);
 351 }
 352
 353 static inline basic_block
 354 if_region_get_condition_block (ifsese if_region)
 355 {
 356   return if_region_entry (if_region)->dest;
 357 }
 358
 359 /* Structure containing the mapping between the old names and the new
 360    names used after block copy in the new loop context.  */
 361 typedef struct rename_map_elt_s
 362 {
 363   tree old_name, expr;
 364 } *rename_map_elt;
 365
 366 DEF_VEC_P(rename_map_elt);
 367 DEF_VEC_ALLOC_P (rename_map_elt, heap);
 368
 369 extern void debug_rename_map (htab_t);
 370 extern hashval_t rename_map_elt_info (const void *);
 371 extern int eq_rename_map_elts (const void *, const void *);
 372 extern void set_rename (htab_t, tree, tree);
 373
 374 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW.  */
 375
 376 static inline rename_map_elt
 377 new_rename_map_elt (tree old_name, tree expr)
 378 {
 379   rename_map_elt res;
 380
 381   res = XNEW (struct rename_map_elt_s);
 382   res->old_name = old_name;
 383   res->expr = expr;
 384
 385   return res;
 386 }
 387
 388 /* Structure containing the mapping between the CLooG's induction
 389    variable and the type of the old induction variable.  */
 390 typedef struct ivtype_map_elt_s
 391 {
 392   tree type;
 393   const char *cloog_iv;
 394 } *ivtype_map_elt;
 395
 396 extern void debug_ivtype_map (htab_t);
 397 extern hashval_t ivtype_map_elt_info (const void *);
 398 extern int eq_ivtype_map_elts (const void *, const void *);
 399
 400 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW.  */
 401
 402 static inline ivtype_map_elt
 403 new_ivtype_map_elt (const char *cloog_iv, tree type)
 404 {
 405   ivtype_map_elt res;
 406
 407   res = XNEW (struct ivtype_map_elt_s);
 408   res->cloog_iv = cloog_iv;
 409   res->type = type;
 410
 411   return res;
 412 }
 413
 414 /* Free and compute again all the dominators information.  */
 415
 416 static inline void
 417 recompute_all_dominators (void)
 418 {
 419   mark_irreducible_loops ();
 420   free_dominance_info (CDI_DOMINATORS);
 421   free_dominance_info (CDI_POST_DOMINATORS);
 422   calculate_dominance_info (CDI_DOMINATORS);
 423   calculate_dominance_info (CDI_POST_DOMINATORS);
 424 }
 425
 426 typedef struct gimple_bb
 427 {
 428   basic_block bb;
 429
 430   /* Lists containing the restrictions of the conditional statements
 431      dominating this bb.  This bb can only be executed, if all conditions
 432      are true.
 433
 434      Example:
 435
 436      for (i = 0; i <= 20; i++)
 437      {
 438        A
 439
 440        if (2i <= 8)
 441          B
 442      }
 443
 444      So for B there is an additional condition (2i <= 8).
 445
 446      List of COND_EXPR and SWITCH_EXPR.  A COND_EXPR is true only if the
 447      corresponding element in CONDITION_CASES is not NULL_TREE.  For a
 448      SWITCH_EXPR the corresponding element in CONDITION_CASES is a
 449      CASE_LABEL_EXPR.  */
 450   VEC (gimple, heap) *conditions;
 451   VEC (gimple, heap) *condition_cases;
 452   VEC (data_reference_p, heap) *data_refs;
 453   htab_t cloog_iv_types;
 454 } *gimple_bb_p;
 455
 456 #define GBB_BB(GBB) GBB->bb
 457 #define GBB_DATA_REFS(GBB) GBB->data_refs
 458 #define GBB_CONDITIONS(GBB) GBB->conditions
 459 #define GBB_CONDITION_CASES(GBB) GBB->condition_cases
 460 #define GBB_CLOOG_IV_TYPES(GBB) GBB->cloog_iv_types
 461
 462 /* Return the innermost loop that contains the basic block GBB.  */
 463
 464 static inline struct loop *
 465 gbb_loop (struct gimple_bb *gbb)
 466 {
 467   return GBB_BB (gbb)->loop_father;
 468 }
 469
 470 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
 471    If there is no corresponding gimple loop, we return NULL.  */
 472
 473 static inline loop_p
 474 gbb_loop_at_index (gimple_bb_p gbb, sese region, int index)
 475 {
 476   loop_p loop = gbb_loop (gbb);
 477   int depth = sese_loop_depth (region, loop);
 478
 479   while (--depth > index)
 480     loop = loop_outer (loop);
 481
 482   gcc_assert (sese_contains_loop (region, loop));
 483
 484   return loop;
 485 }
 486
 487 /* The number of common loops in REGION for GBB1 and GBB2.  */
 488
 489 static inline int
 490 nb_common_loops (sese region, gimple_bb_p gbb1, gimple_bb_p gbb2)
 491 {
 492   loop_p l1 = gbb_loop (gbb1);
 493   loop_p l2 = gbb_loop (gbb2);
 494   loop_p common = find_common_loop (l1, l2);
 495
 496   return sese_loop_depth (region, common);
 497 }
 498
 499 extern void print_gimple_bb (FILE *, gimple_bb_p, int, int);
 500 extern void debug_gbb (gimple_bb_p, int);
 501
 502 #endif