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