gcc/tree-ssa-loop-ch.c

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