gcc/tree-ssa-loop-ch.c

   1 /* Loop header copying on trees.
   2    Copyright (C) 2004-2015 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 3, or (at your option) any
   9 later version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "backend.h"
  24 #include "tree.h"
  25 #include "gimple.h"
  26 #include "cfghooks.h"
  27 #include "tree-pass.h"
  28 #include "gimple-ssa.h"
  29 #include "gimple-iterator.h"
  30 #include "tree-cfg.h"
  31 #include "tree-into-ssa.h"
  32 #include "cfgloop.h"
  33 #include "tree-inline.h"
  34 #include "tree-ssa-scopedtables.h"
  35 #include "tree-ssa-threadedge.h"
  36
  37 /* Duplicates headers of loops if they are small enough, so that the statements
  38    in the loop body are always executed when the loop is entered.  This
  39    increases effectiveness of code motion optimizations, and reduces the need
  40    for loop preconditioning.  */
  41
  42 /* Check whether we should duplicate HEADER of LOOP.  At most *LIMIT
  43    instructions should be duplicated, limit is decreased by the actual
  44    amount.  */
  45
  46 static bool
  47 should_duplicate_loop_header_p (basic_block header, struct loop *loop,
  48                                 int *limit)
  49 {
  50   gimple_stmt_iterator bsi;
  51   gimple *last;
  52
  53   /* Do not copy one block more than once (we do not really want to do
  54      loop peeling here).  */
  55   if (header->aux)
  56     return false;
  57
  58   /* Loop header copying usually increases size of the code.  This used not to
  59      be true, since quite often it is possible to verify that the condition is
  60      satisfied in the first iteration and therefore to eliminate it.  Jump
  61      threading handles these cases now.  */
  62   if (optimize_loop_for_size_p (loop))
  63     return false;
  64
  65   gcc_assert (EDGE_COUNT (header->succs) > 0);
  66   if (single_succ_p (header))
  67     return false;
  68   if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
  69       && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
  70     return false;
  71
  72   /* If this is not the original loop header, we want it to have just
  73      one predecessor in order to match the && pattern.  */
  74   if (header != loop->header && !single_pred_p (header))
  75     return false;
  76
  77   last = last_stmt (header);
  78   if (gimple_code (last) != GIMPLE_COND)
  79     return false;
  80
  81   /* Approximately copy the conditions that used to be used in jump.c --
  82      at most 20 insns and no calls.  */
  83   for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi))
  84     {
  85       last = gsi_stmt (bsi);
  86
  87       if (gimple_code (last) == GIMPLE_LABEL)
  88         continue;
  89
  90       if (is_gimple_debug (last))
  91         continue;
  92
  93       if (is_gimple_call (last))
  94         return false;
  95
  96       *limit -= estimate_num_insns (last, &eni_size_weights);
  97       if (*limit < 0)
  98         return false;
  99     }
 100
 101   return true;
 102 }
 103
 104 /* Checks whether LOOP is a do-while style loop.  */
 105
 106 static bool
 107 do_while_loop_p (struct loop *loop)
 108 {
 109   gimple *stmt = last_stmt (loop->latch);
 110
 111   /* If the latch of the loop is not empty, it is not a do-while loop.  */
 112   if (stmt
 113       && gimple_code (stmt) != GIMPLE_LABEL)
 114     return false;
 115
 116   /* If the header contains just a condition, it is not a do-while loop.  */
 117   stmt = last_and_only_stmt (loop->header);
 118   if (stmt
 119       && gimple_code (stmt) == GIMPLE_COND)
 120     return false;
 121
 122   return true;
 123 }
 124
 125 namespace {
 126
 127 /* Common superclass for both header-copying phases.  */
 128 class ch_base : public gimple_opt_pass
 129 {
 130   protected:
 131     ch_base (pass_data data, gcc::context *ctxt)
 132       : gimple_opt_pass (data, ctxt)
 133     {}
 134
 135   /* Copies headers of all loops in FUN for which process_loop_p is true.  */
 136   unsigned int copy_headers (function *fun);
 137
 138   /* Return true to copy headers of LOOP or false to skip.  */
 139   virtual bool process_loop_p (struct loop *loop) = 0;
 140 };
 141
 142 const pass_data pass_data_ch =
 143 {
 144   GIMPLE_PASS, /* type */
 145   "ch", /* name */
 146   OPTGROUP_LOOP, /* optinfo_flags */
 147   TV_TREE_CH, /* tv_id */
 148   ( PROP_cfg | PROP_ssa ), /* properties_required */
 149   0, /* properties_provided */
 150   0, /* properties_destroyed */
 151   0, /* todo_flags_start */
 152   0, /* todo_flags_finish */
 153 };
 154
 155 class pass_ch : public ch_base
 156 {
 157 public:
 158   pass_ch (gcc::context *ctxt)
 159     : ch_base (pass_data_ch, ctxt)
 160   {}
 161
 162   /* opt_pass methods: */
 163   virtual bool gate (function *) { return flag_tree_ch != 0; }
 164
 165   /* Initialize and finalize loop structures, copying headers inbetween.  */
 166   virtual unsigned int execute (function *);
 167
 168   opt_pass * clone () { return new pass_ch (m_ctxt); }
 169
 170 protected:
 171   /* ch_base method: */
 172   virtual bool process_loop_p (struct loop *loop);
 173 }; // class pass_ch
 174
 175 const pass_data pass_data_ch_vect =
 176 {
 177   GIMPLE_PASS, /* type */
 178   "ch_vect", /* name */
 179   OPTGROUP_LOOP, /* optinfo_flags */
 180   TV_TREE_CH, /* tv_id */
 181   ( PROP_cfg | PROP_ssa ), /* properties_required */
 182   0, /* properties_provided */
 183   0, /* properties_destroyed */
 184   0, /* todo_flags_start */
 185   0, /* todo_flags_finish */
 186 };
 187
 188 /* This is a more aggressive version of the same pass, designed to run just
 189    before if-conversion and vectorization, to put more loops into the form
 190    required for those phases.  */
 191 class pass_ch_vect : public ch_base
 192 {
 193 public:
 194   pass_ch_vect (gcc::context *ctxt)
 195     : ch_base (pass_data_ch_vect, ctxt)
 196   {}
 197
 198   /* opt_pass methods: */
 199   virtual bool gate (function *fun)
 200   {
 201     return flag_tree_ch != 0
 202            && (flag_tree_loop_vectorize != 0 || fun->has_force_vectorize_loops);
 203   }
 204
 205   /* Just copy headers, no initialization/finalization of loop structures.  */
 206   virtual unsigned int execute (function *);
 207
 208 protected:
 209   /* ch_base method: */
 210   virtual bool process_loop_p (struct loop *loop);
 211 }; // class pass_ch_vect
 212
 213 /* For all loops, copy the condition at the end of the loop body in front
 214    of the loop.  This is beneficial since it increases efficiency of
 215    code motion optimizations.  It also saves one jump on entry to the loop.  */
 216
 217 unsigned int
 218 ch_base::copy_headers (function *fun)
 219 {
 220   struct loop *loop;
 221   basic_block header;
 222   edge exit, entry;
 223   basic_block *bbs, *copied_bbs;
 224   unsigned n_bbs;
 225   unsigned bbs_size;
 226   bool changed = false;
 227
 228   if (number_of_loops (fun) <= 1)
 229       return 0;
 230
 231   bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
 232   copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
 233   bbs_size = n_basic_blocks_for_fn (fun);
 234
 235   FOR_EACH_LOOP (loop, 0)
 236     {
 237       /* Copy at most 20 insns.  */
 238       int limit = 20;
 239
 240       header = loop->header;
 241
 242       /* If the loop is already a do-while style one (either because it was
 243          written as such, or because jump threading transformed it into one),
 244          we might be in fact peeling the first iteration of the loop.  This
 245          in general is not a good idea.  */
 246       if (!process_loop_p (loop))
 247         continue;
 248
 249       /* Iterate the header copying up to limit; this takes care of the cases
 250          like while (a && b) {...}, where we want to have both of the conditions
 251          copied.  TODO -- handle while (a || b) - like cases, by not requiring
 252          the header to have just a single successor and copying up to
 253          postdominator.  */
 254
 255       exit = NULL;
 256       n_bbs = 0;
 257       while (should_duplicate_loop_header_p (header, loop, &limit))
 258         {
 259           /* Find a successor of header that is inside a loop; i.e. the new
 260              header after the condition is copied.  */
 261           if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
 262             exit = EDGE_SUCC (header, 0);
 263           else
 264             exit = EDGE_SUCC (header, 1);
 265           bbs[n_bbs++] = header;
 266           gcc_assert (bbs_size > n_bbs);
 267           header = exit->dest;
 268         }
 269
 270       if (!exit)
 271         continue;
 272
 273       if (dump_file && (dump_flags & TDF_DETAILS))
 274         fprintf (dump_file,
 275                  "Duplicating header of the loop %d up to edge %d->%d.\n",
 276                  loop->num, exit->src->index, exit->dest->index);
 277
 278       /* Ensure that the header will have just the latch as a predecessor
 279          inside the loop.  */
 280       if (!single_pred_p (exit->dest))
 281         exit = single_pred_edge (split_edge (exit));
 282
 283       entry = loop_preheader_edge (loop);
 284
 285       propagate_threaded_block_debug_into (exit->dest, entry->dest);
 286       if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs,
 287                                          true))
 288         {
 289           fprintf (dump_file, "Duplication failed.\n");
 290           continue;
 291         }
 292
 293       /* If the loop has the form "for (i = j; i < j + 10; i++)" then
 294          this copying can introduce a case where we rely on undefined
 295          signed overflow to eliminate the preheader condition, because
 296          we assume that "j < j + 10" is true.  We don't want to warn
 297          about that case for -Wstrict-overflow, because in general we
 298          don't warn about overflow involving loops.  Prevent the
 299          warning by setting the no_warning flag in the condition.  */
 300       if (warn_strict_overflow > 0)
 301         {
 302           unsigned int i;
 303
 304           for (i = 0; i < n_bbs; ++i)
 305             {
 306               gimple_stmt_iterator bsi;
 307
 308               for (bsi = gsi_start_bb (copied_bbs[i]);
 309                    !gsi_end_p (bsi);
 310                    gsi_next (&bsi))
 311                 {
 312                   gimple *stmt = gsi_stmt (bsi);
 313                   if (gimple_code (stmt) == GIMPLE_COND)
 314                     gimple_set_no_warning (stmt, true);
 315                   else if (is_gimple_assign (stmt))
 316                     {
 317                       enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
 318                       if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
 319                         gimple_set_no_warning (stmt, true);
 320                     }
 321                 }
 322             }
 323         }
 324
 325       /* Ensure that the latch and the preheader is simple (we know that they
 326          are not now, since there was the loop exit condition.  */
 327       split_edge (loop_preheader_edge (loop));
 328       split_edge (loop_latch_edge (loop));
 329
 330       changed = true;
 331     }
 332
 333   if (changed)
 334     update_ssa (TODO_update_ssa);
 335   free (bbs);
 336   free (copied_bbs);
 337
 338   return changed ? TODO_cleanup_cfg : 0;
 339 }
 340
 341 /* Initialize the loop structures we need, and finalize after.  */
 342
 343 unsigned int
 344 pass_ch::execute (function *fun)
 345 {
 346   loop_optimizer_init (LOOPS_HAVE_PREHEADERS
 347                        | LOOPS_HAVE_SIMPLE_LATCHES);
 348
 349   unsigned int res = copy_headers (fun);
 350
 351   loop_optimizer_finalize ();
 352   return res;
 353 }
 354
 355 /* Assume an earlier phase has already initialized all the loop structures that
 356    we need here (and perhaps others too), and that these will be finalized by
 357    a later phase.  */
 358
 359 unsigned int
 360 pass_ch_vect::execute (function *fun)
 361 {
 362   return copy_headers (fun);
 363 }
 364
 365 /* Apply header copying according to a very simple test of do-while shape.  */
 366
 367 bool
 368 pass_ch::process_loop_p (struct loop *loop)
 369 {
 370   return !do_while_loop_p (loop);
 371 }
 372
 373 /* Apply header-copying to loops where we might enable vectorization.  */
 374
 375 bool
 376 pass_ch_vect::process_loop_p (struct loop *loop)
 377 {
 378   if (!flag_tree_vectorize && !loop->force_vectorize)
 379     return false;
 380
 381   if (loop->dont_vectorize)
 382     return false;
 383
 384   if (!do_while_loop_p (loop))
 385     return true;
 386
 387  /* The vectorizer won't handle anything with multiple exits, so skip.  */
 388   edge exit = single_exit (loop);
 389   if (!exit)
 390     return false;
 391
 392   /* Copy headers iff there looks to be code in the loop after the exit block,
 393      i.e. the exit block has an edge to another block (besides the latch,
 394      which should be empty).  */
 395   edge_iterator ei;
 396   edge e;
 397   FOR_EACH_EDGE (e, ei, exit->src->succs)
 398     if (!loop_exit_edge_p (loop, e)
 399         && e->dest != loop->header
 400         && e->dest != loop->latch)
 401       return true;
 402
 403   return false;
 404 }
 405
 406 } // anon namespace
 407
 408 gimple_opt_pass *
 409 make_pass_ch_vect (gcc::context *ctxt)
 410 {
 411   return new pass_ch_vect (ctxt);
 412 }
 413
 414 gimple_opt_pass *
 415 make_pass_ch (gcc::context *ctxt)
 416 {
 417   return new pass_ch (ctxt);
 418 }