gcc/tree-ssa-loop-unswitch.c

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