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