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