gcc/sese.h

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