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