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