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.  */
 980       link = loop_notes;
 981       while (XEXP (link, 1))
 982         {
 983           gcc_assert (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
 984                       || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END);
 985
 986           reg_pending_barrier = MOVE_BARRIER;
 987           link = XEXP (link, 1);
 988         }
 989       XEXP (link, 1) = REG_NOTES (insn);
 990       REG_NOTES (insn) = loop_notes;
 991     }
 992
 993   /* If this instruction can throw an exception, then moving it changes
 994      where block boundaries fall.  This is mighty confusing elsewhere.
 995      Therefore, prevent such an instruction from being moved.  */
 996   if (can_throw_internal (insn))
 997     reg_pending_barrier = MOVE_BARRIER;
 998
 999   /* Add dependencies if a scheduling barrier was found.  */
1000   if (reg_pending_barrier)
1001     {
1002       /* In the case of barrier the most added dependencies are not
1003          real, so we use anti-dependence here.  */
1004       if (GET_CODE (PATTERN (insn)) == COND_EXEC)
1005         {
1006           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1007             {
1008               struct deps_reg *reg_last = &deps->reg_last[i];
1009               add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1010               add_dependence_list
1011                 (insn, reg_last->sets,
1012                  reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
1013               add_dependence_list
1014                 (insn, reg_last->clobbers,
1015                  reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
1016             }
1017         }
1018       else
1019         {
1020           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1021             {
1022               struct deps_reg *reg_last = &deps->reg_last[i];
1023               add_dependence_list_and_free (insn, &reg_last->uses,
1024                                             REG_DEP_ANTI);
1025               add_dependence_list_and_free
1026                 (insn, &reg_last->sets,
1027                  reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
1028               add_dependence_list_and_free
1029                 (insn, &reg_last->clobbers,
1030                  reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
1031               reg_last->uses_length = 0;
1032               reg_last->clobbers_length = 0;
1033             }
1034         }
1035
1036       for (i = 0; i < (unsigned)deps->max_reg; i++)
1037         {
1038           struct deps_reg *reg_last = &deps->reg_last[i];
1039           reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1040           SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
1041         }
1042
1043       flush_pending_lists (deps, insn, true, true);
1044       CLEAR_REG_SET (&deps->reg_conditional_sets);
1045       reg_pending_barrier = NOT_A_BARRIER;
1046     }
1047   else
1048     {
1049       /* If the current insn is conditional, we can't free any
1050          of the lists.  */
1051       if (GET_CODE (PATTERN (insn)) == COND_EXEC)
1052         {
1053           EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1054             {
1055               struct deps_reg *reg_last = &deps->reg_last[i];
1056               add_dependence_list (insn, reg_last->sets, 0);
1057               add_dependence_list (insn, reg_last->clobbers, 0);
1058               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1059               reg_last->uses_length++;
1060             }
1061           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
1062             {
1063               struct deps_reg *reg_last = &deps->reg_last[i];
1064               add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1065               add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1066               reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1067               reg_last->clobbers_length++;
1068             }
1069           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
1070             {
1071               struct deps_reg *reg_last = &deps->reg_last[i];
1072               add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1073               add_dependence_list (insn, reg_last->clobbers, REG_DEP_OUTPUT);
1074               add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1075               reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1076               SET_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1077             }
1078         }
1079       else
1080         {
1081           EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1082             {
1083               struct deps_reg *reg_last = &deps->reg_last[i];
1084               add_dependence_list (insn, reg_last->sets, 0);
1085               add_dependence_list (insn, reg_last->clobbers, 0);
1086               reg_last->uses_length++;
1087               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1088             }
1089           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
1090             {
1091               struct deps_reg *reg_last = &deps->reg_last[i];
1092               if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
1093                   || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
1094                 {
1095                   add_dependence_list_and_free (insn, &reg_last->sets,
1096                                                 REG_DEP_OUTPUT);
1097                   add_dependence_list_and_free (insn, &reg_last->uses,
1098                                                 REG_DEP_ANTI);
1099                   add_dependence_list_and_free (insn, &reg_last->clobbers,
1100                                                 REG_DEP_OUTPUT);
1101                   reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1102                   reg_last->clobbers_length = 0;
1103                   reg_last->uses_length = 0;
1104                 }
1105               else
1106                 {
1107                   add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1108                   add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1109                 }
1110               reg_last->clobbers_length++;
1111               reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1112             }
1113           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
1114             {
1115               struct deps_reg *reg_last = &deps->reg_last[i];
1116               add_dependence_list_and_free (insn, &reg_last->sets,
1117                                             REG_DEP_OUTPUT);
1118               add_dependence_list_and_free (insn, &reg_last->clobbers,
1119                                             REG_DEP_OUTPUT);
1120               add_dependence_list_and_free (insn, &reg_last->uses,
1121                                             REG_DEP_ANTI);
1122               reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1123               reg_last->uses_length = 0;
1124               reg_last->clobbers_length = 0;
1125               CLEAR_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1126             }
1127         }
1128
1129       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
1130       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
1131       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
1132     }
1133   CLEAR_REG_SET (reg_pending_uses);
1134   CLEAR_REG_SET (reg_pending_clobbers);
1135   CLEAR_REG_SET (reg_pending_sets);
1136
1137   /* If we are currently in a libcall scheduling group, then mark the
1138      current insn as being in a scheduling group and that it can not
1139      be moved into a different basic block.  */
1140
1141   if (deps->libcall_block_tail_insn)
1142     {
1143       SCHED_GROUP_P (insn) = 1;
1144       CANT_MOVE (insn) = 1;
1145     }
1146
1147   /* If a post-call group is still open, see if it should remain so.
1148      This insn must be a simple move of a hard reg to a pseudo or
1149      vice-versa.
1150
1151      We must avoid moving these insns for correctness on
1152      SMALL_REGISTER_CLASS machines, and for special registers like
1153      PIC_OFFSET_TABLE_REGNUM.  For simplicity, extend this to all
1154      hard regs for all targets.  */
1155
1156   if (deps->in_post_call_group_p)
1157     {
1158       rtx tmp, set = single_set (insn);
1159       int src_regno, dest_regno;
1160
1161       if (set == NULL)
1162         goto end_call_group;
1163
1164       tmp = SET_DEST (set);
1165       if (GET_CODE (tmp) == SUBREG)
1166         tmp = SUBREG_REG (tmp);
1167       if (REG_P (tmp))
1168         dest_regno = REGNO (tmp);
1169       else
1170         goto end_call_group;
1171
1172       tmp = SET_SRC (set);
1173       if (GET_CODE (tmp) == SUBREG)
1174         tmp = SUBREG_REG (tmp);
1175       if ((GET_CODE (tmp) == PLUS
1176            || GET_CODE (tmp) == MINUS)
1177           && REG_P (XEXP (tmp, 0))
1178           && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
1179           && dest_regno == STACK_POINTER_REGNUM)
1180         src_regno = STACK_POINTER_REGNUM;
1181       else if (REG_P (tmp))
1182         src_regno = REGNO (tmp);
1183       else
1184         goto end_call_group;
1185
1186       if (src_regno < FIRST_PSEUDO_REGISTER
1187           || dest_regno < FIRST_PSEUDO_REGISTER)
1188         {
1189           if (deps->in_post_call_group_p == post_call_initial)
1190             deps->in_post_call_group_p = post_call;
1191
1192           SCHED_GROUP_P (insn) = 1;
1193           CANT_MOVE (insn) = 1;
1194         }
1195       else
1196         {
1197         end_call_group:
1198           deps->in_post_call_group_p = not_post_call;
1199         }
1200     }
1201
1202   /* Fixup the dependencies in the sched group.  */
1203   if (SCHED_GROUP_P (insn))
1204     fixup_sched_groups (insn);
1205 }
1206
1207 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1208    for every dependency.  */
1209
1210 void
1211 sched_analyze (struct deps *deps, rtx head, rtx tail)
1212 {
1213   rtx insn;
1214   rtx loop_notes = 0;
1215
1216   if (current_sched_info->use_cselib)
1217     cselib_init (true);
1218
1219   /* Before reload, if the previous block ended in a call, show that
1220      we are inside a post-call group, so as to keep the lifetimes of
1221      hard registers correct.  */
1222   if (! reload_completed && !LABEL_P (head))
1223     {
1224       insn = prev_nonnote_insn (head);
1225       if (insn && CALL_P (insn))
1226         deps->in_post_call_group_p = post_call_initial;
1227     }
1228   for (insn = head;; insn = NEXT_INSN (insn))
1229     {
1230       rtx link, end_seq, r0, set;
1231
1232       if (NONJUMP_INSN_P (insn) || JUMP_P (insn))
1233         {
1234           /* Clear out the stale LOG_LINKS from flow.  */
1235           free_INSN_LIST_list (&LOG_LINKS (insn));
1236
1237           /* Make each JUMP_INSN a scheduling barrier for memory
1238              references.  */
1239           if (JUMP_P (insn))
1240             {
1241               /* Keep the list a reasonable size.  */
1242               if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
1243                 flush_pending_lists (deps, insn, true, true);
1244               else
1245                 deps->last_pending_memory_flush
1246                   = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
1247             }
1248           sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1249           loop_notes = 0;
1250         }
1251       else if (CALL_P (insn))
1252         {
1253           int i;
1254
1255           CANT_MOVE (insn) = 1;
1256
1257           /* Clear out the stale LOG_LINKS from flow.  */
1258           free_INSN_LIST_list (&LOG_LINKS (insn));
1259
1260           if (find_reg_note (insn, REG_SETJMP, NULL))
1261             {
1262               /* This is setjmp.  Assume that all registers, not just
1263                  hard registers, may be clobbered by this call.  */
1264               reg_pending_barrier = MOVE_BARRIER;
1265             }
1266           else
1267             {
1268               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1269                 /* A call may read and modify global register variables.  */
1270                 if (global_regs[i])
1271                   {
1272                     SET_REGNO_REG_SET (reg_pending_sets, i);
1273                     SET_REGNO_REG_SET (reg_pending_uses, i);
1274                   }
1275                 /* Other call-clobbered hard regs may be clobbered.
1276                    Since we only have a choice between 'might be clobbered'
1277                    and 'definitely not clobbered', we must include all
1278                    partly call-clobbered registers here.  */
1279                 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
1280                          || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1281                   SET_REGNO_REG_SET (reg_pending_clobbers, i);
1282                 /* We don't know what set of fixed registers might be used
1283                    by the function, but it is certain that the stack pointer
1284                    is among them, but be conservative.  */
1285                 else if (fixed_regs[i])
1286                   SET_REGNO_REG_SET (reg_pending_uses, i);
1287                 /* The frame pointer is normally not used by the function
1288                    itself, but by the debugger.  */
1289                 /* ??? MIPS o32 is an exception.  It uses the frame pointer
1290                    in the macro expansion of jal but does not represent this
1291                    fact in the call_insn rtl.  */
1292                 else if (i == FRAME_POINTER_REGNUM
1293                          || (i == HARD_FRAME_POINTER_REGNUM
1294                              && (! reload_completed || frame_pointer_needed)))
1295                   SET_REGNO_REG_SET (reg_pending_uses, i);
1296             }
1297
1298           /* For each insn which shouldn't cross a call, add a dependence
1299              between that insn and this call insn.  */
1300           add_dependence_list_and_free (insn, &deps->sched_before_next_call,
1301                                         REG_DEP_ANTI);
1302
1303           sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1304           loop_notes = 0;
1305
1306           /* In the absence of interprocedural alias analysis, we must flush
1307              all pending reads and writes, and start new dependencies starting
1308              from here.  But only flush writes for constant calls (which may
1309              be passed a pointer to something we haven't written yet).  */
1310           flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn));
1311
1312           /* Remember the last function call for limiting lifetimes.  */
1313           free_INSN_LIST_list (&deps->last_function_call);
1314           deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
1315
1316           /* Before reload, begin a post-call group, so as to keep the
1317              lifetimes of hard registers correct.  */
1318           if (! reload_completed)
1319             deps->in_post_call_group_p = post_call;
1320         }
1321
1322       /* EH_REGION insn notes can not appear until well after we complete
1323          scheduling.  */
1324       if (NOTE_P (insn))
1325         gcc_assert (NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
1326                     && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END);
1327
1328       /* See comments on reemit_notes as to why we do this.
1329          ??? Actually, the reemit_notes just say what is done, not why.  */
1330
1331       if (NOTE_P (insn)
1332           && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
1333               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END))
1334         {
1335           loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1336                                         GEN_INT (NOTE_LINE_NUMBER (insn)),
1337                                         loop_notes);
1338           CONST_OR_PURE_CALL_P (loop_notes) = CONST_OR_PURE_CALL_P (insn);
1339         }
1340
1341       if (current_sched_info->use_cselib)
1342         cselib_process_insn (insn);
1343
1344       /* Now that we have completed handling INSN, check and see if it is
1345          a CLOBBER beginning a libcall block.   If it is, record the
1346          end of the libcall sequence.
1347
1348          We want to schedule libcall blocks as a unit before reload.  While
1349          this restricts scheduling, it preserves the meaning of a libcall
1350          block.
1351
1352          As a side effect, we may get better code due to decreased register
1353          pressure as well as less chance of a foreign insn appearing in
1354          a libcall block.  */
1355       if (!reload_completed
1356           /* Note we may have nested libcall sequences.  We only care about
1357              the outermost libcall sequence.  */
1358           && deps->libcall_block_tail_insn == 0
1359           /* The sequence must start with a clobber of a register.  */
1360           && NONJUMP_INSN_P (insn)
1361           && GET_CODE (PATTERN (insn)) == CLOBBER
1362           && (r0 = XEXP (PATTERN (insn), 0), REG_P (r0))
1363           && REG_P (XEXP (PATTERN (insn), 0))
1364           /* The CLOBBER must also have a REG_LIBCALL note attached.  */
1365           && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
1366           && (end_seq = XEXP (link, 0)) != 0
1367           /* The insn referenced by the REG_LIBCALL note must be a
1368              simple nop copy with the same destination as the register
1369              mentioned in the clobber.  */
1370           && (set = single_set (end_seq)) != 0
1371           && SET_DEST (set) == r0 && SET_SRC (set) == r0
1372           /* And finally the insn referenced by the REG_LIBCALL must
1373              also contain a REG_EQUAL note and a REG_RETVAL note.  */
1374           && find_reg_note (end_seq, REG_EQUAL, NULL_RTX) != 0
1375           && find_reg_note (end_seq, REG_RETVAL, NULL_RTX) != 0)
1376         deps->libcall_block_tail_insn = XEXP (link, 0);
1377
1378       /* If we have reached the end of a libcall block, then close the
1379          block.  */
1380       if (deps->libcall_block_tail_insn == insn)
1381         deps->libcall_block_tail_insn = 0;
1382
1383       if (insn == tail)
1384         {
1385           if (current_sched_info->use_cselib)
1386             cselib_finish ();
1387           return;
1388         }
1389     }
1390   gcc_unreachable ();
1391 }
1392 \f
1393
1394 /* The following function adds forward dependence (FROM, TO) with
1395    given DEP_TYPE.  The forward dependence should be not exist before.  */
1396
1397 void
1398 add_forward_dependence (rtx from, rtx to, enum reg_note dep_type)
1399 {
1400   rtx new_link;
1401
1402 #ifdef ENABLE_CHECKING
1403   /* If add_dependence is working properly there should never
1404      be notes, deleted insns or duplicates in the backward
1405      links.  Thus we need not check for them here.
1406
1407      However, if we have enabled checking we might as well go
1408      ahead and verify that add_dependence worked properly.  */
1409   gcc_assert (!NOTE_P (from));
1410   gcc_assert (!INSN_DELETED_P (from));
1411   if (forward_dependency_cache)
1412     gcc_assert (!bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
1413                                INSN_LUID (to)));
1414   else
1415     gcc_assert (!find_insn_list (to, INSN_DEPEND (from)));
1416
1417   /* ??? If bitmap_bit_p is a predicate, what is this supposed to do? */
1418   if (forward_dependency_cache != NULL)
1419     bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
1420                   INSN_LUID (to));
1421 #endif
1422
1423   new_link = alloc_INSN_LIST (to, INSN_DEPEND (from));
1424
1425   PUT_REG_NOTE_KIND (new_link, dep_type);
1426
1427   INSN_DEPEND (from) = new_link;
1428   INSN_DEP_COUNT (to) += 1;
1429 }
1430
1431 /* Examine insns in the range [ HEAD, TAIL ] and Use the backward
1432    dependences from LOG_LINKS to build forward dependences in
1433    INSN_DEPEND.  */
1434
1435 void
1436 compute_forward_dependences (rtx head, rtx tail)
1437 {
1438   rtx insn, link;
1439   rtx next_tail;
1440
1441   next_tail = NEXT_INSN (tail);
1442   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1443     {
1444       if (! INSN_P (insn))
1445         continue;
1446
1447       for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
1448         add_forward_dependence (XEXP (link, 0), insn, REG_NOTE_KIND (link));
1449     }
1450 }
1451 \f
1452 /* Initialize variables for region data dependence analysis.
1453    n_bbs is the number of region blocks.  */
1454
1455 void
1456 init_deps (struct deps *deps)
1457 {
1458   int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
1459
1460   deps->max_reg = max_reg;
1461   deps->reg_last = xcalloc (max_reg, sizeof (struct deps_reg));
1462   INIT_REG_SET (&deps->reg_last_in_use);
1463   INIT_REG_SET (&deps->reg_conditional_sets);
1464
1465   deps->pending_read_insns = 0;
1466   deps->pending_read_mems = 0;
1467   deps->pending_write_insns = 0;
1468   deps->pending_write_mems = 0;
1469   deps->pending_lists_length = 0;
1470   deps->pending_flush_length = 0;
1471   deps->last_pending_memory_flush = 0;
1472   deps->last_function_call = 0;
1473   deps->sched_before_next_call = 0;
1474   deps->in_post_call_group_p = not_post_call;
1475   deps->libcall_block_tail_insn = 0;
1476 }
1477
1478 /* Free insn lists found in DEPS.  */
1479
1480 void
1481 free_deps (struct deps *deps)
1482 {
1483   unsigned i;
1484   reg_set_iterator rsi;
1485
1486   free_INSN_LIST_list (&deps->pending_read_insns);
1487   free_EXPR_LIST_list (&deps->pending_read_mems);
1488   free_INSN_LIST_list (&deps->pending_write_insns);
1489   free_EXPR_LIST_list (&deps->pending_write_mems);
1490   free_INSN_LIST_list (&deps->last_pending_memory_flush);
1491
1492   /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
1493      times.  For a testcase with 42000 regs and 8000 small basic blocks,
1494      this loop accounted for nearly 60% (84 sec) of the total -O2 runtime.  */
1495   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1496     {
1497       struct deps_reg *reg_last = &deps->reg_last[i];
1498       if (reg_last->uses)
1499         free_INSN_LIST_list (&reg_last->uses);
1500       if (reg_last->sets)
1501         free_INSN_LIST_list (&reg_last->sets);
1502       if (reg_last->clobbers)
1503         free_INSN_LIST_list (&reg_last->clobbers);
1504     }
1505   CLEAR_REG_SET (&deps->reg_last_in_use);
1506   CLEAR_REG_SET (&deps->reg_conditional_sets);
1507
1508   free (deps->reg_last);
1509 }
1510
1511 /* If it is profitable to use them, initialize caches for tracking
1512    dependency information.  LUID is the number of insns to be scheduled,
1513    it is used in the estimate of profitability.  */
1514
1515 void
1516 init_dependency_caches (int luid)
1517 {
1518   /* ?!? We could save some memory by computing a per-region luid mapping
1519      which could reduce both the number of vectors in the cache and the size
1520      of each vector.  Instead we just avoid the cache entirely unless the
1521      average number of instructions in a basic block is very high.  See
1522      the comment before the declaration of true_dependency_cache for
1523      what we consider "very high".  */
1524   if (luid / n_basic_blocks > 100 * 5)
1525     {
1526       int i;
1527       true_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1528       anti_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1529       output_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1530 #ifdef ENABLE_CHECKING
1531       forward_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1532 #endif
1533       for (i = 0; i < luid; i++)
1534         {
1535           bitmap_initialize (&true_dependency_cache[i], 0);
1536           bitmap_initialize (&anti_dependency_cache[i], 0);
1537           bitmap_initialize (&output_dependency_cache[i], 0);
1538 #ifdef ENABLE_CHECKING
1539           bitmap_initialize (&forward_dependency_cache[i], 0);
1540 #endif
1541         }
1542       cache_size = luid;
1543     }
1544 }
1545
1546 /* Free the caches allocated in init_dependency_caches.  */
1547
1548 void
1549 free_dependency_caches (void)
1550 {
1551   if (true_dependency_cache)
1552     {
1553       int i;
1554
1555       for (i = 0; i < cache_size; i++)
1556         {
1557           bitmap_clear (&true_dependency_cache[i]);
1558           bitmap_clear (&anti_dependency_cache[i]);
1559           bitmap_clear (&output_dependency_cache[i]);
1560 #ifdef ENABLE_CHECKING
1561           bitmap_clear (&forward_dependency_cache[i]);
1562 #endif
1563         }
1564       free (true_dependency_cache);
1565       true_dependency_cache = NULL;
1566       free (anti_dependency_cache);
1567       anti_dependency_cache = NULL;
1568       free (output_dependency_cache);
1569       output_dependency_cache = NULL;
1570 #ifdef ENABLE_CHECKING
1571       free (forward_dependency_cache);
1572       forward_dependency_cache = NULL;
1573 #endif
1574     }
1575 }
1576
1577 /* Initialize some global variables needed by the dependency analysis
1578    code.  */
1579
1580 void
1581 init_deps_global (void)
1582 {
1583   reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
1584   reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
1585   reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
1586   reg_pending_barrier = NOT_A_BARRIER;
1587 }
1588
1589 /* Free everything used by the dependency analysis code.  */
1590
1591 void
1592 finish_deps_global (void)
1593 {
1594   FREE_REG_SET (reg_pending_sets);
1595   FREE_REG_SET (reg_pending_clobbers);
1596   FREE_REG_SET (reg_pending_uses);
1597 }