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