gcc/loop-unswitch.c

   1 /* Loop unswitching for GNU compiler.
   2    Copyright (C) 2002, 2003, 2004, 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301, 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 "obstack.h"
  28 #include "basic-block.h"
  29 #include "cfgloop.h"
  30 #include "cfglayout.h"
  31 #include "params.h"
  32 #include "output.h"
  33 #include "expr.h"
  34
  35 /* This pass moves constant conditions out of loops, duplicating the loop
  36    in progress, i.e. this code:
  37
  38    while (loop_cond)
  39      {
  40        A;
  41        if (cond)
  42          branch1;
  43        else
  44          branch2;
  45        B;
  46        if (cond)
  47          branch3;
  48        C;
  49      }
  50    where nothing inside the loop alters cond is transformed
  51    into
  52
  53    if (cond)
  54      {
  55        while (loop_cond)
  56          {
  57            A;
  58            branch1;
  59            B;
  60            branch3;
  61            C;
  62          }
  63      }
  64    else
  65      {
  66        while (loop_cond)
  67          {
  68            A;
  69            branch2;
  70            B;
  71            C;
  72          }
  73      }
  74
  75   Duplicating the loop might lead to code growth exponential in number of
  76   branches inside loop, so we limit the number of unswitchings performed
  77   in a single loop to PARAM_MAX_UNSWITCH_LEVEL.  We only perform the
  78   transformation on innermost loops, as the benefit of doing it on loops
  79   containing subloops would not be very large compared to complications
  80   with handling this case.  */
  81
  82 static struct loop *unswitch_loop (struct loops *, struct loop *,
  83                                    basic_block, rtx, rtx);
  84 static void unswitch_single_loop (struct loops *, struct loop *, rtx, int);
  85 static rtx may_unswitch_on (basic_block, struct loop *, rtx *);
  86
  87 /* Prepare a sequence comparing OP0 with OP1 using COMP and jumping to LABEL if
  88    true, with probability PROB.  If CINSN is not NULL, it is the insn to copy
  89    in order to create a jump.  */
  90
  91 rtx
  92 compare_and_jump_seq (rtx op0, rtx op1, enum rtx_code comp, rtx label, int prob,
  93                       rtx cinsn)
  94 {
  95   rtx seq, jump, cond;
  96   enum machine_mode mode;
  97
  98   mode = GET_MODE (op0);
  99   if (mode == VOIDmode)
 100     mode = GET_MODE (op1);
 101
 102   start_sequence ();
 103   if (GET_MODE_CLASS (mode) == MODE_CC)
 104     {
 105       /* A hack -- there seems to be no easy generic way how to make a
 106          conditional jump from a ccmode comparison.  */
 107       gcc_assert (cinsn);
 108       cond = XEXP (SET_SRC (pc_set (cinsn)), 0);
 109       gcc_assert (GET_CODE (cond) == comp);
 110       gcc_assert (rtx_equal_p (op0, XEXP (cond, 0)));
 111       gcc_assert (rtx_equal_p (op1, XEXP (cond, 1)));
 112       emit_jump_insn (copy_insn (PATTERN (cinsn)));
 113       jump = get_last_insn ();
 114       JUMP_LABEL (jump) = JUMP_LABEL (cinsn);
 115       LABEL_NUSES (JUMP_LABEL (jump))++;
 116       redirect_jump (jump, label, 0);
 117     }
 118   else
 119     {
 120       gcc_assert (!cinsn);
 121
 122       op0 = force_operand (op0, NULL_RTX);
 123       op1 = force_operand (op1, NULL_RTX);
 124       do_compare_rtx_and_jump (op0, op1, comp, 0,
 125                                mode, NULL_RTX, NULL_RTX, label);
 126       jump = get_last_insn ();
 127       JUMP_LABEL (jump) = label;
 128       LABEL_NUSES (label)++;
 129     }
 130   REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
 131                                         REG_NOTES (jump));
 132   seq = get_insns ();
 133   end_sequence ();
 134
 135   return seq;
 136 }
 137
 138 /* Main entry point.  Perform loop unswitching on all suitable LOOPS.  */
 139 void
 140 unswitch_loops (struct loops *loops)
 141 {
 142   int i, num;
 143   struct loop *loop;
 144
 145   /* Go through inner loops (only original ones).  */
 146   num = loops->num;
 147
 148   for (i = 1; i < num; i++)
 149     {
 150       /* Removed loop?  */
 151       loop = loops->parray[i];
 152       if (!loop)
 153         continue;
 154
 155       if (loop->inner)
 156         continue;
 157
 158       unswitch_single_loop (loops, loop, NULL_RTX, 0);
 159 #ifdef ENABLE_CHECKING
 160       verify_dominators (CDI_DOMINATORS);
 161       verify_loop_structure (loops);
 162 #endif
 163     }
 164
 165   iv_analysis_done ();
 166 }
 167
 168 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
 169    basic blocks (for what it means see comments below).  In case condition
 170    compares loop invariant cc mode register, return the jump in CINSN.  */
 171
 172 static rtx
 173 may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn)
 174 {
 175   rtx test, at, op[2], stest;
 176   struct rtx_iv iv;
 177   unsigned i;
 178   enum machine_mode mode;
 179
 180   /* BB must end in a simple conditional jump.  */
 181   if (EDGE_COUNT (bb->succs) != 2)
 182     return NULL_RTX;
 183   if (!any_condjump_p (BB_END (bb)))
 184     return NULL_RTX;
 185
 186   /* With branches inside loop.  */
 187   if (!flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 0)->dest)
 188       || !flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 1)->dest))
 189     return NULL_RTX;
 190
 191   /* It must be executed just once each iteration (because otherwise we
 192      are unable to update dominator/irreducible loop information correctly).  */
 193   if (!just_once_each_iteration_p (loop, bb))
 194     return NULL_RTX;
 195
 196   /* Condition must be invariant.  */
 197   test = get_condition (BB_END (bb), &at, true, false);
 198   if (!test)
 199     return NULL_RTX;
 200
 201   for (i = 0; i < 2; i++)
 202     {
 203       op[i] = XEXP (test, i);
 204
 205       if (CONSTANT_P (op[i]))
 206         continue;
 207
 208       if (!iv_analyze (at, op[i], &iv))
 209         return NULL_RTX;
 210       if (iv.step != const0_rtx
 211           || iv.first_special)
 212         return NULL_RTX;
 213
 214       op[i] = get_iv_value (&iv, const0_rtx);
 215     }
 216
 217   mode = GET_MODE (op[0]);
 218   if (mode == VOIDmode)
 219     mode = GET_MODE (op[1]);
 220   if (GET_MODE_CLASS (mode) == MODE_CC)
 221     {
 222       if (at != BB_END (bb))
 223         return NULL_RTX;
 224
 225       if (!rtx_equal_p (op[0], XEXP (test, 0))
 226           || !rtx_equal_p (op[1], XEXP (test, 1)))
 227         return NULL_RTX;
 228
 229       *cinsn = BB_END (bb);
 230       return test;
 231     }
 232
 233   stest = simplify_gen_relational (GET_CODE (test), SImode,
 234                                    mode, op[0], op[1]);
 235   if (stest == const0_rtx
 236       || stest == const_true_rtx)
 237     return stest;
 238
 239   return canon_condition (gen_rtx_fmt_ee (GET_CODE (test), SImode,
 240                                           op[0], op[1]));
 241 }
 242
 243 /* Reverses CONDition; returns NULL if we cannot.  */
 244 rtx
 245 reversed_condition (rtx cond)
 246 {
 247   enum rtx_code reversed;
 248   reversed = reversed_comparison_code (cond, NULL);
 249   if (reversed == UNKNOWN)
 250     return NULL_RTX;
 251   else
 252     return gen_rtx_fmt_ee (reversed,
 253                            GET_MODE (cond), XEXP (cond, 0),
 254                            XEXP (cond, 1));
 255 }
 256
 257 /* Unswitch single LOOP.  COND_CHECKED holds list of conditions we already
 258    unswitched on and are therefore known to be true in this LOOP.  NUM is
 259    number of unswitchings done; do not allow it to grow too much, it is too
 260    easy to create example on that the code would grow exponentially.  */
 261 static void
 262 unswitch_single_loop (struct loops *loops, struct loop *loop,
 263                       rtx cond_checked, int num)
 264 {
 265   basic_block *bbs;
 266   struct loop *nloop;
 267   unsigned i;
 268   rtx cond, rcond = NULL_RTX, conds, rconds, acond, cinsn;
 269   int repeat;
 270   edge e;
 271
 272   /* Do not unswitch too much.  */
 273   if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
 274     {
 275       if (dump_file)
 276         fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
 277       return;
 278     }
 279
 280   /* Only unswitch innermost loops.  */
 281   if (loop->inner)
 282     {
 283       if (dump_file)
 284         fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
 285       return;
 286     }
 287
 288   /* We must be able to duplicate loop body.  */
 289   if (!can_duplicate_loop_p (loop))
 290     {
 291       if (dump_file)
 292         fprintf (dump_file, ";; Not unswitching, can't duplicate loop\n");
 293       return;
 294     }
 295
 296   /* The loop should not be too large, to limit code growth.  */
 297   if (num_loop_insns (loop) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
 298     {
 299       if (dump_file)
 300         fprintf (dump_file, ";; Not unswitching, loop too big\n");
 301       return;
 302     }
 303
 304   /* Do not unswitch in cold areas.  */
 305   if (!maybe_hot_bb_p (loop->header))
 306     {
 307       if (dump_file)
 308         fprintf (dump_file, ";; Not unswitching, not hot area\n");
 309       return;
 310     }
 311
 312   /* Nor if the loop usually does not roll.  */
 313   if (expected_loop_iterations (loop) < 1)
 314     {
 315       if (dump_file)
 316         fprintf (dump_file, ";; Not unswitching, loop iterations < 1\n");
 317       return;
 318     }
 319
 320   do
 321     {
 322       repeat = 0;
 323       cinsn = NULL_RTX;
 324
 325       /* Find a bb to unswitch on.  */
 326       bbs = get_loop_body (loop);
 327       iv_analysis_loop_init (loop);
 328       for (i = 0; i < loop->num_nodes; i++)
 329         if ((cond = may_unswitch_on (bbs[i], loop, &cinsn)))
 330           break;
 331
 332       if (i == loop->num_nodes)
 333         {
 334           free (bbs);
 335           return;
 336         }
 337
 338       if (cond != const0_rtx
 339           && cond != const_true_rtx)
 340         {
 341           rcond = reversed_condition (cond);
 342           if (rcond)
 343             rcond = canon_condition (rcond);
 344
 345           /* Check whether the result can be predicted.  */
 346           for (acond = cond_checked; acond; acond = XEXP (acond, 1))
 347             simplify_using_condition (XEXP (acond, 0), &cond, NULL);
 348         }
 349
 350       if (cond == const_true_rtx)
 351         {
 352           /* Remove false path.  */
 353           e = FALLTHRU_EDGE (bbs[i]);
 354           remove_path (loops, e);
 355           free (bbs);
 356           repeat = 1;
 357         }
 358       else if (cond == const0_rtx)
 359         {
 360           /* Remove true path.  */
 361           e = BRANCH_EDGE (bbs[i]);
 362           remove_path (loops, e);
 363           free (bbs);
 364           repeat = 1;
 365         }
 366     } while (repeat);
 367
 368   /* We found the condition we can unswitch on.  */
 369   conds = alloc_EXPR_LIST (0, cond, cond_checked);
 370   if (rcond)
 371     rconds = alloc_EXPR_LIST (0, rcond, cond_checked);
 372   else
 373     rconds = cond_checked;
 374
 375   if (dump_file)
 376     fprintf (dump_file, ";; Unswitching loop\n");
 377
 378   /* Unswitch the loop on this condition.  */
 379   nloop = unswitch_loop (loops, loop, bbs[i], cond, cinsn);
 380   gcc_assert (nloop);
 381
 382   /* Invoke itself on modified loops.  */
 383   unswitch_single_loop (loops, nloop, rconds, num + 1);
 384   unswitch_single_loop (loops, loop, conds, num + 1);
 385
 386   free_EXPR_LIST_node (conds);
 387   if (rcond)
 388     free_EXPR_LIST_node (rconds);
 389
 390   free (bbs);
 391 }
 392
 393 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
 394    unswitching of innermost loops.  UNSWITCH_ON must be executed in every
 395    iteration, i.e. it must dominate LOOP latch.  COND is the condition
 396    determining which loop is entered.  Returns NULL if impossible, new loop
 397    otherwise.  The new loop is entered if COND is true.  If CINSN is not
 398    NULL, it is the insn in that COND is compared.  */
 399
 400 static struct loop *
 401 unswitch_loop (struct loops *loops, struct loop *loop, basic_block unswitch_on,
 402                rtx cond, rtx cinsn)
 403 {
 404   edge entry, latch_edge, true_edge, false_edge, e;
 405   basic_block switch_bb, unswitch_on_alt;
 406   struct loop *nloop;
 407   sbitmap zero_bitmap;
 408   int irred_flag, prob;
 409   rtx seq;
 410
 411   /* Some sanity checking.  */
 412   gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
 413   gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
 414   gcc_assert (just_once_each_iteration_p (loop, unswitch_on));
 415   gcc_assert (!loop->inner);
 416   gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 0)->dest));
 417   gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 1)->dest));
 418
 419   entry = loop_preheader_edge (loop);
 420
 421   /* Make a copy.  */
 422   irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
 423   entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 424   zero_bitmap = sbitmap_alloc (2);
 425   sbitmap_zero (zero_bitmap);
 426   if (!duplicate_loop_to_header_edge (loop, entry, loops, 1,
 427         zero_bitmap, NULL, NULL, NULL, 0))
 428     {
 429       sbitmap_free (zero_bitmap);
 430       return NULL;
 431     }
 432   sbitmap_free (zero_bitmap);
 433   entry->flags |= irred_flag;
 434
 435   /* Record the block with condition we unswitch on.  */
 436   unswitch_on_alt = get_bb_copy (unswitch_on);
 437   true_edge = BRANCH_EDGE (unswitch_on_alt);
 438   false_edge = FALLTHRU_EDGE (unswitch_on);
 439   latch_edge = single_succ_edge (get_bb_copy (loop->latch));
 440
 441   /* Create a block with the condition.  */
 442   prob = true_edge->probability;
 443   switch_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
 444   seq = compare_and_jump_seq (XEXP (cond, 0), XEXP (cond, 1), GET_CODE (cond),
 445                               block_label (true_edge->dest),
 446                               prob, cinsn);
 447   emit_insn_after (seq, BB_END (switch_bb));
 448   e = make_edge (switch_bb, true_edge->dest, 0);
 449   e->probability = prob;
 450   e->count = latch_edge->count * prob / REG_BR_PROB_BASE;
 451   e = make_edge (switch_bb, FALLTHRU_EDGE (unswitch_on)->dest, EDGE_FALLTHRU);
 452   e->probability = false_edge->probability;
 453   e->count = latch_edge->count * (false_edge->probability) / REG_BR_PROB_BASE;
 454
 455   if (irred_flag)
 456     {
 457       switch_bb->flags |= BB_IRREDUCIBLE_LOOP;
 458       EDGE_SUCC (switch_bb, 0)->flags |= EDGE_IRREDUCIBLE_LOOP;
 459       EDGE_SUCC (switch_bb, 1)->flags |= EDGE_IRREDUCIBLE_LOOP;
 460     }
 461   else
 462     {
 463       switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP;
 464       EDGE_SUCC (switch_bb, 0)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 465       EDGE_SUCC (switch_bb, 1)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 466     }
 467
 468   /* Loopify from the copy of LOOP body, constructing the new loop.  */
 469   nloop = loopify (loops, latch_edge,
 470                    single_pred_edge (get_bb_copy (loop->header)), switch_bb,
 471                    BRANCH_EDGE (switch_bb), FALLTHRU_EDGE (switch_bb), true);
 472
 473   /* Remove branches that are now unreachable in new loops.  */
 474   remove_path (loops, true_edge);
 475   remove_path (loops, false_edge);
 476
 477   /* One of created loops do not have to be subloop of the outer loop now,
 478      so fix its placement in loop data structure.  */
 479   fix_loop_placement (loop);
 480   fix_loop_placement (nloop);
 481
 482   /* Preserve the simple loop preheaders.  */
 483   loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
 484   loop_split_edge_with (loop_preheader_edge (nloop), NULL_RTX);
 485
 486   return nloop;
 487 }