gcc/sched-deps.c

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