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   /* Loops completely contained in the SCOP.  */
  36   bitmap loops;
  37   VEC (loop_p, heap) *loop_nest;
  38
  39   /* Are we allowed to add more params?  This is for debugging purpose.  We
  40      can only add new params before generating the bb domains, otherwise they
  41      become invalid.  */
  42   bool add_params;
  43 } *sese;
  44
  45 #define SESE_ENTRY(S) (S->entry)
  46 #define SESE_ENTRY_BB(S) (S->entry->dest)
  47 #define SESE_EXIT(S) (S->exit)
  48 #define SESE_EXIT_BB(S) (S->exit->dest)
  49 #define SESE_PARAMS(S) (S->params)
  50 #define SESE_LOOPS(S) (S->loops)
  51 #define SESE_LOOP_NEST(S) (S->loop_nest)
  52 #define SESE_ADD_PARAMS(S) (S->add_params)
  53
  54 extern sese new_sese (edge, edge);
  55 extern void free_sese (sese);
  56 extern void sese_insert_phis_for_liveouts (sese, basic_block, edge, edge);
  57 extern void sese_adjust_liveout_phis (sese, htab_t, basic_block, edge, edge);
  58 extern void build_sese_loop_nests (sese);
  59 extern edge copy_bb_and_scalar_dependences (basic_block, sese, edge, htab_t);
  60 extern struct loop *outermost_loop_in_sese (sese, basic_block);
  61 extern void insert_loop_close_phis (htab_t, loop_p);
  62 extern void insert_guard_phis (basic_block, edge, edge, htab_t, htab_t);
  63 extern tree scalar_evolution_in_region (sese, loop_p, tree);
  64
  65 /* Check that SESE contains LOOP.  */
  66
  67 static inline bool
  68 sese_contains_loop (sese sese, struct loop *loop)
  69 {
  70   return bitmap_bit_p (SESE_LOOPS (sese), loop->num);
  71 }
  72
  73 /* The number of parameters in REGION. */
  74
  75 static inline unsigned
  76 sese_nb_params (sese region)
  77 {
  78   return VEC_length (tree, SESE_PARAMS (region));
  79 }
  80
  81 /* Checks whether BB is contained in the region delimited by ENTRY and
  82    EXIT blocks.  */
  83
  84 static inline bool
  85 bb_in_region (basic_block bb, basic_block entry, basic_block exit)
  86 {
  87 #ifdef ENABLE_CHECKING
  88   {
  89     edge e;
  90     edge_iterator ei;
  91
  92     /* Check that there are no edges coming in the region: all the
  93        predecessors of EXIT are dominated by ENTRY.  */
  94     FOR_EACH_EDGE (e, ei, exit->preds)
  95       dominated_by_p (CDI_DOMINATORS, e->src, entry);
  96
  97     /* Check that there are no edges going out of the region: the
  98        entry is post-dominated by the exit.  FIXME: This cannot be
  99        checked right now as the CDI_POST_DOMINATORS are needed.  */
 100   }
 101 #endif
 102
 103   return dominated_by_p (CDI_DOMINATORS, bb, entry)
 104          && !(dominated_by_p (CDI_DOMINATORS, bb, exit)
 105               && !dominated_by_p (CDI_DOMINATORS, entry, exit));
 106 }
 107
 108 /* Checks whether BB is contained in the region delimited by ENTRY and
 109    EXIT blocks.  */
 110
 111 static inline bool
 112 bb_in_sese_p (basic_block bb, sese region)
 113 {
 114   basic_block entry = SESE_ENTRY_BB (region);
 115   basic_block exit = SESE_EXIT_BB (region);
 116
 117   return bb_in_region (bb, entry, exit);
 118 }
 119
 120 /* Returns true when NAME is defined in REGION.  */
 121
 122 static inline bool
 123 defined_in_sese_p (tree name, sese region)
 124 {
 125   gimple stmt = SSA_NAME_DEF_STMT (name);
 126   basic_block bb = gimple_bb (stmt);
 127
 128   return bb && bb_in_sese_p (bb, region);
 129 }
 130
 131 /* Returns true when LOOP is in REGION.  */
 132
 133 static inline bool
 134 loop_in_sese_p (struct loop *loop, sese region)
 135 {
 136   return (bb_in_sese_p (loop->header, region)
 137           && bb_in_sese_p (loop->latch, region));
 138 }
 139
 140 /* Returns the loop depth of LOOP in REGION.  The loop depth
 141    is the same as the normal loop depth, but limited by a region.
 142
 143    Example:
 144
 145    loop_0
 146      loop_1
 147        {
 148          S0
 149             <- region start
 150          S1
 151
 152          loop_2
 153            S2
 154
 155          S3
 156             <- region end
 157        }
 158
 159     loop_0 does not exist in the region -> invalid
 160     loop_1 exists, but is not completely contained in the region -> depth 0
 161     loop_2 is completely contained -> depth 1  */
 162
 163 static inline unsigned int
 164 sese_loop_depth (sese region, loop_p loop)
 165 {
 166   unsigned int depth = 0;
 167
 168   gcc_assert ((!loop_in_sese_p (loop, region)
 169                && (SESE_ENTRY_BB (region)->loop_father == loop
 170                    || SESE_EXIT (region)->src->loop_father == loop))
 171               || loop_in_sese_p (loop, region));
 172
 173   while (loop_in_sese_p (loop, region))
 174     {
 175       depth++;
 176       loop = loop_outer (loop);
 177     }
 178
 179   return depth;
 180 }
 181
 182 /* Splits BB to make a single entry single exit region.  */
 183
 184 static inline sese
 185 split_region_for_bb (basic_block bb)
 186 {
 187   edge entry, exit;
 188
 189   if (single_pred_p (bb))
 190     entry = single_pred_edge (bb);
 191   else
 192     {
 193       entry = split_block_after_labels (bb);
 194       bb = single_succ (bb);
 195     }
 196
 197   if (single_succ_p (bb))
 198     exit = single_succ_edge (bb);
 199   else
 200     {
 201       gimple_stmt_iterator gsi = gsi_last_bb (bb);
 202       gsi_prev (&gsi);
 203       exit = split_block (bb, gsi_stmt (gsi));
 204     }
 205
 206   return new_sese (entry, exit);
 207 }
 208
 209 /* Returns the block preceding the entry of a SESE.  */
 210
 211 static inline basic_block
 212 block_before_sese (sese sese)
 213 {
 214   return SESE_ENTRY (sese)->src;
 215 }
 216
 217 \f
 218
 219 /* A single entry single exit specialized for conditions.  */
 220
 221 typedef struct ifsese_s {
 222   sese region;
 223   sese true_region;
 224   sese false_region;
 225 } *ifsese;
 226
 227 extern void if_region_set_false_region (ifsese, sese);
 228 extern ifsese create_if_region_on_edge (edge, tree);
 229 extern ifsese move_sese_in_condition (sese);
 230 extern edge get_true_edge_from_guard_bb (basic_block);
 231 extern edge get_false_edge_from_guard_bb (basic_block);
 232 extern void set_ifsese_condition (ifsese, tree);
 233
 234 static inline edge
 235 if_region_entry (ifsese if_region)
 236 {
 237   return SESE_ENTRY (if_region->region);
 238 }
 239
 240 static inline edge
 241 if_region_exit (ifsese if_region)
 242 {
 243   return SESE_EXIT (if_region->region);
 244 }
 245
 246 static inline basic_block
 247 if_region_get_condition_block (ifsese if_region)
 248 {
 249   return if_region_entry (if_region)->dest;
 250 }
 251
 252 /* Structure containing the mapping between the old names and the new
 253    names used after block copy in the new loop context.  */
 254 typedef struct rename_map_elt_s
 255 {
 256   tree old_name, expr;
 257 } *rename_map_elt;
 258
 259 DEF_VEC_P(rename_map_elt);
 260 DEF_VEC_ALLOC_P (rename_map_elt, heap);
 261
 262 extern void debug_rename_map (htab_t);
 263 extern hashval_t rename_map_elt_info (const void *);
 264 extern int eq_rename_map_elts (const void *, const void *);
 265 extern void set_rename (htab_t, tree, tree);
 266 extern void rename_nb_iterations (htab_t);
 267 extern void rename_sese_parameters (htab_t, sese);
 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   free_dominance_info (CDI_POST_DOMINATORS);
 317   calculate_dominance_info (CDI_DOMINATORS);
 318   calculate_dominance_info (CDI_POST_DOMINATORS);
 319 }
 320
 321 typedef struct gimple_bb
 322 {
 323   basic_block bb;
 324
 325   /* Lists containing the restrictions of the conditional statements
 326      dominating this bb.  This bb can only be executed, if all conditions
 327      are true.
 328
 329      Example:
 330
 331      for (i = 0; i <= 20; i++)
 332      {
 333        A
 334
 335        if (2i <= 8)
 336          B
 337      }
 338
 339      So for B there is an additional condition (2i <= 8).
 340
 341      List of COND_EXPR and SWITCH_EXPR.  A COND_EXPR is true only if the
 342      corresponding element in CONDITION_CASES is not NULL_TREE.  For a
 343      SWITCH_EXPR the corresponding element in CONDITION_CASES is a
 344      CASE_LABEL_EXPR.  */
 345   VEC (gimple, heap) *conditions;
 346   VEC (gimple, heap) *condition_cases;
 347   VEC (data_reference_p, heap) *data_refs;
 348   htab_t cloog_iv_types;
 349 } *gimple_bb_p;
 350
 351 #define GBB_BB(GBB) GBB->bb
 352 #define GBB_DATA_REFS(GBB) GBB->data_refs
 353 #define GBB_CONDITIONS(GBB) GBB->conditions
 354 #define GBB_CONDITION_CASES(GBB) GBB->condition_cases
 355 #define GBB_CLOOG_IV_TYPES(GBB) GBB->cloog_iv_types
 356
 357 /* Return the innermost loop that contains the basic block GBB.  */
 358
 359 static inline struct loop *
 360 gbb_loop (struct gimple_bb *gbb)
 361 {
 362   return GBB_BB (gbb)->loop_father;
 363 }
 364
 365 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
 366    If there is no corresponding gimple loop, we return NULL.  */
 367
 368 static inline loop_p
 369 gbb_loop_at_index (gimple_bb_p gbb, sese region, int index)
 370 {
 371   loop_p loop = gbb_loop (gbb);
 372   int depth = sese_loop_depth (region, loop);
 373
 374   while (--depth > index)
 375     loop = loop_outer (loop);
 376
 377   gcc_assert (sese_contains_loop (region, loop));
 378
 379   return loop;
 380 }
 381
 382 /* The number of common loops in REGION for GBB1 and GBB2.  */
 383
 384 static inline int
 385 nb_common_loops (sese region, gimple_bb_p gbb1, gimple_bb_p gbb2)
 386 {
 387   loop_p l1 = gbb_loop (gbb1);
 388   loop_p l2 = gbb_loop (gbb2);
 389   loop_p common = find_common_loop (l1, l2);
 390
 391   return sese_loop_depth (region, common);
 392 }
 393
 394 #endif