gcc/loop-unswitch.c

   1 /* Loop unswitching for GNU compiler.
   2    Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010, 2012
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  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 "params.h"
  31 #include "expr.h"
  32 #include "dumpfile.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       gcc_assert (JUMP_P (jump));
 113       JUMP_LABEL (jump) = JUMP_LABEL (cinsn);
 114       LABEL_NUSES (JUMP_LABEL (jump))++;
 115       redirect_jump (jump, label, 0);
 116     }
 117   else
 118     {
 119       gcc_assert (!cinsn);
 120
 121       op0 = force_operand (op0, NULL_RTX);
 122       op1 = force_operand (op1, NULL_RTX);
 123       do_compare_rtx_and_jump (op0, op1, comp, 0,
 124                                mode, NULL_RTX, NULL_RTX, label, -1);
 125       jump = get_last_insn ();
 126       gcc_assert (JUMP_P (jump));
 127       JUMP_LABEL (jump) = label;
 128       LABEL_NUSES (label)++;
 129     }
 130   add_reg_note (jump, REG_BR_PROB, GEN_INT (prob));
 131
 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 (void)
 141 {
 142   loop_iterator li;
 143   struct loop *loop;
 144
 145   /* Go through inner loops (only original ones).  */
 146
 147   FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
 148     {
 149       unswitch_single_loop (loop, NULL_RTX, 0);
 150 #ifdef ENABLE_CHECKING
 151       verify_loop_structure ();
 152 #endif
 153     }
 154
 155   iv_analysis_done ();
 156 }
 157
 158 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
 159    basic blocks (for what it means see comments below).  In case condition
 160    compares loop invariant cc mode register, return the jump in CINSN.  */
 161
 162 static rtx
 163 may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn)
 164 {
 165   rtx test, at, op[2], stest;
 166   struct rtx_iv iv;
 167   unsigned i;
 168   enum machine_mode mode;
 169
 170   /* BB must end in a simple conditional jump.  */
 171   if (EDGE_COUNT (bb->succs) != 2)
 172     return NULL_RTX;
 173   if (!any_condjump_p (BB_END (bb)))
 174     return NULL_RTX;
 175
 176   /* With branches inside loop.  */
 177   if (!flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 0)->dest)
 178       || !flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 1)->dest))
 179     return NULL_RTX;
 180
 181   /* It must be executed just once each iteration (because otherwise we
 182      are unable to update dominator/irreducible loop information correctly).  */
 183   if (!just_once_each_iteration_p (loop, bb))
 184     return NULL_RTX;
 185
 186   /* Condition must be invariant.  */
 187   test = get_condition (BB_END (bb), &at, true, false);
 188   if (!test)
 189     return NULL_RTX;
 190
 191   for (i = 0; i < 2; i++)
 192     {
 193       op[i] = XEXP (test, i);
 194
 195       if (CONSTANT_P (op[i]))
 196         continue;
 197
 198       if (!iv_analyze (at, op[i], &iv))
 199         return NULL_RTX;
 200       if (iv.step != const0_rtx
 201           || iv.first_special)
 202         return NULL_RTX;
 203
 204       op[i] = get_iv_value (&iv, const0_rtx);
 205     }
 206
 207   mode = GET_MODE (op[0]);
 208   if (mode == VOIDmode)
 209     mode = GET_MODE (op[1]);
 210   if (GET_MODE_CLASS (mode) == MODE_CC)
 211     {
 212       if (at != BB_END (bb))
 213         return NULL_RTX;
 214
 215       if (!rtx_equal_p (op[0], XEXP (test, 0))
 216           || !rtx_equal_p (op[1], XEXP (test, 1)))
 217         return NULL_RTX;
 218
 219       *cinsn = BB_END (bb);
 220       return test;
 221     }
 222
 223   stest = simplify_gen_relational (GET_CODE (test), SImode,
 224                                    mode, op[0], op[1]);
 225   if (stest == const0_rtx
 226       || stest == const_true_rtx)
 227     return stest;
 228
 229   return canon_condition (gen_rtx_fmt_ee (GET_CODE (test), SImode,
 230                                           op[0], op[1]));
 231 }
 232
 233 /* Reverses CONDition; returns NULL if we cannot.  */
 234 rtx
 235 reversed_condition (rtx cond)
 236 {
 237   enum rtx_code reversed;
 238   reversed = reversed_comparison_code (cond, NULL);
 239   if (reversed == UNKNOWN)
 240     return NULL_RTX;
 241   else
 242     return gen_rtx_fmt_ee (reversed,
 243                            GET_MODE (cond), XEXP (cond, 0),
 244                            XEXP (cond, 1));
 245 }
 246
 247 /* Unswitch single LOOP.  COND_CHECKED holds list of conditions we already
 248    unswitched on and are therefore known to be true in this LOOP.  NUM is
 249    number of unswitchings done; do not allow it to grow too much, it is too
 250    easy to create example on that the code would grow exponentially.  */
 251 static void
 252 unswitch_single_loop (struct loop *loop, rtx cond_checked, int num)
 253 {
 254   basic_block *bbs;
 255   struct loop *nloop;
 256   unsigned i;
 257   rtx cond, rcond = NULL_RTX, conds, rconds, acond, cinsn;
 258   int repeat;
 259   edge e;
 260   HOST_WIDE_INT iterations;
 261
 262   /* Do not unswitch too much.  */
 263   if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
 264     {
 265       if (dump_file)
 266         fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
 267       return;
 268     }
 269
 270   /* Only unswitch innermost loops.  */
 271   if (loop->inner)
 272     {
 273       if (dump_file)
 274         fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
 275       return;
 276     }
 277
 278   /* We must be able to duplicate loop body.  */
 279   if (!can_duplicate_loop_p (loop))
 280     {
 281       if (dump_file)
 282         fprintf (dump_file, ";; Not unswitching, can't duplicate loop\n");
 283       return;
 284     }
 285
 286   /* The loop should not be too large, to limit code growth.  */
 287   if (num_loop_insns (loop) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
 288     {
 289       if (dump_file)
 290         fprintf (dump_file, ";; Not unswitching, loop too big\n");
 291       return;
 292     }
 293
 294   /* Do not unswitch in cold areas.  */
 295   if (optimize_loop_for_size_p (loop))
 296     {
 297       if (dump_file)
 298         fprintf (dump_file, ";; Not unswitching, not hot area\n");
 299       return;
 300     }
 301
 302   /* Nor if the loop usually does not roll.  */
 303   iterations = estimated_loop_iterations_int (loop);
 304   if (iterations >= 0 && iterations <= 1)
 305     {
 306       if (dump_file)
 307         fprintf (dump_file, ";; Not unswitching, loop iterations < 1\n");
 308       return;
 309     }
 310
 311   do
 312     {
 313       repeat = 0;
 314       cinsn = NULL_RTX;
 315
 316       /* Find a bb to unswitch on.  */
 317       bbs = get_loop_body (loop);
 318       iv_analysis_loop_init (loop);
 319       for (i = 0; i < loop->num_nodes; i++)
 320         if ((cond = may_unswitch_on (bbs[i], loop, &cinsn)))
 321           break;
 322
 323       if (i == loop->num_nodes)
 324         {
 325           free (bbs);
 326           return;
 327         }
 328
 329       if (cond != const0_rtx
 330           && cond != const_true_rtx)
 331         {
 332           rcond = reversed_condition (cond);
 333           if (rcond)
 334             rcond = canon_condition (rcond);
 335
 336           /* Check whether the result can be predicted.  */
 337           for (acond = cond_checked; acond; acond = XEXP (acond, 1))
 338             simplify_using_condition (XEXP (acond, 0), &cond, NULL);
 339         }
 340
 341       if (cond == const_true_rtx)
 342         {
 343           /* Remove false path.  */
 344           e = FALLTHRU_EDGE (bbs[i]);
 345           remove_path (e);
 346           free (bbs);
 347           repeat = 1;
 348         }
 349       else if (cond == const0_rtx)
 350         {
 351           /* Remove true path.  */
 352           e = BRANCH_EDGE (bbs[i]);
 353           remove_path (e);
 354           free (bbs);
 355           repeat = 1;
 356         }
 357     } while (repeat);
 358
 359   /* We found the condition we can unswitch on.  */
 360   conds = alloc_EXPR_LIST (0, cond, cond_checked);
 361   if (rcond)
 362     rconds = alloc_EXPR_LIST (0, rcond, cond_checked);
 363   else
 364     rconds = cond_checked;
 365
 366   if (dump_file)
 367     fprintf (dump_file, ";; Unswitching loop\n");
 368
 369   /* Unswitch the loop on this condition.  */
 370   nloop = unswitch_loop (loop, bbs[i], copy_rtx_if_shared (cond), cinsn);
 371   gcc_assert (nloop);
 372
 373   /* Invoke itself on modified loops.  */
 374   unswitch_single_loop (nloop, rconds, num + 1);
 375   unswitch_single_loop (loop, conds, num + 1);
 376
 377   free_EXPR_LIST_node (conds);
 378   if (rcond)
 379     free_EXPR_LIST_node (rconds);
 380
 381   free (bbs);
 382 }
 383
 384 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
 385    unswitching of innermost loops.  UNSWITCH_ON must be executed in every
 386    iteration, i.e. it must dominate LOOP latch.  COND is the condition
 387    determining which loop is entered.  Returns NULL if impossible, new loop
 388    otherwise.  The new loop is entered if COND is true.  If CINSN is not
 389    NULL, it is the insn in that COND is compared.  */
 390
 391 static struct loop *
 392 unswitch_loop (struct loop *loop, basic_block unswitch_on, rtx cond, rtx cinsn)
 393 {
 394   edge entry, latch_edge, true_edge, false_edge, e;
 395   basic_block switch_bb, unswitch_on_alt;
 396   struct loop *nloop;
 397   int irred_flag, prob;
 398   rtx seq;
 399
 400   /* Some sanity checking.  */
 401   gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
 402   gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
 403   gcc_assert (just_once_each_iteration_p (loop, unswitch_on));
 404   gcc_assert (!loop->inner);
 405   gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 0)->dest));
 406   gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 1)->dest));
 407
 408   entry = loop_preheader_edge (loop);
 409
 410   /* Make a copy.  */
 411   irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
 412   entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 413   if (!duplicate_loop_to_header_edge (loop, entry, 1,
 414                                       NULL, NULL, NULL, 0))
 415     return NULL;
 416   entry->flags |= irred_flag;
 417
 418   /* Record the block with condition we unswitch on.  */
 419   unswitch_on_alt = get_bb_copy (unswitch_on);
 420   true_edge = BRANCH_EDGE (unswitch_on_alt);
 421   false_edge = FALLTHRU_EDGE (unswitch_on);
 422   latch_edge = single_succ_edge (get_bb_copy (loop->latch));
 423
 424   /* Create a block with the condition.  */
 425   prob = true_edge->probability;
 426   switch_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
 427   seq = compare_and_jump_seq (XEXP (cond, 0), XEXP (cond, 1), GET_CODE (cond),
 428                               block_label (true_edge->dest),
 429                               prob, cinsn);
 430   emit_insn_after (seq, BB_END (switch_bb));
 431   e = make_edge (switch_bb, true_edge->dest, 0);
 432   e->probability = prob;
 433   e->count = latch_edge->count * prob / REG_BR_PROB_BASE;
 434   e = make_edge (switch_bb, FALLTHRU_EDGE (unswitch_on)->dest, EDGE_FALLTHRU);
 435   e->probability = false_edge->probability;
 436   e->count = latch_edge->count * (false_edge->probability) / REG_BR_PROB_BASE;
 437
 438   if (irred_flag)
 439     {
 440       switch_bb->flags |= BB_IRREDUCIBLE_LOOP;
 441       EDGE_SUCC (switch_bb, 0)->flags |= EDGE_IRREDUCIBLE_LOOP;
 442       EDGE_SUCC (switch_bb, 1)->flags |= EDGE_IRREDUCIBLE_LOOP;
 443     }
 444   else
 445     {
 446       switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP;
 447       EDGE_SUCC (switch_bb, 0)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 448       EDGE_SUCC (switch_bb, 1)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 449     }
 450
 451   /* Loopify from the copy of LOOP body, constructing the new loop.  */
 452   nloop = loopify (latch_edge,
 453                    single_pred_edge (get_bb_copy (loop->header)), switch_bb,
 454                    BRANCH_EDGE (switch_bb), FALLTHRU_EDGE (switch_bb), true,
 455                    prob, REG_BR_PROB_BASE - prob);
 456
 457   copy_loop_info (loop, nloop);
 458   /* Remove branches that are now unreachable in new loops.  */
 459   remove_path (true_edge);
 460   remove_path (false_edge);
 461
 462   /* Preserve the simple loop preheaders.  */
 463   split_edge (loop_preheader_edge (loop));
 464   split_edge (loop_preheader_edge (nloop));
 465
 466   return nloop;
 467 }