gcc/tree-ssa-loop-unswitch.c

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