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