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