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