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-ssa.h"
  29 #include "tree-cfg.h"
  30 #include "tree-into-ssa.h"
  31 #include "tree-pass.h"
  32 #include "cfgloop.h"
  33 #include "tree-inline.h"
  34 #include "flags.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 /* For all loops, copy the condition at the end of the loop body in front
 126    of the loop.  This is beneficial since it increases efficiency of
 127    code motion optimizations.  It also saves one jump on entry to the loop.  */
 128
 129 static unsigned int
 130 copy_loop_headers (void)
 131 {
 132   loop_iterator li;
 133   struct loop *loop;
 134   basic_block header;
 135   edge exit, entry;
 136   basic_block *bbs, *copied_bbs;
 137   unsigned n_bbs;
 138   unsigned bbs_size;
 139
 140   loop_optimizer_init (LOOPS_HAVE_PREHEADERS
 141                        | LOOPS_HAVE_SIMPLE_LATCHES);
 142   if (number_of_loops (cfun) <= 1)
 143     {
 144       loop_optimizer_finalize ();
 145       return 0;
 146     }
 147
 148   bbs = XNEWVEC (basic_block, n_basic_blocks);
 149   copied_bbs = XNEWVEC (basic_block, n_basic_blocks);
 150   bbs_size = n_basic_blocks;
 151
 152   FOR_EACH_LOOP (li, loop, 0)
 153     {
 154       /* Copy at most 20 insns.  */
 155       int limit = 20;
 156
 157       header = loop->header;
 158
 159       /* If the loop is already a do-while style one (either because it was
 160          written as such, or because jump threading transformed it into one),
 161          we might be in fact peeling the first iteration of the loop.  This
 162          in general is not a good idea.  */
 163       if (do_while_loop_p (loop))
 164         continue;
 165
 166       /* Iterate the header copying up to limit; this takes care of the cases
 167          like while (a && b) {...}, where we want to have both of the conditions
 168          copied.  TODO -- handle while (a || b) - like cases, by not requiring
 169          the header to have just a single successor and copying up to
 170          postdominator.  */
 171
 172       exit = NULL;
 173       n_bbs = 0;
 174       while (should_duplicate_loop_header_p (header, loop, &limit))
 175         {
 176           /* Find a successor of header that is inside a loop; i.e. the new
 177              header after the condition is copied.  */
 178           if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
 179             exit = EDGE_SUCC (header, 0);
 180           else
 181             exit = EDGE_SUCC (header, 1);
 182           bbs[n_bbs++] = header;
 183           gcc_assert (bbs_size > n_bbs);
 184           header = exit->dest;
 185         }
 186
 187       if (!exit)
 188         continue;
 189
 190       if (dump_file && (dump_flags & TDF_DETAILS))
 191         fprintf (dump_file,
 192                  "Duplicating header of the loop %d up to edge %d->%d.\n",
 193                  loop->num, exit->src->index, exit->dest->index);
 194
 195       /* Ensure that the header will have just the latch as a predecessor
 196          inside the loop.  */
 197       if (!single_pred_p (exit->dest))
 198         exit = single_pred_edge (split_edge (exit));
 199
 200       entry = loop_preheader_edge (loop);
 201
 202       propagate_threaded_block_debug_into (exit->dest, entry->dest);
 203       if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs,
 204                                          true))
 205         {
 206           fprintf (dump_file, "Duplication failed.\n");
 207           continue;
 208         }
 209
 210       /* If the loop has the form "for (i = j; i < j + 10; i++)" then
 211          this copying can introduce a case where we rely on undefined
 212          signed overflow to eliminate the preheader condition, because
 213          we assume that "j < j + 10" is true.  We don't want to warn
 214          about that case for -Wstrict-overflow, because in general we
 215          don't warn about overflow involving loops.  Prevent the
 216          warning by setting the no_warning flag in the condition.  */
 217       if (warn_strict_overflow > 0)
 218         {
 219           unsigned int i;
 220
 221           for (i = 0; i < n_bbs; ++i)
 222             {
 223               gimple_stmt_iterator bsi;
 224
 225               for (bsi = gsi_start_bb (copied_bbs[i]);
 226                    !gsi_end_p (bsi);
 227                    gsi_next (&bsi))
 228                 {
 229                   gimple stmt = gsi_stmt (bsi);
 230                   if (gimple_code (stmt) == GIMPLE_COND)
 231                     gimple_set_no_warning (stmt, true);
 232                   else if (is_gimple_assign (stmt))
 233                     {
 234                       enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
 235                       if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
 236                         gimple_set_no_warning (stmt, true);
 237                     }
 238                 }
 239             }
 240         }
 241
 242       /* Ensure that the latch and the preheader is simple (we know that they
 243          are not now, since there was the loop exit condition.  */
 244       split_edge (loop_preheader_edge (loop));
 245       split_edge (loop_latch_edge (loop));
 246     }
 247
 248   update_ssa (TODO_update_ssa);
 249   free (bbs);
 250   free (copied_bbs);
 251
 252   loop_optimizer_finalize ();
 253   return 0;
 254 }
 255
 256 static bool
 257 gate_ch (void)
 258 {
 259   return flag_tree_ch != 0;
 260 }
 261
 262 namespace {
 263
 264 const pass_data pass_data_ch =
 265 {
 266   GIMPLE_PASS, /* type */
 267   "ch", /* name */
 268   OPTGROUP_LOOP, /* optinfo_flags */
 269   true, /* has_gate */
 270   true, /* has_execute */
 271   TV_TREE_CH, /* tv_id */
 272   ( PROP_cfg | PROP_ssa ), /* properties_required */
 273   0, /* properties_provided */
 274   0, /* properties_destroyed */
 275   0, /* todo_flags_start */
 276   ( TODO_cleanup_cfg | TODO_verify_ssa
 277     | TODO_verify_flow ), /* todo_flags_finish */
 278 };
 279
 280 class pass_ch : public gimple_opt_pass
 281 {
 282 public:
 283   pass_ch (gcc::context *ctxt)
 284     : gimple_opt_pass (pass_data_ch, ctxt)
 285   {}
 286
 287   /* opt_pass methods: */
 288   bool gate () { return gate_ch (); }
 289   unsigned int execute () { return copy_loop_headers (); }
 290
 291 }; // class pass_ch
 292
 293 } // anon namespace
 294
 295 gimple_opt_pass *
 296 make_pass_ch (gcc::context *ctxt)
 297 {
 298   return new pass_ch (ctxt);
 299 }