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