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