gcc/sese.h

   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 \f
 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