contrib/gcc/sched-deps.c

   1 /* Instruction scheduling pass.  This file computes dependencies between
   2    instructions.
   3    Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   4    1999, 2000, 2001, 2002 Free Software Foundation, Inc.
   5    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
   6    and currently maintained by, Jim Wilson (wilson@cygnus.com)
   7
   8 This file is part of GCC.
   9
  10 GCC is free software; you can redistribute it and/or modify it under
  11 the terms of the GNU General Public License as published by the Free
  12 Software Foundation; either version 2, or (at your option) any later
  13 version.
  14
  15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  17 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  18 for more details.
  19
  20 You should have received a copy of the GNU General Public License
  21 along with GCC; see the file COPYING.  If not, write to the Free
  22 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  23 02111-1307, USA.  */
  24 \f
  25 #include "config.h"
  26 #include "system.h"
  27 #include "toplev.h"
  28 #include "rtl.h"
  29 #include "tm_p.h"
  30 #include "hard-reg-set.h"
  31 #include "basic-block.h"
  32 #include "regs.h"
  33 #include "function.h"
  34 #include "flags.h"
  35 #include "insn-config.h"
  36 #include "insn-attr.h"
  37 #include "except.h"
  38 #include "toplev.h"
  39 #include "recog.h"
  40 #include "sched-int.h"
  41 #include "params.h"
  42 #include "cselib.h"
  43
  44 extern char *reg_known_equiv_p;
  45 extern rtx *reg_known_value;
  46
  47 static regset_head reg_pending_sets_head;
  48 static regset_head reg_pending_clobbers_head;
  49 static regset_head reg_pending_uses_head;
  50
  51 static regset reg_pending_sets;
  52 static regset reg_pending_clobbers;
  53 static regset reg_pending_uses;
  54 static bool reg_pending_barrier;
  55
  56 /* To speed up the test for duplicate dependency links we keep a
  57    record of dependencies created by add_dependence when the average
  58    number of instructions in a basic block is very large.
  59
  60    Studies have shown that there is typically around 5 instructions between
  61    branches for typical C code.  So we can make a guess that the average
  62    basic block is approximately 5 instructions long; we will choose 100X
  63    the average size as a very large basic block.
  64
  65    Each insn has associated bitmaps for its dependencies.  Each bitmap
  66    has enough entries to represent a dependency on any other insn in
  67    the insn chain.  All bitmap for true dependencies cache is
  68    allocated then the rest two ones are also allocated.  */
  69 static sbitmap *true_dependency_cache;
  70 static sbitmap *anti_dependency_cache;
  71 static sbitmap *output_dependency_cache;
  72
  73 /* To speed up checking consistency of formed forward insn
  74    dependencies we use the following cache.  Another possible solution
  75    could be switching off checking duplication of insns in forward
  76    dependencies.  */
  77 #ifdef ENABLE_CHECKING
  78 static sbitmap *forward_dependency_cache;
  79 #endif
  80
  81 static int deps_may_trap_p PARAMS ((rtx));
  82 static void add_dependence_list PARAMS ((rtx, rtx, enum reg_note));
  83 static void add_dependence_list_and_free PARAMS ((rtx, rtx *, enum reg_note));
  84 static void remove_dependence PARAMS ((rtx, rtx));
  85 static void set_sched_group_p PARAMS ((rtx));
  86
  87 static void flush_pending_lists PARAMS ((struct deps *, rtx, int, int));
  88 static void sched_analyze_1 PARAMS ((struct deps *, rtx, rtx));
  89 static void sched_analyze_2 PARAMS ((struct deps *, rtx, rtx));
  90 static void sched_analyze_insn PARAMS ((struct deps *, rtx, rtx, rtx));
  91 static rtx group_leader PARAMS ((rtx));
  92
  93 static rtx get_condition PARAMS ((rtx));
  94 static int conditions_mutex_p PARAMS ((rtx, rtx));
  95 \f
  96 /* Return nonzero if a load of the memory reference MEM can cause a trap.  */
  97
  98 static int
  99 deps_may_trap_p (mem)
 100      rtx mem;
 101 {
 102   rtx addr = XEXP (mem, 0);
 103
 104   if (REG_P (addr)
 105       && REGNO (addr) >= FIRST_PSEUDO_REGISTER
 106       && reg_known_value[REGNO (addr)])
 107     addr = reg_known_value[REGNO (addr)];
 108   return rtx_addr_can_trap_p (addr);
 109 }
 110 \f
 111 /* Return the INSN_LIST containing INSN in LIST, or NULL
 112    if LIST does not contain INSN.  */
 113
 114 rtx
 115 find_insn_list (insn, list)
 116      rtx insn;
 117      rtx list;
 118 {
 119   while (list)
 120     {
 121       if (XEXP (list, 0) == insn)
 122         return list;
 123       list = XEXP (list, 1);
 124     }
 125   return 0;
 126 }
 127 \f
 128 /* Find the condition under which INSN is executed.  */
 129
 130 static rtx
 131 get_condition (insn)
 132      rtx insn;
 133 {
 134   rtx pat = PATTERN (insn);
 135   rtx cond;
 136
 137   if (pat == 0)
 138     return 0;
 139   if (GET_CODE (pat) == COND_EXEC)
 140     return COND_EXEC_TEST (pat);
 141   if (GET_CODE (insn) != JUMP_INSN)
 142     return 0;
 143   if (GET_CODE (pat) != SET || SET_SRC (pat) != pc_rtx)
 144     return 0;
 145   if (GET_CODE (SET_DEST (pat)) != IF_THEN_ELSE)
 146     return 0;
 147   pat = SET_DEST (pat);
 148   cond = XEXP (pat, 0);
 149   if (GET_CODE (XEXP (cond, 1)) == LABEL_REF
 150       && XEXP (cond, 2) == pc_rtx)
 151     return cond;
 152   else if (GET_CODE (XEXP (cond, 2)) == LABEL_REF
 153            && XEXP (cond, 1) == pc_rtx)
 154     return gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)), GET_MODE (cond),
 155                            XEXP (cond, 0), XEXP (cond, 1));
 156   else
 157     return 0;
 158 }
 159
 160 /* Return nonzero if conditions COND1 and COND2 can never be both true.  */
 161
 162 static int
 163 conditions_mutex_p (cond1, cond2)
 164      rtx cond1, cond2;
 165 {
 166   if (GET_RTX_CLASS (GET_CODE (cond1)) == '<'
 167       && GET_RTX_CLASS (GET_CODE (cond2)) == '<'
 168       && GET_CODE (cond1) == reverse_condition (GET_CODE (cond2))
 169       && XEXP (cond1, 0) == XEXP (cond2, 0)
 170       && XEXP (cond1, 1) == XEXP (cond2, 1))
 171     return 1;
 172   return 0;
 173 }
 174 \f
 175 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
 176    LOG_LINKS of INSN, if not already there.  DEP_TYPE indicates the type
 177    of dependence that this link represents.  */
 178
 179 void
 180 add_dependence (insn, elem, dep_type)
 181      rtx insn;
 182      rtx elem;
 183      enum reg_note dep_type;
 184 {
 185   rtx link, next;
 186   int present_p;
 187   rtx cond1, cond2;
 188
 189   /* Don't depend an insn on itself.  */
 190   if (insn == elem)
 191     return;
 192
 193   /* We can get a dependency on deleted insns due to optimizations in
 194      the register allocation and reloading or due to splitting.  Any
 195      such dependency is useless and can be ignored.  */
 196   if (GET_CODE (elem) == NOTE)
 197     return;
 198
 199   /* flow.c doesn't handle conditional lifetimes entirely correctly;
 200      calls mess up the conditional lifetimes.  */
 201   /* ??? add_dependence is the wrong place to be eliding dependencies,
 202      as that forgets that the condition expressions themselves may
 203      be dependent.  */
 204   if (GET_CODE (insn) != CALL_INSN && GET_CODE (elem) != CALL_INSN)
 205     {
 206       cond1 = get_condition (insn);
 207       cond2 = get_condition (elem);
 208       if (cond1 && cond2
 209           && conditions_mutex_p (cond1, cond2)
 210           /* Make sure first instruction doesn't affect condition of second
 211              instruction if switched.  */
 212           && !modified_in_p (cond1, elem)
 213           /* Make sure second instruction doesn't affect condition of first
 214              instruction if switched.  */
 215           && !modified_in_p (cond2, insn))
 216         return;
 217     }
 218
 219   /* If elem is part of a sequence that must be scheduled together, then
 220      make the dependence point to the last insn of the sequence.
 221      When HAVE_cc0, it is possible for NOTEs to exist between users and
 222      setters of the condition codes, so we must skip past notes here.
 223      Otherwise, NOTEs are impossible here.  */
 224   next = next_nonnote_insn (elem);
 225   if (next && SCHED_GROUP_P (next)
 226       && GET_CODE (next) != CODE_LABEL)
 227     {
 228       /* Notes will never intervene here though, so don't bother checking
 229          for them.  */
 230       /* Hah!  Wrong.  */
 231       /* We must reject CODE_LABELs, so that we don't get confused by one
 232          that has LABEL_PRESERVE_P set, which is represented by the same
 233          bit in the rtl as SCHED_GROUP_P.  A CODE_LABEL can never be
 234          SCHED_GROUP_P.  */
 235
 236       rtx nnext;
 237       while ((nnext = next_nonnote_insn (next)) != NULL
 238              && SCHED_GROUP_P (nnext)
 239              && GET_CODE (nnext) != CODE_LABEL)
 240         next = nnext;
 241
 242       /* Again, don't depend an insn on itself.  */
 243       if (insn == next)
 244         return;
 245
 246       /* Make the dependence to NEXT, the last insn of the group, instead
 247          of the original ELEM.  */
 248       elem = next;
 249     }
 250
 251   present_p = 1;
 252 #ifdef INSN_SCHEDULING
 253   /* ??? No good way to tell from here whether we're doing interblock
 254      scheduling.  Possibly add another callback.  */
 255 #if 0
 256   /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
 257      No need for interblock dependences with calls, since
 258      calls are not moved between blocks.   Note: the edge where
 259      elem is a CALL is still required.  */
 260   if (GET_CODE (insn) == CALL_INSN
 261       && (INSN_BB (elem) != INSN_BB (insn)))
 262     return;
 263 #endif
 264
 265   /* If we already have a dependency for ELEM, then we do not need to
 266      do anything.  Avoiding the list walk below can cut compile times
 267      dramatically for some code.  */
 268   if (true_dependency_cache != NULL)
 269     {
 270       enum reg_note present_dep_type = 0;
 271
 272       if (anti_dependency_cache == NULL || output_dependency_cache == NULL)
 273         abort ();
 274       if (TEST_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)))
 275         /* Do nothing (present_set_type is already 0).  */
 276         ;
 277       else if (TEST_BIT (anti_dependency_cache[INSN_LUID (insn)],
 278                          INSN_LUID (elem)))
 279         present_dep_type = REG_DEP_ANTI;
 280       else if (TEST_BIT (output_dependency_cache[INSN_LUID (insn)],
 281                          INSN_LUID (elem)))
 282         present_dep_type = REG_DEP_OUTPUT;
 283       else
 284         present_p = 0;
 285       if (present_p && (int) dep_type >= (int) present_dep_type)
 286         return;
 287     }
 288 #endif
 289
 290   /* Check that we don't already have this dependence.  */
 291   if (present_p)
 292     for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
 293       if (XEXP (link, 0) == elem)
 294         {
 295 #ifdef INSN_SCHEDULING
 296           /* Clear corresponding cache entry because type of the link
 297              may be changed.  */
 298           if (true_dependency_cache != NULL)
 299             {
 300               if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
 301                 RESET_BIT (anti_dependency_cache[INSN_LUID (insn)],
 302                            INSN_LUID (elem));
 303               else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT
 304                        && output_dependency_cache)
 305                 RESET_BIT (output_dependency_cache[INSN_LUID (insn)],
 306                            INSN_LUID (elem));
 307               else
 308                 abort ();
 309             }
 310 #endif
 311
 312           /* If this is a more restrictive type of dependence than the existing
 313              one, then change the existing dependence to this type.  */
 314           if ((int) dep_type < (int) REG_NOTE_KIND (link))
 315             PUT_REG_NOTE_KIND (link, dep_type);
 316
 317 #ifdef INSN_SCHEDULING
 318           /* If we are adding a dependency to INSN's LOG_LINKs, then
 319              note that in the bitmap caches of dependency information.  */
 320           if (true_dependency_cache != NULL)
 321             {
 322               if ((int) REG_NOTE_KIND (link) == 0)
 323                 SET_BIT (true_dependency_cache[INSN_LUID (insn)],
 324                          INSN_LUID (elem));
 325               else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
 326                 SET_BIT (anti_dependency_cache[INSN_LUID (insn)],
 327                          INSN_LUID (elem));
 328               else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
 329                 SET_BIT (output_dependency_cache[INSN_LUID (insn)],
 330                          INSN_LUID (elem));
 331             }
 332 #endif
 333           return;
 334       }
 335   /* Might want to check one level of transitivity to save conses.  */
 336
 337   link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
 338   LOG_LINKS (insn) = link;
 339
 340   /* Insn dependency, not data dependency.  */
 341   PUT_REG_NOTE_KIND (link, dep_type);
 342
 343 #ifdef INSN_SCHEDULING
 344   /* If we are adding a dependency to INSN's LOG_LINKs, then note that
 345      in the bitmap caches of dependency information.  */
 346   if (true_dependency_cache != NULL)
 347     {
 348       if ((int) dep_type == 0)
 349         SET_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
 350       else if (dep_type == REG_DEP_ANTI)
 351         SET_BIT (anti_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
 352       else if (dep_type == REG_DEP_OUTPUT)
 353         SET_BIT (output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
 354     }
 355 #endif
 356 }
 357
 358 /* A convenience wrapper to operate on an entire list.  */
 359
 360 static void
 361 add_dependence_list (insn, list, dep_type)
 362      rtx insn, list;
 363      enum reg_note dep_type;
 364 {
 365   for (; list; list = XEXP (list, 1))
 366     add_dependence (insn, XEXP (list, 0), dep_type);
 367 }
 368
 369 /* Similar, but free *LISTP at the same time.  */
 370
 371 static void
 372 add_dependence_list_and_free (insn, listp, dep_type)
 373      rtx insn;
 374      rtx *listp;
 375      enum reg_note dep_type;
 376 {
 377   rtx list, next;
 378   for (list = *listp, *listp = NULL; list ; list = next)
 379     {
 380       next = XEXP (list, 1);
 381       add_dependence (insn, XEXP (list, 0), dep_type);
 382       free_INSN_LIST_node (list);
 383     }
 384 }
 385
 386 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
 387    of INSN.  Abort if not found.  */
 388
 389 static void
 390 remove_dependence (insn, elem)
 391      rtx insn;
 392      rtx elem;
 393 {
 394   rtx prev, link, next;
 395   int found = 0;
 396
 397   for (prev = 0, link = LOG_LINKS (insn); link; link = next)
 398     {
 399       next = XEXP (link, 1);
 400       if (XEXP (link, 0) == elem)
 401         {
 402           if (prev)
 403             XEXP (prev, 1) = next;
 404           else
 405             LOG_LINKS (insn) = next;
 406
 407 #ifdef INSN_SCHEDULING
 408           /* If we are removing a dependency from the LOG_LINKS list,
 409              make sure to remove it from the cache too.  */
 410           if (true_dependency_cache != NULL)
 411             {
 412               if (REG_NOTE_KIND (link) == 0)
 413                 RESET_BIT (true_dependency_cache[INSN_LUID (insn)],
 414                            INSN_LUID (elem));
 415               else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
 416                 RESET_BIT (anti_dependency_cache[INSN_LUID (insn)],
 417                            INSN_LUID (elem));
 418               else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
 419                 RESET_BIT (output_dependency_cache[INSN_LUID (insn)],
 420                            INSN_LUID (elem));
 421             }
 422 #endif
 423
 424           free_INSN_LIST_node (link);
 425
 426           found = 1;
 427         }
 428       else
 429         prev = link;
 430     }
 431
 432   if (!found)
 433     abort ();
 434   return;
 435 }
 436
 437 /* Return an insn which represents a SCHED_GROUP, which is
 438    the last insn in the group.  */
 439
 440 static rtx
 441 group_leader (insn)
 442      rtx insn;
 443 {
 444   rtx prev;
 445
 446   do
 447     {
 448       prev = insn;
 449       insn = next_nonnote_insn (insn);
 450     }
 451   while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL));
 452
 453   return prev;
 454 }
 455
 456 /* Set SCHED_GROUP_P and care for the rest of the bookkeeping that
 457    goes along with that.  */
 458
 459 static void
 460 set_sched_group_p (insn)
 461      rtx insn;
 462 {
 463   rtx link, prev;
 464
 465   SCHED_GROUP_P (insn) = 1;
 466
 467   /* There may be a note before this insn now, but all notes will
 468      be removed before we actually try to schedule the insns, so
 469      it won't cause a problem later.  We must avoid it here though.  */
 470   prev = prev_nonnote_insn (insn);
 471
 472   /* Make a copy of all dependencies on the immediately previous insn,
 473      and add to this insn.  This is so that all the dependencies will
 474      apply to the group.  Remove an explicit dependence on this insn
 475      as SCHED_GROUP_P now represents it.  */
 476
 477   if (find_insn_list (prev, LOG_LINKS (insn)))
 478     remove_dependence (insn, prev);
 479
 480   for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
 481     add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
 482 }
 483 \f
 484 /* Process an insn's memory dependencies.  There are four kinds of
 485    dependencies:
 486
 487    (0) read dependence: read follows read
 488    (1) true dependence: read follows write
 489    (2) anti dependence: write follows read
 490    (3) output dependence: write follows write
 491
 492    We are careful to build only dependencies which actually exist, and
 493    use transitivity to avoid building too many links.  */
 494
 495 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
 496    The MEM is a memory reference contained within INSN, which we are saving
 497    so that we can do memory aliasing on it.  */
 498
 499 void
 500 add_insn_mem_dependence (deps, insn_list, mem_list, insn, mem)
 501      struct deps *deps;
 502      rtx *insn_list, *mem_list, insn, mem;
 503 {
 504   rtx link;
 505
 506   link = alloc_INSN_LIST (insn, *insn_list);
 507   *insn_list = link;
 508
 509   if (current_sched_info->use_cselib)
 510     {
 511       mem = shallow_copy_rtx (mem);
 512       XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0));
 513     }
 514   link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
 515   *mem_list = link;
 516
 517   deps->pending_lists_length++;
 518 }
 519
 520 /* Make a dependency between every memory reference on the pending lists
 521    and INSN, thus flushing the pending lists.  FOR_READ is true if emitting
 522    dependencies for a read operation, similarly with FOR_WRITE.  */
 523
 524 static void
 525 flush_pending_lists (deps, insn, for_read, for_write)
 526      struct deps *deps;
 527      rtx insn;
 528      int for_read, for_write;
 529 {
 530   if (for_write)
 531     {
 532       add_dependence_list_and_free (insn, &deps->pending_read_insns,
 533                                     REG_DEP_ANTI);
 534       free_EXPR_LIST_list (&deps->pending_read_mems);
 535     }
 536
 537   add_dependence_list_and_free (insn, &deps->pending_write_insns,
 538                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
 539   free_EXPR_LIST_list (&deps->pending_write_mems);
 540   deps->pending_lists_length = 0;
 541
 542   add_dependence_list_and_free (insn, &deps->last_pending_memory_flush,
 543                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
 544   deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
 545   deps->pending_flush_length = 1;
 546 }
 547 \f
 548 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
 549    rtx, X, creating all dependencies generated by the write to the
 550    destination of X, and reads of everything mentioned.  */
 551
 552 static void
 553 sched_analyze_1 (deps, x, insn)
 554      struct deps *deps;
 555      rtx x;
 556      rtx insn;
 557 {
 558   int regno;
 559   rtx dest = XEXP (x, 0);
 560   enum rtx_code code = GET_CODE (x);
 561
 562   if (dest == 0)
 563     return;
 564
 565   if (GET_CODE (dest) == PARALLEL)
 566     {
 567       int i;
 568
 569       for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
 570         if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
 571           sched_analyze_1 (deps,
 572                            gen_rtx_CLOBBER (VOIDmode,
 573                                             XEXP (XVECEXP (dest, 0, i), 0)),
 574                            insn);
 575
 576       if (GET_CODE (x) == SET)
 577         sched_analyze_2 (deps, SET_SRC (x), insn);
 578       return;
 579     }
 580
 581   while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
 582          || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
 583     {
 584       if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
 585         {
 586           /* The second and third arguments are values read by this insn.  */
 587           sched_analyze_2 (deps, XEXP (dest, 1), insn);
 588           sched_analyze_2 (deps, XEXP (dest, 2), insn);
 589         }
 590       dest = XEXP (dest, 0);
 591     }
 592
 593   if (GET_CODE (dest) == REG)
 594     {
 595       regno = REGNO (dest);
 596
 597       /* A hard reg in a wide mode may really be multiple registers.
 598          If so, mark all of them just like the first.  */
 599       if (regno < FIRST_PSEUDO_REGISTER)
 600         {
 601           int i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
 602           if (code == SET)
 603             {
 604               while (--i >= 0)
 605                 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
 606             }
 607           else
 608             {
 609               while (--i >= 0)
 610                 SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
 611             }
 612         }
 613       /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
 614          it does not reload.  Ignore these as they have served their
 615          purpose already.  */
 616       else if (regno >= deps->max_reg)
 617         {
 618           if (GET_CODE (PATTERN (insn)) != USE
 619               && GET_CODE (PATTERN (insn)) != CLOBBER)
 620             abort ();
 621         }
 622       else
 623         {
 624           if (code == SET)
 625             SET_REGNO_REG_SET (reg_pending_sets, regno);
 626           else
 627             SET_REGNO_REG_SET (reg_pending_clobbers, regno);
 628
 629           /* Pseudos that are REG_EQUIV to something may be replaced
 630              by that during reloading.  We need only add dependencies for
 631              the address in the REG_EQUIV note.  */
 632           if (!reload_completed
 633               && reg_known_equiv_p[regno]
 634               && GET_CODE (reg_known_value[regno]) == MEM)
 635             sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn);
 636
 637           /* Don't let it cross a call after scheduling if it doesn't
 638              already cross one.  */
 639           if (REG_N_CALLS_CROSSED (regno) == 0)
 640             add_dependence_list (insn, deps->last_function_call, REG_DEP_ANTI);
 641         }
 642     }
 643   else if (GET_CODE (dest) == MEM)
 644     {
 645       /* Writing memory.  */
 646       rtx t = dest;
 647
 648       if (current_sched_info->use_cselib)
 649         {
 650           t = shallow_copy_rtx (dest);
 651           cselib_lookup (XEXP (t, 0), Pmode, 1);
 652           XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
 653         }
 654
 655       if (deps->pending_lists_length > MAX_PENDING_LIST_LENGTH)
 656         {
 657           /* Flush all pending reads and writes to prevent the pending lists
 658              from getting any larger.  Insn scheduling runs too slowly when
 659              these lists get long.  When compiling GCC with itself,
 660              this flush occurs 8 times for sparc, and 10 times for m88k using
 661              the default value of 32.  */
 662           flush_pending_lists (deps, insn, false, true);
 663         }
 664       else
 665         {
 666           rtx pending, pending_mem;
 667
 668           pending = deps->pending_read_insns;
 669           pending_mem = deps->pending_read_mems;
 670           while (pending)
 671             {
 672               if (anti_dependence (XEXP (pending_mem, 0), t))
 673                 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
 674
 675               pending = XEXP (pending, 1);
 676               pending_mem = XEXP (pending_mem, 1);
 677             }
 678
 679           pending = deps->pending_write_insns;
 680           pending_mem = deps->pending_write_mems;
 681           while (pending)
 682             {
 683               if (output_dependence (XEXP (pending_mem, 0), t))
 684                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
 685
 686               pending = XEXP (pending, 1);
 687               pending_mem = XEXP (pending_mem, 1);
 688             }
 689
 690           add_dependence_list (insn, deps->last_pending_memory_flush,
 691                                REG_DEP_ANTI);
 692
 693           add_insn_mem_dependence (deps, &deps->pending_write_insns,
 694                                    &deps->pending_write_mems, insn, dest);
 695         }
 696       sched_analyze_2 (deps, XEXP (dest, 0), insn);
 697     }
 698
 699   /* Analyze reads.  */
 700   if (GET_CODE (x) == SET)
 701     sched_analyze_2 (deps, SET_SRC (x), insn);
 702 }
 703
 704 /* Analyze the uses of memory and registers in rtx X in INSN.  */
 705
 706 static void
 707 sched_analyze_2 (deps, x, insn)
 708      struct deps *deps;
 709      rtx x;
 710      rtx insn;
 711 {
 712   int i;
 713   int j;
 714   enum rtx_code code;
 715   const char *fmt;
 716
 717   if (x == 0)
 718     return;
 719
 720   code = GET_CODE (x);
 721
 722   switch (code)
 723     {
 724     case CONST_INT:
 725     case CONST_DOUBLE:
 726     case CONST_VECTOR:
 727     case SYMBOL_REF:
 728     case CONST:
 729     case LABEL_REF:
 730       /* Ignore constants.  Note that we must handle CONST_DOUBLE here
 731          because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
 732          this does not mean that this insn is using cc0.  */
 733       return;
 734
 735 #ifdef HAVE_cc0
 736     case CC0:
 737       /* User of CC0 depends on immediately preceding insn.  */
 738       set_sched_group_p (insn);
 739       return;
 740 #endif
 741
 742     case REG:
 743       {
 744         int regno = REGNO (x);
 745         if (regno < FIRST_PSEUDO_REGISTER)
 746           {
 747             int i = HARD_REGNO_NREGS (regno, GET_MODE (x));
 748             while (--i >= 0)
 749               SET_REGNO_REG_SET (reg_pending_uses, regno + i);
 750           }
 751         /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
 752            it does not reload.  Ignore these as they have served their
 753            purpose already.  */
 754         else if (regno >= deps->max_reg)
 755           {
 756             if (GET_CODE (PATTERN (insn)) != USE
 757                 && GET_CODE (PATTERN (insn)) != CLOBBER)
 758               abort ();
 759           }
 760         else
 761           {
 762             SET_REGNO_REG_SET (reg_pending_uses, regno);
 763
 764             /* Pseudos that are REG_EQUIV to something may be replaced
 765                by that during reloading.  We need only add dependencies for
 766                the address in the REG_EQUIV note.  */
 767             if (!reload_completed
 768                 && reg_known_equiv_p[regno]
 769                 && GET_CODE (reg_known_value[regno]) == MEM)
 770               sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn);
 771
 772             /* If the register does not already cross any calls, then add this
 773                insn to the sched_before_next_call list so that it will still
 774                not cross calls after scheduling.  */
 775             if (REG_N_CALLS_CROSSED (regno) == 0)
 776               deps->sched_before_next_call
 777                 = alloc_INSN_LIST (insn, deps->sched_before_next_call);
 778           }
 779         return;
 780       }
 781
 782     case MEM:
 783       {
 784         /* Reading memory.  */
 785         rtx u;
 786         rtx pending, pending_mem;
 787         rtx t = x;
 788
 789         if (current_sched_info->use_cselib)
 790           {
 791             t = shallow_copy_rtx (t);
 792             cselib_lookup (XEXP (t, 0), Pmode, 1);
 793             XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
 794           }
 795         pending = deps->pending_read_insns;
 796         pending_mem = deps->pending_read_mems;
 797         while (pending)
 798           {
 799             if (read_dependence (XEXP (pending_mem, 0), t))
 800               add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
 801
 802             pending = XEXP (pending, 1);
 803             pending_mem = XEXP (pending_mem, 1);
 804           }
 805
 806         pending = deps->pending_write_insns;
 807         pending_mem = deps->pending_write_mems;
 808         while (pending)
 809           {
 810             if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
 811                                  t, rtx_varies_p))
 812               add_dependence (insn, XEXP (pending, 0), 0);
 813
 814             pending = XEXP (pending, 1);
 815             pending_mem = XEXP (pending_mem, 1);
 816           }
 817
 818         for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
 819           if (GET_CODE (XEXP (u, 0)) != JUMP_INSN
 820               || deps_may_trap_p (x))
 821             add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
 822
 823         /* Always add these dependencies to pending_reads, since
 824            this insn may be followed by a write.  */
 825         add_insn_mem_dependence (deps, &deps->pending_read_insns,
 826                                  &deps->pending_read_mems, insn, x);
 827
 828         /* Take advantage of tail recursion here.  */
 829         sched_analyze_2 (deps, XEXP (x, 0), insn);
 830         return;
 831       }
 832
 833     /* Force pending stores to memory in case a trap handler needs them.  */
 834     case TRAP_IF:
 835       flush_pending_lists (deps, insn, true, false);
 836       break;
 837
 838     case ASM_OPERANDS:
 839     case ASM_INPUT:
 840     case UNSPEC_VOLATILE:
 841       {
 842         /* Traditional and volatile asm instructions must be considered to use
 843            and clobber all hard registers, all pseudo-registers and all of
 844            memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
 845
 846            Consider for instance a volatile asm that changes the fpu rounding
 847            mode.  An insn should not be moved across this even if it only uses
 848            pseudo-regs because it might give an incorrectly rounded result.  */
 849         if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
 850           reg_pending_barrier = true;
 851
 852         /* For all ASM_OPERANDS, we must traverse the vector of input operands.
 853            We can not just fall through here since then we would be confused
 854            by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
 855            traditional asms unlike their normal usage.  */
 856
 857         if (code == ASM_OPERANDS)
 858           {
 859             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
 860               sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
 861             return;
 862           }
 863         break;
 864       }
 865
 866     case PRE_DEC:
 867     case POST_DEC:
 868     case PRE_INC:
 869     case POST_INC:
 870       /* These both read and modify the result.  We must handle them as writes
 871          to get proper dependencies for following instructions.  We must handle
 872          them as reads to get proper dependencies from this to previous
 873          instructions.  Thus we need to pass them to both sched_analyze_1
 874          and sched_analyze_2.  We must call sched_analyze_2 first in order
 875          to get the proper antecedent for the read.  */
 876       sched_analyze_2 (deps, XEXP (x, 0), insn);
 877       sched_analyze_1 (deps, x, insn);
 878       return;
 879
 880     case POST_MODIFY:
 881     case PRE_MODIFY:
 882       /* op0 = op0 + op1 */
 883       sched_analyze_2 (deps, XEXP (x, 0), insn);
 884       sched_analyze_2 (deps, XEXP (x, 1), insn);
 885       sched_analyze_1 (deps, x, insn);
 886       return;
 887
 888     default:
 889       break;
 890     }
 891
 892   /* Other cases: walk the insn.  */
 893   fmt = GET_RTX_FORMAT (code);
 894   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 895     {
 896       if (fmt[i] == 'e')
 897         sched_analyze_2 (deps, XEXP (x, i), insn);
 898       else if (fmt[i] == 'E')
 899         for (j = 0; j < XVECLEN (x, i); j++)
 900           sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
 901     }
 902 }
 903
 904 /* Analyze an INSN with pattern X to find all dependencies.  */
 905
 906 static void
 907 sched_analyze_insn (deps, x, insn, loop_notes)
 908      struct deps *deps;
 909      rtx x, insn;
 910      rtx loop_notes;
 911 {
 912   RTX_CODE code = GET_CODE (x);
 913   rtx link;
 914   int i;
 915
 916   if (code == COND_EXEC)
 917     {
 918       sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
 919
 920       /* ??? Should be recording conditions so we reduce the number of
 921          false dependencies.  */
 922       x = COND_EXEC_CODE (x);
 923       code = GET_CODE (x);
 924     }
 925   if (code == SET || code == CLOBBER)
 926     {
 927       sched_analyze_1 (deps, x, insn);
 928
 929       /* Bare clobber insns are used for letting life analysis, reg-stack
 930          and others know that a value is dead.  Depend on the last call
 931          instruction so that reg-stack won't get confused.  */
 932       if (code == CLOBBER)
 933         add_dependence_list (insn, deps->last_function_call, REG_DEP_OUTPUT);
 934     }
 935   else if (code == PARALLEL)
 936     {
 937       int i;
 938       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
 939         {
 940           rtx sub = XVECEXP (x, 0, i);
 941           code = GET_CODE (sub);
 942
 943           if (code == COND_EXEC)
 944             {
 945               sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
 946               sub = COND_EXEC_CODE (sub);
 947               code = GET_CODE (sub);
 948             }
 949           if (code == SET || code == CLOBBER)
 950             sched_analyze_1 (deps, sub, insn);
 951           else
 952             sched_analyze_2 (deps, sub, insn);
 953         }
 954     }
 955   else
 956     sched_analyze_2 (deps, x, insn);
 957
 958   /* Mark registers CLOBBERED or used by called function.  */
 959   if (GET_CODE (insn) == CALL_INSN)
 960     {
 961       for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
 962         {
 963           if (GET_CODE (XEXP (link, 0)) == CLOBBER)
 964             sched_analyze_1 (deps, XEXP (link, 0), insn);
 965           else
 966             sched_analyze_2 (deps, XEXP (link, 0), insn);
 967         }
 968       if (find_reg_note (insn, REG_SETJMP, NULL))
 969         reg_pending_barrier = true;
 970     }
 971
 972   if (GET_CODE (insn) == JUMP_INSN)
 973     {
 974       rtx next;
 975       next = next_nonnote_insn (insn);
 976       if (next && GET_CODE (next) == BARRIER)
 977         reg_pending_barrier = true;
 978       else
 979         {
 980           rtx pending, pending_mem;
 981           regset_head tmp;
 982           INIT_REG_SET (&tmp);
 983
 984           (*current_sched_info->compute_jump_reg_dependencies) (insn, &tmp);
 985           IOR_REG_SET (reg_pending_uses, &tmp);
 986           CLEAR_REG_SET (&tmp);
 987
 988           /* All memory writes and volatile reads must happen before the
 989              jump.  Non-volatile reads must happen before the jump iff
 990              the result is needed by the above register used mask.  */
 991
 992           pending = deps->pending_write_insns;
 993           pending_mem = deps->pending_write_mems;
 994           while (pending)
 995             {
 996               add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
 997               pending = XEXP (pending, 1);
 998               pending_mem = XEXP (pending_mem, 1);
 999             }
1000
1001           pending = deps->pending_read_insns;
1002           pending_mem = deps->pending_read_mems;
1003           while (pending)
1004             {
1005               if (MEM_VOLATILE_P (XEXP (pending_mem, 0)))
1006                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
1007               pending = XEXP (pending, 1);
1008               pending_mem = XEXP (pending_mem, 1);
1009             }
1010
1011           add_dependence_list (insn, deps->last_pending_memory_flush,
1012                                REG_DEP_ANTI);
1013         }
1014     }
1015
1016   /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
1017      block, then we must be sure that no instructions are scheduled across it.
1018      Otherwise, the reg_n_refs info (which depends on loop_depth) would
1019      become incorrect.  */
1020   if (loop_notes)
1021     {
1022       rtx link;
1023
1024       /* Update loop_notes with any notes from this insn.  Also determine
1025          if any of the notes on the list correspond to instruction scheduling
1026          barriers (loop, eh & setjmp notes, but not range notes).  */
1027       link = loop_notes;
1028       while (XEXP (link, 1))
1029         {
1030           if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
1031               || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END
1032               || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG
1033               || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END)
1034             reg_pending_barrier = true;
1035
1036           link = XEXP (link, 1);
1037         }
1038       XEXP (link, 1) = REG_NOTES (insn);
1039       REG_NOTES (insn) = loop_notes;
1040     }
1041
1042   /* If this instruction can throw an exception, then moving it changes
1043      where block boundaries fall.  This is mighty confusing elsewhere.
1044      Therefore, prevent such an instruction from being moved.  */
1045   if (can_throw_internal (insn))
1046     reg_pending_barrier = true;
1047
1048   /* Add dependencies if a scheduling barrier was found.  */
1049   if (reg_pending_barrier)
1050     {
1051       if (GET_CODE (PATTERN (insn)) == COND_EXEC)
1052         {
1053           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i,
1054             {
1055               struct deps_reg *reg_last = &deps->reg_last[i];
1056               add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1057               add_dependence_list (insn, reg_last->sets, 0);
1058               add_dependence_list (insn, reg_last->clobbers, 0);
1059             });
1060         }
1061       else
1062         {
1063           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i,
1064             {
1065               struct deps_reg *reg_last = &deps->reg_last[i];
1066               add_dependence_list_and_free (insn, &reg_last->uses,
1067                                             REG_DEP_ANTI);
1068               add_dependence_list_and_free (insn, &reg_last->sets, 0);
1069               add_dependence_list_and_free (insn, &reg_last->clobbers, 0);
1070               reg_last->uses_length = 0;
1071               reg_last->clobbers_length = 0;
1072             });
1073         }
1074
1075       for (i = 0; i < deps->max_reg; i++)
1076         {
1077           struct deps_reg *reg_last = &deps->reg_last[i];
1078           reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1079           SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
1080         }
1081
1082       flush_pending_lists (deps, insn, true, true);
1083       reg_pending_barrier = false;
1084     }
1085   else
1086     {
1087       /* If the current insn is conditional, we can't free any
1088          of the lists.  */
1089       if (GET_CODE (PATTERN (insn)) == COND_EXEC)
1090         {
1091           EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i,
1092             {
1093               struct deps_reg *reg_last = &deps->reg_last[i];
1094               add_dependence_list (insn, reg_last->sets, 0);
1095               add_dependence_list (insn, reg_last->clobbers, 0);
1096               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1097               reg_last->uses_length++;
1098             });
1099           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i,
1100             {
1101               struct deps_reg *reg_last = &deps->reg_last[i];
1102               add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1103               add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1104               reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1105               reg_last->clobbers_length++;
1106             });
1107           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
1108             {
1109               struct deps_reg *reg_last = &deps->reg_last[i];
1110               add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1111               add_dependence_list (insn, reg_last->clobbers, REG_DEP_OUTPUT);
1112               add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1113               reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1114             });
1115         }
1116       else
1117         {
1118           EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i,
1119             {
1120               struct deps_reg *reg_last = &deps->reg_last[i];
1121               add_dependence_list (insn, reg_last->sets, 0);
1122               add_dependence_list (insn, reg_last->clobbers, 0);
1123               reg_last->uses_length++;
1124               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1125             });
1126           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i,
1127             {
1128               struct deps_reg *reg_last = &deps->reg_last[i];
1129               if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
1130                   || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
1131                 {
1132                   add_dependence_list_and_free (insn, &reg_last->sets,
1133                                                 REG_DEP_OUTPUT);
1134                   add_dependence_list_and_free (insn, &reg_last->uses,
1135                                                 REG_DEP_ANTI);
1136                   add_dependence_list_and_free (insn, &reg_last->clobbers,
1137                                                 REG_DEP_OUTPUT);
1138                   reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1139                   reg_last->clobbers_length = 0;
1140                   reg_last->uses_length = 0;
1141                 }
1142               else
1143                 {
1144                   add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1145                   add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1146                 }
1147               reg_last->clobbers_length++;
1148               reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1149             });
1150           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
1151             {
1152               struct deps_reg *reg_last = &deps->reg_last[i];
1153               add_dependence_list_and_free (insn, &reg_last->sets,
1154                                             REG_DEP_OUTPUT);
1155               add_dependence_list_and_free (insn, &reg_last->clobbers,
1156                                             REG_DEP_OUTPUT);
1157               add_dependence_list_and_free (insn, &reg_last->uses,
1158                                             REG_DEP_ANTI);
1159               reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1160               reg_last->uses_length = 0;
1161               reg_last->clobbers_length = 0;
1162             });
1163         }
1164
1165       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
1166       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
1167       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
1168     }
1169   CLEAR_REG_SET (reg_pending_uses);
1170   CLEAR_REG_SET (reg_pending_clobbers);
1171   CLEAR_REG_SET (reg_pending_sets);
1172
1173   /* If we are currently in a libcall scheduling group, then mark the
1174      current insn as being in a scheduling group and that it can not
1175      be moved into a different basic block.  */
1176
1177   if (deps->libcall_block_tail_insn)
1178     {
1179       set_sched_group_p (insn);
1180       CANT_MOVE (insn) = 1;
1181     }
1182
1183   /* If a post-call group is still open, see if it should remain so.
1184      This insn must be a simple move of a hard reg to a pseudo or
1185      vice-versa.
1186
1187      We must avoid moving these insns for correctness on
1188      SMALL_REGISTER_CLASS machines, and for special registers like
1189      PIC_OFFSET_TABLE_REGNUM.  For simplicity, extend this to all
1190      hard regs for all targets.  */
1191
1192   if (deps->in_post_call_group_p)
1193     {
1194       rtx tmp, set = single_set (insn);
1195       int src_regno, dest_regno;
1196
1197       if (set == NULL)
1198         goto end_call_group;
1199
1200       tmp = SET_DEST (set);
1201       if (GET_CODE (tmp) == SUBREG)
1202         tmp = SUBREG_REG (tmp);
1203       if (GET_CODE (tmp) == REG)
1204         dest_regno = REGNO (tmp);
1205       else
1206         goto end_call_group;
1207
1208       tmp = SET_SRC (set);
1209       if (GET_CODE (tmp) == SUBREG)
1210         tmp = SUBREG_REG (tmp);
1211       if (GET_CODE (tmp) == REG)
1212         src_regno = REGNO (tmp);
1213       else
1214         goto end_call_group;
1215
1216       if (src_regno < FIRST_PSEUDO_REGISTER
1217           || dest_regno < FIRST_PSEUDO_REGISTER)
1218         {
1219           set_sched_group_p (insn);
1220           CANT_MOVE (insn) = 1;
1221         }
1222       else
1223         {
1224         end_call_group:
1225           deps->in_post_call_group_p = false;
1226         }
1227     }
1228 }
1229
1230 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1231    for every dependency.  */
1232
1233 void
1234 sched_analyze (deps, head, tail)
1235      struct deps *deps;
1236      rtx head, tail;
1237 {
1238   rtx insn;
1239   rtx loop_notes = 0;
1240
1241   if (current_sched_info->use_cselib)
1242     cselib_init ();
1243
1244   for (insn = head;; insn = NEXT_INSN (insn))
1245     {
1246       rtx link, end_seq, r0, set, note;
1247
1248       if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
1249         {
1250           /* Clear out the stale LOG_LINKS from flow.  */
1251           free_INSN_LIST_list (&LOG_LINKS (insn));
1252
1253           /* Clear out stale SCHED_GROUP_P.  */
1254           SCHED_GROUP_P (insn) = 0;
1255
1256           /* Make each JUMP_INSN a scheduling barrier for memory
1257              references.  */
1258           if (GET_CODE (insn) == JUMP_INSN)
1259             {
1260               /* Keep the list a reasonable size.  */
1261               if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
1262                 flush_pending_lists (deps, insn, true, true);
1263               else
1264                 deps->last_pending_memory_flush
1265                   = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
1266             }
1267           sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1268           loop_notes = 0;
1269         }
1270       else if (GET_CODE (insn) == CALL_INSN)
1271         {
1272           int i;
1273
1274           CANT_MOVE (insn) = 1;
1275
1276           /* Clear out the stale LOG_LINKS from flow.  */
1277           free_INSN_LIST_list (&LOG_LINKS (insn));
1278
1279           if (find_reg_note (insn, REG_SETJMP, NULL))
1280             {
1281               /* This is setjmp.  Assume that all registers, not just
1282                  hard registers, may be clobbered by this call.  */
1283               reg_pending_barrier = true;
1284             }
1285           else
1286             {
1287               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1288                 /* A call may read and modify global register variables.  */
1289                 if (global_regs[i])
1290                   {
1291                     SET_REGNO_REG_SET (reg_pending_sets, i);
1292                     SET_REGNO_REG_SET (reg_pending_uses, i);
1293                   }
1294                 /* Other call-clobbered hard regs may be clobbered.  */
1295                 else if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1296                   SET_REGNO_REG_SET (reg_pending_clobbers, i);
1297                 /* We don't know what set of fixed registers might be used
1298                    by the function, but it is certain that the stack pointer
1299                    is among them, but be conservative.  */
1300                 else if (fixed_regs[i])
1301                   SET_REGNO_REG_SET (reg_pending_uses, i);
1302                 /* The frame pointer is normally not used by the function
1303                    itself, but by the debugger.  */
1304                 /* ??? MIPS o32 is an exception.  It uses the frame pointer
1305                    in the macro expansion of jal but does not represent this
1306                    fact in the call_insn rtl.  */
1307                 else if (i == FRAME_POINTER_REGNUM
1308                          || (i == HARD_FRAME_POINTER_REGNUM
1309                              && (! reload_completed || frame_pointer_needed)))
1310                   SET_REGNO_REG_SET (reg_pending_uses, i);
1311             }
1312
1313           /* For each insn which shouldn't cross a call, add a dependence
1314              between that insn and this call insn.  */
1315           add_dependence_list_and_free (insn, &deps->sched_before_next_call,
1316                                         REG_DEP_ANTI);
1317
1318           sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1319           loop_notes = 0;
1320
1321           /* In the absence of interprocedural alias analysis, we must flush
1322              all pending reads and writes, and start new dependencies starting
1323              from here.  But only flush writes for constant calls (which may
1324              be passed a pointer to something we haven't written yet).  */
1325           flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn));
1326
1327           /* Remember the last function call for limiting lifetimes.  */
1328           free_INSN_LIST_list (&deps->last_function_call);
1329           deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
1330
1331           /* Before reload, begin a post-call group, so as to keep the
1332              lifetimes of hard registers correct.  */
1333           if (! reload_completed)
1334             deps->in_post_call_group_p = true;
1335         }
1336
1337       /* See comments on reemit_notes as to why we do this.
1338          ??? Actually, the reemit_notes just say what is done, not why.  */
1339
1340       else if (GET_CODE (insn) == NOTE
1341                && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_BEG
1342                    || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END))
1343         {
1344           loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, NOTE_RANGE_INFO (insn),
1345                                         loop_notes);
1346           loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1347                                         GEN_INT (NOTE_LINE_NUMBER (insn)),
1348                                         loop_notes);
1349         }
1350       else if (GET_CODE (insn) == NOTE
1351                && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
1352                    || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
1353                    || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1354                    || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END))
1355         {
1356           rtx rtx_region;
1357
1358           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1359               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
1360             rtx_region = GEN_INT (NOTE_EH_HANDLER (insn));
1361           else
1362             rtx_region = GEN_INT (0);
1363
1364           loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1365                                         rtx_region,
1366                                         loop_notes);
1367           loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1368                                         GEN_INT (NOTE_LINE_NUMBER (insn)),
1369                                         loop_notes);
1370           CONST_OR_PURE_CALL_P (loop_notes) = CONST_OR_PURE_CALL_P (insn);
1371         }
1372
1373       if (current_sched_info->use_cselib)
1374         cselib_process_insn (insn);
1375
1376       /* Now that we have completed handling INSN, check and see if it is
1377          a CLOBBER beginning a libcall block.   If it is, record the
1378          end of the libcall sequence.
1379
1380          We want to schedule libcall blocks as a unit before reload.  While
1381          this restricts scheduling, it preserves the meaning of a libcall
1382          block.
1383
1384          As a side effect, we may get better code due to decreased register
1385          pressure as well as less chance of a foreign insn appearing in
1386          a libcall block.  */
1387       if (!reload_completed
1388           /* Note we may have nested libcall sequences.  We only care about
1389              the outermost libcall sequence.  */
1390           && deps->libcall_block_tail_insn == 0
1391           /* The sequence must start with a clobber of a register.  */
1392           && GET_CODE (insn) == INSN
1393           && GET_CODE (PATTERN (insn)) == CLOBBER
1394           && (r0 = XEXP (PATTERN (insn), 0), GET_CODE (r0) == REG)
1395           && GET_CODE (XEXP (PATTERN (insn), 0)) == REG
1396           /* The CLOBBER must also have a REG_LIBCALL note attached.  */
1397           && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
1398           && (end_seq = XEXP (link, 0)) != 0
1399           /* The insn referenced by the REG_LIBCALL note must be a
1400              simple nop copy with the same destination as the register
1401              mentioned in the clobber.  */
1402           && (set = single_set (end_seq)) != 0
1403           && SET_DEST (set) == r0 && SET_SRC (set) == r0
1404           /* And finally the insn referenced by the REG_LIBCALL must
1405              also contain a REG_EQUAL note and a REG_RETVAL note.  */
1406           && find_reg_note (end_seq, REG_EQUAL, NULL_RTX) != 0
1407           && find_reg_note (end_seq, REG_RETVAL, NULL_RTX) != 0)
1408         deps->libcall_block_tail_insn = XEXP (link, 0);
1409
1410       /* If we have reached the end of a libcall block, then close the
1411          block.  */
1412       if (deps->libcall_block_tail_insn == insn)
1413         deps->libcall_block_tail_insn = 0;
1414
1415       if (insn == tail)
1416         {
1417           if (current_sched_info->use_cselib)
1418             cselib_finish ();
1419           return;
1420         }
1421     }
1422   abort ();
1423 }
1424 \f
1425 /* Examine insns in the range [ HEAD, TAIL ] and Use the backward
1426    dependences from LOG_LINKS to build forward dependences in
1427    INSN_DEPEND.  */
1428
1429 void
1430 compute_forward_dependences (head, tail)
1431      rtx head, tail;
1432 {
1433   rtx insn, link;
1434   rtx next_tail;
1435   enum reg_note dep_type;
1436
1437   next_tail = NEXT_INSN (tail);
1438   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1439     {
1440       if (! INSN_P (insn))
1441         continue;
1442
1443       insn = group_leader (insn);
1444
1445       for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
1446         {
1447           rtx x = group_leader (XEXP (link, 0));
1448           rtx new_link;
1449
1450           if (x != XEXP (link, 0))
1451             continue;
1452
1453 #ifdef ENABLE_CHECKING
1454           /* If add_dependence is working properly there should never
1455              be notes, deleted insns or duplicates in the backward
1456              links.  Thus we need not check for them here.
1457
1458              However, if we have enabled checking we might as well go
1459              ahead and verify that add_dependence worked properly.  */
1460           if (GET_CODE (x) == NOTE
1461               || INSN_DELETED_P (x)
1462               || (forward_dependency_cache != NULL
1463                   && TEST_BIT (forward_dependency_cache[INSN_LUID (x)],
1464                                INSN_LUID (insn)))
1465               || (forward_dependency_cache == NULL
1466                   && find_insn_list (insn, INSN_DEPEND (x))))
1467             abort ();
1468           if (forward_dependency_cache != NULL)
1469             SET_BIT (forward_dependency_cache[INSN_LUID (x)],
1470                      INSN_LUID (insn));
1471 #endif
1472
1473           new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
1474
1475           dep_type = REG_NOTE_KIND (link);
1476           PUT_REG_NOTE_KIND (new_link, dep_type);
1477
1478           INSN_DEPEND (x) = new_link;
1479           INSN_DEP_COUNT (insn) += 1;
1480         }
1481     }
1482 }
1483 \f
1484 /* Initialize variables for region data dependence analysis.
1485    n_bbs is the number of region blocks.  */
1486
1487 void
1488 init_deps (deps)
1489      struct deps *deps;
1490 {
1491   int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
1492
1493   deps->max_reg = max_reg;
1494   deps->reg_last = (struct deps_reg *)
1495     xcalloc (max_reg, sizeof (struct deps_reg));
1496   INIT_REG_SET (&deps->reg_last_in_use);
1497
1498   deps->pending_read_insns = 0;
1499   deps->pending_read_mems = 0;
1500   deps->pending_write_insns = 0;
1501   deps->pending_write_mems = 0;
1502   deps->pending_lists_length = 0;
1503   deps->pending_flush_length = 0;
1504   deps->last_pending_memory_flush = 0;
1505   deps->last_function_call = 0;
1506   deps->sched_before_next_call = 0;
1507   deps->in_post_call_group_p = false;
1508   deps->libcall_block_tail_insn = 0;
1509 }
1510
1511 /* Free insn lists found in DEPS.  */
1512
1513 void
1514 free_deps (deps)
1515      struct deps *deps;
1516 {
1517   int i;
1518
1519   free_INSN_LIST_list (&deps->pending_read_insns);
1520   free_EXPR_LIST_list (&deps->pending_read_mems);
1521   free_INSN_LIST_list (&deps->pending_write_insns);
1522   free_EXPR_LIST_list (&deps->pending_write_mems);
1523   free_INSN_LIST_list (&deps->last_pending_memory_flush);
1524
1525   /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
1526      times.  For a test case with 42000 regs and 8000 small basic blocks,
1527      this loop accounted for nearly 60% (84 sec) of the total -O2 runtime.  */
1528   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i,
1529     {
1530       struct deps_reg *reg_last = &deps->reg_last[i];
1531       free_INSN_LIST_list (&reg_last->uses);
1532       free_INSN_LIST_list (&reg_last->sets);
1533       free_INSN_LIST_list (&reg_last->clobbers);
1534     });
1535   CLEAR_REG_SET (&deps->reg_last_in_use);
1536
1537   free (deps->reg_last);
1538 }
1539
1540 /* If it is profitable to use them, initialize caches for tracking
1541    dependency informatino.  LUID is the number of insns to be scheduled,
1542    it is used in the estimate of profitability.  */
1543
1544 void
1545 init_dependency_caches (luid)
1546      int luid;
1547 {
1548   /* ?!? We could save some memory by computing a per-region luid mapping
1549      which could reduce both the number of vectors in the cache and the size
1550      of each vector.  Instead we just avoid the cache entirely unless the
1551      average number of instructions in a basic block is very high.  See
1552      the comment before the declaration of true_dependency_cache for
1553      what we consider "very high".  */
1554   if (luid / n_basic_blocks > 100 * 5)
1555     {
1556       true_dependency_cache = sbitmap_vector_alloc (luid, luid);
1557       sbitmap_vector_zero (true_dependency_cache, luid);
1558       anti_dependency_cache = sbitmap_vector_alloc (luid, luid);
1559       sbitmap_vector_zero (anti_dependency_cache, luid);
1560       output_dependency_cache = sbitmap_vector_alloc (luid, luid);
1561       sbitmap_vector_zero (output_dependency_cache, luid);
1562 #ifdef ENABLE_CHECKING
1563       forward_dependency_cache = sbitmap_vector_alloc (luid, luid);
1564       sbitmap_vector_zero (forward_dependency_cache, luid);
1565 #endif
1566     }
1567 }
1568
1569 /* Free the caches allocated in init_dependency_caches.  */
1570
1571 void
1572 free_dependency_caches ()
1573 {
1574   if (true_dependency_cache)
1575     {
1576       sbitmap_vector_free (true_dependency_cache);
1577       true_dependency_cache = NULL;
1578       sbitmap_vector_free (anti_dependency_cache);
1579       anti_dependency_cache = NULL;
1580       sbitmap_vector_free (output_dependency_cache);
1581       output_dependency_cache = NULL;
1582 #ifdef ENABLE_CHECKING
1583       sbitmap_vector_free (forward_dependency_cache);
1584       forward_dependency_cache = NULL;
1585 #endif
1586     }
1587 }
1588
1589 /* Initialize some global variables needed by the dependency analysis
1590    code.  */
1591
1592 void
1593 init_deps_global ()
1594 {
1595   reg_pending_sets = INITIALIZE_REG_SET (reg_pending_sets_head);
1596   reg_pending_clobbers = INITIALIZE_REG_SET (reg_pending_clobbers_head);
1597   reg_pending_uses = INITIALIZE_REG_SET (reg_pending_uses_head);
1598   reg_pending_barrier = false;
1599 }
1600
1601 /* Free everything used by the dependency analysis code.  */
1602
1603 void
1604 finish_deps_global ()
1605 {
1606   FREE_REG_SET (reg_pending_sets);
1607   FREE_REG_SET (reg_pending_clobbers);
1608   FREE_REG_SET (reg_pending_uses);
1609 }