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, t)
2640                     && ! sched_insns_conditions_mutex_p (insn,
2641                                                          XEXP (pending, 0)))
2642                   note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2643                                 sched_deps_info->generate_spec_deps
2644                                 ? BEGIN_DATA | DEP_TRUE : DEP_TRUE);
2645
2646                 pending = XEXP (pending, 1);
2647                 pending_mem = XEXP (pending_mem, 1);
2648               }
2649
2650             for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
2651               add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
2652
2653             for (u = deps->pending_jump_insns; u; u = XEXP (u, 1))
2654               if (deps_may_trap_p (x))
2655                 {
2656                   if ((sched_deps_info->generate_spec_deps)
2657                       && sel_sched_p () && (spec_info->mask & BEGIN_CONTROL))
2658                     {
2659                       ds_t ds = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
2660                                               MAX_DEP_WEAK);
2661
2662                       note_dep (XEXP (u, 0), ds);
2663                     }
2664                   else
2665                     add_dependence (insn, XEXP (u, 0), REG_DEP_CONTROL);
2666                 }
2667           }
2668
2669         /* Always add these dependencies to pending_reads, since
2670            this insn may be followed by a write.  */
2671         if (!deps->readonly)
2672           add_insn_mem_dependence (deps, true, insn, x);
2673
2674         sched_analyze_2 (deps, XEXP (x, 0), insn);
2675
2676         if (cslr_p && sched_deps_info->finish_rhs)
2677           sched_deps_info->finish_rhs ();
2678
2679         return;
2680       }
2681
2682     /* Force pending stores to memory in case a trap handler needs them.  */
2683     case TRAP_IF:
2684       flush_pending_lists (deps, insn, true, false);
2685       break;
2686
2687     case PREFETCH:
2688       if (PREFETCH_SCHEDULE_BARRIER_P (x))
2689         reg_pending_barrier = TRUE_BARRIER;
2690       break;
2691
2692     case UNSPEC_VOLATILE:
2693       flush_pending_lists (deps, insn, true, true);
2694       /* FALLTHRU */
2695
2696     case ASM_OPERANDS:
2697     case ASM_INPUT:
2698       {
2699         /* Traditional and volatile asm instructions must be considered to use
2700            and clobber all hard registers, all pseudo-registers and all of
2701            memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
2702
2703            Consider for instance a volatile asm that changes the fpu rounding
2704            mode.  An insn should not be moved across this even if it only uses
2705            pseudo-regs because it might give an incorrectly rounded result.  */
2706         if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
2707           reg_pending_barrier = TRUE_BARRIER;
2708
2709         /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2710            We can not just fall through here since then we would be confused
2711            by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2712            traditional asms unlike their normal usage.  */
2713
2714         if (code == ASM_OPERANDS)
2715           {
2716             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
2717               sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
2718
2719             if (cslr_p && sched_deps_info->finish_rhs)
2720               sched_deps_info->finish_rhs ();
2721
2722             return;
2723           }
2724         break;
2725       }
2726
2727     case PRE_DEC:
2728     case POST_DEC:
2729     case PRE_INC:
2730     case POST_INC:
2731       /* These both read and modify the result.  We must handle them as writes
2732          to get proper dependencies for following instructions.  We must handle
2733          them as reads to get proper dependencies from this to previous
2734          instructions.  Thus we need to pass them to both sched_analyze_1
2735          and sched_analyze_2.  We must call sched_analyze_2 first in order
2736          to get the proper antecedent for the read.  */
2737       sched_analyze_2 (deps, XEXP (x, 0), insn);
2738       sched_analyze_1 (deps, x, insn);
2739
2740       if (cslr_p && sched_deps_info->finish_rhs)
2741         sched_deps_info->finish_rhs ();
2742
2743       return;
2744
2745     case POST_MODIFY:
2746     case PRE_MODIFY:
2747       /* op0 = op0 + op1 */
2748       sched_analyze_2 (deps, XEXP (x, 0), insn);
2749       sched_analyze_2 (deps, XEXP (x, 1), insn);
2750       sched_analyze_1 (deps, x, insn);
2751
2752       if (cslr_p && sched_deps_info->finish_rhs)
2753         sched_deps_info->finish_rhs ();
2754
2755       return;
2756
2757     default:
2758       break;
2759     }
2760
2761   /* Other cases: walk the insn.  */
2762   fmt = GET_RTX_FORMAT (code);
2763   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2764     {
2765       if (fmt[i] == 'e')
2766         sched_analyze_2 (deps, XEXP (x, i), insn);
2767       else if (fmt[i] == 'E')
2768         for (j = 0; j < XVECLEN (x, i); j++)
2769           sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
2770     }
2771
2772   if (cslr_p && sched_deps_info->finish_rhs)
2773     sched_deps_info->finish_rhs ();
2774 }
2775
2776 /* Analyze an INSN with pattern X to find all dependencies.  */
2777 static void
2778 sched_analyze_insn (struct deps_desc *deps, rtx x, rtx insn)
2779 {
2780   RTX_CODE code = GET_CODE (x);
2781   rtx link;
2782   unsigned i;
2783   reg_set_iterator rsi;
2784
2785   if (! reload_completed)
2786     {
2787       HARD_REG_SET temp;
2788
2789       extract_insn (insn);
2790       preprocess_constraints ();
2791       ira_implicitly_set_insn_hard_regs (&temp);
2792       AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
2793       IOR_HARD_REG_SET (implicit_reg_pending_clobbers, temp);
2794     }
2795
2796   can_start_lhs_rhs_p = (NONJUMP_INSN_P (insn)
2797                          && code == SET);
2798
2799   if (may_trap_p (x))
2800     /* Avoid moving trapping instructions accross function calls that might
2801        not always return.  */
2802     add_dependence_list (insn, deps->last_function_call_may_noreturn,
2803                          1, REG_DEP_ANTI);
2804
2805   /* We must avoid creating a situation in which two successors of the
2806      current block have different unwind info after scheduling.  If at any
2807      point the two paths re-join this leads to incorrect unwind info.  */
2808   /* ??? There are certain situations involving a forced frame pointer in
2809      which, with extra effort, we could fix up the unwind info at a later
2810      CFG join.  However, it seems better to notice these cases earlier
2811      during prologue generation and avoid marking the frame pointer setup
2812      as frame-related at all.  */
2813   if (RTX_FRAME_RELATED_P (insn))
2814     {
2815       /* Make sure prologue insn is scheduled before next jump.  */
2816       deps->sched_before_next_jump
2817         = alloc_INSN_LIST (insn, deps->sched_before_next_jump);
2818
2819       /* Make sure epilogue insn is scheduled after preceding jumps.  */
2820       add_dependence_list (insn, deps->pending_jump_insns, 1, REG_DEP_ANTI);
2821     }
2822
2823   if (code == COND_EXEC)
2824     {
2825       sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
2826
2827       /* ??? Should be recording conditions so we reduce the number of
2828          false dependencies.  */
2829       x = COND_EXEC_CODE (x);
2830       code = GET_CODE (x);
2831     }
2832   if (code == SET || code == CLOBBER)
2833     {
2834       sched_analyze_1 (deps, x, insn);
2835
2836       /* Bare clobber insns are used for letting life analysis, reg-stack
2837          and others know that a value is dead.  Depend on the last call
2838          instruction so that reg-stack won't get confused.  */
2839       if (code == CLOBBER)
2840         add_dependence_list (insn, deps->last_function_call, 1,
2841                              REG_DEP_OUTPUT);
2842     }
2843   else if (code == PARALLEL)
2844     {
2845       for (i = XVECLEN (x, 0); i--;)
2846         {
2847           rtx sub = XVECEXP (x, 0, i);
2848           code = GET_CODE (sub);
2849
2850           if (code == COND_EXEC)
2851             {
2852               sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
2853               sub = COND_EXEC_CODE (sub);
2854               code = GET_CODE (sub);
2855             }
2856           if (code == SET || code == CLOBBER)
2857             sched_analyze_1 (deps, sub, insn);
2858           else
2859             sched_analyze_2 (deps, sub, insn);
2860         }
2861     }
2862   else
2863     sched_analyze_2 (deps, x, insn);
2864
2865   /* Mark registers CLOBBERED or used by called function.  */
2866   if (CALL_P (insn))
2867     {
2868       for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
2869         {
2870           if (GET_CODE (XEXP (link, 0)) == CLOBBER)
2871             sched_analyze_1 (deps, XEXP (link, 0), insn);
2872           else
2873             sched_analyze_2 (deps, XEXP (link, 0), insn);
2874         }
2875       /* Don't schedule anything after a tail call, tail call needs
2876          to use at least all call-saved registers.  */
2877       if (SIBLING_CALL_P (insn))
2878         reg_pending_barrier = TRUE_BARRIER;
2879       else if (find_reg_note (insn, REG_SETJMP, NULL))
2880         reg_pending_barrier = MOVE_BARRIER;
2881     }
2882
2883   if (JUMP_P (insn))
2884     {
2885       rtx next;
2886       next = next_nonnote_nondebug_insn (insn);
2887       if (next && BARRIER_P (next))
2888         reg_pending_barrier = MOVE_BARRIER;
2889       else
2890         {
2891           rtx pending, pending_mem;
2892
2893           if (sched_deps_info->compute_jump_reg_dependencies)
2894             {
2895               (*sched_deps_info->compute_jump_reg_dependencies)
2896                 (insn, reg_pending_control_uses);
2897
2898               /* Make latency of jump equal to 0 by using anti-dependence.  */
2899               EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
2900                 {
2901                   struct deps_reg *reg_last = &deps->reg_last[i];
2902                   add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
2903                   add_dependence_list (insn, reg_last->implicit_sets,
2904                                        0, REG_DEP_ANTI);
2905                   add_dependence_list (insn, reg_last->clobbers, 0,
2906                                        REG_DEP_ANTI);
2907                 }
2908             }
2909
2910           /* All memory writes and volatile reads must happen before the
2911              jump.  Non-volatile reads must happen before the jump iff
2912              the result is needed by the above register used mask.  */
2913
2914           pending = deps->pending_write_insns;
2915           pending_mem = deps->pending_write_mems;
2916           while (pending)
2917             {
2918               if (! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2919                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
2920               pending = XEXP (pending, 1);
2921               pending_mem = XEXP (pending_mem, 1);
2922             }
2923
2924           pending = deps->pending_read_insns;
2925           pending_mem = deps->pending_read_mems;
2926           while (pending)
2927             {
2928               if (MEM_VOLATILE_P (XEXP (pending_mem, 0))
2929                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2930                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
2931               pending = XEXP (pending, 1);
2932               pending_mem = XEXP (pending_mem, 1);
2933             }
2934
2935           add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2936                                REG_DEP_ANTI);
2937           add_dependence_list (insn, deps->pending_jump_insns, 1,
2938                                REG_DEP_ANTI);
2939         }
2940     }
2941
2942   /* If this instruction can throw an exception, then moving it changes
2943      where block boundaries fall.  This is mighty confusing elsewhere.
2944      Therefore, prevent such an instruction from being moved.  Same for
2945      non-jump instructions that define block boundaries.
2946      ??? Unclear whether this is still necessary in EBB mode.  If not,
2947      add_branch_dependences should be adjusted for RGN mode instead.  */
2948   if (((CALL_P (insn) || JUMP_P (insn)) && can_throw_internal (insn))
2949       || (NONJUMP_INSN_P (insn) && control_flow_insn_p (insn)))
2950     reg_pending_barrier = MOVE_BARRIER;
2951
2952   if (sched_pressure_p)
2953     {
2954       setup_insn_reg_uses (deps, insn);
2955       init_insn_reg_pressure_info (insn);
2956     }
2957
2958   /* Add register dependencies for insn.  */
2959   if (DEBUG_INSN_P (insn))
2960     {
2961       rtx prev = deps->last_debug_insn;
2962       rtx u;
2963
2964       if (!deps->readonly)
2965         deps->last_debug_insn = insn;
2966
2967       if (prev)
2968         add_dependence (insn, prev, REG_DEP_ANTI);
2969
2970       add_dependence_list (insn, deps->last_function_call, 1,
2971                            REG_DEP_ANTI);
2972
2973       for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
2974         if (!sel_sched_p ())
2975           add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
2976
2977       EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
2978         {
2979           struct deps_reg *reg_last = &deps->reg_last[i];
2980           add_dependence_list (insn, reg_last->sets, 1, REG_DEP_ANTI);
2981           /* There's no point in making REG_DEP_CONTROL dependencies for
2982              debug insns.  */
2983           add_dependence_list (insn, reg_last->clobbers, 1, REG_DEP_ANTI);
2984
2985           if (!deps->readonly)
2986             reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
2987         }
2988       CLEAR_REG_SET (reg_pending_uses);
2989
2990       /* Quite often, a debug insn will refer to stuff in the
2991          previous instruction, but the reason we want this
2992          dependency here is to make sure the scheduler doesn't
2993          gratuitously move a debug insn ahead.  This could dirty
2994          DF flags and cause additional analysis that wouldn't have
2995          occurred in compilation without debug insns, and such
2996          additional analysis can modify the generated code.  */
2997       prev = PREV_INSN (insn);
2998
2999       if (prev && NONDEBUG_INSN_P (prev))
3000         add_dependence (insn, prev, REG_DEP_ANTI);
3001     }
3002   else
3003     {
3004       regset_head set_or_clobbered;
3005
3006       EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
3007         {
3008           struct deps_reg *reg_last = &deps->reg_last[i];
3009           add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
3010           add_dependence_list (insn, reg_last->implicit_sets, 0, REG_DEP_ANTI);
3011           add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
3012
3013           if (!deps->readonly)
3014             {
3015               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3016               reg_last->uses_length++;
3017             }
3018         }
3019
3020       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3021         if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i))
3022           {
3023             struct deps_reg *reg_last = &deps->reg_last[i];
3024             add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
3025             add_dependence_list (insn, reg_last->implicit_sets, 0,
3026                                  REG_DEP_ANTI);
3027             add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
3028
3029             if (!deps->readonly)
3030               {
3031                 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3032                 reg_last->uses_length++;
3033               }
3034           }
3035
3036       if (targetm.sched.exposed_pipeline)
3037         {
3038           INIT_REG_SET (&set_or_clobbered);
3039           bitmap_ior (&set_or_clobbered, reg_pending_clobbers,
3040                       reg_pending_sets);
3041           EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered, 0, i, rsi)
3042             {
3043               struct deps_reg *reg_last = &deps->reg_last[i];
3044               rtx list;
3045               for (list = reg_last->uses; list; list = XEXP (list, 1))
3046                 {
3047                   rtx other = XEXP (list, 0);
3048                   if (INSN_CACHED_COND (other) != const_true_rtx
3049                       && refers_to_regno_p (i, i + 1, INSN_CACHED_COND (other), NULL))
3050                     INSN_CACHED_COND (other) = const_true_rtx;
3051                 }
3052             }
3053         }
3054
3055       /* If the current insn is conditional, we can't free any
3056          of the lists.  */
3057       if (sched_has_condition_p (insn))
3058         {
3059           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3060             {
3061               struct deps_reg *reg_last = &deps->reg_last[i];
3062               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
3063               add_dependence_list (insn, reg_last->implicit_sets, 0,
3064                                    REG_DEP_ANTI);
3065               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
3066               add_dependence_list (insn, reg_last->control_uses, 0,
3067                                    REG_DEP_CONTROL);
3068
3069               if (!deps->readonly)
3070                 {
3071                   reg_last->clobbers
3072                     = alloc_INSN_LIST (insn, reg_last->clobbers);
3073                   reg_last->clobbers_length++;
3074                 }
3075             }
3076           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3077             {
3078               struct deps_reg *reg_last = &deps->reg_last[i];
3079               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
3080               add_dependence_list (insn, reg_last->implicit_sets, 0,
3081                                    REG_DEP_ANTI);
3082               add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT);
3083               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
3084               add_dependence_list (insn, reg_last->control_uses, 0,
3085                                    REG_DEP_CONTROL);
3086
3087               if (!deps->readonly)
3088                 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3089             }
3090         }
3091       else
3092         {
3093           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3094             {
3095               struct deps_reg *reg_last = &deps->reg_last[i];
3096               if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
3097                   || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
3098                 {
3099                   add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3100                                                 REG_DEP_OUTPUT);
3101                   add_dependence_list_and_free (deps, insn,
3102                                                 &reg_last->implicit_sets, 0,
3103                                                 REG_DEP_ANTI);
3104                   add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3105                                                 REG_DEP_ANTI);
3106                   add_dependence_list_and_free (deps, insn,
3107                                                 &reg_last->control_uses, 0,
3108                                                 REG_DEP_ANTI);
3109                   add_dependence_list_and_free
3110                     (deps, insn, &reg_last->clobbers, 0, REG_DEP_OUTPUT);
3111
3112                   if (!deps->readonly)
3113                     {
3114                       reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3115                       reg_last->clobbers_length = 0;
3116                       reg_last->uses_length = 0;
3117                     }
3118                 }
3119               else
3120                 {
3121                   add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
3122                   add_dependence_list (insn, reg_last->implicit_sets, 0,
3123                                        REG_DEP_ANTI);
3124                   add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
3125                   add_dependence_list (insn, reg_last->control_uses, 0,
3126                                        REG_DEP_CONTROL);
3127                 }
3128
3129               if (!deps->readonly)
3130                 {
3131                   reg_last->clobbers_length++;
3132                   reg_last->clobbers
3133                     = alloc_INSN_LIST (insn, reg_last->clobbers);
3134                 }
3135             }
3136           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3137             {
3138               struct deps_reg *reg_last = &deps->reg_last[i];
3139
3140               add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3141                                             REG_DEP_OUTPUT);
3142               add_dependence_list_and_free (deps, insn,
3143                                             &reg_last->implicit_sets,
3144                                             0, REG_DEP_ANTI);
3145               add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3146                                             REG_DEP_OUTPUT);
3147               add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3148                                             REG_DEP_ANTI);
3149               add_dependence_list (insn, reg_last->control_uses, 0,
3150                                    REG_DEP_CONTROL);
3151
3152               if (!deps->readonly)
3153                 {
3154                   reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3155                   reg_last->uses_length = 0;
3156                   reg_last->clobbers_length = 0;
3157                 }
3158             }
3159         }
3160       if (!deps->readonly)
3161         {
3162           EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
3163             {
3164               struct deps_reg *reg_last = &deps->reg_last[i];
3165               reg_last->control_uses
3166                 = alloc_INSN_LIST (insn, reg_last->control_uses);
3167             }
3168         }
3169     }
3170
3171   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3172     if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
3173       {
3174         struct deps_reg *reg_last = &deps->reg_last[i];
3175         add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
3176         add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI);
3177         add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
3178         add_dependence_list (insn, reg_last->control_uses, 0, REG_DEP_ANTI);
3179
3180         if (!deps->readonly)
3181           reg_last->implicit_sets
3182             = alloc_INSN_LIST (insn, reg_last->implicit_sets);
3183       }
3184
3185   if (!deps->readonly)
3186     {
3187       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
3188       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
3189       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
3190       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3191         if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i)
3192             || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
3193           SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3194
3195       /* Set up the pending barrier found.  */
3196       deps->last_reg_pending_barrier = reg_pending_barrier;
3197     }
3198
3199   CLEAR_REG_SET (reg_pending_uses);
3200   CLEAR_REG_SET (reg_pending_clobbers);
3201   CLEAR_REG_SET (reg_pending_sets);
3202   CLEAR_REG_SET (reg_pending_control_uses);
3203   CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
3204   CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
3205
3206   /* Add dependencies if a scheduling barrier was found.  */
3207   if (reg_pending_barrier)
3208     {
3209       /* In the case of barrier the most added dependencies are not
3210          real, so we use anti-dependence here.  */
3211       if (sched_has_condition_p (insn))
3212         {
3213           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3214             {
3215               struct deps_reg *reg_last = &deps->reg_last[i];
3216               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
3217               add_dependence_list (insn, reg_last->sets, 0,
3218                                    reg_pending_barrier == TRUE_BARRIER
3219                                    ? REG_DEP_TRUE : REG_DEP_ANTI);
3220               add_dependence_list (insn, reg_last->implicit_sets, 0,
3221                                    REG_DEP_ANTI);
3222               add_dependence_list (insn, reg_last->clobbers, 0,
3223                                    reg_pending_barrier == TRUE_BARRIER
3224                                    ? REG_DEP_TRUE : REG_DEP_ANTI);
3225             }
3226         }
3227       else
3228         {
3229           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3230             {
3231               struct deps_reg *reg_last = &deps->reg_last[i];
3232               add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3233                                             REG_DEP_ANTI);
3234               add_dependence_list_and_free (deps, insn,
3235                                             &reg_last->control_uses, 0,
3236                                             REG_DEP_CONTROL);
3237               add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3238                                             reg_pending_barrier == TRUE_BARRIER
3239                                             ? REG_DEP_TRUE : REG_DEP_ANTI);
3240               add_dependence_list_and_free (deps, insn,
3241                                             &reg_last->implicit_sets, 0,
3242                                             REG_DEP_ANTI);
3243               add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3244                                             reg_pending_barrier == TRUE_BARRIER
3245                                             ? REG_DEP_TRUE : REG_DEP_ANTI);
3246
3247               if (!deps->readonly)
3248                 {
3249                   reg_last->uses_length = 0;
3250                   reg_last->clobbers_length = 0;
3251                 }
3252             }
3253         }
3254
3255       if (!deps->readonly)
3256         for (i = 0; i < (unsigned)deps->max_reg; i++)
3257           {
3258             struct deps_reg *reg_last = &deps->reg_last[i];
3259             reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3260             SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3261           }
3262
3263       /* Flush pending lists on jumps, but not on speculative checks.  */
3264       if (JUMP_P (insn) && !(sel_sched_p ()
3265                              && sel_insn_is_speculation_check (insn)))
3266         flush_pending_lists (deps, insn, true, true);
3267
3268       reg_pending_barrier = NOT_A_BARRIER;
3269     }
3270
3271   /* If a post-call group is still open, see if it should remain so.
3272      This insn must be a simple move of a hard reg to a pseudo or
3273      vice-versa.
3274
3275      We must avoid moving these insns for correctness on targets
3276      with small register classes, and for special registers like
3277      PIC_OFFSET_TABLE_REGNUM.  For simplicity, extend this to all
3278      hard regs for all targets.  */
3279
3280   if (deps->in_post_call_group_p)
3281     {
3282       rtx tmp, set = single_set (insn);
3283       int src_regno, dest_regno;
3284
3285       if (set == NULL)
3286         {
3287           if (DEBUG_INSN_P (insn))
3288             /* We don't want to mark debug insns as part of the same
3289                sched group.  We know they really aren't, but if we use
3290                debug insns to tell that a call group is over, we'll
3291                get different code if debug insns are not there and
3292                instructions that follow seem like they should be part
3293                of the call group.
3294
3295                Also, if we did, fixup_sched_groups() would move the
3296                deps of the debug insn to the call insn, modifying
3297                non-debug post-dependency counts of the debug insn
3298                dependencies and otherwise messing with the scheduling
3299                order.
3300
3301                Instead, let such debug insns be scheduled freely, but
3302                keep the call group open in case there are insns that
3303                should be part of it afterwards.  Since we grant debug
3304                insns higher priority than even sched group insns, it
3305                will all turn out all right.  */
3306             goto debug_dont_end_call_group;
3307           else
3308             goto end_call_group;
3309         }
3310
3311       tmp = SET_DEST (set);
3312       if (GET_CODE (tmp) == SUBREG)
3313         tmp = SUBREG_REG (tmp);
3314       if (REG_P (tmp))
3315         dest_regno = REGNO (tmp);
3316       else
3317         goto end_call_group;
3318
3319       tmp = SET_SRC (set);
3320       if (GET_CODE (tmp) == SUBREG)
3321         tmp = SUBREG_REG (tmp);
3322       if ((GET_CODE (tmp) == PLUS
3323            || GET_CODE (tmp) == MINUS)
3324           && REG_P (XEXP (tmp, 0))
3325           && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
3326           && dest_regno == STACK_POINTER_REGNUM)
3327         src_regno = STACK_POINTER_REGNUM;
3328       else if (REG_P (tmp))
3329         src_regno = REGNO (tmp);
3330       else
3331         goto end_call_group;
3332
3333       if (src_regno < FIRST_PSEUDO_REGISTER
3334           || dest_regno < FIRST_PSEUDO_REGISTER)
3335         {
3336           if (!deps->readonly
3337               && deps->in_post_call_group_p == post_call_initial)
3338             deps->in_post_call_group_p = post_call;
3339
3340           if (!sel_sched_p () || sched_emulate_haifa_p)
3341             {
3342               SCHED_GROUP_P (insn) = 1;
3343               CANT_MOVE (insn) = 1;
3344             }
3345         }
3346       else
3347         {
3348         end_call_group:
3349           if (!deps->readonly)
3350             deps->in_post_call_group_p = not_post_call;
3351         }
3352     }
3353
3354  debug_dont_end_call_group:
3355   if ((current_sched_info->flags & DO_SPECULATION)
3356       && !sched_insn_is_legitimate_for_speculation_p (insn, 0))
3357     /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3358        be speculated.  */
3359     {
3360       if (sel_sched_p ())
3361         sel_mark_hard_insn (insn);
3362       else
3363         {
3364           sd_iterator_def sd_it;
3365           dep_t dep;
3366
3367           for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3368                sd_iterator_cond (&sd_it, &dep);)
3369             change_spec_dep_to_hard (sd_it);
3370         }
3371     }
3372 }
3373
3374 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3375    longjmp, loop forever, ...).  */
3376 static bool
3377 call_may_noreturn_p (rtx insn)
3378 {
3379   rtx call;
3380
3381   /* const or pure calls that aren't looping will always return.  */
3382   if (RTL_CONST_OR_PURE_CALL_P (insn)
3383       && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))
3384     return false;
3385
3386   call = PATTERN (insn);
3387   if (GET_CODE (call) == PARALLEL)
3388     call = XVECEXP (call, 0, 0);
3389   if (GET_CODE (call) == SET)
3390     call = SET_SRC (call);
3391   if (GET_CODE (call) == CALL
3392       && MEM_P (XEXP (call, 0))
3393       && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
3394     {
3395       rtx symbol = XEXP (XEXP (call, 0), 0);
3396       if (SYMBOL_REF_DECL (symbol)
3397           && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
3398         {
3399           if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
3400               == BUILT_IN_NORMAL)
3401             switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol)))
3402               {
3403               case BUILT_IN_BCMP:
3404               case BUILT_IN_BCOPY:
3405               case BUILT_IN_BZERO:
3406               case BUILT_IN_INDEX:
3407               case BUILT_IN_MEMCHR:
3408               case BUILT_IN_MEMCMP:
3409               case BUILT_IN_MEMCPY:
3410               case BUILT_IN_MEMMOVE:
3411               case BUILT_IN_MEMPCPY:
3412               case BUILT_IN_MEMSET:
3413               case BUILT_IN_RINDEX:
3414               case BUILT_IN_STPCPY:
3415               case BUILT_IN_STPNCPY:
3416               case BUILT_IN_STRCAT:
3417               case BUILT_IN_STRCHR:
3418               case BUILT_IN_STRCMP:
3419               case BUILT_IN_STRCPY:
3420               case BUILT_IN_STRCSPN:
3421               case BUILT_IN_STRLEN:
3422               case BUILT_IN_STRNCAT:
3423               case BUILT_IN_STRNCMP:
3424               case BUILT_IN_STRNCPY:
3425               case BUILT_IN_STRPBRK:
3426               case BUILT_IN_STRRCHR:
3427               case BUILT_IN_STRSPN:
3428               case BUILT_IN_STRSTR:
3429                 /* Assume certain string/memory builtins always return.  */
3430                 return false;
3431               default:
3432                 break;
3433               }
3434         }
3435     }
3436
3437   /* For all other calls assume that they might not always return.  */
3438   return true;
3439 }
3440
3441 /* Analyze INSN with DEPS as a context.  */
3442 void
3443 deps_analyze_insn (struct deps_desc *deps, rtx insn)
3444 {
3445   if (sched_deps_info->start_insn)
3446     sched_deps_info->start_insn (insn);
3447
3448   /* Record the condition for this insn.  */
3449   if (NONDEBUG_INSN_P (insn))
3450     {
3451       rtx t;
3452       sched_get_condition_with_rev (insn, NULL);
3453       t = INSN_CACHED_COND (insn);
3454       INSN_COND_DEPS (insn) = NULL_RTX;
3455       if (reload_completed
3456           && (current_sched_info->flags & DO_PREDICATION)
3457           && COMPARISON_P (t)
3458           && REG_P (XEXP (t, 0))
3459           && CONSTANT_P (XEXP (t, 1)))
3460         {
3461           unsigned int regno;
3462           int nregs;
3463           t = XEXP (t, 0);
3464           regno = REGNO (t);
3465           nregs = hard_regno_nregs[regno][GET_MODE (t)];
3466           t = NULL_RTX;
3467           while (nregs-- > 0)
3468             {
3469               struct deps_reg *reg_last = &deps->reg_last[regno + nregs];
3470               t = concat_INSN_LIST (reg_last->sets, t);
3471               t = concat_INSN_LIST (reg_last->clobbers, t);
3472               t = concat_INSN_LIST (reg_last->implicit_sets, t);
3473             }
3474           INSN_COND_DEPS (insn) = t;
3475         }
3476     }
3477
3478   if (JUMP_P (insn))
3479     {
3480       /* Make each JUMP_INSN (but not a speculative check)
3481          a scheduling barrier for memory references.  */
3482       if (!deps->readonly
3483           && !(sel_sched_p ()
3484                && sel_insn_is_speculation_check (insn)))
3485         {
3486           /* Keep the list a reasonable size.  */
3487           if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
3488             flush_pending_lists (deps, insn, true, true);
3489           else
3490             deps->pending_jump_insns
3491               = alloc_INSN_LIST (insn, deps->pending_jump_insns);
3492         }
3493
3494       /* For each insn which shouldn't cross a jump, add a dependence.  */
3495       add_dependence_list_and_free (deps, insn,
3496                                     &deps->sched_before_next_jump, 1,
3497                                     REG_DEP_ANTI);
3498
3499       sched_analyze_insn (deps, PATTERN (insn), insn);
3500     }
3501   else if (NONJUMP_INSN_P (insn) || DEBUG_INSN_P (insn))
3502     {
3503       sched_analyze_insn (deps, PATTERN (insn), insn);
3504     }
3505   else if (CALL_P (insn))
3506     {
3507       int i;
3508
3509       CANT_MOVE (insn) = 1;
3510
3511       if (find_reg_note (insn, REG_SETJMP, NULL))
3512         {
3513           /* This is setjmp.  Assume that all registers, not just
3514              hard registers, may be clobbered by this call.  */
3515           reg_pending_barrier = MOVE_BARRIER;
3516         }
3517       else
3518         {
3519           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3520             /* A call may read and modify global register variables.  */
3521             if (global_regs[i])
3522               {
3523                 SET_REGNO_REG_SET (reg_pending_sets, i);
3524                 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3525               }
3526           /* Other call-clobbered hard regs may be clobbered.
3527              Since we only have a choice between 'might be clobbered'
3528              and 'definitely not clobbered', we must include all
3529              partly call-clobbered registers here.  */
3530             else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
3531                      || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3532               SET_REGNO_REG_SET (reg_pending_clobbers, i);
3533           /* We don't know what set of fixed registers might be used
3534              by the function, but it is certain that the stack pointer
3535              is among them, but be conservative.  */
3536             else if (fixed_regs[i])
3537               SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3538           /* The frame pointer is normally not used by the function
3539              itself, but by the debugger.  */
3540           /* ??? MIPS o32 is an exception.  It uses the frame pointer
3541              in the macro expansion of jal but does not represent this
3542              fact in the call_insn rtl.  */
3543             else if (i == FRAME_POINTER_REGNUM
3544                      || (i == HARD_FRAME_POINTER_REGNUM
3545                          && (! reload_completed || frame_pointer_needed)))
3546               SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3547         }
3548
3549       /* For each insn which shouldn't cross a call, add a dependence
3550          between that insn and this call insn.  */
3551       add_dependence_list_and_free (deps, insn,
3552                                     &deps->sched_before_next_call, 1,
3553                                     REG_DEP_ANTI);
3554
3555       sched_analyze_insn (deps, PATTERN (insn), insn);
3556
3557       /* If CALL would be in a sched group, then this will violate
3558          convention that sched group insns have dependencies only on the
3559          previous instruction.
3560
3561          Of course one can say: "Hey!  What about head of the sched group?"
3562          And I will answer: "Basic principles (one dep per insn) are always
3563          the same."  */
3564       gcc_assert (!SCHED_GROUP_P (insn));
3565
3566       /* In the absence of interprocedural alias analysis, we must flush
3567          all pending reads and writes, and start new dependencies starting
3568          from here.  But only flush writes for constant calls (which may
3569          be passed a pointer to something we haven't written yet).  */
3570       flush_pending_lists (deps, insn, true, ! RTL_CONST_OR_PURE_CALL_P (insn));
3571
3572       if (!deps->readonly)
3573         {
3574           /* Remember the last function call for limiting lifetimes.  */
3575           free_INSN_LIST_list (&deps->last_function_call);
3576           deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3577
3578           if (call_may_noreturn_p (insn))
3579             {
3580               /* Remember the last function call that might not always return
3581                  normally for limiting moves of trapping insns.  */
3582               free_INSN_LIST_list (&deps->last_function_call_may_noreturn);
3583               deps->last_function_call_may_noreturn
3584                 = alloc_INSN_LIST (insn, NULL_RTX);
3585             }
3586
3587           /* Before reload, begin a post-call group, so as to keep the
3588              lifetimes of hard registers correct.  */
3589           if (! reload_completed)
3590             deps->in_post_call_group_p = post_call;
3591         }
3592     }
3593
3594   if (sched_deps_info->use_cselib)
3595     cselib_process_insn (insn);
3596
3597   /* EH_REGION insn notes can not appear until well after we complete
3598      scheduling.  */
3599   if (NOTE_P (insn))
3600     gcc_assert (NOTE_KIND (insn) != NOTE_INSN_EH_REGION_BEG
3601                 && NOTE_KIND (insn) != NOTE_INSN_EH_REGION_END);
3602
3603   if (sched_deps_info->finish_insn)
3604     sched_deps_info->finish_insn ();
3605
3606   /* Fixup the dependencies in the sched group.  */
3607   if ((NONJUMP_INSN_P (insn) || JUMP_P (insn))
3608       && SCHED_GROUP_P (insn) && !sel_sched_p ())
3609     fixup_sched_groups (insn);
3610 }
3611
3612 /* Initialize DEPS for the new block beginning with HEAD.  */
3613 void
3614 deps_start_bb (struct deps_desc *deps, rtx head)
3615 {
3616   gcc_assert (!deps->readonly);
3617
3618   /* Before reload, if the previous block ended in a call, show that
3619      we are inside a post-call group, so as to keep the lifetimes of
3620      hard registers correct.  */
3621   if (! reload_completed && !LABEL_P (head))
3622     {
3623       rtx insn = prev_nonnote_nondebug_insn (head);
3624
3625       if (insn && CALL_P (insn))
3626         deps->in_post_call_group_p = post_call_initial;
3627     }
3628 }
3629
3630 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3631    dependencies for each insn.  */
3632 void
3633 sched_analyze (struct deps_desc *deps, rtx head, rtx tail)
3634 {
3635   rtx insn;
3636
3637   if (sched_deps_info->use_cselib)
3638     cselib_init (CSELIB_RECORD_MEMORY);
3639
3640   deps_start_bb (deps, head);
3641
3642   for (insn = head;; insn = NEXT_INSN (insn))
3643     {
3644
3645       if (INSN_P (insn))
3646         {
3647           /* And initialize deps_lists.  */
3648           sd_init_insn (insn);
3649         }
3650
3651       deps_analyze_insn (deps, insn);
3652
3653       if (insn == tail)
3654         {
3655           if (sched_deps_info->use_cselib)
3656             cselib_finish ();
3657           return;
3658         }
3659     }
3660   gcc_unreachable ();
3661 }
3662
3663 /* Helper for sched_free_deps ().
3664    Delete INSN's (RESOLVED_P) backward dependencies.  */
3665 static void
3666 delete_dep_nodes_in_back_deps (rtx insn, bool resolved_p)
3667 {
3668   sd_iterator_def sd_it;
3669   dep_t dep;
3670   sd_list_types_def types;
3671
3672   if (resolved_p)
3673     types = SD_LIST_RES_BACK;
3674   else
3675     types = SD_LIST_BACK;
3676
3677   for (sd_it = sd_iterator_start (insn, types);
3678        sd_iterator_cond (&sd_it, &dep);)
3679     {
3680       dep_link_t link = *sd_it.linkp;
3681       dep_node_t node = DEP_LINK_NODE (link);
3682       deps_list_t back_list;
3683       deps_list_t forw_list;
3684
3685       get_back_and_forw_lists (dep, resolved_p, &back_list, &forw_list);
3686       remove_from_deps_list (link, back_list);
3687       delete_dep_node (node);
3688     }
3689 }
3690
3691 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3692    deps_lists.  */
3693 void
3694 sched_free_deps (rtx head, rtx tail, bool resolved_p)
3695 {
3696   rtx insn;
3697   rtx next_tail = NEXT_INSN (tail);
3698
3699   /* We make two passes since some insns may be scheduled before their
3700      dependencies are resolved.  */
3701   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3702     if (INSN_P (insn) && INSN_LUID (insn) > 0)
3703       {
3704         /* Clear forward deps and leave the dep_nodes to the
3705            corresponding back_deps list.  */
3706         if (resolved_p)
3707           clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
3708         else
3709           clear_deps_list (INSN_FORW_DEPS (insn));
3710       }
3711   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3712     if (INSN_P (insn) && INSN_LUID (insn) > 0)
3713       {
3714         /* Clear resolved back deps together with its dep_nodes.  */
3715         delete_dep_nodes_in_back_deps (insn, resolved_p);
3716
3717         sd_finish_insn (insn);
3718       }
3719 }
3720 \f
3721 /* Initialize variables for region data dependence analysis.
3722    When LAZY_REG_LAST is true, do not allocate reg_last array
3723    of struct deps_desc immediately.  */
3724
3725 void
3726 init_deps (struct deps_desc *deps, bool lazy_reg_last)
3727 {
3728   int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
3729
3730   deps->max_reg = max_reg;
3731   if (lazy_reg_last)
3732     deps->reg_last = NULL;
3733   else
3734     deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
3735   INIT_REG_SET (&deps->reg_last_in_use);
3736
3737   deps->pending_read_insns = 0;
3738   deps->pending_read_mems = 0;
3739   deps->pending_write_insns = 0;
3740   deps->pending_write_mems = 0;
3741   deps->pending_jump_insns = 0;
3742   deps->pending_read_list_length = 0;
3743   deps->pending_write_list_length = 0;
3744   deps->pending_flush_length = 0;
3745   deps->last_pending_memory_flush = 0;
3746   deps->last_function_call = 0;
3747   deps->last_function_call_may_noreturn = 0;
3748   deps->sched_before_next_call = 0;
3749   deps->sched_before_next_jump = 0;
3750   deps->in_post_call_group_p = not_post_call;
3751   deps->last_debug_insn = 0;
3752   deps->last_reg_pending_barrier = NOT_A_BARRIER;
3753   deps->readonly = 0;
3754 }
3755
3756 /* Init only reg_last field of DEPS, which was not allocated before as
3757    we inited DEPS lazily.  */
3758 void
3759 init_deps_reg_last (struct deps_desc *deps)
3760 {
3761   gcc_assert (deps && deps->max_reg > 0);
3762   gcc_assert (deps->reg_last == NULL);
3763
3764   deps->reg_last = XCNEWVEC (struct deps_reg, deps->max_reg);
3765 }
3766
3767
3768 /* Free insn lists found in DEPS.  */
3769
3770 void
3771 free_deps (struct deps_desc *deps)
3772 {
3773   unsigned i;
3774   reg_set_iterator rsi;
3775
3776   /* We set max_reg to 0 when this context was already freed.  */
3777   if (deps->max_reg == 0)
3778     {
3779       gcc_assert (deps->reg_last == NULL);
3780       return;
3781     }
3782   deps->max_reg = 0;
3783
3784   free_INSN_LIST_list (&deps->pending_read_insns);
3785   free_EXPR_LIST_list (&deps->pending_read_mems);
3786   free_INSN_LIST_list (&deps->pending_write_insns);
3787   free_EXPR_LIST_list (&deps->pending_write_mems);
3788   free_INSN_LIST_list (&deps->last_pending_memory_flush);
3789
3790   /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3791      times.  For a testcase with 42000 regs and 8000 small basic blocks,
3792      this loop accounted for nearly 60% (84 sec) of the total -O2 runtime.  */
3793   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3794     {
3795       struct deps_reg *reg_last = &deps->reg_last[i];
3796       if (reg_last->uses)
3797         free_INSN_LIST_list (&reg_last->uses);
3798       if (reg_last->sets)
3799         free_INSN_LIST_list (&reg_last->sets);
3800       if (reg_last->implicit_sets)
3801         free_INSN_LIST_list (&reg_last->implicit_sets);
3802       if (reg_last->control_uses)
3803         free_INSN_LIST_list (&reg_last->control_uses);
3804       if (reg_last->clobbers)
3805         free_INSN_LIST_list (&reg_last->clobbers);
3806     }
3807   CLEAR_REG_SET (&deps->reg_last_in_use);
3808
3809   /* As we initialize reg_last lazily, it is possible that we didn't allocate
3810      it at all.  */
3811   free (deps->reg_last);
3812   deps->reg_last = NULL;
3813
3814   deps = NULL;
3815 }
3816
3817 /* Remove INSN from dependence contexts DEPS.  */
3818 void
3819 remove_from_deps (struct deps_desc *deps, rtx insn)
3820 {
3821   int removed;
3822   unsigned i;
3823   reg_set_iterator rsi;
3824
3825   removed = remove_from_both_dependence_lists (insn, &deps->pending_read_insns,
3826                                                &deps->pending_read_mems);
3827   if (!DEBUG_INSN_P (insn))
3828     deps->pending_read_list_length -= removed;
3829   removed = remove_from_both_dependence_lists (insn, &deps->pending_write_insns,
3830                                                &deps->pending_write_mems);
3831   deps->pending_write_list_length -= removed;
3832
3833   removed = remove_from_dependence_list (insn, &deps->pending_jump_insns);
3834   deps->pending_flush_length -= removed;
3835   removed = remove_from_dependence_list (insn, &deps->last_pending_memory_flush);
3836   deps->pending_flush_length -= removed;
3837
3838   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3839     {
3840       struct deps_reg *reg_last = &deps->reg_last[i];
3841       if (reg_last->uses)
3842         remove_from_dependence_list (insn, &reg_last->uses);
3843       if (reg_last->sets)
3844         remove_from_dependence_list (insn, &reg_last->sets);
3845       if (reg_last->implicit_sets)
3846         remove_from_dependence_list (insn, &reg_last->implicit_sets);
3847       if (reg_last->clobbers)
3848         remove_from_dependence_list (insn, &reg_last->clobbers);
3849       if (!reg_last->uses && !reg_last->sets && !reg_last->implicit_sets
3850           && !reg_last->clobbers)
3851         CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, i);
3852     }
3853
3854   if (CALL_P (insn))
3855     {
3856       remove_from_dependence_list (insn, &deps->last_function_call);
3857       remove_from_dependence_list (insn,
3858                                    &deps->last_function_call_may_noreturn);
3859     }
3860   remove_from_dependence_list (insn, &deps->sched_before_next_call);
3861 }
3862
3863 /* Init deps data vector.  */
3864 static void
3865 init_deps_data_vector (void)
3866 {
3867   int reserve = (sched_max_luid + 1
3868                  - VEC_length (haifa_deps_insn_data_def, h_d_i_d));
3869   if (reserve > 0
3870       && ! VEC_space (haifa_deps_insn_data_def, h_d_i_d, reserve))
3871     VEC_safe_grow_cleared (haifa_deps_insn_data_def, heap, h_d_i_d,
3872                            3 * sched_max_luid / 2);
3873 }
3874
3875 /* If it is profitable to use them, initialize or extend (depending on
3876    GLOBAL_P) dependency data.  */
3877 void
3878 sched_deps_init (bool global_p)
3879 {
3880   /* Average number of insns in the basic block.
3881      '+ 1' is used to make it nonzero.  */
3882   int insns_in_block = sched_max_luid / n_basic_blocks + 1;
3883
3884   init_deps_data_vector ();
3885
3886   /* We use another caching mechanism for selective scheduling, so
3887      we don't use this one.  */
3888   if (!sel_sched_p () && global_p && insns_in_block > 100 * 5)
3889     {
3890       /* ?!? We could save some memory by computing a per-region luid mapping
3891          which could reduce both the number of vectors in the cache and the
3892          size of each vector.  Instead we just avoid the cache entirely unless
3893          the average number of instructions in a basic block is very high.  See
3894          the comment before the declaration of true_dependency_cache for
3895          what we consider "very high".  */
3896       cache_size = 0;
3897       extend_dependency_caches (sched_max_luid, true);
3898     }
3899
3900   if (global_p)
3901     {
3902       dl_pool = create_alloc_pool ("deps_list", sizeof (struct _deps_list),
3903                                    /* Allocate lists for one block at a time.  */
3904                                    insns_in_block);
3905       dn_pool = create_alloc_pool ("dep_node", sizeof (struct _dep_node),
3906                                    /* Allocate nodes for one block at a time.
3907                                       We assume that average insn has
3908                                       5 producers.  */
3909                                    5 * insns_in_block);
3910     }
3911 }
3912
3913
3914 /* Create or extend (depending on CREATE_P) dependency caches to
3915    size N.  */
3916 void
3917 extend_dependency_caches (int n, bool create_p)
3918 {
3919   if (create_p || true_dependency_cache)
3920     {
3921       int i, luid = cache_size + n;
3922
3923       true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
3924                                           luid);
3925       output_dependency_cache = XRESIZEVEC (bitmap_head,
3926                                             output_dependency_cache, luid);
3927       anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
3928                                           luid);
3929       control_dependency_cache = XRESIZEVEC (bitmap_head, control_dependency_cache,
3930                                           luid);
3931
3932       if (current_sched_info->flags & DO_SPECULATION)
3933         spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
3934                                             luid);
3935
3936       for (i = cache_size; i < luid; i++)
3937         {
3938           bitmap_initialize (&true_dependency_cache[i], 0);
3939           bitmap_initialize (&output_dependency_cache[i], 0);
3940           bitmap_initialize (&anti_dependency_cache[i], 0);
3941           bitmap_initialize (&control_dependency_cache[i], 0);
3942
3943           if (current_sched_info->flags & DO_SPECULATION)
3944             bitmap_initialize (&spec_dependency_cache[i], 0);
3945         }
3946       cache_size = luid;
3947     }
3948 }
3949
3950 /* Finalize dependency information for the whole function.  */
3951 void
3952 sched_deps_finish (void)
3953 {
3954   gcc_assert (deps_pools_are_empty_p ());
3955   free_alloc_pool_if_empty (&dn_pool);
3956   free_alloc_pool_if_empty (&dl_pool);
3957   gcc_assert (dn_pool == NULL && dl_pool == NULL);
3958
3959   VEC_free (haifa_deps_insn_data_def, heap, h_d_i_d);
3960   cache_size = 0;
3961
3962   if (true_dependency_cache)
3963     {
3964       int i;
3965
3966       for (i = 0; i < cache_size; i++)
3967         {
3968           bitmap_clear (&true_dependency_cache[i]);
3969           bitmap_clear (&output_dependency_cache[i]);
3970           bitmap_clear (&anti_dependency_cache[i]);
3971           bitmap_clear (&control_dependency_cache[i]);
3972
3973           if (sched_deps_info->generate_spec_deps)
3974             bitmap_clear (&spec_dependency_cache[i]);
3975         }
3976       free (true_dependency_cache);
3977       true_dependency_cache = NULL;
3978       free (output_dependency_cache);
3979       output_dependency_cache = NULL;
3980       free (anti_dependency_cache);
3981       anti_dependency_cache = NULL;
3982       free (control_dependency_cache);
3983       control_dependency_cache = NULL;
3984
3985       if (sched_deps_info->generate_spec_deps)
3986         {
3987           free (spec_dependency_cache);
3988           spec_dependency_cache = NULL;
3989         }
3990
3991     }
3992 }
3993
3994 /* Initialize some global variables needed by the dependency analysis
3995    code.  */
3996
3997 void
3998 init_deps_global (void)
3999 {
4000   CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
4001   CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
4002   reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
4003   reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
4004   reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
4005   reg_pending_control_uses = ALLOC_REG_SET (&reg_obstack);
4006   reg_pending_barrier = NOT_A_BARRIER;
4007
4008   if (!sel_sched_p () || sched_emulate_haifa_p)
4009     {
4010       sched_deps_info->start_insn = haifa_start_insn;
4011       sched_deps_info->finish_insn = haifa_finish_insn;
4012
4013       sched_deps_info->note_reg_set = haifa_note_reg_set;
4014       sched_deps_info->note_reg_clobber = haifa_note_reg_clobber;
4015       sched_deps_info->note_reg_use = haifa_note_reg_use;
4016
4017       sched_deps_info->note_mem_dep = haifa_note_mem_dep;
4018       sched_deps_info->note_dep = haifa_note_dep;
4019    }
4020 }
4021
4022 /* Free everything used by the dependency analysis code.  */
4023
4024 void
4025 finish_deps_global (void)
4026 {
4027   FREE_REG_SET (reg_pending_sets);
4028   FREE_REG_SET (reg_pending_clobbers);
4029   FREE_REG_SET (reg_pending_uses);
4030   FREE_REG_SET (reg_pending_control_uses);
4031 }
4032
4033 /* Estimate the weakness of dependence between MEM1 and MEM2.  */
4034 dw_t
4035 estimate_dep_weak (rtx mem1, rtx mem2)
4036 {
4037   rtx r1, r2;
4038
4039   if (mem1 == mem2)
4040     /* MEMs are the same - don't speculate.  */
4041     return MIN_DEP_WEAK;
4042
4043   r1 = XEXP (mem1, 0);
4044   r2 = XEXP (mem2, 0);
4045
4046   if (r1 == r2
4047       || (REG_P (r1) && REG_P (r2)
4048           && REGNO (r1) == REGNO (r2)))
4049     /* Again, MEMs are the same.  */
4050     return MIN_DEP_WEAK;
4051   else if ((REG_P (r1) && !REG_P (r2))
4052            || (!REG_P (r1) && REG_P (r2)))
4053     /* Different addressing modes - reason to be more speculative,
4054        than usual.  */
4055     return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
4056   else
4057     /* We can't say anything about the dependence.  */
4058     return UNCERTAIN_DEP_WEAK;
4059 }
4060
4061 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
4062    This function can handle same INSN and ELEM (INSN == ELEM).
4063    It is a convenience wrapper.  */
4064 static void
4065 add_dependence_1 (rtx insn, rtx elem, enum reg_note dep_type)
4066 {
4067   ds_t ds;
4068   bool internal;
4069
4070   if (dep_type == REG_DEP_TRUE)
4071     ds = DEP_TRUE;
4072   else if (dep_type == REG_DEP_OUTPUT)
4073     ds = DEP_OUTPUT;
4074   else if (dep_type == REG_DEP_CONTROL)
4075     ds = DEP_CONTROL;
4076   else
4077     {
4078       gcc_assert (dep_type == REG_DEP_ANTI);
4079       ds = DEP_ANTI;
4080     }
4081
4082   /* When add_dependence is called from inside sched-deps.c, we expect
4083      cur_insn to be non-null.  */
4084   internal = cur_insn != NULL;
4085   if (internal)
4086     gcc_assert (insn == cur_insn);
4087   else
4088     cur_insn = insn;
4089
4090   note_dep (elem, ds);
4091   if (!internal)
4092     cur_insn = NULL;
4093 }
4094
4095 /* Return weakness of speculative type TYPE in the dep_status DS.  */
4096 dw_t
4097 get_dep_weak_1 (ds_t ds, ds_t type)
4098 {
4099   ds = ds & type;
4100
4101   switch (type)
4102     {
4103     case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
4104     case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
4105     case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
4106     case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
4107     default: gcc_unreachable ();
4108     }
4109
4110   return (dw_t) ds;
4111 }
4112
4113 dw_t
4114 get_dep_weak (ds_t ds, ds_t type)
4115 {
4116   dw_t dw = get_dep_weak_1 (ds, type);
4117
4118   gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4119   return dw;
4120 }
4121
4122 /* Return the dep_status, which has the same parameters as DS, except for
4123    speculative type TYPE, that will have weakness DW.  */
4124 ds_t
4125 set_dep_weak (ds_t ds, ds_t type, dw_t dw)
4126 {
4127   gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4128
4129   ds &= ~type;
4130   switch (type)
4131     {
4132     case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
4133     case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
4134     case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
4135     case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
4136     default: gcc_unreachable ();
4137     }
4138   return ds;
4139 }
4140
4141 /* Return the join of two dep_statuses DS1 and DS2.
4142    If MAX_P is true then choose the greater probability,
4143    otherwise multiply probabilities.
4144    This function assumes that both DS1 and DS2 contain speculative bits.  */
4145 static ds_t
4146 ds_merge_1 (ds_t ds1, ds_t ds2, bool max_p)
4147 {
4148   ds_t ds, t;
4149
4150   gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
4151
4152   ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
4153
4154   t = FIRST_SPEC_TYPE;
4155   do
4156     {
4157       if ((ds1 & t) && !(ds2 & t))
4158         ds |= ds1 & t;
4159       else if (!(ds1 & t) && (ds2 & t))
4160         ds |= ds2 & t;
4161       else if ((ds1 & t) && (ds2 & t))
4162         {
4163           dw_t dw1 = get_dep_weak (ds1, t);
4164           dw_t dw2 = get_dep_weak (ds2, t);
4165           ds_t dw;
4166
4167           if (!max_p)
4168             {
4169               dw = ((ds_t) dw1) * ((ds_t) dw2);
4170               dw /= MAX_DEP_WEAK;
4171               if (dw < MIN_DEP_WEAK)
4172                 dw = MIN_DEP_WEAK;
4173             }
4174           else
4175             {
4176               if (dw1 >= dw2)
4177                 dw = dw1;
4178               else
4179                 dw = dw2;
4180             }
4181
4182           ds = set_dep_weak (ds, t, (dw_t) dw);
4183         }
4184
4185       if (t == LAST_SPEC_TYPE)
4186         break;
4187       t <<= SPEC_TYPE_SHIFT;
4188     }
4189   while (1);
4190
4191   return ds;
4192 }
4193
4194 /* Return the join of two dep_statuses DS1 and DS2.
4195    This function assumes that both DS1 and DS2 contain speculative bits.  */
4196 ds_t
4197 ds_merge (ds_t ds1, ds_t ds2)
4198 {
4199   return ds_merge_1 (ds1, ds2, false);
4200 }
4201
4202 /* Return the join of two dep_statuses DS1 and DS2.  */
4203 ds_t
4204 ds_full_merge (ds_t ds, ds_t ds2, rtx mem1, rtx mem2)
4205 {
4206   ds_t new_status = ds | ds2;
4207
4208   if (new_status & SPECULATIVE)
4209     {
4210       if ((ds && !(ds & SPECULATIVE))
4211           || (ds2 && !(ds2 & SPECULATIVE)))
4212         /* Then this dep can't be speculative.  */
4213         new_status &= ~SPECULATIVE;
4214       else
4215         {
4216           /* Both are speculative.  Merging probabilities.  */
4217           if (mem1)
4218             {
4219               dw_t dw;
4220
4221               dw = estimate_dep_weak (mem1, mem2);
4222               ds = set_dep_weak (ds, BEGIN_DATA, dw);
4223             }
4224
4225           if (!ds)
4226             new_status = ds2;
4227           else if (!ds2)
4228             new_status = ds;
4229           else
4230             new_status = ds_merge (ds2, ds);
4231         }
4232     }
4233
4234   return new_status;
4235 }
4236
4237 /* Return the join of DS1 and DS2.  Use maximum instead of multiplying
4238    probabilities.  */
4239 ds_t
4240 ds_max_merge (ds_t ds1, ds_t ds2)
4241 {
4242   if (ds1 == 0 && ds2 == 0)
4243     return 0;
4244
4245   if (ds1 == 0 && ds2 != 0)
4246     return ds2;
4247
4248   if (ds1 != 0 && ds2 == 0)
4249     return ds1;
4250
4251   return ds_merge_1 (ds1, ds2, true);
4252 }
4253
4254 /* Return the probability of speculation success for the speculation
4255    status DS.  */
4256 dw_t
4257 ds_weak (ds_t ds)
4258 {
4259   ds_t res = 1, dt;
4260   int n = 0;
4261
4262   dt = FIRST_SPEC_TYPE;
4263   do
4264     {
4265       if (ds & dt)
4266         {
4267           res *= (ds_t) get_dep_weak (ds, dt);
4268           n++;
4269         }
4270
4271       if (dt == LAST_SPEC_TYPE)
4272         break;
4273       dt <<= SPEC_TYPE_SHIFT;
4274     }
4275   while (1);
4276
4277   gcc_assert (n);
4278   while (--n)
4279     res /= MAX_DEP_WEAK;
4280
4281   if (res < MIN_DEP_WEAK)
4282     res = MIN_DEP_WEAK;
4283
4284   gcc_assert (res <= MAX_DEP_WEAK);
4285
4286   return (dw_t) res;
4287 }
4288
4289 /* Return a dep status that contains all speculation types of DS.  */
4290 ds_t
4291 ds_get_speculation_types (ds_t ds)
4292 {
4293   if (ds & BEGIN_DATA)
4294     ds |= BEGIN_DATA;
4295   if (ds & BE_IN_DATA)
4296     ds |= BE_IN_DATA;
4297   if (ds & BEGIN_CONTROL)
4298     ds |= BEGIN_CONTROL;
4299   if (ds & BE_IN_CONTROL)
4300     ds |= BE_IN_CONTROL;
4301
4302   return ds & SPECULATIVE;
4303 }
4304
4305 /* Return a dep status that contains maximal weakness for each speculation
4306    type present in DS.  */
4307 ds_t
4308 ds_get_max_dep_weak (ds_t ds)
4309 {
4310   if (ds & BEGIN_DATA)
4311     ds = set_dep_weak (ds, BEGIN_DATA, MAX_DEP_WEAK);
4312   if (ds & BE_IN_DATA)
4313     ds = set_dep_weak (ds, BE_IN_DATA, MAX_DEP_WEAK);
4314   if (ds & BEGIN_CONTROL)
4315     ds = set_dep_weak (ds, BEGIN_CONTROL, MAX_DEP_WEAK);
4316   if (ds & BE_IN_CONTROL)
4317     ds = set_dep_weak (ds, BE_IN_CONTROL, MAX_DEP_WEAK);
4318
4319   return ds;
4320 }
4321
4322 /* Dump information about the dependence status S.  */
4323 static void
4324 dump_ds (FILE *f, ds_t s)
4325 {
4326   fprintf (f, "{");
4327
4328   if (s & BEGIN_DATA)
4329     fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak_1 (s, BEGIN_DATA));
4330   if (s & BE_IN_DATA)
4331     fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak_1 (s, BE_IN_DATA));
4332   if (s & BEGIN_CONTROL)
4333     fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s, BEGIN_CONTROL));
4334   if (s & BE_IN_CONTROL)
4335     fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s, BE_IN_CONTROL));
4336
4337   if (s & HARD_DEP)
4338     fprintf (f, "HARD_DEP; ");
4339
4340   if (s & DEP_TRUE)
4341     fprintf (f, "DEP_TRUE; ");
4342   if (s & DEP_OUTPUT)
4343     fprintf (f, "DEP_OUTPUT; ");
4344   if (s & DEP_ANTI)
4345     fprintf (f, "DEP_ANTI; ");
4346   if (s & DEP_CONTROL)
4347     fprintf (f, "DEP_CONTROL; ");
4348
4349   fprintf (f, "}");
4350 }
4351
4352 DEBUG_FUNCTION void
4353 debug_ds (ds_t s)
4354 {
4355   dump_ds (stderr, s);
4356   fprintf (stderr, "\n");
4357 }
4358
4359 #ifdef ENABLE_CHECKING
4360 /* Verify that dependence type and status are consistent.
4361    If RELAXED_P is true, then skip dep_weakness checks.  */
4362 static void
4363 check_dep (dep_t dep, bool relaxed_p)
4364 {
4365   enum reg_note dt = DEP_TYPE (dep);
4366   ds_t ds = DEP_STATUS (dep);
4367
4368   gcc_assert (DEP_PRO (dep) != DEP_CON (dep));
4369
4370   if (!(current_sched_info->flags & USE_DEPS_LIST))
4371     {
4372       gcc_assert (ds == 0);
4373       return;
4374     }
4375
4376   /* Check that dependence type contains the same bits as the status.  */
4377   if (dt == REG_DEP_TRUE)
4378     gcc_assert (ds & DEP_TRUE);
4379   else if (dt == REG_DEP_OUTPUT)
4380     gcc_assert ((ds & DEP_OUTPUT)
4381                 && !(ds & DEP_TRUE));
4382   else if (dt == REG_DEP_ANTI)
4383     gcc_assert ((ds & DEP_ANTI)
4384                 && !(ds & (DEP_OUTPUT | DEP_TRUE)));
4385   else
4386     gcc_assert (dt == REG_DEP_CONTROL
4387                 && (ds & DEP_CONTROL)
4388                 && !(ds & (DEP_OUTPUT | DEP_ANTI | DEP_TRUE)));
4389
4390   /* HARD_DEP can not appear in dep_status of a link.  */
4391   gcc_assert (!(ds & HARD_DEP));
4392
4393   /* Check that dependence status is set correctly when speculation is not
4394      supported.  */
4395   if (!sched_deps_info->generate_spec_deps)
4396     gcc_assert (!(ds & SPECULATIVE));
4397   else if (ds & SPECULATIVE)
4398     {
4399       if (!relaxed_p)
4400         {
4401           ds_t type = FIRST_SPEC_TYPE;
4402
4403           /* Check that dependence weakness is in proper range.  */
4404           do
4405             {
4406               if (ds & type)
4407                 get_dep_weak (ds, type);
4408
4409               if (type == LAST_SPEC_TYPE)
4410                 break;
4411               type <<= SPEC_TYPE_SHIFT;
4412             }
4413           while (1);
4414         }
4415
4416       if (ds & BEGIN_SPEC)
4417         {
4418           /* Only true dependence can be data speculative.  */
4419           if (ds & BEGIN_DATA)
4420             gcc_assert (ds & DEP_TRUE);
4421
4422           /* Control dependencies in the insn scheduler are represented by
4423              anti-dependencies, therefore only anti dependence can be
4424              control speculative.  */
4425           if (ds & BEGIN_CONTROL)
4426             gcc_assert (ds & DEP_ANTI);
4427         }
4428       else
4429         {
4430           /* Subsequent speculations should resolve true dependencies.  */
4431           gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
4432         }
4433
4434       /* Check that true and anti dependencies can't have other speculative
4435          statuses.  */
4436       if (ds & DEP_TRUE)
4437         gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
4438       /* An output dependence can't be speculative at all.  */
4439       gcc_assert (!(ds & DEP_OUTPUT));
4440       if (ds & DEP_ANTI)
4441         gcc_assert (ds & BEGIN_CONTROL);
4442     }
4443 }
4444 #endif /* ENABLE_CHECKING */
4445
4446 #endif /* INSN_SCHEDULING */