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