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