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 bool 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_int_reg_note (jump, REG_BR_PROB, 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   struct loop *loop;
 142   bool changed = false;
 143
 144   /* Go through inner loops (only original ones).  */
 145
 146   FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST)
 147     changed |= unswitch_single_loop (loop, NULL_RTX, 0);
 148
 149   iv_analysis_done ();
 150
 151   /* If we unswitched any loop discover new loops that are eventually
 152      exposed by making irreducible regions reducible.  */
 153   if (changed)
 154     {
 155       calculate_dominance_info (CDI_DOMINATORS);
 156       fix_loop_structure (NULL);
 157     }
 158 }
 159
 160 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
 161    basic blocks (for what it means see comments below).  In case condition
 162    compares loop invariant cc mode register, return the jump in CINSN.  */
 163
 164 static rtx
 165 may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn)
 166 {
 167   rtx test, at, op[2], stest;
 168   struct rtx_iv iv;
 169   unsigned i;
 170   enum machine_mode mode;
 171
 172   /* BB must end in a simple conditional jump.  */
 173   if (EDGE_COUNT (bb->succs) != 2)
 174     return NULL_RTX;
 175   if (!any_condjump_p (BB_END (bb)))
 176     return NULL_RTX;
 177
 178   /* With branches inside loop.  */
 179   if (!flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 0)->dest)
 180       || !flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 1)->dest))
 181     return NULL_RTX;
 182
 183   /* It must be executed just once each iteration (because otherwise we
 184      are unable to update dominator/irreducible loop information correctly).  */
 185   if (!just_once_each_iteration_p (loop, bb))
 186     return NULL_RTX;
 187
 188   /* Condition must be invariant.  */
 189   test = get_condition (BB_END (bb), &at, true, false);
 190   if (!test)
 191     return NULL_RTX;
 192
 193   mode = VOIDmode;
 194   for (i = 0; i < 2; i++)
 195     {
 196       op[i] = XEXP (test, i);
 197
 198       if (CONSTANT_P (op[i]))
 199         continue;
 200
 201       if (!iv_analyze (at, op[i], &iv))
 202         return NULL_RTX;
 203       if (iv.step != const0_rtx
 204           || iv.first_special)
 205         return NULL_RTX;
 206
 207       op[i] = get_iv_value (&iv, const0_rtx);
 208       if (iv.extend != IV_UNKNOWN_EXTEND
 209           && iv.mode != iv.extend_mode)
 210         op[i] = lowpart_subreg (iv.mode, op[i], iv.extend_mode);
 211       if (mode == VOIDmode)
 212         mode = iv.mode;
 213       else
 214         gcc_assert (mode == iv.mode);
 215     }
 216
 217   if (GET_MODE_CLASS (mode) == MODE_CC)
 218     {
 219       if (at != BB_END (bb))
 220         return NULL_RTX;
 221
 222       if (!rtx_equal_p (op[0], XEXP (test, 0))
 223           || !rtx_equal_p (op[1], XEXP (test, 1)))
 224         return NULL_RTX;
 225
 226       *cinsn = BB_END (bb);
 227       return test;
 228     }
 229
 230   stest = simplify_gen_relational (GET_CODE (test), SImode,
 231                                    mode, op[0], op[1]);
 232   if (stest == const0_rtx
 233       || stest == const_true_rtx)
 234     return stest;
 235
 236   return canon_condition (gen_rtx_fmt_ee (GET_CODE (test), SImode,
 237                                           op[0], op[1]));
 238 }
 239
 240 /* Reverses CONDition; returns NULL if we cannot.  */
 241 rtx
 242 reversed_condition (rtx cond)
 243 {
 244   enum rtx_code reversed;
 245   reversed = reversed_comparison_code (cond, NULL);
 246   if (reversed == UNKNOWN)
 247     return NULL_RTX;
 248   else
 249     return gen_rtx_fmt_ee (reversed,
 250                            GET_MODE (cond), XEXP (cond, 0),
 251                            XEXP (cond, 1));
 252 }
 253
 254 /* Unswitch single LOOP.  COND_CHECKED holds list of conditions we already
 255    unswitched on and are therefore known to be true in this LOOP.  NUM is
 256    number of unswitchings done; do not allow it to grow too much, it is too
 257    easy to create example on that the code would grow exponentially.
 258    Returns true LOOP was unswitched.  */
 259 static bool
 260 unswitch_single_loop (struct loop *loop, rtx cond_checked, int num)
 261 {
 262   basic_block *bbs;
 263   struct loop *nloop;
 264   unsigned i;
 265   rtx cond, rcond = NULL_RTX, conds, rconds, acond, cinsn;
 266   int repeat;
 267   edge e;
 268   HOST_WIDE_INT iterations;
 269
 270   /* Do not unswitch too much.  */
 271   if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
 272     {
 273       if (dump_file)
 274         fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
 275       return false;
 276     }
 277
 278   /* Only unswitch innermost loops.  */
 279   if (loop->inner)
 280     {
 281       if (dump_file)
 282         fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
 283       return false;
 284     }
 285
 286   /* We must be able to duplicate loop body.  */
 287   if (!can_duplicate_loop_p (loop))
 288     {
 289       if (dump_file)
 290         fprintf (dump_file, ";; Not unswitching, can't duplicate loop\n");
 291       return false;
 292     }
 293
 294   /* The loop should not be too large, to limit code growth.  */
 295   if (num_loop_insns (loop) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
 296     {
 297       if (dump_file)
 298         fprintf (dump_file, ";; Not unswitching, loop too big\n");
 299       return false;
 300     }
 301
 302   /* Do not unswitch in cold areas.  */
 303   if (optimize_loop_for_size_p (loop))
 304     {
 305       if (dump_file)
 306         fprintf (dump_file, ";; Not unswitching, not hot area\n");
 307       return false;
 308     }
 309
 310   /* Nor if the loop usually does not roll.  */
 311   iterations = get_estimated_loop_iterations_int (loop);
 312   if (iterations >= 0 && iterations <= 1)
 313     {
 314       if (dump_file)
 315         fprintf (dump_file, ";; Not unswitching, loop iterations < 1\n");
 316       return false;
 317     }
 318
 319   do
 320     {
 321       repeat = 0;
 322       cinsn = NULL_RTX;
 323
 324       /* Find a bb to unswitch on.  */
 325       bbs = get_loop_body (loop);
 326       iv_analysis_loop_init (loop);
 327       for (i = 0; i < loop->num_nodes; i++)
 328         if ((cond = may_unswitch_on (bbs[i], loop, &cinsn)))
 329           break;
 330
 331       if (i == loop->num_nodes)
 332         {
 333           free (bbs);
 334           return false;
 335         }
 336
 337       if (cond != const0_rtx
 338           && cond != const_true_rtx)
 339         {
 340           rcond = reversed_condition (cond);
 341           if (rcond)
 342             rcond = canon_condition (rcond);
 343
 344           /* Check whether the result can be predicted.  */
 345           for (acond = cond_checked; acond; acond = XEXP (acond, 1))
 346             simplify_using_condition (XEXP (acond, 0), &cond, NULL);
 347         }
 348
 349       if (cond == const_true_rtx)
 350         {
 351           /* Remove false path.  */
 352           e = FALLTHRU_EDGE (bbs[i]);
 353           remove_path (e);
 354           free (bbs);
 355           repeat = 1;
 356         }
 357       else if (cond == const0_rtx)
 358         {
 359           /* Remove true path.  */
 360           e = BRANCH_EDGE (bbs[i]);
 361           remove_path (e);
 362           free (bbs);
 363           repeat = 1;
 364         }
 365     } while (repeat);
 366
 367   /* We found the condition we can unswitch on.  */
 368   conds = alloc_EXPR_LIST (0, cond, cond_checked);
 369   if (rcond)
 370     rconds = alloc_EXPR_LIST (0, rcond, cond_checked);
 371   else
 372     rconds = cond_checked;
 373
 374   if (dump_file)
 375     fprintf (dump_file, ";; Unswitching loop\n");
 376
 377   /* Unswitch the loop on this condition.  */
 378   nloop = unswitch_loop (loop, bbs[i], copy_rtx_if_shared (cond), cinsn);
 379   gcc_assert (nloop);
 380
 381   /* Invoke itself on modified loops.  */
 382   unswitch_single_loop (nloop, rconds, num + 1);
 383   unswitch_single_loop (loop, conds, num + 1);
 384
 385   free_EXPR_LIST_node (conds);
 386   if (rcond)
 387     free_EXPR_LIST_node (rconds);
 388
 389   free (bbs);
 390
 391   return true;
 392 }
 393
 394 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
 395    unswitching of innermost loops.  UNSWITCH_ON must be executed in every
 396    iteration, i.e. it must dominate LOOP latch.  COND is the condition
 397    determining which loop is entered.  Returns NULL if impossible, new loop
 398    otherwise.  The new loop is entered if COND is true.  If CINSN is not
 399    NULL, it is the insn in that COND is compared.  */
 400
 401 static struct loop *
 402 unswitch_loop (struct loop *loop, basic_block unswitch_on, 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   int irred_flag, prob;
 408   rtx seq;
 409
 410   /* Some sanity checking.  */
 411   gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
 412   gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
 413   gcc_assert (just_once_each_iteration_p (loop, unswitch_on));
 414   gcc_assert (!loop->inner);
 415   gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 0)->dest));
 416   gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 1)->dest));
 417
 418   entry = loop_preheader_edge (loop);
 419
 420   /* Make a copy.  */
 421   irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
 422   entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 423   if (!duplicate_loop_to_header_edge (loop, entry, 1,
 424                                       NULL, NULL, NULL, 0))
 425     return NULL;
 426   entry->flags |= irred_flag;
 427
 428   /* Record the block with condition we unswitch on.  */
 429   unswitch_on_alt = get_bb_copy (unswitch_on);
 430   true_edge = BRANCH_EDGE (unswitch_on_alt);
 431   false_edge = FALLTHRU_EDGE (unswitch_on);
 432   latch_edge = single_succ_edge (get_bb_copy (loop->latch));
 433
 434   /* Create a block with the condition.  */
 435   prob = true_edge->probability;
 436   switch_bb = create_empty_bb (EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
 437   seq = compare_and_jump_seq (XEXP (cond, 0), XEXP (cond, 1), GET_CODE (cond),
 438                               block_label (true_edge->dest),
 439                               prob, cinsn);
 440   emit_insn_after (seq, BB_END (switch_bb));
 441   e = make_edge (switch_bb, true_edge->dest, 0);
 442   e->probability = prob;
 443   e->count = apply_probability (latch_edge->count, prob);
 444   e = make_edge (switch_bb, FALLTHRU_EDGE (unswitch_on)->dest, EDGE_FALLTHRU);
 445   e->probability = false_edge->probability;
 446   e->count = apply_probability (latch_edge->count, false_edge->probability);
 447
 448   if (irred_flag)
 449     {
 450       switch_bb->flags |= BB_IRREDUCIBLE_LOOP;
 451       EDGE_SUCC (switch_bb, 0)->flags |= EDGE_IRREDUCIBLE_LOOP;
 452       EDGE_SUCC (switch_bb, 1)->flags |= EDGE_IRREDUCIBLE_LOOP;
 453     }
 454   else
 455     {
 456       switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP;
 457       EDGE_SUCC (switch_bb, 0)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 458       EDGE_SUCC (switch_bb, 1)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 459     }
 460
 461   /* Loopify from the copy of LOOP body, constructing the new loop.  */
 462   nloop = loopify (latch_edge,
 463                    single_pred_edge (get_bb_copy (loop->header)), switch_bb,
 464                    BRANCH_EDGE (switch_bb), FALLTHRU_EDGE (switch_bb), true,
 465                    prob, REG_BR_PROB_BASE - prob);
 466
 467   copy_loop_info (loop, nloop);
 468   /* Remove branches that are now unreachable in new loops.  */
 469   remove_path (true_edge);
 470   remove_path (false_edge);
 471
 472   /* Preserve the simple loop preheaders.  */
 473   split_edge (loop_preheader_edge (loop));
 474   split_edge (loop_preheader_edge (nloop));
 475
 476   return nloop;
 477 }