gcc/tree-ssa-loop-unswitch.c

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