gcc/loop-doloop.c

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