gcc/sched-deps.c

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