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