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, 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       noloop = XEXP (condition, 1);
 303       if (noloop != const0_rtx)
 304         {
 305           gcc_assert (noloop == const1_rtx);
 306           increment_count = true;
 307         }
 308       break;
 309
 310     case GE:
 311       /* Currently only GE tests against zero are supported.  */
 312       gcc_assert (XEXP (condition, 1) == const0_rtx);
 313
 314       noloop = constm1_rtx;
 315
 316       /* The iteration count does not need incrementing for a GE test.  */
 317       increment_count = false;
 318
 319       /* Determine if the iteration counter will be non-negative.
 320          Note that the maximum value loaded is iterations_max - 1.  */
 321       if (desc->niter_max
 322           <= ((unsigned HOST_WIDEST_INT) 1
 323               << (GET_MODE_BITSIZE (mode) - 1)))
 324         nonneg = 1;
 325       break;
 326
 327       /* Abort if an invalid doloop pattern has been generated.  */
 328     default:
 329       gcc_unreachable ();
 330     }
 331
 332   if (increment_count)
 333     count = simplify_gen_binary (PLUS, mode, count, const1_rtx);
 334
 335   /* Insert initialization of the count register into the loop header.  */
 336   start_sequence ();
 337   tmp = force_operand (count, counter_reg);
 338   convert_move (counter_reg, tmp, 1);
 339   sequence = get_insns ();
 340   end_sequence ();
 341   emit_insn_after (sequence, BB_END (loop_preheader_edge (loop)->src));
 342
 343   if (desc->noloop_assumptions)
 344     {
 345       rtx ass = copy_rtx (desc->noloop_assumptions);
 346       basic_block preheader = loop_preheader_edge (loop)->src;
 347       basic_block set_zero
 348               = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
 349       basic_block new_preheader
 350               = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
 351       basic_block bb;
 352       edge te;
 353       gcov_type cnt;
 354
 355       /* Expand the condition testing the assumptions and if it does not pass,
 356          reset the count register to 0.  */
 357       add_test (XEXP (ass, 0), preheader, set_zero);
 358       single_succ_edge (preheader)->flags &= ~EDGE_FALLTHRU;
 359       cnt = single_succ_edge (preheader)->count;
 360       single_succ_edge (preheader)->probability = 0;
 361       single_succ_edge (preheader)->count = 0;
 362       irr = single_succ_edge (preheader)->flags & EDGE_IRREDUCIBLE_LOOP;
 363       te = make_edge (preheader, new_preheader, EDGE_FALLTHRU | irr);
 364       te->probability = REG_BR_PROB_BASE;
 365       te->count = cnt;
 366       set_immediate_dominator (CDI_DOMINATORS, new_preheader, preheader);
 367
 368       set_zero->count = 0;
 369       set_zero->frequency = 0;
 370
 371       for (ass = XEXP (ass, 1); ass; ass = XEXP (ass, 1))
 372         {
 373           bb = loop_split_edge_with (te, NULL_RTX);
 374           te = single_succ_edge (bb);
 375           add_test (XEXP (ass, 0), bb, set_zero);
 376           make_edge (bb, set_zero, irr);
 377         }
 378
 379       start_sequence ();
 380       convert_move (counter_reg, noloop, 0);
 381       sequence = get_insns ();
 382       end_sequence ();
 383       emit_insn_after (sequence, BB_END (set_zero));
 384     }
 385
 386   /* Some targets (eg, C4x) need to initialize special looping
 387      registers.  */
 388 #ifdef HAVE_doloop_begin
 389   {
 390     rtx init;
 391     unsigned level = get_loop_level (loop) + 1;
 392     init = gen_doloop_begin (counter_reg,
 393                              desc->const_iter ? desc->niter_expr : const0_rtx,
 394                              desc->niter_max,
 395                              GEN_INT (level));
 396     if (init)
 397       {
 398         start_sequence ();
 399         emit_insn (init);
 400         sequence = get_insns ();
 401         end_sequence ();
 402         emit_insn_after (sequence, BB_END (loop_preheader_edge (loop)->src));
 403       }
 404   }
 405 #endif
 406
 407   /* Insert the new low-overhead looping insn.  */
 408   emit_jump_insn_after (doloop_seq, BB_END (loop_end));
 409   jump_insn = BB_END (loop_end);
 410   jump_label = block_label (desc->in_edge->dest);
 411   JUMP_LABEL (jump_insn) = jump_label;
 412   LABEL_NUSES (jump_label)++;
 413
 414   /* Ensure the right fallthru edge is marked, for case we have reversed
 415      the condition.  */
 416   desc->in_edge->flags &= ~EDGE_FALLTHRU;
 417   desc->out_edge->flags |= EDGE_FALLTHRU;
 418
 419   /* Add a REG_NONNEG note if the actual or estimated maximum number
 420      of iterations is non-negative.  */
 421   if (nonneg)
 422     {
 423       REG_NOTES (jump_insn)
 424         = gen_rtx_EXPR_LIST (REG_NONNEG, NULL_RTX, REG_NOTES (jump_insn));
 425     }
 426 }
 427
 428 /* Process loop described by LOOP validating that the loop is suitable for
 429    conversion to use a low overhead looping instruction, replacing the jump
 430    insn where suitable.  Returns true if the loop was successfully
 431    modified.  */
 432
 433 static bool
 434 doloop_optimize (struct loop *loop)
 435 {
 436   enum machine_mode mode;
 437   rtx doloop_seq, doloop_pat, doloop_reg;
 438   rtx iterations, count;
 439   rtx iterations_max;
 440   rtx start_label;
 441   rtx condition;
 442   unsigned level, est_niter;
 443   struct niter_desc *desc;
 444   unsigned word_mode_size;
 445   unsigned HOST_WIDE_INT word_mode_max;
 446
 447   if (dump_file)
 448     fprintf (dump_file, "Doloop: Processing loop %d.\n", loop->num);
 449
 450   iv_analysis_loop_init (loop);
 451
 452   /* Find the simple exit of a LOOP.  */
 453   desc = get_simple_loop_desc (loop);
 454
 455   /* Check that loop is a candidate for a low-overhead looping insn.  */
 456   if (!doloop_valid_p (loop, desc))
 457     {
 458       if (dump_file)
 459         fprintf (dump_file,
 460                  "Doloop: The loop is not suitable.\n");
 461       return false;
 462     }
 463   mode = desc->mode;
 464
 465   est_niter = 3;
 466   if (desc->const_iter)
 467     est_niter = desc->niter;
 468   /* If the estimate on number of iterations is reliable (comes from profile
 469      feedback), use it.  Do not use it normally, since the expected number
 470      of iterations of an unrolled loop is 2.  */
 471   if (loop->header->count)
 472     est_niter = expected_loop_iterations (loop);
 473
 474   if (est_niter < 3)
 475     {
 476       if (dump_file)
 477         fprintf (dump_file,
 478                  "Doloop: Too few iterations (%u) to be profitable.\n",
 479                  est_niter);
 480       return false;
 481     }
 482
 483   count = copy_rtx (desc->niter_expr);
 484   iterations = desc->const_iter ? desc->niter_expr : const0_rtx;
 485   iterations_max = GEN_INT (desc->niter_max);
 486   level = get_loop_level (loop) + 1;
 487
 488   /* Generate looping insn.  If the pattern FAILs then give up trying
 489      to modify the loop since there is some aspect the back-end does
 490      not like.  */
 491   start_label = block_label (desc->in_edge->dest);
 492   doloop_reg = gen_reg_rtx (mode);
 493   doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
 494                                GEN_INT (level), start_label);
 495
 496   word_mode_size = GET_MODE_BITSIZE (word_mode);
 497   word_mode_max
 498           = ((unsigned HOST_WIDE_INT) 1 << (word_mode_size - 1) << 1) - 1;
 499   if (! doloop_seq
 500       && mode != word_mode
 501       /* Before trying mode different from the one in that # of iterations is
 502          computed, we must be sure that the number of iterations fits into
 503          the new mode.  */
 504       && (word_mode_size >= GET_MODE_BITSIZE (mode)
 505           || desc->niter_max <= word_mode_max))
 506     {
 507       if (word_mode_size > GET_MODE_BITSIZE (mode))
 508         {
 509           count = simplify_gen_unary (ZERO_EXTEND, word_mode,
 510                                       count, mode);
 511           iterations = simplify_gen_unary (ZERO_EXTEND, word_mode,
 512                                            iterations, mode);
 513           iterations_max = simplify_gen_unary (ZERO_EXTEND, word_mode,
 514                                                iterations_max, mode);
 515         }
 516       else
 517         {
 518           count = lowpart_subreg (word_mode, count, mode);
 519           iterations = lowpart_subreg (word_mode, iterations, mode);
 520           iterations_max = lowpart_subreg (word_mode, iterations_max, mode);
 521         }
 522       PUT_MODE (doloop_reg, word_mode);
 523       doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
 524                                    GEN_INT (level), start_label);
 525     }
 526   if (! doloop_seq)
 527     {
 528       if (dump_file)
 529         fprintf (dump_file,
 530                  "Doloop: Target unwilling to use doloop pattern!\n");
 531       return false;
 532     }
 533
 534   /* If multiple instructions were created, the last must be the
 535      jump instruction.  Also, a raw define_insn may yield a plain
 536      pattern.  */
 537   doloop_pat = doloop_seq;
 538   if (INSN_P (doloop_pat))
 539     {
 540       while (NEXT_INSN (doloop_pat) != NULL_RTX)
 541         doloop_pat = NEXT_INSN (doloop_pat);
 542       if (JUMP_P (doloop_pat))
 543         doloop_pat = PATTERN (doloop_pat);
 544       else
 545         doloop_pat = NULL_RTX;
 546     }
 547
 548   if (! doloop_pat
 549       || ! (condition = doloop_condition_get (doloop_pat)))
 550     {
 551       if (dump_file)
 552         fprintf (dump_file, "Doloop: Unrecognizable doloop pattern!\n");
 553       return false;
 554     }
 555
 556   doloop_modify (loop, desc, doloop_seq, condition, count);
 557   return true;
 558 }
 559
 560 /* This is the main entry point.  Process all LOOPS using doloop_optimize.  */
 561
 562 void
 563 doloop_optimize_loops (struct loops *loops)
 564 {
 565   unsigned i;
 566   struct loop *loop;
 567
 568   for (i = 1; i < loops->num; i++)
 569     {
 570       loop = loops->parray[i];
 571       if (!loop)
 572         continue;
 573
 574       doloop_optimize (loop);
 575     }
 576
 577   iv_analysis_done ();
 578
 579 #ifdef ENABLE_CHECKING
 580   verify_dominators (CDI_DOMINATORS);
 581   verify_loop_structure (loops);
 582 #endif
 583 }
 584 #endif /* HAVE_doloop_end */
 585