gcc/tree-ssa-loop-unswitch.c

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