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