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