gcc/loop-unswitch.c

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