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
   5    Free Software Foundation, Inc.
   6    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
   7    and currently maintained by, Jim Wilson (wilson@cygnus.com)
   8
   9 This file is part of GCC.
  10
  11 GCC is free software; you can redistribute it and/or modify it under
  12 the terms of the GNU General Public License as published by the Free
  13 Software Foundation; either version 3, or (at your option) any later
  14 version.
  15
  16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  18 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  19 for more details.
  20
  21 You should have received a copy of the GNU General Public License
  22 along with GCC; see the file COPYING3.  If not see
  23 <http://www.gnu.org/licenses/>.  */
  24 \f
  25 #include "config.h"
  26 #include "system.h"
  27 #include "coretypes.h"
  28 #include "tm.h"
  29 #include "toplev.h"
  30 #include "rtl.h"
  31 #include "tm_p.h"
  32 #include "hard-reg-set.h"
  33 #include "regs.h"
  34 #include "function.h"
  35 #include "flags.h"
  36 #include "insn-config.h"
  37 #include "insn-attr.h"
  38 #include "except.h"
  39 #include "toplev.h"
  40 #include "recog.h"
  41 #include "sched-int.h"
  42 #include "params.h"
  43 #include "cselib.h"
  44
  45 #ifdef INSN_SCHEDULING
  46
  47 #ifdef ENABLE_CHECKING
  48 #define CHECK (true)
  49 #else
  50 #define CHECK (false)
  51 #endif
  52
  53 /* Return the major type present in the DS.  */
  54 enum reg_note
  55 ds_to_dk (ds_t ds)
  56 {
  57   if (ds & DEP_TRUE)
  58     return REG_DEP_TRUE;
  59
  60   if (ds & DEP_OUTPUT)
  61     return REG_DEP_OUTPUT;
  62
  63   gcc_assert (ds & DEP_ANTI);
  64
  65   return REG_DEP_ANTI;
  66 }
  67
  68 /* Return equivalent dep_status.  */
  69 ds_t
  70 dk_to_ds (enum reg_note dk)
  71 {
  72   switch (dk)
  73     {
  74     case REG_DEP_TRUE:
  75       return DEP_TRUE;
  76
  77     case REG_DEP_OUTPUT:
  78       return DEP_OUTPUT;
  79
  80     default:
  81       gcc_assert (dk == REG_DEP_ANTI);
  82       return DEP_ANTI;
  83     }
  84 }
  85
  86 /* Functions to operate with dependence information container - dep_t.  */
  87
  88 /* Init DEP with the arguments.  */
  89 void
  90 init_dep_1 (dep_t dep, rtx pro, rtx con, enum reg_note type, ds_t ds)
  91 {
  92   DEP_PRO (dep) = pro;
  93   DEP_CON (dep) = con;
  94   DEP_TYPE (dep) = type;
  95   DEP_STATUS (dep) = ds;
  96 }
  97
  98 /* Init DEP with the arguments.
  99    While most of the scheduler (including targets) only need the major type
 100    of the dependency, it is convenient to hide full dep_status from them.  */
 101 void
 102 init_dep (dep_t dep, rtx pro, rtx con, enum reg_note kind)
 103 {
 104   ds_t ds;
 105
 106   if ((current_sched_info->flags & USE_DEPS_LIST))
 107     ds = dk_to_ds (kind);
 108   else
 109     ds = -1;
 110
 111   init_dep_1 (dep, pro, con, kind, ds);
 112 }
 113
 114 /* Make a copy of FROM in TO.  */
 115 static void
 116 copy_dep (dep_t to, dep_t from)
 117 {
 118   memcpy (to, from, sizeof (*to));
 119 }
 120
 121 static void dump_ds (FILE *, ds_t);
 122
 123 /* Define flags for dump_dep ().  */
 124
 125 /* Dump producer of the dependence.  */
 126 #define DUMP_DEP_PRO (2)
 127
 128 /* Dump consumer of the dependence.  */
 129 #define DUMP_DEP_CON (4)
 130
 131 /* Dump type of the dependence.  */
 132 #define DUMP_DEP_TYPE (8)
 133
 134 /* Dump status of the dependence.  */
 135 #define DUMP_DEP_STATUS (16)
 136
 137 /* Dump all information about the dependence.  */
 138 #define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE       \
 139                       |DUMP_DEP_STATUS)
 140
 141 /* Dump DEP to DUMP.
 142    FLAGS is a bit mask specifying what information about DEP needs
 143    to be printed.
 144    If FLAGS has the very first bit set, then dump all information about DEP
 145    and propagate this bit into the callee dump functions.  */
 146 static void
 147 dump_dep (FILE *dump, dep_t dep, int flags)
 148 {
 149   if (flags & 1)
 150     flags |= DUMP_DEP_ALL;
 151
 152   fprintf (dump, "<");
 153
 154   if (flags & DUMP_DEP_PRO)
 155     fprintf (dump, "%d; ", INSN_UID (DEP_PRO (dep)));
 156
 157   if (flags & DUMP_DEP_CON)
 158     fprintf (dump, "%d; ", INSN_UID (DEP_CON (dep)));
 159
 160   if (flags & DUMP_DEP_TYPE)
 161     {
 162       char t;
 163       enum reg_note type = DEP_TYPE (dep);
 164
 165       switch (type)
 166         {
 167         case REG_DEP_TRUE:
 168           t = 't';
 169           break;
 170
 171         case REG_DEP_OUTPUT:
 172           t = 'o';
 173           break;
 174
 175         case REG_DEP_ANTI:
 176           t = 'a';
 177           break;
 178
 179         default:
 180           gcc_unreachable ();
 181           break;
 182         }
 183
 184       fprintf (dump, "%c; ", t);
 185     }
 186
 187   if (flags & DUMP_DEP_STATUS)
 188     {
 189       if (current_sched_info->flags & USE_DEPS_LIST)
 190         dump_ds (dump, DEP_STATUS (dep));
 191     }
 192
 193   fprintf (dump, ">");
 194 }
 195
 196 /* Default flags for dump_dep ().  */
 197 static int dump_dep_flags = (DUMP_DEP_PRO | DUMP_DEP_CON);
 198
 199 /* Dump all fields of DEP to STDERR.  */
 200 void
 201 sd_debug_dep (dep_t dep)
 202 {
 203   dump_dep (stderr, dep, 1);
 204   fprintf (stderr, "\n");
 205 }
 206
 207 /* Functions to operate with a single link from the dependencies lists -
 208    dep_link_t.  */
 209
 210 /* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
 211    PREV_NEXT_P.  */
 212 static void
 213 attach_dep_link (dep_link_t l, dep_link_t *prev_nextp)
 214 {
 215   dep_link_t next = *prev_nextp;
 216
 217   gcc_assert (DEP_LINK_PREV_NEXTP (l) == NULL
 218               && DEP_LINK_NEXT (l) == NULL);
 219
 220   /* Init node being inserted.  */
 221   DEP_LINK_PREV_NEXTP (l) = prev_nextp;
 222   DEP_LINK_NEXT (l) = next;
 223
 224   /* Fix next node.  */
 225   if (next != NULL)
 226     {
 227       gcc_assert (DEP_LINK_PREV_NEXTP (next) == prev_nextp);
 228
 229       DEP_LINK_PREV_NEXTP (next) = &DEP_LINK_NEXT (l);
 230     }
 231
 232   /* Fix prev node.  */
 233   *prev_nextp = l;
 234 }
 235
 236 /* Add dep_link LINK to deps_list L.  */
 237 static void
 238 add_to_deps_list (dep_link_t link, deps_list_t l)
 239 {
 240   attach_dep_link (link, &DEPS_LIST_FIRST (l));
 241
 242   ++DEPS_LIST_N_LINKS (l);
 243 }
 244
 245 /* Detach dep_link L from the list.  */
 246 static void
 247 detach_dep_link (dep_link_t l)
 248 {
 249   dep_link_t *prev_nextp = DEP_LINK_PREV_NEXTP (l);
 250   dep_link_t next = DEP_LINK_NEXT (l);
 251
 252   *prev_nextp = next;
 253
 254   if (next != NULL)
 255     DEP_LINK_PREV_NEXTP (next) = prev_nextp;
 256
 257   DEP_LINK_PREV_NEXTP (l) = NULL;
 258   DEP_LINK_NEXT (l) = NULL;
 259 }
 260
 261 /* Remove link LINK from list LIST.  */
 262 static void
 263 remove_from_deps_list (dep_link_t link, deps_list_t list)
 264 {
 265   detach_dep_link (link);
 266
 267   --DEPS_LIST_N_LINKS (list);
 268 }
 269
 270 /* Move link LINK from list FROM to list TO.  */
 271 static void
 272 move_dep_link (dep_link_t link, deps_list_t from, deps_list_t to)
 273 {
 274   remove_from_deps_list (link, from);
 275   add_to_deps_list (link, to);
 276 }
 277
 278 /* Return true of LINK is not attached to any list.  */
 279 static bool
 280 dep_link_is_detached_p (dep_link_t link)
 281 {
 282   return DEP_LINK_PREV_NEXTP (link) == NULL;
 283 }
 284
 285 /* Pool to hold all dependency nodes (dep_node_t).  */
 286 static alloc_pool dn_pool;
 287
 288 /* Number of dep_nodes out there.  */
 289 static int dn_pool_diff = 0;
 290
 291 /* Create a dep_node.  */
 292 static dep_node_t
 293 create_dep_node (void)
 294 {
 295   dep_node_t n = (dep_node_t) pool_alloc (dn_pool);
 296   dep_link_t back = DEP_NODE_BACK (n);
 297   dep_link_t forw = DEP_NODE_FORW (n);
 298
 299   DEP_LINK_NODE (back) = n;
 300   DEP_LINK_NEXT (back) = NULL;
 301   DEP_LINK_PREV_NEXTP (back) = NULL;
 302
 303   DEP_LINK_NODE (forw) = n;
 304   DEP_LINK_NEXT (forw) = NULL;
 305   DEP_LINK_PREV_NEXTP (forw) = NULL;
 306
 307   ++dn_pool_diff;
 308
 309   return n;
 310 }
 311
 312 /* Delete dep_node N.  N must not be connected to any deps_list.  */
 313 static void
 314 delete_dep_node (dep_node_t n)
 315 {
 316   gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n))
 317               && dep_link_is_detached_p (DEP_NODE_FORW (n)));
 318
 319   --dn_pool_diff;
 320
 321   pool_free (dn_pool, n);
 322 }
 323
 324 /* Pool to hold dependencies lists (deps_list_t).  */
 325 static alloc_pool dl_pool;
 326
 327 /* Number of deps_lists out there.  */
 328 static int dl_pool_diff = 0;
 329
 330 /* Functions to operate with dependences lists - deps_list_t.  */
 331
 332 /* Return true if list L is empty.  */
 333 static bool
 334 deps_list_empty_p (deps_list_t l)
 335 {
 336   return DEPS_LIST_N_LINKS (l) == 0;
 337 }
 338
 339 /* Create a new deps_list.  */
 340 static deps_list_t
 341 create_deps_list (void)
 342 {
 343   deps_list_t l = (deps_list_t) pool_alloc (dl_pool);
 344
 345   DEPS_LIST_FIRST (l) = NULL;
 346   DEPS_LIST_N_LINKS (l) = 0;
 347
 348   ++dl_pool_diff;
 349   return l;
 350 }
 351
 352 /* Free deps_list L.  */
 353 static void
 354 free_deps_list (deps_list_t l)
 355 {
 356   gcc_assert (deps_list_empty_p (l));
 357
 358   --dl_pool_diff;
 359
 360   pool_free (dl_pool, l);
 361 }
 362
 363 /* Return true if there is no dep_nodes and deps_lists out there.
 364    After the region is scheduled all the dependency nodes and lists
 365    should [generally] be returned to pool.  */
 366 bool
 367 deps_pools_are_empty_p (void)
 368 {
 369   return dn_pool_diff == 0 && dl_pool_diff == 0;
 370 }
 371
 372 /* Remove all elements from L.  */
 373 static void
 374 clear_deps_list (deps_list_t l)
 375 {
 376   do
 377     {
 378       dep_link_t link = DEPS_LIST_FIRST (l);
 379
 380       if (link == NULL)
 381         break;
 382
 383       remove_from_deps_list (link, l);
 384     }
 385   while (1);
 386 }
 387
 388 static regset reg_pending_sets;
 389 static regset reg_pending_clobbers;
 390 static regset reg_pending_uses;
 391
 392 /* The following enumeration values tell us what dependencies we
 393    should use to implement the barrier.  We use true-dependencies for
 394    TRUE_BARRIER and anti-dependencies for MOVE_BARRIER.  */
 395 enum reg_pending_barrier_mode
 396 {
 397   NOT_A_BARRIER = 0,
 398   MOVE_BARRIER,
 399   TRUE_BARRIER
 400 };
 401
 402 static enum reg_pending_barrier_mode reg_pending_barrier;
 403
 404 /* To speed up the test for duplicate dependency links we keep a
 405    record of dependencies created by add_dependence when the average
 406    number of instructions in a basic block is very large.
 407
 408    Studies have shown that there is typically around 5 instructions between
 409    branches for typical C code.  So we can make a guess that the average
 410    basic block is approximately 5 instructions long; we will choose 100X
 411    the average size as a very large basic block.
 412
 413    Each insn has associated bitmaps for its dependencies.  Each bitmap
 414    has enough entries to represent a dependency on any other insn in
 415    the insn chain.  All bitmap for true dependencies cache is
 416    allocated then the rest two ones are also allocated.  */
 417 static bitmap_head *true_dependency_cache;
 418 static bitmap_head *output_dependency_cache;
 419 static bitmap_head *anti_dependency_cache;
 420 static bitmap_head *spec_dependency_cache;
 421 static int cache_size;
 422
 423 static int deps_may_trap_p (const_rtx);
 424 static void add_dependence_list (rtx, rtx, int, enum reg_note);
 425 static void add_dependence_list_and_free (rtx, rtx *, int, enum reg_note);
 426 static void delete_all_dependences (rtx);
 427 static void fixup_sched_groups (rtx);
 428
 429 static void flush_pending_lists (struct deps *, rtx, int, int);
 430 static void sched_analyze_1 (struct deps *, rtx, rtx);
 431 static void sched_analyze_2 (struct deps *, rtx, rtx);
 432 static void sched_analyze_insn (struct deps *, rtx, rtx);
 433
 434 static rtx sched_get_condition (const_rtx);
 435 static int conditions_mutex_p (const_rtx, const_rtx);
 436
 437 static enum DEPS_ADJUST_RESULT maybe_add_or_update_dep_1 (dep_t, bool,
 438                                                           rtx, rtx);
 439 static enum DEPS_ADJUST_RESULT add_or_update_dep_1 (dep_t, bool, rtx, rtx);
 440
 441 static dw_t estimate_dep_weak (rtx, rtx);
 442 #ifdef ENABLE_CHECKING
 443 static void check_dep (dep_t, bool);
 444 #endif
 445 \f
 446 /* Return nonzero if a load of the memory reference MEM can cause a trap.  */
 447
 448 static int
 449 deps_may_trap_p (const_rtx mem)
 450 {
 451   const_rtx addr = XEXP (mem, 0);
 452
 453   if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
 454     {
 455       const_rtx t = get_reg_known_value (REGNO (addr));
 456       if (t)
 457         addr = t;
 458     }
 459   return rtx_addr_can_trap_p (addr);
 460 }
 461 \f
 462 /* Find the condition under which INSN is executed.  */
 463
 464 static rtx
 465 sched_get_condition (const_rtx insn)
 466 {
 467   rtx pat = PATTERN (insn);
 468   rtx src;
 469
 470   if (pat == 0)
 471     return 0;
 472
 473   if (GET_CODE (pat) == COND_EXEC)
 474     return COND_EXEC_TEST (pat);
 475
 476   if (!any_condjump_p (insn) || !onlyjump_p (insn))
 477     return 0;
 478
 479   src = SET_SRC (pc_set (insn));
 480
 481   if (XEXP (src, 2) == pc_rtx)
 482     return XEXP (src, 0);
 483   else if (XEXP (src, 1) == pc_rtx)
 484     {
 485       rtx cond = XEXP (src, 0);
 486       enum rtx_code revcode = reversed_comparison_code (cond, insn);
 487
 488       if (revcode == UNKNOWN)
 489         return 0;
 490       return gen_rtx_fmt_ee (revcode, GET_MODE (cond), XEXP (cond, 0),
 491                              XEXP (cond, 1));
 492     }
 493
 494   return 0;
 495 }
 496
 497 \f
 498 /* Return nonzero if conditions COND1 and COND2 can never be both true.  */
 499
 500 static int
 501 conditions_mutex_p (const_rtx cond1, const_rtx cond2)
 502 {
 503   if (COMPARISON_P (cond1)
 504       && COMPARISON_P (cond2)
 505       && GET_CODE (cond1) == reversed_comparison_code (cond2, NULL)
 506       && XEXP (cond1, 0) == XEXP (cond2, 0)
 507       && XEXP (cond1, 1) == XEXP (cond2, 1))
 508     return 1;
 509   return 0;
 510 }
 511
 512 /* Return true if insn1 and insn2 can never depend on one another because
 513    the conditions under which they are executed are mutually exclusive.  */
 514 bool
 515 sched_insns_conditions_mutex_p (const_rtx insn1, const_rtx insn2)
 516 {
 517   rtx cond1, cond2;
 518
 519   /* df doesn't handle conditional lifetimes entirely correctly;
 520      calls mess up the conditional lifetimes.  */
 521   if (!CALL_P (insn1) && !CALL_P (insn2))
 522     {
 523       cond1 = sched_get_condition (insn1);
 524       cond2 = sched_get_condition (insn2);
 525       if (cond1 && cond2
 526           && conditions_mutex_p (cond1, cond2)
 527           /* Make sure first instruction doesn't affect condition of second
 528              instruction if switched.  */
 529           && !modified_in_p (cond1, insn2)
 530           /* Make sure second instruction doesn't affect condition of first
 531              instruction if switched.  */
 532           && !modified_in_p (cond2, insn1))
 533         return true;
 534     }
 535   return false;
 536 }
 537 \f
 538
 539 /* Return true if INSN can potentially be speculated with type DS.  */
 540 bool
 541 sched_insn_is_legitimate_for_speculation_p (const_rtx insn, ds_t ds)
 542 {
 543   if (HAS_INTERNAL_DEP (insn))
 544     return false;
 545
 546   if (!NONJUMP_INSN_P (insn))
 547     return false;
 548
 549   if (SCHED_GROUP_P (insn))
 550     return false;
 551
 552   if (IS_SPECULATION_CHECK_P (insn))
 553     return false;
 554
 555   if (side_effects_p (PATTERN (insn)))
 556     return false;
 557
 558   if (ds & BE_IN_SPEC)
 559     /* The following instructions, which depend on a speculatively scheduled
 560        instruction, cannot be speculatively scheduled along.  */
 561     {
 562       if (may_trap_p (PATTERN (insn)))
 563         /* If instruction might trap, it cannot be speculatively scheduled.
 564            For control speculation it's obvious why and for data speculation
 565            it's because the insn might get wrong input if speculation
 566            wasn't successful.  */
 567         return false;
 568
 569       if ((ds & BE_IN_DATA)
 570           && sched_get_condition (insn) != NULL_RTX)
 571         /* If this is a predicated instruction, then it cannot be
 572            speculatively scheduled.  See PR35659.  */
 573         return false;
 574     }
 575
 576   return true;
 577 }
 578
 579 /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
 580    initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
 581    and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
 582    This function is used to switch sd_iterator to the next list.
 583    !!! For internal use only.  Might consider moving it to sched-int.h.  */
 584 void
 585 sd_next_list (const_rtx insn, sd_list_types_def *types_ptr,
 586               deps_list_t *list_ptr, bool *resolved_p_ptr)
 587 {
 588   sd_list_types_def types = *types_ptr;
 589
 590   if (types & SD_LIST_HARD_BACK)
 591     {
 592       *list_ptr = INSN_HARD_BACK_DEPS (insn);
 593       *resolved_p_ptr = false;
 594       *types_ptr = types & ~SD_LIST_HARD_BACK;
 595     }
 596   else if (types & SD_LIST_SPEC_BACK)
 597     {
 598       *list_ptr = INSN_SPEC_BACK_DEPS (insn);
 599       *resolved_p_ptr = false;
 600       *types_ptr = types & ~SD_LIST_SPEC_BACK;
 601     }
 602   else if (types & SD_LIST_FORW)
 603     {
 604       *list_ptr = INSN_FORW_DEPS (insn);
 605       *resolved_p_ptr = false;
 606       *types_ptr = types & ~SD_LIST_FORW;
 607     }
 608   else if (types & SD_LIST_RES_BACK)
 609     {
 610       *list_ptr = INSN_RESOLVED_BACK_DEPS (insn);
 611       *resolved_p_ptr = true;
 612       *types_ptr = types & ~SD_LIST_RES_BACK;
 613     }
 614   else if (types & SD_LIST_RES_FORW)
 615     {
 616       *list_ptr = INSN_RESOLVED_FORW_DEPS (insn);
 617       *resolved_p_ptr = true;
 618       *types_ptr = types & ~SD_LIST_RES_FORW;
 619     }
 620   else
 621     {
 622       *list_ptr = NULL;
 623       *resolved_p_ptr = false;
 624       *types_ptr = SD_LIST_NONE;
 625     }
 626 }
 627
 628 /* Return the summary size of INSN's lists defined by LIST_TYPES.  */
 629 int
 630 sd_lists_size (const_rtx insn, sd_list_types_def list_types)
 631 {
 632   int size = 0;
 633
 634   while (list_types != SD_LIST_NONE)
 635     {
 636       deps_list_t list;
 637       bool resolved_p;
 638
 639       sd_next_list (insn, &list_types, &list, &resolved_p);
 640       size += DEPS_LIST_N_LINKS (list);
 641     }
 642
 643   return size;
 644 }
 645
 646 /* Return true if INSN's lists defined by LIST_TYPES are all empty.  */
 647 bool
 648 sd_lists_empty_p (const_rtx insn, sd_list_types_def list_types)
 649 {
 650   return sd_lists_size (insn, list_types) == 0;
 651 }
 652
 653 /* Initialize data for INSN.  */
 654 void
 655 sd_init_insn (rtx insn)
 656 {
 657   INSN_HARD_BACK_DEPS (insn) = create_deps_list ();
 658   INSN_SPEC_BACK_DEPS (insn) = create_deps_list ();
 659   INSN_RESOLVED_BACK_DEPS (insn) = create_deps_list ();
 660   INSN_FORW_DEPS (insn) = create_deps_list ();
 661   INSN_RESOLVED_FORW_DEPS (insn) = create_deps_list ();
 662
 663   /* ??? It would be nice to allocate dependency caches here.  */
 664 }
 665
 666 /* Free data for INSN.  */
 667 void
 668 sd_finish_insn (rtx insn)
 669 {
 670   /* ??? It would be nice to deallocate dependency caches here.  */
 671
 672   free_deps_list (INSN_HARD_BACK_DEPS (insn));
 673   INSN_HARD_BACK_DEPS (insn) = NULL;
 674
 675   free_deps_list (INSN_SPEC_BACK_DEPS (insn));
 676   INSN_SPEC_BACK_DEPS (insn) = NULL;
 677
 678   free_deps_list (INSN_RESOLVED_BACK_DEPS (insn));
 679   INSN_RESOLVED_BACK_DEPS (insn) = NULL;
 680
 681   free_deps_list (INSN_FORW_DEPS (insn));
 682   INSN_FORW_DEPS (insn) = NULL;
 683
 684   free_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
 685   INSN_RESOLVED_FORW_DEPS (insn) = NULL;
 686 }
 687
 688 /* Find a dependency between producer PRO and consumer CON.
 689    Search through resolved dependency lists if RESOLVED_P is true.
 690    If no such dependency is found return NULL,
 691    otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
 692    with an iterator pointing to it.  */
 693 static dep_t
 694 sd_find_dep_between_no_cache (rtx pro, rtx con, bool resolved_p,
 695                               sd_iterator_def *sd_it_ptr)
 696 {
 697   sd_list_types_def pro_list_type;
 698   sd_list_types_def con_list_type;
 699   sd_iterator_def sd_it;
 700   dep_t dep;
 701   bool found_p = false;
 702
 703   if (resolved_p)
 704     {
 705       pro_list_type = SD_LIST_RES_FORW;
 706       con_list_type = SD_LIST_RES_BACK;
 707     }
 708   else
 709     {
 710       pro_list_type = SD_LIST_FORW;
 711       con_list_type = SD_LIST_BACK;
 712     }
 713
 714   /* Walk through either back list of INSN or forw list of ELEM
 715      depending on which one is shorter.  */
 716   if (sd_lists_size (con, con_list_type) < sd_lists_size (pro, pro_list_type))
 717     {
 718       /* Find the dep_link with producer PRO in consumer's back_deps.  */
 719       FOR_EACH_DEP (con, con_list_type, sd_it, dep)
 720         if (DEP_PRO (dep) == pro)
 721           {
 722             found_p = true;
 723             break;
 724           }
 725     }
 726   else
 727     {
 728       /* Find the dep_link with consumer CON in producer's forw_deps.  */
 729       FOR_EACH_DEP (pro, pro_list_type, sd_it, dep)
 730         if (DEP_CON (dep) == con)
 731           {
 732             found_p = true;
 733             break;
 734           }
 735     }
 736
 737   if (found_p)
 738     {
 739       if (sd_it_ptr != NULL)
 740         *sd_it_ptr = sd_it;
 741
 742       return dep;
 743     }
 744
 745   return NULL;
 746 }
 747
 748 /* Find a dependency between producer PRO and consumer CON.
 749    Use dependency [if available] to check if dependency is present at all.
 750    Search through resolved dependency lists if RESOLVED_P is true.
 751    If the dependency or NULL if none found.  */
 752 dep_t
 753 sd_find_dep_between (rtx pro, rtx con, bool resolved_p)
 754 {
 755   if (true_dependency_cache != NULL)
 756     /* Avoiding the list walk below can cut compile times dramatically
 757        for some code.  */
 758     {
 759       int elem_luid = INSN_LUID (pro);
 760       int insn_luid = INSN_LUID (con);
 761
 762       gcc_assert (output_dependency_cache != NULL
 763                   && anti_dependency_cache != NULL);
 764
 765       if (!bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid)
 766           && !bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid)
 767           && !bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
 768         return NULL;
 769     }
 770
 771   return sd_find_dep_between_no_cache (pro, con, resolved_p, NULL);
 772 }
 773
 774 /* Add or update  a dependence described by DEP.
 775    MEM1 and MEM2, if non-null, correspond to memory locations in case of
 776    data speculation.
 777
 778    The function returns a value indicating if an old entry has been changed
 779    or a new entry has been added to insn's backward deps.
 780
 781    This function merely checks if producer and consumer is the same insn
 782    and doesn't create a dep in this case.  Actual manipulation of
 783    dependence data structures is performed in add_or_update_dep_1.  */
 784 static enum DEPS_ADJUST_RESULT
 785 maybe_add_or_update_dep_1 (dep_t dep, bool resolved_p, rtx mem1, rtx mem2)
 786 {
 787   rtx elem = DEP_PRO (dep);
 788   rtx insn = DEP_CON (dep);
 789
 790   gcc_assert (INSN_P (insn) && INSN_P (elem));
 791
 792   /* Don't depend an insn on itself.  */
 793   if (insn == elem)
 794     {
 795       if (current_sched_info->flags & DO_SPECULATION)
 796         /* INSN has an internal dependence, which we can't overcome.  */
 797         HAS_INTERNAL_DEP (insn) = 1;
 798
 799       return DEP_NODEP;
 800     }
 801
 802   return add_or_update_dep_1 (dep, resolved_p, mem1, mem2);
 803 }
 804
 805 /* Ask dependency caches what needs to be done for dependence DEP.
 806    Return DEP_CREATED if new dependence should be created and there is no
 807    need to try to find one searching the dependencies lists.
 808    Return DEP_PRESENT if there already is a dependence described by DEP and
 809    hence nothing is to be done.
 810    Return DEP_CHANGED if there already is a dependence, but it should be
 811    updated to incorporate additional information from DEP.  */
 812 static enum DEPS_ADJUST_RESULT
 813 ask_dependency_caches (dep_t dep)
 814 {
 815   int elem_luid = INSN_LUID (DEP_PRO (dep));
 816   int insn_luid = INSN_LUID (DEP_CON (dep));
 817
 818   gcc_assert (true_dependency_cache != NULL
 819               && output_dependency_cache != NULL
 820               && anti_dependency_cache != NULL);
 821
 822   if (!(current_sched_info->flags & USE_DEPS_LIST))
 823     {
 824       enum reg_note present_dep_type;
 825
 826       if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
 827         present_dep_type = REG_DEP_TRUE;
 828       else if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
 829         present_dep_type = REG_DEP_OUTPUT;
 830       else if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
 831         present_dep_type = REG_DEP_ANTI;
 832       else
 833         /* There is no existing dep so it should be created.  */
 834         return DEP_CREATED;
 835
 836       if ((int) DEP_TYPE (dep) >= (int) present_dep_type)
 837         /* DEP does not add anything to the existing dependence.  */
 838         return DEP_PRESENT;
 839     }
 840   else
 841     {
 842       ds_t present_dep_types = 0;
 843
 844       if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
 845         present_dep_types |= DEP_TRUE;
 846       if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
 847         present_dep_types |= DEP_OUTPUT;
 848       if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
 849         present_dep_types |= DEP_ANTI;
 850
 851       if (present_dep_types == 0)
 852         /* There is no existing dep so it should be created.  */
 853         return DEP_CREATED;
 854
 855       if (!(current_sched_info->flags & DO_SPECULATION)
 856           || !bitmap_bit_p (&spec_dependency_cache[insn_luid], elem_luid))
 857         {
 858           if ((present_dep_types | (DEP_STATUS (dep) & DEP_TYPES))
 859               == present_dep_types)
 860             /* DEP does not add anything to the existing dependence.  */
 861             return DEP_PRESENT;
 862         }
 863       else
 864         {
 865           /* Only true dependencies can be data speculative and
 866              only anti dependencies can be control speculative.  */
 867           gcc_assert ((present_dep_types & (DEP_TRUE | DEP_ANTI))
 868                       == present_dep_types);
 869
 870           /* if (DEP is SPECULATIVE) then
 871              ..we should update DEP_STATUS
 872              else
 873              ..we should reset existing dep to non-speculative.  */
 874         }
 875     }
 876
 877   return DEP_CHANGED;
 878 }
 879
 880 /* Set dependency caches according to DEP.  */
 881 static void
 882 set_dependency_caches (dep_t dep)
 883 {
 884   int elem_luid = INSN_LUID (DEP_PRO (dep));
 885   int insn_luid = INSN_LUID (DEP_CON (dep));
 886
 887   if (!(current_sched_info->flags & USE_DEPS_LIST))
 888     {
 889       switch (DEP_TYPE (dep))
 890         {
 891         case REG_DEP_TRUE:
 892           bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
 893           break;
 894
 895         case REG_DEP_OUTPUT:
 896           bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
 897           break;
 898
 899         case REG_DEP_ANTI:
 900           bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
 901           break;
 902
 903         default:
 904           gcc_unreachable ();
 905         }
 906     }
 907   else
 908     {
 909       ds_t ds = DEP_STATUS (dep);
 910
 911       if (ds & DEP_TRUE)
 912         bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
 913       if (ds & DEP_OUTPUT)
 914         bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
 915       if (ds & DEP_ANTI)
 916         bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
 917
 918       if (ds & SPECULATIVE)
 919         {
 920           gcc_assert (current_sched_info->flags & DO_SPECULATION);
 921           bitmap_set_bit (&spec_dependency_cache[insn_luid], elem_luid);
 922         }
 923     }
 924 }
 925
 926 /* Type of dependence DEP have changed from OLD_TYPE.  Update dependency
 927    caches accordingly.  */
 928 static void
 929 update_dependency_caches (dep_t dep, enum reg_note old_type)
 930 {
 931   int elem_luid = INSN_LUID (DEP_PRO (dep));
 932   int insn_luid = INSN_LUID (DEP_CON (dep));
 933
 934   /* Clear corresponding cache entry because type of the link
 935      may have changed.  Keep them if we use_deps_list.  */
 936   if (!(current_sched_info->flags & USE_DEPS_LIST))
 937     {
 938       switch (old_type)
 939         {
 940         case REG_DEP_OUTPUT:
 941           bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
 942           break;
 943
 944         case REG_DEP_ANTI:
 945           bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
 946           break;
 947
 948         default:
 949           gcc_unreachable ();
 950         }
 951     }
 952
 953   set_dependency_caches (dep);
 954 }
 955
 956 /* Convert a dependence pointed to by SD_IT to be non-speculative.  */
 957 static void
 958 change_spec_dep_to_hard (sd_iterator_def sd_it)
 959 {
 960   dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
 961   dep_link_t link = DEP_NODE_BACK (node);
 962   dep_t dep = DEP_NODE_DEP (node);
 963   rtx elem = DEP_PRO (dep);
 964   rtx insn = DEP_CON (dep);
 965
 966   move_dep_link (link, INSN_SPEC_BACK_DEPS (insn), INSN_HARD_BACK_DEPS (insn));
 967
 968   DEP_STATUS (dep) &= ~SPECULATIVE;
 969
 970   if (true_dependency_cache != NULL)
 971     /* Clear the cache entry.  */
 972     bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
 973                       INSN_LUID (elem));
 974 }
 975
 976 /* Update DEP to incorporate information from NEW_DEP.
 977    SD_IT points to DEP in case it should be moved to another list.
 978    MEM1 and MEM2, if nonnull, correspond to memory locations in case if
 979    data-speculative dependence should be updated.  */
 980 static enum DEPS_ADJUST_RESULT
 981 update_dep (dep_t dep, dep_t new_dep,
 982             sd_iterator_def sd_it ATTRIBUTE_UNUSED,
 983             rtx mem1 ATTRIBUTE_UNUSED,
 984             rtx mem2 ATTRIBUTE_UNUSED)
 985 {
 986   enum DEPS_ADJUST_RESULT res = DEP_PRESENT;
 987   enum reg_note old_type = DEP_TYPE (dep);
 988
 989   /* If this is a more restrictive type of dependence than the
 990      existing one, then change the existing dependence to this
 991      type.  */
 992   if ((int) DEP_TYPE (new_dep) < (int) old_type)
 993     {
 994       DEP_TYPE (dep) = DEP_TYPE (new_dep);
 995       res = DEP_CHANGED;
 996     }
 997
 998   if (current_sched_info->flags & USE_DEPS_LIST)
 999     /* Update DEP_STATUS.  */
1000     {
1001       ds_t dep_status = DEP_STATUS (dep);
1002       ds_t ds = DEP_STATUS (new_dep);
1003       ds_t new_status = ds | dep_status;
1004
1005       if (new_status & SPECULATIVE)
1006         /* Either existing dep or a dep we're adding or both are
1007            speculative.  */
1008         {
1009           if (!(ds & SPECULATIVE)
1010               || !(dep_status & SPECULATIVE))
1011             /* The new dep can't be speculative.  */
1012             {
1013               new_status &= ~SPECULATIVE;
1014
1015               if (dep_status & SPECULATIVE)
1016                 /* The old dep was speculative, but now it
1017                    isn't.  */
1018                 change_spec_dep_to_hard (sd_it);
1019             }
1020           else
1021             {
1022               /* Both are speculative.  Merge probabilities.  */
1023               if (mem1 != NULL)
1024                 {
1025                   dw_t dw;
1026
1027                   dw = estimate_dep_weak (mem1, mem2);
1028                   ds = set_dep_weak (ds, BEGIN_DATA, dw);
1029                 }
1030
1031               new_status = ds_merge (dep_status, ds);
1032             }
1033         }
1034
1035       ds = new_status;
1036
1037       if (dep_status != ds)
1038         {
1039           DEP_STATUS (dep) = ds;
1040           res = DEP_CHANGED;
1041         }
1042     }
1043
1044   if (true_dependency_cache != NULL
1045       && res == DEP_CHANGED)
1046     update_dependency_caches (dep, old_type);
1047
1048   return res;
1049 }
1050
1051 /* Add or update  a dependence described by DEP.
1052    MEM1 and MEM2, if non-null, correspond to memory locations in case of
1053    data speculation.
1054
1055    The function returns a value indicating if an old entry has been changed
1056    or a new entry has been added to insn's backward deps or nothing has
1057    been updated at all.  */
1058 static enum DEPS_ADJUST_RESULT
1059 add_or_update_dep_1 (dep_t new_dep, bool resolved_p,
1060                      rtx mem1 ATTRIBUTE_UNUSED, rtx mem2 ATTRIBUTE_UNUSED)
1061 {
1062   bool maybe_present_p = true;
1063   bool present_p = false;
1064
1065   gcc_assert (INSN_P (DEP_PRO (new_dep)) && INSN_P (DEP_CON (new_dep))
1066               && DEP_PRO (new_dep) != DEP_CON (new_dep));
1067
1068 #ifdef ENABLE_CHECKING
1069   check_dep (new_dep, mem1 != NULL);
1070 #endif
1071
1072   if (true_dependency_cache != NULL)
1073     {
1074       switch (ask_dependency_caches (new_dep))
1075         {
1076         case DEP_PRESENT:
1077           return DEP_PRESENT;
1078
1079         case DEP_CHANGED:
1080           maybe_present_p = true;
1081           present_p = true;
1082           break;
1083
1084         case DEP_CREATED:
1085           maybe_present_p = false;
1086           present_p = false;
1087           break;
1088
1089         default:
1090           gcc_unreachable ();
1091           break;
1092         }
1093     }
1094
1095   /* Check that we don't already have this dependence.  */
1096   if (maybe_present_p)
1097     {
1098       dep_t present_dep;
1099       sd_iterator_def sd_it;
1100
1101       gcc_assert (true_dependency_cache == NULL || present_p);
1102
1103       present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
1104                                                   DEP_CON (new_dep),
1105                                                   resolved_p, &sd_it);
1106
1107       if (present_dep != NULL)
1108         /* We found an existing dependency between ELEM and INSN.  */
1109         return update_dep (present_dep, new_dep, sd_it, mem1, mem2);
1110       else
1111         /* We didn't find a dep, it shouldn't present in the cache.  */
1112         gcc_assert (!present_p);
1113     }
1114
1115   /* Might want to check one level of transitivity to save conses.
1116      This check should be done in maybe_add_or_update_dep_1.
1117      Since we made it to add_or_update_dep_1, we must create
1118      (or update) a link.  */
1119
1120   if (mem1 != NULL_RTX)
1121     {
1122       gcc_assert (current_sched_info->flags & DO_SPECULATION);
1123       DEP_STATUS (new_dep) = set_dep_weak (DEP_STATUS (new_dep), BEGIN_DATA,
1124                                            estimate_dep_weak (mem1, mem2));
1125     }
1126
1127   sd_add_dep (new_dep, resolved_p);
1128
1129   return DEP_CREATED;
1130 }
1131
1132 /* Initialize BACK_LIST_PTR with consumer's backward list and
1133    FORW_LIST_PTR with producer's forward list.  If RESOLVED_P is true
1134    initialize with lists that hold resolved deps.  */
1135 static void
1136 get_back_and_forw_lists (dep_t dep, bool resolved_p,
1137                          deps_list_t *back_list_ptr,
1138                          deps_list_t *forw_list_ptr)
1139 {
1140   rtx con = DEP_CON (dep);
1141
1142   if (!resolved_p)
1143     {
1144       if ((current_sched_info->flags & DO_SPECULATION)
1145           && (DEP_STATUS (dep) & SPECULATIVE))
1146         *back_list_ptr = INSN_SPEC_BACK_DEPS (con);
1147       else
1148         *back_list_ptr = INSN_HARD_BACK_DEPS (con);
1149
1150       *forw_list_ptr = INSN_FORW_DEPS (DEP_PRO (dep));
1151     }
1152   else
1153     {
1154       *back_list_ptr = INSN_RESOLVED_BACK_DEPS (con);
1155       *forw_list_ptr = INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep));
1156     }
1157 }
1158
1159 /* Add dependence described by DEP.
1160    If RESOLVED_P is true treat the dependence as a resolved one.  */
1161 void
1162 sd_add_dep (dep_t dep, bool resolved_p)
1163 {
1164   dep_node_t n = create_dep_node ();
1165   deps_list_t con_back_deps;
1166   deps_list_t pro_forw_deps;
1167   rtx elem = DEP_PRO (dep);
1168   rtx insn = DEP_CON (dep);
1169
1170   gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
1171
1172   if ((current_sched_info->flags & DO_SPECULATION)
1173       && !sched_insn_is_legitimate_for_speculation_p (insn, DEP_STATUS (dep)))
1174     DEP_STATUS (dep) &= ~SPECULATIVE;
1175
1176   copy_dep (DEP_NODE_DEP (n), dep);
1177
1178   get_back_and_forw_lists (dep, resolved_p, &con_back_deps, &pro_forw_deps);
1179
1180   add_to_deps_list (DEP_NODE_BACK (n), con_back_deps);
1181
1182 #ifdef ENABLE_CHECKING
1183   check_dep (dep, false);
1184 #endif
1185
1186   add_to_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1187
1188   /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1189      in the bitmap caches of dependency information.  */
1190   if (true_dependency_cache != NULL)
1191     set_dependency_caches (dep);
1192 }
1193
1194 /* Add or update backward dependence between INSN and ELEM
1195    with given type DEP_TYPE and dep_status DS.
1196    This function is a convenience wrapper.  */
1197 enum DEPS_ADJUST_RESULT
1198 sd_add_or_update_dep (dep_t dep, bool resolved_p)
1199 {
1200   return add_or_update_dep_1 (dep, resolved_p, NULL_RTX, NULL_RTX);
1201 }
1202
1203 /* Resolved dependence pointed to by SD_IT.
1204    SD_IT will advance to the next element.  */
1205 void
1206 sd_resolve_dep (sd_iterator_def sd_it)
1207 {
1208   dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1209   dep_t dep = DEP_NODE_DEP (node);
1210   rtx pro = DEP_PRO (dep);
1211   rtx con = DEP_CON (dep);
1212
1213   if ((current_sched_info->flags & DO_SPECULATION)
1214       && (DEP_STATUS (dep) & SPECULATIVE))
1215     move_dep_link (DEP_NODE_BACK (node), INSN_SPEC_BACK_DEPS (con),
1216                    INSN_RESOLVED_BACK_DEPS (con));
1217   else
1218     move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
1219                    INSN_RESOLVED_BACK_DEPS (con));
1220
1221   move_dep_link (DEP_NODE_FORW (node), INSN_FORW_DEPS (pro),
1222                  INSN_RESOLVED_FORW_DEPS (pro));
1223 }
1224
1225 /* Make TO depend on all the FROM's producers.
1226    If RESOLVED_P is true add dependencies to the resolved lists.  */
1227 void
1228 sd_copy_back_deps (rtx to, rtx from, bool resolved_p)
1229 {
1230   sd_list_types_def list_type;
1231   sd_iterator_def sd_it;
1232   dep_t dep;
1233
1234   list_type = resolved_p ? SD_LIST_RES_BACK : SD_LIST_BACK;
1235
1236   FOR_EACH_DEP (from, list_type, sd_it, dep)
1237     {
1238       dep_def _new_dep, *new_dep = &_new_dep;
1239
1240       copy_dep (new_dep, dep);
1241       DEP_CON (new_dep) = to;
1242       sd_add_dep (new_dep, resolved_p);
1243     }
1244 }
1245
1246 /* Remove a dependency referred to by SD_IT.
1247    SD_IT will point to the next dependence after removal.  */
1248 void
1249 sd_delete_dep (sd_iterator_def sd_it)
1250 {
1251   dep_node_t n = DEP_LINK_NODE (*sd_it.linkp);
1252   dep_t dep = DEP_NODE_DEP (n);
1253   rtx pro = DEP_PRO (dep);
1254   rtx con = DEP_CON (dep);
1255   deps_list_t con_back_deps;
1256   deps_list_t pro_forw_deps;
1257
1258   if (true_dependency_cache != NULL)
1259     {
1260       int elem_luid = INSN_LUID (pro);
1261       int insn_luid = INSN_LUID (con);
1262
1263       bitmap_clear_bit (&true_dependency_cache[insn_luid], elem_luid);
1264       bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1265       bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
1266
1267       if (current_sched_info->flags & DO_SPECULATION)
1268         bitmap_clear_bit (&spec_dependency_cache[insn_luid], elem_luid);
1269     }
1270
1271   get_back_and_forw_lists (dep, sd_it.resolved_p,
1272                            &con_back_deps, &pro_forw_deps);
1273
1274   remove_from_deps_list (DEP_NODE_BACK (n), con_back_deps);
1275   remove_from_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1276
1277   delete_dep_node (n);
1278 }
1279
1280 /* Dump size of the lists.  */
1281 #define DUMP_LISTS_SIZE (2)
1282
1283 /* Dump dependencies of the lists.  */
1284 #define DUMP_LISTS_DEPS (4)
1285
1286 /* Dump all information about the lists.  */
1287 #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1288
1289 /* Dump deps_lists of INSN specified by TYPES to DUMP.
1290    FLAGS is a bit mask specifying what information about the lists needs
1291    to be printed.
1292    If FLAGS has the very first bit set, then dump all information about
1293    the lists and propagate this bit into the callee dump functions.  */
1294 static void
1295 dump_lists (FILE *dump, rtx insn, sd_list_types_def types, int flags)
1296 {
1297   sd_iterator_def sd_it;
1298   dep_t dep;
1299   int all;
1300
1301   all = (flags & 1);
1302
1303   if (all)
1304     flags |= DUMP_LISTS_ALL;
1305
1306   fprintf (dump, "[");
1307
1308   if (flags & DUMP_LISTS_SIZE)
1309     fprintf (dump, "%d; ", sd_lists_size (insn, types));
1310
1311   if (flags & DUMP_LISTS_DEPS)
1312     {
1313       FOR_EACH_DEP (insn, types, sd_it, dep)
1314         {
1315           dump_dep (dump, dep, dump_dep_flags | all);
1316           fprintf (dump, " ");
1317         }
1318     }
1319 }
1320
1321 /* Dump all information about deps_lists of INSN specified by TYPES
1322    to STDERR.  */
1323 void
1324 sd_debug_lists (rtx insn, sd_list_types_def types)
1325 {
1326   dump_lists (stderr, insn, types, 1);
1327   fprintf (stderr, "\n");
1328 }
1329
1330 /* A convenience wrapper to operate on an entire list.  */
1331
1332 static void
1333 add_dependence_list (rtx insn, rtx list, int uncond, enum reg_note dep_type)
1334 {
1335   for (; list; list = XEXP (list, 1))
1336     {
1337       if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
1338         add_dependence (insn, XEXP (list, 0), dep_type);
1339     }
1340 }
1341
1342 /* Similar, but free *LISTP at the same time.  */
1343
1344 static void
1345 add_dependence_list_and_free (rtx insn, rtx *listp, int uncond,
1346                               enum reg_note dep_type)
1347 {
1348   rtx list, next;
1349   for (list = *listp, *listp = NULL; list ; list = next)
1350     {
1351       next = XEXP (list, 1);
1352       if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
1353         add_dependence (insn, XEXP (list, 0), dep_type);
1354       free_INSN_LIST_node (list);
1355     }
1356 }
1357
1358 /* Clear all dependencies for an insn.  */
1359 static void
1360 delete_all_dependences (rtx insn)
1361 {
1362   sd_iterator_def sd_it;
1363   dep_t dep;
1364
1365   /* The below cycle can be optimized to clear the caches and back_deps
1366      in one call but that would provoke duplication of code from
1367      delete_dep ().  */
1368
1369   for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
1370        sd_iterator_cond (&sd_it, &dep);)
1371     sd_delete_dep (sd_it);
1372 }
1373
1374 /* All insns in a scheduling group except the first should only have
1375    dependencies on the previous insn in the group.  So we find the
1376    first instruction in the scheduling group by walking the dependence
1377    chains backwards. Then we add the dependencies for the group to
1378    the previous nonnote insn.  */
1379
1380 static void
1381 fixup_sched_groups (rtx insn)
1382 {
1383   sd_iterator_def sd_it;
1384   dep_t dep;
1385   rtx prev_nonnote;
1386
1387   FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
1388     {
1389       rtx i = insn;
1390       rtx pro = DEP_PRO (dep);
1391
1392       do
1393         {
1394           i = prev_nonnote_insn (i);
1395
1396           if (pro == i)
1397             goto next_link;
1398         } while (SCHED_GROUP_P (i));
1399
1400       if (! sched_insns_conditions_mutex_p (i, pro))
1401         add_dependence (i, pro, DEP_TYPE (dep));
1402     next_link:;
1403     }
1404
1405   delete_all_dependences (insn);
1406
1407   prev_nonnote = prev_nonnote_insn (insn);
1408   if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
1409       && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
1410     add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
1411 }
1412 \f
1413 /* Process an insn's memory dependencies.  There are four kinds of
1414    dependencies:
1415
1416    (0) read dependence: read follows read
1417    (1) true dependence: read follows write
1418    (2) output dependence: write follows write
1419    (3) anti dependence: write follows read
1420
1421    We are careful to build only dependencies which actually exist, and
1422    use transitivity to avoid building too many links.  */
1423
1424 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1425    The MEM is a memory reference contained within INSN, which we are saving
1426    so that we can do memory aliasing on it.  */
1427
1428 static void
1429 add_insn_mem_dependence (struct deps *deps, bool read_p,
1430                          rtx insn, rtx mem)
1431 {
1432   rtx *insn_list;
1433   rtx *mem_list;
1434   rtx link;
1435
1436   if (read_p)
1437     {
1438       insn_list = &deps->pending_read_insns;
1439       mem_list = &deps->pending_read_mems;
1440       deps->pending_read_list_length++;
1441     }
1442   else
1443     {
1444       insn_list = &deps->pending_write_insns;
1445       mem_list = &deps->pending_write_mems;
1446       deps->pending_write_list_length++;
1447     }
1448
1449   link = alloc_INSN_LIST (insn, *insn_list);
1450   *insn_list = link;
1451
1452   if (current_sched_info->use_cselib)
1453     {
1454       mem = shallow_copy_rtx (mem);
1455       XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0));
1456     }
1457   link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
1458   *mem_list = link;
1459 }
1460
1461 /* Make a dependency between every memory reference on the pending lists
1462    and INSN, thus flushing the pending lists.  FOR_READ is true if emitting
1463    dependencies for a read operation, similarly with FOR_WRITE.  */
1464
1465 static void
1466 flush_pending_lists (struct deps *deps, rtx insn, int for_read,
1467                      int for_write)
1468 {
1469   if (for_write)
1470     {
1471       add_dependence_list_and_free (insn, &deps->pending_read_insns, 1,
1472                                     REG_DEP_ANTI);
1473       free_EXPR_LIST_list (&deps->pending_read_mems);
1474       deps->pending_read_list_length = 0;
1475     }
1476
1477   add_dependence_list_and_free (insn, &deps->pending_write_insns, 1,
1478                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
1479   free_EXPR_LIST_list (&deps->pending_write_mems);
1480   deps->pending_write_list_length = 0;
1481
1482   add_dependence_list_and_free (insn, &deps->last_pending_memory_flush, 1,
1483                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
1484   deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
1485   deps->pending_flush_length = 1;
1486 }
1487 \f
1488 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
1489    The type of the reference is specified by REF and can be SET,
1490    CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE.  */
1491
1492 static void
1493 sched_analyze_reg (struct deps *deps, int regno, enum machine_mode mode,
1494                    enum rtx_code ref, rtx insn)
1495 {
1496   /* A hard reg in a wide mode may really be multiple registers.
1497      If so, mark all of them just like the first.  */
1498   if (regno < FIRST_PSEUDO_REGISTER)
1499     {
1500       int i = hard_regno_nregs[regno][mode];
1501       if (ref == SET)
1502         {
1503           while (--i >= 0)
1504             SET_REGNO_REG_SET (reg_pending_sets, regno + i);
1505         }
1506       else if (ref == USE)
1507         {
1508           while (--i >= 0)
1509             SET_REGNO_REG_SET (reg_pending_uses, regno + i);
1510         }
1511       else
1512         {
1513           while (--i >= 0)
1514             SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
1515         }
1516     }
1517
1518   /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
1519      it does not reload.  Ignore these as they have served their
1520      purpose already.  */
1521   else if (regno >= deps->max_reg)
1522     {
1523       enum rtx_code code = GET_CODE (PATTERN (insn));
1524       gcc_assert (code == USE || code == CLOBBER);
1525     }
1526
1527   else
1528     {
1529       if (ref == SET)
1530         SET_REGNO_REG_SET (reg_pending_sets, regno);
1531       else if (ref == USE)
1532         SET_REGNO_REG_SET (reg_pending_uses, regno);
1533       else
1534         SET_REGNO_REG_SET (reg_pending_clobbers, regno);
1535
1536       /* Pseudos that are REG_EQUIV to something may be replaced
1537          by that during reloading.  We need only add dependencies for
1538         the address in the REG_EQUIV note.  */
1539       if (!reload_completed && get_reg_known_equiv_p (regno))
1540         {
1541           rtx t = get_reg_known_value (regno);
1542           if (MEM_P (t))
1543             sched_analyze_2 (deps, XEXP (t, 0), insn);
1544         }
1545
1546       /* Don't let it cross a call after scheduling if it doesn't
1547          already cross one.  */
1548       if (REG_N_CALLS_CROSSED (regno) == 0)
1549         {
1550           if (ref == USE)
1551             deps->sched_before_next_call
1552               = alloc_INSN_LIST (insn, deps->sched_before_next_call);
1553           else
1554             add_dependence_list (insn, deps->last_function_call, 1,
1555                                  REG_DEP_ANTI);
1556         }
1557     }
1558 }
1559
1560 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
1561    rtx, X, creating all dependencies generated by the write to the
1562    destination of X, and reads of everything mentioned.  */
1563
1564 static void
1565 sched_analyze_1 (struct deps *deps, rtx x, rtx insn)
1566 {
1567   rtx dest = XEXP (x, 0);
1568   enum rtx_code code = GET_CODE (x);
1569
1570   if (dest == 0)
1571     return;
1572
1573   if (GET_CODE (dest) == PARALLEL)
1574     {
1575       int i;
1576
1577       for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
1578         if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
1579           sched_analyze_1 (deps,
1580                            gen_rtx_CLOBBER (VOIDmode,
1581                                             XEXP (XVECEXP (dest, 0, i), 0)),
1582                            insn);
1583
1584       if (GET_CODE (x) == SET)
1585         sched_analyze_2 (deps, SET_SRC (x), insn);
1586       return;
1587     }
1588
1589   while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
1590          || GET_CODE (dest) == ZERO_EXTRACT)
1591     {
1592       if (GET_CODE (dest) == STRICT_LOW_PART
1593          || GET_CODE (dest) == ZERO_EXTRACT
1594          || df_read_modify_subreg_p (dest))
1595         {
1596           /* These both read and modify the result.  We must handle
1597              them as writes to get proper dependencies for following
1598              instructions.  We must handle them as reads to get proper
1599              dependencies from this to previous instructions.
1600              Thus we need to call sched_analyze_2.  */
1601
1602           sched_analyze_2 (deps, XEXP (dest, 0), insn);
1603         }
1604       if (GET_CODE (dest) == ZERO_EXTRACT)
1605         {
1606           /* The second and third arguments are values read by this insn.  */
1607           sched_analyze_2 (deps, XEXP (dest, 1), insn);
1608           sched_analyze_2 (deps, XEXP (dest, 2), insn);
1609         }
1610       dest = XEXP (dest, 0);
1611     }
1612
1613   if (REG_P (dest))
1614     {
1615       int regno = REGNO (dest);
1616       enum machine_mode mode = GET_MODE (dest);
1617
1618       sched_analyze_reg (deps, regno, mode, code, insn);
1619
1620 #ifdef STACK_REGS
1621       /* Treat all writes to a stack register as modifying the TOS.  */
1622       if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
1623         {
1624           /* Avoid analyzing the same register twice.  */
1625           if (regno != FIRST_STACK_REG)
1626             sched_analyze_reg (deps, FIRST_STACK_REG, mode, code, insn);
1627           sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
1628         }
1629 #endif
1630     }
1631   else if (MEM_P (dest))
1632     {
1633       /* Writing memory.  */
1634       rtx t = dest;
1635
1636       if (current_sched_info->use_cselib)
1637         {
1638           t = shallow_copy_rtx (dest);
1639           cselib_lookup (XEXP (t, 0), Pmode, 1);
1640           XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
1641         }
1642       t = canon_rtx (t);
1643
1644       if ((deps->pending_read_list_length + deps->pending_write_list_length)
1645           > MAX_PENDING_LIST_LENGTH)
1646         {
1647           /* Flush all pending reads and writes to prevent the pending lists
1648              from getting any larger.  Insn scheduling runs too slowly when
1649              these lists get long.  When compiling GCC with itself,
1650              this flush occurs 8 times for sparc, and 10 times for m88k using
1651              the default value of 32.  */
1652           flush_pending_lists (deps, insn, false, true);
1653         }
1654       else
1655         {
1656           rtx pending, pending_mem;
1657
1658           pending = deps->pending_read_insns;
1659           pending_mem = deps->pending_read_mems;
1660           while (pending)
1661             {
1662               if (anti_dependence (XEXP (pending_mem, 0), t)
1663                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1664                 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
1665
1666               pending = XEXP (pending, 1);
1667               pending_mem = XEXP (pending_mem, 1);
1668             }
1669
1670           pending = deps->pending_write_insns;
1671           pending_mem = deps->pending_write_mems;
1672           while (pending)
1673             {
1674               if (output_dependence (XEXP (pending_mem, 0), t)
1675                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1676                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
1677
1678               pending = XEXP (pending, 1);
1679               pending_mem = XEXP (pending_mem, 1);
1680             }
1681
1682           add_dependence_list (insn, deps->last_pending_memory_flush, 1,
1683                                REG_DEP_ANTI);
1684
1685           add_insn_mem_dependence (deps, false, insn, dest);
1686         }
1687       sched_analyze_2 (deps, XEXP (dest, 0), insn);
1688     }
1689
1690   /* Analyze reads.  */
1691   if (GET_CODE (x) == SET)
1692     sched_analyze_2 (deps, SET_SRC (x), insn);
1693 }
1694
1695 /* Analyze the uses of memory and registers in rtx X in INSN.  */
1696
1697 static void
1698 sched_analyze_2 (struct deps *deps, rtx x, rtx insn)
1699 {
1700   int i;
1701   int j;
1702   enum rtx_code code;
1703   const char *fmt;
1704
1705   if (x == 0)
1706     return;
1707
1708   code = GET_CODE (x);
1709
1710   switch (code)
1711     {
1712     case CONST_INT:
1713     case CONST_DOUBLE:
1714     case CONST_FIXED:
1715     case CONST_VECTOR:
1716     case SYMBOL_REF:
1717     case CONST:
1718     case LABEL_REF:
1719       /* Ignore constants.  Note that we must handle CONST_DOUBLE here
1720          because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
1721          this does not mean that this insn is using cc0.  */
1722       return;
1723
1724 #ifdef HAVE_cc0
1725     case CC0:
1726       /* User of CC0 depends on immediately preceding insn.  */
1727       SCHED_GROUP_P (insn) = 1;
1728        /* Don't move CC0 setter to another block (it can set up the
1729         same flag for previous CC0 users which is safe).  */
1730       CANT_MOVE (prev_nonnote_insn (insn)) = 1;
1731       return;
1732 #endif
1733
1734     case REG:
1735       {
1736         int regno = REGNO (x);
1737         enum machine_mode mode = GET_MODE (x);
1738
1739         sched_analyze_reg (deps, regno, mode, USE, insn);
1740
1741 #ifdef STACK_REGS
1742       /* Treat all reads of a stack register as modifying the TOS.  */
1743       if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
1744         {
1745           /* Avoid analyzing the same register twice.  */
1746           if (regno != FIRST_STACK_REG)
1747             sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
1748           sched_analyze_reg (deps, FIRST_STACK_REG, mode, SET, insn);
1749         }
1750 #endif
1751         return;
1752       }
1753
1754     case MEM:
1755       {
1756         /* Reading memory.  */
1757         rtx u;
1758         rtx pending, pending_mem;
1759         rtx t = x;
1760
1761         if (current_sched_info->use_cselib)
1762           {
1763             t = shallow_copy_rtx (t);
1764             cselib_lookup (XEXP (t, 0), Pmode, 1);
1765             XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
1766           }
1767         t = canon_rtx (t);
1768         pending = deps->pending_read_insns;
1769         pending_mem = deps->pending_read_mems;
1770         while (pending)
1771           {
1772             if (read_dependence (XEXP (pending_mem, 0), t)
1773                 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1774               add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
1775
1776             pending = XEXP (pending, 1);
1777             pending_mem = XEXP (pending_mem, 1);
1778           }
1779
1780         pending = deps->pending_write_insns;
1781         pending_mem = deps->pending_write_mems;
1782         while (pending)
1783           {
1784             if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
1785                                  t, rtx_varies_p)
1786                 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1787               {
1788                 if ((current_sched_info->flags & DO_SPECULATION)
1789                     && (spec_info->mask & BEGIN_DATA))
1790                   /* Create a data-speculative dependence between producer
1791                      and consumer.  */
1792                   {
1793                     dep_def _dep, *dep = &_dep;
1794
1795                     init_dep_1 (dep, XEXP (pending, 0), insn, REG_DEP_TRUE,
1796                                 BEGIN_DATA | DEP_TRUE);
1797
1798                     maybe_add_or_update_dep_1 (dep, false,
1799                                                XEXP (pending_mem, 0), t);
1800                   }
1801                 else
1802                   add_dependence (insn, XEXP (pending, 0), REG_DEP_TRUE);
1803               }
1804
1805             pending = XEXP (pending, 1);
1806             pending_mem = XEXP (pending_mem, 1);
1807           }
1808
1809         for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
1810           if (! JUMP_P (XEXP (u, 0)) || deps_may_trap_p (x))
1811             add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1812
1813         /* Always add these dependencies to pending_reads, since
1814            this insn may be followed by a write.  */
1815         add_insn_mem_dependence (deps, true, insn, x);
1816
1817         /* Take advantage of tail recursion here.  */
1818         sched_analyze_2 (deps, XEXP (x, 0), insn);
1819         return;
1820       }
1821
1822     /* Force pending stores to memory in case a trap handler needs them.  */
1823     case TRAP_IF:
1824       flush_pending_lists (deps, insn, true, false);
1825       break;
1826
1827     case ASM_OPERANDS:
1828     case ASM_INPUT:
1829     case UNSPEC_VOLATILE:
1830       {
1831         /* Traditional and volatile asm instructions must be considered to use
1832            and clobber all hard registers, all pseudo-registers and all of
1833            memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
1834
1835            Consider for instance a volatile asm that changes the fpu rounding
1836            mode.  An insn should not be moved across this even if it only uses
1837            pseudo-regs because it might give an incorrectly rounded result.  */
1838         if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
1839           reg_pending_barrier = TRUE_BARRIER;
1840
1841         /* For all ASM_OPERANDS, we must traverse the vector of input operands.
1842            We can not just fall through here since then we would be confused
1843            by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
1844            traditional asms unlike their normal usage.  */
1845
1846         if (code == ASM_OPERANDS)
1847           {
1848             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
1849               sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
1850             return;
1851           }
1852         break;
1853       }
1854
1855     case PRE_DEC:
1856     case POST_DEC:
1857     case PRE_INC:
1858     case POST_INC:
1859       /* These both read and modify the result.  We must handle them as writes
1860          to get proper dependencies for following instructions.  We must handle
1861          them as reads to get proper dependencies from this to previous
1862          instructions.  Thus we need to pass them to both sched_analyze_1
1863          and sched_analyze_2.  We must call sched_analyze_2 first in order
1864          to get the proper antecedent for the read.  */
1865       sched_analyze_2 (deps, XEXP (x, 0), insn);
1866       sched_analyze_1 (deps, x, insn);
1867       return;
1868
1869     case POST_MODIFY:
1870     case PRE_MODIFY:
1871       /* op0 = op0 + op1 */
1872       sched_analyze_2 (deps, XEXP (x, 0), insn);
1873       sched_analyze_2 (deps, XEXP (x, 1), insn);
1874       sched_analyze_1 (deps, x, insn);
1875       return;
1876
1877     default:
1878       break;
1879     }
1880
1881   /* Other cases: walk the insn.  */
1882   fmt = GET_RTX_FORMAT (code);
1883   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1884     {
1885       if (fmt[i] == 'e')
1886         sched_analyze_2 (deps, XEXP (x, i), insn);
1887       else if (fmt[i] == 'E')
1888         for (j = 0; j < XVECLEN (x, i); j++)
1889           sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
1890     }
1891 }
1892
1893 /* Analyze an INSN with pattern X to find all dependencies.  */
1894
1895 static void
1896 sched_analyze_insn (struct deps *deps, rtx x, rtx insn)
1897 {
1898   RTX_CODE code = GET_CODE (x);
1899   rtx link;
1900   unsigned i;
1901   reg_set_iterator rsi;
1902
1903   if (code == COND_EXEC)
1904     {
1905       sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
1906
1907       /* ??? Should be recording conditions so we reduce the number of
1908          false dependencies.  */
1909       x = COND_EXEC_CODE (x);
1910       code = GET_CODE (x);
1911     }
1912   if (code == SET || code == CLOBBER)
1913     {
1914       sched_analyze_1 (deps, x, insn);
1915
1916       /* Bare clobber insns are used for letting life analysis, reg-stack
1917          and others know that a value is dead.  Depend on the last call
1918          instruction so that reg-stack won't get confused.  */
1919       if (code == CLOBBER)
1920         add_dependence_list (insn, deps->last_function_call, 1, REG_DEP_OUTPUT);
1921     }
1922   else if (code == PARALLEL)
1923     {
1924       for (i = XVECLEN (x, 0); i--;)
1925         {
1926           rtx sub = XVECEXP (x, 0, i);
1927           code = GET_CODE (sub);
1928
1929           if (code == COND_EXEC)
1930             {
1931               sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
1932               sub = COND_EXEC_CODE (sub);
1933               code = GET_CODE (sub);
1934             }
1935           if (code == SET || code == CLOBBER)
1936             sched_analyze_1 (deps, sub, insn);
1937           else
1938             sched_analyze_2 (deps, sub, insn);
1939         }
1940     }
1941   else
1942     sched_analyze_2 (deps, x, insn);
1943
1944   /* Mark registers CLOBBERED or used by called function.  */
1945   if (CALL_P (insn))
1946     {
1947       for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
1948         {
1949           if (GET_CODE (XEXP (link, 0)) == CLOBBER)
1950             sched_analyze_1 (deps, XEXP (link, 0), insn);
1951           else
1952             sched_analyze_2 (deps, XEXP (link, 0), insn);
1953         }
1954       if (find_reg_note (insn, REG_SETJMP, NULL))
1955         reg_pending_barrier = MOVE_BARRIER;
1956     }
1957
1958   if (JUMP_P (insn))
1959     {
1960       rtx next;
1961       next = next_nonnote_insn (insn);
1962       if (next && BARRIER_P (next))
1963         reg_pending_barrier = MOVE_BARRIER;
1964       else
1965         {
1966           rtx pending, pending_mem;
1967           regset_head tmp_uses, tmp_sets;
1968           INIT_REG_SET (&tmp_uses);
1969           INIT_REG_SET (&tmp_sets);
1970
1971           (*current_sched_info->compute_jump_reg_dependencies)
1972             (insn, &deps->reg_conditional_sets, &tmp_uses, &tmp_sets);
1973           /* Make latency of jump equal to 0 by using anti-dependence.  */
1974           EXECUTE_IF_SET_IN_REG_SET (&tmp_uses, 0, i, rsi)
1975             {
1976               struct deps_reg *reg_last = &deps->reg_last[i];
1977               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
1978               add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI);
1979               reg_last->uses_length++;
1980               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1981             }
1982           IOR_REG_SET (reg_pending_sets, &tmp_sets);
1983
1984           CLEAR_REG_SET (&tmp_uses);
1985           CLEAR_REG_SET (&tmp_sets);
1986
1987           /* All memory writes and volatile reads must happen before the
1988              jump.  Non-volatile reads must happen before the jump iff
1989              the result is needed by the above register used mask.  */
1990
1991           pending = deps->pending_write_insns;
1992           pending_mem = deps->pending_write_mems;
1993           while (pending)
1994             {
1995               if (! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1996                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
1997               pending = XEXP (pending, 1);
1998               pending_mem = XEXP (pending_mem, 1);
1999             }
2000
2001           pending = deps->pending_read_insns;
2002           pending_mem = deps->pending_read_mems;
2003           while (pending)
2004             {
2005               if (MEM_VOLATILE_P (XEXP (pending_mem, 0))
2006                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2007                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
2008               pending = XEXP (pending, 1);
2009               pending_mem = XEXP (pending_mem, 1);
2010             }
2011
2012           add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2013                                REG_DEP_ANTI);
2014         }
2015     }
2016
2017   /* If this instruction can throw an exception, then moving it changes
2018      where block boundaries fall.  This is mighty confusing elsewhere.
2019      Therefore, prevent such an instruction from being moved.  Same for
2020      non-jump instructions that define block boundaries.
2021      ??? Unclear whether this is still necessary in EBB mode.  If not,
2022      add_branch_dependences should be adjusted for RGN mode instead.  */
2023   if (((CALL_P (insn) || JUMP_P (insn)) && can_throw_internal (insn))
2024       || (NONJUMP_INSN_P (insn) && control_flow_insn_p (insn)))
2025     reg_pending_barrier = MOVE_BARRIER;
2026
2027   /* Add register dependencies for insn.
2028      If the current insn is conditional, we can't free any of the lists.  */
2029   if (sched_get_condition (insn))
2030     {
2031       EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
2032         {
2033           struct deps_reg *reg_last = &deps->reg_last[i];
2034           add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
2035           add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
2036           reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
2037           reg_last->uses_length++;
2038         }
2039       EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
2040         {
2041           struct deps_reg *reg_last = &deps->reg_last[i];
2042           add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
2043           add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
2044           reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
2045           reg_last->clobbers_length++;
2046         }
2047       EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
2048         {
2049           struct deps_reg *reg_last = &deps->reg_last[i];
2050           add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
2051           add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT);
2052           add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
2053           reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
2054           SET_REGNO_REG_SET (&deps->reg_conditional_sets, i);
2055         }
2056     }
2057   else
2058     {
2059       EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
2060         {
2061           struct deps_reg *reg_last = &deps->reg_last[i];
2062           add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
2063           add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
2064           reg_last->uses_length++;
2065           reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
2066         }
2067       EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
2068         {
2069           struct deps_reg *reg_last = &deps->reg_last[i];
2070           if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
2071               || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
2072             {
2073               add_dependence_list_and_free (insn, &reg_last->sets, 0,
2074                                             REG_DEP_OUTPUT);
2075               add_dependence_list_and_free (insn, &reg_last->uses, 0,
2076                                             REG_DEP_ANTI);
2077               add_dependence_list_and_free (insn, &reg_last->clobbers, 0,
2078                                             REG_DEP_OUTPUT);
2079               reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
2080               reg_last->clobbers_length = 0;
2081               reg_last->uses_length = 0;
2082             }
2083           else
2084             {
2085               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
2086               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
2087             }
2088           reg_last->clobbers_length++;
2089           reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
2090         }
2091       EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
2092         {
2093           struct deps_reg *reg_last = &deps->reg_last[i];
2094           add_dependence_list_and_free (insn, &reg_last->sets, 0,
2095                                         REG_DEP_OUTPUT);
2096           add_dependence_list_and_free (insn, &reg_last->clobbers, 0,
2097                                         REG_DEP_OUTPUT);
2098           add_dependence_list_and_free (insn, &reg_last->uses, 0,
2099                                         REG_DEP_ANTI);
2100           reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
2101           reg_last->uses_length = 0;
2102           reg_last->clobbers_length = 0;
2103           CLEAR_REGNO_REG_SET (&deps->reg_conditional_sets, i);
2104         }
2105     }
2106
2107   IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
2108   IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
2109   IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
2110
2111   CLEAR_REG_SET (reg_pending_uses);
2112   CLEAR_REG_SET (reg_pending_clobbers);
2113   CLEAR_REG_SET (reg_pending_sets);
2114
2115   /* Add dependencies if a scheduling barrier was found.  */
2116   if (reg_pending_barrier)
2117     {
2118       /* In the case of barrier the most added dependencies are not
2119          real, so we use anti-dependence here.  */
2120       if (sched_get_condition (insn))
2121         {
2122           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
2123             {
2124               struct deps_reg *reg_last = &deps->reg_last[i];
2125               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
2126               add_dependence_list
2127                 (insn, reg_last->sets, 0,
2128                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
2129               add_dependence_list
2130                 (insn, reg_last->clobbers, 0,
2131                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
2132             }
2133         }
2134       else
2135         {
2136           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
2137             {
2138               struct deps_reg *reg_last = &deps->reg_last[i];
2139               add_dependence_list_and_free (insn, &reg_last->uses, 0,
2140                                             REG_DEP_ANTI);
2141               add_dependence_list_and_free
2142                 (insn, &reg_last->sets, 0,
2143                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
2144               add_dependence_list_and_free
2145                 (insn, &reg_last->clobbers, 0,
2146                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
2147               reg_last->uses_length = 0;
2148               reg_last->clobbers_length = 0;
2149             }
2150         }
2151
2152       for (i = 0; i < (unsigned)deps->max_reg; i++)
2153         {
2154           struct deps_reg *reg_last = &deps->reg_last[i];
2155           reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
2156           SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
2157         }
2158
2159       flush_pending_lists (deps, insn, true, true);
2160       CLEAR_REG_SET (&deps->reg_conditional_sets);
2161       reg_pending_barrier = NOT_A_BARRIER;
2162     }
2163
2164   /* If a post-call group is still open, see if it should remain so.
2165      This insn must be a simple move of a hard reg to a pseudo or
2166      vice-versa.
2167
2168      We must avoid moving these insns for correctness on
2169      SMALL_REGISTER_CLASS machines, and for special registers like
2170      PIC_OFFSET_TABLE_REGNUM.  For simplicity, extend this to all
2171      hard regs for all targets.  */
2172
2173   if (deps->in_post_call_group_p)
2174     {
2175       rtx tmp, set = single_set (insn);
2176       int src_regno, dest_regno;
2177
2178       if (set == NULL)
2179         goto end_call_group;
2180
2181       tmp = SET_DEST (set);
2182       if (GET_CODE (tmp) == SUBREG)
2183         tmp = SUBREG_REG (tmp);
2184       if (REG_P (tmp))
2185         dest_regno = REGNO (tmp);
2186       else
2187         goto end_call_group;
2188
2189       tmp = SET_SRC (set);
2190       if (GET_CODE (tmp) == SUBREG)
2191         tmp = SUBREG_REG (tmp);
2192       if ((GET_CODE (tmp) == PLUS
2193            || GET_CODE (tmp) == MINUS)
2194           && REG_P (XEXP (tmp, 0))
2195           && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
2196           && dest_regno == STACK_POINTER_REGNUM)
2197         src_regno = STACK_POINTER_REGNUM;
2198       else if (REG_P (tmp))
2199         src_regno = REGNO (tmp);
2200       else
2201         goto end_call_group;
2202
2203       if (src_regno < FIRST_PSEUDO_REGISTER
2204           || dest_regno < FIRST_PSEUDO_REGISTER)
2205         {
2206           if (deps->in_post_call_group_p == post_call_initial)
2207             deps->in_post_call_group_p = post_call;
2208
2209           SCHED_GROUP_P (insn) = 1;
2210           CANT_MOVE (insn) = 1;
2211         }
2212       else
2213         {
2214         end_call_group:
2215           deps->in_post_call_group_p = not_post_call;
2216         }
2217     }
2218
2219   /* Fixup the dependencies in the sched group.  */
2220   if (SCHED_GROUP_P (insn))
2221     fixup_sched_groups (insn);
2222
2223   if ((current_sched_info->flags & DO_SPECULATION)
2224       && !sched_insn_is_legitimate_for_speculation_p (insn, 0))
2225     /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
2226        be speculated.  */
2227     {
2228       sd_iterator_def sd_it;
2229       dep_t dep;
2230
2231       for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
2232            sd_iterator_cond (&sd_it, &dep);)
2233         change_spec_dep_to_hard (sd_it);
2234     }
2235 }
2236
2237 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
2238    dependencies for each insn.  */
2239
2240 void
2241 sched_analyze (struct deps *deps, rtx head, rtx tail)
2242 {
2243   rtx insn;
2244
2245   if (current_sched_info->use_cselib)
2246     cselib_init (true);
2247
2248   /* Before reload, if the previous block ended in a call, show that
2249      we are inside a post-call group, so as to keep the lifetimes of
2250      hard registers correct.  */
2251   if (! reload_completed && !LABEL_P (head))
2252     {
2253       insn = prev_nonnote_insn (head);
2254       if (insn && CALL_P (insn))
2255         deps->in_post_call_group_p = post_call_initial;
2256     }
2257   for (insn = head;; insn = NEXT_INSN (insn))
2258     {
2259       if (INSN_P (insn))
2260         {
2261           /* And initialize deps_lists.  */
2262           sd_init_insn (insn);
2263         }
2264
2265       if (NONJUMP_INSN_P (insn) || JUMP_P (insn))
2266         {
2267           /* Make each JUMP_INSN a scheduling barrier for memory
2268              references.  */
2269           if (JUMP_P (insn))
2270             {
2271               /* Keep the list a reasonable size.  */
2272               if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
2273                 flush_pending_lists (deps, insn, true, true);
2274               else
2275                 deps->last_pending_memory_flush
2276                   = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
2277             }
2278           sched_analyze_insn (deps, PATTERN (insn), insn);
2279         }
2280       else if (CALL_P (insn))
2281         {
2282           int i;
2283
2284           CANT_MOVE (insn) = 1;
2285
2286           if (find_reg_note (insn, REG_SETJMP, NULL))
2287             {
2288               /* This is setjmp.  Assume that all registers, not just
2289                  hard registers, may be clobbered by this call.  */
2290               reg_pending_barrier = MOVE_BARRIER;
2291             }
2292           else
2293             {
2294               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2295                 /* A call may read and modify global register variables.  */
2296                 if (global_regs[i])
2297                   {
2298                     SET_REGNO_REG_SET (reg_pending_sets, i);
2299                     SET_REGNO_REG_SET (reg_pending_uses, i);
2300                   }
2301                 /* Other call-clobbered hard regs may be clobbered.
2302                    Since we only have a choice between 'might be clobbered'
2303                    and 'definitely not clobbered', we must include all
2304                    partly call-clobbered registers here.  */
2305                 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
2306                          || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
2307                   SET_REGNO_REG_SET (reg_pending_clobbers, i);
2308                 /* We don't know what set of fixed registers might be used
2309                    by the function, but it is certain that the stack pointer
2310                    is among them, but be conservative.  */
2311                 else if (fixed_regs[i])
2312                   SET_REGNO_REG_SET (reg_pending_uses, i);
2313                 /* The frame pointer is normally not used by the function
2314                    itself, but by the debugger.  */
2315                 /* ??? MIPS o32 is an exception.  It uses the frame pointer
2316                    in the macro expansion of jal but does not represent this
2317                    fact in the call_insn rtl.  */
2318                 else if (i == FRAME_POINTER_REGNUM
2319                          || (i == HARD_FRAME_POINTER_REGNUM
2320                              && (! reload_completed || frame_pointer_needed)))
2321                   SET_REGNO_REG_SET (reg_pending_uses, i);
2322             }
2323
2324           /* For each insn which shouldn't cross a call, add a dependence
2325              between that insn and this call insn.  */
2326           add_dependence_list_and_free (insn, &deps->sched_before_next_call, 1,
2327                                         REG_DEP_ANTI);
2328
2329           sched_analyze_insn (deps, PATTERN (insn), insn);
2330
2331           /* In the absence of interprocedural alias analysis, we must flush
2332              all pending reads and writes, and start new dependencies starting
2333              from here.  But only flush writes for constant calls (which may
2334              be passed a pointer to something we haven't written yet).  */
2335           flush_pending_lists (deps, insn, true,
2336                                ! RTL_CONST_OR_PURE_CALL_P (insn));
2337
2338           /* Remember the last function call for limiting lifetimes.  */
2339           free_INSN_LIST_list (&deps->last_function_call);
2340           deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
2341
2342           /* Before reload, begin a post-call group, so as to keep the
2343              lifetimes of hard registers correct.  */
2344           if (! reload_completed)
2345             deps->in_post_call_group_p = post_call;
2346         }
2347
2348       /* EH_REGION insn notes can not appear until well after we complete
2349          scheduling.  */
2350       if (NOTE_P (insn))
2351         gcc_assert (NOTE_KIND (insn) != NOTE_INSN_EH_REGION_BEG
2352                     && NOTE_KIND (insn) != NOTE_INSN_EH_REGION_END);
2353
2354       if (current_sched_info->use_cselib)
2355         cselib_process_insn (insn);
2356
2357       if (insn == tail)
2358         {
2359           if (current_sched_info->use_cselib)
2360             cselib_finish ();
2361           return;
2362         }
2363     }
2364   gcc_unreachable ();
2365 }
2366
2367 /* Helper for sched_free_deps ().
2368    Delete INSN's (RESOLVED_P) backward dependencies.  */
2369 static void
2370 delete_dep_nodes_in_back_deps (rtx insn, bool resolved_p)
2371 {
2372   sd_iterator_def sd_it;
2373   dep_t dep;
2374   sd_list_types_def types;
2375
2376   if (resolved_p)
2377     types = SD_LIST_RES_BACK;
2378   else
2379     types = SD_LIST_BACK;
2380
2381   for (sd_it = sd_iterator_start (insn, types);
2382        sd_iterator_cond (&sd_it, &dep);)
2383     {
2384       dep_link_t link = *sd_it.linkp;
2385       dep_node_t node = DEP_LINK_NODE (link);
2386       deps_list_t back_list;
2387       deps_list_t forw_list;
2388
2389       get_back_and_forw_lists (dep, resolved_p, &back_list, &forw_list);
2390       remove_from_deps_list (link, back_list);
2391       delete_dep_node (node);
2392     }
2393 }
2394
2395 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
2396    deps_lists.  */
2397 void
2398 sched_free_deps (rtx head, rtx tail, bool resolved_p)
2399 {
2400   rtx insn;
2401   rtx next_tail = NEXT_INSN (tail);
2402
2403   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
2404     if (INSN_P (insn) && INSN_LUID (insn) > 0)
2405       {
2406         /* Clear resolved back deps together with its dep_nodes.  */
2407         delete_dep_nodes_in_back_deps (insn, resolved_p);
2408
2409         /* Clear forward deps and leave the dep_nodes to the
2410            corresponding back_deps list.  */
2411         if (resolved_p)
2412           clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
2413         else
2414           clear_deps_list (INSN_FORW_DEPS (insn));
2415
2416         sd_finish_insn (insn);
2417       }
2418 }
2419 \f
2420 /* Initialize variables for region data dependence analysis.
2421    n_bbs is the number of region blocks.  */
2422
2423 void
2424 init_deps (struct deps *deps)
2425 {
2426   int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
2427
2428   deps->max_reg = max_reg;
2429   deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
2430   INIT_REG_SET (&deps->reg_last_in_use);
2431   INIT_REG_SET (&deps->reg_conditional_sets);
2432
2433   deps->pending_read_insns = 0;
2434   deps->pending_read_mems = 0;
2435   deps->pending_write_insns = 0;
2436   deps->pending_write_mems = 0;
2437   deps->pending_read_list_length = 0;
2438   deps->pending_write_list_length = 0;
2439   deps->pending_flush_length = 0;
2440   deps->last_pending_memory_flush = 0;
2441   deps->last_function_call = 0;
2442   deps->sched_before_next_call = 0;
2443   deps->in_post_call_group_p = not_post_call;
2444 }
2445
2446 /* Free insn lists found in DEPS.  */
2447
2448 void
2449 free_deps (struct deps *deps)
2450 {
2451   unsigned i;
2452   reg_set_iterator rsi;
2453
2454   free_INSN_LIST_list (&deps->pending_read_insns);
2455   free_EXPR_LIST_list (&deps->pending_read_mems);
2456   free_INSN_LIST_list (&deps->pending_write_insns);
2457   free_EXPR_LIST_list (&deps->pending_write_mems);
2458   free_INSN_LIST_list (&deps->last_pending_memory_flush);
2459
2460   /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
2461      times.  For a testcase with 42000 regs and 8000 small basic blocks,
2462      this loop accounted for nearly 60% (84 sec) of the total -O2 runtime.  */
2463   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
2464     {
2465       struct deps_reg *reg_last = &deps->reg_last[i];
2466       if (reg_last->uses)
2467         free_INSN_LIST_list (&reg_last->uses);
2468       if (reg_last->sets)
2469         free_INSN_LIST_list (&reg_last->sets);
2470       if (reg_last->clobbers)
2471         free_INSN_LIST_list (&reg_last->clobbers);
2472     }
2473   CLEAR_REG_SET (&deps->reg_last_in_use);
2474   CLEAR_REG_SET (&deps->reg_conditional_sets);
2475
2476   free (deps->reg_last);
2477 }
2478
2479 /* If it is profitable to use them, initialize caches for tracking
2480    dependency information.  LUID is the number of insns to be scheduled,
2481    it is used in the estimate of profitability.  */
2482
2483 void
2484 init_dependency_caches (int luid)
2485 {
2486   /* Average number of insns in the basic block.
2487      '+ 1' is used to make it nonzero.  */
2488   int insns_in_block = luid / n_basic_blocks + 1;
2489
2490   /* ?!? We could save some memory by computing a per-region luid mapping
2491      which could reduce both the number of vectors in the cache and the size
2492      of each vector.  Instead we just avoid the cache entirely unless the
2493      average number of instructions in a basic block is very high.  See
2494      the comment before the declaration of true_dependency_cache for
2495      what we consider "very high".  */
2496   if (insns_in_block > 100 * 5)
2497     {
2498       cache_size = 0;
2499       extend_dependency_caches (luid, true);
2500     }
2501
2502   dl_pool = create_alloc_pool ("deps_list", sizeof (struct _deps_list),
2503                                /* Allocate lists for one block at a time.  */
2504                                insns_in_block);
2505
2506   dn_pool = create_alloc_pool ("dep_node", sizeof (struct _dep_node),
2507                                /* Allocate nodes for one block at a time.
2508                                   We assume that average insn has
2509                                   5 producers.  */
2510                                5 * insns_in_block);
2511 }
2512
2513 /* Create or extend (depending on CREATE_P) dependency caches to
2514    size N.  */
2515 void
2516 extend_dependency_caches (int n, bool create_p)
2517 {
2518   if (create_p || true_dependency_cache)
2519     {
2520       int i, luid = cache_size + n;
2521
2522       true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
2523                                           luid);
2524       output_dependency_cache = XRESIZEVEC (bitmap_head,
2525                                             output_dependency_cache, luid);
2526       anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
2527                                           luid);
2528
2529       if (current_sched_info->flags & DO_SPECULATION)
2530         spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
2531                                             luid);
2532
2533       for (i = cache_size; i < luid; i++)
2534         {
2535           bitmap_initialize (&true_dependency_cache[i], 0);
2536           bitmap_initialize (&output_dependency_cache[i], 0);
2537           bitmap_initialize (&anti_dependency_cache[i], 0);
2538
2539           if (current_sched_info->flags & DO_SPECULATION)
2540             bitmap_initialize (&spec_dependency_cache[i], 0);
2541         }
2542       cache_size = luid;
2543     }
2544 }
2545
2546 /* Free the caches allocated in init_dependency_caches.  */
2547
2548 void
2549 free_dependency_caches (void)
2550 {
2551   gcc_assert (deps_pools_are_empty_p ());
2552   free_alloc_pool_if_empty (&dn_pool);
2553   free_alloc_pool_if_empty (&dl_pool);
2554   gcc_assert (dn_pool == NULL && dl_pool == NULL);
2555
2556   if (true_dependency_cache)
2557     {
2558       int i;
2559
2560       for (i = 0; i < cache_size; i++)
2561         {
2562           bitmap_clear (&true_dependency_cache[i]);
2563           bitmap_clear (&output_dependency_cache[i]);
2564           bitmap_clear (&anti_dependency_cache[i]);
2565
2566           if (current_sched_info->flags & DO_SPECULATION)
2567             bitmap_clear (&spec_dependency_cache[i]);
2568         }
2569       free (true_dependency_cache);
2570       true_dependency_cache = NULL;
2571       free (output_dependency_cache);
2572       output_dependency_cache = NULL;
2573       free (anti_dependency_cache);
2574       anti_dependency_cache = NULL;
2575
2576       if (current_sched_info->flags & DO_SPECULATION)
2577         {
2578           free (spec_dependency_cache);
2579           spec_dependency_cache = NULL;
2580         }
2581     }
2582 }
2583
2584 /* Initialize some global variables needed by the dependency analysis
2585    code.  */
2586
2587 void
2588 init_deps_global (void)
2589 {
2590   reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
2591   reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
2592   reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
2593   reg_pending_barrier = NOT_A_BARRIER;
2594 }
2595
2596 /* Free everything used by the dependency analysis code.  */
2597
2598 void
2599 finish_deps_global (void)
2600 {
2601   FREE_REG_SET (reg_pending_sets);
2602   FREE_REG_SET (reg_pending_clobbers);
2603   FREE_REG_SET (reg_pending_uses);
2604 }
2605
2606 /* Estimate the weakness of dependence between MEM1 and MEM2.  */
2607 static dw_t
2608 estimate_dep_weak (rtx mem1, rtx mem2)
2609 {
2610   rtx r1, r2;
2611
2612   if (mem1 == mem2)
2613     /* MEMs are the same - don't speculate.  */
2614     return MIN_DEP_WEAK;
2615
2616   r1 = XEXP (mem1, 0);
2617   r2 = XEXP (mem2, 0);
2618
2619   if (r1 == r2
2620       || (REG_P (r1) && REG_P (r2)
2621           && REGNO (r1) == REGNO (r2)))
2622     /* Again, MEMs are the same.  */
2623     return MIN_DEP_WEAK;
2624   else if ((REG_P (r1) && !REG_P (r2))
2625            || (!REG_P (r1) && REG_P (r2)))
2626     /* Different addressing modes - reason to be more speculative,
2627        than usual.  */
2628     return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
2629   else
2630     /* We can't say anything about the dependence.  */
2631     return UNCERTAIN_DEP_WEAK;
2632 }
2633
2634 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
2635    This function can handle same INSN and ELEM (INSN == ELEM).
2636    It is a convenience wrapper.  */
2637 void
2638 add_dependence (rtx insn, rtx elem, enum reg_note dep_type)
2639 {
2640   dep_def _dep, *dep = &_dep;
2641
2642   init_dep (dep, elem, insn, dep_type);
2643   maybe_add_or_update_dep_1 (dep, false, NULL_RTX, NULL_RTX);
2644 }
2645
2646 /* Return weakness of speculative type TYPE in the dep_status DS.  */
2647 static dw_t
2648 get_dep_weak_1 (ds_t ds, ds_t type)
2649 {
2650   ds = ds & type;
2651   switch (type)
2652     {
2653     case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
2654     case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
2655     case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
2656     case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
2657     default: gcc_unreachable ();
2658     }
2659
2660   return (dw_t) ds;
2661 }
2662
2663 /* Return weakness of speculative type TYPE in the dep_status DS.  */
2664 dw_t
2665 get_dep_weak (ds_t ds, ds_t type)
2666 {
2667   dw_t dw = get_dep_weak_1 (ds, type);
2668
2669   gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
2670
2671   return dw;
2672 }
2673
2674 /* Return the dep_status, which has the same parameters as DS, except for
2675    speculative type TYPE, that will have weakness DW.  */
2676 ds_t
2677 set_dep_weak (ds_t ds, ds_t type, dw_t dw)
2678 {
2679   gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
2680
2681   ds &= ~type;
2682   switch (type)
2683     {
2684     case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
2685     case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
2686     case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
2687     case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
2688     default: gcc_unreachable ();
2689     }
2690   return ds;
2691 }
2692
2693 /* Return the join of two dep_statuses DS1 and DS2.  */
2694 ds_t
2695 ds_merge (ds_t ds1, ds_t ds2)
2696 {
2697   ds_t ds, t;
2698
2699   gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
2700
2701   ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
2702
2703   t = FIRST_SPEC_TYPE;
2704   do
2705     {
2706       if ((ds1 & t) && !(ds2 & t))
2707         ds |= ds1 & t;
2708       else if (!(ds1 & t) && (ds2 & t))
2709         ds |= ds2 & t;
2710       else if ((ds1 & t) && (ds2 & t))
2711         {
2712           ds_t dw;
2713
2714           dw = ((ds_t) get_dep_weak (ds1, t)) * ((ds_t) get_dep_weak (ds2, t));
2715           dw /= MAX_DEP_WEAK;
2716           if (dw < MIN_DEP_WEAK)
2717             dw = MIN_DEP_WEAK;
2718
2719           ds = set_dep_weak (ds, t, (dw_t) dw);
2720         }
2721
2722       if (t == LAST_SPEC_TYPE)
2723         break;
2724       t <<= SPEC_TYPE_SHIFT;
2725     }
2726   while (1);
2727
2728   return ds;
2729 }
2730
2731 /* Dump information about the dependence status S.  */
2732 static void
2733 dump_ds (FILE *f, ds_t s)
2734 {
2735   fprintf (f, "{");
2736
2737   if (s & BEGIN_DATA)
2738     fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak_1 (s, BEGIN_DATA));
2739   if (s & BE_IN_DATA)
2740     fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak_1 (s, BE_IN_DATA));
2741   if (s & BEGIN_CONTROL)
2742     fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s, BEGIN_CONTROL));
2743   if (s & BE_IN_CONTROL)
2744     fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s, BE_IN_CONTROL));
2745
2746   if (s & HARD_DEP)
2747     fprintf (f, "HARD_DEP; ");
2748
2749   if (s & DEP_TRUE)
2750     fprintf (f, "DEP_TRUE; ");
2751   if (s & DEP_ANTI)
2752     fprintf (f, "DEP_ANTI; ");
2753   if (s & DEP_OUTPUT)
2754     fprintf (f, "DEP_OUTPUT; ");
2755
2756   fprintf (f, "}");
2757 }
2758
2759 void
2760 debug_ds (ds_t s)
2761 {
2762   dump_ds (stderr, s);
2763   fprintf (stderr, "\n");
2764 }
2765
2766 #ifdef ENABLE_CHECKING
2767 /* Verify that dependence type and status are consistent.
2768    If RELAXED_P is true, then skip dep_weakness checks.  */
2769 static void
2770 check_dep (dep_t dep, bool relaxed_p)
2771 {
2772   enum reg_note dt = DEP_TYPE (dep);
2773   ds_t ds = DEP_STATUS (dep);
2774
2775   gcc_assert (DEP_PRO (dep) != DEP_CON (dep));
2776
2777   if (!(current_sched_info->flags & USE_DEPS_LIST))
2778     {
2779       gcc_assert (ds == -1);
2780       return;
2781     }
2782
2783   /* Check that dependence type contains the same bits as the status.  */
2784   if (dt == REG_DEP_TRUE)
2785     gcc_assert (ds & DEP_TRUE);
2786   else if (dt == REG_DEP_OUTPUT)
2787     gcc_assert ((ds & DEP_OUTPUT)
2788                 && !(ds & DEP_TRUE));
2789   else
2790     gcc_assert ((dt == REG_DEP_ANTI)
2791                 && (ds & DEP_ANTI)
2792                 && !(ds & (DEP_OUTPUT | DEP_TRUE)));
2793
2794   /* HARD_DEP can not appear in dep_status of a link.  */
2795   gcc_assert (!(ds & HARD_DEP));
2796
2797   /* Check that dependence status is set correctly when speculation is not
2798      supported.  */
2799   if (!(current_sched_info->flags & DO_SPECULATION))
2800     gcc_assert (!(ds & SPECULATIVE));
2801   else if (ds & SPECULATIVE)
2802     {
2803       if (!relaxed_p)
2804         {
2805           ds_t type = FIRST_SPEC_TYPE;
2806
2807           /* Check that dependence weakness is in proper range.  */
2808           do
2809             {
2810               if (ds & type)
2811                 get_dep_weak (ds, type);
2812
2813               if (type == LAST_SPEC_TYPE)
2814                 break;
2815               type <<= SPEC_TYPE_SHIFT;
2816             }
2817           while (1);
2818         }
2819
2820       if (ds & BEGIN_SPEC)
2821         {
2822           /* Only true dependence can be data speculative.  */
2823           if (ds & BEGIN_DATA)
2824             gcc_assert (ds & DEP_TRUE);
2825
2826           /* Control dependencies in the insn scheduler are represented by
2827              anti-dependencies, therefore only anti dependence can be
2828              control speculative.  */
2829           if (ds & BEGIN_CONTROL)
2830             gcc_assert (ds & DEP_ANTI);
2831         }
2832       else
2833         {
2834           /* Subsequent speculations should resolve true dependencies.  */
2835           gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
2836         }
2837
2838       /* Check that true and anti dependencies can't have other speculative
2839          statuses.  */
2840       if (ds & DEP_TRUE)
2841         gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
2842       /* An output dependence can't be speculative at all.  */
2843       gcc_assert (!(ds & DEP_OUTPUT));
2844       if (ds & DEP_ANTI)
2845         gcc_assert (ds & BEGIN_CONTROL);
2846     }
2847 }
2848 #endif /* ENABLE_CHECKING */
2849
2850 #endif /* INSN_SCHEDULING */