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