gcc/sched-deps.c

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