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