gcc/loop-unswitch.c

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