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