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