gcc/sched-deps.c

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