gcc/sched-deps.c

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