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, 2005, 2006
   5    Free Software Foundation, Inc.
   6    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
   7    and currently maintained by, Jim Wilson (wilson@cygnus.com)
   8
   9 This file is part of GCC.
  10
  11 GCC is free software; you can redistribute it and/or modify it under
  12 the terms of the GNU General Public License as published by the Free
  13 Software Foundation; either version 2, or (at your option) any later
  14 version.
  15
  16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  18 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  19 for more details.
  20
  21 You should have received a copy of the GNU General Public License
  22 along with GCC; see the file COPYING.  If not, write to the Free
  23 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  24 02110-1301, USA.  */
  25 \f
  26 #include "config.h"
  27 #include "system.h"
  28 #include "coretypes.h"
  29 #include "tm.h"
  30 #include "toplev.h"
  31 #include "rtl.h"
  32 #include "tm_p.h"
  33 #include "hard-reg-set.h"
  34 #include "regs.h"
  35 #include "function.h"
  36 #include "flags.h"
  37 #include "insn-config.h"
  38 #include "insn-attr.h"
  39 #include "except.h"
  40 #include "toplev.h"
  41 #include "recog.h"
  42 #include "sched-int.h"
  43 #include "params.h"
  44 #include "cselib.h"
  45 #include "df.h"
  46
  47
  48 static regset reg_pending_sets;
  49 static regset reg_pending_clobbers;
  50 static regset reg_pending_uses;
  51
  52 /* The following enumeration values tell us what dependencies we
  53    should use to implement the barrier.  We use true-dependencies for
  54    TRUE_BARRIER and anti-dependencies for MOVE_BARRIER.  */
  55 enum reg_pending_barrier_mode
  56 {
  57   NOT_A_BARRIER = 0,
  58   MOVE_BARRIER,
  59   TRUE_BARRIER
  60 };
  61
  62 static enum reg_pending_barrier_mode reg_pending_barrier;
  63
  64 /* To speed up the test for duplicate dependency links we keep a
  65    record of dependencies created by add_dependence when the average
  66    number of instructions in a basic block is very large.
  67
  68    Studies have shown that there is typically around 5 instructions between
  69    branches for typical C code.  So we can make a guess that the average
  70    basic block is approximately 5 instructions long; we will choose 100X
  71    the average size as a very large basic block.
  72
  73    Each insn has associated bitmaps for its dependencies.  Each bitmap
  74    has enough entries to represent a dependency on any other insn in
  75    the insn chain.  All bitmap for true dependencies cache is
  76    allocated then the rest two ones are also allocated.  */
  77 static bitmap_head *true_dependency_cache;
  78 static bitmap_head *output_dependency_cache;
  79 static bitmap_head *anti_dependency_cache;
  80 static bitmap_head *spec_dependency_cache;
  81 static int cache_size;
  82
  83 /* To speed up checking consistency of formed forward insn
  84    dependencies we use the following cache.  Another possible solution
  85    could be switching off checking duplication of insns in forward
  86    dependencies.  */
  87 #ifdef ENABLE_CHECKING
  88 static bitmap_head *forward_dependency_cache;
  89 #endif
  90
  91 static int deps_may_trap_p (rtx);
  92 static void add_dependence_list (rtx, rtx, int, enum reg_note);
  93 static void add_dependence_list_and_free (rtx, rtx *, int, enum reg_note);
  94 static void delete_all_dependences (rtx);
  95 static void fixup_sched_groups (rtx);
  96
  97 static void flush_pending_lists (struct deps *, rtx, int, int);
  98 static void sched_analyze_1 (struct deps *, rtx, rtx);
  99 static void sched_analyze_2 (struct deps *, rtx, rtx);
 100 static void sched_analyze_insn (struct deps *, rtx, rtx);
 101
 102 static rtx sched_get_condition (rtx);
 103 static int conditions_mutex_p (rtx, rtx);
 104
 105 static enum DEPS_ADJUST_RESULT maybe_add_or_update_back_dep_1 (rtx, rtx,
 106                                enum reg_note, ds_t, rtx, rtx, rtx **);
 107 static enum DEPS_ADJUST_RESULT add_or_update_back_dep_1 (rtx, rtx,
 108                                enum reg_note, ds_t, rtx, rtx, rtx **);
 109 static void add_back_dep (rtx, rtx, enum reg_note, ds_t);
 110
 111 static void adjust_add_sorted_back_dep (rtx, rtx, rtx *);
 112 static void adjust_back_add_forw_dep (rtx, rtx *);
 113 static void delete_forw_dep (rtx, rtx);
 114 static dw_t estimate_dep_weak (rtx, rtx);
 115 #ifdef INSN_SCHEDULING
 116 #ifdef ENABLE_CHECKING
 117 static void check_dep_status (enum reg_note, ds_t, bool);
 118 #endif
 119 #endif
 120 \f
 121 /* Return nonzero if a load of the memory reference MEM can cause a trap.  */
 122
 123 static int
 124 deps_may_trap_p (rtx mem)
 125 {
 126   rtx addr = XEXP (mem, 0);
 127
 128   if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
 129     {
 130       rtx t = get_reg_known_value (REGNO (addr));
 131       if (t)
 132         addr = t;
 133     }
 134   return rtx_addr_can_trap_p (addr);
 135 }
 136 \f
 137 /* Return the INSN_LIST containing INSN in LIST, or NULL
 138    if LIST does not contain INSN.  */
 139
 140 rtx
 141 find_insn_list (rtx insn, rtx list)
 142 {
 143   while (list)
 144     {
 145       if (XEXP (list, 0) == insn)
 146         return list;
 147       list = XEXP (list, 1);
 148     }
 149   return 0;
 150 }
 151 \f
 152 /* Find the condition under which INSN is executed.  */
 153
 154 static rtx
 155 sched_get_condition (rtx insn)
 156 {
 157   rtx pat = PATTERN (insn);
 158   rtx src;
 159
 160   if (pat == 0)
 161     return 0;
 162
 163   if (GET_CODE (pat) == COND_EXEC)
 164     return COND_EXEC_TEST (pat);
 165
 166   if (!any_condjump_p (insn) || !onlyjump_p (insn))
 167     return 0;
 168
 169   src = SET_SRC (pc_set (insn));
 170
 171   if (XEXP (src, 2) == pc_rtx)
 172     return XEXP (src, 0);
 173   else if (XEXP (src, 1) == pc_rtx)
 174     {
 175       rtx cond = XEXP (src, 0);
 176       enum rtx_code revcode = reversed_comparison_code (cond, insn);
 177
 178       if (revcode == UNKNOWN)
 179         return 0;
 180       return gen_rtx_fmt_ee (revcode, GET_MODE (cond), XEXP (cond, 0),
 181                              XEXP (cond, 1));
 182     }
 183
 184   return 0;
 185 }
 186
 187 \f
 188 /* Return nonzero if conditions COND1 and COND2 can never be both true.  */
 189
 190 static int
 191 conditions_mutex_p (rtx cond1, rtx cond2)
 192 {
 193   if (COMPARISON_P (cond1)
 194       && COMPARISON_P (cond2)
 195       && GET_CODE (cond1) == reversed_comparison_code (cond2, NULL)
 196       && XEXP (cond1, 0) == XEXP (cond2, 0)
 197       && XEXP (cond1, 1) == XEXP (cond2, 1))
 198     return 1;
 199   return 0;
 200 }
 201
 202 /* Return true if insn1 and insn2 can never depend on one another because
 203    the conditions under which they are executed are mutually exclusive.  */
 204 bool
 205 sched_insns_conditions_mutex_p (rtx insn1, rtx insn2)
 206 {
 207   rtx cond1, cond2;
 208
 209   /* flow.c doesn't handle conditional lifetimes entirely correctly;
 210      calls mess up the conditional lifetimes.  */
 211   if (!CALL_P (insn1) && !CALL_P (insn2))
 212     {
 213       cond1 = sched_get_condition (insn1);
 214       cond2 = sched_get_condition (insn2);
 215       if (cond1 && cond2
 216           && conditions_mutex_p (cond1, cond2)
 217           /* Make sure first instruction doesn't affect condition of second
 218              instruction if switched.  */
 219           && !modified_in_p (cond1, insn2)
 220           /* Make sure second instruction doesn't affect condition of first
 221              instruction if switched.  */
 222           && !modified_in_p (cond2, insn1))
 223         return true;
 224     }
 225   return false;
 226 }
 227 \f
 228 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
 229    LOG_LINKS of INSN, if it is not already there.  DEP_TYPE indicates the
 230    type of dependence that this link represents.  DS, if nonzero,
 231    indicates speculations, through which this dependence can be overcome.
 232    MEM1 and MEM2, if non-null, corresponds to memory locations in case of
 233    data speculation.  The function returns a value indicating if an old entry
 234    has been changed or a new entry has been added to insn's LOG_LINK.
 235    In case of changed entry CHANGED_LINKPP sets to its address.
 236    See also the definition of enum DEPS_ADJUST_RESULT in sched-int.h.
 237    Actual manipulation of dependence data structures is performed in
 238    add_or_update_back_dep_1.  */
 239
 240 static enum DEPS_ADJUST_RESULT
 241 maybe_add_or_update_back_dep_1 (rtx insn, rtx elem, enum reg_note dep_type,
 242                                 ds_t ds, rtx mem1, rtx mem2,
 243                                 rtx **changed_linkpp)
 244 {
 245   gcc_assert (INSN_P (insn) && INSN_P (elem));
 246
 247   /* Don't depend an insn on itself.  */
 248   if (insn == elem)
 249     {
 250 #ifdef INSN_SCHEDULING
 251       if (current_sched_info->flags & DO_SPECULATION)
 252         /* INSN has an internal dependence, which we can't overcome.  */
 253         HAS_INTERNAL_DEP (insn) = 1;
 254 #endif
 255       return 0;
 256     }
 257
 258   return add_or_update_back_dep_1 (insn, elem, dep_type,
 259                                    ds, mem1, mem2, changed_linkpp);
 260 }
 261
 262 /* This function has the same meaning of parameters and return values
 263    as maybe_add_or_update_back_dep_1.  The only difference between these
 264    two functions is that INSN and ELEM are guaranteed not to be the same
 265    in this one.  */
 266 static enum DEPS_ADJUST_RESULT
 267 add_or_update_back_dep_1 (rtx insn, rtx elem, enum reg_note dep_type,
 268                           ds_t ds ATTRIBUTE_UNUSED,
 269                           rtx mem1 ATTRIBUTE_UNUSED, rtx mem2 ATTRIBUTE_UNUSED,
 270                           rtx **changed_linkpp ATTRIBUTE_UNUSED)
 271 {
 272   bool maybe_present_p = true, present_p = false;
 273
 274   gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
 275
 276 #ifdef INSN_SCHEDULING
 277
 278 #ifdef ENABLE_CHECKING
 279   check_dep_status (dep_type, ds, mem1 != NULL);
 280 #endif
 281
 282   /* If we already have a dependency for ELEM, then we do not need to
 283      do anything.  Avoiding the list walk below can cut compile times
 284      dramatically for some code.  */
 285   if (true_dependency_cache != NULL)
 286     {
 287       enum reg_note present_dep_type;
 288
 289       gcc_assert (output_dependency_cache);
 290       gcc_assert (anti_dependency_cache);
 291       if (!(current_sched_info->flags & USE_DEPS_LIST))
 292         {
 293           if (bitmap_bit_p (&true_dependency_cache[INSN_LUID (insn)],
 294                             INSN_LUID (elem)))
 295             present_dep_type = REG_DEP_TRUE;
 296           else if (bitmap_bit_p (&output_dependency_cache[INSN_LUID (insn)],
 297                                  INSN_LUID (elem)))
 298             present_dep_type = REG_DEP_OUTPUT;
 299           else if (bitmap_bit_p (&anti_dependency_cache[INSN_LUID (insn)],
 300                                  INSN_LUID (elem)))
 301             present_dep_type = REG_DEP_ANTI;
 302           else
 303             maybe_present_p = false;
 304
 305           if (maybe_present_p)
 306             {
 307               if ((int) dep_type >= (int) present_dep_type)
 308                 return DEP_PRESENT;
 309
 310               present_p = true;
 311             }
 312         }
 313       else
 314         {
 315           ds_t present_dep_types = 0;
 316
 317           if (bitmap_bit_p (&true_dependency_cache[INSN_LUID (insn)],
 318                             INSN_LUID (elem)))
 319             present_dep_types |= DEP_TRUE;
 320           if (bitmap_bit_p (&output_dependency_cache[INSN_LUID (insn)],
 321                             INSN_LUID (elem)))
 322             present_dep_types |= DEP_OUTPUT;
 323           if (bitmap_bit_p (&anti_dependency_cache[INSN_LUID (insn)],
 324                             INSN_LUID (elem)))
 325             present_dep_types |= DEP_ANTI;
 326
 327           if (present_dep_types)
 328             {
 329               if (!(current_sched_info->flags & DO_SPECULATION)
 330                   || !bitmap_bit_p (&spec_dependency_cache[INSN_LUID (insn)],
 331                                     INSN_LUID (elem)))
 332                 {
 333                   if ((present_dep_types | (ds & DEP_TYPES))
 334                       == present_dep_types)
 335                     /* We already have all these bits.  */
 336                     return DEP_PRESENT;
 337                 }
 338               else
 339                 {
 340                   /* Only true dependencies can be data speculative and
 341                      only anti dependencies can be control speculative.  */
 342                   gcc_assert ((present_dep_types & (DEP_TRUE | DEP_ANTI))
 343                               == present_dep_types);
 344
 345                   /* if (additional dep is SPECULATIVE) then
 346                        we should update DEP_STATUS
 347                      else
 348                        we should reset existing dep to non-speculative.  */
 349                 }
 350
 351               present_p = true;
 352             }
 353           else
 354             maybe_present_p = false;
 355         }
 356     }
 357 #endif
 358
 359   /* Check that we don't already have this dependence.  */
 360   if (maybe_present_p)
 361     {
 362       rtx *linkp;
 363
 364       for (linkp = &LOG_LINKS (insn); *linkp; linkp = &XEXP (*linkp, 1))
 365         {
 366           rtx link = *linkp;
 367
 368           gcc_assert (true_dependency_cache == 0 || present_p);
 369
 370           if (XEXP (link, 0) == elem)
 371             {
 372               enum DEPS_ADJUST_RESULT changed_p = DEP_PRESENT;
 373
 374 #ifdef INSN_SCHEDULING
 375               if (current_sched_info->flags & USE_DEPS_LIST)
 376                 {
 377                   ds_t new_status = ds | DEP_STATUS (link);
 378
 379                   if (new_status & SPECULATIVE)
 380                     {
 381                       if (!(ds & SPECULATIVE)
 382                           || !(DEP_STATUS (link) & SPECULATIVE))
 383                         /* Then this dep can't be speculative.  */
 384                         {
 385                           new_status &= ~SPECULATIVE;
 386                           if (true_dependency_cache
 387                               && (DEP_STATUS (link) & SPECULATIVE))
 388                             bitmap_clear_bit (&spec_dependency_cache
 389                                               [INSN_LUID (insn)],
 390                                               INSN_LUID (elem));
 391                         }
 392                       else
 393                         {
 394                           /* Both are speculative.  Merging probabilities.  */
 395                           if (mem1)
 396                             {
 397                               dw_t dw;
 398
 399                               dw = estimate_dep_weak (mem1, mem2);
 400                               ds = set_dep_weak (ds, BEGIN_DATA, dw);
 401                             }
 402
 403                           new_status = ds_merge (DEP_STATUS (link), ds);
 404                         }
 405                     }
 406
 407                   ds = new_status;
 408                 }
 409
 410               /* Clear corresponding cache entry because type of the link
 411                  may have changed.  Keep them if we use_deps_list.  */
 412               if (true_dependency_cache != NULL
 413                   && !(current_sched_info->flags & USE_DEPS_LIST))
 414                 {
 415                   enum reg_note kind = REG_NOTE_KIND (link);
 416
 417                   switch (kind)
 418                     {
 419                     case REG_DEP_OUTPUT:
 420                       bitmap_clear_bit (&output_dependency_cache
 421                                         [INSN_LUID (insn)], INSN_LUID (elem));
 422                       break;
 423                     case REG_DEP_ANTI:
 424                       bitmap_clear_bit (&anti_dependency_cache
 425                                         [INSN_LUID (insn)], INSN_LUID (elem));
 426                       break;
 427                     default:
 428                       gcc_unreachable ();
 429                     }
 430                 }
 431
 432               if ((current_sched_info->flags & USE_DEPS_LIST)
 433                   && DEP_STATUS (link) != ds)
 434                 {
 435                   DEP_STATUS (link) = ds;
 436                   changed_p = DEP_CHANGED;
 437                 }
 438 #endif
 439
 440               /* If this is a more restrictive type of dependence than the
 441                  existing one, then change the existing dependence to this
 442                  type.  */
 443               if ((int) dep_type < (int) REG_NOTE_KIND (link))
 444                 {
 445                   PUT_REG_NOTE_KIND (link, dep_type);
 446                   changed_p = DEP_CHANGED;
 447                 }
 448
 449 #ifdef INSN_SCHEDULING
 450               /* If we are adding a dependency to INSN's LOG_LINKs, then
 451                  note that in the bitmap caches of dependency information.  */
 452               if (true_dependency_cache != NULL)
 453                 {
 454                   if (!(current_sched_info->flags & USE_DEPS_LIST))
 455                     {
 456                       if (REG_NOTE_KIND (link) == REG_DEP_TRUE)
 457                         bitmap_set_bit (&true_dependency_cache
 458                                         [INSN_LUID (insn)], INSN_LUID (elem));
 459                       else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
 460                         bitmap_set_bit (&output_dependency_cache
 461                                         [INSN_LUID (insn)], INSN_LUID (elem));
 462                       else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
 463                         bitmap_set_bit (&anti_dependency_cache
 464                                         [INSN_LUID (insn)], INSN_LUID (elem));
 465                     }
 466                   else
 467                     {
 468                       if (ds & DEP_TRUE)
 469                         bitmap_set_bit (&true_dependency_cache
 470                                         [INSN_LUID (insn)], INSN_LUID (elem));
 471                       if (ds & DEP_OUTPUT)
 472                         bitmap_set_bit (&output_dependency_cache
 473                                         [INSN_LUID (insn)], INSN_LUID (elem));
 474                       if (ds & DEP_ANTI)
 475                         bitmap_set_bit (&anti_dependency_cache
 476                                         [INSN_LUID (insn)], INSN_LUID (elem));
 477                       /* Note, that dep can become speculative only
 478                          at the moment of creation. Thus, we don't need to
 479                          check for it here.  */
 480                     }
 481                 }
 482
 483               if (changed_linkpp && changed_p == DEP_CHANGED)
 484                 *changed_linkpp = linkp;
 485 #endif
 486               return changed_p;
 487             }
 488         }
 489       /* We didn't find a dep. It shouldn't be present in the cache.  */
 490       gcc_assert (!present_p);
 491     }
 492
 493   /* Might want to check one level of transitivity to save conses.
 494      This check should be done in maybe_add_or_update_back_dep_1.
 495      Since we made it to add_or_update_back_dep_1, we must create
 496      (or update) a link.  */
 497
 498   if (mem1)
 499     {
 500       gcc_assert (current_sched_info->flags & DO_SPECULATION);
 501       ds = set_dep_weak (ds, BEGIN_DATA, estimate_dep_weak (mem1, mem2));
 502     }
 503
 504   add_back_dep (insn, elem, dep_type, ds);
 505
 506   return DEP_CREATED;
 507 }
 508
 509 /* This function creates a link between INSN and ELEM under any
 510    conditions.  DS describes speculative status of the link.  */
 511 static void
 512 add_back_dep (rtx insn, rtx elem, enum reg_note dep_type, ds_t ds)
 513 {
 514   gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
 515
 516   if (current_sched_info->flags & USE_DEPS_LIST)
 517     LOG_LINKS (insn) = alloc_DEPS_LIST (elem, LOG_LINKS (insn), ds);
 518   else
 519     LOG_LINKS (insn) = alloc_INSN_LIST (elem, LOG_LINKS (insn));
 520
 521   /* Insn dependency, not data dependency.  */
 522   PUT_REG_NOTE_KIND (LOG_LINKS (insn), dep_type);
 523
 524 #ifdef INSN_SCHEDULING
 525 #ifdef ENABLE_CHECKING
 526   check_dep_status (dep_type, ds, false);
 527 #endif
 528
 529   /* If we are adding a dependency to INSN's LOG_LINKs, then note that
 530      in the bitmap caches of dependency information.  */
 531   if (true_dependency_cache != NULL)
 532     {
 533       if (!(current_sched_info->flags & USE_DEPS_LIST))
 534         {
 535           if (dep_type == REG_DEP_TRUE)
 536             bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)],
 537                             INSN_LUID (elem));
 538           else if (dep_type == REG_DEP_OUTPUT)
 539             bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)],
 540                             INSN_LUID (elem));
 541           else if (dep_type == REG_DEP_ANTI)
 542                 bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)],
 543                                 INSN_LUID (elem));
 544         }
 545       else
 546         {
 547           if (ds & DEP_TRUE)
 548             bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)],
 549                             INSN_LUID (elem));
 550           if (ds & DEP_OUTPUT)
 551             bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)],
 552                             INSN_LUID (elem));
 553           if (ds & DEP_ANTI)
 554             bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)],
 555                             INSN_LUID (elem));
 556           if (ds & SPECULATIVE)
 557             {
 558               gcc_assert (current_sched_info->flags & DO_SPECULATION);
 559               bitmap_set_bit (&spec_dependency_cache[INSN_LUID (insn)],
 560                               INSN_LUID (elem));
 561             }
 562         }
 563     }
 564 #endif
 565 }
 566
 567 /* A convenience wrapper to operate on an entire list.  */
 568
 569 static void
 570 add_dependence_list (rtx insn, rtx list, int uncond, enum reg_note dep_type)
 571 {
 572   for (; list; list = XEXP (list, 1))
 573     {
 574       if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
 575         add_dependence (insn, XEXP (list, 0), dep_type);
 576     }
 577 }
 578
 579 /* Similar, but free *LISTP at the same time.  */
 580
 581 static void
 582 add_dependence_list_and_free (rtx insn, rtx *listp, int uncond,
 583                               enum reg_note dep_type)
 584 {
 585   rtx list, next;
 586   for (list = *listp, *listp = NULL; list ; list = next)
 587     {
 588       next = XEXP (list, 1);
 589       if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
 590         add_dependence (insn, XEXP (list, 0), dep_type);
 591       free_INSN_LIST_node (list);
 592     }
 593 }
 594
 595 /* Clear all dependencies for an insn.  */
 596
 597 static void
 598 delete_all_dependences (rtx insn)
 599 {
 600   /* Clear caches, if they exist, as well as free the dependence.  */
 601
 602 #ifdef INSN_SCHEDULING
 603   if (true_dependency_cache != NULL)
 604     {
 605       bitmap_clear (&true_dependency_cache[INSN_LUID (insn)]);
 606       bitmap_clear (&output_dependency_cache[INSN_LUID (insn)]);
 607       bitmap_clear (&anti_dependency_cache[INSN_LUID (insn)]);
 608       /* We don't have to clear forward_dependency_cache here,
 609          because it is formed later.  */
 610       if (current_sched_info->flags & DO_SPECULATION)
 611         bitmap_clear (&spec_dependency_cache[INSN_LUID (insn)]);
 612     }
 613 #endif
 614
 615   if (!(current_sched_info->flags & USE_DEPS_LIST))
 616     /* In this case LOG_LINKS are formed from the DEPS_LISTs,
 617        not the INSN_LISTs.  */
 618     free_INSN_LIST_list (&LOG_LINKS (insn));
 619   else
 620     free_DEPS_LIST_list (&LOG_LINKS (insn));
 621 }
 622
 623 /* All insns in a scheduling group except the first should only have
 624    dependencies on the previous insn in the group.  So we find the
 625    first instruction in the scheduling group by walking the dependence
 626    chains backwards. Then we add the dependencies for the group to
 627    the previous nonnote insn.  */
 628
 629 static void
 630 fixup_sched_groups (rtx insn)
 631 {
 632   rtx link, prev_nonnote;
 633
 634   for (link = LOG_LINKS (insn); link ; link = XEXP (link, 1))
 635     {
 636       rtx i = insn;
 637       do
 638         {
 639           i = prev_nonnote_insn (i);
 640
 641           if (XEXP (link, 0) == i)
 642             goto next_link;
 643         } while (SCHED_GROUP_P (i));
 644       if (! sched_insns_conditions_mutex_p (i, XEXP (link, 0)))
 645         add_dependence (i, XEXP (link, 0), REG_NOTE_KIND (link));
 646     next_link:;
 647     }
 648
 649   delete_all_dependences (insn);
 650
 651   prev_nonnote = prev_nonnote_insn (insn);
 652   if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
 653       && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
 654     add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
 655 }
 656 \f
 657 /* Process an insn's memory dependencies.  There are four kinds of
 658    dependencies:
 659
 660    (0) read dependence: read follows read
 661    (1) true dependence: read follows write
 662    (2) output dependence: write follows write
 663    (3) anti dependence: write follows read
 664
 665    We are careful to build only dependencies which actually exist, and
 666    use transitivity to avoid building too many links.  */
 667
 668 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
 669    The MEM is a memory reference contained within INSN, which we are saving
 670    so that we can do memory aliasing on it.  */
 671
 672 static void
 673 add_insn_mem_dependence (struct deps *deps, rtx *insn_list, rtx *mem_list,
 674                          rtx insn, rtx mem)
 675 {
 676   rtx link;
 677
 678   link = alloc_INSN_LIST (insn, *insn_list);
 679   *insn_list = link;
 680
 681   if (current_sched_info->use_cselib)
 682     {
 683       mem = shallow_copy_rtx (mem);
 684       XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0));
 685     }
 686   link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
 687   *mem_list = link;
 688
 689   deps->pending_lists_length++;
 690 }
 691
 692 /* Make a dependency between every memory reference on the pending lists
 693    and INSN, thus flushing the pending lists.  FOR_READ is true if emitting
 694    dependencies for a read operation, similarly with FOR_WRITE.  */
 695
 696 static void
 697 flush_pending_lists (struct deps *deps, rtx insn, int for_read,
 698                      int for_write)
 699 {
 700   if (for_write)
 701     {
 702       add_dependence_list_and_free (insn, &deps->pending_read_insns, 1,
 703                                     REG_DEP_ANTI);
 704       free_EXPR_LIST_list (&deps->pending_read_mems);
 705     }
 706
 707   add_dependence_list_and_free (insn, &deps->pending_write_insns, 1,
 708                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
 709   free_EXPR_LIST_list (&deps->pending_write_mems);
 710   deps->pending_lists_length = 0;
 711
 712   add_dependence_list_and_free (insn, &deps->last_pending_memory_flush, 1,
 713                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
 714   deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
 715   deps->pending_flush_length = 1;
 716 }
 717 \f
 718 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
 719    The type of the reference is specified by REF and can be SET,
 720    CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE.  */
 721
 722 static void
 723 sched_analyze_reg (struct deps *deps, int regno, enum machine_mode mode,
 724                    enum rtx_code ref, rtx insn)
 725 {
 726   /* A hard reg in a wide mode may really be multiple registers.
 727      If so, mark all of them just like the first.  */
 728   if (regno < FIRST_PSEUDO_REGISTER)
 729     {
 730       int i = hard_regno_nregs[regno][mode];
 731       if (ref == SET)
 732         {
 733           while (--i >= 0)
 734             SET_REGNO_REG_SET (reg_pending_sets, regno + i);
 735         }
 736       else if (ref == USE)
 737         {
 738           while (--i >= 0)
 739             SET_REGNO_REG_SET (reg_pending_uses, regno + i);
 740         }
 741       else
 742         {
 743           while (--i >= 0)
 744             SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
 745         }
 746     }
 747
 748   /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
 749      it does not reload.  Ignore these as they have served their
 750      purpose already.  */
 751   else if (regno >= deps->max_reg)
 752     {
 753       enum rtx_code code = GET_CODE (PATTERN (insn));
 754       gcc_assert (code == USE || code == CLOBBER);
 755     }
 756
 757   else
 758     {
 759       if (ref == SET)
 760         SET_REGNO_REG_SET (reg_pending_sets, regno);
 761       else if (ref == USE)
 762         SET_REGNO_REG_SET (reg_pending_uses, regno);
 763       else
 764         SET_REGNO_REG_SET (reg_pending_clobbers, regno);
 765
 766       /* Pseudos that are REG_EQUIV to something may be replaced
 767          by that during reloading.  We need only add dependencies for
 768         the address in the REG_EQUIV note.  */
 769       if (!reload_completed && get_reg_known_equiv_p (regno))
 770         {
 771           rtx t = get_reg_known_value (regno);
 772           if (MEM_P (t))
 773             sched_analyze_2 (deps, XEXP (t, 0), insn);
 774         }
 775
 776       /* Don't let it cross a call after scheduling if it doesn't
 777          already cross one.  */
 778       if (REG_N_CALLS_CROSSED (regno) == 0)
 779         {
 780           if (ref == USE)
 781             deps->sched_before_next_call
 782               = alloc_INSN_LIST (insn, deps->sched_before_next_call);
 783           else
 784             add_dependence_list (insn, deps->last_function_call, 1,
 785                                  REG_DEP_ANTI);
 786         }
 787     }
 788 }
 789
 790 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
 791    rtx, X, creating all dependencies generated by the write to the
 792    destination of X, and reads of everything mentioned.  */
 793
 794 static void
 795 sched_analyze_1 (struct deps *deps, rtx x, rtx insn)
 796 {
 797   rtx dest = XEXP (x, 0);
 798   enum rtx_code code = GET_CODE (x);
 799
 800   if (dest == 0)
 801     return;
 802
 803   if (GET_CODE (dest) == PARALLEL)
 804     {
 805       int i;
 806
 807       for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
 808         if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
 809           sched_analyze_1 (deps,
 810                            gen_rtx_CLOBBER (VOIDmode,
 811                                             XEXP (XVECEXP (dest, 0, i), 0)),
 812                            insn);
 813
 814       if (GET_CODE (x) == SET)
 815         sched_analyze_2 (deps, SET_SRC (x), insn);
 816       return;
 817     }
 818
 819   while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
 820          || GET_CODE (dest) == ZERO_EXTRACT)
 821     {
 822       if (GET_CODE (dest) == STRICT_LOW_PART
 823          || GET_CODE (dest) == ZERO_EXTRACT
 824          || df_read_modify_subreg_p (dest))
 825         {
 826           /* These both read and modify the result.  We must handle
 827              them as writes to get proper dependencies for following
 828              instructions.  We must handle them as reads to get proper
 829              dependencies from this to previous instructions.
 830              Thus we need to call sched_analyze_2.  */
 831
 832           sched_analyze_2 (deps, XEXP (dest, 0), insn);
 833         }
 834       if (GET_CODE (dest) == ZERO_EXTRACT)
 835         {
 836           /* The second and third arguments are values read by this insn.  */
 837           sched_analyze_2 (deps, XEXP (dest, 1), insn);
 838           sched_analyze_2 (deps, XEXP (dest, 2), insn);
 839         }
 840       dest = XEXP (dest, 0);
 841     }
 842
 843   if (REG_P (dest))
 844     {
 845       int regno = REGNO (dest);
 846       enum machine_mode mode = GET_MODE (dest);
 847
 848       sched_analyze_reg (deps, regno, mode, code, insn);
 849
 850 #ifdef STACK_REGS
 851       /* Treat all writes to a stack register as modifying the TOS.  */
 852       if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
 853         {
 854           /* Avoid analyzing the same register twice.  */
 855           if (regno != FIRST_STACK_REG)
 856             sched_analyze_reg (deps, FIRST_STACK_REG, mode, code, insn);
 857           sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
 858         }
 859 #endif
 860     }
 861   else if (MEM_P (dest))
 862     {
 863       /* Writing memory.  */
 864       rtx t = dest;
 865
 866       if (current_sched_info->use_cselib)
 867         {
 868           t = shallow_copy_rtx (dest);
 869           cselib_lookup (XEXP (t, 0), Pmode, 1);
 870           XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
 871         }
 872       t = canon_rtx (t);
 873
 874       if (deps->pending_lists_length > MAX_PENDING_LIST_LENGTH)
 875         {
 876           /* Flush all pending reads and writes to prevent the pending lists
 877              from getting any larger.  Insn scheduling runs too slowly when
 878              these lists get long.  When compiling GCC with itself,
 879              this flush occurs 8 times for sparc, and 10 times for m88k using
 880              the default value of 32.  */
 881           flush_pending_lists (deps, insn, false, true);
 882         }
 883       else
 884         {
 885           rtx pending, pending_mem;
 886
 887           pending = deps->pending_read_insns;
 888           pending_mem = deps->pending_read_mems;
 889           while (pending)
 890             {
 891               if (anti_dependence (XEXP (pending_mem, 0), t)
 892                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
 893                 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
 894
 895               pending = XEXP (pending, 1);
 896               pending_mem = XEXP (pending_mem, 1);
 897             }
 898
 899           pending = deps->pending_write_insns;
 900           pending_mem = deps->pending_write_mems;
 901           while (pending)
 902             {
 903               if (output_dependence (XEXP (pending_mem, 0), t)
 904                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
 905                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
 906
 907               pending = XEXP (pending, 1);
 908               pending_mem = XEXP (pending_mem, 1);
 909             }
 910
 911           add_dependence_list (insn, deps->last_pending_memory_flush, 1,
 912                                REG_DEP_ANTI);
 913
 914           add_insn_mem_dependence (deps, &deps->pending_write_insns,
 915                                    &deps->pending_write_mems, insn, dest);
 916         }
 917       sched_analyze_2 (deps, XEXP (dest, 0), insn);
 918     }
 919
 920   /* Analyze reads.  */
 921   if (GET_CODE (x) == SET)
 922     sched_analyze_2 (deps, SET_SRC (x), insn);
 923 }
 924
 925 /* Analyze the uses of memory and registers in rtx X in INSN.  */
 926
 927 static void
 928 sched_analyze_2 (struct deps *deps, rtx x, rtx insn)
 929 {
 930   int i;
 931   int j;
 932   enum rtx_code code;
 933   const char *fmt;
 934
 935   if (x == 0)
 936     return;
 937
 938   code = GET_CODE (x);
 939
 940   switch (code)
 941     {
 942     case CONST_INT:
 943     case CONST_DOUBLE:
 944     case CONST_VECTOR:
 945     case SYMBOL_REF:
 946     case CONST:
 947     case LABEL_REF:
 948       /* Ignore constants.  Note that we must handle CONST_DOUBLE here
 949          because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
 950          this does not mean that this insn is using cc0.  */
 951       return;
 952
 953 #ifdef HAVE_cc0
 954     case CC0:
 955       /* User of CC0 depends on immediately preceding insn.  */
 956       SCHED_GROUP_P (insn) = 1;
 957        /* Don't move CC0 setter to another block (it can set up the
 958         same flag for previous CC0 users which is safe).  */
 959       CANT_MOVE (prev_nonnote_insn (insn)) = 1;
 960       return;
 961 #endif
 962
 963     case REG:
 964       {
 965         int regno = REGNO (x);
 966         enum machine_mode mode = GET_MODE (x);
 967
 968         sched_analyze_reg (deps, regno, mode, USE, insn);
 969
 970 #ifdef STACK_REGS
 971       /* Treat all reads of a stack register as modifying the TOS.  */
 972       if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
 973         {
 974           /* Avoid analyzing the same register twice.  */
 975           if (regno != FIRST_STACK_REG)
 976             sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
 977           sched_analyze_reg (deps, FIRST_STACK_REG, mode, SET, insn);
 978         }
 979 #endif
 980         return;
 981       }
 982
 983     case MEM:
 984       {
 985         /* Reading memory.  */
 986         rtx u;
 987         rtx pending, pending_mem;
 988         rtx t = x;
 989
 990         if (current_sched_info->use_cselib)
 991           {
 992             t = shallow_copy_rtx (t);
 993             cselib_lookup (XEXP (t, 0), Pmode, 1);
 994             XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
 995           }
 996         t = canon_rtx (t);
 997         pending = deps->pending_read_insns;
 998         pending_mem = deps->pending_read_mems;
 999         while (pending)
1000           {
1001             if (read_dependence (XEXP (pending_mem, 0), t)
1002                 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1003               add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
1004
1005             pending = XEXP (pending, 1);
1006             pending_mem = XEXP (pending_mem, 1);
1007           }
1008
1009         pending = deps->pending_write_insns;
1010         pending_mem = deps->pending_write_mems;
1011         while (pending)
1012           {
1013             if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
1014                                  t, rtx_varies_p)
1015                 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1016               {
1017                 if (current_sched_info->flags & DO_SPECULATION)
1018                   maybe_add_or_update_back_dep_1 (insn, XEXP (pending, 0),
1019                                                   REG_DEP_TRUE,
1020                                                   BEGIN_DATA | DEP_TRUE,
1021                                                   XEXP (pending_mem, 0), t, 0);
1022                 else
1023                   add_dependence (insn, XEXP (pending, 0), REG_DEP_TRUE);
1024               }
1025
1026             pending = XEXP (pending, 1);
1027             pending_mem = XEXP (pending_mem, 1);
1028           }
1029
1030         for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
1031           if (! JUMP_P (XEXP (u, 0)) || deps_may_trap_p (x))
1032             add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1033
1034         /* Always add these dependencies to pending_reads, since
1035            this insn may be followed by a write.  */
1036         add_insn_mem_dependence (deps, &deps->pending_read_insns,
1037                                  &deps->pending_read_mems, insn, x);
1038
1039         /* Take advantage of tail recursion here.  */
1040         sched_analyze_2 (deps, XEXP (x, 0), insn);
1041         return;
1042       }
1043
1044     /* Force pending stores to memory in case a trap handler needs them.  */
1045     case TRAP_IF:
1046       flush_pending_lists (deps, insn, true, false);
1047       break;
1048
1049     case ASM_OPERANDS:
1050     case ASM_INPUT:
1051     case UNSPEC_VOLATILE:
1052       {
1053         /* Traditional and volatile asm instructions must be considered to use
1054            and clobber all hard registers, all pseudo-registers and all of
1055            memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
1056
1057            Consider for instance a volatile asm that changes the fpu rounding
1058            mode.  An insn should not be moved across this even if it only uses
1059            pseudo-regs because it might give an incorrectly rounded result.  */
1060         if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
1061           reg_pending_barrier = TRUE_BARRIER;
1062
1063         /* For all ASM_OPERANDS, we must traverse the vector of input operands.
1064            We can not just fall through here since then we would be confused
1065            by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
1066            traditional asms unlike their normal usage.  */
1067
1068         if (code == ASM_OPERANDS)
1069           {
1070             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
1071               sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
1072             return;
1073           }
1074         break;
1075       }
1076
1077     case PRE_DEC:
1078     case POST_DEC:
1079     case PRE_INC:
1080     case POST_INC:
1081       /* These both read and modify the result.  We must handle them as writes
1082          to get proper dependencies for following instructions.  We must handle
1083          them as reads to get proper dependencies from this to previous
1084          instructions.  Thus we need to pass them to both sched_analyze_1
1085          and sched_analyze_2.  We must call sched_analyze_2 first in order
1086          to get the proper antecedent for the read.  */
1087       sched_analyze_2 (deps, XEXP (x, 0), insn);
1088       sched_analyze_1 (deps, x, insn);
1089       return;
1090
1091     case POST_MODIFY:
1092     case PRE_MODIFY:
1093       /* op0 = op0 + op1 */
1094       sched_analyze_2 (deps, XEXP (x, 0), insn);
1095       sched_analyze_2 (deps, XEXP (x, 1), insn);
1096       sched_analyze_1 (deps, x, insn);
1097       return;
1098
1099     default:
1100       break;
1101     }
1102
1103   /* Other cases: walk the insn.  */
1104   fmt = GET_RTX_FORMAT (code);
1105   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1106     {
1107       if (fmt[i] == 'e')
1108         sched_analyze_2 (deps, XEXP (x, i), insn);
1109       else if (fmt[i] == 'E')
1110         for (j = 0; j < XVECLEN (x, i); j++)
1111           sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
1112     }
1113 }
1114
1115 /* Analyze an INSN with pattern X to find all dependencies.  */
1116
1117 static void
1118 sched_analyze_insn (struct deps *deps, rtx x, rtx insn)
1119 {
1120   RTX_CODE code = GET_CODE (x);
1121   rtx link;
1122   unsigned i;
1123   reg_set_iterator rsi;
1124
1125   if (code == COND_EXEC)
1126     {
1127       sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
1128
1129       /* ??? Should be recording conditions so we reduce the number of
1130          false dependencies.  */
1131       x = COND_EXEC_CODE (x);
1132       code = GET_CODE (x);
1133     }
1134   if (code == SET || code == CLOBBER)
1135     {
1136       sched_analyze_1 (deps, x, insn);
1137
1138       /* Bare clobber insns are used for letting life analysis, reg-stack
1139          and others know that a value is dead.  Depend on the last call
1140          instruction so that reg-stack won't get confused.  */
1141       if (code == CLOBBER)
1142         add_dependence_list (insn, deps->last_function_call, 1, REG_DEP_OUTPUT);
1143     }
1144   else if (code == PARALLEL)
1145     {
1146       for (i = XVECLEN (x, 0); i--;)
1147         {
1148           rtx sub = XVECEXP (x, 0, i);
1149           code = GET_CODE (sub);
1150
1151           if (code == COND_EXEC)
1152             {
1153               sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
1154               sub = COND_EXEC_CODE (sub);
1155               code = GET_CODE (sub);
1156             }
1157           if (code == SET || code == CLOBBER)
1158             sched_analyze_1 (deps, sub, insn);
1159           else
1160             sched_analyze_2 (deps, sub, insn);
1161         }
1162     }
1163   else
1164     sched_analyze_2 (deps, x, insn);
1165
1166   /* Mark registers CLOBBERED or used by called function.  */
1167   if (CALL_P (insn))
1168     {
1169       for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
1170         {
1171           if (GET_CODE (XEXP (link, 0)) == CLOBBER)
1172             sched_analyze_1 (deps, XEXP (link, 0), insn);
1173           else
1174             sched_analyze_2 (deps, XEXP (link, 0), insn);
1175         }
1176       if (find_reg_note (insn, REG_SETJMP, NULL))
1177         reg_pending_barrier = MOVE_BARRIER;
1178     }
1179
1180   if (JUMP_P (insn))
1181     {
1182       rtx next;
1183       next = next_nonnote_insn (insn);
1184       if (next && BARRIER_P (next))
1185         reg_pending_barrier = TRUE_BARRIER;
1186       else
1187         {
1188           rtx pending, pending_mem;
1189           regset_head tmp_uses, tmp_sets;
1190           INIT_REG_SET (&tmp_uses);
1191           INIT_REG_SET (&tmp_sets);
1192
1193           (*current_sched_info->compute_jump_reg_dependencies)
1194             (insn, &deps->reg_conditional_sets, &tmp_uses, &tmp_sets);
1195           /* Make latency of jump equal to 0 by using anti-dependence.  */
1196           EXECUTE_IF_SET_IN_REG_SET (&tmp_uses, 0, i, rsi)
1197             {
1198               struct deps_reg *reg_last = &deps->reg_last[i];
1199               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
1200               add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI);
1201               reg_last->uses_length++;
1202               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1203             }
1204           IOR_REG_SET (reg_pending_sets, &tmp_sets);
1205
1206           CLEAR_REG_SET (&tmp_uses);
1207           CLEAR_REG_SET (&tmp_sets);
1208
1209           /* All memory writes and volatile reads must happen before the
1210              jump.  Non-volatile reads must happen before the jump iff
1211              the result is needed by the above register used mask.  */
1212
1213           pending = deps->pending_write_insns;
1214           pending_mem = deps->pending_write_mems;
1215           while (pending)
1216             {
1217               if (! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1218                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
1219               pending = XEXP (pending, 1);
1220               pending_mem = XEXP (pending_mem, 1);
1221             }
1222
1223           pending = deps->pending_read_insns;
1224           pending_mem = deps->pending_read_mems;
1225           while (pending)
1226             {
1227               if (MEM_VOLATILE_P (XEXP (pending_mem, 0))
1228                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1229                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
1230               pending = XEXP (pending, 1);
1231               pending_mem = XEXP (pending_mem, 1);
1232             }
1233
1234           add_dependence_list (insn, deps->last_pending_memory_flush, 1,
1235                                REG_DEP_ANTI);
1236         }
1237     }
1238
1239   /* If this instruction can throw an exception, then moving it changes
1240      where block boundaries fall.  This is mighty confusing elsewhere.
1241      Therefore, prevent such an instruction from being moved.  */
1242   if (can_throw_internal (insn))
1243     reg_pending_barrier = MOVE_BARRIER;
1244
1245   /* Add dependencies if a scheduling barrier was found.  */
1246   if (reg_pending_barrier)
1247     {
1248       /* In the case of barrier the most added dependencies are not
1249          real, so we use anti-dependence here.  */
1250       if (sched_get_condition (insn))
1251         {
1252           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1253             {
1254               struct deps_reg *reg_last = &deps->reg_last[i];
1255               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1256               add_dependence_list
1257                 (insn, reg_last->sets, 0,
1258                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1259               add_dependence_list
1260                 (insn, reg_last->clobbers, 0,
1261                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1262             }
1263         }
1264       else
1265         {
1266           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1267             {
1268               struct deps_reg *reg_last = &deps->reg_last[i];
1269               add_dependence_list_and_free (insn, &reg_last->uses, 0,
1270                                             REG_DEP_ANTI);
1271               add_dependence_list_and_free
1272                 (insn, &reg_last->sets, 0,
1273                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1274               add_dependence_list_and_free
1275                 (insn, &reg_last->clobbers, 0,
1276                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1277               reg_last->uses_length = 0;
1278               reg_last->clobbers_length = 0;
1279             }
1280         }
1281
1282       for (i = 0; i < (unsigned)deps->max_reg; i++)
1283         {
1284           struct deps_reg *reg_last = &deps->reg_last[i];
1285           reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1286           SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
1287         }
1288
1289       flush_pending_lists (deps, insn, true, true);
1290       CLEAR_REG_SET (&deps->reg_conditional_sets);
1291       reg_pending_barrier = NOT_A_BARRIER;
1292     }
1293   else
1294     {
1295       /* If the current insn is conditional, we can't free any
1296          of the lists.  */
1297       if (sched_get_condition (insn))
1298         {
1299           EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1300             {
1301               struct deps_reg *reg_last = &deps->reg_last[i];
1302               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
1303               add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
1304               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1305               reg_last->uses_length++;
1306             }
1307           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
1308             {
1309               struct deps_reg *reg_last = &deps->reg_last[i];
1310               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
1311               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1312               reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1313               reg_last->clobbers_length++;
1314             }
1315           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
1316             {
1317               struct deps_reg *reg_last = &deps->reg_last[i];
1318               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
1319               add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT);
1320               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1321               reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1322               SET_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1323             }
1324         }
1325       else
1326         {
1327           EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1328             {
1329               struct deps_reg *reg_last = &deps->reg_last[i];
1330               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
1331               add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
1332               reg_last->uses_length++;
1333               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1334             }
1335           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
1336             {
1337               struct deps_reg *reg_last = &deps->reg_last[i];
1338               if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
1339                   || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
1340                 {
1341                   add_dependence_list_and_free (insn, &reg_last->sets, 0,
1342                                                 REG_DEP_OUTPUT);
1343                   add_dependence_list_and_free (insn, &reg_last->uses, 0,
1344                                                 REG_DEP_ANTI);
1345                   add_dependence_list_and_free (insn, &reg_last->clobbers, 0,
1346                                                 REG_DEP_OUTPUT);
1347                   reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1348                   reg_last->clobbers_length = 0;
1349                   reg_last->uses_length = 0;
1350                 }
1351               else
1352                 {
1353                   add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
1354                   add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1355                 }
1356               reg_last->clobbers_length++;
1357               reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1358             }
1359           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
1360             {
1361               struct deps_reg *reg_last = &deps->reg_last[i];
1362               add_dependence_list_and_free (insn, &reg_last->sets, 0,
1363                                             REG_DEP_OUTPUT);
1364               add_dependence_list_and_free (insn, &reg_last->clobbers, 0,
1365                                             REG_DEP_OUTPUT);
1366               add_dependence_list_and_free (insn, &reg_last->uses, 0,
1367                                             REG_DEP_ANTI);
1368               reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1369               reg_last->uses_length = 0;
1370               reg_last->clobbers_length = 0;
1371               CLEAR_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1372             }
1373         }
1374
1375       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
1376       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
1377       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
1378     }
1379   CLEAR_REG_SET (reg_pending_uses);
1380   CLEAR_REG_SET (reg_pending_clobbers);
1381   CLEAR_REG_SET (reg_pending_sets);
1382
1383   /* If we are currently in a libcall scheduling group, then mark the
1384      current insn as being in a scheduling group and that it can not
1385      be moved into a different basic block.  */
1386
1387   if (deps->libcall_block_tail_insn)
1388     {
1389       SCHED_GROUP_P (insn) = 1;
1390       CANT_MOVE (insn) = 1;
1391     }
1392
1393   /* If a post-call group is still open, see if it should remain so.
1394      This insn must be a simple move of a hard reg to a pseudo or
1395      vice-versa.
1396
1397      We must avoid moving these insns for correctness on
1398      SMALL_REGISTER_CLASS machines, and for special registers like
1399      PIC_OFFSET_TABLE_REGNUM.  For simplicity, extend this to all
1400      hard regs for all targets.  */
1401
1402   if (deps->in_post_call_group_p)
1403     {
1404       rtx tmp, set = single_set (insn);
1405       int src_regno, dest_regno;
1406
1407       if (set == NULL)
1408         goto end_call_group;
1409
1410       tmp = SET_DEST (set);
1411       if (GET_CODE (tmp) == SUBREG)
1412         tmp = SUBREG_REG (tmp);
1413       if (REG_P (tmp))
1414         dest_regno = REGNO (tmp);
1415       else
1416         goto end_call_group;
1417
1418       tmp = SET_SRC (set);
1419       if (GET_CODE (tmp) == SUBREG)
1420         tmp = SUBREG_REG (tmp);
1421       if ((GET_CODE (tmp) == PLUS
1422            || GET_CODE (tmp) == MINUS)
1423           && REG_P (XEXP (tmp, 0))
1424           && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
1425           && dest_regno == STACK_POINTER_REGNUM)
1426         src_regno = STACK_POINTER_REGNUM;
1427       else if (REG_P (tmp))
1428         src_regno = REGNO (tmp);
1429       else
1430         goto end_call_group;
1431
1432       if (src_regno < FIRST_PSEUDO_REGISTER
1433           || dest_regno < FIRST_PSEUDO_REGISTER)
1434         {
1435           if (deps->in_post_call_group_p == post_call_initial)
1436             deps->in_post_call_group_p = post_call;
1437
1438           SCHED_GROUP_P (insn) = 1;
1439           CANT_MOVE (insn) = 1;
1440         }
1441       else
1442         {
1443         end_call_group:
1444           deps->in_post_call_group_p = not_post_call;
1445         }
1446     }
1447
1448   /* Fixup the dependencies in the sched group.  */
1449   if (SCHED_GROUP_P (insn))
1450     fixup_sched_groups (insn);
1451 }
1452
1453 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1454    for every dependency.  */
1455
1456 void
1457 sched_analyze (struct deps *deps, rtx head, rtx tail)
1458 {
1459   rtx insn;
1460
1461   if (current_sched_info->use_cselib)
1462     cselib_init (true);
1463
1464   /* Before reload, if the previous block ended in a call, show that
1465      we are inside a post-call group, so as to keep the lifetimes of
1466      hard registers correct.  */
1467   if (! reload_completed && !LABEL_P (head))
1468     {
1469       insn = prev_nonnote_insn (head);
1470       if (insn && CALL_P (insn))
1471         deps->in_post_call_group_p = post_call_initial;
1472     }
1473   for (insn = head;; insn = NEXT_INSN (insn))
1474     {
1475       rtx link, end_seq, r0, set;
1476
1477       if (NONJUMP_INSN_P (insn) || JUMP_P (insn))
1478         {
1479           /* Clear out the stale LOG_LINKS from flow.  */
1480           free_INSN_LIST_list (&LOG_LINKS (insn));
1481
1482           /* Make each JUMP_INSN a scheduling barrier for memory
1483              references.  */
1484           if (JUMP_P (insn))
1485             {
1486               /* Keep the list a reasonable size.  */
1487               if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
1488                 flush_pending_lists (deps, insn, true, true);
1489               else
1490                 deps->last_pending_memory_flush
1491                   = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
1492             }
1493           sched_analyze_insn (deps, PATTERN (insn), insn);
1494         }
1495       else if (CALL_P (insn))
1496         {
1497           int i;
1498
1499           CANT_MOVE (insn) = 1;
1500
1501           /* Clear out the stale LOG_LINKS from flow.  */
1502           free_INSN_LIST_list (&LOG_LINKS (insn));
1503
1504           if (find_reg_note (insn, REG_SETJMP, NULL))
1505             {
1506               /* This is setjmp.  Assume that all registers, not just
1507                  hard registers, may be clobbered by this call.  */
1508               reg_pending_barrier = MOVE_BARRIER;
1509             }
1510           else
1511             {
1512               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1513                 /* A call may read and modify global register variables.  */
1514                 if (global_regs[i])
1515                   {
1516                     SET_REGNO_REG_SET (reg_pending_sets, i);
1517                     SET_REGNO_REG_SET (reg_pending_uses, i);
1518                   }
1519                 /* Other call-clobbered hard regs may be clobbered.
1520                    Since we only have a choice between 'might be clobbered'
1521                    and 'definitely not clobbered', we must include all
1522                    partly call-clobbered registers here.  */
1523                 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
1524                          || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1525                   SET_REGNO_REG_SET (reg_pending_clobbers, i);
1526                 /* We don't know what set of fixed registers might be used
1527                    by the function, but it is certain that the stack pointer
1528                    is among them, but be conservative.  */
1529                 else if (fixed_regs[i])
1530                   SET_REGNO_REG_SET (reg_pending_uses, i);
1531                 /* The frame pointer is normally not used by the function
1532                    itself, but by the debugger.  */
1533                 /* ??? MIPS o32 is an exception.  It uses the frame pointer
1534                    in the macro expansion of jal but does not represent this
1535                    fact in the call_insn rtl.  */
1536                 else if (i == FRAME_POINTER_REGNUM
1537                          || (i == HARD_FRAME_POINTER_REGNUM
1538                              && (! reload_completed || frame_pointer_needed)))
1539                   SET_REGNO_REG_SET (reg_pending_uses, i);
1540             }
1541
1542           /* For each insn which shouldn't cross a call, add a dependence
1543              between that insn and this call insn.  */
1544           add_dependence_list_and_free (insn, &deps->sched_before_next_call, 1,
1545                                         REG_DEP_ANTI);
1546
1547           sched_analyze_insn (deps, PATTERN (insn), insn);
1548
1549           /* In the absence of interprocedural alias analysis, we must flush
1550              all pending reads and writes, and start new dependencies starting
1551              from here.  But only flush writes for constant calls (which may
1552              be passed a pointer to something we haven't written yet).  */
1553           flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn));
1554
1555           /* Remember the last function call for limiting lifetimes.  */
1556           free_INSN_LIST_list (&deps->last_function_call);
1557           deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
1558
1559           /* Before reload, begin a post-call group, so as to keep the
1560              lifetimes of hard registers correct.  */
1561           if (! reload_completed)
1562             deps->in_post_call_group_p = post_call;
1563         }
1564
1565       /* EH_REGION insn notes can not appear until well after we complete
1566          scheduling.  */
1567       if (NOTE_P (insn))
1568         gcc_assert (NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
1569                     && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END);
1570
1571       if (current_sched_info->use_cselib)
1572         cselib_process_insn (insn);
1573
1574       /* Now that we have completed handling INSN, check and see if it is
1575          a CLOBBER beginning a libcall block.   If it is, record the
1576          end of the libcall sequence.
1577
1578          We want to schedule libcall blocks as a unit before reload.  While
1579          this restricts scheduling, it preserves the meaning of a libcall
1580          block.
1581
1582          As a side effect, we may get better code due to decreased register
1583          pressure as well as less chance of a foreign insn appearing in
1584          a libcall block.  */
1585       if (!reload_completed
1586           /* Note we may have nested libcall sequences.  We only care about
1587              the outermost libcall sequence.  */
1588           && deps->libcall_block_tail_insn == 0
1589           /* The sequence must start with a clobber of a register.  */
1590           && NONJUMP_INSN_P (insn)
1591           && GET_CODE (PATTERN (insn)) == CLOBBER
1592           && (r0 = XEXP (PATTERN (insn), 0), REG_P (r0))
1593           && REG_P (XEXP (PATTERN (insn), 0))
1594           /* The CLOBBER must also have a REG_LIBCALL note attached.  */
1595           && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
1596           && (end_seq = XEXP (link, 0)) != 0
1597           /* The insn referenced by the REG_LIBCALL note must be a
1598              simple nop copy with the same destination as the register
1599              mentioned in the clobber.  */
1600           && (set = single_set (end_seq)) != 0
1601           && SET_DEST (set) == r0 && SET_SRC (set) == r0
1602           /* And finally the insn referenced by the REG_LIBCALL must
1603              also contain a REG_EQUAL note and a REG_RETVAL note.  */
1604           && find_reg_note (end_seq, REG_EQUAL, NULL_RTX) != 0
1605           && find_reg_note (end_seq, REG_RETVAL, NULL_RTX) != 0)
1606         deps->libcall_block_tail_insn = XEXP (link, 0);
1607
1608       /* If we have reached the end of a libcall block, then close the
1609          block.  */
1610       if (deps->libcall_block_tail_insn == insn)
1611         deps->libcall_block_tail_insn = 0;
1612
1613       if (insn == tail)
1614         {
1615           if (current_sched_info->use_cselib)
1616             cselib_finish ();
1617           return;
1618         }
1619     }
1620   gcc_unreachable ();
1621 }
1622 \f
1623
1624 /* The following function adds forward dependence (FROM, TO) with
1625    given DEP_TYPE.  The forward dependence should be not exist before.  */
1626
1627 void
1628 add_forw_dep (rtx to, rtx link)
1629 {
1630   rtx new_link, from;
1631
1632   from = XEXP (link, 0);
1633
1634 #ifdef ENABLE_CHECKING
1635   /* If add_dependence is working properly there should never
1636      be notes, deleted insns or duplicates in the backward
1637      links.  Thus we need not check for them here.
1638
1639      However, if we have enabled checking we might as well go
1640      ahead and verify that add_dependence worked properly.  */
1641   gcc_assert (INSN_P (from));
1642   gcc_assert (!INSN_DELETED_P (from));
1643   if (true_dependency_cache)
1644     {
1645       gcc_assert (!bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
1646                                  INSN_LUID (to)));
1647       bitmap_set_bit (&forward_dependency_cache[INSN_LUID (from)],
1648                       INSN_LUID (to));
1649     }
1650   else
1651     gcc_assert (!find_insn_list (to, INSN_DEPEND (from)));
1652 #endif
1653
1654   if (!(current_sched_info->flags & USE_DEPS_LIST))
1655     new_link = alloc_INSN_LIST (to, INSN_DEPEND (from));
1656   else
1657     new_link = alloc_DEPS_LIST (to, INSN_DEPEND (from), DEP_STATUS (link));
1658
1659   PUT_REG_NOTE_KIND (new_link, REG_NOTE_KIND (link));
1660
1661   INSN_DEPEND (from) = new_link;
1662   INSN_DEP_COUNT (to) += 1;
1663 }
1664
1665 /* Examine insns in the range [ HEAD, TAIL ] and Use the backward
1666    dependences from LOG_LINKS to build forward dependences in
1667    INSN_DEPEND.  */
1668
1669 void
1670 compute_forward_dependences (rtx head, rtx tail)
1671 {
1672   rtx insn;
1673   rtx next_tail;
1674
1675   next_tail = NEXT_INSN (tail);
1676   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1677     {
1678       rtx link;
1679
1680       if (! INSN_P (insn))
1681         continue;
1682
1683       if (current_sched_info->flags & DO_SPECULATION)
1684         {
1685           rtx new = 0, link, next;
1686
1687           for (link = LOG_LINKS (insn); link; link = next)
1688             {
1689               next = XEXP (link, 1);
1690               adjust_add_sorted_back_dep (insn, link, &new);
1691             }
1692
1693           LOG_LINKS (insn) = new;
1694         }
1695
1696       for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
1697         add_forw_dep (insn, link);
1698     }
1699 }
1700 \f
1701 /* Initialize variables for region data dependence analysis.
1702    n_bbs is the number of region blocks.  */
1703
1704 void
1705 init_deps (struct deps *deps)
1706 {
1707   int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
1708
1709   deps->max_reg = max_reg;
1710   deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
1711   INIT_REG_SET (&deps->reg_last_in_use);
1712   INIT_REG_SET (&deps->reg_conditional_sets);
1713
1714   deps->pending_read_insns = 0;
1715   deps->pending_read_mems = 0;
1716   deps->pending_write_insns = 0;
1717   deps->pending_write_mems = 0;
1718   deps->pending_lists_length = 0;
1719   deps->pending_flush_length = 0;
1720   deps->last_pending_memory_flush = 0;
1721   deps->last_function_call = 0;
1722   deps->sched_before_next_call = 0;
1723   deps->in_post_call_group_p = not_post_call;
1724   deps->libcall_block_tail_insn = 0;
1725 }
1726
1727 /* Free insn lists found in DEPS.  */
1728
1729 void
1730 free_deps (struct deps *deps)
1731 {
1732   unsigned i;
1733   reg_set_iterator rsi;
1734
1735   free_INSN_LIST_list (&deps->pending_read_insns);
1736   free_EXPR_LIST_list (&deps->pending_read_mems);
1737   free_INSN_LIST_list (&deps->pending_write_insns);
1738   free_EXPR_LIST_list (&deps->pending_write_mems);
1739   free_INSN_LIST_list (&deps->last_pending_memory_flush);
1740
1741   /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
1742      times.  For a testcase with 42000 regs and 8000 small basic blocks,
1743      this loop accounted for nearly 60% (84 sec) of the total -O2 runtime.  */
1744   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1745     {
1746       struct deps_reg *reg_last = &deps->reg_last[i];
1747       if (reg_last->uses)
1748         free_INSN_LIST_list (&reg_last->uses);
1749       if (reg_last->sets)
1750         free_INSN_LIST_list (&reg_last->sets);
1751       if (reg_last->clobbers)
1752         free_INSN_LIST_list (&reg_last->clobbers);
1753     }
1754   CLEAR_REG_SET (&deps->reg_last_in_use);
1755   CLEAR_REG_SET (&deps->reg_conditional_sets);
1756
1757   free (deps->reg_last);
1758 }
1759
1760 /* If it is profitable to use them, initialize caches for tracking
1761    dependency information.  LUID is the number of insns to be scheduled,
1762    it is used in the estimate of profitability.  */
1763
1764 void
1765 init_dependency_caches (int luid)
1766 {
1767   /* ?!? We could save some memory by computing a per-region luid mapping
1768      which could reduce both the number of vectors in the cache and the size
1769      of each vector.  Instead we just avoid the cache entirely unless the
1770      average number of instructions in a basic block is very high.  See
1771      the comment before the declaration of true_dependency_cache for
1772      what we consider "very high".  */
1773   if (luid / n_basic_blocks > 100 * 5)
1774     {
1775       cache_size = 0;
1776       extend_dependency_caches (luid, true);
1777     }
1778 }
1779
1780 /* Create or extend (depending on CREATE_P) dependency caches to
1781    size N.  */
1782 void
1783 extend_dependency_caches (int n, bool create_p)
1784 {
1785   if (create_p || true_dependency_cache)
1786     {
1787       int i, luid = cache_size + n;
1788
1789       true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
1790                                           luid);
1791       output_dependency_cache = XRESIZEVEC (bitmap_head,
1792                                             output_dependency_cache, luid);
1793       anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
1794                                           luid);
1795 #ifdef ENABLE_CHECKING
1796       forward_dependency_cache = XRESIZEVEC (bitmap_head,
1797                                              forward_dependency_cache, luid);
1798 #endif
1799       if (current_sched_info->flags & DO_SPECULATION)
1800         spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
1801                                             luid);
1802
1803       for (i = cache_size; i < luid; i++)
1804         {
1805           bitmap_initialize (&true_dependency_cache[i], 0);
1806           bitmap_initialize (&output_dependency_cache[i], 0);
1807           bitmap_initialize (&anti_dependency_cache[i], 0);
1808 #ifdef ENABLE_CHECKING
1809           bitmap_initialize (&forward_dependency_cache[i], 0);
1810 #endif
1811           if (current_sched_info->flags & DO_SPECULATION)
1812             bitmap_initialize (&spec_dependency_cache[i], 0);
1813         }
1814       cache_size = luid;
1815     }
1816 }
1817
1818 /* Free the caches allocated in init_dependency_caches.  */
1819
1820 void
1821 free_dependency_caches (void)
1822 {
1823   if (true_dependency_cache)
1824     {
1825       int i;
1826
1827       for (i = 0; i < cache_size; i++)
1828         {
1829           bitmap_clear (&true_dependency_cache[i]);
1830           bitmap_clear (&output_dependency_cache[i]);
1831           bitmap_clear (&anti_dependency_cache[i]);
1832 #ifdef ENABLE_CHECKING
1833           bitmap_clear (&forward_dependency_cache[i]);
1834 #endif
1835           if (current_sched_info->flags & DO_SPECULATION)
1836             bitmap_clear (&spec_dependency_cache[i]);
1837         }
1838       free (true_dependency_cache);
1839       true_dependency_cache = NULL;
1840       free (output_dependency_cache);
1841       output_dependency_cache = NULL;
1842       free (anti_dependency_cache);
1843       anti_dependency_cache = NULL;
1844 #ifdef ENABLE_CHECKING
1845       free (forward_dependency_cache);
1846       forward_dependency_cache = NULL;
1847 #endif
1848       if (current_sched_info->flags & DO_SPECULATION)
1849         {
1850           free (spec_dependency_cache);
1851           spec_dependency_cache = NULL;
1852         }
1853     }
1854 }
1855
1856 /* Initialize some global variables needed by the dependency analysis
1857    code.  */
1858
1859 void
1860 init_deps_global (void)
1861 {
1862   reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
1863   reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
1864   reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
1865   reg_pending_barrier = NOT_A_BARRIER;
1866 }
1867
1868 /* Free everything used by the dependency analysis code.  */
1869
1870 void
1871 finish_deps_global (void)
1872 {
1873   FREE_REG_SET (reg_pending_sets);
1874   FREE_REG_SET (reg_pending_clobbers);
1875   FREE_REG_SET (reg_pending_uses);
1876 }
1877
1878 /* Insert LINK into the dependence chain pointed to by LINKP and
1879    maintain the sort order.  */
1880 static void
1881 adjust_add_sorted_back_dep (rtx insn, rtx link, rtx *linkp)
1882 {
1883   gcc_assert (current_sched_info->flags & DO_SPECULATION);
1884
1885   /* If the insn cannot move speculatively, but the link is speculative,
1886      make it hard dependence.  */
1887   if (HAS_INTERNAL_DEP (insn)
1888       && (DEP_STATUS (link) & SPECULATIVE))
1889     {
1890       DEP_STATUS (link) &= ~SPECULATIVE;
1891
1892       if (true_dependency_cache)
1893         bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
1894                           INSN_LUID (XEXP (link, 0)));
1895     }
1896
1897   /* Non-speculative links go at the head of LOG_LINKS, followed by
1898      speculative links.  */
1899   if (DEP_STATUS (link) & SPECULATIVE)
1900     while (*linkp && !(DEP_STATUS (*linkp) & SPECULATIVE))
1901       linkp = &XEXP (*linkp, 1);
1902
1903   XEXP (link, 1) = *linkp;
1904   *linkp = link;
1905 }
1906
1907 /* Move the dependence pointed to by LINKP to the back dependencies
1908    of INSN, and also add this dependence to the forward ones.  All LOG_LINKS,
1909    except one pointed to by LINKP, must be sorted.  */
1910 static void
1911 adjust_back_add_forw_dep (rtx insn, rtx *linkp)
1912 {
1913   rtx link;
1914
1915   gcc_assert (current_sched_info->flags & DO_SPECULATION);
1916
1917   link = *linkp;
1918   *linkp = XEXP (*linkp, 1);
1919
1920   adjust_add_sorted_back_dep (insn, link, &LOG_LINKS (insn));
1921   add_forw_dep (insn, link);
1922 }
1923
1924 /* Remove forward dependence ELEM from the DEPS_LIST of INSN.  */
1925 static void
1926 delete_forw_dep (rtx insn, rtx elem)
1927 {
1928   gcc_assert (current_sched_info->flags & DO_SPECULATION);
1929
1930 #ifdef ENABLE_CHECKING
1931   if (true_dependency_cache)
1932     bitmap_clear_bit (&forward_dependency_cache[INSN_LUID (elem)],
1933                       INSN_LUID (insn));
1934 #endif
1935
1936   remove_free_DEPS_LIST_elem (insn, &INSN_DEPEND (elem));
1937   INSN_DEP_COUNT (insn)--;
1938 }
1939
1940 /* Estimate the weakness of dependence between MEM1 and MEM2.  */
1941 static dw_t
1942 estimate_dep_weak (rtx mem1, rtx mem2)
1943 {
1944   rtx r1, r2;
1945
1946   if (mem1 == mem2)
1947     /* MEMs are the same - don't speculate.  */
1948     return MIN_DEP_WEAK;
1949
1950   r1 = XEXP (mem1, 0);
1951   r2 = XEXP (mem2, 0);
1952
1953   if (r1 == r2
1954       || (REG_P (r1) && REG_P (r2)
1955           && REGNO (r1) == REGNO (r2)))
1956     /* Again, MEMs are the same.  */
1957     return MIN_DEP_WEAK;
1958   else if ((REG_P (r1) && !REG_P (r2))
1959            || (!REG_P (r1) && REG_P (r2)))
1960     /* Different addressing modes - reason to be more speculative,
1961        than usual.  */
1962     return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
1963   else
1964     /* We can't say anything about the dependence.  */
1965     return UNCERTAIN_DEP_WEAK;
1966 }
1967
1968 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
1969    This function can handle same INSN and ELEM (INSN == ELEM).
1970    It is a convenience wrapper.  */
1971 void
1972 add_dependence (rtx insn, rtx elem, enum reg_note dep_type)
1973 {
1974   ds_t ds;
1975
1976   if (dep_type == REG_DEP_TRUE)
1977     ds = DEP_TRUE;
1978   else if (dep_type == REG_DEP_OUTPUT)
1979     ds = DEP_OUTPUT;
1980   else if (dep_type == REG_DEP_ANTI)
1981     ds = DEP_ANTI;
1982   else
1983     gcc_unreachable ();
1984
1985   maybe_add_or_update_back_dep_1 (insn, elem, dep_type, ds, 0, 0, 0);
1986 }
1987
1988 /* Add or update backward dependence between INSN and ELEM
1989    with given type DEP_TYPE and dep_status DS.
1990    This function is a convenience wrapper.  */
1991 enum DEPS_ADJUST_RESULT
1992 add_or_update_back_dep (rtx insn, rtx elem, enum reg_note dep_type, ds_t ds)
1993 {
1994   return add_or_update_back_dep_1 (insn, elem, dep_type, ds, 0, 0, 0);
1995 }
1996
1997 /* Add or update both backward and forward dependencies between INSN and ELEM
1998    with given type DEP_TYPE and dep_status DS.  */
1999 void
2000 add_or_update_back_forw_dep (rtx insn, rtx elem, enum reg_note dep_type,
2001                              ds_t ds)
2002 {
2003   enum DEPS_ADJUST_RESULT res;
2004   rtx *linkp;
2005
2006   res = add_or_update_back_dep_1 (insn, elem, dep_type, ds, 0, 0, &linkp);
2007
2008   if (res == DEP_CHANGED || res == DEP_CREATED)
2009     {
2010       if (res == DEP_CHANGED)
2011         delete_forw_dep (insn, elem);
2012       else if (res == DEP_CREATED)
2013         linkp = &LOG_LINKS (insn);
2014
2015       adjust_back_add_forw_dep (insn, linkp);
2016     }
2017 }
2018
2019 /* Add both backward and forward dependencies between INSN and ELEM
2020    with given type DEP_TYPE and dep_status DS.  */
2021 void
2022 add_back_forw_dep (rtx insn, rtx elem, enum reg_note dep_type, ds_t ds)
2023 {
2024   add_back_dep (insn, elem, dep_type, ds);
2025   adjust_back_add_forw_dep (insn, &LOG_LINKS (insn));
2026 }
2027
2028 /* Remove both backward and forward dependencies between INSN and ELEM.  */
2029 void
2030 delete_back_forw_dep (rtx insn, rtx elem)
2031 {
2032   gcc_assert (current_sched_info->flags & DO_SPECULATION);
2033
2034   if (true_dependency_cache != NULL)
2035     {
2036       bitmap_clear_bit (&true_dependency_cache[INSN_LUID (insn)],
2037                         INSN_LUID (elem));
2038       bitmap_clear_bit (&anti_dependency_cache[INSN_LUID (insn)],
2039                         INSN_LUID (elem));
2040       bitmap_clear_bit (&output_dependency_cache[INSN_LUID (insn)],
2041                         INSN_LUID (elem));
2042       bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
2043                         INSN_LUID (elem));
2044     }
2045
2046   remove_free_DEPS_LIST_elem (elem, &LOG_LINKS (insn));
2047   delete_forw_dep (insn, elem);
2048 }
2049
2050 /* Return weakness of speculative type TYPE in the dep_status DS.  */
2051 dw_t
2052 get_dep_weak (ds_t ds, ds_t type)
2053 {
2054   ds = ds & type;
2055   switch (type)
2056     {
2057     case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
2058     case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
2059     case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
2060     case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
2061     default: gcc_unreachable ();
2062     }
2063
2064   gcc_assert (MIN_DEP_WEAK <= ds && ds <= MAX_DEP_WEAK);
2065   return (dw_t) ds;
2066 }
2067
2068 /* Return the dep_status, which has the same parameters as DS, except for
2069    speculative type TYPE, that will have weakness DW.  */
2070 ds_t
2071 set_dep_weak (ds_t ds, ds_t type, dw_t dw)
2072 {
2073   gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
2074
2075   ds &= ~type;
2076   switch (type)
2077     {
2078     case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
2079     case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
2080     case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
2081     case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
2082     default: gcc_unreachable ();
2083     }
2084   return ds;
2085 }
2086
2087 /* Return the join of two dep_statuses DS1 and DS2.  */
2088 ds_t
2089 ds_merge (ds_t ds1, ds_t ds2)
2090 {
2091   ds_t ds, t;
2092
2093   gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
2094
2095   ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
2096
2097   t = FIRST_SPEC_TYPE;
2098   do
2099     {
2100       if ((ds1 & t) && !(ds2 & t))
2101         ds |= ds1 & t;
2102       else if (!(ds1 & t) && (ds2 & t))
2103         ds |= ds2 & t;
2104       else if ((ds1 & t) && (ds2 & t))
2105         {
2106           ds_t dw;
2107
2108           dw = ((ds_t) get_dep_weak (ds1, t)) * ((ds_t) get_dep_weak (ds2, t));
2109           dw /= MAX_DEP_WEAK;
2110           if (dw < MIN_DEP_WEAK)
2111             dw = MIN_DEP_WEAK;
2112
2113           ds = set_dep_weak (ds, t, (dw_t) dw);
2114         }
2115
2116       if (t == LAST_SPEC_TYPE)
2117         break;
2118       t <<= SPEC_TYPE_SHIFT;
2119     }
2120   while (1);
2121
2122   return ds;
2123 }
2124
2125 #ifdef INSN_SCHEDULING
2126 #ifdef ENABLE_CHECKING
2127 /* Verify that dependence type and status are consistent.
2128    If RELAXED_P is true, then skip dep_weakness checks.  */
2129 static void
2130 check_dep_status (enum reg_note dt, ds_t ds, bool relaxed_p)
2131 {
2132   /* Check that dependence type contains the same bits as the status.  */
2133   if (dt == REG_DEP_TRUE)
2134     gcc_assert (ds & DEP_TRUE);
2135   else if (dt == REG_DEP_OUTPUT)
2136     gcc_assert ((ds & DEP_OUTPUT)
2137                 && !(ds & DEP_TRUE));
2138   else
2139     gcc_assert ((dt == REG_DEP_ANTI)
2140                 && (ds & DEP_ANTI)
2141                 && !(ds & (DEP_OUTPUT | DEP_TRUE)));
2142
2143   /* HARD_DEP can not appear in dep_status of a link.  */
2144   gcc_assert (!(ds & HARD_DEP));
2145
2146   /* Check that dependence status is set correctly when speculation is not
2147      supported.  */
2148   if (!(current_sched_info->flags & DO_SPECULATION))
2149     gcc_assert (!(ds & SPECULATIVE));
2150   else if (ds & SPECULATIVE)
2151     {
2152       if (!relaxed_p)
2153         {
2154           ds_t type = FIRST_SPEC_TYPE;
2155
2156           /* Check that dependence weakness is in proper range.  */
2157           do
2158             {
2159               if (ds & type)
2160                 get_dep_weak (ds, type);
2161
2162               if (type == LAST_SPEC_TYPE)
2163                 break;
2164               type <<= SPEC_TYPE_SHIFT;
2165             }
2166           while (1);
2167         }
2168
2169       if (ds & BEGIN_SPEC)
2170         {
2171           /* Only true dependence can be data speculative.  */
2172           if (ds & BEGIN_DATA)
2173             gcc_assert (ds & DEP_TRUE);
2174
2175           /* Control dependencies in the insn scheduler are represented by
2176              anti-dependencies, therefore only anti dependence can be
2177              control speculative.  */
2178           if (ds & BEGIN_CONTROL)
2179             gcc_assert (ds & DEP_ANTI);
2180         }
2181       else
2182         {
2183           /* Subsequent speculations should resolve true dependencies.  */
2184           gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
2185         }
2186
2187       /* Check that true and anti dependencies can't have other speculative
2188          statuses.  */
2189       if (ds & DEP_TRUE)
2190         gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
2191       /* An output dependence can't be speculative at all.  */
2192       gcc_assert (!(ds & DEP_OUTPUT));
2193       if (ds & DEP_ANTI)
2194         gcc_assert (ds & BEGIN_CONTROL);
2195     }
2196 }
2197 #endif
2198 #endif