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