gcc/tree-ssa-loop-unswitch.c

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