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