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 effectivity 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 /* Duplicates destinations of edges in BBS_TO_DUPLICATE.  */
 102
 103 static void
 104 duplicate_blocks (varray_type bbs_to_duplicate)
 105 {
 106   unsigned i;
 107   edge preheader_edge, e, e1;
 108   basic_block header, new_header;
 109   tree phi, new_phi, var;
 110
 111   /* TODO: It should be quite easy to keep the dominance information
 112      up-to-date.  */
 113   free_dominance_info (CDI_DOMINATORS);
 114
 115   for (i = 0; i < VARRAY_ACTIVE_SIZE (bbs_to_duplicate); i++)
 116     {
 117       preheader_edge = VARRAY_GENERIC_PTR_NOGC (bbs_to_duplicate, i);
 118       header = preheader_edge->dest;
 119
 120       gcc_assert (header->aux);
 121       header->aux = NULL;
 122
 123       new_header = duplicate_block (header, preheader_edge);
 124
 125       /* Create the phi nodes on on entry to new_header.  */
 126       for (phi = phi_nodes (header), var = PENDING_STMT (preheader_edge);
 127            phi;
 128            phi = TREE_CHAIN (phi), var = TREE_CHAIN (var))
 129         {
 130           new_phi = create_phi_node (PHI_RESULT (phi), new_header);
 131           add_phi_arg (&new_phi, TREE_VALUE (var), preheader_edge);
 132         }
 133       PENDING_STMT (preheader_edge) = NULL;
 134
 135       /* Add the phi arguments to the outgoing edges.  */
 136       for (e = header->succ; e; e = e->succ_next)
 137         {
 138           for (e1 = new_header->succ; e1->dest != e->dest; e1 = e1->succ_next)
 139             continue;
 140
 141           for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
 142             {
 143               tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
 144               add_phi_arg (&phi, def, e1);
 145             }
 146         }
 147     }
 148
 149   calculate_dominance_info (CDI_DOMINATORS);
 150
 151   rewrite_ssa_into_ssa ();
 152 }
 153
 154 /* Checks whether LOOP is a do-while style loop.  */
 155
 156 static bool
 157 do_while_loop_p (struct loop *loop)
 158 {
 159   tree stmt = last_stmt (loop->latch);
 160
 161   /* If the latch of the loop is not empty, it is not a do-while loop.  */
 162   if (stmt
 163       && TREE_CODE (stmt) != LABEL_EXPR)
 164     return false;
 165
 166   /* If the header contains just a condition, it is not a do-while loop.  */
 167   stmt = last_and_only_stmt (loop->header);
 168   if (stmt
 169       && TREE_CODE (stmt) == COND_EXPR)
 170     return false;
 171
 172   return true;
 173 }
 174
 175 /* For all loops, copy the condition at the end of the loop body in front
 176    of the loop.  This is beneficial since it increases efficiency of
 177    code motion optimizations.  It also saves one jump on entry to the loop.  */
 178
 179 static void
 180 copy_loop_headers (void)
 181 {
 182   struct loops *loops;
 183   unsigned i;
 184   struct loop *loop;
 185   basic_block header;
 186   edge preheader_edge;
 187   varray_type bbs_to_duplicate = NULL;
 188
 189   loops = loop_optimizer_init (dump_file);
 190   if (!loops)
 191     return;
 192
 193   /* We do not try to keep the information about irreducible regions
 194      up-to-date.  */
 195   loops->state &= ~LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
 196
 197 #ifdef ENABLE_CHECKING
 198   verify_loop_structure (loops);
 199 #endif
 200
 201   for (i = 1; i < loops->num; i++)
 202     {
 203       /* Copy at most 20 insns.  */
 204       int limit = 20;
 205
 206       loop = loops->parray[i];
 207       preheader_edge = loop_preheader_edge (loop);
 208       header = preheader_edge->dest;
 209
 210       /* If the loop is already a do-while style one (either because it was
 211          written as such, or because jump threading transformed it into one),
 212          we might be in fact peeling the first iteration of the loop.  This
 213          in general is not a good idea.  */
 214       if (do_while_loop_p (loop))
 215         continue;
 216
 217       /* Iterate the header copying up to limit; this takes care of the cases
 218          like while (a && b) {...}, where we want to have both of the conditions
 219          copied.  TODO -- handle while (a || b) - like cases, by not requiring
 220          the header to have just a single successor and copying up to
 221          postdominator.
 222
 223          We do not really copy the blocks immediately, so that we do not have
 224          to worry about updating loop structures, and also so that we do not
 225          have to rewrite variables out of and into ssa form for each block.
 226          Instead we just record the block into worklist and duplicate all of
 227          them at once.  */
 228       while (should_duplicate_loop_header_p (header, loop, &limit))
 229         {
 230           if (!bbs_to_duplicate)
 231             VARRAY_GENERIC_PTR_NOGC_INIT (bbs_to_duplicate, 10,
 232                                           "bbs_to_duplicate");
 233           VARRAY_PUSH_GENERIC_PTR_NOGC (bbs_to_duplicate, preheader_edge);
 234           header->aux = &header->aux;
 235
 236           if (dump_file && (dump_flags & TDF_DETAILS))
 237             fprintf (dump_file,
 238                      "Scheduled basic block %d for duplication.\n",
 239                      header->index);
 240
 241           /* Find a successor of header that is inside a loop; i.e. the new
 242              header after the condition is copied.  */
 243           if (flow_bb_inside_loop_p (loop, header->succ->dest))
 244             preheader_edge = header->succ;
 245           else
 246             preheader_edge = header->succ->succ_next;
 247           header = preheader_edge->dest;
 248         }
 249     }
 250
 251   loop_optimizer_finalize (loops, NULL);
 252
 253   if (bbs_to_duplicate)
 254     {
 255       duplicate_blocks (bbs_to_duplicate);
 256       VARRAY_FREE (bbs_to_duplicate);
 257     }
 258
 259   /* Run cleanup_tree_cfg here regardless of whether we have done anything, so
 260      that we cleanup the blocks created in order to get the loops into a
 261      canonical shape.  */
 262   cleanup_tree_cfg ();
 263 }
 264
 265 static bool
 266 gate_ch (void)
 267 {
 268   return flag_tree_ch != 0;
 269 }
 270
 271 struct tree_opt_pass pass_ch =
 272 {
 273   "ch",                                 /* name */
 274   gate_ch,                              /* gate */
 275   copy_loop_headers,                    /* execute */
 276   NULL,                                 /* sub */
 277   NULL,                                 /* next */
 278   0,                                    /* static_pass_number */
 279   TV_TREE_CH,                           /* tv_id */
 280   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 281   0,                                    /* properties_provided */
 282   0,                                    /* properties_destroyed */
 283   0,                                    /* todo_flags_start */
 284   (TODO_dump_func
 285    | TODO_verify_ssa),                  /* todo_flags_finish */
 286   0                                     /* letter */
 287 };