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