gcc/sese.h

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