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