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