Mercurial > hg > CbC > CbC_gcc
annotate gcc/loop-unswitch.c @ 86:12b3180c7d07
modify calls.c.
| author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Thu, 15 Dec 2011 02:37:13 +0900 |
| parents | f6334be47118 |
| children |
| rev | line source |
|---|---|
| 0 | 1 /* Loop unswitching for GNU compiler. |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2 Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010 |
| 0 | 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 (); | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
113 gcc_assert (JUMP_P (jump)); |
| 0 | 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, | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
125 mode, NULL_RTX, NULL_RTX, label, -1); |
| 0 | 126 jump = get_last_insn (); |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
127 gcc_assert (JUMP_P (jump)); |
| 0 | 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], 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 } |