gcc/loop-doloop.c

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