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