gcc/loop-unswitch.c

   1 /* Loop unswitching for GNU compiler.
   2    Copyright (C) 2002, 2003, 2004 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 2, 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 COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  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 "basic-block.h"
  28 #include "cfgloop.h"
  29 #include "cfglayout.h"
  30 #include "params.h"
  31 #include "output.h"
  32 #include "expr.h"
  33
  34 /* This pass moves constant conditions out of loops, duplicating the loop
  35    in progress, i.e. this code:
  36
  37    while (loop_cond)
  38      {
  39        A;
  40        if (cond)
  41          branch1;
  42        else
  43          branch2;
  44        B;
  45        if (cond)
  46          branch3;
  47        C;
  48      }
  49    where nothing inside the loop alters cond is transformed
  50    into
  51
  52    if (cond)
  53      {
  54        while (loop_cond)
  55          {
  56            A;
  57            branch1;
  58            B;
  59            branch3;
  60            C;
  61          }
  62      }
  63    else
  64      {
  65        while (loop_cond)
  66          {
  67            A;
  68            branch2;
  69            B;
  70            C;
  71          }
  72      }
  73
  74   Duplicating the loop might lead to code growth exponential in number of
  75   branches inside loop, so we limit the number of unswitchings performed
  76   in a single loop to PARAM_MAX_UNSWITCH_LEVEL.  We only perform the
  77   transformation on innermost loops, as the benefit of doing it on loops
  78   containing subloops would not be very large compared to complications
  79   with handling this case.  */
  80
  81 static struct loop *unswitch_loop (struct loops *, struct loop *,
  82                                    basic_block, rtx, rtx);
  83 static void unswitch_single_loop (struct loops *, 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   REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
 130                                         REG_NOTES (jump));
 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 (struct loops *loops)
 140 {
 141   int i, num;
 142   struct loop *loop;
 143
 144   /* Go through inner loops (only original ones).  */
 145   num = loops->num;
 146
 147   for (i = 1; i < num; i++)
 148     {
 149       /* Removed loop?  */
 150       loop = loops->parray[i];
 151       if (!loop)
 152         continue;
 153
 154       if (loop->inner)
 155         continue;
 156
 157       unswitch_single_loop (loops, loop, NULL_RTX, 0);
 158 #ifdef ENABLE_CHECKING
 159       verify_dominators (CDI_DOMINATORS);
 160       verify_loop_structure (loops);
 161 #endif
 162     }
 163
 164   iv_analysis_done ();
 165 }
 166
 167 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
 168    basic blocks (for what it means see comments below).  In case condition
 169    compares loop invariant cc mode register, return the jump in CINSN.  */
 170
 171 static rtx
 172 may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn)
 173 {
 174   rtx test, at, insn, op[2], stest;
 175   struct rtx_iv iv;
 176   unsigned i;
 177   enum machine_mode mode;
 178
 179   /* BB must end in a simple conditional jump.  */
 180   if (!bb->succ || !bb->succ->succ_next || bb->succ->succ_next->succ_next)
 181     return NULL_RTX;
 182   if (!any_condjump_p (BB_END (bb)))
 183     return NULL_RTX;
 184
 185   /* With branches inside loop.  */
 186   if (!flow_bb_inside_loop_p (loop, bb->succ->dest)
 187       || !flow_bb_inside_loop_p (loop, bb->succ->succ_next->dest))
 188     return NULL_RTX;
 189
 190   /* It must be executed just once each iteration (because otherwise we
 191      are unable to update dominator/irreducible loop information correctly).  */
 192   if (!just_once_each_iteration_p (loop, bb))
 193     return NULL_RTX;
 194
 195   /* Condition must be invariant.  */
 196   test = get_condition (BB_END (bb), &at, true, false);
 197   if (!test)
 198     return NULL_RTX;
 199
 200   for (i = 0; i < 2; i++)
 201     {
 202       op[i] = XEXP (test, i);
 203
 204       if (CONSTANT_P (op[i]))
 205         continue;
 206
 207       insn = iv_get_reaching_def (at, op[i]);
 208       if (!iv_analyze (insn, op[i], &iv))
 209         return NULL_RTX;
 210       if (iv.step != const0_rtx
 211           || iv.first_special)
 212         return NULL_RTX;
 213
 214       op[i] = get_iv_value (&iv, const0_rtx);
 215     }
 216
 217   mode = GET_MODE (op[0]);
 218   if (mode == VOIDmode)
 219     mode = GET_MODE (op[1]);
 220   if (GET_MODE_CLASS (mode) == MODE_CC)
 221     {
 222       if (at != BB_END (bb))
 223         return NULL_RTX;
 224
 225       *cinsn = BB_END (bb);
 226       if (!rtx_equal_p (op[0], XEXP (test, 0))
 227           || !rtx_equal_p (op[1], XEXP (test, 1)))
 228         return NULL_RTX;
 229
 230       return test;
 231     }
 232
 233   stest = simplify_gen_relational (GET_CODE (test), SImode,
 234                                    mode, op[0], op[1]);
 235   if (stest == const0_rtx
 236       || stest == const_true_rtx)
 237     return stest;
 238
 239   return canon_condition (gen_rtx_fmt_ee (GET_CODE (test), SImode,
 240                                           op[0], op[1]));
 241 }
 242
 243 /* Reverses CONDition; returns NULL if we cannot.  */
 244 rtx
 245 reversed_condition (rtx cond)
 246 {
 247   enum rtx_code reversed;
 248   reversed = reversed_comparison_code (cond, NULL);
 249   if (reversed == UNKNOWN)
 250     return NULL_RTX;
 251   else
 252     return gen_rtx_fmt_ee (reversed,
 253                            GET_MODE (cond), XEXP (cond, 0),
 254                            XEXP (cond, 1));
 255 }
 256
 257 /* Unswitch single LOOP.  COND_CHECKED holds list of conditions we already
 258    unswitched on and are therefore known to be true in this LOOP.  NUM is
 259    number of unswitchings done; do not allow it to grow too much, it is too
 260    easy to create example on that the code would grow exponentially.  */
 261 static void
 262 unswitch_single_loop (struct loops *loops, struct loop *loop,
 263                       rtx cond_checked, int num)
 264 {
 265   basic_block *bbs;
 266   struct loop *nloop;
 267   unsigned i;
 268   rtx cond, rcond = NULL_RTX, conds, rconds, acond, cinsn = NULL_RTX;
 269   int repeat;
 270   edge e;
 271
 272   /* Do not unswitch too much.  */
 273   if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
 274     {
 275       if (dump_file)
 276         fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
 277       return;
 278     }
 279
 280   /* Only unswitch innermost loops.  */
 281   if (loop->inner)
 282     {
 283       if (dump_file)
 284         fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
 285       return;
 286     }
 287
 288   /* We must be able to duplicate loop body.  */
 289   if (!can_duplicate_loop_p (loop))
 290     {
 291       if (dump_file)
 292         fprintf (dump_file, ";; Not unswitching, can't duplicate loop\n");
 293       return;
 294     }
 295
 296   /* The loop should not be too large, to limit code growth.  */
 297   if (num_loop_insns (loop) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
 298     {
 299       if (dump_file)
 300         fprintf (dump_file, ";; Not unswitching, loop too big\n");
 301       return;
 302     }
 303
 304   /* Do not unswitch in cold areas.  */
 305   if (!maybe_hot_bb_p (loop->header))
 306     {
 307       if (dump_file)
 308         fprintf (dump_file, ";; Not unswitching, not hot area\n");
 309       return;
 310     }
 311
 312   /* Nor if the loop usually does not roll.  */
 313   if (expected_loop_iterations (loop) < 1)
 314     {
 315       if (dump_file)
 316         fprintf (dump_file, ";; Not unswitching, loop iterations < 1\n");
 317       return;
 318     }
 319
 320   do
 321     {
 322       repeat = 0;
 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;
 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 (loops, 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 (loops, 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 (loops, loop, bbs[i], cond, cinsn);
 379   gcc_assert (nloop);
 380
 381   /* Invoke itself on modified loops.  */
 382   unswitch_single_loop (loops, nloop, rconds, num + 1);
 383   unswitch_single_loop (loops, 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
 392 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
 393    unswitching of innermost loops.  UNSWITCH_ON must be executed in every
 394    iteration, i.e. it must dominate LOOP latch.  COND is the condition
 395    determining which loop is entered.  Returns NULL if impossible, new loop
 396    otherwise.  The new loop is entered if COND is true.  If CINSN is not
 397    NULL, it is the insn in that COND is compared.  */
 398
 399 static struct loop *
 400 unswitch_loop (struct loops *loops, struct loop *loop, basic_block unswitch_on,
 401                rtx cond, rtx cinsn)
 402 {
 403   edge entry, latch_edge, true_edge, false_edge, e;
 404   basic_block switch_bb, unswitch_on_alt, src;
 405   struct loop *nloop;
 406   sbitmap zero_bitmap;
 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
 413   gcc_assert (unswitch_on->succ);
 414   gcc_assert (unswitch_on->succ->succ_next);
 415   gcc_assert (!unswitch_on->succ->succ_next->succ_next);
 416
 417   gcc_assert (just_once_each_iteration_p (loop, unswitch_on));
 418   gcc_assert (!loop->inner);
 419   gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on->succ->dest));
 420   gcc_assert (flow_bb_inside_loop_p (loop,
 421                                      unswitch_on->succ->succ_next->dest));
 422
 423   entry = loop_preheader_edge (loop);
 424
 425   /* Make a copy.  */
 426   src = entry->src;
 427   irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
 428   entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 429   zero_bitmap = sbitmap_alloc (2);
 430   sbitmap_zero (zero_bitmap);
 431   if (!duplicate_loop_to_header_edge (loop, entry, loops, 1,
 432         zero_bitmap, NULL, NULL, NULL, 0))
 433     return NULL;
 434   free (zero_bitmap);
 435   entry->flags |= irred_flag;
 436
 437   /* Record the block with condition we unswitch on.  */
 438   unswitch_on_alt = unswitch_on->rbi->copy;
 439   true_edge = BRANCH_EDGE (unswitch_on_alt);
 440   false_edge = FALLTHRU_EDGE (unswitch_on);
 441   latch_edge = loop->latch->rbi->copy->succ;
 442
 443   /* Create a block with the condition.  */
 444   prob = true_edge->probability;
 445   switch_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
 446   seq = compare_and_jump_seq (XEXP (cond, 0), XEXP (cond, 1), GET_CODE (cond),
 447                               block_label (true_edge->dest),
 448                               prob, cinsn);
 449   emit_insn_after (seq, BB_END (switch_bb));
 450   e = make_edge (switch_bb, true_edge->dest, 0);
 451   e->probability = prob;
 452   e->count = latch_edge->count * prob / REG_BR_PROB_BASE;
 453   e = make_edge (switch_bb, FALLTHRU_EDGE (unswitch_on)->dest, EDGE_FALLTHRU);
 454   e->probability = false_edge->probability;
 455   e->count = latch_edge->count * (false_edge->probability) / REG_BR_PROB_BASE;
 456
 457   if (irred_flag)
 458     {
 459       switch_bb->flags |= BB_IRREDUCIBLE_LOOP;
 460       switch_bb->succ->flags |= EDGE_IRREDUCIBLE_LOOP;
 461       switch_bb->succ->succ_next->flags |= EDGE_IRREDUCIBLE_LOOP;
 462     }
 463   else
 464     {
 465       switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP;
 466       switch_bb->succ->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 467       switch_bb->succ->succ_next->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 468     }
 469
 470   /* Loopify from the copy of LOOP body, constructing the new loop.  */
 471   nloop = loopify (loops, latch_edge,
 472                    loop->header->rbi->copy->pred, switch_bb);
 473
 474   /* Remove branches that are now unreachable in new loops.  */
 475   remove_path (loops, true_edge);
 476   remove_path (loops, false_edge);
 477
 478   /* One of created loops do not have to be subloop of the outer loop now,
 479      so fix its placement in loop data structure.  */
 480   fix_loop_placement (loop);
 481   fix_loop_placement (nloop);
 482
 483   /* Preserve the simple loop preheaders.  */
 484   loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
 485   loop_split_edge_with (loop_preheader_edge (nloop), NULL_RTX);
 486
 487   return nloop;
 488 }