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