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