gcc/tree-ssa-loop-unswitch.c

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