gcc/hw-doloop.cc

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