contrib/gcc-8.0/gcc/tree-ssa-loop-ch.c

   1 /* Loop header copying on trees.
   2    Copyright (C) 2004-2018 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 #include "params.h"
  37
  38 /* Duplicates headers of loops if they are small enough, so that the statements
  39    in the loop body are always executed when the loop is entered.  This
  40    increases effectiveness of code motion optimizations, and reduces the need
  41    for loop preconditioning.  */
  42
  43 /* Check whether we should duplicate HEADER of LOOP.  At most *LIMIT
  44    instructions should be duplicated, limit is decreased by the actual
  45    amount.  */
  46
  47 static bool
  48 should_duplicate_loop_header_p (basic_block header, struct loop *loop,
  49                                 int *limit)
  50 {
  51   gimple_stmt_iterator bsi;
  52   gimple *last;
  53
  54   gcc_assert (!header->aux);
  55
  56   /* Loop header copying usually increases size of the code.  This used not to
  57      be true, since quite often it is possible to verify that the condition is
  58      satisfied in the first iteration and therefore to eliminate it.  Jump
  59      threading handles these cases now.  */
  60   if (optimize_loop_for_size_p (loop)
  61       && !loop->force_vectorize)
  62     {
  63       if (dump_file && (dump_flags & TDF_DETAILS))
  64         fprintf (dump_file,
  65                  "  Not duplicating bb %i: optimizing for size.\n",
  66                  header->index);
  67       return false;
  68     }
  69
  70   gcc_assert (EDGE_COUNT (header->succs) > 0);
  71   if (single_succ_p (header))
  72     {
  73       if (dump_file && (dump_flags & TDF_DETAILS))
  74         fprintf (dump_file,
  75                  "  Not duplicating bb %i: it is single succ.\n",
  76                  header->index);
  77       return false;
  78     }
  79
  80   if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
  81       && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
  82     {
  83       if (dump_file && (dump_flags & TDF_DETAILS))
  84         fprintf (dump_file,
  85                  "  Not duplicating bb %i: both sucessors are in loop.\n",
  86                  loop->num);
  87       return false;
  88     }
  89
  90   /* If this is not the original loop header, we want it to have just
  91      one predecessor in order to match the && pattern.  */
  92   if (header != loop->header && !single_pred_p (header))
  93     {
  94       if (dump_file && (dump_flags & TDF_DETAILS))
  95         fprintf (dump_file,
  96                  "  Not duplicating bb %i: it has mutiple predecestors.\n",
  97                  header->index);
  98       return false;
  99     }
 100
 101   last = last_stmt (header);
 102   if (gimple_code (last) != GIMPLE_COND)
 103     {
 104       if (dump_file && (dump_flags & TDF_DETAILS))
 105         fprintf (dump_file,
 106                  "  Not duplicating bb %i: it does not end by conditional.\n",
 107                  header->index);
 108       return false;
 109     }
 110
 111   /* Count number of instructions and punt on calls.  */
 112   for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi))
 113     {
 114       last = gsi_stmt (bsi);
 115
 116       if (gimple_code (last) == GIMPLE_LABEL)
 117         continue;
 118
 119       if (is_gimple_debug (last))
 120         continue;
 121
 122       if (gimple_code (last) == GIMPLE_CALL
 123           && (!gimple_inexpensive_call_p (as_a <gcall *> (last))
 124               /* IFN_LOOP_DIST_ALIAS means that inner loop is distributed
 125                  at current loop's header.  Don't copy in this case.  */
 126               || gimple_call_internal_p (last, IFN_LOOP_DIST_ALIAS)))
 127         {
 128           if (dump_file && (dump_flags & TDF_DETAILS))
 129             fprintf (dump_file,
 130                      "  Not duplicating bb %i: it contains call.\n",
 131                      header->index);
 132           return false;
 133         }
 134
 135       *limit -= estimate_num_insns (last, &eni_size_weights);
 136       if (*limit < 0)
 137         {
 138           if (dump_file && (dump_flags & TDF_DETAILS))
 139             fprintf (dump_file,
 140                      "  Not duplicating bb %i contains too many insns.\n",
 141                      header->index);
 142           return false;
 143         }
 144     }
 145   if (dump_file && (dump_flags & TDF_DETAILS))
 146     fprintf (dump_file, "    Will duplicate bb %i\n", header->index);
 147   return true;
 148 }
 149
 150 /* Checks whether LOOP is a do-while style loop.  */
 151
 152 static bool
 153 do_while_loop_p (struct loop *loop)
 154 {
 155   gimple *stmt = last_stmt (loop->latch);
 156
 157   /* If the latch of the loop is not empty, it is not a do-while loop.  */
 158   if (stmt
 159       && gimple_code (stmt) != GIMPLE_LABEL)
 160     {
 161       if (dump_file && (dump_flags & TDF_DETAILS))
 162         fprintf (dump_file,
 163                  "Loop %i is not do-while loop: latch is not empty.\n",
 164                  loop->num);
 165       return false;
 166     }
 167
 168   /* If the header contains just a condition, it is not a do-while loop.  */
 169   stmt = last_and_only_stmt (loop->header);
 170   if (stmt
 171       && gimple_code (stmt) == GIMPLE_COND)
 172     {
 173       if (dump_file && (dump_flags & TDF_DETAILS))
 174         fprintf (dump_file,
 175                  "Loop %i is not do-while loop: "
 176                  "header contains just condition.\n", loop->num);
 177       return false;
 178     }
 179   if (dump_file && (dump_flags & TDF_DETAILS))
 180     fprintf (dump_file, "Loop %i is do-while loop\n", loop->num);
 181
 182   return true;
 183 }
 184
 185 namespace {
 186
 187 /* Common superclass for both header-copying phases.  */
 188 class ch_base : public gimple_opt_pass
 189 {
 190   protected:
 191     ch_base (pass_data data, gcc::context *ctxt)
 192       : gimple_opt_pass (data, ctxt)
 193     {}
 194
 195   /* Copies headers of all loops in FUN for which process_loop_p is true.  */
 196   unsigned int copy_headers (function *fun);
 197
 198   /* Return true to copy headers of LOOP or false to skip.  */
 199   virtual bool process_loop_p (struct loop *loop) = 0;
 200 };
 201
 202 const pass_data pass_data_ch =
 203 {
 204   GIMPLE_PASS, /* type */
 205   "ch", /* name */
 206   OPTGROUP_LOOP, /* optinfo_flags */
 207   TV_TREE_CH, /* tv_id */
 208   ( PROP_cfg | PROP_ssa ), /* properties_required */
 209   0, /* properties_provided */
 210   0, /* properties_destroyed */
 211   0, /* todo_flags_start */
 212   0, /* todo_flags_finish */
 213 };
 214
 215 class pass_ch : public ch_base
 216 {
 217 public:
 218   pass_ch (gcc::context *ctxt)
 219     : ch_base (pass_data_ch, ctxt)
 220   {}
 221
 222   /* opt_pass methods: */
 223   virtual bool gate (function *) { return flag_tree_ch != 0; }
 224
 225   /* Initialize and finalize loop structures, copying headers inbetween.  */
 226   virtual unsigned int execute (function *);
 227
 228   opt_pass * clone () { return new pass_ch (m_ctxt); }
 229
 230 protected:
 231   /* ch_base method: */
 232   virtual bool process_loop_p (struct loop *loop);
 233 }; // class pass_ch
 234
 235 const pass_data pass_data_ch_vect =
 236 {
 237   GIMPLE_PASS, /* type */
 238   "ch_vect", /* name */
 239   OPTGROUP_LOOP, /* optinfo_flags */
 240   TV_TREE_CH, /* tv_id */
 241   ( PROP_cfg | PROP_ssa ), /* properties_required */
 242   0, /* properties_provided */
 243   0, /* properties_destroyed */
 244   0, /* todo_flags_start */
 245   0, /* todo_flags_finish */
 246 };
 247
 248 /* This is a more aggressive version of the same pass, designed to run just
 249    before if-conversion and vectorization, to put more loops into the form
 250    required for those phases.  */
 251 class pass_ch_vect : public ch_base
 252 {
 253 public:
 254   pass_ch_vect (gcc::context *ctxt)
 255     : ch_base (pass_data_ch_vect, ctxt)
 256   {}
 257
 258   /* opt_pass methods: */
 259   virtual bool gate (function *fun)
 260   {
 261     return flag_tree_ch != 0
 262            && (flag_tree_loop_vectorize != 0 || fun->has_force_vectorize_loops);
 263   }
 264
 265   /* Just copy headers, no initialization/finalization of loop structures.  */
 266   virtual unsigned int execute (function *);
 267
 268 protected:
 269   /* ch_base method: */
 270   virtual bool process_loop_p (struct loop *loop);
 271 }; // class pass_ch_vect
 272
 273 /* For all loops, copy the condition at the end of the loop body in front
 274    of the loop.  This is beneficial since it increases efficiency of
 275    code motion optimizations.  It also saves one jump on entry to the loop.  */
 276
 277 unsigned int
 278 ch_base::copy_headers (function *fun)
 279 {
 280   struct loop *loop;
 281   basic_block header;
 282   edge exit, entry;
 283   basic_block *bbs, *copied_bbs;
 284   unsigned n_bbs;
 285   unsigned bbs_size;
 286   bool changed = false;
 287
 288   if (number_of_loops (fun) <= 1)
 289       return 0;
 290
 291   bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
 292   copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
 293   bbs_size = n_basic_blocks_for_fn (fun);
 294
 295   FOR_EACH_LOOP (loop, 0)
 296     {
 297       int initial_limit = PARAM_VALUE (PARAM_MAX_LOOP_HEADER_INSNS);
 298       int remaining_limit = initial_limit;
 299       if (dump_file && (dump_flags & TDF_DETAILS))
 300         fprintf (dump_file,
 301                  "Analyzing loop %i\n", loop->num);
 302
 303       header = loop->header;
 304
 305       /* If the loop is already a do-while style one (either because it was
 306          written as such, or because jump threading transformed it into one),
 307          we might be in fact peeling the first iteration of the loop.  This
 308          in general is not a good idea.  */
 309       if (!process_loop_p (loop))
 310         continue;
 311
 312       /* Iterate the header copying up to limit; this takes care of the cases
 313          like while (a && b) {...}, where we want to have both of the conditions
 314          copied.  TODO -- handle while (a || b) - like cases, by not requiring
 315          the header to have just a single successor and copying up to
 316          postdominator.  */
 317
 318       exit = NULL;
 319       n_bbs = 0;
 320       while (should_duplicate_loop_header_p (header, loop, &remaining_limit))
 321         {
 322           /* Find a successor of header that is inside a loop; i.e. the new
 323              header after the condition is copied.  */
 324           if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
 325             exit = EDGE_SUCC (header, 0);
 326           else
 327             exit = EDGE_SUCC (header, 1);
 328           bbs[n_bbs++] = header;
 329           gcc_assert (bbs_size > n_bbs);
 330           header = exit->dest;
 331         }
 332
 333       if (!exit)
 334         continue;
 335
 336       if (dump_file && (dump_flags & TDF_DETAILS))
 337         fprintf (dump_file,
 338                  "Duplicating header of the loop %d up to edge %d->%d,"
 339                  " %i insns.\n",
 340                  loop->num, exit->src->index, exit->dest->index,
 341                  initial_limit - remaining_limit);
 342
 343       /* Ensure that the header will have just the latch as a predecessor
 344          inside the loop.  */
 345       if (!single_pred_p (exit->dest))
 346         exit = single_pred_edge (split_edge (exit));
 347
 348       entry = loop_preheader_edge (loop);
 349
 350       propagate_threaded_block_debug_into (exit->dest, entry->dest);
 351       if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs,
 352                                          true))
 353         {
 354           fprintf (dump_file, "Duplication failed.\n");
 355           continue;
 356         }
 357
 358       /* If the loop has the form "for (i = j; i < j + 10; i++)" then
 359          this copying can introduce a case where we rely on undefined
 360          signed overflow to eliminate the preheader condition, because
 361          we assume that "j < j + 10" is true.  We don't want to warn
 362          about that case for -Wstrict-overflow, because in general we
 363          don't warn about overflow involving loops.  Prevent the
 364          warning by setting the no_warning flag in the condition.  */
 365       if (warn_strict_overflow > 0)
 366         {
 367           unsigned int i;
 368
 369           for (i = 0; i < n_bbs; ++i)
 370             {
 371               gimple_stmt_iterator bsi;
 372
 373               for (bsi = gsi_start_bb (copied_bbs[i]);
 374                    !gsi_end_p (bsi);
 375                    gsi_next (&bsi))
 376                 {
 377                   gimple *stmt = gsi_stmt (bsi);
 378                   if (gimple_code (stmt) == GIMPLE_COND)
 379                     gimple_set_no_warning (stmt, true);
 380                   else if (is_gimple_assign (stmt))
 381                     {
 382                       enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
 383                       if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
 384                         gimple_set_no_warning (stmt, true);
 385                     }
 386                 }
 387             }
 388         }
 389
 390       /* Ensure that the latch and the preheader is simple (we know that they
 391          are not now, since there was the loop exit condition.  */
 392       split_edge (loop_preheader_edge (loop));
 393       split_edge (loop_latch_edge (loop));
 394
 395       changed = true;
 396     }
 397
 398   if (changed)
 399     update_ssa (TODO_update_ssa);
 400   free (bbs);
 401   free (copied_bbs);
 402
 403   return changed ? TODO_cleanup_cfg : 0;
 404 }
 405
 406 /* Initialize the loop structures we need, and finalize after.  */
 407
 408 unsigned int
 409 pass_ch::execute (function *fun)
 410 {
 411   loop_optimizer_init (LOOPS_HAVE_PREHEADERS
 412                        | LOOPS_HAVE_SIMPLE_LATCHES);
 413
 414   unsigned int res = copy_headers (fun);
 415
 416   loop_optimizer_finalize ();
 417   return res;
 418 }
 419
 420 /* Assume an earlier phase has already initialized all the loop structures that
 421    we need here (and perhaps others too), and that these will be finalized by
 422    a later phase.  */
 423
 424 unsigned int
 425 pass_ch_vect::execute (function *fun)
 426 {
 427   return copy_headers (fun);
 428 }
 429
 430 /* Apply header copying according to a very simple test of do-while shape.  */
 431
 432 bool
 433 pass_ch::process_loop_p (struct loop *loop)
 434 {
 435   return !do_while_loop_p (loop);
 436 }
 437
 438 /* Apply header-copying to loops where we might enable vectorization.  */
 439
 440 bool
 441 pass_ch_vect::process_loop_p (struct loop *loop)
 442 {
 443   if (!flag_tree_loop_vectorize && !loop->force_vectorize)
 444     return false;
 445
 446   if (loop->dont_vectorize)
 447     return false;
 448
 449   if (!do_while_loop_p (loop))
 450     return true;
 451
 452  /* The vectorizer won't handle anything with multiple exits, so skip.  */
 453   edge exit = single_exit (loop);
 454   if (!exit)
 455     return false;
 456
 457   /* Copy headers iff there looks to be code in the loop after the exit block,
 458      i.e. the exit block has an edge to another block (besides the latch,
 459      which should be empty).  */
 460   edge_iterator ei;
 461   edge e;
 462   FOR_EACH_EDGE (e, ei, exit->src->succs)
 463     if (!loop_exit_edge_p (loop, e)
 464         && e->dest != loop->header
 465         && e->dest != loop->latch)
 466       return true;
 467
 468   return false;
 469 }
 470
 471 } // anon namespace
 472
 473 gimple_opt_pass *
 474 make_pass_ch_vect (gcc::context *ctxt)
 475 {
 476   return new pass_ch_vect (ctxt);
 477 }
 478
 479 gimple_opt_pass *
 480 make_pass_ch (gcc::context *ctxt)
 481 {
 482   return new pass_ch (ctxt);
 483 }