gcc/loop-unswitch.c

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