gcc/gimple-ssa-split-paths.c

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