gcc/sched-deps.c

   1 /* Instruction scheduling pass.  This file computes dependencies between
   2    instructions.
   3    Copyright (C) 1992-2014 Free Software Foundation, Inc.
   4    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
   5    and currently maintained by, Jim Wilson (wilson@cygnus.com)
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify it under
  10 the terms of the GNU General Public License as published by the Free
  11 Software Foundation; either version 3, or (at your option) any later
  12 version.
  13
  14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  17 for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GCC; see the file COPYING3.  If not see
  21 <http://www.gnu.org/licenses/>.  */
  22 \f
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "diagnostic-core.h"
  28 #include "rtl.h"
  29 #include "tree.h"               /* FIXME: Used by call_may_noreturn_p.  */
  30 #include "tm_p.h"
  31 #include "hard-reg-set.h"
  32 #include "regs.h"
  33 #include "function.h"
  34 #include "flags.h"
  35 #include "insn-config.h"
  36 #include "insn-attr.h"
  37 #include "except.h"
  38 #include "recog.h"
  39 #include "emit-rtl.h"
  40 #include "sched-int.h"
  41 #include "params.h"
  42 #include "cselib.h"
  43 #include "ira.h"
  44 #include "target.h"
  45
  46 #ifdef INSN_SCHEDULING
  47
  48 #ifdef ENABLE_CHECKING
  49 #define CHECK (true)
  50 #else
  51 #define CHECK (false)
  52 #endif
  53
  54 /* Holds current parameters for the dependency analyzer.  */
  55 struct sched_deps_info_def *sched_deps_info;
  56
  57 /* The data is specific to the Haifa scheduler.  */
  58 vec<haifa_deps_insn_data_def>
  59     h_d_i_d = vNULL;
  60
  61 /* Return the major type present in the DS.  */
  62 enum reg_note
  63 ds_to_dk (ds_t ds)
  64 {
  65   if (ds & DEP_TRUE)
  66     return REG_DEP_TRUE;
  67
  68   if (ds & DEP_OUTPUT)
  69     return REG_DEP_OUTPUT;
  70
  71   if (ds & DEP_CONTROL)
  72     return REG_DEP_CONTROL;
  73
  74   gcc_assert (ds & DEP_ANTI);
  75
  76   return REG_DEP_ANTI;
  77 }
  78
  79 /* Return equivalent dep_status.  */
  80 ds_t
  81 dk_to_ds (enum reg_note dk)
  82 {
  83   switch (dk)
  84     {
  85     case REG_DEP_TRUE:
  86       return DEP_TRUE;
  87
  88     case REG_DEP_OUTPUT:
  89       return DEP_OUTPUT;
  90
  91     case REG_DEP_CONTROL:
  92       return DEP_CONTROL;
  93
  94     default:
  95       gcc_assert (dk == REG_DEP_ANTI);
  96       return DEP_ANTI;
  97     }
  98 }
  99
 100 /* Functions to operate with dependence information container - dep_t.  */
 101
 102 /* Init DEP with the arguments.  */
 103 void
 104 init_dep_1 (dep_t dep, rtx pro, rtx con, enum reg_note type, ds_t ds)
 105 {
 106   DEP_PRO (dep) = pro;
 107   DEP_CON (dep) = con;
 108   DEP_TYPE (dep) = type;
 109   DEP_STATUS (dep) = ds;
 110   DEP_COST (dep) = UNKNOWN_DEP_COST;
 111   DEP_NONREG (dep) = 0;
 112   DEP_MULTIPLE (dep) = 0;
 113   DEP_REPLACE (dep) = NULL;
 114 }
 115
 116 /* Init DEP with the arguments.
 117    While most of the scheduler (including targets) only need the major type
 118    of the dependency, it is convenient to hide full dep_status from them.  */
 119 void
 120 init_dep (dep_t dep, rtx pro, rtx con, enum reg_note kind)
 121 {
 122   ds_t ds;
 123
 124   if ((current_sched_info->flags & USE_DEPS_LIST))
 125     ds = dk_to_ds (kind);
 126   else
 127     ds = 0;
 128
 129   init_dep_1 (dep, pro, con, kind, ds);
 130 }
 131
 132 /* Make a copy of FROM in TO.  */
 133 static void
 134 copy_dep (dep_t to, dep_t from)
 135 {
 136   memcpy (to, from, sizeof (*to));
 137 }
 138
 139 static void dump_ds (FILE *, ds_t);
 140
 141 /* Define flags for dump_dep ().  */
 142
 143 /* Dump producer of the dependence.  */
 144 #define DUMP_DEP_PRO (2)
 145
 146 /* Dump consumer of the dependence.  */
 147 #define DUMP_DEP_CON (4)
 148
 149 /* Dump type of the dependence.  */
 150 #define DUMP_DEP_TYPE (8)
 151
 152 /* Dump status of the dependence.  */
 153 #define DUMP_DEP_STATUS (16)
 154
 155 /* Dump all information about the dependence.  */
 156 #define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE       \
 157                       |DUMP_DEP_STATUS)
 158
 159 /* Dump DEP to DUMP.
 160    FLAGS is a bit mask specifying what information about DEP needs
 161    to be printed.
 162    If FLAGS has the very first bit set, then dump all information about DEP
 163    and propagate this bit into the callee dump functions.  */
 164 static void
 165 dump_dep (FILE *dump, dep_t dep, int flags)
 166 {
 167   if (flags & 1)
 168     flags |= DUMP_DEP_ALL;
 169
 170   fprintf (dump, "<");
 171
 172   if (flags & DUMP_DEP_PRO)
 173     fprintf (dump, "%d; ", INSN_UID (DEP_PRO (dep)));
 174
 175   if (flags & DUMP_DEP_CON)
 176     fprintf (dump, "%d; ", INSN_UID (DEP_CON (dep)));
 177
 178   if (flags & DUMP_DEP_TYPE)
 179     {
 180       char t;
 181       enum reg_note type = DEP_TYPE (dep);
 182
 183       switch (type)
 184         {
 185         case REG_DEP_TRUE:
 186           t = 't';
 187           break;
 188
 189         case REG_DEP_OUTPUT:
 190           t = 'o';
 191           break;
 192
 193         case REG_DEP_CONTROL:
 194           t = 'c';
 195           break;
 196
 197         case REG_DEP_ANTI:
 198           t = 'a';
 199           break;
 200
 201         default:
 202           gcc_unreachable ();
 203           break;
 204         }
 205
 206       fprintf (dump, "%c; ", t);
 207     }
 208
 209   if (flags & DUMP_DEP_STATUS)
 210     {
 211       if (current_sched_info->flags & USE_DEPS_LIST)
 212         dump_ds (dump, DEP_STATUS (dep));
 213     }
 214
 215   fprintf (dump, ">");
 216 }
 217
 218 /* Default flags for dump_dep ().  */
 219 static int dump_dep_flags = (DUMP_DEP_PRO | DUMP_DEP_CON);
 220
 221 /* Dump all fields of DEP to STDERR.  */
 222 void
 223 sd_debug_dep (dep_t dep)
 224 {
 225   dump_dep (stderr, dep, 1);
 226   fprintf (stderr, "\n");
 227 }
 228
 229 /* Determine whether DEP is a dependency link of a non-debug insn on a
 230    debug insn.  */
 231
 232 static inline bool
 233 depl_on_debug_p (dep_link_t dep)
 234 {
 235   return (DEBUG_INSN_P (DEP_LINK_PRO (dep))
 236           && !DEBUG_INSN_P (DEP_LINK_CON (dep)));
 237 }
 238
 239 /* Functions to operate with a single link from the dependencies lists -
 240    dep_link_t.  */
 241
 242 /* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
 243    PREV_NEXT_P.  */
 244 static void
 245 attach_dep_link (dep_link_t l, dep_link_t *prev_nextp)
 246 {
 247   dep_link_t next = *prev_nextp;
 248
 249   gcc_assert (DEP_LINK_PREV_NEXTP (l) == NULL
 250               && DEP_LINK_NEXT (l) == NULL);
 251
 252   /* Init node being inserted.  */
 253   DEP_LINK_PREV_NEXTP (l) = prev_nextp;
 254   DEP_LINK_NEXT (l) = next;
 255
 256   /* Fix next node.  */
 257   if (next != NULL)
 258     {
 259       gcc_assert (DEP_LINK_PREV_NEXTP (next) == prev_nextp);
 260
 261       DEP_LINK_PREV_NEXTP (next) = &DEP_LINK_NEXT (l);
 262     }
 263
 264   /* Fix prev node.  */
 265   *prev_nextp = l;
 266 }
 267
 268 /* Add dep_link LINK to deps_list L.  */
 269 static void
 270 add_to_deps_list (dep_link_t link, deps_list_t l)
 271 {
 272   attach_dep_link (link, &DEPS_LIST_FIRST (l));
 273
 274   /* Don't count debug deps.  */
 275   if (!depl_on_debug_p (link))
 276     ++DEPS_LIST_N_LINKS (l);
 277 }
 278
 279 /* Detach dep_link L from the list.  */
 280 static void
 281 detach_dep_link (dep_link_t l)
 282 {
 283   dep_link_t *prev_nextp = DEP_LINK_PREV_NEXTP (l);
 284   dep_link_t next = DEP_LINK_NEXT (l);
 285
 286   *prev_nextp = next;
 287
 288   if (next != NULL)
 289     DEP_LINK_PREV_NEXTP (next) = prev_nextp;
 290
 291   DEP_LINK_PREV_NEXTP (l) = NULL;
 292   DEP_LINK_NEXT (l) = NULL;
 293 }
 294
 295 /* Remove link LINK from list LIST.  */
 296 static void
 297 remove_from_deps_list (dep_link_t link, deps_list_t list)
 298 {
 299   detach_dep_link (link);
 300
 301   /* Don't count debug deps.  */
 302   if (!depl_on_debug_p (link))
 303     --DEPS_LIST_N_LINKS (list);
 304 }
 305
 306 /* Move link LINK from list FROM to list TO.  */
 307 static void
 308 move_dep_link (dep_link_t link, deps_list_t from, deps_list_t to)
 309 {
 310   remove_from_deps_list (link, from);
 311   add_to_deps_list (link, to);
 312 }
 313
 314 /* Return true of LINK is not attached to any list.  */
 315 static bool
 316 dep_link_is_detached_p (dep_link_t link)
 317 {
 318   return DEP_LINK_PREV_NEXTP (link) == NULL;
 319 }
 320
 321 /* Pool to hold all dependency nodes (dep_node_t).  */
 322 static alloc_pool dn_pool;
 323
 324 /* Number of dep_nodes out there.  */
 325 static int dn_pool_diff = 0;
 326
 327 /* Create a dep_node.  */
 328 static dep_node_t
 329 create_dep_node (void)
 330 {
 331   dep_node_t n = (dep_node_t) pool_alloc (dn_pool);
 332   dep_link_t back = DEP_NODE_BACK (n);
 333   dep_link_t forw = DEP_NODE_FORW (n);
 334
 335   DEP_LINK_NODE (back) = n;
 336   DEP_LINK_NEXT (back) = NULL;
 337   DEP_LINK_PREV_NEXTP (back) = NULL;
 338
 339   DEP_LINK_NODE (forw) = n;
 340   DEP_LINK_NEXT (forw) = NULL;
 341   DEP_LINK_PREV_NEXTP (forw) = NULL;
 342
 343   ++dn_pool_diff;
 344
 345   return n;
 346 }
 347
 348 /* Delete dep_node N.  N must not be connected to any deps_list.  */
 349 static void
 350 delete_dep_node (dep_node_t n)
 351 {
 352   gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n))
 353               && dep_link_is_detached_p (DEP_NODE_FORW (n)));
 354
 355   XDELETE (DEP_REPLACE (DEP_NODE_DEP (n)));
 356
 357   --dn_pool_diff;
 358
 359   pool_free (dn_pool, n);
 360 }
 361
 362 /* Pool to hold dependencies lists (deps_list_t).  */
 363 static alloc_pool dl_pool;
 364
 365 /* Number of deps_lists out there.  */
 366 static int dl_pool_diff = 0;
 367
 368 /* Functions to operate with dependences lists - deps_list_t.  */
 369
 370 /* Return true if list L is empty.  */
 371 static bool
 372 deps_list_empty_p (deps_list_t l)
 373 {
 374   return DEPS_LIST_N_LINKS (l) == 0;
 375 }
 376
 377 /* Create a new deps_list.  */
 378 static deps_list_t
 379 create_deps_list (void)
 380 {
 381   deps_list_t l = (deps_list_t) pool_alloc (dl_pool);
 382
 383   DEPS_LIST_FIRST (l) = NULL;
 384   DEPS_LIST_N_LINKS (l) = 0;
 385
 386   ++dl_pool_diff;
 387   return l;
 388 }
 389
 390 /* Free deps_list L.  */
 391 static void
 392 free_deps_list (deps_list_t l)
 393 {
 394   gcc_assert (deps_list_empty_p (l));
 395
 396   --dl_pool_diff;
 397
 398   pool_free (dl_pool, l);
 399 }
 400
 401 /* Return true if there is no dep_nodes and deps_lists out there.
 402    After the region is scheduled all the dependency nodes and lists
 403    should [generally] be returned to pool.  */
 404 bool
 405 deps_pools_are_empty_p (void)
 406 {
 407   return dn_pool_diff == 0 && dl_pool_diff == 0;
 408 }
 409
 410 /* Remove all elements from L.  */
 411 static void
 412 clear_deps_list (deps_list_t l)
 413 {
 414   do
 415     {
 416       dep_link_t link = DEPS_LIST_FIRST (l);
 417
 418       if (link == NULL)
 419         break;
 420
 421       remove_from_deps_list (link, l);
 422     }
 423   while (1);
 424 }
 425
 426 /* Decide whether a dependency should be treated as a hard or a speculative
 427    dependency.  */
 428 static bool
 429 dep_spec_p (dep_t dep)
 430 {
 431   if (current_sched_info->flags & DO_SPECULATION)
 432     {
 433       if (DEP_STATUS (dep) & SPECULATIVE)
 434         return true;
 435     }
 436   if (current_sched_info->flags & DO_PREDICATION)
 437     {
 438       if (DEP_TYPE (dep) == REG_DEP_CONTROL)
 439         return true;
 440     }
 441   if (DEP_REPLACE (dep) != NULL)
 442     return true;
 443   return false;
 444 }
 445
 446 static regset reg_pending_sets;
 447 static regset reg_pending_clobbers;
 448 static regset reg_pending_uses;
 449 static regset reg_pending_control_uses;
 450 static enum reg_pending_barrier_mode reg_pending_barrier;
 451
 452 /* Hard registers implicitly clobbered or used (or may be implicitly
 453    clobbered or used) by the currently analyzed insn.  For example,
 454    insn in its constraint has one register class.  Even if there is
 455    currently no hard register in the insn, the particular hard
 456    register will be in the insn after reload pass because the
 457    constraint requires it.  */
 458 static HARD_REG_SET implicit_reg_pending_clobbers;
 459 static HARD_REG_SET implicit_reg_pending_uses;
 460
 461 /* To speed up the test for duplicate dependency links we keep a
 462    record of dependencies created by add_dependence when the average
 463    number of instructions in a basic block is very large.
 464
 465    Studies have shown that there is typically around 5 instructions between
 466    branches for typical C code.  So we can make a guess that the average
 467    basic block is approximately 5 instructions long; we will choose 100X
 468    the average size as a very large basic block.
 469
 470    Each insn has associated bitmaps for its dependencies.  Each bitmap
 471    has enough entries to represent a dependency on any other insn in
 472    the insn chain.  All bitmap for true dependencies cache is
 473    allocated then the rest two ones are also allocated.  */
 474 static bitmap_head *true_dependency_cache = NULL;
 475 static bitmap_head *output_dependency_cache = NULL;
 476 static bitmap_head *anti_dependency_cache = NULL;
 477 static bitmap_head *control_dependency_cache = NULL;
 478 static bitmap_head *spec_dependency_cache = NULL;
 479 static int cache_size;
 480
 481 /* True if we should mark added dependencies as a non-register deps.  */
 482 static bool mark_as_hard;
 483
 484 static int deps_may_trap_p (const_rtx);
 485 static void add_dependence_1 (rtx, rtx, enum reg_note);
 486 static void add_dependence_list (rtx, rtx, int, enum reg_note, bool);
 487 static void add_dependence_list_and_free (struct deps_desc *, rtx,
 488                                           rtx *, int, enum reg_note, bool);
 489 static void delete_all_dependences (rtx);
 490 static void chain_to_prev_insn (rtx);
 491
 492 static void flush_pending_lists (struct deps_desc *, rtx, int, int);
 493 static void sched_analyze_1 (struct deps_desc *, rtx, rtx);
 494 static void sched_analyze_2 (struct deps_desc *, rtx, rtx);
 495 static void sched_analyze_insn (struct deps_desc *, rtx, rtx);
 496
 497 static bool sched_has_condition_p (const_rtx);
 498 static int conditions_mutex_p (const_rtx, const_rtx, bool, bool);
 499
 500 static enum DEPS_ADJUST_RESULT maybe_add_or_update_dep_1 (dep_t, bool,
 501                                                           rtx, rtx);
 502 static enum DEPS_ADJUST_RESULT add_or_update_dep_1 (dep_t, bool, rtx, rtx);
 503
 504 #ifdef ENABLE_CHECKING
 505 static void check_dep (dep_t, bool);
 506 #endif
 507 \f
 508 /* Return nonzero if a load of the memory reference MEM can cause a trap.  */
 509
 510 static int
 511 deps_may_trap_p (const_rtx mem)
 512 {
 513   const_rtx addr = XEXP (mem, 0);
 514
 515   if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
 516     {
 517       const_rtx t = get_reg_known_value (REGNO (addr));
 518       if (t)
 519         addr = t;
 520     }
 521   return rtx_addr_can_trap_p (addr);
 522 }
 523 \f
 524
 525 /* Find the condition under which INSN is executed.  If REV is not NULL,
 526    it is set to TRUE when the returned comparison should be reversed
 527    to get the actual condition.  */
 528 static rtx
 529 sched_get_condition_with_rev_uncached (const_rtx insn, bool *rev)
 530 {
 531   rtx pat = PATTERN (insn);
 532   rtx src;
 533
 534   if (rev)
 535     *rev = false;
 536
 537   if (GET_CODE (pat) == COND_EXEC)
 538     return COND_EXEC_TEST (pat);
 539
 540   if (!any_condjump_p (insn) || !onlyjump_p (insn))
 541     return 0;
 542
 543   src = SET_SRC (pc_set (insn));
 544
 545   if (XEXP (src, 2) == pc_rtx)
 546     return XEXP (src, 0);
 547   else if (XEXP (src, 1) == pc_rtx)
 548     {
 549       rtx cond = XEXP (src, 0);
 550       enum rtx_code revcode = reversed_comparison_code (cond, insn);
 551
 552       if (revcode == UNKNOWN)
 553         return 0;
 554
 555       if (rev)
 556         *rev = true;
 557       return cond;
 558     }
 559
 560   return 0;
 561 }
 562
 563 /* Return the condition under which INSN does not execute (i.e.  the
 564    not-taken condition for a conditional branch), or NULL if we cannot
 565    find such a condition.  The caller should make a copy of the condition
 566    before using it.  */
 567 rtx
 568 sched_get_reverse_condition_uncached (const_rtx insn)
 569 {
 570   bool rev;
 571   rtx cond = sched_get_condition_with_rev_uncached (insn, &rev);
 572   if (cond == NULL_RTX)
 573     return cond;
 574   if (!rev)
 575     {
 576       enum rtx_code revcode = reversed_comparison_code (cond, insn);
 577       cond = gen_rtx_fmt_ee (revcode, GET_MODE (cond),
 578                              XEXP (cond, 0),
 579                              XEXP (cond, 1));
 580     }
 581   return cond;
 582 }
 583
 584 /* Caching variant of sched_get_condition_with_rev_uncached.
 585    We only do actual work the first time we come here for an insn; the
 586    results are cached in INSN_CACHED_COND and INSN_REVERSE_COND.  */
 587 static rtx
 588 sched_get_condition_with_rev (const_rtx insn, bool *rev)
 589 {
 590   bool tmp;
 591
 592   if (INSN_LUID (insn) == 0)
 593     return sched_get_condition_with_rev_uncached (insn, rev);
 594
 595   if (INSN_CACHED_COND (insn) == const_true_rtx)
 596     return NULL_RTX;
 597
 598   if (INSN_CACHED_COND (insn) != NULL_RTX)
 599     {
 600       if (rev)
 601         *rev = INSN_REVERSE_COND (insn);
 602       return INSN_CACHED_COND (insn);
 603     }
 604
 605   INSN_CACHED_COND (insn) = sched_get_condition_with_rev_uncached (insn, &tmp);
 606   INSN_REVERSE_COND (insn) = tmp;
 607
 608   if (INSN_CACHED_COND (insn) == NULL_RTX)
 609     {
 610       INSN_CACHED_COND (insn) = const_true_rtx;
 611       return NULL_RTX;
 612     }
 613
 614   if (rev)
 615     *rev = INSN_REVERSE_COND (insn);
 616   return INSN_CACHED_COND (insn);
 617 }
 618
 619 /* True when we can find a condition under which INSN is executed.  */
 620 static bool
 621 sched_has_condition_p (const_rtx insn)
 622 {
 623   return !! sched_get_condition_with_rev (insn, NULL);
 624 }
 625
 626 \f
 627
 628 /* Return nonzero if conditions COND1 and COND2 can never be both true.  */
 629 static int
 630 conditions_mutex_p (const_rtx cond1, const_rtx cond2, bool rev1, bool rev2)
 631 {
 632   if (COMPARISON_P (cond1)
 633       && COMPARISON_P (cond2)
 634       && GET_CODE (cond1) ==
 635           (rev1==rev2
 636           ? reversed_comparison_code (cond2, NULL)
 637           : GET_CODE (cond2))
 638       && rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
 639       && XEXP (cond1, 1) == XEXP (cond2, 1))
 640     return 1;
 641   return 0;
 642 }
 643
 644 /* Return true if insn1 and insn2 can never depend on one another because
 645    the conditions under which they are executed are mutually exclusive.  */
 646 bool
 647 sched_insns_conditions_mutex_p (const_rtx insn1, const_rtx insn2)
 648 {
 649   rtx cond1, cond2;
 650   bool rev1 = false, rev2 = false;
 651
 652   /* df doesn't handle conditional lifetimes entirely correctly;
 653      calls mess up the conditional lifetimes.  */
 654   if (!CALL_P (insn1) && !CALL_P (insn2))
 655     {
 656       cond1 = sched_get_condition_with_rev (insn1, &rev1);
 657       cond2 = sched_get_condition_with_rev (insn2, &rev2);
 658       if (cond1 && cond2
 659           && conditions_mutex_p (cond1, cond2, rev1, rev2)
 660           /* Make sure first instruction doesn't affect condition of second
 661              instruction if switched.  */
 662           && !modified_in_p (cond1, insn2)
 663           /* Make sure second instruction doesn't affect condition of first
 664              instruction if switched.  */
 665           && !modified_in_p (cond2, insn1))
 666         return true;
 667     }
 668   return false;
 669 }
 670 \f
 671
 672 /* Return true if INSN can potentially be speculated with type DS.  */
 673 bool
 674 sched_insn_is_legitimate_for_speculation_p (const_rtx insn, ds_t ds)
 675 {
 676   if (HAS_INTERNAL_DEP (insn))
 677     return false;
 678
 679   if (!NONJUMP_INSN_P (insn))
 680     return false;
 681
 682   if (SCHED_GROUP_P (insn))
 683     return false;
 684
 685   if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX (insn)))
 686     return false;
 687
 688   if (side_effects_p (PATTERN (insn)))
 689     return false;
 690
 691   if (ds & BE_IN_SPEC)
 692     /* The following instructions, which depend on a speculatively scheduled
 693        instruction, cannot be speculatively scheduled along.  */
 694     {
 695       if (may_trap_or_fault_p (PATTERN (insn)))
 696         /* If instruction might fault, it cannot be speculatively scheduled.
 697            For control speculation it's obvious why and for data speculation
 698            it's because the insn might get wrong input if speculation
 699            wasn't successful.  */
 700         return false;
 701
 702       if ((ds & BE_IN_DATA)
 703           && sched_has_condition_p (insn))
 704         /* If this is a predicated instruction, then it cannot be
 705            speculatively scheduled.  See PR35659.  */
 706         return false;
 707     }
 708
 709   return true;
 710 }
 711
 712 /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
 713    initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
 714    and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
 715    This function is used to switch sd_iterator to the next list.
 716    !!! For internal use only.  Might consider moving it to sched-int.h.  */
 717 void
 718 sd_next_list (const_rtx insn, sd_list_types_def *types_ptr,
 719               deps_list_t *list_ptr, bool *resolved_p_ptr)
 720 {
 721   sd_list_types_def types = *types_ptr;
 722
 723   if (types & SD_LIST_HARD_BACK)
 724     {
 725       *list_ptr = INSN_HARD_BACK_DEPS (insn);
 726       *resolved_p_ptr = false;
 727       *types_ptr = types & ~SD_LIST_HARD_BACK;
 728     }
 729   else if (types & SD_LIST_SPEC_BACK)
 730     {
 731       *list_ptr = INSN_SPEC_BACK_DEPS (insn);
 732       *resolved_p_ptr = false;
 733       *types_ptr = types & ~SD_LIST_SPEC_BACK;
 734     }
 735   else if (types & SD_LIST_FORW)
 736     {
 737       *list_ptr = INSN_FORW_DEPS (insn);
 738       *resolved_p_ptr = false;
 739       *types_ptr = types & ~SD_LIST_FORW;
 740     }
 741   else if (types & SD_LIST_RES_BACK)
 742     {
 743       *list_ptr = INSN_RESOLVED_BACK_DEPS (insn);
 744       *resolved_p_ptr = true;
 745       *types_ptr = types & ~SD_LIST_RES_BACK;
 746     }
 747   else if (types & SD_LIST_RES_FORW)
 748     {
 749       *list_ptr = INSN_RESOLVED_FORW_DEPS (insn);
 750       *resolved_p_ptr = true;
 751       *types_ptr = types & ~SD_LIST_RES_FORW;
 752     }
 753   else
 754     {
 755       *list_ptr = NULL;
 756       *resolved_p_ptr = false;
 757       *types_ptr = SD_LIST_NONE;
 758     }
 759 }
 760
 761 /* Return the summary size of INSN's lists defined by LIST_TYPES.  */
 762 int
 763 sd_lists_size (const_rtx insn, sd_list_types_def list_types)
 764 {
 765   int size = 0;
 766
 767   while (list_types != SD_LIST_NONE)
 768     {
 769       deps_list_t list;
 770       bool resolved_p;
 771
 772       sd_next_list (insn, &list_types, &list, &resolved_p);
 773       if (list)
 774         size += DEPS_LIST_N_LINKS (list);
 775     }
 776
 777   return size;
 778 }
 779
 780 /* Return true if INSN's lists defined by LIST_TYPES are all empty.  */
 781
 782 bool
 783 sd_lists_empty_p (const_rtx insn, sd_list_types_def list_types)
 784 {
 785   while (list_types != SD_LIST_NONE)
 786     {
 787       deps_list_t list;
 788       bool resolved_p;
 789
 790       sd_next_list (insn, &list_types, &list, &resolved_p);
 791       if (!deps_list_empty_p (list))
 792         return false;
 793     }
 794
 795   return true;
 796 }
 797
 798 /* Initialize data for INSN.  */
 799 void
 800 sd_init_insn (rtx insn)
 801 {
 802   INSN_HARD_BACK_DEPS (insn) = create_deps_list ();
 803   INSN_SPEC_BACK_DEPS (insn) = create_deps_list ();
 804   INSN_RESOLVED_BACK_DEPS (insn) = create_deps_list ();
 805   INSN_FORW_DEPS (insn) = create_deps_list ();
 806   INSN_RESOLVED_FORW_DEPS (insn) = create_deps_list ();
 807
 808   /* ??? It would be nice to allocate dependency caches here.  */
 809 }
 810
 811 /* Free data for INSN.  */
 812 void
 813 sd_finish_insn (rtx insn)
 814 {
 815   /* ??? It would be nice to deallocate dependency caches here.  */
 816
 817   free_deps_list (INSN_HARD_BACK_DEPS (insn));
 818   INSN_HARD_BACK_DEPS (insn) = NULL;
 819
 820   free_deps_list (INSN_SPEC_BACK_DEPS (insn));
 821   INSN_SPEC_BACK_DEPS (insn) = NULL;
 822
 823   free_deps_list (INSN_RESOLVED_BACK_DEPS (insn));
 824   INSN_RESOLVED_BACK_DEPS (insn) = NULL;
 825
 826   free_deps_list (INSN_FORW_DEPS (insn));
 827   INSN_FORW_DEPS (insn) = NULL;
 828
 829   free_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
 830   INSN_RESOLVED_FORW_DEPS (insn) = NULL;
 831 }
 832
 833 /* Find a dependency between producer PRO and consumer CON.
 834    Search through resolved dependency lists if RESOLVED_P is true.
 835    If no such dependency is found return NULL,
 836    otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
 837    with an iterator pointing to it.  */
 838 static dep_t
 839 sd_find_dep_between_no_cache (rtx pro, rtx con, bool resolved_p,
 840                               sd_iterator_def *sd_it_ptr)
 841 {
 842   sd_list_types_def pro_list_type;
 843   sd_list_types_def con_list_type;
 844   sd_iterator_def sd_it;
 845   dep_t dep;
 846   bool found_p = false;
 847
 848   if (resolved_p)
 849     {
 850       pro_list_type = SD_LIST_RES_FORW;
 851       con_list_type = SD_LIST_RES_BACK;
 852     }
 853   else
 854     {
 855       pro_list_type = SD_LIST_FORW;
 856       con_list_type = SD_LIST_BACK;
 857     }
 858
 859   /* Walk through either back list of INSN or forw list of ELEM
 860      depending on which one is shorter.  */
 861   if (sd_lists_size (con, con_list_type) < sd_lists_size (pro, pro_list_type))
 862     {
 863       /* Find the dep_link with producer PRO in consumer's back_deps.  */
 864       FOR_EACH_DEP (con, con_list_type, sd_it, dep)
 865         if (DEP_PRO (dep) == pro)
 866           {
 867             found_p = true;
 868             break;
 869           }
 870     }
 871   else
 872     {
 873       /* Find the dep_link with consumer CON in producer's forw_deps.  */
 874       FOR_EACH_DEP (pro, pro_list_type, sd_it, dep)
 875         if (DEP_CON (dep) == con)
 876           {
 877             found_p = true;
 878             break;
 879           }
 880     }
 881
 882   if (found_p)
 883     {
 884       if (sd_it_ptr != NULL)
 885         *sd_it_ptr = sd_it;
 886
 887       return dep;
 888     }
 889
 890   return NULL;
 891 }
 892
 893 /* Find a dependency between producer PRO and consumer CON.
 894    Use dependency [if available] to check if dependency is present at all.
 895    Search through resolved dependency lists if RESOLVED_P is true.
 896    If the dependency or NULL if none found.  */
 897 dep_t
 898 sd_find_dep_between (rtx pro, rtx con, bool resolved_p)
 899 {
 900   if (true_dependency_cache != NULL)
 901     /* Avoiding the list walk below can cut compile times dramatically
 902        for some code.  */
 903     {
 904       int elem_luid = INSN_LUID (pro);
 905       int insn_luid = INSN_LUID (con);
 906
 907       if (!bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid)
 908           && !bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid)
 909           && !bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid)
 910           && !bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
 911         return NULL;
 912     }
 913
 914   return sd_find_dep_between_no_cache (pro, con, resolved_p, NULL);
 915 }
 916
 917 /* Add or update  a dependence described by DEP.
 918    MEM1 and MEM2, if non-null, correspond to memory locations in case of
 919    data speculation.
 920
 921    The function returns a value indicating if an old entry has been changed
 922    or a new entry has been added to insn's backward deps.
 923
 924    This function merely checks if producer and consumer is the same insn
 925    and doesn't create a dep in this case.  Actual manipulation of
 926    dependence data structures is performed in add_or_update_dep_1.  */
 927 static enum DEPS_ADJUST_RESULT
 928 maybe_add_or_update_dep_1 (dep_t dep, bool resolved_p, rtx mem1, rtx mem2)
 929 {
 930   rtx elem = DEP_PRO (dep);
 931   rtx insn = DEP_CON (dep);
 932
 933   gcc_assert (INSN_P (insn) && INSN_P (elem));
 934
 935   /* Don't depend an insn on itself.  */
 936   if (insn == elem)
 937     {
 938       if (sched_deps_info->generate_spec_deps)
 939         /* INSN has an internal dependence, which we can't overcome.  */
 940         HAS_INTERNAL_DEP (insn) = 1;
 941
 942       return DEP_NODEP;
 943     }
 944
 945   return add_or_update_dep_1 (dep, resolved_p, mem1, mem2);
 946 }
 947
 948 /* Ask dependency caches what needs to be done for dependence DEP.
 949    Return DEP_CREATED if new dependence should be created and there is no
 950    need to try to find one searching the dependencies lists.
 951    Return DEP_PRESENT if there already is a dependence described by DEP and
 952    hence nothing is to be done.
 953    Return DEP_CHANGED if there already is a dependence, but it should be
 954    updated to incorporate additional information from DEP.  */
 955 static enum DEPS_ADJUST_RESULT
 956 ask_dependency_caches (dep_t dep)
 957 {
 958   int elem_luid = INSN_LUID (DEP_PRO (dep));
 959   int insn_luid = INSN_LUID (DEP_CON (dep));
 960
 961   gcc_assert (true_dependency_cache != NULL
 962               && output_dependency_cache != NULL
 963               && anti_dependency_cache != NULL
 964               && control_dependency_cache != NULL);
 965
 966   if (!(current_sched_info->flags & USE_DEPS_LIST))
 967     {
 968       enum reg_note present_dep_type;
 969
 970       if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
 971         present_dep_type = REG_DEP_TRUE;
 972       else if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
 973         present_dep_type = REG_DEP_OUTPUT;
 974       else if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
 975         present_dep_type = REG_DEP_ANTI;
 976       else if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
 977         present_dep_type = REG_DEP_CONTROL;
 978       else
 979         /* There is no existing dep so it should be created.  */
 980         return DEP_CREATED;
 981
 982       if ((int) DEP_TYPE (dep) >= (int) present_dep_type)
 983         /* DEP does not add anything to the existing dependence.  */
 984         return DEP_PRESENT;
 985     }
 986   else
 987     {
 988       ds_t present_dep_types = 0;
 989
 990       if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
 991         present_dep_types |= DEP_TRUE;
 992       if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
 993         present_dep_types |= DEP_OUTPUT;
 994       if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
 995         present_dep_types |= DEP_ANTI;
 996       if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
 997         present_dep_types |= DEP_CONTROL;
 998
 999       if (present_dep_types == 0)
1000         /* There is no existing dep so it should be created.  */
1001         return DEP_CREATED;
1002
1003       if (!(current_sched_info->flags & DO_SPECULATION)
1004           || !bitmap_bit_p (&spec_dependency_cache[insn_luid], elem_luid))
1005         {
1006           if ((present_dep_types | (DEP_STATUS (dep) & DEP_TYPES))
1007               == present_dep_types)
1008             /* DEP does not add anything to the existing dependence.  */
1009             return DEP_PRESENT;
1010         }
1011       else
1012         {
1013           /* Only true dependencies can be data speculative and
1014              only anti dependencies can be control speculative.  */
1015           gcc_assert ((present_dep_types & (DEP_TRUE | DEP_ANTI))
1016                       == present_dep_types);
1017
1018           /* if (DEP is SPECULATIVE) then
1019              ..we should update DEP_STATUS
1020              else
1021              ..we should reset existing dep to non-speculative.  */
1022         }
1023     }
1024
1025   return DEP_CHANGED;
1026 }
1027
1028 /* Set dependency caches according to DEP.  */
1029 static void
1030 set_dependency_caches (dep_t dep)
1031 {
1032   int elem_luid = INSN_LUID (DEP_PRO (dep));
1033   int insn_luid = INSN_LUID (DEP_CON (dep));
1034
1035   if (!(current_sched_info->flags & USE_DEPS_LIST))
1036     {
1037       switch (DEP_TYPE (dep))
1038         {
1039         case REG_DEP_TRUE:
1040           bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
1041           break;
1042
1043         case REG_DEP_OUTPUT:
1044           bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
1045           break;
1046
1047         case REG_DEP_ANTI:
1048           bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
1049           break;
1050
1051         case REG_DEP_CONTROL:
1052           bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid);
1053           break;
1054
1055         default:
1056           gcc_unreachable ();
1057         }
1058     }
1059   else
1060     {
1061       ds_t ds = DEP_STATUS (dep);
1062
1063       if (ds & DEP_TRUE)
1064         bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
1065       if (ds & DEP_OUTPUT)
1066         bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
1067       if (ds & DEP_ANTI)
1068         bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
1069       if (ds & DEP_CONTROL)
1070         bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid);
1071
1072       if (ds & SPECULATIVE)
1073         {
1074           gcc_assert (current_sched_info->flags & DO_SPECULATION);
1075           bitmap_set_bit (&spec_dependency_cache[insn_luid], elem_luid);
1076         }
1077     }
1078 }
1079
1080 /* Type of dependence DEP have changed from OLD_TYPE.  Update dependency
1081    caches accordingly.  */
1082 static void
1083 update_dependency_caches (dep_t dep, enum reg_note old_type)
1084 {
1085   int elem_luid = INSN_LUID (DEP_PRO (dep));
1086   int insn_luid = INSN_LUID (DEP_CON (dep));
1087
1088   /* Clear corresponding cache entry because type of the link
1089      may have changed.  Keep them if we use_deps_list.  */
1090   if (!(current_sched_info->flags & USE_DEPS_LIST))
1091     {
1092       switch (old_type)
1093         {
1094         case REG_DEP_OUTPUT:
1095           bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
1096           break;
1097
1098         case REG_DEP_ANTI:
1099           bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1100           break;
1101
1102         case REG_DEP_CONTROL:
1103           bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid);
1104           break;
1105
1106         default:
1107           gcc_unreachable ();
1108         }
1109     }
1110
1111   set_dependency_caches (dep);
1112 }
1113
1114 /* Convert a dependence pointed to by SD_IT to be non-speculative.  */
1115 static void
1116 change_spec_dep_to_hard (sd_iterator_def sd_it)
1117 {
1118   dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1119   dep_link_t link = DEP_NODE_BACK (node);
1120   dep_t dep = DEP_NODE_DEP (node);
1121   rtx elem = DEP_PRO (dep);
1122   rtx insn = DEP_CON (dep);
1123
1124   move_dep_link (link, INSN_SPEC_BACK_DEPS (insn), INSN_HARD_BACK_DEPS (insn));
1125
1126   DEP_STATUS (dep) &= ~SPECULATIVE;
1127
1128   if (true_dependency_cache != NULL)
1129     /* Clear the cache entry.  */
1130     bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
1131                       INSN_LUID (elem));
1132 }
1133
1134 /* Update DEP to incorporate information from NEW_DEP.
1135    SD_IT points to DEP in case it should be moved to another list.
1136    MEM1 and MEM2, if nonnull, correspond to memory locations in case if
1137    data-speculative dependence should be updated.  */
1138 static enum DEPS_ADJUST_RESULT
1139 update_dep (dep_t dep, dep_t new_dep,
1140             sd_iterator_def sd_it ATTRIBUTE_UNUSED,
1141             rtx mem1 ATTRIBUTE_UNUSED,
1142             rtx mem2 ATTRIBUTE_UNUSED)
1143 {
1144   enum DEPS_ADJUST_RESULT res = DEP_PRESENT;
1145   enum reg_note old_type = DEP_TYPE (dep);
1146   bool was_spec = dep_spec_p (dep);
1147
1148   DEP_NONREG (dep) |= DEP_NONREG (new_dep);
1149   DEP_MULTIPLE (dep) = 1;
1150
1151   /* If this is a more restrictive type of dependence than the
1152      existing one, then change the existing dependence to this
1153      type.  */
1154   if ((int) DEP_TYPE (new_dep) < (int) old_type)
1155     {
1156       DEP_TYPE (dep) = DEP_TYPE (new_dep);
1157       res = DEP_CHANGED;
1158     }
1159
1160   if (current_sched_info->flags & USE_DEPS_LIST)
1161     /* Update DEP_STATUS.  */
1162     {
1163       ds_t dep_status = DEP_STATUS (dep);
1164       ds_t ds = DEP_STATUS (new_dep);
1165       ds_t new_status = ds | dep_status;
1166
1167       if (new_status & SPECULATIVE)
1168         {
1169           /* Either existing dep or a dep we're adding or both are
1170              speculative.  */
1171           if (!(ds & SPECULATIVE)
1172               || !(dep_status & SPECULATIVE))
1173             /* The new dep can't be speculative.  */
1174             new_status &= ~SPECULATIVE;
1175           else
1176             {
1177               /* Both are speculative.  Merge probabilities.  */
1178               if (mem1 != NULL)
1179                 {
1180                   dw_t dw;
1181
1182                   dw = estimate_dep_weak (mem1, mem2);
1183                   ds = set_dep_weak (ds, BEGIN_DATA, dw);
1184                 }
1185
1186               new_status = ds_merge (dep_status, ds);
1187             }
1188         }
1189
1190       ds = new_status;
1191
1192       if (dep_status != ds)
1193         {
1194           DEP_STATUS (dep) = ds;
1195           res = DEP_CHANGED;
1196         }
1197     }
1198
1199   if (was_spec && !dep_spec_p (dep))
1200     /* The old dep was speculative, but now it isn't.  */
1201     change_spec_dep_to_hard (sd_it);
1202
1203   if (true_dependency_cache != NULL
1204       && res == DEP_CHANGED)
1205     update_dependency_caches (dep, old_type);
1206
1207   return res;
1208 }
1209
1210 /* Add or update  a dependence described by DEP.
1211    MEM1 and MEM2, if non-null, correspond to memory locations in case of
1212    data speculation.
1213
1214    The function returns a value indicating if an old entry has been changed
1215    or a new entry has been added to insn's backward deps or nothing has
1216    been updated at all.  */
1217 static enum DEPS_ADJUST_RESULT
1218 add_or_update_dep_1 (dep_t new_dep, bool resolved_p,
1219                      rtx mem1 ATTRIBUTE_UNUSED, rtx mem2 ATTRIBUTE_UNUSED)
1220 {
1221   bool maybe_present_p = true;
1222   bool present_p = false;
1223
1224   gcc_assert (INSN_P (DEP_PRO (new_dep)) && INSN_P (DEP_CON (new_dep))
1225               && DEP_PRO (new_dep) != DEP_CON (new_dep));
1226
1227 #ifdef ENABLE_CHECKING
1228   check_dep (new_dep, mem1 != NULL);
1229 #endif
1230
1231   if (true_dependency_cache != NULL)
1232     {
1233       switch (ask_dependency_caches (new_dep))
1234         {
1235         case DEP_PRESENT:
1236           return DEP_PRESENT;
1237
1238         case DEP_CHANGED:
1239           maybe_present_p = true;
1240           present_p = true;
1241           break;
1242
1243         case DEP_CREATED:
1244           maybe_present_p = false;
1245           present_p = false;
1246           break;
1247
1248         default:
1249           gcc_unreachable ();
1250           break;
1251         }
1252     }
1253
1254   /* Check that we don't already have this dependence.  */
1255   if (maybe_present_p)
1256     {
1257       dep_t present_dep;
1258       sd_iterator_def sd_it;
1259
1260       gcc_assert (true_dependency_cache == NULL || present_p);
1261
1262       present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
1263                                                   DEP_CON (new_dep),
1264                                                   resolved_p, &sd_it);
1265
1266       if (present_dep != NULL)
1267         /* We found an existing dependency between ELEM and INSN.  */
1268         return update_dep (present_dep, new_dep, sd_it, mem1, mem2);
1269       else
1270         /* We didn't find a dep, it shouldn't present in the cache.  */
1271         gcc_assert (!present_p);
1272     }
1273
1274   /* Might want to check one level of transitivity to save conses.
1275      This check should be done in maybe_add_or_update_dep_1.
1276      Since we made it to add_or_update_dep_1, we must create
1277      (or update) a link.  */
1278
1279   if (mem1 != NULL_RTX)
1280     {
1281       gcc_assert (sched_deps_info->generate_spec_deps);
1282       DEP_STATUS (new_dep) = set_dep_weak (DEP_STATUS (new_dep), BEGIN_DATA,
1283                                            estimate_dep_weak (mem1, mem2));
1284     }
1285
1286   sd_add_dep (new_dep, resolved_p);
1287
1288   return DEP_CREATED;
1289 }
1290
1291 /* Initialize BACK_LIST_PTR with consumer's backward list and
1292    FORW_LIST_PTR with producer's forward list.  If RESOLVED_P is true
1293    initialize with lists that hold resolved deps.  */
1294 static void
1295 get_back_and_forw_lists (dep_t dep, bool resolved_p,
1296                          deps_list_t *back_list_ptr,
1297                          deps_list_t *forw_list_ptr)
1298 {
1299   rtx con = DEP_CON (dep);
1300
1301   if (!resolved_p)
1302     {
1303       if (dep_spec_p (dep))
1304         *back_list_ptr = INSN_SPEC_BACK_DEPS (con);
1305       else
1306         *back_list_ptr = INSN_HARD_BACK_DEPS (con);
1307
1308       *forw_list_ptr = INSN_FORW_DEPS (DEP_PRO (dep));
1309     }
1310   else
1311     {
1312       *back_list_ptr = INSN_RESOLVED_BACK_DEPS (con);
1313       *forw_list_ptr = INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep));
1314     }
1315 }
1316
1317 /* Add dependence described by DEP.
1318    If RESOLVED_P is true treat the dependence as a resolved one.  */
1319 void
1320 sd_add_dep (dep_t dep, bool resolved_p)
1321 {
1322   dep_node_t n = create_dep_node ();
1323   deps_list_t con_back_deps;
1324   deps_list_t pro_forw_deps;
1325   rtx elem = DEP_PRO (dep);
1326   rtx insn = DEP_CON (dep);
1327
1328   gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
1329
1330   if ((current_sched_info->flags & DO_SPECULATION) == 0
1331       || !sched_insn_is_legitimate_for_speculation_p (insn, DEP_STATUS (dep)))
1332     DEP_STATUS (dep) &= ~SPECULATIVE;
1333
1334   copy_dep (DEP_NODE_DEP (n), dep);
1335
1336   get_back_and_forw_lists (dep, resolved_p, &con_back_deps, &pro_forw_deps);
1337
1338   add_to_deps_list (DEP_NODE_BACK (n), con_back_deps);
1339
1340 #ifdef ENABLE_CHECKING
1341   check_dep (dep, false);
1342 #endif
1343
1344   add_to_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1345
1346   /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1347      in the bitmap caches of dependency information.  */
1348   if (true_dependency_cache != NULL)
1349     set_dependency_caches (dep);
1350 }
1351
1352 /* Add or update backward dependence between INSN and ELEM
1353    with given type DEP_TYPE and dep_status DS.
1354    This function is a convenience wrapper.  */
1355 enum DEPS_ADJUST_RESULT
1356 sd_add_or_update_dep (dep_t dep, bool resolved_p)
1357 {
1358   return add_or_update_dep_1 (dep, resolved_p, NULL_RTX, NULL_RTX);
1359 }
1360
1361 /* Resolved dependence pointed to by SD_IT.
1362    SD_IT will advance to the next element.  */
1363 void
1364 sd_resolve_dep (sd_iterator_def sd_it)
1365 {
1366   dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1367   dep_t dep = DEP_NODE_DEP (node);
1368   rtx pro = DEP_PRO (dep);
1369   rtx con = DEP_CON (dep);
1370
1371   if (dep_spec_p (dep))
1372     move_dep_link (DEP_NODE_BACK (node), INSN_SPEC_BACK_DEPS (con),
1373                    INSN_RESOLVED_BACK_DEPS (con));
1374   else
1375     move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
1376                    INSN_RESOLVED_BACK_DEPS (con));
1377
1378   move_dep_link (DEP_NODE_FORW (node), INSN_FORW_DEPS (pro),
1379                  INSN_RESOLVED_FORW_DEPS (pro));
1380 }
1381
1382 /* Perform the inverse operation of sd_resolve_dep.  Restore the dependence
1383    pointed to by SD_IT to unresolved state.  */
1384 void
1385 sd_unresolve_dep (sd_iterator_def sd_it)
1386 {
1387   dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1388   dep_t dep = DEP_NODE_DEP (node);
1389   rtx pro = DEP_PRO (dep);
1390   rtx con = DEP_CON (dep);
1391
1392   if (dep_spec_p (dep))
1393     move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con),
1394                    INSN_SPEC_BACK_DEPS (con));
1395   else
1396     move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con),
1397                    INSN_HARD_BACK_DEPS (con));
1398
1399   move_dep_link (DEP_NODE_FORW (node), INSN_RESOLVED_FORW_DEPS (pro),
1400                  INSN_FORW_DEPS (pro));
1401 }
1402
1403 /* Make TO depend on all the FROM's producers.
1404    If RESOLVED_P is true add dependencies to the resolved lists.  */
1405 void
1406 sd_copy_back_deps (rtx to, rtx from, bool resolved_p)
1407 {
1408   sd_list_types_def list_type;
1409   sd_iterator_def sd_it;
1410   dep_t dep;
1411
1412   list_type = resolved_p ? SD_LIST_RES_BACK : SD_LIST_BACK;
1413
1414   FOR_EACH_DEP (from, list_type, sd_it, dep)
1415     {
1416       dep_def _new_dep, *new_dep = &_new_dep;
1417
1418       copy_dep (new_dep, dep);
1419       DEP_CON (new_dep) = to;
1420       sd_add_dep (new_dep, resolved_p);
1421     }
1422 }
1423
1424 /* Remove a dependency referred to by SD_IT.
1425    SD_IT will point to the next dependence after removal.  */
1426 void
1427 sd_delete_dep (sd_iterator_def sd_it)
1428 {
1429   dep_node_t n = DEP_LINK_NODE (*sd_it.linkp);
1430   dep_t dep = DEP_NODE_DEP (n);
1431   rtx pro = DEP_PRO (dep);
1432   rtx con = DEP_CON (dep);
1433   deps_list_t con_back_deps;
1434   deps_list_t pro_forw_deps;
1435
1436   if (true_dependency_cache != NULL)
1437     {
1438       int elem_luid = INSN_LUID (pro);
1439       int insn_luid = INSN_LUID (con);
1440
1441       bitmap_clear_bit (&true_dependency_cache[insn_luid], elem_luid);
1442       bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1443       bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid);
1444       bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
1445
1446       if (current_sched_info->flags & DO_SPECULATION)
1447         bitmap_clear_bit (&spec_dependency_cache[insn_luid], elem_luid);
1448     }
1449
1450   get_back_and_forw_lists (dep, sd_it.resolved_p,
1451                            &con_back_deps, &pro_forw_deps);
1452
1453   remove_from_deps_list (DEP_NODE_BACK (n), con_back_deps);
1454   remove_from_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1455
1456   delete_dep_node (n);
1457 }
1458
1459 /* Dump size of the lists.  */
1460 #define DUMP_LISTS_SIZE (2)
1461
1462 /* Dump dependencies of the lists.  */
1463 #define DUMP_LISTS_DEPS (4)
1464
1465 /* Dump all information about the lists.  */
1466 #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1467
1468 /* Dump deps_lists of INSN specified by TYPES to DUMP.
1469    FLAGS is a bit mask specifying what information about the lists needs
1470    to be printed.
1471    If FLAGS has the very first bit set, then dump all information about
1472    the lists and propagate this bit into the callee dump functions.  */
1473 static void
1474 dump_lists (FILE *dump, rtx insn, sd_list_types_def types, int flags)
1475 {
1476   sd_iterator_def sd_it;
1477   dep_t dep;
1478   int all;
1479
1480   all = (flags & 1);
1481
1482   if (all)
1483     flags |= DUMP_LISTS_ALL;
1484
1485   fprintf (dump, "[");
1486
1487   if (flags & DUMP_LISTS_SIZE)
1488     fprintf (dump, "%d; ", sd_lists_size (insn, types));
1489
1490   if (flags & DUMP_LISTS_DEPS)
1491     {
1492       FOR_EACH_DEP (insn, types, sd_it, dep)
1493         {
1494           dump_dep (dump, dep, dump_dep_flags | all);
1495           fprintf (dump, " ");
1496         }
1497     }
1498 }
1499
1500 /* Dump all information about deps_lists of INSN specified by TYPES
1501    to STDERR.  */
1502 void
1503 sd_debug_lists (rtx insn, sd_list_types_def types)
1504 {
1505   dump_lists (stderr, insn, types, 1);
1506   fprintf (stderr, "\n");
1507 }
1508
1509 /* A wrapper around add_dependence_1, to add a dependence of CON on
1510    PRO, with type DEP_TYPE.  This function implements special handling
1511    for REG_DEP_CONTROL dependencies.  For these, we optionally promote
1512    the type to REG_DEP_ANTI if we can determine that predication is
1513    impossible; otherwise we add additional true dependencies on the
1514    INSN_COND_DEPS list of the jump (which PRO must be).  */
1515 void
1516 add_dependence (rtx con, rtx pro, enum reg_note dep_type)
1517 {
1518   if (dep_type == REG_DEP_CONTROL
1519       && !(current_sched_info->flags & DO_PREDICATION))
1520     dep_type = REG_DEP_ANTI;
1521
1522   /* A REG_DEP_CONTROL dependence may be eliminated through predication,
1523      so we must also make the insn dependent on the setter of the
1524      condition.  */
1525   if (dep_type == REG_DEP_CONTROL)
1526     {
1527       rtx real_pro = pro;
1528       rtx other = real_insn_for_shadow (real_pro);
1529       rtx cond;
1530
1531       if (other != NULL_RTX)
1532         real_pro = other;
1533       cond = sched_get_reverse_condition_uncached (real_pro);
1534       /* Verify that the insn does not use a different value in
1535          the condition register than the one that was present at
1536          the jump.  */
1537       if (cond == NULL_RTX)
1538         dep_type = REG_DEP_ANTI;
1539       else if (INSN_CACHED_COND (real_pro) == const_true_rtx)
1540         {
1541           HARD_REG_SET uses;
1542           CLEAR_HARD_REG_SET (uses);
1543           note_uses (&PATTERN (con), record_hard_reg_uses, &uses);
1544           if (TEST_HARD_REG_BIT (uses, REGNO (XEXP (cond, 0))))
1545             dep_type = REG_DEP_ANTI;
1546         }
1547       if (dep_type == REG_DEP_CONTROL)
1548         {
1549           if (sched_verbose >= 5)
1550             fprintf (sched_dump, "making DEP_CONTROL for %d\n",
1551                      INSN_UID (real_pro));
1552           add_dependence_list (con, INSN_COND_DEPS (real_pro), 0,
1553                                REG_DEP_TRUE, false);
1554         }
1555     }
1556
1557   add_dependence_1 (con, pro, dep_type);
1558 }
1559
1560 /* A convenience wrapper to operate on an entire list.  HARD should be
1561    true if DEP_NONREG should be set on newly created dependencies.  */
1562
1563 static void
1564 add_dependence_list (rtx insn, rtx list, int uncond, enum reg_note dep_type,
1565                      bool hard)
1566 {
1567   mark_as_hard = hard;
1568   for (; list; list = XEXP (list, 1))
1569     {
1570       if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
1571         add_dependence (insn, XEXP (list, 0), dep_type);
1572     }
1573   mark_as_hard = false;
1574 }
1575
1576 /* Similar, but free *LISTP at the same time, when the context
1577    is not readonly.  HARD should be true if DEP_NONREG should be set on
1578    newly created dependencies.  */
1579
1580 static void
1581 add_dependence_list_and_free (struct deps_desc *deps, rtx insn, rtx *listp,
1582                               int uncond, enum reg_note dep_type, bool hard)
1583 {
1584   add_dependence_list (insn, *listp, uncond, dep_type, hard);
1585
1586   /* We don't want to short-circuit dependencies involving debug
1587      insns, because they may cause actual dependencies to be
1588      disregarded.  */
1589   if (deps->readonly || DEBUG_INSN_P (insn))
1590     return;
1591
1592   free_INSN_LIST_list (listp);
1593 }
1594
1595 /* Remove all occurrences of INSN from LIST.  Return the number of
1596    occurrences removed.  */
1597
1598 static int
1599 remove_from_dependence_list (rtx insn, rtx* listp)
1600 {
1601   int removed = 0;
1602
1603   while (*listp)
1604     {
1605       if (XEXP (*listp, 0) == insn)
1606         {
1607           remove_free_INSN_LIST_node (listp);
1608           removed++;
1609           continue;
1610         }
1611
1612       listp = &XEXP (*listp, 1);
1613     }
1614
1615   return removed;
1616 }
1617
1618 /* Same as above, but process two lists at once.  */
1619 static int
1620 remove_from_both_dependence_lists (rtx insn, rtx *listp, rtx *exprp)
1621 {
1622   int removed = 0;
1623
1624   while (*listp)
1625     {
1626       if (XEXP (*listp, 0) == insn)
1627         {
1628           remove_free_INSN_LIST_node (listp);
1629           remove_free_EXPR_LIST_node (exprp);
1630           removed++;
1631           continue;
1632         }
1633
1634       listp = &XEXP (*listp, 1);
1635       exprp = &XEXP (*exprp, 1);
1636     }
1637
1638   return removed;
1639 }
1640
1641 /* Clear all dependencies for an insn.  */
1642 static void
1643 delete_all_dependences (rtx insn)
1644 {
1645   sd_iterator_def sd_it;
1646   dep_t dep;
1647
1648   /* The below cycle can be optimized to clear the caches and back_deps
1649      in one call but that would provoke duplication of code from
1650      delete_dep ().  */
1651
1652   for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
1653        sd_iterator_cond (&sd_it, &dep);)
1654     sd_delete_dep (sd_it);
1655 }
1656
1657 /* All insns in a scheduling group except the first should only have
1658    dependencies on the previous insn in the group.  So we find the
1659    first instruction in the scheduling group by walking the dependence
1660    chains backwards. Then we add the dependencies for the group to
1661    the previous nonnote insn.  */
1662
1663 static void
1664 chain_to_prev_insn (rtx insn)
1665 {
1666   sd_iterator_def sd_it;
1667   dep_t dep;
1668   rtx prev_nonnote;
1669
1670   FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
1671     {
1672       rtx i = insn;
1673       rtx pro = DEP_PRO (dep);
1674
1675       do
1676         {
1677           i = prev_nonnote_insn (i);
1678
1679           if (pro == i)
1680             goto next_link;
1681         } while (SCHED_GROUP_P (i) || DEBUG_INSN_P (i));
1682
1683       if (! sched_insns_conditions_mutex_p (i, pro))
1684         add_dependence (i, pro, DEP_TYPE (dep));
1685     next_link:;
1686     }
1687
1688   delete_all_dependences (insn);
1689
1690   prev_nonnote = prev_nonnote_nondebug_insn (insn);
1691   if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
1692       && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
1693     add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
1694 }
1695 \f
1696 /* Process an insn's memory dependencies.  There are four kinds of
1697    dependencies:
1698
1699    (0) read dependence: read follows read
1700    (1) true dependence: read follows write
1701    (2) output dependence: write follows write
1702    (3) anti dependence: write follows read
1703
1704    We are careful to build only dependencies which actually exist, and
1705    use transitivity to avoid building too many links.  */
1706
1707 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1708    The MEM is a memory reference contained within INSN, which we are saving
1709    so that we can do memory aliasing on it.  */
1710
1711 static void
1712 add_insn_mem_dependence (struct deps_desc *deps, bool read_p,
1713                          rtx insn, rtx mem)
1714 {
1715   rtx *insn_list;
1716   rtx *mem_list;
1717   rtx link;
1718
1719   gcc_assert (!deps->readonly);
1720   if (read_p)
1721     {
1722       insn_list = &deps->pending_read_insns;
1723       mem_list = &deps->pending_read_mems;
1724       if (!DEBUG_INSN_P (insn))
1725         deps->pending_read_list_length++;
1726     }
1727   else
1728     {
1729       insn_list = &deps->pending_write_insns;
1730       mem_list = &deps->pending_write_mems;
1731       deps->pending_write_list_length++;
1732     }
1733
1734   link = alloc_INSN_LIST (insn, *insn_list);
1735   *insn_list = link;
1736
1737   if (sched_deps_info->use_cselib)
1738     {
1739       mem = shallow_copy_rtx (mem);
1740       XEXP (mem, 0) = cselib_subst_to_values_from_insn (XEXP (mem, 0),
1741                                                         GET_MODE (mem), insn);
1742     }
1743   link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
1744   *mem_list = link;
1745 }
1746
1747 /* Make a dependency between every memory reference on the pending lists
1748    and INSN, thus flushing the pending lists.  FOR_READ is true if emitting
1749    dependencies for a read operation, similarly with FOR_WRITE.  */
1750
1751 static void
1752 flush_pending_lists (struct deps_desc *deps, rtx insn, int for_read,
1753                      int for_write)
1754 {
1755   if (for_write)
1756     {
1757       add_dependence_list_and_free (deps, insn, &deps->pending_read_insns,
1758                                     1, REG_DEP_ANTI, true);
1759       if (!deps->readonly)
1760         {
1761           free_EXPR_LIST_list (&deps->pending_read_mems);
1762           deps->pending_read_list_length = 0;
1763         }
1764     }
1765
1766   add_dependence_list_and_free (deps, insn, &deps->pending_write_insns, 1,
1767                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT,
1768                                 true);
1769
1770   add_dependence_list_and_free (deps, insn,
1771                                 &deps->last_pending_memory_flush, 1,
1772                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT,
1773                                 true);
1774
1775   add_dependence_list_and_free (deps, insn, &deps->pending_jump_insns, 1,
1776                                 REG_DEP_ANTI, true);
1777
1778   if (DEBUG_INSN_P (insn))
1779     {
1780       if (for_write)
1781         free_INSN_LIST_list (&deps->pending_read_insns);
1782       free_INSN_LIST_list (&deps->pending_write_insns);
1783       free_INSN_LIST_list (&deps->last_pending_memory_flush);
1784       free_INSN_LIST_list (&deps->pending_jump_insns);
1785     }
1786
1787   if (!deps->readonly)
1788     {
1789       free_EXPR_LIST_list (&deps->pending_write_mems);
1790       deps->pending_write_list_length = 0;
1791
1792       deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
1793       deps->pending_flush_length = 1;
1794     }
1795   mark_as_hard = false;
1796 }
1797 \f
1798 /* Instruction which dependencies we are analyzing.  */
1799 static rtx cur_insn = NULL_RTX;
1800
1801 /* Implement hooks for haifa scheduler.  */
1802
1803 static void
1804 haifa_start_insn (rtx insn)
1805 {
1806   gcc_assert (insn && !cur_insn);
1807
1808   cur_insn = insn;
1809 }
1810
1811 static void
1812 haifa_finish_insn (void)
1813 {
1814   cur_insn = NULL;
1815 }
1816
1817 void
1818 haifa_note_reg_set (int regno)
1819 {
1820   SET_REGNO_REG_SET (reg_pending_sets, regno);
1821 }
1822
1823 void
1824 haifa_note_reg_clobber (int regno)
1825 {
1826   SET_REGNO_REG_SET (reg_pending_clobbers, regno);
1827 }
1828
1829 void
1830 haifa_note_reg_use (int regno)
1831 {
1832   SET_REGNO_REG_SET (reg_pending_uses, regno);
1833 }
1834
1835 static void
1836 haifa_note_mem_dep (rtx mem, rtx pending_mem, rtx pending_insn, ds_t ds)
1837 {
1838   if (!(ds & SPECULATIVE))
1839     {
1840       mem = NULL_RTX;
1841       pending_mem = NULL_RTX;
1842     }
1843   else
1844     gcc_assert (ds & BEGIN_DATA);
1845
1846   {
1847     dep_def _dep, *dep = &_dep;
1848
1849     init_dep_1 (dep, pending_insn, cur_insn, ds_to_dt (ds),
1850                 current_sched_info->flags & USE_DEPS_LIST ? ds : 0);
1851     DEP_NONREG (dep) = 1;
1852     maybe_add_or_update_dep_1 (dep, false, pending_mem, mem);
1853   }
1854
1855 }
1856
1857 static void
1858 haifa_note_dep (rtx elem, ds_t ds)
1859 {
1860   dep_def _dep;
1861   dep_t dep = &_dep;
1862
1863   init_dep (dep, elem, cur_insn, ds_to_dt (ds));
1864   if (mark_as_hard)
1865     DEP_NONREG (dep) = 1;
1866   maybe_add_or_update_dep_1 (dep, false, NULL_RTX, NULL_RTX);
1867 }
1868
1869 static void
1870 note_reg_use (int r)
1871 {
1872   if (sched_deps_info->note_reg_use)
1873     sched_deps_info->note_reg_use (r);
1874 }
1875
1876 static void
1877 note_reg_set (int r)
1878 {
1879   if (sched_deps_info->note_reg_set)
1880     sched_deps_info->note_reg_set (r);
1881 }
1882
1883 static void
1884 note_reg_clobber (int r)
1885 {
1886   if (sched_deps_info->note_reg_clobber)
1887     sched_deps_info->note_reg_clobber (r);
1888 }
1889
1890 static void
1891 note_mem_dep (rtx m1, rtx m2, rtx e, ds_t ds)
1892 {
1893   if (sched_deps_info->note_mem_dep)
1894     sched_deps_info->note_mem_dep (m1, m2, e, ds);
1895 }
1896
1897 static void
1898 note_dep (rtx e, ds_t ds)
1899 {
1900   if (sched_deps_info->note_dep)
1901     sched_deps_info->note_dep (e, ds);
1902 }
1903
1904 /* Return corresponding to DS reg_note.  */
1905 enum reg_note
1906 ds_to_dt (ds_t ds)
1907 {
1908   if (ds & DEP_TRUE)
1909     return REG_DEP_TRUE;
1910   else if (ds & DEP_OUTPUT)
1911     return REG_DEP_OUTPUT;
1912   else if (ds & DEP_ANTI)
1913     return REG_DEP_ANTI;
1914   else
1915     {
1916       gcc_assert (ds & DEP_CONTROL);
1917       return REG_DEP_CONTROL;
1918     }
1919 }
1920
1921 \f
1922
1923 /* Functions for computation of info needed for register pressure
1924    sensitive insn scheduling.  */
1925
1926
1927 /* Allocate and return reg_use_data structure for REGNO and INSN.  */
1928 static struct reg_use_data *
1929 create_insn_reg_use (int regno, rtx insn)
1930 {
1931   struct reg_use_data *use;
1932
1933   use = (struct reg_use_data *) xmalloc (sizeof (struct reg_use_data));
1934   use->regno = regno;
1935   use->insn = insn;
1936   use->next_insn_use = INSN_REG_USE_LIST (insn);
1937   INSN_REG_USE_LIST (insn) = use;
1938   return use;
1939 }
1940
1941 /* Allocate reg_set_data structure for REGNO and INSN.  */
1942 static void
1943 create_insn_reg_set (int regno, rtx insn)
1944 {
1945   struct reg_set_data *set;
1946
1947   set = (struct reg_set_data *) xmalloc (sizeof (struct reg_set_data));
1948   set->regno = regno;
1949   set->insn = insn;
1950   set->next_insn_set = INSN_REG_SET_LIST (insn);
1951   INSN_REG_SET_LIST (insn) = set;
1952 }
1953
1954 /* Set up insn register uses for INSN and dependency context DEPS.  */
1955 static void
1956 setup_insn_reg_uses (struct deps_desc *deps, rtx insn)
1957 {
1958   unsigned i;
1959   reg_set_iterator rsi;
1960   rtx list;
1961   struct reg_use_data *use, *use2, *next;
1962   struct deps_reg *reg_last;
1963
1964   EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1965     {
1966       if (i < FIRST_PSEUDO_REGISTER
1967           && TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
1968         continue;
1969
1970       if (find_regno_note (insn, REG_DEAD, i) == NULL_RTX
1971           && ! REGNO_REG_SET_P (reg_pending_sets, i)
1972           && ! REGNO_REG_SET_P (reg_pending_clobbers, i))
1973         /* Ignore use which is not dying.  */
1974         continue;
1975
1976       use = create_insn_reg_use (i, insn);
1977       use->next_regno_use = use;
1978       reg_last = &deps->reg_last[i];
1979
1980       /* Create the cycle list of uses.  */
1981       for (list = reg_last->uses; list; list = XEXP (list, 1))
1982         {
1983           use2 = create_insn_reg_use (i, XEXP (list, 0));
1984           next = use->next_regno_use;
1985           use->next_regno_use = use2;
1986           use2->next_regno_use = next;
1987         }
1988     }
1989 }
1990
1991 /* Register pressure info for the currently processed insn.  */
1992 static struct reg_pressure_data reg_pressure_info[N_REG_CLASSES];
1993
1994 /* Return TRUE if INSN has the use structure for REGNO.  */
1995 static bool
1996 insn_use_p (rtx insn, int regno)
1997 {
1998   struct reg_use_data *use;
1999
2000   for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
2001     if (use->regno == regno)
2002       return true;
2003   return false;
2004 }
2005
2006 /* Update the register pressure info after birth of pseudo register REGNO
2007    in INSN.  Arguments CLOBBER_P and UNUSED_P say correspondingly that
2008    the register is in clobber or unused after the insn.  */
2009 static void
2010 mark_insn_pseudo_birth (rtx insn, int regno, bool clobber_p, bool unused_p)
2011 {
2012   int incr, new_incr;
2013   enum reg_class cl;
2014
2015   gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
2016   cl = sched_regno_pressure_class[regno];
2017   if (cl != NO_REGS)
2018     {
2019       incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
2020       if (clobber_p)
2021         {
2022           new_incr = reg_pressure_info[cl].clobber_increase + incr;
2023           reg_pressure_info[cl].clobber_increase = new_incr;
2024         }
2025       else if (unused_p)
2026         {
2027           new_incr = reg_pressure_info[cl].unused_set_increase + incr;
2028           reg_pressure_info[cl].unused_set_increase = new_incr;
2029         }
2030       else
2031         {
2032           new_incr = reg_pressure_info[cl].set_increase + incr;
2033           reg_pressure_info[cl].set_increase = new_incr;
2034           if (! insn_use_p (insn, regno))
2035             reg_pressure_info[cl].change += incr;
2036           create_insn_reg_set (regno, insn);
2037         }
2038       gcc_assert (new_incr < (1 << INCREASE_BITS));
2039     }
2040 }
2041
2042 /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
2043    hard registers involved in the birth.  */
2044 static void
2045 mark_insn_hard_regno_birth (rtx insn, int regno, int nregs,
2046                             bool clobber_p, bool unused_p)
2047 {
2048   enum reg_class cl;
2049   int new_incr, last = regno + nregs;
2050
2051   while (regno < last)
2052     {
2053       gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2054       if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
2055         {
2056           cl = sched_regno_pressure_class[regno];
2057           if (cl != NO_REGS)
2058             {
2059               if (clobber_p)
2060                 {
2061                   new_incr = reg_pressure_info[cl].clobber_increase + 1;
2062                   reg_pressure_info[cl].clobber_increase = new_incr;
2063                 }
2064               else if (unused_p)
2065                 {
2066                   new_incr = reg_pressure_info[cl].unused_set_increase + 1;
2067                   reg_pressure_info[cl].unused_set_increase = new_incr;
2068                 }
2069               else
2070                 {
2071                   new_incr = reg_pressure_info[cl].set_increase + 1;
2072                   reg_pressure_info[cl].set_increase = new_incr;
2073                   if (! insn_use_p (insn, regno))
2074                     reg_pressure_info[cl].change += 1;
2075                   create_insn_reg_set (regno, insn);
2076                 }
2077               gcc_assert (new_incr < (1 << INCREASE_BITS));
2078             }
2079         }
2080       regno++;
2081     }
2082 }
2083
2084 /* Update the register pressure info after birth of pseudo or hard
2085    register REG in INSN.  Arguments CLOBBER_P and UNUSED_P say
2086    correspondingly that the register is in clobber or unused after the
2087    insn.  */
2088 static void
2089 mark_insn_reg_birth (rtx insn, rtx reg, bool clobber_p, bool unused_p)
2090 {
2091   int regno;
2092
2093   if (GET_CODE (reg) == SUBREG)
2094     reg = SUBREG_REG (reg);
2095
2096   if (! REG_P (reg))
2097     return;
2098
2099   regno = REGNO (reg);
2100   if (regno < FIRST_PSEUDO_REGISTER)
2101     mark_insn_hard_regno_birth (insn, regno,
2102                                 hard_regno_nregs[regno][GET_MODE (reg)],
2103                                 clobber_p, unused_p);
2104   else
2105     mark_insn_pseudo_birth (insn, regno, clobber_p, unused_p);
2106 }
2107
2108 /* Update the register pressure info after death of pseudo register
2109    REGNO.  */
2110 static void
2111 mark_pseudo_death (int regno)
2112 {
2113   int incr;
2114   enum reg_class cl;
2115
2116   gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
2117   cl = sched_regno_pressure_class[regno];
2118   if (cl != NO_REGS)
2119     {
2120       incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
2121       reg_pressure_info[cl].change -= incr;
2122     }
2123 }
2124
2125 /* Like mark_pseudo_death except that NREGS saying how many hard
2126    registers involved in the death.  */
2127 static void
2128 mark_hard_regno_death (int regno, int nregs)
2129 {
2130   enum reg_class cl;
2131   int last = regno + nregs;
2132
2133   while (regno < last)
2134     {
2135       gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2136       if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
2137         {
2138           cl = sched_regno_pressure_class[regno];
2139           if (cl != NO_REGS)
2140             reg_pressure_info[cl].change -= 1;
2141         }
2142       regno++;
2143     }
2144 }
2145
2146 /* Update the register pressure info after death of pseudo or hard
2147    register REG.  */
2148 static void
2149 mark_reg_death (rtx reg)
2150 {
2151   int regno;
2152
2153   if (GET_CODE (reg) == SUBREG)
2154     reg = SUBREG_REG (reg);
2155
2156   if (! REG_P (reg))
2157     return;
2158
2159   regno = REGNO (reg);
2160   if (regno < FIRST_PSEUDO_REGISTER)
2161     mark_hard_regno_death (regno, hard_regno_nregs[regno][GET_MODE (reg)]);
2162   else
2163     mark_pseudo_death (regno);
2164 }
2165
2166 /* Process SETTER of REG.  DATA is an insn containing the setter.  */
2167 static void
2168 mark_insn_reg_store (rtx reg, const_rtx setter, void *data)
2169 {
2170   if (setter != NULL_RTX && GET_CODE (setter) != SET)
2171     return;
2172   mark_insn_reg_birth
2173     ((rtx) data, reg, false,
2174      find_reg_note ((const_rtx) data, REG_UNUSED, reg) != NULL_RTX);
2175 }
2176
2177 /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs.  */
2178 static void
2179 mark_insn_reg_clobber (rtx reg, const_rtx setter, void *data)
2180 {
2181   if (GET_CODE (setter) == CLOBBER)
2182     mark_insn_reg_birth ((rtx) data, reg, true, false);
2183 }
2184
2185 /* Set up reg pressure info related to INSN.  */
2186 void
2187 init_insn_reg_pressure_info (rtx insn)
2188 {
2189   int i, len;
2190   enum reg_class cl;
2191   static struct reg_pressure_data *pressure_info;
2192   rtx link;
2193
2194   gcc_assert (sched_pressure != SCHED_PRESSURE_NONE);
2195
2196   if (! INSN_P (insn))
2197     return;
2198
2199   for (i = 0; i < ira_pressure_classes_num; i++)
2200     {
2201       cl = ira_pressure_classes[i];
2202       reg_pressure_info[cl].clobber_increase = 0;
2203       reg_pressure_info[cl].set_increase = 0;
2204       reg_pressure_info[cl].unused_set_increase = 0;
2205       reg_pressure_info[cl].change = 0;
2206     }
2207
2208   note_stores (PATTERN (insn), mark_insn_reg_clobber, insn);
2209
2210   note_stores (PATTERN (insn), mark_insn_reg_store, insn);
2211
2212 #ifdef AUTO_INC_DEC
2213   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2214     if (REG_NOTE_KIND (link) == REG_INC)
2215       mark_insn_reg_store (XEXP (link, 0), NULL_RTX, insn);
2216 #endif
2217
2218   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2219     if (REG_NOTE_KIND (link) == REG_DEAD)
2220       mark_reg_death (XEXP (link, 0));
2221
2222   len = sizeof (struct reg_pressure_data) * ira_pressure_classes_num;
2223   pressure_info
2224     = INSN_REG_PRESSURE (insn) = (struct reg_pressure_data *) xmalloc (len);
2225   if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
2226     INSN_MAX_REG_PRESSURE (insn) = (int *) xcalloc (ira_pressure_classes_num
2227                                                     * sizeof (int), 1);
2228   for (i = 0; i < ira_pressure_classes_num; i++)
2229     {
2230       cl = ira_pressure_classes[i];
2231       pressure_info[i].clobber_increase
2232         = reg_pressure_info[cl].clobber_increase;
2233       pressure_info[i].set_increase = reg_pressure_info[cl].set_increase;
2234       pressure_info[i].unused_set_increase
2235         = reg_pressure_info[cl].unused_set_increase;
2236       pressure_info[i].change = reg_pressure_info[cl].change;
2237     }
2238 }
2239
2240
2241 \f
2242
2243 /* Internal variable for sched_analyze_[12] () functions.
2244    If it is nonzero, this means that sched_analyze_[12] looks
2245    at the most toplevel SET.  */
2246 static bool can_start_lhs_rhs_p;
2247
2248 /* Extend reg info for the deps context DEPS given that
2249    we have just generated a register numbered REGNO.  */
2250 static void
2251 extend_deps_reg_info (struct deps_desc *deps, int regno)
2252 {
2253   int max_regno = regno + 1;
2254
2255   gcc_assert (!reload_completed);
2256
2257   /* In a readonly context, it would not hurt to extend info,
2258      but it should not be needed.  */
2259   if (reload_completed && deps->readonly)
2260     {
2261       deps->max_reg = max_regno;
2262       return;
2263     }
2264
2265   if (max_regno > deps->max_reg)
2266     {
2267       deps->reg_last = XRESIZEVEC (struct deps_reg, deps->reg_last,
2268                                    max_regno);
2269       memset (&deps->reg_last[deps->max_reg],
2270               0, (max_regno - deps->max_reg)
2271               * sizeof (struct deps_reg));
2272       deps->max_reg = max_regno;
2273     }
2274 }
2275
2276 /* Extends REG_INFO_P if needed.  */
2277 void
2278 maybe_extend_reg_info_p (void)
2279 {
2280   /* Extend REG_INFO_P, if needed.  */
2281   if ((unsigned int)max_regno - 1 >= reg_info_p_size)
2282     {
2283       size_t new_reg_info_p_size = max_regno + 128;
2284
2285       gcc_assert (!reload_completed && sel_sched_p ());
2286
2287       reg_info_p = (struct reg_info_t *) xrecalloc (reg_info_p,
2288                                                     new_reg_info_p_size,
2289                                                     reg_info_p_size,
2290                                                     sizeof (*reg_info_p));
2291       reg_info_p_size = new_reg_info_p_size;
2292     }
2293 }
2294
2295 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2296    The type of the reference is specified by REF and can be SET,
2297    CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE.  */
2298
2299 static void
2300 sched_analyze_reg (struct deps_desc *deps, int regno, enum machine_mode mode,
2301                    enum rtx_code ref, rtx insn)
2302 {
2303   /* We could emit new pseudos in renaming.  Extend the reg structures.  */
2304   if (!reload_completed && sel_sched_p ()
2305       && (regno >= max_reg_num () - 1 || regno >= deps->max_reg))
2306     extend_deps_reg_info (deps, regno);
2307
2308   maybe_extend_reg_info_p ();
2309
2310   /* A hard reg in a wide mode may really be multiple registers.
2311      If so, mark all of them just like the first.  */
2312   if (regno < FIRST_PSEUDO_REGISTER)
2313     {
2314       int i = hard_regno_nregs[regno][mode];
2315       if (ref == SET)
2316         {
2317           while (--i >= 0)
2318             note_reg_set (regno + i);
2319         }
2320       else if (ref == USE)
2321         {
2322           while (--i >= 0)
2323             note_reg_use (regno + i);
2324         }
2325       else
2326         {
2327           while (--i >= 0)
2328             note_reg_clobber (regno + i);
2329         }
2330     }
2331
2332   /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2333      it does not reload.  Ignore these as they have served their
2334      purpose already.  */
2335   else if (regno >= deps->max_reg)
2336     {
2337       enum rtx_code code = GET_CODE (PATTERN (insn));
2338       gcc_assert (code == USE || code == CLOBBER);
2339     }
2340
2341   else
2342     {
2343       if (ref == SET)
2344         note_reg_set (regno);
2345       else if (ref == USE)
2346         note_reg_use (regno);
2347       else
2348         note_reg_clobber (regno);
2349
2350       /* Pseudos that are REG_EQUIV to something may be replaced
2351          by that during reloading.  We need only add dependencies for
2352         the address in the REG_EQUIV note.  */
2353       if (!reload_completed && get_reg_known_equiv_p (regno))
2354         {
2355           rtx t = get_reg_known_value (regno);
2356           if (MEM_P (t))
2357             sched_analyze_2 (deps, XEXP (t, 0), insn);
2358         }
2359
2360       /* Don't let it cross a call after scheduling if it doesn't
2361          already cross one.  */
2362       if (REG_N_CALLS_CROSSED (regno) == 0)
2363         {
2364           if (!deps->readonly && ref == USE && !DEBUG_INSN_P (insn))
2365             deps->sched_before_next_call
2366               = alloc_INSN_LIST (insn, deps->sched_before_next_call);
2367           else
2368             add_dependence_list (insn, deps->last_function_call, 1,
2369                                  REG_DEP_ANTI, false);
2370         }
2371     }
2372 }
2373
2374 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2375    rtx, X, creating all dependencies generated by the write to the
2376    destination of X, and reads of everything mentioned.  */
2377
2378 static void
2379 sched_analyze_1 (struct deps_desc *deps, rtx x, rtx insn)
2380 {
2381   rtx dest = XEXP (x, 0);
2382   enum rtx_code code = GET_CODE (x);
2383   bool cslr_p = can_start_lhs_rhs_p;
2384
2385   can_start_lhs_rhs_p = false;
2386
2387   gcc_assert (dest);
2388   if (dest == 0)
2389     return;
2390
2391   if (cslr_p && sched_deps_info->start_lhs)
2392     sched_deps_info->start_lhs (dest);
2393
2394   if (GET_CODE (dest) == PARALLEL)
2395     {
2396       int i;
2397
2398       for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
2399         if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
2400           sched_analyze_1 (deps,
2401                            gen_rtx_CLOBBER (VOIDmode,
2402                                             XEXP (XVECEXP (dest, 0, i), 0)),
2403                            insn);
2404
2405       if (cslr_p && sched_deps_info->finish_lhs)
2406         sched_deps_info->finish_lhs ();
2407
2408       if (code == SET)
2409         {
2410           can_start_lhs_rhs_p = cslr_p;
2411
2412           sched_analyze_2 (deps, SET_SRC (x), insn);
2413
2414           can_start_lhs_rhs_p = false;
2415         }
2416
2417       return;
2418     }
2419
2420   while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
2421          || GET_CODE (dest) == ZERO_EXTRACT)
2422     {
2423       if (GET_CODE (dest) == STRICT_LOW_PART
2424          || GET_CODE (dest) == ZERO_EXTRACT
2425          || df_read_modify_subreg_p (dest))
2426         {
2427           /* These both read and modify the result.  We must handle
2428              them as writes to get proper dependencies for following
2429              instructions.  We must handle them as reads to get proper
2430              dependencies from this to previous instructions.
2431              Thus we need to call sched_analyze_2.  */
2432
2433           sched_analyze_2 (deps, XEXP (dest, 0), insn);
2434         }
2435       if (GET_CODE (dest) == ZERO_EXTRACT)
2436         {
2437           /* The second and third arguments are values read by this insn.  */
2438           sched_analyze_2 (deps, XEXP (dest, 1), insn);
2439           sched_analyze_2 (deps, XEXP (dest, 2), insn);
2440         }
2441       dest = XEXP (dest, 0);
2442     }
2443
2444   if (REG_P (dest))
2445     {
2446       int regno = REGNO (dest);
2447       enum machine_mode mode = GET_MODE (dest);
2448
2449       sched_analyze_reg (deps, regno, mode, code, insn);
2450
2451 #ifdef STACK_REGS
2452       /* Treat all writes to a stack register as modifying the TOS.  */
2453       if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2454         {
2455           /* Avoid analyzing the same register twice.  */
2456           if (regno != FIRST_STACK_REG)
2457             sched_analyze_reg (deps, FIRST_STACK_REG, mode, code, insn);
2458
2459           add_to_hard_reg_set (&implicit_reg_pending_uses, mode,
2460                                FIRST_STACK_REG);
2461         }
2462 #endif
2463     }
2464   else if (MEM_P (dest))
2465     {
2466       /* Writing memory.  */
2467       rtx t = dest;
2468
2469       if (sched_deps_info->use_cselib)
2470         {
2471           enum machine_mode address_mode = get_address_mode (dest);
2472
2473           t = shallow_copy_rtx (dest);
2474           cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2475                                    GET_MODE (t), insn);
2476           XEXP (t, 0)
2477             = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
2478                                                 insn);
2479         }
2480       t = canon_rtx (t);
2481
2482       /* Pending lists can't get larger with a readonly context.  */
2483       if (!deps->readonly
2484           && ((deps->pending_read_list_length + deps->pending_write_list_length)
2485               > MAX_PENDING_LIST_LENGTH))
2486         {
2487           /* Flush all pending reads and writes to prevent the pending lists
2488              from getting any larger.  Insn scheduling runs too slowly when
2489              these lists get long.  When compiling GCC with itself,
2490              this flush occurs 8 times for sparc, and 10 times for m88k using
2491              the default value of 32.  */
2492           flush_pending_lists (deps, insn, false, true);
2493         }
2494       else
2495         {
2496           rtx pending, pending_mem;
2497
2498           pending = deps->pending_read_insns;
2499           pending_mem = deps->pending_read_mems;
2500           while (pending)
2501             {
2502               if (anti_dependence (XEXP (pending_mem, 0), t)
2503                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2504                 note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2505                               DEP_ANTI);
2506
2507               pending = XEXP (pending, 1);
2508               pending_mem = XEXP (pending_mem, 1);
2509             }
2510
2511           pending = deps->pending_write_insns;
2512           pending_mem = deps->pending_write_mems;
2513           while (pending)
2514             {
2515               if (output_dependence (XEXP (pending_mem, 0), t)
2516                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2517                 note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2518                               DEP_OUTPUT);
2519
2520               pending = XEXP (pending, 1);
2521               pending_mem = XEXP (pending_mem, 1);
2522             }
2523
2524           add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2525                                REG_DEP_ANTI, true);
2526           add_dependence_list (insn, deps->pending_jump_insns, 1,
2527                                REG_DEP_CONTROL, true);
2528
2529           if (!deps->readonly)
2530             add_insn_mem_dependence (deps, false, insn, dest);
2531         }
2532       sched_analyze_2 (deps, XEXP (dest, 0), insn);
2533     }
2534
2535   if (cslr_p && sched_deps_info->finish_lhs)
2536     sched_deps_info->finish_lhs ();
2537
2538   /* Analyze reads.  */
2539   if (GET_CODE (x) == SET)
2540     {
2541       can_start_lhs_rhs_p = cslr_p;
2542
2543       sched_analyze_2 (deps, SET_SRC (x), insn);
2544
2545       can_start_lhs_rhs_p = false;
2546     }
2547 }
2548
2549 /* Analyze the uses of memory and registers in rtx X in INSN.  */
2550 static void
2551 sched_analyze_2 (struct deps_desc *deps, rtx x, rtx insn)
2552 {
2553   int i;
2554   int j;
2555   enum rtx_code code;
2556   const char *fmt;
2557   bool cslr_p = can_start_lhs_rhs_p;
2558
2559   can_start_lhs_rhs_p = false;
2560
2561   gcc_assert (x);
2562   if (x == 0)
2563     return;
2564
2565   if (cslr_p && sched_deps_info->start_rhs)
2566     sched_deps_info->start_rhs (x);
2567
2568   code = GET_CODE (x);
2569
2570   switch (code)
2571     {
2572     CASE_CONST_ANY:
2573     case SYMBOL_REF:
2574     case CONST:
2575     case LABEL_REF:
2576       /* Ignore constants.  */
2577       if (cslr_p && sched_deps_info->finish_rhs)
2578         sched_deps_info->finish_rhs ();
2579
2580       return;
2581
2582 #ifdef HAVE_cc0
2583     case CC0:
2584       /* User of CC0 depends on immediately preceding insn.  */
2585       SCHED_GROUP_P (insn) = 1;
2586        /* Don't move CC0 setter to another block (it can set up the
2587         same flag for previous CC0 users which is safe).  */
2588       CANT_MOVE (prev_nonnote_insn (insn)) = 1;
2589
2590       if (cslr_p && sched_deps_info->finish_rhs)
2591         sched_deps_info->finish_rhs ();
2592
2593       return;
2594 #endif
2595
2596     case REG:
2597       {
2598         int regno = REGNO (x);
2599         enum machine_mode mode = GET_MODE (x);
2600
2601         sched_analyze_reg (deps, regno, mode, USE, insn);
2602
2603 #ifdef STACK_REGS
2604       /* Treat all reads of a stack register as modifying the TOS.  */
2605       if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2606         {
2607           /* Avoid analyzing the same register twice.  */
2608           if (regno != FIRST_STACK_REG)
2609             sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
2610           sched_analyze_reg (deps, FIRST_STACK_REG, mode, SET, insn);
2611         }
2612 #endif
2613
2614         if (cslr_p && sched_deps_info->finish_rhs)
2615           sched_deps_info->finish_rhs ();
2616
2617         return;
2618       }
2619
2620     case MEM:
2621       {
2622         /* Reading memory.  */
2623         rtx u;
2624         rtx pending, pending_mem;
2625         rtx t = x;
2626
2627         if (sched_deps_info->use_cselib)
2628           {
2629             enum machine_mode address_mode = get_address_mode (t);
2630
2631             t = shallow_copy_rtx (t);
2632             cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2633                                      GET_MODE (t), insn);
2634             XEXP (t, 0)
2635               = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
2636                                                   insn);
2637           }
2638
2639         if (!DEBUG_INSN_P (insn))
2640           {
2641             t = canon_rtx (t);
2642             pending = deps->pending_read_insns;
2643             pending_mem = deps->pending_read_mems;
2644             while (pending)
2645               {
2646                 if (read_dependence (XEXP (pending_mem, 0), t)
2647                     && ! sched_insns_conditions_mutex_p (insn,
2648                                                          XEXP (pending, 0)))
2649                   note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2650                                 DEP_ANTI);
2651
2652                 pending = XEXP (pending, 1);
2653                 pending_mem = XEXP (pending_mem, 1);
2654               }
2655
2656             pending = deps->pending_write_insns;
2657             pending_mem = deps->pending_write_mems;
2658             while (pending)
2659               {
2660                 if (true_dependence (XEXP (pending_mem, 0), VOIDmode, t)
2661                     && ! sched_insns_conditions_mutex_p (insn,
2662                                                          XEXP (pending, 0)))
2663                   note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2664                                 sched_deps_info->generate_spec_deps
2665                                 ? BEGIN_DATA | DEP_TRUE : DEP_TRUE);
2666
2667                 pending = XEXP (pending, 1);
2668                 pending_mem = XEXP (pending_mem, 1);
2669               }
2670
2671             for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
2672               add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
2673
2674             for (u = deps->pending_jump_insns; u; u = XEXP (u, 1))
2675               if (deps_may_trap_p (x))
2676                 {
2677                   if ((sched_deps_info->generate_spec_deps)
2678                       && sel_sched_p () && (spec_info->mask & BEGIN_CONTROL))
2679                     {
2680                       ds_t ds = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
2681                                               MAX_DEP_WEAK);
2682
2683                       note_dep (XEXP (u, 0), ds);
2684                     }
2685                   else
2686                     add_dependence (insn, XEXP (u, 0), REG_DEP_CONTROL);
2687                 }
2688           }
2689
2690         /* Always add these dependencies to pending_reads, since
2691            this insn may be followed by a write.  */
2692         if (!deps->readonly)
2693           {
2694             if ((deps->pending_read_list_length
2695                  + deps->pending_write_list_length)
2696                 > MAX_PENDING_LIST_LENGTH
2697                 && !DEBUG_INSN_P (insn))
2698               flush_pending_lists (deps, insn, true, true);
2699             add_insn_mem_dependence (deps, true, insn, x);
2700           }
2701
2702         sched_analyze_2 (deps, XEXP (x, 0), insn);
2703
2704         if (cslr_p && sched_deps_info->finish_rhs)
2705           sched_deps_info->finish_rhs ();
2706
2707         return;
2708       }
2709
2710     /* Force pending stores to memory in case a trap handler needs them.  */
2711     case TRAP_IF:
2712       flush_pending_lists (deps, insn, true, false);
2713       break;
2714
2715     case PREFETCH:
2716       if (PREFETCH_SCHEDULE_BARRIER_P (x))
2717         reg_pending_barrier = TRUE_BARRIER;
2718       /* Prefetch insn contains addresses only.  So if the prefetch
2719          address has no registers, there will be no dependencies on
2720          the prefetch insn.  This is wrong with result code
2721          correctness point of view as such prefetch can be moved below
2722          a jump insn which usually generates MOVE_BARRIER preventing
2723          to move insns containing registers or memories through the
2724          barrier.  It is also wrong with generated code performance
2725          point of view as prefetch withouth dependecies will have a
2726          tendency to be issued later instead of earlier.  It is hard
2727          to generate accurate dependencies for prefetch insns as
2728          prefetch has only the start address but it is better to have
2729          something than nothing.  */
2730       if (!deps->readonly)
2731         {
2732           rtx x = gen_rtx_MEM (Pmode, XEXP (PATTERN (insn), 0));
2733           if (sched_deps_info->use_cselib)
2734             cselib_lookup_from_insn (x, Pmode, true, VOIDmode, insn);
2735           add_insn_mem_dependence (deps, true, insn, x);
2736         }
2737       break;
2738
2739     case UNSPEC_VOLATILE:
2740       flush_pending_lists (deps, insn, true, true);
2741       /* FALLTHRU */
2742
2743     case ASM_OPERANDS:
2744     case ASM_INPUT:
2745       {
2746         /* Traditional and volatile asm instructions must be considered to use
2747            and clobber all hard registers, all pseudo-registers and all of
2748            memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
2749
2750            Consider for instance a volatile asm that changes the fpu rounding
2751            mode.  An insn should not be moved across this even if it only uses
2752            pseudo-regs because it might give an incorrectly rounded result.  */
2753         if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
2754           reg_pending_barrier = TRUE_BARRIER;
2755
2756         /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2757            We can not just fall through here since then we would be confused
2758            by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2759            traditional asms unlike their normal usage.  */
2760
2761         if (code == ASM_OPERANDS)
2762           {
2763             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
2764               sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
2765
2766             if (cslr_p && sched_deps_info->finish_rhs)
2767               sched_deps_info->finish_rhs ();
2768
2769             return;
2770           }
2771         break;
2772       }
2773
2774     case PRE_DEC:
2775     case POST_DEC:
2776     case PRE_INC:
2777     case POST_INC:
2778       /* These both read and modify the result.  We must handle them as writes
2779          to get proper dependencies for following instructions.  We must handle
2780          them as reads to get proper dependencies from this to previous
2781          instructions.  Thus we need to pass them to both sched_analyze_1
2782          and sched_analyze_2.  We must call sched_analyze_2 first in order
2783          to get the proper antecedent for the read.  */
2784       sched_analyze_2 (deps, XEXP (x, 0), insn);
2785       sched_analyze_1 (deps, x, insn);
2786
2787       if (cslr_p && sched_deps_info->finish_rhs)
2788         sched_deps_info->finish_rhs ();
2789
2790       return;
2791
2792     case POST_MODIFY:
2793     case PRE_MODIFY:
2794       /* op0 = op0 + op1 */
2795       sched_analyze_2 (deps, XEXP (x, 0), insn);
2796       sched_analyze_2 (deps, XEXP (x, 1), insn);
2797       sched_analyze_1 (deps, x, insn);
2798
2799       if (cslr_p && sched_deps_info->finish_rhs)
2800         sched_deps_info->finish_rhs ();
2801
2802       return;
2803
2804     default:
2805       break;
2806     }
2807
2808   /* Other cases: walk the insn.  */
2809   fmt = GET_RTX_FORMAT (code);
2810   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2811     {
2812       if (fmt[i] == 'e')
2813         sched_analyze_2 (deps, XEXP (x, i), insn);
2814       else if (fmt[i] == 'E')
2815         for (j = 0; j < XVECLEN (x, i); j++)
2816           sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
2817     }
2818
2819   if (cslr_p && sched_deps_info->finish_rhs)
2820     sched_deps_info->finish_rhs ();
2821 }
2822
2823 /* Try to group comparison and the following conditional jump INSN if
2824    they're already adjacent. This is to prevent scheduler from scheduling
2825    them apart.  */
2826
2827 static void
2828 try_group_insn (rtx insn)
2829 {
2830   unsigned int condreg1, condreg2;
2831   rtx cc_reg_1;
2832   rtx prev;
2833
2834   if (!any_condjump_p (insn))
2835     return;
2836
2837   targetm.fixed_condition_code_regs (&condreg1, &condreg2);
2838   cc_reg_1 = gen_rtx_REG (CCmode, condreg1);
2839   prev = prev_nonnote_nondebug_insn (insn);
2840   if (!reg_referenced_p (cc_reg_1, PATTERN (insn))
2841       || !prev
2842       || !modified_in_p (cc_reg_1, prev))
2843     return;
2844
2845   /* Different microarchitectures support macro fusions for different
2846      combinations of insn pairs.  */
2847   if (!targetm.sched.macro_fusion_pair_p
2848       || !targetm.sched.macro_fusion_pair_p (prev, insn))
2849     return;
2850
2851   SCHED_GROUP_P (insn) = 1;
2852 }
2853
2854 /* Analyze an INSN with pattern X to find all dependencies.  */
2855 static void
2856 sched_analyze_insn (struct deps_desc *deps, rtx x, rtx insn)
2857 {
2858   RTX_CODE code = GET_CODE (x);
2859   rtx link;
2860   unsigned i;
2861   reg_set_iterator rsi;
2862
2863   if (! reload_completed)
2864     {
2865       HARD_REG_SET temp;
2866
2867       extract_insn (insn);
2868       preprocess_constraints ();
2869       ira_implicitly_set_insn_hard_regs (&temp);
2870       AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
2871       IOR_HARD_REG_SET (implicit_reg_pending_clobbers, temp);
2872     }
2873
2874   can_start_lhs_rhs_p = (NONJUMP_INSN_P (insn)
2875                          && code == SET);
2876
2877   /* Group compare and branch insns for macro-fusion.  */
2878   if (targetm.sched.macro_fusion_p
2879       && targetm.sched.macro_fusion_p ())
2880     try_group_insn (insn);
2881
2882   if (may_trap_p (x))
2883     /* Avoid moving trapping instructions across function calls that might
2884        not always return.  */
2885     add_dependence_list (insn, deps->last_function_call_may_noreturn,
2886                          1, REG_DEP_ANTI, true);
2887
2888   /* We must avoid creating a situation in which two successors of the
2889      current block have different unwind info after scheduling.  If at any
2890      point the two paths re-join this leads to incorrect unwind info.  */
2891   /* ??? There are certain situations involving a forced frame pointer in
2892      which, with extra effort, we could fix up the unwind info at a later
2893      CFG join.  However, it seems better to notice these cases earlier
2894      during prologue generation and avoid marking the frame pointer setup
2895      as frame-related at all.  */
2896   if (RTX_FRAME_RELATED_P (insn))
2897     {
2898       /* Make sure prologue insn is scheduled before next jump.  */
2899       deps->sched_before_next_jump
2900         = alloc_INSN_LIST (insn, deps->sched_before_next_jump);
2901
2902       /* Make sure epilogue insn is scheduled after preceding jumps.  */
2903       add_dependence_list (insn, deps->pending_jump_insns, 1, REG_DEP_ANTI,
2904                            true);
2905     }
2906
2907   if (code == COND_EXEC)
2908     {
2909       sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
2910
2911       /* ??? Should be recording conditions so we reduce the number of
2912          false dependencies.  */
2913       x = COND_EXEC_CODE (x);
2914       code = GET_CODE (x);
2915     }
2916   if (code == SET || code == CLOBBER)
2917     {
2918       sched_analyze_1 (deps, x, insn);
2919
2920       /* Bare clobber insns are used for letting life analysis, reg-stack
2921          and others know that a value is dead.  Depend on the last call
2922          instruction so that reg-stack won't get confused.  */
2923       if (code == CLOBBER)
2924         add_dependence_list (insn, deps->last_function_call, 1,
2925                              REG_DEP_OUTPUT, true);
2926     }
2927   else if (code == PARALLEL)
2928     {
2929       for (i = XVECLEN (x, 0); i--;)
2930         {
2931           rtx sub = XVECEXP (x, 0, i);
2932           code = GET_CODE (sub);
2933
2934           if (code == COND_EXEC)
2935             {
2936               sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
2937               sub = COND_EXEC_CODE (sub);
2938               code = GET_CODE (sub);
2939             }
2940           if (code == SET || code == CLOBBER)
2941             sched_analyze_1 (deps, sub, insn);
2942           else
2943             sched_analyze_2 (deps, sub, insn);
2944         }
2945     }
2946   else
2947     sched_analyze_2 (deps, x, insn);
2948
2949   /* Mark registers CLOBBERED or used by called function.  */
2950   if (CALL_P (insn))
2951     {
2952       for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
2953         {
2954           if (GET_CODE (XEXP (link, 0)) == CLOBBER)
2955             sched_analyze_1 (deps, XEXP (link, 0), insn);
2956           else if (GET_CODE (XEXP (link, 0)) != SET)
2957             sched_analyze_2 (deps, XEXP (link, 0), insn);
2958         }
2959       /* Don't schedule anything after a tail call, tail call needs
2960          to use at least all call-saved registers.  */
2961       if (SIBLING_CALL_P (insn))
2962         reg_pending_barrier = TRUE_BARRIER;
2963       else if (find_reg_note (insn, REG_SETJMP, NULL))
2964         reg_pending_barrier = MOVE_BARRIER;
2965     }
2966
2967   if (JUMP_P (insn))
2968     {
2969       rtx next;
2970       next = next_nonnote_nondebug_insn (insn);
2971       if (next && BARRIER_P (next))
2972         reg_pending_barrier = MOVE_BARRIER;
2973       else
2974         {
2975           rtx pending, pending_mem;
2976
2977           if (sched_deps_info->compute_jump_reg_dependencies)
2978             {
2979               (*sched_deps_info->compute_jump_reg_dependencies)
2980                 (insn, reg_pending_control_uses);
2981
2982               /* Make latency of jump equal to 0 by using anti-dependence.  */
2983               EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
2984                 {
2985                   struct deps_reg *reg_last = &deps->reg_last[i];
2986                   add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI,
2987                                        false);
2988                   add_dependence_list (insn, reg_last->implicit_sets,
2989                                        0, REG_DEP_ANTI, false);
2990                   add_dependence_list (insn, reg_last->clobbers, 0,
2991                                        REG_DEP_ANTI, false);
2992                 }
2993             }
2994
2995           /* All memory writes and volatile reads must happen before the
2996              jump.  Non-volatile reads must happen before the jump iff
2997              the result is needed by the above register used mask.  */
2998
2999           pending = deps->pending_write_insns;
3000           pending_mem = deps->pending_write_mems;
3001           while (pending)
3002             {
3003               if (! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
3004                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
3005               pending = XEXP (pending, 1);
3006               pending_mem = XEXP (pending_mem, 1);
3007             }
3008
3009           pending = deps->pending_read_insns;
3010           pending_mem = deps->pending_read_mems;
3011           while (pending)
3012             {
3013               if (MEM_VOLATILE_P (XEXP (pending_mem, 0))
3014                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
3015                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
3016               pending = XEXP (pending, 1);
3017               pending_mem = XEXP (pending_mem, 1);
3018             }
3019
3020           add_dependence_list (insn, deps->last_pending_memory_flush, 1,
3021                                REG_DEP_ANTI, true);
3022           add_dependence_list (insn, deps->pending_jump_insns, 1,
3023                                REG_DEP_ANTI, true);
3024         }
3025     }
3026
3027   /* If this instruction can throw an exception, then moving it changes
3028      where block boundaries fall.  This is mighty confusing elsewhere.
3029      Therefore, prevent such an instruction from being moved.  Same for
3030      non-jump instructions that define block boundaries.
3031      ??? Unclear whether this is still necessary in EBB mode.  If not,
3032      add_branch_dependences should be adjusted for RGN mode instead.  */
3033   if (((CALL_P (insn) || JUMP_P (insn)) && can_throw_internal (insn))
3034       || (NONJUMP_INSN_P (insn) && control_flow_insn_p (insn)))
3035     reg_pending_barrier = MOVE_BARRIER;
3036
3037   if (sched_pressure != SCHED_PRESSURE_NONE)
3038     {
3039       setup_insn_reg_uses (deps, insn);
3040       init_insn_reg_pressure_info (insn);
3041     }
3042
3043   /* Add register dependencies for insn.  */
3044   if (DEBUG_INSN_P (insn))
3045     {
3046       rtx prev = deps->last_debug_insn;
3047       rtx u;
3048
3049       if (!deps->readonly)
3050         deps->last_debug_insn = insn;
3051
3052       if (prev)
3053         add_dependence (insn, prev, REG_DEP_ANTI);
3054
3055       add_dependence_list (insn, deps->last_function_call, 1,
3056                            REG_DEP_ANTI, false);
3057
3058       if (!sel_sched_p ())
3059         for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
3060           add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3061
3062       EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
3063         {
3064           struct deps_reg *reg_last = &deps->reg_last[i];
3065           add_dependence_list (insn, reg_last->sets, 1, REG_DEP_ANTI, false);
3066           /* There's no point in making REG_DEP_CONTROL dependencies for
3067              debug insns.  */
3068           add_dependence_list (insn, reg_last->clobbers, 1, REG_DEP_ANTI,
3069                                false);
3070
3071           if (!deps->readonly)
3072             reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3073         }
3074       CLEAR_REG_SET (reg_pending_uses);
3075
3076       /* Quite often, a debug insn will refer to stuff in the
3077          previous instruction, but the reason we want this
3078          dependency here is to make sure the scheduler doesn't
3079          gratuitously move a debug insn ahead.  This could dirty
3080          DF flags and cause additional analysis that wouldn't have
3081          occurred in compilation without debug insns, and such
3082          additional analysis can modify the generated code.  */
3083       prev = PREV_INSN (insn);
3084
3085       if (prev && NONDEBUG_INSN_P (prev))
3086         add_dependence (insn, prev, REG_DEP_ANTI);
3087     }
3088   else
3089     {
3090       regset_head set_or_clobbered;
3091
3092       EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
3093         {
3094           struct deps_reg *reg_last = &deps->reg_last[i];
3095           add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false);
3096           add_dependence_list (insn, reg_last->implicit_sets, 0, REG_DEP_ANTI,
3097                                false);
3098           add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE,
3099                                false);
3100
3101           if (!deps->readonly)
3102             {
3103               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3104               reg_last->uses_length++;
3105             }
3106         }
3107
3108       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3109         if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i))
3110           {
3111             struct deps_reg *reg_last = &deps->reg_last[i];
3112             add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false);
3113             add_dependence_list (insn, reg_last->implicit_sets, 0,
3114                                  REG_DEP_ANTI, false);
3115             add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE,
3116                                  false);
3117
3118             if (!deps->readonly)
3119               {
3120                 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3121                 reg_last->uses_length++;
3122               }
3123           }
3124
3125       if (targetm.sched.exposed_pipeline)
3126         {
3127           INIT_REG_SET (&set_or_clobbered);
3128           bitmap_ior (&set_or_clobbered, reg_pending_clobbers,
3129                       reg_pending_sets);
3130           EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered, 0, i, rsi)
3131             {
3132               struct deps_reg *reg_last = &deps->reg_last[i];
3133               rtx list;
3134               for (list = reg_last->uses; list; list = XEXP (list, 1))
3135                 {
3136                   rtx other = XEXP (list, 0);
3137                   if (INSN_CACHED_COND (other) != const_true_rtx
3138                       && refers_to_regno_p (i, i + 1, INSN_CACHED_COND (other), NULL))
3139                     INSN_CACHED_COND (other) = const_true_rtx;
3140                 }
3141             }
3142         }
3143
3144       /* If the current insn is conditional, we can't free any
3145          of the lists.  */
3146       if (sched_has_condition_p (insn))
3147         {
3148           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3149             {
3150               struct deps_reg *reg_last = &deps->reg_last[i];
3151               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3152                                    false);
3153               add_dependence_list (insn, reg_last->implicit_sets, 0,
3154                                    REG_DEP_ANTI, false);
3155               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3156                                    false);
3157               add_dependence_list (insn, reg_last->control_uses, 0,
3158                                    REG_DEP_CONTROL, false);
3159
3160               if (!deps->readonly)
3161                 {
3162                   reg_last->clobbers
3163                     = alloc_INSN_LIST (insn, reg_last->clobbers);
3164                   reg_last->clobbers_length++;
3165                 }
3166             }
3167           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3168             {
3169               struct deps_reg *reg_last = &deps->reg_last[i];
3170               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3171                                    false);
3172               add_dependence_list (insn, reg_last->implicit_sets, 0,
3173                                    REG_DEP_ANTI, false);
3174               add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT,
3175                                    false);
3176               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3177                                    false);
3178               add_dependence_list (insn, reg_last->control_uses, 0,
3179                                    REG_DEP_CONTROL, false);
3180
3181               if (!deps->readonly)
3182                 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3183             }
3184         }
3185       else
3186         {
3187           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3188             {
3189               struct deps_reg *reg_last = &deps->reg_last[i];
3190               if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
3191                   || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
3192                 {
3193                   add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3194                                                 REG_DEP_OUTPUT, false);
3195                   add_dependence_list_and_free (deps, insn,
3196                                                 &reg_last->implicit_sets, 0,
3197                                                 REG_DEP_ANTI, false);
3198                   add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3199                                                 REG_DEP_ANTI, false);
3200                   add_dependence_list_and_free (deps, insn,
3201                                                 &reg_last->control_uses, 0,
3202                                                 REG_DEP_ANTI, false);
3203                   add_dependence_list_and_free (deps, insn,
3204                                                 &reg_last->clobbers, 0,
3205                                                 REG_DEP_OUTPUT, false);
3206
3207                   if (!deps->readonly)
3208                     {
3209                       reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3210                       reg_last->clobbers_length = 0;
3211                       reg_last->uses_length = 0;
3212                     }
3213                 }
3214               else
3215                 {
3216                   add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3217                                        false);
3218                   add_dependence_list (insn, reg_last->implicit_sets, 0,
3219                                        REG_DEP_ANTI, false);
3220                   add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3221                                        false);
3222                   add_dependence_list (insn, reg_last->control_uses, 0,
3223                                        REG_DEP_CONTROL, false);
3224                 }
3225
3226               if (!deps->readonly)
3227                 {
3228                   reg_last->clobbers_length++;
3229                   reg_last->clobbers
3230                     = alloc_INSN_LIST (insn, reg_last->clobbers);
3231                 }
3232             }
3233           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3234             {
3235               struct deps_reg *reg_last = &deps->reg_last[i];
3236
3237               add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3238                                             REG_DEP_OUTPUT, false);
3239               add_dependence_list_and_free (deps, insn,
3240                                             &reg_last->implicit_sets,
3241                                             0, REG_DEP_ANTI, false);
3242               add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3243                                             REG_DEP_OUTPUT, false);
3244               add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3245                                             REG_DEP_ANTI, false);
3246               add_dependence_list (insn, reg_last->control_uses, 0,
3247                                    REG_DEP_CONTROL, false);
3248
3249               if (!deps->readonly)
3250                 {
3251                   reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3252                   reg_last->uses_length = 0;
3253                   reg_last->clobbers_length = 0;
3254                 }
3255             }
3256         }
3257       if (!deps->readonly)
3258         {
3259           EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
3260             {
3261               struct deps_reg *reg_last = &deps->reg_last[i];
3262               reg_last->control_uses
3263                 = alloc_INSN_LIST (insn, reg_last->control_uses);
3264             }
3265         }
3266     }
3267
3268   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3269     if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
3270       {
3271         struct deps_reg *reg_last = &deps->reg_last[i];
3272         add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI, false);
3273         add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI, false);
3274         add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI, false);
3275         add_dependence_list (insn, reg_last->control_uses, 0, REG_DEP_ANTI,
3276                              false);
3277
3278         if (!deps->readonly)
3279           reg_last->implicit_sets
3280             = alloc_INSN_LIST (insn, reg_last->implicit_sets);
3281       }
3282
3283   if (!deps->readonly)
3284     {
3285       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
3286       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
3287       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
3288       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3289         if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i)
3290             || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
3291           SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3292
3293       /* Set up the pending barrier found.  */
3294       deps->last_reg_pending_barrier = reg_pending_barrier;
3295     }
3296
3297   CLEAR_REG_SET (reg_pending_uses);
3298   CLEAR_REG_SET (reg_pending_clobbers);
3299   CLEAR_REG_SET (reg_pending_sets);
3300   CLEAR_REG_SET (reg_pending_control_uses);
3301   CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
3302   CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
3303
3304   /* Add dependencies if a scheduling barrier was found.  */
3305   if (reg_pending_barrier)
3306     {
3307       /* In the case of barrier the most added dependencies are not
3308          real, so we use anti-dependence here.  */
3309       if (sched_has_condition_p (insn))
3310         {
3311           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3312             {
3313               struct deps_reg *reg_last = &deps->reg_last[i];
3314               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3315                                    true);
3316               add_dependence_list (insn, reg_last->sets, 0,
3317                                    reg_pending_barrier == TRUE_BARRIER
3318                                    ? REG_DEP_TRUE : REG_DEP_ANTI, true);
3319               add_dependence_list (insn, reg_last->implicit_sets, 0,
3320                                    REG_DEP_ANTI, true);
3321               add_dependence_list (insn, reg_last->clobbers, 0,
3322                                    reg_pending_barrier == TRUE_BARRIER
3323                                    ? REG_DEP_TRUE : REG_DEP_ANTI, true);
3324             }
3325         }
3326       else
3327         {
3328           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3329             {
3330               struct deps_reg *reg_last = &deps->reg_last[i];
3331               add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3332                                             REG_DEP_ANTI, true);
3333               add_dependence_list_and_free (deps, insn,
3334                                             &reg_last->control_uses, 0,
3335                                             REG_DEP_CONTROL, true);
3336               add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3337                                             reg_pending_barrier == TRUE_BARRIER
3338                                             ? REG_DEP_TRUE : REG_DEP_ANTI,
3339                                             true);
3340               add_dependence_list_and_free (deps, insn,
3341                                             &reg_last->implicit_sets, 0,
3342                                             REG_DEP_ANTI, true);
3343               add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3344                                             reg_pending_barrier == TRUE_BARRIER
3345                                             ? REG_DEP_TRUE : REG_DEP_ANTI,
3346                                             true);
3347
3348               if (!deps->readonly)
3349                 {
3350                   reg_last->uses_length = 0;
3351                   reg_last->clobbers_length = 0;
3352                 }
3353             }
3354         }
3355
3356       if (!deps->readonly)
3357         for (i = 0; i < (unsigned)deps->max_reg; i++)
3358           {
3359             struct deps_reg *reg_last = &deps->reg_last[i];
3360             reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3361             SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3362           }
3363
3364       /* Don't flush pending lists on speculative checks for
3365          selective scheduling.  */
3366       if (!sel_sched_p () || !sel_insn_is_speculation_check (insn))
3367         flush_pending_lists (deps, insn, true, true);
3368
3369       reg_pending_barrier = NOT_A_BARRIER;
3370     }
3371
3372   /* If a post-call group is still open, see if it should remain so.
3373      This insn must be a simple move of a hard reg to a pseudo or
3374      vice-versa.
3375
3376      We must avoid moving these insns for correctness on targets
3377      with small register classes, and for special registers like
3378      PIC_OFFSET_TABLE_REGNUM.  For simplicity, extend this to all
3379      hard regs for all targets.  */
3380
3381   if (deps->in_post_call_group_p)
3382     {
3383       rtx tmp, set = single_set (insn);
3384       int src_regno, dest_regno;
3385
3386       if (set == NULL)
3387         {
3388           if (DEBUG_INSN_P (insn))
3389             /* We don't want to mark debug insns as part of the same
3390                sched group.  We know they really aren't, but if we use
3391                debug insns to tell that a call group is over, we'll
3392                get different code if debug insns are not there and
3393                instructions that follow seem like they should be part
3394                of the call group.
3395
3396                Also, if we did, chain_to_prev_insn would move the
3397                deps of the debug insn to the call insn, modifying
3398                non-debug post-dependency counts of the debug insn
3399                dependencies and otherwise messing with the scheduling
3400                order.
3401
3402                Instead, let such debug insns be scheduled freely, but
3403                keep the call group open in case there are insns that
3404                should be part of it afterwards.  Since we grant debug
3405                insns higher priority than even sched group insns, it
3406                will all turn out all right.  */
3407             goto debug_dont_end_call_group;
3408           else
3409             goto end_call_group;
3410         }
3411
3412       tmp = SET_DEST (set);
3413       if (GET_CODE (tmp) == SUBREG)
3414         tmp = SUBREG_REG (tmp);
3415       if (REG_P (tmp))
3416         dest_regno = REGNO (tmp);
3417       else
3418         goto end_call_group;
3419
3420       tmp = SET_SRC (set);
3421       if (GET_CODE (tmp) == SUBREG)
3422         tmp = SUBREG_REG (tmp);
3423       if ((GET_CODE (tmp) == PLUS
3424            || GET_CODE (tmp) == MINUS)
3425           && REG_P (XEXP (tmp, 0))
3426           && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
3427           && dest_regno == STACK_POINTER_REGNUM)
3428         src_regno = STACK_POINTER_REGNUM;
3429       else if (REG_P (tmp))
3430         src_regno = REGNO (tmp);
3431       else
3432         goto end_call_group;
3433
3434       if (src_regno < FIRST_PSEUDO_REGISTER
3435           || dest_regno < FIRST_PSEUDO_REGISTER)
3436         {
3437           if (!deps->readonly
3438               && deps->in_post_call_group_p == post_call_initial)
3439             deps->in_post_call_group_p = post_call;
3440
3441           if (!sel_sched_p () || sched_emulate_haifa_p)
3442             {
3443               SCHED_GROUP_P (insn) = 1;
3444               CANT_MOVE (insn) = 1;
3445             }
3446         }
3447       else
3448         {
3449         end_call_group:
3450           if (!deps->readonly)
3451             deps->in_post_call_group_p = not_post_call;
3452         }
3453     }
3454
3455  debug_dont_end_call_group:
3456   if ((current_sched_info->flags & DO_SPECULATION)
3457       && !sched_insn_is_legitimate_for_speculation_p (insn, 0))
3458     /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3459        be speculated.  */
3460     {
3461       if (sel_sched_p ())
3462         sel_mark_hard_insn (insn);
3463       else
3464         {
3465           sd_iterator_def sd_it;
3466           dep_t dep;
3467
3468           for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3469                sd_iterator_cond (&sd_it, &dep);)
3470             change_spec_dep_to_hard (sd_it);
3471         }
3472     }
3473
3474   /* We do not yet have code to adjust REG_ARGS_SIZE, therefore we must
3475      honor their original ordering.  */
3476   if (find_reg_note (insn, REG_ARGS_SIZE, NULL))
3477     {
3478       if (deps->last_args_size)
3479         add_dependence (insn, deps->last_args_size, REG_DEP_OUTPUT);
3480       deps->last_args_size = insn;
3481     }
3482 }
3483
3484 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3485    longjmp, loop forever, ...).  */
3486 /* FIXME: Why can't this function just use flags_from_decl_or_type and
3487    test for ECF_NORETURN?  */
3488 static bool
3489 call_may_noreturn_p (rtx insn)
3490 {
3491   rtx call;
3492
3493   /* const or pure calls that aren't looping will always return.  */
3494   if (RTL_CONST_OR_PURE_CALL_P (insn)
3495       && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))
3496     return false;
3497
3498   call = get_call_rtx_from (insn);
3499   if (call && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
3500     {
3501       rtx symbol = XEXP (XEXP (call, 0), 0);
3502       if (SYMBOL_REF_DECL (symbol)
3503           && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
3504         {
3505           if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
3506               == BUILT_IN_NORMAL)
3507             switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol)))
3508               {
3509               case BUILT_IN_BCMP:
3510               case BUILT_IN_BCOPY:
3511               case BUILT_IN_BZERO:
3512               case BUILT_IN_INDEX:
3513               case BUILT_IN_MEMCHR:
3514               case BUILT_IN_MEMCMP:
3515               case BUILT_IN_MEMCPY:
3516               case BUILT_IN_MEMMOVE:
3517               case BUILT_IN_MEMPCPY:
3518               case BUILT_IN_MEMSET:
3519               case BUILT_IN_RINDEX:
3520               case BUILT_IN_STPCPY:
3521               case BUILT_IN_STPNCPY:
3522               case BUILT_IN_STRCAT:
3523               case BUILT_IN_STRCHR:
3524               case BUILT_IN_STRCMP:
3525               case BUILT_IN_STRCPY:
3526               case BUILT_IN_STRCSPN:
3527               case BUILT_IN_STRLEN:
3528               case BUILT_IN_STRNCAT:
3529               case BUILT_IN_STRNCMP:
3530               case BUILT_IN_STRNCPY:
3531               case BUILT_IN_STRPBRK:
3532               case BUILT_IN_STRRCHR:
3533               case BUILT_IN_STRSPN:
3534               case BUILT_IN_STRSTR:
3535                 /* Assume certain string/memory builtins always return.  */
3536                 return false;
3537               default:
3538                 break;
3539               }
3540         }
3541     }
3542
3543   /* For all other calls assume that they might not always return.  */
3544   return true;
3545 }
3546
3547 /* Return true if INSN should be made dependent on the previous instruction
3548    group, and if all INSN's dependencies should be moved to the first
3549    instruction of that group.  */
3550
3551 static bool
3552 chain_to_prev_insn_p (rtx insn)
3553 {
3554   rtx prev, x;
3555
3556   /* INSN forms a group with the previous instruction.  */
3557   if (SCHED_GROUP_P (insn))
3558     return true;
3559
3560   /* If the previous instruction clobbers a register R and this one sets
3561      part of R, the clobber was added specifically to help us track the
3562      liveness of R.  There's no point scheduling the clobber and leaving
3563      INSN behind, especially if we move the clobber to another block.  */
3564   prev = prev_nonnote_nondebug_insn (insn);
3565   if (prev
3566       && INSN_P (prev)
3567       && BLOCK_FOR_INSN (prev) == BLOCK_FOR_INSN (insn)
3568       && GET_CODE (PATTERN (prev)) == CLOBBER)
3569     {
3570       x = XEXP (PATTERN (prev), 0);
3571       if (set_of (x, insn))
3572         return true;
3573     }
3574
3575   return false;
3576 }
3577
3578 /* Analyze INSN with DEPS as a context.  */
3579 void
3580 deps_analyze_insn (struct deps_desc *deps, rtx insn)
3581 {
3582   if (sched_deps_info->start_insn)
3583     sched_deps_info->start_insn (insn);
3584
3585   /* Record the condition for this insn.  */
3586   if (NONDEBUG_INSN_P (insn))
3587     {
3588       rtx t;
3589       sched_get_condition_with_rev (insn, NULL);
3590       t = INSN_CACHED_COND (insn);
3591       INSN_COND_DEPS (insn) = NULL_RTX;
3592       if (reload_completed
3593           && (current_sched_info->flags & DO_PREDICATION)
3594           && COMPARISON_P (t)
3595           && REG_P (XEXP (t, 0))
3596           && CONSTANT_P (XEXP (t, 1)))
3597         {
3598           unsigned int regno;
3599           int nregs;
3600           t = XEXP (t, 0);
3601           regno = REGNO (t);
3602           nregs = hard_regno_nregs[regno][GET_MODE (t)];
3603           t = NULL_RTX;
3604           while (nregs-- > 0)
3605             {
3606               struct deps_reg *reg_last = &deps->reg_last[regno + nregs];
3607               t = concat_INSN_LIST (reg_last->sets, t);
3608               t = concat_INSN_LIST (reg_last->clobbers, t);
3609               t = concat_INSN_LIST (reg_last->implicit_sets, t);
3610             }
3611           INSN_COND_DEPS (insn) = t;
3612         }
3613     }
3614
3615   if (JUMP_P (insn))
3616     {
3617       /* Make each JUMP_INSN (but not a speculative check)
3618          a scheduling barrier for memory references.  */
3619       if (!deps->readonly
3620           && !(sel_sched_p ()
3621                && sel_insn_is_speculation_check (insn)))
3622         {
3623           /* Keep the list a reasonable size.  */
3624           if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
3625             flush_pending_lists (deps, insn, true, true);
3626           else
3627             deps->pending_jump_insns
3628               = alloc_INSN_LIST (insn, deps->pending_jump_insns);
3629         }
3630
3631       /* For each insn which shouldn't cross a jump, add a dependence.  */
3632       add_dependence_list_and_free (deps, insn,
3633                                     &deps->sched_before_next_jump, 1,
3634                                     REG_DEP_ANTI, true);
3635
3636       sched_analyze_insn (deps, PATTERN (insn), insn);
3637     }
3638   else if (NONJUMP_INSN_P (insn) || DEBUG_INSN_P (insn))
3639     {
3640       sched_analyze_insn (deps, PATTERN (insn), insn);
3641     }
3642   else if (CALL_P (insn))
3643     {
3644       int i;
3645
3646       CANT_MOVE (insn) = 1;
3647
3648       if (find_reg_note (insn, REG_SETJMP, NULL))
3649         {
3650           /* This is setjmp.  Assume that all registers, not just
3651              hard registers, may be clobbered by this call.  */
3652           reg_pending_barrier = MOVE_BARRIER;
3653         }
3654       else
3655         {
3656           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3657             /* A call may read and modify global register variables.  */
3658             if (global_regs[i])
3659               {
3660                 SET_REGNO_REG_SET (reg_pending_sets, i);
3661                 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3662               }
3663           /* Other call-clobbered hard regs may be clobbered.
3664              Since we only have a choice between 'might be clobbered'
3665              and 'definitely not clobbered', we must include all
3666              partly call-clobbered registers here.  */
3667             else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
3668                      || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3669               SET_REGNO_REG_SET (reg_pending_clobbers, i);
3670           /* We don't know what set of fixed registers might be used
3671              by the function, but it is certain that the stack pointer
3672              is among them, but be conservative.  */
3673             else if (fixed_regs[i])
3674               SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3675           /* The frame pointer is normally not used by the function
3676              itself, but by the debugger.  */
3677           /* ??? MIPS o32 is an exception.  It uses the frame pointer
3678              in the macro expansion of jal but does not represent this
3679              fact in the call_insn rtl.  */
3680             else if (i == FRAME_POINTER_REGNUM
3681                      || (i == HARD_FRAME_POINTER_REGNUM
3682                          && (! reload_completed || frame_pointer_needed)))
3683               SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3684         }
3685
3686       /* For each insn which shouldn't cross a call, add a dependence
3687          between that insn and this call insn.  */
3688       add_dependence_list_and_free (deps, insn,
3689                                     &deps->sched_before_next_call, 1,
3690                                     REG_DEP_ANTI, true);
3691
3692       sched_analyze_insn (deps, PATTERN (insn), insn);
3693
3694       /* If CALL would be in a sched group, then this will violate
3695          convention that sched group insns have dependencies only on the
3696          previous instruction.
3697
3698          Of course one can say: "Hey!  What about head of the sched group?"
3699          And I will answer: "Basic principles (one dep per insn) are always
3700          the same."  */
3701       gcc_assert (!SCHED_GROUP_P (insn));
3702
3703       /* In the absence of interprocedural alias analysis, we must flush
3704          all pending reads and writes, and start new dependencies starting
3705          from here.  But only flush writes for constant calls (which may
3706          be passed a pointer to something we haven't written yet).  */
3707       flush_pending_lists (deps, insn, true, ! RTL_CONST_OR_PURE_CALL_P (insn));
3708
3709       if (!deps->readonly)
3710         {
3711           /* Remember the last function call for limiting lifetimes.  */
3712           free_INSN_LIST_list (&deps->last_function_call);
3713           deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3714
3715           if (call_may_noreturn_p (insn))
3716             {
3717               /* Remember the last function call that might not always return
3718                  normally for limiting moves of trapping insns.  */
3719               free_INSN_LIST_list (&deps->last_function_call_may_noreturn);
3720               deps->last_function_call_may_noreturn
3721                 = alloc_INSN_LIST (insn, NULL_RTX);
3722             }
3723
3724           /* Before reload, begin a post-call group, so as to keep the
3725              lifetimes of hard registers correct.  */
3726           if (! reload_completed)
3727             deps->in_post_call_group_p = post_call;
3728         }
3729     }
3730
3731   if (sched_deps_info->use_cselib)
3732     cselib_process_insn (insn);
3733
3734   if (sched_deps_info->finish_insn)
3735     sched_deps_info->finish_insn ();
3736
3737   /* Fixup the dependencies in the sched group.  */
3738   if ((NONJUMP_INSN_P (insn) || JUMP_P (insn))
3739       && chain_to_prev_insn_p (insn)
3740       && !sel_sched_p ())
3741     chain_to_prev_insn (insn);
3742 }
3743
3744 /* Initialize DEPS for the new block beginning with HEAD.  */
3745 void
3746 deps_start_bb (struct deps_desc *deps, rtx head)
3747 {
3748   gcc_assert (!deps->readonly);
3749
3750   /* Before reload, if the previous block ended in a call, show that
3751      we are inside a post-call group, so as to keep the lifetimes of
3752      hard registers correct.  */
3753   if (! reload_completed && !LABEL_P (head))
3754     {
3755       rtx insn = prev_nonnote_nondebug_insn (head);
3756
3757       if (insn && CALL_P (insn))
3758         deps->in_post_call_group_p = post_call_initial;
3759     }
3760 }
3761
3762 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3763    dependencies for each insn.  */
3764 void
3765 sched_analyze (struct deps_desc *deps, rtx head, rtx tail)
3766 {
3767   rtx insn;
3768
3769   if (sched_deps_info->use_cselib)
3770     cselib_init (CSELIB_RECORD_MEMORY);
3771
3772   deps_start_bb (deps, head);
3773
3774   for (insn = head;; insn = NEXT_INSN (insn))
3775     {
3776
3777       if (INSN_P (insn))
3778         {
3779           /* And initialize deps_lists.  */
3780           sd_init_insn (insn);
3781           /* Clean up SCHED_GROUP_P which may be set by last
3782              scheduler pass.  */
3783           if (SCHED_GROUP_P (insn))
3784             SCHED_GROUP_P (insn) = 0;
3785         }
3786
3787       deps_analyze_insn (deps, insn);
3788
3789       if (insn == tail)
3790         {
3791           if (sched_deps_info->use_cselib)
3792             cselib_finish ();
3793           return;
3794         }
3795     }
3796   gcc_unreachable ();
3797 }
3798
3799 /* Helper for sched_free_deps ().
3800    Delete INSN's (RESOLVED_P) backward dependencies.  */
3801 static void
3802 delete_dep_nodes_in_back_deps (rtx insn, bool resolved_p)
3803 {
3804   sd_iterator_def sd_it;
3805   dep_t dep;
3806   sd_list_types_def types;
3807
3808   if (resolved_p)
3809     types = SD_LIST_RES_BACK;
3810   else
3811     types = SD_LIST_BACK;
3812
3813   for (sd_it = sd_iterator_start (insn, types);
3814        sd_iterator_cond (&sd_it, &dep);)
3815     {
3816       dep_link_t link = *sd_it.linkp;
3817       dep_node_t node = DEP_LINK_NODE (link);
3818       deps_list_t back_list;
3819       deps_list_t forw_list;
3820
3821       get_back_and_forw_lists (dep, resolved_p, &back_list, &forw_list);
3822       remove_from_deps_list (link, back_list);
3823       delete_dep_node (node);
3824     }
3825 }
3826
3827 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3828    deps_lists.  */
3829 void
3830 sched_free_deps (rtx head, rtx tail, bool resolved_p)
3831 {
3832   rtx insn;
3833   rtx next_tail = NEXT_INSN (tail);
3834
3835   /* We make two passes since some insns may be scheduled before their
3836      dependencies are resolved.  */
3837   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3838     if (INSN_P (insn) && INSN_LUID (insn) > 0)
3839       {
3840         /* Clear forward deps and leave the dep_nodes to the
3841            corresponding back_deps list.  */
3842         if (resolved_p)
3843           clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
3844         else
3845           clear_deps_list (INSN_FORW_DEPS (insn));
3846       }
3847   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3848     if (INSN_P (insn) && INSN_LUID (insn) > 0)
3849       {
3850         /* Clear resolved back deps together with its dep_nodes.  */
3851         delete_dep_nodes_in_back_deps (insn, resolved_p);
3852
3853         sd_finish_insn (insn);
3854       }
3855 }
3856 \f
3857 /* Initialize variables for region data dependence analysis.
3858    When LAZY_REG_LAST is true, do not allocate reg_last array
3859    of struct deps_desc immediately.  */
3860
3861 void
3862 init_deps (struct deps_desc *deps, bool lazy_reg_last)
3863 {
3864   int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
3865
3866   deps->max_reg = max_reg;
3867   if (lazy_reg_last)
3868     deps->reg_last = NULL;
3869   else
3870     deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
3871   INIT_REG_SET (&deps->reg_last_in_use);
3872
3873   deps->pending_read_insns = 0;
3874   deps->pending_read_mems = 0;
3875   deps->pending_write_insns = 0;
3876   deps->pending_write_mems = 0;
3877   deps->pending_jump_insns = 0;
3878   deps->pending_read_list_length = 0;
3879   deps->pending_write_list_length = 0;
3880   deps->pending_flush_length = 0;
3881   deps->last_pending_memory_flush = 0;
3882   deps->last_function_call = 0;
3883   deps->last_function_call_may_noreturn = 0;
3884   deps->sched_before_next_call = 0;
3885   deps->sched_before_next_jump = 0;
3886   deps->in_post_call_group_p = not_post_call;
3887   deps->last_debug_insn = 0;
3888   deps->last_args_size = 0;
3889   deps->last_reg_pending_barrier = NOT_A_BARRIER;
3890   deps->readonly = 0;
3891 }
3892
3893 /* Init only reg_last field of DEPS, which was not allocated before as
3894    we inited DEPS lazily.  */
3895 void
3896 init_deps_reg_last (struct deps_desc *deps)
3897 {
3898   gcc_assert (deps && deps->max_reg > 0);
3899   gcc_assert (deps->reg_last == NULL);
3900
3901   deps->reg_last = XCNEWVEC (struct deps_reg, deps->max_reg);
3902 }
3903
3904
3905 /* Free insn lists found in DEPS.  */
3906
3907 void
3908 free_deps (struct deps_desc *deps)
3909 {
3910   unsigned i;
3911   reg_set_iterator rsi;
3912
3913   /* We set max_reg to 0 when this context was already freed.  */
3914   if (deps->max_reg == 0)
3915     {
3916       gcc_assert (deps->reg_last == NULL);
3917       return;
3918     }
3919   deps->max_reg = 0;
3920
3921   free_INSN_LIST_list (&deps->pending_read_insns);
3922   free_EXPR_LIST_list (&deps->pending_read_mems);
3923   free_INSN_LIST_list (&deps->pending_write_insns);
3924   free_EXPR_LIST_list (&deps->pending_write_mems);
3925   free_INSN_LIST_list (&deps->last_pending_memory_flush);
3926
3927   /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3928      times.  For a testcase with 42000 regs and 8000 small basic blocks,
3929      this loop accounted for nearly 60% (84 sec) of the total -O2 runtime.  */
3930   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3931     {
3932       struct deps_reg *reg_last = &deps->reg_last[i];
3933       if (reg_last->uses)
3934         free_INSN_LIST_list (&reg_last->uses);
3935       if (reg_last->sets)
3936         free_INSN_LIST_list (&reg_last->sets);
3937       if (reg_last->implicit_sets)
3938         free_INSN_LIST_list (&reg_last->implicit_sets);
3939       if (reg_last->control_uses)
3940         free_INSN_LIST_list (&reg_last->control_uses);
3941       if (reg_last->clobbers)
3942         free_INSN_LIST_list (&reg_last->clobbers);
3943     }
3944   CLEAR_REG_SET (&deps->reg_last_in_use);
3945
3946   /* As we initialize reg_last lazily, it is possible that we didn't allocate
3947      it at all.  */
3948   free (deps->reg_last);
3949   deps->reg_last = NULL;
3950
3951   deps = NULL;
3952 }
3953
3954 /* Remove INSN from dependence contexts DEPS.  */
3955 void
3956 remove_from_deps (struct deps_desc *deps, rtx insn)
3957 {
3958   int removed;
3959   unsigned i;
3960   reg_set_iterator rsi;
3961
3962   removed = remove_from_both_dependence_lists (insn, &deps->pending_read_insns,
3963                                                &deps->pending_read_mems);
3964   if (!DEBUG_INSN_P (insn))
3965     deps->pending_read_list_length -= removed;
3966   removed = remove_from_both_dependence_lists (insn, &deps->pending_write_insns,
3967                                                &deps->pending_write_mems);
3968   deps->pending_write_list_length -= removed;
3969
3970   removed = remove_from_dependence_list (insn, &deps->pending_jump_insns);
3971   deps->pending_flush_length -= removed;
3972   removed = remove_from_dependence_list (insn, &deps->last_pending_memory_flush);
3973   deps->pending_flush_length -= removed;
3974
3975   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3976     {
3977       struct deps_reg *reg_last = &deps->reg_last[i];
3978       if (reg_last->uses)
3979         remove_from_dependence_list (insn, &reg_last->uses);
3980       if (reg_last->sets)
3981         remove_from_dependence_list (insn, &reg_last->sets);
3982       if (reg_last->implicit_sets)
3983         remove_from_dependence_list (insn, &reg_last->implicit_sets);
3984       if (reg_last->clobbers)
3985         remove_from_dependence_list (insn, &reg_last->clobbers);
3986       if (!reg_last->uses && !reg_last->sets && !reg_last->implicit_sets
3987           && !reg_last->clobbers)
3988         CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, i);
3989     }
3990
3991   if (CALL_P (insn))
3992     {
3993       remove_from_dependence_list (insn, &deps->last_function_call);
3994       remove_from_dependence_list (insn,
3995                                    &deps->last_function_call_may_noreturn);
3996     }
3997   remove_from_dependence_list (insn, &deps->sched_before_next_call);
3998 }
3999
4000 /* Init deps data vector.  */
4001 static void
4002 init_deps_data_vector (void)
4003 {
4004   int reserve = (sched_max_luid + 1 - h_d_i_d.length ());
4005   if (reserve > 0 && ! h_d_i_d.space (reserve))
4006     h_d_i_d.safe_grow_cleared (3 * sched_max_luid / 2);
4007 }
4008
4009 /* If it is profitable to use them, initialize or extend (depending on
4010    GLOBAL_P) dependency data.  */
4011 void
4012 sched_deps_init (bool global_p)
4013 {
4014   /* Average number of insns in the basic block.
4015      '+ 1' is used to make it nonzero.  */
4016   int insns_in_block = sched_max_luid / n_basic_blocks_for_fn (cfun) + 1;
4017
4018   init_deps_data_vector ();
4019
4020   /* We use another caching mechanism for selective scheduling, so
4021      we don't use this one.  */
4022   if (!sel_sched_p () && global_p && insns_in_block > 100 * 5)
4023     {
4024       /* ?!? We could save some memory by computing a per-region luid mapping
4025          which could reduce both the number of vectors in the cache and the
4026          size of each vector.  Instead we just avoid the cache entirely unless
4027          the average number of instructions in a basic block is very high.  See
4028          the comment before the declaration of true_dependency_cache for
4029          what we consider "very high".  */
4030       cache_size = 0;
4031       extend_dependency_caches (sched_max_luid, true);
4032     }
4033
4034   if (global_p)
4035     {
4036       dl_pool = create_alloc_pool ("deps_list", sizeof (struct _deps_list),
4037                                    /* Allocate lists for one block at a time.  */
4038                                    insns_in_block);
4039       dn_pool = create_alloc_pool ("dep_node", sizeof (struct _dep_node),
4040                                    /* Allocate nodes for one block at a time.
4041                                       We assume that average insn has
4042                                       5 producers.  */
4043                                    5 * insns_in_block);
4044     }
4045 }
4046
4047
4048 /* Create or extend (depending on CREATE_P) dependency caches to
4049    size N.  */
4050 void
4051 extend_dependency_caches (int n, bool create_p)
4052 {
4053   if (create_p || true_dependency_cache)
4054     {
4055       int i, luid = cache_size + n;
4056
4057       true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
4058                                           luid);
4059       output_dependency_cache = XRESIZEVEC (bitmap_head,
4060                                             output_dependency_cache, luid);
4061       anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
4062                                           luid);
4063       control_dependency_cache = XRESIZEVEC (bitmap_head, control_dependency_cache,
4064                                           luid);
4065
4066       if (current_sched_info->flags & DO_SPECULATION)
4067         spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
4068                                             luid);
4069
4070       for (i = cache_size; i < luid; i++)
4071         {
4072           bitmap_initialize (&true_dependency_cache[i], 0);
4073           bitmap_initialize (&output_dependency_cache[i], 0);
4074           bitmap_initialize (&anti_dependency_cache[i], 0);
4075           bitmap_initialize (&control_dependency_cache[i], 0);
4076
4077           if (current_sched_info->flags & DO_SPECULATION)
4078             bitmap_initialize (&spec_dependency_cache[i], 0);
4079         }
4080       cache_size = luid;
4081     }
4082 }
4083
4084 /* Finalize dependency information for the whole function.  */
4085 void
4086 sched_deps_finish (void)
4087 {
4088   gcc_assert (deps_pools_are_empty_p ());
4089   free_alloc_pool_if_empty (&dn_pool);
4090   free_alloc_pool_if_empty (&dl_pool);
4091   gcc_assert (dn_pool == NULL && dl_pool == NULL);
4092
4093   h_d_i_d.release ();
4094   cache_size = 0;
4095
4096   if (true_dependency_cache)
4097     {
4098       int i;
4099
4100       for (i = 0; i < cache_size; i++)
4101         {
4102           bitmap_clear (&true_dependency_cache[i]);
4103           bitmap_clear (&output_dependency_cache[i]);
4104           bitmap_clear (&anti_dependency_cache[i]);
4105           bitmap_clear (&control_dependency_cache[i]);
4106
4107           if (sched_deps_info->generate_spec_deps)
4108             bitmap_clear (&spec_dependency_cache[i]);
4109         }
4110       free (true_dependency_cache);
4111       true_dependency_cache = NULL;
4112       free (output_dependency_cache);
4113       output_dependency_cache = NULL;
4114       free (anti_dependency_cache);
4115       anti_dependency_cache = NULL;
4116       free (control_dependency_cache);
4117       control_dependency_cache = NULL;
4118
4119       if (sched_deps_info->generate_spec_deps)
4120         {
4121           free (spec_dependency_cache);
4122           spec_dependency_cache = NULL;
4123         }
4124
4125     }
4126 }
4127
4128 /* Initialize some global variables needed by the dependency analysis
4129    code.  */
4130
4131 void
4132 init_deps_global (void)
4133 {
4134   CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
4135   CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
4136   reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
4137   reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
4138   reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
4139   reg_pending_control_uses = ALLOC_REG_SET (&reg_obstack);
4140   reg_pending_barrier = NOT_A_BARRIER;
4141
4142   if (!sel_sched_p () || sched_emulate_haifa_p)
4143     {
4144       sched_deps_info->start_insn = haifa_start_insn;
4145       sched_deps_info->finish_insn = haifa_finish_insn;
4146
4147       sched_deps_info->note_reg_set = haifa_note_reg_set;
4148       sched_deps_info->note_reg_clobber = haifa_note_reg_clobber;
4149       sched_deps_info->note_reg_use = haifa_note_reg_use;
4150
4151       sched_deps_info->note_mem_dep = haifa_note_mem_dep;
4152       sched_deps_info->note_dep = haifa_note_dep;
4153    }
4154 }
4155
4156 /* Free everything used by the dependency analysis code.  */
4157
4158 void
4159 finish_deps_global (void)
4160 {
4161   FREE_REG_SET (reg_pending_sets);
4162   FREE_REG_SET (reg_pending_clobbers);
4163   FREE_REG_SET (reg_pending_uses);
4164   FREE_REG_SET (reg_pending_control_uses);
4165 }
4166
4167 /* Estimate the weakness of dependence between MEM1 and MEM2.  */
4168 dw_t
4169 estimate_dep_weak (rtx mem1, rtx mem2)
4170 {
4171   rtx r1, r2;
4172
4173   if (mem1 == mem2)
4174     /* MEMs are the same - don't speculate.  */
4175     return MIN_DEP_WEAK;
4176
4177   r1 = XEXP (mem1, 0);
4178   r2 = XEXP (mem2, 0);
4179
4180   if (r1 == r2
4181       || (REG_P (r1) && REG_P (r2)
4182           && REGNO (r1) == REGNO (r2)))
4183     /* Again, MEMs are the same.  */
4184     return MIN_DEP_WEAK;
4185   else if ((REG_P (r1) && !REG_P (r2))
4186            || (!REG_P (r1) && REG_P (r2)))
4187     /* Different addressing modes - reason to be more speculative,
4188        than usual.  */
4189     return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
4190   else
4191     /* We can't say anything about the dependence.  */
4192     return UNCERTAIN_DEP_WEAK;
4193 }
4194
4195 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
4196    This function can handle same INSN and ELEM (INSN == ELEM).
4197    It is a convenience wrapper.  */
4198 static void
4199 add_dependence_1 (rtx insn, rtx elem, enum reg_note dep_type)
4200 {
4201   ds_t ds;
4202   bool internal;
4203
4204   if (dep_type == REG_DEP_TRUE)
4205     ds = DEP_TRUE;
4206   else if (dep_type == REG_DEP_OUTPUT)
4207     ds = DEP_OUTPUT;
4208   else if (dep_type == REG_DEP_CONTROL)
4209     ds = DEP_CONTROL;
4210   else
4211     {
4212       gcc_assert (dep_type == REG_DEP_ANTI);
4213       ds = DEP_ANTI;
4214     }
4215
4216   /* When add_dependence is called from inside sched-deps.c, we expect
4217      cur_insn to be non-null.  */
4218   internal = cur_insn != NULL;
4219   if (internal)
4220     gcc_assert (insn == cur_insn);
4221   else
4222     cur_insn = insn;
4223
4224   note_dep (elem, ds);
4225   if (!internal)
4226     cur_insn = NULL;
4227 }
4228
4229 /* Return weakness of speculative type TYPE in the dep_status DS,
4230    without checking to prevent ICEs on malformed input.  */
4231 static dw_t
4232 get_dep_weak_1 (ds_t ds, ds_t type)
4233 {
4234   ds = ds & type;
4235
4236   switch (type)
4237     {
4238     case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
4239     case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
4240     case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
4241     case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
4242     default: gcc_unreachable ();
4243     }
4244
4245   return (dw_t) ds;
4246 }
4247
4248 /* Return weakness of speculative type TYPE in the dep_status DS.  */
4249 dw_t
4250 get_dep_weak (ds_t ds, ds_t type)
4251 {
4252   dw_t dw = get_dep_weak_1 (ds, type);
4253
4254   gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4255   return dw;
4256 }
4257
4258 /* Return the dep_status, which has the same parameters as DS, except for
4259    speculative type TYPE, that will have weakness DW.  */
4260 ds_t
4261 set_dep_weak (ds_t ds, ds_t type, dw_t dw)
4262 {
4263   gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4264
4265   ds &= ~type;
4266   switch (type)
4267     {
4268     case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
4269     case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
4270     case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
4271     case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
4272     default: gcc_unreachable ();
4273     }
4274   return ds;
4275 }
4276
4277 /* Return the join of two dep_statuses DS1 and DS2.
4278    If MAX_P is true then choose the greater probability,
4279    otherwise multiply probabilities.
4280    This function assumes that both DS1 and DS2 contain speculative bits.  */
4281 static ds_t
4282 ds_merge_1 (ds_t ds1, ds_t ds2, bool max_p)
4283 {
4284   ds_t ds, t;
4285
4286   gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
4287
4288   ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
4289
4290   t = FIRST_SPEC_TYPE;
4291   do
4292     {
4293       if ((ds1 & t) && !(ds2 & t))
4294         ds |= ds1 & t;
4295       else if (!(ds1 & t) && (ds2 & t))
4296         ds |= ds2 & t;
4297       else if ((ds1 & t) && (ds2 & t))
4298         {
4299           dw_t dw1 = get_dep_weak (ds1, t);
4300           dw_t dw2 = get_dep_weak (ds2, t);
4301           ds_t dw;
4302
4303           if (!max_p)
4304             {
4305               dw = ((ds_t) dw1) * ((ds_t) dw2);
4306               dw /= MAX_DEP_WEAK;
4307               if (dw < MIN_DEP_WEAK)
4308                 dw = MIN_DEP_WEAK;
4309             }
4310           else
4311             {
4312               if (dw1 >= dw2)
4313                 dw = dw1;
4314               else
4315                 dw = dw2;
4316             }
4317
4318           ds = set_dep_weak (ds, t, (dw_t) dw);
4319         }
4320
4321       if (t == LAST_SPEC_TYPE)
4322         break;
4323       t <<= SPEC_TYPE_SHIFT;
4324     }
4325   while (1);
4326
4327   return ds;
4328 }
4329
4330 /* Return the join of two dep_statuses DS1 and DS2.
4331    This function assumes that both DS1 and DS2 contain speculative bits.  */
4332 ds_t
4333 ds_merge (ds_t ds1, ds_t ds2)
4334 {
4335   return ds_merge_1 (ds1, ds2, false);
4336 }
4337
4338 /* Return the join of two dep_statuses DS1 and DS2.  */
4339 ds_t
4340 ds_full_merge (ds_t ds, ds_t ds2, rtx mem1, rtx mem2)
4341 {
4342   ds_t new_status = ds | ds2;
4343
4344   if (new_status & SPECULATIVE)
4345     {
4346       if ((ds && !(ds & SPECULATIVE))
4347           || (ds2 && !(ds2 & SPECULATIVE)))
4348         /* Then this dep can't be speculative.  */
4349         new_status &= ~SPECULATIVE;
4350       else
4351         {
4352           /* Both are speculative.  Merging probabilities.  */
4353           if (mem1)
4354             {
4355               dw_t dw;
4356
4357               dw = estimate_dep_weak (mem1, mem2);
4358               ds = set_dep_weak (ds, BEGIN_DATA, dw);
4359             }
4360
4361           if (!ds)
4362             new_status = ds2;
4363           else if (!ds2)
4364             new_status = ds;
4365           else
4366             new_status = ds_merge (ds2, ds);
4367         }
4368     }
4369
4370   return new_status;
4371 }
4372
4373 /* Return the join of DS1 and DS2.  Use maximum instead of multiplying
4374    probabilities.  */
4375 ds_t
4376 ds_max_merge (ds_t ds1, ds_t ds2)
4377 {
4378   if (ds1 == 0 && ds2 == 0)
4379     return 0;
4380
4381   if (ds1 == 0 && ds2 != 0)
4382     return ds2;
4383
4384   if (ds1 != 0 && ds2 == 0)
4385     return ds1;
4386
4387   return ds_merge_1 (ds1, ds2, true);
4388 }
4389
4390 /* Return the probability of speculation success for the speculation
4391    status DS.  */
4392 dw_t
4393 ds_weak (ds_t ds)
4394 {
4395   ds_t res = 1, dt;
4396   int n = 0;
4397
4398   dt = FIRST_SPEC_TYPE;
4399   do
4400     {
4401       if (ds & dt)
4402         {
4403           res *= (ds_t) get_dep_weak (ds, dt);
4404           n++;
4405         }
4406
4407       if (dt == LAST_SPEC_TYPE)
4408         break;
4409       dt <<= SPEC_TYPE_SHIFT;
4410     }
4411   while (1);
4412
4413   gcc_assert (n);
4414   while (--n)
4415     res /= MAX_DEP_WEAK;
4416
4417   if (res < MIN_DEP_WEAK)
4418     res = MIN_DEP_WEAK;
4419
4420   gcc_assert (res <= MAX_DEP_WEAK);
4421
4422   return (dw_t) res;
4423 }
4424
4425 /* Return a dep status that contains all speculation types of DS.  */
4426 ds_t
4427 ds_get_speculation_types (ds_t ds)
4428 {
4429   if (ds & BEGIN_DATA)
4430     ds |= BEGIN_DATA;
4431   if (ds & BE_IN_DATA)
4432     ds |= BE_IN_DATA;
4433   if (ds & BEGIN_CONTROL)
4434     ds |= BEGIN_CONTROL;
4435   if (ds & BE_IN_CONTROL)
4436     ds |= BE_IN_CONTROL;
4437
4438   return ds & SPECULATIVE;
4439 }
4440
4441 /* Return a dep status that contains maximal weakness for each speculation
4442    type present in DS.  */
4443 ds_t
4444 ds_get_max_dep_weak (ds_t ds)
4445 {
4446   if (ds & BEGIN_DATA)
4447     ds = set_dep_weak (ds, BEGIN_DATA, MAX_DEP_WEAK);
4448   if (ds & BE_IN_DATA)
4449     ds = set_dep_weak (ds, BE_IN_DATA, MAX_DEP_WEAK);
4450   if (ds & BEGIN_CONTROL)
4451     ds = set_dep_weak (ds, BEGIN_CONTROL, MAX_DEP_WEAK);
4452   if (ds & BE_IN_CONTROL)
4453     ds = set_dep_weak (ds, BE_IN_CONTROL, MAX_DEP_WEAK);
4454
4455   return ds;
4456 }
4457
4458 /* Dump information about the dependence status S.  */
4459 static void
4460 dump_ds (FILE *f, ds_t s)
4461 {
4462   fprintf (f, "{");
4463
4464   if (s & BEGIN_DATA)
4465     fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak_1 (s, BEGIN_DATA));
4466   if (s & BE_IN_DATA)
4467     fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak_1 (s, BE_IN_DATA));
4468   if (s & BEGIN_CONTROL)
4469     fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s, BEGIN_CONTROL));
4470   if (s & BE_IN_CONTROL)
4471     fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s, BE_IN_CONTROL));
4472
4473   if (s & HARD_DEP)
4474     fprintf (f, "HARD_DEP; ");
4475
4476   if (s & DEP_TRUE)
4477     fprintf (f, "DEP_TRUE; ");
4478   if (s & DEP_OUTPUT)
4479     fprintf (f, "DEP_OUTPUT; ");
4480   if (s & DEP_ANTI)
4481     fprintf (f, "DEP_ANTI; ");
4482   if (s & DEP_CONTROL)
4483     fprintf (f, "DEP_CONTROL; ");
4484
4485   fprintf (f, "}");
4486 }
4487
4488 DEBUG_FUNCTION void
4489 debug_ds (ds_t s)
4490 {
4491   dump_ds (stderr, s);
4492   fprintf (stderr, "\n");
4493 }
4494
4495 #ifdef ENABLE_CHECKING
4496 /* Verify that dependence type and status are consistent.
4497    If RELAXED_P is true, then skip dep_weakness checks.  */
4498 static void
4499 check_dep (dep_t dep, bool relaxed_p)
4500 {
4501   enum reg_note dt = DEP_TYPE (dep);
4502   ds_t ds = DEP_STATUS (dep);
4503
4504   gcc_assert (DEP_PRO (dep) != DEP_CON (dep));
4505
4506   if (!(current_sched_info->flags & USE_DEPS_LIST))
4507     {
4508       gcc_assert (ds == 0);
4509       return;
4510     }
4511
4512   /* Check that dependence type contains the same bits as the status.  */
4513   if (dt == REG_DEP_TRUE)
4514     gcc_assert (ds & DEP_TRUE);
4515   else if (dt == REG_DEP_OUTPUT)
4516     gcc_assert ((ds & DEP_OUTPUT)
4517                 && !(ds & DEP_TRUE));
4518   else if (dt == REG_DEP_ANTI)
4519     gcc_assert ((ds & DEP_ANTI)
4520                 && !(ds & (DEP_OUTPUT | DEP_TRUE)));
4521   else
4522     gcc_assert (dt == REG_DEP_CONTROL
4523                 && (ds & DEP_CONTROL)
4524                 && !(ds & (DEP_OUTPUT | DEP_ANTI | DEP_TRUE)));
4525
4526   /* HARD_DEP can not appear in dep_status of a link.  */
4527   gcc_assert (!(ds & HARD_DEP));
4528
4529   /* Check that dependence status is set correctly when speculation is not
4530      supported.  */
4531   if (!sched_deps_info->generate_spec_deps)
4532     gcc_assert (!(ds & SPECULATIVE));
4533   else if (ds & SPECULATIVE)
4534     {
4535       if (!relaxed_p)
4536         {
4537           ds_t type = FIRST_SPEC_TYPE;
4538
4539           /* Check that dependence weakness is in proper range.  */
4540           do
4541             {
4542               if (ds & type)
4543                 get_dep_weak (ds, type);
4544
4545               if (type == LAST_SPEC_TYPE)
4546                 break;
4547               type <<= SPEC_TYPE_SHIFT;
4548             }
4549           while (1);
4550         }
4551
4552       if (ds & BEGIN_SPEC)
4553         {
4554           /* Only true dependence can be data speculative.  */
4555           if (ds & BEGIN_DATA)
4556             gcc_assert (ds & DEP_TRUE);
4557
4558           /* Control dependencies in the insn scheduler are represented by
4559              anti-dependencies, therefore only anti dependence can be
4560              control speculative.  */
4561           if (ds & BEGIN_CONTROL)
4562             gcc_assert (ds & DEP_ANTI);
4563         }
4564       else
4565         {
4566           /* Subsequent speculations should resolve true dependencies.  */
4567           gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
4568         }
4569
4570       /* Check that true and anti dependencies can't have other speculative
4571          statuses.  */
4572       if (ds & DEP_TRUE)
4573         gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
4574       /* An output dependence can't be speculative at all.  */
4575       gcc_assert (!(ds & DEP_OUTPUT));
4576       if (ds & DEP_ANTI)
4577         gcc_assert (ds & BEGIN_CONTROL);
4578     }
4579 }
4580 #endif /* ENABLE_CHECKING */
4581
4582 /* The following code discovers opportunities to switch a memory reference
4583    and an increment by modifying the address.  We ensure that this is done
4584    only for dependencies that are only used to show a single register
4585    dependence (using DEP_NONREG and DEP_MULTIPLE), and so that every memory
4586    instruction involved is subject to only one dep that can cause a pattern
4587    change.
4588
4589    When we discover a suitable dependency, we fill in the dep_replacement
4590    structure to show how to modify the memory reference.  */
4591
4592 /* Holds information about a pair of memory reference and register increment
4593    insns which depend on each other, but could possibly be interchanged.  */
4594 struct mem_inc_info
4595 {
4596   rtx inc_insn;
4597   rtx mem_insn;
4598
4599   rtx *mem_loc;
4600   /* A register occurring in the memory address for which we wish to break
4601      the dependence.  This must be identical to the destination register of
4602      the increment.  */
4603   rtx mem_reg0;
4604   /* Any kind of index that is added to that register.  */
4605   rtx mem_index;
4606   /* The constant offset used in the memory address.  */
4607   HOST_WIDE_INT mem_constant;
4608   /* The constant added in the increment insn.  Negated if the increment is
4609      after the memory address.  */
4610   HOST_WIDE_INT inc_constant;
4611   /* The source register used in the increment.  May be different from mem_reg0
4612      if the increment occurs before the memory address.  */
4613   rtx inc_input;
4614 };
4615
4616 /* Verify that the memory location described in MII can be replaced with
4617    one using NEW_ADDR.  Return the new memory reference or NULL_RTX.  The
4618    insn remains unchanged by this function.  */
4619
4620 static rtx
4621 attempt_change (struct mem_inc_info *mii, rtx new_addr)
4622 {
4623   rtx mem = *mii->mem_loc;
4624   rtx new_mem;
4625
4626   /* Jump through a lot of hoops to keep the attributes up to date.  We
4627      do not want to call one of the change address variants that take
4628      an offset even though we know the offset in many cases.  These
4629      assume you are changing where the address is pointing by the
4630      offset.  */
4631   new_mem = replace_equiv_address_nv (mem, new_addr);
4632   if (! validate_change (mii->mem_insn, mii->mem_loc, new_mem, 0))
4633     {
4634       if (sched_verbose >= 5)
4635         fprintf (sched_dump, "validation failure\n");
4636       return NULL_RTX;
4637     }
4638
4639   /* Put back the old one.  */
4640   validate_change (mii->mem_insn, mii->mem_loc, mem, 0);
4641
4642   return new_mem;
4643 }
4644
4645 /* Return true if INSN is of a form "a = b op c" where a and b are
4646    regs.  op is + if c is a reg and +|- if c is a const.  Fill in
4647    informantion in MII about what is found.
4648    BEFORE_MEM indicates whether the increment is found before or after
4649    a corresponding memory reference.  */
4650
4651 static bool
4652 parse_add_or_inc (struct mem_inc_info *mii, rtx insn, bool before_mem)
4653 {
4654   rtx pat = single_set (insn);
4655   rtx src, cst;
4656   bool regs_equal;
4657
4658   if (RTX_FRAME_RELATED_P (insn) || !pat)
4659     return false;
4660
4661   /* Result must be single reg.  */
4662   if (!REG_P (SET_DEST (pat)))
4663     return false;
4664
4665   if (GET_CODE (SET_SRC (pat)) != PLUS)
4666     return false;
4667
4668   mii->inc_insn = insn;
4669   src = SET_SRC (pat);
4670   mii->inc_input = XEXP (src, 0);
4671
4672   if (!REG_P (XEXP (src, 0)))
4673     return false;
4674
4675   if (!rtx_equal_p (SET_DEST (pat), mii->mem_reg0))
4676     return false;
4677
4678   cst = XEXP (src, 1);
4679   if (!CONST_INT_P (cst))
4680     return false;
4681   mii->inc_constant = INTVAL (cst);
4682
4683   regs_equal = rtx_equal_p (mii->inc_input, mii->mem_reg0);
4684
4685   if (!before_mem)
4686     {
4687       mii->inc_constant = -mii->inc_constant;
4688       if (!regs_equal)
4689         return false;
4690     }
4691
4692   if (regs_equal && REGNO (SET_DEST (pat)) == STACK_POINTER_REGNUM)
4693     {
4694       /* Note that the sign has already been reversed for !before_mem.  */
4695 #ifdef STACK_GROWS_DOWNWARD
4696       return mii->inc_constant > 0;
4697 #else
4698       return mii->inc_constant < 0;
4699 #endif
4700     }
4701   return true;
4702 }
4703
4704 /* Once a suitable mem reference has been found and the corresponding data
4705    in MII has been filled in, this function is called to find a suitable
4706    add or inc insn involving the register we found in the memory
4707    reference.  */
4708
4709 static bool
4710 find_inc (struct mem_inc_info *mii, bool backwards)
4711 {
4712   sd_iterator_def sd_it;
4713   dep_t dep;
4714
4715   sd_it = sd_iterator_start (mii->mem_insn,
4716                              backwards ? SD_LIST_HARD_BACK : SD_LIST_FORW);
4717   while (sd_iterator_cond (&sd_it, &dep))
4718     {
4719       dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
4720       rtx pro = DEP_PRO (dep);
4721       rtx con = DEP_CON (dep);
4722       rtx inc_cand = backwards ? pro : con;
4723       if (DEP_NONREG (dep) || DEP_MULTIPLE (dep))
4724         goto next;
4725       if (parse_add_or_inc (mii, inc_cand, backwards))
4726         {
4727           struct dep_replacement *desc;
4728           df_ref *def_rec;
4729           rtx newaddr, newmem;
4730
4731           if (sched_verbose >= 5)
4732             fprintf (sched_dump, "candidate mem/inc pair: %d %d\n",
4733                      INSN_UID (mii->mem_insn), INSN_UID (inc_cand));
4734
4735           /* Need to assure that none of the operands of the inc
4736              instruction are assigned to by the mem insn.  */
4737           for (def_rec = DF_INSN_DEFS (mii->mem_insn); *def_rec; def_rec++)
4738             {
4739               df_ref def = *def_rec;
4740               if (reg_overlap_mentioned_p (DF_REF_REG (def), mii->inc_input)
4741                   || reg_overlap_mentioned_p (DF_REF_REG (def), mii->mem_reg0))
4742                 {
4743                   if (sched_verbose >= 5)
4744                     fprintf (sched_dump,
4745                              "inc conflicts with store failure.\n");
4746                   goto next;
4747                 }
4748             }
4749           newaddr = mii->inc_input;
4750           if (mii->mem_index != NULL_RTX)
4751             newaddr = gen_rtx_PLUS (GET_MODE (newaddr), newaddr,
4752                                     mii->mem_index);
4753           newaddr = plus_constant (GET_MODE (newaddr), newaddr,
4754                                    mii->mem_constant + mii->inc_constant);
4755           newmem = attempt_change (mii, newaddr);
4756           if (newmem == NULL_RTX)
4757             goto next;
4758           if (sched_verbose >= 5)
4759             fprintf (sched_dump, "successful address replacement\n");
4760           desc = XCNEW (struct dep_replacement);
4761           DEP_REPLACE (dep) = desc;
4762           desc->loc = mii->mem_loc;
4763           desc->newval = newmem;
4764           desc->orig = *desc->loc;
4765           desc->insn = mii->mem_insn;
4766           move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
4767                          INSN_SPEC_BACK_DEPS (con));
4768           if (backwards)
4769             {
4770               FOR_EACH_DEP (mii->inc_insn, SD_LIST_BACK, sd_it, dep)
4771                 add_dependence_1 (mii->mem_insn, DEP_PRO (dep),
4772                                   REG_DEP_TRUE);
4773             }
4774           else
4775             {
4776               FOR_EACH_DEP (mii->inc_insn, SD_LIST_FORW, sd_it, dep)
4777                 add_dependence_1 (DEP_CON (dep), mii->mem_insn,
4778                                   REG_DEP_ANTI);
4779             }
4780           return true;
4781         }
4782     next:
4783       sd_iterator_next (&sd_it);
4784     }
4785   return false;
4786 }
4787
4788 /* A recursive function that walks ADDRESS_OF_X to find memory references
4789    which could be modified during scheduling.  We call find_inc for each
4790    one we find that has a recognizable form.  MII holds information about
4791    the pair of memory/increment instructions.
4792    We ensure that every instruction with a memory reference (which will be
4793    the location of the replacement) is assigned at most one breakable
4794    dependency.  */
4795
4796 static bool
4797 find_mem (struct mem_inc_info *mii, rtx *address_of_x)
4798 {
4799   rtx x = *address_of_x;
4800   enum rtx_code code = GET_CODE (x);
4801   const char *const fmt = GET_RTX_FORMAT (code);
4802   int i;
4803
4804   if (code == MEM)
4805     {
4806       rtx reg0 = XEXP (x, 0);
4807
4808       mii->mem_loc = address_of_x;
4809       mii->mem_index = NULL_RTX;
4810       mii->mem_constant = 0;
4811       if (GET_CODE (reg0) == PLUS && CONST_INT_P (XEXP (reg0, 1)))
4812         {
4813           mii->mem_constant = INTVAL (XEXP (reg0, 1));
4814           reg0 = XEXP (reg0, 0);
4815         }
4816       if (GET_CODE (reg0) == PLUS)
4817         {
4818           mii->mem_index = XEXP (reg0, 1);
4819           reg0 = XEXP (reg0, 0);
4820         }
4821       if (REG_P (reg0))
4822         {
4823           df_ref *def_rec;
4824           int occurrences = 0;
4825
4826           /* Make sure this reg appears only once in this insn.  Can't use
4827              count_occurrences since that only works for pseudos.  */
4828           for (def_rec = DF_INSN_USES (mii->mem_insn); *def_rec; def_rec++)
4829             {
4830               df_ref def = *def_rec;
4831               if (reg_overlap_mentioned_p (reg0, DF_REF_REG (def)))
4832                 if (++occurrences > 1)
4833                   {
4834                     if (sched_verbose >= 5)
4835                       fprintf (sched_dump, "mem count failure\n");
4836                     return false;
4837                   }
4838             }
4839
4840           mii->mem_reg0 = reg0;
4841           return find_inc (mii, true) || find_inc (mii, false);
4842         }
4843       return false;
4844     }
4845
4846   if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
4847     {
4848       /* If REG occurs inside a MEM used in a bit-field reference,
4849          that is unacceptable.  */
4850       return false;
4851     }
4852
4853   /* Time for some deep diving.  */
4854   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4855     {
4856       if (fmt[i] == 'e')
4857         {
4858           if (find_mem (mii, &XEXP (x, i)))
4859             return true;
4860         }
4861       else if (fmt[i] == 'E')
4862         {
4863           int j;
4864           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4865             if (find_mem (mii, &XVECEXP (x, i, j)))
4866               return true;
4867         }
4868     }
4869   return false;
4870 }
4871
4872
4873 /* Examine the instructions between HEAD and TAIL and try to find
4874    dependencies that can be broken by modifying one of the patterns.  */
4875
4876 void
4877 find_modifiable_mems (rtx head, rtx tail)
4878 {
4879   rtx insn, next_tail = NEXT_INSN (tail);
4880   int success_in_block = 0;
4881
4882   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4883     {
4884       struct mem_inc_info mii;
4885
4886       if (!NONDEBUG_INSN_P (insn) || RTX_FRAME_RELATED_P (insn))
4887         continue;
4888
4889       mii.mem_insn = insn;
4890       if (find_mem (&mii, &PATTERN (insn)))
4891         success_in_block++;
4892     }
4893   if (success_in_block && sched_verbose >= 5)
4894     fprintf (sched_dump, "%d candidates for address modification found.\n",
4895              success_in_block);
4896 }
4897
4898 #endif /* INSN_SCHEDULING */