gcc/sched-deps.c

   1 /* Instruction scheduling pass.  This file computes dependencies between
   2    instructions.
   3    Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   4    1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
   5    2011, 2012
   6    Free Software Foundation, Inc.
   7    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
   8    and currently maintained by, Jim Wilson (wilson@cygnus.com)
   9
  10 This file is part of GCC.
  11
  12 GCC is free software; you can redistribute it and/or modify it under
  13 the terms of the GNU General Public License as published by the Free
  14 Software Foundation; either version 3, or (at your option) any later
  15 version.
  16
  17 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  18 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  19 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  20 for more details.
  21
  22 You should have received a copy of the GNU General Public License
  23 along with GCC; see the file COPYING3.  If not see
  24 <http://www.gnu.org/licenses/>.  */
  25 \f
  26 #include "config.h"
  27 #include "system.h"
  28 #include "coretypes.h"
  29 #include "tm.h"
  30 #include "diagnostic-core.h"
  31 #include "rtl.h"
  32 #include "tree.h"               /* FIXME: Used by call_may_noreturn_p.  */
  33 #include "tm_p.h"
  34 #include "hard-reg-set.h"
  35 #include "regs.h"
  36 #include "function.h"
  37 #include "flags.h"
  38 #include "insn-config.h"
  39 #include "insn-attr.h"
  40 #include "except.h"
  41 #include "recog.h"
  42 #include "emit-rtl.h"
  43 #include "sched-int.h"
  44 #include "params.h"
  45 #include "cselib.h"
  46 #include "ira.h"
  47 #include "target.h"
  48
  49 #ifdef INSN_SCHEDULING
  50
  51 #ifdef ENABLE_CHECKING
  52 #define CHECK (true)
  53 #else
  54 #define CHECK (false)
  55 #endif
  56
  57 /* Holds current parameters for the dependency analyzer.  */
  58 struct sched_deps_info_def *sched_deps_info;
  59
  60 /* The data is specific to the Haifa scheduler.  */
  61 VEC(haifa_deps_insn_data_def, heap) *h_d_i_d = NULL;
  62
  63 /* Return the major type present in the DS.  */
  64 enum reg_note
  65 ds_to_dk (ds_t ds)
  66 {
  67   if (ds & DEP_TRUE)
  68     return REG_DEP_TRUE;
  69
  70   if (ds & DEP_OUTPUT)
  71     return REG_DEP_OUTPUT;
  72
  73   if (ds & DEP_CONTROL)
  74     return REG_DEP_CONTROL;
  75
  76   gcc_assert (ds & DEP_ANTI);
  77
  78   return REG_DEP_ANTI;
  79 }
  80
  81 /* Return equivalent dep_status.  */
  82 ds_t
  83 dk_to_ds (enum reg_note dk)
  84 {
  85   switch (dk)
  86     {
  87     case REG_DEP_TRUE:
  88       return DEP_TRUE;
  89
  90     case REG_DEP_OUTPUT:
  91       return DEP_OUTPUT;
  92
  93     case REG_DEP_CONTROL:
  94       return DEP_CONTROL;
  95
  96     default:
  97       gcc_assert (dk == REG_DEP_ANTI);
  98       return DEP_ANTI;
  99     }
 100 }
 101
 102 /* Functions to operate with dependence information container - dep_t.  */
 103
 104 /* Init DEP with the arguments.  */
 105 void
 106 init_dep_1 (dep_t dep, rtx pro, rtx con, enum reg_note type, ds_t ds)
 107 {
 108   DEP_PRO (dep) = pro;
 109   DEP_CON (dep) = con;
 110   DEP_TYPE (dep) = type;
 111   DEP_STATUS (dep) = ds;
 112   DEP_COST (dep) = UNKNOWN_DEP_COST;
 113   DEP_NONREG (dep) = 0;
 114   DEP_MULTIPLE (dep) = 0;
 115   DEP_REPLACE (dep) = NULL;
 116 }
 117
 118 /* Init DEP with the arguments.
 119    While most of the scheduler (including targets) only need the major type
 120    of the dependency, it is convenient to hide full dep_status from them.  */
 121 void
 122 init_dep (dep_t dep, rtx pro, rtx con, enum reg_note kind)
 123 {
 124   ds_t ds;
 125
 126   if ((current_sched_info->flags & USE_DEPS_LIST))
 127     ds = dk_to_ds (kind);
 128   else
 129     ds = 0;
 130
 131   init_dep_1 (dep, pro, con, kind, ds);
 132 }
 133
 134 /* Make a copy of FROM in TO.  */
 135 static void
 136 copy_dep (dep_t to, dep_t from)
 137 {
 138   memcpy (to, from, sizeof (*to));
 139 }
 140
 141 static void dump_ds (FILE *, ds_t);
 142
 143 /* Define flags for dump_dep ().  */
 144
 145 /* Dump producer of the dependence.  */
 146 #define DUMP_DEP_PRO (2)
 147
 148 /* Dump consumer of the dependence.  */
 149 #define DUMP_DEP_CON (4)
 150
 151 /* Dump type of the dependence.  */
 152 #define DUMP_DEP_TYPE (8)
 153
 154 /* Dump status of the dependence.  */
 155 #define DUMP_DEP_STATUS (16)
 156
 157 /* Dump all information about the dependence.  */
 158 #define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE       \
 159                       |DUMP_DEP_STATUS)
 160
 161 /* Dump DEP to DUMP.
 162    FLAGS is a bit mask specifying what information about DEP needs
 163    to be printed.
 164    If FLAGS has the very first bit set, then dump all information about DEP
 165    and propagate this bit into the callee dump functions.  */
 166 static void
 167 dump_dep (FILE *dump, dep_t dep, int flags)
 168 {
 169   if (flags & 1)
 170     flags |= DUMP_DEP_ALL;
 171
 172   fprintf (dump, "<");
 173
 174   if (flags & DUMP_DEP_PRO)
 175     fprintf (dump, "%d; ", INSN_UID (DEP_PRO (dep)));
 176
 177   if (flags & DUMP_DEP_CON)
 178     fprintf (dump, "%d; ", INSN_UID (DEP_CON (dep)));
 179
 180   if (flags & DUMP_DEP_TYPE)
 181     {
 182       char t;
 183       enum reg_note type = DEP_TYPE (dep);
 184
 185       switch (type)
 186         {
 187         case REG_DEP_TRUE:
 188           t = 't';
 189           break;
 190
 191         case REG_DEP_OUTPUT:
 192           t = 'o';
 193           break;
 194
 195         case REG_DEP_CONTROL:
 196           t = 'c';
 197           break;
 198
 199         case REG_DEP_ANTI:
 200           t = 'a';
 201           break;
 202
 203         default:
 204           gcc_unreachable ();
 205           break;
 206         }
 207
 208       fprintf (dump, "%c; ", t);
 209     }
 210
 211   if (flags & DUMP_DEP_STATUS)
 212     {
 213       if (current_sched_info->flags & USE_DEPS_LIST)
 214         dump_ds (dump, DEP_STATUS (dep));
 215     }
 216
 217   fprintf (dump, ">");
 218 }
 219
 220 /* Default flags for dump_dep ().  */
 221 static int dump_dep_flags = (DUMP_DEP_PRO | DUMP_DEP_CON);
 222
 223 /* Dump all fields of DEP to STDERR.  */
 224 void
 225 sd_debug_dep (dep_t dep)
 226 {
 227   dump_dep (stderr, dep, 1);
 228   fprintf (stderr, "\n");
 229 }
 230
 231 /* Determine whether DEP is a dependency link of a non-debug insn on a
 232    debug insn.  */
 233
 234 static inline bool
 235 depl_on_debug_p (dep_link_t dep)
 236 {
 237   return (DEBUG_INSN_P (DEP_LINK_PRO (dep))
 238           && !DEBUG_INSN_P (DEP_LINK_CON (dep)));
 239 }
 240
 241 /* Functions to operate with a single link from the dependencies lists -
 242    dep_link_t.  */
 243
 244 /* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
 245    PREV_NEXT_P.  */
 246 static void
 247 attach_dep_link (dep_link_t l, dep_link_t *prev_nextp)
 248 {
 249   dep_link_t next = *prev_nextp;
 250
 251   gcc_assert (DEP_LINK_PREV_NEXTP (l) == NULL
 252               && DEP_LINK_NEXT (l) == NULL);
 253
 254   /* Init node being inserted.  */
 255   DEP_LINK_PREV_NEXTP (l) = prev_nextp;
 256   DEP_LINK_NEXT (l) = next;
 257
 258   /* Fix next node.  */
 259   if (next != NULL)
 260     {
 261       gcc_assert (DEP_LINK_PREV_NEXTP (next) == prev_nextp);
 262
 263       DEP_LINK_PREV_NEXTP (next) = &DEP_LINK_NEXT (l);
 264     }
 265
 266   /* Fix prev node.  */
 267   *prev_nextp = l;
 268 }
 269
 270 /* Add dep_link LINK to deps_list L.  */
 271 static void
 272 add_to_deps_list (dep_link_t link, deps_list_t l)
 273 {
 274   attach_dep_link (link, &DEPS_LIST_FIRST (l));
 275
 276   /* Don't count debug deps.  */
 277   if (!depl_on_debug_p (link))
 278     ++DEPS_LIST_N_LINKS (l);
 279 }
 280
 281 /* Detach dep_link L from the list.  */
 282 static void
 283 detach_dep_link (dep_link_t l)
 284 {
 285   dep_link_t *prev_nextp = DEP_LINK_PREV_NEXTP (l);
 286   dep_link_t next = DEP_LINK_NEXT (l);
 287
 288   *prev_nextp = next;
 289
 290   if (next != NULL)
 291     DEP_LINK_PREV_NEXTP (next) = prev_nextp;
 292
 293   DEP_LINK_PREV_NEXTP (l) = NULL;
 294   DEP_LINK_NEXT (l) = NULL;
 295 }
 296
 297 /* Remove link LINK from list LIST.  */
 298 static void
 299 remove_from_deps_list (dep_link_t link, deps_list_t list)
 300 {
 301   detach_dep_link (link);
 302
 303   /* Don't count debug deps.  */
 304   if (!depl_on_debug_p (link))
 305     --DEPS_LIST_N_LINKS (list);
 306 }
 307
 308 /* Move link LINK from list FROM to list TO.  */
 309 static void
 310 move_dep_link (dep_link_t link, deps_list_t from, deps_list_t to)
 311 {
 312   remove_from_deps_list (link, from);
 313   add_to_deps_list (link, to);
 314 }
 315
 316 /* Return true of LINK is not attached to any list.  */
 317 static bool
 318 dep_link_is_detached_p (dep_link_t link)
 319 {
 320   return DEP_LINK_PREV_NEXTP (link) == NULL;
 321 }
 322
 323 /* Pool to hold all dependency nodes (dep_node_t).  */
 324 static alloc_pool dn_pool;
 325
 326 /* Number of dep_nodes out there.  */
 327 static int dn_pool_diff = 0;
 328
 329 /* Create a dep_node.  */
 330 static dep_node_t
 331 create_dep_node (void)
 332 {
 333   dep_node_t n = (dep_node_t) pool_alloc (dn_pool);
 334   dep_link_t back = DEP_NODE_BACK (n);
 335   dep_link_t forw = DEP_NODE_FORW (n);
 336
 337   DEP_LINK_NODE (back) = n;
 338   DEP_LINK_NEXT (back) = NULL;
 339   DEP_LINK_PREV_NEXTP (back) = NULL;
 340
 341   DEP_LINK_NODE (forw) = n;
 342   DEP_LINK_NEXT (forw) = NULL;
 343   DEP_LINK_PREV_NEXTP (forw) = NULL;
 344
 345   ++dn_pool_diff;
 346
 347   return n;
 348 }
 349
 350 /* Delete dep_node N.  N must not be connected to any deps_list.  */
 351 static void
 352 delete_dep_node (dep_node_t n)
 353 {
 354   gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n))
 355               && dep_link_is_detached_p (DEP_NODE_FORW (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 and return reg_set_data structure for REGNO and INSN.  */
1942 static struct reg_set_data *
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   return set;
1953 }
1954
1955 /* Set up insn register uses for INSN and dependency context DEPS.  */
1956 static void
1957 setup_insn_reg_uses (struct deps_desc *deps, rtx insn)
1958 {
1959   unsigned i;
1960   reg_set_iterator rsi;
1961   rtx list;
1962   struct reg_use_data *use, *use2, *next;
1963   struct deps_reg *reg_last;
1964
1965   EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1966     {
1967       if (i < FIRST_PSEUDO_REGISTER
1968           && TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
1969         continue;
1970
1971       if (find_regno_note (insn, REG_DEAD, i) == NULL_RTX
1972           && ! REGNO_REG_SET_P (reg_pending_sets, i)
1973           && ! REGNO_REG_SET_P (reg_pending_clobbers, i))
1974         /* Ignore use which is not dying.  */
1975         continue;
1976
1977       use = create_insn_reg_use (i, insn);
1978       use->next_regno_use = use;
1979       reg_last = &deps->reg_last[i];
1980
1981       /* Create the cycle list of uses.  */
1982       for (list = reg_last->uses; list; list = XEXP (list, 1))
1983         {
1984           use2 = create_insn_reg_use (i, XEXP (list, 0));
1985           next = use->next_regno_use;
1986           use->next_regno_use = use2;
1987           use2->next_regno_use = next;
1988         }
1989     }
1990 }
1991
1992 /* Register pressure info for the currently processed insn.  */
1993 static struct reg_pressure_data reg_pressure_info[N_REG_CLASSES];
1994
1995 /* Return TRUE if INSN has the use structure for REGNO.  */
1996 static bool
1997 insn_use_p (rtx insn, int regno)
1998 {
1999   struct reg_use_data *use;
2000
2001   for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
2002     if (use->regno == regno)
2003       return true;
2004   return false;
2005 }
2006
2007 /* Update the register pressure info after birth of pseudo register REGNO
2008    in INSN.  Arguments CLOBBER_P and UNUSED_P say correspondingly that
2009    the register is in clobber or unused after the insn.  */
2010 static void
2011 mark_insn_pseudo_birth (rtx insn, int regno, bool clobber_p, bool unused_p)
2012 {
2013   int incr, new_incr;
2014   enum reg_class cl;
2015
2016   gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
2017   cl = sched_regno_pressure_class[regno];
2018   if (cl != NO_REGS)
2019     {
2020       incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
2021       if (clobber_p)
2022         {
2023           new_incr = reg_pressure_info[cl].clobber_increase + incr;
2024           reg_pressure_info[cl].clobber_increase = new_incr;
2025         }
2026       else if (unused_p)
2027         {
2028           new_incr = reg_pressure_info[cl].unused_set_increase + incr;
2029           reg_pressure_info[cl].unused_set_increase = new_incr;
2030         }
2031       else
2032         {
2033           new_incr = reg_pressure_info[cl].set_increase + incr;
2034           reg_pressure_info[cl].set_increase = new_incr;
2035           if (! insn_use_p (insn, regno))
2036             reg_pressure_info[cl].change += incr;
2037           create_insn_reg_set (regno, insn);
2038         }
2039       gcc_assert (new_incr < (1 << INCREASE_BITS));
2040     }
2041 }
2042
2043 /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
2044    hard registers involved in the birth.  */
2045 static void
2046 mark_insn_hard_regno_birth (rtx insn, int regno, int nregs,
2047                             bool clobber_p, bool unused_p)
2048 {
2049   enum reg_class cl;
2050   int new_incr, last = regno + nregs;
2051
2052   while (regno < last)
2053     {
2054       gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2055       if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
2056         {
2057           cl = sched_regno_pressure_class[regno];
2058           if (cl != NO_REGS)
2059             {
2060               if (clobber_p)
2061                 {
2062                   new_incr = reg_pressure_info[cl].clobber_increase + 1;
2063                   reg_pressure_info[cl].clobber_increase = new_incr;
2064                 }
2065               else if (unused_p)
2066                 {
2067                   new_incr = reg_pressure_info[cl].unused_set_increase + 1;
2068                   reg_pressure_info[cl].unused_set_increase = new_incr;
2069                 }
2070               else
2071                 {
2072                   new_incr = reg_pressure_info[cl].set_increase + 1;
2073                   reg_pressure_info[cl].set_increase = new_incr;
2074                   if (! insn_use_p (insn, regno))
2075                     reg_pressure_info[cl].change += 1;
2076                   create_insn_reg_set (regno, insn);
2077                 }
2078               gcc_assert (new_incr < (1 << INCREASE_BITS));
2079             }
2080         }
2081       regno++;
2082     }
2083 }
2084
2085 /* Update the register pressure info after birth of pseudo or hard
2086    register REG in INSN.  Arguments CLOBBER_P and UNUSED_P say
2087    correspondingly that the register is in clobber or unused after the
2088    insn.  */
2089 static void
2090 mark_insn_reg_birth (rtx insn, rtx reg, bool clobber_p, bool unused_p)
2091 {
2092   int regno;
2093
2094   if (GET_CODE (reg) == SUBREG)
2095     reg = SUBREG_REG (reg);
2096
2097   if (! REG_P (reg))
2098     return;
2099
2100   regno = REGNO (reg);
2101   if (regno < FIRST_PSEUDO_REGISTER)
2102     mark_insn_hard_regno_birth (insn, regno,
2103                                 hard_regno_nregs[regno][GET_MODE (reg)],
2104                                 clobber_p, unused_p);
2105   else
2106     mark_insn_pseudo_birth (insn, regno, clobber_p, unused_p);
2107 }
2108
2109 /* Update the register pressure info after death of pseudo register
2110    REGNO.  */
2111 static void
2112 mark_pseudo_death (int regno)
2113 {
2114   int incr;
2115   enum reg_class cl;
2116
2117   gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
2118   cl = sched_regno_pressure_class[regno];
2119   if (cl != NO_REGS)
2120     {
2121       incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
2122       reg_pressure_info[cl].change -= incr;
2123     }
2124 }
2125
2126 /* Like mark_pseudo_death except that NREGS saying how many hard
2127    registers involved in the death.  */
2128 static void
2129 mark_hard_regno_death (int regno, int nregs)
2130 {
2131   enum reg_class cl;
2132   int last = regno + nregs;
2133
2134   while (regno < last)
2135     {
2136       gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2137       if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
2138         {
2139           cl = sched_regno_pressure_class[regno];
2140           if (cl != NO_REGS)
2141             reg_pressure_info[cl].change -= 1;
2142         }
2143       regno++;
2144     }
2145 }
2146
2147 /* Update the register pressure info after death of pseudo or hard
2148    register REG.  */
2149 static void
2150 mark_reg_death (rtx reg)
2151 {
2152   int regno;
2153
2154   if (GET_CODE (reg) == SUBREG)
2155     reg = SUBREG_REG (reg);
2156
2157   if (! REG_P (reg))
2158     return;
2159
2160   regno = REGNO (reg);
2161   if (regno < FIRST_PSEUDO_REGISTER)
2162     mark_hard_regno_death (regno, hard_regno_nregs[regno][GET_MODE (reg)]);
2163   else
2164     mark_pseudo_death (regno);
2165 }
2166
2167 /* Process SETTER of REG.  DATA is an insn containing the setter.  */
2168 static void
2169 mark_insn_reg_store (rtx reg, const_rtx setter, void *data)
2170 {
2171   if (setter != NULL_RTX && GET_CODE (setter) != SET)
2172     return;
2173   mark_insn_reg_birth
2174     ((rtx) data, reg, false,
2175      find_reg_note ((const_rtx) data, REG_UNUSED, reg) != NULL_RTX);
2176 }
2177
2178 /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs.  */
2179 static void
2180 mark_insn_reg_clobber (rtx reg, const_rtx setter, void *data)
2181 {
2182   if (GET_CODE (setter) == CLOBBER)
2183     mark_insn_reg_birth ((rtx) data, reg, true, false);
2184 }
2185
2186 /* Set up reg pressure info related to INSN.  */
2187 void
2188 init_insn_reg_pressure_info (rtx insn)
2189 {
2190   int i, len;
2191   enum reg_class cl;
2192   static struct reg_pressure_data *pressure_info;
2193   rtx link;
2194
2195   gcc_assert (sched_pressure != SCHED_PRESSURE_NONE);
2196
2197   if (! INSN_P (insn))
2198     return;
2199
2200   for (i = 0; i < ira_pressure_classes_num; i++)
2201     {
2202       cl = ira_pressure_classes[i];
2203       reg_pressure_info[cl].clobber_increase = 0;
2204       reg_pressure_info[cl].set_increase = 0;
2205       reg_pressure_info[cl].unused_set_increase = 0;
2206       reg_pressure_info[cl].change = 0;
2207     }
2208
2209   note_stores (PATTERN (insn), mark_insn_reg_clobber, insn);
2210
2211   note_stores (PATTERN (insn), mark_insn_reg_store, insn);
2212
2213 #ifdef AUTO_INC_DEC
2214   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2215     if (REG_NOTE_KIND (link) == REG_INC)
2216       mark_insn_reg_store (XEXP (link, 0), NULL_RTX, insn);
2217 #endif
2218
2219   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2220     if (REG_NOTE_KIND (link) == REG_DEAD)
2221       mark_reg_death (XEXP (link, 0));
2222
2223   len = sizeof (struct reg_pressure_data) * ira_pressure_classes_num;
2224   pressure_info
2225     = INSN_REG_PRESSURE (insn) = (struct reg_pressure_data *) xmalloc (len);
2226   if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
2227     INSN_MAX_REG_PRESSURE (insn) = (int *) xcalloc (ira_pressure_classes_num
2228                                                     * sizeof (int), 1);
2229   for (i = 0; i < ira_pressure_classes_num; i++)
2230     {
2231       cl = ira_pressure_classes[i];
2232       pressure_info[i].clobber_increase
2233         = reg_pressure_info[cl].clobber_increase;
2234       pressure_info[i].set_increase = reg_pressure_info[cl].set_increase;
2235       pressure_info[i].unused_set_increase
2236         = reg_pressure_info[cl].unused_set_increase;
2237       pressure_info[i].change = reg_pressure_info[cl].change;
2238     }
2239 }
2240
2241
2242 \f
2243
2244 /* Internal variable for sched_analyze_[12] () functions.
2245    If it is nonzero, this means that sched_analyze_[12] looks
2246    at the most toplevel SET.  */
2247 static bool can_start_lhs_rhs_p;
2248
2249 /* Extend reg info for the deps context DEPS given that
2250    we have just generated a register numbered REGNO.  */
2251 static void
2252 extend_deps_reg_info (struct deps_desc *deps, int regno)
2253 {
2254   int max_regno = regno + 1;
2255
2256   gcc_assert (!reload_completed);
2257
2258   /* In a readonly context, it would not hurt to extend info,
2259      but it should not be needed.  */
2260   if (reload_completed && deps->readonly)
2261     {
2262       deps->max_reg = max_regno;
2263       return;
2264     }
2265
2266   if (max_regno > deps->max_reg)
2267     {
2268       deps->reg_last = XRESIZEVEC (struct deps_reg, deps->reg_last,
2269                                    max_regno);
2270       memset (&deps->reg_last[deps->max_reg],
2271               0, (max_regno - deps->max_reg)
2272               * sizeof (struct deps_reg));
2273       deps->max_reg = max_regno;
2274     }
2275 }
2276
2277 /* Extends REG_INFO_P if needed.  */
2278 void
2279 maybe_extend_reg_info_p (void)
2280 {
2281   /* Extend REG_INFO_P, if needed.  */
2282   if ((unsigned int)max_regno - 1 >= reg_info_p_size)
2283     {
2284       size_t new_reg_info_p_size = max_regno + 128;
2285
2286       gcc_assert (!reload_completed && sel_sched_p ());
2287
2288       reg_info_p = (struct reg_info_t *) xrecalloc (reg_info_p,
2289                                                     new_reg_info_p_size,
2290                                                     reg_info_p_size,
2291                                                     sizeof (*reg_info_p));
2292       reg_info_p_size = new_reg_info_p_size;
2293     }
2294 }
2295
2296 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2297    The type of the reference is specified by REF and can be SET,
2298    CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE.  */
2299
2300 static void
2301 sched_analyze_reg (struct deps_desc *deps, int regno, enum machine_mode mode,
2302                    enum rtx_code ref, rtx insn)
2303 {
2304   /* We could emit new pseudos in renaming.  Extend the reg structures.  */
2305   if (!reload_completed && sel_sched_p ()
2306       && (regno >= max_reg_num () - 1 || regno >= deps->max_reg))
2307     extend_deps_reg_info (deps, regno);
2308
2309   maybe_extend_reg_info_p ();
2310
2311   /* A hard reg in a wide mode may really be multiple registers.
2312      If so, mark all of them just like the first.  */
2313   if (regno < FIRST_PSEUDO_REGISTER)
2314     {
2315       int i = hard_regno_nregs[regno][mode];
2316       if (ref == SET)
2317         {
2318           while (--i >= 0)
2319             note_reg_set (regno + i);
2320         }
2321       else if (ref == USE)
2322         {
2323           while (--i >= 0)
2324             note_reg_use (regno + i);
2325         }
2326       else
2327         {
2328           while (--i >= 0)
2329             note_reg_clobber (regno + i);
2330         }
2331     }
2332
2333   /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2334      it does not reload.  Ignore these as they have served their
2335      purpose already.  */
2336   else if (regno >= deps->max_reg)
2337     {
2338       enum rtx_code code = GET_CODE (PATTERN (insn));
2339       gcc_assert (code == USE || code == CLOBBER);
2340     }
2341
2342   else
2343     {
2344       if (ref == SET)
2345         note_reg_set (regno);
2346       else if (ref == USE)
2347         note_reg_use (regno);
2348       else
2349         note_reg_clobber (regno);
2350
2351       /* Pseudos that are REG_EQUIV to something may be replaced
2352          by that during reloading.  We need only add dependencies for
2353         the address in the REG_EQUIV note.  */
2354       if (!reload_completed && get_reg_known_equiv_p (regno))
2355         {
2356           rtx t = get_reg_known_value (regno);
2357           if (MEM_P (t))
2358             sched_analyze_2 (deps, XEXP (t, 0), insn);
2359         }
2360
2361       /* Don't let it cross a call after scheduling if it doesn't
2362          already cross one.  */
2363       if (REG_N_CALLS_CROSSED (regno) == 0)
2364         {
2365           if (!deps->readonly && ref == USE && !DEBUG_INSN_P (insn))
2366             deps->sched_before_next_call
2367               = alloc_INSN_LIST (insn, deps->sched_before_next_call);
2368           else
2369             add_dependence_list (insn, deps->last_function_call, 1,
2370                                  REG_DEP_ANTI, false);
2371         }
2372     }
2373 }
2374
2375 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2376    rtx, X, creating all dependencies generated by the write to the
2377    destination of X, and reads of everything mentioned.  */
2378
2379 static void
2380 sched_analyze_1 (struct deps_desc *deps, rtx x, rtx insn)
2381 {
2382   rtx dest = XEXP (x, 0);
2383   enum rtx_code code = GET_CODE (x);
2384   bool cslr_p = can_start_lhs_rhs_p;
2385
2386   can_start_lhs_rhs_p = false;
2387
2388   gcc_assert (dest);
2389   if (dest == 0)
2390     return;
2391
2392   if (cslr_p && sched_deps_info->start_lhs)
2393     sched_deps_info->start_lhs (dest);
2394
2395   if (GET_CODE (dest) == PARALLEL)
2396     {
2397       int i;
2398
2399       for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
2400         if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
2401           sched_analyze_1 (deps,
2402                            gen_rtx_CLOBBER (VOIDmode,
2403                                             XEXP (XVECEXP (dest, 0, i), 0)),
2404                            insn);
2405
2406       if (cslr_p && sched_deps_info->finish_lhs)
2407         sched_deps_info->finish_lhs ();
2408
2409       if (code == SET)
2410         {
2411           can_start_lhs_rhs_p = cslr_p;
2412
2413           sched_analyze_2 (deps, SET_SRC (x), insn);
2414
2415           can_start_lhs_rhs_p = false;
2416         }
2417
2418       return;
2419     }
2420
2421   while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
2422          || GET_CODE (dest) == ZERO_EXTRACT)
2423     {
2424       if (GET_CODE (dest) == STRICT_LOW_PART
2425          || GET_CODE (dest) == ZERO_EXTRACT
2426          || df_read_modify_subreg_p (dest))
2427         {
2428           /* These both read and modify the result.  We must handle
2429              them as writes to get proper dependencies for following
2430              instructions.  We must handle them as reads to get proper
2431              dependencies from this to previous instructions.
2432              Thus we need to call sched_analyze_2.  */
2433
2434           sched_analyze_2 (deps, XEXP (dest, 0), insn);
2435         }
2436       if (GET_CODE (dest) == ZERO_EXTRACT)
2437         {
2438           /* The second and third arguments are values read by this insn.  */
2439           sched_analyze_2 (deps, XEXP (dest, 1), insn);
2440           sched_analyze_2 (deps, XEXP (dest, 2), insn);
2441         }
2442       dest = XEXP (dest, 0);
2443     }
2444
2445   if (REG_P (dest))
2446     {
2447       int regno = REGNO (dest);
2448       enum machine_mode mode = GET_MODE (dest);
2449
2450       sched_analyze_reg (deps, regno, mode, code, insn);
2451
2452 #ifdef STACK_REGS
2453       /* Treat all writes to a stack register as modifying the TOS.  */
2454       if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2455         {
2456           /* Avoid analyzing the same register twice.  */
2457           if (regno != FIRST_STACK_REG)
2458             sched_analyze_reg (deps, FIRST_STACK_REG, mode, code, insn);
2459
2460           add_to_hard_reg_set (&implicit_reg_pending_uses, mode,
2461                                FIRST_STACK_REG);
2462         }
2463 #endif
2464     }
2465   else if (MEM_P (dest))
2466     {
2467       /* Writing memory.  */
2468       rtx t = dest;
2469
2470       if (sched_deps_info->use_cselib)
2471         {
2472           enum machine_mode address_mode = get_address_mode (dest);
2473
2474           t = shallow_copy_rtx (dest);
2475           cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2476                                    GET_MODE (t), insn);
2477           XEXP (t, 0)
2478             = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
2479                                                 insn);
2480         }
2481       t = canon_rtx (t);
2482
2483       /* Pending lists can't get larger with a readonly context.  */
2484       if (!deps->readonly
2485           && ((deps->pending_read_list_length + deps->pending_write_list_length)
2486               > MAX_PENDING_LIST_LENGTH))
2487         {
2488           /* Flush all pending reads and writes to prevent the pending lists
2489              from getting any larger.  Insn scheduling runs too slowly when
2490              these lists get long.  When compiling GCC with itself,
2491              this flush occurs 8 times for sparc, and 10 times for m88k using
2492              the default value of 32.  */
2493           flush_pending_lists (deps, insn, false, true);
2494         }
2495       else
2496         {
2497           rtx pending, pending_mem;
2498
2499           pending = deps->pending_read_insns;
2500           pending_mem = deps->pending_read_mems;
2501           while (pending)
2502             {
2503               if (anti_dependence (XEXP (pending_mem, 0), t)
2504                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2505                 note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2506                               DEP_ANTI);
2507
2508               pending = XEXP (pending, 1);
2509               pending_mem = XEXP (pending_mem, 1);
2510             }
2511
2512           pending = deps->pending_write_insns;
2513           pending_mem = deps->pending_write_mems;
2514           while (pending)
2515             {
2516               if (output_dependence (XEXP (pending_mem, 0), t)
2517                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2518                 note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2519                               DEP_OUTPUT);
2520
2521               pending = XEXP (pending, 1);
2522               pending_mem = XEXP (pending_mem, 1);
2523             }
2524
2525           add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2526                                REG_DEP_ANTI, true);
2527           add_dependence_list (insn, deps->pending_jump_insns, 1,
2528                                REG_DEP_CONTROL, true);
2529
2530           if (!deps->readonly)
2531             add_insn_mem_dependence (deps, false, insn, dest);
2532         }
2533       sched_analyze_2 (deps, XEXP (dest, 0), insn);
2534     }
2535
2536   if (cslr_p && sched_deps_info->finish_lhs)
2537     sched_deps_info->finish_lhs ();
2538
2539   /* Analyze reads.  */
2540   if (GET_CODE (x) == SET)
2541     {
2542       can_start_lhs_rhs_p = cslr_p;
2543
2544       sched_analyze_2 (deps, SET_SRC (x), insn);
2545
2546       can_start_lhs_rhs_p = false;
2547     }
2548 }
2549
2550 /* Analyze the uses of memory and registers in rtx X in INSN.  */
2551 static void
2552 sched_analyze_2 (struct deps_desc *deps, rtx x, rtx insn)
2553 {
2554   int i;
2555   int j;
2556   enum rtx_code code;
2557   const char *fmt;
2558   bool cslr_p = can_start_lhs_rhs_p;
2559
2560   can_start_lhs_rhs_p = false;
2561
2562   gcc_assert (x);
2563   if (x == 0)
2564     return;
2565
2566   if (cslr_p && sched_deps_info->start_rhs)
2567     sched_deps_info->start_rhs (x);
2568
2569   code = GET_CODE (x);
2570
2571   switch (code)
2572     {
2573     CASE_CONST_ANY:
2574     case SYMBOL_REF:
2575     case CONST:
2576     case LABEL_REF:
2577       /* Ignore constants.  */
2578       if (cslr_p && sched_deps_info->finish_rhs)
2579         sched_deps_info->finish_rhs ();
2580
2581       return;
2582
2583 #ifdef HAVE_cc0
2584     case CC0:
2585       /* User of CC0 depends on immediately preceding insn.  */
2586       SCHED_GROUP_P (insn) = 1;
2587        /* Don't move CC0 setter to another block (it can set up the
2588         same flag for previous CC0 users which is safe).  */
2589       CANT_MOVE (prev_nonnote_insn (insn)) = 1;
2590
2591       if (cslr_p && sched_deps_info->finish_rhs)
2592         sched_deps_info->finish_rhs ();
2593
2594       return;
2595 #endif
2596
2597     case REG:
2598       {
2599         int regno = REGNO (x);
2600         enum machine_mode mode = GET_MODE (x);
2601
2602         sched_analyze_reg (deps, regno, mode, USE, insn);
2603
2604 #ifdef STACK_REGS
2605       /* Treat all reads of a stack register as modifying the TOS.  */
2606       if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2607         {
2608           /* Avoid analyzing the same register twice.  */
2609           if (regno != FIRST_STACK_REG)
2610             sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
2611           sched_analyze_reg (deps, FIRST_STACK_REG, mode, SET, insn);
2612         }
2613 #endif
2614
2615         if (cslr_p && sched_deps_info->finish_rhs)
2616           sched_deps_info->finish_rhs ();
2617
2618         return;
2619       }
2620
2621     case MEM:
2622       {
2623         /* Reading memory.  */
2624         rtx u;
2625         rtx pending, pending_mem;
2626         rtx t = x;
2627
2628         if (sched_deps_info->use_cselib)
2629           {
2630             enum machine_mode address_mode = get_address_mode (t);
2631
2632             t = shallow_copy_rtx (t);
2633             cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2634                                      GET_MODE (t), insn);
2635             XEXP (t, 0)
2636               = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
2637                                                   insn);
2638           }
2639
2640         if (!DEBUG_INSN_P (insn))
2641           {
2642             t = canon_rtx (t);
2643             pending = deps->pending_read_insns;
2644             pending_mem = deps->pending_read_mems;
2645             while (pending)
2646               {
2647                 if (read_dependence (XEXP (pending_mem, 0), t)
2648                     && ! sched_insns_conditions_mutex_p (insn,
2649                                                          XEXP (pending, 0)))
2650                   note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2651                                 DEP_ANTI);
2652
2653                 pending = XEXP (pending, 1);
2654                 pending_mem = XEXP (pending_mem, 1);
2655               }
2656
2657             pending = deps->pending_write_insns;
2658             pending_mem = deps->pending_write_mems;
2659             while (pending)
2660               {
2661                 if (true_dependence (XEXP (pending_mem, 0), VOIDmode, t)
2662                     && ! sched_insns_conditions_mutex_p (insn,
2663                                                          XEXP (pending, 0)))
2664                   note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2665                                 sched_deps_info->generate_spec_deps
2666                                 ? BEGIN_DATA | DEP_TRUE : DEP_TRUE);
2667
2668                 pending = XEXP (pending, 1);
2669                 pending_mem = XEXP (pending_mem, 1);
2670               }
2671
2672             for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
2673               add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
2674
2675             for (u = deps->pending_jump_insns; u; u = XEXP (u, 1))
2676               if (deps_may_trap_p (x))
2677                 {
2678                   if ((sched_deps_info->generate_spec_deps)
2679                       && sel_sched_p () && (spec_info->mask & BEGIN_CONTROL))
2680                     {
2681                       ds_t ds = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
2682                                               MAX_DEP_WEAK);
2683
2684                       note_dep (XEXP (u, 0), ds);
2685                     }
2686                   else
2687                     add_dependence (insn, XEXP (u, 0), REG_DEP_CONTROL);
2688                 }
2689           }
2690
2691         /* Always add these dependencies to pending_reads, since
2692            this insn may be followed by a write.  */
2693         if (!deps->readonly)
2694           add_insn_mem_dependence (deps, true, insn, x);
2695
2696         sched_analyze_2 (deps, XEXP (x, 0), insn);
2697
2698         if (cslr_p && sched_deps_info->finish_rhs)
2699           sched_deps_info->finish_rhs ();
2700
2701         return;
2702       }
2703
2704     /* Force pending stores to memory in case a trap handler needs them.  */
2705     case TRAP_IF:
2706       flush_pending_lists (deps, insn, true, false);
2707       break;
2708
2709     case PREFETCH:
2710       if (PREFETCH_SCHEDULE_BARRIER_P (x))
2711         reg_pending_barrier = TRUE_BARRIER;
2712       break;
2713
2714     case UNSPEC_VOLATILE:
2715       flush_pending_lists (deps, insn, true, true);
2716       /* FALLTHRU */
2717
2718     case ASM_OPERANDS:
2719     case ASM_INPUT:
2720       {
2721         /* Traditional and volatile asm instructions must be considered to use
2722            and clobber all hard registers, all pseudo-registers and all of
2723            memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
2724
2725            Consider for instance a volatile asm that changes the fpu rounding
2726            mode.  An insn should not be moved across this even if it only uses
2727            pseudo-regs because it might give an incorrectly rounded result.  */
2728         if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
2729           reg_pending_barrier = TRUE_BARRIER;
2730
2731         /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2732            We can not just fall through here since then we would be confused
2733            by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2734            traditional asms unlike their normal usage.  */
2735
2736         if (code == ASM_OPERANDS)
2737           {
2738             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
2739               sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
2740
2741             if (cslr_p && sched_deps_info->finish_rhs)
2742               sched_deps_info->finish_rhs ();
2743
2744             return;
2745           }
2746         break;
2747       }
2748
2749     case PRE_DEC:
2750     case POST_DEC:
2751     case PRE_INC:
2752     case POST_INC:
2753       /* These both read and modify the result.  We must handle them as writes
2754          to get proper dependencies for following instructions.  We must handle
2755          them as reads to get proper dependencies from this to previous
2756          instructions.  Thus we need to pass them to both sched_analyze_1
2757          and sched_analyze_2.  We must call sched_analyze_2 first in order
2758          to get the proper antecedent for the read.  */
2759       sched_analyze_2 (deps, XEXP (x, 0), insn);
2760       sched_analyze_1 (deps, x, insn);
2761
2762       if (cslr_p && sched_deps_info->finish_rhs)
2763         sched_deps_info->finish_rhs ();
2764
2765       return;
2766
2767     case POST_MODIFY:
2768     case PRE_MODIFY:
2769       /* op0 = op0 + op1 */
2770       sched_analyze_2 (deps, XEXP (x, 0), insn);
2771       sched_analyze_2 (deps, XEXP (x, 1), insn);
2772       sched_analyze_1 (deps, x, insn);
2773
2774       if (cslr_p && sched_deps_info->finish_rhs)
2775         sched_deps_info->finish_rhs ();
2776
2777       return;
2778
2779     default:
2780       break;
2781     }
2782
2783   /* Other cases: walk the insn.  */
2784   fmt = GET_RTX_FORMAT (code);
2785   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2786     {
2787       if (fmt[i] == 'e')
2788         sched_analyze_2 (deps, XEXP (x, i), insn);
2789       else if (fmt[i] == 'E')
2790         for (j = 0; j < XVECLEN (x, i); j++)
2791           sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
2792     }
2793
2794   if (cslr_p && sched_deps_info->finish_rhs)
2795     sched_deps_info->finish_rhs ();
2796 }
2797
2798 /* Analyze an INSN with pattern X to find all dependencies.  */
2799 static void
2800 sched_analyze_insn (struct deps_desc *deps, rtx x, rtx insn)
2801 {
2802   RTX_CODE code = GET_CODE (x);
2803   rtx link;
2804   unsigned i;
2805   reg_set_iterator rsi;
2806
2807   if (! reload_completed)
2808     {
2809       HARD_REG_SET temp;
2810
2811       extract_insn (insn);
2812       preprocess_constraints ();
2813       ira_implicitly_set_insn_hard_regs (&temp);
2814       AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
2815       IOR_HARD_REG_SET (implicit_reg_pending_clobbers, temp);
2816     }
2817
2818   can_start_lhs_rhs_p = (NONJUMP_INSN_P (insn)
2819                          && code == SET);
2820
2821   if (may_trap_p (x))
2822     /* Avoid moving trapping instructions across function calls that might
2823        not always return.  */
2824     add_dependence_list (insn, deps->last_function_call_may_noreturn,
2825                          1, REG_DEP_ANTI, true);
2826
2827   /* We must avoid creating a situation in which two successors of the
2828      current block have different unwind info after scheduling.  If at any
2829      point the two paths re-join this leads to incorrect unwind info.  */
2830   /* ??? There are certain situations involving a forced frame pointer in
2831      which, with extra effort, we could fix up the unwind info at a later
2832      CFG join.  However, it seems better to notice these cases earlier
2833      during prologue generation and avoid marking the frame pointer setup
2834      as frame-related at all.  */
2835   if (RTX_FRAME_RELATED_P (insn))
2836     {
2837       /* Make sure prologue insn is scheduled before next jump.  */
2838       deps->sched_before_next_jump
2839         = alloc_INSN_LIST (insn, deps->sched_before_next_jump);
2840
2841       /* Make sure epilogue insn is scheduled after preceding jumps.  */
2842       add_dependence_list (insn, deps->pending_jump_insns, 1, REG_DEP_ANTI,
2843                            true);
2844     }
2845
2846   if (code == COND_EXEC)
2847     {
2848       sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
2849
2850       /* ??? Should be recording conditions so we reduce the number of
2851          false dependencies.  */
2852       x = COND_EXEC_CODE (x);
2853       code = GET_CODE (x);
2854     }
2855   if (code == SET || code == CLOBBER)
2856     {
2857       sched_analyze_1 (deps, x, insn);
2858
2859       /* Bare clobber insns are used for letting life analysis, reg-stack
2860          and others know that a value is dead.  Depend on the last call
2861          instruction so that reg-stack won't get confused.  */
2862       if (code == CLOBBER)
2863         add_dependence_list (insn, deps->last_function_call, 1,
2864                              REG_DEP_OUTPUT, true);
2865     }
2866   else if (code == PARALLEL)
2867     {
2868       for (i = XVECLEN (x, 0); i--;)
2869         {
2870           rtx sub = XVECEXP (x, 0, i);
2871           code = GET_CODE (sub);
2872
2873           if (code == COND_EXEC)
2874             {
2875               sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
2876               sub = COND_EXEC_CODE (sub);
2877               code = GET_CODE (sub);
2878             }
2879           if (code == SET || code == CLOBBER)
2880             sched_analyze_1 (deps, sub, insn);
2881           else
2882             sched_analyze_2 (deps, sub, insn);
2883         }
2884     }
2885   else
2886     sched_analyze_2 (deps, x, insn);
2887
2888   /* Mark registers CLOBBERED or used by called function.  */
2889   if (CALL_P (insn))
2890     {
2891       for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
2892         {
2893           if (GET_CODE (XEXP (link, 0)) == CLOBBER)
2894             sched_analyze_1 (deps, XEXP (link, 0), insn);
2895           else if (GET_CODE (XEXP (link, 0)) != SET)
2896             sched_analyze_2 (deps, XEXP (link, 0), insn);
2897         }
2898       /* Don't schedule anything after a tail call, tail call needs
2899          to use at least all call-saved registers.  */
2900       if (SIBLING_CALL_P (insn))
2901         reg_pending_barrier = TRUE_BARRIER;
2902       else if (find_reg_note (insn, REG_SETJMP, NULL))
2903         reg_pending_barrier = MOVE_BARRIER;
2904     }
2905
2906   if (JUMP_P (insn))
2907     {
2908       rtx next;
2909       next = next_nonnote_nondebug_insn (insn);
2910       if (next && BARRIER_P (next))
2911         reg_pending_barrier = MOVE_BARRIER;
2912       else
2913         {
2914           rtx pending, pending_mem;
2915
2916           if (sched_deps_info->compute_jump_reg_dependencies)
2917             {
2918               (*sched_deps_info->compute_jump_reg_dependencies)
2919                 (insn, reg_pending_control_uses);
2920
2921               /* Make latency of jump equal to 0 by using anti-dependence.  */
2922               EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
2923                 {
2924                   struct deps_reg *reg_last = &deps->reg_last[i];
2925                   add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI,
2926                                        false);
2927                   add_dependence_list (insn, reg_last->implicit_sets,
2928                                        0, REG_DEP_ANTI, false);
2929                   add_dependence_list (insn, reg_last->clobbers, 0,
2930                                        REG_DEP_ANTI, false);
2931                 }
2932             }
2933
2934           /* All memory writes and volatile reads must happen before the
2935              jump.  Non-volatile reads must happen before the jump iff
2936              the result is needed by the above register used mask.  */
2937
2938           pending = deps->pending_write_insns;
2939           pending_mem = deps->pending_write_mems;
2940           while (pending)
2941             {
2942               if (! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2943                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
2944               pending = XEXP (pending, 1);
2945               pending_mem = XEXP (pending_mem, 1);
2946             }
2947
2948           pending = deps->pending_read_insns;
2949           pending_mem = deps->pending_read_mems;
2950           while (pending)
2951             {
2952               if (MEM_VOLATILE_P (XEXP (pending_mem, 0))
2953                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2954                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
2955               pending = XEXP (pending, 1);
2956               pending_mem = XEXP (pending_mem, 1);
2957             }
2958
2959           add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2960                                REG_DEP_ANTI, true);
2961           add_dependence_list (insn, deps->pending_jump_insns, 1,
2962                                REG_DEP_ANTI, true);
2963         }
2964     }
2965
2966   /* If this instruction can throw an exception, then moving it changes
2967      where block boundaries fall.  This is mighty confusing elsewhere.
2968      Therefore, prevent such an instruction from being moved.  Same for
2969      non-jump instructions that define block boundaries.
2970      ??? Unclear whether this is still necessary in EBB mode.  If not,
2971      add_branch_dependences should be adjusted for RGN mode instead.  */
2972   if (((CALL_P (insn) || JUMP_P (insn)) && can_throw_internal (insn))
2973       || (NONJUMP_INSN_P (insn) && control_flow_insn_p (insn)))
2974     reg_pending_barrier = MOVE_BARRIER;
2975
2976   if (sched_pressure != SCHED_PRESSURE_NONE)
2977     {
2978       setup_insn_reg_uses (deps, insn);
2979       init_insn_reg_pressure_info (insn);
2980     }
2981
2982   /* Add register dependencies for insn.  */
2983   if (DEBUG_INSN_P (insn))
2984     {
2985       rtx prev = deps->last_debug_insn;
2986       rtx u;
2987
2988       if (!deps->readonly)
2989         deps->last_debug_insn = insn;
2990
2991       if (prev)
2992         add_dependence (insn, prev, REG_DEP_ANTI);
2993
2994       add_dependence_list (insn, deps->last_function_call, 1,
2995                            REG_DEP_ANTI, false);
2996
2997       if (!sel_sched_p ())
2998         for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
2999           add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3000
3001       EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
3002         {
3003           struct deps_reg *reg_last = &deps->reg_last[i];
3004           add_dependence_list (insn, reg_last->sets, 1, REG_DEP_ANTI, false);
3005           /* There's no point in making REG_DEP_CONTROL dependencies for
3006              debug insns.  */
3007           add_dependence_list (insn, reg_last->clobbers, 1, REG_DEP_ANTI,
3008                                false);
3009
3010           if (!deps->readonly)
3011             reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3012         }
3013       CLEAR_REG_SET (reg_pending_uses);
3014
3015       /* Quite often, a debug insn will refer to stuff in the
3016          previous instruction, but the reason we want this
3017          dependency here is to make sure the scheduler doesn't
3018          gratuitously move a debug insn ahead.  This could dirty
3019          DF flags and cause additional analysis that wouldn't have
3020          occurred in compilation without debug insns, and such
3021          additional analysis can modify the generated code.  */
3022       prev = PREV_INSN (insn);
3023
3024       if (prev && NONDEBUG_INSN_P (prev))
3025         add_dependence (insn, prev, REG_DEP_ANTI);
3026     }
3027   else
3028     {
3029       regset_head set_or_clobbered;
3030
3031       EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
3032         {
3033           struct deps_reg *reg_last = &deps->reg_last[i];
3034           add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false);
3035           add_dependence_list (insn, reg_last->implicit_sets, 0, REG_DEP_ANTI,
3036                                false);
3037           add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE,
3038                                false);
3039
3040           if (!deps->readonly)
3041             {
3042               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3043               reg_last->uses_length++;
3044             }
3045         }
3046
3047       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3048         if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i))
3049           {
3050             struct deps_reg *reg_last = &deps->reg_last[i];
3051             add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false);
3052             add_dependence_list (insn, reg_last->implicit_sets, 0,
3053                                  REG_DEP_ANTI, false);
3054             add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE,
3055                                  false);
3056
3057             if (!deps->readonly)
3058               {
3059                 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3060                 reg_last->uses_length++;
3061               }
3062           }
3063
3064       if (targetm.sched.exposed_pipeline)
3065         {
3066           INIT_REG_SET (&set_or_clobbered);
3067           bitmap_ior (&set_or_clobbered, reg_pending_clobbers,
3068                       reg_pending_sets);
3069           EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered, 0, i, rsi)
3070             {
3071               struct deps_reg *reg_last = &deps->reg_last[i];
3072               rtx list;
3073               for (list = reg_last->uses; list; list = XEXP (list, 1))
3074                 {
3075                   rtx other = XEXP (list, 0);
3076                   if (INSN_CACHED_COND (other) != const_true_rtx
3077                       && refers_to_regno_p (i, i + 1, INSN_CACHED_COND (other), NULL))
3078                     INSN_CACHED_COND (other) = const_true_rtx;
3079                 }
3080             }
3081         }
3082
3083       /* If the current insn is conditional, we can't free any
3084          of the lists.  */
3085       if (sched_has_condition_p (insn))
3086         {
3087           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3088             {
3089               struct deps_reg *reg_last = &deps->reg_last[i];
3090               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3091                                    false);
3092               add_dependence_list (insn, reg_last->implicit_sets, 0,
3093                                    REG_DEP_ANTI, false);
3094               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3095                                    false);
3096               add_dependence_list (insn, reg_last->control_uses, 0,
3097                                    REG_DEP_CONTROL, false);
3098
3099               if (!deps->readonly)
3100                 {
3101                   reg_last->clobbers
3102                     = alloc_INSN_LIST (insn, reg_last->clobbers);
3103                   reg_last->clobbers_length++;
3104                 }
3105             }
3106           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3107             {
3108               struct deps_reg *reg_last = &deps->reg_last[i];
3109               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3110                                    false);
3111               add_dependence_list (insn, reg_last->implicit_sets, 0,
3112                                    REG_DEP_ANTI, false);
3113               add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT,
3114                                    false);
3115               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3116                                    false);
3117               add_dependence_list (insn, reg_last->control_uses, 0,
3118                                    REG_DEP_CONTROL, false);
3119
3120               if (!deps->readonly)
3121                 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3122             }
3123         }
3124       else
3125         {
3126           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3127             {
3128               struct deps_reg *reg_last = &deps->reg_last[i];
3129               if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
3130                   || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
3131                 {
3132                   add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3133                                                 REG_DEP_OUTPUT, false);
3134                   add_dependence_list_and_free (deps, insn,
3135                                                 &reg_last->implicit_sets, 0,
3136                                                 REG_DEP_ANTI, false);
3137                   add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3138                                                 REG_DEP_ANTI, false);
3139                   add_dependence_list_and_free (deps, insn,
3140                                                 &reg_last->control_uses, 0,
3141                                                 REG_DEP_ANTI, false);
3142                   add_dependence_list_and_free (deps, insn,
3143                                                 &reg_last->clobbers, 0,
3144                                                 REG_DEP_OUTPUT, false);
3145
3146                   if (!deps->readonly)
3147                     {
3148                       reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3149                       reg_last->clobbers_length = 0;
3150                       reg_last->uses_length = 0;
3151                     }
3152                 }
3153               else
3154                 {
3155                   add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3156                                        false);
3157                   add_dependence_list (insn, reg_last->implicit_sets, 0,
3158                                        REG_DEP_ANTI, false);
3159                   add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3160                                        false);
3161                   add_dependence_list (insn, reg_last->control_uses, 0,
3162                                        REG_DEP_CONTROL, false);
3163                 }
3164
3165               if (!deps->readonly)
3166                 {
3167                   reg_last->clobbers_length++;
3168                   reg_last->clobbers
3169                     = alloc_INSN_LIST (insn, reg_last->clobbers);
3170                 }
3171             }
3172           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3173             {
3174               struct deps_reg *reg_last = &deps->reg_last[i];
3175
3176               add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3177                                             REG_DEP_OUTPUT, false);
3178               add_dependence_list_and_free (deps, insn,
3179                                             &reg_last->implicit_sets,
3180                                             0, REG_DEP_ANTI, false);
3181               add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3182                                             REG_DEP_OUTPUT, false);
3183               add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3184                                             REG_DEP_ANTI, false);
3185               add_dependence_list (insn, reg_last->control_uses, 0,
3186                                    REG_DEP_CONTROL, false);
3187
3188               if (!deps->readonly)
3189                 {
3190                   reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3191                   reg_last->uses_length = 0;
3192                   reg_last->clobbers_length = 0;
3193                 }
3194             }
3195         }
3196       if (!deps->readonly)
3197         {
3198           EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
3199             {
3200               struct deps_reg *reg_last = &deps->reg_last[i];
3201               reg_last->control_uses
3202                 = alloc_INSN_LIST (insn, reg_last->control_uses);
3203             }
3204         }
3205     }
3206
3207   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3208     if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
3209       {
3210         struct deps_reg *reg_last = &deps->reg_last[i];
3211         add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI, false);
3212         add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI, false);
3213         add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI, false);
3214         add_dependence_list (insn, reg_last->control_uses, 0, REG_DEP_ANTI,
3215                              false);
3216
3217         if (!deps->readonly)
3218           reg_last->implicit_sets
3219             = alloc_INSN_LIST (insn, reg_last->implicit_sets);
3220       }
3221
3222   if (!deps->readonly)
3223     {
3224       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
3225       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
3226       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
3227       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3228         if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i)
3229             || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
3230           SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3231
3232       /* Set up the pending barrier found.  */
3233       deps->last_reg_pending_barrier = reg_pending_barrier;
3234     }
3235
3236   CLEAR_REG_SET (reg_pending_uses);
3237   CLEAR_REG_SET (reg_pending_clobbers);
3238   CLEAR_REG_SET (reg_pending_sets);
3239   CLEAR_REG_SET (reg_pending_control_uses);
3240   CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
3241   CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
3242
3243   /* Add dependencies if a scheduling barrier was found.  */
3244   if (reg_pending_barrier)
3245     {
3246       /* In the case of barrier the most added dependencies are not
3247          real, so we use anti-dependence here.  */
3248       if (sched_has_condition_p (insn))
3249         {
3250           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3251             {
3252               struct deps_reg *reg_last = &deps->reg_last[i];
3253               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3254                                    true);
3255               add_dependence_list (insn, reg_last->sets, 0,
3256                                    reg_pending_barrier == TRUE_BARRIER
3257                                    ? REG_DEP_TRUE : REG_DEP_ANTI, true);
3258               add_dependence_list (insn, reg_last->implicit_sets, 0,
3259                                    REG_DEP_ANTI, true);
3260               add_dependence_list (insn, reg_last->clobbers, 0,
3261                                    reg_pending_barrier == TRUE_BARRIER
3262                                    ? REG_DEP_TRUE : REG_DEP_ANTI, true);
3263             }
3264         }
3265       else
3266         {
3267           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3268             {
3269               struct deps_reg *reg_last = &deps->reg_last[i];
3270               add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3271                                             REG_DEP_ANTI, true);
3272               add_dependence_list_and_free (deps, insn,
3273                                             &reg_last->control_uses, 0,
3274                                             REG_DEP_CONTROL, true);
3275               add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3276                                             reg_pending_barrier == TRUE_BARRIER
3277                                             ? REG_DEP_TRUE : REG_DEP_ANTI,
3278                                             true);
3279               add_dependence_list_and_free (deps, insn,
3280                                             &reg_last->implicit_sets, 0,
3281                                             REG_DEP_ANTI, true);
3282               add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3283                                             reg_pending_barrier == TRUE_BARRIER
3284                                             ? REG_DEP_TRUE : REG_DEP_ANTI,
3285                                             true);
3286
3287               if (!deps->readonly)
3288                 {
3289                   reg_last->uses_length = 0;
3290                   reg_last->clobbers_length = 0;
3291                 }
3292             }
3293         }
3294
3295       if (!deps->readonly)
3296         for (i = 0; i < (unsigned)deps->max_reg; i++)
3297           {
3298             struct deps_reg *reg_last = &deps->reg_last[i];
3299             reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3300             SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3301           }
3302
3303       /* Flush pending lists on jumps, but not on speculative checks.  */
3304       if (JUMP_P (insn) && !(sel_sched_p ()
3305                              && sel_insn_is_speculation_check (insn)))
3306         flush_pending_lists (deps, insn, true, true);
3307
3308       reg_pending_barrier = NOT_A_BARRIER;
3309     }
3310
3311   /* If a post-call group is still open, see if it should remain so.
3312      This insn must be a simple move of a hard reg to a pseudo or
3313      vice-versa.
3314
3315      We must avoid moving these insns for correctness on targets
3316      with small register classes, and for special registers like
3317      PIC_OFFSET_TABLE_REGNUM.  For simplicity, extend this to all
3318      hard regs for all targets.  */
3319
3320   if (deps->in_post_call_group_p)
3321     {
3322       rtx tmp, set = single_set (insn);
3323       int src_regno, dest_regno;
3324
3325       if (set == NULL)
3326         {
3327           if (DEBUG_INSN_P (insn))
3328             /* We don't want to mark debug insns as part of the same
3329                sched group.  We know they really aren't, but if we use
3330                debug insns to tell that a call group is over, we'll
3331                get different code if debug insns are not there and
3332                instructions that follow seem like they should be part
3333                of the call group.
3334
3335                Also, if we did, chain_to_prev_insn would move the
3336                deps of the debug insn to the call insn, modifying
3337                non-debug post-dependency counts of the debug insn
3338                dependencies and otherwise messing with the scheduling
3339                order.
3340
3341                Instead, let such debug insns be scheduled freely, but
3342                keep the call group open in case there are insns that
3343                should be part of it afterwards.  Since we grant debug
3344                insns higher priority than even sched group insns, it
3345                will all turn out all right.  */
3346             goto debug_dont_end_call_group;
3347           else
3348             goto end_call_group;
3349         }
3350
3351       tmp = SET_DEST (set);
3352       if (GET_CODE (tmp) == SUBREG)
3353         tmp = SUBREG_REG (tmp);
3354       if (REG_P (tmp))
3355         dest_regno = REGNO (tmp);
3356       else
3357         goto end_call_group;
3358
3359       tmp = SET_SRC (set);
3360       if (GET_CODE (tmp) == SUBREG)
3361         tmp = SUBREG_REG (tmp);
3362       if ((GET_CODE (tmp) == PLUS
3363            || GET_CODE (tmp) == MINUS)
3364           && REG_P (XEXP (tmp, 0))
3365           && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
3366           && dest_regno == STACK_POINTER_REGNUM)
3367         src_regno = STACK_POINTER_REGNUM;
3368       else if (REG_P (tmp))
3369         src_regno = REGNO (tmp);
3370       else
3371         goto end_call_group;
3372
3373       if (src_regno < FIRST_PSEUDO_REGISTER
3374           || dest_regno < FIRST_PSEUDO_REGISTER)
3375         {
3376           if (!deps->readonly
3377               && deps->in_post_call_group_p == post_call_initial)
3378             deps->in_post_call_group_p = post_call;
3379
3380           if (!sel_sched_p () || sched_emulate_haifa_p)
3381             {
3382               SCHED_GROUP_P (insn) = 1;
3383               CANT_MOVE (insn) = 1;
3384             }
3385         }
3386       else
3387         {
3388         end_call_group:
3389           if (!deps->readonly)
3390             deps->in_post_call_group_p = not_post_call;
3391         }
3392     }
3393
3394  debug_dont_end_call_group:
3395   if ((current_sched_info->flags & DO_SPECULATION)
3396       && !sched_insn_is_legitimate_for_speculation_p (insn, 0))
3397     /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3398        be speculated.  */
3399     {
3400       if (sel_sched_p ())
3401         sel_mark_hard_insn (insn);
3402       else
3403         {
3404           sd_iterator_def sd_it;
3405           dep_t dep;
3406
3407           for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3408                sd_iterator_cond (&sd_it, &dep);)
3409             change_spec_dep_to_hard (sd_it);
3410         }
3411     }
3412 }
3413
3414 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3415    longjmp, loop forever, ...).  */
3416 /* FIXME: Why can't this function just use flags_from_decl_or_type and
3417    test for ECF_NORETURN?  */
3418 static bool
3419 call_may_noreturn_p (rtx insn)
3420 {
3421   rtx call;
3422
3423   /* const or pure calls that aren't looping will always return.  */
3424   if (RTL_CONST_OR_PURE_CALL_P (insn)
3425       && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))
3426     return false;
3427
3428   call = PATTERN (insn);
3429   if (GET_CODE (call) == PARALLEL)
3430     call = XVECEXP (call, 0, 0);
3431   if (GET_CODE (call) == SET)
3432     call = SET_SRC (call);
3433   if (GET_CODE (call) == CALL
3434       && MEM_P (XEXP (call, 0))
3435       && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
3436     {
3437       rtx symbol = XEXP (XEXP (call, 0), 0);
3438       if (SYMBOL_REF_DECL (symbol)
3439           && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
3440         {
3441           if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
3442               == BUILT_IN_NORMAL)
3443             switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol)))
3444               {
3445               case BUILT_IN_BCMP:
3446               case BUILT_IN_BCOPY:
3447               case BUILT_IN_BZERO:
3448               case BUILT_IN_INDEX:
3449               case BUILT_IN_MEMCHR:
3450               case BUILT_IN_MEMCMP:
3451               case BUILT_IN_MEMCPY:
3452               case BUILT_IN_MEMMOVE:
3453               case BUILT_IN_MEMPCPY:
3454               case BUILT_IN_MEMSET:
3455               case BUILT_IN_RINDEX:
3456               case BUILT_IN_STPCPY:
3457               case BUILT_IN_STPNCPY:
3458               case BUILT_IN_STRCAT:
3459               case BUILT_IN_STRCHR:
3460               case BUILT_IN_STRCMP:
3461               case BUILT_IN_STRCPY:
3462               case BUILT_IN_STRCSPN:
3463               case BUILT_IN_STRLEN:
3464               case BUILT_IN_STRNCAT:
3465               case BUILT_IN_STRNCMP:
3466               case BUILT_IN_STRNCPY:
3467               case BUILT_IN_STRPBRK:
3468               case BUILT_IN_STRRCHR:
3469               case BUILT_IN_STRSPN:
3470               case BUILT_IN_STRSTR:
3471                 /* Assume certain string/memory builtins always return.  */
3472                 return false;
3473               default:
3474                 break;
3475               }
3476         }
3477     }
3478
3479   /* For all other calls assume that they might not always return.  */
3480   return true;
3481 }
3482
3483 /* Return true if INSN should be made dependent on the previous instruction
3484    group, and if all INSN's dependencies should be moved to the first
3485    instruction of that group.  */
3486
3487 static bool
3488 chain_to_prev_insn_p (rtx insn)
3489 {
3490   rtx prev, x;
3491
3492   /* INSN forms a group with the previous instruction.  */
3493   if (SCHED_GROUP_P (insn))
3494     return true;
3495
3496   /* If the previous instruction clobbers a register R and this one sets
3497      part of R, the clobber was added specifically to help us track the
3498      liveness of R.  There's no point scheduling the clobber and leaving
3499      INSN behind, especially if we move the clobber to another block.  */
3500   prev = prev_nonnote_nondebug_insn (insn);
3501   if (prev
3502       && INSN_P (prev)
3503       && BLOCK_FOR_INSN (prev) == BLOCK_FOR_INSN (insn)
3504       && GET_CODE (PATTERN (prev)) == CLOBBER)
3505     {
3506       x = XEXP (PATTERN (prev), 0);
3507       if (set_of (x, insn))
3508         return true;
3509     }
3510
3511   return false;
3512 }
3513
3514 /* Analyze INSN with DEPS as a context.  */
3515 void
3516 deps_analyze_insn (struct deps_desc *deps, rtx insn)
3517 {
3518   if (sched_deps_info->start_insn)
3519     sched_deps_info->start_insn (insn);
3520
3521   /* Record the condition for this insn.  */
3522   if (NONDEBUG_INSN_P (insn))
3523     {
3524       rtx t;
3525       sched_get_condition_with_rev (insn, NULL);
3526       t = INSN_CACHED_COND (insn);
3527       INSN_COND_DEPS (insn) = NULL_RTX;
3528       if (reload_completed
3529           && (current_sched_info->flags & DO_PREDICATION)
3530           && COMPARISON_P (t)
3531           && REG_P (XEXP (t, 0))
3532           && CONSTANT_P (XEXP (t, 1)))
3533         {
3534           unsigned int regno;
3535           int nregs;
3536           t = XEXP (t, 0);
3537           regno = REGNO (t);
3538           nregs = hard_regno_nregs[regno][GET_MODE (t)];
3539           t = NULL_RTX;
3540           while (nregs-- > 0)
3541             {
3542               struct deps_reg *reg_last = &deps->reg_last[regno + nregs];
3543               t = concat_INSN_LIST (reg_last->sets, t);
3544               t = concat_INSN_LIST (reg_last->clobbers, t);
3545               t = concat_INSN_LIST (reg_last->implicit_sets, t);
3546             }
3547           INSN_COND_DEPS (insn) = t;
3548         }
3549     }
3550
3551   if (JUMP_P (insn))
3552     {
3553       /* Make each JUMP_INSN (but not a speculative check)
3554          a scheduling barrier for memory references.  */
3555       if (!deps->readonly
3556           && !(sel_sched_p ()
3557                && sel_insn_is_speculation_check (insn)))
3558         {
3559           /* Keep the list a reasonable size.  */
3560           if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
3561             flush_pending_lists (deps, insn, true, true);
3562           else
3563             deps->pending_jump_insns
3564               = alloc_INSN_LIST (insn, deps->pending_jump_insns);
3565         }
3566
3567       /* For each insn which shouldn't cross a jump, add a dependence.  */
3568       add_dependence_list_and_free (deps, insn,
3569                                     &deps->sched_before_next_jump, 1,
3570                                     REG_DEP_ANTI, true);
3571
3572       sched_analyze_insn (deps, PATTERN (insn), insn);
3573     }
3574   else if (NONJUMP_INSN_P (insn) || DEBUG_INSN_P (insn))
3575     {
3576       sched_analyze_insn (deps, PATTERN (insn), insn);
3577     }
3578   else if (CALL_P (insn))
3579     {
3580       int i;
3581
3582       CANT_MOVE (insn) = 1;
3583
3584       if (find_reg_note (insn, REG_SETJMP, NULL))
3585         {
3586           /* This is setjmp.  Assume that all registers, not just
3587              hard registers, may be clobbered by this call.  */
3588           reg_pending_barrier = MOVE_BARRIER;
3589         }
3590       else
3591         {
3592           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3593             /* A call may read and modify global register variables.  */
3594             if (global_regs[i])
3595               {
3596                 SET_REGNO_REG_SET (reg_pending_sets, i);
3597                 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3598               }
3599           /* Other call-clobbered hard regs may be clobbered.
3600              Since we only have a choice between 'might be clobbered'
3601              and 'definitely not clobbered', we must include all
3602              partly call-clobbered registers here.  */
3603             else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
3604                      || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3605               SET_REGNO_REG_SET (reg_pending_clobbers, i);
3606           /* We don't know what set of fixed registers might be used
3607              by the function, but it is certain that the stack pointer
3608              is among them, but be conservative.  */
3609             else if (fixed_regs[i])
3610               SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3611           /* The frame pointer is normally not used by the function
3612              itself, but by the debugger.  */
3613           /* ??? MIPS o32 is an exception.  It uses the frame pointer
3614              in the macro expansion of jal but does not represent this
3615              fact in the call_insn rtl.  */
3616             else if (i == FRAME_POINTER_REGNUM
3617                      || (i == HARD_FRAME_POINTER_REGNUM
3618                          && (! reload_completed || frame_pointer_needed)))
3619               SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3620         }
3621
3622       /* For each insn which shouldn't cross a call, add a dependence
3623          between that insn and this call insn.  */
3624       add_dependence_list_and_free (deps, insn,
3625                                     &deps->sched_before_next_call, 1,
3626                                     REG_DEP_ANTI, true);
3627
3628       sched_analyze_insn (deps, PATTERN (insn), insn);
3629
3630       /* If CALL would be in a sched group, then this will violate
3631          convention that sched group insns have dependencies only on the
3632          previous instruction.
3633
3634          Of course one can say: "Hey!  What about head of the sched group?"
3635          And I will answer: "Basic principles (one dep per insn) are always
3636          the same."  */
3637       gcc_assert (!SCHED_GROUP_P (insn));
3638
3639       /* In the absence of interprocedural alias analysis, we must flush
3640          all pending reads and writes, and start new dependencies starting
3641          from here.  But only flush writes for constant calls (which may
3642          be passed a pointer to something we haven't written yet).  */
3643       flush_pending_lists (deps, insn, true, ! RTL_CONST_OR_PURE_CALL_P (insn));
3644
3645       if (!deps->readonly)
3646         {
3647           /* Remember the last function call for limiting lifetimes.  */
3648           free_INSN_LIST_list (&deps->last_function_call);
3649           deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3650
3651           if (call_may_noreturn_p (insn))
3652             {
3653               /* Remember the last function call that might not always return
3654                  normally for limiting moves of trapping insns.  */
3655               free_INSN_LIST_list (&deps->last_function_call_may_noreturn);
3656               deps->last_function_call_may_noreturn
3657                 = alloc_INSN_LIST (insn, NULL_RTX);
3658             }
3659
3660           /* Before reload, begin a post-call group, so as to keep the
3661              lifetimes of hard registers correct.  */
3662           if (! reload_completed)
3663             deps->in_post_call_group_p = post_call;
3664         }
3665     }
3666
3667   if (sched_deps_info->use_cselib)
3668     cselib_process_insn (insn);
3669
3670   /* EH_REGION insn notes can not appear until well after we complete
3671      scheduling.  */
3672   if (NOTE_P (insn))
3673     gcc_assert (NOTE_KIND (insn) != NOTE_INSN_EH_REGION_BEG
3674                 && NOTE_KIND (insn) != NOTE_INSN_EH_REGION_END);
3675
3676   if (sched_deps_info->finish_insn)
3677     sched_deps_info->finish_insn ();
3678
3679   /* Fixup the dependencies in the sched group.  */
3680   if ((NONJUMP_INSN_P (insn) || JUMP_P (insn))
3681       && chain_to_prev_insn_p (insn)
3682       && !sel_sched_p ())
3683     chain_to_prev_insn (insn);
3684 }
3685
3686 /* Initialize DEPS for the new block beginning with HEAD.  */
3687 void
3688 deps_start_bb (struct deps_desc *deps, rtx head)
3689 {
3690   gcc_assert (!deps->readonly);
3691
3692   /* Before reload, if the previous block ended in a call, show that
3693      we are inside a post-call group, so as to keep the lifetimes of
3694      hard registers correct.  */
3695   if (! reload_completed && !LABEL_P (head))
3696     {
3697       rtx insn = prev_nonnote_nondebug_insn (head);
3698
3699       if (insn && CALL_P (insn))
3700         deps->in_post_call_group_p = post_call_initial;
3701     }
3702 }
3703
3704 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3705    dependencies for each insn.  */
3706 void
3707 sched_analyze (struct deps_desc *deps, rtx head, rtx tail)
3708 {
3709   rtx insn;
3710
3711   if (sched_deps_info->use_cselib)
3712     cselib_init (CSELIB_RECORD_MEMORY);
3713
3714   deps_start_bb (deps, head);
3715
3716   for (insn = head;; insn = NEXT_INSN (insn))
3717     {
3718
3719       if (INSN_P (insn))
3720         {
3721           /* And initialize deps_lists.  */
3722           sd_init_insn (insn);
3723         }
3724
3725       deps_analyze_insn (deps, insn);
3726
3727       if (insn == tail)
3728         {
3729           if (sched_deps_info->use_cselib)
3730             cselib_finish ();
3731           return;
3732         }
3733     }
3734   gcc_unreachable ();
3735 }
3736
3737 /* Helper for sched_free_deps ().
3738    Delete INSN's (RESOLVED_P) backward dependencies.  */
3739 static void
3740 delete_dep_nodes_in_back_deps (rtx insn, bool resolved_p)
3741 {
3742   sd_iterator_def sd_it;
3743   dep_t dep;
3744   sd_list_types_def types;
3745
3746   if (resolved_p)
3747     types = SD_LIST_RES_BACK;
3748   else
3749     types = SD_LIST_BACK;
3750
3751   for (sd_it = sd_iterator_start (insn, types);
3752        sd_iterator_cond (&sd_it, &dep);)
3753     {
3754       dep_link_t link = *sd_it.linkp;
3755       dep_node_t node = DEP_LINK_NODE (link);
3756       deps_list_t back_list;
3757       deps_list_t forw_list;
3758
3759       get_back_and_forw_lists (dep, resolved_p, &back_list, &forw_list);
3760       remove_from_deps_list (link, back_list);
3761       delete_dep_node (node);
3762     }
3763 }
3764
3765 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3766    deps_lists.  */
3767 void
3768 sched_free_deps (rtx head, rtx tail, bool resolved_p)
3769 {
3770   rtx insn;
3771   rtx next_tail = NEXT_INSN (tail);
3772
3773   /* We make two passes since some insns may be scheduled before their
3774      dependencies are resolved.  */
3775   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3776     if (INSN_P (insn) && INSN_LUID (insn) > 0)
3777       {
3778         /* Clear forward deps and leave the dep_nodes to the
3779            corresponding back_deps list.  */
3780         if (resolved_p)
3781           clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
3782         else
3783           clear_deps_list (INSN_FORW_DEPS (insn));
3784       }
3785   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3786     if (INSN_P (insn) && INSN_LUID (insn) > 0)
3787       {
3788         /* Clear resolved back deps together with its dep_nodes.  */
3789         delete_dep_nodes_in_back_deps (insn, resolved_p);
3790
3791         sd_finish_insn (insn);
3792       }
3793 }
3794 \f
3795 /* Initialize variables for region data dependence analysis.
3796    When LAZY_REG_LAST is true, do not allocate reg_last array
3797    of struct deps_desc immediately.  */
3798
3799 void
3800 init_deps (struct deps_desc *deps, bool lazy_reg_last)
3801 {
3802   int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
3803
3804   deps->max_reg = max_reg;
3805   if (lazy_reg_last)
3806     deps->reg_last = NULL;
3807   else
3808     deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
3809   INIT_REG_SET (&deps->reg_last_in_use);
3810
3811   deps->pending_read_insns = 0;
3812   deps->pending_read_mems = 0;
3813   deps->pending_write_insns = 0;
3814   deps->pending_write_mems = 0;
3815   deps->pending_jump_insns = 0;
3816   deps->pending_read_list_length = 0;
3817   deps->pending_write_list_length = 0;
3818   deps->pending_flush_length = 0;
3819   deps->last_pending_memory_flush = 0;
3820   deps->last_function_call = 0;
3821   deps->last_function_call_may_noreturn = 0;
3822   deps->sched_before_next_call = 0;
3823   deps->sched_before_next_jump = 0;
3824   deps->in_post_call_group_p = not_post_call;
3825   deps->last_debug_insn = 0;
3826   deps->last_reg_pending_barrier = NOT_A_BARRIER;
3827   deps->readonly = 0;
3828 }
3829
3830 /* Init only reg_last field of DEPS, which was not allocated before as
3831    we inited DEPS lazily.  */
3832 void
3833 init_deps_reg_last (struct deps_desc *deps)
3834 {
3835   gcc_assert (deps && deps->max_reg > 0);
3836   gcc_assert (deps->reg_last == NULL);
3837
3838   deps->reg_last = XCNEWVEC (struct deps_reg, deps->max_reg);
3839 }
3840
3841
3842 /* Free insn lists found in DEPS.  */
3843
3844 void
3845 free_deps (struct deps_desc *deps)
3846 {
3847   unsigned i;
3848   reg_set_iterator rsi;
3849
3850   /* We set max_reg to 0 when this context was already freed.  */
3851   if (deps->max_reg == 0)
3852     {
3853       gcc_assert (deps->reg_last == NULL);
3854       return;
3855     }
3856   deps->max_reg = 0;
3857
3858   free_INSN_LIST_list (&deps->pending_read_insns);
3859   free_EXPR_LIST_list (&deps->pending_read_mems);
3860   free_INSN_LIST_list (&deps->pending_write_insns);
3861   free_EXPR_LIST_list (&deps->pending_write_mems);
3862   free_INSN_LIST_list (&deps->last_pending_memory_flush);
3863
3864   /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3865      times.  For a testcase with 42000 regs and 8000 small basic blocks,
3866      this loop accounted for nearly 60% (84 sec) of the total -O2 runtime.  */
3867   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3868     {
3869       struct deps_reg *reg_last = &deps->reg_last[i];
3870       if (reg_last->uses)
3871         free_INSN_LIST_list (&reg_last->uses);
3872       if (reg_last->sets)
3873         free_INSN_LIST_list (&reg_last->sets);
3874       if (reg_last->implicit_sets)
3875         free_INSN_LIST_list (&reg_last->implicit_sets);
3876       if (reg_last->control_uses)
3877         free_INSN_LIST_list (&reg_last->control_uses);
3878       if (reg_last->clobbers)
3879         free_INSN_LIST_list (&reg_last->clobbers);
3880     }
3881   CLEAR_REG_SET (&deps->reg_last_in_use);
3882
3883   /* As we initialize reg_last lazily, it is possible that we didn't allocate
3884      it at all.  */
3885   free (deps->reg_last);
3886   deps->reg_last = NULL;
3887
3888   deps = NULL;
3889 }
3890
3891 /* Remove INSN from dependence contexts DEPS.  */
3892 void
3893 remove_from_deps (struct deps_desc *deps, rtx insn)
3894 {
3895   int removed;
3896   unsigned i;
3897   reg_set_iterator rsi;
3898
3899   removed = remove_from_both_dependence_lists (insn, &deps->pending_read_insns,
3900                                                &deps->pending_read_mems);
3901   if (!DEBUG_INSN_P (insn))
3902     deps->pending_read_list_length -= removed;
3903   removed = remove_from_both_dependence_lists (insn, &deps->pending_write_insns,
3904                                                &deps->pending_write_mems);
3905   deps->pending_write_list_length -= removed;
3906
3907   removed = remove_from_dependence_list (insn, &deps->pending_jump_insns);
3908   deps->pending_flush_length -= removed;
3909   removed = remove_from_dependence_list (insn, &deps->last_pending_memory_flush);
3910   deps->pending_flush_length -= removed;
3911
3912   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3913     {
3914       struct deps_reg *reg_last = &deps->reg_last[i];
3915       if (reg_last->uses)
3916         remove_from_dependence_list (insn, &reg_last->uses);
3917       if (reg_last->sets)
3918         remove_from_dependence_list (insn, &reg_last->sets);
3919       if (reg_last->implicit_sets)
3920         remove_from_dependence_list (insn, &reg_last->implicit_sets);
3921       if (reg_last->clobbers)
3922         remove_from_dependence_list (insn, &reg_last->clobbers);
3923       if (!reg_last->uses && !reg_last->sets && !reg_last->implicit_sets
3924           && !reg_last->clobbers)
3925         CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, i);
3926     }
3927
3928   if (CALL_P (insn))
3929     {
3930       remove_from_dependence_list (insn, &deps->last_function_call);
3931       remove_from_dependence_list (insn,
3932                                    &deps->last_function_call_may_noreturn);
3933     }
3934   remove_from_dependence_list (insn, &deps->sched_before_next_call);
3935 }
3936
3937 /* Init deps data vector.  */
3938 static void
3939 init_deps_data_vector (void)
3940 {
3941   int reserve = (sched_max_luid + 1
3942                  - VEC_length (haifa_deps_insn_data_def, h_d_i_d));
3943   if (reserve > 0
3944       && ! VEC_space (haifa_deps_insn_data_def, h_d_i_d, reserve))
3945     VEC_safe_grow_cleared (haifa_deps_insn_data_def, heap, h_d_i_d,
3946                            3 * sched_max_luid / 2);
3947 }
3948
3949 /* If it is profitable to use them, initialize or extend (depending on
3950    GLOBAL_P) dependency data.  */
3951 void
3952 sched_deps_init (bool global_p)
3953 {
3954   /* Average number of insns in the basic block.
3955      '+ 1' is used to make it nonzero.  */
3956   int insns_in_block = sched_max_luid / n_basic_blocks + 1;
3957
3958   init_deps_data_vector ();
3959
3960   /* We use another caching mechanism for selective scheduling, so
3961      we don't use this one.  */
3962   if (!sel_sched_p () && global_p && insns_in_block > 100 * 5)
3963     {
3964       /* ?!? We could save some memory by computing a per-region luid mapping
3965          which could reduce both the number of vectors in the cache and the
3966          size of each vector.  Instead we just avoid the cache entirely unless
3967          the average number of instructions in a basic block is very high.  See
3968          the comment before the declaration of true_dependency_cache for
3969          what we consider "very high".  */
3970       cache_size = 0;
3971       extend_dependency_caches (sched_max_luid, true);
3972     }
3973
3974   if (global_p)
3975     {
3976       dl_pool = create_alloc_pool ("deps_list", sizeof (struct _deps_list),
3977                                    /* Allocate lists for one block at a time.  */
3978                                    insns_in_block);
3979       dn_pool = create_alloc_pool ("dep_node", sizeof (struct _dep_node),
3980                                    /* Allocate nodes for one block at a time.
3981                                       We assume that average insn has
3982                                       5 producers.  */
3983                                    5 * insns_in_block);
3984     }
3985 }
3986
3987
3988 /* Create or extend (depending on CREATE_P) dependency caches to
3989    size N.  */
3990 void
3991 extend_dependency_caches (int n, bool create_p)
3992 {
3993   if (create_p || true_dependency_cache)
3994     {
3995       int i, luid = cache_size + n;
3996
3997       true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
3998                                           luid);
3999       output_dependency_cache = XRESIZEVEC (bitmap_head,
4000                                             output_dependency_cache, luid);
4001       anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
4002                                           luid);
4003       control_dependency_cache = XRESIZEVEC (bitmap_head, control_dependency_cache,
4004                                           luid);
4005
4006       if (current_sched_info->flags & DO_SPECULATION)
4007         spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
4008                                             luid);
4009
4010       for (i = cache_size; i < luid; i++)
4011         {
4012           bitmap_initialize (&true_dependency_cache[i], 0);
4013           bitmap_initialize (&output_dependency_cache[i], 0);
4014           bitmap_initialize (&anti_dependency_cache[i], 0);
4015           bitmap_initialize (&control_dependency_cache[i], 0);
4016
4017           if (current_sched_info->flags & DO_SPECULATION)
4018             bitmap_initialize (&spec_dependency_cache[i], 0);
4019         }
4020       cache_size = luid;
4021     }
4022 }
4023
4024 /* Finalize dependency information for the whole function.  */
4025 void
4026 sched_deps_finish (void)
4027 {
4028   gcc_assert (deps_pools_are_empty_p ());
4029   free_alloc_pool_if_empty (&dn_pool);
4030   free_alloc_pool_if_empty (&dl_pool);
4031   gcc_assert (dn_pool == NULL && dl_pool == NULL);
4032
4033   VEC_free (haifa_deps_insn_data_def, heap, h_d_i_d);
4034   cache_size = 0;
4035
4036   if (true_dependency_cache)
4037     {
4038       int i;
4039
4040       for (i = 0; i < cache_size; i++)
4041         {
4042           bitmap_clear (&true_dependency_cache[i]);
4043           bitmap_clear (&output_dependency_cache[i]);
4044           bitmap_clear (&anti_dependency_cache[i]);
4045           bitmap_clear (&control_dependency_cache[i]);
4046
4047           if (sched_deps_info->generate_spec_deps)
4048             bitmap_clear (&spec_dependency_cache[i]);
4049         }
4050       free (true_dependency_cache);
4051       true_dependency_cache = NULL;
4052       free (output_dependency_cache);
4053       output_dependency_cache = NULL;
4054       free (anti_dependency_cache);
4055       anti_dependency_cache = NULL;
4056       free (control_dependency_cache);
4057       control_dependency_cache = NULL;
4058
4059       if (sched_deps_info->generate_spec_deps)
4060         {
4061           free (spec_dependency_cache);
4062           spec_dependency_cache = NULL;
4063         }
4064
4065     }
4066 }
4067
4068 /* Initialize some global variables needed by the dependency analysis
4069    code.  */
4070
4071 void
4072 init_deps_global (void)
4073 {
4074   CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
4075   CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
4076   reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
4077   reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
4078   reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
4079   reg_pending_control_uses = ALLOC_REG_SET (&reg_obstack);
4080   reg_pending_barrier = NOT_A_BARRIER;
4081
4082   if (!sel_sched_p () || sched_emulate_haifa_p)
4083     {
4084       sched_deps_info->start_insn = haifa_start_insn;
4085       sched_deps_info->finish_insn = haifa_finish_insn;
4086
4087       sched_deps_info->note_reg_set = haifa_note_reg_set;
4088       sched_deps_info->note_reg_clobber = haifa_note_reg_clobber;
4089       sched_deps_info->note_reg_use = haifa_note_reg_use;
4090
4091       sched_deps_info->note_mem_dep = haifa_note_mem_dep;
4092       sched_deps_info->note_dep = haifa_note_dep;
4093    }
4094 }
4095
4096 /* Free everything used by the dependency analysis code.  */
4097
4098 void
4099 finish_deps_global (void)
4100 {
4101   FREE_REG_SET (reg_pending_sets);
4102   FREE_REG_SET (reg_pending_clobbers);
4103   FREE_REG_SET (reg_pending_uses);
4104   FREE_REG_SET (reg_pending_control_uses);
4105 }
4106
4107 /* Estimate the weakness of dependence between MEM1 and MEM2.  */
4108 dw_t
4109 estimate_dep_weak (rtx mem1, rtx mem2)
4110 {
4111   rtx r1, r2;
4112
4113   if (mem1 == mem2)
4114     /* MEMs are the same - don't speculate.  */
4115     return MIN_DEP_WEAK;
4116
4117   r1 = XEXP (mem1, 0);
4118   r2 = XEXP (mem2, 0);
4119
4120   if (r1 == r2
4121       || (REG_P (r1) && REG_P (r2)
4122           && REGNO (r1) == REGNO (r2)))
4123     /* Again, MEMs are the same.  */
4124     return MIN_DEP_WEAK;
4125   else if ((REG_P (r1) && !REG_P (r2))
4126            || (!REG_P (r1) && REG_P (r2)))
4127     /* Different addressing modes - reason to be more speculative,
4128        than usual.  */
4129     return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
4130   else
4131     /* We can't say anything about the dependence.  */
4132     return UNCERTAIN_DEP_WEAK;
4133 }
4134
4135 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
4136    This function can handle same INSN and ELEM (INSN == ELEM).
4137    It is a convenience wrapper.  */
4138 static void
4139 add_dependence_1 (rtx insn, rtx elem, enum reg_note dep_type)
4140 {
4141   ds_t ds;
4142   bool internal;
4143
4144   if (dep_type == REG_DEP_TRUE)
4145     ds = DEP_TRUE;
4146   else if (dep_type == REG_DEP_OUTPUT)
4147     ds = DEP_OUTPUT;
4148   else if (dep_type == REG_DEP_CONTROL)
4149     ds = DEP_CONTROL;
4150   else
4151     {
4152       gcc_assert (dep_type == REG_DEP_ANTI);
4153       ds = DEP_ANTI;
4154     }
4155
4156   /* When add_dependence is called from inside sched-deps.c, we expect
4157      cur_insn to be non-null.  */
4158   internal = cur_insn != NULL;
4159   if (internal)
4160     gcc_assert (insn == cur_insn);
4161   else
4162     cur_insn = insn;
4163
4164   note_dep (elem, ds);
4165   if (!internal)
4166     cur_insn = NULL;
4167 }
4168
4169 /* Return weakness of speculative type TYPE in the dep_status DS.  */
4170 dw_t
4171 get_dep_weak_1 (ds_t ds, ds_t type)
4172 {
4173   ds = ds & type;
4174
4175   switch (type)
4176     {
4177     case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
4178     case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
4179     case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
4180     case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
4181     default: gcc_unreachable ();
4182     }
4183
4184   return (dw_t) ds;
4185 }
4186
4187 dw_t
4188 get_dep_weak (ds_t ds, ds_t type)
4189 {
4190   dw_t dw = get_dep_weak_1 (ds, type);
4191
4192   gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4193   return dw;
4194 }
4195
4196 /* Return the dep_status, which has the same parameters as DS, except for
4197    speculative type TYPE, that will have weakness DW.  */
4198 ds_t
4199 set_dep_weak (ds_t ds, ds_t type, dw_t dw)
4200 {
4201   gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4202
4203   ds &= ~type;
4204   switch (type)
4205     {
4206     case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
4207     case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
4208     case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
4209     case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
4210     default: gcc_unreachable ();
4211     }
4212   return ds;
4213 }
4214
4215 /* Return the join of two dep_statuses DS1 and DS2.
4216    If MAX_P is true then choose the greater probability,
4217    otherwise multiply probabilities.
4218    This function assumes that both DS1 and DS2 contain speculative bits.  */
4219 static ds_t
4220 ds_merge_1 (ds_t ds1, ds_t ds2, bool max_p)
4221 {
4222   ds_t ds, t;
4223
4224   gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
4225
4226   ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
4227
4228   t = FIRST_SPEC_TYPE;
4229   do
4230     {
4231       if ((ds1 & t) && !(ds2 & t))
4232         ds |= ds1 & t;
4233       else if (!(ds1 & t) && (ds2 & t))
4234         ds |= ds2 & t;
4235       else if ((ds1 & t) && (ds2 & t))
4236         {
4237           dw_t dw1 = get_dep_weak (ds1, t);
4238           dw_t dw2 = get_dep_weak (ds2, t);
4239           ds_t dw;
4240
4241           if (!max_p)
4242             {
4243               dw = ((ds_t) dw1) * ((ds_t) dw2);
4244               dw /= MAX_DEP_WEAK;
4245               if (dw < MIN_DEP_WEAK)
4246                 dw = MIN_DEP_WEAK;
4247             }
4248           else
4249             {
4250               if (dw1 >= dw2)
4251                 dw = dw1;
4252               else
4253                 dw = dw2;
4254             }
4255
4256           ds = set_dep_weak (ds, t, (dw_t) dw);
4257         }
4258
4259       if (t == LAST_SPEC_TYPE)
4260         break;
4261       t <<= SPEC_TYPE_SHIFT;
4262     }
4263   while (1);
4264
4265   return ds;
4266 }
4267
4268 /* Return the join of two dep_statuses DS1 and DS2.
4269    This function assumes that both DS1 and DS2 contain speculative bits.  */
4270 ds_t
4271 ds_merge (ds_t ds1, ds_t ds2)
4272 {
4273   return ds_merge_1 (ds1, ds2, false);
4274 }
4275
4276 /* Return the join of two dep_statuses DS1 and DS2.  */
4277 ds_t
4278 ds_full_merge (ds_t ds, ds_t ds2, rtx mem1, rtx mem2)
4279 {
4280   ds_t new_status = ds | ds2;
4281
4282   if (new_status & SPECULATIVE)
4283     {
4284       if ((ds && !(ds & SPECULATIVE))
4285           || (ds2 && !(ds2 & SPECULATIVE)))
4286         /* Then this dep can't be speculative.  */
4287         new_status &= ~SPECULATIVE;
4288       else
4289         {
4290           /* Both are speculative.  Merging probabilities.  */
4291           if (mem1)
4292             {
4293               dw_t dw;
4294
4295               dw = estimate_dep_weak (mem1, mem2);
4296               ds = set_dep_weak (ds, BEGIN_DATA, dw);
4297             }
4298
4299           if (!ds)
4300             new_status = ds2;
4301           else if (!ds2)
4302             new_status = ds;
4303           else
4304             new_status = ds_merge (ds2, ds);
4305         }
4306     }
4307
4308   return new_status;
4309 }
4310
4311 /* Return the join of DS1 and DS2.  Use maximum instead of multiplying
4312    probabilities.  */
4313 ds_t
4314 ds_max_merge (ds_t ds1, ds_t ds2)
4315 {
4316   if (ds1 == 0 && ds2 == 0)
4317     return 0;
4318
4319   if (ds1 == 0 && ds2 != 0)
4320     return ds2;
4321
4322   if (ds1 != 0 && ds2 == 0)
4323     return ds1;
4324
4325   return ds_merge_1 (ds1, ds2, true);
4326 }
4327
4328 /* Return the probability of speculation success for the speculation
4329    status DS.  */
4330 dw_t
4331 ds_weak (ds_t ds)
4332 {
4333   ds_t res = 1, dt;
4334   int n = 0;
4335
4336   dt = FIRST_SPEC_TYPE;
4337   do
4338     {
4339       if (ds & dt)
4340         {
4341           res *= (ds_t) get_dep_weak (ds, dt);
4342           n++;
4343         }
4344
4345       if (dt == LAST_SPEC_TYPE)
4346         break;
4347       dt <<= SPEC_TYPE_SHIFT;
4348     }
4349   while (1);
4350
4351   gcc_assert (n);
4352   while (--n)
4353     res /= MAX_DEP_WEAK;
4354
4355   if (res < MIN_DEP_WEAK)
4356     res = MIN_DEP_WEAK;
4357
4358   gcc_assert (res <= MAX_DEP_WEAK);
4359
4360   return (dw_t) res;
4361 }
4362
4363 /* Return a dep status that contains all speculation types of DS.  */
4364 ds_t
4365 ds_get_speculation_types (ds_t ds)
4366 {
4367   if (ds & BEGIN_DATA)
4368     ds |= BEGIN_DATA;
4369   if (ds & BE_IN_DATA)
4370     ds |= BE_IN_DATA;
4371   if (ds & BEGIN_CONTROL)
4372     ds |= BEGIN_CONTROL;
4373   if (ds & BE_IN_CONTROL)
4374     ds |= BE_IN_CONTROL;
4375
4376   return ds & SPECULATIVE;
4377 }
4378
4379 /* Return a dep status that contains maximal weakness for each speculation
4380    type present in DS.  */
4381 ds_t
4382 ds_get_max_dep_weak (ds_t ds)
4383 {
4384   if (ds & BEGIN_DATA)
4385     ds = set_dep_weak (ds, BEGIN_DATA, MAX_DEP_WEAK);
4386   if (ds & BE_IN_DATA)
4387     ds = set_dep_weak (ds, BE_IN_DATA, MAX_DEP_WEAK);
4388   if (ds & BEGIN_CONTROL)
4389     ds = set_dep_weak (ds, BEGIN_CONTROL, MAX_DEP_WEAK);
4390   if (ds & BE_IN_CONTROL)
4391     ds = set_dep_weak (ds, BE_IN_CONTROL, MAX_DEP_WEAK);
4392
4393   return ds;
4394 }
4395
4396 /* Dump information about the dependence status S.  */
4397 static void
4398 dump_ds (FILE *f, ds_t s)
4399 {
4400   fprintf (f, "{");
4401
4402   if (s & BEGIN_DATA)
4403     fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak_1 (s, BEGIN_DATA));
4404   if (s & BE_IN_DATA)
4405     fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak_1 (s, BE_IN_DATA));
4406   if (s & BEGIN_CONTROL)
4407     fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s, BEGIN_CONTROL));
4408   if (s & BE_IN_CONTROL)
4409     fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s, BE_IN_CONTROL));
4410
4411   if (s & HARD_DEP)
4412     fprintf (f, "HARD_DEP; ");
4413
4414   if (s & DEP_TRUE)
4415     fprintf (f, "DEP_TRUE; ");
4416   if (s & DEP_OUTPUT)
4417     fprintf (f, "DEP_OUTPUT; ");
4418   if (s & DEP_ANTI)
4419     fprintf (f, "DEP_ANTI; ");
4420   if (s & DEP_CONTROL)
4421     fprintf (f, "DEP_CONTROL; ");
4422
4423   fprintf (f, "}");
4424 }
4425
4426 DEBUG_FUNCTION void
4427 debug_ds (ds_t s)
4428 {
4429   dump_ds (stderr, s);
4430   fprintf (stderr, "\n");
4431 }
4432
4433 #ifdef ENABLE_CHECKING
4434 /* Verify that dependence type and status are consistent.
4435    If RELAXED_P is true, then skip dep_weakness checks.  */
4436 static void
4437 check_dep (dep_t dep, bool relaxed_p)
4438 {
4439   enum reg_note dt = DEP_TYPE (dep);
4440   ds_t ds = DEP_STATUS (dep);
4441
4442   gcc_assert (DEP_PRO (dep) != DEP_CON (dep));
4443
4444   if (!(current_sched_info->flags & USE_DEPS_LIST))
4445     {
4446       gcc_assert (ds == 0);
4447       return;
4448     }
4449
4450   /* Check that dependence type contains the same bits as the status.  */
4451   if (dt == REG_DEP_TRUE)
4452     gcc_assert (ds & DEP_TRUE);
4453   else if (dt == REG_DEP_OUTPUT)
4454     gcc_assert ((ds & DEP_OUTPUT)
4455                 && !(ds & DEP_TRUE));
4456   else if (dt == REG_DEP_ANTI)
4457     gcc_assert ((ds & DEP_ANTI)
4458                 && !(ds & (DEP_OUTPUT | DEP_TRUE)));
4459   else
4460     gcc_assert (dt == REG_DEP_CONTROL
4461                 && (ds & DEP_CONTROL)
4462                 && !(ds & (DEP_OUTPUT | DEP_ANTI | DEP_TRUE)));
4463
4464   /* HARD_DEP can not appear in dep_status of a link.  */
4465   gcc_assert (!(ds & HARD_DEP));
4466
4467   /* Check that dependence status is set correctly when speculation is not
4468      supported.  */
4469   if (!sched_deps_info->generate_spec_deps)
4470     gcc_assert (!(ds & SPECULATIVE));
4471   else if (ds & SPECULATIVE)
4472     {
4473       if (!relaxed_p)
4474         {
4475           ds_t type = FIRST_SPEC_TYPE;
4476
4477           /* Check that dependence weakness is in proper range.  */
4478           do
4479             {
4480               if (ds & type)
4481                 get_dep_weak (ds, type);
4482
4483               if (type == LAST_SPEC_TYPE)
4484                 break;
4485               type <<= SPEC_TYPE_SHIFT;
4486             }
4487           while (1);
4488         }
4489
4490       if (ds & BEGIN_SPEC)
4491         {
4492           /* Only true dependence can be data speculative.  */
4493           if (ds & BEGIN_DATA)
4494             gcc_assert (ds & DEP_TRUE);
4495
4496           /* Control dependencies in the insn scheduler are represented by
4497              anti-dependencies, therefore only anti dependence can be
4498              control speculative.  */
4499           if (ds & BEGIN_CONTROL)
4500             gcc_assert (ds & DEP_ANTI);
4501         }
4502       else
4503         {
4504           /* Subsequent speculations should resolve true dependencies.  */
4505           gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
4506         }
4507
4508       /* Check that true and anti dependencies can't have other speculative
4509          statuses.  */
4510       if (ds & DEP_TRUE)
4511         gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
4512       /* An output dependence can't be speculative at all.  */
4513       gcc_assert (!(ds & DEP_OUTPUT));
4514       if (ds & DEP_ANTI)
4515         gcc_assert (ds & BEGIN_CONTROL);
4516     }
4517 }
4518 #endif /* ENABLE_CHECKING */
4519
4520 /* The following code discovers opportunities to switch a memory reference
4521    and an increment by modifying the address.  We ensure that this is done
4522    only for dependencies that are only used to show a single register
4523    dependence (using DEP_NONREG and DEP_MULTIPLE), and so that every memory
4524    instruction involved is subject to only one dep that can cause a pattern
4525    change.
4526
4527    When we discover a suitable dependency, we fill in the dep_replacement
4528    structure to show how to modify the memory reference.  */
4529
4530 /* Holds information about a pair of memory reference and register increment
4531    insns which depend on each other, but could possibly be interchanged.  */
4532 struct mem_inc_info
4533 {
4534   rtx inc_insn;
4535   rtx mem_insn;
4536
4537   rtx *mem_loc;
4538   /* A register occurring in the memory address for which we wish to break
4539      the dependence.  This must be identical to the destination register of
4540      the increment.  */
4541   rtx mem_reg0;
4542   /* Any kind of index that is added to that register.  */
4543   rtx mem_index;
4544   /* The constant offset used in the memory address.  */
4545   HOST_WIDE_INT mem_constant;
4546   /* The constant added in the increment insn.  Negated if the increment is
4547      after the memory address.  */
4548   HOST_WIDE_INT inc_constant;
4549   /* The source register used in the increment.  May be different from mem_reg0
4550      if the increment occurs before the memory address.  */
4551   rtx inc_input;
4552 };
4553
4554 /* Verify that the memory location described in MII can be replaced with
4555    one using NEW_ADDR.  Return the new memory reference or NULL_RTX.  The
4556    insn remains unchanged by this function.  */
4557
4558 static rtx
4559 attempt_change (struct mem_inc_info *mii, rtx new_addr)
4560 {
4561   rtx mem = *mii->mem_loc;
4562   rtx new_mem;
4563
4564   /* Jump thru a lot of hoops to keep the attributes up to date.  We
4565      do not want to call one of the change address variants that take
4566      an offset even though we know the offset in many cases.  These
4567      assume you are changing where the address is pointing by the
4568      offset.  */
4569   new_mem = replace_equiv_address_nv (mem, new_addr);
4570   if (! validate_change (mii->mem_insn, mii->mem_loc, new_mem, 0))
4571     {
4572       if (sched_verbose >= 5)
4573         fprintf (sched_dump, "validation failure\n");
4574       return NULL_RTX;
4575     }
4576
4577   /* Put back the old one.  */
4578   validate_change (mii->mem_insn, mii->mem_loc, mem, 0);
4579
4580   return new_mem;
4581 }
4582
4583 /* Return true if INSN is of a form "a = b op c" where a and b are
4584    regs.  op is + if c is a reg and +|- if c is a const.  Fill in
4585    informantion in MII about what is found.
4586    BEFORE_MEM indicates whether the increment is found before or after
4587    a corresponding memory reference.  */
4588
4589 static bool
4590 parse_add_or_inc (struct mem_inc_info *mii, rtx insn, bool before_mem)
4591 {
4592   rtx pat = single_set (insn);
4593   rtx src, cst;
4594   bool regs_equal;
4595
4596   if (RTX_FRAME_RELATED_P (insn) || !pat)
4597     return false;
4598
4599   /* Result must be single reg.  */
4600   if (!REG_P (SET_DEST (pat)))
4601     return false;
4602
4603   if (GET_CODE (SET_SRC (pat)) != PLUS)
4604     return false;
4605
4606   mii->inc_insn = insn;
4607   src = SET_SRC (pat);
4608   mii->inc_input = XEXP (src, 0);
4609
4610   if (!REG_P (XEXP (src, 0)))
4611     return false;
4612
4613   if (!rtx_equal_p (SET_DEST (pat), mii->mem_reg0))
4614     return false;
4615
4616   cst = XEXP (src, 1);
4617   if (!CONST_INT_P (cst))
4618     return false;
4619   mii->inc_constant = INTVAL (cst);
4620
4621   regs_equal = rtx_equal_p (mii->inc_input, mii->mem_reg0);
4622
4623   if (!before_mem)
4624     {
4625       mii->inc_constant = -mii->inc_constant;
4626       if (!regs_equal)
4627         return false;
4628     }
4629
4630   if (regs_equal && REGNO (SET_DEST (pat)) == STACK_POINTER_REGNUM)
4631     {
4632       /* Note that the sign has already been reversed for !before_mem.  */
4633 #ifdef STACK_GROWS_DOWNWARD
4634       return mii->inc_constant > 0;
4635 #else
4636       return mii->inc_constant < 0;
4637 #endif
4638     }
4639   return true;
4640 }
4641
4642 /* Once a suitable mem reference has been found and the corresponding data
4643    in MII has been filled in, this function is called to find a suitable
4644    add or inc insn involving the register we found in the memory
4645    reference.  */
4646
4647 static bool
4648 find_inc (struct mem_inc_info *mii, bool backwards)
4649 {
4650   sd_iterator_def sd_it;
4651   dep_t dep;
4652
4653   sd_it = sd_iterator_start (mii->mem_insn,
4654                              backwards ? SD_LIST_HARD_BACK : SD_LIST_FORW);
4655   while (sd_iterator_cond (&sd_it, &dep))
4656     {
4657       dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
4658       rtx pro = DEP_PRO (dep);
4659       rtx con = DEP_CON (dep);
4660       rtx inc_cand = backwards ? pro : con;
4661       if (DEP_NONREG (dep) || DEP_MULTIPLE (dep))
4662         goto next;
4663       if (parse_add_or_inc (mii, inc_cand, backwards))
4664         {
4665           struct dep_replacement *desc;
4666           df_ref *def_rec;
4667           rtx newaddr, newmem;
4668
4669           if (sched_verbose >= 5)
4670             fprintf (sched_dump, "candidate mem/inc pair: %d %d\n",
4671                      INSN_UID (mii->mem_insn), INSN_UID (inc_cand));
4672
4673           /* Need to assure that none of the operands of the inc
4674              instruction are assigned to by the mem insn.  */
4675           for (def_rec = DF_INSN_DEFS (mii->mem_insn); *def_rec; def_rec++)
4676             {
4677               df_ref def = *def_rec;
4678               if (reg_overlap_mentioned_p (DF_REF_REG (def), mii->inc_input)
4679                   || reg_overlap_mentioned_p (DF_REF_REG (def), mii->mem_reg0))
4680                 {
4681                   if (sched_verbose >= 5)
4682                     fprintf (sched_dump,
4683                              "inc conflicts with store failure.\n");
4684                   goto next;
4685                 }
4686             }
4687           newaddr = mii->inc_input;
4688           if (mii->mem_index != NULL_RTX)
4689             newaddr = gen_rtx_PLUS (GET_MODE (newaddr), newaddr,
4690                                     mii->mem_index);
4691           newaddr = plus_constant (GET_MODE (newaddr), newaddr,
4692                                    mii->mem_constant + mii->inc_constant);
4693           newmem = attempt_change (mii, newaddr);
4694           if (newmem == NULL_RTX)
4695             goto next;
4696           if (sched_verbose >= 5)
4697             fprintf (sched_dump, "successful address replacement\n");
4698           desc = XCNEW (struct dep_replacement);
4699           DEP_REPLACE (dep) = desc;
4700           desc->loc = mii->mem_loc;
4701           desc->newval = newmem;
4702           desc->orig = *desc->loc;
4703           desc->insn = mii->mem_insn;
4704           move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
4705                          INSN_SPEC_BACK_DEPS (con));
4706           if (backwards)
4707             {
4708               FOR_EACH_DEP (mii->inc_insn, SD_LIST_BACK, sd_it, dep)
4709                 if (modified_in_p (mii->inc_input, DEP_PRO (dep)))
4710                   add_dependence_1 (mii->mem_insn, DEP_PRO (dep),
4711                                     REG_DEP_TRUE);
4712             }
4713           else
4714             {
4715               FOR_EACH_DEP (mii->inc_insn, SD_LIST_FORW, sd_it, dep)
4716                 if (modified_in_p (mii->inc_input, DEP_CON (dep)))
4717                   add_dependence_1 (DEP_CON (dep), mii->mem_insn,
4718                                     REG_DEP_ANTI);
4719             }
4720           return true;
4721         }
4722     next:
4723       sd_iterator_next (&sd_it);
4724     }
4725   return false;
4726 }
4727
4728 /* A recursive function that walks ADDRESS_OF_X to find memory references
4729    which could be modified during scheduling.  We call find_inc for each
4730    one we find that has a recognizable form.  MII holds information about
4731    the pair of memory/increment instructions.
4732    We ensure that every instruction with a memory reference (which will be
4733    the location of the replacement) is assigned at most one breakable
4734    dependency.  */
4735
4736 static bool
4737 find_mem (struct mem_inc_info *mii, rtx *address_of_x)
4738 {
4739   rtx x = *address_of_x;
4740   enum rtx_code code = GET_CODE (x);
4741   const char *const fmt = GET_RTX_FORMAT (code);
4742   int i;
4743
4744   if (code == MEM)
4745     {
4746       rtx reg0 = XEXP (x, 0);
4747
4748       mii->mem_loc = address_of_x;
4749       mii->mem_index = NULL_RTX;
4750       mii->mem_constant = 0;
4751       if (GET_CODE (reg0) == PLUS && CONST_INT_P (XEXP (reg0, 1)))
4752         {
4753           mii->mem_constant = INTVAL (XEXP (reg0, 1));
4754           reg0 = XEXP (reg0, 0);
4755         }
4756       if (GET_CODE (reg0) == PLUS)
4757         {
4758           mii->mem_index = XEXP (reg0, 1);
4759           reg0 = XEXP (reg0, 0);
4760         }
4761       if (REG_P (reg0))
4762         {
4763           df_ref *def_rec;
4764           int occurrences = 0;
4765
4766           /* Make sure this reg appears only once in this insn.  Can't use
4767              count_occurrences since that only works for pseudos.  */
4768           for (def_rec = DF_INSN_USES (mii->mem_insn); *def_rec; def_rec++)
4769             {
4770               df_ref def = *def_rec;
4771               if (reg_overlap_mentioned_p (reg0, DF_REF_REG (def)))
4772                 if (++occurrences > 1)
4773                   {
4774                     if (sched_verbose >= 5)
4775                       fprintf (sched_dump, "mem count failure\n");
4776                     return false;
4777                   }
4778             }
4779
4780           mii->mem_reg0 = reg0;
4781           return find_inc (mii, true) || find_inc (mii, false);
4782         }
4783       return false;
4784     }
4785
4786   if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
4787     {
4788       /* If REG occurs inside a MEM used in a bit-field reference,
4789          that is unacceptable.  */
4790       return false;
4791     }
4792
4793   /* Time for some deep diving.  */
4794   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4795     {
4796       if (fmt[i] == 'e')
4797         {
4798           if (find_mem (mii, &XEXP (x, i)))
4799             return true;
4800         }
4801       else if (fmt[i] == 'E')
4802         {
4803           int j;
4804           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4805             if (find_mem (mii, &XVECEXP (x, i, j)))
4806               return true;
4807         }
4808     }
4809   return false;
4810 }
4811
4812
4813 /* Examine the instructions between HEAD and TAIL and try to find
4814    dependencies that can be broken by modifying one of the patterns.  */
4815
4816 void
4817 find_modifiable_mems (rtx head, rtx tail)
4818 {
4819   rtx insn, next_tail = NEXT_INSN (tail);
4820   int success_in_block = 0;
4821
4822   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4823     {
4824       struct mem_inc_info mii;
4825
4826       if (!NONDEBUG_INSN_P (insn) || RTX_FRAME_RELATED_P (insn))
4827         continue;
4828
4829       mii.mem_insn = insn;
4830       if (find_mem (&mii, &PATTERN (insn)))
4831         success_in_block++;
4832     }
4833   if (success_in_block && sched_verbose >= 5)
4834     fprintf (sched_dump, "%d candidates for address modification found.\n",
4835              success_in_block);
4836 }
4837
4838 #endif /* INSN_SCHEDULING */