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