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