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       if (!cinsn)
 107         abort ();
 108       cond = XEXP (SET_SRC (pc_set (cinsn)), 0);
 109       if (GET_CODE (cond) != comp
 110           || !rtx_equal_p (op0, XEXP (cond, 0))
 111           || !rtx_equal_p (op1, XEXP (cond, 1)))
 112         abort ();
 113       emit_jump_insn (copy_insn (PATTERN (cinsn)));
 114       jump = get_last_insn ();
 115       JUMP_LABEL (jump) = JUMP_LABEL (cinsn);
 116       LABEL_NUSES (JUMP_LABEL (jump))++;
 117       redirect_jump (jump, label, 0);
 118     }
 119   else
 120     {
 121       if (cinsn)
 122         abort ();
 123
 124       op0 = force_operand (op0, NULL_RTX);
 125       op1 = force_operand (op1, NULL_RTX);
 126       do_compare_rtx_and_jump (op0, op1, comp, 0,
 127                                mode, NULL_RTX, NULL_RTX, label);
 128       jump = get_last_insn ();
 129       JUMP_LABEL (jump) = label;
 130       LABEL_NUSES (label)++;
 131     }
 132   REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
 133                                         REG_NOTES (jump));
 134   seq = get_insns ();
 135   end_sequence ();
 136
 137   return seq;
 138 }
 139
 140 /* Main entry point.  Perform loop unswitching on all suitable LOOPS.  */
 141 void
 142 unswitch_loops (struct loops *loops)
 143 {
 144   int i, num;
 145   struct loop *loop;
 146
 147   /* Go through inner loops (only original ones).  */
 148   num = loops->num;
 149
 150   for (i = 1; i < num; i++)
 151     {
 152       /* Removed loop?  */
 153       loop = loops->parray[i];
 154       if (!loop)
 155         continue;
 156
 157       if (loop->inner)
 158         continue;
 159
 160       unswitch_single_loop (loops, loop, NULL_RTX, 0);
 161 #ifdef ENABLE_CHECKING
 162       verify_dominators (CDI_DOMINATORS);
 163       verify_loop_structure (loops);
 164 #endif
 165     }
 166
 167   iv_analysis_done ();
 168 }
 169
 170 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
 171    basic blocks (for what it means see comments below).  In case condition
 172    compares loop invariant cc mode register, return the jump in CINSN.  */
 173
 174 static rtx
 175 may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn)
 176 {
 177   rtx test, at, insn, op[2];
 178   struct rtx_iv iv;
 179   unsigned i;
 180   enum machine_mode mode;
 181
 182   /* BB must end in a simple conditional jump.  */
 183   if (!bb->succ || !bb->succ->succ_next || bb->succ->succ_next->succ_next)
 184     return NULL_RTX;
 185   if (!any_condjump_p (BB_END (bb)))
 186     return NULL_RTX;
 187
 188   /* With branches inside loop.  */
 189   if (!flow_bb_inside_loop_p (loop, bb->succ->dest)
 190       || !flow_bb_inside_loop_p (loop, bb->succ->succ_next->dest))
 191     return NULL_RTX;
 192
 193   /* It must be executed just once each iteration (because otherwise we
 194      are unable to update dominator/irreducible loop information correctly).  */
 195   if (!just_once_each_iteration_p (loop, bb))
 196     return NULL_RTX;
 197
 198   /* Condition must be invariant.  */
 199   test = get_condition (BB_END (bb), &at, true);
 200   if (!test)
 201     return NULL_RTX;
 202
 203   for (i = 0; i < 2; i++)
 204     {
 205       op[i] = XEXP (test, i);
 206
 207       if (CONSTANT_P (op[i]))
 208         continue;
 209
 210       insn = iv_get_reaching_def (at, op[i]);
 211       if (!iv_analyze (insn, op[i], &iv))
 212         return NULL_RTX;
 213       if (iv.step != const0_rtx
 214           || iv.first_special)
 215         return NULL_RTX;
 216
 217       op[i] = get_iv_value (&iv, const0_rtx);
 218     }
 219
 220   mode = GET_MODE (op[0]);
 221   if (mode == VOIDmode)
 222     mode = GET_MODE (op[1]);
 223   if (GET_MODE_CLASS (mode) == MODE_CC)
 224     {
 225       if (at != BB_END (bb))
 226         return NULL_RTX;
 227
 228       *cinsn = BB_END (bb);
 229       if (!rtx_equal_p (op[0], XEXP (test, 0))
 230           || !rtx_equal_p (op[1], XEXP (test, 1)))
 231         return NULL_RTX;
 232
 233       return test;
 234     }
 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 static void
 259 unswitch_single_loop (struct loops *loops, struct loop *loop,
 260                       rtx cond_checked, int num)
 261 {
 262   basic_block *bbs;
 263   struct loop *nloop;
 264   unsigned i;
 265   rtx cond, rcond, conds, rconds, acond, cinsn = NULL_RTX;
 266   int repeat;
 267   edge e;
 268
 269   /* Do not unswitch too much.  */
 270   if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
 271     {
 272       if (dump_file)
 273         fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
 274       return;
 275     }
 276
 277   /* Only unswitch innermost loops.  */
 278   if (loop->inner)
 279     {
 280       if (dump_file)
 281         fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
 282       return;
 283     }
 284
 285   /* We must be able to duplicate loop body.  */
 286   if (!can_duplicate_loop_p (loop))
 287     {
 288       if (dump_file)
 289         fprintf (dump_file, ";; Not unswitching, can't duplicate loop\n");
 290       return;
 291     }
 292
 293   /* The loop should not be too large, to limit code growth.  */
 294   if (num_loop_insns (loop) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
 295     {
 296       if (dump_file)
 297         fprintf (dump_file, ";; Not unswitching, loop too big\n");
 298       return;
 299     }
 300
 301   /* Do not unswitch in cold areas.  */
 302   if (!maybe_hot_bb_p (loop->header))
 303     {
 304       if (dump_file)
 305         fprintf (dump_file, ";; Not unswitching, not hot area\n");
 306       return;
 307     }
 308
 309   /* Nor if the loop usually does not roll.  */
 310   if (expected_loop_iterations (loop) < 1)
 311     {
 312       if (dump_file)
 313         fprintf (dump_file, ";; Not unswitching, loop iterations < 1\n");
 314       return;
 315     }
 316
 317   do
 318     {
 319       repeat = 0;
 320
 321       /* Find a bb to unswitch on.  */
 322       bbs = get_loop_body (loop);
 323       iv_analysis_loop_init (loop);
 324       for (i = 0; i < loop->num_nodes; i++)
 325         if ((cond = may_unswitch_on (bbs[i], loop, &cinsn)))
 326           break;
 327
 328       if (i == loop->num_nodes)
 329         {
 330           free (bbs);
 331           return;
 332         }
 333
 334       rcond = reversed_condition (cond);
 335       if (rcond)
 336         rcond = canon_condition (rcond);
 337
 338       /* Check whether the result can be predicted.  */
 339       for (acond = cond_checked; acond; acond = XEXP (acond, 1))
 340         simplify_using_condition (XEXP (acond, 0), &cond, NULL);
 341
 342       if (cond == const_true_rtx)
 343         {
 344           /* Remove false path.  */
 345           e = FALLTHRU_EDGE (bbs[i]);
 346           remove_path (loops, e);
 347           free (bbs);
 348           repeat = 1;
 349         }
 350       else if (cond == const0_rtx)
 351         {
 352           /* Remove true path.  */
 353           e = BRANCH_EDGE (bbs[i]);
 354           remove_path (loops, e);
 355           free (bbs);
 356           repeat = 1;
 357         }
 358     } while (repeat);
 359
 360   /* We found the condition we can unswitch on.  */
 361   conds = alloc_EXPR_LIST (0, cond, cond_checked);
 362   if (rcond)
 363     rconds = alloc_EXPR_LIST (0, rcond, cond_checked);
 364   else
 365     rconds = cond_checked;
 366
 367   if (dump_file)
 368     fprintf (dump_file, ";; Unswitching loop\n");
 369
 370   /* Unswitch the loop on this condition.  */
 371   nloop = unswitch_loop (loops, loop, bbs[i], cond, cinsn);
 372   if (!nloop)
 373   abort ();
 374
 375   /* Invoke itself on modified loops.  */
 376   unswitch_single_loop (loops, nloop, rconds, num + 1);
 377   unswitch_single_loop (loops, loop, conds, num + 1);
 378
 379   free_EXPR_LIST_node (conds);
 380   if (rcond)
 381     free_EXPR_LIST_node (rconds);
 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 loops *loops, struct loop *loop, basic_block unswitch_on,
 393                rtx cond, rtx cinsn)
 394 {
 395   edge entry, latch_edge, true_edge, false_edge, e;
 396   basic_block switch_bb, unswitch_on_alt, src;
 397   struct loop *nloop;
 398   sbitmap zero_bitmap;
 399   int irred_flag, prob;
 400   rtx seq;
 401
 402   /* Some sanity checking.  */
 403   if (!flow_bb_inside_loop_p (loop, unswitch_on))
 404     abort ();
 405   if (!unswitch_on->succ || !unswitch_on->succ->succ_next ||
 406       unswitch_on->succ->succ_next->succ_next)
 407     abort ();
 408   if (!just_once_each_iteration_p (loop, unswitch_on))
 409     abort ();
 410   if (loop->inner)
 411     abort ();
 412   if (!flow_bb_inside_loop_p (loop, unswitch_on->succ->dest))
 413     abort ();
 414   if (!flow_bb_inside_loop_p (loop, unswitch_on->succ->succ_next->dest))
 415     abort ();
 416
 417   entry = loop_preheader_edge (loop);
 418
 419   /* Make a copy.  */
 420   src = entry->src;
 421   irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
 422   entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 423   zero_bitmap = sbitmap_alloc (2);
 424   sbitmap_zero (zero_bitmap);
 425   if (!duplicate_loop_to_header_edge (loop, entry, loops, 1,
 426         zero_bitmap, NULL, NULL, NULL, 0))
 427     return NULL;
 428   free (zero_bitmap);
 429   entry->flags |= irred_flag;
 430
 431   /* Record the block with condition we unswitch on.  */
 432   unswitch_on_alt = unswitch_on->rbi->copy;
 433   true_edge = BRANCH_EDGE (unswitch_on_alt);
 434   false_edge = FALLTHRU_EDGE (unswitch_on);
 435   latch_edge = loop->latch->rbi->copy->succ;
 436
 437   /* Create a block with the condition.  */
 438   prob = true_edge->probability;
 439   switch_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
 440   seq = compare_and_jump_seq (XEXP (cond, 0), XEXP (cond, 1), GET_CODE (cond),
 441                               block_label (true_edge->dest),
 442                               prob, cinsn);
 443   emit_insn_after (seq, BB_END (switch_bb));
 444   e = make_edge (switch_bb, true_edge->dest, 0);
 445   e->probability = prob;
 446   e->count = latch_edge->count * prob / REG_BR_PROB_BASE;
 447   e = make_edge (switch_bb, FALLTHRU_EDGE (unswitch_on)->dest, EDGE_FALLTHRU);
 448   e->probability = false_edge->probability;
 449   e->count = latch_edge->count * (false_edge->probability) / REG_BR_PROB_BASE;
 450
 451   if (irred_flag)
 452     {
 453       switch_bb->flags |= BB_IRREDUCIBLE_LOOP;
 454       switch_bb->succ->flags |= EDGE_IRREDUCIBLE_LOOP;
 455       switch_bb->succ->succ_next->flags |= EDGE_IRREDUCIBLE_LOOP;
 456     }
 457   else
 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
 464   /* Loopify from the copy of LOOP body, constructing the new loop.  */
 465   nloop = loopify (loops, latch_edge,
 466                    loop->header->rbi->copy->pred, switch_bb);
 467
 468   /* Remove branches that are now unreachable in new loops.  */
 469   remove_path (loops, true_edge);
 470   remove_path (loops, false_edge);
 471
 472   /* One of created loops do not have to be subloop of the outer loop now,
 473      so fix its placement in loop data structure.  */
 474   fix_loop_placement (loop);
 475   fix_loop_placement (nloop);
 476
 477   /* Preserve the simple loop preheaders.  */
 478   loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
 479   loop_split_edge_with (loop_preheader_edge (nloop), NULL_RTX);
 480
 481   return nloop;
 482 }