1 /* Perform doloop optimizations 2 Copyright (C) 2004-2016 Free Software Foundation, Inc. 3 Based on code by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz) 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 "backend.h" 25 #include "target.h" 26 #include "rtl.h" 27 #include "tree.h" 28 #include "cfghooks.h" 29 #include "emit-rtl.h" 30 #include "dojump.h" 31 #include "expr.h" 32 #include "cfgloop.h" 33 #include "cfgrtl.h" 34 #include "params.h" 35 #include "dumpfile.h" 36 #include "loop-unroll.h" 37 #include "regs.h" 38 #include "df.h" 39 40 /* This module is used to modify loops with a determinable number of 41 iterations to use special low-overhead looping instructions. 42 43 It first validates whether the loop is well behaved and has a 44 determinable number of iterations (either at compile or run-time). 45 It then modifies the loop to use a low-overhead looping pattern as 46 follows: 47 48 1. A pseudo register is allocated as the loop iteration counter. 49 50 2. The number of loop iterations is calculated and is stored 51 in the loop counter. 52 53 3. At the end of the loop, the jump insn is replaced by the 54 doloop_end pattern. The compare must remain because it might be 55 used elsewhere. If the loop-variable or condition register are 56 used elsewhere, they will be eliminated by flow. 57 58 4. An optional doloop_begin pattern is inserted at the top of the 59 loop. 60 61 TODO The optimization should only performed when either the biv used for exit 62 condition is unused at all except for the exit test, or if we do not have to 63 change its value, since otherwise we have to add a new induction variable, 64 which usually will not pay up (unless the cost of the doloop pattern is 65 somehow extremely lower than the cost of compare & jump, or unless the bct 66 register cannot be used for anything else but doloop -- ??? detect these 67 cases). */ 68 69 /* Return the loop termination condition for PATTERN or zero 70 if it is not a decrement and branch jump insn. */ 71 72 rtx 73 doloop_condition_get (rtx doloop_pat) 74 { 75 rtx cmp; 76 rtx inc; 77 rtx reg; 78 rtx inc_src; 79 rtx condition; 80 rtx pattern; 81 rtx cc_reg = NULL_RTX; 82 rtx reg_orig = NULL_RTX; 83 84 /* The canonical doloop pattern we expect has one of the following 85 forms: 86 87 1) (parallel [(set (pc) (if_then_else (condition) 88 (label_ref (label)) 89 (pc))) 90 (set (reg) (plus (reg) (const_int -1))) 91 (additional clobbers and uses)]) 92 93 The branch must be the first entry of the parallel (also required 94 by jump.c), and the second entry of the parallel must be a set of 95 the loop counter register. Some targets (IA-64) wrap the set of 96 the loop counter in an if_then_else too. 97 98 2) (set (reg) (plus (reg) (const_int -1)) 99 (set (pc) (if_then_else (reg != 0) 100 (label_ref (label)) 101 (pc))). 102 103 Some targets (ARM) do the comparison before the branch, as in the 104 following form: 105 106 3) (parallel [(set (cc) (compare ((plus (reg) (const_int -1), 0))) 107 (set (reg) (plus (reg) (const_int -1)))]) 108 (set (pc) (if_then_else (cc == NE) 109 (label_ref (label)) 110 (pc))) */ 111 112 pattern = PATTERN (doloop_pat); 113 114 if (GET_CODE (pattern) != PARALLEL) 115 { 116 rtx cond; 117 rtx_insn *prev_insn = prev_nondebug_insn (doloop_pat); 118 rtx cmp_arg1, cmp_arg2; 119 rtx cmp_orig; 120 121 /* In case the pattern is not PARALLEL we expect two forms 122 of doloop which are cases 2) and 3) above: in case 2) the 123 decrement immediately precedes the branch, while in case 3) 124 the compare and decrement instructions immediately precede 125 the branch. */ 126 127 if (prev_insn == NULL_RTX || !INSN_P (prev_insn)) 128 return 0; 129 130 cmp = pattern; 131 if (GET_CODE (PATTERN (prev_insn)) == PARALLEL) 132 { 133 /* The third case: the compare and decrement instructions 134 immediately precede the branch. */ 135 cmp_orig = XVECEXP (PATTERN (prev_insn), 0, 0); 136 if (GET_CODE (cmp_orig) != SET) 137 return 0; 138 if (GET_CODE (SET_SRC (cmp_orig)) != COMPARE) 139 return 0; 140 cmp_arg1 = XEXP (SET_SRC (cmp_orig), 0); 141 cmp_arg2 = XEXP (SET_SRC (cmp_orig), 1); 142 if (cmp_arg2 != const0_rtx 143 || GET_CODE (cmp_arg1) != PLUS) 144 return 0; 145 reg_orig = XEXP (cmp_arg1, 0); 146 if (XEXP (cmp_arg1, 1) != GEN_INT (-1) 147 || !REG_P (reg_orig)) 148 return 0; 149 cc_reg = SET_DEST (cmp_orig); 150 151 inc = XVECEXP (PATTERN (prev_insn), 0, 1); 152 } 153 else 154 inc = PATTERN (prev_insn); 155 if (GET_CODE (cmp) == SET && GET_CODE (SET_SRC (cmp)) == IF_THEN_ELSE) 156 { 157 /* We expect the condition to be of the form (reg != 0) */ 158 cond = XEXP (SET_SRC (cmp), 0); 159 if (GET_CODE (cond) != NE || XEXP (cond, 1) != const0_rtx) 160 return 0; 161 } 162 } 163 else 164 { 165 cmp = XVECEXP (pattern, 0, 0); 166 inc = XVECEXP (pattern, 0, 1); 167 } 168 169 /* Check for (set (reg) (something)). */ 170 if (GET_CODE (inc) != SET) 171 return 0; 172 reg = SET_DEST (inc); 173 if (! REG_P (reg)) 174 return 0; 175 176 /* Check if something = (plus (reg) (const_int -1)). 177 On IA-64, this decrement is wrapped in an if_then_else. */ 178 inc_src = SET_SRC (inc); 179 if (GET_CODE (inc_src) == IF_THEN_ELSE) 180 inc_src = XEXP (inc_src, 1); 181 if (GET_CODE (inc_src) != PLUS 182 || XEXP (inc_src, 0) != reg 183 || XEXP (inc_src, 1) != constm1_rtx) 184 return 0; 185 186 /* Check for (set (pc) (if_then_else (condition) 187 (label_ref (label)) 188 (pc))). */ 189 if (GET_CODE (cmp) != SET 190 || SET_DEST (cmp) != pc_rtx 191 || GET_CODE (SET_SRC (cmp)) != IF_THEN_ELSE 192 || GET_CODE (XEXP (SET_SRC (cmp), 1)) != LABEL_REF 193 || XEXP (SET_SRC (cmp), 2) != pc_rtx) 194 return 0; 195 196 /* Extract loop termination condition. */ 197 condition = XEXP (SET_SRC (cmp), 0); 198 199 /* We expect a GE or NE comparison with 0 or 1. */ 200 if ((GET_CODE (condition) != GE 201 && GET_CODE (condition) != NE) 202 || (XEXP (condition, 1) != const0_rtx 203 && XEXP (condition, 1) != const1_rtx)) 204 return 0; 205 206 if ((XEXP (condition, 0) == reg) 207 /* For the third case: */ 208 || ((cc_reg != NULL_RTX) 209 && (XEXP (condition, 0) == cc_reg) 210 && (reg_orig == reg)) 211 || (GET_CODE (XEXP (condition, 0)) == PLUS 212 && XEXP (XEXP (condition, 0), 0) == reg)) 213 { 214 if (GET_CODE (pattern) != PARALLEL) 215 /* For the second form we expect: 216 217 (set (reg) (plus (reg) (const_int -1)) 218 (set (pc) (if_then_else (reg != 0) 219 (label_ref (label)) 220 (pc))). 221 222 is equivalent to the following: 223 224 (parallel [(set (pc) (if_then_else (reg != 1) 225 (label_ref (label)) 226 (pc))) 227 (set (reg) (plus (reg) (const_int -1))) 228 (additional clobbers and uses)]) 229 230 For the third form we expect: 231 232 (parallel [(set (cc) (compare ((plus (reg) (const_int -1)), 0)) 233 (set (reg) (plus (reg) (const_int -1)))]) 234 (set (pc) (if_then_else (cc == NE) 235 (label_ref (label)) 236 (pc))) 237 238 which is equivalent to the following: 239 240 (parallel [(set (cc) (compare (reg, 1)) 241 (set (reg) (plus (reg) (const_int -1))) 242 (set (pc) (if_then_else (NE == cc) 243 (label_ref (label)) 244 (pc))))]) 245 246 So we return the second form instead for the two cases. 247 248 */ 249 condition = gen_rtx_fmt_ee (NE, VOIDmode, inc_src, const1_rtx); 250 251 return condition; 252 } 253 254 /* ??? If a machine uses a funny comparison, we could return a 255 canonicalized form here. */ 256 257 return 0; 258 } 259 260 /* Return nonzero if the loop specified by LOOP is suitable for 261 the use of special low-overhead looping instructions. DESC 262 describes the number of iterations of the loop. */ 263 264 static bool 265 doloop_valid_p (struct loop *loop, struct niter_desc *desc) 266 { 267 basic_block *body = get_loop_body (loop), bb; 268 rtx_insn *insn; 269 unsigned i; 270 bool result = true; 271 272 /* Check for loops that may not terminate under special conditions. */ 273 if (!desc->simple_p 274 || desc->assumptions 275 || desc->infinite) 276 { 277 /* There are some cases that would require a special attention. 278 For example if the comparison is LEU and the comparison value 279 is UINT_MAX then the loop will not terminate. Similarly, if the 280 comparison code is GEU and the comparison value is 0, the 281 loop will not terminate. 282 283 If the absolute increment is not 1, the loop can be infinite 284 even with LTU/GTU, e.g. for (i = 3; i > 0; i -= 2) 285 286 ??? We could compute these conditions at run-time and have a 287 additional jump around the loop to ensure an infinite loop. 288 However, it is very unlikely that this is the intended 289 behavior of the loop and checking for these rare boundary 290 conditions would pessimize all other code. 291 292 If the loop is executed only a few times an extra check to 293 restart the loop could use up most of the benefits of using a 294 count register loop. Note however, that normally, this 295 restart branch would never execute, so it could be predicted 296 well by the CPU. We should generate the pessimistic code by 297 default, and have an option, e.g. -funsafe-loops that would 298 enable count-register loops in this case. */ 299 if (dump_file) 300 fprintf (dump_file, "Doloop: Possible infinite iteration case.\n"); 301 result = false; 302 goto cleanup; 303 } 304 305 for (i = 0; i < loop->num_nodes; i++) 306 { 307 bb = body[i]; 308 309 for (insn = BB_HEAD (bb); 310 insn != NEXT_INSN (BB_END (bb)); 311 insn = NEXT_INSN (insn)) 312 { 313 /* Different targets have different necessities for low-overhead 314 looping. Call the back end for each instruction within the loop 315 to let it decide whether the insn prohibits a low-overhead loop. 316 It will then return the cause for it to emit to the dump file. */ 317 const char * invalid = targetm.invalid_within_doloop (insn); 318 if (invalid) 319 { 320 if (dump_file) 321 fprintf (dump_file, "Doloop: %s\n", invalid); 322 result = false; 323 goto cleanup; 324 } 325 } 326 } 327 result = true; 328 329 cleanup: 330 free (body); 331 332 return result; 333 } 334 335 /* Adds test of COND jumping to DEST on edge *E and set *E to the new fallthru 336 edge. If the condition is always false, do not do anything. If it is always 337 true, redirect E to DEST and return false. In all other cases, true is 338 returned. */ 339 340 static bool 341 add_test (rtx cond, edge *e, basic_block dest) 342 { 343 rtx_insn *seq, *jump; 344 rtx_code_label *label; 345 machine_mode mode; 346 rtx op0 = XEXP (cond, 0), op1 = XEXP (cond, 1); 347 enum rtx_code code = GET_CODE (cond); 348 basic_block bb; 349 350 mode = GET_MODE (XEXP (cond, 0)); 351 if (mode == VOIDmode) 352 mode = GET_MODE (XEXP (cond, 1)); 353 354 start_sequence (); 355 op0 = force_operand (op0, NULL_RTX); 356 op1 = force_operand (op1, NULL_RTX); 357 label = block_label (dest); 358 do_compare_rtx_and_jump (op0, op1, code, 0, mode, NULL_RTX, NULL, label, -1); 359 360 jump = get_last_insn (); 361 if (!jump || !JUMP_P (jump)) 362 { 363 /* The condition is always false and the jump was optimized out. */ 364 end_sequence (); 365 return true; 366 } 367 368 seq = get_insns (); 369 end_sequence (); 370 371 /* There always is at least the jump insn in the sequence. */ 372 gcc_assert (seq != NULL_RTX); 373 374 bb = split_edge_and_insert (*e, seq); 375 *e = single_succ_edge (bb); 376 377 if (any_uncondjump_p (jump)) 378 { 379 /* The condition is always true. */ 380 delete_insn (jump); 381 redirect_edge_and_branch_force (*e, dest); 382 return false; 383 } 384 385 JUMP_LABEL (jump) = label; 386 387 /* The jump is supposed to handle an unlikely special case. */ 388 add_int_reg_note (jump, REG_BR_PROB, 0); 389 390 LABEL_NUSES (label)++; 391 392 make_edge (bb, dest, (*e)->flags & ~EDGE_FALLTHRU); 393 return true; 394 } 395 396 /* Modify the loop to use the low-overhead looping insn where LOOP 397 describes the loop, DESC describes the number of iterations of the 398 loop, and DOLOOP_INSN is the low-overhead looping insn to emit at the 399 end of the loop. CONDITION is the condition separated from the 400 DOLOOP_SEQ. COUNT is the number of iterations of the LOOP. */ 401 402 static void 403 doloop_modify (struct loop *loop, struct niter_desc *desc, 404 rtx_insn *doloop_seq, rtx condition, rtx count) 405 { 406 rtx counter_reg; 407 rtx tmp, noloop = NULL_RTX; 408 rtx_insn *sequence; 409 rtx_insn *jump_insn; 410 rtx_code_label *jump_label; 411 int nonneg = 0; 412 bool increment_count; 413 basic_block loop_end = desc->out_edge->src; 414 machine_mode mode; 415 rtx true_prob_val; 416 widest_int iterations; 417 418 jump_insn = BB_END (loop_end); 419 420 if (dump_file) 421 { 422 fprintf (dump_file, "Doloop: Inserting doloop pattern ("); 423 if (desc->const_iter) 424 fprintf (dump_file, "%" PRId64, desc->niter); 425 else 426 fputs ("runtime", dump_file); 427 fputs (" iterations).\n", dump_file); 428 } 429 430 /* Get the probability of the original branch. If it exists we would 431 need to update REG_BR_PROB of the new jump_insn. */ 432 true_prob_val = find_reg_note (jump_insn, REG_BR_PROB, NULL_RTX); 433 434 /* Discard original jump to continue loop. The original compare 435 result may still be live, so it cannot be discarded explicitly. */ 436 delete_insn (jump_insn); 437 438 counter_reg = XEXP (condition, 0); 439 if (GET_CODE (counter_reg) == PLUS) 440 counter_reg = XEXP (counter_reg, 0); 441 mode = GET_MODE (counter_reg); 442 443 increment_count = false; 444 switch (GET_CODE (condition)) 445 { 446 case NE: 447 /* Currently only NE tests against zero and one are supported. */ 448 noloop = XEXP (condition, 1); 449 if (noloop != const0_rtx) 450 { 451 gcc_assert (noloop == const1_rtx); 452 increment_count = true; 453 } 454 break; 455 456 case GE: 457 /* Currently only GE tests against zero are supported. */ 458 gcc_assert (XEXP (condition, 1) == const0_rtx); 459 460 noloop = constm1_rtx; 461 462 /* The iteration count does not need incrementing for a GE test. */ 463 increment_count = false; 464 465 /* Determine if the iteration counter will be non-negative. 466 Note that the maximum value loaded is iterations_max - 1. */ 467 if (get_max_loop_iterations (loop, &iterations) 468 && wi::leu_p (iterations, 469 wi::set_bit_in_zero <widest_int> 470 (GET_MODE_PRECISION (mode) - 1))) 471 nonneg = 1; 472 break; 473 474 /* Abort if an invalid doloop pattern has been generated. */ 475 default: 476 gcc_unreachable (); 477 } 478 479 if (increment_count) 480 count = simplify_gen_binary (PLUS, mode, count, const1_rtx); 481 482 /* Insert initialization of the count register into the loop header. */ 483 start_sequence (); 484 tmp = force_operand (count, counter_reg); 485 convert_move (counter_reg, tmp, 1); 486 sequence = get_insns (); 487 end_sequence (); 488 emit_insn_after (sequence, BB_END (loop_preheader_edge (loop)->src)); 489 490 if (desc->noloop_assumptions) 491 { 492 rtx ass = copy_rtx (desc->noloop_assumptions); 493 basic_block preheader = loop_preheader_edge (loop)->src; 494 basic_block set_zero 495 = split_edge (loop_preheader_edge (loop)); 496 basic_block new_preheader 497 = split_edge (loop_preheader_edge (loop)); 498 edge te; 499 500 /* Expand the condition testing the assumptions and if it does not pass, 501 reset the count register to 0. */ 502 redirect_edge_and_branch_force (single_succ_edge (preheader), new_preheader); 503 set_immediate_dominator (CDI_DOMINATORS, new_preheader, preheader); 504 505 set_zero->count = 0; 506 set_zero->frequency = 0; 507 508 te = single_succ_edge (preheader); 509 for (; ass; ass = XEXP (ass, 1)) 510 if (!add_test (XEXP (ass, 0), &te, set_zero)) 511 break; 512 513 if (ass) 514 { 515 /* We reached a condition that is always true. This is very hard to 516 reproduce (such a loop does not roll, and thus it would most 517 likely get optimized out by some of the preceding optimizations). 518 In fact, I do not have any testcase for it. However, it would 519 also be very hard to show that it is impossible, so we must 520 handle this case. */ 521 set_zero->count = preheader->count; 522 set_zero->frequency = preheader->frequency; 523 } 524 525 if (EDGE_COUNT (set_zero->preds) == 0) 526 { 527 /* All the conditions were simplified to false, remove the 528 unreachable set_zero block. */ 529 delete_basic_block (set_zero); 530 } 531 else 532 { 533 /* Reset the counter to zero in the set_zero block. */ 534 start_sequence (); 535 convert_move (counter_reg, noloop, 0); 536 sequence = get_insns (); 537 end_sequence (); 538 emit_insn_after (sequence, BB_END (set_zero)); 539 540 set_immediate_dominator (CDI_DOMINATORS, set_zero, 541 recompute_dominator (CDI_DOMINATORS, 542 set_zero)); 543 } 544 545 set_immediate_dominator (CDI_DOMINATORS, new_preheader, 546 recompute_dominator (CDI_DOMINATORS, 547 new_preheader)); 548 } 549 550 /* Some targets (eg, C4x) need to initialize special looping 551 registers. */ 552 if (targetm.have_doloop_begin ()) 553 if (rtx_insn *seq = targetm.gen_doloop_begin (counter_reg, doloop_seq)) 554 emit_insn_after (seq, BB_END (loop_preheader_edge (loop)->src)); 555 556 /* Insert the new low-overhead looping insn. */ 557 emit_jump_insn_after (doloop_seq, BB_END (loop_end)); 558 jump_insn = BB_END (loop_end); 559 jump_label = block_label (desc->in_edge->dest); 560 JUMP_LABEL (jump_insn) = jump_label; 561 LABEL_NUSES (jump_label)++; 562 563 /* Ensure the right fallthru edge is marked, for case we have reversed 564 the condition. */ 565 desc->in_edge->flags &= ~EDGE_FALLTHRU; 566 desc->out_edge->flags |= EDGE_FALLTHRU; 567 568 /* Add a REG_NONNEG note if the actual or estimated maximum number 569 of iterations is non-negative. */ 570 if (nonneg) 571 add_reg_note (jump_insn, REG_NONNEG, NULL_RTX); 572 573 /* Update the REG_BR_PROB note. */ 574 if (true_prob_val) 575 { 576 /* Seems safer to use the branch probability. */ 577 add_int_reg_note (jump_insn, REG_BR_PROB, desc->in_edge->probability); 578 } 579 } 580 581 /* Called through note_stores. */ 582 583 static void 584 record_reg_sets (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data) 585 { 586 bitmap mod = (bitmap)data; 587 if (REG_P (x)) 588 { 589 unsigned int regno = REGNO (x); 590 if (HARD_REGISTER_P (x)) 591 { 592 unsigned int end_regno = end_hard_regno (GET_MODE (x), regno); 593 do 594 bitmap_set_bit (mod, regno); 595 while (++regno < end_regno); 596 } 597 else 598 bitmap_set_bit (mod, regno); 599 } 600 } 601 602 /* Process loop described by LOOP validating that the loop is suitable for 603 conversion to use a low overhead looping instruction, replacing the jump 604 insn where suitable. Returns true if the loop was successfully 605 modified. */ 606 607 static bool 608 doloop_optimize (struct loop *loop) 609 { 610 machine_mode mode; 611 rtx doloop_reg; 612 rtx count; 613 widest_int iterations, iterations_max; 614 rtx_code_label *start_label; 615 rtx condition; 616 unsigned level, est_niter; 617 int max_cost; 618 struct niter_desc *desc; 619 unsigned word_mode_size; 620 unsigned HOST_WIDE_INT word_mode_max; 621 int entered_at_top; 622 623 if (dump_file) 624 fprintf (dump_file, "Doloop: Processing loop %d.\n", loop->num); 625 626 iv_analysis_loop_init (loop); 627 628 /* Find the simple exit of a LOOP. */ 629 desc = get_simple_loop_desc (loop); 630 631 /* Check that loop is a candidate for a low-overhead looping insn. */ 632 if (!doloop_valid_p (loop, desc)) 633 { 634 if (dump_file) 635 fprintf (dump_file, 636 "Doloop: The loop is not suitable.\n"); 637 return false; 638 } 639 mode = desc->mode; 640 641 est_niter = 3; 642 if (desc->const_iter) 643 est_niter = desc->niter; 644 /* If the estimate on number of iterations is reliable (comes from profile 645 feedback), use it. Do not use it normally, since the expected number 646 of iterations of an unrolled loop is 2. */ 647 if (loop->header->count) 648 est_niter = expected_loop_iterations (loop); 649 650 if (est_niter < 3) 651 { 652 if (dump_file) 653 fprintf (dump_file, 654 "Doloop: Too few iterations (%u) to be profitable.\n", 655 est_niter); 656 return false; 657 } 658 659 max_cost 660 = COSTS_N_INSNS (PARAM_VALUE (PARAM_MAX_ITERATIONS_COMPUTATION_COST)); 661 if (set_src_cost (desc->niter_expr, mode, optimize_loop_for_speed_p (loop)) 662 > max_cost) 663 { 664 if (dump_file) 665 fprintf (dump_file, 666 "Doloop: number of iterations too costly to compute.\n"); 667 return false; 668 } 669 670 if (desc->const_iter) 671 iterations = widest_int::from (std::make_pair (desc->niter_expr, mode), 672 UNSIGNED); 673 else 674 iterations = 0; 675 if (!get_max_loop_iterations (loop, &iterations_max)) 676 iterations_max = 0; 677 level = get_loop_level (loop) + 1; 678 entered_at_top = (loop->latch == desc->in_edge->dest 679 && contains_no_active_insn_p (loop->latch)); 680 if (!targetm.can_use_doloop_p (iterations, iterations_max, level, 681 entered_at_top)) 682 { 683 if (dump_file) 684 fprintf (dump_file, "Loop rejected by can_use_doloop_p.\n"); 685 return false; 686 } 687 688 /* Generate looping insn. If the pattern FAILs then give up trying 689 to modify the loop since there is some aspect the back-end does 690 not like. */ 691 count = copy_rtx (desc->niter_expr); 692 start_label = block_label (desc->in_edge->dest); 693 doloop_reg = gen_reg_rtx (mode); 694 rtx_insn *doloop_seq = targetm.gen_doloop_end (doloop_reg, start_label); 695 696 word_mode_size = GET_MODE_PRECISION (word_mode); 697 word_mode_max 698 = ((unsigned HOST_WIDE_INT) 1 << (word_mode_size - 1) << 1) - 1; 699 if (! doloop_seq 700 && mode != word_mode 701 /* Before trying mode different from the one in that # of iterations is 702 computed, we must be sure that the number of iterations fits into 703 the new mode. */ 704 && (word_mode_size >= GET_MODE_PRECISION (mode) 705 || wi::leu_p (iterations_max, word_mode_max))) 706 { 707 if (word_mode_size > GET_MODE_PRECISION (mode)) 708 count = simplify_gen_unary (ZERO_EXTEND, word_mode, count, mode); 709 else 710 count = lowpart_subreg (word_mode, count, mode); 711 PUT_MODE (doloop_reg, word_mode); 712 doloop_seq = targetm.gen_doloop_end (doloop_reg, start_label); 713 } 714 if (! doloop_seq) 715 { 716 if (dump_file) 717 fprintf (dump_file, 718 "Doloop: Target unwilling to use doloop pattern!\n"); 719 return false; 720 } 721 722 /* If multiple instructions were created, the last must be the 723 jump instruction. */ 724 rtx_insn *doloop_insn = doloop_seq; 725 while (NEXT_INSN (doloop_insn) != NULL_RTX) 726 doloop_insn = NEXT_INSN (doloop_insn); 727 if (!JUMP_P (doloop_insn) 728 || !(condition = doloop_condition_get (doloop_insn))) 729 { 730 if (dump_file) 731 fprintf (dump_file, "Doloop: Unrecognizable doloop pattern!\n"); 732 return false; 733 } 734 735 /* Ensure that the new sequence doesn't clobber a register that 736 is live at the end of the block. */ 737 { 738 bitmap modified = BITMAP_ALLOC (NULL); 739 740 for (rtx_insn *i = doloop_seq; i != NULL; i = NEXT_INSN (i)) 741 note_stores (PATTERN (i), record_reg_sets, modified); 742 743 basic_block loop_end = desc->out_edge->src; 744 bool fail = bitmap_intersect_p (df_get_live_out (loop_end), modified); 745 BITMAP_FREE (modified); 746 747 if (fail) 748 { 749 if (dump_file) 750 fprintf (dump_file, "Doloop: doloop pattern clobbers live out\n"); 751 return false; 752 } 753 } 754 755 doloop_modify (loop, desc, doloop_seq, condition, count); 756 return true; 757 } 758 759 /* This is the main entry point. Process all loops using doloop_optimize. */ 760 761 void 762 doloop_optimize_loops (void) 763 { 764 struct loop *loop; 765 766 if (optimize == 1) 767 { 768 df_live_add_problem (); 769 df_live_set_all_dirty (); 770 } 771 772 FOR_EACH_LOOP (loop, 0) 773 { 774 doloop_optimize (loop); 775 } 776 777 if (optimize == 1) 778 df_remove_problem (df_live); 779 780 iv_analysis_done (); 781 782 checking_verify_loop_structure (); 783 } 784