gcc/loop-doloop.c

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