gcc/loop-doloop.c

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