gcc/sched-deps.c

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