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