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