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 stmt, def;
 152   tree cond, use;
 153   basic_block def_bb;
 154   ssa_op_iter iter;
 155
 156   /* BB must end in a simple conditional jump.  */
 157   stmt = last_stmt (bb);
 158   if (!stmt || gimple_code (stmt) != GIMPLE_COND)
 159     return NULL_TREE;
 160
 161   /* To keep the things simple, we do not directly remove the conditions,
 162      but just replace tests with 0 != 0 resp. 1 != 0.  Prevent the infinite
 163      loop where we would unswitch again on such a condition.  */
 164   if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
 165     return NULL_TREE;
 166
 167   /* Condition must be invariant.  */
 168   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
 169     {
 170       def = SSA_NAME_DEF_STMT (use);
 171       def_bb = gimple_bb (def);
 172       if (def_bb
 173           && flow_bb_inside_loop_p (loop, def_bb))
 174         return NULL_TREE;
 175     }
 176
 177   cond = build2 (gimple_cond_code (stmt), boolean_type_node,
 178                  gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
 179
 180   return cond;
 181 }
 182
 183 /* Simplifies COND using checks in front of the entry of the LOOP.  Just very
 184    simplish (sufficient to prevent us from duplicating loop in unswitching
 185    unnecessarily).  */
 186
 187 static tree
 188 simplify_using_entry_checks (struct loop *loop, tree cond)
 189 {
 190   edge e = loop_preheader_edge (loop);
 191   gimple stmt;
 192
 193   while (1)
 194     {
 195       stmt = last_stmt (e->src);
 196       if (stmt
 197           && gimple_code (stmt) == GIMPLE_COND
 198           && gimple_cond_code (stmt) == TREE_CODE (cond)
 199           && operand_equal_p (gimple_cond_lhs (stmt),
 200                               TREE_OPERAND (cond, 0), 0)
 201           && operand_equal_p (gimple_cond_rhs (stmt),
 202                               TREE_OPERAND (cond, 1), 0))
 203         return (e->flags & EDGE_TRUE_VALUE
 204                 ? boolean_true_node
 205                 : boolean_false_node);
 206
 207       if (!single_pred_p (e->src))
 208         return cond;
 209
 210       e = single_pred_edge (e->src);
 211       if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
 212         return cond;
 213     }
 214 }
 215
 216 /* Unswitch single LOOP.  NUM is number of unswitchings done; we do not allow
 217    it to grow too much, it is too easy to create example on that the code would
 218    grow exponentially.  */
 219
 220 static bool
 221 tree_unswitch_single_loop (struct loop *loop, int num)
 222 {
 223   basic_block *bbs;
 224   struct loop *nloop;
 225   unsigned i, found;
 226   tree cond = NULL_TREE;
 227   gimple stmt;
 228   bool changed = false;
 229
 230   i = 0;
 231   bbs = get_loop_body (loop);
 232   found = loop->num_nodes;
 233
 234   while (1)
 235     {
 236       /* Find a bb to unswitch on.  */
 237       for (; i < loop->num_nodes; i++)
 238         if ((cond = tree_may_unswitch_on (bbs[i], loop)))
 239           break;
 240
 241       if (i == loop->num_nodes)
 242         {
 243           if (dump_file
 244               && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)
 245               && (dump_flags & TDF_DETAILS))
 246             fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
 247
 248           if (found == loop->num_nodes)
 249             {
 250               free (bbs);
 251               return changed;
 252             }
 253           break;
 254         }
 255
 256       cond = simplify_using_entry_checks (loop, cond);
 257       stmt = last_stmt (bbs[i]);
 258       if (integer_nonzerop (cond))
 259         {
 260           /* Remove false path.  */
 261           gimple_cond_set_condition_from_tree (stmt, boolean_true_node);
 262           changed = true;
 263         }
 264       else if (integer_zerop (cond))
 265         {
 266           /* Remove true path.  */
 267           gimple_cond_set_condition_from_tree (stmt, boolean_false_node);
 268           changed = true;
 269         }
 270       /* Do not unswitch too much.  */
 271       else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
 272         {
 273           i++;
 274           continue;
 275         }
 276       /* In nested tree_unswitch_single_loop first optimize all conditions
 277          using entry checks, then discover still reachable blocks in the
 278          loop and find the condition only among those still reachable bbs.  */
 279       else if (num != 0)
 280         {
 281           if (found == loop->num_nodes)
 282             found = i;
 283           i++;
 284           continue;
 285         }
 286       else
 287         {
 288           found = i;
 289           break;
 290         }
 291
 292       update_stmt (stmt);
 293       i++;
 294     }
 295
 296   if (num != 0)
 297     {
 298       basic_block *tos, *worklist;
 299
 300       /* When called recursively, first do a quick discovery
 301          of reachable bbs after the above changes and only
 302          consider conditions in still reachable bbs.  */
 303       tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
 304
 305       for (i = 0; i < loop->num_nodes; i++)
 306         bbs[i]->flags &= ~BB_REACHABLE;
 307
 308       /* Start with marking header.  */
 309       *tos++ = bbs[0];
 310       bbs[0]->flags |= BB_REACHABLE;
 311
 312       /* Iterate: find everything reachable from what we've already seen
 313          within the same innermost loop.  Don't look through false edges
 314          if condition is always true or true edges if condition is
 315          always false.  */
 316       while (tos != worklist)
 317         {
 318           basic_block b = *--tos;
 319           edge e;
 320           edge_iterator ei;
 321           int flags = 0;
 322
 323           if (EDGE_COUNT (b->succs) == 2)
 324             {
 325               gimple stmt = last_stmt (b);
 326               if (stmt
 327                   && gimple_code (stmt) == GIMPLE_COND)
 328                 {
 329                   if (gimple_cond_true_p (stmt))
 330                     flags = EDGE_FALSE_VALUE;
 331                   else if (gimple_cond_false_p (stmt))
 332                     flags = EDGE_TRUE_VALUE;
 333                 }
 334             }
 335
 336           FOR_EACH_EDGE (e, ei, b->succs)
 337             {
 338               basic_block dest = e->dest;
 339
 340               if (dest->loop_father == loop
 341                   && !(dest->flags & BB_REACHABLE)
 342                   && !(e->flags & flags))
 343                 {
 344                   *tos++ = dest;
 345                   dest->flags |= BB_REACHABLE;
 346                 }
 347             }
 348         }
 349
 350       free (worklist);
 351
 352       /* Find a bb to unswitch on.  */
 353       for (; found < loop->num_nodes; found++)
 354         if ((bbs[found]->flags & BB_REACHABLE)
 355             && (cond = tree_may_unswitch_on (bbs[found], loop)))
 356           break;
 357
 358       if (found == loop->num_nodes)
 359         {
 360           free (bbs);
 361           return changed;
 362         }
 363     }
 364
 365   if (dump_file && (dump_flags & TDF_DETAILS))
 366     fprintf (dump_file, ";; Unswitching loop\n");
 367
 368   initialize_original_copy_tables ();
 369   /* Unswitch the loop on this condition.  */
 370   nloop = tree_unswitch_loop (loop, bbs[found], cond);
 371   if (!nloop)
 372     {
 373       free_original_copy_tables ();
 374       free (bbs);
 375       return changed;
 376     }
 377
 378   /* Update the SSA form after unswitching.  */
 379   update_ssa (TODO_update_ssa);
 380   free_original_copy_tables ();
 381
 382   /* Invoke itself on modified loops.  */
 383   tree_unswitch_single_loop (nloop, num + 1);
 384   tree_unswitch_single_loop (loop, num + 1);
 385   free (bbs);
 386   return true;
 387 }
 388
 389 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
 390    unswitching of innermost loops.  COND is the condition determining which
 391    loop is entered -- the new loop is entered if COND is true.  Returns NULL
 392    if impossible, new loop otherwise.  */
 393
 394 static struct loop *
 395 tree_unswitch_loop (struct loop *loop,
 396                     basic_block unswitch_on, tree cond)
 397 {
 398   unsigned prob_true;
 399   edge edge_true, edge_false;
 400
 401   /* Some sanity checking.  */
 402   gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
 403   gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
 404   gcc_assert (loop->inner == NULL);
 405
 406   extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
 407   prob_true = edge_true->probability;
 408   return loop_version (loop, unshare_expr (cond),
 409                        NULL, prob_true, prob_true,
 410                        REG_BR_PROB_BASE - prob_true, false);
 411 }
 412
 413 /* Loop unswitching pass.  */
 414
 415 namespace {
 416
 417 const pass_data pass_data_tree_unswitch =
 418 {
 419   GIMPLE_PASS, /* type */
 420   "unswitch", /* name */
 421   OPTGROUP_LOOP, /* optinfo_flags */
 422   TV_TREE_LOOP_UNSWITCH, /* tv_id */
 423   PROP_cfg, /* properties_required */
 424   0, /* properties_provided */
 425   0, /* properties_destroyed */
 426   0, /* todo_flags_start */
 427   0, /* todo_flags_finish */
 428 };
 429
 430 class pass_tree_unswitch : public gimple_opt_pass
 431 {
 432 public:
 433   pass_tree_unswitch (gcc::context *ctxt)
 434     : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
 435   {}
 436
 437   /* opt_pass methods: */
 438   virtual bool gate (function *) { return flag_unswitch_loops != 0; }
 439   virtual unsigned int execute (function *);
 440
 441 }; // class pass_tree_unswitch
 442
 443 unsigned int
 444 pass_tree_unswitch::execute (function *fun)
 445 {
 446   if (number_of_loops (fun) <= 1)
 447     return 0;
 448
 449   return tree_ssa_unswitch_loops ();
 450 }
 451
 452 } // anon namespace
 453
 454 gimple_opt_pass *
 455 make_pass_tree_unswitch (gcc::context *ctxt)
 456 {
 457   return new pass_tree_unswitch (ctxt);
 458 }
 459
 460