1/* Loop unswitching for GNU compiler. 2 Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 2, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING. If not, write to the Free 18Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 1902110-1301, 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 "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 82static struct loop *unswitch_loop (struct loops *, struct loop *, 83 basic_block, rtx, rtx); 84static void unswitch_single_loop (struct loops *, struct loop *, rtx, int); 85static rtx may_unswitch_on (basic_block, struct loop *, rtx *); 86 87/* Prepare a sequence comparing OP0 with OP1 using COMP and jumping to LABEL if 88 true, with probability PROB. If CINSN is not NULL, it is the insn to copy 89 in order to create a jump. */ 90 91rtx 92compare_and_jump_seq (rtx op0, rtx op1, enum rtx_code comp, rtx label, int prob, 93 rtx cinsn) 94{ 95 rtx seq, jump, cond; 96 enum machine_mode mode; 97 98 mode = GET_MODE (op0); 99 if (mode == VOIDmode) 100 mode = GET_MODE (op1); 101 102 start_sequence (); 103 if (GET_MODE_CLASS (mode) == MODE_CC) 104 { 105 /* A hack -- there seems to be no easy generic way how to make a 106 conditional jump from a ccmode comparison. */ 107 gcc_assert (cinsn); 108 cond = XEXP (SET_SRC (pc_set (cinsn)), 0); 109 gcc_assert (GET_CODE (cond) == comp); 110 gcc_assert (rtx_equal_p (op0, XEXP (cond, 0))); 111 gcc_assert (rtx_equal_p (op1, XEXP (cond, 1))); 112 emit_jump_insn (copy_insn (PATTERN (cinsn))); 113 jump = get_last_insn (); 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); 126 jump = get_last_insn (); 127 JUMP_LABEL (jump) = label; 128 LABEL_NUSES (label)++; 129 } 130 REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob), 131 REG_NOTES (jump)); 132 seq = get_insns (); 133 end_sequence (); 134 135 return seq; 136} 137 138/* Main entry point. Perform loop unswitching on all suitable LOOPS. */ 139void 140unswitch_loops (struct loops *loops) 141{ 142 int i, num; 143 struct loop *loop; 144 145 /* Go through inner loops (only original ones). */ 146 num = loops->num; 147 148 for (i = 1; i < num; i++) 149 { 150 /* Removed loop? */ 151 loop = loops->parray[i]; 152 if (!loop) 153 continue; 154 155 if (loop->inner) 156 continue; 157 158 unswitch_single_loop (loops, loop, NULL_RTX, 0); 159#ifdef ENABLE_CHECKING 160 verify_dominators (CDI_DOMINATORS); 161 verify_loop_structure (loops); 162#endif 163 } 164 165 iv_analysis_done (); 166} 167 168/* Checks whether we can unswitch LOOP on condition at end of BB -- one of its 169 basic blocks (for what it means see comments below). In case condition 170 compares loop invariant cc mode register, return the jump in CINSN. */ 171 172static rtx 173may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn) 174{ 175 rtx test, at, op[2], stest; 176 struct rtx_iv iv; 177 unsigned i; 178 enum machine_mode mode; 179 180 /* BB must end in a simple conditional jump. */ 181 if (EDGE_COUNT (bb->succs) != 2) 182 return NULL_RTX; 183 if (!any_condjump_p (BB_END (bb))) 184 return NULL_RTX; 185 186 /* With branches inside loop. */ 187 if (!flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 0)->dest) 188 || !flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 1)->dest)) 189 return NULL_RTX; 190 191 /* It must be executed just once each iteration (because otherwise we 192 are unable to update dominator/irreducible loop information correctly). */ 193 if (!just_once_each_iteration_p (loop, bb)) 194 return NULL_RTX; 195 196 /* Condition must be invariant. */ 197 test = get_condition (BB_END (bb), &at, true, false); 198 if (!test) 199 return NULL_RTX; 200 201 for (i = 0; i < 2; i++) 202 { 203 op[i] = XEXP (test, i); 204 205 if (CONSTANT_P (op[i])) 206 continue; 207 208 if (!iv_analyze (at, 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 if (!rtx_equal_p (op[0], XEXP (test, 0)) 226 || !rtx_equal_p (op[1], XEXP (test, 1))) 227 return NULL_RTX; 228 229 *cinsn = BB_END (bb); 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. */ 244rtx 245reversed_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. */ 261static void 262unswitch_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; 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 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; 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 (loops, 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 (loops, 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 (loops, loop, bbs[i], cond, cinsn); 380 gcc_assert (nloop); 381 382 /* Invoke itself on modified loops. */ 383 unswitch_single_loop (loops, nloop, rconds, num + 1); 384 unswitch_single_loop (loops, 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 393/* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support 394 unswitching of innermost loops. UNSWITCH_ON must be executed in every 395 iteration, i.e. it must dominate LOOP latch. COND is the condition 396 determining which loop is entered. Returns NULL if impossible, new loop 397 otherwise. The new loop is entered if COND is true. If CINSN is not 398 NULL, it is the insn in that COND is compared. */ 399 400static struct loop * 401unswitch_loop (struct loops *loops, struct loop *loop, basic_block unswitch_on, 402 rtx cond, rtx cinsn) 403{ 404 edge entry, latch_edge, true_edge, false_edge, e; 405 basic_block switch_bb, unswitch_on_alt; 406 struct loop *nloop; 407 sbitmap zero_bitmap; 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 zero_bitmap = sbitmap_alloc (2); 425 sbitmap_zero (zero_bitmap); 426 if (!duplicate_loop_to_header_edge (loop, entry, loops, 1, 427 zero_bitmap, NULL, NULL, NULL, 0)) 428 { 429 sbitmap_free (zero_bitmap); 430 return NULL; 431 } 432 sbitmap_free (zero_bitmap); 433 entry->flags |= irred_flag; 434 435 /* Record the block with condition we unswitch on. */ 436 unswitch_on_alt = get_bb_copy (unswitch_on); 437 true_edge = BRANCH_EDGE (unswitch_on_alt); 438 false_edge = FALLTHRU_EDGE (unswitch_on); 439 latch_edge = single_succ_edge (get_bb_copy (loop->latch)); 440 441 /* Create a block with the condition. */ 442 prob = true_edge->probability; 443 switch_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb); 444 seq = compare_and_jump_seq (XEXP (cond, 0), XEXP (cond, 1), GET_CODE (cond), 445 block_label (true_edge->dest), 446 prob, cinsn); 447 emit_insn_after (seq, BB_END (switch_bb)); 448 e = make_edge (switch_bb, true_edge->dest, 0); 449 e->probability = prob; 450 e->count = latch_edge->count * prob / REG_BR_PROB_BASE; 451 e = make_edge (switch_bb, FALLTHRU_EDGE (unswitch_on)->dest, EDGE_FALLTHRU); 452 e->probability = false_edge->probability; 453 e->count = latch_edge->count * (false_edge->probability) / REG_BR_PROB_BASE; 454 455 if (irred_flag) 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 else 462 { 463 switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP; 464 EDGE_SUCC (switch_bb, 0)->flags &= ~EDGE_IRREDUCIBLE_LOOP; 465 EDGE_SUCC (switch_bb, 1)->flags &= ~EDGE_IRREDUCIBLE_LOOP; 466 } 467 468 /* Loopify from the copy of LOOP body, constructing the new loop. */ 469 nloop = loopify (loops, latch_edge, 470 single_pred_edge (get_bb_copy (loop->header)), switch_bb, 471 BRANCH_EDGE (switch_bb), FALLTHRU_EDGE (switch_bb), true); 472 473 /* Remove branches that are now unreachable in new loops. */ 474 remove_path (loops, true_edge); 475 remove_path (loops, false_edge); 476 477 /* One of created loops do not have to be subloop of the outer loop now, 478 so fix its placement in loop data structure. */ 479 fix_loop_placement (loop); 480 fix_loop_placement (nloop); 481 482 /* Preserve the simple loop preheaders. */ 483 loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX); 484 loop_split_edge_with (loop_preheader_edge (nloop), NULL_RTX); 485 486 return nloop; 487} 488