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