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 "tree-cfg.h"
  29 #include "cfganal.h"
  30 #include "cfgloop.h"
  31 #include "gimple-iterator.h"
  32 #include "tracer.h"
  33 #include "predict.h"
  34 #include "params.h"
  35
  36 /* Given LATCH, the latch block in a loop, see if the shape of the
  37    path reaching LATCH is suitable for being split by duplication.
  38    If so, return the block that will be duplicated into its predecessor
  39    paths.  Else return NULL.  */
  40
  41 static basic_block
  42 find_block_to_duplicate_for_splitting_paths (basic_block latch)
  43 {
  44   /* We should have simple latches at this point.  So the latch should
  45      have a single successor.  This implies the predecessor of the latch
  46      likely has the loop exit.  And it's that predecessor we're most
  47      interested in. To keep things simple, we're going to require that
  48      the latch have a single predecessor too.  */
  49   if (single_succ_p (latch) && single_pred_p (latch))
  50     {
  51       basic_block bb = get_immediate_dominator (CDI_DOMINATORS, latch);
  52       gcc_assert (single_pred_edge (latch)->src == bb);
  53
  54       /* If BB has been marked as not to be duplicated, then honor that
  55          request.  */
  56       if (ignore_bb_p (bb))
  57         return NULL;
  58
  59       gimple *last = gsi_stmt (gsi_last_nondebug_bb (bb));
  60       /* The immediate dominator of the latch must end in a conditional.  */
  61       if (!last || gimple_code (last) != GIMPLE_COND)
  62         return NULL;
  63
  64       /* We're hoping that BB is a join point for an IF-THEN-ELSE diamond
  65          region.  Verify that it is.
  66
  67          First, verify that BB has two predecessors (each arm of the
  68          IF-THEN-ELSE) and two successors (the latch and exit).  */
  69       if (EDGE_COUNT (bb->preds) == 2 && EDGE_COUNT (bb->succs) == 2)
  70         {
  71           /* Now verify that BB's immediate dominator ends in a
  72              conditional as well.  */
  73           basic_block bb_idom = get_immediate_dominator (CDI_DOMINATORS, bb);
  74           gimple *last = gsi_stmt (gsi_last_nondebug_bb (bb_idom));
  75           if (!last || gimple_code (last) != GIMPLE_COND)
  76             return NULL;
  77
  78           /* And that BB's immediate dominator's successors are the
  79              predecessors of BB.  */
  80           if (!find_edge (bb_idom, EDGE_PRED (bb, 0)->src)
  81               || !find_edge (bb_idom, EDGE_PRED (bb, 1)->src))
  82             return NULL;
  83
  84           /* And that the predecessors of BB each have a single successor.  */
  85           if (!single_succ_p (EDGE_PRED (bb, 0)->src)
  86               || !single_succ_p (EDGE_PRED (bb, 1)->src))
  87             return NULL;
  88
  89           /* So at this point we have a simple diamond for an IF-THEN-ELSE
  90              construct starting at BB_IDOM, with a join point at BB.  BB
  91              pass control outside the loop or to the loop latch.
  92
  93              We're going to want to create two duplicates of BB, one for
  94              each successor of BB_IDOM.  */
  95           return bb;
  96         }
  97     }
  98   return NULL;
  99 }
 100
 101 /* Return the number of non-debug statements in a block.  */
 102 static unsigned int
 103 count_stmts_in_block (basic_block bb)
 104 {
 105   gimple_stmt_iterator gsi;
 106   unsigned int num_stmts = 0;
 107
 108   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 109     {
 110       gimple *stmt = gsi_stmt (gsi);
 111       if (!is_gimple_debug (stmt))
 112         num_stmts++;
 113     }
 114   return num_stmts;
 115 }
 116
 117 /* Return TRUE if CODE represents a tree code that is not likely to
 118    be easily if-convertable because it likely expands into multiple
 119    insns, FALSE otherwise.  */
 120 static bool
 121 poor_ifcvt_candidate_code (enum tree_code code)
 122 {
 123   return (code == MIN_EXPR
 124           || code == MAX_EXPR
 125           || code == ABS_EXPR
 126           || code == COND_EXPR
 127           || code == CALL_EXPR);
 128 }
 129
 130 /* Return TRUE if BB is a reasonable block to duplicate by examining
 131    its size, false otherwise.  BB will always be a loop latch block.
 132
 133    Things to consider:
 134
 135      We do not want to spoil if-conversion if at all possible.
 136
 137      Most of the benefit seems to be from eliminating the unconditional
 138      jump rather than CSE/DCE opportunities.  So favor duplicating
 139      small latches.  A latch with just a conditional branch is ideal.
 140
 141      CSE/DCE opportunties crop up when statements from the predecessors
 142      feed statements in the latch and allow statements in the latch to
 143      simplify.  */
 144
 145 static bool
 146 is_feasible_trace (basic_block bb)
 147 {
 148   basic_block pred1 = EDGE_PRED (bb, 0)->src;
 149   basic_block pred2 = EDGE_PRED (bb, 1)->src;
 150   int num_stmts_in_join = count_stmts_in_block (bb);
 151   int num_stmts_in_pred1 = count_stmts_in_block (pred1);
 152   int num_stmts_in_pred2 = count_stmts_in_block (pred2);
 153
 154   /* This is meant to catch cases that are likely opportunities for
 155      if-conversion.  Essentially we look for the case where
 156      BB's predecessors are both single statement blocks where
 157      the output of that statement feed the same PHI in BB.  */
 158   if (num_stmts_in_pred1 == 1 && num_stmts_in_pred2 == 1)
 159     {
 160       gimple *stmt1 = last_and_only_stmt (pred1);
 161       gimple *stmt2 = last_and_only_stmt (pred2);
 162
 163       if (stmt1 && stmt2
 164           && gimple_code (stmt1) == GIMPLE_ASSIGN
 165           && gimple_code (stmt2) == GIMPLE_ASSIGN)
 166         {
 167           enum tree_code code1 = gimple_assign_rhs_code (stmt1);
 168           enum tree_code code2 = gimple_assign_rhs_code (stmt2);
 169
 170           if (!poor_ifcvt_candidate_code (code1)
 171               && !poor_ifcvt_candidate_code (code2))
 172             {
 173               tree lhs1 = gimple_assign_lhs (stmt1);
 174               tree lhs2 = gimple_assign_lhs (stmt2);
 175               gimple_stmt_iterator gsi;
 176               for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 177                 {
 178                   gimple *phi = gsi_stmt (gsi);
 179                   if ((gimple_phi_arg_def (phi, 0) == lhs1
 180                        && gimple_phi_arg_def (phi, 1) == lhs2)
 181                       || (gimple_phi_arg_def (phi, 1) == lhs1
 182                           && gimple_phi_arg_def (phi, 0) == lhs2))
 183                     {
 184                       if (dump_file && (dump_flags & TDF_DETAILS))
 185                         fprintf (dump_file,
 186                                  "Block %d appears to be a join point for "
 187                                  "if-convertable diamond.\n",
 188                                  bb->index);
 189                       return false;
 190                     }
 191                 }
 192             }
 193         }
 194     }
 195
 196   /* We may want something here which looks at dataflow and tries
 197      to guess if duplication of BB is likely to result in simplification
 198      of instructions in BB in either the original or the duplicate.  */
 199
 200   /* Upper Hard limit on the number statements to copy.  */
 201   if (num_stmts_in_join
 202       >= PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS))
 203     return false;
 204
 205   return true;
 206 }
 207
 208 /* If the immediate dominator of the latch of the loop is
 209    block with conditional branch, then the loop latch  is
 210    duplicated to its predecessors path preserving the SSA
 211    semantics.
 212
 213    CFG before transformation.
 214
 215               2
 216               |
 217               |
 218         +---->3
 219         |    / \
 220         |   /   \
 221         |  4     5
 222         |   \   /
 223         |    \ /
 224         |     6
 225         |    / \
 226         |   /   \
 227         |  8     7
 228         |  |     |
 229         ---+     E
 230
 231
 232
 233     Block 8 is the latch.  We're going to make copies of block 6 (9 & 10)
 234     and wire things up so they look like this:
 235
 236               2
 237               |
 238               |
 239         +---->3
 240         |    / \
 241         |   /   \
 242         |  4     5
 243         |  |     |
 244         |  |     |
 245         |  9    10
 246         |  |\   /|
 247         |  | \ / |
 248         |  |  7  |
 249         |  |  |  |
 250         |  |  E  |
 251         |  |     |
 252         |   \   /
 253         |    \ /
 254         +-----8
 255
 256
 257     Blocks 9 and 10 will get merged into blocks 4 & 5 respectively which
 258     enables CSE, DCE and other optimizations to occur on a larger block
 259     of code.   */
 260
 261 static bool
 262 split_paths ()
 263 {
 264   bool changed = false;
 265   loop_p loop;
 266
 267   loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
 268   initialize_original_copy_tables ();
 269   calculate_dominance_info (CDI_DOMINATORS);
 270
 271   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
 272     {
 273       /* Only split paths if we are optimizing this loop for speed.  */
 274       if (!optimize_loop_for_speed_p (loop))
 275         continue;
 276
 277       /* See if there is a block that we can duplicate to split the
 278          path to the loop latch.  */
 279       basic_block bb
 280         = find_block_to_duplicate_for_splitting_paths (loop->latch);
 281
 282       /* BB is the merge point for an IF-THEN-ELSE we want to transform.
 283
 284          Essentially we want to create a duplicate of bb and redirect the
 285          first predecessor of BB to the duplicate (leaving the second
 286          predecessor as is.  This will split the path leading to the latch
 287          re-using BB to avoid useless copying.  */
 288       if (bb && is_feasible_trace (bb))
 289         {
 290           if (dump_file && (dump_flags & TDF_DETAILS))
 291             fprintf (dump_file,
 292                      "Duplicating join block %d into predecessor paths\n",
 293                      bb->index);
 294           basic_block pred0 = EDGE_PRED (bb, 0)->src;
 295           transform_duplicate (pred0, bb);
 296           changed = true;
 297
 298           /* If BB has an outgoing edge marked as IRREDUCIBLE, then
 299              duplicating BB may result in an irreducible region turning
 300              into a natural loop.
 301
 302              Long term we might want to hook this into the block
 303              duplication code, but as we've seen with similar changes
 304              for edge removal, that can be somewhat risky.  */
 305           if (EDGE_SUCC (bb, 0)->flags & EDGE_IRREDUCIBLE_LOOP
 306               || EDGE_SUCC (bb, 1)->flags & EDGE_IRREDUCIBLE_LOOP)
 307             {
 308               if (dump_file && (dump_flags & TDF_DETAILS))
 309                   fprintf (dump_file,
 310                            "Join block %d has EDGE_IRREDUCIBLE_LOOP set.  "
 311                            "Scheduling loop fixups.\n",
 312                            bb->index);
 313               loops_state_set (LOOPS_NEED_FIXUP);
 314             }
 315         }
 316     }
 317
 318   loop_optimizer_finalize ();
 319   free_original_copy_tables ();
 320   return changed;
 321 }
 322
 323 /* Main entry point for splitting paths.  Returns TODO_cleanup_cfg if any
 324    paths where split, otherwise return zero.  */
 325
 326 static unsigned int
 327 execute_split_paths ()
 328 {
 329   /* If we don't have at least 2 real blocks and backedges in the
 330      CFG, then there's no point in trying to perform path splitting.  */
 331   if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
 332       || !mark_dfs_back_edges ())
 333     return 0;
 334
 335   bool changed = split_paths();
 336   if (changed)
 337     free_dominance_info (CDI_DOMINATORS);
 338
 339   return changed ? TODO_cleanup_cfg : 0;
 340 }
 341
 342 static bool
 343 gate_split_paths ()
 344 {
 345   return flag_split_paths;
 346 }
 347
 348 namespace {
 349
 350 const pass_data pass_data_split_paths =
 351 {
 352   GIMPLE_PASS, /* type */
 353   "split-paths", /* name */
 354   OPTGROUP_NONE, /* optinfo_flags */
 355   TV_SPLIT_PATHS, /* tv_id */
 356   PROP_ssa, /* properties_required */
 357   0, /* properties_provided */
 358   0, /* properties_destroyed */
 359   0, /* todo_flags_start */
 360   TODO_update_ssa, /* todo_flags_finish */
 361 };
 362
 363 class pass_split_paths : public gimple_opt_pass
 364 {
 365    public:
 366     pass_split_paths (gcc::context *ctxt)
 367       : gimple_opt_pass (pass_data_split_paths, ctxt)
 368     {}
 369    /* opt_pass methods: */
 370    opt_pass * clone () { return new pass_split_paths (m_ctxt); }
 371    virtual bool gate (function *) { return gate_split_paths (); }
 372    virtual unsigned int execute (function *) { return execute_split_paths (); }
 373
 374 }; // class pass_split_paths
 375
 376 } // anon namespace
 377
 378 gimple_opt_pass *
 379 make_pass_split_paths (gcc::context *ctxt)
 380 {
 381   return new pass_split_paths (ctxt);
 382 }