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