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 "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 loop *, basic_block, rtx, rtx);
  83 static void unswitch_single_loop (struct loop *, rtx, int);
  84 static rtx may_unswitch_on (basic_block, struct loop *, rtx *);
  85
  86 /* Prepare a sequence comparing OP0 with OP1 using COMP and jumping to LABEL if
  87    true, with probability PROB.  If CINSN is not NULL, it is the insn to copy
  88    in order to create a jump.  */
  89
  90 rtx
  91 compare_and_jump_seq (rtx op0, rtx op1, enum rtx_code comp, rtx label, int prob,
  92                       rtx cinsn)
  93 {
  94   rtx seq, jump, cond;
  95   enum machine_mode mode;
  96
  97   mode = GET_MODE (op0);
  98   if (mode == VOIDmode)
  99     mode = GET_MODE (op1);
 100
 101   start_sequence ();
 102   if (GET_MODE_CLASS (mode) == MODE_CC)
 103     {
 104       /* A hack -- there seems to be no easy generic way how to make a
 105          conditional jump from a ccmode comparison.  */
 106       gcc_assert (cinsn);
 107       cond = XEXP (SET_SRC (pc_set (cinsn)), 0);
 108       gcc_assert (GET_CODE (cond) == comp);
 109       gcc_assert (rtx_equal_p (op0, XEXP (cond, 0)));
 110       gcc_assert (rtx_equal_p (op1, XEXP (cond, 1)));
 111       emit_jump_insn (copy_insn (PATTERN (cinsn)));
 112       jump = get_last_insn ();
 113       gcc_assert (JUMP_P (jump));
 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, -1);
 126       jump = get_last_insn ();
 127       gcc_assert (JUMP_P (jump));
 128       JUMP_LABEL (jump) = label;
 129       LABEL_NUSES (label)++;
 130     }
 131   add_reg_note (jump, REG_BR_PROB, GEN_INT (prob));
 132
 133   seq = get_insns ();
 134   end_sequence ();
 135
 136   return seq;
 137 }
 138
 139 /* Main entry point.  Perform loop unswitching on all suitable loops.  */
 140 void
 141 unswitch_loops (void)
 142 {
 143   loop_iterator li;
 144   struct loop *loop;
 145
 146   /* Go through inner loops (only original ones).  */
 147
 148   FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
 149     {
 150       unswitch_single_loop (loop, NULL_RTX, 0);
 151 #ifdef ENABLE_CHECKING
 152       verify_loop_structure ();
 153 #endif
 154     }
 155
 156   iv_analysis_done ();
 157 }
 158
 159 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
 160    basic blocks (for what it means see comments below).  In case condition
 161    compares loop invariant cc mode register, return the jump in CINSN.  */
 162
 163 static rtx
 164 may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn)
 165 {
 166   rtx test, at, op[2], stest;
 167   struct rtx_iv iv;
 168   unsigned i;
 169   enum machine_mode mode;
 170
 171   /* BB must end in a simple conditional jump.  */
 172   if (EDGE_COUNT (bb->succs) != 2)
 173     return NULL_RTX;
 174   if (!any_condjump_p (BB_END (bb)))
 175     return NULL_RTX;
 176
 177   /* With branches inside loop.  */
 178   if (!flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 0)->dest)
 179       || !flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 1)->dest))
 180     return NULL_RTX;
 181
 182   /* It must be executed just once each iteration (because otherwise we
 183      are unable to update dominator/irreducible loop information correctly).  */
 184   if (!just_once_each_iteration_p (loop, bb))
 185     return NULL_RTX;
 186
 187   /* Condition must be invariant.  */
 188   test = get_condition (BB_END (bb), &at, true, false);
 189   if (!test)
 190     return NULL_RTX;
 191
 192   for (i = 0; i < 2; i++)
 193     {
 194       op[i] = XEXP (test, i);
 195
 196       if (CONSTANT_P (op[i]))
 197         continue;
 198
 199       if (!iv_analyze (at, op[i], &iv))
 200         return NULL_RTX;
 201       if (iv.step != const0_rtx
 202           || iv.first_special)
 203         return NULL_RTX;
 204
 205       op[i] = get_iv_value (&iv, const0_rtx);
 206     }
 207
 208   mode = GET_MODE (op[0]);
 209   if (mode == VOIDmode)
 210     mode = GET_MODE (op[1]);
 211   if (GET_MODE_CLASS (mode) == MODE_CC)
 212     {
 213       if (at != BB_END (bb))
 214         return NULL_RTX;
 215
 216       if (!rtx_equal_p (op[0], XEXP (test, 0))
 217           || !rtx_equal_p (op[1], XEXP (test, 1)))
 218         return NULL_RTX;
 219
 220       *cinsn = BB_END (bb);
 221       return test;
 222     }
 223
 224   stest = simplify_gen_relational (GET_CODE (test), SImode,
 225                                    mode, op[0], op[1]);
 226   if (stest == const0_rtx
 227       || stest == const_true_rtx)
 228     return stest;
 229
 230   return canon_condition (gen_rtx_fmt_ee (GET_CODE (test), SImode,
 231                                           op[0], op[1]));
 232 }
 233
 234 /* Reverses CONDition; returns NULL if we cannot.  */
 235 rtx
 236 reversed_condition (rtx cond)
 237 {
 238   enum rtx_code reversed;
 239   reversed = reversed_comparison_code (cond, NULL);
 240   if (reversed == UNKNOWN)
 241     return NULL_RTX;
 242   else
 243     return gen_rtx_fmt_ee (reversed,
 244                            GET_MODE (cond), XEXP (cond, 0),
 245                            XEXP (cond, 1));
 246 }
 247
 248 /* Unswitch single LOOP.  COND_CHECKED holds list of conditions we already
 249    unswitched on and are therefore known to be true in this LOOP.  NUM is
 250    number of unswitchings done; do not allow it to grow too much, it is too
 251    easy to create example on that the code would grow exponentially.  */
 252 static void
 253 unswitch_single_loop (struct loop *loop, rtx cond_checked, int num)
 254 {
 255   basic_block *bbs;
 256   struct loop *nloop;
 257   unsigned i;
 258   rtx cond, rcond = NULL_RTX, conds, rconds, acond, cinsn;
 259   int repeat;
 260   edge e;
 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   if (expected_loop_iterations (loop) < 1)
 304     {
 305       if (dump_file)
 306         fprintf (dump_file, ";; Not unswitching, loop iterations < 1\n");
 307       return;
 308     }
 309
 310   do
 311     {
 312       repeat = 0;
 313       cinsn = NULL_RTX;
 314
 315       /* Find a bb to unswitch on.  */
 316       bbs = get_loop_body (loop);
 317       iv_analysis_loop_init (loop);
 318       for (i = 0; i < loop->num_nodes; i++)
 319         if ((cond = may_unswitch_on (bbs[i], loop, &cinsn)))
 320           break;
 321
 322       if (i == loop->num_nodes)
 323         {
 324           free (bbs);
 325           return;
 326         }
 327
 328       if (cond != const0_rtx
 329           && cond != const_true_rtx)
 330         {
 331           rcond = reversed_condition (cond);
 332           if (rcond)
 333             rcond = canon_condition (rcond);
 334
 335           /* Check whether the result can be predicted.  */
 336           for (acond = cond_checked; acond; acond = XEXP (acond, 1))
 337             simplify_using_condition (XEXP (acond, 0), &cond, NULL);
 338         }
 339
 340       if (cond == const_true_rtx)
 341         {
 342           /* Remove false path.  */
 343           e = FALLTHRU_EDGE (bbs[i]);
 344           remove_path (e);
 345           free (bbs);
 346           repeat = 1;
 347         }
 348       else if (cond == const0_rtx)
 349         {
 350           /* Remove true path.  */
 351           e = BRANCH_EDGE (bbs[i]);
 352           remove_path (e);
 353           free (bbs);
 354           repeat = 1;
 355         }
 356     } while (repeat);
 357
 358   /* We found the condition we can unswitch on.  */
 359   conds = alloc_EXPR_LIST (0, cond, cond_checked);
 360   if (rcond)
 361     rconds = alloc_EXPR_LIST (0, rcond, cond_checked);
 362   else
 363     rconds = cond_checked;
 364
 365   if (dump_file)
 366     fprintf (dump_file, ";; Unswitching loop\n");
 367
 368   /* Unswitch the loop on this condition.  */
 369   nloop = unswitch_loop (loop, bbs[i], copy_rtx_if_shared (cond), cinsn);
 370   gcc_assert (nloop);
 371
 372   /* Invoke itself on modified loops.  */
 373   unswitch_single_loop (nloop, rconds, num + 1);
 374   unswitch_single_loop (loop, conds, num + 1);
 375
 376   free_EXPR_LIST_node (conds);
 377   if (rcond)
 378     free_EXPR_LIST_node (rconds);
 379
 380   free (bbs);
 381 }
 382
 383 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
 384    unswitching of innermost loops.  UNSWITCH_ON must be executed in every
 385    iteration, i.e. it must dominate LOOP latch.  COND is the condition
 386    determining which loop is entered.  Returns NULL if impossible, new loop
 387    otherwise.  The new loop is entered if COND is true.  If CINSN is not
 388    NULL, it is the insn in that COND is compared.  */
 389
 390 static struct loop *
 391 unswitch_loop (struct loop *loop, basic_block unswitch_on, rtx cond, rtx cinsn)
 392 {
 393   edge entry, latch_edge, true_edge, false_edge, e;
 394   basic_block switch_bb, unswitch_on_alt;
 395   struct loop *nloop;
 396   int irred_flag, prob;
 397   rtx seq;
 398
 399   /* Some sanity checking.  */
 400   gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
 401   gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
 402   gcc_assert (just_once_each_iteration_p (loop, unswitch_on));
 403   gcc_assert (!loop->inner);
 404   gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 0)->dest));
 405   gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 1)->dest));
 406
 407   entry = loop_preheader_edge (loop);
 408
 409   /* Make a copy.  */
 410   irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
 411   entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 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 }