gcc/sese.h

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