gcc/tree-ssa-loop-ch.c

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