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 "basic-block.h"
  27 #include "tree-ssa-alias.h"
  28 #include "internal-fn.h"
  29 #include "gimple-expr.h"
  30 #include "is-a.h"
  31 #include "gimple.h"
  32 #include "gimplify.h"
  33 #include "gimple-ssa.h"
  34 #include "tree-cfg.h"
  35 #include "tree-phinodes.h"
  36 #include "ssa-iterators.h"
  37 #include "tree-ssa-loop-niter.h"
  38 #include "tree-ssa-loop.h"
  39 #include "tree-into-ssa.h"
  40 #include "cfgloop.h"
  41 #include "params.h"
  42 #include "tree-pass.h"
  43 #include "tree-inline.h"
  44
  45 /* This file implements the loop unswitching, i.e. transformation of loops like
  46
  47    while (A)
  48      {
  49        if (inv)
  50          B;
  51
  52        X;
  53
  54        if (!inv)
  55          C;
  56      }
  57
  58    where inv is the loop invariant, into
  59
  60    if (inv)
  61      {
  62        while (A)
  63          {
  64            B;
  65            X;
  66          }
  67      }
  68    else
  69      {
  70        while (A)
  71          {
  72            X;
  73            C;
  74          }
  75      }
  76
  77    Inv is considered invariant iff the values it compares are both invariant;
  78    tree-ssa-loop-im.c ensures that all the suitable conditions are in this
  79    shape.  */
  80
  81 static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree);
  82 static bool tree_unswitch_single_loop (struct loop *, int);
  83 static tree tree_may_unswitch_on (basic_block, struct loop *);
  84
  85 /* Main entry point.  Perform loop unswitching on all suitable loops.  */
  86
  87 unsigned int
  88 tree_ssa_unswitch_loops (void)
  89 {
  90   struct loop *loop;
  91   bool changed = false;
  92   HOST_WIDE_INT iterations;
  93
  94   /* Go through inner loops (only original ones).  */
  95   FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST)
  96     {
  97       if (dump_file && (dump_flags & TDF_DETAILS))
  98         fprintf (dump_file, ";; Considering loop %d\n", loop->num);
  99
 100       /* Do not unswitch in cold regions. */
 101       if (optimize_loop_for_size_p (loop))
 102         {
 103           if (dump_file && (dump_flags & TDF_DETAILS))
 104             fprintf (dump_file, ";; Not unswitching cold loops\n");
 105           continue;
 106         }
 107
 108       /* The loop should not be too large, to limit code growth. */
 109       if (tree_num_loop_insns (loop, &eni_size_weights)
 110           > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
 111         {
 112           if (dump_file && (dump_flags & TDF_DETAILS))
 113             fprintf (dump_file, ";; Not unswitching, loop too big\n");
 114           continue;
 115         }
 116
 117       /* If the loop is not expected to iterate, there is no need
 118          for unswitching.  */
 119       iterations = estimated_loop_iterations_int (loop);
 120       if (iterations >= 0 && iterations <= 1)
 121         {
 122           if (dump_file && (dump_flags & TDF_DETAILS))
 123             fprintf (dump_file, ";; Not unswitching, loop is not expected to iterate\n");
 124           continue;
 125         }
 126
 127       changed |= tree_unswitch_single_loop (loop, 0);
 128     }
 129
 130   if (changed)
 131     return TODO_cleanup_cfg;
 132   return 0;
 133 }
 134
 135 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
 136    basic blocks (for what it means see comments below).  */
 137
 138 static tree
 139 tree_may_unswitch_on (basic_block bb, struct loop *loop)
 140 {
 141   gimple stmt, def;
 142   tree cond, use;
 143   basic_block def_bb;
 144   ssa_op_iter iter;
 145
 146   /* BB must end in a simple conditional jump.  */
 147   stmt = last_stmt (bb);
 148   if (!stmt || gimple_code (stmt) != GIMPLE_COND)
 149     return NULL_TREE;
 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 (stmt, boolean_true_node);
 252           changed = true;
 253         }
 254       else if (integer_zerop (cond))
 255         {
 256           /* Remove true path.  */
 257           gimple_cond_set_condition_from_tree (stmt, boolean_false_node);
 258           changed = true;
 259         }
 260       /* Do not unswitch too much.  */
 261       else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
 262         {
 263           i++;
 264           continue;
 265         }
 266       /* In nested tree_unswitch_single_loop first optimize all conditions
 267          using entry checks, then discover still reachable blocks in the
 268          loop and find the condition only among those still reachable bbs.  */
 269       else if (num != 0)
 270         {
 271           if (found == loop->num_nodes)
 272             found = i;
 273           i++;
 274           continue;
 275         }
 276       else
 277         {
 278           found = i;
 279           break;
 280         }
 281
 282       update_stmt (stmt);
 283       i++;
 284     }
 285
 286   if (num != 0)
 287     {
 288       basic_block *tos, *worklist;
 289
 290       /* When called recursively, first do a quick discovery
 291          of reachable bbs after the above changes and only
 292          consider conditions in still reachable bbs.  */
 293       tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
 294
 295       for (i = 0; i < loop->num_nodes; i++)
 296         bbs[i]->flags &= ~BB_REACHABLE;
 297
 298       /* Start with marking header.  */
 299       *tos++ = bbs[0];
 300       bbs[0]->flags |= BB_REACHABLE;
 301
 302       /* Iterate: find everything reachable from what we've already seen
 303          within the same innermost loop.  Don't look through false edges
 304          if condition is always true or true edges if condition is
 305          always false.  */
 306       while (tos != worklist)
 307         {
 308           basic_block b = *--tos;
 309           edge e;
 310           edge_iterator ei;
 311           int flags = 0;
 312
 313           if (EDGE_COUNT (b->succs) == 2)
 314             {
 315               gimple stmt = last_stmt (b);
 316               if (stmt
 317                   && gimple_code (stmt) == GIMPLE_COND)
 318                 {
 319                   if (gimple_cond_true_p (stmt))
 320                     flags = EDGE_FALSE_VALUE;
 321                   else if (gimple_cond_false_p (stmt))
 322                     flags = EDGE_TRUE_VALUE;
 323                 }
 324             }
 325
 326           FOR_EACH_EDGE (e, ei, b->succs)
 327             {
 328               basic_block dest = e->dest;
 329
 330               if (dest->loop_father == loop
 331                   && !(dest->flags & BB_REACHABLE)
 332                   && !(e->flags & flags))
 333                 {
 334                   *tos++ = dest;
 335                   dest->flags |= BB_REACHABLE;
 336                 }
 337             }
 338         }
 339
 340       free (worklist);
 341
 342       /* Find a bb to unswitch on.  */
 343       for (; found < loop->num_nodes; found++)
 344         if ((bbs[found]->flags & BB_REACHABLE)
 345             && (cond = tree_may_unswitch_on (bbs[found], loop)))
 346           break;
 347
 348       if (found == loop->num_nodes)
 349         {
 350           free (bbs);
 351           return changed;
 352         }
 353     }
 354
 355   if (dump_file && (dump_flags & TDF_DETAILS))
 356     fprintf (dump_file, ";; Unswitching loop\n");
 357
 358   initialize_original_copy_tables ();
 359   /* Unswitch the loop on this condition.  */
 360   nloop = tree_unswitch_loop (loop, bbs[found], cond);
 361   if (!nloop)
 362     {
 363       free_original_copy_tables ();
 364       free (bbs);
 365       return changed;
 366     }
 367
 368   /* Update the SSA form after unswitching.  */
 369   update_ssa (TODO_update_ssa);
 370   free_original_copy_tables ();
 371
 372   /* Invoke itself on modified loops.  */
 373   tree_unswitch_single_loop (nloop, num + 1);
 374   tree_unswitch_single_loop (loop, num + 1);
 375   free (bbs);
 376   return true;
 377 }
 378
 379 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
 380    unswitching of innermost loops.  COND is the condition determining which
 381    loop is entered -- the new loop is entered if COND is true.  Returns NULL
 382    if impossible, new loop otherwise.  */
 383
 384 static struct loop *
 385 tree_unswitch_loop (struct loop *loop,
 386                     basic_block unswitch_on, tree cond)
 387 {
 388   unsigned prob_true;
 389   edge edge_true, edge_false;
 390
 391   /* Some sanity checking.  */
 392   gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
 393   gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
 394   gcc_assert (loop->inner == NULL);
 395
 396   extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
 397   prob_true = edge_true->probability;
 398   return loop_version (loop, unshare_expr (cond),
 399                        NULL, prob_true, prob_true,
 400                        REG_BR_PROB_BASE - prob_true, false);
 401 }
 402
 403 /* Loop unswitching pass.  */
 404
 405 namespace {
 406
 407 const pass_data pass_data_tree_unswitch =
 408 {
 409   GIMPLE_PASS, /* type */
 410   "unswitch", /* name */
 411   OPTGROUP_LOOP, /* optinfo_flags */
 412   true, /* has_execute */
 413   TV_TREE_LOOP_UNSWITCH, /* tv_id */
 414   PROP_cfg, /* properties_required */
 415   0, /* properties_provided */
 416   0, /* properties_destroyed */
 417   0, /* todo_flags_start */
 418   0, /* todo_flags_finish */
 419 };
 420
 421 class pass_tree_unswitch : public gimple_opt_pass
 422 {
 423 public:
 424   pass_tree_unswitch (gcc::context *ctxt)
 425     : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
 426   {}
 427
 428   /* opt_pass methods: */
 429   virtual bool gate (function *) { return flag_unswitch_loops != 0; }
 430   virtual unsigned int execute (function *);
 431
 432 }; // class pass_tree_unswitch
 433
 434 unsigned int
 435 pass_tree_unswitch::execute (function *fun)
 436 {
 437   if (number_of_loops (fun) <= 1)
 438     return 0;
 439
 440   return tree_ssa_unswitch_loops ();
 441 }
 442
 443 } // anon namespace
 444
 445 gimple_opt_pass *
 446 make_pass_tree_unswitch (gcc::context *ctxt)
 447 {
 448   return new pass_tree_unswitch (ctxt);
 449 }
 450
 451