gcc/loop-unswitch.c

   1 /* Loop unswitching for GNU compiler.
   2    Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008
   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       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);
 125       jump = get_last_insn ();
 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
 144   /* Go through inner loops (only original ones).  */
 145
 146   FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
 147     {
 148       unswitch_single_loop (loop, NULL_RTX, 0);
 149 #ifdef ENABLE_CHECKING
 150       verify_dominators (CDI_DOMINATORS);
 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
 261   /* Do not unswitch too much.  */
 262   if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
 263     {
 264       if (dump_file)
 265         fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
 266       return;
 267     }
 268
 269   /* Only unswitch innermost loops.  */
 270   if (loop->inner)
 271     {
 272       if (dump_file)
 273         fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
 274       return;
 275     }
 276
 277   /* We must be able to duplicate loop body.  */
 278   if (!can_duplicate_loop_p (loop))
 279     {
 280       if (dump_file)
 281         fprintf (dump_file, ";; Not unswitching, can't duplicate loop\n");
 282       return;
 283     }
 284
 285   /* The loop should not be too large, to limit code growth.  */
 286   if (num_loop_insns (loop) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
 287     {
 288       if (dump_file)
 289         fprintf (dump_file, ";; Not unswitching, loop too big\n");
 290       return;
 291     }
 292
 293   /* Do not unswitch in cold areas.  */
 294   if (optimize_loop_for_size_p (loop))
 295     {
 296       if (dump_file)
 297         fprintf (dump_file, ";; Not unswitching, not hot area\n");
 298       return;
 299     }
 300
 301   /* Nor if the loop usually does not roll.  */
 302   if (expected_loop_iterations (loop) < 1)
 303     {
 304       if (dump_file)
 305         fprintf (dump_file, ";; Not unswitching, loop iterations < 1\n");
 306       return;
 307     }
 308
 309   do
 310     {
 311       repeat = 0;
 312       cinsn = NULL_RTX;
 313
 314       /* Find a bb to unswitch on.  */
 315       bbs = get_loop_body (loop);
 316       iv_analysis_loop_init (loop);
 317       for (i = 0; i < loop->num_nodes; i++)
 318         if ((cond = may_unswitch_on (bbs[i], loop, &cinsn)))
 319           break;
 320
 321       if (i == loop->num_nodes)
 322         {
 323           free (bbs);
 324           return;
 325         }
 326
 327       if (cond != const0_rtx
 328           && cond != const_true_rtx)
 329         {
 330           rcond = reversed_condition (cond);
 331           if (rcond)
 332             rcond = canon_condition (rcond);
 333
 334           /* Check whether the result can be predicted.  */
 335           for (acond = cond_checked; acond; acond = XEXP (acond, 1))
 336             simplify_using_condition (XEXP (acond, 0), &cond, NULL);
 337         }
 338
 339       if (cond == const_true_rtx)
 340         {
 341           /* Remove false path.  */
 342           e = FALLTHRU_EDGE (bbs[i]);
 343           remove_path (e);
 344           free (bbs);
 345           repeat = 1;
 346         }
 347       else if (cond == const0_rtx)
 348         {
 349           /* Remove true path.  */
 350           e = BRANCH_EDGE (bbs[i]);
 351           remove_path (e);
 352           free (bbs);
 353           repeat = 1;
 354         }
 355     } while (repeat);
 356
 357   /* We found the condition we can unswitch on.  */
 358   conds = alloc_EXPR_LIST (0, cond, cond_checked);
 359   if (rcond)
 360     rconds = alloc_EXPR_LIST (0, rcond, cond_checked);
 361   else
 362     rconds = cond_checked;
 363
 364   if (dump_file)
 365     fprintf (dump_file, ";; Unswitching loop\n");
 366
 367   /* Unswitch the loop on this condition.  */
 368   nloop = unswitch_loop (loop, bbs[i], cond, cinsn);
 369   gcc_assert (nloop);
 370
 371   /* Invoke itself on modified loops.  */
 372   unswitch_single_loop (nloop, rconds, num + 1);
 373   unswitch_single_loop (loop, conds, num + 1);
 374
 375   free_EXPR_LIST_node (conds);
 376   if (rcond)
 377     free_EXPR_LIST_node (rconds);
 378
 379   free (bbs);
 380 }
 381
 382 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
 383    unswitching of innermost loops.  UNSWITCH_ON must be executed in every
 384    iteration, i.e. it must dominate LOOP latch.  COND is the condition
 385    determining which loop is entered.  Returns NULL if impossible, new loop
 386    otherwise.  The new loop is entered if COND is true.  If CINSN is not
 387    NULL, it is the insn in that COND is compared.  */
 388
 389 static struct loop *
 390 unswitch_loop (struct loop *loop, basic_block unswitch_on, rtx cond, rtx cinsn)
 391 {
 392   edge entry, latch_edge, true_edge, false_edge, e;
 393   basic_block switch_bb, unswitch_on_alt;
 394   struct loop *nloop;
 395   sbitmap zero_bitmap;
 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   zero_bitmap = sbitmap_alloc (2);
 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 }