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<basic_block, vec<basic_block> > bb_map_t;
  26 typedef hash_map<tree, vec<tree> > rename_map_t;
  27 typedef struct ifsese_s *ifsese;
  28 /* First phi is the new codegenerated phi second one is original phi.  */
  29 typedef std::pair <gphi *, gphi *> phi_rename;
  30 /* First edge is the init edge and second is the back edge w.r.t. a loop.  */
  31 typedef std::pair<edge, edge> init_back_edge_pair_t;
  32
  33 /* A Single Entry, Single Exit region is a part of the CFG delimited
  34    by two edges.  */
  35 struct sese_l
  36 {
  37   sese_l (edge e, edge x) : entry (e), exit (x) {}
  38
  39   operator bool () const { return entry && exit; }
  40
  41   edge entry;
  42   edge exit;
  43 };
  44
  45 /* Get the entry of an sese S.  */
  46
  47 static inline basic_block
  48 get_entry_bb (sese_l &s)
  49 {
  50   return s.entry->dest;
  51 }
  52
  53 /* Get the exit of an sese S.  */
  54
  55 static inline basic_block
  56 get_exit_bb (sese_l &s)
  57 {
  58   return s.exit->src;
  59 }
  60
  61 /* Returns the index of V where ELEM can be found. -1 Otherwise.  */
  62 template<typename T>
  63 int
  64 vec_find (const vec<T> &v, const T &elem)
  65 {
  66   int i;
  67   T t;
  68   FOR_EACH_VEC_ELT (v, i, t)
  69     if (elem == t)
  70       return i;
  71   return -1;
  72 }
  73
  74 /* A helper structure for bookkeeping information about a scop in graphite.  */
  75 typedef struct sese_info_t
  76 {
  77   /* The SESE region.  */
  78   sese_l region;
  79
  80   /* Parameters used within the SCOP.  */
  81   vec<tree> params;
  82
  83   /* Maps an old name to one or more new names.  When there are several new
  84      names, one has to select the definition corresponding to the immediate
  85      dominator.  */
  86   rename_map_t *rename_map;
  87
  88   /* Loops completely contained in this SESE.  */
  89   bitmap loops;
  90   vec<loop_p> loop_nest;
  91
  92   /* Basic blocks contained in this SESE.  */
  93   vec<basic_block> bbs;
  94
  95   /* Copied basic blocks indexed by the original bb.  */
  96   bb_map_t *copied_bb_map;
  97
  98   /* A vector of phi nodes to be updated when all arguments are available.  The
  99      pair contains first the old_phi and second the new_phi.  */
 100   vec<phi_rename> incomplete_phis;
 101
 102   /* The condition region generated for this sese.  */
 103   ifsese if_region;
 104
 105 } *sese_info_p;
 106
 107 extern sese_info_p new_sese_info (edge, edge);
 108 extern void free_sese_info (sese_info_p);
 109 extern void sese_insert_phis_for_liveouts (sese_info_p, basic_block, edge, edge);
 110 extern void build_sese_loop_nests (sese_info_p);
 111 extern struct loop *outermost_loop_in_sese (sese_l &, basic_block);
 112 extern tree scalar_evolution_in_region (sese_l &, loop_p, tree);
 113 extern bool scev_analyzable_p (tree, sese_l &);
 114 extern bool invariant_in_sese_p_rec (tree, sese_l &, bool *);
 115
 116 /* Check that SESE contains LOOP.  */
 117
 118 static inline bool
 119 sese_contains_loop (sese_info_p sese, struct loop *loop)
 120 {
 121   return bitmap_bit_p (sese->loops, loop->num);
 122 }
 123
 124 /* The number of parameters in REGION. */
 125
 126 static inline unsigned
 127 sese_nb_params (sese_info_p region)
 128 {
 129   return region->params.length ();
 130 }
 131
 132 /* Checks whether BB is contained in the region delimited by ENTRY and
 133    EXIT blocks.  */
 134
 135 static inline bool
 136 bb_in_region (basic_block bb, basic_block entry, basic_block exit)
 137 {
 138   /* FIXME: PR67842.  */
 139 #if 0
 140   if (flag_checking)
 141     {
 142       edge e;
 143       edge_iterator ei;
 144
 145       /* Check that there are no edges coming in the region: all the
 146          predecessors of EXIT are dominated by ENTRY.  */
 147       FOR_EACH_EDGE (e, ei, exit->preds)
 148         gcc_assert (dominated_by_p (CDI_DOMINATORS, e->src, entry));
 149     }
 150 #endif
 151
 152   return dominated_by_p (CDI_DOMINATORS, bb, entry)
 153          && !(dominated_by_p (CDI_DOMINATORS, bb, exit)
 154               && !dominated_by_p (CDI_DOMINATORS, entry, exit));
 155 }
 156
 157 /* Checks whether BB is contained in the region delimited by ENTRY and
 158    EXIT blocks.  */
 159
 160 static inline bool
 161 bb_in_sese_p (basic_block bb, sese_l &r)
 162 {
 163   return bb_in_region (bb, r.entry->dest, r.exit->dest);
 164 }
 165
 166 /* Returns true when STMT is defined in REGION.  */
 167
 168 static inline bool
 169 stmt_in_sese_p (gimple *stmt, sese_l &r)
 170 {
 171   basic_block bb = gimple_bb (stmt);
 172   return bb && bb_in_sese_p (bb, r);
 173 }
 174
 175 /* Returns true when NAME is defined in REGION.  */
 176
 177 static inline bool
 178 defined_in_sese_p (tree name, sese_l &r)
 179 {
 180   return stmt_in_sese_p (SSA_NAME_DEF_STMT (name), r);
 181 }
 182
 183 /* Returns true when LOOP is in REGION.  */
 184
 185 static inline bool
 186 loop_in_sese_p (struct loop *loop, sese_l &region)
 187 {
 188   return (bb_in_sese_p (loop->header, region)
 189           && bb_in_sese_p (loop->latch, region));
 190 }
 191
 192 /* Returns the loop depth of LOOP in REGION.  The loop depth
 193    is the same as the normal loop depth, but limited by a region.
 194
 195    Example:
 196
 197    loop_0
 198      loop_1
 199        {
 200          S0
 201             <- region start
 202          S1
 203
 204          loop_2
 205            S2
 206
 207          S3
 208             <- region end
 209        }
 210
 211     loop_0 does not exist in the region -> invalid
 212     loop_1 exists, but is not completely contained in the region -> depth 0
 213     loop_2 is completely contained -> depth 1  */
 214
 215 static inline unsigned int
 216 sese_loop_depth (sese_l &region, loop_p loop)
 217 {
 218   unsigned int depth = 0;
 219
 220   while (loop_in_sese_p (loop, region))
 221     {
 222       depth++;
 223       loop = loop_outer (loop);
 224     }
 225
 226   return depth;
 227 }
 228
 229 /* A single entry single exit specialized for conditions.  */
 230
 231 typedef struct ifsese_s {
 232   sese_info_p region;
 233   sese_info_p true_region;
 234   sese_info_p false_region;
 235 } *ifsese;
 236
 237 extern void if_region_set_false_region (ifsese, sese_info_p);
 238 extern ifsese move_sese_in_condition (sese_info_p);
 239 extern void set_ifsese_condition (ifsese, tree);
 240 extern edge get_true_edge_from_guard_bb (basic_block);
 241 extern edge get_false_edge_from_guard_bb (basic_block);
 242
 243 static inline edge
 244 if_region_entry (ifsese if_region)
 245 {
 246   return if_region->region->region.entry;
 247 }
 248
 249 static inline edge
 250 if_region_exit (ifsese if_region)
 251 {
 252   return if_region->region->region.exit;
 253 }
 254
 255 static inline basic_block
 256 if_region_get_condition_block (ifsese if_region)
 257 {
 258   return if_region_entry (if_region)->dest;
 259 }
 260
 261 /* Free and compute again all the dominators information.  */
 262
 263 static inline void
 264 recompute_all_dominators (void)
 265 {
 266   mark_irreducible_loops ();
 267   free_dominance_info (CDI_DOMINATORS);
 268   calculate_dominance_info (CDI_DOMINATORS);
 269
 270   free_dominance_info (CDI_POST_DOMINATORS);
 271   calculate_dominance_info (CDI_POST_DOMINATORS);
 272 }
 273
 274 typedef std::pair <gimple *, tree> scalar_use;
 275
 276 typedef struct gimple_poly_bb
 277 {
 278   basic_block bb;
 279   struct poly_bb *pbb;
 280
 281   /* Lists containing the restrictions of the conditional statements
 282      dominating this bb.  This bb can only be executed, if all conditions
 283      are true.
 284
 285      Example:
 286
 287      for (i = 0; i <= 20; i++)
 288      {
 289        A
 290
 291        if (2i <= 8)
 292          B
 293      }
 294
 295      So for B there is an additional condition (2i <= 8).
 296
 297      List of COND_EXPR and SWITCH_EXPR.  A COND_EXPR is true only if the
 298      corresponding element in CONDITION_CASES is not NULL_TREE.  For a
 299      SWITCH_EXPR the corresponding element in CONDITION_CASES is a
 300      CASE_LABEL_EXPR.  */
 301   vec<gimple *> conditions;
 302   vec<gimple *> condition_cases;
 303   vec<data_reference_p> data_refs;
 304   vec<scalar_use> read_scalar_refs;
 305   vec<tree> write_scalar_refs;
 306 } *gimple_poly_bb_p;
 307
 308 #define GBB_BB(GBB) (GBB)->bb
 309 #define GBB_PBB(GBB) (GBB)->pbb
 310 #define GBB_DATA_REFS(GBB) (GBB)->data_refs
 311 #define GBB_CONDITIONS(GBB) (GBB)->conditions
 312 #define GBB_CONDITION_CASES(GBB) (GBB)->condition_cases
 313
 314 /* Return the innermost loop that contains the basic block GBB.  */
 315
 316 static inline struct loop *
 317 gbb_loop (gimple_poly_bb_p gbb)
 318 {
 319   return GBB_BB (gbb)->loop_father;
 320 }
 321
 322 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
 323    If there is no corresponding gimple loop, we return NULL.  */
 324
 325 static inline loop_p
 326 gbb_loop_at_index (gimple_poly_bb_p gbb, sese_l &region, int index)
 327 {
 328   loop_p loop = gbb_loop (gbb);
 329   int depth = sese_loop_depth (region, loop);
 330
 331   while (--depth > index)
 332     loop = loop_outer (loop);
 333
 334   gcc_assert (loop_in_sese_p (loop, region));
 335
 336   return loop;
 337 }
 338
 339 /* The number of common loops in REGION for GBB1 and GBB2.  */
 340
 341 static inline int
 342 nb_common_loops (sese_l &region, gimple_poly_bb_p gbb1, gimple_poly_bb_p gbb2)
 343 {
 344   loop_p l1 = gbb_loop (gbb1);
 345   loop_p l2 = gbb_loop (gbb2);
 346   loop_p common = find_common_loop (l1, l2);
 347
 348   return sese_loop_depth (region, common);
 349 }
 350
 351 #endif