gcc/sched-deps.c

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