gcc/tree-ssa-loop-ch.c

   1 /* Loop header copying on trees.
   2    Copyright (C) 2004 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 2, 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 COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "hard-reg-set.h"
  29 #include "basic-block.h"
  30 #include "output.h"
  31 #include "diagnostic.h"
  32 #include "tree-flow.h"
  33 #include "tree-dump.h"
  34 #include "tree-pass.h"
  35 #include "timevar.h"
  36 #include "cfgloop.h"
  37 #include "tree-inline.h"
  38 #include "flags.h"
  39 #include "tree-inline.h"
  40
  41 /* Duplicates headers of loops if they are small enough, so that the statements
  42    in the loop body are always executed when the loop is entered.  This
  43    increases effectiveness of code motion optimizations, and reduces the need
  44    for loop preconditioning.  */
  45
  46 /* Check whether we should duplicate HEADER of LOOP.  At most *LIMIT
  47    instructions should be duplicated, limit is decreased by the actual
  48    amount.  */
  49
  50 static bool
  51 should_duplicate_loop_header_p (basic_block header, struct loop *loop,
  52                                 int *limit)
  53 {
  54   block_stmt_iterator bsi;
  55   tree last;
  56
  57   /* Do not copy one block more than once (we do not really want to do
  58      loop peeling here).  */
  59   if (header->aux)
  60     return false;
  61
  62   gcc_assert (header->succ);
  63   if (!header->succ->succ_next)
  64     return false;
  65   if (header->succ->succ_next->succ_next)
  66     return false;
  67   if (flow_bb_inside_loop_p (loop, header->succ->dest)
  68       && flow_bb_inside_loop_p (loop, header->succ->succ_next->dest))
  69     return false;
  70
  71   /* If this is not the original loop header, we want it to have just
  72      one predecessor in order to match the && pattern.  */
  73   if (header != loop->header
  74       && header->pred->pred_next)
  75     return false;
  76
  77   last = last_stmt (header);
  78   if (TREE_CODE (last) != COND_EXPR)
  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 = bsi_start (header); !bsi_end_p (bsi); bsi_next (&bsi))
  84     {
  85       last = bsi_stmt (bsi);
  86
  87       if (TREE_CODE (last) == LABEL_EXPR)
  88         continue;
  89
  90       if (get_call_expr_in (last))
  91         return false;
  92
  93       *limit -= estimate_num_insns (last);
  94       if (*limit < 0)
  95         return false;
  96     }
  97
  98   return true;
  99 }
 100
 101 /* Checks whether LOOP is a do-while style loop.  */
 102
 103 static bool
 104 do_while_loop_p (struct loop *loop)
 105 {
 106   tree stmt = last_stmt (loop->latch);
 107
 108   /* If the latch of the loop is not empty, it is not a do-while loop.  */
 109   if (stmt
 110       && TREE_CODE (stmt) != LABEL_EXPR)
 111     return false;
 112
 113   /* If the header contains just a condition, it is not a do-while loop.  */
 114   stmt = last_and_only_stmt (loop->header);
 115   if (stmt
 116       && TREE_CODE (stmt) == COND_EXPR)
 117     return false;
 118
 119   return true;
 120 }
 121
 122 /* For all loops, copy the condition at the end of the loop body in front
 123    of the loop.  This is beneficial since it increases efficiency of
 124    code motion optimizations.  It also saves one jump on entry to the loop.  */
 125
 126 static void
 127 copy_loop_headers (void)
 128 {
 129   struct loops *loops;
 130   unsigned i;
 131   struct loop *loop;
 132   basic_block header;
 133   edge exit;
 134   basic_block *bbs;
 135   unsigned n_bbs;
 136
 137   loops = loop_optimizer_init (dump_file);
 138   if (!loops)
 139     return;
 140   rewrite_into_loop_closed_ssa ();
 141
 142   /* We do not try to keep the information about irreducible regions
 143      up-to-date.  */
 144   loops->state &= ~LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
 145
 146 #ifdef ENABLE_CHECKING
 147   verify_loop_structure (loops);
 148 #endif
 149
 150   bbs = xmalloc (sizeof (basic_block) * n_basic_blocks);
 151
 152   for (i = 1; i < loops->num; i++)
 153     {
 154       /* Copy at most 20 insns.  */
 155       int limit = 20;
 156
 157       loop = loops->parray[i];
 158       header = loop->header;
 159
 160       /* If the loop is already a do-while style one (either because it was
 161          written as such, or because jump threading transformed it into one),
 162          we might be in fact peeling the first iteration of the loop.  This
 163          in general is not a good idea.  */
 164       if (do_while_loop_p (loop))
 165         continue;
 166
 167       /* Iterate the header copying up to limit; this takes care of the cases
 168          like while (a && b) {...}, where we want to have both of the conditions
 169          copied.  TODO -- handle while (a || b) - like cases, by not requiring
 170          the header to have just a single successor and copying up to
 171          postdominator.  */
 172
 173       exit = NULL;
 174       n_bbs = 0;
 175       while (should_duplicate_loop_header_p (header, loop, &limit))
 176         {
 177           /* Find a successor of header that is inside a loop; i.e. the new
 178              header after the condition is copied.  */
 179           if (flow_bb_inside_loop_p (loop, header->succ->dest))
 180             exit = header->succ;
 181           else
 182             exit = header->succ->succ_next;
 183           bbs[n_bbs++] = header;
 184           header = exit->dest;
 185         }
 186
 187       if (!exit)
 188         continue;
 189
 190       if (dump_file && (dump_flags & TDF_DETAILS))
 191         fprintf (dump_file,
 192                  "Duplicating header of the loop %d up to edge %d->%d.\n",
 193                  loop->num, exit->src->index, exit->dest->index);
 194
 195       /* Ensure that the header will have just the latch as a predecessor
 196          inside the loop.  */
 197       if (exit->dest->pred->pred_next)
 198         exit = loop_split_edge_with (exit, NULL)->succ;
 199
 200       if (!tree_duplicate_sese_region (loop_preheader_edge (loop), exit,
 201                                        bbs, n_bbs, NULL))
 202         {
 203           fprintf (dump_file, "Duplication failed.\n");
 204           continue;
 205         }
 206
 207       /* Ensure that the latch and the preheader is simple (we know that they
 208          are not now, since there was the loop exit condition.  */
 209       loop_split_edge_with (loop_preheader_edge (loop), NULL);
 210       loop_split_edge_with (loop_latch_edge (loop), NULL);
 211     }
 212
 213   free (bbs);
 214
 215 #ifdef ENABLE_CHECKING
 216   verify_loop_closed_ssa ();
 217 #endif
 218
 219   loop_optimizer_finalize (loops, NULL);
 220
 221   /* Run cleanup_tree_cfg here regardless of whether we have done anything, so
 222      that we cleanup the blocks created in order to get the loops into a
 223      canonical shape.  */
 224   cleanup_tree_cfg ();
 225 }
 226
 227 static bool
 228 gate_ch (void)
 229 {
 230   return flag_tree_ch != 0;
 231 }
 232
 233 struct tree_opt_pass pass_ch =
 234 {
 235   "ch",                                 /* name */
 236   gate_ch,                              /* gate */
 237   copy_loop_headers,                    /* execute */
 238   NULL,                                 /* sub */
 239   NULL,                                 /* next */
 240   0,                                    /* static_pass_number */
 241   TV_TREE_CH,                           /* tv_id */
 242   PROP_cfg | PROP_ssa,                  /* properties_required */
 243   0,                                    /* properties_provided */
 244   0,                                    /* properties_destroyed */
 245   0,                                    /* todo_flags_start */
 246   (TODO_dump_func
 247    | TODO_verify_ssa),                  /* todo_flags_finish */
 248   0                                     /* letter */
 249 };