gcc/sese.h

   1 /* Single entry single exit control flow regions.
   2    Copyright (C) 2008-2013 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> params;
  34
  35   /* Loops completely contained in the SCOP.  */
  36   bitmap loops;
  37   vec<loop_p> 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 build_sese_loop_nests (sese);
  58 extern edge copy_bb_and_scalar_dependences (basic_block, sese, edge,
  59                                             vec<tree> , bool *);
  60 extern struct loop *outermost_loop_in_sese (sese, basic_block);
  61 extern tree scalar_evolution_in_region (sese, loop_p, tree);
  62
  63 /* Check that SESE contains LOOP.  */
  64
  65 static inline bool
  66 sese_contains_loop (sese sese, struct loop *loop)
  67 {
  68   return bitmap_bit_p (SESE_LOOPS (sese), loop->num);
  69 }
  70
  71 /* The number of parameters in REGION. */
  72
  73 static inline unsigned
  74 sese_nb_params (sese region)
  75 {
  76   return SESE_PARAMS (region).length ();
  77 }
  78
  79 /* Checks whether BB is contained in the region delimited by ENTRY and
  80    EXIT blocks.  */
  81
  82 static inline bool
  83 bb_in_region (basic_block bb, basic_block entry, basic_block exit)
  84 {
  85 #ifdef ENABLE_CHECKING
  86   {
  87     edge e;
  88     edge_iterator ei;
  89
  90     /* Check that there are no edges coming in the region: all the
  91        predecessors of EXIT are dominated by ENTRY.  */
  92     FOR_EACH_EDGE (e, ei, exit->preds)
  93       dominated_by_p (CDI_DOMINATORS, e->src, entry);
  94   }
  95 #endif
  96
  97   return dominated_by_p (CDI_DOMINATORS, bb, entry)
  98          && !(dominated_by_p (CDI_DOMINATORS, bb, exit)
  99               && !dominated_by_p (CDI_DOMINATORS, entry, exit));
 100 }
 101
 102 /* Checks whether BB is contained in the region delimited by ENTRY and
 103    EXIT blocks.  */
 104
 105 static inline bool
 106 bb_in_sese_p (basic_block bb, sese region)
 107 {
 108   basic_block entry = SESE_ENTRY_BB (region);
 109   basic_block exit = SESE_EXIT_BB (region);
 110
 111   return bb_in_region (bb, entry, exit);
 112 }
 113
 114 /* Returns true when STMT is defined in REGION.  */
 115
 116 static inline bool
 117 stmt_in_sese_p (gimple stmt, sese region)
 118 {
 119   basic_block bb = gimple_bb (stmt);
 120   return bb && bb_in_sese_p (bb, region);
 121 }
 122
 123 /* Returns true when NAME is defined in REGION.  */
 124
 125 static inline bool
 126 defined_in_sese_p (tree name, sese region)
 127 {
 128   gimple stmt = SSA_NAME_DEF_STMT (name);
 129   return stmt_in_sese_p (stmt, region);
 130 }
 131
 132 /* Returns true when LOOP is in REGION.  */
 133
 134 static inline bool
 135 loop_in_sese_p (struct loop *loop, sese region)
 136 {
 137   return (bb_in_sese_p (loop->header, region)
 138           && bb_in_sese_p (loop->latch, region));
 139 }
 140
 141 /* Returns the loop depth of LOOP in REGION.  The loop depth
 142    is the same as the normal loop depth, but limited by a region.
 143
 144    Example:
 145
 146    loop_0
 147      loop_1
 148        {
 149          S0
 150             <- region start
 151          S1
 152
 153          loop_2
 154            S2
 155
 156          S3
 157             <- region end
 158        }
 159
 160     loop_0 does not exist in the region -> invalid
 161     loop_1 exists, but is not completely contained in the region -> depth 0
 162     loop_2 is completely contained -> depth 1  */
 163
 164 static inline unsigned int
 165 sese_loop_depth (sese region, loop_p loop)
 166 {
 167   unsigned int depth = 0;
 168
 169   gcc_assert ((!loop_in_sese_p (loop, region)
 170                && (SESE_ENTRY_BB (region)->loop_father == loop
 171                    || SESE_EXIT (region)->src->loop_father == loop))
 172               || loop_in_sese_p (loop, region));
 173
 174   while (loop_in_sese_p (loop, region))
 175     {
 176       depth++;
 177       loop = loop_outer (loop);
 178     }
 179
 180   return depth;
 181 }
 182
 183 /* Splits BB to make a single entry single exit region.  */
 184
 185 static inline sese
 186 split_region_for_bb (basic_block bb)
 187 {
 188   edge entry, exit;
 189
 190   if (single_pred_p (bb))
 191     entry = single_pred_edge (bb);
 192   else
 193     {
 194       entry = split_block_after_labels (bb);
 195       bb = single_succ (bb);
 196     }
 197
 198   if (single_succ_p (bb))
 199     exit = single_succ_edge (bb);
 200   else
 201     {
 202       gimple_stmt_iterator gsi = gsi_last_bb (bb);
 203       gsi_prev (&gsi);
 204       exit = split_block (bb, gsi_stmt (gsi));
 205     }
 206
 207   return new_sese (entry, exit);
 208 }
 209
 210 /* Returns the block preceding the entry of a SESE.  */
 211
 212 static inline basic_block
 213 block_before_sese (sese sese)
 214 {
 215   return SESE_ENTRY (sese)->src;
 216 }
 217
 218 \f
 219
 220 /* A single entry single exit specialized for conditions.  */
 221
 222 typedef struct ifsese_s {
 223   sese region;
 224   sese true_region;
 225   sese false_region;
 226 } *ifsese;
 227
 228 extern void if_region_set_false_region (ifsese, sese);
 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
 260 extern void debug_rename_map (htab_t);
 261 extern hashval_t rename_map_elt_info (const void *);
 262 extern int eq_rename_map_elts (const void *, const void *);
 263
 264 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW.  */
 265
 266 static inline rename_map_elt
 267 new_rename_map_elt (tree old_name, tree expr)
 268 {
 269   rename_map_elt res;
 270
 271   res = XNEW (struct rename_map_elt_s);
 272   res->old_name = old_name;
 273   res->expr = expr;
 274
 275   return res;
 276 }
 277
 278 /* Free and compute again all the dominators information.  */
 279
 280 static inline void
 281 recompute_all_dominators (void)
 282 {
 283   mark_irreducible_loops ();
 284   free_dominance_info (CDI_DOMINATORS);
 285   calculate_dominance_info (CDI_DOMINATORS);
 286 }
 287
 288 typedef struct gimple_bb
 289 {
 290   basic_block bb;
 291   struct poly_bb *pbb;
 292
 293   /* Lists containing the restrictions of the conditional statements
 294      dominating this bb.  This bb can only be executed, if all conditions
 295      are true.
 296
 297      Example:
 298
 299      for (i = 0; i <= 20; i++)
 300      {
 301        A
 302
 303        if (2i <= 8)
 304          B
 305      }
 306
 307      So for B there is an additional condition (2i <= 8).
 308
 309      List of COND_EXPR and SWITCH_EXPR.  A COND_EXPR is true only if the
 310      corresponding element in CONDITION_CASES is not NULL_TREE.  For a
 311      SWITCH_EXPR the corresponding element in CONDITION_CASES is a
 312      CASE_LABEL_EXPR.  */
 313   vec<gimple> conditions;
 314   vec<gimple> condition_cases;
 315   vec<data_reference_p> data_refs;
 316 } *gimple_bb_p;
 317
 318 #define GBB_BB(GBB) (GBB)->bb
 319 #define GBB_PBB(GBB) (GBB)->pbb
 320 #define GBB_DATA_REFS(GBB) (GBB)->data_refs
 321 #define GBB_CONDITIONS(GBB) (GBB)->conditions
 322 #define GBB_CONDITION_CASES(GBB) (GBB)->condition_cases
 323
 324 /* Return the innermost loop that contains the basic block GBB.  */
 325
 326 static inline struct loop *
 327 gbb_loop (struct gimple_bb *gbb)
 328 {
 329   return GBB_BB (gbb)->loop_father;
 330 }
 331
 332 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
 333    If there is no corresponding gimple loop, we return NULL.  */
 334
 335 static inline loop_p
 336 gbb_loop_at_index (gimple_bb_p gbb, sese region, int index)
 337 {
 338   loop_p loop = gbb_loop (gbb);
 339   int depth = sese_loop_depth (region, loop);
 340
 341   while (--depth > index)
 342     loop = loop_outer (loop);
 343
 344   gcc_assert (sese_contains_loop (region, loop));
 345
 346   return loop;
 347 }
 348
 349 /* The number of common loops in REGION for GBB1 and GBB2.  */
 350
 351 static inline int
 352 nb_common_loops (sese region, gimple_bb_p gbb1, gimple_bb_p gbb2)
 353 {
 354   loop_p l1 = gbb_loop (gbb1);
 355   loop_p l2 = gbb_loop (gbb2);
 356   loop_p common = find_common_loop (l1, l2);
 357
 358   return sese_loop_depth (region, common);
 359 }
 360
 361 /* Return true when DEF can be analyzed in REGION by the scalar
 362    evolution analyzer.  */
 363
 364 static inline bool
 365 scev_analyzable_p (tree def, sese region)
 366 {
 367   loop_p loop;
 368   tree scev;
 369   tree type = TREE_TYPE (def);
 370
 371   /* When Graphite generates code for a scev, the code generator
 372      expresses the scev in function of a single induction variable.
 373      This is unsafe for floating point computations, as it may replace
 374      a floating point sum reduction with a multiplication.  The
 375      following test returns false for non integer types to avoid such
 376      problems.  */
 377   if (!INTEGRAL_TYPE_P (type)
 378       && !POINTER_TYPE_P (type))
 379     return false;
 380
 381   loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
 382   scev = scalar_evolution_in_region (region, loop, def);
 383
 384   return !chrec_contains_undetermined (scev)
 385     && (TREE_CODE (scev) != SSA_NAME
 386         || !defined_in_sese_p (scev, region))
 387     && (tree_does_not_contain_chrecs (scev)
 388         || evolution_function_is_affine_p (scev));
 389 }
 390
 391 #endif