gcc/sched-deps.c

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