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