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