1 /* Loop unswitching for GNU compiler. 2 Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010, 2012 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], copy_rtx_if_shared (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 } 467