gcc/tree-ssa-loop-unswitch.c

   1 /* Loop unswitching.
   2    Copyright (C) 2004, 2005, 2007, 2008, 2010 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 3, 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 COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "tm.h"
  24 #include "tree.h"
  25 #include "tm_p.h"
  26 #include "basic-block.h"
  27 #include "tree-flow.h"
  28 #include "cfgloop.h"
  29 #include "params.h"
  30 #include "tree-pass.h"
  31 #include "tree-inline.h"
  32
  33 /* This file implements the loop unswitching, i.e. transformation of loops like
  34
  35    while (A)
  36      {
  37        if (inv)
  38          B;
  39
  40        X;
  41
  42        if (!inv)
  43          C;
  44      }
  45
  46    where inv is the loop invariant, into
  47
  48    if (inv)
  49      {
  50        while (A)
  51          {
  52            B;
  53            X;
  54          }
  55      }
  56    else
  57      {
  58        while (A)
  59          {
  60            X;
  61            C;
  62          }
  63      }
  64
  65    Inv is considered invariant iff the values it compares are both invariant;
  66    tree-ssa-loop-im.c ensures that all the suitable conditions are in this
  67    shape.  */
  68
  69 static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree);
  70 static bool tree_unswitch_single_loop (struct loop *, int);
  71 static tree tree_may_unswitch_on (basic_block, struct loop *);
  72
  73 /* Main entry point.  Perform loop unswitching on all suitable loops.  */
  74
  75 unsigned int
  76 tree_ssa_unswitch_loops (void)
  77 {
  78   loop_iterator li;
  79   struct loop *loop;
  80   bool changed = false;
  81
  82   /* Go through inner loops (only original ones).  */
  83   FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
  84     {
  85       if (dump_file && (dump_flags & TDF_DETAILS))
  86         fprintf (dump_file, ";; Considering loop %d\n", loop->num);
  87
  88       /* Do not unswitch in cold regions. */
  89       if (optimize_loop_for_size_p (loop))
  90         {
  91           if (dump_file && (dump_flags & TDF_DETAILS))
  92             fprintf (dump_file, ";; Not unswitching cold loops\n");
  93           continue;
  94         }
  95
  96       /* The loop should not be too large, to limit code growth. */
  97       if (tree_num_loop_insns (loop, &eni_size_weights)
  98           > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
  99         {
 100           if (dump_file && (dump_flags & TDF_DETAILS))
 101             fprintf (dump_file, ";; Not unswitching, loop too big\n");
 102           continue;
 103         }
 104
 105       changed |= tree_unswitch_single_loop (loop, 0);
 106     }
 107
 108   if (changed)
 109     return TODO_cleanup_cfg;
 110   return 0;
 111 }
 112
 113 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
 114    basic blocks (for what it means see comments below).  */
 115
 116 static tree
 117 tree_may_unswitch_on (basic_block bb, struct loop *loop)
 118 {
 119   gimple stmt, def;
 120   tree cond, use;
 121   basic_block def_bb;
 122   ssa_op_iter iter;
 123
 124   /* BB must end in a simple conditional jump.  */
 125   stmt = last_stmt (bb);
 126   if (!stmt || gimple_code (stmt) != GIMPLE_COND)
 127     return NULL_TREE;
 128
 129   /* To keep the things simple, we do not directly remove the conditions,
 130      but just replace tests with 0 != 0 resp. 1 != 0.  Prevent the infinite
 131      loop where we would unswitch again on such a condition.  */
 132   if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
 133     return NULL_TREE;
 134
 135   /* Condition must be invariant.  */
 136   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
 137     {
 138       def = SSA_NAME_DEF_STMT (use);
 139       def_bb = gimple_bb (def);
 140       if (def_bb
 141           && flow_bb_inside_loop_p (loop, def_bb))
 142         return NULL_TREE;
 143     }
 144
 145   cond = build2 (gimple_cond_code (stmt), boolean_type_node,
 146                  gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
 147
 148   return cond;
 149 }
 150
 151 /* Simplifies COND using checks in front of the entry of the LOOP.  Just very
 152    simplish (sufficient to prevent us from duplicating loop in unswitching
 153    unnecessarily).  */
 154
 155 static tree
 156 simplify_using_entry_checks (struct loop *loop, tree cond)
 157 {
 158   edge e = loop_preheader_edge (loop);
 159   gimple stmt;
 160
 161   while (1)
 162     {
 163       stmt = last_stmt (e->src);
 164       if (stmt
 165           && gimple_code (stmt) == GIMPLE_COND
 166           && gimple_cond_code (stmt) == TREE_CODE (cond)
 167           && operand_equal_p (gimple_cond_lhs (stmt),
 168                               TREE_OPERAND (cond, 0), 0)
 169           && operand_equal_p (gimple_cond_rhs (stmt),
 170                               TREE_OPERAND (cond, 1), 0))
 171         return (e->flags & EDGE_TRUE_VALUE
 172                 ? boolean_true_node
 173                 : boolean_false_node);
 174
 175       if (!single_pred_p (e->src))
 176         return cond;
 177
 178       e = single_pred_edge (e->src);
 179       if (e->src == ENTRY_BLOCK_PTR)
 180         return cond;
 181     }
 182 }
 183
 184 /* Unswitch single LOOP.  NUM is number of unswitchings done; we do not allow
 185    it to grow too much, it is too easy to create example on that the code would
 186    grow exponentially.  */
 187
 188 static bool
 189 tree_unswitch_single_loop (struct loop *loop, int num)
 190 {
 191   basic_block *bbs;
 192   struct loop *nloop;
 193   unsigned i, found;
 194   tree cond = NULL_TREE;
 195   gimple stmt;
 196   bool changed = false;
 197
 198   i = 0;
 199   bbs = get_loop_body (loop);
 200   found = loop->num_nodes;
 201
 202   while (1)
 203     {
 204       /* Find a bb to unswitch on.  */
 205       for (; i < loop->num_nodes; i++)
 206         if ((cond = tree_may_unswitch_on (bbs[i], loop)))
 207           break;
 208
 209       if (i == loop->num_nodes)
 210         {
 211           if (dump_file
 212               && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)
 213               && (dump_flags & TDF_DETAILS))
 214             fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
 215
 216           if (found == loop->num_nodes)
 217             {
 218               free (bbs);
 219               return changed;
 220             }
 221           break;
 222         }
 223
 224       cond = simplify_using_entry_checks (loop, cond);
 225       stmt = last_stmt (bbs[i]);
 226       if (integer_nonzerop (cond))
 227         {
 228           /* Remove false path.  */
 229           gimple_cond_set_condition_from_tree (stmt, boolean_true_node);
 230           changed = true;
 231         }
 232       else if (integer_zerop (cond))
 233         {
 234           /* Remove true path.  */
 235           gimple_cond_set_condition_from_tree (stmt, boolean_false_node);
 236           changed = true;
 237         }
 238       /* Do not unswitch too much.  */
 239       else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
 240         {
 241           i++;
 242           continue;
 243         }
 244       /* In nested tree_unswitch_single_loop first optimize all conditions
 245          using entry checks, then discover still reachable blocks in the
 246          loop and find the condition only among those still reachable bbs.  */
 247       else if (num != 0)
 248         {
 249           if (found == loop->num_nodes)
 250             found = i;
 251           i++;
 252           continue;
 253         }
 254       else
 255         {
 256           found = i;
 257           break;
 258         }
 259
 260       update_stmt (stmt);
 261       i++;
 262     }
 263
 264   if (num != 0)
 265     {
 266       basic_block *tos, *worklist;
 267
 268       /* When called recursively, first do a quick discovery
 269          of reachable bbs after the above changes and only
 270          consider conditions in still reachable bbs.  */
 271       tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
 272
 273       for (i = 0; i < loop->num_nodes; i++)
 274         bbs[i]->flags &= ~BB_REACHABLE;
 275
 276       /* Start with marking header.  */
 277       *tos++ = bbs[0];
 278       bbs[0]->flags |= BB_REACHABLE;
 279
 280       /* Iterate: find everything reachable from what we've already seen
 281          within the same innermost loop.  Don't look through false edges
 282          if condition is always true or true edges if condition is
 283          always false.  */
 284       while (tos != worklist)
 285         {
 286           basic_block b = *--tos;
 287           edge e;
 288           edge_iterator ei;
 289           int flags = 0;
 290
 291           if (EDGE_COUNT (b->succs) == 2)
 292             {
 293               gimple stmt = last_stmt (b);
 294               if (stmt
 295                   && gimple_code (stmt) == GIMPLE_COND)
 296                 {
 297                   if (gimple_cond_true_p (stmt))
 298                     flags = EDGE_FALSE_VALUE;
 299                   else if (gimple_cond_false_p (stmt))
 300                     flags = EDGE_TRUE_VALUE;
 301                 }
 302             }
 303
 304           FOR_EACH_EDGE (e, ei, b->succs)
 305             {
 306               basic_block dest = e->dest;
 307
 308               if (dest->loop_father == loop
 309                   && !(dest->flags & BB_REACHABLE)
 310                   && !(e->flags & flags))
 311                 {
 312                   *tos++ = dest;
 313                   dest->flags |= BB_REACHABLE;
 314                 }
 315             }
 316         }
 317
 318       free (worklist);
 319
 320       /* Find a bb to unswitch on.  */
 321       for (; found < loop->num_nodes; found++)
 322         if ((bbs[found]->flags & BB_REACHABLE)
 323             && (cond = tree_may_unswitch_on (bbs[found], loop)))
 324           break;
 325
 326       if (found == loop->num_nodes)
 327         {
 328           free (bbs);
 329           return changed;
 330         }
 331     }
 332
 333   if (dump_file && (dump_flags & TDF_DETAILS))
 334     fprintf (dump_file, ";; Unswitching loop\n");
 335
 336   initialize_original_copy_tables ();
 337   /* Unswitch the loop on this condition.  */
 338   nloop = tree_unswitch_loop (loop, bbs[found], cond);
 339   if (!nloop)
 340     {
 341       free_original_copy_tables ();
 342       free (bbs);
 343       return changed;
 344     }
 345
 346   /* Update the SSA form after unswitching.  */
 347   update_ssa (TODO_update_ssa);
 348   free_original_copy_tables ();
 349
 350   /* Invoke itself on modified loops.  */
 351   tree_unswitch_single_loop (nloop, num + 1);
 352   tree_unswitch_single_loop (loop, num + 1);
 353   free (bbs);
 354   return true;
 355 }
 356
 357 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
 358    unswitching of innermost loops.  COND is the condition determining which
 359    loop is entered -- the new loop is entered if COND is true.  Returns NULL
 360    if impossible, new loop otherwise.  */
 361
 362 static struct loop *
 363 tree_unswitch_loop (struct loop *loop,
 364                     basic_block unswitch_on, tree cond)
 365 {
 366   unsigned prob_true;
 367   edge edge_true, edge_false;
 368
 369   /* Some sanity checking.  */
 370   gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
 371   gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
 372   gcc_assert (loop->inner == NULL);
 373
 374   extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
 375   prob_true = edge_true->probability;
 376   return loop_version (loop, unshare_expr (cond),
 377                        NULL, prob_true, prob_true,
 378                        REG_BR_PROB_BASE - prob_true, false);
 379 }