gcc/sched-deps.c

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