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 *, 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 *, rtx, int, int);
 451 static void sched_analyze_1 (struct deps *, rtx, rtx);
 452 static void sched_analyze_2 (struct deps *, rtx, rtx);
 453 static void sched_analyze_insn (struct deps *, 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 *deps, rtx insn, rtx *listp,
1406                               int uncond, enum reg_note dep_type)
1407 {
1408   rtx list, next;
1409
1410   if (deps->readonly)
1411     {
1412       add_dependence_list (insn, *listp, uncond, dep_type);
1413       return;
1414     }
1415
1416   for (list = *listp, *listp = NULL; list ; list = next)
1417     {
1418       next = XEXP (list, 1);
1419       if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
1420         add_dependence (insn, XEXP (list, 0), dep_type);
1421       free_INSN_LIST_node (list);
1422     }
1423 }
1424
1425 /* Remove all occurences of INSN from LIST.  Return the number of
1426    occurences removed.  */
1427
1428 static int
1429 remove_from_dependence_list (rtx insn, rtx* listp)
1430 {
1431   int removed = 0;
1432
1433   while (*listp)
1434     {
1435       if (XEXP (*listp, 0) == insn)
1436         {
1437           remove_free_INSN_LIST_node (listp);
1438           removed++;
1439           continue;
1440         }
1441
1442       listp = &XEXP (*listp, 1);
1443     }
1444
1445   return removed;
1446 }
1447
1448 /* Same as above, but process two lists at once.  */
1449 static int
1450 remove_from_both_dependence_lists (rtx insn, rtx *listp, rtx *exprp)
1451 {
1452   int removed = 0;
1453
1454   while (*listp)
1455     {
1456       if (XEXP (*listp, 0) == insn)
1457         {
1458           remove_free_INSN_LIST_node (listp);
1459           remove_free_EXPR_LIST_node (exprp);
1460           removed++;
1461           continue;
1462         }
1463
1464       listp = &XEXP (*listp, 1);
1465       exprp = &XEXP (*exprp, 1);
1466     }
1467
1468   return removed;
1469 }
1470
1471 /* Clear all dependencies for an insn.  */
1472 static void
1473 delete_all_dependences (rtx insn)
1474 {
1475   sd_iterator_def sd_it;
1476   dep_t dep;
1477
1478   /* The below cycle can be optimized to clear the caches and back_deps
1479      in one call but that would provoke duplication of code from
1480      delete_dep ().  */
1481
1482   for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
1483        sd_iterator_cond (&sd_it, &dep);)
1484     sd_delete_dep (sd_it);
1485 }
1486
1487 /* All insns in a scheduling group except the first should only have
1488    dependencies on the previous insn in the group.  So we find the
1489    first instruction in the scheduling group by walking the dependence
1490    chains backwards. Then we add the dependencies for the group to
1491    the previous nonnote insn.  */
1492
1493 static void
1494 fixup_sched_groups (rtx insn)
1495 {
1496   sd_iterator_def sd_it;
1497   dep_t dep;
1498   rtx prev_nonnote;
1499
1500   FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
1501     {
1502       rtx i = insn;
1503       rtx pro = DEP_PRO (dep);
1504
1505       do
1506         {
1507           i = prev_nonnote_insn (i);
1508
1509           if (pro == i)
1510             goto next_link;
1511         } while (SCHED_GROUP_P (i) || DEBUG_INSN_P (i));
1512
1513       if (! sched_insns_conditions_mutex_p (i, pro))
1514         add_dependence (i, pro, DEP_TYPE (dep));
1515     next_link:;
1516     }
1517
1518   delete_all_dependences (insn);
1519
1520   prev_nonnote = prev_nonnote_insn (insn);
1521   while (DEBUG_INSN_P (prev_nonnote))
1522     prev_nonnote = prev_nonnote_insn (prev_nonnote);
1523   if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
1524       && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
1525     add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
1526 }
1527 \f
1528 /* Process an insn's memory dependencies.  There are four kinds of
1529    dependencies:
1530
1531    (0) read dependence: read follows read
1532    (1) true dependence: read follows write
1533    (2) output dependence: write follows write
1534    (3) anti dependence: write follows read
1535
1536    We are careful to build only dependencies which actually exist, and
1537    use transitivity to avoid building too many links.  */
1538
1539 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1540    The MEM is a memory reference contained within INSN, which we are saving
1541    so that we can do memory aliasing on it.  */
1542
1543 static void
1544 add_insn_mem_dependence (struct deps *deps, bool read_p,
1545                          rtx insn, rtx mem)
1546 {
1547   rtx *insn_list;
1548   rtx *mem_list;
1549   rtx link;
1550
1551   gcc_assert (!deps->readonly);
1552   if (read_p)
1553     {
1554       insn_list = &deps->pending_read_insns;
1555       mem_list = &deps->pending_read_mems;
1556       if (!DEBUG_INSN_P (insn))
1557         deps->pending_read_list_length++;
1558     }
1559   else
1560     {
1561       insn_list = &deps->pending_write_insns;
1562       mem_list = &deps->pending_write_mems;
1563       deps->pending_write_list_length++;
1564     }
1565
1566   link = alloc_INSN_LIST (insn, *insn_list);
1567   *insn_list = link;
1568
1569   if (sched_deps_info->use_cselib)
1570     {
1571       mem = shallow_copy_rtx (mem);
1572       XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0));
1573     }
1574   link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
1575   *mem_list = link;
1576 }
1577
1578 /* Make a dependency between every memory reference on the pending lists
1579    and INSN, thus flushing the pending lists.  FOR_READ is true if emitting
1580    dependencies for a read operation, similarly with FOR_WRITE.  */
1581
1582 static void
1583 flush_pending_lists (struct deps *deps, rtx insn, int for_read,
1584                      int for_write)
1585 {
1586   if (for_write)
1587     {
1588       add_dependence_list_and_free (deps, insn, &deps->pending_read_insns,
1589                                     1, REG_DEP_ANTI);
1590       if (!deps->readonly)
1591         {
1592           free_EXPR_LIST_list (&deps->pending_read_mems);
1593           deps->pending_read_list_length = 0;
1594         }
1595     }
1596
1597   add_dependence_list_and_free (deps, insn, &deps->pending_write_insns, 1,
1598                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
1599
1600   add_dependence_list_and_free (deps, insn,
1601                                 &deps->last_pending_memory_flush, 1,
1602                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
1603   if (!deps->readonly)
1604     {
1605       free_EXPR_LIST_list (&deps->pending_write_mems);
1606       deps->pending_write_list_length = 0;
1607
1608       deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
1609       deps->pending_flush_length = 1;
1610     }
1611 }
1612 \f
1613 /* Instruction which dependencies we are analyzing.  */
1614 static rtx cur_insn = NULL_RTX;
1615
1616 /* Implement hooks for haifa scheduler.  */
1617
1618 static void
1619 haifa_start_insn (rtx insn)
1620 {
1621   gcc_assert (insn && !cur_insn);
1622
1623   cur_insn = insn;
1624 }
1625
1626 static void
1627 haifa_finish_insn (void)
1628 {
1629   cur_insn = NULL;
1630 }
1631
1632 void
1633 haifa_note_reg_set (int regno)
1634 {
1635   SET_REGNO_REG_SET (reg_pending_sets, regno);
1636 }
1637
1638 void
1639 haifa_note_reg_clobber (int regno)
1640 {
1641   SET_REGNO_REG_SET (reg_pending_clobbers, regno);
1642 }
1643
1644 void
1645 haifa_note_reg_use (int regno)
1646 {
1647   SET_REGNO_REG_SET (reg_pending_uses, regno);
1648 }
1649
1650 static void
1651 haifa_note_mem_dep (rtx mem, rtx pending_mem, rtx pending_insn, ds_t ds)
1652 {
1653   if (!(ds & SPECULATIVE))
1654     {
1655       mem = NULL_RTX;
1656       pending_mem = NULL_RTX;
1657     }
1658   else
1659     gcc_assert (ds & BEGIN_DATA);
1660
1661   {
1662     dep_def _dep, *dep = &_dep;
1663
1664     init_dep_1 (dep, pending_insn, cur_insn, ds_to_dt (ds),
1665                 current_sched_info->flags & USE_DEPS_LIST ? ds : -1);
1666     maybe_add_or_update_dep_1 (dep, false, pending_mem, mem);
1667   }
1668
1669 }
1670
1671 static void
1672 haifa_note_dep (rtx elem, ds_t ds)
1673 {
1674   dep_def _dep;
1675   dep_t dep = &_dep;
1676
1677   init_dep (dep, elem, cur_insn, ds_to_dt (ds));
1678   maybe_add_or_update_dep_1 (dep, false, NULL_RTX, NULL_RTX);
1679 }
1680
1681 static void
1682 note_reg_use (int r)
1683 {
1684   if (sched_deps_info->note_reg_use)
1685     sched_deps_info->note_reg_use (r);
1686 }
1687
1688 static void
1689 note_reg_set (int r)
1690 {
1691   if (sched_deps_info->note_reg_set)
1692     sched_deps_info->note_reg_set (r);
1693 }
1694
1695 static void
1696 note_reg_clobber (int r)
1697 {
1698   if (sched_deps_info->note_reg_clobber)
1699     sched_deps_info->note_reg_clobber (r);
1700 }
1701
1702 static void
1703 note_mem_dep (rtx m1, rtx m2, rtx e, ds_t ds)
1704 {
1705   if (sched_deps_info->note_mem_dep)
1706     sched_deps_info->note_mem_dep (m1, m2, e, ds);
1707 }
1708
1709 static void
1710 note_dep (rtx e, ds_t ds)
1711 {
1712   if (sched_deps_info->note_dep)
1713     sched_deps_info->note_dep (e, ds);
1714 }
1715
1716 /* Return corresponding to DS reg_note.  */
1717 enum reg_note
1718 ds_to_dt (ds_t ds)
1719 {
1720   if (ds & DEP_TRUE)
1721     return REG_DEP_TRUE;
1722   else if (ds & DEP_OUTPUT)
1723     return REG_DEP_OUTPUT;
1724   else
1725     {
1726       gcc_assert (ds & DEP_ANTI);
1727       return REG_DEP_ANTI;
1728     }
1729 }
1730
1731 \f
1732
1733 /* Functions for computation of info needed for register pressure
1734    sensitive insn scheduling.  */
1735
1736
1737 /* Allocate and return reg_use_data structure for REGNO and INSN.  */
1738 static struct reg_use_data *
1739 create_insn_reg_use (int regno, rtx insn)
1740 {
1741   struct reg_use_data *use;
1742
1743   use = (struct reg_use_data *) xmalloc (sizeof (struct reg_use_data));
1744   use->regno = regno;
1745   use->insn = insn;
1746   use->next_insn_use = INSN_REG_USE_LIST (insn);
1747   INSN_REG_USE_LIST (insn) = use;
1748   return use;
1749 }
1750
1751 /* Allocate and return reg_set_data structure for REGNO and INSN.  */
1752 static struct reg_set_data *
1753 create_insn_reg_set (int regno, rtx insn)
1754 {
1755   struct reg_set_data *set;
1756
1757   set = (struct reg_set_data *) xmalloc (sizeof (struct reg_set_data));
1758   set->regno = regno;
1759   set->insn = insn;
1760   set->next_insn_set = INSN_REG_SET_LIST (insn);
1761   INSN_REG_SET_LIST (insn) = set;
1762   return set;
1763 }
1764
1765 /* Set up insn register uses for INSN and dependency context DEPS.  */
1766 static void
1767 setup_insn_reg_uses (struct deps *deps, rtx insn)
1768 {
1769   unsigned i;
1770   reg_set_iterator rsi;
1771   rtx list;
1772   struct reg_use_data *use, *use2, *next;
1773   struct deps_reg *reg_last;
1774
1775   EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1776     {
1777       if (i < FIRST_PSEUDO_REGISTER
1778           && TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
1779         continue;
1780
1781       if (find_regno_note (insn, REG_DEAD, i) == NULL_RTX
1782           && ! REGNO_REG_SET_P (reg_pending_sets, i)
1783           && ! REGNO_REG_SET_P (reg_pending_clobbers, i))
1784         /* Ignore use which is not dying.  */
1785         continue;
1786
1787       use = create_insn_reg_use (i, insn);
1788       use->next_regno_use = use;
1789       reg_last = &deps->reg_last[i];
1790
1791       /* Create the cycle list of uses.  */
1792       for (list = reg_last->uses; list; list = XEXP (list, 1))
1793         {
1794           use2 = create_insn_reg_use (i, XEXP (list, 0));
1795           next = use->next_regno_use;
1796           use->next_regno_use = use2;
1797           use2->next_regno_use = next;
1798         }
1799     }
1800 }
1801
1802 /* Register pressure info for the currently processed insn.  */
1803 static struct reg_pressure_data reg_pressure_info[N_REG_CLASSES];
1804
1805 /* Return TRUE if INSN has the use structure for REGNO.  */
1806 static bool
1807 insn_use_p (rtx insn, int regno)
1808 {
1809   struct reg_use_data *use;
1810
1811   for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
1812     if (use->regno == regno)
1813       return true;
1814   return false;
1815 }
1816
1817 /* Update the register pressure info after birth of pseudo register REGNO
1818    in INSN.  Arguments CLOBBER_P and UNUSED_P say correspondingly that
1819    the register is in clobber or unused after the insn.  */
1820 static void
1821 mark_insn_pseudo_birth (rtx insn, int regno, bool clobber_p, bool unused_p)
1822 {
1823   int incr, new_incr;
1824   enum reg_class cl;
1825
1826   gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
1827   cl = sched_regno_cover_class[regno];
1828   if (cl != NO_REGS)
1829     {
1830       incr = ira_reg_class_nregs[cl][PSEUDO_REGNO_MODE (regno)];
1831       if (clobber_p)
1832         {
1833           new_incr = reg_pressure_info[cl].clobber_increase + incr;
1834           reg_pressure_info[cl].clobber_increase = new_incr;
1835         }
1836       else if (unused_p)
1837         {
1838           new_incr = reg_pressure_info[cl].unused_set_increase + incr;
1839           reg_pressure_info[cl].unused_set_increase = new_incr;
1840         }
1841       else
1842         {
1843           new_incr = reg_pressure_info[cl].set_increase + incr;
1844           reg_pressure_info[cl].set_increase = new_incr;
1845           if (! insn_use_p (insn, regno))
1846             reg_pressure_info[cl].change += incr;
1847           create_insn_reg_set (regno, insn);
1848         }
1849       gcc_assert (new_incr < (1 << INCREASE_BITS));
1850     }
1851 }
1852
1853 /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
1854    hard registers involved in the birth.  */
1855 static void
1856 mark_insn_hard_regno_birth (rtx insn, int regno, int nregs,
1857                             bool clobber_p, bool unused_p)
1858 {
1859   enum reg_class cl;
1860   int new_incr, last = regno + nregs;
1861
1862   while (regno < last)
1863     {
1864       gcc_assert (regno < FIRST_PSEUDO_REGISTER);
1865       if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
1866         {
1867           cl = sched_regno_cover_class[regno];
1868           if (cl != NO_REGS)
1869             {
1870               if (clobber_p)
1871                 {
1872                   new_incr = reg_pressure_info[cl].clobber_increase + 1;
1873                   reg_pressure_info[cl].clobber_increase = new_incr;
1874                 }
1875               else if (unused_p)
1876                 {
1877                   new_incr = reg_pressure_info[cl].unused_set_increase + 1;
1878                   reg_pressure_info[cl].unused_set_increase = new_incr;
1879                 }
1880               else
1881                 {
1882                   new_incr = reg_pressure_info[cl].set_increase + 1;
1883                   reg_pressure_info[cl].set_increase = new_incr;
1884                   if (! insn_use_p (insn, regno))
1885                     reg_pressure_info[cl].change += 1;
1886                   create_insn_reg_set (regno, insn);
1887                 }
1888               gcc_assert (new_incr < (1 << INCREASE_BITS));
1889             }
1890         }
1891       regno++;
1892     }
1893 }
1894
1895 /* Update the register pressure info after birth of pseudo or hard
1896    register REG in INSN.  Arguments CLOBBER_P and UNUSED_P say
1897    correspondingly that the register is in clobber or unused after the
1898    insn.  */
1899 static void
1900 mark_insn_reg_birth (rtx insn, rtx reg, bool clobber_p, bool unused_p)
1901 {
1902   int regno;
1903
1904   if (GET_CODE (reg) == SUBREG)
1905     reg = SUBREG_REG (reg);
1906
1907   if (! REG_P (reg))
1908     return;
1909
1910   regno = REGNO (reg);
1911   if (regno < FIRST_PSEUDO_REGISTER)
1912     mark_insn_hard_regno_birth (insn, regno,
1913                                 hard_regno_nregs[regno][GET_MODE (reg)],
1914                                 clobber_p, unused_p);
1915   else
1916     mark_insn_pseudo_birth (insn, regno, clobber_p, unused_p);
1917 }
1918
1919 /* Update the register pressure info after death of pseudo register
1920    REGNO.  */
1921 static void
1922 mark_pseudo_death (int regno)
1923 {
1924   int incr;
1925   enum reg_class cl;
1926
1927   gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
1928   cl = sched_regno_cover_class[regno];
1929   if (cl != NO_REGS)
1930     {
1931       incr = ira_reg_class_nregs[cl][PSEUDO_REGNO_MODE (regno)];
1932       reg_pressure_info[cl].change -= incr;
1933     }
1934 }
1935
1936 /* Like mark_pseudo_death except that NREGS saying how many hard
1937    registers involved in the death.  */
1938 static void
1939 mark_hard_regno_death (int regno, int nregs)
1940 {
1941   enum reg_class cl;
1942   int last = regno + nregs;
1943
1944   while (regno < last)
1945     {
1946       gcc_assert (regno < FIRST_PSEUDO_REGISTER);
1947       if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
1948         {
1949           cl = sched_regno_cover_class[regno];
1950           if (cl != NO_REGS)
1951             reg_pressure_info[cl].change -= 1;
1952         }
1953       regno++;
1954     }
1955 }
1956
1957 /* Update the register pressure info after death of pseudo or hard
1958    register REG.  */
1959 static void
1960 mark_reg_death (rtx reg)
1961 {
1962   int regno;
1963
1964   if (GET_CODE (reg) == SUBREG)
1965     reg = SUBREG_REG (reg);
1966
1967   if (! REG_P (reg))
1968     return;
1969
1970   regno = REGNO (reg);
1971   if (regno < FIRST_PSEUDO_REGISTER)
1972     mark_hard_regno_death (regno, hard_regno_nregs[regno][GET_MODE (reg)]);
1973   else
1974     mark_pseudo_death (regno);
1975 }
1976
1977 /* Process SETTER of REG.  DATA is an insn containing the setter.  */
1978 static void
1979 mark_insn_reg_store (rtx reg, const_rtx setter, void *data)
1980 {
1981   if (setter != NULL_RTX && GET_CODE (setter) != SET)
1982     return;
1983   mark_insn_reg_birth
1984     ((rtx) data, reg, false,
1985      find_reg_note ((const_rtx) data, REG_UNUSED, reg) != NULL_RTX);
1986 }
1987
1988 /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs.  */
1989 static void
1990 mark_insn_reg_clobber (rtx reg, const_rtx setter, void *data)
1991 {
1992   if (GET_CODE (setter) == CLOBBER)
1993     mark_insn_reg_birth ((rtx) data, reg, true, false);
1994 }
1995
1996 /* Set up reg pressure info related to INSN.  */
1997 static void
1998 setup_insn_reg_pressure_info (rtx insn)
1999 {
2000   int i, len;
2001   enum reg_class cl;
2002   static struct reg_pressure_data *pressure_info;
2003   rtx link;
2004
2005   gcc_assert (sched_pressure_p);
2006
2007   if (! INSN_P (insn))
2008     return;
2009
2010   for (i = 0; i < ira_reg_class_cover_size; i++)
2011     {
2012       cl = ira_reg_class_cover[i];
2013       reg_pressure_info[cl].clobber_increase = 0;
2014       reg_pressure_info[cl].set_increase = 0;
2015       reg_pressure_info[cl].unused_set_increase = 0;
2016       reg_pressure_info[cl].change = 0;
2017     }
2018
2019   note_stores (PATTERN (insn), mark_insn_reg_clobber, insn);
2020
2021   note_stores (PATTERN (insn), mark_insn_reg_store, insn);
2022
2023 #ifdef AUTO_INC_DEC
2024   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2025     if (REG_NOTE_KIND (link) == REG_INC)
2026       mark_insn_reg_store (XEXP (link, 0), NULL_RTX, insn);
2027 #endif
2028
2029   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2030     if (REG_NOTE_KIND (link) == REG_DEAD)
2031       mark_reg_death (XEXP (link, 0));
2032
2033   len = sizeof (struct reg_pressure_data) * ira_reg_class_cover_size;
2034   pressure_info
2035     = INSN_REG_PRESSURE (insn) = (struct reg_pressure_data *) xmalloc (len);
2036   INSN_MAX_REG_PRESSURE (insn) = (int *) xcalloc (ira_reg_class_cover_size
2037                                                   * sizeof (int), 1);
2038   for (i = 0; i < ira_reg_class_cover_size; i++)
2039     {
2040       cl = ira_reg_class_cover[i];
2041       pressure_info[i].clobber_increase
2042         = reg_pressure_info[cl].clobber_increase;
2043       pressure_info[i].set_increase = reg_pressure_info[cl].set_increase;
2044       pressure_info[i].unused_set_increase
2045         = reg_pressure_info[cl].unused_set_increase;
2046       pressure_info[i].change = reg_pressure_info[cl].change;
2047     }
2048 }
2049
2050
2051 \f
2052
2053 /* Internal variable for sched_analyze_[12] () functions.
2054    If it is nonzero, this means that sched_analyze_[12] looks
2055    at the most toplevel SET.  */
2056 static bool can_start_lhs_rhs_p;
2057
2058 /* Extend reg info for the deps context DEPS given that
2059    we have just generated a register numbered REGNO.  */
2060 static void
2061 extend_deps_reg_info (struct deps *deps, int regno)
2062 {
2063   int max_regno = regno + 1;
2064
2065   gcc_assert (!reload_completed);
2066
2067   /* In a readonly context, it would not hurt to extend info,
2068      but it should not be needed.  */
2069   if (reload_completed && deps->readonly)
2070     {
2071       deps->max_reg = max_regno;
2072       return;
2073     }
2074
2075   if (max_regno > deps->max_reg)
2076     {
2077       deps->reg_last = XRESIZEVEC (struct deps_reg, deps->reg_last,
2078                                    max_regno);
2079       memset (&deps->reg_last[deps->max_reg],
2080               0, (max_regno - deps->max_reg)
2081               * sizeof (struct deps_reg));
2082       deps->max_reg = max_regno;
2083     }
2084 }
2085
2086 /* Extends REG_INFO_P if needed.  */
2087 void
2088 maybe_extend_reg_info_p (void)
2089 {
2090   /* Extend REG_INFO_P, if needed.  */
2091   if ((unsigned int)max_regno - 1 >= reg_info_p_size)
2092     {
2093       size_t new_reg_info_p_size = max_regno + 128;
2094
2095       gcc_assert (!reload_completed && sel_sched_p ());
2096
2097       reg_info_p = (struct reg_info_t *) xrecalloc (reg_info_p,
2098                                                     new_reg_info_p_size,
2099                                                     reg_info_p_size,
2100                                                     sizeof (*reg_info_p));
2101       reg_info_p_size = new_reg_info_p_size;
2102     }
2103 }
2104
2105 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2106    The type of the reference is specified by REF and can be SET,
2107    CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE.  */
2108
2109 static void
2110 sched_analyze_reg (struct deps *deps, int regno, enum machine_mode mode,
2111                    enum rtx_code ref, rtx insn)
2112 {
2113   /* We could emit new pseudos in renaming.  Extend the reg structures.  */
2114   if (!reload_completed && sel_sched_p ()
2115       && (regno >= max_reg_num () - 1 || regno >= deps->max_reg))
2116     extend_deps_reg_info (deps, regno);
2117
2118   maybe_extend_reg_info_p ();
2119
2120   /* A hard reg in a wide mode may really be multiple registers.
2121      If so, mark all of them just like the first.  */
2122   if (regno < FIRST_PSEUDO_REGISTER)
2123     {
2124       int i = hard_regno_nregs[regno][mode];
2125       if (ref == SET)
2126         {
2127           while (--i >= 0)
2128             note_reg_set (regno + i);
2129         }
2130       else if (ref == USE)
2131         {
2132           while (--i >= 0)
2133             note_reg_use (regno + i);
2134         }
2135       else
2136         {
2137           while (--i >= 0)
2138             note_reg_clobber (regno + i);
2139         }
2140     }
2141
2142   /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2143      it does not reload.  Ignore these as they have served their
2144      purpose already.  */
2145   else if (regno >= deps->max_reg)
2146     {
2147       enum rtx_code code = GET_CODE (PATTERN (insn));
2148       gcc_assert (code == USE || code == CLOBBER);
2149     }
2150
2151   else
2152     {
2153       if (ref == SET)
2154         note_reg_set (regno);
2155       else if (ref == USE)
2156         note_reg_use (regno);
2157       else
2158         note_reg_clobber (regno);
2159
2160       /* Pseudos that are REG_EQUIV to something may be replaced
2161          by that during reloading.  We need only add dependencies for
2162         the address in the REG_EQUIV note.  */
2163       if (!reload_completed && get_reg_known_equiv_p (regno))
2164         {
2165           rtx t = get_reg_known_value (regno);
2166           if (MEM_P (t))
2167             sched_analyze_2 (deps, XEXP (t, 0), insn);
2168         }
2169
2170       /* Don't let it cross a call after scheduling if it doesn't
2171          already cross one.  */
2172       if (REG_N_CALLS_CROSSED (regno) == 0)
2173         {
2174           if (!deps->readonly && ref == USE && !DEBUG_INSN_P (insn))
2175             deps->sched_before_next_call
2176               = alloc_INSN_LIST (insn, deps->sched_before_next_call);
2177           else
2178             add_dependence_list (insn, deps->last_function_call, 1,
2179                                  REG_DEP_ANTI);
2180         }
2181     }
2182 }
2183
2184 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2185    rtx, X, creating all dependencies generated by the write to the
2186    destination of X, and reads of everything mentioned.  */
2187
2188 static void
2189 sched_analyze_1 (struct deps *deps, rtx x, rtx insn)
2190 {
2191   rtx dest = XEXP (x, 0);
2192   enum rtx_code code = GET_CODE (x);
2193   bool cslr_p = can_start_lhs_rhs_p;
2194
2195   can_start_lhs_rhs_p = false;
2196
2197   gcc_assert (dest);
2198   if (dest == 0)
2199     return;
2200
2201   if (cslr_p && sched_deps_info->start_lhs)
2202     sched_deps_info->start_lhs (dest);
2203
2204   if (GET_CODE (dest) == PARALLEL)
2205     {
2206       int i;
2207
2208       for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
2209         if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
2210           sched_analyze_1 (deps,
2211                            gen_rtx_CLOBBER (VOIDmode,
2212                                             XEXP (XVECEXP (dest, 0, i), 0)),
2213                            insn);
2214
2215       if (cslr_p && sched_deps_info->finish_lhs)
2216         sched_deps_info->finish_lhs ();
2217
2218       if (code == SET)
2219         {
2220           can_start_lhs_rhs_p = cslr_p;
2221
2222           sched_analyze_2 (deps, SET_SRC (x), insn);
2223
2224           can_start_lhs_rhs_p = false;
2225         }
2226
2227       return;
2228     }
2229
2230   while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
2231          || GET_CODE (dest) == ZERO_EXTRACT)
2232     {
2233       if (GET_CODE (dest) == STRICT_LOW_PART
2234          || GET_CODE (dest) == ZERO_EXTRACT
2235          || df_read_modify_subreg_p (dest))
2236         {
2237           /* These both read and modify the result.  We must handle
2238              them as writes to get proper dependencies for following
2239              instructions.  We must handle them as reads to get proper
2240              dependencies from this to previous instructions.
2241              Thus we need to call sched_analyze_2.  */
2242
2243           sched_analyze_2 (deps, XEXP (dest, 0), insn);
2244         }
2245       if (GET_CODE (dest) == ZERO_EXTRACT)
2246         {
2247           /* The second and third arguments are values read by this insn.  */
2248           sched_analyze_2 (deps, XEXP (dest, 1), insn);
2249           sched_analyze_2 (deps, XEXP (dest, 2), insn);
2250         }
2251       dest = XEXP (dest, 0);
2252     }
2253
2254   if (REG_P (dest))
2255     {
2256       int regno = REGNO (dest);
2257       enum machine_mode mode = GET_MODE (dest);
2258
2259       sched_analyze_reg (deps, regno, mode, code, insn);
2260
2261 #ifdef STACK_REGS
2262       /* Treat all writes to a stack register as modifying the TOS.  */
2263       if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2264         {
2265           int nregs;
2266
2267           /* Avoid analyzing the same register twice.  */
2268           if (regno != FIRST_STACK_REG)
2269             sched_analyze_reg (deps, FIRST_STACK_REG, mode, code, insn);
2270
2271           nregs = hard_regno_nregs[FIRST_STACK_REG][mode];
2272           while (--nregs >= 0)
2273             SET_HARD_REG_BIT (implicit_reg_pending_uses,
2274                               FIRST_STACK_REG + nregs);
2275         }
2276 #endif
2277     }
2278   else if (MEM_P (dest))
2279     {
2280       /* Writing memory.  */
2281       rtx t = dest;
2282
2283       if (sched_deps_info->use_cselib)
2284         {
2285           enum machine_mode address_mode
2286             = targetm.addr_space.address_mode (MEM_ADDR_SPACE (dest));
2287
2288           t = shallow_copy_rtx (dest);
2289           cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1, insn);
2290           XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
2291         }
2292       t = canon_rtx (t);
2293
2294       /* Pending lists can't get larger with a readonly context.  */
2295       if (!deps->readonly
2296           && ((deps->pending_read_list_length + deps->pending_write_list_length)
2297               > MAX_PENDING_LIST_LENGTH))
2298         {
2299           /* Flush all pending reads and writes to prevent the pending lists
2300              from getting any larger.  Insn scheduling runs too slowly when
2301              these lists get long.  When compiling GCC with itself,
2302              this flush occurs 8 times for sparc, and 10 times for m88k using
2303              the default value of 32.  */
2304           flush_pending_lists (deps, insn, false, true);
2305         }
2306       else
2307         {
2308           rtx pending, pending_mem;
2309
2310           pending = deps->pending_read_insns;
2311           pending_mem = deps->pending_read_mems;
2312           while (pending)
2313             {
2314               if (anti_dependence (XEXP (pending_mem, 0), t)
2315                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2316                 note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2317                               DEP_ANTI);
2318
2319               pending = XEXP (pending, 1);
2320               pending_mem = XEXP (pending_mem, 1);
2321             }
2322
2323           pending = deps->pending_write_insns;
2324           pending_mem = deps->pending_write_mems;
2325           while (pending)
2326             {
2327               if (output_dependence (XEXP (pending_mem, 0), t)
2328                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2329                 note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2330                               DEP_OUTPUT);
2331
2332               pending = XEXP (pending, 1);
2333               pending_mem = XEXP (pending_mem, 1);
2334             }
2335
2336           add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2337                                REG_DEP_ANTI);
2338
2339           if (!deps->readonly)
2340             add_insn_mem_dependence (deps, false, insn, dest);
2341         }
2342       sched_analyze_2 (deps, XEXP (dest, 0), insn);
2343     }
2344
2345   if (cslr_p && sched_deps_info->finish_lhs)
2346     sched_deps_info->finish_lhs ();
2347
2348   /* Analyze reads.  */
2349   if (GET_CODE (x) == SET)
2350     {
2351       can_start_lhs_rhs_p = cslr_p;
2352
2353       sched_analyze_2 (deps, SET_SRC (x), insn);
2354
2355       can_start_lhs_rhs_p = false;
2356     }
2357 }
2358
2359 /* Analyze the uses of memory and registers in rtx X in INSN.  */
2360 static void
2361 sched_analyze_2 (struct deps *deps, rtx x, rtx insn)
2362 {
2363   int i;
2364   int j;
2365   enum rtx_code code;
2366   const char *fmt;
2367   bool cslr_p = can_start_lhs_rhs_p;
2368
2369   can_start_lhs_rhs_p = false;
2370
2371   gcc_assert (x);
2372   if (x == 0)
2373     return;
2374
2375   if (cslr_p && sched_deps_info->start_rhs)
2376     sched_deps_info->start_rhs (x);
2377
2378   code = GET_CODE (x);
2379
2380   switch (code)
2381     {
2382     case CONST_INT:
2383     case CONST_DOUBLE:
2384     case CONST_FIXED:
2385     case CONST_VECTOR:
2386     case SYMBOL_REF:
2387     case CONST:
2388     case LABEL_REF:
2389       /* Ignore constants.  */
2390       if (cslr_p && sched_deps_info->finish_rhs)
2391         sched_deps_info->finish_rhs ();
2392
2393       return;
2394
2395 #ifdef HAVE_cc0
2396     case CC0:
2397       /* User of CC0 depends on immediately preceding insn.  */
2398       SCHED_GROUP_P (insn) = 1;
2399        /* Don't move CC0 setter to another block (it can set up the
2400         same flag for previous CC0 users which is safe).  */
2401       CANT_MOVE (prev_nonnote_insn (insn)) = 1;
2402
2403       if (cslr_p && sched_deps_info->finish_rhs)
2404         sched_deps_info->finish_rhs ();
2405
2406       return;
2407 #endif
2408
2409     case REG:
2410       {
2411         int regno = REGNO (x);
2412         enum machine_mode mode = GET_MODE (x);
2413
2414         sched_analyze_reg (deps, regno, mode, USE, insn);
2415
2416 #ifdef STACK_REGS
2417       /* Treat all reads of a stack register as modifying the TOS.  */
2418       if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2419         {
2420           /* Avoid analyzing the same register twice.  */
2421           if (regno != FIRST_STACK_REG)
2422             sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
2423           sched_analyze_reg (deps, FIRST_STACK_REG, mode, SET, insn);
2424         }
2425 #endif
2426
2427         if (cslr_p && sched_deps_info->finish_rhs)
2428           sched_deps_info->finish_rhs ();
2429
2430         return;
2431       }
2432
2433     case MEM:
2434       {
2435         /* Reading memory.  */
2436         rtx u;
2437         rtx pending, pending_mem;
2438         rtx t = x;
2439
2440         if (sched_deps_info->use_cselib)
2441           {
2442             enum machine_mode address_mode
2443               = targetm.addr_space.address_mode (MEM_ADDR_SPACE (t));
2444
2445             t = shallow_copy_rtx (t);
2446             cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1, insn);
2447             XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
2448           }
2449
2450         if (!DEBUG_INSN_P (insn))
2451           {
2452             t = canon_rtx (t);
2453             pending = deps->pending_read_insns;
2454             pending_mem = deps->pending_read_mems;
2455             while (pending)
2456               {
2457                 if (read_dependence (XEXP (pending_mem, 0), t)
2458                     && ! sched_insns_conditions_mutex_p (insn,
2459                                                          XEXP (pending, 0)))
2460                   note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2461                                 DEP_ANTI);
2462
2463                 pending = XEXP (pending, 1);
2464                 pending_mem = XEXP (pending_mem, 1);
2465               }
2466
2467             pending = deps->pending_write_insns;
2468             pending_mem = deps->pending_write_mems;
2469             while (pending)
2470               {
2471                 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
2472                                      t, rtx_varies_p)
2473                     && ! sched_insns_conditions_mutex_p (insn,
2474                                                          XEXP (pending, 0)))
2475                   note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2476                                 sched_deps_info->generate_spec_deps
2477                                 ? BEGIN_DATA | DEP_TRUE : DEP_TRUE);
2478
2479                 pending = XEXP (pending, 1);
2480                 pending_mem = XEXP (pending_mem, 1);
2481               }
2482
2483             for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
2484               {
2485                 if (! JUMP_P (XEXP (u, 0)))
2486                   add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
2487                 else if (deps_may_trap_p (x))
2488                   {
2489                     if ((sched_deps_info->generate_spec_deps)
2490                         && sel_sched_p () && (spec_info->mask & BEGIN_CONTROL))
2491                       {
2492                         ds_t ds = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
2493                                                 MAX_DEP_WEAK);
2494
2495                         note_dep (XEXP (u, 0), ds);
2496                       }
2497                     else
2498                       add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
2499                   }
2500               }
2501           }
2502
2503         /* Always add these dependencies to pending_reads, since
2504            this insn may be followed by a write.  */
2505         if (!deps->readonly)
2506           add_insn_mem_dependence (deps, true, insn, x);
2507
2508         sched_analyze_2 (deps, XEXP (x, 0), insn);
2509
2510         if (cslr_p && sched_deps_info->finish_rhs)
2511           sched_deps_info->finish_rhs ();
2512
2513         return;
2514       }
2515
2516     /* Force pending stores to memory in case a trap handler needs them.  */
2517     case TRAP_IF:
2518       flush_pending_lists (deps, insn, true, false);
2519       break;
2520
2521     case PREFETCH:
2522       if (PREFETCH_SCHEDULE_BARRIER_P (x))
2523         reg_pending_barrier = TRUE_BARRIER;
2524       break;
2525
2526     case UNSPEC_VOLATILE:
2527       flush_pending_lists (deps, insn, true, true);
2528       /* FALLTHRU */
2529
2530     case ASM_OPERANDS:
2531     case ASM_INPUT:
2532       {
2533         /* Traditional and volatile asm instructions must be considered to use
2534            and clobber all hard registers, all pseudo-registers and all of
2535            memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
2536
2537            Consider for instance a volatile asm that changes the fpu rounding
2538            mode.  An insn should not be moved across this even if it only uses
2539            pseudo-regs because it might give an incorrectly rounded result.  */
2540         if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
2541           reg_pending_barrier = TRUE_BARRIER;
2542
2543         /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2544            We can not just fall through here since then we would be confused
2545            by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2546            traditional asms unlike their normal usage.  */
2547
2548         if (code == ASM_OPERANDS)
2549           {
2550             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
2551               sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
2552
2553             if (cslr_p && sched_deps_info->finish_rhs)
2554               sched_deps_info->finish_rhs ();
2555
2556             return;
2557           }
2558         break;
2559       }
2560
2561     case PRE_DEC:
2562     case POST_DEC:
2563     case PRE_INC:
2564     case POST_INC:
2565       /* These both read and modify the result.  We must handle them as writes
2566          to get proper dependencies for following instructions.  We must handle
2567          them as reads to get proper dependencies from this to previous
2568          instructions.  Thus we need to pass them to both sched_analyze_1
2569          and sched_analyze_2.  We must call sched_analyze_2 first in order
2570          to get the proper antecedent for the read.  */
2571       sched_analyze_2 (deps, XEXP (x, 0), insn);
2572       sched_analyze_1 (deps, x, insn);
2573
2574       if (cslr_p && sched_deps_info->finish_rhs)
2575         sched_deps_info->finish_rhs ();
2576
2577       return;
2578
2579     case POST_MODIFY:
2580     case PRE_MODIFY:
2581       /* op0 = op0 + op1 */
2582       sched_analyze_2 (deps, XEXP (x, 0), insn);
2583       sched_analyze_2 (deps, XEXP (x, 1), insn);
2584       sched_analyze_1 (deps, x, insn);
2585
2586       if (cslr_p && sched_deps_info->finish_rhs)
2587         sched_deps_info->finish_rhs ();
2588
2589       return;
2590
2591     default:
2592       break;
2593     }
2594
2595   /* Other cases: walk the insn.  */
2596   fmt = GET_RTX_FORMAT (code);
2597   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2598     {
2599       if (fmt[i] == 'e')
2600         sched_analyze_2 (deps, XEXP (x, i), insn);
2601       else if (fmt[i] == 'E')
2602         for (j = 0; j < XVECLEN (x, i); j++)
2603           sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
2604     }
2605
2606   if (cslr_p && sched_deps_info->finish_rhs)
2607     sched_deps_info->finish_rhs ();
2608 }
2609
2610 /* Analyze an INSN with pattern X to find all dependencies.  */
2611 static void
2612 sched_analyze_insn (struct deps *deps, rtx x, rtx insn)
2613 {
2614   RTX_CODE code = GET_CODE (x);
2615   rtx link;
2616   unsigned i;
2617   reg_set_iterator rsi;
2618
2619   if (! reload_completed)
2620     {
2621       HARD_REG_SET temp;
2622
2623       extract_insn (insn);
2624       preprocess_constraints ();
2625       ira_implicitly_set_insn_hard_regs (&temp);
2626       AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
2627       IOR_HARD_REG_SET (implicit_reg_pending_clobbers, temp);
2628     }
2629
2630   can_start_lhs_rhs_p = (NONJUMP_INSN_P (insn)
2631                          && code == SET);
2632
2633   if (may_trap_p (x))
2634     /* Avoid moving trapping instructions accross function calls that might
2635        not always return.  */
2636     add_dependence_list (insn, deps->last_function_call_may_noreturn,
2637                          1, REG_DEP_ANTI);
2638
2639   if (code == COND_EXEC)
2640     {
2641       sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
2642
2643       /* ??? Should be recording conditions so we reduce the number of
2644          false dependencies.  */
2645       x = COND_EXEC_CODE (x);
2646       code = GET_CODE (x);
2647     }
2648   if (code == SET || code == CLOBBER)
2649     {
2650       sched_analyze_1 (deps, x, insn);
2651
2652       /* Bare clobber insns are used for letting life analysis, reg-stack
2653          and others know that a value is dead.  Depend on the last call
2654          instruction so that reg-stack won't get confused.  */
2655       if (code == CLOBBER)
2656         add_dependence_list (insn, deps->last_function_call, 1,
2657                              REG_DEP_OUTPUT);
2658     }
2659   else if (code == PARALLEL)
2660     {
2661       for (i = XVECLEN (x, 0); i--;)
2662         {
2663           rtx sub = XVECEXP (x, 0, i);
2664           code = GET_CODE (sub);
2665
2666           if (code == COND_EXEC)
2667             {
2668               sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
2669               sub = COND_EXEC_CODE (sub);
2670               code = GET_CODE (sub);
2671             }
2672           if (code == SET || code == CLOBBER)
2673             sched_analyze_1 (deps, sub, insn);
2674           else
2675             sched_analyze_2 (deps, sub, insn);
2676         }
2677     }
2678   else
2679     sched_analyze_2 (deps, x, insn);
2680
2681   /* Mark registers CLOBBERED or used by called function.  */
2682   if (CALL_P (insn))
2683     {
2684       for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
2685         {
2686           if (GET_CODE (XEXP (link, 0)) == CLOBBER)
2687             sched_analyze_1 (deps, XEXP (link, 0), insn);
2688           else
2689             sched_analyze_2 (deps, XEXP (link, 0), insn);
2690         }
2691       if (find_reg_note (insn, REG_SETJMP, NULL))
2692         reg_pending_barrier = MOVE_BARRIER;
2693     }
2694
2695   if (JUMP_P (insn))
2696     {
2697       rtx next;
2698       next = next_nonnote_insn (insn);
2699       while (next && DEBUG_INSN_P (next))
2700         next = next_nonnote_insn (next);
2701       if (next && BARRIER_P (next))
2702         reg_pending_barrier = MOVE_BARRIER;
2703       else
2704         {
2705           rtx pending, pending_mem;
2706
2707           if (sched_deps_info->compute_jump_reg_dependencies)
2708             {
2709               regset_head tmp_uses, tmp_sets;
2710               INIT_REG_SET (&tmp_uses);
2711               INIT_REG_SET (&tmp_sets);
2712
2713               (*sched_deps_info->compute_jump_reg_dependencies)
2714                 (insn, &deps->reg_conditional_sets, &tmp_uses, &tmp_sets);
2715               /* Make latency of jump equal to 0 by using anti-dependence.  */
2716               EXECUTE_IF_SET_IN_REG_SET (&tmp_uses, 0, i, rsi)
2717                 {
2718                   struct deps_reg *reg_last = &deps->reg_last[i];
2719                   add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
2720                   add_dependence_list (insn, reg_last->implicit_sets,
2721                                        0, REG_DEP_ANTI);
2722                   add_dependence_list (insn, reg_last->clobbers, 0,
2723                                        REG_DEP_ANTI);
2724
2725                   if (!deps->readonly)
2726                     {
2727                       reg_last->uses_length++;
2728                       reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
2729                     }
2730                 }
2731               IOR_REG_SET (reg_pending_sets, &tmp_sets);
2732
2733               CLEAR_REG_SET (&tmp_uses);
2734               CLEAR_REG_SET (&tmp_sets);
2735             }
2736
2737           /* All memory writes and volatile reads must happen before the
2738              jump.  Non-volatile reads must happen before the jump iff
2739              the result is needed by the above register used mask.  */
2740
2741           pending = deps->pending_write_insns;
2742           pending_mem = deps->pending_write_mems;
2743           while (pending)
2744             {
2745               if (! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2746                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
2747               pending = XEXP (pending, 1);
2748               pending_mem = XEXP (pending_mem, 1);
2749             }
2750
2751           pending = deps->pending_read_insns;
2752           pending_mem = deps->pending_read_mems;
2753           while (pending)
2754             {
2755               if (MEM_VOLATILE_P (XEXP (pending_mem, 0))
2756                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2757                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
2758               pending = XEXP (pending, 1);
2759               pending_mem = XEXP (pending_mem, 1);
2760             }
2761
2762           add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2763                                REG_DEP_ANTI);
2764         }
2765     }
2766
2767   /* If this instruction can throw an exception, then moving it changes
2768      where block boundaries fall.  This is mighty confusing elsewhere.
2769      Therefore, prevent such an instruction from being moved.  Same for
2770      non-jump instructions that define block boundaries.
2771      ??? Unclear whether this is still necessary in EBB mode.  If not,
2772      add_branch_dependences should be adjusted for RGN mode instead.  */
2773   if (((CALL_P (insn) || JUMP_P (insn)) && can_throw_internal (insn))
2774       || (NONJUMP_INSN_P (insn) && control_flow_insn_p (insn)))
2775     reg_pending_barrier = MOVE_BARRIER;
2776
2777   if (sched_pressure_p)
2778     {
2779       setup_insn_reg_uses (deps, insn);
2780       setup_insn_reg_pressure_info (insn);
2781     }
2782
2783   /* Add register dependencies for insn.  */
2784   if (DEBUG_INSN_P (insn))
2785     {
2786       rtx prev = deps->last_debug_insn;
2787       rtx u;
2788
2789       if (!deps->readonly)
2790         deps->last_debug_insn = insn;
2791
2792       if (prev)
2793         add_dependence (insn, prev, REG_DEP_ANTI);
2794
2795       add_dependence_list (insn, deps->last_function_call, 1,
2796                            REG_DEP_ANTI);
2797
2798       for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
2799         if (! JUMP_P (XEXP (u, 0))
2800             || !sel_sched_p ())
2801           add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
2802
2803       EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
2804         {
2805           struct deps_reg *reg_last = &deps->reg_last[i];
2806           add_dependence_list (insn, reg_last->sets, 1, REG_DEP_ANTI);
2807           add_dependence_list (insn, reg_last->clobbers, 1, REG_DEP_ANTI);
2808
2809           if (!deps->readonly)
2810             reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
2811         }
2812       CLEAR_REG_SET (reg_pending_uses);
2813
2814       /* Quite often, a debug insn will refer to stuff in the
2815          previous instruction, but the reason we want this
2816          dependency here is to make sure the scheduler doesn't
2817          gratuitously move a debug insn ahead.  This could dirty
2818          DF flags and cause additional analysis that wouldn't have
2819          occurred in compilation without debug insns, and such
2820          additional analysis can modify the generated code.  */
2821       prev = PREV_INSN (insn);
2822
2823       if (prev && NONDEBUG_INSN_P (prev))
2824         add_dependence (insn, prev, REG_DEP_ANTI);
2825     }
2826   else
2827     {
2828       EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
2829         {
2830           struct deps_reg *reg_last = &deps->reg_last[i];
2831           add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
2832           add_dependence_list (insn, reg_last->implicit_sets, 0, REG_DEP_ANTI);
2833           add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
2834
2835           if (!deps->readonly)
2836             {
2837               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
2838               reg_last->uses_length++;
2839             }
2840         }
2841
2842       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2843         if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i))
2844           {
2845             struct deps_reg *reg_last = &deps->reg_last[i];
2846             add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
2847             add_dependence_list (insn, reg_last->implicit_sets, 0,
2848                                  REG_DEP_ANTI);
2849             add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
2850
2851             if (!deps->readonly)
2852               {
2853                 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
2854                 reg_last->uses_length++;
2855               }
2856           }
2857
2858       /* If the current insn is conditional, we can't free any
2859          of the lists.  */
2860       if (sched_has_condition_p (insn))
2861         {
2862           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
2863             {
2864               struct deps_reg *reg_last = &deps->reg_last[i];
2865               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
2866               add_dependence_list (insn, reg_last->implicit_sets, 0,
2867                                    REG_DEP_ANTI);
2868               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
2869
2870               if (!deps->readonly)
2871                 {
2872                   reg_last->clobbers
2873                     = alloc_INSN_LIST (insn, reg_last->clobbers);
2874                   reg_last->clobbers_length++;
2875                 }
2876             }
2877           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
2878             {
2879               struct deps_reg *reg_last = &deps->reg_last[i];
2880               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
2881               add_dependence_list (insn, reg_last->implicit_sets, 0,
2882                                    REG_DEP_ANTI);
2883               add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT);
2884               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
2885
2886               if (!deps->readonly)
2887                 {
2888                   reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
2889                   SET_REGNO_REG_SET (&deps->reg_conditional_sets, i);
2890                 }
2891             }
2892         }
2893       else
2894         {
2895           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
2896             {
2897               struct deps_reg *reg_last = &deps->reg_last[i];
2898               if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
2899                   || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
2900                 {
2901                   add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
2902                                                 REG_DEP_OUTPUT);
2903                   add_dependence_list_and_free (deps, insn,
2904                                                 &reg_last->implicit_sets, 0,
2905                                                 REG_DEP_ANTI);
2906                   add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
2907                                                 REG_DEP_ANTI);
2908                   add_dependence_list_and_free
2909                     (deps, insn, &reg_last->clobbers, 0, REG_DEP_OUTPUT);
2910
2911                   if (!deps->readonly)
2912                     {
2913                       reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
2914                       reg_last->clobbers_length = 0;
2915                       reg_last->uses_length = 0;
2916                     }
2917                 }
2918               else
2919                 {
2920                   add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
2921                   add_dependence_list (insn, reg_last->implicit_sets, 0,
2922                                        REG_DEP_ANTI);
2923                   add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
2924                 }
2925
2926               if (!deps->readonly)
2927                 {
2928                   reg_last->clobbers_length++;
2929                   reg_last->clobbers
2930                     = alloc_INSN_LIST (insn, reg_last->clobbers);
2931                 }
2932             }
2933           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
2934             {
2935               struct deps_reg *reg_last = &deps->reg_last[i];
2936
2937               add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
2938                                             REG_DEP_OUTPUT);
2939               add_dependence_list_and_free (deps, insn,
2940                                             &reg_last->implicit_sets,
2941                                             0, REG_DEP_ANTI);
2942               add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
2943                                             REG_DEP_OUTPUT);
2944               add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
2945                                             REG_DEP_ANTI);
2946
2947               if (!deps->readonly)
2948                 {
2949                   reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
2950                   reg_last->uses_length = 0;
2951                   reg_last->clobbers_length = 0;
2952                   CLEAR_REGNO_REG_SET (&deps->reg_conditional_sets, i);
2953                 }
2954             }
2955         }
2956     }
2957
2958   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2959     if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
2960       {
2961         struct deps_reg *reg_last = &deps->reg_last[i];
2962         add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
2963         add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI);
2964         add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
2965
2966         if (!deps->readonly)
2967           reg_last->implicit_sets
2968             = alloc_INSN_LIST (insn, reg_last->implicit_sets);
2969       }
2970
2971   if (!deps->readonly)
2972     {
2973       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
2974       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
2975       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
2976       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2977         if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i)
2978             || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
2979           SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
2980
2981       /* Set up the pending barrier found.  */
2982       deps->last_reg_pending_barrier = reg_pending_barrier;
2983     }
2984
2985   CLEAR_REG_SET (reg_pending_uses);
2986   CLEAR_REG_SET (reg_pending_clobbers);
2987   CLEAR_REG_SET (reg_pending_sets);
2988   CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
2989   CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
2990
2991   /* Add dependencies if a scheduling barrier was found.  */
2992   if (reg_pending_barrier)
2993     {
2994       /* In the case of barrier the most added dependencies are not
2995          real, so we use anti-dependence here.  */
2996       if (sched_has_condition_p (insn))
2997         {
2998           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
2999             {
3000               struct deps_reg *reg_last = &deps->reg_last[i];
3001               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
3002               add_dependence_list (insn, reg_last->sets, 0,
3003                                    reg_pending_barrier == TRUE_BARRIER
3004                                    ? REG_DEP_TRUE : REG_DEP_ANTI);
3005               add_dependence_list (insn, reg_last->implicit_sets, 0,
3006                                    REG_DEP_ANTI);
3007               add_dependence_list (insn, reg_last->clobbers, 0,
3008                                    reg_pending_barrier == TRUE_BARRIER
3009                                    ? REG_DEP_TRUE : REG_DEP_ANTI);
3010             }
3011         }
3012       else
3013         {
3014           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3015             {
3016               struct deps_reg *reg_last = &deps->reg_last[i];
3017               add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3018                                             REG_DEP_ANTI);
3019               add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3020                                             reg_pending_barrier == TRUE_BARRIER
3021                                             ? REG_DEP_TRUE : REG_DEP_ANTI);
3022               add_dependence_list_and_free (deps, insn,
3023                                             &reg_last->implicit_sets, 0,
3024                                             REG_DEP_ANTI);
3025               add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3026                                             reg_pending_barrier == TRUE_BARRIER
3027                                             ? REG_DEP_TRUE : REG_DEP_ANTI);
3028
3029               if (!deps->readonly)
3030                 {
3031                   reg_last->uses_length = 0;
3032                   reg_last->clobbers_length = 0;
3033                 }
3034             }
3035         }
3036
3037       if (!deps->readonly)
3038         for (i = 0; i < (unsigned)deps->max_reg; i++)
3039           {
3040             struct deps_reg *reg_last = &deps->reg_last[i];
3041             reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3042             SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3043           }
3044
3045       /* Flush pending lists on jumps, but not on speculative checks.  */
3046       if (JUMP_P (insn) && !(sel_sched_p ()
3047                              && sel_insn_is_speculation_check (insn)))
3048         flush_pending_lists (deps, insn, true, true);
3049
3050       if (!deps->readonly)
3051         CLEAR_REG_SET (&deps->reg_conditional_sets);
3052       reg_pending_barrier = NOT_A_BARRIER;
3053     }
3054
3055   /* If a post-call group is still open, see if it should remain so.
3056      This insn must be a simple move of a hard reg to a pseudo or
3057      vice-versa.
3058
3059      We must avoid moving these insns for correctness on
3060      SMALL_REGISTER_CLASS machines, and for special registers like
3061      PIC_OFFSET_TABLE_REGNUM.  For simplicity, extend this to all
3062      hard regs for all targets.  */
3063
3064   if (deps->in_post_call_group_p)
3065     {
3066       rtx tmp, set = single_set (insn);
3067       int src_regno, dest_regno;
3068
3069       if (set == NULL)
3070         {
3071           if (DEBUG_INSN_P (insn))
3072             /* We don't want to mark debug insns as part of the same
3073                sched group.  We know they really aren't, but if we use
3074                debug insns to tell that a call group is over, we'll
3075                get different code if debug insns are not there and
3076                instructions that follow seem like they should be part
3077                of the call group.
3078
3079                Also, if we did, fixup_sched_groups() would move the
3080                deps of the debug insn to the call insn, modifying
3081                non-debug post-dependency counts of the debug insn
3082                dependencies and otherwise messing with the scheduling
3083                order.
3084
3085                Instead, let such debug insns be scheduled freely, but
3086                keep the call group open in case there are insns that
3087                should be part of it afterwards.  Since we grant debug
3088                insns higher priority than even sched group insns, it
3089                will all turn out all right.  */
3090             goto debug_dont_end_call_group;
3091           else
3092             goto end_call_group;
3093         }
3094
3095       tmp = SET_DEST (set);
3096       if (GET_CODE (tmp) == SUBREG)
3097         tmp = SUBREG_REG (tmp);
3098       if (REG_P (tmp))
3099         dest_regno = REGNO (tmp);
3100       else
3101         goto end_call_group;
3102
3103       tmp = SET_SRC (set);
3104       if (GET_CODE (tmp) == SUBREG)
3105         tmp = SUBREG_REG (tmp);
3106       if ((GET_CODE (tmp) == PLUS
3107            || GET_CODE (tmp) == MINUS)
3108           && REG_P (XEXP (tmp, 0))
3109           && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
3110           && dest_regno == STACK_POINTER_REGNUM)
3111         src_regno = STACK_POINTER_REGNUM;
3112       else if (REG_P (tmp))
3113         src_regno = REGNO (tmp);
3114       else
3115         goto end_call_group;
3116
3117       if (src_regno < FIRST_PSEUDO_REGISTER
3118           || dest_regno < FIRST_PSEUDO_REGISTER)
3119         {
3120           if (!deps->readonly
3121               && deps->in_post_call_group_p == post_call_initial)
3122             deps->in_post_call_group_p = post_call;
3123
3124           if (!sel_sched_p () || sched_emulate_haifa_p)
3125             {
3126               SCHED_GROUP_P (insn) = 1;
3127               CANT_MOVE (insn) = 1;
3128             }
3129         }
3130       else
3131         {
3132         end_call_group:
3133           if (!deps->readonly)
3134             deps->in_post_call_group_p = not_post_call;
3135         }
3136     }
3137
3138  debug_dont_end_call_group:
3139   if ((current_sched_info->flags & DO_SPECULATION)
3140       && !sched_insn_is_legitimate_for_speculation_p (insn, 0))
3141     /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3142        be speculated.  */
3143     {
3144       if (sel_sched_p ())
3145         sel_mark_hard_insn (insn);
3146       else
3147         {
3148           sd_iterator_def sd_it;
3149           dep_t dep;
3150
3151           for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3152                sd_iterator_cond (&sd_it, &dep);)
3153             change_spec_dep_to_hard (sd_it);
3154         }
3155     }
3156 }
3157
3158 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3159    longjmp, loop forever, ...).  */
3160 static bool
3161 call_may_noreturn_p (rtx insn)
3162 {
3163   rtx call;
3164
3165   /* const or pure calls that aren't looping will always return.  */
3166   if (RTL_CONST_OR_PURE_CALL_P (insn)
3167       && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))
3168     return false;
3169
3170   call = PATTERN (insn);
3171   if (GET_CODE (call) == PARALLEL)
3172     call = XVECEXP (call, 0, 0);
3173   if (GET_CODE (call) == SET)
3174     call = SET_SRC (call);
3175   if (GET_CODE (call) == CALL
3176       && MEM_P (XEXP (call, 0))
3177       && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
3178     {
3179       rtx symbol = XEXP (XEXP (call, 0), 0);
3180       if (SYMBOL_REF_DECL (symbol)
3181           && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
3182         {
3183           if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
3184               == BUILT_IN_NORMAL)
3185             switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol)))
3186               {
3187               case BUILT_IN_BCMP:
3188               case BUILT_IN_BCOPY:
3189               case BUILT_IN_BZERO:
3190               case BUILT_IN_INDEX:
3191               case BUILT_IN_MEMCHR:
3192               case BUILT_IN_MEMCMP:
3193               case BUILT_IN_MEMCPY:
3194               case BUILT_IN_MEMMOVE:
3195               case BUILT_IN_MEMPCPY:
3196               case BUILT_IN_MEMSET:
3197               case BUILT_IN_RINDEX:
3198               case BUILT_IN_STPCPY:
3199               case BUILT_IN_STPNCPY:
3200               case BUILT_IN_STRCAT:
3201               case BUILT_IN_STRCHR:
3202               case BUILT_IN_STRCMP:
3203               case BUILT_IN_STRCPY:
3204               case BUILT_IN_STRCSPN:
3205               case BUILT_IN_STRLEN:
3206               case BUILT_IN_STRNCAT:
3207               case BUILT_IN_STRNCMP:
3208               case BUILT_IN_STRNCPY:
3209               case BUILT_IN_STRPBRK:
3210               case BUILT_IN_STRRCHR:
3211               case BUILT_IN_STRSPN:
3212               case BUILT_IN_STRSTR:
3213                 /* Assume certain string/memory builtins always return.  */
3214                 return false;
3215               default:
3216                 break;
3217               }
3218         }
3219     }
3220
3221   /* For all other calls assume that they might not always return.  */
3222   return true;
3223 }
3224
3225 /* Analyze INSN with DEPS as a context.  */
3226 void
3227 deps_analyze_insn (struct deps *deps, rtx insn)
3228 {
3229   if (sched_deps_info->start_insn)
3230     sched_deps_info->start_insn (insn);
3231
3232   if (NONJUMP_INSN_P (insn) || DEBUG_INSN_P (insn) || JUMP_P (insn))
3233     {
3234       /* Make each JUMP_INSN (but not a speculative check)
3235          a scheduling barrier for memory references.  */
3236       if (!deps->readonly
3237           && JUMP_P (insn)
3238           && !(sel_sched_p ()
3239                && sel_insn_is_speculation_check (insn)))
3240         {
3241           /* Keep the list a reasonable size.  */
3242           if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
3243             flush_pending_lists (deps, insn, true, true);
3244           else
3245             deps->last_pending_memory_flush
3246               = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
3247         }
3248
3249       sched_analyze_insn (deps, PATTERN (insn), insn);
3250     }
3251   else if (CALL_P (insn))
3252     {
3253       int i;
3254
3255       CANT_MOVE (insn) = 1;
3256
3257       if (find_reg_note (insn, REG_SETJMP, NULL))
3258         {
3259           /* This is setjmp.  Assume that all registers, not just
3260              hard registers, may be clobbered by this call.  */
3261           reg_pending_barrier = MOVE_BARRIER;
3262         }
3263       else
3264         {
3265           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3266             /* A call may read and modify global register variables.  */
3267             if (global_regs[i])
3268               {
3269                 SET_REGNO_REG_SET (reg_pending_sets, i);
3270                 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3271               }
3272           /* Other call-clobbered hard regs may be clobbered.
3273              Since we only have a choice between 'might be clobbered'
3274              and 'definitely not clobbered', we must include all
3275              partly call-clobbered registers here.  */
3276             else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
3277                      || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3278               SET_REGNO_REG_SET (reg_pending_clobbers, i);
3279           /* We don't know what set of fixed registers might be used
3280              by the function, but it is certain that the stack pointer
3281              is among them, but be conservative.  */
3282             else if (fixed_regs[i])
3283               SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3284           /* The frame pointer is normally not used by the function
3285              itself, but by the debugger.  */
3286           /* ??? MIPS o32 is an exception.  It uses the frame pointer
3287              in the macro expansion of jal but does not represent this
3288              fact in the call_insn rtl.  */
3289             else if (i == FRAME_POINTER_REGNUM
3290                      || (i == HARD_FRAME_POINTER_REGNUM
3291                          && (! reload_completed || frame_pointer_needed)))
3292               SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3293         }
3294
3295       /* For each insn which shouldn't cross a call, add a dependence
3296          between that insn and this call insn.  */
3297       add_dependence_list_and_free (deps, insn,
3298                                     &deps->sched_before_next_call, 1,
3299                                     REG_DEP_ANTI);
3300
3301       sched_analyze_insn (deps, PATTERN (insn), insn);
3302
3303       /* If CALL would be in a sched group, then this will violate
3304          convention that sched group insns have dependencies only on the
3305          previous instruction.
3306
3307          Of course one can say: "Hey!  What about head of the sched group?"
3308          And I will answer: "Basic principles (one dep per insn) are always
3309          the same."  */
3310       gcc_assert (!SCHED_GROUP_P (insn));
3311
3312       /* In the absence of interprocedural alias analysis, we must flush
3313          all pending reads and writes, and start new dependencies starting
3314          from here.  But only flush writes for constant calls (which may
3315          be passed a pointer to something we haven't written yet).  */
3316       flush_pending_lists (deps, insn, true, ! RTL_CONST_OR_PURE_CALL_P (insn));
3317
3318       if (!deps->readonly)
3319         {
3320           /* Remember the last function call for limiting lifetimes.  */
3321           free_INSN_LIST_list (&deps->last_function_call);
3322           deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3323
3324           if (call_may_noreturn_p (insn))
3325             {
3326               /* Remember the last function call that might not always return
3327                  normally for limiting moves of trapping insns.  */
3328               free_INSN_LIST_list (&deps->last_function_call_may_noreturn);
3329               deps->last_function_call_may_noreturn
3330                 = alloc_INSN_LIST (insn, NULL_RTX);
3331             }
3332
3333           /* Before reload, begin a post-call group, so as to keep the
3334              lifetimes of hard registers correct.  */
3335           if (! reload_completed)
3336             deps->in_post_call_group_p = post_call;
3337         }
3338     }
3339
3340   if (sched_deps_info->use_cselib)
3341     cselib_process_insn (insn);
3342
3343   /* EH_REGION insn notes can not appear until well after we complete
3344      scheduling.  */
3345   if (NOTE_P (insn))
3346     gcc_assert (NOTE_KIND (insn) != NOTE_INSN_EH_REGION_BEG
3347                 && NOTE_KIND (insn) != NOTE_INSN_EH_REGION_END);
3348
3349   if (sched_deps_info->finish_insn)
3350     sched_deps_info->finish_insn ();
3351
3352   /* Fixup the dependencies in the sched group.  */
3353   if ((NONJUMP_INSN_P (insn) || JUMP_P (insn))
3354       && SCHED_GROUP_P (insn) && !sel_sched_p ())
3355     fixup_sched_groups (insn);
3356 }
3357
3358 /* Initialize DEPS for the new block beginning with HEAD.  */
3359 void
3360 deps_start_bb (struct deps *deps, rtx head)
3361 {
3362   gcc_assert (!deps->readonly);
3363
3364   /* Before reload, if the previous block ended in a call, show that
3365      we are inside a post-call group, so as to keep the lifetimes of
3366      hard registers correct.  */
3367   if (! reload_completed && !LABEL_P (head))
3368     {
3369       rtx insn = prev_nonnote_insn (head);
3370
3371       while (insn && DEBUG_INSN_P (insn))
3372         insn = prev_nonnote_insn (insn);
3373       if (insn && CALL_P (insn))
3374         deps->in_post_call_group_p = post_call_initial;
3375     }
3376 }
3377
3378 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3379    dependencies for each insn.  */
3380 void
3381 sched_analyze (struct deps *deps, rtx head, rtx tail)
3382 {
3383   rtx insn;
3384
3385   if (sched_deps_info->use_cselib)
3386     cselib_init (CSELIB_RECORD_MEMORY);
3387
3388   deps_start_bb (deps, head);
3389
3390   for (insn = head;; insn = NEXT_INSN (insn))
3391     {
3392
3393       if (INSN_P (insn))
3394         {
3395           /* And initialize deps_lists.  */
3396           sd_init_insn (insn);
3397         }
3398
3399       deps_analyze_insn (deps, insn);
3400
3401       if (insn == tail)
3402         {
3403           if (sched_deps_info->use_cselib)
3404             cselib_finish ();
3405           return;
3406         }
3407     }
3408   gcc_unreachable ();
3409 }
3410
3411 /* Helper for sched_free_deps ().
3412    Delete INSN's (RESOLVED_P) backward dependencies.  */
3413 static void
3414 delete_dep_nodes_in_back_deps (rtx insn, bool resolved_p)
3415 {
3416   sd_iterator_def sd_it;
3417   dep_t dep;
3418   sd_list_types_def types;
3419
3420   if (resolved_p)
3421     types = SD_LIST_RES_BACK;
3422   else
3423     types = SD_LIST_BACK;
3424
3425   for (sd_it = sd_iterator_start (insn, types);
3426        sd_iterator_cond (&sd_it, &dep);)
3427     {
3428       dep_link_t link = *sd_it.linkp;
3429       dep_node_t node = DEP_LINK_NODE (link);
3430       deps_list_t back_list;
3431       deps_list_t forw_list;
3432
3433       get_back_and_forw_lists (dep, resolved_p, &back_list, &forw_list);
3434       remove_from_deps_list (link, back_list);
3435       delete_dep_node (node);
3436     }
3437 }
3438
3439 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3440    deps_lists.  */
3441 void
3442 sched_free_deps (rtx head, rtx tail, bool resolved_p)
3443 {
3444   rtx insn;
3445   rtx next_tail = NEXT_INSN (tail);
3446
3447   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3448     if (INSN_P (insn) && INSN_LUID (insn) > 0)
3449       {
3450         /* Clear resolved back deps together with its dep_nodes.  */
3451         delete_dep_nodes_in_back_deps (insn, resolved_p);
3452
3453         /* Clear forward deps and leave the dep_nodes to the
3454            corresponding back_deps list.  */
3455         if (resolved_p)
3456           clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
3457         else
3458           clear_deps_list (INSN_FORW_DEPS (insn));
3459
3460         sd_finish_insn (insn);
3461       }
3462 }
3463 \f
3464 /* Initialize variables for region data dependence analysis.
3465    When LAZY_REG_LAST is true, do not allocate reg_last array
3466    of struct deps immediately.  */
3467
3468 void
3469 init_deps (struct deps *deps, bool lazy_reg_last)
3470 {
3471   int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
3472
3473   deps->max_reg = max_reg;
3474   if (lazy_reg_last)
3475     deps->reg_last = NULL;
3476   else
3477     deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
3478   INIT_REG_SET (&deps->reg_last_in_use);
3479   INIT_REG_SET (&deps->reg_conditional_sets);
3480
3481   deps->pending_read_insns = 0;
3482   deps->pending_read_mems = 0;
3483   deps->pending_write_insns = 0;
3484   deps->pending_write_mems = 0;
3485   deps->pending_read_list_length = 0;
3486   deps->pending_write_list_length = 0;
3487   deps->pending_flush_length = 0;
3488   deps->last_pending_memory_flush = 0;
3489   deps->last_function_call = 0;
3490   deps->last_function_call_may_noreturn = 0;
3491   deps->sched_before_next_call = 0;
3492   deps->in_post_call_group_p = not_post_call;
3493   deps->last_debug_insn = 0;
3494   deps->last_reg_pending_barrier = NOT_A_BARRIER;
3495   deps->readonly = 0;
3496 }
3497
3498 /* Init only reg_last field of DEPS, which was not allocated before as
3499    we inited DEPS lazily.  */
3500 void
3501 init_deps_reg_last (struct deps *deps)
3502 {
3503   gcc_assert (deps && deps->max_reg > 0);
3504   gcc_assert (deps->reg_last == NULL);
3505
3506   deps->reg_last = XCNEWVEC (struct deps_reg, deps->max_reg);
3507 }
3508
3509
3510 /* Free insn lists found in DEPS.  */
3511
3512 void
3513 free_deps (struct deps *deps)
3514 {
3515   unsigned i;
3516   reg_set_iterator rsi;
3517
3518   /* We set max_reg to 0 when this context was already freed.  */
3519   if (deps->max_reg == 0)
3520     {
3521       gcc_assert (deps->reg_last == NULL);
3522       return;
3523     }
3524   deps->max_reg = 0;
3525
3526   free_INSN_LIST_list (&deps->pending_read_insns);
3527   free_EXPR_LIST_list (&deps->pending_read_mems);
3528   free_INSN_LIST_list (&deps->pending_write_insns);
3529   free_EXPR_LIST_list (&deps->pending_write_mems);
3530   free_INSN_LIST_list (&deps->last_pending_memory_flush);
3531
3532   /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3533      times.  For a testcase with 42000 regs and 8000 small basic blocks,
3534      this loop accounted for nearly 60% (84 sec) of the total -O2 runtime.  */
3535   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3536     {
3537       struct deps_reg *reg_last = &deps->reg_last[i];
3538       if (reg_last->uses)
3539         free_INSN_LIST_list (&reg_last->uses);
3540       if (reg_last->sets)
3541         free_INSN_LIST_list (&reg_last->sets);
3542       if (reg_last->implicit_sets)
3543         free_INSN_LIST_list (&reg_last->implicit_sets);
3544       if (reg_last->clobbers)
3545         free_INSN_LIST_list (&reg_last->clobbers);
3546     }
3547   CLEAR_REG_SET (&deps->reg_last_in_use);
3548   CLEAR_REG_SET (&deps->reg_conditional_sets);
3549
3550   /* As we initialize reg_last lazily, it is possible that we didn't allocate
3551      it at all.  */
3552   if (deps->reg_last)
3553     free (deps->reg_last);
3554   deps->reg_last = NULL;
3555
3556   deps = NULL;
3557 }
3558
3559 /* Remove INSN from dependence contexts DEPS.  Caution: reg_conditional_sets
3560    is not handled.  */
3561 void
3562 remove_from_deps (struct deps *deps, rtx insn)
3563 {
3564   int removed;
3565   unsigned i;
3566   reg_set_iterator rsi;
3567
3568   removed = remove_from_both_dependence_lists (insn, &deps->pending_read_insns,
3569                                                &deps->pending_read_mems);
3570   if (!DEBUG_INSN_P (insn))
3571     deps->pending_read_list_length -= removed;
3572   removed = remove_from_both_dependence_lists (insn, &deps->pending_write_insns,
3573                                                &deps->pending_write_mems);
3574   deps->pending_write_list_length -= removed;
3575   removed = remove_from_dependence_list (insn, &deps->last_pending_memory_flush);
3576   deps->pending_flush_length -= removed;
3577
3578   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3579     {
3580       struct deps_reg *reg_last = &deps->reg_last[i];
3581       if (reg_last->uses)
3582         remove_from_dependence_list (insn, &reg_last->uses);
3583       if (reg_last->sets)
3584         remove_from_dependence_list (insn, &reg_last->sets);
3585       if (reg_last->implicit_sets)
3586         remove_from_dependence_list (insn, &reg_last->implicit_sets);
3587       if (reg_last->clobbers)
3588         remove_from_dependence_list (insn, &reg_last->clobbers);
3589       if (!reg_last->uses && !reg_last->sets && !reg_last->implicit_sets
3590           && !reg_last->clobbers)
3591         CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, i);
3592     }
3593
3594   if (CALL_P (insn))
3595     {
3596       remove_from_dependence_list (insn, &deps->last_function_call);
3597       remove_from_dependence_list (insn,
3598                                    &deps->last_function_call_may_noreturn);
3599     }
3600   remove_from_dependence_list (insn, &deps->sched_before_next_call);
3601 }
3602
3603 /* Init deps data vector.  */
3604 static void
3605 init_deps_data_vector (void)
3606 {
3607   int reserve = (sched_max_luid + 1
3608                  - VEC_length (haifa_deps_insn_data_def, h_d_i_d));
3609   if (reserve > 0
3610       && ! VEC_space (haifa_deps_insn_data_def, h_d_i_d, reserve))
3611     VEC_safe_grow_cleared (haifa_deps_insn_data_def, heap, h_d_i_d,
3612                            3 * sched_max_luid / 2);
3613 }
3614
3615 /* If it is profitable to use them, initialize or extend (depending on
3616    GLOBAL_P) dependency data.  */
3617 void
3618 sched_deps_init (bool global_p)
3619 {
3620   /* Average number of insns in the basic block.
3621      '+ 1' is used to make it nonzero.  */
3622   int insns_in_block = sched_max_luid / n_basic_blocks + 1;
3623
3624   init_deps_data_vector ();
3625
3626   /* We use another caching mechanism for selective scheduling, so
3627      we don't use this one.  */
3628   if (!sel_sched_p () && global_p && insns_in_block > 100 * 5)
3629     {
3630       /* ?!? We could save some memory by computing a per-region luid mapping
3631          which could reduce both the number of vectors in the cache and the
3632          size of each vector.  Instead we just avoid the cache entirely unless
3633          the average number of instructions in a basic block is very high.  See
3634          the comment before the declaration of true_dependency_cache for
3635          what we consider "very high".  */
3636       cache_size = 0;
3637       extend_dependency_caches (sched_max_luid, true);
3638     }
3639
3640   if (global_p)
3641     {
3642       dl_pool = create_alloc_pool ("deps_list", sizeof (struct _deps_list),
3643                                    /* Allocate lists for one block at a time.  */
3644                                    insns_in_block);
3645       dn_pool = create_alloc_pool ("dep_node", sizeof (struct _dep_node),
3646                                    /* Allocate nodes for one block at a time.
3647                                       We assume that average insn has
3648                                       5 producers.  */
3649                                    5 * insns_in_block);
3650     }
3651 }
3652
3653
3654 /* Create or extend (depending on CREATE_P) dependency caches to
3655    size N.  */
3656 void
3657 extend_dependency_caches (int n, bool create_p)
3658 {
3659   if (create_p || true_dependency_cache)
3660     {
3661       int i, luid = cache_size + n;
3662
3663       true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
3664                                           luid);
3665       output_dependency_cache = XRESIZEVEC (bitmap_head,
3666                                             output_dependency_cache, luid);
3667       anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
3668                                           luid);
3669
3670       if (current_sched_info->flags & DO_SPECULATION)
3671         spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
3672                                             luid);
3673
3674       for (i = cache_size; i < luid; i++)
3675         {
3676           bitmap_initialize (&true_dependency_cache[i], 0);
3677           bitmap_initialize (&output_dependency_cache[i], 0);
3678           bitmap_initialize (&anti_dependency_cache[i], 0);
3679
3680           if (current_sched_info->flags & DO_SPECULATION)
3681             bitmap_initialize (&spec_dependency_cache[i], 0);
3682         }
3683       cache_size = luid;
3684     }
3685 }
3686
3687 /* Finalize dependency information for the whole function.  */
3688 void
3689 sched_deps_finish (void)
3690 {
3691   gcc_assert (deps_pools_are_empty_p ());
3692   free_alloc_pool_if_empty (&dn_pool);
3693   free_alloc_pool_if_empty (&dl_pool);
3694   gcc_assert (dn_pool == NULL && dl_pool == NULL);
3695
3696   VEC_free (haifa_deps_insn_data_def, heap, h_d_i_d);
3697   cache_size = 0;
3698
3699   if (true_dependency_cache)
3700     {
3701       int i;
3702
3703       for (i = 0; i < cache_size; i++)
3704         {
3705           bitmap_clear (&true_dependency_cache[i]);
3706           bitmap_clear (&output_dependency_cache[i]);
3707           bitmap_clear (&anti_dependency_cache[i]);
3708
3709           if (sched_deps_info->generate_spec_deps)
3710             bitmap_clear (&spec_dependency_cache[i]);
3711         }
3712       free (true_dependency_cache);
3713       true_dependency_cache = NULL;
3714       free (output_dependency_cache);
3715       output_dependency_cache = NULL;
3716       free (anti_dependency_cache);
3717       anti_dependency_cache = NULL;
3718
3719       if (sched_deps_info->generate_spec_deps)
3720         {
3721           free (spec_dependency_cache);
3722           spec_dependency_cache = NULL;
3723         }
3724
3725     }
3726 }
3727
3728 /* Initialize some global variables needed by the dependency analysis
3729    code.  */
3730
3731 void
3732 init_deps_global (void)
3733 {
3734   CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
3735   CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
3736   reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
3737   reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
3738   reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
3739   reg_pending_barrier = NOT_A_BARRIER;
3740
3741   if (!sel_sched_p () || sched_emulate_haifa_p)
3742     {
3743       sched_deps_info->start_insn = haifa_start_insn;
3744       sched_deps_info->finish_insn = haifa_finish_insn;
3745
3746       sched_deps_info->note_reg_set = haifa_note_reg_set;
3747       sched_deps_info->note_reg_clobber = haifa_note_reg_clobber;
3748       sched_deps_info->note_reg_use = haifa_note_reg_use;
3749
3750       sched_deps_info->note_mem_dep = haifa_note_mem_dep;
3751       sched_deps_info->note_dep = haifa_note_dep;
3752    }
3753 }
3754
3755 /* Free everything used by the dependency analysis code.  */
3756
3757 void
3758 finish_deps_global (void)
3759 {
3760   FREE_REG_SET (reg_pending_sets);
3761   FREE_REG_SET (reg_pending_clobbers);
3762   FREE_REG_SET (reg_pending_uses);
3763 }
3764
3765 /* Estimate the weakness of dependence between MEM1 and MEM2.  */
3766 dw_t
3767 estimate_dep_weak (rtx mem1, rtx mem2)
3768 {
3769   rtx r1, r2;
3770
3771   if (mem1 == mem2)
3772     /* MEMs are the same - don't speculate.  */
3773     return MIN_DEP_WEAK;
3774
3775   r1 = XEXP (mem1, 0);
3776   r2 = XEXP (mem2, 0);
3777
3778   if (r1 == r2
3779       || (REG_P (r1) && REG_P (r2)
3780           && REGNO (r1) == REGNO (r2)))
3781     /* Again, MEMs are the same.  */
3782     return MIN_DEP_WEAK;
3783   else if ((REG_P (r1) && !REG_P (r2))
3784            || (!REG_P (r1) && REG_P (r2)))
3785     /* Different addressing modes - reason to be more speculative,
3786        than usual.  */
3787     return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
3788   else
3789     /* We can't say anything about the dependence.  */
3790     return UNCERTAIN_DEP_WEAK;
3791 }
3792
3793 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
3794    This function can handle same INSN and ELEM (INSN == ELEM).
3795    It is a convenience wrapper.  */
3796 void
3797 add_dependence (rtx insn, rtx elem, enum reg_note dep_type)
3798 {
3799   ds_t ds;
3800   bool internal;
3801
3802   if (dep_type == REG_DEP_TRUE)
3803     ds = DEP_TRUE;
3804   else if (dep_type == REG_DEP_OUTPUT)
3805     ds = DEP_OUTPUT;
3806   else
3807     {
3808       gcc_assert (dep_type == REG_DEP_ANTI);
3809       ds = DEP_ANTI;
3810     }
3811
3812   /* When add_dependence is called from inside sched-deps.c, we expect
3813      cur_insn to be non-null.  */
3814   internal = cur_insn != NULL;
3815   if (internal)
3816     gcc_assert (insn == cur_insn);
3817   else
3818     cur_insn = insn;
3819
3820   note_dep (elem, ds);
3821   if (!internal)
3822     cur_insn = NULL;
3823 }
3824
3825 /* Return weakness of speculative type TYPE in the dep_status DS.  */
3826 dw_t
3827 get_dep_weak_1 (ds_t ds, ds_t type)
3828 {
3829   ds = ds & type;
3830
3831   switch (type)
3832     {
3833     case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
3834     case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
3835     case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
3836     case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
3837     default: gcc_unreachable ();
3838     }
3839
3840   return (dw_t) ds;
3841 }
3842
3843 dw_t
3844 get_dep_weak (ds_t ds, ds_t type)
3845 {
3846   dw_t dw = get_dep_weak_1 (ds, type);
3847
3848   gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
3849   return dw;
3850 }
3851
3852 /* Return the dep_status, which has the same parameters as DS, except for
3853    speculative type TYPE, that will have weakness DW.  */
3854 ds_t
3855 set_dep_weak (ds_t ds, ds_t type, dw_t dw)
3856 {
3857   gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
3858
3859   ds &= ~type;
3860   switch (type)
3861     {
3862     case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
3863     case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
3864     case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
3865     case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
3866     default: gcc_unreachable ();
3867     }
3868   return ds;
3869 }
3870
3871 /* Return the join of two dep_statuses DS1 and DS2.
3872    If MAX_P is true then choose the greater probability,
3873    otherwise multiply probabilities.
3874    This function assumes that both DS1 and DS2 contain speculative bits.  */
3875 static ds_t
3876 ds_merge_1 (ds_t ds1, ds_t ds2, bool max_p)
3877 {
3878   ds_t ds, t;
3879
3880   gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
3881
3882   ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
3883
3884   t = FIRST_SPEC_TYPE;
3885   do
3886     {
3887       if ((ds1 & t) && !(ds2 & t))
3888         ds |= ds1 & t;
3889       else if (!(ds1 & t) && (ds2 & t))
3890         ds |= ds2 & t;
3891       else if ((ds1 & t) && (ds2 & t))
3892         {
3893           dw_t dw1 = get_dep_weak (ds1, t);
3894           dw_t dw2 = get_dep_weak (ds2, t);
3895           ds_t dw;
3896
3897           if (!max_p)
3898             {
3899               dw = ((ds_t) dw1) * ((ds_t) dw2);
3900               dw /= MAX_DEP_WEAK;
3901               if (dw < MIN_DEP_WEAK)
3902                 dw = MIN_DEP_WEAK;
3903             }
3904           else
3905             {
3906               if (dw1 >= dw2)
3907                 dw = dw1;
3908               else
3909                 dw = dw2;
3910             }
3911
3912           ds = set_dep_weak (ds, t, (dw_t) dw);
3913         }
3914
3915       if (t == LAST_SPEC_TYPE)
3916         break;
3917       t <<= SPEC_TYPE_SHIFT;
3918     }
3919   while (1);
3920
3921   return ds;
3922 }
3923
3924 /* Return the join of two dep_statuses DS1 and DS2.
3925    This function assumes that both DS1 and DS2 contain speculative bits.  */
3926 ds_t
3927 ds_merge (ds_t ds1, ds_t ds2)
3928 {
3929   return ds_merge_1 (ds1, ds2, false);
3930 }
3931
3932 /* Return the join of two dep_statuses DS1 and DS2.  */
3933 ds_t
3934 ds_full_merge (ds_t ds, ds_t ds2, rtx mem1, rtx mem2)
3935 {
3936   ds_t new_status = ds | ds2;
3937
3938   if (new_status & SPECULATIVE)
3939     {
3940       if ((ds && !(ds & SPECULATIVE))
3941           || (ds2 && !(ds2 & SPECULATIVE)))
3942         /* Then this dep can't be speculative.  */
3943         new_status &= ~SPECULATIVE;
3944       else
3945         {
3946           /* Both are speculative.  Merging probabilities.  */
3947           if (mem1)
3948             {
3949               dw_t dw;
3950
3951               dw = estimate_dep_weak (mem1, mem2);
3952               ds = set_dep_weak (ds, BEGIN_DATA, dw);
3953             }
3954
3955           if (!ds)
3956             new_status = ds2;
3957           else if (!ds2)
3958             new_status = ds;
3959           else
3960             new_status = ds_merge (ds2, ds);
3961         }
3962     }
3963
3964   return new_status;
3965 }
3966
3967 /* Return the join of DS1 and DS2.  Use maximum instead of multiplying
3968    probabilities.  */
3969 ds_t
3970 ds_max_merge (ds_t ds1, ds_t ds2)
3971 {
3972   if (ds1 == 0 && ds2 == 0)
3973     return 0;
3974
3975   if (ds1 == 0 && ds2 != 0)
3976     return ds2;
3977
3978   if (ds1 != 0 && ds2 == 0)
3979     return ds1;
3980
3981   return ds_merge_1 (ds1, ds2, true);
3982 }
3983
3984 /* Return the probability of speculation success for the speculation
3985    status DS.  */
3986 dw_t
3987 ds_weak (ds_t ds)
3988 {
3989   ds_t res = 1, dt;
3990   int n = 0;
3991
3992   dt = FIRST_SPEC_TYPE;
3993   do
3994     {
3995       if (ds & dt)
3996         {
3997           res *= (ds_t) get_dep_weak (ds, dt);
3998           n++;
3999         }
4000
4001       if (dt == LAST_SPEC_TYPE)
4002         break;
4003       dt <<= SPEC_TYPE_SHIFT;
4004     }
4005   while (1);
4006
4007   gcc_assert (n);
4008   while (--n)
4009     res /= MAX_DEP_WEAK;
4010
4011   if (res < MIN_DEP_WEAK)
4012     res = MIN_DEP_WEAK;
4013
4014   gcc_assert (res <= MAX_DEP_WEAK);
4015
4016   return (dw_t) res;
4017 }
4018
4019 /* Return a dep status that contains all speculation types of DS.  */
4020 ds_t
4021 ds_get_speculation_types (ds_t ds)
4022 {
4023   if (ds & BEGIN_DATA)
4024     ds |= BEGIN_DATA;
4025   if (ds & BE_IN_DATA)
4026     ds |= BE_IN_DATA;
4027   if (ds & BEGIN_CONTROL)
4028     ds |= BEGIN_CONTROL;
4029   if (ds & BE_IN_CONTROL)
4030     ds |= BE_IN_CONTROL;
4031
4032   return ds & SPECULATIVE;
4033 }
4034
4035 /* Return a dep status that contains maximal weakness for each speculation
4036    type present in DS.  */
4037 ds_t
4038 ds_get_max_dep_weak (ds_t ds)
4039 {
4040   if (ds & BEGIN_DATA)
4041     ds = set_dep_weak (ds, BEGIN_DATA, MAX_DEP_WEAK);
4042   if (ds & BE_IN_DATA)
4043     ds = set_dep_weak (ds, BE_IN_DATA, MAX_DEP_WEAK);
4044   if (ds & BEGIN_CONTROL)
4045     ds = set_dep_weak (ds, BEGIN_CONTROL, MAX_DEP_WEAK);
4046   if (ds & BE_IN_CONTROL)
4047     ds = set_dep_weak (ds, BE_IN_CONTROL, MAX_DEP_WEAK);
4048
4049   return ds;
4050 }
4051
4052 /* Dump information about the dependence status S.  */
4053 static void
4054 dump_ds (FILE *f, ds_t s)
4055 {
4056   fprintf (f, "{");
4057
4058   if (s & BEGIN_DATA)
4059     fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak_1 (s, BEGIN_DATA));
4060   if (s & BE_IN_DATA)
4061     fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak_1 (s, BE_IN_DATA));
4062   if (s & BEGIN_CONTROL)
4063     fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s, BEGIN_CONTROL));
4064   if (s & BE_IN_CONTROL)
4065     fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s, BE_IN_CONTROL));
4066
4067   if (s & HARD_DEP)
4068     fprintf (f, "HARD_DEP; ");
4069
4070   if (s & DEP_TRUE)
4071     fprintf (f, "DEP_TRUE; ");
4072   if (s & DEP_ANTI)
4073     fprintf (f, "DEP_ANTI; ");
4074   if (s & DEP_OUTPUT)
4075     fprintf (f, "DEP_OUTPUT; ");
4076
4077   fprintf (f, "}");
4078 }
4079
4080 void
4081 debug_ds (ds_t s)
4082 {
4083   dump_ds (stderr, s);
4084   fprintf (stderr, "\n");
4085 }
4086
4087 #ifdef ENABLE_CHECKING
4088 /* Verify that dependence type and status are consistent.
4089    If RELAXED_P is true, then skip dep_weakness checks.  */
4090 static void
4091 check_dep (dep_t dep, bool relaxed_p)
4092 {
4093   enum reg_note dt = DEP_TYPE (dep);
4094   ds_t ds = DEP_STATUS (dep);
4095
4096   gcc_assert (DEP_PRO (dep) != DEP_CON (dep));
4097
4098   if (!(current_sched_info->flags & USE_DEPS_LIST))
4099     {
4100       gcc_assert (ds == -1);
4101       return;
4102     }
4103
4104   /* Check that dependence type contains the same bits as the status.  */
4105   if (dt == REG_DEP_TRUE)
4106     gcc_assert (ds & DEP_TRUE);
4107   else if (dt == REG_DEP_OUTPUT)
4108     gcc_assert ((ds & DEP_OUTPUT)
4109                 && !(ds & DEP_TRUE));
4110   else
4111     gcc_assert ((dt == REG_DEP_ANTI)
4112                 && (ds & DEP_ANTI)
4113                 && !(ds & (DEP_OUTPUT | DEP_TRUE)));
4114
4115   /* HARD_DEP can not appear in dep_status of a link.  */
4116   gcc_assert (!(ds & HARD_DEP));
4117
4118   /* Check that dependence status is set correctly when speculation is not
4119      supported.  */
4120   if (!sched_deps_info->generate_spec_deps)
4121     gcc_assert (!(ds & SPECULATIVE));
4122   else if (ds & SPECULATIVE)
4123     {
4124       if (!relaxed_p)
4125         {
4126           ds_t type = FIRST_SPEC_TYPE;
4127
4128           /* Check that dependence weakness is in proper range.  */
4129           do
4130             {
4131               if (ds & type)
4132                 get_dep_weak (ds, type);
4133
4134               if (type == LAST_SPEC_TYPE)
4135                 break;
4136               type <<= SPEC_TYPE_SHIFT;
4137             }
4138           while (1);
4139         }
4140
4141       if (ds & BEGIN_SPEC)
4142         {
4143           /* Only true dependence can be data speculative.  */
4144           if (ds & BEGIN_DATA)
4145             gcc_assert (ds & DEP_TRUE);
4146
4147           /* Control dependencies in the insn scheduler are represented by
4148              anti-dependencies, therefore only anti dependence can be
4149              control speculative.  */
4150           if (ds & BEGIN_CONTROL)
4151             gcc_assert (ds & DEP_ANTI);
4152         }
4153       else
4154         {
4155           /* Subsequent speculations should resolve true dependencies.  */
4156           gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
4157         }
4158
4159       /* Check that true and anti dependencies can't have other speculative
4160          statuses.  */
4161       if (ds & DEP_TRUE)
4162         gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
4163       /* An output dependence can't be speculative at all.  */
4164       gcc_assert (!(ds & DEP_OUTPUT));
4165       if (ds & DEP_ANTI)
4166         gcc_assert (ds & BEGIN_CONTROL);
4167     }
4168 }
4169 #endif /* ENABLE_CHECKING */
4170
4171 #endif /* INSN_SCHEDULING */