gcc/sched-deps.c

   1 /* Instruction scheduling pass.  This file computes dependencies between
   2    instructions.
   3    Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   4    1999, 2000, 2001, 2002 Free Software Foundation, Inc.
   5    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
   6    and currently maintained by, Jim Wilson (wilson@cygnus.com)
   7
   8 This file is part of GCC.
   9
  10 GCC is free software; you can redistribute it and/or modify it under
  11 the terms of the GNU General Public License as published by the Free
  12 Software Foundation; either version 2, or (at your option) any later
  13 version.
  14
  15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  17 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  18 for more details.
  19
  20 You should have received a copy of the GNU General Public License
  21 along with GCC; see the file COPYING.  If not, write to the Free
  22 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  23 02111-1307, USA.  */
  24 \f
  25 #include "config.h"
  26 #include "system.h"
  27 #include "toplev.h"
  28 #include "rtl.h"
  29 #include "tm_p.h"
  30 #include "hard-reg-set.h"
  31 #include "basic-block.h"
  32 #include "regs.h"
  33 #include "function.h"
  34 #include "flags.h"
  35 #include "insn-config.h"
  36 #include "insn-attr.h"
  37 #include "except.h"
  38 #include "toplev.h"
  39 #include "recog.h"
  40 #include "sched-int.h"
  41 #include "params.h"
  42 #include "cselib.h"
  43
  44 extern char *reg_known_equiv_p;
  45 extern rtx *reg_known_value;
  46
  47 static regset_head reg_pending_sets_head;
  48 static regset_head reg_pending_clobbers_head;
  49 static regset_head reg_pending_uses_head;
  50
  51 static regset reg_pending_sets;
  52 static regset reg_pending_clobbers;
  53 static regset reg_pending_uses;
  54 static bool reg_pending_barrier;
  55
  56 /* To speed up the test for duplicate dependency links we keep a
  57    record of dependencies created by add_dependence when the average
  58    number of instructions in a basic block is very large.
  59
  60    Studies have shown that there is typically around 5 instructions between
  61    branches for typical C code.  So we can make a guess that the average
  62    basic block is approximately 5 instructions long; we will choose 100X
  63    the average size as a very large basic block.
  64
  65    Each insn has associated bitmaps for its dependencies.  Each bitmap
  66    has enough entries to represent a dependency on any other insn in
  67    the insn chain.  All bitmap for true dependencies cache is
  68    allocated then the rest two ones are also allocated.  */
  69 static sbitmap *true_dependency_cache;
  70 static sbitmap *anti_dependency_cache;
  71 static sbitmap *output_dependency_cache;
  72
  73 /* To speed up checking consistency of formed forward insn
  74    dependencies we use the following cache.  Another possible solution
  75    could be switching off checking duplication of insns in forward
  76    dependencies.  */
  77 #ifdef ENABLE_CHECKING
  78 static sbitmap *forward_dependency_cache;
  79 #endif
  80
  81 static int deps_may_trap_p PARAMS ((rtx));
  82 static void add_dependence_list PARAMS ((rtx, rtx, enum reg_note));
  83 static void add_dependence_list_and_free PARAMS ((rtx, rtx *, enum reg_note));
  84 static void remove_dependence PARAMS ((rtx, rtx));
  85 static void set_sched_group_p PARAMS ((rtx));
  86
  87 static void flush_pending_lists PARAMS ((struct deps *, rtx, int, int));
  88 static void sched_analyze_1 PARAMS ((struct deps *, rtx, rtx));
  89 static void sched_analyze_2 PARAMS ((struct deps *, rtx, rtx));
  90 static void sched_analyze_insn PARAMS ((struct deps *, rtx, rtx, rtx));
  91 static rtx group_leader PARAMS ((rtx));
  92
  93 static rtx get_condition PARAMS ((rtx));
  94 static int conditions_mutex_p PARAMS ((rtx, rtx));
  95 \f
  96 /* Return nonzero if a load of the memory reference MEM can cause a trap.  */
  97
  98 static int
  99 deps_may_trap_p (mem)
 100      rtx mem;
 101 {
 102   rtx addr = XEXP (mem, 0);
 103
 104   if (REG_P (addr)
 105       && REGNO (addr) >= FIRST_PSEUDO_REGISTER
 106       && reg_known_value[REGNO (addr)])
 107     addr = reg_known_value[REGNO (addr)];
 108   return rtx_addr_can_trap_p (addr);
 109 }
 110 \f
 111 /* Return the INSN_LIST containing INSN in LIST, or NULL
 112    if LIST does not contain INSN.  */
 113
 114 rtx
 115 find_insn_list (insn, list)
 116      rtx insn;
 117      rtx list;
 118 {
 119   while (list)
 120     {
 121       if (XEXP (list, 0) == insn)
 122         return list;
 123       list = XEXP (list, 1);
 124     }
 125   return 0;
 126 }
 127 \f
 128 /* Find the condition under which INSN is executed.  */
 129
 130 static rtx
 131 get_condition (insn)
 132      rtx insn;
 133 {
 134   rtx pat = PATTERN (insn);
 135   rtx cond;
 136
 137   if (pat == 0)
 138     return 0;
 139   if (GET_CODE (pat) == COND_EXEC)
 140     return COND_EXEC_TEST (pat);
 141   if (GET_CODE (insn) != JUMP_INSN)
 142     return 0;
 143   if (GET_CODE (pat) != SET || SET_SRC (pat) != pc_rtx)
 144     return 0;
 145   if (GET_CODE (SET_DEST (pat)) != IF_THEN_ELSE)
 146     return 0;
 147   pat = SET_DEST (pat);
 148   cond = XEXP (pat, 0);
 149   if (GET_CODE (XEXP (cond, 1)) == LABEL_REF
 150       && XEXP (cond, 2) == pc_rtx)
 151     return cond;
 152   else if (GET_CODE (XEXP (cond, 2)) == LABEL_REF
 153            && XEXP (cond, 1) == pc_rtx)
 154     return gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)), GET_MODE (cond),
 155                            XEXP (cond, 0), XEXP (cond, 1));
 156   else
 157     return 0;
 158 }
 159
 160 /* Return nonzero if conditions COND1 and COND2 can never be both true.  */
 161
 162 static int
 163 conditions_mutex_p (cond1, cond2)
 164      rtx cond1, cond2;
 165 {
 166   if (GET_RTX_CLASS (GET_CODE (cond1)) == '<'
 167       && GET_RTX_CLASS (GET_CODE (cond2)) == '<'
 168       && GET_CODE (cond1) == reverse_condition (GET_CODE (cond2))
 169       && XEXP (cond1, 0) == XEXP (cond2, 0)
 170       && XEXP (cond1, 1) == XEXP (cond2, 1))
 171     return 1;
 172   return 0;
 173 }
 174 \f
 175 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
 176    LOG_LINKS of INSN, if not already there.  DEP_TYPE indicates the type
 177    of dependence that this link represents.  */
 178
 179 void
 180 add_dependence (insn, elem, dep_type)
 181      rtx insn;
 182      rtx elem;
 183      enum reg_note dep_type;
 184 {
 185   rtx link, next;
 186   int present_p;
 187   rtx cond1, cond2;
 188
 189   /* Don't depend an insn on itself.  */
 190   if (insn == elem)
 191     return;
 192
 193   /* We can get a dependency on deleted insns due to optimizations in
 194      the register allocation and reloading or due to splitting.  Any
 195      such dependency is useless and can be ignored.  */
 196   if (GET_CODE (elem) == NOTE)
 197     return;
 198
 199   /* flow.c doesn't handle conditional lifetimes entirely correctly;
 200      calls mess up the conditional lifetimes.  */
 201   /* ??? add_dependence is the wrong place to be eliding dependencies,
 202      as that forgets that the condition expressions themselves may
 203      be dependent.  */
 204   if (GET_CODE (insn) != CALL_INSN && GET_CODE (elem) != CALL_INSN)
 205     {
 206       cond1 = get_condition (insn);
 207       cond2 = get_condition (elem);
 208       if (cond1 && cond2
 209           && conditions_mutex_p (cond1, cond2)
 210           /* Make sure first instruction doesn't affect condition of second
 211              instruction if switched.  */
 212           && !modified_in_p (cond1, elem)
 213           /* Make sure second instruction doesn't affect condition of first
 214              instruction if switched.  */
 215           && !modified_in_p (cond2, insn))
 216         return;
 217     }
 218
 219   /* If elem is part of a sequence that must be scheduled together, then
 220      make the dependence point to the last insn of the sequence.
 221      When HAVE_cc0, it is possible for NOTEs to exist between users and
 222      setters of the condition codes, so we must skip past notes here.
 223      Otherwise, NOTEs are impossible here.  */
 224   next = next_nonnote_insn (elem);
 225   if (next && SCHED_GROUP_P (next)
 226       && GET_CODE (next) != CODE_LABEL)
 227     {
 228       /* Notes will never intervene here though, so don't bother checking
 229          for them.  */
 230       /* Hah!  Wrong.  */
 231       /* We must reject CODE_LABELs, so that we don't get confused by one
 232          that has LABEL_PRESERVE_P set, which is represented by the same
 233          bit in the rtl as SCHED_GROUP_P.  A CODE_LABEL can never be
 234          SCHED_GROUP_P.  */
 235
 236       rtx nnext;
 237       while ((nnext = next_nonnote_insn (next)) != NULL
 238              && SCHED_GROUP_P (nnext)
 239              && GET_CODE (nnext) != CODE_LABEL)
 240         next = nnext;
 241
 242       /* Again, don't depend an insn on itself.  */
 243       if (insn == next)
 244         return;
 245
 246       /* Make the dependence to NEXT, the last insn of the group, instead
 247          of the original ELEM.  */
 248       elem = next;
 249     }
 250
 251   present_p = 1;
 252 #ifdef INSN_SCHEDULING
 253   /* ??? No good way to tell from here whether we're doing interblock
 254      scheduling.  Possibly add another callback.  */
 255 #if 0
 256   /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
 257      No need for interblock dependences with calls, since
 258      calls are not moved between blocks.   Note: the edge where
 259      elem is a CALL is still required.  */
 260   if (GET_CODE (insn) == CALL_INSN
 261       && (INSN_BB (elem) != INSN_BB (insn)))
 262     return;
 263 #endif
 264
 265   /* If we already have a dependency for ELEM, then we do not need to
 266      do anything.  Avoiding the list walk below can cut compile times
 267      dramatically for some code.  */
 268   if (true_dependency_cache != NULL)
 269     {
 270       enum reg_note present_dep_type = 0;
 271
 272       if (anti_dependency_cache == NULL || output_dependency_cache == NULL)
 273         abort ();
 274       if (TEST_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)))
 275         /* Do nothing (present_set_type is already 0).  */
 276         ;
 277       else if (TEST_BIT (anti_dependency_cache[INSN_LUID (insn)],
 278                          INSN_LUID (elem)))
 279         present_dep_type = REG_DEP_ANTI;
 280       else if (TEST_BIT (output_dependency_cache[INSN_LUID (insn)],
 281                          INSN_LUID (elem)))
 282         present_dep_type = REG_DEP_OUTPUT;
 283       else
 284         present_p = 0;
 285       if (present_p && (int) dep_type >= (int) present_dep_type)
 286         return;
 287     }
 288 #endif
 289
 290   /* Check that we don't already have this dependence.  */
 291   if (present_p)
 292     for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
 293       if (XEXP (link, 0) == elem)
 294         {
 295 #ifdef INSN_SCHEDULING
 296           /* Clear corresponding cache entry because type of the link
 297              may be changed.  */
 298           if (true_dependency_cache != NULL)
 299             {
 300               if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
 301                 RESET_BIT (anti_dependency_cache[INSN_LUID (insn)],
 302                            INSN_LUID (elem));
 303               else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT
 304                        && output_dependency_cache)
 305                 RESET_BIT (output_dependency_cache[INSN_LUID (insn)],
 306                            INSN_LUID (elem));
 307               else
 308                 abort ();
 309             }
 310 #endif
 311
 312           /* If this is a more restrictive type of dependence than the existing
 313              one, then change the existing dependence to this type.  */
 314           if ((int) dep_type < (int) REG_NOTE_KIND (link))
 315             PUT_REG_NOTE_KIND (link, dep_type);
 316
 317 #ifdef INSN_SCHEDULING
 318           /* If we are adding a dependency to INSN's LOG_LINKs, then
 319              note that in the bitmap caches of dependency information.  */
 320           if (true_dependency_cache != NULL)
 321             {
 322               if ((int) REG_NOTE_KIND (link) == 0)
 323                 SET_BIT (true_dependency_cache[INSN_LUID (insn)],
 324                          INSN_LUID (elem));
 325               else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
 326                 SET_BIT (anti_dependency_cache[INSN_LUID (insn)],
 327                          INSN_LUID (elem));
 328               else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
 329                 SET_BIT (output_dependency_cache[INSN_LUID (insn)],
 330                          INSN_LUID (elem));
 331             }
 332 #endif
 333           return;
 334       }
 335   /* Might want to check one level of transitivity to save conses.  */
 336
 337   link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
 338   LOG_LINKS (insn) = link;
 339
 340   /* Insn dependency, not data dependency.  */
 341   PUT_REG_NOTE_KIND (link, dep_type);
 342
 343 #ifdef INSN_SCHEDULING
 344   /* If we are adding a dependency to INSN's LOG_LINKs, then note that
 345      in the bitmap caches of dependency information.  */
 346   if (true_dependency_cache != NULL)
 347     {
 348       if ((int) dep_type == 0)
 349         SET_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
 350       else if (dep_type == REG_DEP_ANTI)
 351         SET_BIT (anti_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
 352       else if (dep_type == REG_DEP_OUTPUT)
 353         SET_BIT (output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
 354     }
 355 #endif
 356 }
 357
 358 /* A convenience wrapper to operate on an entire list.  */
 359
 360 static void
 361 add_dependence_list (insn, list, dep_type)
 362      rtx insn, list;
 363      enum reg_note dep_type;
 364 {
 365   for (; list; list = XEXP (list, 1))
 366     add_dependence (insn, XEXP (list, 0), dep_type);
 367 }
 368
 369 /* Similar, but free *LISTP at the same time.  */
 370
 371 static void
 372 add_dependence_list_and_free (insn, listp, dep_type)
 373      rtx insn;
 374      rtx *listp;
 375      enum reg_note dep_type;
 376 {
 377   rtx list, next;
 378   for (list = *listp, *listp = NULL; list ; list = next)
 379     {
 380       next = XEXP (list, 1);
 381       add_dependence (insn, XEXP (list, 0), dep_type);
 382       free_INSN_LIST_node (list);
 383     }
 384 }
 385
 386 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
 387    of INSN.  Abort if not found.  */
 388
 389 static void
 390 remove_dependence (insn, elem)
 391      rtx insn;
 392      rtx elem;
 393 {
 394   rtx prev, link, next;
 395   int found = 0;
 396
 397   for (prev = 0, link = LOG_LINKS (insn); link; link = next)
 398     {
 399       next = XEXP (link, 1);
 400       if (XEXP (link, 0) == elem)
 401         {
 402           if (prev)
 403             XEXP (prev, 1) = next;
 404           else
 405             LOG_LINKS (insn) = next;
 406
 407 #ifdef INSN_SCHEDULING
 408           /* If we are removing a dependency from the LOG_LINKS list,
 409              make sure to remove it from the cache too.  */
 410           if (true_dependency_cache != NULL)
 411             {
 412               if (REG_NOTE_KIND (link) == 0)
 413                 RESET_BIT (true_dependency_cache[INSN_LUID (insn)],
 414                            INSN_LUID (elem));
 415               else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
 416                 RESET_BIT (anti_dependency_cache[INSN_LUID (insn)],
 417                            INSN_LUID (elem));
 418               else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
 419                 RESET_BIT (output_dependency_cache[INSN_LUID (insn)],
 420                            INSN_LUID (elem));
 421             }
 422 #endif
 423
 424           free_INSN_LIST_node (link);
 425
 426           found = 1;
 427         }
 428       else
 429         prev = link;
 430     }
 431
 432   if (!found)
 433     abort ();
 434   return;
 435 }
 436
 437 /* Return an insn which represents a SCHED_GROUP, which is
 438    the last insn in the group.  */
 439
 440 static rtx
 441 group_leader (insn)
 442      rtx insn;
 443 {
 444   rtx prev;
 445
 446   do
 447     {
 448       prev = insn;
 449       insn = next_nonnote_insn (insn);
 450     }
 451   while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL));
 452
 453   return prev;
 454 }
 455
 456 /* Set SCHED_GROUP_P and care for the rest of the bookkeeping that
 457    goes along with that.  */
 458
 459 static void
 460 set_sched_group_p (insn)
 461      rtx insn;
 462 {
 463   rtx link, prev;
 464
 465   SCHED_GROUP_P (insn) = 1;
 466
 467   /* There may be a note before this insn now, but all notes will
 468      be removed before we actually try to schedule the insns, so
 469      it won't cause a problem later.  We must avoid it here though.  */
 470   prev = prev_nonnote_insn (insn);
 471
 472   /* Make a copy of all dependencies on the immediately previous insn,
 473      and add to this insn.  This is so that all the dependencies will
 474      apply to the group.  Remove an explicit dependence on this insn
 475      as SCHED_GROUP_P now represents it.  */
 476
 477   if (find_insn_list (prev, LOG_LINKS (insn)))
 478     remove_dependence (insn, prev);
 479
 480   for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
 481     add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
 482 }
 483 \f
 484 /* Process an insn's memory dependencies.  There are four kinds of
 485    dependencies:
 486
 487    (0) read dependence: read follows read
 488    (1) true dependence: read follows write
 489    (2) anti dependence: write follows read
 490    (3) output dependence: write follows write
 491
 492    We are careful to build only dependencies which actually exist, and
 493    use transitivity to avoid building too many links.  */
 494
 495 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
 496    The MEM is a memory reference contained within INSN, which we are saving
 497    so that we can do memory aliasing on it.  */
 498
 499 void
 500 add_insn_mem_dependence (deps, insn_list, mem_list, insn, mem)
 501      struct deps *deps;
 502      rtx *insn_list, *mem_list, insn, mem;
 503 {
 504   rtx link;
 505
 506   link = alloc_INSN_LIST (insn, *insn_list);
 507   *insn_list = link;
 508
 509   if (current_sched_info->use_cselib)
 510     {
 511       mem = shallow_copy_rtx (mem);
 512       XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0));
 513     }
 514   link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
 515   *mem_list = link;
 516
 517   deps->pending_lists_length++;
 518 }
 519
 520 /* Make a dependency between every memory reference on the pending lists
 521    and INSN, thus flushing the pending lists.  FOR_READ is true if emitting
 522    dependencies for a read operation, similarly with FOR_WRITE.  */
 523
 524 static void
 525 flush_pending_lists (deps, insn, for_read, for_write)
 526      struct deps *deps;
 527      rtx insn;
 528      int for_read, for_write;
 529 {
 530   if (for_write)
 531     {
 532       add_dependence_list_and_free (insn, &deps->pending_read_insns,
 533                                     REG_DEP_ANTI);
 534       free_EXPR_LIST_list (&deps->pending_read_mems);
 535     }
 536
 537   add_dependence_list_and_free (insn, &deps->pending_write_insns,
 538                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
 539   free_EXPR_LIST_list (&deps->pending_write_mems);
 540   deps->pending_lists_length = 0;
 541
 542   add_dependence_list_and_free (insn, &deps->last_pending_memory_flush,
 543                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
 544   deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
 545   deps->pending_flush_length = 1;
 546 }
 547 \f
 548 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
 549    rtx, X, creating all dependencies generated by the write to the
 550    destination of X, and reads of everything mentioned.  */
 551
 552 static void
 553 sched_analyze_1 (deps, x, insn)
 554      struct deps *deps;
 555      rtx x;
 556      rtx insn;
 557 {
 558   int regno;
 559   rtx dest = XEXP (x, 0);
 560   enum rtx_code code = GET_CODE (x);
 561
 562   if (dest == 0)
 563     return;
 564
 565   if (GET_CODE (dest) == PARALLEL)
 566     {
 567       int i;
 568
 569       for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
 570         if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
 571           sched_analyze_1 (deps,
 572                            gen_rtx_CLOBBER (VOIDmode,
 573                                             XEXP (XVECEXP (dest, 0, i), 0)),
 574                            insn);
 575
 576       if (GET_CODE (x) == SET)
 577         sched_analyze_2 (deps, SET_SRC (x), insn);
 578       return;
 579     }
 580
 581   while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
 582          || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
 583     {
 584       if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
 585         {
 586           /* The second and third arguments are values read by this insn.  */
 587           sched_analyze_2 (deps, XEXP (dest, 1), insn);
 588           sched_analyze_2 (deps, XEXP (dest, 2), insn);
 589         }
 590       dest = XEXP (dest, 0);
 591     }
 592
 593   if (GET_CODE (dest) == REG)
 594     {
 595       regno = REGNO (dest);
 596
 597       /* A hard reg in a wide mode may really be multiple registers.
 598          If so, mark all of them just like the first.  */
 599       if (regno < FIRST_PSEUDO_REGISTER)
 600         {
 601           int i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
 602           if (code == SET)
 603             {
 604               while (--i >= 0)
 605                 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
 606             }
 607           else
 608             {
 609               while (--i >= 0)
 610                 SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
 611             }
 612         }
 613       /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
 614          it does not reload.  Ignore these as they have served their
 615          purpose already.  */
 616       else if (regno >= deps->max_reg)
 617         {
 618           if (GET_CODE (PATTERN (insn)) != USE
 619               && GET_CODE (PATTERN (insn)) != CLOBBER)
 620             abort ();
 621         }
 622       else
 623         {
 624           if (code == SET)
 625             SET_REGNO_REG_SET (reg_pending_sets, regno);
 626           else
 627             SET_REGNO_REG_SET (reg_pending_clobbers, regno);
 628
 629           /* Pseudos that are REG_EQUIV to something may be replaced
 630              by that during reloading.  We need only add dependencies for
 631              the address in the REG_EQUIV note.  */
 632           if (!reload_completed
 633               && reg_known_equiv_p[regno]
 634               && GET_CODE (reg_known_value[regno]) == MEM)
 635             sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn);
 636
 637           /* Don't let it cross a call after scheduling if it doesn't
 638              already cross one.  */
 639           if (REG_N_CALLS_CROSSED (regno) == 0)
 640             add_dependence_list (insn, deps->last_function_call, REG_DEP_ANTI);
 641         }
 642     }
 643   else if (GET_CODE (dest) == MEM)
 644     {
 645       /* Writing memory.  */
 646       rtx t = dest;
 647
 648       if (current_sched_info->use_cselib)
 649         {
 650           t = shallow_copy_rtx (dest);
 651           cselib_lookup (XEXP (t, 0), Pmode, 1);
 652           XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
 653         }
 654
 655       if (deps->pending_lists_length > MAX_PENDING_LIST_LENGTH)
 656         {
 657           /* Flush all pending reads and writes to prevent the pending lists
 658              from getting any larger.  Insn scheduling runs too slowly when
 659              these lists get long.  When compiling GCC with itself,
 660              this flush occurs 8 times for sparc, and 10 times for m88k using
 661              the default value of 32.  */
 662           flush_pending_lists (deps, insn, false, true);
 663         }
 664       else
 665         {
 666           rtx pending, pending_mem;
 667
 668           pending = deps->pending_read_insns;
 669           pending_mem = deps->pending_read_mems;
 670           while (pending)
 671             {
 672               if (anti_dependence (XEXP (pending_mem, 0), t))
 673                 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
 674
 675               pending = XEXP (pending, 1);
 676               pending_mem = XEXP (pending_mem, 1);
 677             }
 678
 679           pending = deps->pending_write_insns;
 680           pending_mem = deps->pending_write_mems;
 681           while (pending)
 682             {
 683               if (output_dependence (XEXP (pending_mem, 0), t))
 684                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
 685
 686               pending = XEXP (pending, 1);
 687               pending_mem = XEXP (pending_mem, 1);
 688             }
 689
 690           add_dependence_list (insn, deps->last_pending_memory_flush,
 691                                REG_DEP_ANTI);
 692
 693           add_insn_mem_dependence (deps, &deps->pending_write_insns,
 694                                    &deps->pending_write_mems, insn, dest);
 695         }
 696       sched_analyze_2 (deps, XEXP (dest, 0), insn);
 697     }
 698
 699   /* Analyze reads.  */
 700   if (GET_CODE (x) == SET)
 701     sched_analyze_2 (deps, SET_SRC (x), insn);
 702 }
 703
 704 /* Analyze the uses of memory and registers in rtx X in INSN.  */
 705
 706 static void
 707 sched_analyze_2 (deps, x, insn)
 708      struct deps *deps;
 709      rtx x;
 710      rtx insn;
 711 {
 712   int i;
 713   int j;
 714   enum rtx_code code;
 715   const char *fmt;
 716
 717   if (x == 0)
 718     return;
 719
 720   code = GET_CODE (x);
 721
 722   switch (code)
 723     {
 724     case CONST_INT:
 725     case CONST_DOUBLE:
 726     case 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 a post-call group is still open, see if it should remain so.
1166      This insn must be a simple move of a hard reg to a pseudo or
1167      vice-versa.
1168
1169      We must avoid moving these insns for correctness on
1170      SMALL_REGISTER_CLASS machines, and for special registers like
1171      PIC_OFFSET_TABLE_REGNUM.  For simplicity, extend this to all
1172      hard regs for all targets.  */
1173
1174   if (deps->in_post_call_group_p)
1175     {
1176       rtx tmp, set = single_set (insn);
1177       int src_regno, dest_regno;
1178
1179       if (set == NULL)
1180         goto end_call_group;
1181
1182       tmp = SET_DEST (set);
1183       if (GET_CODE (tmp) == SUBREG)
1184         tmp = SUBREG_REG (tmp);
1185       if (GET_CODE (tmp) == REG)
1186         dest_regno = REGNO (tmp);
1187       else
1188         goto end_call_group;
1189
1190       tmp = SET_SRC (set);
1191       if (GET_CODE (tmp) == SUBREG)
1192         tmp = SUBREG_REG (tmp);
1193       if (GET_CODE (tmp) == REG)
1194         src_regno = REGNO (tmp);
1195       else
1196         goto end_call_group;
1197
1198       if (src_regno < FIRST_PSEUDO_REGISTER
1199           || dest_regno < FIRST_PSEUDO_REGISTER)
1200         {
1201           set_sched_group_p (insn);
1202           CANT_MOVE (insn) = 1;
1203         }
1204       else
1205         {
1206         end_call_group:
1207           deps->in_post_call_group_p = false;
1208         }
1209     }
1210 }
1211
1212 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1213    for every dependency.  */
1214
1215 void
1216 sched_analyze (deps, head, tail)
1217      struct deps *deps;
1218      rtx head, tail;
1219 {
1220   rtx insn;
1221   rtx loop_notes = 0;
1222
1223   if (current_sched_info->use_cselib)
1224     cselib_init ();
1225
1226   for (insn = head;; insn = NEXT_INSN (insn))
1227     {
1228       if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
1229         {
1230           /* Clear out the stale LOG_LINKS from flow.  */
1231           free_INSN_LIST_list (&LOG_LINKS (insn));
1232
1233           /* Clear out stale SCHED_GROUP_P.  */
1234           SCHED_GROUP_P (insn) = 0;
1235
1236           /* Make each JUMP_INSN a scheduling barrier for memory
1237              references.  */
1238           if (GET_CODE (insn) == JUMP_INSN)
1239             {
1240               /* Keep the list a reasonable size.  */
1241               if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
1242                 flush_pending_lists (deps, insn, true, true);
1243               else
1244                 deps->last_pending_memory_flush
1245                   = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
1246             }
1247           sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1248           loop_notes = 0;
1249         }
1250       else if (GET_CODE (insn) == CALL_INSN)
1251         {
1252           int i;
1253
1254           /* Clear out stale SCHED_GROUP_P.  */
1255           SCHED_GROUP_P (insn) = 0;
1256
1257           CANT_MOVE (insn) = 1;
1258
1259           /* Clear out the stale LOG_LINKS from flow.  */
1260           free_INSN_LIST_list (&LOG_LINKS (insn));
1261
1262           if (find_reg_note (insn, REG_SETJMP, NULL))
1263             {
1264               /* This is setjmp.  Assume that all registers, not just
1265                  hard registers, may be clobbered by this call.  */
1266               reg_pending_barrier = true;
1267             }
1268           else
1269             {
1270               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1271                 /* A call may read and modify global register variables.  */
1272                 if (global_regs[i])
1273                   {
1274                     SET_REGNO_REG_SET (reg_pending_sets, i);
1275                     SET_REGNO_REG_SET (reg_pending_uses, i);
1276                   }
1277                 /* Other call-clobbered hard regs may be clobbered.  */
1278                 else if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1279                   SET_REGNO_REG_SET (reg_pending_clobbers, i);
1280                 /* We don't know what set of fixed registers might be used
1281                    by the function, but it is certain that the stack pointer
1282                    is among them, but be conservative.  */
1283                 else if (fixed_regs[i])
1284                   SET_REGNO_REG_SET (reg_pending_uses, i);
1285                 /* The frame pointer is normally not used by the function
1286                    itself, but by the debugger.  */
1287                 /* ??? MIPS o32 is an exception.  It uses the frame pointer
1288                    in the macro expansion of jal but does not represent this
1289                    fact in the call_insn rtl.  */
1290                 else if (i == FRAME_POINTER_REGNUM
1291                          || (i == HARD_FRAME_POINTER_REGNUM
1292                              && (! reload_completed || frame_pointer_needed)))
1293                   SET_REGNO_REG_SET (reg_pending_uses, i);
1294             }
1295
1296           /* For each insn which shouldn't cross a call, add a dependence
1297              between that insn and this call insn.  */
1298           add_dependence_list_and_free (insn, &deps->sched_before_next_call,
1299                                         REG_DEP_ANTI);
1300
1301           sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1302           loop_notes = 0;
1303
1304           /* In the absence of interprocedural alias analysis, we must flush
1305              all pending reads and writes, and start new dependencies starting
1306              from here.  But only flush writes for constant calls (which may
1307              be passed a pointer to something we haven't written yet).  */
1308           flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn));
1309
1310           /* Remember the last function call for limiting lifetimes.  */
1311           free_INSN_LIST_list (&deps->last_function_call);
1312           deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
1313
1314           /* Before reload, begin a post-call group, so as to keep the
1315              lifetimes of hard registers correct.  */
1316           if (! reload_completed)
1317             deps->in_post_call_group_p = true;
1318         }
1319
1320       /* See comments on reemit_notes as to why we do this.
1321          ??? Actually, the reemit_notes just say what is done, not why.  */
1322
1323       else if (GET_CODE (insn) == NOTE
1324                && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_BEG
1325                    || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END))
1326         {
1327           loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, NOTE_RANGE_INFO (insn),
1328                                         loop_notes);
1329           loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1330                                         GEN_INT (NOTE_LINE_NUMBER (insn)),
1331                                         loop_notes);
1332         }
1333       else if (GET_CODE (insn) == NOTE
1334                && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
1335                    || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
1336                    || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1337                    || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END))
1338         {
1339           rtx rtx_region;
1340
1341           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1342               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
1343             rtx_region = GEN_INT (NOTE_EH_HANDLER (insn));
1344           else
1345             rtx_region = GEN_INT (0);
1346
1347           loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1348                                         rtx_region,
1349                                         loop_notes);
1350           loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1351                                         GEN_INT (NOTE_LINE_NUMBER (insn)),
1352                                         loop_notes);
1353           CONST_OR_PURE_CALL_P (loop_notes) = CONST_OR_PURE_CALL_P (insn);
1354         }
1355
1356       if (current_sched_info->use_cselib)
1357         cselib_process_insn (insn);
1358       if (insn == tail)
1359         {
1360           if (current_sched_info->use_cselib)
1361             cselib_finish ();
1362           return;
1363         }
1364     }
1365   abort ();
1366 }
1367 \f
1368 /* Examine insns in the range [ HEAD, TAIL ] and Use the backward
1369    dependences from LOG_LINKS to build forward dependences in
1370    INSN_DEPEND.  */
1371
1372 void
1373 compute_forward_dependences (head, tail)
1374      rtx head, tail;
1375 {
1376   rtx insn, link;
1377   rtx next_tail;
1378   enum reg_note dep_type;
1379
1380   next_tail = NEXT_INSN (tail);
1381   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1382     {
1383       if (! INSN_P (insn))
1384         continue;
1385
1386       insn = group_leader (insn);
1387
1388       for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
1389         {
1390           rtx x = group_leader (XEXP (link, 0));
1391           rtx new_link;
1392
1393           if (x != XEXP (link, 0))
1394             continue;
1395
1396 #ifdef ENABLE_CHECKING
1397           /* If add_dependence is working properly there should never
1398              be notes, deleted insns or duplicates in the backward
1399              links.  Thus we need not check for them here.
1400
1401              However, if we have enabled checking we might as well go
1402              ahead and verify that add_dependence worked properly.  */
1403           if (GET_CODE (x) == NOTE
1404               || INSN_DELETED_P (x)
1405               || (forward_dependency_cache != NULL
1406                   && TEST_BIT (forward_dependency_cache[INSN_LUID (x)],
1407                                INSN_LUID (insn)))
1408               || (forward_dependency_cache == NULL
1409                   && find_insn_list (insn, INSN_DEPEND (x))))
1410             abort ();
1411           if (forward_dependency_cache != NULL)
1412             SET_BIT (forward_dependency_cache[INSN_LUID (x)],
1413                      INSN_LUID (insn));
1414 #endif
1415
1416           new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
1417
1418           dep_type = REG_NOTE_KIND (link);
1419           PUT_REG_NOTE_KIND (new_link, dep_type);
1420
1421           INSN_DEPEND (x) = new_link;
1422           INSN_DEP_COUNT (insn) += 1;
1423         }
1424     }
1425 }
1426 \f
1427 /* Initialize variables for region data dependence analysis.
1428    n_bbs is the number of region blocks.  */
1429
1430 void
1431 init_deps (deps)
1432      struct deps *deps;
1433 {
1434   int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
1435
1436   deps->max_reg = max_reg;
1437   deps->reg_last = (struct deps_reg *)
1438     xcalloc (max_reg, sizeof (struct deps_reg));
1439   INIT_REG_SET (&deps->reg_last_in_use);
1440
1441   deps->pending_read_insns = 0;
1442   deps->pending_read_mems = 0;
1443   deps->pending_write_insns = 0;
1444   deps->pending_write_mems = 0;
1445   deps->pending_lists_length = 0;
1446   deps->pending_flush_length = 0;
1447   deps->last_pending_memory_flush = 0;
1448   deps->last_function_call = 0;
1449   deps->sched_before_next_call = 0;
1450   deps->in_post_call_group_p = false;
1451 }
1452
1453 /* Free insn lists found in DEPS.  */
1454
1455 void
1456 free_deps (deps)
1457      struct deps *deps;
1458 {
1459   int i;
1460
1461   free_INSN_LIST_list (&deps->pending_read_insns);
1462   free_EXPR_LIST_list (&deps->pending_read_mems);
1463   free_INSN_LIST_list (&deps->pending_write_insns);
1464   free_EXPR_LIST_list (&deps->pending_write_mems);
1465   free_INSN_LIST_list (&deps->last_pending_memory_flush);
1466
1467   /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
1468      times.  For a test case with 42000 regs and 8000 small basic blocks,
1469      this loop accounted for nearly 60% (84 sec) of the total -O2 runtime.  */
1470   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i,
1471     {
1472       struct deps_reg *reg_last = &deps->reg_last[i];
1473       free_INSN_LIST_list (&reg_last->uses);
1474       free_INSN_LIST_list (&reg_last->sets);
1475       free_INSN_LIST_list (&reg_last->clobbers);
1476     });
1477   CLEAR_REG_SET (&deps->reg_last_in_use);
1478
1479   free (deps->reg_last);
1480 }
1481
1482 /* If it is profitable to use them, initialize caches for tracking
1483    dependency informatino.  LUID is the number of insns to be scheduled,
1484    it is used in the estimate of profitability.  */
1485
1486 void
1487 init_dependency_caches (luid)
1488      int luid;
1489 {
1490   /* ?!? We could save some memory by computing a per-region luid mapping
1491      which could reduce both the number of vectors in the cache and the size
1492      of each vector.  Instead we just avoid the cache entirely unless the
1493      average number of instructions in a basic block is very high.  See
1494      the comment before the declaration of true_dependency_cache for
1495      what we consider "very high".  */
1496   if (luid / n_basic_blocks > 100 * 5)
1497     {
1498       true_dependency_cache = sbitmap_vector_alloc (luid, luid);
1499       sbitmap_vector_zero (true_dependency_cache, luid);
1500       anti_dependency_cache = sbitmap_vector_alloc (luid, luid);
1501       sbitmap_vector_zero (anti_dependency_cache, luid);
1502       output_dependency_cache = sbitmap_vector_alloc (luid, luid);
1503       sbitmap_vector_zero (output_dependency_cache, luid);
1504 #ifdef ENABLE_CHECKING
1505       forward_dependency_cache = sbitmap_vector_alloc (luid, luid);
1506       sbitmap_vector_zero (forward_dependency_cache, luid);
1507 #endif
1508     }
1509 }
1510
1511 /* Free the caches allocated in init_dependency_caches.  */
1512
1513 void
1514 free_dependency_caches ()
1515 {
1516   if (true_dependency_cache)
1517     {
1518       sbitmap_vector_free (true_dependency_cache);
1519       true_dependency_cache = NULL;
1520       sbitmap_vector_free (anti_dependency_cache);
1521       anti_dependency_cache = NULL;
1522       sbitmap_vector_free (output_dependency_cache);
1523       output_dependency_cache = NULL;
1524 #ifdef ENABLE_CHECKING
1525       sbitmap_vector_free (forward_dependency_cache);
1526       forward_dependency_cache = NULL;
1527 #endif
1528     }
1529 }
1530
1531 /* Initialize some global variables needed by the dependency analysis
1532    code.  */
1533
1534 void
1535 init_deps_global ()
1536 {
1537   reg_pending_sets = INITIALIZE_REG_SET (reg_pending_sets_head);
1538   reg_pending_clobbers = INITIALIZE_REG_SET (reg_pending_clobbers_head);
1539   reg_pending_uses = INITIALIZE_REG_SET (reg_pending_uses_head);
1540   reg_pending_barrier = false;
1541 }
1542
1543 /* Free everything used by the dependency analysis code.  */
1544
1545 void
1546 finish_deps_global ()
1547 {
1548   FREE_REG_SET (reg_pending_sets);
1549   FREE_REG_SET (reg_pending_clobbers);
1550   FREE_REG_SET (reg_pending_uses);
1551 }