gcc/tree-ssa-loop.c

   1 /* Loop optimizations over tree-ssa.
   2    Copyright (C) 2003 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 "basic-block.h"
  33 #include "tree-flow.h"
  34 #include "tree-dump.h"
  35 #include "tree-pass.h"
  36 #include "timevar.h"
  37 #include "cfgloop.h"
  38 #include "flags.h"
  39 #include "tree-inline.h"
  40
  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   block_stmt_iterator bsi;
  51   tree 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   if (!header->succ)
  59     abort ();
  60   if (!header->succ->succ_next)
  61     return false;
  62   if (header->succ->succ_next->succ_next)
  63     return false;
  64   if (flow_bb_inside_loop_p (loop, header->succ->dest)
  65       && flow_bb_inside_loop_p (loop, header->succ->succ_next->dest))
  66     return false;
  67
  68   /* If this is not the original loop header, we want it to have just
  69      one predecessor in order to match the && pattern.  */
  70   if (header != loop->header
  71       && header->pred->pred_next)
  72     return false;
  73
  74   last = last_stmt (header);
  75   if (TREE_CODE (last) != COND_EXPR)
  76     return false;
  77
  78   /* Approximately copy the conditions that used to be used in jump.c --
  79      at most 20 insns and no calls.  */
  80   for (bsi = bsi_start (header); !bsi_end_p (bsi); bsi_next (&bsi))
  81     {
  82       last = bsi_stmt (bsi);
  83
  84       if (TREE_CODE (last) == LABEL_EXPR)
  85         continue;
  86
  87       if (get_call_expr_in (last))
  88         return false;
  89
  90       *limit -= estimate_num_insns (last);
  91       if (*limit < 0)
  92         return false;
  93     }
  94
  95   return true;
  96 }
  97
  98 /* Marks variables defined in basic block BB for rewriting.  */
  99
 100 static void
 101 mark_defs_for_rewrite (basic_block bb)
 102 {
 103   tree stmt, var;
 104   block_stmt_iterator bsi;
 105   stmt_ann_t ann;
 106   def_optype defs;
 107   v_may_def_optype v_may_defs;
 108   vuse_optype vuses;
 109   v_must_def_optype v_must_defs;
 110   unsigned i;
 111
 112   for (stmt = phi_nodes (bb); stmt; stmt = PHI_CHAIN (stmt))
 113     {
 114       var = SSA_NAME_VAR (PHI_RESULT (stmt));
 115       bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
 116
 117       /* If we have a type_mem_tag, add it as well.  Due to rewriting the
 118          variable out of ssa, we lose its name tag, so we use type_mem_tag
 119          instead.  */
 120       var = var_ann (var)->type_mem_tag;
 121       if (var)
 122         bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
 123     }
 124
 125   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 126     {
 127       stmt = bsi_stmt (bsi);
 128       get_stmt_operands (stmt);
 129       ann = stmt_ann (stmt);
 130
 131       defs = DEF_OPS (ann);
 132       for (i = 0; i < NUM_DEFS (defs); i++)
 133         {
 134           var = SSA_NAME_VAR (DEF_OP (defs, i));
 135           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
 136
 137           /* If we have a type_mem_tag, add it as well.  Due to rewriting the
 138              variable out of ssa, we lose its name tag, so we use type_mem_tag
 139              instead.  */
 140           var = var_ann (var)->type_mem_tag;
 141           if (var)
 142             bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
 143         }
 144
 145       v_may_defs = V_MAY_DEF_OPS (ann);
 146       for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
 147         {
 148           var = SSA_NAME_VAR (V_MAY_DEF_RESULT (v_may_defs, i));
 149           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
 150         }
 151
 152       v_must_defs = V_MUST_DEF_OPS (ann);
 153       for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
 154         {
 155           var = SSA_NAME_VAR (V_MUST_DEF_OP (v_must_defs, i));
 156           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
 157         }
 158
 159       /* We also need to rewrite vuses, since we will copy the statements
 160          and the ssa versions could not be recovered in the copy.  We do
 161          not have to do this for operands of V_MAY_DEFS explicitly, since
 162          they have the same underlying variable as the results.  */
 163       vuses = VUSE_OPS (ann);
 164       for (i = 0; i < NUM_VUSES (vuses); i++)
 165         {
 166           var = SSA_NAME_VAR (VUSE_OP (vuses, i));
 167           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
 168         }
 169     }
 170 }
 171
 172 /* Duplicates destinations of edges in BBS_TO_DUPLICATE.  */
 173
 174 static void
 175 duplicate_blocks (varray_type bbs_to_duplicate)
 176 {
 177   unsigned i;
 178   edge preheader_edge, e, e1;
 179   basic_block header, new_header;
 180   tree phi;
 181   size_t old_num_referenced_vars = num_referenced_vars;
 182
 183   for (i = 0; i < VARRAY_ACTIVE_SIZE (bbs_to_duplicate); i++)
 184     {
 185       preheader_edge = VARRAY_GENERIC_PTR_NOGC (bbs_to_duplicate, i);
 186       header = preheader_edge->dest;
 187
 188       /* It is sufficient to rewrite the definitions, since the uses of
 189          the operands defined outside of the duplicated basic block are
 190          still valid (every basic block that dominates the original block
 191          also dominates the duplicate).  */
 192       mark_defs_for_rewrite (header);
 193     }
 194
 195   rewrite_vars_out_of_ssa (vars_to_rename);
 196
 197   for (i = old_num_referenced_vars; i < num_referenced_vars; i++)
 198     {
 199       bitmap_set_bit (vars_to_rename, i);
 200       var_ann (referenced_var (i))->out_of_ssa_tag = 0;
 201     }
 202
 203   for (i = 0; i < VARRAY_ACTIVE_SIZE (bbs_to_duplicate); i++)
 204     {
 205       preheader_edge = VARRAY_GENERIC_PTR_NOGC (bbs_to_duplicate, i);
 206       header = preheader_edge->dest;
 207
 208       /* We might have split the edge into the loop header when we have
 209          eliminated the phi nodes, so find the edge to that we want to
 210          copy the header.  */
 211       while (!header->aux)
 212         {
 213           preheader_edge = header->succ;
 214           header = preheader_edge->dest;
 215         }
 216       header->aux = NULL;
 217
 218       new_header = duplicate_block (header, preheader_edge);
 219
 220       /* Add the phi arguments to the outgoing edges.  */
 221       for (e = header->succ; e; e = e->succ_next)
 222         {
 223           for (e1 = new_header->succ; e1->dest != e->dest; e1 = e1->succ_next)
 224             continue;
 225
 226           for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
 227             {
 228               tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
 229               add_phi_arg (&phi, def, e1);
 230             }
 231         }
 232     }
 233 }
 234
 235 /* Checks whether LOOP is a do-while style loop.  */
 236
 237 static bool
 238 do_while_loop_p (struct loop *loop)
 239 {
 240   tree stmt = last_stmt (loop->latch);
 241
 242   /* If the latch of the loop is not empty, it is not a do-while loop.  */
 243   if (stmt
 244       && TREE_CODE (stmt) != LABEL_EXPR)
 245     return false;
 246
 247   /* If the header contains just a condition, it is not a do-while loop.  */
 248   stmt = last_and_only_stmt (loop->header);
 249   if (stmt
 250       && TREE_CODE (stmt) == COND_EXPR)
 251     return false;
 252
 253   return true;
 254 }
 255
 256 /* For all loops, copy the condition at the end of the loop body in front
 257    of the loop.  This is beneficial since it increases effectivity of
 258    code motion optimizations.  It also saves one jump on entry to the loop.  */
 259
 260 static void
 261 copy_loop_headers (void)
 262 {
 263   struct loops *loops;
 264   unsigned i;
 265   struct loop *loop;
 266   basic_block header;
 267   edge preheader_edge;
 268   varray_type bbs_to_duplicate = NULL;
 269
 270   loops = loop_optimizer_init (dump_file);
 271   if (!loops)
 272     return;
 273
 274   /* We are not going to need or update dominators.  */
 275   free_dominance_info (CDI_DOMINATORS);
 276
 277   create_preheaders (loops, CP_SIMPLE_PREHEADERS);
 278
 279   /* We do not try to keep the information about irreducible regions
 280      up-to-date.  */
 281   loops->state &= ~LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
 282
 283 #ifdef ENABLE_CHECKING
 284   verify_loop_structure (loops);
 285 #endif
 286
 287   for (i = 1; i < loops->num; i++)
 288     {
 289       /* Copy at most 20 insns.  */
 290       int limit = 20;
 291
 292       loop = loops->parray[i];
 293       preheader_edge = loop_preheader_edge (loop);
 294       header = preheader_edge->dest;
 295
 296       /* If the loop is already a do-while style one (either because it was
 297          written as such, or because jump threading transformed it into one),
 298          we might be in fact peeling the first iteration of the loop.  This
 299          in general is not a good idea.  */
 300       if (do_while_loop_p (loop))
 301         continue;
 302
 303       /* Iterate the header copying up to limit; this takes care of the cases
 304          like while (a && b) {...}, where we want to have both of the conditions
 305          copied.  TODO -- handle while (a || b) - like cases, by not requiring
 306          the header to have just a single successor and copying up to
 307          postdominator.
 308
 309          We do not really copy the blocks immediately, so that we do not have
 310          to worry about updating loop structures, and also so that we do not
 311          have to rewrite variables out of and into ssa form for each block.
 312          Instead we just record the block into worklist and duplicate all of
 313          them at once.  */
 314       while (should_duplicate_loop_header_p (header, loop, &limit))
 315         {
 316           if (!bbs_to_duplicate)
 317             VARRAY_GENERIC_PTR_NOGC_INIT (bbs_to_duplicate, 10,
 318                                           "bbs_to_duplicate");
 319           VARRAY_PUSH_GENERIC_PTR_NOGC (bbs_to_duplicate, preheader_edge);
 320           header->aux = &header->aux;
 321
 322           if (dump_file && (dump_flags & TDF_DETAILS))
 323             fprintf (dump_file,
 324                      "Scheduled basic block %d for duplication.\n",
 325                      header->index);
 326
 327           /* Find a successor of header that is inside a loop; i.e. the new
 328              header after the condition is copied.  */
 329           if (flow_bb_inside_loop_p (loop, header->succ->dest))
 330             preheader_edge = header->succ;
 331           else
 332             preheader_edge = header->succ->succ_next;
 333           header = preheader_edge->dest;
 334         }
 335     }
 336
 337   loop_optimizer_finalize (loops, NULL);
 338
 339   if (bbs_to_duplicate)
 340     {
 341       duplicate_blocks (bbs_to_duplicate);
 342       VARRAY_FREE (bbs_to_duplicate);
 343     }
 344
 345   /* Run cleanup_tree_cfg here regardless of whether we have done anything, so
 346      that we cleanup the blocks created in order to get the loops into a
 347      canonical shape.  */
 348   cleanup_tree_cfg ();
 349 }
 350
 351 static bool
 352 gate_ch (void)
 353 {
 354   return flag_tree_ch != 0;
 355 }
 356
 357 struct tree_opt_pass pass_ch =
 358 {
 359   "ch",                                 /* name */
 360   gate_ch,                              /* gate */
 361   copy_loop_headers,                    /* execute */
 362   NULL,                                 /* sub */
 363   NULL,                                 /* next */
 364   0,                                    /* static_pass_number */
 365   TV_TREE_CH,                           /* tv_id */
 366   PROP_cfg | PROP_ssa,                  /* properties_required */
 367   0,                                    /* properties_provided */
 368   0,                                    /* properties_destroyed */
 369   0,                                    /* todo_flags_start */
 370   (TODO_rename_vars
 371    | TODO_dump_func
 372    | TODO_verify_ssa)                   /* todo_flags_finish */
 373 };