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