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