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