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   /* We must avoid creating a situation in which two successors of the
2700      current block have different unwind info after scheduling.  If at any
2701      point the two paths re-join this leads to incorrect unwind info.  */
2702   /* ??? There are certain situations involving a forced frame pointer in
2703      which, with extra effort, we could fix up the unwind info at a later
2704      CFG join.  However, it seems better to notice these cases earlier
2705      during prologue generation and avoid marking the frame pointer setup
2706      as frame-related at all.  */
2707   if (RTX_FRAME_RELATED_P (insn))
2708     deps->sched_before_next_jump
2709       = alloc_INSN_LIST (insn, deps->sched_before_next_jump);
2710
2711   if (code == COND_EXEC)
2712     {
2713       sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
2714
2715       /* ??? Should be recording conditions so we reduce the number of
2716          false dependencies.  */
2717       x = COND_EXEC_CODE (x);
2718       code = GET_CODE (x);
2719     }
2720   if (code == SET || code == CLOBBER)
2721     {
2722       sched_analyze_1 (deps, x, insn);
2723
2724       /* Bare clobber insns are used for letting life analysis, reg-stack
2725          and others know that a value is dead.  Depend on the last call
2726          instruction so that reg-stack won't get confused.  */
2727       if (code == CLOBBER)
2728         add_dependence_list (insn, deps->last_function_call, 1,
2729                              REG_DEP_OUTPUT);
2730     }
2731   else if (code == PARALLEL)
2732     {
2733       for (i = XVECLEN (x, 0); i--;)
2734         {
2735           rtx sub = XVECEXP (x, 0, i);
2736           code = GET_CODE (sub);
2737
2738           if (code == COND_EXEC)
2739             {
2740               sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
2741               sub = COND_EXEC_CODE (sub);
2742               code = GET_CODE (sub);
2743             }
2744           if (code == SET || code == CLOBBER)
2745             sched_analyze_1 (deps, sub, insn);
2746           else
2747             sched_analyze_2 (deps, sub, insn);
2748         }
2749     }
2750   else
2751     sched_analyze_2 (deps, x, insn);
2752
2753   /* Mark registers CLOBBERED or used by called function.  */
2754   if (CALL_P (insn))
2755     {
2756       for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
2757         {
2758           if (GET_CODE (XEXP (link, 0)) == CLOBBER)
2759             sched_analyze_1 (deps, XEXP (link, 0), insn);
2760           else
2761             sched_analyze_2 (deps, XEXP (link, 0), insn);
2762         }
2763       if (find_reg_note (insn, REG_SETJMP, NULL))
2764         reg_pending_barrier = MOVE_BARRIER;
2765     }
2766
2767   if (JUMP_P (insn))
2768     {
2769       rtx next;
2770       next = next_nonnote_nondebug_insn (insn);
2771       if (next && BARRIER_P (next))
2772         reg_pending_barrier = MOVE_BARRIER;
2773       else
2774         {
2775           rtx pending, pending_mem;
2776
2777           if (sched_deps_info->compute_jump_reg_dependencies)
2778             {
2779               regset_head tmp;
2780               INIT_REG_SET (&tmp);
2781
2782               (*sched_deps_info->compute_jump_reg_dependencies) (insn, &tmp);
2783
2784               /* Make latency of jump equal to 0 by using anti-dependence.  */
2785               EXECUTE_IF_SET_IN_REG_SET (&tmp, 0, i, rsi)
2786                 {
2787                   struct deps_reg *reg_last = &deps->reg_last[i];
2788                   add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
2789                   add_dependence_list (insn, reg_last->implicit_sets,
2790                                        0, REG_DEP_ANTI);
2791                   add_dependence_list (insn, reg_last->clobbers, 0,
2792                                        REG_DEP_ANTI);
2793
2794                   if (!deps->readonly)
2795                     {
2796                       reg_last->uses_length++;
2797                       reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
2798                     }
2799                 }
2800
2801               CLEAR_REG_SET (&tmp);
2802             }
2803
2804           /* All memory writes and volatile reads must happen before the
2805              jump.  Non-volatile reads must happen before the jump iff
2806              the result is needed by the above register used mask.  */
2807
2808           pending = deps->pending_write_insns;
2809           pending_mem = deps->pending_write_mems;
2810           while (pending)
2811             {
2812               if (! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2813                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
2814               pending = XEXP (pending, 1);
2815               pending_mem = XEXP (pending_mem, 1);
2816             }
2817
2818           pending = deps->pending_read_insns;
2819           pending_mem = deps->pending_read_mems;
2820           while (pending)
2821             {
2822               if (MEM_VOLATILE_P (XEXP (pending_mem, 0))
2823                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2824                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
2825               pending = XEXP (pending, 1);
2826               pending_mem = XEXP (pending_mem, 1);
2827             }
2828
2829           add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2830                                REG_DEP_ANTI);
2831         }
2832     }
2833
2834   /* If this instruction can throw an exception, then moving it changes
2835      where block boundaries fall.  This is mighty confusing elsewhere.
2836      Therefore, prevent such an instruction from being moved.  Same for
2837      non-jump instructions that define block boundaries.
2838      ??? Unclear whether this is still necessary in EBB mode.  If not,
2839      add_branch_dependences should be adjusted for RGN mode instead.  */
2840   if (((CALL_P (insn) || JUMP_P (insn)) && can_throw_internal (insn))
2841       || (NONJUMP_INSN_P (insn) && control_flow_insn_p (insn)))
2842     reg_pending_barrier = MOVE_BARRIER;
2843
2844   if (sched_pressure_p)
2845     {
2846       setup_insn_reg_uses (deps, insn);
2847       init_insn_reg_pressure_info (insn);
2848     }
2849
2850   /* Add register dependencies for insn.  */
2851   if (DEBUG_INSN_P (insn))
2852     {
2853       rtx prev = deps->last_debug_insn;
2854       rtx u;
2855
2856       if (!deps->readonly)
2857         deps->last_debug_insn = insn;
2858
2859       if (prev)
2860         add_dependence (insn, prev, REG_DEP_ANTI);
2861
2862       add_dependence_list (insn, deps->last_function_call, 1,
2863                            REG_DEP_ANTI);
2864
2865       for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
2866         if (! NON_FLUSH_JUMP_P (u) || !sel_sched_p ())
2867           add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
2868
2869       EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
2870         {
2871           struct deps_reg *reg_last = &deps->reg_last[i];
2872           add_dependence_list (insn, reg_last->sets, 1, REG_DEP_ANTI);
2873           add_dependence_list (insn, reg_last->clobbers, 1, REG_DEP_ANTI);
2874
2875           if (!deps->readonly)
2876             reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
2877         }
2878       CLEAR_REG_SET (reg_pending_uses);
2879
2880       /* Quite often, a debug insn will refer to stuff in the
2881          previous instruction, but the reason we want this
2882          dependency here is to make sure the scheduler doesn't
2883          gratuitously move a debug insn ahead.  This could dirty
2884          DF flags and cause additional analysis that wouldn't have
2885          occurred in compilation without debug insns, and such
2886          additional analysis can modify the generated code.  */
2887       prev = PREV_INSN (insn);
2888
2889       if (prev && NONDEBUG_INSN_P (prev))
2890         add_dependence (insn, prev, REG_DEP_ANTI);
2891     }
2892   else
2893     {
2894       regset_head set_or_clobbered;
2895
2896       EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
2897         {
2898           struct deps_reg *reg_last = &deps->reg_last[i];
2899           add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
2900           add_dependence_list (insn, reg_last->implicit_sets, 0, REG_DEP_ANTI);
2901           add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
2902
2903           if (!deps->readonly)
2904             {
2905               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
2906               reg_last->uses_length++;
2907             }
2908         }
2909
2910       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2911         if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i))
2912           {
2913             struct deps_reg *reg_last = &deps->reg_last[i];
2914             add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
2915             add_dependence_list (insn, reg_last->implicit_sets, 0,
2916                                  REG_DEP_ANTI);
2917             add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
2918
2919             if (!deps->readonly)
2920               {
2921                 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
2922                 reg_last->uses_length++;
2923               }
2924           }
2925
2926       if (targetm.sched.exposed_pipeline)
2927         {
2928           INIT_REG_SET (&set_or_clobbered);
2929           bitmap_ior (&set_or_clobbered, reg_pending_clobbers,
2930                       reg_pending_sets);
2931           EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered, 0, i, rsi)
2932             {
2933               struct deps_reg *reg_last = &deps->reg_last[i];
2934               rtx list;
2935               for (list = reg_last->uses; list; list = XEXP (list, 1))
2936                 {
2937                   rtx other = XEXP (list, 0);
2938                   if (INSN_CACHED_COND (other) != const_true_rtx
2939                       && refers_to_regno_p (i, i + 1, INSN_CACHED_COND (other), NULL))
2940                     INSN_CACHED_COND (other) = const_true_rtx;
2941                 }
2942             }
2943         }
2944
2945       /* If the current insn is conditional, we can't free any
2946          of the lists.  */
2947       if (sched_has_condition_p (insn))
2948         {
2949           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
2950             {
2951               struct deps_reg *reg_last = &deps->reg_last[i];
2952               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
2953               add_dependence_list (insn, reg_last->implicit_sets, 0,
2954                                    REG_DEP_ANTI);
2955               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
2956
2957               if (!deps->readonly)
2958                 {
2959                   reg_last->clobbers
2960                     = alloc_INSN_LIST (insn, reg_last->clobbers);
2961                   reg_last->clobbers_length++;
2962                 }
2963             }
2964           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
2965             {
2966               struct deps_reg *reg_last = &deps->reg_last[i];
2967               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
2968               add_dependence_list (insn, reg_last->implicit_sets, 0,
2969                                    REG_DEP_ANTI);
2970               add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT);
2971               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
2972
2973               if (!deps->readonly)
2974                 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
2975             }
2976         }
2977       else
2978         {
2979           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
2980             {
2981               struct deps_reg *reg_last = &deps->reg_last[i];
2982               if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
2983                   || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
2984                 {
2985                   add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
2986                                                 REG_DEP_OUTPUT);
2987                   add_dependence_list_and_free (deps, insn,
2988                                                 &reg_last->implicit_sets, 0,
2989                                                 REG_DEP_ANTI);
2990                   add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
2991                                                 REG_DEP_ANTI);
2992                   add_dependence_list_and_free
2993                     (deps, insn, &reg_last->clobbers, 0, REG_DEP_OUTPUT);
2994
2995                   if (!deps->readonly)
2996                     {
2997                       reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
2998                       reg_last->clobbers_length = 0;
2999                       reg_last->uses_length = 0;
3000                     }
3001                 }
3002               else
3003                 {
3004                   add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
3005                   add_dependence_list (insn, reg_last->implicit_sets, 0,
3006                                        REG_DEP_ANTI);
3007                   add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
3008                 }
3009
3010               if (!deps->readonly)
3011                 {
3012                   reg_last->clobbers_length++;
3013                   reg_last->clobbers
3014                     = alloc_INSN_LIST (insn, reg_last->clobbers);
3015                 }
3016             }
3017           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3018             {
3019               struct deps_reg *reg_last = &deps->reg_last[i];
3020
3021               add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3022                                             REG_DEP_OUTPUT);
3023               add_dependence_list_and_free (deps, insn,
3024                                             &reg_last->implicit_sets,
3025                                             0, REG_DEP_ANTI);
3026               add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3027                                             REG_DEP_OUTPUT);
3028               add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3029                                             REG_DEP_ANTI);
3030
3031               if (!deps->readonly)
3032                 {
3033                   reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3034                   reg_last->uses_length = 0;
3035                   reg_last->clobbers_length = 0;
3036                 }
3037             }
3038         }
3039     }
3040
3041   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3042     if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
3043       {
3044         struct deps_reg *reg_last = &deps->reg_last[i];
3045         add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
3046         add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI);
3047         add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
3048
3049         if (!deps->readonly)
3050           reg_last->implicit_sets
3051             = alloc_INSN_LIST (insn, reg_last->implicit_sets);
3052       }
3053
3054   if (!deps->readonly)
3055     {
3056       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
3057       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
3058       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
3059       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3060         if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i)
3061             || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
3062           SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3063
3064       /* Set up the pending barrier found.  */
3065       deps->last_reg_pending_barrier = reg_pending_barrier;
3066     }
3067
3068   CLEAR_REG_SET (reg_pending_uses);
3069   CLEAR_REG_SET (reg_pending_clobbers);
3070   CLEAR_REG_SET (reg_pending_sets);
3071   CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
3072   CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
3073
3074   /* Add dependencies if a scheduling barrier was found.  */
3075   if (reg_pending_barrier)
3076     {
3077       /* In the case of barrier the most added dependencies are not
3078          real, so we use anti-dependence here.  */
3079       if (sched_has_condition_p (insn))
3080         {
3081           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3082             {
3083               struct deps_reg *reg_last = &deps->reg_last[i];
3084               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
3085               add_dependence_list (insn, reg_last->sets, 0,
3086                                    reg_pending_barrier == TRUE_BARRIER
3087                                    ? REG_DEP_TRUE : REG_DEP_ANTI);
3088               add_dependence_list (insn, reg_last->implicit_sets, 0,
3089                                    REG_DEP_ANTI);
3090               add_dependence_list (insn, reg_last->clobbers, 0,
3091                                    reg_pending_barrier == TRUE_BARRIER
3092                                    ? REG_DEP_TRUE : REG_DEP_ANTI);
3093             }
3094         }
3095       else
3096         {
3097           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3098             {
3099               struct deps_reg *reg_last = &deps->reg_last[i];
3100               add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3101                                             REG_DEP_ANTI);
3102               add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3103                                             reg_pending_barrier == TRUE_BARRIER
3104                                             ? REG_DEP_TRUE : REG_DEP_ANTI);
3105               add_dependence_list_and_free (deps, insn,
3106                                             &reg_last->implicit_sets, 0,
3107                                             REG_DEP_ANTI);
3108               add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3109                                             reg_pending_barrier == TRUE_BARRIER
3110                                             ? REG_DEP_TRUE : REG_DEP_ANTI);
3111
3112               if (!deps->readonly)
3113                 {
3114                   reg_last->uses_length = 0;
3115                   reg_last->clobbers_length = 0;
3116                 }
3117             }
3118         }
3119
3120       if (!deps->readonly)
3121         for (i = 0; i < (unsigned)deps->max_reg; i++)
3122           {
3123             struct deps_reg *reg_last = &deps->reg_last[i];
3124             reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3125             SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3126           }
3127
3128       /* Flush pending lists on jumps, but not on speculative checks.  */
3129       if (JUMP_P (insn) && !(sel_sched_p ()
3130                              && sel_insn_is_speculation_check (insn)))
3131         flush_pending_lists (deps, insn, true, true);
3132
3133       reg_pending_barrier = NOT_A_BARRIER;
3134     }
3135
3136   /* If a post-call group is still open, see if it should remain so.
3137      This insn must be a simple move of a hard reg to a pseudo or
3138      vice-versa.
3139
3140      We must avoid moving these insns for correctness on targets
3141      with small register classes, and for special registers like
3142      PIC_OFFSET_TABLE_REGNUM.  For simplicity, extend this to all
3143      hard regs for all targets.  */
3144
3145   if (deps->in_post_call_group_p)
3146     {
3147       rtx tmp, set = single_set (insn);
3148       int src_regno, dest_regno;
3149
3150       if (set == NULL)
3151         {
3152           if (DEBUG_INSN_P (insn))
3153             /* We don't want to mark debug insns as part of the same
3154                sched group.  We know they really aren't, but if we use
3155                debug insns to tell that a call group is over, we'll
3156                get different code if debug insns are not there and
3157                instructions that follow seem like they should be part
3158                of the call group.
3159
3160                Also, if we did, fixup_sched_groups() would move the
3161                deps of the debug insn to the call insn, modifying
3162                non-debug post-dependency counts of the debug insn
3163                dependencies and otherwise messing with the scheduling
3164                order.
3165
3166                Instead, let such debug insns be scheduled freely, but
3167                keep the call group open in case there are insns that
3168                should be part of it afterwards.  Since we grant debug
3169                insns higher priority than even sched group insns, it
3170                will all turn out all right.  */
3171             goto debug_dont_end_call_group;
3172           else
3173             goto end_call_group;
3174         }
3175
3176       tmp = SET_DEST (set);
3177       if (GET_CODE (tmp) == SUBREG)
3178         tmp = SUBREG_REG (tmp);
3179       if (REG_P (tmp))
3180         dest_regno = REGNO (tmp);
3181       else
3182         goto end_call_group;
3183
3184       tmp = SET_SRC (set);
3185       if (GET_CODE (tmp) == SUBREG)
3186         tmp = SUBREG_REG (tmp);
3187       if ((GET_CODE (tmp) == PLUS
3188            || GET_CODE (tmp) == MINUS)
3189           && REG_P (XEXP (tmp, 0))
3190           && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
3191           && dest_regno == STACK_POINTER_REGNUM)
3192         src_regno = STACK_POINTER_REGNUM;
3193       else if (REG_P (tmp))
3194         src_regno = REGNO (tmp);
3195       else
3196         goto end_call_group;
3197
3198       if (src_regno < FIRST_PSEUDO_REGISTER
3199           || dest_regno < FIRST_PSEUDO_REGISTER)
3200         {
3201           if (!deps->readonly
3202               && deps->in_post_call_group_p == post_call_initial)
3203             deps->in_post_call_group_p = post_call;
3204
3205           if (!sel_sched_p () || sched_emulate_haifa_p)
3206             {
3207               SCHED_GROUP_P (insn) = 1;
3208               CANT_MOVE (insn) = 1;
3209             }
3210         }
3211       else
3212         {
3213         end_call_group:
3214           if (!deps->readonly)
3215             deps->in_post_call_group_p = not_post_call;
3216         }
3217     }
3218
3219  debug_dont_end_call_group:
3220   if ((current_sched_info->flags & DO_SPECULATION)
3221       && !sched_insn_is_legitimate_for_speculation_p (insn, 0))
3222     /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3223        be speculated.  */
3224     {
3225       if (sel_sched_p ())
3226         sel_mark_hard_insn (insn);
3227       else
3228         {
3229           sd_iterator_def sd_it;
3230           dep_t dep;
3231
3232           for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3233                sd_iterator_cond (&sd_it, &dep);)
3234             change_spec_dep_to_hard (sd_it);
3235         }
3236     }
3237 }
3238
3239 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3240    longjmp, loop forever, ...).  */
3241 static bool
3242 call_may_noreturn_p (rtx insn)
3243 {
3244   rtx call;
3245
3246   /* const or pure calls that aren't looping will always return.  */
3247   if (RTL_CONST_OR_PURE_CALL_P (insn)
3248       && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))
3249     return false;
3250
3251   call = PATTERN (insn);
3252   if (GET_CODE (call) == PARALLEL)
3253     call = XVECEXP (call, 0, 0);
3254   if (GET_CODE (call) == SET)
3255     call = SET_SRC (call);
3256   if (GET_CODE (call) == CALL
3257       && MEM_P (XEXP (call, 0))
3258       && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
3259     {
3260       rtx symbol = XEXP (XEXP (call, 0), 0);
3261       if (SYMBOL_REF_DECL (symbol)
3262           && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
3263         {
3264           if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
3265               == BUILT_IN_NORMAL)
3266             switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol)))
3267               {
3268               case BUILT_IN_BCMP:
3269               case BUILT_IN_BCOPY:
3270               case BUILT_IN_BZERO:
3271               case BUILT_IN_INDEX:
3272               case BUILT_IN_MEMCHR:
3273               case BUILT_IN_MEMCMP:
3274               case BUILT_IN_MEMCPY:
3275               case BUILT_IN_MEMMOVE:
3276               case BUILT_IN_MEMPCPY:
3277               case BUILT_IN_MEMSET:
3278               case BUILT_IN_RINDEX:
3279               case BUILT_IN_STPCPY:
3280               case BUILT_IN_STPNCPY:
3281               case BUILT_IN_STRCAT:
3282               case BUILT_IN_STRCHR:
3283               case BUILT_IN_STRCMP:
3284               case BUILT_IN_STRCPY:
3285               case BUILT_IN_STRCSPN:
3286               case BUILT_IN_STRLEN:
3287               case BUILT_IN_STRNCAT:
3288               case BUILT_IN_STRNCMP:
3289               case BUILT_IN_STRNCPY:
3290               case BUILT_IN_STRPBRK:
3291               case BUILT_IN_STRRCHR:
3292               case BUILT_IN_STRSPN:
3293               case BUILT_IN_STRSTR:
3294                 /* Assume certain string/memory builtins always return.  */
3295                 return false;
3296               default:
3297                 break;
3298               }
3299         }
3300     }
3301
3302   /* For all other calls assume that they might not always return.  */
3303   return true;
3304 }
3305
3306 /* Analyze INSN with DEPS as a context.  */
3307 void
3308 deps_analyze_insn (struct deps_desc *deps, rtx insn)
3309 {
3310   if (sched_deps_info->start_insn)
3311     sched_deps_info->start_insn (insn);
3312
3313   /* Record the condition for this insn.  */
3314   if (NONDEBUG_INSN_P (insn))
3315     sched_get_condition_with_rev (insn, NULL);
3316
3317   if (JUMP_P (insn))
3318     {
3319       /* Make each JUMP_INSN (but not a speculative check)
3320          a scheduling barrier for memory references.  */
3321       if (!deps->readonly
3322           && !(sel_sched_p ()
3323                && sel_insn_is_speculation_check (insn)))
3324         {
3325           /* Keep the list a reasonable size.  */
3326           if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
3327             flush_pending_lists (deps, insn, true, true);
3328           else
3329             {
3330               deps->last_pending_memory_flush
3331                 = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
3332               /* Signal to sched_analyze_insn that this jump stands
3333                  just for its own, not any other pending memory
3334                  reads/writes flush_pending_lists had to flush.  */
3335               PUT_REG_NOTE_KIND (deps->last_pending_memory_flush,
3336                                  NON_FLUSH_JUMP_KIND);
3337             }
3338         }
3339
3340       /* For each insn which shouldn't cross a jump, add a dependence.  */
3341       add_dependence_list_and_free (deps, insn,
3342                                     &deps->sched_before_next_jump, 1,
3343                                     REG_DEP_ANTI);
3344
3345       sched_analyze_insn (deps, PATTERN (insn), insn);
3346     }
3347   else if (NONJUMP_INSN_P (insn) || DEBUG_INSN_P (insn))
3348     {
3349       sched_analyze_insn (deps, PATTERN (insn), insn);
3350     }
3351   else if (CALL_P (insn))
3352     {
3353       int i;
3354
3355       CANT_MOVE (insn) = 1;
3356
3357       if (find_reg_note (insn, REG_SETJMP, NULL))
3358         {
3359           /* This is setjmp.  Assume that all registers, not just
3360              hard registers, may be clobbered by this call.  */
3361           reg_pending_barrier = MOVE_BARRIER;
3362         }
3363       else
3364         {
3365           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3366             /* A call may read and modify global register variables.  */
3367             if (global_regs[i])
3368               {
3369                 SET_REGNO_REG_SET (reg_pending_sets, i);
3370                 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3371               }
3372           /* Other call-clobbered hard regs may be clobbered.
3373              Since we only have a choice between 'might be clobbered'
3374              and 'definitely not clobbered', we must include all
3375              partly call-clobbered registers here.  */
3376             else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
3377                      || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3378               SET_REGNO_REG_SET (reg_pending_clobbers, i);
3379           /* We don't know what set of fixed registers might be used
3380              by the function, but it is certain that the stack pointer
3381              is among them, but be conservative.  */
3382             else if (fixed_regs[i])
3383               SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3384           /* The frame pointer is normally not used by the function
3385              itself, but by the debugger.  */
3386           /* ??? MIPS o32 is an exception.  It uses the frame pointer
3387              in the macro expansion of jal but does not represent this
3388              fact in the call_insn rtl.  */
3389             else if (i == FRAME_POINTER_REGNUM
3390                      || (i == HARD_FRAME_POINTER_REGNUM
3391                          && (! reload_completed || frame_pointer_needed)))
3392               SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3393         }
3394
3395       /* For each insn which shouldn't cross a call, add a dependence
3396          between that insn and this call insn.  */
3397       add_dependence_list_and_free (deps, insn,
3398                                     &deps->sched_before_next_call, 1,
3399                                     REG_DEP_ANTI);
3400
3401       sched_analyze_insn (deps, PATTERN (insn), insn);
3402
3403       /* If CALL would be in a sched group, then this will violate
3404          convention that sched group insns have dependencies only on the
3405          previous instruction.
3406
3407          Of course one can say: "Hey!  What about head of the sched group?"
3408          And I will answer: "Basic principles (one dep per insn) are always
3409          the same."  */
3410       gcc_assert (!SCHED_GROUP_P (insn));
3411
3412       /* In the absence of interprocedural alias analysis, we must flush
3413          all pending reads and writes, and start new dependencies starting
3414          from here.  But only flush writes for constant calls (which may
3415          be passed a pointer to something we haven't written yet).  */
3416       flush_pending_lists (deps, insn, true, ! RTL_CONST_OR_PURE_CALL_P (insn));
3417
3418       if (!deps->readonly)
3419         {
3420           /* Remember the last function call for limiting lifetimes.  */
3421           free_INSN_LIST_list (&deps->last_function_call);
3422           deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3423
3424           if (call_may_noreturn_p (insn))
3425             {
3426               /* Remember the last function call that might not always return
3427                  normally for limiting moves of trapping insns.  */
3428               free_INSN_LIST_list (&deps->last_function_call_may_noreturn);
3429               deps->last_function_call_may_noreturn
3430                 = alloc_INSN_LIST (insn, NULL_RTX);
3431             }
3432
3433           /* Before reload, begin a post-call group, so as to keep the
3434              lifetimes of hard registers correct.  */
3435           if (! reload_completed)
3436             deps->in_post_call_group_p = post_call;
3437         }
3438     }
3439
3440   if (sched_deps_info->use_cselib)
3441     cselib_process_insn (insn);
3442
3443   /* EH_REGION insn notes can not appear until well after we complete
3444      scheduling.  */
3445   if (NOTE_P (insn))
3446     gcc_assert (NOTE_KIND (insn) != NOTE_INSN_EH_REGION_BEG
3447                 && NOTE_KIND (insn) != NOTE_INSN_EH_REGION_END);
3448
3449   if (sched_deps_info->finish_insn)
3450     sched_deps_info->finish_insn ();
3451
3452   /* Fixup the dependencies in the sched group.  */
3453   if ((NONJUMP_INSN_P (insn) || JUMP_P (insn))
3454       && SCHED_GROUP_P (insn) && !sel_sched_p ())
3455     fixup_sched_groups (insn);
3456 }
3457
3458 /* Initialize DEPS for the new block beginning with HEAD.  */
3459 void
3460 deps_start_bb (struct deps_desc *deps, rtx head)
3461 {
3462   gcc_assert (!deps->readonly);
3463
3464   /* Before reload, if the previous block ended in a call, show that
3465      we are inside a post-call group, so as to keep the lifetimes of
3466      hard registers correct.  */
3467   if (! reload_completed && !LABEL_P (head))
3468     {
3469       rtx insn = prev_nonnote_nondebug_insn (head);
3470
3471       if (insn && CALL_P (insn))
3472         deps->in_post_call_group_p = post_call_initial;
3473     }
3474 }
3475
3476 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3477    dependencies for each insn.  */
3478 void
3479 sched_analyze (struct deps_desc *deps, rtx head, rtx tail)
3480 {
3481   rtx insn;
3482
3483   if (sched_deps_info->use_cselib)
3484     cselib_init (CSELIB_RECORD_MEMORY);
3485
3486   deps_start_bb (deps, head);
3487
3488   for (insn = head;; insn = NEXT_INSN (insn))
3489     {
3490
3491       if (INSN_P (insn))
3492         {
3493           /* And initialize deps_lists.  */
3494           sd_init_insn (insn);
3495         }
3496
3497       deps_analyze_insn (deps, insn);
3498
3499       if (insn == tail)
3500         {
3501           if (sched_deps_info->use_cselib)
3502             cselib_finish ();
3503           return;
3504         }
3505     }
3506   gcc_unreachable ();
3507 }
3508
3509 /* Helper for sched_free_deps ().
3510    Delete INSN's (RESOLVED_P) backward dependencies.  */
3511 static void
3512 delete_dep_nodes_in_back_deps (rtx insn, bool resolved_p)
3513 {
3514   sd_iterator_def sd_it;
3515   dep_t dep;
3516   sd_list_types_def types;
3517
3518   if (resolved_p)
3519     types = SD_LIST_RES_BACK;
3520   else
3521     types = SD_LIST_BACK;
3522
3523   for (sd_it = sd_iterator_start (insn, types);
3524        sd_iterator_cond (&sd_it, &dep);)
3525     {
3526       dep_link_t link = *sd_it.linkp;
3527       dep_node_t node = DEP_LINK_NODE (link);
3528       deps_list_t back_list;
3529       deps_list_t forw_list;
3530
3531       get_back_and_forw_lists (dep, resolved_p, &back_list, &forw_list);
3532       remove_from_deps_list (link, back_list);
3533       delete_dep_node (node);
3534     }
3535 }
3536
3537 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3538    deps_lists.  */
3539 void
3540 sched_free_deps (rtx head, rtx tail, bool resolved_p)
3541 {
3542   rtx insn;
3543   rtx next_tail = NEXT_INSN (tail);
3544
3545   /* We make two passes since some insns may be scheduled before their
3546      dependencies are resolved.  */
3547   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3548     if (INSN_P (insn) && INSN_LUID (insn) > 0)
3549       {
3550         /* Clear forward deps and leave the dep_nodes to the
3551            corresponding back_deps list.  */
3552         if (resolved_p)
3553           clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
3554         else
3555           clear_deps_list (INSN_FORW_DEPS (insn));
3556       }
3557   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3558     if (INSN_P (insn) && INSN_LUID (insn) > 0)
3559       {
3560         /* Clear resolved back deps together with its dep_nodes.  */
3561         delete_dep_nodes_in_back_deps (insn, resolved_p);
3562
3563         sd_finish_insn (insn);
3564       }
3565 }
3566 \f
3567 /* Initialize variables for region data dependence analysis.
3568    When LAZY_REG_LAST is true, do not allocate reg_last array
3569    of struct deps_desc immediately.  */
3570
3571 void
3572 init_deps (struct deps_desc *deps, bool lazy_reg_last)
3573 {
3574   int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
3575
3576   deps->max_reg = max_reg;
3577   if (lazy_reg_last)
3578     deps->reg_last = NULL;
3579   else
3580     deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
3581   INIT_REG_SET (&deps->reg_last_in_use);
3582
3583   deps->pending_read_insns = 0;
3584   deps->pending_read_mems = 0;
3585   deps->pending_write_insns = 0;
3586   deps->pending_write_mems = 0;
3587   deps->pending_read_list_length = 0;
3588   deps->pending_write_list_length = 0;
3589   deps->pending_flush_length = 0;
3590   deps->last_pending_memory_flush = 0;
3591   deps->last_function_call = 0;
3592   deps->last_function_call_may_noreturn = 0;
3593   deps->sched_before_next_call = 0;
3594   deps->sched_before_next_jump = 0;
3595   deps->in_post_call_group_p = not_post_call;
3596   deps->last_debug_insn = 0;
3597   deps->last_reg_pending_barrier = NOT_A_BARRIER;
3598   deps->readonly = 0;
3599 }
3600
3601 /* Init only reg_last field of DEPS, which was not allocated before as
3602    we inited DEPS lazily.  */
3603 void
3604 init_deps_reg_last (struct deps_desc *deps)
3605 {
3606   gcc_assert (deps && deps->max_reg > 0);
3607   gcc_assert (deps->reg_last == NULL);
3608
3609   deps->reg_last = XCNEWVEC (struct deps_reg, deps->max_reg);
3610 }
3611
3612
3613 /* Free insn lists found in DEPS.  */
3614
3615 void
3616 free_deps (struct deps_desc *deps)
3617 {
3618   unsigned i;
3619   reg_set_iterator rsi;
3620
3621   /* We set max_reg to 0 when this context was already freed.  */
3622   if (deps->max_reg == 0)
3623     {
3624       gcc_assert (deps->reg_last == NULL);
3625       return;
3626     }
3627   deps->max_reg = 0;
3628
3629   free_INSN_LIST_list (&deps->pending_read_insns);
3630   free_EXPR_LIST_list (&deps->pending_read_mems);
3631   free_INSN_LIST_list (&deps->pending_write_insns);
3632   free_EXPR_LIST_list (&deps->pending_write_mems);
3633   free_INSN_LIST_list (&deps->last_pending_memory_flush);
3634
3635   /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3636      times.  For a testcase with 42000 regs and 8000 small basic blocks,
3637      this loop accounted for nearly 60% (84 sec) of the total -O2 runtime.  */
3638   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3639     {
3640       struct deps_reg *reg_last = &deps->reg_last[i];
3641       if (reg_last->uses)
3642         free_INSN_LIST_list (&reg_last->uses);
3643       if (reg_last->sets)
3644         free_INSN_LIST_list (&reg_last->sets);
3645       if (reg_last->implicit_sets)
3646         free_INSN_LIST_list (&reg_last->implicit_sets);
3647       if (reg_last->clobbers)
3648         free_INSN_LIST_list (&reg_last->clobbers);
3649     }
3650   CLEAR_REG_SET (&deps->reg_last_in_use);
3651
3652   /* As we initialize reg_last lazily, it is possible that we didn't allocate
3653      it at all.  */
3654   free (deps->reg_last);
3655   deps->reg_last = NULL;
3656
3657   deps = NULL;
3658 }
3659
3660 /* Remove INSN from dependence contexts DEPS.  */
3661 void
3662 remove_from_deps (struct deps_desc *deps, rtx insn)
3663 {
3664   int removed;
3665   unsigned i;
3666   reg_set_iterator rsi;
3667
3668   removed = remove_from_both_dependence_lists (insn, &deps->pending_read_insns,
3669                                                &deps->pending_read_mems);
3670   if (!DEBUG_INSN_P (insn))
3671     deps->pending_read_list_length -= removed;
3672   removed = remove_from_both_dependence_lists (insn, &deps->pending_write_insns,
3673                                                &deps->pending_write_mems);
3674   deps->pending_write_list_length -= removed;
3675   removed = remove_from_dependence_list (insn, &deps->last_pending_memory_flush);
3676   deps->pending_flush_length -= removed;
3677
3678   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3679     {
3680       struct deps_reg *reg_last = &deps->reg_last[i];
3681       if (reg_last->uses)
3682         remove_from_dependence_list (insn, &reg_last->uses);
3683       if (reg_last->sets)
3684         remove_from_dependence_list (insn, &reg_last->sets);
3685       if (reg_last->implicit_sets)
3686         remove_from_dependence_list (insn, &reg_last->implicit_sets);
3687       if (reg_last->clobbers)
3688         remove_from_dependence_list (insn, &reg_last->clobbers);
3689       if (!reg_last->uses && !reg_last->sets && !reg_last->implicit_sets
3690           && !reg_last->clobbers)
3691         CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, i);
3692     }
3693
3694   if (CALL_P (insn))
3695     {
3696       remove_from_dependence_list (insn, &deps->last_function_call);
3697       remove_from_dependence_list (insn,
3698                                    &deps->last_function_call_may_noreturn);
3699     }
3700   remove_from_dependence_list (insn, &deps->sched_before_next_call);
3701 }
3702
3703 /* Init deps data vector.  */
3704 static void
3705 init_deps_data_vector (void)
3706 {
3707   int reserve = (sched_max_luid + 1
3708                  - VEC_length (haifa_deps_insn_data_def, h_d_i_d));
3709   if (reserve > 0
3710       && ! VEC_space (haifa_deps_insn_data_def, h_d_i_d, reserve))
3711     VEC_safe_grow_cleared (haifa_deps_insn_data_def, heap, h_d_i_d,
3712                            3 * sched_max_luid / 2);
3713 }
3714
3715 /* If it is profitable to use them, initialize or extend (depending on
3716    GLOBAL_P) dependency data.  */
3717 void
3718 sched_deps_init (bool global_p)
3719 {
3720   /* Average number of insns in the basic block.
3721      '+ 1' is used to make it nonzero.  */
3722   int insns_in_block = sched_max_luid / n_basic_blocks + 1;
3723
3724   init_deps_data_vector ();
3725
3726   /* We use another caching mechanism for selective scheduling, so
3727      we don't use this one.  */
3728   if (!sel_sched_p () && global_p && insns_in_block > 100 * 5)
3729     {
3730       /* ?!? We could save some memory by computing a per-region luid mapping
3731          which could reduce both the number of vectors in the cache and the
3732          size of each vector.  Instead we just avoid the cache entirely unless
3733          the average number of instructions in a basic block is very high.  See
3734          the comment before the declaration of true_dependency_cache for
3735          what we consider "very high".  */
3736       cache_size = 0;
3737       extend_dependency_caches (sched_max_luid, true);
3738     }
3739
3740   if (global_p)
3741     {
3742       dl_pool = create_alloc_pool ("deps_list", sizeof (struct _deps_list),
3743                                    /* Allocate lists for one block at a time.  */
3744                                    insns_in_block);
3745       dn_pool = create_alloc_pool ("dep_node", sizeof (struct _dep_node),
3746                                    /* Allocate nodes for one block at a time.
3747                                       We assume that average insn has
3748                                       5 producers.  */
3749                                    5 * insns_in_block);
3750     }
3751 }
3752
3753
3754 /* Create or extend (depending on CREATE_P) dependency caches to
3755    size N.  */
3756 void
3757 extend_dependency_caches (int n, bool create_p)
3758 {
3759   if (create_p || true_dependency_cache)
3760     {
3761       int i, luid = cache_size + n;
3762
3763       true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
3764                                           luid);
3765       output_dependency_cache = XRESIZEVEC (bitmap_head,
3766                                             output_dependency_cache, luid);
3767       anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
3768                                           luid);
3769
3770       if (current_sched_info->flags & DO_SPECULATION)
3771         spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
3772                                             luid);
3773
3774       for (i = cache_size; i < luid; i++)
3775         {
3776           bitmap_initialize (&true_dependency_cache[i], 0);
3777           bitmap_initialize (&output_dependency_cache[i], 0);
3778           bitmap_initialize (&anti_dependency_cache[i], 0);
3779
3780           if (current_sched_info->flags & DO_SPECULATION)
3781             bitmap_initialize (&spec_dependency_cache[i], 0);
3782         }
3783       cache_size = luid;
3784     }
3785 }
3786
3787 /* Finalize dependency information for the whole function.  */
3788 void
3789 sched_deps_finish (void)
3790 {
3791   gcc_assert (deps_pools_are_empty_p ());
3792   free_alloc_pool_if_empty (&dn_pool);
3793   free_alloc_pool_if_empty (&dl_pool);
3794   gcc_assert (dn_pool == NULL && dl_pool == NULL);
3795
3796   VEC_free (haifa_deps_insn_data_def, heap, h_d_i_d);
3797   cache_size = 0;
3798
3799   if (true_dependency_cache)
3800     {
3801       int i;
3802
3803       for (i = 0; i < cache_size; i++)
3804         {
3805           bitmap_clear (&true_dependency_cache[i]);
3806           bitmap_clear (&output_dependency_cache[i]);
3807           bitmap_clear (&anti_dependency_cache[i]);
3808
3809           if (sched_deps_info->generate_spec_deps)
3810             bitmap_clear (&spec_dependency_cache[i]);
3811         }
3812       free (true_dependency_cache);
3813       true_dependency_cache = NULL;
3814       free (output_dependency_cache);
3815       output_dependency_cache = NULL;
3816       free (anti_dependency_cache);
3817       anti_dependency_cache = NULL;
3818
3819       if (sched_deps_info->generate_spec_deps)
3820         {
3821           free (spec_dependency_cache);
3822           spec_dependency_cache = NULL;
3823         }
3824
3825     }
3826 }
3827
3828 /* Initialize some global variables needed by the dependency analysis
3829    code.  */
3830
3831 void
3832 init_deps_global (void)
3833 {
3834   CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
3835   CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
3836   reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
3837   reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
3838   reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
3839   reg_pending_barrier = NOT_A_BARRIER;
3840
3841   if (!sel_sched_p () || sched_emulate_haifa_p)
3842     {
3843       sched_deps_info->start_insn = haifa_start_insn;
3844       sched_deps_info->finish_insn = haifa_finish_insn;
3845
3846       sched_deps_info->note_reg_set = haifa_note_reg_set;
3847       sched_deps_info->note_reg_clobber = haifa_note_reg_clobber;
3848       sched_deps_info->note_reg_use = haifa_note_reg_use;
3849
3850       sched_deps_info->note_mem_dep = haifa_note_mem_dep;
3851       sched_deps_info->note_dep = haifa_note_dep;
3852    }
3853 }
3854
3855 /* Free everything used by the dependency analysis code.  */
3856
3857 void
3858 finish_deps_global (void)
3859 {
3860   FREE_REG_SET (reg_pending_sets);
3861   FREE_REG_SET (reg_pending_clobbers);
3862   FREE_REG_SET (reg_pending_uses);
3863 }
3864
3865 /* Estimate the weakness of dependence between MEM1 and MEM2.  */
3866 dw_t
3867 estimate_dep_weak (rtx mem1, rtx mem2)
3868 {
3869   rtx r1, r2;
3870
3871   if (mem1 == mem2)
3872     /* MEMs are the same - don't speculate.  */
3873     return MIN_DEP_WEAK;
3874
3875   r1 = XEXP (mem1, 0);
3876   r2 = XEXP (mem2, 0);
3877
3878   if (r1 == r2
3879       || (REG_P (r1) && REG_P (r2)
3880           && REGNO (r1) == REGNO (r2)))
3881     /* Again, MEMs are the same.  */
3882     return MIN_DEP_WEAK;
3883   else if ((REG_P (r1) && !REG_P (r2))
3884            || (!REG_P (r1) && REG_P (r2)))
3885     /* Different addressing modes - reason to be more speculative,
3886        than usual.  */
3887     return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
3888   else
3889     /* We can't say anything about the dependence.  */
3890     return UNCERTAIN_DEP_WEAK;
3891 }
3892
3893 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
3894    This function can handle same INSN and ELEM (INSN == ELEM).
3895    It is a convenience wrapper.  */
3896 void
3897 add_dependence (rtx insn, rtx elem, enum reg_note dep_type)
3898 {
3899   ds_t ds;
3900   bool internal;
3901
3902   if (dep_type == REG_DEP_TRUE)
3903     ds = DEP_TRUE;
3904   else if (dep_type == REG_DEP_OUTPUT)
3905     ds = DEP_OUTPUT;
3906   else
3907     {
3908       gcc_assert (dep_type == REG_DEP_ANTI);
3909       ds = DEP_ANTI;
3910     }
3911
3912   /* When add_dependence is called from inside sched-deps.c, we expect
3913      cur_insn to be non-null.  */
3914   internal = cur_insn != NULL;
3915   if (internal)
3916     gcc_assert (insn == cur_insn);
3917   else
3918     cur_insn = insn;
3919
3920   note_dep (elem, ds);
3921   if (!internal)
3922     cur_insn = NULL;
3923 }
3924
3925 /* Return weakness of speculative type TYPE in the dep_status DS.  */
3926 dw_t
3927 get_dep_weak_1 (ds_t ds, ds_t type)
3928 {
3929   ds = ds & type;
3930
3931   switch (type)
3932     {
3933     case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
3934     case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
3935     case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
3936     case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
3937     default: gcc_unreachable ();
3938     }
3939
3940   return (dw_t) ds;
3941 }
3942
3943 dw_t
3944 get_dep_weak (ds_t ds, ds_t type)
3945 {
3946   dw_t dw = get_dep_weak_1 (ds, type);
3947
3948   gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
3949   return dw;
3950 }
3951
3952 /* Return the dep_status, which has the same parameters as DS, except for
3953    speculative type TYPE, that will have weakness DW.  */
3954 ds_t
3955 set_dep_weak (ds_t ds, ds_t type, dw_t dw)
3956 {
3957   gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
3958
3959   ds &= ~type;
3960   switch (type)
3961     {
3962     case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
3963     case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
3964     case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
3965     case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
3966     default: gcc_unreachable ();
3967     }
3968   return ds;
3969 }
3970
3971 /* Return the join of two dep_statuses DS1 and DS2.
3972    If MAX_P is true then choose the greater probability,
3973    otherwise multiply probabilities.
3974    This function assumes that both DS1 and DS2 contain speculative bits.  */
3975 static ds_t
3976 ds_merge_1 (ds_t ds1, ds_t ds2, bool max_p)
3977 {
3978   ds_t ds, t;
3979
3980   gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
3981
3982   ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
3983
3984   t = FIRST_SPEC_TYPE;
3985   do
3986     {
3987       if ((ds1 & t) && !(ds2 & t))
3988         ds |= ds1 & t;
3989       else if (!(ds1 & t) && (ds2 & t))
3990         ds |= ds2 & t;
3991       else if ((ds1 & t) && (ds2 & t))
3992         {
3993           dw_t dw1 = get_dep_weak (ds1, t);
3994           dw_t dw2 = get_dep_weak (ds2, t);
3995           ds_t dw;
3996
3997           if (!max_p)
3998             {
3999               dw = ((ds_t) dw1) * ((ds_t) dw2);
4000               dw /= MAX_DEP_WEAK;
4001               if (dw < MIN_DEP_WEAK)
4002                 dw = MIN_DEP_WEAK;
4003             }
4004           else
4005             {
4006               if (dw1 >= dw2)
4007                 dw = dw1;
4008               else
4009                 dw = dw2;
4010             }
4011
4012           ds = set_dep_weak (ds, t, (dw_t) dw);
4013         }
4014
4015       if (t == LAST_SPEC_TYPE)
4016         break;
4017       t <<= SPEC_TYPE_SHIFT;
4018     }
4019   while (1);
4020
4021   return ds;
4022 }
4023
4024 /* Return the join of two dep_statuses DS1 and DS2.
4025    This function assumes that both DS1 and DS2 contain speculative bits.  */
4026 ds_t
4027 ds_merge (ds_t ds1, ds_t ds2)
4028 {
4029   return ds_merge_1 (ds1, ds2, false);
4030 }
4031
4032 /* Return the join of two dep_statuses DS1 and DS2.  */
4033 ds_t
4034 ds_full_merge (ds_t ds, ds_t ds2, rtx mem1, rtx mem2)
4035 {
4036   ds_t new_status = ds | ds2;
4037
4038   if (new_status & SPECULATIVE)
4039     {
4040       if ((ds && !(ds & SPECULATIVE))
4041           || (ds2 && !(ds2 & SPECULATIVE)))
4042         /* Then this dep can't be speculative.  */
4043         new_status &= ~SPECULATIVE;
4044       else
4045         {
4046           /* Both are speculative.  Merging probabilities.  */
4047           if (mem1)
4048             {
4049               dw_t dw;
4050
4051               dw = estimate_dep_weak (mem1, mem2);
4052               ds = set_dep_weak (ds, BEGIN_DATA, dw);
4053             }
4054
4055           if (!ds)
4056             new_status = ds2;
4057           else if (!ds2)
4058             new_status = ds;
4059           else
4060             new_status = ds_merge (ds2, ds);
4061         }
4062     }
4063
4064   return new_status;
4065 }
4066
4067 /* Return the join of DS1 and DS2.  Use maximum instead of multiplying
4068    probabilities.  */
4069 ds_t
4070 ds_max_merge (ds_t ds1, ds_t ds2)
4071 {
4072   if (ds1 == 0 && ds2 == 0)
4073     return 0;
4074
4075   if (ds1 == 0 && ds2 != 0)
4076     return ds2;
4077
4078   if (ds1 != 0 && ds2 == 0)
4079     return ds1;
4080
4081   return ds_merge_1 (ds1, ds2, true);
4082 }
4083
4084 /* Return the probability of speculation success for the speculation
4085    status DS.  */
4086 dw_t
4087 ds_weak (ds_t ds)
4088 {
4089   ds_t res = 1, dt;
4090   int n = 0;
4091
4092   dt = FIRST_SPEC_TYPE;
4093   do
4094     {
4095       if (ds & dt)
4096         {
4097           res *= (ds_t) get_dep_weak (ds, dt);
4098           n++;
4099         }
4100
4101       if (dt == LAST_SPEC_TYPE)
4102         break;
4103       dt <<= SPEC_TYPE_SHIFT;
4104     }
4105   while (1);
4106
4107   gcc_assert (n);
4108   while (--n)
4109     res /= MAX_DEP_WEAK;
4110
4111   if (res < MIN_DEP_WEAK)
4112     res = MIN_DEP_WEAK;
4113
4114   gcc_assert (res <= MAX_DEP_WEAK);
4115
4116   return (dw_t) res;
4117 }
4118
4119 /* Return a dep status that contains all speculation types of DS.  */
4120 ds_t
4121 ds_get_speculation_types (ds_t ds)
4122 {
4123   if (ds & BEGIN_DATA)
4124     ds |= BEGIN_DATA;
4125   if (ds & BE_IN_DATA)
4126     ds |= BE_IN_DATA;
4127   if (ds & BEGIN_CONTROL)
4128     ds |= BEGIN_CONTROL;
4129   if (ds & BE_IN_CONTROL)
4130     ds |= BE_IN_CONTROL;
4131
4132   return ds & SPECULATIVE;
4133 }
4134
4135 /* Return a dep status that contains maximal weakness for each speculation
4136    type present in DS.  */
4137 ds_t
4138 ds_get_max_dep_weak (ds_t ds)
4139 {
4140   if (ds & BEGIN_DATA)
4141     ds = set_dep_weak (ds, BEGIN_DATA, MAX_DEP_WEAK);
4142   if (ds & BE_IN_DATA)
4143     ds = set_dep_weak (ds, BE_IN_DATA, MAX_DEP_WEAK);
4144   if (ds & BEGIN_CONTROL)
4145     ds = set_dep_weak (ds, BEGIN_CONTROL, MAX_DEP_WEAK);
4146   if (ds & BE_IN_CONTROL)
4147     ds = set_dep_weak (ds, BE_IN_CONTROL, MAX_DEP_WEAK);
4148
4149   return ds;
4150 }
4151
4152 /* Dump information about the dependence status S.  */
4153 static void
4154 dump_ds (FILE *f, ds_t s)
4155 {
4156   fprintf (f, "{");
4157
4158   if (s & BEGIN_DATA)
4159     fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak_1 (s, BEGIN_DATA));
4160   if (s & BE_IN_DATA)
4161     fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak_1 (s, BE_IN_DATA));
4162   if (s & BEGIN_CONTROL)
4163     fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s, BEGIN_CONTROL));
4164   if (s & BE_IN_CONTROL)
4165     fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s, BE_IN_CONTROL));
4166
4167   if (s & HARD_DEP)
4168     fprintf (f, "HARD_DEP; ");
4169
4170   if (s & DEP_TRUE)
4171     fprintf (f, "DEP_TRUE; ");
4172   if (s & DEP_ANTI)
4173     fprintf (f, "DEP_ANTI; ");
4174   if (s & DEP_OUTPUT)
4175     fprintf (f, "DEP_OUTPUT; ");
4176
4177   fprintf (f, "}");
4178 }
4179
4180 DEBUG_FUNCTION void
4181 debug_ds (ds_t s)
4182 {
4183   dump_ds (stderr, s);
4184   fprintf (stderr, "\n");
4185 }
4186
4187 #ifdef ENABLE_CHECKING
4188 /* Verify that dependence type and status are consistent.
4189    If RELAXED_P is true, then skip dep_weakness checks.  */
4190 static void
4191 check_dep (dep_t dep, bool relaxed_p)
4192 {
4193   enum reg_note dt = DEP_TYPE (dep);
4194   ds_t ds = DEP_STATUS (dep);
4195
4196   gcc_assert (DEP_PRO (dep) != DEP_CON (dep));
4197
4198   if (!(current_sched_info->flags & USE_DEPS_LIST))
4199     {
4200       gcc_assert (ds == 0);
4201       return;
4202     }
4203
4204   /* Check that dependence type contains the same bits as the status.  */
4205   if (dt == REG_DEP_TRUE)
4206     gcc_assert (ds & DEP_TRUE);
4207   else if (dt == REG_DEP_OUTPUT)
4208     gcc_assert ((ds & DEP_OUTPUT)
4209                 && !(ds & DEP_TRUE));
4210   else
4211     gcc_assert ((dt == REG_DEP_ANTI)
4212                 && (ds & DEP_ANTI)
4213                 && !(ds & (DEP_OUTPUT | DEP_TRUE)));
4214
4215   /* HARD_DEP can not appear in dep_status of a link.  */
4216   gcc_assert (!(ds & HARD_DEP));
4217
4218   /* Check that dependence status is set correctly when speculation is not
4219      supported.  */
4220   if (!sched_deps_info->generate_spec_deps)
4221     gcc_assert (!(ds & SPECULATIVE));
4222   else if (ds & SPECULATIVE)
4223     {
4224       if (!relaxed_p)
4225         {
4226           ds_t type = FIRST_SPEC_TYPE;
4227
4228           /* Check that dependence weakness is in proper range.  */
4229           do
4230             {
4231               if (ds & type)
4232                 get_dep_weak (ds, type);
4233
4234               if (type == LAST_SPEC_TYPE)
4235                 break;
4236               type <<= SPEC_TYPE_SHIFT;
4237             }
4238           while (1);
4239         }
4240
4241       if (ds & BEGIN_SPEC)
4242         {
4243           /* Only true dependence can be data speculative.  */
4244           if (ds & BEGIN_DATA)
4245             gcc_assert (ds & DEP_TRUE);
4246
4247           /* Control dependencies in the insn scheduler are represented by
4248              anti-dependencies, therefore only anti dependence can be
4249              control speculative.  */
4250           if (ds & BEGIN_CONTROL)
4251             gcc_assert (ds & DEP_ANTI);
4252         }
4253       else
4254         {
4255           /* Subsequent speculations should resolve true dependencies.  */
4256           gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
4257         }
4258
4259       /* Check that true and anti dependencies can't have other speculative
4260          statuses.  */
4261       if (ds & DEP_TRUE)
4262         gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
4263       /* An output dependence can't be speculative at all.  */
4264       gcc_assert (!(ds & DEP_OUTPUT));
4265       if (ds & DEP_ANTI)
4266         gcc_assert (ds & BEGIN_CONTROL);
4267     }
4268 }
4269 #endif /* ENABLE_CHECKING */
4270
4271 #endif /* INSN_SCHEDULING */