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 Free Software Foundation, Inc.
   5    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
   6    and currently maintained by, Jim Wilson (wilson@cygnus.com)
   7
   8 This file is part of GCC.
   9
  10 GCC is free software; you can redistribute it and/or modify it under
  11 the terms of the GNU General Public License as published by the Free
  12 Software Foundation; either version 2, or (at your option) any later
  13 version.
  14
  15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  17 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  18 for more details.
  19
  20 You should have received a copy of the GNU General Public License
  21 along with GCC; see the file COPYING.  If not, write to the Free
  22 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  23 02110-1301, USA.  */
  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 #include "df.h"
  45
  46
  47 static regset reg_pending_sets;
  48 static regset reg_pending_clobbers;
  49 static regset reg_pending_uses;
  50
  51 /* The following enumeration values tell us what dependencies we
  52    should use to implement the barrier.  We use true-dependencies for
  53    TRUE_BARRIER and anti-dependencies for MOVE_BARRIER.  */
  54 enum reg_pending_barrier_mode
  55 {
  56   NOT_A_BARRIER = 0,
  57   MOVE_BARRIER,
  58   TRUE_BARRIER
  59 };
  60
  61 static enum reg_pending_barrier_mode reg_pending_barrier;
  62
  63 /* To speed up the test for duplicate dependency links we keep a
  64    record of dependencies created by add_dependence when the average
  65    number of instructions in a basic block is very large.
  66
  67    Studies have shown that there is typically around 5 instructions between
  68    branches for typical C code.  So we can make a guess that the average
  69    basic block is approximately 5 instructions long; we will choose 100X
  70    the average size as a very large basic block.
  71
  72    Each insn has associated bitmaps for its dependencies.  Each bitmap
  73    has enough entries to represent a dependency on any other insn in
  74    the insn chain.  All bitmap for true dependencies cache is
  75    allocated then the rest two ones are also allocated.  */
  76 static bitmap_head *true_dependency_cache;
  77 static bitmap_head *anti_dependency_cache;
  78 static bitmap_head *output_dependency_cache;
  79 static int cache_size;
  80
  81 /* To speed up checking consistency of formed forward insn
  82    dependencies we use the following cache.  Another possible solution
  83    could be switching off checking duplication of insns in forward
  84    dependencies.  */
  85 #ifdef ENABLE_CHECKING
  86 static bitmap_head *forward_dependency_cache;
  87 #endif
  88
  89 static int deps_may_trap_p (rtx);
  90 static void add_dependence_list (rtx, rtx, enum reg_note);
  91 static void add_dependence_list_and_free (rtx, rtx *, enum reg_note);
  92 static void delete_all_dependences (rtx);
  93 static void fixup_sched_groups (rtx);
  94
  95 static void flush_pending_lists (struct deps *, rtx, int, int);
  96 static void sched_analyze_1 (struct deps *, rtx, rtx);
  97 static void sched_analyze_2 (struct deps *, rtx, rtx);
  98 static void sched_analyze_insn (struct deps *, rtx, rtx, rtx);
  99
 100 static rtx sched_get_condition (rtx);
 101 static int conditions_mutex_p (rtx, rtx);
 102 \f
 103 /* Return nonzero if a load of the memory reference MEM can cause a trap.  */
 104
 105 static int
 106 deps_may_trap_p (rtx mem)
 107 {
 108   rtx addr = XEXP (mem, 0);
 109
 110   if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
 111     {
 112       rtx t = get_reg_known_value (REGNO (addr));
 113       if (t)
 114         addr = t;
 115     }
 116   return rtx_addr_can_trap_p (addr);
 117 }
 118 \f
 119 /* Return the INSN_LIST containing INSN in LIST, or NULL
 120    if LIST does not contain INSN.  */
 121
 122 rtx
 123 find_insn_list (rtx insn, rtx list)
 124 {
 125   while (list)
 126     {
 127       if (XEXP (list, 0) == insn)
 128         return list;
 129       list = XEXP (list, 1);
 130     }
 131   return 0;
 132 }
 133 \f
 134 /* Find the condition under which INSN is executed.  */
 135
 136 static rtx
 137 sched_get_condition (rtx insn)
 138 {
 139   rtx pat = PATTERN (insn);
 140   rtx src;
 141
 142   if (pat == 0)
 143     return 0;
 144
 145   if (GET_CODE (pat) == COND_EXEC)
 146     return COND_EXEC_TEST (pat);
 147
 148   if (!any_condjump_p (insn) || !onlyjump_p (insn))
 149     return 0;
 150
 151   src = SET_SRC (pc_set (insn));
 152
 153   if (XEXP (src, 2) == pc_rtx)
 154     return XEXP (src, 0);
 155   else if (XEXP (src, 1) == pc_rtx)
 156     {
 157       rtx cond = XEXP (src, 0);
 158       enum rtx_code revcode = reversed_comparison_code (cond, insn);
 159
 160       if (revcode == UNKNOWN)
 161         return 0;
 162       return gen_rtx_fmt_ee (revcode, GET_MODE (cond), XEXP (cond, 0),
 163                              XEXP (cond, 1));
 164     }
 165
 166   return 0;
 167 }
 168
 169 \f
 170 /* Return nonzero if conditions COND1 and COND2 can never be both true.  */
 171
 172 static int
 173 conditions_mutex_p (rtx cond1, rtx cond2)
 174 {
 175   if (COMPARISON_P (cond1)
 176       && COMPARISON_P (cond2)
 177       && GET_CODE (cond1) == reversed_comparison_code (cond2, NULL)
 178       && XEXP (cond1, 0) == XEXP (cond2, 0)
 179       && XEXP (cond1, 1) == XEXP (cond2, 1))
 180     return 1;
 181   return 0;
 182 }
 183
 184 /* Return true if insn1 and insn2 can never depend on one another because
 185    the conditions under which they are executed are mutually exclusive.  */
 186 bool
 187 sched_insns_conditions_mutex_p (rtx insn1, rtx insn2)
 188 {
 189   rtx cond1, cond2;
 190
 191   /* flow.c doesn't handle conditional lifetimes entirely correctly;
 192      calls mess up the conditional lifetimes.  */
 193   if (!CALL_P (insn1) && !CALL_P (insn2))
 194     {
 195       cond1 = sched_get_condition (insn1);
 196       cond2 = sched_get_condition (insn2);
 197       if (cond1 && cond2
 198           && conditions_mutex_p (cond1, cond2)
 199           /* Make sure first instruction doesn't affect condition of second
 200              instruction if switched.  */
 201           && !modified_in_p (cond1, insn2)
 202           /* Make sure second instruction doesn't affect condition of first
 203              instruction if switched.  */
 204           && !modified_in_p (cond2, insn1))
 205         return true;
 206     }
 207   return false;
 208 }
 209 \f
 210 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
 211    LOG_LINKS of INSN, if not already there.  DEP_TYPE indicates the
 212    type of dependence that this link represents.  The function returns
 213    nonzero if a new entry has been added to insn's LOG_LINK.  */
 214
 215 int
 216 add_dependence (rtx insn, rtx elem, enum reg_note dep_type)
 217 {
 218   rtx link;
 219   int present_p;
 220
 221   /* Don't depend an insn on itself.  */
 222   if (insn == elem)
 223     return 0;
 224
 225   /* We can get a dependency on deleted insns due to optimizations in
 226      the register allocation and reloading or due to splitting.  Any
 227      such dependency is useless and can be ignored.  */
 228   if (NOTE_P (elem))
 229     return 0;
 230
 231   present_p = 1;
 232 #ifdef INSN_SCHEDULING
 233   /* ??? No good way to tell from here whether we're doing interblock
 234      scheduling.  Possibly add another callback.  */
 235 #if 0
 236   /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
 237      No need for interblock dependences with calls, since
 238      calls are not moved between blocks.   Note: the edge where
 239      elem is a CALL is still required.  */
 240   if (CALL_P (insn)
 241       && (INSN_BB (elem) != INSN_BB (insn)))
 242     return 0;
 243 #endif
 244
 245   /* If we already have a dependency for ELEM, then we do not need to
 246      do anything.  Avoiding the list walk below can cut compile times
 247      dramatically for some code.  */
 248   if (true_dependency_cache != NULL)
 249     {
 250       enum reg_note present_dep_type = 0;
 251
 252       gcc_assert (anti_dependency_cache);
 253       gcc_assert (output_dependency_cache);
 254       if (bitmap_bit_p (&true_dependency_cache[INSN_LUID (insn)],
 255                         INSN_LUID (elem)))
 256         /* Do nothing (present_set_type is already 0).  */
 257         ;
 258       else if (bitmap_bit_p (&anti_dependency_cache[INSN_LUID (insn)],
 259                          INSN_LUID (elem)))
 260         present_dep_type = REG_DEP_ANTI;
 261       else if (bitmap_bit_p (&output_dependency_cache[INSN_LUID (insn)],
 262                          INSN_LUID (elem)))
 263         present_dep_type = REG_DEP_OUTPUT;
 264       else
 265         present_p = 0;
 266       if (present_p && (int) dep_type >= (int) present_dep_type)
 267         return 0;
 268     }
 269 #endif
 270
 271   /* Check that we don't already have this dependence.  */
 272   if (present_p)
 273     for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
 274       if (XEXP (link, 0) == elem)
 275         {
 276 #ifdef INSN_SCHEDULING
 277           /* Clear corresponding cache entry because type of the link
 278              may be changed.  */
 279           if (true_dependency_cache != NULL)
 280             {
 281               enum reg_note kind = REG_NOTE_KIND (link);
 282               switch (kind)
 283                 {
 284                 case REG_DEP_ANTI:
 285                   bitmap_clear_bit (&anti_dependency_cache[INSN_LUID (insn)],
 286                                     INSN_LUID (elem));
 287                   break;
 288                 case REG_DEP_OUTPUT:
 289                   gcc_assert (output_dependency_cache);
 290                   bitmap_clear_bit (&output_dependency_cache[INSN_LUID (insn)],
 291                                     INSN_LUID (elem));
 292                   break;
 293                 default:
 294                   gcc_unreachable ();
 295                 }
 296             }
 297 #endif
 298
 299           /* If this is a more restrictive type of dependence than the existing
 300              one, then change the existing dependence to this type.  */
 301           if ((int) dep_type < (int) REG_NOTE_KIND (link))
 302             PUT_REG_NOTE_KIND (link, dep_type);
 303
 304 #ifdef INSN_SCHEDULING
 305           /* If we are adding a dependency to INSN's LOG_LINKs, then
 306              note that in the bitmap caches of dependency information.  */
 307           if (true_dependency_cache != NULL)
 308             {
 309               if ((int) REG_NOTE_KIND (link) == 0)
 310                 bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)],
 311                                 INSN_LUID (elem));
 312               else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
 313                 bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)],
 314                                 INSN_LUID (elem));
 315               else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
 316                 bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)],
 317                                 INSN_LUID (elem));
 318             }
 319 #endif
 320           return 0;
 321         }
 322   /* Might want to check one level of transitivity to save conses.  */
 323
 324   link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
 325   LOG_LINKS (insn) = link;
 326
 327   /* Insn dependency, not data dependency.  */
 328   PUT_REG_NOTE_KIND (link, dep_type);
 329
 330 #ifdef INSN_SCHEDULING
 331   /* If we are adding a dependency to INSN's LOG_LINKs, then note that
 332      in the bitmap caches of dependency information.  */
 333   if (true_dependency_cache != NULL)
 334     {
 335       if ((int) dep_type == 0)
 336         bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
 337       else if (dep_type == REG_DEP_ANTI)
 338         bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
 339       else if (dep_type == REG_DEP_OUTPUT)
 340         bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
 341     }
 342 #endif
 343   return 1;
 344 }
 345
 346 /* A convenience wrapper to operate on an entire list.  */
 347
 348 static void
 349 add_dependence_list (rtx insn, rtx list, enum reg_note dep_type)
 350 {
 351   for (; list; list = XEXP (list, 1))
 352     {
 353       if (! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
 354         add_dependence (insn, XEXP (list, 0), dep_type);
 355     }
 356 }
 357
 358 /* Similar, but free *LISTP at the same time.  */
 359
 360 static void
 361 add_dependence_list_and_free (rtx insn, rtx *listp, enum reg_note dep_type)
 362 {
 363   rtx list, next;
 364   for (list = *listp, *listp = NULL; list ; list = next)
 365     {
 366       next = XEXP (list, 1);
 367       if (! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
 368         add_dependence (insn, XEXP (list, 0), dep_type);
 369       free_INSN_LIST_node (list);
 370     }
 371 }
 372
 373 /* Clear all dependencies for an insn.  */
 374
 375 static void
 376 delete_all_dependences (rtx insn)
 377 {
 378   /* Clear caches, if they exist, as well as free the dependence.  */
 379
 380 #ifdef INSN_SCHEDULING
 381   if (true_dependency_cache != NULL)
 382     {
 383       bitmap_clear (&true_dependency_cache[INSN_LUID (insn)]);
 384       bitmap_clear (&anti_dependency_cache[INSN_LUID (insn)]);
 385       bitmap_clear (&output_dependency_cache[INSN_LUID (insn)]);
 386     }
 387 #endif
 388
 389   free_INSN_LIST_list (&LOG_LINKS (insn));
 390 }
 391
 392 /* All insns in a scheduling group except the first should only have
 393    dependencies on the previous insn in the group.  So we find the
 394    first instruction in the scheduling group by walking the dependence
 395    chains backwards. Then we add the dependencies for the group to
 396    the previous nonnote insn.  */
 397
 398 static void
 399 fixup_sched_groups (rtx insn)
 400 {
 401   rtx link, prev_nonnote;
 402
 403   for (link = LOG_LINKS (insn); link ; link = XEXP (link, 1))
 404     {
 405       rtx i = insn;
 406       do
 407         {
 408           i = prev_nonnote_insn (i);
 409
 410           if (XEXP (link, 0) == i)
 411             goto next_link;
 412         } while (SCHED_GROUP_P (i));
 413       if (! sched_insns_conditions_mutex_p (i, XEXP (link, 0)))
 414         add_dependence (i, XEXP (link, 0), REG_NOTE_KIND (link));
 415     next_link:;
 416     }
 417
 418   delete_all_dependences (insn);
 419
 420   prev_nonnote = prev_nonnote_insn (insn);
 421   if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
 422       && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
 423     add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
 424 }
 425 \f
 426 /* Process an insn's memory dependencies.  There are four kinds of
 427    dependencies:
 428
 429    (0) read dependence: read follows read
 430    (1) true dependence: read follows write
 431    (2) anti dependence: write follows read
 432    (3) output dependence: write follows write
 433
 434    We are careful to build only dependencies which actually exist, and
 435    use transitivity to avoid building too many links.  */
 436
 437 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
 438    The MEM is a memory reference contained within INSN, which we are saving
 439    so that we can do memory aliasing on it.  */
 440
 441 static void
 442 add_insn_mem_dependence (struct deps *deps, rtx *insn_list, rtx *mem_list,
 443                          rtx insn, rtx mem)
 444 {
 445   rtx link;
 446
 447   link = alloc_INSN_LIST (insn, *insn_list);
 448   *insn_list = link;
 449
 450   if (current_sched_info->use_cselib)
 451     {
 452       mem = shallow_copy_rtx (mem);
 453       XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0));
 454     }
 455   link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
 456   *mem_list = link;
 457
 458   deps->pending_lists_length++;
 459 }
 460
 461 /* Make a dependency between every memory reference on the pending lists
 462    and INSN, thus flushing the pending lists.  FOR_READ is true if emitting
 463    dependencies for a read operation, similarly with FOR_WRITE.  */
 464
 465 static void
 466 flush_pending_lists (struct deps *deps, rtx insn, int for_read,
 467                      int for_write)
 468 {
 469   if (for_write)
 470     {
 471       add_dependence_list_and_free (insn, &deps->pending_read_insns,
 472                                     REG_DEP_ANTI);
 473       free_EXPR_LIST_list (&deps->pending_read_mems);
 474     }
 475
 476   add_dependence_list_and_free (insn, &deps->pending_write_insns,
 477                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
 478   free_EXPR_LIST_list (&deps->pending_write_mems);
 479   deps->pending_lists_length = 0;
 480
 481   add_dependence_list_and_free (insn, &deps->last_pending_memory_flush,
 482                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
 483   deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
 484   deps->pending_flush_length = 1;
 485 }
 486 \f
 487 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
 488    rtx, X, creating all dependencies generated by the write to the
 489    destination of X, and reads of everything mentioned.  */
 490
 491 static void
 492 sched_analyze_1 (struct deps *deps, rtx x, rtx insn)
 493 {
 494   int regno;
 495   rtx dest = XEXP (x, 0);
 496   enum rtx_code code = GET_CODE (x);
 497
 498   if (dest == 0)
 499     return;
 500
 501   if (GET_CODE (dest) == PARALLEL)
 502     {
 503       int i;
 504
 505       for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
 506         if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
 507           sched_analyze_1 (deps,
 508                            gen_rtx_CLOBBER (VOIDmode,
 509                                             XEXP (XVECEXP (dest, 0, i), 0)),
 510                            insn);
 511
 512       if (GET_CODE (x) == SET)
 513         sched_analyze_2 (deps, SET_SRC (x), insn);
 514       return;
 515     }
 516
 517   while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
 518          || GET_CODE (dest) == ZERO_EXTRACT)
 519     {
 520       if (GET_CODE (dest) == STRICT_LOW_PART
 521          || GET_CODE (dest) == ZERO_EXTRACT
 522          || read_modify_subreg_p (dest))
 523         {
 524           /* These both read and modify the result.  We must handle
 525              them as writes to get proper dependencies for following
 526              instructions.  We must handle them as reads to get proper
 527              dependencies from this to previous instructions.
 528              Thus we need to call sched_analyze_2.  */
 529
 530           sched_analyze_2 (deps, XEXP (dest, 0), insn);
 531         }
 532       if (GET_CODE (dest) == ZERO_EXTRACT)
 533         {
 534           /* The second and third arguments are values read by this insn.  */
 535           sched_analyze_2 (deps, XEXP (dest, 1), insn);
 536           sched_analyze_2 (deps, XEXP (dest, 2), insn);
 537         }
 538       dest = XEXP (dest, 0);
 539     }
 540
 541   if (REG_P (dest))
 542     {
 543       regno = REGNO (dest);
 544
 545 #ifdef STACK_REGS
 546       /* Treat all writes to a stack register as modifying the TOS.  */
 547       if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
 548         {
 549           SET_REGNO_REG_SET (reg_pending_uses, FIRST_STACK_REG);
 550           regno = FIRST_STACK_REG;
 551         }
 552 #endif
 553
 554       /* A hard reg in a wide mode may really be multiple registers.
 555          If so, mark all of them just like the first.  */
 556       if (regno < FIRST_PSEUDO_REGISTER)
 557         {
 558           int i = hard_regno_nregs[regno][GET_MODE (dest)];
 559           if (code == SET)
 560             {
 561               while (--i >= 0)
 562                 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
 563             }
 564           else
 565             {
 566               while (--i >= 0)
 567                 SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
 568             }
 569         }
 570       /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
 571          it does not reload.  Ignore these as they have served their
 572          purpose already.  */
 573       else if (regno >= deps->max_reg)
 574         {
 575           gcc_assert (GET_CODE (PATTERN (insn)) == USE
 576                       || GET_CODE (PATTERN (insn)) == CLOBBER);
 577         }
 578       else
 579         {
 580           if (code == SET)
 581             SET_REGNO_REG_SET (reg_pending_sets, regno);
 582           else
 583             SET_REGNO_REG_SET (reg_pending_clobbers, regno);
 584
 585           /* Pseudos that are REG_EQUIV to something may be replaced
 586              by that during reloading.  We need only add dependencies for
 587              the address in the REG_EQUIV note.  */
 588           if (!reload_completed && get_reg_known_equiv_p (regno))
 589             {
 590               rtx t = get_reg_known_value (regno);
 591               if (MEM_P (t))
 592                 sched_analyze_2 (deps, XEXP (t, 0), insn);
 593             }
 594
 595           /* Don't let it cross a call after scheduling if it doesn't
 596              already cross one.  */
 597           if (REG_N_CALLS_CROSSED (regno) == 0)
 598             add_dependence_list (insn, deps->last_function_call, REG_DEP_ANTI);
 599         }
 600     }
 601   else if (MEM_P (dest))
 602     {
 603       /* Writing memory.  */
 604       rtx t = dest;
 605
 606       if (current_sched_info->use_cselib)
 607         {
 608           t = shallow_copy_rtx (dest);
 609           cselib_lookup (XEXP (t, 0), Pmode, 1);
 610           XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
 611         }
 612       t = canon_rtx (t);
 613
 614       if (deps->pending_lists_length > MAX_PENDING_LIST_LENGTH)
 615         {
 616           /* Flush all pending reads and writes to prevent the pending lists
 617              from getting any larger.  Insn scheduling runs too slowly when
 618              these lists get long.  When compiling GCC with itself,
 619              this flush occurs 8 times for sparc, and 10 times for m88k using
 620              the default value of 32.  */
 621           flush_pending_lists (deps, insn, false, true);
 622         }
 623       else
 624         {
 625           rtx pending, pending_mem;
 626
 627           pending = deps->pending_read_insns;
 628           pending_mem = deps->pending_read_mems;
 629           while (pending)
 630             {
 631               if (anti_dependence (XEXP (pending_mem, 0), t)
 632                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
 633                 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
 634
 635               pending = XEXP (pending, 1);
 636               pending_mem = XEXP (pending_mem, 1);
 637             }
 638
 639           pending = deps->pending_write_insns;
 640           pending_mem = deps->pending_write_mems;
 641           while (pending)
 642             {
 643               if (output_dependence (XEXP (pending_mem, 0), t)
 644                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
 645                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
 646
 647               pending = XEXP (pending, 1);
 648               pending_mem = XEXP (pending_mem, 1);
 649             }
 650
 651           add_dependence_list (insn, deps->last_pending_memory_flush,
 652                                REG_DEP_ANTI);
 653
 654           add_insn_mem_dependence (deps, &deps->pending_write_insns,
 655                                    &deps->pending_write_mems, insn, dest);
 656         }
 657       sched_analyze_2 (deps, XEXP (dest, 0), insn);
 658     }
 659
 660   /* Analyze reads.  */
 661   if (GET_CODE (x) == SET)
 662     sched_analyze_2 (deps, SET_SRC (x), insn);
 663 }
 664
 665 /* Analyze the uses of memory and registers in rtx X in INSN.  */
 666
 667 static void
 668 sched_analyze_2 (struct deps *deps, rtx x, rtx insn)
 669 {
 670   int i;
 671   int j;
 672   enum rtx_code code;
 673   const char *fmt;
 674
 675   if (x == 0)
 676     return;
 677
 678   code = GET_CODE (x);
 679
 680   switch (code)
 681     {
 682     case CONST_INT:
 683     case CONST_DOUBLE:
 684     case CONST_VECTOR:
 685     case SYMBOL_REF:
 686     case CONST:
 687     case LABEL_REF:
 688       /* Ignore constants.  Note that we must handle CONST_DOUBLE here
 689          because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
 690          this does not mean that this insn is using cc0.  */
 691       return;
 692
 693 #ifdef HAVE_cc0
 694     case CC0:
 695       /* User of CC0 depends on immediately preceding insn.  */
 696       SCHED_GROUP_P (insn) = 1;
 697        /* Don't move CC0 setter to another block (it can set up the
 698         same flag for previous CC0 users which is safe).  */
 699       CANT_MOVE (prev_nonnote_insn (insn)) = 1;
 700       return;
 701 #endif
 702
 703     case REG:
 704       {
 705         int regno = REGNO (x);
 706
 707 #ifdef STACK_REGS
 708       /* Treat all reads of a stack register as modifying the TOS.  */
 709       if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
 710         {
 711           SET_REGNO_REG_SET (reg_pending_sets, FIRST_STACK_REG);
 712           regno = FIRST_STACK_REG;
 713         }
 714 #endif
 715
 716         if (regno < FIRST_PSEUDO_REGISTER)
 717           {
 718             int i = hard_regno_nregs[regno][GET_MODE (x)];
 719             while (--i >= 0)
 720               SET_REGNO_REG_SET (reg_pending_uses, regno + i);
 721           }
 722         /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
 723            it does not reload.  Ignore these as they have served their
 724            purpose already.  */
 725         else if (regno >= deps->max_reg)
 726           {
 727             gcc_assert (GET_CODE (PATTERN (insn)) == USE
 728                         || GET_CODE (PATTERN (insn)) == CLOBBER);
 729           }
 730         else
 731           {
 732             SET_REGNO_REG_SET (reg_pending_uses, regno);
 733
 734             /* Pseudos that are REG_EQUIV to something may be replaced
 735                by that during reloading.  We need only add dependencies for
 736                the address in the REG_EQUIV note.  */
 737             if (!reload_completed && get_reg_known_equiv_p (regno))
 738               {
 739                 rtx t = get_reg_known_value (regno);
 740                 if (MEM_P (t))
 741                   sched_analyze_2 (deps, XEXP (t, 0), insn);
 742               }
 743
 744             /* If the register does not already cross any calls, then add this
 745                insn to the sched_before_next_call list so that it will still
 746                not cross calls after scheduling.  */
 747             if (REG_N_CALLS_CROSSED (regno) == 0)
 748               deps->sched_before_next_call
 749                 = alloc_INSN_LIST (insn, deps->sched_before_next_call);
 750           }
 751         return;
 752       }
 753
 754     case MEM:
 755       {
 756         /* Reading memory.  */
 757         rtx u;
 758         rtx pending, pending_mem;
 759         rtx t = x;
 760
 761         if (current_sched_info->use_cselib)
 762           {
 763             t = shallow_copy_rtx (t);
 764             cselib_lookup (XEXP (t, 0), Pmode, 1);
 765             XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
 766           }
 767         t = canon_rtx (t);
 768         pending = deps->pending_read_insns;
 769         pending_mem = deps->pending_read_mems;
 770         while (pending)
 771           {
 772             if (read_dependence (XEXP (pending_mem, 0), t)
 773                 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
 774               add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
 775
 776             pending = XEXP (pending, 1);
 777             pending_mem = XEXP (pending_mem, 1);
 778           }
 779
 780         pending = deps->pending_write_insns;
 781         pending_mem = deps->pending_write_mems;
 782         while (pending)
 783           {
 784             if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
 785                                  t, rtx_varies_p)
 786                 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
 787               add_dependence (insn, XEXP (pending, 0), REG_DEP_TRUE);
 788
 789             pending = XEXP (pending, 1);
 790             pending_mem = XEXP (pending_mem, 1);
 791           }
 792
 793         for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
 794           if ((! JUMP_P (XEXP (u, 0)) || deps_may_trap_p (x))
 795               && ! sched_insns_conditions_mutex_p (insn, XEXP (u, 0)))
 796             add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
 797
 798         /* Always add these dependencies to pending_reads, since
 799            this insn may be followed by a write.  */
 800         add_insn_mem_dependence (deps, &deps->pending_read_insns,
 801                                  &deps->pending_read_mems, insn, x);
 802
 803         /* Take advantage of tail recursion here.  */
 804         sched_analyze_2 (deps, XEXP (x, 0), insn);
 805         return;
 806       }
 807
 808     /* Force pending stores to memory in case a trap handler needs them.  */
 809     case TRAP_IF:
 810       flush_pending_lists (deps, insn, true, false);
 811       break;
 812
 813     case ASM_OPERANDS:
 814     case ASM_INPUT:
 815     case UNSPEC_VOLATILE:
 816       {
 817         /* Traditional and volatile asm instructions must be considered to use
 818            and clobber all hard registers, all pseudo-registers and all of
 819            memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
 820
 821            Consider for instance a volatile asm that changes the fpu rounding
 822            mode.  An insn should not be moved across this even if it only uses
 823            pseudo-regs because it might give an incorrectly rounded result.  */
 824         if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
 825           reg_pending_barrier = TRUE_BARRIER;
 826
 827         /* For all ASM_OPERANDS, we must traverse the vector of input operands.
 828            We can not just fall through here since then we would be confused
 829            by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
 830            traditional asms unlike their normal usage.  */
 831
 832         if (code == ASM_OPERANDS)
 833           {
 834             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
 835               sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
 836             return;
 837           }
 838         break;
 839       }
 840
 841     case PRE_DEC:
 842     case POST_DEC:
 843     case PRE_INC:
 844     case POST_INC:
 845       /* These both read and modify the result.  We must handle them as writes
 846          to get proper dependencies for following instructions.  We must handle
 847          them as reads to get proper dependencies from this to previous
 848          instructions.  Thus we need to pass them to both sched_analyze_1
 849          and sched_analyze_2.  We must call sched_analyze_2 first in order
 850          to get the proper antecedent for the read.  */
 851       sched_analyze_2 (deps, XEXP (x, 0), insn);
 852       sched_analyze_1 (deps, x, insn);
 853       return;
 854
 855     case POST_MODIFY:
 856     case PRE_MODIFY:
 857       /* op0 = op0 + op1 */
 858       sched_analyze_2 (deps, XEXP (x, 0), insn);
 859       sched_analyze_2 (deps, XEXP (x, 1), insn);
 860       sched_analyze_1 (deps, x, insn);
 861       return;
 862
 863     default:
 864       break;
 865     }
 866
 867   /* Other cases: walk the insn.  */
 868   fmt = GET_RTX_FORMAT (code);
 869   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 870     {
 871       if (fmt[i] == 'e')
 872         sched_analyze_2 (deps, XEXP (x, i), insn);
 873       else if (fmt[i] == 'E')
 874         for (j = 0; j < XVECLEN (x, i); j++)
 875           sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
 876     }
 877 }
 878
 879 /* Analyze an INSN with pattern X to find all dependencies.  */
 880
 881 static void
 882 sched_analyze_insn (struct deps *deps, rtx x, rtx insn, rtx loop_notes)
 883 {
 884   RTX_CODE code = GET_CODE (x);
 885   rtx link;
 886   unsigned i;
 887   reg_set_iterator rsi;
 888
 889   if (code == COND_EXEC)
 890     {
 891       sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
 892
 893       /* ??? Should be recording conditions so we reduce the number of
 894          false dependencies.  */
 895       x = COND_EXEC_CODE (x);
 896       code = GET_CODE (x);
 897     }
 898   if (code == SET || code == CLOBBER)
 899     {
 900       sched_analyze_1 (deps, x, insn);
 901
 902       /* Bare clobber insns are used for letting life analysis, reg-stack
 903          and others know that a value is dead.  Depend on the last call
 904          instruction so that reg-stack won't get confused.  */
 905       if (code == CLOBBER)
 906         add_dependence_list (insn, deps->last_function_call, REG_DEP_OUTPUT);
 907     }
 908   else if (code == PARALLEL)
 909     {
 910       for (i = XVECLEN (x, 0); i--;)
 911         {
 912           rtx sub = XVECEXP (x, 0, i);
 913           code = GET_CODE (sub);
 914
 915           if (code == COND_EXEC)
 916             {
 917               sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
 918               sub = COND_EXEC_CODE (sub);
 919               code = GET_CODE (sub);
 920             }
 921           if (code == SET || code == CLOBBER)
 922             sched_analyze_1 (deps, sub, insn);
 923           else
 924             sched_analyze_2 (deps, sub, insn);
 925         }
 926     }
 927   else
 928     sched_analyze_2 (deps, x, insn);
 929
 930   /* Mark registers CLOBBERED or used by called function.  */
 931   if (CALL_P (insn))
 932     {
 933       for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
 934         {
 935           if (GET_CODE (XEXP (link, 0)) == CLOBBER)
 936             sched_analyze_1 (deps, XEXP (link, 0), insn);
 937           else
 938             sched_analyze_2 (deps, XEXP (link, 0), insn);
 939         }
 940       if (find_reg_note (insn, REG_SETJMP, NULL))
 941         reg_pending_barrier = MOVE_BARRIER;
 942     }
 943
 944   if (JUMP_P (insn))
 945     {
 946       rtx next;
 947       next = next_nonnote_insn (insn);
 948       if (next && BARRIER_P (next))
 949         reg_pending_barrier = TRUE_BARRIER;
 950       else
 951         {
 952           rtx pending, pending_mem;
 953           regset_head tmp_uses, tmp_sets;
 954           INIT_REG_SET (&tmp_uses);
 955           INIT_REG_SET (&tmp_sets);
 956
 957           (*current_sched_info->compute_jump_reg_dependencies)
 958             (insn, &deps->reg_conditional_sets, &tmp_uses, &tmp_sets);
 959           /* Make latency of jump equal to 0 by using anti-dependence.  */
 960           EXECUTE_IF_SET_IN_REG_SET (&tmp_uses, 0, i, rsi)
 961             {
 962               struct deps_reg *reg_last = &deps->reg_last[i];
 963               add_dependence_list (insn, reg_last->sets, REG_DEP_ANTI);
 964               add_dependence_list (insn, reg_last->clobbers, REG_DEP_ANTI);
 965               reg_last->uses_length++;
 966               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
 967             }
 968           IOR_REG_SET (reg_pending_sets, &tmp_sets);
 969
 970           CLEAR_REG_SET (&tmp_uses);
 971           CLEAR_REG_SET (&tmp_sets);
 972
 973           /* All memory writes and volatile reads must happen before the
 974              jump.  Non-volatile reads must happen before the jump iff
 975              the result is needed by the above register used mask.  */
 976
 977           pending = deps->pending_write_insns;
 978           pending_mem = deps->pending_write_mems;
 979           while (pending)
 980             {
 981               if (! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
 982                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
 983               pending = XEXP (pending, 1);
 984               pending_mem = XEXP (pending_mem, 1);
 985             }
 986
 987           pending = deps->pending_read_insns;
 988           pending_mem = deps->pending_read_mems;
 989           while (pending)
 990             {
 991               if (MEM_VOLATILE_P (XEXP (pending_mem, 0))
 992                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
 993                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
 994               pending = XEXP (pending, 1);
 995               pending_mem = XEXP (pending_mem, 1);
 996             }
 997
 998           add_dependence_list (insn, deps->last_pending_memory_flush,
 999                                REG_DEP_ANTI);
1000         }
1001     }
1002
1003   /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
1004      block, then we must be sure that no instructions are scheduled across it.
1005      Otherwise, the reg_n_refs info (which depends on loop_depth) would
1006      become incorrect.  */
1007   if (loop_notes)
1008     {
1009       rtx link;
1010
1011       /* Update loop_notes with any notes from this insn.  */
1012       link = loop_notes;
1013       while (XEXP (link, 1))
1014         {
1015           gcc_assert (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
1016                       || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END);
1017
1018           reg_pending_barrier = MOVE_BARRIER;
1019           link = XEXP (link, 1);
1020         }
1021       XEXP (link, 1) = REG_NOTES (insn);
1022       REG_NOTES (insn) = loop_notes;
1023     }
1024
1025   /* If this instruction can throw an exception, then moving it changes
1026      where block boundaries fall.  This is mighty confusing elsewhere.
1027      Therefore, prevent such an instruction from being moved.  */
1028   if (can_throw_internal (insn))
1029     reg_pending_barrier = MOVE_BARRIER;
1030
1031   /* Add dependencies if a scheduling barrier was found.  */
1032   if (reg_pending_barrier)
1033     {
1034       /* In the case of barrier the most added dependencies are not
1035          real, so we use anti-dependence here.  */
1036       if (sched_get_condition (insn))
1037         {
1038           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1039             {
1040               struct deps_reg *reg_last = &deps->reg_last[i];
1041               add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1042               add_dependence_list
1043                 (insn, reg_last->sets,
1044                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1045               add_dependence_list
1046                 (insn, reg_last->clobbers,
1047                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1048             }
1049         }
1050       else
1051         {
1052           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1053             {
1054               struct deps_reg *reg_last = &deps->reg_last[i];
1055               add_dependence_list_and_free (insn, &reg_last->uses,
1056                                             REG_DEP_ANTI);
1057               add_dependence_list_and_free
1058                 (insn, &reg_last->sets,
1059                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1060               add_dependence_list_and_free
1061                 (insn, &reg_last->clobbers,
1062                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1063               reg_last->uses_length = 0;
1064               reg_last->clobbers_length = 0;
1065             }
1066         }
1067
1068       for (i = 0; i < (unsigned)deps->max_reg; i++)
1069         {
1070           struct deps_reg *reg_last = &deps->reg_last[i];
1071           reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1072           SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
1073         }
1074
1075       flush_pending_lists (deps, insn, true, true);
1076       CLEAR_REG_SET (&deps->reg_conditional_sets);
1077       reg_pending_barrier = NOT_A_BARRIER;
1078     }
1079   else
1080     {
1081       /* If the current insn is conditional, we can't free any
1082          of the lists.  */
1083       if (sched_get_condition (insn))
1084         {
1085           EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1086             {
1087               struct deps_reg *reg_last = &deps->reg_last[i];
1088               add_dependence_list (insn, reg_last->sets, REG_DEP_TRUE);
1089               add_dependence_list (insn, reg_last->clobbers, REG_DEP_TRUE);
1090               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1091               reg_last->uses_length++;
1092             }
1093           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
1094             {
1095               struct deps_reg *reg_last = &deps->reg_last[i];
1096               add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1097               add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1098               reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1099               reg_last->clobbers_length++;
1100             }
1101           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
1102             {
1103               struct deps_reg *reg_last = &deps->reg_last[i];
1104               add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1105               add_dependence_list (insn, reg_last->clobbers, REG_DEP_OUTPUT);
1106               add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1107               reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1108               SET_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1109             }
1110         }
1111       else
1112         {
1113           EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1114             {
1115               struct deps_reg *reg_last = &deps->reg_last[i];
1116               add_dependence_list (insn, reg_last->sets, REG_DEP_TRUE);
1117               add_dependence_list (insn, reg_last->clobbers, REG_DEP_TRUE);
1118               reg_last->uses_length++;
1119               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1120             }
1121           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
1122             {
1123               struct deps_reg *reg_last = &deps->reg_last[i];
1124               if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
1125                   || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
1126                 {
1127                   add_dependence_list_and_free (insn, &reg_last->sets,
1128                                                 REG_DEP_OUTPUT);
1129                   add_dependence_list_and_free (insn, &reg_last->uses,
1130                                                 REG_DEP_ANTI);
1131                   add_dependence_list_and_free (insn, &reg_last->clobbers,
1132                                                 REG_DEP_OUTPUT);
1133                   reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1134                   reg_last->clobbers_length = 0;
1135                   reg_last->uses_length = 0;
1136                 }
1137               else
1138                 {
1139                   add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1140                   add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1141                 }
1142               reg_last->clobbers_length++;
1143               reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1144             }
1145           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
1146             {
1147               struct deps_reg *reg_last = &deps->reg_last[i];
1148               add_dependence_list_and_free (insn, &reg_last->sets,
1149                                             REG_DEP_OUTPUT);
1150               add_dependence_list_and_free (insn, &reg_last->clobbers,
1151                                             REG_DEP_OUTPUT);
1152               add_dependence_list_and_free (insn, &reg_last->uses,
1153                                             REG_DEP_ANTI);
1154               reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1155               reg_last->uses_length = 0;
1156               reg_last->clobbers_length = 0;
1157               CLEAR_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1158             }
1159         }
1160
1161       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
1162       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
1163       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
1164     }
1165   CLEAR_REG_SET (reg_pending_uses);
1166   CLEAR_REG_SET (reg_pending_clobbers);
1167   CLEAR_REG_SET (reg_pending_sets);
1168
1169   /* If we are currently in a libcall scheduling group, then mark the
1170      current insn as being in a scheduling group and that it can not
1171      be moved into a different basic block.  */
1172
1173   if (deps->libcall_block_tail_insn)
1174     {
1175       SCHED_GROUP_P (insn) = 1;
1176       CANT_MOVE (insn) = 1;
1177     }
1178
1179   /* If a post-call group is still open, see if it should remain so.
1180      This insn must be a simple move of a hard reg to a pseudo or
1181      vice-versa.
1182
1183      We must avoid moving these insns for correctness on
1184      SMALL_REGISTER_CLASS machines, and for special registers like
1185      PIC_OFFSET_TABLE_REGNUM.  For simplicity, extend this to all
1186      hard regs for all targets.  */
1187
1188   if (deps->in_post_call_group_p)
1189     {
1190       rtx tmp, set = single_set (insn);
1191       int src_regno, dest_regno;
1192
1193       if (set == NULL)
1194         goto end_call_group;
1195
1196       tmp = SET_DEST (set);
1197       if (GET_CODE (tmp) == SUBREG)
1198         tmp = SUBREG_REG (tmp);
1199       if (REG_P (tmp))
1200         dest_regno = REGNO (tmp);
1201       else
1202         goto end_call_group;
1203
1204       tmp = SET_SRC (set);
1205       if (GET_CODE (tmp) == SUBREG)
1206         tmp = SUBREG_REG (tmp);
1207       if ((GET_CODE (tmp) == PLUS
1208            || GET_CODE (tmp) == MINUS)
1209           && REG_P (XEXP (tmp, 0))
1210           && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
1211           && dest_regno == STACK_POINTER_REGNUM)
1212         src_regno = STACK_POINTER_REGNUM;
1213       else if (REG_P (tmp))
1214         src_regno = REGNO (tmp);
1215       else
1216         goto end_call_group;
1217
1218       if (src_regno < FIRST_PSEUDO_REGISTER
1219           || dest_regno < FIRST_PSEUDO_REGISTER)
1220         {
1221           if (deps->in_post_call_group_p == post_call_initial)
1222             deps->in_post_call_group_p = post_call;
1223
1224           SCHED_GROUP_P (insn) = 1;
1225           CANT_MOVE (insn) = 1;
1226         }
1227       else
1228         {
1229         end_call_group:
1230           deps->in_post_call_group_p = not_post_call;
1231         }
1232     }
1233
1234   /* Fixup the dependencies in the sched group.  */
1235   if (SCHED_GROUP_P (insn))
1236     fixup_sched_groups (insn);
1237 }
1238
1239 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1240    for every dependency.  */
1241
1242 void
1243 sched_analyze (struct deps *deps, rtx head, rtx tail)
1244 {
1245   rtx insn;
1246   rtx loop_notes = 0;
1247
1248   if (current_sched_info->use_cselib)
1249     cselib_init (true);
1250
1251   /* Before reload, if the previous block ended in a call, show that
1252      we are inside a post-call group, so as to keep the lifetimes of
1253      hard registers correct.  */
1254   if (! reload_completed && !LABEL_P (head))
1255     {
1256       insn = prev_nonnote_insn (head);
1257       if (insn && CALL_P (insn))
1258         deps->in_post_call_group_p = post_call_initial;
1259     }
1260   for (insn = head;; insn = NEXT_INSN (insn))
1261     {
1262       rtx link, end_seq, r0, set;
1263
1264       if (NONJUMP_INSN_P (insn) || JUMP_P (insn))
1265         {
1266           /* Clear out the stale LOG_LINKS from flow.  */
1267           free_INSN_LIST_list (&LOG_LINKS (insn));
1268
1269           /* Make each JUMP_INSN a scheduling barrier for memory
1270              references.  */
1271           if (JUMP_P (insn))
1272             {
1273               /* Keep the list a reasonable size.  */
1274               if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
1275                 flush_pending_lists (deps, insn, true, true);
1276               else
1277                 deps->last_pending_memory_flush
1278                   = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
1279             }
1280           sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1281           loop_notes = 0;
1282         }
1283       else if (CALL_P (insn))
1284         {
1285           int i;
1286
1287           CANT_MOVE (insn) = 1;
1288
1289           /* Clear out the stale LOG_LINKS from flow.  */
1290           free_INSN_LIST_list (&LOG_LINKS (insn));
1291
1292           if (find_reg_note (insn, REG_SETJMP, NULL))
1293             {
1294               /* This is setjmp.  Assume that all registers, not just
1295                  hard registers, may be clobbered by this call.  */
1296               reg_pending_barrier = MOVE_BARRIER;
1297             }
1298           else
1299             {
1300               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1301                 /* A call may read and modify global register variables.  */
1302                 if (global_regs[i])
1303                   {
1304                     SET_REGNO_REG_SET (reg_pending_sets, i);
1305                     SET_REGNO_REG_SET (reg_pending_uses, i);
1306                   }
1307                 /* Other call-clobbered hard regs may be clobbered.
1308                    Since we only have a choice between 'might be clobbered'
1309                    and 'definitely not clobbered', we must include all
1310                    partly call-clobbered registers here.  */
1311                 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
1312                          || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1313                   SET_REGNO_REG_SET (reg_pending_clobbers, i);
1314                 /* We don't know what set of fixed registers might be used
1315                    by the function, but it is certain that the stack pointer
1316                    is among them, but be conservative.  */
1317                 else if (fixed_regs[i])
1318                   SET_REGNO_REG_SET (reg_pending_uses, i);
1319                 /* The frame pointer is normally not used by the function
1320                    itself, but by the debugger.  */
1321                 /* ??? MIPS o32 is an exception.  It uses the frame pointer
1322                    in the macro expansion of jal but does not represent this
1323                    fact in the call_insn rtl.  */
1324                 else if (i == FRAME_POINTER_REGNUM
1325                          || (i == HARD_FRAME_POINTER_REGNUM
1326                              && (! reload_completed || frame_pointer_needed)))
1327                   SET_REGNO_REG_SET (reg_pending_uses, i);
1328             }
1329
1330           /* For each insn which shouldn't cross a call, add a dependence
1331              between that insn and this call insn.  */
1332           add_dependence_list_and_free (insn, &deps->sched_before_next_call,
1333                                         REG_DEP_ANTI);
1334
1335           sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1336           loop_notes = 0;
1337
1338           /* In the absence of interprocedural alias analysis, we must flush
1339              all pending reads and writes, and start new dependencies starting
1340              from here.  But only flush writes for constant calls (which may
1341              be passed a pointer to something we haven't written yet).  */
1342           flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn));
1343
1344           /* Remember the last function call for limiting lifetimes.  */
1345           free_INSN_LIST_list (&deps->last_function_call);
1346           deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
1347
1348           /* Before reload, begin a post-call group, so as to keep the
1349              lifetimes of hard registers correct.  */
1350           if (! reload_completed)
1351             deps->in_post_call_group_p = post_call;
1352         }
1353
1354       /* EH_REGION insn notes can not appear until well after we complete
1355          scheduling.  */
1356       if (NOTE_P (insn))
1357         gcc_assert (NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
1358                     && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END);
1359
1360       /* See comments on reemit_notes as to why we do this.
1361          ??? Actually, the reemit_notes just say what is done, not why.  */
1362
1363       if (NOTE_P (insn)
1364           && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
1365               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END))
1366         {
1367           loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1368                                         GEN_INT (NOTE_LINE_NUMBER (insn)),
1369                                         loop_notes);
1370           CONST_OR_PURE_CALL_P (loop_notes) = CONST_OR_PURE_CALL_P (insn);
1371         }
1372
1373       if (current_sched_info->use_cselib)
1374         cselib_process_insn (insn);
1375
1376       /* Now that we have completed handling INSN, check and see if it is
1377          a CLOBBER beginning a libcall block.   If it is, record the
1378          end of the libcall sequence.
1379
1380          We want to schedule libcall blocks as a unit before reload.  While
1381          this restricts scheduling, it preserves the meaning of a libcall
1382          block.
1383
1384          As a side effect, we may get better code due to decreased register
1385          pressure as well as less chance of a foreign insn appearing in
1386          a libcall block.  */
1387       if (!reload_completed
1388           /* Note we may have nested libcall sequences.  We only care about
1389              the outermost libcall sequence.  */
1390           && deps->libcall_block_tail_insn == 0
1391           /* The sequence must start with a clobber of a register.  */
1392           && NONJUMP_INSN_P (insn)
1393           && GET_CODE (PATTERN (insn)) == CLOBBER
1394           && (r0 = XEXP (PATTERN (insn), 0), REG_P (r0))
1395           && REG_P (XEXP (PATTERN (insn), 0))
1396           /* The CLOBBER must also have a REG_LIBCALL note attached.  */
1397           && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
1398           && (end_seq = XEXP (link, 0)) != 0
1399           /* The insn referenced by the REG_LIBCALL note must be a
1400              simple nop copy with the same destination as the register
1401              mentioned in the clobber.  */
1402           && (set = single_set (end_seq)) != 0
1403           && SET_DEST (set) == r0 && SET_SRC (set) == r0
1404           /* And finally the insn referenced by the REG_LIBCALL must
1405              also contain a REG_EQUAL note and a REG_RETVAL note.  */
1406           && find_reg_note (end_seq, REG_EQUAL, NULL_RTX) != 0
1407           && find_reg_note (end_seq, REG_RETVAL, NULL_RTX) != 0)
1408         deps->libcall_block_tail_insn = XEXP (link, 0);
1409
1410       /* If we have reached the end of a libcall block, then close the
1411          block.  */
1412       if (deps->libcall_block_tail_insn == insn)
1413         deps->libcall_block_tail_insn = 0;
1414
1415       if (insn == tail)
1416         {
1417           if (current_sched_info->use_cselib)
1418             cselib_finish ();
1419           return;
1420         }
1421     }
1422   gcc_unreachable ();
1423 }
1424 \f
1425
1426 /* The following function adds forward dependence (FROM, TO) with
1427    given DEP_TYPE.  The forward dependence should be not exist before.  */
1428
1429 void
1430 add_forward_dependence (rtx from, rtx to, enum reg_note dep_type)
1431 {
1432   rtx new_link;
1433
1434 #ifdef ENABLE_CHECKING
1435   /* If add_dependence is working properly there should never
1436      be notes, deleted insns or duplicates in the backward
1437      links.  Thus we need not check for them here.
1438
1439      However, if we have enabled checking we might as well go
1440      ahead and verify that add_dependence worked properly.  */
1441   gcc_assert (!NOTE_P (from));
1442   gcc_assert (!INSN_DELETED_P (from));
1443   if (forward_dependency_cache)
1444     gcc_assert (!bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
1445                                INSN_LUID (to)));
1446   else
1447     gcc_assert (!find_insn_list (to, INSN_DEPEND (from)));
1448
1449   /* ??? If bitmap_bit_p is a predicate, what is this supposed to do? */
1450   if (forward_dependency_cache != NULL)
1451     bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
1452                   INSN_LUID (to));
1453 #endif
1454
1455   new_link = alloc_INSN_LIST (to, INSN_DEPEND (from));
1456
1457   PUT_REG_NOTE_KIND (new_link, dep_type);
1458
1459   INSN_DEPEND (from) = new_link;
1460   INSN_DEP_COUNT (to) += 1;
1461 }
1462
1463 /* Examine insns in the range [ HEAD, TAIL ] and Use the backward
1464    dependences from LOG_LINKS to build forward dependences in
1465    INSN_DEPEND.  */
1466
1467 void
1468 compute_forward_dependences (rtx head, rtx tail)
1469 {
1470   rtx insn, link;
1471   rtx next_tail;
1472
1473   next_tail = NEXT_INSN (tail);
1474   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1475     {
1476       if (! INSN_P (insn))
1477         continue;
1478
1479       for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
1480         add_forward_dependence (XEXP (link, 0), insn, REG_NOTE_KIND (link));
1481     }
1482 }
1483 \f
1484 /* Initialize variables for region data dependence analysis.
1485    n_bbs is the number of region blocks.  */
1486
1487 void
1488 init_deps (struct deps *deps)
1489 {
1490   int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
1491
1492   deps->max_reg = max_reg;
1493   deps->reg_last = xcalloc (max_reg, sizeof (struct deps_reg));
1494   INIT_REG_SET (&deps->reg_last_in_use);
1495   INIT_REG_SET (&deps->reg_conditional_sets);
1496
1497   deps->pending_read_insns = 0;
1498   deps->pending_read_mems = 0;
1499   deps->pending_write_insns = 0;
1500   deps->pending_write_mems = 0;
1501   deps->pending_lists_length = 0;
1502   deps->pending_flush_length = 0;
1503   deps->last_pending_memory_flush = 0;
1504   deps->last_function_call = 0;
1505   deps->sched_before_next_call = 0;
1506   deps->in_post_call_group_p = not_post_call;
1507   deps->libcall_block_tail_insn = 0;
1508 }
1509
1510 /* Free insn lists found in DEPS.  */
1511
1512 void
1513 free_deps (struct deps *deps)
1514 {
1515   unsigned i;
1516   reg_set_iterator rsi;
1517
1518   free_INSN_LIST_list (&deps->pending_read_insns);
1519   free_EXPR_LIST_list (&deps->pending_read_mems);
1520   free_INSN_LIST_list (&deps->pending_write_insns);
1521   free_EXPR_LIST_list (&deps->pending_write_mems);
1522   free_INSN_LIST_list (&deps->last_pending_memory_flush);
1523
1524   /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
1525      times.  For a testcase with 42000 regs and 8000 small basic blocks,
1526      this loop accounted for nearly 60% (84 sec) of the total -O2 runtime.  */
1527   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1528     {
1529       struct deps_reg *reg_last = &deps->reg_last[i];
1530       if (reg_last->uses)
1531         free_INSN_LIST_list (&reg_last->uses);
1532       if (reg_last->sets)
1533         free_INSN_LIST_list (&reg_last->sets);
1534       if (reg_last->clobbers)
1535         free_INSN_LIST_list (&reg_last->clobbers);
1536     }
1537   CLEAR_REG_SET (&deps->reg_last_in_use);
1538   CLEAR_REG_SET (&deps->reg_conditional_sets);
1539
1540   free (deps->reg_last);
1541 }
1542
1543 /* If it is profitable to use them, initialize caches for tracking
1544    dependency information.  LUID is the number of insns to be scheduled,
1545    it is used in the estimate of profitability.  */
1546
1547 void
1548 init_dependency_caches (int luid)
1549 {
1550   /* ?!? We could save some memory by computing a per-region luid mapping
1551      which could reduce both the number of vectors in the cache and the size
1552      of each vector.  Instead we just avoid the cache entirely unless the
1553      average number of instructions in a basic block is very high.  See
1554      the comment before the declaration of true_dependency_cache for
1555      what we consider "very high".  */
1556   if (luid / n_basic_blocks > 100 * 5)
1557     {
1558       int i;
1559       true_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1560       anti_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1561       output_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1562 #ifdef ENABLE_CHECKING
1563       forward_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1564 #endif
1565       for (i = 0; i < luid; i++)
1566         {
1567           bitmap_initialize (&true_dependency_cache[i], 0);
1568           bitmap_initialize (&anti_dependency_cache[i], 0);
1569           bitmap_initialize (&output_dependency_cache[i], 0);
1570 #ifdef ENABLE_CHECKING
1571           bitmap_initialize (&forward_dependency_cache[i], 0);
1572 #endif
1573         }
1574       cache_size = luid;
1575     }
1576 }
1577
1578 /* Free the caches allocated in init_dependency_caches.  */
1579
1580 void
1581 free_dependency_caches (void)
1582 {
1583   if (true_dependency_cache)
1584     {
1585       int i;
1586
1587       for (i = 0; i < cache_size; i++)
1588         {
1589           bitmap_clear (&true_dependency_cache[i]);
1590           bitmap_clear (&anti_dependency_cache[i]);
1591           bitmap_clear (&output_dependency_cache[i]);
1592 #ifdef ENABLE_CHECKING
1593           bitmap_clear (&forward_dependency_cache[i]);
1594 #endif
1595         }
1596       free (true_dependency_cache);
1597       true_dependency_cache = NULL;
1598       free (anti_dependency_cache);
1599       anti_dependency_cache = NULL;
1600       free (output_dependency_cache);
1601       output_dependency_cache = NULL;
1602 #ifdef ENABLE_CHECKING
1603       free (forward_dependency_cache);
1604       forward_dependency_cache = NULL;
1605 #endif
1606     }
1607 }
1608
1609 /* Initialize some global variables needed by the dependency analysis
1610    code.  */
1611
1612 void
1613 init_deps_global (void)
1614 {
1615   reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
1616   reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
1617   reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
1618   reg_pending_barrier = NOT_A_BARRIER;
1619 }
1620
1621 /* Free everything used by the dependency analysis code.  */
1622
1623 void
1624 finish_deps_global (void)
1625 {
1626   FREE_REG_SET (reg_pending_sets);
1627   FREE_REG_SET (reg_pending_clobbers);
1628   FREE_REG_SET (reg_pending_uses);
1629 }