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