gcc/tree-ssa-loop-ch.c

   1 /* Loop header copying on trees.
   2    Copyright (C) 2004-2013 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 "tree.h"
  25 #include "tm_p.h"
  26 #include "basic-block.h"
  27 #include "gimple.h"
  28 #include "gimple-iterator.h"
  29 #include "gimple-ssa.h"
  30 #include "tree-cfg.h"
  31 #include "tree-into-ssa.h"
  32 #include "tree-pass.h"
  33 #include "cfgloop.h"
  34 #include "tree-inline.h"
  35 #include "flags.h"
  36 #include "tree-ssa-threadedge.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   /* Do not copy one block more than once (we do not really want to do
  55      loop peeling here).  */
  56   if (header->aux)
  57     return false;
  58
  59   /* Loop header copying usually increases size of the code.  This used not to
  60      be true, since quite often it is possible to verify that the condition is
  61      satisfied in the first iteration and therefore to eliminate it.  Jump
  62      threading handles these cases now.  */
  63   if (optimize_loop_for_size_p (loop))
  64     return false;
  65
  66   gcc_assert (EDGE_COUNT (header->succs) > 0);
  67   if (single_succ_p (header))
  68     return false;
  69   if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
  70       && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
  71     return false;
  72
  73   /* If this is not the original loop header, we want it to have just
  74      one predecessor in order to match the && pattern.  */
  75   if (header != loop->header && !single_pred_p (header))
  76     return false;
  77
  78   last = last_stmt (header);
  79   if (gimple_code (last) != GIMPLE_COND)
  80     return false;
  81
  82   /* Approximately copy the conditions that used to be used in jump.c --
  83      at most 20 insns and no calls.  */
  84   for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi))
  85     {
  86       last = gsi_stmt (bsi);
  87
  88       if (gimple_code (last) == GIMPLE_LABEL)
  89         continue;
  90
  91       if (is_gimple_debug (last))
  92         continue;
  93
  94       if (is_gimple_call (last))
  95         return false;
  96
  97       *limit -= estimate_num_insns (last, &eni_size_weights);
  98       if (*limit < 0)
  99         return false;
 100     }
 101
 102   return true;
 103 }
 104
 105 /* Checks whether LOOP is a do-while style loop.  */
 106
 107 static bool
 108 do_while_loop_p (struct loop *loop)
 109 {
 110   gimple stmt = last_stmt (loop->latch);
 111
 112   /* If the latch of the loop is not empty, it is not a do-while loop.  */
 113   if (stmt
 114       && gimple_code (stmt) != GIMPLE_LABEL)
 115     return false;
 116
 117   /* If the header contains just a condition, it is not a do-while loop.  */
 118   stmt = last_and_only_stmt (loop->header);
 119   if (stmt
 120       && gimple_code (stmt) == GIMPLE_COND)
 121     return false;
 122
 123   return true;
 124 }
 125
 126 /* For all loops, copy the condition at the end of the loop body in front
 127    of the loop.  This is beneficial since it increases efficiency of
 128    code motion optimizations.  It also saves one jump on entry to the loop.  */
 129
 130 static unsigned int
 131 copy_loop_headers (void)
 132 {
 133   loop_iterator li;
 134   struct loop *loop;
 135   basic_block header;
 136   edge exit, entry;
 137   basic_block *bbs, *copied_bbs;
 138   unsigned n_bbs;
 139   unsigned bbs_size;
 140
 141   loop_optimizer_init (LOOPS_HAVE_PREHEADERS
 142                        | LOOPS_HAVE_SIMPLE_LATCHES);
 143   if (number_of_loops (cfun) <= 1)
 144     {
 145       loop_optimizer_finalize ();
 146       return 0;
 147     }
 148
 149   bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
 150   copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
 151   bbs_size = n_basic_blocks_for_fn (cfun);
 152
 153   FOR_EACH_LOOP (li, loop, 0)
 154     {
 155       /* Copy at most 20 insns.  */
 156       int limit = 20;
 157
 158       header = loop->header;
 159
 160       /* If the loop is already a do-while style one (either because it was
 161          written as such, or because jump threading transformed it into one),
 162          we might be in fact peeling the first iteration of the loop.  This
 163          in general is not a good idea.  */
 164       if (do_while_loop_p (loop))
 165         continue;
 166
 167       /* Iterate the header copying up to limit; this takes care of the cases
 168          like while (a && b) {...}, where we want to have both of the conditions
 169          copied.  TODO -- handle while (a || b) - like cases, by not requiring
 170          the header to have just a single successor and copying up to
 171          postdominator.  */
 172
 173       exit = NULL;
 174       n_bbs = 0;
 175       while (should_duplicate_loop_header_p (header, loop, &limit))
 176         {
 177           /* Find a successor of header that is inside a loop; i.e. the new
 178              header after the condition is copied.  */
 179           if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
 180             exit = EDGE_SUCC (header, 0);
 181           else
 182             exit = EDGE_SUCC (header, 1);
 183           bbs[n_bbs++] = header;
 184           gcc_assert (bbs_size > n_bbs);
 185           header = exit->dest;
 186         }
 187
 188       if (!exit)
 189         continue;
 190
 191       if (dump_file && (dump_flags & TDF_DETAILS))
 192         fprintf (dump_file,
 193                  "Duplicating header of the loop %d up to edge %d->%d.\n",
 194                  loop->num, exit->src->index, exit->dest->index);
 195
 196       /* Ensure that the header will have just the latch as a predecessor
 197          inside the loop.  */
 198       if (!single_pred_p (exit->dest))
 199         exit = single_pred_edge (split_edge (exit));
 200
 201       entry = loop_preheader_edge (loop);
 202
 203       propagate_threaded_block_debug_into (exit->dest, entry->dest);
 204       if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs,
 205                                          true))
 206         {
 207           fprintf (dump_file, "Duplication failed.\n");
 208           continue;
 209         }
 210
 211       /* If the loop has the form "for (i = j; i < j + 10; i++)" then
 212          this copying can introduce a case where we rely on undefined
 213          signed overflow to eliminate the preheader condition, because
 214          we assume that "j < j + 10" is true.  We don't want to warn
 215          about that case for -Wstrict-overflow, because in general we
 216          don't warn about overflow involving loops.  Prevent the
 217          warning by setting the no_warning flag in the condition.  */
 218       if (warn_strict_overflow > 0)
 219         {
 220           unsigned int i;
 221
 222           for (i = 0; i < n_bbs; ++i)
 223             {
 224               gimple_stmt_iterator bsi;
 225
 226               for (bsi = gsi_start_bb (copied_bbs[i]);
 227                    !gsi_end_p (bsi);
 228                    gsi_next (&bsi))
 229                 {
 230                   gimple stmt = gsi_stmt (bsi);
 231                   if (gimple_code (stmt) == GIMPLE_COND)
 232                     gimple_set_no_warning (stmt, true);
 233                   else if (is_gimple_assign (stmt))
 234                     {
 235                       enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
 236                       if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
 237                         gimple_set_no_warning (stmt, true);
 238                     }
 239                 }
 240             }
 241         }
 242
 243       /* Ensure that the latch and the preheader is simple (we know that they
 244          are not now, since there was the loop exit condition.  */
 245       split_edge (loop_preheader_edge (loop));
 246       split_edge (loop_latch_edge (loop));
 247     }
 248
 249   update_ssa (TODO_update_ssa);
 250   free (bbs);
 251   free (copied_bbs);
 252
 253   loop_optimizer_finalize ();
 254   return 0;
 255 }
 256
 257 static bool
 258 gate_ch (void)
 259 {
 260   return flag_tree_ch != 0;
 261 }
 262
 263 namespace {
 264
 265 const pass_data pass_data_ch =
 266 {
 267   GIMPLE_PASS, /* type */
 268   "ch", /* name */
 269   OPTGROUP_LOOP, /* optinfo_flags */
 270   true, /* has_gate */
 271   true, /* has_execute */
 272   TV_TREE_CH, /* tv_id */
 273   ( PROP_cfg | PROP_ssa ), /* properties_required */
 274   0, /* properties_provided */
 275   0, /* properties_destroyed */
 276   0, /* todo_flags_start */
 277   ( TODO_cleanup_cfg | TODO_verify_ssa
 278     | TODO_verify_flow ), /* todo_flags_finish */
 279 };
 280
 281 class pass_ch : public gimple_opt_pass
 282 {
 283 public:
 284   pass_ch (gcc::context *ctxt)
 285     : gimple_opt_pass (pass_data_ch, ctxt)
 286   {}
 287
 288   /* opt_pass methods: */
 289   bool gate () { return gate_ch (); }
 290   unsigned int execute () { return copy_loop_headers (); }
 291
 292 }; // class pass_ch
 293
 294 } // anon namespace
 295
 296 gimple_opt_pass *
 297 make_pass_ch (gcc::context *ctxt)
 298 {
 299   return new pass_ch (ctxt);
 300 }