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