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 protected:
 169   /* ch_base method: */
 170   virtual bool process_loop_p (struct loop *loop);
 171 }; // class pass_ch
 172
 173 const pass_data pass_data_ch_vect =
 174 {
 175   GIMPLE_PASS, /* type */
 176   "ch_vect", /* name */
 177   OPTGROUP_LOOP, /* optinfo_flags */
 178   TV_TREE_CH, /* tv_id */
 179   ( PROP_cfg | PROP_ssa ), /* properties_required */
 180   0, /* properties_provided */
 181   0, /* properties_destroyed */
 182   0, /* todo_flags_start */
 183   0, /* todo_flags_finish */
 184 };
 185
 186 /* This is a more aggressive version of the same pass, designed to run just
 187    before if-conversion and vectorization, to put more loops into the form
 188    required for those phases.  */
 189 class pass_ch_vect : public ch_base
 190 {
 191 public:
 192   pass_ch_vect (gcc::context *ctxt)
 193     : ch_base (pass_data_ch_vect, ctxt)
 194   {}
 195
 196   /* opt_pass methods: */
 197   virtual bool gate (function *fun)
 198   {
 199     return flag_tree_ch != 0
 200            && (flag_tree_loop_vectorize != 0 || fun->has_force_vectorize_loops);
 201   }
 202
 203   /* Just copy headers, no initialization/finalization of loop structures.  */
 204   virtual unsigned int execute (function *);
 205
 206 protected:
 207   /* ch_base method: */
 208   virtual bool process_loop_p (struct loop *loop);
 209 }; // class pass_ch_vect
 210
 211 /* For all loops, copy the condition at the end of the loop body in front
 212    of the loop.  This is beneficial since it increases efficiency of
 213    code motion optimizations.  It also saves one jump on entry to the loop.  */
 214
 215 unsigned int
 216 ch_base::copy_headers (function *fun)
 217 {
 218   struct loop *loop;
 219   basic_block header;
 220   edge exit, entry;
 221   basic_block *bbs, *copied_bbs;
 222   unsigned n_bbs;
 223   unsigned bbs_size;
 224   bool changed = false;
 225
 226   if (number_of_loops (fun) <= 1)
 227       return 0;
 228
 229   bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
 230   copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
 231   bbs_size = n_basic_blocks_for_fn (fun);
 232
 233   FOR_EACH_LOOP (loop, 0)
 234     {
 235       /* Copy at most 20 insns.  */
 236       int limit = 20;
 237
 238       header = loop->header;
 239
 240       /* If the loop is already a do-while style one (either because it was
 241          written as such, or because jump threading transformed it into one),
 242          we might be in fact peeling the first iteration of the loop.  This
 243          in general is not a good idea.  */
 244       if (!process_loop_p (loop))
 245         continue;
 246
 247       /* Iterate the header copying up to limit; this takes care of the cases
 248          like while (a && b) {...}, where we want to have both of the conditions
 249          copied.  TODO -- handle while (a || b) - like cases, by not requiring
 250          the header to have just a single successor and copying up to
 251          postdominator.  */
 252
 253       exit = NULL;
 254       n_bbs = 0;
 255       while (should_duplicate_loop_header_p (header, loop, &limit))
 256         {
 257           /* Find a successor of header that is inside a loop; i.e. the new
 258              header after the condition is copied.  */
 259           if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
 260             exit = EDGE_SUCC (header, 0);
 261           else
 262             exit = EDGE_SUCC (header, 1);
 263           bbs[n_bbs++] = header;
 264           gcc_assert (bbs_size > n_bbs);
 265           header = exit->dest;
 266         }
 267
 268       if (!exit)
 269         continue;
 270
 271       if (dump_file && (dump_flags & TDF_DETAILS))
 272         fprintf (dump_file,
 273                  "Duplicating header of the loop %d up to edge %d->%d.\n",
 274                  loop->num, exit->src->index, exit->dest->index);
 275
 276       /* Ensure that the header will have just the latch as a predecessor
 277          inside the loop.  */
 278       if (!single_pred_p (exit->dest))
 279         exit = single_pred_edge (split_edge (exit));
 280
 281       entry = loop_preheader_edge (loop);
 282
 283       propagate_threaded_block_debug_into (exit->dest, entry->dest);
 284       if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs,
 285                                          true))
 286         {
 287           fprintf (dump_file, "Duplication failed.\n");
 288           continue;
 289         }
 290
 291       /* If the loop has the form "for (i = j; i < j + 10; i++)" then
 292          this copying can introduce a case where we rely on undefined
 293          signed overflow to eliminate the preheader condition, because
 294          we assume that "j < j + 10" is true.  We don't want to warn
 295          about that case for -Wstrict-overflow, because in general we
 296          don't warn about overflow involving loops.  Prevent the
 297          warning by setting the no_warning flag in the condition.  */
 298       if (warn_strict_overflow > 0)
 299         {
 300           unsigned int i;
 301
 302           for (i = 0; i < n_bbs; ++i)
 303             {
 304               gimple_stmt_iterator bsi;
 305
 306               for (bsi = gsi_start_bb (copied_bbs[i]);
 307                    !gsi_end_p (bsi);
 308                    gsi_next (&bsi))
 309                 {
 310                   gimple *stmt = gsi_stmt (bsi);
 311                   if (gimple_code (stmt) == GIMPLE_COND)
 312                     gimple_set_no_warning (stmt, true);
 313                   else if (is_gimple_assign (stmt))
 314                     {
 315                       enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
 316                       if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
 317                         gimple_set_no_warning (stmt, true);
 318                     }
 319                 }
 320             }
 321         }
 322
 323       /* Ensure that the latch and the preheader is simple (we know that they
 324          are not now, since there was the loop exit condition.  */
 325       split_edge (loop_preheader_edge (loop));
 326       split_edge (loop_latch_edge (loop));
 327
 328       changed = true;
 329     }
 330
 331   if (changed)
 332     update_ssa (TODO_update_ssa);
 333   free (bbs);
 334   free (copied_bbs);
 335
 336   return changed ? TODO_cleanup_cfg : 0;
 337 }
 338
 339 /* Initialize the loop structures we need, and finalize after.  */
 340
 341 unsigned int
 342 pass_ch::execute (function *fun)
 343 {
 344   loop_optimizer_init (LOOPS_HAVE_PREHEADERS
 345                        | LOOPS_HAVE_SIMPLE_LATCHES);
 346
 347   unsigned int res = copy_headers (fun);
 348
 349   loop_optimizer_finalize ();
 350   return res;
 351 }
 352
 353 /* Assume an earlier phase has already initialized all the loop structures that
 354    we need here (and perhaps others too), and that these will be finalized by
 355    a later phase.  */
 356
 357 unsigned int
 358 pass_ch_vect::execute (function *fun)
 359 {
 360   return copy_headers (fun);
 361 }
 362
 363 /* Apply header copying according to a very simple test of do-while shape.  */
 364
 365 bool
 366 pass_ch::process_loop_p (struct loop *loop)
 367 {
 368   return !do_while_loop_p (loop);
 369 }
 370
 371 /* Apply header-copying to loops where we might enable vectorization.  */
 372
 373 bool
 374 pass_ch_vect::process_loop_p (struct loop *loop)
 375 {
 376   if (!flag_tree_vectorize && !loop->force_vectorize)
 377     return false;
 378
 379   if (loop->dont_vectorize)
 380     return false;
 381
 382   if (!do_while_loop_p (loop))
 383     return true;
 384
 385  /* The vectorizer won't handle anything with multiple exits, so skip.  */
 386   edge exit = single_exit (loop);
 387   if (!exit)
 388     return false;
 389
 390   /* Copy headers iff there looks to be code in the loop after the exit block,
 391      i.e. the exit block has an edge to another block (besides the latch,
 392      which should be empty).  */
 393   edge_iterator ei;
 394   edge e;
 395   FOR_EACH_EDGE (e, ei, exit->src->succs)
 396     if (!loop_exit_edge_p (loop, e)
 397         && e->dest != loop->header
 398         && e->dest != loop->latch)
 399       return true;
 400
 401   return false;
 402 }
 403
 404 } // anon namespace
 405
 406 gimple_opt_pass *
 407 make_pass_ch_vect (gcc::context *ctxt)
 408 {
 409   return new pass_ch_vect (ctxt);
 410 }
 411
 412 gimple_opt_pass *
 413 make_pass_ch (gcc::context *ctxt)
 414 {
 415   return new pass_ch (ctxt);
 416 }