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