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