gcc/loop-unswitch.c

   1 /* Loop unswitching for GNU compiler.
   2    Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010
   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_dominators (CDI_DOMINATORS);
 153       verify_loop_structure ();
 154 #endif
 155     }
 156
 157   iv_analysis_done ();
 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   for (i = 0; i < 2; i++)
 194     {
 195       op[i] = XEXP (test, i);
 196
 197       if (CONSTANT_P (op[i]))
 198         continue;
 199
 200       if (!iv_analyze (at, op[i], &iv))
 201         return NULL_RTX;
 202       if (iv.step != const0_rtx
 203           || iv.first_special)
 204         return NULL_RTX;
 205
 206       op[i] = get_iv_value (&iv, const0_rtx);
 207     }
 208
 209   mode = GET_MODE (op[0]);
 210   if (mode == VOIDmode)
 211     mode = GET_MODE (op[1]);
 212   if (GET_MODE_CLASS (mode) == MODE_CC)
 213     {
 214       if (at != BB_END (bb))
 215         return NULL_RTX;
 216
 217       if (!rtx_equal_p (op[0], XEXP (test, 0))
 218           || !rtx_equal_p (op[1], XEXP (test, 1)))
 219         return NULL_RTX;
 220
 221       *cinsn = BB_END (bb);
 222       return test;
 223     }
 224
 225   stest = simplify_gen_relational (GET_CODE (test), SImode,
 226                                    mode, op[0], op[1]);
 227   if (stest == const0_rtx
 228       || stest == const_true_rtx)
 229     return stest;
 230
 231   return canon_condition (gen_rtx_fmt_ee (GET_CODE (test), SImode,
 232                                           op[0], op[1]));
 233 }
 234
 235 /* Reverses CONDition; returns NULL if we cannot.  */
 236 rtx
 237 reversed_condition (rtx cond)
 238 {
 239   enum rtx_code reversed;
 240   reversed = reversed_comparison_code (cond, NULL);
 241   if (reversed == UNKNOWN)
 242     return NULL_RTX;
 243   else
 244     return gen_rtx_fmt_ee (reversed,
 245                            GET_MODE (cond), XEXP (cond, 0),
 246                            XEXP (cond, 1));
 247 }
 248
 249 /* Unswitch single LOOP.  COND_CHECKED holds list of conditions we already
 250    unswitched on and are therefore known to be true in this LOOP.  NUM is
 251    number of unswitchings done; do not allow it to grow too much, it is too
 252    easy to create example on that the code would grow exponentially.  */
 253 static void
 254 unswitch_single_loop (struct loop *loop, rtx cond_checked, int num)
 255 {
 256   basic_block *bbs;
 257   struct loop *nloop;
 258   unsigned i;
 259   rtx cond, rcond = NULL_RTX, conds, rconds, acond, cinsn;
 260   int repeat;
 261   edge e;
 262
 263   /* Do not unswitch too much.  */
 264   if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
 265     {
 266       if (dump_file)
 267         fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
 268       return;
 269     }
 270
 271   /* Only unswitch innermost loops.  */
 272   if (loop->inner)
 273     {
 274       if (dump_file)
 275         fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
 276       return;
 277     }
 278
 279   /* We must be able to duplicate loop body.  */
 280   if (!can_duplicate_loop_p (loop))
 281     {
 282       if (dump_file)
 283         fprintf (dump_file, ";; Not unswitching, can't duplicate loop\n");
 284       return;
 285     }
 286
 287   /* The loop should not be too large, to limit code growth.  */
 288   if (num_loop_insns (loop) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
 289     {
 290       if (dump_file)
 291         fprintf (dump_file, ";; Not unswitching, loop too big\n");
 292       return;
 293     }
 294
 295   /* Do not unswitch in cold areas.  */
 296   if (optimize_loop_for_size_p (loop))
 297     {
 298       if (dump_file)
 299         fprintf (dump_file, ";; Not unswitching, not hot area\n");
 300       return;
 301     }
 302
 303   /* Nor if the loop usually does not roll.  */
 304   if (expected_loop_iterations (loop) < 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], 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   /* Remove branches that are now unreachable in new loops.  */
 458   remove_path (true_edge);
 459   remove_path (false_edge);
 460
 461   /* Preserve the simple loop preheaders.  */
 462   split_edge (loop_preheader_edge (loop));
 463   split_edge (loop_preheader_edge (nloop));
 464
 465   return nloop;
 466 }