gcc/gimple-ssa-split-paths.c

   1 /* Support routines for Splitting Paths to loop backedges
   2    Copyright (C) 2015 Free Software Foundation, Inc.
   3    Contributed by Ajit Kumar Agarwal <ajitkum@xilinx.com>.
   4
   5  This file is part of GCC.
   6
   7  GCC is free software; you can redistribute it and/or modify
   8  it under the terms of the GNU General Public License as published by
   9  the Free Software Foundation; either version 3, or (at your option)
  10  any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "backend.h"
  25 #include "tree.h"
  26 #include "gimple.h"
  27 #include "tree-pass.h"
  28 #include "cfganal.h"
  29 #include "cfgloop.h"
  30 #include "gimple-iterator.h"
  31 #include "tracer.h"
  32
  33 /* Given LATCH, the latch block in a loop, see if the shape of the
  34    path reaching LATCH is suitable for being split by duplication.
  35    If so, return the block that will be duplicated into its predecessor
  36    paths.  Else return NULL.  */
  37
  38 static basic_block
  39 find_block_to_duplicate_for_splitting_paths (basic_block latch)
  40 {
  41   /* We should have simple latches at this point.  So the latch should
  42      have a single successor.  This implies the predecessor of the latch
  43      likely has the loop exit.  And it's that predecessor we're most
  44      interested in. To keep things simple, we're going to require that
  45      the latch have a single predecessor too.  */
  46   if (single_succ_p (latch) && single_pred_p (latch))
  47     {
  48       basic_block bb = get_immediate_dominator (CDI_DOMINATORS, latch);
  49       gcc_assert (single_pred_edge (latch)->src == bb);
  50
  51       /* If BB has been marked as not to be duplicated, then honor that
  52          request.  */
  53       if (ignore_bb_p (bb))
  54         return NULL;
  55
  56       gimple *last = gsi_stmt (gsi_last_nondebug_bb (bb));
  57       /* The immediate dominator of the latch must end in a conditional.  */
  58       if (!last || gimple_code (last) != GIMPLE_COND)
  59         return NULL;
  60
  61       /* We're hoping that BB is a join point for an IF-THEN-ELSE diamond
  62          region.  Verify that it is.
  63
  64          First, verify that BB has two predecessors (each arm of the
  65          IF-THEN-ELSE) and two successors (the latch and exit).  */
  66       if (EDGE_COUNT (bb->preds) == 2 && EDGE_COUNT (bb->succs) == 2)
  67         {
  68           /* Now verify that BB's immediate dominator ends in a
  69              conditional as well.  */
  70           basic_block bb_idom = get_immediate_dominator (CDI_DOMINATORS, bb);
  71           gimple *last = gsi_stmt (gsi_last_nondebug_bb (bb_idom));
  72           if (!last || gimple_code (last) != GIMPLE_COND)
  73             return NULL;
  74
  75           /* And that BB's immediate dominator's successors are the
  76              the predecessors of BB.  */
  77           if (!find_edge (bb_idom, EDGE_PRED (bb, 0)->src)
  78               || !find_edge (bb_idom, EDGE_PRED (bb, 1)->src))
  79             return NULL;
  80
  81           /* So at this point we have a simple diamond for an IF-THEN-ELSE
  82              construct starting at BB_IDOM, with a join point at BB.  BB
  83              pass control outside the loop or to the loop latch.
  84
  85              We're going to want to create two duplicates of BB, one for
  86              each successor of BB_IDOM.  */
  87           return bb;
  88         }
  89     }
  90   return NULL;
  91 }
  92
  93 /* Return TRUE if BB is a reasonable block to duplicate by examining
  94    its size, false otherwise.  BB will always be a loop latch block.
  95
  96    Should this use the same tests as we do for jump threading?  */
  97
  98 static bool
  99 is_feasible_trace (basic_block bb)
 100 {
 101   int num_stmt = 0;
 102   gimple_stmt_iterator gsi;
 103
 104   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 105     {
 106       gimple *stmt = gsi_stmt (gsi);
 107       if (!is_gimple_debug (stmt))
 108         num_stmt++;
 109     }
 110
 111   /* We may want to limit how many statements we copy.  */
 112   if (num_stmt > 1)
 113     return true;
 114
 115   return false;
 116 }
 117
 118 /* If the immediate dominator of the latch of the loop is
 119    block with conditional branch, then the loop latch  is
 120    duplicated to its predecessors path preserving the SSA
 121    semantics.
 122
 123    CFG before transformation.
 124
 125               2
 126               |
 127               |
 128         +---->3
 129         |    / \
 130         |   /   \
 131         |  4     5
 132         |   \   /
 133         |    \ /
 134         |     6
 135         |    / \
 136         |   /   \
 137         |  8     7
 138         |  |     |
 139         ---+     E
 140
 141
 142
 143     Block 8 is the latch.  We're going to make copies of block 6 (9 & 10)
 144     and wire things up so they look like this:
 145
 146               2
 147               |
 148               |
 149         +---->3
 150         |    / \
 151         |   /   \
 152         |  4     5
 153         |  |     |
 154         |  |     |
 155         |  9    10
 156         |  |\   /|
 157         |  | \ / |
 158         |  |  7  |
 159         |  |  |  |
 160         |  |  E  |
 161         |  |     |
 162         |   \   /
 163         |    \ /
 164         +-----8
 165
 166
 167     Blocks 9 and 10 will get merged into blocks 4 & 5 respectively which
 168     enables CSE, DCE and other optimizations to occur on a larger block
 169     of code.   */
 170
 171 static bool
 172 split_paths ()
 173 {
 174   bool changed = false;
 175   loop_p loop;
 176
 177   loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
 178   initialize_original_copy_tables ();
 179   calculate_dominance_info (CDI_DOMINATORS);
 180
 181   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
 182     {
 183       /* See if there is a block that we can duplicate to split the
 184          path to the loop latch.  */
 185       basic_block bb = find_block_to_duplicate_for_splitting_paths (loop->latch);
 186
 187       /* BB is the merge point for an IF-THEN-ELSE we want to transform.
 188
 189          Essentially we want to create two duplicates of BB and append
 190          a duplicate to the THEN and ELSE clauses.  This will split the
 191          path leading to the latch.  BB will be unreachable and removed.  */
 192       if (bb && is_feasible_trace (bb))
 193         {
 194           if (dump_file && (dump_flags & TDF_DETAILS))
 195             fprintf (dump_file,
 196                      "Duplicating join block %d into predecessor paths\n",
 197                      bb->index);
 198           basic_block pred0 = EDGE_PRED (bb, 0)->src;
 199           basic_block pred1 = EDGE_PRED (bb, 1)->src;
 200           transform_duplicate (pred0, bb);
 201           transform_duplicate (pred1, bb);
 202           changed = true;
 203         }
 204     }
 205
 206   loop_optimizer_finalize ();
 207   free_original_copy_tables ();
 208   return changed;
 209 }
 210
 211 /* Main entry point for splitting paths.  Returns TODO_cleanup_cfg if any
 212    paths where split, otherwise return zero.  */
 213
 214 static unsigned int
 215 execute_split_paths ()
 216 {
 217   /* If we don't have at least 2 real blocks and backedges in the
 218      CFG, then there's no point in trying to perform path splitting.  */
 219   if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
 220       || !mark_dfs_back_edges ())
 221     return 0;
 222
 223   bool changed = split_paths();
 224   if (changed)
 225     free_dominance_info (CDI_DOMINATORS);
 226
 227   return changed ? TODO_cleanup_cfg : 0;
 228 }
 229
 230 static bool
 231 gate_split_paths ()
 232 {
 233   return flag_split_paths;
 234 }
 235
 236 namespace {
 237
 238 const pass_data pass_data_split_paths =
 239 {
 240   GIMPLE_PASS, /* type */
 241   "split-paths", /* name */
 242   OPTGROUP_NONE, /* optinfo_flags */
 243   TV_SPLIT_PATHS, /* tv_id */
 244   PROP_ssa, /* properties_required */
 245   0, /* properties_provided */
 246   0, /* properties_destroyed */
 247   0, /* todo_flags_start */
 248   TODO_update_ssa, /* todo_flags_finish */
 249 };
 250
 251 class pass_split_paths : public gimple_opt_pass
 252 {
 253    public:
 254     pass_split_paths (gcc::context *ctxt)
 255       : gimple_opt_pass (pass_data_split_paths, ctxt)
 256     {}
 257    /* opt_pass methods: */
 258    opt_pass * clone () { return new pass_split_paths (m_ctxt); }
 259    virtual bool gate (function *) { return gate_split_paths (); }
 260    virtual unsigned int execute (function *) { return execute_split_paths (); }
 261
 262 }; // class pass_split_paths
 263
 264 } // anon namespace
 265
 266 gimple_opt_pass *
 267 make_pass_split_paths (gcc::context *ctxt)
 268 {
 269   return new pass_split_paths (ctxt);
 270 }