gcc/loop-unswitch.c

   1 /* Loop unswitching for GNU compiler.
   2    Copyright (C) 2002, 2003 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 under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 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 COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "rtl.h"
  26 #include "hard-reg-set.h"
  27 #include "basic-block.h"
  28 #include "cfgloop.h"
  29 #include "cfglayout.h"
  30 #include "params.h"
  31 #include "output.h"
  32 #include "expr.h"
  33
  34 /* This pass moves constant conditions out of loops, duplicating the loop
  35    in progress, i.e. this code:
  36
  37    while (loop_cond)
  38      {
  39        A;
  40        if (cond)
  41          branch1;
  42        else
  43          branch2;
  44        B;
  45        if (cond)
  46          branch3;
  47        C;
  48      }
  49    where nothing inside the loop alters cond is transformed
  50    into
  51
  52    if (cond)
  53      {
  54        while (loop_cond)
  55          {
  56            A;
  57            branch1;
  58            B;
  59            branch3;
  60            C;
  61          }
  62      }
  63    else
  64      {
  65        while (loop_cond)
  66          {
  67            A;
  68            branch2;
  69            B;
  70            C;
  71          }
  72      }
  73
  74   Duplicating the loop might lead to code growth exponential in number of
  75   branches inside loop, so we limit the number of unswitchings performed
  76   in a single loop to PARAM_MAX_UNSWITCH_LEVEL.  We only perform the
  77   transformation on innermost loops, as the benefit of doing it on loops
  78   containing subloops would not be very large compared to complications
  79   with handling this case.  */
  80
  81 static struct loop *unswitch_loop (struct loops *, struct loop *,
  82                                    basic_block);
  83 static void unswitch_single_loop (struct loops *, struct loop *, rtx, int);
  84 static bool may_unswitch_on_p (struct loops *, basic_block, struct loop *,
  85                                basic_block *);
  86 static rtx reversed_condition (rtx);
  87
  88 /* Main entry point.  Perform loop unswitching on all suitable LOOPS.  */
  89 void
  90 unswitch_loops (struct loops *loops)
  91 {
  92   int i, num;
  93   struct loop *loop;
  94
  95   /* Go through inner loops (only original ones).  */
  96   num = loops->num;
  97
  98   for (i = 1; i < num; i++)
  99     {
 100       /* Removed loop?  */
 101       loop = loops->parray[i];
 102       if (!loop)
 103         continue;
 104
 105       if (loop->inner)
 106         continue;
 107
 108       unswitch_single_loop (loops, loop, NULL_RTX, 0);
 109 #ifdef ENABLE_CHECKING
 110       verify_dominators (loops->cfg.dom);
 111       verify_loop_structure (loops);
 112 #endif
 113     }
 114 }
 115
 116 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
 117    basic blocks (for what it means see comments below).  List of basic blocks
 118    inside LOOP is provided in BODY to save time.  */
 119 static bool
 120 may_unswitch_on_p (struct loops *loops, basic_block bb, struct loop *loop,
 121                    basic_block *body)
 122 {
 123   rtx test;
 124   unsigned i;
 125
 126   /* BB must end in a simple conditional jump.  */
 127   if (!bb->succ || !bb->succ->succ_next || bb->succ->succ_next->succ_next)
 128     return false;
 129   if (!any_condjump_p (bb->end))
 130     return false;
 131
 132   /* With branches inside loop.  */
 133   if (!flow_bb_inside_loop_p (loop, bb->succ->dest)
 134       || !flow_bb_inside_loop_p (loop, bb->succ->succ_next->dest))
 135     return false;
 136
 137   /* It must be executed just once each iteration (because otherwise we
 138      are unable to update dominator/irreducible loop information correctly).  */
 139   if (!just_once_each_iteration_p (loops, loop, bb))
 140     return false;
 141
 142   /* Condition must be invariant.  We use just a stupid test of invariantness
 143      of the condition: all used regs must not be modified inside loop body.  */
 144   test = get_condition (bb->end, NULL);
 145   if (!test)
 146     return false;
 147
 148   for (i = 0; i < loop->num_nodes; i++)
 149     if (modified_between_p (test, body[i]->head, NEXT_INSN (body[i]->end)))
 150       return false;
 151
 152   return true;
 153 }
 154
 155 /* Reverses CONDition; returns NULL if we cannot.  */
 156 static rtx
 157 reversed_condition (rtx cond)
 158 {
 159   enum rtx_code reversed;
 160   reversed = reversed_comparison_code (cond, NULL);
 161   if (reversed == UNKNOWN)
 162     return NULL_RTX;
 163   else
 164     return gen_rtx_fmt_ee (reversed,
 165                            GET_MODE (cond), XEXP (cond, 0),
 166                            XEXP (cond, 1));
 167 }
 168
 169 /* Unswitch single LOOP.  COND_CHECKED holds list of conditions we already
 170    unswitched on and are therefore known to be true in this LOOP.  NUM is
 171    number of unswitchings done; do not allow it to grow too much, it is too
 172    easy to create example on that the code would grow exponentially.  */
 173 static void
 174 unswitch_single_loop (struct loops *loops, struct loop *loop,
 175                       rtx cond_checked, int num)
 176 {
 177   basic_block *bbs, bb;
 178   struct loop *nloop;
 179   unsigned i;
 180   int true_first;
 181   rtx cond, rcond, conds, rconds, acond, split_before;
 182   int always_true;
 183   int always_false;
 184   int repeat;
 185   edge e;
 186
 187   /* Do not unswitch too much.  */
 188   if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
 189     {
 190       if (rtl_dump_file)
 191         fprintf (rtl_dump_file, ";; Not unswitching anymore, hit max level\n");
 192       return;
 193     }
 194
 195   /* Only unswitch innermost loops.  */
 196   if (loop->inner)
 197     {
 198       if (rtl_dump_file)
 199         fprintf (rtl_dump_file, ";; Not unswitching, not innermost loop\n");
 200       return;
 201     }
 202
 203   /* We must be able to duplicate loop body.  */
 204   if (!can_duplicate_loop_p (loop))
 205     {
 206       if (rtl_dump_file)
 207         fprintf (rtl_dump_file, ";; Not unswitching, can't duplicate loop\n");
 208       return;
 209     }
 210
 211   /* The loop should not be too large, to limit code growth.  */
 212   if (num_loop_insns (loop) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
 213     {
 214       if (rtl_dump_file)
 215         fprintf (rtl_dump_file, ";; Not unswitching, loop too big\n");
 216       return;
 217     }
 218
 219   /* Do not unswitch in cold areas.  */
 220   if (!maybe_hot_bb_p (loop->header))
 221     {
 222       if (rtl_dump_file)
 223         fprintf (rtl_dump_file, ";; Not unswitching, not hot area\n");
 224       return;
 225     }
 226
 227   /* Nor if the loop usually does not roll.  */
 228   if (expected_loop_iterations (loop) < 1)
 229     {
 230       if (rtl_dump_file)
 231         fprintf (rtl_dump_file, ";; Not unswitching, loop iterations < 1\n");
 232       return;
 233     }
 234
 235   do
 236     {
 237       repeat = 0;
 238
 239       /* Find a bb to unswitch on.  */
 240       bbs = get_loop_body (loop);
 241       for (i = 0; i < loop->num_nodes; i++)
 242         if (may_unswitch_on_p (loops, bbs[i], loop, bbs))
 243           break;
 244
 245       if (i == loop->num_nodes)
 246         {
 247           free (bbs);
 248           return;
 249         }
 250
 251       if (!(cond = get_condition (bbs[i]->end, &split_before)))
 252         abort ();
 253       rcond = reversed_condition (cond);
 254
 255       /* Check whether the result can be predicted.  */
 256       always_true = 0;
 257       always_false = 0;
 258       for (acond = cond_checked; acond; acond = XEXP (acond, 1))
 259         {
 260           if (rtx_equal_p (cond, XEXP (acond, 0)))
 261             {
 262               always_true = 1;
 263               break;
 264             }
 265           if (rtx_equal_p (rcond, XEXP (acond, 0)))
 266             {
 267               always_false = 1;
 268               break;
 269             }
 270         }
 271
 272       if (always_true)
 273         {
 274           /* Remove false path.  */
 275           for (e = bbs[i]->succ; !(e->flags & EDGE_FALLTHRU); e = e->succ_next);
 276           remove_path (loops, e);
 277           free (bbs);
 278           repeat = 1;
 279         }
 280       else if (always_false)
 281         {
 282           /* Remove true path.  */
 283           for (e = bbs[i]->succ; e->flags & EDGE_FALLTHRU; e = e->succ_next);
 284           remove_path (loops, e);
 285           free (bbs);
 286           repeat = 1;
 287         }
 288     } while (repeat);
 289
 290   /* We found the condition we can unswitch on.  */
 291   conds = alloc_EXPR_LIST (0, cond, cond_checked);
 292   if (rcond)
 293     rconds = alloc_EXPR_LIST (0, rcond, cond_checked);
 294   else
 295     rconds = cond_checked;
 296
 297   /* Separate condition in a single basic block.  */
 298   bb = split_loop_bb (loops, bbs[i], PREV_INSN (split_before))->dest;
 299   free (bbs);
 300   true_first = !(bb->succ->flags & EDGE_FALLTHRU);
 301   if (rtl_dump_file)
 302     fprintf (rtl_dump_file, ";; Unswitching loop\n");
 303
 304   /* Unswitch the loop on this condition.  */
 305   nloop = unswitch_loop (loops, loop, bb);
 306   if (!nloop)
 307   abort ();
 308
 309   /* Invoke itself on modified loops.  */
 310   unswitch_single_loop (loops, nloop, true_first ? conds : rconds, num + 1);
 311   unswitch_single_loop (loops, loop, true_first ? rconds : conds, num + 1);
 312
 313   free_EXPR_LIST_node (conds);
 314   if (rcond)
 315     free_EXPR_LIST_node (rconds);
 316 }
 317
 318 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
 319    unswitching of innermost loops.  UNSWITCH_ON must be executed in every
 320    iteration, i.e. it must dominate LOOP latch, and should only contain code
 321    for the condition we unswitch on.  Returns NULL if impossible, new
 322    loop otherwise.  */
 323 static struct loop *
 324 unswitch_loop (struct loops *loops, struct loop *loop, basic_block unswitch_on)
 325 {
 326   edge entry, latch_edge;
 327   basic_block switch_bb, unswitch_on_alt, src;
 328   struct loop *nloop;
 329   sbitmap zero_bitmap;
 330   int irred_flag;
 331
 332   /* Some sanity checking.  */
 333   if (!flow_bb_inside_loop_p (loop, unswitch_on))
 334     abort ();
 335   if (!unswitch_on->succ || !unswitch_on->succ->succ_next ||
 336       unswitch_on->succ->succ_next->succ_next)
 337     abort ();
 338   if (!just_once_each_iteration_p (loops, loop, unswitch_on))
 339     abort ();
 340   if (loop->inner)
 341     abort ();
 342   if (!flow_bb_inside_loop_p (loop, unswitch_on->succ->dest))
 343     abort ();
 344   if (!flow_bb_inside_loop_p (loop, unswitch_on->succ->succ_next->dest))
 345     abort ();
 346
 347   /* Will we be able to perform redirection?  */
 348   if (!any_condjump_p (unswitch_on->end))
 349     return NULL;
 350   if (!cfg_layout_can_duplicate_bb_p (unswitch_on))
 351     return NULL;
 352
 353   entry = loop_preheader_edge (loop);
 354
 355   /* Make a copy.  */
 356   src = entry->src;
 357   irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
 358   entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 359   zero_bitmap = sbitmap_alloc (2);
 360   sbitmap_zero (zero_bitmap);
 361   if (!duplicate_loop_to_header_edge (loop, entry, loops, 1,
 362         zero_bitmap, NULL, NULL, NULL, 0))
 363     return NULL;
 364   free (zero_bitmap);
 365   entry->flags |= irred_flag;
 366
 367   /* Record the block with condition we unswitch on.  */
 368   unswitch_on_alt = unswitch_on->rbi->copy;
 369
 370   /* Make a copy of the block containing the condition; we will use
 371      it as switch to decide which loop we want to use.  */
 372   switch_bb = cfg_layout_duplicate_bb (unswitch_on, NULL);
 373   if (irred_flag)
 374     {
 375       switch_bb->flags |= BB_IRREDUCIBLE_LOOP;
 376       switch_bb->succ->flags |= EDGE_IRREDUCIBLE_LOOP;
 377       switch_bb->succ->succ_next->flags |= EDGE_IRREDUCIBLE_LOOP;
 378     }
 379   else
 380     {
 381       switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP;
 382       switch_bb->succ->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 383       switch_bb->succ->succ_next->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 384     }
 385   add_to_dominance_info (loops->cfg.dom, switch_bb);
 386   unswitch_on->rbi->copy = unswitch_on_alt;
 387
 388   /* Loopify from the copy of LOOP body, constructing the new loop.  */
 389   for (latch_edge = loop->latch->rbi->copy->succ;
 390        latch_edge->dest != loop->header;
 391        latch_edge = latch_edge->succ_next);
 392   nloop = loopify (loops, latch_edge,
 393                    loop->header->rbi->copy->pred, switch_bb);
 394
 395   /* Remove branches that are now unreachable in new loops.  We rely on the
 396      fact that cfg_layout_duplicate_bb reverses list of edges.  */
 397   remove_path (loops, unswitch_on->succ);
 398   remove_path (loops, unswitch_on_alt->succ);
 399
 400   /* One of created loops do not have to be subloop of the outer loop now,
 401      so fix its placement in loop data structure.  */
 402   fix_loop_placement (loop);
 403   fix_loop_placement (nloop);
 404
 405   return nloop;
 406 }