gcc/hw-doloop.c

   1 /* Code to analyze doloop loops in order for targets to perform late
   2    optimizations converting doloops to other forms of hardware loops.
   3    Copyright (C) 2011 Free Software Foundation, Inc.
   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 "regs.h"
  30 #include "basic-block.h"
  31 #include "tm_p.h"
  32 #include "df.h"
  33 #include "cfgloop.h"
  34 #include "recog.h"
  35 #include "target.h"
  36 #include "hw-doloop.h"
  37
  38 #ifdef HAVE_doloop_end
  39
  40 /* Dump information collected in LOOPS.  */
  41 static void
  42 dump_hwloops (hwloop_info loops)
  43 {
  44   hwloop_info loop;
  45
  46   for (loop = loops; loop; loop = loop->next)
  47     {
  48       hwloop_info i;
  49       basic_block b;
  50       unsigned ix;
  51
  52       fprintf (dump_file, ";; loop %d: ", loop->loop_no);
  53       if (loop->bad)
  54         fprintf (dump_file, "(bad) ");
  55       fprintf (dump_file, "{head:%d, depth:%d, reg:%u}",
  56                loop->head == NULL ? -1 : loop->head->index,
  57                loop->depth, REGNO (loop->iter_reg));
  58
  59       fprintf (dump_file, " blocks: [ ");
  60       for (ix = 0; VEC_iterate (basic_block, loop->blocks, ix, b); ix++)
  61         fprintf (dump_file, "%d ", b->index);
  62       fprintf (dump_file, "] ");
  63
  64       fprintf (dump_file, " inner loops: [ ");
  65       for (ix = 0; VEC_iterate (hwloop_info, loop->loops, ix, i); ix++)
  66         fprintf (dump_file, "%d ", i->loop_no);
  67       fprintf (dump_file, "]\n");
  68     }
  69   fprintf (dump_file, "\n");
  70 }
  71
  72 /* Return true if BB is part of LOOP.  */
  73 static bool
  74 bb_in_loop_p (hwloop_info loop, basic_block bb)
  75 {
  76   return bitmap_bit_p (loop->block_bitmap, bb->index);
  77 }
  78
  79 /* Scan the blocks of LOOP (and its inferiors), and record things such as
  80    hard registers set, jumps out of and within the loop.  */
  81 static void
  82 scan_loop (hwloop_info loop)
  83 {
  84   unsigned ix;
  85   basic_block bb;
  86
  87   if (loop->bad)
  88     return;
  89
  90   if (REGNO_REG_SET_P (df_get_live_in (loop->successor),
  91                        REGNO (loop->iter_reg)))
  92     loop->iter_reg_used_outside = true;
  93
  94   for (ix = 0; VEC_iterate (basic_block, loop->blocks, ix, bb); ix++)
  95     {
  96       rtx insn;
  97       edge e;
  98       edge_iterator ei;
  99
 100       if (bb != loop->tail)
 101         FOR_EACH_EDGE (e, ei, bb->succs)
 102           {
 103             if (bb_in_loop_p (loop, e->dest))
 104               {
 105                 if (!(e->flags & EDGE_FALLTHRU))
 106                   loop->jumps_within = true;
 107               }
 108             else
 109               {
 110                 loop->jumps_outof = true;
 111                 if (!loop->bad)
 112                   gcc_assert (!REGNO_REG_SET_P (df_get_live_in (e->dest),
 113                                                 REGNO (loop->iter_reg)));
 114               }
 115           }
 116
 117       for (insn = BB_HEAD (bb);
 118            insn != NEXT_INSN (BB_END (bb));
 119            insn = NEXT_INSN (insn))
 120         {
 121           df_ref *def_rec;
 122           HARD_REG_SET set_this_insn;
 123
 124           if (!NONDEBUG_INSN_P (insn))
 125             continue;
 126
 127           if (recog_memoized (insn) < 0
 128               && (GET_CODE (PATTERN (insn)) == ASM_INPUT
 129                   || asm_noperands (PATTERN (insn)) >= 0))
 130             loop->has_asm = true;
 131
 132           CLEAR_HARD_REG_SET (set_this_insn);
 133           for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 134             {
 135               rtx dreg = DF_REF_REG (*def_rec);
 136
 137               if (!REG_P (dreg))
 138                 continue;
 139
 140               add_to_hard_reg_set (&set_this_insn, GET_MODE (dreg),
 141                                    REGNO (dreg));
 142             }
 143
 144           if (insn == loop->loop_end)
 145             CLEAR_HARD_REG_BIT (set_this_insn, REGNO (loop->iter_reg));
 146           else if (reg_mentioned_p (loop->iter_reg, PATTERN (insn)))
 147             loop->iter_reg_used = true;
 148           IOR_HARD_REG_SET (loop->regs_set_in_loop, set_this_insn);
 149         }
 150     }
 151 }
 152
 153 /* Compute the incoming_dest and incoming_src members of LOOP by
 154    identifying the edges that jump into the loop.  If there is more
 155    than one block that jumps into the loop, incoming_src will be set
 156    to NULL; likewise, if there is more than one block in the loop that
 157    is the destination of an incoming edge, incoming_dest will be NULL.
 158
 159    Return true if either of these two fields is nonnull, false
 160    otherwise.  */
 161 static bool
 162 process_incoming_edges (hwloop_info loop)
 163 {
 164   edge e;
 165   edge_iterator ei;
 166   bool first = true;
 167
 168   FOR_EACH_EDGE (e, ei, loop->incoming)
 169     {
 170       if (first)
 171         {
 172           loop->incoming_src = e->src;
 173           loop->incoming_dest = e->dest;
 174           first = false;
 175         }
 176       else
 177         {
 178           if (e->dest != loop->incoming_dest)
 179             loop->incoming_dest = NULL;
 180           if (e->src != loop->incoming_src)
 181             loop->incoming_src = NULL;
 182         }
 183     }
 184   if (loop->incoming_src == NULL && loop->incoming_dest == NULL)
 185     return false;
 186
 187   return true;
 188 }
 189
 190 /* Try to identify a forwarder block that jump into LOOP, and add it to
 191    the set of blocks in the loop, updating the vector of incoming blocks as
 192    well.  This transformation gives a second chance to loops we couldn't
 193    otherwise handle by increasing the chance that we'll end up with one
 194    incoming_src block.
 195    Return true if we made a change, false otherwise.  */
 196 static bool
 197 add_forwarder_blocks (hwloop_info loop)
 198 {
 199   edge e;
 200   edge_iterator ei;
 201
 202   FOR_EACH_EDGE (e, ei, loop->incoming)
 203     {
 204       if (forwarder_block_p (e->src))
 205         {
 206           edge e2;
 207           edge_iterator ei2;
 208
 209           if (dump_file)
 210             fprintf (dump_file,
 211                      ";; Adding forwarder block %d to loop %d and retrying\n",
 212                      e->src->index, loop->loop_no);
 213           VEC_safe_push (basic_block, heap, loop->blocks, e->src);
 214           bitmap_set_bit (loop->block_bitmap, e->src->index);
 215           FOR_EACH_EDGE (e2, ei2, e->src->preds)
 216             VEC_safe_push (edge, gc, loop->incoming, e2);
 217           VEC_unordered_remove (edge, loop->incoming, ei.index);
 218           return true;
 219         }
 220     }
 221   return false;
 222 }
 223
 224 /* Called from reorg_loops when a potential loop end is found.  LOOP is
 225    a newly set up structure describing the loop, it is this function's
 226    responsibility to fill most of it.  TAIL_BB and TAIL_INSN point to the
 227    loop_end insn and its enclosing basic block.  REG is the loop counter
 228    register.
 229    For our purposes, a loop is defined by the set of blocks reachable from
 230    the loop head in which the loop counter register is live.  This matches
 231    the expected use; targets that call into this code usually replace the
 232    loop counter with a different special register.  */
 233 static void
 234 discover_loop (hwloop_info loop, basic_block tail_bb, rtx tail_insn, rtx reg)
 235 {
 236   bool found_tail;
 237   unsigned dwork = 0;
 238   basic_block bb;
 239   VEC (basic_block,heap) *works;
 240
 241   loop->tail = tail_bb;
 242   loop->loop_end = tail_insn;
 243   loop->iter_reg = reg;
 244   loop->incoming = VEC_alloc (edge, gc, 2);
 245   loop->start_label = JUMP_LABEL (tail_insn);
 246
 247   if (EDGE_COUNT (tail_bb->succs) != 2)
 248     {
 249       loop->bad = true;
 250       return;
 251     }
 252   loop->head = BRANCH_EDGE (tail_bb)->dest;
 253   loop->successor = FALLTHRU_EDGE (tail_bb)->dest;
 254
 255   works = VEC_alloc (basic_block, heap, 20);
 256   VEC_safe_push (basic_block, heap, works, loop->head);
 257
 258   found_tail = false;
 259   for (dwork = 0; VEC_iterate (basic_block, works, dwork, bb); dwork++)
 260     {
 261       edge e;
 262       edge_iterator ei;
 263       if (bb == EXIT_BLOCK_PTR)
 264         {
 265           /* We've reached the exit block.  The loop must be bad. */
 266           if (dump_file)
 267             fprintf (dump_file,
 268                      ";; Loop is bad - reached exit block while scanning\n");
 269           loop->bad = true;
 270           break;
 271         }
 272
 273       if (bitmap_bit_p (loop->block_bitmap, bb->index))
 274         continue;
 275
 276       /* We've not seen this block before.  Add it to the loop's
 277          list and then add each successor to the work list.  */
 278
 279       VEC_safe_push (basic_block, heap, loop->blocks, bb);
 280       bitmap_set_bit (loop->block_bitmap, bb->index);
 281
 282       if (bb == tail_bb)
 283         found_tail = true;
 284       else
 285         {
 286           FOR_EACH_EDGE (e, ei, bb->succs)
 287             {
 288               basic_block succ = EDGE_SUCC (bb, ei.index)->dest;
 289               if (REGNO_REG_SET_P (df_get_live_in (succ),
 290                                    REGNO (loop->iter_reg)))
 291                 VEC_safe_push (basic_block, heap, works, succ);
 292             }
 293         }
 294     }
 295
 296   if (!found_tail)
 297     loop->bad = true;
 298
 299   /* Find the predecessor, and make sure nothing else jumps into this loop.  */
 300   if (!loop->bad)
 301     {
 302       FOR_EACH_VEC_ELT (basic_block, loop->blocks, dwork, bb)
 303         {
 304           edge e;
 305           edge_iterator ei;
 306           FOR_EACH_EDGE (e, ei, bb->preds)
 307             {
 308               basic_block pred = e->src;
 309
 310               if (!bb_in_loop_p (loop, pred))
 311                 {
 312                   if (dump_file)
 313                     fprintf (dump_file, ";; Loop %d: incoming edge %d -> %d\n",
 314                              loop->loop_no, pred->index,
 315                              e->dest->index);
 316                   VEC_safe_push (edge, gc, loop->incoming, e);
 317                 }
 318             }
 319         }
 320
 321       if (!process_incoming_edges (loop))
 322         {
 323           if (dump_file)
 324             fprintf (dump_file,
 325                      ";; retrying loop %d with forwarder blocks\n",
 326                      loop->loop_no);
 327           if (!add_forwarder_blocks (loop))
 328             {
 329               if (dump_file)
 330                 fprintf (dump_file, ";; No forwarder blocks found\n");
 331               loop->bad = true;
 332             }
 333           else if (!process_incoming_edges (loop))
 334             {
 335               if (dump_file)
 336                 fprintf (dump_file,
 337                          ";; can't find suitable entry for loop %d\n",
 338                          loop->loop_no);
 339             }
 340         }
 341     }
 342
 343   VEC_free (basic_block, heap, works);
 344 }
 345
 346 /* Analyze the structure of the loops in the current function.  Use
 347    STACK for bitmap allocations.  Returns all the valid candidates for
 348    hardware loops found in this function.  HOOKS is the argument
 349    passed to reorg_loops, used here to find the iteration registers
 350    from a loop_end pattern.  */
 351 static hwloop_info
 352 discover_loops (bitmap_obstack *stack, struct hw_doloop_hooks *hooks)
 353 {
 354   hwloop_info loops = NULL;
 355   hwloop_info loop;
 356   basic_block bb;
 357   int nloops = 0;
 358
 359   /* Find all the possible loop tails.  This means searching for every
 360      loop_end instruction.  For each one found, create a hwloop_info
 361      structure and add the head block to the work list. */
 362   FOR_EACH_BB (bb)
 363     {
 364       rtx tail = BB_END (bb);
 365       rtx insn, reg;
 366
 367       while (tail && GET_CODE (tail) == NOTE && tail != BB_HEAD (bb))
 368         tail = PREV_INSN (tail);
 369
 370       if (tail == NULL_RTX)
 371         continue;
 372
 373       if (!JUMP_P (tail))
 374         continue;
 375       reg = hooks->end_pattern_reg (tail);
 376       if (reg == NULL_RTX)
 377         continue;
 378
 379       /* A possible loop end */
 380
 381       /* There's a degenerate case we can handle - an empty loop consisting
 382          of only a back branch.  Handle that by deleting the branch.  */
 383       insn = JUMP_LABEL (tail);
 384       while (insn && !NONDEBUG_INSN_P (insn))
 385         insn = NEXT_INSN (insn);
 386       if (insn == tail)
 387         {
 388           basic_block succ = FALLTHRU_EDGE (bb)->dest;
 389           if (dump_file)
 390             {
 391               fprintf (dump_file, ";; degenerate loop ending at\n");
 392               print_rtl_single (dump_file, tail);
 393             }
 394           if (!REGNO_REG_SET_P (df_get_live_in (succ), REGNO (reg)))
 395             {
 396               if (dump_file)
 397                 fprintf (dump_file, ";; deleting it\n");
 398               delete_insn_and_edges (tail);
 399               continue;
 400             }
 401         }
 402
 403       loop = XCNEW (struct hwloop_info_d);
 404       loop->next = loops;
 405       loops = loop;
 406       loop->loop_no = nloops++;
 407       loop->blocks = VEC_alloc (basic_block, heap, 20);
 408       loop->block_bitmap = BITMAP_ALLOC (stack);
 409
 410       if (dump_file)
 411         {
 412           fprintf (dump_file, ";; potential loop %d ending at\n",
 413                    loop->loop_no);
 414           print_rtl_single (dump_file, tail);
 415         }
 416
 417       discover_loop (loop, bb, tail, reg);
 418     }
 419
 420   /* Compute loop nestings.  Given two loops A and B, either the sets
 421      of their blocks don't intersect at all, or one is the subset of
 422      the other, or the blocks don't form a good nesting structure.  */
 423   for (loop = loops; loop; loop = loop->next)
 424     {
 425       hwloop_info other;
 426
 427       if (loop->bad)
 428         continue;
 429
 430       for (other = loops; other; other = other->next)
 431         {
 432           if (other->bad)
 433             continue;
 434
 435           if (!bitmap_intersect_p (other->block_bitmap, loop->block_bitmap))
 436             continue;
 437           if (!bitmap_intersect_compl_p (other->block_bitmap,
 438                                          loop->block_bitmap))
 439             VEC_safe_push (hwloop_info, heap, loop->loops, other);
 440           else if (!bitmap_intersect_compl_p (loop->block_bitmap,
 441                                               other->block_bitmap))
 442             VEC_safe_push (hwloop_info, heap, other->loops, loop);
 443           else
 444             {
 445               if (dump_file)
 446                 fprintf (dump_file,
 447                          ";; can't find suitable nesting for loops %d and %d\n",
 448                          loop->loop_no, other->loop_no);
 449               loop->bad = other->bad = true;
 450             }
 451         }
 452     }
 453
 454   if (dump_file)
 455     dump_hwloops (loops);
 456
 457   return loops;
 458 }
 459
 460 /* Free up the loop structures in LOOPS.  */
 461 static void
 462 free_loops (hwloop_info loops)
 463 {
 464   while (loops)
 465     {
 466       hwloop_info loop = loops;
 467       loops = loop->next;
 468       VEC_free (hwloop_info, heap, loop->loops);
 469       VEC_free (basic_block, heap, loop->blocks);
 470       BITMAP_FREE (loop->block_bitmap);
 471       XDELETE (loop);
 472     }
 473 }
 474
 475 #define BB_AUX_INDEX(BB) ((intptr_t) (BB)->aux)
 476
 477 /* Initialize the aux fields to give ascending indices to basic blocks.  */
 478 static void
 479 set_bb_indices (void)
 480 {
 481   basic_block bb;
 482   intptr_t index;
 483
 484   index = 0;
 485   FOR_EACH_BB (bb)
 486     bb->aux = (void *) index++;
 487 }
 488
 489 /* The taken-branch edge from the loop end can actually go forward.
 490    If the target's hardware loop support requires that the loop end be
 491    after the loop start, try to reorder a loop's basic blocks when we
 492    find such a case.
 493    This is not very aggressive; it only moves at most one block.  It
 494    does not introduce new branches into loops; it may remove them, or
 495    it may switch fallthru/jump edges.  */
 496 static void
 497 reorder_loops (hwloop_info loops)
 498 {
 499   basic_block bb;
 500   hwloop_info loop;
 501
 502   cfg_layout_initialize (0);
 503
 504   set_bb_indices ();
 505
 506   for (loop = loops; loop; loop = loop->next)
 507     {
 508       edge e;
 509       edge_iterator ei;
 510
 511       if (loop->bad)
 512         continue;
 513
 514       if (BB_AUX_INDEX (loop->head) <= BB_AUX_INDEX (loop->tail))
 515         continue;
 516
 517       FOR_EACH_EDGE (e, ei, loop->head->succs)
 518         {
 519           if (bitmap_bit_p (loop->block_bitmap, e->dest->index)
 520               && BB_AUX_INDEX (e->dest) < BB_AUX_INDEX (loop->tail))
 521             {
 522               basic_block start_bb = e->dest;
 523               basic_block start_prev_bb = start_bb->prev_bb;
 524
 525               if (dump_file)
 526                 fprintf (dump_file, ";; Moving block %d before block %d\n",
 527                          loop->head->index, start_bb->index);
 528               loop->head->prev_bb->next_bb = loop->head->next_bb;
 529               loop->head->next_bb->prev_bb = loop->head->prev_bb;
 530
 531               loop->head->prev_bb = start_prev_bb;
 532               loop->head->next_bb = start_bb;
 533               start_prev_bb->next_bb = start_bb->prev_bb = loop->head;
 534
 535               set_bb_indices ();
 536               break;
 537             }
 538         }
 539       loops = loops->next;
 540     }
 541
 542   FOR_EACH_BB (bb)
 543     {
 544       if (bb->next_bb != EXIT_BLOCK_PTR)
 545         bb->aux = bb->next_bb;
 546       else
 547         bb->aux = NULL;
 548     }
 549   cfg_layout_finalize ();
 550   clear_aux_for_blocks ();
 551   df_analyze ();
 552 }
 553
 554 /* Call the OPT function for LOOP and all of its sub-loops.  This is
 555    done in a depth-first search; innermost loops are visited first.
 556    OPTIMIZE and FAIL are the functions passed to reorg_loops by the
 557    target's reorg pass.  */
 558 static void
 559 optimize_loop (hwloop_info loop, struct hw_doloop_hooks *hooks)
 560 {
 561   int ix;
 562   hwloop_info inner;
 563   int inner_depth = 0;
 564
 565   if (loop->visited)
 566     return;
 567
 568   loop->visited = 1;
 569
 570   if (loop->bad)
 571     {
 572       if (dump_file)
 573         fprintf (dump_file, ";; loop %d bad when found\n", loop->loop_no);
 574       goto bad_loop;
 575     }
 576
 577   /* Every loop contains in its list of inner loops every loop nested inside
 578      it, even if there are intermediate loops.  This works because we're doing
 579      a depth-first search here and never visit a loop more than once.
 580      Recursion depth is effectively limited by the number of available
 581      hardware registers.  */
 582   for (ix = 0; VEC_iterate (hwloop_info, loop->loops, ix, inner); ix++)
 583     {
 584       optimize_loop (inner, hooks);
 585
 586       if (!inner->bad && inner_depth < inner->depth)
 587         inner_depth = inner->depth;
 588       /* The set of registers may be changed while optimizing the inner
 589          loop.  */
 590       IOR_HARD_REG_SET (loop->regs_set_in_loop, inner->regs_set_in_loop);
 591     }
 592
 593   loop->depth = inner_depth + 1;
 594
 595   if (hooks->opt (loop))
 596     return;
 597
 598  bad_loop:
 599   if (dump_file)
 600     fprintf (dump_file, ";; loop %d is bad\n", loop->loop_no);
 601
 602   loop->bad = true;
 603   hooks->fail (loop);
 604 }
 605
 606 /* This function can be used from a port's machine_dependent_reorg to
 607    find and analyze loops that end in loop_end instructions.  It uses
 608    a set of function pointers in HOOKS to call back into the
 609    target-specific functions to perform the actual machine-specific
 610    transformations.
 611
 612    Such transformations typically involve additional set-up
 613    instructions before the loop, to define loop bounds or set up a
 614    special loop counter register.
 615
 616    DO_REORDER should be set to true if we should try to use the
 617    reorder_loops function to ensure the loop end occurs after the loop
 618    start.  This is for use by targets where the loop hardware requires
 619    this condition.
 620
 621    HOOKS is used to pass in target specific hooks; see
 622    hw-doloop.h.  */
 623 void
 624 reorg_loops (bool do_reorder, struct hw_doloop_hooks *hooks)
 625 {
 626   hwloop_info loops = NULL;
 627   hwloop_info loop;
 628   bitmap_obstack stack;
 629
 630   df_live_add_problem ();
 631   df_live_set_all_dirty ();
 632   df_analyze ();
 633
 634   bitmap_obstack_initialize (&stack);
 635
 636   if (dump_file)
 637     fprintf (dump_file, ";; Find loops, first pass\n\n");
 638
 639   loops = discover_loops (&stack, hooks);
 640
 641   if (do_reorder)
 642     {
 643       reorder_loops (loops);
 644       free_loops (loops);
 645
 646       if (dump_file)
 647         fprintf (dump_file, ";; Find loops, second pass\n\n");
 648
 649       loops = discover_loops (&stack, hooks);
 650     }
 651
 652   for (loop = loops; loop; loop = loop->next)
 653     scan_loop (loop);
 654
 655   /* Now apply the optimizations.  */
 656   for (loop = loops; loop; loop = loop->next)
 657     optimize_loop (loop, hooks);
 658
 659   if (dump_file)
 660     {
 661       fprintf (dump_file, ";; After hardware loops optimization:\n\n");
 662       dump_hwloops (loops);
 663     }
 664
 665   free_loops (loops);
 666
 667   if (dump_file)
 668     print_rtl (dump_file, get_insns ());
 669 }
 670 #endif